8数据挖掘ppt.ppt

挖掘频繁模式，关联和相关性： 基本概念和方法 6.1基本概念 6.2频繁项集挖掘方法 6.3哪些模式是有趣的：模式评估方法 频繁模式是频繁的出现在数据集中的模式。（项集，子序集，子结构） 频繁项集：频繁的同时出现在交易数据集中的商品的集合。（面包和牛奶） 频繁子序集：一个子序列，如果它频繁的出现在购物历史数据中。（pc→数码相机→内存卡） 频繁子结构：一个子结构可能涉及不同的结构形式，如：子图，子树，子格；如果一个子结构频繁出现。 6.1.1购物篮分析 频繁项集挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入他们“购物篮”中的商品之间的关联，分析顾客习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而更好地制定方案。 购物篮分析可以帮助设计不同的商品布局。一种策略：经常买的商品可以摆放近一些，以便进一步刺激这些商品同时销售；另一种策略：把两种关联度高的产品放在商店两端，可以诱发买这些商品的顾客一路挑选其他商品。（如面包和黄油）  每一个购物篮可以由一个布尔向量表示，可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式，这些模式可以用关联规则的形式表示。 例 购买计算机也趋向于同时购买杀毒软件，可以表示为computer→antivirus software[support=2%;confidence=60%](6.1) 意义：分析所有事务的2%显示计算机和杀毒软件被同时购买；置信度60%意味着购买计算机的60%页购买了杀毒软件。 规则的支持度和置信度是规则兴趣度的两种度量。它们分别分别反映所发现规则的有用性和确定性。 最小支持度阈值，最小置信度阈值 6.1.2 频繁项集，闭项集和关联规则 支持度s support(A→B)=P(AUB) (6.2) 置信度c confidence(A→B) =P(B│A) (6.3) 同时满足最小支持度阀值，最小置信度阀值 的规划称为强规划。 项的集合称为项集。包含k个项的项集称为k项集 如果相对支持度满足预定义最小支持度阈值，则是频繁项集 。 频繁k项集的集合通常记为  由（6.3）式，有 一般而言，关联规则的挖掘是一个两步过程：（1）找出所有的频繁项集；（2）由频繁项集产生强关联规则。 从大型数据集中挖掘频繁项集的主要挑战是，这种挖掘常常产生大量满足最小阀值的项集，当阀值设定的很低时尤其如此。这是因为如果一个项集是频繁的，则它的每一个项集都是频繁的。 例 一个长度为100频繁项集{a1,a2,...a100}包含100个频繁1项集， 个频繁2项集，因此频繁项集的总个数为 个。为了克服这个困难，引入闭频繁项集和极大频繁项集的概念。  项集X的数据集D中是闭的，如果不存在真超项集Y使得Y与X在D中 具有相同的支持度计数。 项集X是数据集D中的闭频繁项集，如果X在D中是闭的和频繁的。 项集X是D中的极大频繁项集或极大项集，如果X是频繁的，并且不存在超项集Y使得 并且Y在D中是频繁的。（它的任意一个超级都是非频繁的） 例6.2闭的和极大的频繁项集。假设事务数据库只有两个事务：{a1,a2,....a100},{a1,a2,...a50}.设最小支持度阀值为1.我们发现两个频繁项集和他们的支持度即：C={{a1,a2, .....a100}：1，{a1,a2,....a50}:2}.只有一个极大频繁项集M={a1,a2, .....a100}:1。注意，我们不能断言{a1,a2,....a50}是极大频繁项集，因为它有一个频繁的超集{a1,a2, .....a100}。 闭的频繁项集的集合包含了频繁项集的完整信息。例 可以从C推出：（1）{{a2,a45}:2},是因为{a2,a45}是{a1,a2,....a50}:2}的子集(2){{a8,a55}:1},因为{a8,a55}不是{a1,a2,....a50}:2}的子集，而是{{a1,a2, .....a100}：1的子集。然而，从极大频繁项集只能断言两个集合{a2,a45}，{a8,a55}是频繁的，但不能推断它们的实际支持度计数。 6.2频繁项集挖掘方法 6.2.1 Apriori 算法：通过限制候选产生发现频繁项集 Apriori算法使用一种称为逐层有哪些信誉好的足球投注网站的迭代方法，其中k项集用于探索（k+1）项集。首先，通过每一项的计数，并收集满足最小支持度的项，找出频繁1项的集合，记为L1；然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此进行下去，直到不能再找到频繁K项集。找出每个LK需要一次数据库的完整扫描。 为了提高频繁项集逐层产生的效率，一种称为先验性质的重要