数据挖掘apriori算法例题_peterson算法[通俗易懂]

一、Apriori算法

Apriori算法是一种常用的数据挖掘算法，用于在数据集中发现频繁项集。它常用于市场篮子分析，帮助识别顾客购买产品之间的关系。以下是该算法的简要介绍：

1. 支持度： 该算法使用用户定义的阈值，称为”支持度”。支持度表示项集必须在数据集中出现的最低次数，才能被视为频繁项集。

2. Apriori原则： 该算法基于Apriori原则运作，该原则指出，如果一个项集是频繁的，那么它的所有子集也必须是频繁的。这减少了需要检查频繁性的项集数量。

3. 生成候选项集： 该算法首先找到满足最小支持度阈值的单个项（1-项集）。然后，它通过迭代生成更大的项集（2-项集、3-项集等），方法是连接频繁的（k-1）-项集。

4. 剪枝： 在每次迭代中，该算法会修剪不频繁的项集，减少搜索空间。

5. 重复： 步骤3和4会重复，直到不再有频繁项集满足支持度要求。

这个算法的核心思想是通过递增地生成和检查候选项集，找出频繁出现的项集，以便进一步的分析或决策。

代码生成：

from collections import defaultdict
from itertools import combinations

# 数据集
transactions = [
{“A”, “B”, “C”},
{“B”, “C”},
{“A”, “B”},
{“A”, “B”, “C”},
{“A”},{“A”, “B”, “D”},
{“A”, “B”, “D”},
{“E”, “B”, “C”}
]

# 设定支持度阈值
min_support = 2
# 生成候选项集C1
def generate_C1(transactions):
C1 = set()
for transaction in transactions:
for item in transaction:
C1.add(frozenset([item]))
# print(C1)
return C1

# 过滤候选项集，得到频繁项集
def filter_candidates(transactions, candidates, min_support):
item_counts = defaultdict(int)
for transaction in transactions:
for candidate in candidates:
if candidate.issubset(transaction):
item_counts[candidate] += 1

frequent_items = set()
for item, count in item_counts.items():
if count >= min_support:
frequent_items.add(item)
# print(frequent_items)
return frequent_items

# 生成候选项集Ck+1
def generate_next_candidates(frequent_items, k):
next_candidates = set()
for a in frequent_items:
for b in frequent_items:
union = a.union(b)
if len(union) == k + 1:
next_candidates.add(union)
return next_candidates

# Apriori算法主函数
def apriori(transactions, min_support):
frequent_items = set()
candidates = generate_C1(transactions)
k = 1
while candidates:
candidates = filter_candidates(transactions, candidates, min_support)
frequent_items.update(candidates)
k += 1
candidates = generate_next_candidates(candidates, k)
# print(frequent_items)
return frequent_items

frequent_itemsets = apriori(transactions, min_support)
for itemset in frequent_itemsets:
print(itemset)

二、FP-growth算法

FP-growth（频繁模式生长）算法是一种用于数据挖掘和关联规则挖掘的常用算法，特别适用于发现频繁项集。以下是该算法的中文介绍：

1. 构建FP树： FP-growth算法的第一步是构建FP树，即频繁模式树。FP树是一种紧凑的数据结构，用于表示频繁项集的频繁程度和关系。

2. 建立项头表： 与FP树一同构建的是项头表，其中包含数据集中的每个不同项以及它们在FP树中的链接。这些链接用于高效地查找频繁项。

3. 挖掘频繁项集： 通过递归地生长FP树和利用项头表，算法发现频繁项集。它以一种深度优先的方式遍历FP树，同时使用条件模式基来构建条件FP树，以寻找更多的频繁项。

4. 剪枝： FP-growth不需要像Apriori算法那样生成候选项集，因此它通常比Apriori更快。这是因为FP-growth利用FP树的结构，通过路径压缩和条件模式基的剪枝，减少了不必要的计算。

FP-growth算法在大规模数据集上通常表现出色，因为它能够以高效的方式发现频繁项集，而无需生成大量的候选项集。这使得它成为关联规则挖掘和市场篮子分析等应用领域的强大工具。

代码生成：

import pyfpgrowth   

# 示例数据集
dataset = [
[“A”, “B”, “C”, “D”],
[“A”, “B”],
[“A”, “B”, “D”],
[“A”],
[“A”, “C”, “D”]
]

# 设置最小支持阈值
min_support = 2

# 执行FP-Growth算法
patterns = pyfpgrowth.find_frequent_patterns(dataset, min_support)

# 找到关联规则
rules = pyfpgrowth.generate_association_rules(patterns, confidence_threshold=0.5)

# 打印频繁项集
print(“频繁项集:”)
for pattern, support in patterns.items():
print(f”Pattern: {pattern}, Support: {support}”)

三、ECLAT算法

ECLAT（Equivalence Class Clustering and Bottom-Up Lattice Traversal）算法是一种用于数据挖掘的频繁项集挖掘算法。以下是该算法的中文介绍：

1. 构建事务数据库： ECLAT算法首先将数据集表示为一个事务数据库，其中每个事务包含一组项，每个项都代表数据集中的一个特定元素。

2. 构建候选项集树： 与Apriori算法不同，ECLAT不生成候选项集。相反，它构建了一种称为”候选项集树”的数据结构。该树是一种基于前缀的数据结构，用于存储频繁项集的信息。

3. 垂直数据压缩： ECLAT使用一种称为”垂直数据压缩”的技术，将事务数据库重新组织为一个垂直数据结构，以便更快速地发现频繁项集。

4. 递归搜索： ECLAT采用递归的方式从候选项集树中搜索频繁项集。它以一种深度优先的方式遍历树结构，同时使用垂直数据表示和前缀信息来减少搜索的复杂性。

5. 发现频繁项集： 通过递归搜索，ECLAT算法找到频繁项集的所有组合，其支持度满足用户指定的最小支持度阈值。

ECLAT算法以高效的方式挖掘频繁项集，特别适用于处理大规模数据集，因为它不需要生成候选项集，而是直接利用候选项集树和垂直数据压缩技术来提高效率。这使得它成为关联规则挖掘的有力工具。

代码生成：

from collections import defaultdict
class EclatNode:
def __init__(self, item, tid_list):
self.item = item
self.tid_list = tid_list
self.children = {}
def generate_dataset():
dataset = [
[“A”, “B”, “C”, “D”],
[“A”, “B”],
[“A”, “B”, “D”],
[“A”],
[“A”, “C”, “D”]
]
return dataset
def build_eclat_tree(dataset, min_support):
item_tids = defaultdict(list)

for tid, transaction in enumerate(dataset):
for item in transaction:
item_tids[item].append(tid)

frequent_items = [item for item, tids in item_tids.items() if len(tids) >= min_support]
frequent_items.sort()

root = EclatNode(None, list(range(len(dataset))))
for item in frequent_items:
root.children[item] = EclatNode(item, item_tids[item])
return root
def eclat_mining(node, min_support, prefix, frequent_itemsets):
if len(node.tid_list) >= min_support and node.item is not None:
frequent_itemsets.append((prefix + [node.item], len(node.tid_list)))

for item, child_node in node.children.items():
eclat_mining(child_node, min_support, prefix + [node.item], frequent_itemsets)
def eclat(dataset, min_support):
frequent_itemsets = []
eclat_tree = build_eclat_tree(dataset, min_support)
eclat_mining(eclat_tree, min_support, [], frequent_itemsets)
return frequent_itemsets
# 示例用法
dataset = generate_dataset()
min_support = 3
frequent_itemsets = eclat(dataset, min_support)
for itemset, support in frequent_itemsets:
print(f”Frequent Itemset: {itemset}, Support: {support}”)

今天的文章数据挖掘apriori算法例题_peterson算法[通俗易懂]分享到此就结束了，感谢您的阅读。