METHOD AND SYSTEM FOR AUTOMATICALLY EXTRACTING DATA FROM WEB SITES

• US 20080114800A1
• Filed: 01/15/2008
• Published: 05/15/2008
• Est. Priority Date: 07/15/2005
• Status: Active Grant

• Current Assignee: Import.io Corporation (Import-io Corp.)
• Original Assignee: Fetch Technologies, Inc.
• Inventors: GAZEN, Bora, MINTON, Steven
• Granted Patent: US 8,117,203 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/95 Retrieval from the web

Abstract

In accordance with an embodiment, data may be automatically extracted from semi-structured web sites. Unsupervised learning may be used to analyze web sites and discover their structure. One method utilizes a set of heterogeneous “experts,” each expert being capable of identifying certain types of generic structure. Each expert represents its discoveries as “hints.” Based on these hints, the system may cluster the pages and text segments and identify semi-structured data that can be extracted. To identify a good clustering, a probabilistic model of the hint-generation process may be used.

Claims

1. A method for automatically extracting and structuring the data from a semi-structured web site, the method comprising:

developing a set of experts;

analyzing the links and pages on the website by means of the experts;

identifying predetermined types of generic structures by means of the experts;

clustering pages and text segments within the pages based on the identified structures; and

identifying, based on the clustering, the semi-structured data that can be extracted.

2. The method of claim 1, and further comprising extracting and structuring the data on the web site to enable the data to be transformed into relational form.

3. The method of claim 1, wherein the experts produce hints indicating that two items should be in the same cluster.

4. The method of claim 3, and further comprising evaluating the probability of clustering based on the hints employed to determine the quality of the clustering.

5. The method of claim 3, wherein clustering provides at least two alternative clusterings.

6. The method of claim 5, and further comprising employing probabilistic models to rate the alternative clusterings.

7. The method of claim 3, and further comprising employing a generative probabilistic model to enable assignment of a probability to the hints in view of a clustering.

8. The method of claim 7, wherein the probability is assigned to both page hints and token hints.

9. The method of claim 8, wherein the probability of page hints is determined from page clusters.

10. The method of claim 8, wherein the probability of token hints is determined from token clusters.

11. The method of claim 3, wherein an expert expresses its identifying of predetermined types of generic structures by adding to the hints a binary hint that indicates that two samples are in the same cluster.

12. The method of claim 11, and further comprising extending constraint language of constraint clustering, wherein the constraints of constrained clustering are defined in the form of must-link or cannot-link pairs.

13. The method of claim 12, and further comprising extending the constraint language so that constraints are assigned confidence scores, thereby permitting an expert to output hints with varying levels of confidence.

14. The method of claim 1, wherein the clustering is represented as a Bayesian belief network.

15. The method of claim 14, and further comprising adding a layer of nodes to the network, the added layer of nodes containing a node for every pair of samples being analyzed.

16. The method of claim 15, wherein one node is an in-same-cluster node which represents whether or not the pair of samples being analyzed is in the same cluster.

17. The method of claim 16, wherein the experts provide as their output probabilistic suggestions represented as virtual-evidence nodes.

18. The method of claim 17, wherein each such virtual-evidence node is dependent from an in-same-cluster node and each in-same-cluster node has as many virtual-evidence nodes as there are experts.

19. The method of claim 16, and further comprising determining the confidence an expert has on the determination that the samples in the pair of samples are in the same cluster.

20. The method of claim 19, wherein the confidence determination comprises:

assigning a similarity value to the pair of samples; and

mapping the similarity value into a confidence score.

21. The method of claim 17, wherein the Bayesian network for clustering comprises:

collecting the virtual evidence from the experts;

calculating the belief in the corresponding in-same-cluster node by propagating belief from all the virtual-evidence nodes; and

computing the belief in a root clustering node by propagation from all the in-same cluster nodes.

22. The method of claim 14, and further comprising finding a most likely value of a clustering variable after all evidence has been propagated through the Bayesian network by means of a greedy agglomerative search process comprising:

considering all pairs of clusters;

evaluating the set of edges connecting one sample from one cluster to another sample in another cluster to choose one pair of clusters;

repeatedly merging the chosen pair of clusters to create a larger cluster until a single cluster results.

23. The method of claim 22, and further comprising assigning a score to the pair of clusters, the score being the product of the probabilities associated with the edges, wherein the pair of clusters with the highest score is merged in each step as the process is repeated.

24. The method of claim 23, wherein the greedy agglomerative search process considers each clustering and calculates that clustering'"'"'s probability by evaluating it within the Bayesian network.

25. The method of claim 24, wherein the greedy agglomerative search process chooses the clustering with the highest probability

26. The method of claim 1, and further comprising, after the page clusters have been determined, applying the text-segment clustering process which comprises:

finding the page clusters;

determining the set of text segments for each page cluster; and

then

clustering the text-segments.

27. A method for automatically extracting and structuring the data from a semi-structured web site, the method comprising:

spidering the web site to obtain a subject set of HTML pages on the web site, including the links on each page;

discovering low-level structure of the pages, text segments, and links on the web site by means of a set of heterogeneous experts;

clustering the pages and text segments to determine a consistent global structure; and

determining the relational form of the data from the page and text segment clusters.

28. The method of claim 27, wherein each expert in the set of experts focuses on a particular type of structure independently from all the other experts.

29. The method of claim 28, wherein each expert analyzes the pages and the links with respect to its assigned type of structure, and outputs hints to indicate the similarities and dissimilarities between items of structure.

30. The method of claim 27, and further comprising:

dividing the pages into individual components based on the analysis performed by the set of experts, the individual components being tokens, the pages and tokens being clustered;

providing the relational view of the data by producing corresponding tables, there being a set of tables for each page cluster, and each column in each table is represented by a token cluster.

31. The method of claim 27, wherein the set of experts produces hints indicating that two items should be in the same cluster.

32. The method of claim 31, wherein multiple experts generate hints that describe local structural similarities between pairs of pages or tokens.

33. The method of claim 32, wherein the hints are page-level and token-level, the page-level hints being a pair of page references indicating that those pages should be in the same page cluster, and the token-level hints being a pair of token sequences indicating that the tokens of the two sequences should be in the same token-clusters.

34. A computer program product for use with a computer system for automatically extracting and structuring the data from a semi-structured web site, the computer program product comprising:

a computer-readable medium;

means, provided on the computer-readable medium, for developing a set of experts;

means, provided on the computer-readable medium, for analyzing the links and pages on the web site by means of the experts;

means, provided on the computer-readable medium, for identifying predetermined types of generic structures by means of the experts;

means, provided on the computer-readable medium, for clustering pages and text segments within the pages based on the identified structures; and

means, provided on the computer-readable medium, for identifying, based on the clustering, the semi-structured data that can be extracted.

35. The computer program product of claim 34, and further comprising means, provided on the computer-readable medium, for extracting and structuring the data on the web site to enable the data to be transformed into relational form.

36. The computer program product of claim 34, and further comprising means, provided on the computer-readable medium, for the experts to produce hints indicating that two items should be in the same cluster, and means, provided on the computer-readable medium, for evaluating the probability of clustering based on the hints employed to determine the quality of the clustering.

37. A system for automatically extracting and structuring the data from a semi-structured web site, the system comprising:

means for developing a set of experts;

means for analyzing the links and pages on the website by means of the experts;

means for identifying predetermined types of generic structures by means of the experts;

means for clustering pages and text segments within the pages based on the identified structures; and

means for identifying, based on the clustering, the semi-structured data that can be extracted.

38. The method of claim 37, and further comprising means for extracting and structuring the data on the web site to enable the data to be transformed into relational form.

39. The method of claim 37, wherein the experts produce hints indicating that two items should be in the same cluster.

40. The method of claim 39, and further comprising means for evaluating the probability of clustering based on the hints employed to determine the quality of the clustering.

41. The method of claim 39, and further comprising means for employing a generative probabilistic model to enable assignment of a probability to the hints in view of a clustering.