聚類分析簡介原理與應(yīng)用

聚類分析陳龍震聚類分析聚類分析的簡介Q型聚類統(tǒng)計(jì)量——距離R型聚類統(tǒng)計(jì)量——相似系數(shù)系統(tǒng)聚類動態(tài)聚類——k均值聚類其他聚類分析的定義聚類分析是研究如何研究對象(樣品或變量)按照多個方面的特征進(jìn)行綜合分類的一種多元統(tǒng)計(jì)方法，它是根據(jù)物以類聚的原理將相似的樣品(或變量)歸為一類。聚類和分類有什么區(qū)別？無監(jiān)督學(xué)習(xí)與分類判別不同，進(jìn)行聚類前并不知道將要劃分成幾個組和什么樣的組，也不知道根據(jù)哪些空間區(qū)分規(guī)則來定義組商業(yè)聚類分析被用來發(fā)現(xiàn)不同的客戶群，并且通過購買模式刻畫不同的客戶群的特征。聚類分析是細(xì)分市場的有效工具，同時(shí)也可用于研究消費(fèi)者行為，尋找新的潛在市場、選擇實(shí)驗(yàn)的市場，并作為多元分析的預(yù)處理。聚類分析——主要應(yīng)用聚類分析——主要應(yīng)用生物聚類分析被用來動植物分類和對基因進(jìn)行分類，獲取對種群固有結(jié)構(gòu)的認(rèn)識Q型聚類統(tǒng)計(jì)量與R型聚類統(tǒng)計(jì)量設(shè)有容量為n的樣本觀測數(shù)據(jù),觀測矩陣為：樣本變量Q型聚類R型聚類變量之間的聚類即R型聚類分析，常用相似系數(shù)來測度變量之間的親疏程度。樣品之間的聚類即Q型聚類分析，常用距離來測度樣品之間的親疏程度。Q型聚類統(tǒng)計(jì)量——距離明氏距離測度明考夫斯基(Minkowski)距離設(shè)

和是第i和j個樣品的觀測值，則二者之間的距離為：當(dāng)

時(shí)，絕對值距離當(dāng)

時(shí)，歐氏距離當(dāng)

時(shí)，切比雪夫距離記切比雪夫距離證明Q型聚類統(tǒng)計(jì)量——距離國際象棋棋盤上二個位置間的切比雪夫距離是指王要從一個位子移至另一個位子需要走的步數(shù)。由于王可以往斜前或斜后方向移動一格，因此可以較有效率的到達(dá)目的的格子。上圖是棋盤上所有位置距f6位置的切比雪夫距離。Q型聚類統(tǒng)計(jì)量——距離明氏距離兩個缺點(diǎn)：明氏距離的值與各指標(biāo)的量綱有關(guān)明氏距離的定義沒有考慮各個變量之間的相關(guān)性和重要性。

明氏距離是把各個變量都同等看待，將兩個樣品在各個變量上的離差簡單地進(jìn)行了綜合。蘭氏距離馬氏距離Q型聚類統(tǒng)計(jì)量——距離這是印度著名統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(P．C．Mahalanobis)所定義的一種距離，其計(jì)算公式為：分別表示第i個樣品和第j樣品的p指標(biāo)觀測值所組成的列向量，即樣本數(shù)據(jù)矩陣中第i個和第j個行向量的轉(zhuǎn)置，

表示觀測變量之間的協(xié)方差短陣。在實(shí)踐應(yīng)用中，若總體協(xié)方差矩陣

未知，則可用樣本協(xié)方差矩陣作為估計(jì)代替計(jì)算。R型聚類統(tǒng)計(jì)量——相似系數(shù)相似系數(shù)設(shè)和是第和個樣品的觀測值，則二者之間的相似測度為:R型聚類統(tǒng)計(jì)量——夾角余弦夾角余弦夾角余弦時(shí)從向量集合的角度所定義的一種測度變量之間親疏程度的相似系數(shù)。設(shè)在n維空間的向量問題馬（歐）氏距離和余弦相似度的區(qū)別問題適用于何種不同的數(shù)據(jù)分析模型歐氏距離能夠體現(xiàn)個體數(shù)值特征的絕對差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值不敏感，更多的用于使用用戶對內(nèi)容評分來區(qū)分用戶興趣的相似度和差異，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問題（因?yàn)橛嘞蚁嗨贫葘^對數(shù)值不敏感）商品1商品2用戶133用戶255問題Q型與R型聚類區(qū)別？Q型聚類：當(dāng)聚類把所有的觀測記錄（cases）進(jìn)行分類時(shí)，它把性質(zhì)相似的觀測分在同一個類，性質(zhì)差異較大的觀測分在不同的類。R型聚類：當(dāng)聚類把變量（variables）作為分類對象時(shí)。這種聚類用在變量數(shù)目比較多、且相關(guān)性比較強(qiáng)的情形，目的是將性質(zhì)相近的變量聚類為同一個類，并從中找出代表變量，從而減少變量個數(shù)以達(dá)到降維的效果。系統(tǒng)聚類凝聚的：從點(diǎn)作為個體簇開始，每一步合并兩個最接近的簇。這需要定義簇的臨近性(類間距離)的概念。分裂的：從包含所有點(diǎn)的某個簇開始，每一步分裂一個簇，直到剩下單點(diǎn)簇。在這種情況下，我們需要確定我每一步分裂那個簇，以及如何分裂。系統(tǒng)聚類——方法最短距離法設(shè)兩個類，分別含有n1和n2個樣本點(diǎn)系統(tǒng)聚類——方法若某步聚類將

和

合并為新類,即,新類與其他類

間的距離遞推公式為

系統(tǒng)聚類——方法最長距離法設(shè)兩個類，分別含有n1和n2個樣本點(diǎn)系統(tǒng)聚類——方法若某步聚類將

和

合并為新類,即,新類與其他類

間的距離遞推公式為

系統(tǒng)聚類——方法重心法重心距離：兩類中心分別為，則系統(tǒng)聚類——方法類平均法遞推公式：推導(dǎo)：系統(tǒng)聚類——方法離差平方和設(shè)將n個樣品分成k類G1，G2，…，Gk，用Xit表示Gt中的第I個樣品，nt表示Gt中樣品的個數(shù)，是Gt的重心，則Gt的樣品離差平方和為系統(tǒng)聚類——方法遞推公式上述的各種類間距離定義的遞推公式可以統(tǒng)一成如下公式系統(tǒng)聚類書：175頁例子系統(tǒng)聚類——類的個數(shù)確定給定閾值：通過觀測聚類圖，給出一個合適的閾值T。要求類與類之間的距離不要超過T值。例如我們給定T=0.3，當(dāng)聚類時(shí)，類間的距離已經(jīng)超過了0.3，則聚類結(jié)束。系統(tǒng)聚類——半偏相關(guān)半偏相關(guān)統(tǒng)計(jì)量其中T是數(shù)據(jù)的總離差平方和，是組內(nèi)離差平方和。

比較大，說明分G個類時(shí)類內(nèi)的離差平方和比較小，也就是說分G類是合適的。但是，分類越多，每個類的類內(nèi)的離差平方和就越小，也就越大；所以我們只能取合適的G，使得足夠大，而G本身很小，隨著G的增加，的增幅不大。比如，假定分4類時(shí)，=0.8；下一次合并分3類時(shí),下降了許多，=0.32，則分4類是合適的。系統(tǒng)聚類——半偏相關(guān)系統(tǒng)聚類——偽F統(tǒng)計(jì)量偽F統(tǒng)計(jì)量偽F統(tǒng)計(jì)量用于評價(jià)聚為G類的效果。如果聚類的效果好，類間的離差平方和相對于類內(nèi)的離差平方和大，所以應(yīng)該取偽F統(tǒng)計(jì)量較大而類數(shù)較小的聚類水平。其中T是數(shù)據(jù)的總離差平方和，

是類內(nèi)離差平方和系統(tǒng)聚類——偽F統(tǒng)計(jì)量

偽統(tǒng)計(jì)量的定義為其中和分別是的類內(nèi)離差平方和，是將K和L合并為第M類的離差平方和

=--為合并導(dǎo)致的類內(nèi)離差平方和的增量。用它評價(jià)合并第K和L類的效果，偽統(tǒng)計(jì)量大說明不應(yīng)該合并這兩類，應(yīng)該取合并前的水平。系統(tǒng)聚類——偽統(tǒng)計(jì)量系統(tǒng)聚類——CCC統(tǒng)計(jì)量立方聚類準(zhǔn)則其中

，v是方差穩(wěn)定化變換，一般取值為一般由

維空間的均勻分布得到。一般選擇

后的第一個局部極大值點(diǎn)對應(yīng)的分類數(shù)。系統(tǒng)聚類——CCC統(tǒng)計(jì)量系統(tǒng)聚類法的基本性質(zhì)

在聚類分析過程中，并類距離分別為lk（k=1，2，3，…

）若滿足，則稱該聚類方法具有單調(diào)性。除了重心法和中間距離法之外，其他的系統(tǒng)聚類法均滿足單調(diào)性的條件。單調(diào)性系統(tǒng)聚類法的基本性質(zhì)空間的濃縮和擴(kuò)張?jiān)O(shè)有兩種系統(tǒng)聚類法A和B，他們在第i步的距離矩陣分別為Ai和Bi（I=1，2，3…），若Ai>Bi，則稱第一種方法A比第二種方法B使空間擴(kuò)張，或第二種方法比第一種方法濃縮。

D（短）D（平），D（重）D（平）；D（長）

D（平）；方法的比較類平均法適中系統(tǒng)聚類局限樣品一旦劃到某個類以后就不變了，這要求分類方法比較準(zhǔn)確樣品數(shù)n很大時(shí)，系統(tǒng)聚類法的計(jì)算很龐大，從而使其不方便應(yīng)用動態(tài)聚類解決的問題是：假如有個樣本點(diǎn)，要把它們分為類，使得每一類內(nèi)的元素都是聚合的，并且類與類之間還能很好地區(qū)別開。動態(tài)聚類使用于大型數(shù)據(jù)。動態(tài)聚類步驟動態(tài)聚類——凝聚點(diǎn)選擇憑經(jīng)驗(yàn)選擇，如果對問題已經(jīng)有一定的了解，可將所有的的樣品大致分類，在每類選擇一個有代表性的樣品作為聚類點(diǎn)將所有的樣品隨機(jī)地分成k類，計(jì)算每一類的均值，將這些均值作為凝聚點(diǎn)采用最大最小原則，假設(shè)樣品最終分為k類，先選擇所有樣品中相距最遠(yuǎn)的兩個樣品為凝聚點(diǎn)，即選擇

，使.選擇第三個凝聚點(diǎn)

與前面兩個聚類點(diǎn)的距離最小者等于所有其余的樣品與

的最小距離中最大的。動態(tài)聚類——k均值聚類動態(tài)聚類——k均值聚類不足凝聚點(diǎn)選擇不當(dāng)動態(tài)聚類——k均值聚類不足不同的簇動態(tài)聚類——k均值聚類不足離群點(diǎn)其他基于劃分聚類算法（partitionclustering)k-means：是一種典型的劃分聚類算法，它用一個聚類的中心來代表一個簇，即在迭代過程中選擇的聚點(diǎn)不一定是聚類中的一個點(diǎn)，該算法只能處理數(shù)值型數(shù)據(jù)k-modes：K-Means算法的擴(kuò)展，采用簡單匹配方法來度量分類型數(shù)據(jù)的相似度k-prototypes：結(jié)合了K-Means和K-Modes兩種算法，能夠處理混合型數(shù)據(jù)k-medoids：在迭代過程中選擇簇中的某點(diǎn)作為聚點(diǎn)，PAM是典型的k-medoids算法CLARA：CLARA算法在PAM的基礎(chǔ)上采用了抽樣技術(shù)，能夠處理大規(guī)模數(shù)據(jù)CLARANS：CLARANS算法融合了PAM和CLARA兩者的優(yōu)點(diǎn)，是第一個用于空間數(shù)據(jù)庫的聚類算法FocusedCLARAN：采用了空間索引技術(shù)提高了CLARANS算法的效率PCM：模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法其他基于密度聚類算法：DBSCAN：DBSCAN算法是一種典型的基于密度的聚類算法，該算法采用空間索引技術(shù)來搜索對象的鄰域，引入了“核心對象”和“密度可達(dá)”等概念，從核心對象出發(fā)，把所有密度可達(dá)的對象組成一個簇GDBSCAN：算法通過泛化DBSCAN算法中鄰域的概念，以適應(yīng)空間對象的特點(diǎn)DBLASD：OPTICS：OPTICS算法結(jié)合了聚類的自動性和交互性，先生成聚類的次序，可以對不同的聚類設(shè)置不同的參數(shù)，來得到用戶滿意的結(jié)果FDC：FDC算法通過構(gòu)造k-dtree把整個數(shù)據(jù)空間劃分成若干個矩形空間，當(dāng)空間維數(shù)較少時(shí)可以大大提高DBSCAN的效率其他基于層次聚類算法：CURE：采用抽樣技術(shù)先對數(shù)據(jù)集D隨機(jī)抽取樣本，再采用分區(qū)技術(shù)對樣本進(jìn)行分區(qū)，然后對每個分區(qū)局部聚類，最后對局部聚類進(jìn)行全局聚類ROCK：也采用了隨機(jī)抽樣技術(shù)，該算法在計(jì)算兩個對象的相似度時(shí)，同時(shí)考慮了周圍對象的影響CHEMALOEN（變色龍算法）：首先由數(shù)據(jù)集構(gòu)造成一個K-最近鄰圖Gk,再通過一個圖的劃分算法將圖Gk劃分成大量的子圖,每個子圖代表一個初始子簇,最后用一個凝聚的層次聚類算法反復(fù)合并子簇，找到真正的結(jié)果簇SBAC：SBAC算法則在計(jì)算對象間相似度時(shí)，考慮了屬性特征對于體現(xiàn)對象本質(zhì)的重要程度，對于更能體現(xiàn)對象本質(zhì)的屬性賦予較高的權(quán)值BIRCH：BIRCH算法利用樹結(jié)構(gòu)對數(shù)據(jù)集進(jìn)行處理，葉結(jié)點(diǎn)存儲一個聚類，用中心和半徑表示，順序處理每一個對象，并把它劃分到距離最近的結(jié)點(diǎn)，該算法也可以作為其他聚類算法的預(yù)處理過程BUBBLE：BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間BUBBLE-FM：BUBBLE-FM算法通過減少距離的計(jì)算次數(shù)，提高了BUBBLE算法的效率其他STING：利用網(wǎng)格單元保存數(shù)據(jù)統(tǒng)計(jì)信息，從而實(shí)現(xiàn)多分辨率的聚類WaveCluster：在聚類分析中引入了小波變換的原理，主要應(yīng)用于信號處理領(lǐng)域。（備注：小波算法在信號處理，圖形圖像，加密解密等領(lǐng)域有重要應(yīng)用，是一種比較高深和牛逼的東西）CLIQUE：是一種結(jié)合了網(wǎng)格和密度的聚類算法OPTIGRID：基于網(wǎng)格的聚類算法：基于統(tǒng)計(jì)學(xué)的聚類算法：COBWeb：COBWeb是一個通用的概念聚類方法，它用分類樹的形式表現(xiàn)層次聚類CLASSIT：AutoClass：是以概率混合模型為基礎(chǔ)，利用屬性的概率分布來描述聚類，該方法能夠處理混合型的數(shù)據(jù)，但要求各屬性相互獨(dú)立R軟件與聚類分析在R軟件中，dist()函數(shù)給出了各種距離的計(jì)算結(jié)果，其使用格式是其中x是樣本構(gòu)