算法蜘蛛搜索引擎

第32卷第3期计算机应用与软件Vol32No.
32015年3月ComputerApplicationsandSoftwareMar.
2015面向城市交通信息的垂直搜索引擎的设计与实现袁萌1,2李景文1,2胡泊11(桂林理工大学测绘地理信息学院广西桂林541004)2(广西空间信息与测绘重点实验室广西桂林541004)收稿日期:2013-09-23.
广西自然科学基金重点项目(2011GXNSFD018003).
袁萌,硕士生,主研领域:GIS理论和应用.
李景文,教授.
胡泊,硕士生.
摘要针对当前网络中城市交通信息以几何形式递增的趋势,研究面向城市交通信息垂直搜索引擎的设计与实现技术,提出改进的基于Nutch搜索引擎技术与Google地图服务相结合的方法,设计主题信息抓取、中文分词、主题相关性判断、构建索引等检索功能模块,以Web地图服务为平台,完成主题交通的搜索与分析服务.
实验结果表明,相对于其他通用搜索引擎面向城市交通信息的垂直搜索引擎更具有主题优势,在交通特征领域爬行深度和覆盖范围都得到加强,改进的算法能够有效提取高质量的网页文档,同时,在交通信息定位和主题排序方面也更为精确.
关键词垂直搜索引擎NutchGoogle地图服务城市交通信息中图分类号TP393文献标识码ADOI:10.
3969/j.
issn.
1000386x.
2015.
03.
072DESIGNANDIMPLEMENTATIONOFURBANTRAFFICINFORMATIONORIENTEDVERTICALSEARCHENGINEYuanMeng1,2LiJingwen1,2HuBo11(CollegeofGeomaticEngineeringandGeoinformatics,GuilinUniversityofTechnology,Guilin541004,Guangxi,China)2(GuangxiKeyLaboratoryofSpatialInformationandGeomatics,GuilinUniversityofTechnology,Guilin541004,Guangxi,China)AbstractAimingatthetrendthaturbantrafficinformationprogressivelyincreasesingeometricalformincurrentnetwork,weresearchthedesignandimplementationtechnologiesinregardtourbantrafficinformationorientedverticalsearchengine,andpresenttheimprovedmethodwhichisbasedonthecombinationofNutchsearchenginetechnologyandGooglemapsservices.
Wedesigntheretrievalfunctionmodulesincludingtopicinformationgrab,Chinesewordsegmentation,topicrelevancejudgment,andindexconstruction,etc.
ThemethodtakesWebmapservicesastheplatform,completesthesearchandanalysisservicesofthemetraffics.
Experimentalresultsdemonstratethatrelativetoothergeneralsearchengines,theurbantrafficinformationorientedverticalsearchengineismoredominantinthemes.
Intrafficfeaturefielditscrawlingdepthandcoveragerangeareallenhanced.
Theimprovedalgorithmcaneffectivelyextracthighqualitywebpagefilesaswell.
Meanwhileitisalsomoreaccurateinpositioningthetrafficinformationandthemessorting.
KeywordsVerticalsearchengineNutchGooglemapsserviceUrbantrafficinformation0引言"智慧城市"是当前城市发展的前沿热点,瑞典为了减缓城市交通堵塞状况,设计了"智慧交通";在国内,随着数字化城市发展的推进,互联网中城市交通信息呈现爆炸式增长的趋势[1],因此,城市交通业对主题检索服务的需求日益增长.
在搜索引擎发展的阶段中,不断有学者提出新的思路和技术方法,根据搜索引擎在信息获取范围和提供的检索方式的进化中将搜索引擎分为以下几种:目录式搜索引擎、通用搜索引擎、元搜索引擎以及垂直搜索引擎也称为主题搜索引擎.
主题搜索引擎因其应用于特定行业和专业领域,更符合当今信息时代多元化的需求,例如:NorthCarolina大学开发的面向法学信息的垂直搜索引擎LIBClientIRISWeb,利用普通语句对互联网上的法律数据进行全文检索,通过缩小蜘蛛爬取范围、加深爬取深度,使得用户在获取高质量的法律咨询时主题搜索引擎可以提供有效的帮助[1].
Google、Baidu等通用搜索引擎虽然支持城市交通信息的查询,但微软亚洲研究院的专家坦言:使用通用搜索引擎75%的网页内容检索不到,这主要是由于主题信息资源广、更新快,爬行程序搜索不准确、查询深度不够,所以加快对面向城市交通信息的垂直搜索引擎的研究是迫在眉睫的.
众所周知,交通信息离不开地图的支撑,在Web地图服务中,用户可以准确地找出所需交通所在位置以及周边地物空间位置关系.
因此,如何快速有效地检索到用户所需的城市交通主题信息,并依托Web地图平台提供快捷、高质量的搜索平台成为一个具有重要现实意义的研究问题.
本文以"Google地图"为索引平台交互性服务界面,结合面向城市交通主题信息的垂直搜索引擎技术,利用改进过的Nutch搜索引擎,完成对信息的爬取和中文分词,通过筛选主题第3期袁萌等:面向城市交通信息的垂直搜索引擎的设计与实现307相关度较高的交通信息,建立和优化索引.
在数据结构组织上构建主题数据与地理数据的映射关系,从而提供给用户有效、便捷的Web地图检索服务.
1整体结构设计面向城市交通信息主题搜索引擎采用主流的B/S架构,以减少模块间的耦合性,提高系统适用性,整体架构设计主要分为3层:客户层、Web服务器层、数据层(如图1所示).
将网络中的城市交通Web站点数据与搜索模块以服务的形式进行接口配置和封装,检索服务构成了主题搜索引擎的核心.
图1整体结构设计图2主题搜索引擎的关键技术2.
1信息的爬取与分词2.
1.
1爬取过程随着Web技术的发展,城市中交通信息以几何形式递增,如何从广域数据中提取相关度高的数据,从而在根源上减少采集信息时产生的"噪音".
Nutch是一个基于Lucene实现分布式云计算的Web搜索引擎,主要完成城市中交通领域Web站点网页抓取和索引的编制(如图2所示).
在模拟Linux的Cygwin运行下,通过网络蜘蛛爬行城市交通预指定的URL种子集,爬行工作开始后,垂直搜索引擎通常有3种常用的方法控制抓取的相关性和质量:①基于BFS(BreadthFirstSearch)spider机制的限制蜘蛛只抓取特定网站内容信息;②基于PageRankspider机制,通过限定网页重要性的阈值,过滤收集到的页面;③基于HopfieldNetspider机制,将Web视为一个神经网络,每个网页即为神经元[2].
由于需要处理大量交通信息页面,选择BFSspider机制预指定URL集,以深度优先的原则对Web站点进行跟踪.
图2Nutch爬行工作流程图2.
1.
2中文分词针对我国城市交通信息中绝大部分为中文表达,若采用Nutch标配的StandardAnalyzer单字切分分词组件,则不能表达中文词组的含义,并且多次分词严重影响效率,例如对"桂林的主要高速公路有桂柳高速公路和两江国际机场高速公路.
"进行分析,结果为"桂/n林/n的/n主/n要/n高/n速/n公/n路/n有/n桂/n柳/n高/n速/n公/n路/n和/n两/n江/n国/n际/n机/n场/n高/n速/n公/n路/n.
".
因此本研究在NutchDocumentAnalyzer分词接口的基础上进行修改,添加了以ICTCLAS为核心的汉语词法分词组件,该组件能够完成中文分词、词性标注、词语识别等功能,分词正确率高达97.
58%[3],经过测试对相同语句的分词结果如图3所示,分词结果语言表达较为准确.
ICTCLAS组件采用多层隐马模型可以对文章进行准确的切分,同时,结合Nutch开源机制具有良好的扩展性.
图3测试结果图2.
1.
3主题相关性判断为了提高对信息的处理效率,采用对页面进行分块解析,将网页中的每一份文档视为相互独立的n维特征属性向量T=(t1,t2,…,tn),利用向量空间模型算法来判断主题相关度较高的网页文档[4].
一般网页P主要按照P={DT,DL,DN}的形式进行划分,其中DT为主题文档块;DL为链接块,主要包含导航锚文本和噪音锚文本;DN为噪音块,主要为广告信息.
通过对不同文本块设定权重w,得到该页面的总体主题相关度RP,UT为文档对当前页面P的一种抽象概括,若UT属于噪音文本块,则RP赋值为0,反之,则RP的值取决于RDT、RDL与其对应的权值因子乘积的求和(如式(1)所示).
Rp=w1·RDT+w2·RDLUTDN0UT∈D{N(1)通过引入向量空间模型,将n维向量文档与查询词Q的匹配问题转换为空间矢量的匹配,以矢量间的夹角余弦cosθ表示主题相关度结果,其算法过程(如式(2)所示),式中sim(d,Q)为主题文本块与链接块向量vT分别与查询向量vQ的余弦值,由于文档为多维向量组成,则利用求和法则,依次累计.
按照主题相关度对爬取的网页文档依次排序,保留分值较高的文档,反之,丢弃相关度值低的页面[5].
sim(d,Q)=cosθ=∑ni=1vT·vQvT*vQ=∑ni=1v(T·Q)∑ni=1vT2*∑ni=1vQ槡2(2)2.
2索引的建立通过Nutch搜索引擎机制对预先指定的城市交通Web站点进行爬取,为了更好地提取高质量的主题文档,设定爬取深度N,过滤噪音干扰率较高的URL链接[10].
调用改进Nutch中的Analyzer分析模块,配置ICTCLAS中文分词组件接口,深度读取爬取文档,利用基于分块的空间向量模型计算各主题文档的相关度.
由于本文研究的垂直搜索引擎是依托于Web地图服务,在Google地图上准确显示用户所需交通地物的位置,取决于该地308计算机应用与软件2015年物实体的经纬度坐标的精确程度和周围地物的空间对应关系.
利用YahooGeoPlanetAPI从GeoPlanet服务器获取地理信息编码,例如组建桂林市县主要交通的地理本体,包括ID、市县级重要地物的地名、邮政编码、中心点经纬度坐标、地物层次关系等信,将爬取到的主题文档信息以最长字符匹配法的原则同地物名称进行相关性计算,返回相关度高的地理本体对应的地理知识库信息,按文档主题信息、地理主题信息按照指定的Field字段存储,完成索引源数据库构建工作.
基于城市交通信息的索引源数据库中需要组织主题特征、时空特征与位置特征的映射关系[8],通过唯一的ID标识将3种特征属性进行封装,构建一个相互共存的四元组Tetrad={ID,TC,SC,LC}(如图4所示).
其中TC为城市交通主题信息,主要包括交通等级、类别、主题等信息;SC为时间关联和空间关联等关系信息;LC为位置坐标信息,以便在地图服务中展示其所在位置,四组特征属性并不是独立存在的,而是相互依存的.
图4数据组织结构图3城市交通信息主题搜索引擎的实现3.
1基于Google地图服务的交互界面Google地图是2005年由美国谷歌公司自主建设的覆盖全球的地理信息综合服务平台,作为集计算机图形学、空间拓扑关系和数据挖掘于一体的分析空间实体对象的尖端技术[6].
通过JavaScript脚本调用其API接口,实现了地图的显示、地图控件的使用、街道地图和卫星地图的转换、指定区域信息查询以及悬浮框信息弹出等功能,并结合Lucene的检索功能完成客户端的请求和响应工作.
在Google地图这一公共地理信息平台上搭建基于城市交通信息的智能检索,并对检索结果进行按主题相关性排序,为用户提供更高质更便捷的主题服务(平台界面如图5所示).
图5引擎平台界面3.
2检索结果集排序及显示针对城市交通信息广、覆盖领域面大,检索结果集量大且无规则的特点[7],从而需要对结果集进行相关性主题排序.
Web服务器端通过Http协议接收到客户端的请求字符串,调用基于Lucene实现的开源搜索引擎,构建检索关键字字符串后将进行分析处理,并将结果集存入Hits集合[9].
为了将相关度较高的信息链接置于顶端,从而方便用户获取高质量的信息,使用Sort类指定排序方式和排序字段,该引擎采用Lucene默认的相关性降序排序,满足高质量文档置于前段的条件,而对于Hits结果集中各文档主题相关度的分值评判,则依靠基于向量空间模型的分值排序算法函数Score(query,d)(如式(3)所示).
若搜索"桂林市主要道路",排序结果和部分向量因子见表1所示,式中文档检索词使用的频率tf(t)越高,则其辨别力越强,权值也越高;boost(t)即为文档重要性权值;lengthNorm(t)表示检索词长度与文档的长度比,若长度所占比例越大,则分值就越高.
Score(q,d)=coord(q,d)*queryNorm(q)*(∑tinqtf(tind)*idf(t)*boost(t.
fieldind)*lengthNorm(t.
fieldind))(3)表1部分影响因素及排序结果检索词结果集Tf((t)LengthNom(t)总分桂林市主要道路包茂高速公路3.
4510320.
0468520.
352146解放东路2.
76201520.
06246930.
271635中山中路1.
26432530.
0468520.
246349…………城市交通信息搜索引擎左侧主题面板将显示已排序的检索信息,右侧地图面板通过加载Google地图服务完成交通实体对象的基于经纬度坐标信息的显示,并利用点击事件可在地图悬浮框查看该对象的详细信息,ID为四元组实体对象的唯一标识,也是连接主题面板与地图面板的桥梁,检索结果界面见图6所示.
图6检索结果界面4结语基于Nutch的面向主题的垂直搜索引擎提供了深度抓取Web网页的接口,能够较好地实现按主题相关度分块计算网页文档的主题相关度,而Google地图服务平台具有良好的地理实体显示功能,但是二者缺乏相应的组织关系.
本文研究了利用面向实体对象的四元组数据组织方法实现搜索引擎中的主题特征与地图服务中的位置特征的交互连接,设计了改进的基于Nutch的中文分词和向量空间模型计算主题相关度的处理方法,解决了互联网中面向海量城市交通信息按主题相关度检索及优化的问题,如何改进客户端多功能服务,提高海量数据存储及检索的算法效率将成为下一步的研究重点.
(下转第320页)320计算机应用与软件2015年图6各算法在ETHZ数据集序列2上的累积匹配特性曲线从图5、图6可以看出,n=1时,本文算法的识别率低于RLPP算法,但是,当n≥2时,本文算法的识别率高于其他各个算法,从图中可以看出,与LogESR算法相比,本文算法的识别率明显高出了很多.
3.
4性能比较最后,比较了本文算法与其他几种算法在三个数据集上训练和分类所需的平均总完成时间,比较结果如表3所示.
表3各算法在三个数据集上的平均总完成时间(秒)算法BrodatzFERETETHZLogESR0.
96972.
321904.
43RLPP2.
842343.
924231.
09HPE2.
922494.
304694.
58SDALF1.
591392.
683095.
49TSC1.
951620.
05—本文算法0.
49417.
68921.
31从表3可以看出,本文算法的总完成时间比其他各个算法都少很多,RLPP、HPE算法的总完成时间甚至是本文算法的5至6倍,在几种比较算法中,LogESR的总完成时间最少,尽管如此,却也是本文算法的2倍,由此可见本文算法的高效性.
分析原因可知,本文算法通过将黎曼流形嵌入到欧氏空间,无需像传统的算法那样再生核Hilbert空间,故可以节省大量的时间.
4结语为了简化这种黎曼流形的处理,传统的算法通常将流形嵌入更高维欧氏空间,然而,嵌入流形只考虑切线空间却忽略了流形结构以致不准确的建模.
基于此,提出了一种基于关系型发散的黎曼流形分类算法,通过在流形上建立表示黎曼点的一组参考点,借助于最近提出的斯坦因发散,有效地将流形分类问题转换成了找合适的相似空间问题,从而可以通过传统的特征提取方法解决.
通过纹理分类、人脸识别、人体识别实验验证了本文算法的有效性及高效性,相比其他几种较为先进的算法,提出的算法不仅具有较高的识别率,而且大大降低了计算开销.
本文算法使用所有训练样本作为参考点,虽然很有效,但可能会受到外界影响,此外,由于类的实例很多,这种算法可能不具有可扩展性.
因此,创建类的替代算法将是未来的研究重点,例如直接在流形上聚类.
参考文献[1]程丹,杨钦,李吉刚,等.
二维黎曼流形的Voronoi图生成算法[J].
软件学报,2009,20(9):24072416.
[2]陈绍荣,王宏强,黎湘,等.
一种新的黎曼流形学习方法[J].
南京大学学报:自然科学版,2012,23(1):107113.
[3]刘佳,陈纯,叶承羲,等.
基于协方差描述子和黎曼流形的语音情感识别[J].
模式识别与人工智能,2009,22(5):673677.
[4]陆亚哲.
正曲率黎曼流形拓扑结构的研究[D].
西南交通大学,2012.
[5]刘雅萍.
基于未知信号先验知识的精确重构[D].
哈尔滨工业大学,2011.
[6]YuanC,HuW,LiX,etal.
Humanactionrecognitionunderlogeuclideanriemannianmetric[M]//ComputerVisionACCV2009.
SpringerBerlinHeidelberg,2010:343353.
[7]周春光,孙明芳,王盨菁,等.
基于稀疏张量的人脸图像特征提取[J].
吉林大学学报:工学版,2012,42(6):15211526.
[8]李广伟,刘云鹏,尹健,等.
基于黎曼二阶最小化的投影图像配准算法[J].
仪器仪表学报,2010,32(6):13231329.
[9]BazzaniL,CristaniM,PerinaA,etal.
Multipleshotpersonreidentificationbyhpesignature[C]//PatternRecognition(ICPR),201020thInternationalConferenceon.
IEEE,2010:14131416.
[10]FarenzenaM,BazzaniL,PerinaA,etal.
Personreidentificationbysymmetrydrivenaccumulationoflocalfeatures[C]//ComputerVisionandPatternRecognition(CVPR),2010IEEEConferenceon.
IEEE,2010:23602367.
[11]付风云.
半(次)黎曼流形上的共形和射影映射的几何不变性研究[D].
南京理工大学,2012.
[12]石磊.
基于数据的学习:埃尔米特算法与黎曼流形上的法向量估计[D].
中国科学技术大学,2010.
[13]SraS.
PositivedefinitematricesandthesymmetricSteindivergence[J].
arXivpreprintarXiv:1110.
1773,2011.
[14]RavivD,BronsteinAM,BronsteinMM,etal.
Affineinvariantgeodesicgeometryofdeformable3Dshapes[J].
Computers&Graphics,2011,35(3):692697.
[15]张俊.
基于局部特征集合的图像匹配技术研究与应用[D].
浙江大学,2011.
(上接第308页)参考文献[1]陈竹敏.
面向垂直搜索引擎的主题爬行技术研究[D].
山东:山东大学,2008.
[2]王晔.
垂直搜索引擎若干问题研究[D].
上海:复旦大学,2012.
[3]张思发,马永格.
面向地学信息领域垂直搜索引擎设计与实现[J].
计算机工程与应用,2012,48(33):8588.
[4]赵珂,逯鹏,李永强.
基于Lucene的搜索引擎设计与实现[J].
计算机工程,2011,37(16):3941.
[5]赵德平,刘阳,李鹏.
基于Lucene的房产信息垂直搜索引擎的研究[J].
沈阳建筑大学学报,2011,27(1):179183.
[6]李景文,邹文娟,田丽亚,等.
基于过程的面向对象时空数据模型数据组织方法[J].
测绘科学,2013,38(5):100102.
[7]时延军.
基于Nutch的分布式搜索引擎的设计与研究[D].
长春理工大学,2010.
[8]贺财平,覃事刚,刘建勋.
Web服务搜索引擎的设计与实现[J].
计算机应用与软件,2011,28(1):4446.
[9]王锡钢,王正,陈虎.
关于搜索引擎的中文分词与页面排序的研究[J].
计算机应用与软件,2013,30(9):211214.
[10]邵星星.
基于Lucene的中文分词技术研究[D].
西安:西安电子科技大学,2012.