关联分析基本概念与算法.ppt

FP增长（FP-growth）算法关联模式的评估（PatternEvaluation）030201关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的。第一组标准可以通过统计论据建立。涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。这些令人感兴趣的模式可以使用客观兴趣度度量来排除。第二组标准可以通过主观论据建立。一个模式被主观认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。例如：{黄油}?{面包}可能不是有趣的，尽管有很高的支持度和置信度，但是它表示的关系显而易见。另一方面，规则{尿布}?{啤酒}是有趣的，因为这种联系十分出乎意料，并且可能为零售商提供新的交叉销售机会。将主观知识加入到模式的评价中是一项困难的任务，因为需要来自领域专家的大量先验信息。下面是一些将主观信息加入到模式发现任务中的方法。兴趣度客观度量（objectiveinterestingnessmeasure）ContingencytableforX?YYYXf11f10f1+Xf01f00fo+f+1f+0|T|支持度-置信度框架的局限性现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。例子：假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总到下表6-8。CoffeeCoffeeTea15050200Tea6501508008002001000似乎喜欢喝茶的人也喜欢喝咖啡，因为该规则的支持度（15%）和置信度（75%）都相当高。置信度的缺点在于该度量忽略了规则后件中项集的支持度。可以使用表中给出的信息来评估关系规则{茶}?{咖啡}。但是所有人中，不管他是否喝茶，喝咖啡的人的比例为80%。这意味着，一个人如果喝茶，则他喝咖啡的可能性由80%减到了75%。01020304支持度-置信度框架的局限性Hash树结构1591451363453673683563576892345671244571254581,4,72,5,83,6,9HashFunctionCandidateHashTreeHashon3,6or9356使用Hash树进行支持度计数159145136345367368356357689234567124457125458123561+23562+563+1,4,72,5,83,6,9HashFunctiontransaction356使用Hash树进行支持度计数1591451363453673683563576892345671244571254581,4,72,5,83,6,9HashFunction1235635612+5613+615+2+563+1+2356transaction356使用Hash树进行支持度计数1591451363453673683563576892345671244571254581,4,72,5,83,6,9HashFunction1235635612+5613+615+2+563+1+2356transaction15个项集中的9个与事务进行比较存放在被访问的叶结点中的候选项集与事务进行比较，如果候选项集是该事务的子集，则增加它的支持度计数。01在该例子中，访问了9个叶子结点中的5个。0215个项集中的9个与事务进行比较03事务的平均宽度04频繁项集的最大长度随事务平均宽度增加而增加随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数事务数03由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数增加而增加项数02随着项数的增加，需要更多的空间来存储项的支持度计数。如果频繁项集的数目也随着数据项数增加而增长，则