关联规则挖掘算法及应用研究

单位代码：10293密级：专业学位硕士论文论文题目：关联规则挖掘算法及应用研究1212042919顾苗李玲娟教授工程硕士申请全日制申请计算机技术2015年2月学号姓名导师专业学位类别类型专业（领域）论文提交日期ResearchonAssociationRuleMiningAlgorithmandItsApplicationThesisSubmittedtoNanjingUniversityofPostsandTelecommunicationsfortheDegreeofMasterofEngineeringByGuMiaoSupervisor:Prof.LiLingjuanFeb.2015南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名：_____________日期：____________研究生签名：____________导师签名：____________日期：_____________I摘要随着信息技术的发展，尤其是大数据时代的到来，各行各业都积累了大量的数据。如何从这丰富的数据中挖掘出对我们的工作和生活有用的知识，已成为现在及未来的一个热门的研究课题之一。关联规则挖掘作为数据挖掘的重要分支，可以用来分析不同项之间的关联性，分析结果可用于指导许多商业活动做出合理的商业决策，其在很多商业数据的处理中起到了关键的作用。本文主要对关联规则挖掘算法及其应用进行了研究，介绍了关联规则挖掘的基本理论，分析了经典关联规则挖掘算法：Apriori和FP-growth算法，对比了这两种算法的优缺点。在此基础上，对FP-growth算法进行了改进，提出了基于分组和压缩FP-growth算法GCFP-growth(GroupingandCompressingonFrequent-PatternGrowth)。该算法对FP-growth算法做了两方面改进。一方面，将数据源根据数据挖掘研究的目的按照某一个属性进行分组，分组后的数据至少有一个属性值是相同的，在挖掘的时候就可以省去这一列的挖掘，只要在挖掘的结果中加上这一属性值即可。这种方法达到了减少属性的目的，同时也减少了数据挖掘一次性处理过大数据量的压力。另一方面，本文通过改变相邻结点顺序和忽略中间节点的方法实现了对FP-tree的有效压缩。这种方法可以降低新结点的生成频率，达到降低空间和时间复杂度的目的。本文对GCFP-growth算法的优越性进行了验证，并开发了一个招聘信息挖掘系统来客观地体现GCFP-growth算法的实用性。将GCFP-growth算法应用到了现实数据中，对招聘信息进行关联规则挖掘，得到有趣的关联规则，为应聘者提出可行的就业指导建议。关键词:关联规则挖掘，FP-growth，分组，FP-tree压缩，GCFP-growth，招聘信息挖掘IIAbstractWiththedevelopmentofinformationtechnology,especiallytheadventoftheeraofbigdata,largeamountsofdatahavebeenaccumulated.Howtodigoutofknowledgefromthisabundantdataisusefultothewayweworkandlife.Whichisoneofthehotresearchtopics.Associationruleminingisanimportantbranchofdatamining.Itcanbeusedtoanalyzethecorrelationsbetweendifferentitems,andthecorrelationscanguidemanycommercialactivitiestomakesoundbusinessdecisions.Associationrulesminingplaysakeyroleinprocessingbusinessdata.Thisthesisfocusesontheresearchofassociationruleminingalgorithmanditsapplication.itdescribesthebasictheoryofassociationrules,followedbyadetaileddescriptionoftheclassicalassociationruleminingalgorithm:AprioriandFP-growthalgorithm.Bycomparingtheadvantagesanddisadvantagesofthetwodataminingalgorithms.Onthisbasis,theFP-growthalgorithmisimprovedandputtingforwardthepacket-basedandcompressionbasedonFP-growthalgorithm,whichisGCFP-growth(GroupingandCompressingonFrequent-PatternGrowth).thisthesisfocusedontheFP-growthalgorithm.TheGCFP-growthalgorithmisbasedontheFP-growthalgorithmandhasbeenimprovedintwoaspects.Oneaspect,dependingonthepurposeofdatamining,thedatasourceisunderoneattributetomakepacket,sothegroupingdataatleasthavesameitemwhichcanbeomitted,thenaddingthisitemintoresult.Thisapproachcanachievethepurposeofreducingattributesandreducethedisposableprocessingpressureofdataminingonlargeamountofdata.Ontheotherhand,thethesisachievesthecompressionofFP-treebychangingthesequenceoftheadjacentnodesandignoringtheintermediatenodes.Suchacompressionmethodcaneffectivelyreducethegenerationofnewnodes,soastoachievethepurposeofreducingoccupiedtimeandspace.Inthisthesis,thesuperiorityofGCFP-growthalgorithmisvalidatedandIdevelopearecruitmentinformationminingsystemtoobjectivelyreflectthepracticalityofGCFP-growthalgorithm.thecorefunctionofthissystemistoapplytheGCFP-growthalgorithmonrecruitmentinformationdataandminingresultsaredisplayedintheformofwebpages,whichcanbeusefultoanalyzethefrequentitemsetsofrecruitmentinformationtogetinterestingassociationrules,whichcanputforwardfeasiblesuggestionstoguidecandidates’career.Keywords:Dataminingofassociationrule,FP-growth,CompressionofFP-tree,IIIGCFP-growth,RecruitmentinformationminingIV目录第一章绪论.............................................................................................................................................................11.1研究背景及选题的意义............................................................................................................................11.2国内外关联规则挖掘技术研究及应用现状.............................................................................................31.3主要研究内容及论文的结构....................................................................................................................5第二章数据挖掘技术概述.....................................................................................................................................62.1数据挖掘的有关概念................................................................................................................................62.2数据挖掘的数据类型................................................................................................................................72.2.1经典数据类型.................................................................................................................................82.2.2其他数据类型.................................................................................................................................9