资源描述：
《一种基于Markov链模型的动态聚类方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第40卷第2期计算机研究与发展Vol40,No22003年2月JOURNALOFCOMPUTERRESEARCHANDDEVELOPMENTFeb2003一种基于Markov链模型的动态聚类方法邢永康马少平(清华大学计算机系智能技术与系统国家重点实验室北京100084)(xingyongkang@tsinghuaorgcn)摘要对单变量时间序列的聚类,是一类有着广泛应用背景的特殊的聚类问题由于该问题的特殊性,现有的聚类方法无法直接使用,故提出了一种新的基于Markov链模型的动态聚类方法该方
2、法首先对每一个时间序列建立一个描述其动态特征的Markov链模型,从而把对时间序列的聚类问题转化为对Markov链模型的聚类问题然后通过定义各个Markov链之间的距离,采用动态聚类算法完成对这些Markov链模型的聚类使用该方法,分别对一批真实数据和仿真数据进行了聚类试验,都获得了比较好的聚类结果关键词网络数据挖掘;聚类分析;Markov链中图法分类号TP391AClusteringAlgorithmBasedonMarkovChainModelsXINGYongKangandMAShaoPing(S
3、tateKeyLaboratoryofIntelligentTechnologyandSystems,TsinghuaUniversity,Beijing100084)AbstractClusteringasetofunivariatetimeseriesbasedontheirdynamicsisapopularproblemthatcanbewidelyfoundinmanyresearchareasBecausethecommonclusteringalgorithmcan!tdirectlybeusedto
4、resolvethisproblem,anewapproachtogroupingtimeseriesisproposedThisapproachfirstlymodelseachtimeseriesasaMarkovchainthatcapturesthedynamiccharacterofthetimeseries,andthengetstheclusteringresulttothesetimeseriesbyclusteringtheMarkovchainsUsingthismethod,twodiff
5、erentdatasetsareclustered,inwhich,oneisrealdata,andtheotherisartificialdataByqualitativeandquantitativeanalysis,itisprovedthatbothoftheclusteringresultsaregoodKeywordswebmining;clusteranalysis;Markovchain然而它与其他的聚类问题有所不同:∀用于聚类的1简介数据不同一般用于聚类的数据是对研究对象的一个或多个属
6、性的观测值而我们这里的数据是由每11问题描述个用户的浏览过程所产生的一个时间序列而且由为了研究Web上用户的浏览特征,我们对用户于每个用户所访问的页面不相同,所以这些浏览序的浏览过程进行了观察,并获得了一批数据该数列的长度也不相同#聚类的目的不同在一般的据记录了每个用户浏览过的所有页面及访问每个页聚类问题中,聚类的目的是根据研究对象的对应属面的时间我们的目的是根据每个用户的浏览序列性之间的相似性,对其进行分类,使同一类对象具有中所反映出的动态特点,对这些用户进行分类,将具相同或相近的属性取值而在用户浏
7、览序列的聚类有相同或相近的浏览特点的用户分为一类由于预中,我们不仅要考虑用户浏览了那些网页,还要考虑先无法确定分类的数目,所以这是一个聚类问题用户浏览这些网页的时间顺序如对于以下的3个收稿日期:20020131;修回日期:20020603基金项目:国家重点基础研究项目(G1998030509);自然科学基金项目(60223004);国家八六三高技术研究发展计划项目(2001AA114082)130计算机研究与发展2003年用户浏览序列:(用A,B,C∃表示不同的网页)类算法包括均值法、密度法等实际
8、中应用广泛的[3]User1:A%B%C%D%BK均值法,也属于这一类聚类方法User2:B%C%D可以看出,不管采用那一种聚类方法,前提都是User3:C%A%D%B%A要选定或定义一个对研究对象之间相似性的度量,尽管User1和User3包含相同的页面,但它们一般统称为距离度量然而,在对时间序列的聚类的浏览顺序完全不同
