k-means算法

发表于   |   分类于

算法简介

K-means 是一种无监督的聚类算法，对于给定的数据划分为K个簇，并且给出每个簇的中心。

K-means算法

数据预处理

数据预处理包括：
a.剔除离群点
b.数据归一化：0-1区间（由于k-means算法依赖于距离，因此必须保证每个维度的距离单位一致）
c.数据标准化：转化为正态分布

初始化：随机选择K个中心点

其中，(0)代表迭代次数

定义损失函数：

因为机器学习算法是通过学习完成一定的功能，迭代的方向谁来指定呢？—— 损失函数

t为迭代步数，重复下面a、b过程至算法收敛

a.对于每个样本点，将其分配到最近的簇

b.对于每个簇，重新计算聚类质心

K-means算法缺点

1.需要人工选择K值，不一定符合真实数据分布

2.受初始值和离群点的影响较大，稳定性较差。不同的初始值对应不同的迭代次数，离群点对于簇的中心点有影响，需要更多的轮数达到收敛

3.只能用于连续性变量

4.通常结果并非全部最优，而是局部最优（与初始值选取有关）

K-means算法优点

1.对于大数据集，算法时间复杂度为线性O(NKT)

N:样本点个数 K:聚类中心个数 T:迭代轮数

2.局部最优解通常已经满足问题的需要

K-means算法调优过程

K值选择

手肘法

原理是尝试不同的K值，横坐标：聚类个数K，纵坐标：误差平方和(损失函数) J，即各聚类的类内间距离和：

为什么曲线是递降的？考虑若只有10个样本，那么当聚类数K=10时，损失函数 J=0 （每个簇只有一个点，那么质心也为该点，即类间距离均为0）；当K=1时，即所有样本归属于一类，所有样本距离质心的距离最大（由于没有寻找距离样本最优的质心，因此距离最大）

在上图中，我们认为4是比较合理的，即拐点位置。

轮廓系数

评判标准：轮廓系数（silhouette coefficient）

a(i)：样本点与被划分到相同类别的其他样本点的距离，距离越小反映该样本点越应该与其他点划分为一类，也称为“内置度”，值越小越好

b(i)：样本点与其他类样本点距离，也称为“分离度”

S(i)会被限制在-1~1之间，当S(i)越接近-1则表示划分结果越差，越接近1则表示划分结果越好

轮廓系数等于所有点轮廓系数的平均值

最终需要结合手肘法和轮廓系数两个值来进行判断，在手肘法中寻找相对稳定的区域，轮廓系数越高越好。

K-means算法改进

由于受初始值的影响较大，影响算法稳定性（迭代次数），因此我们可以对初识值的选择进行优化 —— K-means++算法。

改进思想：选取第n+1个聚类中心时，距离其他聚类中心越远，被选中的概率越大

K-means算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from numpy import *
import pandas as pd
import DataFrame as df
import matplotlib.pyplot as plt

# 距离度量函数
def calc_distance(vec1, vec2):
    print(vec1)
    print(vec2)
    print(sqrt(sum(power(vec1 - vec2, 2))))
    return sqrt(sum(power(vec1 - vec2, 2)))
               
# 创建初始聚类质心  
def create_centroid(data, k):
    # 初始质心，随机选取的P1,P4,P7
    centroids = zeros((k,n))
    centroids[0,0] = 2
    centroids[0,1] = 10
    centroids[1,0] = 5
    centroids[1,1] = 8
    centroids[2,0] = 1
    centroids[2,1] = 2
    
    return centroids
                   

# k-means聚类
def kMeans(data, k, dist, create_center=create_centroid):
    # 初始化cluster_assment，存储中间结果
    # 第一列存储索引，第二列存储距离
    # 样本的个数
    m = shape(data)[0]
    init = zeros((m,2))
    cluster_assment = mat(init) # 转成矩阵,存储索引和距离
    
    # 初始化聚类中心矩阵
    centroids = create_centroid(data, k)
    
    for epoch in range(1): # 迭代一次
        # 对数据集中每个样本点进行计算
        for i in range(m):
            min_dist = inf # 用于记录最短的质心距离
            min_index = -1 # 用于记录最短的质心索引
            # 对每个样本点到质心的距离进行计算
            for j in range(k):
                dist_ij = calc_distance(centroids[j, :], data[i, :])
                # 找到距离最近的中心距离和索引
                if dist_ij < min_dist:
                    min_dist = dist_ij
                    min_index = j 
                    cluster_assment[i,:] = min_index, min_dist
                    
        # 对所有节点聚类之后，重新更新中心
        for i in range(k):
            # .A把矩阵转成数组
            pts_in_cluster = data[nonzero(cluster_assment[:,0].A==i)[0]]
            centroids[i:0] = mean(pts_in_cluster, axis=0)
            
    return centroids,cluster_assment
    
    
    
if __name__ == '__main__':
    # 创建数据集
    data = array([[2,10],[2,5],[8,4],[5,8],[7,5],[6,4],[1,2],[4,9]])
    k = 3 # k为聚类个数
    n = 2 # n为特征个数，数据维度
    
    centroids,cluster_assment = kMeans(data, k, dist=calc_distance, create_center=create_centroid);
    
    predict_label = cluster_assment[:,0]
    data_and_pred = column_stack((data, predict_label))
    
    # 转成df：原始数据样本和预测出来的类别
    df = pd.DataFrame(data_and_pred, columns =['data1','data2','pred'])
    df0 = df[df.pred == 0].values
    df1 = df[df.pred == 1].values
    df2 = df[df.pred == 2].values
    
    display(centroids)
    
    # 画图
    plt.scatter(df0[:,0],df0[:,1],c='turquoise',marker='o',label='label0')
    plt.scatter(df1[:,0],df1[:,1],c='green',marker='*',label='label1')
    plt.scatter(df2[:,0],df2[:,1],c='blue',marker='+',label='label2')
    plt.scatter(centroids[:, 0].tolist(), centroids[:, 1].tolist(), c='red')
    plt.legend(loc=2)
    plt.show()

算法调优代码

针对K值进行调优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

if __name__ == '__main__':
    # 创建数据集
    data = array([[2,10],[2,5],[8,4],[5,8],[7,5],[6,4],[1,2],[4,9]])
    
    # 手肘法调优：最终取3
    sse = []
    for i in range(1,9):
        mid = KMeans(n_clusters=i, init='random', n_init=10, max_iter=200)
        mid.fit(data)
        sse.append(mid.inertia_) #inertia为簇内误差平方和
        
    plt.plot(range(1,9), sse, marker='o')
    plt.xlabel('k')
    plt.ylabel('SSE')
    plt.show()