大數據分析方法與應用第4章聚類算法4.1聚類的原理目錄CONTENTS4.2K-Means聚類4.3

K最近鄰算法4.4

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

聚類的原理聚類的一般過程01數據特征標準化和降維數據準備03通過對選擇的特征進行轉換形成新的突出特征特征提取02特征選擇04基于某種距離函數進行相似度度量，獲取簇聚類05分析聚類結果，如距離誤差等聚類結果評估從最初的特征中選擇最有效的特征，并將其存儲在向量中4.2K-Means聚類

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

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

K-Means聚類4.2.1K-Means聚類算法的原理數據對象集合S如下表所示，作為一個聚類分析的二維樣本，要求的簇的數量k=2O12345x001.555y20002數據對象集合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）對剩余的每個對象，根據其與各個簇中心的距離，將它賦給最近的簇a.

對于O3：

；

；

因為d(M1,O3)≥d(M2,O3)，故將O3分配給C2。b. 對于O4：

；

因為d(M1,O4)≥d(M2,O4)，故將O4分配給C2。c. 對于O5：

；

因為d(M1,O5)≤d(M2,O5)，故將O5分配給C1。綜上，得到新簇C1={O1,O5}，中心為M1=O1=(0,2)；C2={O2,O3,O4}，中心為M2=O2=(0,0)。計算平方誤差準則，單個方差為：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。總體平均方差是：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)重復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)。單個方差為：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，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。3）計算新簇的中心4.2

K-Means聚類

K-Means聚類4.2.1K-Means聚類算法的原理K-Means算法的主要優點是解決聚類問題的一種經典算法，簡單、快速;對處理大數據集，該算法是相對可伸縮和高效率的;k值可以根據實際需求自行調節，以達到控制類簇內樣本點數量的目的;當結果簇是密集的，而簇與簇之間區別明顯時，它的效果較好.4.2

K-Means聚類K-Means聚類4.2.1K-Means聚類算法的原理K-Means算法的主要缺點在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數據不適用;必須事先給出k（要生成的簇的數目），而且對初值敏感，對于不同的初始值，可能會導致不同結果。經常發生得到次優劃分的情況。解決方法是多次嘗試不同的初始值;它對于“噪聲”和孤立點數據是敏感的，少量的該類數據能夠對平均值產生極大的影響.4.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實現MATLAB提供了專用函數K-Means用于聚類的質心，默認為歐幾里得距離，如圖所示

MATLAB專用函數K-Means4.2

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

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實現依據下表中二維數據，通過MATLAB中K-Means算法，令K=3進行聚類。x23-121011540421211222y2010101231-1020212-110

K-Means算法代碼示例數據4.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實現K-Means算法代碼示例14.2

K-Means聚類K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實現K-Means算法代碼示例24.2

K-Means聚類

K-Means聚類4.2.2K-Means聚類算法在MATLAB中的實現聚類結果示意由右圖可知，K-Means根據距離的遠近將數據集中的樣本點劃分成了三個類簇，并分別用不同的顏色和標記（+，o，*）表示，質心點由“?”表示。4.3K最近鄰算法

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

K最近鄰算法4.3.1K最近鄰算法的原理K-Means算法與KNN算法的區別K-Means算法K-Means算法是無監督學習，沒有樣本的輸出K-Means算法有很明顯的訓練過程，需要訓練選擇質心KNN算法是監督學習，有分類的輸出KNN算法基本沒有訓練過程，其原理是根據測試集的結果選擇距離訓練集前k個最近的值KNN算法4.3K最近鄰算法

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

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現實例基于六條測井曲線，對巖性進行劃分，訓練集如圖所示訓練集由3300個深度的測井曲線以及對應的巖性分類組成。則每一個深度看作一個樣本，測井曲線的數值作為屬性、巖性作為分類結果。367個深度的測井曲線以及對應的巖性分類作為測試集，測試建立的模型性能。基于六條測井曲線數據構建一個KNN模型，用于巖性類型劃分數據目的基于測井數據的巖性識別結果示意圖4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現1）數據導入4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現2）建立使用訓練數據集構造KDTree4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現3）尋找測試集K個鄰居使用KDTree結構體MDI，得到n,

n為樣本數x鄰居數的矩陣，每一行對應一個測試樣本，這一行的所有元素代表最鄰近的訓練集樣本點的索引。4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現4）循環提取測試集樣本對應鄰居循環提取測試樣本的鄰居，并統計眾數進行投票，得到最終分類結果。使用validate計算最終的準確率分類。其中mode用于計算最近鄰點分類向量tempClass中的眾數。4.3K最近鄰算法

K最近鄰算法4.3.2K最近鄰算法在MATLAB中的實現5）對K進行優化調參將以上過程封裝為函數myKNNCLass，將k作為參數進行調參，由于需要使用眾數作為結果，因此鄰居數應該選擇為奇數。4.3K最近鄰算法

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

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

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

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

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

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

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

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值算法優缺點FCM算法優越于傳統硬C均值聚類算法在于隸屬度可以連續取值于[0,1]區間，考慮到了樣本屬于各個類的“亦此亦彼”性，能夠對類與類之間樣本有重疊的數據集進行分類，具有良好的收斂性。而且FCM算法復雜度低，易于實現。優點如目標函數在迭代過程中容易陷入局部最小、函數收斂速度慢、對初始值、噪聲比較敏感等問題。缺點4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實現數據集由400個二維平面上的點組成，這些點構成4個集合，但彼此之間沒有明顯的極限。數據集示例如圖數據集分布4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實現模糊C均值代碼4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的實現數據集分布4.4模糊C-均值算法

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

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟1）基本思路模糊C均值聚類分析的基本思路是通過不斷優化目標函數來獲得各樣本點對于所有聚類中心的隸屬度，進而確定樣本點的類屬，最終達到自動對樣本數據聚類的目的。4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟2）模型的構建本文提出的用電需求分類預測模型。首先把數據按不同的行為特征分成n個類，其結果是一組n個具有不同輸入輸出的數據集。其次對每個數據集建立起相應的模型。最后對預測結果進行匯總。模型框架結構如下圖所示。基于模糊C均值聚類的方法建立了居民中期用電需求分類預測模型。4.4模糊C-均值算法

模糊C-均值算法4.4.3用戶需求聚類案例分析分析步驟2）模型的構建分類負荷預測模型框架4.4模糊C-均值算法

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

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

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