1.2. Линейный Дискриминантный Анализ и Квадратичный Дискриминантный Анализ¶
Линейный Дискриминантный Анализ (Linear Discriminant Analysis - LDA) (LinearDiscriminantAnalysis)
и Квадратичный Дискриминантный Анализ (Quadratic Discriminant Analysis - QDA) (QuadraticDiscriminantAnalysis)
два класса классификатора с, как следует из названия, имеют линейную и квадратичную сложностью решения.
Эти классификаторы интресны тем, что имеют решения вида “закрытого ящика”, они могут быть легко вычислены, наследуют мультиклассовость, так же доказано, что хорошо работают на практике и не имеют гиперпараметров для настройки.
График показывает границы решение для Линейного Дискриминантного Анализа и Квадратичного Дискриминантного Анализа. Нижняя строка показывает что Линейный Дискриминантный Анализ может только обучаться линейным границам, тогда как Квадратичный Дескриминантный Анализ может обучаться квадратичным границам и следовательно является более гибкий.
1.2.1. Снижение размерности с использованием Линейного Дискриминантного Анализа¶
Класс LinearDiscriminantAnalysis может быть
использован для выпонения контролируемого снижения размерности,
путем проектирования входных данных в линейное подпространство, которые направлены
на максимизацию разделение между классов
(более точном смысле обсуждается в математическом разделе ниже).
Размерность выхода должна быть меньше чем чесло классов,
так что в целом это довольно сильное снижение размерности и имеет смысл тольк в
многоклассовой конфигурации.
Такая обработка реализована в методе transform. Желаемая размерность может быть
установлена с помощью параметра n_components.
этот параметр не имеет влияние на методы fit и predict.
1.2.2. Математическая формулировка LDA и QDA классификации¶
И LDA, и QDA могут быть получены из простых вероятностных моделей, которые моделируют условное распределение данных по классам с вероянтностью \(P(X|y=k)\) для каждого класса \(k\). Затем прогнозы можно получить с помощью правила Байеса для каждой обучающей выборки \(x \in \mathcal{R}^d\):
и выбираем класс \(k\) который максимизирует эту апостериорную вероятность.
В частности, для линейного и квадратичного дискриминантного анализа \(P(x|y)\) моделируется многомерным распределением Гаусса с плотностью:
где \(d\) количество призакнов.
1.2.2.1. QDA¶
Согласно модели, приведенной выше, логорифмируем выражения:
где постоянный член \(Cst\) соответствует знаменателю \(P(x)\), в дополнение к другим постоянным членам из гауссиана. predicted class is the one that maximises this log-posterior. Прогнозируемый класс - это тот, который максимизирует этот логарифмическое выражение.
Примечание
Связь с гауссовским наивным байесовским методом
Если в модели QDA предполагается, что ковариационные матрицы диагональны,
то входные данные условно независимы в каждом классе
и результирующий классификатор эквивалентен гауссовскому наивному байесовскому
классификатору naive_bayes.GaussianNB.
1.2.2.2. LDA¶
LDA это частный случай QDA, где предполагается, что гауссианы для каждого класса имеют одну и ту же ковариационную матрицу: \(\Sigma_k = \Sigma\) для всех \(k\). Это уменьшает размер логорифма до:
Выражение \((x-\mu_k)^t \Sigma^{-1} (x-\mu_k)\) соответствует Расстоянию Махаланобиса между входным значением \(x\) и средней \(\mu_k\). Расстоянию Махаланобиса показывает, насколько близко \(x\) из \(\mu_k\), при этом также учитывается дисперсия каждого признака. Таким образом, мы можем интерпретировать LDA как присвоение \(x\) к классу, среднее значение которого является наиболее близким с точки зрения расстояния Махаланобиса, с учетом априорных вероятностей класса.
Логорифмическое выражение LDA также можно записать [3] как:
где \(\omega_k = \Sigma^{-1} \mu_k\) и \(\omega_{k0} = -\frac{1}{2} \mu_k^t\Sigma^{-1}\mu_k + \log P (y = k)\).
Эти величины соответствуют coef_ и intercept_ атрибутам, соответственно.
Из приведенной выше формулы ясно, что LDA имеет линейную поверхность принятия решений. В случае QDA нет никаких предположений о ковариационных матрицах \(\Sigma_k\) гауссиана, чтоприводит к квадратичным решающим поверхностям. Смотри источник [1] для более подробной информации.
1.2.3. Математическая формулировка снижения размерности LDA¶
Сначала обратите внимание, что K означает \(\mu_k\) векторы в \(\mathcal{R}^d\), и они лежат в аффинном подпространстве \(H\) размерности не более \(K - 1\) (2 точки лежат на прямой, 3 точки лежат на плоскости и т.д.).
Как упоминалось выше, мы можем интерпретировать LDA как присвоение \(x\) классу, среднее значение которого \(\mu_k\) является наиболее близким с точки зрения расстояния Махаланобиса, при этом также учитывая априорные вероятности класса. Альтернативно, LDA эквивалентен сначала сферизации данных так, чтобы ковариационная матрица была идентичной, а затем присвоению \(x\) ближайшему среднему с точки зрения евклидова расстояния (с учетом априорных значений класса).
Вычисление евклидовых расстояний в этом d-мерном пространстве эквивалентно первому проецированию точек данных в \(H\) и вычислению расстояний в нем (поскольку остальные измерения будут вносить равный вклад в каждый класс с точки зрения расстояния). Другими словами, если \(x\) ближе всего к \(\mu_k\) в исходном пространстве, то это будет так и в \(H\). Это показывает, что в классификаторе LDA неявно присутствует снижение размерности путем линейного проецирования на пространство размерности \(K-1\).
Мы можем снизить размерность еще больше, до выбранного \(L\), проецируя на линейное подпространство \(H_L\), которое максимизирует дисперсию \(\mu^*_k\) после проецирования (по сути, мы делаем форму PCA для преобразованных средств класса \(\mu^*_k\)).
Этот \(L\) соответствует параметру n_components, используемому в методе transform. Более подробную информацию см. в [1].
1.2.4. Усадка (Shrinkage) и ковариационная модель¶
Shrinkage - это форма регуляризации, используемая для улучшения оценки ковариационных матриц в ситуациях, когда количество обучающих выборок мало по сравнению с количеством признаков. В этом случае эмпирическая ковариация выборки является плохой моделью, и усадка помогает улучшить обобщающие характеристики классификатора.
Усадка LDA может быть использована путем установки параметра shrinkage класса LinearDiscriminantAnalysis в значение ‘auto’. Это автоматически определяет оптимальный параметр усадки аналитическим способом, следуя лемме, введенной Ледуа и Вольфом [2].
Обратите внимание, что в настоящее время усадка работает только при установке параметра solver в значение ‘lsqr’ или ‘eigen’.
Параметр shrinkage также может быть установлен вручную в диапазоне от 0 до 1. В частности, значение 0 соответствует отсутствию усадки (что означает использование эмпирической ковариационной матрицы), а значение 1 соответствует полной усадке (что означает, что диагональная матрица дисперсий будет использоваться в качестве оценки для ковариационной матрицы). Установка этого параметра в значение между этими двумя экстремумами приведет к оценке уменьшенной версии ковариационной матрицы.
Сокращенная оценка ковариации Ледойта и Вольфа не всегда является наилучшим выбором. Например, если распределение данных является нормально распределенным, то Приближенная Оценка Oracle (Oracle Approximating Shrinkage) sklearn.covariance.OAS дает меньшую среднюю квадратическую ошибку, чем та, которую дает формула Ледойта и Вольфа, используемая с shrinkage=”auto”. В LDA предполагается, что данные являются гауссовыми условно для класса. Если эти предположения справедливы, то использование LDA с оценкой ковариации OAS обеспечит более высокую точность классификации, чем использование оценки ковариации Ледойта и Вольфа или эмпирической оценки ковариации.
Оценку ковариации можно выбрать с помощью параметра covariance_estimator класса discriminant_analysis.LinearDiscriminantAnalysis. Ковариационная модель должен иметь метод fit и атрибут covariance_, как и все ковариационные модели в модуле sklearn.covariance.
1.2.5. Алгоритмы оценивания¶
Использование LDA и QDA требует вычисления log-posterior, который зависит от приор класса \(P(y=k)\), средств класса \(\mu_k\), и ковариационных матриц.
Алгоритм ‘svd’ является алгоритмом по умолчанию для LinearDiscriminantAnalysis, и это единственный доступный алгоритм для QuadraticDiscriminantAnalysis.
Он может выполнять как классификацию, так и преобразование (для LDA).
Поскольку он не зависит от вычисления ковариационной матрицы, алгоритм ‘svd’ может быть предпочтительнее в ситуациях, когда количество признаков велико.
Алгоритм ‘svd’ нельзя использовать с усадкой.
Для QDA использование SVD-алгоритма основано на том, что ковариационная матрица \(\Sigma_k\), по определению, равна \(\frac{1}{n - 1} X_k^tX_k = \frac{1}{n - 1} V S^2 V^t\), где \(V\) происходит из SVD (центрированной) матрицы: \(X_k = U S V^t\). Оказывается, мы можем вычислить log-posterior выше без необходимости явного вычисления \(\Sigma\): достаточно вычислить \(S\) и \(V\) через SVD от \(X\). Для LDA вычисляются два SVD: SVD центрированной входной матрицы \(X\) и SVD средних векторов по классам.
Алгоритм ‘lsqr’ - это эффективный алгоритм, который работает только для классификации. Он требует явного вычисления ковариационной матрицы \(\Sigma\), поддерживает сокращение и пользовательские оценки ковариации.
Этот алгоритм вычисляет коэффициенты \(\omega_k = \Sigma^{-1}\mu_k\), решая для \(\Sigma \omega = \mu_k\), избегая явного вычисления обратной \(\Sigma^{-1}\).
Алгоритм ‘eigen’ основан на оптимизации отношения разброса между классами к разбросу внутри класса. Его можно использовать как для классификации, так и для преобразования, и он поддерживает сокращение. Однако для решения задачи ‘eigen’ необходимо вычислить ковариационную матрицу, поэтому она может не подойти для ситуаций с большим числом признаков.