TCS -TR-A-05-02

TCS Technical Report

Reputation Extraction Using Both Structural andContent Information

by

H. Hasegawa, M. Kudo and A. Nakamura

Division of Computer Science
Report Series A
February 17, 2005

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

atsu@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-6806+81-011-706-7832

Reputation Extraction Using Both Structural and Content
Information
Hiroyuki Hasegawa

Mineichi Kudo

Atsuyoshi Nakamura

Graduate School ofInformation Science andTechnology
Hokkaido University
Sapporo, 060-0814 Japan

Graduate School ofInformation Science andTechnology
Hokkaido University
Sapporo, 060-0814 Japan

Graduate School ofInformation Science andTechnology
Hokkaido University
Sapporo, 060-0814 Japan

hase@main.ist.hokudai.ac.jp mine@main.ist.hokudai.ac.jp atsu@main.ist.hokudai.ac.jp
The problem we address in this paper is extraction of

Abstracttexts that have a certain relation with a given keyword from
We propose a new method of extracting texts related
to a given keyword from Web pages collected by asearch engine. By combining structural pattern matching and text classification, texts related to a given keyword such as reputations of a given restaurant can beextracted automatically from Web pages in unfixedsites, which is impossible by conventional wrappers.
According to our cross validation results on extracting
reputations of a given Ramen shop from Web pages
collected by a search engine, our method achieved
79.3% precision and 56.6% recall by allowing acceptable errors.

all Web pages that contain the keyword. Given a restaurant name, extracting texts that are its reputations from all
Web pages retrieved by a search engine is one example ofthe problem. This problem would be easy if the Web pages
from which reputations are extracted were those in a number of fixed sites that use fixed formats. In such case, simple
wrappers such as LR wrapper [8] and TreeWrapper [9] canextract such pairs of a keyword and its related text by pattern

1.

matching around them. But by fixing sites from which repu-

INTRODUCTION

tations are extracted, sometimes enough information cannot
What do you use to get information when you want to findbe obtained though there is a lot of information in othera nice restaurant that serves a certain kind of dishes? Today,sites. Besides, new information that is obtainable from new

many people will answer that they use WWW (World Widesites can never be extracted by doing so. However, extrac-

Web). Actually, you may find a restaurant easily throughtion from unfixed sites is difficult, for example, LR wrapper

WWW, but it is difficult to judge whether the found restau-

and TreeWrapper cannot be constructed because there arerant really suits your taste. Maybe, most people try to judge

no common patterns around the parts to be extracted.

based on its reputations, which are also found in WWW.

Extraction from unfixed sites can be done to some ex-

Though there are restaurant-evaluation sites in which you

tent by constructing a wrapper that uses a set of consistent

can find a lot of reputations on restaurants, you cannot ob-

patterns (rules), namely, each of which correctly extract in-

tain enough reputations from one such site for minor restau-

formation from some pages but does not wrongly extract in-

rants. Then, you have to collect their reputations from sev-

formation from any pages [4]. But there may be no such seteral sites until enough information is obtained. But this isof patterns. For example, consider a case that a restaurant

not an easy task because not all pages that contain a restau-name and its reputation are written in the first and the third

rant name contain its reputation, and even such pages thatcolumns in one table while a restaurant name and how tocontain a reputation of a target restaurant may be very large

access to it are written in those columns in another table. If

pages with a lot of irrelevant information including informa-

all the patterns around the columns are the same in the twotion of other restaurants.

tables, it is impossible to create a consistent pattern unlessconditions on the contents of the third column are also in-.

1corporated into the created pattern. Content-based pattern

reputations of a given Ramen shop from Web pages collected

matching is easy if contents always appear in the same for-by a search engine, our method achieved 79.3% precision andmat like email addresses and telephone numbers, but it is not

56.6% recall by allowing acceptable errors.

so trivial when contents are given by free texts.

1.1 Other Related WorkTo overcome this difficulty, we propose a method thatcombines pattern matching and text classification. In our

As a wrapper using SVM, there is a method proposed bymethod, given a keyword, candidates of related texts are ex-

Kashima and Koyanagi [7]. Their use of SVM is not text

tracted by pattern matching using a set of patterns that re-classification but tree classification, and they use a special

lates a keyword to a target text, then predicted target texts

kernel for tree structure. Their method make use of tree

are selected from the candidates by text classification. We

structure only, so it seems to be difficult to extract target

also propose a learning method of a set of patterns and a text

information from unfixed sites.

classifier from a training data.

The method proposed by Ikeda, Yamada and Hirokawa

In our method, each pattern is represented by a simple[5] is one method that uses not only tree structure but also

DOM-tree that consists of a root node and two paths leading

text information in a target text node. But they used text

to the leaves, one is a node for a keyword and the other isinformation in order to extract a part of a text in a text nodea node for a target text. This pattern DOM-tree is similar

by detecting template strings like LR wrapper does.

to that used by TreeWrapper [9] and Ltagpath [4], but our

Tateishi, Ishiguro and Fukushima [10] developed a rep-pattern matching allows elastic matching as considered byutation search engine by using natural language processing

Zaki [12] in the context of frequent-tree mining, that is, twotechnique. Their engine extracts reputation sentences fromnodes of parent-child relation in a pattern tree can also matchdocuments and does not use any special features of HTMLsuch two nodes as the relation between them is not parent-

documents.

child but ancestor-descendant. By allowing this matching,

2. PROBLEM STATEMENT

we can construct more general patterns from training data.
Using general patterns is important because only a few target

A rooted tree T = (V, B) is a connected acyclic graph withtexts are extracted by using patterns that are too specifica set V of vertices and a set B of directed edges (NT ,i , NT ,j ) ∈and non-target texts extracted by pattern matching can be

V × V that represent parent-child relation, which satisfies thefiltered out by text classification.

condition that every vertex but just one vertex (root) has

We propose a method of learning a set of above patterns,

just one parent vertex. For a tree, a vertex and an edge

by which common pattern DOM-trees are obtained for eachare called a node and a branch, respectively. An ordered

subset of positive training DOM-trees that have the same

tree T = (V, B, ) is a rooted tree (V, B) with partial ordertag for the node containing target texts and also have the‘’ on V representing a sibling relation, where the order issame tag for the least common ancestor of a node contain-

defined just for all the pair of siblings, children having theing a given keyword and the node containing target texts.

same parent. A (simplified) DOM-tree, a representation ofCommon pattern DOM-trees can be obtained by using thean HTML document in document object model, is an orderedsequencial mining algorithm AprioriALL [1] several times.

tree T in which each node NT has two attribute tag and text.

In the text classification phase, any classifier [2] can be

We assume tha a value of a tag attribute is an element in a

used. Negative training data for learning a classifier are au-label set L and a value of a text attribute is a string thattomatically generated from training data by using a set ofis a sequence of characters in a character set Σ. We also

patterns created in the previous phase. we adopted support

assume that a text attribute of NT is not null only when avector machine (SVM) [11] as a classifier in our experiments

tag attribute of NT is “#text”1 .

because its good performance was reported [6].

1
In HTML, the tag “#text” does not exist, but here we assume that all text nodes in a DOM-tree have this tag attribute value.

According to our cross validation results on extracting

2

html
head

body

title

big

br

font
#text

strong#text

Best Sushi restaurant in the world

My favorite restaurant#text
Little Sapporo<html><head><title> My favorite restaurant </title></head><body bgcolor="yellow"><big><strong> Little Sapporo </strong></big><br><font color="blue">Best Sushi restaurant in the world</font></body></html>Figure 1: Example of a DOM-tree and the HTML document it represents
T .root
T .id
S.treeid
NT .tag
NT .text
NT .parent
NT .firstchildNT .nextsibling
NT .prevsibling
NT .idcontain(s0 , s1 )An example of a DOM-tree and the HTML document it
represents are shown in Figure 1. Note that nodes in our
DOM-tree do not have other attributes like the attribute“bgcolor” for the node with the tag “body”2 .
An id of a node NT is its position in the depth-first traversal of the tree T . In this paper, we let the depth-first traversal mean the unique one in which siblings are passed in thepartial order ‘’.

duplicate(NT )s.firstx.valuex.nextappend(s, u)

The parent-child relation, which is defined by a set B
of branches, induces another partial order ‘≤’, an ancestordescendant relation, by extending the relation so as to satisfy

root of T
id of Ttree id of S
tag of NT
text of NT
parent of NT
first child of NT
next sibling of NTprevious sibling of NT
id of NTboolean function that is true if and only
if s1 appears in s0
copied node of NT
first element of svalue of x
next element of x
append a list element with value u to sreflexivity and transitivity. If NT ,i and NT ,j are not compaTable 1: Notations used in this paper for a tree T , a
part-tree S, a node NT of T , strings s1 and s2 , a lists and its element x.

rable in order ‘≤’, NT ,j is said to be a left-collateral of NT ,iwhen the id of NT ,i is larger than the id of NT ,j and a rightcollateral of NT ,i when the id of NT ,i is smaller than the idof a training data (W, T, NT∗ ) to the least common ancestor ofof NT ,jall the text nodes that have a target relation with a keyword

A part-tree S of a tree T is a connected subgraph of T . A

W.

node id of a part-tree S of a tree T is not its position in thedepth-first traversal of the tree S, but the same as the id of

3. METHOD

its correspondence in T . Each tree T is assumed to have an
unique id. In addition to such an unique id, each part-tree S

3.1 Prediction Functionof a tree T has a tree id that is the id of T .
We use notations shown in Table 1 throughout the paper.

A function f to be learned makes a prediction by using

In this paper, we address the following problem.

three functions fpat , fcon and fdec . The function fpat isa function of a keyword W and a DOM-tree T that outputs

Problem 2.1. Let a training data set D be a set of triples

a candidate node set {NT ,1 , NT ,2 , ..., NT ,k } that may have a(W, T, NT∗ ), where W is a keyword, T is a DOM-tree that has

target relation between W . We call fpat a pattern-matchingtext nodes containing W , and NT∗ is a node in T that has afunction because the function winnows the candidates by pat-target relation with W or NT∗ is null when there are no suchtern matching. The function fcon is a function of a node NT

nodes in T . For a given D, learn a function f of a keyword

that outputs a label 1 or −1 based on the attributes of the

W and a DOM-tree T that outputs a node in T that has anode. Here as attributes, we use the ones extracted from thetarget relation with a keyword W .

texts that are contained in the subtree rooted by the node.
So, we call fcon a content-based function. The function fdec

Relation between a restaurant and its reputation is an
example of a target relation. In this paper, we set a node NT∗

is a function of a set {(NT ,1 , l1 ), (NT ,2 , l2 ), ..., (NT ,k , lk )}, where2each pair is composed of a node NT ,j and a label lj , and out-

TreeMiner [9] uses those attributes.
3

0 T
html

puts one node NT ,j for j ∈ {1, 2, ..., k} or null. We call fdec
1
head

a decision function. In this paper, we fix a function fdec to2
title

the function that outputs the node of the smallest id among
3

those having the positive label.

#text

φ

5
big

8

body

br

9
font

6
strong

My favorite restaurant 7#text

Then, a function f is defined as follows.

P

4
body
φ
∗

NT

strong10#text

Best Sushi restaurant in the world

Little Sapporo

φ

#text
CP

#text
KP
φ

f (W, T ) = fdec ({(NT , fcon (NT )) : NT ∈ fpat (W, T )})3.2 Pattern-Matching Function

Figure 2: Example of a pattern tree P . The structural relation of the node NT∗ to keyword “Little Sapporo” matches the pattern (P, 3).

A function fpat selects all the nodes in a DOM-tree Tof which structural relation to a keyword W matches one ofpatterns in a set P. A pattern is a pair of a pattern tree P

W are searched first in the procedure find-candidate. For

and its leaf distance r. A pattern tree P is a simple DOM-

each found node and for each pattern (P, r) ∈ P, its an-tree that consists of a root node and two paths leading to thecestors to which some mapping φ satisfying the above 6

leaf nodes, a keyword node KP whose tag is “#text” and aconditions may map from the root node of P are searchedtarget node CP . Here3 , we restrict pattern trees to the onesin the procedure matching.

in which KP appears before CP , that is, KP .id < CP .id. The

tor, its descendants whose structural relation to W matches

structural relation of a node NT to a keyword W matches a

the pattern (P, r) are searched in the procedure find-node.

pattern (P, r) if and only if there is a one-to-one mapping

The worst-case computational time of this implementation isφ from the set of nodes in P to the set of nodes in T that

O((kW,T nP + 1)nT + nW + nt ), where kW,T is the number ofsatisfies the following six conditions for all nodes NP,1 andnodes in T that contains the keyword W , nP is the number

NP,2 in P .

of patterns in P, nT is the number of nodes in T , nW is the

Finally, for each such ances-length of W and nt is the total length of all texts contained
1. target matching: NT = φ(CP )in T .

2. Label preserving: NP,1 .tag = φ(NP,1 ).tag

3.2.2 Learning

3. Keyword matching: contain(φ(KP ).text, W )A pattern matching function fpat needs a pattern set P,
4. Ancestor-descendant relation preserving: If node

which is learned from a training data D. A proposed learning

NP,1 is a child of node NP,2 , node φ(NP,1 ) is a descen-function Learn-fpat is shown in Figure 4. The training data

dant of node φ(NP,2 ).

D is composed of triples (W, T, NT∗ ), where W is a keyword,
T is a DOM-tree and NT∗ is a node in T that has a target

5. Sibling relation preserving: φ(KP ).id < φ(CP ).id.

relation with W or NT∗ is null when there are no such nodes

6. Acceptable distance: |φ(KP ).id − φ(CP ).id| ≤ r

in T . The function Learn-fpat uses positive data only, thatis, triples (W, T, NT∗ ) with NT∗ ! =null.

An example of a pattern tree P and a matching function φ
are shown in Figure 2. Note that the matching satisfying the

For each positive data (W, T, NT∗ ), Learn-fpat calls theabove 6 conditions is elastic, and the nodes with tag “big”

function extract-parttree shown in Figure 5, which extracts

and tag “font” can be jumped over in the matching.

one part-tree for each text node NT ,W that is a left-collateralof NT∗ and of which text contains W . Each extracted part-3.2.1 Implementation

tree consists of two nodes NT∗ and NT ,W , the least common
In

ancestor NT ,0 of them, all the nodes between NT ,0 and NT∗

the implementation, text nodes that contain the keyword

and all the nodes between NT ,0 and NT ,W . Search for NT ,W3

is done by checking, for each ancestor node of NT∗ , all the de-An implementation of fpat is shown in Figure 3.

Extension for allowing the reverse order is easy, but a related
text appears after a keyword in most cases, we restricted thepattern trees.

scendant leaf text node that is a left-collateral of NT∗ , which
4

Function Learn-fpat (D)D : training data
begin
Dpat = ∅for each (W, T, NT∗ ) ∈ D do
if NT∗ ! =null thenextract-parttree(Dpat , W, NT∗ )
endif
enddo
P=∅
for each El,t ∈ Dpat do
P = P∪maximal-common-pattern(El,t , n)enddo
return P
end

Function fpat (W, T )W : keyword, T : DOM-tree
begin
return find-candidate(W, T .root)
end
Function find-candidate(W, NT )W : keyword, NT : node of T
begin
C=∅
if NT .tag==”#text” andcontain(NT .text, W )==true thenfor each (P, r) ∈ P domatching(KP , NT , NT .id+r, C)
enddo
endif
M = NT .firstchildwhile M ! =null do
C = C∪find-candidate(W, M )M = M .nextsibling
enddo
return C
end
Procedure matching(NP , NT , b, C)
NP : node of P , NT : node of Tb : maximum allowable node id
C : candidate set (updated when returned)
begin
while NT .parent! =null do
if NP .parent == null andNT .parent.tag == NP .tag thenMP = NP .firstchild.nextsibling
MT = NT .nextsibling
while MT ! =null dofind-node(MT , MP , b, C)
MT = MT .nextsibling
enddo
else if NP .parent.tag==NT .parent.tag thenNP = NP .parent
if NP .parent ==null then continue
endif
NT = NT .parent
enddo
end
Procedure find-node(NT , NP , b, C)
NT : node of T , NP : node of Pb : maximum allowable node id
C : candidate set (updated when returned)
begin
if NT .id > b then return
if NP .tag == NT .tag thenif NP .firstchild == null then C = C ∪ {NT }else NP = NP .firstchildendif
M = NT .firstchildwhile M ! =null dofind-node(M, NP , b, C)
M = M .nextsibling
enddo
end

Figure 4: Function of learning a pattern set P

is done by the function keynode. In the keynode function, theset of the extracted part-trees S are classified by two tags, a
tag l of the root node of S and a tag t of the leaf node corresponding to NT∗ . After the executions of the function extractparttree for all positive data, Dpat , a set of classes El,t ofpart-trees, is constructed. Note that function get partition,
create and add used in the procedure keynode are defined
as follows. The function get partition(Dpat , l, t) returns theclass El,t of part-trees for the pair (l, t) of tags if exists andnull otherwise. This function is efficiently implemented byusing a hash table. The function create(Dpat , l, t) creates anempty class El,t for the pair (l, t) of tags and returns it. The
function add(El,t , S) adds a part-tree S to the class El,t .
For each class El,t , generalized patterns are obtained by
the function maximal-common-pattern shown in Figure 6,
which is called by the function Learn-fpat . The function
maximal-common-pattern outputs the maximal common patterns (P, r) of part-trees in a given set El,t , namely, maximal
patterns (P, r) that are matched by the structural relation of
the node NT∗ to a keyword W for all (W, T, NT∗ ) ∈ D satisfying that for T there is an S ∈ El,t with S.treeid = T .id. The
acceptable distance r is calculated by the function max-leafdistance (Figure 6), which outputs the maximum difference
between two leaf node ids of S in El,t .
The maximal common patterns for a given set El,t of parttrees can be obtained by using the algorithm AprioriAll sev-

Figure 3: Implementation of the function fpat

eral times with minimum support 1.0, where AprioriALL isan algorithm for mining sequential patterns developed by
Agrawal and Srikant [1]. The first execution of AprioriAll
5

Procedure extract-parttree(Dpat , W, NT )Dpat : transformed data (updated when returned)
W : keyword, NT : node in T
begin
S.root=null
t = NT .tag
insert child(S, duplicate(NT ))while NT .parent! =null do
insert child(S, duplicate(NT .parent))l = NT .parent.tag
MT = NT .prevsibling
while MT ! =null do
keynode(Dpat , W, MT , S.root,l,t)
MT = MT .prevsiblingenddo
NT = NT .parent
enddo
end
Procedure keynode(Dpat , W, NT , NS ,l,t)Dpat : transformed data (updated when returned)
W : keyword, NS : node in S, NT : node in Tl : tag of the least common ancestor nodet : tag of the target node
begin
add child(NS , duplicate(NT ))if NT .tag==”#text” andcontain(NT .text, W )==true thenEl,t =get partition(Dpat , l, t)
if El,t ==null then El,t =create(Dpat , l, t)
add(El,t , S)else
NT = NT .firstchildwhile NT ! =null do
keynode(Dpat , W, NT , NS .firstchild,l,t)
NT = NT .nextsibling
enddo
endif
remove child(NS )end
Procedre insert child(S, NS )S : DOM-tree, NS : copied node in T
begin
NS .firstchild=S.root
NS .nextsibling= NS .prevsibling=null
S.root= NS
end
Procedre add child(NS , MS )NS : node in S, MS : copied node in T
begin
MS .nextsibling=NS .firstchild
MS .firstchild= MS .prevsibling=null
NS .firstchild= MS
end
Procedre remove child(NS )NS : node in S
begin
NS .firstchild= NS .firstchild.nextsiblingif NS .firstchild! =null then NS .firstchild.prevsibling=null
end

Function maximal-common-pattern(El,t )El,t : set of part-trees
begin
L = {(S.treeid,tag-seq(S.root.firstchild))S .id : S ∈ El,t }n = |{i : (i, s) ∈ L}|
SEl,t =AprioriAll(L, 1.0 × n)
P=∅for each (s1 , I1 ) ∈ SEl,t do
L = {(S.treeid,tag-seq(S.root.firstchild.nextsibling))S .id :S ∈ El,t , S.id ∈ I1 }
Ss1 =AprioriAll(L, 1.0 × n)
for each (s2 , I2 ) ∈ Ss1 do
P = make-pattern-tree(l, t, s1 , s2 )r = max-leaf-distance(El,t , I2 )P = P ∪ {(P, r)}
enddo
enddo
return P
end
Function AprioriAll(L, σ)
L : set of pairs (tree id,tag sequence)σ : (minimum suport)×(number of training data)
begin
L1 = {(c, I) : I = {i : (j, X)i ∈ L, contain(X, c) == true},c is a length-1 tag sequence with|{j : (j, X)i ∈ L, i ∈ I}| ≥ σ}
k=2while Lk−1 6= ∅ do
Ck = {(c1 , I1 ) ⊗ (c2 , I2 ) : (c1 , I1 ), (c2 , I2 ) ∈ Lk−1 ,prefix(c1 , k − 2) == prefix(c2 , k − 2)}
Lk = {(c, I) : (c, I) ∈ Ck , |{j : (j, X)i ∈ L, i ∈ I}| ≥ σ}k = k+1
enddo
S
return {(c, I) : (c, I) ∈ k−1
h=1 Lh , c is maximal}
end
Function tag-seq(NS )NS : node in S
begin
s =null
while NS .firstchild! =null doappend(s, NS .tag)
NS = NS .firstchild
enddo
return s
end
Figure 6: Function of calculating the maximal common patterns (1)is done for finding the maximal common tag subsequencesof all the paths from the root node to the first leaf node of
the part-trees in El,t . Note that support is calculated basedon the number of distinct tree ids of part-trees, namely, thenumber of trees from which part-trees are extracted. Thus,
even for support 1.0, some of the tag sequences given to thefunction AprioriAll may not contain the obtained tag sub-Figure 5: Function of extracting a part-tree

sequences. In our implementation of AprioriAll (Figure 6),
in addition to the maximal common tag subsequences s1 ,6

Function make-pattern-tree(l, t, s1 , s2 )l, t : tag, s1 , s2 : tag sequence
begin
N .tag = l
N .firstchild = N .nextsibling = N .prevsibling =null
P .root = duplicate(N )make-path(P .root, s2 , t)
make-path(P .root, s1 ,”#text”)
return P
end
Procedure make-path(NP , s, u)
NP : node of P , s : tag sequence, u : tag
begin
x = s.first
while x! =null do
N .tag = x.value
add child(NP , duplicate(N ))NP = NP .firstchildx = x.next
enddo
N .tag = u
add child(NP , duplicate(N ))end

nW is the length of W and nt is the total length of all texts
in T . Note that searching nodes with text that contains W
takes O(nT ), copying found part-trees takes O(kW,T ,NT∗ nT ),and string pattern matching takes O(nW + nt ). Therefore,
the worst-case computational time of the first loop in thefunction Learn-fpat is O((kD + 1)nD + nW + nd ), where nD
is the sum of the number of nodes in T belonging to D,
kD = max(W,T ,NT∗ )∈D kW,T ,NT∗ , and nW and nd are the sum ofnW and nt , respectively, for all training data (W, T, NT∗ ) ∈ D.
In all the executions of AprioriAll, totally at most 2lP +1 nP |L|
candidates are generated, where lP is the maximum numberof nodes between a root node and a leaf node of pattern
trees in P, nP is the number of the maximal common patterns, and |L| is the number of tags. For each candidate pattern, computational time O(kD nD ) is enough for its support
calculation, so the worst-case computational time of function

Figure 7: Function of calculating the maximal common patterns (2)maximal-common-pattern is O(2lP +1 nP |L|kD nD ). Thus, theworst-case computational time of the function Learn-fP is
O(2lP +1 nP |L|(kD + 1)nD + nW + nd ).

the set I1 of ids of part-trees that contains s1 is returnedfor each s1 . In the function AprioriAll, a length-k candi-

3.3 Content-based Function

date c for frequent sequences is generated from two length(k−1) frequent sequences c1 , c2 with the same prefix of length

The function fcon classifies a given node NT into +1 ork − 2 (prefix(c1 , k − 2) = prefix(c2 , k − 2)) by appending−1 by its attribute values. Since a target information is com-the last tag of c2 to c1 . By a join operation of (c1 , I1 ) andposed of texts in our problem setting, any text classification(c2 , I2 ) denoted by (c1 , I1 ) ⊗ (c2 , I2 ), (c, I) is created, where

technique can be used to design the function fcon . As an at-

I = {i : i ∈ I1 ∩ I2 , contain(X, c) = true for (j, X)i ∈ L}.

tribute vector, we use an index term vector [2] that is created

For each (s1 , I1 ) obtained by the first execution of Aprior-from all the texts of the descendant nodes of the given nodeiAll, AprioriAll is executed for finding the maximal common

NT . An index term vector is a collection of weights associ-tag subsequences of all the paths from the root node to theated with each representative keyword called index term. Its

second leaf node of the part-trees in {S : S ∈ El,t , S.id ∈ I1 }.

weights can be binary, normalized term frequencies or tf-idfs.

Note that all part-trees in El,t have the tag l of the root

A classifier used in the function fcon can be any one that

node, the tag “#text” of the first leaf node and the tag t of

inputs a real valued vector.

the second leaf node. The tag sequences given to AprioriAll do not contain the tags of those nodes. In the function

3.3.1 Training data generation for a classifier

make-pattern-tree (Figure 7), which is called by the function
maximal-common-pattern, a pattern tree P is constructed fi-

A training data for a classifier is generated from the orig-

nally from the tags of the root node and two leaf nodes, andinal training data D by the function Data-generation shown

the two common tag subsequences obtained by AprioriAll.

in Figure 8. For each (W, T, NT∗ ) ∈ D, the pattern matching

The worst-case computational time of the function extract-function fpat is executed. A positive training data instanceparttree is O((kW,T ,NT∗ + 1)nT + nW + nt ), where kW,T ,NT∗ isis generated for each NT∗ . A negative training data instancethe number of nodes in T that is a left-collateral of NT∗ andis generated for each NT in a set C output by the functionof which text contains W , nT is the number of nodes in T ,fpat except for NT .id ≥ NT∗ .id.
7

Function Data-generation(D)D : training data
begin
Dcon = ∅for each (W, T, NT∗ ) ∈ D do
C = fpat (W, T )for each NT ∈ C dol = −1
if NT∗ ! =null thenif NT .id > NT∗ .id then continue
if NT .id == NT∗ .id then l = 1
endif~v =index-term-vector(NT )Dcon = Dcon ∪ {(~v , l)}
enddo
enddo
return Dconend

the collected HTML pages and shop names used to retrieve
them. Each non-null target node NT∗ of a DOM-tree T was
set to the least common ancestor node6 of the text nodes
whose text contains the target reputation.
We conducted cross validation by using the pages retrievedfor each one of 10 shops as test data.
Index terms we used in our experiments are basically standard forms of nouns, verbs, adjectives and adverbs. We dealt
with Japanese text, and Chasen7 , one of Japanese morphological analysis systems, is used to extract index terms. As aterm weight, we used a term frequency normalized with respect to Euclidean norm. A support vector machine (SVM)
was used as a classifier in the experiments. We used SVM-

Figure 8: Function of generating training data for aclassifier
Shop No.
1
2
3
4
5
6
7
8
9
10
total

#HTML
34
19
73
24
26
23
21
33
20
28
301

#POS
26
9
46
14
12
17
11
21
13
20
189

#ONE
8
2
15
4
4
7
6
6
5
5
62

Torch II8 with polynomial kernel K(x, y) = (xy + 1)3 andother default parameters.

#MANY
18
7
31
10
8
10
5
15
8
15
127

We compared our method with other two simpler methods, a method using patterns only and a method using simple patterns. A method using patterns only is the one thatusesfcon ≡ 1 in our proposed prediction function. Simple
patterns used in the second method are pairs (t, r) of a tag t
for a target node and a distance r from a keyword node. For
these patterns, all the nodes that have tag t and id i which
satisfies k < i ≤ k+r are matched, where k is the id of a node

Table 2: Experimental data (#ONE: number ofpages containing reputations of the target shop only,#MANY: number of pages also containing reputations of other shops)

whose text contains a given keyword. A method using simple
patterns is the one that uses this pattern matching function
as the function fpat in our proposed prediction function. A
set P of simple patterns (t, r) learn from training data D for

4.

EXPERIMENTS

tests and training data generation for a classifier is{(t, r) : t ∈ L, r =4.1 Methodology

max

∗ )∈D
(W,T ,NTt(NT∗ .id − min id(W, T ))},

where

The HTML documents we used in our experiment are
Web pages containing the information about a given Ramen (lamian, Chinese noodles in Soup) Shop. Among themost popular 100 Ramen-shops introduced in a popular local
town information magazine4 , we selected the most popular
10 Ramen shops with more than 15 Web pages retrieved byL={NT∗ .tag : (W, T, NT∗ ) ∈ D},

Dt={(W, T, NT∗ ) ∈ D : NT∗ .tag = t} andmin id(W, T ) =min{NT .id : contain(NT .text, W )}.

4.2 Results

keyword search5 using a shop name and its telephone numThe results are shown in Table 3. Note that in the columns

ber. Totally 301 pages were retrieved and 189 pages of them

6
If the subtree rooted by the least common ancestor nodecontains reputations of other restaurants, the most informative one text node is selected as a representative instead ofthe least common ancestor node.
7
ChaSen 2.3.3. (URL:chasen.aist-nara.ac.jp/hiki/ChaSen)
8
URL:www.idiap.ch/ bengio/projects/SVMTorch.html

contained the reputation about a target shop. (See Table 2.)
We constructed the experimental data (W, T, NT∗ ) from4
5

Hokkaido Walker 2002 NO.3.
Google(www.google.co.jp) was used in the search.
8

for fpat , fcon and fdec , the number of correctly extracted

is correctly extracted, “4” indicates that the corresponding

nodes included in the outputs of the functions for NT∗ ! =null

extracted node is acceptable, and “×” indicates that the text

is written. A precision is a rate of the number of correctly

contains no reputation about a target shop. All the extracted

extracted nodes among all the extracted nodes, and a recall

texts looks reputations of some shops, so text classification by

is a rate of the number of correctly extracted nodes among

SVM works to some extent. For the first “×”-labeled text,

all the nodes that should be extracted.

the target node was included in the output of a pattern-

The method using patterns only suffers low precision andmatching function, but was labeled −1 by a content-based

recall even for training data. Compared to this method, thefunction. For the second “×”-labeled text, the target nodeother two methods, which also use contents information, ob-

was not output by a pattern-matching function.

tain rather higher precision and recall for both data. The
4 A super-popular shop selected as the best Ramen shop!!
In the shop, there was a card saying that the taste of our Ramenis the result of pursuing delicious Ramen. The taste is mild and fairly
heavy but its aftertaste is clear. Fat back floating on the soup is madeby stewing it several hours in a separate cooking pot. The soup has
become whitish by stewing pig bones and pig legs more than 12 hours.
The noodle, which is thickish and curly, is made by noodle company
K. Besides this soy sauce Ramen, ZYANSYANMEN is also popular.
× Shop S. Sapporo. Tram station named NISHI 9 ZYO. You can enjoy
pork-based salt, soy sauce and miso Ramens. The soup is made fromHIDAKA konbu and dried SANRIKU saury. The Ramen contains
three thick slices of roast pork, in most cases, two slices of pork belly
and one slice of pork loin. I felt nice to see that the noodle waswell drained by a flat bamboo sieve. Each taste of the three kinds ofRamens (700 yen each) is good. Besides, a chicken-based limited salt
Ramen, which price is 800 yen, tastes better. Chicken fat is floatingon all the surface of the soup. The soup also contains saury taste andthe harmony of the taste is good. It is also nice that they use rocksalt. My recommendation is this limited salt Ramen. However, thesoup of the other Ramens is a little tepid, especially, miso Ramen isquite tepid, so it is not recommended. The fact that miso Ramen is
tepid is the character of noodle company K? 2003.04.26. eating of thelimited salt Ramen 2003.04.27. I have eaten miso Ramen. limited
salt ? Sapporo city · · · (telephone number) Closed on Monday. Open
11:30-20:30. Parking space for 3 cars. 15 seats.
I had been hesitating to introduce my favorite Ramen shops because
everyone has a different taste. (It was OK for me to introduce curry
Ramens last time because it is a special kind of Ramens.) Some people
might disagree with me, but the shop I am introducing here is the best
among the Ramens I have tasted for the last 5 or 6 years. The noodleof this Ramen is thick and curly, and the soup is made by stewing
pig bones. You can enjoy three tastes, miso, salt and soy sauce. The
noodle is a little hard, so you can get normal noodle if you say thatyou like softish noodle. The soup is a little thick because of using thicknoodle, but I felt that it was not so strong. The shop was introducedin Hokkaido Walker in Febuary, 2002, as the second popular Ramen
shop. The most popular one introduced in the magazine was Shop G.
(Evaluations appeared in this page are the ones I have done personallyafter eating the Ramens actually.) Q: Is Sapporo near Muroran? You
said that you introduce about shops around Muroran. A: Yes! (I amsure.)
Papa A: I have heard that the shop is crowded, and it was true.
People might have been waiting for the opening of this famous shop at
this convenient place. Hardness of noodle of Ramens we ordered, salt,
miso and soy sauce was different, which cause might be crowdedness.
They did not frequently change the water used for boiling the noodle.
Are those acceptable? The miso and soy sauce Ramen still tasted
good. Did the salt Ramen taste like this before? The noodle is madeby Company K. ——— ? ? ??
× Pork that was like roast pork and stewed until it became soft isextremely delicious.
Since there was a long waiting line at Sunday noon, I went there alittle after 11 o’clock on a weekday. People came in the shop after byafter, and the shop became crowded soon. The soup of the Ramens
is based on pig bones. The miso soup is rich and a little spicy. The
noodle is fairly hard and curly. I want to eat a popular soy sauce
Ramen next time. The shop is clean. There is parking space.
4 Fat back poured finally makes the soup rich taste!

proposed method outperformed the method using simple patterns by 5 ∼ 7 percentages. The numbers in the parentheses
are precisions and recalls that were calculated by including
extracted acceptable nodes in the set of correctly extracted
nodes. Here, acceptable nodes are defined as the ones which
include a part of reputations about a target shop and exclude any information about other shops. In the proposed
method, 79.3% of extracted nodes were acceptable and acceptable nodes are extracted for 56.6% of the nodes thatshould be extracted.

4.3 Discussion
Figure 9 shows all patterns output by Learn-fpat for thewhole experimental data. #NUM is the number of data thatmatches each pattern. Each pattern tree is represented by its
string encoding, a tag sequence of nodes in their passing order in a depth-first traversal, where the additional tag “−1”is added when backtracking from a child. Nodes corresponding to the tags with suffixes “(1)” and “(2)” are a keyword
node and a target node, respectively. A several patterns oftable structure in the found pattern set, such as “table tr td#text(1) -1 -1 -1 tr td(2) -1 -1”, look useful to winnow candidates. Some patterns such as “body #text(1) -1 #text(2)-1” are too general to winnow candidates, and pruning or
further specification of such patterns may increase precision.
Though this seems to decrease recall, but note that this canalso increase recall if quality of negative training data forlearning a classifier improves by using different set of patterns.
The reputations extracted for Shop 2 by using patterns
and an SVM learned from data of other shops are shownin Table 4. In the table, “

Table 4: Reputations extracted for Shop 2 (translated from Japanese)” indicates that a reputation
9

used information
patterns only
simple patterns + contents
patterns + contents (proposed)

training data
ave. pre. ave. rec.
0.113
0.169
0.907
0.897
0.943
0.938

fpat
166
183
166

fcon
166
86
95

fdec
30
74
85

test data
precision
0.106
0.561 (0.727)
0.630 (0.793)

recall0.159
0.391 (0.508)
0.450 (0.566)

Table 3: Precisions and recalls for three methods
#NUM
30
20
19
19
16
10
8
7
5
1
1
1
1
1
18
13
11
4
4
2
7
2
2
2
3
3
2
2
1
4
4
2
2
2
1

r
245
452
80
256
177
8
496
38
270
12
28
22
5
2
51
56
173
265
64
47
166
151
33
9
107
7
135
120
66
1
12
17
2
23
17

pattern tree
body #text(1) -1 #text(2) -1
table tr #text(1) -1 -1 tr td #text(2) -1 -1 -1
tr td #text(1) -1 -1 td #text(2) -1 -1
td #text(1) -1 #text(2) -1
html head title #text(1) -1 -1 -1 body #text(2) -1 -1
p #text(1) -1 #text(2) -1
tbody tr td #text(1) -1 -1 -1 tr td #text(2) -1 -1 -1
li #text(1) -1 #text(2) -1
div #text(1) -1 #text(2) -1
blockquote strong #text(1) -1 -1 #text(2) -1
ol li #text(1) -1 -1 li #text(2) -1 -1
h3 #text(1) -1 #text(2) -1
dl dt #text(1) -1 -1 dd #text(2) -1 -1
span strong #text(1) -1 -1 #text(2) -1
tr td #text(1) -1 -1 td(2) -1
table tr td #text(1) -1 -1 -1 tr td(2) -1 -1
tbody tr td #text(1) -1 -1 -1 tr td(2) -1 -1
html head title #text(1) -1 -1 -1 body table tr td(2) -1 -1 -1 -1
body #text(1) -1 table tr td(2) -1 -1 -1
td strong #text(1) -1 -1 table tr td(2) -1 -1 -1
body #text(1) -1 p(2) -1
html head title #text(1) -1 -1 -1 body p(2) -1 -1
tr td h2 #text(1) -1 -1 -1 td p(2) -1 -1
td #text(1) -1 p(2) -1
html head title #text(1) -1 -1 -1 body table(2) -1 -1
body table tr #text(1) -1 -1 -1 table(2) -1
html head title #text(1) -1 -1 -1 body table tbody tr(2) -1 -1 -1 -1
tbody tr td #text(1) -1 -1 -1 tr(2) -1
body table tbody tr td strong #text(1) -1 -1 -1 -1 -1 -1 table tbody tr(2) -1 -1 -1
html head title #text(1) -1 -1 -1 body(2) -1
tbody tr td #text(1) -1 -1 -1 tr td span(2) -1 -1 -1
html head title #text(1) -1 -1 -1 body blockquote(2) -1 -1
body p strong #text(1) -1 -1 -1 blockquote(2) -1
body strong #text(1) -1 -1 p strong(2) -1 -1
html head title #text(1) -1 -1 -1 body p strong(2) -1 -1 -1

simple pattern (t,r)(#text,496),#NUM=139(td,265),#NUM=52(p,166),#NUM=13(table,107),#NUM=6(tr,135),#NUM=5(body,1),#NUM=4(span,12),#NUM=4(blockquote,17),#NUM=4(strong,23),#NUM=3

Figure 9: Patterns output by fpat for the set of all the data
According to Table 3, 12% of the target nodes were notexperiments on reputation extraction, our method achieved

extracted by a pattern-matching function, and 43% of theabout 79.3% precision and 56.6% recall by allowing accept-

other target nodes were not labeled 1 by a content-basedable errors. The precision looks rather low compared to thatfunction. Considering high precision and recall for trainingof conventional wrappers, but our method can extract moredata, the reason why so much target nodes were not labeledinformation because sites from which texts are extracted are

1 by the content-based function may be that the number

not fixed, and even a set of extracted texts that contains aof training data for the function was too small to learn thesmall percentage of wrong ones can be used to assist people’sfunction. This problem may be solved to some extent bydecision if original Web pages can be accessed by clicking the

reducing the number of index terms through more careful

extracted texts. In order to improve precision while keeping

selection of them.

recall, it seems also necessary to detect repetition structures5.

considered in [3].

CONCLUSIONS

Acknowledgments

We proposed a combined method of structural patternmatching and text classification that can extract texts related

We would like to thank Prof. Hiroki Arimura for helpful

to a given keyword from Web pages in unfixed sites. In ourcomments.
10

6.

REFERENCES[12] M. J. Zaki. Efficiently mining frequent trees in a forest.
In Proc. SIGKDD’02, pages 71–80, 2002.

[1] R. Agrawal and R. Srikant. Mining sequential patterns.
In Proc. 11th Int’l Conf. on Data Eng., pages 3–14,
1995.
[2] R. Baeza-Yates and B. Ribriro-Neto. Modern
Information Retrieval. ACM Press, New York, NY,
1999.
[3] C.-H. Chang and S.-C.Lui. Iepad: Information
extraction based on pattern discovery. In Proc. of 10thInt’l World Wide Web Conf., pages 4–15, 2001.
[4] W. W. Cohen, M. Hurst, and L. S. Jensen. A flexible
learning system for wrapping tables and lists in html
documents. In Proc. of 11th Int’l World Wide Web
Conf., pages 232–241, 2002.
[5] D. Ikeda, Y. Yamada, and S. Hirokawa. Expressive
power of tree and string based wrappers. In Proc. of
IJCAI-03 Workshop on Information Integration on the
Web (IIWeb-03), pages 21–26, 2003.
[6] T. Joachims. Text categorization with support vector
machines: Learning with many relevant features. In
Proc. of 10th European Conference on Machine
Learning, pages 137–142, 1998.
[7] H. Kashima and T. Koyanagi. Kernels forsemi-structured data. In Proc. of 19th International
Conference on Machine Learning (ICML 2002), pages
291–298, 2002.
[8] N. Kushmerick. Wrapper induction:efficiency andexpressiveness. Artificial Intelligence, 118:15–68, 2000.
[9] Y. Murakami, H. Sakamoto, H. Arimura, and
S. Arikawa. Extracting text data from html documents.
The Information Processing Society of Japan (IPSJ)
Transactions on Mathematical Modeling and its
Applications (TOM), 42(SIG 14(TOM 5)):39–49, 2001.
In Japanese.
[10] K. Tateishi, Y. Ishiguro, and T. Fukushima. A
reputation search engine that collects people’s opinions
by information extraction technology. The Information
Processing Society of Japan (IPSJ) Transactions on
Databases (TOD), 45(SIG 07), 2004. In Japanese.
[11] V. N. Vapnik. The Nature of Statistical Learning
Theory. Springer, New York, NY, 1995.
11