データマイニングにおけるAprioriアルゴリズム：例を使用した実装

apriori algorithm data mining

データマイニングで頻繁なアイテムセットを見つけるためのAprioriアルゴリズムに関する詳細なチュートリアル。このチュートリアルでは、Aprioriの手順とその仕組みについて説明します。

これで データマイニングチュートリアルシリーズ 、私たちは見ていた デシジョンツリーアルゴリズム 前のチュートリアルで。

データマイニングには、関連付け、相関、分類、クラスタリングなど、いくつかの方法があります。

最高のゲーム会社は何ですか

このチュートリアルは、主に相関ルールを使用したマイニングに焦点を当てています。アソシエーションルールにより、テーブル内で一緒に発生するアイテムまたは属性のセットを識別します。

学習内容：

• アイテムセットとは何ですか？
  • 頻繁なアイテムセットとは何ですか？
  • フリークエントパターンマイニング（FPM）
  • アソシエーションルール
• なぜ頻繁なアイテムセットマイニング？
  • Aprioriアルゴリズム–頻繁なパターンアルゴリズム
    • アプリオリのステップ
    • 利点
    • 短所
• アプリオリの効率を改善する方法
• Aprioriアルゴリズムのアプリケーション
• 結論
  • 推奨読書

アイテムセットとは何ですか？

アイテムのセットをまとめてアイテムセットと呼びます。アイテムセットにkアイテムがある場合、それはkアイテムセットと呼ばれます。アイテムセットは、2つ以上のアイテムで構成されます。頻繁に発生するアイテムセットは、頻繁なアイテムセットと呼ばれます。 したがって、頻繁なアイテムセットマイニングは、一緒に頻繁に発生するアイテムを識別するためのデータマイニング手法です。

例えば 、パンとバター、ラップトップとウイルス対策ソフトウェアなど。

頻繁なアイテムセットとは何ですか？

アイテムのセットは、サポートと信頼性の最小しきい値を満たしている場合、頻繁と呼ばれます。サポートは、単一のトランザクションで一緒に購入されたアイテムとのトランザクションを示します。信頼度は、アイテムが次々に購入されるトランザクションを示します。

頻繁なアイテムセットマイニング方法の場合、最小しきい値のサポートと信頼性の要件を満たすトランザクションのみを考慮します。これらのマイニングアルゴリズムからの洞察は、多くの利点、コスト削減、および競争上の優位性の向上をもたらします。

データのマイニングにかかる​​時間と、頻繁なマイニングのデータ量にはトレードオフがあります。頻繁なマイニングアルゴリズムは、アイテムセットの隠れたパターンを短時間でより少ないメモリ消費でマイニングするための効率的なアルゴリズムです。

フリークエントパターンマイニング（FPM）

頻繁なパターンマイニングアルゴリズムは、データセット内のさまざまなアイテム間の関係を発見するためのデータマイニングの最も重要な手法の1つです。これらの関係は、相関ルールの形式で表されます。データの不規則性を見つけるのに役立ちます。

FPMには、データ分析、ソフトウェアバグ、クロスマーケティング、販売キャンペーン分析、マーケットバスケット分析などの分野で多くのアプリケーションがあります。

Aprioriを通じて発見された頻繁なアイテムセットは、データマイニングタスクで多くのアプリケーションを持っています。データベース内の興味深いパターンの検索、シーケンスの検索、相関ルールのマイニングなどのタスクは、それらの中で最も重要です。

相関ルールは、スーパーマーケットのトランザクションデータに適用されます。つまり、購入した製品に関する顧客の行動を調べるために適用されます。アソシエーションルールは、アイテムが一緒に購入される頻度を記述します。

アソシエーションルール

アソシエーションルールマイニングは次のように定義されます。

「I = {…}をアイテムと呼ばれる「n」個のバイナリ属性のセットとします。 D = {…。}をデータベースと呼ばれるトランザクションのセットとします。 Dの各トランザクションには一意のトランザクションIDがあり、Iのアイテムのサブセットが含まれています。ルールは、X-> Yの形式の含意として定義されます。ここでX、Y？私とX？Y =?。アイテムXとYのセットは、それぞれルールの前件と後件と呼ばれます。」

相関ルールの学習は、大規模なデータベースの属性間の関係を見つけるために使用されます。一連のトランザクションの相関ルールA => Bは、「最小のサポートと信頼が満たされる条件下で、アイテムセットAの値によってアイテムセットBの値が決定される」という形式になります。

サポートと信頼は、次の例で表すことができます。

上記のステートメントは、相関ルールの例です。これは、パンとバターを一緒に購入したトランザクションが2％あり、パンとバターを一緒に購入した顧客の60％がいることを意味します。

アイテムセットAとBのサポートと信頼性は、次の式で表されます。

アソシエーションルールマイニングは、次の2つのステップで構成されます。

1. よくあるアイテムセットをすべて見つけます。
2. 上記の頻繁なアイテムセットからアソシエーションルールを生成します。

なぜ頻繁なアイテムセットマイニング？

頻繁なアイテムセットまたはパターンマイニングは、マイニング相関ルール、相関、および頻繁なパターン、シーケンシャルパターン、およびその他の多くのデータマイニングタスクに基づくグラフパターン制約に幅広く適用されるため、広く使用されています。

Aprioriアルゴリズム– 頻繁なパターンアルゴリズム

Aprioriアルゴリズムは、頻繁なアイテムセットマイニングのために提案された最初のアルゴリズムでした。その後、RAgarwalとRSrikantによって改良され、Aprioriとして知られるようになりました。このアルゴリズムは、「結合」と「プルーニング」の2つのステップを使用して、検索スペースを削減します。これは、最も頻繁なアイテムセットを見つけるための反復的なアプローチです。

アプリオリは言う：

アイテムIが頻繁に発生しない確率は、次の場合です。

• P（I）
• P（I + A）
• アイテムセットセットの値が最小サポートよりも小さい場合、そのすべてのスーパーセットも最小サポートを下回るため、無視できます。このプロパティは、Antimonotoneプロパティと呼ばれます。

データマイニングのAprioriアルゴリズムで実行される手順は次のとおりです。

1. ステップに参加 ：このステップでは、各アイテムをそれ自体と結合することにより、Kアイテムセットから（K + 1）アイテムセットを生成します。
2. プルーンステップ ：このステップでは、データベース内の各アイテムの数をスキャンします。候補アイテムが最小サポートを満たしていない場合、そのアイテムはまれであると見なされるため、削除されます。このステップは、候補アイテムセットのサイズを縮小するために実行されます。

アプリオリのステップ

Aprioriアルゴリズムは、特定のデータベースで最も頻度の高いアイテムセットを見つけるために従うべき一連の手順です。このデータマイニング手法は、最も頻繁なアイテムセットが達成されるまで、結合とプルーニングのステップを繰り返し実行します。最小サポートしきい値が問題に指定されているか、ユーザーが想定しています。

＃1） アルゴリズムの最初の反復では、各アイテムが1アイテムセットの候補として扱われます。アルゴリズムは、各アイテムの出現をカウントします。

＃二） min_sup（2など）という最小限のサポートがあるとします。 1のセット–発生が最小supを満たすアイテムセットが決定されます。 min_sup以上をカウントする候補のみが次の反復に先取りされ、他の候補は枝刈りされます。

＃3） 次に、min_supを持つ2アイテムセットの頻繁なアイテムが検出されます。このため、結合ステップでは、アイテムをそれ自体と組み合わせて2つのグループを形成することにより、2アイテムセットが生成されます。

＃4） 2項目セットの候補は、min-supしきい値を使用して枝刈りされます。これで、テーブルにはmin-supのみの2つのアイテムセットが含まれます。

＃5） 次の反復では、結合およびプルーニングステップを使用して3つのアイテムセットが形成されます。この反復は、3アイテムセットのサブセット、つまり各グループの2アイテムセットサブセットがmin_supに含まれるアンチモノトーンプロパティに従います。すべての2項目セットのサブセットが頻繁である場合、スーパーセットは頻繁になります。そうでない場合は、プルーニングされます。

＃6） 次のステップでは、3-itemsetをそれ自体と結合し、そのサブセットがmin_sup基準を満たさない場合はプルーニングすることにより、4-itemsetを作成します。最も頻繁なアイテムセットが達成されると、アルゴリズムは停止します。

(画像 ソース )

アプリオリの例：サポートしきい値= 50％、信頼度= 60％

表1

解決：

サポートしきい値= 50％=> 0.5 * 6 = 3 => min_sup = 3

1.各アイテムの数

表-2

2.2。 プルーンステップ： 表-2 は、I5アイテムがmin_sup = 3を満たしていないため、削除され、I1、I2、I3、I4のみがmin_supカウントを満たしていることを示しています。

表-3

3.3。 参加ステップ： フォーム2-アイテムセット。から 表1 2アイテムセットの出現を見つけます。

表-4

四。 プルーンステップ： 表-4 は、アイテムセット{I1、I4}および{I3、I4}がmin_supに適合しないため、削除されることを示しています。

表-5

5.5。 ステップに参加して整理する： フォーム3-アイテムセット。から 表1 3-itemsetの発生を見つけます。から 表-5 、min_supをサポートする2項目セットのサブセットを見つけます。

アイテムセット{I1、I2、I3}サブセット、{I1、I2}、{I1、I3}、{I2、I3}が発生していることがわかります。 表-5 したがって、{I1、I2、I3}が頻繁に発生します。

アイテムセット{I1、I2、I4}サブセットについては、{I1、I2}、{I1、I4}、{I2、I4}、{I1、I4}は頻繁ではないため、 表-5 したがって、{I1、I2、I4}は頻繁ではないため、削除されます。

Windows10でjarファイルを開く

表-6

{I1、I2、I3}のみが頻繁に発生します 。

6.アソシエーションルールを生成します。 上記で発見された頻繁なアイテムセットから、関連付けは次のようになります。

{I1、I2} => {I3}

信頼度=サポート{I1、I2、I3} /サポート{I1、I2} =（3/4）* 100 = 75％

{I1、I3} => {I2}

信頼度=サポート{I1、I2、I3} /サポート{I1、I3} =（3/3）* 100 = 100％

{I2、I3} => {I1}

信頼度=サポート{I1、I2、I3} /サポート{I2、I3} =（3/4）* 100 = 75％

{I1} => {I2、I3}

信頼度=サポート{I1、I2、I3} /サポート{I1} =（3/4）* 100 = 75％

{I2} => {I1、I3}

信頼度=サポート{I1、I2、I3} /サポート{I2 =（3/5）* 100 = 60％

{I3} => {I1、I2}

信頼度=サポート{I1、I2、I3} /サポート{I3} =（3/4）* 100 = 75％

これは、最小信頼しきい値が60％の場合、上記のすべての相関ルールが強力であることを示しています。

Aprioriアルゴリズム：擬似コード

C：サイズkの候補アイテムセット

L：サイズkの頻繁なアイテムセット

(画像 ソース )

利点

1. わかりやすいアルゴリズム
2. 結合とプルーニングの手順は、大規模なデータベースの大規模なアイテムセットに簡単に実装できます。

短所

1. アイテムセットが非常に大きく、最小サポートが非常に低く保たれている場合は、高い計算が必要です。
2. データベース全体をスキャンする必要があります。

アプリオリの効率を改善する方法

アルゴリズムの効率を改善するために多くの方法が利用可能です。

1. ハッシュベースの手法： このメソッドは、ハッシュテーブルと呼ばれるハッシュベースの構造を使用して、kアイテムセットとそれに対応するカウントを生成します。テーブルを生成するためにハッシュ関数を使用します。
2. トランザクションの削減： この方法により、反復でスキャンするトランザクションの数が減ります。頻繁なアイテムを含まないトランザクションは、マークまたは削除されます。
3. パーティショニング： この方法では、頻繁なアイテムセットをマイニングするために2回のデータベーススキャンのみが必要です。アイテムセットがデータベースで頻繁に発生する可能性があるためには、データベースのパーティションの少なくとも1つで頻繁に発生する必要があることを示しています。
4. サンプリング： このメソッドは、データベースDからランダムサンプルSを選択し、Sで頻繁なアイテムセットを検索します。グローバルな頻繁なアイテムセットを失う可能性があります。これは、min_supを下げることで減らすことができます。
5. 動的アイテムセットカウント： この手法では、データベースのスキャン中に、データベースのマークされた開始点に新しい候補アイテムセットを追加できます。

Aprioriアルゴリズムのアプリケーション

Aprioriが使用されるいくつかのフィールド：

1. 教育分野： 特性と専門分野を通じて、入学した学生のデータマイニングにおける相関ルールを抽出します。
2. 医療分野： たとえば、患者のデータベースの分析。
3. 林業： 森林火災データによる森林火災の確率と強度の分析。
4. AprioriはAmazonのような多くの企業で使用されています レコメンダーシステム オートコンプリート機能についてはGoogleによる。

結論

Aprioriアルゴリズムは、データベースを1回だけスキャンする効率的なアルゴリズムです。

データベース内のアイテムセットのサイズを大幅に削減し、優れたパフォーマンスを提供します。したがって、データマイニングは、消費者と業界が意思決定プロセスを改善するのに役立ちます。

Frequent Pattern Growth Algorithmの詳細については、今後のチュートリアルをご覧ください。

前のチュートリアル | 次のチュートリアル

推奨読書

• データマイニング技術：アルゴリズム、方法、トップデータマイニングツール
• データマイニング：データ分析におけるプロセス、技術、および主要な問題
• データマイニングの例：データマイニング2021の最も一般的なアプリケーション
• データマイニングにおける決定木アルゴリズムの例
• データマイニングプロセス：モデル、プロセスステップ、および関連する課題
• データマイニングvs機械学習vs人工知能vsディープラーニング
• トップ15の最高の無料データマイニングツール：最も包括的なリスト
• ユーザー定義変数を使用したJMeterデータのパラメーター化