基于序列模式的序列聚类挖掘算法研究

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

1、分类TP391密级_____________硕士学位论文基于序列模式的序列聚类挖掘算法研究杨天霞导师姓名职称：王治和教授专业名称：计算机应用技术研究方向：数据库技术及应用（数据挖掘）论文答辩日期：2010年6月学位授予日期：2010年6月答辩委员会主席：评阅人：二○一○年六月硕士学位论文M.D.Thesis基于序列模式的序列聚类挖掘算法研究Thestudyofsequenceclusteringminingalgorithmbasedonsequencepattern杨天霞YangTianxia独创性声明-I-摘要序列模式挖掘是从大型时序数据库中

2、发现事件之间存在的隐藏的、有趣的序列关系，挖掘出基于时间或者其它顺序的出现频率高的频繁序列模式。它弥补了关联规则挖掘不能反映事件在时间顺序上相关性的缺点。序列模式挖掘技术已在顾客购买行为分析、DNA序列模式分析等多个领域得到了广泛的应用。本文重点研究了在已挖掘的频繁序列模式的基础上，再利用划分聚类的K-均值算法对序列数据进行聚类研究。文中利用Huffman树的构造思想对K-均值算法随机选取初始中心点会导致聚类结果的不稳定性缺点提出了一种新的解决算法K-SPAM(K-meansalgorithmofsequencepatternminingbase

3、dontheHuffmanMethod)。K-SPAM算法实现了对包含相似模式的序列数据进行聚类，通过对聚类初始中心点的选取采用Huffman思想，减少了K-均值算法的迭代次数，提高了聚类的稳定性。并通过实验对K-SPAM和K-均值算法的聚类结果进行比较，进一步证实了K-SPAM算法的优点。关键词：数据挖掘；序列模式；K-均值；相异度；Huffman算法-II-AbstractSequentialpatternminingistodiscoverhiddenandinterestingsequencerelationshipsbetweeneve

4、ntsfromlargesequencedatabases,andtotapoutthehighfrequentsequentialpatternsoftime-basedorothersequences.Sequencepatternminingmakesupfortheshortcomingsthatassociationruleminingdoesnotreflectthechronologicalorderrelevancebetweenevents.Sequentialpatternmininghasbeenwidelyappliedi

5、nmanyfields,suchasCustomerBuyingBehaviorAnalysis,DNASequencePatternAnalysisandetc.ThispaperfocusesontheproblemthatsequentialdatabasehasbeenfurtherclusteredbyusingK-meansalgorithmonthebasisoftheresultsofsequentialpatternmining.Inthepaper,anewalgorithmnamedK-SPAM(K-meansalgorit

6、hmofsequencepatternminingbasedontheHuffmanMethod)isproposedonthebasisofHuffmantree’sstructureideas.Thisalgorithmaddressesthisshortcomingthatitcouldleadtotheinstabilityofclusteringresultstoselecttheinitialcenterrandomlyinthek-meansclusteringalgorithm.K-SPAMrealizesthefunctiont

7、hatdatasequencescontainingsimilarpatternsareclustered.Huffman’sideasareadoptedtoselectinitialcenterinthek-meansalgorithm.Asaresult,thenumberofiterationsarereducedandthestabilityofclusteringisalsoimproved.Finally,theK-SPAMalgorithmhasbeencomparedwithk-meansalgorithmabouttheclu

8、steringresultsbytheexperimentalmethod,tofurtherconfirmtheadvantageso