《大数据分析理论与方法：关联分析》

# test.py中的关键预处理代码
def load_dataset(file_path):
    dataset = []
    with open(abs_path, 'r') as f:
        for line in f:
            raw_items = line.strip().split('\t')  # 制表符分割
            transaction = [item.strip() for item in raw_items if item.strip()]
            if transaction:
                dataset.append(transaction)  # 过滤空行
    return dataset

# Apriori.py中的迭代过程
while True:
    # 计算候选项支持度
    candidate_counts = defaultdict(int)
    for transaction in dataset:
        for candidate in single_items:
            if set(candidate).issubset(transaction):
                candidate_counts[tuple(candidate)] += 1
    # 使用defaultdict自动初始化未出现的键，避免KeyError
    # 遍历每个事务，检查候选项是否为事务的子集
    
    # 剪枝：筛选满足min_support的项集
    min_count = min_support * len(dataset)
    freq_k = [list(k) for k,v in candidate_counts.items() if v >= min_count]
    if not freq_k:  # 终止条件：当前层无频繁项集
        break
    
    # 生成下一层候选项（连接+剪枝）
    next_candidates = []
    for i in range(len(freq_k)):
        for j in range(i+1, len(freq_k)):
            combined = sorted(list(set(freq_k[i]+freq_k[j])))  # 合并两个项集
            # 检查合并后项集长度是否为k+1，避免无效扩展
            # 验证所有k项子集是否都在频繁项集中（剪枝步骤）
            if len(combined) == k+1 and all(subset in freq_k for subset in combinations(combined, k)):
                next_candidates.append(combined)
    # 此处通过组合验证确保先验性质成立

# FP_Growth.py中的树构建
def build_fp_tree(dataset, min_support):
    # 第一次扫描统计频次
    item_counts = defaultdict(int)
    for trans in dataset:
        for item in trans:
            item_counts[item] += 1  # 统计所有单项支持度
    
    # 生成头指针表（仅保留频繁项）
    min_count = min_support * len(dataset)
    header_table = {item: [count, None] for item,count in item_counts.items() 
                   if count >= min_count}  # [频次, 链表头指针]
    
    # 若无频繁项，直接返回空树
    if not header_table:
        return None, None
    
    root = TreeNode('Null', 1, None)  # 创建FP树根节点
    
    # 第二次扫描构建树
    for trans in dataset:
        # 过滤非频繁项并按频次降序排序
        filtered = [item for item in trans if item in header_table]
        filtered.sort(key=lambda x: (-header_table[x][0], x))  # 降序保证树压缩效果
        
        current_node = root
        for item in filtered:
            # 插入事务到树中
            if item in current_node.children:
                current_node.children[item].count += 1  # 已有节点则增加计数
            else:
                # 创建新节点并链接到父节点
                new_node = TreeNode(item, 1, current_node)
                current_node.children[item] = new_node
                # 更新头指针链表
                if header_table[item][1] is None:
                    header_table[item][1] = new_node  # 链表头指针指向第一个节点
                else:
                    node = header_table[item][1]
                    while node.link:  # 找到链表末尾
                        node = node.link
                    node.link = new_node  # 将新节点追加到链表尾部
            current_node = current_node.children[item]  # 移动到子节点
    return root, header_table

# FP_Growth.py中的规则生成（与Apriori共用逻辑）
for itemset in freq_items:
    if len(itemset) < 2:
        continue
    for i in range(1, len(itemset)):
        for antecedent in combinations(itemset, i):
            antecedent = tuple(antecedent)
            consequent = tuple([item for item in itemset if item not in antecedent])
            
            # 计算支持度与置信度
            sup_all = sum(1 for t in dataset if set(itemset).issubset(t)) / len(dataset)
            sup_ant = sum(1 for t in dataset if set(antecedent).issubset(t)) / len(dataset)
            conf = sup_all / sup_ant  # 置信度公式
            
            if conf >= min_conf:
                # 计算提升度：衡量规则独立性
                sup_con = ...  # 同前计算
                lift = sup_all / (sup_ant * sup_con)
                rules.append((antecedent, consequent, sup_all, conf, lift))