Skip to content
検索結果に戻る

Aprioriアルゴリズム

提唱者
Agrawal, R. & Srikant, R.
年
1994
種類
Frequent itemset and association rule mining algorithm
系統
Machine learning

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

文字サイズ

何をする手法か?

Aprioriアルゴリズムは、1994年にAgrawalとSrikantによって導入された、トランザクションデータベースにおける頻出アイテムセットおよび相関ルールの発見のための基礎的な手法である。このアルゴリズムは、サポートの反単調性(anti-monotone property)によって導かれる幅優先・レベルごとの探索を利用し、ユーザー設定の最小閾値を上回る共起頻度を持つアイテムの組み合わせを効率的に列挙し、それらのパターンから解釈可能な「ならば」ルールを抽出する。

手法の背後にある直感

スーパーマーケットのレシートデータベースを考えてみよう。Aprioriの洞察は反単調性にある。すなわち、一緒に購入されることが稀な商品のペアがあれば、そのペアを含むより大きなアイテムセットが頻出することはありえない。これにより、アルゴリズムは、アイテムの組み合わせの指数関数的に広がる探索空間を、レベルごとに候補を構築することで刈り込むことができる。単一アイテムから始め、次にペア、次にトリプルと進み、そのサブセットが既に頻度が低いことがわかっている候補は、データ中でカウントする前に破棄される。

歴史学

Rakesh AgrawalとRamakrishnan Srikantは、相関ルールマイニング問題の1993年の定式化に基づき、1994年のVLDBでAprioriアルゴリズムを導入した。この名前は、その主要な洞察、すなわち、頻出(k)-アイテムセットの事前知識を利用してレベルk+1の候補を刈り込むことを反映している。このアルゴリズムは、FP-Growth (2000) や Eclat を含むすべての後続の頻出アイテムセットアルゴリズムに対する標準的なベンチマークとなり、データマイニングおよび機械学習の教科書における標準的な章であり続けている。

使うべき場面

トランザクションデータまたはバイナリのアイテム存在データにおける共起パターンまたは「ならば」関係を発見することが目標である場合、Aprioriを使用する。例えば、マーケットバスケット分析、アンケートのアイテム共推薦、医療診断の共起、またはテキスト用語の関連付けなどである。出力ルールの透明性と解釈可能性が優先される中規模データセットに適している。トランザクションデータベースが非常に大きい(数百万行でアイテムカタログが広い)場合、AprioriはFP-Growthと比較して遅いため使用しないこと。そのような場合はFP-Growthが好ましい。また、離散化されていない連続数値データには不適切であり、方向性や因果関係をモデル化しない。

限界と注意点

  • トランザクションデータベースの繰り返しフルスキャンにより、大規模データセットでは遅くなる。スケールが大きい場合はFP-Growthがしばしば好まれる。
  • サポート閾値を下げると、指数関数的な数の候補アイテムセットとルールが生成され、解釈が困難になる可能性がある。
  • アイテム間の時間的順序、方向性、または因果関係を捉えない。
  • 結果は、ドメイン知識または体系的なチューニングを必要とするサポートと信頼度の閾値の選択に敏感である。

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

強み

  • サポート、信頼度、リフトが定量化された、完全に解釈可能な「ならば」ルールを生成する。
  • 反単調性による刈り込み特性により、本来指数関数的な探索が実行可能になる。
  • データに対する事前のラベル付けを必要とせず、完全に教師なしである。
  • 閾値パラメータ(サポート、信頼度)により、分析者はルールの粒度を直接制御できる。
  • 出力ルールは実行可能であり、アルゴリズムの背景知識を持たない非技術的なステークホルダーにも伝達できる。
  • 基礎的で、多く引用されており、事実上すべての主要なデータマイニングライブラリに実装されている。

応用

  • マーケットバスケット分析:棚の配置やプロモーションをガイドするために、どの製品が一緒に購入されるかを特定する。
  • 医療情報学:患者記録における共起する症状、診断、または処方箋を特定する。
  • ウェブ利用マイニング:ユーザーが一緒に訪問またはアクティブにする傾向があるページや機能を特定する。
  • アンケートおよび質問紙分析:どのアイテムまたはスケール回答が体系的に共推薦されるかを検出する。
  • 推薦システムブートストラップ:協調フィルタリングを展開する前に、候補アイテムの関連性を生成する。
  • 不正検出:通常のバスケットから逸脱するトランザクションログ内の異常な共起パターンを表面化する。

使い方

使い方

1

分析者はアルゴリズムを実行する前に2つの閾値を選択する。最小サポート(特定のアイテムセットが頻出とみなされるために必要なトランザクションの割合)と最小信頼度(保持される「ならば」ルールに必要な条件付き確率)である。これら2つの値は、出力の量と特異度を制御し、ドメイン知識または探索的な実行を通じて調整されるべきである。

2

アルゴリズムは、トランザクションデータベースを1回フルスキャンして、各個々のアイテムの出現頻度をカウントする。サポートが最小サポート閾値を満たすかそれを超えるアイテムのみが保持され、残りは破棄される。この頻出単一アイテムのセットが、候補の最初のレベルを形成する。

数式
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

レベルkで見つかった頻出アイテムセットをペアごとに結合して、サイズk+1の候補アイテムセットを形成する。最初のk-1個のアイテムを共有するペアのみが結合される。この規則により、候補セットはコンパクトに保たれる。新しいデータベーススキャンで、各候補のサポートをカウントする。

4

カウントする前に、サイズk+1の各候補は、そのすべての(k)-サブセットに対してチェックされる。もしサブセットのいずれかが前のレベルで頻出でなかった場合、その候補はデータ読み込みなしに直ちに刈り込まれ、反単調性を利用して計算が削減される。この刈り込みステップを生き残ったものが、次のレベルの頻出アイテムセットを形成する。

5

サイズ2以上の各頻出アイテムセットから、アイテムを先行部分(antecedent)と後続部分(consequent)に分割することによって、可能なすべての「ならば」ルールが生成される。各ルールは、先行部分を含むトランザクションのうち後続部分も含むものの割合である信頼度で評価される。最小信頼度を下回るルールは破棄される。

数式
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

生き残ったルールは、観測された信頼度を後続部分のベースライン頻度と比較するリフト値でランク付けされる。1を超えるリフトは、先行部分と後続部分が偶然以上に共起することを示唆する。1に近いリフトは独立性を示し、1を下回るリフトは負の相関を示す。最も高いリフトを持つルールが、最も実行可能な発見である。

数式
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

よくある落とし穴

  • 最小サポートを低く設定しすぎると、リフトによるフィルタリングなしに、数千もの低品質なルールに埋もれてしまう。
  • 高い信頼度を共起ではなく因果関係と解釈してしまう。高い信頼度を持つがリフトが1に近いルールは些細なものである。
  • 連続特徴量を事前に離散化せずにAprioriに適用し、アイテム空間を膨張させ、結果を劣化させる。
  • アイテムセットのサンプルサイズがサポート推定値を信頼するのに十分な大きさであるかを確認せずにルールを報告する。
  • (店舗の会員カードのような)普遍的に購入されるアイテムに関わる非情報的なルールを除外することを怠る。

よくある質問

サポート、信頼度、リフトの違いは何ですか?

サポートは、アイテムセットを含む全トランザクションの割合であり、普及度を測定する。信頼度は、先行部分が与えられた場合に後続部分が現れる条件付き確率であり、ルールの信頼性を測定する。リフトは、観測された信頼度と後続部分のベースライン頻度の比率であり、1を超えるリフトは、アイテムの人気によって駆動される偶然ではなく、真の正の相関を示す。

どのような場合にAprioriよりもFP-Growthを選択すべきですか?

FP-Growthはデータベースをツリー構造に圧縮し、繰り返しフルスキャンなしでマイニングするため、大規模データセットや最小サポートが低い場合に大幅に高速になる。Aprioriは理解と実装が容易で、実行時間がボトルネックにならない小規模から中規模のデータセットでうまく機能する。

最小サポートと信頼度をどのように選択しますか?

普遍的なルールはない。一般的な実践としては、いくつかのサポートレベルでアルゴリズムを実行し、サポートに対する頻出アイテムセットの数をプロットし、曲線の肘の部分で値を選択する。信頼度は、ビジネスまたは研究の質問に基づいて設定される。ミッションクリティカルなルールにはより高い信頼度を、探索的な発見にはより低い信頼度を設定する。常にドメイン専門知識に対してトップルールを検証すること。

Aprioriは数値または連続データも扱えますか?

Aprioriはバイナリのアイテム存在データを必要とする。連続変数は、アイテムとしてエンコードする前にビン(例:年齢を低/中/高)に離散化する必要がある。不適切な離散化は発見されたルールを著しく歪める可能性があるため、ビニング戦略は慎重な検討に値する。

Aprioriはアイテム間の因果関係を示唆しますか?

いいえ。相関ルールは共起を捉えるものであり、因果関係や方向性を捉えるものではない。「パン → バター」というルールは、それらが同じバスケットに頻繁に現れることを意味する。パンを買うことがバターを買う原因になるとか、関係が因果的に非対称であるという意味ではない。

関連する手法

参考文献

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    出版物の文献を開く
    コピーしました。
  2. Apriori algorithm. Wikipedia.

    出版物の文献を開く
    コピーしました。