16章は、フラットクラスタリングについて。
クラスタリング
クラスタリングとは、データセットをクラスタと呼ばれるサブセットにグループ化する手法。
データの類似度を基にクラスタに分ける。
教師なし学習(訓練データで学習せずに、データの分布などなどからデータのデータの特徴的パターンを見付ける学習法)である。
ちなみに、前章までで説明してきたような、人手で作成した訓練データを使ってデータを分類する学習法を、教師あり学習という。
クラスタリングは、再現率向上に役立つ。
例えば、ドキュメント d がクエリとマッチしていれば、d を含むクラスタ内の他のドキュメントも結果として返すことができる。
クラスタリングの目標は、関係性のあるデータが同じクラスタに属させ、関係性のないデータは違うクラスタに属させること。
気をつけるべき点は、以下のようなことである。
クラスタリングには、大きく分けて以下の2種類がある。
- フラットクラスタリング
- 階層的クラスタリング
また、以下のような2種類にも分かれる。
- ハードクラスタリング
1つのデータは、1つのクラスタに属する。
- ソフトクラスタリング
1つのデータは、複数のクラスタに属してもよい。
この章では、フラットクラスタリングについて説明する。
K-means
K-means(K-平均化法)は、クラスタリング手法の中で最も有名である、フラットかつハードなクラスタリング手法。
以下にアルゴリズムを示す。
1.各データに対してK個のクラスタにランダムに割り振る。
2.各クラスタのセントロイドを求める。
3.各データを、それと最も近い重心のクラスタに割り当て直す。
4.2,3を繰り返し、クラスタが変化しなくなったところで処理を終了する。
K-meansの欠点としては、初期値のクラスタによって結果が変化し、場合によっては最適なクラスタリングとならないことである。
この欠点を補うために、以下のようなことを行う。
また、計算量は、重心の再計算回数 I、クラスタの数 K、ドキュメント数 N、ベクトルの次元 M とするとo(IKMN)であり、階層的クラスタリングと比べてコストが低い。
ちなみに、K-meansを一般化して、ソフトクラスタリングを実現するアルゴリズムである、EMアルゴリズムというものもある。
