聚类与降维

K均值聚类与PCA算法详解

K均值聚类

聚类是一种无监督学习,它将相似的对象归到同一个簇中
聚类与分类不同之处在于,分类的目标事先已知,而聚类不一样,类别没有事先定义

K均值是发现给定数据集的K个簇的算法。簇个数K是用户给定的,每一个簇通过其质心,即簇中所有点的中心来描述

具体实现

思想
1.随机确定K个初始点为作为质心,然后将数据集中的每个点分配到每一个簇中,具体来讲,为每个点找距离其最近的质心,并将其分配给质心所对应的簇。
2.将每个簇的质心更新为该簇所有点的平均值。
迭代至簇不发生变化或达到最大迭代次数

1
2
3
4
5
选择K个点作为初始质心
repeat
将每个点指派到最近的质心,形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数

这里的重新计算每个簇的质心,如何计算的是根据目标函数得来的,因此在开始时我们要考虑距离度量和目标函数。

考虑欧几里得距离的数据,使用误差平方和(Sum of the Squared Error,SSE)作为聚类的目标函数,目标是使得SSE最小。

"da"
k表示k个聚类中心,ci表示第几个中心,dist表示的是欧几里得距离。
"da"

K均值算法缺陷

1.在大规模数据集上收敛较慢
2.K值需要预先给定,属于预先知识,很多情况下K值的估计是非常困难的
3.K-Means算法对初始选取的聚类中心点是敏感的,不同的随机种子点得到的聚类结果完全不同
4.K均值算法并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇
5.当初始质心是随机的进行初始化的时候,K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕,可能只能得到局部的最优解,而无法得到全局的最优解

K均值优化算法(二分K-means)

为了克服K-Means算法收敛于局部最小值的问题,提出了一种二分K-均值(bisecting K-means)
算法的伪代码如下

1
2
3
4
5
6
7
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2
计算将该簇划分成两个簇后总误差
选择是的误差最小的那个簇进行划分

数据降维

在原始的高维空间中,包含冗余信息和噪声信息,会在实际应用中引入误差,影响准确率;
而降维可以提取数据内部的本质结构,减少冗余信息和噪声信息造成的误差,提高应用中的精度
数据降维的算法主要有主成分分析,等距映射,局部线性嵌入等

主成分分析算法

Principal Component Analysis(PCA)是最常用的线性降维方法,它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性,将数据的主成分(包含信息量大的维度)保留下来

最大方差思想:
选取数据差异最大的方向(方差最大的方向,方差反应的是数据与其方差(均值)之间的偏离程度,我们通常认为方差越大数据的信息量就越大)作为第一个主成分,第二个主成分选择方差次大的方向,并且与第一个主成分正交。不断重复这个过程直到找到n个主成分。

"da"
"da"
"da"
"da"

参考资料
【1】《机器学习实战》Peter Harrington(美) 人民邮电出版社
【2】深入理解K-Means
【3】-PCA数据降维:从代码到原理的深入解析
【4】四大机器学习降维方法