（模式识别与智能系统专业论文）rss内容过滤算法研究及实现.pdf

r s s 内容过滤算法研究及实现 摘要 随着互联网络的飞速发展，网络上的各种新业务层出不穷，随着 业务本身的发展，人们的生活，工作方式也在改变，互联网史前年代 出现的电子邮件，在今天的商务中被广泛使用，随着更多的人使用互 联网，网络逐渐成为获取信息，知识，商机的重要渠道，诞生于二十 世纪九十年代的r s s ，在信息爆炸的今天，成为了网络中最重要的一 种信息推送方式，本文针对日益广泛使用的r s s 服务，提出了一种 对其内容进行过滤的模型。 本文对r s s 的结构和规范作了介绍，并概述了当前流行的文本 聚类和分类算法，针对目前流行的以关键词为主，对r s s 进行过滤 的方案，提出了一种新的对r s s 内容进行过滤的模型： ( 1 ) 本模型寻求构建一个满足r s s 订阅者需求的最小核心内容 集合，根据r s s 内容的重要性来对r s s 文档内容过滤，提出了基于 分层思想的三层模型，核心层，中间层，外层。其重要性依次递减。 ( 2 ) 在模型中，有效地把聚类和分类算法融合起来，对首次获取 r s s 源的文档内容进行层次聚类，构建内容过滤模型，对后续获取的 内容使用分类算法来满足订阅者的需求。 ( 3 ) 在过滤的机制上，根据r s s 文档内容的特点，采用关键词组 和向量空间模型相结合的方式，充分利用r s s 文档的属性，例如标 题，发布时间，发布源，作者等，有效地甄别了r s s 文档的内容。 ( 4 ) 考虑到了中文的特殊性，尤其是中文分词造成的特殊性，在 模型中引入了增删关键词的功能，并赋予其正向和逆向属性，也便于 灵活更新分词词典，通过这种反馈，提高内容过滤的效果。 最后对模型进行了实验，验证了算法的有效性。 关键词：r s s 内容过滤最小内容集层次聚类 r e s e a r c ha n di m p l e m e n t a t i o no fr s s c o n t e n tf i l t e i u n ga l g o r i t h m a b s t r a c t w i t h 也er a p i dd e v e l o p m e n to ft h ei n t e m e t ，ag o o dm a n yo fn e w n e t w o r kb u s i n e s sa p p e a r s w i t ht h ed e v e l o p m e n to ft h eb u s i n e s s ，t h ew a y o fo u rl i v e sa n dw o r ka r ec h a n g i n g p e o p l e sp a r t i c i p a t a t i o nm a k e st h e n e t w o r kb e c o m e sa ni m p o r t a n tw a yt oo b t a i ni n f o r m a t i o n ，k n o w l e d g ea n d o p p o r t u n i t i e s t h e nr s sb e c o m e s t h em o s ti m p o r t a n tt y p eo fi n f o r m a t i o n p u s hc a r r i e r a g a i n s tt h ei n c r e a s i n g l yw i d e l y u s e dr s ss e r v i c e ，t h i sp a p e r p r o p o s e dac o n t e n tf i l t e r i n gm o d e l t h i sp a p e ri n t r o d u c e st h es t r u c t u r ea n ds t a n d a r do fr ssa n dt e x t c l u s t e r i n g a n dc l a s s i f i c a t i o n a l g o r i t h ma n dp u t f o r w a r dan e wr s s c o n t e n tf i l t e r i n gm o d e l ( 1 ) t 1 1 i sm o d e lc o n s t r u c t sam i n i m u mc o r ec o n t e n ts e tt om e e tt h e s u b s c r i b e r s n e e d c o n s i d e r i n gt h er s sc o n t e n t s i m p o r t a n c e ，w ef i l t e r t h er s sd o c u m e n t sa n dp r o p o s et h r e e - t i e rm o d e li n c l u d i n gt h ec o r el a y e r , t h em i d d l el a y e ra n dt h eo u t e rl a y e r t h ec o r el a y e ri sd e f i n i t e l y s u b s c r i b e r s i n t e r e s t ，w h i l et h eo t h e ri st h e i rs e c o n dc h o i s e ( 2 ) i nt h i sm o d e l ，t h ea l g o r i t h mo fc l u s t e r i n ga n dc l a s s i f i c a t i o na r e i n t e g r a t e de f f e c t i v e l y w r eh i e r a r c h i c a l l yc l u s t e r e dd o c u m e n t c o n t e n t st h a t r e c i e v er s ss o u r c ef o rt h ef i r s tt i m et ob u i l dc o n t e n tf i l t e r i n gm o d e la n d u s ec l a s s i f i c a t i o na l g o r i t h mf o rt h ef o l l o w i n gr e c e i v e dc o n t e n t st om e e t s u b s c r i b e r sd e m a n d ( 3 ) i nf i l t e r i n gm e c h a n i s m ，w ec o m b i n et h ew a yo fk e y w o r d sa n d v s mm o d e la n du s er ssf i l ea t t r i b u t e s ，s u c ha st i t l e ，t i m eo fp u b l i c a t i o n s o u r c e ，a u t h o rt os c r e e nt h ec o n t e n t so fr s sd o c u m e n te f f e c t i v e l y 3 ( 4 ) t h i sm o d e lc o n s i d e r st h es p e c i a lc h i n e s en a t u r ea n dt h ea d d i n g a n dd e l e t i n go f k e yw o r d s i t sf o r w a r da n dr e v e r s ea t t r i b u t e sm a k ei tm o r e f l e x i b l ef o ru p d a t i n g d i c t i o n a r y b yf e e d b a c k ，t h em o d e l sc o n t e n t o ，一 t l l t e n n ge n e c t l v e n e s si si n c r e a s e d f i n a l l y , w ed os o m ee x p e r i m e n tt ot e s tt h em o d e la n dv a l i d a t et h e a l g o r i t h m k e yw o r d sr ss c o n t e n tf i l t e r i n gm i n i m u mc o n t e n ts e t h i e r a r c h i c a lc l u s t e r i n g 4 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 翅匕皇日期：趟：q 至望 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：妇 ：左日期：巡2 ：2 i ：至8 导师签名： 彳舡日期：如翻心f 北京邮电大学硕上研究生学位论文 1 1 课题背景及其研究意义 第一章绪论 随着网络的进一步发展以及信息化程度提高，截止2 0 0 7 年6 月，中国网民 数量达到1 6 2 亿，仅次于美国的2 1 l 亿，位居世界第二【l 】。网络作为一种沟通， 交流和寻找信息，学习知识的工具受到了普通的应用，网络从由门户控制型向用 户参与型转化过程中，人人都成为信息的作者，信息才真正呈现爆炸性增长，而 传统的靠门户或者媒体主动去推送内容到用户的方式已变得不太合适宜，这之中 主要有下面几个原因：( 1 ) 内容的增长必导致垃圾信息的增长，主动推送对多样 性的用户的需求不清楚，如果一把所有的内容全部推送给用户，带来的必然是更 多的垃圾和用户的反感；( 2 ) 在信息大量增长的前提下，用户人数群的大量增长， 主动推送必然给宿主带来更大的负担；( 3 ) 信息大量增长，加上盲目的推送也必 将给用户带来阅读上的问题，时间愈长，就愈反感这种阅读方式。随着信息增长 和网络上用户人群的增长，以及个人作为作者参与网络的普遍性，在信息订阅方 面也出现了一种新的趋势：对网络信息提供者而言，向传统的分类信息回归，虽 然爱因斯坦说过专业的划分只是现阶段人类认识能力的局限造成的，可是从实际 出发，还是发现大多数人群还是仅对几个专业或者几个类别有兴趣或者熟悉，作 为内容或者服务提供商，捕获大多数人群是他们的目标；另一方面，随着个人网 络写作的盛行，传统的个人主页在逐渐向个人博客转移，这样，现实中的追星效 应延续到了网络之中，在网络之中找习性相似的朋友或者对某人的观点感兴趣， 想拜读其大作等想法大量出现，于是在人们阅读分类信息之外，对个人主页或者 博客的订阅也是一种主流，于是在这种背景下，r s s 作为一种x m l 格式的应用， 被推向了互联网应用的前台，通过r s s 技术，订阅者只要知道信息提供者的网 址就可以按时去相应的网址上获取需要的信息，作为一种被动的推送技术，内容 提供者并没有为此付出额外的代价，比如人力或者服务器开销等。 为什么需要使用r s s 呢? 最初r s s 被设计为用以显示选择的数据资料，如 果没有r s s ，用户要关注某个网站的话，那么就需要不停的打开该网站察看，这 是一件非常耗时的工作，如果有更新的话还算有所值，如果没有更新就是浪费时 间，如果有r s s 地址，则用于只需要一个客户端就可以知道该网站有更新没有， 北京邮电大学硕十研究生学位论文 这只是针对一个网站，对更多的网站，这显然是非常方便的方式，另一方面，由 于r s s 数据量小，也能很好的使用在移动终端上。 使用了r s s ，网络上的信息更容易寻找，对于w e b 内容的拥有者而言，通 过这种方式能把信息传递给更多的用户，从而实现其价值。 这种技术的出现与电子邮件的使用相似，与电子邮件的副作用一样，也有可 能出现大量的垃圾信息，因为订阅者是根据一个网址来进行订阅的，对其中的内 容并不筛选，这需要借助于其它手段实现。提到其他手段时，追本溯源，时光回 溯到1 9 8 2 年，d e n n i n g 提出了信息过滤【2 】的概念，并描述了一个信息过滤的实例， 在电子邮件系统中，利用过滤机制区分紧急邮件和普通优先级邮件，同时根据用 户需要限制例行信息的显示方式，在这种设想下，d e n n i n g 构造了一个“内容过 滤模型 。在后面的十年中，信息过滤的研究逐渐开展起来，并延伸到了很多领 域，随着网络的发展以及人类活动领域的拓展，过去的十年中，在文本过滤及相 关领域取得了长足的进展，并开发了很多文本过滤系统。如s t a n d f o r d 大学开发 的s i f t ( s t a n d f o r di n f o r m a t i o nf i l t e r i n gt 0 0 1 ) 系, 统p j ，s t e v e n s 研制的i n f o s c o p e 系 统 4 1 ，基于协作过滤的t a p e s t r y 5 q 和g r o u p l e n s 7 1 1 8 1 系统，f a b 【9 1 系统则结合了内 容过滤和协作过滤两种方式。 本文把作为载体的r s s 和内容过滤结合起来，提出了一个对r s s 中的内容 进行内容过滤的模型，这方面的内容在国外主要集中在基于关键词组过滤上，而 对国内主要集中在对r s s 的用户兴趣建模和怎样获取更多的内容上，对大规模 的r s s 内容而言并没有提供一种很好的过滤思路。 1 2 本论文的主要研究内容及论文的组织 1 2 1 本论文的主要研究内容 本论文针对日益广泛使用的r s s 服务，提供了对其内容进行过滤的一种新 的方案，从结构上说，e m a i l 与r s s 最大的不同是e m a i l 来源于各种不同的地址， 如果能确定某一个地址为垃圾邮件的地址，则可以直接抛入黑名单中，而r s s 则不同，一般情况下，众多的内容源于一个r s s 源，因此不能采取一刀切的办 法，需要对内容进行深入的了解。与传统的e m a i l 内容不同，r s s 内容订阅更为 杂乱且相对数量巨大，个人的电子邮件信息五花 k f - ，但r s s 内容订阅可以分 为两个类别：一是综合性的内容订阅，其中包含的内容较为凌乱，而订阅者的目 的是了解其中的某一部分内容，而不是r s s 订阅内容的全部，因此对同一个地 址，不同的订阅者需求的东西是不一样的。另一种分类的r s s 内容，类别也过 2 北京邮电大学硕士研究生学位论文 于广泛，对订阅者而言，还需进一步缩小订阅的类别范围。 本文分析了当前对r s s 内容进行过滤的方案，并讲述了w e b 信息挖掘的相 关知识，并根据r s s 内容订阅的特点及订阅者的需要设计了一种寻找最小内容 集的算法，相应的实现了一个模型来检测算法的有效性。 1 2 2 本论文的组织 本论文共分五章，具体的组织如下： 第一章是全文绪论，描述了本课题的研究背景及选题意义，对r s s 出现的 历史，现状及发展趋势作了概要的描述，并简述了本文的主要研究内容及论文的 组织结构。 第二章是r s s 的原理性描述，并描述了r s s 过滤的初始化模型，叙述了当 前w e b 文本挖掘技术在r s s 内容过滤上的使用。其中详细表述了文本分类及文 本聚类的相关算法，为后续的系统设计提供了理论基础。 第三章提出了本文设计的系统架构，简要描述了相应模块的功能，并对系 统中的关键性技术进行了详细分析，提供了评价r s s 过滤，排序系统优劣的方 案，并提出了多种提升系统的建议。 第四章实现了模型并提供了样本来检验其可用性以及r s s 内容订阅者对 r s s 内容处理效果的容忍度。 第五章总结了全文的研究工作，并提出了进一步需要研究的问题。 3 北京邮电人学硕士研究生学位论文 第二章r s s 及文本挖掘技术 基于r s s 的内容过滤主要涉及两部分的内容，一是r s s 标准本身，另一部 份是文本挖掘技术，因此本章着重介绍与本论文相关的两部分的基础知识，一是 r s s 相关技术介绍，主要涉及其历史，标准的产生，现状以及格式；由于本文的 研究对象是互联网上的r s s 内容，所以先对其标准进行描述，并介绍其格式； 二是对常用的w e b 文本分类，聚类，过滤算法的介绍，要构建互联网上r s s 内 容过滤模型，由于内容的交错，不能使用单一的技术去实现，本文把相关技术作 了描述，并详细介绍了流行的文本分类，文本聚类算法，以及其评价标准，但在 实际模型的构建中，作为一个整体，综合了这些独立的部分，其目标是实现订阅 者的需求，而不是考虑这些算法在此模型下得优劣。 2 1r s s 相关技术 2 1 1h t m l ，x m l ，s g m l 和r d f h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) ，中文名超文本标记语言，是创建网页 的标记语言，由w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 联盟创建并负责维护。目前广 泛使用的是4 0 版本，5 0 版本正在开发之中。在数据的展示方面，h t m l 取得 了巨大的成功，但是在对数据进行结构化存储，以及目前广泛使用的数据传输方 面，却遇到了越来越大的麻烦，这主要是由于其把表现和数据的描述放在一起造 成的。 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 应时而生，x m l 主要是表达数据中结构的 共同语法，例如h t m l 中 标记用以对指定文本定义某一字体和大小，在 x m l 中则更为细化，明确用标签定义出信息的种类，而这些定义的种类作为 x m l 的子属性存在，比如可以用 表示人名这个属性， 表示其年龄 这个属性。通过将结构，内容和表现分离开，则通过不同的方式，可以呈现多样 的视图。 s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ( s g m l ) 是在文字处理应用中表达数 据的一个方法。到现在为止，已有十余年的历史，x m l 和h t m l 都是从s g m l 发展而来的文档形式。因此，它们都有一些共同点，如相似的语法和带括弧的标 记符的使用。但是h t m l 是s g m l 的一个应用，而x m l 是s g m l 的一个子 集。这就形成了一个重要的区别：h t m l 不能用来定义新的应用，而x m l 却可 4 北京邮电大学硕上研究生学位论文 以，比如r e s o u r c ed e s c r i p t i o nf o r m a t ( r d f ) 和c h a n n e ld e s c r i p t i o nf o r m a t ( c d f ) 都是使用x m l 定义的应用。x m l 和h t m l 更象表兄弟，而不是亲兄弟。 如果x m l 是说语言的能力，x m l 应用软件则是特定的语言。资源描述格 式( r e s o u r c ed e s c r i p t i o nf o r m a tr d f ) 是这样的一个应用软件：使用x m l 语法的 数据建模语言。r d f 是描述和访问数据的一个方法。这意味着r d f 是关于数据 的数据，或者说元数据。在w e b 中，这些元数据将被用于建立标准的站点地图， 更精确的搜索结果，和分层次的主题索引。通过r d f ，人们可以使用自己的词 汇表描述任何资源，但人们更乐意将它用于描述w 曲站点和页面，一个r d f 文 件包含多个资源描述，而一个资源描述是由多个语句构成，一个语句是由资源、 属性类型、属性值构成的三元体，表示资源具有的一个属性。 2 1 2r s s 概念及历史 r s s 1 3 】【1 4 】【1 5 1 不像其长辈e m a i l 那样有一个建议的r f c 文档并以一种统一的 格式出现在应用中，从下面的历史可以看出，其根据差异分成两个派别，最初可 以追溯到19 9 5 年a p p l e 公司的r a m a n a t h a nv g u h a 等人提出的m c f ( m e t ac o n t e n t f r a m e w o r k ) ，接着在应用领域出现的是1 9 9 9 年，n e t s c a p e 公司的g u h a 提出的第 一个r s s 版本，即后来所知的r s s0 9 版本。但其格式由于采用了r d f 来描述， 显得较为复杂，在后续的r s s l 0 版本延续了这种风格，大概四个月后，同样来 自于n e t s c a p e 的d a nl i b b y 简化了格式，即移出了g u h a 的r d f 元素，采用了 d a v ew i n e r 的一个新闻脚本同步格式，此时，r s s 的简写从r d fs i t es u m m a r y 变成了m e l ls i t es u m m a r y ，同时，此版本被命名为r s s0 9 1 。由于最初的分歧， 从而在r s s 进化的历史上出现了两条并行的路线：一是以r d f 为描述框架的 r s s ，其包括的版本如下： 1 ) r s so 9 0r s s 最初的版本，n o t s c a p e 公司创建，其r s s 是r d fs i t e s u m m a r y 的简称，作为一个初稿与最终的r s s 标准并不兼容。 2 ) r s s1 0 ，是r s s d e v 工作组定义的开放格式，其在2 0 0 1 年1 2 月发布， 其仍然是r d fs i t es u m m a r y 的缩写，但与r s s0 9 并不完全兼容，因为其建立 在r d f1 0 标准之上，但加入了x m l 名字空间。 3 ) r s s1 1 是为了更新和替代r s s1 0 推出的，其是一个相对中立的标准， 但是后来却没有组织或者个人对其正式的支持。 r s s2 x 分支包含如下一些版本： 4 ) r s s0 9 1 是n e t , s c a p e 释放出来的一个简化版本，此版本的名称中的r s s 是砌c hs i t es u m m a r y 的简写，这主要是其脱胎于r s s0 9 0 ，但是却没有使用众 5 北京邮电大学硕士研究生学位论文 所周知的r d f 格式来描述，使其化繁为简，今天开来他派生出来的变体使用最 多。 5 ) r s s 0 9 2 到r s s 0 9 4 是对r s so 9 1 的扩展，其中r s s 0 9 1 在2 0 0 1 年1 2 月发布，由于其引入了c l o s u r e 元素，使得可以加入音频文件在r s sf e e d s 中， 使得博客迅速传播开来，接着发布的r s s 0 9 3 ，o 9 4 仅是细节的修补，但保持了 良好的兼容性，此时，r s s 不再是一个缩写。 6 ) r s s 2 0 1 是一个r s s 2 0 的内部版本号，此版本出来后，宣称所有的特性 均将冻结，但是仍在持续的更新，只不过版本号不再变化，现在r s s 是r e a l l y s i m p l es y n d i c a t i o n 的简写，此版本相对于0 9 x 系列的版本最大的变化是引入了 x m l 名字空间，并且移出了r s s 0 9 4 种加入的t y p e 属性。 2 1 3r s s 规范 从上文可以看出，r s s 从其产生开始就差不多两个流派并行，一直并行发展， 随着其在w e b 中应用的广泛，易用性占据了上风，其中类r s s 2 0 规范占整个 r s s 使用量的7 5 以上( 数据来自w w w w 3 s c h o o l s c o m ) ，但由于绝对数量巨大， 本文仍将介绍两种主流规范。 r s s l 0 源于最初的r s s 0 9 0 ，其采用r d f 格式来格式化和传输数据，其规 范均使用了r d f 来格式化每一个子元素，整个r s s 内容显得比较冗余。r s s 2 0 的规范，则移出了复杂的r d f 格式，采用了传统的x m l 格式，简化了r s s 内 容的格式化和传输。 图2 1 是r s s 2 0 格式框图，从中可以看出由于其提供了时间戳以及该内容 的宿主，再加上内容，则可以设计一种思路来对其进行分类排列，例如该i t e m 是订阅者需要的，还是不是订阅者需要的等，在后面的叙述中，将提供一种从中 提取订阅者有用信息的思路。 6 北京邮电大学硕士研究生学位论文 图2 - 1r s s 2 0 格式解析 2 1 4 传统w e b 浏览与r s s 订阅信息的区别 传统w e b 浏览方式浏览着需要打开多个浏览器窗口或者标签，进入不同的 门户网站，然后寻找浏览器感兴趣的标题，接着点击相应的链接查阅具体的内容， 在一些门户网站，浏览者为了查看某项具体的内容，需要多次点击鼠标，在这种 浏览方式中，一般浏览者并不关心内容的实效性。通过r s s 订阅w e b 消息，则 是把订阅者订阅源发布的消息全部集中到一个窗口中，然后订阅者再点击相应的 感兴趣的内容，订阅者在r s s 聚合站点或者r s s 阅读器中有针对性的订阅自己 感兴趣的信息源，利用r s s 技术，目标信息源将r s s 内容f e e d 即时传送到聚合 站点或者r s s 阅读器中，订阅者只要访问一个自己定制的聚合站点或者阅读器 就可以获取感兴趣的信息，重要的是这些信息是即时的，看起来，r s s 订阅方式 如同浏览器的收藏夹，但对于收藏夹中的数百千个网站，只有逐一浏览才能知道 更新与否，但对于r s s 订阅，则只要有更新，则会自动推送到聚合站点或者r s s 阅读器中。图2 2 描述了传统的w e b 浏览行为，而图2 3 描述了通过r s s 订阅 的浏览行为。 7 北京邮电大学硕：f ：研究生学位论文 图2 - 2 传统w e b 浏览行为 2 2 文本挖掘技术 图2 - 3r s s 订阅信息行为 基于r s s 的内容过滤是文本挖掘技术这个大方向中的一部分，因此在本节 对文本分类技术进行介绍，并对本文相关的一些文本挖掘概念和算法进行深入的 探讨。 文本挖掘【1 6 】【1 刀【1 8 1 是- - f 7 综合技术，其涉及到了数据挖掘，计算机语言学， 自然语言处理，信息科学等多个领域，从不同的目的出发，对其理解也不尽相同， 因此一直以来，也没有一个比较公允的定义来描述文本挖掘，本文对文本挖掘作 如下的描述：文本挖掘是指从大量文本数据中找出匹配某种模式的信息或知识的 8 北京邮电大学硕士研究生学位论文 过程，一般地，提取文本摘要，对文本进行分类，聚类，关联分析以及根据文本 关键词等进行趋势预测等均可以划入文本挖掘领域，在介绍中，文本挖掘包含以 下几部分：文本检索技术，文本自动分类技术，文本自动聚类技术，话题检测跟 踪技术，文本过滤技术，关联分析技术，文档自动摘要技术，信息抽取，智能问 答( q a ) 技术，o n t o l o g y 技术等。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个 适当的类别，利用此技术可以迅速的为大量文档进行自动分类，目前分类算法繁 多，例如朴素贝叶斯，支持向量机，决策树，k 最近邻算法等 文本聚类与分类不同之处在于聚类并没有固定的事先定义的类别，其目标是 将要聚类的文档集合聚成若干个子集合，要求每一个子集合中的文档内容的相似 度尽可能大，而不同子集之间的相似度尽可能小，目前有多种聚类算法，基于层 次的聚类算法，g h a c ，平面划分法k - m e a n s 等。 作为一个崭新的研究领域，文本过滤项目的任务定义开始时是逐渐演化的， 难度越来越大，以更好地模拟真实环境。从1 9 9 7 年的t r e c 6 开始，文本过滤 的主要任务逐渐固定下来。下面给出t r e c 9 至今文本过滤项目的任务定义【6 】： 给定一个主题描述( 即用户需求) ，建立一个能从文本流中自动选择最相关文本的 过滤模板( f i l t e r i n gp r o f i l e ) 。随着文本流的逐渐进入，过滤系统自动地接受或拒绝 文本，并得到文本相关与否的反馈信息，根据反馈信息自适应地修正过滤模板。， 文本过滤项目包含3 个子任务。一个是被称为分流( m u t i n g ) 的子任务。其定 义为：用户需求固定，提供对应于该用户需求的训练文本集中的相关文本，从用 户需求构造查询语句来查询测试文本集。另一个是批过滤( b a t c hf i l t e r i n g ) ：用户 需求固定，提供对应于该用户需求的训练文本集中的相关文本，构造过滤系统， 对测试文本集中的每一个文本作出接受或拒绝的决策。最重要的子任务是自适应 过滤( a d a p t i v ef i l t e r i n g ) 。它要求仅仅从主题描述出发，不提供或只提供很少的训 练文本，逐一判断输入文本流中的文本是否相关。“接受”的文本，能得到用户的 反馈信息，用以自适应地修正过滤模板。而被“拒绝”的文本是不提供反馈信息的。 这是最接近真实环境，但也是最困难的子任务。 文本摘要时从文档中抽取出关键信息，用简洁的形式对文档的内容进行摘要 或者解释，以达到化繁为简的功用。 基于文本的内容过滤的算法主要有：关键词匹配法，潜在语义索引，神经网 络法。文本过滤有两个突出的特点：内容性和实时性。这两个特点决定了衡量内 容过滤的技术优劣的标准是过滤精度和过滤速度。 关键词匹配法是以特征向量为基础，将文本内容转换为向量的方式，将用户 的需求模型也转换成向量的方式，然后以用户需求之向量与过滤文本之向量的夹 9 北京邮电大学硕士研究生学位论文 角余弦来衡量文本同用户需求的相似度，根据事先约定的关键词匹配的“过滤阈 值 来确定是否滤除。 上面概述了文本挖掘的相关技术，从现在开始讨论文本分类及聚类技术，这 部分内容对基于r s s 的内容过滤算法的研究是必不可少的，由于本文主要针对 中文的r s s 进行内容过滤，本文对中文，其中涉及到中文文本的表示，分词处 理，文本的特征选择和特征抽取，分类模型，聚类模型以及评价标准。 文本分类是根据文本的内容，将待分类的文本分配到已经存在的一个或者多 个类别之中的过程，即建立一个待分类文本与已有类别的映射，基于机器学习的 文本分类过程大部分由两个阶段组成：训练和分类阶段，训练阶段是指从训练文 本中学习分类知识，建立分类器，这种情况下，训练集合中的文本已经确定了相 应的类别；而分类过程则是把待分类的文本通过与分类器中的类别向量进行相似 度计算，从而匹配最大的相似度的类别的过程。文本分类的训练过程和分类过程 可以用图2 - 4 来表示： 分类过程 图2 - 4 文本分类流程图 2 2 1 中文文本的预处理 由于中文文本与英语的巨大差异，在对文本进行向量表示之前，还需要对其 进行分词处理，中文分词把连续的文本划分为有语义的词或者词组，将连续的文 本转换为含有分隔符的词或者词组的序列。现有的分词技术主要有三类：基于字 符串匹配，基于理解，基于统计的分词方法。 1 ) 基于字符串匹配的分词： 按照一定策略将待分词的子串与一个充分大的词典中的词进行匹配，如果在 词典中找到了，即匹配成功。按扫描方式不同，分为正向匹配和逆向匹配，按照 不同长度优先，分为最长和最短，按照是否与词性标注相结合，有单纯的分词方 法和分词与标注相结合的方法。一般采用正向最长匹配和逆向最长匹配，或相结 合的方式来分词，由于这种分词方法中词的选择与词典密切相关，词典不能囊括 北京邮电人学硕士研究生学位论文 所有的词，一方面是语言的不断发展，另一方面，汉语中有大量的方言，其中不 乏大量的特色词汇，所以一部好的或者全的词典对分词的影响很大，另一方面， 不停的对词典进行更新以加入新的词条也是相对有效的工作。这种机械分词方法 有两个较大的缺点，一是一些交集词汇的处理，有时无从判别，比如“辛勤劳动”， 是“辛勤，“勤劳刀，“劳动 ，如何选择需要一定的策略去辅助。二是一些组合， 在特殊语境中“玩笑 ，是作为一个词，也可能作为两个词。 2 ) 基于理解的分词 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则 在后续过程中来处理歧义切分的问题，其分词过程只是整个语言理解过程的一小 部分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义 信息来处理歧义现象。这类方法通常包括三个部分：分词子系统、句法语义子系 统和总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句 法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。该类分 词方法主要有扩充转移网络法、联想一回溯法、邻接约束法、语境相关法、专家 系统分词法、基于神经网络的分词法等。以扩充转移网络法为例，它是一种普遍 应用于数据库自然语言查询中进行语法分析的方法。在实现中，需要建立一个语 法知识集合，用以作为弧间状态迁移的测试条件。利用这种方法可大大提高分词 的精度，与机械分词法相比，切分的智能性更进一步。 3 ) 基于统计的分词 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词，因此字与字相邻出现的频率或概率能够较好 地反映成词的可信度。可以与语料中相邻出现的各个字的组合的频度进行统计， 计算他们的互现信息，定义两个字的互现信息为公式2 1 所示： 1 3 1l ，、 m ( x ，y ) = l o g 二立竺二_ l式( 2 1 ) 。p ( x ) 尸( y ) 其中p ( x ，y ) 是汉字x ，y 的相邻共现概率，p ( 石) 和尸( 】，) 分别是x ，y 在 语料中出现的概率。互现信息体现了汉字之间结合关系的紧密程序。当紧密程度 高于某一个阈值时，就判定该字组构成一个词。此方法仅对语料中的字组频度进 行统计，不需要切分词典，因此称之为统计分词方法。但此方法会经常抽出一 些共现频度高，但并不是词的常用字，比如“有的力，“这一一，“孩子的一等，且 对常用词的识别精度差，时空开销大。实际使用中的统计分词系统都是用一部基 本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，将串频统计 和串匹配结合起来，这样切分速度快，效率高，且利用了无词典分词结合上下文 1 1 北京邮电大学硕上研究生学位论文 分词，自动消除歧义的优点。 2 2 2 文本的向量表示 让计算机处理文本，就必须对文本按计算机能处理的方式进行表示，将文本 表示成数学模型，目前有布尔模型，向量空间模型和概念模型等，本文主要介绍 文本的向量空间模型【1 9 1 ： 向量空间模型目前是使用最为广泛的统计模型，是美国的g s a l t o n 在2 0 世 纪六十年代提出的，顾名思义，用向量来表示文本。该模型的前提是将文档视为 一组词序列，词序列经预处理后得到1 1 个特征词，由这些特征词z 组成一个1 1 维 欧式空间，每一文档被形式化为n 维空间中的一个点，以向量( 碾，呒，形) 的 形式给出，其中形为向量在特征词z 轴上对应的坐标值，即特征词霉在文档 中的权重。权重计算通常采用t f 2 i d f ( t e r mf r e q u e n c y 2 i n v e r s ed o c u m e n t f r e q u e n c y ) 方法。 最初向量中的词的表示是0 ，1 的形式，即文本中出现了该词，表示为l ， 否则为0 ，但这种方式不能精确的描述一些关键词的信息，后来演化为以出现该 词的次数来表示其向量，即词频。词频分为绝对词频和相对词频，绝对词频是词 在文本中出现的频率的绝对数量，相对词频是经过归一化处理后的词频，归一化 处理采用上文提到的t f i d f ，一般地，使用如下通用的公式： 州) 2 忑t f 丽( t , d ) 丽* l o g 雨( n n , 雨+ 0 0 而1 ) 式( 2 - 2 ) 其中，w ( t ，e 1 ) 是项t 在文档d 中的权重，t f ( t ，d ) 是项t 在文档d 中的词频， n 是训练文档的总数，n t 是项t 在训练文档集合中出现的次数， 脚【矿( f ，d ) 幸l o g ( 啊+ o 0 1 ) 】2 是归一化因子。对一篇中文档，经过分词后， 进行特征选择，滤掉一些对分类效果没有影响的词，标点，然后再统计相关词频， 代入上文出现的公式中，即可得到文档的归一化向量空间模型。 2 2 3 特征选择 中文信息处理中，特征项主要是指文本经过切分技术后得到的词汇，所以一 般地，特征项的维数会相当大，在这之中有很多标点，“你 ，“我 等代词，“嘻 嘻哈哈等对文本分类或者聚类意义不大的词汇，除了这些没有语义的词汇外， 北京邮电大学硕士研究生学位论文 另外还有一些词汇对文档的分类或者聚类并没有影响，例如对一些每一篇文档均 出现的词汇，如果使用所有出现的词汇，计算的代价也会很高，特征选择是文本 挖掘中一个很重要的问题。 在自然语言处理中，有很多特征选择方法，特征抽取一般是根据某个特征评 价函数计算各个特征的评分，然后按平分排序，最后选取预定数目的特征项作为 结果【明，目前有很多特征评估函数【2 8 1 【刈：文档频率( d o c u m e n tf r e q u e n c y ，d f ) ， 信息增益( i n f o r m a t i o ng a i n ，i g ) ，互信息( m u t u a li n f o r m a t i o n ，m r ) ，词汇与类别的 r 统计量，期望交叉熵( e x p e c t e dc r o s se n t r o p y ) ，文本证据权( t h ew e i g h to f e v i d e n c e f o rt e x o ，几率比( o d d sr a t i o ) 等。 1 ) 文档频率 d f 是最简单的特征评估函数，他表示在训练集中包含特征项t 的文档数， 该方法基于这样一个假设：d f 较小的特征项对分类聚类的结果影响较小，而 d f 较大的特征项对分类聚类影响的结果较大，该算法优选d f 较大的特征项。 2 ) 信息增益 信息增益是一种在机器学习领域应用较为广泛的特征选择方法。他从信息论 的角度出发，根据特征取值情况在划分学习样本空间时，以所获信息增益的多寡， 来选择相应的特征，对于特征t 和文档类别c ，i g 考察类别c 中出现和不出现词 条t 的文档频率来衡量词条t 对于类别c 的信息增益。特征t 对于文档类别c 的 信息增益i g ( t ，c ) 计算公式如下： i g ( t , c ，= 以& ，c ，- 唱羞豸磊告+ 以瓦，c ，- o s 羞豸磊苦式c 2 - 3 ， 其中：c 为某一类文档集合；7 表示特征t 不出现，信息增益的不足之处在 于它考虑了单词未发生的情况，即在公式中的以夏，c ，”。g 羞豸发苦部分。虽然 某个词条不出现也可能对判定文本类别有益处，但实验证实，这种贡献往往小于 考虑单词不出现情况所带来的干扰。特别是在类分布和特征分布高度不平衡的情 况下，绝大多数类都是负类，绝大多数特征值都是“不出现 的，此时信息增益 大的特征主要是信息增益公式中后一部分( 代表单词不出现情况) 大，而非前一 部分( 代表单次出现情况) 大，信息增益的效果就会大大降低了。 3 ) 期望交叉熵 期望交叉熵是一种基于概率的方法，信息增益要求计算所有特征属性的值， 而期望交叉熵则只计算出现有文档中的单词，其计算公式如下所示： 北京邮电大学硕十研究生学位论文 c e t 叫f ) 莓p c j ) 1 0 9 等 都q ，、， 其中e ( c jit ) 表示出现词条t 的文本属于类别勺的概率，p ( c j ) 嬲jc j 出现 的概率，如果词条和类别相关，即p ( c jt ) 的值大，且相应的类别p ( c j ) 出现的概 率又小，则说明词条对分类的影响大，相应的函数值就大，即该词条有可能被选 中作为特征项。交叉熵反映了文本类别的概率分布和在出现了某个特定词条件下 的文本类别的概率分布之间的距离，特征词t 的交叉熵越大，对文本类别分布的 影响也越大。 4 ) 互信息 如果a 表示词条t 属于类别c 的频率，b 表示包含词条t 但不属于类别c 的 频率，c 表示属于类别c 但不包含词条t 的频率，n 表示整个训练语料中的文档 总数，则词条t 与类别c 之间的互信息为： m i ( c f ) - 岫两苦面 式( 2 _ 5 ) 当文档t 与类别c 相互独立时，m i ( e ，t ) 的值则为0 ，如果训练集合中有k 个类别，则对每个词条w 都有k 个互信息量，取其中的最大值为每个词条的全 局互信息量，然后将全局互信息量进行排序，设定一个阈值，将低于某个阈值的 特征词全部移出，保留在某个阈值之上的词，从而降低特征空间的维数。 5 ) x 2 统计量 石2 统计方法度量词条与文档类别之间的相关程度，并假设词条和类别之间 符合具有一阶自由度的x 2 分布，词条对于某个类别的工2 统计量越高，表明其与