基于图理论的约束聚类方法及应用研究

Constrained clustering methods are the efficient technical approaches to improve the efficiency of clustering analysis and the quality of clustering results by embedding the specific domain knowledge in the form of constraints in the clustering process. This project studies on constraint abstraction, multi-type constraints integration and graph theory model utilization by making full use of clustering constraints, which provide a complete theoretical framework of semi-supervised clustering method based on graph theory. Taking the problem of community detection in directed networks as application scenario and considering the asymmetry of directed networks, constrained clustering methods based on graph theory will be applied to propose effective technical solutions.

约束聚类方法将特定的领域知识以约束条件的形式嵌入聚类过程，是提高聚类分析效率和聚类结果质量的有效技术手段。本项目拟通过充分挖掘和利用约束信息，对聚类约束的提取、多类型约束的集成以及图论模型运用进行相关研究，为基于图理论的约束聚类方法提供较为完整的理论框架。同时考虑有向网络的非对称性特点，将有向网络的社团检测问题作为应用场景，运用基于图理论的约束聚类方法提出有效技术方案。

基于图理论的聚类分析方法研究对于发现复杂网络中隐藏的模式和规律具有重要的理论意义。本项目针对于基于图理论的约束聚类方法开展研究，并将复杂网络的社团检测作为应用场景，取得了一系列研究成果。本项目的主要工作如下：基于样本点间的距离度量和最近邻思想，提出了一种基于万有引力搜索的密度峰聚类算法；针对目前的重叠社团检测算法存在识别准确度低、在大规模复杂网络中效率低等问题，基于顶点增长覆盖率生成约束集，提出一种自适应重叠社团检测算法；提出一种差分隐私保护的密度峰聚类算法，在局部密度和最短距离的计算过程中加入Laplace噪声进行差分隐私保护。项目执行期间，已发表相关学术论文18篇，包括Engineering Applications of Artificial Intelligence、Concurrency and Computation: Practice and Experience、World Wide Web、Journal of Intelligent Information Systems、 Intelligent Data Analysis等重要学术期刊论文，以及ICDM等高水平国际会议论文；其中，SCI收录11篇、EI收录3篇；授权发明专利1项。