维普资讯 http://www.cqvip.com 第１７卷计算机技术与发展 Ｖ０１．２００７年６月 第６期 Ｊ７ Ｎ。．６ ＣＤＭＰＵＦＥＲＴＥＣＨＮＯＬＯＧＹ ＡＮＤＤＥＶＥＬＯＰＭＥＮＴ Ｊｕｎ． ２００７ 基于Ｈａｓｈ表的关联规则挖掘算法的改进 卢云彬，曹汉强 （华中科技大学电子与信息工程系，湖北武汉４３００７４） 摘要：经典的Ａｐｒｉｏｒｉ算法在大项目集的挖掘过程中因为重复搜索导致效率低下。提出一种改进的Ｈａｓｈ表结构应用于 ＤＨＰ算法中的项目集存放，定义新的Ｈａｓｈ函数确定项目集的存放地址，并基于新的Ｈａｓｈ表结构，以并行挖掘的方式优化 关联规则算法的剪枝过程。实验结果表明，与Ａｐｆｉｏｆｉ算法相比，文中的方法可以更好地节省存储空间，提高挖掘效率。 关键词：数据挖掘；关联规则；Ａｐｆｉｏｉｆ算法；ＤＨＰ算法；Ｈａｓｈ表 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２００７）０６—００１２—０３ Ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｈａｓｈ Ｔａｂｌｅ ＬＵ Ｙｕｎ—ｂｉｎ，ＣＡＯ Ｈａｎ—ｑｉａｎｇ （Ｄｅｐｔ．ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ｎａｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｃｌａｓｓｉｃａｌＡｐｒ￣ｒｉ ａｌｇｏｒｉｔｈｍ，ｍｉｎｉｎｇｌａｒｇｅｉｔｅｍｓｅｔｓｉｓｉｎｅｆｆｉｃｉｅｎｔ ｂｅｃａｕｓｅｏｆ ｒｅｐｅａｔｅｄ ｓｃａｎｎｉｎｇ．Ｉｎｔｈｉｓｐａｐｅｒ，ｄｅｖｅｌｏｐ ａＤ ａｌｇｏ— ｒｉｔｍｈＤＨＰｗｉｔｈｉｍｐｒｏｖｅｄＨａｓｈｔａｂｌｅｆｏｒ ｅｆｆｉｃｉｅｎｔｌａｒｇｅｉｔｅｍｓｅｔ ｇｅｎｅｒａｔｉｏｎ；Ｔｈｅ ｓｔｏｒｅｄ ａｄｄｒｅｓｓ ｏｆｉｔ￣ｒｎｓｅｔｓｉｓ ｄｅｔｅｒｍｉｎｅｄ ｂｙ ａ ｎ Ｉ－ｈｓｈ ｆｕｎｃｔｉｏｎ．Ｂａｓｅｄ Ｏ１１ｔｈｅ ｎｅｖ￣Ｈａｓｈｔａｂｌｅ．ｃａｎ ｕｓｅ ｐａｒａｌｌｅｌｍｉｎｉｇｎｔｏｉｍｐｒｏｖｅ ｐｒｕｎｉｇｎ ｐｒｏｃｅｓｓｉｎ ａｓｓｏｃｉａｔｉｏｎｖａｌｅｓ ａｌｇｏｒｉｔｍｈ．Ｆｒｏｍｔｈｅ ｅｘｐｅｒｉ・ ｍｅｎｔ ｒｅｓｕｌｔｓ．ｔｈｅｍｅｔｈｏｄｉｎｔｈｉｓｐａｐｅｒｃａｎ＆ａｖｅ１Ｔｌｏｒｅ ｓｔｏｒｉｎｇ ｓｐａｃｅ ａｎｄ ｅｎｈａｎｃｅｍｉｎｉｇｎ ｅｆｆｉｃｉｅｎｃｙ ｃｏｍｐａｒｅｄｗｉｔｈＡｐｒｉ￣ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｍｉｎｉｇｎ；ａｓｓｏｃｉａｔｉｏｎ ｒｉｄｅｓ；Ａｐｒｉｏｒｌ ａｌｇｏｒｉｔｈｍ；ＤＨＰ ａｌｇｏｒｉｔｈｍ；Ｈａｓｈ ｔａｂｌｅ Ｏ引 言 掘过程中导致重复搜索的问题，首先提出了ＤＨＰ（Ｄｉ— 近年来，数据挖掘技术引起了越多越多的关注。 ｒｅｃｔ Ｈａｓｈｉｎｇ ａｎｄ Ｐｒｕｎｉｇｎ）算法【３Ｉ，ＤＨＰ算法利用直接 关联规则算法是数据挖掘的一个重要研究方向，自其 哈希修剪技术，快速发现频繁项集，提高搜索效率。 提出后就一直受到重视，它直接反映出项目集中数据 ＪｏｈｎＤ．Ｈｏｌｔ和ＳｏｏｎＭ．Ｃｈｕｎｇ对上述两种经典算法及 间的潜在关联，通过概率统计得出最常见的情况，用以 其改进算法做了研究综述－４ Ｊ，并应用到文本数据库中 指导以后的决策，以及判断新的行为是否合法，后者应 进行比较，发现在数据量增大后，ＤＨＰ算法相对于传 用在入侵检测中有十分重要的意义。 统Ａｐｆｉｏｆｉ算法效率有很大提高。 关联规则算法有很多，Ａｇｒａｗａｌ Ｒ．最早提出了经 文中提出了一种新的ＤＨＰ算法Ｈａｓｈ表结构，通 典的Ａｐｒｉｏｒｉ算法－１】，该算法解决了关联规则的基本定 过选择有序Ｈａｓｈ树结构存放频繁项目集，能有效提高 义和要求，但瓶颈是效率低；其后，他又作了很多改进 挖掘效率，优化了Ａｐｒｉｏ￣算法生成大项目集的剪枝过 效率的研究，提出候选集是大项目集的充要条件是当 程，同时，极大地节省了大项目集存储空间，在时间和 且仅当它的所有子集都是大项目集－２ Ｊ，该性质决定了 空间两方面同时改进了频繁项目集的挖掘效率。 大项目集生成的迭代步骤，可以提前去掉无效的ｋ一 项目集，避免生成无用的（ｋ＋１）一项目集，改进了候 １ Ａｐｒｉｏｒｉ算法和ＤＨＰ算法的分析 选集的筛选过程。Ｊ．Ｓ．Ｐａｒｋ等人针对Ａｐｒｉｏｒｉ算法挖 Ａｐｆｉｏｆｉ算法是一种先验概率算法，它利用了频集 特性的先验知识，采取层次顺序搜索的循环方法来完 收稿日期：２００６—０９一ｌ１ 基金项目：国家科技攻关项目（２００４ＢＡ￣１ １１３０６） 成频繁项集的挖掘工作－５ Ｊ，这一循环方法主要利用ｋ ～作者简介：卢云彬（１９８２一），男，湖北大冶人，硕士研究生，研究方向 项集来产生（ｋ＋１）一项集。具体描述如下：首先找出 为信息安全、数据库系统及其应用；曹汉强，博士，教授，博士生导 频繁１一项集，记为Ｌ１；然后利用Ｌ１来挖掘Ｌ２，即频 师，研究方向为数字图像处理、信息安全、激光全息防伪技术。 繁２一项集；不断迭代循环，直至无法发现更多的频繁 维普资讯 http://www.cqvip.com 第６期 卢云彬等：基于Ｈａｓｈ表的关联规则挖掘算法的改进 ・ ｌ３・ （ｋ＋１）一项集 ＋１为止。Ａｇｒａｗａｌ Ｒ证明了大项目集 址由修正的Ｈａｓｈ函数得到，例如，项目集Ｂｃ按Ｈａｓｈ 函数Ｈ（ｘ，Ｙ）＝（Ｉ（ｘ＊２＋ｙ）Ｉ ｍｏｄｌｉ）＋１计算得 到地址８，填充表格时发现地址８已经填人了项目集 ＡＥ，那么再按Ｈａｓｈ函数Ｈ（Ｘ， ）＝（１（ｘ＊２一ｙ）ｌ 性质：大项目集的任一子集也一定是大的＿６ｊ。在这个性 质下，迭代过程中增加了候选集 ，由大项目集 产 生下一层候选集 川，再通过剪枝过程筛选出大项目 集形成 ＋１。 Ａｐｒｉｒｏｒｉ算法存在一个重复扫描数据库的问题，即 为了对候选集 剪枝，不得不对 中的每一项依次 作判断，要回到数据库搜索其支持度是否满足大于判 决门限Ｓ的要求，这个重复扫描占用了大量的时间开 ｍｏｄｌｉ）＋１计算得到地址２，如发现该地址为空，则将 项目集ＢＣ填人，同时在地址８的链表中填人２，表示有 一个冲突项已经填人到新的地址２中。如果地址２又被 另一个项Ａ，占据，因为已无法从Ｈａｓｈ函数再得到新 的值，此时用链表结构将ＢＣ直接填人地址８后面的空 销。 ＤＨＰ算法是利用直接哈希修剪技术的算法，用来 减少数据传输量。对候选项目集构建Ｈａｓｈ表后，直接 从Ｈａｓｈ树中获取各项目集的支持度，而不必重复搜索 数据库，能有效减小大项目集的体积，有效减少数据传 输量，有效减少数据库扫描趟数。 ２基于有序Ｈａｓｈ表的ＤｔｔＰ算法 如前所述，由于候选集中每一项的判断都需要到 前一层查询，所以前一层频繁集在Ｈａｓｈ表中的结构会 对查询工作有很大的影响，有序快捷的存储能有效改 进查询效率。因此，文中提出了一种有序Ｈａｓｈ表结 构，能够直接通过Ｈａｓｈ函数定位所需要的项目是否存 在，而不必逐项搜寻。 有序Ｈａｓｈ表结构设计如下：为了在Ｈａｓｈ表中书 写方便起见，项目集采用简写形式，如ｉＢ Ｃ｝简写为 ＢＣ。 （１）同层项目集存放在连续的位置，即在某一段 或某－－Ｎ表格中，存放的均为 ，在另一段或者另一 列表格中存放 川； （２）在同层项目集中，用Ｈａｓｈ函数决定其存放位 置，这样可以直接得到项目集的存储地址进行读取，而 不需要逐项寻找。 Ｈａｓｈ函数定义为：Ｈ（ｘ，Ｙ）＝（Ｉ（Ｘ＊２±Ｙ）Ｉ ｍｏｄｌｉ）＋１ 其中，ｘ为项目集的首项，ｙ为后面所有项，将各项按 照字母顺序对应如表１所示。 表１ 各数据项对应的转换数值 例如，Ｈ（Ａ，Ｂ）＝（Ｉ（１＊２＋２）Ｉ ｍｏｄｌ１）＋１＝ ５，Ｈ（Ｂ，ＣＤ）＝（Ｉ（２＊２＋３＋４）Ｉ ｍｏｄｌ１）＋１＝１ 不同项可能得到相同Ｈａｓｈ地址，需要用链表结构 来存储冲突项。为了减少因避免冲突而预留太多的存 储空间，文中采用了修正Ｈａｓｈ函数值与链表结合的方 法，链表中存放冲突项新的Ｈａｓｈ地址，此新的Ｈａｓｈ地 位，同时在地址指针中填人地址８，表示该冲突项填在 了地址８的后面链表中。 对于数据项远超过１１的情况，会导致很多冲突数 据项在此公式下找不到空位置，在这种情况下应该先 修正Ｈａｓｈ公式，即除数１１改为略大于数据项总量一半 的第一个质数。文中采用的Ｈａｓｈ地址由Ｈ（ｘ，Ｙ）＝ （Ｉ（ｘ＊２＋ｙ）Ｉ ｍｏｄｌｉ）＋１计算得到，修正函数只是 用来查找一个新地址存放冲突数据项，以减少空间浪 费。 ３实验仿真与数据分析 ３．１文中算法得到的Ｈａｓｈ表结构 对于包含６个事务的１～项集Ｌ ＝ｉ ｉＡ｝，ｉ Ｂ｝， ｛ｃ｝，｛Ｄ｝，｛Ｅ｝，｛Ｆ｝｝，经过连接得到全部的２一项候 选集ｃ２，根据算法，得到Ｃ２各子项存放的Ｈａｓｈ表仿真 结果如表２所示。 表２全部２一项集存放的Ｈａｓｈ表结构 Ｈａｓｈ地址 ｌ ２ ３ ４ ５ ６ ７ ８ ９ １０ ｌｌ ２一项集 ＢＤ ＢＣ ＣＤ ＤＥ ＡＢ ＡＣ ＡＤ ＡＥ ＡＦ ＢＥ ＢＦ 链表地址 ｌ ２ ４ ４ Ｏ ６ Ｏ ２ ｌ Ｏ ３ ２一项集 ＣＥ （．Ｆ ＤＦ ＥＦ 从该Ｈａｓｈ表结构可以看出，该存储方式合理地利 用了存储空间，Ｈａｓｈ函数的２次地址选择能够让每一 层空间尽量用满，而不会因为部分冲突导致链表过长 而浪费空间。 该表格的生成时间很短，而且随项目集的增多变 化并不大，因为Ｈａｓｈ地址是由函数直接计算获得，不 存在遍历过程，只需要处理冲突情况，所以时间开销很 少，但对搜索效果的提高却十分显著。在查找数据项 时，只需根据此函数确定地址，冲突项获取的新地址必 然在对应链表中，所以从该地址能判断一个数据项是 否存在于整个Ｈａｓｈ表中，需要搜索的只是一个链表， 而不必对整个表格遍历，所以节省了大量时间。 ３．２采用Ｈａｓｈ表结构对搜索的改进 文中实验的硬件条件为：Ｉ）４ ３．０Ｇ的ＣＰＵ，５１２Ｍ 维普资讯 http://www.cqvip.com ・ １４・ 计算机技术与发展 第ｌ７卷 内存，８０Ｇ并口硬盘。系统采用Ｗｉｎｄｏｗｓ ２００３ Ｓｅｒｖｅｒ， 搜索时间，点划线为文中ＤＨＰ算法下进行的Ｈａｓｈ寻 算法采用的编程语言是Ｍａｔｌａｂ。通过进行２一项集搜 址搜索时间。 索测试，得到遍历时间与项目集数量的变化曲线，如图 从图１可以看到，项目集中事务数量较少时，增加 １所示。 事务导致时间开销的增大不明显。但是在项目集变得 很大时，遍历时间开销的增大幅度将呈非线性的幂函 数曲线变化，而采用Ｈａｓｈ表存储结构后的搜索时间依 然保持较低的平缓变化。 从图２可以看出，采用Ｈａｓｈ表结构的ＤＨＰ算法 可以改进Ａｐｎｏｎ算法挖掘大项目集的效率，不论设定 多少支持度，都能保证在更短的时间内完成全部项目 集的挖掘。 ４结论 文中对ＤＨＰ算法中的Ｈａｓｈ表进行了改进，并通 项目集数量 过实验明了文中的Ｈ￣ａｓｈ表结构能够有效地提 图１搜索时间随项目增多的变化 高项目集的搜索效率，更快地确定项目是否属于频繁 图１横坐标表示项目集数量的变化，纵坐标表示 项。同时，采用Ｈａｓｈ函数能够高效地利用存储空间， 运行时间的变化。２一项集的数量从５开始变化到 减少因为冲突项而出现的预留空间浪费。不同层的项 １００，采用存放在普通表格和文中提出的Ｈａｓｈ表结构 目集将存放在不同表格中，可以进一步减少冲突项的 分别进行了两次实验。前者实验结果为实线，后者实 出现。这些改进进一步提升了ＤＨＰ算法的挖掘效率， 验结果为点划线。 更快地产生全部大项目集，为生成全部关联规则节省 在对全部的２一项集挖掘后，得到如图２所示的 了大量的时间。 仿真结果，其中横坐标表示设定的最小支持度，纵坐标 表示运行时间，单位为秒。本实验的测试环境是在２ 参考文献： ［１］ＡｇｒａｗａｌＲ，ＩｍｉｅｌｉｎｓｋｉＴ，ＳｗａｍｉＡ．Ｄａｔａｂａｓｅｍｉｎｉｎｇ：ａ ｐｅａｏｒ－ 一项集为５００时作的大项目集挖掘，其中虚线为候选 ｒｉｉＲｒｌｃｅ ｐｅｒｓｐｅｔｃｉｖｅ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ ａｎｄＤａｔａＥｎｇｉｎｅｅｒｉｎｇ，ＩＥＥＥ 集的输入时间，实线为Ａｐｒｉｏｒｉ算法下进行的顺序遍历 Ｔｒａｎｓａｃｔｉｏｎｓ，１９９３，５（６）：９１４—９２５． ［２］ Ａｇｒａｗａｌ Ｒ，Ｉｍｉｅｌｉｎｓｋｉ Ｔ，Ｓｗａｍｉ Ａ．Ｍｉｎｉｇｎ ａｓａｚ￣ａｔｉｏｎ ｒｕｌｅｓ ｂｅｔｗｅｅｎ ｓｅｔｓ ｏｆ ｉｔｅｍｓ ｉｎ ｌａｒｇｅ ｄａｔａｂａｓｅｓ［Ｊ］．ＡＣＭ ＳＩＧＭＯＤ Ｒｅｃｏｒｄ，１９９３，２２（２）：２０７—２１６． ［３］Ｐａｒｋ Ｊｏｎｇ Ｓｏｏ，Ｃｈｅｎ Ｍｉｎｇ—Ｓｙａｎ，Ｙｕ Ｐ Ｓ．Ｕｓｉｇｎ ａ Ｈａｓｈ— ＢａｓｅｄＭｅｔｈｏｄｗｉｔｈＴｒａｎｓａｃｔｉｏｎＴｒｉｍｍｉｇｎｆｏｒＭｉｎｉｎｇＡｓｍｅｉ— ａｔｉｏｎ Ｒｕｌｓｅ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｇｎ，ＩＥＥＥ Ｔｒａｎｓａｔｃｉｏｎｓ，１９９７，９（５）：８１３—８２５． ［４］Ｈｏｌｔ Ｊ Ｄ，Ｃｈｔｍｇ Ｓ Ｍ．Ｅｆｆｉｃｉｅｎｔ ｍｉｎｉｎｇ ｏｆ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｓｅ ｉｎ ｔｅｘｔ ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｇｎｓ ｏｆ ｔｈｅ ｅｉｇｈｔｈ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎ￣ｅｒｅ／１ｃｅ ｏｎ ｈｄｏｒｍａｔｉｏｎ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｍａｎａｇｅｍｅｎｔ．［ｓ． Ｉ．］：ＡＣＭＰｒｅｓｓ，１９９９：２３４—２４２． ［５］Ｈａｎ Ｊｉａｗｅｉ，Ｋａｒｎｂｅｒ Ｍ．ＤＡＴＡ ＭＩＮＩＮＧ Ｃｏｎｃｅｐｔｓ ｎａｄ Ｔｅｅｈ— ｉｎｑｕｅｓ［Ｍ］．北京：高等教育出版社，２００１． ｔ｜Ｓ ［６］ＤｕｎｈａｍＭＨ．数据挖掘教程［Ｍ］．郭崇慧，田凤占，靳晓明 图２全部２一项集的挖掘时间 译．北京：清华大学出版社，２００５． （上接第儿页） 社，１９９０． 出版社，２００３． ［４］何迎晖，钱伟民．随机过程简明教程［Ｍ］．上海：同济大学 ［６］Ｓｏｎｋａ Ｍ，Ｈｌａｖａｅ Ｖ．图像处理、分析与机器视觉［Ｍ］．北京： 出版社，２００４． 人民邮电出版社，２００２． ［５］ＣｏｓｔｌｅｍａｎＫＲ．Ｄｉｇｉｔａｌｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ［Ｍ］．北京：清华大学
