Radius k-means算法及其拓展问题的研究

This project firstly proposes a Radius k-means, which couples each cluster with a radius R. Only the data point, which is located in the area covered by cluster, can be assigned to the cluster. This is different from the k-means algorithm which aims to partition the data into k clusters. The Radius k-means algorithm aims to learn clusters with less information and higher density. Less information ensures the consistency of the cluster while higher density ensures the coherence of the cluster. The objection function of radius will be optimized with a sequential “draw-merge” procedure, which ensure the convergence of the algorithm, and can be easily implemented. By examining the information carried by the data point, we can determine whether it is suitable to be assigned to multiple clusters. As a result, the separation of the clusters can be controlled. By exploring the hidden relation between the parameter R and the size of cluster, we design a technology to automatically determine parameter R. The Bregman information is used to measure the connectivity between two clusters, thus we can merge the clusters when they are well connected. By this, the higher patterns are extracted from multiple clusters. This project, on the one hand, makes a breakthrough of classical k-means; on the other hand, provides an effective mechanism for big data analysis.

项目首次提出Radius k-means，它打破了k-means算法的划分聚类，为每一个簇匹配一个半径R，只有位于以簇质心为中心点、R为半径所覆盖区域内的数据对象才可被指派到该簇中。Radius k-means力图从数据中学习低信息、高密度的簇，低信息确保了簇内数据对象的一致性，高密度确保了簇的凝聚性。针对项目研究中亟待解决的关键问题，拟采用顺序“抽取-合并”策略来优化目标函数，它具有聚类速度快、实施性强的特点；拟通过考察每一个数据对象自身携带的信息来判断它是否适合被指派到多个簇中，从而控制簇与簇之间的分离性；拟通过探索R与簇所包含数据对象的数量之间的规律来解决R的确定问题；拟采用重叠区域数据对象所承载的信息量作为簇与簇是否连通的判定依据，来解决基于可信簇的数据高层模式再抽取问题。该项目的研究，一方面完成对经典k-means的突破，另一方面为大数据分析提供一种有效的学习机制。

Radius K-Means从质心、半径、互信息及密度四个方面来描述簇，其中质心决定了簇在数据空间中的位置，半径刻画了簇所能覆盖的范围，互信息度量了簇中所包含对象的一致性，密度反映了簇所包含对象的数量。给定一个半径，期望从数据空间中寻找具有低信息、高密度的簇，低信息使得簇内所包含的数据对象具有较强的一致性，高密度使得一个簇具有较强的凝聚性。为此，项目研究了Radius K-Means目标函数的定义、算法的优化、聚类的灵活性、理论分析、应用适宜性等。在Radius k-means思想的基础上，项目研究了一致性聚类、多任务聚类、聚类的可解释性、推荐算法、集体行为识别等。在项目的资助下，在国内外期刊会议上发表论文15篇，其中一些研究成果发表在软件学报、计算机学报、计算机研究与发展、IJCAI 2016、CVPR 2017、ICNC-FSKD 2017、Information Sciences、IEEE Trans on Multimedia、Water上。