数据挖掘技术与关联规则挖掘算法研究

工学博士学位论文数据挖掘技术与关联规则挖掘算法研究毛国君北北京京工工业业大大学学2003年4月分类号：TP311单位代码：10005学号：B200007009密级：北京工业大学工学博士学位论文题目:数据挖掘技术与关联规则挖掘算法研究英文题目:DATAMININGTECHNIQUESANDALGORITHMSFORMININGASSOCIATIONRULES研究生姓名：毛国君专业：计算机应用技术研究方向：人工智能与知识工程导师姓名：刘椿年职称：教授论文报告提交日期：2003.4学位授予日期：授予单位名称和地址：北京工业大学（北京市朝阳区平乐园100号）摘要I摘要数据挖掘是致力于数据分析和理解、揭示数据内部蕴藏知识的技术，它成为未来信息技术应用的重要目标之一。经过十几年的努力，数据挖掘产生了许多新概念和方法。特别是最近几年，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。像其它新技术的发展历程一样，数据挖掘技术也必须经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段，迫切需要在基础理论、应用模式、系统构架以及挖掘算法和挖掘语言等方面进行创新。关联规则挖掘是数据挖掘中成果颇丰而且比较活跃的研究分支，留给研究者的是更深入的课题。面对大型数据库，关联规则挖掘需要在挖掘效率、可用性、精确性等方面得到提升。因此，需要探索新的挖掘理论和模型；需要利用用户的约束等聚焦挖掘目标；需要对一些传统的算法进行改进；也需要研究新的更有效的算法等。鉴于目前数据挖掘技术和关联规则挖掘研究的现状和发展趋势，在各类基金的支持下，我们选择了这一课题开展相关工作。本文的研究主要包括数据挖掘应用系统体系结构、关联规则挖掘理论及其算法等。关于数据挖掘应用系统体系结构研究方面，我们设计了一个数据挖掘应用系统的原型体系结构，系统化地分析了知识发现的基本过程和系统的各部件功能。由于不同的源数据类型、不同的应用目标以及不同的挖掘策略对数据挖掘系统的功能部件要求不同，这些研究主要是从知识发现的基本过程出发，探讨系统应具备的主要功能部件及其相互联系等。在关联规则挖掘理论研究上，我们首次给出了项目序列集格空间，并且探讨了在这个空间上的基本操作算子。基于项目序列集格空间及其操作，我们建立了关联规则挖掘模型和算法。在关联规则挖掘算法方面，设计了基于项目序列集操作理论的关联规则挖掘算法ISS-DM、时态约束下的关联规则挖掘算法TISS-DM、数据分割下的关联规则挖掘算法PISS-DM。ISS-DM算法是建立在严格的项目序列集格理论及其操作基础上，是一个一次数据库扫描的而且不使用侯选集的高效算法。我们选择目前引用率较高的Apriori算法和ISS-DM进行了对比实验。结果表明，ISS-DM执行时间整体上优于Apriori算法，而且随着数据量的增大ISS-DM执行时间的增长幅度也小于Apriori算法。为了提高对大型数据集挖掘的适应性，将时态约束应用到挖掘的预处理中，改进ISS-DM成TISS-DM。这部分工作还包括对时态区间、时态约束下的数据挖掘空间以及时态区间操作等进行了形式化，它们是TISS-DM的理论基础。对ISS-DM的另一个改进算法是PISS-DM。它是针对大数据集挖掘过程中对内存和CPU等系统资源要求较高的情况被提出和设计的，采用了数据分割的方法来减少资源的占用。本文解决了数据分割下局部频繁项目序列集和全局频繁项目序列集的转换等问题，是一个两次扫描数据库的算法。总之，本文在分析、归类现有数据挖掘研究成果以及原型系统的基础上，进行了数据挖掘应用系统体系结构、关联规则挖掘理论模型以及算法方面的研究。在项目序列集格及其操作、时态约束挖掘空间等方面具有较好的摘要II理论价值，所设计的算法在挖掘效率和对大型数据库挖掘的可用性方面具有潜在的应用前景。关键词：数据挖掘，知识发现，关联规则，项目序列集，时态约束，数据分割。AbstractIIIAbstractDataminingisatechniquethataimstoanalyzeandunderstandlargesourcedataandrevealknowledgehiddeninthedata.Ithasbeenviewedasanimportantevolutionininformationprocessing.Whytherehavebeenmoreattentionstoitfromresearchersorbusinessmenisduetothewideavailabilityofhugeamountsofdataandimminentneedsforturningsuchdataintovaluableinformation.Duringthepastdecadeorover,theconceptsandtechniquesondatamininghavebeenpresented,andsomeofthemhavebeendiscussedinhigherlevelsforthelastfewyears.Datamininginvolvesanintegrationoftechniquesfromdatabase,artificialintelligence,machinelearning,statistics,knowledgeengineering,object-orientedmethod,informationretrieval,high-performancecomputingandvisualization.Essentially,dataminingishigh-levelanalysistechnologyandithasastrongpurposeforbusinessprofiting.UnlikeOLTPapplications,dataminingshouldprovidein-depthdataanalysisandthesupportsforbusinessdecisions.Liketheothernewtechniques,however,dataminingmustdevelopgraduallyfromconceptcreation,acceptedimportance,widediscussion,fewusageattemptstoalargeapplications.Mostexpertsconsideritasthephaseofwidediscussiontoday.Itstillneedstheoreticstudiesandalgorithmexploring.Thoughsomeresultshavebeenachieved,moretheoreticproblemsarekeptinongoingresearches.Inaddition,dataminingisfromrealapplicationsandmustcombinewiththespecificbusinessapplicationlogictosolvethespecificproblem.Thisisbecausethatdifferentbusinessfieldshavedifferentminingneedsandtargets.Thesuccessfuldataminingsystemsaretheexcellentcombinationofdataminingtechniquesandthebusinesslogic,ratherthantoolsthataredesignedtomakedataminingapplicationdevelopmentconvenient.AssociationruleminingisanimportantbranchAbstractIVofdataminingthatithasobtainedmanyvaluableresultsbuttherestillareadealofmorechallengingproblemstodiscuss.Forlargedatabases,theresearchonimprovingtheminingperformanceandprecisionisnecessary,somanyfocusesoftodayonassociationruleminingareaboutnewminingtheories,algorithmsandimprovementtooldmethods.Inthispaper,themainresearchesinvolvetheapplicationarchitectureofdatamining,theminingtheoriesforassociationrulesandthedesignofnewefficientalgorithms.ThispaperanalyzedthebasicprocessingphasesofdataminingorKDD,andgivesthecomponentsofadataminingapplicationsystemandtheirfunctions.Intheoreticresearch,wefirstdefineSetofItemSequences,andgivesomeoperatorsonthisalgebralattice.Applyingsuchtheoreticresults,wedesignanalgorithmforminingassociationrulescalledISS-DM,whichisefficientwithonepasstothedatabaseandwithoutlargecandidatesgeneratedandstored.Formininglarge-scaledatabases,itissmartstrategytomakeuseofconstrainsforimprovingdataqualityandreducingdatacapability.Thispaperintroducestheproblemofdataminingbasedontemporalconstrains.WecreatetwonewoperatorsontemporalintervalspaceanddesignanalgorithmcalledTISS-DMbymakingadvanceoftheseoperators.TISS-DMmaybeseenasanimprovementalgorithmtoISS-DM,whichcanprocessmorescaledatabases.Infact,recentresearcheshavepaidmoreattentiontoreducethenumberofpassesoverdatabases(I/Ocost),memoryusageandCPUoverhead.ThispaperalsogivesanalgorithmcalledPISS-DMwhichemploysdatapartitioningtechniqueandonlyhastwopassesoverdatabases.Experimentalresultsshowedthatthesealgorithmshavehigherminingefficiencyinexecutiontime,memoryusageandCPUutilizationthanmostcurrentoneslikeApriori.Inconclusion,thispaperanalyzesapplicationAbstractVarchitectureofdataminingsystems,createsnewmining