FPツリーの表現は何ですか？

FPツリーは、入力データの確実な記述です。これは、一度に1つのトランザクションでデータセットを読み取り、FPツリー内のルートで各トランザクションを測定することによって組み立てられます。複数のトランザクションに複数のアイテムが共通している可能性があり、それらのルートは重複している可能性があります。

ルートが互いにオーバーラップするほど、FPツリーアーキテクチャを使用してより多くの圧縮を実装できます。 FPツリーのサイズがメインメモリに収まるのに十分な場合、これにより、ディスクに保存されたデータに対して繰り返しパスを作成するのではなく、メモリ内のアーキテクチャから直接頻繁なアイテムセットを抽出できるようになります。

ツリーの各ノードには、アイテムのラベルと、指定されたルートにマップされた複数のトランザクションを表示するカウンターが含まれています。元々、FPツリーにはnulfシンボルで定義されたルートノードのみが含まれています。

FPツリーは次の方法で継続されます-

データセットを1回検索して、各アイテムのサポート数を決定します。頻度の低いアイテムは削除されますが、頻度の高いアイテムはサポート数を減らすために一定です。

アルゴリズムは、データ上に2番目のパスを作成して、FPツリーを作成します。最初のトランザクション{a、b}を確認した後、aおよびbのラベルが付いたノードが生成されます。トランザクションを暗号化するために、null→a→bからパスが形成されます。ルートに沿った各ノードの頻度カウントは1です。

2番目のトランザクション{b、c、d}を確認した後、アイテムb、c、およびdの新しいノードのセットが生成されます。次に、ノードnull→b→c→dをリンクすることにより、トランザクションを定義するルートが形成されます。

このルートに沿った各ノードにも、1と同じ頻度カウントがあります。最初の2つのトランザクションには頻繁なアイテム（b）がありますが、トランザクションが頻繁なプレフィックスを共有していないため、それらのルートは互いに素です。

3番目のトランザクション{a、c、d、e}は、頻繁なプレフィックス項目（a）を最初のトランザクションと共有します。したがって、3番目のトランザクションのルートnull→a→c→d→eは、最初のトランザクションのルートnuII→a→bとオーバーラップします。ルートが重複しているため、ノードoの頻度カウントは2に増加しますが、最近作成されたノードc、d、およびeの頻度カウントは1と同じです。

このフェーズは、各トランザクションがFPツリーで指定されたルートの1つにマップされるまで続きます。マーケットバスケット情報のいくつかのトランザクションがより多くのアイテムを共有するため、FPツリーのサイズは非圧縮データのサイズよりも小さくなります。