FP-Growth

概要

この演算子は、FPツリーデータ構造を使用して、ExampleSetで頻繁に発生するすべてのアイテムセットを効率的に計算します。

詳細

オンラインショッピングの際に、次のフォームが提案される場合があります。「商品Xを購入したお客様は商品Yも購入しました。」この提案は、関連付けルールの例です。それを引き出すには、まず、市場のどのアイテムが顧客の買い物かごで最も頻繁に発生するかを知る必要があります。ここで、FP-Growthアルゴリズムが果たす役割があります。

FP-Growthアルゴリズムは、トランザクションデータベースで頻繁に発生するアイテムを計算するための効率的なアルゴリズムです。どのように機能するかを理解するために、顧客のトランザクションを例として使用して、いくつかの用語から始めましょう。

item-市場で販売されているオブジェクト
バスケット-顧客が選択した1つ以上のアイテムのコンテナ
アイテムセット-同じ買い物かごで一緒に販売されるアイテムのサブセット
トランザクション-購入時の個々の買い物かご内のアイテムの完全なセット
トランザクションデータベース-商人が記録したショッピングバスケット/トランザクションの完全なセット

ここでは、「バスケット」と「トランザクション」という言葉が交互に使用されています。これは、購入したアイテムで顧客の買い物かごを識別するためです。これらの定義を具体的にするには、次のトランザクションデータベースを検討してください。

transaction1 =（product1、product2、product7）
transaction2 =（product2、product5、product7）
transaction3 =（product6、product7、product8、product9）
transaction4 =（product1、product3、product4、product6、product7）

9つの異なるアイテムが販売されており、アイテムの数が異なる4つのバスケット/トランザクションがあります。最も頻繁に表示される商品product7は、トランザクションデータベースに4回表示されます。次の各項目セットは2回発生します：（product1、product7）、（product2、product7）、（product6、product7）。

FPツリーデータ構造を効率的に作成し、多くの場合、大規模なデータベースでさえメインメモリに収まるほどデータを圧縮できます。上記の例では、FPツリーに最も頻繁に発生する製品であるproduct7がルートの隣にあり、product7からproduct1、product2、およびproduct6への分岐があります。製品がトランザクションデータベースに複数回表示される必要があると主張する場合、残りの製品はFPツリーから除外されます。トランザクションデータベースは、多くのゼロエントリを持つ4 x 9（トランザクションx製品）データテーブルとして開始された可能性がありますが、関連する頻度データのみをキャプチャするミニマルなツリーに縮小されました。

効率的なツリー構造でも、アルゴリズムで考慮されるアイテムセットの数は非常に大きくなる可能性があります。パラメータmax number of itemsetsを使用すると、必要に応じてランタイムとメモリを削減できます。

オンラインショッピングは単なる例であることを忘れないでください。 FP-Growthアルゴリズムは、アイテム、アイテムセット、バスケット/トランザクションの観点から定式化できる問題に適用できます。アルゴリズムの一般的な設定は、大規模なトランザクションデータベース（多数のバスケット）で、各バスケットには少数のアイテムのみがあり、すべてのアイテムのセットに比べて小さいです。

support =（データベースにアイテムまたはアイテムセットが表示される回数）/（データベース内のバスケットの数）

一般に、「最小サポート」の概念はカットオフを作成し、アイテムセットの頻繁な発生またはそれほど頻繁ではない発生が意味するものを定義します。アイテムまたはアイテムセットが少数のバスケットにのみ表示される場合、パラメータmin supportまたはmin frequencyを介して除外されます。まれにしか発生しないアイテムおよびアイテムセットを除外すると、データの圧縮に役立ち、結果の統計的有意性が向上します。一方、 最小サポートまたは最小頻度の値が高すぎると、アルゴリズムはゼロのアイテムセットを見つける可能性があります。したがって、このオペレーターは、アイテムセットの最小数を見つけるチェックボックスを介して、2つの主要なモードを提供します：

1.オフの場合、最小サポート値が固定され、

2.結果に最小数のアイテムセットが含まれることを確認するために、動的な最小サポート値でチェックした場合。

FP-Growthは、入力データに対していくつかの異なる形式をサポートしています。次の要件に注意してください。

ExampleSetでは、1つのトランザクション= 1つの行。列の説明については、以下を参照してください。
すべてのアイテムの値は公称値でなければなりません
トランザクションIDはオプションであり、存在する場合は、アイテムとして識別されないように「id」ロールを持つ必要があります。

列については、2つの使用可能な入力形式が、必要な前処理とともに2番目のチュートリアルに示されています。概要は次のとおりです。

列のアイテムリスト：トランザクションに属するすべてのアイテムは、CSVのような形式で、アイテムの区切り文字で区切られた単一の列に表示されます。 CSVファイルと同様に、アイテムは引用符で囲むことができ、エスケープ文字を使用できます。アイテム名をトリムできます。
個別の列のアイテム：トランザクションに属するすべてのアイテムは個別の列に表示されます。各トランザクションでは、最初のアイテム名が最初の列に表示され、2番目のアイテム名が2番目の列に表示されます。列の数は、最大アイテム数のバスケットに対応します。欠損値はアイテムがないことを示します。アイテム名をトリムできます。
ダミーのコード化列のアイテム：すべてのアイテムのセット内のすべてのアイテムには独自の列があり、アイテム名は列名です。トランザクションごとに、二項値（true / false）は、アイテムがバスケットで見つかるかどうかを示します。データが二項ですが、値がtrue / falseとして識別されない場合、正の値パラメーターを設定する必要があります。

入力

example set （IOObject）この入力ポートには、ExampleSetが必要です。説明で詳細に説明したように、このオペレーターは入力データのいくつかの異なる形式をサポートしています。

出力

example set（IOObject）入力として与えられたExampleSetは、変更なしでパススルーされます。
frequent sets（頻出品目セット）頻繁に発生するアイテムセットは、このポートを介して配信されます。アソシエーションルールの作成などのオペレータは、これらの頻繁に発生するアイテムセットを使用してアソシエーションルールを生成できます。

パラメーター

input_format例については、2番目のチュートリアルを参照してください。説明で詳細に説明したように、このオペレーターは入力データのいくつかの異なる形式をサポートしています。
- item list in a column：トランザクションに属するすべてのアイテムは、CSVのような形式で、アイテムの区切り文字で区切られた単一の列に表示されます。
- items in separate columns：トランザクションに属するすべてのアイテムは別々の列に表示され、最初のアイテム名が最初の列に表示され、2番目のアイテム名が2番目の列に表示されます。
- tems in dummy coded columns:すべてのアイテムのセット内のすべてのアイテムには独自の列があり、アイテム名は列名です。トランザクションごとに、二項値（true / false）は、アイテムがバスケットで見つかるかどうかを示します。
範囲：
item_separatorsこのパラメーターは、アイテムの区切りを定義します。正規表現として提供することもできます。範囲：
use_quotesこのパラメーターをチェックして、 引用符文字を定義します。 CSVファイルの場合と同様に、アイテム名にアイテム区切り記号が含まれる可能性がある場合は、混乱を避けるために引用符を使用できます。たとえば、（、）がアイテムセパレータで、（ “）が引用符文字である場合、行（a、b、c、d）は4つのアイテムとして解釈されます。一方、（” a、b、c 、d “）は、値a、b、c、dを持つ単一のアイテムとして解釈されます。範囲：
quotes_characterこのパラメーターは引用符文字を定義し、 引用符を 使用がチェックされている場合にのみ使用可能です。範囲：
trim_item_names、 引用符文字または項目区切り文字をエスケープするために使用されるエスケープ文字を定義します。たとえば、（ “）が引用符文字であり、（ ‘\’）がエスケープ文字である場合、（” yes “）は（yes）として解釈され、（\” yes \ “）は（” yes “）として解釈されます。（ ‘|’）が項目区切り記号であり、（ ‘\’）がエスケープ文字である場合、行（a \ | b | c）は2つの項目（a | b）および（c）として解釈されます。範囲：
trim_item_namesこのパラメーターをオンにすると、アイテム名の先頭と末尾の空白が削除されます。範囲：
positive_value二項属性を持つダミーのコード化された列のアイテムの場合、このパラメーターは、どの値を正として扱う必要があるか、したがってどのアイテムがトランザクションに属するかを決定します。このパラメーターを空白のままにすると、正の値はExampleSetから推測されます。範囲：
min_requirementこのパラメーターは、カットオフを定義するために2つの異なる方法を使用可能にし、まれに発生するアイテムセットを排除します。
- support：サポートの最小値（ExampleSetサイズに対するオカレンスの比率）
- 頻度：最小頻度（発生回数）
範囲：
min_support最小サポート=（アイテムセットの出現回数）/（ExampleSetのサイズ）結果の項目セットの数を増やすには、この値を減らします。範囲：
min_frequency最小頻度=アイテムセットの出現回数結果の項目セットの数を増やすには、この値を減らします。範囲：
min_items_per_itemsetアイテムセットのサイズの下限。範囲：
max_items_per_itemsetアイテムセットのサイズの上限（0：上限なし）。範囲：
max_number_of_itemsetsアイテムセット数の上限（0：上限なし）。メモリが不足している場合は、この値を減らすか、 min supportまたはmin frequencyの値を増やします。範囲：
find_min_number_of_itemsetsこのパラメーターがチェックされている場合、結果には少なくとも最小数のitemsetsが含まれます。最小サポート値は、アイテムセットの最小数が見つかるまで自動的に減少します。範囲：
min_number_of_itemsetsこのパラメーターは、最小セット数のアイテムセットを検索する場合にのみ使用できます。このパラメーターは、結果に含める必要があるアイテムセットの最小数を指定します。範囲：
max_number_of_retriesこのパラメーターは、最小セット数のアイテムセットを検索する場合にのみ使用できます。最小サポート/最小頻度の値を自動的に減らす場合、このパラメーターは、オペレーターが断念するまでに値を減らすことができる回数を決定します。より多くの結果を得るには、この数を増やします。範囲：
requirements_decrease_factorこのパラメーターは、最小セット数のアイテムセットを検索する場合にのみ使用できます。最小サポート/最小頻度の値を自動的に減少させるとき、この乗法因子は新しいカットオフ値を決定します。値を小さくすると、必要な数のアイテムセットを見つけるための手順が少なくなります。範囲：
must_contain_listこのパラメーターは、正確なアイテム名のリストを使用して、頻繁に発生するアイテムセットに含める必要があるアイテムを指定します（存在する場合）。範囲：
must_contain_regexpこのパラメーターは、頻繁に発生するアイテムセット（存在する場合）に正規表現を介して含める必要があるアイテムを指定します。範囲：

チュートリアルプロセス

FP-Growthオペレーターの紹介

このプロセスは、マーケットバスケット分析を示しています。トランザクションを含むデータセットは、Retrieve Operatorを使用してロードされます。 ExampleSetを表示できるように、ブレークポイントがここに挿入されます。 ExampleSetを受け入れ可能な入力形式に成形するには、Aggregate Operatorを使用していくつかの前処理を行う必要があります。入力データを表示できるように、FP-Growth演算子の前にブレークポイントが挿入されます。 FP-Growth Operatorは、頻繁なアイテムセットを生成するために適用されます。最後に、Create Association Rules Operatorを使用して、頻繁なアイテムセットからルールを作成します。頻繁なアイテムセットと関連付けルールは、結果ビューで表示できます。この演算子の理解を深めるために、パラメータの異なる値でこのプロセスを実行します。

FP-Growth Operatorの入力形式データがロードされ、3つの異なる入力形式に変換されます。これらの各形式の入力データを表示できるように、FP-Growth Operatorsの前にブレークポイントが挿入されます。 FP-Growth演算子が使用され、結果のアイテムセットは結果ビューで表示できます。フォーマットは異なりますが、入力データは同じであるため、結果はすべて同じです。