线性判别分析算法的实现

我们详细探讨了不同的映射方式对映射后的数据的影响，这些是线性判别算法最根本的思想。接下来看一看线性判别算法是如何由这些简单的思想实现的。

1. 投影的实际应用

有两种类别的数据：空心圆和实心圆，如图 1 所示。

图1：两种数据的分布
 

现在要将它们映射到一条直线上，保证映射之后仍然可以明显分类。通过《线性判别分析算法：方差与投影》内容学习，我们的一个思路就是使映射之后同一类别的方差最小（短），这样不同类别就不容易重合。不妨将它们映射到y轴上，如图 2 所示，投影之后，可以很容易地把二者区分开来。

图2：两组数据同时映射到y轴上

但这种方法并不是任何情况下都可行，比如图 3 所示的两种类别的数据分布。

图3：另一种分布形势

如果我们将它们映射到 y 轴上，就会出现严重的重叠，如图 4 所示。

图4：两组数据同时映射到y轴上，几乎重叠
 

两种数据几乎完全重叠了，这样就达不到分类的效果。

2. 解决重叠问题

如何克服上述提到的重叠情况呢？有另一个思路，就是让映射之后的数据尽量分离。在数学中，我们用不同组数据中心点之间的距离来描述“分离”的程度。如图 5 所示，不妨将这两组数据全部投影到 x 轴上，这样，虽然两组数据各自的方差很大，但是因为二者投影之后组间的数据相距足够远，还是可以进行明显的分类。

图5：两组数据同时映射到x轴上
 

和上述观察不同投影对投影之后方差的影响一样，我们也可以逐渐增大斜率，观察不同投影对组间数据中心点距离的影响。增大斜率到 0.5，如图 6 所示，两组数据映射后中心点的距离减小，二者边界接近重合。

图6：随着k增大，两组投影数据的边界将要重叠
 

继续增大斜率到 0.75，如图 7 所示，两组数据的边界恰好重叠。

图7：随着k增大，两组投影数据恰好重叠
 

继续增大斜率到 1.5，如图 8 所示，两组数据的边界重叠部分增多，二者中心点也在靠近。

图8：随着k增大，两组投影数据重叠部分增多
 

继续增大斜率到正无穷，如图 9 所示，二者数据完全重叠，中心点也重叠。

图9：随着k增大，两组投影数据将完全重叠
 

斜率从 0 到正无穷逐渐增大的过程中，二者中心点距离是逐渐缩小的，也就是中心点距离与斜率成反比。

3. 线性判别算法的实质

经过上面的分析，我们知道，要想将这两个数组区分开，需要找到一条直线，这条直线需要满足以下两个条件。

• 投影后每组数据的方差足够小。
• 投影后组与组之间的距离足够大。

图 10 所示的直线就是最终我们要找的直线，综合考虑了组内的方差和组间的距离。

图10：最佳的投影直线
 

可以明显看出，虽然投影到x轴可以将两组数据分类，但是组之间的间距并不是最大的。而这条最优直线，可以将两组数据的间距拉到最大。