在直观印象中,说起聚类算法,首先想到的k-means.

k-means作为经典的聚类算法,应用范围很广,但是在运行前要指定聚类的数量n,这个值对于最终的计算结果有很大的影响.而现在也没有通用的方法来得到这个值.

本文介绍了包括k-means在内的多种聚类算法,可以在实际中灵活使用.

聚类常用算法

top-5

1. K-means
2. Mean-Shift Clustering algorithm
3. DBSCAN, Density-Based Spatial Clusting of Applications with Noise
4. EM using GMM, Expectation-Maximization(EM) Clusting using Gaussian Mixture Models
5. Agglomerative Hierarchical Clustering

scikit-learn中各种聚类方法

1 K-means

KMeans算法聚类数据,是通过将不同样本分离成方差相等的n组,最小化惯性(inertia)或者叫类内平方和(within-cluster sum-of-squares).这个算法需要指定聚类的数量.可应用于大量样本的情况,在很多不同领域有大量的应用.

K-means算法将一个样本数量N的集合X划分成K个类别C,每个类别被描述成该类别下样本的平均值uj.通常把这些平均值称为’质心’,注意到通常情况下这些质心并不是集合X中的点,尽管他们位于同一个空间.

K-means算法的目的是选择合适的质心,使得惯性或者类内平方和最小:

inertia可以作为聚类内部相关程度的度量.它受以下因素影响:

1. inertia假设聚类是凸形和各向同性的(convex and isotropic),实际中不总是这样.因此聚类为细长或者不规则的情况下表现较差.
2. inertia不是正规矩阵,我们只知道值越小越好,0是最优的.但是在高阶空间下,鸥拉距离会发生膨胀(这就是所谓的"维度灾难"的实例).运行维度减小算法,比如主成分分析(PCA)再进行k-means聚类,可以降低维度灾难的可能性,并且可以加速计算.

2 Mean Shift

MeanShift聚类用于发现平滑密度样本中的斑点(blobs).这是一种基于质心的算法,计算给定区域样本的均值,用这个值更新质心的候选点.最后,把这些候选点中相近重复的过滤掉,剩下的作为最终的质心集.

给定一个候选质心xi,迭代次数t,通过下面这个公式来更新质心:

N(xi)是在xi周围给定一个距离的样本,m是平均迁移向量,得到质心变为区域密度最大值所在位置.通过下面这个公式计算,有效地更新质心到它周围样本的平局值:

该算法自动生成聚类的数量,相应的依赖参数bandwidth,表示搜索区域的大小.该参数可以手动设置,也可以通过函数estimate_bandwidth估计,当bandwidth没有设置时自动调用该函数.

这个算法可扩展性不是很高,因为在算法执行时需要多个临近搜索.算法能够保证收敛,当质心变化太小时会停止迭代.

对于一个给定的样本,找到最近的质心,既可以给该样本打标签.

示例:
A demo of the mean-shift clustering algorithm:Mean Shift聚类算法用于合成的2D数据集,3个类别

参考:
“Mean shift: A robust approach toward feature space analysis.”: D. Comaniciu and P. Meer, IEEE Transactions on Pattern Analysis and Machine Intelligence (2002)

3 DBSCAN

DBSCAN算法把聚类看成高密度区域被低密度区域包围.基于这个通用的观点,被DBSCAN认定的聚类可以是任意形状的,而不是k-means假定的聚类是凸形状.DBSCAN的核心组件是核样本的概念(concept of core samples),即在高密度区域的样本.一个聚类是核样本的集合,与其他核样本相连(通过距离测量),也与非核样本相连,该非核样本又与其他核样本相连.在这个算法中,有2个参数,min_samples和eps,用于正式地定义我们所说的密度.更高的min_samples和更低的eps意味着更高的密度用于组成一个聚类.

更加正式的,我们定义核样本为在数据集的该样本,在距离eps内存在最少不低于min_samples的其他样本,这些样本被认为核样本的另据.这告诉我们核样本位于向量空间的高密度区域.一个聚类被看作核样本的集合,可以通过迭代获取核样本的方式建立,找到该核样本周围的所有核样本,继续找出这些核样本周围的所有核样本.一个聚类也包含非核样本的集合,这些样本在核样本的周围,但他们本身不是核样本.直观上,这样样本位于聚类的边缘.

任意核样本是某个聚类的一部分.任意非核样本,存在核样本与该非核样本距离超过eps,被DBSCAN认为是离群值(outlier).

min_samples参数用来限制算法对噪声的容忍程度(对于噪声和大数据集,可以相应的增大该参数),选择合适的eps参数是非常重要的,对于不同的数据集和距离函数,通常情况下不能选择默认值.它控制着临近的程度.太小时,大多数的数据不会被选择到(噪声会被标记为’-1’).太大时,会导致临近的聚类组合成一个,最终所有的数据生成为一个聚类.在某些文献中,提出用启发式算法来选择该参数,比如基于最临近点的knee(based on a knee in the nearest neighbor distances plot, 可参考在下面的引用文献)

在下图中,颜色代表着聚类成员,大圆表示算法找出的核样本.小圆表示非核样本,但依然是聚类的成员.离群值用黑点表示

示例:

Demo of DBSCAN clustering algorithm

实现:

DBSCAN算法是确定性的,按相同顺序输入相同的值总会输出相同的结果.然后,如果数据按不同的顺序结果可能会有所不同.首先,尽管核样本会被归于同样的聚类,聚类的标签会依赖于样本遇到数据的顺序.然后更重要的是,聚类中非核样本会因为数据顺序的不同而归于不同的聚类.根据三角形不等式,两种不同聚类下的核样本距离大于eps,不然说明这两个核样本是位于相同的聚类中.非核样本被归于哪一类聚类取决于它首先遇到哪个核样本,因此这个结果会根据数据顺序而不同.

当前实现采用ball trees和kd-trees来决定临近的点,避免计算全距离矩阵.

大数据量时的内存消耗:

当前实现默认不采用内存有效方式,因为创建了一个全量对相似性矩阵(a full pairwise similarity matrix)以防kd-trees 或者ball-trees不能使用的情况(e.g. 稀疏矩阵).这个矩阵会消耗n^2浮点数空间.一系列解决问题的机制是:

1. 使用 OPTICS聚类,联合extract_dbscan方法.OPTICS聚类也使用全量相似性矩阵,但是每次只在内存中保存一行(内存复杂度n).
2. 用内存有效的方式提前计算稀疏半径邻域图(推定缺失实例在eps之外),dbscan在运行时标注 metric=‘precomputed’.详情查看 sklearn.neighbors.NearestNeighbors.radius_neighbors_graph.
3. 数据集可以被压缩,要么移除数据中重复的部分,或者使用 BIRCH.就有了相对小数量的数据代表大量的点.然后在灌入数据到DBSCAN时可以设置sample_weight

参考:

1. “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise” Ester, M., H. P. Kriegel, J. Sander, and X. Xu, In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
2. “DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). In ACM Transactions on Database Systems (TODS), 42(3), 19.

HDBSCAN参数调整

HDBSCAN结合了dbscan和层次聚类两种方法,当前还没有集中到scikit-learn的当前正式版本(0.19.1)中.

HDBSCAN参数调整

1. min_cluster_size 理论上,这是一个相对直观的参数,把它设置成你认为聚类的最小样本数量.它的影响是轻微不显著的.
2. min_samples
3. cluster_selection_epsilon

to be continued…