Ant-based Constrained Clustering And Classification

Inspired by nature, ant-based unsupervised clustering are successful in dealing with many clustering problem. The potential which swarm intelligence approach reflected in data analysis attracts a large number of researchers. Previous studies have focused on the improvement in the performance of the algorithms, proof of the convergence, function optimization, combinatorial optimization and other aspects. In this context, in this paper we creatively use the idea of swarm intelligence for data mining and enrich the swarm intelligence applications. There are two categories of semi-supervised information:first, a small number of data points to be marked; the second is a small number of data points to be constrained by must-link and cannot-link constraints. For these two categories, ant constrained clustering we proposed, extends the ability to deal with a priori information to the framework of the ant clustering algorithm, at the same time we also invent a new transductive learning model the ants transductive learning.Clustering analysis is a very important tool of data mining and in the field of machine learning it is considered as unsupervised learning strategy. Constrained clustering and transductive learning mainly deal with learning problems between unsupervised learning and supervised learning. In the real world, accessing to raw data is much cheaper, but trying to get the information related to the class or category or the correlation between data points tends to be costly. Using the small amount of a priori information to improve the clustering result is an urgent need. Usually, such problems are also known as semi-supervised learning. Semi-supervised learning problems play a good role in dealing with the real world problem. In the academic community it is also attracting a large number of scholars’attention. Comparing with supervised learning it is more cost-saving and comparing with the unsupervised learning strategy it can improve the considerable learning accuracy.The specific contribution of this paper is as follows:1) Ant constrained clustering. For semi-supervised information appearing as constraints, we extend the ants sleeping model to be able to handle must-link, and can not-link constraint information. Taking maximum and minimum strategy, according to the must-link and can not-link constraints to limit correction data points similarity matrix we propose a simple ant constraint clustering method. Also by introducing the attractors and repellers deal with constraints, we propose a limited moving ant constrained clustering method.2) Heuristic ants clustering algorithm and its constrained clustering problem promotion. We expand and improve the RWAC algorithm. Before ants random walking on the grid, they perform heuristic walk strategy first. Using the idea of the nearest and farthest neighbor heuristic walk strategy and combining with the constrained information, the speed and accuracy of clustering are excellent, meanwhile the algorithm can be extended to handle constraints clustering easily.3) Ant transductive learning. The a priori information appearing as a small amount of labeled data points, we propose a new ant transductive learning framework. A number of ants assigned on each data vertex perform self-avoiding random walk on the undirected complete graph consisting of data points. If the ant arrives at a labeled vertex, it will stop to update the label vector. The task of transductive learning can be completed by the collaboration of multiple ants.