好久之前寫過K-Means, 但寫的極其丑陋，使用的時候還得用 sklearn.cluster.KMeans 包來干。最近需要手撕k-Means，自己也受不了多重for 循環(huán)這么disgusting的方式。sklearn.cluster.KMeans等包加入了相當多細節(jié)優(yōu)化和向量化計算，同時也想能否用 numpy 來原生實現(xiàn)更高效的加速。在網(wǎng)上找了半天，終于看到這篇簡潔又高效的numpy實現(xiàn)了。

Clustering and NumPy?ixora.io

K-Means原理很簡單。按照西瓜書的定義，就是在給定樣本集

?，找出簇中心?來最小化平方誤差：

說人話就是找到?

個類中心，讓所有樣本被分在簇內的話樣本相似度越高。但是這是個NP難問題，通常使用迭代優(yōu)化來近似尋找?個類中心，也就是只要誤差在可接受范圍內就認為找到了所有樣本到類中心的最小化誤差。

這里我們首先隨機或者基于某種策略生成?

個簇中心，然后計算所有數(shù)據(jù)與 ? 個簇中心的距離，將數(shù)據(jù)根據(jù)與其相鄰最近的簇中心分配為某個聚類，之后再次根據(jù)新的劃分計算簇中心... 這樣周而復始直到簇中心不再變化或者計算超出預期輪次，流程圖如下：

原理上較為簡單，一般都可以簡單實現(xiàn)。這里分析一下優(yōu)化的點，計算所有樣本與簇中心的時候，往往會使用 多重for循環(huán) 來遍歷所有樣本，并重新計算類中心。實際上 numpy 提供了廣播機制(broadcasting)來進行高效矩陣計算，這在各個小型神經(jīng)網(wǎng)絡與計算圖框架中均使用到了（MyGrad, micrograd, tinygrad），一直沒有深入底層研究過。結合其他博主的文章來先看一看：

司南牧：2個規(guī)則弄懂numpy的broadcast廣播機制?zhuanlan.zhihu.com

這篇博客

Clustering and NumPy?ixora.io

就利用 broadcasting 來進行的計算，實現(xiàn)上非常高效，我們對關鍵部分進行解析：

import numpy as np def kmeans(data, k=3, normalize=False, limit=500):# normalize 數(shù)據(jù)if normalize:stats = (data.mean(axis=0), data.std(axis=0))data = (data - stats[0]) / stats[1]# 直接將前K個數(shù)據(jù)當成簇中心centers = data[:k]for i in range(limit):# 首先利用廣播機制計算每個樣本到簇中心的距離，之后根據(jù)最小距離重新歸類classifications = np.argmin(((data[:, :, None] - centers.T[None, :, :])**2).sum(axis=1), axis=1)# 對每個新的簇計算簇中心new_centers = np.array([data[classifications == j, :].mean(axis=0) for j in range(k)])# 簇中心不再移動的話，結束循環(huán)if (new_centers == centers).all():breakelse:centers = new_centerselse:# 如果在for循環(huán)里正常結束，下面不會執(zhí)行raise RuntimeError(f"Clustering algorithm did not complete within {limit} iterations")# 如果normalize了數(shù)據(jù)，簇中心會反向 scaled 到原來大小if normalize:centers = centers * stats[1] + stats[0]return classifications, centers

接下來就是產(chǎn)生一些隨機數(shù)來測試一下吧

data = np.random.rand(200, 2) classifications, centers = kmeans(data, k=5)

將聚類的結果可視化出來，每個類分別上不同的色，其中每個簇中心用黑色三角表示：

from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt%matplotlib inlineplt.figure(figsize=(12, 8)) plt.scatter(x=data[:, 0], y=data[:, 1], s=100, c=classifications) plt.scatter(x=centers[:, 0], y=centers[:, 1], s=500, c='k', marker='^'); # 16輪迭代結束

k-means算法對每個數(shù)據(jù)維數(shù)的相對尺度很敏感。如果某個維度是更大，距離函數(shù)會在該維度的計算權重會更大一些。直觀一些，當我們將數(shù)據(jù)第一維擴大10倍后，觀察一下：

data = np.random.rand(200, 2) data[:, 0] *= 10 # 第一維擴大10倍classifications, centers = kmeans(data, k=5)plt.figure(figsize=(12, 8)) plt.scatter(x=data[:, 0], y=data[:, 1], s=100, c=classifications) plt.scatter(x=centers[:, 0], y=centers[:, 1], s=500, c='k', marker='^'); # 13輪迭代結束

數(shù)據(jù)在垂直方向分成了5類，很顯然因為x軸的權重大于y軸（第1維度擴大了10倍）。使用歸一化參數(shù)對數(shù)據(jù)進行歸一化，可以得到更好的結果，我們可視化一下：

classifications, centers = kmeans(data, normalize=True, k=5)plt.figure(figsize=(12, 8)) plt.scatter(x=data[:, 0], y=data[:, 1], s=100, c=classifications) plt.scatter(x=centers[:, 0], y=centers[:, 1], s=500, c='k', marker='^'); # 9輪迭代結束

該算法還可以對2維以上數(shù)據(jù)進行聚類，下面進行3維聚類：

data = np.random.rand(200, 3)classifications, centers = kmeans(data, normalize=True, k=5)fig = plt.figure(figsize=(12, 8)) ax = fig.add_subplot(111, projection='3d')ax.scatter(data[:, 0], data[:, 1], data[:, 2], c=classifications, s=100) ax.scatter(centers[:, 0], centers[:, 1], centers[:, 2], s=500, c='k', marker='^'); # 8輪迭代

總結

以上是生活随笔為你收集整理的numpy归一化_使用numpy 高效实现K-Means聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。