トランザクションストリーム上のオンライン型頻出飽和集合マイニング

トランザクションストリーム上のオンライン型

頻出飽和集合マイニング

An Online Frequent Closed Itemset Mining on a Transaction Stream

福田翔士

1∗

_岩沼宏治

2

_山本泰生

2

Fukuda Shoshi

1

_{Iwanuma Koji}

2

_{Yamamoto Yoshitaka}

2

1

_{山梨大学大学院 医学工学総合教育部 コンピュータ・メディア工学専攻}

1

_{Computer Science and Media Engineering, Interdisciplinary Graduate School of Medical and}

Engineering, University of Yamanashi

2

_{山梨大学大学院 医学工学総合研究部 コンピュータ・メディア工学専攻}

2

_{Interdisciplinary Graduate School of Medical and Engineering, University of Yamanashi}

Abstract: In order to avoid a combinatorial explosion in transaction stream pocessing, we propose a new approximation algorithm using the feature of the closed itemsets. The new algo-rithm LC-CloStream is an online frequent closed itemset mining algoalgo-rithm obtained by combining CloStream algorithm and Lossy Counting algorithm. We give some theoretical studies and also show several results of its experimental evaluation.

1

はじめに

ストリームマイニングの代表的なアルゴリズムとし て, Lossy Counting 法 [2] や Sikp LC-SS 法 [3] などが 挙げられる. これらのアルゴリズムはストリームデー タから誤差を許容して頻出アイテム集合を抽出するオ ンライン型の決定性近似アルゴリズムである. しかし, 頻出アイテム集合マイニングでは, アイテムの組み合わ せ爆発のため抽出されるアイテム集合の候補数が非常 に膨大になるという問題がある. そこで本稿では, アイテム集合ではなく, その可逆圧 縮形式である飽和アイテム集合を抽出の対象し, アイテ ムの組み合わせ爆発を抑えること目的とした, オンライ ン型頻出飽和アイテム集合マイニングを提案する.

2

準備

本稿で用いる表記法と用語の定義を以下に示す. 定義 1 アイテムの全体集合を I ={i1, i2,· · · , in} とす るとき, I の部分集合をアイテム集合, もしくはトランザ クションと呼ぶ. トランザクション列⟨T1, T2, . . . , TN⟩ をトランザクションストリームと呼び, N をストリー ム長と定める. 本稿では, 以下, アイテムは英子文字 a, b, c,· · · で表し, また, 簡略化のため, アイテム集合 {i1, i2,· · · , in} を i1i2· · · in と表記する. 定義 2 S =⟨T1, T2, . . . , TN⟩ をストリーム, α をアイ テム集合とするとき, S(α) を{Ti ∈ S|α ⊂ Ti} となる トランザクション集合とする. このとき, アイテム集合 α の S 上の絶対頻度 s(α) を, s(α) =|S(α)| と定め る. また,相対頻度 sR_{(α) を s}R_{(α) =} S(α) N と定める. ∗_{連絡先：山梨大学大学院医学工学総合教育部}       コンピュータ・メディア工学専攻       〒 400-8511 山梨県甲府市武田 4-3-11        E-mail: [email protected] 頻出アイテム集合とは, S において, ユーザが与えた閾 値（以下, 最少頻度と呼ぶ）以上の頻度をもつアイテム 集合と定める. 定義 3 (飽和アイテム集合) アイテム集合 α に対して, α̸= α′ であり α⊂ α′ かつ s(α) = s(α′)であるアイ テム集合 α′ が存在しないとき, α を飽和アイテム集合 と呼ぶ. 飽和アイテム集合は, アイテム集合の可逆圧縮形式の 1種である. 飽和アイテム集合の性質として, 以下の定 理が成り立つ. 定理 1 ([4]) すべての飽和アイテム集合 α, β（α̸= β） において, α∩ β = γ かつ γ ̸= ∅ であるアイテム集合 γ は必ず飽和アイテム集合である. 本稿では, マイニングの対象として, 飽和アイテム集合 を用いる. 定理 1 を利用して, アイテムの組み合わせ爆 発を抑えることを目的とする. 通常, k 個のアイテムからなるトランザクション Ti から作られるアイテム集合の候補数は 2k_{− 1 個となり} 組み合わせ爆発を起こしやすい. しかし, 飽和アイテム 集合で考えた場合, メモリ内部に登録されているアイテ ム集合の数を L とすると, 作られる飽和アイテム集合 の候補数は 定理 1 より |L| + 1 となる. なぜなら, メ モリに保存されるアイテム集合は, すべて飽和アイテム 集合である. したがって, 定理 1 より, メモリに新しく 登録される飽和アイテム集合の候補は, メモリ内部に登 録されてる飽和アイテム集合 と Ti の積で求められる からである. 図 1 に, 定理 1 の一例を示す. 図中の頻度表 T S と は飽和アイテム集合と頻度の組（エントリー）の集合 である. T S に飽和アイテム集合 abc が頻度 1, bde が 頻度 1, b が頻度 2 で登録されているとする. ストリー ムから新たな入力トランザクションとして T = af が きた場合を考える. このとき, T はそれ自身が飽和ア イテム集合であるため, 候補集合は, T と T S に登録さ れている飽和アイテム集合の積で求めることができる. 人工知能学会研究会資料 SIG-FPAI-B404-01

✽ ✁ ✂ ✄ ☎ ✆ ✝ ✞ ✟ ✠ ✌ ✡ ☛ ☞ ✍ ✎ ✏ ✑ ✒ ✓ ✔ ✕ ✖ ✓ ✔ ✕ ✖ ✓ ✔ ✕ ✖ ✓ ✔ ✕ ✖ ✗ ✘ ✎ ✏ ✑ ✒ ✙ ✚ ✛ ●✜ ✢ ✣ ✤ ✥ ✦✢ ✧ ●★ ✩ ✪ ●✜ ✢ ✣ ✤ ✥ ✦✢ ✫ ✬ ✭ ❋ ✍ ✗ ✘ ✮ ✯ ✰ ✪ ✎ ✏ ✱ ✲ ✳ ✴ ✵ ✶ ✷ ✸ ✹ ✺ ✻ ✼ ✾ ✿ ✺ 図 1: 定理 1 の一例 af∩ abc = a, af ∩ bde = ∅, af ∩ b = ∅ となるため, 候 補集合は af , a の 2 つとなる.

3

先行研究

本章では, 先行研究であるストリーム中の頻出飽和ア イテム集合マイニング（以下, CloStream）[4], Lossy Counting法（以下, LC 法）[2] について概説する.

3.1

CloStream

CloStreamは, 定理 1 を用いて, 高速にトランザク ションストリームから飽和アイテム集合を抽出するオ ンライン型厳密アルゴリズムである. 頻度表とトラン ザクションの積は, 各アイテムの頻度表中に出現するエ ントリーのリストを用いることで, 効率よく求める. 図 2に頻度表 T S とアイテムの出現エントリーのリスト 表 CLT の一例を示す. ここで, CLT とは, アイテム とそのアイテムの出現エントリーの集合の 2 つ組の表 である. ✽ ✁ ● ✂ ✄ ☎ ✍ ✆ ✝ ✞ ✟ ✠ ✡ ☛ ✼ ☞ ● ✂ ✄ ☎ ✼ ☞ ✽ ✌ ✎ ✏ ✑ ✒ ✓ ✔ ✕ ✖ ✗✘ ✙ ✒ ✘ ❋ ✗✚ 図 2: 頻度表とアイテムの出現エントリーのリスト表 アイテム b に関して, T S 中の飽和アイテム集合で b を含むものは cid 番号 1, 2, 3 のそれぞれのアイテム 集合である. よって, この cid の集合 {1, 2, 3} を b の 出現エントリーの集合として CLT に登録する. 以下, CLTにおいて, b に対する cid の集合を cidset(b) と表 記する. 3.1.1 CloStreamに関する予備的評価実験 CloStreamの性能を評価する. 実験には, Frequent

Itemset Mining Dataset Repository[5]より疎なデータ

セット 1 種と密なデータセット 1 種, Machine Learning Repository[6]より密なデータセット 1 種, また, 1992 年から 2013 年までに日本で発生した地震データの 4 つ のデータセットを用いる. 各データセットの詳細を以 下の表 1 に示す. 表 1: 実験に使用したデータ

データセット #(item) #(trans.) max ave

セット (trans.) (trans.) EarthQuake 1,229 16,769 74 2.48 retail 16,470 88,162 76 10.3 mushroom 118 8,124 23 23.0 connect 129 67,557 43 43.0 CloStreamに対して, 表 1 のデータセットも用いて 実行時間を計る予備実験1_{を行った. ここで条件とし} て, CPU 時間 12 時間（= 43,200 秒） でタイムアウト とする. その結果を表 2 に示す. 表中の N.A とは, 条件よりタイムアウトになったこ とを示している. 表 2 より, CloStream は, EarthQuake 以外のデータセットでタイムアウトとなっている. 理由 としては, CloStream は厳密アルゴリズムであるため, ストリーム上に出現した全ての飽和アイテム集合の頻 度を計算する. そのため, 処理が進むにつれ, 頻度表が 巨大になり, 計算速度が著しく低下するのだと考えられ る. よって本稿では, CloStream を厳密アルゴリズムか ら近似アルゴリズムに拡張し, 低頻度のエントリーを頻 度表から削除しメモリ節約を行うことを考える. 拡張 に用いる手法として Lossy Counting 法を利用する.

3.2

Lossy Counting

法

LC法 [2] はストリームデータから頻出アイテム集合 を抽出する誤差保証型のオンライン型近似アルゴリズ ムである. 相対最少頻度 σ（0 < σ < 1）, 許容誤差 ϵ （0 < ϵ≤ σ）, ストリーム長 N のストリームデータが 与えられたとき, LC 法は s(α)≥ (σ − ϵ)N となる全て のアイテム集合 α を抽出する. ∆(t)を時刻 t における誤差とする. アイテム集合 α において, f (α) を頻度表に登録されてからカウントさ れた実頻度, ∆αを α が頻度表に登録された時刻 tα で の誤差とする. α が LC 法のアルゴリズムによって与 えれる頻度 c(α) は f (α) + ∆αとなり, α の真の頻度 s(α) に対して, f (α)≤ s(α) ≤ f(α) + ∆α という関係 が成り立つ. 以下, c(α) を見積もり頻度と呼ぶ. した がって, 見積もり頻度は必ず真の頻度よりも大きい値と なる. 真の頻度が頻出であるならば, 見積もり頻度にお いても頻出となり, すべての頻出アイテム集合を抽出 することができる. また, LC 法のアルゴリズムは現時 刻 t において, c(α) < ∆(t) となる頻度をもつ α を頻 度表から削除している（ϵ-Elimination処理）. これ により, メモリ消費を抑えている. 1_{この実験は, 相対最少頻度 σ の値に依存しない}

4

LC-CloStream

本稿では, LC 法と CloStream の融合型である頻出飽 和アイテム集合のオンライン型近似アルゴリズム LC-CloStreamを提案する. LC-CloStream は, メモリ節約 を行いながらストリーム上の頻出飽和アイテム集合を 高速に抽出する. LC-CloStreamのアルゴリズムは, CloStream のアル ゴリズムに LC 法の ϵ-Elimination 処理を導入したもの である. また, それに伴い, LC-CloStream では, LC 法 で用いられている見積もり頻度を使用する. ここで, 時 刻 t で飽和アイテム集合 α を新たに頻度表に登録する ときについて説明する. もし, α がトランザクションと, 頻度表のエントリーである飽和アイテム集合 β との共 通部分だった場合, α は見積もり頻度 1 + f (β) + ∆βと して頻度表に登録する. このとき, f (β) を β が頻度表 に登録されてからカウントされた実頻度, ∆β を β が 頻度表に登録された時刻 tβでの誤差とする. そうでな かった場合, つまり, 新しく出現した飽和アイテム集合 （=トランザクション) を頻度表に登録する場合, α の見 積もり頻度は 1 + ∆(t) となる. 次に, ϵ-Elimination 処 理について説明する. LC 法と同様に, 現時刻 t におい て, 見積もり頻度が ∆(t) 未満となる飽和アイテム集合 αを 頻度表中から削除する.

4.1

幾つかの理論的性質

LC-CloStreamでは 2 つの理論的性質が考えられる. 1つは抽出した飽和アイテム集合に対する準完全性, も う 1 つは抽出した飽和アイテム集合から復元される頻 出アイテム集合に対する ϵ-完全性である. 以下にそれ ぞれの性質について示す. 4.1.1 飽和アイテム集合に対する準完全性 アルゴリズムの都合上, 全ての頻出飽和アイテム集合 は抽出できない場合が存在する. 以下に反例を示す. 例 1 (完全性の反例) 図 3 は頻出飽和アイテム集合の 抽出の完全性の反例である. 相対最少頻度 σ = 0.4, 許容誤差 ϵ = 0.1 とする. また, ストリームは T1 = ab, T2= abと到着したのち, T3 から T21 まで xyz の トランザクションが到着する. その後は  abc のトラ ンザクションが到着し続けるという状況を想定する. 図 3の上図は T21 を読み込んだときの真の飽和アイテム 集合とアルゴリズムにより計算された飽和アイテム集 合を表している. T21 を読み込んだ結果, アルゴリズム は飽和アイテム集合 xyz を頻度 19, ab を頻度 2 で保 持している. しかし, abc の頻度は ϵN 未満であるた め, ϵ-Elimination 処理により削除される. 次に図 3 の 下図より, T22= abcを読み込んだとき, アルゴリズム で保持される飽和アイテム集合と, ここまでのストリー ムから抽出される真の飽和アイテム集合は下図に通り であり, アルゴリズムは ab を抜き出せていない. この まま, ストリームを読み続けた場合, 本来なら頻出飽和 アイテム集合として ab を抜き出す必要があるが, アル ゴリズムは抜き出すことができない. しかし, アルゴリズムは以下の性質が成り立つ. ✪ ✁ ✂ ✄ ☎ ✆ ✶ ✝ ✆ ● ✞ ✟ ✠✡ ☛ ☞ ✌ ✍ ✎ ✏ ✑ ✒ ✽ ✓ ● ✔ ✕ ☛ ✖ ✗ ✛ ✘ ✙ ✽ ✓ ● ✔ ✕ ☛ ✖ ✗ ✚✚✚✚✚✚ ✚✚✚✚✚✚ ✜ ✢ ❋ ✣✤✥ ✦ ✪ ✁ ✂ ✄ ☎ ✆ ✶ ✝ ✆ ✞ ✟ ● ✠ ✡ ☛☞ ✌ ✍ ✎ ✏ ✑ ✒ ✓ ✔ ✽ ✕ ● ✖ ✗ ✌ ✘ ✙ ✛ ✚ ✜ ✽ ✕ ● ✖ ✗ ✌ ✘ ✙ ✢✢✢✢✢✢ ✢✢✢✢✢✢ 図 3: 頻出飽和アイテム集合の抽出の完全性の反例 定義 4 (ϵ-拡大不可能な飽和アイテム集合) 飽和アイテ ム集合 α とその絶対頻度を s(α) とし, ストリーム長 N , 許容誤差 ϵ とする. α に対して, α ⊃ α′ かつ sup(α)− sup(α′) < ϵN である飽和アイテム集合 α′ が 存在しないとき, α を ϵ-拡大不可能な飽和アイテム集 合と呼ぶ. 定理 2 (準完全性) LC-CloStream は, ϵ-拡大不可能な 飽和アイテム集合で頻出なものは全て抽出することが できる. 紙面の都合上, 定理 2 の証明は省略する. 4.1.2 頻出アイテム集合に対する ϵ-完全性 時刻 i におけるトランザクションを Ti とする. 任 意のアイテム集合 α について, 以下の集合族 T S(α, n) を定義する: T S(α, n) ={β|α ⊆ β, ⟨β, f(β), ∆(β)⟩ ∈ T S(n)}. ただし, T S(n) は, 時刻 n における頻度表と する. f (α) と ∆(α) を以下のように定義する: 1. T S(α, n)が空のとき, f (α) = 0, ∆(α) = ∆n, た だし, ∆nは時刻 n で処理が終了した時点での頻 度誤差. 2. そうでないとき, f (α) = f (αmax(n)), ∆(α) =

∆(αmax(n)), ただし, αmax(n) = argmax(β ∈

T S(α, n)).

αの見積もり頻度 c(α) を c(α) = f (α) + ∆(α) と定義

時刻 n での処理が終了した時点で, 出力要求があったと き, アルゴリズムが抽出するアイテム集合族を S(n) と する. このとき, S(n) = A(n)∪ B(n) とする. ただし, A(n) = {α|α ∈ T S(n), c(α) ≥ σt} B(n) = {β|β ⊆ α, β ̸= ∅, α ∈ A(n)} である. 任意のアイテム集合 α について, 時刻 i にお ける真の頻度を sup(α, i) とする. LC-CloStreamは頻出アイテム集合に関して, 以下の 完全性が成り立つ. 定理 3 (ϵ 誤差保証) 任意の時刻 n において, 任意の アイテム集合 α について, f (α)≤ sup(α, n) ≤ f(α) + ∆(α)を満たす. 定理 4 (ϵ-完全性) σn≤ ∆(n) のとき, 任意の頻出ア イテム集合 α は S(n) に含まれる. この 2 つの定理より, アルゴリズムで抽出した頻出飽 和アイテム集合から, すべての頻出アイテム集合を, 頻 度誤差 ϵt（= ∆(t)）の範囲で求めることができる. 紙 面の都合上, これらの定理の証明は省略する.

4.2

LC-CloStream

の評価実験

LC-CloStreamに対して, 表 1 のデータセットを用い て実行時間を計る実験2_{を実験 3.1.1 と同様に行った.} その結果を表 2 に示す. ここで, ϵ とは許容誤差である. 表 2 より, LC-CloStream は retail, mushroom, connect で大幅な速度向上がみら れる. 12 時間 (=43,200 秒) でタイムアウトであるため, retailと mushroom は 10 倍以上実行時間が早くなった ことがわかる. しかし, EarthQuake において, ϵ = 0.001 のとき, 実行時間は LC-CloStream のほうが遅い. これ は頻度表と, CLT を操作するオーバーヘッドがかかって いるためだと考えられる. そこで, 次は LC-CloStream のデータ構造の改良を考える.

4.3

データ構造の改良案

CloStream, LC-CloStreamともに, CLT を用いて頻 度表のエントリーを絞り込み, 候補集合の計算の高速 化を図っている. しかし, そのために行う和の計算が非 常に難しい. また, LC 法の導入により, 頻度表エント リーの削除に伴い, CLT の更新が必要となる. しかし, 先行研究である CloStream ではこれらの計算を効率化 するデータ構造の考慮がなされていない. そこで, 本稿 では, データ構造の改良を行う. まず, CLT の和の計算について考える. 任意（不特 定）個の集合の和を効率的に求めることはかなり難しい ので, ここでは, 和は求めずに直接登録されている cid のエントリーとトランザクションの積を求める. そし て, 積を求めた cid は計算済みとしてハッシュに登録 する. もし, ハッシュに登録されている cid が出現した ら, その cid はスキップする. これにより, 和の計算を 省略し, 実行時間の高速化を図る. 次に, エントリーの削除を伴う CLT の更新につい て考える. 改良案では, エントリーに CLT へのポイン タを持たせ, エントリーからダイレクトアクセスで削除 できるように改良した. これにより, CLT の更新を定 数時間で行い, 処理の高速化を図る. 2_{この実験は, 相対最少頻度 σ の値に依存しない}

4.4

改良型アルゴリズムの評価実験

データ構造を改良した改良型 CloStream, 改良型 LC-CloStreamに対して, 表 1 のデータセットを用いて幾 つかの評価実験3_{を行った. その結果を以下に示す.} 4.4.1 実行速度 まず, これまでと同様に改良型 CloStream, 改良型 LC-CloStreamの実行速度を図る実験を行った. その実 験結果を表 2 に示す.

まず CloStream と改良型 CloStram を比較する.

re-tail, connectに関しては N.A のままであったが,

Earth-Quakeでは約 15 倍ほど速度が早くなった. また, 改

良型 CloStream では mushroom での処理が終了する ようになり, 約 24 倍以上速度が向上している.

LC-CloStreamと改良型 LC-CloStream の比較に関しても,

改良型 LC-CloStream は retail, mushroom では約 10 倍, EarthQuake と connect では約 30 倍の速度向上が みられる. このことから, データ構造を改良したことで 実行時間を大幅に短縮することができた. 4.4.2 頻度表サイズの推移 次に, 改良型 CloStream と改良型 LC-CloStream で の処理中の頻度表サイズの推移を比較する. その結果 を図 4 に示す. 尚, 今回は紙面の関係上, mushroom の 結果のみを紹介する. ✶ 図 4: 処理中の頻度表サイズの推移: mushroom 図 4 において, 横軸が時刻 t, 縦軸が頻度表サイズで ある. 図 4 より, 改良型 CloStream での頻度表サイズは, 時 間ともに上昇し, 最終的なサイズは 25 万である. それ に対し, 改良型 LC-CloStream での頻度表サイズの推 移は, 非常に緩やかに上昇しており, 最終的なサイズ は 5 万である. これは改良型 CloStream と比較して 1₅ と なっている. したがって, LC-CloStream は, epsilon-Elimination処理が効果的に働いており, 大幅なメモリ 節約を行っていることがわかる. 3_{実験 4.4.1, 4.4.2, 4.4.4 は, 相対最少頻度 σ に依存しない}

表 2: 各アルゴリズムの実行時間 データ ϵ CloStream LC-CloStream 改良型 改良型 セット CloStream LC-CloStream 0.001 2,630.9 s 72.8 s EarhQuake 0.002 1,468.8 s 1,291.4 s 90.0 s 71.0 s 0.003 1,199.3 s 70.2 s 0.001 4,709.1 s 489.0 s

retail 0.002 N.A 892.7 s N.A 286.2 s

0.003 324.2 s 241.1 s

0.02 4,780.4 s 187.0 s

mushroom 0.03 N.A 2,368.3 s 1,791.9 s 122.0 s

0.04 1,424.3 s 89.8 s

0.80 N.A 18,872.4 s

connect 0.85 N.A N.A N.A 8,935.8 s

0.90 36,418.6 s 4,103.9 s 4.4.3 ϵを変化させたときの最終頻度表サイズと実行 時間 次に, 改良 CloStream-LC に対して, 許容誤差 ϵ を変 化させたときの最終的な頻度表サイズと実行時間の関 係を確認するための実験を行った. その実験結果の図 5に示す. 尚, 今回は紙面の関係上, connect の結果のみ を紹介する. ✶ 図 5: ϵ を変化させたときの最終頻度表サイズと実行 時間 横軸は許容誤差 ϵ である. 左縦軸は各 ϵ での最終的 な頻度表を大きさであり, 右縦軸は各 ϵ での実行時間 である. 図 5 より, 最終的な頻度表の大きさは, ϵ の値 と大きくするにつれ, 大きさは小さくなっている. また 実行速度についても同様に, ϵ の値と大きくするにつれ, 速度は早くなっている. 他のデータセットに対しても, 同じ傾向が見られた. このことから, 頻度表の大きさと 実行時間は比例関係にあり, 頻度表の大きさが小さくな るほど, 実行時間も早くなるのだと考えられる. 4.4.4 候補集合数 次に, 改良 CloStream と改良 LC-CloStream に対し て, 時刻毎の候補集合の数を確認する実験を行った. こ の結果を以下の表 3 に示す. max(freq.), ave(freq.) はアイテム集合をマイニング したときの候補集合数の最大と平均である. max(Clo.), ave(Clo.) は飽和アイテム集合を改良型 CloStream で マイニングしたときの候補集合数の最大と平均である. max(LC-Clo.), ave(LC-Clo.) は飽和アイテム集合を改 良型 LC-CloStream でマイニングしたときの候補集合 数の最大と平均である. まず, アイテム集合での候補集合数と提案手法であ る LC-CloStream での飽和アイテム集合の候補集合数 について比較する. 各データセットにおいて, アイテム 集合でマイニングした場合の候補集合数と比べて, LC-CloStreamでマイニングした場合の候補集合数は非常 に小さい数となっている. 特に, retail について, アイ テム集合の最大候補集合数は 276_{個であるところ,} LC-CloStreamでの最大候補集合数は ϵ = 0.001 のとき 920 であった. つまり, 飽和アイテム集合にすることで, 755 垓個 の候補集合を 920 個まで大幅に削減している. ま た, connect についても, アイテム集合での最大候補集 合数が 243 個であるところ, LC-CloStream では 最大 候補集合数 が ϵ = 0.8 で 123,554 個であった. 飽和ア イテム集合にすることで, 約 9 兆 個の候補集合数を 10 万個まで削減している. 次に, CloStream と CloStream を比較すると, LC-CloStreamの候補集合数は CloStream の候補集合より も小さい値となっているが, ほとんど変わらない. ここ で, mushroom の結果に注目する. CloStream と LC-CloStreamの候補集合数に大きな差は見られない. し かし, 表 4 より, 頻度表サイズの推移の大きな違いが 見られ, 結果として, 表 2 より, LC-CloStream の実行 速度は, CloStream よりも 10 倍早くなっている. した がって, 候補集合数はわずかな違いでしかないが, 処理 が進むにつれて, その差が積み重なっていき, 最終的な 頻度表サイズに大きく影響を及ぼすと考えられる. 以上のことから, 飽和アイテム集合を扱うことで, アイ テムの組み合わせ爆発を大幅に抑えていることがわかる. 加えて, 提案手法である LC-CloStream は, CloStream よりも組み合わせ爆発の抑制効果が高いと考えられる. 4.4.5 再現率と適合率 改良型 LC-CloStream に対して, 表 1 のデータセッ トを用いて, 頻出飽和アイテム集合を抽出する実験を 行った. このとき, 各データセット毎で許容誤差 ϵ は 固定し, 相対最少頻度 σ を変化させて実験を行ってい る. この実験結果を以下の表 4 に示す. ここで, U を アルゴリズムが抽出した頻出飽和アイテム集合の集合, X を U 中の真の頻出飽和アイテム集合の集合, A をス トリーム中の真の頻出飽和アイテム集合の集合とする. このとき, 再現率, 適合率を以下に定義する. 再現率 : |X| |A|, 適合率 : |X| |U|

表 3: 候補集合数

データ ϵ max(freq.) ave(freq.) max(Clo.) ave(Clo.) max ave

セット (LC-Clo.) (LC-Clo.)

0.001 5,718 11.7

EarhQuake 0.002 274 ₂2.5 _{5,793 12.9 5,717 11.4}

0.003 5,712 11.2

0.001 920 32.6

retail 0.002 276 ₂10.3 _{N.A N.A 654 25.1}

0.003 518 22.2

0.02 5,953 926.9

mushroom 0.03 223 ₂23 _{8,554 1,175.9 4,994 828.4}

0.04 4,316 749.3

0.80 123,554 48,627.3

connect 0.85 243 243 N.A N.A 77,166 31,408.0

0.90 40,739 16,779.4 表 4: 再現率と適合率 データ σ ϵ 抽出した 再現率 適合率 セット アイテム (%) (%) 0.007 146 100 88.4 EarhQuake 0.008 0.001 112 100 87.5 0.009 87 100 93.1 0.007 327 100 96.3 retail 0.008 0.001 248 100 98.0 0.009 196 100 98.5 0.2 1,185 95.8 96.8 mushroom 0.3 0.02 423 94.8 95.7 0.4 140 91.4 91.4 0.90 3,608  100 96.6 connect 0.91 0.8 2,915 100 96.7 0.92 2,313 100 95.6

表 4 では, EarthQuake, retail, connect については再 現率 100 ％であったが, mushroom は, 再現率 100 ％に はならなかった. 今回のデータセットの傾向から, 疎な データセットよりも密なデータセットのほうが, アルゴ リズムによる頻出飽和アイテム集合の抽出漏れが起き やすいのではないかと思われる. しかし, connect も密 なデータセットであったが, 再現率は 100 ％となってお り, すべての頻出飽和アイテム集合を抽出できている. ここで, connect と mushroom を比較してみると, 表 1 より, connect のストリーム長は mushroom の 10 倍程 度の大きさがある. ストリーム長が長いデータセット では, ϵ-Elimination 処理で飽和アイテム集合を削除し ても, 処理の途中で再び出現する可能性が高くなり, 最 終的な結果として, すべての頻出飽和アイテム集合を抽 出できるのではないかと推測する. ここで ϵ-完全性により Y を U から求められる頻出 アイテム集合とし, B をストリーム中の頻出アイテム 集合としたとき, 頻出アイテム集合における再現率を以 下に定義する. 頻出アイテム集合における再現率 : |Y | |B| アルゴリズムの理論的性質から, ストリーム中におけ る頻出アイテム集合についての再現率は 100 ％となる. したがって, この結果は圧縮の可能性を示している. 適合率は EarthQuake を除いてすべて 90 ％以上であ り, 高精度に飽和アイテム集合を抽出している. Earth-Quakeの適合率が下がってしまっている要因としては, σ と ϵ の値が近かったため, 誤差による影響をうけて しまい, 余分な飽和アイテム集合を多く抽出してしまっ たと考えられる.

5

まとめと今後の課題

本稿では, アイテムの組み合わせ爆発を抑えることを 目的に, 飽和アイテム集合のオンライン型近似アルゴリ ズムを提案した. 先行研究である CloStream を拡張し た LC-CloStream を提案し, 幾つかの理論的性質を示 した. また, 先行研究では考慮されていないデータ構造 の改良案を提案した. アルゴリズムを実装し評価実験 を行った結果, 候補集合数を大幅に削減し, 組み合わせ 爆発を抑えることに成功した. また, データ構造の改良 により, 実行速度を大幅に向上させた. 今後の課題として, 頻度表のエントリーを固定する ことで, 高速にマイニングを行うアルゴリズムの検討 を行っていく. また, 理論的性質と実験結果から LC-CloStreamはある種の圧縮を行っているといえる. そ のため, 今後, 圧縮に関しても検討も行っていく.

謝辞

本研究は一部，ISPS 科学研究費補助金（No.25330256） および JST さきがけの援助を受けている．

参考文献

[1] 有村博紀: 大規模データストリームのためのマイニン グ技術の動向,電子情報通信学会論文誌, Vol.J88-D-I, pp.563–575 (2005)

[2] G. S Manku and R. Motwani: Approximate fre-quency counts over data streams. Proc VLDM’02, pp.346–357 (2002)

[3] Y. Yamamoto, K. Iwanuma, S. Fukuda: Resource-oriented Approximation for Frequent Itemset Min-ing from Bursty Data Streams. SIGMOD’2014, 2014, June 22-27, Showbird, UT, USA.

[4] S. Yen, C. Wu, Y. Lee, V.S. Tseng, C. Hsieh: A Fast Algorithm for Mining Frequent Closed Itemsets over Stream Sliding Window. IEEE International

Confer-ence on Fuzzy Systems, 2011, June 27-30, Taipei.

[5] Frequent Itemset Mining Dataset Repository. http://fimi.ua.ac.be/data/.

(最終アクセス日: 2015/1/9). [6] Machine Learning Repository.

http://archive.ics.uci.edu/ml/datasets/Mushroom. (最終アクセス日: 2015/1/9)