基于高平均效用的模式挖掘算法研究

《基于高平均效用的模式挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于高平均效用的模式挖掘算法研究RESEARCHOFHIGHAVERAGEUTILITYPATTERNMININGALGORITHMS任师锋哈尔滨工业大学2017年12月国内图书分类号：TP391.4学校代码：10213国际图书分类号：621.3密级：公开工程硕士学位论文基于高平均效用的模式挖掘算法研究硕士研究生：任师锋导师：林浚玮副教授申请学位：工程硕士学科：计算机技术所在单位：深圳研究生院答辩日期：2017年12月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP391

2、.4U.D.C:621.3DissertationfortheMaster’sDegreeofEngineeringRESEARCHOFHIGHAVERAGEUTILITYPATTERNMININGALGORITHMSCandidate：ShifengRenSupervisor：AssociateProf.Chun-WeiLinAcademicDegreeAppliedfor：Master’sDegreeofEngineeringSpeciality：ComputerTechnologyAffili

3、ation：ShenzhenGraduateSchoolDateofDefence：December,2017Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要数据挖掘的主要目标是从不同类型的数据集中挖掘出重要的，有意义的，具有潜在价值的信息。频繁项集和关联规则挖掘是模式挖掘中经典的课题之一，其主要考虑项集的频繁度并对得到的项集进行关联分析。频繁项集挖掘仅考虑项集在数据集中出现的频繁度，没有涉及其他维度

4、的信息。为发现更多有意义的模式，例如高利润的商品组合，通过综合考虑项集的数量和利润，高效用项集挖掘被提出用于挖掘出具有高效用的项集。高效用项集挖掘的缺点在于其没有考虑项集的长度，容易挖掘出无效的长模式，其中组成长模式的项的效用非常低。因此，通过综合考虑效用和长度，高平均效用项集挖掘被提出，在高平均效用的概念框架下，本文主要解决目前存在的三个问题。针对现有算法在挖掘增量式数据集时效率低下问题，本文提出了一个基于HAUP-tree树模式的算法。该算法在内存中维护一个特殊的树结构，用于保存历史数据集的必要

5、信息。每当有新数据插入时，算法只需要对新增数据进行遍历获取必要信息，然后基于设计的快速更新策略，更新内存中的树结构，并执行挖掘算法。相比现有算法，该算法仅需要很少次数的数据集遍历就能达到和现有算法一样的挖掘效果。由于现有算法采用的上限模型过于宽松，因此本文提出了一个更加高效的算法，该算法通过设计的二个新上限模型和基于该模型的剪枝策略，减小了搜索空间，提升了项集挖掘的效率。新的上限模型从理论上保证了新算法的搜索空间小于采用旧上限模型的算法。由于现有算法都是在设置单一阈值的情况下挖掘项集，忽略了数据集中

6、不同项的特点，容易导致稀有项解问题，即设置过大的阈值容易漏掉有意义的项集，而设置过小则又易挖掘出许多无意义的项集。针对该问题，本文提出了基于多阈值的高平均效用项集算法，该算法能够克服现有算法低效的弱点，通过设计的排序搜索树保证上限模型的向下封闭性，并基于优化的平均效用表结构设计剪枝策略，减小搜索空间，避免现有算法频繁扫描数据库的缺点。本文针对性的解决了高平均效用项集中的三个基本问题，并设计和运行大量实验验证了本文所提出算法的有效性，其均能克服现有算法的缺点，达到更高效更节省内存的目标。关键字：高平均

7、效用模式挖掘；多阈值；上限模型；事务数据I哈尔滨工业大学工程硕士学位论文ABSTRACTThemainpurposeofdataminingistodiscoverimportant,interestingandvaluableinformationfromvariouskindsofdatabases.Frequentitemsetmining(FIM)andassociationrulemining(ARM)aretwooftheearliesttopicsofpatternmining.FIM

8、discoversallitemsetwhosefrequencyisgreaterthantheuserpreferredminimumsupportthreshold.ARManalyzethecorrelationofdiscovereditemsetsandfindallassociationruleswhoseconfidenceisgreaterthantheuserpreferredminimumconfidence.FIMjustconsiderthe