Information resource taxonomy

• US 8,166,030 B2
• Filed: 12/18/2002
• Issued: 04/24/2012
• Est. Priority Date: 12/18/2001
• Status: Expired due to Fees

• Current Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Original Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Inventors: Ryan, Simon David, Raskutti, Bhavani, Phiet, Do Quang, Sember, Peter Paul
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US10/499,587
• Publication Number:
  US 20050080781A1
• Time in Patent Office: 3,415 Days
• Field of Search: 707101-102
• US Class Current: 707/736
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

An information resource taxonomy system, including a data collector for collecting information resources from a communications network; and a taxonomy generator for generating a taxonomy represented by a hierarchy of resource clusters, using cluster criteria generated from the collected resources. The system includes an editor for editing the criteria, and a renderer for generating linked document data for displaying the hierarchy. A parallel cluster search system is used to evaluate clusters in parallel. The system also includes a parallel classifier for classifying further collected resources.

Claims

1. A process for generating a taxonomy for a plurality of information resources in a communications network, including:

(i) collecting said plurality of information resources from said communications network;

(ii) generating clusters of said plurality of collected information resources on the basis of a similarity threshold value for clustering and similarity values for said plurality of collected information resources;

(iii) iteratively generating sub-clusters of said generated clusters based on the similarity threshold value for clustering and similarity values for information resources within each of said generated clusters and within each of said generated sub-clusters, wherein the generated clusters and sub-clusters provide a hierarchy of resource clusters, wherein the number of resource clusters at each level of said hierarchy is determined by content of said plurality of collected information resources;

(iv) collecting further information resources from said communications network;

(v) assigning the further collected information resources to a plurality of the resource clusters;

(vi) maintaining the coherence of the plurality of resource clusters as further collected information resources are assigned by at least one of;

(a) reducing the similarity threshold value for clustering with an increasing number of the further collected information resources; and

(b) selecting a random subset of resources from the collected information resources;

generating a new similarity threshold value for clustering based on the selected random subset of resources; and

re-clustering the collected information resources using the generated new similarity threshold value for clustering; and

(vii) repeating the steps of collecting further information resources, reducing similarity and maintaining the coherence.

2. The process as claimed in claim 1, wherein said step of iteratively generating includes selecting one or more of said generated clusters if one or more intra-cluster similarity values for respective resources of said generated clusters exceeds corresponding similarity threshold value, and iteratively generating sub-clusters of the selected one or more of said generated clusters.

3. The process as claimed in claim 1, wherein said step of generating clusters includes:

selecting one or more portions of said plurality of information resources on the basis of respective metrics of the relevance of said one or more portions, wherein the number of said generated clusters is determined on the basis of the selected one or more portions of said plurality of information resources.

4. The process as claimed in claim 3, wherein clusters are generated on the basis of similarity values generated from word frequency data generated from one or more selected portions of said plurality of information resources.

5. The process as claimed in claim 1, including generating linked document data for displaying said hierarchy of resource clusters.

6. The process as claimed in claim 5, wherein said linked document data includes markup language data.

7. The process as claimed in claim 5, wherein said linked document data includes metadata of said plurality of information resources.

8. The process as claimed in claim 1, including generating descriptive text for said plurality of information resources and descriptive text for each resource cluster of said hierarchy.

9. The process as claimed in claim 1, wherein said plurality of information resources include dynamically generated content of said communications network.

10. The process as claimed in claim 1, wherein components of said hierarchy are sorted based on access frequencies of said plurality of collected information resources.

11. The process as claimed in claim 1, wherein a resource is added to an existing cluster if the similarity of said resource to said cluster meets a similarity requirement.

12. The process as claimed in claim 1, wherein a new cluster is generated if the similarity of resource to each existing cluster does not meet a similarity requirement.

13. The process as claimed in claim 1, wherein said step of generating clusters includes determining the similarity threshold value for clustering on the basis of goodness values for respective groupings of said plurality of collected information resources generated for respective similarity threshold values.

14. The process as claimed in claim 13, wherein the goodness value for each grouping is generated on the basis of similarity values for resources within the clusters of the grouping and differences between cluster centroids for the clusters of the grouping and a global centroid for said resources.

15. The process as claimed in claim 1, wherein said steps of generating clusters and iteratively generating sub-clusters are scalable with the number of said plurality of collected information resources.

16. The process as claimed in claim 1, wherein the plurality of information resources collected at step (i) are a selected subset of a larger set of resources including the further information resources collected at step (iv).

17. The process as claimed in claim 16, including selecting said subset by random sampling of said larger set of resources.

18. The process as claimed in claim 16, including classifying resources into said resource clusters.

19. The process as claimed in claim 16, including using said clusters generated at steps (ii) and (iii) as a training set for a classifier used at step (v) to assign the further information resources to at least one of the resource clusters.

20. The process as claimed in claim 19, wherein said classifier includes a support vector machine.

21. The process as claimed in claim 16, including clustering using a similarity value determined whilst clustering the subset of said larger set of resources.

22. The process as claimed in claim 21, including maintaining the coherence of clusters as the further additional resources are collected by reducing said similarity threshold value with increasing number of resources.

23. The process as claimed in claim 22, including determining a new similarity value for reclustering existing clusters on the basis of the quality of said existing clusters.

24. The process as claimed in claim 16, including maintaining generating a new hierarchy of resource clusters and classifying unselected resources into said new hierarchy of resource clusters.

25. The process as claimed in claim 16, including selecting a subset of clustered resources as the number of clustered resources increases to generate a metric for evaluating the quality of existing clusters.

26. The process as claimed in claim 1, including generating one or more new clusters for resources that are not substantially similar to existing clusters.

27. The process as claimed in claim 1, wherein said step of iteratively generating includes selecting one or more of said generated clusters on the basis of respective measures of coherence of said generated clusters, and iteratively generating sub-clusters of the selected one or more of said generated clusters.

28. An information resource taxonomy system having computer system hardware components, including at least one processor operating according to one or more software modules, the at least one processor and software modules configured to execute the steps of claim 1.

29. A computer-readable storage medium, having stored thereon program code for executing the steps of claim 1.

30. The process as claimed in claim 1, wherein the content of resources in each cluster determines the number of sub-clusters generated from the cluster in the immediately inferior level of the hierarchy.

31. The process as claimed in claim 30, wherein the number of levels of said hierarchy is determined by content of said plurality of information resources.

32. The process as claimed in claim 1 wherein the number of levels of said hierarchy is determined by content of said plurality of information resources.

33. An information resource taxonomy system, including:

a data collector having computer system hardware components including at least one processor operating according to one or more software modules, the at least one processor and one or more software modules configured for collecting information resources from a communications network;

a taxonomy generator for generating clusters of said collected information resources based on a similarity threshold value for clustering and similarity values for said collected information resources and for iteratively generating sub-clusters of said generated clusters based on the similarity threshold value for clustering and similarity values for information resources within each of said generated clusters and within each of said generated sub-clusters, wherein the generated clusters and sub-clusters provide a hierarchy of resource clusters, wherein the number of resource clusters in each level of said hierarchy is determined by content of said collected information resources;

a classifier configured to classify further information resources collected from the communication network to a plurality of the resource clusters; and

a component configured to maintain the coherence of the plurality of resource clusters as further information resources are classified by at least one of;

(a) reducing the similarity threshold value for clustering with increasing numbers of the further collected information resources; and

(b) selecting a random subset of information resources from the collected information resources;

generating a new similarity threshold value for the selected random subset of information resource; and

re-clustering the collected information resources using the new similarity threshold value for clustering.

34. The system as claimed in claim 33, including an editor for editing said taxonomy hierarchy of resource clusters, and a renderer for generating linked document data for displaying said hierarchy of resource clusters.

35. The system as claimed in claim 33, wherein said system is scalable with respect to the number of said information resources.

36. The system as claimed in claim 33, including a parallel cluster search system for evaluating clusters in parallel.

37. The system as claimed in claim 33, wherein the classifier is including a parallel classifier for classifying further resources in parallel.

38. The system as claimed in claim 33, wherein the number resource clusters in each level of said hierarchy is determined by content of resources, each resource cluster determines the number of sub-clusters generated from the resource cluster in the immediately inferior level of the hierarchy.

39. The system as claimed in claim 38, wherein the number of levels of said hierarchy is determined by content of said information resources.

40. The system as claimed in claim 33, wherein the number of levels of said hierarchy is determined by content of said information resources.