US6654743B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Robust clustering of web documents
Assignee: Xerox Corp
•
Filing: 2000-11-13
•
Granted: 2003-11-25
•
Expires: 2020-11-13
Abstract
Abstract A method and apparatus for clustering documents from a set of documents includes issuing a request from an electronic device for documents which are relevant to the request. The documents believed to meet the request requirements are identified and the documents are thereafter supplied to a document clustering system. The document clustering system forms clusters of the documents by operation of the clustering system. A robustness criterion, by analogy with self-assembled physical systems, is applied to select the best, most robust, clustering. Robust clusters have a higher designability feature than other clusters which are generated where designability refers to a number of ways a particular cluster can be formed.
Inventors
- 👤 Tad H. Hogg
- 👤 Rajan M. Lukose
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 11:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/355; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
155 words
A method for clustering documents from a set of documents, comprising the steps of: (a) issuing a request from an electronic device for documents which are relevant to the request; (b) identifying documents intended to meet the request; (c) supplying the documents to a document clustering system; (d) forming a clustering of the documents by operation of the clustering system; (e) repeating steps c and d for a predetermined number of repetitions, using systematic variation in supplying the documents to the document clustering system and in clustering the supplied documents, wherein using the systematic variation in supplying and clustering documents include at least one of presenting the documents in different orders through statistical sampling, applying different clustering algorithms and using different similarity metrics; (f) identifying clusterings formed by operation of steps c, d, and e, including a frequency with which each clustering occurs; and (g) selecting a robust clustering based on the frequency of occurrence.
Claim 2
Independent Claim
155 words
A method for clustering documents from a set of documents, comprising the steps of: (a) issuing a request from an electronic device for documents which are relevant to the request; (b) identifying documents intended to meet the request; (c) supplying the documents to a document clustering system; (d) forming a clustering of the documents by operation of the clustering system; (e) repeating steps c and d for a predetermined number of repetitions, using systematic variation in supplying the documents to the document clustering system and in clustering the supplied documents, wherein using the systematic variation in supplying and clustering documents include at least one of presenting the documents in different orders through statistical sampling, applying different clustering algorithms and using different similarity metrics; (f) identifying clusterings formed by operation of steps c, d, and e, including a frequency with which each clustering occurs; and (g) selecting a robust clustering based on the frequency of occurrence.
Claim 3
Dependent Claim
17 words
The method according to claim 1 wherein the robust clustering is one that is formed most often.
Claim 4
Dependent Claim
27 words
The method according to claim 1 wherein identifying how often a cluster occurs includes a step of generating a histogram of the clusterings produced by the repetition.
Claim 5
Dependent Claim
38 words
The method according to claim 1 wherein using systematic variation in supplying and clustering documents include at least one of presenting the documents in different orders through statistical sampling, applying different clustering algorithms and using different similarity metrics.
Claim 6
Dependent Claim
18 words
The method according to claim 1 wherein the document clustering system includes a plurality of document clustering systems.
Claim 7
Dependent Claim
22 words
The method according to claim 1 wherein the repeating step, includes applying a varying order of the documents to the clustering system.
Claim 8
Dependent Claim
27 words
The method according to claim 1 wherein the step of forming clusters includes organizing the individual documents of the set of documents based on a similarity measure.
Claim 9
Dependent Claim
14 words
The method according to claim 1 wherein designability defines a robustness of the cluster.
Claim 10
Dependent Claim
21 words
The method according to claim 6 , wherein designability refers to a number of ways a particular cluster can be formed.
Claim 11
Dependent Claim
18 words
The method according to claim 1 further including a step of displaying the robust cluster to a user.
Claim 12
Independent Claim
146 words
A method for clustering documents from a set of documents, comprising the steps of: (a) issuing a request from an electronic device for documents which are relevant to the request; (b) identifying documents intended to meet the request; (c) supplying the documents to a document clustering system; (d) forming clusterings of the documents by operation of the clustering system, the supplying and forming steps using systematic variation in the supplying of the documents to the document clustering system, and the forming of the clusterings of the documents, wherein using the systematic variation in supplying and clustering documents include at least one of presenting the documents in different orders through statistical sampling, applying different clustering algorithms and using different similarity metrics; (e) performing processing operations on the clusterings formed by operation of the clustering system; and (f) selecting a robust clustering through operation of the performing step.
Claim 13
Independent Claim
146 words
A method for clustering documents from a set of documents, comprising the steps of: (a) issuing a request from an electronic device for documents which are relevant to the request; (b) identifying documents intended to meet the request; (c) supplying the documents to a document clustering system; (d) forming clusterings of the documents by operation of the clustering system, the supplying and forming steps using systematic variation in the supplying of the documents to the document clustering system, and the forming of the clusterings of the documents, wherein using the systematic variation in supplying and clustering documents include at least one of presenting the documents in different orders through statistical sampling, applying different clustering algorithms and using different similarity metrics; (e) performing processing operations on the clusterings formed by operation of the clustering system; and (f) selecting a robust clustering through operation of the performing step.
Claim 14
Dependent Claim
23 words
The method according to claim 11 wherein the step of performing processing operations includes a step of generating a histogram of the clusterings.
Claim 15
Dependent Claim
18 words
The method according to claim 11 wherein the document clustering system includes a plurality of document clustering systems.
Claim 16
Dependent Claim
26 words
The method according to claim 11 wherein the step of forming clusters includes organizing individual documents of the set of documents based on a similarity measure.
Claim 17
Dependent Claim
20 words
The method according to claim 11 , wherein the greater a designability of a cluster, the more robust the cluster.
Claim 18
Dependent Claim
15 words
The method according to claim 15 , wherein designability defines a robustness of the cluster.
Claim 19
Dependent Claim
18 words
The method according to claim 11 further including a step of displaying the robust cluster to a user.
Claim 20
Dependent Claim
17 words
The method according to claim 11 wherein the robust clustering is one that is formed most often.
Claim 21
Independent Claim
108 words
An apparatus for generating a robust cluster from a set of electronic documents comprising: a clustering system designed to receive a set of documents and to form clusterings of documents from the set, the clustering mechanism designed to provide documents and to perform a plurality of clustering operations using a systematic variation, the using of the systematic variation in supplying and clustering documents including at least one of presenting the documents in different order through statistical sampling, applying different clustering algorithms and using different similarity metrics; and a robust cluster mechanism designed to receive the clusterings and perform self-assembly processing operations to select at least one robust clustering.
Claim 22
Independent Claim
108 words
An apparatus for generating a robust cluster from a set of electronic documents comprising: a clustering system designed to receive a set of documents and to form clusterings of documents from the set, the clustering mechanism designed to provide documents and to perform a plurality of clustering operations using a systematic variation, the using of the systematic variation in supplying and clustering documents including at least one of presenting the documents in different order through statistical sampling, applying different clustering algorithms and using different similarity metrics; and a robust cluster mechanism designed to receive the clusterings and perform self-assembly processing operations to select at least one robust clustering.
Claim 23
Dependent Claim
19 words
The method according to claim 19 wherein the greater a designability of a cluster, the more robust the cluster.
Claim 24
Dependent Claim
21 words
The method according to claim 19 , wherein designability refers to a number of ways a particular cluster can be formed.
References Cited (Backward Citations)
US5864845A
Cited
US5857179A
Cited
US5924105A
Cited
US6078913A
Cited
US5895471A
Cited
US6363379B1
Cited
US6115708A
Cited
US6038574A
Cited
US6119124A
Cited
US6098064A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-11-24 | 2007-05-26 | 2007-11-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-11-24 | 2011-05-26 | 2011-11-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-11-24 | 2015-05-26 | 2015-11-25 | $7700.00 | Window Closed / Lapsed |