E4关联规则挖掘Apriori算法的研究.doc

基于关联规则挖掘Apriori算法的研究及改进吕 建 06379031（2006级 信息与计算科学（双专业）摘 要 关联规则挖掘能够发现大量数据中项集之间有意义的关联或相关联系，是数据挖掘研究的一项重要内容。在分析研究关联规则挖掘技术及其相关算法Apriori算法基础上，针对该算法存在的两个缺陷，即多次扫描事务数据库和产生大量的候选数据集，分别从减少搜索事务个数、划分、抽样和散列的方法，举出了几种改进的Apriori算法。改进后的算法都在某一程度上减少了运行开销，提高了挖掘速度，从而获得更好的性能。关键词 数据挖掘；关联规则；Apriori算法；频繁项集 Improved Algorithm Based On Apriori Mining Association Rules AlgorithmLvjian 06379031（2006 Information and Computing Sciences（Double Majors）Abstract Abundant meaningful relations and relevance among the different itemsets can be located by means of the association rules mining which is a significant topic in the data mining field. On the base of analyzing and reseaching the technique of association rules mining and the relevant Apriori algorithm which has two defects: scanning database too much and creating excessive candidate itemsets, the thesis presents several improved Apriori algorithms with decreasing amount of searching transaction, Partition, Sampling and Hash methods. The improved algorithms reduce runtime expenses to some extent, and accelerate data mining, then achieve better performance.Key Words data mining; association rules; Apriori algorithm; frequent itemset目 录1 引 言32 关联规则32.1关联规则的基本概念32.2 关联规则属性32.2.1 支持度（Support）32.2.2 置信度（Confidence）及平均置信度（Average Confidence）42.2.3 期望置信度（Expected Confidence）42.2.4 作用度（Lift）43Apriori算法43.1算法概述43.2 主要步骤53.3 算法描述53.4 算法实例63.4.1 产生频繁项集63.4.2 由频繁项集产生关联规则83.5 性能分析93.5.1 Apriori算法的时间复杂度93.5.2 Apriori算法的空间复杂度94 Apriori算法改进94.1减少搜索事务个数的方法104.1.1 AprioriTID算法104.1.2 矩阵算法104.2 基于划分（Partition）的方法134.3 基于抽样（Sampling）的方法154.4 基于散列（Hash）的方法165总结18参考文献:19致谢201 引 言随着计算机的广泛应用和数据的大量积累，如何有效地处理海量数据并从中提取有价值的信息和人们感兴趣的知识逐渐受到广泛的关注，数据挖掘（Data Mining）技术由此应运而生。数据挖掘1，也称为知识发现，是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。而数据挖掘中的一个非常重要的数据处理方法是关联规则的挖掘。关联规则反映一个事务与其他事务之间的相互依存性和关联性，从海量记录中挖掘有用的关联信息，可以帮助决策者制定决策。Apriori 算法是关联规则中的经典算法，由Rakesh Agrawal和Rnamakrishnan Srikant在1994年提出2，其基本思想3是逐层迭代寻找频繁项集，从长度为Lk的频繁集迭代地产生长度为Lk+1的候选集，再扫描数据库以验证其是否为频繁集。使用Apriori算法能够比较有效地产生频繁项集，但其代价是巨大的，特别是应用于处理海量数据时，求候选集的规模呈指数增长3，对时间和空间都是一种挑战。针对Apriori算法在实际应用中存在的问题，人们相继提出了一些改进的算法。本文对基于关联规则挖掘的Apriori算法进行研究，介绍几种优化的Apriori算法，并分析其性能。2 关联规则2.1关联规则的基本概念关联规则问题首先由Agrawal等提出，是数据挖掘领域的一个基本、重要的问题。其源于零售商的货篮分析，通过分析顾客购物货篮中的不同商品、不同项之间的联系，了解顾客的购物习惯，从而得到顾客所购商品之间的关联。这种关联的发现可以帮助零售商制定营销策略。关联规则定义2：设I= I1，I2，Im 是所有项的集合，其中Ik（k=1，2，m）称为项。项的集合称为项集，包含k个项的项集称为k-项集。一个事务T（Transaction）是一个项集，它是I的一个子集，每个事务均与一个唯一标识符Tid相联系。不同的事务一起组成了事务集D，它构成了关联规则发现的事务数据库（Transaction Database）。如果项集XT，则称事务T支持（Support）项集X，也称事务T包含项集X。关联规则是如下形式的一种蕴涵X Y，其中X I，Y I，且XY=。2.2 关联规则属性2.2.1 支持度（Support）关联规则XY 对事务集合D的支持度（Support）定义为D中包含有事务X和Y的百分比。支持度描述了X和Y这两个项集的并集XY在所有事务中出现的概率。数学表达式为support（XY）=support（XY）其中“| |”表示集合中的元素个数。2.2.2 置信度（Confidence）及平均置信度（Average Confidence）称规则XY的置信度为confidence（XY），如果confidence（XY）其中support（XY）表示规则XY的支持数，即在事务集D中包含项集合XY的所有项的数目，support（X）表示项集合X的支持数，即support(X)=|T|TD and XT|。项集Y的平均置信度（Average Confidence）4可以通过以下公式计算得出confidence(Y) =其中n是有效实例的数目，有效实例是指具有大于特定阀值的支持度和置信度的规则的实例。2.2.3 期望置信度（Expected Confidence）设事务集D中有e%的事务支持项集Y，e%称为关联规则XY的期望置信度。期望置信度描述了在没有任何条件影响时，项集Y在所有事务中出现的概率。公式表示为expectedconfidence（XY）2.2.4 作用度（Lift） 作用度是置信度与期望置信度的比值。作用度描述了项集X的出现对项集Y的出现影响程度。公式表示为 lift（XY）根据概率和条件概率的计算公式，可得下表2-12：名称描述公式支持度项集X和Y同时出现的概率P(XY)置信度项集Y在X出现下出现的概率P(Y | X)期望置信度项集Y出现的概率P(Y)作用度置信度与期望置信度的比值P(Y|X)/P(Y)表2-1 关联规则4个参数的计算公式关联规则的挖掘问题就是在事务数据库 D中找出具有用户给定的阀值最小支持度minsup和最小置信度minconf的关联规则。3 Apriori 算法3.1 算法概述Apriori算法5是一种以概率为基础的具有影响的挖掘布尔型关联规则频繁项集的算法。项集的出现频率是包含项集的事务数，称为项集的频率。如果项集满足最小支持度minsup，则称它为频繁项集（Freqent Itemset）。频繁k-项集的集合通常记为Lk。Apriori算法的关键任务是求出事务集D中的所有频繁项集，挖掘出所有频繁项集是该算法的核心，占整个计算量的大部分。另一任务是利用频繁项集生成满足最小置信度minconf的所有关联规则。该算法过程分为两步： 一为连接（类矩阵运算），二为剪枝（去掉那些没必要的中间结果）。Apriori算法在生成候选项集时利用了两个性质：一个频繁项集的任一非空子集必定也是频繁项集；一个非频繁项集的任一超集必定也是非频繁项集。3.2 主要步骤Apriori算法主要包含以下3 个步骤6：一、连接步：连接（k-l）项频繁项集Lk-l生成k项候选集Ck。可以连接的条件是两个（k-l）项的前k-2项相等并且第l个（k-l）项集的第（k-l）项比第2个（k-l）项集的第（k-l）项小。记li是Lk-1中的项集，lij表示li的第j项。设l1、l2是可连接的，即如果（l11=l21l12=l22(l1k-2=l2k-2)(l1k-1l2k-1)，则连接l1和l2产生的结果项集是l11l12l1k-2l1k-1l2k-1。由Lk-1中科连接的项集中连接所产生的k-项集的集合便是Ck。二、剪枝步：利用Apriori算法性质对k-项候选集Ck 进行剪枝。剪枝的规则是，若其中某个k-项候选集的任一（k-l）项子集不属于（k-l）项频繁集Lk-1，那么该候选k项集就不可能成为一个频繁k-项集，可以将其从Ck中删除。三、计数步：扫描事务数据库，累计k项候选集在事务数据库中出现的次数。对于一个候选项集，若某条事务记录包含该候选项集，则该候选项集出现的次数加1。最后根据给定的最小支持度生成k-项频繁项集Lk。3.3 算法描述算法：3-1 Apriori78输入：事务数据库D，最小支持度阈值minsup输出：D中的频繁项集L1) L1=find_frequent_1-itemsets(D); /发现1-项集2) for(k=2; Lk-1; k+) do3) begin4) Ck=apriori-gen(Lk-1); /根据频繁(k-1)-项集产生候选k-项集5) for all transactions tD do /扫描数据库，以确定每个候选项集的支持频度6) begin7) Ct=subset(Ck, t); /获得t所包含的候选项集8) for all candidates cCt do9) c.count+;10) end11) Lk=cCk|c.count minsup;12) end13) Answer L=kLk;Procedure find_frequent_1-itemsets(D)1) begin2) for all transactions tD do3) begin4) for each item ikt do5) ik.count+;6) end7) L1=iI|i.count minsup8) return L1;9) endProcedure Apriori-gen(Lk)1) begin2) for each itemset l1Lk do3) for each itemset l2Lk do4) begin5) if(l11=l21)(l12=l22)(l1k-1=l2k-1)(l1kl2k) then6) begin7) c=l1 l2; / 连接产生候选项集8) if Is_include_infrenquent_subset(c,Lk) then9) delete c; /除去不可能产生频繁项集的候选10) else add c to Ck+1;11) end12) end13) return Ck+1;14) endProcedure Is_include_infrenquent_subset(c,Lk)1) begin2) for each k-subset s of c3) if sLk then4) reture TRUE;5) return FALSE;6) end3.4 算法实例下面通过举例阐述上述算法，考虑某超市包含9个事务的数据库D（表3-1），即 |D|=9，并假定这些事务的项按顺序存放。设定最小支持度minsup=2/9=22%，即最小支持计数为2。3.4.1 产生频繁项集TID项列表T1I1, I2, I5T2I2, I4T3I2, I3T4I1, I2, I4T5I1, I3T6I2, I3T7I1, I3T8I1, I2, I3, I5T9I1, I2, I3表3-1某超市数据库D下图3-1是Apriori算法寻找D中频繁项集的过程。 C1 C1 L1项集I1I2I3I4I5项集支持计数I1I2I3I4I567622项集支持计数I1I2I3I4I567622扫描D 与最小 计算支支持计持计数数相比 C2 C2 L2 项集I1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I5项集支持计数I1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I54412422010项集支持计数I1, I2I1, I3I1, I5I2, I3I2, I4I2, I5442422L1连接扫描D与最小 产生候计算支支持计选集C2持计数数相比 C3 C3项集I1, I2, I3I1, I2, I5I1, I3, I5I2, I3, I4I2, I3, I5I2, I4, I5项集I1, I2, I3I1, I2, I5L2连接删除存在子产生候集 不 属 于选集C3 L2 的 项 集项集支持计数I1, I2, I3I1, I2, I522 C3 L3项集支持计数I1, I2, I3I1, I2, I522扫描D与最小计算支支持计持计数数相比 C4 C4 项集I1, I2, I3，I5项集 L3连接产生删除存在子集不候选集C4属于 L2 的项集图3-1 频繁集产生过程具体过程描述如下：(1) 寻找频繁项集1-项集 数据库中每个数据项均为候选1-项集的集合C1中的元素，对于C1中每个项集，扫描数据库中的事务，统计其支持计数。然后与最小支持计数2相比，判断是否频繁，从而确定频繁1-项集的集合L1。(2) 寻找频繁2-项集连接L1产生候选2-项集的项集C2，即C2=L1L1= I1, I2,I1, I3,I1, I4,I1, I5,I2, I3,I2, I4,I2, I5,I3, I4,I3, I5,I4, I5。由于C2中每个2-项集的所有1-项集子集都包含在L1中，所以不需要剪枝。对于C2中每个项集，扫描数据库中的事务，统计其支持计数。然后与最小支持计数2相比，判断是否频繁，从而确定频繁2-项集的集合L2。(3) 寻找频繁3-项集连接L2产生候选3-项集的项集C3，即C3=L2L2= I1, I2, I3, I1, I2, I5, I1, I3, I5, I2, I3, I4, I2, I3, I5, I2, I4, I5。然后对C2进行剪枝，例如项集I1, I2, I3的2-项子集的为I1, I2, I1, I3, I2, I3。由于项集I1, I2, I3的全部2-项子集都是L2的子集，所以项集I1, I2, I3保留在C3中。又如对另一项集I2, I3, I5，其2-项子集的为I2, I3,I2, I5,I3,I5。但I3,I5不是L2的子集，所以项集I2, I3, I5不是频繁项集，应当将其从C3中删除。对C3中其他的项集采用同样方法进行剪枝，最后得C3=I1, I2, I3, I1, I2, I5。对于C3中每个项集，扫描数据库中的事务，统计其支持计数。然后与最小支持计数2相比，判断是否频繁，从而确定频繁3-项集的集合L3。(4) 寻找频繁4-项集 连接L3产生候选4-项集的项集C4，C4= I1, I2, I3, I5，其子项集I2, I3, I5不属于L3，因此将项集I1, I2, I3, I5从C4中删除，此时C4=，算法结束。3.4.2 由频繁项集产生关联规则找出频繁项集后，就可按以下方法提取关联规则：(1) 对于每个频繁项集Li，求出其全部非空子集。(2) 对于频繁项集Li的每个非空子集S，计算规则“S(Li-S)”的置信度，即confidence（S(Li-S)）如果confidence（S(Li-S)） minconf则此产生关联规则S(Li-S)。由上例，得到数据库D的频繁项集L= I1,I2,I3,I4,I5,I1,I2,I1,I3,I1,I5, I2,I3,I2,I4,I2,I5,I1,I2,I3,I1,I2,I5。例如设定最小置信度minconf=70%，则对于集合I1,I2,I5，其非空子集为I1,I2, I1,I5, I2,I5, I1, I2, I5。计算得confidence(I1 I2I5) = scI1,I2,I5/scI1,I2=2/4 = 50%confidence(I1 I5I2) = scI1,I2,I5/scI1,I5 = 2/2 = 100%confidence(I2 I5I1) = scI1,I2,I5/scI2,I5 = 2/2 = 100%confidence(I1I2 I5) = scI1,I2,I5/scI1 = 2/6 = 33%confidence(I2I1 I5) = scI1,I2,I5/scI2 = 2/7 = 29%confidence(I5I1 I2) = scI1,I2,I5/scI5 = 2/2 = 100%与最小置信度70%相比，则得关联规则I1 I5I2、I2 I5I1和I5I1 I2。3.5 性能分析由上述实例可见，Apriori算法每次扫描都要彻底扫描整个原始数据库D，这要耗费大量的时间；而且进行连接操作而生成完整的候选项集后才进行置信度的计算，将消耗大量的存储空间。3.5.1 Apriori算法的时间复杂度虽然Ap riori算法自身已经做了一定的优化，但仍然存在算法效率不高的问题。Ap riori算法主要的时间消耗是在以下四个方面910：(1) 利用k-频繁项集连接产生k+1候选项目集，判断连接条件时比较次数太多。假设项集个数为m的频繁项集集合Lk，判断连接条件时比较的时间复杂度是O ( k*m2 )，并且其中m的值会很大。因为，假设1-项集合中项集个数为102 ，那将会产生5000个候选2-项集。最坏情况下即假设发现了一个长度为100的频繁项集，则将产生约1030 个候选项集。(2) 对任意一个c Ck判断c的k个( k-1) -子集是否都在Lk - 1中。在这个过程中，对于c在最好情况下只需扫描一次Lk 1，即第一个(k-1)-子集不在Lk - 1 中。在最坏情况下则需要一直扫描到第k次时才发现第k个(k 1) -子集不在Lk - 1 中或k个( k - 1) -子集都在Lk - 1中。于是，在平均情况下，对任意一个c Ck扫描Lk - 1次数为| Lk - 1|k /2；那么对所有候选k-项集需要扫描次数为 | Ck | Lk - 1 | k /2。(4) Apriori算法的时间复杂度为O(|C|D|)，|C|为潜在频繁项集的长度之和，|D|为事情务数据库规模。用Hi 来表示第i次生成频繁项的长度，则|C|Hi。(3) 为了得到所有Ck ( k = 1, 2, , n) 候选频繁项集的支持度，需要扫描数据库n次。3.5.2 Apriori算法的空间复杂度 在空间耗费上，设频繁项的最大长度为项的总数量m，若不对min_up限制，Apriori算法的空间复杂度为：S(m)=2m-1。项集连接方法产生的潜在频繁项集，往往随着商品种类增长而成指数增长，当数据事务大规模增加时，这种情况更加明显。一个超市中，其产品达上千种，其空间需求在最坏情况下可达21000-1。4 Apriori算法改进鉴于Apriori算法存在上述问题，许多改进的算法已经被提出来，这些算法主要为以下几类：减少搜索事务个数的方法、基于划分（Partition）的方法、基于散列（Hash）的方法和基于采样（Sampling）的方法。这些方法都在一定程度（减少扫描数据库次数、降低项集比较次数、减少空间消耗等）上优化了Apriori算法，但任何算法无论如何改进，总会存在优点和缺点，只是不同的改进算法适用于某些领域相对会有更好的性能。4.1减少搜索事务个数的方法 该思想也是由Agrawal等人提出的，通过减少用于未来扫描的事务集的大小来改进Apriori算法。现已有多种基于该方法的算法，如AprioriTID算法、矩阵算法。4.1.1 AprioriTID算法AprioriTID算法是在Apriori算法基础上改进的关联规则挖掘的经典算法。该算法的特点是在第一次对事务数据库D扫描时计算候选项集的支持度，其他各次用其上一次扫描生成的候选事务数据库Tk来计算候选频繁项集的支持度。Tk中每个成员的形式为，其中每个Xk是一个事务中潜在的k-项集。在标示符为TID的事务中，对于k=1，Tk对应于事务数据库D。对于k1，Tk由算法产生与事务t相对应的Tk成员是。如果一个事务不包含任何候选k-项集，那么Tk中就不会有该事务的项集。因此，当k的值很大时，Tk中项的数目将比事务数据库D中的事务数少很多。AprioriTID算法描述如下11：算法：4-1 AprioriTID输入：事务数据库D，最小支持度阈值minsup输出：D中的频繁项集L1) C1=candidate1-itemsets;2) L1=cC1|c.count minsup;3) T1=事务数据库D;4) for(k=2;Lk-1;k+) do bigin5) Ck=Apriori-gen(Lk-1);6) Tk=;7) 根据Tk-1和Ck生成Tk；8) 由Tk计算Ck中各项集的支持数;9) Lk=cCk|c.count minsup; /生成频繁k-项集Lk10) end11) L=kLk;4.1.2 矩阵算法矩阵算法15（Matrix algorithm）通过一次扫描数据库，得到一个由0和1组成的矩阵。采用矩阵形式，只扫描了一次数据库，减少了I/O 操作，并且突破常规的采用先假设频繁项集项目数的办法，从高阶项集着手寻找频繁项集，最大限度的减少了候选数据集的个数，大大提高了算法的效率。令项集I=i1，i2，in，集合D=t1，t2，tm，则矩阵G的元素gij定义如下：其中i=1，2，m；j=1，2，n。下面用表3-1的数据说明矩阵的生成过程。设I=I1，I2，I3，I4，I5，事务数据库为t1= I1, I2, I5，t2= I2, I4，t3= I2, I3，t4= I1, I2, I4，t5= I1, I3，t6= I2, I3，t7= I1, I3，t8= I1, I2, I3, I5，t9= I1, I2, I3。则生成的矩阵如图4-1图4-1 矩阵G算法思想如下3：对关联矩阵G的每一行进行求和，计算出所有事务项目数；选取大于等于最小支持度的项目数为测试频繁项集项目数；合并所有项目数为测试频繁项集项目数的项目集；计算其支持数，删除小于最小支持度的项目集，剩余的为我们寻找的频繁项目集；若剩余数为0，则测试频繁项集项目数-1，继续，直至找到频繁项目集。算法描述如下：输入：事务数据库D，最小支持度阈值minsup输出：D中的频繁项集L1）Cn=0; /Cn，n为最大项目数2）for each tiT do3）i=|ti|； /i 为每个事务所含的项目数4）Ci=Ci+15）for i=n to 16）If (Ci minsup) then7）k=I; /假定k = i为最大频繁项目集项目数8 ) break;9） for i=k to 1 do10）Ck=select k-itemsets /挑选出含有k个事务数的候选数据集11）for each Ci Ck do12）Lk = Ci| count(Ci) minsup ;13）If (Lk ) return Lk;算法实例：表4-1为事务数据库D，其最小事务支持数mincount=2，即minsup = 2 /8 = 25%。TID项列表T1I1, I2, I3, I4T2I2, I3T3I1, I3, I5T4I3, I4T5I1, I2T6I1, I3T7I2, I3, I4T8I2表4-1事务数据库D根据矩阵算法求频繁项集过程如下： G C1 L1项集支持计数I1I2I3I4I545631项集支持计数TIDI1I2I3I44563T1,T3,T5,T6T1,T2,T5,T7,T8T1,T2,T3,T4,T6,T7T1,T4,T7 G1 C2 L2项集支持计数I1,I2I1,I3I1.I4I2,I3I2,I4I3,I4231323项集支持计数TIDI1,I2I1,I3I2,I3I2,I4I3,I423323T1,T5T1,T3,T6T1,T2,T7T1,T7T1,T4,T7G2 C3 L3 项集支持计数I1,I2,I3I2,I3,I412项集支持计数TIDI2,I3,I42T1,T7从上述过程可以看出，矩阵在不断地压缩，从G到G1 删除了第8列，也就是将事务8删除了；从G1到G2 删除了第2，3，4，5，6列，也就是将事务2，3，4，5，6删除了。这样每一次都尽可能地删除对生成下一层候选项集不起作用的事务。在这个实例中，如果用Apriori算法就要完整地扫描3次事务数据库，而改进后的算法只要在最初构造矩阵时扫描一次事务数据库就够了，以后只需要通过扫描矩阵就可以得到频繁项集；而且矩阵是不断变小的，这样可以大大提高算法的效率。4.2 基于划分（Partition）的方法Partition挖掘算法14采用“分而治之”的方法，将事务数据库分为N个互不相交且能一次性装入内存的数据块。每次处理一个数据块，利用Apriori算法得到局部频繁项集。然后将各数据块局部频繁项集合并，生成候选项集，扫描整个事务数据库，计算这些项集的支持度，最终得到全局大项集。就整个数据库D而言，一个局部频繁项集不一定就是全局频繁项集；但是任何全局频繁项集一定会出现从所有划分所获得的这些局部频繁项集中。这一点很容易反证获得。因此可以将从N个划分中所挖掘出的局部频繁项集作为整个数据库D中频繁项集的候选项集；而在第二阶段中再次扫描整个数据库以获得所有候选项集的支持频度，以便最终确定全局频繁的项集。各划分大小和数目可以以每个划分大小能够整个放入内存为准，因此每个阶段只需读入一次数据库内容，而整个挖掘就需要两次扫描整个数据库。由于局部频繁项集的生成在内存中进行，这样就大大提高了算法的运行效率。Partition算法描述：定义一个划分PD为事务数据库D任意一个子集，并且任何两个划分都不相交，即PiPj=，ij。为划分P的局部候选k-项集的集合，为划分P的局部频繁k-项集的集合，Lp为划分P的全部局部频繁项集的集合，为全局k-项集的集合，CG为全部全局候选项集的集合，为全局频繁k-项集的集合。算法：Partition算法输入：项集I，事务数据库D，最小支持度阈值minsup输出：频繁项集L1) P = partition-database(D);2) n = Number of partitions;3) for i = 1 to n begin / Phase I4) read_in_partition(PiP);5) Li= gen_frequency_itemsets(Pi);6) end7) for (i = 2; , j = 1, 2, . . , n; i+) do8) =j=1,2,n ; / Merge Phase10) for i = 1 to n begin / Phase II11) readin_partition(PiP);12) for all candidates cCG gen_count(c, Pi);13) end14) LG = cCG|c.count minsup;Procedure gen_frequency_itemsets(P: database partition)1) = frequency l-itemsets along with their tidlists;2) for ( k = 2; ; k+) do begin3) forall itemsets L1 do begin4) forall itemsets L2 do begin5) if L11 = L21 L12 = L22 L1k-2=L2k-2 L1k-11)所占用的空间。例如：在扫描事务数据库D以便从候选项集中产生频1-项集时，就可以为每个事务记录产生所有的2-项集并将它们散列到相应的桶中，且增加相应桶的计数。对于表3-1的事务数据库D，设定哈希函数h(x,y)=(order of x)10+(order of y) mod 7，例如h(I2,I3)=(210+3)mod 7=2。如表4-117，Hash表中一个存放2-项集的桶计数若低于最小支持频度（设minsup=0.3，最小支持计数为3），则0桶、1桶、3桶、4桶中项集总个数小于3，不能成为频繁项集，2桶、5桶、6桶成为候选频繁2-项集，即C2= I2, I3，I1, I2，I1, I3。利用这样Hash表技术可以有效减少需要检查的候选k-项集数目，尤其是当k=2时。桶地址0123456桶计数2242244桶内容I1, I4I3, I5I1, I5I1, I5I2, I3I2, I3I2, I3I2, I3I2, I4I2, I4I2, I5I2, I5I1, I2I1, I2I1, I2I1, I2I1, I3I1, I3I1, I3I1, I3表4-1利用Hash表H2创建2-项集C2基于Hash方法的DHP算法描述如下：算法：DHP算法输入：事务数据库D，最小支持度阈值minsup输出：D中的频繁项集L/ Part 11) s=minsup;2) set all the buckets of H2 to zero; /Hash table3) forall transaction tD do begin4) insert and count 1-items occurrences in a hash tree;5) forall 2-subsets s of t do6) H2h2(x)+;7) end8) L1=c|c.count s, c exists in the leaf node of the hash tree;