過去，我們曾經介紹集成（Ensemble）分群（Cluster）演算法的技術，包含 Majority Vote、Iterative Voting Consensus、Iterative Probabilistic Voting Consensus、Iterative Pairwise Consensus。
這麼多集成的方法，到底要選哪一個比較好呢？今天，我們要來介紹一個評估集成結果的評價指標：Symmetric Distance Metric （Nguyen and Caruana, 2007）。
一、分群交集
要計算 Symmetric Distance Metric，我們要先找到分群的交集。假設有 2 個分群結果，則「分群演算法 A 中子群 1 的資料」與「分群演算法 B 中子群 1 的資料」的交集，即為資料同時出現在「分群演算法 A 中子群 1」以及「分群演算法 B 中子群 1」所成的集合。
以下圖為例，紅色點就是資料都是在演算法 A 跟演算法 B 的子群 1。
交集的集合的大小，也就是資料筆數，我們用以下符號來代替：
二、Symmetric Distance Metric
了解怎麼計算交集之後，我們就可以計算 Symmetric Distance Metric。公式如下：
這是什麼意思呢？假設有 2 個分群演算法 A 跟 B，我們要找演算法 A 的子群 1，跟演算法 B 的哪一個子群交集最多；接著找找演算法 A 的子群 2，跟演算法 B 的哪一個子群交集最多...如此依序找。
處理完演算法 A 之後，換處理演算法 B。也就是找演算法 B 的子群 1，跟演算法 A 的哪一個子群交集最多；接著找找演算法 B 的子群 2，跟演算法 A 的哪一個子群交集最多…如此依序找。
最後，使用 2N 減去上述找出的交集資料筆數，除以 2N，就是答案囉。
三、Python 實作
我們先建立一個函式，用來計算 2 個分群演算法中的 2 個子群，有多少筆資料是一樣，也就是交集的資料筆數。
def get_intersect_num(x, x_cluster, y, y_cluster):
x_index = [i for i in range(len(x)) if x[i] == x_cluster]
y_index = [i for i in range(len(y)) if y[i] == y_cluster]
return len(set(x_index) & set(y_index))接著，針對任一個分群演算法中的任一個子群，計算與另一個子群的最大交集數，即可獲得 Symmetric Distance Metric。
def get_symmetric_distance(x, n_clusters):
n_sample = len(x[0])
n_intersect = np.zeros(n_clusters)
score = 2 * n_sample
learner_A = x[0]
learner_B = x[1]
for i in range(0, n_clusters):
for j in range(0, n_clusters):
n_intersect[j] = get_intersect_num(learner_A,
i,
learner_B,
j)
score = score - max(n_intersect)
for i in range(0, n_clusters):
for j in range(0, n_clusters):
n_intersect[j] = get_intersect_num(learner_B,
j,
learner_A,
i)
score = score - max(n_intersect)return score / (2 * n_sample)
參考資料
Nguyen, Nam & Caruana, Rich. (2007). Consensus Clusterings. Proceedings — IEEE International Conference on Data Mining, ICDM. 607–612.
關於作者
Chia-Hao Li received the M.S. degree in computer science from Durham University, United Kingdom. He engages in computer algorithm, machine learning, and hardware/software codesign. He was former senior engineer in Mediatek, Taiwan. His currently research topic is the application of machine learning techniques for fault detection in the high-performance computing systems.
