用户搜索关键词

ComputerScienceandApplication计算机科学与应用,2013,3,232-238http://dx.
doi.
org/10.
12677/csa.
2013.
34040PublishedOnlineJuly2013(http://www.
hanspub.
org/journal/csa.
html)TheStudyandImplementationofWebUserMiningSystemBasedontheSimilarityofWords*ChengxiaLiu1,2,FeiyingWu21ComputerSchool,BeijingUniversityofPostsandTelecommunications,Beijing2ComputerSchool,BeijingInformationandTechnologyUniversity,BeijingEmail:cecilia7812@163.
comReceived:May13th,2013;revised:May27th,2013;accepted:Jun.
5th,2013Copyright2013ChengxiaLiu,FeiyingWu.
ThisisanopenaccessarticledistributedundertheCreativeCommonsAttributionLicense,whichpermitsunrestricteduse,distribution,andreproductioninanymedium,providedtheoriginalworkisproperlycited.
Abstract:Nowadays,aswebminingisextremelyprevalent,itiseasytocollecthugeamountsofdatabuttofigureoutwhichmaterialsareusefultoanalyzeafterde-noisingismoreimportant.
Thisarticlediscusseshowtousetheresultofuser'ssearchingkeywordsclusteringasthelabeloftheclientforoperationalanalyststoreferto.
Thesimilaritybetweenisolatedwordsiscalculatedbyturningthewordsemanticdistancebasedonworldknowledgeorclassificationsystem.
Thenthesimilaritybetweenclients(keywordsets)isdefinedastheEuclideandistanceofasimilaritymatrixconstitutedbythesimilaritiesbetweenkeywordsetswhichdeterminedbywordfrequencyandwordweight.
The"depmix"packagewhichbasedontheHiddenMarkovModelin"R"softwareisusedastheclusteringalgorithmandtheuserclusteringresultisdisplayedatlastusingtherealdataoftheusersofasearchengine.
Keywords:TheSimilarityofWords;TheSimilarityBetweenClients(KeywordSets);UserClustering基于关键词相似度的Web用户挖掘研究与实现*刘城霞1,2,吴菲滢21北京邮电大学计算机学院,北京2北京信息科技大学计算机学院,北京Email:cecilia7812@163.
com收稿日期:2013年5月13日;修回日期:2013年5月27日;录用日期:2013年6月5日摘要:在Web挖掘极度盛行的今天,收集大量网络数据已经不是问题,而如何在海量数据中抽取去噪后的有用数据成为要解决的关键问题.
本文研究将网站用户的搜索关键词分析聚类,作为用户的兴趣、爱好标签,以供运营分析人员参考.
文中根据世界知识或分类体系计算词语语义距离后转化为词语相似度的方法,将词语间距离依据词频、词权重等因子加工计算出关键词集合间相似度矩阵后,用欧式距离表示其关键字集的相似度;之后聚类算法利用现有R软件中开源算法包——基于隐马尔科夫模型的depmix算法包进行的用户聚类算法.
最终用某搜索引擎用户的真实数据,经过数据去噪后所得实验数据进行聚类,并于前台展示聚类及用户周边相关结果.
关键词:词语相似度;关键词集合相似度;用户聚类1.
引言近些年来互联网行业飞速发展,机构、团体和个人越来越多地依赖互联网发布信息、查找信息,这成就了互联网上的海量数据,但同时这些无结构的、动*资助信息:北京市人才强教计划——骨干教师(PHR201008428),北京市教委科技发展计划项目(KM201110772013)资助.
Copyright2013Hanspub232基于关键词相似度的Web用户挖掘研究与实现态的Web页面的复杂程度远远超过了文本文档,所以人们要想找到自己想要的数据依然犹如大海捞针一般.
Web挖掘是将传统的数据挖掘技术和Web结合起来,就能解决这些问题.
如果说Web使用挖掘是通过挖掘访问者在网站上留下的痕迹来获取有用的信息,那么Web用户挖掘则是要寻找Web用户的根源.
通过对Web用户信息的统计分析,能够帮助运营商以较低成本获得准确度较高的客户兴趣倾向、个性化需求以及新业务发展趋势等信息.
本文是基于搜索引擎用户进行的研究,致力于根据不同用户的不同搜索关键词,为用户打上相应的个性标签,以便运营分析人员对用户的兴趣、爱好有更精确的方向上的把握,并且做出更好的信息推送及搜索引擎优化.
2.
关键词间相似度算法2.
1.
相似度计算的基本概念相似度计算中有两个主要的概念为:"概念"与"义原".
"概念"是用来描述词汇的语义的,一个词语可以用一个或多个概念来表示.
这种描述方法叫做用"知识表示语言"来描述词语的语义,而这种用来构成"知识表示语言"的"词汇"就叫做"义原".
与一般的语义词典不同,"知网"中的概念层次树并不仅仅是一个归结了所有"概念"的概念层次体系树,而是将每一个"概念"用一系列的"义原"来描述清晰.
"知网"将义原分为以下几个大类[1]:1)Event|事件2)entity|实体3)attribute|属性值4)aValue|属性值5)quantity|数量6)qValue|数量值7)SecondaryFeature|次要特征8)syntax|语法9)EventRole|动态角色10)EventFeatures|动态属性这些义原大致被归为3组:第1组,第1~7类义原,称之为"基本义原",用来描述单个概念的语义特征;第2组,第8类义原,称之为"语法义原",用于描述词语的语法特征,主要是词性的表达;第3组,第9、10类义原,称之为"关系义原",用于描述概念和概念之间的关系.
2.
2.
词语相似度算法分析对于两个词语W1和W2,如果W1有n个概念:S11,S12,…,S1n,W2有m个概念:S21,S22,…,S2m,把两词语间的相似度问题定义为两组概念间的相似度问题.
1)义原相似度的计算义原间的相似度计算是概念相似度的计算的基础,因为所有概念最终都会归结于用义原来表示.
本文采用通过语义距离来计算义原结点间相似度的办法,即假设两个义原在此层次体系中的路径距离为d,则这两个义原间的语义距离[2]可由1212Sim,,WWDisWW(1)计算得来,具体化为:12Sim,PPd(2)其中为可调节参数,P1和P2表示两个不同义原,d是P1和P2在层次树中的路径长度,记为一正整数.
2)虚词概念的相似度的计算因为在"知网"的知识描述语言中,虚词概念只用"{句法义原}"或"{关系义原}"这两种方式进行描述,所以计算虚词概念的相似度就等价于计算其对应的句法义原或关系义原之间的相似度.
3)实词概念的相似度的计算本文采用的相似度计算方法是通过部分相似度的合成来代替整体相似度.
首先建立两个整体中的各个部分之间一一对应的关系,随后计算各个配对间的相似度,加权求和.
若某一部分的对应为空时其相似度定义为一个比较小的常数δ,和具体词与义原的相似度定义为同一级别.
4)特征结构和集合的相似度计算①特征结构的相似度计算特征的定义是一个"属性:值"对,特征结构就是"属性:值"对的集合.
在特征结构中,每个"特Copyright2013Hanspub233基于关键词相似度的Web用户挖掘研究与实现征"的"属性"是唯一的.
将特征结构的相似度转化为各个特征之间的相似度的均值.
两个特征的相似度就等价于其"值"的相似度.
②集合的相似度计算两个集合的相似度计算的简单模型如下:m搜索关键词对用户搜索关键词词频以及用户搜索关键词的乘积进行求和后比上每一对后两者的乘积求和所得的商便是最终的用户–关键词的加权平均相似度.
n个关键词集合(用户)与m个特征关键词首用户-关键词矩阵(n*m),定义为:111mQQ1nQQnm(5)ijQ定义如下:其中,11,itjtQkwkwititijitittTkwWkwQTkwWkw(6)其中,Q(kwit,kwj)表示关键词集合(用户)i的第t个关键词与关键词集合W中第j个关键词的相似度;T(kwit)是关键词集合i的第t个关键词在关键词集合中出现的频次;W(kwit)是关键词集合(用户)i的第t个关键词的权重.
由于Q的取值在[0,1]之间,显然ijQ∈[0,1].
ijQ的定义考虑了将关键词综合加权来表示关键词集用户)在特征空间中的取值.
使用欧式距离表示关键词与合(关键词集合(用户)的相似度.
即两用户间距离表示为两用户与每个关键词相似度的差平方的和的开平方,相似度S定义公式如下:21mikjkkSQQ(7)由以上定义可得出关键词与用户可以描述:的相似度(S),并以此为依据聚类出与关键词相关的用户群.
3.
相似度算法设计3.
1.
词语间相似度算法词语间相似度计算算法Copyright2013Hanspub235基于关键词相似度的Web用户挖掘研究与实现step1:若两词语中有一个词语未收录到词库中,则默两词语相关联的所有解释概念(义原ep3:计算两个解释概念的相似度时,若两概念一为3.
2.
算法涉及(KeywordVector)、关键词与关细信息述:键词算两用户与同与同集合中所有关户间get_sim_VV(intclient1_id,intcli-ent2i;sum=0.
0;每一个关键词的相似度的差平方个数;i++){相似度矩阵中的位置,=取得client1_id的第i个关键词;相似度=temp_differ*temp_differ;//计算相似度,求差平th.
sqrt(sum);//求和后的差平方开平方}词在"用得到两用户与同集合中所有关两用户间legetVWsim(int[]vcti,intj)//vcti为关键sum_sim_t_w,sum_t_w;认相似度为0;step2:分别计算/基本词)的相似度,取其最大值为两词语相似度;st实词一为虚词,则相似度默认为0;若两概念均为虚词,则返回其虚词义原间相似度;若两概念均为实词,则分别计算其第一基本义原相似度、其他基本义原相似度、关系义原相似度以及关系符号相似度,依照(2)计算其相似度并返回.
用户间相似度算法到关键词集合键词集合相似度(Similarity_V_W)和关键词集合间相似度(VectorSimilarity)三个类,其关系如下:一个KeywordVector实例提供所有关键词的详及个关键词间相似度矩阵的map;一个Similarity_V_W实例在初始化时,便根据clients文件计算出所有不重复关键词向量及个个关键词的词频、id,并查询KeywordVector实例中的相似度矩阵生成所有用户与关键词间的相似度矩阵.
而一个VectorSimilarity实例通过查询一个Similarity_V_W的实例,提供了计算用户间相似度的计算方法.
用户–用户相似度算法描依次从关键词集合中取出一个关step1:根用户id以及关键词id分别计一关键词在"用户–关键词"相似度矩阵中的id;setp2:根据这两个id查询相似度矩阵得到两用户一关键词的相似度,并求其差平方;step3:重复第step1-step3步直至关键词键词已使用过,过程中将相似度的差平方累加;step4:将最后的累加和开平方后得到的就是两用的相似度.
publicdouble_id){intDouble//将两关键词集合与求和后再开平方for(i=0;i搜索关键词本身比较偏僻,导致计算词语相似度是已经不合理或者该用户的搜索关键词词频较低及该用户的搜索关键词在关键词集合中的权重较低.
索结果的满意程度决定下一搜索关键词的内容.
同时随着时间的推移社会热点的变动,搜索关键词的主流内容也会随之变动.
因此可以认为用户的搜索关键词与用户的兴趣[10]及时间有着密切联系.
在用户聚类过程中,实验采用了R软件的中的隐马尔科夫模型用于聚类.
通过聚类,测试数据中84位用户共聚类出24类用户群,以"电影"主题相关的聚类结果结果为例分析如表4:可以看到前两位用户与"电影"主题有较5位用户与"电影"主题关联渐弱.
原因是挑选主题相关用户类时是挑选与该主题相似度最大的用户的所在类,所以并不是该类所有用户都与该主题相Table3.
Resultofusersimilarity表3.
用户相似度结果分析1/0.
0.
62480.
68930.
735258631.
01482//0.
84270.
94380.
81421.
22863///0.
59750.
83310.
69174////0.
84880.
952251.
0764Table4.
Clustefmovietitle表4.
果idro题相关的聚类结"电影"主注册方式关键词标签用户11ipad,iteye275手机注册明天,新闻,用户21231邮箱注册2小有限公司,物流,公司黄岩岛,油价,下调,012,娱乐,音乐,李双江用户31100手机注册升初,怪圈,安阳,教育局用户41304邮箱注册洛阳,众,托,货运,赛,成功用户51616邮箱注册用户61631手机注册盘古,搜索,百度用户71224手机注册我,爱,你Copyright2013Hanspub237基于关键词相似度的Web用户挖掘研究与实现Copyright2013Hanspub238似度很大就果中聚为户会参考文献(References).
http://wwwzhiwang_r.
html度计算[D].
报,2008,22(5):84-89.
究[J].
计算向量的词语相似度计算onfeatureselection度的中文文本相似度算法研究[D].
浙于关键词和摘要相关度的文献聚类研究兴趣相似性的Web用户聚类[J].
山东;还有是聚类结一类的用有机各自不同的关注面,因此被选用户类中只有部分用户与主题相关较大.
如希望得到更好的效果,可以参考文献[3]的方法.
[1]董振东,董强.
知网[URL],2003.
keenage.
com/zhiwang/c_[2]刘群,李素建.
基于《知网》的词汇语义相似中国科学院计算技术研究所,2002.
北京:[D].
南京大学,2008.
[10]张文东,易轶虎.
基于[3]江敏,肖诗斌,王弘蔚,施水才.
一种改进的基于《知网》的词语语义相似度计算[J].
中文信息学[4]王小林,王义.
改进的基于知网的词语相似度算法[J].
计算应用,2011,31(11):3075-3090.
[5]杨金柱,刘金岭.
基于词语上下文的文本分类研机技术与发展,2011,21(8):145-149.
[6]张涛,杨尔弘.
基于上下文词语同现[J].
电脑开发与应用,2005,18(3):41-43.
[7]Y.
Yang,J.
O.
Pedersen.
Acomparativestudyintextcategorization.
Proceedingsofthe14thInternationalCon-ferenceonMachineLearning.
SanFrancisco:MorganKauf-mann,1997:412-442.
[8]金希茜.
基于语义相似江工业大学,2009.
[9]魏建香,苏新宁.
基大学学报,2006,41(3):45-48.