浅谈数据挖掘中的关联规则挖掘

数据挖掘期末报告——浅谈数据挖掘中的关联规则挖掘人们通过发现关联的规则，可以从一件事情的发生，来推测另外一件事情的发生，从而更好地了解和掌握事物的发展规律等等，这就是寻找关联规则的基本意义。关联规则的实际应用包括：交叉销售、邮购目录的设计、商品摆放、流失客户分析、基于购买模式进行客户区隔等等……举个最简单的例子，比如通过调查商场里顾客买的东西发现，30%的顾客会同时购买床单和枕套，而购买床单的人中有80%购买了枕套，这里面就隐藏了一条关联：床单—枕套，也就是说很大一部分顾客会同时购买床单和枕套，那么对于商场来说，可以把床单和枕套放在同一个购物区，那样就方便顾客进行购物了。专业一些来讲数据挖掘指以某种方式分析数据源，从中发现一些潜在的有用的信息，所以数据挖掘又称作知识发现，而关联规则挖掘则是数据挖掘中的一个很重要的课题和聚类算法一样，关联规则挖掘属于无监督学习方法，它描述的是在一个事物中物品间同时出现的规律的知识模式，现实生活中，比如超市购物时，顾客购买记录常常隐含着很多关联规则，比如购买圆珠笔的顾客中有65%也购买了笔记本，利用这些规则，商场人员可以很好的规划商品摆放问题；为叙述方便，设R={I1,I2......Im}是一组物品集，W是一组事务集。W中的每个事务T是一组物品，T是R的子集。假设有一个物品集A，一个事务T，关联规则是如下形式的一种蕴含：A→B，其中A、B是两组物品，A属于I子集，B属于I子集。在关联规则中设计4个常用关键指标1.置信度(confidence)简单地说，可信度就是指在出现了物品集A的事务T中，物品集B也同时出现的概率有多大。实例说明：上面所举的圆珠笔和笔记本的例子，该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了圆珠笔，那么他也购买笔记本的可能性有多大呢？在上述例子中，购买圆珠笔的顾客中有65％的人购买了笔记本,所以可信度是65％。概率描述：物品集A对物品集B的置信度confidence（A==B）=P（A|B）2.支持度(support)简单地说，A==B的支持度就是指物品集A和物品集B同时出现的概率。实例说明：某天共有1000个顾客到商场购买物品，其中有150个顾客同时购买了圆珠笔和笔记本，那么上述的关联规则的支持度就是15％。概率描述：物品集A对物品集B的支持度support（A==B）=P（AnB）3.期望置信度（Expectedconfidence）期望可信度描述了在没有任何条件影响时，物品集B在所有事务中出现的概率有多大。实例说明：如果某天共有1000个顾客到商场购买物品，其中有250个顾客购买了圆珠笔，则上述的关联规则的期望可信度就是25％。概率描述：物品集A对物品集B的期望置信度为support（B）=P（B）4.提升度（lift）提升度反映了“物品集A的出现”对物品集B的出现概率发生了多大的变化。实例说明：上述的关联规则的提升度=65%/25%=2.6概率描述：物品集A对物品集B的期望置信度为lift（A==B）=confidence（A==B）/support(B)=p(B|A)/p(B)总之，可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。Apriori算法使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。这个算法的思路，简单的说就是如果集合I不是频繁项集，那么所有包含集合I的更大的集合也不可能是频繁项集。算法原始数据如下：TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3算法的基本过程如下图：首先扫描所有事务，得到1-项集C1，根据支持度要求滤去不满足条件项集，得到频繁1-项集。下面进行递归运算：已知频繁k-项集(频繁1-项集已知)，根据频繁k-项集中的项，连接得到所有可能的K+1_项，并进行剪枝（如果该k+1_项集的所有k项子集不都能满足支持度条件，那么该k+1_项集被剪掉），得到项集，然后滤去该项集中不满足支持度条件的项得到频繁k+1-项集。如果得到的项集为空，则算法结束。连接的方法：假设项集中的所有项都是按照相同的顺序排列的，那么如果[i]和[j]中的前k-1项都是完全相同的，而第k项不同，则[i]和[j]是可连接的。比如中的{I1,I2}和{I1,I3}就是可连接的，连接之后得到{I1,I2,I3}，但是{I1,I2}和{I2,I3}是不可连接的，否则将导致项集中出现重复项。关于剪枝再举例说明一下，如在由生成的过程中，列举得到的3_项集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}，但是由于{I3,I4}和{I4,I5}没有出现在中，所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。海量数据下，Apriori算法的时空复杂度都不容忽视。空间复杂度：如果数量达到的量级，那么中的候选项将达到的量级。时间复杂度：每计算一次就需要扫描一遍数据库。参考：://