A Novel Approach to Web Information Extraction

A Novel Approach to Web Information Extraction Antonia M. Reina Quintero(B), Patricia Jim´enez, and Rafael Corchuelo ETSI Inform´atica, Avda. Reina Mercedes, s/n., 41012 Sevilla, Spain {reinaqu,patriciajimenez,corchu}@us.es Abstract. Business Intelligence requires the acquisition and aggregation of key pieces of knowledge from multiple sources in order to provide valuable information to customers. The Web is the largest source of information nowadays. Unfortunately, the information it provides is available in semi-structured human-friendly formats, which makes it difficult to be processed by automated business processes. Classical propositional and ILP machine-learning techniques have been applied for this purpose. However, the former have not enough expressive power, whereas the latter are more expressive but intractable with large datasets. Propositionalisation was devised as a means to provide propositional techniques with more expressive power, enabling them to exploit structural information in a propositional way that allows them to be efficient. In this paper, we present a proposal to extract information from semi-structured web documents that uses this approach. It leverages a classical propositional machine learning technique and enhances it with the ability to learn from an unbounded context, which helps increase its precision and recall. Our experiments prove that our proposal outperforms other stateof-art techniques in the literature. 1 Introduction Business Intelligence can be defined as the process of finding, gathering, aggregating, and analysing information for decision making [15]. The World Wide Web is an increasingly important data source for business decision making; however, extracting information from the Web remains one of the challenging issues related to Web business intelligence applications [6]. Web business intelligence is an emerging type of decision support software that “leverages the unprecedented content on the Web to extract actionable knowledge in an organizational setting” according to [20]. Web business intelligence applications should have access to structured data that could be easily extracted and incorporated into decision-making applications. However, the Web provides textual information in semi-structured formats, but those formats are intended for human consumption, which makes them difficult to be processed automatically for business purposes. Web information extractors are tools designed to extract the information of interest from such documents in a structured format. c Springer International Publishing Switzerland 2015 W. Abramowicz (Ed.): BIS 2015, LNBIP 208, pp. 152–161, 2015. DOI: 10.1007/978-3-319-19027-3 13 We focus on supervised rule-based information extractors, which are generalpurpose algorithms that are configured by means of extraction rules that are learnt from labelled examples that must be provided by a user. Such rules are actually classifiers, since they get a piece of text or a DOM node as input and predict a user-defined class for it. Unfortunately, many existing proposals build on specific-purpose machinelearning techniques that were specifically tailored to the problem of extracting web information. This makes it difficult to adapt them as the Web evolves because the features of the documents on which they rely and the techniques used to analyse them are built into the proposals. Machine-learning techniques that come from the field of concept learning have proven to be the only approaches that can scale along a number of distinct sources and can infer knowledge in a general way. There exists two approaches: relational and propositional learning. The former attempts to learn first-order rules that generalise a set of examples by using rich representations that allow to exploit both attributive features of the examples and their relationships, whereas the latter only use attributive features. Therefore, relational systems are preferable since they allow to learn more expressive rules than their counterparts [9]. Unfortunately, a major drawback of relational systems is the expensive learning process, which becomes intractable with large datasets [1]. Propositionalisation [11] is a different way to conduct relational learning efficiently. It maps a relational representation onto features in propositional form, that is, in an attribute-value representation that is amenable for conventional data mining systems. Although propositionalisation has some inherent limitations, such as the inability to learn recurrent definitions, there are several reasons for using this process, the most important ones are: it deals with the combinatorial explosion of the number of potential features; it can leverage the existing knowledge regarding propositionalisation; and, finally, our results prove that our approach is very competitive in terms of effectiveness and efficiency since it outperforms the results obtained by classical and new proposals in the literature for web information extraction. To the best of our knowledge, no propositionalisation system has been developed in the field of web information extraction. In this paper, we present the first such proposal in the literature. We have performed an extensive experimentation that proves that it outperforms other state-of-the-art proposals, which proves that it is very promising. The intuitive idea behind our approach, named Yebra, is the following: it relies on a training set that consists of a set of nodes to extract and a subset of nodes that should not be extracted. Then, it learns the best possible rules by using only the attributive features of the nodes in the training set. If the rules thus learnt are perfect, the process finishes. Otherwise, Yebra tries to find better rules by combining attributive features of the nodes in the training set with attributive features of their neighbour nodes. Neighbour nodes are reached by applying relational features such as next sibling or parent, amongst others. At each step and whilst no perfect rules are found, the system continues combining attributive features from the previous step with attributive features of increasingly distant neighbour nodes. Algorithm 1. Yebra’s main procedure. 1: procedure Yebra(dataSet, relations) 2: trainingSet ←createT rainingSet(dataSet) 3: testSet ←dataSet 4: resultRule ←learnRule(trainingSet, testSet) 5: resultBindings ←{(node, null, null)} 6: expansion ←resultRule 7: while ¬isP erfect(resultRule, testSet)and expansion =null do 8: (expansion, resultBindings, trainingSet, testSet)← findExpansion(resultRule, resultBindings, trainingSet, testSet, dataSet, relations) 9: if expansion =null then 10: resultRule ←expansion 11: end if 12: end while 13: return (resultRule, resultBindings) 14: end procedure The rest of the paper is organised as follows: Sect. 2explains our proposal; then the experimental results are detailed in Sect. 3; Sect. 4presents the related work; Sect. 5concludes the paper. 2 Description of Our Proposal In this section, we first describe our training and test sets, then report on Yebra’s main algorithm, and then on the algorithms to learn a rule and to expand it. 2.1 The Training Set and the Test Set The training set is a bag of vectors. Each vector refers to a node in the DOM tree, for which it holds its set of attributive features (Aij) and its class (Ci). An initial training set is created by the createTrainingSet function (Line 2), which works as follows: first, it adds the positive examples to the training set. Positive examples are those vectors whose class is not null. Then, it adds some negatives examples (not all) to the training set. The negative examples are the ones whose class is null. The negative examples added to the training set are computed amongst the negative examples that are the nearest neighbours to the positive examples that belong to the dataset. That is, for every positive example, Yebra finds its knearest neighbours and adds them to the training set. Note that this process helps Yebra to better discover the frontier amongst positive and negative examples. Experimentally, we have found out that setting kto three is a good trade off between efficiency and effectiveness. 2.2 The Main Procedure Algorithm 1presents the main procedure in Yebra. The first step is to find the best rule using attributive features only (Lines 2–4). Then, it iterates until the rule being learnt is perfect or there are not any further expansions (Line 7). An expansion is a new rule learnt by adding extra information to the training set. The extra information is added as new components to the vectors of the training set (and also the test set). The new components are the attributive features of those nodes that are reachable by applying a relational feature or a combination of relational features. Thus, the existence of an expansion means that Yebra has found a rule that improves on the previous one. But it has to check if this new rule can also be improved (that is, if a new, better classifier can be learnt by adding more features of the neighbours to the training set). If the rule cannot be improved, then there are no expansions, which means that Yebra has found the best possible rule. Finally, note that in each iteration resultRule contains the best rule found so far. If it is not perfect, but can be improved, Yebra continues with the next iteration. If it is not perfect and cannot be improved, Yebra stops and returns it. 2.3 Learning a Rule Once the initial training and test sets are created, Yebra has to learn the best possible rule using procedure learnRule (Algorithm 2). It works on a training set and a test set and returns a rule. The intuitive idea behind this procedure is the following: first, it learns a rule, if the rule is perfect, then the procedure stops and returns that rule; otherwise, the training set is modified by adding the misclassified examples, and the process is repeated until the rule is perfect or the rule does not improve on the previous one. That is, the training set is enriched iteratively with misclassified examples, which helps learn better rules. The procedure starts by balancing the training set (Line 2). This step is necessary because function learnClassifier (Line 3) uses a PART learner [21], which does not have good results with unbalanced datasets. The balance function computes the number of elements of the majority class, and it then replicates as many examples of each class as needed to obtain a training set that has approximately the same number of examples of every class. After that, it learns a PART classifier from the balanced training set (Line 3). Then, the set of misclassified examples is computed using this classifier and the test set. Note that although the classifier has been learnt from the input training set (which is a subset of the nodes in the original dataset), the misclassified examples are computed from the test set (which includes all of the nodes in the original dataset). Then, the procedure iterates until the rule is perfect (the misclassified set is empty) or the new rule does not improve on the old rule. In each iteration: 1. A new training set is computed. It is the union of the vectors included in the previous training set and the vectors related to the nodes that have been misclassified. 2. A new classifier is learnt from the new training set. 3. A new set of misclassified examples is computed for the new classifier. If the new classifier is perfect, the procedure ends and returns the new classifier. If the new classifier is not perfect and does not improve on the old classifier, the Algorithm 2. Procedure learnRule 1: procedure learnRule(trainingSet, testSet) 2: oldT rainingSet ←balance(trainingSet) 3: oldRule ←learnClassifier(oldT rainingSet) 4: oldMisclassified ←findMisclassified(oldRule, testSet) 5: isP erfect ←oldMisclassified =∅ 6: improves ←true 7: while ¬isP erfect and improves do 8: newT rainingSet ←balance(oldT rainingSet ∪oldMisclassified) 9: newRule ←learnClassifier(newT rainingSet) 10: newMisclassified ←findMisclassified(newRule, testSet) 11: isP erfect ←oldMisclassified =∅ 12: improves ←| newMisclassified |<|oldMisclassified | 13: if isP erfect or improves then 14: oldT rainingSet ←newT rainingSet 15: oldRule ←newRule 16: oldMisclassified ←newMisclassified 17: end if 18: end while 19: result ←oldRule 20: return result 21: end procedure procedure ends and returns the old classifier. Finally, if the new classifier is not perfect but improves on the old one, the process is repeated to see if the new classifier can be improved. (Rule R1improves on rule R2if R1misclassifies less examples than R2.) 2.4 Expanding a Rule Once Yebra has learnt the best rule using only attributive features, it tries to improve it by adding extra information to the training set. The extra information is obtained by navigating trough the DOM tree by means of relational features, in such a way that if Niis a vector belonging to the training set with components (Ai1,Ai2,...,Ain,Ci), and Njis a vector belonging to the dataset with components (Aj1,Aj2,...,Ajn,Cj), and Rpis a relational feature such that Nj=Rp(Ni), then an expansion of Niusing Rpis the vector (Ai1,Ai2,...,Ain,Aj1,Aj2,...,Ajn,Ci). To deal with expansions Yebra relies on so-called bindings. A binding is a triplet (target, relation, source)inwhichtarget and source are variable names, and relation refers to a relational feature. We can think of a binding as an expression similar to target ←relation(source), that is, a binding maps a source node onto a target node using a relational feature. The procedure responsible for expanding the rule, and as a consequence, the training and test sets, is findExpansion (Algorithm 3). findExpansion works on a rule, a set of bindings, the training set, the test set, the original dataset, and a set of relational features. If findExpansion Algorithm 3. Procedure findExpansion 1: procedure findExpansion(rule, bindings, trainingSet, testSet, dataSet, relations) 2: resultRule ←null 3: resultBindings ←null 4: resultT rainingSet ←null 5: resultT estSet ←null 6: for all binding b in bindings while ¬isP erfect(resultRule, testSet)do 7: for all relation r in relations while ¬isP erfect(resultRule, testSet)do 8: newBinding ←(freshV ariable(),r,target(b)) 9: newT rainingSet ←expand(trainingSet, newBinding, dataset, relations) 10: newT estSet ←expand(testSet, newBinding, dataset, relations) 11: newRule ←learnRule(newT rainingSet, newT estSet) 12: if gain(rule, testSet, newRule, newT estSet)> gain(rule, testSet, resultRule, resultT estSet)then 13: resultRule ←newRule 14: resultBindings ←bindings ∪{newBinding} 15: resultT rainingSet ←newT rainingSet 16: resultT estSet ←newT estSet 17: end if 18: end for 19: end for 20: return (resultRule, resultBindings, resultT rainingSet, resultT estSet) 21: end procedure cannot find an expansion that improves on the input rule, it returns a null expansion; otherwise, it expands the training and test sets, the bindings, and returns the new, improved, rule. Yebra starts with the initial binding (node, null,null) (Algorithm 1, Line 5), that is, the algorithm starts with a variable named node, and no relation involved. So the first time findExpasion is executed, the set of bindings has only one element, the initial binding. First, findExpansion initialises with null values the variables resultRule, resultBindings,resultTrainingSet,andresultTestSet. Note that if no expansions can be found, resultRule remains with a null value. Then it iterates on the Cartesian product of bindings and relations. For each pair: 1. It creates a new binding. The new binding is the result of applying the relational feature to that binding. 2. It expands the training set. This implies the expansion of every vector in the training set, by applying the relation specified by the new binding. 3. It expands the test set. This implies the expansion of every vector in the test set, by applying the relation defined in the new binding. 4. It learns a new rule with the expanded training and test sets. Note that we are learning the best possible rule for the expanded training set. 5. It checks whether the new rule improves on the previous one. In that case, it stores the new rule, the expanded training and test set, and the new binding. To evaluate if the rule learnt by means of an expansion is better than the rule obtained using another different expansion, Yebra relies on the information gain function [14]. Thus, when the findExpansion procedure is called, the best rule obtained by expanding the training set is computed (if there is one). After that, Yebra calls findExpansion again to check further expansions can improve on the current rule. 3 Experimental Analysis To prove that our proposal is worth from a practical point of view, we have performed a series of experiments in which we have collected the usual effectiveness measures, namely: precision (P), recall (R), and the F1 measure (F1). We have developed a Java 1.7 implementation of Yebra and we have run it on a four-threaded Intel Core i7 computer that ran at 2.93 GHz, had 4 GiB of RAM, Windows 7 Pro 64-bit, Oracle’s Java Development Kit 1.7.002, and Weka 3.6.8. We used a collection of 23 datasets that provides 850 web documents regarding books, movies, conferences, cars, doctors, sports, restaurants, and so on. The empirical comparison was performed with two classical proposals (SoftMealy [7] and WIEN [12]) and three recent proposals (RoadRunner [4], FiVaTech [10], and Trinity [18]). Regarding Yebra, we selected six documents from each site to learn an extraction rule, and then validated the result using the remaining documents; in average, we used 22.78 ±9.87 % of the datasets for training purposes and the rest for validation purposes. Table 1summarises our results. A dash in a cell means that the corresponding proposal was not able to learn a rule for a given dataset, be it because it failed to find it, because it ran out of memory, or a bug that raised an exception. It is not surprising at all that the recent proposals outperform the classical ones regarding every effectiveness measure. Amongst the recent proposals, Trinity seems to be the one that achieves the best effectiveness. Note, however, that Yebra outperforms them all since it is able to induce rules that are more precise and have better recall in general; furthermore, the standard deviation of precision and recall is smaller, which means that our learning approach is more generally stable than the others, that is, it does not generally produce rules whose effectiveness largely deviates from the average. These results prove that Yebra is quite an effective approach to web information extraction. 4 Related Work The majority of supervised techniques in the literature build on ad-hoc machine learning algorithms that were specifically tailored to the problem of learning extraction rules [3,16]. Most of them try to learn token or XPath patterns that are based on token lexemes, their lexical classes, or HTML tags and their attributes: [12] presented a pioneering technique to learn two patterns of tokens that characterise the left and the right context of the information to extract. Hsu and Dung [7] devised an approach that first models the structure of the information in a set of web documents using finite automata and then learns transition conditions. Soderland [19] presented a proposal that starts with an overly-general Table 1. Experimental results rule and then specialises it with patterns that match token sequences. Muslea et al. [13] presented a proposal that builds on a hierarchical schema that models the information in a web document; for every positive example, it attempts to learn an automata that can recognise the sequence of tokens from the starting of the parent example until its initial token, and an automata that recognises the sequence of tokens from the final token until the final token of the parent example. Sleiman and Corchuelo [17] presented the most recent proposal in this field; they use finite automata to represent the structure of the information to be extracted and then use neural networks to learn transition conditions. None of the previous techniques have explored the idea of tackling information extraction using features of the tokens or the DOM trees themselves, e.g., their length, their colour, their depth, the ratio of letters, and the like; neither have they explored using features of the nodes in the neighbourhood. The only proposals that have explored this idea rely on first-order learning procedures, namely: SRV [5], which works on the textual view of the documents; it starts with the most general rule and then specialises it by adding conditions so that the rule matches as many positive examples as possible and reduces the number of negative ones matched. Irmak and Suel [8]presentedaproposalthatworks on the DOM-tree view of the documents and their rules are sets of conditions that work on XPaths; their proposal creates several sets of extraction rules that generalise the user-annotated examples in different ways; next, the user has to select the set of records that best suits his or her interests, and the learning process is executed again to correct mistakes. B˘adic˘a et al. [2]presentedaproposal that also works on the DOM-tree view of the input documents; their rules basically attempt to classify positive examples by means of their tags and the tags of their neighbouring nodes; their algorithm relies on the FOIL system [14] to learn a set of Horn clauses from a logic representation of the DOM-tree nodes and their features. Our contribution to the state of the art is twofold: on the one hand, we use a propositional approach that relies on a extensive catalogue of features; on the other hand, our propositional approach has the ability to exploit relational features that explore an unbounded context in the neighbourhood of the DOM tree nodes to extract. None of these approaches has been explored so far in the literature regarding web information extraction, but our results prove that they are very promising. 5 Conclusions In this paper, we have presented a new approach to information extraction; contrarily to the majority of proposals in the literature, which provide ad-hoc algorithms, our proposal maps the problem of information extraction onto the problem of learning from a set of vectors that represent the features computed on a DOM tree plus a number of relations amongst them. Our empirical results prove that our approach is very promising since it achieves better effectiveness than other state-of-the-art proposals. Acknowledgements. Our work was funded by the Spanish and the Andalusian R&D &I programmes by means of grants TIN2007-64119, P07-TIC-2602, P08-TIC-4100, TIN2008-04718-E, TIN2010-21744, TIN2010-09809-E, TIN2010-10811-E, TIN2010-099 88-E, TIN2011-15497-E, and TIN2013-40848-R, which got funds from the European FEDER programme. References 1. Blockeel, H., Raedt, L.D., Jacobs, N., Demoen, B.: Scaling up inductive logic programming by learning from interpretations. Data Min. Knowl. Discov. 3(1), 59–93 (1999) 2. B˘adic˘a, C., B˘adic˘a, A., Popescu, E., Abraham, A.: L-Wrappers: concepts, properties and construction. Soft Comput. 11(8), 753–772 (2007) 3. Chang, C.H., Kayed, M., Girgis, M.R., Shaalan, K.F.: A survey of web information extraction systems. IEEE Trans. Knowl. Data Eng. 18(10), 1411–1428 (2006) 4. Crescenzi, V., Merialdo, P.: Wrapper inference for ambiguous web pages. Appl. Artif. Intell. 22(1&2), 21–52 (2008) 5. Freitag, D.: Machine learning for information extraction in informal domains. Mach. Learn. 39(2/3), 169–202 (2000) 6. Gregg, D.G., Walczak, S.: Exploiting the information web. IEEE Trans. Syst. Man Cybern. Part C 37(1), 109–125 (2007)