Python實(shí)現(xiàn)聚類K-means算法詳解

更新時(shí)間：2022年07月15日 11:38:23 作者：Castria

這篇文章主要介紹了Python實(shí)現(xiàn)聚類K-means算法詳解，K-means（K均值）算法是最簡(jiǎn)單的一種聚類算法，它期望最小化平方誤差，具體詳解需要的朋友可以參考一下

下面我們用python來(lái)實(shí)現(xiàn)一下K-means算法：我們先嘗試手動(dòng)實(shí)現(xiàn)這個(gè)算法，再用sklearn庫(kù)中的KMeans類來(lái)實(shí)現(xiàn)。數(shù)據(jù)我們采用《機(jī)器學(xué)習(xí)》的西瓜數(shù)據(jù)(P202表9.1):

# 下面的內(nèi)容保存在 melons.txt 中
# 第一列為西瓜的密度；第二列為西瓜的含糖率。我們要把這30個(gè)西瓜分為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

手動(dòng)實(shí)現(xiàn)

我們用到的庫(kù)有matplotlib和numpy，如果沒有需要先用pip安裝一下。

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

下面定義一些數(shù)據(jù)：

k = 3 # 要分的簇?cái)?shù)
rnd = 0 # 輪次，用于控制迭代次數(shù)（見上文）
ROUND_LIMIT = 100 # 輪次的上限
THRESHOLD = 1e-10 # 單輪改變距離的閾值，若改變幅度小于該閾值，算法終止
melons = [] # 西瓜的列表
clusters = [] # 簇的列表，clusters[i]表示第i簇包含的西瓜

從melons.txt讀取數(shù)據(jù)，保存在列表中：

f = open('melons.txt', 'r')
for line in f:
	# 把字符串轉(zhuǎn)化為numpy中的float64類型
    melons.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))

從 m m m個(gè)數(shù)據(jù)中隨機(jī)挑選出 k k k個(gè)，對(duì)應(yīng)上面算法的第 1 1 1行：

# random的sample函數(shù)從列表中隨機(jī)挑選出k個(gè)樣本（不重復(fù)）。我們?cè)谶@里把這些樣本作為均值向量
mean_vectors = random.sample(melons, k)

下面是算法的主要部分。

# 這個(gè)while對(duì)應(yīng)上面算法的2-17行
while True:
    rnd += 1 # 輪次增加
    change = 0 # 把改變幅度重置為0

	# 清空對(duì)簇的劃分，對(duì)應(yīng)上面算法的第3行
    clusters = []
    for i in range(k):
        clusters.append([])
    # 這個(gè)for對(duì)應(yīng)上面算法的4-8行
    for melon in melons:
    	'''
    	argmin 函數(shù)找出容器中最小的下標(biāo)，在這里這個(gè)目標(biāo)容器是
    	list(map(lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors)),
    	它表示melon與mean_vectors中所有向量的距離列表。
    	(numpy.linalg.norm計(jì)算向量的范數(shù),ord = 2即歐幾里得范數(shù)，或模長(zhǎng))
    	'''
        c = np.argmin(
            list(map( lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors))
        )
        clusters[c].append(melon)
	# 這個(gè)for對(duì)應(yīng)上面算法的9-16行
    for i in range(k):
    	# 求每個(gè)簇的新均值向量
        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
	# 若超過(guò)設(shè)定的輪次或者變化幅度<預(yù)先設(shè)定的閾值，結(jié)束算法
    if rnd > ROUND_LIMIT or change < THRESHOLD:
        break
print('最終迭代%d輪'%rnd)

最后我們繪圖來(lái)觀察一下劃分的結(jié)果：

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

# 每個(gè)簇?fù)Q一下顏色，同時(shí)迭代簇和顏色兩個(gè)列表
for i, col in zip(range(k), colors):
    for melon in clusters[i]:
    	# 繪制散點(diǎn)圖
        plt.scatter(melon[0], melon[1], color = col)
plt.show()

劃分結(jié)果（由于最開始的 k k k個(gè)均值向量隨機(jī)選取，每次劃分的結(jié)果可能會(huì)不同）:

完整代碼：

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庫(kù)中的KMeans

這種經(jīng)典算法顯然不需要我們反復(fù)地造輪子，被廣泛使用的python機(jī)器學(xué)習(xí)庫(kù)sklearn已經(jīng)提供了該算法的實(shí)現(xiàn)。sklearn的官方文檔中給了我們一個(gè)示例：

>>> 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即要聚類的數(shù)據(jù)(1,2),(1,4),(1,0)等。
KMeans類的初始化參數(shù)n_clusters即簇?cái)?shù) k k k;
random_state是用于初始化選取 k k k個(gè)向量的隨機(jī)數(shù)種子;
kmeans.labels_即每個(gè)點(diǎn)所屬的簇；
kmeans.predict方法預(yù)測(cè)新的數(shù)據(jù)屬于哪個(gè)簇;
kmeans.cluster_centers_返回每個(gè)簇的中心。
我們就改造一下這個(gè)簡(jiǎn)單的示例，完成對(duì)上面西瓜的聚類。

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()

運(yùn)行結(jié)果如下，可以看到和我們手寫的聚類結(jié)果基本一致：