K-means（K均值）算法是最简单的一种聚类算法，它期望最小化平方误差

注：为避免运行时间过长，通常设置一个最大运行轮数或最小调整幅度阈值，若到达最大轮数或调整幅度小于阈值，则停止运行。

下面我们用python来实现一下K-means算法：我们先尝试手动实现这个算法，再用sklearn库中的KMeans类来实现。数据我们采用《机器学习》的西瓜数据(P202表9.1):

# 下面的内容保存在 melons.txt 中
# 第一列为西瓜的密度；第二列为西瓜的含糖率。我们要把这30个西瓜分为3类
0.697 0.460
0.774 0.376
0.634 0.264
0.608 0.318
0.556 0.215
0.403 0.237
0.481 0.149
0.437 0.211
0.666 0.091
0.243 0.267
0.245 0.057
0.343 0.099
0.639 0.161
0.657 0.198
0.360 0.370
0.593 0.042
0.719 0.103
0.359 0.188
0.339 0.241
0.282 0.257
0.748 0.232
0.714 0.346
0.483 0.312
0.478 0.437
0.525 0.369
0.751 0.489
0.532 0.472
0.473 0.376
0.725 0.445
0.446 0.459

手动实现

我们用到的库有matplotlib和numpy，如果没有需要先用pip安装一下。

import random
import numpy as np
import matplotlib.pyplot as plt

下面定义一些数据：

k = 3 # 要分的簇数
rnd = 0 # 轮次，用于控制迭代次数（见上文）
ROUND_LIMIT = 100 # 轮次的上限
THRESHOLD = 1e-10 # 单轮改变距离的阈值，若改变幅度小于该阈值，算法终止
melons = [] # 西瓜的列表
clusters = [] # 簇的列表，clusters[i]表示第i簇包含的西瓜

从melons.txt读取数据，保存在列表中：

f = open('melons.txt', 'r')
for line in f:
	# 把字符串转化为numpy中的float64类型
    melons.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))

从 m m m个数据中随机挑选出 k k k个，对应上面算法的第 1 1 1行：

# random的sample函数从列表中随机挑选出k个样本（不重复）。我们在这里把这些样本作为均值向量
mean_vectors = random.sample(melons, k)

下面是算法的主要部分。

# 这个while对应上面算法的2-17行
while True:
    rnd += 1 # 轮次增加
    change = 0 # 把改变幅度重置为0

	# 清空对簇的划分，对应上面算法的第3行
    clusters = []
    for i in range(k):
        clusters.append([])
    # 这个for对应上面算法的4-8行
    for melon in melons:
    	'''
    	argmin 函数找出容器中最小的下标，在这里这个目标容器是
    	list(map(lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors)),
    	它表示melon与mean_vectors中所有向量的距离列表。
    	(numpy.linalg.norm计算向量的范数,ord = 2即欧几里得范数，或模长)
    	'''
        c = np.argmin(
            list(map( lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors))
        )
        clusters[c].append(melon)
	# 这个for对应上面算法的9-16行
    for i in range(k):
    	# 求每个簇的新均值向量
        new_vector = np.zeros((1,2))
        for melon in clusters[i]:
            new_vector += melon
        new_vector /= len(clusters[i])

        # 累加改变幅度并更新均值向量
        change += np.linalg.norm(mean_vectors[i] - new_vector, ord = 2)
        mean_vectors[i] = new_vector
	# 若超过设定的轮次或者变化幅度
 
   ROUND_LIMIT or change < THRESHOLD:
        break
print('最终迭代%d轮'%rnd)
 

最后我们绘图来观察一下划分的结果：

colors = ['red', 'green', 'blue']

# 每个簇换一下颜色，同时迭代簇和颜色两个列表
for i, col in zip(range(k), colors):
    for melon in clusters[i]:
    	# 绘制散点图
        plt.scatter(melon[0], melon[1], color = col)
plt.show()

划分结果（由于最开始的 k k k个均值向量随机选取，每次划分的结果可能会不同）:

完整代码：

import random
import numpy as np
import matplotlib.pyplot as plt

k = 3
rnd = 0
ROUND_LIMIT = 10
THRESHOLD = 1e-10
melons = []
clusters = []
f = open('melons.txt', 'r')
for line in f:
    melons.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))
mean_vectors = random.sample(melons, k)

while True:
    rnd += 1
    change = 0
    clusters = []
    for i in range(k):
        clusters.append([])
    for melon in melons:
        c = np.argmin(
            list(map( lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors))
        )
        clusters[c].append(melon)
    for i in range(k):
        new_vector = np.zeros((1,2))
        for melon in clusters[i]:
            new_vector += melon
        new_vector /= len(clusters[i])

        change += np.linalg.norm(mean_vectors[i] - new_vector, ord = 2)
        mean_vectors[i] = new_vector

    if rnd > ROUND_LIMIT or change < THRESHOLD:
        break
print('最终迭代%d轮'%rnd)
colors = ['red', 'green', 'blue']
for i, col in zip(range(k), colors):
    for melon in clusters[i]:
        plt.scatter(melon[0], melon[1], color = col)
plt.show()

sklearn库中的KMeans

这种经典算法显然不需要我们反复地造轮子，被广泛使用的python机器学习库sklearn已经提供了该算法的实现。sklearn的官方文档中给了我们一个示例：

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([1, 0], dtype=int32)
>>> kmeans.cluster_centers_
array([[10.,  2.],
       [ 1.,  2.]])

可以看出，X即要聚类的数据(1,2),(1,4),(1,0)等。

KMeans类的初始化参数n_clusters即簇数 k k k;

random_state是用于初始化选取 k k k个向量的随机数种子;

kmeans.labels_即每个点所属的簇；

kmeans.predict方法预测新的数据属于哪个簇;

kmeans.cluster_centers_返回每个簇的中心。

我们就改造一下这个简单的示例，完成对上面西瓜的聚类。

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

X = []
f = open('melons.txt', 'r')
for line in f:
    X.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))
kmeans = KMeans(n_clusters = 3, random_state = 0).fit(X)
colors = ['red', 'green', 'blue']
for i, cluster in enumerate(kmeans.labels_):
    plt.scatter(X[i][0], X[i][1], color = colors[cluster])
plt.show()

运行结果如下，可以看到和我们手写的聚类结果基本一致：

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：mmqy2019@163.com进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

猜你喜欢

• swoole和yaf分别适合用于做什么，各特点是什么

  swoole和yaf的区别：yaf跟swoole这两个框架还是比较典型的，yaf更适合用作后台开发，swoole更适合用作聊天室开发（虽然用php做socket性能不太好）。

• PHP数组有哪些特性，底层实现是怎样的

  PHP 的数组是一种非常强大灵活的数据类型，在讲它的底层实现之前，先看一下 PHP 的数组都具有哪些特性。

• PHP中提高执行效率的简单技巧有哪些

  1、用单引号代替双引号来包含字符串，这样做会更快一些。因为PHP会在双引号包围的字符串中搜寻变量，单引号则不会，注意：只有echo能这么做，它是一种可以把多个字符串当...

• PDO::errorCode的用法是什么，简单实例是怎样的

  今天小编就为大家分享一篇关于PDO::errorCode讲解，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看吧

• laravel日志没有写入有什么原因？怎样处理？

  laravel中日志没有写入的问题如何解决？当我们把项目部署到Linux 服务器上，可能会出现日志没有写入的情况，一些朋友不清楚怎样解决这个问题，对此下面分享一下解决办法供大家参考。