关联规则挖掘研究述评
贾彩燕倪现君
*中国科学院计算技术所智能信息处理重点实验室北京+""
.//0123420567:2525;<.=7>?9@
A B C D E F G H E I J B K F E I G A L I
*M N OP E Q%R E S%R O%T B I S N&&F U N I V N B I T%R W E S F%IX R%V N Y Y F I U Z B I Y S F S L S N%T D%W[L S F I U\\N V]I%&%U O Z D]F I N Y N C V E^N W O%T_V F N I V N Y Z‘N F a F I U+""
.b/4>314C Y Y%V F E S F%IR L&NW F I F I U]E YQ N N I%I N%T S]NW%Y S[%[L&E R^E S EW F I F I UY L Q N a V S YE I^]E YEc F^NR E I U N%T E[[&F V E Q F&F S O d B IS]F Y[E[N R Z c NT F R Y SF I e N Y S F U E S NS]NW E F I E[[R%E V]N YT%RS]NS E Y f%TE Y Y%V F E S F%I R L&NW F I F I U Z E I^
E I E&O g N^S]NN Y Y N I V N%T S]NE&U%R
F S]W Y d\\]N Ic NR N e F N c T%L I^E S F%I Y%T E Y Y%V E S F%IR L&NW F I F I UQ E Y N^%IS]NY N e N R E&
[%Y Y F Q&N S]N%R N S F V E&T R E W N c%R f Y T%R^E S EW F I F I U d h]E S i Y W%R N Z c N Y]%c S]N%[N I[R%Q&N W Y F IT F N&^%T S]N E Y Y%V F E S F%I R L&N W F I F I UE I^T F U L R N%L S S]N S N I^N I V O%T F S Y^N e N&%[W N I S F IR N V N I S O N E R Y d
j9@k0>l/m E S E W F I F I U Z m E S E Q E Y N Z C Y Y%V F E S F%IR L&N Y Z C[R F%R F E&U%R F S]W
+引言
近年来Z数据挖掘*又称为数据库中知识发现Z M m m-引
起了信息产业界的极大关注n关联规则挖掘作为数据挖掘的一种重要模式Z已成为数据挖掘领域的一个非常重要的研究课题n它在商务管理o生产控制o市场分析o工程设计o科学探索等领域都有着重要的应用Z目前又逐渐向生物医药o金融分析o电信等领域渗透n
所谓关联规则挖掘是指<从海量数据库中提取给定数据集中项之间的有趣模式p 且q#s{$%令&’(表示一个事务数据 库Z每个事务&{|} )+Z})!Z~Z})*"+&’(|)+Z~Z)*{+Z~Z!"是一些项目的列表Z u v称为规则的支撑度Z是事务数据库中同时包含q和s的事务在事务数据库中所占的比例Z它是概率u v{,*q-s-%w v称为规则的信任度Z是事务数据库中包含q的事务同时也包含s的百分比Z w v{,*s.q-n 例如关联规则挖掘由C U R E c E&t+Z!x等人首次提出并用于购物篮分析*如上例-Z但它只是关联规则挖掘的一种表现形式n自从关联规则挖掘被提出之后Z人们对它的算法和应用的研究方兴未艾Z提出了许多种类型的关联规则和许多种挖掘算法n 按要挖掘值的类型和其抽象水平来分主要有%布尔关联规则o多值关联规则o单水平关联规则o多水平关联规则o单维关联规则o关联规则%从数据库应用的角度讲有<事务数据挖掘*一般意义上的关联规则挖掘-Z序列模式挖掘Z文本挖掘Z hN Q挖掘Z多媒体数据挖掘Z生物信息数据挖掘Z关系型数据库挖掘等等n 本文我们主要以事务数据库为例介绍几种主流的关联规则挖掘算法Z对它的实质和性能进行分析Z指出目前主要存在的主要问题和未来发展的趋势n !关联规则挖掘算法分析 *+-经典的关联规则挖掘算法.4>20>2 +55#年C U R E c E&t+x等人提出关联规则挖掘算法后Z给出了经典关联规则挖掘算法C[R F%R F Z算法主要有以下两个步骤< +’找出所有的频繁项目集n所谓频繁项目集*又称为大项目集-是指那些支撑度大于用户指定的最小支撑度阈值的项目集n !’由频繁项目集产生关联规则n在频繁项目集中寻找满足用户指定的信任度阈值的规则n C[R F%R F算法的性能主要由第一步决定Z第二步在第一步的基础上很容易得到Z算法的核心也主要在寻找频繁项目集上n它主要基于这样一个性质*m%c I c E R^V&%Y N^[R%[N R S O-<频繁项目集的所有非空子集必为频繁项目集Z利用这个性质可以有效地压缩搜索空间n算法主要思路如下<首先寻找+G 频繁项目集6 +Z 利用+G频繁项目集产生!G候选集7 !Z 在7 ! 中 寻找!G频繁项目集6 !Z 再产生#G候选集Z依次下去直到某个 7+为空n在产生7:Z:{+Z~Z8时Z可以利用一定的剪枝策 略压缩7 :n 如利用任何非:;+G频繁项目集都不可能是:G频 繁项目集这一事实Z删去那些:;+子集不在6 :;+ 中的:G候选项目集n 该算法能够比较有效地产生关联规则Z但它存在着以下缺陷< *+-算法产生太多虚假*冗余-的规则n当数据库太大或支撑度o信任度阈值太低时产生的规则太多Z用户很难人为地对这些规则做出区分o判断n *!-算法在效率上存在着问题n主要原因为数据库扫描的次数太多Z寻找每个f G频繁项目集*:{+Z~Z8-都需要扫描数据库一次Z共需要扫描M次n另外Z当模式太长时产生的候选项目集也多得让人无法接受n因此当数据库或M太大时Z 算法的时耗太大或无法完成n故算法可扩展性也不强Z难于推广n 基于以上原因Z人们对C[R F%R F算法进行了一定的改进Z 希望能够在提高算法的可靠性o高效性及可扩展性等方面做 < 1 ) + < 万方数据 一些工作!主要技巧有" #基于采样的策略$ %& 该方法主要思想是"随机地选取一些样本数据集’使用这些样本发现关联规则’然后用数据库 中剩余的部分检验并修正得到的结果!该方法不但能够减少数据库扫描的次数’而且能够减少()*和+,-负担’ 在执行效率上有很大提高! 由于数据库规模的急剧膨胀’人们认为取样数据库’使用其中一小部分的数据发现关联规则的思想是提高算法性能和可扩展性的一个好的方法’但如何对数据库进行合理取样而尽可能不丢失信息’是目前人们已经注意到’尚未很好解决的公开问题! #基于分片的策略$ .& 该方法的主要思想是"第一次扫描分两个阶段"/0 将数据库分为1片’使得每一片能够在内存中进行处理’在每一片小数据集上以局部支撑度阈值产生局部频繁项目集230汇总产生全局候选频繁项目集!第二次扫描计算全局候选项目集的全局支撑度阈值得到全局频繁项目集!该方法具有分布4并行的思想’最多扫描数据库两次’同样可以减轻()*和+,-负担’ 提高算法性能和可扩展性!#动态项目集计算策略$/5& 该方法是基于前两种方法的思想基础之上的’主要思路是"6/0在扫描的任何时候用户可以自由调整支撑度和信任度!630将数据库以7678/ 990划分为:;<=:,7片’从第一片开始扫描’以用户指定的支撑度先寻找/>频繁项目集’在中途某一片停止寻找/>频繁项目集转而寻找3>频繁项目集’继而是?>频繁项目集4.>频繁项目集@!该方法能有效地减少数据库扫描的次数6一般不超过两次0’提高算法的效率!另外’我们认为利用这种方法自适应地调整A 4支撑度和信任度可以更好地提高算法的性能! #剪枝策略该策略有多种表现形式’如在剪枝B C 的同时剪枝数据库D E F ’在产生每个B C 时’凡被认为对C >频繁项目集G C 的产生不做贡献的事务被剪掉’以后不再对该事务做任何处理’ 这样可以使得随着C 的增大扫描的数据库越来越小!较复杂且高效的剪枝方法可参考-H I J K L M 的文章$?/& ! #基于N J O P 表的项目集计算策略 $3Q ’/%& 作者发现初始产生的候选项目集’尤其是B 3的好坏是提高算法性能的重要 因素!这是因为’每一次扫描G C 被用来产生B C R /’B C R /中包含的项目集越多’产生G C R /的处理花费也越大’特别是B 3的处理花费6:B 3:S :G / :T U 30’所以扫描整个数据库由B 3得到G 3 是最耗时的一步’并且B 3的大小将影响整个算法的性能!因此该方法主要利用N J O P 表将数据库投影到N J O P 表上来减 少产生的3候选项目集的数量!但是’由于N J O P 表的内存耗费’算法对于稠密4大数据库的性能是一个值得考虑的问题! #项目集与标号集同时使用策略$ 5’/9& 由于每个项目在每个事务中对应一个事务标号’因此每个项目在整个D E F 中 就会对应一个标号集’ 对标号集上定义一些算子可以计算项目集的出现频度’避免对D E F 的多次扫描!这是目前改进算 法性能的一个比较好的策略! #基于的策略$ /Q & 由于频繁模式挖掘经常产生大量的频繁项目集和关联规则’这使得用户必须从这些大量的 规则中筛选有用的模式!最近’人们越来越强调的重要性!在挖掘的过程中用户可以表达自己最关心的方面’有效地控制规则的产生!总的来说有这样几类"V W X W Y W X Z ’[X Y \\>V W X W Y W X Z ’]^__\\X _Y ’_W X ‘Z a Y \\b c Z ’有一些可以直接加入d e H f M H f 算法中’有的还存在问题6如g M K h i H j f k I i 0!基于的关联规则挖掘算法是近期人们比较关注和热心于研究的问 题! 在这些思想的推动下产生了一些新的想法和新的算法’下面我们主要对几种主流的算法进行一些介绍! 630基于闭项目集的l m n o p 算法$q ’r & 正如我们所知’d e H f M H f 类型的关联规则挖掘算法会产生许多虚假4冗余的规则’并且在较低的支撑度或信任度要求下’ 产生的关联规则会飞快增长’冗余问题也越严重!对于现实生活中的真实数据库而言’产生的频繁项目集之多4冗余度之大’ 更让人无法忍受!因此’怎样找到尽可能少又有效的频繁项目集及无冗余4精确的关联规则是一个值得人们思考的问题! 一个好的解决方案是基于闭频繁项目集的(N d s A 算 法!闭频繁项目集是相应的频繁项目集的子集’它完全抓住了频繁项目集的所有信息’它是频繁项目集的无失真信息的最小集合’ 任一个频繁项目集都可以由闭频繁项目集得到!闭项目集的概念来源于优美的正规概念分析的数学框架 6t M H u J I (M K g i e j d K J I v O f O 0$Q & ’如果项目集w 满足B Y \\6w 0S w ’则称x 为闭项目集2类似的’如果标号集y 满足B \\Y 6z 0S z 则称y 为闭标号集2如果x 是闭项目集且y 是闭标号集’则称 二元关系6w ’z 0{|};|<为一个概念!其中Y 6w 0S Y \\~6! 0’\\6z 0S \\Y Z V 6z 0’z 是x 对应的标号集’D +E 为整个标号集!闭项目集与闭标号集是成对出现的’也就是说找到了频繁概念就找到了闭频繁项目集!基于闭项目集的(N d s A 算法的一 个特色是" 同时搜索项目集和标号集!其主要步骤如下"/"从/> 项目集开始寻找频繁概念!3"利用闭频繁项目集寻找关联规则的最小生成集’也称为关联规则的基!任一个关联规则都可由传递算子4增加算子及合并算子通过最小生成集生成! 该方法主要计算步骤是确认闭频繁项目集!它以完全格的形式表示项目集及其相应的标号集6二元关系0’格顶点为空结点’一层子格结点为/> 项目集及其相应的标号集’每一个子格结点的孩子结点由他与他的兄弟联合形成’同时使用两种剪枝策略’即剪掉非频繁的项目集’又剪掉非闭的项目集’采用深度优先遍历子格寻找频繁概念!该方法的另一个优点是"标号集的使用使得项目集的支撑度可直接由标号集上的操作得到’避免了数据库的多次扫描!实验表明在低的支撑度阈值下’用该方法产生的闭频繁项目集和发现的关联规则比原来少了很多倍!该方法适用于低支撑度阈值和稠密数据库的情形’ 且算法随着事务数量的增加具有线性可扩展性!是目前关联规则挖掘算法中性能较好的一种方法! 6?0#$%&’()*+算法$/.,/Q & 传统的d e H f M H f 类型的关联规则挖掘算法’采用候选>测试的方法产生关联规则! 然而’当支撑阈值太低或产生的模式长度太长时’基于候选项目集的算法可能会浪费很多不必要的花费!另外’当数据库太大时产生的候选项目集也势必会太大!因此’N J K 等人给出了不产生频繁项目集的t )>-H M .j P 算法!该算法有以下几个显著特点" /0 不产生候选项目集’以分而治之的方法将要检测的数据集以其重要程度分块’分析集中在相关数据集的频度!这种分而治之的方法可以大大地减少搜索空间且具有并行算法的机制! 30将原数据库以高压缩的方式t )>j H i i 存贮在内存中’将原来从磁盘的读取工作直接放入内存中进行’随着计算机技术的发展’高容量内存已不再是对系统性能的一个’内 # r ./#万方数据 算法主要步骤为" #$构造频繁模式树%&’()**!并利用%&’()**挖掘频繁模式+即频繁项目集! ,$由频繁项目集产生关联规则! 算法精髓在于%&’()**的设计和构造!%&’()**是一种高压缩的存贮结构+它将#’项目集以频度由大到小排序+不满足最小支撑阈值的舍去-每一个项目有一个带有头结点的链!扫描数据库+相同前缀的事务共享一个前缀存贮空间+同时记下每个项目当前出现的频度+并且相同的项目连成一条链以便于频度的计算和模式的发现!然后+以单个项目重要程度将数据库分块+边搜索频繁模式边生成各条件数据库的%&’./0()**!该算法的实质是将1’频繁项目集的发现问题转化为1个#’频繁项目集的发现问题! 该算法可以处理大的2稠密的数据库+不失为一种高效2扩展性强的好算法+并且可以很容易地推广到闭频繁模式挖掘3如4567算法:2最大模式挖掘3下文给出定义:2基于的挖掘及序列模式挖掘等! 3;:<=>?@A算法B#C D 4567算法是基于闭频繁项目集与%&’E)F G(H算法的思想基础之上的一种算法+正如上文如述+它用%&’ E)F G(H算法的方法挖掘闭频繁项目集3具体算法不再细述:!本文在这里特别列出的主要原因是"本来这应该是一种好的算法+因为它结合了闭频繁模式挖掘与%&’E)F G(H算法两者的优点于一身+但实验结果表明+它在真实数据库上性能比4I J K L和%&’E)F G(H都差B M D!可能有以下几个原因" #:真实数据库相对人工合成的数据库稠密+因此 4567在人工合成的数据库和真实数据库上表现出不同的性能+出现过拟合的现象! ,:%&’()**和%&’./0()**子树的构造相对4I J K L中格的构造费时且大量占用了内存空间+尤其是对现实世界中的稠密数据库而言这方面的时间消耗就更大! M:在4567算法中+闭项目集的查找需要多次比较2匹配+这势必会增加4&N的负担! 总之+4567算法的性能有待改进+算法的复杂性值得思考! 3C:O P Q R ST U算法B##D 对一些稠密数据库而言+频繁项目集也好闭频繁项目集也好都会增长到让人无法容忍的地步!由于所有频繁项目集的子集必为频繁项目集+那么为什么不直接找到最大的频繁项目集!在这方面人们提出了很多种算法B#V M D+这里我们以 E*W LX Y为例进行介绍! 一个频繁项目集被称为是最大的+如果它不是任何其它频繁项目集的子集!E*W LX Y是一种基于回溯搜索挖掘最大频繁项目集的方法+在搜索的同时快速剪枝搜索空间!主要思想如下"扫描数据库+采用回溯法深度优先遍历每一个事务+在搜索的同时使用有益的剪枝策略’回溯过程中被已有最大频繁项目集包含的项目被剪掉! 该方法有一个致命缺陷"可以产生整个频繁项目集+但不易产生规则+这是由于除最大频繁项目集外+其它频繁项目集的支撑度都未知+这使得规则的信任度无法计算3Z3[\\]:^ Z3]_[:‘Z3]::!因此还需要重新计算每个非最大频繁项目集的支撑度+这又是一笔额外的开销-并且产生的规则冗余性又是一个需要考虑的问题!但它对于一些具有较长模式的数据库的关联规则发现具有比较高的效率3如生物信息数据库:+因此该算法仍具有很高的实用价值! 3a:ST b Q c d>e f?算法B#,+#M D 前面所述的算法都致力于寻找频繁项目集+人们自然会想到有没有一个好的方法直接挖掘用户感兴趣的关联规则而无须生成频繁项目集!g X h X)i F和j*00在这点上可谓独创+然而+g X h X)i F B M k D中只产生具有指定结果的关联规则+不能产生所有的规则!j*00给出的LX l W/m6&N7算法可以直接发现用户感兴趣的所有关联规则!LX l W/m6&N7的特点是" #:基于最优无序剪枝搜索策略6&N7-,:将数据库放入内存中进行处理! 算法思想是"利用6&N7深度优先搜索事务数据库+同时利用规则间的减少需考虑的项目集的数目!算法的精髓在于剪枝策略6&N7’优先处理不满足条件的枝+这使得凡是包含不满足条件的项目的整个枝都被剪掉+它可以每次剪掉将近当前搜索空间一半的数据+剪枝效率非常高!它的另一个显著特点是"利用6&N7的最优化思想+可以发现预先指定数量的2质量最好的关联规则+而并非所有规则+这将有助于提高算法性能且更面向用户!该算法的最大优点是适用于挖掘稠密的且可以是动态增加的数据库中的关联规则! 另外+算法可以直接推广用于挖掘具有数值变量的关联规则+且同样可以处理稠密数据库! J n)o F)o24I J K L2%&’E)F G(H2LX l W/m6&N72E*W LX Y 等算法中给出了关联规则挖掘领域中几种好的理念+其它对它们的改进算法都从某种程度上提高了算法的性能+但要从根本上解决目前关联规则挖掘的主要问题+兴趣模式的有效2自动提取+这就需要数据挖掘技术与人工智能技术的进一步结合! M关联规则挖掘算法的统一描述及其理论基础综上所述+我们可以看到在数据库中寻找令用户感兴趣的关联规则时+有这样几个着眼点" #:数据库的处理技术!如整个数据库的采样-有效的剪枝策略减少搜索空间-数据库分片3并行处理:-对数据库进行压缩3内存中处理:-多处理器搜索数据库等! ,:搜索策略!如深度优先-广度优先-自底向上-自顶向下等! M:支撑度2信任度的计算方法!I X.H法-标号集法-频度法等! 因此关联规则挖掘算法可以描述为"数据库的处理技术 p搜索策略p统计策略!究其实质关联规则挖掘是"数据库’树3可退化为格等:的最优化搜索策略!这即是一个人们研究已久的老问题3树的搜索:+又是一个加上了新的特性3基于数据库:的新问题!下面我们来深入探讨一下关联规则挖掘究竟应该隶属于哪种理论框架之内! 我们知道关联规则挖掘是数据挖掘的核心任务之一+关联规则挖掘的理论框架应该能够包含在数据挖掘的理论框架之内+二者相辅相承!在寻找数据挖掘的理论框架进而为关联规则挖掘我们找到一个强有力的支持之前+我们有必要先回答这样一个问题"为什么要寻找理论框架q纵观科学发展的历史+但凡一门技术或学科如果没有一个可靠的理论保证+它就象黑暗中的溯流没有一个清晰的结构+不知道会流向何方!好的理论对相应的科学技术的发展具有指导2护航的作用! LX W W o r X B s+,k V,M D等人在这方面做了一些有益的工作!总的来说有以下几种观点" t s ; # t 万方数据数据挖掘的统计和机器学习观点!"#$%直观地说&数据挖掘可以被视为统计理论或机器学习的一部分&但数据挖掘技术所具有的一些特性是统计及机器学习无法包容的%虽在某种程度上可以说&数据挖掘是统计在大数据集上的扩展&但数据挖掘包容了许多数据分析领域内的新的观点&完全不同于传统的统计学观点%另一方面人们必须认识到&是计算机科学家而不是统计学家将统计的观点融入了数据挖掘领域%再者统计学关心的是数据的全局模型而数据挖掘关心的是数据的局部特性’模式发现(%同样&机器学习也与数据挖掘存在很大差别&机器学习无法处理数据挖掘所处理的如此之大的海量数据库&它的一些理论模型无法满足数据挖掘技术的特殊要求%其中最值得注意的是)数据挖掘任务中尤以关联规则挖掘不能用传统的统计学观点和机器学习观点来解释%数据挖掘的概述分布观点%概率分布理论可以作为数据挖掘的一个比较合理的理论框架&数据挖掘中的分类和聚类问题适合于这一理论&但它似乎无法解释数据挖掘过程&特别是关联规则挖掘过程中的递归和交互过程% 数据挖掘的数据压缩观点%在这一领域数据挖掘任务可以表述为)压缩数据库以发现它的一些结构%简单的关联规则挖掘*聚类*分类等任务在某种程度上都可以用该理论解释&但它仍缺乏完备性% 数据挖掘的微观经济学观点!"+$%传统数学意义上的优化模型与复杂的*高度未知性*不能精确形式化的*靠启发式方法处理的数据挖掘模型之间存在很大差距%,-./01.23发现它更类似于微观经济学中的模型&提出了基于优化的数据挖掘的微观经济学观点%该理论能够用来描述简单的模式发现’如关联规则(*聚类等数据挖掘算法&是一种新颖的数据挖掘的理论框架%有望在进一步的发展*充实后成为一种可被人们接受的理论观点% 数据挖掘的归纳数据库观点!""$%456-/7869等人认为关系数据库模型及其查询语言是推动数据库技术发展的理论基石&在数据库的基础上加上一些有关数据库的理论’规则*语句等(得到归纳数据库模型&可以作为数据挖掘的理论框架%该理论能够描述关联规则挖掘&但无法对数据挖掘的另一重要算法:聚类进行描述% ;8我们认为数据挖掘作为数据库技术*人工智能*统计学等学科的交叉学科&很难找到一个合适的*全面的理论框架%这一框架必须建立在这几门学科相关概念*思想的基础之上%首先需要解决的问题是怎样对数据挖掘各种任务给一个比较形式化的描述&然后考虑数据挖掘的整个过程才能建立一个合理的数据挖掘理论框架% 总的来说&关联规则挖掘的理论框架乃至整个数据挖掘理论都有很长的路要走&是目前数据挖掘领域一个具有挑战性的工作% >关联规则挖掘算法主要存在的问题及其发展趋势 由前文我们可以看到&关联规则挖掘主要存在着如下几个问题) ’+(算法在性能上有待改进&尤其是并行性和可扩展性%无庸置疑高性能的关联规则挖掘算法总是人们感兴趣的一个问题% ’"(正如我们上文所述整个数据挖掘算法目前还没有一个统一的理论框架&这不仅包括算法理论基础及其模型&还包括算法复杂性问题*取样定理的研究等等%这方面研究工作的缺乏势必会阻碍关联规则挖掘的发展% ’?(关联规则挖掘的新的应用领域%随着各种数据库资源的不断丰富和膨胀&越来越多的领域需要从海量的数据中发现有用的模式&以提高资源的利用率或增强自身的竞争力等% ’>(数据库的安全性和私有保护问题%我们知道数据挖掘是建立在对原始数据库或数据仓库处理的基础之上的&不同的处理任务有不同的安全性要求%怎样在数据库中挖掘人们感兴趣的信息又在一定程度上保护数据的私有性&是现今人们在数据挖掘的发展中逐步认识到的且必须解决的问题%基于以上存在的问题&关联规则目前和今后一段时间的发展主要集中在) ’+(寻找高性能的关联规则挖掘算法% ’"(建立关联规则挖掘乃至整个数据挖掘的理论框架%包括复杂性分析*取样定理*数学模型等等% ’?(私有’@2/A87BC2.D.2A/03(保护关联规则挖掘!"?E"F$% ’>(寻找与其它类型数据库的融合%如空间数据库G多媒体数据库G时序和有序数据库G文本数据库G H.1数据库% ’F(开拓新的应用领域%如科研*生物信息*金融市场*电信等领域!"I&"J$&这也是一个具有挑战性的工作% ’I(模式或规则的兴趣度的研究%如好的模式是什么&怎样利用领域知识区分好的模式和坏的模式等等% 总之&关联规则挖掘会以其新鲜血液的不断注入而越来越有生命力&它的应用领域也会越广越宽% 结论数据挖掘&特别是关联规则挖掘以其固有的解决问题的能力和其潜在的商业价值引起了人们的极大兴趣%本文我们首先主要对目前几种主流的关联规则挖掘算法进行介绍&深入分析了关联规则挖掘的实质&综合描述了现有的数据挖掘进而是关联规则挖掘的理论框架及其重要意义%最后&总结了关联规则挖掘目前主要存在的问题和未来发展的趋势%我们认为本文的研究工作对有志于该领域的学者具有一定的指导意义% 参考文献 +K328L8-M&N O/.-/0D1.9L..0Q.9D5TN9.O D/0U823.V818D.R N0Q N W SX V Y#?& H8D Z/03950&V[&S8B+##?R"\\=E"+I "K328L8-M&Q2/<809M R]8D9K-352/9Z O DT52S/0/03K D D57//50 M6-.D R N0^U V4Y#>&Q809/835&[Z/-.&Q.C R+##>R>J#E>## ?;Z.03;&,5Z8A/M&S8D50U R M.8-H52-_@.2T52O807.5T K D D57//50M6-.K-352/9Z O D R N0)@257R5T9Z.D.A.09Z K[S: Q N W,V V N09R[50T R50,05L-._3.V/D75A.2B80_V8S/0/03&‘.L a52<&‘B&"\\\\+ >Q8A8D.2.K&X O/.7/0D"+9Z R[50T R50^.2B U823.V818D.D’^U V4Y#F(&;c2/9Z& Q L/9d.2-80_&Q.C R+##F F;8I;8V/D75A.2B80_V8S/0/03&‘.L a52<&‘a)K[S&?>E>? =;8J P5/A50.0f R Q8O C-.U823.V818D.DT52K D D57//50M6-.D R N0) @257R5T9Z.""0_N09R[50T R50^.2BU823.V848D.D&S52380 h J > + h 万方数据!"#$%"&&’())*+(,-.(-/ )01223’45&67:’;"<="817">8=4+?@A B916=%C$B9?C C B D1"61B& E#@8F1&1&A G?48&"@H#98I"&>J B%2"91C B&+?J F G H K4!L L’3#@I M N N N (N01223’45&67:’;"<="817">8=4+F1&1&A?C C B D1"61B&E#@8C O LP1&A?H#21B9?@A B916=%Q I?&"@I C1&A R B>"I S C ?229B"D=8C+K&O T9B D+B$6=8-6=U#9B28"&J B&$+B&T91&D12@8C"&> T9"D61D8B$!&B V@8>A8L1C D B PI’W I B&’X9"&D8’H82+M N N N ((4B#>"!’Y"<1F3+U$$1D18&6@I F1&1&A F"Z1%"@X98[#8&6 K68%C86C (M\\8Q Q4K+U$$1D18&6H8"9D=$B9?C C B D1"61B&E#@8C+K&!L L G M N N N ]B C6B&’F?’?#A+M N N N (,\\8Q Q4K+L1C D B P1&A?C C B D1"61B&V16=;#%1D^"91"Q@8C+K& !L L G M N N(H"&X9"&D1C D B’J?’?#A+M N N(+ (-0"&3’T813’_1&_+F1&1&AX98[#8&6T"66&C V16=B#6J"&>1>"68 48&"61B&+K&H K4F‘L a N N’L"@@"C’R b’F"I M N N N+(.(M (/T813’0"&3’F"B E+J W‘H U R O?&U$$1D18&6?@A B916=%$B9F1&1&A X98[#8&6J@B C8>K68%C86C+K&L F!L a N N’L"@@"C’R b’F"I M N N N+ ((.M N (*0"&3’T813+F1&1&A X98[#8&6T"66&C Q I T"66&G49B V6=O F86=B>B@B A I"&>K%2@1D"61B&C+M N N( (c T813’0"&3’W" (d‘e78@H?’45P8&190?+?&?@A B916=%$B9F1&1&A?C C B D1"61B& E#@8C:C1&AT$8D60"C=1&A"&>L"6"Q"C8T9#&1&A ()]91&H’FB6V"&1E’:@@%"&3L’R C#9H+L I&"%1D K68%C86 J B#&61&A"&>K%2@1D"61B&E#@8C$B9F"9<86]"C<86L"6"+K&O T9B D+ B$6=8?J F G H K4F‘L a)c’())c M N F"&&1@"0+R=8B9861D"@X9"%8V B9 M(!@81&QA3’T"2">1%1691B#J’E"A="P"&T+?F1D9B8D B&B%1D ^18V B$L"6"F1&1&A+L"6"F1&1&A"&>!&B V@8>A8L1C D B PI’())d’M f-g O,((.,M- M M]B#@1D"#63G X’86"@+FB>8@1&A!L L T9B D8C C8C V16=1&6=8 K&>#D61P8L"6"Q"C8X9"%8V B9<+L"6"\\"98=B#C1&A"&> !&B V@8>A8L1C D B PI f L"\\"<()))g’F+!+FB="&1""&>?+F+ R h B"f8>C g’T T+M),.,N M M,J@B$6B&J+T91P"D IT98CP1&AL1C691Q#68>L"6"F1&1&A M-?A9"V"@E’H91<"&6E+T91P"D I G T98CP1&AL"6"F1&1&A+K&O T9B D+ B$6=8())c?J F G H K4F‘L J B&$+B&F"&"A8%8&6B$L"6"’L"@@"C’R b’F"I M N N N+(-.() M/W1&>8@_’T1&<"C]+T91P"D IT98CP1&AL"6"F1&1&A+K&?>P"&D8C 1&J9I26B@B A I G J E_T R‘’H291&AG^@"A’?#A+M N N N+,*./- M*0"&3’!"%%Q9F+L"6"F1&1&A J B&D826C"&>R8D=&1[#8C+ FB9A"&!"#$%"&&T#Q@1C=C’M N N N M c T"9<3H’J=8&F H’_#TH+:C1&A"0"C=G]"C8>F86=B>V16= R9"&C"D61B&R91%%1&A$B9F1&1&A?C C B D1"61B&E#@8C+K U U U R9"&C"D61B&C B&!&B V@8>A8"&>L"6"U&A1&81&A’())c’)f/g M d48=9<83+;8V E8C8"9D=L198D61B&C1&!L L+E82B96B&6=8 H K4!L L M N N(J B&$8&D8T"&8@ M)H%I6=T+L"6"F1&1&A"66=8K&6$"D8B$J B%2#6H D18&D8"&> H6"61C61D C+L"6"F1&1&A$B9H D18&61$1D"&>U&A1&81&A ?22@1D"61B&C’6B"228"9’M N N M ,N]"I"9>BE339+’?A9"V"@E+F1&1&A6=8FB C6K&68C61&A9#@8C+ K&O T9B D+B$6=8X1$6=?J F H K4!L L K&6S@J B&$+B&!&B V@8>A8 L1C D B PI"&>L"6"F1&1&A’()))+(-/.(/- ,(‘9@"&>B H’T"@%1&1T’T8A B E+U&="&D1&A6=8?291B91 ?@A B916=%$B9X98[#8&6H86J B#&61&A+L"\\" 较结果如图(所示i另外从范例删除前j后对J]E系统范例提取效率f仍采用最近邻提取算法g的影响来评价删除策略性能’实验结果如图M所示 i 图(两种删除策略下测试集平均相似度随删除范例数 增加的变化情况 图M提取时间随删除范例数增加的变化情况 从图(j图M可以看出’基于聚类策略的范例删除方法比随机范例删除方法具有更高的平均相似度k而且在删除范例数增加时’该方法下的平均相似度减少缓慢’而范例提取时间明显下降’从而该方法能够在保持J]E系统解决问题能力的前提下’最大限度地减少范例库’改进J]E系统的性能i 结束语本文提出了一种有效的基于聚类策略的范例删除方法’从实验结果可知’该方法能在保持J]E系统解决问题能力的前提下’最大限度地减少范例库’提高范例提取的效率’改进J]E系统的性能i与此同时’算法中经验参数的选取有待进一步的研究i 参考文献 (H D="& W8"9&1&A1&J B%2#6C"&>T8B2@8+J"%Q91>A8:&1PC16IT98C C’J"%Q91>A8’:!’()d M M X9"&D1C?4’E"%?+R=8#61@16I29B Q@8%1&D"C8G Q"C8>98"C B&1&A+ K&O T9B D+?K G),J"C8G]"C8>E8"C B&1&A\\B9 H I C68%C+K3J?K’())/+,c c.,d, -W8"<8L]’\\1@C B&L J+E8%8%Q1&A\\=I6B E8%8%QO T$B9%"&D8G4#1>8>J"C8G]"C8F"1&68&"&D8+U\\J]E M N N N’H291&A^@"A’22(*(.(c M /范明’孟小峰等译+数据挖掘概念与技术+北京O机械工业出版社’M N N( *F1&6B&H+l#"@16"61P8E8C#@6C J B&D&1&A6=8:61@16I B$ U Z2@"&"61B&G]"C8>W8"9&1&A+?961$1D1"@K&68@@1A8&D8’())N’-M O ,*,.,)( c=662Om V V V G B@>n1D C n#D1n8>#o2#Q o%"D=1&8G@8"9&1&A G>"6"Q"C8C o "#6B C o p ) - ( p 万方数据+Z}!Z~Z}!"
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
