aprior算法关联规则

Apriori算法是一种常用的关联规则挖掘算法[^1]。它通过扫描数据集多次来发现频繁项集，然后利用频繁项集生成关联规则。Apriori算法的基本思想是利用频繁项集的性质，即如果一个项集是频繁的，那么它的所有子集也是频繁的。算法的过程如下：

1. 初始化：将每个项作为单独的项集，并计算每个项集的支持度。
2. 迭代生成候选项集：根据上一次迭代得到的频繁项集，生成候选项集。候选项集的生成过程是通过连接和剪枝操作实现的。
- 连接：将频繁项集按照长度进行连接，得到候选项集。
- 剪枝：对于候选项集，检查其所有子集是否都是频繁项集，如果不是，则剪枝。
3. 计算候选项集的支持度：扫描数据集，统计每个候选项集的支持度。
4. 生成频繁项集：根据候选项集的支持度，筛选出满足最小支持度阈值的频繁项集。
5. 生成关联规则：对于每个频繁项集，生成其所有非空子集作为规则的前件，计算规则的置信度和提升度。
- 置信度：规则的置信度表示在前件出现的情况下，后件也出现的概率。
- 提升度：规则的提升度表示在前件出现的情况下，后件出现的概率相对于在整个数据集中出现的概率的提升程度。

通过Apriori算法，可以挖掘出频繁项集和关联规则，从而发现物品之间的相关性。这些关联规则可以应用于广告推荐、流量探索等领域。

相关问题

aprior算法关联规则挖掘

### Apriori算法在关联规则挖掘中的应用

#### 1. 基本概念与原理

Apriori 算法是一种用于发现事务数据库中频繁项集的有效方法，进而从中提取有价值的关联规则。该算法利用了先验性质（即如果某个项集是非频繁的，则其所有的超集也必定是非频繁的），从而减少了不必要的计算开销[^1]。

#### 2. 主要步骤说明

- **候选项集生成**：从单个物品开始构建长度为 k 的候选集合 Ck；
- **支持度计数**：扫描整个交易记录来统计各个候选项目的出现次数；
- **剪枝操作**：移除那些不满足最小支持度条件的项目组合；
- **重复上述过程直到不再有新的频繁模式被找到为止**；

此过程中会不断迭代地增加考虑的商品数量直至无法再找出更复杂的购买行为模式。

#### 3. Python实现示例

下面给出一段简单的Python代码片段用来演示Apriori算法的具体执行流程：

from collections import defaultdict
import itertools


def apriori(transactions, min_support=0.5):
    items = defaultdict(int)

    # 记录每种商品的支持度
    for transaction in transactions:
        for item in transaction:
            items[item] += 1
    
    num_transactions = float(len(transactions))
    
    frequent_items = set()
    all_frequent_itemsets = []

    # 过滤掉低于设定阈值的商品作为初始频繁一项集
    for key, value in items.items():
        support = value / num_transactions
        
        if support >= min_support:
            frequent_items.add(frozenset([key]))
            
    current_l_set = frequent_items
    
    while(current_l_set != set([])):
        all_frequent_itemsets.append(current_l_set)
        
        next_c_set = generate_candidate_sets(current_l_set)
        current_l_set = find_frequent_itemset(
            transactions,
            next_c_set,
            min_support,
            num_transactions
        )
        
    return all_frequent_itemsets
    

def generate_candidate_sets(itemsets):
    candidate_sets = []
    
    for i in itemsets:
        for j in itemsets:
            union = i.union(j)
            
            if (len(union) == len(i)+1 and 
                not any(x in candidate_sets for x in [frozenset(y) for y in list(itertools.combinations(sorted(list(union)), len(i)))])):
                
                candidate_sets.append(union)
                
    return candidate_sets


def find_frequent_itemset(transactions, c_k, min_support, total_count):
    l_k = set()

    local_dict = {}
    
    for t in transactions:
        for can in c_k:
            if can.issubset(t):
                try:
                    local_dict[can] += 1
                except KeyError:
                    local_dict[can] = 1
                    
    for itemset, count in local_dict.items():
        support = count/total_count
        
        if support >= min_support:
            l_k.add(itemset)
            
    return l_k

这段程序实现了基本版的Apriori逻辑框架，可以根据给定的数据集和最低支持率参数返回符合条件的所有频繁项集列表。

关联规则aprior算法代码实现

以下是Apriori算法的Python实现：

def loadDataSet():
    """
    创建一个用于测试的简单数据集
    """
    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]

def createC1(dataSet):
    """
    创建初始候选项集C1
    """
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)

def scanD(D, Ck, minSupport):
    """
    从候选项集Ck生成符合最小支持度的项集Lk
    """
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not can in ssCnt:
                    ssCnt[can] = 1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0,key)
        supportData[key] = support
    return retList, supportData

def aprioriGen(Lk, k):
    """
    根据Lk生成候选项集Ck+1
    """
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1==L2:
                retList.append(Lk[i] | Lk[j])
    return retList

def apriori(dataSet, minSupport = 0.5):
    """
    Apriori算法
    """
    C1 = createC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

使用方法如下：

dataSet = loadDataSet()
L, suppData = apriori(dataSet, minSupport=0.5)
print(L)
print(suppData)

其中，`dataSet`是数据集，`minSupport`是最小支持度。`L`即为频繁项集，`suppData`是包含支持度信息的字典。