《1 引言》
1 引言
数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物, 是国际上数据库和信息决策系统最前沿的研究方向之一。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。关联规则是数据挖掘领域中的一个非常重要的研究课题, 广泛应用于各个领域, 既可以检验行业内长期形成的知识模式, 也能够发现隐藏的新规律。有效地发现、理解、运用关联规则是完成数据挖掘任务的重要手段, 因此对关联规则的研究具有重要的理论价值和现实意义。
R. Agrawal 等人
《2 关联规则基本原理》
2 关联规则基本原理
设I = {i1, i2, …, im} 是m个不同的项目组成的集合, 给定一个事务数据库D, 其中的每一个事务T是I中一组项目的集合, 即T⊂I, T有一个唯一的标志符TID。若项集X⊂I且X⊂T, 则事务集T包含项集X。一条关联规则就是形如X⇒Y的蕴涵式, 其中X⊂I, Y⊂I, X∩Y=∅。关联规则X⇒Y成立的条件:a. 它具有支持度s, 即事务数据库D中至少有s % 的事务包含X∪Y。b. 它具有置信度c, 即在事务数据库D中包含X的事务至少有c %同时也包含Y。
1) 找出存在与事务数据库中的所有强项集X的支持度support
(X) 不小于用户给定的最小支持度minsup, 则称X为强项集 (large itemset) 。
2) 利用强项集生成关联规则。
对于每个强项集A, 若B⊂A, B≠∅, 且support (A) /support (B) ≥minconf, 则有关联规则B⇒ (A-B) 。
第2个子问题比较容易, 其生成算法可参考文献
《3 关联规则算法概述及典型算法分析》
3 关联规则算法概述及典型算法分析
R. Agrawal等提出了关联规则挖掘问题以后, 一批有效的挖掘关联规则的算法在过去几年中得到了长足的发展。到目前为止, 其主要研究方向有:基于规则中涉及到的数据维数的挖掘算法, 基于规则中数据的抽象层次的挖掘算法, 基于规则中处理变量类别的挖掘算法, 其他关联规则算法等。
《3.1基于规则中涉及到的数据维数的挖掘算法》
3.1基于规则中涉及到的数据维数的挖掘算法
按照关联规则中涉及到的变量数目可以把关联规则分为单维关联规则和多维关联规则。单维关联规则只涉及数据的一个维度 (即一个变量) ;而多维关联规则要处理多维数据, 涉及多个变量。
《3.1.1 单维关联规则》
3.1.1 单维关联规则
1) 经典频集方法
在算法AIS中, 候选强项集是在扫描数据库的过程中产生, 即在对数据库进行第k次扫描时, 候选强项集 (其中每一个元素的元素个数不一定是k个, 可以大于k) 是由第k-1次扫描所产生的边界集 (frontier set) 通过增加当前事务中的项得到, 同时计算候选强项集中的元素支持数, 直到某一次扫描所产生的边界集为空时停止运算, 第k次扫描所产生的边界要大于本次扫描生成的强项集, 该算法的缺点在于生成的候选强项集太大。
算法 Apriori 利用“在给定的事务数据库D中, 任意强项集的子集都是强项集;任意弱项集的超集都是弱项集”这一原理对事务数据库进行多次扫描, 第一次扫描得出大1-项集L1 , 第k (k>1) 次扫描前先利用第k-1次扫描的结果 (即大k-1项集Lk-1 ) 和函数 Apriori-gen产生候选大k-项集Ck , 然后在扫描过程中确定Ck中每个元素的支持数, 最后在每次扫描结束时计算出大k-项集Lk, 算法在当候选大k-项集Ck为空时结束。该算法所产生的候选强项集比算法AIS小得多, 提高了算法效率。
2) DHP算法
J. S. Park 等
3) 频集算法的优化方法
虽然Apriori算法自身已经进行了一定的优化, 但是在实际的应用中, 还是存在不令人满意的地方, 于是人们相继提出了一些优化的方法。
a. 基于划分的方法 Savasere等
b. 基于采样的方法 基于对数据集前一遍扫描得到的信息, 对此仔细地做组合分析, 可以得到一个改进的算法。Mannila等
Brin等
c. 减少交易的个数 R. Agrawal等人提出的AprioriTid和AprioriHybrid
d. 基于兴趣度的关联规则挖掘算法 现有的关联规则挖掘算法主要考虑可信度和支持度的阈值, 如经典的Apriori算法和DHP算法。然而过去的一些应用发现, 从一个数据库中很容易产生大量规则, 但是其中的大部分对用户来说可能是不感兴趣的或者是没用的, 甚至还可能引起误导。文献
e. 基于约束的规则挖掘 基于约束的关联规则的主要目的是发现更有趣的、更实用的和更特别的关联规则。文献
综上所述, 基于约束的规则挖掘
对于基于Apriori 的频集方法, 即使进行了优化, 但一些固有的缺陷还是无法克服。Apriori 的算法及其优化算法可能产生大量的候选集。当长度为1的频集有10000个的时候, 长度为2的候选集就会成指数倍增长, 其候选集个数将会超过107。如果要生成一个很长的规则时, 要产生的中间元素也是巨大量的。对此可采用FP树算法解决。
FP树算法采用了一种 FP-growth 的方法
4) 增量式关联规则挖掘算法
关联规则增量更新主要有3个问题:a. 在给定的最小支持度和最小置信度下, 当一个新的数据集db添加到旧的数据库DB中时, 如何生成db∪DB中的关联规则。b. 在给定的最小支持度和最小置信度下, 当一个数据集db从旧的数据库DB中删除时, 如何生成DB∪db中的关联规则。c. 给定数据库DB, 在最小支持度和最小置信度发生变化时, 如何生成数据库DB中的关联规则。
所有的关联规则更新问题都可以归结为以上3种情况或它们的组合。解决关联规则更新问题的最直观和最简单的方法就是运用挖掘算法对更新后的数据库重新进行挖掘。这种方法虽然实现简单, 但是它没有充分利用己经得到的结果, 效率较低。
D. W. Cheung等
算法 IUA 采用了一个独特的候选强项集生成算法 IUA-GEN, 在每一次对数据库DB扫描之前生成较小的候选强项集, 从而提高了算法的效率。它也要求上一次对数据库进行挖掘时发现的强项集L=∪
单维关联规则算法除了以上介绍的之外, 还有J. Roberto等
《3.1.2 多维关联规则挖掘》
3.1.2 多维关联规则挖掘
它指关联规则涉及2个或2个以上变量。根据是否允许同一个维重复出现 , 多维关联规则又可以细分为维间关联规则 (不允许维重复出现 ) 和混合维关联规则 (允许维在规则的左右同时出现 ) 。比如“年龄 20至 30, 喜欢郊游→喜欢游泳”就是混合维关联规则。维间关联规则和混合维关联规则的挖掘还要考虑不同的字段种类, 即类别数据与数值数据。对于类别资料, 一般关联规则算法都可以处理, 而对数值型资料, 就需要将这些资料转换成类别资料才可以处理。
处理数值型字段的方法基本上有以下几种:
1) 数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。
2) 数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间, 落在其中则为1, 反之为 0。这种分法是动态的。得出的规则叫布尔数量关联规则。
3) 数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离因素。得出的规则称基于距离的关联规则。
4) 直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析, 并且结合多层关联规则的概念, 在多个层次之间进行比较从而得出一些有用的规则。得出的规则称为多层数量关联规则。
《3.2基于规则中数据的抽象层次的挖掘算法》
3.2基于规则中数据的抽象层次的挖掘算法
基于要挖掘的数据库中的概念层次和发现单一概念层次中的关联规则的算法, 学者们提出了许多高效发现一般或多层关联规则的算法, 主要有:Han等的ML-T2L1及其变种 ML-T1LA, ML-TML1, ML-T2LA
算法ML-T2L1的基本思想是首先根据要发现的任务从原事务数据库生成一个根据概念层次信息进行编码的事务数据库, 利用这个具有概念层次信息的新生成的数据库, 自顶向下逐层递近地在不同层次发现相应的关联规则。它实际上是算法Apriori在多概念层次环境中的扩展。根据在发现高层关联规则过程中所用的数据结构和所生成的中间结果的共享方式不同, 算法ML-T2L1有三个变种:ML-T1LA, ML-TML1, ML-T2LA。
算法Coumulate的基本思想与Apriori完全一样, 只是在扫描到事务数据库某一事务时, 将此事务中所有项的祖先加入到本事务中。并加入3个优化:a. 对加入到事务中的祖先进行过滤。b. 预先计算概念关系T中的每一个项的祖先, 得到项集与其祖先的对照表T*。c. 对既包含项集X又包含X的祖先的项集进行剪枝。
算法Stratify基于“若项集X的父辈不是强项集, 则X肯定不会是强项集”的事实进行设计。其基本思想为:在概念层次有向非循环图中, 定义没有父辈的项集X的深度depth (X) = 0, 其他项集的深度为: (max ({depth (X′) /X′是X的父辈}) +1) 。算法要对事务数据库进行多遍扫描, 第k (k≥0) 次扫描计算深度为k (k≥0) 的所有项集Ck的支持数, 并得出深度为k (k≥0) 的大项集Lk。在第k (k≥1) 次扫描前, 对Ck进行剪枝, 即删除Ck中那些祖先包含在Ck-1-Lk-1中的元素。围绕着决定某些深度较大的项集是否是强项集问题, 文献
《3.3基于规则中处理变量类别的挖掘算法》
3.3基于规则中处理变量类别的挖掘算法
根据变量的类别, 关联规则分为布尔型关联规则和多值属性关联规则。多值属性又可分为数量属性 (quantitative attribute) (如年龄, 价格等) 和类别属性 (categorical attribute) (如品牌, 制造商等) 。
基于支持信任理论的关联规则挖掘布尔型描述的数据已经比较成熟。多值属性关联规则挖掘问题在文献
目前提出的挖掘多值属性关联规则的算法大多是将多值属性关联规则挖掘问题转化为布尔型关联规则挖掘问题, 即将多值属性的值划分为多个区间, 每个区间作为一个属性, 将类别属性的每一个类别当作一个属性。然后针对这些属性应用布尔关联规则挖掘算法。
如何划分区段是实现多值关联规则挖掘到布尔型关联规则挖掘转变的关键。其中有2个互相牵制的问题: 当区段的范围太窄时, 则可能使每个区段对应的属性支持度很低, 出现“最小支持度问题”;当区段的范围太宽时, 则可能使每个区段对应的属性可信度很低, 出现“最小可信度问题”。
给定一个数据库D, 多值关联规则挖掘问题就是发现所有支持度和置信度分别大于等于用户给定的最小支持度minsup和最小置信度minconf的多值关联规则。关联规则中的项目可以是数值或类别。
多值关联规则挖掘问题一般按照以下步骤完成:
1) 在每个数值属性 x 的值域[l, u]上确定划分的区间数及分割点, 确定与属性 x相关的原子集合 split (x) ;
2) 将每个〈x, lk, uk〉∈ split (x) 映射为一个逻辑属性A, 进而将所有数值属性及其值域区间映射为项目集;
3) 产生支持度大于等于最小支持度 minsup 的频繁项集;
4) 利用频繁项集产生置信度大于最小置信度 minconf 的关联规则;
5) 从所有产生的规则中确定出有趣的规则。
文献
《3.4其他关联规则算法》
3.4其他关联规则算法
除了以上列举的关联规则算法之外, 还有一些研究方向, 如: 发现关联规则的语言
《4 总结与展望》
4 总结与展望
目前, 数据库关联规则挖掘已经取得了令人瞩目的成绩, 但对下列问题进行研究将是具有挑战性的工作。
1) 开发更高效的挖掘算法
随着数据库的尺寸不断增大, 不仅增大了挖掘算法的搜索空间, 而且也增加了盲目发现的可能性。因此必须利用领域知识去提取与发现任务有关的数据, 删除无用的数据, 有效地降低问题的维数, 设计出更加有效的挖掘算法。在这方面, 基于约束的关联规则挖掘具有广阔的前途。
2) 可视化挖掘
设计一个灵活方便的用户界面, 允许用户与挖掘系统进行交互, 并对所挖掘的结果进行很好的可视化表示, 使非领域专家也能进行挖掘。
3) 各种非结构化数据的挖掘
目前大多数关联规则挖掘大多是基于关系数据库或事务数据库的算法, 设计应用于其他类型数据库 (如面向对象数据库、数据仓库、文本数据、图形图像数据、多媒体数据等) 关联规则挖掘算法也将是十分有意义的工作。
4) 并行关联规则数据挖掘
随着数据挖掘中数据量的高速增长以及大规模并行计算在数据挖掘中的应用, 由于挖掘系统本身的原因, 并行数据挖掘过程更加趋向粗粒度的挖掘, 无法实现任意程度的并行。目前在并行数据挖掘中尚有一些问题需要解决:数据量的不断增长, 维数越来越高, 数据定位问题, 数据的不对称性, 动态负载平衡, 多表数据库的数据分布和索引方案, 增量的方法, 并行的数据库管理系统与文件系统。
5) 制定更为合理的关联规则衡量评价标准
目前的关联规则衡量标准可能会发现一些冗余的、虚假的和非挖掘者关心的关联规则, 因而有必要制定一些新的衡量标准, 用来衡量关联规则挖掘算法的优劣, 但这些标准的制定可能要具体问题具体分析。
《6) 与其他系统的集成》
6) 与其他系统的集成
这里的集成包括与其他挖掘方法的集成和与其他系统 (如专家系统、决策支持系统等) 的集成。
7) 研究在网络环境下的关联规则挖掘技术
特别是在Internet上建立DM服务器, 与数据库服务器配合, 实现数据挖掘。