Python의 FP-Growth 알고리즘에 대한 자세한 설명

FP-Growth 알고리즘은 고전적인 빈발 패턴 마이닝 알고리즘으로, 데이터 세트에서 자주 함께 나타나는 항목의 컬렉션을 마이닝하는 데 매우 효율적인 알고리즘입니다. 이번 글에서는 FP-Growth 알고리즘의 원리와 구현 방법을 자세히 소개하겠습니다.

1. FP-Growth 알고리즘의 기본 원리

FP-Growth 알고리즘의 기본 아이디어는 데이터 세트의 빈발 항목 집합을 표현하기 위한 FP-Tree(빈번 항목 집합 트리)를 구축하고, 빈발 항목을 마이닝하는 것입니다. FP-Tree 세트에서. FP-Tree는 후보 빈발항목집합을 생성하지 않고도 빈발항목집합을 마이닝할 수 있는 효율적인 자료구조이다.

FP-Tree에는 루트 노드와 트리 노드라는 두 부분이 있습니다. 루트 노드에는 값이 없지만 트리 노드에는 항목 이름과 항목 발생 횟수가 포함됩니다. FP-Tree에는 동일한 노드를 가리키는 링크도 포함되어 있으며 이러한 링크를 "링크 포인터"라고 합니다.

FP-Growth 알고리즘의 프로세스는 두 부분으로 구성됩니다: FP-Tree 구축 및 빈발 항목 집합 채굴:

1. FP-Tree 구축:

각 거래에 대해 비빈번 항목을 삭제하고 지원에 따라 빈도를 계산합니다. 빈번한 항목의 크기별로 정렬하여 빈번한 항목 집합을 가져옵니다.

각 트랜잭션을 탐색하여 각 트랜잭션의 빈발 항목 집합을 나타나는 순서대로 FP-Tree에 삽입합니다. 이미 노드가 있으면 개수를 늘립니다.

2. 빈발 항목 집합 마이닝:

FP-Tree에서 빈발 항목 집합을 마이닝하는 방법은 다음과 같습니다.

FP-Tree의 맨 아래에서 시작하여 각 항목 집합의 조건 패턴 라이브러리를 찾습니다. 이 항목 집합을 포함하는 거래입니다. 이후 조건부 패턴 라이브러리에 대해 새로운 FP-Tree를 재귀적으로 구축하고 트리 내 빈발항목집합을 검색한다.

새로운 FP-Tree에서는 각 빈번 항목을 지지도에 따라 정렬하고 후보 집합을 구성한 후 재귀적으로 채굴합니다. 빈발항목집합을 모두 찾을 때까지 위 과정을 반복합니다.

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

그 중 create_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 중국어 웹사이트의 기타 관련 기사를 참조하세요!