June 3,2013

Discovery of Spatial Association Rules in Geographic Information Databases
Krzysztof Koperski , Jiawei Han
Advances in Spatial Databases, 4th International Symposium(SSD), 1995
pp.47‐66 (June 3,2013, 園田担当) Abstract
• 空間データマイニング
空 デ タ
グ
– 空間DBにおける知識の発見
空間
おける知識 発見
• 空間相関ルール
– (非)空間predicateの相関関係
(非)空間 di
の相関関係
– 強い相関ルール=高頻度での共起関係を含有
• 空間DBからの相関ルールの効率の良い発見
– 多量データの近似計算
– 上記から詳細なルールの発見
1 Introduction
1.Introduction
• 膨大な量の(非)空間データを運用
膨大な量 非 空 デ タを
– リモートセンシング
リ
ンシング
– データの自動収集ツール
• 従来の検索ツール
– 単にストレージを用いて明示的にデータを貯蓄
– 大きな問題が有
• 空間的関係の暗黙的抽出
• 他のパタ
他のパターン(DBに存在しない)の発見
ン(DBに存在しない)の発見
1 Introduction
1.Introduction
• DM手法
法 = 盛んに議論
盛
議論
– 強い相関関係
強 相関関係
– 独立的なルール
– 属性指向帰納
– 判別ルール
– どの研究も空間DBへの適用が有望
研究
間
適用 有
1 Introduction
1.Introduction
• 空間DMのカテゴライズ
空
ゴ
ズ
– A spatial characteristic
p
• 一般的な空間関係データ
• Ex)地域ごとの気象パターン
Ex)地域ごとの気象パタ ン
– A spatial discriminant rule
• 空間関係間の対照、比較
空間関係間の対照 比較
• Ex)二つの地域間での気象パターンの比較
– A spatial association rule
A
ti l
i ti
l
• 別の特徴により関連付けられる特徴
• Ex)カナダ/USの国境があれば、側にカナダの大都市がある
カナダ
国境があれば 側 カナダ 大都市がある
1 Introduction
1.Introduction
• A spatial characteristic rule
• A spatial discriminant rule
A spatial discriminant rule
– 深く研究
• A spatial association rule
– まだまだ不足
• 本稿の焦点:A spatial association rule
本稿の焦点 A
i l
i i
l
– トランザクションDBの相関ルールの発見手法を空
間関係に拡張
1 Introduction
1.Introduction
2.Previous Work Related to Spatial Data Mining
• 2.1 Statistical Analysis
– 一般的手法
般的手法
• 空間的現象を把握
• 最適化が可能
– 非現実な影響
• 統計的に独立であると仮定
– 空間的表現の難化
空間的表現 難化
– 計算コストが高い
2.2 Generalization‐based Spatial Data Mining
• 空間DM手法の主流
– 特性やデータを’各レベル’で解析
– 属性指向帰納[Lu&Han 1993]
•
•
•
•
ハイレベルをコンセプトに(非)空間関係を描写
2STEPで実行
(1) The nonspatial‐dominant generalization
(2) The spatial‐dominant generalization
属性帰納指向(Attribute‐Oriented induction)
• (1)Nonspatial‐dominant generalization
– 各オブジェクトの属性の一般化
各オ ジ ク
属性
般化
• 数値データ : レンジや高度な表現
– Ex) ‐9°⇒
)
レンジ : ‐10~0 高度な表現 : cold
• シンボルデータ
– Ex) ポテト 甜菜 ⇒ 野菜
• 一般化された非空間データが同一の高レベルを保有
• 空間的に同一なポインタを持つことが可能
野菜
ポテト
同一ポインタ
野菜
甜菜
属性帰納指向(Attribute‐Oriented induction)
• (2)Spatial‐dominant generalization
– 何らかのデータ構造を用いて階層構造を展開
何ら
デ タ構造を用
階層構造を展開
• R‐tree
• Quad‐tree
Quad tree
– 一般化された空間関係のある非空間データを合
体
野菜
野菜
ポ
ポテト
甜菜
菜
野菜
ポテト
甜菜
2 3 Other Relevant Studies
2.3 Other Relevant Studies
• 画像DBのマイニング
像
グ
– Ex)空
)空
• 各オブジェクトの基本属性を抽出
– エリア 光度 ピーク光度の位置 モーメント
• 専門家によるテストデータを用いて決定木で分類
銀
• 空objj ⇒ 星class ,, 銀河class
• Relational Database
– TDのDBから相関ルールを抽出
TDのDBから相関ル ルを抽出
– Ex) butter ⇒ bread (90%)
• バターを買った客は90%の確信度でパンを買う
3 Spatial Association Rules
3 Spatial Association Rules
• 属性帰納指向の問題
性 納指向
– 空間オブジェクトのpredicateを非考慮
空間オ ジ ク
p
を非考慮
• 空間/空間 空間/非空間
• Ex)adjacent_to
Ex)adjacent to , near_by
, near by , inside , close_to
, inside , close to ,intersecting
– 空間的相関ルールを補完
•
•
•
•
空間的条件から非空間的結果
Is_a(x,house)∧close_to(x,beach) → is_expensive(x)
(非)空間的条件から空間的結果
Is_a(x,gas_station) → close_to(x,highway)
3 Spatial Association Rules
3. Spatial Association Rules
3 Spatial Association rules
3. Spatial Association rules
3 Spatial Association rules
3. Spatial Association rules
• Example 1 : British Columbiaの相関ルール
相
– 各空間オブジェクトを定義
各空間オ ジ ク を定義
– 属性geo:地図に使われる点や線
属性g
図 使わ
点 線
– 属性type:空間オブジェクトの種類
• Ex)road.type
Ex)road type : national highway , local higiway
: national highway local higiway , street
street
– 省略したフィールド:他の情報を含有
3 Spatial Association Rules
3. Spatial Association Rules
• 仮定
仮定:BCの地図内の大きな町の傍にある各オ
地
大きな
傍 ある各
ブジェクトを探索
3 Spatial Association Rules
3.Spatial Association Rules
• Data、predicate毎に階層構造を設定
毎 階 構造を 定
– 多次元相関ルールを容易に処理
多次元相関ル ルを容易 処理
Data階層構造
predicate階層構造
big city
big_city
Large_town
M_size_city
town
Small_town
・・・
4. A Method for Mining Spatial Association Rules
• 4.1 An Example of Mining Spatial Association p
Rules : Example 2
– 例1の空間マイニング手法
– 関連データセットはDMクエリを適用
• 導出されるデータセットはBCに含有
– 町とその他の属性(town,road,etc)のg_close_toは
町とその他の属性(
d )の l
は
高速アルゴリズムで算出
• MBR,R‐tree.etc
– 各obj.のサポートを計算し、閾値でスクリーニング
• Ex)Mine
4.1 An Example of Mining Spatial Association Rules : Example 2
Association Rules : Example 2
• 空間関係の詳細な計算
– 表1よりpredicateを含めた表2を生成
– トップレベルから頻度を算出
• Ex)<adjacent_to Water> <intersects Road>等をカウント
• カウント後閾値未満であれば除去
– 1‐predicate後、アプリオリ的にk‐predicatesを生成
1
di
後 アプリオリ的にk
di
を生成
–あ
4.1 An Example of Mining Spatial Association Rules : Example 2
Association Rules : Example 2
• 相関ルールを直接算出
相
を直接算
– <intersects,highway> = 29
, g
y
– <adjacent_to,water><intersects,highway> = 25
4.1 An Example of Mining Spatial Association Rules : Example 2
Association Rules : Example 2
• 下位レベルも同様に探索
位 ベ も 様 探索
– レベル1で最小サポート以下のpredicateは無視
ル 最小サポ
以下 p
は無視
4.2 An Algorithm for Mining Spatial Association Rules
4.2 An Algorithm for Mining Spatial Association Rules
• Output:相関ルール
相
• Method
4.2 An Algorithm for Mining Spatial Association Rules
• 空間検索を実行
– Task_relevant_DBに各オブジェクトを格納
T k l
DBに各オブジ クトを格納
• Coarse_level(high level)でのカウント
– 効率的な空間アルゴリズムで探索
– Coarse_predicate_DBに格納
• サポートを計算し、閾値でスクリーニング
サポートを計算し 閾値でスクリーニング
– Large_coarse_predicate_DBに格納
4.2 An Algorithm for Mining Spatial Association Rules • Fine_Level(low‐level)での探索
– Large_Coarse_predicate_DBに含まれるpredicatesの
み探索 カウント 閾値未満を除去
– 最適手法はApriori的探索
最適手法は
的探索
• 相関ルールを生成
– 1.各レベルの最大のkを獲得
各
最
を獲得
– 2.レベル1の1‐predicateから関連するレベル2の1‐
predicateを獲得
– 3.その際、各レベルのk‐predicateを獲得
4.2 An Algorithm for Mining Spatial Association Rules 4.2 An Algorithm for Mining Spatial Association Rules 4 3 A Discussion of the Algorithm
4.3 A Discussion of the Algorithm
• アルゴリズムの正当性、効率性を評価
ゴ ズ
性 効率性を評価
• Correctness of the algorithm
Correctness of the algorithm
– STEP1:全てのデータを抽出する空間DMプロセス
• 完全性、正当性に準拠
完全性 正当性に準拠
– STEP2:Coarse_levelでの空間計算
• 完全性、正当性に準拠
– STEP3:最小サポートによる除去
– STEP4:Fine_levelでの空間計算
• STEP2同様完全性、正当性に準拠
– STEP5:アプリオリに基づく相関ルールの抽出
4 3 Discussion of the Algorithm
4.3 Discussion of the Algorithm
4 3 Discussion of the Algorithm
4.3 Discussion of the Algorithm
• DMの実行時間
実行時
4 3 Discussion of the Algorithm
4.3 Discussion of the Algorithm
• DMの実行時間
実行時
5 Discussion
5 Discussion
• 5.1 Major Strengths of the Method
– ユーザのクエリによるDMに焦点
• 探索するobj.や関係を指定
• データセットを限定、効率的な処理
– ユーザが操作可能な対話的マイニング
– 候補セットの削減による計算量
– 詳細な空間計算
• 一度の実行で多重レベルでのマイニングに利用
– 最適化
• Aprioriによる効率の良い探索