试论挖掘频繁闭项集并构建其格的快速算法研究

《试论挖掘频繁闭项集并构建其格的快速算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、挖掘频繁闭项集并构建其格的快速算法研究重庆大学硕士学位论文学生姓名：张贺指导老师：李学明副教授专业：计算机软件与理论学科门类：工学重庆大学计算机学院二OO八年四月ResearchonAFastAlgorithmforMiningClosedFrequentItemsetsandBuildingTheirLatticeAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheDegreeofMasterofEngineeringbyZhangHeSupervisor:AssociatePr

2、of.LiXuemingMajor:ComputerSoftwareandTheoriesCollegeofComputerScienceofChongqingUniversity,Chongqing,ChinaApril,2008重庆大学硕士学位论文中文摘要摘要随着经济的发展，信息对于一个国家或者企业越来越重要，人们被淹没信息之中，却得不到更多有用的知识。因此数据挖掘技术应运而生，并越来越显示出强大的生命力。关联规则挖掘作为数据挖掘领域的一个重要研究分支，它的任务是发现所有满足支持度阈值和置信度阈值的强关联规则。近年来，关联规则挖掘研究己经成为数据挖掘中的一个热点，并被广泛应用于金融

3、、市场营销、事务分析等应用领域。关联规则挖掘算法是关联规则挖掘研究的主要内容，传统的关联规则挖掘算法以挖掘频繁项集为主要任务，但挖掘所有频繁项集需要大量的工作量；较前的研究表明：传统的关联规则挖掘产生太多冗余规则，而挖掘频繁闭项集的数量远小于所有频繁项集的数量，而且频繁闭项集不会产生信息丢失。因此用挖掘频繁闭项集来代替挖掘所有频繁项集是一个不错的选择。但为了加快产生关联规则的速度，仅仅有频繁闭项集是不够的，需要将项集之间的关系用一种有效的数据结构保存起来，格就是这样一种结构。因此用挖掘频繁闭项集及其格结构算法来快速高效的产生关联规则是一个重要的研究方向。本文主要工作包括：1）总结了目前

4、一些挖掘频繁闭项集算法的不足，并针对最新的CHARM算法和频繁闭项集及其格结构算法CHARM_L进行了深入分析。2）针对CHARM_L算法中消除冗余效率不高、建格效率较低等缺点，引入了preC的概念，并进而提出了一种改进算法：Q-CFIsL算法。该算法在CHARM_L基础上，继承了CHARM_L的优化策略，同时采用了一些新的方法克服了CHARM_L的不足；该算法基于垂直数据结构，采用了一种直接利用IT-Tree的线性消除冗余的有效方法来构建频繁闭项集格，从而实现了挖掘频繁闭项集与建格的统一，并通过实验表明：当最小支持度越小，Q-CFIsL算法的性能就越优越，优于当前最新的同类算法CHA

5、RM_L。3）结合Q-CFIsL算法，利用挖掘出的频繁闭项集格来挖掘最小关联规则，根据最小关联规则推导出所有满足条件的关联规则，并通过实验证明了最小关联规则的有效性。关键词：关联规则，频繁闭项集，频繁闭项集格I重庆大学硕士学位论文英文摘要ABSTRACTWiththedevelopmentofeconomy,informationbecomesincreasinglyimportantforacountryandenterprises.Peoplearedrownedininformation,butgetlittleusefulknowledge.Thereforedataminin

6、gtechnologieshaveemergedandshownstrongvitality.Associationrulesmining,producinginterestingassociationorcorrelationrelationshipsamongalargesetofdataitems,isanimportantsub-branchofDataMining.Associationrulesareconsideredinterestingiftheysatisfyboththeminimumsupportthresholdandtheminimumconfidencet

7、hreshold.Associationrulesmininghasbecomeahotresearchtopicinrecentyears,andbeappliedwidelytovariousfields,suchasfinance,marketingdecisionanalysisandbusinessmanagementetc.Intheassociationrulesmining,thealgorithmsarethecore.Con