互联网中的海量用户行为挖掘算法研究

中国科学技术大学硕士学位论文互联网中的海量用户行为挖掘算法研究姓名：周津申请学位级别：硕士专业：信号与信息处理指导教师：俞能海2011-05-05摘要Ⅰ摘要随着计算机技术以及互联网的飞速发展，在Web中产生了越来越多的基于用户的应用，这些应用数年来收集了海量的用户行为数据，且数据还正以指数级增长，这些海量数据中包含了大量和用户相关的信息。及时、精确地从这些海量用户信息中发现有用的知识，挖掘出这些数据背后隐藏的用户行为模式，能够帮助互联网应用提供更好的用户体验，并提高企业的市场竞争力。本文采用数据挖掘的方法对互联网中的用户行为进行分析挖掘，找出其中隐藏的规律与模式。并从基于Web2.0的社会化标记系统中的用户标记行为分析和互联网搜索引擎中的用户检索行为分析两个方面进行说明。(1)在社会化标记系统中，用户可以自主采用不同的标签标记资源，并利用这些用户标签实现信息资源的组织、分类和检索，但是这种自由的用户标记行为存在着信息描述不精确、标签组织混乱和标签语意模糊等问题。现有研究常采用聚类等数据挖掘技术来解决这些问题，现有标签聚类算法大多根据不同标签在对象中共同出现的次数来计算它们之间的相似度，但是这种方法聚类的精确度与召回率并不高。针对此问题，本文提出了一种新的标签聚类算法，充分考虑标签的标记信息，采用基于对象的特征向量来精确地表征一个标签，根据余弦相似度公式得到较为准确的标签相似度，然后采用K-Means算法将用户标签进行聚类。实验结果表明该算法能够得到更加精确的聚类结果。最后将该算法应用于中国科学技术大学《图书馆交互式科研管理平台》证明该算法的实用性。(2)另一方面，在搜索引擎中，后台日志会记录用户输入的查询词和点击的URL，作为用户与搜索引擎的交互信息。通过挖掘搜索引擎日志中的用户行为，可以发现用户的行为规律，收集统计信息，进而用来改善搜索引擎返回结果的排序。但是由于搜索引擎中日志记录数据海量的特性，传统的聚类算法无法适用在搜索引擎用户行为分析中。针对此问题，本文对搜索引擎中的用户行为采用三部图模型建模，利用特征向量来表征用户输入的查询词，并提出一种基于倒排表查询和MapReduce的分布式K-Means聚类算法，实验证明该算法能够应对海量用户查询词聚类的问题，并且在大规模数据集下表现出高效的性能。最后再根据实验得到的聚类结果分析当前互联网搜索引擎中用户行为的特点。关键词：特征向量数据挖掘用户行为分析K-Means分布式MapReduceAbstractⅡABSTRACTWiththefastdevelopmentofthecomputertechnologyandInternet,moreandmoreapplicationsbasedonusersaregeneratedintheWeb.Theseapplicationshavecollectedmassiveuserbehaviordataforseveralyears,andthedataisgrowingexponentially.Thismassivedatacontainslargeamountsofinformationaboutusers.ItcanhelpInternetapplicationsprovidebetteduserexperience,andimprovecompany’smarketcompetitiveness,ifwecouldfindusefulknowledgefromthemassiveuserinformation,andgettheuserbehaviorpatternsbehindthesedata.Inthispaper,weanalyzeandstudytheuserbehaviorsinInternetusingthedataminingmethod,andfindthehiddenregularpatternsandmodels.Wecarryoutourresearchesintwoaspects:theanalysisofusertaggingbehaviorinthesocialtaggingsystembasedonWeb2.0;andtheanalysisofuserqueryingbehaviorinthesearchengineinInternet.(1)Inthesocialtaggingsystems,usercanmarkresourcesfreelywithdifferenttags,andachievethegoalofinformationresource’sorganization,classificationandretrievalusingtheseusertags.Buttherearemanyproblemsinthiskindoffreeusertaggingbehavior,suchasimprecisionofinformationdescription,messoftagorganizationandconfusionoftagsemanticmeanings.Existingresearchoftenusesdataminingtechniques,suchasclustering,toremedytheproblemsoftagredundancyandambiguity.Thecurrenttagclusteringalgorithmsaremainlybasedonthetagco-occurrenceindifferentitems,butthesealgorithms’clusteringprecisionandrecallarerelativelylow,whichcanonlycalculatethesimilaritybetweentwotags.Weproposeanewtagclusteringalgorithminthisthesis,whichintroducesanobject-basedfeaturevectortocharacterizeasingletag.Thisfeaturevectorcanrepresentatagexactlyandcangetamoreaccuratesimilaritybetweentwotagsbyusingcosinesimilarityformula.K-Meansalgorithmisusedtoclustertheusers’tags.Theexperimentshowsthatthealgorithmproposedinthispapercangetamoreaccurateclusteringresult.Atlast,weapplythisalgorithmtothe“LibraryInteractiveSystemforEducationandResearch”systeminouruniversitytoapprovethisalgorithm’spracticability.(2)Ontheotherhand,inthesearchengine,backendlogrecorduser’sinputqueriesandclickedURLsastheinteractiveinformationbetweenuserandsearchengine.Throughminingtheuserbehaviorsinsearchlog,wecanfinduserbehavior’sAbstractⅢregularpattern,collectstatisticinformation,andthenuseittoimprovethesearchengine’sresultrank.Butbecauseofthemassivepropertyofsearchengine’slogdata,traditionalclusteringmethodcannothandletheanalysisofuserbehaviorsinsearchengine.Towardsthisproblem,weuseatripartitegraphtomodeltheuserbehaviorinsearchengine,anduseafeaturevectortocharacterizeuserinputqueries,andthenproposeadistributedK-Meansclusteringalgorithmbasedoninvertedtable’squeryandMapReduceinthisthesis.Theexperimentshowsthatthisalgorithmcanhandletheclusteringproblemofmassiveuserqueries,anddemonstrateeffectiveperformanceinlarge-scaledataset.Atlast,weanalyzethecharacteristicofuserbehaviorsincurrentsearchenginebasedontheclusteringresult.Keywords:featurevector,datamining,userbehavioranalysis,K-Means,distributedsystem,MapReduce中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：___________签字日期：_______________中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。□公开□保密（____年）作者签名：_______________导师签名：_______________签字日期：_______________签字日期：_______________第1章绪论1第1章绪论1.1研究背景近年来，随着互联网技术的不断发展，其应用越来越广泛，互联网与生活的结合也越来越紧密，对于很多人来说，上网成了生活必不可少的一部分。同时，随着计算机网络的普及，因特网已经发展成为一个蕴藏着有用知识的海量信息空间，其中蕴含的数据量已经无法计算。对于一般互联网用户而言，一个很关键的问题是怎样准确、快速地从网上获取有价值的信息，并从中找到自己需要的那部分。另一方面，对于互联网运营者来说，他们所关心的一大难题是怎样合理有效地分析用户行为，将用户及其感兴趣的话题、网页进行合理聚类，以提供更好的个性化服务，从而提高企业利益。因此如何分析挖掘互联网中海量的用户行为信息，就成为近年来互联网研究领域的一个重要课题。下面我们举两个互联网常用的基于用户的应用例子来分析下用户行为挖掘的重要性。Web2.0是一种新兴的高度网络化，自由化的互联网形态，它架构在用户、内容、应用基础上，因此吸引了大量用户，衍生出诸如社区网络、博客、播客、网络文摘、维基百科等Web2.0类应用。社会化标注系统就是一种典型的web2.0应用，目前非常流行，也很有发展前景。例如Flickr[4]、del.icio.us[5]、豆瓣网[6]等网站都采用了协同标注，它们的主要特点之一在于它们是公开的、不受控制的系统。用户根据自己的社会文化背景、专门技术和世界观，用不同