大數(shù)據(jù)分析方法與應(yīng)用 課件 第4章 聚類算法

大數(shù)據(jù)分析方法與應(yīng)用第4章聚類算法4.1聚類的原理目錄CONTENTS4.2K-Means聚類4.3

K最近鄰算法4.4

模糊C-均值算法第4章聚類算法4.1聚類的原理聚類的原理聚類（Clustering）是指根據(jù)“物以類聚”的原理，將本身沒有類別的樣本聚集成不同的組，這樣的一組數(shù)據(jù)對(duì)象的集合叫作簇。聚類算法是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中常見的技術(shù)之一，具有廣泛的應(yīng)用。聚類是按照某個(gè)特定標(biāo)準(zhǔn)（如距離）把一個(gè)數(shù)據(jù)集分割成不同的類或簇，使得同一個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象的相似性盡可能大，同時(shí)不在同一個(gè)簇中的數(shù)據(jù)對(duì)象的差異性也盡可能地大。也即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同類數(shù)據(jù)盡量分離。在分類（Classification）中，對(duì)于目標(biāo)數(shù)據(jù)庫(kù)中存在哪些類是知道的，要做的就是將每一條記錄分別屬于哪一類標(biāo)記出來(lái)。4.1聚類的原理

聚類的原理聚類的一般過(guò)程01數(shù)據(jù)特征標(biāo)準(zhǔn)化和降維數(shù)據(jù)準(zhǔn)備03通過(guò)對(duì)選擇的特征進(jìn)行轉(zhuǎn)換形成新的突出特征特征提取02特征選擇04基于某種距離函數(shù)進(jìn)行相似度度量，獲取簇聚類05分析聚類結(jié)果，如距離誤差等聚類結(jié)果評(píng)估從最初的特征中選擇最有效的特征，并將其存儲(chǔ)在向量中4.2K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理K-Means算法步驟為每個(gè)聚類確定一個(gè)初始聚類中心，這樣就有k個(gè)初始聚類中心將樣本集中的樣本按照最小距離原則分配到最近鄰聚類使用每個(gè)聚類中的樣本均值作為新的聚類中心結(jié)束得到k個(gè)聚類重復(fù)步驟2和3直到聚類中心不再變化輸入輸出簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)k個(gè)簇，使平方誤差準(zhǔn)則最小4.2K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理K-Means聚類算法使用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個(gè)聚類子集X1,X2,…,Xk；各個(gè)聚類子集中的樣本數(shù)量分別為n1,n2,…,nk；各個(gè)聚類子集的均值代表點(diǎn)（也稱聚類中心）分別為m1,m2,…,mk。誤差平方和準(zhǔn)則函數(shù)公式為：4.2K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理數(shù)據(jù)對(duì)象集合S如下表所示，作為一個(gè)聚類分析的二維樣本，要求的簇的數(shù)量k=2O12345x001.555y20002數(shù)據(jù)對(duì)象集合S1）選擇O1(0,2)，O2(0,0)為初始的簇中心，即M1=O1=(0,2)，M2=O2=(0,0)4.2K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理2）對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇a.

對(duì)于O3：

；

；

因?yàn)閐(M1,O3)≥d(M2,O3)，故將O3分配給C2。b. 對(duì)于O4：

；

因?yàn)閐(M1,O4)≥d(M2,O4)，故將O4分配給C2。c. 對(duì)于O5：

；

因?yàn)閐(M1,O5)≤d(M2,O5)，故將O5分配給C1。綜上，得到新簇C1={O1,O5}，中心為M1=O1=(0,2)；C2={O2,O3,O4}，中心為M2=O2=(0,0)。計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為：E1=[(0-0)2+(2-2)2]+[(0-5)2+(2-2)2]=25；E2=[(0-0)2+(0-0)2]+[(0-1.5)2+(0-0)2]+[(0-5)2+(0-0)2]=27.25?？傮w平均方差是：E=E1+E2=25+27.25=52.254.2K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理M1=((0+5)/2,(2+2)/2)=(2.5,2)；M2=((0+1.5+5)/3,(0+0+0+0)/3)=(2.17,0)重復(fù)2和3，得到O1分配給C1，O2分配給C2，O3分配給C2，O4分配給C2，O5分配給C1。綜上，得到新簇C1={O1,O5}，中心為M1=(2.5,2)和C2={O2,O3,O4}，中心為M2=(2.17,0)。單個(gè)方差為：E1=[(0-2.5)2+(2-2)2]+[(2.5-5)2+(2-2)2]=12.5；E2=[(2.17-0)2+(0-0)2]+[(2.17-1.5)2+(0-0)2]+[(2.17-5)2+(0-0)2]=13.1667。總體平均方差是：E=E1+E2=12.5+13.1667=25.667。由上可以看出，第一次迭代后，總體平均方差值由52.25至25.667，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過(guò)程，算法停止。3）計(jì)算新簇的中心4.2

K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理K-Means算法的主要優(yōu)點(diǎn)是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速;對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的;k值可以根據(jù)實(shí)際需求自行調(diào)節(jié)，以達(dá)到控制類簇內(nèi)樣本點(diǎn)數(shù)量的目的;當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，它的效果較好.4.2

K-Means聚類K-Means聚類4.2.1K-Means聚類算法的原理K-Means算法的主要缺點(diǎn)在簇的平均值被定義的情況下才能使用，這對(duì)于處理符號(hào)屬性的數(shù)據(jù)不適用;必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。經(jīng)常發(fā)生得到次優(yōu)劃分的情況。解決方法是多次嘗試不同的初始值;它對(duì)于“噪聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響.4.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)MATLAB提供了專用函數(shù)K-Means用于聚類的質(zhì)心，默認(rèn)為歐幾里得距離，如圖所示

MATLAB專用函數(shù)K-Means4.2

K-Means聚類K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)假設(shè)給定的數(shù)據(jù)集X={xm|m=1,2,…,total}，X中的樣本用d個(gè)描述屬性A1,A2,…,Ad（維度）來(lái)表示。數(shù)據(jù)樣本xi=(xi1,xi2,…,xid)，xj=(xj1,xj2,…,xjd)，其中xi1,xi2,…,xid和xj1,xj2,…,xjd分別是樣本xi和xj對(duì)應(yīng)d個(gè)描述屬性A1,A2,…,Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來(lái)表示，距離越小，樣本xi和xj越相似，差異度越??；距離越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：4.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)依據(jù)下表中二維數(shù)據(jù)，通過(guò)MATLAB中K-Means算法，令K=3進(jìn)行聚類。x23-121011540421211222y2010101231-1020212-110

K-Means算法代碼示例數(shù)據(jù)4.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)K-Means算法代碼示例14.2

K-Means聚類K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)K-Means算法代碼示例24.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實(shí)現(xiàn)聚類結(jié)果示意由右圖可知，K-Means根據(jù)距離的遠(yuǎn)近將數(shù)據(jù)集中的樣本點(diǎn)劃分成了三個(gè)類簇，并分別用不同的顏色和標(biāo)記（+，o，*）表示，質(zhì)心點(diǎn)由“?”表示。4.3K最近鄰算法

K最近鄰算法4.3.1K最近鄰算法的原理KNN（k-NearestNeighbor），就是K最近鄰算法，這是一種常用的監(jiān)督學(xué)習(xí)方法。該方法的思路非常簡(jiǎn)單直觀：如果一個(gè)樣本在特征空間中的K個(gè)最相似（即特征空間中最鄰近）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，即“物以類聚，人以群分”。K最近鄰算法概述如圖所示K最近鄰算法概述圖4.3K最近鄰算法

K最近鄰算法4.3.1K最近鄰算法的原理K-Means算法與KNN算法的區(qū)別K-Means算法K-Means算法是無(wú)監(jiān)督學(xué)習(xí)，沒有樣本的輸出K-Means算法有很明顯的訓(xùn)練過(guò)程，需要訓(xùn)練選擇質(zhì)心KNN算法是監(jiān)督學(xué)習(xí)，有分類的輸出KNN算法基本沒有訓(xùn)練過(guò)程，其原理是根據(jù)測(cè)試集的結(jié)果選擇距離訓(xùn)練集前k個(gè)最近的值KNN算法4.3K最近鄰算法

K最近鄰算法4.3.1K最近鄰算法的原理KNN算法實(shí)現(xiàn)過(guò)程模型三要素距離度量k值分類決策規(guī)則首先，隨機(jī)選擇k個(gè)對(duì)象，所選擇的每個(gè)對(duì)象都代表一個(gè)組的初始均值或初始的組中心值，對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)組初始均值的距離，將他們分配各最近的（最相似）小組其次，重新計(jì)算每個(gè)小組新的均值最后，這個(gè)過(guò)程不斷重復(fù)，直到所有的對(duì)象在K組分布中都找到離自己最近的組4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)實(shí)例基于六條測(cè)井曲線，對(duì)巖性進(jìn)行劃分，訓(xùn)練集如圖所示訓(xùn)練集由3300個(gè)深度的測(cè)井曲線以及對(duì)應(yīng)的巖性分類組成。則每一個(gè)深度看作一個(gè)樣本，測(cè)井曲線的數(shù)值作為屬性、巖性作為分類結(jié)果。367個(gè)深度的測(cè)井曲線以及對(duì)應(yīng)的巖性分類作為測(cè)試集，測(cè)試建立的模型性能?；诹鶙l測(cè)井曲線數(shù)據(jù)構(gòu)建一個(gè)KNN模型，用于巖性類型劃分?jǐn)?shù)據(jù)目的基于測(cè)井?dāng)?shù)據(jù)的巖性識(shí)別結(jié)果示意圖4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)1）數(shù)據(jù)導(dǎo)入4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)2）建立使用訓(xùn)練數(shù)據(jù)集構(gòu)造KDTree4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)3）尋找測(cè)試集K個(gè)鄰居使用KDTree結(jié)構(gòu)體MDI，得到n,

n為樣本數(shù)x鄰居數(shù)的矩陣，每一行對(duì)應(yīng)一個(gè)測(cè)試樣本，這一行的所有元素代表最鄰近的訓(xùn)練集樣本點(diǎn)的索引。4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)4）循環(huán)提取測(cè)試集樣本對(duì)應(yīng)鄰居循環(huán)提取測(cè)試樣本的鄰居，并統(tǒng)計(jì)眾數(shù)進(jìn)行投票，得到最終分類結(jié)果。使用validate計(jì)算最終的準(zhǔn)確率分類。其中mode用于計(jì)算最近鄰點(diǎn)分類向量tempClass中的眾數(shù)。4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)5）對(duì)K進(jìn)行優(yōu)化調(diào)參將以上過(guò)程封裝為函數(shù)myKNNCLass，將k作為參數(shù)進(jìn)行調(diào)參，由于需要使用眾數(shù)作為結(jié)果，因此鄰居數(shù)應(yīng)該選擇為奇數(shù)。4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實(shí)現(xiàn)得到結(jié)果取近鄰數(shù)K=1;此時(shí)的準(zhǔn)確率為90.9836%取近鄰數(shù)K=3;此時(shí)的準(zhǔn)確率為87.9781%取近鄰數(shù)K=5;此時(shí)的準(zhǔn)確率為84.153%取近鄰數(shù)K=7;此時(shí)的準(zhǔn)確率為84.9727%取近鄰數(shù)K=9;此時(shí)的準(zhǔn)確率為82.2404%取近鄰數(shù)K=11;此時(shí)的準(zhǔn)確率為80.0546%取近鄰數(shù)K=13;此時(shí)的準(zhǔn)確率為79.235%取近鄰數(shù)K=15;此時(shí)的準(zhǔn)確率為77.8689%，則最后使用取近鄰數(shù)1為最好。4.3K最近鄰算法

K最近鄰算法4.3.3鳶尾花分類案例分析Iris也稱鳶尾花卉數(shù)據(jù)集，是一類多重變量分析的數(shù)據(jù)集鳶尾花有3個(gè)亞屬，分別為山鳶尾（Iris-setosa）、變色鳶尾（Iris-versicolor）和維吉尼亞鳶尾（Iris-virginica）數(shù)據(jù)集包含150個(gè)數(shù)據(jù)樣本，分為3類，每類50個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)包含4個(gè)屬性可通過(guò)花萼長(zhǎng)度，花萼寬度，花瓣長(zhǎng)度，花瓣寬度4個(gè)屬性預(yù)測(cè)鳶尾花卉分別屬于三個(gè)亞屬中的哪一類列名說(shuō)明數(shù)據(jù)類型SepalLength花萼長(zhǎng)度FloatSepalWidth花萼寬度FloatPetalLength花瓣長(zhǎng)度FloatPetalWidth花瓣寬度FloatClass類別變量。0表示山鳶尾，1表示變色鳶尾，2表示維吉尼亞鳶尾。Int鳶尾花數(shù)據(jù)集特征4.3K最近鄰算法

K最近鄰算法4.3.3鳶尾花分類案例分析不同特征描述下鳶尾花分布4.3K最近鄰算法

K最近鄰算法4.3.3鳶尾花分類案例分析K近鄰學(xué)習(xí)的工作機(jī)制給定測(cè)試樣本，基于某種距離度量找出訓(xùn)練集中與其最靠近的K個(gè)訓(xùn)練樣本，然后基于這K個(gè)“鄰居”的信息來(lái)進(jìn)行預(yù)測(cè)。示例代碼如圖4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理傳統(tǒng)的聚類分析是一種硬劃分（CrispPartition），它把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某類中，具有“非此即彼”的性質(zhì)。然而實(shí)際上大多數(shù)對(duì)象并沒有嚴(yán)格的屬性，它們?cè)谛再|(zhì)和類屬方面存在著中介性，具有“亦此亦彼”的性質(zhì)，因此適合進(jìn)行軟劃分。Zadeh提出的模糊集理論為這種軟劃分提供了有力的分析工具，用模糊方法來(lái)處理聚類問題，稱之為模糊聚類分析。模糊聚類得到了樣本屬于各個(gè)類別的不確定性程度，表達(dá)了樣本類屬的中介性，建立起了樣本對(duì)于類別的不確定性的描述，能更客觀地反映現(xiàn)實(shí)世界，從而成為聚類分析研究的主流。在基于目標(biāo)函數(shù)的聚類算法中模糊C均值（FuzzyC-Means,FCM）類型算法的理論最為完善，應(yīng)用最為廣泛。4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值聚類的準(zhǔn)則設(shè)xi(i=1,2,…,n)是n個(gè)樣本組成的樣本集合，c為預(yù)定的類別數(shù)目，μj(xi)是第i個(gè)樣本對(duì)于第j類的隸屬度函數(shù)。用隸屬度函數(shù)定義的聚類損失函數(shù)可以寫為：其中，b>1是一個(gè)可以控制聚類結(jié)果的模糊程度的常數(shù)。在不同的隸屬度定義方法下最小化聚類損失函數(shù)，就得到不同的模糊聚類方法。其中最有代表性的是模糊C均值方法，它要求一個(gè)樣本對(duì)于各個(gè)聚類的隸屬度之和為1，即（i=1,2,…,n）4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值算法步驟設(shè)置目標(biāo)函數(shù)的精度e，模糊指數(shù)b（b通常取2）和算法最大迭代次數(shù)初始化隸屬度矩陣μij和聚類中心vi由公式更新模糊劃分矩陣μij和聚類中心vi根據(jù)所得到的隸屬度矩陣，取樣本隸屬度最大值所對(duì)應(yīng)類作為樣本聚類的結(jié)果，聚類結(jié)束若目標(biāo)函數(shù)|J(t)-J(t+1)|<e則迭代結(jié)束，否則跳轉(zhuǎn)執(zhí)行步驟3123454.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值算法優(yōu)缺點(diǎn)FCM算法優(yōu)越于傳統(tǒng)硬C均值聚類算法在于隸屬度可以連續(xù)取值于[0,1]區(qū)間，考慮到了樣本屬于各個(gè)類的“亦此亦彼”性，能夠?qū)︻惻c類之間樣本有重疊的數(shù)據(jù)集進(jìn)行分類，具有良好的收斂性。而且FCM算法復(fù)雜度低，易于實(shí)現(xiàn)。優(yōu)點(diǎn)如目標(biāo)函數(shù)在迭代過(guò)程中容易陷入局部最小、函數(shù)收斂速度慢、對(duì)初始值、噪聲比較敏感等問題。缺點(diǎn)4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實(shí)現(xiàn)數(shù)據(jù)集由400個(gè)二維平面上的點(diǎn)組成，這些點(diǎn)構(gòu)成4個(gè)集合，但彼此之間沒有明顯的極限。數(shù)據(jù)集示例如圖數(shù)據(jù)集分布4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實(shí)現(xiàn)模糊C均值代碼4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實(shí)現(xiàn)數(shù)據(jù)集分布4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟基本思路用電特征提取模型的構(gòu)建聚類個(gè)數(shù)確定4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟1）基本思路模糊C均值聚類分析的基本思路是通過(guò)不斷優(yōu)化目標(biāo)函數(shù)來(lái)獲得各樣本點(diǎn)對(duì)于所有聚類中心的隸屬度，進(jìn)而確定樣本點(diǎn)的類屬，最終達(dá)到自動(dòng)對(duì)樣本數(shù)據(jù)聚類的目的。4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟2）模型的構(gòu)建本文提出的用電需求分類預(yù)測(cè)模型。首先把數(shù)據(jù)按不同的行為特征分成n個(gè)類，其結(jié)果是一組n個(gè)具有不同輸入輸出的數(shù)據(jù)集。其次對(duì)每個(gè)數(shù)據(jù)集建立起相應(yīng)的模型。最后對(duì)預(yù)測(cè)結(jié)果進(jìn)行匯總。模型框架結(jié)構(gòu)如下圖所示?；谀：鼵均值聚類的方法建立了居民中期用電需求分類預(yù)測(cè)模型。4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟2）模型的構(gòu)建分類負(fù)荷預(yù)測(cè)模型框架4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟3）用電特征提取特征提取主要包括聚類屬性選擇與預(yù)測(cè)輸入變量提取2個(gè)部分提取了各用戶日均用電量、月電量達(dá)到第2檔的比例、月電量達(dá)到第3檔的比例與高溫敏感性4組聚類屬性所有預(yù)測(cè)模型的輸入變量主要提取出過(guò)去7天的用電量與當(dāng)天的氣溫共計(jì)8個(gè)輸入屬性分檔月用電量電價(jià)/（元?kWh-1）第1檔200kWh以下0.4983第2檔201-400kWh0.5483第3檔400kWh以上0.7983福建省居民生活用電價(jià)格表4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟4）聚類個(gè)數(shù)確定最佳聚類個(gè)數(shù)確定的流程圖如圖所示。4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟4）聚類個(gè)數(shù)確定為了客觀地確定合適的聚類個(gè)數(shù)，本文主要通過(guò)計(jì)算每一個(gè)試探類別數(shù)的誤差平方（SSE）和MeanIndexAdequacy（MIA）值，通過(guò)對(duì)比分析找出最優(yōu)的聚類個(gè)數(shù)參數(shù)。SSE和MIA計(jì)算公式如下。4.