计算机系统应用2009年第7期基于关联规则的分类模型系统CIassificationModelingSystemBasedonAssociationRule晃玉宁许孝元(广东工业大学计算机学院广东广州510006)摘要:关联分类是数据挖掘及机器学习领域的一个研究热点利用原子关联分类算法(CAAR)建立了数据模型的机器学习系统,详细说明了CAAR算法的分类步骤并给出了算法的伪代码表示在UO提供的标准数据集上进行测试,实验验证了在大规模数据集中,在不同的抽样率情况下,原子关联分类算法的分类准确度,用数据的方式与其他分类算法做T比较对数据集记录次序的依赖性进行的10一折交又验证实验表明,原子关联分类算法的分类准确度要高于CBA算法关键词:数据挖掘原子关联规则分类机器学习数据挖掘就是从大量数据中提取或 挖掘!有用类的准确度和模型的可理解性都优于决策树与CBA的知识,因此数据挖掘又被称为数据库中的知识发现本文首先介绍CAAR算法的分类原理及系统设计,再关联分类是数据挖掘及机器学习领域内的一个很重要从实验的角度,在UO提供的标准数据集上进行测试,的研究热点许多实验也都证明了关联分类具有良好比较CAAR与其他算法的分类准确度的分类准确性利用简易规则构造分类模型,可以追溯到19931CAAR算法理论(原子关联规则分类算法)年出现的1R(或OneR)分类算法川该算法的基本思1.1原子关联分类的相关定义想是对数据集上的各个属性创建单层的决策树,然后定义1.关联规则:它表现为项集之间的关联关计算训练集上达到的错误率,最终选择错误率最低的系关联规则r表示为:
,其中LHS是单一属性产生的单层决策数作为分类策略在IR算一个项集,称为规则的前件或条件,RHS是一个类标法的改进算法中112,引入了加权机制,如果有两个或签,成为规则的后件或结论,可以表示为LHSRHS两个以上的规则有相同的最小错误率,则选择权重较定义2.支持度(suP):指数据集中包含LHS及大的规则作为分类规则1998年,Uu提出了类关联类标签RHS的实例数与数据集中总的实例数O的比规则分类算法CBA13]该算法使用类Apriori算法产值生分类规则,当遇到高维数据库时,会遗失部分长模定义3.置信度(cono:指数据集中包含LHS及式的优质规则,降低模型的分类准确度此后,陆续类标签RHS的实例数与只包含LHS的实例数的比值有人针对CBA的不足提出了各种关联分类算法,典型定义4.原子型分类关联规则:指规则的前件只的有CMARI4]∀C队R15]∀基于概念格的关联规则分类有一个项的分类关联规则,即#LHS卜1法116等但这些关联分类算法并没有解决分类模型准定义5.强关联规则:指支持度大于minsup且确度低,执行效率低,系统资源消耗大的问题2004置信度大于minconf的关联规则年,提出了采用多步原子关联规则的分类新技术在CAAR算法中,minconf=kxmaxconf(一般CAARI7](ClassificationbasedonAtomicAssocia-k=0.98),其中maxconf是候选原子关联规则的最高itonRules),消除了关联规则挖掘时的 组合爆炸效置信度我们只选择具有最高置信度和接近最高置信应!就算法的性能来看CAAR有不俗的业绩,其分度的强关联规则用于分类器的构建收稿时间2008一11一1108研究开发Rese别mhandDevelOPment 2009年第7期计算机系统应用 1.2CAAR算法描述CAAR算法的出现不是偶然的,它是在发现知识要点的背景下提出的CAAR算法的分类思想是,利用人类在区分事物时采取 利用突出特征和先易后难策略!的分类原理对数据集进行几次部分分类,直到全部实例分类完毕CAAR算法重要的第一步是产算法的伪代码表示如下:Gen_Classifier(DatasetDO) Rulesetclassifier+-甲:Dx=Do部分分类的数据集//Dx为∋Countereounter+-newCounter()(counter.counting(Do)还脚HILE}D:卜0ANDNumofClass(Dx)>1Do 生强原子规则,用于原子规则产生的数据结构是一个COunter类,它用一个三维数组去存储与原子规则有关的2一项集(r.LHSAr.RHS)的计数这个类用∃ava语言定义如下:)Ruleset卜sarGen_SAR(D:,counter)//sar为强原子规则集∗counter.clear()//为下一次计数做准备 PublicclassCounter{publicint[][][]count=newint[mlln刃[nC];Publicvoidcounting(Datasetd){%}Publicvoidcounting(Instanceinst){%}PublicintgetCount(intX,intVx,Intc){%}PublicintgetCount(intX,intVx){%}}+Rulesetcr卜PruneRules(sar,D:,counter)//在PruneRules中更新Dx ,elassifier+-classifierUcr//将部分分类的分类规则集加入分类器−ENo00 .lF的规则旧:卜0TH/N/产生一个指示缺省类 @c一assifieroe一assifierU{<指示缺省类的规则>}.ENOIF/在预测时总是取最后一个规则的结果作为缺省类.returnclassifier首先调用Counter类的counting方法扫描数据集O(第3行),对所有出现的项以及与原子规则对应的2一项集计数NumofClas函数获得数据集中实例的种类数(第4行)Gen_SAR函数通过计数器产生强原子规则(第5行)PruneRules函数对冗余的规则剪枝,并删除数据集中被规则覆盖的实例;同时,这里,m=属性个数,nC=类标签个数nV表示最大的属性值域空间大小重载的Counter 类的getCount方法既能返回候选原子规则前件项(r.LHS)的计数,也能返回原子规则r对应2一项集(r.LHSAr.RHS)的计数,通过三个下标值存取原子规则的计数CAAR算法产生分类器的步骤如下:输入:数据集O,最小支持度minsup和最小置信度minconf输出:分类规则集(1)挖掘原子型分类关联规则,选择具有最高置信度和接近最高置信度的强原子规则用于部分分类对没有被规则覆盖的记录进行计数,为下一次的部分分类做准备分类器由每一步部分分类产生的分类规则集顺序组合而成当数据集中实例数为O时,则完(2)为了与其他关联分类算法进行比较,对强原子关联规则按置信度为第一关键字∀支持度为第二关键字进行降序排序(更好的排序方法是文献&]中指出8的);接着,在数据集上测试强原子关联规则集,删除被规则筱盖的实例;当数据集扫描完毕时,删除冗余规则成分类器的构造或者,数据集中的实例数不等于O且其中的所有实例都属于一个类时,产生一个指示缺省类的规则(第10一12行),完成分类器的构造CAAR分类算法与文献&1#中的IR算法提取的规则都属于简单规则,得到的分类模型简单易于理解,并且(3)对余下的数据,继续上述部分分类过程,直到数据集的实例数为零最后顺序组合各阶段的分类规则,得到分类模型在每次部分分类中,在测试强关联规则集选择分类规则时,同时进行下一次部分分类有效实例的计数,模型不易出现过学习现象但它们也存在以下的不同点:(1)分类机理不同:IR算法基于简单的统计计数,规则局限于某一个属性,是一个粗糙的单步分类过程CAAR算法基于人工智能原理,模仿人类区分事物时利用突出特征与先易后难策略进行分类,是精细的多esR即CharndDeve#即功etn研究开发81因此,减少了对数据集的扫描次数 计算机系统应用2009年第7期步分类过程是第一关键字∀支持度是第二关键字对强原子规则进行排序parittion:是一个对数据集进行分区的类函数将数据集一部分作为训练集,剩余的做测试集通常用到的是10一折交叉验证,是把数据集分为大小相同(2)规则的度量方法不同:IR算法仅采用基于计数的误差值选择分类属性而CAAR使用多项数据挖掘技术,利用具有最高置信度和接近最高置信度的优质原子规则构建分类器(3)分类准确度不同:IR算法及其改进算法在平均分类准确度上都不及决策树,而CAAR算法的平均分类的10份,选择其中一份作测试集,而其余的9份全作训练集该过程重复10次,使得每份数据用于测试恰好一次Attributeset:是用于存储数据集中属性集的类 准确度显著高于决策树及关联分类基准算法CBA[刀2 系统设计与实现原子关联分类算法机器学习系统的功能就是利用函数,其用哈希表结构实现本文所做的实验都是在微机上进行的,处理器为:Pentiumll.60GHZ,内存为512M操作系统:MicrosoftXPProfessional,CAAR算法采用Java语言编写,实现平台为JBuilder9.0CAAR分类算法实现对装入的数据集进行分类关联规则的提取,构建分类器能够正确的预测未知样本的类标号此系统还可以显示,所测试数据集进行部分分类的次数,及每次分类所提取的原子规则,预测模型的分类准确度和建模时间机器学习系统主要由以下类函数实现:App:是对算法的应用也是学习模型的主函数3实验结果与分析文献[4]中给出了CAAR算法在26个不同类型数据集上的实验测试结果这里利用抽样技术对大规模数据集在不同采样点的分类准确度进行测试目前,对于大规模数据库知识发现,抽样技术是一种行之有效的方法这里对一个实际大规模数据集Census-ncIome进行不同采样点的测试该数据集取自在此函数中选择要测试的数据集CAAR:是对原子关联规则算法的实现用于产生原子规则,构建分类器,并计算建立分类模型的时间I0baGl:是用于对数据集进行抽样的类函数,然后对抽样到的数据进行训练和测试第4部分将列出 在大型数据集进行抽样,不同抽样率下,不同分类算法的分类准确度的比较Counter:是对候选原子规则前件和原子规则r对应2一项集计数的类函数该函数中实现按置信度表1 101000UCI(httP://kdd.ics.uci.edu/databases/census一income/census一income.html)提供的标准大规模机器学习测试数据库数据集包含199523个实例,有41个属性,调查的对象分为两类:一类是高于50000,另一类是低于50000实验中,数据集的连续属性均采用基于嫡的方法进行离散化算法在不同采样点下的分类准确度50001000020000300004000050000 记录数数CAARRCBAA19952295.31193.7111995597.244∀98一455399998.755100.000199998.999100.00099998.999100,000666100.000100.000499100一000100.000399100.000100.D00 J485.04493.999.444.444.90095.45587.75594.877本文利用C++实现的CBA算法及决策树中的由表1可以得出,在大规模数据集中CBA算法的分类准确度不及CAAR算法,因为CBA算法规定了挖掘的规则不能超过80000个0,规则左部的属性个数最大为6个,当遇到高维数据库时,当属性个数达到3个或4个时规则数过多就停止了,不能挖掘出完整的规则集,导致分类准确度的降低当数据集中实例个∃48算法进行对比测试,在不同抽样率情况下应用CAAR∀CBA及J48算法对所采集到的数据进行训练,并在该数据集上进行测试这里CAAR算法的动态支持度为0.01,其他算法的实验参数取缺省值(例如,CBA算法中规则前件最大长度为6)以下是实验结果: 82研究开发助~hand氏vel叩m印t2009年第7期计算机系统应用数减少时,CAAR和CBA的分类准确度相差不多,对抽样率较低的情况下,仍然能提取有效的分类模型,于较小数据集,两者的分类准确度相等,但是CBA算达到100%的分类准确度法分类模型学习时间却比CAAR长的多l]7由表1还这里再对UCI提供的200数据集进行10一折交可以看出,抽样率对∃48分类的影响较大,它的分类叉验证测试,对比CBA算法与CAAR算法的分类准确效果对抽样率的变化比较敏感对任何抽样率,∃48度该数据集有101个实例,无属性值的缺失先对的分类准确度都不如CAAR这是因为决策树∃48采200数据集进行随机洗牌,使实例随机的变换顺序,用基于嫡的技术,在类分布严重不均衡的情况下,148再对该数据集进行10一折交叉验证测试,计算测试的有忽略少数类的缺点,从而降级分类准确度在测试平均分类准确度表2是对上述过程重复21次的实中,CAAR算法采用动态支持度,在类分布严重倾斜,验结果:表2200数据集随机洗牌后10一折交叉验证测试的分类准确度算法数据集随机洗牌后10一折交差验证测试的分类准确度度1234567100111CAARR97.09993.00096.00095.985.00095.984.00095.994.996.00096.000CBAA92.09995.00092.00095.00092.185.27792.00095.09994.00094.09996.000算法数据集随机洗牌后10一折文差验证测试的分类准确度度12133144155l66l77f88199200211CAARR92.87797.00095.994.09997.983.995.00095.995.996.099CBAA93.00094.00092.00096.09994.09993.09994.00092.09995.00093.099由表2可以看出,CAAR算法赢17局,负3局,Links心ocumenis八mProved%20OneR%20Algorlthm.平1局21次10一折交叉验证的平均预测准确度:Pdf.CAAR为95.45%,CBA为93.77%,CAAR最高的分3LiuB,Hsu,WMaY.hite脚tingelassifieationand类准确度已高达98%可见,CAAR算法的分类准确sasoeiaitonrulemining.Proeeedignsof4thACMInt.度是优于CBA算法的Conf.onKDD,NewYor,k1998:80一86.4LiWM,HanJW,PeiJ.Cmar:Aeeur磁eandefifcient4结论elassifciationbasedonmuitiPleelass一sasoeiationrules.关联分类的分类准确度和分类模型的稳定性一直是巧eeedingsoftheIEEEInt.Conf.onDataMinign,研究人员关注的问题本文给出了CAAR算法构建分类Califo而礼2001:369一376.器的步骤,主要利用抽样技术,在大规模数据集中进行5YinXX,HanJW.Pcar:elassifieationbasedonPrediet-测试,验证了CAAR分类算法的有效性对200数据集itveassoeiaitonrules.Proeeedingsofthe2003SIAM进行的10一折交叉验证也表明CAAR的分类准确度明显tihemtaionalConferenceonDataMining高于CBA算法原子关联分类算法的分类模型简单,易(SDM03),SanF.Inciseo,2003:34一42.于理解,算法本身具有内在加速特性,执行速度快且分6胡可云,陆玉昌,石纯一基于概念格的分类和关联规则类准确度较高,在数据挖掘中具有重要的应用价值的集成挖掘方法.软件学抵加oo,ll(l1)l:478一1484.7XuXY,HanGQ,MinHQ.Con2It!cteonciseand今考万忆浦汽cacurateelassifierbyaotmieassocia-tionrules.Proeof1HolteCR.VerysimPleelassifieationrulesPerofmrhtehTdriIntoConfonMaehineLeamnignadwellonmosteorn们nonlyuseddaats出.MaehineCybemeties,NewYOrk:IEEEPress,2004,8:1604一Leanring,1993,(11):63一90.1609.2BuddhinatqDeryrD.AS汕PleEnhancementtoone8许孝元,韩国强,阂华清.多步原子规则的大规模关联uRleClassificaiton.htPt:刀认乃丫w.buddhinaht.n叫0出e卜分类.控制理论与应用,2007,(6:)471一474.eR,,吐chandE阳veloPment研究开发83
