アプリオリアルゴリズム原理の要約

[[182123]]

関連付けアルゴリズムは、データ マイニングにおける重要なタイプのアルゴリズムです。 1993 年に、R. Agrawal らは、顧客取引データ内のアイテム セット間の関連ルールをマイニングする問題を初めて提案しました。この問題の核心は、2 段階の頻繁セットのアイデアに基づく再帰アルゴリズムです。この関連ルールは、1 次元、1 層、ブール関連ルールに分類され、代表的なアルゴリズムは Apriori アルゴリズムです。

Apriori アルゴリズムは、関連ルールの検出プロセスを 2 つのステップに分割します。最初のステップでは、反復処理を通じてトランザクション データベース 1 内のすべての頻繁アイテム セット (つまり、サポートがユーザーが設定したしきい値以上であるアイテム セット) を取得します。2 番目のステップでは、頻繁アイテム セットを使用して、ユーザーの最小信頼を満たすルールを構築します。その中で、すべての頻繁なアイテム セットのマイニングまたは識別がアルゴリズムの中核であり、全体の計算作業の大部分を占めます。

Apriori アルゴリズムは、データ関連ルールのマイニングによく使用されるアルゴリズムです。データ値に頻繁に出現するデータ セットを見つけるために使用されます。これらのセットのパターンを見つけることは、何らかの決定を下すのに役立ちます。たとえば、一般的なスーパーマーケットの買い物データセットや電子商取引のオンラインショッピングデータセットで、頻繁に出現するデータセットを見つけると、スーパーマーケットの場合は商品の配置を最適化でき、電子商取引の場合は商品の倉庫の場所を最適化できるため、コストを節約し、経済的利益を増やすことができます。以下に Apriori アルゴリズムの概要を示します。

1. 頻出アイテムセットの評価基準

頻繁なアイテムセットとはどのようなデータでしょうか。これは簡単ではない、肉眼で一目見れば、出現回数の多いデータセットが頻繁なアイテムセットである、と言うかもしれません。確かに、これは間違いではありませんが、2 つの問題があります。1 つ目は、データ量が非常に多い場合、頻繁なアイテムセットを肉眼で直接見つけることができないことです。このため、Apriori、PrefixSpan、CBA などの関連ルール マイニング アルゴリズムが生まれました。 2 つ目は、頻繁なアイテムセットの標準が存在しないことです。たとえば、レコードが 10 件あり、A と B が同時に 3 回出現する場合、A と B を合わせて頻出アイテム セットを構成していると言えますか? そのため、頻出アイテム セットを評価するための基準が必要です。

頻繁に使用されるアイテムセットの評価基準として一般的に使用されるのは、サポート、信頼性、リフトです。

サポートとは、データセット全体に対する、データセット内に複数の関連データが出現する回数の割合です。または、複数のデータの関連付けが発生する確率。相関関係を分析したい2つのデータXとYがある場合、対応するサポートは

同様に、相関関係を分析したい 3 つのデータ X、Y、Z がある場合、対応するサポートは次のようになります。

一般的に言えば、サポート率の高いデータは必ずしも頻繁なアイテムセットを構成するわけではありませんが、サポート率が低すぎるデータは必ずしも頻繁なアイテムセットを構成しません。

信頼度は、1 つのデータが出現した後に別のデータが出現する確率、またはデータの条件付き確率を反映します。相関関係を分析したい2つのデータXとYがある場合、XのYに対する信頼度は

同じことが複数のデータの信頼度にも当てはまります。たとえば、3 つのデータ X、Y、Z の場合、Y と Z に対する X の信頼度は次のようになります。

たとえば、ショッピングデータでは、鶏の足に対応するペーパータオルの信頼度レベルは 40%、サポートレベルは 1% です。つまり、ショッピングデータでは、合計 1% のユーザーが鶏の足とペーパータオルの両方を購入しており、鶏の足を購入するユーザーの 40% がペーパータオルも購入していることになります。

リフトは、Y が含まれる条件下で X が含まれる確率と、X が全体的に発生する確率の比率を表します。

リフトはXとYの相関関係を反映します。相関関係が高いほど、リフトは小さくなります。特別なケースとして、XとYが独立している場合、

***に到達してください。この時点で

一般的に、データセット内の頻繁なデータセットを選択するには、評価基準をカスタマイズする必要があります。最も一般的に使用される評価基準は、カスタム サポート、またはカスタム サポートと信頼性の組み合わせです。

2. アプリオリアルゴリズムのアイデア

Apriori アルゴリズムでは、頻繁なアイテムセットを判断する基準としてサポートを使用します。 Apriori アルゴリズムの目的は、最適な K 頻繁セットを見つけることです。ここには 2 つの意味があります。まず、サポート基準を満たす頻繁なセットを見つける必要があります。しかし、このような頻繁なセットはたくさんあるかもしれません。 2 番目の意味は、頻出セットの *** 個を見つけたいということです。たとえば、サポートを満たす頻繁セット AB と ABE が見つかった場合、AB は 2 項目の頻繁セットであり、ABE は 3 項目の頻繁セットであるため、AB を破棄して ABE のみを保持します。では具体的に、Apriori アルゴリズムはどのようにして K 項目の頻出セットをマイニングするのでしょうか?

Apriori アルゴリズムは反復法を使用して、最初に候補となる 1 項目セットとそれに対応するサポートを検索し、次にサポートが低い 1 項目セットを削除して、頻繁な 1 項目セットを取得します。次に、残りの頻繁な 1 アイテム セットを接続して、候補となる頻繁な 2 アイテム セットを取得します。サポートが低い候補となる頻繁な 2 アイテム セットは除外され、真の頻繁な 2 アイテム セットが取得されます。このプロセスは、頻繁な k+1 アイテム セットが見つからなくなるまで何度も繰り返されます。対応する頻繁な k アイテム セットのセットが、アルゴリズムの出力結果です。

このアルゴリズムは依然として非常に単純であることがわかります。i 回目の反復プロセスには、候補となる頻繁な i アイテム セットのサポートをスキャンして計算する、真の頻繁な i アイテム セットを取得するための剪定、および候補となる頻繁な i+1 アイテム セットを生成するための接続という 3 つのステップが含まれます。

次の簡単な例を見てみましょう。

データセット D には、134、235、1235、25 の 4 つのレコードがあります。ここで、頻出 k 項目セットを見つけるために Apriori アルゴリズムを使用し、最小サポートを 50% に設定します。まず、5 つのデータすべてを含む候補となる頻繁な 1 項目セットを生成し、5 つのデータのサポートを計算します。計算後、データを整理します。データ 4 はサポートが 25% しかないため、整理されます。最終的な頻繁な 1 項目セットは 1235 です。次に、12、13、15、23、25、35 の合計 6 つのグループを含む候補の頻繁な 2 項目セットをリンクして生成します。この時点で、最初の反復ラウンドは終了します。

2 回目の反復では、データセットをスキャンして候補となる頻出 2 項目セットのサポートを計算し、プルーニングを実行します。12 と 15 のサポートは 25% しかないため、これらは除外され、13、23、25、35 を含む実際の頻出 2 項目セットが取得されます。ここで、候補となる頻出 3 項目セット (123、125、135、235) の合計 4 つのグループを生成しますが、これは図には描かれていません。候補となる頻出 3 項目セットのサポートを計算すると、123、125、135 のサポートは 25% であることがわかったので、これらを整理し、最終的な実際の頻出 3 項目セットは 235 になります。この時点ではデータを接続できず、候補となる頻出項目 4 項目セットを取得できないため、最終結果は頻出項目 3 項目セット 235 になります。

3. 事前アルゴリズムプロセス

以下に、Aprior アルゴリズムのプロセスを要約します。

入力: データセットD、サポート閾値αα

出力: *** 頻繁な k-アイテムセット

1) データセット全体をスキャンし、頻出1項目セットの候補として出現したすべてのデータを取得します。 k=1 の場合、頻出 0 項目セットは空セットになります。

2) 頻出k項目セットのマイニング

a) データをスキャンして、候補となる頻出k項目セットのサポートを計算する

b) 候補となる頻繁な k 項目セット内のサポートがしきい値より低いデータ セットを削除して、頻繁な k 項目セットを取得します。取得された頻繁な k 項目セットが空の場合、頻繁な k-1 項目セットのセットがアルゴリズムの結果として直接返され、アルゴリズムは終了します。取得された頻繁な k 項目セットに項目が 1 つしかない場合、頻繁な k 項目セットのセットがアルゴリズムの結果として直接返され、アルゴリズムは終了します。

c) 頻出 k 項目セットに基づいて、候補となる頻出 k+1 項目セットを連結して生成します。

3) k=k+1 としてステップ 2 に進みます。

アルゴリズムの手順から、Aprior アルゴリズムは各反復でデータ セットをスキャンする必要があることがわかります。そのため、データ セットが大きく、データの種類が多い場合、アルゴリズムの効率は非常に低くなります。

4. Apriorアルゴリズムの概要

Aprior アルゴリズムは、非常に古典的な頻繁なアイテムセット マイニング アルゴリズムです。FP-Tree、GSP、CBA など、多くのアルゴリズムが Aprior アルゴリズムに基づいています。これらのアルゴリズムは、Aprior アルゴリズムの考え方を活用していますが、アルゴリズムに改良が加えられ、データマイニングの効率が向上しています。そのため、現在では、Aprior アルゴリズムを直接データマイニングに使用することはほとんどありません。ただし、Aprior アルゴリズムを理解することは、他の Aprior 型アルゴリズムを理解するための前提条件です。同時に、アルゴリズム自体は複雑ではないため、勉強する価値があります。

ただ、scikit-learnには頻出集合マイニング関連のアルゴリズムライブラリがないので残念です。後のバージョンで追加されるのかな。

著者: Liu Jianping Pinard (プログラマーとして 10 年の経験があり、数理統計、データマイニング、機械学習、ビッグデータプラットフォーム、ビッグデータプラットフォームアプリケーション開発、ビッグデータの可視化に興味があります。ブログ: Liu Jianping Pinard)