（信号与信息处理专业论文）特定领域词聚类的研究及用mdl原理对词聚类的研究.pdf

北京邮也火学硬 学位论文 摘要 本文分为两部分，两部分都是对自然语言理解中的词聚类进行研究： 第一部分是面向特定领域的词聚类研究，实现了k 平均聚类和分层聚类算 法，并根据词语搭配关系构造了一种新的词聚类向量空间模型，并对结果进行了 测试分析。第二部分是基于名词形容词共现的词聚类研究，我们看待这个词聚类 问题是对名词形容词联合概率的估算。本文实现了基于m d l 原理的模拟退火算 法，并对名词和形容词对聚类，并对聚类结果进行了分析。 本文的研究结果表明：词语搭配关系的统计抽取具有一定的语法语义特征； 基于m d l 原理的模拟退火算法应用于词聚类的研究可以自动构建词类。 关键词；涧聚类，向量空同模型，m d l 原理、模拟退火算法 a b s t r a c t t h i sp a p e rc o n t a i n st w op a r t sb o t ho fw h i c ha d d r e s s e dt h e p r o b l e m , , o fw o r d c l u s t e r si nn l r i nt h ef i r s t p a r t ，w ed e a lw i t ht h ep r o b l e m so fc l u s t e r i n gw o r d si nas p e c i a lf i e l d w e e m p l o yk m e a n sc l u s t e ra l g o r i t h ma n dh i e r a r c h i c a lc l u s t e ra l g o r i t h mb a s e do nt h e r e l a t i v ep o s i t i o ni n f o r m a t i o no fw o r d s a tt h ee n do ft h i sp a r t ，w eo b t a i na n da n a l y z e t h ec l u s t e r i n gr e s u l t s i nt h es e c o n dp a r t ，w ea d d r e s st h ep r o b l e mo fc l u s t e r i n gw o r d s ( o rc o n s t r u c t i n gat h e s a u r u s ) b a s e do nc o o c c u r r e n c ed a t a w ev i e wt h i sp r o b l o ma s t h a to fe s t i m a t i n ga j o i n td i s t r i b u t i o no fn o u na n da b j e c t i v ep a i r s w ee m p l o yt h e s i m u l a t e d a n n e a l i n g m e t h o db a s e do nt h em i n i m u md e s c r i p t i o n l e n g t h ( m d l ) p r i n c i p l e a tt h ee n do ft h i sp a r t ，w ee l a b o r a t e l ya n a l y z et h ep e r f o r m a n c eo fo u r m e t h o db a s e do nt h em d l p r i n c i p l e w ec o n d u d ew 1t h ef o l l o w i n gr e m a r k s ： 1 ) i ns o l l l e l e x t e n t ，t h ee x t r a c t i o no ft h er e l a l l v ep o s i t i o ni n l o r m a t i o no fw o r d s c o r r e s p o n d e n tw i t ht h er e q u i r e m e n to fs y n t a so rs e m a n t i c 2 ) i nw o r d c i u s t e r i n g f i e l d t h es i m u l a t e d a n n e a l i n g m e t h o db a s e do nt h e m i n i m u md e s c r i p t i o n l e n g t h ( m d l ) c a l lb eu s e d t os o l v et h e p r o b l e mo t a l l l ( ) n a i c a l i yc o n s t r u c t i n g at h e s a u r u s m i n i l l l u ni ) c s c r i p t i o nl e n g t hl r i n c i p l c i h l f 【| | ：i u 人川1 6 i l 4 ，f ，l f ， 第部分特定领域的词聚类的彬f 究 1 1 本论文的选题背景 第一章绪论 数字电子计算机在非数值领域的应用最早是在语言信息处理领域内丌始尝 试的。电子计算机问世不久，就开始了机器翻译实验。但无论同计算机技术本身 的发展速度相比较，还是同计算机在其它领域的应用技术的发展速度相比较，语 言信息处理的发展是相当缓慢的，道路是曲折的。本世纪5 0 年代后期硬6 0 年代 前期美国出现过机器翻译研究的第次热潮。1 9 6 6 年美国科学院语i 。；自动处理 咨询委员会发表的a l p a c 报告给机器翻译泼了一瓢冷水，语言信息处理又有过 一段沉寂期。自7 0 年代后期以来，由于计算机技术的飞速进步和语。i 学理论的 发展，由于一些机器翻译系统和数掘库自然语言界面进入实用，更由一j 社会需求 的推动，语言信息处理研究重新进入繁荣期，其显著标志是已有相当多的语占信 息处理产品进入市场。然而道路并不平坦。原定9 0 年代初完成的国际上两个大 型机器翻译研究计划( 欧共体的e u r o t r a 和日本与4 个邻国的o d a ) 都未能 达到预期的目标。9 0 年代初一一些学者倡导的基于语料库的统计学方泄：同样碰到 藿重障碍。国内外都有相当一部分号家对自然语言处理的现状、i 单论璀础、技术 路线在进行冷静的思考，一些学者认为至今尚未能跨越“语义障碍”，川时也在酝 酿着新的突破。近年来，i n t e r n e t 迅速扩张，大量的信息犹如潮水般f i 自来，这些 信息的主要载体仍然是自然语言，人们渴望发展自然语言信息处理技术以实现文 本自动分类、文献检索、信息提取、语言翻译、自动文摘、自动勘校，j 日速信息、 知识j 文化的交流，促进社会、经济、科学的进步，显然这是每个家都面临 的挑战。语言信息处理技术的发展父有了新的强大的推动力量。随着数据属和网 络等技术的迅速发展，人们迅速搜集数掘的能力越来越强，大量的数据储存存数据 库和数据仓库中。在某种意义七浼 j 前我们不是缺少信息，而是被信息淹没了。 i i 前的数据库系统可以高效地实现故掘的录入、修改、统计、查洵管功能但足 尤法发脱数川t t ，存i - 的关系和舰则，九“袱w 现有的数圳预测未来的发胜趋辨，缺 乏挖拥 敛捌7 肝隐藏的知以的手段，甘j 改_ r “数掂爆炸似知以贫乏”的肌缘。人 们需要订新的、史有效的手段对各种人鞋数据进行挖掘以发挥其潜能，数拂：挖掘 j f - 是在这样的心用需求环境下产生并迅速发展起来的，它的出现为自动和智能地 把海量的数据转化为有用的信息和知识提供了手段。 聚类是数壬l - ：挖f i i 的重要方法，和人i 智能、自然语言相结合的数据挖捌| _ 1 益 成为f i j f 究的课题，聚类的方法已广泛的心川在这一领域。浏聚类就足划某种语言 的某个特定领域术语集中的相关词语进行聚类。词聚类技术的一个重要应用就是 改善信息检索系统的人机交互效率。由于人们对信息源的内容不完全知道，所以 不可能直接检索到信息。人们总是根据信息的一些相似模式来找相关信息的。比 如，当用户面对一。个内容不熟悉的数据库时，往往为提出合适的查询关键词而不 知所措，如果存在一个相关词语的帮助系统，则用户町先输入自己熟知的词语， 自动得到数据库中的一批与之相关的词语，从而帮助用户提出合适的查询要求。 在多媒体浏览系统| j 自动的词聚类也可用来帮助超文本的生成。汉文与西文在 构词上有一些区别对英文而言最好的词聚类方法，对于汉文不一定是最好的。 因此，对于汉语进j r 词聚类方法的比较和研究是很有意义的。词聚类的研究成果 还不多。 综上所述，词聚类的研究正是适合时宜的恰当的选题方向。本文是在总结了 词聚类的共词矩阵的基础上提出了一种基于给定词( 即主题词) 来聚集它的同义 词和近义词的硼聚炎方法，同时设计了其权重评价函数。 1 2 词聚类与数据挖掘的关系 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发t 魁( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ， k d d ) ，是指从大型数据库或数据仓库中提耿隐含的、未知的、非平 凡的及有潜在j 、i 用价值的信息或模式 3 6 1 ，它是数据所。研究中的一个很有应用价 值的新领域，融合j 数瓠：库、人工智能、机器学二j 、统计学等多个领域的理论和 技术。数据挖埘系统的州想情况是一个自治的学习a g e n t ，自动地探索有用的和 令人感兴趣的信息，并以适当的形式报告其发现结果 5 l j ：i | i mj # 卜列- 玲上 f 数扒挖扣f 7 相i 外发挺i 7 j 数圳挖扣m i 要覆盖符种符样小i rd f jj 衄川仃务， 从数捌的颅处s l l i j 天l f j 圳| j ! | j 、聚类分析、放圳分类、偏彳j 榆件、j f 列1 = 5 ：；等等特 定的模式。凶此，这技术应川是一个极富挑战性的任务。圳为近年来 现的数 据挖掘技术能够获得，“泛的应_ f f ! | ，日前被认为是具有令人兴含的研究 m 景。如用 于支持企业关键性决策，f f j 场策略的制定等等。面对汹涌而来的大量数据，企业 埘数据挖捌应川彤成极人的需求，将使这技术迅速得到发腱和完善。幽外，在 大型_ | ； i 业、金融、保险、叭比航等人型食业郁丌始得到应川。内讨总体| 二 处于理论探讨、应用试验阶段。 聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进 下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广 泛地应用在许多应用中。聚类诈在蓬勃发展，有贡献的研究领域包括数据挖掘、 统计学、机器学习、空间数据库技术、，l 二物学、以及市场营销。 为了进一步理清数掘挖掘和聚类的关系，澄清在本论文中提及数据挖掘的必 要性，在此引入数据挖掘系统的体系结构图加以说明。数据挖掘系统的体系结构 图示数据挖掘系统可以大致分为三层结构，如图1 1 所示第一层是数据源，包括 数据库、数据仓库数据挖掘不一定要建立在数据仓库的基础上，但如果数掘挖掘 与数据仓库办同工作，则将大大提高数据挖掘的效率第二层是数据挖掘器，利用 m 三j 曩 ”l 兰j 二二_ 一厂鬲i f 一 飚勇三二 、 一 ： 他 ： 数 ；蠢i 图1 1 数据挖掘系统的体系结构图 i ： l l | 】l ：i u ，、，7 帕 ， ，绝迎 数 l i 挖舶| 力，、分f j i 数拱t ：h i f 的数烈l ：，也矗天l f x 分目i 、j f 歹0 十葵式分丰i 、分类分卡j i 、 聚类分析锋讹j 。；足川，、外i f i f ，将抉取的化! 、l j , f 唑f ：川，o 删斛州脱察的力心 映给f j 户，i t j 以使j f j 可视化【j 具。可见，聚类分析足位t 二数捌挖掘体系的第：联 卜，分析的数据来源是由数钳仓库、数据库、je 他数据库形成的o d b c 或其他数 据库接口。聚类分析必须建屯在数据预处理的艰础之j 二。 凼为b d 聚类的研究的研究对象是文本语料。| f | j 如自然晤言文本、图像、声厅 等，都是难rc f 接放入数据阵。 ，的二j e 结构化数批，恰恰在这些数据驰隐含了巫j i 价值的知i = 。非结构化数据挖掘技术尚未得到深入研究。因此，利用已有的结构 化数据挖掘技术是非结构化数据的知识发现的捷径。在结构化数据( s d ) 挖掘技术 的基础上，非结构化数据( 屿d ) 的知识发现可以有两种途径：1 在知识发现中建 立全新的数据挖掘算法，直接对非结构化数据库进行数据挖掘，此时的数据挖捌 算法完全不同于传统的结构化数据挖掘算法，其挖掘的对象是并未纳入数据库中 的非结构化数据库，由f 非结构化数据库的结构复杂，非结构化的数据挖掘算法 将是极为复杂的。2 在知识发现中仍采用原有的结构化数据库挖掘技术，但先将 非结构化数据转化为准结构化，纳入树形分层数据库( t r e es t r u c l u r e da n d m u l t i p i el a y e r e dd a t a b a s e ，t s m l d b ) ，再利用数据变换函数将其转换为结构 化数据，最后利用结构化数据挖掘算法对结构化数据进行数据挖掘。目前结构化 数据库挖掘技术已相当成熟而诈结构化数据库挖掘技术尚未得到深入研究。本 文采用第2 种途径。即先将i f 结构化的数据库转化为结构化的数据库，并在此基 础上进行数据挖掘。 1 3 聚类分析和分类分析的比较 要谈聚类分析有必螟要l 一别j ：分类。 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模型f 或 函数) ，以便能够使用模型颅测类标记未知的对象类。导出模，诅是基f 对训练数 掘集( 即其类标记已知的数堀对象) 的分析 2 9 1 。 聚类分析与分类和颅测1 i 同，聚类( c l u s t e r i n g ) 分析数据对豫，而不考虑u 知 的类标记。一般情况下，i ) l i 缘数据中不提供类标记，因为不知嗵从何丌始。聚类 。- 州 址，、，5 1r ? 伯玲卫 t ：l 以矧n “：重这徉斡簇( 聚类) ，使霉f 谯令簇f | ，鹩对象j 钍缀t j b 静捌豫隧，碡l + j l i 他族- f t 的肘缘 醍f i 州似。所肜成的徘个簇”- 以靠作个埘鲰炎，i l i 它j 以皆 胤则。聚炎也便于分类编制( t a x o n o m yf o r m a t i o n ) ，将脱察i i j 的内缚鲥【纵成炎 分壕结构，搬类似的事件鲍 织n ：起。聚类方法但撼绞汁方法、机器学j i 力法、 1 l 经霜终方渡秘_ 垂凌数据库戆办法。 谯机器学。t f t 聚类称作龙舱饿或尤教师乒悖i i ；州为和分类学爿卡 ll e ，分类学 爿的例二r 或数引对象仃类别书j i ，m 篮聚类的例r i ! | j 没仃标记，i 觜婴聚类学列 算法来自动确定。 1 。4 溺黎炎掰史回顾 科学技术的f 1 新月异也带动了词聚类的发展。遮不仪体现在词聚类聚类方法 二的不断完耱，也体现在词聚类征逐步走向自动化，即运用计算枫对文档进彳亍自 蘑豹调聚癸。汉字秘英文在匀法缝弱土存在羞穰火不鞫。英文静诵黎类舞法教诸 汉字，效聚并不好。所以有必熨专f 3 为汉字开发“己的词聚类算法。 目前词聚类的发展还处于起步阶段，在这方砸i 的成果不多，国内的i 主= = 要的成 果有： 中基秘举蔽塞动纯磷究顼静豫渡舞、黄泰翼豹一秘精簸豹蠲聚类算法器可变 长统诗语蠢横氅，该文蓬子鼓然语言词与词之闽鹩辅似度，提出了一耱溺懿分层 聚类算法。该算法在算法复杂度和聚类效果上比f 统的基】：贪婪原则的统计聚类 算法都有明晟的改进。存提高预测能力方面，提出了种新的基于类的研变长模 型( v a r i g r a m ) 的生成疗法。 嚣安建筑籽技大学耱李娶警瓣淀豢类方法秘稀突，筵文讨论了诿聚炎方法豹 性能准则，掇m 用模糊淡知冈应用于词聚类。 中国隈料人学的郑# 川，f 晓欧，辛彦的对高j 顷主缨主题词进行共词聚类分 析，这是对隧+ 、文档进行i 然谣言处理对抗原cd 4 4 壤类捡测的研究。 中毽茨辩夫学数崔翥熬专题文歉高频主题词豹共谢聚类分瓠。 传统的谰聚类方法 ：要怒蘩于调频共现，这稚方澎：简尊，编程实现容荔：侄l 是词的信息关j f ) 松澈，f ：容易得别好的效果。在这之后的发展了基于贪黻原则的 8 北京邮i u 大学顾l j 学位论文 统计聚类方法，是以语言的困惑度或似然函数作为判别函数。这类方法的主要缺 点是聚类速度慢，初值对结果影响大，亦陷入局部最优。 词聚类技术的研究正处在发展阶段，尚有许多问题需要解决，需要各界同人 共同努力。 北京邮电大学砸j + 学位论文 2 1 蓠言 第二章词聚类涉及的相关领域 词聚类悬一门交叉学科，在本研究中，自然语言理解、语料库技术、数据 挖掘和人工神经网络等学科的蒸本概念或思想，都对本文产生了直接或闼接的 稚藜律矮。鑫然语言瑾释瑟是零黧诗算税瑾瓣人类饺鲻豹语言，换萄话说就是 人类希望和计算机直接用自然谬畜来对话。自然语裔理解的理论和成果怒本文 词聚类的基础，本文的词汇知 ： 和理论依据都来自于自然语言理解。谣料库是 自然语言理解的重要组成部分，髓前在国内外语料库已经有很多种，通常语料 蓐可以分为糕懑糕痒秘糖语辩，耀语艇痒是未经文零糖工_ 遂翁语秘疼，壤浯辩 库是经过分谢、句法分析、语义椽注等方法处理螽的谮料库。本文使用的就是 经过分词处理后的语料库。数据挖掘也称知识发现，聚类是数据挖掘的麓要方 法，本文中的词聚类是一种新词的知识发现过程，目的是找寻现实世界中同义 词和近意词，数据挖掘的方法对本文有极大的借鉴作用。人工神经网络怒一静 有导戆过程，对j 线往骞羹妊懿遴遂往，人工享孛经戆络援术与聚类分辑黪缝合 是现在研究的热门，本人从中汲取了很多经验。 2 2 自然语亩理解 随着社会静r 益信息化，人们越来越强烈地希望腭囊然语言同计算褫交流。 自然语言理解是计算机科学中的一个引人入胜的、寓肖挑战性的课题。从计算 机科学特别熄从人工智能的观点辫，自然语言理解的任务是建立一种计鳟机模 型，这耱计籁飘模型能够给出象人郝样理解、分橱并燃答骞然语言( 鄹入们日 常使丽躲番耱逶络语言) 貔结鬃。鑫然语言处理礤究在电子诗算辊闷畿之秘藏 开始了，并于5 0 年代初开展了机器翻译实验。当时的研究方法还不能称作带有 北京邮电人学颀卜学位论文 ”智能”。到了6 0 年代乔姆斯基的转换生成语法得到广泛的认可，生成语法的核 心是短语结构规则，分析句子结构的过程就是利用规则自顶向下或自底向上的 句法树生成过程。出于认识到生成语法缺少表示语义知识的手段，在7 0 年代随 着认知科学的兴盛，研究者又相继提出了语义网络、c d 理论、格框架等语义 表示理论。这些语法和语义理论经过各自的发展。逐渐开始趋于相互结合。到 8 0 年代一批新的语法理论脱颖而出，具有代表性的有词汇功能语法( l f g ) 、功 能合一语法( f u g ) 4 i 广义短语结构语法( g p s g ) 等。这些基于规则的分析方法可 以称之为自然语言处理中的”理性主义”。现有的手段虽然基本上掌握了单个句 子的分析技术，但是还很难覆盖全面的语言现象，特别是对于整个段落或篇章 的理解还无从下手。与”理性主义”相对的是”经验主义”豹研究思路，主要是指 针对大规模语料库的研究。语料库是大量文本的集合。计算机出现后，语料可 以被方便地存贮起来，利用计算机查找也很容易。随着电子出版物的出现，采 集语料也不再成为困难。自然语言理解技术大致可分为机器翻译、语义理解及 人机会话技术几个方面。其中机器翻译( m a c h i n et r a n s l a t i o n ) ，又称机译( m t l ， 是利用计算机把一一种自然语言转变成另一种自然语言的过程。智能搜索引擎在 这。一领域的研究将使得用户可以使用母语搜索非母语的网页，并以母语浏览搜 索结果。语义理解通过将语言学的研究成果和计算机技术结合在一起，实现了 对词语在语义层次上的理解。人机会话技术可以为计算机提供下一代的人机交 互接口，实现从文字接口、图形接口到自然语言接口的革命，同时在家用电器 的人性化设计方面有着广泛的应用前景，其技术内涵主要包括语音识别、语音 合成两个核心部分。 尽管自然语言理解在几十年的努力中已取得了长足的进步，但是，现在的 计算机的智能还远远没有达到能够象人一样理解自然语言的水平，而且在可预 见的将来也达不到这样的水平。因此，关于计算机对自然语言的理解一般是从 实用的角度进行评判的。如果计算机实现了人机会话，或机器翻译，或自动文 摘等语言信息处理功能，则认为计算机具备了自然语言理解的能力。自然语言 处理的应用领域非常广泛，如信息检索、信息抽取、自动文摘、多语言检索、 语言生成、语音汉别、数据挖掘、知识发现、智能代理搜索和决策支持等等。 我国自然语言理解的研究起步较晚，比国外晚了1 7 年。国外在1 9 6 3 年就 北京邮l b 人学硕卜学位论文 建成了早期的自然语言理解系统，而我国直到1 9 8 0 年才建成了两个汉语自然语 言理解模型，都以人机对话的方式来实现。口 ) k - f 一年代中期，在国际新一代计算机激烈竞争的影响下，自然语言理解的 研究在国内得到了更多的重视，”自然语言理解和人机接口”列入了新一代计算 机的研制规划，研究单位增多了，研究队伍也壮大了。 本文词聚类技术是对大规模语料库进行处理，词与词之间的位置信息是本 文构造向量空问模型的关键，它的研究依赖于自然语言处理的理论和成果，同 时其成果也必将促进自然语言理解的发展。 2 3 语料库技术 语料库是指按照一定的语言学原则，运用随机抽样方法，收集自然出现的 连续的语言运用文本或话语片段，而建成的具有一定容量的大型电子文库 1 5 】。 从其本质上讲，语料库实际上是通过对自然语言运用的随机抽样，以一定大小 的语言样本代表某一研究中所确定的语言运用总体。作为一种语言学研究方法， 语料库及索引早在十八世纪就在欧洲得到了应用。当时的语料库大多以手工方 法收集，其索引和分析过程也都是通过手工进行的，极为耗时费力。到了十九 世纪，语料库方法在语言学研究中继续得到运用，基于语料库的研究主要集中 在词典编纂和语法研究方面。二十世纪五十年代，基于语料库的语言学研究转 入低谷。八十年代中期是语料库研究的复兴时期。真正意义的现代语料库是指 大型的以电子文档为主要构成的计算机语料库。最早于6 0 年代编制的b r o w n 和l o b 两个计算机语料库，分别具有1 0 0 万词次的规模。进入9 0 年代可以轻 易列举出的语料库有几十个之多，象d c i 、e c i 、i c a m e 、b n c 、l d c 、c l r 等，其规模最高达到1 0 9 数量级。 对语料库的研究分成3 个方面：工具软件的开发、语料库的标注、基于语 料库的语言分析方法。采集到未经处理的生语料不能直接提供有关语言的各种 知识，只有通过词法、句法、语义等多层次的加工才能使知识获取成为可能。 加工的方式就是在语料中标注各种记号，标注的内容包括每个词的词性、语义 项、短语结构、句型和句间关系等。随着标注程度的加深语料库逐渐熟化，成 北京邮l 乜人学硕f 学位论文 为一个分布的、统计意义上的知识源。利用这个知识源可以进行许多语言分析 工作，如根据从已标注语料中总结出的频度规律可以给新文本逐词标注词性， 划分句子成分等。语料库提供的知识是用统计强度表示的，而不是确定性的， 随着规模的扩大，旨在覆盖全面的语言现象。但是对于语言中基本的确定性的 规则仍然用统计强度的大小去判断，这与人们的常识相违背。这种”经验主义” 研究中的不足要靠”理性主义”的方法来弥补。两类方法的融合也正是当前自然 语言处理发展的趋势。 语料库的发展大致可分为三个阶段。第一阶段为初始阶段。这个阶段包括 从十八f ! 纪开始到二十世纪五十年代计算机语料库出现前的各种手工语料库。 语料库发展的第二阶段是复兴阶段。这个阶段是以电子语料库的兴起为主 要特征。从二十世纪六十年代到八十年代，各种计算机语料库纷纷建成。语料 库的发展以容量不断增加和种类的不断扩展为主要特征。 语料库发展的第三个阶段是壮大阶段。第二代超大型计算机语料库开始出 现。如果说第一一代电子语料库是以百万计的话，第三代语料库则以千万甚至亿 计。进入9 0 年代后，由于计算机文本处理技术的广泛应用，各出版社和出版商 已拥有数量巨大的机器可读文本，一个新闻出版单位每天可积累约1 0 0 万词的 机读文本。所以第三代语料库，如牛津文本档案库和美国计算语言学会资助的 a c l d c i 语料库等，规模都超过了1 亿词。根据语料库规模的这样一种巨大的 增长速度，据估计，到公元2 0 1 0 年将出现l 万亿词的语料库。 我国计算机专家也建立了一批语料库，特别是9 0 年代以来，取得了显著 的成就，建立了不同规模和不同用途的语料库：国家语委主持的7 0 0 0 万字现代 汉语历时语料库，清华大学主持的5 0 0 0 万字现代汉语共时语料库，哈尔滨工业 大学机器翻译研究室建立的3 万句对带有词性标注的汉英双语语料库，北京语 言文化大学开发的北京口语语料库和中介语语料库等等。 语料库技术的发展和成熟是本文词聚类研究的不可或缺的条件之一，本文 的研究虽然没有涉及语料库技术，但是使用了语料库技术的成果。没有成熟的 语料库，本文的词聚类是不可能实现的。 北京f f i | ；l 也人学坝j j 学位论文 2 4 数据挖掘 数据挖掘技术的产生背景是随着数据库技术的迅速发展以及数据库管理系 统的广泛应用，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的 信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目 前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现 数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏挖 掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。数据 库中的知识发现是一门交叉性学科，涉及机器学习、模式识别、统计学、智能 数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。从数据 库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许 多方面。在k d d 9 6 国际会议上，f a y y a d ，p i a t e t s k y s h a p i r o 和s m y t h 对k d d 作 了如下描述：指从数据库中获取正确、新颖、有潜在应用价值和最终可理解的 模式的非平凡过程【2 6 】。数据挖掘( d a t a m i n i n g ，d m ) 受多个学科的影响，包括数据 库系统、统计学、机器学习、可视化和信息科学等。依赖于所挖掘的数据类型 或应用领域，数据挖掘可能集成空间数据分析、图像分析、模式识别、w e b 技 术、信息检索、，i i , 珲学等领域的技术。数据挖掘存在多种分类发法，按挖掘的 数掘库分类不同的数据库其数据的描述、组织和存储方式都不相同，一般可以 分为关系数据库、事务数掘库、面向对象数据库、空间数据库、时间数据库、 多媒体数据库、主动数据库、i n t e m e t 信息库等。数据挖掘可以按所挖掘的数据 库的不同而划分为不同的种类，其中从关系数据库中挖掘知识，是使用的最为 ，。泛的一种，也是最为成熟的一类数据挖掘技术。按挖掘出的知识分类，一般 情况下，数据挖掘可以挖掘出的知识包括：关联规则、特征规则、分类规则、聚 类规则、序列模式、数据综合和概括、总结规则、趋势分析、偏差分析、模式 分析等。数据挖掘可以用到的技术方法很多，主要包括：统计分析方法、遗传算法、 粗集方法、决策树、人工神经网络、模糊逻辑、规则归纳、聚类分析和模式识 别、最近邻技术、可视化技术等。从数据库中挖掘的规则可以有以下多种表达 形式：关联规则，特征规则，异常规则，转移规则，序列规则，分类，聚类等。尽管数据 挖掘已有了很多方法，但是，kdd 研究还有许多困难：其一，数据集合性质 北京i | | | jj u 人学硕= l 学位论文 往往非常复杂，非线性、时序性与噪音普遍存在；其二，对数据分析的目标具 有多样性，而复杂目标无论在表达还是在处理上均与领域知识有关：其三，在 多样性目标下，对数据集合的分析，目前还没有现成的且满足可计算条件的一 般性理论与方法。所以，当前数据挖掘的研究是以知识发现的任务描述、知识评 价与知识表示为主线，有效的知识发现算法为中心，面向具体应用，开发原型系统 与实用系统。研究与开发基于数据挖掘的通用工具。 数据挖掘的成果对本文有极好的借鉴作用，本文向量空间模型的基本构造 就是借鉴了数据挖掘技术的成果。词聚类技术和数据挖掘技术的融合给本文带 来了生机和活力。 2 5 人工神经网络 回顾认知科学的发展，有所谓符号主义和联结主义两大流派。符号主义从 宏观层次上，撇开人脑的内部结构和机制，仅从人脑外在表现出来的智能现象 出发进行研究。例如，将记忆、判断、推理、学习等心理活动总结成规律、甚 至编制成规则，然后用计算机进行模拟，使计算机表现出各种智能。符号主义 认为，认识的基本元素是符号，认知过程是对符号表示的运算。人类的语言， 文字的思维均可用符号来描述，而且思维过程只不过是这些符号的存储、变换 和输入、输出而已。以这种方法实现的系统具有串行、线性、准确、简洁、易 于表达的特点，体现了逻辑思维的基本特性。七十年代的专家系统和八十年代 同本的第五代计算机研究计划就是其主要代表。联接主义则与其不同，其特点 是从微观出发。联接主义认为符号是不存在的，认知的基本元素就是神经细胞 ( 神经元) ，认知过程是大量神经元的联接，以及这种联接所引起的神经元的 不同兴奋状态和系统所表现出的总体行为。八十年代再度兴起的神经网络和神 经计算机就是这种联接主义的代表。 人工神经网络是由大量简单的基本元件神经元相互联结，模拟人的大脑神 经处理信息的方式，进行信息并行处理和非线形转换的复杂网络系统。人工神 经网络处理信息是通过信息样本对神经网络的训练，使其具有人的大脑的记忆、 辨识能力，完成各种信息处理功能。人工神经网络具有良好的自学习、自适应、 北京f f f 也人学撷j j 学位论文 联想记忆、并行处理和非线形转换的能力，避免了复杂数学推导。在样本缺损 和参数漂移的情况下，仍能保证稳定的输出。人工神经网络这种模拟人脑智力 的特性，受到学术界的高度重视和广泛研究，已经成功地应用于众多领域，如 模式识别、图象处理、语音识别、智能控制、虚拟现实、优化计算、人工智能 等领域。按照网络的拓扑结构和运行方式，神经网络模型分为前馈多层式网络 模型、反馈递归式网络模型、随机型网络模型等。目前在模式识别中应用成熟 较多的模型是前馈多层式网络中的b p 反向传播模型。神经网络的主要特征是： 大规模的并行处理和分布式的信息存储，良好的自适应、自组织性，以及很强 的学习功能、联想功能和容错功能。与当今的冯诺依曼式计算机相比，更加 接近人脑的信息处理模式。 目前，神经网络和聚类结合的研究是一个新的发展方向，该领域的理论和 方法同样可以使用于本文词聚类的研究。有许多学者正在开展通过神经网络来 做词聚类的研究，神经网络的技术对本文有极好的借鉴和帮助作用。 北京邮 也大学硕卜学位论文 3 1 数据预处理技术 3 1 1 概述 第三章词聚类中若干关键技术的讨论 近年来，数据挖掘引起信息产业界的极大关注，其主要原因是存在大量数据可 以广泛使用，并且迫切需要从这些数据中发现、提炼有用的信息和知识，以广泛应 用于各种领域，包括商务管理、生产控制、市场分析、证券分析、工程设计和科 学探索等。 数据预处理对于建立数据仓库和数据挖掘都是一个重要的问题，因为现实 世界中的数据多半是不完整的、有噪声的和不一致的。数据含噪声( 具有不正 确的属性值) 可能有多种原因。收集数据的设备可能出故障；人的或计算机的 错误可能在数据输入时出现；数据传输中的错误也可能出现。数据预处理包括 数据清理、数据集成、数据变换和数据归约。数据清理可以用于填充空缺的值， 平滑数掘，找出孤立点并纠正数据的不一致性。数据集成将来自不同数据源的 数据整合成一致的数据存储。元数据、相关分析、数据冲突检测和语义异种性 的解析都有助于数据集成。数据变换将数据变换成适于挖掘的形式。数据归约 技术可以用来得到数据的归约表示，如数据立方体聚集、维归约、数据压缩、 数值归约和离散化，而使得信息内容的损失最小。 本文使用的是不规则语料库，即经过分词处理的文本语料，数据预处理的 目的就是从文本语料库中抽取词的相似度信息。跟据本研究的实际情况，在本 研究中对数据进行了信息抽取、去除噪声和构建空间向量模型。 北京| | | | l b 人学烦卜学位论文 3 1 2 信息抽取 数据抽取目的是对数据进行浓缩，给出它的紧凑描述。数据挖掘主要关心 从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从 低层次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是 最原始、基本的信息。人们有时希望能从较高层次的视图上处理或浏览数据， 因此需要对数据进行不同层次上的泛化以适应各种查询要求。因为本文的词聚 类算法涉及两个文本语料，一个是台独领域语料，另一个是人民同报语料。选 用两个语料库是出于如下观点考虑：1 ) 特定语料库包含着词的某种固有使用信 息，针对与特定领域查找相似性近的词，这种信息是必不可少。2 ) 根据本文的 算法，在寻找到修饰词后，如果还在同一语料中查找匹配词，再经过聚类算法， 主题词很有可能被就聚类算法认为成孤立点，这样就与本文的初衷相违背。人 民闩报语料是自然语言处理的一个丰硕成果，本文使用的人民日报语料库的内 容达到了1 8 7 m ，比及在本文台独语料使用的2 m 语料存在着覆盖面广、语义信 息丰富的优点。 本文的数据抽取涉及两个过程。第一个过程是从特定领域语料中抽取主题 词的搭配信息，第二个过程是从人民日报语料中抽取与修饰词匹配的搭配词的 信息。在这两个过程中都要计算一下词语之间的条件概率，把词与词之间的信 息以数值形式保存下来。 3 1 3 数据的去噪 存在不完整的、含噪声的和不一致的数据是大型的、现实世界数据库或数 掘仓库的共同特点。数据含噪声( 具有不正确的属性值) 可能有多种原因。对 如自然语言而言，其处理的前端数据是文本语料，本来就是不规则数据库，数 据抽取的目的就是把自然语言的信息通过数值的方式存储下来：这是一种在经 验模式指导下提取的信息，在经过数据抽取后，还存在着大量随机错误或偏差。 就本文而言，在经过数据抽取后，得到的结果还不是理想的。下面举一个 例来说明在本文中遇到的去噪问题。图3 1 是在没有做数据去噪前抽取的样本。 北京 f f ； b 大学颀i j 学位沦史 必但当局调查多次更海域会汇报竟可可以 f | 尚未算是所他探险家突然为未我们学者 已有无再中共 图3 1 数据预处理前抽取修饰词的样本 由图可见本文中的噪声主要有两方面，一种是标点符号如“。，等等， 另利是“的、为、却、难”等停用词。这种停用词可以和很多词组成搭配关 系，但是在搭配时关联的信息并不强，于本文没有重要的作用，同时却会增大 计算机处理的性能，消耗计算机的资源。本文对这两种噪声都采取了忽略的处 理。图3 2 是处理后的数据组成。 包括笔者当局调查多次海域汇报可以人员尚未算是探险 家突然我们学者有无中共 图3 。2 数据预处理后抽取修饰词的样本 3 1 空间向量模型技术 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以 产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上 说，它只认识0 和1 ，所以必须将文本转换为计算机可以识别的格式。根据“贝 叶斯假设”，假定组成文本的字或词在作用上相互独立，这样，可以就使用文本 中出现的字或词的搭配来代替文本，不言而喻，这将丢失大量关于词真正含义 的信息，但是这种假设可以使词的表示和处理形式化，并且可以在语言处理中 取得较好的效果。 目前，在信息处理方向上，文本中词的表示主要采用向量空间模型( v s m ) 。 向量空间模型的基本思想是以向量来表示词：( w l ，w 2 ，w 3 w n ) ，其中w i 为第i 个特征项的权重。一般可以选择字、词或词组，根据实验结果，普遍认 为选取词作为特征项要优于字和词组。因此，要将词表示为向量空间中的一个 i 顺 一 括女 一 包能，难 北京揶也人学钡卜学位论文 向量，就首先要将文本分词，由这些词作为向量的维数来表示与之搭配的词， 最初的向量表示完全是0 、l 形式，即如果语料库中出现了该词，那么词向量 的浚维为l ，否则为0 。这种方法无法体现这个词在语义中的作用程度，所以 逐渐0 、1 被更精确的词频代替，词频分为绝对词频和相对词频，绝对词频， 即使用词在文本中出现的频率表示词的信息，相对词频为归一化的词频。 在本文中根据研究算法的需要自定义了一种词权重的表示方法，向量空间 模型的权重是由如下公式得出： m 。= p ，( w ，1 w ) 弓( w i1 w ，) 其中。m ，是向量空间模型的权重，尸( w ，1 w ) 是在已知主题词( 主题词的定 义在第四章) w 的情况下回溯其前一词w ，的条件概率。0 ( w ，1 w ，) 是在已知w ， 的情况下，上溯至后一词w ，的条件概率。公式的迸一步说明将在第四章给出。 3 4 聚类分析 对数据的表示通常是以一个特征集来表示，我们称这种数据表示方式为数 掘表示模型。词表示数据对象之间的相似性是根据特征集形成的向量之间的距 离来表示。聚类的目标是把相似的对象聚成相似的组，不相似的对象所在的组 不同。 在统计自然语言处理中，聚类有两种主要的功能。一种是对待探索的数据 分析( e d a ) 。设想一下对不熟悉“英语”或“中文”的人，他或她可以根据聚 类对词进行化分，这个划分的结果有利于他或她理解和分析篇章。e d a 是统计 数掘中最主要的活动，我们无论是面对新的问题，还是开发一个新的概率模型， 还是了解现象的特征，e d a 都是晟基本的步骤。不花费时间检查数据的相似性， 都是一个严重的错误。在自然语言处理中，聚类是特别重要的e d a 工艺，因为 语言对象没有直接的可视化“证据”，可视化的“证据”可以提供直观的理解和 分析，而聚类在自然语言处理中却是不多的可视化“证据”。 在自然语言处理中，聚类的另一个主要作用是归纳。我们先讨论一下英文 的归纳情况。众所周知，在英文中名词和介词的搭配是比较固定的，而且，英 文对名词聚类常会用到介词信息。假设我们要发现名词“f r i d a y ”所搭配的介 2 0 北京邮! 乜大学碳i ：学位论文 词，如果我们已有英文的训练语料，其中包括短语“o n s u n d a y ”、“o n m o n d a y ” 和“o nt h u r s d a y ”，但是没有“o nf r i d a y ”。我们可以猜测“f r i d a y ”前的介词 应该为“o i l ”。那么这个猜测的理论依据是什么昵? 如果我们把英文名词按相同 的语法语义环境来聚类，那么表示同期的词将分为一类，这是因为他们有相同 的环境。如果我们假设一个上下文环境如果对类中一个成员适用，对类中其他 成员也适用。那么我们可以从“o nm o n d a y ”、“o nt h u r s d a y ”、“0 ns u n d a y ”推 断出“o nf r i d a y ”。所以聚类是一个学习的方法，在中文中也有相似的情况，当 然中文和英文的语法不同，不可能用介词来限定名词，而在英语中介词限定名 词的情况与中文中语言搭配或者语言框架很相似，比如“在铁路上”、“在公路 上”、“在大路上”、“在小路上”，假设我们不知道“在铁路上”，那么我们可以 根据聚类的学习方法，得出“在上”是和“铁路”搭配的。 对对象的划分还有一种方法日q 分类。分类和聚类的差别是“有导”还是“无 导”。分类要求事先对各类训练事例进行标注，聚类并不要求事先进行标注，这 样的过程就好像有老师指导和无老师指导的过程。可见，聚类并不依靠事前给 定的归类，而完全依靠数据的“自觉”划分。 现在聚类算法有很多，但是主要可以归为几种基本的类型。根据结构可以 把聚类算法划分为分层聚类和扁平聚类( 或叫非分层聚类) 。扁平聚类是将对象 简单的划分为一定数量的簇。大部分扁平聚类的方法多是用迭代的方法，通常 从一个初始簇开始，然后对对象重新划分，通过迭代来改变划分的簇。分层聚 类是一个分级的聚类，它的叶节点就是聚类的对象，每一个节点都是其母节点 的子类，而母节点就是包括所有子孙对象的簇。在扁平聚类中我们可以根据 对象的划分属于一类还是多类而划分为硬聚类和软聚类。对于硬聚类而言，每 一个对象被分配到唯一的簇中：软聚类和硬聚类不同，对象作为簇中成员的关 系是通过它属于该簇的可能性来表示的。通常这种可能性以概率来表示，在簇 c ，已知情况下，对象x ，的概率分布表示为p ( 。ix ，) ，那么就用p ( c ，lx ，) 来表示 对象x ，是簇c 成员的概率。 尽管聚类已经在广泛的领域内得到了应用，例如统计分析、财政、金融、 医药等等行业，而且也体现了很好的成果。但是应用到自然语言处理中，硬聚 类的算法就表现出了缺陷，这种缺陷源于对聚类算法的假设：每一个对象是属于 北京揶也人学碳卜学位论文 唯一的一个簇的。这种假设明显与事实不符，有许多词可以被划分到不同的类 中，这种现象叫做词的兼类，比如“建议”即可以做名词，又可以做动词。如 果我们把多个对象f 确归类后，再进行研究，那么就会出现一个复杂的兼类网 络。因此，从感觉上软聚类在解决自然语言处理的问题中是更适用的，以“建 议”为例，软聚类可以为“建议”分配两个概率，这两个概率表示为“建议” 分别划分为名词类和动词类概率。然而，软聚类的算法也存在缺点，首先，软