关键词盘古搜索引擎

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关系词概念相似度的计算为一个特征结构,该特征最重要的一个基本义原,描述:即除第一基本义原以外所有基本系义原描述:即语义表达式中所有的关系义原,:即所有的关系符号描述式,也表示为一却相其中,βi(1≤i≤4)是可调节的各部分相似度权重参数,stubborn|倔,文字,surname|姓,human|人,Propvestock|牲畜共有表示性格、姓氏以及动物三个为:"属性值","文字","牲义原,默认最大距离20,相似似度Sim1(文字)=0.
15畜"义原距离为2,相似度Sim1(牲畜)=0.
44其它基本义原描述义原:"举止","倔","莠)/m,其中sum为两组A.
一个集合与它本身的相似度为1;B.
假设两个集合都有n个元素,其中m(素相同,又假设两个元素的相似度只能是0(不同)或1(相同),那么这两个集合的相似度应该是m/n.
而两个集合各个元素之间的一一对应关系如下:a)生成两个集合中所有元素两两间相似度的矩b个元素关联为一对;c)从相似度矩阵中取其相互间的相似度;d)重复第b、c两步,与另一集合中某元素生成关联对;e)将没有建立起对应关系的元素与空元根据上述方法建立起两个集合元素的一一对应后,集合的相似度等于其元素对的相似度的算术平均.
5)实对一个实词的描述可以表示结构含有以下四个特征:第一基本义原描述:即实词两个概念相对应的这一部分的相似度记为:Sim1(S1,S2);其它基本义原义原的集合,这一部分的相似度记为:Sim2(S1,S2);关表示为一个特征结构,这一部分的相似度记为:Sim3(S1,S2);关系符号描述个特征结构,这一部分的相似度记为:Sim4(S1,S2).
考虑以下情况:当Sim1非常小,但Sim3或者Sim4对较大时,若直接计算相似度平均值会导致整体的相似度仍然较大,但不合理的现象.
因此很多改进的词语相似度算法也就应运而生[4-6],本文改进实词间相似度算法后公式如下:4121121Sim,Sim,iijjiSSSS(3)且有:β1+β2+β3+β4=1,β1≥β2≥β3≥β4.
β反映了Sim1到Sim4对于总体相似度所起到的作用依次递减.
其意义在于,主要部分的相似度值对于次要部分的相似度值起到制约作用,即若主要部分相似度比较低,那么次要部分的相似度对于整体相似度所起到的作用也要降低,且可以保证一个词和它本身的相似度为1.
举例:两个实词"鸟"、"牛"的相似度计算.
查阅词库得到以下概念的解释:牛N——value|属性值,behavior|举止,undesired|莠牛N——character|erName|专牛N——li鸟N——bird|禽可以看到,"牛"解释,而"鸟"只有禽畜一种解释.
下面来具体分析这两个词的相似度:a)第一基本义原描述"牛"的三组基本义原畜";"鸟"的基本义原为:"禽".
根据查询词库可得:"属性值"没有相同根度Sim1(属性值)=0.
074,"文字"义原距离为9,相1,"牲.
b)"牛"的三组其它基本";"姓","人","专";空.
"鸟"的其它基本义原为空.
因此,由公式(sum+δ*(mn)其它基本义原中依次挑出相似度最大的义原对直至一组基本义原被挑空的相似度之和(由于"鸟"没有其他基本义原,因此sum为0)、m为两组其它基本义原中较多义原一组的义原个数、n为较少一组的义Copyright2013Hanspub234基于关键词相似度的Web用户挖掘研究与实现原个数,可得这两个关键词的其它基本义原的相似度Sim2如表1:c)关系义原描述:此处两词没有关系义原的解释,两词没有关系义原的解释,似度描述因此Sim3默认为1.
0.
d)关系符号描述:此处因此Sim4默认为1.
0.
最终"牛"与"鸟"的相11212SimSimSimSim312341234SimSimSimSimSimSimSim取β1=0.
5,β2=0.
2,β3=0.
17,β4=0.
13得取最大值,得到"鸟"与"猪"的相似度为Sim=0.
44.
2.
3.
用户相似度算法在确定独立关键词间相似度算法后,便可以得到两用矩阵,首先要生成每个用户与Table1.
Basesimilarityofbirdandcow表牛户–关键词相似度矩阵并不仅仅是将用户每个搜索,其相似度、先构成了0.
5*0.
0740.
2*0.
074*0.
2性值组Sim0.
17*0.
074*0.
2*10.
13*0.
074*0.
2*1*10.
044属Sim0.
5*0.
1510.
2*0.
151*0.
20.
17*0.
151*0.
2*10.
13*0.
151*0.
2*1*10.
091文字组Sim0.
5*0.
440.
2*0.
44*10.
17*0.
44*1*10.
13*0.
44*1*1*10.
44牲畜组户关键词集合的相似度矩阵.
传统的文本相似度算法是基于关键词向量的算法[7,8],通常可以通过文献标题、关键词和摘要合并形成特征向量空间来提高文献表示的精度[9],但这增加了计算的维度.
而且传统的文本聚类方法都是将文档表示成关键词特征空间中的一个向量,其取值非0即1,没有考虑关键词部分的相似性.
本文基于以上两点,采用了基于关键词加权的文献相似度计算方法,在不增加特征向量空间维数的情况下,考虑了关键词之间的部分相似性,提高了相似度计算的精度.
要求得各用户之间距离每个关键词之间的用户–关键词相似度矩阵.
用1.
"鸟"与"牛"其它基本义原相似度其他基本属性值3个3个牲畜无义原似度文字鸟无((0.
20.
2*3)/3=0.
22*3)/3=0.
默认为1关键词与关键词集合中关键词间的相似度计算算术平均值罗列出来,而是加入词频、权重等因子的制衡的加权平均相似度.
其中:某关键词的词频即为该关键词在所有的关键词总集合中出现的频次;某关键词的权重为该关键词与所有的关键词总集合中的每一个关键词相似度的最大值.
那么最终用户(关键词集合)与关键词间的相似度就由以下算法确定:对于每一个关键词–用户搜索关键词对用户搜索关键词词频以及用户搜索关键词的乘积进行求和后比上每一对后两者的乘积求和所得的商便是最终的用户–关键词的加权平均相似度.
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<关键词//计算用户与关键词相似度在即其idintkey1intkey2=取得client2_id的第i个关键词;Doubletemp_differ=两用户与同一关键词的差;sum+方求和}returnMa用户–关键词相似度算法的算法描述:step1:依次从关键词集合中取出一个关键step2:根据id分别计算两用户与同一关键词户–关键词"相似度矩阵中的id;step3:根据这两个id查询相似度矩阵一关键词的相似度,并求其差平方;step4:重复第step1-step3步直至关键词键词已使用过,将相似度的差平方累加;step5:将最后的累加和开平方后得到的就是的相似度.
privateDoub字集合{Doublesum_sim_t_w=sum("stw",vcti,j);//计算1tQk1,itjititijitittwkwTkwWkwQTkwWkw()的分母sum_t_w=sum("tw",vcti,j);//计算1tQk1,itjititijitittwkwTkwWkwQTkwWkw()的分子DoublevwSim=sum_sim_t_w/sum_t_w;//计算关键词4.
结词语相似度结果分析两组词语相似度对比如2:较合理的:–用户相似度returnvwSim;}果分析4.
1.
表可以看到,绝大部分结果还是比Copyright2013Hanspub236基于关键词相似度的Web用户挖掘研究与实现Table2.
Resultofwordsimilarity表2.
词语相似度结果分析词语相似度鸟服务腐败人殡葬主题0.
0.
042957950.
04290.
06640.
0429器官0.
14930.
16670.
14040.
06640.
0429捐献0.
07410.
07410.
04290.
13790.
0444春天0.
44440.
04440.
04290.
07400.
0444a)"主题"与另一组中关键词的"人"相似度最大;)"器官"与另一组中关键词的"人"相似度最大;)"捐献"与另一组中关键词的"服务"相似度最大春天"与另一组中关键词的"鸟"相似度最大;有部分结果不够合理,例如"捐献"与"人"、"器4.
2.
用户相似度结果分析用户关键"默默","张歆艺"}徐州"}似度理,其中3、4也有用户相似度结果不太合理的,原因主要是用4.
3.
用户聚类结果分析由于用户在进行搜索行为时,会主观根据某一词条搜开源软件包大联系,而后123456bc;d)"也官"与"人"的相似度都偏低,原因是"器官"、"捐献"只有单一概念解释,因此计算相似度时含义分析不够丰满.
这也从一个侧面反映了某些定义不合理或不一致之处,需要进一步改进.
词集合如下:1{"坚守","岗位",2{"魅力","非凡","四季","女装"}3{"北京","企业","信用","网络"}4{"江泽民","九寨沟","互联网"}5{"中国","邮政","储蓄"}6{"银行","中国矿业大学","由于此处计算的是用户间欧氏距离,距离与其相成反比,则没有绝对最大距离,只有当距离为0.
0是其相似度确定为1,其距离对比如表3.
可以得到:3、4用户相似度较高比较合用户都关心网络、地名;而1、5用户相似度较高则无理可循;同样含有地名"徐州"的用户6与用户3相似度也较高,他们还共同关心企业方面搜索内容,反观用户6与用户4的相似度就相对较低,虽然同样都包含地名,但两者间并无其他共性;用户2与所有其他用户的相似度中,与用户1距离最小也比较合理.
当然户的搜索关键词本身比较偏僻,导致计算词语相似度是已经不合理或者该用户的搜索关键词词频较低及该用户的搜索关键词在关键词集合中的权重较低.
索结果的满意程度决定下一搜索关键词的内容.
同时随着时间的推移社会热点的变动,搜索关键词的主流内容也会随之变动.
因此可以认为用户的搜索关键词与用户的兴趣[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.