毕业论文-基于概念格和粗糙集的数据挖掘方法研究.doc

《毕业论文-基于概念格和粗糙集的数据挖掘方法研究.doc》由会员分享，可在线阅读，更多相关《毕业论文-基于概念格和粗糙集的数据挖掘方法研究.doc（56页珍藏版）》请在三一文库上搜索。

1、毕业论文-基于概念格和粗糙集的数据挖掘方法研究 基于概念格和粗糙集的数据挖掘方法研究 博士学位论文 培 养 单 位：清华大学计算机科学与技术系专 业：计算机应用技术研 究 生：胡可云指 导 教 师：石纯一 教授副 指 导 教 师：陆玉昌 教授摘 要概念格是从数据中进行概念发现的一种数学工具, 可通过哈斯图表现出概念之间的层次关系, 已在信息检索、数字图书馆、软件工程和知识发现等方面得到应用。 粗糙集理论是处理模糊和不确定知识的一种数学工具, 已在人工智能与知识发现, 模式识别与分类, 故障检测等方面得到了较好应用。 本文就基于概念格和粗糙集的几种数据挖掘方法做了研究。 主要研究工作包括:提出一

2、种基于概念格的增量关联规则的构造方法,只需扫描数据库一次, 并且只生成最大化的项目集, 计算速度和复杂性优于apriori算法。 提出一种在概念格上提取分类和关联规则的集成算法, 可从格上生成具有任意指定后件的分类/关联规则。 给出了几条指导生成非冗余规则的规则。提出一种概念格中概念近似的方法。 通过发现概念格的性质和形式背景之间的关系, 利用粗糙集的分析方法, 建立了任意对象集合或属性集合在概念格上的近似。 这些近似可以立即被计算出来而无需生成概念格。 进一步提出一种从概念格中直接计算所需节点的方法。 对给定属性或对象集合, 利用概念格的性质, 可以直接找到格中的匹配节点或者近似节点, 进而

3、计算父节点集和子节点集。提出一种启发式约简算法。 利用属性在区分矩阵中出现的频率建立启发规则, 来寻找最小约简。 算法并不确保找到最小约简, 但是实验表明, 在大多数情况下, 可以找到最小约简。 而且在没找到最小约简的情况下, 会找到次优约简。给出一个基于采样的两阶段近似约简算法, 能找到较短和错误率较低的近似约简。提出一种多值粗糙集模型, 是属性取多值情况时粗糙集模型的扩展。 给出一种近似关系, 并证明了在粗糙熵下的逼近优于基于相似模型的定义。 实现了一个数据挖掘系统原型, 包含了主要的数据挖掘算法, 并对提出的算法进行了实验分析。 关键词: 数据挖掘, 粗糙集, 概念格, 近似, 规则,

4、约简AbstractConcept lattice is an effective tool for concept discovery from data, having the ability to embody relationship of concepts in a vivid and concise way using hasse diagram. Concept lattice has been widely used in information retrieval, digital library, software engineering and knowledge dis

5、covery. Rough set theory is a new mathematical tool dealing with vagueness and uncertainty, has found its applications in many areas such as AI, KDD, pattern recognition and classification and fault diagnostication. This paper studies several data mining methods based on concept lattice and rough se

6、t theory. Main topics includeWe present an incremental association rule mining algorithm based on Godins lattice construction algorithm. The algorithm scans database only once and generates only imal item sets. Experiment shows that it is efficient than apriori. We also propose an integrated classif

7、ication and association rule mining algorithm from concept lattice. The algorithm generates association and classification rule from the lattice with specified right hand side. We present several heuristic rules to fasten and simplify the rule generation process. Experiment shows the algorithm outpe

8、rforms c4.5 in 8 of 10 data sets. We propose a new concept approximation method on concept lattice. Using the similar idea of rough set theory and unique properties of concept lattice, upper and lower approximations of any object or attribute set can be found by exploiting meet- union- irreducible e

9、lements in concept lattice, the approximations can be performed on the fly. We show that our approach is more natural and effective than existing approach. Furthermore, we present a novel approach to compute lattice node from data without generating the whole concept lattice based on the previous wo

10、rk. Upper and lower approximations of any object or attribute set can be found directly by exploiting meet- union- irreducible elements in concept lattice. Furthermore, once the approximate nodes are found, we can explore their neighbor nodes. This avoids computing and memory burden brought by latti

11、ce generation and makes the concept lattice approach available to large database.Reduct finding, especially optimal reduct finding, similar to feature selection problem, is a crucial task in rough set applications to data mining, We propose a heuristic optimal reduct finding algorithm, which is base

12、d on frequencies of attributes appeared in discernibility matrix. Our method does not guarantee to find optimal reduct, but experiment shows that in most situations it does; and it is fast. Constructing a discernibility matrix is a very expensive operation in very large databases. A sampling method

13、for finding approximate reduct in very large database is presented. Experiment shows the method can find good approximate reducts in short time.It is observed in some practical cases that information system has multivalued attributes. The classic rough set theory has difficulties in dealing with suc

14、h cases. We present a multivalued rough set model that deal with information systems with multivalued attributes. We generalize the equivalence relation to common relation and propose a new definition of approximation that can approximate rough concept in a closer way. We prove that our definition i

15、s better than similar-based rough set model in that rough entropy based on our method is monotonic. We also show how to use our model to extract rules from data.A prototype data mining system is proposed. The system includes main data mining algorithm and procedures. The system is design to meet the

16、 following criteria: quick response, scalability, friendly user interface, extensibility, and ability to select models and parameters automatically. Keywords data mining, rough set, concept lattice, approximation, rule, reduct目 录第一章 引言11.1 数据挖掘技术概述11.2 本文的主要研究内容12第二章 概念格上的规则提取152.1 概念格理论及其研究现状152.2

17、增量式关联规则挖掘232.3 关联规则和分类规则的集成挖掘28第三章 概念格上的概念近似和节点直接生成373.1 基本定理383.2 概念近似393.3 邻近节点直接生成423.4 时间复杂度433.5 例子443.6 结论46第四章 粗糙集约简算法及多值模型474.1 粗糙集理论及其研究现状474.2 一个启发式最小约简算法554.3 基于采样的近似约简算法634.4 多值粗糙集模型68第五章 数据挖掘系统原型775.1 数据挖掘模型CRISP-DM775.2 数据挖掘系统原型785.3结论82结束语83本文工作总结83进一步的研究工作84参考文献86攻读博士学位期间的研究成果和发表的学术论

18、文100致 谢102第一章 引言数据挖掘技术是人工智能, 数据库和统计理论的结合技术, 具有较为广泛的应用前景。 专家预测数据挖掘在未来十年内会有革命性进展, 是个性化web,个人偏好分析, 实时识别和分析用户信息的关键技术。 数据挖掘的目的是从数据中找出有意义的模式。 模式可以是一组规则, 聚类, 决策树, 依赖网络或其他方式表示的知识。 一般来说, 一个典型的数据挖掘过程可以分成四个阶段, 即数据预处理, 建模, 模型评估及模型应用。 数据预处理阶段主要包括数据的理解, 属性选择, 连续属性离散化, 数据中的噪声及丢失值处理, 实例选择等。 建模包括学习算法的选择, 算法参数的确定等。 模

19、型评估进行模型的训练和测试, 对得到的模型进行评价。 这三个阶段是循环往复的过程, 直到得到用户满意的模型为止。 在得到满意的模型后, 就可以运用此模型对新数据进行解释。 数据挖掘过程是交互的和领域相关, 需要用户特别是领域专家的参予。一般一种发现算法不可能适合所有的挖掘问题的需要。 一种算法可能只适合特定的问题。 例如, 决策树分类比较适合于发现高维空间的结构但是并不适合于决策类间的边界是由二次多项式描述的问题。 因此, 没有通用的数据挖掘算法。 为特定问题挑选一个特定的合适的算法是困难的, 但是已经有了一些相关研究。本节主要讨论在数据挖掘过程中的常用的技术, 如属性选择算法, 连续属性离散

20、化, 实例选择算法, 分类算法, 聚类算法, 关联规则, 组合学习技术以及web/文本挖掘方法等。1.1 数据挖掘技术概述 属性选择方法属性选择及属性转换是数据预处理过程中广泛使用的技术。 因为许多学习算法处理高维数据有困难, 并且大量无关属性的存在, 也使得数据分析受到干扰。 属性选择的目的是找到满足特定标准的最小的属性子集。 标准通常是错误率, 不一致率, 信息熵, 依赖程度等 Liu and Motoda, 1998 。 属性选择算法和后续的学习算法之间的关系可以归为两类: wrapper方法和filter方法 Kohavi and John, 1997 。 在wrapper方法中, 属

21、性选择算法利用学习算法评估属性选择的效果, 选出具有最好学习效果的一组属性; filter方法则不考虑学习算法, 利用自己的标准进行属性选择,选择完毕再使用学习算法。 一般来说, wrapper方法的效果要好于filter方法, 但是时间复杂度也高于filter方法。在属性选择算法中, 搜索算法起着重要的作用。 搜索算法可以用搜索方向 前向, 后向, 双向 , 搜索方式 穷尽搜索, 启发式, 非确定式 及评价方式 精确度, 一致性, 依赖度等 等三个方面来分类。 使用最为广泛的是各种各样的贪婪算法。 其主要思想是不断加入使评估标准最大化的属性, 直到达到标准为止, 而不进行回溯。 此算法简单易

22、行, 在大多数情况下也能获得较为满意的结果。粗糙集理论也是属性选择的有力武器之一。 粗糙集理论对知识作了一整套的形式化描述 Pawlak, 1991 , 严格定义了知识的冗余等概念, 在此基础上提出了能够保持分类能力不变的最小属性子集约简的概念, 并给出了约简计算的一般方法。除此之外, 还有许多的属性选择算法。 例如神经网络方法, 遗传算法, 分形, 小波方法等 Liu and Motoda, 1998 。 这些方法各有特色, 但是没有一个绝对好的方法。 主成分分析 PCA 也是使用比较广泛的方法之一, 其缺点是没有考虑到类信息。 Liu and Setiono, 1995 提出一种利用 2分

23、布对连续数据离散化进而选择属性的方法。 属性离散化方法许多学习算法要求输入的属性值是离散的, 因此引出了许多连续值属性的离散化的方法, 这可以由领域专家根据经验给出相应的区间, 也可以根据某种原则对输入空间进行划分, 给出离散点进行离散化。 一般可以分为有监督和无监督的离散化方法 Dougherty, Kohavi and Sahami, 1995 , 主要区别是否利用类信息,根据是对所有连续属性同时离散化还是单个属性单独离散化,又可分为全局方法和局部方法。也可根据划分是在分类之前还是分类时做出的而分为静态方法和动态方法。最优划分区间的寻找是NP问题 Skowron and Nguyen, 1

24、995 。 常用的离散化的策略有最简单的划分策略是平分。将输入空间划分成平等的区间, 适应于输入空间中的值分布均匀的情形。自适应方法。 属性值域首先被平分成两个区间, 然后从中提取规则, 再评价规则的分类能力。 若正确分类率低于某个门限值, 则将其中一个分区再细分, 如此反复。 等频率区间法。 在用户指定划分的区间个数后, 计算每个区间的样本数 对象总数除以区间个数 。 根据每个区间的样本数去确定区间边界。 基于类信息熵的方法。 首先依照类信息墒最小的原则寻求分点q: E A,q;U |S1| Ent S1 /|U| + |S2| Ent S2 /|U|根据此分点将原始区间二分成U1和U2。

25、接着我们对U1和U2寻找最佳分点。 假定分别为q1和q2。 我们比较E A,q1;U1 和E A,q2;U2 , 若前者较大, 就划分U1, 否则U2。 这样总是划分类信息墒较大的集合。 接着递归地使用上述方法找出其他k-2个分点, 连同边界就有了k个区间。 Skowron and Nguyen, 1995 把离散化问题转化成布尔推理问题, 从而可以利用各种布尔函数化简技术寻找最优划分。这是一种全局有监督算法。此外还有许多离散化方法。 例如1R是一种有监督的基于区间方法 Holte, 1993 ; Chi2使用 2分布对连续数据离散化 Liu and Setiono, 1995 ; Zeta使

26、用zeta计算属性和类之间的关联程度来进行离散化 Ho and Scott, 1997 。同样地, 对于不同的数据类型, 上述各种方法的效果是不同的, 没有一个绝对最好的离散化方法。 实例选择方法当数据集很大的时候, 实例选择方法是必要的。 最直接的实例选择的方法是对数据集采样。 目前提出了各种各样的采样方法, 例如随机采样, 渐近采样, 自适应采样等等。随机采样是最简单也是最广泛使用的技术。 Iyengar, Apte and Zhang, 2000 使用一种自适应重采样的方法找到需要加类别标签的大数据集中的最具代表性的子集, 从而大大削减了工作量。 Provost, Jenson and

27、Oates, 1999 提出渐近采样方法, 使用越来越大的样本直到模型的精度到达标准为止。 许多研究者提出了利用采样方法提取关联规则的算法。采样通常在类别数据分布比较均匀的情况下具有良好的效果。 但是如果类别的分布极为不均匀, 可能不会得到好的结果。 DuMouchel, Volinsky and Johnson et al, 1999 给出了一个新颖的数据”挤压”技术。 挤压过程包括三个模块化的步骤:分组 grouping , 矩计算 mementizing , 和数据生成。原始数据 大规模数据集 被分成不相交的组或bins; 在每个小块中计算一系列低阶统计矩; 最后, 这些统计矩被用来产生

28、少量具有代表性的有同样统计矩的假数据。 试验的结果表明该方法好于随机抽样。组合学习方法从某种程度来说也是操纵实例的方法。 将在后面的小节中讨论。 分类算法分类算法这一类具有相当多的成员。 我们这里只讨论常见的几种算法, 即决策树, AQ, Bayes, SVM, 神经网络等。 粗糙集方法将在第二节中介绍。 .1 决策树构造一个决策树分类器通常分为两步：树的生成和剪枝。 树的生成采用自上而下的递归分治法。 如果当前训练例子集合中的所有实例是同类的, 构造一个叶节点, 节点内容即是该类别。 否则, 根据某种策略选择一个属性, 按照该属性的不同取值, 把当前实例集合划分为若干子集合。 对每个子集合重

29、复此过程, 直到当前集中的实例是同类的为止。 剪枝就是剪去那些不会增大树的错误预测率的分枝。 经过剪枝, 不仅能有效的克服噪声, 还使树变得简单, 容易理解。 生成最优的决策树同样是NP问题。 目前的决策树算法通过启发式属性选择策略来解决问题。ID3及其后续版本C4.5, C5是使用最为广泛的决策树方法 Quinlan, 1993 。 采用信息熵增益及其改进增益率进行属性选择。 增益率能克服增益偏向于多值属性特点。 CART Breiman, Frieman, Olshen and Stone, 1984 则采用基于最小距离的Gini index标准和为了克服Gini在处理很多类问题上的困难而

30、做的改进twoing rule。 事实上还提出了许多其他选择属性的方法, 例如 2统计, C-Sep, Impurity, MDL等等 Murthy, 2000 。有些研究者对决策树在超大规模数据集中的应用作了研究, 提出了一些扩展。 如SLIQ Mehta, Agrawal and Rissanen, 1996 , 它采用预排序技术来克服将所有数据放入内存的方法, 从而能处理更大的数据库, 并用了MDL剪枝算法, 使树更小和精度更高。 SPRINT Shafer, Agrawal and Mehta, 1996 , 引入了并行算法的方式, 具有良好的可扩展性。 传统的决策树在分支的时候只考虑

31、一个属性。 Brodley and Utgoff, 1995 讨论了构造多元决策树的一些问题。 提出了一些新的构造多元决策树的方法, 认为多元测试形成的决策树较单元决策树的精度高。 但是构造多元决策树的复杂度要远高于单元决策树。 许多研究者对决策树方法进行了各种各样的扩展。 如和神经网络, 模糊数学, 概率论的结合, 使用遗传算法对树的优化, 新的属性选择算法, 剪枝策略, 树的增量算法, 处理缺失值的方法等等 Murthy, 2000 。.2 AQ存在大量的基于规则的分类方法, 以及对规则进行后处理如剪枝等工作。 AQ是一种典型的基于规则的方法。 限于篇幅, 这里仅简要讨论AQ方法。AQ是一

32、种覆盖算法, 由Micalski和洪家荣提出 洪, 1997 。 算法的核心是所谓的”星”。 一个正例集合在反例集合背景下的星是覆盖所有正例而排斥所有反例的极大复合的集合。 算法就是要求得这样的最大复合。 算法从正例中的一个种子的一个选择子 属性值对 出发, 逐渐地增加选择子, 直到找到覆盖所有正例的最大复合。 在最初的AQ11基础上, AQ15增加了渐近学习, 构造学习和近似推理等功能, 成为比较成熟的覆盖算法。为了改进星算法的效率, 不进行复杂的逻辑推理, 洪家荣提出了扩张矩阵的概念及相应的AE1, AE9算法。 扩张矩阵把正例在反例之间的关系表示成矩阵, 把搜索最大复合的过程转换成在矩阵

33、中找寻一条”最大公共路”的过程。 并提出了相应的启发式搜索方法。 后来吴信东在其博士论文中推广了扩充矩阵的概念, 并提出一种改进算法HCV。值得说明的是, AQ算法和粗糙集理论有许多共同之处 Tsumoto and Tanaka, 1993 。 AQ中覆盖正例的复合对应于粗糙集理论的下近似或者说是正区域。 粗糙集中区分函数的化简结果, 等同于AQ的最大复合。 也即是说, AQ求出的规则等同于粗糙集的一致规则。 但是, 粗糙集有坚实的理论基础, 和对概念进行近似的能力, 因而应用范围更广。.3 Bayes方法贝叶斯统计分析起源于英国学者Bayes 文”An essay towards solvi

34、ng a problem in the doctrine of chances” 1763年 , 给出了著名的贝叶斯公式和一种归纳推理方法。 其后一些统计学家将其发展成一种系统的统计推断方法, 到本世纪30年代形成了贝叶斯学派, 5060年代发展成了一个有影响的统计学派。贝叶斯方法的学习机制是利用贝叶斯公式将先验信息与样本信息综合, 得到后验信息。 在数据挖掘中, 主要有两种bayes方法, 即Na?ve-bayes方法和bayes网络。 前者直接利用bayes公式进行预测, 把从训练样本中计算出的各个属性值和类别频率比作为先验概率, 并假定各个属性之间是独立的, 就可以用bayes公式和相应

35、的概率公司计算出要预测实例的对各类别的条件概率值。 选取概率值最大的类别作为预测值。 此方法简单易行并且具有较好的精度。bayes网络是一个带有概率注释的有向无环图 Heckerman, 1997 。 这个图模型能有效地表示大的变量集合的联合概率分布 物理的或bayes的 , 从而适合用来分析大量变量之间的相互关系, 利用bayes公式的学习和推理功能, 实现预测、分类等数据采掘任务。 因为关于变量组X的贝叶斯网络表示了X的联合概率分布, 所以, 一旦网络及其参数确定, 原则上可以用它来推断任何感兴趣的概率。 bayes网络也是一种适合处理不确定性知识问题的知识表示方法, 因为它可以从部分概率

36、中进行推导。构造bayes网络需要进行网络结构和网络参数两部分的学习。 为了建立建立一个表示的有向无环图最后Kohonen, ART, RNN, KBANN, RBF等等。 虽然试验表明, 神经网络在某些分类问题上具有比符号方法更好的表现, 但是神经网络用于数据挖掘主要不利之处在于无法获取显式的规则。 近年来许多学者提出了从神经网络中提取规则的方法, 典型的如KBANN Towell and Shavlik, 1994 等。 主要可以分为三类方法: 分解法, 学习法以及这两种的折衷方法。分解抽取方法的最大特点是对神经元网络内部的单个节点（隐含和输出）所表示的概念进行解释，从每个节点中抽取的规则

37、是由与此节点相连的诸输入节点来表示的，典型的分解算法有SUBSET及其改进MOFN Towell and Shavlik, 1994 , KT Fu, 1993 和RULEX Andrews, Diederich and Tickle, 1996 。学习抽取法的基本思想是将训练后的神经元网络看成一个黑箱，而把规则抽取过程看成是一个学习过程，其中所学的目标概念由神经元网络函数计算得到，而其输入变量则为神经元网络的输入特征组成。学习抽取方法主要利用符号学习算法作为学习工具，而利用神经元网络作为学习例子生成器，主要代表方法有TREPAN Craven and Shavlik, 1995 和RL Cr

38、aven and Shavlik, 1994 算法。 聚类算法一般把学习算法分成有导师 或监督 和无导师学习两种方式。 主要区别是有没有类信息作为指导。 聚类是典型的无导师学习算法, 一般用于自动分类。聚类是按照某个特定标准 通常是某种距离 把一个数据集分割成不同的类（class）, 使得类内相似性尽可能的大, 同时类间的区别性也尽可能的大。 直观的说, 最终形成的每个聚类, 在空间上都是一个稠密的区域。聚类方法主要分为平面 partition 聚类和层次聚类。 平面聚类方法通过优化一个评估函数把数据集分割成多个部分；分层聚类在不同层次上对数据进行分割, 具有明显的层次性, 算法的执行过程可以

39、用一棵层次树 多为是二叉树 来描述。 进行平面聚类, 一般用距离来量度对象之间的相似性, 典型的是欧氏距离 其它的如Mahalanobis 马氏 距离、LP距等 。 距离越大, 则相似性越小, 反之亦然。 若用对象的平均值来表示聚类的中心, 则可以用对象到中心的距离来作为分类的标准（判别函数）, 把对象分配到离它最近的一个聚类中去, 由此而导出了最小方差标准。 因此一般的基于距离的算法可以分成以下两个步骤：首先把每个对象, 分配到距离最近的一个聚类或组中去, 然后重新调整该类的中心。 反复重复这两个步骤, 直到没有对象被重新分配, 且满足判别函数（分类标准）为止。此类算法很多, 最著名的是K-

40、Means算法, 它要求用户给定聚类数目k值, 然后任意选取k个点（数据）作为类中心开始迭代, 直到满足判别函数。 层次聚类方法可以分为分治法和聚合法。 后者把实例集合看做单独的类, 自下而上地合并。 前者则相反, 开始整个的实例集作为一个类, 逐渐分裂。 层次聚类的度量两个类的标准常见的有去两个类之间最小的距离作为类距离, 也有取平均距离和最长距离的。 聚类方法具有广泛的应用。 典型的如文档的聚类 Larsen and Aone, 1999 以及一些特定领域的成功应用 Vogt, Nagel, and Sator, 1987 。 Zhang, 1997 把聚类方法扩充到超大规模数据库下, 提

41、出了birch系统。 Ganti, Gehrke and Ramakrishnan, 1999; Ada, Fu and Zhang, 1999 研究了子空间聚类问题。 但是由于聚类是无导师的学习方法, 其所研究的数据没有类别标签, 我们很难判断得到的聚类划分是否反映了事物的本质。 在 Ada, Fu and Zhang, 1999 中对此问题作了初步探讨。 关联规则关联规则是形如X Y的规则, 其中X、Y为属性-值对集 或称项目集 且XY为空集。 在数据库中若s%的实例同时包含X和Y（或s%的实例包含XY）则关联规则X Y的支持率为s%。 若c%的包含属性-值对集X的事务也包含属性-值对集Y

42、, 则关联规则X Y的置信度为c%。 一般来说, 需要找出的是支持率和置信度分别大于或等于用户指定的最小支持率 minsup 和最小置信度 minconf 的关联规则。 关联规则采掘过程可以分解为以下两个子问题：找出所有的频繁项目集及其支持率; 根据找到的频繁项目集导出所有的置信度大于或等于用户指定的最小置信度的关联规则。 第二个子问题的解决是直截了当的, 所以一般的研究集中在第一个子问题上。 关联规则的经典算法是apriori算法 Agrawal and Srikant, 1994 。 Apriori算法通过多次迭代来找出所有的频繁项目集, 在第k次迭代过程中找出所有的频繁k项目集Lk。 该

43、算法使用如下启发式规则：一个项目集是频繁项目集, 则此项目集的所有子集构成的项目集也一定是频繁项目集；一个项目集是非频繁项目集, 则此项目集的所有超集（即包含此项目集的项目集）一定是非频繁项目集。 因此, 第k次迭代时的候选项目集可由第k-1次迭代时找出的所有频繁（k-1）项目集之间通过连接运算得到。 此后, 涌现出大量的apriori的改进算法。 如利用hash表的DHP算法 Park, Chen and Yu, 1996 , 基于采样的算法 Toivonen, 1996 , 并行关联规则算法 Agrawal and Shafer, 1996 , 分布式关联规则算法, 多层关联规则算法 Ha

44、n and Fu, 1995 , 数值扩展的关联规则算法 Srikant and Agrawal, 1996 , 利用关联规则进行分类 Liu, Hsu and Ma, 1998 , 具有限制条件的关联规则 Bayardo, Agrawal and Gunopulos, 1999 等等。 由于典型的关联规则的算法会产生大量无意义的规则, 因此出现了基于兴趣度的规则后处理算法 Klemettinen and Mannila et al, 1994 。另外一些研究采用不同的数据结构进行关联规则的挖掘。 例如 Anderson and Moore, 1998 采用一种Adtree的数据结构, Ami

45、r, Feldman and Kashi, 1997 采用trie树, Pasquier and Bastide et al。,1999 使用项目格。 Zaki, 2000 也采用一种类似格的形式。 Hu, Lu and Shi, 1999; Hu, Lu, Zhou and Shi, 1999 则采用概念格来挖掘关联规则。 组合学习方法bagging Breiman, 1996 和boosting Freund and Schapire, 1997 是近来研究提高分类器学习系统预测能力的方法, 也是组合学习中最具代表性和应用前景的方法。 二者都建立了通过投票结合起来的预测器集合。 Baggi

46、ng通过产生样本的重复Bootstrap实例作为训练集。 每一回运行Bagging都给学习算法提供有替代地随机从大小为m的原始训练集抽取出m个训练样本的集合。 这种训练集被称作原始训练集合的Bootstrap复制, 这种技术也叫做Bootstrap综合, 即Bagging。 平均来说, 每个Bootstrap复制包含原始训练集的63.2%, 有些训练例子会出现多次。 与Bagging类似, Boosting操纵训练例子来产生多个假设。 它主要包括两个系列：Boost-by-majority和AdaBoost。 Boosting在训练例子上维护一套概率分布。 在每一回迭代中Boost-by-ma

47、jority通过重取样生成不同的训练集, 而AdaBoost在每个例子上调整这种分布。 具体的学习算法被用来产生成员分类器。 AdaBoost用成员分类器在训练例子上的错误率来调整训练例子上的概率分布。 权重改变的的作用是在被误分的例子上放置更多的权重, 在分正确的例子上其权重将减少。 最终分类器通过单个分类器的加权投票建立起来。 每个分类器按照其在训练集上的精度而加权。 如果产生成员分类器的具体学习算法可以直接使用例子上的分布, 则通常会有很好的结果。 如果不能, 则样本可以随机地有替代地按照概率分布从训练集中抽出。 这使AdaBoost更不确定, 但实验表明该过程仍然很有效。 这两种方法一

48、般用于提高不稳定的学习器的性能。 近年来, 组合预测方法方法已得到了较为广泛的实验和应用, 尤其是在数据挖掘方面其前景日趋看好。近几年, 一些学者对Bagging和Boosting的对比性能测试作了很多实验。 如用于组合CART和最近邻方法 Breiman, 1998 , 决策树算法 Drucker and Cortes, 1996; Quinlan, 1996 , 单属性值测试的两种算法、最近邻法及C4.5 Freund and Schapire, 1996 等等。 实验结果通常表明, 对不稳定的基学习器, 提供给组合分类方法的样本数越大, 代表性越好则泛化性能越好。 而Boosting的错误率通常要更低一些。 但是, 在与C4.5结合的实验中发现Bagging在某种意义上比Boosting稳定, 因为它以较Boosting少的可能性得到比C4.5大得多的错误率。 同时, Dietterich, 1999 的实验发现AdaBoost对噪声更为敏感。 另外, Bagging比AdaBoost更易于实现为并行和分布处理版本。 Breiman, 1998 的实验结果表明, 尽管Bagging和Boosting都减少了一点偏差, 它们对精度的主