（计算机应用技术专业论文）基于最大熵模型的网页分类.pdf

摘要 随着w w w 的迅猛发展，对网页进行分类成为处理和组织大量文档数 据的关键技术。由于最大熵模型可以综合观察到的各种相关或不相关 的概率知识，对许多问题的处理都可以达到较好的结果。研究者通过 实验比较和分析了基于最大熵模型的分类器的分类性能，并且分别对 其进行了特征优化、预分类处理以及平滑处理的比较，结果发现预分 类处理对分类的帮助是很明显的，其余两种操作也在一定程度上提高 了分类精度。 本文针对最大熵的优点做了以下研究： ( 1 ) 对网页结构进行分析，根据其连接程度分为c h u b 页面和内 容页面两种，以便进一步研究时，可根据不同的特点采取不同的研究 方法，旨在提高网页的分类精度。 ( 2 ) 对网页进行了预处理，包括分词、建造类别词库等。通过对 词专指度的计算，给出能够确定文章类别的关键词入库。 ( 3 ) 基于最大熵模型，本文用g i s 算法求得特征函数，并用传统 的特征归纳方法，通过计算两个概率分布之间的距离，分析引入某一 特征后的信息增益，对每一特征进行筛选，选出有用的特征组成一个 特征优化集合。 ( 4 ) 分别对结构分析得到的两种页面设计特征函数。对于内容页 面，由于其形式与纯文本文档非常接近，我们用词一类别作为其特征， 采用词频作为特征值；对于c h u b 页面，由于有较高的文字链接比， 我们主要对h t m l 格式进行分析。首先通过分析h t m l 语言提取出一 个优化的h t m l 标记集合作为研究对象，然后引入s a l t o n 提出的文本 表示方法，并加以改进，用以表示网页内容，把词本身的特征与其所 在位置相结合，计算出特征值t ；，生成特征函数。 试验结果表明基于最大熵的网页分类方法是行之有效的。它不但能 得到最一致的分布，而且保证了网页分类的查准率和查全率。而且它比 其他方法较少依赖语言学知识、预处理或语义数据库。不失为一种理想 的网页分类方法。 关键词：网页分类；最大熵模型；类别词 a b s t r a c t w i t ht h er a p i dp r o g r e s so fw b r i dw i d ew 如c l a s s i f y i n gw e bp a g e si s b e c o m i n g a p w o t a lt e c h n o l o g yi np r o c e s s i n g a n do r g a n l z m gam a s so f d o c u m e n t sa n dd a t a a si tc a r lh e l po b s e r v ea 1 1k i n d so fr e l a t i v ea n di r r e l a t i v e p r o b a b i l i t yk n o w l e d g e ，m a x i m u me n t r o p ym o d e l sg i v ec o m p a r a t i v e l yb e t t e r s o l u t i o n st om a n yp r o b l e m s r e s e a r c h e r st h r o u g hm a n ye x p e r i m e n t sc o m p a r e a n da n a l y z et h ep e r f o r m a n c eo f t h es o r t e rb a s e do nm a x i m u me n t r o p ym o d e l t h ee s s a yw i l lm a k er e s e a r c ho nt h ea d v a n t a g eo f m a x i m u me n t r o p ym o d e l ： ( 1 ) b ya n a l y z i n gt h e i rs t r u c t u r e ，a c c o r d i n gt ot h ec o n n e c t i o n ，t h ew e b p a g e sw i l lb ed i v i d e di n t ot w ok i n d s ：c h u bw e b p a g ea n dc o n t e n tw b b p a g e s ot h a tt h ef u r t h e rr e s e a r c hc a nt a k ea d v a n t a g eo ft h e i rd i f f e r e n tf e a t u r e sa n d i m p r o v et h ec l a s s i l y i n gp r e c i s i o n ( 2 ) t h ep r e p r o c e s st ot h ew e b p a g ei n c l u d e ss o r t i n gw o r d s ，e s t a b l i s h i n g s o r t i n gv o c a b u l a r y , e t e c o m p u t i n gt h ep a r t i c u l a r i t yo fw o r dc a na d di n t ot h e v o c a b u l a r yt h ek e yw o r d sd e c i d i n gt h ew e b p a g e sf e a t u r e s ( 3 ) b a s e do nt h em a x i m u me n t r o p ym o d e l ，t h ee s s a ym a k e su s eo fg i s a l g o r i t h mt og e tt h ef e a t u r ef u n c t i o n ，a n dt h e nb yt r a d i t i o n a lf e a t u r e s i n d u c t i v em e t h o d so fg e t t i n gt h ed i s t a n c eb e t w e e nt w op r o b a b i l i t i e s ， a n a l y z a b i l i t yb r i n g si n f o r m a t i o ng a i nw i t hs o m ef e a t u r et os c r e e no u tt h e u s e f u lc h a r a c t e r i s t i c sa n de s t a b l i s hf lc h a r a c t e r i s t i c - o p t i m i z e dc o l l e c t i o n ( 4 1a n a l y z i n gt h es t r u c t u r et og e tt h ef e a t u r e so f t w ow e bp a g ed e s i g n t h e s t r u c t u r eo fc o n t e n tw e bp a g ei sv e r ys i m i l a rw i t ht d o c u m e n t s ow eu s e 研d s o r ta si t sf e a t u r e a n dw o r d 丹e q u e n c ya si t sf e a t u r e s ；t h ec h u bw e b p a g eh a sah i g h e rw o r dc o n n e c t i o nr a t i o s ow em a i n l ya n a l y z eh 瑚f o r m a t f i r s t l y , w ea n a l y z eh 咖，l a n g u a g ea n de x t r a c ta no p t i m i z e dh t m l m a r k c o l l e c t i o na sr e s e a r c ho b j e c t t h e nw eb r i n gi nt l l em e t h o dw h i c hs a l t o np u t f o r w a r dt of i g u r et e x t sa n di m p r o v ei tt os h o wt h ec o n t e n to f w e bp a g e l a s t l y , w ec o m b i n et h ec h a r a c t e r i s t i c so fw o r d st h e m s e l v e sw i t ht h e i rp o s i t i o n st o c o m p u t et h ef e a t u r e ，t i n o w , w eg e tt h ef e a t u r e t h er e s u l tp r o v e st h a tt h ew e b p a g e s o r t i n gm e t h o db a s e do nm a x i m u m e n t r o p ym o d e li s e f f e c t i v e i tn o to n l yc a ng e tt h em o s tc o n s i s t e n t d i s t r i b u t i o n ，b u te n s u r et h ea c c u r a c ya n du n i v e r s a l i t yi ns o r t i n gw e b p a g e c l a s s i f i c a t i o na sw e l l b e s i d e s ，i td e p e n d sl e s so nt h el a n g u a g ek n o w l e d g e ， l y r e p r o c e s sa n dd e f i n i t i o nd a t a b a s e s ot h ew e b p a g e s o r t i n gm e t h o db a s e do n m a x i m u m e n t r o p ym o d e l i sar e l a t i v e l yp e r f e c tw e b p a g ec l a s s i f y i n gm e t h o d k e y w o r d sw e b p a g ec l a s s i f i c a t i o n ；m a x i m u me n t r o p ym o d e l ； c a t e g o r y - w o r d 第一章引言 第一章引言 1 1 研究的意义 自1 9 6 9 年美国国防部创建的第一个分组交换网a r p a n e t 的诞生，网络以惊人 的速度发展。目前因特网已成为世界上规模最大的和增长速率最快的计算机网络。 据研究咨询公司e t f o r e c a s t s 公布的最新数据显示，截至去年底，全球互联网用户人 数达到1 0 8 亿，比2 0 0 4 年增长了1 5 亿人。e t f o r e c a s t s 预计，未来五年全球互联网 用户人数将再增长一倍，达到2 0 亿人。随着因特网的迅猛发展、w e b 信息的增加， 用户要在信息海洋里查找有用信息，就象大海捞针一样，搜索引擎技术恰好解决了 这一难题。 搜索引擎以一定的策略在互联网中搜索、发现信息，对信息进行理解、提取、 组织和处理，将这些信息进行分类并建立索引，以便提供给上网用户导航服务。搜 索引擎通过在互联网上提取各个网站的信息( 以网页文字为主) 建立数据库，以便 检索与用户查询条件相匹配的相关记录。c h e k u r i 等人提出先分类后搜索的思想， 但事实上目前大多数入口网站提供的搜索引擎与分类目录次两种检索功能是通 常相互分离的，并且分类目录次下的网页仍采用人工分类方法进行组织。虽然 人工分类精度较高，但要耗费的时间与人力成本难以估计且还存在一致性问题， 即不同的人进行分类判断时会有不同的结果。 在数据库越来越大的情况下，对网页本身加以分类的问题已经越来越多地得到 人们的重视。引入网页分类技术后，我们可以在一个以用户要求为中心、按照范围 缩小了的确定空问来进一步搜索，从而优化了搜索引擎的搜索性能。所以在搜索引 擎相对成熟的今天，更多的人把目光放在了对网页进行分析、分类这一问题上。 1 2 国内外研究现状 网页分类是由纯文本分类技术发展而来的。近年来，研究者们结合机器学习方 法和人工智能的技术进行了大胆的探索，提出了多种分类模型和分类算法。目前文 本分类的研究大致分为以下三类： ( 1 ) 向量空间模型( v s m ) 表示法，文档表示为特征词向量，向量中元素对应词频， 丢弃了特征词在文档中的顺序信息，也称为b o w 表示。使用v s m 的算法大多属于 基于词频统计的学习方法，如朴素b a y e s ( n b ) 【却、支持向量机方法( s v m ) i n 、k n n 4 1 、 l l s f 5 】、n n e t f 9 1 、b o o s t i n g 1 0 1 等。特征词通常要进行选择实现降维，文档向量根据特 征词权重对词频权值进行调整。 l 基于最大熵模型的网页分类 ( 2 ) s o w 表示，跟v s m 相比忽略词频信息，只关心特征词是否出现。使用s o w 的算法有c 4 5 、m p p c r 、f o i l 等符号规则归纳算法。 ( 3 ) 基于语义的表示，v s m 和s o w 表示方式没有考虑特征词的语义信息，基于 文档语义进行分类也是一个研究方向。w o r dn e t 和知网( h o w - n e t ) 分别是描述英、 中文概念的语义知识库。研究表明，基于词频统计的学习方法取得不错的分类性能， 基于语义的分类结果没有显著提高，如果数据集很大分类性能反而降低，这也许跟目 前自然语言理解水平还比较低有关。如何将这两个方向的研究相结合值得关注。 w e b 页面与纯文本页面的主要区别在于，除了文本部分以外，w e b 页面又添加了 一些其它信息，如声音、图象、页面格式以及文字连接等，这些都是在分类过程中 值得参考的一些因素。 ( 1 ) 基于纯文本的网页分类。即把网页转换为纯文本格式； ( 2 ) 基于网页特征的网页分类。单纯利用网页特征在一定条件下也可快速 判定网页类别，如利用标题、资源定位符、链接的已知类别的相邻网页等。 ( 3 ) 文本与网页特征有机结合分类法。单纯利用文本或网页特征在某种程 度上都存在局限性，将二者有机结合的分类模式是最完美的一种分类方法。近 年众多学者在传统文本分类技术基础上还利用网页本身特性来提升分类的精确 性，相关的研究大致可分为： ( 1 ) 网页标识( h t m l t a g ) 辅助式分类 ( 2 ) 网页链接( l i n kp a g e ) 辅助式分类 1 3 研究的难点 万维网是一个分布式的超媒体( h y p e r m e d i a ) 系统，它包含多种表示方式，如 图形、图象、声音、动画甚至活动视频图象，加之网页书写者爱好、水平及其表达 方式各异，这就使网页内容丰富、形式多样，而且鱼龙混杂，给分类带来一定难度。 另外大部分门户网站分类法不再是单维展开方式，而采用多重划分、多元展开的类 归结构，使用链接方式对多重从属关系加以重复揭示。 例如我们对门户网站的教育类目： e d u c a t i o n - 一h i 曲e d u c a t i o n s c i e n c e - - ) e d u c a t i o n b u s i n e s sa n de c o n o m y 一一- - ) s h o p p i n ga n ds e r v i c e s - - 一- - ) e d u c a t i o n r e g i o n a l u s s t a t e 一- ) c i t i e s - ) n e w y o r k - - ) e d u c a t i o n 第一章引言 我们可见其分类体系是以对象加学科辅助及各类目多重覆盖、相互联系、多维展开 的网状分类特征。这就与线形分类特征相比，增加了其分类难度。 最后w e b 页面除纯文本信息外，还有一些网页特有的信息，如h t m l 标签中的 t i t l e 、h n 、b 、i 、u 、m e t a 等标签对分类贡献都不容忽视，因此在设计分类方 法时，必须结合网页特点，将文本信息和网页特征有机的结合起来分析。比如， 同样是“竞技”一词，某一页面出现在h 6 中，而在另一页面出现在h 2 中，它 们的分类权值显然是不一样的。同时也充斥着大量噪声园子，如广告链接、设 计注释、版权申明等和内容无关的信息。如何在普通文本处理技术的基础上选 择有效标记，过滤干扰标记，或者说如何确定网页特征，是一项重要工作。这 是本文解决的关键问题，也是其难点所在。 1 4 本文的组织 第一章引言 介绍了本课题研究的意义、研究的难点以及常用的一些研究方法等。 第二章最大熵模型介绍 引入最大熵概念及最大熵在自然语言处理中的应用模型，并概括了最大熵 模型的优点。 第三章基于最大熵模型的特征提取 第四章用最大熵模型进行网页分类 首先是对网页进行预处理，即把、w w 页面分为c h u b 页面和内容页面两 种，并给出分类算法。然后为分类模型建造类别词词库，以及结合本文研究的 问题进行了特征的归纳，并给出求特征参数的算法，最后对预处理后的两类网 页分别给出特征函数的形式。 第五章系统设计与实验分析 具体设计本实验系统，并给出分析结果。 第六章结论 对本文进行总结并提出下一步要做的工作。 基于最大熵模型的网页分类 第二章最大熵模型 2 1 引言 熵本来是物理学中的一个概念，用来描述客观事物的复杂程度。一切客观事物 自动使自己内部状态的复杂程度在限制条件下达到最大值。要选择在一系列限制条 件下的一种分布时，并且这些限制条件不能确定唯一的一种分布，那么最好的分布 则是具有最大熵的分布。最大熵定理也称作最复杂定理。它也象其他的客观规律一 样自动地在客观事物中体现自己的存在，而不管你喜欢它或者反对它。我们仅有承 认它、利用或者限制它的能力，却没有取消它的权利。最大熵原理是一大批客观现 象的普遍事理的一个集中点。一旦我们认识了它，我们对很多现象的认识也就从感 性阶段提高到理性阶段。从被动承受到主动利用。同时由于最大熵模型的简洁、通 用、易理解性，对于分类问题有着广泛的应用。 2 2 最大熵模型 最大熵模型是用来进行概率估计的。假设a 是某个事件b 是事件a 发生的环境( 或 称上下文) ，我们想知道a 和b 的联合概率，记为p ( a ，b ) 。更一般地，设所有可能 发生的事件组成的集合为a ，所有环境组成的集合是b ，我们想知道，对于任意给定 的a e a ，b b ，概率p ( a ，b ) 是多少? 我们把这个问题放到自然语言处理的领域来讨论，对于网页分类问题，一个w e b 页面分到某个类别可以看成一个事件，页面中出现的词或标记可以看成这个事件发 生的环境，我们想知道包含词或标记b 的页面属于某一类a 的概率。很容易想到的 方法是通过训练语料进行统计。给定一个训练集，定义a = f a 。，a 2 ， 是网页 所属类别集，b = b ，b 。，b 。 是网页的特征词集，s = f s 。s 2 一，s ) 为网页 分类时要参考的标记集，删m ( q ，b j ) 或h u m ( a ，s ，) 为训练集中二元组( q ，6 ，) 或( 口。，5j ) 出现的次数，那么我们可以使用如下公式进行概率估计： p ( a ib ，) ：墨盟 n u m ( a ， 0 5 5 的单字词入库，选定s ( w o r d ，i ) 0 4 5 第三章基十最夫熵模型的特征提取 的双字或双字以上的词入库。 输入的训练语料即熟语料t ，该语料中每一篇文档都带有类别参数。其组成应为 下图所示。这里建造的类别词词库，作为一个候补特征集合f ，要将特征引入最大熵 模型，还必须对这些特征进行优化处理，选择那些对分类有用的特征，去掉多余特 征以提高分类的速度和精度。 3 3 特征优化 3 3 1 常用的特征优化方法 特征优化即对提取的特征进行筛选，去掉对分类贡献小或没有贡献的那些特征。 在我们选定的2 0 0 篇训练语料中，经过特征选择后生成2 4 6 4 0 个类别词。我们研究 发现，类别词集中存在大量出现频率低、区分度小的词。如“上一页”、“首页” 等这些频率较高但对分类影响较小的词。为了进一步提高分类精度和速度，我们引 入特征优化算法。特征优化的主要方式有文档频度( d f ) 、信息增益( i g ) 、交叉 熵( c e ) 、：c 统计、互信息( m i ) 等几种方法。实验证明 8 信息增益和z 统计方法 比较高效。本文用信息增益来进行特征提取。 ( 1 ) 文档频度( d f ) 文档频次是指有该词条出现的文档数量。基于文档频率的特征选择方法首先计算 每个特征的文档频率，然后去掉那些文档频率小于或大于某个阈值的特征。该方法 通常被认为是一个提高效率的特别方法，而不仅仅是一个选择特征词的规则标准， 因为在信息提取中有一个广泛承认的规则标准。 ( 2 ) 信息增益( i g ) 信息增益在机器学习中经常被用作特征词评判的标准，它是一个基于熵的评估 方法，涉及较多的数学理论和复杂的熵理论公式，定义为某特征在文档中出现前后 的信息熵之差。根据训练数据，计算出各个特征词的信息增益，删除信息增益很小 的词，其余的按照信息增益从大到小排序。信息增益评估函数被定义为 g ( a ) _ p ( a 黜小) l o g 掣+ p ( 石) x i p ( b i 协。g 等 其中，p ( a ) 是词a 出现的概率；p ( b ) 是取第i 类时的概率；p ( b ia ) 是假定a 出现 时取第i 类的概率。这个定义比较综合地应用在二元分类模型中，这种计算包括估算 给定词条类的条件概率和在这个定义中的熵计算。概率估计有时间复杂度0 ( n ) 和空 间复杂度0 ( n ) ，其中是n 训练文档的数量，l 是词条的长度，熵计算有时问复杂度 基于最大熵模型的网页分类 o ( l m ) 。 ( 3 ) 交叉熵( c e ) g ( a ) = ；叫b ia ) l o g 裂 p ( b i ) 是取第i 类时的概率；p ( b 。ia ) 是假定a 出现时取第i 类的概率。交叉熵也称k l 距离。它反映了文本类别的概率分布和在出现了某特定词汇的条件下文本类别的概 率分布之闻的距离，词汇的交叉熵越大，对文本类别分布的影响也越大。 ( 4 ) 互信息( m i ) 在统计学中用于表示两变量的相关性。 g ( a ) = l o g 等 p ( a ) 是词a 出现的概率；p ( alb i ) 是假定a 出现在第i 类的概率。 ( 5 ) ) c 2 统计 x z 统计也用于表示两变量的相关性。其同时考虑了属性存在和不存在的情 况。某个词的z 2 统计表示为： x 2 ( a ) = p ( b j ) x 2 ( a ，b j ) 该式表明：x 2 越大特征的独立性越小，相关性越大。 国外学者y i m i n gy a n g z 等对上述特征词的对英文文本关键词提取中作了对比研 究，发现i g 、c h i 、d f 三种方法的效果相当，而m i 方法效果较差。国内北京大学李 晓明等人对中文网页特征提取时也作为这方面的对比实验，得出了相同的结论。我 们在特征提取中借鉴上述经验，采用了i g 方法进行特征提取i t s 。 3 3 2 特征优化算法 这里我们采用信息增益的方法进行特征优化。其研究是建立在前面特征提取基础 上的。我们在最大熵模型中要选取特征，尤其对于自然语言问题，这些特征的选取 往往具有很大的主观性。同时因为特征数量之大，我们必须引入一个客观标准自动 计算以对其进行优化。d e l l ap i e t r a 对自然语言处理中随机域( r a n d o mf i e l d ) 的特 征选取进行了描述，这里进行特征优化时，是由特征的信息增益作为衡量标准的。 一个特征对所处理问题带来的信息越多，该特征越适合引入到模型中。一般我们首 先形式化一个特征空间，所有可能的特征都为候补特征，然后从这个候补特征集合 内选取对模型最为有用的特征集合。特征优化的步骤如下： 第三章基于最大熵模型的特征提取 输入：候补特征集合f ，经验分布p ( x ，y ) 输出：模型选用的特征集合s ，结合这些特征的模型p s ( 1 ) 初始化：特征集合s 为空，它所对应的模型p s 均匀分布，n = o ： ( 2 ) 对于候补特征集合f 中的每一个特征f f ，计算加入该特征后为模型带来的 增益值g f ： ( 3 ) 选择具有最大增益值g ( s ，f ) 的特征； ( 4 ) 把特征f n 加入到集合s 中，s = ( f l ，f 2 ，f n ) ： ( 5 ) 重新调整参数值，使用g i s 算法计算模型p s ； ( 6 ) n = n + l ，返回到第2 步： 该算法的第2 步中，要计算每个特征的增益值，这里是根据k u i i b a c k l e i b l e r ( 简 称k l ) 距离来计算的。衡量两个概率分布p 和q 的k l 距离，公式如下： 驯护莩删n 舞。 距离的大小与两种分布的相似程度成反比，距离越小表示两种分布越逼近。因此 在加入第1 1 个特征前后，求的模型分布与样本分布之间的k l 距离为： 旧 q ( a - 1 ) b 莩 ( x ) l n 瑞 旧 q “) ) 2 莩 ( x ) h 嵩 这样，我们定义引入第i 3 个特征f n 后的增益值为： g ( p ，f n ) = d ( 西l | q “。) d ( 百iq “) 因此选择的第n 个特征为： f - a r g m a x g ( p ，f n ) 模型选取特征是从候补特征集合中选取的，因此我们首先定义一个特征空间， 也可以看作是选取特征的模式，从中派生出所有的候补特征。这个模型选取特征其 实是候补特征的一个子集。 图3 4 模型特征集与优化特征集的关系图 基于最大熵模型的网页分类 不是每一个特征都是对于模型“有用”的特征。只有选择适合的特征集合，才 能使最大熵模型发挥最好的性能。最后对于选取的每个特征都赋予一个权值，也就 是我们模型的参数。这时就可以根据模型进行预测将来的行为。为了能够定量分析 引入特征优化带来的性能改进，我们对网页分类进行了多次实验。具体数值比较见 第五章表。 1 6 第四章用最大熵模型进行网页分类 第四章用最大熵进行网页分类 4 1 页面预处理 对于不同的网页，由于其形式不同，内部结构也有很大差异。本文根据一个w e b 网页中超链接个数的多少，对训练语料进行预分类，预分类的结果作为页面分类的 研究对象。根据页面的链接程度，可以分为两类，即c - h u b 网页和内容网页 z3 j 。对 于不同结构的网页其分类依据也应有所区别。内容网页主要内容为文本格式，所以 可以按照文本分类的方法对其进行研究；而c - h u b 网页页面以超链接为主，按纯文 本分类的方法分析显然不够。所以，在进行网页分类之前，先对该页面初步划分， 若为内容页面，按照纯文本分类的方法分析，若为c - h u b 页面，应结合连接信息进 行类别分析。 4 1 1 相关定义 定义1 ：一个站点内的所有网页可分为二类：一类网页主要是包括大量超链接的 网页，称为c h u b 网页( c o n t e n th u bp a g e ) ，另一类是以文本为主的网页，这种网 页中的超链接是比较少的，称为内容网页( c o n t e n t p a g e ) 。 以一个国内典型的新闻网站w w w s i n a c o m c n 为例，首页就是一个c - h u b 网页， 它几乎所有的内容都是超链接，它指向多个类别的网页，如新闻、体育、汽车等， 点击每个类别后就进入了对应的类别网页，而每个类别网页中包含有该类别的有关 条目，比如新闻类别网页中包含的是一条条新闻的超链接，所以，这些类别网页也 是c - h u b 网页，而其中的超链接所指向的是一条条具体的新闻网页，这些网页则是 内容网页。 定义2 ：设t l ( p ) = 罗| t ( l ) i为网页p 中所有的超链接的文字的长 l 为网页p 磊妇链接集 度之和；z c ( p ) = i r ( c ) j 为网页p 中所有的正文的长度之和；则定义文字 c 为嗣更丽超链搔集 链龇儿r ( t e x tl i n kr a t i o ) = 虱淼1 0 其中：三为一个超链接，t ( 三) 为取出三中的文字的函数，i t ( 工) l 为超链接三中文字 的长度。显然0 s t l r 1 。 定义3 ：设( a ，b ) 是一个开区间，若对于网页集 p i 中的任一网页p ， t l r ( p ) ) a 都成立；反之，对任一网页p ，则t l r ( p ) 6 都成立；反之，任意内容网页，则t l r ( p i ) 6 都成立。可以看出， 基于最大熵模型的网页分类 t l r 临界区( a ，b ) 中的任意一个值都可以作为6 ，一般情况下取6 = ( a + b ) ，2 。 4 1 2 预处理算法 从上述可以看出，区分c - h u b 网页和内容网页的关键问题在于找到对应网页集 的6 ( 中心临界t l r ) 。其步骤如下： 1 对网页集f p i 中的每个网页p ，求出它的t l ( p ) ，t c ( p ) 以及t l r ( p ) ； 2 求出该集合的6 ( 中心临界t l r ) ： ( 1 ) 求出 p i 中最小t l r ：a = m i n ( t l r ( p i ) ) ( 2 ) 求出 p i 中最大t l r ：b = m a x ( t l r ( p i ) ) ( 3 ) 取6 = ( a + b ) 2 3 对于给定网页p ： ( 1 ) 若t l r ( p ) 6 ，则p 为c h u b 网页 ( 2 ) 若t l r ( p ) e 类别。 这样，对于文本分类，最重要的问题是特征函数的选择。一般情况下，特征函 数是一个二值函数，这对文本分类这种基于文档层面应用来说是不够的。我们使用 词频作为特征值 川。对于词w 和类别a ，它的特征函数如下所示： r t ：a = a f w ( a , b ) 。 0 1 。t h e r w i s e 4 其中t i 定义如下，对于一般文本，设所有文本的全部特征总数是n ，则构成一 个n 维的向量空间( 2 7 。其中每一个文本被表示为一个n 维向量( t l ，t 2 ，t 3 t 。，) 。 向量在每一维上的分量对应该特征在这篇文本中的权值。我们引入s a l t o n 2 6 提出的 文本表示方法如下： t i = t f i l o g ( n n i ) ( 4 2 ) 其中，“i 表示该特征在给定文本中出现的次数，即词频；n 是训练集中所含文 本的总数，n 是出现该特征的文本数。 4 2 2c h u b 页面 与内容页面相对应，还有一种w e b 页面，其中存在大量超文本( h y p e r t e x t ) 部 分，我们称其为c - h u b 页面。该类页面结构以超链接为主，只存在极少量文本内容， 页面中即使存在少量非超链接内容，也对分类影响甚小。比如新浪主页就是一个典 基于最大熵模型的网页分类 型的c - h u b 页面，该页面中除了有关版权说明等个别文字外，其余都是超链接部分， 有较高的文字链接比。这类文档信息主要是以h t m l ( h y p e rt e x tm a r k u p l a n g u a g e ) 页面的形式出现的，对此类文档上信息的分析，主要就是对h t m l 文本进 行分析。 h t m l 语言有些类似排版语言，用h t m l 语言写成的源文本由标记( 用“ ” 括起来的代表特定含义的标示) 和文本组成，这些文件本质上仍是文本文件，其基 本格式如下： ( 标题) q h e a d ( 内容) 通常把描述文件结构的 等特殊的符号称为标签( t a g ) 。在每份 h t m l 文件里含有许多标签，标签的格式为 ，标签通 常是成对的，位于标示内容前方的称之为起始标签，表示某一种格式的开始，位于 表示内容后方的称之为结束标签，表示某一种格式的结束，这样一来就以某种格式 标记了文件中的文字，通过这些标签描述出整篇文章的文件格式，经过浏览器解释 后，显示出来的页面效果就象排版系统制出来的印刷品一样。其中 啪 是超文本链按标签，通过设置不同的h r e f 属性值可以把不同的文件，甚至位于不 同的w w w 服务器上的文件，相互连接起来构成网状结构，组成超文本系统。 分析h t m l 语言时，可以利用基于有限状态自动机的h t m l 分析器， 把由 h t m l 语言形式的页面分解成文本块和标记矢量( t a gv e c t o r ) ，标记矢量中的每一个 元素都是一个包含各种属性的复杂特征集，这些属性大致可以分为两类： ( 1 ) 页面中各种资源的u r l ，如链接的定义： ( 2 ) 页面元素的约束属性，如： 往往用来定义文章的段落： 则定义了字体的颜色。 分析h t m l 文件的格式，我们考虑如下的标记： 题头( t i t l e ) ，标题( h 1 ) ，( h 2 ) ，( h 6 ) ，粗体( b ) ，下划线( u ) ， 第四章用晟大熵模型进行网页分类 斜体( i ) ， 文档的标题标记 一级标题标记 二级标题标记 三级标题标记 五级标题标记 锄六级标题标记 吲b 粗体杯记 底线杯记 斜体杯记 f 在模拟i t i q p 协议的 中1响应报头文 表4 2 分类算法中引入的关键标记及其含义 根据这些标记的含义可知：t i t l e 概括和总结了整个网页的内容，因此在分类 中起关键作用。h l ，h 6 中的内容具体地阐述了网页的基本构成，h i 到h 6 的 重要性依次降低。而b ，u ，i 三种格式起强调作用，从一定侧面反映了相关内容。 m e t a 中的数据也提供了一些有用信息，但由于其格式不规范，而且经常不出现，只 起借鉴作用。 综上所述，为了精确表示网页的内容，定义： 标记集s = n t l e ，h l ，h 2 ，h 3 ，h 4 ，h 5 ，h 6 ，b ，u ，i ，m e t a ) 权值集t = t a a 仨s ， 与内容页面数据不同，c h u b 页面的数据是一种半结构化的数据。在网页表示 中，有两个因素影响特征的权值。一是该特征在h t m l 文档中出现的频率，另一个 是该特征在该文档中出现的位置。引入上述定义的标记集和权值集，将公式( 4 2 ) 作一演变，则c - h u b 页面特征的表示方法可为： 基于最大熵模型的网页分类 ( t a t f i a ) l o g ( n n i ) t ；= ：二! ! i ! ：= ：一( 4 - 3 ) 1 z ( ( z ( t a t f j a ) 1 0 9 ( n n 3 ) ) 2 v ， a e s 其中t a 为标记人对应的权值，并且有t t m e t h 。 t h ， t m 砌， t “为词i 在标记人中的词频。结合上小节所述，我们定义c h u b 类页面的特征函 数如下： o ( a ，b ，= ：i 姜善：m 给a ， 其中w 。为标记s 中出现的词，t j 为该词的特征值，如公式( 4 3 ) 定义。 4 2 3 算法描述 特征函数f 的构造算法描述如下。 s t a t u sf e a t u r e a ( i n ti , s t r i n g8 ，a ，i n tf ) i = 1 ； 读第一个特征w ； w h i l e ( 文档b 中还有未分析的特征) f i f ( w i 是类别词) t h e n ( 读取其类别字段a ； i f ( a - a ) t h e n ；k e l s e = 0 ； i = i + 1 ；】 读下个特征w l ： r e t u r n f 上述算法中，t j 值由训练过程通过分析训练语料得到。得到的特征函数，以数 组的形式存储。 以y a h o o 网获取的一个页面文档b 为例来分析其分类过程( 以文档的前三个词 为例) 。经过预处理，t l r ( b ) = 0 3 1 ，显然应归于内容页面。先取a = w 0 1 0 1 ( 股市 类) ，文本经分词后为b 7 ： ( 1 ) 读第一个词w 1 = “昨天”，由于该词不在类别词词库s 中，所以滤去； ( 2 ) 读第二个词w 2 = “保鉴会”，由s 得知该词的类别号a 2 = w 0 1 o l ( 股市 类) ，则有a = a 2 ，所以，。，( a b ) = 珐鉴会股市( 股市，b ) = t 2 ，其中 t 2 由训练过程得到； 第四章用最大熵模型进行网页分类 ( 3 ) 读第三个词w 3 = “保险公司”，有s 得知该词的类别号a ，= w 0 1 0 3 ( 理 财类) ，则有a a 3t 所以f w ，。，( a ，b ) = f 保险公司理财( 股市，b ) = 0 。 这里得到的每一个特征函数都有一个权值与之相匹配，即第二章中参数估计算 法得到的特征参数，将它们引入最大熵模型，通过最大熵计算，即可实现分类结果。 4 3 平滑( s m o o t h i n g ) 技术 从公式( 4 1 ) 、( 4 4 ) 分析得知，对于分类问题，每一篇文档的特征是非常稀疏 的。也就是说，对于一篇文档，大部分特征值是0 ，在分类问题中我们可以采取平滑 技术处理这一问题。本文采取绝对折扣( a b s o l u t e d i s c o u t i n g ) 【4 0 呼滑技术。绝对折 扣平滑技术是指对于模型中观察到的事件进行折扣，减掉一个固定值d ，然后将折 扣得来的概率分摊到所有未现事件中。由于特征函数的值是词频或词的特征值，对 特征出现次数进行折扣时不涉及到保持概率和为l 的问题，所以我们只需直接给所 有出现次数为0 的特征一个值即可。使用绝对折扣平滑技术后，特征函数( 4 1 ) 、( 4 4 ) 变为： 。( a ，啦岱a m = a 哪t 洒 泠s ， 本文我们取d 为0 1 。 基于最大熵模型的网更分类 第五章系统设计与实验分析 5 1 系统设计 本系统主要由三大模块组成：训练模块、测试模块和分类器。 5 1 1 训练模块 训练模块的分析对象是训练文档，首先对训练文档进行词语切分：然后对分词 后的文档进行分析，建造一个初步的类别词库；再进一步特征归纳，提取有用的类 别词生成一个优化的类别词库以供生成特征函数时用，同时产生一系列特征参数。 具体工作如下： ( 1 ) 词语切分。本系统使用f c 2 0 0 0 词语切分软件进行词语切分。我们在实验 中使用的所有w w w 中文页面都要先经过f c 2 0 0 0 的处理，以便得到词语切分完毕 的语料，这样才能够继续后面的研究。 ( 2 ) 特征生成。对词语切分后的文档进一步提取其特征。由于在最大熵模型中， 我们以词类别作为其特征，所以这里特征提取的过程也是一个建造类别词词库的过 程。即把一些较为关键的词语归类然后与其类别一同入库。 ( 3 ) 特征归纳。特征生成的过程我们只考虑到了词语本身的一些特点，作为分 类算法，我们应该提取那些对分类有用的特征进行分析，而对于那些冗余词，如果 不进行筛选，不仅会影响分类速度，还可能影响到分类精度。本系统中我们通过计 算信息增益来提取有用特征，选取那些增益值较大的词形成一个优化的类别词词库。 ( 4 ) 生成特征参数。本系统用了g i s 方法生成特征参数九，作为分类器的输入 文件。 5 1 2 测试模块 测试模块的分析对象是测试预料。输入测试文档，首先要做的工作同样是词语 切分，我们仍用f c 2 0 0 0 系统进行分词处理；然后对所有分词后的测试文档进行分析， 从其超链接的角度把所有w w w 页面分为两类：c - h u b 页面和内容页面，针对不同类 型页面采取不同分类措施，以达到更高的分类精度；最后确定特征函数f ，作为分类 器的输入文件。 ( 1 ) 结构分析。分析对象为分词后的w w w 文档。通过计算页面的文字链接比 并引入一个临界值，来划分页面类型。划分结果生成两个文件，c - h u b 页面文件和 内容页面文件，作为特征函数生成算法的输入文件。 ( 2 ) 确定特征函数。我们对网页结构分析的结果进一步研究，根据最大熵模型 第五章系统设计与实验分析 的概念及对网页页面的分析，确定其特