Model selection in machine learning with applications to document clustering

Abstract

A objective function based on a Bayesian statistical estimation framework is used to determine an optimal model selection by choosing both the optimal number of clusters and the optimal feature set. Heuristics can be applied to find the optimal (or at least sub-optimal) of this objective function in terms of the feature sets and the number of clusters, wherein the maximization of the objective function corresponds to the optimal model structure.

What is claimed is:  
     
       1. A computer-based method for optimal clustering of data, said data retained with computer storage, said method comprising the steps: 
       tokenizing a data set;  
       identifying unique tokens in said tokenized data set;  
       performing distributional clustering of said unique tokens to reduce noise and useful search space and identifying one or more subsets of said unique tokens;  
       selecting said identified one or more subsets and calculating an objective function value for each of said selected subsets, said calculation based upon varying number of clusters over a predetermined range, and for each number of clusters, cluster said data by a clustering algorithm to form data clusters;  
       choosing among said subsets the one that maximizes said objective function value, and  
       wherein an optimal model for clustering said data is obtained by simultaneously determining optimal values for: the number of clusters, the token subset, and the data clusters, whereby said optimal values taken together, maximizes said objective function value.  
     
     
       2. A computer-based method for optimal clustering of data, said data retained with computer storage, as per  claim 1 , wherein said data set comprises a collection of documents, said documents retained locally or remotely in computer storage. 
     
     
       3. A computer-based method for optimal clustering of data, said data retained with computer storage, as per  claim 1 , wherein said data set is a voice or image data set, said voice or image data set stored locally or remotely in computer storage. 
     
     
       4. A computer-based method for optimal clustering of data, said data retained with computer storage, as per  claim 3 , wherein said data stored remotely includes data stored across networks. 
     
     
       5. A computer-based method for optimal clustering of data, said data retained with computer storage, as per  claim 4 , wherein said networks include Internet, LANs, or Web-based networks. 
     
     
       6. A computer-based method for optimal clustering of data, said data retained with computer storage, as per  claim 1 , wherein said step of selecting a subset of tokens comprises: 
       computing the number of documents which each said token appears in, and  
       performing estimations of clusters using a relative entropy distance measure.  
     
     
       7. A computer-based method of selecting a model for optimal clustering of data, said data retained with computer storage, as per  claim 1 , wherein said step of identifying unique tokens is implemented via a distributed clustering heuristic method. 
     
     
       8. A computer-based method of selecting a model for optimal clustering of data, said data retained with computer storage, as per  claim 7 , wherein said distributed heuristic clustering heuristic method is based on non-parametric density estimation. 
     
     
       9. A computer-based method of selecting a model for optimal clustering of data, said data retained with computer storage, as per  claim 1 , wherein said objective function is a Bayesian function. 
     
     
       10. A computer-based method of selecting a model for unsupervised learning comprising the steps: 
       generating a list of features within a data set;  
       selecting a plurality of subsets of said list of features; for each of said plurality of subsets, performing the following steps:  
       performing clustering of data sets;  
       evaluating an objective function, wherein said objective function depends on both one of said plurality of subsets and a result of clustering based on said one subset, and  
       identifying an optimal subset of said plurality of subsets which maximizes said objective function.  
     
     
       11. A computer-based method of selecting a model for unsupervised learning, as per  claim 10 , wherein said selecting a plurality of subsets of said list of features further comprises the steps: 
       for each feature in said list of features, computing a density estimation within said data list;  
       clustering said density estimation, and  
       wherein a resulting number of clusters is much smaller than a cardinality of said list of features.  
     
     
       12. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, said system comprising: 
       a tokenizer to identify a list of features within said electronic documents;  
       a selector to select a plurality of subsets of said identified features;  
       a reducer to reduce said selected subsets based on a density estimation;  
       a cluster mechanism to cluster documents for each of said selected subsets;  
       a processing mechanism to evaluate a Bayesian function of said selected subsets, and  
       wherein a model for optimizing clustering of said electronic documents is based both on the number of clusters and the subsets selected. 
     
     
       13. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, as per  claim 12 , wherein said electronic documents are located on the world wide web and said model for optimizing clustering improves search results for an associated search engine. 
     
     
       14. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, as per  claim 12 , wherein said reducer implements a distributional clustering heuristic algorithm. 
     
     
       15. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, as per  claim 14 , wherein said distributed clustering heuristic algorithm is based on a non-parametric density estimation. 
     
     
       16. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, as per  claim 15 , wherein said non-parametric density estimation implements a computed histogram using a relative entropy algorithm. 
     
     
       17. A computer-based system for processing a collection of electronic documents, said electronic documents located local to said computer or located remotely across computer networks, as per  claim 16 , wherein said relative entropy algorithm comprises a K—L distance algorithm. 
     
     
       18. An article of manufacture comprising a computer useable medium having computer readable code embodied therein which selects a model for unsupervised learning, said computer readable code comprising: 
       computer readable program code generating a tokenized data set;  
       computer readable program code identifying all unique features or tokens in said tokenized data set;  
       computer readable program code selecting a subset of said tokens;  
       computer readable program code running an EM algorithm for each said selected subset;  
       computer readable program code calculating an objective function for each said selected subset, and  
       computer readable program code choosing among said subsets the one that optimizes the objective function.