kmeans演算法要實現什麼

⑴ kmeans聚類演算法是什麼

kmeans聚類演算法是將樣本聚類成k個簇（cluster）。

K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。在實際K-Mean演算法中，我們一般會多次運行圖c和圖d，才能達到最終的比較優的類別。

用數據表達式表示

假設簇劃分為$(C_1,C_2,...C_k)$，則我們的目標是最小化平方誤差E：$$ E = sumlimits_{i=1}^ksumlimits_{x in C_i} ||x-mu_i||_2^2$$。

其中$mu_i$是簇$C_i$的均值向量，有時也稱為質心，表達式為：$$mu_i = frac{1}{|C_i|}sumlimits_{x in C_i}x$$。

⑵ Kmeans聚類演算法簡介（有點枯燥）

1. Kmeans聚類演算法簡介

由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。

Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：

μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。

2. K值的確定

2.1 根據問題內容確定

這種方法就不多講了，文章開篇就舉了一個例子。

2.2 肘部法則

如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：

從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。

2.3 與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。

2.4 穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。

2.5 系統演化方法

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。

2.6 使用canopy演算法進行初始劃分

基於Canopy Method的聚類演算法將聚類過程分為兩個階段

(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；

(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。

其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。

3. 初始質心的選取

選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。

第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy演算法。

4. 距離的度量

常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。

藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。

因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。

5. 聚類效果評估

我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：

aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。

6. Kmeans演算法流程

輸入：聚類個數k，數據集XmxnXmxn。 

輸出：滿足方差最小標準的k個聚類。

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

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

(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；

(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。

Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。

7. Kmeans演算法優缺點

7.1 優點

(1). 演算法原理簡單。需要調節的超參數就是一個k。

(2). 由具有出色的速度和良好的可擴展性。

7.2 缺點

(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。

(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。

(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。

(4). 對離群點很敏感。

(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。

(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。

(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。

(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。

針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。

Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。

⑶ Kmeans演算法原理

Kmeans是一種無監督的基於距離的聚類演算法，其變種還有Kmeans++。

注意，某些聚類中心可能沒有被分配到樣本，這樣的聚類中心就會被淘汰（意味著最終的類數可能會減少）

和其他機器學習演算法一樣，K-Means 也要評估並且最小化聚類代價，在引入 K-Means 的代價函數之前，先引入如下定義：

引入代價函數：

5） 對噪音和異常點比較的敏感。

數據呈圓形、凸型、在一起的簇的數據形狀近似高斯分布的這些數據是kmeans喜歡的數據。

⑷ k-means聚類演算法的實現和可視化

k-means是一個非監督演算法，以前我們學的都是監督演算法或者半監督演算法，例如多元回歸，貝葉斯判別，支持向量機，隨機森林演算法等。而這種距離演算法則是非監督演算法。

PS：常見的聚類方法有：系統聚類法，k均值聚類法
系統聚類法是計算所有數據之間的距離，根據不同的分類數，迭代，直到全部不能分為止，意思是你想要多少類都能分給你。

聚類演算法根據數據之間的相似性或者距離將數據分為幾個簇，簇與簇之間不同。

在這個演算法中，我們需要提前指定數據可能分成的堆數，每個數據對象在不同的堆里都不同。

兩個距離：（距離體現了他們之間的差異性）
個體與個體之間的距離
類與類之間的距離
距離的計算種類：馬氏距離，歐氏距離，明氏距離等

每一個簇都有聚類中心，根據數據到聚類中心的距離，把它歸為哪一類。

工具：python3.6 sklearn iris

結果不太理想，因為我用的是鳶尾花的數據，該數據適合用來做判別分析。
sklearn里還有很多好用的功能，這倒是一個新發現。

⑸ k means演算法如何具體實現呢

1.基本Kmeans演算法[1]

[cpp] view plain
選擇K個點作為初始質心
repeat
將每個點指派到最近的質心，形成K個簇
重新計算每個簇的質心
until 簇不發生變化或達到最大迭代次數

時間復雜度：O(tKmn)，其中，t為迭代次數，K為簇的數目，m為記錄數，n為維數

空間復雜度：O((m+K)n)，其中，K為簇的數目，m為記錄數，n為維數

⑹ kmeans演算法是什麼

K-means演算法是一種基於距離的聚類演算法，也叫做K均值或K平均，也經常被稱為勞埃德(Lloyd)演算法。是通過迭代的方式將數據集中的各個點劃分到距離它最近的簇內，距離指的是數據點到簇中心的距離。

K-means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本劃分為K個簇。將簇內的數據盡量緊密的連在一起，而讓簇間的距離盡量的大。

演算法流程

1、選取數據空間中的K個對象作為初始中心，每個對象代表一個聚類中心。

2、對於樣本中的數據對象，根據它們與這些聚類中心的歐氏距離，按距離最近的准則將它們分到距離它們最近的聚類中心（最相似）所對應的類。

3、更新聚類中心：將每個類別中所有對象所對應的均值作為該類別的聚類中心，計算目標函數的值。

4、判斷聚類中心和目標函數的值是否發生改變，若不變，則輸出結果，若改變，則返回2）。

⑺ 聚類演算法之K均值演算法(k-means)的Python實現

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

通常，人們根據樣本間的某種距離或者相似性來定義聚類，即把相似的（或距離近的）樣本聚為同一類，而把不相似的（或距離遠的）樣本歸在其他類。

所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種演算法將D劃分成k個子集，要求每個子集內部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。

k-means演算法是一種很常見的聚類演算法，它的基本思想是：通過迭代尋找k個聚類的一種劃分方案，使得用這k個聚類的均值來代表相應各類樣本時所得的總體誤差最小。

看起來還不錯

分析一個公司的客戶分類，這樣可以對不同的客戶使用不同的商業策略，或是電子商務中分析商品相似度，歸類商品，從而可以使用一些不同的銷售策略，等等。

⑻ kmeans聚類演算法是什麼

K-means演算法是最為經典的基於劃分的聚類方法，是十大經典數據挖掘演算法之一。K-means演算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

聚類屬於無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特徵x，比如假設宇宙中的星星可以表示成三維空間中的點集。

(8)kmeans演算法要實現什麼擴展閱讀：

k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

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

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

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

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

⑼ kmeans演算法用Python怎麼實現

1、從Kmeans說起

Kmeans是一個非常基礎的聚類演算法，使用了迭代的思想，關於其原理這里不說了。下面說一下如何在matlab中使用kmeans演算法。

創建7個二維的數據點：

復制代碼 代碼如下:
x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];

使用kmeans函數：

復制代碼 代碼如下:
class = kmeans(x, 2);

x是數據點，x的每一行代表一個數據；2指定要有2個中心點，也就是聚類結果要有2個簇。 class將是一個具有70個元素的列向量，這些元素依次對應70個數據點，元素值代表著其對應的數據點所處的分類號。某次運行後，class的值是：

復制代碼 代碼如下:

2
2
2
1
1
1
1

這說明x的前三個數據點屬於簇2，而後四個數據點屬於簇1。 kmeans函數也可以像下面這樣使用：

復制代碼 代碼如下:

>> [class, C, sumd, D] = kmeans(x, 2)
class =
2
2
2
1
1
1
1

C =
4.0629 4.0845
-0.1341 0.1201

sumd =
1.2017
0.2939

D =
34.3727 0.0184
29.5644 0.1858
36.3511 0.0898
0.1247 37.4801
0.7537 24.0659
0.1979 36.7666
0.1256 36.2149

class依舊代表著每個數據點的分類;C包含最終的中心點，一行代表一個中心點；sumd代表著每個中心點與所屬簇內各個數據點的距離之和；D的
每一行也對應一個數據點，行中的數值依次是該數據點與各個中心點之間的距離，Kmeans默認使用的距離是歐幾里得距離（參考資料[3]）的平方值。
kmeans函數使用的距離，也可以是曼哈頓距離（L1-距離），以及其他類型的距離，可以通過添加參數指定。

kmeans有幾個缺點（這在很多資料上都有說明）：

1、最終簇的類別數目（即中心點或者說種子點的數目）k並不一定能事先知道，所以如何選一個合適的k的值是一個問題。
2、最開始的種子點的選擇的好壞會影響到聚類結果。
3、對雜訊和離群點敏感。
4、等等。

2、kmeans++演算法的基本思路

kmeans++演算法的主要工作體現在種子點的選擇上，基本原則是使得各個種子點之間的距離盡可能的大，但是又得排除雜訊的影響。 以下為基本思路：

1、從輸入的數據點集合（要求有k個聚類）中隨機選擇一個點作為第一個聚類中心
2、對於數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)
3、選擇一個新的數據點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的概率較大
4、重復2和3直到k個聚類中心被選出來
5、利用這k個初始的聚類中心來運行標準的k-means演算法

假定數據點集合X有n個數據點，依次用X(1)、X(2)、……、X(n)表示，那麼，在第2步中依次計算每個數據點與最近的種子點（聚類中心）的
距離，依次得到D(1)、D(2)、……、D(n)構成的集合D。在D中，為了避免雜訊，不能直接選取值最大的元素，應該選擇值較大的元素，然後將其對應
的數據點作為種子點。

如何選擇值較大的元素呢，下面是一種思路（暫未找到最初的來源，在資料[2]等地方均有提及，筆者換了一種讓自己更好理解的說法）：
把集合D中的每個元素D(x)想像為一根線L(x)，線的長度就是元素的值。將這些線依次按照L(1)、L(2)、……、L(n)的順序連接起來，組成長
線L。L(1)、L(2)、……、L(n)稱為L的子線。根據概率的相關知識，如果我們在L上隨機選擇一個點，那麼這個點所在的子線很有可能是比較長的子
線，而這個子線對應的數據點就可以作為種子點。下文中kmeans++的兩種實現均是這個原理。

3、python版本的kmeans++

在http://rosettacode.org/wiki/K-means%2B%2B_clustering 中能找到多種編程語言版本的Kmeans++實現。下面的內容是基於python的實現（中文注釋是筆者添加的）：

復制代碼 代碼如下:

from math import pi, sin, cos
from collections import namedtuple
from random import random, choice
from import
try:
import psyco
psyco.full()
except ImportError:
pass

FLOAT_MAX = 1e100

class Point:
__slots__ = ["x", "y", "group"]
def __init__(self, x=0.0, y=0.0, group=0):
self.x, self.y, self.group = x, y, group

def generate_points(npoints, radius):
points = [Point() for _ in xrange(npoints)]

# note: this is not a uniform 2-d distribution
for p in points:
r = random() * radius
ang = random() * 2 * pi
p.x = r * cos(ang)
p.y = r * sin(ang)

return points

def nearest_cluster_center(point, cluster_centers):
"""Distance and index of the closest cluster center"""
def sqr_distance_2D(a, b):
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2

min_index = point.group
min_dist = FLOAT_MAX

for i, cc in enumerate(cluster_centers):
d = sqr_distance_2D(cc, point)
if min_dist > d:
min_dist = d
min_index = i

return (min_index, min_dist)

'''
points是數據點，nclusters是給定的簇類數目
cluster_centers包含初始化的nclusters個中心點，開始都是對象->(0,0,0)
'''

def kpp(points, cluster_centers):
cluster_centers[0] = (choice(points)) #隨機選取第一個中心點
d = [0.0 for _ in xrange(len(points))] #列表，長度為len(points)，保存每個點離最近的中心點的距離

for i in xrange(1, len(cluster_centers)): # i=1...len(c_c)-1
sum = 0
for j, p in enumerate(points):
d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j個數據點p與各個中心點距離的最小值
sum += d[j]

sum *= random()

for j, di in enumerate(d):
sum -= di
if sum > 0:
continue
cluster_centers[i] = (points[j])
break

for p in points:
p.group = nearest_cluster_center(p, cluster_centers)[0]

'''
points是數據點，nclusters是給定的簇類數目
'''
def lloyd(points, nclusters):
cluster_centers = [Point() for _ in xrange(nclusters)] #根據指定的中心點個數，初始化中心點，均為(0,0,0)

# call k++ init
kpp(points, cluster_centers) #選擇初始種子點

# 下面是kmeans
lenpts10 = len(points) >> 10

changed = 0
while True:
# group element for centroids are used as counters
for cc in cluster_centers:
cc.x = 0
cc.y = 0
cc.group = 0

for p in points:
cluster_centers[p.group].group += 1 #與該種子點在同一簇的數據點的個數
cluster_centers[p.group].x += p.x
cluster_centers[p.group].y += p.y

for cc in cluster_centers: #生成新的中心點
cc.x /= cc.group
cc.y /= cc.group

# find closest centroid of each PointPtr
changed = 0 #記錄所屬簇發生變化的數據點的個數
for p in points:
min_i = nearest_cluster_center(p, cluster_centers)[0]
if min_i != p.group:
changed += 1
p.group = min_i

# stop when 99.9% of points are good
if changed <= lenpts10:
break

for i, cc in enumerate(cluster_centers):
cc.group = i

return cluster_centers

def print_eps(points, cluster_centers, W=400, H=400):
Color = namedtuple("Color", "r g b");

colors = []
for i in xrange(len(cluster_centers)):
colors.append(Color((3 * (i + 1) % 11) / 11.0,
(7 * i % 11) / 11.0,
(9 * i % 11) / 11.0))

max_x = max_y = -FLOAT_MAX
min_x = min_y = FLOAT_MAX

for p in points:
if max_x < p.x: max_x = p.x
if min_x > p.x: min_x = p.x
if max_y < p.y: max_y = p.y
if min_y > p.y: min_y = p.y

scale = min(W / (max_x - min_x),
H / (max_y - min_y))
cx = (max_x + min_x) / 2
cy = (max_y + min_y) / 2

print "%%!PS-Adobe-3.0\n%%%%BoundingBox: -5 -5 %d %d" % (W + 10, H + 10)

print ("/l {rlineto} def /m {rmoveto} def\n" +
"/c { .25 sub exch .25 sub exch .5 0 360 arc fill } def\n" +
"/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath " +
" gsave 1 setgray fill grestore gsave 3 setlinewidth" +
" 1 setgray stroke grestore 0 setgray stroke }def")

for i, cc in enumerate(cluster_centers):
print ("%g %g %g setrgbcolor" %
(colors[i].r, colors[i].g, colors[i].b))

for p in points:
if p.group != i:
continue
print ("%.3f %.3f c" % ((p.x - cx) * scale + W / 2,
(p.y - cy) * scale + H / 2))

print ("\n0 setgray %g %g s" % ((cc.x - cx) * scale + W / 2,
(cc.y - cy) * scale + H / 2))

print "\n%%%%EOF"

def main():
npoints = 30000
k = 7 # # clusters

points = generate_points(npoints, 10)
cluster_centers = lloyd(points, k)
print_eps(points, cluster_centers)

main()

上述代碼實現的演算法是針對二維數據的，所以Point對象有三個屬性，分別是在x軸上的值、在y軸上的值、以及所屬的簇的標識。函數lloyd是
kmeans++演算法的整體實現，其先是通過kpp函數選取合適的種子點，然後對數據集實行kmeans演算法進行聚類。kpp函數的實現完全符合上述
kmeans++的基本思路的2、3、4步。

⑽ k-means演算法解決了什麼問題

k-means
演算法屬於聚類分析方法中一種基本的且應用最廣泛的劃分演算法，它是一種已知聚類類別數的聚類演算法。指定類別數為k，對樣本集合進行聚類，聚類的結果由k
個聚類中心來表達，基於給定的聚類目標函數（或者說是聚類效果判別准則），演算法採用迭代更新的方法，每一次迭代過程都是向目標函數值減小的方向進行，最終的聚類結果使目標函數值取得極小值，達到較優的聚類效果。使用平均誤差准則函數e作為聚類結果好壞的衡量標准之一，保證了演算法運行結果的可靠性和有效性。