読者です 読者をやめる 読者になる 読者になる

IIR16章まとめ

16章は、フラットクラスタリングについて。

クラスタリング

クラスタリングとは、データセットクラスタと呼ばれるサブセットにグループ化する手法。

データの類似度を基にクラスタに分ける。

教師なし学習(訓練データで学習せずに、データの分布などなどからデータのデータの特徴的パターンを見付ける学習法)である。

ちなみに、前章までで説明してきたような、人手で作成した訓練データを使ってデータを分類する学習法を、教師あり学習という。

クラスタリングは、再現率向上に役立つ。
例えば、ドキュメント d がクエリとマッチしていれば、d を含むクラスタ内の他のドキュメントも結果として返すことができる。

クラスタリングの目標は、関係性のあるデータが同じクラスタに属させ、関係性のないデータは違うクラスタに属させること。

気をつけるべき点は、以下のようなことである。

クラスタリングには、大きく分けて以下の2種類がある。

クラスタ間に関係性がないようなクラスタリング

クラスタ間に階層的構造を見出すようなクラスタリング

また、以下のような2種類にも分かれる。

1つのデータは、1つのクラスタに属する。

1つのデータは、複数のクラスタに属してもよい。

この章では、フラットクラスタリングについて説明する。

K-means

K-means(K-平均化法)は、クラスタリング手法の中で最も有名である、フラットかつハードなクラスタリング手法。

以下にアルゴリズムを示す。

1.各データに対してK個のクラスタにランダムに割り振る。

2.クラスタのセントロイドを求める。

3.各データを、それと最も近い重心のクラスタに割り当て直す。

4.2,3を繰り返し、クラスタが変化しなくなったところで処理を終了する。

K-meansの欠点としては、初期値のクラスタによって結果が変化し、場合によっては最適なクラスタリングとならないことである。

この欠点を補うために、以下のようなことを行う。

  • 初期値をランダムではなく、ヒューリスティックな手法で決定する。
  • 階層的クラスタリングを用いる。
  • 異なる初期値で複数回K-meansを適用し、その中で最もよい結果を最終的な結果にする。

また、計算量は、重心の再計算回数 I、クラスタの数 K、ドキュメント数 N、ベクトルの次元 M とするとo(IKMN)であり、階層的クラスタリングと比べてコストが低い。

ちなみに、K-meansを一般化して、ソフトクラスタリングを実現するアルゴリズムである、EMアルゴリズムというものもある。

クラスタリングの評価

以下、代表的な2つの手法を説明する。

Purity(純度)

クラスタにおいて、最も多く含まれたクラスタに属する正解クラスタの要素数の割合の加重平均。

  • Ω = {ω1, ω2, …, ωk}
  • C = {c1, c2, …, cj}


上図の場合、次のように求まる。

(1/17) × (5 + 4 + 3) ≈ 0.71

Rand index

以下の式で定義される。

以下に例を示す。

(20 + 72)/(20 + 20 + 24 + 72) ≈ 0.68

他の評価手法としては、NMI(正規化相互情報量)やF値などがある。

Kの決定法

クラスタ数Kはどのように決定すればよいのか。

以下、2つのアプローチを与える。

1.
1つのクラスタから始めて、クラスタ数を順に増やしていくことにより最適なクラスタ数を探す。

その際、新しいクラスタに対してペナルティを与える。

2.
以下のグラフで、「ひざ」となる部分、すなわち急激に傾きが変化している部分を見付ける。

この例では、K = 4 or 9 である。