アイテム集合の和のクラスに対する効率良い代表パターンマイニング

DEIM Forum 2016 P4-2

アイテム集合の和のクラスに対する効率良い代表パターンマイニング

Space Efficient 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,

††

[email protected],

†††

[email protected]

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

マイニング技術が注目されている．膨大な数の類似パターンを回避するために，飽和パターン（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 背 景 近年，大規模データからの知識発見技術が注目されている． 計算技術の進歩に伴い，これまで処理が困難だった規模の巨大 なデータを扱うことが可能となり，また，機械学習やデータマ イニング技術の高度化によって，そこから有用な知見を得る ことができるようになった．知識発見の普及に伴い，扱われる データは多様になり，複雑な現象を予測する技術が求められて いる．同時に，高度な知識発見，統計的に有意なデータマイニ ングや正則化などの技術の提案により，組み合わせパターンを 特徴として用いた高次元データを扱うことも可能になってきた． 以上の背景より，高度な知識発見を行うにあたって，二値デー タベース上の複雑な特徴の発見を行うパターンマイニング技術 が注目されるようになっている． 1. 2 関 連 研 究 関連研究として，2006年にZhaoとZakiはデータベースか ら頻出な（一定の回数以上データに出現する）命題論理式を網 羅的に発見するアルゴリズムを与えている[1]．また，2005年

にShimaと，Hirata，Haraoらは，選言標準形の命題論理式，

すなわち，アイテム集合の和を網羅的に発見するアルゴリズム を与えている [2]．これらの研究に共通した問題点として，膨 大な量の類似したパターンが発見されることがあげられる．従 来のアイテム集合マイニングにおいては，この問題に対して飽 和パターン（closed pattern）とよばれるデータベース中で同 じ出現を持つようなパターンからなる同値類の代表元を見つけ る手法が提案されている．例えば，UnoとKiyomi，Arimura

らのLCMアルゴリズムは，飽和アイテム集合を時間とメモリ の両方で効率よく発見する[3]． 1. 3 本稿の目的 本稿では，頻出アイテム集合マイニングを拡張し，発見する 特徴を複合特徴，すなわちパターンの和として，効率よく頻出 なパターン和を発見するマイニング問題を考察する．パターン 和に対しては，飽和パターンマイニングの場合のような冗長な パターン和列挙を回避するための研究は，まだほとんど行わ れていない．とくに，冗長性の基本となるパターン和の等価性 （どのようなパターンが，見かけは異なっていても「同じパター ン」なのかの定義）に関する厳密な定式化と，それらの定義間 の包含関係については，著者らの知る限りでは未だに研究され ていないのが実情である[1–3]．そこで本稿では，冗長なパター ン和の回避を考慮したパターン和マイニング問題のいくつかの 定式化を与え，関連するパターン和の族とマイニング問題の性 質を調べる． 1. 4 本稿の内容 2節で基本的な定義を導入したあと，3節では，パターンの和 の族を導入する．4節では，頻出アイテム集合発見問題をパター

ンの和のクラスへと拡張する．さらに，冗長なパターン和の列 挙を避けるために，タイプ1からタイプ4までの飽和パターン 和の間の同値性を導入する．まず，演算子の可換性に注目した 等価性を導入する．次に，冗長な要素パターンに関する等価性 を考察する．最後に，要素パターンの出現集合に関する等価性 を導入し，対応する飽和パターン和の正規形を与える．これら をまとめて，従来研究 [2, 4]の定義を一般化する形で，飽和パ ターン和マイニング問題を定式化する．5節では，はじめに飽 和アイテム集合を高速に発見するLCMアルゴリズムをもとに， 解集合のイタレータ（繰り返し子）であるLCMIteratorを構成 する．次に，タイプ4の飽和パターン和のクラスに対して，メ モリ効率の良い列挙アルゴリズムCDM（Closed Disjunctive Itemsets Miner）を与える．最後に，飽和パターン和の効率よ い発見に関する問題点について議論する．5節では，本稿をま とめる．

2.

準

備

本節では，本稿で必要な定義を与える．任意の整数の組i <_{= j} に対して，[i, j]で区間{i, i + 1, . . . , j}を表す． 2. 1 頻出アイテム集合マイニング 頻出アイテム集合マイニングとは，離散的なアイテム集合に よって表現されるトランザクションの連なりであるトランザク ションデータベース中に，一定の閾値を超えて頻出するアイテ ム集合を見つけ出すアルゴリズムのことである． Σ = {1, 2, ..., n}をアイテムの集合とする．ここで，Σ中 のアイテムは，Σ上の自然な全順序として整数の大小関係 i <_=Σ j ⇐⇒ i <_{= j}をとる．以後，アイテムの全順序集合 (Σ, <_=Σ)を考える． このとき，アイテムの集合t⊂₌ΣをΣ上のトランザクションと し，TをΣ上のトランザクションからなるデータベースとする． X⊂ =Σをパターンまたはアイテム集合（itemset）とよび，X⊂=t であるようなT中のトランザクションtを，Xの出現（マッチ） という．T中の出現の集合をOcc(X, T ) ={t|X⊂₌t, t∈ T }と 表記し，X の出現集合とよぶ．出現集合の大きさ|Occ(X, T )| をXの頻度といい，f req(X)と表記する．パターンXに関し て，f req(X) >_{= σ}であるとき，パターンX は頻出であるとい い，頻出の閾値σをサポートとよぶ． 頻出アイテム集合マイニングは，データベースTにおいて， 出現頻度が閾値σを越えるようなパターンを列挙する問題であ る．代表的な手法として，Agrawalらによるアプリオリアルゴ リズム[5]，Bayardoらによるバックトラックアルゴリズム[6] などが存在する． 2. 2 飽和アイテム集合 通常の頻出集合マイニングでは，指定したサポートσについ て，f req(X) >_{= σ}であるような全てのパターンを列挙する．し かし，このようにしてパターンを列挙するとき，非常に多くの 解を処理しなくてはいけない場合があり，こうした際には，冗 長な解を除外するために頻出飽和集合をマイニングするという 方法が用いられる． あるアイテム集合Xについて，Xを真に含み，かつXと頻 Algorithm 1頻出パターンのLCM列挙アルゴリズム．アイ テム集合がΣ ={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); ▷ Occは Y の出現リスト

5: if|Occ| < σ then 6: return ; ▷親へバックトラックする 7: X∪ {i} を解として出力する． 8: for each i := k + 1, . . . , n do 9: Z = Closure(Y∪ {i}); 10: if Y∩ [1, i − 1] = Z ∩ [1, i − 1] then 11: LCM(Z, i, Occ; n, T , σ); 12: procedure UpdateOcc(Occ0, i)

13: //ある X の出現リスト Occ0 から Occ(X∪ {i}, T ) を漸増的 に計算する． 14: return{ t ∈ Occ0 | i ∈ t }; 度が等しいアイテム集合がT 中に存在しないとき，Xを飽和 集合とよぶ．飽和集合は出現頻度が等しい全てのパターンの代 表元となっている．より正確には，飽和集合は次のように定義 されるアイテム集合の同値関係≡T に関する同値類の代表元に なっていることが知られている． X ≡TY ⇐⇒ Occ(X, T ) = Occ(Y, T ). (1) したがって，飽和集合を列挙することで，必要な情報を失うこ となく，算出する解の個数を絞ったマイニングを行うことがで きる． アイテム集合Xについて，Xの閉包(closure)を Closure(X) :=∩Occ(X, T ) =∩{ t ∈ T | X⊂₌t} (2) と定義すると，Closure(X)はX を部分集合として含む飽和集 合となることが知られている[3]．さらに，Xが飽和集合であ ることと，条件Closure(X) = Xが成立することは同値である． 2. 3 LCMアルゴリズム LCMアルゴリズムは，宇野，有村らによって開発された，頻 出飽和アイテム集合を高速に列挙するアルゴリズムである[3]． LCMは，LCMは深さ優先探索に基づくバックトラック型アル ゴリズムであり，飽和集合発見の多くの先行アルゴリズムと同 様に閉包計算に基づく． 通常，閉包計算による飽和アイテム集合の列挙では重複した解 が生成されてしまうが，LCMでは，次のようにプレフィックス保 存飽和拡張という手法を利用することで，頻出飽和集合数に対し て線形の時間計算量での列挙を実現している．飽和集合Xにつ いて，コアアイテムcore(X)を，Closure(X∩{1, ..., j}) = X が成り立つような最小のjと定義する．このとき，あるパター ンY がX のプレフィックス保存飽和拡張(prefix-preserving closure extension, PPC-extension)であるとは，あるアイテム

(i) Y = Closure(X∪ {i})，かつ (ii) X∩ [1, i − 1] = Y ∩ [1, i − 1] であることをいう． 任意の飽和集合Y は，必ず他のある単一の飽和集合X（Y の親と呼ばれる）からプレフィックス保存飽和拡張によって算 出され，さらに，そのようなXは一意であることがいえる[3]． Algorithm 1にLCMアルゴリズムの擬似コードを示す． 2. 4 アイテム集合と飽和アイテム集合の正規形 ここで，以下の議論で用いるパターン（アイテム集合）の族 に対する正規形を定める．アイテムの全順序集合を(Σ, <_=Σ)と おく．Σ上のパターンX⊂₌Σの正規形表現（canonical

repre-sentation）とは，次の(i)と(ii)を満たすようなアイテムの順

序列X = iˆ 1· · · imである： (i) {i1, . . . , im} = X，かつ (ii) i1<_{= . . . <= i}m． すなわち，パターンXの正規形とは，その要素をΣ上の全順 序によって昇順に整列した列をいう（注 1）_{．与えられたパターン} X の正規形は一意である．パターンXの正規形をXˆで表す． 以後，正規形パターン全体の族をPˆで表す．本稿でパターン 和を列挙するときは，その要素パターンは正規形であるものだ けを考える． 次に正規形のパターン上の全順序を導入する．パターンX がパターンY よりも辞書式順序で小さいことを，X <lexY と 書きし，次のいずれかを満たす場合として定義する： (i) XがY の真の接頭辞であるとき． (ii) あ る 1 <_{= k <= min(|X|, |Y |)}が 存 在 し て ，任 意 の 1 <_{= i <= k − 1}に対してX[i] = Y [i]かつX[k] <Σ Y [k]が 成立するとき． 本稿では，正規形の飽和パターン全体の族Cˆに対する全順序 を必要とする．しかし，単なる正規形アイテム集合の辞書式順 序は，飽和アイテム集合の列挙との整合性がつかないので，わ れわれの目的には適さない．そこで，そのような全順序として， 2. 3節のLCMアルゴリズムの探索過程を用いて，次のLCM順 序<LCMを定める． ［定義1］（LCM順序） LCM順序とは，次をみたすCˆ上の二 項関係<LCMである：任意の飽和アイテム集合X, Y ∈ C に対 して，X <LCMY であることを，LCMアルゴリズムの探索木に おける頂点の前順巡回（pre-order traversal）において，Xが Yより先に出現することと定義する．定義より，LCM順<LCM はCˆ上の全順序をなす． 2. 5 パターン和の族 Pを任意のパターンの族とする．P上のサイズkのパターン 和(disjunctive pattern)とは， P = X1∨ . . . ∨ Xk (3) である．ここで，X1, ..., Xk∈ PはP上の任意のパターンであ り，要素パターンと呼ばれる．|P | = kでP のサイズを表し， （注 1）：厳密に言えば正規形 ˆXはアイテムの列であり，集合ではないが，簡便の ため集合と同一視して，i∈ ˆXのように書くことがある． 図 1 パターン和の族 アイテム集合X = XiのP への所属性をX ∈ P で表す．パ ターン和P の出現集合Occ(P, T )を，要素パターンの出現集 合の和

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

で定義する．Pの頻度をf req(P, T ) :=|Occ(P, T )|と定める． 最小サポートσ∈ [0, |T |]に対して，f req(P ) >_{= σ}であるとき， データベースT上でPは頻出である． パターン和Pがあるトランザクションtに出現するとは，あ る1 <_{= i <= k}に対して，t∈ Occ(Xi)をいう．いいかえれば， パターン和Pの特徴関数は，要素パターンの特徴関数の選言 [t∈ P ] := [t ∈ X1]∨ · · · ∨ [t ∈ Xk] (5) として書ける． 2. 6 パターン和に関する制約 興味深いパターン和の発見にあたり，Shima [4]らはデータ ベースT上のパターンPについていくつかの制約を与えて いる． • パターン和Pが全体θ-頻出である ⇐⇒

|Occ(P )| = |Occ(X1)∪ ... ∪ Occ(Xk)| >_{= θ.}

• パターン和Pが局所σ-頻出である ⇐⇒

|Occ(Xi)| >_{= σ, ∀i = 1, ..., k.}

• パターン和Pがγ-重複である ⇐⇒

|Occ(Xi)∩ Occ(Xj)| <_{= γ, ∀i, j = 1, ..., k, i |}= j.

• パターン和Pがα-弁別である ⇐⇒ 指定されたスコア 関数について，Pの分類スコアがα以上である． 2. 7 頻出パターン和マイニング 頻出パターン和マイニングは，データベースT，パターン和 のパラメータΘ ={K, θ, σ, γ, ...}を入力として受け取り，デー タベースT上に出現し，与えられた制約を満たすK-パターン 和を全て発見するアルゴリズムである．

3.

飽和パターン和の等価性

パターン和はデータベース上での二値特徴に対応する．この とき，同じ二値特徴を与えるような等価なパターン和が複数発 見されることは冗長であり，回避することが望ましい．以下で は，そのような冗長性をパターン和の等価性として定式化し， 対応する正規形を与える． 3. 1 タイプ1：順序の異なるパターン和 論理和∨は可換であるため，パターン和に含まれるパターン

図 2 タイプ 1,2,3 の等価性 が同一であれば，結合順序が変わっても出現リストは同一とな る．したがって，あるパターン和Pについて，和として含まれ る個々のパターンの順序を入れ替えることで，K!個の等価な パターンを作ることができる．これを定式化して，次の定義を 与える． ［定義2］（タイプ1の等価性） パターン和P = X1∨ ... ∨ Xk とQ = Y1∨ ... ∨ Ym(k, m >_{= 0)}がタイプ1の等価性を持つこ とをP ≡1Qと書き，次の条件が成立することと定める： (i) k = m． (ii) ある置換π :{1, . . . , k} → {1, . . . , k}が存在して，任 意の1 <_{= i <= k}に対してXi= Yπ(i)． タイプ1の等価性については，パターン間に辞書式の順序を 指定し，パターン和を必ずパターンの降順の結合に制限するこ とで回避することができる．この考えに基づき，次のようにタ イプ1の正規形を定める． ［定義3］（タイプ1の正規形） パターン和P = X1∨ · · · ∨ Xk がタイプ1の正規形であるとは，次の条件(i)と(ii)が成立す ることをいう： (i) 任意の1 <_{= i <= k}に対してXiは正規形である．

(ii) X1<lex· · · <lexXkが成立する．

正規形のパターン和を，P のタイプ1の正規形と呼び，Pˆ で表す．（注 2） それがあきらかであれば，以下では，辞書式順序 <lexの代わりに，アイテム集合族上の任意の全順序<を用い た場合も，タイプ1の正規形と呼ぶ． 次の補題は，ここで導入したタイプ1の正規形が正しい代表 元になることをいう． ［補題1］ タイプ1の正規形は，タイプ1の等価性の同値類に 対する代表元を与える． （証明） アイテム集合の族に対して，その正規形は一意であ る．辞書順<lexは，アイテム集合の族に対する全順序なので， タイプ1で等価な，すなわち並べ替えで同一となるアイテム集 合和の同値類に対して，ただ一つ決まるので示された． □ （注 2）：以後，タイプを明示する必要があるときには， ˆP[1]_{のように書く．} 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の正規形である． (ii) P は非冗長である． 任意の非正規なパターン和Pから，P が冗長な要素パター ンY ∈ P を含む限り，それを取り除くことを繰り返すことで， タイプ2の正規なパターン和を得ることができる（注 3）_．これを ˆ P[2]で表す．タイプ2の正規形に関する等価性を次のように与 えておく． ［定義5］（タイプ2の等価性） パターン和PとQがタイプ2 の等価性を持つことをP≡2Qと書き，次の条件が成立するこ とと定める： ˆ P[2]= ˆQ[2]. (6) 3. 3 タイプ3：要素パターンの出現同値性に基づく等価性 2. 2節で，二つのアイテム集合XとY ∈ PがT上で等価で あることをX ≡TY ⇐⇒ O(X, T ) = Occ(Y, T )と定義した． これより，アイテム集合和が含む要素パターンを出現等価なパ ターンで置き換えることで，等価なパタン和が得られる．これ により，最悪時には指数個の等価なパターン和が存在し得るこ とがわかる．これを定式化して，次の定義を与える． ［定義6］（タイプ3の等価性） パターン和P = X1∨ ... ∨ Xk とQ = Y1∨ ... ∨ Ym(k, m >_{= 0)}がタイプ3の等価性を持つこ とを次の条件が成立することと定め，P≡3′ Qと書く： (i) k = m． (ii) ある置換π :{1, . . . , k} → {1, . . . , k}が存在して，任 意の1 <_{= i <= k}に対してOcc(Xi, T ) = Occ(Yπ(i), T )．

タイプ3の等価性に関して，次のように正規形を与える．2. 4 節で導入したデータベースT 上のLCM順序を<LCMとおく． ［定義7］（タイプ3の正規形） 正規形の飽和パターン上の全 順序<C が与えられたと仮定する．このとき，パターン和 P = X1∨ · · · ∨ Xkがタイプ3の正規形であるとは，次の条件 が成立することと定める： (i) 任意の1 <_{= i <= k}に対してXi∈ Cは，T 上の正規形 の飽和アイテム集合である． (ii) X1<LCM· · · <LCMXkが成立する．すなわち，Pの 要素は，飽和アイテム集合のLCM順序の昇順で左から右に整 列されている． （注 3）：実際，タイプ 2 の正規形は，半順序集合 (P,⊂₌)の極小元の集合として 定まり，上記の手続きはこれを求めることが言える．

Algorithm 2頻出パターン和（CD）の素朴なマイニングア ルゴリズム．データベースT上のM 個以下のσ頻出集合から なるタイプ4のパターン和全てを，入力の指数領域を用いて列 挙する． 1: procedure NaiveCDM(n, M , T , σ) 2: F := LCM(, 0, n, T, σ); ▷ σ頻出パターン全体F(T, σ) 3: RecNaiveCDM(∅, 0; |F|, M, F); 4: procedure RecNaiveCDM(P, k; N, M,F) 5: if P が冗長である then ▷非冗長性は半単調な性質 6: return ; ▷親へバックトラックする 7: P を解として出力する． 8: if|P | >_{= M then} 9: return ; ▷親へバックトラックする 10: for each i := k + 1, . . . , N do 11: Y :=F[i]; ▷第 i 番目のパターン 12: RecNaiveCDM(P∪ {Y }, i; N, M, F) 3. 4 タイプ4：複合的な等価性 今までに定義したタイプ1からタイプ3の三つの等価性を合 わせて，タイプ4の等価性を導入する． ［定義8］（タイプ4の等価性） パターン和PとQがタイプ4 の等価性をもつとは（P ≡4Qで表す），PとQそれぞれのタ イプ2の正規形がタイプ3の等価性をもつことと定義する．す なわち，P ≡4Q def ⇐⇒ ˆP[2]_≡ 3Qˆ[2]である． 二項関係の合成演算◦を用いると，≡2と≡3が同値関係で あることから，次の補題が成立する． ［補題2］ 次の等式が成立する． (≡4) = (≡2◦ ≡3) = · · · = (≡2◦ ≡3)∗ (7) = (≡2∪ ≡3)2 = · · · = (≡2∪ ≡3)∗ (8) ここに，R∗は二項関係Rの推移閉包である． この考えに基づき，次のようにタイプ4の正規形を定める． ［補題3］ 次の包含関係が成立する: • ≡1⊂_{= ≡}2 ⊂_{= ≡}4 • ≡1⊂_{= ≡}3 ⊂_{= ≡}4 ［定義9］（タイプ4の正規形） 正規形の飽和パターン上の全 順序<_C が与えられたと仮定する．このとき，パターン和 P = X1∨ · · · ∨ Xkがタイプ4の正規形であるとは，次の条件 が成立することと定める： (i) 任意の1 <_{= i <= k}に対してXi∈ Cは，T 上の正規形 の飽和パターン（飽和アイテム集合）である． (ii) P は非冗長である． (iii) X1<LCM· · · <LCMXkが成立する．すなわち，Pの 要素は，飽和アイテム集合のLCM順序の昇順で左から右に整 列されている． 3. 5 パターン和マイニング問題 任意のタイプα = 1, 2, 3, 4に対して，タイプαのパターン 和マイニング問題とは，データベースT において，全体θ-頻 出かつ，局所σ-頻出，γ-重複であるようなタイプαの正規形 のパターン和を列挙する問題である．このとき，正規形が正し く定義されているならば，等価性の意味で同じパターンを2度 以上出すことはないことに注意されたい． タイプαのパターン和マイニングに対する基本的なアルゴリ ズムの構築方法として，次のような方法が提案されている[2,4]． • 既存のアルゴリズムを用いて，局所σ-頻出なそのタイプ の要素パターンをすべて列挙してメモリに格納しておく． • 次にこれらの要素パターン全てを辞書順で昇順に整列し て，パターン番号付けをする． • このパターン番号を新たなアイテムとみなして部分集合 列挙を行い，全体θ-頻出性とγ-重複性の検索を行って，検査を パスしたもののみを出力する． Algorithm 2に，タイプ4のパターン和の素朴なマイニング アルゴリズムを与える．このアルゴリズムは，入力データベー スから初めに全ての頻出パターンの集合を求めておき，それら を新しいアイテムとみなして，Mパターン和を列挙する． しかし，この素朴なアルゴリズムは，前処理でLCMを用い て計算したパターン全てをメモリに格納するので，データベー スがメモリに収まる場合でも，列挙する局所頻出パターン全て がメモリに収まらない場合は，パターン和マイニングを行えな いという問題点をもつ． 次の節では，小さなメモリ量で効率よく全てのパターン和を 列挙するアルゴリズムについて議論する．

4.

飽和パターン和発見の省メモリアルゴリズム

本節では，飽和パターンを要素とするKパターン和を，入 力サイズの多項式メモリで列挙する省メモリ型マイニングアル ゴリズムCDMを与える． 以下では，データベースTと最小頻度パラメータσ∈ [0, |T |] に対して，LCMアルゴリズムが飽和集合全体Cを計算する際 に，探索する探索木をTLCMで表す．さらに，探索中に生成す るアイテム集合の最大サイズ（探索木の高さ）と，最大の子の 数（探索木の最大分岐数），最長の出現リストの長さを，それ ぞれ，h <_{= |Σ|}と，b <_{= |Σ|}，maxocc <_{= |T |}で表す． 4. 1 飽和パターンのイタレータ型列挙 本小節では，飽和パターンを列挙するイタレータ（繰り返し 子）の実現方法を説明する． ［定義10］（イタレータ） 対象物の集合Oとその上の全順序<₌ が与えられたとき，(O, <₌₎に対するイタレータとは，Oの要素を < =で昇順に整列して得られる要素列O0< O1<· · · < O_|O|−1 に対して，次をみたす演算を実現するデータ構造Iである． • 初期化関数init(Θ): 引数Θでデータ構造を初期化する． • 複製関数clone(): 現在のデータ構造の複製を返す． • 後者関数next(): 演算initの呼び出し後，最初の呼び 出しならばO0 を返す．第i番目の呼び出しにおいて，もし

i <|O|ならばOiの後者Oi+1を返し，i >_{= |O|}ならば，解の

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

Algorithm 3とAlgorithm 4に，飽和パターンマイニングア ルゴリズムLCMを線形化して得たイタレータLCMIteratorを

示す．なおアルゴリズムは，C++やJavaなどのオブジェクト

Algorithm 3飽和パターンのイタレータ型列挙アルゴリズム を実装したオブジェクトのクラスLCMIterator．クラスの変数 と，初期化および複製手続きのみ示す． 1: class LCMIterator 2: クラス変数: n, T , σ;   ▷すべてのオブジェクトで共通 3: インスタンス変数: SQStack; ▷オブジェクト毎に異なり得る 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();

12: N ewSQStack :=∅;

13: for each queue∈ SQStack do

14: N ewSQStack.push(cloneQueue(queue)); 15: N ewIt.SQStack := N ewSQStack; 16: return N ewIt; 17: procedure cloneQueue(Q: 状態キュー) 18: //副手続き：与えられたキューの複製を返す． 19: N ewQ :=∅;

20: for each state∈ Q do

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

23: procedure cloneState(state: 状態)

24: //副手続き：与えられた状態の複製を返す．

25: N ewOcc :=∅;

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

28: end class もったLCMIterator型のオブジェクトである．これは，飽和ア イテム集合の全体に対するイタレータデータ構造であり，初期 化関数initと後者関数nextByLCMをもつ．以下に詳しい説明 を与える． イタレータは，Algorithm 1のLCMアルゴリズムの計算の 内部状態を内部に保持し，線形の計算でバックトラックによる 飽和パターンの探索を模倣する． 4. 1. 1 状態の表現 まず，次の情報は変化しないので定数として保持する． • n: 最大のアイテム番号．（Σ = [1, n].） • T : 入力データベース． • σ: 最小頻度パラメータ． 探索木の現在の頂点を作業頂点と呼び，そこから根までのパ スを作業パスと呼ぶ．イタレータItは，再帰手続きの作業頂 点における状態を内部に保持する． 初めに，状態は，次の情報をフィールドにもつオブジェクト である． • itemset: 現在訪問中のアイテム集合X⊂ =[1, n]. • tail: X中の最大のアイテムk = max(X)∈ [−1, n]．も しX =∅ならば，tail =−1とする． • Occ: Xのデータベース中の出現リストOcc(X, T )⊂₌T . • depth: 飽和アイテム集合の探索木におけるX の深さ depth >_{= 0}． こ れ は ， 定 数 情 報 n, T, σと 合 わ せ て ，現 在 の 頂 点 の 子 Y = X∪ {i}に対して後で呼び出すべき，再帰的な手続き 呼び出しLCM(Y, i, Occ; n, T, σ)を表す（Algorithm 1の11行 目を参照）．状態キューとは，状態の列を保持するキュー（待 ち行列）である．状態キューは，現在の作業頂点における残り の計算を表す． 補足として，ここでは残りの計算を表すのに状態キューを 用いているが，バックトラックの基本アルゴリズムのイタレー タ化だけならば，本当は現在呼び出している状態のみを保持 すれば良い．しかし，本稿では，あとでLCMが用いている occurrence deliver手法[3]を適用するために，子すべての情 報を保持するのに状態キューを用いている． 4. 1. 2 状態の初期化と複製 Algorithm 3に，イタレータの初期状態を返す手続きinitを 示す．初期状態は，次の情報を含む状態である． • itemset := ∅. • tail := −1. • Occ := T . • depth := 0. イタレータは，この初期状態だけを含んだキューから，計算 をスタートする． 同じく，Algorithm 3に，イタレータの複製演算を実装した 手続きcloneを示す．これは，現在の状態がもつ情報をすべて複 製したイタレータを返す．ここで，スタックの内容自体の「深 い複製」をとっていることに注意されたい．

［補題4］ Algorithm 3とAlgorithm 4のイタレータ LCMIt-eratorのデータ構造は，O(h· b · maxocc) = O(|Σ|2|T |)領域 で実現できる．

（証明） 一つの状態state = (X, tail, Occ, depth)がもつ情報

は，出現リストOcc以外は定数サイズで表現できる．データ ベースT は変化しないので，Occはそのタプルへのポインタの リストを使えば，O(|Occ|)領域で表せる．構成からイタレータ の格納に必要な領域は，それがもつスタック中に含まれるすべ てのキューを考えて，それらに含まれる出現リストの長さの総 和に等しい．よって導かれた． □ ［補題5］ Algorithm 3の手続きcloneは，与えられたイタレー

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

（証明） アルゴリズムの構成から，複製の計算時間は，現在の イタレータのデータ構造がもつ領域量に比例する．よって，補 題4から示された． □ Algorithm 4に，イタレータの現在の状態から次の飽和パター ンを返す後者演算を実現する手続きnextByLCMを示す．この手 続きは，Algorithm 1のLCMアルゴリズムが実行する再帰的 な探索計算を，現在のイタレータの状態をもとに，nextbyLCM 手続きの繰り返しによって模倣する．

Algorithm 4 飽和パターンのイタレータLCMIterator．現在 の状態から次の飽和パターンを返す手続き． 1: class LCMIterator 2: クラス変数: n, T , σ;   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 12: queue.enqueue((Y, i, S.occ, S.depth + 1)); 13: return S; 14: procedure getNextFreqState() 15: //探索木上の前順巡回において，現在の状態より後で，σ 以上 の頻度をもつ最初の状態をみつける． 16: while SQStack̸= ∅ do 17: currentQueue := SQStack.peek(); ▷頂上の要素を見る 18: while currentQueue̸= ∅ do 19: currentState := currentQueue.dequeue(); 20: if tail =−1 then 21: currentState.Occ := T ; 22: else 23: currentState.Occ := updateOcc(currentState.parentOcc, tail); 24: if|currentState.Occ| < σ then 25: continue; 26: resultState := currentState; 27: if resultState = null then 28: SQStack.pop() 29: else 30: return resultState; 31: return EOS ; ▷解のストリームの最後を表す特別な状態 32: end class 基本的な考え方は，深さ優先探索におけるLCMの内部状態 と，それに続く計算状態を，状態キューのスタックに保持して， 探索を模倣することである．これは，関数型プログラミングに おける継続（continuation）の考え方を，バックトラック型の 深さ優先探索アルゴリズムのイタレータ化に適用したもので ある． ［補題6］ Algorithm 4に示した手続nextByLCMは，解一個

あたりO(h· b · maxocc) = O(|Σ|2_{|T |)時間で，後者関数を正}

しく実装する． （証明） LCMの探索木TLCM上の一つの辺を，親からへまた は子から親へと移動する時間は高々O(b ˙maxocc)である．今， 一つ前に出力した飽和集合をX とおき，次に出力する飽和集 合をY とおく．計算時間はXからY へ到達するまでに実行 したUpdateOccの実行時間の総和で支配される．このとき頻 度の反単調性から，木TLCM上においてXおよびY の先祖と なる飽和集合はすべてσ-頻出な飽和パターンである．したがっ て，木TLCMにおけるXとY の最近共通先祖Zを考えると， XからZまでのパスと，ZからY までのパスはすべて解とな り，さらにXからY への訪問の間に，これらのパスから距離 1のノード，すなわちパスの子，にしか到達しないことが言え る．よって，UpdateOccは，パス長と，最大分岐数，出現リス トの最大長の積で抑えられる．よって示された． _□ 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の飽和 パターン和全てを，O(M|Σ|2|T |)領域で計算する． （証明） 部分集合列挙アルゴリズムの正当性と，イタレータ 版のLCMの正当性より，このアルゴリズムが正しくタイプ4 の飽和パターン和を列挙することがいえる．補題4から，一つ のイタレータはO(|Σ|2|T |)領域を要する．CDMの探索全体で は，再帰呼び出しの深さは最大M であり，したがって高々M 個のイたレータしか同時には保持されない．したがって，結果 が示された． _□ 解列挙の出力依存計算時間について，アルゴリズムCDMが 出力多項式時間をもつかどうかは不明である．一方で，タイプ 3の飽和集合和の列挙に制限した場合には，次を示すことがで きる．アルゴリズムCDMをタイプ3の列挙に変更するには， Algorithm 5のRecCDMの6行目から7行目の冗長性チェック を外せば良い．このとき，次が示せる． ［定理2］ 任意の正整数Mと，アイテム全体集合Σ，データ ベースT，正整数σ∈ [0, |T |]に対して，修正したアルゴリズ ムCDMは，サイズが高々M のタイプ3の飽和パターン和全 てを，O(M|Σ|2|T |)領域を用いて，解一個あたりO(|Σ|2|T |) 時間で計算する． （証明） タイプ3の飽和集合和への変更においてCDMは，イ タレータの後者関数nextByLCMが新しい飽和集合を一つ返す ごとに，必ず飽和パターン和を一つ生成する．したがって，解 一つあたりの後者関数の呼び出し回数は1回である．補題6か ら解一つあたりの計算時間はO(|Σ|2|T |)時間であるので，結 果が示された． _□

Algorithm 5イタレータを用いた飽和パターン和の列挙アル ゴリズムCDM（Closed Disjunction Miner）．アイテム集合が

Σ ={1, . . . , n}のとき，データベースT上のM個のσ飽和集 合からなるパターン和を全て列挙する．

1: procedure CDM(n, M , T , σ)

2: LCMIterator It := new LCMIterator(n, T, σ);

3: It.init();

4: RecCDM(∅, It; M);

5: procedure RecCDM(P, It; M )

6: if P が冗長である then ▷非冗長性は半単調な性質

7: return ; ▷親へバックトラックする

8: P を解として出力する．

9: if|P | >_{= M then}

10: return ; ▷親へバックトラックする

11: 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レポジ トリ（注 4） のT10I4D100Kから，最初の10000行を切り出した もので，異なるアイテム数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アルゴリズムの 実装と評価があげられる．とくに，イタレータの複製に関わる （注 4）：http://fimi.ua.ac.be/data/ 0.1 1 10 100 1000 10000 LCM LCMIter 図 3 入力サイズに対する総計算時間の比較 オーバーヘッドの評価が必要である．複合特徴発見の視点から は，本稿で提案した省メモリのパターン和発見法を，パターン 和以外の複合特徴へと一般化することが課題である．例えば， 論理積と論理和が混在したブール式や，決定リストなどへの拡 張は興味深い．機械学習アルゴリズムの特徴抽出に用いた場合 の性能評価も課題である．

謝

辞

瀬々 潤氏および，津田 宏治氏，寺田 愛花氏，美添 一樹氏に はデータベースからの複合特徴発見とパターン探索について， 貴重なコメントとご教示をいただきました．ここに謝意を表し ます．本研究の一部は，科研費基盤(A)24240021および科研費 基盤研究(S)15H05711による． 文 献

[1] Lizhuang Zhao, Mohammed J Zaki, and Naren Ramakrish-nan. Blosom: a framework for mining arbitrary boolean expressions. In Proceedings of the 12th ACM SIGKDD

in-ternational conference on Knowledge discovery and data mining, pp. 827–832. ACM, 2006.

[2] Yoshikazu Shima, Kouichi Hirata, and Masateru Harao. Ex-traction of frequent few-overlapped monotone dnf formulas with depth-first pruning. In Proceedings of the 9th

Pacific-Asia Conference on Advances in Knowledge Discovery and Data 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: Efficient Mining Algorithms for Frequent / Closed / Maximal Itemsets. Workshop on Frequent Itemset Mining, 2004.

[4] Yoshikazu Shima, Shinji Mitsuishi, Kouichi Hirata, and Masateru Harao. Extracting minimal and closed monotone dnf formulas. Discovery Science, 2004.

[5] Rakesh Agrawal and Ramakrishnan Srikant. Fast algo-rithms 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. Efficiently Mining Long Patterns from Databases. Proceedings of the 1998 ACM SIGMOD

International Conference on Management of Data, pp. 85–