1.2. 线性判别分析和二次判别分析(Linear and Quadratic Discriminant Analysis)

线性判别分析( discriminant_analysis.LinearDiscriminantAnalysis ) 和 二次判别分析(discriminant_analysis.QuadraticDiscriminantAnalysis) 是两个经典的分类器。 正如他们名字所描述的那样,他们分别代表了线性决策平面和二次决策平面。

这些分类器十分具有吸引力,因为他们可以很容易计算得到闭式解(即解析解),其天生具有多分类的特性, 在实践中已经被证明很有效,并且没有超参数要去调节。

ldaqda

以上这些图像展示了 线性判别分析(LDA)以及 二次判别分析(QDA)的决策边界。 其中,最后一行表明了线性判别分析只能学习线性边界, 而二次判别分析则可以学习二次边界,因此它相对而言更加灵活。

案例:

协方差椭球化情形下LDA和QDA的比较: Comparison of LDA and QDA on synthetic data.

1.2.1. 使用线性判别分析进行维数约减

discriminant_analysis.LinearDiscriminantAnalysis 可以进行有监督的维数约简, 这是通过把输入数据投影到一个线性子空间来实现的,而这个线性子空间是由最大化类之间分离的方向所组成的。(详细的内容见下面的数学推导)。 输出的维度必然会比原来的类别数量更少的。因此它总体而言是十分强大的降维方式,同样也仅仅在多分类环境下才能感觉到。

实现方式在 discriminant_analysis.LinearDiscriminantAnalysis.transform 中。关于维度的数量可以通过 n_components 参数来调节。 值得注意的是,这个参数不会对 discriminant_analysis.LinearDiscriminantAnalysis.fit 或者 discriminant_analysis.LinearDiscriminantAnalysis.predict 产生影响。

案例:

LDA与PCA在鸢尾花数据集上的二维投影的比较: Comparison of LDA and PCA for dimensionality reduction of the Iris dataset

1.2.2. LDA 和 QDA 分类器的数学化形式

LDA 和 QDA 都可以通过简单的概率模型推导出来,对每一个类别 \(k\) 的类条件分布 \(P(X|y=k)\) 进行建模。 有了类条件概率分布(class conditional distribution)后,预测就可以通过贝叶斯定理所获得。

\[P(y=k | X) = \frac{P(X | y=k) P(y=k)}{P(X)} = \frac{P(X | y=k) P(y = k)}{ \sum_{l} P(X | y=l) \cdot P(y=l)}\]

我们选择能够使上述条件概率最大化的类别 \(k\) 作为预测结果 。

更具体地说,对于线性以及二次判别分析,类条件分布 \(P(X|y)\) 被建模成多变量高斯分布(multivariate Gaussian distribution), 其密度函数如下所示:

\[P(X | y=k) = \frac{1}{(2\pi)^{d/2} |\Sigma_k|^{1/2}}\exp\left(-\frac{1}{2} (X-\mu_k)^t \Sigma_k^{-1} (X-\mu_k)\right)\]

其中 \(d\) 是特征分量的个数.

为了把该模型作为分类器使用,我们只需要从训练数据中估计出类的先验概率 \(P(y=k)\) 的样本的比例得到) 类别均值 \(\mu_k\) (通过经验样本的类别均值得到)以及协方差矩阵 (通过经验样本的类别协方差或者正则化的估计器 estimator 得到: 见下面的 shrinkage 章节)。

在LDA中,假定每个类的高斯分布与其他所有类共享同一个协方差矩阵 \(\Sigma_k = \Sigma\) 。这样一个假设就导致了线性决策面(linear decision surfaces), 我们可以通过比较对数概率比(log-probability ratios): \(\log[P(y=k | X) / P(y=l | X)]\) 看到这一现象:

\[ \begin{align}\begin{aligned}\log\left(\frac{P(y=k|X)}{P(y=l|X)}\right)= \log\left(\frac{P(X|y=k)P(y=k)}{P(X|y=l)P(y=l)}\right)=0 \Leftrightarrow\\(\mu_k-\mu_l)^t\Sigma^{-1} X = \frac{1}{2} (\mu_k^t \Sigma^{-1} \mu_k - \mu_l^t \Sigma^{-1} \mu_l) - \log\frac{P(y=k)}{P(y=l)}\end{aligned}\end{align} \]

在QDA中, 对各个类的高斯分布的协方差矩阵 \(\Sigma_k\) 没有做任何假定,这样就会产生二次决策面(quadratic decision surfaces)。 请看参考文献 [3] 获得更多详情。

Note

QDA与高斯朴素贝叶斯的关系(Gaussian Naive Bayes)

如果我们在QDA模型中假定了协方差矩阵为对角阵(diagonal),那么就假定了每一个类的输入是条件独立的(conditionally independent), 由此产生的分类器就等价于高斯贝叶斯分类器( naive_bayes.GaussianNB ).

1.2.3. LDA 维数约减的数学化形式

为了理解 LDA 在降维上的应用,我们从上面解释的 LDA 分类规则的几何重构(geometric reformulation)开始说起是十分有用的。 令 \(K\) 为目标类的总数量。既然我们在LDA中假定了所有类都共享同一个估计得到的协方差矩阵 \(\Sigma\), 我们就可以 缩放数据(rescale the data)使得这个共享的协方差矩阵是个单位阵(identity):

\[X^* = D^{-1/2}U^t X\text{ with }\Sigma = UDU^t\]

然后,我们就会发现要对一个经过缩放的数据点进行分类就等价于在欧式空间中找到距离这个数据点最近的某个类的均值 \(\mu^*_k\),只要找到这个均值, 就可以把该均值所代表的类标签付给我门要分类的那个数据点。 But this can be done just as well after projecting on the \(K-1\) affine subspace \(H_K\) generated by all the \(\mu^*_k\) for all classes. 这表明 LDA 分类器通过在 \(K-1\) 维空间上的线性投影潜在的具有维数约简的功能( This shows that, implicit in the LDA classifier, there is a dimensionality reduction by linear projection onto a \(K-1\) dimensional space.)。

We can reduce the dimension even more, to a chosen \(L\), by projecting onto the linear subspace \(H_L\) which maximizes the variance of the \(\mu^*_k\) after projection (in effect, we are doing a form of PCA for the transformed class means \(\mu^*_k\)). This \(L\) corresponds to the n_components parameter used in the discriminant_analysis.LinearDiscriminantAnalysis.transform method. See [3] for more details.

1.2.4. 收缩(Shrinkage)

收缩(Shrinkage)是一种在训练样本数量相比特征而言很小的情况下可以提升协方差矩阵预测准确性的工具。 在这个情况下,经验样本协方差是对真实协方差矩阵的很差的预测。Shrinkage LDA 可以通过设置 discriminant_analysis.LinearDiscriminantAnalysis 类的 shrinkage 参数为 ‘auto’ 来实现。根据Ledoit and Wolf [4] 的介绍的引理(lemma),这样做可以以解析的方式自动确定最优的收缩参数。 需要注意的是,目前 shrinkage 只能在 求解器参数 solver 为 ‘lsqr’ 或 ‘eigen’ 的时候正常工作。

参数 shrinkage 也可以手动的设置为 0 到 1 之间的值。如果参数值等于0则意味着没有任何收缩shrinkage (也意味着经验协方差矩阵(empirical covariance matrix)将会被使用) ;如果参数值等于1就意味着完全收缩(complete shrinkage) (这也意味着方差的对角矩阵(diagonal matrix of variances)将会被作为协方差矩阵的估计值)。将参数 shrinkage 的取值设定在0到1之间的话 就可以估计出一个收缩版的协方差矩阵(a shrunk version of the covariance matrix)。

shrinkage

1.2.5. 估计算法

默认的求解器是 ‘svd’。 它既可以执行分类也可以执行变换(transform),而且不依赖于协方差矩阵的计算,在特征的数量很大的时候这将是一大优势。 然而,’svd’ 求解器不能与 shrinkage 参数同时使用。

‘lsqr’ 求解器是一个只能用于分类的高效算法,它支持 shrinkage。

‘eigen’ 求解器 是一种通过优化类间散度(between class scatter)与类内散度(within class scatter)的比率进行求解的方法。它也支持 shrinkage。 然而, ‘eigen’ 求解器需要计算协方差, 因此这种求解器不适用于高维特征的情况。

案例:

应用于分类任务的 正常LDA和缩减LDA: Comparison of LDA classifiers with and without shrinkage.

参考文献:

[3](1, 2) “The Elements of Statistical Learning”, Hastie T., Tibshirani R., Friedman J., Section 4.3, p.106-119, 2008.
[4]Ledoit O, Wolf M. Honey, I Shrunk the Sample Covariance Matrix. The Journal of Portfolio Management 30(4), 110-119, 2004.