人工智慧–K-Means演算法

人工智慧之K-Means演算法

前言：人工智慧機器學習有關演算法內容，請參見公眾號「科技優化生活」之前相關文章。人工智慧之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下K-Means演算法。^_^

K-Means是十大經典數據挖掘演算法之一。K-Means和KNN(K鄰近)看上去都是K打頭，但卻是不同種類的演算法。kNN是監督學習中的分類演算法，而K-Means則是非監督學習中的聚類演算法；二者相同之處是均利用近鄰信息來標註類別。

提到「聚類」一詞，使人不禁想到：「物以類聚，人以群分」。聚類是數據挖掘中一種非常重要的學習流派，指將未標註的樣本數據中相似的分為同一類。

K-means演算法是很典型的基於距離的聚類演算法。於1982年由Lloyod提出。它是簡單而又有效的統計聚類演算法。一般採用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該演算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。

K-Means概念：

K-means演算法是硬聚類演算法，是典型的基於原型的目標函數聚類方法的代表，它是數據點到原型的某種距離作為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則。K-means演算法以歐式距離作為相似度測度，它是求對應某一初始聚類中心向量V最優分類，使得評價指標J最小。演算法採用誤差平方和準則函數作為聚類準則函數。

K-Means核心思想：

由用戶指定k個初始質心（initial centroids)，作為聚類的類別（cluster），重複迭代直至演算法收斂。即以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

k個初始類聚類中心點的選取對聚類結果具有較大的。

K-Means演算法描述：

假設要把樣本集分為c個類別，演算法描述如下：

1）適當選擇c個類的初始中心；

2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；

3）利用均值等方法更新該類的中心值；

4）對於所有的c個聚類中心，如果利用2）和3）的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。

具體如下：

輸入：k, data[n];

1）選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1]；

2）對於data[0]….data[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；

3）對於所有標記為i點，重新計算c[i]={所有標記為i的data[j]之和}/標記為i的個數；

4）重複2)和3)，直到所有c[i]值的變化小於給定閾值。

該演算法的最大優勢在於簡潔和快速。演算法的關鍵在於初始中心的選擇和距離公式。

K-Means工作流程：

1）從n個數據對象任意選擇k個對象作為初始聚類中心；

2）根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；並根據最小距離重新對相應對象進行劃分；

3）重新計算每個（有變化）聚類的均值（中心對象）；

4）循環2）到3）直到每個聚類不再發生變化為止，即標準測度函數收斂為止。

註：一般採用均方差作為標準測度函數。

K-Means演算法接受輸入量k；然後將n個數據對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。即，各聚類本身儘可能的緊湊，而各聚類之間儘可能的分開。

聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

K-Means優點：

1）演算法快速、簡單；

2）對大數據集有較高效率並且是可伸縮性的；

3）確定的K個劃分達到平方誤差最小；

4）時間複雜度近於線性，而且適合挖掘大規模數據集。K-Means聚類演算法的時間複雜度是O(nkt) ,其中n代表數據集中對象的數量，t代表著演算法迭代的次數，k代表著簇的數目，且k

K-Means缺點：

1）在K-means演算法中K是事先給定的，這個K值的選定是非常難以估計的；

2）在K-means演算法中，初始聚類中心的選擇對聚類結果有較大影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果；

3）從K-means演算法框架可以看出，該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新聚類中心，因此當數據量非常大時，演算法時間開銷非常大。

K-Means演算法改進:

1）針對K值選定難以估計問題，通過類的自動合併和分裂，得到較為合理的類型數目K，例如，ISODATA演算法。

2）針對初始值選擇不好無法得到有效聚類結果問題，可採用遺傳演算法GA（參見人工智慧（28））進行初始化，以內部聚類準則作為評價指標。

3）針對演算法時間開銷大問題，採用對樣本數據進行聚類，無論是初始點的選擇還是一次迭代完成時對數據的調整，都是建立在隨機選取樣本數據的基礎上，這樣可以提高演算法的收斂速度。

K-Means應用場景：

K-means演算法具有快速、簡單，對大數據集有較高效率和可伸縮性等優點，是最為經典，也是使用最為廣泛的聚類演算法。K-means演算法在機器學習、知識發現和數據挖掘等領域得到廣泛應用。

結語:

K-Means是聚類演算法中最為簡單、高效且易於理解。K-Means演算法採用誤差平方和準則函數作為聚類準則函數。K-Means演算法有其缺點，但大多缺點都可以克服，最大的優點就是演算法複雜度低，可以在短時間內處理海量數據，這對於當今數據爆炸時代非常重要！K-Means演算法在世界上廣為流傳，得到極大的關注。K-Means演算法在機器學習、知識發現和數據挖掘等領域得到廣泛應用。通過研究K-means演算法，可以發現：一個真正偉大的演算法不是因為它有多麼複雜，而是它能夠用最簡單的原理解決最複雜的問題！

------以往文章推薦------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！