DEIM Forum 2016 P4-2

アイテム集合の和のクラスに対する効率良い代表パターンマイニング
Space Eﬃcient Mining of Closed Disjunctive Itemsets from Databases
長部

和仁†

平田

耕一††

宇野

毅明†††

有村

博紀†

† 北海道大学情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目†† 九州工業大学情報工学研究院 〒 820-8502 福岡県飯塚市川津 680-4††† 国立情報学研究所 〒 101-8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{kz-osabe,arim}@ist.hokudai.ac.jp, ††hirata@dumbo.ai.kyutech.ac.jp, †††uno@nii.jp
あらまし

大規模データの出現と機械学習技術の高度化を背景として，複雑な組み合わせ特徴を見つけ出すパターン

マイニング技術が注目されている．膨大な数の類似パターンを回避するために，飽和パターン（closed pattern）とよばれる代表元を見つける手法が提案されている．本稿では，飽和アイテム集合発見問題（closed itemset mining,CIM）を一般化して，飽和アイテム集合和発見問題（closed disjunctive item sets mining, CDM）へ拡張する．冗長性を回避するためのさまざまなアイテム集合和の等価性の概念を導入した上で，タイプ 1 からタイプ 4 までの飽和アイテム集合和を定義する．既存研究の前処理で全ての飽和集合を計算し，それらを組み合わせる戦略におけるメモリ
爆発の問題に対して，本稿では，高速な飽和アイテム集合発見アルゴリズムの LCM アルゴリズムに基づいて，解集合のイタレータ（繰り返し子）である LCMIterator を構成する．これは，データベースと最小頻度を与えて初期化すると，後続関数（next 関数）を呼ぶたびに，すべての解を保持することなく，LCM の解を一つずつ漸増的に計算して返す関数である．次に，これを用いて，タイプ 4 の飽和パターン和のクラスに対して，メモリ効率の良い列挙アルゴリ
ズム CDM（Closed Disjunctive Itemsets Miner）を与える．これはすべての飽和アイテム集合をメモリ上に保持することなく，LCMIterator を用いて，サイズ M 以下のタイプ 4 の飽和アイテム和すべてを発見する．
キーワード

パターンマイニング, 深さ優先探索,LCM, 複合パターンマイニング, 列挙, 頻出アイテム集合, 特徴発見

1. は じ め に
1. 1 背景来のアイテム集合マイニングにおいては，この問題に対して飽
和パターン（closed pattern）とよばれるデータベース中で同じ出現を持つようなパターンからなる同値類の代表元を見つけ

近年，大規模データからの知識発見技術が注目されている．

る手法が提案されている．例えば，Uno と Kiyomi，Arimura

計算技術の進歩に伴い，これまで処理が困難だった規模の巨大らの LCM アルゴリズムは，飽和アイテム集合を時間とメモリなデータを扱うことが可能となり，また，機械学習やデータマの両方で効率よく発見する [3]．

イニング技術の高度化によって，そこから有用な知見を得る

1. 3 本稿の目的ことができるようになった．知識発見の普及に伴い，扱われる

本稿では，頻出アイテム集合マイニングを拡張し，発見する

データは多様になり，複雑な現象を予測する技術が求められて特徴を複合特徴，すなわちパターンの和として，効率よく頻出いる．同時に，高度な知識発見，統計的に有意なデータマイニ

なパターン和を発見するマイニング問題を考察する．パターン

ングや正則化などの技術の提案により，組み合わせパターンを和に対しては，飽和パターンマイニングの場合のような冗長な特徴として用いた高次元データを扱うことも可能になってきた．

パターン和列挙を回避するための研究は，まだほとんど行わ

以上の背景より，高度な知識発見を行うにあたって，二値デー

れていない．とくに，冗長性の基本となるパターン和の等価性

タベース上の複雑な特徴の発見を行うパターンマイニング技術（どのようなパターンが，見かけは異なっていても「同じパターが注目されるようになっている．

ン」なのかの定義）に関する厳密な定式化と，それらの定義間

1. 2 関 連 研 究の包含関係については，著者らの知る限りでは未だに研究され関連研究として，2006 年に Zhao と Zaki はデータベースかていないのが実情である [1–3]．そこで本稿では，冗長なパター

ら頻出な（一定の回数以上データに出現する）命題論理式を網

ン和の回避を考慮したパターン和マイニング問題のいくつかの羅的に発見するアルゴリズムを与えている [1]．また，2005 年

定式化を与え，関連するパターン和の族とマイニング問題の性に Shima と，Hirata，Harao らは，選言標準形の命題論理式，質を調べる．

すなわち，アイテム集合の和を網羅的に発見するアルゴリズム

1. 4 本稿の内容を与えている [2]．これらの研究に共通した問題点として，膨2 節で基本的な定義を導入したあと，3 節では，パターンの和

大な量の類似したパターンが発見されることがあげられる．従の族を導入する．4 節では，頻出アイテム集合発見問題をパター—1—

ンの和のクラスへと拡張する．さらに，冗長なパターン和の列

Algorithm 1 頻出パターンの LCM 列挙アルゴリズム．アイ

挙を避けるために，タイプ 1 からタイプ 4 までの飽和パターン

テム集合が Σ = {1, . . . , n} のとき，LCM(∅, 0, Σ; n, T, σ) デー

和の間の同値性を導入する．まず，演算子の可換性に注目した

タベース T 上の σ 頻出パターンを全て列挙する．

等価性を導入する．次に，冗長な要素パターンに関する等価性

1: procedure LCM(X, k, Occ0; n, T, σ)を考察する．最後に，要素パターンの出現集合に関する等価性

2://X は親アイテム集合であり，Occ0 = Occ(X, T ) はその出現リスト．

を導入し，対応する飽和パターン和の正規形を与える．これら
3:

Y := X ∪ {i};4:Occ := UpdateOcc(Occ0, i);5:

和アイテム集合を高速に発見する LCM アルゴリズムをもとに，

if |Occ| < σ then6:

return ;解集合のイタレータ（繰り返し子）である LCMIterator を構成

7:

X ∪ {i} を解として出力する．

する．次に，タイプ 4 の飽和パターン和のクラスに対して，メ8:

for each i := k + 1, . . . , n do

モリ効率の良い列挙アルゴリズム CDM（Closed Disjunctive

9:

Z = Closure(Y ∪ {i});Itemsets Miner）を与える．最後に，飽和パターン和の効率よ10:

if Y ∩ [1, i − 1] = Z ∩ [1, i − 1] then

い発見に関する問題点について議論する．5 節では，本稿をま11:をまとめて，従来研究 [2, 4] の定義を一般化する形で，飽和パターン和マイニング問題を定式化する．5 節では，はじめに飽▷ Occ は Y の出現リスト▷ 親へバックトラックする

LCM(Z, i, Occ; n, T, σ);

とめる．
12: procedure UpdateOcc(Occ0, i)

2. 準

備

本節では，本稿で必要な定義を与える．任意の整数の組 i <=j//ある X の出現リスト Occ0 から Occ(X ∪ {i}, T ) を漸増的13:に計算する．
14:に対して，[i, j] で区間 {i, i + 1, . . . , j} を表す．

2. 1 頻出アイテム集合マイニング
頻出アイテム集合マイニングとは，離散的なアイテム集合によって表現されるトランザクションの連なりであるトランザク
ションデータベース中に，一定の閾値を超えて頻出するアイテ
ム集合を見つけ出すアルゴリズムのことである．

Σ = {1, 2, ..., n} をアイテムの集合とする．ここで，Σ 中のアイテムは，Σ 上の自然な全順序として整数の大小関係

i <=Σ j ⇐⇒ i <= j をとる．以後，アイテムの全順序集合
(Σ, <
)
を考える．
=Σ
このとき，アイテムの集合 t⊂=Σ を Σ 上のトランザクションとし，T を Σ 上のトランザクションからなるデータベースとする．

⊂
X⊂=Σ をパターンまたはアイテム集合（itemset）とよび，X =tであるような T 中のトランザクション t を，X の出現（マッチ）return { t ∈ Occ0 | i ∈ t };度が等しいアイテム集合が T 中に存在しないとき，X を飽和集合とよぶ．飽和集合は出現頻度が等しい全てのパターンの代
表元となっている．より正確には，飽和集合は次のように定義されるアイテム集合の同値関係 ≡T に関する同値類の代表元になっていることが知られている．

X ≡T Y ⇐⇒ Occ(X, T ) = Occ(Y, T ).

(1)

したがって，飽和集合を列挙することで，必要な情報を失うことなく，算出する解の個数を絞ったマイニングを行うことができる．
アイテム集合 X について，X の閉包 (closure) を∩∩
Closure(X) :=Occ(X, T ) = { t ∈ T | X ⊂
=t }

(2)

という．T 中の出現の集合を Occ(X, T ) = {t|X ⊂=t, t ∈ T } とと定義すると，Closure(X) は X を部分集合として含む飽和集

表記し，X の出現集合とよぶ．出現集合の大きさ |Occ(X, T )|合となることが知られている [3]．さらに，X が飽和集合であを X の頻度といい，f req(X) と表記する．パターン X に関しることと，条件 Closure(X) = X が成立することは同値である．

て，f req(X) >= σ であるとき，パターン X は頻出であるとい

2. 3 LCM アルゴリズム

い，頻出の閾値 σ をサポートとよぶ．

LCM アルゴリズムは，宇野，有村らによって開発された，頻頻出アイテム集合マイニングは，データベース T において，

出飽和アイテム集合を高速に列挙するアルゴリズムである [3]．

出現頻度が閾値 σ を越えるようなパターンを列挙する問題であ

LCM は，LCM は深さ優先探索に基づくバックトラック型アルる．代表的な手法として，Agrawal らによるアプリオリアルゴ

ゴリズムであり，飽和集合発見の多くの先行アルゴリズムと同

リズム [5]，Bayardo らによるバックトラックアルゴリズム [6]様に閉包計算に基づく．

などが存在する．

通常，閉包計算による飽和アイテム集合の列挙では重複した解2. 2 飽和アイテム集合が生成されてしまうが，LCM では，次のようにプレフィックス保通常の頻出集合マイニングでは，指定したサポート σ につい

存飽和拡張という手法を利用することで，頻出飽和集合数に対して，f req(X) >= σ であるような全てのパターンを列挙する．しかし，このようにしてパターンを列挙するとき，非常に多くのて線形の時間計算量での列挙を実現している．飽和集合 X につ∩いて，コアアイテム core(X) を，Closure(X {1, ..., j}) = X

解を処理しなくてはいけない場合があり，こうした際には，冗が成り立つような最小の j と定義する．このとき，あるパター長な解を除外するために頻出飽和集合をマイニングするというン Y が X のプレフィックス保存飽和拡張 (prefix-preserving

方法が用いられる．

closure extension, PPC-extension) であるとは，あるアイテム

あるアイテム集合 X について，X を真に含み，かつ X と頻

i > core(X) について，—2—

(i) Y = Closure(X ∪ {i})，かつ(ii) X ∩ [1, i − 1] = Y ∩ [1, i − 1]
であることをいう．
任意の飽和集合 Y は，必ず他のある単一の飽和集合 X （Yの親と呼ばれる）からプレフィックス保存飽和拡張によって算出され，さらに，そのような X は一意であることがいえる [3]．

Algorithm 1 に LCM アルゴリズムの擬似コードを示す．
2. 4 アイテム集合と飽和アイテム集合の正規形
ここで，以下の議論で用いるパターン（アイテム集合）の族

図1に対する正規形を定める．アイテムの全順序集合を (Σ, <=Σ ) とおく．Σ 上のパターン X ⊂=Σ の正規形表現（canonical repre-

sentation）とは，次の (i) と (ii) を満たすようなアイテムの順
序列 X̂ = i1 · · · im である：

パターン和の族

アイテム集合 X = Xi の P への所属性を X ∈ P で表す．パターン和 P の出現集合 Occ(P, T ) を，要素パターンの出現集
合の和(i) {i1 , . . . , im } = X ，かつ(ii) i1 <= ... <
= im ．

Occ(P, T ) = Occ(X1 , T ) ∪ ... ∪ Occ(Xk , T )⊂=T

(4)

すなわち，パターン X の正規形とは，その要素を Σ 上の全順で定義する．P の頻度を f req(P, T ) := |Occ(P, T )| と定める．

序によって昇順に整列した列をいう（注 1）．与えられたパターン

最小サポート σ ∈ [0, |T |] に対して，f req(P ) >= σ であるとき，

X の正規形は一意である．パターン X の正規形を X̂ で表す．

データベース T 上で P は頻出である．

以後，正規形パターン全体の族を P̂ で表す．本稿でパターン

パターン和 P があるトランザクション t に出現するとは，あ和を列挙するときは，その要素パターンは正規形であるものだ

る1<=i<= k に対して，t ∈ Occ(Xi ) をいう．いいかえれば，けを考える．

パターン和 P の特徴関数は，要素パターンの特徴関数の選言

次に正規形のパターン上の全順序を導入する．パターン Xがパターン Y よりも辞書式順序で小さいことを，X <lex Y と書きし，次のいずれかを満たす場合として定義する：[t ∈ P ] := [t ∈ X1 ] ∨ · · · ∨ [t ∈ Xk ](5)として書ける．

(i) X が Y の真の接頭辞であるとき．
(ii) あ る 1 <= k <= min(|X|, |Y |) が 存 在 し て ，任 意 の2. 6 パターン和に関する制約
興味深いパターン和の発見にあたり，Shima [4] らはデータ

1 <
= i <
= k − 1 に対して X[i] = Y [i] かつ X[k] <Σ Y [k] が成立するとき．
本稿では，正規形の飽和パターン全体の族 Cˆ に対する全順序いる．

を必要とする．しかし，単なる正規形アイテム集合の辞書式順|Occ(P )| = |Occ(X1 ) ∪ ... ∪ Occ(Xk )| >= θ.

序は，飽和アイテム集合の列挙との整合性がつかないので，われわれの目的には適さない．そこで，そのような全順序として，

2. 3 節の LCM アルゴリズムの探索過程を用いて，次の LCM 順

ベース T 上のパターン P についていくつかの制約を与えて••パターン和 P が全体 θ-頻出である ⇐⇒パターン和 P が局所 σ-頻出である ⇐⇒|Occ(Xi )| >= σ, ∀i = 1, ..., k.
•

パターン和 P が γ-重複である ⇐⇒|Occ(Xi ) ∩ Occ(Xj )| <| j.
= γ, ∀i, j = 1, ..., k, i =序 <LCM を定める．
［定義 1］（LCM 順序） LCM 順序とは，次をみたす Cˆ 上の二
項関係 <LCM である：任意の飽和アイテム集合 X, Y ∈ C に対して，X <LCM Y であることを，LCM アルゴリズムの探索木に•

パターン和 P が α-弁別である ⇐⇒ 指定されたスコア

関数について，P の分類スコアが α 以上である．

2. 7 頻出パターン和マイニング

おける頂点の前順巡回（pre-order traversal）において，X が頻出パターン和マイニングは，データベース T，パターン和

Y より先に出現することと定義する．定義より，LCM 順 <LCM
は Cˆ 上の全順序をなす．

のパラメータ Θ = {K, θ, σ, γ, ...} を入力として受け取り，デー

2. 5 パターン和の族

和を全て発見するアルゴリズムである．

P を任意のパターンの族とする．P 上のサイズ k のパターン
和 (disjunctive pattern) とは，

P = X1 ∨ . . . ∨ Xk

タベース T 上に出現し，与えられた制約を満たす K-パターン(3)

3. 飽和パターン和の等価性
パターン和はデータベース上での二値特徴に対応する．このとき，同じ二値特徴を与えるような等価なパターン和が複数発である．ここで，X1 , ..., Xk ∈ P は P 上の任意のパターンであ見されることは冗長であり，回避することが望ましい．以下でり，要素パターンと呼ばれる．|P | = k で P のサイズを表し，は，そのような冗長性をパターン和の等価性として定式化し，対応する正規形を与える．

（注 1）：厳密に言えば正規形 X̂ はアイテムの列であり，集合ではないが，簡便の3. 1 タイプ 1：順序の異なるパターン和

ため集合と同一視して，i ∈ X̂ のように書くことがある．

論理和 ∨ は可換であるため，パターン和に含まれるパターン—3—3. 2 タイプ 2：パターンとそれに内包されるパターンの和
パターン和 P に，互いに集合の包含関係 X ⊂=Y を満たすよ
うな異なるパターン X と Y が含まれる場合，Y の出現集合
occ(Y )⊂
=occ(X) であるため，Y を除外してもパターン和の出現は等価となる．これを次のように定式化する．
パターン和 P が非冗長（irredundant）であるとは，P が冗長な要素パターンを含まないことをいう．ここに，X が冗長とは，ある異なる要素パターン Y ∈ P (X ̸= Y ) に対して，Y ⊂=Xが成立することをいう．
［定義 4］（タイプ 2 の正規形） パターン和 P = X1 ∨ · · · ∨ Xk
がタイプ 2 の正規形であるとは，次の条件が成立することと定
める：(i) P はタイプ 1 の正規形である．
図2(ii) P は非冗長である．

タイプ 1,2,3 の等価性

任意の非正規なパターン和 P から，P が冗長な要素パターが同一であれば，結合順序が変わっても出現リストは同一となる．したがって，あるパターン和 P について，和として含まれる個々のパターンの順序を入れ替えることで，K! 個の等価なパターンを作ることができる．これを定式化して，次の定義をン Y ∈ P を含む限り，それを取り除くことを繰り返すことで，タイプ 2 の正規なパターン和を得ることができる（注 3）．これをP̂ [2] で表す．タイプ 2 の正規形に関する等価性を次のように与えておく．
［定義 5］（タイプ 2 の等価性） パターン和 P と Q がタイプ 2

与える．
［定義 2］（タイプ 1 の等価性） パターン和 P = X1 ∨ ... ∨ Xkと Q = Y1 ∨ ... ∨ Ym (k, m >= 0) がタイプ 1 の等価性を持つことを P ≡1 Q と書き，次の条件が成立することと定める：の等価性を持つことを P ≡2 Q と書き，次の条件が成立することと定める：

P̂ [2] = Q̂[2] .

(i) k = m．
(ii) ある置換 π : {1, . . . , k} → {1, . . . , k} が存在して，任意の 1 <=i<= k に対して Xi = Yπ(i) ．
タイプ 1 の等価性については，パターン間に辞書式の順序を指定し，パターン和を必ずパターンの降順の結合に制限することで回避することができる．この考えに基づき，次のようにタ
イプ 1 の正規形を定める．
［定義 3］（タイプ 1 の正規形） パターン和 P = X1 ∨ · · · ∨ Xk
がタイプ 1 の正規形であるとは，次の条件 (i) と (ii) が成立することをいう：(6)

3. 3 タイプ 3：要素パターンの出現同値性に基づく等価性
2. 2 節で，二つのアイテム集合 X と Y ∈ P が T 上で等価であることを X ≡T Y ⇐⇒ O(X, T ) = Occ(Y, T ) と定義した．
これより，アイテム集合和が含む要素パターンを出現等価なパターンで置き換えることで，等価なパタン和が得られる．これにより，最悪時には指数個の等価なパターン和が存在し得ることがわかる．これを定式化して，次の定義を与える．
［定義 6］（タイプ 3 の等価性） パターン和 P = X1 ∨ ... ∨ Xkと Q = Y1 ∨ ... ∨ Ym (k, m >= 0) がタイプ 3 の等価性を持つことを次の条件が成立することと定め，P ≡3′ Q と書く：

(i) 任意の 1 <=i<= k に対して Xi は正規形である．

(i) k = m．

(ii) X1 <lex · · · <lex Xk が成立する．
正規形のパターン和を，P のタイプ 1 の正規形と呼び，P̂で表す．（注 2） それがあきらかであれば，以下では，辞書式順序<lex の代わりに，アイテム集合族上の任意の全順序 < を用いた場合も，タイプ 1 の正規形と呼ぶ．

(ii) ある置換 π : {1, . . . , k} → {1, . . . , k} が存在して，任意の 1 <=i<= k に対して Occ(Xi , T ) = Occ(Yπ(i) , T )．
タイプ 3 の等価性に関して，次のように正規形を与える．2. 4
節で導入したデータベース T 上の LCM 順序を <LCM とおく．
［定義 7］（タイプ 3 の正規形） 正規形の飽和パターン上の全次の補題は，ここで導入したタイプ 1 の正規形が正しい代表
元になることをいう．
［補題 1］ タイプ 1 の正規形は，タイプ 1 の等価性の同値類に対する代表元を与える．

順序 <C が与えられたと仮定する．このとき，パターン和P = X1 ∨ · · · ∨ Xk がタイプ 3 の正規形であるとは，次の条件が成立することと定める：(i) 任意の 1 <= k に対して Xi ∈ C は，T 上の正規形=i<（証明） アイテム集合の族に対して，その正規形は一意であの飽和アイテム集合である．

る．辞書順 <lex は，アイテム集合の族に対する全順序なので，(ii) X1 <LCM · · · <LCM Xk が成立する．すなわち，P のタイプ 1 で等価な，すなわち並べ替えで同一となるアイテム集

要素は，飽和アイテム集合の LCM 順序の昇順で左から右に整合和の同値類に対して，ただ一つ決まるので示された．

□

列されている．
（注 3）：実際，タイプ 2 の正規形は，半順序集合 (P, ⊂=) の極小元の集合として（注 2）：以後，タイプを明示する必要があるときには，P̂ [1] のように書く．

定まり，上記の手続きはこれを求めることが言える．

—4—

Algorithm 2 頻出パターン和（CD）の素朴なマイニングア

く定義されているならば，等価性の意味で同じパターンを 2 度

ルゴリズム．データベース T 上の M 個以下の σ 頻出集合から以上出すことはないことに注意されたい．

なるタイプ 4 のパターン和全てを，入力の指数領域を用いて列ズムの構築方法として，次のような方法が提案されている [2,4]．

挙する．

•

1: procedure NaiveCDM(n, M , T , σ)2:F := LCM(, 0, n, T, σ);

3:

RecNaiveCDM(∅, 0; |F|, M, F);▷ σ 頻出パターン全体 F (T, σ)

if P が冗長である then

▷ 非冗長性は半単調な性質

8:

列挙を行い，全体 θ-頻出性と γ-重複性の検索を行って，検査をアルゴリズムを与える．このアルゴリズムは，入力データベー
スから初めに全ての頻出パターンの集合を求めておき，それら

for each i := k + 1, . . . , N do

10:

このパターン番号を新たなアイテムとみなして部分集合

Algorithm 2 に，タイプ 4 のパターン和の素朴なマイニング▷ 親へバックトラックする

return ;9:•

パスしたもののみを出力する．

P を解として出力する．
if |P | >= M then7:

次にこれらの要素パターン全てを辞書順で昇順に整列して，パターン番号付けをする．

▷ 親へバックトラックする

return ;6:

既存のアルゴリズムを用いて，局所 σ-頻出なそのタイプの要素パターンをすべて列挙してメモリに格納しておく．

•

4: procedure RecNaiveCDM(P, k; N, M, F)
5:

タイプ α のパターン和マイニングに対する基本的なアルゴリ

11:

Y := F [i];12:RecNaiveCDM(P ∪ {Y }, i; N, M, F)▷ 第 i 番目のパターン

を新しいアイテムとみなして，M パターン和を列挙する．
しかし，この素朴なアルゴリズムは，前処理で LCM を用いて計算したパターン全てをメモリに格納するので，データベー

3. 4 タイプ 4：複合的な等価性

スがメモリに収まる場合でも，列挙する局所頻出パターン全て

今までに定義したタイプ 1 からタイプ 3 の三つの等価性を合がメモリに収まらない場合は，パターン和マイニングを行えないという問題点をもつ．

わせて，タイプ 4 の等価性を導入する．
［定義 8］（タイプ 4 の等価性） パターン和 P と Q がタイプ 4の等価性をもつとは（P ≡4 Q で表す），P と Q それぞれのタ
イプ 2 の正規形がタイプ 3 の等価性をもつことと定義する．すdef

なわち，P ≡4 Q ⇐⇒ P̂ [2] ≡3 Q̂[2] である．
二項関係の合成演算 ◦ を用いると，≡2 と ≡3 が同値関係で次の節では，小さなメモリ量で効率よく全てのパターン和を列挙するアルゴリズムについて議論する．

4. 飽和パターン和発見の省メモリアルゴリズム
本節では，飽和パターンを要素とする K パターン和を，入あることから，次の補題が成立する．

力サイズの多項式メモリで列挙する省メモリ型マイニングアル［補題 2］ 次の等式が成立する．

ゴリズム CDM を与える．

(≡4 ) = (≡2 ◦ ≡3 ) = · · · = (≡2 ◦ ≡3 )∗= (≡2 ∪ ≡3 )2 = · · · = (≡2 ∪ ≡3 )∗

(7)
(8)

ここに，R∗ は二項関係 R の推移閉包である．
この考えに基づき，次のようにタイプ 4 の正規形を定める．
［補題 3］ 次の包含関係が成立する:

•

⊂
≡1 ⊂
= ≡2 = ≡4

以下では，データベース T と最小頻度パラメータ σ ∈ [0, |T |]に対して，LCM アルゴリズムが飽和集合全体 C を計算する際に，探索する探索木を TLCM で表す．さらに，探索中に生成するアイテム集合の最大サイズ（探索木の高さ）と，最大の子の数（探索木の最大分岐数），最長の出現リストの長さを，それぞれ，h <= |Σ| と，b <= |Σ|，maxocc <= |T | で表す．

4. 1 飽和パターンのイタレータ型列挙• ≡1 ⊂ ≡3 ⊂ ≡4==
［定義 9］（タイプ 4 の正規形） 正規形の飽和パターン上の全子）の実現方法を説明する．

順序 <C が与えられたと仮定する．このとき，パターン和［定義 10］（イタレータ） 対象物の集合 O とその上の全順序 <=P = X1 ∨ · · · ∨ Xk がタイプ 4 の正規形であるとは，次の条件が与えられたとき，(O, <=) に対するイタレータとは，O の要素をが成立することと定める：<= で昇順に整列して得られる要素列 O0 < O1 < · · · < O|O|−1に対して，次をみたす演算を実現するデータ構造 I である．

(i) 任意の 1 <= k に対して Xi ∈ C は，T 上の正規形=i<の飽和パターン（飽和アイテム集合）である．

(ii) P は非冗長である．
(iii) X1 <LCM · · · <LCM Xk が成立する．すなわち，P の本小節では，飽和パターンを列挙するイタレータ（繰り返し•初期化関数 init(Θ): 引数 Θ でデータ構造を初期化する．

•

複製関数 clone(): 現在のデータ構造の複製を返す．

•

後者関数 next(): 演算 init の呼び出し後，最初の呼び要素は，飽和アイテム集合の LCM 順序の昇順で左から右に整出しならば O0 を返す．第 i 番目の呼び出しにおいて，もし列されている．

i < |O| ならば Oi の後者 Oi+1 を返し，i >= |O| ならば，解の3. 5 パターン和マイニング問題

終わりを示す特別な値 EOS を返す．

任意のタイプ α = 1, 2, 3, 4 に対して，タイプ α のパターン

Algorithm 3 と Algorithm 4 に，飽和パターンマイニングア

和マイニング問題とは，データベース T において，全体 θ-頻

ルゴリズム LCM を線形化して得たイタレータ LCMIterator を出かつ，局所 σ-頻出，γ-重複であるようなタイプ α の正規形示す．なおアルゴリズムは，C++や Java などのオブジェクトのパターン和を列挙する問題である．このとき，正規形が正し指向言語のスタイルの擬似言語で記述されており，内部状態を—5—

Algorithm 3 飽和パターンのイタレータ型列挙アルゴリズムを実装したオブジェクトのクラス LCMIterator．クラスの変数と，初期化および複製手続きのみ示す．

••

Occ: X のデータベース中の出現リスト Occ(X, T )⊂=T .
depth: 飽和アイテム集合の探索木における X の深さ

depth >= 0．
こ れ は， 定数 情報 n, T, σ と合わせ て，現 在の 頂点 の子

1: class LCMIterator
2: クラス変数: n, T , σ;

▷ すべてのオブジェクトで共通

Y = X ∪ {i} に対して後で呼び出すべき，再帰的な手続き

3: インスタンス変数: SQStack;▷ オブジェクト毎に異なり得る

呼び出し LCM(Y, i, Occ; n, T, σ) を表す（Algorithm 1 の 11 行

4: procedure init(n0 , T0 , σ0 )5://イタレータ自身を初期化する．

6:(n, T, σ) := (n0 , T0 , σ0 );7:

Q0 := {(∅, −1, T, 0)};8:

SQStack.push(Q0 );▷ 初期状態を含む状態キュー

9: procedure clone()目を参照）．状態キューとは，状態の列を保持するキュー（待ち行列）である．状態キューは，現在の作業頂点における残りの計算を表す．
補足として，ここでは残りの計算を表すのに状態キューを用いているが，バックトラックの基本アルゴリズムのイタレー

10://イタレータ自身の複製を返す．

タ化だけならば，本当は現在呼び出している状態のみを保持

11:

LCMIterator N ewIt := new LCMIterator();すれば良い．しかし，本稿では，あとで LCM が用いている

12:

N ewSQStack := ∅;for each queue ∈ SQStack do

occurrence deliver 手法 [3] を適用するために，子すべての情

13:

N ewSQStack.push(cloneQueue(queue));

14:
15:

N ewIt.SQStack := N ewSQStack;16:

return N ewIt;

17: procedure cloneQueue(Q: 状態キュー)

4. 1. 2 状態の初期化と複製
Algorithm 3 に，イタレータの初期状態を返す手続き init を示す．初期状態は，次の情報を含む状態である．

•

itemset := ∅.

N ewQ := ∅;•tail := −1.

for each state ∈ Q do•

Occ := T .

•depth := 0.

18://副手続き：与えられたキューの複製を返す．

19:
20:

N ewQ.enqueue(cloneState(state));21:

return N ewQ;

22:報を保持するのに状態キューを用いている．

23: procedure cloneState(state: 状態)
24://副手続き：与えられた状態の複製を返す．

25:

N ewOcc := ∅;26:

for each t ∈ Occ do N ewOcc := N ewOcc ∪ {t};27:return (state.itemset, state.tail, N ewOcc, state.depth);

28: end class

イタレータは，この初期状態だけを含んだキューから，計算をスタートする．
同じく，Algorithm 3 に，イタレータの複製演算を実装した
手続き clone を示す．これは，現在の状態がもつ情報をすべて複製したイタレータを返す．ここで，スタックの内容自体の「深い複製」をとっていることに注意されたい．
［補題 4］ Algorithm 3 と Algorithm 4 のイタレータ LCMIt-

erator のデータ構造は，O(h · b · maxocc) = O(|Σ|2 |T |) 領域
もった LCMIterator 型のオブジェクトである．これは，飽和アイテム集合の全体に対するイタレータデータ構造であり，初期化関数 init と後者関数 nextByLCM をもつ．以下に詳しい説明を与える．
イタレータは，Algorithm 1 の LCM アルゴリズムの計算の内部状態を内部に保持し，線形の計算でバックトラックによる飽和パターンの探索を模倣する．

4. 1. 1 状態の表現
まず，次の情報は変化しないので定数として保持する．

で実現できる．
（証明） 一つの状態 state = (X, tail, Occ, depth) がもつ情報
は，出現リスト Occ 以外は定数サイズで表現できる．データ
ベース T は変化しないので，Occ はそのタプルへのポインタのリストを使えば，O(|Occ|) 領域で表せる．構成からイタレータの格納に必要な領域は，それがもつスタック中に含まれるすべてのキューを考えて，それらに含まれる出現リストの長さの総和に等しい．よって導かれた．

□•

n: 最大のアイテム番号．
（Σ = [1, n].）

［補題 5］ Algorithm 3 の手続き clone は，与えられたイタレー•

T : 入力データベース．

タの複製を，O(h · b · maxocc) = O(|Σ|2 |T |) 時間で計算する．

•

σ: 最小頻度パラメータ．

（証明） アルゴリズムの構成から，複製の計算時間は，現在の探索木の現在の頂点を作業頂点と呼び，そこから根までのパ
スを作業パスと呼ぶ．イタレータ It は，再帰手続きの作業頂点における状態を内部に保持する．
初めに，状態は，次の情報をフィールドにもつオブジェクト
である．

•
•

itemset: 現在訪問中のアイテム集合 X ⊂=[1, n].
tail: X 中の最大のアイテム k = max(X) ∈ [−1, n]．もし X = ∅ ならば，tail = −1 とする．

イタレータのデータ構造がもつ領域量に比例する．よって，補題 4 から示された．

□

Algorithm 4 に，イタレータの現在の状態から次の飽和パター
ンを返す後者演算を実現する手続き nextByLCM を示す．この手続きは，Algorithm 1 の LCM アルゴリズムが実行する再帰的な探索計算を，現在のイタレータの状態をもとに，nextbyLCM
手続きの繰り返しによって模倣する．

—6—

Algorithm 4 飽和パターンのイタレータ LCMIterator．現在なる飽和集合はすべて σ-頻出な飽和パターンである．したがっの状態から次の飽和パターンを返す手続き．

て，木 TLCM における X と Y の最近共通先祖 Z を考えると，

1: class LCMIterator

X から Z までのパスと，Z から Y までのパスはすべて解とな

2: クラス変数: n, T , σ;

り，さらに X から Y への訪問の間に，これらのパスから距離

3: インスタンス変数: SQStack;▷ 状態キュースタック

4: procedure nextByLCM()
5:

S = getN extF reqState();6:

if (nextState = EOS ) then return ;7:

SQStack.push();8://アイテム集合 nextState.itemset の拡張を行う．

9:

for i := nextState.tail + 1, . . . , n do

10:

Y = Closure(S.itemset ∪ {i}, T );11:

if X ∩ [1, i − 1] = Y ∩ [1, i − 1] then

▷ 空のキューを状態スタックへ入れる

queue.enqueue((Y, i, S.occ, S.depth + 1));12:

14: procedure getNextFreqState()//探索木上の前順巡回において，現在の状態より後で，σ 以上

15:の頻度をもつ最初の状態をみつける．
16:

while SQStack ̸= ∅ do17:

currentQueue := SQStack.peek(); ▷ 頂上の要素を見る

18:

while currentQueue ̸= ∅ do19:

currentState := currentQueue.dequeue();20:

if tail = −1 thencurrentState.Occ := T ;21:currentState.Occ

23::= updateOcc(currentState.parentOcc, tail);
if |currentState.Occ| < σ then24:

continue;

25:

resultState := currentState;

26:
27:

if resultState = null then
SQStack.pop()

28:
29:

31:

□

4. 2 イタレータを用いた飽和パターン和の列挙
Algorithm 5 に，4. 1 節で導入したイタレータ LCMIteratorを用いた飽和パターン和の列挙アルゴリズム CDM（Closed

Disjunctive Itemsets Miner）を示す．このアルゴリズムは，入力データベースと最小頻度からイタレータのオブジェクトを生
ゴリズムの内部で用いて，与えられた任意の M >= 1 に対して

M -飽和アイテム集合和すべてを列挙する．
パターン和列挙用のバックトラック型アルゴリズムは，LCMIt-

erator を用いた以外は，部分集合列挙のバックトラック型アル
ゴリズムをそのまま用いている．
［定理 1］ 任意の正整数 M と，アイテム全体集合 Σ，データ
ベース T ，正整数 σ ∈ [0, |T |] に対して，Algorithm 5 に示したアルゴリズム CDM は，サイズが高々M のタイプ 4 の飽和

return resultState;
return EOS ;（証明） 部分集合列挙アルゴリズムの正当性と，イタレータ
版の LCM の正当性より，このアルゴリズムが正しくタイプ 4の飽和パターン和を列挙することがいえる．補題 4 から，一つのイタレータは O(|Σ|2 |T |) 領域を要する．CDM の探索全体では，再帰呼び出しの深さは最大 M であり，したがって高々M個のイたレータしか同時には保持されない．したがって，結果が示された．

else

30:

トの最大長の積で抑えられる．よって示された．

パターン和全てを，O(M |Σ|2 |T |) 領域で計算する．

else

22:

る．よって，UpdateOcc は，パス長と，最大分岐数，出現リス成し，次に，これをパターン和列挙用のバックトラック型アルreturn S;

13:

1 のノード，すなわちパスの子，にしか到達しないことが言え▷ 解のストリームの最後を表す特別な状態

32: end class□

解列挙の出力依存計算時間について，アルゴリズム CDM が
出力多項式時間をもつかどうかは不明である．一方で，タイプ3 の飽和集合和の列挙に制限した場合には，次を示すことができる．アルゴリズム CDM をタイプ 3 の列挙に変更するには，基本的な考え方は，深さ優先探索における LCM の内部状態

Algorithm 5 の RecCDM の 6 行目から 7 行目の冗長性チェックと，それに続く計算状態を，状態キューのスタックに保持して，を外せば良い．このとき，次が示せる．

探索を模倣することである．これは，関数型プログラミングに［定理 2］ 任意の正整数 M と，アイテム全体集合 Σ，データおける継続（continuation）の考え方を，バックトラック型の

ベース T ，正整数 σ ∈ [0, |T |] に対して，修正したアルゴリズ

深さ優先探索アルゴリズムのイタレータ化に適用したもので

ム CDM は，サイズが高々M のタイプ 3 の飽和パターン和全ある．

てを，O(M |Σ|2 |T |) 領域を用いて，解一個あたり O(|Σ|2 |T |)［補題 6］ Algorithm 4 に示した手続 nextByLCM は，解一個時間で計算する．

あたり O(h · b · maxocc) = O(|Σ|2 |T |) 時間で，後者関数を正（証明） タイプ 3 の飽和集合和への変更において CDM は，イ

しく実装する．

タレータの後者関数 nextByLCM が新しい飽和集合を一つ返す（証明） LCM の探索木 TLCM 上の一つの辺を，親からへまたごとに，必ず飽和パターン和を一つ生成する．したがって，解は子から親へと移動する時間は高々O(bṁaxocc) である．今，一つあたりの後者関数の呼び出し回数は 1 回である．補題 6 か一つ前に出力した飽和集合を X とおき，次に出力する飽和集

ら解一つあたりの計算時間は O(|Σ|2 |T |) 時間であるので，結合を Y とおく．計算時間は X から Y へ到達するまでに実行果が示された．

□

した UpdateOcc の実行時間の総和で支配される．このとき頻度の反単調性から，木 TLCM 上において X および Y の先祖と—7—

Algorithm 5 イタレータを用いた飽和パターン和の列挙アル
LCM

ゴリズム CDM（Closed Disjunction Miner）．アイテム集合がLCMIterΣ = {1, . . . , n} のとき，データベース T 上の M 個の σ 飽和集
1合からなるパターン和を全て列挙する．
1: procedure CDM(n, M , T , σ)2:

LCMIterator It := new LCMIterator(n, T, σ);3:It.init();

4:

RecCDM(∅, It; M );

0.1
10

100

1000

10000

5: procedure RecCDM(P, It; M )
6:
7:
8:
9:
10:
11:

if P が冗長である then

▷ 非冗長性は半単調な性質
図 3 入力サイズに対する総計算時間の比較▷ 親へバックトラックする

return ;P を解として出力する．
if |P | >= M then

オーバーヘッドの評価が必要である．複合特徴発見の視点から▷ 親へバックトラックする

return ;while ((state := It.nextByLCM()) ̸= EOS ) do

12:

(X, tail, Occ, depth) := state;

13:

NewIt := It.clone();14:

RecCDM(P ∪ {X}, NewIt; M )15:free(NewIt);▷ 新しい状態は，本稿で提案した省メモリのパターン和発見法を，パターン
和以外の複合特徴へと一般化することが課題である．例えば，論理積と論理和が混在したブール式や，決定リストなどへの拡張は興味深い．機械学習アルゴリズムの特徴抽出に用いた場合の性能評価も課題である．

謝

5. 実

験

辞

瀬々 潤氏および，津田 宏治氏，寺田 愛花氏，美添 一樹氏にはデータベースからの複合特徴発見とパターン探索について，

予備実験として，4. 1 節で提案した LCMIterator を人工デー

貴重なコメントとご教示をいただきました．ここに謝意を表し

タ上で走らせて計算時間を計測した．データは，FIMI レポジ

ます．本研究の一部は，科研費基盤 (A)24240021 および科研費

トリ（注 4） の T10I4D100K から，最初の 10000 行を切り出した基盤研究 (S)15H05711 による．

もので，異なるアイテム数 867 個，各行は 11.05 アイテム，総サイズ 400,467 バイトであった．
プログラムとして，2. 2 節の LCM（procLCM）と 4. 1 節のLCMIterator（LCMIter）を Java 言語で実装し，全飽和パターンを出力するのに要した時間を time コマンドで実測した．ここで，LCM には Occurrence Deliver 等の最適化手法 [3] を含まない．実行環境として，PC（Intel Corei5 3GHz, 64bit, 8GB,

Mac OSX 10.11.3）と Java HotSpot VM を用いた．
図 3 に入力トランザクションの行数を n = 10, 100, 1000,

10000 と変化させたときの，LCM と LCMIterator の計算時間のグラフを示す．両方のプログラムの計算時間は n のほぼ線形であり，明確な違いは見られないことから，飽和集合生成に関しては LCMIterator は LCM と同程度に高速といえる．

6. お わ り に
本稿では，飽和アイテム集合発見問題を，飽和パターン和のクラスへと拡張し，種々のパターン和の同値性と，それらに関する正規形を与えた．続いて，飽和アイテム集合の列挙アル
ゴリズム LCM をもとに，解集合のイタレータ（繰り返し子）

LCMIterator を与え，これを用いて，頻出飽和パターン和を発見するメモリ効率の良いアルゴリズム CDM を与えた．
今後の課題として，これをもとにした CDM アルゴリズムの文

献[1] Lizhuang Zhao, Mohammed J Zaki, and Naren Ramakrishnan. Blosom: a framework for mining arbitrary boolean
expressions. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data
mining, pp. 827–832. ACM, 2006.
[2] Yoshikazu Shima, Kouichi Hirata, and Masateru Harao. Extraction of frequent few-overlapped monotone dnf formulaswith depth-first pruning. In Proceedings of the 9th PacificAsia Conference on Advances in Knowledge Discovery andData Mining (PAKDD 2005), Vol. 3518 of Lecture Notes in
Computer Science, pp. 50–60. Springer, 2005.
[3] Takeaki Uno, Masashi Kiyomi, and Hiroki Arimura. LCM
ver. 2: Eﬃcient Mining Algorithms for Frequent / Closed /Maximal Itemsets. Workshop on Frequent Itemset Mining,
2004.
[4] Yoshikazu Shima, Shinji Mitsuishi, Kouichi Hirata, andMasateru Harao. Extracting minimal and closed monotone
dnf formulas. Discovery Science, 2004.
[5] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. Proceeding VLDB ’94
Proceedings of the 20th International Conference on Very
Large Data Bases, Vol. 1215, pp. 487–499, 1994.
[6] Roberto J Bayardo Jr. Eﬃciently Mining Long Patterns
from Databases. Proceedings of the 1998 ACM SIGMODInternational Conference on Management of Data, pp. 85–
93, 1998.

実装と評価があげられる．とくに，イタレータの複製に関わる（注 4）：http://fimi.ua.ac.be/data/—8—