领域查网速的网站

1国家自然科学基金(61271304)、北京市教委科技发展计划重点项目暨北京市自然科学基金B类重点项目(KZ201311232037)和北京市科学技术研究院创新工程(PXM2013-178215-000004)资助收稿日期:20140727;修回日期:201403;网络出版时间:北京大学学报(自然科学版)ActaScientiarumNaturaliumUniversitatisPekinensisdoi:10.
13209/j.
0479-8023.
2015.
047利用URL-Key进行查询分类李雪伟1吕学强1,董志安1刘克会2,31.
北京信息科技大学网络文化与数字传播北京市重点实验室,北京100101;2.
北京理工大学管理与经济学院,北京100081;3.
北京城市系统工程研究中心,北京100035;通信作者,E-mail:lxq@bistu.
edu.
cn摘要针对查询分类问题,借助互联网中人工组织的分类网站领域URL,利用URL-key在各个类别中使用的频度,提出基于方差的领域URL-key识别方法,利用机器翻译、拼音翻译和搜索结果反馈等技术对URL-key进行过滤,构建领域URL-key.
然后结合伪相关反馈技术,选取URL-key为特征,构建URL-key向量,利用SVM对查询串进行分类.
实验结果表明,该方法不仅F值比对比方法提高7%,而且资源的使用也远远小于对比方法,提高了系统的时效性.
关键词查询分类;URL;URL-key;伪相关反馈中图分类号TP391QueryClassificationbyUsingURL-KeyLIXuewei1,LXueqiang1,,DONGZhian1,LIUKehui2,31.
BeijingKeyLaboratoryofInternetCultureandDigitalDisseminationResearch,BeijingInformationScienceandTechnologyUniversity,Beijing100101;2.
SchoolofManagementandEconomics,BeijingInstituteofTechnology,Beijing100081;3.
BeijingResearchCenterofUrbanSystemsEngineering,Beijing100035;Correspondingauthor,E-mail:lxq@bistu.
edu.
cnAbstractFortheproblemofqueryclassification,avariancebasedmethodisproposedtoidentifydomainURL-keybyusingdomainURLorganizedmanuallyfromaggregatorsitesandtheusefrequencyofURL-keyineachcategory.
Then,theURL-keyisfilteredbyusingmachinetranslation,pinyinandsearchresultsfeedbacktechnology.
Finally,coupledwithrelevancefeedback,weclassifythequerybyselectingtheURL-keyasfeatureandestablishingtheURL-keyvectorwithaSVMmulti-classclassifier.
Experimentalresultsshowthatourmethodnotonlyuseslessresources,butalsotheF-valueis7%higherthancontrastmethod.
Keywordsqueryclassification;URL;URL-key;feedback随着社会的发展,搜索引擎已经成为人们生活的工具.
然而,搜索引擎反馈结果的准确性还不能满足人们的需求,因此需要对查询串分类进行研究.
查询分类是将用户提交的查询按照查询的意图分配到已定义好的类别中,对于用户输入的查询串,根据历史用户查询日志分类来推断当前查询的类别.
查询分类被广泛应用于搜索广告投放[1]、搜索结果改进[2]、用户行为分析[3]以及知识挖掘[4]等领域.
查询分类与文本分类的不同之处在于处理的对象不同,它处理的是用户输入的查询串,其主要特点有以下两方面:1)查询串比较短,通常4个字左右,缺少上下文语境;2)查询串容易出现歧义现象[3].
仅针对查询本身,传统的文本分类方法难以构造足够的特征,面临特征稀疏问题.
解决该问题的思路是,通过查询扩展,构建更丰富的查询特征[5].
例如利用搜索引擎返回的文档,从中抽取与查询共现的词汇扩展查询,构建更丰富的特征表示.
此类方法通常要对在线搜索结果进行复杂处理,由2014-11-2815:20网络出版地址:http://www.
cnki.
net/kcms/doi/10.
13209/j.
0479-8023.
2015.
047.
html北京大学学报(自然科学版)2表1URL分布Table1DistributionofURL领域URLEconomy15205IT5312Health2353Sports1502Travel1856Education7560Job276Art6162Military255Auto414此导致的延时将影响实际应用.
张宇等[6]提出基于URL匹配的查询分类方法,在一定程度上解决了查询分类的问题,但同时也存在不足,如时效性差、URL的收集困难等.
由于领域URL收集的数量有限,而互联网中网站的增长速度非常快,有限的领域URL无法满足爆炸式增长的网站,所以应该找到一个更好的方法来取代URL.
URL作为Internet上用来描述信息资源的字符串,主要由三部分组成:协议、域名和路径.
域名通常由两部分构成:域名主体和域名后缀.
例如,对于"match.
sports.
sina.
com.
cn"这个域名来说,"match.
sports.
sina"为该域名的主体词,"com.
cn"为该域名的后缀.
域名的主体词通常与信息资源的类别有关.
路径指信息资源具体存放的位置.
人们在构建路径时,为了方便信息资源归类,通常会考虑将不同的资源放在不同的路径下,且为路径起的名称与资源的主题相关,如football的路径下应该放与足球相关的信息资源.
通过上述对URL的分析发现,人们在申请域名或者创建路径时,通常会思考与信息资源的相关性.
虽然各网站的域名不同,但是相同主题下的域名主体词及路径引导词可能会相同.
通常,会集中使用一些领域性强的词语,如体育类中的"sport",经济类中的"finance",汽车类中的"auto",等等.
也就说,互联网中的域名主体词及路径引导词被赋予人们智慧的结晶.
本文将URL中含有类别信息的域名词主体词及路径引导词统称为URL-key.
本文放弃传统的搜索引擎结果文本扩展的方法,利用反馈的URL作为桥梁,利用URL-key类别来判断URL的类别,从而判断查询串的类别.
例如:用户输入的查询串为"凯美瑞",搜索引擎返回的URL={"http://www.
52car.
net/","http://www.
yicars.
com/",…},由于car在汽车类中容易出现,在其他类别中很难出现,所以很容易得出"凯美瑞"为汽车类的查询串.
本文根据URL-key在不同领域中使用的差异性,对文献[6]中收集的领域URL进行领域URL-key提取,构建领域URL-key词表.
然后,根据待分类的查询串反馈的URL结果集,构建领域URL-key向量,最终利用SVM对查询串进行分类.
1领域URL-key构建为了得到更多的领域URL-key,需要找到更多的领域URL.
在互联网中很多资源都凝聚了人类的群体智慧,如分类网站,通常是经过人工整理分类后呈现给用户的,具有很高的可信度.
张宇等[6]采集了Yaboo,Google和Baidu的中文分类网页目录,以Yahoo网页目录的前两层作为分类的标准,并将Google和Baidu网页目录全部映射到Yahoo的类别体系中,最终得到10类领域,40895个URL(表1).
文献[6]采用URL匹配的方法进行查询分类,而网络中存在着海量的URL,且每天都在不断的增长,因此使用URL匹配的方法已经不能满足当前的需要.
本文通过对文献[6]收集的URL进行分析发现,在构建URL时词语的使用存在差异性,分布不均衡,特定词语使用的频次较高.
例如:"sport"在体育类URL中大量出现,"car"在汽车类URL中大量出现,"finance"在金融类URL中大量出现.
因此,本文尝试用领域URL-key代替领域URL进行查询分类,这样不仅可以解决URL增长带来的问题,同时也可使用较少的资源,提升计算速度.
本文利用分割符T=对文献[6]收集的URL进行切分,构成一系列的字符串,删除长度为1的字串、纯数字串和一些无意义的特殊字符序列(如:http,www,com等),最终构建候选字符串集合为CandidatekeySet.
如http://www.
tennis.
com/player/539/na-li/经过切分后得到Candidatekey为tennis,player,na,li.
本文将从CandidatekeySet中提取领域URL-key.
根据Candidatekey在每个类别中分布的差异李雪伟等:利用URL-Key进行查询分类3性,本文提出基于方差的领域URL-key识别方法,并利用机器翻译、拼音翻译和搜索结果3种方法对领域URL-key进行过滤.
1.
1基于方差的领域URL-key提取李素建等[7]利用方差的思想实现领域术语的提取.
本文借鉴此思想解决领域URL-key的领域性问题.
本文利用Candidatekey在各个领域中使用差异性,衡量Candidatekey的领域性.
使用差异性越小则领域性低,反之则领域性越强.
首先,计算词语在不同领域中使用概率的总方差.
设共有N个词语,每个词语为Wi(02Var()jiijiPWRWWM,(1)()ijjijWPWW,(2)()()jijiPWRWM.
(3)在CandidatekeySet集合中,若某个Candidatekey使用概率差异性较大,则说明该Candidatekey可能为领域URL-key.
但是,该URL-key所属领域还需要进一步计算.
本文认为一个URL-key在其他类别中使用概率值小,而在特定类别中使用概率大,则该URL-key为该领域的领域URL-key.
为了得到领域URL-key的所属领域,本文主要从两方面进行考虑:1)URL-key的方差贡献度;2)URL-key在各领域中的使用情况,即URL-key的IDF(W).
1)方差贡献度:由于Var(Wi)的值是根据Wi在j中的使用概率来确定的,也就是说Wi在j领域中的Pj(Wi)越大,则对Var(Wi)贡献越大,因此词语Wi的方差贡献度为j()Con()()ijijijPWWPW.
(4)2)URL-key使用度:通常一个URL-key在其他领域中没有出现,只在某个特定领域中出现,则该URL-key的领域性强.
词语Wi的使用度为Use()log10jiLWM,(5)其中L为类别总个数,L=10;λ为平滑因子,λ=0.
001.
由上可知,某领域URL-key的方差值不仅受其方差贡献度影响,还受URL-key使用度影响,因此URL-key的领域度公式如下:Domain()=Var()Con()Use()jiijijiWWWW.
(6)1.
2领域URL-key过滤本文通过对领域URL-key的观察发现,URL-key多为一些领域常用的词汇,可明显地与其他类别词进行区分.
领域URL-key可以分为3类,如表2所示.
表2URL-key类型Table2URL-keytype类别实例英文单词或缩写sport,hospital,finance,nba,oly,…汉语拼音或缩写tiyu,rencai,junshi,caijing,ty,rc,…特殊网站域名zhibo,teixue,atohome,toyota由表2可知,人们一般会使用简单、方便、领域性强的词语来构建网站URL.
本文根据领域URL-key的类型特点提出以下3种过滤方式.
1)基于机器翻译的过滤.
从表2可知,领域URL-key中词语多为英文单词或缩写,将领域词串W放入Google翻译系统中,得到GW机器翻译.
如果W能被翻译,且G(W)有意义,则G为1,否则G为0.
1ifG()0otherwiseWG,机器翻译结果中,,.
(7)2)基于汉语拼音翻译的过滤.
从表2可知,领域URL-key中存在汉语拼音.
由于搜狗输入法占据市场的很大份额,同时也积累了很多汉语拼音书写的习惯,因此本文选择sogo翻译进行拼音翻译.
将G过滤后的无法翻译的W放入sogo翻译系统中,选择自动检测语言,得到WP拼音翻译.
如果W能被翻译,且P(W)有意义,则P为1,否则P为0.
1if()0otherwisePWP,拼音翻译结果中,,.
(9)3)基于搜索引擎的过滤.
将G和P过滤后无法翻译的词语放入sogo搜索引擎中搜索,得到北京大学学报(自然科学版)4WS搜索引擎.
如果W被检索,切top10中S(W)有意义,则S为1,否则S为0.
1iftop10(),0otherwiseSWS,搜索结果中,.
(9)根据Candidatekeyj的G,P,S值构建一个j领域的Rj矩阵,如式(10)所示,由Rj矩阵的值来判别Candidatekeyj是否为领域URL-key,如果Candidatekeyj的G∪P∪S=1,则Candidatekeyj为领域URL-key,最终构建URL-keySetj集合.
111j.
.
.
iiiiiiinininGPSGPSGPPR.
(10)2基于URL-key的查询分类本文在已构建的领域URL-key语料的基础上,利用搜索引擎伪反馈技术,得到相关的URL反馈信息.
然后,利用URL中各类别URL-key的分数来构建特征向量,最后利用SVM分类器判断查询串的类别.
伪相关反馈是假设搜索引擎系统查询反馈的搜索结果排名越靠前与查询越相关[8].
本文基于以上假设,构建待分类查询串query的URL-key特征向量.
首先利用T集合对伪反馈URL={URL1,URL2,…,URLl}进行切分,构建一个bagi={Candidatekeyi1,Candidatekeyi2,…,Candidatekeyij},目标类别为C={c1,c2,…,cn},其中l为搜索引擎返回的前l条结果,j为第i个URL切分后获取Candidatekey的个数,n为类别个数.
为了构建query的领域URL-key向量,需要计算query伪反馈URL结果中每一类的URL-key分数Score(cn|query).
本文利用式(11)计算query在各个类别中含有的个数.
由于反馈结果中排名越靠前,与查询串越相关,则反馈的URL与query的相关性与位置有一定的关系.
也就是说,URL中含有URL-key且其位置越靠前,Score(cn|query)越高.
本文将反馈结果的前10个查询结果看成权重相同的,后面结果随着排名的增加权重逐渐降低.
具体分布如式(12)所示.
n1ifurl-keyCount(Urlkey)0ifurl-keybagbag,中含有,中不含有.
(11)1(110),Pos()1(10)log(1)iiii.
(12)综上所述,查询串的Score(cn|query)与反馈结果中含有的领域URL-key有关,同时也与位置信息有关.
计算公式如下:1Score(|query)count(Urlkey)pos()lnici.
(13)根据每一类含有URL-key的分数值,最终构建出query的特征向量{Score(c1|query),Score(c2|query),…,Score(cn|query)}.
最后,利用SVM分类器对查询串进行分类.
3实验结果与分析3.
1实验数据本文使用的领域URL数据是文献[6]所收集整理的语料,分为10个类,共40895个URL.
为了与文献[6]进行对比,本实验中用到的实验语料与其相同,共2073个查询,分布如表3所示.
在每一个类查询串中选取20%作为测试语料,共计411条数据,其余80%作为训练语料,共计1662条数据.
测试查询串的分布如表4所示.
3.
2结果与分析3.
2.
1评价指标借用文本分类评价中采用的准确率(P)、召回率(R)、F值和精确率(A)进行评价.
100%aPab,(4)表3查询串分布Table3Distributionofquery领域查询串数量Economy217IT152Health248Sports187Travel240Education230Job101Art249Military200Auto249李雪伟等:利用URL-Key进行查询分类5表5部分领域URL-keyTable5ExamplesofURL-key领域URL-keySportsports,sport,nba,espnstar,pingpang,guojizuqiu,basketaball,snooker,soccer,tennis,badminton,olympics,olympic,tiyu,tiyv,ty,zhongchao,cbachina,weiqi,guoneizuqiu,sportsbl,chess,saichang,nba,wangqiu,cba,volleyballAutoauto,car,xcar,vw,toyota,chinacars,dongfeng,nissan,vehicles,audi,bitauto,new_cars,chery,newcar,peugeot,webcars,qiche,autohome,cheEconomystock,bond,eastmoney,soufun,forex,ccb,cmbchina,stockstar,icbc,invest,boc,insurance,money表4测试查询串分布Table4Distributionoftestquery领域查询串数量Economy43IT30Health49Sports37Travel48Education46Job20Art49Military40Auto49100%aRac,(5)2100%PRFPR,(6)A正确分类的查询数总查询数.
(7)对于类别C,分类的结果可分为以下几种情况.
1)原本为C类被划分为C类,数量记为a.
2)原本为非C类被划分为C类,数量记为b.
3)原本为C类被划分为非C类,数量记为c.
3.
2.
2结果分析通过对领域URL的切分,利用方差计算公式计算每一个候选领域URL-key的领域度,再根据领域度的大小进行排序,取top100作为候选领域URL-key,结果如表5所示.
通过对领域URL-key的观察,发现领域URL-key主要有以下特点:1)由英文单词或缩写组成,大约占总URL-key的35%,如sport,auto,car,bond,nba,vw等;2)为汉语拼音或缩写,大约占总URL-key的26%,如tiyu,che,ccb,icbc等;3)为特殊网站域名,大约占总URL-key的14%,如autohome,zhibo等.
本文根据领域URL-key的上述特点,利用机器翻译技术、拼音翻译技术和搜索技术构建R矩阵.
遍历R矩阵,若R矩阵中Rj的G,P,S的值都为零,则过滤此候选URL-key.
最终得到717个领域URL-key,分布如表6所示.
本文利用Query伪反馈的领域URL-key分数构建特征向量,使用SVM对查询串进行分类.
图1展示URL数目变化时P,R,F,A的表现,也就是含有URL-key数目的变化.
从图1可以看出,随着URL数目增加P,R,F总体上呈现先下降再上升的趋势.
当URL个数为100时,实验结果最好.
分析其原因为:搜索引擎返回的结果排名越靠前与查询串越相关,但随着URL数量的增加会受到一定的噪音影响.
实验结果随URL个数的增加呈现下降的趋势,当URL数量为50个的时候P,R,F值最低,主要是因为增加的搜索结果与查询串的主题表6领域URL-key数量分布Table6DistributionofdomainURL-key领域URL-key数量Economy72IT85Health74Sports69Travel76Education72Job87Art53Military55Auto74北京大学学报(自然科学版)6图1实验结果随URL数目的变化Fig.
1PerformanceofexperimentresultswithdifferentnumberofURL表7实验结果Table7Experimentalresult方法P/%R/%F/%A/%本文87.
3587.
5687.
4588.
07文献[6]82.
8478.
8380.
7882.
26无关.
由此猜想,搜索引擎在第3~5页时检索的结果与查询串的主题相关性可能比较小.
但是,当URL大于50个时,随着URL个数的增加,P,R,F值呈增加的趋势.
当URL达到100个时结果最好,且随着URL的增加趋于平稳状态.
这是因为随着URL的增长,可被分类的URL-key数量增多,可以利用的资源更多,结果更好.
但是用较大数目的URL有可能引入非相关文档,增加匹配时间,损害分类的效果.
表7给出本文方法与文献[6]方法的对比,均使用前100条URL作为实验语料.
实验结果表明,本文的方法要好于对比方法,准确率为87.
35%,召回率为87.
56%,F值为87.
45%,F值提高近7%,精确率提高近6%.
这是由于文献[6]采用的是基于URL匹配的方法,搜索结果反馈的URL中不能准确地与人工收集的URL进行完全的匹配.
据统计,每返回100条URL时,有大约20%的URL能够进行URL匹配,大约40%的URL能够进行领域URL-key匹配.
本文使用的基于领域URL-key的方法可以解决这个问题.
本文不仅在实验结果上好于对比实验,而且使用的资源较少.
本文只使用717个URL-key进行匹配,而文献[6]使用40895个URL进行循环剪枝匹配,大大影响了实验的时间效率.
表8给出本文方法在不同类别中的各个指标参数,可以看出,对于健康类、旅游类、军事类和汽车类,本文方法取得较好的准确率和召回率,这是由于搜索引擎反馈的结果与主题查询比较明确.
然而对于IT类,取得了较好的召回率,但准确率相对比较差.
对实验结果分析发现,一些娱乐类的查询串被误分到IT类.
分析其原因,娱乐查询中主要是小说查询,在返回的结果中含有"下载"的链接较多,而"下载"为IT类的URL-key,所以IT类中娱乐类的数据会较多.
此外,还有一些查询串本身就可以被分到多个类别中,如"j10"被标注为军事类,实际上被分配到IT类.
对于教育类和求职类的查询串,搜索引擎反馈结果的类别URL-key不好区分,经常被相互误分,所以准确率、召回率都比较低.
表8SVM分类结果Table8ResultofclassificationbySVM领域PRFEconomy0.
8695650.
9302330.
898876IT0.
7435900.
9666670.
840580Health0.
9574470.
9183670.
937500Sports0.
9393940.
8378380.
885714Travel0.
9361700.
9166670.
926316Education0.
8260870.
8260870.
826087Job0.
7142860.
7500000.
731707Art0.
8200000.
8367350.
828283Military0.
9722220.
8750000.
921053Auto0.
9565220.
8979590.
926316平均值0.
8735280.
8755550.
8745414总结本文利用互联网中凝聚人们智慧的URL为资源,提取领域URL-key,首次提出利用领域URL-key进行查询分类的方法,有效地解决了由网站爆炸式增长带来的领域URL不匹配问题,同时也解决了人工收集领域URL带来的时间效率问题.
首先利用方差提取领域候选URL-key,再利用机器翻李雪伟等:利用URL-Key进行查询分类7译技术、拼音翻译技术和搜索反馈技术对领域URL-key进行过滤,构建领域URL-key词表.
利用伪相关反馈技术,构建query各个类别的URL-key得分向量,使用SVM对query进行分类,最终得到查询串的类别.
本文方法的准确率达到87.
35%,F值为87.
45%,在一定的程度上解决了部分查询分类的问题,为查询分类提供了新的思路.
本文提出的方法仍有需要改进的地方,例如:领域URL-key的构建应该更加精确,分类应该更细化.
这些将在未来工作中进一步研究.
参考文献[1]BroderAZ,FontouraM,GabrilovichE,etal.
Robustclassificationofrarequeriesusingwebknowledge//Proceedingsofthe30thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.
NewYork:ACM,2007:231238[2]WangX,ZhaiCX.
Learnfromwebsearchlogstoorganizesearchresults//Proceedingsofthe30thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.
NewYork:ACM,2007:8794[3]董志安,吕学强.
基于百度搜索日志的用户行为分析.
计算机应用与软件,2013,30(7):1720[4][TanevaB,ChengT,ChakrabartiK,etal.
Miningacronymexpansionsandtheirmeaningsusingqueryclicklog//Proceedingsofthe22ndInternationalConferenceonWorldWideWeb.
Geneva:InternationalWorldWideWebConferencesSteeringCommittee,2013:12611272[5]ShenD,PanR,SunJT,etal.
Queryenrichmentforweb-queryclassification.
ACMTransactionsonInformationSystems(TOIS),2006,24(3):320352[6]张宇,宋巍,刘挺,等.
基于URL主题的查询分类方法.
计算机研究与发展,2012,49(6):12981305[7]李素建,宋涛,高杰,等.
一种基于使用差异的词语领域性分析方法.
中文信息学报,2009,23(6):7278[8]YuS,CaiD,WenJR,etal.
Improvingpseudo-relevancefeedbackinwebinformationretrievalusingwebpagesegmentation//Proceedingsofthe12thInternationalConferenceonWorldWideWeb.
NewYork:ACM,2003:1118