二分決定グラフ(BDD)を活用したデータマイニング·知識発見技術の最近の話題

摘要

二分決定グラフ(BDD)は，大規模論理関数を主記憶上に効率よく表現するデータ構造であり，1990年頃より，主にVLSI設計自動化の分野で盛んに研究開発されてきた．近年，このBDDが，データマイニング·知識発見の分野においても活用できることがわかってきた．特に，ゼロサプレス型BDD (ZBDD)と呼ばれるタイプのBDDは，疎な組合せ集合を効率よく扱うことができるため，現実に扱われる多くのデータベースの解析処理に適している．本稿では，ZBDDを用いた頻出アイテム集合マイニングの技法や，様々なクエリを集合演算として処理する演繹データベースへの応用，アイテム集合に関する独立成分や対称成分を高速に抽出するアルゴリズム等，BDDを用いたデータマイニング·知識発見技術に関する最近の話題について述べる．