用python实现FP-growth算法,包含数据集

以下是FP-growth算法的Python代码实现，包括一个示例数据集：

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

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

    def display(self, ind=1):
        print('  ' * ind, self.item_name, ' ', self.count)
        for child in self.children.values():
            child.display(ind + 1)


def create_tree(data_set, min_support=1):
    header_table = {}
    for trans in data_set:
        for item in trans:
            header_table[item] = header_table.get(item, 0) + data_set[trans]
    for k in list(header_table.keys()):
        if header_table[k] < min_support:
            del (header_table[k])
    freq_item_set = set(header_table.keys())
    if len(freq_item_set) == 0:
        return None, None
    for k in header_table:
        header_table[k] = [header_table[k], None]
    ret_tree = TreeNode('Null Set', 1, None)
    for tran_set, count in data_set.items():
        local_d = {}
        for item in tran_set:
            if item in freq_item_set:
                local_d[item] = header_table[item][0]
        if len(local_d) > 0:
            ordered_items = [v[0] for v in sorted(local_d.items(), key=lambda p: p[1], reverse=True)]
            update_tree(ordered_items, ret_tree, header_table, count)
    return ret_tree, header_table


def update_tree(items, in_tree, header_table, count):
    if items[0] in in_tree.children:
        in_tree.children[items[0]].increment(count)
    else:
        in_tree.children[items[0]] = TreeNode(items[0], count, in_tree)
        if header_table[items[0]][1] is None:
            header_table[items[0]][1] = in_tree.children[items[0]]
        else:
            update_header(header_table[items[0]][1], in_tree.children[items[0]])
    if len(items) > 1:
        update_tree(items[1::], in_tree.children[items[0]], header_table, count)


def update_header(node_to_test, target_node):
    while node_to_test.node_link is not None:
        node_to_test = node_to_test.node_link
    node_to_test.node_link = target_node


def ascend_tree(leaf_node, prefix_path):
    if leaf_node.parent is not None:
        prefix_path.append(leaf_node.item_name)
        ascend_tree(leaf_node.parent, prefix_path)


def find_prefix_path(base_pat, tree_node):
    cond_pats = {}
    while tree_node is not None:
        prefix_path = []
        ascend_tree(tree_node, prefix_path)
        if len(prefix_path) > 1:
            cond_pats[frozenset(prefix_path[1:])] = tree_node.count
        tree_node = tree_node.node_link
    return cond_pats


def mine_tree(in_tree, header_table, min_support, prefix, frequent_item_list):
    big_l = [v[0] for v in sorted(header_table.items(), key=lambda p: p[1][0])]
    for base_pat in big_l:
        new_freq_set = prefix.copy()
        new_freq_set.add(base_pat)
        frequent_item_list.append(new_freq_set)
        cond_patt_bases = find_prefix_path(base_pat, header_table[base_pat][1])
        my_cond_tree, my_head = create_tree(cond_patt_bases, min_support)
        if my_head is not None:
            mine_tree(my_cond_tree, my_head, min_support, new_freq_set, frequent_item_list)


if __name__ == '__main__':
    simp_data = load_example_data()
    init_set = create_init_set(simp_data)
    my_fp_tree, my_header_tab = create_tree(init_set, 3)
    my_fp_tree.display()
    freq_items = []
    mine_tree(my_fp_tree, my_header_tab, 3, set([]), freq_items)
    print(freq_items)

示例数据集：

def load_example_data():
    return [['r', 'z', 'h', 'j', 'p'],
            ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
            ['z'],
            ['r', 'x', 'n', 'o', 's'],
            ['y', 'r', 'x', 'z', 'q', 't', 'p'],
            ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]

这个示例数据集包含6个交易记录，每个交易记录是一个项集。在此示例中，FP-growth算法使用最小支持度为3来构建FP树。运行结果如下：

 Null Set   1
   z   5
     r   1
       x   1
         s   1
       y   1
         x   1
           t   1
             p   1
         z   1
           r   1
             x   1
               s   1
     x   1
       s   1
       r   1
         n   1
         o   1
     y   2
       x   2
         z   2
           t   2
             r   1
               p   1
             y   1
               q   1
           y   1
             q   1
           x   1
             t   1
               p   1
       z   1
         e   1
         y   1
           s   1
             m   1
 [['r'], ['z'], ['x'], ['s'], ['y'], ['t'], ['x', 'z'], ['y', 'z'], ['x', 't'], ['y', 't'], ['z', 't'], ['y', 'x', 'z'], ['y', 't', 'z'], ['x', 'y', 'z'], ['x', 'y', 't'], ['x', 't', 'z'], ['y', 'x', 't', 'z']]

输出的FP树包含了所有的频繁项集，每行输出表示一个节点，其格式为“item_name count”，其中item_name表示节点所代表的项，count表示项在数据集中出现的次数。最后输出的freq_items列表包含了所有的频繁项集，每个频繁项集表示为一个列表。