海量短语信息挖掘技术的研究与实现

论文摘要

互连网和信息技术的飞速发展造成海量的数据积累,其中很大一部分是短文数据,如文章摘要和聊天室的会话。对海量的短文数据进行自动的分析和挖掘,从中获取有价值的隐含知识,已经成为一项迫切的需求。与普通文档不同,短文中关键词出现的次数很少,传统的基于词频的文本挖掘技术在处理短文数据时很难得到可接受的准确度。同时,面对几百GB甚至TB级的海量数据,传统的文本挖掘算法变的很低效甚至根本无法运行。本文在对海量短语信息挖掘的研究现状和面临的挑战进行深入分析的基础上,以海量数据处理系统项目为背景、以开发高准确度和高可伸缩性的海量短语信息挖掘算法为目标,在海量短语信息数据库中的频繁词集挖掘、分类、聚类等方面开展了深入的研究。为了提高挖掘算法的准确度主要采用了基于语义的方法。为了提高算法的性能和可伸缩性主要采用了并行化的方法。本文的贡献主要包括以下方面:1.针对海量短文本数据库中的频繁词集挖掘所面临的挑战,提出了一个top-k频繁词集挖掘的并行算法parTFT。该算法使用了一种新颖的逻辑纵向数据划分方法来确保top-k频繁词集挖掘能够在各数据分区中并行执行。同时在每个挖掘结点通过启发策略来裁剪H-struct的header table,从而提高算法的性能。实验结果表明该算法在进行海量短文数据库中的频繁词集挖掘时具有比同类算法更好的性能和可伸缩性。parTFT算法的相关成果发表在第六届Web时代信息管理大会（WAIM2005）上,SCI检索号BDG49。2.针对短语信息分类中的低准确度问题,提出了一个基于语义的短文分类算法SDCS。该算法使用文本语义特征图来表示语义信息,并通过K-近邻（KNN）的思想来进行短文分类。实验结果表明该算法在处理大规模短文数据时,性能和准确度都超过了其它的短文分类算法。相应的成果已投计算机研究与发展杂志。3.在对短文本聚类面临的挑战进行分析的基础上,针对不同的应用需求提出了基于频繁词集的短文本聚类算法FTSDC和基于密度的短文本聚类算法DSDC。FTSDC首先根据频繁词集进行初始簇划分,然后利用语义信息进行簇优化。DSDC使用语义信息来计算样本距离,基于共享近邻（SNN）图来进行基本聚类,并通过数据抽样和子图划分来实现并行聚类。实验结果表明两种方法在准确度和可伸缩性上都比类似的算法有一定的提高。FTSDC的相关成果发表在WISE2006的研讨会“基于Web的海量信息处理（WMDP2006）”上,SCI检索号BFF82。DSDC的相应成果已投软件学报。4.针对基于语义信息的文本挖掘中准确度仍然有待提高以及语义信息不易管理和交换的问题,定义了领域本体并给出了其构建方法,并在此基础上提出了基于频繁词集和领域本体的聚类方法OFSDC,以及基于密度和领域本体的聚类方法DFSDC。实验结果表明基于领域本体的文本挖掘方法能够更好地利用语料中的语义信息,从而获得更高的准确度。OFSDC的相关成果发表在VLDB2006的研讨会“数据库和信息系统中基于本体的技术（ODBIS2006）”上,SCI检索号待查。5.在对并行数据挖掘的体系结构进行研究的基础上,提出了基于CORBA的海量短语信息并行挖掘体系结构,并在大规模事务处理中间件StarTPMonitor的背景下实现了海量短语信息挖掘引擎。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.1.1 信息时代的数据规模
• 1.1.2 海量文本挖掘需求
• 1.2 研究现状
• 1.2.1 文本挖掘的相关工作
• 1.2.2 海量短语信息挖掘面临的挑战
• 1.3 本文工作
• 1.4 论文结构
• 第二章 海量短文数据库中的频繁词集挖掘
• 2.1 频繁词集挖掘
• 2.1.1 关联规则挖掘和频繁词集
• 2.1.2 频繁项集挖掘方法
• 2.1.3 频繁词集挖掘面临的挑战
• 2.2 并行Top-k频繁词集挖掘算法
• 2.2.1 问题描述和基础工作
• 2.2.2 短词集和重复词集排除
• 2.2.3 H-struct裁剪策略
• 2.2.4 数据划分和并行化处理
• 2.2.5 parTFT算法
• 2.3 算法实验研究
• 2.4 本章小结
• 第三章 海量短语信息分类
• 3.1 文本分类
• 3.1.1 问题描述
• 3.1.2 向量空间模型和文本特征选择
• 3.1.3 基于向量空间模型的文本分类
• 3.1.4 基于语义的文本分类
• 3.2 概念语义空间和信息流
• 3.2.1 HAL概念语义空间
• 3.2.2 概念组合策略
• 3.2.3 基于HAL的信息流计算
• 3.3 文本语义特征图
• 3.3.1 基于图的语义信息表示
• 3.3.2 基本语义树构建
• 3.3.3 优化语义树
• 3.3.4 语义特征图构建
• 3.4 基于语义的短语信息分类算法
• 3.4.1 基于TSFG的KNN方法
• 3.4.2 加权最短路径问题
• 3.4.3 SDCS算法
• 3.5 算法分析和实验研究
• 3.5.1 准确度度量
• 3.5.2 实验环境和数据集
• 3.5.3 实验方法和结果
• 3.6 本章小结
• 第四章 海量短语信息聚类
• 4.1 短文本聚类
• 4.1.1 文本聚类方法
• 4.1.2 短文本聚类面临的挑战
• 4.2 基于频繁词集的短文本聚类
• 4.2.1 基本聚类方法和簇的表示
• 4.2.2 并行化方法
• 4.2.3 基于语义信息的簇重叠消除
• 4.2.4 FTSDC算法
• 4.3 基于密度的短文本聚类
• 4.3.1 基本的密度聚类方法
• 4.3.2 基于SNN的密度聚类
• 4.3.3 短文本距离计算
• 4.3.4 并行化方法
• 4.4 算法实验研究
• 4.4.1 FTSDC算法实验研究
• 4.4.2 DSDC算法实验研究
• 4.5 本章小结
• 第五章 基于本体论的海量短语信息挖掘
• 5.1 基于本体论的文本挖掘
• 5.1.1 本体论概述
• 5.1.2 基于本体论的文本挖掘方法
• 5.2 短文数据库上的领域本体构建
• 5.2.1 本体描述
• 5.2.2 形式概念分析
• 5.2.3 领域本体构建
• 5.3 基于领域本体的海量短语信息聚类
• 5.3.1 OFSDC的基本思想
• 5.3.2 基于频繁概念集的短文聚类
• 5.3.3 基于领域本体和密度的短文聚类
• 5.4 算法实验研究
• 5.4.1 OFSDC算法实验研究
• 5.4.2 ODSDC算法实验研究
• 5.5 本章小结
• 第六章 海量短语信息挖掘引擎的设计与实现
• 6.1 StarTPMonitor系统结构
• 6.2 StarSTMiner总体设计
• 6.2.1 总体结构
• 6.2.2 并行化体系结构
• 6.3 StarSTMiner子模块的设计与实现
• 6.3.1 汉语分析模块
• 6.3.2 语义信息构建模块
• 6.3.3 短文挖掘模块
• 6.4 本章小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果