Training set construction for taxonomic classification

• US 8,484,194 B1
• Filed: 01/13/2012
• Issued: 07/09/2013
• 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:
  US13/350,213
• Time in Patent Office: 543 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 comprising:

at least one processor; and

a computer-readable medium storing instructions that, when executed by the at least one processor, cause the computer system to execute;

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, the crawler including a site finder configured to receive the plurality of top-level sites from a user, and

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.

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 site finder receives the plurality of top-level sites from the user by way of a graphical user interface (GUI).

4. The system of claim 1, wherein the site finder is configured to execute a search for top level sites to obtain potential top-level sites and to receive a selection from the 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, 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.

9. The system of claim 1, the computer system further executing a trainer configured to receive the training set and determine a classifier model based thereon.

10. The system of claim 9, the computer system further executing 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.

11. The system of claim 10, 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.

12. The system of claim 1, 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.

13. A computer-implemented method comprising:

determining a taxonomy including a hierarchy of categories;

receiving a plurality of top-level sites related to the taxonomy from a user;

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; and

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 for a training set.

14. The method of claim 13, wherein the plurality of top-level sites are received from the user via a graphical user interface.

15. The method of claim 13, wherein

receiving the plurality of top-level sites comprises:

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

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

16. The method of claim 13 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.

17. A computer program product, the computer program product being tangibly embodied on a non-transitory 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;

receive a plurality of top-level sites related to the taxonomy from a user;

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 for a training set.

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

19. The computer program product of claim 17, wherein the executable code, when executed, causes 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 thereto;

select supplemental content, based on the classification; and

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

20. The computer program product of claim 17, wherein the executable code, when executed, causes the data processing apparatus to determine a new category of the hierarchy of categories, based on the crawl data, and to augment the taxonomy by adding the new category thereto.