Taxonomy-based object classification

• US 7,788,265 B2
• Filed: 12/21/2006
• Issued: 08/31/2010
• Est. Priority Date: 12/21/2006
• Status: Active Grant

• Current Assignee: Finebrain.com AG
• Original Assignee: Finebrain.com AG
• Inventors: Morscher, Thomas, Loffler, Wolfgang
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): YOUNG, KEVIN L.
• Application Number:
  US11/614,722
• Publication Number:
  US 20080154875A1
• Time in Patent Office: 1,349 Days
• Field of Search: None
• US Class Current: 707/740
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/956 Hierarchical

Abstract

Objects, such as documents, are classified according to a taxonomy. The taxonomy includes nodes, corresponding to object classes, arranged in a hierarchy. Class keywords are associated with the nodes. Search strings are formed for the classes by traversing the taxonomic branches and concatenating the keywords associated with the classes. For each object to be classified, a search engine is used to perform searches on the object using the search strings. The searches produce search scores for each search string. Each object is classified by identifying the class(es) corresponding to the highest search score(s) for the object, and classifying the object into the identified class(es).

Claims

1. A computer-implemented method for classifying an object in a taxonomy, the taxonomy including a plurality of nodes associated with a plurality of classes, the object being external to the taxonomy, the method comprising:

(A) identifying a plurality of search strings based on a first plurality of class keywords associated with the plurality of nodes, wherein identifying comprises, for at least one particular node N in the plurality of nodes;

(A)(1) traversing a first branch in the taxonomy linking a root node of the taxonomy to node N; and

(A)(2) for each node M in the first branch, selecting a class keyword associated with node M and adding the selected class keyword to a first one of the plurality of search strings associated with node N, whereby the first one of the plurality of search strings contains a second plurality of class keywords;

(B) using a search engine to perform a plurality of searches on the object using the plurality of search strings to produce a plurality of search scores corresponding to the plurality of search strings;

(C) identifying one of the plurality of nodes based on the plurality of search scores; and

(D) classifying the object in a class associated with the identified node.

2. The method of claim 1, wherein (A) further comprises:

(A)(3) traversing a second branch in the taxonomy linking node N to the root node of the taxonomy; and

(A)(4) for each node L in the second branch, selecting a class keyword associated with node L and adding the selected class keyword to a second one of the plurality of search strings associated with node N.

3. The method of claim 1, wherein (A) further comprises delimiting each of the second plurality of class keywords in the first one of the plurality of search strings to mark each of the second plurality of class keywords in the first one of the plurality of search strings as an atomic entity.

4. The method of claim 1, wherein (A) further comprises concatenating the second plurality of class keywords in the first one of the plurality of search strings with symbols indicating logical relationships of the second plurality of class keywords in the first one of the plurality of search strings to each other.

5. The method of claim 1, wherein a third plurality of class keywords having an order is associated with node M, and wherein (A)(2) comprises selecting the class keyword based on the order of the third plurality of class keywords associated with node M.

6. The method of claim 1, wherein (C) comprises:

(C)(1) identifying one of the plurality of search scores having a maximum value among the plurality of search scores;

(C)(2) identifying one of the plurality of search strings that produced the search score having the maximum value; and

(C)(3) identifying one of the plurality of nodes associated with a plurality of class keywords on which the identified one of the plurality of search strings was based.

7. The method of claim 1, wherein (D) comprises:

(D)(1) identifying a class among the plurality of classes associated with the identified one of the plurality of nodes; and

(D)(2) classifying the object in the identified class.

8. The method of claim 1, wherein the object comprises a document.

9. The method of claim 1, wherein (A) further comprises:

(A)(3) identifying a first plurality of search strings based on the first plurality of class keywords associated with the plurality of nodes;

(A)(4) identifying a plurality of rankings of the first plurality of search strings; and

(A)(5) identifying a subset of the first plurality of search strings based on the plurality of rankings; and

wherein (B) comprises performing the plurality of searches on the object using the subset of the first plurality of search strings to produce the plurality of search scores.

10. The method of claim 1, wherein (C) comprises:

(C)(1) providing a user with an indication of a plurality of nodes corresponding to a subset of the plurality of search scores; and

(C)(2) receiving from the user a selection of one of the plurality of nodes corresponding to the subset of the plurality of search scores.

11. A computer program product comprising computer-executable instructions, tangibly stored on a computer readable medium, for execution by a processor to perform a method for classifying an object in a taxonomy, the taxonomy including a plurality of nodes associated with a plurality of classes, the object being external to the taxonomy, the method comprising:

(A) identifying a first plurality of search strings based on a plurality of class keywords associated with the plurality of nodes, wherein identifying comprises, for at least one particular node N in the plurality of nodes;

(A)(1) traversing a first branch in the taxonomy linking a root node of the taxonomy to node N; and

(A)(2) for each node M in the first branch, selecting a class keyword associated with node M and adding the selected class keyword to a first one of the plurality of search strings associated with node N, whereby the first one of the plurality of search strings contains a second plurality of class keywords;

(B) performing a plurality of searches on the object using the plurality of search strings to produce a plurality of search scores corresponding to the plurality of search strings;

(C) identifying one of the plurality of nodes based on the plurality of search scores; and

(D) classifying the object in a class associated with the identified node.

12. The computer program product of claim 11, wherein (A) further comprises:

(A)(3) traversing a branch in the taxonomy linking node N to the root node of the taxonomy; and

(A)(4) for each node L in the second branch, selecting a class keyword associated with node L and adding the selected class keyword to a second one of the plurality of search strings associated with node N.

13. The computer program product of claim 11, wherein (A) further comprises delimiting each of the second plurality of class keywords in the first one of the plurality of search strings to mark each of the second plurality of class keywords in the first one of the plurality of search strings as an atomic entity.

14. The computer program product of claim 11, wherein (A) further comprises concatenating the second plurality of class keywords in the first one of the plurality of search strings with symbols indicating logical relationships of the second plurality of class keywords in the first one of the plurality of search strings to each other.

15. The computer program product of claim 11, wherein a third plurality of class keywords having an order is associated with node M, and wherein (A)(2) comprises selecting the class keyword based on the order of the third plurality of class keywords associated with node M.

16. The computer program product of claim 11, wherein (C) comprises:

(C)(1) identifying one of the plurality of search scores having a maximum value among the plurality of search scores;

(C)(2) identifying one of the plurality of search strings that produced the search score having the maximum value; and

(C)(3) identifying one of the plurality of nodes associated with a plurality of class keywords on which the identified one of the plurality of search strings was based.

17. The computer program product of claim 11, wherein (D) comprises:

(D)(1) identifying a class among the plurality of classes associated with the identified one of the plurality of nodes; and

(D)(2) classifying the object in the identified class.

18. The computer program product of claim 11, wherein the object comprises a document.

19. The computer program product of claim 11, wherein (A) comprises:

(A)(3) identifying a first plurality of search strings based on the plurality of class keywords associated with the plurality of nodes;

(A)(4) identifying a plurality of rankings of the first plurality of search strings; and

(A)(5) identifying a subset of the first plurality of search strings based on the plurality of rankings; and

wherein (B) comprises performing the plurality of searches on the object using the subset of the first plurality of search strings to produce the plurality of search scores.

20. The computer program product of claim 11, wherein (C) comprises:

(C)(1) providing a user with an indication of a plurality of nodes corresponding to a subset of the plurality of search scores; and

(C)(2) receiving from the user a selection of one of the plurality of nodes corresponding to the subset of the plurality of search scores.

21. The computer program product of claim 11, wherein (B) comprises a search engine.