聚类（K-Means聚类）原理与代码实现

目标
将样本集D划分为若干互不相交的子集，即样本族
结果
族内相似度高，且族间相似度低

将聚类结果与某个“参考模型”进行比较----外部指标
Jaccard系数（JC) [0,1]
FM指数（FMI） [0,1]
Rand指数（RI） [0,1]
**上述指数越大越好 **

直接考察聚类结果而不利用任何参考模型------内部指标
DB指数（DBI） 越小越好
Dunn指数（DI） 越大越好

有序属性
{1，2，3，…}
指标：闵可夫斯基距离（p=1曼哈顿距离，p=2欧氏距离）

离散属性（无序属性）
{飞机，火车，轮船}
指标：VDM距离

混合属性
{1，飞机，2，轮船}
指标：闵可夫斯基距离 + VDM距离

算法

输入：
       样本集D = {x(1), x(2), x(3),...,x(m)}
       聚类族数k
过程：
1. 从D中**随机选择**k个样本作为**初始**均值向量{u(1), u(2),...,u(k)}
2. Repeat
	 3. for j = 1,2,...,m do
            计算样本x(j)到这k个样本的距离(即与各均值向量之间的距离）
            将样本x(j)分别归入距离最小的一类
        end for 
     4. for i=1,2,3,...,k do
     	    计算得到的k个类的新的均值向量{u‘(1）, u'(2), ..., u'(k)}
     		if u' != u then
     			将当前均值向量u更新为u'
     		else
     			保持当前均值向量不变
     		end if
     	end for
5.untile 当前均值向量均未更新  (前面相当于迭代）   
输出：
      族划分 C = {C1, C2, C3,...,CK}
备注：为避免运行时间过长，通常设置一个最大运行轮数或最小调整
幅度阈值，若未达到最大轮数或者调整幅度小于阈值，则停止运行。

注
K均值聚类采用的是随机选择K个样本作为初始的均值向量 ，k-means++ 以一种智能的方式为 k-means 聚类选择初始聚类中心以加速收敛。

样本数据带有label

采用概率模型对原型进行刻画，族划分由原型对应后验概率确定

基于密度的刻画
通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类族来获得最终结果

在不同层次对数据集进行划分，从而形成树形的聚类结构

# 导入包
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

# 数据介绍
# x (n_samples:150, features:2)
# 聚类
# n_clusters:要形成的簇数k。 init:初始化方式，random/kmeans++。n_init:使用不同质心种子运行算法的次数，最终输出最佳结果。max_inter: 最大迭代次数。tol:范数收敛的阈值。
model = KMeans(n_clusters=3, init='random', n_init=10, max_inter=300, tol=1e-04, random_state=0) 
# 训练+预测
y_pred = model.fit_predict(x)

# 画出预测的三个族类
plt.scatter(x[y_pred==0, 0], x[y_pred==0, 1],
            s=50, c='lightgreen', marker='s', edgecolors='black',
            label='cluster 1')
plt.scatter(x[y_pred==1, 0], x[y_pred==1, 1],
            s=50, c='orange', marker='o', edgecolors='black',
            label='cluster 2')
plt.scatter(x[y_pred==2, 0], x[y_pred==2, 1],
            s=50, c='lightblue', marker='v', edgecolors='black',
            label='cluster 3')
#画出聚类的中心
plt.scatter(model.cluster_centers_[:, 0],
            model.cluster_centers_[:, 1],
            s=50, marker='*', edgecolors='black', c='red',
            label='centroids')
plt.legend(scatterpoints=1)  # 为散点图图例条目创建的标记点数  
plt.grid() # 显示网格线 1=True=默认显示；0=False=不显示
plt.show()

# 计算inertia（轮廓系数）随k变化的情况
distortions = []
for i in range(1,10):
    model = KMeans(
        n_clusters=i, init='random',
        n_init=10, max_iter=300,
        tol=1e-04, random_state=0
    )
    model.fit(x)
    distortions.append(model.inertia_)
#画图可以看出k越大，inertia越小， 追求k越大对应用无益处
# 每个簇内到其质心的距离相加，叫inertia。各个簇的inertia相加的和越小，即簇内越相似。（但是k越大inertia越小，追求k越大对应用无益处
plt.figure()
plt.plot(range(1,10), distortions, marker='o')
plt.xlabel('Number of cluster')
plt.ylabel('Distortion')
plt.show()

理论参考： 《西瓜书》BY 周志华
代码参考： github: datawhalechina
机器学习笔记