PythonによるFP-Growthアルゴリズムの詳細説明

FP-Growth アルゴリズムは、古典的な頻出パターン マイニング アルゴリズムであり、データ セットから頻繁に一緒に出現する項目のコレクションをマイニングするための非常に効率的なアルゴリズムです。この記事ではFP-Growthアルゴリズムの原理と実装方法について詳しく紹介します。

1. FP-Growth アルゴリズムの基本原理

FP-Growth アルゴリズムの基本的な考え方は、頻繁に使用されるアイテムセットを表す FP ツリー (頻繁に使用されるアイテムセット ツリー) を確立することです。データ セット、および FP-Tree からの頻繁なアイテムセットのマイニング。 FP-Tree は、頻繁に使用されるアイテムセットの候補を生成せずに、頻繁に使用されるアイテムセットをマイニングできる効率的なデータ構造です。

FP-Tree には、ルート ノードとツリー ノードの 2 つの部分が含まれています。ルート ノードには値がありませんが、ツリー ノードには項目の名前とその項目の出現回数が含まれます。 FP-Tree には同じノードを指すリンクも含まれており、これらのリンクは「リンク ポインタ」と呼ばれます。

FP-Growth アルゴリズムのプロセスには 2 つの部分が含まれます: FP ツリーの構築と頻繁なアイテムセットのマイニング:

1. FP ツリーの構築:

Forトランザクションごとに、頻度の低い項目が削除され、頻度の高い項目のサポートに従って並べ替えられ、頻度の高い項目セットが取得されます。

各トランザクションを走査し、各トランザクションの頻繁な項目セットを出現順に FP ツリーに挿入します。ノードがすでに存在する場合は、その数を増やします。存在しない場合は、新しいノードを挿入します。 。

2. 頻繁に使用されるアイテムセットのマイニング:

FP-Tree から頻繁に使用されるアイテムセットをマイニングする方法は次のとおりです:

FP-Tree の一番下から開始して、各項目セットの条件付きパターン ライブラリ。条件付きパターン ライブラリには、その項目セットを含むすべてのトランザクションが含まれます。次に、条件付きパターン ライブラリに対して新しい FP ツリーが再帰的に構築され、ツリー内の頻出項目セットが検索されます。

新しい FP ツリーでは、各頻繁に使用される項目がそのサポートに従って並べ替えられ、候補のセットが構築され、再帰的にマイニングされます。頻度の高い項目セットがすべて見つかるまで、上記のプロセスを繰り返します。

2. FP-Growth アルゴリズムの実装

FP-Growth アルゴリズムは、Python プログラミング言語を使用して実装できます。以下は、FP-Growth アルゴリズムの実装を示す簡単な例です。

最初に、データ セットを定義します (例:

dataset = [['v', 'a', 'p', 'e', 's'],
           ['b', 'a', 'k', 'e'],
           ['a', 'p', 'p', 'l', 'e', 's'],
           ['d', 'i', 'n', 'n', 'e', 'r']]

)。次に、順序付きアイテム セットを生成する関数を作成します (例:

def create_ordered_items(dataset):
    # 遍历数据集，统计每个项出现的次数
    item_dict = {}
    for trans in dataset:
        for item in trans:
            if item not in item_dict:
                item_dict[item] = 1
            else:
                item_dict[item] += 1

    # 生成有序项集
    ordered_items = [v[0] for v in sorted(item_dict.items(), key=lambda x: x[1], reverse=True)]
    return ordered_items

)。関数は、項目の出現数によって順序付けされた項目セットを取得するために使用されます。

次に、FP-Tree を構築する関数を作成します。

class TreeNode:
    def __init__(self, name, count, parent):
        self.name = name
        self.count = count
        self.parent = parent
        self.children = {}
        self.node_link = None

    def increase_count(self, count):
        self.count += count

def create_tree(dataset, min_support):
    # 生成有序项集
    ordered_items = create_ordered_items(dataset)

    # 建立根节点
    root_node = TreeNode('Null Set', 0, None)

    # 建立FP-Tree
    head_table = {}
    for trans in dataset:
        # 过滤非频繁项
        filtered_items = [item for item in trans if item in ordered_items]
        # 对每个事务中的项集按频繁项的支持度从大到小排序
        filtered_items.sort(key=lambda x: ordered_items.index(x))
        # 插入到FP-Tree中
        insert_tree(filtered_items, root_node, head_table)

    return root_node, head_table

def insert_tree(items, node, head_table):
    if items[0] in node.children:
        # 如果节点已存在，则增加其计数
        node.children[items[0]].increase_count(1)
    else:
        # 如果节点不存在，则插入新的节点
        new_node = TreeNode(items[0], 1, node)
        node.children[items[0]] = new_node
        # 更新链表中的指针
        if head_table.get(items[0], None) is None:
            head_table[items[0]] = new_node
        else:
            current_node = head_table[items[0]]
            while current_node.node_link is not None:
                current_node = current_node.node_link
            current_node.node_link = new_node

    if len(items) > 1:
        # 对剩余的项进行插入
        insert_tree(items[1:], node.children[items[0]], head_table)

create_tree 関数は、FP-Tree を構築するために使用されます。

最後に、頻繁に使用されるアイテムセットをマイニングする関数を作成します。

def find_freq_items(head_table, prefix, freq_items, min_support):
    # 对头指针表中的每个项按照出现的次数从小到大排序
    sorted_items = [v[0] for v in sorted(head_table.items(), key=lambda x: x[1].count)]
    for item in sorted_items:
        # 将前缀加上该项，得到新的频繁项
        freq_set = prefix + [item]
        freq_count = head_table[item].count
        freq_items.append((freq_set, freq_count))
        # 构建该项的条件模式库
        cond_pat_base = get_cond_pat_base(head_table[item])
        # 递归地构建新的FP-Tree，并寻找频繁项集
        sub_head_table, sub_freq_items = create_tree(cond_pat_base, min_support)
        if sub_head_table is not None:
            find_freq_items(sub_head_table, freq_set, freq_items, min_support)

def get_cond_pat_base(tree_node):
    cond_pat_base = []
    while tree_node is not None:
        trans = []
        curr = tree_node.parent
        while curr.parent is not None:
            trans.append(curr.name)
            curr = curr.parent
        cond_pat_base.append(trans)
        tree_node = tree_node.node_link
    return cond_pat_base

def mine_fp_tree(dataset, min_support):
    freq_items = []
    # 构建FP-Tree
    root_node, head_table = create_tree(dataset, min_support)
    # 挖掘频繁项集
    find_freq_items(head_table, [], freq_items, min_support)
    return freq_items

mine_fp_tree 関数は、頻繁に使用されるアイテムセットをマイニングするために使用されます。

3. まとめ

FP-Growthアルゴリズムは効率的な頻出パターンマイニングアルゴリズムであり、FP-Treeを構築することで頻出項目集合の候補を生成することなく頻出項目をマイニングすることができます。 Python は、FP-Growth アルゴリズムの実装に非常に適したプログラミング言語です。Python を使用すると、このアルゴリズムを迅速に実装し、頻繁に使用されるアイテムセットをマイニングするために実際に使用できます。この記事が、FP-Growth アルゴリズムの原理と実装方法をより深く理解するのに役立つことを願っています。

以上がPythonによるFP-Growthアルゴリズムの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。