学ぶ FP-Growthアルゴリズムによる頻出パターンツリーの構築 | 高性能ルールマイニングとスケール最適化

メニューを表示するにはスワイプしてください

FP-Growthの概要

FP-Growthは、大規模なトランザクションデータセットにおける頻出アイテムセットの抽出に特化した高性能アルゴリズム。Aprioriとは異なり、候補アイテムセットの生成やデータベースの繰り返し走査を行わず、FP-Tree（頻出パターンツリー）と呼ばれるコンパクトなデータ構造を構築し、候補生成なしで頻出パターンを抽出。これにより、多数の頻出パターンを持つデータセットでも、処理速度とメモリ効率が大幅に向上。

ツリー構造

FP-Tree構造は、すべてのトランザクションをプレフィックスツリー形式で圧縮。各トランザクションは、アイテムを出現頻度の降順で並べ替えた後、既存のパスと共通するプレフィックスを共有しながらツリーに挿入。ルートノードはエントリーポイントとなるnullノードであり、ツリー内の各ノードはアイテムと、その時点までにそのプレフィックスを共有するトランザクション数を表すカウントを持つ。

ノードリンク

効率的なマイニングのため、同じアイテムを表すすべてのノードはリンクリストで接続され、ヘッダテーブルを形成。これにより、ツリー内の特定アイテムのすべての出現箇所を迅速にたどることが可能。ヘッダテーブルの各エントリは、そのアイテムの最初のノードを指し、各ノードは同じアイテム名を持つ次のノードへのリンクを保持。

パターンのマイニング

FP-Treeから頻出パターンを抽出するには、主に2つのステップが必要。まず、ヘッダテーブル内の各アイテムについて、リンクをたどりながらツリーを下から上へ走査し、そのアイテムに至るすべてのプレフィックスパスを収集。次に、各アイテムごとに条件付きFP-Treeを構築し、再帰的にマイニングを行い、すべての頻出アイテムセットを抽出。この再帰処理は、これ以上頻出パターンが見つからなくなるまで継続。

例：FP-Tree 構築のステップバイステップ

最小サポート閾値を2（アイテムが少なくとも2回出現する必要がある）と仮定し、例のトランザクションを用いてFP-Tree構築の正確な手順を説明します。

次のようなトランザクションがあるとします：

- トランザクション 1: A, B, D;
- トランザクション 2: B, C, E;
- トランザクション 3: A, B, C, E;
- トランザクション 4: B, E.

ステップ1：データベースのスキャンと頻度順でのソート

まず、アルゴリズムはデータセット全体を読み込み、各アイテムが何回出現するかをカウントします。最小サポート閾値未満のアイテムは除外されます。その後、頻度が高い順にグローバルなソート順が決定されます。

グローバルアイテム出現回数：

B：4回出現

E：3回出現

A：2回出現

C：2回出現

D：1回出現（最小サポート2未満のため除外）

最終的な並び替えルール： すべてのトランザクションは、以下の降順頻度ルールに従ってフィルタリング・並び替えされます：

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

ステップ2：各トランザクションの並び替え

アイテムをツリーに挿入する前に、アルゴリズムは各トランザクションを書き換えます。頻度の低いアイテム（D）を除外し、残りのアイテムを新しいグローバル順序に並び替えます。

- トランザクション 1: A, B, D → B, A
- トランザクション 2: B, C, E → B, E, C
- トランザクション 3: A, B, C, E → B, E, A, C
- トランザクション 4: B, E → B, E

ステップ3：FP-Treeへのパス挿入

すべてのFP-Treeは、Null Root Node（空のルートノード）から始まります。並び替えたトランザクションを1つずつツリーに挿入し、パスが重複する場合はカウンタを増やし、分岐する場合は新しい枝を作成します。

トランザクション1 {B, A} の挿入： ツリーはルートからまっすぐ新しい枝を作成します。

トランザクション2 {B, E, C} の挿入： アルゴリズムはルートからBを確認します。Bはすでにルートの子として存在するため、パスが重複します。Bのカウントを2に増やします。次はEです。Bの子にEがまだないため、ここで分岐しE、続いてCの新しいサブブランチを作成します。

トランザクション3 {B, E, A, C} の挿入： ルートからB（カウント3に増加）、次に既存のEノード（カウント2に増加）へ進みます。次はAです。Eの子にAがないため、Eの下に新しい分岐（A:1）→（C:1）を作成します。

トランザクション4 {B, E} の挿入： アルゴリズムは最も頻出のプレフィックスパスをたどり、Bを4、Eを3に増やします。ここでトランザクションは終了し、新しいノードは追加されません。

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

このコードサンプルは、Pythonを用いてトランザクションリストからFP-Treeを構築する方法を示しています。各ステップの詳細な説明は以下の通りです：

アイテム頻度のカウント：
- collectionsモジュールのCounterクラスを使用し、すべてのトランザクションで各アイテムが何回出現するかをカウントします；
- これにより、ツリーに含めるべき十分に頻出するアイテムを特定します。
頻度の低いアイテムの除外：
- 最小サポート閾値を満たさないアイテムは除外されます；
- セットfreq_itemsには、min_supportで指定された回数以上出現するアイテムのみが含まれます。
トランザクションの頻度順ソート：
- 各トランザクションは頻出アイテムのみを残すようにフィルタリングされます；
- アイテムはグローバル頻度の降順（同じ頻度の場合はアルファベット順）で並び替えられます；
- 並び替えによりFP-Tree内でのプレフィックス共有が最大化され、ツリーがよりコンパクトになります。
FP-Treeノードクラスの定義：
- FPTreeNodeクラスはツリー内の各ノードを表します；
- 各ノードはアイテム名、カウント、親ノードへのポインタ、子ノードの辞書、同じアイテム名を持つ次のノードへのリンク（ヘッダテーブル用）を保持します。
FP-Treeとヘッダテーブルの構築：
- build_fp_tree関数は、各ソート済みトランザクションを挿入してツリーを作成します；
- ルートから始めて、トランザクション内の各アイテムについて子ノードが存在するか確認し、なければ新規作成してヘッダテーブルに追加します；
- 既存ノードがあればカウントを増やします；
- ツリー構築後、link属性を使って同じアイテム名を持つすべてのノードを連結し、ヘッダテーブル経由で高速に走査できるようにします。
FP-Tree構造の表示：
- print_tree関数は、各ノードとそのカウントをインデント付きで再帰的に表示し、ツリー構造を可視化します；
- この出力により、トランザクションがFP-Tree内でどのように共有パスとして圧縮されているかを視覚的に把握できます。

1. 次のうち、FP-GrowthがAprioriアルゴリズムより優れている主な利点はどれですか？

2. FP-Treeノードの構造はどのようになっていますか？

すべて明確でしたか？

フィードバックありがとうございます！

セクション 2. 章 1

AIに質問する

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 2. 章 1