Generalization from Observed to Unobserved Features by Clustering

摘要

We argue that when objects are characterized by many attributes, clusteringthem on the basis of a random subset of these attributes cancapture information on the unobserved attributes as well. Moreover,we show that under mild technical conditions, clustering the objectson the basis of such a random subset performs almost as well as clusteringwith the full attribute set. We prove finite sample generalizationtheorems for this novel learning scheme that extends analogous resultsfrom the supervised learning setting. We use our framework to analyzegeneralization to unobserved features of two well-known clusteringalgorithms: k-means and the maximum likelihood multinomial mixturemodel. The scheme is demonstrated for collaborative filtering of userswith movie ratings as attributes and document clustering with wordsas attributes. color="gray">