javaKMEANS演算法

㈠ kmeans聚類演算法優缺點

優缺點如下：

1、優點

k-平均演算法是解決聚類問題的一種經典演算法，演算法簡單、快速。

對處理大數據集，該演算法是相對可伸縮的和高效率的，因為它的復雜度大約是O(nkt) O(nkt)O(nkt)，其中n是所有對象的數目，k是簇的數目，t是迭代的次數。通常k<<n。這個演算法經常以局部最優結束。

演算法嘗試找出使平方誤差函數值最小的k個劃分。當簇是密集的、球狀或團狀的，而簇與簇之間區別明顯時，它的聚類效果很好。

2、缺點

對K值敏感。也就是說，K的選擇會較大程度上影響分類效果。在聚類之前，我們需要預先設定K的大小，但是我們很難確定分成幾類是最佳的，比如上面的數據集中，顯然分為2類，即K = 2最好，但是當數據量很大時，我們預先無法判斷。

對離群點和雜訊點敏感。如果在上述數據集中添加一個噪音點，這個噪音點獨立成一個類。很顯然，如果K=2,其餘點是一類，噪音點自成一類，原本可以區分出來的點被噪音點影響，成為了一類了。如果K=3，噪音點也是自成一類，剩下的數據分成兩類。這說明噪音點會極大的影響其他點的分類。

聚類分析特點

聚類分析的實質：是建立一種分類方法，它能夠將一批樣本數據按照他們在性質上的親密程度在沒有先驗知識的情況下自動進行分類。這里所說的類就是一個具有相似性的個體的集合，不同類之間具有明顯的區別。

層次聚類分析是根據觀察值或變數之間的親疏程度，將最相似的對象結合在 一起，以逐次聚合的方式（Agglomerative Clustering），它將觀察值分類，直到最後所有樣本都聚成一類。

層次聚類分析有兩種形式，一種是對樣本（個案）進行分類，稱為Q型聚類；另一種是對研究對象的觀察變數進行分類，稱為R型聚類。

㈡ 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$$。

㈢ k-means演算法怎麼為對稱矩陣進行聚類

幾種典型的聚類融合演算法：
1.基於超圖劃分的聚類融合演算法
(1)Cluster-based Similarity Partitioning Algorithm(GSPA)
(2)Hyper Graph-Partitioning Algorithm(HGPA)
(3)Meta-Clustering Algorithm(MCLA)
2.基於關聯矩陣的聚類融合演算法
Voting-K-Means演算法。
3.基於投票策略的聚類融合演算法
w-vote是一種典型的基於加權投票的聚類融合演算法。
同時還有基於互信息的聚類融合演算法和基於有限混合模型的聚類融合演算法。
二、基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法
Voting-K-Means演算法是一種基於關聯矩陣的聚類融合演算法，關聯矩陣的每一行和每一列代表一個數據點，關聯矩陣的元素表示數據集中數據點對共同出現在同一個簇中的概率。
演算法過程：
1.在一個數據集上得到若干個聚類成員；
2.依次掃描這些聚類成員，如果數據點i和j在某個聚類成員中被劃分到同一個簇中，那麼就在關聯矩陣對應的位置計數加1；關聯矩陣中的元素值越大，說明該元素對應的兩個數據點被劃分到同一個簇中的概率越大；
3.得到關聯矩陣之後，Voting-K-Means演算法依次檢查關聯矩陣中的每個元素，如果它的值大於演算法預先設定的閥值，就把這個元素對應的兩個數據點劃分到同一個簇中。

Voting-K-Means演算法的優缺點：
Voting-K-Means演算法不需要設置任何參數，在聚類融合的過程中可以自動地的選擇簇的個數 並且可以處理任意形狀的簇。因為Voting-K-Means演算法在聚類融合過程中是根據兩個數據點共同出現在同一個簇中的可能性大小對它們進行劃分的，所以只要兩個數據點距離足夠近，它們就會被劃分到一個簇中。
Voting-K-Means演算法的缺點是時間復雜度較高，它的時間復雜度是O(n^2);需要較多的聚類成員，如果聚類成員達不到一定規模，那麼關聯矩陣就不能准確反映出兩個數據點出現在同一個簇的概率。

package clustering;import java.io.FileWriter;import weka.clusterers.ClusterEvaluation;import weka.clusterers.SimpleKMeans;import weka.core.DistanceFunction;import weka.core.EuclideanDistance;import weka.core.Instances;import weka.core.converters.ConverterUtils.DataSource;import weka.filters.unsupervised.attribute.Remove;public class Votingkmeans2 extends SimpleKMeans { /** 生成的序列號 */ private static final long serialVersionUID = 1557181390469997876L; /** 劃分的簇數 */ private int m_NumClusters; /** 每個劃分的簇中的實例的數量 */ public int[] m_ClusterSizes; /** 使用的距離函數，這里是歐幾里德距離 */ protected DistanceFunction m_DistanceFunction = new EuclideanDistance(); /** 實例的簇號賦值 */ protected int[] m_Assignments; /** 設定聚類成員融合閥值 */ private final static double THREASOD = 0.5; /** 生成一個聚類器 */ public void buildClusterer(Instances data) throws Exception{ final int numinst = data.numInstances(); // 數據集的大小 double [][]association = new double[numinst][numinst]; // 定義並初始化一個關聯矩陣 int numIteration = 40; // 設置生成的聚類成員數 final int k = (int)Math.sqrt(numinst); // 設置K-Means聚類演算法參數——簇數 for(int i = 0; i < numIteration; i++) { if(data.classIndex() == -1) data.setClassIndex(data.numAttributes() - 1); // 索引是從0開始 String[] filteroption = new String[2]; filteroption[0] = "-R"; filteroption[1] = String.valueOf(data.classIndex() + 1);// 索引是從1開始 Remove remove = new Remove(); remove.setOptions(filteroption); remove.setInputFormat(data); /* 使用過濾器模式生成新的數據集；新數據集是去掉類標簽之後的數據集 */ Instances newdata = weka.filters.Filter.useFilter(data, remove); /* 生成一個K-Means聚類器 */ SimpleKMeans sm = new SimpleKMeans(); sm.setNumClusters(k); sm.setPreserveInstancesOrder(true); // 保持數據集實例的原始順序 sm.setSeed(i); // 通過設置不同的種子，設置不同的簇初始中心點，從而得到不同的聚類結果 sm.buildClusterer(newdata); int[] assigm = sm.getAssignments(); // 得到數據集各個實例的賦值 /* 建立關聯矩陣 */ for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { if(assigm[j] == assigm[m]) { association[j][m] = association[j][m] + 1.0 / numIteration ; } } } } System.out.println(); /* 將生成的關聯矩陣寫入.txt文件（註：生成的txt文本文件在e:/result.txt中） */ FileWriter fw = new FileWriter("e://result.txt"); for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { //由於關聯矩陣是對稱的，為了改進演算法的效率，只計算矩陣的上三角 String number = String.format("%8.2f", association[j][m]); fw.write(number); } fw.write("\n"); } /* 處理關聯矩陣，分別考慮了兩種情況 ：1.關聯矩陣中某個元素對應的兩個數據點已經被劃分到了不同的簇中 * 2.兩個數據點中有一個或者兩個都沒有被劃分到某個簇中。 */ int[] flag = new int[numinst]; int[] flagk = new int[k]; int[] finallabel = new int[numinst]; for(int m = 0; m < numinst; m++) { for(int n = m; n < numinst; n++) { if(association[m][n] > THREASOD) { if(flag[m] == 0 && flag[n] == 0) { // 兩個數據點都沒有被劃分到某個簇中， int i = 0; // 將他們劃分到同一個簇中即可 while (i < k && flagk[i] == 1) i = i + 1; finallabel[m] = i; finallabel[n] = i; flag[m] = 1; flag[n] = 1; flagk[i] = 1; } else if (flag[m] == 0 && flag[n] == 1) { // 兩個數據點中有一個沒有被劃分到某個簇中， finallabel[m] = finallabel[n]; // 將他們劃分到同一個簇中即可 flag[m] = 1; } else if (flag[m] == 1 && flag[n] == 0) { finallabel[n] = finallabel[m]; flag[n] = 1; } else if (flag[m] == 1 && flag[n] == 1 && finallabel[m] != finallabel[n]) { // 兩個數據點已被劃分到了不同的簇中， flagk[finallabel[n]] = 0; // 將它們所在的簇合並 int temp = finallabel[n]; for(int i = 0; i < numinst; i++) { if(finallabel[i] == temp) finallabel[i] = finallabel[m]; } } } } } m_Assignments = new int[numinst]; System.out.println("基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法的最終聚類結果"); for(int i = 0; i < numinst; i++) { m_Assignments[i] = finallabel[i]; System.out.print(finallabel[i] + " "); if((i+1) % 50 == 0) System.out.println(); } for(int i = 0; i < k; i++) { if(flagk[i] == 1) m_NumClusters++; } } /** * return a string describing this clusterer * * @return a description of the clusterer as a string */ public String toString() { return "Voting-KMeans\n"; } public static void main(String []args) { try {String filename="e://weka-data//iris.arff"; Instances data = DataSource.read(filename); Votingkmeans2 vk = new Votingkmeans2(); vk.buildClusterer(data); /* 要生成Voting-K-Means的聚類評估結果包括准確率等需要覆蓋重寫toString()方法； * 因為沒有覆蓋重寫，所以這里生產的評估結果沒有具體內容。 */ ClusterEvaluation eval = new ClusterEvaluation(); eval.setClusterer(vk); eval.evaluateClusterer(new Instances(data)); System.out.println(eval.clusterResultsToString()); } catch (Exception e) { e.printStackTrace(); }}}

分析代碼時注意：得到的類成員變數m_Assignments就是最終Voting-K-Means聚類結果；由於是採用了開源機器學習軟體Weka中實現的SimpleKMeans聚類演算法，初始時要指定簇的個數，這里是數據集大小開根號向下取整；指定的閥值為0.5，即當關聯矩陣元素的值大於閥值時，才對該元素對應的兩個數據點進行融合，劃分到一個簇中，考慮兩種情況，代碼注釋已有，這里不再詳述。但聚類融合的實驗結果並不理想，鶯尾花數據集irsi.arff是數據挖掘實驗中最常用的數據集，原數據集共有三個類；但本實驗進行四十個聚類成員的融合，其最終聚類結果劃分成兩個簇；其原因可能有兩個：一是演算法本身的問題，需要使用其他更加優化的聚類融合演算法；二是實現上的問題，主要就在聚類結果的融合上，需要進行一步對照關聯矩陣進行邏輯上的分析，找出代碼中的問題。關聯矩陣文本文件http://download.csdn.net/detail/lhkaikai/7294323

---------------------

本文來自 Turingkk 的CSDN 博客 ，全文地址請點擊：https://blog.csdn.net/lhkaikai/article/details/25004823?utm_source=

㈣ 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值 ：要得到的簇的個數

質心 ：每個簇的均值向量，即向量各維取平均即可

距離量度 ：常用歐幾里得距離和餘弦相似度（先標准化）

演算法流程：

1、首先確定一個k值，即我們希望將數據集經過聚類得到k個集合。

2、從數據集中隨機選擇k個數據點作為質心。

3、對數據集中每一個點，計算其與每一個質心的距離（如歐式距離），離哪個質心近，就劃分到那個質心所屬的集合。

4、把所有數據歸好集合後，一共有k個集合。然後重新計算每個集合的質心。

5、如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值（表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂），我們可以認為聚類已經達到期望的結果，演算法終止。

6、如果新質心和原質心距離變化很大，需要迭代3~5步驟。

K-Means採用的啟發式方式很簡單，用下面一組圖就可以形象的描述:

        上圖a表達了初始的數據集，假設k=2。在圖b中，我們隨機選擇了兩個k類所對應的類別質心，即圖中的紅色質心和藍色質心，然後分別求樣本中所有點到這兩個質心的距離，並標記每個樣本的類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。

坐標系中有六個點：

1、我們分兩組，令K等於2，我們隨機選擇兩個點：P1和P2

2、通過勾股定理計算剩餘點分別到這兩個點的距離：

3、第一次分組後結果：

        組A：P1

        組B：P2、P3、P4、P5、P6

4、分別計算A組和B組的質心：

        A組質心還是P1=（0，0）

        B組新的質心坐標為：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）

5、再次計算每個點到質心的距離：

6、第二次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

7、再次計算質心：

        P哥1=（1.33，1） 

        P哥2=（9，8.33）

8、再次計算每個點到質心的距離：

9、第三次分組結果：

        組A：P1、P2、P3

        組B：P4、P5、P6

可以發現，第三次分組結果和第二次分組結果一致，說明已經收斂，聚類結束。

優點：

1、原理比較簡單，實現也是很容易，收斂速度快。

2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

3、主要需要調參的參數僅僅是簇數k。

缺點：

1、K值需要預先給定，很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同 ，對結果影響很大。

3、對噪音和異常點比較的敏感。用來檢測異常值。

4、採用迭代方法， 可能只能得到局部的最優解，而無法得到全局的最優解 。

1、K值怎麼定？

        答：分幾類主要取決於個人的經驗與感覺，通常的做法是多嘗試幾個K值，看分成幾類的結果更好解釋，更符合分析目的等。或者可以把各種K值算出的 E 做比較，取最小的 E 的K值。

2、初始的K個質心怎麼選？

        答：最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更reasonable，就用哪個結果。 當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法（如層次聚類）得到聚類結果，從結果中每個分類選一個點。

3、關於離群值？

        答：離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些「極大」「極小」之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離群值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

4、單位要一致！

        答：比如X的單位是米，Y也是米，那麼距離算出來的單位還是米，是有意義的。但是如果X是米，Y是噸，用距離公式計算就會出現「米的平方」加上「噸的平方」再開平方，最後算出的東西沒有數學意義，這就有問題了。

5、標准化

        答：如果數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼，在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里德距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化（normalization），即將數據按比例縮放，使之落入一個小的特定區間。

參考文章： 聚類、K-Means、例子、細節

㈦ kmeans是什麼意思

kmeans的意思：是一種簡單的聚類方法，一般在數據分析前期使用，選取適當的k，將數據分類後，然後分類研究不同聚類下數據的特點。

Kmeans聚類演算法是一種常用的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。

㈧ kmeans聚類演算法是什麼

k均值聚類演算法是一種迭代求解的聚類分析演算法，由於簡潔和效率使得他成為所有聚類演算法中最廣泛使用的。k均值聚類演算法通過給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值演算法根據某個距離函數反復把數據分入k個聚類中。

k均值聚類演算法的具體步驟：

其步驟是預將數據分為K組，則隨機選取K個對象作為初始的聚類中心，然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。

每分配一個樣本，聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

㈨ K-MEANS演算法的終止條件

K-MEANS演算法的終止條件可以是以下任何一個：

1、沒有（或最小數目）對象被重新分配給不同的聚類。

2、沒有（或最小數目）聚類中心再發生變化。

3、誤差平方和局部最小。

偽代碼

選擇k個點作為初始質心。

repeat 將每個點指派到最近的質心，形成k個簇，重新計算每個簇的質心，until，質心不發生變化。

(9)javaKMEANS演算法擴展閱讀：

定義：

聚類是一個將數據集中在某些方面相似的數據成員進行分類組織的過程，聚類就是一種發現這種內在結構的技術，聚類技術經常被稱為無監督學習。

k均值聚類是最著名的劃分聚類演算法，由於簡潔和效率使得他成為所有聚類演算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值演算法根據某個距離函數反復把數據分入k個聚類中。

K-MEANS演算法的性質：k均值聚類是使用最大期望演算法（Expectation-Maximization algorithm）求解的高斯混合模型（Gaussian Mixture Model, GMM）在正態分布的協方差為單位矩陣，且隱變數的後驗分布為一組狄拉克δ函數時所得到的特例。