KMeans是一种简单的对给定数据集将其划分成k个簇的聚类算法,数据挖掘十大算法之一,其数学原理也是非常的朴素。本文将根据KMeans的原理将其实现,并对其性能进行分析,讨论其缺陷与探讨业界主流的改进方式。
KMeans 算法的思想是由许多跨学科领域的研究者们经过长时间不断的交织出来的,但其第一次使用是由Lloyd(1957, 1982)所提出用于调制脉冲编码,关于KMeans的更多历史信息可在[2]中找到,KMeans提出之初因为其朴素算法涉及组合爆炸问题导致其是NP-Hard的问题,但Gray and Neuhoff[3]提出了一种非常高效的启发式搜索算法,使其能够较快的收敛至局部最优值。
本文第二节会详细的阐述KMeans的数学原理(这是必要的),根据其核心原理使用Python语言将其实现;第三节中会使用scikit-learn产生一组测试数据集,该数据集由三个不同的高斯分布生成,而后会将第二节中实现的KMeans算法应用在此数据集上,并与scikit-learn中提供的KMeans算法进行对比,最后会讨论KMeans的不足并探讨业界流行的改进方式;第四节是对本文的总结。
KMeans其本质是一种基于形心的聚类技术[5],目的要把 中的所有对象分配到个簇中,使得对于且。使用一个距离度量评价划分的质量,即
其中是评价的距离度量函数,而是簇的形心(均值点),一般地传统的KMeans采用的距离度量是欧几里的距离(欧氏距离),那么就是可以形象的理解为数据集中所有点与误差的平方和,即
而优化的目标就是让E尽可能的小,业已证明,在一般都欧氏空间中枚举所有的划分可能是一个NP-Hard的问题,因此优化的手段就改成一种启发式的搜索,该启发式算法由数据分配(Data Assignment)和更新均值(Update)组成。
负责将所有的根据计算分配至距离最近的簇中,返回每个的簇标记。
则负责根据当前步骤的簇标记对所有的簇形心进行簇内求均值,返回更新后的
不断的执行迭代,直到不再发生变化,即收敛至局部最优值。
伪代码如图1所示。
Python实现如下
def random_init_centroids(X, k): ids = np.random.choice(X.shape[0], k, replace=True) return X[ids] def data_assignment(X, centroids): m = X.shape[0] ids = np.zeros((m, )) for i in range(m): V = X[i] - centroids V = np.dot(V, V.T) ids[i] = np.argmin(np.diag(V)) return ids def update(X, centroids, ids): K = centroids.shape[0] new_centroids = np.zeros(centroids.shape) for i in range(K): new_centroids[i] = np.sum(X[ids==i], axis=0) / \ np.size(np.where(ids==i)) return new_centroids def k_means(X, k, max_iter=500): # randomly initial centroids centroids = random_init_centroids(X, k) previous_centroids = centroids for i in range(max_iter): # data assignment ids = data_assignment(X, centroids) # plot each situation of iteration. plot_cluster(X, ids, ['o', 'x', '^'], ['r', 'g', 'b'], centroids=centroids.tolist(), title=f"Iteration {i+1}", x_label="X1", y_label="X2", labels=['cluster 1', 'cluster 2', 'cluster 3']) plt.show() # update previous_centroids = centroids centroids = update(X, centroids, ids) if np.allclose(previous_centroids, centroids): print(f"k-mean finish at {i+1}") break return centroids 复制代码
为了能清楚的了解KMeans的每一次迭代变化,在代码中加入了来展示聚类实况。
本文所有代码示例见附录。
为了检验第二节中实现的KMeans的准确性,使用scikit-learn所提供的make_blobs来产生测试聚类数据,该方法可以产生各向同性高斯数据,浅白点说就是产生若干个有相同分布的数据簇。
from sklearn.datasets import make_blobs real_centroids = [(-4, -4), (0, 0), (4, 4)] X, y = make_blobs(n_samples=300, centers=real_centroids, n_features=2, random_state=42) 复制代码
注: 不同的random_state
会产生不同的数据点。
为了方便验证,遂依次产生分别以为中心点的样本数据,一个中心点产生100个。图2展示了原数据集的各簇样本情况,可见在簇2(绿色x)中产生了一个距离簇3(蓝色三角)相对较近的离群点,因此该点在运行KMeans算法后很有可能被分配至簇3中。
图3是在原数据集中应用KMeans后的结果,因为KMeans的不稳定性所以簇类标记颠倒了,不过仍然可以看出原簇2的离群点被分配到了原簇3(即现在的簇1,红色圆点)中,各簇形心的收敛结果如下:
array([[ 0.15868461, 0.0155145 ], [-4.10690785, -3.93685302], [ 3.92090405, 3.87351944]]) 复制代码
可以看出虽然经过计算后的各簇形心都并非能够收敛至原定形心,不过各对应形心的位置已非常的接近,导致其现象的原因是KMeans会收敛于局部最小值的算法,随着初始点的选择不同,收敛点的值也会差异,但会无限接近于真实值。
接着使用scikit-learn中提供的KMeans运行原数据集,与本文所实现的KMeans算法产生对照,代码如下:
from sklearn.cluster import KMeans sk_kmeans = KMeans(n_clusters=3, random_state=42).fit(X) print(sk_kmeans.cluster_centers_) 复制代码
结果如下所示:
array([[ 0.15868461, 0.0155145 ], [ 3.92090405, 3.87351944], [-4.10690785, -3.93685302]]) 复制代码
可见与本文实现的KMeans结果几乎一致。
KMeans虽拥有简单的数学原理以及非常广泛的应用途径,但其不足之初也是非常多的。
kmeans++
[6]的初始化方式,这种方式考虑全局性能够加快KMeans的收敛速度,scikit-learn工具包中提供的KMeans采用的就是这样的方式。局部最优解陷阱 KMeans除了依赖初始点的选择之外,还非常的容易陷入局部最优点中,如3.1结果分析中的两种KMeans运行后返回的中心点均与设定的中心点有差异,在真实数据集中这种现象的影响会被放大,因此摆脱局部最优点的途径有二,其一是不断的更换初始中心点,使得能在不同的方向收敛,然后取其最有结果;其二是使用震荡因子,当收敛于最优点时再附加震荡因子使其摆脱局部最优点。其中方案一是最为行之有效也使用最广发的方案。
mean
是一种脆弱的计量
对比图2与图3,可知不论是何种初始化策略的KMeans都没有办法消除位于中间簇中的离群点的影响,均将其分配至簇3(位于右上角的簇)中,其本质是因为在对所有簇内样本点进行平均(mean)操作时产生的统计误差,这样的现象在真实得数据集中更为常见,影响可能也更大,因此在运行KMeans之前,进行数据预处理是必要的,剔除离群点以及对数据进行归一化,能够提升KMeans的性能。
高斯分布限制 KMeans本质上是在欧氏空间进行数据划分,对隐含高斯分布的数据集能够很好的运行,但是若对于那些可能并不隐含高斯分布或者无法在欧氏空间划分的数据就会表现得很糟糕,因此可以借鉴SVM的解决方式,使用核函数(kernal function)将其映射至更高维(无限维)的空间中,再对其进行划分。得益于KMeans算法简单,可复现度强,因此对公式2.1中的进行改造是易于进行的。
本文完成了KMeans在Python中的实现,并且对实验结果进行了对照,知KMeans算法在大部分的数据集上仅能计算出无限接近于真实的簇中心点,并且讨论了KMeans的若干不足以及提出了相应的改进方法,在多数情况下,运行KMeans算法前对数据进行预处理能够提高KMeans算法的聚类性能,在处理较低纬度不可分的数据时可以采用核函数将其映射至高维空间中,再划分。
Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall, Englewood Cliffs
Gray RM, Neuhoff DL (1998) Quantization. IEEE Trans Inform Theory 44(6):2325–2384
周志华, 机器学习, 2012.
Jiawei Han, 数据挖掘概念与技术, 2017.