Training set construction for taxonomic classification

• US 8,122,005 B1
• Filed: 10/22/2009
• Issued: 02/21/2012
• Est. Priority Date: 10/22/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Juang, Philo, Testa, Christopher, Mote, Nicolaus
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US12/604,025
• Time in Patent Office: 852 Days
• Field of Search: None
• US Class Current: 707/710
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

A training set generator may be configured to input a taxonomy including a hierarchy of categories and a plurality of top-level sites, and to output a training set of categorized data. The training set generator may include a crawler configured to crawl each of the top-level sites to determine at least one lower-level site associated therewith and to store the top-level sites and associated lower-level sites as crawl data. The training set generator also may include an extractor configured to determine, for each of the top-level sites, a corresponding site-specific extraction template associating at least one portion of the corresponding top-level site with at least one category of the hierarchy of categories, and further configured to apply each site-specific extraction template to corresponding crawl data to thereby associate the crawl data with the categories of the hierarchical categories and obtain categorized data of the training set.

Claims

1. A computer system including instructions stored on a computer-readable medium, the computer system comprising:

a training set generator configured to input a taxonomy including a hierarchy of categories and a plurality of top-level sites, and to output a training set of categorized data, the training set generator including;

a crawler configured to crawl each of the top-level sites to determine at least one lower-level site associated therewith and to store the top-level sites and associated lower-level sites as crawl data;

an extractor configured to determine, for each of the top-level sites, a corresponding site-specific extraction template associating at least one portion of the corresponding top-level site with at least one category of the hierarchy of categories, and further configured to apply each site-specific extraction template to corresponding crawl data to thereby associate the crawl data with the categories of the hierarchical categories and obtain categorized data of the training set,

wherein the extractor includes at least one site-specific extractor that is configured to apply the site-specific extraction template to the crawl data associated with the corresponding top-level site, including extracting instances of the categories from the crawl data and labeling the extracted instances using the categories within the training set, and

wherein the training set generator is configured to periodically replace the training set with a modified training set, including re-crawling the top-level sites and re-applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, and extracting new instances of the categories from the crawl data and labeling the new instances using the categories within the modified training set.

2. The system of claim 1, wherein the taxonomy includes a tree structure of the hierarchy of categories.

3. The system of claim 1, wherein the crawler includes a site finder configured to receive the plurality of top-level sites from a user by way of a graphical user interface (GUI).

4. The system of claim 1, wherein the crawler includes a site finder configured to execute a search for top level sites to obtain potential top-level sites and to receive a selection from a user of the plurality of the top-level sites from the potential top-level sites.

5. The system of claim 1, wherein the crawler includes a site crawler configured to execute the crawling of the top-level sites including following at least one link from each top-level site through following linked sites until a criteria is met.

6. The system of claim 1, wherein the extractor includes at least one site-specific template generator configured to input a particular top-level site and to receive a correlation of the at least one portion thereof with the at least one category, to thereby generate the corresponding site-specific extraction template.

7. The system of claim 6, wherein the correlation is identified based on a structure of the particular top-level site.

8. The system of claim 1, comprising a trainer configured to receive the training set and determine a classifier model based thereon.

9. The system of claim 8, comprising a classifier associated with supplemental information and configured to receive a new document and to apply the classifier model thereto to obtain a classification thereof.

10. The system of claim 9, wherein the classifier is configured to select supplemental content from the supplemental information, based on the classification, and further configured to supplement the new document with the supplemental content to obtain a supplemented new document.

11. A computer system including instructions stored on a computer-readable medium, the computer system comprising:

a training set generator configured to input a taxonomy including a hierarchy of categories and a plurality of top-level sites, and to output a training set of categorized data, the training set generator including;

a crawler configured to crawl each of the top-level sites to determine at least one lower-level site associated therewith and to store the top-level sites and associated lower-level sites as crawl data;

an extractor configured to determine, for each of the top-level sites, a corresponding site-specific extraction template associating at least one portion of the corresponding top-level site with at least one category of the hierarchy of categories, and further configured to apply each site-specific extraction template to corresponding crawl data to thereby associate the crawl data with the categories of the hierarchical categories and obtain categorized data of the training set,

wherein the training set generator is configured to determine a new category of the hierarchy of categories, based on the crawl data, and configured to augment the taxonomy by adding the new category thereto.

12. A computer-implemented method comprising:

determining a taxonomy including a hierarchy of categories;

determining a plurality of top-level sites related to the taxonomy;

determining, for each of the top-level sites, a corresponding site-specific extraction template associating at least one portion of the corresponding top-level site with at least one category of the hierarchy of categories;

crawling each of the top-level sites to determine at least one lower-level site associated therewith;

storing the top-level sites and associated lower-level sites as crawl data;

applying each site-specific extraction template to corresponding crawl data to thereby associate the crawl data with the categories of the hierarchical categories and obtain categorized data, including applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, and further including extracting instances of the categories from the crawl data and labeling the extracted instances using the categories within the training set, and

replacing, periodically, the training set with a modified training set, including re-crawling the top-level sites and re-applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, and further including extracting new instances of the categories from the crawl data and labeling the new instances using the categories within the modified training set.

13. The method of claim 12, wherein determining a plurality of top-level sites comprises receiving the plurality of top-level sites from a user.

14. The method of claim 12, wherein determining a plurality of top-level sites comprises:

executing a search for top level sites to obtain potential top-level sites; and

receiving a selection from a user of the plurality of the top-level sites from the potential top-level sites.

15. The method of claim 12 wherein applying each site-specific extraction template comprises:

applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, including extracting instances of the categories from the crawl data and labeling the extracted instances using the categories within the training set.

16. A computer program product, the computer program product being tangibly embodied on a computer-readable medium and including executable code that, when executed, is configured to cause a data processing apparatus to:

determine a taxonomy including a hierarchy of categories;

determine a plurality of top-level sites related to the taxonomy;

determine, for each of the top-level sites, a corresponding site-specific extraction template associating at least one portion of the corresponding top-level site with at least one category of the hierarchy of categories;

crawl each of the top-level sites to determine at least one lower-level site associated therewith;

store the top-level sites and associated lower-level sites as crawl data; and

apply each site-specific extraction template to corresponding crawl data to thereby associate the crawl data with the categories of the hierarchical categories and obtain categorized data, including applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, and further including extracting instances of the categories from the crawl data and labeling the extracted instances using the categories within the training set, and

replace, periodically, the training set with a modified training set, including re-crawling the top-level sites and re-applying the site-specific extraction template to the crawl data associated with the corresponding top-level site, and further including extracting new instances of the categories from the crawl data and labeling the new instances using the categories within the modified training set.

17. The computer program product of claim 16, wherein the plurality of top-level sites are received from a user.

18. The computer program product of claim 16, wherein the instructions, when executed, cause the data processing apparatus to:

receive the training set and determine a classifier model based thereon;

receive a new document and to apply the classifier model thereto to obtain a classification thereon;

select supplemental content, based on the classification; and

supplement the new document with the supplemental content to obtain a supplemented new document.