- 本文上接：【数据聚类】第三章第二节2：K-Means算法及其Python实现（算法实现、结果展示）
- 本文下接：
- 六：性能分析
- （1）时间复杂度
- （2）空间复杂度
- 七：优缺点
- （1）优点
- （2）缺点
- 补充：关于凸数据和非凸数据
- 八：关于K值的选择
- （1）“手肘法”
- （2）轮廓系数
- （3）Calinski-Harabasz指标
- 九：聚类算法评估指标
K K K- M e a n s Means Means算法时间复杂度可以表示为
O ( i × k × n × m ) O(i×k×n×m) O(i×k×n×m)
- i i i：收敛所需要的迭代次数
- k k k：簇的个数
- n n n：数据集中包含的数据点个数
- m m m：每个数据的属性数
由于收敛大多发生在早期阶段，所以 i i i值通常较小，因此只要 k k k显著小于 n n n，那么 K K K- M e a n s Means Means计算时间就与 n n n是线性相关的
（2）空间复杂度K K K- M e a n s Means Means算法空间复杂度可以表示为
O ( ( k + n ) × m ) O((k+n)×m) O((k+n)×m)
- k k k：簇的个数
- n n n：数据集中包含的数据点个数
- m m m：每个数据的属性数
优点有：
- 该算法适用于各种数据类型
- 当潜在的簇形状是凸、簇与簇之间大小相近且差异明显时，聚类结果效果明显
- 对于规模很大的数据集合，该算法非常高效且伸缩性好
缺点有：
- 一旦在某一问题中，无法定义簇内数据点的平均值时，那么该算法将无法发挥效果，所以该算法在处理具有分类属性的数据时就无从下手
- k k k值和初始中心点的选择对算法结果有很大的影响；不合适的设定很容易造成算法最终收敛到局部最优，这使得算法对先验知识具有较强的依赖性
- 该算法对噪声点和离群点十分敏感，少量异常数据就会对簇内平均值的计算造成很大干扰，这种干扰甚至会导致簇划分的不合理
- 难以聚类非凸数据
关于 K K K- M e a n s Means Means算法的不足，许多学者针对以上几个方面也做出了改进，具体将会在后面的文章介绍
补充：关于凸数据和非凸数据关于凸数据和非凸数据，可以这样直观区分
-
凸数据：可以用一条直线将数据集轻松分开
-
非凸数据：无法用直线分开数据集
对于凸数据：它沿着梯度方向走一定可以得到最优解，对应于凸函数（任意两点连线上所有的点都在函数图像的下方）
对于非凸数据：它沿着梯度方向走到底只能保证局部最优，无法保证全局最优，对应于非凸函数（两点连线上的点可能分布在函数图像的两侧）
K K K- M e a n s Means Means算法最让人诟病的地方就是簇个数 K K K的选择，因为它十分依赖于先验知识、经验，所以在实际处理过程中用户往往需要一些辅助方法去确定 K K K的个数
（1）“手肘法”手肘法：设置一个最大的阈值，让 k k k从小逐渐增大，观察 S S E SSE SSE的变化选取合适的 k k k，即绘制 k k k- S S E SSE SSE图。观察图像，在最初 k k k很小时， k k k的增大会使 S S E SSE SSE的值迅速减小；当 k k k增加到一定的数值时， S S E SSE SSE的减小速度会减慢，之后趋于平缓。因此，选取图像中的拐点附近的值作为 k k k的初始值，就可以得到很好的聚类效果
如下，借助sklearn中的 K K K- M e a n s Means Means算法，以鸢尾花数据集为例，绘制出 k k k- S S E SSE SSE图
# 导入所需模块
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
from sklearn.metrics import silhouette_score
from sklearn.metrics import calinski_harabasz_score
# 导入鸢尾花数据集
iris = load_iris()
X = iris.data[:]
# print(X)
print(X.shape)
# 肘方法看k值
d = []
for i in range(1, 11): # k取值1~11，做kmeans聚类，看不同k值对应的SSE
km = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=300, random_state=0)
km.fit(X)
d.append(km.inertia_) # inertia簇内误差平方和
plt.figure(figsize=(12, 10), dpi=80)
plt.subplot(2, 1, 1) # 第一幅图正常显示
plt.plot(range(1, 11), d, marker='o')
plt.xlabel('number of clusters')
plt.ylabel('distortions')
plt.subplot(2, 1, 2) # 第二幅图放大一点
plt.plot(range(1, 11), d, marker='o')
plt.xlabel('number of clusters')
plt.ylabel('distortions')
plt.axis([1, 4, 0, 600])
plt.show()
可以看出 k k k=3后，曲线趋于平缓，所以建议 k k k取3
（2）轮廓系数轮廓系数：对于一个聚类任务，我们希望得到的类别簇中，簇内尽量紧密，簇间尽量远离，轮廓系数便是类的密集与分散程度的评价指标，，公式如下
s ( i ) = b ( i ) − a ( i ) m a x { a ( i ) , b ( i ) } s(i)=frac{b(i)-a(i)}{max{{a(i),b(i)}}} s(i)=max{a(i),b(i)}b(i)−a(i)
其中
- a ( i ) a(i) a(i)（越小越好）：表示样本 i i i到同簇其它样本的平均距离； a ( i ) a(i) a(i)说明样本 i i i就越应该被分到该簇，且将 a ( i ) a(i) a(i)称为样本 i i i的簇内不相似度
- b ( i ) b(i) b(i)（越大越好）：表示样本 i i i到其他某簇 C j C_{j} Cj的所有样本的平均距离 b i j b_{ij} bij,称为样本 i i i与某簇 C j C_{j} Cj的不相似度； b ( i ) = m i n { b i 1 , b i 2 , . . . , b i k } b(i)=min{b_{i1},b_{i2},...,b_{ik}} b(i)=min{bi1,bi2,...,bik}
轮廓系数 s ( i ) s(i) s(i)的取值范围为[-1, 1]，且
- 若 s ( i ) s(i) s(i)接近1（ a ( i ) a(i) a(i)< b ( i ) b(i) b(i)）：说明样本 i i i聚类合理（轮廓系数越大越好）
- 若 s ( i ) s(i) s(i)接近-1（ a ( i ) a(i) a(i)> b ( i ) b(i) b(i)）：说明样本 i i i更应该分类到另外的簇上，聚类效果很差
- 若 s ( i ) s(i) s(i)接近0（ a ( i ) a(i) a(i)= b ( i ) b(i) b(i)）：说明样本 i i i在两个簇的边界上
如下，借助sklearn中的KK-MeansMeans算法，以鸢尾花数据集为例
# 导入所需模块
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
from sklearn.metrics import silhouette_score
from sklearn.metrics import calinski_harabasz_score
# 导入鸢尾花数据集
iris = load_iris()
X = iris.data[:]
# print(X)
print(X.shape)
# 肘方法看k值
d = []
for i in range(2, 11): # k取值1~11，做kmeans聚类，看不同k值对应的簇内误差平方和
km = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=300, random_state=0)
km.fit(X)
d.append(silhouette_score(X, km.labels_)) # 轮廓系数
print(d)
plt.figure(figsize=(12, 5), dpi=80)
plt.plot(range(2, 11), d, marker='o')
plt.xlabel('number of clusters')
plt.ylabel('distortions')
plt.show()
可以看出，当 k k k=2时轮廓系数最大，虽然实际种类为3（这也说明了这些方法只是一种参考，和先验知识并不是一定一致的）
（3）Calinski-Harabasz指标轮廓系数CH指标通过计算类中各点与类中心的距离平方和来度量类内的紧密度，通过计算各类中心点与数据集中心点距离平方和来度量数据集的分离度，公式为
C H ( K ) = B ( K ) ( N − K ) W ( K ) ( K − 1 ) CH(K)=frac{B(K)(N-K)}{W(K)(K-1)} CH(K)=W(K)(K−1)B(K)(N−K)
其中：
- B ( K ) B(K) B(K)为类间散度（分散度）： B ( K ) = ∑ k = 1 K a k ∣ ∣ X k ‾ − X ‾ ∣ ∣ 2 B(K)=sum_{k=1}^{K}a_{k}||overline{X_{k}}-overline{X}||^{2} B(K)=∑k=1Kak∣∣Xk−X∣∣2
- W ( K ) W(K) W(K)为类内散度（紧密度）： W ( K ) = ∑ k = 1 K ∑ C j = k ∣ ∣ X j − X k ‾ ∣ ∣ 2 W(K)=sum_{k=1}^{K}sum_{C_{j}=k}||X_{j}-overline{X_{k}}||^{2} W(K)=∑k=1K∑Cj=k∣∣Xj−Xk∣∣2
因此，CH指标由分离度与紧密度的比值得到，所以，CH越大代表着类自身越紧密，类与类之间越分散，即更优的聚类结果
九：聚类算法评估指标聚类算法评价指标分为外部评估和内部评估，如下
- 外部评估： 将结果与某个“参考模型”（reference model）进行比较
- 内部评估： 直接考虑聚类结果而不利用任何参考模型
