聚类算法总结

聚类算法概念：

聚类就是按照某个特定标准(如距离准则)把一个数据集聚成不同的簇，使得同一簇内的数据的相似性尽可能大，同时不在同一个簇中的数据的相似性尽可能小。即聚类后要使得同一簇的数据尽可能聚集到一起，不同簇的数据尽量分离。聚类属于无监督学习算法。

聚类算法分类：

聚类算法的研究也是一个很大的家族，比较常见的有基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网络的聚类方法、基于模型的聚类方法、基于模糊的聚类方法、量子聚类、谱聚类、核聚类、基于粒度的聚类方法、基于约束的聚类方法等。

聚类过程：

数据准备过程：包括特征标准化和降维
特征选择过程：从最初的特征中选择最有效的特征
特征提取：对所选特征进行转换形成新的突出特征
聚类：选择合适的距离度量函数，然后进行聚类

聚类算法优劣衡量标准:

处理大数据集的能力
处理任意形状数据的能力
算法是否独立于数据输入顺序
是否需要预先知道聚类簇的个数，是否需要用户给出领域知识
对数据维度是否敏感

Hierarchical methods（层次聚类算法）

通过一种层次架构方法，反复将数据进行分裂或聚合。主要有二种思想，一种是自下而上法(bottom-up)，一种是自上而下法(top-down)，自下而上法意思是开始每个点都是一个类，然后根据距离度量寻找同类，最后形成一个”类”。自上而下法就是反过来，一开始所有点都属于一个”类”，然后根据距离度量一步步分开。

典型的有凝聚型层次聚类。

凝聚型层次聚类：

算法主要过程：
1. 将每个点看作一类，并且计算两两之间的距离
2. 将距离最小的两个类合并成一个新类
3. 重新计算新类与所有类之间的距离
4. 重复第2、3步，直到最后合并成指定的K类

Partition-based methods(划分聚类算法)

预先指定聚类数，反复迭代逐步降低目标函数误差值直至收敛。经典的有K-means，k-means对初始值选择很敏感；所有又出现了K-means++、intelligent k-means，k-means对噪声和离群点非常敏感，所以又出现了k-medoids、k-medians； k-means只用于numerical类型数据，不适用于categorical类型数据，所以出现了k-modes；k-means不能解决非凸数据，所以出现了kernel k-means。

经典K-means算法流程：

随机选择k个点，每个点代表一个簇的中心
对其它的点，计算它们与各簇中心的距离，并根据距离将其归入最近的簇
对新形成的k个簇，重新计算每个簇的中心(计算方法有很多种)
重复第2、3步，直到目标函数收敛

k-means算法如何确定初始化聚类中心K？

随机初始化
最远遍历(这种方法噪声点影响大)
K-means++：
(1)随机选择第一个点
(2)计算每个样本与当前已有聚类中心之间的最短聚类(即与最近的一个聚类中心的距离)，用D(x)表示
(3)计算每个样本被选为下一个聚类中心的概率(距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心)
(4)重复第(2)步直到选出K个聚类中心

如何确定k-means算法的聚类中心K数？

交叉验证法(cross-validation)：
(1)把数据集切分成训练集和验证集
(2)在训练集上用不同的K，然后在验证集上看效果，选择使验证集效果最好的K
Heuristic(Elbow’s method)
从K取1，2，……,n，每选一次k，算一次损失函数，选择一个k，使得在此之前，cost下降很快，在此之后，cost变化很小

Density-based methods(基于密度的聚类算法)

只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。

擅于解决不规则形状的聚类问题(k-means做不到)，广泛应用于空间信息处理，包括SGC、GCHL、DBSCAN算法、OPTICS算法、DENCLUE算法。

DBSCAN算法：

对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。

Grid-based methods(基于网格的聚类算法)

基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。

代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。

Model-based methods(基于模型的聚类算法)

为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，同一”类“的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。

参考:
1. https://www.zhihu.com/question/34554321/answer/233489816
2. https://www.zhihu.com/question/34554321