（信号与信息处理专业论文）文本挖掘中若干关键问题的研究.pdf

摘要 文本挖掘中若干关键问题的研究 摘要 文本挖掘是指从文本数据中获取可理解的、可用的知识的过程， 其涉及数据挖掘、模式识别、信息检索、自然语言处理等多个领域的 内容。本文针对文本挖掘中的若干关键问题，例如文本分类的特征抽 取、聚类分析以及查询扩展等，展开了如下的研究： ( 1 ) 基于鉴别语义分析的文本特征抽取。本文提出一个适用于高 维数据的鲁棒线性鉴别模型r d m ( r o b u s tl i n e a rd i s c r i m i n a n ta n a l y s i s m o d e l ) 。该模型采用正则化方法提高传统鉴别分析模型的泛化能力， 并引入能量自适应准则自动选择正则化参数，从而避免了复杂的模型 参数选择问题。在r d m 基础之上，本文提出一种鉴别语义特征抽取 d s f ( d i s c r i m i n a t i v es e m a n t i cf e a t u r ee x t r a c t i o n ) 算法，该算法在文 本的潜在语义空间内进行鲁棒鉴别分析，从而抽取出最能体现分类信 息的语义特征。文本分类实验表明d s f 算法性能优于常用的线性鉴 别分析算法，并且其性能不受潜在语义空间维度大小的影响，从而验 证了r d m 的鲁棒性。 ( 2 ) 基于局部鉴别索引的文本特征抽取。本文研究面向分类的流 形建模方法，提出一个新的文本特征抽取算法一局部鉴别索引l d i ( l o c a l i t yd i s c r i m i n a t i n gi n d e x i n g ) 。该算法用近邻图来描述语义空间 中文本类内的局部邻近结构，同时提出入侵图的概念，并用其自适应 地描述不同类别流形在局部区域内的交叠。l d i 算法通过求解广义特 征值问题得到一个在增强类内流形结构紧致性的同时减少不同类流 形间交叠的最优线性子空间。l d i 算法成功地使用流形学习的思想来 提高文本的类别可分性，文本分类实验结果表明局部鉴别索引算法优 于其它基于流形学习的特征抽取算法。 ( 3 ) 基于子类合并的文本聚类。针对传统聚类算法无法发现复杂 文本类别结构的不足，本文提出一个新的自适应子类合并a s m ( a d a p t i v es u b c l u s t e rm e r g i n g ) 算法。该算法首先将文本集划分成若 干个相似粒度的子类，而后根据类中心密度大于类边缘密度的假设将 部分子类合并，从而得出聚类结果。在合成数据和文本数据上的聚类 实验结果表明a s m 算法的聚类有效性明显优于最大方差聚类算法， 北京邮电人学博上学位论文摘要 同时也避免了基于密度聚类算法的复杂的参数选择过程。 ( 4 ) 基于局部一致和全局平滑假设的文本半监督聚类。无监督的 聚类的结果很难与数据的真实类别结构一致。为了解决这一问题，本 文提出一种基于局部一致和全局平滑l c g s ( l o c a lc o n s i s t e n c ya n d g l o b a ls m o o t h i n g ) 的半监督聚类算法。l c g s 算法将已知的少量标 注信息用一个约束等式表示，将局部一致和全局平滑思想体现在目标 函数中，从而将半监督聚类问题转化为一个带约束的二次优化问题， 并最终得到一个全局最优的聚类结果。在文本数据上的实验表明当标 注数据仅占数据总量的2 时，l c g s 算法的聚类有效性就可比无监 督聚类算法高6 0 。 ( 5 ) 融合词语相关性与语义相似度的查询扩展。在文本检索系统 中，查询短小和查询词与索引词不匹配现象会降低系统的检索精度。 为了解决这个问题，本文首先提出一种基于全局分析g a ( g l o b a l a n a l y s i s ) 的查询扩展算法。g a 算法通过统计语料集中词对的互信 息和距离得到索引词间的相关性，从而扩展出与原始查询最为相关的 词。而后，本文将统计分析得出的词语相关性与通过知识库知 网得到的语义相似度融合，提出基于相关性和相似度融合r s i ( r e l e v a n c ea n ds i m i l a r i t yi n t e r g r a t i n g ) 的扩展算法，从而确保扩展词 不仅与查询相关并且与查询的主旨相近。实验结果表明g a 算法的性 能优于局部伪反馈算法，而r s i 算法的检索精度又高于g a 算法。 关键词：文本分类特征抽取文本聚类半监督聚类文本检索查询 扩展 北京邮电大学博士学位论文 r e s e a r c h0 nk e yp r o b l e m si nt e x tn n i n g a b s t r a c t t e x tm i n i n gr e f e r sg e n e r a l l yt ot h ep r o c e s so fd e r i v i n gh i g hq u a l i t y i n f o r m a t i o nf r o mt e x t ，w h i c hi sa l li n t e r d i s c i p l i n a r yr e s e a r c hf i e l da c r o s s i n f o r m a t i o nr e t r i e v a l ，d a t am i n i n g ，m a c h i n el e a r n i n g ，s t a t i s t i c s ，a n d n a t u r a l l a n g u a g ep r o c e s s i n g t h i s d i s s e r t a t i o nf o c u s e so nt h ek e y p r o b l e m s ，s u c ha st h ef e a t u r ee x t r a c t i o ni nt e x tc l a s s i f i c a t i o n ，c l u s t e r i n g a n a l y s i s ，a n dt h eq u e r ye x p a n s i o n ，a n dp r o p o s e st h en o v e la l g o r i t h m sa s f o l l o w s ( 1 ) d i s c r i m i n a t i v es e m a n t i ca n a l y s i sb a s e dt e x tf e a t u r ee x t r a c t i o n t h i sd i s s e r t a t i o np r o p o s e san e wr o b u s tl i n e a rd i s c r i m i n a n t a n a l y s i s m o d e l ( r d m ) f o rh i g hd i m e n s i o n a lt e x td a t a t h er d mm o d e la p p l i e s r e g u l a r i z e dm e t h o dt oe n h a n c et h eg e n e r a l i z a t i o na b i l i t yo ft h et r a d i t i o n a l l i n e a rd i s c r i m i n a n tm o d e l ，a n du t i l i z e sa ne n e r g y - a d a p t i v ec r i t e r i o nt o a v o i dt h ec o m p l e xs e l e c t i o no ft h er e g u l a r i z a t i o np a r a m e t e r a sar e s u l t ， t h i sm o d e lc a na v o i dc o m p l i c a t e dp r o c e s so fp a r a m e t e rs e l e c t i o n u p o n t h i sr o b u s tm o d e l ，t h ed i s s e r t a t i o np r o p o s e sad i s c r i m i n a n ts e m a n t i c f e a t u r e ( d s f ) a l g o r i t h m t h i sa l g o r i t h mf i r s ta p p l i e sl a t e n ts e m a n t i c a n a l y s i st ot h eh i g hd i m e n s i o n a lf e a t u r ev e c t o ra n dt h e nu s er o b u s t d i s c r i m i n a n ta n a l y s i si nt h es e m a n t i cs p a c ei no r d e rt oe x t r a c tt h em o s t d i s c r i m i n a n ts e m a n t i cf e a t u r eo ft h et e x t e x p e r i m e n tr e s u l t sd e m o n s t r a t e t h a tt h ed s fa l g o r i t h mi ss u p e r i o rt oo t h e rc o m m o nl i n e a rd i s c r i m i n a n t a n a l y s i sa l g o r i t h m s w h a ti sm o r e ，t h er e s u l t so ft h i sa l g o r i t h ma r en o t a f f e c t e db yt h ec h a n g i n go fl a t e n ts e m a n t i cs p a c e sd i m e n s i o n s ，w h i c h p r o v e st h er o b u s tc h a r a c t e ro f t h ep r o p o s e dr d mm o d e l ( 2 ) l o c a l i t yd i s c r i m i n a t i n gi n d e x i n gb a s e dt e x tf e a t u r ee x t r a c t i o n t h i sd i s s e r t a t i o nc o n d u c t st h er e s e a r c ho nt h em a n i f o l db a s e dd a t a m o d e l i n g ，a n dp r o p o s e san e wm e t h o df o rt e x tf e a t u r ee x t r a c t i o nm e t h o d c a l l e dl o c a l i t yd i s c r i m i n a t i n gi n d e x i n g ( l d i ) t h i sa l g o r i t h mu s e s i l l 北京邮电大学博士学位论文 a b s t r a c t n e a r e s tn e i g h b o rg r a p ht od e s c r i b el o c a ls t r u c t u r ew i t h i nt h es a m ec l a s s ， a n da p p l i e sc o n c e p to fi n v a d e rg r a p hw h i c hi su s e dt od e p i c tm a n i f o l d o v e r l a p so fd i f f e r e n tc l a s s e s l d ia l g o r i t h m f i n d st h e o p t i m a ll i n e a r s u b s p a c et h r o u g hs o l v i n gag e n e r a l i z e de i g e n v a l u ep r o b l e m ，w h i c hc a l l e r d a a n c et h ec o m p a c t n e s so fw i t h i nc l a s sm a n i f o l da n da tt h es a m et i m e r e d u c e o v e r l a p s b e t w e e nd i f f e r e n tc l a s s e s t h el d i a l g o r i t h m s u c c e s s f u l l ya p p l i e st h em a n i f o l dl e a r n i n gt e c h n i q u e t oe n h a n c et h e ：o a r a b i l i t vo fx t , , g o d e s t h ei ：r i m e n ts h e t h e 30sedseparability o ft e x tc a t e g o r i e s h ee x p e r i m e n ts n o w sm ep r o p o s e a a l g o r i t h mi ss u p e r i o rt o o t h e rf e a t u r ee x t r a c t i o nm e t h o d sb a s e do n m a n i f o l dl e a r n i n g ( 3 ) t e x tc l u s t e r i n gu s i n ga d a p t i v e s u b c l u s t e r m e r g i n g t h i s d i s s e r t a t i o np r o p o s e sa na d a p t i v es u b c l u s t e rm e r g i n g ( a s m ) t oa d d r e s s t h ep r o b l e mo nd i s c o v e r i n gh e t e r g e n o u st e x tc l u s t e r i n gs t r u c t u r e s t h i s a l g o r i t h mh a st w os t a g e s ：s u b c l u s t e rp a t i t i o na n ds u b c l u s t e rm e n n g 1 n e 一一 。 一一 r1 s t r a t e g yo ft h ef i r s ts t a g ei se x p a n d i n gb yt h en e a r e s tn e i g h b o r t 1 1 a ti st o s a yw h e nt h ev a r i a n c eo f t h ec u r r e n ts u b c l u s t e ri sb e l o wt h et h r e s h o l dw e u s et h es u b c l u s t e r sn e a r e s tn e i g h b o rt oe x p a n di t a f t e rt h i ss t a g e ，e v e r y t e x ti nt h ed a t a b a s ei sp a r t i t i o n e di n t os o m es u b c l u s t e ro ft h es a m e g r a n u l a r i t y s u b c l u s t e rm e r g i n gp r o c e d u r em e r g e st h es u b c l u s t e r si fi t s e d g ed e n s i t y i sl a r g e rt h a nt h ea v e r a g ed e n s i t y , b a s e do nt h ea s s u m p t i o n t h a tt h ei n n e rd e n s i t yo ft h ec l u s t e ri sl a r g e rt h a ni t so u t e rd e n s i t y t h e e x p e r i m e n t a lr e s u l t so nt h es i m u l a t e dd a t aa n d t e x td a t av a l i d a t et h a tt h e p r o p o s e da l g o r i t h mc a no v e r c o m et h eh o m o g e n o u sr e s u l t so ft h ev a r i a n c e b a s e dc l u s t e r i n ga l g o r i t h m sa n da l s oa v o i dt h ec o m p l i c a t e ds e l e c t i o no f d e n s i t yp a r a m e t e r ( 4 ) s e m i s u p e r v i s e dt e x tc l u s t e r i n gu s i n gl o c a lc o n s i s t e n c ya n d g l o b a ls m o o t h i n g t h ec l u s t e r i n gr e s u l t sf x o mu n s u p e r v i s e dl e a m i n ga r e o f t e nf a rf r o mt h et e a ld a t ac l u s t e r s i no r d e rt os o l v et h i sp r o b l e m ，t h i s d i s s e r t a t i o ns t u d i e ss e m i s u p e r v i s e dc l u s t e r i n ga l g o r i t h m s ，a n dp r o p o s e sa l o c a lc o n s i s t e n c ya n dg l o b a ls m o o t h i n g ( l e g s ) b a s e ds e m i s u p e r v i s e d c l u s t e r i n ga l g o r i t h m l e g sa l g o r i t h mu s e sar e s t r i c t e de q u a t i o nt or e f l e c t t h es u p e r v i s e di n f o r m a t i o na n da c h i e v e st h el o c a lc o n s i s t e n c y , a n d i m p o s e st h eg l o b a ls m o o t h i n gh y p o t h e s i sb yt h ec o s t f u n c t i o n t h e n l c g sc o n v e r t sas e m i s u p e r v i s e dc l u s t e r i n gp r o c e s si n t oar e s t r i c t e d i v q u a d r a t i co p t i m i z a t i o np r o b l e ms ot h a tt h eo p t i m a lc l u s t e r i n gr e s u l tc a l l b eo b t a i n e d e x p e r i m e n to n2 0 一n e w s g r o u p sd a t a s e ti n d i c a t e st h a t b y u s i n go n l y2 o fl a b e li n f o r m a t i o n ，t h el c g s a l g o r i t h mc a ni m p r o v et h e c l u s t e rv a l i d i t yb y6 0 ( 5 ) f u s i o no fs t a t i s t i c a lr e l e v a n ta n ds e m a n t i cs i m i l a r i t yf o rq u e r y e x p a n s i o n i nt e x tr e t r i e v a ls y s t e m ，q u e r ye x p a n s i o na l g o r i t h m sc a n o p t i m i z et h eq u e r ye x p r e s s i o n so f f e r e db yu s e r sa n de n h a n c et h e p r e c i s i o na n de f f i c i e n c yo ft h es y s t e m t h i sd i s s e r t a t i o nf i r s ti n t r o d u c e sa g l o b a la n a l y s i s ( g a ) b a s e dq u e r ye x p a n s i o na l g o r i t h m t h i sa l g o r i t h m f i r s tc o m p u t e st h ec o o c c u l t e n c ea n dt h ed i s t a n c eo ft e r mp a i r s ，a n dt h e n e x p a n d st h eq u e r yb yt h em o s tr e l e v a n tt e r m si no r d e rt oc l a d f yt h ef u z z 5 , q u e r y t h e nt h i sd i s s e r t a t i o nf u r t h e rp r o p o s e sa q u e r ye x p a n s i o n a l g o r i t h mw h i c hi n t e g r a t e st h es t a t i s t i c a lr e l e v a n ta n ds e m a n t i cs i m i l a r i t v c o m p u t e db yh o w n e t i ta i m st oi n s u r et h a tt h ee x p a n d e dt e r m sa r en o t o n l yr e l e v a n tt ot h eo r i g i n a lq u e r yb u ta l s os e m a n t i c a l l ys i m i l a rt ot h e q u e r y e x p e r i m e n t a l r e s u l t ss h o wt 1 1 a tt h e p r o p o s e dg am e t h o d o u t p e r f o r m st h er o c c h i oa l g o r i t h m ，a n dt h ef u s i o no fg aa n dh o w n e t c a nf u r t h e re n h a n c et h er e t r i e v a lp e r f o r m a n c e k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，f e a t u r e e x t r a c t i o n ，t e x tc l u s t e r i n g ， s e m i s u p e r v i s e dc l u s t e r i n g ，t e x tr e t r i e v a l ，q u e r ye x p a n s i o n v 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：生 日期：兰丝61 塑 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期： 2 丝! ：。! 芝 日期： 兰竺堕：生：! 芝 北京邮电大学博士学位论文 第一章绪论 1 1 课题的研究背景 第一章绪论 文字资料是人类文明的重要的产物之一，对文本内容的理解和应用是知识得 以传播的主要手段。在信息时代，飞速发展的技术手段促使文本的出版、保存以 及传播更加简便快捷。随着计算机技术和网络技术的发展，文本的内涵和外延都 得到了充实。现今，文本不仅仅指存在于纸质媒介上的文字信息，它还涵盖计算 机可处理的电子文档。本文的研究对象“文本”指的是含有纯文本对象的电 子文档，其外延包括各种以纯文本内容为主的文本组织形式，例如，w e b 网页、 电子邮件、短信、博客等。当今是一个信息爆炸的时代，文本作为重要的信息载 体之一，其数量正在以惊人速度增长。中国互联网络信息中心( c n n i c ) 2 0 0 8 年1 月发布的第2 1 次中国互联网络发展状况统计报告中显示，截止2 0 0 7 年1 2 月3 1 日，中国网页总数已经有8 4 7 亿个，年增长率达到8 9 4 ，是2 0 0 7 年互联网基础资源中增长最快的一项，互联网上的信息资源数量日趋丰富；从网 页内容上看，仍是文本居多，占到网页总数的8 7 8 ，其次是图像，音频和视频 网页数量仍旧相对比例不高【l 】。从统计报告中的数据来看，尽管互联网上信息的 组成非常复杂，但文本信息依然占有重要的比重。这是因为文本是信息的主要载 体，而且多数其他形式的信息( 图像、语音) 均可以用文本进行标注。 毋庸置疑，与日俱增的文本信息不断地扩大着人们的视野。然而，海量的信 息也产生了诸多新的问题。例如，文档冗余严重，这主要是由网页间的不断转载 造成的；信息查找困难，由于现有的查找手段较为有限，常无法精确找出淹没在 浩瀚的无序信息之中的有用信息；信息污染，垃圾邮件以及垃圾短信泛滥，互联 网上黄色有害信息横行等等。这些问题导致了所谓的“信息爆炸但知识相对匮乏 现象。与此同时，传统手工的信息提取、标注、分类、过滤和查找方式已经无法 满足人们日益增长的信息需求。因此，如何利用机器自动的处理海量的文本信息， 并从中挖掘出有用信息成为了一个亟待解决的重大课题。文本挖掘的相关技术正 是在这样一个背景下产生并发展起来的。 文本挖掘是一个跨学科的研究领域，它涉及到数据挖掘、模式识别、信息检 索、自然语言处理等多个领域的内容，不同的研究者从各自的研究领域出发，对 文本挖掘的含义有不同的理解。例如，一些学者从数据挖掘角度出发，认为文本 北京邮电大学博士学位论文第一章绪论 挖掘就是利用挖掘技术自动地从文本集中发现隐含模式的过程【2 】【3 】；而另一些学 者则认为文本挖掘所处理的对象是非结构化的文本不同于传统的数据挖掘中的 结构化数据，而将文本挖掘归入以信息检索、自然语言理解等技术为基础的文本 信息处理领域【4 】【5 1 。尽管不同学者对文本挖掘的定义各不相同，但是得到普遍认 可的文本挖掘定义为：文本挖掘是指从文本数据中获取可理解的、可用的知识的 过程，同时运用这些知识更好地组织信息以便将来参掣6 。 在这一广阔的内涵下，文本分类、文本聚类、文本检索、文本摘要、文本情 感分析、文本趋势分析等等都可以看作是文本挖掘中的子任务。目前，文本挖掘 领域的相关工作受到的广泛的关注和研究【刀【8 】【9 】【1 0 】【1 1 】【1 2 1 。本文的工作重点在文本 分类、聚类以及检索中的若干问题的研究。 本章的第2 节分别介绍文本分类、聚类和检索的系统结构和典型应用。然后 在第3 节中指出目前这些研究领域中存在的关键问题。本章的最后介绍本文针对 这些关键问题所提出的创新性算法，并简述了全文的结构安排。 1 2 文本分类、聚类及检索系统概述及应用 本文的研究工作涉及文本的分类、聚类和检索。作为背景知识，本节将从系 统构成和应用前景两方面简要地介绍这三项技术。 1 2 1 文本分类系统概述及应用 文本分类就是在预先设定的分类体系下，根据文本的内容自动确定文本所属 类别的过程。文本类别既可以通过概念进行定义，又可以通过标注的实例学习得 到。 1 文本分类系统概述 文本分类过程本质上就是一个模式识别过程，典型的文本分类系统结构如图 1 1 所示。就功能而言，文本分类系统分为预处理、特征降维以及训练、分类模 块。下面简单介绍这三个模块所涉及到的关键技术。 2 北京邮电大学博士学位论文第一章绪论 输出分类结果 l 坌耋璺曼j 图1 - 1 文本分类系统的总体结构 ( 1 ) 预处理 预处理模块的任务是将文本信息表示成计算机可以处理的结构化信息。这一 过程中涉及到两个问题，其一是文本特征项的确定，而后是文本的表示。对于中 文文本而言，文本是由字、词、短语、句子以及段落等组成的，这些语言单位都 可以作为文本的特征项。特征所处的语法层次就越高就越具有代表性，从而其包 含的信息也就越丰富。但是随着特征语法层次的提高，特征数目会呈现指数增长， 所以其所付出的分析代价也就越大。因此，基于句子和段落层次的特征在文本分 类中较少使用。根据研究人员得出的实验结果，目前普遍认为选取词作为特征项 要优于字和词组【l 引。此外n g r a m 项也常作为文本特征项，它是通过固定长度为 n 的窗口对长文本进行分割得到的【1 4 1 。对于中文来说，n g r a m 项一般由相邻字 构成。例如：从“邮电大学 中提取2 - g r a m 项，可以得到“邮电 、“电大 、“大 学 三个2 g r a m 项。 只有找到一个能把文本和类别进行数学表示的模型，才能够对文本间的相似 度进行计算，因此文本表示是自动文本分类的前提和基础。目前常用的文本表示 模型有三种，即概率模型【1 5 】、布尔模型【1 6 】、以及向量空间模型【1 7 1 。 ( 2 ) 特征降维 无论采用何种文本表示模型，中等规模文本集( 如r e u t e r s 2 1 5 7 8 ) 所对应的 文本特征通常都高达几万、甚至十几万个，其对应的向量空间维数远远多于用于 分类器训练的文本的个数。如果直接在这样一个高维特征空间上进行分类器的训 练和分类，很可能带来两个棘手的问题：一是在训练样本数一定的前提下，过多 的特征使得样本统计特性的估计失真，从而降低了统计分类器的推广能力或泛化 能力，呈现所谓的“过学习 或“过训练的现象；二是很多在低维空间具有良 好性能的统计分类算法在如此高维空间上的计算不可行【引。文本数据最大的特点 3 北京邮电大学博士学位论文第一章绪论 就是特征间具有的相关性、同义性以及多义性。在文本分类系统中引入特征降维 的目的就是希望在减少文本向量中的特征维数并提高分类器的工作效率和性能。 特征降维有两种实现途径：特征选择【1 8 】【1 9 】【2 0 1 和特征抽取【2 l 】。 ( 3 ) 分类算法 文本的分类方法可以分为两大类。一种是基于统计的方法，如n a i v eb a y e s 2 2 1 ， k n n 2 3 】、类中心向型2 2 1 、支持向量机2 4 】【2 5 】、最大熵模型2 卅等方法：另一种是基 于连接的方法，即人工神经网络【2 刀。 2 文本分类系统的应用 文本分类作为处理和组织大量文本数据的关键技术，可以在较大程度上解决 信息杂乱现象，方便用户准确地定位所需信息和分流信息【2 酊。文本分类有着广 泛的应用前景，其中最主要的应用点有如下四点： ( 1 ) 数字图书馆。图书期刊的数字化比例正日益增大，在对图书进行归类 时，图书管理员不可能对各个学科都十分了解。将自动文本分类技术用于期刊和 图书的分类，可以帮助图书管理员快速准确的对图书资料进行归整，极大的减少 人工的工作量。 ( 2 ) 文本的组织和管理。采用文本分类技术来辅助信息资源的组织和管理 不仅能够将人们从繁重的手工分类的劳动中解放出来，而且能大大提高数据组织 和整理的效率和效益，从而能够管理更多的海量资源。例如，美国国家专利和商 标管理局使用的专利分类和查找系统就是一个具体应用实例。该系统根据专利申 请者提供的相关文字资料确定出新专利所属的类型和涉及的具体应用领域，专利 审批者可以将涉及相同应用领域并具有相同类型的所有专利查找出来，与其进行 比较，从而确定新专利的价值。该系统的最大优势在于可以帮助专利审批人员快 速查找与新申请专利相关的所有专利资料，从而大大提高了专利审批的工作效率 【8 】 o ( 3 ) 词义消歧。词义消歧是指找出多义词在特定语言环境下的含义。例如， 英语中的“b a n k 有“银行”和“河岸 两个不同的含义，当出现在短语“t h e b a n k o f c h i n a ”中时，b a n k 指银行，当出现在短语“t h eb a n ko f r i v e r 中时，b a n k 指 河岸。为了解决一词多义的歧义性问题，我们可以将词所处的语言环境看成文本， 而将词的不同意义看成类别，那么词义消歧就可以转化成文本分类问题【8 】【2 8 】【2 9 1 。 ( 4 ) 文本过滤。文本过滤是一种特殊的文本分类过程，其分类对象是从文 本产生者到文本使用者之间不断发送的文本流。文本过滤可以看成一种两类分 类，过滤系统根据用户的特定需求将文本流中的文本分成与需求相关和与需求不 相关的两个类。对终端用户而言，可以用具有文本过滤功能的代理程序来接收原 始文本流，如垃圾邮件过滤【3 0 】【3 1 1 【3 2 1 1 3 3 1 。对信息提供方而言，可以根据用户的信 4 北京邮电大学博士学位论文第一章绪论 息需求过滤新闻、广告等信息，然后将用户可能感兴趣的内容发送给用户，从而 实现主动信息推送。 1 2 2 文本聚类系统概述及应用 文本聚类是将文本集聚合成为由若干个的文本簇组成的集合的过程，并保证 同一类中的文本彼此相似，而异类中的文本各自相异。 1 文本聚类系统概述 文本聚类系统的体系结构如图1 2 所示。文本聚类系统的输入是一个文本集 合，经过分词( 取词干) 、去停用词、特征选择等预处理过程后形成文本矩阵， 然后用聚类算法进行聚类。系统最终输出的是对文档集的划分，这个划分可以是 确定的( 每篇文本只能属于一个类) 也可以是模糊的( 一篇文本从属与多个类别) 。 聚类分析的研究极具挑战性，并存在一系列典型的问题，例如难以发现数据集中 类的形状、大小、密度，对噪音数据敏感等p 引。 图卜2 文本聚美系统的结构图 2 文本聚类系统的应用 文本聚类作为一种无监督的机器学习方法，已经成为对文本信息进行有效地 组织、摘要和导航的重要手段，为越来越多的研究人员所关注【3 5 】【3 6 1 。文本聚类 的主要应用点有以下四点： ( 1 ) 文本浏览。在文本浏览系统中运用聚类技术可以使用户的浏览变得便 捷，并加快用户的信息定位速度。s c a t t e r g a t h e r 就是这样一个基于聚类的文档浏 览系统【3 7 l 。在哥伦比亚大学开发的多文档自动文摘系统n e w s b l a s t e r j s l 中，系统 每晚从网络上搜集当天的要闻，然后对各种新闻进行聚类，并最终对每个类别下 北京邮电大学博士学位论文 第一章绪论 的文本集分别生成一篇简明扼要的摘要提供给用户浏览。 ( 2 ) 改善分类和检索的性能。在分类和检索系统中应用聚类技术可以帮助 用户快速准确查找到其所需信息，提高系统分类和检索的精度。v i v i s i m o l 3 9 1 就是 一个成功运用了聚类技术的搜索引擎，其最大的特色就是对搜索结果自动聚类， 提取各个类的关键词，并将聚类结果以及用关键词描述的聚类内容展示给用户。 近年也有学者从服务器端搜集搜索引擎的检索日志，对日志进行聚类分析，并用 此信息指导检索结果的聚类，从而辅助用户通过其自身的兴趣偏好快速定位其所 需信息【4 0 1 。微软研究院的j r w e n 等人则利用聚类技术对用户提出的查询记录 进行聚类，并利用聚类结果更新搜索引擎网站的f a q h 。此外，俄亥俄州立大 学的y c f a n g 等学者利用聚类技术来改善文本分类的结果1 4 2 j 。 ( 3 ) 热点主题发现和追踪。在互联网中，每天都有大量的新网页涌现。如 何快速发现网络中的新兴热点主题并进行追踪对维护社会和谐以及保护国家安 全具有重要的意义。聚类以及增量式的聚类算法不仅可以找出关于已知主题的文 本而且能发现新主题以及新热点【4 引。此外，利用聚类技术对用户的行为进行分 析，还可以发现用户的兴趣偏好，从而实现主动的信息推送f 4 4 j 。 1 ，2 。3 文本检索系统概述及应用 文本检索是指用户根据自身的信息需求向检索系统提交查询，系统依据一定 的相关性准则，在文本集中找出与查询条件相关的文本子集，并按照它们与查询 的相关性进行降序排序，最后为用户返回个有相关性排序的文本子集。从挖掘 的角度出发，文本检索问题可以看作为从文本集中挖掘与用户查询相关信息的过 程。 1 文本检索系统概述 文本检索系统由预处理、索引以及检索排序等模块构成。图卜3 示意了用户 与文本检索系统的交互过程。首先，用户向检索系统提交查询，系统通过检索排 序运算输出与查询相关的文本。此时，用户可以向系统返回其认定为相关的文本， 然后系统根据相关信息进行二次检索并返回优化后的结果。当用户输入的查询过 于短小和模糊时，系统可以通过自身的查询扩展算法添加一定的扩展词，从而提 高检索精度。 6 北京邮电大学博士学位论文第一章绪论 反 馈 八 杏 文本预处理和存储过程 文本检索过程 蔷 图1 - 3 用户与文本检索系统的交互图 若从数学角度来看，文本检索模型可以用一个四元组 d ，q ，f ，r ( q t ，d j ) ) 来 描述，其中： ( 1 ) d 是文本集中的文本逻辑表示； ( 2 ) q 是用户信息需求( 查询) 的逻辑表示； ( 3 ) f 是一种文本与查询之间关系的模型； ( 4 ) r ( q t ，d j ) 是排序函数，其函数值反映文档d i 和查询q i 的相关程度。 文本检索的任务就是定义d 、q 、f 、r ，从而找出满足用户检索需求的文本。根 据d 、q 、f 、r 的不同定义，可以建立不同的信息检索模型，其中最常用的有 布尔模型【1 6 1 、向量空间模型1 7 】1 4 s 1 1 4 6 1 、概率模型 4 t i 4 8 】f 4 9 】【删和语言模型 【5 l 】【5 2 1 【5 3 1 【堋【5 5 】【5 6 1 。 2 文本检索系统的应用 第2 1 次中国互联网络发展状况统计报告中显示，截止2 0 0 7 年1 2 月3 1 日， 我国网民总人数达到2 1 亿，并且7 2 4 的网民使用搜索引擎在网络中搜寻有用信 息并因此获益【i 】。此外，据统计截至2 0 0 7 年底，百度作为世界上中文索引量最大 的搜索引擎，能够索引到超过8 0 亿的中文w e b 页面，而其每天处理的用户查询数 量则是千万量级的。面对如此海量的信息和庞大的搜索需求，如何提高检索算法 的效率和准确率显得尤其重要。文本检索技术的应用范围已经扩展到以下各个领 域： ( 1 ) 通用网络搜索。在互连网中w e b 信息检索与传统文本检索有所不同： 一是信息资源海量，用户对查全率的追求降低，查准率要求越来越高；二是文档 之间的超链接结构。网页间的超链接一定程度上描述了文档间的关联性和权威 性，由此产生了基于超链接结构的检索技术。尽管w e b 页面不同于普通的文本， 网络搜索引擎也发展了其独特的检索和排序算法( 如网页结构分析、超链接分析 等) ，但是w e b 内容分析和w e b 结构分析之间的关系尤如内容和形式的关系， 7 北京邮电大学博士学位论文 第一章绪论 网页的结构信息是为了体现网页的内容而制定的。因此，针对于文本内容分析的 文本检索技术仍然是网络搜索引擎的根基。 ( 2 ) 企业内联网的内容搜索。随着网络技术的发展，众多企业通常将企业 的信息以及各种资源发布到公司的企业内部网站( i n t r a n e tw e b ) 上，让企业各 个职能部门的同事共享公司信息，或者与公司