Method and apparatus for data clustering

• US 20020099702A1
• Filed: 01/19/2001
• Published: 07/25/2002
• Est. Priority Date: 01/19/2001
• Status: Abandoned Application

• Current Assignee: Sedna Patent Services LLC
• Original Assignee: Sedna Patent Services LLC
• Inventors: Oddo, Anthony Scott
• Application Number:
  US09/766,377
• Publication Number:
  US 20020099702A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

A method and apparatus are provided for clustering data inputs into groups. The first data input is initially designated as center of a first group. Each other data input is successively analyzed to identify a group whose center is sufficiently close to that data input. If such a group is identified, the input is assigned to the identified group. If no such group is identified, a new group is created and the data input is designated as the center of the new group. The analysis of data inputs is repeated until all data inputs have been assigned to groups. Optionally, thereafter for optimal performance, for each data input, the closest group center to that input is determined, and the data input is assigned to the group having that center.

Claims

1. A method for clustering a plurality of data inputs into groups, comprising:

(a) defining a match threshold;

(b) designating a first data input as center of a group;

(c) analyzing another data input to identify a group whose center has a proximity to the input that is above the match threshold, and if such a group is identified, assigning the data input to that group;

(d) if the data input has a proximity to the center of no group above the match threshold, creating a new group and designating said data input as center of the new group; and

(e) repeating steps (c) and (d) until all data inputs have been assigned to groups.

2. The method of claim 1 further comprising (f) identifying the closest group center to each data input and, and assigning the data input to the group having that center.

3. The method of claim 1 wherein each data input comprises an input vector.

4. The method of claim 1 wherein said match threshold specifies a maximum distance between a data input and a group center.

5. The method of claim 1 wherein identifying a group center closest to an input comprises calculating the distance between each group center and the input and selecting the smallest distance.

6. The method of claim 5 wherein each data input is a binary vector input, and wherein calculating the distance comprises determining the degree of match by counting the number of matching positions in each vector.

7. The method of claim 5 wherein each data input is a non-binary vector input.

8. The method of claim 1 further comprising using feedback to more closely match data inputs to groups.

9. The method of claim 8 wherein using feedback comprises assigning an input to a group only if the input has a value matching a value of the group.

10. A computer program product in computer-readable media for clustering a plurality of data inputs into groups, the computer program product comprising:

means for designating a first data input as center of a group; and

means for successively analyzing each of the other data inputs to identify a group having a center whose proximity to the data input is above a predetermined match threshold, assigning said data input to the identified group; and

if no group is identified, creating a new group and designating the data input as center of the new group; and

repeating data input analysis until all data inputs have been assigned to groups.

11. The computer program product of claim 10 further comprising means for identifying the closest group center to each data input and, and assigning the data input to the group having that center.

12. The computer program product of claim 10 wherein each data input comprises an input vector.

13. The computer program product of claim 10 wherein said match threshold specifies a maximum distance between a data input and a group center.

14. The computer program product of claim 10 wherein the means for identifying a group center closest to an input calculates the distance between each group center and the input and selects the smallest distance.

15. The computer program product of claim 14 wherein each data input is a binary vector input, and wherein calculating the distance comprises determining the degree of match by counting the number of matching positions in each vector.

16. The computer program product of claim 10 wherein said computer program product further comprises means for using feedback to more closely match data inputs to groups.

18. The computer of claim 17 wherein the program further comprises means for identifying the closest group center to each data input and, and assigning the data input to the group having that center.

19. The computer of claim 17 wherein each data input comprises an input vector.

20. The computer of claim 17 wherein said match threshold specifies a maximum distance between a data input and a group center.

21. The computer of claim 17 wherein the means for identifying a group center closest to an input calculates the distance between each group center and the input and selects the smallest distance.

22. The computer of claim 21 wherein each data input is a binary vector input, and wherein calculating the distance comprises determining the degree of match by counting the number of matching positions in each vector.

23. The computer of claim 21 wherein each data input is a non-binary vector input.

25. The method of claim 24 wherein identifying a group of Web users having similar profiles comprises using a clustering process to group users.

26. The method of claim 25 wherein users are designated as data inputs, and the clustering process comprises

(a) defining a match threshold;

(b) designating a first data input as center of a group;

(c) analyzing another data input to identify a group center whose proximity to said another data input is above the match threshold, and assigning said another data input to the group having said group center;

(d) if no group center is identified, creating a new group and designating said another data input as center of the new group; and

(e) repeating steps (c) to (d) until all data inputs have been assigned to groups.

27. The method of claim 26 further comprising (f) identifying the closest group center to each data input and, and assigning the data input to the group having that center.

28. The method of claim 24 further comprising rating the sites not visited by the user based on how frequently other users in the group have visited the sites, and suggesting the highest rated sites to the user.

29. The method of claim 24 wherein suggesting to the user sites not visited by the user comprises providing a button on a client device operated by the user, said button linked to the sites not visited by the user.

30. The method of claim 29 wherein said button is on a browser tool bar on the client device.

31. The method of claim 24 wherein data on sites visited by each user is stored on a client device operated by said user.

32. The method of claim 31 wherein determining which of the sites visited by other users in the group have not been visited by the user is performed by the client device operated by the user.

17. A computer, comprising:

at least one processor;

memory associated with the at least one processor;

a display; and

a program supported in the memory for clustering a plurality of data inputs into groups, the program comprising;

means for designating a first data input as center of a group; and

means for successively analyzing each other data inputs to identify a group center closest to each data input, and if the proximity between the data input and the closest group center is above a predetermined match threshold, assigning said data input to the group having said group center; and

if the proximity between the data input to the closest group center is not above the match threshold, creating a new group and designating the data input as center of the new group; and

repeating data input analysis until all data inputs have been assigned to groups.

means for successively analyzing each of the other data inputs to identify a group having a center whose proximity to the data input is above a predetermined match threshold, assigning said data input to the identified group; and

if no group is identified, creating a new group and designating the data input as center of the new group; and

repeating data input analysis until all data inputs have been assigned to groups.

24. A method of suggesting a Web site to a Web user, comprising:

identifying a group of Web users having similar profiles;

recording Web sites visited by Web users in the group;

for a Web user in the group, determining which of the sites visited by other users in the group have not been visited by the user; and

suggesting to the user the sites not visited by said user.

33. A method of organizing search engine results, comprising:

identifying a group of Web users having similar profiles;

recording search queries made by the users in the group and Web sites visited by users resulting from said search queries; and

for a Web user in the group making a search query, determining if the query was previously made by other users in the group and, if so, identifying to the user the Web sites visited by other users resulting from said search query.

34. The method of claim 33 further comprising rating the Web sites identified to the user based on how frequently other users have visited the sites resulting from said query.

35. The method of claim 33 wherein identifying a group of Web users having similar profiles comprises using a clustering process to group users.

36. The method of claim 35 wherein users are designated as data inputs, and the clustering process comprises

(a) defining a match threshold;

(b) designating a first data input as center of a group;

(c) analyzing another data input to identify a group center whose proximity to said another data input is above the match threshold, and assigning said another data input to the group having said group center;

(e) if no group center is identified, creating a new group and designating said another data input as center of the new group; and

(f) repeating steps (c) to (e) until all data inputs have been assigned to groups.

37. The method of claim 36 further comprising (g) identifying the closest group center to each data input and, and assigning the data input to the group having that center.

38. A method for clustering a plurality of data inputs into groups, comprising:

(a) designating a first data input as center of a group;

(b) analyzing another data input to determine if it is sufficiently close to a center of a group and, if so, assigning the data input to the group;

(c) if no group is found to be sufficiently close to the data input, defining a new group and assigning the data input to the new group; and

(d) repeating steps (b) and (c) until all data inputs have been assigned to groups.