apriori算法实现_关联算法—Apriori
上次讲解了分类算法K近邻这一节内容，它是一种典型的分类方法。那么这次我们将深入学习数据挖掘算法中的关联分析算法——Apriori算法。它的最初应用就是从交易数据中挖掘商品之间的关联规则，在经典的案例中也就是我们常说的"尿布与啤酒"现象。随着互联网技术的快速发展，在各个行业领域上都取得了广泛的应用和发展。
下面直接进入主题。
一、重要的定义
事务型数据：关联分析的数据通常属于事务型数据。
其特点是，在数据集中每一笔记录对应一个事务（如交易详细信息），而每个事务中的元素则被称为项。
项集即由一个或多个项组成的集合。
如果包含K个项，则称其为K-项目集。
支持率：一个项目集合的发生率是指该项目集合在交易数据集中出现的频率。例如，在一个包含100个项目集合的交易数据库中, 项目集合{A,B}共出现在30个交易中, 则项目集合{A,B}的发生率为0.3, 其具体计算公式如下: 其中,N表示交易数据库中的总记录数,count(X)表示项目集合X在交易数据库中出现的次数: \text{support}(X)=\frac{\text{count}(X)}{N}
置信度常用于评估项集规则的有效性，在实际应用中常用于筛选出具有实际意义的项集规则。具体而言，在二元数据系统中计算某两个事件同时发生的概率作为其发生概率值，则该概率值即为此二元集合的概率值
提升度指标显示：当频繁项集规则的支持度与置信度较高时（我们称）这类规则被称为强关联规则。为了评估这些强关联规则的有效性（我们需要）通过计算提升度来判断其有效性程度。具体而言，在购买了商品X的前提下（顾客）也会购买商品Y的概率（其），相较于商品Y的整体销售情况（而言），其发生概率是其（总体）概率的a倍。数学表达式上，则有：
二、Apriori算法原理与性质
Apriori算法的核心依据的是频繁项集的先验性质, 即任何一个频繁项集的所有子集都必然是高频的, 因此使用n-1阶项集来探索潜在的n阶项集合, 从而有效地减少了对关联规则搜索空间的需求。该算法要求预先设定一个支持度阈值, 作为判断频繁项集的基本标准。首先对事务数据集合进行一次完整的扫描, 生成所有可能的一阶候选项集合, 这些一阶候选集合仅包含单个项目。基于预先设定的支持度阈值筛选出满足条件的一阶候选集合, 并将其标记为一阶高频项集合S₁。接着再次从原始数据集中挖掘包含S₁的所有二阶候选组合形成二阶候选项集合S₂, 并基于相同的标准不断迭代上述过程直至生成高频n阶组合Sₙ为止, 当无法再发现满足支持度与置信度双约束条件下的(n+1) 阶候选项时即终止整个过程。最终所得的结果即是从原始数据库中提取出来的所有高频组合模式
在Apriori关联规则挖掘算法中, 所有高频项目集合均具备'其所有子项目组合均为高频项目集合'的特点.因此, 在检查候选k-ary集合时若其对应的(k-1)-ary组合不在高频(k-1)-ary集合中, 则可确定该候选不符合条件并予以剔除.随后, 筛选出缩减后的k-ary集合, 并进一步去除那些未达到预设最低支持度的标准.最后, 基于这一规律性特征进行操作, 从而有效减少对数据集中高频项目集合进行搜索所需的时间.
三、Apriori算法步骤
(1)：遍历原始事务型数据并生成候选1项集集合，在给定最小支持度s的前提下筛选出频次不低于s的项目构成频繁1项集。
(2)：遍历原始事务型数据后生成候选2项集集合，并对各候选2项集进行筛选与验证工作；剔除包含非频繁1项集元素的项目组合形成新的候选集合。
(3)：持续应用上述方法逻辑依次获取高频项目组合直至满足后续条件。
(4)：设定置信度阈值对各频繁项目组合关联性进行评判，并计算其提升度值以确定强关联规则的有效性。
下面是Apriori算法过程示意图：
四、算法优点与局限
Apriori算法有效地应用了候选取集合与频繁项集之间的关联关系，在整个过程中充分体现了该算法的优势。该方法通过不断优化候选取集合，并结合其固有特性，在这一过程中能够系统地获取所有的频繁项集。经过持续优化剪枝操作后，在这一过程中实现了缩减候选取集合规模的目标，并且该过程最终充分体现了该算法的优势。该方法非常适合处理大规模事务型数据，并且从数据中提取出的相关规则也便于理解和应用
但是也需要注意以下三个问题：首先，在频繁项集数量较多的情况下，该算法可能会生成大量候选对象集合；其次，在算法运行过程中需要反复扫描数据库；对此类问题已有许多Apriori算法的变体进行了改进；最后，在数据集中某些特定项的比例较低时（即当某些项的支持度较低时），由于设定较高的最小支持度阈值可能会导致这些项目无法被分析为有效的关联规则；然而，在这种情况下降低最小支持度阈值虽然能够帮助发现更多潜在的关联规则（即能够发现更多潜在的模式），但同时也可能导致算法运行效率下降。
五、基于R实现关联规则挖掘
1、前期准备
为了在R语言中实施关联规则挖掘过程,我们通常会调用arules拓展包.
首先安装了arules包，并通过其apriori函数实现了该算法。接着使用了arulesViz这一工具来提供可视化的展示手段。
library(arules)
library(arulesViz)接着是我们要挖掘的一种事务型数据集登场了。在之前的论文研究中,我们曾收集过双十一期间的商品交易数据,但当时的数据量较为有限,因此转而采用R语言内置的Groceries数据集,该数据集记录了一个杂货店一个月内的真实销售记录情况。在这个背景下,我们需要引入稀疏矩阵这一概念:在稀疏矩阵中,每一列代表一种商品,取值为0或1,其中1表示对应的交易记录中含有该商品的存在;而每一行则对应一条完整的交易记录信息。在R语言中,则可以直接调用read.transactions()函数来生成这种稀疏矩阵结构。
#将工作目录中的交易数据集转换为稀疏矩阵的形式
groceries <- read.transactions("groceries.csv", sep = ",")
#使用summary()查看groceries的具体信息
summary(groceries)
上文中的截图包括了整个交易数据集中购买频率较高的商品。例如whole milk被购买了2513次。此外还描述了交易记录的规模，在一次交易中仅购买一样商品的记录共有2159条。当然地为了更直观地观察到交易数据集中商品的交易频率可以使用itemFrequencyPlot()该函数并设置参数TopN以指定需要获取的商品数量之后将对这些指定数量的商品进行可视化展示
2、模型建立
在构建模型之前，请先确定支持度与置信度这两个关键参数。这是一个通常会遇到的难题，在缺乏系统方法的情况下尤其如此。如果将这两个参数设定得过于简单化，则会导致生成的所有关联规则过于普通而缺乏实际应用价值。另一方面，在设置参数时如果过于随意，则可能导致生成大量无关紧要的规则，并且可能需要很长时间才能获得最终结果。我的经验是可以通过分析数据集的具体情况以及研究周期性特征来预估初始阈值，并以此为基础进行相应调整。接下来的任务就是实现对Groceries数据集进行关联规则挖掘工作：
# 设置支持度0.006,置信度0.25,规则的最小项集为2
groceryrules <- apriori(groceries, parameter = list(support =0.006, confidence = 0.25, minlen = 2))
#查看规则规模
summary(groceryrules)
观察到我们获得了满足支持度和置信度阈值的所有集合总数为463个，并且这些集合按照项目的数量分为几类：包含2-项目集合的有150个；包含3-项目集合的是297个；仅包含4-项目集合的数量为16个
3、认识规则模式
在分析结论法则之前 应先了解其分类模式 通常会分为三种类型 可行 平凡与特殊 这些法则各有不同 特别是可行型关联法则具有明确性和实用性 它们的发现难度较高 需要深入的理解与参数调整 平凡型则是指那些在日常生活中显而易见的基本规律 这类法则是明确无误地正确的 但由于其普遍性 所提供的商业价值有限 最后一类则是特殊型关联法则 这些法则看似奇怪 需要进一步的信息才能理解其内在含义 因此这类法则是数据挖掘中较为偶然的现象 通常只是一组随机的数据模式 R语言中的Apriori算法生成的结果由左部(lhs)与右部(rhs)构成 左部表示触发条件 右部代表预期结果 我们可以通过特定方法查看前五条相关联则
#查看前五条关联规则
inspect(groceryrules[1:5])
4、探索关键规则
数量上符合支持度及置信度阈值的支持项关联 Rules 共计有 463 条；然而实际上那些真正具有重要价值的关键项 association Rules 数量相对较少；因此我们需要采用特定方法高效手段从数百项 association Rules 中筛选出具有显著特征的关键 item association Rules 或者根据需求选择的商品化处理方案；下面我们将介绍几种常用 association Rules 策略
1、按支持度排序的部分规则
支持度被视为我们所设计的关联规则算法的第一个关键门槛。在确定阈值时需要特别注意的是这一参数对最终结果的影响。为了确保筛选出的有效规律我们采用了一种系统化的排序方法：将收集到的所有候选规律按照支持度从高到低进行排序并逐一评估其重要性。这种方法不仅能够有效减少噪声数据还能够帮助我们更有针对性地提取出那些具有实际应用价值的关键模式。
#按照支持度降序排列规则
inspect(sort(groceryrules,by='con'))
高支持度的前10条规则
2、按置信度排序的部分规则
支持程度仅作为我们在筛选关联规则时的第一个判据；随后的是置信水平；而这个指标能够验证那些具有较高支持程度的关联规则在多大程度上值得信赖；同样的道理下，在对我们的数据进行分析时，我们会按照置信水平进行降序排列
inspect(sort(groceryrules,by='sup'))
高置信度的前10条规则
3、按提升度排序的部分规则
除了前面提到的支持度和置信度外
inspect(sort(groceryrules,by='lift'))
高提升度的前10条规则
4、选择包含目标商品的规则
有时为了研究特定商品与其他商品之间的关联关系, 我们需要找出所有包含该商品的关联式子, 然后从中筛选出支持率、可信度和提升率较高的关联式子进行深入研究。例如, 在实际操作中我们可以选择像 whole milk 这样的具体实例来研究。
A1 = subset(groceryrules, items %in% c('whole milk'))
inspect(A1)
包含whole milk的前10条规则
当我们从多个角度提取出关联规则后，在这种情况下就可以对它们的内容进行深入分析；通过模拟生活场景等多种方法去深入理解这些规律出现的原因；这一点就是我们在挖掘这些规律时需要重点关注的核心内容。
5、规则可视化
抵达此地后，则我们的最终目标便是呈现关联规则的可视化形式。在R语言中，则用于展示关联规则可视化的拓展包是arulesViz包。其可视化涵盖graph图、grouped图以及paracoord图这三种类型。其中所采用的函数是plot()函数，并根据method参数确定绘图类型。
#加载arulesViz
library(arulesViz)
# 使用包含whole milk的前5条规则，分别用三种方法进行可视化
plot(A1[1:5],method = 'graph',control=list(main='关联规则-graph'))
plot(A1[1:5],method = 'grouped',control=list(main='关联规则-grouped'))
plot(A1[130:140],method = 'paracoord',control=list(main='关联规则-paracoord'))
graph图
在graph图中（graph图），商品之间通过带有指向性的箭头构成某种模式；圆形的大小则用于表示支持程度；面积越大则反映出该模式的支持力度更大；圆形的颜色则进一步表征着支持程度
group图
此外, grouped图的表现与graph图相映成趣, 其中横轴代表前件LHS, 纵轴代表结果RHS, 圆圈大小体现规则支持度, 圆圈色调则反映规则提升度
paracoord图
而paracoord图在直观性程度上，并未如前两种图表显示得那样明显。通过由左至右延伸且带有箭头的折线来展示关联股则中的lhs和rhs关系，在折线上段粗细程度来体现规则的支持强度大小，在颜色深浅层次上则反映了提升幅度的不同
在此之前我们已经完整地回顾了R语言中Apriori算法的基本流程和运行机制，并深入探讨了其核心原理。事实上并不过于复杂的是其他关联规则挖掘算法中的Eclat算法以及基于前缀树的FP-Tree算法它们的学习难度略高于Apriori算法对于有进一步兴趣的读者而言在网上的资源库中也可以找到相关资料供参考