Feature Selection for Unsupervised Learning
Journal of Machine Learning ResearchPublished 1 December 2004
Jennifer Dy, Carla E. Brodley
Citations890
SJR quartileQ1
SJR score2.02
SNIP3.07
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper explores the feature selection problem and issues through FSSEM (Feature Subset Selection using Expectation-Maximization (EM) clustering) and through two different performance criteria for evaluating candidate feature subsets: scatter separability and maximum likelihood.
Abstract
In this paper, we identify two issues involved in developing an automated feature subset selection algorithm for unlabeled data: the need for finding the number of clusters in conjunction with feature selection, and the need for normalizing the bias of feature selection criteria with respect to dimension. We explore the feature selection problem and these issues through FSSEM (Feature Subset Selection using Expectation-Maximization (EM) clustering) and through two different performance criteria for evaluating candidate feature subsets: scatter separability and maximum likelihood. We present proofs on the dimensionality biases of these feature criteria, and present a cross-projection normalization scheme that can be applied to any criterion to ameliorate these biases. Our experiments show the need for feature selection, the need for addressing these two issues, and the effectiveness of our proposed solutions.
Keywords
Computer Science
IEEE Transactions on Automatic ControlA new look at the statistical model identification
50,732 Citations1974Hirotugu Akaike
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Choice Reviews OnlineArtificial intelligence: a modern approach
22,205 Citations1995Stuart Russell, Peter Norvig +2 more
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
BiometricsApplied Multivariate Statistical Analysis.
11,424 Citations1988Andrea Johnson, Dean W. Wichern
Artificial IntelligenceWrappers for feature subset selection
8,925 Citations1997Ron Kohavi, George H. John
The wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain and compares the wrapper approach to induction without feature subset selection and to Relief, a filter approach tofeature subset selection.
Cambridge University Press eBooksPattern Recognition and Neural Networks
6,468 Citations1996B. D. Ripley
TechnometricsThe EM Algorithm and Extensions
5,108 Citations1998Debashis Kushary, Geoffrey J. McLachlan +1 more
Journal of the American Statistical AssociationModel-Based Clustering, Discriminant Analysis, and Density Estimation
4,282 Citations2002Chris Fraley, Adrian E. Raftery
This work reviews a general methodology for model-based clustering that provides a principled statistical approach to important practical questions that arise in cluster analysis, such as how many clusters are there, which clustering method should be used, and how should outliers be handled.
The Annals of StatisticsOn the Convergence Properties of the EM Algorithm
3,252 Citations1983Changbao Wu
IEEE Signal Processing MagazineThe expectation-maximization algorithm
3,138 Citations1996Todd K. Moon
The EM (expectation-maximization) algorithm is ideally suited to problems of parameter estimation, in that it produces maximum-likelihood (ML) estimates of parameters when there is a many-to-one mapping from an underlying distribution to the distribution governing the observation.
Elsevier eBooksA Practical Approach to Feature Selection
2,954 Citations1992Kenji Kira, Larry Rendell
Comparison with other feature selection algorithms shows Relief's advantages in terms of learning time and the accuracy of the learned concept, suggesting Relief's practicality.
Lecture notes in computer scienceEstimating attributes: Analysis and extensions of RELIEF
2,950 Citations1994Igor Kononenko
In the context of machine learning from examples this paper deals with the problem of estimating the quality of attributes with and without dependencies among them and is analysed and extended to deal with noisy, incomplete, and multi-class data sets.
Journal of the American Statistical AssociationStatistical Analysis of Finite Mixture Distributions.
2,940 Citations1987Bruce G. Lindsay, D. M. Titterington +2 more
Automatic subspace clustering of high dimensional data for data mining applications
2,386 Citations1998Rakesh Agrawal, Johannes Gehrke +2 more
CLIQUE is presented, a clustering algorithm that satisfies each of these requirements of data mining applications including the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records.
Elsevier eBooksIrrelevant Features and the Subset Selection Problem
2,374 Citations1994George H. John, Ron Kohavi +1 more
A method for feature subset selection using cross-validation that is applicable to any induction algorithm is described, and experiments conducted with ID3 and C4.5 on artificial and real datasets are discussed.
X-means: Extending K-means with Efficient Estimation of the Number of Clusters
2,162 Citations2000Dan Pelleg, Andrew Moore
A new algorithm is introduced that eeciently, searches the space of cluster locations and number of clusters to optimize the Bayesian Information Criterion (BIC) or the Akaike Information Criteria (AIC) measure.
IEEE Transactions on Pattern Analysis and Machine IntelligenceUnsupervised learning of finite mixture models
2,110 Citations2002Mário A. T. Figueiredo, Anil K. Jain
The novelty of the approach is that it does not use a model selection criterion to choose one among a set of preestimated candidate models; instead, it seamlessly integrate estimation and model selection in a single algorithm.
Queensland's institutional digital repository (The University of Queensland)Mixture models : inference and applications to clustering
2,074 Citations1988Geoffrey J. McLachlan, K. E. Basford
Neural ComputationMixtures of Probabilistic Principal Component Analyzers
1,903 Citations1999Michael E. Tipping, Chris Bishop
PCA is formulated within a maximum likelihood framework, based on a specific form of gaussian latent variable model, which leads to a well-defined mixture model for probabilistic principal component analyzers, whose parameters can be determined using an expectation-maximization algorithm.
Machine LearningKnowledge Acquisition Via Incremental Conceptual Clustering
1,754 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
The Annals of StatisticsA Universal Prior for Integers and Estimation by Minimum Description Length
1,667 Citations1983J. Rissanen
Estimation based upon the principle of minimizing the total number of binary digits required to rewrite the observed data, when each observation is given with some precision is studied.
IEEE Transactions on ComputersA Branch and Bound Algorithm for Feature Subset Selection
1,240 Citations1977Narendra, Fukunaga
A feature subset selection algorithm based on branch and bound techniques is developed to select the best subset of m features from an n-feature set with the computational effort of evaluating only 6000 subsets.
Survey on Independent Component Analysis
1,122 Citations1999Aapo Hyvärinen
This paper surveys the existing theory and methods for independent component analysis (ICA), in which the desired representation is the one that minimizes the statistical dependence of the components of the representation.
Refining Initial Points for K-Means Clustering
999 Citations1998Paul S. Bradley, Usama M. Fayyad
A procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution that allows the iterative algorithm to converge to a “better” local minimum.
Bayesian classification (AutoClass): theory and results
972 Citations1996Peter Cheeseman, John Stutz
It is emphasized that no current unsupervised classi(cid:12)cation system can produce maximally useful results when operated alone, and that it is the interaction between domain experts and the machine searching over the model space, that generates new knowledge.
Journal of the American Statistical AssociationExploratory Projection Pursuit
789 Citations1987Jerome H. Friedman
A new projection pursuit algorithm for exploring multivariate data is presented that has both statistical and computational advantages over previous methods and the emphasis here is on the discovery of nonlinear effects such as clustering or other general nonlinear associations among the variables.
Neural ComputationDimension Reduction by Local Principal Component Analysis
723 Citations1997Nandakishore Kambhatla, Todd K. Leen
A local linear approach to dimension reduction that provides accurate representations and is fast to compute is developed and it is shown that the local linear techniques outperform neural network implementations.
IEEE Transactions on Information TheoryOn the effectiveness of receptors in recognition systems
655 Citations1963Thomas Marill, D. Green
Some of the theoretical problems encountered in trying to determine a more formal measure of the effectiveness of a set of tests are discussed; a measure which might be a practical substitute for the empirical evaluation.
National Conference on Artificial IntelligenceLearning with many irrelevant features
611 Citations1991Hussein Almuallim, Thomas G. Dietterich
It is demonstrated that CaS protects against oxidative stress‐induced keratinocyte cell death in part through the activation of Nrf2‐mediated HO‐1 induction via the PI3K/Akt and/or PKC pathways, but not MAPK signaling.
Multivariate Behavioral ResearchPATTERN CLUSTERING BY MULTIVARIATE MIXTURE ANALYSIS
604 Citations1970J. H. Wolfe
The maximum-likelihood theory and numerical solution techniques are developed for a fairly general class of distributions and the feasibility of the procedures is demonstrated by two examples of computer solutions for normal mixture models of the Fisher Iris data and of artify generated clusters with unequal covariance matrices.
Scientific Repository (Petra Christian University)The EM algorithm for mixtures of factor analyzers
585 Citations1996Zoubin Ghahramani, GE Hinton
This work presents an exact Expectation{Maximization algorithm for determining the parameters of this mixture of factor analyzers which concurrently performs clustering and dimensionality reduction, and can be thought of as a reduced dimension mixture of Gaussians.
Elsevier eBooksGreedy Attribute Selection
541 Citations1994Rich Caruana, Dayne Freitag
Experiments suggest hillclimbing in attribute space can yield substantial improvements in generalization performance, and a caching scheme is presented that makes attribute hillClimbing more practical computationally.
Models of Incremental Concept Formation
527 Citations1988John H. Gennari, Pat Langley +1 more
Journal of the Royal Statistical Society Series B (Statistical Methodology)Clustering Objects on Subsets of Attributes (with Discussion)
427 Citations2004Jerome H. Friedman, Jacqueline J. Meulman
A new procedure is proposed for clustering attribute value data that encourages those algorithms to detect automatically subgroups of objects that preferentially cluster on subsets of the attribute variables rather than on all of them simultaneously.
Neural ComputationSMEM Algorithm for Mixture Models
411 Citations2000Naonori Ueda, Ryohei Nakano +2 more
A split-and-merge expectation-maximization algorithm to overcome the local maxima problem in parameter estimation of finite mixture models and is applied to the training of gaussian mixtures and mixtures of factor analyzers and shows the practical usefulness by applying it to image compression and pattern recognition problems.
PsychometrikaA Monte Carlo Study of Thirty Internal Criterion Measures for Cluster Analysis
410 Citations1981Glenn W. Milligan
Results indicated that a subset of internal criterion measures could be identified which appear to be valid indices of correct cluster recovery and could form the basis of a permutation test for the existence of cluster structure or a clustering algorithm.
Variational Inference for Bayesian Mixtures of Factor Analysers
380 Citations1999Zoubin Ghahramani, Matthew J. Beal
An algorithm is presented that infers the model structure of a mixture of factor analysers using an efficient and deterministic variational approximation to full Bayesian integration over model parameters and shows how to obtain unbiased estimates of the true evidence, the exact predictive density, and the KL divergence between the variational posterior and the true posterior.
Journal of the Royal Statistical Society Series C (Applied Statistics)On Using Principal Components Before Separating a Mixture of Two Multivariate Normal Distributions
308 Citations1983Wei-Chien Chang
IEEE Transactions on Pattern Analysis and Machine IntelligenceUnsupervised feature selection applied to content-based retrieval of lung images
253 Citations2003Jennifer Dy, Carla E. Brodley +3 more
The results show that the system using CQA retrieval doubled the doctors' diagnostic accuracy and developed a new algorithm called FSSEM (feature subset selection using expectation-maximization clustering), which radically improves the retrieval precision over the single feature vector approach.
Elsevier eBooksUsing Decision Trees to Improve Case-Based Learning
252 Citations1993Claire Cardie
Results clearly indicate that decision trees can be used to improve the performance of CBL systems and do so without reliance on potentially expensive expert knowledge.
Feature Subset Selection and Order Identification for Unsupervised Learning
236 Citations2000Jennifer Dy, Carla E. Brodley
This paper examines feature subset selection wrapped around expectation-maximization (EM) clustering with order identi cation (identifying the number of clusters in the data).
Journal of Artificial Intelligence ResearchIterative Optimization and Simplification of Hierarchical Clusterings
189 Citations1996Douglas Fisher
This work evaluates an inexpensive strategy for creating initial clusterings, coupled with several control strategies for iterative optimization, each of which repeatedly modifies an initial clustering in search of a better one.
Lecture notes in statisticsSearching for Dependencies in Bayesian Classifiers
187 Citations1996Michael J. Pazzani
It is shown that the backward sequential elimination and joining algorithm provides the most improvement over the naive Bayesian classifier and that the violations of the independence assumption that affect the accuracy of the classifier can be detected from training data.
Clustering using Monte Carlo cross-validation
174 Citations1996Padhraic Smyth
Experimental results with Gaussian mixtures on real and simulated data suggest that MCCV provides genuine insight into cluster structure, v-fold cross-validation appears inferior to the penalized likelihood method (BIC), a Bayesian algorithm (AutoClass v2.0), and the new MccV algorithm.
Initialization of iterative refinement clustering algorithms
153 Citations1998Usama M. Fayyad, Cory Reina +1 more
This work presents a procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution, and shows that refined initial points indeed lead to improved solutions.
Feature Selection for Case-Based Classification of Cloud Types: An Empirical Comparison
130 Citations1994David W. Aha, Richard L. Bankert
A set of such algorithms that use case-based classifiers, empirically compare them, and introduce novel extensions of backward sequential selection that allows it to scale to this task are described.
Efficient Feature Selection in Conceptual Clustering
116 Citations1997Mark Devaney, Ashwin Ram
An implementation of a sequential feature selection algorithm based on an existing conceptual clustering system is described and an implementation which employs a technique for improving the efficiency of the search for an optimal description is presented.
Intelligent Data AnalysisEvolutionary model selection in unsupervised learning
107 Citations2002YongSeog Kim, W. Nick Street +1 more
ELSA is used, an evolutionary local selection algorithm that maintains a diverse population of solutions that approximate the Pareto front in a multi-dimensional objective space and results in models with better and clearer semantic relevance.
Feature Selection as a Preprocessing Step for Hierarchical Clustering
91 Citations1999Luis Talavera
Empirical results suggest that feature selection as preprocessing only provides limited improvements in the performance task, and the problem of the notion of irrelevance in unsupervised settings is raised.
Oblivious Decision Trees and Abstract Cases
89 Citations1994Pat Langley, Stephanie Sage
A new algorithm is presented, OBLIVION, that carries out greedy pruning of oblivious decision trees, which effectively store a set of abstract cases in memory, and it is hypothesized that this approach will efficiently identify relevant features even when they interact, as in parity concepts.
Feature Selection in Mixture-Based Clustering
81 Citations2002M.H.C. Law, Anil K. Jain +1 more
Two approaches to feature selection in the context of Gaussian mixture-based clustering are proposed, one of which wraps mixture estimation in an outer layer that performs feature selection and the other extends Koller and Sahami's mutual-information-based feature relevance criterion to the unsupervised case.
Visualization and interactive feature selection for unsupervised data
65 Citations2000Jennifer Dy, Carla E. Brodley
This paper introduces Visual-FSSEM (Visual Feature Subset Selection using Expectation-Maximization Clustering), which incorporates visualization techniques, clustering, and user interaction to guide the feature subset search and to enable a deeper understanding of the data.
Machine LearningConcept Learning and Feature Selection Based on Square-Error Clustering
53 Citations1999Boris Mirkin
Based on a reinterpretation of the square-error criterion for classical clustering, a “separate-and-conquer” version of K-Means clustering is presented and a contribution weight is determined for each variable of every cluster.
Knowledge-Based SystemsDimensionality reduction via discretization
36 Citations1996Huan Liu, Rudy Setiono
A method that reduces data vertically and horizontally, keeps the discriminating power of the original data, and paves the way for extracting concepts from the raw data is introduced.
Elsevier eBooksA Comparison of Induction Algorithms for Selective and non-Selective Bayesian Classifiers
31 Citations1995Moninder Singh, Gregory Provan
This selective Bayesian network classifier selects a subset of attributes that maximizes predictive accuracy prior to the network learning phase, thereby learning Bayesian networks with a bias for small, high-predictive-accuracy networks.
The customized-queries approach to CBIR using EM
26 Citations2003Jennifer Dy, Carla E. Brodley +3 more
An approach called the "customized-queries" approach (CQA) to content-based image retrieval and an algorithm called FSSEM that performs feature selection and clustering simultaneously that radically improves the retrieval precision over the traditional approach that performs retrieval using a single feature vector.