飽和系列パターンの

多項式時間列挙アルゴリズムの実装

谷研究室 栗原 純

２月１０日(金)

飽和系列パターンの

多項式時間列挙アルゴリズムの実装

谷研究室 栗原 純

２月１０日(金)

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

研究目的

データベースからの頻出アイテム集合発見はデータマイニングにおける代表的な研究トピックである。

一般に膨大な数の互いに類似した頻出パターンが出力されるという問題がある。

飽和系列パターンの多項式時間列挙アルゴリズム

系列パターン発見を効率化できる！

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

準備

長さ

の系列パターン : 任意の系列

系列データベース(データベース)：

p

r

x =

p

r

t

q

s

y =

p

r

x =

p

r

t

q

s

y =

p

r

t

x =

p

r

t

q

s

y =

p

r

t

x =

p

r

t

q

s

y =

部分系列であるという。

真部分系列であるという。

x =

y =

p

r

t

x =

p

r

t

q

s

y =

位置出現：

p

r

t

x =

p

r

t

q

s

y =

位置出現：

位置出現集合：

文書出現集合：

非負整数である最小頻度パラメータ

に対して

がS上で

ー頻出であるとは、

が成立することをいう。

データベースS

bc {A3,B4,D4}

abc {A3,B4,D4}

頻出である。

飽和系列パターン：

与えられたデータベース中で同じ出現集合をもつような系列パターン中で、部分系列関係に関して極大な系列パターンである。

上の位置飽和系列パターン：

上の文書飽和系列パターン：

データベースS

bc {A3,B4,D4}

abc {A3,B4,D4}

位置飽和系列パターンではない

文書飽和系列パターンではない

データベースS

bc {A3,B4,D4}

abc {A3,B4,D4}

位置飽和系列パターンかつ文書飽和系列パターンである

と書く。

拡張であるという。

パターンの拡張において、記号を挿入する場所をパターンの右端に制限して、次の定義を得る。

定義

最右拡張という。

定理１

に対して、次の(1)と(2)は等価である：

親といい、

子という。

=

親

子

定理2

親

子

位置飽和系列パターン

位置飽和系列パターン

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

多項式時間列挙アルゴリズム

入力：系列データベース

最小頻度

出力：

上のすべての飽和パターン

空パターンからはじめて、親パターンから子パターンをすべて試しながら、探索木を深さ優先探索することで、S上のすべての飽和パターンを重複なく列挙する

各パターンにおいて、それが飽和性と頻出性を満たさなく

なった場合は、ただちにその子孫の探索を打ち切って、

次の候補を探索する

多項式時間列挙アルゴリズム

データベースS

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aaa{C4,C5}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aab{B3}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

aaca{}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

ab{A2,B3,C2,D2}

aba{C3,C4,C5,D3}

abc{A3,B4,B5,D4}

ac{A3,B4,B5,D4}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

ab{A2,B3,C2,D2}

aba{C3,C4,C5,D3}

abc{A3,B4,B5,D4}

b{A2,B3,C2,D2}

データベースS

ε{A1,A2,A3,B1,B2,...,D4}

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

ab{A2,B3,C2,D2}

aba{C3,C4,C5,D3}

abc{A3,B4,B5,D4}

c{A3,B4,B5,D4}

データベースS

a{A1,B1,B2,C1,C3,

C4,C5,D1,D3}

aa{B2,C3,C4,C5,D3}

aac{B4,

B5,D4}

ab{A2,B3,C2,D2}

aba{C3,C4,C5,D3}

abc{A3,B4,B5,D4}

ε{A1,A2,A3,B1,B2,...,D4}

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

実験結果

居酒屋データ

(レシート)

データ数：２００

実験結果

居酒屋データ

(レシート)

分類した

ファイルデータ

データ数：２００

ex). 頻出値＝20

ex). 頻出値＝45

ex). 頻出値＝50

実験結果

頻出

高

低

...

...

...

ビール

サラダ

揚げ物

カクテル

デザート

デザート

サラダ

列挙数

少

多

実験結果

目次

研究目的

準備

多項式時間列挙アルゴリズム

実験結果

今後の課題

今後の目標

データ数を増やして(単品メニュー)実験する

文書出現に関する飽和系列パターンの
多項式時間列挙アルゴリズム

おわり。

2005-12-07T16:45:56