Skip to content
検索結果に戻る

ECLAT による頻出アイテムセットマイニング

提唱者
Mohammed J. Zaki
年
2000
種類
Frequent-itemset mining algorithm (vertical format)
系統
Pattern mining

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

ECLAT は、Mohammed Zaki が 2000 年に導入した手法で、垂直データ表現を用いて頻出アイテムセットをマイニングします。トランザクションをスキャンする代わりに、各アイテムについて、それを含むトランザクションIDの集合(tidset)を格納し、アイテムセットのサポートをtidsetの共通部分を取ることで計算します。この深さ優先の共通部分ベースのアプローチは、Apriori の水平スキャンや FP-Growth のツリーに代わる、高速でメモリ効率の良い方法です。

手法の背後にある直感

ほとんどのアイテムセットマイナーは行ごとに考えます。つまり、各トランザクションにどのアイテムが含まれているか、という具合です。ECLAT はこの考え方を横倒しにします。各アイテムについて、それを含むトランザクションのリストを保持します。すると、アイテムペアのサポートは、それらのリストの重複部分のサイズ、つまり単純な集合の共通部分を取るだけで得られ、データベースを再スキャンする必要は全くありません。より長い頻出アイテムセットを見つけるには、短いアイテムセットのリストを共通部分で結合していきます。この深さ優先探索を行い、共通部分が小さくなりすぎた時点で枝刈りすることで、効率的にすべての頻出アイテムセットを列挙します。

歴史学

Mohammed Zaki は、2000 年の IEEE TKDE 誌におけるスケーラブルな相関マイニングに関する論文で ECLAT と垂直マイニングパラダイムを導入し、その後 diffset (dECLAT) で改良しました。これは、Apriori (1994 年、水平候補生成) および FP-Growth (2000 年、ツリーベース) とともに、3 つの代表的な頻出アイテムセットアルゴリズムファミリーの 1 つとなり、それぞれがスキャン、メモリ、データ密度を異なる方法でトレードオフしています。ECLAT は、データマイニングツールキットにおける標準的な選択肢であり続けています。

使うべき場面

垂直的で共通部分ベースのアプローチがデータに適している場合には、ECLAT を頻出アイテムセットマイニングに使用してください。これは、密なデータセットで非常に高速であることが多く、データベースのスキャンを繰り返すことを回避するため、Apriori に代わる強力な選択肢であり、FP-Growth と同等の性能を発揮します。tidsetが適度なサイズでメモリに収まる場合に特に有効で、diffsetバリアントは密なデータをうまく処理します。そのコストとしては、頻出アイテムのtidsetが大きなスパースデータセットではメモリを大量に消費する可能性があり、中間的な共通部分の計算にはオーバーヘッドが伴います。また、他のすべてのサポートベースのマイニングと同様に、最小サポート閾値に敏感です。常にそうであるように、頻出アイテムセットは最初の段階に過ぎず、信頼度/リフトを持つ相関ルールはその後生成されます。データ密度とメモリに基づいて、ECLAT、FP-Growth、Apriori の中から選択してください。

限界と注意点

  • 頻出アイテムのtidsetは大きくなる可能性があり、大規模データセットではメモリを消費する。
  • 中間的な共通部分の結果は、メモリ/時間オーバーヘッドを追加する。
  • 水平(Apriori)表現よりも直感的ではない。
  • 他のすべてのアイテムセットマイニングと同様に、最小サポート閾値に敏感。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 高速なtidsetの共通部分計算によるサポート算出 — データベースのスキャンを繰り返す必要なし。
  • プレフィックス同値クラスを用いた深さ優先探索により、作業の再利用とメモリの局所化を実現。
  • 密なデータセットで非常に効率的であり、FP-Growth と競合する。
  • diffset最適化により、メモリと共通部分のコストをさらに削減。

応用

  • マーケットバスケット分析および小売業における相関マイニング。
  • ウェブおよびクリックスルーの共起分析。
  • バイオインフォマティクスにおける頻出共起発見。
  • 垂直的で共通部分ベースのアプローチを好むあらゆる頻出アイテムセットタスク。
  • diffset ECLAT が得意とする密なトランザクションデータセット。

使い方

使い方

1

データベースは一度、垂直形式に変換されます。各アイテムは、そのアイテムが出現するトランザクションIDの集合であるtidsetにマッピングされます。これが主要なデータ構造となり、以降のすべての処理は、元のトランザクションに対するパスではなく、tidsetに対する集合演算となります。

数式
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

アイテムセットのサポートは、そのアイテムのtidsetの共通部分の要素数、すなわちそれらすべてを含むトランザクションの数です。カウントは共通部分の計算に変わり、これは高速です。頻出単一アイテム(そのtidsetが十分に大きいもの)が探索の種となります。

数式
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

アイテムセットは、tidsetを共通部分で結合することによって拡張されます。X ∪ {y} のtidsetは、X のtidsetと {y} のtidsetの共通部分です。ECLAT は、アイテムセット格子を、共通のプレフィックスを持つアイテムセットである同値クラス内で深さ優先で探索するため、共通部分が再利用され、探索は局所的に保たれます。

数式
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

拡張は、そのtidset(したがってサポート)が最小サポート閾値を満たす場合にのみ保持されます。そうでなければ、その枝は刈り込まれます(反単調性:上位集合は頻出ではありえません)。Diffset(tidset間の差分のみを格納する)は、メモリと共通部分のコストをさらに削減する一般的な最適化です。

数式
\text{keep extensions with } \text{support} \ge \text{minsup}

よくある落とし穴

  • tidsetがメモリを爆発させるような非常に大きなスパースデータをマイニングする場合 — diffsetまたはFP-Growthを検討してください。
  • 最小サポートを低く設定しすぎると、管理不能な数のアイテムセットが生成される。
  • 頻出アイテムセットと相関ルールを混同すること(ルールは別のステップ)。
  • 密なデータで大きな利点をもたらすdiffsetバリアントを無視すること。

よくある質問

ECLAT は Apriori および FP-Growth とどのように異なりますか?

3 つすべてが頻出アイテムセットを見つけます。Apriori は候補生成と多数のスキャンを伴う水平形式を使用します。FP-Growth はデータをツリーに圧縮して再帰的にマイニングします。ECLAT は垂直 tidset 形式を使用し、深さ優先でトランザクションIDリストを共通部分で結合してサポートを計算します。ECLAT と FP-Growth は Apriori の繰り返しスキャンを回避します。

tidset とは何ですか?

tidset(トランザクションIDセット)は、特定のアイテムまたはアイテムセットを含むトランザクションのリストです。ECLAT はこれらを垂直に格納し、アイテムセットのサポートを、そのアイテムのtidsetの共通部分のサイズとして計算し、カウントを集合の共通部分に変換します。

diffset とは何ですか?

diffset は、フル tidset の代わりに、アイテムセットの tidset とその親の tidset との差分のみを格納します。密なデータでは、これによりメモリと共通部分のコストが劇的に削減され、dECLAT バリアントに大幅な効率上の利点をもたらします。

関連する手法

参考文献

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    DOI 文献を開く
    コピーしました。