《高维数据中频繁项集生成算法的研究》.pdf

《《高维数据中频繁项集生成算法的研究》.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、，1．．．．．．．．口同维数据中频繁项集生成算法的研究姜请超(河北软件职业技术学院，保定07101)0)【摘要】在关联规则的挖掘中，频繁项集的生成是影响算法性能和效率的关键因素。随着数据维数的增大，传统的关联规则挖掘算法显然无法适应高维数据挖掘的需求。本文针对高维数据中关联规则的挖掘I"-1题提出了．SplitMtrix_Apriori算法。该算法通过生成数据库的布尔矩阵减少了在频繁项集的生成中需多次扫描数据库所带来的开销，从根本上提高了算法的效率。【关键词】数据挖掘Apriori算法．splitMtrix_Apriori算法一七_-1的列，和删除支持度计

2、数小于最小支持度的项所对应的行、引言在关联规则算法中最著名的算法是Apriori算法，是A—向量。然后迭代上面的过程，得到每一个分组的最大频繁集grawal和Srikantt于1994年提出的，也是一个广度优先的算(<_，)。然后再由每一组中最大频繁项集中的项重新组成布尔法。Apriori算法采取了自底向上、分层搜索策略，这意味要找矩阵，迭代上述的过程直至没有频繁项集生成时算法结束。到k_项集，就需要做k次迭代。虽然Apriori算法能够很好的2、SplitMtrix_Apriori算法描述计算频繁集挖掘出关联规则，但其算法的效率不是太好。因为(1)Ste

3、pI、建立事务数据库Boolean矩阵。扫描数据库D，Ariori算法的候选集都很大，通过Hash技术可以压缩候选K然后将其转化为一个压缩的事务布尔矩阵。行向量代表项一候选集，在cA川)zD一1Ⅳ函数部分减少计算开销；事(1tem)，列向量代表事务，同时并建立一个行向量对事务计数。务压缩主要是利用关联规则计算的一些定理，来裁剪一些冗扫描一条事务记录，然后将其转化为一条代表事务的列向量。余事务，降低在计算频繁集时扫描交易数据库的记录范围。本然后，核对该条向量是否存在矩阵中，如果存在则将对应的事文从分组和压缩矩阵的角度对高维数据中频繁项集的挖掘算务计数加l；如

4、果不存在，将该向量加入矩阵，并将该事务计数法进行了讨论。设置为l。在布尔矩阵中相同的事务只有一条记录用相应的事二、算法依据的主要定理务计数来表示该事务的真实的记录数。如果事务数据库D定理2．1在事务数据库D中，事务记录豫包含的最大项拥有rn个项和n条事务记录，经过扫描后生成m行n列的布集A，而且IAI=C，如果c<2，则可以删除豫所对应的列向量尔矩阵Dmxn，其中每个元素的按式2生成。fdik，dik，⋯⋯．．dik}T。(2)Tc(s)为行向量负责为每一个事务出项的频数计数，该证明：在事务豫中，其包含的最大项集A，则其对于任意行向量起着压缩矩阵的作用。S

5、tep2、对事务数据库矩阵进行分项集B，BA组。为了减少在频繁项集的生成过程中由于数据维数过高而’．．1B{≤lAl，IAl≤2增加的时间开销，本算法采取了分组执行的策略。根据式3确‘．．IBl≤2定的策略进行分组。·。．B不会是任何一频繁集(K>2)。(3)Df为分组后产生的事务数据库的子矩阵，综合子矩阵·．．事务豫对于计算，_频繁集(K>2)时没有任何意义，可列向量的个数不超过100。以删除。Step3、生成子矩阵的l一频繁集。通过公式4计算事务数根据定理2．1可得出如下推论：据库子矩阵Dl中每个项集的支持度sup(／i)，如果sup(1i)比最推论l

6、：在事务数据库D中，事务记录豫包含的最大项小支持度min_sup小，那么li为非频繁1一项集，该项在计算集A，而且Ial=~，在汁算频繁集时，如果c

7、的是为了提1一频繁集，利用穷举法生成2一频繁候选集，并按公式5对生高高维数据中关联规则的挖掘效率，弥补现有的却riori算法成的2一频繁候选集计算支持度sup(1i，Ij)其中row(Di)、row在进行关联规则挖掘时需多次扫描数据库的缺陷。基于这种fDj)为项li，／j对应行向量。如果sup(I~，Ij)d,于rain_sup则将思想，litMtrix_Apriori算法开始是扫描交易事务数据库，然该候选集划入2一非频繁集，否则划入2一频繁集。后将数据库转化成一个布尔类型的矩阵。在转化过程中，可(5)Step4、生成子矩阵的k-，频繁集。根据(_】)一频

8、繁集，利采用标记同一事务出现的频数的方法对重复出现的事务进行压用穷