Kmeans聚類算法課件

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

2、歸到距離它最近的那個(gè)中心所處在的簇類中;四、調(diào)整新類并且重新計(jì)算出新類的中心。五、計(jì)算聚類準(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（補(bǔ)充）距離的算法的選擇 一般，我們都是以歐

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

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

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

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

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

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