第29卷第3期2008年3月东北大学学报(自然科学版)JournalofNortheasternUniversity(NaturalScience)Vol.29,No.3Mar.2008一种用于数据挖掘算法的数据生成方法魏伟杰,张 斌,王 波,张明卫(东北大学信息科学与工程学院,辽宁沈阳 110004)摘 要:由于受到保密性、时间和数据多样性等一些原因的限制,测试数据集的获取一直困扰着数据挖掘算法的研究·因此,提出一种基于遗传算法和熵的测试数据集的模拟生成方法,生成方法利用遗传算法具有继承性的特性对采集到的少量的真实数据进行扩充和模拟,用熵衡量生成数据与真实数据的相似程度,最终生成规模大的测试数据集,并给出了描述型数据的生成算法·使用此方法,可以生成同真实数据集具有相同的属性,相同的属性取值区间和属性值分布,类似属性关联关系的测试数据集,加速数据挖掘算法的研究进程·关 键 词:数据挖掘;算法测试;模拟数据集生成;遗传算法;熵中图分类号:TP274 文献标识码:A 文章编号:1005-3026(2008)03-0328-04AMethodGeneratingDataSetstoTestDataMiningAlgorithmsWEIWei-jie,ZHANGBin,WANGBo,ZHANGMing-wei(SchoolofInformationScience&Engineering,NortheasternUniversity,Shenyang110004,China.Correspondent:WEIWei-jie,E-mail:weiwj@126.com)Abstract:Becauseofsecurity,uncertaintime,diversityofdataetc,theproblemofhowtoacquirethedatasettotestdataminingalgorithmshasbeenconfusingthestudyondatamining.Asimulatingmethodisthereforesuggestedtogeneratethedatasetonthebasisofthegeneticalgorithmandentropy.ThemethodextendsafewdatawhichwerecollectedfromrealitybyGA,thenevaluatesthesimilaritybetweenextendeddatasetsandrealonewithentropy,andgeneratesthemostsimilardatasetofbigsizeamongtheextendedonesasthedatasettotestthedataminingalgorithms.Agenerationalgorithmisalsogiven.Thismethodisavailabletogeneratethedatasetfortesting,whichhasthesameattributes,scalesofattributevalueanddistributionsofattributevaluetothedatasetfromreality,aswellasthecorrelationsamongtheattributes.Thisdatasetfortestingwillacceleratethestudyondataminingalgorithms.Keywords:datamining;algorithmtesting;simulationofdatageneration;geneticalgorithm;entropy在数据挖掘算法的研究和测试过程中,获得测试算法用的数据集是一个十分重要的内容·由于时间、保密性、数据多样性、数据规模、噪音等原因[1]Quest测试数据生成代码和数据生成器[1][7]以及利用云模型生成数据的方法·测试时采用由数据挖掘研究机构提供的测试数据集,结果只能说明算法在测试数据集上的应用情况,无法分析和推断算法在其他具体数据集上的应用情况·而在使用数据生成算法生成数据集时,需要设定一系列的先验知识和规则,对于领域专家来说,人为制定面向一个复杂应用的先验知识和规则是不可能完成的因此,使用现有的数据集获取手段得到的数·据集无法满足算法测试的需要·为获得可用数据集,本文提出一种新的数据,很难获得可靠的测试数据集·并且,不同的算法需要不同数据集的支持[2-4]·缺少适用的数据集制约了数据挖掘研究的发展·目前用于数据挖掘算法测试的数据集可分为两类:①数据挖掘研究机构提供的测试数据集:KDDCup提供了一些测试数据集,包括通用数据集[5]和用于各类专项算法测试用的数据集[6];②使用数据生成算法生成的测试数据集:IBM的收稿日期:2007-03-30基金项目:国家自然科学基金资助项目(60773218)·作者简介:魏伟杰(1980-),男,辽宁沈阳人,东北大学博士研究生;张 斌(1964-)男,辽宁沈阳人,东北大学教授,博士生导师·第3期 魏伟杰等:一种用于数据挖掘算法的数据生成方法329生成方法DGGE(datasetsgenerationmethodbaseonGA&entropy),算法将真实数据作为原始数据集,使用遗传算法中的交叉算子和变异算子对原始数据进行扩充;对扩充后数据集进行分组;使用基于熵定义的数据集相似度函数计算扩充后数据集分组与原始数据集之间的相似度,选择相似度最高的数据集分组;在相似度的指导下反复进行数据集的扩充、分组、相似度计算和选择,以得到最终的数据集·以真实数据作为原始数据集,保证了数据中先验知识和规则的正确性和全面性;遗传算法对数据特征具有继承特性,可以将原始数据中所隐含的先验知识和规则继承到扩充数据集中,使算法不依赖领域专家制定的先验知识和规则;使用基于熵的相似度函数对生成过程进行指导,确保最终的数据集具有同原始数据集相同的属性,相同属性取值区间和属性值分布,类似的属性关联关系·试验证明,根据少量的真实数据,算法可以自主地生成算法测试数据集·生成数据集同真实数据具有相同的数据特性,可在具体的领域中测试挖掘算法·1 使用遗传算法的交叉算子和变异算子对数据集进行扩充使用遗传算法的交叉算子和变异算子对数据进行扩展,可以把搜索空间扩展到整个问题空间,实现数据集的扩充·1.1 将数据集编码为群体将采集到的每一条真实数据编码成染色体[8-9],形成群体·其形式如下:P=(c1,c2,…,cN),P为群体,c为染色体,N为群体中染色体的个数;c=v1v2…vk,其中k为染色体长度,vi(i∈k)为非负整数·1.2 使用交叉算子进行群体扩充对于群体中任意的两个染色体,使用交叉算子对染色体按照一定的概率Pc进行重组,生成新的染色体,新染色体继承了原有染色体的信息,将新染色体构成的群体与原有群体合并,实现群体的扩充·使用交叉算子最终将群体的大小增加了2×C2其中,C2N×Pc个,N为种群中任取两个个体的组合数,N为种群中个体数量·1.3 使用变异算子进行群体扩充对群体中的任意一个染色体,按照一定的概率Pm在某一个位置改变值,生成新的染色体·变异增加了群体中染色体的多样性,将新染色体构成的群体与原有群体合并,实现群体的扩充·变异算子将数据集的规模扩充了Pm×N个,其中,N为种群中个体数量·经过交叉算子和变异算子对种群的扩充,可以得到扩充的种群,种群大小为N+P2m×N+2×CN×Pc·1.4 对扩充群体进行分组使用交叉算子和变异算子产生的新染色体具有随机性,并不是所有的染色体都继承了原始群体中的特性·因此,需要对生成的染色体进行评估,判断染色体是否很好地继承了原始群体的特性·为评估染色体的继承性,将扩充后的群体分组,形成候选群体,以候选群体为单位来考察染色体中数据特征的继承情况·将继承情况最优的候选群体作为最终群体返回·2 基于熵的群体相似性函数熵可以对数据中的数据关系进行衡量,因此,采用基于熵的函数来衡量群体之间的相似度,进而衡量数据集之间的相似度·如果两个群体P1,P2相似,那么,1)两个群体中各个位置的取值具有相似的信息熵[10],即HP1(X)≈HP2(X)·其中,随机变量X表示群体中第i个位置的取值;HP1(X)是群体P1上第i个位置取值的信息熵;HP2(X)是群体P2上第i个位置取值的信息熵·2)群体P1中任意两个位置上的取值之间的互信息与群体P[10]2中对应值的互信息是相似的,即MP1(X,Y)≈MP2(X,Y)·其中,X,Y是群体中两个位置上的取值·3)两个群体对应位置上的取值的相对熵[10]相等且为零,即H(PP1(X),PP2(X))=n∑PP1(Xi)lgPP1(Xi)P≈0i=1P2(Xi)·其中,随机变量X表示群体中的任意位置取值·设原始群体为PI,一个群体分组为PG,由上面的论断,得出群体相似度计算函数为f(PI,PG)=fI(PI,PG)+fM(PI,PG)+fH(PI,PG)·其中,330N东北大学学报(自然科学版) 第29卷fI(PI,PG)=fM(PI,PG)=NN∑(HPG(Xi)-HPI(Xi)),i=1度函数计算群体分组与原始群体的相似度,得到其中相似度最高的候选群体·如果候选群体满足终止扩充条件,那么,将候选群体作为结果群体,向下执行;否则,将候选群体作为下一次的待扩充群体,返回步骤2)·4)将结果群体解码,形成测试数据集·∑∑j=1i=1MPG(Xi,Yj)-MPI(Xi,Yj),i≠j,NfH(PI,PG)=∑H(Pi=1PG(Xi),PP(Xi))·IN为染色体的长度,Xi,Yj为对应于染色体位置i和j的随机变量·f(PI,PG)趋近于零,群体分组与原始群体相似;f(PI,PG)等于零,两群体等价·4 实验与分析以中医小儿肺炎数据挖掘所使用的数据为例,采集到的进行数据挖掘的数据为9839例,从中随机抽取1000例作为数据生成算法的初始数据集进行数据的生成,数据生成算法中的参数是:初始种群中个体数为1000,交叉概率Pc为0.6,变异概率Pm为0.001,扩充因子SL为1.1,相似度阈值为0.01·算法DGGE用VC++实现,实验平台是内存为512MB,处理器为Pentium41.86G,使用WindowsXP操作系统的个人计算机·取真实数据集和模拟数据集中对应的两个属性Attr1,Attr2(两个属性各有5个取值,对应为图1中的坐标0～4)进行属性关联程度的比较·数据集中的数据是描述性的属性,为展示数据点的分布,在比较属性关联程度时,对坐标系中坐标重复的点进行偏移处理,以反映坐标系中表征两个数据相关程度的点的分布密集程度·使用Weka[11]3 测试数据集生成方法基于上述讨论,本文构造了一种基于遗传算DGGE(datasets法和熵的测试数据生成算法:generationmethodbaseonGA&entropy)·算法的目标是以采集到的少量真实数据为基础进行模拟,生成同真实数据集相似的规模足够大的数据集,用于测试数据挖掘算法·基本步骤如下:1)数据预处理过程,以应用领域内的少量真实数据为基础,对真实数据进行编码形成遗传算法可以处理的原始群体,将原始群体作为待扩充群体·2)数据扩充过程,使用遗传算法中的交叉算子和变异算子扩大待扩充群体的规模,形成扩充群体·对扩充群体进行分组,形成多个候选群体·为保证群体的扩充,分组大小为待扩充群体的SL倍,其中,SL大于1,称为扩充因子·3)基于熵定义数据集相似度函数,使用相似的可视化工具进行展示,如图1所示·其中图1a为真实数据集中两个属性的分布,图1b为模拟数据集中两个属性的分布·图1 属性联合分布图Fig.1 Associateddistributions’figureoftwoattributes(a)—真实数据集;(b)—模拟数据集·可以看到,面向指定的领域,领域内数据之间是有关联的,即不同的坐标点附近的数据点的个1)数是不同的虽然图1a和图1b中坐标位置(1,·处的数据点分布有些偏差,但是总体上说,模拟数据的联合分布情况同真实数据中的联合分布情况是相似的·5 结 论本文提出了一种结合遗传算法和熵的数据生成方法·该方法根据从现实世界中采集到的小规第3期 魏伟杰等:一种用于数据挖掘算法的数据生成方法331模数据集,使用遗传算法对数据集进行扩充,用基于熵的相似度函数测试数据集同现实真实数据集的相似度,以生成同真实数据相似的测试数据集·生成算法不依赖使用者制定的先验知识,并保证了生成的数据集具有同原始数据集一致的属性间的关联和属性值的分布,生成算法为数据挖掘算法的测试提供了可靠的数据集·参考文献:[1]杜 ,李德毅·一种测试数据挖掘算法的数据源生成方法[J]·计算机研究与发展,2000,37(7):776-782·(DuYi,LiDe-yi.Amethodofdatasourcegenerationfortestingdataminingalgorithms[J].JournalofComputerResearch&Development,2000,37(7):776-782.)[2]DasG,LinK,MannilaH,etal.Rulediscoveryfromtimeseries[C]∥ProceedingsoftheFourthInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:AAAIPress,1998:16-22.[3]SatouK,ShibayamaG,OnoT,etal.Findingassociationsrulesonheterogeneousgenomedata[C]∥ProceedingsofthePacificSymposiumonBiocomputing’97.Hawaii:IEEEPress,1997:397-408.[4]HatonenK,KlemettinenM,MannilaH,etal.Knowledgediscoveryfromtelecommunicationnetworkalarmdatabases[C]∥Proceedingsofthe12thInternationalConferenceonDataEngineering.NewOrleans:IEEEPress,1996:115-122.[5]DatabaseResearchGroup.Datacollection[DB/OL].HongKong:ChineseUniversityofHongKong,(2005-06-15)[2007-01-20].http:∥www.cse.cuhk.edu.hk/～kdd/data-collection.html.[6]KDDCup2000.Realdatasetsforassociationrulediscovery[DB/OL].Boston:ACMSpecialInterestGrouponKnowledgeDiscoveryandDataMining,(2002-06-18)[2007-01-20].http:∥www.ecn.purdue.edu/KDDCUP/data/BMS-POS.dat.gz.[7]IBMAlmadenResearchCenter.Questsyntheticdatagenerationcode[CP/OL].UnitedStates:IBM,[2007-01-20].http:∥www.almaden.ibm.com/cs/projects/iis/hdb/Projects/data-mining/mining.shtml.[8]周明,孙树栋·遗传算法原理及应用[M]·北京:国防工业出版社,1999:34-56·(ZhouMing,SunShu-dong.Geneticalgorithms:theoryandapplications[M].Beijing:NationalDefenceIndustryPress,1999:34-56.)[9]MelanieM.Anintroductiontogeneticalgorithms[M].Boston:MITPress,1998:121-124.[10]CoverTM,ThomasJA.Elementsofinformationtheory[M].NewYork:JohnWiley&Sons,1991:130-233.[11]TheUniversityofWaikato.Weka3.4[CP/OL].Waikato:Opensource,(2005-03-07)[2007-01-20].Http:∥www.cs.waikato.ac.nz/ml/weka/index.