ارزیابی ویژگی ها و انتخاب با تئوری بازی تعاونی

Recent years, various information theoretic based measurements have been proposed to remove redundant features from high-dimensional data set as many as possible. However, most traditional Information-theoretic based selectors will ignore some features which have strong discriminatory power as a group but are weak as individuals. To cope with this problem, this paper introduces a cooperative game theory based framework to evaluate the power of each feature. The power can be served as a metric of the importance of each feature according to the intricate and intrinsic interrelation among features. Then a general filter feature selection scheme is presented based on the introduced framework to handle the feature selection problem. To verify the effectiveness of our method, experimental comparisons with several other existing feature selection methods on fifteen UCI data sets are carried out using four typical classifiers. The results show that the proposed algorithm achieves better results than other methods in most cases.

Feature selection, also known as variable selection, is one of the fundamental problems in the fields of machine learning, pattern recognition and statistics. With the new emergences in computer applications, such as social networks clustering, gene expression array analysis and combinatorial chemistry, datasets with tens or hundreds of thousands of features are available. Nevertheless, most of the features in huge dataset are irrelevant or redundant, which lead learning algorithms to low efficiency and over-fitting. Thus, feature selection becomes one of the most active research areas to address this problem. The essential idea of feature selection is to eliminate the irrelevant and redundant features from data set as many as possible. Feature selection in machine learning has been well studied, aiming at finding a good feature subset which produces higher classification accuracy [1]. Also, it is helpful to acquire a better understanding of relationships among the features. Recently several researches have combined feature selection and classification together in various application area to improve the performance of machine learning, e.g., video semantic detection [2], text categorization [3], bioinformatics [4] and [5] and intrusion detection [6]. Up to present, several different approaches are employed in feature selection, such as genetic algorithm [7], simulated annealing [8], SVM [9] and boosting method [10]. Furthermore, all of these feature selection methods typically fall into three categories: embedded, wrapper and filter methods. Embedded methods are embedded in and specific to a given machine learning algorithm, and select the features through the process of generating the classifier. Wrappers, evaluating each subset by specified learning algorithms which were treated as a black box, can choose optimal features to yield high prediction performance. One drawback of the wrapper methods, however, is their less generalization of the selected features on other classifiers and high computational complexity in learning, because they are tightly coupled with specified learning algorithms. What's more, they may have a risk of over fitting to the algorithm. Consequently, wrapper methods can hardly deal with large scale problems. Filter methods are independent of learning algorithms. Instead, they rely on statistical tests over the original features of the training data. In practice, the filter methods have much lower computational complexity than the wrappers, meanwhile, they achieve comparable classification accuracy for most classifiers. Thus, the filter methods are very popular to high-dimension data set. To date, a modest number of efficient filter selection algorithms have been proposed in the literature. It is noteworthy that among various evaluation criterions, Information-theoretic based measurements achieve excellent performance and have drawn more and more attention. This is due to that such measurements capture both linear and nonlinear dependencies without requiring a theoretical probability distribution or specific model of dependency. However, most of these selectors discard features which are highly correlated to the selected ones although relevant to the target class, which is likely to ignore features which as a group have strong discriminatory power but are weak as individuals [11]. To untie this knot, this paper introduces a cooperative game theory based framework to evaluate the power of each feature. Then a general filter feature selection scheme is presented based on the introduced framework to handle the feature selection problem using any Information-theoretic criteria. The rest of this paper is structured as follows: In Section 2, related works are briefly reviewed. Section 3 introduces some basic concepts of information theory in feature selection and the necessary background of cooperative game theory. Section 4 provides a cooperative game theory-based framework to evaluate the power of each feature, and presents a general filter feature selection algorithm. Section 5 gives experimental results on UCI data sets to evaluate the effectiveness of our approach and some discussions. Conclusions and future work are presented in Section 6.

Feature selection plays an important role in machine learning and data mining. In this paper, we firstly introduce a cooperative game theory based framework to evaluate the power of each feature, in order to overcome the disadvantage that traditional Information-theoretic based selectors ignore some features which as a group have strong discriminatory power but are weak as individuals. The second objective of this paper is to propose a general filter feature selection scheme based on the introduced framework to handle the feature selection problem. In this scheme, many Information-theoretic based feature selection methods, such as BIF, MIFS, SU and mRMR, can be employed. Experimental results on fifteen UCI datasets show that the proposed method works well and outperforms mRMR, Relief and IG at most cases. Its proven efficiency and effectiveness compared with other algorithms by four classifiers suggest that CoFS is practical for feature selection of high-dimensional data.