過去我們分別介紹了 4 個集成（Ensemble）分群（Clustering）基學習器（Base Learner）的方法：Majority Vote、Iterative Voting Consensus、Iterative Probabilistic Voting Consensus、Iterative Pairwise Consensus，也介紹了 1 個可以衡量集成分群的效能：Symmetric Distance Metric。今天，我們要介紹另一個簡單好用的評價指標：Rand Distance（Nguyen and Caruana, 2007）。
一、任意 2 筆資料的分群集成結果
假設我們現在要集成分群演算法 A 跟分群演算法 B，集成結果稱為 E。現在考慮資料集裡頭任 2 筆資料 X 跟 Y。我們要來看看 X 跟 Y 所有可能的結果。
第 1 種可能：集成結果、分群演算法 A 都把 X 跟 Y 放在同一個子群。
第 2 種可能：集成結果把 X 跟 Y 放在不同的子群，但是分群演算法 A 把 X 跟 Y 放在同一個子群
第 3 種可能：集成結果把 X 跟 Y 放在同一個子群，但是分群演算法 A 把 X 跟 Y 放在不同的子群
第 4 種可能：集成結果跟分群演算法 A 都把 X 跟 Y 放在不同的子群。
討論完集成結果與分群演算法 A 之後，我們可以接著討論集成結果跟分群演算法 B 的關係。
二、Rand Distance
看完了任 2 筆資料的可能情況後，我們就能夠說明 Rand Distance 了。計算公式如下：
這是什麼意思呢？
其實很簡單，對分群演算法 A，我們都找出該分群演算法跟集成結果 4 種可能的個數。接著代入下方公式：
我們可以找出集成結果與各個分群演算法的 Rand Distance，然後計算 Rand Distance 的平均，得到該集成結果的效能。
三、Python 程式
下方 Python 程式中，最外層的迴圈是要根據每一個基學習器，計算 Rand Distance。裡面 2 個迴圈，則是要根據任 2 筆資料，計算到底是屬於 4 種可能的哪一種。
def get_rand_distance(x, n_clusters): n_sample = len(x[0])
n_ensemble = len(x)
distance = np.zeros(n_ensemble)
N10 = 0
N01 = 0
N11 = 0
N00 = 0 for i in range(1, n_ensemble):
for j in range(n_sample):
for k in range(n_sample):
learner = (x[i][j] == x[i][k])
ensemble = (x[0][j] == x[0][k])
if((learner == True)and(ensemble == True)):
N11 = N11 + 1
elif((learner == True)and(ensemble == False)):
N10 = N10 + 1
elif((learner == False)and(ensemble == True)):
N01 = N01 + 1
else:
N00 = N00 + 1
distance[i - 1] = (N01 + N10) / (N00 + N01 + N10 + N11)
return np.sum(distance) / n_ensemble
參考資料
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.
