给定一堆数据点，根据算法把他们分成几组，让每个组内的点都有相似的特性，这种方法就叫聚类。理论上来说，能分成一组的都是有相似特性的，不是一组的肯定有不一样的特征。
一、 K-means聚类
k-means最小化簇内样本与簇的均值向量的平方误差
- 随机初始化k个聚类的中心点
- 计算所有数据点到k个中心的距离，根据距离最近的中心确定分组
- 计算每组的均值作为每组新的中心点
- 重复以上步骤直到每组的中心点不再变化
k-means计算很简单，但是有很多缺点，比如一定要指定分组的数量，每个聚类的中心点都是随机初始化的，所以很有可能每次运行的得到的中心点位置都不一样。
二、Mean shift聚类
- 随机选择一个初始点和一个半径r的窗口
- 在每一步中，滑动窗口都会向密度更高的方向移动
- 继续移动直到窗口内密度不再增加
- 使用多个滑动窗口并重复以上步骤，直到每一个点都有自己的分组。对于重叠的部分，包含数据点较多的分组会被保留下来。
与k-means不同的是，mean shift不需要定义分组的数量，但是需要定义窗口的大小。
三、空间聚类（spatial clustering）
- 计算所有点的近似矩阵A
- 定义对角矩阵D，（i，i）出的值为A的第i行之和，然后构造矩阵L
- 找到L的前k个最大的特征值，按列放在一起构成一个新的矩阵X
- 正则化X的每行构成Y矩阵
- 把Y的每一行都党组一个新的数据点， 用k-mean或者其他算法分成k个聚类。
- 如果Y矩阵的第i行被分到了j组，则对应的初始数据点被分到j组。
四、密度聚类
Density-Based Spatial Clustering of Applications with Noise (DBSCAN)，基于一组邻域参数来刻画样本分布的紧密程度。邻域值得是样本集中与一个样本距离不大于ε的样本。
- 从一个没有访问过的数据点开始，距离点ε范围内的所有点作为该点的邻域
- 如果该邻域内有数量足够的点，则认为这个点开始了一个新的簇，并且成为新簇的第一个点，否则被记为噪声点。这两种情况下该点都被记作已访问。
- 新簇中的第一个点的邻域里的点，也被看作是同一簇里的点，并将他们邻域内所有的点也加进同一簇。
- 重复步骤2和3， 直到簇邻域内的所有点都被访问。
- 当前簇处理完之后，检索一个新的未访问过的点，从而开始一个新的簇
DBSCAN 不需要实现设置聚类的数量，并且可以对任意形状的数据集进行聚类，在聚类的同时也能分辨出噪声点。
缺点是在样本密度不均匀，聚集性较差的时候不太合适，不过可以通过转换到高纬度空间来解决。
五、高斯混合聚类
k-means的缺点之一是使用了聚类的均值作为中心点，对于卷起来这种的结构就不合适。
高斯混合模型假设每个簇的数据都是高斯分布的。
- 选择k个分组的中心，并为每个聚类随机生成高斯分布
- 计算每个数据点属于某个聚类的概率
- 基于这些概率，重新计算新的均值、协方差，更新新的混合系数，使数据点在聚类内的概率最大。
- 重复直到收敛。
GMM与k-means相比更加灵活，聚类的形状可以是椭圆形。由于用的概率，GMM也可以得出每个点分别属于不同组的概率。
六、层次聚类
层次聚类在不同层次上对数据集进行划分，从而形成树形的聚类结构。AGNES是一种采用自底向上聚合的层次聚类算法。
- 将数据集中的每个样本看作一个初始聚类簇
- 找出距离最近的两个聚类簇进行合并。聚类间的距离由两个簇之间样本的最小距离，最大距离以及平均距离等决定。
- 重复合并直到达到预设的聚类个数
参考
[1] The 5 Clustering Algorithms Data Scientists Need to Know
[2] Ng A Y, Jordan M I, Weiss Y. On spectral clustering: Analysis and an algorithm[C]//Advances in neural information processing systems. 2002: 849-856.
网友评论