負の相関ルールマイニングの拡張を目的とした一般化アイテム集合とその飽和集合の抽出手法

負の相関ルールマイニングの拡張を目的とした

一般化アイテム集合とその飽和集合の抽出手法

Generalized Itemsets for Extending of Negative Association Rules

and its Fast Extraction Methods of their Closed Itemsets

安藤 祐太

1∗

_{岩沼 宏冶}

2

_{山本 泰生}

2

Yuta Ando

1

_{Koji Iwanuma}

2

_{Yoshitaka Yamamoto}

2

1

_{山梨大学大学院医工農学総合教育部工学専攻コンピュータ理工学コース}

1

_{Computer Science and Engineering Course, Integrated Graduate School of Medicine}

Engineering and Agricultural Sciences, University of Yamanashi

2

_{山梨大学大学院総合研究部}

2

_{Interdisciplinary Graduate School, University of Yamanashi}

Abstract: In this paper, we consider a generalized itemset which consists of both positive and negative items, in order to extend an expressive power of negative association rules. We study some extraction algorithms of closed generalized itemsets. Especially, we give a theorem for separating the closed positive itemset from a closed generalized itemset, and also proposed a incremental algorithm for enumerating closed generalized itemsets based on the separation theorem. Finally, we show some experimental results of evaluating several extraction algorithms.

1

はじめに

相関ルールとはデータベース中で事象の集合 X と Y の共起関係を表現したものである. 正の相関ルール X ⇒ Y とは, X が生起したときに Y が頻繁に共起する ことを表す表現である. これに対して, 負の相関ルール とはある事象が生起した際に, 別のある事象が生起しな いような負の共起現象を表すルールである [1][2]. 負の相 関ルールで扱う負のアイテム集合_{¬X = ¬{a}1,· · · , an} には否定積形_{¬a1∧· · ·∧¬an}と否定和形_{¬a1∨· · ·∨¬an} という２つの解釈が存在する [3]. ここで¬a は a が発 生しないことを表す負のアイテムである. 否定積形の 負のアイテム集合では, 正と負のアイテムが混在する 事象を (¬X) ∪ Y のように表現できるが, 可能なルール の数が膨大になる. そのため, 近年の研究では, 可能な 負の相関ルールの数が大幅に少ない否定和形の負のア イテム集合を扱うものが多い [1][3]. また, 否定積形の 負のアイテム集合を扱う研究は過去にも行われていた が, 定義が複数あり, 曖昧で決定的なものが存在しない [4][5]. 本研究では, 負の相関ルールを拡張するために, 負アイテム集合の概念を拡張・整理し一般化する. ま た, 一般化アイテム集合の飽和圧縮について考察し, そ の飽和集合の抽出手法を提案する. ∗_{連絡先：山梨大学大学院工学専攻コンピュータ理工学コース}       〒 400-8510 山梨県甲府市武田 4-3-11        E-mail: [email protected] 以下，第 2 章は準備である．第 3 章では，まず一般 化アイテム集合を定義し, 一般化アイテム集合の圧縮に 関する飽和集合について考察する. 第 4 章では一般化 アイテム集合の飽和集合の抽出手法を提案する．第 5 章では提案手法の評価実験を行う．第 6 章はまとめで ある．

2

準備

2.1

正の相関ルール

I = {i1, i2,· · · , in} をアイテムの全体集合とし, ア イテムの集合 X ⊆ I を正のアイテム集合と呼ぶ. ま たトランザクション t をアイテムの集合 t ⊆ I と定め る. トランザクションデータベース T D をトランザク ションの多重集合とする. X をアイテム集合とすると き, X ⊆ t となる T D 中のトランザクション t を出現 と呼び, その集合を T D(X) = {ti∈ T D | X ⊆ ti} と 表記する. 多重集合 A の大きさを|A| と表記するとき, |T D(X)| を T D 中の X の出現頻度と呼ぶ. T D 中の X の支持度 sup(X) を sup(X) = |T D(X)|_{|T D|} と定義する. 最小支持度 ms はユーザが与える支持度の閾値である. sup(X)≥ ms を満たす X を頻出な正のアイテム集合 と呼ぶ. 正の相関ルールとは, X∩ Y = ∅ である正のア イテム集合 X, Y における X ⇒ Y なる形式の表現で ある. 人工知能学会研究会資料 SIG-FPAI-B802-04

正の相関ルールの抽出数を抑える圧縮表現として, 飽 和アイテム集合 [6](以後, 飽和集合と略) が存在する. ア イテム集合 X が正の飽和集合であるとは, X ⊊ X′_, sup(X) = sup(X′) を満たす正のアイテム集合 X′が存 在しない場合をいう.

2.2

負のアイテム, 集合, ルール

負のアイテム集合には否定積形と否定和形の２つの 解釈が存在する. 否定積形では集合の各要素に否定が かかり, ¬{a, b} を (¬a ∧ ¬b) と解釈する. 一方, 否定

和形では_{¬{a, b} を ¬(a ∧ b) = ¬a ∨ ¬b と解釈し. 集} 合全体に否定がかかる. 本論文では否定積形の負のア イテム集合を扱う. X = {a1, a2,· · · , am} とすると き,¬X = {¬a1,¬a2,· · · , ¬am} を負のアイテム集合と 定める. X を¬X の基底と呼び, B(¬X) と表記する. ¬a は a が出現しない事象を表す負のアイテムであり, ¬X = ¬a1∧ ¬a2∧ · · · ∧ ¬amと解釈する. 負の相関 ルールは, アイテム集合の出現と非出現の関係を表し, ¬X ⇒ Y や Y ⇒ ¬X のような形式のルールである.

3

アイテム集合の概念の拡張

本章では, アイテム集合を拡張し, 正負のアイテムの 混在を許す一般化アイテム集合について考察する.

3.1

一般化アイテム集合

X, Y を X∩ Y = ∅ である正のアイテム集合とする. 一般化アイテム集合 bZ を正と負のアイテムからなる集合 b Z = X∪¬Y と定義する. 定義より, 必ず X ∩B(¬Y ) = ∅ となる. 一般化アイテム集合 bZ が出現するデータベー ス中のトランザクションの集合 T D(X∪ ¬Y ) を以下の ように定義する.

T D(X∪¬Y )={ti∈T D(X) | ∀yj∈B(¬Y )[yj∈/ti]} |T D( bZ)| を T D 中の bZ の出現頻度と呼ぶ. T D 中の 一般化アイテム集合 bZ の支持度 sup( bZ) を sup( bZ) = |T D( bZ)| |T D| と定義する. sup( bZ)≥ ms を満たす bZ を頻出 な一般化アイテム集合と呼ぶ. 一般化アイテム集合を bZ = X∪ Y, cZ′= X′∪ Y′と したとき, 一般化アイテム集合の包含関係 bZ ⊆ cZ′を以 下の条件を満たす場合と定める. X ⊆ X′, Y ⊆ Y′ 補題 1 (一般化アイテム集合の支持度の逆単調性) 一般化アイテム集合を bZ1, bZ2としたとき, bZ1⊆ bZ2なら ば sup( bZ1)≥ sup( bZ2) となる 証明 容易なので省略 ₂ 補題 1 より, 支持度の逆単調性による一般化アイテム 集合の探索空間の枝刈りが可能となる. アイテムの種類数を d としたとき, 正のアイテム集合 の束空間の大きさは 2d_{だが, 一般化アイテム集合の探} 索空間の大きさは 3d_{に膨れ上がる. d の値は, 実問題} において最低でも 100 以上となるため, 一般化アイテ ム集合を全て扱うことは困難である. そのため一般化 アイテム集合に対する制約を考えて抽出数を抑制する. 頻出アイテム集合マイニングでは高頻度なアイテム に重きを置いているため, 低頻度なアイテムの情報は あまり重要ではない. そのため低頻度なアイテムの否 定形を考える必要性は低い. また, 小売店の購買履歴で は購入されたもの, 即ち正のアイテムが必ず記録され ていて, 未購入のもの, 即ち負のアイテムだけの一般化 アイテム集合は購買履歴には存在しない. このように 負のアイテムだけの一般化アイテム集合は, 正の事象 を全く持たないので, 実問題ではほとんど出現しない. 以上の理由から以下の 2 つを制約として定める. • 負のアイテム ¬bjの基底 bjは正の頻出アイテム に限定 • 正のアイテムを 1 つ以上含むものに限定 制約条件を定めることで抽出する一般化アイテム集 合を限定できるが, その数を抑制するには不十分であ る. 制約条件とは別に, 一般化アイテム集合を圧縮する 手法を考える必要がある.

3.2

一般化アイテム集合の

飽和集合に基づく圧縮

一般化アイテム集合では, 負のアイテムを正のアイテ ムのように扱う. そのため, 飽和集合による一般化アイ テム集合の圧縮も可能と考えられる. 一般化アイテム集合 bZ が飽和しているとは, 以下の 条件を満たす一般化アイテム集合 cZ′が存在しない場合 をいう. b Z ⊆ cZ′, bZ ̸= cZ′, sup( bZ) = sup(cZ′) 飽和性による一般化アイテム集合の圧縮性能を確認 するために, 予備実験として 4 章で述べる手法を用いて 宇野らの LCM[7] で一般化飽和集合の抽出を行う. 予 備実験で用いたデータセットは FIMD Repository[8] の mushroom と retail の 2 つである. mushroom は稠密 なデータセット, retail は疎なデータセットである. 各 データセットの詳細を表 1 に示す. Item はアイテム総 数, TD はトランザクション総数, ave-Item は各トラン ザクションに出現するアイテム総数の平均を表してい る. 予備実験の結果を表 2 に示す. 一般化アイテム集合 には前述の 2 つの制約を課している. PFI, PCI, GFI, GCI はそれぞれ正の頻出アイテム集合, 正の飽和集合,

頻出一般化アイテム集合, 一般化飽和集合の抽出数で ある. 予備実験の結果より, 飽和集合を用いることで頻出一 般化アイテム集合の数が mushroom では約 16%以下に 圧縮されている. ms = 0.25 では頻出一般化アイテム 集合は 0.1%以下に圧縮されていて, ms を下げるほど 圧縮効果が顕著になる. 飽和集合による一般化アイテ ム集合の圧縮が効果的であることが確認できる. 一方, retail では頻出一般化アイテム集合と一般化飽和集合の 数がほどんど変動せず, 圧縮できていない. 一般に疎な データでは, アイテム集合に負のアイテムを逐次加え ても, 頻度が等しい場合はほとんど存在せず, 頻度が下 がる. そのため, 頻出一般化アイテム集合のほとんどが 一般化飽和集合となり, 圧縮できない. 疎なデータセッ トでは正のアイテムの出現頻度は低く, 負のアイテム の出現頻度は高い. 飽和性による圧縮は出現するアイ テムの密度が高いほど有効であることが知られている ので, 疎なデータで一般化アイテム集合を扱う際には, 負のアイテム集合の部分を圧縮できると予想していた. 予備実験の結果からは, 負のアイテム集合部分での飽和 圧縮も殆ど効果がないことが判明した. よって以下で は稠密なデータ上での一般化飽和集合の抽出に重点を 置いて考察する. 表 1: 使用するデータセットの概要 ID データセット Item TD ave-Item #1 mushroom 119 8,124 23.0 #2 retail 16,470 88,162 10.3 表 2: 予備実験の結果

ID ms PFI PCI GFI GCI

0.4 566 141 1371 216 #1 0.35 1190 261 4700 473 0.3 2736 428 51,120 1,332 0.25 5,546 689 3,097,682 10,774 0.2 53,584 1,198 841,737,709 198,321 0.019 63 63 20,925,772 20,469,793 #2 0.018 66 66 43,428,493 42,341,447 0.017 69 69 45,669,501 44,318,702 0.016 77 77 724,527,873 700,993,462

4

一般化飽和集合の抽出手法

一般化飽和集合を抽出する単純な手段として, データ ベース中の各トランザクションに負のアイテムを明示 的に加えることで, 正の飽和集合抽出手法で一般化アイ テム集合を扱うことが可能となる. しかし, この方法で は平均トランザクション長が頻出アイテムの総数とな りトランザクションが巨大化するため, 実行時間が大幅 にかかると予想される. 本章では一般化飽和集合の抽 出法として, 正の飽和集合を負のアイテムで拡張する手 法を提案する. 一般化飽和集合から負のアイテムを全て除いた正の アイテム集合は必ず飽和集合となることを証明する. 今 回の証明は一般化アイテム集合に正のアイテム集合が 含まれていることを前提とし, 正のアイテム集合 X =∅ のときは考慮しないものとする. 定理 1 (一般化飽和集合の正負分離定理) 一般化アイテム集合 bZ = X∪ ¬Y が一般化飽和集合で あるとき, 部分集合 X は正の飽和集合である. 証明 正のアイテム集合 X が飽和集合でないと仮定す る. この場合, X ⊊ X′_{, sup(X) = sup(X}′_{) となる} 正のアイテム集合 X′が存在し, T D(X′) = T D(X) と なる. 一般化アイテム集合に対する T D の定義より, T D(X∪ ¬Y ) = T D(X′∪ ¬Y ) となるので, sup(X ∪ ¬Y ) = sup(X′_{∪ ¬Y ) となる. 仮定より X ⊊ X}′_であ るので, (X∪ ¬Y ) ⊊ (X′_{∪ ¬Y ) となり, bZ = X∪ ¬Y} が一般化飽和集合であることに矛盾する. よって, X は 正の飽和集合である. 以上から定理 1 が証明された. 2 一般化飽和集合の正負分離定理より, 正の飽和集合 に適当な負のアイテム集合を追加することで, 全ての 一般化飽和集合が構成できることが分かる. そこで正 負分離定理を利用する負アイテム逐次加算法を考察す る. この手法は正の飽和集合抽出アルゴリズムにより, 正の飽和集合が抽出済みであることを前提とする.

4.1

負アイテム逐次加算法

正の飽和集合に負のアイテムを逐次的に加えること で一般化飽和集合の抽出を行う. 一般化アイテム集合 を考える際に, 辞書式順序木を探索する. 辞書式順序木 を扱うことで加える負のアイテムの順序が固定される ため, 全ての一般化飽和集合へのパスの存在とその一意 性が保証される. 図 1 は負アイテム逐次加算法の概念 図である. 各¬bjは負のアイテムであり, 一般化飽和集 合は灰色の背景で表している. 図 1 のように正の飽和 集合に既定の順序で負のアイテムを加えて, 一般化飽和 集合を網羅する. 本手法では, 垂直配置形式で各アイテ ムの出現トランザクション集合を保持する. 䠖 ṇ䛾㣬࿴㞟ྜ ୍⯡໬㣬࿴㞟ྜ 図 1: 負アイテム逐次加算法の基本方針

効率的に一般化飽和集合を探索するために飽和性に 基づく枝刈りを行う. 辞書式順序木では, アイテムの 順序が固定されているため, 各頂点の子頂点のアイテ ム集合と弟頂点のアイテム集合は等しい. そのため弟 頂点は必ず自身の子頂点となる. 頂点 P¬b1の出現ト ランザクション集合 T D(P¬b1) がその弟頂点 P¬b2の 出現トランザクション集合 T D(P¬b2) を含む場合, 必 ず P¬b1の子頂点 P¬b1¬b2の出現トランザクション 集合 T D(P¬b1¬b2) は T D(P¬b2) と等しくなる. 図 2 は頂点 a¬b に着目した例である. 図中の中括弧はその 頂点が持つ出現トランザクション集合を表す. 図 2 で は a¬b の出現トランザクション集合 {2, 4, 5} は a ¬c の持つ出現トランザクション集合_{{4, 5} を含む. a ¬b} の子頂点と弟頂点を比較すると, a¬b ¬c は a ¬c を真に 含み, かつ出現トランザクション集合が等しい. 同様に a¬b ¬c ¬d は a ¬c ¬d を真に含み, かつ出現トランザク ション集合が等しい. よって, 定義より, a¬c と a ¬c ¬d は一般化飽和集合ではないので, a¬c の頂点を枝刈り できる. ᆶ┤㓄⨨ 䜰䜲䝔䝮 d/䝸䝇䝖 㻝 㻞㻌㻟㻠㻌㻡 㻝㻞㻟㻌㻌㻌 㻝㻌㻞 㻝㻞㻌㻟㻠 ฟ⌧䝖䝷䞁䝄䜽䝅䝵䞁㞟ྜ 図 2: 飽和性に基づく枝刈り また, 特殊な枝刈りとして, 頂点 P¬b1の出現トラン ザクション集合 T D(P¬b1) がその親頂点 P の出現ト ランザクション集合 T D(P ) と等しい場合, 頂点 P¬b1 の出現トランザクション集合は P¬b1の全ての弟頂点 の出現トランザクション集合を含む. そのため, P¬b1 の全ての弟頂点を枝刈りできる. 特殊な枝刈りの例を 図 3 に示す. 図 3 では頂点 a¬b の出現集合と親頂点 a の出現集合が等しい. このとき, a¬b の出現集合 {1, 2, 3, 4} は弟頂点 a ¬c の出現集合 {3, 4} と a ¬d の出 現集合_{{1, 4} を含む. そのため, 各弟頂点に対して必} ず飽和性に基づく枝刈りを行うことができる. ᆶ┤㓄⨨ 䜰䜲䝔䝮 d/䝸䝇䝖 㻝 㻞㻌㻟㻌㻠 㻝㻌㻞 㻝 㻞㻌㻟㻌㻠㻌㻡㻌㻌㻌 㻝㻞㻌㻟㻌 図 3: 飽和性に基づく特殊な枝刈り 負アイテム逐次加算法の擬似コードを Algorithm1 と 2 に示す. まず, 頻出アイテムと正の飽和集合それぞれ の出現トランザクションのリスト (以降, 出現リストと 略) を作成する. 次にトライ木に正の飽和集合を順次格 納していく. 9 行目ではそれぞれの正の飽和集合に対 して, 飽和集合の要素でない頻出アイテムの全てを抽 出し, 新しく加える負アイテムの候補として変数 B に 保持する. 新しく加えるアイテムは辞書順でソートを 行う. Gen gis関数では, 一般化アイテム集合の拡張の 準備をする. アイテム集合 X と B 中のアイテム biの 出現リストから, 新たな一般化アイテム集合 X¬biの 出現リストを求める. このとき, 出現リストは辞書順で ソート済みであることに注意していただきたい. |tmp| は X¬biの出現頻度であり, 出現頻度が ms 以上である 場合のみ出現リストを保持する. 23 行目では, 支持度 の逆単調性に基づく枝刈りを行い, 頻出ではない集合の 生成を防いでいる. 25 行目では, 飽和性による枝刈り を行う. 親の出現リストと等しい場合, 以降の弟頂点は 出現リストを求めることなく, 枝刈りする. Gen bro関 数では, 兄弟頂点が持つ出現リストの包含関係のチェッ クを行う. 41 行目では, 各頂点について自分の兄とな る頂点の中で出現リストが包含関係にあるものが存在 するかチェックする. もし存在するならば, 飽和性に基 づく枝刈りを行う. 枝刈りが行われない場合は, その頂 点が表す一般化アイテム集合をトライ木の頂点として 新しく追加し, 再帰的に計算を続ける. 最終的には全て の一般化飽和集合を格納したトライ木を得ることがで きる. Algorithm 1 一般化飽和集合抽出アルゴリズム Input: トランザクションデータベース T D={t1, t2,· · · , th}, 最小支持度 ms, 正の飽和集合の集合 CP =_{P1, P2,· · · , Pn} 頻出アイテムの集合 F Output: 一般化飽和集合の集合を格納したトライ木 Trie ▷ 正の飽和集合に負のアイテムを順次加えることで, 一般化飽 和集合を抽出する 1: Initialize(Trie) ▷ 一般化飽和集合を格納するトライ木の初期化 2: Initialize(TDlist) ▷ アイテム集合の出現リストを保持する配列の初期化 3: Init TDlist(TDlist) ▷ F 及び CP の各元の出現リストを保持 4: Initialize(CTD) ▷ 出現リストを一時的に保持する配列 CT Dの初期化 5: for each X∈ CP do ▷ 正の飽和集合を Trie に格納 6: X を Trie に追加 7: end for 8: for each X∈ CP do   9: B← F − X ▷ リストの初期化 ▷ X の要素でない頻出アイテムを格納するリスト 10: if B =∅ then 11: do nothing 12: else 13: Sort(B)

14: node←Find(X, Trie)

▷ トライ木中の X が格納されている頂点を返す 15: Gen gis(X, node, Trie, B, TDlist [X])

16: end if

17: end for

Algorithm 2 一般化飽和集合抽出アルゴリズム 2

18: procedure Gen gis(X, node, Trie, B, td)

Input: アイテム集合 X アイテム集合 X を格納している Trie の頂点 node トライ木 Trie 加える負アイテム候補のリスト B =_⟨b1, b2,· · · , bl⟩ ▷ B 中のアイテムは辞書順であると仮定 アイテム集合 X の出現リスト td ▷ 最初の枝刈りを行い, 一般化アイテム集合の拡張の準備をする 19: m← 0 ▷ どこのアイテムまで共通部分を求めたのかを保持 20: for i = 1 to|B| do 21: m← m + 1 22: tmp← td− TDlist[bi] ▷ TDlist [bi] : biの出現リスト 23: if |tmp|_{|T D|} ≥ ms then ▷ 頻出性のチェック 24: CT D[i]← tmp ▷ 出現リストを格納 25: if CT D[i] = td then ▷ 飽和性による弟頂点の枝刈 26: break 27: end if 28: else ▷ 頻出でない場合 29: CT D[i]← NULL 30: B←Remove(B, bi) ▷ 加えても頻出にならないアイテムを除く 31: end if 32: end for

33: Gen bro(X, node, Trie, m, B, CT D)

▷ Gen bro関数で共通部分間の関係をチェックして枝 刈り後, 一般化アイテム集合を拡大する

34: end procedure

35: procedure Gen bro(X, node, Trie, m, B, CTD)

Input: アイテム集合 X アイテム集合 X を格納している Trie の頂点 node トライ木 Trie 最後に共通部分を求めたアイテムの添え字 m 加える負アイテム候補のリスト B =_⟨b1, b2,· · · , bl⟩ ▷ B 中のアイテムは辞書順になっていると仮定 出現リストを保持する配列 CTD ▷ 1≤ j ≤ m の範囲で, CTD[j] = td − TDlist[bj] が成り立っている ▷ 兄弟の出現リストの包含関係をチェックして枝刈りする 36: for j = 1 to m do 37: if CT D[j]̸= NULL then 38: Pr flag← false ▷ 子頂点の枝刈りを行うか判定するフラグを false で初期化 39: if j≥ 2 then 40: for k = 1 to j− 1 do 41: if CT D[k]⊇ CTD[j] then ▷ 飽和性による子頂点の枝刈り 42: Pr flag← true 43: break 44: end if 45: end for 46: end if

47: if Pr flag = false then ▷ 枝刈りしない場合 48: new node← Insert(node, Trie, ¬bj)

▷ node の子頂点として¬bjをトライ木に追 加して一般化アイテム集合を拡大し, 追加 した頂点を返す 49: G← X ◦ ⟨¬bj⟩ ▷ 一般化アイテム集合 50: B←Remove(B, bj) ▷ 加えたアイテムを B から除く 51: Gen gis(G, new node, Trie, B, CT D[j])

▷ 再帰的に子頂点を探索 52: else ▷ 枝刈りする場合, 子頂点は探索しない 53: do nothing 54: end if 55: end if 56: end for 57: end procedure

5

比較実験

本章では, 一般化飽和集合を抽出する効果的な手法 を明らかにするために, 2 つの手法の性能比較実験を行 う. 予備実験の結果から, 疎なデータに対して一般化飽 和集合を求める必要はないと判断し, 比較実験では稠密 なデータセットだけを対象とする. 比較実験には, 稠密 なデータセットである mushroom を用いる. 比較対象の手法を表 3 に示す. 正の飽和集合抽出手 法として宇野らの LCM[7], Borgelt らの IsTa[9] を用い る. LCM は, 小さい正の飽和集合を拡張していくこと で全ての正の飽和集合を網羅する手法である. IsTa は, 各トランザクションの集合積をとることで全ての正の 飽和集合を抽出する手法である. 詳細はそれぞれ文献 [7], [9] を参照いただきたい. データベース拡張型は負 のアイテムで拡張したデータベースを LCM, IsTa に適 用させる手法である. 負アイテム逐次加算法における 前処理とは, LCM, IsTa で正の飽和集合を抽出するこ とを指す. 表 3: 実験の比較対象 特徴 一般化アイテム集合の抽出 データベース拡張型 LCM 適用 IsTa 適用 正負分離型 順次負アイテム 前処理（LCM） 加算法 前処理（IsTa）

5.1

実験結果

比較実験の結果を表 4 に示す. 最小支持度 ms の値を 変化させて一般化飽和集合の抽出を行った. 順次負アイ テム加算法における前処理による実行時間の差は見ら れない. 最も高速な手法はデータベース拡張型 +LCM であると確認できる. 提案手法である順次負アイテム 加算法があまり高速ではないことが確認できる. 表 4: 実行時間の比較 ms データベース拡張型 順次負アイテム加算法 LCM[s] IsTa[s] 前 (LCM)[s] 前 (IsTa)[s] 0.4 0.06 0.07 0.29 0.31 0.35 0.08 0.13 0.45 0.46 0.3 0.09 0.23 1.03 1.04 0.25 0.11 2.04 5.77 5.81 0.2 0.35 102.86 303.68 303.71

5.2

考察

データベース拡張型 +LCM が高速だったのはデータ ベースを拡張する際に正の頻出アイテムの否定形しか 加えないため, 拡張後のデータベースがそれ程巨大にな らず, 実行時間への影響が少ないことが要因である. 各 ms における拡張後のトランザクション長 (出現するア

イテム数) の平均を表 5 に示す. ms を 0.4 から 0.2 に 下げてもデータベースは 1.5 倍しか大きくならない. 拡 張前データベースの平均アイテム長が 23 であるから, ms = 0.2 のときでも, 元のデータベースの 2 倍程度し か拡張されていない. 表 5: 拡張後データベースの平均アイテム長 ms ave-Item 0.4 30.93 0.35 32.76 0.3 35.49 0.25 40.52 0.2 46.73 提案手法である負アイテム逐次加算法において, 前処 理として LCM を用いたときの処理時間の内訳を表 6 に 示す. 表中の” 全体” は全体の処理時間, ” 頻度計算” は 一般化アイテム集合の頻度計算にかかる時間を表し, ” 包含チェック 1” は枝刈りをする際に兄弟頂点間の出現 集合の包含関係チェックにかかる時間, ” 包含チェック 2” は一般化飽和集合として抽出した集合が, 他の飽和 集合の部分集合となるか否かのチェックの時間を表す. ms = 0.25 までは全体の処理時間のうち, 大部分を頻度 計算が占めている. しかし, ms = 0.2 では頻度計算に かかる時間は全体の 2 割程度であり, 包含チェック 2 に 時間がかかっていることが確認できる. 包含チェック 2 では一般化飽和集合の候補に対して頻度別のバケット を作り, チェックの対象を絞り込んでいる. バケットを 作成する例を図 4 に示す. この包含チェック 2 は先の Algorithm1 と 2 には含まれていない. 提案したアルゴ リズムでは全ての一般化飽和集合を抽出できるが, 一般 化飽和集合でない集合も一部抽出してしまうため, 包含 チェック 2 を行う必要が生じた. この問題には, 異なる 正の飽和集合をもととするトライ木に飽和集合が存在 する場合と同じトライ木内に飽和集合が存在する場合 の 2 種類存在する. 表 6: 実行時間の内訳 (負アイテム逐次加算法+LCM) ms 全体 [s] 頻度計算 [s] 包含 包含 チェック 1[s] チェック 2[s] 0.4 0.29 0.092 0.001 0.001 0.35 0.45 0.226 0.003 0.001 0.3 1.03 0.755 0.009 0.012 0.25 5.77 4.493 0.083 0.931 0.2 303.68 46.047 1.154 255.768 図 5 は正の飽和集合 b を拡張する例を表している. 破 線で囲まれた頂点は頻出性及び飽和性の枝刈りを行う. ¬a b と b ¬c ¬d は枝刈りされずに残ってしまう. 提案 アルゴリズムでは残った頂点を一般化飽和集合と誤っ て抽出してしまう. b とは別の正の飽和集合 b c d を拡 張して得られる_{¬a b c d が ¬a b の飽和集合である. ま} た, a b を拡張して得られる a b¬c ¬d が b ¬c ¬d の飽和 集合である. a b と b c d を拡張する例を図 6 に示す.

͙

䛾㢖ᗘ 䛾ሙྜ 䝞䜿䝑䝖䛻㏣ຍ 㢖ᗘู䛾䝞䜿䝑䝖 図 4: 頻度別のバケットの作成 䝕䞊䝍䝧䞊䝇 䜰䜲䝔䝮 d/䝸䝇䝖 㻝 㻞㻌㻟㻌㻠 㻝㻌㻞㻌㻟㻌㻠㻌㻡 㻝㻌㻞㻌㻟㻌㻠㻌㻡 㻝㻞㻌㻟㻌㻠㻌㻡㻌㻌㻌 ᯞส䜚 ᯞส䜚 ୍⯡໬㣬࿴㞟ྜ䛷䛿䛺䛔䛜͕ ᯞส䜚䛥䜜䛺䛔 図 5: 一般化飽和集合とならない例 1 ᯞส䜚 䝕䞊䝍䝧䞊䝇 䜰䜲䝔䝮 d/䝸䝇䝖 㻝 㻞㻌㻟㻌㻠 㻝㻌㻞㻌㻟㻌㻠㻌㻡 㻝㻌㻞㻌㻟㻌㻠㻌㻡 㻝㻞㻌㻟㻌㻠㻌㻡㻌㻌㻌 ϭ ୍⯡໬㣬࿴㞟ྜ 図 6: 一般化飽和集合の例 図 7 は正の飽和集合 a を拡張する場合を表している. 一般化飽和集合は灰色の背景で示している. 破線で囲 まれた頂点は枝刈りされるが, a¬c ¬d は枝刈りされず に残ってしまう. a¬c ¬d を真に含む同頻度の集合は a¬b ¬c ¬d であり, この集合が一般化飽和集合である. これらの問題の解決策として, 水平配置形式のデー タベースを保持しておくことで例 1 の場合は未然に枝 刈りできる. 枝刈りする例を図 8 に示す. b¬c が出現 する TID3 と 4 では b 以外に a が共通して出現してい るため, a b を拡張することで b¬c と出現トランザク ション集合が等しい一般化飽和集合を得られる. よっ て b¬c は一般化飽和集合ではないため, b ¬c の頂点を 枝刈りできる. 例 1 の抽出を防ぐことで, チェックの対 象を例 2 の場合だけに絞り込むことができる. 異なる 正の飽和集合をもととするトライ木をチェックする必 要はなくなる. そのためチェックにかかる時間を大幅に 削減できると予想している. 今後, 実装していく予定で ある.

䝕䞊䝍䝧䞊䝇 䜰䜲䝔䝮 d/䝸䝇䝖 㻝 㻞㻌㻟㻌㻠 㻝㻌㻞 㻝 㻝㻞㻌㻌㻌 ᯞส䜚 ୍⯡໬㣬࿴㞟ྜ䛷䛿䛺䛔䛜͕ ᯞส䜚䛥䜜䛺䛔 図 7: 一般化飽和集合とならない例 2 Ỉᖹ㓄⨨ d/ 䜰䜲䝔䝮㞟ྜ ௨እ䛻 䛜 ඹ㏻䛧䛶ฟ⌧䛧䛶䛔䜛 ᯞส䜚 図 8: 解決策の例

6

まとめ

本研究では, 一般化アイテム集合とその飽和集合につ いて考察し, 一般化アイテム集合の正負分離定理に基づ く飽和集合の抽出手法を提案した. 特に正負アイテム の分離定理を示した. また, 稠密なデータセットにおい て, 飽和性による一般化アイテム集合の圧縮が有効なこ とを確認できた. 疎なデータセットでは, 正のアイテム 集合を扱う場合と同様に飽和性による圧縮の効果が薄 い. 疎なデータセットで一般化アイテム集合を扱うに は, 飽和集合の頻度誤差を許すような近似法を考えてい く必要がある. 提案した負アイテム逐次加算法では一般化飽和集合 でない集合も抽出してしまうため, 実行時間が大幅に遅 くなってしまう. 一般化飽和集合でない集合を抽出し ない工夫をさらに考察し, 実装していくことが今後の課 題である.

謝辞

本研究は一部, ISPS 科学研究費補助金（NO.16K00298） の援助を受けている.

参考文献

[1] Wang, H., Zhang, X. and Chen, G.: Mining a Com-plete Set of Both Positive and Negative Association Rules from Large Databases. Proc. the PAKDD’08, pp.777-784 (2008).

[2] Wu, X., Zhang, C. and Zhang, S.: Efficient Mining of Both Positive and Negative Association Rules. ACM

Trans. on information Systems, Vol.22, No.3,

pp.381-405 (2004).

[3] Cornelis, C., Yan, P., Zhang, X. and Chen, G.: Min-ing Positive and Negative Association Rules from Large Databases. Proc. CIS 2006. Lect. Notes in

Comput. Sci, Vol.4456, pp.613-618 (2006).

[4] Antonie, M.-L., Za¨ıane, O. R.: Mining Positive and Negative Association Rules: An Approach for Con-fined Rules. Proc. 8th Euro. Conf. on Principles

and Practice of Knowledge Discovery in Databases,

pp.27-38 (2004).

[5] Taniar, D., Rahayu, W., Lee, V. and Daly, O.: Ex-ception Rules in Association Rule Mining. Applied

Mathmatics and Computation, Vol.205, pp.735-750

(2008).

[6] Zaki, J., M.: Mining Non-Redundant Association Rules. Data Mining and Knowledge Discovery, Vol. 9, pp.223-248 (2004).

[7] 宇野 毅明,有村 博紀: LCM公開プログラム,

<http://research.nii.ac.jp/ uno/codes-j.htm>

[8] Frequent Itemset Mining Dataset Repository,

<http://fimi.ua.ac.be/>(2018-10-22).

[9] Borgelt, C., Yang, X., Nogales-Cadenas, R., Carmona-Saez, P. and Pascual-Montano, A.: Find-ing Closed Frequent Item Sets by IntersectFind-ing Trans-actions. Proc. 14th Int. Conf. on Extending Database

Technology (EDBT 2011, Uppsala, Sweden),