1、精選課件數據挖掘算法、原理與實踐數據挖掘算法、原理與實踐王振武王振武精選課件八、八、K-meansK-means聚類算法聚類算法1. 1.簡介簡介 K-means聚類算法就是基于距離的聚類算法（cluster algorithm） 主要通過不斷地取離種子點最近均值的算法2個中心點的kmeans精選課件八、八、K-meansK-means聚類算法聚類算法2. K-means2. K-means聚類算法原理聚類算法原理 K-means聚類算法的基本思想：一、指定需要劃分的簇的個數k值;二、隨機地選擇k個初始數據對象點作為初始的聚類中心;三、計算其余的各個數據對象到這k個初始聚類中心的距離，把數據對

2、象劃歸到距離它最近的那個中心所處在的簇類中;四、調整新類并且重新計算出新類的中心。五、計算聚類準則函數E，若E不滿足收斂條件。重復二、三、四，六、結束精選課件八、八、K-meansK-means聚類算法聚類算法2. K-means2. K-means聚類算法原理聚類算法原理 K-Means算法的工作框架：精選課件八、八、K-meansK-means聚類算法聚類算法2. K-means2. K-means聚類算法原理聚類算法原理K-meansK-means算法的工作流程算法的工作流程精選課件（補充）距離的算法的選擇（補充）距離的算法的選擇 一般，我們都是以歐拉距離來計算與種子點的距離。但是，還有

3、幾種可以用于k-means的距離計算方法。1）閔可夫斯基距離可以隨意取值，可以是負數，也可以是正數，或是無窮大。2）歐拉距離也就是第一個公式=2的情況3）市郊區距離公式也就是第一個公式=1的情況4）余弦距離（常用于文本）精選課件（補充）距離的算法的選擇（補充）距離的算法的選擇 閔可夫斯基距離歐拉距離市郊區距離公式精選課件八、八、K-meansK-means聚類算法聚類算法3 K-means3 K-means聚類算法特點及應用聚類算法特點及應用 3.1 K-means 3.1 K-means聚類算法特點聚類算法特點優點：（1）算法簡單、快速。（2）對處理大數據集，該算法是相對可伸縮的和高效率的。

4、（3）算法嘗試找出使平方誤差函數值最小的k個劃分。缺點：（1）K-means聚類算法只有在簇的平均值被定義的情況下才能使用。（2）要求用戶必須事先給出要生成的簇的數目k。（3）對初值敏感。（4）不適合于發現非凸面形狀的簇，或者大小差別很大的簇。（5）對于“噪聲”和孤立點數據敏感。精選課件K-meansK-means缺點以及改進缺點以及改進（1 1）要求用戶必須事先給出要生成的簇的數目k。這個k并不是最好的。解決解決：肘部算法肘部算法是一種啟發式方法來估計最優聚類數量，稱為肘部法則（Elbow Method）。從圖中可以看出， K 值從1到3時，平均畸變程度變化最大。超過3以后，平均畸變程度變化

5、顯著降低。因此肘部就是 K=3 。各個類畸變程度（distortions）之和；每個類的畸變程度等于該類重心與其內部成員位置距離的平方和；最優解以成本函數最小化為目標，其中uk是第k個類的重心位置精選課件K-meansK-means缺點以及改進缺點以及改進（2 2）K-Means算法需要用初始隨機種子點來搞，不同是起點結果不同。可能導致算法陷入局部最優。解決解決：K-Means+算法（初始的聚類中心之間的相互距離要盡可能的遠）1.先從我們的數據庫隨機挑個隨機點當“種子點”2.對于每個點，我們都計算其和最近的一個“種子點”的距離D(x)并保存在一個數組里，然后把這些距離加起來得到Sum(D(x)

6、。3.然后，再取一個隨機值，用權重的方式來取計算下一個“種子點”。這個算法的實現是，先取一個能落在Sum(D(x)中的隨機值Random，然后用Random -= D(x)，直到其=0，此時的點就是下一個“種子點”。4.重復2和3直到k個聚類中心被選出來5.利用這k個初始的聚類中心來運行標準的k-means算法假設A、B、C、D的D(x)如上圖所示，當算法取值Sum(D(x)*random時，該值會以較大的概率落入D(x)較大的區間內，所以對應的點會以較大的概率被選中作為新的聚類中心。精選課件八、八、K-meansK-means聚類算法聚類算法3 K-means3 K-means聚類算法特點及

7、應用聚類算法特點及應用 3.2 K-means 3.2 K-means聚類算法應用聚類算法應用 （1）K-means 算法在散貨船代貨運系統中的應用（2）K-Means 算法在客戶細分中的應用補充：K-means 適用于各種各樣的領域。比如文本分析、路徑規劃、神經網絡、用戶行為、生物信息等精選課件八、八、K-meansK-means聚類算法聚類算法實例分析一實例分析一利用K-mean方法，對AL 12個數據分成兩類。初始的隨機點指定為M1(20,60)，M2(80,80)。列出每一次分類結果及每一類中的平均值（中心點）。 i=1,2精選課件八、八、K-meansK-means聚類算法聚類算法精選課件八、八、K-meansK-means聚類算法聚類算法精選課件八、八、K-meansK-means聚類算法聚類算法 精選課件八、八、K-meansK-means聚類算法聚類算法精選課件八、八、K-meansK-means聚類算法聚類算法實例分析二實例分析二設有數據樣本集合為X=1,5,10,9,26,32,16,21,14，將X聚為3類，即K=3。隨即選擇前三個數值為初始的聚