基于最大公共子图的谱聚类算法在文本聚类中的应用研究

This project proposes a spectral clustering model which based on maximum common subgraph and grey theory. The inner feature of a text is described via text-graph model which based on entity relationship so that the text can be mapped into an undirected graph. The similarity of any two texts is calculated via maximum common subgraph so that numerial calculation in high dimension space can be transformed into process of traversing a graph structure in order that data sparse and isolated point problems in similarity calculation can get solved. The transitive regular is established to optimize similarity matrix. What's more, a fuzzy spectral clustering model is built by grey Laplace matrix which based on grey theory and traditional spectral clustering. The research contains five key problems: (1)mining entity inner feature and establishing entity relationship; (1) building mapping model from text into graph; (2) calculating maximum common subgraph and text similarity; (4)proposing transitive rule for text similarity; (5) building fuzzy spectral clustering model based on maximum common subgraph. The project will establish an experiment system which based on maximum common subgraph, then process fuzzy spectral clustering in Chinese texts and analyze performance of the system.

本课题探讨一种基于最大公共子图和灰色理论的谱聚类模型。基于实体关系建立文本-图映射模型，刻画文本内涵特征，将文本映射为无向网状图结构。为了解决文本聚类过程中可能遇到的数据稀疏及孤立点问题，将高维数值计算问题转化为对映射图拓扑结构的遍历问题，通过求解映射图的最大公共子图计算文本相似性。基于文本相似度传递的思想，建立传递规则，优化相似度矩阵。结合灰色理论及谱聚类思想，构建灰色拉普拉斯矩阵并建立模糊的谱聚类模型。研究涉及5个关键性问题：（1）挖掘实体内涵特征并构建实体关系；（2）建立文本-图映射模型；（3）求解最大公共子图并计算文本相似度；（4）提出文本相似度传递规则（5）建立基于最大公共子图的模糊谱聚类模型。本课题将基于最大公共子图相似度算法，建立模糊谱聚类实验系统，采集中文文本信息实施文本聚类，根据聚类结果分析系统性能。

本项目主要研究了基于最大公共子图的文本谱聚类算法及其应用。主要研究成果包括：1）实体抽取及文本-图映射模型；2）基于最大公共子图的谱聚类算法；3）研究成果转化及应用。. 基于实体-动作关联模型提出文本-图的两级映射。第一级：实体-语句映射。基于浅层句法分析，从语句中抽取实体-动作关联。第二级：语句-文本映射。将文本的实体映射到节点集，动作关系映射到边集，把文本表示成图结构。. 提出了利用文本映射图的最大公共子图来表征文本相似性的方法。提出了一种快速求解最大公共子图的算法。根据文本映射图的稠密程度调节相似度计算的重点。我们分析了文本长度的差异对算法的影响，设计了比例加权算法。当两个文本的长度存在较大差别时，根据权重占比来量化文本相似度。. 提出了基于灰色理论的自适应模糊谱聚类算法。我们改进了传统谱聚类算法对隶属度矩阵的约束条件，增强算法的抗噪能力。构建了文本和词汇之间的二部图模型，使用词-文档矩阵的奇异向量解决谱图的分割问题。根据隶属度矩阵特征值之间的差值，实现聚类数目的自适应调整。提出独立于聚类过程的聚类重构策略及近邻域的概念，对谱聚类的结果实施评价和优化，调整不正确的聚类结果。. 项目组将研究的成果应用到实际应用中，与贵州耕云科技有限公司联合开发了大数据融合开发平台DDP（Data Development Platform）。我们承担了平台的部分数据挖掘和分析任务，包括文本特征抽取、可视化文本分析、实体分析、聚类分析等。项目组为平台提供了各种机器学习组件，支持各类语义分析、数据挖掘、预测与评估等算法。提供了针对行业用户业务需求的数据挖掘算法，构建了一个数据挖掘和机器学习平台。. 目前项目组已经在《中文信息学报》等核心刊物上发表论文11篇。目前3篇论文被《中文信息学报》收录，2篇已经见刊。1篇会议论文发表于CCL2015。另有一篇论文正在《计算机研究与发展》进行审稿。培养了一名在读博士生，12名硕士研究生，其中10名硕士研究生顺利完成学业并取得学位。.