Discovery Sagaサイレントキーワード俯瞰

本研究に関する研究費を申請した1997年当時,統計的指標を最適化するアソシエーションルールを高速に枚挙することは市場からのニーズがあるものの,計算の高速化は難しいと考えられていた.Stanford大学やIBMワトソン研究所でも解決に向けた提案がされていたが,問題に制約を入れてから従来のAproriアルゴリズムをそのまま用いるという戦略で解いており,計算効率に問題があった.我々はこの問題への取り組みを開始したが,1997-9年半ばまでは,探索木を基本にそれを並列化により高速化するという極めてオーソドックスな解きかたに頼っており,残念ながらあまり効率的には動作しなかった.
我々は探索木の並列化という方針を諦めた.主記憶管理やバッファ管理に配慮したAprioriアルゴリズムは市場で非常によく利用されており,このアルゴリズムに若干の変更を加えることで統計的指標を扱えないかというアプローチを検討した.このようにすることで,開発した技術が容易に様々なソフトウエアに組み込めると言う利点がある.しかしAprioriは評価関数の反単調性に依存した方法であり,反単調性を持たない統計的指標に応用するのは見通しが得にくい.
1999年夏に統計的指標の上界を低コストで求める方法から反単調性を導いて,かつ枝狩りにも利用できることが分かった.Aprioriアルゴリズムと融合しても結果の正当性を保証できた.このアイデアを大学院生の瀬々潤君が本格的に実装したところ,良好な性能が得られた.国際的な評価も受け,ACM主催の理論系のデータベース国際会議PODSでの発表、および国際会議からの招待講演を2件受けた.
現在,1千万属性,数百万レコードのデータでさえ,標準的なPCワークステーション上で現実的な時間で処理できるまで実装が進んでおり,当初の目標を達成し,研究をまとめることができたのではないかと考えている.

【研究分担者】
中谷明弘	東京大学	医科学研究所	寄付研究部門教員	(Kakenデータベース)