面向短消息的文本聚类研究

面向短消息的文本聚类研究 学校代号: 学 号: 密 级: 普通 湖南大学硕士学位 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 面向短消息的文本聚类研究吣 川 四 眦 哪 心 肌 .. 、 勉 . ,究所取 任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名: 芸雾 日期:排月勰日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 、保密口,在 年解密后适用本授权书。 、不保密囹。 请在以上相应方框内打“?” 作者签名: 日期:扣『,年 夕月甥日 关爹/ 日期如/年 夕月泓日 // 、\,\ 导师签名:.多绷 山卜唧颈:学位论文 摘要 在网络信息时代,随着通信技术的不断发展,即时通信得到了广泛应用,产 生了巨大的短消息数据,短消息数据中蕴藏了大量有用信息资源,如何对短 消息 数据进行采集、存储、分析和挖掘,对于信息管理和信息检索等具有重要意 义。 短消息具有动态性、错综复杂性、非规范性、大规模性等特点,这些给数据 挖掘带来极大挑战。本文以短消息挖掘为背景,研究短消息聚类相关技术,涉及 短消息预处理、合成会话、相似性度量以及聚类算法的研究,其中重点对相似性 度量和聚类算法进行了研究,并试图提高聚类准确性和聚类算法的可伸缩性,为 聚类输出提供实际应用。研究的主要内容如下: 首先提出了短消息文本聚类场景系统。‘聚类系统包括数据接收采集、归档消 息数据库、聚类节点、输出节点四部分。本文描述了聚类场景系统的结构体系, 分析各个部分的功能,其中重点研究了接收采集部分需要处理的问题:如何采集, 能否按时间段划分消息记录,如何合成会话等。该系统的提出为本文展开短消息 聚类相关技术研究提供了基础。 接着提出了基于语义的短文本相似性度量方法。本文的相似性度量方法基于 词法分类器,通过计算词语的语义距离,得到词语相似度,并可 结合特征词权重一起计算文本相似度。该方法能够解决短文本的关键词稀疏带来 的相似度偏离问题。 针对短消息的文本聚类算法,本文提出了基于频繁词集和.的混合聚 类方法。基于频繁词集的文本聚类算法执行效率很高,且可以适应高维的 大规模数据。.算法得到的聚簇更接近于数据的真实分类,且算法基于树 结构,执行效率较高。基于频繁词集和.的混合聚类方法,利用基于频繁 词集聚类算法处理文本数据的效率优势,生成初始聚簇;计算轮廓系数来消 除初 始聚簇中的重叠,在此基础上再通过.算法继续精化,最终得到高质量的 结果输出。而且聚类结果保留了树状层级结构,为应用提供了更丰富的信息。 最后设计了应用于聊天软件中的短消息文本挖掘系统,介绍了该系统的总体 结构,阐述了各单元的功能结构与设计实现。 关键词:短消息,语义,短文本相似度,文本聚类,频繁词集,., , .. ,, ,, . , , , , . , : .,“ , , ,,:, , . ., , , 。 . . , 。 . ‘ , 曲 ., . 硕:学位论文 , , . ?. .. , .. , .: , , “, , ,? ?面向矩消息的文本聚类研究 目 录 学位论文原创性声明和学位论文版权使用授权书? 摘要插图索引?. 附表索引 第章绪论?. .研究背景和意义.研究的主要问题和挑战?. .本文的研究内容.本文的组织结构??一 第章文本模型及聚类方法分析?.. .文本表示模型 ..布尔模型..向量空间模型? ..概率模型?.. ..其他模型??. .相似度计算方法 ..基于向量空间模型的.方法. ..潜在语义标引法??. ..基于汉明距离的文本相似度计算方法..基于语义理解的文本相似度计算 方法.主要聚类算法..划分的方法?. ..层次的方法? ..基于密度的方法 ..基于网格的方法?:. ..基于模型的方法?.. ..后缀树聚类算法??.. .本章小结?.. 第章短消息会话场景聚类系统设计.常规文本聚类过程 .短消息文本特性分析硕一:学位论文 ..会话交错性特征?.. ..文本稀疏性特征. ..大规模特征.. .短消息聚类系统设计.会话抽取技术??一 .本章小结?. 第章短文本相似度计算??.. .相关问题及技术分析 ..相关问题?. ..相关技术?一 .基于词法分类器度量词间关系..《知网》简介 ..义原相似度计算..概念相似度计算?一 ..词语相似度计算.短文本相似性度量算法? .实验??“ .本章小结及改进设想第章短文本聚类算法洲 .基于频繁词集的聚类算法 . .算法??. .基于频繁词集和.的混合聚类算法 ..构建初始聚簇. ..轮廓系数.. 算法?. .实验? ..实验设置.. 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 指标 ..实验结果及分析??. .本章小结??一 第章短消息文本聚类系统应用设计?一 .系统结构?. .各功能单元结构分析??. ..数据访问单元??一 ..文本预处理单元?~ 面向知肖息的文本聚类研究 ..相似性度量单元?.. ..会话合成单元??.. ..聚类单元..检索单元? .本章小结 总结?.. 参考文献. 附录攻读硕士学位期间所发表的学术论文?.. 致 谢. 硕:学位论文 插图索引 图. 年~ 年中国网民与即时通讯用户规模发展趋势图. ~年中国手机即时通讯用 户规模??. 图.基于的文本聚类过程? 图.一般文本聚类过程示意图? 图. 群中的一段消息?一 图.短消息会话聚类系统结构图 图.短消息流和会话示意图??. 图.树状义原层次结构一 图. .算法 次迭代的值图. 主算法结构图. 图.蚂蚁的自聚集行为形成的树结构?. 图.蚂蚁在瞄移动时的邻域状态??. 图.形成的聚类树结构图 图.使用最大频繁词集得到初始划分??一 图.使用.频繁词集得到初始划分. 图. 混合聚类算法图.数据库文档表结构. 图.不同值时聚类结果的平均值?. 图.短文本挖掘系统总体结构?. 图.数据访问单元功能结构??. 图.聚类单元功能结构??. 图.检索单元功能结构??. 面向如消息的义奉聚类研究 附表索引 表.使用.度量短消息文本的相似度表.《知网》中义原分类关系? 表.两种相似度计算的.聚类质量比较 表. 和.算法平均值比较?. 硕上学位论文 第章绪论 .研究背景和意义 随着网络通信技术不断发展,网络文本资源在不断增长和充实,面对海量的 信息资源,要从中获取有价值的信息资源,仅仅使用人工判断己完全不能胜任, 必须借助于机器进行文本挖掘,才能找到对自己有用的信息。 文本挖掘是数据挖掘的重要研究方向。文本挖掘可通过文本分类和聚类进行, 分类需要事先确定分类目录,但互联网信息是动态变化的,难以用现有的分类模 型来刻画主题。这时无监督的文本聚类就显得很重要。文本聚类是文本挖掘重要 的手段之一,也是当前研究的热点。目前,国内对中文文本聚类的研究主要包括 利用概率统计的方法、基于训练学习的方法来生成概念空间,或通过自定义模糊 概念图描述概念空间、采用潜在语义分析技术 、聚类技术的融合等方面。随着 文本聚类理论的研究和发展,实际应用将更广泛,处理对象也在不断扩大。文本 聚类是挖掘信息资源的一种有效手段,能够判断文本的相似性从而划分成不同类 别,而且是一种无监督的机器学习方法,能够进行自动化处理。 人们在互联网的通信活动中,产生了大量的短文本信息资源,包括论坛, 新闻组,,微博,即时通信软件产生的聊天信息。其中,微博、即时通信已 经成为一种比较流行的通讯方式。短文本信息与我们生活密切相关,蕴藏着大量 有价值的信息资源,使用聚类技术对这些短文本信息进行分析和组织,能够发掘 有用信息,对信息进行有效管理,提供各种服务,给我们生产生活带来便利。 即时通讯方式便利实用,受到了人们的欢迎,被广泛应用于日常生活、办公 和企业商务中。随着即时通讯产业近年的发展,即时通讯软件不断涌现,用户 规模不断增大。据艾瑞咨询《.年中国即时通讯行业发展报告》公布的 数据,年中国即时通讯用户规模已达.亿人,在整个互联网网民中占比 .%。年,即时通讯用户规模将达到.亿人,届时在全体网民中的占比 将升至.%。另外年中国移动即时通讯用户规模也达到.亿人,同比 增长.%,保持飞速增长态势。如图.、图.所示。 网民通过、阿里旺旺、 、和等通信工具进行交 流,产生了海量的短消息数据,存储量已经非常巨大,而且数据每日都在不断 增 长。据腾讯公司致信感谢广大网友《同时在线过亿》,作为中国第一个即 时通信软件,在中国即时通讯市场份额上一直稳居第一。可想而知,同时在线 过 亿的用户每日产生的数据量是相当可观的。 描?猫 煳 。 ? 忽盔盟中落网曼鼓量亿人匕中罾鄹通甩户数量亿人 昂通用户蝠长率% 弱是培长率% 图. 年~年中国网民与即时通讯用户规模发展趋势【】 弱 ? ? ? ,舶 ,? ; ? ? 刃 猢硒 四 田? 圆手机鄹时通讯用户规模“孀长率% 注:手机鄹时通讯用户篾摸是指一年闪每个季赛至少爱甩过?次手钒即对通讯魄用户人数. 图. ~年中国手机即时通讯用户规模‘】 通过以上分析可以看出,从全球到中国,即时通信已经得到了广泛的普及和 应用。 等即时通信工具使用广泛,同事、朋友、亲戚之间都在使用它,用户可以 以对话方式进行交流、沟通,方便、快捷,交互性强。而且用户交互越紧密,消 息文本越短小。通过这种高交互性的活动产生了大量用语不规范、长度短小的文 硕士学位论文 本,在此称为短消息文本。相比电子邮件与新闻组,它交互性更强,长度更短。 除了传递交流信息外,短消息还携带了一些个人信息,蕴藏着较大价值的用户信 息。对于此类数据对象的分析和挖掘需求亦凸现出来。对此类信息挖掘应用较广, 主要有以下一些方面: 、社会舆情发现。随着社会民主的需要,人民地位的提高,人民参与政治的 热情在增加。同时随着互联网技术的普及,人们通过网络表达观点、看法的积极 性不断增强,即时通信等网络通信和传播工具在人们参政议政方面扮演着重要角 色。作为公众领导者和决策者,在制定新政策或政策实施后,必须要了解社会的 舆论情况,才能正确把握实际情况,反映人们的意愿。而许多公众的个人看法往 往只通过微博、聊天工具等来表达。因此,对短消息传播的内容进行聚类研究, 发现社会焦点话题,了解民情民意,将为决策者提供决策支持。而且通过这些通 信传播工具,为大众舆论监督提供了一种新途径。 、信息的有效管理。为专门的政府机构、事业单位和社会团体设立通信组、 聊天群,用于内部文件精神的传达、会议通知的发布、个人信息的交互。但目前 的即时通信工具对消息基本不能完好保存,更缺乏有效管理的途径,不会对消息 记录区分重要程度,更不会将只言片语的短消息合成一段有意义的会话。通过聚 类技术,实现对信息的有效管理,维护消息记录间的次序关系,分类存储重要信 息,发掘和呈送有价值的信息。譬如,教师在教学过程中,就可以针对某门课程 建立聊天组,要求学生相互交流、讨论,教师可以并查看消息记录发现学生关心 的问题和存在的疑惑,提供实时指导和在线答疑,对消息记录进行系统的归类存 档,并可整理出教辅材料,对改进教学方法、充实教学资料大有裨益。 、改善和优化企业产品服务。随着电子商务发展,很早就有企业在自己网站 中创建了网上客服系统,据相关统计,即时通信工具将成为企业进行电 子贸易活动的首选工具,大有取代电子邮件的趋势。现在的企业越来越重视建立 自己的客服系统,包括在线咨询、售后维修服务等系统。譬如,联想 公司的网上客服系统就比较完善。有在线互动咨询、联想机器人、联想问吧、电 脑故障报修等方面的服务,而在线互动咨询实时交互性强,是解决用户问题的最 主要途径,为企业售前咨询和售后服务提供了保障。通过对在线咨询服务系统中 的对话记录进行组织分析,可以发现用户的需求,发现产品的缺陷,同时通过聚 类挖掘技术,可有效组织问答记录,建立较完善的用户帮助手册,为改善和优化 企业产品服务提供持续保障,也是企业竞争的重要机制。 、不良信息的过滤和屏蔽。手机垃圾信息的问题日益突出,据《 年手 机短信息状况调查报告第二次》统计,用户平均每周收到垃圾短信息. 条,用户平均每月在垃圾短信息拦截产品的预算费用为.元,.%的用户认 为垃圾短信息产生的原因是运营商从中获得利益,相对应,.%的用户认为运面向短消息的文本聚类研究 营商应该承担主要 责任 安全质量包保责任状安全管理目标责任状8安全事故责任追究制幼儿园安全责任状占有损害赔偿请求权 。另外,的复杂性使得网上垃圾信息不断增多,一 些聊天室充斥着大量广告信息、色情信息。如何解决垃圾信息、屏蔽不良信息, 将是电信运营商、聊天网站运营商要解决的重要问题。运营商可利用文本聚类技 术,分析垃圾信息特征词,对垃圾信息进行屏蔽,避免传播。同时,可使用监控 技术,对经常发布有害信息的聊天室进行关闭。这将对整治网络环境、预防违法 犯罪行为提供有力手段。 、相似用户发现。通过对聊天消息记录进行聚类分析,用于发现与某一用户 性情相近、兴趣相似的用户,发现与该用户接触最紧密、通信频繁的用户。通过 聚类技术,不但可以提取出用户的性情、兴趣,还可以找到与其关系最紧密地一 类用户。这一技术可以应用到侦查方面。当要搜查出与某一犯罪分子有关的人物 时,就可从他的即时通信记录方面着手,进行深入发掘。 、提供搜索引擎数据源。通过采集短消息记录得到的大量文本信息,可作为 数据源提供搜索引擎对象使用。并可对搜索引擎返回的结果进行聚类,使用户迅 速定位到所需要的信息。 综上可见,短消息通信已经在人民的生产和生活中得到广泛使用,短消息中 携带了大量有价值的信息资源,这些信息可以帮助人们更好地组织和管理生产、 改善生活质量。企业对消息数据进行分析和管理,挖掘有用信息,提高产品质量, 改善售后服务,提升企业竞争力,赢取更大市场;政府和组织攫取具有共性的、 重复突出的有用信息,可以了解人们关注的问题,不断提高服务质量。 通过聚类技术对通信中产生的消息记录采集、存储、分析、生成聚簇类别, 再进行有效管理、组织,可以胜任上述各种实际应用需求。 .研究的主要问题和挑战 短消息蕴藏巨大的信息资源,很有必要进行挖掘。传统的常规文本如纯文本、 静态网页文本,书写规范,内容较多,具有较强的逻辑性。与常规文本不同,短 消息文本具有动态性、错综复杂性、非规范性等特点,下面分别进行阐述: 、动态性。聊天是一个实时动态的过程,当然也有离线的消息在服务器中存 储转发。单个用户产生的数据量可能比较少,但从整体在线的来看,将会动态 产 生大规模的消息文本,尽管并不是所有信息都是有意义或有用的。如何有效接受 和处理动态数据、采集会话消息并归档将成为聚类技术的一个关键点。 、大规模特征。当前使用即时通讯软件的用户越来越多,大有替代电子邮件 的趋势。譬如据腾讯官方发布目前注册用户达到了亿以上,同时在线用户 达到了一亿。、群通信所产生的消息记录应该是海量的,况且,其它即时 通讯工具还很多,它们所产生的数据量规模之大就可想而知了。如何对这些大规 模的数据进行存储将面临新的挑战。 硕:学位论文 、不完整性。聊天过程中的消息记录可能是一些只言片语,仅看一条消息, 可能毫无意义,而且它们书写很不规范,消息中可能央杂着大量错别字、拼音、 符号、表情。如果脱离聊天会话的上下环境,将不知所言,反映不出会话的主题 内容。 、错综复杂性。网页和电子邮件文本具有很好的条理性,论坛数据也具有一 定的组织线索。但是一段聊天会话,却没有明显的条理或次序。聊天室中的一段 会话可能包含不同入围绕不同的主题展开的对话,这些聊天记录错杂在一起,前 几条记录可能与后一条记录毫无关系,一个人可能针对不同的话题都发表了看法, 各种会话难以直观辨认,从而使得一段聊天会话的关系变得很复杂。 当前,文本挖掘特别是文本聚类技术已经比较成熟,研究成果颇多,近几年 来提出了不少新算法,取得了不少新进展。在分析了短消息文本的特征后,可以 有针对性将这些聚类技术引入并加以改进,设计出适合短消息文本特征的聚类方 法,充分挖掘短消息中的信息资源,进行实际应用并为用户带来便利。最近,针 对短消息文本,已经有一些研究者提出了新的算法,文献】提出基于语义概念的 海量短信文本聚类,文献【】提出了基于频繁词集的海量短语信息文本聚类算法, 文献【】提出了将汉字转化为拼音串的变异短文本的快速聚类算法。不过大部分是 在已有文本聚类算法基础上,提出一些改进方法。主要集中在会话抽取技术、特 征提取技术、基于语义的相似度计算等方面的研究。 由于大规模短消息数据具有交互性、动态性和非正规性等特征,现有的文本 聚类技术面临多方面挑战,并不能完全照搬应用于短消息聚类,还需要进一步研 究和改进,使其能够真正处理好动态性、大规模性、交错性等问题。本文也是针 对这些问题展开研究的。 对于短消息文本的处理离不开现有的聚类技术,但又不能照搬,必须符合短 消息文本的特征,设计出符合自身规律的体系结构,使用聚类方法充分挖掘短消 息中所蕴含的有用信息。 相对于传统文本,短消息文本在聚类方面面对的主要挑战如下。 第一,针对短消息的动态性、交互性等特征如何采集归档成会话文本。由前 面特征分析可知,短消息动态产生,具有错综复杂性,一次会话包含若干条消息 记录,各种会话杂糅在一起,会话之间没有明显的特征和线索。所以,要提取会 话,需要发现和分析短消息记录的自身规律,综合考虑时间顺序、语义内容等方 面的特点进行。抽取成会话后,可以更方便地为文本相似度计算、聚类等进一步 处理提供便利。 第二,对于变异短文本的处理问题。短消息文本语法很不规范,关键词稀疏。 由于即时通信在较短时间内进行交流,交互性强,口语多,俗语多,拼音输入容 易导致错误同音字,以及汉语表达的多样性和复杂性,文字表达极不规范。可 能 面向短消息的文奉聚类研究 会有很多错别字、拼音,如“恰饭”表示“吃饭”,“’’表示“你好”;可能 会有不少特殊符号,如“”可能不是数字含义,而表示“我爱你”的谐音,“” 表示“牛逼意思;也可能会有不少表情,如“,,表示笑脸的含义,等等。 这些不正规的表达给文本相似度计算带来了挑战,传统的.等相似性度量 方法已经不能胜任。 第三,如何解决短消息文本的大规模性问题。当前即时通信工具应用广泛, 信息、阿里旺旺信息、聊天室信息、在线咨询信息、微博信息、手机短信息 等等,各种通信工具应用到了各行各业,相应快速产生了大量的动态消息序列, 所积累的数据集将是空前的、大规模的,对它们进行处理,将消息记录合成会话, 将会话文本输出聚簇,既要解决准确性问题,又要解决时间性问题。因此,如何 对大规模的短文本集进行聚类,使其具有较好的质量,同时具有较高的效率,是 需要解决的核心问题。 当然,针对短消息文本挖掘,在应用方面肯定还存在一些具体的问题。但毕 竟同样是文本,本质并没有改变。因此可以在现有文本聚类技术基础上设计合理 的处理技术和聚类方法。基于上述要求,本课题主要设计适合短消息特点的 文本 聚类模型,改进现有的文本相似度计算方法,设计合适的文本聚类算法。这些工 作将有利于丰富文本聚类算法理论,有利于促进数据挖掘等学科的发展。一旦被 加以开发实际利用,对于社会舆论调查、企业改善服务、机构管理信息等方面具 有重要意义。且作为一种新的检索资源,通过聚类结果能为普通用户带来实实在 在的好处。 .本文的研究内容 本文利用已有文本聚类的研究成果,针对短消息文本的特征进行分析研究, 并进行合理的改进,提出短消息文本聚类模型,改进相似度计算,设计适合短消 息特征的聚类算法。力求该聚类系统能够在可伸缩性、聚类结果准确度方面有一 定突破。当前的文本数据规模正在从级跃升为级甚至级,而且数据 是动态增加的。要提高聚类系统的可伸缩性,使其满足短消息文本的数据规模。 而且用户要求挖掘算法的运行时间必须是可预计的和可接受的。传统的数据结构, 如向量空间模型,在随着数据规模的增大也变得复杂和难以处理。如何改进 是首 要研究的问题。另外,较高的准确度是各种文本聚类算法追求的目标,虽然有些 文本挖掘算法达到了比较高的准确度,但可能由于实验数据规模很小且经过了精 细的预处理。总之,现有技术在精度上和效率上不尽人满意,所以如何提高准确 度和降低运行时间都是需要深入考虑的问题。 本文研究内容主要分为四方面,其中主要集中在聚类节点部分的研究。这四 个方面的主要内容如下。 硕:学位论文 、提出短消息文本聚类场景系统。整个聚类系统由数据接收采集、归档消息 数据库、聚类节点、输出节点四部分组成。各部分有机统一,共同实现短消息文 本的处理。采集节点对实时动态产生的短消息流进行接收、处理,处理包括分词、 提取特征词、合成会话等,并将处理的数据保存到归档消息数据库;聚类节点利 用文本聚类技术,调用相似度计算方法,得到内容相关的聚簇;输出节点控制输 出,实现具体的应用。通过提出该场景系统模型,描述系统的结构和过程,分析 各个部分的功能。另外,本部分主要提出接收采集部分需要处理的问题:如何采 集,能否按时间段划分消息记录,如何合成会话,如何进行会话抽取等。对于接 收采集部分技术方面的研究不是本文的重点,在此只侧重于提出问题和分析问题。 、短文本表示和相似性度量方法。短消息会话间的文本相似度计算是短消息 聚类中的一个重要操作,是聚类算法提高准确度的关键。然而,短消息会话是一 种不规范的短文本,使得处理后提取的关键词较少;另一方面,短消息数据的大 规模性使得处理时受到高维瓶颈制约。这些矛盾使得传统的文本相似性度量方法 失效。因此,设计合适的度量方法显得尤为重要,决定了聚类的准确度问题。本 文在基于模型基础上,研究改进文本相似度的计算方法,设计基于语义的 中文短消息文本相似度计算。 、设计针对短消息的文本聚类算法,提出基于频繁词集和.【的混合 聚类方法。本算法基于频繁词集并对.聚类算法改进设计得到的。 .算法是基于蚂蚁自我聚集行为的聚类算法,该算法得到的聚簇更接 近于数据的真实分类,且算法基于树结构,执行效率较高。但是算法的初始化很 重要,它影响整个算法的质量。 一些文本聚类算法对于小规模的数据处理效率可能很高,但对于大规模的短 消息数据集,会受到高维瓶颈制约,不能在有限的时间内得到聚类结果,更满足 不了实时性要求。基于频繁词集的文本聚类算法具有很高的处理效率。该方法选 择包含某一频繁出现的词语集的文档生成簇集,由于数据库查询语句的快捷性, 即使数据规模很大,也能高效地将它们归到相应划分,形成初始聚簇。但该方法 存在这样的问题,一篇文档可能被划分到多个聚簇中,因此如何消除重叠的文档 显得很重要。本文使用轮廓系数来消重,以期获得较高的聚类质量。 基于频繁词集和.的混合聚类方法,利用基于频繁词集聚类算法处理 文本数据的效率优势,生成初始聚簇;计算轮廓系数来消除初始聚簇中的重叠, 并利用.算法的优势,在去重基础上再通过.算法继续精化,最终 得到高质量的结果输出。这也是本文的研究重点和主要创新。 、将本文提出的聚类模型以及算法应用于聊天软件中,建立原型系统, 设计系统如何进行提取舆情信息,阐述主要结构与意义。 面向知消息的文本聚类研究 .本文的组织结构 本文的结构如下: 第一章介绍了面向短消息文本聚类研究的背景意义、主要问题和研究内容, 并给出了论文的结构安排。 第二章系统地介绍了文本模型、相似度计算方法、聚类方法及其应用,着重 介绍文本表示模型和基于模型的文本聚类算法与方法,分析了基于 模型的文本聚类方法中存在的问题和相似度计算在短消息文本聚类中存在 的不足。 第三章提出短消息文本聚类场景系统。分析聚类系统各部分的功能,另外重 点分析了短消息的采集、会话合成的过程和方法。 第四章主要分析和研究短文本表示和相似性度量方法。提出基于语义的中文 短消息文本相似度计算方法。 第五章针对短文本大规模性特点,提出基于频繁词集和.【】的混合聚 类方法。该方法利用频繁词集获得初始聚簇,并利用.得到精化结 果。 第六章使用本文提的聚类方法对等及时聊天软件中的短消息文本聚类系 统进行设计,分析系统结构及意义。 最后是对本文的总结及对今后工作的展望。 硕士学位:文 第章文本模型及聚类方法分析 文本聚类将一个文档集分成若干称为集簇的子集,聚类没有预先定义好主题 类别标记,需要由聚类学习算法来自动确定。它主要是依据著名的聚类假设: 同 类的文档相似度较大,而不同类的文档相似度较小。作为一种无监督的机器学习 方法,聚类由于不需要训练过程,以及不需要预先对文档手工标注类别,因此具 有一定的灵活性和较高的自动化处理能力,已经成为对文本信息进行有效地组织、 。 摘要和导航的重要手段,为越来越多的研究人员所关注【 文本聚类的实现需要建立文本模型,将文本转化为相应数据格式。文本模型 首先要反映数据的语义关系,并在此基础上建立文本相似度计算方法,最后通过 文本聚类方法生成聚簇,实现具体应用。下面分别对文本模型、相似度计算方法、 聚类方法进行分析。 .文本表示模型 目前常用的文本表示模型主要有布尔模型、向量空间模型和概率模型。其中, 向量空间模型表示方法由于效率和效果较佳,成为广泛使用的方法。 ..布尔模型 布尔模型是基于集合论和布尔代数的一种简单检索模型【,该模型提供了一 个信息检索系统用户容易掌握的框架。该模型通过布尔值标识文本,检索条件与 文档判断一致返回真,否则返回假。 该方法虽然简单,但存在着许多不足。其仅考虑文本中是否出现特征词,不 管语义是否相关,也不考虑词语表达方式的不同。它的检索策略是基于二元判定 标准,缺乏文档分级的概念,限制了检索功能。虽然布尔表达式具有精 确的语义,但常常很难将用户的信息需求转换为布尔表达式,实际上大多数检索 用户发现在把他们所需的查询信息转换为布尔值时并不是那么容易。尽管存在不 足,但该模型仍然是文档数据库系统中的主要模型。 ..向量空间模型 向量空间模型是由美国教授等人提出的文本表示模型【】,该 方法的思想是:把文本表征成由特征项构成的向量空间中的一个点,通过计算向 量之间的距离,来判定文本之间的相似程度。采用该模型的文本分类方法一般步 骤是:先通过对训练语料的学习对每个类建立特征向量作为该类的表征,然后依 面向矩消息的文本聚类研究 次计算该向量和各个类的特性向量的距离,选取距离大小符合域值的类别作为该 文本所属的最终类别。此模型中对所有的文档类和未知文档表示为 ,,,,...,。,,其中为关键字,为该关键字在文档中的 权重,一般使用. . 方式计算权重, 两个文档之间的相似度的计算可采用余弦方法。 模型将文本内容表示成数学上可分析处理的形式,然后在此基础上,使 用聚类算法对文本进行处理。基于的文本聚类过程如图.所示: 图.基于的文本聚类过程 通过向量表示文本,易于计算机处理,并引入了特征项权重,使得文档 相似度计算与文档内容更紧密结合,改善了布尔模型的二值逻辑缺陷。但 的特征项没有考虑词语之间语义依赖关系,使得文本相似度计算存在一定偏差。 当然,有不少针对的改进模型,如潜在语义索引和基于本地的语义模型等。 ..概率模型 概率模型是信息检索领域中一个比较成熟的模型,在很多系统中取得不错的 应用效果。概率模型是一系列模型的简称,它综合考虑了词频、文档频率和文档 长度等因素,在概率测度空间上通过概率来衡量两个文本的语义相似度。经典概 率模型主要思想为:根据输入的检索条件,将文档集划分为与条件相关和不相关 的子集,并分别计算它们的概率值。概率值的计算与文本集的特征词有关,显然 对于较大规模的文本数据,由于特征词过多,计算将变得繁琐和不切实际。可引 入一些假设条件得到简化,实际应用中有二元独立概率模型、二元一阶相关概率 模型、双泊松分布概率模型等等。 概率模型的主要优点在于,文档可以按照他们相关概率递减的顺序来计算秩 ,而且简单直观。但是,它需要猜测一个初始的划分,将信息样本分成 相关和无关的两个集合,所有的权重都是二值的;对带有相关性标注的学习文档 硕:学位论文 具有依赖性,参数难以估计。这些不足是目前需要重点研究和改进的地方。 ..其他模型 其他还有基于概率和统计的语言学模型,通过建立数学模型来处理自然语言。 另外,还有新型非的文本表示模型,通过树和图的数据结构来表示文本关 系,并记录文本中词序结构、词语临近关系以及语义关系,增强计算的准确性, 使得这些模型更加灵活和实用,主要有后缀树模型、频繁词集超图模型和图空间 模型等。 本文在的基础上,利用其易于处理且支持处理大规模文本数据的特长, 改善其在表达语义方面的不足,达到更有效处理短消息文本的目的。 .相似度计算方法 在文本数据挖掘中,相似度计算起着基础性作用,具有较高的地位。而且, 文本相似度计算是聚类技术中的一个关键问题,文本相似度计算的优劣决定了最 终聚类结果准确与否。研究和分析现有的文本相似性度量方法,有助于了解它的 发展情况,发现它的不足之处,为设计适合短文本相似性计算方法提供理论依据。 下面将对目前典型的文本相似性度量方法的思想和适用领域进行介绍,并对其优 缺点进行简单分析。 ..基于向量空间模型的.方法 .方法是一种统计方法,在文档集或语料集中,用来评估一个字词在一 篇文档中的重要程度。字词的重要性与它在文件中出现的次数成正比,反过来与 它在语料库中出现的频率成反比。?方法一般基于模型。 在中,令文档由关键词集,,?,组成,通过计算关键词的重要 程度,得到权值。于是可以构建维向量空间,,,?,对应的坐标值分别 为,,?,。。由此将文档映射成向量空间中一个点,并可以用 ,,,,?,。,来表示文档集中的每篇文档,通过向量空间的转化后,文 档的相似性度量问题相应地转变为矢量计算问题。 .中,表示词条在文档中出现的频率,表示反文档频率, 主要基于这样的思想:如果包含词条的文档越少,则越大, 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 词条具 有很好的类别区分能力;否则的类别区分能力较差。 设,?,。为所有文档关键词集合,任意文档用,,?,。表示。 代表权重,计算方法如公式.所示: ,,厂、 彬珥×竺 \碍/ .】面向矩消息的文本聚类研究 其中,指特征项在文档中出现的次数,表示文档集合中所有文档 的数目,表示所有文档集合中出现的次数,称为特征项的文档频率。反 映特征项在整个文档集合中的分布情况,在一定程度上体现了该特征项的区 分能 力;反映特征项在文档内部的分布情况。.算法可以排除那些高频、低 区分度的词,因此.是一种有效的权重定义方法。用同样的方法,可以计 算目标文本的维向量 , ,?,。’。然后,用向量余弦方法来计 算两文本和 之间的相似度。公式如.所示: 跏伍‖卜腩 . 向量展开后的余弦系数公式如.所示: 疗 ?%‰ 七 . 跏伍,乃 其中,表示文本的特征向量,表示文本 的特征向量,;。、,。分别 为对应文档第维的权重。 以上除了余弦计算方法外,还有内积法、系数法、系数法等。 ?方法基于关键词权重计算,只有当文本关键词数量较多时,这种统计方法 才会显示出足够的优势。而对于词语数量较少的短文本,该方法并不太适合。 ‘ ..潜在语义标引法 潜在语义标引 ,‘】是一种信息检索技术,可以 认为经典向量空间模型的一种改进,性能优于传统技术。 是一种建立在统计之上的学习方法:它试图发现对象之间的关联模式及 其隐藏的对象间的结构关系。方法最初应用于文本信息检索领域,它可以有 效地解决了同义词和多义词的问题,通过识别文本中的同义词,将信息检索 精度提高了%至%。 原理主要是利用矩阵理论中的“奇异值分解’’ ,技术。分解定理如下:设是秩为的×的实值矩阵, 则存在阶正交矩阵,阶正交矩阵,使得?,其中对角矩阵?为 ?旃昭,仃,?仃,,,?,满足仃?仃,??仃,,,,?,称仃,为矩阵的奇异 值,,的列向量分别称为的左、右奇异向量。 在向量空间模型中,一篇文档可用中的一个向量来表示,由此,先将 文档向量构造词频矩阵,然后将其转化为奇异矩阵,并使用标准化的内积来 计算 硕:学位论文 向量之间的夹角余弦,最后根据计算结果比较文本间的相似度。 在一定程度上解决了语义相似问题,但其效果依赖于上下文环境,适用 于上下文联系紧密的较长文本,而不适合短文本相似度计算。 ..基于汉明距离的文本相似度计算方法 汉明距离又称汉明重量。在信息论中,两个等长字符串之间的汉明距离是两 个字符串对应位置的不同字符的个数。假设两个长码子分别为:?。?‘ 则它们之间的距离计算公式如.所示: . ,?%儿 七 其中,表示模加运算,靠?,,妖?,。,,表示和在同一 位置码符号差异数之和。换句话说,它就是将一个字符串变换成另外一个字 符串 所需要替换的字符个数。它为比较两字符串的相似度提供了一种依据。例如: 与 之间的汉明距离是。 同样,文本信息可用这些码字表示,通过计算汉明距离可以定量地表示文本 之间的相似程度。设文本对应的码字为,文本对应的码字为,码字 用二迸制表示,和分别表示文本对应位置的信息分量是否具有。通过公式. 计算,可得到两文本之间的距离。 文献】提出了基于汉明距离的文本相似度计算方法。对于不同文本,或文 本与查询之间,先确定它们的码字集,令??,。,那么相似度计算公式如.所示: . 跏,一?稚。儿 七 其中、分别表示文本对应的码字和查询式对应的码字中 第位的分量,要么为要么为,就是模加运算。模运算对于计算机来说 非常方便,能达到极快的速度。 用上述方法刻画文本相似度是合理的,但由于文本转换为码字及码字之间匹 配工作非常耗时,该方法对于较大规模的文本数据聚类时效果并不明显。 ..基于语义理解的文本相似度计算方法 文献【 】提出了基于语义理解的文本相似度算法。在知网语义相似度的基础 上,由词语相似度计算得到句子相似度,并将基于语义理解的相似度计算推广到 段落范围,进而可以将这种段落相似度推广到篇章相似度计算。该方法给出了文 本包括词语、句子、段落相似度的计算公式及算法,用于计算两文本之间的相 面向怎消息的文本聚类研究 似度。该方法不需要较长的训练时间,也不需要大规模语料集支持,准确率较高。 但这种推广计算方法,需要花费大量时间,效率并不高。 除了上述分析的文本相似度计算方法外,还有一些较常用的方法,如基于属 性论的文本相似度计算方法【】、基于压缩稀疏矩阵矢量相乘的文本相似度计算方 法【等。本文在.的基础上进行改进,基于语义克服短文本关键词少、词 频低的问题,改善词间关系和语义表达上的不足,支持大规模短消息聚类。 .主要聚类算法 文本聚类系统中最关键的是聚类算法,算法的优劣决定了聚类的最终效果和 效率。目前文本聚类算法很多,划分可以基于不同的标准,比如凝聚的还是分裂 的、增量的还是非增量的、确定的还是随机的、硬划分还是模糊的等等。聚类算 法体系的分类标准并不统一,且难以明确划分分类界限,不少聚类算法可能同时 具有其他类别的特征。概括起来,还是可以根据它们的聚类原理、组织方式进行 分类,主要有划分聚类、层次聚类、密度聚类、网格聚类以及基于模型的聚类方 法等。 ..划分的方法 划分聚类算法对包含个文档的文本集合,划分将生成个分组,,每 一个分组代表一个聚类。划分方法通常使用迭代优化的方法,反复计算每个分组 的类别中心,并将对象分配到与中心具有最大相似度的类别中去,直到划分 达到 最优,准则函数开始收敛为止,也就是中心点不再改变,文本对象不再重新分 配。 划分聚类算法的准则函数通常选用平方误差准则,如公式.所示: . ?:.?一一% 典型的划分方法包括.和.方法。.方法用该聚类中 所有对象的均值来代表该聚类,而.方法则选用簇中位置最靠近中心的 对象作为代表对象中心点,试图找出更好的中心点,消除噪声数据的影响, 以改进聚类结果的质量。 .是一种比较常见的聚类算法,常常在文本聚类中使用,具体步骤如 下: 任意选择个对象作为初始的类的中心; ; 根据类中文档的平均值,将每个文档重新赋给最相近的类; 更新类的平均值; 不再发生变化,即没有对象进行被重新分配时过程结束。 顶‘学化论文 该算法试图找出使平方误差值最小的个划分。当结果簇是密集的,而簇与 簇之间区分明显时,它的效果较好。该算法虽然运行时间快,但是存在一些缺 点 如受初始簇中心影响较大,要预先指定聚类数,容易受孤立点的影响等。 ..层次的方法 层次聚类法 将文本集合进行层次分解,组成一颗凝 聚树。根据层次的形成方式可以分为两类:凝聚的方法,也称自 底向上.;分裂的方法,也称自顶向下?。代表 性的算法有、、等。 凝聚的层次聚类方法采用自底向上的策略,首先将每个文档看作一个类,然 后相继合并相近的文本类,直到所有的文档合并为一个类,或者达到某个终止条 件,如希望得到的类的个数或者两个相近的类超过了某一个阈值,就结束进行。 分裂的层次聚类方法首先将所有的文档看作一个类,然后逐渐细分为越来越 小的类,直到每个文档自成一类,或者达到某个终止条件,如希望得到的类的个 数或者两个相近的类超过了某一个阈值,就结束进行。 层次聚类法对聚类粒度具有较大的灵活性,适合任意形状的簇。不足之处在 于一旦一个步骤合并或分裂完成就不能修正,以致划分错误的文档无法更正, 当然,此方面缺陷在、、算法中有一定改善;另外不足 在于难以适应动态数据集。 ..基于密度的方法 基于密度的方法认为:只要邻近区域的数据密度超过了某个特定值,则继续 聚类,直到达到某一阈值。这样能保证在某个类中任意数据点的给定区域范 围内, 不能少于多少数目的点,否则还得继续聚类。通过这种方法,一些噪声点数据将 会被排除在外,利于对真正有效的数据进行聚类。另外,该方法能够发现任意形 状的簇,处理数据灵活性高,比其它聚类算法如划分的方法具有一定的优势。从 整个数据空间来看,使用该方法进行聚类后,将形成由低密度区域分隔开的高密 度数据区域。 基于密度的常用方法有算法、算法和方法。 ..基于网格的方法 基于网格的方法利用多维网络数据结构,把对象空间量化为有限数目的单元, 形成一个网格结构。所有的聚类操作都在这个网格结构即量化的空间上进行。 该方法处理速度快,其处理速度独立于数据对象的数目,只与量化空间中每一维 的单元数目有关。缺点是不适合应用于大规模数据。典型算法有、 和。 面向短消息的文奉聚类研究 利用存储在网格单元中的统计信息进行聚类,利用一种 小波变换方法来聚类对象,则是在高维数据空间中综合了基于密度和基 于网格的聚类方法。 ..基于模型的方法 基于模型的方法对每一个簇设定一个模型,为该模型比对匹配数据。并通过 设置反映数据点空间分布的密度函数来定义聚类。它也基于标准的统计数字自动 决定聚类的数目,考虑噪声数据或孤立点,从而产生健壮的聚类方法。这样的方 法经常基于这样的假设:数据是根据潜在的概率分布生成的。该方法主要有两类: 统计学方法和神经网络方法。著名的自组织特征映射 , 就是一种利用了人工神经网络技术的聚类方法。 ..后缀树聚类算法 算法主要思想【】:后缀树聚类算法是一种直观的文本聚类算法,它将文本聚 类为一组的依据是文本含有共同的短语。实际上是将文本看成词的序列,充分利 用了词与词之间的距离信息,在寻找文本共同的短语的过程中使用了后缀树这种 数据结构。 首先提出了后缀树聚类算法,并且将这种技术运用到搜索 结果的可视化中,取得了很好的效果。搜索引擎中的部分工作也利用了 算法实现曲搜索结果的聚类,并且指出了算法的若干不足,但没有 对聚类结果的质量进行评价。 除了以上的聚类算法外,还有其他应用于文档聚类分析但很难分到上面的体 系内的算法,包括基于关联规则与超图划分的聚类算法、蚁群聚类算 法以及各种改进算法等。 许多文本聚类算法已经相当成熟,但从上亦可看出,不少算法未能解决文本 数据集的动态性和大规模性。一个好的聚类算法主要参考以下标准: 有较高的可伸缩性。不仅用于实验,还能用于实际处理大规模文本数据集。 能处理高维数据。对表示的高维数据能够适时降维。 能发现任意形状的聚类。 输入参数与领域知识的依赖性低。 对数据的输入顺序不敏感。如在中,把 词汇 英语3500词汇语境记忆pets3考试词汇二年级反义词和近义词初中词汇词汇大全考研英语二高频词汇表 当作特征项单位,对应 值为词汇的权重,这些键值对的输入顺序应不能影响聚类的结果。 能够处理和解决噪声数据的干扰。 文本聚类算法是与文本表示模型密切相关的,在文本聚类过程中,文本聚类 算法需要根据模型数据建立相适应的处理方式。本文提出了基于频繁词集和 .的混合算法,通过频繁词集挖掘算法生成初始聚簇,计算轮廓系 数去重,调用基于语义的相似性计算方法,使用.算法输出聚簇,实现具 硕学位论文 体应用。 .本章小结 本章主要介绍了种文本聚类的模型,介绍了一些文本相似度计算方法,另 外阐述了当前主要的聚类算法。其中重点介绍了基于向量空间模型的.方 法以及典型的聚类算法。 文本聚类应用很广,近年来在信息检索、多文档自动文摘、信息管理等领域 都有广泛的应用,功能大致归纳如下:改善分类和检索的性能;将聚类结果作为 分类的输入;利用聚类技术对用户的行为进行分析,用以发现用户的兴趣偏好, 从而实现对用户的主动信息推送。另外,还可用于垃圾邮件甄别、了解用户建议 和反馈信息、掌握社会舆情状况、提供决策支持等。 文本数据挖掘和相关聚类技术具有较长的发展历程,而对短消息文本相关研 究发展较晚,其与以往关注的常规文本也具有较大区别。这里所说的短消息指由 即时通信平台产生的持续、快速、大规模的短文本数据。这些数据信息数据量巨 大,是一种非正式的、无结构性的短文本,如何对这些数据进行有效的存储、分 析、计算和挖掘,这是当前时代环境下面临的极大挑战。下面的章节将针对短消 息文本设计相应的文本聚类算法。