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

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