首页 > 线性判别分析 阅读数:2

线性判别分析算法的实现

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

1. 投影的实际应用

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


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

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

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

另一种分布形势
图3:另一种分布形势

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

两组数据同时映射到y轴上,几乎重叠
图4:两组数据同时映射到y轴上,几乎重叠
 
两种数据几乎完全重叠了,这样就达不到分类的效果。

2. 解决重叠问题

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

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

随着k增大,两组投影数据的边界将要重叠
图6:随着k增大,两组投影数据的边界将要重叠
 
继续增大斜率到 0.75,如图 7 所示,两组数据的边界恰好重叠。

随着k增大,两组投影数据恰好重叠
图7:随着k增大,两组投影数据恰好重叠
 
继续增大斜率到 1.5,如图 8 所示,两组数据的边界重叠部分增多,二者中心点也在靠近。

随着k增大,两组投影数据重叠部分增多
图8:随着k增大,两组投影数据重叠部分增多
 
继续增大斜率到正无穷,如图 9 所示,二者数据完全重叠,中心点也重叠。

随着k增大,两组投影数据将完全重叠
图9:随着k增大,两组投影数据将完全重叠
 
斜率从 0 到正无穷逐渐增大的过程中,二者中心点距离是逐渐缩小的,也就是中心点距离与斜率成反比。

3. 线性判别算法的实质

经过上面的分析,我们知道,要想将这两个数组区分开,需要找到一条直线,这条直线需要满足以下两个条件。
图 10 所示的直线就是最终我们要找的直线,综合考虑了组内的方差和组间的距离。

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

优秀文章