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进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

猜你喜欢

• PHP中return和exit的作用和用法是什么，有何差异

  先说一下exit函数的用法。 作用：输出一则消息并且终止当前脚本。 如果一段文本中包括多个以结束的脚本，则exit退出当前所在脚本。 比如一篇php文本包括一下代码,则输出为world。 <% echo"hello"; exit; ?> echo"world"; ?> 语法格式：void表示没有返回值。 voidexit([string$status]) vo

• 基于Laravel如何制作rbac权限管理功能，方法是怎样

  这篇文章主要介绍了Laravel框架实现的rbac权限管理操作,结合实例形式分析了Laravel框架权限控制rbac相关数据库创建、读写及权限判断等操作技巧,需要的朋友可以参考下

• laravel关闭csrf验证的做法是什么，有哪些方法

  方法：1、打开app下的“Kernel.php”文件，找到并注释掉“App\Http\Middleware\VerifyCsrfToken”代码。2、打开app下的“VerifyCsrfToken.PHP”文件，修改“$except”属性。

• laravel框架的故障问题如何解决？

  laravel框架是PHP中比较常用的框架，有很多新手在学习PHP时会遇到一些laravel框架相关的故障问题不知道怎么样解决，下面小编就给大家介绍一下常见的故障问题以及解决办法。

• laravel门面的定义和优点是什么，怎样使用

  在laravel中，门面Facades用于为应用的IoC服务容器的类提供了一个静态的接口，Laravel的门面作为服务容器中底层类的静态代理，相比于传统静态方法，在维护时能够提供更加易于测试的语法。