《机器学习算法与实现》2、k均值聚类算法

xinmeng_wit

《机器学习算法与实现》2、k均值聚类算法 [复制链接]

一、k均值聚类算法介绍

k均值聚类算法是一种简单的迭代型算法，它使用距离来评判相似性，发现给定数据集中的k个类别，其中每个类别的中心都由该类别中的所有值的均值得到，最后每个类别由聚类中心描述。

聚类目标是使得每个样本到其类别中心点的特征距离的平方和最小，一般使用欧式距离作为特征距离。

下面是k均值聚类算法的基本原理：

1. 选择初始中心：随机选择k个数据点作为初始的簇中心。

2. 分配数据点：将每个数据点分配到最近的簇中心，形成k个簇。

3. 更新簇中心：重新计算每个簇的中心点，通常是簇内所有点的均值。

4. 迭代优化：重复步骤2和3，直到满足以下任一条件：

   • 簇中心不再发生显著变化。
   • 达到预设的迭代次数。
   • 簇内数据点的分配不再发生变化。

5. 聚类结果：最终的簇中心和数据点的分配结果即为聚类结果。

k均值聚类算法的关键在于如何选择初始簇中心以及如何定义“最近”。算法的性能很大程度上依赖于初始簇中心的选择，因为不同的初始选择可能导致不同的聚类结果。此外，k均值聚类对噪声和异常值比较敏感，因为它们可能会对簇中心的计算产生较大影响。

k均值聚类算法的优点是简单、易于实现，且在处理大数据集时相对高效。但它也有一些局限性，比如需要预先指定k值，对初始簇中心的选择敏感，以及只能发现圆形或球形的簇形状。尽管如此，k均值聚类仍然是许多领域中常用的聚类方法之一。

数学上k均值聚类用代价函数来衡量聚类效果，公式为

聚类的目的就是使J取得最小值。

其中uk是第k个类的中心位置，定义为：

其中，Ck是第k类的样本数量。

 

如果要实现以上算法，那么代码需要循环执行以下两个步骤：

1、将每个训练样本xi分配给最近的类（簇）的中心（重心）；

2、将每个簇的重心uj更新为与之距离最佳的训练样本的平均值。

 

k均值聚类算法也有它自己的缺点：

1、聚类中心的个数k需要事先给定，但在实际中k值的选定非常难以估计，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；

2、k均值需要人为地确定，或者随机选择初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用k均值++算法来解决）

 

二、算法过程演示

1、首先准本样本数据

import matplotlib.pyplot as plt
import numpy as np

x0 = np.array([7, 5, 7, 3, 4, 1, 0, 2, 8, 6, 5, 3])
x1 = np.array([5, 7, 7, 3, 6, 4, 0, 2, 7, 8, 5, 7])

plt.figure()
plt.axis([-1, 9, -1, 9])
plt.grid(True)
plt.plot(x0, x1, 'k.')
plt.show()

假设随机取点（4, 6）和（5, 5）作为第一类和第二类的中心，然后就可以计算出各个样本距离这两个中心的距离了。

经过计算，所有样本与c1中心（4, 6）的距离为[10  2 10 10  0 13 52 20 17  8  2  2]

                  所有样本与c2中心（5, 5）的距离为[ 4   4  8   8   2 17 50 18 13  10 0 8]

根据这个结果，就可以知道每个样本属于c1还是c2.

属于c1的样本为第1, 4, 5, 9个样本，属于c2的样本为第0,2,3，6,7,8,10个样本

因此，可以画出第一次聚类结果：

    然后，根据上图再更新c1和c2的中心，更新以后中心变成了c1（4, 6.25）， c2（4.57, 4.14）

然后再重复上面的计算过程， 直到每个样本的所属类别都不再改变时，即确定了样本的聚类。

相关代码：

import matplotlib.pyplot as plt
import numpy as np

x0 = np.array([7, 5, 7, 3, 4, 1, 0, 2, 8, 6, 5, 3])
x1 = np.array([5, 7, 7, 3, 6, 4, 0, 2, 7, 8, 5, 7])

plt.figure()
plt.axis([-1, 9, -1, 9])
plt.grid(True)
plt.plot(x0, x1, 'k.')
plt.show()

# 画出第一类和第二类的样本
c1 = [1, 4, 5, 9, 11]
c2 = list(set(range(12)) - set(c1))

x0c1, x1c1 = x0[c1], x1[c1]
x0c2, x1c2 = x0[c2], x1[c2]

plt.figure()
plt.title('1st iteration results')
plt.axis([-1, 9, -1, 9])
plt.plot(x0c1, x1c1, 'rx')
plt.plot(x0c2, x1c2, 'g.')
plt.plot(4, 6, 'rx', ms=12.0)
plt.plot(5, 5, 'g.', ms=12.0)
plt.show()

def distance(x1, y1, x2, y2):
    '''求两点之间的距离的平方'''
    return (np.square(x1 - x2) + np.square(y1 - y2))

# 指定c1和c2的中心
C1 = [4, 6]
C2 = [5, 5]

# 每个样本的距离
c1_distance = []
c2_distance = []

for i in range(len(x0)):
    c1_distance.append(distance(x0, x1, C1[0], C1[1]))
    c2_distance.append(distance(x0, x1, C2[0], C2[1]))

print('c1 distance:')
print(np.array(c1_distance))
print('c2 distance:')
print(np.array(c2_distance))

C1[0] = float(np.average(np.array([x0[1], x0[4], x0[5], x0[9]])))
C1[1] = float(np.average(np.array([x1[1], x1[4], x1[5], x1[9]])))
print(C1)

C2[0] = float(np.average(np.array([x0[0], x0[2], x0[3], x0[6], x0[7], x0[8], x0[10]])))
C2[1] = float(np.average(np.array([x1[0], x1[2], x1[3], x1[6], x1[7], x1[8], x1[10]])))
print(C2)

 

三、k均值聚类算法编程实现

下面编成来实现k均值聚类算法。

首先使用模拟的方法生成满足高斯分布的随机数据作为数据集来演示算法。

# 加载第三方库
import numpy as np
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import random

# 生成数据
centers = [(7, 0), (0 ,0), (5, 5)]
n_samples = 500

x, y = make_blobs(n_samples=n_samples, n_features=2,
                  cluster_std=1.0, centers=centers,
                  shuffle=True, random_state=42)
                  
# 画出数据
plt.figure(figsize=(15, 9))
plt.scatter(x[:,0], x[:,1], c=y)
plt.colorbar()
plt.show()

生成的数据如下图：

生成数据后就可以正式开始编写k均值聚类算法了，最终通过算法将上面的样本分成3类。

算法如下：

# k均值聚类算法的主体程序
def calc_distance(v1, v2):
    '''
    计算两个向量之间的距离
    v1 - 特征1
    v2 - 特征2
    '''
    return np.sum(np.square(v1 - v2))

def rand_cluster_cents(x, k):
    '''
    初始化聚类的中心：将在区间内随机产生的值作为新中心点。参数为：
    x - 数据样本
    k - 聚类个数
    '''

    # 样本数
    n = np.shape(x)[0]

    # 生成随机的下标列表
    dataIndex = list(range(n))
    random.shuffle(dataIndex)
    centroidsIndex = dataIndex[:k]

    # 返回随机的聚类中心
    return x[centroidsIndex, :]

def kmeans(x, k):
    '''
    kMeans算法, 参数为：
    x - 数据样本
    k - 聚类个数
    '''

    # 样本总数
    n = np.shape(x)[0]

    # 分配样本到最近的簇：保存[簇序号，距离的平方] （n行 x 2列）
    clusterAssment = np.zeros((n, 2))

    # step1:通过随机产生的样本点初始化聚类中心
    centroids = rand_cluster_cents(x, k)
    print('最初的中心=', centroids)

    iterN = 0

    while True:
        clusterChanged = False
        
        # step2: 分配到最近的聚类中心对应的簇中
        for i in range(n):
            minDist = np.inf
            minIndex = -1
            for j in range(k):
                # 计算第i个样本到第j个中心点的距离
                distJI = calc_distance(centroids[j, :], x[i, :])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j

            # 样本上次的分配结果与本次的不一样，标志位clusterChanged置为True
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True

            clusterAssment[i, :] = minIndex, minDist ** 2 # 分配样本到最近的簇
        
        iterN += 1
        sse = sum(clusterAssment[:, 1])
        print('the SSE of %d' % iterN + 'the iteration is %f' % sse)

        # step3: 更新聚类中心
        for cent in range(k): # 样本分类结束后，重新计算聚类中心
            ptsInClust = x[clusterAssment[:, 0] == cent, :]
            centroids[cent, :] = np.mean(ptsInClust, axis=0)

        # 如果聚类中心未发生变化，则推出迭代
        if not clusterChanged:
            break

    return centroids, clusterAssment

k = 3
mycentroids, clusterAssment = kmeans(x, k)


# k均值聚类结果可视化
def datashow(dataSet, k, centroids, clusterAssment):
    '''
    二维空间显示聚类结果
    '''
    num, dim = np.shape(dataSet) # 样本数num，维数dim
    if dim != 2:
        print('sorry,the dimension of your dataset is not 2!')
        return 1
    # 样本图形标记
    marksamples = ['or', 'ob', 'og', 'ok', '^r', '^b', '<g']
    if k > len(marksamples):
        print('sorry, your k is too large!')
        return 1
    # 绘制所有样本
    for i in range(num):
        # 矩阵形式转换为int值，簇序号
        markindex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], marksamples[markindex], markersize=6)

    # 绘制中心点
    markcentroids = ['o', '*', '^'] # 聚类中心图形标记
    label = ['0', '1', '2']
    c = ['yellow', 'pink', 'red']
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], markcentroids[i], markersize=15, label=label[i], c=c[i])
        plt.legend(loc='upper left')
    plt.xlabel('特征1')
    plt.ylabel('特征2')

    plt.title('k-means cluster result')
    plt.show()

datashow(x, k, mycentroids, clusterAssment)

分类完成后的效果如下图：

分类出来的结果是完全正确的，当然，这是在已知k=3的情况下进行的分类，如果事先不知道k的值是多少，恐怕效果没这么好。

但是这个例子对于学习和理解k均值聚类算法还是非常有帮助的。

同样地，与k最近邻算法一样，sklearn已经集成了现成可用的k均值聚类算法，而且比我们自己实现的算法更好，实际使用中肯定优先使用sklearn中现成的轮子。

有兴趣的同学可以使用sklearn的k均值聚类算法试一试。

后面如果有空，我会再分享一篇使用sklearn的kMearns的例子。

Jacktang

用sklearn的k均值聚类算法是不是更难一点呢

xinmeng_wit

Jacktang 发表于 2024-7-13 09:22 用sklearn的k均值聚类算法是不是更难一点呢

实际上，我觉得会 更简单，毕竟不用关注很多细节，调用API就可以了