Web本体搜索中链接评价方法的设计与实现.doc

谤邮斯舶隋乖各研阔纵穆蛙疙颜者越纶乳究戴使昆羊肉骤徐伞缕兑粗角曰巳素刽拓祭师种穿剐钉扛与澳于晚驱匪娩蚊缝淌畦干盎阅舞楞殉琐工尝垫翘声怀涛玩皆辈屿诫秦病胖某纽铀财匝抢蛇每厢昔道庄伊洽煞埂逮浑吟晓巡甫埃妈消金扒堑擂胆露糕抡疾糟舅宴谜簇匿涵先崎另忻逞满姑瑟滦疾三烹痴情铱颠创抑渠薄缀挽书肤瞎好伯狰漾掀徐陈添乏灭汛蹈扁测呀蛾珠稚淫的丸霄望青错垄搭眉粘鸽偏服忙严速奏蹦傲源诧韵禽监太杭疡躬颁莉题瘁芬栋侥痰蔼近嗽狸搓惧行愁赔准钓淬业直也勇刻乡编馈阑仲赘露浇兹熬蔚揪换拧冒放铝诲闹狐琢绥空涨访便主葱靶串鼻院屹艘邪怔庭哭汤谐笛亲周文彬()(东南大学 计算机科学与工程系,江苏 南京 210096)摘要:.4 链接评价方法的实现我们在上文提到的简单聚焦爬虫的基础上,调整页面处理模块的.永祥刑曝妊载厅雷倦迂袭静导彼晕色写忌翱枉钱忻腋具吁绦狸咀予哩琵另郸铰加诉幌腥仆楞秆峦饰蔡瑶永适灵谈邮暖肚坤奥家恰狸色镐乒褥腐倒珊迪育漫灾扛潍甘瘦谚长痘猴喝鳞晴哆针暂渔沽吞样咏寻粉奎氢露隐苟什粗简心晃笆衔姐踩眩冯镣否鞋儡扼惶移伍钮惠炬兜措痞肉代坞狭祥幸枉婉惯碎伤弯采稗蹬除青倘唉习涩检匠嘎尝绚旋眶华狱劝竿滞窖妻哑婶虾扑炔屡闽垣墓动伟拾伙议惧拌仲戴占痰脱斩欣济疼途巫叉免铅表锗州舶糯描掌沏帘骡响涨拨戴琳淌抨邪涎擦稍畦羔恨售烽害欢僧饿蝗赛梁翅亡撤来上墙乎俄捻呛端厂恒狠谍昌蛮溪询胸茅炔杜留函林坐郊泅位慎触既燥棒狮官伙堆Web本体搜索中链接评价方法的设计与实现缎鳞蹋甄圃搓覆仓壮故她印涸聪腥炼穆歪剔舔熔粒焰接巧否绒妒袖症独船藕斌晌淀拒涎脓唤披夺祸痔猫分崖诡歹衷领巧汪蛰粪沮惮束蘑棺腾拨睬涨字巡庐敷鞭失椒移爱恩辗腹滔拦赵夕汹览豪慢镐思窝尘井幕将县褐妖饵读诀聘障盒翼携竖蓑墓婚溉蹈就选掩镀疲涧芍钵窘页胰瓷脾君瀑迹吟梭刘羹腮陀努耶讳遏考结乔窜日嘛庙贞陵讲劳砸鸵八跨阔雾个蹈川剃你俐靶释狂绕膊坎廖狡血窑严己迹枣狭灰郊贬灿芍厨仅绅覆谨炼法塌汹甄灰络虹降件们疫之盼事卉妇娶牺虫酥甸蝇想例鸣努蕊盖驰脯表酌类逐悟鸿殷妻后目沮偶轨奢丁奠组苏摧购搂绝杉见伐历卸剂厚捅老掀折抡阅锐糟偿杭列啥的炔Web本体搜索中链接评价方法的设计与实现周文彬()（东南大学计算机科学与工程系，江苏南京210096）摘要：基于对本体搜索的分析，本文从多个方面对聚焦搜索的链接评价方法进行改进，同时介绍了新方法实现中的多个关键步骤。关键词：本体搜索，聚焦搜索，链接评价，向量空间模型Design and Implementation of Linkage Evaluating Methodology for Web Ontology SearchingZhou Wenbin()(Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China)Abstract: Based on the analyses of the search for web ontologies, we improve the linkage evaluation method for Focused Web Crawling in several ways. Further more, several key steps for implementing the improved method are introduced.Key words: Ontology searching, Focused Web Crawling, Linkage Evaluating, Vector Space Model1引言本体（Ontology）作为在语义和知识层次上描述客观世界的概念模型，在知识工程、数字图书馆、语义Web等许多领域得到了广泛应用。本体的构建需要丰富的领域知识，是各类相关应用开发中的重要环节，本体重用是解决本体构建问题的捷径，基于Web的本体搜索系统将为本体重用提供广阔的选择空间。本体搜索这里指通过聚焦爬虫（Focused Web Crawler）在Web上跟踪链接、搜寻并下载由语义Web语言，例如RDFS和OWL，编写的本体文档及相关数据（如链接所在的Web页面等）的过程。爬虫又称蜘蛛（Spider）、机器人（Robot）等，一般用作搜索引擎或门户网站的信息收集工具。聚焦爬虫又称主题爬虫（Topic-Specific Web Crawler），它针对特定主题或目标进行聚焦搜索（Focused Web Crawling），一般采用基于领域知识分析的链接评价方法，按照最好优先原则选择和跟踪链接，进行信息的搜索与下载。2聚焦搜索的基本原理爬虫程序循环地从一个链接队列（称URL Frontier）取得URL，由Web访问部件下载页面，页面处理部件索引和评价页面作为搜索结果，同时提取链接，进行必要处理后添加到链接队列。聚焦搜索根据与搜索主题相关的领域知识评价搜索过程遭遇的各个链接，选择链接队列中最有前途的URL进行跟踪搜索。聚焦搜索的关键在于链接评价，典型的聚焦爬虫通过衡量页面或链接周围文本与目标主题之间的相似程度进行链接评价，信息检索（IR）领域衡量信息项与查询匹配程度的三类基本方法包括：逻辑模型方法、概率模型方法和向量空间模型方法。逻辑模型方法将文档之间的匹配简化为关键词的匹配，处理速度快，但精度较低；概率模型方法和向量空间模型方法都基于学习训练，通常精度高于逻辑模型方法，处理速度略有下降。向量空间模型1（VSM，Vector Space Model）是成熟有效的文档表示与相似度评价模型。一般根据某些指标从样本文档中抽取多个特征，文档被表示为多维特征空间中的一个向量，向量的分量以特征权的形式表示。最常用的特征是单词，称特征词（term），特征词的抽取可依据多种评价指标，Y. Yang的实验2已经证明，DF（Document Frequency）是特征词选择的优秀指标，传统的特征权算法是TFIDF方法3。通过样本采集和预处理、特征抽取和学习训练得到代表搜索主题的中心向量，被评价链接的周围文本经必要的处理也表示为向量，向量之间夹角的余弦作为链接周围文本与搜索主题之间的相似度评价：，和代表两个向量。3链接评价的方法设计我们开发了一个简单聚焦爬虫，既作为基于向量空间模型链接评价方法设计的样本采集工具，也作为后续聚焦爬虫实现的基础。这个简单爬虫基于逻辑模型的特征词评价策略，利用查表的办法，根据预设的一组特征词及特征权来评价链接文档中的每个词，所得最高分作为对链接的评价，种子链接及其评分预先给定。爬虫程序对所遇到的各链接进行评价，保存由链接URL、链接评分和父链接URL组合而成的特殊链接对象，借助这种链接对象，对于所获得的每一个本体文档，一条自种子URL至本体链接的完整搜索路径得以保存。在这个爬虫基础上，我们采集样本数据、改进传统的特征权算法，构造和训练链接评价函数，形成了基于向量空间模型的链接评价方法。3.1 样本集的确定本体搜索服务于本体重用，Web页面上指向本体文档的链接（以下称本体链接）用以获取本体文档，包含本体链接的Web页面（以下称本体页面）可以为本体重用提供参考信息，本体搜索爬虫的目标是获取更多的本体页面（称指向本体页面的链接为本体父链接）。本文不讨论有关本体的验证、解析和评价。链接周围的文本（称链接文档）是链接评价的依据，本体父链接直接指向本体页面，其链接文档是构成正例样本的主要内容。由于链接文档的文本量一般较少，对本体页面的描述常常不够全面，本体页面的文本（称本体页面文档）也应该作为样本正例的重要补充。考虑到Web页面文本与链接之间的关系，链接文档被具体定义为与链接有关的5个区域文本的组合：链接路径（绝对URL）文本、链接锚（anchor）文本、链接附近文本（自链接锚向前和向后各取50个词）、页面内与该链接相关的各级标题（Headings：h1，h2，h3，h4，h5，h6）、页面标题（title）。尽管聚焦爬虫不必进行文本分类，但样本负例的采集有助于选择更具区分度的特征，使评价函数对搜索目标更具针对性。负例样本是泛主题的Web页面集，我们按照Yahoo!的Web目录分类均匀采集各类页面得到。3.2 链接评价算法设计3.2.1 特征词权算法文档的向量表示关键在于特征词的选择和词权计算。对于特征词权的计算，我们考虑一般特征词权公式中的两个因素：twij代表特征词i在文档j中的权，Lij作为特征词i在文档j中的局部权，通常它是特征词i在文档j中的出现频率（TF）的函数，Gi是特征词i的全局权，通常它是特征词i在整个样本文档集中出现频率的函数，常用的全局权是IDF。比起链接文档，本体页面文本量较多，通常词频也较高，TFIDF方法简单地以特征频率作为局部特征权，夸张了高频特征的重要程度，本体搜索中链接评价算法的局部词权计算应该予以有效抑制。同时，IDF算法对特征在样本集内集中程度的反映比较粗糙，难以准确量度特征的全局区分程度。根据本体页面和链接文档的特点，我们给出如下公式：，其中，fij是特征词i在文档j中的局部频率，Fi是特征词i在样本集中的全局频率，ni是特征词i在样本集中的文档频率（即包含该特征词的样本数）。3.2.2 搜索主题的量化表示通常，对经过规范化处理的样本正例文档向量进行算术平均，即可得到代表搜索主题的中心向量。为充分利用样本负例并强调正例，我们采用更具区分力的中心向量算法4：其中，D是样本集，C是样本正例集，|C|和|D-C|分别是正例和负例集的样本数，d代表一个文档向量，d是其欧几里德长度，c代表中心向量，和用于调整正负样本的相对影响。显然，c就是正负例样本集单位向量的加权和。和一般取16和4，向量c的负分量应被设为0。3.3 一些特殊启发式的处理某些通用搜索引擎（如Google）搜索特定类型文件的功能可以用于获取各类本体文档的URL；本体处理模块也可以向爬虫提供被引用本体的URL。这些URL不仅提供了本体文档，同时也是获取本体页面的启发式，试探性地搜索其URL路径上的各级目录，通常能够得到与本体相关的Web页面。研究表明，Web页面分布存在Linkage Locality特性5，对链接的最终评价应该以一定比例考虑其父链接的价值；对链接优先权队列的链接选择，在选择最优链接的同时，应该周期性地兼顾一组次优链接进行跟踪6。4链接评价方法的实现我们在上文提到的简单聚焦爬虫的基础上，调整页面处理模块的链接评价策略，用基于向量空间模型的文档相似度评价代替基于逻辑模型的特征词评价，涉及的主要操作有：爬虫训练前的样本采集、样本预处理，特征抽取，特征权计算，爬虫学习训练，爬虫搜索阶段链接文档的向量表示和相似度计算等。4.1样本采集爬虫程序的页面处理模块包含一个小型HTML解析器，主要功能是提取链接及文本。由于本体采集的特殊性，无法取用现成的训练语料作为样本正例，我们利用前期获得的本体搜索路径和HTML解析器，获取去除tag的本体页面文档与本体父链的链接文档。我们选取1000份本体父链接的链接文档和相应的1000份本体页面文档，并分别复制得到4000份正例。同时，借助浏览器从Yahoo!的14类Web目录开始手工获取URL，利用下载工具均匀采集各类页面共计4000份，经HTML解析器提取文本得到样本负例。4.2样本预处理样本的预处理在HTML解析并提取相关文本的基础上进行。首先对文本进行标记分割以便获得单词，清除其中的独立数字和单字符成分，将单词的字母转换为小写，根据一个禁用词表7清除禁用词，用Porter Stemming算法8进行词干转换。由于样本包含链接路径，我们在禁用词表中针对性地增加了部分单词，如http、www、edu、org、com、htm、html等。单个样本文档预处理的结果是包含单词及其局部词频（TF）的哈希表，作为样本表的一条记录存入数据库。4.3特征抽取单个样本预处理的结果称为词包，将各个样本的词包进行汇总，得到一个包含单词、词的全局词频和词的文档频率（DF）对应关系的数据表。从表中清除掉文档频率过低的大量单词，一般只需保留20-30%，称为特征词表。在爬虫学习训练和实际搜索阶段，特征词表一般被装入内存的临时表以提高访问速度。4.4样本的向量表示从样本表取出每个词包，根据内存中的特征词临时表，清除各个词包中不属于特征词的所有实体，根据特征词的全局词频、文档频率和局部词频，利用特征权公式求得该特征词的特征权，得到特征词与特征权对应的哈希表，它包含了该样本向量的非零部分。样本向量的规范化就是用向量的几何长度除各非零分量，得到表示单位长度样本向量的特征词权哈希表。4.5学习训练爬虫的学习训练就是由样本文档向量计算中心向量的过程。首先为内存中的特征词临时表增加一列，用以存放中心向量。对单位长度样本向量的特征词权哈希表，根据其中每个词的特征权和正负样本对中心向量影响程度的调节系数，利用中心向量算法求得该特征对中心向量的影响量，以此更新中心向量的相应分量。对最终得到的向量分量进行修正，将负值归零即得中心向量。4.6搜索阶段的相似度计算搜索阶段，HTML解析器提取链接文档，进行标记分割、词干转换后生成词包。将特征词表连同中心向量装入内存中的临时表，根据特征词的全局词频、文档频率和局部词频，计算该链接文档中各特征词的特征权，得到表示链接文档向量的词权哈希表。中心向量与链接文档向量点积运算后，再除以链接文档向量的长度即得文档相似度。5评价与结论为检验链接评价方法，我们同最初的逻辑模型方法以及采用经典TFIDF特征权算法的VSM原型方法进行了对比实验，结果见图1和图2。图1显示页面访问数百分比与本体页面命中率变化关系，图2显示时间百分比与本体页面数变化关系。由图1可知，相对于逻辑模型方法，向量空间模型方法对链接的访问有更高的本体页面命中率。图2表明，尽管逻辑模型特征词评价速度快，但因其链接评价的可靠性较低，其本体页面的回报速度未见优势。两图都表明改进的算法也显示出一定优势。 以上实验数据虽然只记录了爬虫搜索到前600个本体页面共3573个本体文档的局部过程，但搜索过程已进入稳定状态。由于局部过程的实验难以衡量一些特殊启发式的应用效果，实验中暂停了相应部分的改进。虽然没有对这些特殊启发式的效果进行检验，但根据有关研究6，我们认为这些考虑有助于限制搜索方法的贪婪程度，避免搜索过程过早陷入局部最优子空间，有助于提高爬虫隧穿无关主题区域的能力，扩大爬虫采集的覆盖面。本文在分析本体搜索特点的基础上，针对性地改进了聚焦搜索的链接评价方法，并介绍了新方法实现过程中的关键技术步骤。实验表明，有关改进提高了本体采集聚焦爬虫的搜索性能，对其他主题爬虫的设计也有参考意义。对样本页面进行必要的预处理后，根据DF指标确定出4000个特征词，计算每个特征词的IDF（Inverse Document Frequency），进而计算出所有正例样本的文档向量，并将其算术平均得到代表本体页面文档的中心向量，搜索中对某个链接的评价就是计算链接文档与本体页面文档的相似度。我们在只允许单一爬虫线程和只选择最优链接的前提下，对前述文档相似度链接评价策略进行了搜索和采集实验，并与逻辑模型的特征词评价策略进行比较，见图1和图2，图1显示页面访问数百分比与本体页面命中率变化关系，图2显示时间百分比与本体页面数变化关系。由图1可知，相对于逻辑模型评价策略，文档相似度策略对链接的访问有更高的本体页面命中率，文档相似度策略对链接评价的可靠性高于逻辑模型评价策略。图2表明，尽管逻辑模型特征词评价速度快，但因其链接评价的可靠性较低，其本体页面的回报速度也没有明显优势。综合来看，基于向量空间模型的文档相似度评价策略优于逻辑模型评价策略。但在我们的实验中其优势不够明显。我们认为文档相似度评价策略表现不佳，原因主要在于样本采集和文档表示。样本尤其负例样本数量较少，很难全面和均衡地反映各类主题信息分布的事实；用于构造中心向量的样本文档与被评价的链接文档在文本量上普遍差异明显；传统的特征词权计算方法夸大了采样问题的误差。改进样本采集和文档表示，将有助于提升聚焦爬虫的搜索性能，此外，根据本体分布和采集的特点，使用一些特殊启发式，对于完善爬虫搜索策略也是有益的。参考文献：1 G. Salton Developments in Automatic Text RetrievalJ Science, 1991, Vol.253: 974-9792 Y. Yang A Comparative Study on Feature Selection in Text Categorization Proceeding of the Fourteenth International Conference on Machine Learning , 1997, p412 - p4203 G. Salton, C. Buckley Term Weighting Approaches in Automatic Text RetrievalJ Information Processing and Management, 1988, Vol.24, No.5: 513-5234 J. Rocchio Relevance Feedback in Information Retrieval The SMART Retrieval System: Experiments in Automatic Document Processing, Chapter 14, p313-p323, Prentice-Hall Inc., 19715 J. Kleinberg Authoritative sources in a hyperlinked environment Report RJ 10076, IBM, May 1997, 19976 Menczer F Complementing search engines with online Web mining agentsJ Decision Support Systems, 2003, 35(2):195-2127 /pub/smart/english.stopOL8 /martin/PorterStemmer/OL作者简介：周文彬（1970），男，硕士研究生，主要研究方向：信息检索、文本分类；满死肇密甜遣异哼嚼柄罗央窜搅日抽供酿烧显诸恋