（计算机应用技术专业论文）网络聊天室内容监控预处理研究.pdf

中国科学技术大学硕士学位论文 摘要 随着i n t e r n e t 的飞速发展，网络聊天室以其操作简单、方便快捷、私密 性好等优点已经迅速发展成为最普遍的网络交流方式之一它在为用户带来便 利的同时，也为一些别有用心的人进行恶意甚至违法的活动打开了方便之门。 因此，对聊天室内容进行监控已成为亟待解决的问题。 对聊天数据进行预处理是聊天室内容监控过程中的基础部分，预处理结果 的好坏，直接影响到监控系统工作的稳定性、快速性和准确性。由些可见，针 对聊天数据预处理工作的研究是十分重要和必要的 本文以流行的i r c 网络聊天室的内容监控为背景，对聊天数据的预处理技 术进行了深入的研究。论文的主要工作与特色有： ( 1 ) 通过加强的聊天数据时序性启发规则集推断聊天数据的社会网络， 并结合用户对话相似性优化社会网络。该方法通过分析用户间聊天 对话表现出的时间上的一般性规律，总结出用于推断社会网络的启发 性规则集，并根据该规则集来推断聊天数据中包含的社会网络；合并 相似用户对话，结合对话内容相似性优化社会网络。 ( 2 ) 提出了聊天数据中噪声对话的概念，并设计了噪声判断和过滤的方 法该方法根据通过从聊天数据中推断出的社会网络确定用户之间 的交流关系；然后通过分析用户对话的数量、时间和对话对象等因素， 建立噪声过滤的条件集，并根据过滤条件集遍历社会网络中的每个结 点，删除结点的噪声对话和孤立结点。 ( 3 ) 设计了一种专门针对聊天数据中词汇权值计算的方法首先通过比 较聊天数据集与文本集之间的差别，概括出聊天数据的特殊性，并分 析目前监控系统中常用的t f * i d f 方法计算聊天词汇权值的缺点；然 后，针对这些特殊性和不足，提出了一种专门用于聊天词汇权值计算 的方法c d t f i d f 方法。通过实验比较这两种方法。c d t f 1 d f 方法获得了更高的准确率。 关键词：聊天室监控，预处理，社会网络，词汇权值，噪声过滤 1 1 | 中国科学技术大学硕士学位论文 a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fi n t e m e t , c h a tr o o mb c c o m 嚣o n eo ft h em o s t p o p u l a rc o m m u n i c a t i o nm a n n e r s 3o ni n t e m e tb yt h ev i r t u e so fe a s yo p e r a t i o n , s p e c d i n e 嚣，p r i v a c y i tb r i n g sm u c hc o n v e n i e n c et ot h eu s e 培h o w e v e r , i ta l s o p r o v i d e sa no p p o r t u n i t yt o t h em a l i c i o u st oa c h i e v et h e i rs p e c i a lo b j e c t s s oi t b e c o m e sam a t t e ro f u r g e n c yn e p a i st ob er e s o l v e d t h ep r e t r e a t m e n to fc h a td a t ai st h eb a s e m e n to fm o n i t o r i n gc h a tr o o mc o n t e n t i nt h es y s t e m , a n dc h a td a t ap r e l r e a t m e n ti n f l u e n c e ss t a b i l i t y , s p e e da n d a c c m a c yo f t h es y s t e m s oi ti so b v i o u s l yt os a yt h a tp r e t r e a t m e n to fc h a td a t ai sm o s ti m p o r t a n t a n dn e c e s s a r y i nt h i st h e s i s ，w et a k et h ec o n t e n to ft h ep o p u l a ri r cc h a tr o o ms y s t e ma st h e o b j e c to f m o n i t o r i n g , a n dt a k ea ni n - d e p t hs t u d yo nt h ep r e t r e a l m e n to f c h a td a t a t h e t h e s i sc o m p r i s e st h ef o l l o w i n gm a i np a r t s ： ( 1 ) d e d u c i n g t h es o c i a ln e t w o r ki nc h a td a t ab yf e a t u r e so fu t t e r a n c e s t e m p o r a lr e l m i o n sa n dc o n t e n tc o m p a r a b i l i t y t h r o u g ha n a l y z i n gu n i v e r s a lt e m p o r a lr u l e so fu t t e r a n c e si nc h a td a t a , w eb u i l du pas e to f h e u r i s t i cr u l e s ，a n dt h e nd e d u c et h es o c i a ln e t w o r k b yt h e s eh e u r i s t i cr u l e s ( 2 ) j u d g m e n ta n df i l t e rn o i s eu t t e r a n c ei nt h ec h a td a t a w ec a nd e f m et h er e l a t i o no f u s e r si nc h a tr o o mb yt h es o c i a ln e t w o r k o ft h ec h a td a t a t h r o u g ha n a l y z i n gt h ea m o u n t ，t i m e , o 均e c to fu s e 糟 u t t e r a n c e sa n ds oo n , w eb u i l du pas e to f c o n d i t i o n st o j u d g et h en o i s e , t h e ni n s p e c te v e r yp o i n ti nt h es o c i a ln e t w o r k , a n dd e l e t et h en o i s e u t t e r a n c e sa n di s o l a t e dp o i n t si nt e r mo f c o n d i t i o ns e t ( 3 ) d e s i g n i n g an e wm e t h o dt oc a l c u l a t et h et e r m s w e i g h ti nc h a td a t a t h r o u g hc o m p a r i n gc h a td a t aw i t ht e x ts e tw eg e tt h ep a r t i c u l a r i t yo f c h a td a t aa n dt h es h o r t c o m i n g so ft h em e t h o dt f * i d ft h a ti 8u s e dt o c a l c u l a t e t e r m s w e i g h t i n t e x t a i m i n ga t t h ef e a t u r e sa n d s h o r t c o m i n g s ，w ed e s i g nan e wm e t h o dt oc a l c u l a t et c 哪n s w e i g h t 中国科学技术大学硕士学位论文 b s t r c t n a m e dc d t f + i d f1 h mi ss p e c i a lf o rc h a td a t a e x p e r i m e n t ss h o w c d t f + i d fw o r k sb e t t e rt h a nt f + i d fi nc h a td a t a k e yw o r d s ：c h a tr o o mm o n i t o r i n g ，p r e t r e a t m e n t ，s o c i a ln e t w o r k s ，t e r mw e i g h t , n o i s ef i l t e r v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：高趱 瑚1 年月 e 1 中国科学技术大学硕士学位论文第一章绪论 第一章绪论 网络聊天室作为一种新兴的交流形式，受到了越来越多用户的欢迎网络聊 天室类似于电子邮件，用户通过使用键盘与他人进行实时交漉它为人们交友 提供了一个自由的，开放的虚拟空问，事实上人们可以在聊天室中讨论任何能 够想到的目愿根据统计，判2 0 0 5 年底网络聊天室已经超过了电子邮件成为人 们在网络上进行交流的主要方式 i m ( i m t 珊m 嚣嘲；i n g ) 是一种使人们能在网上识别在线用户并与他们实时交 换消息的技术目前流行的网络聊天室大都是基于h 江技术的【l 】比较成熟的n 订 软件产品有m s nm e 懿a g e r 、y a h o om e s s a g e r 、和m l r c 等最早出现的d 订协议 是琅c ( i 匝c 1 4 5 9 ) ，它是一个非常著名的，长期被许多网络聊天室使用的协议 i r c 是英文i n t e m e tr e l a yc h a t 的缩写，1 9 8 8 年起源于芬兰，已广泛应用于世界 7 0 多个国家基于i r c 的辫天室系统是多用户、多频道的讨论系统，它能同时 负载成千上万的用户交流信息闭在i r c 聊天室系统中，用户可以设置单独的 频道，在这个频道内输出的文字可供所有人都看到，这样能够使来自世界不同 角落的人同时得到有关信息，也可以单独和某人进行秘密交谈，甚至可以不用 逶过服务器，这样能够保证谈话的保密性i r c 聊天室的这些优点为用户交流 提供了极大的方便，因此成为当前最为流行的聊天工具我们的工作选择以琢c 网络聊天室的内容瓶控为背景。对聊天数据的预处理技术进行了深入的研究 1 1 研究背景 与e - i l 、b b s 等网络交流方式相比，使用聊天室聊天用户无需身份认 证几乎可以不受限制的加入已经存在的各种话题的讨论，也可以根据自己的 兴趣建立新的话题进行讨论这种开放性给用户带来方便的同时，也为一些别 有用心的人进行非法活动提供了可乘之机 实际上，从近几年开始，聊天室的这一特点已越来越多地被某些特定群体人 员有意识地使用，借以达到他们的特殊目的：如诱拐儿童和青少年唧，间谍传 递重要的情报l 1 。甚至是策划恐怖行动哪聊天室所带来的负面影响已经显现出 来，其引发的犯罪案件和治安案件正呈逐年上升态势如果不对聊天室进行监 控和管理，它将会对社会造成很大的负面影响甚至破坏作用由于聊天室在我 中国科学技术大学硕士学位论文第一章绪论 国已成为一个主要的网络交互平台，因此，为加强对麓天信息的监控水平，聊 天室监控系统的研究在我国已成为个迫在眉睫的工作 然而，对聊天室进行监控是非常困难的采用人工监控方式单调乏味，费 时费力。成本过高，且不能保证监控结果的稳定性和准确性此外。由于聊天 室具有开放性，实时性、多话题交错等特点，使得目前的自动监控技术也难以 取得令人满意的结果因此，对聊天内容监控系统的研究是非常有意义的，该 系统能够自动监测聊天用户活动，有效的分析聊天数据，并辅助情报人员检测 犯罪行为聊天内容监控技术属于新兴的前沿学科情报与安全信息学 ( i n t e l l i g e n c ea n ds e c u r i t yi n f o r m a t i c s ，i s i ) 的一个子课题。其研 究涉及到数据库、网络、自然语言处理、人工智能、模式识别等多个学科，是 当前多学科交叉的一个研究熟点 ， 设计一个完整的聊天室内容监控系统需要综合研究信息获取、特征提取， 分类机制的设计等多个方面。目前聊天室的内容监控主要针对信息过滤、话题 检测、交流关系发现等问题，采用文本挖掘技术作为主要技术手段不管聊天 室内容监控针对哪个问题，聊天数据的预处理都是对聊天内容监控过程中十分 重要和必要的一步，聊天数据预处理包括分词s t e m m i n g 、噪声过滤、特征表示、 特征选择等部分之所以说聊天数据预处理技术的研究很必要，这是因为： ( 1 )与文本内容相比聊天对话的内容的更加随意；如噪声、词汇简写、 用户经常更换昵称等这些特点使得聊天数据更接近于自然对话 因此，利用常规的文本预处理方法直接处理聊天数据，很难保证效 果 ( 2 )在聊天数据的预处理过程中，需要使用一些新的处理方法，而这些 方法在文本预处理技术是没有的，或者说是涉及不到的，例如本文 后面介绍的推断聊天数据的社会网络，聊天数据中的噪声对话过滤 等这些方法对提高监控系统的准确性、快速性和稳定性起到了很 重要的作用 ( 3 )预处理阶段的必要性还在于预处理是整个监控系统中的基础部分， 通过预处理得到的词汇集市，应该包含能够准确描述聊天数据中话 题的词汇如果词汇集市内容不准确。则通过系统后续部分处理很 难得到正确的结果 2 中国科学技术大学硕士学位论文 第一章绪论 由以上分析可以看出，预处理的效果直接影响后续工作的效率和准确率， 它在监控系统中的作用和重要性是显而易见的因此，我们研究的重点以 聊天数据预处理为主，通过设计噪声过滤方法和聊天数据词汇权值计算方 法提高整个监控系统的工作效率 1 2 国内外研究现状 从国内外目前的研究现状来看，基于话题检测的聊天室内容监控方面的研究 还处于起步阶段典型的工作有zi l i t 的b u t t e r f l y 系统，该系统根据用户提 出的话题描述，找出含有相关话题的聊天频道并推荐给用户 6 1 1f a m a nm e l n a h r a w y 将k n n 、b s y e s 和s v m 三种分类方法用于聊天室的话题检测，并对 三种方法的性能进行了分析比较川：文献【8 1 全面介绍了s o c i a l n e t w o r k 的结构、 组织方式和主要应用；v i l l eh 等人首先提出了使用8 0 c h dn e t w o r k 分析辅助分 类检测的方法，它的主要技术是首先推断出聊天室的社会网络关系，然后利用 该社会网络关系对用户所发布的信息的重要性进行评估，并根据该信息对原始 数据进行扩展，最后使用s v g 分类器对扩展后的数据进行分类检测1 9 1 这些工 作主要是使用文本分类的方法对聊天室内容进行了简单的分类，而没有真正实 现“事件”级的检测 实现“事件”级的聊天室话题检测的工作还较少代表性工作有：t h o m a s k o l e n d a 等人使用独立分量分析法( i c ) 来将混合在一起的聊天话题分离出 来i 1 0 1 ；e l l ab i n g h a m 等提出使用c o m p l e x i t yp u r s u i t 算法进行聊天数据的话题检 测【i 这两个工作使用无监督分析方法实现了“事件”级的话题检测，但是它 们的方法只适用于新闻频道的数据因为真实的聊天室中的频道是多种多样的， 而许多频道讨论的内容并不是针对具体事件的，所以使用无监督的分析方法检 测出的很可能并不是事件相关的话题 目前一个相对比较完整的聊天室监控系是j a s o nb o n g e l 等人设计的 c h a t t r a c k 系统【1 2 1 ，它实现了聊天室数据的自动收集、检索和分类其主要技 术是首先对现有聊天服务器进行修改，使其能够按要求记录聊天日志，然后使 用增量索引技术对聊天数据建立索引以便用户能够对聊天数据进行检索，最后 使用向量比较技术对数据进行分类该系统基本实现了聊天室监控的主要功能， 但并没有对其分类的准确率进行详细的分析，其系统结构如图卜1 该系统也没 有真正实现“事件”级的检测，并且不能对未知的话题进行检测 还有一些相似的工作，如：c l l r i sc l i f t o n 等提出使用传统数据挖掘技术挖掘 中盈科学技术大学磺士学位论文 第一章绪论 数据中的关联规则，然后根据关联规则进行聚类话题检测【嘲；m 嘣i l i 蛐i h a n m m o t o 等对流数据话题检测的三种技术进行了比较研究【堋，这三种技术是l s v d 、c l l 鼬嚣i n g 和i c a ；1 i y r 评测会议中的系统【1 5 1 6 , 1 7 1 但它们都是针对网络 新闻数据源的 圈1 - 1c i t r a c k 系统结构示意圈 a l e xa f i 渊对基于话题检测的文本摘要的研究啪，其主要技术是使 用聚类方法法对语义相关的句子进行聚类，而句子之间的相似度评估是根据两 个句子中名词的距离( 由w o r d n e t 辞典得到) 来计算的。该工作是针对普通文本 进行文本摘要，而且并没有实现。事件”级的话题检测；a t a k a b i n ，x i n w a n g 提出使用隐马尔科夫模型对聊天用户的活动信息( 用户m 的时序数据) 进行分 析，发现隐含的聊天组【l 明：p a u lm u h o n 用构造启发性规则的方法来推断聊天室 中的社会网络关系，并将其可视化网这两个工作虽然是针对聊天室的，但它 们主要针对的是如何发现用户间的交流关系与话题检测相比，得到用户问的 交流关系并不能发现危险信息，只能起到一个辅助分析的作用，对话题检测的 研究才是聊天室内容监控的重点但是用户闻的交流关系是一个非常重要的特 征，不仅可以用来辅助分析，也可以提高话题检测的准确率，所以这两个工作 是十分值得借鉴的 与国外的工作相比，国内尚未发现有针对聊天室监控的工作几个相关的 代表性工作有：刘昌钰等综合潜在语义分析技术和b a y e s 分类技术对b b s 文档 进行分类1 2 1 1 ；于静等使用混合过滤模型对b b s 数据进行过滤，并引入社会网络 技术进行辅助分析圆这几个工作都是针对b b s 数据的，相对于秭天数据而言， b b s 数据中不同话题的数据相互分离的，而且其用户之间的交流关系一目了然， 所以聊天室的内容监控要比b b s 的监控困难的多；陈科等人根据海量汉语短文 中臣科学技术大学顼士学位论文第章绪论 本话题提取系统中多信源、短文篇幅小的特点，结合词汇语义相似性度量，提 出了一个用于汉语短文本的权重算法阐 从监控的最终目标看，只有实现了。事件”级的检滔，才能够了解聊天室 中的舆论倾向，更加有效的辅助分析员对聊天室的安全问题进行全面的监控 所以实现。事件”级的检测是有较高的实际意义的 然而，与新闻报道、b 酷等的检测相比，在聊天室中实现。事件”级的话 愿检测更为困难存在的难点主要有； ( 1 )聊天数据中的话题是相互交错的，多个话题混合在一起影响了话题 检测的准确性 ( 2 ) 聊天室中存在大量的缩写和拼写错误，与事件密切相关的人名、地 点等信息常常出现同义多词的现象 ( 3 )检测率与速度难以同时令人满意，为提高系统的检测率，需要使用 更多的特征信息和更复杂的分类机制；但与此同时，这将大大降低 系统的检测速度，从而使系统无法实时检测，降低其实用价值 ( 4 ) “事件”级的话题检测的特征集与普通文档分类所用的特征集并不 完全相同，所以如何选择出。事件”级的话题检测的最佳特征集是 最为关键的问题 在聊天室内容监控系统的研究工作中，除了上述介绍的系统结构和话题检 测技术外，针对聊天数据的预处理技术的研究也是十分重要和必要的通过研 究我们发现，目前典型的聊天塞监控系统基本上都是采用文本预处理的方法， 聊天数据的预处理研究还没有引起足够的重视。还没有什么工作专门关注于此 典型的监控系统如c h a t t r a c k t l 2 1 和b u t t e r f l 3 4 e l ，都是采用文本分类预处理的方法 建立聊天数据的特征向量空问，利用文本特征权值算法t f * i d f 计算词汇权值： 文献【9 】通过聊天数据的社会网络和话题检测进行聊天数据挖掘，在计算特征权 值时也是通过t f * i d f 方法，实验结果并不理想文献 3 6 1 通过分析短文本的 特点，结合语义分析提出了一种针对中文短文本的特征权值计算方法，提高了 权值表达的准确性，短文本与聊天数据有较高的相似性，对我们的工作有很大 的借鉴意义由以上分析可见预处理研究的重要性和必要性，必须设计专门用 于聊天数据的预处理技术因此，本文将聊天数据的预处理作为我们的选题 ， 中田科学技术大学硬士学位论文第一章绪论 1 3 聊天室监控系统一般结构介绍 目前，聊天室监控系统都是通过对聊天数据进行数据预处理、话题检测、 结果分析等几个基本步骤实现的图1 - 2 概括描述了一个完整的聊天内容监控 系统的一般结构 这里我们介绍一下图l - 2 中各模块的作用：用户界面是向用户提供个可 视化的操作环境用户可以通过该接口检索原始聊天数据，设置过滤规则，察 看数据分析结果等；数据采集模块负责根据用户要求从聊天服务器上获取聊天 数据用户可以设定具体的采集规则，如：采集频道、采集时问、要采集的用 户等。数据库用来存储数据采集模块从聊天服务器上得到的用户对话，以备情 报分析人员进一步审查系统监控结果；数据预处理模块包括对原始聊天数据建 立索引、进行过滤、分词、权重计算、特征选择等，减少数据量，给话题分类 模块提供合适的数据结构；话题分类检测模块实现对聊天数据进行分类、聚类、 话题发现等；分析决策模块将上一模块得到的结果进行优化，形成给情报分析 人员易于理解的结果 田1 2 囊天室内容监控结掬圈 6 中田科学技术大学硕士学位论文第章绪论 从图l - 2 中可以看出系统监控工作主要包含有两个流程： ( 1 )麓天数据收集流程t 首先，聊天数据采集模登录刭c h a t 服务器；然 后数据采集器记录该服务器韵聊天数据；最后将聊天数据存入数据 库 ( 2 )分析监控流程；首先，数据预处理模块对待检测的聊天片断进行预 处理；然后由分类检测模块分析出聊天数据中的话题；最后，分析决 策模块形成分析报告并返回给情报分析员 其中，数据预处理模块是整个系统的基础，其处理结果的好坏直接影响着分 类检测的工作效率分类检测模块是整个系统的关键与难点只有有效的检酒 出聊天数据中的话题，分析决策模块才能形成正确的分析报告，否则将会误导 情报分析员因此，个优秀聊天室内容监控系统，采用高效的数据预处理技 术和话题检测技术是关键 下面我们主要介绍预处理模块和话题检测模块采用常用技术 1 3 1 预处理模块 预处理模块一般包括分词、鼠锄i n i 雌、噪音词、特征表示、特征选择等 其处理流程如图l 一3 所示： 画日国日圆西圜西囝 田1 - 3 预处理的一般流程 在分词，s 1 舶吼i 以前进行一些初始化筛选，可有效降低特征向量维数，主 要方法如下： ( 1 ) 停用词表：将一些在文本中出现频率高但是含义虚泛的词放入停用 词表这些词在不同的语言环境有不同的表示例如在英语中的矗。 a n d ，t h i s ，a t ，i n ，中文中的“的，得，地，这，尽管，但是”等， 保证出现在停用词表中的词不能选作文档特征 ( 2 )稀有词处理：有些词条在整个文档集中出现的频率都很低，它们也 不适合作为文本的特征项通过对文档集进行词条频率统计并设计 中田科学技术大学硕士学位论文第一章绪论 一个词频闷值，只要是词条皴低于这个词频阈值的词就被删除 ( 3 )单词归并；为了提高分类效果，采取单词归并和同义词归并的策略， 把表达形式不f 可而含义相同的或是含义相似的词作为同一个词条处 理。如英文中的f o o t b a l l 和s o c c e r 。中文的“电脑”和“计算机” 等 ( 4 ) 同根词处理：在英文中，还可以进行s t r i ph e a d e r 和咖删啦i 豫的操 作来对文本进行初始化例如：t a l k ，t a l k i n g 和t a l k e d 它们同属于一 个词根t a l k 通过初始化筛选后，需要对处理内容进行分词或咖删n i 雌，对英文而言需 要进行s t e r 锄i n g 处理。在中文的情况则不同，与英文相比较为复杂，因为中文 词与词之间没有固有的间隔符( 空格) ，需要进行分词处理目前主要有基于词 库的分词算法和无词典的分词技术两种 基于词库的分词算法包括正向最大匹配、正向最小匹配、逆向匹配及逐诃 遍历匹配法等1 这类算法的特点是易于实现，设计简单；但分词的正确性很 大程度上取决于所建的词库刚因此，基于词库的分词技术对于歧义和未登录 词的切分具有很大的困难文献【2 5 】在分析了最大匹配法的特点后，提出了一种 改时的算法该算法在允许一定的分词错误率的情况下，能显著提高分词效率， 其速度优予传统的最大匹配法文献 2 6 1 中采用了基于词典的正向逐词遍历匹配 法，取得了较好的效果。 基于无词典的分词技术的基本思想是：基于词频的统计，将原文中任意前 后紧邻的两个字作为一个词进行出现频率的统计，出现的次数越高，成为一个 词的可能性也就越大，在频率超过某个预先设定的阈值时，就将其作为一个词 进行索引这种方法能够有效地提取出未登录词口 2 1 1 文献【2 9 1 设计了一个基 于无词典分词的算法，能比较准确地切分出文本中的新词文献【3 鲫基于层次隐 马尔可夫模型，设计开发了“汉语词法分析系统”，将分词，词语排除歧义、未 登录词的识别三个过程融合到一个相对统一的理论模型中 特征表示 对聊天数据的特征表示方法采用文本挖掘中常用的方法近年来应用较多 的并且效果较好的方法是矢量空间模型( v e c t o rs p a c em o d e l s ) p 1 1 矢量空间模 型由s a l t o ng 等人干6 睥代末提出，它是近些年来所研究的信息检索方法的一 个重要分支由于矢量空间模型是建立在规范的数学模型基础上，所以该模型 在信息捡索领域中的应用最为广泛矢量空间模型用特征项及其相应权值代表 i 中田科学技术大学硕士学位论文第一章绪论 文档信息，其应用前提是一篇文挡的中心涵义能通过其中的词汇信息( 即特征 项) 体现出来 f 句量空间模型表示方法是在文本中提取其特征项组成特征徽量，并以某种 方式为特征项赋权，如：文档d 可表示成占，f 2 ，0 ) ，其中“是特征项，1 k n 由于特征项的重要程度不同，要用附加权重- k 来进行量化，这样文档d 可 以表示为讹，m ；f s 。h ) ，简记为d ( w i ，) ，这里说项 的权 重为雌，l k n 向量空问模型是指给定一个自然语言文档d ；d ( f l ，嘶；r 2 ，嘞；t n ，蛳) 。 在暂不考虑“在文档中的先后顺序并要求f i 互异( 即没有重复) 时，可以把 t l , r 2 。，t x 看成一个n 维的坐标系而m ，吩。，为相应的坐标值，因而 d ( m ，w 2 ，_ i ) 被看成是n 维空问中的一个向量称d ( 嵋，) 为文档d 的向量表示或向量空间模型即，在忽略特征项之间的相关信息后，个文本 就可以用一个特征向量来表示；而一个文本集可以表示成一个矩阵，也就是特 征项空阃中的一些点的集合 向量空间模型中的另一个概念是相似度( s i m i l a r i t y ) ：相似度s i r e ( d , ，d 2 ) 用于度量两个文档d i 和d 2 之间的内容相关程度当文档被表示为文档空间的向 量，就可以利用向量之阃的距离计算公式表示文档问的相似度常用的距离有 向量的内积距离： 。 上 跏( d l 。d 2 ) = + 或余弦距离： s z m ( 1 ) l , z 2 ) = c o s o = 啊。 除了向量空间模型之外，$ t e p h e nr o b e r t s o n 和s p a r kj o n e s 等人提出的概 率模型也得到了人们的广泛认可该模型综合考虑了词频、文档频率和文档长 度等因素，把文档和用户兴趣( 查询) 按照一定的概率关系融合，形成了著名 的o k a p i 公式【4 孔该信息在信息检测领域取得了成功 词汇权值用以刻画词汇在描述文档内容时所起作用的重要程度，是特征提取 的衡量标准词汇权值计算唯一的准则就是要最大限度的区分不阿文档所以 针对词汇权值计算，必须具备以下三个特征参考： 9 中田科学技术大学硕士学位论文第章绪论 ( 1 ) 完全性；特征词能够确实表示目标内容 ( 2 ) 区分性：根据特征向量。能将目标同其他的文本相区分 ( 3 )精练性：特征向量的维数应该尽可能的小 目前常用的针对静态文本的词祀权值计算函数主要有以下四种； 布尔豳数f 。 1 斫1 、0 斫= 0 平方根函数，。玩 对数函数= i o g ( 斫+ 1 ) t f i d f 函数，= 莎l 呶) 【3 2 】 ，t 其中矾为词汇f 的频率的函数，为总的文档数，m 台有词汇i 的文档数 由以上常用的权值计算方法可以看出，特征权值算法一般由频率因子、文档 集因子和规格化医子兰分部组成 ( 1 )在文档中频繁出现的特征项有较高的权童，因此检索系统常使用频 率因子t f ( t e r mf r e q u e n c y ) 进行特征项赋权，使用高频特征项进 行查询可以提高的查全率 ( 2 )权使用频率因子并不能保证系统的查询性能，提高查全率时会影响 检索系统的查准率因此需要弓i 入一个与文档集合有关的因子。加 大文档之间的区分度如果特征项在集合中较少的文档中出现，则 相应的文档集因子i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 较大在文 档总数为n 的集中。如果包含某特项的文档数为i i ，则文档因子是 t o y = l o g ( n 吣较好的查询表达式通常包含能够将一些特定文档 与文档集合中其它文档区别开来的特征项，这种特征项不仅要有较 高的出现频率，还要在文档集合中较少的文档中出现将频率因子 和文档集因子相乘就可以实现此目的，这就是文本检索最常用的 t f i d f 方法 ( 3 )当文档较长，查询式与文档进行匹配的可能性更大，所以长文档比 短文档更有可能被提取出来，因此引入规则化因子来消除文档长度 l o 中田科学技术大学硕士学位论文第一章绪论 对匹配结果的影响假定w 代表特征权值，最后的规格化因子定义 为： 文献t 3 3 1 通过分析索引词应具备的三点特征，提出一种文本索引词项相对权 值计算方法，该方法取得了较好的效果文献f 3 4 】通过引入信息论中信息增益的 概念，提出一种对t f * i d f 的改进方法t f * i d f * i g 方法该方法将词的信息增 益作为词汇权值表示的一个因子，来衡量词在文本集合中分布比例在量上的差 异文献1 3 5 j 提出了一种新的权值计算方法1 1 p p d f 方法，并得用该方法来提 取短周期内新闻集合中的热点信息文献【3 6 】中面向海量汉语短文话题提取系统 中多信源、文章篇幅较小的特点，结合词汇语义相似度量，在t f * p d f 方法的 基础提出了一种词汇权重计算法s u r f * p d f 特征选择 。 文档特征向量的维数非常的大，如此高维的特征对将进行的分类学习未必 是有益的，而且高维的特征可能会大大增加机器的学习时问，而学习分类结果仅 与小得多的特征子集训练出的分类器相近，所以必须对特征集进行缩减特征 选择就是指按照挖掘目标选取有用的特征，得到代表文档集合地有效的、精简的 特征子集 特征项选择有几个原则：一是应当选取包含语义信息较多，对文本的表示 能力较强的语言单位作为特征项；二是文本在这些特征项上的分布应当有较为 明显的统计规律性这些将适用于信息检索、文档分类等应用系统；三是特征 选取过程应该容易实现，时间和空间复杂度都不太大实际应用中常常采用字、 词或词组作为特征项 一特征项的选择依赖于频度、分散度和集中度等多项测试指标频度是最常 用的特征选择测试指标，该方法认为在某类文本中出现次数越多的特征项越 能代表这类文本；集中度指标认为，一个有标引价值的特征项，应该集中出现在 莱一类文本中而不是均匀地分布在各类文本中；分散度指标认为，在某类文本 中均匀出现的特征项对该类文本应具有较高的标引价值，若只集中出现在该类 的个别文本中，而在该类别的其他文本中很少出现，则该词的标引价值相对就要 小多了显然对于某一特征项，其频度越高、分散度越大、集中度越强，则对文 本分类越有用，即分辨度越强常用的评估方法有以下几种： 或 素 中田科学技来大学硕士学位论文 第一章绪论 ( 1 ) 文档频数( d o c u m e n tf r e q u e n c yt h r e s h o l 词频是指词条出现的文本数目，这种方法是计算训练集中每个词的词差更 并排除那些词频数小于预先规定好的阈值的词 ( 2 ) 信息增益( i n f o r m a t i o ng a i n ) 令c l ，c 2 , ，c k 表示可能的分类，对特征项的i g 函数为： ，g m ；芝尸妈) i o 妒的) + 足 皂喇，叻l 。g 喇，田+ 反粕动l 。妒蚵，动 这里p ( c i ) 为第j 类值的出现频率，p ( w ) 为诃- 的出现频率，p ( c i ，w ) 为 词，出现时文档属于c ；类的条件概率，计算每个词的信息增益，捧除其 小于预先给定值的词 ( 3 )互信息( m u t 崛li n f o r m a t i o n ) 词条和类别的互信息体现了词条与类别的相关程度，是一种广泛用于 建立词关联统计模型的标准在某个类别c ；中出现的概率高，而在其它类 别中出现的概率低的特征项将获得较高的互信息，也就有可能被选取为类 别的c 。的特征 施m 粪婀) 崦掣 ( 4 )x2 统i t c h l c a n ( r ) ；子p k 、f f 。一；p 弛、 型终生二生生r 2 ；p 呜) f 以勺) 2 丢p 呜历了i 西羞置竞孝乞；页而 一 一、，】1 1 1 一一1 一t 1 1 、1 ， 其中4 表示特征项，在q 中出现的频度，五表示- 在除q 以外的其它 类别中出现的频度，以表示除- 以外的其它词在c t 中出现的频度，以表示 除- 外的其它词在除a 以外的其它类别中出现的频度该方法类似于互信 息词条的x ( c h i ) 统计值比较了词条对一个类别的贡献和对其余类别的 贡献。以及词条和其它词条对分类的影响当- 与q 互相独立时。 4 4 一彳：以= o ，好( c h i 的值为o ；若属4 一鸽五 0 ，说明，与q 正 相关，即词条出现说明某个类别也可能出现；反之，若a i 广 。 。 0 的- 作为特征值 ( 5 ) 期望交叉熵( e x p e c t e dc r o s se n t r o 曲y ) 中田辩学技术大学硕士学位论文 第一章绪论 c 联叻= p ( 叻妻鹏i 叻l o g 号笔学 j 一 、y jj 期望交叉熵没有考虑单词未出现的情况如果词条和类别强相关， p bi 忉就大，若，瓴) 又很小的话，则说明该词条对分类的影响大此时 相应的函数值就大，就有可能被选中作为特征值交叉熵反映了文本类别 的概率分布和出现了莱种特定词的条件下文本类别的概率分布之间的距 膏词条的交叉熵越大。对文本类别分布的影响也筑越大 ( 6 )文本证据权( w e i g ho fe v i d e n c ef o rt e x t ) w e t ( w ) = p ( r ) 枷g - 川 l 其中p ( c 1 ) 表示第j 类文档在文档集合中出现的概率，以忉表示词- 出现 的概率，户( c li 忉表示出现词- 的情况下，文档属于第j 类的概率 在文献【4 6 通过结合考虑频度、分散度和集中度等几项测试指标，提出了 一种新的特征选择方法，避免了从单一的澍试指标进行特征选择所造成的“过 度拟合”闯题；文献【4 7 】提出一种结合类别文本量占整个文本集的比率的改进 型互信息特征选择方法。取得了较好的效果；文献【铝】介绍一种基于文本集密 度的特征选择的方法，该方法有效的提高了词语的文本区分度。使索引词的权 值更有效，但其缺点是增加了处理时间 1 3 2 话题分类检测模块 话题分类检测模块采用文本分类和聚类方法实现对聊天话题的检测目前 常用的文本分类和聚类方法都可以用于聊天数据的话题检测 文本分类的常用方法 文档分类的算法主要有r o c c h i o 法、决策树法、贝叶斯方法( b n ) 、k 近邻 分类法( k ) 、神经网络法、支持向量机( s v l o 和投票法等 ( 1 ) r o c c h i o 法( 即质心法) r o c c h i o 法是情报检索领域最经典的算法在算法中，首先为每一个类c 建立一个原型向量( 即训练集中c 类的所有样本的平均向量) 然后通过计 算各文档向量d 与每一个原型向量的相似度，将文档d 归入相似度最高的类 这种方法的优点是简单、学习速度快 中国科学技术大学硕士学位论文 第一章绪论 c 2 ) 决策树分类法 决策树是一种常用数据分类技术，它捧除嗓音的强壮性以及学习反义 表达的能力，使其更适合于文本分类其基本思想是构造个树结构。其中 每个内部节点表示在一个属性上的测试，每个分支表示个澍试输出，而每 个叶节点表示分类结果决策树的建立算法有多种，其中包括：基于信息增 益的启发式算法i d 3s 基于信息增益率的解决连续属性分类的算法“5 1 基 于- 6 i n i 系数的算法c a 盯；针对大样本集的可伸缩算法s l i m 可并行化算法 s p i i i 町；将建树和剪枝集成到一起的算法p b u l i c ( 3 )朴素贝叶斯分类 朴素贝叶斯分类的基本思想是利用类别的先验概率和词的分布来计算 未知文本属于某一类别的概率( 即贝叶斯公式) p ( c ii o ) = j 。( c