聚类 高维聚类 聚类评估标准 EM模型聚类
高維數據的聚類分析
高維聚類研究方向
高維數據聚類的難點在于：
1、適用于普通集合的聚類算法，在高維數據集合中效率極低
2、由于高維空間的稀疏性以及最近鄰特性，高維的空間中基本不存在數據簇。
?在高維聚類的研究中有如下幾個研究重點：
1）維度約簡，主要分為特征變換和特征選擇兩大類。前者是對特征空間的變換映射，常見的有PCA、SVD等。后者則是選擇特征的子集，常見的搜索方式有自頂向下、隨機搜索等；（降維）
2）高維聚類算法，主要分為高維全空間聚類和子空間聚類算法。前者的研究主要聚焦在對傳統聚類算法的優化改進上，后者則可以看做維度約簡的推廣；
子空間聚類：
特征選擇算法綜述：http://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html
不同的簇對應不同的子空間，并且每個子空間維數不同，因此也不可能一個子空間就可以發現所有的簇。選取與給定簇密切相關的維，然后在對應的子空間進行聚類。子空間聚類需要自定義一種搜索策略和評測標準來篩選出需要聚類的簇
傳統的特征選擇算法可以用來確定相關維。
CLIQUE算法（綜合了基于密度和基于網格的算法）
CLIQUE把每個維劃分成不重疊的區間，從而把數據對象的整個嵌入空間劃分成單元。它使用一個密度閾值識別稠密單元和稀疏單元。如果映射到它的對象數超過該密度閾值，則這個單元是稠密的。
CLIQUE通過兩個階段進行聚類。在第一階段，CLIQUE把d-維數據空間劃分若干互不重疊的矩形單元，并且從中識別出稠密單元。CLIQUE在所有的子空間中發現稠密單元。
為了做到這一點，CLIQUE把每個維都劃分成區間，并識別至少包含l個點的區間，其中l是密度閾值。
然后，CLIQUE迭代地連接子空間.CLIQUE檢查中的點數是否滿足密度閾值。
當沒有候選產生或候選都不稠密時，迭代終止。
在第二階段中，CLIQUE使用每個子空間中的稠密單元來裝配可能具有任意形狀的簇。其思想是利用最小描述長度（MDL)原理,使用最大區域來覆蓋連接的稠密單元，其中最大區域是一個超矩形，落人該區域中的每個單元都是稠密的，并且該區域在該子空間的任何維上都不能再擴展。一般地找出簇的最佳描述是NP一困難的。因此，CLIQUE采用了一種簡單的貪心方法。它從一個任意稠密單元開始，找出覆蓋該單元的最大區域，然后在尚未被覆蓋的剩余的稠密單元上繼續這一過程。當所有稠密單元都被覆蓋時，貪心方法終止。
簡單說：
?對每個屬性進行?N等分,?整個數據空間就被劃分為一個超長方體集合,?對每個單元進行數據點計數,?大于某個閾值?S?的單元稱為稠密單元,?然后對稠密單元進行連接就構成類.?不同于其它方法,?它可以自動地識別嵌入在數據子空間中的類
子空間聚類與基于降維的聚類對比
子空間聚類從某種程度上來講與基于降維的聚類有些類似，但后者是通過直接的降維來對高維數據進行預處理，即在降維之后的某一個特定的低維空間中進行聚類處理；而前者是把高維數據劃分成若干不同的子空間，再根據需要在不同的子空間中尋求數據的聚類。
子空間聚類算法拓展了特征選擇的任務，嘗試在相同數據集的不同子空間上發現聚類。和特征選擇一樣，子空間聚類需要使用一種搜索策略和評測標準來篩選出需要聚類的簇，不過考慮到不同簇存在于不同的子空間，需要對評測標準做一些限制。
3）聚類有效性，是對量化評估方法的研究；
基于降維的聚類從根本上說都是以數據之間的距離 或相似度評價為聚類依據，當數據的維數不是很高時，這些方法效果較好，但當數據維度增高，聚類處理將很難達到預期的 效果。 原因在于：
ａ）在一個很高維的空間中定義一個距離度量本身就是一個很困難的事情；
ｂ）基于距離的方法通常需要計算各個聚類之間的距離均值，當數據的維度很高時，不同聚類之間的距離差異將會變得很小。
4）聚類結果表示方法；
5）高維數據索引結構；
6）高維離群點的研究
?
筆記︱多種常見聚類模型以及分群質量評估（聚類注意事項、使用技巧）
一、聚類分析的距離問題
聚類分析的目的就是讓類群內觀測的距離最近，同時不同群體之間的距離最大。
1.樣本聚類距離以及標準化
幾種常見的距離，歐氏距離、絕對值距離、明氏距離、馬氏距離。與前面不同的是，概率分布的距離衡量，K-L距離代表P、Q概率分布差的期望。
一般來說，聚類分析的數據都會進行標準化，標準化是因為聚類數據會受數據的量綱影響。
在以上的幾個距離明氏距離受量綱影響較大。馬氏距離受量綱影響較小
還有cos(余弦相似性)余弦值的范圍在[-1,1]之間，值越趨近于1，代表兩個向量的方向越趨近于0，他們的方向更加一致。相應的相似度也越高（cos距離可以用在文本挖掘，文本詞向量距離之上）。
幾種標準化的方法，有規范化、標準化（R語言︱數據規范化、歸一化）
?
2.不同類型變量距離計算?
算法雜貨鋪——k均值聚類(K-means)
1、標量：歐幾里得距離??曼哈頓距離??閔可夫斯基距離 標準化
????? 標量也就是無方向意義的數字，也叫標度變量。現在先考慮元素的所有特征屬性都是標量的情況。例如，計算X={2,1,102}和Y={1,3,2}的相異度。一種很自然的想法是用兩者的歐幾里得距離來作為相異度，歐幾里得距離的定義如下：
?????
????? 其意義就是兩個元素在歐氏空間中的集合距離，因為其直觀易懂且可解釋性強，被廣泛用于標識兩個標量元素的相異度。將上面兩個示例數據代入公式，可得兩者的歐氏距離為：
?????
????? 除歐氏距離外，常用作度量標量相異度的還有曼哈頓距離和閔可夫斯基距離，兩者定義如下：
????? 曼哈頓距離：
????? 閔可夫斯基距離：
????? 歐氏距離和曼哈頓距離可以看做是閔可夫斯基距離在p=2和p=1下的特例。另外這三種距離都可以加權，這個很容易理解，不再贅述。
????? 下面要說一下標量的規格化問題。上面這樣計算相異度的方式有一點問題，就是取值范圍大的屬性對距離的影響高于取值范圍小的屬性。例如上述例子中第三個屬性的取值跨度遠大于前兩個，這樣不利于真實反映真實的相異度，為了解決這個問題，一般要對屬性值進行規格化。所謂規格化就是將各個屬性值按比例映射到相同的取值區間，這樣是為了平衡各個屬性對距離的影響。通常將各個屬性均映射到[0,1]區間，映射公式為：
?????
????? 其中max(ai)和min(ai)表示所有元素項中第i個屬性的最大值和最小值。例如，將示例中的元素規格化到[0,1]區間后，就變成了X’={1,0,1}，Y’={0,1,0}，重新計算歐氏距離約為1.732。
2、二元變量：相同序位同值屬性的比例?Jaccard系數
????? 所謂二元變量是只能取0和1兩種值變量，有點類似布爾值，通常用來標識是或不是這種二值屬性。對于二元變量，上一節提到的距離不能很好標識其相異度，我們需要一種更適合的標識。一種常用的方法是用元素相同序位同值屬性的比例來標識其相異度。
????? 設有X={1,0,0,0,1,0,1,1}，Y={0,0,0,1,1,1,1,1}，可以看到，兩個元素第2、3、5、7和8個屬性取值相同，而第1、4和6個取值不同，那么相異度可以標識為3/8=0.375。一般的，對于二元變量，相異度可用“取值不同的同位屬性數/單個元素的屬性位數”標識。
????? 上面所說的相異度應該叫做對稱二元相異度。現實中還有一種情況，就是我們只關心兩者都取1的情況，而認為兩者都取0的屬性并不意味著兩者更相似。例如在根據病情對病人聚類時，如果兩個人都患有肺癌，我們認為兩個人增強了相似度，但如果兩個人都沒患肺癌，并不覺得這加強了兩人的相似性，在這種情況下，改用“取值不同的同位屬性數/(單個元素的屬性位數-同取0的位數)”來標識相異度，這叫做非對稱二元相異度。如果用1減去非對稱二元相異度，則得到非對稱二元相似度，也叫Jaccard系數，是一個非常重要的概念。
3、分類變量
????? 分類變量是二元變量的推廣，類似于程序中的枚舉變量，但各個值沒有數字或序數意義，如顏色、民族等等，對于分類變量，用“取值不同的同位屬性數/單個元素的全部屬性數”來標識其相異度。
4、序數變量：轉成標量
????? 序數變量是具有序數意義的分類變量，通常可以按照一定順序意義排列，如冠軍、亞軍和季軍。對于序數變量，一般為每個值分配一個數，叫做這個值的秩，然后以秩代替原值當做標量屬性計算相異度。
5、向量：余弦相似度
????? 對于向量，由于它不僅有大小而且有方向，所以閔可夫斯基距離不是度量其相異度的好辦法，一種流行的做法是用兩個向量的余弦度量，其度量公式為：
?????
????? 其中||X||表示X的歐幾里得范數。要注意，余弦度量度量的不是兩者的相異度，而是相似度！
?
3.群體聚類距離
前面是樣本之間的距離，如果是一個點集，群落，如何定義群體距離。一般有以下幾種距離。
?
二.EM聚類
KMEANS注意點
1.K均值聚類算法對離群值最敏感，因為它使用集群數據點的平均值來查找集群的中心。
在數據包含異常值、數據點在數據空間上的密度擴展具有差異、數據點為非凹形狀的情況下，K均值聚類算法的運行結果不佳。
2.K均值對簇中心初始化非常敏感。
?
高斯混合模型聚類算法
高斯混合模型GMMs Gaussian Mixture Models 高斯模型即正態分布，高斯混合模型就是幾個正態分布的疊加，每一個正態分布代表一個類別，所以和K-means 很像，高斯混合模型也可以用來做無監督的聚類分析。 ? 高斯混合模型聚類算法EM步驟如下：?注：當高斯混合模型的特征值維數大于一維時，在計算加權的時候還要計算協方差，即要考慮不同維度之間的相互關聯。
高斯混合模型和K-means的比較： ???????相同點：三.常見聚類模型的比較
| ? | K-means | 層次聚類 | EM模型聚類 |
| 優點 | 屬于快速聚類，計算效率高 | 1、能夠展現數據層次結構，易于理解 2、可以基于層次事后再選擇類的個數（根據數據選擇類，但是數據量大，速度慢） | 相比其他方法能夠擬合多種形狀的類 |
| 缺點 | 1、需要實現指定類的個數（需要指定類） 2、有時會不穩定，陷入局部收斂 | 1、計算量比較大，不適合樣本量大的情形 2、較多用于宏觀綜合評價 | 需要事先指定類的個數和初始分布 |
?
分群指標詳細說明：7.9 聚類模型評估
四.聚類分群的數量如何確定？分群效果如何評價？
沒有固定標準，一般會3-10分群。或者用一些指標評價，然后交叉驗證不同群的分群指標。
一般的指標：輪廓系數silhouette（-1,1之間，值越大，聚類效果越好）（fpc包），蘭德指數rand；R語言中有一個包用30種方法來評價不同類的方法（NbClust），但是速度較慢。既可以確定分群數量，也可以評價聚類質量
商業上的指標：分群結果的覆蓋率；分群結果的穩定性；分群結果是否從商業上易于理解和執行
1 . 蘭德指數 需要標簽
蘭德指數（Rand index）需要給定實際類別信息$C$，假設$K$是聚類結果，$a$表示在$C$與$K$中都是同類別的元素對數，$b$表示在$C$與$K$中都是不同類別的元素對數，則蘭德指數為：
${\rm RI}=\frac{a+b}{C_2^{n_{\rm samples}}}$，
對于以上公式，
- 分子：屬性一致的樣本數，即同屬于這一類或都不屬于這一類。a是真實在同一類、預測也在同一類的樣本數；b是真實在不同類、預測也在不同類的樣本數；
- 分母：任意兩個樣本為一類有多少種組合，是數據集中可以組成的總元素對數；
- RI取值范圍為[0,1]，值越大意味著聚類結果與真實情況越吻合。
對于隨機結果，RI并不能保證分數接近零。為了實現“在聚類結果隨機產生的情況下，指標應該接近零”，調整蘭德系數（Adjusted rand index）被提出，它具有更高的區分度：
${\rm ARI}=\frac{{\rm RI}-E[{\rm RI}]}{\max({\rm RI})-E[{\rm RI}]}$，
具體計算方式參見Adjusted Rand index。
ARI取值范圍為$[-1,1]$，值越大意味著聚類結果與真實情況越吻合。從廣義的角度來講，ARI衡量的是兩個數據分布的吻合程度。
2. 互信息?需要標簽、先驗知識
互信息（Mutual Information）也是用來衡量兩個數據分布的吻合程度。假設$U$與$V$是對$N$個樣本標簽的分配情況，則兩種分布的熵（熵表示的是不確定程度）分別為：
$H(U)=\sum\limits_{i=1}^{|U|}P(i)\log (P(i)), H(V)=\sum\limits_{j=1}^{|V|}P'(j)\log (P'(j))$，
其中$P(i)=|U_i|/N,P'(j)=|V_j|/N$。$U$與$V$之間的互信息（MI）定義為：
${\rm MI}(U,V)=\sum\limits_{i=1}^{|U|}\sum\limits_{j=1}^{|V|}P(i,j)\log\left ( \frac{P(i,j)}{P(i)P'(j)}\right )$，
其中$P(i,j)=|U_i\bigcap V_j|/N$。標準化后的互信息（Normalized mutual information）為：
${\rm NMI}(U,V)=\frac{{\rm MI}(U,V)}{\sqrt{H(U)H(V)}}$。
與ARI類似，調整互信息（Adjusted mutual information）定義為：
${\rm AMI}=\frac{{\rm MI}-E[{\rm MI}]}{\max(H(U), H(V))-E[{\rm MI}]}$。
利用基于互信息的方法來衡量聚類效果需要實際類別信息，MI與NMI取值范圍為$[0,1]$，AMI取值范圍為$[-1,1]$，它們都是值越大意味著聚類結果與真實情況越吻合。
3. 輪廓系數
輪廓系數旨在將某個對象與自己的簇的相似程度和與其他簇的相似程度進行比較。輪廓系數最高的簇的數量表示簇的數量的最佳選擇。
輪廓系數（Silhouette coefficient）適用于實際類別信息未知的情況。對于單個樣本，設$a$是與它同類別中其他樣本的平均距離，$b$是與它距離最近不同類別中樣本的平均距離，輪廓系數為：
$s=\frac{b-a}{\max(a,b)}$。
對于一個樣本集合，它的輪廓系數是所有樣本輪廓系數的平均值。
輪廓系數取值范圍是$[-1,1]$，同類別樣本越距離相近且不同類別樣本距離越遠，分數越高。
一般來說，平均輪廓系數越高，聚類的質量也相對較好。在這，對于研究區域的網格單元，最優聚類數應該是2，這時平均輪廓系數的值最高。但是，聚類結果（k=2）的 SSE 值太大了。當 k=6 時，SEE 的值會低很多，但此時平均輪廓系數的值非常高，僅僅比 k=2 時的值低一點。因此，k=6 是最佳的選擇。
五、kmeans時候出現的超級大群現象，如何解決？
?kmeans做聚類的時候，往往會出現一個超級大群，一類樣本數據很多很多，其他類別數量很少。兩極分化很嚴重。在實際使用的時候會出現以下這幾個問題：
80%的數據分布在1%的空間內，而剩下的20%的數據分布在99%的空間內。聚類時，分布在1%空間內的大部分數據會被聚為一類，剩下的聚為一類。當不斷增加K值時，模型一般是對99%空間內的數據不斷進行細分，因為這些數據之間的空間距離比較大。
? ? ? 而對分布在1%空間內的數據則很難進一步細分，或者即使細分了，也只是剝離出了外側少量數據。下圖是我們在某個項目中的聚類結果，可以看到有一類用戶占了90%以上，而且隨著K的增加，這類用戶里只有很小一部分數據會被劃分出來。
?
? ? ??解決辦法：那么為了解決這個問題，一種可行的方法是是對特征取LOG，減輕長尾問題。經過這兩種方法處理后，都能較好的對玩家進行分類。下圖是上圖中的數據點取LOG后得到的分布圖。
? ? ??缺點：取LOG的方法的缺點在于，會使數據變得不直觀，不好理解。
DBSCAN
k-dist
另外，DBSCAN要求用戶指定一個全局參數Eps(為了減少計算量，預先確定參數 Minpts)。為了確定取值，DBSCAN計算任意對象與它的第k個最臨近的對象之間的距離。然后，根據求得的距離由小到大排序，并繪出排序后的圖，稱做k-dist圖。k-dist圖中的橫坐標表示數據對象與它的第k個最近的對象間的距離；縱坐標為對應于某一k-dist距離值的數據對象的個數。
R-樹
為了有效地執行區域查詢，DBSCAN算法使用了空間查 詢R-樹結構。在進行聚類前，必須建立針對所有數據的R*-樹。
轉載于:https://www.cnblogs.com/34fj/p/9163578.html
總結
以上是生活随笔為你收集整理的聚类 高维聚类 聚类评估标准 EM模型聚类的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端基础-jQuery的事件的用法
- 下一篇： redis 数据类型、命令