Method and system for automatically extracting data from web sites
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.
1. A method for automatically extracting and structuring data from a semi-structured web site, the method comprising:
executing instructions stored in a computer memory by a computer processor for:
developing a set of experts;
analyzing links and pages on the web site by the set of experts;
identifying predetermined types of generic structures by the set of experts;
clustering pages and textual segments within the pages based on the identified types of generic structures, the clustering is being represented as a Bayesian belief network and including:
adding a layer of nodes to the Bayesian belief network, the added layer of nodes including a node for every pair of samples being analyzed, at least one node in the added layer of nodes being an in-same-cluster node which represents whether or not a respective pair of samples being analyzed is in a same cluster, and the set of experts providing their output probabilistic suggestions represented as virtual-evidence nodes;
collecting virtual-evidence from the set of experts;
calculating a belief in a corresponding in-same-cluster node by propagating beliefs from all the virtual evidence nodes; and
calculating a belief in a root clustering node by propagating beliefs from all corresponding in-same-cluster nodes;
identifying, based on the clustering, semi-structured data that can be extracted; and
extracting the identified semi-structured data from the web site.
2. The method of claim 1 , wherein each expert in the set of experts is assigned a particular type of structure independently from all other experts to focus on.
3. The method of claim 2 , wherein each expert in the set of experts analyzes the links and pages with respect to its assigned type of structure.
4. The method of claim 1 , wherein the clustering further includes:
finding a most likely value of a clustering variable after all virtual-evidence have been propagated through the Bayesian belief network by means of a greedy agglomerative search process including:
consider all pairs of clusters;
evaluating a set of edges connecting one sample in one cluster to another sample in another cluster to choose one pair of clusters; and
merging repeatedly the chosen pair of clusters to create a larger cluster until only one cluster results.
5. The method of claim 4 , wherein the greedy agglomerative search process further includes:
assigning a score to each of the pairs of clusters, the score being a product of probabilities associated with the edges and a pair of clusters with a highest score being merged when the merging is repeated.
6. The method of claim 5 , wherein the greed agglomerative search process further includes:
calculating each clustering's probability by evaluating it within the Bayesian belief network.
7. The method of claim 6 , wherein the greedy agglomerative search process further includes:
selecting a clustering with a highest probability.
8. A system for automatically extracting and structuring data from a semi-structured web site, the system comprising:
a computer processor executing instructions for:
developing a set of experts;
analyzing links and pages on the web site by the set of experts;
identifying predetermined types of generic structures by the set of experts;
clustering pages and textual segments within the pages based on the identified types of generic structures, the clustering being represented as a Bayesian belief network and including:
adding a layer of nodes to the Bayesian belief network, the added layer of nodes including a node for every pair of samples being analyzed, at least one node in the added layer of nodes being an in-same-cluster node which represents whether or not a respective pair of samples being analyzed is in a same cluster, and the set of experts providing their output probabilistic suggestions represented as virtual-evidence nodes;
collecting virtual-evidence from the set of experts;
calculating a belief in a corresponding in-same-cluster node by propagating beliefs from all the virtual evidence nodes; and
calculating a belief in a root clustering node by propagating beliefs from all corresponding in-same-cluster nodes;
identifying, based on the clustering, semi-structured data that can be extracted; and
extracting the identified semi-structured data from the web site.
9. The system of claim 8 , wherein each expert in the set of experts is assigned a particular type of structure independently from all other experts to focus on.
10. The system of claim 9 , wherein each expert in the set of experts analyzes the links and pages with respect to its assigned type of structure.
11. The system of claim 8 , wherein the clustering further includes:
finding a most likely value of a clustering variable after all virtual-evidence have been propagated through the Bayesian belief network by means of a greedy agglomerative search process including:
consider all pairs of clusters;
evaluating a set of edges connecting one sample in one cluster to another sample in another cluster to choose one pair of clusters; and
merging repeatedly the chosen pair of clusters to create a larger cluster until only one cluster results.
12. The system of claim 11 , wherein the greedy agglomerative search process further includes:
assigning a score to each of the pairs of clusters, the score being a product of probabilities associated with the edges and a pair of clusters with a highest score being merged when the merging is repeated.
13. The system of claim 12 , wherein the greed agglomerative search process further includes:
calculating each clustering's probability by evaluating it within the Bayesian belief network.
14. The system of claim 13 , wherein the greedy agglomerative search process further includes:
selecting a clustering with a highest probability.
15. A non-transitory computer-readable storage medium having embodied thereon a program, the program being executable by a computer processor to perform a method for automatically extracting and structuring data from a semi-structured web site, the method comprising:
developing a set of experts;
analyzing links and pages on the web site by the set of experts;
identifying predetermined types of generic structures by the set of experts;
clustering pages and textual segments within the pages based on the identified types of generic structures, the clustering being represented as a Bayesian belief network and including:
adding a layer of nodes to the Bayesian belief network, the added layer of nodes including a node for every pair of samples being analyzed, at least one node in the added layer of nodes being an in-same-cluster node which represents whether or not a respective pair of samples being analyzed is in a same cluster, and the set of experts providing their output probabilistic suggestions represented as virtual-evidence nodes;
collecting virtual-evidence from the set of experts;
calculating a belief in a corresponding in-same-cluster node by propagating beliefs from all the virtual evidence nodes; and
calculating a belief in a root clustering node by propagating beliefs from all corresponding in-same-cluster nodes;
identifying, based on the clustering, semi-structured data that can be extracted; and
extracting the identified semi-structured data from the web site.
16. The non-transitory computer-readable storage medium of claim 15 , wherein each expert in the set of experts is assigned a particular type of structure independently from all other experts to focus on.
17. The non-transitory computer-readable storage medium of claim 16 , wherein each expert in the set of experts analyzes the links and pages with respect to its assigned type of structure.
18. The non-transitory computer-readable storage medium of claim 15 , wherein the clustering further includes:
finding a most likely value of a clustering variable after all virtual-evidence have been propagated through the Bayesian belief network by means of a greedy agglomerative search process including:
consider all pairs of clusters;
evaluating a set of edges connecting one sample in one cluster to another sample in another cluster to choose one pair of clusters; and
merging repeatedly the chosen pair of clusters to create a larger cluster until only one cluster results.
19. The non-transitory computer-readable storage medium of claim 18 , wherein the greedy agglomerative search process further includes:
assigning a score to each of the pairs of clusters, the score being a product of probabilities associated with the edges and a pair of clusters with a highest score being merged when the merging is repeated.
20. The non-transitory computer-readable storage medium of claim 19 , wherein the greed agglomerative search process further includes:
calculating each clustering's probability by evaluating it within the Bayesian belief network.
21. The non-transitory computer-readable storage medium of claim 20 , wherein the greedy agglomerative search process further includes:
selecting a clustering with a highest probability.