frequent pattern growth algorithm data mining
FPツリーの形式でデータベースを表す頻繁なパターン成長アルゴリズムに関する詳細なチュートリアル。 FPの成長とアプリオリの比較が含まれます:
アプリオリアルゴリズム 以前のチュートリアルで詳細に説明されました。このチュートリアルでは、頻繁なパターンの成長について学習します– FPの成長は、頻繁なアイテムセットをマイニングする方法です。
C ++のフレンド関数
ご存知のとおり、Aprioriは、アイテムセットの生成と最も頻繁なアイテムセットの検出に焦点を当てた、頻繁なパターンマイニングのアルゴリズムです。データベース内のアイテムセットのサイズを大幅に削減しますが、Aprioriには独自の欠点もあります。
私たちを読んでください データマイニングトレーニングシリーズ全体 概念の完全な知識のため。
学習内容:
- Aprioriアルゴリズムの欠点
- 頻繁なパターン成長アルゴリズム
- FPツリー
- 頻繁なパターンアルゴリズムの手順
- FP-Growthアルゴリズムの例
- FP成長アルゴリズムの利点
- FP-Growthアルゴリズムのデメリット
- FPの成長とアプリオリ
- 輝く
- 結論
- 推奨読書
Aprioriアルゴリズムの欠点
- Aprioriを使用するには、候補アイテムセットの生成が必要です。データベース内のアイテムセットが巨大な場合、これらのアイテムセットの数が多くなる可能性があります。
- Aprioriは、生成された各アイテムセットのサポートを確認するためにデータベースを複数回スキャンする必要があり、これは高コストにつながります。
これらの欠点は、FP成長アルゴリズムを使用して克服できます。
頻繁なパターン成長アルゴリズム
このアルゴリズムは、Aprioriメソッドを改良したものです。候補を生成しなくても、頻繁なパターンが生成されます。 FP成長アルゴリズムは、データベースを頻度パターンツリーまたはFPツリーと呼ばれるツリーの形式で表します。
このツリー構造は、アイテムセット間の関連付けを維持します。データベースは、1つの頻繁なアイテムを使用して断片化されています。この断片化された部分は「パターン断片」と呼ばれます。これらの断片化されたパターンのアイテムセットが分析されます。したがって、この方法では、頻繁なアイテムセットの検索が比較的少なくなります。
FPツリー
Frequent Pattern Treeは、データベースの最初のアイテムセットで作成されたツリーのような構造です。 FPツリーの目的は、最も頻繁なパターンをマイニングすることです。 FPツリーの各ノードは、アイテムセットのアイテムを表します。
ルートノードはnullを表し、下位ノードはアイテムセットを表します。ツリーを形成している間、他のアイテムセットとのアイテムセットである下位ノードとのノードの関連付けは維持されます。
頻繁なパターンアルゴリズムの手順
頻繁なパターン成長法により、候補を生成せずに頻繁なパターンを見つけることができます。
頻繁なパターン成長アルゴリズムを使用して頻繁なパターンをマイニングするための手順を見てみましょう。
#1) 最初のステップは、データベースをスキャンして、データベース内のアイテムセットの出現を見つけることです。このステップは、Aprioriの最初のステップと同じです。データベース内の1アイテムセットの数は、サポートカウントまたは1アイテムセットの頻度と呼ばれます。
Webアプリケーション用のストレステストツール
#二) 2番目のステップは、FPツリーを構築することです。このために、ツリーのルートを作成します。ルートはnullで表されます。
#3) 次のステップは、データベースを再度スキャンしてトランザクションを調べることです。最初のトランザクションを調べて、その中のアイテムセットを見つけます。最大数のアイテムセットが一番上に、次の数が少ないアイテムセットというように続きます。これは、ツリーのブランチが、カウントの降順でトランザクションアイテムセットを使用して構築されていることを意味します。
#4) データベース内の次のトランザクションが調べられます。アイテムセットは、カウントの降順で並べられています。このトランザクションのアイテムセットが別のブランチ(たとえば、最初のトランザクション)にすでに存在する場合、このトランザクションブランチはルートに共通のプレフィックスを共有します。
これは、共通アイテムセットがこのトランザクションの別のアイテムセットの新しいノードにリンクされていることを意味します。
#5) また、アイテムセットの数は、トランザクションで発生するたびに増加します。共通ノードと新しいノードの数は、トランザクションに従って作成およびリンクされるため、1ずつ増加します。
#6) 次のステップは、作成されたFPツリーをマイニングすることです。このために、最下位ノードのリンクとともに最下位ノードが最初に調べられます。最も低いノードは周波数パターンの長さ1を表します。これから、FPツリーのパスをトラバースします。この1つまたは複数のパスは、条件付きパターンベースと呼ばれます。
条件付きパターンベースは、最下位ノード(サフィックス)で発生するFPツリーのプレフィックスパスで構成されるサブデータベースです。
# 7) パス内のアイテムセットの数によって形成される条件付きFPツリーを構築します。しきい値サポートを満たすアイテムセットは、条件付きFPツリーで考慮されます。
#8) 頻繁なパターンは、条件付きFPツリーから生成されます。
FP-Growthアルゴリズムの例
サポートしきい値= 50%、信頼度= 60%
表1
トランザクション | アイテムのリスト |
---|---|
メモリ使用量 | |
T1 | I1、I2、I3 |
T2 | I2、I3、I4 |
T3 | I4、I5 |
T4 | I1、I2、I4 |
T5 | I1、I2、I3、I5 |
T6 | I1、I2、I3、I4 |
解決:
サポートしきい値= 50%=> 0.5 * 6 = 3 => min_sup = 3
1.各アイテムの数
表2
項目 | カウント |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
I4 | 4 |
I5 | 二 |
2.アイテムセットを降順で並べ替えます。
表3
Javaでjunitテストケースを書く
項目 | カウント |
---|---|
I2 | 5 |
I1 | 4 |
I3 | 4 |
I4 | 4 |
3.FPツリーを構築します
- ルートノードがnullであると見なします。
- トランザクションT1の最初のスキャン:I1、I2、I3には、3つのアイテム{I1:1}、{I2:1}、{I3:1}が含まれます。ここで、I2は子としてルートにリンクされ、I1はI2およびI3にリンクされます。 I1にリンクされています。
- T2:I2、I3、I4にはI2、I3、およびI4が含まれ、I2はルートにリンクされ、I3はI2にリンクされ、I4はI3にリンクされます。ただし、このブランチは、T1ですでに使用されているのと同じくらい共通のI2ノードを共有します。
- I2のカウントを1インクリメントすると、I3は子としてI2にリンクされ、I4は子としてI3にリンクされます。カウントは{I2:2}、{I3:1}、{I4:1}です。
- T3:I4、I5。同様に、子が作成されると、I5の新しいブランチがI4にリンクされます。
- T4:I1、I2、I4。シーケンスはI2、I1、およびI4になります。 I2はすでにルートノードにリンクされているため、1ずつ増加します。同様に、I1はT1のI2と既にリンクされているため、1ずつ増加します。したがって、{I2:3}、{I1:2}、{I4: 1}。
- T5:I1、I2、I3、I5。シーケンスはI2、I1、I3、およびI5になります。したがって、{I2:4}、{I1:3}、{I3:2}、{I5:1}。
- T6:I1、I2、I3、I4。シーケンスはI2、I1、I3、およびI4になります。したがって、{I2:5}、{I1:4}、{I3:3}、{I41}。
4.FPツリーのマイニングを以下に要約します。
- 最下位ノードのアイテムI5は、最小サポートカウントがないため考慮されないため、削除されます。
- 次に低いノードはI4です。 I4は、{I2、I1、I3:、I41}、{I2、I3、I4:1}の2つのブランチで発生します。したがって、I4をサフィックスと見なすと、プレフィックスパスは{I2、I1、I3:1}、{I2、I3:1}になります。これは、条件付きパターンベースを形成します。
- 条件付きパターンベースはトランザクションデータベースと見なされ、FPツリーが構築されます。これには{I2:2、I3:2}が含まれますが、I1は最小サポートカウントを満たしていないため、考慮されません。
- このパスは、頻繁なパターンのすべての組み合わせを生成します:{I2、I4:2}、{I3、I4:2}、{I2、I3、I4:2}
- I3の場合、プレフィックスパスは次のようになります:{I2、I1:3}、{I2:1}、これにより2ノードのFPツリーが生成されます:{I2:4、I1:3}そして頻繁なパターンが生成されます:{I2 、I3:4}、{I1:I3:3}、{I2、I1、I3:3}。
- I1の場合、プレフィックスパスは次のようになります。{I2:4}これにより、単一ノードのFPツリーが生成されます:{I2:4}、頻繁なパターンが生成されます:{I2、I1:4}。
項目 | 条件付きパターンベース | 条件付きFPツリー | 頻繁に生成されるパターン |
---|---|---|---|
I4 | {I2、I1、I3:1}、{I2、I3:1} | {I2:2、I3:2} | {I2、I4:2}、{I3、I4:2}、{I2、I3、I4:2} |
I3 | {I2、I1:3}、{I2:1} | {I2:4、I1:3} | {I2、I3:4}、{I1:I3:3}、{I2、I1、I3:3} |
I1 | {I2:4} | {I2:4} | {I2、I1:4} |
以下の図は、条件付きノードI3に関連付けられた条件付きFPツリーを示しています。
FP成長アルゴリズムの利点
- このアルゴリズムは、反復ごとにトランザクションをスキャンするAprioriと比較した場合、データベースを2回スキャンするだけで済みます。
- このアルゴリズムではアイテムのペアリングは行われないため、高速になります。
- データベースはコンパクトバージョンでメモリに保存されます。
- 長い頻度のパターンと短い頻度のパターンの両方をマイニングするのに効率的でスケーラブルです。
FP-Growthアルゴリズムのデメリット
- FP Treeは、Aprioriよりも作成が面倒で困難です。
- それは高価かもしれません。
- データベースが大きい場合、アルゴリズムが共有メモリに収まらない可能性があります。
FPの成長とアプリオリ
FPの成長 | アプリオリ |
---|---|
パターン生成 | |
FPの成長は、FPツリーを構築することによってパターンを生成します | Aprioriは、アイテムをシングルトン、ペア、トリプレットにペアリングすることでパターンを生成します。 |
候補者の生成 | |
候補世代はありません | Aprioriは候補世代を使用します |
処理する | |
このプロセスは、Aprioriと比較して高速です。プロセスの実行時間は、アイテムセットの数の増加とともに直線的に増加します。 | プロセスはFPGrowthよりも比較的遅く、実行時間はアイテムセットの数の増加とともに指数関数的に増加します |
データベースのコンパクトバージョンが保存されます | 候補の組み合わせはメモリに保存されます |
輝く
上記の方法であるAprioriとFPの成長では、水平データ形式を使用して頻繁なアイテムセットをマイニングします。 ECLATは、垂直データ形式を使用して頻繁なアイテムセットをマイニングする方法です。水平データ形式のデータを垂直形式に変換します。
例えば、AprioriとFPの成長の使用:
トランザクション | アイテムのリスト |
---|---|
T1 | I1、I2、I3 |
T2 | I2、I3、I4 |
T3 | I4、I5 |
T4 | I1、I2、I4 |
T5 | I1、I2、I3、I5 |
T6 | I1、I2、I3、I4 |
ECLATのテーブルの形式は次のとおりです。
項目 | トランザクションセット |
---|---|
I1 | {T1、T4、T5、T6} |
I2 | {T1、T2、T4、T5、T6} |
I3 | {T1、T2、T5、T6} |
I4 | {T2、T3、T4、T5} |
I5 | {T3、T5} |
このメソッドは、垂直データ形式で2アイテムセット、3アイテムセット、kアイテムセットを形成します。 kを使用したこのプロセスは、候補アイテムセットが見つからなくなるまで1ずつ増加します。 diffsetなどのいくつかの最適化手法は、Aprioriとともに使用されます。
この方法は、k + 1アイテムセットのサポートを見つけるためにデータベースをスキャンする必要がないため、Aprioriよりも優れています。これは、トランザクションセットがトランザクション(サポート)内の各アイテムの発生回数を保持するためです。ボトルネックは、セットを交差させるために膨大なメモリと計算時間を必要とする多くのトランザクションがある場合に発生します。
結論
Aprioriアルゴリズムは、マイニングアソシエーションルールに使用されます。これは、「頻繁なアイテムセットの空でないサブセットも頻繁でなければならない」という原則に基づいて機能します。 (k-1)アイテムセットからkアイテムセット候補を形成し、データベースをスキャンして頻繁なアイテムセットを見つけます。
Frequent Pattern Growth Algorithmは、候補を生成せずに頻繁なパターンを見つける方法です。 Aprioriの生成およびテスト戦略を使用するのではなく、FPツリーを構築します。 FP Growthアルゴリズムの焦点は、アイテムのパスを断片化し、頻繁なパターンをマイニングすることです。
データマイニングシリーズのこれらのチュートリアルが、データマイニングに関する知識を深めることを願っています。