瞎聊机器学习——K-均值聚类（K-means）算法

本文中我们将会聊到一种常用的无监督学习算法——K-means。

1、K-means算法的原理

K-means算法是一种迭代型的聚类算法，在算法中我们首先要随机确定K个初始点作为质心，然后去计算其他样本距离每一个质心的距离，将该样本归类为距离最近的一个质心所属类别中（一个簇中）。

举个例子来表述一下：

如图所示，我们进行反向思考，我设定四个固定的随机点的位置（红色点），在每一个点的附近都随机生成50个蓝色点，对所有的蓝色点进行聚类分析，如果设定簇的数量为4个（K=4）,是不是最后的结果越靠近这四个红色的点越好呢？当然在寻找最优解的过程中图中的每一个蓝色的点都可以当做要选取的质心，我们进行的是一个迭代求解的过程，下面说一下K-means算法的步骤：

（1）随机选取数据中的K个对象作为聚类中心，每个对象都代表一个类（K个类的确定）；

（2）计算每一个样本到每一个聚类中心的距离（欧氏距离），将该样本分到距离最近的那个类的簇中；

（3）遍历每一个簇，算出每个簇的中心，将该中心作为新的聚类中心；

（4）重复进行（2）（3），直到聚类中心不再发生变化为止。

2、K-means算法的优缺点

优点：对于聚类算法来说K-means算法原理简单；计算复杂度是O(NKt)，N为数据对象的数目，K是聚类中心的数目，t是迭代的次数；对于大数据集的处理，K-means算法具有可伸缩性和高效性。

缺点：需要预先设定K值，K值得设定和真实的数据样本未必是吻合的；求解的结果是局部最优而非全局最优（当数据簇的分布差异较大时表现的不好）；容易受到噪声点的影响；样本最后只能被分到单一的类别中。

3、K-means算法中K值的选择

K值得选择是K-means算法中最大的问题之一，也是该算法的主要缺点所在，然而K值的选择一般都要基于经验和多次试验的结果，我们可以将不同K值下的平均距离进行绘图：

根据图片我们可以看出当K=(1~4)时，K值下的平均距离急速下降，当K>4时，曲线趋于平稳，此时我们可以认为K=4就是最佳的K值。

4、K-means算法的代码实现

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

# 先在四个中心点附近产生一堆数据
real_center = [(1, 1), (1, 2), (2, 2), (2, 1)]
point_number = 50

points_x = []
points_y = []
k_x = []
k_y = []
for center in real_center:
    offset_x, offset_y = np.random.randn(point_number) * 0.3, np.random.randn(point_number) * 0.25
    x_val, y_val = center[0] + offset_x, center[1] + offset_y
    k_x.append(center[0])
    k_y.append(center[1])
    points_x.append(x_val)
    points_y.append(y_val)

points_x = np.concatenate(points_x)  # 将二维数组拼接成一个list
points_y = np.concatenate(points_y)


# plt.scatter(k_x,k_y,c='r')
# plt.scatter(points_x, points_y, c='b')
# plt.show()

def k_means(K, p_list, center):
    points_set = {key: [] for key in range(K)}
    for p in p_list:
        # np.argmin返回（距离）最小值的下标，参数axis=1
        nearest_index = np.argmin(np.sum((centeroid - p) ** 2, axis=1) ** 0.5)
        points_set[nearest_index].append(p)
    # point_set = {0:[([x1,y1]),([x2,y2]),......],1:[],......}
    for k_index, p_set in points_set.items():
        p_xs = [p[0] for p in p_set]
        p_ys = [p[1] for p in p_set]
        center[k_index, 0] = sum(p_xs) / len(p_set)
        center[k_index, 1] = sum(p_ys) / len(p_set)
    return center, points_set


K = 4
# 用np.stack将points_x和points_y拼接，变成（x,y）的坐标形式   p_list.shape(200,2)
p_list = np.stack([points_x, points_y], axis=1)
# 通过choice函数随机选出K个聚类中心
index = np.random.choice(len(p_list), size=K)
centeroid = p_list[index]
print(centeroid)
k_means(K, p_list, centeroid)

for i in range(10):
    center, point_set = k_means(K, p_list, centeroid)
print(center)             # 输出聚类中心
print(point_set)          # 输出聚类后的每个簇

# 利用Sklearn中的kmeans绘制出K值及其聚类簇中平均距离的折线图，取得最佳K值
# loss = []
# for i in range(1, 10):
#     kmeans = KMeans(n_clusters=i, max_iter=100).fit(p_list)
#     loss.append(kmeans.inertia_ / point_number / K)
#
# plt.plot(range(1, 10), loss)
# plt.show()