具有虚拟领导的Flocking聚类算法

A New Clustering Algorithm Based on Flocking with Virtual Leaders

该文提出一种改进的带虚拟领导的Flocking模型,并基于此模型开发了一种数据聚类算法。在此算法中,数据集中的数据点被考虑为可以在空间中移动的Agent,并且根据改进的模型,生成有权无向图。然后从数据集中选定一组虚拟领导,每个数据点与其中γ个虚拟领导建立连接。所有与这个数据点有连接的邻居,都通过一个势函数产生场,对这个数据点进行作用,此数据点将沿着所有场矢量叠加的方向移动一段距离。算法中,虚拟领导的加入有效减少了数据点,特别是邻居较少的数据点向某个中心收敛的时间。在所有数据点不断受到作用而移动的过程中,同类的数据点就会逐渐地聚集到一起,而不同类的数据点则相互远离,最后自动形成聚类。此算法的实验结果表明,数据点能合理有效地被聚类,并且算法具有较快的收敛速度,同时,与其他算法对比也验证了此算法的有效性。

A modified flocking model with virtual leaders is proposed, and then a clustering algorithm based on it is developed. In the algorithm, firstly a weighted and undirected graph is established by all data points in a dataset according to the model, where each data point is regarded as an agent who can move in space. Then a set of virtual leaders are identified, from which γ virtual leaders are chosen and linked by each data point. Furthermore, each data point is acted by all linked data points through fields established by them in space, so it will take a step along the direction of the vector sum of all fields. Thanks to those virtual leaders, they accelerate the rate of convergence of the algorithm. As all data points move in space according to the proposed model, data points that belong to the same class are located at a same position, whereas those that belong to other classes are away from one another. Consequently, the experimental results demonstrate that data points in datasets are clustered reasonably and efficiently, and in several iterations the convergence of the algorithm will be reached. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of proposed approach.