Generalization from Observed to Unobserved Features by Clustering

@article{citeulike:2587571, abstract = {We argue that when objects are characterized by many attributes, clustering them on the basis of a random subset of these attributes can capture information on the unobserved attributes as well. Moreover, we show that under mild technical conditions, clustering the objects on the basis of such a random subset performs almost as well as clustering with the full attribute set. We prove finite sample generalization theorems for this novel learning scheme that extends analogous results from the supervised learning setting. We use our framework to analyze generalization to unobserved features of two well-known clustering algorithms: k-means and the maximum likelihood multinomial mixture model. The scheme is demonstrated for collaborative filtering of users with movie ratings as attributes and document clustering with words as attributes.}, author = {Krupka, Eyal and Tishby, Naftali }, citeulike-article-id = {2587571}, journal = {Journal of Machine Learning Research}, keywords = {clustering, negative-features, unobserved-features}, month = {March}, pages = {339--370}, posted-at = {2008-06-02 10:31:33}, priority = {2}, title = {Generalization from Observed to Unobserved Features by Clustering}, url = {http://www.jmlr.org/papers/volume9/krupka08a/krupka08a.pdf}, volume = {9}, year = {2008} }

TY - JOUR ID - citeulike:2587571 L3 - citeulike-article-id:2587571 TI - Generalization from Observed to Unobserved Features by Clustering JF - Journal of Machine Learning Research VL - 9 SP - 339 EP - 370 N2 - We argue that when objects are characterized by many attributes, clustering them on the basis of a random subset of these attributes can capture information on the unobserved attributes as well. Moreover, we show that under mild technical conditions, clustering the objects on the basis of such a random subset performs almost as well as clustering with the full attribute set. We prove finite sample generalization theorems for this novel learning scheme that extends analogous results from the supervised learning setting. We use our framework to analyze generalization to unobserved features of two well-known clustering algorithms: k-means and the maximum likelihood multinomial mixture model. The scheme is demonstrated for collaborative filtering of users with movie ratings as attributes and document clustering with words as attributes. KW - clustering KW - negative-features KW - unobserved-features AU - Krupka, Eyal AU - Tishby, Naftali PY - 2008/03// UR - http://www.jmlr.org/papers/volume9/krupka08a/krupka08a.pdf ER -