<style></style> <style></style> <style></style> <style></style>
注：本系列所有博客將持續更新并發布在github和gitee上，您可以通過github、gitee下載本系列所有文章筆記檔案，
1 聚類¶
本文我們來總結K-means演算法，
與之前介紹過的諸多分類演算法不同，K-means演算法屬于聚類演算法的范疇，說到這里，必須得所以說分類演算法與聚類演算法的區別，
分類演算法與聚類演算法最本質的區別在于分類演算法是一種有監督學習方法，這一類演算法在真正用于實踐前，必須通過已知樣本標簽的資料進行訓練，以建立樣本特征屬性到樣本標簽的最佳擬合模型；與之相反，無監督學習方法可以在沒有任何先驗知識的情況下進行分類，這種方法根據相似性原則，將具有較高相似度的資料物件劃分至同一類簇，將具有較高相異度的資料物件劃分至不同類簇，最終實作對資料集的分類，
2 K-means演算法¶
2.1 演算法思想¶
K-means演算法是一種基于距離的聚類演算法，這類聚類演算法以距離來度量物件間的相似性，兩樣本物件間距離越大，相似性越小，關于K-means演算法，有一個非常經典的故事：
有4個牧師去郊區村莊授課，剛開始，4個牧師在村莊里分別隨機選了一個位置，然后將位置公布給全村村民，村民收到訊息后，紛紛選擇最近的一個牧師那里去聽課，牧師授課時，眾多村民反饋路途太遠，于是牧師記錄了來聽自己授課的所有村民的居住地址，第二次授課時，牧師選擇自己記錄的村民的中心位置作為新的授課位置，然后將位置公布給全村村民，村民收到4位牧師新的授課位置后，同樣根據距離選擇最近的牧師去聽課，之后4位牧師的每次一次授課都根據來聽自己講課的村民登記的居住地址來更新下一次授課的位置，而村民也更新4位牧師更新的位置來選擇授課牧師，直到村民的選擇不再發生變化，則牧師授課的位置也徹底穩定下來，
K-means演算法思想與上面故事中牧師選位所表現出來的原理是十分相似的，最終的目的都是實作所有樣本資料（村民）到聚類中心（牧師）的距離之和最小化，K-means演算法實作步驟如下：
輸入：資料集$D = \{ {x_1},{x_2}, \cdots ,{x_n}\} $，聚類個數$k$
輸出：聚類結果類簇
（1）隨機初始化$k$個樣本作為聚類中心$\{ {\mu _1},{\mu _2}, \cdots ,{\mu_k}\} $；
（2）計算資料集中所有樣本$x_i$到各個聚類中心$\mu_j$的距離$dist({x_i},{\mu _j})$，并將$x_i$劃分到距離最小的聚類中心所在類簇中；
（3）對于每一個類簇，更新其聚類中心：${\mu _i} = \frac{1}{{|{c_i}|}}\sum\limits_{x \in {c_i}} x $
（4）重復（2）（3）步驟，直到聚類中心不再有明顯變化或滿足迭代次數，
總結而言，K-means演算法整個流程可總結為一個優化問題，通過不斷迭代使得目標函式收斂，K-means演算法目標函式為： $$J = \sum\nolimits_{j = 1}^k {\sum\nolimits_{i = 1}^n {dist({x_i},{\mu _j})} } $$
從目標函式中可以看出，有兩個因素對聚類結果有著至關重要的影響：$k$值、距離度量方式，
對于$k$值，這是K-means演算法一個繞不開的問題，直接影響著最終聚類結果的準確性，在如何確定$k$值問題上，傳統的的K-means演算法在對資料分布未知的情況下只能通過多次嘗試不同的$k$值來探索最優取值，值得一說的是，眾多專家學者針對K-means演算法中如何確定$k$值、甚至避開$k$值的的問題對K-means演算法進行優化改進，設計了許多改進的K-means演算法，這又是一個大話題了，本文不在深究，
下面在說說距離度量的問題，
2.2 距離度量¶
對于K-means演算法這類基于距離（其他還有基于密度、網格、層次、模型）的聚類演算法，距離度量貫穿了演算法的整個流程，所以選擇一種合適的距離度量方式尤為重要，
這里列舉幾種常見的距離度量方式，
（1）閔可夫斯基距離（Minkowski Distance） 對于兩個給定的$d$維資料樣本$X = ({x_1},{x_2}, \cdots ,{x_p})$，$Y = ({y_1},{y_2}, \cdots ,{y_p})$，閔可夫斯基距離定義為： $$dist(X,Y) = \root p \of {\sum\limits_{i = 1}^d {|{x_i} - {y_i}{|^p}} } $$
當$p=1$時，閔可夫斯基距離又被稱為曼哈頓距離(Manhattan Distance)： $$dist(X,Y) = \sum\limits_{i = 1}^d {|{x_i} - {y_i}|} $$ 曼哈頓距離可以看做是資料樣本在各維度差值的絕對值之和，又被稱為折線距離、街區距離，相比于歐氏距離，曼哈頓距離沒進行平方運算，所以對離群點不敏感，
當$p=2$時，閔可夫斯基距離就是我們熟悉的歐氏距離： $$dist(X,Y) = \sqrt {\sum\limits_{i = 1}^d {|{x_i} - {y_i}{|^2}} } $$
（2）余弦距離（Cosine）
余弦距離以兩向量夾角余弦值來反映相似度，取值在$[0,1]$之間，值越大，相似度越大，
$$dist(X,Y) = \cos (X,Y) = \frac{{\sum\nolimits_{i = 1}^d {{x_i}{y_i}} }}{{\sqrt {\sum\nolimits_{i = 1}^d {{{({x_i})}^2}} } \sqrt {\sum\nolimits_{i = 1}^d {{{({y_i})}^2}} } }}$$
余弦距離在文本識別中應用比較普遍，
（3）切比雪夫距離 (Chebyshev Distance )
切比雪夫距離是以各維度差值的最大值作為最終的相似度： $$dist(X,Y) = \mathop {\max }\limits_i (|{x_i} - {y_i}|)$$
除了這三個常用距離外，還有馬氏距離、皮爾遜相關系數、KL散度等等距離度量方法，
2.3 演算法總結¶
K-means演算法是一個應用十分廣泛、出場率極高的一個聚類演算法，思想簡單，解釋性強，設定好$k$值后即可輸出指定數量的類簇，不過，在實際應用中，也需要注意K-means演算法的不足之處：
- K-means演算法的$k$值必須在聚類前確定，在缺乏對資料集分布認知的情況下這往往是很難估計的，只能通過多次的嘗試探索最佳的$k$值，
- K-means演算法第一次迭代時的$k$個聚類中心對演算法最終結果有很大影響，但在K-means演算法中，第一次迭代的$k$各聚類中心是隨機選定的，這給演算法聚類結果帶來了不確定性，
- K-means演算法對非球狀分布的資料集上表現不佳，K-means演算法這類基于距離的聚類演算法基本假設是同一類簇內部物件間距離遠小于不同類簇間物件距離，這種假設相當于將類簇看作是一個球狀，所以對非球狀分布的資料集，K-means演算法表現可能并不佳，
- K-means演算法在不斷迭代程序中使得演算法逐漸優化，在每一次迭代中，都必須計算每一個物件與聚類中心的距離，所以當資料量非常大時，時間開銷比較大，
天下沒有免費的誤差，也沒有適合所有場景的演算法，想要享受演算法有點，就必須承受演算法的不足，根據實際應用選擇合適的演算法才是最佳選擇，
3 python實作K-means演算法¶
In [1]:import numpy as np import matplotlib.pyplot as plt import copy
先創建一個包含3個類簇的資料集：
In [2]:a = np.random.normal(20,5,300) b = np.random.normal(15,5,300) cluster1 = np.array([[x, y] for x, y in zip(a,b)])In [3]:
a = np.random.normal(20,5,300) b = np.random.normal(45,5,300) cluster2 = np.array([[x, y] for x, y in zip(a,b)])In [4]:
a = np.random.normal(55,5,300) b = np.random.normal(30,5,300) cluster3 = np.array([[x, y] for x, y in zip(a,b)])In [5]:
dataset = np.append(np.append(cluster1,cluster2, axis=0),cluster3, axis=0)
展示一下剛創建的資料集：
In [6]:for i in dataset: plt.scatter(i[0], i[1],c='black',s=6) plt.show()
定義一個方法用于計算歐氏距離：
In [7]:def calc_dist(simple1, simple2): """計算兩資料物件間的歐氏距離""" return np.linalg.norm(simple1-simple2)
定義一個方法用于演算法第一次迭代時隨機出世后聚類中心：
In [8]:def init_centers(k, dataset): """隨機獲取k個初始化聚類中心""" shuffle_array = np.arange(dataset.shape[0]) np.random.shuffle(shuffle_array) center_index = shuffle_array[:k] # 獲取k個隨機索引 center_dict = {} for i in range(k): center = dataset[center_index[i]] # 聚類中心 center_dict[i] = center return center_dictIn [9]:
def k_means(k,dataset): """實作K-means演算法""" ds = copy.deepcopy(dataset) # 復制一份資料 epoch = 0 # 迭代次數 center_dict = init_centers(k, ds) # 第一次迭代時，隨機初始化k個聚類中心 ds = np.insert(ds, 2, values=-1, axis=1) # 插入一列作為類標簽，默認為0 total_last = np.inf # 上一次迭代距離總和 while epoch<=20: # 迭代次數少于20次時繼續迭代，也可以直接設為True，當目標函式收斂時自動結束迭代 cluster_dist = {i:0 for i in range(k)} # 記錄每一個類簇距離總和 for simple in ds: min_dist = np.inf # simple 到最近的聚類中心的距離 min_label = -1 # 最近的聚類中心類標簽 for label in center_dict.keys(): dist = calc_dist(simple[:2], center_dict[label]) if dist < min_dist: min_dist = dist min_label = label simple[2] = min_label # 將當前樣本點劃分到最近的聚類中心所在聚類中 cluster_dist[int(min_label)] = cluster_dist[int(min_label)] + min_dist # 更新類簇內部距離總和 loss_now = sum(cluster_dist.values()) # 所有類簇內部距離總和 print("epoch:{}, tatal distance: {}".format(epoch,loss_now)) for i in ds: if i[2] == 0: plt.scatter(i[0], i[1],c='red',s=6) elif i[2] == 1: plt.scatter(i[0], i[1],c='green',s=6) else: plt.scatter(i[0], i[1],c='blue',s=6) for center in center_dict.values(): plt.scatter(center[0], center[1],c='black') plt.show() if total_last == loss_now: # 如果兩次迭代距離總和都不變，證明已收斂 break total_last = loss_now for label in center_dict.keys(): # 更新聚類中心 simple_list = ds[ds[:,2]==label] # 挑選出類標簽為k的所有樣本 x = np.mean(simple_list[:, 0]) y = np.mean(simple_list[:, 1]) center_dict[label] = [x, y] epoch += 1 return ds, center_dictIn [12]:
ds,cluster_label = k_means(3,dataset)
epoch:0, tatal distance: 12934.408559284844
epoch:1, tatal distance: 7964.838789624616
epoch:2, tatal distance: 5778.574439702343
epoch:3, tatal distance: 5628.049794639323
epoch:4, tatal distance: 5628.049794639323
好了，K-means演算法就算實作好了，從上多幅圖中可以看到每一次迭代聚類中心是如何變化的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63754.html
標籤：其他
上一篇：記錄一下：could not create cublas handle: CUBLAS_STATUS_ALLOC_FAILED解決辦法