next up previous
次へ: データ圧縮への応用 上へ: 組み合わせ最適化問題への応用 戻る: 実際のデ―タによる実験

本章のまとめ

本章では、多変量解析手法(K-L展開および数量化3類)を用いて大まかな情報を抽 出することにより、日程表作成問題をダイナミックプログラミングによって多項式時 間で解が得られる一次元の組み合わせ問題に帰着させて解く手法を提案した。実験で は、これらの手法によりまずまずの日程表が作成できた。このことは、他の複雑な問 題を解く場合にも、K-L展開あるいは数量化3類等の多変量データ解析手法を用いた 情報抽出が有効な補助手段となり得ることを示唆していると考えられる。

一方、評価基準に沿って導出した測度 $m$ を用いる手法は、多変量解析手法を用い て大まかな情報を抽出して難しい問題を簡単な問題に帰着させて解く手法と異なり、 問題に即した手法であり、日程表作成問題に対してより良い結果を与えた。階層的ク ラスタリングには、クラスター間の類似度(距離)をどう定めるかによって多くの手 法が存在するが、日程表作成問題の場合、クラスター代表ベクトルおよびクラスター 統合のための測度が評価基準から論理的に一意に定まり、しかも、原データに対する 論理演算により計算できる点が興味深い。これは、離散的な評価基準を持つ二値(質 的)データのクラスタリングの問題に対する自然な結果と考えられる。

5.4.2において、JaccardのMatching Coefficientを用いる手法が、 定性的にタイの処理をした測度mを用いる手法と似た振舞いをすることを示したが、 実験的にも、その傾向が分かる。さらに詳細な比較のためには、多くの例についての 実験が必要であろう。また、5.4.3において、項目間の類似度を該当ベクトル間の 要素ごとのANDを取ったベクトルの1の個数としたGroup Average法と測度mを用 いる手法との関係について述べたが、それらに対する実験および詳細な比較等は今後 の課題である。



Takio Kurita 平成14年7月3日