libcs チュートリアル
- はじめに
- クラスタリングプログラムを作る
- クラスタの代表単語を表示する
- 検索結果を自動分類する
- クラスタリングアルゴリズムの詳細
5 クラスタリングアルゴリズムの詳細
最後にクラスタリングアルゴリズムの詳細を説明します.
クラスタリングプログラムを作るでも説明しましたが,
関数 csb は以下のようなボトムアップ階層型アルゴリズムに基づいています.
- 初期化:
- 各データだけから成るクラスタ(よってデータ数は1)を作る.
- すべてのクラスタ間の距離を計算する.(距離行列の初期化)
- 反復:
- 最も距離の近いクラスタ対をマージする.
- マージによって出来たクラスタと他のクラスタとの距離を更新する.(距離行列の更新)
ここで,距離の計算方法により幾つかのバリエーションが生まれます.
代表的なものを挙げると,
- ・単一リンク法(CS_SLINK)
- 初期距離行列: 任意
クラスタ間の距離: 一番近いデータ対の距離 - ・完全リンク法(CS_CLINK)
- 初期距離行列: 任意
クラスタ間の距離: 一番遠いデータ対の距離 - ・群平均法(CS_GAVE)
- 初期距離行列: 任意
クラスタ間の距離: 全てのデータ対の距離平均 - ・WARD法(CS_WARD)
- 距離行列の初期化: ユークリッド距離
クラスタ間の距離: マージしてできた新たなクラスタにおける分散.
つまり,新クラスタの平均ベクトル(セントロイド)との誤差平方和.
となります.関数 csb では,CS_SLINK, CS_CLINK, CS_GAVE, CS_WARDとしてそれぞれのアルゴルズムを指定できます.
上記で「初期距離行列: 任意」となっている箇所は,
tf.idf で重み付けしたベクトル間の cosine を計算しています.
また,WARD法でも,ベクトルの各要素は tf.idf で重み付けしています.csb ではもう一つ,
確率的なクラスタリングアルゴリズムもインプリメントされています.CS_HBC で指定できます.詳しくは [1] を見てください.
これらのアルゴリズムでどれが優れているかは一概に言えませんので,
いろいろ試してみて一番適したものを使うとようでしょう.
実験してみると,
確率的クラスタリング(CS_HBC)は粒のそろった(大きさのそろった)クラスタを生成するようです.
また,将来的には,「任意」である「初期距離行列」の計算方法は,
ユーザが自由に定義できるようになる予定です.
[1]: 岩山真, 徳永健伸, "確率的クラスタリングを用いた文書連想検索", 自然言語処理, Vol 5. No. 1, pp. 101-117, 1998.
「4: 検索結果を自動分類する」に戻る
「1: はじめに」に戻る