一种基于DHP算法频繁项集改进方法.doc

一种基于DHP算法频繁项集改进方法 　　【摘 要】本文给出了对于频繁项目集发现算法的一个有效改进措施，提出了基于划分技术的频繁项目集的生成技术DHPBP算法。该算法利用数据分块来储存数据库中的事务，对于每个数据分块减小数据库长度，提高扫描速度，在发现频繁项目集的过程中减少产生候选项目集的代价，从而减少了算法在挖掘过程中使用的存储空间和计算时间，对于增加事务数有良好的适应性。 【关键词】关联规则；频繁项目集；DHP；DHPBP 1 DHP算法描述（基于散列的方法） 在发现关联规则的每趟扫描中，需要使用频繁项目集Li生成候选项目集Ci+1，即合并有i-1个公共项的两个Li频繁项目集（表示为L1 *L1）。然后，扫描数据库，并统计Ci+1中每个项目集的支持度，以确定Li+1。通常，Ci中的项目集越多，确定Li的处理代价就越高。在Apriori中，C2=Li2。从C2中确定L2这一步，由于扫描整个数据库，并检查C2的支持度，所以需要花费很长的时间。DHP算法之所以采用哈希表的方法，是因为哈希表通常用于快速统计过程，通过构造一个小得多的C2，来生成更小的D3并派生C3来提高效率。随着项目集长度i的增加，Li的数量迅速减小。更小的Li又会导致更小的Ci+1，所以相应的处理时间更短。 哈希表为存储对应的哈希函数取值个数的表，便于描述算法，从概念上定义桶的数据结构。一个桶由下面三个部分组成：桶地址：即对应的哈希函数取值；桶内容：哈希表中具体存放的元素；桶计数：放入到哈希表中单元格元素的个数。 哈希表由所有桶的第三部分（即放入单元格的个数）组成。 所有的桶组成一个位向量。位向量中每一位的取值与其对应的桶内元素的个数相关。如果个数大于等于minsup，则为1，否则为0。 2 DHPBP算法 2.1 基本思想 DHP算法是以附加一个Hash表的计算和数据库表的存储空间（为了进行数据库的修剪）为代价，换取执行时间的加速。但这要求数据库可以存放在内存中，如果由于数据库过大，而不能放在内存中，那么，从磁盘上读取将浪费很多时间，而且建立Hash表的代价也是很大的。鉴于以上原因给出基于划分技术的DHP改进算法DHPBP（DHP Based Partition）。 2.2 实现过程 （1）对原始数据库D进行划分，分割成互不重叠的n块，记为D1、D2、…、Dn。 （2）由已知的最小支持数minsup-count，求出局部最小支持数minsup-counti，运用公式 minsup-counti=minsup-count*‖Di‖/‖D‖（i=1，2，…，n） （3）对每一个数据库分块Di中的事务行分解出其所有的项目集。 （4）应用哈希函数，即：h{x，y}=（（order of x）*10+（order of y））mod 7（其中order of x为x在所有取值序列中的序号），生成分解项目集对应的桶地址，并将相应的项目分配到对应的桶中。同时记录桶中元素的个数，与局部最小支持数minsup-counti作比较，大于最小支持数的记为1，小于它的记为0，得出结果位向量。 （5）将每个数据分块得出的位相量进行“析取或”运算，即设X =（xi）1×n，Y=（yj）1×n ，则定义X∨Y=（xi∨yj）1×n ，对得出的析取位相量中是0的位置进行修剪。 （6）将数据分块得到的析取位相量是1的位置对应的桶内容进行叠加，再与全局最小支持数进行比较，得到频繁项目集。 2.3 示例分析 对表1所示的事务数据库跟踪DHPBP算法的执行过程（设minsup-count=3）。 （1）由最小支持数minsup-count=3可以得出最小支持率min-sup=1/3，将事务数据库进行分块，分为三个数据块，每个数据块中各含有三个事务行（如表2-4），每个数据块的最小支持数minsup-counti=3*1/3=1。 （2）对三各表中的每个事务行的项进行分解，如表5-7所示。 （3）利用哈希函数，h{x，y}=（（order of x）*10+（order of y））mod 7（其中order of x为x在所有取值序列中的序号），生成分解项目对应的桶地址，并将相应的项目分配到对应的桶中。同时记录桶中元素的个数。如表8-10。 （4）将桶计数与局部最小支持数作比较，得到位相量X=（0，1，1，1，1，1，0），Y=（1，0，1，1，0，1，1），Z=（1，1，1，0，1，1，1），X∨Y∨Z=（1，1，1，1，1，1，1），对以上哈希表中所有的桶地址对应的内容杂凑（如表11）。 （5）将最后所得表11中的元素个数与全局最小支持度比较，得出频繁项目