Improvements on searching relevant features and samples for pattern recognition

Abstract

This thesis focuses on the study of reducing the size of a dataset (a supervised dataset in most cases) without losing the information useful for fulfilling a pattern recognition task. In the study of this type, there are two aspects: pattern (set) reduction and feature (set) reduction. A method for pattern reduction is developed, in which the reduction criterion and the reduction procedure are totally novel. Using the concept of entropy, the proposed reduction criterion is able to evaluate a reduced pattern set from a comprehensive and sophisticated viewpoint. The proposed reduction algorithm explores a data domain in an efficient and controllable way. Also, with the merits of the newly developed criterion, respectable reduction results can be guaranteed. In the thesis, this algorithm is extensively evaluated from the perspectives of efficiency, effectiveness and robustness to initialization. As to feature selection, two probability-based feature selection schemes are firstly proposed. One is a mutual information based methodology. In the existing mutual information based feature selection techniques, all the mutual information estimation approaches cannot deliver the respectable results either in a high-dimensional data domain or when a given feature set has highly redundancy. These shortcomings inevitably degrade the performance of those feature selection schemes. In the proposed mutual information based scheme, using the quadratic mutual information and Parzen window probability density estimators, high-dimensional mutual information can be reliably estimated even when the pattern set is very small with respect of the feature set. Also, a new criterion is designed to address the problem of highly redundancy, with which the proposed feature selection scheme can avoid the redundant selected features in a systematic way. The other probability-based feature selection scheme introduced in this thesis is based on the concept of Bayesian discriminant. Using this concept, the proposed scheme enables the pattern recognition decision rule to be explicitly incorporated during the feature selection process. In this way, the performance of feature selection is improved. In this thesis, feature searching engine is also studied. Two strategies are developed to speed up a feature searching engine. In the first strategy, the basic idea is to coarsely eliminate the redundant features before salient features are determined in a fine way. This strategy is based on the concept of grid, and thus can be conducted in a very efficient way. Apparently, this strategy is extremely helpful for dealing with a huge and redundant feature set. The second strategy is a weighted type searching engine in which, through the weight operation, the feature searching is transferred from a discrete domain to a continuous one. In this thesis, a gradient-based algorithm is proposed to optimize a differentiated feature evaluation criterion and then evaluate all the features at the same time. With a high convergence rate and robustness to initialization, this algorithm has the respectable performance even in the cases with a huge feature set.

Date of Award	15 Feb 2005
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wai Shing Tommy CHOW (Supervisor)