前節で紹介したクラスタリングプログラム clustering.c を作りながら， libcs の使い方を学びます．
まずはインクルードファイルを定義します．
#include <geta/cs.h>通常はこの他にも， WAM に関するインクルードファイルや libae に関するインクルードファイルも定義します．
#include <geta/wam.h>
#include <geta/ci.h>
#include <geta/cs.h>これくらい定義しておけば十分です．関数 csb がクラスタリングを行います．
#define NKW 5
syminfo *q;
int qlen;
cs_elem *cslst;
int csno;
WAM *wam;
int wam_dir;
int nc;
cslst = csb(q, qlen, 0, wam, wam_dir, CS_HBC, &nc, 2, NKW);クラスタリングの対象となるデータは syminfo 型のリストに格納します．
ここでは，*q がそれに相当します．qlen は *q の長さです．
注意したいのは，csb は *q を破壊的に書きかえるということです．
書きかえるというよりは，*q の要素を並べかえるといったほうが正確です．
つまり，csb は syminfo 型リストをソートする関数の一種になります．例として，5個の文書データをクラスタリングしてみます． それぞれの id は 1, 2, 3, 4, 5とします．csb を呼ぶ前に，これらの id を *q の各要素に代入してください．順番はどうでも構いませんが，例えば，
q[0].id = 1;
q[1].id = 2;
q[2].id = 3;
q[3].id = 4;
q[4].id = 5;とします．
実際のプログラム clustering.c では，
引数に id の列を指定し，
引数から読みこんだ id を *q の各要素に代入してみましょう．
更に，各文書には重みもつけることができます．
例えば検索結果を分類する場合には，
検索要求との類似度を重みとするのがよいでしょう．
ここで付けた重みは，
クラスタ間の順番やクラスタ内文書の順番に反映します．
今の例では，重みを全部 1.0 としておきます． q[0].weight = 1.0;
q[1].weight = 1.0;
q[2].weight = 1.0;
q[3].weight = 1.0;
q[4].weight = 1.0;csb の引数の wam は，
対象データが収められているコーパスの WAM です．wam_dir は WAM を見る向きです．
今の場合，文書が対象ですから向きは WAM_ROW になります．CS_HBC は，クラスタリングのアルゴリズムを指定しています．
他にも幾つか代表的なアルゴリズムが選べます．
詳しくは man ページを参照してください．nc には，まとめたいクラスタ数を指定します．csb の呼び出しが終った後，nc は実際にまとまったクラスタ数に書きかわります．
たいていは指定したクラスタ数と同じになります．
次の 2 は，例外クラスタを排除するための数です．
指定した数(この場合2個)以下の文書からなるクラスタは例外として扱い，
最終的な結果から除きます．
とりあえず 2 くらいを指定しておけばよいでしょう．
最後に NKW で各クラスタからとりだす代表単語数を指定します．クラスタリングの結果を見るには二種類の方法があります． まずは，csb の返り値を調べる方法です．csb は cs_elem 型のリストを自動的に確保し， そこに各クラスタの情報を入れます． この方法については 「クラスタの代表単語を表示する」 で詳しく説明します． 本節では，もう一つの方法について説明したいと思います．
先程， 「csb は引数で指定した syminfo 型リスト *q を並べかえる関数である」 と書きました． 具体的には，近い文書はなるべく近く配置するよう並べかえます． したがって，並べかわった *q を見れば， 各クラスタがどのような文書を含んでいるかがわかります．
実際に上の例で考えましょう．*q には {1, 2, 3, 4, 5} の順でデータ(文書)が収められていました． 関数 csb はまず，全てのデータ対間の距離を計算して一番近いデータ対を見つけます． 例えば，3 と 5 が一番近かったとすると， このデータ対をまとめ上げて近くに配置します． データの並びは {1, 2, (3, 5), 4} となります． 5つあったデータが 4 つにまとまりました． 次に，まとまったデータ対(3, 5)を新たな一つの仮想データとして扱い， 更に一番近いデータ対を探します． 次は 1 と 4 が一番近かったとしましょう． ここまでで，{(1, 4), 2, (3, 5)} と 3 つにまとまりました． 1 と 4 および 3 と 5 の近いデータがとなりあって配置されています． 同様にして，次は 2 と (3, 5) が一番近いとすると， {(1, 4), (2, (3, 5))} と 2 つにまとまります． 最後は残った 2 つのデータをまとめ，{((1, 4), (2, (3, 5)))} となります．
データ データ 結果
1回目のマージ 3 5 {1,2,(3,5),4}
2回目のマージ 1 4 {(1,4),2,(3,5)}
3回目のマージ 2 (3,5) {(1,4),(2,(3,5))}
4回目のマージ (1,5) (2,(3,4)) {((1,4),(2,(3,5)))}木の形で書くともっとわかりやすくなるでしょう．
この木はデンドログラムと呼ばれています． +---+----+ <-- 4回目のマージ
| |
| +--+--+ <-- 3回目のマージ
| | |
2回目のマージ --> +-+-+ | |
| | | |
| | | +-+-+ <-- 1回目のマージ
| | | | |
1 4 2 3 5最初は，{1, 2, 3, 4, 5} の順で *q に格納されていたデータが，
クラスタリングの結果，{1, 4, 2, 3, 5}と並べかわります．
つまり， 要素 値
q[0].id 1
q[1].id 4
q[2].id 2
q[3].id 3
q[4].id 5となります．
完璧ではありませんが，近いデータはできるだけ近く配置されています．
ここで，最終的に2つのグループに分割したければ，
5 と 2 の間に敷居を作り { 1, 4 | 2, 3, 5 } と分割します．
なぜなら，一番最後のマージが，
一番嫌々結びついたマージだからです．
二つに分けるのなら，ここで分けるのが妥当です．
3 つに分割したければ，次に嫌々結びついた
2 と (3, 5) の間にあらたな敷居を作り { 1, 4 | 2 | 3, 5 } とすればよいのです．
どこに敷居を作るかが違うだけで，
データの順番は 1, 4, 2, 3, 5 で変らない所に注目してください．少し脱線しますが， 上の例で，例えば (1, 4) と (2, 3, 5) の間の順番を逆にして， { 2, 3, 5, 1, 4 } としても構いません． この順番を決めるときに文書の重みを使います． 文書の重み平均が大きいグループを先に配置します．
さて本題に戻って，残るはどこに敷居を立てればよいかです． 敷居の場所は，マージの順番に大きく依存しています． 例えば，極端に 5 個のグループに分割することを考えます． この場合，{ 1 | 4 | 2 | 3 | 5 } のように全データ間に敷居が立ちます． では，4個のグループに分割したいとしましょう． 敷居を一つ取りはらえばよいのですが， 最初にマージされるデータ間の敷居(3と5の間)を取ればよいことはあきらかです． 一番近いデータ対だからです． 敷居を取りはらった結果，{ 1 | 4 | 2 | 3, 5 } となります． 3個のグループに分割したい時は，更に一つ敷居をはずします． 二番目にマージされるデータ間の敷居(1と4の間)です． このように 5 個のデータを nc 個に分割したいときは， (5 - nc) 回目のマージまでの敷居をはずせばよいことがわかります．
敷居の情報--マージの順番--は，syminfo 型要素(つまり各文書に関する要素)の u.i というメンバに入っています． 例の場合，
文書番号 敷居(マージの順番)
要素 メンバ 値 メンバ 値
q[0] id 1 u.i 0
q[1] id 4 u.i 2
q[2] id 2 u.i 4
q[3] id 3 u.i 3
q[4] id 5 u.i 1となります．
最初の要素 q[0] の u.i が 0 となっていますが，これはダミー情報です．例えば，3個のグループに分割したい時は，*q の要素を 0 から調べていき， 各要素のメンバ u.i が (5-3)=2 よりも大きければ，その直前に敷居を立てます．
添字 0 1 2 3 4
id 1 4 2 3 5
u.i 0 2 4 3 1
敷居 | |この場合，最初の要素 q[0] の u.i は 0 ですから敷居は立ちません．
次の q[1].u.i は 2 です．
これも 2 より大きくありませんから敷居は立ちません．
次の q[2].u.i は 4 で， 2 より大きい数字です．
よって，q[1] と q[2] の間に敷居が立ちます．
次の q[3].u.i も 2 より大きい数字(3)ですから敷居が立ちます．
最後の q[4].u.i は 2 より小さい(1)ですから敷居は立ちません．
最終的には { 1, 4 | 2 | 3. 5 } となります．このようにして，*q の各要素について u.i を調べれば，*q を任意の個数に分割することができますが， libcs には， このための関数 sort_cw_syminfo_list が用意されています．
sort_cw_syminfo_list(q, qlen, nc_orig, CS_SORT_DENDRO);sort_cw_syminfo_list は *q を nc_orig 個に分割します． 具体的には，*q の各要素の u.i をクラスタ番号に書きかえます． 例の場合，nc_orig を 3 にして呼ぶと，*q は以下のようになります．
添字 0 1 2 3 4
id 1 5 2 3 4
u.i 0 0 1 2 2メンバ u.i の値が書きかわってしまう点に注意してください．更に，最後の引数の CS_SORT_DENDRO を CS_SORT_WEIGHT に変更すると， 各グループ内の文書が重み順にソートされます． この場合，*q の並びは関数 csb が返す並びとは異なります．
プログラムをコンパイルしましょう．
% cc msearch3.c -o msearch3 -I$GETAROOT/include -L$GETAROOT/lib
-lcs -lae -lwam -lgetamu -lsrvmu -lm「3: クラスタの代表単語を表示する」に進む
「1: はじめに」に戻る