A02 計算理論的設計による知識抽出モデルに関する研究 徳山　豪　　（東北大学） 塩浦昭義　 （東北大学） 全眞嬉　　　（東北大学） 河原林健一（東北大学→NII)

研究の目的 知識抽出システムでの計算理論的設計や解析の手法を探る 計算困難性を打破するためのモデルの検討 　知識抽出：　データマイニングだけではない 　計算幾何学でのパターン抽出 　Voronoi図：　点集合データ→理解しやすい知識形態 全列挙→マイニング→最適化　　（目的がはっきりするに従い） 計算困難性を打破するためのモデルの検討 　入力の性質を利用した高速アルゴリズム パラメトリック複雑度 アルゴリズム的グラフマイナー理論 　数理経済学での価格決定のモデル 　離散凸解析　

プロジェクトと成果（2004－2007） １： 最適曲面近似とデータマイニング（直接のテーマ） ２： Voronoi図とZone図 １：　最適曲面近似とデータマイニング（直接のテーマ） 　全，徳山+浅野，加藤他 　Journal：5（Algorithmicaなど）　Conf（ISAACなど）：6 ２：　Voronoi図とZone図 　徳山＋浅野,Matousek他 Journal ：2（SICOMP, Adv. Math), Conf： 2 (STOC, SODA) ３：　パラメトリック複雑度 　徳山＋Halldorsson他 　Journal： 2（TCSなど）,　Conf： １（WADS)，IETA：2

プロジェクトと成果：２ ４： アルゴリズム的グラフマイナー理論 ５： オプションの価格決定でのモデルと解析 ６： 離散凸解析 ４：　アルゴリズム的グラフマイナー理論 　河原林＋海外研究者等 　Journal 多数（30くらい）、Conf 多数　 　STOC２、FOCS，SODA、ISAAC（Best Paper) ５：　オプションの価格決定でのモデルと解析 　塩浦、徳山 　Journal ：2（Algorithmica, IPL),　Conf ：1 ６：　離散凸解析 　塩浦＋室田他 　Journal 多数（10くらい） ７：　その他：　アドホックネットワークのモデルなど

最適曲面近似についての進展 非負行列データ： A = (a(i,j) ) i,j = 1,2,..,n 　2次元格子上の関数と思う Aの単峰近似：　F = (f(i,j)) : 単峰関数 Fの水平切断が「良い形」　 Minimize ｜A－F｜2　：　L2距離　 等高線で書かれた地図から「山」を切り出す　

　単峰近似　（1次元（上図）　2次元（下図））

単峰近似の手法 グラフの「最大重み支配閉包」問題に帰着する 最大流問題に帰着（多項式時間解法） G ＝（V, E): 有向グラフ、 頂点に重み w(v) （負の重みもある） G　の支配閉包：　頂点の集合X 　uがXの要素で(u，v)が有向辺ならばvもXの要素 　最大重み支配閉包　（山の等高線に対応） 　重み和が最大になる支配閉包　 最大流問題に帰着（多項式時間解法）　

中心点に向いた格子グラフでの支配閉包 -1 -2 1 1 1 -1 1 2 1 -2 2 -1 2 - - 3 1 2 2 - 4 4 - 1 2 - - 2 - - 4

最近の進展（１） 「山」の水平断面として自然なのは？ 星型領域（輪）についての解法の提案 星型領域 （技術的困難があった） 　星型領域　（技術的困難があった） 　凸領域　（未解決） 　星型領域の輪 星型領域（輪）についての解法の提案 　難しさ：　グリッドでの星型領域は何か？ 　星型領域：　各点から中心点へ向かう直線分を含むような領域 　グリッドでの「直線分」の定義が難しい 通常の定義だと「星型」らしくなくなる

グリッド星型領域を定めるグラフ（木） （Martin Noellenburg製作）

最近の進展（２） 多峰近似は多項式時間で出来るか？ 2つのグラフの最大重み支配閉包和問題 頂点集合Vと重み（入力行列の要素に対応） G=(V, E), G’ =(V, E’) ： V上の有向グラフ　 　2つの山に対応 X:　Gでの支配閉包，Y:　G’での支配閉包 X∪Y　の形で最大重みのものを求める　 NHCの会議（06調布）でのOpen Problem　 NP困難か？G, G’が根付き有向木の場合にはどうか？ 木の場合は、支配閉包＝根付き部分木　

残念ながらNP困難 2つの根付き有向木（グリッドの部分木に向きをつけたもの）に対してすらNP困難 　MAX2SATを帰着する 　→　現在の定式化だと2次元での多峰近似は難しそう 多峰近似問題の近似アルゴリズム？？ 　最大支配閉包和の形だと近似できない

S3 S3 S2 S2 S1 S1 S3 S3 S2 S2 S1 S1 S1 S1 S2 S2 S3 S3 S1 S1 S2 S2 S3 M+N S3 ∨S2 S3 -N 1/2 S3 ∨S1 S3 ∨S2 S3 -N 1/2 1/2 S2 ∨S3 S2 -N 1/2 S2 ∨S1 S2∨S3 S2 -N 1/2 1/2 S1 -N S1 -N 1/2 1/2 S1∨S3 S1∨S2 S3 -M -M M -N M+N S3 -M M -M -N M+N S2 -M -M M -N M+N S2 -M M -M -N M+N S1 -M -M M -N M+N S1 -M M -M -N M+N -M -M -M -M -M -M S1 S1 S2 S2 S3 S3 S1 S1 S2 S2 S3 S3

総重み＝ ｎM＋MAX２SAT S3 S3 S2 S2 S1 S1 S3 S3 S2 S2 S1 S1 S1 S1 S2 S2 S3 S3 M+N M+N M+N M+N M+N M+N S3 ∨S2 S3 -N 1/2 S3 ∨S1 S3 ∨S2 S3 -N 1/2 1/2 S2 ∨S3 S2 -N 1/2 S2 ∨S1 S2∨S3 S2 -N 1/2 1/2 S1 -N S1 -N 1/2 1/2 S1∨S3 S1∨S2 S3 -M -M M -N M+N S3 -M M -M -N M+N S2 -M -M M -N M+N S2 -M M -M -N M+N S1 -M -M M -N M+N S1 -M M -M -N M+N -M -M -M -M -M -M S1 S1 S2 S2 S3 S3 S1 S1 S2 S2 S3 S3