On using tabu search for fuzzy clustering analysis

Yongguo Liu, Xindong Wu, Yi-Dong ShenScientific 2011 · DOI

TL;DR

This paper introduces the Improved Tabu Search Fuzzy Clustering (ITSFC) algorithm, a novel metaheuristic approach for fuzzy clustering. ITSFC combines a fuzzy c-means operation for faster convergence and a divide-and-merge operation to explore the solution space more effectively, outperforming existing tabu search and artificial bee colony methods on various datasets.

What Problem Does This Paper Address?

Clustering is a fundamental task in data analysis, aiming to group similar objects. However, real-world data often lacks clear boundaries between groups, making "hard" clustering (where each object belongs to exactly one cluster) insufficient. Fuzzy clustering addresses this by allowing objects to belong to multiple clusters with varying degrees of membership. While Fuzzy C-Means (FCM) is a popular fuzzy clustering algorithm, it's prone to getting stuck in local optima due to its sensitivity to initial cluster assignments. To overcome this, researchers have turned to metaheuristic techniques. This paper tackles the challenge of improving fuzzy clustering by developing a more robust and efficient tabu search-based algorithm that can better explore the complex solution space and avoid local optima.

Methods

The core contribution of this paper is the Improved Tabu Search Fuzzy Clustering (ITSFC) algorithm. ITSFC builds upon the tabu search metaheuristic by incorporating two key novel components:

  • Fuzzy c-means operation: This standard fuzzy clustering algorithm is integrated into ITSFC to "fine-tune" the current clustering solution. This helps to accelerate the convergence speed of the overall algorithm by leveraging domain knowledge within the clustering procedure.
  • Divide-and-merge operation: This is a novel neighborhood generation strategy. It modulates the distribution of objects among clusters by either:
  • Division: Splitting an existing cluster into two new ones.
  • Merger: Absorbing one cluster into another. This operation is designed to explore a wider range of potential solutions and establish a richer neighborhood for the tabu search to explore.

The overall ITSFC algorithm follows a general structure: Initialization, Fuzzy c-means operation, Divide-and-merge operation (to create neighbors), Update of the current solution (based on tabu list and aspiration criteria), Update of the tabu list, and Termination check.

Datasets

The paper evaluates ITSFC on a combination of artificial and real-world datasets:

  • Artificial Datasets:
    • Data-52 (N=250, d=2, c=5): 250 overlapping objects with 5 clusters.
  • Data-62 (N=300, d=2, c=6): 300 non-overlapping objects with 6 clusters.
  • Real-life Datasets:
    • Fisher's iris data set (N=150, d=4, c=3): A classic dataset with three species of iris flowers.
  • Wine data set (N=178, d=13, c=3): Chemical analysis of wines from three different cultivars.
  • Ripley's glass data set (N=214, d=9, c=6): Six types of glass with 9 features each.
  • Contraceptive method choice data set (N=1473, d=9, c=3): A subset of a survey predicting contraceptive method choice.

These datasets are standard benchmarks in clustering research.

Key Insights and Ideas

  • Synergy of Metaheuristics and Fuzzy Logic: The paper demonstrates that combining the exploration power of metaheuristics like tabu search with the nuanced representation of fuzzy logic can lead to superior clustering performance.
  • The Power of Neighborhood Exploration: The novel divide-and-merge operation is crucial. It allows ITSFC to systematically explore solutions by both splitting and merging clusters, providing a more comprehensive search than methods that solely rely on moving cluster centers.
  • Balancing Convergence and Exploration: The integration of the fuzzy c-means operation acts as a local search or refinement step, accelerating convergence, while the divide-and-merge operation ensures broader exploration, preventing premature convergence to suboptimal solutions.
  • Robustness to Initialization: By employing metaheuristics, ITSFC is less sensitive to the initial placement of cluster centers compared to standard FCM, leading to more consistent and reliable results.

Key Results

The experimental results, summarized in Table 1 and Figure 2, highlight the effectiveness of ITSFC:

  • Superior Objective Function Values: ITSFC consistently achieved lower average objective function values across all tested datasets compared to the standard Tabu Search Fuzzy Clustering (TSFC) and Artificial Bee Colony Fuzzy Clustering (ABC-FC) algorithms. The standard deviation values were also significantly lower, indicating greater stability and consistency.
  • Faster Convergence (for Real-world Data): While the ABC-FC algorithm showed faster initial convergence, ITSFC demonstrated better overall convergence speed and achieved better results for Data-52, Data-62, and Iris datasets. For real-life datasets, ITSFC provided lower objective function values sooner than TSFC as the number of objects increased.
  • Trade-off in Run Time: Table 2 shows that while ABC-FC was the fastest, it did not produce meaningful clustering results. ITSFC generally took longer than TSFC for artificial datasets but provided better results. For real-life datasets, ITSFC's improved performance came with a higher run time compared to TSFC.

Limitations and Future Work

The authors acknowledge a key limitation:

  • Requires Pre-defined Number of Clusters: The ITSFC algorithm, like many clustering methods, requires the user to specify the number of clusters (c) as an input. This is a challenge in real-world scenarios where the number of clusters is often unknown a priori.

Future research directions suggested by the authors include:

  • Automatic Cluster Number Evolution: Developing methods to automatically determine or evolve the optimal number of clusters during the clustering process.
  • Neighboring Solutions with Varying Cluster Numbers: Exploring how to generate neighboring solutions that dynamically adjust the number of clusters.
  • Accurate Fuzzy Partition Quality Metrics: Investigating more sophisticated criteria to quantitatively measure the quality of the fuzzy partition obtained.
  • Balancing Fuzzy C-Means and Divide-and-Merge: Further optimizing the balance between the fuzzy c-means operation and the divide-and-merge operation to enhance convergence speed.

Summary updated

Abstract

Clustering is an important technique for discovering the inherent structure in a given data set without any ‘priori’ knowledge. Fuzzy clustering analysis is to assign objects to a given number of clusters with respect to some criteria such that each object may belong to more than one cluster with different degrees of membership. In this article, a new fuzzy clustering method based on tabu search called Improved Tabu Search Fuzzy Clustering (ITSFC) is proposed to find the proper clustering of data sets. In the ITSFC approach, a fuzzy c-means operation is developed to fine-tune the clustering solution obtained in the process of iterations and a divide-and-merge operation is designed to establish the neighborhood. Experimental results on two artificial and four real life data sets are given to illustrate the superiority of the proposed algorithm over a tabu search clustering algorithm and an artificial bee colony clustering algorithm.   Key words: Fuzzy clustering, tabu search, artificial bee colony.
BibTeX
@inproceedings{liu2011using,
  author = {Yongguo Liu and Xindong Wu and Yi-Dong Shen},
  title = {{On using tabu search for fuzzy clustering analysis}},
  booktitle = {Scientific},
  year = {2011},
  doi = {10.5897/sre11.523},
}
Figure