Kmeans聚類算法ppt課件

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

2、那個中心所處在的簇類中;四、調(diào)整新類并且重新計(jì)算出新類的中心。五、計(jì)算聚類準(zhǔn)則函數(shù)E，若E不滿足收斂條件。重復(fù)二、三、四，六、結(jié)束3八、八、K-meansK-means聚類算法聚類算法2. K-means2. K-means聚類算法原理聚類算法原理 K-Means算法的工作框架：4八、八、K-meansK-means聚類算法聚類算法2. K-means2. K-means聚類算法原理聚類算法原理K-meansK-means算法的工作流程算法的工作流程5（補(bǔ)充）距離的算法的選擇（補(bǔ)充）距離的算法的選擇 一般，我們都是以歐拉距離來計(jì)算與種子點(diǎn)的距離。但是，還有幾種可以用于k-means的距離計(jì)算方

3、法。1）閔可夫斯基距離可以隨意取值，可以是負(fù)數(shù)，也可以是正數(shù)，或是無窮大。2）歐拉距離也就是第一個公式=2的情況3）市郊區(qū)距離公式也就是第一個公式=1的情況4）余弦距離（常用于文本）6（補(bǔ)充）距離的算法的選擇（補(bǔ)充）距離的算法的選擇 閔可夫斯基距離歐拉距離市郊區(qū)距離公式7八、八、K-meansK-means聚類算法聚類算法3 K-means3 K-means聚類算法特點(diǎn)及應(yīng)用聚類算法特點(diǎn)及應(yīng)用 3.1 K-means 3.1 K-means聚類算法特點(diǎn)聚類算法特點(diǎn)優(yōu)點(diǎn)：（1）算法簡單、快速。（2）對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的。（3）算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。

4、缺點(diǎn)：（1）K-means聚類算法只有在簇的平均值被定義的情況下才能使用。（2）要求用戶必須事先給出要生成的簇的數(shù)目k。（3）對初值敏感。（4）不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。（5）對于“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感。8K-meansK-means缺點(diǎn)以及改進(jìn)缺點(diǎn)以及改進(jìn)（1 1）要求用戶必須事先給出要生成的簇的數(shù)目k。這個k并不是最好的。解決解決：肘部算法肘部算法是一種啟發(fā)式方法來估計(jì)最優(yōu)聚類數(shù)量，稱為肘部法則（Elbow Method）。從圖中可以看出， K 值從1到3時，平均畸變程度變化最大。超過3以后，平均畸變程度變化顯著降低。因此肘部就是 K=3 。各個類畸變程度（dis

5、tortions）之和；每個類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和；最優(yōu)解以成本函數(shù)最小化為目標(biāo)，其中uk是第k個類的重心位置9K-meansK-means缺點(diǎn)以及改進(jìn)缺點(diǎn)以及改進(jìn)（2 2）K-Means算法需要用初始隨機(jī)種子點(diǎn)來搞，不同是起點(diǎn)結(jié)果不同。可能導(dǎo)致算法陷入局部最優(yōu)。解決解決：K-Means+算法（初始的聚類中心之間的相互距離要盡可能的遠(yuǎn)）1.先從我們的數(shù)據(jù)庫隨機(jī)挑個隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”2.對于每個點(diǎn)，我們都計(jì)算其和最近的一個“種子點(diǎn)”的距離D(x)并保存在一個數(shù)組里，然后把這些距離加起來得到Sum(D(x)。3.然后，再取一個隨機(jī)值，用權(quán)重的方式來取計(jì)算下一個“種子點(diǎn)

6、”。這個算法的實(shí)現(xiàn)是，先取一個能落在Sum(D(x)中的隨機(jī)值Random，然后用Random -= D(x)，直到其=0，此時的點(diǎn)就是下一個“種子點(diǎn)”。4.重復(fù)2和3直到k個聚類中心被選出來5.利用這k個初始的聚類中心來運(yùn)行標(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)的點(diǎn)會以較大的概率被選中作為新的聚類中心。10八、八、K-meansK-means聚類算法聚類算法3 K-means3 K-means聚類算法特點(diǎn)及應(yīng)用聚類算法特點(diǎn)及應(yīng)用 3.2 K-means 3.2 K-mea

7、ns聚類算法應(yīng)用聚類算法應(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八、八、K-meansK-means聚類算法聚類算法實(shí)例分析一實(shí)例分析一利用K-mean方法，對AL 12個數(shù)據(jù)分成兩類。初始的隨機(jī)點(diǎn)指定為M1(20,60)，M2(80,80)。列出每一次分類結(jié)果及每一類中的平均值（中心點(diǎn)）。 i=1,212八、八、K-meansK-means聚類算法聚類算法13八、八、K-meansK-means聚類算法聚類算法14八、八、K-meansK-means聚類算法聚類算法 15八、八、K-meansK-means聚類算法聚類算法16八、八、K-meansK-means聚類算法聚類算法實(shí)例分析二實(shí)例分析二設(shè)有數(shù)據(jù)樣本集合為X=1,5,10,9,26,32,16,21,14，將X聚為3類，即K=3。隨即選擇前三個數(shù)值為初始的聚類中