kmeans手寫實現與sklearn接口

kmeans簡介

K 均值聚類是最基礎的一種聚類方法。它是一種迭代求解的聚類分析算法。

kmeans的迭代步驟

1. 給各個簇中心 ${\mu }_1,\dots ,{\mu }_c$ 以適當的初值；

2. 更新樣本 $x_1,\dots ,x_n$ 對應的簇標簽 $y_1,\dots ,y_n$
   yi←argminy∈{1,…,c}∣∣xi?μy∣∣2,i=1,…,ny_i\leftarrow argmin_{y\in \{1,\dots,c\}}||x_i-\mu_y||^2,\ \ \ i=1,\dots,n yi?←argminy∈{1,…,c}?∣∣xi??μy?∣∣2,???i=1,…,n

3. 更新各個簇中心 ${\mu }_1,\dots ,{\mu }_c$
   $${\mu }_y\leftarrow \frac{1}{n_y}\sum _{i:y_i=y}{x}_i,y=1,\dots ,c$$
   其中，$n_y$ 為屬于簇 $y$ 的類別總數

4. 重復上述步驟2, 3，直到簇標簽不再變化（變化足夠小），達到收斂精度為止

優缺點

優點

1. 算法快速、簡單;
2. 對大數據集有較高的效率并且是可伸縮性的;
3. 時間復雜度近于線性，而且適合挖掘大規模數據集。K-Means聚類算法的時間復雜度是O(n×k×t) ,其中n代表數據集中對象的數量，t代表著算法迭代的次數，k代表著簇的數目

缺點

1. 在k-measn算法中K是事先給定的，但是K值的選定是非常難以估計的。
2. 在 K-means 算法中，首先需要根據初始聚類中心來確定一個初始劃分，然后對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果，這也成為 K-means算法的一個主要問題。
3. 當數據量很大時，算法的開銷是非常大的。

kmeans算法的改進

• kmeans++
• 二分Kmeans
  • 分解最大 SSE (誤差平方和)的簇
  • 合并距離最小的簇 或者 合并SSE增幅最小的兩個簇。

手寫實現

偽代碼：

創建 k 個點作為起始質心 (隨機選擇):當任意一個點的簇分配結果發生改變的時候:對數據集中的每個數據點:對每個質心:計算質心與數據點之間的距離將數據點分配到距其最近的簇對每一個簇:求出均值并將其更新為質心

Python實現：

import numpy as npdef kmeans(data, n_clusters, tolerence):n_samples = data.shape[0]sample_asign = np.zeros((n_samples, 2))cluster_centers = data[: n_clusters, :]isChanged = Trueepoch_cnt = 0while isChanged:epoch_cnt += 1isChanged = False# 更新每個樣本點所屬于的類for sample_index in range(n_samples):min_dist = np.infmin_index = 0for cluster_index in range(n_clusters):dist = np.linalg.norm(data[sample_index, :] - cluster_centers[cluster_index, :])if dist < min_dist:min_dist = distmin_index = cluster_indexsample_asign[sample_index, :] = min_dist, min_index# 更新每個聚類中心for cluster_index in range(n_clusters):new_cluster_samples = data[ sample_asign[:, 1] == cluster_index ]new_center = np.mean(new_cluster_samples, axis=0)cluster_center_diff = np.linalg.norm( new_center - cluster_centers[cluster_index, :] )cluster_centers[cluster_index, :] = new_centerif cluster_center_diff > tolerence:isChanged = Trueprint(f"epoch count: {epoch_cnt}")return cluster_centersif __name__ == '__main__':n_samples = 512data_dim = 3n_clusters = 4data = np.random.randn(n_samples, data_dim)tol = 1e-12centers = kmeans(data, n_clusters, tol)print(centers)

sklearn接口

kmeans 手寫實現主要還是為了理解算法，在實際應用中，我們一般調 sklearn 的包就好了。

class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')

類初始化參數

• init：指定初始化聚類中心的方法。可以是 kmeans++ （默認），random 隨機選取，或者是一個形狀為 (n_clusters, n_features) 的數組，直接將該數組作為初始的聚類中心。
• n_init：使用不同質心 (centeroid) 種子運行k -means 算法的次數。最終結果將是 inertia 最佳時的輸出。整型，默認為 10。
• max_iter：kmeans 算法單詞運行的最大迭代數。整型，默認 300。
• tol：關于兩次連續迭代的聚類中心差異的 Frobenius 范數的相對容忍度，小于該值認為收斂。浮點數。
• verbose：是否打印迭代過程中的輸出。整型，默認為 0。
• random_state：決定初始聚類中心的隨機數種子。整型。
• copy_x：在預先計算距離時，首先將數據居中在數值上更準確。 如果 copy_x 為 True（默認），則不修改原始數據。 如果為 False，則修改原始數據，并在函數返回之前放回，但通過減去再添加數據均值可能會引入小的數值差異。 請注意，如果原始數據不是 C 連續的，即使 copy_x 為 False，也會進行復制。 如果原始數據是稀疏的，但不是 CSR 格式，即使 copy_x 為 False，也會進行復制。
• algorithm：要使用的 K-means 算法。 默認是經典的 EM 風格算法 “lloyd”。可選項有：“lloyd”, “elkan”, “auto”, “full”。

類屬性

• cluster_centers_：聚類中心的坐標，是一個形狀為 (n_clusters, n_features) 的數組。如果算法完全收斂，則與 labels_ 一致。
• labels_：每個點的標簽，形狀為 (n_clusters, ) 。
• inertia_：樣本到其最近聚類中心的平方距離總和，如果給了權重的話會計算加權和。浮點數。
• n_features_in_：在運行 fit 方法時見到的特征數，整型、
• feature_names_in_：在運行 fit 方法時見到到的特征名稱。只有當 X 的要素名稱均為字符串時才定義。形狀為 (n_features_in_, ) 的數組。

類方法

函數簽名	說明
fit(X[, y, sample_weight])	計算 kmeans 聚類
fit_predict(X[, y, sample_weight])	計算 kmeans 聚類并預測每個樣本的簇序號
fit_transform(X[, y, sample_weight])	計算 kmeans 聚類并將 X 轉換到聚類距離空間
get_feature_names_out([input_features])	獲取轉換的輸出特征名稱
get_params([deep])	獲取 estimator 的參數
predict(X[, sample_weight])	預測 X 中每個樣本所屬于的簇
score(X[, y, sample_weight])	（看起來是評估模型的準確率）
set_params(**params)	設置 estimator 的參數
transform(X)	將 X 轉換到聚類距離空間

模型保存與加載

需要通過 joblib 來保存，安裝：

pip install joblib

保存/加載模型

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import joblibx, y = make_blobs(n_samples=1000, n_features=4, centers=[[-1, -1], [0, 0], [1, 1], [2, 2]], cluster_std=[0.4, 0.2, 0.2, 0.4], random_state=42)
model = KMeans(n_clusters=6)
model.fit(x, y)
print(model.cluster_centers_)
# 保存模型
joblib.dump(model, 'kmeans_model.pkl')
# 加載模型
model = joblib.load('kmeans_model.pkl')
print(model.cluster_centers_)

Ref

1. 圖解機器學習——杉山將
2. sklearn官方文檔
3. k-means原理與實現