论文部分内容阅读
摘 要：数据挖掘当下已成为十分热门的话题，人们对它将随之带来长远的经济社会效益清晰可见。面对现今要处理如此庞大的数据量，高效、准确地挖掘出数据中的有效信息十分必要。在数据挖掘领域中，关联规则旨在找出数据集中项与项之间未知的关系，进而可以从挖掘出的数据对象信息中得到我们需要的信息。Apriori算法是关联规则里的一项基本算法，也是数据挖掘领域十大经典算法之一，可以利用它挖掘数据集中数据项间的潜在关系。
关键词：数据挖掘；关联规则；Apriori算法；购物篮分析；频繁项集
中图分类号：TP391.4
先从著名的啤酒与尿布的案例说起。美国某零售业企业对过去的历史数据进行分析，意外发现很多购买尿布的顾客会购买啤酒。这样的结论按平常的思维根本不能解释，经过仔细调查，商家发现了潜在的秘密：美国的妈妈们习惯将购买尿布的任务交给下班后的小孩爸爸，其中有一些爸爸在买完尿布之后再去购买自己喜欢的啤酒，啤酒与尿布两个不相关联的事物就这样联系了起来。得到这一结论后，这家企业立即采取行动，将啤酒与尿布放在距离相近的位置，大大提高了銷售额。由此，诞生了购物篮分析（Market Basket Analysis）方法，衍生到数据挖掘领域称之为关联规则（Association Rules）。关联规则揭示了事物之间的相互依存性和关联性。关联规则在当今生活中应用十分广泛，如电商根据顾客近期的消费记录向顾客推送相似商品的广告信息，60%购买了牛奶的顾客会购买面包等。
1 关联规则概述
1.1 规则与关联规则
形如“如果…那么…”，通过条件得到结果，就是一项规则。关联规则可以用蕴含式：R：X Y表示，度量一项规则是否够好有两个指标：置信度（Confidence）和支持度（Support）。
1.2 置信度和支持度
置信度：表示一条规则值得信赖的程度。如果A表示条件，B表示结果，则置信度的数学表示为Confidence（A—>B）=P（B|A），其含义是在条件A发生的情况中同时条件B发生的概率。
支持度：表示在总体情况下当前情况发生的概率。如果A、B均表示一种可能发生的情况，则支持度数学表示为Support（A—>B）=P（AB），其含义是A、B同时发生的概率。
1.3 关联规则的相关概念
项目（Item）：集合I={k1，k2，…，kn}中每一个kn（n=1，2，…，n）叫做一个项目。集合I叫做项集（Itemset）。集合中元素个数为k的项集叫做k-项集（k-Itemset）。
交易（Transaction）：集合I的子集构成的集合称为交易，记为T，T I。每一笔交易有自己唯一的编号，即交易号TID。若干交易构成的集合D称为交易集D，交易集D中包含的交易个数记为count（D）。
项集支持度：对于规则X Y，Support（X Y）=count（X∪Y）/count（D），X、Y I，支持度的含义就是含X、Y的交易数与总交易数之比。
项集置信度：Confidence（X Y）=Support（X Y）/Support（X），置信度的含义是包含X、Y的交易与包含X的交易之比。支持度与置信度刻画了用户兴趣程度，一般来说，两者都高表示用户对其兴趣越高。
1.4 最小支持度与频繁项集
关联规则作用的集合必须满足一个最小支持阈值，即存在最小支持度（Minimum Support）。所有项的支持度均大于等于最小支持度的集合，称之为频繁项集（Frequent Itemset）。同样也存在一个最小置信度（Minimum Confidence）。最小支持度与最小置信度用来衡量关联规则的最低可靠程度。
1.5 强关联规则
满足支持度大于等于最小支持度，置信度大于等于最小置信度的关联规则称之为强关联规则（Strong Rules）。反之，称为弱关联规则。
2 Apriori算法的实现
Apriori算法是一种生成关联规则的频繁项集挖掘经典算法，利用该算法，可以找到项之间关系。Apriori算法有两个重要的性质：
（1）频繁项集的子集一定是频繁项集。
（2）非频繁项集的超集一定是非频繁项集。
Apriori算法挖掘的步骤：
（1）扫描数据库，算出初始项集K1各个项的支持度，即1-项集的支持度，通过最小支持度筛选得到1-项集的频繁集，记为Q1。
（2）扫描数据库，通过Q1中项与项之间连接∞得到备选项集K2，K2是2-项集。
（3）通过最小支持度筛选K2得到频繁集Q2，即将K2中不满足最小支持度的项舍去得到Q2。
（4）通过Q2以（2）中的方法计算出K3，通过K3以（3）中的方法计算出Q4，继续扫描数据库，用（2）（3）中方法继续计算更高层次的频繁项集，（2）中使用的的方法叫做连接（Join），（3）中使用的方法叫做剪枝（Prune），重复步骤连接、剪枝，直到不再产生新的项集为止。例：
K1={k1，k2，k3，k4，k5}，最小支持度Supmin=45%，最小置信度Conmin=45%
（1）计算k1各项支持度：sup{k1}=50%，sup{k2}=75%，sup{k3}=75%，sup{k4}=25%，sup{k5}=75%。
∵sup（k4） （2）Q1中项与项之间做连接 ：K2={{k1，k2}，{k1，k3}，{k1，k5}，{k2，k3}，{k2，k5}，{k3，k5}}。
（3）计算K2各项支持度，得到sup{k1，k2} （4）循环（2）（3）中步骤，最终得到频繁项集{k2，k3，k5}。通过{k2，k3，k5}的非空子集和最小置信度即可产生强关联规则。
3 Apriori算法的不足
Apriori算法存在一个很严重的问题是效率低。因为Apriori算法是从1-项集开始逐层计算得到最大项集的，从k-项集通过连接、剪枝到k+1项集需要扫描一次数据库，如果项集中项数越多，则扫描次数越多。比如：项集中含10个项，则要扫描数据库10次，I/O负载特别大。针对它的不足，Jiawei Han等人提出了FP-growth算法，也有人研究出一些改进算法，大大提高了算法的效率。
参考文献：
[1]杨文博.零售业数据挖掘的再认识[J].商业时代，2004（11）：10-11.
[2]刘华婷，郭仁祥，姜浩.关联规则挖掘Apriori算法的研究与改进[J].计算机应用与软件，2009（01）：146-149.
[3]赵洪英，蔡乐才，李先杰.关联规则挖掘的Apriori算法综述[J].四川理工学院学报（自然科学版），2011（01）：66-70.
[4]张红艳，都娟.关联规则中Apriori算法的应用[J].数字技术与应用，2011（08）：14-15.
作者简介：侯雲峰（1993.05-），男，四川阆中人，本科，研究方向：计算机科学与技术。
作者单位：四川大学，成都 610000
关键词：数据挖掘；关联规则；Apriori算法；购物篮分析；频繁项集
中图分类号：TP391.4
先从著名的啤酒与尿布的案例说起。美国某零售业企业对过去的历史数据进行分析，意外发现很多购买尿布的顾客会购买啤酒。这样的结论按平常的思维根本不能解释，经过仔细调查，商家发现了潜在的秘密：美国的妈妈们习惯将购买尿布的任务交给下班后的小孩爸爸，其中有一些爸爸在买完尿布之后再去购买自己喜欢的啤酒，啤酒与尿布两个不相关联的事物就这样联系了起来。得到这一结论后，这家企业立即采取行动，将啤酒与尿布放在距离相近的位置，大大提高了銷售额。由此，诞生了购物篮分析（Market Basket Analysis）方法，衍生到数据挖掘领域称之为关联规则（Association Rules）。关联规则揭示了事物之间的相互依存性和关联性。关联规则在当今生活中应用十分广泛，如电商根据顾客近期的消费记录向顾客推送相似商品的广告信息，60%购买了牛奶的顾客会购买面包等。
1 关联规则概述
1.1 规则与关联规则
形如“如果…那么…”，通过条件得到结果，就是一项规则。关联规则可以用蕴含式：R：X Y表示，度量一项规则是否够好有两个指标：置信度（Confidence）和支持度（Support）。
1.2 置信度和支持度
置信度：表示一条规则值得信赖的程度。如果A表示条件，B表示结果，则置信度的数学表示为Confidence（A—>B）=P（B|A），其含义是在条件A发生的情况中同时条件B发生的概率。
支持度：表示在总体情况下当前情况发生的概率。如果A、B均表示一种可能发生的情况，则支持度数学表示为Support（A—>B）=P（AB），其含义是A、B同时发生的概率。
1.3 关联规则的相关概念
项目（Item）：集合I={k1，k2，…，kn}中每一个kn（n=1，2，…，n）叫做一个项目。集合I叫做项集（Itemset）。集合中元素个数为k的项集叫做k-项集（k-Itemset）。
交易（Transaction）：集合I的子集构成的集合称为交易，记为T，T I。每一笔交易有自己唯一的编号，即交易号TID。若干交易构成的集合D称为交易集D，交易集D中包含的交易个数记为count（D）。
项集支持度：对于规则X Y，Support（X Y）=count（X∪Y）/count（D），X、Y I，支持度的含义就是含X、Y的交易数与总交易数之比。
项集置信度：Confidence（X Y）=Support（X Y）/Support（X），置信度的含义是包含X、Y的交易与包含X的交易之比。支持度与置信度刻画了用户兴趣程度，一般来说，两者都高表示用户对其兴趣越高。
1.4 最小支持度与频繁项集
关联规则作用的集合必须满足一个最小支持阈值，即存在最小支持度（Minimum Support）。所有项的支持度均大于等于最小支持度的集合，称之为频繁项集（Frequent Itemset）。同样也存在一个最小置信度（Minimum Confidence）。最小支持度与最小置信度用来衡量关联规则的最低可靠程度。
1.5 强关联规则
满足支持度大于等于最小支持度，置信度大于等于最小置信度的关联规则称之为强关联规则（Strong Rules）。反之，称为弱关联规则。
2 Apriori算法的实现
Apriori算法是一种生成关联规则的频繁项集挖掘经典算法，利用该算法，可以找到项之间关系。Apriori算法有两个重要的性质：
（1）频繁项集的子集一定是频繁项集。
（2）非频繁项集的超集一定是非频繁项集。
Apriori算法挖掘的步骤：
（1）扫描数据库，算出初始项集K1各个项的支持度，即1-项集的支持度，通过最小支持度筛选得到1-项集的频繁集，记为Q1。
（2）扫描数据库，通过Q1中项与项之间连接∞得到备选项集K2，K2是2-项集。
（3）通过最小支持度筛选K2得到频繁集Q2，即将K2中不满足最小支持度的项舍去得到Q2。
（4）通过Q2以（2）中的方法计算出K3，通过K3以（3）中的方法计算出Q4，继续扫描数据库，用（2）（3）中方法继续计算更高层次的频繁项集，（2）中使用的的方法叫做连接（Join），（3）中使用的方法叫做剪枝（Prune），重复步骤连接、剪枝，直到不再产生新的项集为止。例：
K1={k1，k2，k3，k4，k5}，最小支持度Supmin=45%，最小置信度Conmin=45%
（1）计算k1各项支持度：sup{k1}=50%，sup{k2}=75%，sup{k3}=75%，sup{k4}=25%，sup{k5}=75%。
∵sup（k4）
（3）计算K2各项支持度，得到sup{k1，k2}
3 Apriori算法的不足
Apriori算法存在一个很严重的问题是效率低。因为Apriori算法是从1-项集开始逐层计算得到最大项集的，从k-项集通过连接、剪枝到k+1项集需要扫描一次数据库，如果项集中项数越多，则扫描次数越多。比如：项集中含10个项，则要扫描数据库10次，I/O负载特别大。针对它的不足，Jiawei Han等人提出了FP-growth算法，也有人研究出一些改进算法，大大提高了算法的效率。
参考文献：
[1]杨文博.零售业数据挖掘的再认识[J].商业时代，2004（11）：10-11.
[2]刘华婷，郭仁祥，姜浩.关联规则挖掘Apriori算法的研究与改进[J].计算机应用与软件，2009（01）：146-149.
[3]赵洪英，蔡乐才，李先杰.关联规则挖掘的Apriori算法综述[J].四川理工学院学报（自然科学版），2011（01）：66-70.
[4]张红艳，都娟.关联规则中Apriori算法的应用[J].数字技术与应用，2011（08）：14-15.
作者简介：侯雲峰（1993.05-），男，四川阆中人，本科，研究方向：计算机科学与技术。
作者单位：四川大学，成都 610000