聚類演算法第三篇-層次聚類演算法Chameleon

05-18

1 概述

Chameleon（變色龍）演算法[1]是一種兩階段層次聚類演算法。在進行兩個類簇合併時使用更高的標準，同時考慮了類簇之間的互連性（連接兩個子簇的邊的權重之和）和近似性（連接兩個子簇的邊的平均權重），具有發現任意形狀和大小的簇的能力。演算法的過程可分為兩個階段，第一階段有數據集構造一個K近鄰圖 $G_{k}$ ，再通過一個圖劃分演算法將 $G_{k}$ 劃分成大量的子圖，每個子圖代表一個初始子簇，第二階段通過一個凝聚的層次聚類演算法反覆的合併子簇來找到真正的聚類結果。可直觀如下圖理解：

2 一些關鍵概念

2.1 稀疏圖

Chameleon使用稀疏的k近鄰圖來對數據集進行建模，圖中的每一個節點代表一個數據點，任意兩個節點v和u之間存在每一條邊代表u在v的k個最鄰近的節點中。如下圖，(a)是原始數據，(b)(c)(d)分別是1,2,3近鄰圖。

2.2 子簇相似性度量

Chameleon使用相對互連性（Relative Interconnectivity）和相對近似性（Relative Closeness）來決定子簇之間的相似性，會選擇RI和RC都高的子簇對進行合併。

相對互連性： $RI(C_{i}, C_{j})=frac{EC(C_{i}, C_{j})}{frac{|EC(C_{i})|+|EC(C_{j})|}{2}}$

其中， $EC(C_{i}, C_{j})$ 是連接簇 $C_{i}$ 和 $C_{j}$ 的邊的權重之和， $EC(C_{i})$ 是把簇 $C_{i}$ 劃分成兩個大小大致相等部分的最少邊的權重之和。相對互連性解決的是簇之間形狀不同和互連度不同的問題。

相對近似性： $RC(C_{i}, C_{j})=frac{overline SEC(C_{i}, C_{j})}{frac{|C_{i}|}{|C_{i}|+|C_{j}|}overline SEC(C_{i})+frac{|C_{j}|}{|C_{i}|+|C_{j}|}overline SEC(C_{j})}$

其中， $overline SEC(C_{i}, C_{j})$ 是連接簇 $C_{i}$ 和 $C_{j}$ 的邊的平均權重， $overline SEC(C_{i})$ 是把簇 $C_{i}$ 劃分成兩個大小大致相等部分的最少邊的平均權重。

3 Chameleon聚類過程

3.1 子圖劃分

Chameleon使用hMetis[2]演算法根據最小化截斷的邊的權重之和來分隔k近鄰圖。

3.2 子簇合併

Chameleon使用度量 $RI(C_{i}, C_{j}) imes RC(C_{i}, C_{j})^{alpha }$ 來選擇合併的子簇，用這個度量是同時考慮到了兩個子簇之間的互連性和近似性。

4 Chameleon聚類結果及與DBSCAN的對比

原始論文中使用了上面4個數據集，(a) DS1中有8000個點，(b) DS2中有6000個點，(c) DS3中有10000個點，(d) DS4中有8000個點。

Chameleon聚類結果圖：

DBSCAN針對DS1在參數MinPts=4，(a)Eps=0.5, (b)Eps=0.4時的聚類結果圖：

DBSCAN針對DS2在參數MinPts=4，(a)Eps=5.0, (b)Eps=3.5, (c)Eps=3.0時的聚類結果圖：

5 結束語

Chameleon演算法能高質量的發現一些任意形狀的聚類，但裡面的參數調整並不容易，圖切分過程中的k值的選取並不那麼直觀，此外，演算法的時間複雜度在 $O(n^2)$ ，在數據量過大時並不適用。

參考文獻

【1】CHAMELEON：A Hierarchical Clustering Algorithm Using Dynamic Modeling

【2】hMETIS - Hypergraph & Circuit Partitioning