2011/09/30 列挙学校（再放送）
有村博紀，北大
改訂版ver12: 2011/09/30
列挙学校：第４コマ
パターンマイニングにおける
列挙アルゴリズム
有村 博紀
北海道大学
大学院情報科学研究科
教材PPT:
http://www-ikn.ist.hokudai.ac.jp/~arim/
rekkyo/rekkyo2011.ppt
1
自己紹介
第１回2008年9月12日
GCOE公開講座
氏名： 有村 博紀（ありむら ひろき）
九州大学理学部物理学科を卒業(1988年卒)
北海道大学大学院 情報科学研究科 (2004～)
妻あり子供二人ありの46才
A
2004年から北海道在住
B
A
A
主な研究経歴
C
B
A
A
B
Motif with wildcards:
0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21
ABCABRRABRABCABABRABBC
pos = 0
pos = 7
pos = 15
An integer 0 (quorum)
ABoAB
=3
A motif
複雑・小規模
機械学習
データマイニングアルゴリズム
知識発見
情報検索アルゴリズム
単純・大規模
大規模離散構造データ
（系列，木，グラフ，．． ）を効率良く扱いたい
2
今回の講義：目次
2011/09/30 列挙学校（再放送）
有村博紀，北大
４コマ目の目的：
データマイニングを題材に
列挙はどんなことに使えそうか？
応用分野では，列挙はどのように
使われているか？
データマイニング(DM)と機械学習に
おける列挙に関連した話題を提供
DMの歴史も少し紹介
http://www.sigkdd.org/kdd/1995/poster/kdd1995-poster-thumb.jpg
3
目次
2011/09/30 列挙学校（再放送）
有村博紀，北大
パート1: データマイニングと頻出集合発見
データマイニング
頻出集合マイニング
パート２: 構造データのマイニング
木とグラフのマイニング
列挙によるパターンのマイニング
関連した話題
4
2011/09/30 列挙学校（再放送）
有村博紀，北大
列挙学校：第４コマ
パート１:データマイニングと頻出集合発見
有村 博紀
北海道大学大学院 情報科学研究科 コンピュータサイエンス専攻
email: {arim,kida}@ist.hokudai.ac.jp
http://www-ikn.ist.hokudai.ac.jp/~arim
．
5
2011/09/05, 富士通研勉強会，北海道大学, 有村博紀
データマイニングとは
大量のデータから人間にとって有用なパターンや
規則を半自動的にとりだす方法の研究
1990年代半ばから研究が盛んになった
• Apriori algorithm [Agrawal, Srikant,
3. 発見した
知識の利用
VLDB1994]
潜在的には古くからある研究の集大成．
•
ただし，大量データに対する効率的計算に重点
2. 知識を
パターンや規則と
して発見
機械学習・数理統計学・
データベース技術の境界分野
CC
H XX
H
H
知識
Knowledge
1. 対象領域の
理解・データ
の前処理
半構造データ
Semi-structured Data
CC
H XX
半構造パターン発見
Pattern Discovery
6
Backgrounds
2011/09/30 列挙学校（再放送）
有村博紀，北大
データマイニングのプロセスの全体
1.対象領域の理解
2.データ集合の前処理
3.パターンの発見（狭義のデータマイニング）
4.得られたパターンの解析
5.解析結果の利用
8
私のデータマイニングのイメージ
2011/09/30 列挙学校（再放送）
有村博紀，北大
情報検索
キーワード検索
Finding/Discovering hidden
knowledge from massive data
直接目で見る
<dallers>
<wheat>
<u.s.>
<shipping >
<gulf >
<sea men>
<strike >
<port >
<ships>
<the gulf >
<vessels >
<iranian >
<iran >
<attack >
データマイニング
<silk worm
<strikemissile>
>
9
データマイニングの研究動向
パターン発見
予測学習・自動分類
構造マイニング
トランザクションデータか
ら共通して出現する規則
性を発見する
不完全なデータから，
未知の規則を学習する
SVM [Vapnik ‘96],
非定型構造データから特
徴的な部分構造を規則
性を発見する
頻出パターン発見
[Agrawal et a. ‘94]
Boosting [Shapire & Kearns
グラフマイニング[Washio
最適化マイニング [森下
’96, ’98, ‘00]
C4.5 [Quinlan ‘96]
‘96]
確率モデリング
クラスタリング
高次元大規模データから
不確実な現象を予測・モ
デル化する
データを類似したものど
うしグルーピングする．
大規模・不完全なデータから
の高速クラスタリング
K-means, CLARANS,
DBSCAN
CC
H XX
H
H
2011/09/30 列挙学校（再放送）
有村博紀，北大
大規模データ
H XXCC
H
H
有用な規
ベイジアンネットワーク
則・パター
[Pearl ’90s]
ン・
知識
データマイニ
ング
HMM [Asai], MCMC, ベイ
ズ推定・MDL・AIC
& Motoda ‘00], [Zaki ’02],
[Uno, Asai, Arimura, ’02,
‘03]
新しいタイプの
データマイニング
テキストマイニング
自然言語テキスト
情報抽出
意味マイニング
ストリームマイニング
センサー監視
近似統計処理
10
10 Algorithms in Data Mining
情報知識ネットワーク特論 DM1
In an effort to identify some of the most influential algorithms that have been
widely used in the data mining community, the IEEE International Conference
on Data Mining (ICDM) identified the top 10 algorithms in data mining for
presentation at ICDM '06 in Hong Kong.
• C4.5
- 決定木
• PageRank
- スペクトル
• k-Means
- クラスタリング
• AdaBoost
- 計算学習
• SVM
- 計算学習
• kNN
- 統計学習
• Apriori
- 頻出集合
• Naive Bayes
• EM
- 統計学習
• CART
- 統計学習
- 計算学習
X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, P. S.
Yu, Z.-H. Zhou, M. Steinbach, D. J. Hand and D. Steinberg: Top 10 Algorithms in Data Mining,
Knowledge and Information Systems, 14(2008), 1: 1-37.
11
これからのデータマイニング
「ポストペタスケール時代」
「ビッグデータ」
人間
(IBMTM
:-)
• 超大規模で
• 不均質かつ不完全な
• 非構造データ
どうやってあつかうか？
大量のデータ
クラウド
多数のＣＰＵ
高速なネットワーク
膨大な計算
12
「集中」
さまざまなデバイス
多様な人間活動と応用
多様で非均一な時空間
不完全で複雑なデータと情報
「分散」
2011/09/30 列挙学校（再放送）
2011/09/30 列挙学校（再放送）有村博紀，北大
情報に関する最近の話題
ワトソン君
•
•
•
•
IBMリサーチ (2011/02/16)
クイズ番組で人間に勝利！
１００万冊の本を読んで回答
人工知能と自然言語，アルゴリズム，
検索の技術で
クラウド計算
世界中の情報を計算！
米国の人気クイズ番組「ジョパディ！」のワトソン君
クイズ王に挑戦中
From http://www06.ibm.com/ibm/jp/lead/ideasfromibm/watson/
From geek.com: Google server firm
http://www.geek.com/articles/chips/up-next-for-googleenterprise-wars-2009078/
データマイニング
データマイニング
大量のデータから有用なパターンや規則を
半自動的にとりだす方法の研究
1990年代半ばに顕在化．定型データを対象とする
3. 新たな
知識の構築
非構造／半構造データ
多様な構造をもつ膨大なデータ
2. 知識を
パターンや規則と
して発見
新しいデータマイニング技術が必要!
知識
Knowledge
文科省科研費 特定「発見科学」(H10-H12),
「情報学」(H13-H17), 基盤研究B(H12-H14,
H15-H17)等
文科省科研費特別推進研究（平成１７年～１
９年）「知識基盤形成のための大規模半構造
データからの超高速パターン発見」
文科省GCOEプログラム「知の創出のための
14
次世代情報基盤拠点」（H19-H23）
CC
H XX
H
H
知識を有機的に
つなげる
半構造パターン発見
Pattern Discovery
半構造データ
CC
Semi-structured HData
XX
H
データマイニングの二つの柱
「列挙と最適化は車の両輪」 by S. Minato
と
列挙
最適化
湊真一先生
（北大＆ERATO）
データに含まれる
パターンを網羅的に
見つける
目的関数を最大化す
るパターンを
求める
パターン発見手法
機械学習手法
相補的な関係
2011/09/30 列挙学校（再放送）
有村博紀，北大
パート1の１：
頻出集合マイニングの枠組み
～ (Agrawal & Srikant,1994)
16
Backgrounds
Frequent Itemset Mining
Finding all "frequent" sets of elements (items)
appearing no more than σ times in a given
transaction data base.
Introduced by Agrawal and Srikant [VLDB'94]
One of the most popular data mining problem
Basis for more complicated / sophisticated data
mining problems
動機： 結合ルールマイニング
Association Rule Mining [Agrawal 1993/1994]
• Finding combination of “items” frequently appearing
in a given database
• トランザクションデータ
• バスケットデータ
• 二値データベース
• レコード/タプル
• バスケット
ID
Chips
Mustard Sausage Softdrink
Beer
001
1
0
0
0
1
002
1
1
1
1
1
003
1
0
1
0
0
004
0
0
1
0
1
005
0
1
1
1
1
006
1
1
1
0
1
007
1
0
1
1
1
008
1
1
1
0
0
009
1
0
0
1
0
010
0
1
1
0
1
トランザクション／レコードの意味
「 レコード003の顧客は，ポテトチップとソーセージを一緒に買った」
•カラム/属性
•アイテム
動機： 結合ルールマイニング
Frequent Itemset X = { Mustard, Sausage, Beer }
• with support/frequency 40%
ID
001
002
003
004
005
006
007
008
009
010
Chips
1
1
1
0
0
1
1
1
1
0
Mustard Sausage Softdrink
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
1
0
Beer
1
1
0
1
1
1
1
0
0
1
•アイテム集合 X
•Xの出現リスト
Occ(X) = {002, 005,
006, 010}
•Xの頻度（サポート）
freq(X) = |Occ(X)|
= 4/10 = 40%
アイテム集合 X の意味
X = 「マスタードとソーセージ，ビールを一緒に買う人」が全体の40％いた
頻出アイテム集合マイニング
Frequent Itemset Mining Problem
Given: A database DB over a set Σ of items, and a number
σ≧0 called “minsup” (minimum support)
Problem: Find all itemsets X⊆Σ appearing in no less than σ
records of DB
20
2011/09/30 列挙学校（再放送）
有村博紀，北大
Definitions: Database
A set Σ = { 1, ..., n } of items (elements)
Transaction database
− A set T = { t1, ..., tm } of subsets of Σ
− Each subset t ⊆Σ is called a tuple (record)
Transaction database
Alphabet of items
I = {1,2,3,4}
id
1
2
3
tuples
1, 3
2, 4
1, 2, 3, 4
4
1, 2, 4
21
21
Definitions: Itemset lattice
2011/09/30 列挙学校（再放送）
有村博紀，北大
Item set: any subset X ⊆ Σ = { 1, ..., n }
(Item) set lattice L = (2Σ, ⊆)
− The power set 2Σ = { X : X ⊆ Σ }
− The subset relation⊆over 2Σ
Example:
The set lattice
forΣ = {1,2,3,4}
22
Definitions: Frequent sets
2011/09/30 列挙学校（再放送）
有村博紀，北大
An itemset X appears in a tuple t: X ⊆ t
The occurrence of X in a database T:
Occ(X, T) = { t ∈ T : X ⊆ t }
The frequency of X: Fr(X, T) = | Occ(X, T) |
Minimum support (minsup): an integer 0≦ σ ≦|T|
X is σ-frequent (frequent) in T if Fr(X, T) ≧ σ.
Alphabet of items
I = {A,B,C,D}
Occurrences and frequences of itemsets
Occ(3, T) = {1, 3}
Fr(3, T) = 2
Occ(24, T) = {2, 3, 4},
Fr(24, T) = 3
Transaction database
id
1
2
3
4
tuples
1, 3
2, 4
1, 2, 3, 4
1, 2, 4
23
23
Definitions: Frequent sets
2011/09/30 列挙学校（再放送）
有村博紀，北大
The occurrence of X in a database T:
Occ(X, T) = { t ∈ T : X ⊆ t }
X is σ-frequent (frequent) in T if Fr(X, T) = | Occ(X, T) | ≧ σ.
minsupσ= 2
Frequent
sets
∅,
1, 2, 3, 4,
12, 13, 14,
23, 24, 124
1
Frequent sets
t1
○
○
t4
t5
3
○
4
5
○
○
t2
t3
2
○
○
○
○
○
○
○
○
○
database
The itemset lattice (2Σ, ⊆)
24
Definitions: Problem
2011/09/30 列挙学校（再放送）
有村博紀，北大
Frequent Itemset Mining Problem
Given: A transaction database T and a non-negative
integer 0≦ σ ≦|T|
Task: Enumerate all "frequent" itemsets X in T
that have frequency at least σ (Fr(X)≧σ)
F: the class of all σ-frequent itemsets
The number |F| of solutions is exponential in the
number n of items.
a typical enumeration problem.
25
2011/09/30 列挙学校（再放送）
Computational Complexity of Data Mining
Algorithms
有村博紀，北大
Modeling data mining as enumeration
Idea: Mesure the computation time per solution
Input size M
Output-polynomial (OUT-POLY)
Total time = poly(N, M)
Input
polynomial-time enumeration, or
amortized polynomial-delay
(POLY-ENUM)
Amotized delay is poly(Input), or
Total time = M·poly(N)
Algorithm
Output size M
Outputs
Time
Delay D
polynomial-delay (POLY-DELAY)
Maximum of delay is poly(Input)
Total Time T
+ polynomial-space (POLY-SPACE)
28
2011/09/30 列挙
Computational Complexity of Data Mining Algorithms
学校（再放送）
有村博紀，北大
Modeling data mining as enumeration
Idea: Mesure the computation time per solution
Ultimate Goal:
Input size M
Output-polynomial (OUT-POLY)
To design
Total time is poly(Input, Output)
polynomial delay and
polynomial space algorithm
polynomial-time enumeration
problem
(POLY-ENUM) for a given data miningOutputs
Input
Algorithm
Output size M
Amotized delay is poly(Input), or
Total time is Output·poly(Input)
Time
Delay D
polynomial-delay (POLY-DELAY)
Maximum of delay is poly(Input)
Total Time T
+ polynomial-space (POLY-SPACE)
29
2011/09/30 列挙
学校（再放送）
有村博紀，北大
パート1の2：
頻出集合マイニングの
幅優先(BFS)型アルゴリズム
～ Aprioriアルゴリズム (Agrawal & Srikant,1994)
～ 頻出集合マイニングの最初のアルゴリズム
Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules
in Large Databases. VLDB 1994: 487-499.
～ データマイニングで最も有名な論文の一つ
(Google Scholarでの引用数: 11215件, Sep .2011）
30
頻出集合マイニング
2011/09/30 列挙
学校（再放送）
有村博紀，北大
• データベースの与えられた個数以上の組に含まれる集
合（アイテム集合）をすべて見つける問題
• 二つの部分からなる
パターン列挙
• 定められたクラス
に属するパターン
をすべて生成する
• 組み合わせ列挙
頻度計算
• データベース中での
各パターンの出現回
数や場所を計算
• パターンマッチング
• 埋め込み計算
31
頻出集合マイニングの素朴なアルゴリズム
有村博紀，北大
32
•
2011/09/30
頻出集合マイニング
2011/09/30 列挙
学校（再放送）
有村博紀，北大
素朴なアルゴリズム (Piatetsky-Shapiro?, KDD'88)
• すべての部分集合を生成し，
• データベースからその頻度を計算する
欠点
• 解となる頻出集合の数に関係なく，
指数個の集合を生成してしまう．
• 頻度計算に（すごく）時間がかかる．
• 百数十アイテム数百レコードに対して，数時間～数日を
要する！
33
BFS (Breadth-first search) algorithm
Most popular, the 1st generation frequent itemset miner
[Agrawal & Srikant, VLDB’94; Mannila, Toivonen, Verkamo, KDD’94]
?
Dr. Agrawal
Prof. Mannila
IBM Almaden Lab. Helsinki Inst. Tech.
Univ. Helsinki
Cadidate Generation: BFS (Breadth-first search)
?
APRIORI Algorithm
Starting from the smallest element, search the itemset lattice from
smaller to larger
Generate itemsets level by level (level-wise algorithm)
Frequency Counting: Horizontal Data Layout
Sequentially scanning a large database placed on a hard disk from left
to right to compute the frequencies
All the candidate itemsets is stored in a dictionary (a hash tree) in main
memory.
34
Basic idea: “Anti-monotonicity” lemma
Lemma (Agrawal, Srikant): For every minsup σ, if Y is σ-frequent
then any subset X of Y is also σ-frequent in DB T.
Corollary: Every non-empty σ-frequent set Y is obtained from
some σ-frequent set X by adding some new element.
The class Fσ of all frequent sets is monotone subclass of (2Σ, ⊆)
Anti-monotone property
minsupσ= 2
Frequent
sets
∅,
1, 2, 3, 4,
12, 13, 14,
23, 24, 124
The itemset lattice (2Σ, ⊆)
解の境界
parent
X
child
Y
parent
X
child
Y
1
t1
○
○
t4
t5
3
○
4
5
○
○
t2
t3
2
○
○
○
○
○
○
○
○
○
database
35
Cadidate Generation by BFS
Apriori algorithm [Agrawal, Srikant, 1994] (Also called Level-wise [Mannila et al., 1994])
Slice the item set-lattice 2Σ into levels L0, L1, …., Ln ()
Compute Fk = { X∈ Lk : X is a frequent set of size k }
for k = 0,1,2, … in a bottom-up manner
Generation of the k-th candidate set Ck+1 from Fk:
• For each a1…ak and b1…bk ∈ Fi with a1=b1…ak-1=bk-1 and ak < bk,
add a1…akbk into Ci
level 0
Φ
1
level 1
1
2
3
4
t1
level 2
12
13
14
23
34
24
level 3
level 4
123
124
134
234
○
○
t4
t5
3
○
4
5
○
○
t2
t3
2
○
○
○
○
○
○
○
○
○
1234
database
2011/09/30 列挙学校（再放送）
有村博紀，北大
Basic Idea: Cadidate Generation by BFS
Apriori algorithm [Agrawal, Srikant, 1994] (Also called Level-wise [Mannila et al., 1994])
Slice the item set-lattice 2Σ into levels L0, L1, …., Ln ()
Compute Fk = { X∈ Lk : X is a frequent set of size k }
for k = 0,1,2, … in a bottom-up manner
Generation of the k-th candidate set Ck+1 from Fk:
• For each a1…ak and b1…bk ∈ Fi with a1=b1…ak-1=bk-1 and ak < bk,
add a1…akbk into Ci
level 0
Φ
Frequent sets F
1
level 1
1
2
3
4
t1
level 2
12
13
14
23
34
24
level 3
level 4
123
124
134
234
○
○
t4
t5
3
○
4
5
○
○
t2
t3
2
○
○
○
○
○
○
○
○
○
1234
database
37
Breadth-first search algorithm
アルゴリズム Apriori(T:データベース, 0 ≤σ≤|T|: minsup):
出力：全頻出集合の集合F.
サイズ1の頻出集合の全体F1を計算する． i = 2.
while (Fi-1 /= ∅) do //ステージi:
STEP1（候補生成 AprioriGen）: Fi-1のサイズ(i-1)の頻出集合
同士を組合わせ，サイズiの候補集合の集まりCiを計算する．
STEP2（頻度計算）: データベースを一度だけ走査し，各候補
集合X ∈ Ciの頻度Freq(X)を一度に計算する． Fi = ∅.
STEP3: Ciから頻度σ以上のすべての候補集合を取り出し， Fi
に入れる．
STEP4: i = i + 1.
return F = F1∪…∪Fi を出力する．
40
Apriori アルゴリズム
[Agrawal 1994, Mannila 1995]
The state-of-the-art algorithm for association rules
Clever use of the present computer technology
Fast
Processor
+
Medium sized
Main memory
+
Huge
Hard disk
A pool of patterns
Levelwise search
coke & hamburger & chips: 24
d=3
sausage & beer
coke & chips: 48
coke & hamburger: 52
sausage: 62 chips: 124
coke: 254
mustard: 24 beer: 128
Sequential Disk Scan
d=2
d=1
Fast counting by
Hash tree
Large collection
of data
議論
Aprioriアルゴリズム(Agrawal '94)の意義
• 当時（１９９０年代半ば）の計算機の技術トレンドを
最大限に活用：
それ以前に比べて，格段に大きくなったメモリ（主
記憶）と，安価で高速なＣＰＵ，低速だが極めて大
容量のハードディスク
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li: New Algorithms for
Fast Discovery of Association Rules. KDD 1997: 283-286; ("prefix equivalence class" method)
Shohei Hido, Hiroyuki Kawano: AMIOT: Induced Ordered Tree Mining in Tree-Structured
42
2011/09/30 列挙学校（再放送）
有村博紀，北大
Databases.
ICDM 2005: 170-177
議論
Aprioriアルゴリズム(Agrawal '94)の
「候補生成法」（AprioriGen手続き）は
，本当に役立っているか？
• 集合の族の場合，列挙自体はもっと簡単なア
ルゴリズムでできる(例：家系木法/DFS)．
• ただし，木やグラフの族の場合，頻度制約を考
えると，効率良い場合がある．
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li: New Algorithms for
Fast Discovery of Association Rules. KDD 1997: 283-286; ("prefix equivalence class" method)
Shohei Hido, Hiroyuki Kawano: AMIOT: Induced Ordered Tree Mining in Tree-Structured
43
2011/09/30 列挙学校（再放送）
有村博紀，北大
Databases.
ICDM 2005: 170-177
2011/09/30 列挙学校（再放送）
有村博紀，北大
パート1の3：
頻出集合マイニングの
深さ優先(DFS)型アルゴリズム
～ Eclatアルゴリズム (Zaki, SDM 2000)
～ (Sese & Morishita, PODS 2000)
～ (Bayardo SIGMOD’98)
その他
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li: New
Algorithms for Fast Discovery of Association Rules. KDD 1997: 283-286
Shinichi Morishita, Jun Sese: Traversing Itemset Lattice with Statistical Metric Pruning.
PODS 2000: 226-236
44
ＢＦＳ型アルゴリズムの欠点
Aprioriアルゴリズム(Agrawal et al., '94)：
重複解の回避のため，解をすべて保持する
メモリを使いすぎる！
2011/09/30 列挙学校（再放送）
有村博紀，北大
45
深さ優先型(DFS)アルゴリズム
2011/09/30 列挙学校（再放送）
有村博紀，北大
「バックトラック 」アルゴリズム
第2世代の頻出集合発見アルゴリズム
− Eclat [Zaki et al., KDD’97]
− [Morishita DS’98], [Bayardo SIGMOD’98]
− LCM [Unoら, FIMI'03,'04,DS'04]
アルゴリズムのキモ
主記憶型の単純な再帰アルゴリズム
集合の家系木の上で「深さ優先探索」(DFS)をする．
「垂直データレイアウト」を採用．
メモリ効率が良くて，実際に高速．
いわゆる「パターン成長アプローチ」 "Pattern growth"
46
2011/09/30 列挙学校（再放送）
有村博紀，北大
Two approaches to Frequent sets mining
Backtrack algorithm
[1997-1998]
Apriori algorithm
[1994]
• Depth-first search (DFS)
• Vertical data layout
• Breadth-first search (BFS)
• Horizontal data layout
1
t1
○
•
generation
• External memory
algorithm
t3
○
t4
t5
3
○
4
5
○
○
t2
1st
2
○
○
○
○
○
○
○
○
○
database
• 2nd generation
• In-core algorithm
• Space efficient
48
DFS(Depth-first search) algorithm
DFS algorithm
How to generate all subsets X⊆Σin depth-first search?
Use enumeration of subsets! (岡本先生の講義の「部分集合列挙」)
The set lattice L = (2Σ, ⊆)
The set lattice for
Σ = {1,2,3,4}
σ=2
F = { ∅, 1, 2, 3, 4, 12,
13, 14, 23, 24,
124 }
49
The set enumeration tree (the family tree)
A spanning tree for all frequent itemsets
Assign the unique parent Pa(Y) = Y- { max(Y) } =: X to each
non-empty frequent set Y.
Given a parent X, we can generate its children Y = X∪{ i } by
attaching every item i satisfying i > max(X).
The set enumeration tree for F
The set lattice for
Σ = {1,2,3,4}
σ=2
F = { ∅, 1, 2, 3, 4, 12,
13, 14, 23, 24,
124 }
50
2011/09/30 列挙学校（再放送）
有村博紀，北大
DFS algorithm for Frequent Itemset Mining
Σ = {1, ..., n}: アイテムの全体集合
Algorithm Backtrack //主プログラム
BacktrackExpand(∅, Occ(∅), 0, n);
procedure BacktrackExpand(X, Occ(X), k, n)
Input: X:itemset, Occ(X), k: tail, n: maximum item;
if Freq(X) = |Occ(X)| < σ then return; //Backtrack!
Print a frequent set X;
for i = k+1,...,n do：
− 新しい出現リストOcc(X∪{i})を計算する;
− BacktrackExpand(X∪{i}, Occ(X∪{i}), i, n) ;
51
効率良い頻度計算
2011/09/30 列挙学校（再放送）
有村博紀，北大
アイテムを足すごとに各集合の出現リストを更新する
Lemma: For any X1, X2, Occ(X ∪ Y) = Occ(X) ∩ Occ(Y).
Lemma: For any set X, item a, Occ(X∪{a}) = { t∈Occ(X) : a ∈t }
tuples
t1
1
2
3
t2
2
4
5
t3
1
2
4
t4
2
3
t5
1
Downward closure [Zaki et al ‘97]
database D
items
2
4
Occ(1)
5
…
1
f
t1
4
t2
items
1
2
3
4
Vertical
layout:
t1
t2
t1
t2
t3
t3
t3
t3
The occurrence
list representation
t5
t4
t4
t5
t5
5
t4
t3
t4
t5
Occ(f)
1
Occ(2 3)
t1
t3
2
t5
23
3
2
t2
t3
t3
4
t4
24
UpdateOcc
t4
t2
t5
t3
Occ(2)
Occ(2 4)
t5
DFS over the set enumeration tree
52
52
Efficient update of Occ(X)
2011/09/30 列挙学校（再放送）
有村博紀，北大
Properties:
For any X1, X2, Occ(X ∪ Y) = Occ(X) ∩ Occ(Y). (basic)
For any set X, item a, Occ(X∪{a}) = { t∈Occ(X) : a ∈t }
手続き UpdateOcc(X, a, O(X)) 古い出現リストから，
一個ずつ位置を取り
Input：X⊆Σと, a ∈Σ, O(X).
出して，まだ大丈夫
Output: O(X∪{a}).
か調べる
Y = X∪{a}; Occ(Y) = ∅;
foreach t ∈O(X) do
− if a ∈t then Occ(Y) = Occ(Y)∪{t};
return Occ(Y);
Downward closure [Zaki et al ‘97]
53
DFS: Main result
Theorem
The algorithm Backtrack can be implemented to
enumerates all σ-frequent itemsets X in a given
transaction database T
− in O(l・|Occ(X)|) time per frequent itemset
− using O(l・|Occ(X)|) space
where l is the maximum length of tuples in T and
|Occ(X)| is the number of occurrences of X.
Space and time efficient (poly-delay & poly-space)
On the other hand, the algorithm Apriori requires O(l・|Occ(X)|)
time per frequent itemset and O(maxi ||Fi||) space.
54
2011/09/30 列挙学校（再放送）
有村博紀，北大
Summary: BFS vs. DFS
Backtrack algorithm
[1997-1998]
Apriori algorithm
[1994]
• Depth-first search (DFS)
• Vertical data layout
• Breadth-first search (BFS)
• Horizontal data layout
x1
t1
○
•
generation
• External memory
algorithm
t3
○
t4
t5
x3
○
x4
x5
○
○
t2
1st
x2
○
○
○
○
○
○
○
○
○
database
• 2nd generation
• Space efficient
• In-core algorithm
55
2011/09/30 列挙学校（再放送）
有村博紀，北大
Summary: Horizontal & Vertical Layout
データベースD
水平/ Horizontal layout
(Aprioriアルゴリズム)
1
3
t2
2
4
t3
1
2
t4
2
3
t5
1
2
2
t1 ○
3
4
tuples
t1
1
t2
4
5
○
○
○
t3 ○ ○ ○ ○
t4
○ ○
t5 ○ ○
4
3
垂直 / Vertical layout
(Backtrackアルゴリズム)
○
1
2
3
4
5
t1
t2
t1
t2
t4
t3
t3
t3
t3
t5
t4
t4
t5
○
Scan
t5
Scan
set
123
124
134
234
245
freq
1
2
1
1
2
外部記憶
向き
候補アイテム集合の出現リストを，
追加ごとに更新する
1
候補アイテム
集合の出現数
をまとめて計
数する
t2
t3
t5
主記憶
向き
12
124
t3
t3
t5
t5
56
2011/09/30 列挙学校（再放送）
有村博紀，北大
FP-growthアルゴリズム
データベース
最もよく知られたアルゴリズムの一つ（Hanら，SIGMOD2000）
パターンとデータを木構造(FP-Tree ="Frequent Pattern Tree")
に格納する．当初は「候補生成なしマイニング」と呼ばれていた．
A: 1,2,5,6,7,9
現在では，DFS法の変種と理解（同じパターン列挙と出現計算）
C: 1,2,7,8,9
実際のデータに対して高速といわれている
D: 1,7,9
B: 2,3,4,5
E: 2,3,7,9
頻出パターン木
(FP-Tree)
データベース木
7
9 179
9
19
集合27の出現リスト
頻出集合
1
Φ
{1} {2} {7}
{9} {1,7}
{1,9} {2,7}
φ
2
7
7
9
9 279
27
27
27あ
29
{2,9} {7,9}
{1,7,9}
{2,7,9}
9
9
9
79
F: 2,7,9
集合 27
* 1 22 5
7
7
7 9
2
2 3 4
7
7
7
7 99
集合279の
出現リスト
6 77 99 A
8 99
C
D
5 B
99 E
F
J. Han, J. Pei, Y. Yin, Mining Frequent Patterns without Candidate Generation, Proc. SIGMOD2000, 1-12 (2000)
57
ＬＣＭアルゴリズム
（Linear-time Closed Itemset Miner）
飽和集合／極大集合マイニングアルゴリズム
理論的性能保証： 出力線形時間アルゴリズム
"The world-fastest closed set mining algorithm"
(according to IEEE ICDM "the top-10 data mining
algorithms" article)
高速な代表元パターンマイニング
極大２部クリーク C
(宇野・有村, DS'04, FIMI'04)
ニュース速報 (Nov. 1, 2004, Brighton, UK)
第2回 FIMI Workshop で宇野・清見・
有村組(LCM ver.2) が優勝！
FIMI'04 Best Implementation Award
くわしくは宇野毅明の
講義で．．．
今年は
勝ちま
した
FIMI Workshop：
「頻出アイテム集合マイニング実装（FIMI)」に関する
データマイニング分野のプログラミングコンテスト
今年は，8+5 実装が最終エントリ (問合せ80件超)
({w,
({w,y},
y}, {a,
{a,b,
b,d})
d})
transactions
items
u
a
v
b
w
c
x
d
y
e
LCMアルゴリズム: PPC拡張による出力多項式時間の 宇野毅明先生
閉アイテム集合列挙アルゴリズム [宇野・有村 DS'04]
(NII, A01班）
• LCM, 宇野先生HP, program codes：http://research.nii.ac.jp/~uno/codes.htm
• FIMI Frequent Itemset Mining Implementations Repository: http://fimi.cs.helsinki.fi/ 58
Summary
Frequent Itemset Mining
Finding all "frequent" sets of elements appearing in a given
transaction data base.
Introduced by Agrawal and Srikant [VLDB'94]
One of the most basic data mining problem
Algorithms
BFS algorithm － Apriori [Agrawal et al, ‘94]
DFS algorithm － Backtrack [Zaki et al. ’97; Morishita’98]
Applications
Feature extraction for SVM & Boosting
Closed and Maximal Frequent Itemset Mining
Sequences and Graphs
Bibliography
2011/09/30 列挙学校（再放送）
有村博紀，北大
パート1：データマイニングと頻出集合発見
•
[AIS 93] R. Agrawal, T. Imielinski, A. N. Swami: Mining Association Rules between Sets of
Items in Large Databases, Proc. SIGMOD Conference 1993, pp. 207-216, 1993.
•
[AMST 96] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, A. I. Verkamo: Fast Discovery of
Association Rules, Advances in Knowledge Discovery and Data Mining, pp. 307-328, 1996.
•
[Agrawal & Srikant, VLDB’94] R. Agrawal, R. Srikant: Fast Algorithms for Mining Association
Rules in Large Databases. Proc. VLDB 1994, pp. 487-499, 1994. (Apriori)
•
[Bayardo, SIGMOD’98] R. J. Bayardo Jr.: Efficiently Mining Long Patterns from Databases,
Proc. SIGMOD Conference 1998: pp. 85-93, 1998.
•
[Han et al. SIGMOD’00] J. Han, J. Pei, Y. Yin, Mining Frequent Patterns without Candidate
Generation, Proc. SIGMOD Conference 2000, pp. 1-12, 2000. (FP-growth)
•
[Morishita & Sese PODS’00] S. Morishita, J. Sese: Traversing Itemset Lattice with Statistical
Metric Pruning, Proc. PODS 2000, pp. 226-236, 2000.
•
[Zaki et al., KDD’97] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li, New algorithms for fast
discovery of association rules, Proc. KDD 1997, pp. 283-286, 1997. (Eclat)
•
[宇野，有村] 宇野毅明，有村博紀,「データインテンシブコンピューティング その２ － 頻出アイテム集
合発見アルゴリズム －」,人工知能学会誌，レクチャーシリーズ「知能コンピューティングとその周辺」,
(編)西田豊明, 第2回, Vol.22, No.3, 2007年5月. (PDF: http://www-ikn.ist.hokudai.ac.jp/~arim/jtalks.html)
60
2011/09/30 列挙学校（再放送）
有村博紀，北大
列挙学校：第４コマ
パート２: 系列とグラフのマイニング
有村 博紀
北海道大学大学院 情報科学研究科 コンピュータサイエンス専攻
email: {arim,kida}@ist.hokudai.ac.jp
http://www-ikn.ist.hokudai.ac.jp/~arim
．
61
2011/09/30 列挙学校（再放送）
有村博紀，北大
パート２の１：
半構造マイニング
～ 頻出グラフマイニングの定式化（Inokuchi,
Washio, Motoda, PKDD2000)
その他
62
2011/09/30 列挙学校（再放送），有村博紀，北大
64
半構造データマイニング
半構造データ
多様な構造をもつ膨大なデータ
従来のデータマイニング手法は，
半構造データには直接適用不可能
3. 新たな
知識の構築
新しい半構造データマイニング技術が必要
高速かつ頑健なマイニング技術が鍵
2. 知識を
パターンや規則と
して発見
知識
Knowledge
文科省科研費特別推進研究（平成１７年～１
９年）「知識基盤形成のための大規模半構造デ
ータからの超高速パターン発見」
CC
H XX
H
H
半構造パターン発見
Pattern Discovery
知識を有機的に
つなげる
半構造データ
Semi-structured Data
CC
H XX
H
2011/09/30 列挙学校（再放送），有村博紀，北大
Applications of Semi-structured Data
Mining
C
Graph / Network Analysis
H
H
Information Extraction
Natural Language Processing
X
X
Text/HTML page classification
C
H
Query Optimization
Data Compression
Knowledge Disocvery from Complex Data
Chemical Compounds/Molecules
Network Log
Link structures in Web
Gene Networks...
65
2011/09/30 列挙学校（再放送），有村博紀，北大
半構造データマイニングの歴史
～1995
1996
1997
1998
1999
2000
2001
2002
2003
Algorithm for finding subgraphs by MDL principle
Subdue [Holder et al. (KDD’94)]
Finding frequent paths [Wang and Liu (KDD’97)]
Finding Semi-structured Schema
[Nestrov, Abiteboul et al. (SIGMOD’98)]
Finding frequent subgraphs
AGM [Inokuchi, Wahio, Motoda (PKDD’00, MLJ. 2003)]
FSG [Kuramochi et al. (ICDM’01)
Finding frequent / optimal ordered trees
FREQT [Ours (SDM’02)]，Treeminer [Zaki (KDD’02)]
Finding frequent subgraphs
gSpan [Yan and Han (ICDM’02)], VG [Venetik, et al.(ICDM’02)]
Finding frequent un-ordered trees
UNOT [Ours (SDM’03)]，NK [Nijssen, Kok (MGTS’03)]
Frequent Maximal/Closed Trees & Graphs mining [Yan&Han '03; 66
Termier et al.'04] and many algorithms in 2000s
68
2011/09/30 列挙学校（再放送）
パート２の２：
頻出順序木のマイニング
～ TreeMiner (Zaki, KDD2002)
～ Freqt (Asai et al., SDM2002)
～ Nakano (IPL, 2002)
Mohammed Javeed Zaki: Efficiently mining frequent trees in a forest. KDD 2002: 71-80.
Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroki Arimura, Hiroshi Sakamoto, Setsuo
Arikawa: Efficient Substructure Discovery from Large Semi-structured Data, SDM 2002.
Shin-Ichi Nakano: Efficient generation of plane trees. Inf. Process. Lett. 84(3): 167-172
有村博紀，北大
(2002)
FIT2008, 有村博紀，北海道大学
Frequent Pattern Mining
for
Ordered Trees
Minining ordered and
unordered trees
2011/09/30 列挙学校（再放送），有村博紀，北大
Tree Mining
Association Rule,
Frequent Itemsets
Simple
Efficient algorithms
Expressive patterns & Efficient algorithms
Trees
General graphs
(AGM, FSG, gSpan)
Development of
Efficient tree mining
algorithms
Expressive
Computationally Hard
70
研究成果：高速半構造マイニング
高速半構造データマイニングエンジン
FIT2008, 有村博紀，北海道大学
高速な木パターン発見エンジン
Discovering all frequent sub-structures
from a colection of labeled trees
Extendible to most statistical functions
半構造データの特徴的部分構造の発見
理論と実装： FREQT, StreamT, Unot
SIAM DM'02, PKDD'02, IEEE
ICDM'02), DS'03
公開＆応用
Canonical form for unordered
trees (Left-Biased Tree)
(Lexicographically largest trees
over depth-label sequence
encoding)
A
T1
B
FREQT: Efficient ordered tree mining
A
engine (SIAM DM'02)
Applications
Applications
B
Japanese
Japanese Text
Text Mining
Mining
(Morinaga,
(Morinaga, Arimura
Arimura et
et
al.,
al., FIT'04,
FIT'04, IBIS'04,
IBIS'04,
submitting
submitting 2005)
2005)
FREQT:
DEWS'02優秀論文賞（H14年6月）
Chemical
mining
Chemical
mining
Software
Software engineering
engineering
etc.
etc.
Unot: DEWS’04優秀論文賞（H16年6月）
frequent
B
B
B
B
B
frequent
A
B
B
B
A
A
A
B
A
B
infrequent
A
A
B
B
B
A
B
B
B
B
B
A
A
B
＞
C
C
Rightmost Expansion &
Ordered Tree Enumeration
Trees (SIAM DM’02, IEEE
ICDM’02, DS’03))
A
T2
B
(0A,1B,2A,3C,2B,1B,2C)
B
B
A
C
C
(0A,1B,2B,2A,3C,1B,2C)
Difficulties in unordered tree mining
Awarded
Awarded
Exponentially many
"無順序木マイニングエンジン
"無順序木マイニングエンジンUNOT"
UNOT"
isomorphic patterns！
IEICE
Data
Engineering
Workshp
MaxMotif:
Awarded
DEWS2004（H17.6）
IEICE
Data
Engineering
Workshp
Unique representation？
Japan
Japan'04,
'04,best
bestpaper
paperaward
award
Enumeration without
（（房延・浅井・有村・宇野・中野,
June
房延・浅井・有村・宇野・中野,
June2004）
2004）
duplicates in a unique way
StreamT:
’０３AI学会大会優秀賞（H15.6）
Efficient computation of
71
2011/09/30 列挙学校（再放送），有村博紀，北大
パターンとデータ：ラベル付き順序木
Labeled Ordered Tree
根付き (rooted)
順序木(兄弟の順序があ
る)
ラベル付き(各ノードはラベ
ルをもつ)
people
person
例
HTML/XML文書
階層レコード
自然言語の「かがり受け
木」(dependency tree).
person
name
@age
@id
tel
email
@id
name
#text
25
#text
608
John
#text
609
#text
555-4567
[email protected]
Mary
72
2011/09/30 列挙学校（再放送），有村博紀，北大
順序木のマッチング（パターン照合）
パターン木 Tがデータ木 D
にマッチする (出現する)
pattern tree T
B
f
f
f
f
There is a matching
function f from T into D
matching
function f
A
1
C
は1-to-1.
は親子関係を保存.
は (間接) 兄弟関係を保存.
はラベルを保存.
A
2
3
B
data tree D
r
4
A
7
5
6
C
B
8
9
B
C
A
B
11
10
C
73
2011/09/30 列挙学校（再放送），有村博紀，北大
パターンの頻度
• A root occurrence of pattern T:
• The node to which the root of T maps by a matching function
• The frequency fr(T) = #root occurrences of T in D
T
A
1
B
r
D
C
A
2
Root occurrence list
OccD(T) = {2, 8}
3
B
4
A
P2
P1
5
C
C
A
B
9
B
11
8
B
6
7
C
10
74
2011/09/30 列挙学校（再放送），有村博紀，北大
頻出木パターン発見問題
Given: a colection S of labeled ordered trees and
a minimum frequency threshold s
Task: Discover all frequent ordered trees in S (with
frequency no less than s) without duplicates
頻度しきい値
(minimum support)
s = 50%
頻度しきい値50%での
頻出木パターン
75
2011/09/30 列挙学校（再放送），有村博紀，北大
Efficent Algorithms
Depth-first mining algorithm for frequent
ordered trees
Freqt [Asai, Arimura et al., SIAM DM'02]
TreeMiner [Zaki, KDD'02]
Performance guarantee
Polynomial time enumeration per pattern
Small memory footprint
Key technique: Rightmost expansion
76
2011/09/30 列挙学校（再放送），有村博紀，北大
半構造パターン発見アルゴリズムの
設計のキーポイント
1. パターンをどのように表現するか？
2. 候補パターン（部分構造）を，どうやって重複
なしに列挙するか？
3. 各パターンの頻度を，どのようにして高速に
計算するか？
matching
function f
A
B
1
C
B
data tree
A
2
3
r
4
A
7
5
6
C
B
8
9
B
D
C
A
10
B
11
C
77
2011/09/30 列挙学校（再放送），有村博紀，北大
78
超高速半構造パターン発見技術
最右拡張技法 (Rightmost expansion)
申請者等が2002年に開発 [SIAM DM'02]
世界初の多項式時間アルゴリズムを提案
現在，さまざまな組合せ構造の効率よい列挙
に用いられる[当該分野の国際会議論文の大半に引用]
1
p
l
k
Tree
k-1
Freqt [Asai, Arimura et al.,
SIAM DM'02]
TreeMiner [Zaki, KDD'02]
78
2011/09/30 列挙学校（再放送），有村博紀，北大
２．頻度制約の導入（頻出木マイニング）
頻度に関する単調性
「もしある順序木 T が頻出なら，その親S も頻出」
探索の枝刈りとバックトラック
頻出でなくなったら，その子孫の探索は枝刈りする．
⊥
B
frequent
B
B
B
B
B
frequent A
A
A
A
B
B
B
A
B
B
B
B
infrequent B
A
A
B
B
B
B
79
2011/09/30 列挙学校（再放送），有村博紀，北大
Itemset mining revisited: BFS vs. DFS
アプリオリ型
アルゴリズム [1994]
バックトラック型
アルゴリズム[1997-2000]
• 幅優先探索 (BFS)
How to
• 水平データレイアウト
• Apriori algorithm
[1994] DFS
implement
• 深さ優先探索 (DFS)
• 垂直データレイアウト
• MaxMiner, Eclat, FP-growth etc
[1998-2000].
for ordered tree
patterns?
1
t1
• 「第一世代」
• 外部記憶型アルゴリ
ズム
t2
2
○
3
4
○
○
○
t3
○ ○ ○ ○
t4
○ ○
t5
5
○ ○
○
○
database
• 「第二世代」
• メモリ型省スペースア
ルゴリズム
80
研究成果：高速半構造マイニング
高速半構造データマイニングエンジン
FIT2008, 有村博紀，北海道大学
高速な木パターン発見エンジン
Discovering all frequent sub-structures
from a colection of labeled trees
Extendible to most statistical functions
半構造データの特徴的部分構造の発見
理論と実装： FREQT, StreamT, Unot
SIAM DM'02, PKDD'02, IEEE
ICDM'02), DS'03
公開＆応用
Canonical form for unordered
trees (Left-Biased Tree)
(Lexicographically largest trees
over depth-label sequence
encoding)
A
T1
B
FREQT: Efficient ordered tree mining
A
engine (SIAM DM'02)
Applications
Applications
B
Japanese
Japanese Text
Text Mining
Mining
(Morinaga,
(Morinaga, Arimura
Arimura et
et
al.,
al., FIT'04,
FIT'04, IBIS'04,
IBIS'04,
submitting
submitting 2005)
2005)
FREQT:
DEWS'02優秀論文賞（H14年6月）
Chemical
mining
Chemical
mining
Software
Software engineering
engineering
etc.
etc.
Unot: DEWS’04優秀論文賞（H16年6月）
frequent
B
B
B
B
B
frequent
A
B
B
B
A
A
A
B
A
B
infrequent
A
A
B
B
B
A
B
B
B
B
B
A
A
B
＞
C
C
Rightmost Expansion &
Ordered Tree Enumeration
Trees (SIAM DM’02, IEEE
ICDM’02, DS’03))
A
T2
B
(0A,1B,2A,3C,2B,1B,2C)
B
B
A
C
C
(0A,1B,2B,2A,3C,1B,2C)
Difficulties in unordered tree mining
Awarded
Awarded
Exponentially many
"無順序木マイニングエンジン
"無順序木マイニングエンジンUNOT"
UNOT"
isomorphic patterns！
IEICE
Data
Engineering
Workshp
MaxMotif:
Awarded
DEWS2004（H17.6）
IEICE
Data
Engineering
Workshp
Unique representation？
Japan
Japan'04,
'04,best
bestpaper
paperaward
award
Enumeration without
（（房延・浅井・有村・宇野・中野,
June
房延・浅井・有村・宇野・中野,
June2004）
2004）
duplicates in a unique way
StreamT:
’０３AI学会大会優秀賞（H15.6）
Efficient computation of
81
2011/09/30 列挙学校（再放送），有村博紀，北大
Theoretical performance guanrantee
How to measure the time complexity of
mining algorithms?
Exponentially many answers!
As enumeration algorithms
Output-polynomial (OUT-POLY)
Total time = poly(N, M)
Input size M
Input
polynomial-time enumeration, or
amortized polynomial-delay (POLY-ENUM)
Amotized delay is poly(Input), or
Total time = M·poly(N)
Algorithm
Output size M
Outputs
Time
polynomial-delay (POLY-DELAY)
Maximum of delay is poly(Input)
Delay D
Total Time T
+ polynomial-space (POLY-SPACE)
82
82
2011/09/30 列挙学校（再放送），有村博紀，北大
EXP: Scalability
Dataset: citeseers
Minimum support: s=3.0(%) fixed
Increasing the data size from 0.3MB to 5.6MB.
Runtime (sec)
Runtime
(sec)
(178285, 1.39)
2
1.5
This algorithm is scalable.
1
0.5
0
0
50000
100000
150000
Number of nodes in a data tree
200000
83
# of nodes
84
2011/09/30 列挙学校（再放送）
パート２の３：
頻出無順序木のマイニング
～ Unot (Asai, Arimura, Uno, Nakano, DS2003)
～ (Nijssen & Kok, MGTS2003)
Tatsuya Asai, Hiroki Arimura, Takeaki Uno, Shin-Ichi Nakano: Discovering Frequent
Substructures in Large Unordered Trees. Discovery Science 2003: 47-61
S. Nijssen and J.N. Kok. Efficient discovery of frequent unordered trees. In: Proceedings
of the First International Workshop on Mining Graphs, Trees and Sequences (MGTS),
有村博紀，北大
2003.
2011/09/30 列挙学校（再放送），有村博紀，北大
グラフマイニングの究極の目標
Sets (itemsets)
Simple
Efficient algorithms
Expressive patterns & Efficient algorithms
Trees
一般のグラフ
Development of
Efficient tree mining
algorithms
Expressive
Computationally Hard
85
86
高速な無順序木パターン発見エンジン
UNOT (DS2004)
無順序木：
グラフの自明でない部
分クラス
Canonical form for unordered
trees (Left-Biased Tree)
(Lexicographically largest trees
over depth-label sequence
encoding)
A
T1
B
A
B
B
A
T2
B
＞
C
C
(0A,1B,2A,3C,2B,1B,2C)
B
B
A
C
C
(0A,1B,2B,2A,3C,1B,2C)
Difficulties in unordered tree mining
Exponentially many
isomorphic patterns！
Unique representation？
Enumeration without
duplicates in a unique way
Efficient computation of
occurrences
Awarded
Awarded
"無順序木マイニングエンジン
"無順序木マイニングエンジンUNOT"
UNOT"
IEICE
IEICE Data
DataEngineering
EngineeringWorkshp
Workshp
Japan
'04,
best
paper
award
Japan '04, best paper award
無順序木マイニングア
ルゴリズム
Unot [Asai,
Arimura, DS'03]
NK [Nijssen, Kok,
MGTS’03]
（（房延・浅井・有村・宇野・中野,
房延・浅井・有村・宇野・中野,June
June2004）
2004）
FREQT: DEWS'02優秀論文賞（H14年6月）
Unot: DEWS’04優秀論文賞（H16年6月）
2011/09/30 列挙学校（再放送），有村博紀，北大
86
2011/09/30 列挙学校（再放送），有村博紀，北大
0．無順序木マイニングの問題点
問題点：
兄弟の入れ替えによって同値な木が，指数的に多く存在する
A
T1
B
A
C
T2
B
B
A
C
B
B
A
C
T3
B
B
C
C
A
T4
B
B
A
C
これらの木はすべて
無順序木としては
互いに同値！
A
B
C
B
B
A
C
87
2011/09/30 列挙学校（再放送），有村博紀，北大
１．無順序木の一意な表現
アイディア：
無順序木の正規系として，「深さラベル列」のさまざまな回転
に関して，辞書式順序で最大の表現を採用する
A
T1
B
A
T2
B
B
A
C
C
(0A,1B,2A,3C,2B,1B,2C)
＞
B
B
A
T3
B
B
C
C
C
(0A,1B,2B,2A,3C,1B,2C)
A
T4
B
B
A
A
B
C
(0A,1B,2C,1B,2A,3C,2B)
C
B
B
A
C
(0A,1B,2C,1B,2B,2A,3C)
88
2011/09/30 列挙学校（再放送），有村博紀，北大
２．候補となる無順序木パターンの列挙
「逆探索性」
最右拡張に関して，正規形無順序木の親は，やはり
正規形無順序木
列挙
順序木の場合と同じように，最右拡張が使える
ただし，最右でない子をチェックして生成しない
最右拡張
89
SAME
90
2011/09/30 列挙学校（再放送）
パート２の３：
一般のグラフの頻出マイニング
～ AGM (Inokuchi, Washio, Motoda,
PKDD2000; Machine Learning 50(3), 2003)
～ gSpan (Yan, Han, ICDM2002)
Akihiro Inokuchi, Takashi Washio, Hiroshi Motoda: An Apriori-Based Algorithm for Mining
Frequent Substructures from Graph Data. PKDD 2000: 13-23
Xifeng Yan, Jiawei Han: gSpan: Graph-Based Substructure Pattern Mining. ICDM 2002:
721-724
有村博紀，北大
どうやって一般のグラフをマイニングする
か？
⊥
基本戦略はパターン
成長法
小さなグラフに，頂点
と辺を一つずつ追加
する
問題点
グラフ同形性（graph
isomorphism）
Jump!
2011/09/30 列挙学校（再放送），有村博紀，北大
91
グラフマイニング
Inokuchi, Washio, Motoda [PKDD’00]
Kuramochi & Karypis [ICDM’01, ICDM’02]
AGM: “An Apriori-based Algorithm for Mining Frequent Substructures
from Graph Data”
FSG: “Frequent Subgraph Discovery”
Yan & Han [ICDM’02]
gSpan: “gSpan: Graph-based substructure pattern mining”
深さ優先探索
DFS木表現 = rightmost expansion プラス 同形性判定
C
H
C
X
X
H
H
2011/09/30 列挙学校（再放送），有村博紀，北大
92
2011/09/30 列挙学校（再放送），有村博紀，北大
AGM [Inokuchi, Washio, Motoda (PKDD’00)]
AGM = Apriori-based Graph Mining
隣接行列表現を用いて，Apriori風に頻出部分グラフを
発見するアルゴリズム
パターンの生成法
隣接行列の正準形を効率よく計算
Cl C Cl C Cl H
Cl
Cl
C
H
C
Cl
トリクロロエチレン
Cl
C
Cl
C
Cl
H
0
1
0
0
0
0
1
0
1
2
0
0
0
1
0
0
0
0
0
2
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
隣接行列の正準形
行と列を入れ替えて
Codeが最小となる
ような隣接行列
Code = 101020000100010
93
2011/09/30 列挙学校（再放送），有村博紀，北大
グラフマイニングへの逆探索手法
gSpanアルゴリズム（Yan & Han, 2002）
最速のグラフマイニング手法の一つ
B
⊥最右拡張手法を使い，木を通して，
frequent
グラフを列挙
B
B
B
B
B
frequent A
A
infrequent
B
A
A
A
B
B
B
B
B
B
A
infrequent B
A
A
A
B
B
A
B
B
94
2011/09/30 列挙学校（再放送），有村博紀，北大
さまざまな半構造データへの拡張
H
極大パターン発見
LCMアルゴリズムを系列，木，グラフへ拡張
X X
H
H
C C
B C D D C C D B B D
α→β
Sequence
Motifs
Motif with
wildcards:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
pos = 7
pos = 15
An integer 0 (quorum)
ABoAB
A motif
Item Sets
21
=3
B
A
ABCABRRABRABCABABRABBC
pos = 0
D B
C D B
C D
B C D
A B C D B A
A
C
B
A
A
B
Attribute trees
95
2011/09/30 列挙学校（再放送）
有村博紀，北大
History of Sequence Mining
～1995
1996
1997
1998
1999
Statistical Sequence Mining
HMM (Hidden Markov Model ]*1)
Data Mining Area
Frequent Sequence Mining
[Haussler, Krogh et al., 26th HICSS 1993]
[Durvin, Eddy, Krogh, Mitchison, Cambridge, 1998]
Mining frequent episodes in an event sequence (BFS)
[Mannila, Toivonen, Verkamo, KDD1995]
MOTIF program
[Smith, Annau et al., PNAS, 87,1990]
Mining frequent itemset sequence (BFS)
Sequential Patterns [Agrawal, Srikant VLDB1995]
PRATT program
[Jonassen et al., Protein Sci. 4, 1995]
2000
Mining frequent itemset sequence (DFS)
Spade [Zaki, 1998; Mach. Learn. 2000]
2001
Mining frequent sequences (DFS + Projected DB)
PrefixSpan [Pei, Han, et al., ICDE 2001]
2002
2003
2004
2005
TEIRESIAS program
[Rigoutsos, Floratos, Bioinformatics 14, 1998]
Closed Sequence Mining
Mining frequent closed frequent sequences (DFS)
CloSpan [Yan, Han, et al., SDM 2003]
Mining frequent closed sequences (DFS)
BIDE [Wang & Han, ICDE 2004]
eMOTIF program
[Nevill-Manning et al., PNAS 95, 1998]
a PTAS algorithm for concensus
motif problem in Hamming distance
[Li, Ma, Wang, STOC 1999]
PROJECTION (Random projection)
[Buhler, Tompa, J. Comp. Bio. 9(2), 2002]
2006
Mining frequent closed sequeces with wildcards (DFS)
MaxMotif [Arimura, Uno, LNCS 3827, ISAAC2005]
2007
Mining frequent closed sequeces with gaps (DFS)
AU [Arimura, Uno, LNAI 4914, LLLL2007]
2008
Bioinfomatics Area
飽和系列の多項式時間
列挙アルゴリズム
96
Sequences: Maximal Motif Discovery
The problem of enumerating all maximal motifs in an
input sequence without duplicates for the class of
repeated motifs with wildcards [Parida et al. 2000, SIAM SODA]
An integer 0 (quorum)
An input string s in S*
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
=3
ABCABRRABRABCABABRABBC
Task: Enumerate all maximal
motifs without duplicates
AB
e
B
BC
ABRAB
ABoAB
BoAB
BoABoAB
Solutions
BoABoooooB
BoooooB
97
ギャップ付きモチーフに対する
極大パターン発見 [ISAAC 2005]
[]*
[B]*
[AB]*
[A]
[BC]*
[C]
[ABRAB]*
[R]
[RA]
[RAB]
21
9
7
7
3
3
3
3
3
3
[RoB] 3
[BR]
3
[ABR] 3
[ABRA] 3
[ABRoB] 3
[ABoA] 4
[AoR]
3
[AoRA] 3
[AoRAB] 3
[AoRoB] 3
[AooA]
[BRA]
[BRAB]
[BRoB]
[BoAB]*
[BooB]
[ABoAB]*
[ABooB]
[AooAB]
[AoooB]
50 motifs (frequent motifs)
In real datasets, the number of
maximal motifs is much smaller
than that of motifs containing the
complete information
Succinct representation for all
(frequent) motifs
4
3
3
3
5
5
4
4
4
4
[BoA]
5
[BooBooB]
[BoABoA] 3
[BooooAB]
[BoAooA] 3
[ABoooooB]
[BooBoA] 3
[BoooooB]*
[BooooA] 3
[BoABoooooB]*
[BoABoAB]*3
[AooooooB]
[BoABooB] 3
[BoAooooooB]
[BoAooAB] 3
[BooBoooooB]
[]* 3
21
[BoAoooB]
[BooooooooB]
[B]*
9
[BooBoAB] 3
[AB]*
7
[BC]*
3
[ABRAB]*
3
[BoAB]*
5
[ABoAB]*
4
[BoABoAB]*
3
[BoooooB]*
4
[BoABoooooB]* 3
3
3
3
4
3
3
3
3
3
10 maximal motifs
00
10
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
ABBCABRABRABCABABRABBC
input string s & quorum q = 3
Arimura and Uno [ISAAC 2005; J. Comb. Optim., 2006]
98
2011/09/30 列挙学校（再放送），有村博紀，北大
エピソードマイニング
root
[Katou, Arimura, Hirata, PAKDD'08,09, DS'09]
a
a
時系列データのマイニング
データに隠れたイベント間の
(半)順序関係を発見する
Mannila et al. (KDD'95)
a
b
c
e
a
b
a
episode
院内感染症の要因解析
（Katou, Arimura, Hirata,
CME2009）
「症状 e が起きた後で，治療 a,
b, c を行ったら，症状の改善 d
が見られた」
a
b
a
b
a
input sequence
11
a
b
d
12
e
13
b
c
d
14
a
b
a
a
d
高速なアルゴリズム
医療データへの応用
b
15
a
b
c
sliding window
16
a
b
d
18
a
b
a
b
d
b
a
b
a
a
c
a
2011/09/30 列挙学校（再放送）
有村博紀，北大
演習：
「図形のようなグラフ」
の列挙
幾何グラフの列挙
100
2011/09/30 列挙学校（再放送），有村博紀，北大
極大2次元幾何グラフのマイニング
幾何変換（並進・回転・拡大）のもとで頻出で
極大な点配置レイアウトを発見
(Arimura, Uno, Shimozono, DS'07)
y
A
2.0
g
1.0
Goemetric Graph Database
A
1.0
A
g
g
g
g
g
A
g
A
2.0
Ag
A
g
gA
Graph
Pattern
3.0 x
Hiroki Arimura, Takeaki Uno, Shinichi Shimozono: Time and Space Efficient Discovery of
Maximal Geometric Graphs. Discovery Science 2007: 42-55
Sebastian Nowozin, Koji Tsuda: Frequent Subgraph Retrieval in Geometric Graph Databases. 101
ICDM 2008: 953-958
2011/09/30 列挙学校（再放送），有村博紀，北大
列挙アルゴリズム
n点の幾何グラフGの表現
開始点1を任意に選び，重心mの反時計回りに，すべての点を1, 2, ..., nと
番号づける．
点列，辺列，ラベル列の順に要素を並べて符号化．
正規形：全ローテーションで辞書順最小の符号
Geometric Graph
Pattern
A
1 単位長さ
（最初の辺）
A
m
B
頂点を反時計回り
に順序付け
102
2011/09/30 列挙学校（再放送），有村博紀，北大
列挙アルゴリズム
A
n点の幾何グラフGの表現
開始点1を任意に選び，重心mの反時
計回りに，すべての点を1, 2, ..., nと番
号づける．
点列，辺列，ラベル列の順に要素を並
B
べて符号化．
Geometric Graph
正規形：
Pattern
全ローテーションで辞書順最小の符号
正規形はC1
1 単位長さ
（最初の辺）
A
m
頂点を反時計回り
に順序付け
103
2011/09/30 列挙学校（再放送），有村博紀，北大
列挙アルゴリズム
「逆探索」を用いて，グラフと照合写像を同時に列挙．
家系木の根は，単位長さの線分．
子グラフＧの「親」は，正規形の符号で最後の点（最大の点）を除いたも
の，のさらに正規形をとったもの．
親から子をつくるには，ためしに新しい頂点をつけてみて，回転して正
規形符号を求める．つけたものが符号の最後ならＯＫ．
追加する頂点の候補は，照合写像の逆写像でデータ点から作る．
A
A
m
親の計算
104
2011/09/30 列挙学校（再放送），有村博紀，北大
極大2次元幾何グラフのマイニング
幾何変換（並進・回転・拡大）のもとで頻出で
極大な点配置レイアウトを発見 (Arimura, Uno, Shimozono, DS'07)
応用：空間データ，物体の配置図・設計図データ
タンパク質分子に拡張（3次元&誤差）(Nowozin,Tsuda, ICDM'08）
y
A
2.0
g
1.0
Goemetric Graph Database
A
1.0
A
g
g
g
g
g
A
g
A
2.0
Ag
A
g
gA
Graph
Pattern
3.0 x
Hiroki Arimura, Takeaki Uno, Shinichi Shimozono: Time and Space Efficient Discovery of
Maximal Geometric Graphs. Discovery Science 2007: 42-55
Sebastian Nowozin, Koji Tsuda: Frequent Subgraph Retrieval in Geometric Graph Databases. 105
ICDM 2008: 953-958
FIT2008, 有村博紀，北海道大学
おわりに
Applications
and future
directions
半構造データマイニングのシナリオ
107
応用：最適パターン発見
すべての可能な部分構造の中で，統計的評価関数を
最小化するパターンを発見する
統計的評価関数
• 分類誤差
• 情報エントロピー
• Gini 指標ｓ
f(p): 不均衡関数
ノイズに強い．性能保障が可能
さまざまな知識獲得問題に対応可能
最近の機械学習アルゴリズムと組み合わせて，
分類，予測，クラスタリングに応用
p : パターンが出現
する正例の割合
0%
悪い パターン
9 positives
9 negatives
50%
100%
良い パターン
8 positives
2 negatives
108
応用：半構造データの自動分類
機械学習の素性抽出に使う
unknown function f : Graphs → {+1, -1}
１．入力グラフから
素性として，多数の特
徴的な部分構造を抽
出
２．機械学習手法を用いて，
未知の分類関数を学習
f : Graphs → {+1, -1}
C
H
C C
C
X
X
H
H
H
HTCGCGAGGT
H
TCGCGAGGCTAGCT
TCGCGAGGCTAT
-1
+1
H
-1
H
-1
H
N
H
X X
H
-1
H
Fe
+1
H
H
GCAGAGTAT
+1
H
H
+1
TCGCGAGGCTAT
H
N
+1
109
応用：半構造データの自動分類
1990年代に機械学習分野で，高性能予測
の新しい理論が急速に進展
決定木
最初の実用的予測アルゴリズム
ブースティング
多数の機械学習アルゴリズムを
統合して高精度予測
オンライン予測の理論
SVM
現在の state-of-the-art methods
高次元空間と多様なデータへ
マージン最適化＋カーネル法
鍵となる技術
ブースティング学習
（Boosting）
SVMとカーネル法（サポート
ベクトル機械）
ニューラルネットワーク
オンライン予測とゲーム理論
計算学習理論
研究者
ブースティング, SVM：渡辺
治・金森（東工大）
SVM：津田宏治（AIST），鹿
島久嗣（IBM TRL）
オンライン予測：瀧本英二（東
北大）
110
機械学習アルゴリズムへの応用
2011/09/30 列挙学校（再
有村博紀，北大
放送）
ブースティング (Boosting) [Freund, Shapire 1996]
多数の機械学習アルゴリズムを統合して高精度予測
オンライン予測の理論と深い関連
SVM (Support Vector Machines) [Vapnik 1996]
マージン最大化による現在の state-of-the-art methods
カーネル法を用いた高次元空間と多様なデータへの拡張
これらの学習アルゴリズムと，重みつきアイテム集合マイニング
を組み合わせて利用できる
キーワード: Boosting, SVM, オンライン予測, ニューラルネット, 計算学習理論
国際会議: NIPS, ICML, COLT, ALT
• V. Vapnik, Statistical Learning Theory, Wiley, 1998. (textbook)
• N. Cristianini and J. Shawe-Taylor, An introduction to support vector machines and other
kernel-based learning methods, Cambridge, 2000. (textbook)
• Y. Freund and R. E. Schapire, A decisiontheoretic generalization of on-line learning and
an application to boosting, JCSS, 55, 119-139, 1997. (AdaBoost)
• 金森, 畑埜, 渡辺,ブースティング: 学習アルゴリズムの設計技法, 森北出版 (text book)
111
111
これからのデータマイニング
膨大なデータ集積
多数の独立したＣＰＵ
ネットワークによる結合
多くの計算リクエスト
112
「集中」
さまざまなデバイス
多様な人間活動と応用
多様で非均一な時空間
不完全で複雑なデータと情報
「分散」
2011/09/30 列挙学校（再放送）
まとめ：半構造データマイニング
データマイニング
大量のデータから有用なパターンや規則を
半自動的にとりだす方法の研究
1990年代半ばに顕在化．定型データを対象とする
3. 新たな
知識の構築
半構造データ
多様な構造をもつ膨大なデータ
従来のデータマイニング手法は，
半構造データには直接適用不可能
2. 知識を
パターンや規則と
して発見
新しい半構造データマイニング技術が必要
高速かつ頑健なマイニング技術が鍵
JSTさきがけ研究「情報と知」(H11-H13)
文科省科研費 特定「発見科学」(H10-H12),
「情報学」(H13-H17), 基盤研究B(H12-H14,
H15-H17)等
H
文科省科研費特別推進研究（平成１７年～１
９年）「知識基盤形成のための大規模半構造
データからの超高速パターン発見」
CC
XX
H
H
知識
Knowledge
半構造パターン発見
Pattern Discovery
知識を有機的に
つなげる
半構造データ
Semi-structured Data
CC
H XX
H
113
今回の講義（まとめ）
2011/09/30 列挙学校（再
有村博紀，北大
放送）
４コマ目の目的：
データマイニングを題材に
列挙はどんなことに使えそうか？
データマイニング(DM)と機械学習における
列挙に関連した話題を提供
DMの歴史をすこし
パート1: データマイニングと頻出集合発見
パート２: 構造データのマイニング
（木とグラフ）
114
http://www.sigkdd.org/kdd/1995/poster/kdd1995-poster-thumb.jpg
© Copyright 2024 ExpyDoc
