クラスタリングのまとめ

機械学習

凝集型クラスタリング（ボトムアップクラスタリング）
簡単に言うと、一番末節から樹形図を書いていって、一つのルートにマージしていくアルゴリズム

入力：事例集合D={x1,x2,...,xD}
C={c1,c2,...,cD}
＃１つのクラスタに１つの事例を割り当てる
c1={x1},c2={x2},...,cD={xD}
while C>2 #停止条件
＃もっとも似ているクラスタ対を見つける
(c_m, c_n) = arg {max}_{c_i,c_j \in C} sim (c_i,c_j)
＃見つかったクラスタ対を融合する
merge(cm,cn)
end while

クラスタ間の類似度sim(cm,cn)の判定法として、以下のようなものがある。
・単連結法（single-link method）：最も近い事例対の類似度をクラスタの類似度にする
・完全連結法（complete-link method）：最も遠い事例対の類似度をクラスタの類似度にする
・重心法（centroid method）：各クラスタの重心同士の類似度をクラスタの類似度にする

k-平均法（k-meansクラスタリング）

入力：事例ベクトル集合D={x1,x2,...xD} & クラスタ数k
無作為にクラスタ（k個）の代表ベクトルm1,m2,...,mkを決定
until 収束
foreach x^{(i) \in D}
\forall c, c_{max} = arg max_c sim( \bf x^{(i)}, m_c ) #事例ベクトル集合の分割
insert x^{(i)} into c_{max}
end foreach
\forall c, m_c = \frac{1}{|c|} \sum_{x^i \in C} x^{(i)} #代表ベクトルを再計算
end until

注意点：凝集型クラスタリングではとりあえずクラスタリングを行なって、樹形図のどこで切るかはあとで決めればよかったが、k-meansクラスタリングではクラスタ数kを予め決めておかなければならない

混合正規分布によるクラスタリング
k-means法をマイルドにすることを考える。
２つのクラスタの境界に位置するデータを、単純に（冷酷に）類似度のみで割り振るのではなく、確率的に分類する
この割り振り時の確率分布（事後確率）を正規分布と仮定→混合正規分布によるクラスタリング
代表ベクトルの再計算の際にも確率的な重み付けを行う

入力：事例ベクトル集合D={x1,x2,...xD} & クラスタ数k
無作為にクラスタ（k個）の代表ベクトルm1,m2,...,mkを決定
until 収束
foreach x^{(i) \in D}
\forall c, c_{max} = arg max_c sim( \bf x^{(i)}, m_c ) #事例ベクトル集合の分割
insert x^{(i)} into c_{max}
end foreach
\forall c, m_c = \frac{1}{|c|} \sum_{x^i \in C} x^{(i)} #代表ベクトルを再計算
end until

k-means法と似ている所：初めにクラスタ数ｋを仮定するところ。代表ベクトルを更新していくところ。k-means法との違い：混合正規分布によるクラスタリングではP(c|xi)の値（事後確率：あるベクトルをあるクラスタに割り振る確率）は、各データが割り振られるクラスタが変わらなくなっても（結果が収束しても）微小に変化しつづけるので、収束判定が必要（計算を打ち切る条件が「結果の収束」とは別の軸で必要）→つまりΣ|m-m'|<εなど→EMアルゴリズムの収束判定を用いたほうが良い

EMアルゴリズム（一般的な枠組み）
混合正規分布によるクラスタリングはEMアルゴリズムの特殊な場合である。

EMアルゴリズム
入力：不完全データD
θの初期値は無作為に決める
until収束
　Eステップ：任意の x^{(i) \in D、任意のcについて、 P(c|\bf{x}^{(i)}) を計算
　Mステップ： \theta^{max} = arg {max}_{\theta} Q(\theta | \theta^{\prime})
　 \theta^{\prime} = \theta
end until
ただし、（尤度に基づく）Q関数の定義
Q(\theta;\theta^{\prime} )= \sum_{\bf{x}^{(i)} \in D} \sum_c P(c|\bf{x}^{(i)} ;\theta^{\prime} ) log P(c,\bf{x}^{(i)} ; \theta)

他に、
・EMアルゴリズムの枠組みを利用した、PLSAやPLSI
・スペクトラルクラスタリング（spectral clustering）：事例感の類似度に基づいて次元圧縮を行い、そのあとでk-means法等を用いてクラスタリングを行う
・制約付きクラスタリング：なんらかの情報を制約として与えて、できる限り望ましいクラスタを作る
・自己組織化マップ：可視化の際に注意が必要→２次元平面でのクラスタリング結果の描画が意味のある結果を表している保証はない