基于博弈论的高效稳定聚类算法研究

项目名称： 基于博弈论的高效稳定聚类算法研究

项目编号： No.61473045

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 其他

项目作者： 侯建

作者单位： 渤海大学

项目金额： 80万元

中文摘要： 聚类是计算机科学中一种重要的基本分析工具。现有聚类算法一般需要某种形式的参数输入，并面临着数据噪声和类别模糊等方面的问题。主集聚类方法将博弈论中的纳什均衡和类联系起来，较好地解决了现有聚类方法存在的主要问题。针对现有主集聚类算法存在的不足，本申请以聚类在模式识别和计算机视觉中的应用为背景，从博弈论的角度出发，深入研究基于博弈论的聚类机理，并由此提出高效稳定的新型聚类算法。首先研究数据相似度影响聚类结果的机理，解决聚类算法依赖参数输入的问题。研究一种新型博弈动力学，从根本上解决聚类过程内存消耗大和计算速度慢的问题。在分析数据权重的基础上，提出一种能够稳定收敛的软聚类算法。在两两相似度聚类算法的基础上，研究基于博弈论的新型超图聚类算法，进一步拓展博弈论的应用领域。本申请的研究内容涉及机器学习、博弈论、图论、模式识别与计算机视觉等多个领域，其成果对其它相关领域也具有一定的参考价值。

中文关键词： 主集；聚类；博弈论；模式识别；计算机视觉

英文摘要： Clustering is an important and basic tool in computer science and widely applied in various domains. However, existing clustering algorithms usually require parameters as input, and are afflicted by such problems as noisy data and cluster ambiguity, etc. By building a correspondence between clusters and Nash equilibria in game theory, dominant sets clustering solves the main problems afflicting existing clustering algorithms quite satisfactorily and exhibits significant theoretical and practical potential. In order to extend the application of clustering in pattern recognition and computer vision tasks, this proposal proposes to investigate the mechanism of game-theoretic clustering and present an efficient and robust clustering algorithm. Firstly, the impact of data similarity on clustering results is investigated, and a non-parametric clustering algorithm is presented. Secondly,a novel game dynamics is to be designed to reduce the memory and computation load in the clustering process significantly. Based on the weights of members inside a dominant set, a novel soft clustering algorithm is to be presented .Beyond the clustering based on pairwise similarity of input data, a novel game-theoretic hypergraph clustering algorithm is presented, which extends the application of game theory. The research topics of this proposal is related to such active research domains as machine learning, game theory, graph theory, pattern recognition and computer vision. This project gives rise to a set of reliable and efficient clustering algorithms, which is also useful to related domains.

英文关键词： dominant set;clustering;game theory;pattern recognition;computer vision