基于图论模型的文本重叠聚类研究

"How to find the number of the clusters" and "how to model overlapping clustering" are two important research problems in document clustering..In order to solve these two problems, we propose a graph model and an overlapping clustering algorithm for documents categorization. Our research mainly focuses on: (1) Introducing a graph model for document clustering and mapping information between different documents into the graph model. Convert the hierarchical clustering of Documents into the contraction of subgraphs. (2) Selection of overlapping subgraphs in the graph model. Realize the overlapping clustering of documents by finding appropriate overlapping subgraphs in the graph model. (3) Optimization of the maximum cut problem. Using the max cut in the hierarchical clustering tree to get the best number of clusters. Based on our previous research results on graph model for text classification, the structual information of text document is mapped into a sinature graph. By applying the proposed clustering method to the signature graph, the number of clusters coud be automatically determined and good overlapping clustering results would be achieved. Document clustering has wide applications in information retrival, search engine, document topic identification. It is an important research field in information science.

针对现有文本聚类分析中"如何选择最佳的聚类类簇数和如何实现重叠聚类"这两个重要研究课题，探讨实现文本重叠聚类的图论模型和聚类方法。主要研究内容包括：（1）研究文本聚类的图论模型，将文本间的信息映射到图空间，把自下而上的层次聚类问题转化成子图逐层收缩问题;（2）研究加权图中子图的密度变化特点，通过选取合理的重叠子图实现文本聚类结果中"单文本多类属"这一重叠聚类目标;（3）研究图论中最大割的组合优化算法，将选择最佳类簇个数这一问题转化为寻找聚类层次图中最大割问题。在此研究结果上，结合申请者在文本特征建模方面的已有成果，将文本的结构信息映射为特征图以改良传统的文本特征信息，最终实现文本聚类类簇个数的自动确定和高效的重叠聚类。文本聚类广泛应用于信息索引、搜索引擎、文档主题识别等领域，是信息科学的一个重要研究问题。本课题的研究对文本信息技术的发展具有重要的学术和应用价值。

大规模文档聚类是解决海量文本中数据理解和信息挖掘的有效解决手段，是信息科学的一个重要研究问题。本项目围绕如何选择合适的聚类类簇个数和如何实现重叠聚类这两个基本问题开展一系列研究，完成了项目研究任务，取得了预期的研究成果。.针对常规聚类算法在处理海量数据时聚类效果不够理想这一问题，本项目研究了基于可变网格划分的抽样算法，构建与原始数据集分布特征一致的网格空间，解决大规模不均匀数据集的抽样问题。并提出基于特征选择的统计最优样本大小算法，自动确定最优样本大小。该方法在减少聚类样本数量的同时，有效地保持原始数据集的相关信息。在Web页面特征信息提取方面，本项目研究了增强约束条件随机场模型，在条件随机场模型中引入可信约束条件，将大间隔理论的思想融入到条件随机场模型训练方法，在条件随机场模型中引入增强因子，提高Web对象属性标注的正确率。基于每个点的中心度反映该点在网络结构中的重要程度这一发现，我们提出了基于节点中心度和图收缩的重叠聚类模型。该聚类算法实现聚类类簇个数的自动确定，并允许单个节点属于多个类别，实现了重叠聚类。针对传统的模糊C-均值聚类算法对初始聚类中心较敏感、易陷入局部最优这一问题，课题组利用粒子群算法的全局搜索能力代替FCM算法寻找初始聚类中心，并从类内紧致性和类间分离度两方面出发对适应度函数进行重新设计，实现全局最优模糊聚类。在聚类类簇个数自动确定方面，研究了基于加权距离计算的自适应粗糙K-均值算法。本项目还将课题组研究的算法扩展应用到计算机视觉领域，在目标分割和图像理解方面也取得一定成果。.本项目的研究进展与成果丰富了文本聚类方法，具有重要的学术价值与应用价值。目前已在国内外重要期刊及国际会议发表论文23篇，其中SCI/EI论文8篇。申报国家发明专利二项，其中一项已获得授权。培养研究生7人。获省部级科学技术进步奖一等奖1项、三等奖1项。