Feature selection for robust knowledge discovery from data.

摘要

Modern information systems provide the ability to record, store, retrieve, and transmit massive amounts of data, and indeed, such systems have become a routine part of daily life for many people. While computers are adept at handling information, it has long been the goal of the knowledge discovery from data (KDD) community to enable computers to extract meaningful knowledge from this information – knowledge that would be otherwise lost to humans in the sheer volume of data. Feature selection techniques are often used in this discovery process to help combat the “curse of dimensionality,'' or the tremendous sample requirements that occur with high-dimensional data. Traditional feature selection algorithms only considered data sets with many available samples, and where the distribution of samples is assumed to accurately represent the entire population (an unbiased sample set). There are many situations where these assumptions do not hold, causing existing feature selection techniques to break down and in turn prevent automated KDD processes from being used. Each of these situations presents their own unique challenges to feature selection. In this dissertation, I analyze these challenges and develop feature selection algorithms that can perform robustly – specifically on small sample-size problems and in domains where biased data is unavoidable. In small sample-size data, results show that traditional feature selection algorithms produce unstable selected subsets, that is, subset membership will change with perturbations to the sample set. This reduces confidence that the selected subsets are truly relevant to the learning target and casts doubts on any extracted knowledge. Using traditional feature selection techniques in biased data will lead to heavily biased models that are not informative with respect to the entire problem. In dynamic situations where biased data is encountered, such as in reinforcement learning, this can prevent learning from proceeding at all, breaking the KDD process. In this dissertation, I present several techniques for overcoming these issues and demonstrate their effectiveness on diverse applications. Furthermore, I show that methods we developed can significantly outperform state-of-the-art feature selection algorithms in each application.