Sort-Merge Feature Selection for Video Data
Yan Liu, John R. Kender · 2003
Applying existing feature selection algorithms to video classification is impractical. A novel algorithm called Basic Sort-Merge Tree (BSMT) is proposed to choose a very small subset of features for video classification in linear time in the number of features. We reduce the cardinality of the input data by sorting the individual features by their effectiveness in categorization, and then merging pairwise these features into feature sets of cardinality two. Repeating this Sort-Merge process several times results in the learning of a small-cardinality, efficient, but highly accurate feature set. As the wrapper model, this paper exploits a novel combination of Fastmap for dimensionality reduction and Mahalanobis distance for likelihood determination. The time complexity of this induction part is linear in the number of training data. We provide theoretical proof of time cost and empirical validation of the accuracy.