SYSTEM AND METHOD FOR CLUSTERING DATA OBJECTS IN A COLLECTION

• US 20030110181A1
• Filed: 10/19/1999
• Published: 06/12/2003
• Est. Priority Date: 01/26/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: LI, JUN, CHI, ED H., PITKOW, JAMES E., PIROLLI, PETER L., SCHUETZE, HINRICH
• Granted Patent: US 6,598,054 B2
• Time in Patent Office: Days
• US Class Current: 707/103R
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for browsing, retrieving, and recommending information from a collection uses multi-modal features of the documents in the collection, as well as an analysis of users'"'"' prior browsing and retrieval behavior. The system and method are premised on various disclosed methods for quantitatively representing documents in a document collection as vectors in multi-dimensional vector spaces, quantitatively determining similarity between documents, and clustering documents according to those similarities. The system and method also rely on methods for quantitatively representing users in a user population, quantitatively determining similarity between users, clustering users according to those similarities, and visually representing clusters of users by analogy to clusters of documents.

Claims

1. A method for selecting a set of initial cluster centers in clustering a collection of objects in a multi-dimensional vector space, comprising the steps of:

selecting a first number of first objects from the collection;

computing a vector centroid of the first objects;

selecting a second number of second objects from the collection; and

identifying a second number of initial cluster centers between the centroid and the second objects.

2. The method of claim 1, wherein the first objects are selected randomly from the collection.

3. The method of claim 2, wherein the first number is much smaller than the number of objects in the collection.

4. The method of claim 3, wherein the first number is greater than five (5).

5. The method of claim 4, wherein the second number is ten (10).

6. The method of claim 1, wherein the second objects are selected randomly from the collection.

7. The method of claim 6, wherein the second number is equal to a desired number of initial cluster centers.

8. The method of claim 1, wherein each of the second number of initial cluster centers is calculated according to {right arrow over (x)}_i′

=α

{right arrow over (c)}+(1−

α

){right arrow over (x)}i, where {right arrow over (x)}_i′

represents an initial cluster center, α

represents a scalar factor, {right arrow over (x)}_i represents one of the second objects, and {right arrow over (c)} represents the vector centroid of the first objects.

9. The method of claim 8, wherein α

is approximately equal to 0.9.

10. A method for clustering a collection of objects in a multi-dimensional vector space, comprising the steps of:

selecting a first number of first objects from the collection;

computing a vector centroid of the first objects;

selecting a second number of second objects from the collection;

identifying a second number of initial cluster centers between the centroid and the second objects; and

performing iterated k-means clustering around the initial cluster centers to cluster the objects.