【数据挖掘笔记十一】高级聚类分析
?
11.高級聚類分析
11.1?基于概率模型的聚類
研究一個對象屬于多個簇的聚類主題。
1）模糊簇
模糊集S是整體對象集X的一個子集，允許X中的每個對象都具有一個屬于S的0到1之間的隸屬度。給定對象的集合，一個簇就是對象的一個模糊集，這種簇就是模糊簇，一個聚類包含多個模糊簇。模糊聚類就是劃分模糊簇的過程。對象隸屬于模糊簇的隸屬度，可以用對象與其被指派到的簇的中心之間的距離或相似度來衡量。由于一個對象可能參與多個簇，用隸屬度加權的到簇中心的距離之和捕獲對象擬合聚類的程度。誤差平方和SSE可用來度量模糊聚類對數據集的擬合程度。模糊聚類也稱為軟聚類，允許一個對象屬于多個簇，和傳統的硬聚類強制每個對象互斥地僅屬于一個簇不同。
2）基于概率模型的聚類
聚類分析的目標是發現隱藏的類別。作為聚類分析主題的數據集可以看做隱藏的類別的可能實例的一個樣本，但沒有類標號。由聚類分析導出的簇使用數據集推斷，并且旨在逼近隱藏的類別。
從統計學上，可以假定隱藏的類別是數據空間上的一個分布，可以使用概率密度函數或分布函數精確地表示。這種隱藏的類別稱為概率簇。對于一個概率簇C，它的密度函數和數據空間的點o，f(o)是C的一個實例在o上出現的相對似然。假定概率粗符合某種分布，用數據集（觀測的數據）來學習到這種分布，捕獲潛在的類別。存在多個概率簇，也就是說觀測的對象集是由這些概率簇所生成的數據。給定數據集D和所要求的的簇數k，基于概率模型的聚類分析任務是推導出最有可能產生D的k個概率簇。
數據生成的過程，每個觀測對象都獨立地有兩步生成：首先，根據簇的概率選擇一個概率簇；然后根據選定簇的概率密度函數選擇一個樣本。
基于概率模型的聚類最終就歸結為求k個簇的概率密度函數的參數。如假定是高斯分布，則要求出均值和方差。
3）期望最大化算法
模糊聚類和基于概率模型的聚類都是通過EM算法來實現。EM算法是一種框架，逼近統計模型參數的最大似然或最大后驗估計。在模糊或基于概率模型的聚類情況下，EM算法從初始參數集出發，并且迭代直到不能改善聚類，即直到聚類收斂或改變充分小。
模糊聚類或基于概率模型的聚類的EM步驟：
第一：期望步，根據當前的模糊聚類或概率簇的參數，把對象指派到簇中；
第二：最大化步，發現新的聚類或參數，最大化模糊聚類的SSE或基于概率模型的聚類的期望似然。
總結：基于概率模型的聚類，使用合適的統計模型以捕獲潛在的簇。EM算法可能收斂不到最優解，而且可能收斂于局部極大，避免局部極大的啟發式方法，包括使用不同的隨機初始值，運行EM過程多次。對于分布很多或數據集只包含很少觀測數據點，則EM算法的計算開銷可能很大。
11.2?聚類高維數據
在高維空間中，傳統的距離度量可能被一些維上的噪聲所左右。和傳統的低維空間聚類不同，隱藏在高維空間中的簇通常非常小，如何為高維數據聚類創建一個合適的模型是主要出發點。
1）子空間聚類方法
子空間搜索方法為聚類搜索各種子空間。這里，簇是在子空間中彼此相似的對象的子集。相似性用傳統的方法度量，如距離或密度。
基于相關性的聚類方法，如使用PCA導出新的、不相關的維集合，然后在新的空間或它的子空間中挖掘簇。除PCA外，還可以使用Hough變換或分形維，都是空間變換技術。
2）雙聚類方法
雙聚類方法在基因表達和推薦系統中有應用。雙聚類是同時聚類對象和屬性，結果簇是雙簇，滿足：只有一個小對象集參與一個簇、一個簇只涉及少數屬性、一個對象可以參與多個簇或完全不參與任何簇、一個屬性可以被多個簇涉及或完全不被任何簇涉及。在含噪聲的數據中發現雙簇的方法主要有兩類：基于最優化的方法執行迭代搜索，在每個迭代中，具有最高顯著性得分的子矩陣被識別為雙簇，這一個過程在用戶指定的條件滿足時終止，考慮到計算開銷，通常使用貪心搜索，找到局部最優的雙簇，代表性算法是δ-簇；枚舉方法使用一個容忍閾值指定被挖掘的雙簇對噪聲的容忍度，并試圖枚舉所有滿足要求的雙簇的子矩陣，代表性算法是MaPle。
3）維歸約方法和譜聚類
聚類高維數據的維歸約方法是構造一個新的空間，而不是使用原數據空間的子空間。
譜聚類方法就是這種思想，對數據生成相似矩陣，在進行特征值分解，選擇前k個特征向量，然后在新空間聚類，之后投影回原數據。
11.3?聚類圖和網絡數據
在圖和網絡數據上的聚類分析提取有價值的知識和信息。圖和網絡數據，如偶圖、web搜索引擎、社會網絡等，值給出了對象（頂點）和它們之間的聯系（邊），沒有明確定義維和屬性，要在這上面進行聚類分析，存在相似性度量和有效聚類模型設計的量大挑戰。
相似性度量采用測地距和基于隨機游走的距離。
1）測地距：圖中兩個頂點之間距離的一種簡單度量是兩個頂點之間的最短路徑，兩個頂點之間的測地距就是兩個頂點之間最短路徑的邊數。
2）SimRank，基于隨機游走和結構情境的相似性，隨機游走是一個軌跡，由相繼的隨機步組成。基于結構情境的相似性的直觀意義是，圖中兩個頂點是相似的，如果它們與相似的頂點相鏈接。
圖聚類就是切割圖成若干片，每片就是一個簇，使得簇內的頂點很好地互連，而不同的頂點以很弱的方式連接。割是圖G的頂點V的一個劃分，割的割集是邊的集合，割的大小是割集的邊數，對于加權圖，割的大小是割集的邊的加權和。圖聚類問題就歸結為尋找最好的割，作為簇來分類。如何在圖中找最好的割，如最稀疏的割，存在挑戰，如高計算開銷、復雜的圖、高維性、稀疏性。圖聚類的方法，一類是使用聚類高維數據的方法，如譜聚類；另一類是專門用于圖的方法，如SCAN，搜索圖，找出良連通的成分作為簇。
11.4?具有約束的聚類
聚類分析涉及三個基本方面：作為簇實例的對象、作為對象群的簇、對象之間的相似性。約束有三類：實例上的約束、簇上的約束、相似性度量上的約束。
實例上的約束包括：必須聯系約束和不能聯系約束。
簇上的約束使用簇的睡醒，說明對簇的要求。
相似性度量上的約束說明相似性計算必須遵守的要求。
具有約束的聚類方法，包括處理硬性約束和處理軟性約束兩種。
處理硬性約束的策略是，在聚類的指派過程中，嚴格遵守約束。
具有軟性約束的聚類是一個優化問題。當聚類違反軟性約束時，在聚類上施加一個罰。聚類的最優化目標包含兩部分：優化聚類質量和最小化違反約束的罰，總體目標函數是聚類質量得分和罰得分的組合。
11.5?小結
1）傳統聚類分析中，對象被互斥地指派到一個簇中，然后在很多應用中，需以模糊或概率方式把一個對象指派到一個或多個簇中。模糊聚類和基于概率模型的聚類允許一個對象屬于一個或多個簇。劃分矩陣記錄對象屬于簇的隸屬度。
2）基于概率模型的聚類假定每個簇是一個有參分布。使用待聚類的數據作為觀測樣本，可以估計簇的參數。
3）混合模型假定觀測對象是來自多個概率簇的實例的混合。從概念上講，每個觀測對象都是通過如下方法獨立地產生的：首先根據簇概率選擇一個概率簇，然后根據選定簇的概率密度函數選擇一個樣本。
4）期望最大化EM算法是一個框架，它逼近最大似然或統計模型參數的后驗概率估計。EM算法可以用來計算模糊聚類和基于概率模型的聚類。
5）高維數據對聚類分析提出了挑戰，包括如何對高維簇建模和如何搜索這樣的簇。
6）高維數據聚類方法主要有兩類：子空間聚類方法和維歸約方法。子空間聚類方法在原空間的子空間中搜索簇。例子包括子空間搜索方法、基于相關性的聚類方法和雙聚類方法。維歸約方法創建較低維的新空間，并在新空間搜索簇。
7）雙聚類方法同時聚類對象和屬性。雙簇的類型包括具有常數值、行/列常數值、想干值、行/列想干演變值的雙簇。雙聚類方法的兩種主要類型是基于最優化的方法和枚舉方法。
8）譜聚類是一種維歸約方法。其一般思想是使用相似矩陣構建新維。
9）聚類圖和網絡數據有很多應用，如社會網絡分析。挑戰包括如何度量圖中對象之間的相似性和如何為圖和網絡數據設計聚類方法。
10）測地距是圖中兩個頂點之間的邊數，可以用來度量相似性。社會網絡這樣的圖的相似性可以用結構情境和隨機游走度量。SimRank是基于結構情境和隨機游走的相似性度量。
11）圖聚類可以建模為計算圖割。最稀疏的割導致好的聚類，而模塊性可以用來度量聚類質量。
12）SCAN是一種圖聚類算法，它搜索圖，識別良連通的成分作為簇。
13）約束可以用來表達具體應用丟聚類分析的要求或背景知識。聚類約束可以分為實例、簇和相似性度量上的約束。實例上的約束可以是必須聯系約束和不能聯系約束。約束可以是硬性的或軟性的。
14）聚類的硬性約束可以通過在聚類指派過程嚴格遵守約束而強制實施。軟性約束聚類是一個優化問題，可以使用啟發式方法加快約束聚類的速度。
?
總結
以上是生活随笔為你收集整理的【数据挖掘笔记十一】高级聚类分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【数据挖掘笔记十】聚类分析：基本概念和方
- 下一篇： 【数据挖掘笔记十二】离群点检测