（电路与系统专业论文）数据采掘中的关联规则采掘技术研究.pdf

摘 西琶3 吼2 为 j s u p p o r t ( y )( 2 2 ) ( i i ) 若x c y ，如果x 是非频繁项目集，则y 也是非 频繁项目集 ( i i i ) 若x c _ y ，如果y 是频繁项目集，则x 也是频繁 项目集 证明 地散靛灿：一c x 产裔 华中师范大学学位论文用纸 ( i ) 对任意的事务t ，因为x c _ v ，就有y c t j x t 。因此， a x a y ，得到 s u p p 洲( z ) 2 茜独一咿) _ 裔 得证。 ( i i ) 由x 是非频繁项目有 s u p p 州心) _ 裔砌s 卿州 因为x c _ y ，由( 2 2 ) 式知 s u p p o r t ( x ) s u p p o r t ( y ) 由此可知 s u p p o r t ( y ) s u p p o r t ( y ) 由可知 s u p p o r t ( x ) _ m i n s u p p o t ，即x 是频繁项目集 得证。 定义2 4 若x 、y 为项目集，且x n y = g ，蕴涵式x j y 称为 关联规则，x 、y 分别称为关联规则x j y 的前提和结论。项目集 ( x u y ) 的支持率称为关联规则x y 的支持率，记作： s u p p o r t ( x = y ) ， s u p p o rt ( x j y ) = s u p p o rt ( x u y ) ( 2 3 ) 关联规则x j y 的置信度记作：c o n f i d e n c e ( x j y ) ， c o n fid e n c e ( x = y 】：s u pp o r t ( xu y ) s u pp o r t ( x ) 通常用户根据采掘需要指定的最小置信度记为 m i n c o n f i d e n c e 支持率和置信度是描述关联规则的两个重要概念，前者用于 华中师范大学学位论文用纸 衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联 规则的可信程度。一般来说，只有支持率和嚣信度均较高的关联 规则才可能是用户感兴趣的、有用的关联规则。 定义2 5如果s u p p o r t ( x j y ) m i n s u p p o r t 且 c o n f i d e n c e ( x j y ) m i n c o n f i d e n c e ，称关联规则x j y 为强规 则，否则称关联规则x j y 为弱规则。 2 3 关联规则采掘问题的分解 关联规则采掘的任务就是要采掘出d 中所有的强规则。强规 则x y 对应的项目集( x u y ) 必定是频繁项目集( 由定义5 和 ( 13 ) 式可知) ，由定理l ( i i ) f t l ( 14 ) 式可知：频繁项目集( x u y ) 导出的关联规则x j y 的置信度可由频繁项目集x 和( x u y ) 的 支持率计算。因此，可以把关联规则采掘划分为两个子问题： ( 1 )根据最小支持率找出数据集d 中的所有频繁项目集； ( 2 ) 根据频繁项目集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频繁项目 集，是关联规则采掘的中心问题，是衡量关联规则采掘算法的标 准，目前大多数有关关联规则采掘问题的研究都是针对第一个子 问题而展开的：第二个子问题可直接( 1 1 ) 式和( 1 4 ) 式求解。 23 1 根据频繁项目集产生强规则 由( 2 4 ) 式知，强规则的产生过程如下： 对于每个频繁项目集f ，产生f 的所有非空真子集； 对于f 的每个非空子集m ，如果 塑丝警1 0 0 忉i n c o n f i d e n c p ，则输出强规则 “m = ，( f - m ) ”， 推论对项目集f 和其子集m 和m ，若m 三m ，则关联规则 m j e m 的置信度不可能大于关联规则m j f - m 的置信度。 证明 由鱼m 、鱼m 且m m ，根据定理2 1 ( i ) 知 s u p p o r t ( m ) s u p p o r t ( m ) s u p p o r t ( f m ) s u p p o r t ( 0 m ) 而 ” 华中师范大学学位论文用纸 唧叫c m 蛳邮= 篇鬻署 s u p p o r t c m j 删2 篙普孑 因此 s u p p o n ( m 7 = ，f m ) s u p p o r t ( m = ，f - m ) 得证 在根据频繁项目集产生强规则时，利用推论22 可以减少计 算量，进一步提高强规则的产生效率。 232 关联规则采掘的基本模型 综上所述，关联规则采掘的基本模型可用图21 表示 图2 1 中d 为数据集，a l g o r i t h m 1 为频繁项目集的搜索算法， a l g o r i t h m 一2 为关联规则的产生算法，r 为采掘出的关联规则集合。 用户通过指定m i n s u p p o r t 、m i n c o n f i d e n c e 分别与算法 a l g o r i t h m - 1 和a l g o r i t h m 2 交互，并通过与r 的交互对采掘结果 进行解释和评价。 2 4 关联规则采掘算法 现有的各种关联规则采捌算法大致可分为搜索算法、层次算 法、数据集划分算法、抽样算法等。 2 4 1 搜索算法 搜索算法的庄读入数据集中的每条事务时，对该事务中包含 l s 华中师范大学学位论文用纸 的所有项目集进行处理，因此搜索算法需计算数据集d 中所有项 目集的支持数。a i s 算法【”1 、s e t m 算法【删、以及以建格算法为 主体的关联规则采掘算法【3 8 1 都是这种搜索算法。 搜索算法只需对数据集次扫描就可以找出所有的频繁项目 集，对每一条包含n 个项目的事务就将产生2 “个项目集，数据集 d 中包含的项目数很大时，所需计算和存储的候选项目集的数量 往往非常庞大。因此，该类算法只适合于项目集数量相对较小的 数据集中的关联规则采掘。 2 4 2 层次算法 以a p r i o r i 算法为代表的层次算法是按含项目数自小而大的 顺序寻找频繁项目集( 数据集中含项目数最大的频繁项目集称为 最大频繁项目集) 。a p r i o r i 算法在第k 次扫描数据集时找出所有 的频繁k 项目集，第k + 1 次扫描数据集时的候选项目集由所有的 频繁k 项目集通过连接运算产生】。a p r i o r i 算法需扫描数据集的 次数等于最大频繁项目集的项目数。a p r i o r i t i d 算法在a p r i o r i 算 法的基础上对数据集进行修剪，以减少扫描数据库的时间，但对 数据集的修剪需要额外的计算和i o 操作。d h a 算法采用哈希技 术对数据集和候选项目集进行修剪，特别是对候选2 项目集的修 剪特别有效口“。a p r i o h y b r o 算法是a p r i o r i 算法和a p r i o r i t i d 算法 的融合，该算法开始采用a p r i o r i 算法，然后在每次扫描完数据集 之后计算修剪后的数据集的大小；若修剪后的数据集可在内存中 进行处理，则切换至a p r i o r i t i d 算法直到找出出所有的频繁项目 集。 以a p r i o r i 算法为代表的层次算法可以产生相对较小的候选 项目集，扫描数据库的次数由最大频繁项目集的项目数决定。因 此，这类算法适合于最大频繁项目集相对较小的数据集中的关联 规则的采掘。 2 4 3 数据集划分算法 数据集划分算法包括p a r t i t i o n 算法、d i c 算法【6 5 1 等，这些算 法将整个数据集划分成可以存放在内存中进行处理的数据块，以 节省访问外存的i o 开销。p a r t i t i o n 算法只需要对整个数据集进 行两次扫描，d i c 算法在数据块划分恰当时可以通过两次扫描数 据集找出所有的频繁项目集。 数据集划分算法的候选项目集的数量一般比a p r i o r i 算法的 1 9 ￥ 女鞫隧瓣螽善董一，涵鑫赫，? 滋蕊溷潮瞄麓蕊鞠蕊爵磊 华中师范大学学位论文用纸 候选项目集的数量大，增加各数据块的数据扭曲性可以减少候选 项目集数量。数据集划分算法是各种并行关联规则采掘算法和分 布式关联规则采掘算法的基础。 2 44 抽样算法 抽样算法通过对数据集d 抽样产生抽样数据集d 5 ，找出抽 样数据集中的频繁项目集作为候选项目集，然后扫描数据集d 确定其中的频繁项目集【：。 如何计算负边界以找回部分遗漏的频繁项目集是抽样算法的 关键。抽样算法适合于要求采掘效率较高，而采掘准确性不太高 的环境下的关联规则采掘。 2 5 关联规则采掘的改进和扩展模型 关联规则采掘的基本模型是针对事务数据库中的关联规则采 掘问题而提出来的，其它数据集或软、硬件环境下的关联规则采 掘必须对基本模型进行扩展，以完成采掘任务或提高采掘效率。 2 5 1 针对数据集的扩展 关联规则采掘的基本模型所能处理的数据集只能是事务数据 库，缺乏对其他数据集，如包含连续属性的关系数据表、不完整 数据集的处理能力，数值关联规则采掘和不完整数据集中的关联 规则采掘分别针对这些数据集进行了扩展1 6 1 1 州m 】。对存在大量频 繁项目集的数据集，采用一般的关联规则采掘算法寻找其中所有 频繁项目集需要的计算量异常庞大，t o b e r t oj b a y a r d o 等人提出 了长模式采掘可- 苗效地从含较多频繁项目集的数据集中找出最大 频繁项目集【6 ”。 2 5 2 针对应用环境的扩展 在实际的数据采掘任务中，其应用环境是多样的，可以充分 利用已有的软、硬件条件提高关联规则采掘的效率。 随着关系型数据库应用日益广泛，s q l 技术使得数据的访问 和获取变得简单而迅速。关系数据库中的关联规则采掘，可以利 用s q l 操作来实现。一方面，s q l 本身是经过合理优化的，另 一方面整个或部分采掘任务可以在服务器上完成 6 6 】。利用s q l 技 术实现关联规则采掘是种较好的解决方案，如s e t m 算法就是 由s q l 实现的m 】。 华中师范大学学位论文用纸 此外，可以利用大型并行机的高速处理能力来进一步提高关 联规则的采掘效率m l 。并行关联规则采掘算法就是针对大型并行 机而设计的并行算法。通过分布在网络上的多台微机的协同工作 来完成同一采掘任务，是提高关联规则采掘效率的另一种方法【l ”。 分布式关联规则采掘算法对劂络环境下实现关联规则采掘需要解 决的通讯和协同问题进行了研究 2 5 3 关联规则采掘方式的改进 关联规则采掘的基本模型在数据集更新( 事务数的少量增 减) 时，需要对整个数据集重新进行采掘。关联规则采掘的增量 算法对数据集数据集中的事务增加时的关联规则采掘进行了优 化，算法只需要找出新增数据集中的频繁项目集并对原数据集扫 描一次就可以确定更新后的整个数据集中的新的频繁项目集 【1 0 】。 o n l i n e 关联规则采掘是针对关联规则采掘的基本模型的封闭 性而作的改进。关联规则采掘的基本模型的封闭性是指在寻找频 繁项目集的过程中，用户难以与采掘算法交互。o n l i n e 关联规则 采掘使用户在第一次扫描数据集的任何时候都可以根据需要调整 最小支持率和最小置信度，以采掘出所需的关联规则，该算法只 需对数据集扫描两次。 为了采掘出用户希望了解的关联规则，r n g 等人提出了限 制关联规则采掘i ”。限制关联规则采掘通过对项目或项目集的 限制来聚焦整个采掘过程。项目限制可以使算法只采掘出项目集 i i 中的各个项目间存在的关联规则；项目集限制根据项目的附 加信息和用户的需要对候选项目集进行修剪，针对不同类型的项 目集限制，修剪过程可以在扫描数据库之前一次完成或在每次扫 描完数据集后进行。限制关联规则的采掘由于项目数或候选项目 集数量的减少而降低了寻找频繁项目集所需的计算量，并可由此 对关联规则采掘算法进行优化：通过规定项目或项目集限制降低 了算法的搜索空间，可以使关联规则采掘算法在较短的时间内对 用户的采掘要求作出反应，增强了关联规则采掘算法的交互性 p 7 6 。 2 6 关联规则采掘技术的研究方向 国内外在关联规则采掘方面的研究已经取得了较大的进展， 2 l 华中师范大学学位论文周纸 但关联规则采掘技术在有些方面仍然存在着不足，需要进一步的 研究和更好的解决方案。 2 61 关联规则采掘算法效率的提高。 关联规则所面对的是大规模的数据集( 事务数和项目数巨 大) ，而且，数值关联规则采掘中由于涉及到连续属性的属性值 划分和合并使得项目数量急剧增加州。目前的大多数关联规则采 掘算法在这些情况下效率较低，必须对关联规则采掘算法作进一 步的研究。 2 6 2 关联规则的兴趣度 最小支持率和最小置信度并不能确保所采掘出的关联规则都 是用户所感兴趣的，其中可能包含许多冗余、无意义的关联规则， 而且支持率和置信度较高的关联规则有可能是常识性的知识【4 ”。 制定好的关联规则兴趣度计算标准可以使采掘出的关联规则更能 满足用户的需要：同时还可用于优化关联规则采掘算法，提高关 联规则采掘的效率【4 ”。 通过对关联规则的聚类可以对采掘出的关联规则进行整理，+ 便于用户的浏览：通过制定规则模板【7 9 】、元规则【4 2 】1 、项目或项 目集限制可以减小算法的搜索空间，采掘出满足这些要求的关联 规则，但这些方法并不能防止采掘出冗余、无意义的关联规则。 确定数据采掘结果的兴趣度的方法分为客观方法和主观方法。数 值关联规则的兴趣度计算方法、基于近邻的关联规则兴趣度计算 方法对确定关联规则兴趣度的客观方法进行了研究。一条关联规 则对用户来说是否为兴趣的，往往还与用户知识密切相关，具有 较大的主观性，有必要对确定关联规则主观兴趣度的方法进行研 究。 2 ，6 - 3 关联规则采掘算法的交互性 目前的关联规则采掘过程一般是在用户规定最小支持率和最 小置信度等参数之后，通过扫描数据集找出所有的频繁项目集， 并根据频繁项目集生成关联规则，最后将采掘出的关联规则提交 给用户。由于频繁项目集的寻找比较费时，用户在指定最小支持 率、最小置信度等参数之后，不得不等待较长的时间才能获得采 掘结果。如果用户不满意所得到的采掘结果，则需要修改最小支 持率、最小置信度等参数并再次运行关联规则采掘算法。用户要 得到满意的结果可能需要上述过程的多次反复，因此需要较长的 f 、4 2 2 、p 每o a 然纛赫毫觥。，砖漱添船i 瀚麓麓豳黼隧蕊溺嚣繇嚣 华中师范大学学位论文用纸 等待时间。虽然上述过程可以优化，但仍然难以达到理想的结果。 增强关联规则采掘算法与用户的交互性可以减小算法的搜索空 间，提高采掘效率【1 6 l ，采掘出满足用户需求的关联规则。o n l i n e 关联规则采掘技术为提高关联规则采掘算法的交互性而提出的一 种可行的解决方案”“。 2 64 关联规则采掘技术与其他技术的融合 关联规则采掘技术的研究吸引了许多其它领域的研究者从事 该问题的研究，使得关联规则采掘可以吸收其他领域的研究成 果。如关联规则采掘可以利用s q l 技术来进行数据访问、数据获 取甚至进行关联规则的采掘口0 1 ：元规则指导的数据立方中的关联 规则采掘则是数据立方技术与关联规则采掘技术的有机融合。关 联规则采掘技术与数据立方、数据仓库、空间数据库系统 7 4 】等数 据库技术的融合将推动关联规则采掘技术进一步走向实用化。 此外，关联规则采掘技术不仅可直接作为一种决策支持的手 段，还可以应用到其它数据采掘技术中。如关联规则采掘技术可 用于时间序列数据分析【j l 【二1j 【删、分类以及决策树归纳【州等数据采 掘技术中。 2 7 小结 本节通过定义项目集、支持率、置信度、强规则及项目集关 系定理等内容介绍了关联规则采掘的基本概念：对搜索算法、层 次算法、数据集划分算法、抽样算法等各种关联规则采掘算法进 行了比较：分析了各种关联规则采掘的改进和扩展模型；最后指 出了关联规则采掘技术的研究方向。 华中师范大学学位论文用纸 第三章典型的布尔关联规则 采掘算法 在关联规则采掘问题提出时，关联规则采掘所针对的数据集 主要是事务数据库。事务数据库中的关联规则采掘问题称为布尔 关联规则采掘，采掘出的关联规则称为布尔关联规则。表31 是 一个事务数据库的例子。 表3 1 一个事务数据库的例子 事务号包含在事务中的项目 l o o a ，c ，d 2 0 0 b ，c ，e 3 0 0 a ，b ，c ，e 4 0 0b e 3 1 布尔关联规则采掘算法的设计 在关联规则采掘的两个子问题中，强规则的产生比较容易、 直接，所需的计算量相对较小；而频繁项目集的寻找要复杂得多， 一股所说的关联规则采掘算法通常指的就是频繁项目集的搜索算 法。 最直接的频繁项目集搜索算法可以这样设计：从i 中产生所 有可能的项目集，并为每个项目集分配一个初值为零的计数器， 然后顺序扫描d 中的每条事务，并把包含在当前事务中的所有项 目集的计数器值增l 。在扫描完数据集d 中的全部事务后，即可 根据各个项目集的计数器值确定所有的频繁项目集。 上述算法仅需要对数据集d 扫描一次就可以找出其中的所有 频繁项目集，但困难在于i 中可能的项目集有2 | i i 1 个，如果每 个项目集和其计数器仅需要l b y t e 的存储空间，当i l = 1 0 0 0 时共 需要2 ”1 0 “b y t e 的存储空间，这是目前的微机系统难以承受 的a 因此，必须设计效率更高、更有效的算法，减少需要计算支 持率的项目集数量。 定义3 1 一种关联规则采掘算法为找出所有的频繁项目集 而需要计算支持率的项目集称为候选项目集 露黼器嚣荔毛：如i 基滋瓣。懑滋酒翻遴赢，矗瀛骶辨藏 华中师范大学学位论文用纸 由候选项目集的定义可知，候选项目集的数量必须大于或等 于频繁项目集的数量，否则将遗漏部分频繁项目集。 从时间复杂度和空问复杂度来考虑，设计布尔关联规则采掘 算法需要解决的主要问题有两个： ( 1 ) 减少t o 操作，关联规则采掘的数据集有时可达g b 甚至t b 数量级，频繁的i o 操作必将影响关联规则的 采掘效率，减少i o 操作主要是减少扫描数据集d 的 次数： ( 2 ) 降低候选项目集的数量，使其与频繁项目集的数量接 近。候选项目集数量的降低可以节省为处理部分候选 项目集所需的计算时间和存储空间。 一般来说，减少扫描数据集的次数和减少候选项目集的数量 是一对矛盾，如何处理这一对矛盾，寻找最佳的平衡点是提高布 尔关联规则采掘算法效率的关键。 3 2 砧s 算法 a j s 算法是a g r a w a l 等人在1 9 9 3 年提出的最早的布尔关联规 则采掘算法，该算法给出了解决布尔关联规则采掘问题的基本思 路，是以后发展起来的其它关联规则采掘算法的基础。 3 2 1a j s 算法的主要过程 定义3 2 对项目集x 、y ( x n 忙，项目集z ( z = x u ”称为项 目集x 的扩展项目集，若l y l = k ，则称项目集z 为项目集x 的k 扩 展项目桑。 定义3 3 若项目集m 和h 都是项目集x 的扩展项目集，则称 项目集x 为项目集m 和n 的父集，m 、n 互为同胞项目集。 在, a d s 算法中，候选项目集通过对扩展项目集的扩展产生， 每次扫描数据集时将被扩展的项目集称为初始项目集。a i s 算法 如算法3 1 所示，其中c 为候选项目集的集合，f s 为初始项目集 的集合，f 为频繁项目集的集合。 算法3 1 ；a i s 算法 输入：d ，m i n s u p p o r t m i n c o n f i d e n c e ： 输出：所有强规则的集合： 主要过程： ( i ) f 口0 ：f s ；o ； 华中师范大学学位论文用纸 一 ( 2 ) w h i l e ( f s ：# ( 乃) ( 3 )c = o ； ( 4 )f o r ( 每条事务t e d ) ( 5 )f o r ( 每个f f s ) ( 6 ) i f ( f c _ t ) ( 7 )c r = e x t e n d ( f , d ( 8 )f o r ( 每个c f c 0 ( 9 )i f ( e f c ) ( i o ) c f c o l i n t h - ； ( 1 1 ) e l s e ( 1 2 )c o u n t = 0 ： ( 1 3 )c = c + c f ； f 1 4 ) f s = o ： ( 1 5 ) f _ f u c c k 等_ m i n s u p p o r t ) ； ( 1 6 ) f s = g e n e r a t ef r o n t i e r ( c ) ( 1 7 ) ( 1 8 ) r e t u r n ( f ) ： 在a i s 算法中，f s 在第一次扫描数据集之前初始化为；在 扫描数据集的过程中，每读入一条事务，就通过e x t e n d ( ) 过程对 每个初始项目集进行扩展，并由产生的扩展项目集构成候选项目 集；在完成对整个数据集的一次扫描之后，舢s 算法根据各候选 项目集的计数器值来计算各自的支持率、确定其中的频繁项目 集，同时由g e n e r a t e过程产生下次扫描数据集时的初始frontier() 项目集集合。 3 2 4 候选项目集的产生 在! m s 算法中，每次扫描数据集时的候选项目集通过对扩展 项目集的扩展而得到( 为了讨论方便，假设每个项目集和每条事 务中的项目都是有序的) ：令t 为当前读入的事务，f 为包含在t 中的初始项目集，项目集s = t f = - i ，k ，i 。) ，则根据t 对初始项 目集进行扩展产生2 - 个扩展项目集： x u s s l ( 眶s ) a ( s o ) ) ( 1 - i - 2 9 ) 对每个项目集x u s ( 1 9 2 - ) 都要判断其是否包含在候选项目 集集合c 中，若x u s 。c ，就为之分配一个初始为1 的计数器并 将其加入到候选项目集的集合中，否则将该项目集对应的计数器 值加l 。 , m s 算法的候选项目集产生过程e x t e n d o 如下 华中师范大学学位论文用纸 e x t e n d ( x ：项目集t ：数据集中的事务) i = 项目集x 中序号最大的项目： f o r ( 每个项目i k ( i k t 且i k 的序号大于t ) ) 产生候选项目集x + i k ： 耐项目集x + i 。被预测为频繁项目集) e x t e n d ( x + i k , t 1 ： 在a i s 算法中一旦产生了某个候选项目集，在后续的数据集 扫描过程主送都必须计算该候选项目集的支持数。如果能对新产 生的候选项目集的支持率进行预测，在对初始项目集进行扩展的 时找出并放弃不可能成为频繁项目集的扩展项目集，就可以减少 候选项目集的数量，提高关联规则的采掘效率。 由定理21 可知：若预测项目集x us ( s = “，o ，i k ) ，1 k 印) 为 非频繁项目集，则项目集x w s ( s i ，i ，i 。) 且s e q ，1 k n ) f lo ) k = l ： f 1 1 )读入数据块d 。： ( 1 2 )f o r ( 每个t e d k ) ( 1 3 ) ( 1 4 )f o r ( 每个c e c ) ( 1 5 )i f ( c t ) f 1 6 ) cc o u n t 。h 。： ( 1 7 ) ( 1 8 )f o r ( 每个c c ) ( 1 9 ) ( 2 0 )i f ( ( ( n + k - cg e t l e r _ n u m ) m o d n ) = n ) ( 2 1 ) ( 2 2 ) 啦箐m i n s u p p o r f ) f 2 3 ) f = f + c ； ， f 2 4 1c = c c ： ( 2 5 ) ( 2 6 ) e l s e ( 2 7 ) i 坟面夏面c i c o u 面n t 瓣m i n s u pp o ，f ) r 2 8 1s = s + c ； ( 2 9 ) ( 3 0 )由s 中的所有项目集产生新的候选项目集，这些项目集 的g e n e r _ n u m 设置为k 计数器c o u n t 初始化为o ： ( 3 1 ) k + + ： ( 3 2 ) w h i l e ( 没有新的候选项目集产生，且已经计算所有候选项目 集在d 中的支持率) 3 4 3d i c 算法中的t r i e 树 d i c 算法需要一种数据结构来管理不同大小的项目集，这种 数据结构应可以实现下述功能： ( 1 ) 可以管理包含不同项目数的项目集： ( 2 ) 能够动态增加新的候选项目集； ( 3 ) 可以为每个项目集分配计数器并附加其它状态描述信息 ( 如指示某项目集是否已经扫描完整个数据集的状态信息 萋蠢瓣懿穗。喾量般j 一：# 囊随滋溺溪翻麟霪酊摹慧弱i 蟊 华中师范大学学位论文用纸 一一 等) ； ( 4 、查找效率高。 a p r i o r i 算法中的哈希数不能实现上述功能，在d i c 算法中采 用t r i e 树作为候选项目集的存储结构，它具有如下性质： f 1 ) 每个项目集中的项目是排序的； f 2 ) 每个项目集对应t r i e 树中的一个结点； ( 3 ) 空集为根结点；所有i 项目集与根结点相连；k ( k 1 ) 项目 集所在结点与其k 1 前缀构成的项目集所在结点相连，并 由其最后一个结点标识。 存储有项目集 a ) 、 b j 、 c ) 、 d ) 、 a ，b 、( a c 、 丸d ) 、 b ，c ) 、( b ，d 、( c ，d 、 a ，b ，c 、 b ，c ，d 的t r i e 树如图3 4 所 示。 根 图3 4d 3 4 4 数据分布对d i c 算法的影响 d i c 算法所采用的候选项目集动态产生技术要求项 j 集在各 个数据块中的分布比较均匀。若最大频繁项目集包含的项目数为 k ，则只要扫描开始k 个数据块即可产生大部分候选项日集，在 后续数据块的扫描中产生的新候选项目集的数量极少，因此只要 再次扫描到第k 个数据块时就可以找出所有的频繁项目集。但是 如果各个数据块中的数据分布不均匀，在扫描各个数据块时都会 产生新的候选项目集，因此将延长对数据集的扫描时间，最坏情 3 8 华中师范大学学位论文用纸 一。 况下可能需要对数据集扫描k 次，使算法的效率下降。 3 4 5 数据块大小的选择 数据块大小的选择将对d i c 算法的效率产生极大的影响。数 据块越大，则各个数据块中的频繁项目集的集合与整个数据集中 的频繁项目集的集合越接近，因此候选项目集的数量也相对较 少，但大的数据块使得扫描数据集所需时间总量增加：相反，数 据块越小，则扫描各个数据集所需时间总量较少，但是候选项目 集的数量较大。 3 5d p a r 算法 d p a r ( d a t ap a r t i t i o na s s o c i a t i o nr u l em i n i n g ) 算法是本文提 出的一种利用数据集本身所具有的聚类倾向对数据集进行划分， 并利用层次算法从划分形成的数据块中进行关联规则采掘的布尔 关联规则采掘算法。此外，d p a r 算法很容易修改成可应用于大 型并行处理机的并行关联规则采掘算法。 3 51 数据集的聚类和划分 在数据集划分算法中，不同的划分方法将极大地影响算法的 采掘效率。最有效的数据集划分算法是利用数据聚类技术，对整 个数据集中的事务进行聚类，由各个事务聚类将整个数据集划分 为各个数据块。对事务进行聚类一般需要多次扫描整个数据集， 当数据集中包含的事务数较多时，所需代价太高。 在数据集中各个项目之间往往存在着分类层次关系，当数据 集的平均事务长度l 卅与项目数i 引相差较大( 即l 引 i 丁j ) 时，可 lj t。 。 ii 以利用分类层次关系对数据集中的事务进行聚类，设根据分类层 次关系可以将项目集合划分为m 类：i ，、i ：、i 。，可以将数据 集中的事务划分为m + 1 个数据块d ，、d ：、d 。、d 。，其中数 据块d 。、d ：、d 。与类别i ，、i ：、k 对应，d 。是所有不能 被正确划分到数据块d ，、耽、d 。中的事务形成的数据块。 对数据集中的任意一条事务t ，按下述方将其划分至数据块d 、 d 、d 。、d 。7 中的一个数据块中： ( 1 ) 若存在i ， i i , i 。i 。 使得 l t - i 1 姐l i m ，c 【为整数( 31 ) 华中师范大学学位论文用纸 则将事务t 划分至数据块d 。中； ( 2 ) 若对所有的1 1 、i ：、i 。和事务t ( 31 ) 式均不成立，则 将事务t 划分至数据块d 。中。 其中仪指定的整数，为保证一条事务不会被划分至多个数据块中， a 需满足 c t m i n ( 1 i 小| i ：| 、叫)( 32 ) c c 的选择将决定划分的精度。 对划分形成的数据块d 、d