网页超5成大学生脱发

北京大学博士研究生学位论文题目:中文网页自动分类技术研究及其在搜索引擎中的应用姓名:冯是聪学号:10008826院系:计算机科学技术系专业:计算机软件与理论研究方向:计算机网络与分布式系统导师:李晓明教授2003年5月AStudyontheTechnologyofChineseWebPageAutomaticCategorizationandItsApplicationtoSearchEngineDissertationSubmittedtoPekingUniversityinpartialfulfillmentoftherequirementforthedegreeofDoctorofPhilosophyByShi-congFeng(ComputerScienceandTechnology)DissertationSupervisor:ProfessorXiaomingLIMAY,2003声明任何收存和保管本论文各种版本的单位和个人,未经本论文作者授权,不得将本论文转借他人并复印、抄录、拍照、或以任何方式传播.
否则,引起有碍作者著作权益之问题,将可能承担法律责任.
北京大学学位论文原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果.
除文中已经注明引用的内容外,本论文不含任何其它个人或集体已经发表或撰写过的作品成果.
对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明.
本人完全意识到本声明的法律结果由本人承担.
学位论文作者签名:日期:2003年6月8日摘要i摘要为了能够有效地组织和分析海量的Web信息资源,帮助用户迅速地获取其所需要的知识和信息,人们希望能够按照其内容实现对网页的自动分类.
Web的迅猛发展为文档自动分类技术提供了一个前所未有的实验环境和应用平台,同时也带来了新的挑战,需要在传统的技术基础之上,开展针对Web网页特性的研究工作.
本文对中文网页自动分类技术这一具有重要理论意义和广阔应用前景的课题进行了研究和探索,主要的研究成果有:⑴影响分类器性能的关键因素的定量分析针对影响分类器性能的两个基本指标(分类质量和分类效率)及其相互关系,本文从系统的角度出发,综合地考虑了影响分类器性能的各种关键因素,并且通过定量地分析这些因素,提出了一种新的中文网页分类器的设计方案.
实验结果表明,应用该方案设计实现的中文网页分类器不仅具有较高的分类质量,而且同时具有较高的分类效率,满足了处理大规模中文网页的要求.
⑵中文网页内"噪音"的自动清除同普通文档相比,网页的设计比较随意,通常都包含大量"噪音",这些"噪音"影响了网页分类的质量.
为此,本文提出了一种自动从中文网页中自动清除"噪音"的方法.
该方法通过利用中文网页的结构信息和内容信息,并结合中文网页自动分类技术,实现了自动从中文网页中自动清除"噪音".
实验结果表明,该方法不仅可以有效地从中文网页中自动清除"噪音",而且,还可以有效地改进中文网页分类器的分类质量.
⑶从搜索引擎日志中学习新词针对直接从专业语料库中学习新词所面临的困难,本文提出了一种从搜索引擎日志中学习新词的方法.
同传统的方法相比,该方法具有学习效率和准确率高、不受领域的局限、实现简单、易于推广等优点.
该方法的基本思想是,根据用户查询词的长度分布特性和频度分布特性以及分词系统的先验知识,从所有汉字组合模式中尽可能地排除无效的组合模式,从而提高了学习新词的效率和准确性.
实验结果表明,该方法不仅可以有效摘要ii地从搜索引擎日志中学习新词,为新词的自动学习提供了一种新的思路,而且,通过不断扩大分词字典的规模,还可以有效地改进网页分类质量.
⑷应用中文网页的自动分类技术,在"自动式"搜索引擎"天网"系统中同时提供目录导航服务为了提高搜索引擎的查准率,帮助用户快速地定位其感兴趣的网页,本文应用中文网页自动分类技术,在"自动式"搜索引擎系统中实现了目录导航服务.
这种同时具有目录导航功能的"自动式"搜索引擎系统,不仅能够维护大规模的网页,而且具有较高的查准率.
关键词:搜索引擎,Web挖掘,中文网页自动分类,定量分析,噪音清除,新词学习,目录导航AbstractiiiAbstractToeffectivelyorganizeandanalyzemassiveWebinformationresourceandhelpuserstopromptlygetknowledgeandinformationtheyneed,itneedstoimplementWebpagesautomaticcategorizationbytheircontents.
ThepromptdevelopmentofWebnotonlyprovidesanunprecedentedexperimentenvironmentandanapplicationplatformfortextautomaticcategorization,butalsoanewchallenge.
Therefore,basedonthetraditionaltechnologies,researchworkaimingatthefeaturesofWebpagesisneededtodevelop.
ThisdissertationexploresthetopiconChineseWebpageautomaticcategorization,whichisaresearchissuewithgreatsignificanceintheoryandwideperspectiveinapplication.
Themaincontributionsofthisdissertationareasfollows:⑴QuantitativeanalysisofthekeyfactorswhichaffecttheperformanceofclassifierFocusedonthebasictwoevaluationstandards(categorizationqualityandcategorizationefficiency)andtheirrelations,thisdissertationputsforwardanoveldesignsolutionofChineseWebpageclassifierbyquantitativeandsyntheticalanalysisofthekeyfactorsaffecttheperformanceofclassifier.
Theexperimentalresultsshowthattheclassifiersaredesignedbythissolutionnotonlyhavehighercategorizationquality,butalsohavehighercategorizationefficiency,whichcansatisfytherequestofprocessinglargescaleChineseWebpages.
⑵AutomaticnoisereductionofChineseWebpagesComparedwithplaintexts,Webpagesaredesignedatwillandcontainplentyofnoise,whichaffectsthequalityofWebpagecategorization.
Therefore,thisdissertationprovidesanapproachtoreducenoisefromChineseWebpagesautomatically,whichmakesgooduseofthestructuralinformationandcontentsofChineseWebpagesandcombinesChineseWebpageautomaticAbstractivcategorization.
TheexperimentalresultsshowthatthismethodnotonlycaneffectivelyreducenoisefromChineseWebpages,butalsocaneffectivelyimprovethequalityofWebpagecategorization.
⑶LearningnewwordsfromsearchenginelogfilesAimingatthedifficultiesinlearningnewwordsfromprofessionalcorpus,thisdissertationputsforwardanapproachoflearningnewwordsfromsearchenginelogfiles.
Comparedwiththetraditionalmethods,thismethodhasseveraladvantages,suchashavinghigherefficiencyandprecision,notlimitedbyspecialdomains,simplyimplemented,andpopularization.
ThemainideaofthismethodistofilteroutinvalidcombinationsofChinesecharactersasmanyaspossibleaccordingtothedistributionofthelengthandfrequencyofquerywordsandthetranscendentalknowledgeofChinesewordsegmentationsystems.
Theexperimentalresultsshowthatthismethodnotonlycaneffectivelylearnnewwordsfromsearchenginelogfiles,whichprovidesanovelapproachforlearningnewwords,butalsocaneffectivelyimprovethequalityofWebpagecategorizationbyenlargingthescaleofsegmentationdictionary.
⑷Toprovidecategorynavigationserviceinspider-stylesearchengineTianWangwiththeapplicationofChineseWebpageautomaticcategorizationToimprovetheprecisionofsearchengineandlocateuser-interestingWebpagepromptly,thisdissertationappliesChineseWebpageautomaticcategorizationtechnologytoprovidedirectorynavigationserviceinspider-stylesearchengines.
Thiskindofspider-stylesearchengineswithcategorynavigationfunctionnotonlycanmaintainlargescaleWebpages,butalsohavehigherprecision.
Keywords:SearchEngine,WebMining,ChineseWebPageAutomaticCategorization,QuantitativeAnalysis,NoiseReduction,NewWordsLearning,CategoryNavigation目录v目录摘要iAbstractiii目录v图表索引viii第1章绪论.
11.
1研究背景11.
2中文网页自动分类技术概述21.
2.
1文档自动分类算法的分类.
21.
2.
2实现中文网页自动分类的一般过程41.
2.
3中文网页自动分类的关键技术61.
2.
4实现中文网页自动分类面临的主要问题151.
3本文的主要工作161.
3.
1本文的主要研究内容161.
3.
2本文的创新之处.
181.
4本文的组织结构19第2章影响分类器性能的关键因素的定量分析.
212.
1引言.
212.
2影响分类器性能的关键因素的定量分析222.
2.
1实验设置222.
2.
2训练样本222.
2.
3特征选取272.
2.
4分类算法282.
2.
5阈值策略332.
2.
6一个中文网页分类器的设计方案342.
3相关研究352.
4本章小结36第3章中文网页内噪音的自动清除38目录vi3.
1引言.
383.
2噪音清除算法393.
3实验结果及其分析.
413.
3.
1实验设置413.
3.
2实验结果413.
4相关研究433.
5本章小结44第4章从搜索引擎日志中学习新词454.
1引言.
454.
2一种从搜索引擎日志中学习新词的方法474.
2.
1基本思想474.
2.
2用户查询词的分布特性分析494.
2.
3组合模式的提取.
524.
2.
4候选词的筛选544.
2.
5算法分析554.
3实验结果及其分析.
564.
3.
1新词学习方法质量的测试.
564.
3.
2新词学习方法效率的测试.
584.
4分词字典的规模对分类质量的影响.
594.
5相关研究604.
6本章小结61第5章中文网页自动分类技术在搜索引擎中的应用.
625.
1引言.
625.
2"天网"目录导航服务645.
2.
1"天网"目录导航服务的体系结构645.
2.
2"天网"目录的运行实例.
655.
3相关研究675.
4本章小结68第6章总结与展望.
696.
1本文的总结.
696.
2进一步的研究工作.
71目录vii参考文献73附录"天网"中文网页分类目录(1.
0版)80博士生期间录用和提交的论文87致谢88图表索引viii图表索引图1-1文档自动分类算法的分类.
3图1-2实现中文网页自动分类的一般过程5图1-3中文网页分类器的工作原理图.
5图2-1WebSmart—一个网页实例集收集和整理工具24图2-2一个中文网页分类体系25图2-3Macro-F1值随样本数的变化26图2-4Micro-F1值随样本数的变化26图2-5CHI、IG、DF、MI的比较(Macro-F1)27图2-6CHI、IG、DF、MI的比较(Micro-F1)28图2-7kNN与NB分类结果的比较29图2-8k的取值对分类器质量的影响(Marco-F1)30图2-9k的取值对分类器质量的影响(Micro-F1)30图2-10兰式距离法与欧式距离法对12个不同类别的分类情况.
31图2-11基于层次模型的kNN与基本kNN的比较32图2-12RCut和SCut阈值策略的比较33图2-13新方案同基本kNN的比较.
35图3-1一个网页的HTML源代码图3-2一棵典型的标签树.
.
.
.
40图3-3处理前的网页42图3-4应用NR算法处理后的网页42图3-5NR算法对中文网页分类质量的影响.
43图4-1从搜索引擎日志中学习新词的一般步骤.
48图4-2"天网"搜索引擎的用户查询日志举例.
48图4-3用户查询词的长度分布图.
50图4-4用户查询词的频度分布图.
51图4-5一种从搜索引擎日志中提取汉字组合模式的算法53图4-6新词学习方法的"学全率-学准率"曲线图.
57图4-7从搜索引擎日志中自动学习得到的新词的举例58图表索引ix图4-8新词学习方法的时间复杂度59图5-1"天网"目录的体系结构.
65图5-2"天网"目录导航服务系统的用户查询界面66表1-1信息检索系统的评价标准.
13表2-1样本集中类别及实例数量的分布情况表.
23表2-2kNN和NB算法的分类质量和分类效率比较.
28表2-3欧式距离与兰式距离的比较31表2-4基于层次模型的kNN与基本kNN的比较32表2-5RCut和SCut阈值策略的比较.
33表2-6一个中文网页分类器的设计方案.
34表2-7采用新方案设计的分类器的性能.
34表3-1选用的HTML标签及其相应的权重39表4-1字典的规模对分类质量的影响.
60第1章绪论1第1章绪论1.
1研究背景因特网的飞速发展为人们提供了一个可以跨越时间和空间的界限来共享和发布信息的平台.
作为因特网上最成功的应用,万维网(WorldWideWeb,简记为Web)在短短十几年中获得了举世瞩目的成就,为人们的学习和生活带来了巨大的便利.
一方面,人们可以通过Web来获取所需要的信息和服务:通过电子商务,足不出户就能够购买到所需要的商品;通过远程教育,可以接受来自世界各地著名学府的教育或培训;通过浏览新闻站点,可以及时地了解到国内外的新闻焦点…….
另一方面,人们还可以通过Web来共享和发布各种信息:企业通过创建主页来展示和宣传自己的产品;科研机构通过网页来交流最新的研究成果;个人用户也通过创建个人主页来结识更多的朋友……,所有这些都导致了Web上网页量的迅速膨胀.
到2003年4月,Google搜索引擎索引的网页数已经超过30亿[Google].
根据"天网"搜索引擎[TianWang][周利民97]在中文网页的收集工作中统计得到的数据,到2003年4月,中国拥有的网页数已经超过了一亿,而且还将在相当长的一段时间内快速地增长.
拥有海量网页信息的Web就像一本无所不包的百科全书.
由于没有"主编",人们可以随心所欲地向这本书提交任何信息,这样就导致了这本书在内容组织上的极端混乱.
尽管它包含着极大的信息资源,但是真正有用的信息却相对匮乏.
面对规模如此庞大的信息海洋,试图通过浏览Web网页来发现信息已经变得异常困难,往往花费大量的精力却所获甚少.
因此,在Web用户和Web信息资源之间出现了巨大的鸿沟:一方面,Web资源中蕴含着极其丰富的有价值的信息和知识;另一方面,用户却无法有效地获取这些信息和知识.
因此,为了能够有效地组织和分析海量的Web信息资源,帮助Web用户方便地获取其需要的信息和知识,人们希望能够按照其内容实现对网页的自动分类.
事实上,网页自动分类技术在面向主第1章绪论2题的搜索引擎[CBD99]、个性化搜索引擎[PG99]、搜索引擎的目录导航服务[CG][CR00]、Web信息过滤[CF00]、Web信息的主动推送服务[BMK98]、数字图书馆等领域得到了广泛地应用,已经成为Web信息检索领域中的研究热点.
由于本文处理的对象主要是Web上的中文网页资源,因此本文将对中文网页自动分类技术这一具有重要理论意义和广阔应用前景的课题进行研究和探索.
1.
2中文网页自动分类技术概述在Web出现之前,人们已研究过许多普通文档分类的方法,形成了各种文档自动分类(AutomaticTextCategorization,ATC)技术[YL99].
随着海量网页信息的涌现,ATC技术的处理对象从普通文档扩展到网页信息,自然地,ATC技术成了实现网页自动分类技术的基础.
所谓文档自动分类就是用计算机程序来确定文档和预先定义类别之间的隶属关系[Fabrizio].
中文网页自动分类技术涉及到Web信息检索、自然语言处理、机器学习等多个领域.
下面,本节首先将简要地回顾一下文档自动分类算法的分类,接着归纳了实现中文网页自动分类的一般过程,并根据这个一般过程来设计中文网页分类器的基本框架,随后重点介绍了与本文研究工作相关的基本概念和关键技术,最后针对中文网页资源较普通文本相比所具有的特性,对实现中文网页自动分类过程中存在的主要问题进行了分析.
1.
2.
1文档自动分类算法的分类目前,已有的主要文档自动分类算法可以分为三类:⑴词匹配法.
词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种.
简单词匹配法是最简单、最直观的文档分类算法,它根据文档和类名中共同出现的词决定文档属于哪些类.
很显然,这种算法的分类规则过于简单,分类效果也很差.
基于同义词的词匹配法是对简单词匹配法的改进,它先定义一张同义词表,然后根据文档和类名以及类的描述中共同出现的词(含同义词)决定文档属于哪些类.
这种分类算法扩大了词的第1章绪论3匹配范围,在性能上要优于简单词匹配法.
不过,这种算法的分类规则仍然很机械,而且同义词表的构成是静态的,对文档的上下文不敏感,无法正确处理文档中其具体含义依赖于上下文的词,分类的准确度也很低.
⑵基于知识工程的方法.
基于知识工程的文档分类方法,需要知识工程师手工地编制大量的推理规则,这些规则通常面向具体的领域,当处理不同领域的分类问题时,需要不同领域的专家制定不同的推理规则,而且分类质量严重依赖于推理规则的质量.
因此,在实际的分类系统中较少使用基于知识工程的学习法.
⑶统计学习法.
统计学习法和词匹配法在分类机制上有着本质的不同.
它的基本思路是先收集一些与待分类文档同处一个领域的文档作为训练集,并由专家进行人工分类,保证分类的准确性,然后分析这些已经分好类的文档,从中挖掘关键词和类之间的联系,最后再利用这些学到的知识对文档分类,而不是机械地按词进行匹配.
因此,这种方法通常忽略文档的语言学结构,而用关键词来表示文档,通过有指导的机器学习来训练分类器,最后利用训练过的分类器来对待分类的文档进行分类.
这种基于统计的经验学习法由于具有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点,目前实用的分类系统基本上都是采用这种分类方法.
文档自动分类算法词匹配法知识工程法统计学习法M-aryIndependencyBinaryWORDLLSFDTreeNBNNetKNNNNRocchioSVM图1-1文档自动分类算法的分类本文介绍的文档分类算法都属于统计学习法.
根据分类结果的不同,基于统计学习法的分类系统在整体上可以被分为两类:独立二元(IndependentBinary)分类系统和m元(m-ary)分类系统.
所谓独立二元分类,就是给定一篇文档,分类系统对每一个类都独立地判断这篇文档第1章绪论4是否属于该类:要么属于,要么不属于,而不存在其它的结果,并且在分类过程中,不同类别之间互不影响.
所谓m元分类就是给定一篇文档,系统计算这篇文档与所有预先定义的类的相似度,并按这篇文档和各个候选类的相似度排序,最后输出候选类列表.
文档分类算法示意图如图1-1所示,本文将在第1.
2.
3节介绍其中几个典型的分类算法.
1.
2.
2实现中文网页自动分类的一般过程在应用基于案例的有指导的机器学习方法实现中文网页自动分类的过程中有一个基本的假设:文档的内容与其中所包含的词之间有着必然的联系,同一类的文档之间总存在多个共同的词,而不同类的文档所包含的词之间差异很大.
因此,分类器的训练过程可以看作是在已知文档类别的情况下,统计不同类别内的词的分布,即在预先定义的类别集合C(C={c1,…,ck,…,cm})与词项集合T(T={t1,…,tk,…,tn})的幂集之间建立一种加权的映射关系,形成一种向量表示;相应的,分类器的分类过程,可以看作在已知一篇文档内所包含词的分布(用一个向量表示)情况下,和在训练中形成的每个类别的向量表示进行对比,来确定该文档与类别之间的隶属关系.
根据对文档分类过程实质的分析,下面给出中文网页自动分类的一般过程.
同普通英文文档相比,中文网页信息具有自身的特性:⑴中文网页的内容使用中文书写,不像英文单词之间存在自然的形态间隔,因此为了对中文网页进行有效地处理,首先需要进行分词处理,而且分词的效果将显著地影响分类效果.
⑵网页使用超文本设计.
它包含大量的HTML标签和超链接,有可能利用这些信息来改进分类的质量.
比如包含在标题标签内的内容通常要比出现在网页正文标签内的内容要重要的多.
在Web上相邻的网页通常具有相关或相同的主题,因此网页之间的超链信息也可以给本文一些启发.
⑶网页通常包含大量的"噪音".
同普通文本相比,网页的设计比较随意,通常包含各类广告,设计人员的注释以及版权申明等无关信息.
有时同一个网页甚至会包含多个不同的主题.
在进行分类之前,需要自动清第1章绪论5除这些"噪音",否则这些"噪音"会降低分类质量.
因此,需要对中文网页进行预处理后,才能应用相应的文档自动分类算法实现分类.
结合中文网页的特性,图1-2给出了实现中文网页自动分类的一般过程.
其中:预处理过程主要包括中文分词以及网页内"噪音"清除等处理;基于二元分类算法的分类器,可以把分类结果直接作为待分类网页的类别结果,而基于m元分类算法的分类器,还需要对该分类结果进行进一步的筛选后,才能作为待分类网页的类别结果.
训练集预处理分类算法参数调整测试特征选取分类结果截尾算法IndependencyBinary分类M-ary分类图1-2实现中文网页自动分类的一般过程待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程分类过程图1-3中文网页分类器的工作原理图根据图1-2所示的实现中文网页分类的一般过程,本文设计了中文网页分类器的基本框架,其工作原理如图1-3所示.
从总体上,分类器的整个工作周期可以分成训练过程和分类过程.
在训练过程中,训练集实例经过中文分词和特征选取处理后被表示成向量形式.
该特征向量集用来描述类别模式,在分类过程中使用.
校验集是训练集的一部分,通过应用相应的阈值策略来预先确定每个类别的截尾阈值.
在分类过程中,一个待分类第1章绪论6的中文网页经过中文分词并表示成向量后,应用分类算法同训练过程得到的类别模式逐一比较,得到候选类别列表,然后同训练过程中得到的每个类别的阈值相比较,保留大于阈值的类别,并作为该网页的分类结果.
从图1-3可以看出,构建一个分类器的关键因素包括:预处理、训练集、特征选取算法、分类算法和阈值策略等.
本文的第2致第4章将逐一定量地分析这些因素对分类器性能的影响.
1.
2.
3中文网页自动分类的关键技术从图1-3所示的中文网页分类器的工作原理图可以看出,为了实现中文网页的自动分类,通常需要关注训练分类器使用的训练样本集、特征选取算法、分类算法、阈值策略、分类系统的性能评价值指标等方面的问题.
下面将分别介绍.
⑴训练样本集为了评价各种文档自动分类算法的优劣,推进信息检索领域的发展,由美国国家标准和技术研究院(NIST)、信息技术实验室(ITL)检索小组、美国国防部高级研究计划署(DARPA)信息技术处、高级研究开发机构(ARDA)等单位共同发起了有全球影响的文档检索会议[TREC].
从1992年起,每年一次,至今已召开了11次.
TREC会议实际上是文本信息检索系统的擂台赛,可以说,在TREC上展示的文本分类系统代表了文本分类领域的最新研究成果.
一些大学,如CMU、BERKLEY、CORNELL等和一些公司带着自己开发的文本分类系统参加会议,由大会使用相同的训练集和测试集对这些系统进行评测.
中国科学院计算所、清华大学等单位近几年也有派队参加,并取得了不错的成绩.
同时本文注意到,由于Web技术的发展,TREC也逐步开始提供标准的英文网页语料[TED]来评测Web信息检索系统.
与面向英文的分类系统相比,中文分类系统的起步比较晚.
从第五次TREC会议开始,增加了对中文分类系统的评测.
实际上参加TREC-5的中文分类系统处理的重点还停留在中文的分词问题上,而且处理的对象还是新华社的新闻稿这类普通的中文文本.
基于案例的有指导的机器学习方法是实现中文网页自动分类的理论基础.
因此,中文网页训练集是实现中文网页自动分类的前提条件.
但是,到目前为止,还没有出现标准的中文网第1章绪论7页语料库,也没有出现针对中文网页分类系统的评测,因此为了研究中文网页的自动分类的问题,首先需要解决的问题是中文网页训练样本集的收集和整理,本文将在第2章继续讨论这个问题.
⑵特征选取算法实现文本自动分类的基本困难之一是特征项空间的维数过高.
所谓"特征项",在中文文本中主要指分词处理后得到的词汇,而特征项的维数则对应不同词汇的个数.
数量过大的特征项一方面导致分类算法的代价过高,另一方面导致无法准确地提取文档的类别信息,造成分类效果不佳.
因此,需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维数.
"特征选取"的任务就是要将信息量小,"不重要"的词汇从特征项空间中删除,从而减少特征项的个数,它是文本自动分类系统中的一个关键步骤.
为便于后面的描述,这里简要给出特征选取的一般过程.
给定训练文档集合DOCS={d1,…,dn},设TERMS={t1,t2,…,tm}为对DOCS中的文档做分词后得到的词汇全集,用[m]表示集合{1,2,…,m}.
所谓"特征选取"可以看成是确定从TERMS到[m]的一个1-1映射,即F-Selection:TERMSà[m]然后根据计算开销的考虑,取一个i∈[m],认为TERMS中那些函数值不小于i的词汇为"选取的特征项",记作TERMSs.
在完成了特征选取后,分类就是基于TERMSs,即以其中的元素为基础,用一个向量来表达每一个文档.
分类的过程就是按照某种算法来比较待分类文档的表示向量和训练集文档的表示向量,取最相近者所处于的类为待分类文档的类.
人们已经研究了多种特征选取方法,如:文档频率(DocumentFrequency,DF)、信息增益(InformationGain,IG)、互信息(MutualInformation,MI)、开方拟和检验(χ2-test,CHI)、术语强度(TermStrength,TS)等.
文献[YJP97]针对英文纯文本比较研究了上述五种经典特征选取方法的优劣.
实验结果表明:CHI和IG方法的效果最佳;DF方法的性能同IG和CHI的性能大体相当,而且DF方法还具有实现简单、算法复杂度低等优点;TS方法性能一般;MI方法的性能最差.
下面对这些典型的特征选第1章绪论8取算法做一下简单地介绍:Ⅰ文档频率DF表示在训练集中包含某个特征项t的文档数.
这种衡量特征项重要程度方法基于这样一个假设:DF较小的特征项对分类结果的影响较小.
这种方法优先取DF较大的特征项,而DF较小的特征项将被剔除.
即特征项按照DF值排序.
这里,为物理意义清楚起见,本文并没有像本节开始那样讲严格的从TERMS到[m]的映射,但显然这是没有困难的,不赘述(后同).
不过要注意,这种策略不符合被广泛接受的信息检索理论:高频词没有低频词对文档特征贡献大[YJP97].
DF是最简单的特征项选取方法,而且该方法的计算复杂度低,能够胜任大规模的分类任务.
Ⅱ信息增益IG通过统计某个特征项t在一篇文档中出现或不出现的次数来预测文档的类别.
IG的计算公式如公式(1-1)所示:G(t)=∑=miirircPcP1)(log)(∑=+miirirtcPtcP1r)|(log)|((t)p∑=+miirirrtcPtcPtP1)|(log)|()((1-1)其中:)(ircP表示一篇文档属于类别ic的概率;)(tPr表示特征项t在一篇文档内出现的概率;)(tPr表示特征项t不在一篇文档内出现的概率;)|(tcPir表示特征项t在属于类别ic的文档内出现的概率;)|(tcPir表示特征项t不在属于类别ic的文档内出现的概率.
m是文档类别数.
G(t)值大则被选取的可能性大,即特征项按照G值排序.
Ⅲ互信息MI使用公式(1-2)计算某个特征项t和类别c之间的相关性.
)()(log),(BACANActI+*+*≈(1-2)其中:A为t和c同时出现的次数;B为t出现而c没有出现的次数;C为c出现而t没有出现的次数.
N为所有文档数.
如果t和c不相关,则),(ctI值为0.
如果有m个类,于是对于每个t会有m个值,取它们的平均,就可得到特征选取所需的一个线性序.
大的I平均值的特征被选取的可能性大.
第1章绪论9ⅣCHI使用MI衡量特征项的重要程度时,只考虑到了正相关对特征项重要程度的影响.
如果特征项t和类别c反相关,就说明含有特征项t的文档不属于c的概率要大一些,这对于判断一篇文档是否不属于类别c也是很有指导意义的.
为克服这个缺陷,CHI使用公式(1-3)计算特征项t和类别c的相关性:)()()()()(22),(DCBADBCACBADNct+*+*+*+*=χ(1-3)其中:A为t和c同时出现的次数;B为t出现而c没有出现的次数.
C为c出现而t没有出现的次数;D为t和c同时没有出现的次数.
N为训练集中的文档数.
和MI类似,如果t和c不相关,则),(2ctχ值为0.
同MI相同,如果有m个类,每个t就会有m个值,取它们的平均,就可得到特征选取所需的一个线性序.
大的2χ平均值的特征被选取的可能性大.
⑶分类算法在本文的第1.
2.
1节,介绍了各种文档自动分类算法的分类.
下面对几个比较典型的分类算法进行具体的介绍.
ⅠkNN算法kNN分类算法是一种传统的基于统计的模式识别方法.
算法思想很简单:对于一篇待分类文档χv,系统在训练集中找到k个最相近的邻居,使用这k个邻居的类别为该文档的候选类别.
该文档与k个邻居之间的相似度按类别分别求和,减去一个预先得到的截尾阈值,就得到该文档的类别测度.
用kNN也表示所选k个最相近文档的集合,公式(1-4)刻画了上述思想[YL99].
jjikNNdijbcdydsimcyi=∑∈),(),(),(vrvvvχχ(1-4)其中:χv为一篇待分类网页的向量表示;dv为训练集中的一篇实例网页的向第1章绪论10量表示;cj为一类别;}1,0{),(∈jicdyv(当dv属于cj时取1;当dv不属于cj时取0);bj为预先计算得到的Cj的最优截尾阈值;),(idsimvvχ为待分类网页与网页实例之间的相似度,由公式(1-5)计算得到:||||,dxdxdxCosrrrr>=标签内的内容通常要比出现在网页正文标签内的内容要重要的多;⑶网页的设计比较随意,通常包含各类广告、设计人员的注释以及版权申明等同网页主题无关的信息.
这些"噪音"影响了网页分类的质量,因此,在中文网页自动分类的过程中,需要自动地从中文网页中清除"噪音".
尽管网页在视觉上给人比较凌乱的感觉,但是通过仔细观察网页的源代码,我们会发现,HTML网页中的内容是按树状层次结构组织的,这个树状结构描述的是网页内容的结构信息,但是从结构信息中蕴含着一定的内容相关性和内容重要性信息.
此外,在HTML标准中定义了一套标签用来特殊显示其包含的内容(比如:字体变大、粗体、斜体、以超链形式显示,等等),这类标签也隐含着一定的重要性信息[张志刚],图3-1给出了一个典型的网页HTML源代码.
本文把所有的HTML标签分成两类:一类影响网页内关键词的权重,如等;另一类不影响,如等.
表3-1列出了选用的HTML标签及其相应的权重.
本文使用表3-1来调整网页内一个关键词的权重.
应用公式(3-1)计算一个关键词每次出现时的权重;应用公式(3-2)计算一个关键词在整个网页中的权重.
其中W0是一个候选特征项的初始权重.
W(tagi)为一个关键词周围第i个标签的第3章中文网页内噪音的自动清除39权重.
如果W0等于1并且W(tagi)等于0,那么W(t)就是t的文档频率.
)()(100∑=+=niitagWWtW(3-1)∑==10)()(niitWtW(3-2)表3-1选用的HTML标签及其相应的权重TagW(tag)TagW(tag)422222222422224221111112本章将利用中文网页的结构信息以及内容信息,并结合网页分类技术,自动地从中文网页中清除"噪音",进而改进网页分类的质量.
本章的如下部分是这样安排的:第3.
2节为本章的主体部分,详细介绍了从中文网页中自动清除"噪音"的算法;第3.
3节给出了实验及其结果分析;第3.
4节介绍了与本章相关的研究;第3.
5节总结了本章并指出了进一步的工作方向.
3.
2噪音清除算法下面详细介绍从中文网页内自动清除"噪音"的算法,为方便起见这第3章中文网页内噪音的自动清除40里称之为NR算法.
Step1.
根据网页源码创建标签树.
网页是由超文本设计的,因此可以根据层次的HTML标签自动创建标签树.
通过统计可以知道,、、、、五种标签是最为常用的容器标签[张志刚].
给定一篇HTML网页,顺序整理出上述5种标签的嵌套关系就得到了对应的标签树的主干.
而后,在上述得到的标签树中每个内容块内整理超链和重要信息标签的信息,并将其作为该内容块的数据信息.
这样,就构造了一棵完整的标签树,标签树中每个结点都有类型和属性集两组描述性信息,以及超链集和重要标签集等数据信息,图3-2显示了一个典型标签树的构成.
图3-1一个网页的HTML源代码图3-2一棵典型的标签树Step2.
识别相关和不相关子树.
整个网页的标签树由两部分构成:相关和不相关子树.
本文这里首先使用2个特殊规则来识别不相关子树:规则3-1.
最后的和标签对以及注释信息.
因为注释信息是网页设计人员为编辑网页的方便加上的注释,而用户通过浏览器是无法看到.
因此,可以直接删除""之间的不相关子树.
版权信息通常被放置在最后或标签对中,因此,放置在最后的和标签对中的子树通常是不相关的.
.
.
.
htmlheadbodytabletrtdatrtdatabletrtrtdatrtdatabletr相关子树不相关子树第3章中文网页内噪音的自动清除41规则3-2.
TABLE标签的大小和位置.
不相关子树通常被放置在网页的左边或右边,并且TABLE尺寸的比较小,介于10%与25%之间.
网页内通常包含各种超链接,其中部分超链接同网页主题相关,部分超链接同网页主题不相关.
因此,需要过滤掉同网页主题不相关的超链接.
本文在这里主要利用了超链接的anchortext.
anchortext是对超链接所指向网页简短、概要的说明,在一定程度上体现了所指向网页的内容.
由于超链接通常集中在一个子树中,而且位于同一子树中的超链接通常具有相同的主题.
因此,超链接的选取是通过比较每个子树内的anchortext集合与网页正文的相似度来决定该块中链接的取舍.
对于网页正文的判断,本文的处理比较简单:包括的文字最多而且HTML标签比较少的子树内文本为该网页的正文.
本文应用第1章的公式(1-4)来计算每个子树内的anchortext集合与网页正文的相似度.
这里需要说明的是,这里侧重的是一张网页内部各个内容块之间的相似度比较,而不是网页间的相似度比较.
因此,在关键词权值的计算方法上,我们更侧重关键词在一张网页内部的重要性,而不是关键词在一个文档集合内基于统计的重要性.
Step3.
删除不相关子树.
删除第2步识别出来的不相关子树.
3.
3实验结果及其分析3.
3.
1实验设置为了验证NR算法对中文网页分类的影响,本文实现了一个中文网页分类器.
该分类器的设计方案除了预处理部分不同外,其它的同本文第2.
2.
1节的方案.
具体为:分类算法为kNN,实验中k取20;无特征选取处理;无阈值策略.
并且在识别无关超链接时,比较每个子树内的anchortext集合与网页正文的相似度也使用该分类器.
3.
3.
2实验结果图3-3和图3-4直观地显示了NR算法的效果:图2-3所示的网页在处第3章中文网页内噪音的自动清除42理前包括版权所有信息,无关的超连接等.
应用NR算法处理之后,仅剩下正文部分.
相对而言,图3-4要比图3-3要"干净"多了,由此可见,NR算法的效果是非常明显的.
图3-3处理前的网页图3-4应用NR算法处理后的网页下面考察NR算法对中文网页分类算法的影响.
这里使用的测试网页为本文第2.
2.
2节介绍的训练样本集,包括12336个训练网页实例和3269个测试网页实例.
在实验中,对于同样的网页实例,一组实验中使用NR算法进行"噪音"清除处理,另一组实验中不进行处理.
图3-5对两组实第3章中文网页内噪音的自动清除43验结果进行了对比,其中,横轴为类别代码,分别代表的类别名称请参见第2章的表2-1.
从图3-5可以看出NR算法的效果是非常明显的,经过NR算法处理后的所有类别的分类结果均比没有进行处理的分类结果有所上升.
由于这里并没有进行分类的任何改进,所以,图3-5所示的提高完全是进行"噪音"清除得到好处.
图3-5NR算法对中文网页分类质量的影响3.
4相关研究文献[Yang95]提出了通过去掉文档中的噪音内容来提高文档分类质量的方法.
但是该方法主要是针对普通文档的,所以对于网页这个特殊对象这个方法就不能使用了.
[LH02]提出了一个利用网页结构信息去除网页中噪音内容的方法.
实验证明该方法是有效的,但该方法必须局限在基于同一个模板的网页集,而Web上的网页模板不计其数,该方法显然不够通用.
本文通过利用中文网页的结构信息和内容信息,并结合中文网页自动分类技术等3个方面的因素,实现了自动从中文网页中自动清除"噪音".
第3章中文网页内噪音的自动清除443.
5本章小结同普通文档相比,网页的设计比较随意,通常都包含大量"噪音",这些"噪音"影响了网页分类的质量.
为此,本文提出了一种自动从中文网页中自动清除"噪音"的方法.
该方法通过利用中文网页的结构信息和内容信息,并结合中文网页自动分类技术,实现了自动从中文网页中自动清除"噪音".
实验结果表明,该方法不仅可以有效地从中文网页中自动清除"噪音",而且,还可以有效地改进中文网页分类器的分类质量.
第4章从搜索引擎日志中学习新词45第4章从搜索引擎日志中学习新词分词是有效地进行中文信息处理的前提和基础.
因此,为了有效地实现中文网页的自动分类,分词是对中文网页进行预处理的过程中一个必不可少的处理.
词典规模是影响分词准确率的最重要的因素之一,而分词使用的词典通常是不完备的,因此,需要通过自动学习词典中未登录的新词来不断扩大词典的规模.
本章通过提高分词的准确率来最终提高中文网页分类的质量.
针对直接从面向领域的专业语料库中学习新词所面临的困难,本文提出了一种从搜索引擎日志中学习新词的方法.
同传统的方法相比,该方法具有学习效率和准确率高、不受领域限制、实现简单、易于推广等优点.
该方法的基本思想是,根据用户查询词的长度分布特性和频度分布特性以及分词系统的先验知识,从所有汉字组合模式中尽可能地排除无效的组合模式,从而提高了学习新词的效率和准确率.
实验结果表明,该方法可以有效地从搜索引擎日志中学习新词,为新词的自动学习提供了一种新的思路.
4.
1引言中文不同于英文,句子中的词语之间没有天然的形态间隔,因此需要按照一定的规范进行词语的切分,即分词.
分词是有效地进行中文信息处理的前提和基础.
从1980年以来,自动分词一直是中文信息处理领域研究的热点和难点.
分词技术在搜索引擎、信息检索等领域得到了广泛的应用[LLWC00].
研究表明,词典规模是影响分词准确率的最重要的因素之一.
分词使用的词典通常是不完备的,无论是常见的通用词典,还是面向领域的专业词典都不可能把所有的词条都收录进去[王继成00].
而且,中文词汇作为一个动态开放的集合,不断地会有大量的新词涌现.
尤其在Web环境下,不时会出现各种时髦的反映时代特征的新词汇.
人工维护方式的词典的更新速度往往滞后于新词的产生速度.
因此,需要通过快速而且准确第4章从搜索引擎日志中学习新词46地自动学习词典中未登录的新词来不断扩大词典的规模.
目前,在自动识别或者学习词典未登录新词,特别是面向领域的专业词汇以及人名、地名、机构名等专有名词等方面,已经有了一些比较有意义的研究工作.
文献[黄宣菁96]利用CHI统计方法从领域语料库中自动生成领域专业词典;文献[郑家恒00]利用语料库以及辅助的局部规则实现了中文人名的自动识别;文献[张小衡97]从语料库中归纳出机构名称的构造规则,实现了机构名的自动识别.
这些方法的共同点是直接从面向领域的专业语料库中学习新词.
本文利用用户查询词的分布特性以及分词系统的先验知识,提出了一种从搜索引擎日志中学习新词的方法.
同直接从面向领域的专业语料库中学习新词的方法相比,这种从搜索引擎日志中学习新词的方法具有以下三个方面的优点:(1)学习新词的效率、准确率高.
直接从整篇的文章中学习新词往往需要复杂的词法、句法分析,处理起来比较复杂,新词学习算法的复杂度高.
而搜索引擎日志文件中用户的查询词(本章所指的用户查询词,不是指具有语义或语法功能的独立词条,而是指用户输入的整个查询字符串)通常比较简短,几乎没有完整的句子,只需做一些的简单处理,即可方便地学习新词.
而且,如果用户查询词在词典内没有收录,很有可能就是潜在的新词.
因此,学习新词的准确率也比较高.
(2)能够及时地学习到最近出现的新词,而且这些新词不受领域的局限.
搜索引擎日志及时地反映社会时尚和热点,其中包含了大量具有时代特征的新词.
而且,搜索引擎为大量的Web用户提供服务,不同用户的需求千差万别,这些查询词面向几乎所有领域,不受领域的局限.
而专业语料通常是面向某个领域的,当需要应用到其它的领域时需要重新训练新词学习算法.
并且,当应用环境没有明确的领域特征时,应用专业语料来学习新词就比较困难.
(3)客观性.
语料库的收集和整理往往需要耗费大量的人力和物力,通常是一件比较费时的工作.
整理出来的语料样本还难免受到人为主观因素的影响而出现偏差.
而搜索引擎用户日志的收集过程是搜索引擎系统自动完成的,无须人工的干预,它客观地反映用户检索行为的特性.
本文将第4章从搜索引擎日志中学习新词47在第4.
2节详细讨论用户查询词的特征分布,并根据这些特性来设计新词的学习策略.
本章的如下部分是这样安排的:第4.
2节详细地介绍了一种从搜索引擎日志中学习新词的方法.
该方法的主要特色是充分利用了用户查询词的分布特性以及分词系统的先验知识,从所有汉字组合模式中尽可能地排除无效的组合模式,从而提高了新词学习的效率和准确率;第4.
3节通过实验验证了该方法的有效性;第4.
4节分析了分词字典的规模对中文网页分类质量的影响;第4.
5节简要地讨论了与本文相关的研究;第4.
6节对本章进行了总结,并指出了未来的工作方向.
4.
2一种从搜索引擎日志中学习新词的方法4.
2.
1基本思想词条是汉字字符的一种基本组合模式.
在所有可能的汉字组合模式中,只有很少一部分组合模式才能产生有确定语义或语法功能的词条,绝大多数的组合模式都是无效的.
这些无效的组合模式不仅需要花费大量的处理时间,降低了新词的学习效率,而且由这些无效的组合模式产生的新词为"噪音",还需要再次把它们过滤掉.
因此,本文的基本思想是在新词的学习过程中,尽可能地减少无效的组合模式,而仅保留那些最有可能是有效的组合模式.
为做到这一点,主要依据有两个:(1)已有分词系统(这里使用的分词系统由北京大学计算语言所开发,该版本主词典包括46731个基本词条,用户字典中包括283个基本词条)的先验知识.
在获取有效组合模式的过程中,那些已经被分词系统作为基本词条的组合模式可以直接被过滤掉,仅需保留那些被分词系统未识别的模式.
这样,经过分词处理,可以过滤掉大量已知的组合模式;(2)用户查询词的分布特性.
搜索引擎日志中记录的用户查询词具有自身的分布特性,在获取有效组合模式的过程中,可以充分利用这些特性来尽可能地减少无效的组合模式.
根据上述的基本思想,图4-1给出了从搜索引擎日志中学习新词的一第4章从搜索引擎日志中学习新词48般步骤.
预处理查询词分布特性,分词组合搜索引擎日志候选新词模式模式筛选新词123图4-1从搜索引擎日志中学习新词的一般步骤第一步:预处理.
图4-2给出了一段"天网"搜索引擎的用户查询日志.
从图4-2可以看出,尽管用户的一次查询过后,系统自动记录了相关图4-2"天网"搜索引擎的用户查询日志举例的5项内容,但是本文关心的仅有一项:用户的查询词.
用户提交的查询MonSep216:22:132002//查询时间202.
197.
186.
101//查询IPCache//查询结果是否在cache中命中软件下载//查询词1//用户在返回结果中的翻页次数MonSep216:22:14200261.
243.
188.
195Cache走遍美国1MonSep216:22:142002210.
45.
144.
16Database主板接口1第4章从搜索引擎日志中学习新词49词可以分成三类:中文词、英文词、中英文混合词.
本文这里处理的是中文新词学习,因此首先将所有的英文词汇直接过滤掉.
至于中英文混合的查询词,由于分词系统的词典不能登录这类中英文混合词,对这类新词的学习没有意义,因此也直接过滤掉,接着统计每一个用户查询词出现的频率,并过滤掉频率较低的查询词(本文在实验中取的最小频率为5次).
过滤低频词有两个好处:其一是,对于那些只有极少数人关心的生僻词汇,本文不加入到词典中,因为词典的过度膨胀会在一定程度上降低系统运行的效率.
其二是,有很多用户不能十分确定要检索的中文词的正确拼写,或者在检索时不小心输入错误,如将"搜狐"输入成为"搜虎".
通过词频的筛选,本文可以在一定程度上解决这个问题.
第二步:根据用户查询词的分布特性以及分词的结果,从所有组合模式中仅保留那些最可能为有效的组合模式.
然后根据这些组合模式生成候选新词.
第三步,最后根据不同的组合模式的筛选策略,从候选新词中选择最终的新词.
4.
2.
2用户查询词的分布特性分析搜索引擎日志记录了用户的访问历史,通过对这些用户检索行为的统计分析,可以从中获取用户查询词的分布特性,然后利用这些特性来尽可能地减少无效的组合模式.
为了保证分析得到的分布特性具有普遍性,而不是一种偶然现象,本文分别以"天网"搜索引擎收集的三批日志文件数据为分析对象:第一批是从2000年11月20日至2001年9月4日期间的日志数据(共9,256,772条记录);第二批是从2001年12月20日至2002年2月3日期间的日志数据(共9,394,200条记录);第三批是从2002年7月1日至2002年8月14日期间的日志数据(共6,391,282条记录).
(1)用户查询词的长度分布特性用户查询词长度的分布情况如图4-3所示.
其中横轴为查询词的长度(个汉字),纵轴为所占比例.
从图4-3可以看出,这三批数据得到的用户第4章从搜索引擎日志中学习新词50查询词长度分布是完全一致的:(1)用户的查询词通常都是非常简短的,92%以上的用户查询词的长度不超过8个汉字;(2)65%以上的查询词的长度不超过4个汉字.
在所有查询词中,4个汉字长的查询词最多,占28%以上.
2个汉字长的查询词次之,占22%以上.
在用户查询词中很少出现完整的句子,分析处理起来要比普通语料的费用要小的多.
而且,这些简短的查询词高度浓缩地反映了用户的查询意图,几乎不包含其它无关的信息,因此从中学习新词也准确的多.
图4-3用户查询词的长度分布图(2)用户查询词的频度分布特性本文利用上述的三批数据统计了用户查询词的频度分布情况.
为了说明问题方便,需要引入一些代号:n表示所有不同的查询词的个数;S表示n个查询词按频率从高到低排列后组成的序列,S={S1,S2,…,Sn},Si表示第i个查询词;Ci表示Si对应的查询次数,C表示由Ci构成的序列,C={C1,C2,…,Cn}.
把这n个查询词分成20个等份,然后根据公式(1)分别计算在前k(1≤k≤20)个不同等份内这些查询词出现的次数占总的第4章从搜索引擎日志中学习新词51查询次数的比例P:P=∑*=20/1nkiiC∑=niiC1(4-1)最后得到的结果如图4-4所示(这里本文仅保留了1≤k≤5的结果,因为这段区间内查询次数比例增长最快).
从图4-4可以看出,搜索引擎日志中图4-4用户查询词的频度分布图用户查询词在频度分布上是高度集中的:前5%的高频词占据了64%以上的总查询次数;前20%的查询词占据了83%以上的总查询次数.
以第三批数据为例,在639.
1万次的用户查询中,共有447,1万次中文查询,而这些查询词中仅包含了43.
4万不同的查询词,频率大于等于5次的仅有11.
9万个.
本章的实验结果同文献[王建勇01]得到的结论一致.
因此,本文可以利用查询词的频度分布特性来大量地减少模式提取过程中的扫描字符串的次数:不需要逐条分析所有查询词,而是预先把所有相同的查询词进行第4章从搜索引擎日志中学习新词52合并.
而在一篇完整的文档中,很少会有一段文字多次重复出现的现象.
因此,这也是普通语料所不能具备的特性.
4.
2.
3组合模式的提取为了从所有汉字组合模式中尽可能地排除无效的组合模式,提高新词学习的效率和准确率,本文根据用户查询词的分布特性以及分词系统的先验知识,在提取汉字的组合模式的过程中,遵守了以下两个规则:规则4-1直接删除已经被分词系统作为单个词条的已知组合模式,并且在模式提取的过程中不破坏已有的基本词条.
例如,"流星花园"这个查询词,被分词系统分成"流星"、"花园"两个基本词条.
如果采用"正向增字匹配方法"[王继成00],4个字的所有可能组合形式将有1+2+3+1=7种可能,但是根据规则4-1,最后只有"流星花园"4个字连在一起这一种组合模式可能为有效的,其它模式均被视为无效.
规则4-2如果查询词的长度n≤4个汉字字符长,在日志中出现的频率比较高,而且被分词系统分割成单个汉字的组合,那么由这些单个汉字一起组成的词就作为一个侯选新词,而其它的组合则被视为无效.
例如,"下载"这个查询词的长度为2,频率为50401次(第三批日志数据),被分词系统分成"下"、"载"两个单字,那么在组合模式的提取过程中,根据规则4-2,本文提出的新词学习方法就会把它直接作为一个新词"下载"的候选词.
结合规则4-1和规则4-2,下面给出从搜索引擎日志中提取汉字组合模式的算法:第一步,对用户的查询词S进行分词处理.
设分词结果为S=(S1,S2,…Sm).
其中m为从S中分词得到的词条个数,Si为第i个词条(1≤i≤m);第二步,根据用户查询词S的长度n以及m的值,并结合规则4-1和规则4-2,从所有可能的组合模式中选择有效的组合模式.
根据分词结果,仅保留m≠1的组合模式.
对于m=1的情况,根据规则4-1直接过滤掉.
第4章从搜索引擎日志中学习新词53下面根据n的取值情况分成四种情况讨论:(1)n=2.
当m=2时,根据规则2,整个查询词作为一个候选新词;(2)n=3.
当m=3时,根据规则2,整个查询词作为一个候选新词;当m=2时,根据规则4-1,不拆分已有的组合模式,所以也只有一种可能,整个查询词作为一个词条.
(3)n=4.
当m=4或m=2时,根据规则4-2,整个查询词作为一个词条;当m=3时,根据分词的结果,为产生的一个基本词条加上"前缀"或"后缀"来组成新词.
(4)n>4.
从首字符开始,每次取4个字符,然后调用n=4时的处理方法进行模式提取.
最后再根据余下部分的长度分别调用相应的方法.
图4-4给出了从搜索引擎日志中提取汉字组合模式算法的伪码表示(其中∪表示把两个词条合并成一个词条的操作符):图4-5一种从搜索引擎日志中提取汉字组合模式的算法输入:经过预处理后保留下来的所有用户查询词输出:候选新词集ω算法:1.
count←经过预处理后保留下来的所有用户查询词的个数2.
while(count>0)3.
取一个查询词S,n←S的长度,m←S分词后得到的词条数,mi←第i个词条4.
if(NOTm=1)5.
if(n=2ORn=3)S∈ω6.
elseif(n=4)7.
if(m=2ORm=4)S∈ω8.
elseif(m=3)S∈ωOR(m1∪m2)∈ωOR(m2∪m3)∈ω9.
elseif(n>4)10.
按正向增字的方法,S←取4个字符,GOTO311.
count←count–1第4章从搜索引擎日志中学习新词544.
2.
4候选词的筛选尽管已经充分利用了分词系统的先验知识以及用户查询词的分布特性,但是4.
2.
3给出的组合模式选取算法是建立在统计规则的基础之上,以及由于分词系统本身不是完备的,因此并不能保证得到的组合模式都是有效的,需要把无效的组合模式过滤掉.
本文把由无效组合模式形成的候选词分成两类:"伪词条"和"伪组合词".
(1)"伪词条"的筛选所谓"伪词条"就是不能形成真实词条的候选词.
"伪词条"的产生通常是由于在组合模式提取的过程中,保留了无效的组合.
根据实际实验的观察,可以发现这类"伪词条"的频率通常都不高.
因此,本文在实验过程中,取所有候选新词词频的平均值作为筛选"伪词条"的阈值.
根据这个阈值就可以把"伪词条"过滤掉,但是这种方法同时也会过滤掉一些频率比较低的正确词条.
(2)"伪组合词"的筛选"伪组合词"就是在模式提取过程中,把不能构成真实组合词的两个词放在一起作为一个组合词的候选词.
例如,根据4.
2.
3节的组合模式提取算法,"动画下载"下被作为一个候选新词.
但是,"动画"和"下载"已经被单独作为一个独立的词条,而且"动画下载"一起出现的频率远小于"动画"或"下载"的频率,因此把"动画下载"作为一个组合词是不合理的.
为了筛选掉这类"伪组合词",本文分别计算每个组合词的"前半部分"、"后半部分"和"整体"的出现频率,分别用freq(S1)、freq(S2)和freq(S)表示,其中S=S1US2.
根据公式(4-2)来计算三者之间的差异:Diff=)()()(21SfreqSfreqSfreq(4-2)(1)如果freq(S1)>>freq(S2),那么S1最可能是基本词条;(2)第4章从搜索引擎日志中学习新词55如果freq(S1)<在实验中,本文分别为Diff取不同的阈值:(1)当Diff≥2时,"前半部分"S1为有效词条;(2)当Diff≤-2时,"后半部分"S2为有效词条;(3)当-24.
2.
5算法分析为了讨论问题的方便,需要引入一些记号.
假设用户的查询词为一个字符串S,长度为n,中文词条的最大有效长度为k.
如果采用所有汉字组合模式的穷举法,也就是把所有可能的汉字组合模式都穷举出来,然后对每一种组合来匹配查询词S,对于6763个一、二级汉字,两个汉字的组合模式有6763*6763种,三个汉字的组合模式有67633种,依次类推,k个汉字可能产生的组合模式有∑=kii26763种.
如k取4,那么约有2.
1*1015种.
很显然,通过匹配如此多的汉字组合模式来学习新词是不现实的.
下面分析本文新词学习算法的复杂度.
与上述穷举法不同,本文不是试图穷举所有的汉字组合模式,而是仅考虑在查询词中可能出现的组合模式.
为了尽可能的减少了扫描匹配字符串的次数,本文采取了以下措施:(1)在预处理的过程中,合并大量重复的查询词,而不是逐条分析查询词;(2)在组合模式提取的过程中,对于n≤4的查询词,首先进行分词处理,然后根据分词结果和查询词的分布特性来尽可能地减少无效的组合模式;对于4根据查询词的长度分布以及不同长度查询词的字符串匹配次数,可以根据公式(4-3)估算本文组合模式提取算法的复杂度:O(S)=∑=82)()(iiiiSOSP(4-3)其中:Pi(Si)为不同长度查询词的长度分布(见图4-3);O(Si)为不同长度查询词需要的字符串匹配次数.
当i=2或i=3时,需要匹配的次数为常数1;当i=4时,根据分词结果,需要匹配的最大次数为常数3;当4最后代入公式(2),求得O(S)≈3.
4次.
从上面的分析可以看出,本文使用的组合模式提取算法的复杂度维持在常数级,这主要是由于查询词的长度分布特性决定的.
4.
3实验结果及其分析4.
3.
1新词学习方法质量的测试为评价第4.
2节提出的新词学习方法,本文借鉴信息检索领域查准率和查全率的定义[Yang99],分别给出以下定义:符号说明:令a=学习得到的新词中包含的正确词条数;b=学习得到的新词中包含的错误词条数;c=日志中包含而没有被学习出来的新词数.
于是,可以得到新词学习方法的"学准率"p和"学全率"r:定义4-1"学准率"p=baa+,即学习得到的新词中包含的正确词条数与学习得到的新词总数的比值.
定义4-2"学全率"r=caa+,即学习得到的新词中包含的正确词条数与日志中包含的所有新词数的比值.
根据定义4-1和定义4-2,人工获得a的值相对容易,而人工获得c的值要困难的多,这需要把所有的用户查询词人工地分词,工作量巨大,实际操作比较困难.
因此,本文随机地从预处理后保留的用户查询词中选择3000个不同的查询词进行人工地分词,删除分词系统已经作为一个独立词条的词后,得到743个新词,然后同系统自动学习新词的结果进行比较.
本文将自动学习得到的821个新词按频率从高到低排列,并分成8个等份,并分别统计前k(1≤k≤8)个等份的a、b、c值之和,然后根据定义4-1第4章从搜索引擎日志中学习新词57和定义4-2,分别求前k个等份对应的"学准率"p和"学全率"r值.
这样就得到了8个测试点(从左到右分别为第1到第8个测试点),最后得到本文新词学习方法的"学准率"p和"学全率"r曲线图,如图4-6所示,其中横轴表示"学全率"r,纵轴表示"学准率"p.
从图4-6可以看出,从搜索引擎日志中学习新词可以取得90%以上的"学准率",对于高频词,最高可以达到97%的准确率.
同时,"学全率"也可以达到比较理想的结果.
图4-6新词学习方法的"学全率-学准率"曲线图理论上,新词学习方法可以达到100%的"学准率"和100%的"学全率",但是实际的学习方法只能够无限地逼近这一理想值.
就"学准率"而言,应用本文提出的方法可以非常准确地从日志中学习出诸如"下载"、"短信"、"美眉"之类的时髦词汇.
但是,有时也会出现学习错误的情况,也就是不能让"学准率"p达到100%.
例如,由于用户不能确定到底是"璩美凤"还是"虞美凤",导致两者的查询频率都很高,被系统同时作为了新词,而从常识来看,作为台湾"光盘"事件的主角"璩美凤"才是一个有第4章从搜索引擎日志中学习新词58效词汇.
就"学全率"而言,由于本文提出的方法把频率作为是否作为一个新词的主要依据,因此就会把一些低率词,而实际上为一个有效词条的候选词过滤掉,因此也不能让"学全率"r达到100%.
例如,由于"玄奘"的频率只有有限的5次而没有被学习出来,图4-7给出了一些利用本文提出的方法从搜索引擎日志中自动学习的得到的新词的一些例子.
图4-7从搜索引擎日志中自动学习得到的新词的举例4.
3.
2新词学习方法效率的测试本文使用第三组日志数据测试新词学习方法的效率.
分别取得了从100万到600万条日志记录的6组数据,实验结果如图4-8所示.
从图4-8可以看出,新词学习算法的复杂度与日志记录数成线性关系.
经实验测试,新词学习算法的主要开销在预处理和分词阶段,约占总开销的85%以上.
下载乱伦寻秦记破解考研走光三级片手机清华偷窥课件大史记黑客天龙八部攻略五笔动画一夜情周杰伦主页网站屏保刘德华天网美眉美国江泽民专升本舒琪周星驰北京站中关村封神榜自慰深圳法轮功杀毒物流香港孙燕姿宋祖英网址声卡古龙王菲网页路由器宽带搜狐十六大西柏坡控件考博短信六合彩中考搞笑任贤齐齐天大圣哈利波特第4章从搜索引擎日志中学习新词59图4-8新词学习方法的时间复杂度4.
4分词字典的规模对分类质量的影响本章介绍的新词学习方法的效果,不仅体现在新词学习方法本身的学习质量和学习效率,而且还体现在对中文网页分类质量的影响上,本文通过从搜索引擎日志中学习得到的新词来不断地扩充分词字典的规模.
下面用实验来考察分词字典的规模对分类质量的影响.
为了真实地反映分词字典的规模对分类质量的影响,本文继续使用第2章第2.
2.
1节中的实验设置来安排两组实验:对网页内容除了中文分词没有其他预处理、没有进行特征选取、对分类结果没有应用阈值策略、共同使用kNN分类算法,也就是除了字典规模不同以外,其他实验条件完全相同.
其中一组实验使用的字典包括46731个基本词条,这里使用"基本字典"表示;另一组实验使用的字典包括66159个词条,其中19428个词条是通过从搜索引擎日志中学习得到的,这里使用"扩充字典"表示,实验结果分别如表4-1所示.
第4章从搜索引擎日志中学习新词60表4-1字典的规模对分类质量的影响Micro-F1Macro-F1基本字典0.
82660.
7600扩充字典0.
83310.
7814从表4-1可以看出,通过扩充分词字典的规模后,无论是宏观F1值还是微观F1值都有一定提高,其中宏观F1值提高了两个百分点以上,由此可见,适当地扩充分词字典的规模可以提高中文网页的分类质量.
4.
5相关研究如同本章4.
1节引言部分介绍了那样,在自动识别或者学习词典未登录新词,特别是面向领域的专业词汇以及人名、地名、机构名等专有名词等方面,已经有了一些比较有意义的研究工作[黄宣菁96][郑家恒00][张小衡97],这些方法的共同点是直接从面向领域的专业语料库中学习新词,其主要面临的问题有:⑴学习新词的效率、准确率低.
直接从整篇的文章中学习新词需要复杂的词法、句法分析,处理起来比较复杂,新词学习算法的复杂度高,当面对海量的网页信息时,这些方法有时是无能为力的.
而且,由于需要复杂的词法、句法分析,而中文语言中存在大量的歧义问题,因此新词学习的准确率也比较低.
⑵新词的学习受到领域的局限.
这种利用专业语料的学习方法,通常是面向某个领域的,当需要应用到其它的领域时需要重新训练新词学习算法.
并且当应用环境没有明确的领域特征时,应用专业语料来学习新词就比较困难,因此这种面向领域的新词学习方法的应用面是十分有限的.
⑶主观性.
专业语料库是通过人工方式来收集和整理的,因此整理出来的语料样本难免受到人为主观因素的影响而出现偏差,最终必然会影响到新词学习的准确率.
因此,为了克服直接从专业语料库中学习新词时所面临的困难,本文提出了一种从搜索引擎日志中学习新词的方法,该方法为为新词的自动学第4章从搜索引擎日志中学习新词61习提供了一种新的思路.
4.
6本章小结针对直接从面向领域的专业语料库中学习新词所面临的困难,本文提出了一种从搜索引擎日志中学习新词的方法.
同传统的方法相比,该方法具有学习效率和准确率高、不受领域限制、实现简单、易于推广等优点.
该方法的基本思想是,根据用户查询词的长度分布特性(92%以上的用户查询词的长度不超过8个汉字;65%以上的查询词的长度不超过4个汉字;在所有查询词中,4个汉字长的查询词最多,占28%以上.
2个汉字长的查询词次之,占22%以上)和频度分布特性(搜索引擎日志中用户查询词在频度分布上是高度集中的.
前5%的高频词占据了64%以上的总查询次数;前20%的查询词占据了83%以上的总查询次数)以及分词系统的先验知识,从所有汉字组合模式中尽可能地排除无效的组合模式,从而提高了学习新词的效率(新词学习算法的复杂度与日志记录数成线性关系)和准确率(从搜索引擎日志中学习新词可以取得90%以上的"学准率",对于高频词,最高可以达到97%的准确率).
实验结果表明,该方法可以有效地从搜索引擎日志中学习新词,为新词的自动学习提供了一种新的思路.
本文通过从搜索引擎日志中自动学习词典中未登录的新词来不断扩大词典的规模,不但提高了分词系统的准确率,而且还提高了中文网页分类的质量.
进一步的研究工作包括:(1)考察分词系统对搜索引擎性能和质量的影响;(2)利用日志信息更新迅速的特点,实现增量式学习.
第5章中文网页自动分类技术在搜索引擎中的应用62第5章中文网页自动分类技术在搜索引擎中的应用在本文的第2至第4章主要研究了中文网页自动分类技术本身,即:如何应用有指导的机器学习方法实现大规模中文网页的自动分类.
本章将关注中文网页自动分类技术在搜索引擎系统中的一个具体应用,即:如何应用中文网页自动分类技术在"自动式"搜索引擎"天网"中同时提供目录导航服务.
5.
1引言如何帮助用户从Web信息海洋中快速地获取其需要的信息是Web服务的核心问题之一.
目前的解决方案是利用搜索引擎为用户提供Web文档的快速检索.
[CNNIC]调查显示,51.
3%的用户最常使用的网络服务是搜索引擎,仅次于电子信箱服务.
57.
5%的用户通过搜索引擎来获知新网站,在获知新网站的主要途径中占第一位.
由此可见搜索引擎服务是一种非常重要的网络服务,越来越多的用户通过它来获取信息.
目前提供Web导航服务的系统主要可以分为两大类(也有人把元(Meta)搜索引擎作为一类.
但从严格意义上讲,它不是搜索引擎,因为它没有自己的数据).
第一类是目录式导航服务系统.
它主要是通过具有专业知识的网页编辑人员人工地对网页进行精选,建立一个索引目录,向用户提供目录导航服务.
用户可以沿着分类目录的层次结构,逐步进入自己感兴趣的主题,进而找到所需的信息.
这类系统的特点是提供的网页准确率高,但是系统的网页覆盖率小,系统维护的网页数量有限.
其典型代表是Yahoo!
的目录系统[YAHOO].
第二类是"自动式"搜索引擎系统.
它通过被称为"Spider"的程序自动地在网上沿着超文本链接递归地访问、收集Web网页,分析页面的内容,生成索引和摘要,并向用户提供Web查询页面,然后根据用户的查询请求在索引库中查找相关信息在网上的位置,最后将查询结果按照相关度排序后返回,帮助用户尽快地找到所需的信息.
这类系统的优点是系统维护的网页数量巨大,系统的网页覆盖率高,但是检索的第5章中文网页自动分类技术在搜索引擎中的应用63准确率相对比较低,其典型代表是Google[Google].
下面简要地比较一下这两种搜索引擎系统.
⑴"自动式"搜索引擎由系统自动地收集、分析和处理网页,无需人工的参与,因而它索引的网页数多,信息量大,并且能够定期或增量地收集网页,更新索引库的内容,向用户提供最新的Web网页信息.
但是,传统的"自动式"搜索引擎是基于关键词匹配的方式进行全文检索的,检索结果对用户而言不够理想.
当用户不能确切地知道自己感兴趣的网页中含有哪些关键词时,传统的"自动式"搜索引擎就无能为力了.
否则,返回的结果很可能和用户的实际需求"风马牛不相及".
如果搜索引擎能够对收集的网页进行自动分类,用户就可以沿着层次目录逐步缩小搜索范围,最终找到自己感兴趣的主题.
这样就能将许多无关网页排除在返回结果之外,大大提高检索结果的准确率,同时也可以方便用户的使用.
因此,Web用户希望"自动式"搜索引擎同时能够提供目录导航服务⑵目录式搜索引擎支持基于分类目录的检索.
目录式搜索引擎对收集的网页采用人工分类.
由于这种人工方式对网页内容的理解比较准确,因此查询的准确性优于"自动式"搜索引擎.
当用户对某个领域感兴趣但并不熟悉这个领域的关键词时,这种查询方式能很好地为用户提供服务.
但是,由于人工分类效率低,网页更新困难,目录式搜索引擎在索引的网页的规模上受到了很大的限制.
Google等"自动式"搜索引擎索引的网页数量早以突破十亿级,yahoo!
维护的网页规模相对而言要小得多.
由上述的分析可以看出,这两类搜索引擎都存在着各自的优缺点:目录导航式搜索引擎的查准率较高,但维护的网页规模有限;"自动式"搜索引擎维护的网页规模较大,但检索的查准率相对较低.
那么能否研制一种搜索引擎同时具备上述两类搜索引擎的优点即系统维护网页规模比较大而且具有较高的服务质量这是本章要研究的主要内容.
本章将讨论如何利用中文网页自动分类技术来解决传统的"自动式"搜索引擎面临的问题.
事实上,如何在传统的"自动式"搜索引擎中同时提供目录导航服务,已成为搜索引擎技术的一个新的发展方向和研究热点之一.
本章的如下部分是这样安排的:第5.
2节为本章的主体部分,详细介绍了"天网"目录导航服务系统的设计与实现.
首先给出了"天网"目录导航服务系统的体系结构,接着介绍了系统的一个运行实例;第5.
3节介第5章中文网页自动分类技术在搜索引擎中的应用64绍了相关的研究工作;第5.
4节对本章进行了总结,并指出了未来的工作方向.
5.
2"天网"目录导航服务"天网"搜索引擎是一个典型的"自动式"搜索引擎,主要处理中文网页.
自从1997年10月正式在CERNET上提供服务以来,"天网"系统体系结构从集中式发展到分布式,无论收集的网页数量还是提供的服务质量都已发生了巨大的变化.
目前平均每天提供10万次以上的服务.
其索引的网页数在国内的搜索引擎中名列前茅,查询响应速度极快,受到了广泛的好评.
但是也有一些用户抱怨"天网"的检索结果不够准确,常常包含大量的无关或无用的结果.
还有一些用户在希望"天网"能够提供目录导航服务,通过逐步缩小查询范围,快速而且精确地定位自己感兴趣的网页.
因此,为了提高"天网"的查准率并向用户提供目录导航服务,本文应用有指导的机器学习技术实现了中文网页的自动分类,在没有减小网页规模的情况下,在"自动式"搜索引擎中同时提供目录导航服务,提高了系统的服务质量.
事实上,同时支持目录导航服务已经成为"自动式"搜索引擎的发展趋势.
下面将介绍如何应用中文网页自动分类技术在"天网"搜索引擎中提供目录导航服务.
5.
2.
1"天网"目录导航服务的体系结构"天网"目录导航服务的体系结构如图5.
1所示.
系统整体上可以分为两个部分:在线部分和离线部分.
在线部分首先接受用户的查询条件,然后根据用户所处的网页目录自动地进行查询扩展,接着在预先分好类的网页库中检索,最后实时地返回查询结果.
离线部分的核心部件为中文网页分类器,负责中文网页的自动分类.
本文这里使用的中文网页分类器的工作原理图请参见图1-3,这里不再赘述.
分类器的整个工作周期可以分成训练过程和分类过程.
在训练过程中,训练集实例经过中文分词和特征选取处理后被表示成向量形式,该特征向量用来描述类别模式,在分类过程中使用.
校验集是训练集的一部分,通过应用相应的阈值策略来预先确第5章中文网页自动分类技术在搜索引擎中的应用65定每个类别的截尾阈值.
在分类过程中,一个待分类的中文网页经过中文浏览器"天网"搜索引擎被分类的网页用户分类器查询词①检索结果④Web网页网页抓取器网页类别查询词+类别②抓取类别匹配③在线离线图5-1"天网"目录的体系结构分词并表示成向量后,应用分类算法同训练过程得到的类别模式逐一比较,得到候选类别列表,然后同训练过程中得到的每个类别的阈值相比较,保留大于阈值的类别,并作为该网页的分类结果.
5.
2.
2"天网"目录的运行实例图5-1给出了"天网"目录导航服务系统的体系结构,下面说明该系统是如何工作的.
图5-2显示了"天网"目录导航服务系统的用户查询界面[天网目录],该界面首先呈现在用户面前的是分类目录的第一层目录,包括"计算机与因特网"、"医疗与健康"等12个大类(详细的中文网页分类目录请参见附录:"天网"中文网页分类目录(1.
0版)).
下面按照用户检索系统的顺序来描述系统的工作过程:⑴导航.
首先,用户沿着系统提供的层次目录逐步进入自己感兴趣的特定领域,由于本文使用的分类目录最多有三层,因此用户沿着层次目录最多翻页3次,而不是像在普通站点上那样递归地访问超链接,可能最终会一无所获.
当用户在这个阶段找到感兴趣的主题,那么就可以进入第2步:输入检索条件进行检索.
当然,用户如果愿意在结果页面内翻页查找,那么就不必输入检索条件进行检索了.
第5章中文网页自动分类技术在搜索引擎中的应用66⑵用户输入检索条件.
当用户进入自己感兴趣的特定领域后,为缩小人工查找的范围,可以向系统提供检索条件,由系统帮助查找.
⑶查询扩展.
当系统接受用户的检索条件时,根据用户当前在网页目录中所处的位置,在用户的检索条件上自动加上此时类别代码,从而进行了查询扩展.
⑷类别匹配.
由于目录导航系统的离线部分预先对搜索引擎抓取的网页进行了分类,网页的类别为已知,同时,用户检索条件经过查询扩展后的类别也为已知,所以可能通过匹配这两者之间的类别来缩小用户的检索范围.
⑸返回结果.
最后一步,系统把同时符合两个条件的结果页面返回给用户.
这两个条件是:a)结果网页中必须用户的检索条件;b)结果网页的类别必须同用户感兴趣的类别相同.
经过从第1步到第5步的处理,系统就能够为用户提供目录导航服务.
图5-2"天网"目录导航服务系统的用户查询界面第5章中文网页自动分类技术在搜索引擎中的应用675.
3相关研究在搜索引擎上提供大规模网页资源目录导航服务,同时具有代表意义的系统有三个:Yahoo!
、Google、以及北大网络实验室设计并实现的"天网"搜索引擎[LW01][周利民97].
⑴"天网"搜索引擎本章的工作是建立在"天网"搜索引擎系统的基础之上的,因此,这里简要的介绍一下"天网"搜索引擎.
系统整体上可以分为搜集、分析、索引、检索、用户界面及日志挖掘等5个子系统.
其中:搜集子系统负责从Web上获取网页;分析子系统负责对网页内容的分析提取;索引子系统负责建立特征项与网页之间的索引表;用户界面和日志挖掘子系统负责优化检索端数据库,增加检索的质量.
自从1997年提供服务以来,"天网"系统体系结构从集中式发展到分布式,无论收集的网页数量还是提供的服务质量都已发生了巨大的变化,越来越受到广大用户的欢迎.
有关"天网"搜索引擎的文件搜索、主题搜索等方面,这里不再赘述,有兴趣的读者可以参见文献[LLWC00][闫宏飞02][Tianwang],等等.
⑵Yahoo!
如本章引言部分所述,Yahoo!
是一种典型的目录式搜索引擎,其完全采用人工的方式对网站进行分类.
但是,由于人工分类效率低,目录式搜索引擎在索引的网页的规模上受到了很大的限制.
⑶GoogleGoogle最初是由Stanford大学研制开发的,在商业运作后,Stanford大学继续Web信息检索方面的研究.
在系统结构上,Google是一种高性能的分布式Web信息系统.
它使用OpenDirectoryProject[ODP]这个分类系统来设计Google的网页目录.
OpenDirectoryProject是网景公司所主持的一项大型公共网页目录.
由全世界各地的义务编辑人员来审核挑选网页,并依照网页的性质及内容来分门别类.
Google提供了多种语言的网页目录,就简体中文网页而言,其收集得网页主要局限在网站的主页面上,维护的网页规模极其有限,不到1万个,这个规模的网页量对一个搜索引擎而言太有限了.
因此,这种第5章中文网页自动分类技术在搜索引擎中的应用68完全使用人工维护的网页导航系统功能是有限的,需要新的技术来克服这个困难.
5.
4本章小结本章主要介绍了中文网页自动分类技术在搜索引擎系统中的一个具体应用,即:如何应用中文网页自动分类技术在"自动式"搜索引擎"天网"中同时提供目录导航服务.
这种同时具有目录导航功能的"自动式"搜索引擎系统,不仅能够维护大规模的网页,而且具有较高的查准率,能够帮助用户快速地定位其感兴趣的网页.
进一步的工作有:⑴提供个性化检索服务.
在当前的搜索引擎工作模式下,对于所有用户,如果他们输入的检索条件相同,那么搜索引擎就会为他们返回相同的结果.
事实上,尽管某些网页也含有检索关键词,但是同用户的本意无关,最后也被返回给用户了.
用户希望搜索引擎能够提供个性化服务,使得查询结果符合用户的个性需求.
⑵应用或研究新的理论知识,进一步提高目录导航系统的性能.
第6章总结与展望69第6章总结与展望6.
1本文的总结海量的网页在为人们提供包罗万象、无比丰富的信息资源的同时,也向人们提出了如何快速地从Web中获取其所需信息的挑战.
为了能够有效地组织和分析海量的Web信息,帮助Web用户方便地获取其需要的信息和知识,人们希望能够按照其内容实现对网页的自动分类.
本文针对Web上的中文信息资源,对中文网页自动分类技术这一具有广阔应用前景的课题进行了研究和探索.
本文主要研究了两个相关的子问题:⑴如何应用有指导的机器学习方法实现大规模中文网页的自动分类;⑵如何应用中文网页自动分类方法在"自动式"搜索引擎中实现目录导航服务.
本文的主要研究工作具体可以概括为以下几个方面:⑴系统地定量分析了影响分类器性能的关键因素针对分类器性能的两个基本指标(分类质量和分类效率)及其相互关系,定量分析了影响分类器性能的各种因素,并根据实验测试结果,提出了一种中文网页分类器的设计方案,这里包含下述5个方面的成果:①训练样本的数量对分类质量的影响.
网页训练集是实现中文网页自动分类的前提和基础.
但是到目前为止还没有出现标准的中文网页训练样本集.
为了解决这一问题,本文构建了一个基于层次模型的中文网页训练样本集.
实验发现,针对本文使用的网页训练集,训练集中每一类的最优样本数约为15个,即此时得到的分类器的分类质量比较稳定,而后再增加样本数对分类器质量的改进不大.
②特征选取算法对分类器质量和效率的影响.
本文系统地比较研究了CHI、信息增益(IG)、文档频率(DF)、互信息(MI)等4个经典特征选取算法,实验结果表明IG、CHI算法最有效;DF方法在一定程度上可以用来替代IG和CHI;MI方法最差.
第6章总结与展望70③分类算法对分类器质量和效率的影响.
本文比较研究了k最近邻居(kNN)和朴素贝叶斯(NB)分类算法.
实验结果表明:kNN的分类质量明显优于NB;从总体而言,NB算法对不同类别表现有明显差异,是一种不稳定的分类算法.
kNN的分类质量受类别的影响不大;但是,kNN方法的分类效率要比NB差.
此外,针对kNN分类算法,本文定量分析了3种因素对分类质量的影响:1),k的取值.
实验结果表明,当k取15时,分类器的分类质量最好;2),衡量两篇文档之间相似度的方法.
实验结果表明,无论是分类质量,还是分类效率,兰式距离法都明显优于欧式距离法;3),分类目录中类别之间的层次关系.
实验结果表明,基于层次的kNN分类算法的分类效率明显优于基本的kNN分类算法.
但是,这需要牺牲一定的分类质量作为代价.
④阈值策略对分类器质量的影响.
本文比较研究了RCut和SCut两种经典的阈值策略.
实验结果表明SCut算法对分类器分类质量的影响明显优于RCut算法但是算法费用要比RCut大.
⑤一个中文网页分类器的设计方案.
本文首先定量地分析了影响分类器性能的4类关键因素.
然后,本文根据相应的实际测试结果来设计一个分类器,最后得到的设计方案为:训练样本实例取15个;选用CHI方法为特征选取算法;选kNN为分类器的分类算法.
其中,k的取值为15;采用兰式距离法度量两篇文档之间的相似度;充分应用分类目录之间的层次关系减少与样本文档的比较次数;阈值策略选用SCut.
实验结果表明,应用该方案设计实现的中文网页分类器不仅具有较高的分类质量,而且同时具有较高的分类效率,满足了处理大规模中文网页的要求.
⑵中文网页中"噪音"的自动清除同普通文档相比,网页的设计比较随意,通常都包含大量"噪音",比如,各类广告,设计人员的注释以及版权申明等和主题内容无关的信息.
有时,同一个网页甚至会包含多个不同的主题.
因此,本文通过结合中文网页的结构信息和内容信息,并结合网页分类技术,实现了一种自动从中文网页中自动清除"噪音"的方法.
实验结果表明,应用该方案设计实现的中文网页分类器不仅具有较高的分类质量,而且同时具有较高的分类效率,满足了处理大规模中文网页的要求.
⑶从搜索引擎日志中学习新词第6章总结与展望71本文首先分析了搜索引擎日志同普通文件、Web网页等基本语料相比所具有的特点:用户查询词长度分布上是非常简短的,在频度分不上是高度集中的.
因此,本文充分利用用户查询词的长度和频度分布特性以及分词系统的先验知识,从所有汉字组合模式中尽可能地排除无效的组合模式,从而实现了一种具有高效率而且具有高准确率的新词学习方法.
实验结果表明,该方法可以有效地从搜索引擎日志中学习新词.
最后还分析了分词字典规模对分类质量的影响.
实验结果表明,该方法不仅可以有效地从搜索引擎日志中学习新词,为新词的自动学习提供了一种新的思路,而且,通过不断扩大分词字典的规模,还可以有效地改进网页分类质量.
⑷在"自动式"搜索引擎系统中提供目录导航服务为了提高搜索引擎的查准率,帮助用户快速地定位其感兴趣的网页,本文应用中文网页自动分类技术,在"自动式"搜索引擎系统中实现了目录导航服务.
这种同时目录导航功能的"自动式"搜索引擎系统,不仅能够维护大规模的网页,而且具有较高的查准率.
6.
2进一步的研究工作中文网页自动分类技术是Web信息检索和Web挖掘领域的一个研究热点,同时也是一个难点.
本文从中文网页自动分类技术本身及其应用进行了研究和探索.
在今后的工作中,作者还将围绕以下几个方面进行更深入的研究和改进:⑴分类器的增量训练.
目前,在完成分类器的训练工作之后,分类器就不会再改变,这样的分类器显然是没有主动学习能力的.
但是,随着Web网页数据源以及用户关心主题的改变,分类器应该具有增量学习功能来自动适应这种变化.
因此,可以尝试合理利用用户的反馈信息以及网页数据源的变化来实现分类器的增量训练.
⑵特征项之间的语义关系.
目前,比较实用的分类器使用的文档表示模型通常是向量空间模型.
虽然该模型具有很多优点,并且很大的成功,但是,该模型是一种统计模型,它完全忽略了特征项之间的语义关系.
因此,可以尝试利用特征项之间的语义规则和知识库等手段来弥补统计方法本身的一些缺陷.
第6章总结与展望72⑶分类器质量的评价.
目前,通常预先人工收集和整理的语料库来测试分类器质量的优劣,并且把特定集合(语料库中包含的测试集)的测试的结果作为分类器的最终质量指标.
由于语料库中的训练集和测试集通常都是经过人工精心挑选的,而且两者之间比较相似,故使用特定测实集得到的测试结果要比真实的分类效果要好的多.
因此,如何得到分类器的真实分类结果是一个值得深入研究的课题.
⑷中文网页自动分类的训练集的标准化.
标准的网页训练集是实现中文网页自动分类的前提和基础,但是到目前为止还没有出现标准的中文网页训练样本集,尽管本文初步构建了一个基于层次模型的中文网页训练样本集,但是它还不是一个完备的基础语料库.
因此,为了促进中文网页自动分类技术的发展,还需要把该语料库作进一步的完善.
⑸个性化搜索引擎.
传统的搜索引擎没有考虑用户特性,如果输入相同的查询条件,搜索引擎就会为所有用户返回相同的结果,尽管这些用户的兴趣爱好可能各不相同.
因此,为了提高搜索引擎的查准率,帮助用户快速地定位其真正需要的内容,搜索引擎系统需要提供个性化的检索服务.
进一步开展个性化搜索引擎的工作,具有重要的理论研究意义和实际应用价值.
参考文献73参考文献[BMK97]Barrett,R.
,Maglio,P.
P.
andKellen,D.
C.
HowtoPersonalizetheWeb.
in:ProceedingsoftheConferenceonHumanFactorsincomputingSystems(CHI'97),ACMPress,NewYork[BMK98]Barrett,R.
,Maglio,P.
P.
,andKellen,D.
C.
Intermediaries:NewPlacesforProducingandManipulatingWebContent.
7thWWWCoference,Brisbane,1998[CBD99]S.
Chakrabarti,Martin.
v.
d.
Berg,ByronDom.
Focusedcrawling:anewApproachtotopic-specificWebresourcediscovery.
ComputerNetworks31,1999,pp.
1623-1640[CF00]Cohen.
W.
W,WeiFan.
Web-collaborativeFiltering:RecommendingMusicbyCrawlingtheWeb.
In:9thWWWConference,Amsterdam,2000[CG]C.
Chekuri,M.
H.
Goldwasser,P.
Raghavan.
WebSearchUsingAutomaticClassification.
http://theory.
stanford.
edu/people/wass/publications/Web_Search/Web_Search.
html[Chakrabarti00]S.
Chakrabarti.
Dataminingforhypertext:atutorialsurvey.
ACMSIGKDDExplorations,1(2),pages1-11,2000[CJT01]S.
Chakrabarti,M.
Joshi,V.
Tawde.
Enhancedtopicdistillationusingtext,markuptags,andhyperlinks.
ACMSIGIR,2001[CKL98]Cheung-DW,Kao-B,Lee-J,DiscoveringUserAccessPatternsontheWorld-Wide-Web,In:KnowledgebasedSystems1998,Vol10,Iss7,pp.
463-470[CMS97]Cooley.
R,Mobasher.
R,Srivastava.
J,WebMining:InformationandPatternDiscoveryontheWorldWideWeb.
In:Proceedingsofthe9thIEEEInternationalConferenceonToolswithArtificialIntelligence(ICTAI'97),November1997,pp.
558-567[CNNIC]ChinaInternetNetworkDevelopmentStatusStatisticalReports.
参考文献74http://www.
cnnic.
net.
cn/develst/report.
shtml[CR00]M.
Crampes,S.
Ranwez.
Ontology-supportedandontology-drivenconceptualnavigationontheWorldWideWeb.
Hypertext2000,SanAntonio,ACM,2000[Fabrizio]SebastinaiFabrizio.
AtutorialonAutomatedtextcategorization.
http://faure.
iei.
pi.
cnr.
it/~fabrizio/ATCtutorialprogram.
html[FGCF99]O.
Frieder,D.
A.
Grossman,A.
Chowdhury,andG.
Frieder.
EfficiencyConsiderationsofScalableInformationRetrievalServers.
JournalofDigitalInformation,1999[FHZ00]Fong.
J,Hughes.
J.
G,Zhu.
J.
OnlineWebMiningTransactionsAssociationRulesUsingFrameMetadataModel,ProceedingsoftheFirstInternationalIEEEConferenceonWebInformationSystemsEngineering2000,Volume2,2000,pp.
121-129vol.
2[FSZGL02]FengShicong,ShanSongwei,ZhangZhigong,GongBihong,LiXiaoming.
AdatasetofChineseWebpagesanditscategorization.
Proceedingsofthecross-straitinformationtechnologyworkshop,October,2002,Nanjing,pp.
121-129[Google]http://www.
google.
com[GSY01]R.
Ghani,S.
SlatteryandY.
Yang.
HypertextCategorizationUsingHyperlinkPatternsandMetaData.
TheEighteenthInternationalConferenceonMachineLearning(ICML'01),pp.
178-185,2001[Harman92]D.
Harman.
EvaluationissuesinInformationRetrieval.
InformationProcessing&Management,1992,28(4)[Hull94]D.
A.
Hull.
ImprovingTextRetrievalfortheRoutingProblemUsingLatentSemanticIndexing.
InProceedingsofSIGIR-94,17thACMInternationalConferenceonResearchandDevelopmentinInformationRetrieval,pp.
282-289,Dublin,IE,1994[JFM97]Joachims,T.
,Freitag,D.
,Mitchell,T.
,WebWatcher:ATourGuidefortheWorldWideWeb.
In:ProceedingsoftheInternationalJointConferenceinAI(IJCAI97),August1997[Lewis92a]D.
D.
Lewis.
Anevaluationofphrasalandclusteredrepresentations参考文献75onatextcategorizationtask.
ProceedingofSIGIR-92,15thACMInternationalConferenceonResearchandDevelopmentinInformationRetrieval,pp37-50,Kobenhavn,DK,1992[Lewis92b]D.
D.
Lewis.
RepresentationandLearninginInformationRetrieval.
PhDthesis,DepartmentofComputerScience,UniversityofMassachusetts,Amherst,US,1992[Lewis95]D.
D.
Lewis.
EvaluatingandOptmizingAutonomousTextClassificationSystems.
ProceedingsofSIGIR-95,18thACMInternationalConferenceonResearchandDevelopmentinInformationRetrieval,pp.
246-254,Seattle,US,1995[Lewis98]D.
D.
Lewis.
Naive(Bayes)atforty:TheIndependenceAssumptioninInformationRetrieval.
InProceedingsofECML-98,10thEuropeanConferenceonMachineLearning,pages4-15,Chemnitz,DE,1998[LG94]D.
D.
LewisandW.
A.
Gale.
ASequentialAlgorithmforTrainingTextClassifiers.
ProceedingsofSIGIR-94,17thACMInternationalConferenceonResearchandDevelopmentinInformationRetrieval,pp.
3-12,Dublin,IE,1994[LG99]SteveLawrence,C.
LeeGiles,AccessibilityofInformationontheWeb,Nature,Vol.
400,8,Jul.
1999,pp107-109[LH98]W.
LamandC.
Y.
Ho.
UsingaGeneralizedInstanceSetforAutomaticTextCategorization.
InProceedingsofSIGIR-98,21stACMInternationalConferenceonResearchandDevelopmentinInformationRetrieval,pp.
81-89,Melbourne,AU,1998[LH02]Shian-huaLin,Jan-MingHo.
DiscoveringInformativeContentBlocksfromWebDocuments.
InSIGKDD02,July23—26,Alberta,Canada[LJZM99]NealLesh,MohammedJ,Zaki,Ogihara.
M,Miningfeaturesforsequenceclassification,In:ProceedingsofthefifthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,1999,Pages342–346[LJW98]Lynch.
R.
S,Jr,Willett.
P.
K.
BayesianClassificationandtheReductionofIrrelevantFeaturesfromTrainingdata.
In:Proceedingsofthe37th参考文献76IEEEConferenceonDecisionandControl,1998,vol.
2,pp1591-1592[LLWC00]J.
Liu,M.
Lei,J.
Wang,andB.
Chen.
Diggingforgoldontheweb:ExperiencewiththeWebGather.
InProceedingsofthe4thInternationalConferenceonHighPerformanceComputingintheAsia-PacificRegion,Beijing,P.
RChina,May14-17,2000.
IEEEComputerSocietyPress.
PP:751-755[LR94]D.
D.
LewisandM.
Ringuette.
AComparisonofTwoLearningAlgorithmsforTextCategorization.
InProceedingsofSDAIR-94,3rdAnnualSymposiumonDocumentAnalysisandInformationRetrieval,pp.
81-93,LasVegas,US,1994[LRS99]WaiLam,MiguelRuiz,andPadminiSrinivasan.
AutomaticTextCategorizationandItsApplicationtoTextRetrieval.
IEEETRANSACTIONSONKNOWLEDGEANDDATAENGINEERING,VOL.
11,NO.
6,NOVEMBER/DECEMBER1999[LSCP96]D.
D.
Lewis,R.
E.
Schapire,J.
P.
Callan,andR.
Papka.
TrainingAlgorithmsforLinearTextClassifiers.
Proceeding19thInt'lACMSIGIRConf.
ResearchandDevelopmentinInformationRetrieval,pp.
298-306,1996[LS02]LIXiaoliandSHIZhongzhi.
InnovatingWebPageClassificationThroughReducingNoise.
InJournalofComputerScience&Technology,Vol.
17,Jan.
2002[LW01]LIXiaoming,WANGJianyong.
WebGather:towardsQualityandScalabilityofaWebSearchService,ForumforCurrentResearchandDevelopmentoftheWWWinPRC,aneventofWWW10,May1-5,2001[LWCL01]LeiMing,WangJianyong,ChenBaojue,andLiXiaoming.
ImprovedrelevancerankinginWebGather.
JournalofComputerScienceandTechnology,Vol.
16,No.
5,September2001,pp410-417[Mitchell96]T.
Mitchell.
Machinelearning.
McGrawHill,NewYork,US,1996[MCS00]Mobasher,B,Cooley,R,Srivastava,J,AutomaticPersonalizationBasedonWebUsageMining.
CommunicationsoftheACM,Volume43,参考文献77Number8(2000),pp.
142-151[MCS99]Mobasher.
R,Cooley.
R,Srivastava.
J,CreatingAdaptiveWebSitesThroughUsage-BasedClusteringofURLs.
In:Proceedingsofthe1999IEEEKnowledgeandDataEngineeringExchangeWorkshop(KDEX'99),November1999[NGL97]H.
T.
Ng,W.
B.
Goh,andK.
L.
Low.
FeatureSelection,Perceptronlearning,andaUsabilityCaseStudyforTextCategorization.
In20thAnnIntACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'97),pp.
67-73,1997[ODP]http://dmoz.
org/[OGC01]Ossenbruggen.
J,Geurts.
J,Cornelissen.
F.
TowardsSecondandThirdGenerationWeb-basedMultimedia.
10thWWWConference,HongKong,2001[PG99]AlexanderPretschner,SusanGauch.
Ontologybasedpersonalizedsearch.
http://computer.
org/Proceedings/ictai/0456/04560391abs.
htm[Sarukkai00]Sarukkai.
P.
R.
LinkPredictionandPathAnalysisUsingMarkovChains.
9thWWWConference,Amsterdam,2000[SP97]Spertus.
E.
Parasite:MiningStructuralInformationontheWeb.
ComputerNetworksandISDNSystems29(1997)pp1205-1215[TED]http://www.
ted.
cmis.
csiro.
au/TRECWeb/access_to_data.
html[TianWang]http://e.
pku.
edu.
cn[TK99]Tanaka.
H.
Kumano.
T.
AnEfficientDocumentClusteringAlgorithmandItsapplicationtoDocumentaBrowser,In:InformationProcessingandManagement,35(1999),pp541-557[TREC]http://trec.
nist.
gov/[VDDRN00]VanderMee.
D,Dutta.
K,Datta.
A,Ramamritham.
KNavanthe.
S.
B.
EnablingScalableOnlinePersonalizationontheWeb.
Proceedingsofthe2ndACMConferenceonElectronicCommerce,2000,pp185–196[WSLXL01]J.
Wang,S.
Shan,M.
Lei,Z.
XieandX.
Li.
WebSearchEngine:CharacteristicsofUserBehaviorsandTheirImplication.
ScienceinChinaSeriesE,2001参考文献78[YAHOO]http://www.
yahoo.
com[Yang94]Y.
Yang.
ExpertNetwork:EffectiveandEfficientLearningfromHumanDecisionsinTextCategorizationandRetrieval.
Proceedingsofthe17thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'94)pp.
11-211,1994[Yang95]Y.
Yang.
NoiseReductioninaStatisticalApproachtoTextCategorization.
ACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'95),pp.
256-263,1995[Yang96]Y.
Yang.
SamplingStrategiesandLearningEfficiencyinTextCategorization.
AAAISpringSymposiumonMachineLearninginInformationAccess,pp.
88-95,1996[Yang99]Y.
Yang.
AnEvaluationofStatisticalApproachestoTextCategorization.
InformationRetrievalJournal,May,1999[Yang01]Y.
Yang.
Astudyonthresholdingstrategiesfortextcategorization.
ProceedingsofACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'01),2001[YHC02]H.
Yu,J.
Han,K.
Chen.
PEBL:PositiveExampleBasedLearningforWebPageClassificationUsingVSM.
ACMSIGKDD,2002[YL99]Y.
Yang,XinLiu.
Are-examinationoftextcategorizationmethods.
ProceedingsofACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'99,pp.
42-49),1999[YJP97]Y.
Yang,JanO.
Pedersen.
AComparativeStudyonFeatureSelectioninTextCategorization.
ProceedingsoftheFourteenthInternationalConferenceonMachineLearning(ICML'97),1997[YPL00]Y.
Yang,ThomasAult,ThomasPierceandCharlesWLattimer.
ImprovingTextCategorizationMethodsforEventTracking.
ProceedingsofACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'00),pp65-72,2000[YSG01]Y.
Yang,S.
SlatteryandR.
Ghani.
AStudyofApproachestoHypertextCategorization.
JournalofIntelligentInformationSystems,2001[Yuwono]BudiYuwono,etc.
AWorldWideWebResourceDiscoverySystem,参考文献79Proc.
4thWorldWideWebConference,pp.
145-158[YWLG01]H.
Yan,J.
Wang,X.
Li,andL.
Guo.
ArchitecturalDesignandEvaluationofanEfficientWeb-crawlingSystem.
Acceptedby1stInternationalWorkshoponInternetComputingandE-Commerce.
SanFrancisco,California,USA,April27,2001[丁雅娴94]丁雅娴.
学科分类研究与应用.
中国标准出版社,1994,6[黄宣菁96]黄宣菁,吴立德,王文欣,叶丹瑾.
具有机器学习的无需人工编制字典的切词系统.
模式识别与人工智能,1996.
9(4):297-303[黄菁萱98]黄菁萱,吴立德.
基于向量空间模型的文档分类系统.
模式识别和人工智能,1998年11卷第二期[卜东波00]卜东波.
聚类/分类理论研究及其在文本挖掘中的应用[博士论文],中科院,北京,2000[天网目录]http://162.
105.
80.
84/cgi-bin/getdirectoryccode=0&first=1[王继成00]王继成.
基于元数据的Web信息检索技术研究[博士学位论文],南京大学,南京,2000[王建勇00]王建勇,谢正茂,雷鸣,李晓明.
近似镜像网页检测算法的研究与评测.
《电子学报》,Vol28,No.
11A,2000年11月,130-132[王建勇01]王建勇,单松巍,雷鸣,谢正茂,李晓明.
海量web搜索引擎系统中用户行为的分布特征及其启示.
《中国科学》E辑,2001年8月,第31卷,第四期,第372-384页[郑家恒00]郑家恒,李鑫,谭红叶.
基于语料库的中文姓名识别方法研究.
中文信息学报,2000,14(1):7-12[闫宏飞02]闫宏飞.
可扩展Web信息搜集系统的设计实现与应用初探[博士学位论文],北京大学,北京,2002[周利民97]周利民,刘建国,陈葆珏.
天网:一个中英文环球搜索引擎.
软件学报,Vol.
8增刊,1997[张小衡97]张小衡,王玲玲.
中文机构名称的识别与分析.
中文信息学报,1997,11(4):21-31[张志刚]张志刚,陈静,李晓明.
一个面向应用的HTML网页表示模型.
准备投稿附录"天网"中文网页分类目录(1.
0版)80附录"天网"中文网页分类目录(1.
0版)01,人文与艺术0103,视觉艺术010301,计算机创作010302,摄影010303,涂鸦与喷画010304,雕塑010305,书法与篆刻010308,陶瓷010309,纸艺010313,绘画0107,表演艺术010703,相声010705,木偶戏010708,舞蹈010709,杂技010711,戏剧010714,戏曲与歌剧0119,设计艺术011904,工业设计011907,绘图011910,建筑011911,室内设计0121,工艺品012101,刺绣02,新闻与媒体0201,政治新闻0202,科技新闻0203,社会新闻0204,经济新闻0205,娱乐新闻0206,体育新闻03,商业与经济0304,发明0306,房地产0308,经济技术开发区0310,公司031004,银行业031005,清洁业031006,包装031007,化工产品031010,环保031014,设计031018,布料031020,食品031021,采矿031025,家用电器031026,水电气公共设施031027,仓储031031,建设营造031032,图书031033,建筑031041,金融服务031046,就业服务031047,电子业031050,动物031056,法律031057,饮料031059,零售031060,印刷031061,服装031065,购物031076,拍卖031083,制造业031084,珠宝钟表031087,殡仪031088,出版031091,礼品与工艺品0314,交通运输031401,航运031402,海运031403,高速公路与道路031405,公共交通031409,火车与铁路031412,货运0319,贸易0324,消费者权益0329,中小企业0331,投资0332,服务行业04,娱乐与休闲0403,嗜好040307,抽烟040317,收藏040322,模型0406,体育运动040603,摔交040604,棒球040605,篮球040607,保龄球040608,垒球040609,体操040610,壁球040612,田径040613,冲浪040614,溜冰040615,网球040617,马术040618,武术040623,排球040625,帆船附录"天网"中文网页分类目录(1.
0版)81040626,跑步040628,飞盘040629,乒乓球040630,游泳与潜水040631,高尔夫球040633,羽毛球040635,曲棍球040636,运动会040637,滑板040638,拳击040639,运动员040640,滑板车040641,赛车040643,滑水040645,自行车040646,滑雪040647,射击040648,足球040650,射箭040652,击剑040653,手球040655,举重0408,居家与园艺040805,水电040806,园艺0409,玩具040902,虚拟宠物040904,娃娃0410,航空041002,滑翔041007,航空表演0413,户外活动041302,海滩041304,登山041307,钓鱼041317,露营041320,攀岩0414,旅游0418,游戏041803,益智游戏041804,计算机游戏041807,掌上型游戏041808,台球041809,纸牌041811,下棋0422,抽奖0423,KTV与卡拉OK0425,博彩0426,电影042603,电影音乐042604,电影院042608,奖项042609,剧本042610,拍摄制作042615,影评0427,动画与卡通042701,动画042703,漫画0429,科幻与奇想0437,星相命理043703,星座043705,看相算命0439,音乐043901,Disc043908,乐器043911,声乐0441,游乐场05,计算机与因特网0501,人工智能050101,自然语言处理050102,模式识别0502,计算机系统结构050201,并行处理050202,分布式处理系统0503,通讯与网络050301,ATM050302,电子邮件050304,DSL050307,ISDN050308,局域网050314,协议0504,信息安全050401,病毒050403,黑客0505,计算机应用050501,计算机图形学050502,计算机图像处理050503,计算机辅助设计050504,计算机辅助教学0507,计算机基础科学050702,可计算理论050704,数据结构0515,因特网051501,WWW051508,搜寻与检索051514,网络电话0516,程序设计语言051601,CandC++051602,JavaScript051603,VisualBasic051604,Delphi051605,Perl051608,SQL051610,Java051611,XML051612,HTML0518,硬件051801,单片机051802,CPU051803,存储介质051804,显示器051805,计算机外附录"天网"中文网页分类目录(1.
0版)82设051806,主板051807,适配卡0529,软件052901,软件工程052904,操作系统052905,编译系统052914,仿真器052920,数据库0531,多媒体053102,音频053104,视频053105,动画053106,虚拟现实07,教育0704,成人进修教育0705,大专院校与研究所070501,大学入学070502,大专院校0706,教育改革0707,考试0708,海外留学0710,奖助学金0712,教学技术0715,女性教育0717,特殊教育0720,幼儿教育0721,远程教学0723,职业教育0725,中小学072503,小学072505,中学08,区域0801,国家与地区080102,台湾080103,阿富汗080104,阿根廷080105,埃及080106,爱尔兰080109,澳大利亚080110,澳门080111,巴基斯坦080112,巴勒斯坦080114,巴西080121,朝鲜080123,德国080125,俄罗斯080126,法国080129,哥伦比亚080131,韩国080132,荷兰080133,加拿大080140,马来西亚080141,美国080147,南非080148,南斯拉夫080150,挪威080151,葡萄牙080152,日本080153,瑞典080154,瑞士080156,沙特阿拉伯080157,泰国080159,土耳其080161,乌克兰080162,西班牙080164,香港080165,新加坡080166,新西兰080168,伊拉克080169,伊朗080170,以色列080171,意大利080172,印度080173,印度尼西亚080174,英国080175,越南0802,洲080202,北美洲080203,大洋洲080204,非洲080206,南美洲080207,欧洲080209,亚洲080210,南极洲10,自然科学1004,地理学100406,自然地理学100407,人文地理学1005,地球科学100501,地质学与大气物理学100503,海洋学100505,气象学100506,水文学100507,地球科学史100508,大气科学100509,空间物理学100510,地图学100511,地质学1008,工程学100801,材料科学100802,电机工程100803,电子工程100804,工业工程100805,光电工程100806,海洋工程100809,环境工程100810,机械工程100812,矿业100814,质量管理100816,人体工学100817,生物医学工程100821,土木工程100822,系统工程100823,冶金工程附录"天网"中文网页分类目录(1.
0版)831009,航空、航天科学技术100903,航空、航天科学技术100904,飞行器100905,航天器100906,卫星1010,化学101004,化学史101005,无机化学101006,有机化学101007,分析化学101008,物理化学101009,结构化学101010,催化化学101011,电、磁化学101012,高分子化学101013,核化学101014,应用化学1015,另类科学1017,农业科学101713,农业基础科学101714,土壤学101715,农业经济学101716,农业工程学101717,水产学1019,认知科学1020,生命科学1021,生态学102102,生态系统1022,生物学102201,动物学102202,分子生物学102207,神经科学102208,生物科技102209,微生物学102210,细胞生物学102213,植物学102217,生物化学1023,数学102303,统计与数理统计102304,数理逻辑与数学基础102305,数论102306,代数学102307,几何学102308,拓扑学102309,函数论102310,运筹学102311,离散数学102312,应用数学102313,数学史1025,天文学102504,太阳系102505,天文馆102508,天文学史102509,天体物理学102510,星系与宇宙学1027,物理学102701,高能与分子物理102702,力学102707,物理学史102708,理论物理学102709,声学102710,热学102711,光学102712,电磁学102713,无线电物理102714,原子核物理1031,林业学1032,渔业学1033,核科学1034,电子、通信、控制技术103401,电子技术103402,半导体技术103403,信息处理技术103404,通信技术103405,自动控制技术1035,环境科学103501,环境科学基础学科103502,环境工程科学1037,信息科学与系统科学103701,信息科学与系统科学103703,系统学103705,控制理论103708,系统工程11,政府与政治1102,公安、检察院、法院1104,大使馆,领事馆与办事处1105,军事110501,陆军110502,海军110503,空军110504,特种部队110505,武器与军备110506,训练与教育110507,退伍军人1110,国徽,国旗与国歌附录"天网"中文网页分类目录(1.
0版)841111,税务1112,政治111201,两岸关系111204,选举111205,政党111206,政论12,社会科学1201,教育学120101,教育学原理120102,教育社会学120103,教育心理学120104,教育技术学1203,历史学120301,史学理论120302,中国史120303,世界通史120304,亚洲史120305,欧洲史120306,非洲史120307,美洲史1205,新闻与传播学120501,新闻理论120503,新闻学120504,传播学1206,妇女研究1207,法学120702,宪法120703,法学研究120704,法学院120705,经济法120706,劳动法120707,国际法120708,刑法120709,商业法120710,行政法120711,婚姻法120712,隐私权120713,知识产权120714,环境法120716,民法120717,军事法120718,安全法1208,经济学120802,会计学与审计学120803,货币银行学120806,经济政策120807,论文120808,期刊120809,研究机构120811,宏观经济学120812,微观经济学120814,国际贸易学120815,金融学120817,国际货币经济学120818,国民经济学120819,管理经济学120820,城市经济学120821,资源经济学120822,环境经济学120823,商业经济学120824,价格学120826,保险学120827,财政学1214,人类学与考古学121401,博物馆121403,考古学1215,企业管理121501,生产与运作管理121502,财务管理121503,营销管理121504,物流管理121505,成本管理121506,设备管理121507,质量管理121508,经营管理121509,人力资源管理121510,战略管理121511,信息管理121512,知识管理121513,风险管理121514,审计121515,统计学1216,管理工程121601,决策分析121603,管理信息系统1217,社会学121701,人口学121702,犯罪学121705,公共关系学121709,社会学理论1222,语言学122201,翻译122205,语言1223,政治学122302,政治制度122305,国际政治学1225,图书馆、情报与文献学1228,哲学122801,马列主义122802,毛泽东思想附录"天网"中文网页分类目录(1.
0版)85122803,邓小平理论122804,三讲与三个代表122805,哲学史122806,美学122807,逻辑学1229,宗教学122901,佛教122902,道教122903,伊斯兰教122904,基督教13,医疗与健康1301,疾病与症状130103,艾滋病130104,白化症130105,白内障130106,白血病130107,白癜风130108,鼻咽癌130111,德国麻疹130113,地中海型贫血130114,毒品与药物滥用130115,多汗症130117,肺癌130118,肺炎130119,肝癌130120,肝炎130122,高血压130123,骨科疾病130124,骨质疏松症130125,关节炎130127,汉他病130129,霍乱130130,基因异常130131,肌肉萎缩130132,肌无力症130133,脊髓灰质炎(小儿麻痹症)130134,脊髓损伤130135,甲状腺疾病130136,间质性膀胱炎130139,结核病130140,克雅二氏症(疯牛症)130142,狼疮130143,老年痴呆症130144,流行性感冒130145,脑膜炎130146,脑性麻痹130147,尿床症130149,帕金森氏症130150,皮肤疾病130151,前列腺炎130152,青光眼130153,情感性精神病130154,乳癌130155,烧伤130156,肾病130157,失眠130158,水痘130159,睡眠问题130160,炭疽病130162,糖尿病130163,脱发130168,哮喘130172,性病130173,酗酒130174,眩晕症130175,血友病130176,循环系统疾病130177,烟害130178,眼睛疾病130179,银屑病130180,忧郁症130182,运动损伤130183,中风130184,自闭症130185,自体免疫性疾病130186,癫痫症1302,基础医学130201,人体解剖学130202,人体生理学130204,人体免疫学130205,病理学130206,药理学130207,生物医学工程学1303,临床医学130301,临床诊断学130302,保健医学130303,理疗学130304,麻醉学130305,内科学130306,外科学130307,妇产科学130308,儿科学130309,眼科学130310,耳鼻咽喉科学130311,口腔医学130312,皮肤病学130313,性医学130314,神经病学130315,急症医学130316,肿瘤学130317,护理学1304,预防医学与卫生学附录"天网"中文网页分类目录(1.
0版)86130401,营养学130402,消毒学130403,传染病学130405,职业病学130406,卫生检查学130408,妇幼卫生学130410,放射卫生学130411,计划生育学130412,优生学1305,军事医学与特种医学130501,军事医学130502,特种医学1306,药学130601,药物化学130602,药剂学130603,药效学130604,医药工程1307,中医学与中药学130701,草药130702,气功130704,针灸130705,按摩推拿130706,中药学1308,兽医学与畜牧学130801,兽医学130802,畜牧学1309,健康130901,女性健康130902,避孕130903,怀孕与生产130904,儿童健康130905,心理健康130906,环境健康130907,性教育130908,减肥130909,营养130910,美容130911,健身1310,治疗与程序131001,器官移植131002,输血131003,芳香疗法1311,公共卫生与安全1312,急救服务14,社会与文化403,残障140301,残障140306,援助1404,犯罪140403,执法机关140404,罪行1405,环境与自然140501,环境保护140505,环境变迁140513,水资源140514,污染140518,环境灾难140520,资源1406,婚礼1408,家庭140807,育儿1409,节庆假日140901,春节140902,端午节140903,儿童节140904,复活节140905,父亲节140906,感恩节140907,公元2000年140908,教师节140909,节气140910,母亲节140911,七夕节140912,情人节140913,圣诞节140914,万圣节140915,元旦140916,元宵节140917,中秋节140918,中元节1414,人际关系141401,爱情141402,婚姻141404,交友1415,人物141510,姓氏1416,神话与民间风俗1417,死亡141701,安乐死141703,自杀1418,讨论话题141802,慈善事业141807,人口141808,人权1419,文化与团体141902,变性141903,儿童141906,老人141908,男性141909,女性141910,青少年141911,素食者141912,同性恋与双性恋者141913,虚拟文化141915,左撇子1422,饮食142203,烹调142205,食物安全142208,饮料与品酒1424,宗教博士生期间录用和提交的论文87博士生期间录用和提交的论文1.
冯是聪,单松巍,龚笔宏,张志刚,李晓明.
"天网"目录导航服务研究.
计算机研究与发展.
已录用,将于2003年(第40卷)刊出2.
冯是聪,王继民.
关于"中文网页自动分类竞赛"结果的分析.
中文信息学报.
已录用3.
冯是聪,张志刚,李晓明.
一种中文网页自动分类方法的实现及其应用.
计算机工程,已录用,将于2004年3月刊出4.
冯是聪,单松巍,张志刚,龚笔宏,李晓明.
基于Web挖掘的个性化技术研究.
计算机工程与设计,已录用,将于2004年第4期刊出5.
冯是聪,单松巍,张志刚,龚笔宏,李晓明.
一个中文网页训练样本集及其分类体系.
第四届海峡两岸信息(咨讯)技术研讨会论文集(InEnglish:ADataSetofChineseWebPagesandItsCategorization),2002.
10,pp121-1296.
龚笔宏,冯是聪.
kNN与NB算法在中文网页分类上的比较研究.
全国搜索引擎与网上信息挖掘研讨会论文集"搜索引擎与Web挖掘进展",高等教育出版社,2003.
3,pp73-797.
单松巍,冯是聪,李晓明.
几种典型特征选取方法在中文网页分类上的效果比较.
计算机工程与应用,已录用,将于2003年8月刊出8.
冯是聪,彭波,李晓明.
一种从搜索引擎日志中学习新词的方法.
计算机学报.
已投稿9.
冯是聪,龚笔宏,李晓明.
中文网页自动分类技术研究研究及其在搜索引擎中的应用.
973项目专项图书.
已投稿10.
专利:一种从搜索引擎日志中学习新词的方法及其系统.
专利申请中致谢88致谢首先要衷心地感谢我的导师李晓明教授,感谢他在我三年的博士生阶段对我的精心指导.
李老师渊博的学识、严谨的治学态度、高尚的个人修养,以及对事业的执着追求精神都深深地感染了我,让我受益终身.
无论是做学问还是做人,李老师都是我学习的榜样,我为能够在漫漫求学的道路上遇到这样的良师而感到庆幸!
衷心感谢代亚非教授在我博士一年级时对我的悉心指导.
在博士论文的选题、调研以及论文的写作等方面,她提出了很多宝贵意见和并给予了大量的帮助.
特别感谢北大网络实验室"天网"组的龚笔宏、张志刚、单松巍同学两年来的大力帮助和积极配合,本文的许多实验都是在他们的帮助下完成的.
同时还要感谢同组的闫宏飞、王继民老师、谢正茂、孟涛、彭波、陈华、黄连恩、谢欣等同学以及北大网络实验室的严伟、韩华等老师和张丽、肖明忠等同学,在我学习和生活中给予的帮助和支持.
深情感谢我的妻子何有娣女士.
是她在我灰心丧气时给我支持和鼓励;是她陪伴我度过了求学生涯中最艰难的日子;是她给予了我无私的爱.
作为一名医生,在"非典"时期承受着巨大的心理压力和面临着随时被感染的危险,为了不影响我的学业,一个人默默地面对着这一切.
用言辞无法表达我对她的感激之情,衷心祝福她能平安地度过这场人类共同的灾难.
感谢我的家人多年来对我学业的支持,没有他们,本文的一切都无从谈起.
最后,感谢国家重点基础研究发展规划项目(国家973项目:G1999032706)基金对本文的资助.