垂直搜索引擎系统的设计与实现

1、第29卷第3期2011年3月Vol.29,No.3March,2011垂直搜索引擎系统的设计与实现张敏,杜华(河北北方学院信息科学与工程学院,河北张家口075000摘要:面对日益专业和个性化的信息检索需求,通用搜索引擎存在的问题暴露无遗。垂直搜索技术作为搜索引擎发展的一个主要方向,正在受到越来越多的关注。在给出一个垂直搜索引擎总体结构的基础上,详细分析了所涉及的关键技术:网页抓取、中文分词、文本分类等。并将分词和分类算法加入到Nutch 中,实现了系统原型。实验证明,该系统主题相关度达到94%以上。关键词:垂直搜索引擎;中文分词;文本分类;主题相关度;nutch 中图分类号:G350文献标识码

2、:A文章编号:1007-7634(201103-0421-04Design and Implement of Vertical Search EngineZHANG Min,DU Hua(School of Information Science and Engineering ,Hebei North University ,Zhangjiakou 075000,China Abstract :Faced with increasingly professional and personalized needs of information retrieval,the problem for

3、 general search engine is exposed.It is more and more attention for vertical search technology as a major direction of search engine development.To gives the general structure of a vertical search engine,based on it,the key technologies involved are analyzed in detail:Web crawling,Chinese word segme

4、ntation,text classification and so on.And segmentation and classification algorithms add to the Nutch,realizing a prototype system.Experiments show that the degree of the system subject is to 94%.Key words :vertical search engine;chinese word segmentation;text classification;degree of the system sub

5、ject ;nutch收稿日期:2010-04-21基金项目:张家口市2009年科技攻关项目(0921047B 作者简介:张敏(1974-,女,满族,北京人,讲师,硕士研究生,主要从事网络信息管理研究.随着互联网的普及和发展,搜索引擎作为提供资源检索服务的工具已经成为人们获取信息的重要途径,正在深刻影响着我们的生活【1】。但通用搜索引擎在满足搜索全面性要求的同时很难兼顾专业性的查询需求,用户需求与网络服务之间的巨大反差产生了强大的“搜索噪音”。垂直搜索引擎凭借明确的检索目标定位,对网页进行选择性收集,信息采集量小,更新及时,因而能有效解决通用搜索引擎的弊端。垂直搜索引擎正在以其日趋精准化、人性

6、化的信息检索服务提升着人们对搜索引擎的使用率和认同度,助推了搜索引擎的快速发展【2】。1垂直搜索引擎系统总体结构本系统建立的垂直搜索引擎系统总体结构如图1所示。系统由三部分组成:信息采集(Crawler、索引(Indexer和查询(Query。信息采集模块负责从网络情报科学上搜集网页,对其内容在分词的基础上进行解析、提取、过滤;索引模块对搜索到的信息进行整理、分类和索引;查询模块根据用户的查询要求,从索引数据库中检索出与之相关的资料反馈给用户。图1垂直搜索引擎系统总体结构本文的工作主要集中在对“信息采集”子系统的研究上,而索引和查询子系统利用了Lucene提供的操作,今后我们可以针对系统的需求

7、以开源组件为基础进行个性化的改进。2信息采集系统的设计与实现2.1网页抓取模块本模块实现对Web信息的采集。垂直搜索引擎使用专业网络蜘蛛Spider抓取网页,此过程称为“generate/fetch/update”循环【3】。Step1:创建一个新的WebDB;Step2:把开始抓取的根URL放入WebDB;Step3:从WebDB的新segment中生成fetch-list;Step4:根据fetchlist列表抓取网页的内容;Step5:根据抓取回来的网页链接URL更新WebDB;Step6:重复上面3-5步,直到达到指定抓取层数。2.2中文分词模块中文分词是研究中文搜索引擎必须实现的关键

8、技术之一。中文分词算法分为三类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法【4】。本系统基于Nutch设计,其目前还没有应用上述三种方案的中文分词模块。虽然Nutch具有默认的中文分词功能,但它采用的分词方法是单字分词,即每个字被认为是一个词。这种方法对中文信息分析和处理的结果远未达到人们的期望效果。因此,文中选择采用基于词库的正向最大匹配分词算法,设计并实现适用于Nutch的中文分词模块,以满足系统对中文文本的分析和处理能力。中文分词算法设计。最大匹配法分词需要一个词典,分词过程中文本里的候选词与词典中的词进行比较,若匹配则认为候选词是词,予以切分。所谓最大匹配,就是尽

9、可能用最长的词来匹配句子中的汉字串。中文分词的正向最大匹配算法是:对一个字符串从前到后逐字扫描,从词表中逐一寻找最长匹配项,这是一种减字的匹配方法。中文分词模块的实现。文中设计的分词模块实现了正向最大匹配算法MM,并提供语料训练功能。由于MM算法是基于词典的分词算法,所以词典的权威性直接影响算法的分词效果,而分词效果对搜索引擎的性能起着至关重要的作用。本文在研究中通过总结现在流行的词库,自行合并去除重复,最后得到了本系统的中文词库,一个词汇量为36805的中文词典dic.dat,该词典为通用词汇词典。为了实现对新增词汇的切分,设计了语料训练模块,通过语料训练功能将新词添加到现有的词汇库中,设计

10、结构如图2所示。图2中文分词模块设计类图WordSegment对外提供分词接口;Dictionary 是词典类,记录所有分词;SegStrategy实现中文分词;WordSegFrame和DicTrainer提供新词训练,这样就使系统具有了识别新词的能力。2.3主题确立模块主题确立即文本训练过程。文中选用的训练文本包括教育和非教育两大类文本。首先调用分词模块对训练文本进行分词处理获取文本特征,将训练422情报科学29 卷文本集内的文本由连续的字符流转换成带有分割符的原始文本特征集,进行词性标注,为后面的特征项选择预处理做准备。由于分词之后所得到的原始文本特征集的特征数非常高,所以必须采用特征选

11、择算法对原始特征集进行压缩,从文本特征集里提取一个最优的特征子集,这里的最优特征子集是由评估算法来判定的。确定最优特征子集的过程就是学习获取最优分类函数的过程。先通过特征抽取算法给原始特征集中的特征打分,然后按照评分值从高到低对词项进行排序,选取评分最高的前n项作为特征词,最后进入训练分类器进行文本分类。特征项的选择。本文采用向量空间模型(VSM作为实现文本分类的表示模式。特征项的选择对向量空间模型的表达效果有着重要意义。由于词汇是文本最基本的表示项,在文本中出现频度较高,呈现一定的统计规律,所以本文选择词汇作为特征项的单位。但是如果直接选用文本中的词或词组作为文本特征项,存在下述问题:文本中

12、包含大量没有实在意义但使用频率很高的虚词和功能词,例如“的”、“把”、“了”等,经常会把那些真正有分类作用的实词淹没掉。解决该问题的方法是组织一个禁用词表。但禁用词表中很难全面包括所有禁用词,况且语言是不断发展的,禁用词表也要随着训练文本集合的不同而不同。针对这种情况,文中采用的办法是,在禁用词表的基础上配合进行权重计算。对禁用词表中未包含的虚词和功能词,计算其权重,使它们的权重很低,通过取阀值将其丢弃。另外,由于最能代表一篇文章实际意义的词通常是实词(形容词、动词、名词,所以本文只提取这三类词作为特征项。特征选择算法的设计与实现。特征选择方法的优劣直接影响到系统的效果。基于信息增益IG (I

13、nformation Gain的特征选择方法是最经典的特征选择算法之一,分类准确性较高。信息增益IG【5】。信息增益表示文档中包含某一特征值时文档类的平均信息量。它定义为某一特征在文档中出现前后的信息熵之差。计算公式如下:(1式中,t表示特征项,P(t表示w发生的概率,P(C i表示第i类发生的概率值,P(C i|t表示文本中出现t时,文本属于C i的概率。特征提取算法的实现:Step1:从训练文档库中提取所有特征项,构成文档属性集合F;Step2:对集合F中的每一项采用特征评估函数IG进行打分;Step3:对F中所有项都完成打分后,按分值由高到低进行排序;Step4:假设需要选取N个文档分类

14、属性,则从F中选取分值高的N个项,构成最终的分类属性集合Fs,Fs将用于文档的训练与分类。权重计算。自然语言文本中,汉字在不同内容的文本中所呈现出的频率分布是不同的,因此可根据词的频率特性进行权重评价。目前被广泛使用的是基于统计的TF-IDF公式,这个公式在大量的实际工作中被证明是有效可行的,这是一个以词为特征单元的经验公式。公式如下:W ik=TF ik*IDF ik(2其中TF ik为Tk在文档D i的词频,IDF ik为反比文本词频,其计算方法有很多种。目前较为常用的公式为:W ik=TF ik*log(N/n k+0.01(3其中W ik代表文档D i其特征单元第K项的权重,TF ik

15、为T k在文档D i的词频,N代表的是所有的训练文本,n k代表训练文本中出现该特征项的文本数。本文对特征词的权重评价是在大量训练文本的基础上,根据各特征词对文本内容的贡献,经过多次统计学习完成的。2.4主题预测模块主题预测即文本分类。该模块接收经网页分析模块处理后的网页内容,首先对其进行分词处理,然后通过相似度计算,确定网页内容与主题的相似程度,得到网页文本所属的类别。文本分类。文本分类指按照预先定义的主题类别,为文档集合中的每个文档确定一个类别。目前,应用于英文文本分类的方法较多,而用于中文文本分类的方法则较少,主要有朴素贝叶斯分类(Nave Bayes、K近邻(KNN、向量空间模型(Ve

16、ctor Space Model【6】以及线性最小二乘LLSF(Linear Least Sq uare Fit等。本文采用K近邻算法。K近邻算法(K Nearest Neighbors,简称KNN【7】是1968年Cover和Hart3期垂直搜索引擎系统的设计与实现423提出的。K 近邻就是考察和待分类文本最相似的K 篇文本,根据这K 篇文本的类别来判断待分类文本的类别值。相似值的判断可以使用欧拉距离,或是余弦相似度等。而最相似的K 篇文本按其和待分类文本的相似度高低对类别值予以加权平均,从而预测待分类文本的类别值。本文所使用的分类系统中相似度值的计算采用余弦相似度。公式如下:其中,d i

17、为新文本的特征向量,d j 为第j 类的中心向量,M 为特征向量的维数,W k 为向量的第k 维。分类器的设计与实现。本模块实现了一个基于教育主题的文本分类器。KNN 分类算法实现步骤:Step1:根据特征项集合重新描述训练文本向量;Step2:在新文本到达后,根据特征词分词新文本,确定新文本的向量表示;Step3:利用公式(4,在训练文本集中选出与新文本最相似的K 个文本;Step4:在新文本的K 个邻居中,依次计算每类的权重,比较类的权重,将文本分到权重最大的那个类别中。在K 近邻分类器中,K 是一个重要参数。如果K 值选择过小,则不能充分体现待分类文本的特点;而若K 值选择过大,则与待分

18、类文本实际上并不相似的某些文本也被包含了进来,造成噪声增加导致分类效果的降低。K 值的确定目前没有很好的方法,一般采用先定一个初始值,然后根据实验测试的结果调整K 值,在本系统中K 的初始值确定为20。3实验验证及分析3.1文本分类实验语料库介绍。在文本自动分类系统中,通常将用于实验的文本集分为两个部分:训练集和测试集。训练集由一组已分好类(即已给定类别标号的文本组成,用于归纳各个类别的特性以构造分类器。测试集是用于测试分类效果的文档集合。其中每个文本都通过分类器分类,然后与正确决策的分类结果相比较得到对分类器效果的评价。训练和测试文档的各个类别分布如表1。表1训练和测试文档的各类别分布分类系

19、统评估。准确率(Precision:测试本系统的分类效果。计算公式如下:准确率(P =分类的正确文本数实际分类的文本数(5实验数据:训练集样本数为1883。针对训练数据不同的测试集进行测试,测试集样本数为934。分类算法KNN ,特征预处理采用禁用词表,权重计算公式T'F*IDF ,K 值取20,特征数目从50到100000。实验结果:分类准确率。实验结论:表2显示,对于中文文本分类,特征向量空间过大或过小时,分类准确度都不高。当选用的特征词过少时,不能全面反映各个类别的特征,因而不能准确地区分各类别文档;相反,选用的特征词过多时,一些区分度很低的冗余词汇也被加了进来,那些区分度较高的

20、词在其中被“稀释”了,不能有效地为区分文档做贡献。因此,特征向量空间大小的合理设置,直接影响文本分类的效果。3.2主题相关度实验实验目的:测试系统主题评价精度。实验方法:收集一定数目的页面(1010个,首先针对这1010个页面进行人工判别,统计出与主题相关和与主题无关的页面数;然后再对这1010个页面使用本系统进行主题判别,将判别结果和人工统计结果相比较,计算给出主题判别准确率即主题评价精度。实验结果如表3所示。实验结论:实验证明本系统针对指定主题的Web 资源发现率较高,接近95%;而对于与主题无关页面的判断更高达97.68%。充分说明本系统能够424情报科学29卷训练文档数测试文档数教育类

21、799496非教育类1084438总计188393477.4380.3782.3586.7588.9487.2585.8379.1671.6366.06表2KNN 分类器的分类准确率(下转第439页 (责任编辑:徐波(责任编辑:徐波(上接第424页较好地实现特定主题信息的专业化搜索。表3网页主题相关度实验结果4结语本文在给出一个垂直搜索引擎总体结构的基础之上,详细分析了所涉及的关键技术,讨论了具体的实现方法。试验数据证明,该系统主题相关度达到94%以上,能够较好地实现对特定主题信息的专业化搜索。当然,系统还存在不足之处,如现有分词算法实现较为简单,效率有待提高;训练数据的质量对于分类至关重要,

22、由于各方面限制,当前训练文本不够全面,需要继续收集训练和测试数据以提高分类质量等。在今后的工作中将针对上述问题做进一步的研究。参考文献1中国互联网络信息中心.第二十四次中国互联网发展状况2中国互联网络信息中心.第二十五次中国互联网发展状况3Heritrix Crawler vs.Nutch Crawler EB/OL.http:/www. m1,2006-09-24.4张淑梅.词典与后缀数组相接合的中文分词D.长春:吉林大学,2006.5代六玲,黄河燕,陈肇雄.中文文本分类中特征抽取方法的比较研究J.中文信息学报,2003,18(11:26-32.6G Salton,C S Yang.On the Specification of Term Values in Automatic Indexing J.Journal of Documentation,197