Apriori
Apriori 算法是一种经典的关联规则挖掘算法，用于发现数据集中项集之间的频繁模式和关联规则。它由 Agrawal 和 Srikant 在 1994 年提出，广泛应用于市场分析、推荐系统等领域。如果某个项集是频繁的，那么它的所有子集也是频繁的。这一原理有助于避免项集数目的指数增长，从而在合理时间内计算出频繁项集。
可结合树模型，深度分析随机森林
基本概念
1. 项集（Itemset）
项集是数据集中的一组项（items）。例如，在超市购物篮数据中，项集可以是 {牛奶, 面包, 黄油}。
2. 支持度（Support）
支持度是项集在数据集中出现的频率。支持度定义为包含该项集的事务数与总事务数的比值。
$$ \text{Support}(X) = \frac{\text{Number of transactions containing } X}{\text{Total number of transactions}} $$
3. 频繁项集（Frequent Itemset）
频繁项集是指支持度大于或等于某个最小支持度阈值（min_support）的项集。
4. 关联规则（Association Rule）
关联规则是形如 ( X \rightarrow Y ) 的规则，其中 ( X ) 和 ( Y ) 是项集，且 ( X \cap Y = \emptyset )。
5. 置信度（Confidence）
置信度是关联规则 ( X \rightarrow Y ) 的度量，表示在包含 ( X ) 的事务中，同时包含 ( Y ) 的事务的比例。
$$ \text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} $$
6. 提升度（Lift）
提升度是关联规则 ( X \rightarrow Y ) 的另一个度量，表示包含 ( X ) 的事务中同时包含 ( Y ) 的概率与 ( Y ) 的总体概率的比值。
$$ \text{Lift}(X \rightarrow Y) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} $$
Apriori 算法步骤
Apriori 算法主要包含以下步骤：
1. 生成候选项集（Candidate Itemsets）
从单个项开始，生成所有可能的项集。
2. 计算支持度
计算每个候选项集的支持度，并筛选出频繁项集。
3. 生成关联规则
从频繁项集中生成关联规则，并计算其置信度和提升度。
4. 筛选关联规则
根据最小置信度阈值（min_confidence）筛选出有效的关联规则。
算法流程
- 初始化：生成所有单个项的项集，并计算其支持度。
- 迭代生成频繁项集：
- 从频繁 ( k-1 ) 项集生成候选 ( k ) 项集。
- 计算候选 ( k ) 项集的支持度。
- 筛选出频繁 ( k ) 项集。
- 生成关联规则：
- 从频繁项集中生成关联规则。
- 计算每个关联规则的置信度和提升度。
- 筛选出有效的关联规则。
示例
假设我们有以下购物篮数据：
| 事务ID | 项集 |
|---|---|
| 1 | {牛奶, 面包} |
| 2 | {牛奶, 黄油} |
| 3 | {面包, 黄油} |
| 4 | {牛奶, 面包, 黄油} |
1. 生成候选项集
- 单个项集：{牛奶}, {面包}, {黄油}
- 二个项集：{牛奶, 面包}, {牛奶, 黄油}, {面包, 黄油}
- 三个项集：{牛奶, 面包, 黄油}
2. 计算支持度
- 支持度({牛奶}) = 3/4
- 支持度({面包}) = 3/4
- 支持度({黄油}) = 3/4
- 支持度({牛奶, 面包}) = 2/4
- 支持度({牛奶, 黄油}) = 2/4
- 支持度({面包, 黄油}) = 2/4
- 支持度({牛奶, 面包, 黄油}) = 1/4
假设最小支持度阈值为 0.5，则频繁项集为： - {牛奶}, {面包}, {黄油}, {牛奶, 面包}, {牛奶, 黄油}, {面包, 黄油}
3. 生成关联规则
- 从频繁项集中生成关联规则，并计算置信度和提升度。
例如： - 规则：{牛奶} → {面包} - 置信度 = 支持度({牛奶, 面包}) / 支持度({牛奶}) = (2/4) / (3/4) = 2/3 - 提升度 = 置信度 / 支持度({面包}) = (2/3) / (3/4) = 8/9
4. 筛选关联规则
根据最小置信度阈值筛选出有效的关联规则（置信度越大越好）。
提升度
1. 评估规则的相关性
提升度可以帮助我们判断关联规则 ( X \rightarrow Y ) 是否具有实际意义，即 ( X ) 和 ( Y ) 之间是否存在真正的关联关系，而不仅仅是偶然的共现。
2. 区分偶然性和必然性
提升度的值可以帮助我们区分规则的偶然性和必然性：
- 提升度 = 1：表示 ( X ) 和 ( Y ) 之间没有关联，即 ( X ) 和 ( Y ) 的出现是独立的。
- 提升度 > 1：表示 ( X ) 和 ( Y ) 之间存在正向关联，即 ( X ) 的出现增加了 ( Y ) 出现的概率。
- 提升度 < 1：表示 ( X ) 和 ( Y ) 之间存在负向关联，即 ( X ) 的出现减少了 ( Y ) 出现的概率。
3. 选择有效的关联规则
在实际应用中，我们通常会选择提升度大于 1 的关联规则，因为这些规则表明 ( X ) 和 ( Y ) 之间存在有意义的关联关系。提升度越大，关联规则的相关性越强。
总结
Apriori 算法通过迭代生成候选项集和计算支持度，有效地挖掘数据集中的频繁项集和关联规则。它利用了频繁项集的先验性质（Apriori 性质），即一个项集是频繁的，则其所有子集也是频繁的。这大大减少了计算量，提高了算法的效率。希望这个详解对你有所帮助！如果你有任何问题或需要进一步的帮助，请随时告诉我。
from itertools import combinations
class Apriori:
def __init__(self, min_support, min_confidence,load_data=None):
self.min_support = min_support
self.min_confidence = min_confidence
self.frequent_itemsets = {}
self.rules = []
if(load_data):self.load_data=load_data
def load_data(self):
# 示例数据集
data = [
['牛奶', '面包', '黄油'],
['牛奶', '面包', '尿布', '啤酒'],
['牛奶', '尿布', '啤酒', '可乐'],
['面包', '黄油', '尿布', '啤酒'],
['面包', '尿布', '啤酒']
]
return data
def create_candidates(self, data, k):
candidates = set()
for transaction in data:
for item in transaction:
candidates.add(frozenset([item]))
return [frozenset(item) for item in candidates]
def filter_candidates(self, data, candidates):
item_count = {}
for transaction in data:
for candidate in candidates:
if candidate.issubset(transaction):
if candidate not in item_count:
item_count[candidate] = 1
else:
item_count[candidate] += 1
num_transactions = len(data)
frequent_items = {item: count / num_transactions for item, count in item_count.items() if count / num_transactions >= self.min_support}
return frequent_items
def generate_frequent_itemsets(self, data, max_length=3):
k = 1
candidates = self.create_candidates(data, k)
while candidates and k <= max_length:
frequent_items = self.filter_candidates(data, candidates)
self.frequent_itemsets.update(frequent_items)
k += 1
candidates = [frozenset(comb) for comb in combinations(set().union(*frequent_items.keys()), k)]
def generate_rules(self):
for itemset in self.frequent_itemsets:
if len(itemset) > 1:
for i in range(1, len(itemset)):
for subset in combinations(itemset, i):
antecedent = frozenset(subset)
consequent = itemset - antecedent
confidence = self.frequent_itemsets[itemset] / self.frequent_itemsets[antecedent]
if confidence >= self.min_confidence:
self.rules.append((antecedent, consequent, confidence))
def run(self):
data = self.load_data()
self.generate_frequent_itemsets(data)
self.generate_rules()
def print_results(self):
print("Frequent Itemsets:")
for itemset, support in self.frequent_itemsets.items():
print(f"{set(itemset)}: {support:.2f}")
print("\nAssociation Rules:")
for antecedent, consequent, confidence in self.rules:
print(f"{set(antecedent)} => {set(consequent)}: {confidence:.2f}")
apriori = Apriori(min_support=0.6, min_confidence=0.7)
apriori.run()
apriori.print_results()