数据关联分析.pptx

《数据关联分析.pptx》由会员分享，可在线阅读，更多相关《数据关联分析.pptx（75页珍藏版）》请在优知文库上搜索。

1、第7章 数据关联分析7.1基 本 概 念7.2频繁项集产生7.3规则产生7.4频繁项集的紧凑表示7.5产生频繁项集的其他方法7.6FP-growth算法7.7关 联 评 估17.1基本概念 关联分析关联分析（association analysis）用于发现隐藏在大型数据集中的令人）用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则（感兴趣的联系，所发现的模式通常用关联规则（association rule）或频繁）或频繁项集的形式表示项集的形式表示。关于。关于关联规则的几个概念：关联规则的几个概念：项集项集：项目：项目的集合，包含的集合，包含k个项的项集称为个项的项集称

2、为k-项集；项集；支持度（支持度（support）：数据库：数据库中含有这个项集的所有项目在中含有这个项集的所有项目在事事务务集中集中所占的比例。所占的比例。置信度（置信度（confidence）：出现：出现项集项集A的事务集的事务集D中，项集中，项集B出现出现的概率。的概率。频繁项集频繁项集：支持：支持度大于或等于度大于或等于min_sup的的项集。项集。2 关联规则挖掘的两个步骤：关联规则挖掘的两个步骤：频繁项集产生（支持度测试）。其目标是发现满足最小支持度阈频繁项集产生（支持度测试）。其目标是发现满足最小支持度阈值的所有项集，即频繁项集。值的所有项集，即频繁项集。规则产生（置信度测试）。

3、其目标是从上一步发现的频繁项集中规则产生（置信度测试）。其目标是从上一步发现的频繁项集中提取所有高置信度（大于等于最小置信度阈值）的关联规则，即提取所有高置信度（大于等于最小置信度阈值）的关联规则，即强关联规则。强关联规则。 在上述两个步骤中，第一步骤是关键，它将影响整个关联规则挖掘在上述两个步骤中，第一步骤是关键，它将影响整个关联规则挖掘算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生。算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生。7.1基本概念3 格结构（格结构（lattice structure）常常被用来枚举所有可能的项集。图）常常被用来枚举所有可能的项集。图中中显示显

4、示的的是是I=a，b，c，d，e的项集格的项集格。包含。包含k个项的数据个项的数据集最多产生集最多产生2k-1 个频繁个频繁项集，不包括项集，不包括空集。空集。7.2频繁项集产生4 发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度计数计数。这必须这必须比较每个比较每个候选项集与每个候选项集与每个事务。如候选事务。如候选项集包含在事务中，项集包含在事务中，则候选项集的支持度计数增加则候选项集的支持度计数增加。如。如，由于项集，由于项集 Milk，Bread 出现在事务出现在事务1，4，5中，其支持度计数将增加中，其支持度计数

5、将增加3次次。这种比较开销大。这种比较开销大。7.2频繁项集产生57.2.1先验原理 先验原理先验原理是减少候选项集的数量（是减少候选项集的数量（M）的方法之一。）的方法之一。 其基本思想是其基本思想是：如果一个项集是频繁的，则它的所有子集一定也是：如果一个项集是频繁的，则它的所有子集一定也是频繁的。例如，频繁的。例如，假定假定 c，d，e是频繁项是频繁项集，显然任何包含项集集，显然任何包含项集c，d，e的事务一定包含它的子集的事务一定包含它的子集c，d ， c，e ， d，e， c ， d和和e。这样，如果。这样，如果c，d，e是频繁的，则它的所有子集一定也是频繁是频繁的，则它的所有子集一定

6、也是频繁的。的。 反之，反之，如项集如项集是非频繁的，则它的所有超集也一定是非频繁的。是非频繁的，则它的所有超集也一定是非频繁的。7.2频繁项集产生67.2.1先验原理 如图所示，一旦发现如图所示，一旦发现a，b是非频繁的，则整个包含是非频繁的，则整个包含a，b超集的子超集的子图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝。于支持度的剪枝。7.2频繁项集产生77.2.2Apriori算法的频繁项集产生 Apriori算法算法是一种最具影响力的挖掘布尔关联规则频繁项集的算是一种最具影响力的挖掘布尔关联

7、规则频繁项集的算法。法。Apriori的命名由来是因为使用了频繁项集性质的先验知识，即的命名由来是因为使用了频繁项集性质的先验知识，即Apriori性质。性质。Apriori性质的内容是：频繁项集的所有非空子集也必须是频繁性质的内容是：频繁项集的所有非空子集也必须是频繁的。该性质通过减少搜索空间来提高频繁项集逐层产生的效率。的。该性质通过减少搜索空间来提高频繁项集逐层产生的效率。 Apriori算法利用算法利用Apriori性质，通过逐层搜索的迭代方法，将性质，通过逐层搜索的迭代方法，将k-项集用项集用于探索（于探索（k+1）-项集，来穷尽数据集中的所有频繁项集。项集，来穷尽数据集中的所有频繁

8、项集。7.2频繁项集产生87.2.2Apriori算法的频繁项集产生 特点特点：它是一个逐层算法，即从频繁它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍项集到最长的频繁项集，它每次遍历项集格中的一层。先找到频繁历项集格中的一层。先找到频繁1-项集集合项集集合Ll，然后用，然后用Ll找到频繁找到频繁2-项集集合项集集合L2，接着用，接着用L2找找L3，直到找不到频繁，直到找不到频繁k-项集，找每个项集，找每个Lk需要需要一次数据库扫描；一次数据库扫描；它使用产生它使用产生-测试策略来发现频繁项集。在每次迭代之后，新的候选测试策略来发现频繁项集。在每次迭代之后，新的候选项集由前一次迭

9、代发现的频繁项集产生，然后对每个候选的支持度项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次数是数是kmax+1，其中，其中kmax是频繁项集的最大长度。是频繁项集的最大长度。7.2频繁项集产生97.2.2Apriori算法的频繁项集产生 AprioriApriori算法的主要步骤由连接步和剪枝步组成。算法的主要步骤由连接步和剪枝步组成。连接步连接步。为找出为找出Lk，通过，通过Lk-1与自身连接产生候选与自身连接产生候选k-项集的项集的集合集合，记记作作Ck。设。设l

10、1和和l2是是Lk-1中的项集中的项集。lij表示表示li的第的第j项。假定项。假定事务或项集中事务或项集中的项按字典次序的项按字典次序排序，排序，使得使得li1li2.lik-1。执行连接。执行连接Lk-1 Lk-1；其中其中Lk-1的元素是可连接的，的元素是可连接的，如它们如它们前（前（k-2）个项相同）个项相同，即即Lk-1的元的元素素l1和和l2是可连接的，是可连接的，如（如（l11=l21） （l12=l22） . （l1k-2l2k-2） （l1k-1l2k-1）。条件）。条件l1k-1l2k-1是简单地确保不产生是简单地确保不产生重复。连接重复。连接l1和和l2产生的结果项集是产

11、生的结果项集是l11，l12，.l1k-1，l2k-1。7.2频繁项集产生107.2.2Apriori算法的频繁项集产生剪枝步。剪枝步。 Ck是是Lk的超集的超集，即即Ck的成员可以是频繁的，也可以不是频的成员可以是频繁的，也可以不是频繁的，但所有频繁繁的，但所有频繁k-项集都包含在项集都包含在Ck中。扫描数据库，确定中。扫描数据库，确定Ck中每中每个候选的支持度计数，从而确定个候选的支持度计数，从而确定Lk（即根据定义，计数值不小于最（即根据定义，计数值不小于最小支持度计数的所有候选都是频繁的，从而属于小支持度计数的所有候选都是频繁的，从而属于Lk）。然而，）。然而，Ck可可能很大，因此所涉

12、及的计算量就很大。为了压缩能很大，因此所涉及的计算量就很大。为了压缩Ck，可以，可以用用Apriori性质，性质，即即非非频繁的（频繁的（k-1）-项集都不是频繁项集都不是频繁k-项集的项集的子集，如候选子集，如候选k-项集的（项集的（k-1）-子集不在子集不在Lk-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的，从而从而从从Ck中删除。这种子集测试中删除。这种子集测试可使用可使用所有频繁项集的散列树快速完成。所有频繁项集的散列树快速完成。7.2频繁项集产生117.2.2Apriori算法的频繁项集产生 下面下面举举一个具体例子。该例基于表中的一个具体例子。该例基于表中的AllE

13、lectronics的事务数据库的事务数据库D。该数据库有该数据库有9个事务个事务，假定事务中的项按字典次序存放。假定事务中的项按字典次序存放。7.2频繁项集产生127.2.2Apriori算法的频繁项集产生 使用图使用图来来解释解释Apriori算法发现算法发现D中的频繁项集。中的频繁项集。7.2频繁项集产生137.2.2Apriori算法的频繁项集产生 挖掘布尔关联规则发现频繁项集的挖掘布尔关联规则发现频繁项集的AprioriApriori算法如下。算法如下。 算法算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项集。使用逐层迭代方法基于候选产生找出频繁项集。 输入输入：事务数据

14、库：事务数据库D；最小支持度阈值；最小支持度阈值min_sup。 输出输出：D中的频繁项集中的频繁项集L。 方法方法：L1=find_frequent_1_itemsets（D）；）；for（k=2；Lk-1；k+） Ck=apriori_gen（Lk-1）；）； for each 事务事务tD /扫描扫描D，进行计数，进行计数 Ct=subset（Ck，t）；）； /得到得到t的子集，它们是候选的子集，它们是候选 for each 候选候选cCt c.count+； Lk=cCk | c.countmin_sup；return L=k Lk；7.2频繁项集产生147.2.2Apriori算法

15、的频繁项集产生procedure apriori_gen（Lk-1：frequent（k-1）-itemsets）for each 项集项集l1 Lk-1 for each 项集项集l2 Lk-1 if（l11=l21） . （l1k-2l2k-2） （l1k-1l2k-2）then c= l1 l2； /连接步：产生候选连接步：产生候选 if has_infrequent_subset（c，Lk-1） then delete c； /剪枝步：删除非频繁的候选剪枝步：删除非频繁的候选 else add c to Ck；return Ck；procedure has_infrequent_sub

16、set(c：candidate k-itemsets；Lk-1：frequent(k-1)-itemsets)/使用使用Apriori知识知识for each（k-1）-subset s of c if s Lk-1 then return TRUE； return FALSE；7.2频繁项集产生157.2.3支持度计数 支持度计数用以支持度计数用以确定在确定在apriori-gen函数的候选项剪枝步骤保留下来的函数的候选项剪枝步骤保留下来的每个候选项集出现的频繁程度。每个候选项集出现的频繁程度。 计算支持度的主要方法有计算支持度的主要方法有两种两种：一是一是将每个事务与所有候选项集进行比较，并且更新包含在事务中的将每个事务与所有候选项集进行比较，并且更新包含在事务中的候选项集的支持度计数。这种方法的计算候选项集的支持度计数。这种方法的计算成本很高成本很高，尤其当事务和候，尤其当事务和候选项集的数目都很大时。选项集的数目都很大时。或或枚举枚举每个每个事务包含事务包含的项集，的项集，并利用并利用其其更新更新对应的候选项集的支持度。对应的候选项集的支持度。7.2频繁项集产生167.2.3支