Techniques for clustering structurally similar web pages based on page features
Web page clustering techniques described herein are URL Clustering and Page Clustering, whereby clustering algorithms cluster together pages that are structurally similar. Regarding URL clustering, because similarly structured pages have similar patterns in their URLs, grouping similar URL patterns will group structurally similar pages. Embodiments of URL clustering may involve: (a) URL normalization and (b) URL variation computation. Regarding page clustering, page feature-based techniques further cluster any given set of homogenous clusters, reducing the number of clusters based on the underlying page code. Embodiments of page clustering may reduce the number of clusters based on the tag probabilities and the tag sequence, utilizing an Approximate Nearest Neighborhood (ANN) graph along with evaluation of intra-cluster and inter-cluster compactness.
1. A method comprising:
for a sample of pages from each of a plurality of groups of Web pages, wherein the pages within a group are grouped together based on similarity of the pages,
computing a respective distance of structural similarity between features within each sample page and the features within the other sample pages from the plurality of groups, and
computing a radius of influence for each sample page, wherein the radius of influence for the sample page is based on the distance of structural similarity between the features within the sample page and the features within a nearest neighboring sample page;
determining for each sample page, influential sample pages, from the other sample pages from the plurality of groups, whose distance of structural similarity from the sample page is within the radius of influence for the sample page;
identifying, from the plurality of groups, one or more candidate group pairs whose constituent groups are a candidate for merging based on the sum of (a) a first summed distances of structural similarity between the sample pages from a first group of a group pair and the influential sample pages from a second group of the group pair, and (b) a second summed distances of structural similarity between the sample pages from the second group of the group pair and the influential sample pages from the first group of the group pair;
computing intra-group compactness of each group from a first candidate group pair;
computing inter-group compactness of the groups from the first candidate group pair; and
determining whether to merge the groups from the first candidate group pair based on the intra-group compactness and the inter-group compactness;
wherein the method is performed by one or more computing devices.
2. The method of claim 1 , wherein identifying one or more candidate group pairs whose constituent groups are a candidate for merging includes identifying one or more candidate group pairs whose constituent groups are a candidate for merging further based on the sum of (c) a number of pages from the second group that are within the radii of influence of the sample pages from the first group, and (d) a number of pages from the first group that are within the radii of influence of the sample pages from the second group.
3. The medium of claim 2 , wherein the one or more sequences of instructions include instructions which, when executed by one or more processors, causes the one or more processors to perform identifying one or more candidate group pairs whose constituent groups are a candidate for merging further based on the sum of (c) a number of pages from the second group that are within the radii of influence of the sample pages from the first group, and (d) a number of pages from the first group that are within the radii of influence of the sample pages from the second group.
4. The medium of claim 3 , wherein the one or more sequences of instructions include instructions which, when executed by one or more processors, causes the one or more processors to perform computing distances between a first page and a second page based on (a) the respective number of occurrences of tags in the first page and the respective number of occurrences of the tags in the second page and (b) the sequence of tags within the first page and the sequence of tags within the second page.
5. The method of claim 2 , wherein computing the distances of structural similarity between features includes computing distances between a first page and a second page based on (a) the respective number of occurrences of tags in the first page and the respective number of occurrences of the tags in the second page and (b) the sequence of tags within the first page and the sequence of tags within the second page.
6. The method of claim 1 , wherein determining whether to merge comprises determining to merge the groups from the first candidate group pair in response to the inter-group compactness exceeding the intra-group compactness for each group from the first candidate group pair.
7. The method of claim 1 , wherein the plurality of groups of Web pages comprises groups formed from a set of Web pages and formed based on similarities at corresponding levels of Uniform Resource Locators associated with the set of Web pages.
8. The method of claim 1 , wherein the Web pages from the plurality of groups consist of Web pages from a certain domain.
9. The method of claim 8 , wherein the certain domain is a certain website.
10. The method of claim 1 , wherein identifying the one or more candidate groups comprises identifying based on a ratio of the total number of distances of structural similarity between the sample pages from the first and second groups over the sum of the first and second summed distances.
11. A volatile or non-volatile computer-readable-medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:
for a sample of pages from each of a plurality of groups of Web pages, wherein the pages within a group are grouped together based on similarity of the pages,
computing a respective distance of structural similarity between features within each sample page and the features within the other sample pages from the plurality of groups, and
computing a radius of influence for each sample page, wherein the radius of influence for the sample page is based on the distance of structural similarity between the features within the sample page and the features within a nearest neighboring sample page;
determining for each sample page, influential sample pages, from the other sample pages from the plurality of groups, whose distance of structural similarity from the sample page is within the radius of influence for the sample page;
identifying, from the plurality of groups, one or more candidate group pairs whose constituent groups are a candidate for merging based on the sum of (a) a first summed distances of structural similarity between the sample pages from a first group of a group pair and the influential sample pages from a second group of the group pair, and (b) a second summed distances of structural similarity between the sample pages from the second group of the group pair and the influential sample pages from the first group of the group pair;
computing intra-group compactness of each group from a first candidate group pair;
computing inter-group compactness of the groups from the first candidate group pair; and
determining whether to merge the groups from the first candidate group pair based on the intra-group compactness and the inter-group compactness.
12. The medium of claim 11 , wherein the one or more sequences of instructions include instructions which, when executed by one or more processors, causes the one or more processors to perform determining to merge the groups from the first candidate group pair in response to the inter-group compactness exceeding the intra-group compactness for each group from the first candidate group pair.
13. The medium of claim 11 , wherein the plurality of groups of Web pages comprises groups formed from a set of Web pages and formed based on similarities at corresponding levels of Uniform Resource Locators associated with the set of Web pages.
14. The medium of claim 11 , wherein the Web pages from the plurality of groups consist of Web pages from a certain domain.
15. The medium of claim 14 , wherein the certain domain is a certain website.
16. The medium of claim 11 , wherein identifying the one or more candidate groups comprises identifying based on a ratio of the total number of distances of structural similarity between the sample pages from the first and second groups over the sum of the first and second summed distances.