K-Means聚类分析实战

一、K-means算法原理

K-means算法是无监督学习算法中的聚类算法，根据特征上的相似性，把数据聚集在一起，或者说分成几类。

优点

1. 原理简单，实现方便，收敛速度快
2. 聚类效果优
3. 可解释性强
4. 超参数较少

缺点

1. 需要先决定k，即先确定聚类的类别数量，且k的选取不容易把握
2. 只能获得局部的最优解，对初始化簇心的位置敏感
3. 对噪音和异常点敏感
4. 对于不平衡的数据集和非凸数据集效果不好

基本思路

1. 首先选择好将数据分成k类，然后随机初始化k个点作为中心点。
2. 对于每一个数据点，选取与之距离最近的中心点作为自己的类别。
3. 当所有数据点都归类完毕后，调整中心点：把中心点重新设置为该类别中所有数据点的中心位置，每一轴都设置为平均值。（所以称为means）
4. 重复以上2)~3)步骤直至数据点的类别不再发生变化。

问题

随机初始化簇心是必须取存在的数据点的值吗？还是数据空间内随便一个点的值呢？
答：数据跨度范围内随机值，并不一定需要是存在的数据点

二、代码实现

实验环境：jupyter notebook + python3.7

导入代码的依赖库

# 数据操作
import numpy as np
import pandas as pd
# 数据可视化
import matplotlib.pyplot as plt
import seaborn as sns

K-means整个流程的实现需要基于三个函数：计算两个数据点间距离、初始化K个簇心、计算本次聚类的损失函数值

计算两个向量的欧几里得距离

def calDistEclud(vecA, vecB):
    return np.sqrt(sum(np.power(vecA - vecB, 2)))

随机初始化k个簇心

def randClusterCenter(dataset, k):
    n = np.shape(dataset)[1]  # 特征个数，也就是特征向量维度
    centroids = np.zeros((k, n))  # 初始化一个簇心数组k*n

    for j in range(n):  # 因为要计算单个特征跨度，所以是每次迭代分配一个特征给k个簇心
        feat_min = min(dataset[:, j])
        feat_range = float(max(dataset[:, j]) - feat_min)
        centroids[:, j] = feat_min + np.random.rand(k, ) * feat_range

    return centroids

计算损失函数值（和方差）

def lossFuncVal(clusterAssment):
    sse = sum(i ** 2 for i in clusterAssment[:, 1])
    return sse

K-means算法

def kMeans(dataset, k, calDist=calDistEclud, createClusCenter=randClusterCenter):
    centroids = createClusCenter(dataset, k)  # 初始化k个簇心
    m = np.shape(dataset)[0]  # 记录数据点个数
    clusterAssment = np.zeros((m, 2))  # 记录每个数据点被分配到的簇以及到簇心的距离
    clusterChanged = True  # 记录数据点归属类别是否产生变化，如果没有则结束算法

    while clusterChanged:
        clusterChanged = False
        for i in range(m):  # 遍历每一个数据点
            minCentIndex, minDist = -1, np.inf  # 记录最近簇心及到它的距离
            for j in range(k):  # 对于单个数据点，遍历每个簇心
                dist = calDist(dataset[i, :], centroids[j, :])  # 计算该数据点到每个簇心的距离
                if dist < minDist:
                    minDist, minCentIndex = dist, j  # 如果发现更近的簇心，则取代原来的
            if clusterAssment[i, 0] != minCentIndex:  # 如果某一个点的归属改变了
                clusterChanged = True  # 那么应该继续执行算法
            clusterAssment[i, :] = minCentIndex, minDist  # 更新数据点记录为最近的簇心及簇心距离

        for cent in range(k):
            ptsInClust = dataset[np.nonzero(clusterAssment[:, 0] == cent)]  # 寻找以该簇心为类别的所有数据点
            centroids[cent, :] = np.mean(ptsInClust, axis=0)  # axis=0对各列求均值，更新簇心位置为该类的中心位置

    return centroids, clusterAssment  # 返回簇心及每个数据点簇归属

将算法应用于实验数据

为了一定程度上解决基础版本的K-means对簇心初始位置敏感问题，我们多次运行K-means，然后选择使损失函数SSE最小的聚类结果。

k = 4
multi_random_run = 5

centroids_list = []
clusterAssment_list = []
lossFuncVal_list = []
data = pd.read_table('dataforkmeans - .txt', header=None, sep='    ', engine='python').values
for i in range(multi_random_run):
    centroids, clusterAssment = kMeans(data, k)
    centroids_list.append(centroids)
    clusterAssment_list.append(clusterAssment)
    lossFuncVal_list.append(lossFuncVal(clusterAssment))
print(lossFuncVal_list)
best_centroids = centroids_list[lossFuncVal_list.index(min(lossFuncVal_list))]
best_clusterAssment = clusterAssment_list[lossFuncVal_list.index(min(lossFuncVal_list))]

结果：[503.1469824561403, 503.1469824561403, 883.3927509617755, 503.1469824561403, 503.1469824561403]

发现中间产生了一次SSE比较大的结果，这说明了聚类结果确实受到随机初始化的影响，我们选择SSE最小的结果做可视化。

原始数据可视化

plt.figure(figsize=(10, 8))
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
data = pd.read_table('dataforkmeans - .txt', header=None, sep='    ', engine='python').values
plt.title('原始数据分布', fontsize=20)
plt.xlabel('数据特征1')
plt.ylabel('数据特征2')
sns.scatterplot(data[:, 0], data[:, 1])
plt.show()

聚类结果可视化

plt.figure(figsize=(10, 8))
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
d = dataframe[clusterResult[u'聚类类别'] == '0']
sns.scatterplot(d[0], d[1], color='r', marker='o')
d = dataframe[clusterResult[u'聚类类别'] == '1']
sns.scatterplot(d[0], d[1], color='b', marker='o')
d = dataframe[clusterResult[u'聚类类别'] == '2']
sns.scatterplot(d[0], d[1], color='c', marker='o')
d = dataframe[clusterResult[u'聚类类别'] == '3']
sns.scatterplot(d[0], d[1], color='y', marker='o')
plt.ylabel('数据特征2')
plt.xlabel('数据特征1')
plt.title('聚类结果', fontsize=20)
plt.show()

三、不足和改进方案

1. K-means++优化初始化簇心的策略，原则是尽可能使初始簇心分开，减少迭代次数，加快运算速度
2. elkan K-means利用三角形性质优化距离计算策略
3. 在数据量非常大时，采用Mini Batch K-means更快地收敛
4. 使用二分K-means克服基础算法收敛于局部最小值的问题

四、参考资料

1. https://blog.csdn.net/l18930738887/article/details/50629409 SSE,MSE,RMSE,R-square指标讲解
2. https://www.cnblogs.com/DOLFAMINGO/p/9360120.html 吴恩达机器学习笔记（七） —— K-means算法
3. https://blog.csdn.net/weixin_42029738/article/details/81978038 K-means原理、优化及应用
4. https://blog.csdn.net/lbweiwan/article/details/82759670 K-means聚类分析，并用t-SNE可视化聚类结果