Automatic multi-objective clustering based on game theory

Data clustering is a very well studied problem in machine learning, data mining, and related disciplines. Most of the existing clustering methods have focused on optimizing a single clustering objective. Often, several recent disciplines such as robot team deployment, ad hoc networks, multi-agent systems, facility location, etc., need to consider multiple criteria, often conflicting, during clustering. Motivated by this, in this paper, we propose a sequential game theoretic approach for multi-objective clustering, called ClusSMOG-II. It is specially designed to optimize simultaneously intrinsically conflicting objectives, which are inter-cluster/intra-cluster inertia and connectivity. This technique has an advantage of keeping the number of clusters dynamic. The approach consists of three main steps. The first step sets initial clusters with their representatives, whereas the second step calculates the correct number of clusters by resolving a sequence of multi-objective multi-act sequential two-player games for conflict-clusters. Finally, the third step constructs homogenous clusters by resolving sequential two-player game between each cluster representative and the representative of its nearest neighbor. For each game, we define payoff functions that correspond to the model objectives. We use a methodology based on backward induction to calculate a pure Nash equilibrium for each game. Experimental results confirm the effectiveness of the proposed approach over state-of-the-art clustering algorithms.