Extraction methods for uncertain inference rules by ant colony optimization

Ling Chen, Yun Sun, Yuanguo ZhuJournal of Uncertainty Analysis and Applications 2015 · DOI

Abstract

In recent years, the research on data mining methods has received increasing attention. In this paper, we design an uncertain system with the extracted uncertain inference rules to solve the classification problems in data mining. And then, two extraction methods integrated with ant colony optimization are proposed for the generation of the uncertain inference rules. Finally, two applications are given to verify the effectiveness and superiority of the proposed methods.

Introduction

In the field of data mining, the extraction of interpretable "if-then" rules is a cornerstone for creating transparent decision-making models. While traditional methods often rely on probability theory, they can struggle when data is scarce or when expert "belief degrees" are more relevant than frequentist distributions. This paper, published in the Journal of Uncertainty Analysis and Applications, introduces a framework based on Uncertainty Theory to handle subjective indeterminacy. To automate the discovery of these rules, the authors propose two novel methods integrating Ant Colony Optimization (ACO) with local search heuristics.

The Uncertain Inference System

The proposed system is structured into five functional components: inputs, a rule-base, an inference engine, an expected value operator, and outputs. Unlike fuzzy systems that rely on membership functions derived from probability, this system utilizes uncertain sets to represent linguistic variables (e.g., "low," "medium," "high"). The goal is to find a set of rules that maximizes classification accuracy while maintaining model parsimony.

Proposed ACO Hybrid Methods

To navigate the complex search space of potential rule sets, the authors developed two hybrid algorithms designed to overcome the "stagnation" problem common in standard ACO, where ants converge prematurely on sub-optimal solutions.

  1. ACO with Mutation (Method A): This approach introduces a stochastic mutation operator. After an ant constructs a rule, the rule is subjected to random perturbations. If the mutated rule yields better performance, it replaces the original, ensuring continuous exploration of the search space.
  2. ACO with Simulated Annealing (Method B): This method integrates Simulated Annealing (SA) as a local search mechanism. By allowing the algorithm to occasionally accept inferior solutions based on a "temperature" parameter that cools over time, Method B can escape local optima more effectively than simple mutation, leading to more stable and globally optimal rule sets.

Experimental Results

The effectiveness of these methods was evaluated using two benchmark datasets: the IRIS dataset (150 instances, 4 attributes) and the Wisconsin Breast Cancer (WBC) dataset (699 instances, 9 attributes).

  • IRIS Classification: Method B achieved a peak accuracy of 97.5%, surpassing the standard C4.5 decision tree (94.0%) and other ACO variants like MACO (95.53%). Remarkably, the system achieved this with only 7 rules.
  • WBC Classification: Method A demonstrated superior performance on this larger dataset, reaching 98.37% accuracy. This outperformed both C4.5 (94.25%) and the Fuzzy Min-Max (FMM) network (97.86%).

The results indicate that while Method A (Mutation) often converges faster, Method B (Simulated Annealing) provides a more robust search for the absolute best configuration in smaller, more sensitive datasets.

Conclusion

By combining the logical rigor of Uncertainty Theory with the global search capabilities of hybrid Ant Colony Optimization, the authors have provided a powerful tool for interpretable data mining. These methods not only match or exceed the accuracy of traditional "black-box" or frequentist models but also produce rules that align closely with human reasoning. Future research will focus on extending these uncertain inference rules to regression tasks and testing their scalability on larger, high-dimensional datasets.

Summary updated

Abstract

Abstract In recent years, the research on data mining methods has received increasing attention. In this paper, we design an uncertain system with the extracted uncertain inference rules to solve the classification problems in data mining. And then, two extraction methods integrated with ant colony optimization are proposed for the generation of the uncertain inference rules. Finally, two applications are given to verify the effectiveness and superiority of the proposed methods.
BibTeX
@article{chen2015extraction,
  author = {Ling Chen and Yun Sun and Yuanguo Zhu},
  title = {{Extraction methods for uncertain inference rules by ant colony optimization}},
  journal = {Journal of Uncertainty Analysis and Applications},
  year = {2015},
  doi = {10.1186/s40467-015-0033-9},
}
Figure