Document

アルゴリズム理論的な
データ近似へのアプローチ
とデータマイニング
ピラミッド階層構造構築を例にして
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)
確信度とサポート：ルールの評価基準
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
Rectangle containing
a given point p
Union of rectangles
stabbed at p
p
Rectangles containing 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
-1
3
2
1
4
3
-2
2
-1
3
3
2
0
-2
1
0
-1
-2
-2
-1
-1
-3
-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
G
t
Negative
weighted
nodes
Construction of G’ (an example)
1
-3
1
-2
1
3
2
s
1
1
3
1 3 2
2
t
1
-1
最大利得領域の計算 = 最小カットの手間
すべての階段の高さｔでの最大パラメトリック利得
領域の計算→プロセスの分岐手法を用いる
O(t(n,n) log N)時間アルゴリズム
あるtで高さ3t/2で
高さt/2で
2分探索で全
ての段を探す
どのような領域族なら良いか？
集合演算について閉じている領域族
グリッドの接続グラフの部分グラフのカッ
トの支配集合に対応していれば良い.
中心ｐを固定した星型領域の族
グリッド超曲面で切られた下半領域の族
-1
-1
-2
1
0
-2
1
2
2
-1
-1
2
2
0
2
-1
1
-1
2
-１
1
0
--3
-4
4
--4
-1
-1
-2
1
0
-2
1
2
2
-1
1
2
2
0
2
1
1
-1
2
--2
1
0
--3
-4
4
--4
まとめ
アルゴリズム理論的なデータ近似
自由度の高い、高精度の近似
欠点（？）：グリッドをベースにする
領域族に依存した最適化
利用法：
データの視覚化
ファジーな決定構造

Download Report