アルゴリズム理論的な データ近似へのアプローチとデータマイニング アルゴリズム理論的な　　データ近似へのアプローチとデータマイニング ピラミッド階層構造構築を例にして Pictures from web page of Institute of Egyptology, Waseda University, Japan

データマイニング データベースからの知識抽出 関係データベース 属性： 収入、年齢、血圧、血液型、性別など 　属性：　収入、年齢、血圧、血液型、性別など 　タプル(データ行）：　属性値のベクトル 属性間の一般的（統計的）な関連法則を知りたい 　目的：　自動診断、自動推定、自動調整システム 　既知の属性値から未知の属性値を推定する 　制御可能な属性値を変更して目的属性値を改良する 法則は、正確で判りやすく，汎用性があるものが良い

カテゴリー属性結合ルール：簡単な法則の形態 （Blood ＝ AB) ⇒ （Car = Honda) 　(Blood =AB) ∧ (Car = Honda) ⇒(Accident = No) 高速生成アルゴリズム　Aggrawal　他　１９９３ 　数値結合ルール 　（400<Income<800) ⇒　（Car　= Honda) (500 < Income) ∧(Age > 25) ⇒（Accident<0.01) ((Age, Income) ∈R)　⇒　(Accident　< 0.01)

((Age, Income) ∈R) ⇒ (Accident= No) 確信度とサポート：ルールの評価基準 　A　⇒　C ((Age, Income) ∈R)　⇒　(Accident= No) サポート：　左辺が成立する確率　Prob(A=yes) ヒット：両辺とも成立する確率Prob（A∧C　＝yes) 確信度：　　　ヒット/サポート　　　　　　　　　　　　Prob（A∧C　＝yes) / Prob(A=yes) サポートが大きく、確信度も大きいルールが良い

Output of SONAR data mining system ( System for Optimized Numeric Association Rules) Given a database that contains 3.54% of unreliable customers ( Age, Balance) ∈ Ｒ ⇒ ( CardLoanDelay = yes) R contains about 10% of customers and maximizes the probability (14.39%) of unreliable customers.

福田－森本－森下－徳山　の手法 ‘96 ((Age, Income) ∈R)　⇒　(Accident= No) サポートも確信度も高い領域Rを求める Support（R)　： Rに入るデータ数 Hit （R)：　Rに入るヒットデータ数 パラメトリックな利得 Gain(R,t) = Hit （R)　– t ・ Support(R) 良いグリッド領域族の利用 パラメトリック利得を最大化するRの高速計算 良いパラメタ　t の自動推定

Output of SONAR data mining system ( System for Optimized Numeric Association Rules) Given a database that contains 3.54% of unreliable customers ( Age, Balance) ∈ Ｒ ⇒ ( CardLoanDelay = yes) R contains about 10% of customers and maximizes the probability (14.39%) of unreliable customers.

問題点　と解決 　領域Rの内部と外部に分けるルールは強すぎる　（データの位置情報の消失、過学習） 　3　つ以上の条件属性を考えると計算量が爆発する　(次元の制限） 最適な階層構造でのデータの近似 統計的なアプローチ 計算理論的なアプローチ

Pyramidic (or layered) rule

数学的定式化 Input: 　ｄ変数サポート関数μ、確信度関数　ρ 　　　　　d次元のグリッド領域族　F Output (階層ルール）: 　確信度関数の近似　f 単峰、もしくは与えられた数のピークを持つ 水平スライス（｛ｘ：f（x）＜h｝）がFに属する 目的: f とρ の（μを測度にする）L2距離最小化 確信度による“玉ねぎ”構造

サポート関数が定数関数なら、地形図をならしてピラミッド(山）に最適近似することに対応

困難と解決 　1次元なら線形時間で解ける 　目的関数を水平切りと垂直切りで考える 　リーマン積分とルベーグ積分のようなもの 　2次元以上で？ 　解決策 良いグリッド領域族を定義する パラメトリック手法（高さがパラメタ） グラフアルゴリズムの利用

What is the region family for this pyramid ? U(p)= ピクセルp を含む長方形の和集合たちの族　（stabbed union of rectangles at p)

p p Rectangle containing a given point p Rectangles containing p Union of rectangles stabbed at p Corresponding pyramid

　ｄ次元　（ｄ個の数値属性）の階層構造の計算 Fd(p) = d次元voxel グリッドにおいて、voxel p を含む軸方向長方形の和集合たちの族 定理. Fd(p) に関する最適階層ルールは 　　　　O(t(n,n) log N) 時間で計算される, ここで t(n,m) は n頂点m辺の有向重みつきグラフの　 minimum s-t cut の計算時間. T(n,n)=O(n 1.5 log N) (Goldberg-Rao 97) N: weight sum=database size

出力の高さｈでのスライスの計算 t 4 4 4 4 3 3 1 1 - - 1 1 -1 3 3 3 3 - - 1 1 3 3 -2 2 2 - - 1 1 - - 3 3 2 2 2 2 - - 2 2 - - 4 4 1 1 - - 1 1 - - 2 2 - - 2 2 - - 4 4 s グリッドの接続グラフに、p への向きと、パラメトリック利得情報から得られる頂点重みをつけたグラフG　で、支配集合が最大重みを持つカットを求める

The cut in G minimizing the sum of node weights of dominated vertices = minimum s-t cut in a modified directed graph G’ (Hochbaum(01)) Positive weighted nodes s Negative weighted nodes G t

Construction of G’ (an example) -1 2 3 1 -2 -3 s 1 1 2 3 1 2 3 1 t

すべての階段の高さｔでの最大パラメトリック利得領域の計算→プロセスの分岐手法を用いる 最大利得領域の計算　=　最小カットの手間 すべての階段の高さｔでの最大パラメトリック利得領域の計算→プロセスの分岐手法を用いる O(t(n,n) log N)時間アルゴリズム 2分探索で全ての段を探す 　あるtで 高さ3t/2で 高さt/2で

　どのような領域族なら良いか？ 集合演算について閉じている領域族 グリッドの接続グラフの部分グラフのカットの支配集合に対応していれば良い. 中心ｐを固定した星型領域の族 グリッド超曲面で切られた下半領域の族

-1 -1 -2 -1 1 -1 1 2 1 -2 2 2 -1 - - 3 1 2 2 - 4 4 - 1 2 -１ - - - 4

-1 -2 1 1 1 -1 1 2 1 -2 2 -1 2 - - 3 1 2 2 - 4 4 - 1 2 - - 2 - - 4

まとめ アルゴリズム理論的なデータ近似 自由度の高い、高精度の近似 欠点（？）：グリッドをベースにする 　　　　　　　領域族に依存した最適化 利用法：　　データの視覚化　 　　　　　　　ファジーな決定構造