Rough set approach to feature reduction in KDD: Evolutionary computing and data sampling.

摘要

We develop a framework for parallel computation of rough set decision reducts from data. We adapt the island model for evolutionary computing. The idea is to optimize reducts within separate populations (islands) and enable the best reducts-chromosomes to migrate among islands. Experiments show that the proposed method speeds up calculations and often provides better quality results compared to genetic algorithms applied to date to the feature reduction (aka feature selection or attribute reduction). We continue by extending our genetic algorithm framework onto dynamic reducts, based on random sampling of datasets. Decision rules generated from the best dynamic reducts proved to be stable and highly accurate classifiers. However, calculation of dynamic reducts and corresponding rules is even more expensive in regards of time and memory than in the case of classical rough set decision reducts. In parallel to improving the calculation speed, we investigate our own two extensions of dynamic reducts (called multi-reducts and dynamic semi-reducts), which can be easily optimized using hybrid, order-based genetic algorithms (OGAs). We evaluate our methods with KDD CUP 1999 datasets. The proposed extensions outperform the speed of conventional dynamic reduct calculation while preserving the quality of the resulting classifiers.