Aprioriアルゴリズムとは

1994年にRakesh Agrawal と Ramakrishnan Srikant (リンクはibm.com外部にあります) によって導入された「Apriori」という名前は、アルゴリズムが計算で使用する頻出アイテムセットの事前知識を認めるものです。このアルゴリズムは、データに対して反復を実行して、kアイテムセット、つまり頻繁に一緒に発生するk個のアイテムを識別します。次に、kアイテムセットを使用して、k+1アイテムセットを識別します。Aprioriアルゴリズムは、頻繁に購入されるグループにアイテムを追加すると、その頻度を増やすのではなく、減らすだけであるという洞察に基づいています。このプロセスは、アイテムセットがデータ・セットに頻繁に出現する場合、そのサブセットもすべて頻繁である必要があるというAprioriプロパティに依存します。逆に、あるアイテムセットが低頻度であると識別された場合、そのスーパーセットはすべて低頻度であるとみなされます。

Aprioriアルゴリズムは、あらゆる種類のデータ・セット、特にトランザクション・データベースによって生成されたデータ・セットに適用でき、推奨システムをサポートするためのマーケットバスケット分析によく使用されます。例えば、衣服や靴を販売するEコマースプラットフォームを使用している場合、買い物客は靴を検索し、正式な黒の靴をショッピングカートに追加することにします。その後、買い物客は、インターフェースがソケットなどの他のアイテムの購入を推奨していることに気づきます。このレコメンデーション・システムの仕組みの1つは、顧客の購入パターンを学習し、おそらく一緒に購入された履歴があるアイテムを関連付けることです。

Aprioriアルゴリズムを使用する最大の利点の1つは、そのシンプルさと適応性です。ただし、Aprioriアルゴリズムは大規模なデータ・セットを処理する場合、それほど効率的ではありません。アイテムセット候補を生成する複数の反復プロセスは、計算コストがかかり、大量のメモリーを必要とする可能性があります。Aprioriは、多くの場合、こうした問題を軽減するために他の手法と組み合わせて使用されます。

Apriori関数はPython、Java、Rなどの多くの一般的なプログラミング言語に統合されており、既存のアプリケーションやシステムに統合することで、品質アソシエーションルールと頻繁なアイテムセットを簡単に生成できます。

Aprioriアルゴリズムの主要なステップでは、アイテムセットとそのすべてのスーパーセットを特定し、最も頻度の高いものを探してアソシエーションルールを作成します。

アルゴリズムはまず、データ・セット内のユニークなアイテム（1アイテムセットと呼ばれることもあります）とその頻度を識別します。次に、指定されたしきい値を超える確率で出現するアイテムを候補アイテムセットに結合し、出現頻度の低いアイテムセットを除外して、以降の手順で計算コストを削減します。このプロセスは頻繁なアイテムセットマイニングと呼ばれ、意味のある頻度を持つアイテムセットのみを探します。

このアルゴリズムはAprioriプロパティを使用して、頻繁なアイテムセットをさらに結合して、より大きなアイテムセットを形成します。確率が低い、より大きなアイテムセットの組み合わせがプルーニングされます。これにより、検索スペースがさらに削減され、計算がより効率的になります。

このアルゴリズムは、定義されたしきい値確率を満たすすべての頻度アイテムが網羅されるまで、ステップ1と2を繰り返します。各反復により、アイテムセットでより複雑で包括的な関連付けが生成されます。

Aprioriがアイテムセットを作成したら、生成された関連性と関係の強さを調べることができます。

Aprioriアルゴリズムは、サポート、信頼性、およびリフトメトリクスを使用して、その動作基準を定義し、性能効率を向上させます。

サポートは、トランザクションでアイテムが発生した回数と、トランザクションの合計回数の比率として定義されます。したがって、このメトリクスは、トランザクションで個々のアイテムが発生する確率を定義します。同じロジックをアイテムセットに拡張できます。

$S（I_A）=\frac{おCC（I_A）}{ToTalTranSaCTIonS}$

I _AはアイテムA、Occ（I _A）はアイテムAの発生数、 S（I _A） = アイテムAのサポート

例えば、小売店では、1日あたり2000件の取引のうち 250件にリンゴの購入が含まれているとします。計算式を使う：

$S（I_{APPleS}）=\frac{250}{\mathrm{2000年}}=0.125$

この結果は、リンゴがその日に購入された可能性が12.5%あることを意味します。

Aprioriアルゴリズムを適用するときに、必要な最小サポートしきい値を指定できます。これは、指定された最小サポートよりもサポートが少ないアイテムまたはアイテムセットは、使用頻度が低いとみなされます。

信頼度メトリクスは、アイテムまたはアイテムセットが一緒に発生する確率を識別します。例えば、トランザクションに2つのアイテムがある場合、一方のアイテムが存在すると、もう一方のアイテムにつながるものと想定されます。最初のアイテムまたはアイテムセットが 前提で、2 番目のアイテムセットが 結果です。したがって、信頼度は、前例と結果の両方を持つトランザクションの数と、前例のみを含むトランザクションの数の比率として定義されます。このシナリオは次のように表されます。

$C（A，B）=\frac{おCC（A\cap B）}{おCC（A）}$

ここで、 Aは前事態、 Bは結果、 C（A、B）はAがBにつながる確信を表します。

前の例を拡張して、リンゴとバナナを一緒に購入したトランザクションが150件あるとします。信頼度は次のように計算されます。

$C（APPleS，BananaS）=\frac{150}{250}=0.6$

この結果は、リンゴの購入がバナナの購入につながる可能性が60%であることを示しています。同様に、バナナの取引が合計500件あると仮定すると、バナナの購入がリンゴの購入につながるという確信度は次のように計算されます。

$C（BananaS，APPleS）=\frac{150}{500}=0.3$

バナナの購入がリンゴの購入につながる可能性は30%しかありません。

信頼性は確率を測る良い尺度ですが、アイテム間の明確な関連性を保証するものではありません。信頼度の値は、他の理由で高くなる場合があります。このため、アソシエーションルールを使用したマイニング中に、可能性の低いアソシエーションを除外するために、最小信頼度しきい値が適用されます。

上昇率は、品目Aから品目Bに至る可能性が品目Aの発生確率よりも高くなる要因です。このメトリクスは、AとBの間の関連性の強さを定量化します。これは、アイテムセット内のアイテム間に実際の関係があるのか、それとも偶然にグループ化されているのかを示すのに役立ちます。

$L（A，B）=\frac{C（A，B）}{S（A）}$ 


L_A、BはアイテムAがアイテムBにつながるリフトで、 C_A、BはアイテムAがアイテムBにつながるという確信を持ち、 S_AはアイテムAのサポートを表します。

上記の例では、次のことがわかります。

$L（APPleS，BananaS）=\frac{0.6}{0.125}=4.8$

高いリフト値は、リンゴとバナナが一緒に購入される可能性が、リンゴだけが購入される可能性の4.8倍であることを示しています。また、次のことがわかります。 

$L（BananaS，APPleS）=\frac{0.3}{0.25}=1.2$

ここでのリフト値が低いことから、バナナの購入がリンゴの購入につながるのは単なる偶然である可能性があることを示しています。

多くの場合、ブルートフォースアプローチ（ibm.com外部へのリンク）を適用してすべてのルールのサポートと信頼度のしきい値を計算し、しきい値を満たさないルールを削除すると、計算上、法外な負担がかかる可能性があります。Aprioriアルゴリズムの適用をより効率的にするために、他のアソシエーションルールマイニング手法と組み合わせることがよくあります。最も一般的な2つは、メモリーと計算の制約を減らすFP-growthアルゴリズム（ibm.com外部へのリンク）とその変形であるFP-Maxです。Aprioriアルゴリズムはdecision treeと組み合わせることもできます。その場合、Aprioriアルゴリズムは頻繁なアイテムセットを識別し、decision treeはアソシエーションルールを識別するのに役立ちます。

Aprioriアルゴリズムのもう1つの一般的なバリエーションは、動的アイテムセットカウンティング（DIC）（リンクはibm.comの外部にあります）です。これにより、すべてのトランザクションが記録されるのを待たずに、潜在的なアイテムセットのカウントが早期に開始されます。DICはデータ・セットをより小さなセグメントに分割し、各セグメントを個別に処理します。このセグメンテーションにより、アルゴリズムが頻度の高いアイテムセットを特定できない場合に早期に停止できますが、データを分割することで計算コストの大幅な削減にも役立ちます。

Aprioriアルゴリズムは、データがそれをサポートしている場合、クラスタリング・アルゴリズム のような教師なし学習ベースの人工知能アプリケーションにも役立ちます。一見独立したエンティティー間の関係や関連を特定し、それらを可能なクラスターにグループ化するのに役立ちます。

アイテムセットの検出とグループ化には複数の用途があり、Aprioriアルゴリズムはその汎用性から、データマイナーが最初に試すものと呼ばれることもあります。さまざまな業界の一般的なユースケースをいくつか見ていきます。

Aprioriアルゴリズムの最も一般的なアプリケーションの1 つは、マーケットバスケット分析を実行することです。小売業者は顧客の購入履歴を分析し、頻繁に購入される商品を互いに近くに、または同じ棚に配置する保管方法で、店舗のレイアウトを最適化します。Eコマースプラットフォームは、Aprioriアルゴリズムを使用して、ユーザーの好みと購入パターンマイニング分析に基づいて製品ベースの関係を研究し、効率的な顧客レコメンデーション・システムを作成します。同じ種類の分析を使用して、サービスの購入を最適化できます。例えば、カタログからトレーニングコースを選択したり、保険を選択する際に他のタイプの補償を推奨したりできます。

Aprioriアルゴリズムを使用して、症状と病気の間の強力なアソシエーションルールを見つけ、診断の効率を向上させ、的を絞った治療計画を考案することができます。例えば、 糖尿病を発症する可能性が高い患者は誰か（ibm.com外部へのリンク）、あるいは食事やライフスタイルが病気にどのような影響を与えるか（ibm.com外部へのリンク）などです。また、医薬品の副作用に関連する要因を特定するのにも役立ちます。

Aprioriアルゴリズムは非トランザクション・データベースにも適用できます。データアナリストは、ウェブ利用状況のマイニング、クリックストリームデータの分析、ユーザーの行動の解釈にAprioriをよく使用します。

Aprioriアルゴリズムのもう1つの一般的な応用例は、金融取引における不正なパターンを特定することです。特定の購入パターンが不正の可能性があると特定すると、金融機関は取引を一時停止するか、口座名義人に連絡するために迅速に行動することができます。