HTML boilerplate code is used on webpages as presentation directives for a browser to display data to a human end user. For machines, our community has made tremenduous e orts to provide querying endpoints using agreed-upon schemas, protocols, and principles since the avent of the Semantic Web. These data lifting e orts have been some of the primary materials for bootstrapping the Web of data. Data lifting usually involves an original data structure from which the semantic architect has to produce a mapper to RDF vocabularies. Less e orts are made in order to lift data produced by a Web mining process, due to the di culty to provide an e cient and scalable solution. Nonetheless, the Web of documents is mainly composed of natural language twisted in HTML boilerplate code, and few data schemas can be mapped into RDF. In this paper, we present CommentsLifter, a system that is able to lift SIOC data from user-generated comments in Web 2.0.
The SIOC ontology [
In this paper we present CommentsLifter, a web-mining approach that aims at extracting users' comments directly from HTML pages, in order to circumvent 1 http://sioc-project.org/exporters
the exporter issue. The comments are identi ed in webpages by mining frequent induced subtrees from the DOM , and using heuristics allow to discriminate the di erent eld of the comment (username, date, : : :). This approach does not require any a priori knowledge of the webpage. We empirically evaluated our approach and obtained very good results.
The paper is structured as follows. The next section presents related works on both structuring data into semantic web formats and web mining approaches. Section 3 presents a formalisation of the problem and recalls some theoretical tree mining results. Section 4 details the di erent steps of CommentsLifter, followed by experimental results. Finally, section 6 concludes. 2
Converting existing format of data into RDF is a cornerstone in the success of the
semantic web. The W3C maintains a list of available RDFizers on its website
3. Input data can be either structured or unstructured. In the former case, if
the semantics of the data can be extracted, then the conversion can take place
without human intervention [
been performed in [
Several techniques have been developed for web extraction. In [
The purpose of our work is to provide a solution for the leverage of Linked Data using the SIOC schema from user generated comments on webpages, without any a priori knowledge on the webpage. Our main assumption is that comments on a given webpage (even at website scale) are embedded in the same HTML pattern. This assumption is well ful lled in practice since comments are usually stored in a relational database and exposed into HTML after an automatic processing step. Therefore our goal is to automatically determine the HTML pattern that is used to expose the comments and then to identify the relevant information in the content to ll SIOC instances.
Basically a comment is a sioc:Post contained in a sioc:Forum container. We identi ed the following subset of the core-ontology properties of sioc:Post to be relevant for the extraction (we marked with * the mandatory properties and relationships) : sioc:content *: text-only representation of the content dc:terms: title of the comment dcterms:created : creation date
and relationships : sioc:has creator *: points to a sioc:UserAccount which is the resource sioc:has container *: indicates a sioc:Container object sioc:reply to: links to a sioc:Post item sioc:has reply : links to sioc:Post items
The sioc:Container pointed by sioc:has container can be from di erent types in our case. We consider extraction from user reviews (sioct:ReviewArea), posts on forum (sioc:Forum), comments from blogs (sioct:Weblog ), Q&A answers (sioct:) or generally for newspaper discussion (sioc:Thread ). However, distinguishing these di erents subclasses of sioc:Container would require classi cation from the webpages we intend to perform extraction on. This is out of the scope of our paper, we will therefore uniformally consider the container as an instance of sioc:Container. Similarly there exists subclasses of a sioc:Post for each container. As for the container, our algorithm will output sioc:Post items.
To summarize, our problem is the following : in order to generate SIOC data from raw HTML, we must identify the di erent items (sioc:Post ) and their conversational relationships (sioc:reply to and sioc:has reply ). For each item we must identify the user (sioc:UserAccount ), the content of the post (sioc:content ) and when possible the date and the title. 3.1
In the case of product listing extraction, the goal is to extract frequent subtrees that are identical in the page. For this purpose, a bottom-up subtree mining objective is su cient. For selecting a feature among mined items, for example title and price, a lter on the leaf nodes can be applied. In the case of comments extraction, the patterns can be nested. Assuming that the pattern we are looking for is [a[p; br; p; div]], if we encounter a reply to a comment, i.e. nested instances in the pattern, the tag tree for the comment and its answer could be as follows : [a[p; br; p; div; [a[p; br; p; div]]]]. In the case of a single comment we will encounter our pattern [a[p; br; p; div]]. We observe that nodes can be skipped horizontally along with their descendants.
In frequent subtree mining, three types of subtrees are distinguished :
bottomup, induced and embedded. Figure 1 depicts these di erent subtrees. For more
details on frequent subtree mining, we refer the reader to [
We observed empirically that instances are nested in the way we described previously : the direct parenting relation is preserved. Consequently induced subtree is a su cient type of subtree for our purpose. Embedded subtree mining could also be used, however since the algorithms complexity grow with the complexity of the pattern to mine, induced subtree mining is de nitely more appropriate. The main advantage of subtree mining over existing works is that it provides a mine once extract many approach. In order to mine large websites, one would need to mine the pattern from only one webpage from each site and could later extract data by simple pattern matching on other pages, thus D
B E saving large amount of computational resources and time. In the next section, we present CommentsLifter, our approach to comments' extraction based on frequent subtree mining. 4
We now start the description of CommentsLifter. This section presents the different steps of our algorithm. The underlying idea of CommentsLifter is to use simple observations on Web page structures to reduce the candidate set generation. This allows us to minimize the error rate while selecting the winning pattern, and to contribute to the runtime performance optimization objective. To extract comments from a Web page, CommentsLifter uses seven steps: Document preprocessing, Frequent subtrees extraction, Clustering, Merging, Pattern expansion, Winner selection, Field extraction, Data extraction. In the next subsections we detail the process followed in each step of our algorithm. 4.1
Recommendations issued by the W3C aim at specifying the languages of the World Wide Web, with various versions of HTML and CSS. While pages following these recommendations produce clean DOM trees, they represent only 4.13 % of the Web pages5. The remaining pages are made up of wrongly formatted HTML code that is often referred to as "tag soup"6. Due to the large portion that these pages represent, Web browser engines are able to handle malformed HTML tags, improperly nested elements, and other common mistakes. In our algorithm, the rst step is to convert any input HTML document (malformed or not) and to output a well-formed document as a DOM tree. For this purpose, any dedicated library (Jsoup7, Jtidy8) or browser engine can be used. 5 http://arstechnica.com/Web/news/2008/10/opera-study-only-4-13-of-the-Web-isstandards-compliant.ars
4.2
The next step of our algorithm consists of the generation of a rst candidate set.
For this purpose we extract frequent depth-two trees from the DOM and store
them in a cardinality map (an example is given in Table 1). The basis of our
approach is to select patterns with a depth of two that will be expanded into
larger patterns (empirical results in Section 5 show that the average depth of
a comment pattern is 4.58). For this purpose, a tag tree is generated from the
preprocessed DOM. CommentsLifter traverses the tree in a top down fashion
and stores the encountered trees of size two (each node that has children, along
with its children). The results are sorted, as presented in Table 1. Candidates
with less than two occurrences are discarded, since we assume that there are at
least two comments. The same assumption is made for instance by [
Count 13 12 10 8 Tree div[a;br;i;p] ul[li;li] div[p;p] div[p;p;p]
Table 1. Example of two depth candidates.
At this stage our candidate set is initialized and contains the instances of comments we are looking for. 4.3
Comments in a Web page appear in a continuous manner, so it is very unlikely that comments are stored in di erent branches of the DOM tree. We did not encounter the case of split comments in di erent subtrees during our experiments. In fact, comments are organized in a tree structure, where the beginning of the comments block is the root of the tree. Since comments are located in the same subtree, we proceed to a clustering phase of the occurrences for each pattern.
In this step, we aim at clustering co-located instances of the same pattern. In other words, the algorithm builds the pairs (pattern; Instances), where each pattern is associated with a set of instances matching it that are located in the same subtree and close to each other. Consequently, one pattern can be associated multiple times with a unique set of instances, whose member is distinct from any other member of another associated set to the pattern. This means that each pair (pattern; Instances) is splitted into di erent (pattern; Instances) where the instances in Instances do belong to the same subtree in the DOM. The basis of our algorithm is a distance-based clustering.For each given pattern, the algorithm sorts its instances along their depth in the tree. At each depth, we check for each instance if it has a parent in the previously found (pattern; Instances). For the remaining instances, we cluster them using a classical node distance in trees : d(a; b) 2 N is the length of the shortest path between the nodes a and b. After building the set of (pattern; Instances), we remove elements where the cardinality of instances is equal to one.
For example, running our algorithm on the tree provided by Figure 2 with the pattern ul[li; li] would produce two pairs (pattern; Instances) that are depicted with dotted and dashed boxes in the same gure.
lllllllllRRRRRRRRR div : : : a yyyyyyEEEEEE ul yyyyyyEEEEEE li li
ul yyyyyyEEEEEE li li
div _ _ _ _ _ _ _
ul yyyyyyEEEEEE li li _ _ _ _ _ _ _
At the end of this step, CommentsLifter holds the set of pairs (pattern; Instances) that matches a pattern to a set of co-located instances in the DOM tree. In the next step, we try to identify mergeable patterns from this data structure. HTML patterns that contain comments often have a depth greater than two (see Section 5 for more details). Consequently our candidate set may at this step contain pairs of (pattern; Instances) that belong to the same global pattern, that we did not discover yet because the pattern expansion process will occur later. Instead of discovering the same pattern from di erent candidates, we aim at merging these candidates beforehand for optimization.
For this purpose we perform a pairwise comparison between the sets of instances. We process a merge between sets of instance when every element of a set S1 is topped by an element from the other set of instances. An element is topped by another if the latter is a parent of the former. If a set of instances is topped by another set, we discard this set and restart the process until no further updates to the candidate set are performed.
Algorithm 1 presents this merging process. After this step, the candidate set is again drastically pruned since we eliminated all potentially duplicate patterns for the expansion phase. This process, together with the previous clustering process, are the key phases of our algorithm since they discard both duplicate and irrelevant candidates.
Algorithm 1: M ergeP atterns : Merge similar pattern
Data: A collection of couple (Pattern,Instances) Input where all patterns are di erent, minDepth the mininum depth of the instances in the DOM tree Result: A collection Candidates of (pattern,Instances) where similar couples have been merged recursion f alse; Candidates ;; for i : 0 : : : Input:size do for j : i : : : Input:size do //Depth of the highest common element ; commonDepth depth(HighestCommon(Input[i]:Instances;; Input[j]:Instances)); //Save useless computation ; if commonDepth < minDepth then
continue ; end end return Candidates; end Small setW ithLessInstances(Input[i]; Input[j]); Large setW ithM oreInstances(Input[i]; Input[j]); if 8k 2 Small:Instances; 9l 2 Large:Instances; isP arentOf (l; k) then Candidates Input n Small; //Restart the merging process; M ergeP atterns(Candidates); //Cut the current call; break;; else Candidates
Candidates [ Large [ Small Since the candidate set contains simple patterns (i.e. of depth two), we process a pattern expansion to discover the fully matching patterns. Patterns may be expanded in both directions, towards the top and the bottom of the tree.
For each candidate (pattern; Instances), we distinguish two cases. In the rst case every instance is at the same depth in the tree, this is the case of product listing extraction that we call the at case. This is the case of bottomup subtree mining (see Figure 1). The second case also called the nested case is the one where instances belong to the same subtree but at di erent depths, this is the case of induced subtrees in Figure 1 . Top expansion is straightforward, we check if the type of the parent node (i.e. HTML markup tags) for every instance is the same, in this case we expand the pattern with the new parent node and update the instances consequently. This process is executed until all the instances do not share the same tag as parent node or if the same node (in sense of label in the tree, not HTML markup tag) is the parent of all instances. This process is the same for both nested and at cases.
div _ _ _ _ _ _jj_jj_jjj_jj_jjU_UU_UUU_UU_UUU_ _ _ _ ul //// div : : : li li p li li p _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Once a pattern is expanded in the top direction, the bottom expansion takes place. This bottom expansion in the at case, similar to the top expansion is simple since top-down subtrees are easy to extract. One just needs to traverse the instances trees in a top-down lefmost direction, looking for nodes that are shared by all instances. Once a node is not present in every instance the algorithm uses backtracking to select the next sibling, and then continues its process.
However the nested case is not trivial since we look for embedded subtrees.
Standard algorithms such as AMIOT [
Recurring structures competing with the comments pattern in the candidate set
are usually menu elements, links to other articles. In [
Our experimentation showed that instances with a link density greater than 0:5 (Kohlschutter found 0.33 for news article) are always boilerplate. Short comments in very complex HTML boilerplate patterns can produce instances with a quite high link density. We empirically observed that links are on the username or on its avatar and link to a pro le page. Consequently we discard candidates where the average link density is above 0:5.
For the remaining candidates their score is given by the following formula: Score(p; I) = lgt(I) v u u t n 1 1 n X lgt(I) j=1 lgt(Ij ) 2 (1)
The above formula computes the average text length times its standard
deviation. This heuristic promotes candidates where the instances have longer
text length with variable length. Finally we did not use heuristics based on
a lower bound of words (as in [
Once the HTML pattern containing comments has been selected, the next step of our algorithm consists of extracting the related SIOC elds as we described in section 3. Two elds are always present in a comment : the username and the content of the comment. From our observations on various websites (online press, Q&A, blogs, reviews), two other elds appear often. Firstly the date when the comment has been posted occurs in 97.95 % of the cases (See Table 2). Comments less often have a title, but the percentage we measured (24.48 %) remains high enough to be of interest. We voluntarily skipped the extraction of rare elds (vote on comments, account creation date) because of their few occurrences and the fact that they complicate the whole eld's identi cation process. From our observations, we noticed that content and title are always contained in their own HTML markup tags, i.e. it is very unlikely to see the title and the content in the same div. However we noticed that username and date often occur between the same markup tag, for example we often encountered comments elds such as <div>John, May 25, 2012 at 5:00 p.m</div>. Therefore we apply the following procedures : rst, identifying the date eld within the pattern. We store the location of the date in the pattern and remove dates in every instances. For instance, the previous example will become<div>John</div>. At this point we are sure that the elds we are looking for will be in distinct nodes of the pattern. Date parsing Date parsing library such as JodaTime9 and JChronic10 perform well on extracting date from messy data. These libraries takes a String as input and return a Date object. However they do not o er the feature of returning the original text without the substring containing the date. Therefore we developed our library, using features and heuristics from both of the above mentioned libraries, that o ers the date string removal feature.
Fields selection Our heuristic is based again on simple observations. We know that every comment contains at least a username and a content, with date and title being optional. For each leaf of our pattern, we compute the following measures over its instances : percentage of date found, average text length, standard deviation of text length, text entropy and average word count, standard deviation on word count. Using these values, we build two candidate sets, the rst one for the date, and the other one for title, content and username. We distinguish these elds using the fact that title, content and username are unstructured text, however dates have a particular structure (containing year, days, : : :).
A node in the pattern is a candidate for the date eld if its percentage of date found is over 0:7 (to take into account the fact that date extraction is not perfect), has more than two words and has a coe cient of variation on the word count that is inferior to 0:2. This latter condition requires that the number of words is very close from one instance to another. We did not set the value to zero to avoid discarding elds where the date has a variable length, for example one hour ago and yesterday. From these candidates, we pick the eld with the highest entropy in order to discard constant elds that may have been recognized as a date. However if the set is empty, then no dates are speci ed for the comments, in practice this happens very rarely.
The second candidate set should contain only nodes that instances own textual data. For this purpose we discard the nodes in the pattern where the variation of text entropy is equal to zero (constant text in every instance). Since we know that the node containing the content must be present within this set, we aim at identifying this eld in the rst place. Luckily the content is very simple to identify since it contains the most words, has a very variable length and word count. In the practice, selecting the node having the highest word count average is su cient. Once the content has been removed from this candidate set, we rst check its size. If the size is equal to one, the remaining candidate matches the username. In the case where two candidates are present, we have to distinguish between username and title. Usernames are very short names, usually one or two words, and are then in average shorter than the title. If two elds are present, the shorter is identi ed as being the username and the longest is then the title.
This section presents the evaluation protocol of CommentsLifter as well as our experiment's results. We rst detail the experimental setup, which is a bit particuliar for comments extraction due to the large use of AJAX. Finally we present global and detailed results for both at and nested cases. Many Web pages handle comments using AJAX, consequently downloading raw HTML along manual ground truth construction is not su cient for building the dataset. To circumvent this issue we developed two components: Firefox Extension We implemented a Firefox extension that sends the current
DOM (after browser-side Javascript processing) to a Web server. Web Server The server receives the DOM from the browser through a POST request on a servlet, then runs CommentsLifter and presents an evaluation form along with the extracted comments. The user is asked to evaluate the pertinence of the extraction. We distinguish three cases for the result. We used Jena11 to generate the SIOC output. 5.2
The results obtained from our evaluation are given in Table 2 and Table 3. Table 2 presents extraction results of the pattern mining part (steps 1 to 6 of 11 http://jena.apache.org/ the algorithm) whereas Table 3 presents the eld identi cation results (step 7). The rst six steps of the algorithm present very good results, with a global F1 score over 92%. Concerning eld identi cation we rst present the occurrence of the di erent elds over our dataset. Username and content are always present, while the date is not far from being present in every comment. However titles are to be found in one quarter of the comments. The evaluation accords to the heuristics we describe in section 4.7. Content extraction is a straightforward task since it is easy to "measure" di erences with other elds, our algorithm performs perfectly at this task. Date parsing is no easy task, however our algorithm still performs well with an identi cation rate of 83.67 %. However we note that while the rest of the process is language agnostic, date parsing libraries are designed to work with western languages (English, German, french, spanish, : : :) but may fail with other languages, especially with non latin alphabet. 6
In this paper, we presented CommentsLifter, an algorithm that extracts users' comments and outputs SIOC data. Our algorithm combines mining induced subtrees from the DOM with simple yet robust heuristics to select the pattern containing the comment as well as identifying several elds within the pattern. The empirical evaluation presents very good results, for both extraction and eld identi cation. We successfully extracted comments from various types of Web sites, without a priori knowledge, such as online newspapers, forum, user reviews, blogs and we were able to reconstruct the conversations.
Further research will focus on re ning the category of the extracted container, in order to determine whether the discussion takes into a forum, Q&A, blog or review area.