機器學習：基於網格的聚類演算法
更多騰訊海量技術文章，請關注云加社區：https://cloud.tencent.com/developer
作者：張蓓
俗話說：「物以類聚，人以群分」，在機器學習中，聚類演算法是一種無監督分類演算法。聚類演算法很多，包括基於劃分的聚類演算法（如：kmeans），基於層次的聚類演算法（如：BIRCH），基於密度的聚類演算法（如：DBScan），基於網格的聚類演算法等等。基於劃分和層次聚類方法都無法發現非凸面形狀的簇，真正能有效發現任意形狀簇的演算法是基於密度的演算法，但基於密度的演算法一般時間複雜度較高，1996年到2000年間，研究數據挖掘的學者們提出了大量基於網格的聚類演算法，網格方法可以有效減少演算法的計算複雜度，且同樣對密度參數敏感。
典型演算法
STING：基於網格多解析度，將空間劃分為方形單元，對應不同解析度
CLIQUE：結合網格和密度聚類的思想，子空間聚類處理大規模高維度數據
WaveCluster：用小波分析使簇的邊界變得更加清晰
這些演算法用不同的網格劃分方法，將數據空間劃分成為有限個單元（cell）的網格結構,並對網格數據結構進行了不同的處理，但核心步驟是相同的：
1、 劃分網格
2、 使用網格單元內數據的統計信息對數據進行壓縮表達
3、 基於這些統計信息判斷高密度網格單元
4、 最後將相連的高密度網格單元識別為簇
Statistical Information Grid(STING)演算法
STING演算法的核心思想：首先我們先劃分一些層次，每個層次上我們根據維度或者概念分層不同的cell，實際上這裡的每個層次對應的是樣本的一個解析度。每個高層的cell在其下一層中被對應得劃分成多個cell，每個cell我們都計算出它的統計信息，估計出它的分布。利用這樣的結構，我們很容易進行查詢，比如我們查詢具有某些屬性的樣本，我們從上到下開始，根據cell的統計信息計算query在每個cell的置信區間，找出最大的那個cell，然後到下一層，依次直至到最底層。這樣的好處是，我們不用計算所有的樣本，演算法每進一層都會拋棄不相關的樣本，所需的計算量會越來越少，那麼速度就會很快。
這種方法雖然不是一種顯然的聚類法，但它確實可以用來聚類，因為query返回的樣本實際上就是某一聚類。Query本質上於聚類問題是有等價性的。
STING演算法的兩個參數：
? 網格的步長——確定空間網格劃分
? 密度閾值——網格中對象數量大於等於該閾值表示該網格為稠密網格
STING網格建立流程
1 .首先我們先劃分一些層次，按層次劃分網格
2 .計算最底層單位網格的統計信息（如均值，最大值和最小值）；
網格中統計信息：
? n —— 網格中對象數目
? m —— 網格中所有值的平均值
? s —— 網格中屬性值的標準偏差
? min —— 網格中屬性值的最小值
? max —— 網格中屬性值的最大值
? distribution —— 網格中屬性值符合的分布類型。如正態分布，均勻分布，指數分布
1）最底層的單元參數直接由數據計算，父單元格統計信息由其對應的子單元格計算，具體計算公式見2）3）
2）父單元格計算公式如下
3）父單元格distribution 計算方式
設dist為對應子單元格多數的分布類型，計算confl
示例：根據以下子網格計算父網格的參數
n = 220
m = (20.1100)+(19.750+2160+20.510)/220=2260/220=20.27
s = 2.37
min = 3.8
max = 40
dist = NORMAL
3 .從最底層逐層計算上一層每個父單元格的統計信息，直到最頂層；
4 .同時根據密度閾值標記稠密網格
STING查詢演算法步驟：
（1） 從一個層次開始
（2） 對於這一個層次的每個單元格，我們計算查詢相關的屬性值。
（3） 從計算的屬性值以及約束條件下，我們將每一個單元格標記成相關或者不想關。(不相關的單元格不再考慮，下一個較低層的處理就只檢查剩餘的相關單元)
（4） 如果這一層是底層，那麼轉（6），否則轉（5）
（5） 我們由層次結構轉到下一層，依照步驟2進行
（6） 查詢結果得到滿足，轉到步驟8，否則（7）
（7） 恢複數據到相關的單元格進一步處理以得到滿意的結果，轉到步驟（8）
（8） 停止
CLIQUE聚類演算法
CLIQUE演算法是結合了基於密度和基於網格的聚類演算法，因此既能夠發現任意形狀的簇，又可以處理高維數據。
CLIQUE演算法核心思想：首先掃描所有網格。當發現第一個密集網格時，便以該網格開始擴展，擴展原則是若一個網格與已知密集區域內的網格鄰接並且其其自身也是密集的，則將該網格加入到該密集區域中，知道不再有這樣的網格被發現為止。（密集網格合併） 演算法再繼續掃描網格並重複上述過程，直到所有網格被遍歷。以自動地發現最高維的子空間，高密度聚類存在於這些子空間中，並且對元組的輸入順序不敏感，無需假設任何規範的數據分布，它隨輸入數據的大小線性地擴展，當數據的維數增加時具有良好的可伸縮性。
高維數據聚類的難點在於：
適用於普通集合的聚類演算法，在高維數據集合中效率極低
由於高維空間的稀疏性以及最近鄰特性，高維的空間中基本不存在數據簇
聚類的目標是將整個數據集劃分為多個數據簇（聚類），而使得其類內相似性最大，類間相似性最小，但在高維空間中很多情況下距離度量已經失效，這使得聚類的概念失去了意義。另一方面，建立索引結構和採用網格劃分方法是很多大數據集聚類演算法提高效率的主要策略，但在高維空間中索引結構的失效和網格數隨維數呈指數級增長的問題也使得這些策略不再有效。
CLIQUE識別候選搜索空間的主要策略是使用稠密單元關於維度的單調性。這基於頻繁模式和關聯規則挖掘使用的先驗性質。在子空間聚類的背景下，單調性陳述如下：
一個k-維（>1）單元c至少有I個點，僅當c的每個（k-1）-維投影（它是（k-1）-維單元）至少有1個點。考慮下圖，其中嵌人數據空間包含3個維：age,salary,vacation. 例如，子空間age和salary中的一個二維單元包含l個點，僅當該單元在每個維（即分別在age和salary上的投影都至少包含l個點).
CLIQUE演算法的兩個參數：
? 網格的步長——確定空間網格劃分
? 密度閾值——網格中對象數量大於等於該閾值表示該網格為稠密網格
CLIQUE演算法流程：
1、 對n維空間進行劃分，對每一個維度等量劃分，將全空間劃分為互不相交的網格單元
2、 計算每個網格的密度，根據給定的閾值識別稠密網格和非稠密網格，且置所有網格初始狀態為「未處理」
CLIQUE採用自下而上的識別方式，首先確定低維空間的數據密集單元，當確定了k-1維中所有的密集單元，k維空間上的可能密集單元就可以確定。因為，當某一單元的數據在k維空間中是密集的，那麼在任一k-1維空間中都是密集的。如果數據在某一k-1維空間中不密集，那麼數據在k維空間中也是不密集
3、 遍歷所有網格，判斷當前網格是否為「未處理」，若不是「未處理」狀態，則處理下一個網格；若是「未處理」狀態，則進行步驟4~8處理，直到所有網格處理完成，轉到步驟8
4、 改變網格標記為「已處理」，若是非稠密網格，則轉到步驟2
5、 若是稠密網格，則將其賦予新的簇標記，創建一個隊列，將該稠密網格置於隊列中
6、 判斷隊列是否為空，若空，則處理下一個網格，轉到第2步；若隊列不為空，則進行如下處理
1） 取隊頭的網格元素，檢查其所有鄰接的有「未處理」的網格
2） 更改網格標記為「已處理」
3） 若鄰接網格為稠密網格，則將其富裕當前簇標記，並將其加入隊列
4） 轉到步驟5
7、 密度連通區域檢查結束，標記相同的稠密網格組成密度連通區域，即目標簇
8、 修改簇標記，進行下一個簇的查找，轉到第2步
9、 遍歷整個數據集，將數據元素標記為所有網格簇標記值
示例：以下是密度閾值為4的結果
WaveCluster演算法
離散小波變換DWT(Discrete Wavelet Transform)
離散小波DWT(Discrete Wavelet Transform)：
[x0,x1,x2,x3]=[90,70,100,70]
為了達到壓縮效果，取 (x0+x1)/2 (x0-x1)/2 來代表新的x0,x1
[90,70] 表示為 [80,10] 80即平均數（頻率），10是小範圍波動數（振幅）
同理[100,70]表示為[85,15]
80和85是局部的平均值，反映的是頻率，叫做低頻部分（Low-Pass）
10和15是小範圍波動的幅度，叫做高頻部分（High-Pass）
即[90,70,100,70]經過一次小波變換，可以表示為[80,85,10,15]，低頻部分在前(L)，高頻部分在後(H)
示例：
對X=[90,70,100,70,80,70,90,80,100,70,90,70,80,90,100,70]進行三次小波變換，結果如下所示
離散小波變換用於二維圖像處理
示例：
? 第一步，對原始圖像的每一行進行一次dwt，得到新的特徵圖像；
? 第二步，對第一步得到的特徵圖像的每一列進行一次dwt，得到結果
? LL: 接近原始圖像（縮小了一倍）；
? LH: 圖像水平邊界信息(horizontal edges)；
? HL: 圖像垂直邊界信息(vertical edges)；
? HH: corners
WaveCluster聚類演算法
WaveCluster演算法的核心思想是將數據空間劃分為網格後，對此網格數據結構進行小波變換，然後將變換後的空間中的高密度區域識別為簇。基於數據點數目大於網格單元數目（N≥K）的假設，WaveCluster的時間複雜度為O(N)，其中N為數據集內數據點數目，K為網格內的網格單元數目。
WaveCluster演算法需要兩個參數：
? 網格的步長——確定空間網格劃分
? 密度閾值——網格中對象數量大於等於該閾值表示該網格為稠密網格
WaveCluster演算法流程
1 .將原始空間離散化為網狀空間，並把原始數據放入對應單元格，形成新的特徵空間；
2 .對特徵空間進行小波轉換，即用小波變換對原始數據進行壓縮
對每行進行小波變換，得到
再對每列進行小波變換，得到
註：LL空間相當於是壓縮後的信息，本例是44壓縮為22
3 .找出小波轉換後的LL空間中密度大於閾值（這裡取3）的網格，將其標記為稠密；
4 .對於密度相連的網格作為一個簇，打上其所在簇序號的標籤；
5 . 建立轉換前後單元格的映射表;
6 .把原始數據映射到各自的簇上。
小波聚類-效率
聚類演算法對比
不同的聚類演算法有不同的應用背景，有的適合於大數據集，可以發現任意形狀的聚簇；有的演算法思想簡單，適用於小數據集。總的來說，數據挖掘中針對聚類的典型要求包括：
（1）可伸縮性：當數據量從幾百上升到幾百萬時，聚類結果的準確度能一致。
（2）處理不同類型屬性的能力：許多演算法針對的數值類型的數據。但是，實際應用場景中，會遇到二元類型數據，分類/標稱類型數據，序數型數據。
（3）發現任意形狀的類簇：許多聚類演算法基於距離（歐式距離或曼哈頓距離）來量化對象之間的相似度。基於這種方式，我們往往只能發現相似尺寸和密度的球狀類簇或者凸型類簇。但是，實際中類簇的形狀可能是任意的。
（4）初始化參數的需求最小化：很多演算法需要用戶提供一定個數的初始參數，比如期望的類簇個數，類簇初始中心點的設定。聚類的結果對這些參數十分敏感，調參數需要大量的人力負擔，也非常影響聚類結果的準確性。
（5）處理雜訊數據的能力：雜訊數據通常可以理解為影響聚類結果的干擾數據，包含孤立點，錯誤數據等，一些演算法對這些雜訊數據非常敏感，會導致低質量的聚類。
（6）增量聚類和對輸入次序的不敏感：一些演算法不能將新加入的數據快速插入到已有的聚類結果中，還有一些演算法針對不同次序的數據輸入，產生的聚類結果差異很大。
（7）高維性：有些演算法只能處理2到3維的低緯度數據，而處理高維數據的能力很弱，高維空間中的數據分布十分稀疏，且高度傾斜。
（8）可解釋性和可用性：我們希望得到的聚類結果都能用特定的語義、知識進行解釋，和實際的應用場景相聯繫。
幾種常用的聚類演算法從可伸縮性、適合的數據類型、高維性（處理高維數據的能力）、異常數據的抗干擾度、聚類形狀和演算法效率6個方面進行了綜合性能評價，評價結果如表1所示：
網格聚類演算法對比
參考文獻：
[1] Jiawei Han &MichelineKamber&Jian Pei.數據挖掘概念與技術（第三版）[M]，2012，297-305.
[2] Ian H. Witten &Eibe Frank&Mark A. Hall. 數據挖掘使用機器學習工具與技術[M]，2014,58-60.
[3] Wei Wang, Jiong Yang, and Richard MuntzSTING : A Statistical Information Grid Approach to Spatial Data
Mining [J]，1997
[4] GholamhoseinSheikholeslami&Surojit Chatterjee &Aidongzhang. WaveCluster:A Multi-Resolution Clustering Approach for Very Large Spatial Database [J]，1998
TAG:機器學習 |