Document

頻出パターン発見アルゴリズム入門
－アイテム集合からグラフまで－ Part 1
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
2008年6月13日人工知能学会
列挙（マイニング）の利用と難しさ
列挙 ≠ マイニング
・「マイニング」「発見」は、解を見つける手法の総称
・「列挙」は、全ての解を重複無く見つける手法の総称
 完全性の保証が必要
・マイニングでは、完全性を問わないこともあるが、
多くの場合暗に完全性を要求している
・列挙的なアプローチでは、
－全探索を効率化
－解候補を簡単に生成
－候補から良い解を選んで、最適性を保証
－全体像の把握、個別の解のランキング
列挙の利用法
・列挙は解を全て見つける  最適化してベストを見つける
－最適解がどの程度「最適」なのか、最適解からはわからない
 列挙なら、良い解の分布が分かる
－目的関数が真の目的に合致していると限らない場合、
解候補を列挙して真の目的で再評価
－目的関数の評価が大変な場合、直接的な探索が難しい場合
も、部分条件を満たす解を列挙して真の目的で再評価
－解の完全性を利用して、データの評価値として利用
列挙の難しさ
・列挙アルゴリズムを設計するときには、いくつかの難しさがある
－計算を速くする難しさ（計算アルゴリズム）
－全てを見つける難しさ（探索経路構築）
－重複を回避する難しさ（逆探索）
－同型なものを同一視する難しさ（標準型）
…
しかし、実際はうまく解ける物も多い
探索の難しさ
・列挙の対象はたいてい、１つ見つけるのは簡単な物
・今まで見つけた物が全ての解であるか、どのように調べる？
－経路列挙で、今まで見つけた経路が全てか調べる？
・クリークやパス（経路）は、隣接性を持つ
－クリークは１つずつ付け足すと全てが得られる
－パスは再帰的な場合分けができ、空の問題のチェックが簡単
・しかし、こううまくいくものばかりではない。
－極大な××、極小な○○
－あの条件とこの条件とこの条件と．．．
 互いに隣接していない、場合分けも難しい
111…1
頻出
000…0
重複を回避する難しさ
・探索はできるので、全て見つけることはできるとする
・しかし、どうやって同じものを２度出さないようにするか、あるいは
同じ探索を繰り返さないようにするかは、それほど自明でない
・簡単に回避するなら、解を全部メモリに保存すればよい
 解が多くなるとメモリ効率が悪い
 動的にメモリを確保して解を保存するルーチンと、解を効率
よく検索するルーチンが必要（ハッシュがあればいい）
・今の解を出力するか、あるいは探索を続けるか、過去の履歴を
見ずに、解自体から計算できるようにすることが重要
計算の高速化
・高速化は、通常のアルゴリズムに対するテクニックが有効
・各反復の計算の高速化
－２分木、ハッシュなどのデータ構造、
－隣接行列  接続行列による疎性の利用
－よけいな処理を省いて、高速化  計算オーダー減少
－キャッシュ、コードの最適化
・列挙の場合、解を少しずつ変更する操作が多いので、
データを動的に管理する方法が有効
 各頂点の次数、重み和、頻出度など
・指数的に広がる再帰構造を使った高速化が特に有効
アルゴリズム理論の利点
・大規模な計算には、アルゴリズム理論に基づいた技術が有効
 アルゴリズム理論による高速化は、問題の大きさに対する計算
時間の増加を抑える
 計算の結果は変化しない
100項目
100万項目
2-3倍
10000倍
データが巨大になるほど、アルゴリズム改良の加速率は上がる
本レクチャーでは、パターンマイニングアルゴリズムの設計手法を
頻出集合・半構造のマイニングについて解説
３．頻出集合の列挙（LCM）
頻出パターンの列挙
・データベースの中に多く現れるパターンを全て見つける問題を
頻出パターン列挙（あるいは発見、マイニング）問題という
データベース：トランザクション、ツリー、グラフ、多次元ベクトル
パターン：部分集合、木、パス・サイクル、グラフ、図形
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
頻出する
パターンを抽出
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
・実験1● ,実験3 ▲
・実験2● ,実験4●
・実験2●, 実験3 ▲, 実験4●
・実験2▲ ,実験3 ▲
．
．
．
・ ATGCAT
・ CCCGGGTAA
・ GGCGTTA
・ ATAAGGG
．
．
．
トランザクションデータベース
トランザクションデータベース：
各トランザクション T がアイテム集合 E の部分集合
になっているようなデータベース、つまり、∀T ∈D, T ⊆ E
1,2,5,6,7,9
集合 P に対して：
2,3,4,5
P の出現： P を含むD のトランザクション
D ＝ 1,2,7,8,9
P の出現集合 Occ(P)： P の出現の集合
1,7,9
P の頻出度 frq( P)： P の出現集合の大きさ
2,7,9
2
{1,2}の出現集合
＝ { {1,2,5,6,7,9},
{1,2,7,8,9} }
{2,7,9}の出現集合
＝ { {1,2,5,6,7,9},
{1,2,7,8,9},
{2,7,9} }
頻出集合
・頻出集合： D の定数σ個以上のトランザクションに含まれる集合
（頻出度がσ以上の集合）（ σを最小サポートとよぶ）
例）データベース D の3つ以上のトランザクションに含まれる集合
1,2,5,6,7,9
2,3,4,5
D ＝ 1,2,7,8,9
1,7,9
2,7,9
2
３つ以上に含まれるもの
{1} {2} {7} {9}
{1,7} {1,9}
{2,7} {2,9} {7,9}
{1,7,9} {2,7,9}
頻出集合列挙は、与えられたトランザクションデータベース
と最小サポートσに対して、頻出集合を全て見つける問題
パターンマイニングの応用
売上げデータの分析
・雑誌とおにぎりが良く一緒に売れてます
・夜訪れる男性は高めの弁当を買ってます
・さんまと大根とすだちは
セット販売したらどうですか？
・・・
画像認識
項目の自動分類
遺伝子Z： ●○★
遺伝子A： ●△▲
遺伝子Z： ●○★
遺伝子B： ●△▲
・・・遺伝子F1： ■□
遺伝子D： ●△▲
遺伝子F2： ■□
・・・
・・・
Webページのトピック分類
・みかんとみかんでない画像を分ける
特徴を見つける
・ Webページを、リンクやキーワードの
組合せで、トピック毎に分類
全国
ラーメンラーメン
巡りの旅人
カツカレー
と私カレーの
作り方
基礎的な問題なので、応用に広がりがある
頻出集合の単調性
・工夫をするためには、何か問題の特徴を
つかまなくてはいけない
111…1
・使えそうなのが、「頻出集合の部分集合は
必ず頻出」、というもの（単調性という）
 つまり、ハッセ図（包含関係を
図示したもの）の上では、
頻出集合が存在する
エリアはつながっている
頻出
000…0
1,2,3,4
1,2,3 1,2,4
1,2
1,3
1
空集合から出発して、山登り的に（重複を出
さないように）探索（共通の基本アイディア）
1,3,4
1,4
2,3,4
2,3
2,4
3,4
2
3
4
φ
マイニングの技術の歴史
・いくつかのブレイクスルーがある
第１世代
apriori （幅優先）：ディスク上のデータ用
111…1
頻出
第２世代
深さ優先探索：データをメモリに保持
000…0
第３世代
データベースの圧縮： trie(FP-tree) などで再帰的に圧縮
第４世代？
基数ソート、振り分け、および ppc拡張による飽和集合列挙
第１世代： apriori
・各レベルごとに頻出集合の候補（１つ下のレベルの頻出集合に１つアイ
テムを加えたもの）を生成し、それらの頻出度を計算
S0={φ}, k := 0
while Sk が空でない
for each トランザクション Ti
for each P∈Sk,P⊆Ti
P の頻出度＋１
頻出でない P を Sk から除去
for each P∈Sk
for each アイテム e
P+e を Sk+1 に挿入
1,2,3,4
1,2,3 1,2,4
1,2
1,3
1
1,3,4
1,4
2,3,4
2,3
2,4 3,4
2
3
φ
・ P+e の部分集合で、Skに入っていないものがあれば頻出でない
・１レベルにつき、ディスクのスキャンが一回ですむ
・メモリ使用量と検索の手間がボトルネック
4
第２世代：深さ優先（バックトラック）
・空集合から出発し、頻出集合である限り再帰的にアイテムを追加
Backtrack (P, Occ(P) )
output P
for each e > Pの末尾（ P の最大のアイテム）
Occ(P∪e) = Occ(P) ∩ Occ(e)
If P∪e が頻出集合 then
call Backtrack (P＋e)
ダウンプロジェクト
1,2,3,4
1,2,3 1,2,4 1,3,4 2,3,4
・メモリにデータベースが全部
乗らないと効率が悪い
・出現を更新していくところがポイント
1,2 1,3 1,4 2,3 2,4 3,4
1
3
2
φ
4
第３世代：再帰的データ圧縮（FP-tree）
・データベースの縮約により、再帰の深いレベルでの高速化する
（１）前回追加したアイテムより小さいアイテムは消す
（２）現在の出現集合からできるデータベースの中で、頻出になって
いないアイテムは消去する
（再帰呼び出しの中で加えられることが無いから）
（３）まったく同一のトランザクションは、１つにまとめる
・実データだと、下のほうのレベルではだいたい大きさが定数になる
・ FP-tree（trie）を使うと、共有する prefix
も圧縮されるが、オーバーヘッドも大きい
１
１
２
２
５
６
４
７
４
３
２
４
４
３
１
σが小さいときと速度の大きな差はない
３
４
４
５
６
７
６
７
６
７
末広がり性
・再帰の末端以外はさほど高速化されていないのに、なぜ実
際には大幅に高速化されるのか？
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 反復の平均計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間短
ダウンプロジェクトや圧縮による末端の高速化が
全体を高速化している
第４？世代：振り分け・基数ソート・ppc拡張
・ trie を使ったデータの圧縮には nlogn の時間がかかる
 基数ソートで、（ハッシュでの）オーバーヘッドなしに線形時間
・疎な行列の転置を使って、追加するアイテムの出現を、いっぺん
に線形時間で求める（振り分け）
・ ppc 拡張を用いて飽和集合を無駄なく列挙
１
１
３
２
２
６
４
７
４
３
２
５
４
３
１
４
４
４
５
６
７
６
７
６
７
振り分け
for each P の各出現 T
for each T に含まれる e, e > Pの末尾
eのバケツに T を挿入
・計算時間は,
P の各出現の (Pの末尾) より大きなアイテムの数の総和
・各アイテムに対する再帰呼び出しの
準備をいっぺんにすることで、
効率化している
A: 1,2,5,6,7
B: 2,3,4,5
C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
振り分けの動画
・ Compute the denotations of P ∪{i} for all i’s at once,
A 1 A2
1,2,5,6,7,9
2,3,4,5
D＝ 1,2,7,8,9
1,7,9
2,7,9
P = {1,7}
2
A5 A6 7
A9
B
2 3 4 5
C 1 C2
7 C8 C9
D 1
7
D9
7
9
E
2
F
2
１反復の計算時間のイメージ
・普通に頻出度の計算をすると
各 P＋e に対してデータを
一回スキャンする
・ダウンプロジェクトは
Occ(P) と Occ({e}) をスキャンする
 Occ(P) を n-i 回スキャンし、
データベースの i より大きな
アイテムをスキャンする
n個
＋
(n-i)個
i
・振り分けは出現Occ(P) 中のトランザ
クションの i より大きい部分をスキャンする
Occ(P)
i
実データ
（すかすか）
平均の大きさ5-10
BMS-POS
BMSWebView2
retail
実データ
（すかすか）
メモリ使用量
BMS-POS
BMSWebView2
retail
技術のまとめ
第１世代 apriori （幅優先）
ディスク上のデータ用のスキャン回数を最小化
データがメモリに乗らないとき速い
第２世代深さ優先（バックトラック）
出現の集合を保持するところがミソ
データをメモリに入ると速い
第３世代再帰的データ圧縮(FP-tree)
末端の計算の高速化が全体を高速化
第４世代基数ソート、振り分け、 ppc拡張
検索技術からアルゴリズム技術へ
111…1
頻出
000…0
３．２飽和集合の列挙
頻出集合の問題点
・面白い頻出集合を見つけようとすると、σを小さくする必要がある
 大量の頻出集合が出てくる
・情報を失わずに、頻出集合的な、数の少ないものを
見つけるようにモデルを変えたい
111…1
１．極大頻出集合：
他の頻出集合に含まれない頻出集合
２．飽和集合：
出現集合が等しいものの中で極大なもの
000…0
極大頻出集合と飽和集合の例
・頻出集合を出現集合で分類
1,2,5,6,7,9
2,3,4,5
D＝ 1,2,7,8,9
1,7,9
2,7,9
2
３つ以上に含まれるもの
{1}
{2}
{7}
{1,7}
{1,9}
{2,7}
{2,9}
{1,7,9}
{9}
{7,9}
{2,7,9}
頻出飽和集合
極大頻出集合
出現集合の共通部分が
飽和集合になる
極大頻出集合と飽和集合
極大頻出集合
・多項式時間で列挙できるかどうか、未解決
・クリークと同じように枝刈りをすると、高速に列挙できる
・数が少ないがσによる解のぶれが大きい
飽和集合
・逆探索という探索手法で多項式時間列挙可能
・離散アルゴリズムと末広がり性を用いて、高速列挙可能
・出現の意味で情報の損失がない
・ノイズが多いと出現集合が等しいものが少なくなり、
解の減少効率が悪くなる
両者とも、１つあたりほぼ定数時間、1秒間に1～10万個
２部グラフによる表現
・アイテム、トランザクションを頂点とし、包含関係を枝とする
A: 1,2,5,6,7,9
B: 2,3,4,5
D＝ C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
1 2 3 4 5 6 7 8 9 P
A
B
C
D
E
F Occ(P)
・アイテム集合と、それらを含むトランザクションの集合
 ２部グラフの２部クリーク
・アイテム集合とその出現集合
 トランザクション側が極大な２部クリーク
・飽和集合とその出現集合  極大２部クリーク
・トランザクション集合の列挙へも（構造パターンにも適用可）
隣接行列で見ると
・アイテム、トランザクションを頂点とし、包含関係を枝とする
A: 1,2,5,6,7,9
B: 2,3,4,5
D＝ C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
1 2 3 4 5 6 7 8 9
A 1 1
B
1 1 1
1
1 1 1 1
C 1 1
1 1 1
D 1
1
1
1
1
E
1
F
1
・アイテム集合と、それらを含むトランザクションの集合
 全てのセルに1が入っている部分行列
飽和集合の列挙手法
第１世代頻出集合列挙ベース
－頻出集合列挙アルゴリズムをベースに、多少無駄な計算を
省く
－飽和集合のよさが出ない。計算時間の改善も少ない
第２世代保存＋枝狩り
－見つけた解を保存し、それを用いて無駄な分枝を刈る
－計算速度はまあまあ
－解保存のためにメモリを使用し、それがひとつのネック
第３世代逆探索＋データベース縮約
－計算効率が良い
－解保存用のメモリが不要
（LCM）
飽和集合の隣接関係
・飽和集合から、添え字の大きい順に要素を抜いていく
・どこかで出現集合が大きくなる
・その出現集合の飽和集合を求める
・こうして求めた飽和集合を、親とする（一意的に定まる）
・親の頻出度は必ず真に大きいので、
親子関係は非巡回的
 親子関係は有向根付き木を導出する
逆探索
親子関係は有向根付き木を導出する
この木を深さ優先探索すれば全ての解を見つけられる
・探索には、子供を見つけるアルゴリズムがあれば十分
・子供が１つあたり多項式時間で見つかれば、全体も多項式時間
（親に要素を１つ加えて極大をとった飽和集合が子供になる）
非巡回的な親子関係と、子供を見つける多項式時間アル
ゴリズムがあれば、なんでも多項式時間列挙ができる
親子関係の例
・データベースの全ての
飽和集合とその親子関係
φ
2
1,2,5,6,7,9
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
2,7,9
2
7,9
1,7,9
2,5
1,2,7,9
2,3,4,5
出現集合が隣接
親子関係（ppc拡張）
1,2,7,8,9
1,2,5,6,7,9
2,7,9
子どもを求める
・子どもから親を作る際に抜いた、最後のアイテムを親に追加
すると、出現集合は子どもと等しくなる
 子どもは、アイテムを１つ追加して、出現集合の共通部分
をとると得られる
 とはいえ、そのようにして作ったもの全てが子どもになると
は限らない
 子どもである条件は、抜いたアイテムより前の部分に、新
しくアイテムが追加されないこと
（prefix preserving closure extension, prefix保存飽和拡張）
データベースの縮小
・頻出集合と同じように、データベースの縮小をしたい
・追加したアイテムの前半部分を捨てられない
 ppc 拡張の際に参照されるので
・しかし、
－後半が同一なら、必ず同時に Occ に入る
－必要なのは前半（prefix）の共通部分だけ
なので、前半の共通部分をとり、保存すればよい
・多くのトランザクションが1つになれば、
自然に共通部分も小さくなる
１
１
２
２
５
６
４
７
４
３
２
４
４
３
１
θが小さいときと速度の大きな差はない
３
４
４
５
６
７
６
７
６
７
比較の手間
・K+e の出現の共通部分、素直に計算してもよいが、「共通部分
がKと等しいか」を調べるだけなので、必ずしも全て計算する必
要はない
 異なることがわかった時点で、計算をやめてよい
・ K+e の出現それぞれを小さい順にたどり、
K
全てに共通するものがあるか調べる
3 4 6 9 11
・全てに共通するものがあったら
K に入っているか調べる
・前回たどったところで止まって
おき、次回はそこからたどる
4 11
1 3 4 5 9 11
K+e の
出現集合
23 4 5 9 11
1 2 4 6 9 11
1 4 9 11
ビットマトリクス
・スウィープポインタは、行列の形でデータを持ってないがゆえ
の工夫。隣接行列を持って入れば、もっと単純に速くできる
・が、隣接行列は、大きすぎて構築することすら不可能
・出現集合がある程度以下に小さくなったところで、
行列を構築しよう
 ビットで持てば、各列が1つの変数に入る！
ビットマトリクスの定数時間計算
・各アイテムに対応する列を１変数で持っていると、K+e の出現全
てにそのアイテムが含まれるかどうか、1ステップでチェックできる
・ K+e の出現のビットパターンと、アイテム i の列のビットパターン
の AND をとる
・アイテム i が K+e の出現全てに含まれるなら、共通部分はK+e
の出現ビットパターンと等しくなる
K の頂点
・・・
K<i ∩N(vi)
実データ
（すかすか）
平均の大きさ5-10
BMS-POS
BMSWebView2
retail
実データ
（すかすか）
メモリ使用量
BMS-POS
BMSWebView2
retail
密（50%程度）で
構造があるデータ
connect
pumsb
chess
密で構造がある
データ、メモリ量
connect
pumsb
chess
頻出集合発見の応用事例
応用：他の頻出パターンマイニング
・パターンマイニングは、基本的にパターン毎にプログラムを組み
替える必要がある
・もし、部分パターン列挙が可能であれば、各項目に含まれる部分
パターンを列挙してしまうと、アイテム集合マイニングに帰着できる
例）項目が高さ２以下の木であるデータから、
高さ2以下の木のパターンを見つける
1
2
{1, 2, 3, 4}
3
4
5
・・・
グラフ、シークエンスの集合など
各項目が×××の集合
応用：他の頻出パターンマイニング
・部分パターンがあまり多くない場合、例えばマルチセットのマイニ
ングや各項目が複数のグラフや系列でできている場合など、パター
ンが構造の集合、という形をしているときに有効なテクニックである。
・有向非閉路グラフから頻出有向グラフを見つけるアルゴリズム
有向
非閉路
グラフ
⊇
Alexandre Termier, Yoshinori Tamada, Seiya Imoto, Takashi Washio,
Tomoyuki Higuchi, From Closed Tree Mining to Closed DAG Mining
応用：遺伝子のクラスタリング
・多くの遺伝子は他の遺伝子と共起して機能する
・臓器などの部位、発達段階による時期などで、一緒に発現する
・共起しやすい遺伝子をグループ化すると、関係の深い遺伝子が
分かるだろう
A: ● ● ●
●
B: ● ● ● ●
C: ● ● ●
●
・トランザクション 発現する場所（時）、アイテム 遺伝子
とすると、頻出集合は、多くの場所で共通に発現する遺伝子のグ
ループになる。（実際は飽和集合を見つけている）
・似通った物を消すため、25%の領域が他に含まれるものは消去
Y. Okada, W. Fujibuchi, P. Horton, Module Discovery in
Gene Expression Data Using Closed Itemset Mining Algorithm
応用：分類規則の発見
・パターンが含まれる項目の重みの合計を考えると、重み付きの
頻出パターン発見ができる
正例（＋の重み）
 含まれることが重要な項目を指定できる
 頻出パターンの場合、項目の重みは全て１負例（－の重み）
・さらに負の重みを許すと、「含まれたくない項目」が表現できる
 自動分類を行いたいデータに対して、正例の項目には正の重み、
負例のデータには負の重みを与えると、分類規則に相当するアイ
テム集合が見つかる
・見つかるパターン数に対する計算時間は長くなるが、それでも実
用の範囲内
応用：画像分類
・自動分類の手法の一つに、各項目の特徴ベクトルと基準ベクトル
の内積を取って、その値によって正例と負例に分類する方法があ
る
・基準ベクトルを最適化して、分類規則を学習する
・特徴ベクトルに使う特徴には、属性値をそのまま使うことが多い
が、そこにアイテム集合を使うと可能性が広がる
・変数が多くなるので、列生成法を使って最適化する
S. Nowozin, K. Tsuda, T. Uno, T. Kudo, G. Bakir
Weighted Substructure Mining for Image Analysis
２部グラフによる表現
・アイテム、トランザクションを頂点とし、包含関係を枝とする
A: 1,2,5,6,7,9
B: 2,3,4,5
D＝ C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
1 2 3 4 5 6 7 8 9
A
B
C
D
E
・アイテム集合と、それらを含むトランザクションの集合
 ２部グラフの２部クリーク
・アイテム集合とその出現集合
 トランザクション側が極大な２部クリーク
F
応用：複合語による単語の分類
・単語を、複合語の作り方を
使ってグループに分類
・単語が頂点、単語を組合せて
複合語ができるとき、枝を張る
として2部グラフを作る
関東
地方
関西
地区
中国
電力
北陸
・極大2部クリークを見つけると、それが類義語、あるいは反対語な
ど、関連する意味を持つ単語群になるだろう
中渡瀬秀一, 相澤彰子
完全N部グラフ構造を用いた単語の多義性獲得
応用： webコミュニティーの抽出
・ web のリンク構造から、
2部クリークを見つけ出す
－リンク元: 共通の趣味を持つページ
－リンク先: 同じカテゴリのページ
・グラフから2部クリークを見つける
には、グラフを2部グラフに変換
グラフ
サイト
サイト
趣味バイク
ホンダ
バイク好き
カワサキ
バイク万歳
ヤマハ
バイク人生
隣接している頂
点間に枝を張る
頂点
集合
頂点
集合
実装の参照先
・宇野のHP （頻出集合の他の構造のマイニング、列挙や類似比
較アルゴリズムの実装）
http:research.nii.ac.jp/~uno/
・実装、問題、論文のレポジトリ（比較実験の数々も）
http://fimi.cs.helsinki.fi/
・羽室・森田による GUI 「IGVMiner」（GUIによる操作と結果の
可視化。情報大航海プロジェクトの成果物）
応用：その他
・ブログユーザ空間からの頻出なコミュニティ抽出法
・ Extracting generic basis of association rules from SAGE data
・ローカルデータベースにおけるアイテム集合の相関の違いに基
づく隠れた相関の発見
・コンピュータゲームプレイヤの静的評価関数の自動生成に関する
研究動向
・駒位置と効き関係に注目した詰み評価関数の自動生成
・Mining complex genotypic features for predicting HIV-1 drug
resistance
・・・
参考文献など
・頻出集合およびその応用 (’90～) 星の数ほど
“frequent pattern”、”frequent itemset” で検索すると出てくる
・極大頻出集合およびその応用 (’90～) やはり多い
“maximal frequent itemset” などで検索すると出てくる
・ pasquerらのアルゴリズム (‘99) 飽和集合の導入
・宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム
・実装 LCM: (Linear time Closed itemset Miner) 宇野のHP
http:research.nii.ac.jp/~uno/
・レポジトリ（実装、論文、比較実験の数々）
http://fimi.cs.helsinki.fi/
・中野・宇野・有村（’03～）順序木・無順序木の多項式時間頻出列挙
前半のまとめ
・列挙アルゴリズムの難しさ：
－簡単な構造でも、いいかげんでは劇的に失敗
・頻出集合マイニングと高速化の技法：
－１－４世代アルゴリズム
－計算の局所性と、末端高速化による改良
・頻出飽和集合と逆探索：
－親子関係による探索路の構築
－計算の局所性と、末端高速化による改良
・応用研究、実社会での利用：
－クラスタリング、分類、...
－他のデータマイニングアルゴリズムでの利用
列挙的なモデルを使った研究や
システムの開発が進むと嬉しいです

Download Report