« AdaBoost アルゴリズム (ブースティング) | トップページ | 国際会議WWW2009論文感想その7 »

クラスタリング アルゴリズムの評価

クラスタリングの研究をしていると,その評価にはいつも悩まされます.人手で行った正解クラスタリングとの類似性を評価指標とすることも考えられますが,実際の利用では特定のクラスタに入って,その使い勝手を見ることも多いでしょう.もし,特定のクラスタに注目して評価するならば,そのクラスタが何の集まりなのかを決めないといけません.支配的な集まりを仮の正解とすることも考えられますが,これで完全であるとは言えません.
人手で行った正解クラスタリングとの類似性を評価指標に,以下のようなものが見つかったので紹介します.

・Folwkes-Mallows index
E. Fowlkes and C. Mallows: A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, Vol.78, No. 383, pp.553-569, 1983.
2つのクラスタリングC1とC2.C1は計算機によるクラスタリング結果.C2は人手による正解のクラスタリング.
N11:サンプルがC1,C2の両方において同じクラスタにある.
N00:サンプルがC1,C2の両方において異なるクラスタにある.
N10:サンプルがC1においては同じクラスタにあり,C2においては異なるクラスタにある.
N01:サンプルがC1においては異なるクラスタにあり,C2においては同じクラスタにある.

WI(C1,C2)=N11/(N11+N01)
WII(C1,C2)=N11/(N11+N10)
Folwkes-Mallows index=sqrt(WI(C1,C2)*WII(C1,C2))

・variation of information
M. Meila: Comparing clusterings: An information based distance, Journal of Multivariate Analysis, Vol.98, No.5, pp.873-895, 2007.
クラスタk,クラスタ内のサンプル数nk,全体のサンプル数n,C(C1とC2)はクラスタリング結果,KはクラスタリングC内のクラスタ個数

サンプルがクラスタkに属する確率
P(k)=nk/n
サンプルがどのクラスタに属しているかという不確実性H(C)は,
H(C)=-sigma{k=1, K}(P(k)*logP(k))
サンプルがクラスタリングC1中のkとC2中のk'に含まれている確率
P(k,k')=|C1k∧C2k'|/n
相互情報量はあらゆるクラスタの組を考慮に入れて
I(C1,C2)=Sigma{k=1,K}Sigma{k'=1,K'}P(k,k')log(P(k,k')/P(K)P(k')
ランダムなサンプルに対して,それが所属するC1のクラスタについての不確実性はH(C1).あるサンプルがC1においてどのクラスタに属するか与えられたときは,C2における不確実性をI(C1,C2)だけ減少させられる.
すなわち,
variation of information = H(C1,C2)+H(C2,C1)
=[H(C1)-I(C1,C2)]+[H(C2)-I(C1,C2)]

|

« AdaBoost アルゴリズム (ブースティング) | トップページ | 国際会議WWW2009論文感想その7 »

Web研究」カテゴリの記事