Method and system for clustering identified forms

• US 7,996,390 B2
• Filed: 02/15/2008
• Issued: 08/09/2011
• Est. Priority Date: 02/15/2008
• Status: Expired due to Fees

• Current Assignee: University of Utah Research Foundation (State of Utah)
• Original Assignee: University of Utah Research Foundation (State of Utah)
• Inventors: Barbosa, Luciano, Freire, Juliana
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): Jami; Hares
• Application Number:
  US12/032,331
• Publication Number:
  US 20090210406A1
• Time in Patent Office: 1,271 Days
• Field of Search: 707/705, 707720-735, 707/999.1, 707/999.3, 707/999.6, 707/999.7, 707/736, 707/737, 707/758
• US Class Current: 707/722
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method is provided for organizing a plurality of documents that include forms. An initial set of clusters is defined for the plurality of documents. The initial set of clusters is reclustered based on similarity values calculated in multiple feature spaces. For example, a first feature space may be associated with a content of a document while a second feature space may be associated with a content of a form associated with the document. Each cluster has an associated centroid vector in each feature space that is used to represent the cluster. The similarity between the document and each cluster is calculated in both feature spaces. Each document is assigned to the cluster whose centroid is most similar. The cluster centroids may be recalculated and the process repeated until the cluster assignments become stable.

Claims

1. A device for organizing a plurality of documents that include forms, the device comprising:

a processor;

a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium comprising instructions that, upon execution by the processor, perform operations comprising

(a) identifying a first form in a first document selected from a plurality of documents;

(b) calculating a first similarity value in a first feature space between a first cluster selected from a plurality of clusters defined for the plurality of documents and the first document, the first feature space associated with a content of the first document and a content of a document assigned to the first cluster;

(c) calculating a second similarity value in a second feature space between the first cluster and the first document, the second feature space associated with a content of the identified first form and a content of a form in the document assigned to the first cluster;

(d) calculating a similarity value between the first document and the first cluster based on the calculated first similarity value and the calculated second similarity value;

(e) repeating (b)-(d) with each of the plurality of clusters as the first cluster selected from the plurality of clusters;

(f) determining a cluster of the plurality of clusters to which to assign the first document based on the calculated similarity value for each of the plurality of clusters; and

repeat (a)-(f) for each of the plurality of documents as the first document selected from the plurality of documents until the assignments become stable, wherein determining if the assignments become stable includes calculating a number of documents of the plurality of documents that are assigned to a different cluster in (f).

2. A non-transitory computer-readable medium comprising computer-readable instructions therein that, upon execution by a processor, cause the processor to organize a plurality of documents that include forms, the instructions configured to cause a computing device to:

(a) identify a first form in a first document selected from a plurality of documents;

(b) calculate a first similarity value in a first feature space between a first cluster selected from a plurality of clusters defined for the plurality of documents and the first document, the first feature space associated with a content of the first document and a content of a document assigned to the first cluster;

(c) calculate a second similarity value in a second feature space between the first cluster and the first document, the second feature space associated with a content of the identified first form and a content of a form in the document assigned to the first cluster;

(d) calculate a similarity value between the first document and the first cluster based on the calculated first similarity value and the calculated second similarity value;

(e) repeat (b)-(d) with each of the plurality of clusters as the first cluster selected from the plurality of clusters;

(f) determine a cluster of the plurality of clusters to which to assign the first document based on the calculated similarity value for each of the plurality of clusters; and

repeat (a)-(f) for each of the plurality of documents as the first document selected from the plurality of documents until the assignments become stable, wherein determining if the assignments become stable includes calculating a number of documents of the plurality of documents that are assigned to a different cluster in (f).

3. A method of organizing a plurality of documents that include forms, the method comprising:

(a) identifying, by a computing device, a first form in a first document selected from a plurality of documents;

(b) calculating, by the computing device, a first similarity value in a first feature space between a first cluster selected from a plurality of clusters defined for the plurality of documents and the first document, the first feature space associated with a content of the first document and a content of a document assigned to the first cluster;

(c) calculating, by the computing device, a second similarity value in a second feature space between the first cluster and the first document, the second feature space associated with a content of the identified first form and a content of a form in the document assigned to the first cluster;

(d) calculating, by the computing device, a similarity value between the first document and the first cluster based on the calculated first similarity value and the calculated second similarity value;

(e) repeating (b)-(d), by the computing device, with each of the plurality of clusters as the first cluster selected from the plurality of clusters;

(f) determining, by the computing device, a cluster of the plurality of clusters to which to assign the first document based on the calculated similarity value for each of the plurality of clusters; and

repeating (a)-(f) for each of the plurality of documents as the first document selected from the plurality of documents until the assignments become stable, wherein determining if the assignments become stable includes calculating a number of documents of the plurality of documents that are assigned to a different cluster in (f).

4. The method of claim 3, wherein identifying the first form comprises selecting text between markup language tags used to partition the first document.

5. The method of claim 3, further comprising organizing the plurality of documents by assigning the plurality of documents to the plurality of clusters based on repeating (a)-(f) with each of the plurality of documents as the first document selected from the plurality of documents.

6. The method of claim 5, further comprising outputting the organized documents wherein outputting comprises at least one of printing the assignments, displaying the assignments, and storing the assignments in a memory for use as an input to an application.

7. The method of claim 3, wherein the plurality of documents are identified as documents containing a searchable form.

8. The method of claim 3, wherein the plurality of documents are identified from a search of a plurality of computers connected in a network.

9. The method of claim 8, wherein the network is the Internet.

10. The method of claim 3, wherein calculating the first similarity value comprises:

calculating a first value in the first feature space for the first cluster based on the document assigned to the first cluster; and

calculating the first similarity value based on a third value and the calculated first value, the third value calculated in the first feature space for the first document.

11. The method of claim 10, wherein the first value for the first cluster comprises a first centroid vector defined for the document assigned to the first cluster.

12. The method of claim 11, wherein the first centroid vector is defined as a first average of weights of terms identified from the document assigned to the first cluster.

13. The method of claim 12, wherein the first similarity value comprises a first distance calculated between the first centroid vector and the first vector.

14. The method of claim 13, wherein the third value comprises a first vector including first weights calculated for a first plurality of terms identified from the first document.

15. The method of claim 14, wherein the first distance is calculated as a cosine distance between the first centroid vector and the first vector.

16. The method of claim 3, wherein calculating the second similarity value comprises:

calculating a second value in the second feature space for the first cluster based on the form in the document assigned to the first cluster; and

calculating the second similarity value based on a fourth value and the calculated second value, the fourth value calculated in the second feature space for the identified first form.

17. The method of claim 16, wherein the second value for the first cluster comprises a second centroid vector defined for the form identified in the document assigned to the first cluster.

18. The method of claim 17, wherein the second centroid vector is calculated as a second average of weights of terms identified from the form identified in the document assigned to the first cluster.

19. The method of claim 18, wherein the fourth value comprises a second vector including second weights calculated for a second plurality of terms identified from the first form.

20. The method of claim 19, wherein the second similarity value comprises a second distance calculated between the second centroid vector and the second vector.

21. The method of claim 3, wherein the similarity value is a sum of the first similarity value and the second similarity value.

22. The method of claim 21, wherein the similarity value is a weighted sum of the first similarity value and the second similarity value.

23. The method of claim 3, wherein determining if the assignments become stable further includes calculating a ratio of the number of documents assigned to a different cluster relative to a second number of the plurality of documents.

24. The method of claim 3, further comprising, before (a), randomly assigning an initial document of the plurality of documents to each of the plurality of clusters.

25. The method of claim 3, further comprising assigning an initial document to each of the plurality of clusters based on a location of the initial document.

26. The method of claim 25, wherein assigning the initial document to each of the plurality of clusters based on the location of the initial document comprises:

(g) identifying a plurality of hubs for the plurality of documents, wherein a hub of the plurality of hubs is associated with a document from which a plurality of the plurality of documents can be reached either directly or indirectly;

(h) identifying a plurality of hub clusters based on the identified plurality of hubs;

(i) calculating a plurality of similarity values, wherein a hub similarity value of the plurality of similarity values indicates a similarity between a pair of the identified plurality of hub clusters;

(j) identifying a first hub cluster and a second hub cluster from the identified plurality of hub clusters based on the calculated plurality of similarity values, wherein the first hub cluster and the second hub cluster are least similar; and

(k) adding the identified first hub cluster and the identified second hub cluster as clusters to the plurality of clusters.

27. The method of claim 26, further comprising:

(l) calculating a second plurality of similarity values between each remaining hub cluster of the identified plurality of hub clusters and the plurality of clusters;

(m) identifying a third hub cluster from the remaining hub clusters based on the calculated second plurality of similarity values, wherein the third hub cluster is least similar to the plurality of clusters;

(n) adding the identified third hub cluster as a cluster to the plurality of clusters; and

(o) repeating (l)-(n) until a stop condition is satisfied.

28. The method of claim 27, further comprising receiving a value representing a desired number of clusters.

29. The method of claim 28, wherein the stop condition comprises a comparison between a cluster count identifying the number of the plurality of clusters and the received value.

30. The method of claim 3, wherein the first feature space includes information associated with a link of the first document.

31. The method of claim 3, wherein the second feature space includes information associated with a link of the identified first form.

32. The method of claim 3, wherein the cluster is determined using a clustering algorithm selected from the group consisting of a k-means clustering algorithm, an agglomerative hierarchical clustering algorithm, a divisive hierarchical clustering algorithm, a balanced iterative reducing and clustering using hierarchies clustering algorithm, a clustering using representatives clustering algorithm, a density-based clustering algorithm, and a grid-based clustering algorithm.