基于灰色系统理论动态关联规则挖掘研究

《基于灰色系统理论动态关联规则挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

硕士学位论文基于灰色系统理论的动态关联规则挖掘研究ResearchonDynamicAssociationRuleMiningbasedonGreySystemTheory作者姓名:石皓尹学科、专业:计算机应用技术学号:0211741指导教师:张忠林完成日期:2014.04兰州交通大学LanzhouJiaotongUniversity万方数据 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含获得兰州交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解兰州交通大学有关保留、使用学位论文的规定。特授权兰州交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日万方数据 兰州交通大学硕士学位论文摘要数据挖掘是通过分析大型数据库或数据仓库中的数据，从而揭示其中隐含未知的或验证已知规律的过程。数据挖掘大致可分为分类、回归、关联规则、时间序列和聚类等模式，其中关联规则是应用得最为普遍的方法，同时也是近年来研究的热点。传统的关联规则是一种基于事务数据库的一种静态的挖掘，但是挖掘的过程中并没有充分考虑到关联规则随时间变化的特性。经过长期的实际运用和研究发现，在实际数据库里面挖掘出来的关联规则往往具有时间特性，因此有必要把规则的时间特性加入到关联规则的挖掘之中，进而观测关联规则在时间上的变化。为了描述关联规则随时间变化的这一特性，动态关联规则应运而生。动态关联规则通过对数据集进行等时间段划分实现对规则时间特性的描述。但是，由于传统的动态关联规则是基于已有数据的挖掘，对于得到的强动态关联规则，我们很难确定它们在将来是否还有效。同时，目前对于动态关联关联规则挖掘研究主要集中在挖掘算法的改进方面，较少涉及到时序数据库中关联规则挖掘质量的问题。因此有必要对动态关联规则挖掘进行更深层次的研究，从而获得高质量的、有真实价值的信息。本文在研究灰色系统理论等相关知识的基础之上，利用灰色模型独特的少数据建模且精度较高的特点，将灰色系统理论与动态关联规则元规则挖掘以及动态关联规则趋势度挖掘相结合，提出了基于灰色-周期外延模型的动态关联规则元规则挖掘算法和基于灰色马尔可夫模型的动态关联规则趋势度挖掘方法。通过针对不同类型的数据，建立不同的数据模型，发现以上两种算法在面临原始数据较少时充分发挥了灰色模型的优点，对于数据的建模和预测都有着很好的效果。同时，将所提出的方法运用在实际的挖掘中，验证在实际挖掘中所具有的实用性以及较高的预测精度。通过与近几年提出的基于动态关联规则元规则和动态关联规则趋势度的挖掘算法进行对比，发现本文所提出的方法挖掘出的规则质量更高、可用性更强，在一定程度上克服了挖掘的盲目性，最大程度的挖掘有效规则以及潜在规则，有效提高了动态关联规则挖掘的效率和挖掘结果的参考价值。与传统的动态关联规则挖掘算法相比，通过数学模型分析规则的变化趋势，能得到规则随时间的变化情况。关键词：动态关联规则；元规则；趋势度；灰色系统理论；组合模型论文类型：应用研究-I-万方数据 基于灰色系统理论的动态关联规则挖掘研究AbstractDataminingisaprocessofrevealingtheimpliedknownunknownorvalidationrulesbyanalyzingdatainlargedatabaseordatawarehouse.Itcanberoughlydividedintomanymodelssuchasclassification,regression,associationrules,timeseriesandclusteramongwhichassociationrulemodelisthemostwidelyusedmethodandit’sahotspotofresearchinrecentyearsatthemeantime.Thetraditionalassociationruleminingisakindofstaticminingbasedontransactiondatabase.Butintheprocessofminingit’snotfullyconsideringthecharacteristicsofthechangeovertime.Afteralongperiodofpracticalapplicationandstudy,it’sknownthattheassociationrulesminedintheactualdatabaseareoftenwithtimecharacteristics.Soit’snecessarytojointhetimecharacteristictotheminingprocesstoobservethechangesofrulesovertime.Thedynamicassociationruleminingwasbornconsideringthattheruleschangeovertime.Itsetsboundariesondatasetstodescribethetimecharacteristicoftherules.Butbecauseofthatthetraditionaldynamicassociationruleminingmethodsarebasedonexistingdata,it’sdifficulttoknowwhetherthestrongdynamicassociationrulesarestillvalidinthefuture.Andatthesametime,thecurrentdynamicassociationruleminingresearchesaremainlyfocusonimprovingalgorithmandlessinvolvedinthequalityofminingintemporaldatabase.Soit’snecessarytododeepenresearchondynamicassociationruleminingtoobtaininformationwithhighqualityandrealvalue.Thispaperproposedadynamicmeta-ruleassociationruleminingalgorithmbasedonGrey-cycleextensionmodelandamethodoftendencyminingbasedonGreyMarkovmodelindynamicassociationrulebycombiningthegreysystemtheory,thedynamicassociationmeta-ruleminingandtendencyminingtogetheronthebasisoftherelevantknowledge.Bysettingupdifferentmodelsinviewofdifferenttypesofdata,thegiventwoalgorithmsfullytakeadvantagesofgreymodelwhentheoriginaldataissmallandhaveabettereffectfordatamodelingandprediction.Andbyapplyingtheproposedmethodsinactualmining,theyareprovedtobevalidandhavehigherprediction.Bycomparingtheproposedmethodswiththetraditionaldynamicassociationmeta-ruleminingmethodsandtendencyminingalgorithm,thetwomethodsareprovedcanminhigherqualityandstrongerrules.Andtoacertaindegreetheyovercometheblindnessofminingandcanmaximummineffectiveandpotentialrulestoeffectivelyimprovetheefficiencyofthedynamicassociationruleminingandreferencevalueoftheresults.Anddifferentwiththetraditionalalgorithm,theproposedmethodscangettheruleswiththechangeovertimebyanalyzingthetendencyoftherulethroughthemathematicalmodels.-II-万方数据 兰州交通大学硕士学位论文Keywords:Dynamicassociationrule;Metarule;Tendency;Greysystemtheory;Combinedmodel-III-万方数据 基于灰色系统理论的动态关联规则挖掘研究目录摘要.....................................................................................................................................IAbstract......................................................................................................................................II1引言...................................................................................................................................11.1研究的背景和意义......................................................................................................11.2研究现状......................................................................................................................21.2.1存在的不足.......................................................................................................21.2.2解决问题的基本思想和方法...........................................................................21.3研究的内容和创新......................................................................................................31.4本文的组织结构..........................................................................................................32关联规则描述.........................................................................................................................52.1关联规则的基本概念..................................................................................................52.2关联规则挖掘过程......................................................................................................62.3关联规则分类..............................................................................................................72.4基本算法......................................................................................................................82.4.1Apriori算法.......................................................................................................82.4.2FP-Growth算法...............................................................................................112.5动态关联规则............................................................................................................132.5.1动态关联规则的原定义.................................................................................132.5.2原定义的补充和改进.....................................................................................152.6元规则定义................................................................................................................172.7趋势度定义................................................................................................................172.8本章小结....................................................................................................................183灰色系统理论.......................................................................................................................193.1灰色系统概念与原理................................................................................................193.2灰色系统模型............................................................................................................203.2.1灰色系统建模思想.........................................................................................203.2.2GM1,1模型.................................................................................................203.2.3GM1,1模型的检验.....................................................................................223.3灰色组合模型............................................................................................................223.3.1灰色-周期外延模型.......................................................................................23-IV-万方数据 兰州交通大学硕士学位论文3.3.2灰色马尔可夫模型.........................................................................................243.4本章小结....................................................................................................................254基于灰色模型的动态关联规则元规则以及趋势度挖掘...................................................264.1基于灰色-周期外延模型的动态关联规则元规则挖掘..........................................264.1.1算法描述.........................................................................................................264.1.2建模过程.........................................................................................................264.1.3实验分析.........................................................................................................274.1.4方法对比.........................................................................................................304.2基于灰色Markov模型的动态关联规则趋势度挖掘.............................................324.2.1算法描述.........................................................................................................324.2.2建模过程.........................................................................................................334.2.3实例分析.........................................................................................................334.2.4方法对比.........................................................................................................384.3本章小结....................................................................................................................40结论...................................................................................................................................41致谢...................................................................................................................................43参考文献.............................................................................................................................44攻读学位期间的研究成果.......................................................................................................48-V-万方数据 兰州交通大学硕士学位论文1引言1.1研究的背景和意义在科学技术高速发展的趋势之下，人们将面临越来越多的信息。为了能够更高效地管理数据，以数据库技术为核心的信息处理技术得到了极大的发展，数据分析和数据建模技术也得到了巨大进步。关系数据库的研究取得了极大进展，使关系数据库系统逐渐成为应用范围最广的数据库系统，同时，研究人员也开始着手研究和开发功能更为强大的数据库系统。在数据库技术逐渐成熟的基础之上，相关研究人员将探索的重点逐渐转移到了如何有效地从数据中发现知识的研究之上。因而，数据挖掘(DM:DataMining)作为知识发现(KDD:KnowledgeDiscoverinDatabase)过程之中一个核心的技术受到了研究人员和学者的广泛关注[1]。由于人类对各类信息的时效性和有效性等要求逐步提高，因而怎样从大量的数据中快速准确地找出自己所需要的数据信息，特别是从具有海量数据的数据库或者数据仓库中的找出有价值的信息成为目前研究的主要方向。数据挖掘简要的来说就是通过一定的方法挖掘出不容易被人们发现的、有价值的以及潜在信息的过程，而且通常这些经过挖掘得来的数据信息是隐藏在模糊的、有噪声的、不完全的大量数据之中[2]，数据挖掘是通过利用关联规则从大型数据库中提取出对人们有利用价值信息的过程，提取的知识表示为概念以及规则等形式。数据挖掘是在一些相互关联的学科的基础上发展建立起来的。由于数据的背后普遍隐藏着很多有价值的信息，这在一定程度上加快了数据挖掘在实际生活中的多维发展和广泛应用。进而提出了关联规则的相关概念和极具影响力的Apropri算法，但是挖掘的过程中并没有充分考虑到关联规则随时间变化的特性[3]；鉴于此，在本世纪初国外著名的研究学者GANTIV和GEHRKEJ首次提出了基于时间特性的关联规则[4]；同时，国内相关研究人员在文献[5,6]中提出了用支持度和置信度二个特征变量来衡量关联规则在时间上变化的动态性；为了描述关联规则随时间变化的特点，在综合以上研究的基础之上，文献[7]率先提出了动态关联规则的相关概念，并且对动态关联规则的基本定义进行详细的描述，通过动态关联规则对模式自身的变化过程进行描述；在创新动态关联规则原有学说和挖掘方式的基础之上，提出了二种新的动态关联规则挖掘算法[8]；随着动态关联规则体系的不断完善，文献[9]提出了动态关联规则元规则的理论，将元规则作为描述和权衡动态关联规则的一个参考因素；文献[10]中提出了一种基于时间序列的动态关联规则挖掘方法，而文献[11-14]将时间序列的相关概念、马尔可夫链理论以及相关模-1-万方数据 基于灰色系统理论的动态关联规则挖掘研究型、灰色系统理论以及相关模型、自回归模型、小波变化以及相关的组合模型运用到动态关联规则元规则挖掘当中，在一定程度上提高了适用范围和预测的精度；为了进一步完善动态关联规则体系，文献[15]提出了动态关联规则趋势的相关定义，将趋势度作为判定动态关联规则强弱性的一个重要标准。在上个世纪末，灰色系统理论被我国研究人员提出[16]。该理论一经提出就被极其广泛的应用于经济、社会、科技、学术研究、农业、生态等各个领域。经过较长时间的实践应用和系统理论的不断完善，灰色系统理论已经发展成为一套相当完善和严谨的理论，在全球各行各业中间产生了巨大的影响[17-20]。1.2研究现状1.2.1存在的不足针对动态关联规则元规则挖掘所提出的各种方法在适用范围和预测精度上有一定的不足：由于使用自回归模型、马尔可夫链理论、小波变换等模型建模时需要大量的历史数据才能得到可信度比较高的指导信息，而当在历史数据信息较少的情况下单纯的运用自回归模型、马尔可夫链理论、小波变换等模型时建模预测的精度会大大的降低，从而使得到信息可靠性偏低；同时，在实际生产中，大量的历史数据或强或弱的都会表现出一定的周期性，即：各类数据信息会随着人为划分的时间段或者自然时间段出现一定周期性的变化，而以上方法忽视了原始数据的周期变化的特点，例如：马尔可夫链理论只考虑到原始系统的随机变化的规律。综上所述，可知以上方法所使用的领域并不能完全涵盖和解决在实际生活以及生产中所遇到的问题。由于没有一种完美的数据建模模型适用于所有遇到的情况，因此，必须用新的方法来进行动态关联规则元规则的挖掘，从而进一步扩大元规则挖掘的适用范围，进一步提高预测的精度，为决策者提供更好的更有价值的可靠信息。文献[15]虽然提出了一种挖掘趋势度的方法，但是也存在着一些不足。例如：只考虑目前各个规则的强弱性，而忽视了规则之后会朝着什么方向来发展，是稳定的、是大幅度的变强变弱或者小幅度的变化。因而它只能够给决策者提供有限的参考，而决策者对于规则在现在之后的时间段内的变化，往往只能通过自身的经验或者其他一些因素做出可靠性较低的决定，其决策的风险性可想而知。1.2.2解决问题的基本思想和方法灰色模型具有在数据量较少的时候预测精度高，且只需要三个数据就可以建模的特点，这是其他的模型所不具有的。因此，在动态关联规则元规则挖掘中运用灰色模型是-2-万方数据 兰州交通大学硕士学位论文非常有必要的。但是由于灰色模型只能反映出原始数据或者历史数据总的变化趋势，对于数据的周期性变化没有充分顾及，因此将周期外延模型与灰色模型相结合可以扩大挖掘范围和提高预测精度。同理，在动态关联规则趋势度的挖掘之中引入灰色系统理论可以使挖掘更有效果，能够提供更多有价值的参考信息。因此，本文在之前介绍的由众多研究者的研究成果的基础之上，将灰色系统理论与动态关联规则相结合，运用其它建模模型组成的灰色组合模型进一步改进了动态关联规则表示性方法。将灰色模型运用到动态关联规则趋势度的挖掘之中，在很大程度上完善了原有定义，同时可以挖掘出更全面的可用信息，使趋势度挖掘的有效性进一步增加。1.3研究的内容和创新本文首先详细的描述了关联规则的基本概念和基本表示形式，并且着重介绍了关联规则挖掘的二种经典的挖掘算法：Apriori算法以及在Apriori算法的基础之上有着很大改进的Fp-growth算法，同时对以上两种挖掘算法的具体挖掘过程给出了详细的阐述和对比。为了能够更好地观察动态关联规则在时间的特征分析和趋势变化，引入时间序列概念这一特性，将灰色组合模型运用在动态关联规则元规则以及趋势度的挖掘当中。从而提出了：基于灰色-周期外延模型的动态关联规则元规则挖掘方法和基于灰色-马尔可夫模型的动态关联规则趋势度挖掘方法。对其建模思想和建模过程进行深入分析，然后进行试验和实例的仿真和数据分析，最后在与其他原有方法对比的基础上，分析所提出方法的优点。下面的将本文的创新点予以说明。(1)在动态关联规则元规则挖掘中观测支持度向量计数趋势变化，分析其存在的周期性。针对支持度向量计数存在的小数据性和周期性，建立灰色-周期外延模型进行规则的挖掘。(2)将灰色马尔可夫模型运用到动态关联规则趋势度挖掘当中，对原有方法进行改进，从而获得更多有价值的规则信息。1.4本文的组织结构第一章详细介绍了本论文的选题背景、研究的意义、目前研究存在的不足以及解决问题的基本方法和思路，研究的目的、论文主要的研究内容以及论文的创新点等。第二章阐述关联规则挖掘的基本定义和分类，介绍FP-growth算法和Apriori算法并且分析了以上两种算法的优点与存在的不足。介绍动态关联规则相关概念和已有的动态关联规则挖掘算法，并且指出了动态关联规则原定义存在的不足。给出了元规则的内涵和形式化定义，详细介绍了趋势度的基本概念和一种基本的挖掘方法。第三章详细的描述了灰色系统理论的基本定义以及建模思想，着重介绍灰色模型-3-万方数据 基于灰色系统理论的动态关联规则挖掘研究中最为常用的GM1,1模型，并对其建模过程进行阐述。在此基础之上，提出了两种基于灰色系统理论GM1,1模型的组合模型，即：灰色-周期外延模型和灰色马尔可夫模型，并且分析两种模型的特点。第四章将以上两种模型应用在具体的动态关联规则趋势度和元规则实例当中，并且与原有方法进行对比，分析方法的可行性和有效性以及所具有的优势。最后，对全文进行总结和展望。总结本文的研究成果，分析本文目前研究存在亟需改进之处，为进一步的研究工作作出展望。-4-万方数据 兰州交通大学硕士学位论文2关联规则描述由于存储在数据库中的存储数据量不断地增加，数据与数据之间的关联性逐渐提高，进而我们从这些看似毫无关系的数据中经过挖掘从而得到有价值的关联规则的可能性也越来越大。例如：在实际的经济活动的数据库中挖掘有价值的关联规则能够在一定程度上辅助商家设计合理的商品目录、优化商品具体的摆放位置、便于实施交叉营销等相关策略。关联规则挖掘之中最典型的应用就是针对市场购物的分析，它可以根据历史销售数据通过一定的挖掘方法分析出其中某些顾客的一些消费习惯，从而发现购物者同时购买的某种或者若干种商品的概率，这能在很大程度上帮助管理者制定或者优化更加高效的市场营销策略。分析超市销售数据：购物者在购买牛奶时，是否会同时购买面包以及这种可能性有多大。显然如果管理者得到了这些相关的信息，就可以对商品进行合理摆放，有针对性的进行商品促销，同时也会在很大程度上提高其他周边商品的销售量，进一步提高经济活动中的效益。进一步分析：如果有这种可能性，那么便可以将牛奶和面包放在相邻或者比较近的位置，那么会同时提高两者的销量；若这种可能性非常大，可以认为买牛奶的顾客一定会买面包，那么可以将两种商品分别放在距离较远的两个地方，那么可以使顾客在买了一种商品之后寻找另外一种商品的过程中能够看到更多种类的其他商品，从而提高顾客购买其它商品的可能性。因此，不管是在实际的销售还是生产中，充分考虑这种关联规则的重要性都有着积极意义。2.1关联规则的基本概念关联规则是由AgrawalR等人在1993年率先提出。关联规则可以表现为形如AB的这种形式，I表示为项的集合。在给定的一个事务数据库中，用t来表示非空子集I的每个事务，TID代表标识符(TransactionID)且与事务数据库中每条记录一一相对应。支持度则表示在事务数据库中D中包含的A、B的概率百分比；同样的，置信度表示的是在数据库既包含项A的事务中项B存在的概率。支持度和置信度的阈值需要在关联规则挖掘之前进行人为的设定，而设定这个值需要专业人员根据某些因素进行决定。挖掘出来的数据一定满足最小的支持度和最小置信度才有使用价值。如果设定的支持度的阈值过大，那么所挖掘出来的关联规则就会不足；如果设定的支持度的阈值过小，会产生一些噪声规则、无用的规则。关联规则在数据挖掘中占有举-5-万方数据 基于灰色系统理论的动态关联规则挖掘研究足轻重的地位，很多算法都是在此基础上提出的。AgrawalR等人在文献[3]对关联规则的定义如下：定义2.1设Iii,,,i，I代表项的集合，D表示事务数据库的事务集合，T为12n事务数据库D中的事务是一个非空项集，每个I(Iii,,,i)由若干个事务T组成，12n即TI。D中每一个事务都对应唯一的一个事务标示符，称之为TID。设A和B都是一个项集，A、B包含在事物T中，即AT，BT。关联规则是形如AB的蕴涵式，其中AI，BI，A，B，并且AB=，AB同时具有支持度s和置信度c。定义2.2规则AB的支持度(Support)的定义为在数据库D中事务包含AB（即集合A和B的并集或者A和B两者）的百分比。可以表示为：Support(AB)PAB(2.1)定义2.3AB的置信度(Confidence)的定义为在事务数据库D中包含A的事务同时也包含B的事务的百分比，为条件概率。即：Confidence(AB)PBA|(2.2)2.2关联规则挖掘过程支持度和置信度是评价关联规则的重要标准，只有大于最小支持度和置信度的关联规则才是有作用的。人为设定置信度和支持度阈值之后，在事务数据库中进行关联规则挖掘时，需按照支持度和置信度这两个度量指标进行选择。其中支持度用来统计关联规则在整个数据集出现的情况，是对规则重要性的衡量；而置信度则是在支持度的条件下挖掘某个频繁项集，可以用来考量规则的重要性及其可靠的程度。规则支持度的大小可以说明规则事务集中代表性有多大，支持度越大，规则的重要性也就越高。若一个项集中有k项，称此项集为k项集，项集的频率是该项集所出现的次数。在整个数据库总数占有的比例大或者等于最小支持度Support(AB)，那AB对应的min项集是频繁项集，支持度Support(AB)可通过AB的频数在总事务数所占的比例而得到，而置信度则Confidence(AB)可利用AB支持度Support(AB)与A的支持度Support()A相比得到。一般而言，关联规则的挖掘过程一般可以划分为以下两个阶段[2]：(1)首先遍历数据库，通过挖掘事务数据库，找出所有的频繁项集，同时确保这些频繁项集出现的次数大于或等于预先设定的最小支持度计数min_sup。(2)将1中满足最小置信度min_conf要求的频繁项集作为强关联规则进行输出。-6-万方数据 兰州交通大学硕士学位论文由于基本过程的第一步需要遍历查询整个事务数据库，不但会历经一个很长的过程，而且得到结果的数据量是很庞大的。因此算法的速度和时间开销是衡量算法高效性的一个重要指标。第二步相对于第一步来说相对简单和直接，而对于每一个频繁项集S，找到S的所有非空子集A、B，其中BSA，如果满足SupportS/upportSAminconf，则生成关联规则ASA，其中SupportS/upportSA为规则ASA的置信度。为了更加直观的表现关联规则挖掘过程，我们可以用算法的基本过程图来直观的表述，如图2.1所示：D第一步第二步RMin-sup用户图2.1关联规则挖掘模型其中上图2.1中R表示输出的结果也就是用户得到的强关联规则集，数据库D为事务数据库，第一步和第二步表示以上算法的两个基本过程。两个过程分别用最小支持度和最小置信度来进行判定。2.3关联规则分类(1)对于很多应用而言强关联规则可能是在较高的抽象层发现的，虽然它有很高的支持度，但是可能是一般的常识性规则知识，实际意义不大。这时我们希望能够往较低层次继续挖掘，在更细节更低的抽象层发现新颖的模式。关注在多个抽象层之间进行挖掘，更容易在不同的抽象空间转换，实现更加灵活的挖掘。(2)关联规则按照挖掘的思维方法分为：基于数据立方体挖掘的量化关联规则、基于聚类的量化关联规则以及使用统计学理论发现的三种类别。(3)关联规则可在不同维数的事务数据库中进行挖掘，因此可以将关联规则分为单维和多维关联规则。(4)根据数据需要处理的标量的类型来进行划分，关联规则可以划分为数值型和布尔型，其中数值型的含义是把它与多维关联或多层关联规则结合起来，用来对数值型的-7-万方数据 基于灰色系统理论的动态关联规则挖掘研究字段进行处理，并且将其动态的划分，而布尔型关联规则则就是把数值进行离散化和种类化，这样做的目的就是显示了这些变量之间的关系。2.4基本算法关联规则挖掘挖掘算法大致分为以下四种：Apriori算法[3]、FP-Growth算法[21]、OP算法[22]、H-Mine算法[23]等，其中最为经典且影响力最大的两种算法是Apriori算法和FP-Growth算法。很多算法都是在这两种算法的基础之上通过改进和优化演变而来的，因此下面重点介绍这两种算法。2.4.1Apriori算法Apriori算法其核心思想是基于两阶段频集思想的递推。Apriori算法其过程可以大致可以分为搜寻发现所有的频繁项集和由找到的频繁项集产生规则进而输出两个相关联的阶段。此方法是一种逐层扫描搜索的迭代方法，该算法由k-项集搜索(k1)-项集。首先，遍历数据得到频繁1-项集的集合L；之后在频繁1-项集和L中的通过不同11项去其它项相连接方式产生所有可能的候选2-项集的集合C(即产生所有的2-项集，不2管它是否满足要求；同时符合要求的频繁2-项集也一定在集合C中)；然后使用频繁项2集的性质对C的集合进行过滤得到频繁2-项集的集合L(即：去除不满足要求的2-项22集)。然后，利用频繁2-项集L搜索频繁3-项集L(同上：其过程也是先产生所有可能的233-项集再进行检验去除不满足要求的项集)，如此下去，一直到k-项集不是频繁项为止[2]。该算法是建立在集合空间理论之上的，运用到了集合理论的相关知识：任意一个k-项的频繁项集的任何非空子集都是一个n-项的频繁项集，其中1nk；而任何一个k-项的非频繁项集的超集(以此非频繁项集为子集的集合)都是非频繁项目集。综上所述，Apriori算法来挖掘频繁项集的基本过程就可以分为连接和剪枝两个过程：(1)连接步根据连接性质，依次连接L集合中所有可以连接项集得到C。如果L为频繁k1kk1(k1)-项集的集合，连接步就是通过频繁项集L从而产生C的过程，其中C为候选k-k1kk项集的集合。I和I为集合L中的两个项集，那么I表示项集I的第j项。如果频繁12k1iji项集I和I有且只有前k2个元素相同，也就是I和I只有最后一个元素不同，那么I12121和I就是可以进行连接的。若果两个项集是可连接操的，那么操作就是把I和I的组合212-8-万方数据 兰州交通大学硕士学位论文产生一个k-项集:即I11,I12,I1k2,I1k1,I2k，其中：II,II,II(2.3)112112221k22k2(2)剪枝步由于任何(k1)-项的非频繁项集都不可能是频繁k-项集的子集，因此经过接步可以得到频繁k-项集L的超集C，即候选项集C中包含所有的频繁项集L。但是候选项集kkkkC中的项集也可能是非频繁的。因此，如果一个候选k-项集的(k1)-项集不在频繁k(k1)-项集的集合L中，则该候选项集肯定不是频繁项集，必须C中将其删除[2]。在k1k整个剪枝的过程中需要再次扫描整个数据库，以便于计算得到频繁候选项集C中每一个k候选项的计数数值，即：频繁次数，进而确定L。kApriori算法描述如下[2]：算法:Apriori假设D表示事务数据库，L为频繁项集的集合输入:D;min_support；//D为事务数据库，设定的最小支持度输出:L。//L为频繁项集kkL1find_frequent_1_itemsetsD;for(k2;L；k){k1Ckapriori_genLk1,min_support；//频繁k1-项集生成候选k项集foreachtransactiontDCtsubsetC,tk;//构造t的候选子集foreachcandidatecCtc.count++;}L{cC|c.count0}＞kk}//C为候选项集kreturnLL;kk其中函数apriori_gen()的核心算法描述如下：foreachitemsetlL1k1foreachitemsetlL2k1if(l1l1l2l2lk1lk1then{121212-9-万方数据 基于灰色系统理论的动态关联规则挖掘研究cll；//连接12ifcontain_subset_infrequent(c,L)thenk1delete(c);//剪枝elseaddctoC;k}returnC;k函数contain_subset_infrequent()实现了候选k-项集的剪枝，其算法描述如下：foreachk-1subsetsofcifnotsLthenk1returnTRUE;returnFALSE;Apriori算法完全是按照关联规则挖掘的基本思路和理论来进行分两步实现的：连接和剪枝。Apriori算法是一种经典的关联规则挖掘方法，同时也存在这效率不高等问题，但是它的优点在于易于理解，实现起来比较简单。同时也伴随着产生了算法效率存在一定的瓶颈问题，主要表现以及原因主要在以下几个方面：(1)人为设置的支持度和趋势度阈值，会直接造成挖掘出的规则不同，难以发现用户真正需要的规则信息。(2)不可避免产生数量庞大的候选项集。当产生的频繁1-项目集的数量过于庞大的时候，那么通过连接步产生的候选2-项集会以指数级别增加，这大大增加了算法的时间和空间开销，直接造成算法效率的低下。例如频繁1-项目集的数据为104个，那么经过连接后就有可能产生接近107个2-候选集，这对时间和主存空间都是一种考验。(3)多次扫描数据库。在连接步和剪枝步都需要多次扫描源数据，尤其在剪枝步对候选项集进行验证的时候，候选项集有多少个项，就需要扫描遍历几次原数据，这个过程耗时很大。为了进一步提高Apriori算法的性能和效率，已经有很多基于Apriori算法且经过优化改进的算法被提出。这些新的算法与原Apriori算法的区别以及改进优化的方向在以下几个方面：(1)提高产生频繁项集的性能。(2)进一步减少扫描数据库的次数。(3)运用新的理论方法进一步减少候选集的数量。(4)改善输出和输入的方法规则。(5)将优化的并行算法运用到Apriori算法当中。-10-万方数据 兰州交通大学硕士学位论文这些方面的重大改进，进一步扩大了Apriori算法的适用范围。在数据量较大的情况下，运用Apriori算法也能有很好的效果。2.4.2FP-Growth算法由于Apriori算法是一个基本算法而且有很多待改进的地方，同时最重要的是它需要二次扫描数据库，这对算法效率的影响很大。FP-Growth(Frequent–PatterGrowth)算法是由HAN等人在2000年提出的一个以分而治之策略为核心思想的基于Apriori算法改进的算法[21]。与Apriori算法最大的不同是该算法只需要一次扫描数据库以提高算法的效率，在读取的同时记录下所有的频繁项集。将记录下的频繁项集构建成为一个频繁模式树，即FP-tree。该算法的第二步为扫描数据库挖掘频繁项集，然后再将其压缩到频繁模式树中，然后将FP-Tree分成一组条件FP-Tree，其中每一个数据库关联一个“模式段”也就是频繁项，每个条件数据库再被挖掘。因此FP-Growth算法中两个关键步骤为：首先是构造FP-tree；然后是挖掘频繁模式。FP-Growth算法的核心是构建FP-Tree过程，其中关联信息会始终保留在这棵树中，其次把频繁模式树分解为每一个长度为1的频集相关数据库，然后在不产生不必要候选项集的基础上通过连接以提高算法的性能。(1)FP-Tree的构造构造压缩结构的FP-Tree的基本思想如下：○1如果两个事务有公共的前缀，则可以用一个公共的前缀结构合并共同的部分，并记下发生的次数；○2在挖掘频繁项集之前的条件是首先挖掘出频繁1-项集；○3如果事务的频繁项集可以保存到一个压缩的结构中，那么就不用重复扫描事务数据库；○4如果频繁项出现在多个事务，则将其合并，并记录下发生的次数。根据以上所述的思想，可以使如下方法来构建FP-Tree：首先对事务库D进行扫描，获取其中频繁项集，及其支持度。按支持度大小降序排序频繁项集中的频繁项。然后创建一个标记为“NULL”根结点，并且用它来作为频繁模式树根结点。然后对数据库进行首次扫描，把频繁1-项集的投影事务加入到FP-Tree结构中。在加入时，假若存在相同的前缀，则在相同部分只增加节点的计数，而在不同的部分则增加新的分枝若不存在，则在根节点中增加一个新的分枝[20]。采用这种结构后，频繁项集的挖掘，就转化成递归的找出挖掘FP-树的问题。(2)FP-Tree的挖掘-11-万方数据 基于灰色系统理论的动态关联规则挖掘研究FP-Growth算法描述如下：假设D为事务数据库，C为候选项集，L为频繁项集，min_sup为设定的最小支持度，则有：输入：最小支持度min_support，事务数据库D；输出：频繁模式的完全集。算法：用FP-Tree，挖掘频繁模式。扫描数据库得到频繁1-项集及其支持度，按降序排列得到频繁项表L。创建根节点，并将其设置为“Null”。第一个元素则是p，则剩余元素的表格是P，紧接着插入树中，即调用方法Tree_Insert([p|P],T)，这个方法的是用来判断是否子树上存在子节点满足条件N.ItemName=p.ItemName，并链接到相同ItemName的节点上。反之将计数N加1，若P非空，则可以递归地调用Tree_Insert(P,N)函数。FP-Tree的挖掘算法描述如下:FP_Growth_Gen(Tree,a)//产生树的函数if(Tree存在单个的路径P)thenfor(对于每个路径的每个组合b){产生模式ba；}elsefor对于每个pi在频繁模式树Tree的头部{则其支持度support=a.Support；}if(Treeb)then使用第二步的FP_Growth_Gen(Treeb,b)函数；对FP-Growth的算法性能分析可知它是高效和可伸缩的，而且它的执行速度比Apriori算法高一个数量级，而且在实际的运用和试验之中发现，FP-Growth算法比Apriori算法更加有效，同时有很高的适应性。但是在长期的运用当中也发现了FP-Growth算法存在如下的缺陷：①假若挖掘的项集是属于很稀疏的短模式，算法的效率很受到很大的影响，挖掘的效果不是很理想。②因为FP-Growth算法过程中需要建立树，而树需要占用很大的内存，而同时我们很难确定FP-Growth算法到底需要的内存空间的大小。因此当数据库比较大时，可能会影响系统的性能，造成系统崩溃。在针对Apriori算法存在问题的基础上，FP-Growth算法应用了一种新的存储结构表示事务数据，无论从算法思想上还是实际的应用中都达到了很好的效果。研究人员提出了一些相关改进算法[24-26]。-12-万方数据 兰州交通大学硕士学位论文2.5动态关联规则为了得到更加合理有效的决策信息，研究工作者提出了动态关联规则的挖掘。基于此，国内外很多研究人员和学者提出了用不同的理论和方法运用到关联规则挖掘中，试图弥补原关联规则没有考虑时间因素的缺点，同时也提出了很多考虑时间因素的关联规则挖掘算法[27-32]。传统的关联规则挖掘算法认为所发现的关联规则是静态和永恒有效的。实际上，规则并不一定是永恒有效的。例如：以某超市一年的销售数据库作为分析对象，有可能发现“顾客在购买香烟的同时也会购买礼品”这条规则，但通过分析数据库可知支持这条规则的数据集大多集中在春节、圣诞节和国庆节前后，而在其它时间段规则支持度很小，并不具有全局指导作用。因此，利用基于静态宏观思想所挖掘出的规则进行决策存在一定的弊端。目前的关联规则挖掘算法挖掘出的关联规则是将所有的历史数据作为一个整体而且认为他的分布式均匀的，所谓挖掘出的强规则是对整体而言都是强规则，认为规则具有普遍性。前提假设是：各项的分布是均匀的[33]。因此在某些数据库中挖掘出来的关联规则在时间因素上是变化的，因此挖掘出来的的支持度向量和置信度向量可以用一个类似与数组的方式直接的反映规则随时间的变化趋势。动态关联规则这一理论则可以很大程度上的解决这个问题，因为它根据不同时间段划将原时间分出不同的子集，而把每个时间段的数据作为一个整体，进行单独的挖掘。得到规则在每个相同的时间段的支持度和置信度，并将其按照时间的前后逻辑顺序分别定义成一个向量，从而描述规则所具有的动态性质，为关联规则元规则挖掘奠定了基础。近年来许多基于时间特性的关联规则挖掘算法被提出[34-39]，和大多数其它的理论一样，动态关联规则也经历提出和在对此不断深入研究的基础上进行补充和完善。动态关联规则原始定义和后来对其补充如下。2.5.1动态关联规则的原定义若C是项的集合，设时间段额总长度为t，事先把数据库的时间划分为长度相同但2相邻二个时间上是相互没有交集的，即相邻二个时间段没重叠，即有t{,,tt,}t。12n根据t的划分，整个数据集D可以被分n个数据子集，其中数据子集Di1,2,,n的i数据是在ti1,2,,n时间段内收集的项集T满足TI。对动态关联规则基本概念可以用如下几个定义来描述，如下所示：-13-万方数据 基于灰色系统理论的动态关联规则挖掘研究定义2.4动态关联规则是形如AB的蕴涵式，其中A和B为项集，AI，BI并且AB。定义2.5事务集D中的规则AB，具有支持度s，s是AB(即A和B二者)占总数据库D的百分比，它是概率PA(B)，即每个子数据集Di({1,2,,})n中包含Di的AB在总数据集D中占的百分比之和，s计算公式如下：ns[PAD(B)]i(2.4)i1其中PA(B)表示数据子集D中包含的项集AB的事务数目在数据集D总的Dii事务数目中所占比例。定义2.6事务集D中的规则AB，具有置信度c，它是D中包含A的事务同时也包含B的百分比，即每个子数据集Di({1,2,,})n中包含AB相对于D中包含Ai的事务的百分比之和，c计算公式如下：ncPBAD(i|)(2.5)i1其中PBA(|)表示数据子集D中项集B的事务数与整个数据集D中所包含项集ADii的事务数之比。定义2.7项集AB的支持度向量定义为：SV[,ss,,]s(2.6)12n其中s的值是AB项集在子数据集D中出现的频数与数据集D的总事务数M的ii比值。s对应于关联规则定义中所提到的概率PA(B)，这是一个0%~100%之间的百分iDi数，因此有：fis,i{1,2,,}n(2.7)iM项集AB的支持度，记做s，则有：nssi(2.8)i1设最小支持度为min_sup，则当smin_sup时，项集AB就是动态频繁项集。上面所给的公式是用支持度的值表示示支持度向量的各元素，但在某些情况下，利用项集频数表示支持度向量会更加合适。一个支持度向量表示为：SV[,ff,f](2.9)12n-14-万方数据 兰州交通大学硕士学位论文相应的支持度可以表示为：nsfi(2.10)i1同样当smin_sup时，项集AB就是动态频繁项集。定义2.8动态关联规则AB的置信度向量定义为：CV[,,cc,c](2.11)12nAB的置信度向量CV可以利用项集A、B和AB的支持度向量计算得出。设项集A的支持度向量为SV[s,s,,s]，项集B的支持度向量为AA1A2AnSV[s,s,,s]，项集AB的支持度向量为SV[s,s,,s]。则BB1B2BnAB(AB)1(AB)2(ABn)c，i{1,2,,}n的计算过程如下：iss(ABi)(ABi)cins(2.12)sAAii1其中s是项集A的支持度。A动态关联规则AB的置信度，记做c，则有：ns(ABi)nci1sABcnsi(2.13)AsAii1i1其中s表示项集AB的支持度，s、s分别表示项集A和项集B的支持度。ABAB设最小支持度为min_sup，最小置信度为min_conf，则同时满足smin_sup，cmin_conf的规则称为强动态关联规则。2.5.2原定义的补充和改进原定义这种计算方法并没有反映出项集AB在各个子数据集中的支持度度量，仅能提供AB在子数据集的频数相对于总数据集的比例。从信息理论的角度分析，SV和CV提供的信息是一致的，因此CV的信息是冗余的。针对动态关联规则存在上述问题，对SV、CV进行了重新定义，描述如下：定义2.9支持度向量(SV)：动态关联规则AB(或者项集AB)支持度向量的表示形式如下：SV[s,s,,s](AB)1(AB)2(AB)nsfDi({1,2,n})(2.14)(AB)i(AB)ii-15-万方数据 基于灰色系统理论的动态关联规则挖掘研究f表示项集AB在数据子集Di({1,2,,})n中出现的频数，D为D中的事务(AB)iiii数。设项集AB的支持度为s则有：nss(AB)f(AB)Mf(AB)iM(2.15)i1其中，M是D中的事务数。定义2.10动态关联规则AB频数向量有如下表示形式：FV[f,f,,f](2.16)(AB)1(AB)2(AB)n其中，f为项集AB在数据子集Di({1,2,,})n中出现的频数。(AB)ii定义2.11置信度向量(CV)：动态关联规则AB的置信度向量的表示形式如下：CV[c,c,,c](AB)1(AB)2(AB)ncss(2.17)(AB)i(AB)iAi其中s为项集AB在D中的支持度，s为项集A的在D中的支持度。(AB)iiAii上述定义中，c反映了项集AB在D中的置信度度量。则AB的置信度c(AB)ii可以通过下式计算得到：css(2.18)(AB)A定义2.12一条完整的动态关联规则就可以表述为：具有支持度向量SV，置信度向量CV，支持度s，置信度c四个参数的关联规则。其表示形式如下所示：ABSVCVsc(,,,)(2.19)其中scSVCV,,,可分别由(2.14)、(2.15)、(2.17)、(2.18)式计算，并利用这四个度量指标来描述关联规则的动态性质。根据以上定义得到的支持度向量SV和置信度向量CV的各个元素值与经典的支持度、置信度定义相吻合，在描述动态关联规则相关信息上可用性更强。2.6元规则定义关联规则可以提供一些潜在的有价值的信息，为了描述规则有效性随时间的变化过程，研究人员提出了动态关联规则的挖掘，但动态关联规则仍存在如何设定支持度的问题，而元规则通过对趋势的分析，可以预测未来时间段规则支持度和置信度的值。对动态关联规则进行进一步的元规则挖掘，可以更加有效的挖掘数据集中的关联模式。简而言之，元规则就是规则的规则，即：关联规则的变化。那么元规则的挖掘，也即对关联规则的规则变化的挖掘。元规则是对数据间依赖关系的关联规则的形式的模-16-万方数据 兰州交通大学硕士学位论文式，它使得用户可以说明他们感兴趣的规则的语法形式，规则的形式可以做为约束，指导知识的发现，帮助提高挖掘过程的性能。元规则可以根据分析者的经验、期望或对数据的直觉或者数据库模式自动生成。元规则是形如AAABBB的规则模式，其中A(i1,,2l)和12l12riB(j1,,2r)是示例谓词或是谓词变量。j定义2.13在事务数据集DD,D,,D,(i1,2,,n)上，规则AB的支持度12n向量定义为：SV[s,s,,s]，SABmin_sup。动态关联规则在数(AB)1(AB)2(AB)ni据集D上的支持度元规则为ABSV:。2.7趋势度定义在2.5节中我们详细的介绍了动态关联规则的基本定义，其中最重要的就是以划分时间段为基础。而趋势度这一定义就是在此基础上提出了，是基于“置信度向量”和“支持度向量”的一种深层次剖析。提出趋势度这一概念的重要性在于增加了动态关联规则评价的标准，进一步完善评价体系。同时也能为决策者提供更多更全面的有依据的信息。动态关联规则趋势度的定义如下[15]：定义2.14若规则AB的支持度和置信度小于支持度和置信度的阈值，但是AB规则的支持度向量SV中每个数字都小于它后面的值，也就是说SV是由一个单调递增的数组组成的，我们称AB规则是具有上升支持度特性的支持度上升型动态关联规则。反之称它为下降型规则。定义2.15若规则AB是前面提到的强动态关联规则，即SV中所有的数值都大于提前设定支持度阈值，我们称这种规则为稳定型动态关联规则。定义2.16若规则AB规则中的支持度计数序列没有单调性且不满足稳定型定义，但是计数的变化具有一定的周期性，即：变化有一定的规律可遵循，那么我们陈这种规则为周期型动态关联规则。定义2.17若规则AB的支持度向量不满足以上三个定义，就需要借助最大上升和下降子时间支持度序列，其定义为：因为支持度向量是按照时间顺序排列的，找到其中最大的单调的数列，此时需要注意的是必须按照原始序列中数据的顺序。这个最大上升子序列的长度为此规则的最大上升子时间序列长度。同理，可以找到最大下降子时间序列。定义2.18若规则满足具有单调性和稳定性，那么它的趋势度SRI为1。若规则不满-17-万方数据 基于灰色系统理论的动态关联规则挖掘研究足前两个定义，那么在找到它的最大上升和下降子时间序列的基础上根据：SRIMaxLSn{,}对它们的趋势度进行计算。定义2.19若其大于等于用户给定趋势度阈值(趋势度阈值也需要人为进行提前设定)，则为强动态关联规则。趋势度的值介于0到1之间，代表着该规则的强弱程度。趋势度的优势在于可以给决策者提供很好的依据，是决策者对规则的变化有更直观的了解。2.8本章小结本章分别介绍了：关联规则基本概念、存在的问题、具体分类和经典的两种算法；之后同时介绍了元规则和趋势度的定义，从而将它们作为独立的动态关联规则评价标准，从不同方面对规则进行评价。-18-万方数据 兰州交通大学硕士学位论文3灰色系统理论3.1灰色系统概念与原理1982年，我国学者邓聚龙教授创立了灰色系统理论，经过20多年的发展，灰色系统理论已建立起其学科体系结构，主要内容包括以灰色代数系统、灰色方程、灰色矩阵等为基础的理论体系，以灰色序列生成为基础的方法体系，以灰色关联空间为依托的分析体系，以灰色模型为核心的模型体系，以系统分析、评估、建模、预测、决策、控制、优化为主体的技术体系。系统科学理论这些学科都具有一个共同点，即：具有横向性和交叉性。在灰色系统被提出之后，灰色预测就被应用在实际生活和生产中的各个方面，例如：气象预报、地震预报、病虫害预报以及其它学科的科学研究等方面[40-43]。灰色系统理论主要研究贫信息的、原始数据量比较少的不确定性问题，其研究对象通常为外延明确，内涵不明确的对象[16]。现有的三种数学建模理论主要有：灰色系统理论、概率统计以及模糊数学。以上的三种方法的主要不同归纳如下表：表3.1三种不确定性方法的比较方向概率统计模糊数学灰色系统主要特色大样本凭经验小样本基础集合康托集模糊集灰色朦胧集方法依据映射映射信息覆盖方法侧重内涵外延内涵原理1差异信息原理：“差异”是信息，凡信息必有差异，即：两个事物不是相等的，那么他们至少在一个方面存在着不同，也就是说任何事物包括信息都有其特殊性。正是这种差异性使我们认识世界的基础。原理2在条件足够多的时候我们只能得到一个正确的解，而在条件不足的不完备信息系统的时候，我们得到的解是非唯一的。原理3灰色系统理论可以在贫瘠信息的情况下取得一个较理想的结果，这正是灰色系统与其他方法最大一个区别。原理4认知根据原理：准确认知所有事物的根据是信息。即：得到的信息必须是在已知信息的基础上得来的，并不是凭空得到。-19-万方数据 基于灰色系统理论的动态关联规则挖掘研究原理5运用灰色系统理论主要的目的就是要得到新的信息，因此人为得到的新信息的价值大于历史信息。原理6任何实物的信息都不是绝对的可知，任何的事务总有未知的部分信息。以上的六个原理不仅仅是灰色系统的六个基本原理，同时也是灰色系统的基础和优点，正是由于存在以上的优点。灰色系统理论在一经提出之后就被应用在社会生产生活的各个方面。灰色系统理论与概率统计、模糊数学、马尔科夫相比更适用于解决贫信息、小样本不确定性的问题。动态关联规则支持度向量和置信度向量序列一般是按照周、月、年等大时间粒度划分数据库后得到的，序列样本数并不是很多，符合灰色系统建模的特点。3.2灰色系统模型3.2.1灰色系统建模思想研究一个系统，一般首先应该建立系统的数学模型。灰色模型的构建分为五步，主要的建模过程可分为：思想开发、因素分析、量化、动态化以及优化五个步骤[44,45]。3.2.2GM1,1模型GM1,1模型是灰色系统中应用最为广泛同时也是最重要的一个模型，由于其有很大的使用范围，同时具有其他方法所不具备的三个数据建模的优势，因而有着巨大的进步意义。GM1,1模型的建模过程如下：01111(1)假设时间序列X有n个观察值，Xx1,x2,,xn，为了使其成为有规律的时间序列数据,需要对其作一次累加运算,令t10xtxn(3.1)n111111得到的新的生成数列为X，即Xx1,x2,,xn。(1)(1)(1)(1)(2)x(x(1),x(2),,x())n满足单变量常微分方程：(1)dx(1)axb(3.2)dt其中a为发展系数，b为灰色作用变量。此方程的解为：(1)(0)bakbxˆ(k1)x(1)e(3.3)aa-20-万方数据 兰州交通大学硕士学位论文系数a和b运用灰色系统生成理论按最小二乘法可求解：aˆ1TTBBBY(3.4)bˆ其中：(0)x(2)(0)x(3)Y(3.5)(0)x()n1(1)(1)x(2)x(1)121x(1)(3)x(1)(2)1B2(3.6)1(1)(1)x()nx(n1)12(3)把估计值aˆ，bˆ代入式(3.3)中得到时间影响方程：(1)(0)bˆakˆbˆxˆ(k1)x(1)e(3.7)aˆaˆ(1)(0)(4)对序列xˆ(k1)做还原处理可得原始列x的灰色预测模型：bˆ(0)aˆ(0)akˆ(1)xˆk(1e)(x(1))e(3.8)aˆ当k1,2,,n时，由式(3.8)得到的是拟合值，而当kn1时，得到的是预测值。发展系数a反映了序列的而发展趋势，a为正时序列有增大的趋势，反之则有减小的趋势，而灰作用量b反映了数据之间的变化关系。以上简单介绍了GM1,1模型的一般建模过程，于此同时需要注意的是：在运用GM1,1模型建模时需要注意的是GM1,1模型虽然有着很好的适应性，但不是所有的数据都可以用GM1,1模型来进行建模[46]。可以运用GM1,1模型建模的数据序列应满足以下的条件：(0)xk(1)使用灰色建模序列x的级比()k必须落在可行域中。xk()可行域为：-21-万方数据 基于灰色系统理论的动态关联规则挖掘研究22()ken1,en1(3.9)(0)其中n为序列x的长度。对于不满足以上要求的数据，要使其满足GM1,1模型建模的要求必须对其进行数据的预处理。其中数据预处理的方法主要包括：对数处理(变换)、方根处理、平移处理(变换)三种方法。同时在条件一定的情况下，运用发展GM1,1不一定会取得很好的效果。系数a是[47]，其关系如下表GM1,1模型适用性范围的标准，模型适用范围与发展系数a相关所示:表3.2灰色模型适用范围表a预测模型适用的范围a<0.3可用于中短期预测0.3<a<0.5可用于短期预测0.5<a<0.8可用于短期预测a>1不宜采用3.2.3GM1,1模型的检验前两个检验方法已经在前面介绍完毕，下面主要介绍事后的可信度检验。GM1,1模型中运用的检验方法是残差检验，只有通过检验的模型才能适用于预测。(0)假设模拟值的残差为e()t，则(0)(0)(0)e()tx()txˆ()t(3.10)差百分比为:(0)(0)x()txˆ()t()t%(3.11)(0)x()t3.3灰色组合模型在现实中，数据量很难满足建模要求；不存一个完美的模型能够在任何情况下都有很好的精度，任何一种模型只着重研究一个或者若干个方面，也就是说每个模型的侧重点不同。下面将主要介绍其中最为经典的两种模型。-22-万方数据 兰州交通大学硕士学位论文3.3.1灰色-周期外延模型对于那些同时具有总体趋势和周期性或季节性的变化的数据，单纯使用GM1,1模型只能反映数据总体的变化，而将周期外延模型与GM1,1模型进行有机的结合能有效解决这一问题，同时此模型有着良好的性能被广泛应用在各个领域[48-51]。首先建立序列GM1,1模型，在得到拟合值之后进而得到残差序列，然后以得到的残差序列为对象进行周期外延模型建模，将这一部分作为对第一步建模的补充，最后将两者结合起来形成最终的结果。基本建模步骤如下：设原始数据序列为(0)(0)(1)(0)X[x(1),x(2),,x()]k。(1)运用GM1,1模型相关知识，建立GM1,1模型：ak(1)xkˆ()((1)xbae)ba(3.12)(2)得到拟合值之后，进而求出残差数列xk'()：(0)xk'()x()kxkˆ()(3.13)(3)建立周期外延模型。1)序列xk'()的均值生成函数，计算方法如下：nm1xim()(xijm'())nmi1,2,,,1mmM(3.14)j0其中n为数据序列长度；n为小于nm向上取整；M为小于n2向上取整。可得均值生m成函数矩阵如下式：x1(1)x2(1)x3(1)xM(1)x(2)x(2)x(2)23Mx(3)x(3)(3.15)3Mx(M)M周期性延拓，即：fk()xk(),ki[mod()],mk1,2,n(3.16)mm2)提取优势周期。提取周期的方法目前主要有两种，本文取第二种方法，因第二种方法较简单。○1用下式确定周期：()m()mF(nmS)((m1))S(3.17)服从自由度(m1,nm)的F分布。-23-万方数据 基于灰色系统理论的动态关联规则挖掘研究其中，m()m2Snxii(m()x)i1nninix,(xi())ni1mn2S((xi(j1))mxim())(3.18)i1jn○2确定周期取Smm()max()Smm,2mM(3.19)3)序列xk'()减去周期m所对应的延拓函数构成一新序列，提取其优势周期。4)将不同周期同一时刻的值叠加为fk()，mfk()fki()(3.20)i1称此模型为周期外延模型，xk'()可近似地取为fk()。(0)(4)序列x()k的拟合可用xkˆ()与fk()的组合表示：xk()xkˆ()fk()(3.21)3.3.2灰色马尔可夫模型马尔可夫链理论可以简单的认为是状态转移矩阵，而状态转移矩阵可以很大程度上的描述系统的随即变化过程。就是根据历史数据，人为的设置一些状态，再有这些状态之间的变化关系得出一些规律，即：当系统处于某种状态时下一个或者若干时段系统处于哪种状态的概率最大。进而用这种状态对原系统进行修正，此模型和上面提到的灰色-周期外延模型最大的相同点是：充分考虑了系统的变化，而与其不同是在于马尔可夫模型重在考虑不同状态的之间的关系，而周期外延模型重在考虑这种变化与时间的关系。建模思想：1)首先对数据建立GM1,1模型。2)得到拟合值之后，进而求出残差。3)根据残差的不同，人为的区划分不同的状态。4)得到状态转移矩阵。5)由系统目前所处的状态，得到系统在下个或者若干个时间段所处的具体状态。6)根据状态对结果进行修正。-24-万方数据 兰州交通大学硕士学位论文由于本模型具有的优势，已被广泛应用。对于在建模过程中所用到的马尔可夫链理论的相关知识以及概率统计等相关知，本文不在做详细介绍[52-55]。3.4本章小结本章主要介绍了灰色系统理论的相关知识，着重阐述了GM1,1模型的建模过程。之后介绍了本文所用的两种基于灰色系统理论的组合模型。-25-万方数据 基于灰色系统理论的动态关联规则挖掘研究4基于灰色模型的动态关联规则元规则以及趋势度挖掘4.1基于灰色-周期外延模型的动态关联规则元规则挖掘对有周期性或季节性的动态关联规则支持度向量序列，可以应用灰色-周期外延组合模型进行元规则挖掘。灰色GM1,1模型能够很好地反映序列的总体趋势，所以可以首先建立序列GM1,1模型，然后对残差序列建立周期外延模型，作为灰色GM1,1模型的残差补偿，通过将二者有机地结合可以适用于既有总体变化趋势又有周期波动的数据序列的预测。4.1.1算法描述由于现有关联规则的挖掘算法大多是基于静态数据库的。同时在挖掘中认为所有的项目和事物都是同等重要的，其次在对挖掘所得到的规则进行分析发现大多规则在时间上的分布不均匀。鉴于关联规则的挖掘中存在严重的不足，所述静态关联规则已经不在适应当代各方面发展的需求。动态关联规则挖掘与之前的静态关联规则挖掘的本质区别在于挖掘过程中充分考虑到时间因素的重要性，通过对时间段进行划分，针对每个子时间段内的数据通过设置最小支持度和最小置信度的方法进行挖掘，可以得到连续且分布均匀的动态关联规则。因此动态关联规则挖掘在一定程度上克服静态关联规则挖掘的不足，其参考价值和指导意义相对静态关联规则挖掘有了显著地提高。但是动态关联规则依然有不足之处：不同的时间段划分方法可能会得到不同的结果；在挖掘过程中所有项目和事物不可能具有相同的重要性，因此挖掘结果的参考价值也会不同。在本文第一部分提到的几种挖掘方法虽然可以针对具有不同特点的动态关联规则元规则进行挖掘，但还是存在这一定的局限性，没有充分考虑在实际挖掘中所存在的周期性。例如针对某商场或者超市的销售数据进行数据挖掘之后，我们可能会发现部分关联规则具有很强的周期性或者季节性。这时如果我们还用以上提出的几种方法来进行元规则挖掘，那么预测的精度会大大的下降，从而使得到的可靠性不高的结果。综上所述，本文提出了一种基于灰色-周期外延模型的动态关联规则元规则挖掘方法，将GM1,1模型和周期外模型相结合，组成灰色-周期外延模型。4.1.2建模过程该方法既能很好地反映序列的总体趋势，也能在很大程度的反映出周期变化这一特点，具体过程如下：-26-万方数据 兰州交通大学硕士学位论文(1)设SVf,f,,f为经过挖掘所得到的支持度向量，将SV中各数据组成的支12n持度计数序列{,ff,,f}作为原始序列xk()进行级比()k验证，并且对其建立12nGM1,1模型。(2)运用GM1,1模型建模方法得到序列{,ff,,f}的预测公式。12n(3)得到序列的拟合值xkˆ()，由拟合值和真实值进一步残差序列xk()。(4)运用周期外延模型的相关知识，将xk()进行周期外延建模。(5)确定xk()的优势周期。(6)将序列xk()中不同周期中同一时刻的值相加：mfk()fk()(4.1)ii1(7)将xkˆ()与fk()之和作为原始序列xk()的最终拟合值：xk()=()+()xkˆfk(4.2)进一步得到最终的预测值。由于本文着重于描述元规则的挖掘，以及相关的数据建模是重点阐述的，因此对于关联规则和动态关联规则规则挖掘过程不再详细说明。4.1.3实验分析实例分析部分所采用的数据来源于文献[16]，运用挖掘方法得到支持度计数SV,SV[278,256,273,273,255,269,268,254,264,261,248,258,257,243,255]。用2010年全年12个月的数据(SV中前12个数据)建立模型，并用此模型预测2011年第一季度支持度计数的预测值。在此基础上，将预测结果和2011年第一季度的实际结果进行对比。具体步骤如下：1)将SV中前12个数据作为原始序列，(0)(0)(0)(0){x(x(1),x(2),,x()),nn1,2,12}(4.3)建立GM1,1模型。首先，进行GM1,1模型级比验证后，确定本数据无需进行数据预处理，可以直接建立GM1,1模型。2)得到原始序列GM1,1模型的发展系数a和灰色作用变量b的值。其中a0.004242，b269.061410(注：为简化只取小数点后6位，而在具体建模时以计算出的实际值进行运算)。由发展系数的值可以确定，可用GM1,1模型对数据进行中短期预测，从而得到时间影响公式：-27-万方数据 基于灰色系统理论的动态关联规则挖掘研究0.004242k1xkˆ()268.451027e(4.4)3)根据第二步得到的时间影响公式，进而得出原始序列的拟合值、残差以及残差百分比，如表4.1所示：表4.1预测模型拟合值分析表月份真实值拟合值残差百分比1278268.4510279.5489723.434882%2256267.314504-11.314504-4.419728%3273266.1827936.8172062.497145%4273265.0558737.9441262.909936%5255263.933724-8.933724-3.503421%6269262.8163266.1836732.298763%7268261.7036596.2963402.349380%8254260.595702-6.595702-2.596733%9264259.4924364.5075631.707410%10261258.3938412.6061580.998528%11248257.299896-9.299896-3.749958%12258256.2105841.7894150.693572%由上表可以看出：GM1,1能反映出序列总体变化趋势，即有逐步降低之势；同时负误周期出现，说明GM1,1模型没有反应出序列周期波动的规律。4)计算残差序列xk()的均值得到均值生成函数矩阵：x1(1)x2(1)x3(1)x6(1)x(2)x(2)x(2)236x(3)x(3)=36x(6)60.79581.48946.59881.70763.21637.92260.10219.03590.84151.61438.95514.82441.27120.11075.66231.04596.22585.27513.16379.11683.9865-28-万方数据 兰州交通大学硕士学位论文5)提取残差序列xk()的周期。本文采用Smm()max()Smm(4.5)的方法确定周期，可以得到S(3)3max()Smm。据此残差序列xk()的周期为3。6)周期外延预测模型为fk()fk()(4.6)3均值生成函数x()16.5988，x(2)9.0359，x()34.8244。3337)叠加生成灰色-周期外延组合模型：0.004242k1xk()=()xkˆ+f(k)268.451027ef()k(4.7)3拟合结果见表4.2：表4.2组合模型拟合值分析表月份真实值拟合值残差百分比1278275.0499262.9500731.061177%2256258.278547-2.278547-0.890057%3273271.0072581.9927410.729942%4273271.6547731.3452260.492757%5255254.8977670.1022320.040091%6269267.6407911.3592080.505281%7268268.302559-0.302559-0.112895%8254251.5597452.4402540.960730%9264264.316901-0.316901-0.120038%10261264.992740-3.992740-1.529785%11248248.263939-0.263939-0.106427%12258261.035048-3.035048-1.176375%由上表可知，用此方法进行建模后，取得了很好的效果：残差都在可信范围内，且误差百分比十分小，因此本方法是完全可信的，可用本方法进行预测。2011年首个季度的支持度计数的预测值如下表，可知本方法在数据预测上有着很好的精度，同时本模型充分反映了原始数据和预测数据的周边变化的特性。引用本方法进行动态关联规则元规则挖掘是有效且可靠的。-29-万方数据 基于灰色系统理论的动态关联规则挖掘研究表4.3预测值分析表月份122真实值257243255预测值261.724782245.009816257.794702残差-4.724782-2.009816-2.794702百分比-1.83843%-0.0827%-1.0959%4.1.4方法对比将GM1,1模型应用在上一节所提到的销售数据中，两种模型的拟合精度分析图如图4.1所示。由图4.1可知GM1,1模型预测的误差百分比绝对值之和是灰色-周期外延模型预测的误差百分比绝对值之和近两倍，这主要是因为单纯的使用GM1,1模型时结果只具有下降的趋势，而本文所使用的方法考虑了数据周期波动性，而且GM1,1模型只能表现出变化的总体趋势。图4.1拟合值分析图同时，灰色-周期外延模型的误差和GM1,1模型的误差都是在可接受范围值，我们分别用两种模型来对2011年第一季度的数据做预测，之后用实际数据验证预测精度。具体结果如表4.4所示：-30-万方数据 兰州交通大学硕士学位论文表4.4两种模型预测分析表月份123真实值257243255预测值255.125882254.045774252.970237GM(1,1)模型误差1.874117-11.0457742.029762百分比0.07292%-4.5455%0.07959%预测值261.724782245.009816257.794702灰色-周期外误差-4.724782-2.009816-2.794702延百分比-1.83843%-0.0827%-1.0959%下面把本文所提出的方法和文献[12]中提出的基于AR-Markov模型的挖掘方法进行横向对比，进一步研究本方法适用的范围和建模特点。为了充分验证本方法的优势，下面将使用本文的方法对文献[12]中的实例数据进行建模分析，从而和基于AR-Markov模型的动态关联规则元规则挖掘方法做详细对比。对序列162,175,,171,164运用本文所提出的方法。具体过程和结果如下：○1首先我们得到GM1,1模型的预测公式：0.001050k1xkˆ()164.474853e(4.8)○2由发展系数的值可知，可用GM1,1模型进行中短期预测。得到拟合值之后，通过对残差序列建立周期外延拓扑模型，运用本文在之前提到的周期确定的方法，可得残差序列的最优周期为12。○3进一步可以得到最终的预测公式：0.001050k1xkˆ()164.474853e(4.9)拟合值、残差以及残差百分比的具体结果如表4.5所示，由表4.5可知，数据的拟合效果较理想，残差和残差百分比都在很小的范围变动，有着较高的可靠性。同时证明了本方法有着很好的适应性，可以在许多情况下运用灰色周期外延模型进行建模。两种方法的具体对比结果如下图4.2所示。通过表4.5和图4.2我们发现在拟合过程中，采用本文所提出方法的拟合精度要高于文献[12]中所使用挖掘方法的精度，且使用AR模型时会出现个别误差较大的情况。而使用灰色-周期外延模型时没有出现误差过大的情况，而且误差分布的比较平稳。再次验证了本方法具有较好的有效性和较高的预测精度。-31-万方数据 基于灰色系统理论的动态关联规则挖掘研究表4.5拟合值分析表月份真实值拟合值残差百分比1171167.54313.45682.0215%2183180.04422.95571.6151%3163163.5453-0.5453-0.3345%4152155.0464-3.0464-2.0042%5165170.5475-5.5475-3.3621%6175167.04867.95134.5436%7167161.54975.45023.2636%8170174.5508-4.5508-2.6769%9170165.55194.44802.6164%10167170.0530-3.0530-1.8281%11171169.55411.44580.8455%12164164.0552-0.0552-0.0337%图4.2拟合值分析图4.2基于灰色Markov模型的动态关联规则趋势度挖掘4.2.1算法描述通过对GM1,1模型研究发现，GM1,1模型只能得到原始数据的整体变化趋势，对于数据的波动性变化则没有显现，因此利用Markov链的相关理论对其进行补充是十-32-万方数据 兰州交通大学硕士学位论文分必要的。Markov链理论是基于概率统计的理论，适用于具有随机变化的动态过程，通过状态转移矩阵我们可以得到系统在下一个时刻所处状态的概率，因此将两者结合起来可以得到更加准确的预测结果。4.2.2建模过程本文所提出的基于灰色-Markov模型的动态关联规则趋势度挖掘方法的重点是对灰色-Markov模型的运用。在描述算法之前将算法中所用到的名词进行解释，FP-Growth算法：文献[56]中率先提出的一种经典的关联规则的挖掘方法；ITS算法：文献[8]中提出的一种动态关联规则的挖掘算法。下面将本文所提出方法的具体过程以及建模的过程进行详细描述。主要过程如下：(1)调用FP-Growth算法挖掘出满足支持度阈值的频繁项集。(2)再次扫描数据库，得到每个频繁项集的支持度计数。(3)根据支持度向量的变化趋势以及支持度向量的分类和计算公式得出各频繁项集的趋势度SRI。(4)判断各频繁项集的趋势度SRI是否大于趋势度阈值DRI。(5)将不满足DRI要求的频繁项集的支持度计数序列用GM1,1模型进行建模。首先需要的是进行GM1,1模型的级比验证，若符合建模要求则直接建模，反之则需要进行数据的预处理，从而得到原始数据的拟合公式。(6)由拟合公式得到原始数据的拟合值，进一步得到残差和残差百分比，同时有确定的GM1,1模型发展系数来确定可以预测的种类。运用Markov链理论，结合实际情况进行状态划分。(7)得到状态转移到其他任何状态的转移概率p，进而得到一步转移概率矩阵p和ijk步转移概率矩阵pk()。(8)可得此支持度向量下一个或k个值的取值状态概率。(9)得到最终的预测的支持度计数。(10)将预测得到的支持度计数加入原频繁项集支持度向量，判断新的支持度序列是否满足支持度阈值要求。(11)判断(10)中满足支持度阈值的支持度序列的趋势度是否大于DRI。(12)将(4)和(11)中满足要求的规则作为强趋势度动态关联规则进行输出。4.2.3实例分析实验数据采用SQLServer2005自带的某商场2004年的销售数据作为实验数据。挖-33-万方数据 基于灰色系统理论的动态关联规则挖掘研究掘出形如{,}II频繁项集，其中I、I为商品的编号。设最小支持度为0.4，最小支持1212度数为40，最小置信度为0.4，趋势度阈值DRI0.55。实例分析过程：第一步：调用FP-Growth算法，由设定的支持度阈值进行挖掘，得到频繁项集：{,}II，{,}II，{,}II，{,}II。12242545第二步：得到各频繁项集支持度向量SV：SV{,}II1241,40,42,41,43,44,40,41、SV{II2,}437,39,40,40,41,42,43,45、SV{II2,}543,39,39,42,40,43,42,40、SV{II4,}543,38,38,42,41,39,42,40。第三步：根据趋势度的定义和趋势度的计算公式，计算各频繁项集的趋势度。{,}II12支持度向量中每个元素的支持度均大于最小支持度阈值，它属于支持度稳定型向量，即：SRI1；{,}II支持度向量属于支持度上升型频繁向量，SRI1；{,}II最大{,}II1224{II2,}425上升子时间序列长度为4，最大下降子时间序列向量长度为4，可得：SRI0.5；{II2,}5{,}II最大上升子时间序列长度和最大下降子时间序列向量长度均为4，可得：45SRI0.5。{II4,}5第四步：根据趋势度阈值{,}II和{,}II为强动态关联规则，{,}II和{,}II为非12242545强动态关联规则。第五步：对非强动态关联规则{,}II和{,}II的支持度向量，运用GM1,1模型进2545行建模。对所得到的规则{,}II以及{,}II的支持度序列43,39,39,42,40,43,42,40和254543,38,38,42,41,39,42,40作为原始序列：(0)(0)(0)(0){x(x(1),x(2),,x()),nn1,2,,8}(4.10)(0)(0)(0)(0){y(y(1),y(2),,y()),nn1,2,,8}(4.11)按以下步骤进行：(1)首先根据公式获得级比序列。经检验级比()k满足：2222n1n1()ke,ee9,e90.8007,1.2488(4.12)(0)(0)(0)(0)(2)直接对原始序列：{x(x(1),x(2),,x()),nn1,2,,8}建立GM1,1模型。分别得到两个参数：a0.008618，b39.127803；a0.009673，b38.245032。1122由发展系数的值可知，可用GM1,1模型对其分别进行中短期预测，根据步骤1可知，分别得到两序列的时间影响方程：-34-万方数据 兰州交通大学硕士学位论文(1)0.008618kxˆ(k1)4583.241703e4540.241703(4.13)(1)0.009673kyˆ(k1)3996.792205e3953.792205(4.14)第六步：利用时间影响方程得到模拟序列，分析规则{,}II和{,}II支持度的模拟2545值、残差和残差百分比，如表4.6所示：表4.6模拟值分析表规则月份真实值GM(1,1)模拟值残差百分比1434300%23939.66-0.66-1.69%33940.01-1.01-2.58%44240.351.653.92%{,}II2554040.70-0.70-1.75%64341.061.944.51%74241.410.591.40%84041.77-1.77-4.42%1434300%23838.84-0.84-2.21%33839.22-1.22-3.21%44239.602.405.71%{,}II4554139.991.012.46%63940.38-1.38-3.53%74240.771.232.92%84041.16-1.16-2.90%(1)通过表4.6可知：序列x的变化趋势是逐步减小的，根据这个灰色预测曲线方程得(1)(1)到的模拟值序列x的平均相对误差为2.54%，而最大误差为4.51%；序列y的变化趋(1)势是逐步增大的，根据这个灰色预测曲线方程得到的模拟值序列y的平均相对误差为2.87%，而最大误差为5.71%。虽然使用GM1,1模型有着很好的效果，误差都在可接受范围之内。但是由于GM1,1模型是一个线性的模型，只能表现出数据的整体变化趋势，对于数据的随机变化拟合值没有充分表现出来，具体变化如下两图所示：从图中可以看出拟合的数据对数据的随机变化表示不足，进而造成了拟合值有一定的误差，为了使预测的数据更加的准确，进行状态划分。-35-万方数据 基于灰色系统理论的动态关联规则挖掘研究图4.3规则{,}II拟合值分析图25图4.4规则{,}II拟合值分析图45根据规则的支持度计数拟合结果和残差百分比划分出五种状态：E，E，E，E1234和E。残差百分比小于-8%设为E；残差百分比大于-8%且小于-2%设为E；残差百分512比大于-2%且小于2%设为E；残差百分比大于2%且小于8%设为E；残差百分比大于34-36-万方数据 兰州交通大学硕士学位论文8%设为E；5第七步：计算状态转移概率，确定状态转移矩阵。由以上的五个状态划分得到规则{,}II，{,}II各状态转移情况，如表4.7所示：2545表4.7状态转移表规则状态E2E3E4合计E00112{,}IIE2013253E02024E10232{,}IIE0000453E20134进一步得到一步状态转移概率矩阵和两步状态转移概率矩阵：0010102112P0，P(2)0333301021c331254003399P000，P(2)0002145003399第八步：定接下来两个月支持度计数的状态。规则{,}II在第8个月处于状态E，252根据一步状态转移矩阵P和两步状态转移矩阵P(2)，可知规则{,}II在接下来两个月支25持度计数分别处于E和E；规则{,}II在第8个月处于状态E，根据一步状态转移矩42452阵P和两步状态转移矩阵P(2)，可知规则{,}II在接下来两个月支持度计数都将处于45状态E。4-37-万方数据 基于灰色系统理论的动态关联规则挖掘研究第九步：分别预测两规则在接下来两个月的值。得到规则{,}II和{,}II接下来两2545个月的支持度计数如表4.8所示：表4.8支持度预测规则月份状态灰色区间中位数取整9E4[42.99,45.80]44{,}II2510E2[39.35,41.66]419E4[42.41,45.18]44{,}II4510E4[42.83.45.62]44第十步：将预测值添加到原规则支持度序列中后，两规则的支持度向量分别为：SV{II2,}543,39,39,42,40,43,42,40,44,41，SV{II4,}543,38,38,42,41,39,42,40,44,44。经检验SV和SV都满足支持度阈值要求。{II2,}5{II4,}5第十一步：计算趋势度。根据公式得：SRI{,}II250.5，SRI{II4,}50.6。第十二步：生成规则。{,}II和{,}II的支持度和置信度都大于阈值，并且趋势度1224为1，是强动态关联规则；{,}II的支持度和置信度都满足阈值要求，但是它的趋势度250.5DRI0.55，并且对支持度序列进行预测之后仍然小于趋势度阈值，因此它不是强动态关联规则；频繁项集{,}II，它的支持度和置信度都满足阈值，且对其支持度序列45进行预测之后满足阈值要求0.6DRI0.55，因此将{,}II作为强动态关联规则输出。45最终我们得到三组共六条高趋势度的动态关联规则：I1I2、I2I1、I2I4、I4I2、I4I5、I5I4。4.2.4方法对比为了说明算法的有效性和可行性，本在上一节用一个实例详细的阐述了本方法的具体过程以及得出的结果。为了说明本方法与之前其他方法的区别和优势，本文用传统动态关联规则挖掘算法ITS算法以及基于趋势度的动态关联规则挖掘算法两种算法作对比，研究三种挖掘算法产生的规则。采用用FP-Growth算法对上文的实例进行挖掘，得到了的频繁项集为：I1I2，I2I1；I2I4，I4I2；I2I5，I5I2；I4I5，I5I4。而在ITS算法中作为强动态关联规则输出的只有I1I2，I2I1；I2I4，I4I2。由于规则I2I5、I5I2、I4I5以及I5I4在静态关联规则中其支持度满-38-万方数据 兰州交通大学硕士学位论文足阈值要求，但是在动态关联规则的挖掘中把时间段进行划分后，存在个别的支持度计数小于阈值，造成这种现象的原因是：由于时间短的划分不合理，在某个时间内数据的量发生了变化。在得到的频繁项集的基础上进行趋势度挖掘，由于其他两组规则目前不满足趋势度阈值的要求，得到的结果是：I1I2，I2I1；I2I4，I4I2。结果如表4.9所示：表4.9三种方法结果对比表频繁项集ITS算法基于趋势度的动态关联规则挖掘算法本文提出的方法I1I2I2I1I1I2I2I4I1I2I1I2I2I1I4I2I2I1I2I1I2I4I2I5I2I4I2I4I4I2I5I2I4I2I4I2I4I5I4I5I5I4I5I4用传统的关联规则挖掘算法得到的频繁项集有四组共八条；用ITS算法挖掘出的强动态关联规则只有两组共四条；进而基于趋势度的动态关联规则挖掘算法也可以得到两组四条高趋势度的动态关联规则；而用本文所提出的方法可以得到三组六条高趋势度的动态关联规则。I2I5、I5I2、I4I5和I5I4由于存在个别的时间段趋势度计数不满足要求而非动态关联规则，进而也不可能属于强趋势度的动态关联规则。但是对两组规则进行建模后发现：规则I2I5和I5I2其支持度计数变化随机性比较大，决策者不能从中得到有效的决策信息，其参考价值并不大，不将其进行输出是完全必要的；而对于规则I4I5和I5I4，对其支持度向量序列建模可知，虽然现有的支持度计数有一定的随机变化性，但是其支持度计数有着随时间变大的趋势，同时在之后的若干个时间段其支持度计数都满足阈值要求，同时其趋势度也满足趋势度的要求，可以从中得到有效的信息，因此将其作为强趋势度动态关联规则进行输出是很有需要的。因为进行数据挖掘的目的就是要得到对今后有价值的信息，而趋势度挖掘则更加注重规则变化的重要性。因此，新的动态关联规则挖掘算法针对动态关联规则中有一定变化趋势的规则进行-39-万方数据 基于灰色系统理论的动态关联规则挖掘研究挖掘，充分考虑到规则随时间而变化的特性，提高了规则挖掘的质量，同时也为决策者提供了更加全面、有效地信息，从而使决策更有依据、更可靠。4.3本章小结提出基于灰色系统理论的灰色周期外延模型的动态关联规则元规则挖掘以及灰色马尔可夫模型的动态关联规则趋势度的挖掘方法。在介绍基本建模思路和建模方法的基础上，将以上两种模型应用在具体的实例和试验之中，并且在分别将两种方法和原有方法进行对比，分析二个方法的有效性和所具有的优势。-40-万方数据 兰州交通大学硕士学位论文结论在数据挖掘中，关联规则是一个研究的热点，而在这其中动态关联规则的研究也是国内研究热点中的重点。于此同时，动态关联规则元规则及其趋势度挖掘也发挥着越来越大的作用。目前关联规则挖掘逐渐发展成熟，被广泛应用到实际生活中，例如银行、超市、电信等各行业中。然而目前的基于关联规则事物挖掘大多是静态的，即没有考虑到关联规则随着时间变化而变化，实际上关联规则在时间上市有着趋势变化的，因此有必要从时间性质上实现对动态关联规则的挖掘。特别是动态关联规则挖掘、元规则挖掘、趋势度挖掘的相关研究进一步拓宽了普通关联规则挖掘研究的方向，这在一定程度上解决了规则有效性随时间变化容易出现波动的问题，更加着重对规则本身的研究。动态关联规则挖掘的目的不仅是为了发现有用的规则，而且还考虑到了如何更加合理地、人性化地表示这些规则信息，这样能更加的对实际应用做出更好的决策。文章第一章节重点在于介绍国内外的研究现状,研究的内容、背景、目的、及意义；第二章在第一章节的基础上引出关联规则的基本概念，然后在此基础上考虑到数据库中存在时间因素，进而引出动态关联规则概念，并对其进行详细的描述，采用四个参数及支持度、置信度、支持度向量、置信度向量可以用来观察规则在时间上的变化，给出其基本的定义；第三章则是灰色系统理论的一些基础理论介绍；第四章介绍二个挖掘方法，本文在GM1,1模型和马尔科夫链理论相结合的基础上，将其组成的组合模型运用到动态关联规则趋势度的挖掘中。在动态关联规则趋势度的挖掘中运用本方法，不仅能直观的了解到规则趋势度的总体的变化情况，还可以对其进行预测。同时通过一个实例说明基于灰色周期外延模型的动态关联规则元规则挖掘方法的一般过程。最后，通过比较得出此模型比直接用灰色模型预测要可靠、合理，总体效果要优于灰色GM1,1模型，能更准确的把握规则的变化趋势从而使动态关联规则挖掘在合理的元规则指导下得到更精确的结果。结果表明本方法能够在一定程度提高规则挖掘的效率，为决策提供了更可靠的信息。今后的主要研究方向将放在：当原始数列波动性过大且无明显规律时如何保证预测的精度；如何将灰色-周期外延模型应用到动态关联规则趋势度的挖掘中；在大数据的时代到来之际，如果对象为大数据库或者海量数据时，在使用灰色系统理论时进行相关的挖掘之中，如何提高挖掘算法的效率和准确性[57-59]。虽然对相关研究领域进行了长时间的研究，同时也取得了一定的成果，然而本文的研究也存在一定缺陷，还可以在某些方面进行相关的研究和改进。进一步深入研究的工-41-万方数据 基于灰色系统理论的动态关联规则挖掘研究作主要有以下几个方面：(1)时间粒度的划分：现有的动态关联规则的时间粒度是等时间段划分的，是静态的，但是时间序列可以依据时间信号的趋势变化进行时间段的动态划分。(2)基于趋势度的动态关联规则算法的改进。本文的算法是传统动态关联规则算法的扩展，对挖掘有趋势的动态关联规则算法性能未做详细的分析，在综合的算法设计上有必要开展深入的研究。(3)进一步提高预测精度。本文提出的方法还有一定的局限性，应尝试把其他的方法和理论运用到动态关联规则的挖掘当中，进一步提高预测的精度。再次，由于灰色系统在少数据时有很高的预测精度，当数据量较大时怎么提高灰色建模的适应性和可行性。-42-万方数据 兰州交通大学硕士学位论文致谢这篇文章是我三年来研究的成果，在这里首先向所有给予我帮助，关心我的导师和老师、领导、同学等表示感谢。感谢我的导师张忠林教授，他一丝不苟的的治学态度、积极开拓的科研精神、灵活开阔的学术思想和渊博的学术理论深深的感染着我，是我一生学习的榜样。在论文思想启蒙阶段，他就像一盏明灯指引我前进，在查询论文和寻求知识的这条艰难坎坷路上，张老师一点一点给我指点。在整个研究的过程中，经常和张老师交流学习心得，不仅丰富了理论知识，而且学习到了许多人生的哲理，三年来，在学习、科研、生活的各个方面，都给予我无私的帮助，让我不仅仅得到学业上的收获，更教会了我许多为人处事的方法。在此，再次向导师致以最深切的感激和最崇高的敬意。另外，我要感谢我的母校-兰州交通大学对我培育，这里有认认真真教导我电子与信息工程学院的老师，正是他们孜孜不倦的教导，才使我能够汲取更多的知识；这里有关心我学业和人生情感的领导，这里有在学业方面的努力激励我不断进取；同时感谢同门的师姐、师兄、师弟、师妹们，为我开拓了眼界，给予我很大的启发。感谢我的家人和朋友，他们给予我前进的勇气和力量。最后，特别感谢评阅本文的各位专家对本文提出的宝贵意见。-43-万方数据 基于灰色系统理论的动态关联规则挖掘研究参考文献[1]史忠植.知识发现.北京:清华大学出版社,2002.[2]JiaweiHan,MichelineKamber著.范明,孟小峰等译.数据挖掘:概念与技术.北京:机械工业出版社,2001.[3]AGRAWALR,IMEIELINKSIT,SWAMIA.MiningAssociationRulesBetweenSetsofItemsinLargeDatabases//Proceedingsofthe1993ACMSIGMODConferenceWashingtonDC:Washington:1993:207-2l6．[4]GANTIV,GEHRKEJ,RAMAKRISHNANR.D.Miningandmonitoringevolvingdata.IEEETransonKnowledgeandDataEngineering,2001,1(1):50-63.[5]周欣,沙朝锋,朱扬勇等.趋势度关联规则的又一个阈值.计算机研究与发展,2000,37(5):627–633.[6]LIUJin-Feng,RONGGang.Miningdynamicassociationrulesindatabases,2005.Xi’anProceedingsofInternationalConferenceonComputationalIntelligencesandSecurity.Xi’an,2005:688-955.[7]荣冈,刘进锋,顾海杰.数据库中动态关联规则的挖掘.控制理论与应用,2007,24(1):129-133.[8]沈斌,姚敏.一种新的动态关联规则及其挖掘算法.控制与决策,2009,24(9):1310-1315.[9]刘俊,谢彦峰,张忠林.基于灰色Markov模型动态关联规则元规则挖掘.计算机应用,2008,28(9):2353-2356.[10]刘俊,张忠林,谢彦峰等.基于时间序列模型的关联规则元规则挖掘.计算机工程,2009,15(35).94-96.[11]张忠林,许凡.基于小波变换的动态关联规则元规则GM(1,1)挖掘.计算机科学,2013,40(5):209-212.[12]张忠林,刘俊,谢彦峰.AR-Markov模型在动态关联规则挖掘中的应用.计算机工程与应用,2010,(14):135-137.[13]张忠林,许凡.基于小波变换的动态关联规则元规则挖掘方法.计算机应用,2012,(7):1983-1986.[14]张忠林,石皓尹,宋航.灰色-周期外延模型的动态关联规则元规则挖掘.计算机科学,2014,04:239-243.[15]张忠林,曾庆飞,许凡.动态关联规则的趋势度挖掘方法.计算机应用,2012,32(1):196-198.[16]刘思峰,党耀国,方志耕等.灰色系统理论及其应用.北京:科学出版社,2004,142-146.[17]朱陵凤,韩春好,李超.灰色模型用于卫星钟差长期预报的性能研究.天文研究与技术,2007,4(9):226-230.[18]杨建明,石建军,赵和仲等.灰色系统理论在矿山安全事故预测中的应用.矿业研究与开发,2004,24(1):56-58.[19]曹奎,冯玉才.基于GM(1,1)模型的压缩域图像表示与检索技术.计算机工程,2004,3O(7):121-123.-44-万方数据 兰州交通大学硕士学位论文[20]贾占强,梁玉英.灰色GM(1,1)模型在雷达寿命试验中的应用.微计算机信息,2007,23(9):244-245.[21]HanJ,PeiJ,YinY,etal.Miningfrequentpatternswithoutcandidategeneration:AFrequent-PatternTreeapproach.In:ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData.2000:54-87.[22]LiuJ,PanY,WangK,etal.Miningfrequentitemsetsbyopportunisticprojection.In:ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData.2002:229-238.[23]PeiJ,HanJ,LuH,etal.H-Mine:Hyper-structureminingoffrequentinlargedatabases.In:ProceedingsoftheInternationalConferenceonDataMining,2001:38-49.[24]陈安龙,唐常杰,陶宏才等.基于极大团和FP-Tree的挖掘关联规则的改进算法.软件学报,2005,15(8):1198-1207.[25]焦明海,姜慧研,唐加福.一种基于聚合链的改进FP-Growth算法.东北大学学报(自然科学版),2006,27(2):153-156.[26]董平,胥杰,苏力萍.一种基于TFP树的频繁项集改进挖掘算法.微计算机信息,2007,33:139-140.[27]YangM.,SunZ.H.,SongY.Q.FastUpdatingofGloballyFrequentItemsets.JournalofSoftware,2004,8:1189-1196.[28]CheungD.W.Maintenanceofdiscoveredassociationrulesinlargedatabases:Anincrementalupdatingtechnique.In:Procofthe12thInt’lConfonDataEngineering.NewOrleans,Louisiana,1996:106-114.[29]厉浩,李珊.一个新的FUP-Based关联规则增量式更新算法.计算机工程与科学,2005,27(7):74-76.[30]王云岚,李增智,屈科文.基于候选项集个数上阶的增量式关联规则更新算法.电子学报,2004,35(4):731-734.[31]FelixC,BenK,DavidC,etal.AnEfficientAlgorithmforIncrementalUpdateofConceptSpaces,AdvancesinKnowledgeDiscoveryandDataMining:6thPacific-AsiaConference,Taipel,Taiwan,2002:368-380.[32]ChristieI.Ezeife,YueS.MiningIncrementalAssociationRuleswithGeneralizedFP-Tree,LectureNotesinComputerScience,AdvancesinArtificialIntelligence:15thConferenceoftheCanadianSocietyforComputationalStudiesofIntelligence,Canada,2002:147-160.[33]欧阳为民,郑诚,蔡庆生.数据库中加权关联规则的发现.软件学报2001,04.[34]朱玉全,孙志挥.基于频繁模式树的关联规则增量式更新算法.计算机学报,2003,26(1):91-96.[35]K.L.Lee,GuanlingL,ArbeeL.P.Chen.EfficientGraph-BasedAlgorithmforDiscoveringandMaintainingKnowledgeinLargeDatabases.MethodologiesforKnowledgeDiscoveryandDataMining:ThirdPacific-AsiaConferencePAKDD-99,Beijing,China,1999:409-419.[36]MingCT,WenYLandRongJeng.MaintenanceofGeneralizedAssociationRulesUnderTransaction.DataWarehousingandKnowledgeDiscovery:7thInternationalConference’,DaWaK2005,Copenhagen,Denmark,2005:336-345.-45-万方数据 基于灰色系统理论的动态关联规则挖掘研究[37]ZequnZhou,C.I.Ezeife.ALow-ScanIncrementalAssociationRuleMaintenanceMethodBasedontheAprioriProperty.AdvancesinArtificialIntelligence:14thBiennialConferenceoftheCanadianSocietyforComputationalStudiesofIntelligence,Ottawa,Canada,2001:26-35.[38]Jia-LingKoh,Shui-FengShieh.AnEfficientApproachforMaintainingAssociationRulesBasedonAdjustingFP-TreeStructures.DatabaseSystemsforAdvancedApplications:9thInternationalConference,DASFAA2004,JejuIsland,Korea,2003:417-424.[39]PaurayS.M.Tsai,Chih-ChongLee,ArbeeL.P.Chen.AnEfficientApproachforIncrementalAssociationRuleMining.MethodologiesforKnowledgeDiscoveryandDataMining:ThirdPacific-AsiaConference,PAKDD-99,Beijing,China,April1999.Proceedings:74-83.[40]王晓墩,熊伟.基于改进灰色预测模型的动态顾客需求分析.系统工程理论与实践,2010,30(8):1380-1388.[41]平海,罗国强.基于灰色系统理论的物料采购预测模型.统计与决策,2010,12:171-172.[42]仇芝.灰色组合模型研究与应用.南京航空航天大学,2006.[43]贾海峰,郑耀泉.灰色时序组合预测模型及其在年降水量预测中的应用.系统工程理论与实践,1998,18(8):122-126.[44]ZhangYi,WeiYong,ZhouPing.ImprovedApproachofGrayDerivativeinGM(1,1)Model.TheJournalofGreySystem.2006,116(10):160-162.[45]SunYan-na.OptimizationofGreyDerivativeinGM(1,1)BasedontheDiscreteExponentialSequence,2009.Huangshan,P.R.China,Proceedingofthe2ndInternationalSymposiumonInformationProcessing(ISTP2009):2009,313-315.[46]邓聚龙.灰预测与灰决策.华中理工大学出版社,2002,60-71.[47]刘思峰,邓聚龙.GM(1,1)模型的适用范围.系统工程理论及实践,2000,20(5):121-124.[48]任峰,李伟,丁超.基于灰色-周期外延组合模型的电力负荷预测.电网技术,2007,24:52-54.[49]杨俊祥,程盛芳.灰色-周期外延组合模型在煤炭需求预测中的应用.统计与决策,2010,13:162-163.[50]迟道才,李雪,张兰芬,陈涛涛,王堃.灰色-周期外延组合模型在参考作物腾发量预测中的应用.节水灌溉,2012,12:30-36.[51]刘素芳,邓卓燊.中山大学附属医院总诊疗人次灰色-周期外延组合预测模型分析.中国卫生统计,2012,06:875-876.[52]马春茂,邵延君,潘宏侠,刘永姜.基于灰色马尔可夫模型的装备故障间隔期预测研究.兵工学报,2013,09:1193-1196.[53]张绍德,毛雪菲,毛雪芹,高尚义.基于greyMarkov-支持向量机的电弧炉终点参数预报.控制理论与应用,2009,12:1443-1448.[54]HanjuLi,YangYi,XiaoxingLi,ZixinGuo.HumanactivityrecognitionbasedonHMMbyimprovedPSOandeventprobabilitysequence.JournalofSystemsEngineeringandElectronics,2013,03:545-554.[55]HanJ,PeiJ,YinY.Miningfrequentpatternswithoutcandidategeneration//Proceedingsof-46-万方数据 基于灰色系统理论的动态关联规则挖掘研究攻读学位期间的研究成果在校期间发表的学术论文：[1]张忠林,石皓尹,宋航.灰色-周期外延模型的动态关联规则元规则挖掘[J].计算机科学,2014,41(4):239-243.[2]张忠林,石皓尹,闫光辉.灰色Markov模型动态关联规则趋势度挖掘方法.计算机工程与应用,2014,10.在校期间参与的科研项目：[1]《通信资源资产经营决策支持系统研发与开发》[2]《基于动态关联规则元规则的通信客户流失预测模型的挖掘研究》-48-万方数据