2017年4月 - 2020年3月
弱閉集合の代数的構造の解明と知識発見への応用
日本学術振興会 科学研究費助成事業 基盤研究(B) 基盤研究(B)
本研究は,自然言語データにおける本文とキーワードの関係,Webページ間のリンク構造における参照元と参照先の関係など,2つの離散値属性間の2項関係から部分関係を抽出することによる知識発見を対象とする.研究計画で設定した[課題1]~[課題5]のうち,本年度は,[課題1]閉集合が数学的に定義されているためノイズを許さないため実用に向かないことがある一方,密集合は実応用から提案されたためノイズを許容するものの数学的な定義がない,という相補的な点に着目し,密な部分関係を弱閉集合として集合論的に定式化する[課題3]の弱集合に対して,閉集合と同様の不動点意味論を構成する,[課題5]弱集合の効率的列挙アルゴリズムの開発と実用性検討,の3課題を中心に研究を展開したした.
[課題1]については,閉集合をグラフ理論のことばを用いれば,2部グラフの完全部分グラフという解釈が可能であることに着目し,グラフ理論における完全グラフの定義を弱めたk-Plexという概念を範として,弱集合を(k,l)-閉集合として定式化した.以下では弱集合を(k,l)-閉集合とよぶ.
そして,[課題3]の不動点を構成するための反復関数を,オリジナルの閉集合のための反復関数を修正して定式化した上で,(k,l)-閉集合と反復関数の不動点の関係を与えた.閉集合の場合は,反復関数の不動点と閉集合は1対1に対応するが,(k,l)-閉集合の場合は必ずしも1対1にはならないこと,そもそも反復関数が収束しないことがあることも示した.これらの結果をもとに,[課題5]に取り組み,閉集合の高速列挙アルゴリズムであるLCMを修正することにより,(k,l)-閉集合の列挙が可能であることを示した.このアルゴリズムは,理論上は高速な列挙が不可能な場合もあるが,現実の小規模データに対しては十分高速に列挙することを確認した.
[課題1]については,閉集合をグラフ理論のことばを用いれば,2部グラフの完全部分グラフという解釈が可能であることに着目し,グラフ理論における完全グラフの定義を弱めたk-Plexという概念を範として,弱集合を(k,l)-閉集合として定式化した.以下では弱集合を(k,l)-閉集合とよぶ.
そして,[課題3]の不動点を構成するための反復関数を,オリジナルの閉集合のための反復関数を修正して定式化した上で,(k,l)-閉集合と反復関数の不動点の関係を与えた.閉集合の場合は,反復関数の不動点と閉集合は1対1に対応するが,(k,l)-閉集合の場合は必ずしも1対1にはならないこと,そもそも反復関数が収束しないことがあることも示した.これらの結果をもとに,[課題5]に取り組み,閉集合の高速列挙アルゴリズムであるLCMを修正することにより,(k,l)-閉集合の列挙が可能であることを示した.このアルゴリズムは,理論上は高速な列挙が不可能な場合もあるが,現実の小規模データに対しては十分高速に列挙することを確認した.
- リンク情報
- ID情報
-
- 課題番号 : 17H01788
- 体系的課題番号 : JP17H01788