Navigation Objects Extraction for Better Content Structure Understanding
Kui Zhao Bangpeng Li Zilun Peng Jiajun Bu Can Wang




  College of Computer Science, Zhejiang University
  Hangzhou 
  China

zhaokui@zju.edu.cn



  College of Computer Science, Zhejiang University
  Hangzhou 
  China

bondlee@zju.edu.cn



  Department of Computer Science, University of British Columbia
  Vancouver 
  Canada

zilunpeng@gmail.com



  Alibaba-Zhejiang University Joint Institute of Frontier Technologies, College of Computer Science, Zhejiang University
  Hangzhou 
  China

bjj@zju.edu.cn



  Alibaba-Zhejiang University Joint Institute of Frontier Technologies, College of Computer Science, Zhejiang University
  Hangzhou 
  China
 
wcan@zju.edu.cn


Existing works for extracting navigation objects from webpages focus on navigation menus, so as to reveal the information architecture of the site. However, web 2.0 sites such as social networks, e-commerce portals etc. are making the understanding of the content structure in a web site increasingly difficult. Dynamic and personalized elements such as top stories, recommended list in a webpage are vital to the understanding of the dynamic nature of web 2.0 sites. To better understand the content structure in web 2.0 sites, in this paper we propose a new extraction method for navigation objects in a webpage.  Our method will extract not only the static navigation menus, but also the dynamic and personalized page-specific navigation lists. Since the navigation objects in a webpage naturally come in blocks, we first cluster hyperlinks into different blocks by exploiting spatial locations of hyperlinks, the hierarchical structure of the DOM-tree and the hyperlink density. Then we identify navigation objects from those blocks using the SVM classifier with novel features such as anchor text lengths etc. Experiments on real-world data sets with webpages from various domains and styles verified the effectiveness of our method.








<ccs2012>
<concept>
<concept_id>10002951.10003260.10003277.10003279</concept_id>
<concept_desc>Information systems Data extraction and integration</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003227.10003351</concept_id>
<concept_desc>Information systems Data mining</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10010147.10010257.10010258.10010260.10003697</concept_id>
<concept_desc>Computing methodologies Cluster analysis</concept_desc>
<concept_significance>300</concept_significance>
</concept>
</ccs2012>


[300]Information systems Data mining
[300]Computing methodologies Cluster analysis
[500]Information systems Data extraction and integration





Navigation Objects Extraction for Better Content Structure Understanding
    Can Wang
    December 30, 2023
========================================================================





§ INTRODUCTION

The explosive growth of the World Wide Web generates tremendous amount of web data 
and consequently web data mining has become an important technique for discovering useful information and knowledge. 
Among many popular topics in web data mining, extracting information 
architecture or content structures for a web site has attracted many research attention in recent years. 
Existing works mainly extract navigation menus from webpages to 
reveal the content structure of the site <cit.>. 
Many applications can be derived from the extracted content structure, including generating site map to improve information accessibility for disabled users, or providing content hierarchy in search results <cit.> etc. 

However, the increasing number of web 2.0 sites such as social networks, e-commerce portals etc. are 
turning the web from a static information repository into a dynamic platform for information sharing and interactions. 
As shown in Figure <ref>, the information architecture on these sites are characterized 
not only by the traditional static directory structure of the site, 
but also by the dynamic elements such as  the top reading list, recommended items etc. 
In fact, the dynamic nature of web 2.0 sites are better captured by these dynamic and personalized elements. 
But their importance are neglected in existing works of web structure extraction, 
which mainly focus on extracting static web site structures such as the navigation menus<cit.>, headings<cit.> etc. 



In this paper, we propose a new extraction method for navigation objects 
in a webpage to capture both the static directory structures and the dynamic content structures in a web site. 
It is a non-trivial task mainly because of the great diversities in webpage structures. Webpages come with 
various layouts, thus navigation objects in different webpages varies greatly in their presentation. 
Moreover, many navigation elements in a webpage nowadays  are generated dynamically, or customized for specific users. 

To overcome these difficulties, we attempt to develop a page-dependent extractor for navigation objects in a webpage. 
Our method is based on following observations for navigation objects, in a typical webpage: 
1) the navigation objects are naturally grouped in different hyperlink blocks, in which few other contents other than these hyperlinks exist; 2) the anchor text for these hyperlinks are usually short and well aligned. 
With these observations, the first step of our method is to cluster hyperlinks in a webpage into multiple blocks by exploiting 
features such as spatial locations of hyperlinks, the hierarchical structure of the DOM-tree and the hyperlink density etc. 

Then we identify navigation objects using the SVM classifier. 
Generally, the hyperlink blocks in a webpage can be divided into the following four categories:


  * Navigation Menu. Hyperlinks provide site-level navigation. 
They stay relatively invariant and can be directly mapped to the static directory structure in a website.

  * Navigation List. Hyperlinks provide page-dependent navigation and capture the dynamic and personalized content structures, 
such as recommended list etc.  

  * Content Hyperlink. Hyperlinks appears in the main content. 

  * Others. Hyperlinks include Ads, copyright information etc. 


Obviously, we intend to extract Navigation Menu and Navigation List in a webpage. 
The SVM classifier is trained with some well defined features, 
such as the number of hyperlinks, the mean and the variance of anchor text lengths etc. 
Experimental results in multiple real-world datasets verify the effectiveness of our method. 

The rest of the paper is organized as follows. We briefly	review related works in section 2. 
We describe our method in section 3 and 4, the part of clustering hyperlinks into blocks is in section 3 
and the part of classifying hyperlink blocks is in section 4. 
Then in section 5 we show our experimental setup and results followed by discussing the results. 
Finally, we present our conclusions and plans to future research in section 6. 



§ RELATED WORK

Our work is related to areas of web structure mining and web information extraction. 

Web structure mining. 
Web structure mining aims to study the hyperlink structure of the web.  
Some early works studied the structure of the web at large <cit.><cit.> 
and uncover the major connected components of the web. Others analyzed the generally properties related 
with the web graph, such as its diameter <cit.>, 
size and accessibility of information on the web <cit.> etc.  
PageRank <cit.> exploits the linkage information to learn the 
importance of webpages and becomes widely used in modern search engines. 

Recent works on web structure mining focused more on the local structures of the web graph.
Ravi et al. <cit.> used the hierarchical structure of URLs 
to generate hierarchical web site segmentation. 
Though the hierarchical structure of URLs was also used in many other works, such as <cit.>, 
the hierarchical structure of URLs does not reflect the web site organization accurately. 
Eduarda Mendes et al. <cit.> noticed that and thought navigation objects could 
reflect the web site structure better. 
They applied frequent item-set algorithms on the 
outgoing hyperlinks of webpages to detect repeated navigation menus and then used them to represent web sites. 
Keller et al. <cit.> also tried to use navigation menus to 
reveal the information architecture of web sites, but they extracted navigation menus in a very different way. 
They extracted navigation menus by analyzing maximal cliques on the web graph. 
Some works do not extract navigation objects directly, but they take into account the 
structural information navigation objects provide. For instance, 
when Cindy Xide et al. <cit.> clustered webpages, 
they considered parallel links which are siblings in the DOM-tree of a webpage 
and usually in the same navigation objects. 
However, these works only focus on the static structure of a web site represented by navigation menus etc. 
and neglect the dynamic structure represented by personalized page-specific navigation lists. 
These navigation elements is vital to understand the dynamic nature of web 2.0 sites.

Web information extraction. 
Information extraction from webpages has many applications. 
Most of the existing works focus on main content extraction from webpages and the early work about that can 
be traced back to Rahman et al. <cit.>. 
They segment the webpages into zones based on its HTML structure and extract important 
contents by analyzing zone attributes. 

Among many different categories of extraction methods, template-based ones are popular because they are highly accurate and easy to implement. 
They extracted content from pages with a common template by looking for special HTML cues using regular expressions. 
A different category of template-based methods used template detection algorithms 
<cit.><cit.><cit.><cit.>, 
in which webpages with the same template are collected and used to learn common structures. 
The major problem with template-based extractors is that different extractors must be developed for different templates. 
What's more, once the template updates, as frequently happens in many web site, the extractor will be invalidated. 

To overcome the limitations of template-based methods, many researchers attempted to extract 
content from webpages in a template-independent way. 
Cai et al. <cit.> proposed a vision-based webpage segmentation algorithm 
named VIPS to divide a webpage into several blocks by its visual presentation. 
Zheng et al. <cit.> presented a template-independent news extraction method based on visual consistency. 
Wang et al. <cit.> exploited more features about the relation between the news title and body by firstly extracting 
the title block and then extracting the body block.  Shanchan et al. <cit.> trained a machine learning model with multiple features generated by utilizing DOM-tree node properties and extracted content using this model.
Although these methods extract webpage content in a template-independent way, they still have to rely on some particular HTML cues (e.g., <table>, <td>, color and font etc) in their extraction, and thus are more easily affected by the underlying web development technologies.
Two recent works, CETR <cit.> and CETD <cit.> address this issue by identifying regions with 
high text density, i.e., regions including many words and few tags are more likely to be main content. 

As can be seen, most existing works of information extraction from webpages 
focus on main content extraction and they can not be applied to extracting navigation objects directly. 
Even the template-based methods cannot be used directly to extract navigation objects because 
navigation lists in webpages are usually generated dynamically and page-dependent.


§ CLUSTERING HYPERLINKS

Our work is motivated by the observation that the navigation objects are naturally grouped in different hyperlink blocks according to their purposes. To better illustrate our idea, we use a typical webpage, the home page of  Techweb[http://www.techweb.com] as an example. As shown in Figure <ref>, 
the hyperlinks in the webpage are obviously grouped in different blocks with their different visual presentation features. 




 §.§ DOM-tree


Before clustering hyperlinks in a webpage into blocks, we parse the webpage into a DOM-tree. 
Each webpage corresponds to a DOM-tree where detailed text, images and hyperlinks etc. are leaf nodes. 
An example of the DOM-tree is shown in Figure <ref>. 
The DOM-tree at the bottom of Figure <ref> is derived from the HTML code 
at the top right, whose webpage layout is at the top left. 


The DOM-tree is a hierarchical structure and it has three useful properties as follows. 
First, the relation between child node and parent node reflects their relation in 
the webpage layout, e.g., in Figure <ref> the node <p> and <img> are child nodes 
of node <div> reflects that text and image are included in the block corresponding to <div> in the webpage layout. 
Second, the relative positions of sibling nodes are preserved when they are displaying in the webpage. 
More specifically, if node a and node b are sibling nodes and a is at the left side of b on the DOM-tree, 
the displaying element corresponding to a must stay at the left side or the top of 
the displaying element corresponding to b in the webpage layout. 
Third, hyperlinks in the same block must have the same ancestor, 
which is the root node of the smallest sub-tree including that block. 
The above three properties are very useful when we cluster hyperlinks into blocks on the DOM-tree of a webpage.


 §.§ DOM-tree Distance

The central problem in clustering hyperlinks is to define a reasonable distance between them that well conforms to their visual presentation. The most intuitive choice is the Euclid distance between their locations on the webpage as rendered by browsers. However, obtaining these locations requires expensive computation cost. Moreover, locations for many hyperlinks can not be obtained without user interactions, e.g., in multilevel menus, the displaying locations of hyperlinks in the second or third level menus are only available after clicking their parent menus. 

To address this issue, we analyze the structure of the HTML code and use the DOM-tree distance 
to approximate the distance between two hyperlinks. We first traverse the DOM-tree of a given webpage 
with depth-first search order and index each node we encounter, starting from 1. 
Then we calculate the DOM-tree Distance (DD) between hyperlinks l_1 and l_2 as follow:

    DD(l_1, l_2)=| index(l_1)- index(l_2)|,

where index(l_i) means the index of hyperlink l_i. 

For two given hyperlink blocks B_1 and B_2, we define the gap between them as 
the minimum distance between hyperlinks in B_1 and B_2:

    gap(B_1, B_2)=min_i,jDD(l_i,l_j),

where l_i∈ B_1, l_j∈ B_2. 
We can use the internal node to represent a hyperlink block, which includes all hyperlink nodes in the corresponding sub-tree. 
In Figure <ref>, the node indexed with 2 can represent the hyperlink block 
including hyperlinks indexed with 6, 8 and the node indexed with 11 
can represent the hyperlink block including hyperlink indexed with 12.
The gap between these two hyperlink blocks is min{4, 6}=4.



 §.§ Hyperlink Density

Another important observation is that a hyperlink block usually includes few text except the text in hyperlinks.
We consequently define the Hyperlink Density HD(S) for a given layout block S,
which consists of one or more sub-trees of a DOM-tree: 

    HD(S)=#{anchor text in S}+ϵ/#{all text in S}+ϵ,

where #{anchor text in S} means the word number of the anchor text in all hyperlinks in S, 
#{all text in S} means the word number of all text in S and ϵ is the 
smoothing parameter to avoid dividing zero. We set ϵ=10^-10 in all our experiments.   



 §.§ Clustering on  DOM-tree

In the process of clustering hyperlinks into blocks, we make good use of the hierarchical structure of the DOM-tree 
and its properties.  The complete algorithm of clustering hyperlinks on the DOM-tree is shown 
in Algorithm <ref> with details. 


The core of our algorithm is a recursive process. For two given hyperlink blocks B_1 and B_2, 
in which the hyperlinks have been ensured in the same block respectively. 
If these two hyperlink blocks have the same parent and are neighbors, we try to merge them. 
When the gap between hyperlink blocks B_1 and B_2 is no larger than a given threshold gt and the Hyperlink Density of the 
potential hyperlink block consisting of B_1 and B_2 is no smaller than a given threshold hdt, we merge them into one hyperlink block. 
We only try to merge hyperlink blocks which have the same parent because hyperlinks in the same block should have the same ancestor. 
We only try to merge hyperlink blocks which are neighbors because the relative positions of sibling nodes are preserved 
when displaying in the webpage layout. 

The whole process executes from bottom to top on the whole DOM-tree and from left to right on each level of the DOM-tree. 
We have avoided a lot of  useless comparison by making good use of the hierarchical structure and properties of the DOM-tree.
 


 §.§ Threshold

We use the gap threshold (denoted by gt) and the Hyperlink Density threshold (denoted by hdt) to control the results of clustering. 
Due to the variety of webpages, gt and hdt vary greatly for different webpages. 
So we need an effective method to learn proper gt and hdt for each webpage. 


  §.§.§ Gap threshold


As we have explained in the previous sub-section, 
we only try to merge hyperlink blocks which are neighbors. 
So the proper value of gt is among the gaps between all neighbor hyperlink blocks with an additional 0. 
Though we cannot directly get the set S_b of all gaps between neighbor hyperlink blocks, 
we can easily get the set S_h of all distances between neighbor hyperlinks and we now prove that S_b=S_h. 
Firstly, each hyperlink is a hyperlink block which only contains one hyperlink, so S_h⊂ S_b . 
Secondly, as defined in equation (<ref>),  the gap between two hyperlink blocks 
is the minimum distance between hyperlinks in those two hyperlink blocks, 
which must be the distance between two neighbor hyperlinks, so S_b⊂ S_h. 
Above all, S_b=S_h is proved. 

Let DL denote S_h with an additional 0, the problem of calculating gt becomes choosing a proper value from DL:

(1) The gt should not be too large to avoid clustering all hyperlinks into very few big blocks;

(2) The gt should not be too small to avoid clustering all hyperlinks into too many small blocks. 

We choose the following i-th value in DL as gt after sorting DL in decreasing order:

    _imin(DL_i/DL_1+βi/length(DL))

where the DL_1 is the maximum value in DL, the length(DL) is the number of values in DL, 
1≤ i ≤length(DL). They are used to normalize the value of distance and the number of potential blocks. 
β is a tradeoff parameter and we set β = 1 in all our experiments.  



  §.§.§ Hyperlink density threshold


A hyperlink block includes few text except the text in hyperlinks. 
Intuitively, since the node with <body> tag is the root node of the DOM-tree 
and it contains no less other text than each hyperlink block. 
Let HD_B denote the Hyperlink Density of the whole webpage, then 

    hdt=γHD_B

perform the lower bound of Hyperlink Density of hyperlink blocks. 
γ≥0 is a tuning parameter and we set γ = 1 in our experiments. 



§ CLASSIFYING HYPERLINK BLOCKS


We train a SVM classifier using RBF kernel with some well defined features to identify navigation objects. 


 §.§ Features



  §.§.§ The number of hyperlinks

From our observation, the navigation object usually contains many hyperlinks, while other hyperlink blocks contain less hyperlinks. 
So the number of hyperlinks is a very useful feature to distinguish navigation object from non-navigation object. 
For a given hyperlink block B_i, we denote the number of hyperlinks in it as #B_i.



  §.§.§ Text length in hyperlinks

The length of anchor text is also very useful. 
On one hand, anchor texts in a navigation object are usually short, 
while hyperlinks in main content usually have relatively longer texts and hyperlinks 
in Ads etc. usually contain images without any text. 
So the mean of text length in a navigation object is usually small but not zero. 
On the other hand, the text in a navigation object is usually neat and the variance of these text lengths is small. 
For a given hyperlink block B_i, we denote the mean and variance of the text length in its hyperlinks 
as B_i^tm and B_i^tv respectively. 
We apply the re-implemented Gaussian smoothing <cit.> to the text lengths of hyperlinks in a DOM-tree 
to avoid sudden changes in the text lengths. 

Above all, for a given hyperlink block B_i, the feature vector of B_i is [#B_i, B_i^tm, B_i^tv]. 
Then the SVM classifier with RBF kernel is applied to classify B_i as navigation object or non-navigation object. 



 §.§ SVM Classifier

Support Vector Machine (SVM) is a famous supervised learning model.
In order to perform non-linear classification, we use the SVM classifier with RBF kernel <cit.>.

When using SVM classifiers, we need to calculate the distance between two points. 
Since the ranges of different features are significantly widely different, 
the features are normalized so that each feature contributes approximately in an equal proportion to the final distance. 
What's more, the normalization can also reduce the training time of SVM classifiers <cit.>.


§ EXPERIMENT


Experiments on real world dataset demonstrate the effectiveness of our method. 


 §.§ Date Set

In our experiments we use data from two sources: (1) dataset from CleanEval<cit.>; 
(2) news site data from MSS<cit.>. 

CleanEval: CleanEval is a shared competitive evaluation on the topic of cleaning arbitrary webpages
[http://cleaneval.sigwac.org.uk].  
It is a diverse dataset, only a few webpages are used from each site and the sites use various styles and structures. 
Moreover, this data set has many webpages including dynamic and page-dependent navigation elements. 

MSS: The dataset can be retrieved from Pasternak and Roth's repository[http://cogcomp.cs.illinois.edu/Data/MSS/]. 
This data set contains 45 individual websites which are further separated into two non-overlapping sets. 1) the Big 5: 
Tribune, Freep, Ny Post, Suntimes and Techweb; 2) the Myriad 40: the webpages which 
were chosen randomly from the Yahoo! Directory. 
The Big 5 includes five most popular news sites and the Myriad 40 
contains an international mix of 40 English-language sites of widely varying size and 
sophistication. 



 §.§ Performance Metrics



  §.§.§ Clustering hyperlinks

The results of clustering hyperlinks are identifications of several hyperlink blocks, 
and we compared them with the hand-labeled ground truth.

The first metric is the Adjusted Rand Index (ARI)  <cit.>. 
Rand Index (RI) is used to measure the agreement between the output results of clustering and the ground truth<cit.>. 
ARI is a adjusted-for-chance version of the Rand Index, which equals 0 on average for random partitions and 1 
for two identical partitions. So the larger ARI value means the better performance. 

The second metric is the Adjusted Mutual Information (AMI) <cit.>. Mutual Information (MI) is 
a symmetric measurement for quantifying the statistical information shared between the output results of clustering 
and the ground truth <cit.>. 
AMI is an adjustment of the MI to account chances, it ranges from 0 to 1 and larger value indicates better performance.




  §.§.§ Classifying hyperlink blocks


The performance of classifying hyperlink blocks is measured by standard metrics. 
Specifically, precision, recall and F_1-score are calculated by comparing the output 
of our method against a hand-labeled gold standard. 

Performances on each dataset are calculated by averaging the scores of above metrics over all webpages.
Note that every hyperlink in the webpage is considered as a distinct hyperlink even if 
some hyperlinks appear multiple times in a webpage.
 





 §.§ Implementation Details

All programs were implemented in Python language with the help of scikit-learn <cit.>. 
After parsing the HTML file of a webpage into a DOM-tree, we treated all elements with the tag <a> as hyperlinks, 
including some buttons and drop-down lists. We kept everything in a webpage without any preprocess, 
in order to show that our method can handle most noise in the webpage.


  §.§.§ Clustering hyperlinks

In order to properly evaluate the performance of our method on clustering hyperlinks, we compared our method's
performance with several common clustering algorithms, 
including Agglomeration, DBSCAN, K-Means and Spectral Clustering <cit.>. 
All algorithms use equation (1) to measure the distance between two hyperlinks. 
The Agglomeration initializes every hyperlink to a singleton cluster at the beginning. 
At each of the N-1 steps, the two closest clusters are merged into one singleton cluster. 
We implement this algorithm by ourselves and use single-linkage to measure the intergroup dissimilarity 
and use gt as the threshold to jump out of its iteration. 
The DBSCAN algorithm regards clusters as areas with high density separated by 
areas with low density. We use the implementation in scikit-learn by setting eps = gt,  min_samples=1,
where eps means the maximum distance between two samples for them to be considered as 
in the same neighborhood and min_samples is the minimum number of samples in 
a neighborhood for a point to be considered as a core point. 
The K-Means algorithm clusters data by trying to split samples into K groups. 
We use the implementation in scikit-learn by setting parameter K with the number of blocks in the ground truth. 
For Spectral Clustering ,we use the implementation in scikit-learn by setting parameter K with the number 
of blocks in the ground truth and use the one nearest neighbor method to construct the affinity matrix for Spectral Clustering. 

There are two versions of our method. CHD is the version of clustering hyperlink on DOM-tree 
without considering Hyperlink Density by setting γ = 0 in equation (<ref>) and  
CHD-HD is the version considering Hyperlink Density by setting γ = 1.


  §.§.§ Classifying hyperlink blocks

The standard deviation is σ=2 in the re-implemented Gaussian smoothing algorithm.
We classify each hyperlink block as navigation object or non-navigation object by using SVM with RBF kernel implemented in scikit-learn. 
The parameters in this SVM classifier are set as C=1.0 and γ =0.1, where C is the penalty 
parameter of the error term and γ is the kernel coefficient for RBF. 



 §.§ Results

For each data set, we randomly select 50% webpages as the training set and the remaining webpages as the testing set. 


  §.§.§ Clustering hyperlinks

Table <ref> and Table <ref> present the hyperlink clustering performance of  
different algorithms on the CleanEval, Myriad 40 and Big 5 data sets in the ARI metric and AMI metric respectively. 
The Big 5 has been broken down into it's individual sources. 

Comparing the average ARI values and AMI values over all data sets, 
our methods (including both CHD and CHD-HD) outperform all comparison methods. 
Actually, our methods have a better performance than most comparison methods when comparing 
ARI values and AMI values on individual data set. 
Moreover, our method is more reliable than the comparison methods since our method has a stable performances while comparison 
methods may collapse on some particular data sets. 
It is because that our method makes good use of the hierarchical structure of the DOM-tree as well as the distance information on DOM-tree. 
Finally, CHD-HD always performs better than CHD, especially on the dataset CleanEval, 
which has the greatest diversity and most dynamic and page-dependent navigation elements. 
That means besides the hierarchical structure of the DOM-tree, Hyperlink Density is also very helpful. 

Besides our method, the Agglomeration has the best performance, except the collapse of performance on Suntimes data set. 
Although it makes no use of any information from the hierarchical structure, it uses the fact that hyperlinks 
in a block are gathering together. The DBSCAN also uses this fact, so its performances are quite similar with 
the performance of Agglomeration. For instance, on the Myriad 40 and four sources in Big 5, the performance 
of DBSCAN is the same as Agglomeration. For K-Means and Spectral clustering, the performance is very poor, 
even though they have “cheatet” by using K obtained from the ground truth. 
Actually, finding the best K is very difficult. 

The average cumulative percentage of webpages for which the clustering performance of 
a particular method is less than a certain ARI value is plotted in Figure <ref>. 
The corresponding figure for AMI is in Figure <ref>. The slower the curve goes up from 
left to right, the better performance the corresponding method has. 
These two figures provide a more obvious illustration than Table <ref> and Table <ref>, 
in terms of the better performance that our method achieved on each ARI and AMI value relative to 
comparison methods. The majority of webpages that our method processed have a larger 
AMI or ARI value. Taking Figure <ref> as an example, 
for Agglomeration, DBSCAN, K-Means and Spectral clustering, the average percentages of ARI 
value lower than 0.6 are about 26%, 27%, 84% and 89%. At the same time, for CHD and CHD-HD, 
such percentage are only 13% and 10% respectively.






  §.§.§ Classifying hyperlink blocks

Table <ref> and Table <ref> present the results of classifying hyperlink blocks. 
It clearly shows that our method performs very well, not only on datasets with webpages from 
a single site (such as Tribune and Freep etc.) but also on datasets with webpages from 
various sites (such as CleanEval and Myriad 40). The results on 
CleanEval data set are less competitive because this data set has the greatest diversity. 
Moreover, the result in which CHD-HD is used for clustering is better than 
the result under clustering using CHD. That is very reasonable because 
CHD-HD can achieve better clustering results than CHD. 





 §.§ Discussion

To show the generalization ability of our method, we continuously increase the percentage of hyperlinks 
in training set to be used from 1% to 100%, and plot the corresponding F_ 1-scores. 
The incremental value is 1% when the percentage is less than 10%, 
and the incremental value is 10% otherwise. 
We used CHD-HD to cluster hyperlinks in this experiment. 
We can observe that even using very few hyperlinks as the training data, 
5% hyperlinks of whole training set for an example, the performance of our method is very impressive. 
This means our method has a strong generalization ability because it needs very few training data to perform very well.  
That brings great practicability to our method. 





§ CONCLUSIONS


In this paper we propose a new extracting method for navigation objects in a webpage 
to capture both the static directory structures and the dynamic content structures in a website.  
Our method will extract not only the static navigation menus, 
but also the dynamic and personalized page-specific navigation lists, 
including top stories and recommended list etc.
Based on the observation that hyperlinks in a webpage are naturally arranged in different blocks, 
we use a two-step process to extract navigation objects in a webpage by first clustering hyperlinks in a webpage into multiple blocks and then identify navigation object blocks from the clustering results using the SVM classifier. 
The effectiveness of our method is verified with experiments on real-world data sets. 

In addition to its effectiveness, the greatest strengths of our method are 
the simplicity of its implementation and its great practicability. 
Firstly, it has a very strong ability of generalization and needs very few training data to perform well, 
which gives it great practicability. Secondly, our method only requires the HTML file of a webpage and 
does not need any preprocess to handle noises in the webpage. 
Thirdly, our method does not rely on any special HTML cues (e.g., <table>, <td>, color and font etc.), 
which brings great stabilization over time. 

There are several interesting problems to be investigated in our future work:
(1) we will consider using more features in clustering hyperlinks and classifying hyperlink blocks without injuring the simplicity of our method; 
(2) we may try to achieve similar performance without any training data, which makes the method much easier to use; 
(3) we can incorporate additional information in our method, such as the cliques in the web graph, 
to further improve the understanding of content structures in websites.




§ ACKNOWLEDGMENTS

This work is supported by Alibaba-Zhejiang University Joint Institute of Frontier Technologies,  
Zhejiang Provincial Soft Science Project (Grant no. 2015C25053), 
Zhejiang Provincial Natural Science Foundation of China (Grant no. LZ13F020001), 
National Science Foundation of China (Grant no. 61173185). 

ACM-Reference-Format
 

