Kmeans聚類算法課件

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

2、歸到距離它最近的那個中心所處在的簇類中;四、調(diào)整新類并且重新計算出新類的中心。五、計算聚類準(zhǔn)則函數(shù)E，若E不滿足收斂條件。重復(fù)二、三、四，六、結(jié)束3精選版課件ppt八、K-means聚類算法2. K-means聚類算法原理3八、K-means聚類算法2. K-means聚類算法原理 K-Means算法的工作框架：4精選版課件ppt八、K-means聚類算法2. K-means聚類算法原理4八、K-means聚類算法2. K-means聚類算法原理K-means算法的工作流程5精選版課件ppt八、K-means聚類算法2. K-means聚類算法原理K（補充）距離的算法的選擇 一般，我們都是以歐

3、拉距離來計算與種子點的距離。但是，還有幾種可以用于k-means的距離計算方法。1）閔可夫斯基距離可以隨意取值，可以是負(fù)數(shù)，也可以是正數(shù)，或是無窮大。2）歐拉距離也就是第一個公式=2的情況3）市郊區(qū)距離公式也就是第一個公式=1的情況4）余弦距離（常用于文本）6精選版課件ppt（補充）距離的算法的選擇6精選版課件ppt（補充）距離的算法的選擇 閔可夫斯基距離歐拉距離市郊區(qū)距離公式7精選版課件ppt（補充）距離的算法的選擇閔可夫斯基距離歐拉距離市郊區(qū)距離公式八、K-means聚類算法3 K-means聚類算法特點及應(yīng)用 3.1 K-means聚類算法特點優(yōu)點：（1）算法簡單、快速。（2）對處理大數(shù)

4、據(jù)集，該算法是相對可伸縮的和高效率的。（3）算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。缺點：（1）K-means聚類算法只有在簇的平均值被定義的情況下才能使用。（2）要求用戶必須事先給出要生成的簇的數(shù)目k。（3）對初值敏感。（4）不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。（5）對于“噪聲”和孤立點數(shù)據(jù)敏感。8精選版課件ppt八、K-means聚類算法3 K-means聚類算法特點及應(yīng)K-means缺點以及改進（1）要求用戶必須事先給出要生成的簇的數(shù)目k。這個k并不是最好的。解決：肘部算法肘部算法是一種啟發(fā)式方法來估計最優(yōu)聚類數(shù)量，稱為肘部法則（Elbow Method）。從圖中可以看

5、出， K 值從1到3時，平均畸變程度變化最大。超過3以后，平均畸變程度變化顯著降低。因此肘部就是 K=3 。各個類畸變程度（distortions）之和；每個類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和；最優(yōu)解以成本函數(shù)最小化為目標(biāo)，其中uk是第k個類的重心位置9精選版課件pptK-means缺點以及改進從圖中可以看出， K 值從1到3時K-means缺點以及改進（2）K-Means算法需要用初始隨機種子點來搞，不同是起點結(jié)果不同。可能導(dǎo)致算法陷入局部最優(yōu)。解決：K-Means+算法（初始的聚類中心之間的相互距離要盡可能的遠）1.先從我們的數(shù)據(jù)庫隨機挑個隨機點當(dāng)“種子點”2.對于每個點

6、，我們都計算其和最近的一個“種子點”的距離D(x)并保存在一個數(shù)組里，然后把這些距離加起來得到Sum(D(x)。3.然后，再取一個隨機值，用權(quán)重的方式來取計算下一個“種子點”。這個算法的實現(xiàn)是，先取一個能落在Sum(D(x)中的隨機值Random，然后用Random -= D(x)，直到其=0，此時的點就是下一個“種子點”。4.重復(fù)2和3直到k個聚類中心被選出來5.利用這k個初始的聚類中心來運行標(biāo)準(zhǔn)的k-means算法假設(shè)A、B、C、D的D(x)如上圖所示，當(dāng)算法取值Sum(D(x)*random時，該值會以較大的概率落入D(x)較大的區(qū)間內(nèi)，所以對應(yīng)的點會以較大的概率被選中作為新的聚類中心。

7、10精選版課件pptK-means缺點以及改進1.先從我們的數(shù)據(jù)庫隨機挑個隨機點八、K-means聚類算法3 K-means聚類算法特點及應(yīng)用 3.2 K-means聚類算法應(yīng)用 （1）K-means 算法在散貨船代貨運系統(tǒng)中的應(yīng)用（2）K-Means 算法在客戶細分中的應(yīng)用補充：K-means 適用于各種各樣的領(lǐng)域。比如文本分析、路徑規(guī)劃、神經(jīng)網(wǎng)絡(luò)、用戶行為、生物信息等11精選版課件ppt八、K-means聚類算法3 K-means聚類算法特點及應(yīng)八、K-means聚類算法實例分析一利用K-mean方法，對AL 12個數(shù)據(jù)分成兩類。初始的隨機點指定為M1(20,60)，M2(80,80)。列

8、出每一次分類結(jié)果及每一類中的平均值（中心點）。i=1,212精選版課件ppt八、K-means聚類算法實例分析一i=1,212精選版課八、K-means聚類算法13精選版課件ppt八、K-means聚類算法13精選版課件ppt八、K-means聚類算法14精選版課件ppt八、K-means聚類算法14精選版課件ppt八、K-means聚類算法15精選版課件ppt八、K-means聚類算法15精選版課件ppt八、K-means聚類算法16精選版課件ppt八、K-means聚類算法16精選版課件ppt八、K-means聚類算法實例分析二設(shè)有數(shù)據(jù)樣本集合為X=1,5,10,9,26,32,16,21,14，將X聚為3類，即K=3。隨即選擇前三個數(shù)值為初始的聚類中心，即z1=1,z2=5,z3=10（采用歐氏距離計算）第一次第二次17精選版課件ppt八、K-means聚類算法實例分析二第一次第二次17精選版課八、K-means聚類算法在第五次迭代時，得到的三個簇與第四迭代結(jié)果相同，而且