高次元ブール値テンソルデータからの多項閉集合を用いた知識発見

点击翻译按钮获取中文摘要

本年度はまず課題２（多項閉集合の高速列挙）に取り組んだ．基本方針は，２次元ブール値データから２項閉集合を生成し列挙するアルゴリズムを利用しながら，高次元ブール値データから多項閉集合を列挙するアルゴリズムを設計し，プログラムとしての実装を行う，というものである．２項閉集合は組合せ集合を列挙ためのアルゴリズムであるZDDを利用して実装できることが知られている．さらにZDDは集合間の演算を高速に計算できるため，本研究ではZDDを利用することとした．また本年度は３次元ブール値データを対象とした．開発した列挙アルゴリズムはZ-TCAと名付けている．２項閉集合を生成し列挙するためには，２項閉集合が集合から集合へ定義された２つの写像をを合成した写像の不動点になるという性質を用いる．このれらの写像を２次元以上に拡張することは可能ではあるが，多項閉集合が不動点と一致するという便利な性質は備えていないものの，次元を1次元ずつ減少させることにより２項閉集合の列挙に還元できる，という性質がある．集合から集合への写像は集合の演算として表現できるため，ZDDを用いれば多項閉集合の生成と列挙が高速化可能となる．この集合演算のZDDによる実装を設計し，従来研究で提案されていた「逐次的な次元数削減と集合間演算によるアルゴリズム」の実装に適用した結果，素朴な集合演算の実装を利用した場合に比して，実データを用いた計算機実験において３倍の高速化が達成された．さらに課題３にも取り組んだ．年度当初の計画では，生命システム機能分析のためのデータセット集積体であるKEGGデータベース中のデータセットを使う予定であったが，この研究に利用するには大規模なフォーマット変換が必要であることから断念し，Wikipediaから生成された知識グラフを利用することとし，知識グラフから有用な３項閉集合を抽出する実験を行った．