短语消息聚类相关技术研究

论文摘要

随着互联网和通信技术的发展,Instant Messaging、Internet Relay Chat等即时通信工具得到广泛普及和应用。这些即时通信工具往往产生大量的、用于人们交流和通信的交互性短文本,简称为短语消息。短语消息在传递公开信息的同时携带了丰富的用户信息,从而成为一种新的具有极大价值的信息资源。对短语消息进行分析和挖掘,对于信息的管理和优化、关键信息的提取、以及信息的理解等具有重要意义。短语消息是一种即时交互性短文本,与常规文本相比,具有不完整性、交错性、不规范性和混淆性的特点。此外,高速的短语消息流造成了大规模的短语消息归档数据库。这些特征给短语消息挖掘研究提出了挑战。本文以短语消息挖掘为背景,以短语消息聚类相关技术为研究内容,以构建准确、高可伸缩的短语消息聚类系统为目标,展开了从短文本相似性度量到短语消息预处理,再到并行的短语消息聚类算法的系列研究。主要研究成果包括:（1）针对短语消息的特点,提出了一个短语消息聚类系统模型MeCSyM,该模型兼顾了短语消息流和归档的短语消息数据库场景,包括短语消息会话抽取、短文本表示与相似性度量、并行短语消息聚类算法三个主要部分,为短语消息聚类提供了一个可选的总体研究方针和路线,是本文开展短语消息聚类研究、设计和实现的基础。（2）详细分析了短语消息的内容特征、语法特征和时间特征,提出了短语消息流上的会话抽取算法DWExter。利用短语消息间时间分布特征,设计了双时间窗口机制及其数据结构RMR,以支持DWExter算法较高的执行效率,实现动态短语消息流上高效的会话抽取功能。在真实数据集上的实验表明,与两个基准测试算法相比,DWExter的准确性分别提高了约85%和18%。（3）针对短文本关键词稀疏而导致常规度量方法下文本相似度漂移的问题,提出了基于HowNet和语料集的词间关系量化算法CrtNRG。在该算法的基础上,针对高速文本消息流分析和大规模短文本数据挖掘,提出了短文本的动态向量表示和相似性度量算法SiM。在短文本聚类实验中,分别采用TF-IDF方法、基于语料集的方法和SiM算法作为文本相似性度量算法,实验结果表明,与TF-IDF方法相比,SiM算法使聚类质量提高了一倍以上,而与基于语料集的方法相比,采用SiM算法的聚类质量也得到了约36%的提升。（4）在分析k-means算法和基于频繁词集聚类算法特点的基础上,提出了一个短文本混合聚类算法SHDC。该算法利用上述的SiM算法,可以为短语消息会话生成高质量的聚类结果,并且为聚簇提供了描述信息。另外,以降低数据子集间耦合度为目标,设计了一个纵向的数据划分策略VDiV。以此为基础,提出了并行k-means的改进算法OK-means,并提出了粗聚类的概念和并行粗聚类算法parROC。基于以上两个并行算法,设计了一个并行的短文本混合聚类算法parSHDC。实验结果表明,相对PDDP K-mean和并行k-means算法,parSHDC在聚类质量上分别提高了约12%和18%,而加速比分别提高了约38%和50%。（5）基于上述研究成果和研究组已有的系统平台StarTPMonitor,设计并实现了一个短语消息聚类原型系统StarSTMiner+,通过对StarSTMiner+系统结构的介绍,讨论了主要模块的实现方法和可进一步完善的方面。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 短语消息聚类需求背景
• 1.1.2 短语消息聚类问题的提出
• 1.2 相关工作分析与挑战
• 1.2.1 会话抽取相关工作分析
• 1.2.2 文本模型分析
• 1.2.3 主要聚类算法分析
• 1.2.4 短语消息特征和挑战
• 1.3 本文工作
• 1.3.1 研究内容
• 1.3.2 主要工作和创新
• 1.4 论文结构
• 1.5 术语和符号
• 第二章 短语消息聚类系统模型MeCuSyM
• 2.1 常规文本聚类模型分析
• 2.2 短语消息特征分析
• 2.2.1 交错性特征
• 2.2.2 稀疏性特征
• 2.2.3 大规模特征
• 2.3 MeCSyM 模型的提出
• 2.4 MeCSyM 模型分析
• 2.4.1 会话抽取模块
• 2.4.2 文本表示与相似性度量模块
• 2.4.3 并行聚类处理模块
• 2.5 本章小结
• 第三章 会话抽取算法DWExter
• 3.1 短语消息流基本特征
• 3.1.1 内容特征
• 3.1.2 语法特征
• 3.1.3 时间特征
• 3.2 相关技术分析
• 3.2.1 基本算法介绍
• 3.2.2 关键算法分析
• 3.3 消息-会话相关性度量
• 3.3.1 消息与会话间相关度定义
• 3.3.2 最大反向相关数据结构RMR
• 3.4 会话抽取算法DWExter
• 3.4.1 DWExter 算法描述
• 3.4.2 算法复杂性分析
• 3.5 实验
• 3.5.1 实验设置
• 3.5.2 评价指标
• 3.5.3 测试数据集
• 3.5.4 实验结果
• 3.6 本章小结
• 第四章 短文本内容相似性度量算法SiM
• 4.1 问题描述与相关技术分析
• 4.1.1 问题描述
• 4.1.2 相关技术分析
• 4.2 词间关系无向图NRG
• 4.2.1 基于词法分类器度量词间关系
• 4.2.2 基于语料集度量词间关系
• 4.2.3 非均衡关键词权重
• 4.2.4 NRG 构建算法CrtNRG
• 4.2.5 基于NRG 的词间关系
• 4.3 文本动态表示向量
• 4.4 相似性度量算法SiM
• 4.5 实验
• 4.5.1 实验设置
• 4.5.2 评价指标
• 4.5.3 测试数据集
• 4.5.4 实验结果
• 4.6 本章小结
• 第五章 混合聚类算法SHDC 和parSHDC
• 5.1 基本概念与问题描述
• 5.1.1 基于频繁词集的聚类算法
• 5.1.2 k-means 算法
• 5.1.3 问题描述
• 5.2 相关技术分析
• 5.2.1 基于频繁词集的聚类算法
• 5.2.2 k-means 优化方法
• 5.2.3 基于频繁词集和k-means 的混合聚类算法
• 5.3 混合聚类算法SHDC
• 5.3.1 构建初始聚簇
• 5.3.2 SHDC 算法
• 5.4 并行聚类算法parSHDC
• 5.4.1 MPI
• 5.4.2 纵向数据划分策略VDiV
• 5.4.3 并行粗聚类算法parROC
• 5.4.4 改进的并行k-means 算法OK-means
• 5.4.5 并行混合聚类算法parSHDC
• 5.5 实验
• 5.5.1 实验一
• 5.5.2 实验二
• 5.6 本章小结
• 第六章 短语消息聚类原型系统设计与实现
• 6.1 StarTPMonitor 系统结构
• 6.2 StarSTMiner+系统结构
• 6.2.1 总体结构
• 6.2.2 系统平台
• 6.3 StarSTMiner+子模块设计与实现
• 6.3.1 数据访问模块
• 6.3.2 预处理模块
• 6.3.3 NRG 维护模块
• 6.3.4 相似度模块
• 6.3.5 会话合成模块
• 6.3.6 数据划分模块
• 6.3.7 聚类模块
• 6.3.8 调度模块
• 6.4 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间已发表和待发表的论文
• 攻读博士学位期间参与的科研项目