FP-growth算法：Python实现中的数据输入与输出优化指南

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

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

# 更新FP树
def update_tree(items, node, header_table):
    first_item = items[0]
    if first_item in node.children:
        node.children[first_item].increment(1)
    else:
        new_node = TreeNode(first_item, 1, node)
        node.children[first_item] = new_node

        # 将新节点链接到头指针表中具有相同项名的节点链表
        if not header_table[first_item][1]:
            header_table[first_item][1] = new_node
        else:
            update_header(new_node, header_table[first_item][1])

    if len(items) > 1:
        update_tree(items[1:], node.children[first_item], header_table)

# 更新头指针表中的链接
def update_header(node_to_test, target_node):
    while target_node.link is not None:
        target_node = target_node.link
    target_node.link = node_to_test

# 挖掘频繁项集
def mine_tree(header_table, min_support, prefix, freq_items):
    # 根据频率和项名排序，从底部开始挖掘
    sorted_items = [v[0] for v in sorted(header_table.items(), key=lambda p: (p[1][0], p[0]))]
    for base_pat in sorted_items[::-1]:  
        new_freq_set = prefix.copy()
        new_freq_set.add(base_pat)
        freq_items.append((new_freq_set, header_table[base_pat][0]))

        # 查找前缀路径
        cond_patt_bases = find_prefix_path(base_pat, header_table[base_pat][1])
        # 创建条件FP树
        cond_tree, head = create_tree(cond_patt_bases, min_support)

        if head is not None:
            mine_tree(head, min_support, new_freq_set, freq_items)

# 向上遍历树
def ascend_tree(node, prefix_path):
    if node.parent is not None:
        prefix_path.append(node.name)
        ascend_tree(node.parent, prefix_path)

# 查找前缀路径
def find_prefix_path(base_pat, treeNode):
    cond_pats = {}
    while treeNode is not None:
        prefix_path = []
        ascend_tree(treeNode, prefix_path)
        if len(prefix_path) > 1:
            cond_pats[frozenset(prefix_path[1:])] = treeNode.frequency
        treeNode = treeNode.link
    return cond_pats

# 创建FP-growth树
def create_tree(transactions, min_support):
    header_table = {}
    for transaction in transactions:
        for item in transaction:
            header_table[item] = header_table.get(item, 0) + 1

    # 移除不满足最小支持度的项
    for k in list(header_table):
        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]

    tree_root = TreeNode('Null Set', 1, None)
    for transaction in transactions:
        transaction_filtered = [item for item in transaction if item in freq_item_set]
        # 按照频率降序排序
        transaction_filtered.sort(key=lambda item: header_table[item][0], reverse=True)
        if transaction_filtered:
            update_tree(transaction_filtered, tree_root, header_table)
    return tree_root, header_table

# 从文件加载数据
def load_data(file_path):
    dataset = []
    with open(file_path, 'r') as file:
        for line in file.readlines():
            # 假设每行是一个事务，项之间用逗号分隔
            transaction = line.strip().split(',')  
            dataset.append(transaction)
    return dataset

# 主函数运行FP-growth算法
def fpgrowth():
    file_path = "InputData.txt"  # 指定数据集文件名
    transactions = load_data(file_path)
    min_support = int(input("请输入最小支持度: "))

    # 构建FP-growth树
    tree, header_table = create_tree(transactions, min_support)

    # 发现频繁项集
    freq_items = []
    if tree is not None:
        mine_tree(header_table, min_support, set(), freq_items)

    # 将频繁项集写入输出文件
    output_file_name = "frequent_itemsets.txt"
    with open(output_file_name, 'w') as f:
        # 按照支持度降序排序输出
        for itemset, support in sorted(freq_items, key=lambda i: i[1], reverse=True):
            f.write(f"{', '.join(sorted(list(itemset)))}: {support}\n") # 确保输出格式一致
    print(f"频繁项集已写入到 {output_file_name}")

# 运行FP-growth算法
if __name__ == "__main__":
    fpgrowth()

dataset = [ ['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'], ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'], ['Milk', 'Apple', 'Kidney Beans', 'Eggs'], ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'], ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs'] ]

['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt']
['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt']
...

Milk,Onion,Nutmeg,Kidney Beans,Eggs,Yogurt
Dill,Onion,Nutmeg,Kidney Beans,Eggs,Yogurt
Milk,Apple,Kidney Beans,Eggs
Milk,Unicorn,Corn,Kidney Beans,Yogurt
Corn,Onion,Onion,Kidney Beans,Ice cream,Eggs

# 将频繁项集写入输出文件
output_file_name = "frequent_itemsets.txt"
with open(output_file_name, 'w') as f:
    # 按照支持度降序排序输出
    for itemset, support in sorted(freq_items, key=lambda i: i[1], reverse=True):
        # 对itemset中的项进行排序，以确保输出格式一致性
        f.write(f"{', '.join(sorted(list(itemset)))}: {support}\n") 
print(f"频繁项集已写入到 {output_file_name}")