論文
Improvement in TF-IDF scheme for Web
Pages and its Retrieval Accuracy
Kazunari SUGIYAMA♥ Kenji HATANO♦
Masatoshi YOSHIKAWA♠ Shunsuke UEMURA♦
In IR (information retrieval) systems based on the vector
space model, the tf-idf scheme is widely used to characterize
documents. However, in the case of documents with hyperlink structures such as Web pages, it is necessary to develop
a technique for representing the contents of Web pages moreaccurately by exploiting that of their hyperlinked neighboring pages. In this paper, we first propose some methods for
improving the tf-idf scheme for a target Web page by using
the contents of its hyperlinked neighboring pages, and thencompare retrieval accuracy of our proposed methods.

1. Introduction
The WWW (World Wide Web) is a useful resource for users to obtain a great variety of information. However, since the number of
Web pages continues to grow, it is getting more and more difficult
for users to find relevant information on the WWW. Under thesecircumstances, search engines are one of the most popular methods for finding valuable information effectively. Recently, in orderto obtain more higher retrieval accuracy, the hyperlink structures of
Web pages are taken into account in IR systems. For example, IR
systems based on the concept of “Optimal Document Granularity”
using the hyperlink structures of Web pages [1, 2, 3] are proposed.
However, as for these works, we do not believe that users could understand the search results intuitively because the multiple query
keywords disperse in several hyperlinked Web pages. In addition,although HITS (Hypertext Induced Topic Search) [4] and PageRank[5] achives higher retrieval accuracy using the hyperlink structuresof Web pages, these algorithms have shortcomings in that (1) the
weight for a Web page is merely defined; and (2) the relativity ofcontents among hyperlinked Web pages is not considered. As a result, the problem of Web pages irrelevant to user’s query often being
ranked higher still remains. Therefore, in order to provide users
with relevant Web pages, it is necessary to develop a technique forrepresenting the contents of Web pages more accurately. To achieve
this purpose, we have proposed some methods for improving a feature vector for target Web page [6]. Our proposed methods, however,also have a problem in that only Web pages out-linked from a target Web page are exploited to generate the feature vector of target
Web page. Therefore, in this paper, we propose three methods for improving the tf-idf scheme [7] for a target Web page using both its inand out-linked pages in order to represent the contents of the target
Web page more accurately. Our method is novel in improving tf-idf
based feature vector of target Web page by reflecting the contents of
its hyperlinked neighboring Web pages.

2.

Proposed Method

On the basis of the problems of IR systems described in Section
1, in order to represent the contents of Web pages more accurately,
the feature vector of a Web page should be generated by using thecontents of its hyperlinked neighboring pages. We, therefore, propose improving the tf-idf scheme for a target Web page by using thecontents of its hyperlinked neighboring pages. Unlike the works described in Section 1, our method is novel in improving tf-idf based♥ Student Member

Graduate School of Information Science,
Nara Institute of Science and Technology
kazuna-s@is.aist-nara.ac.jp♦ Regular Member Graduate School of Information Science,
Nara Institute of Science and Technology{hatano, uemura}@is.aist-nara.ac.jp♠ Director Information Technology Center, Nagoya University
yosikawa@itc.nagoya-u.ac.jp

1

DBSJ Letters Vol. 2, No. 1
feature vector of a target Web page by reflecting the contents of its
hyperlinked neighboring Web pages.
In the following discussion, let a target page be ptgt . Then, we
define i as the number of the shortest directed path from ptgt . Let
us assume that there are Ni Web pages (pi1 , pi2 , · · · , piNi ) in the ith
level from ptgt . Moreover, we denote the feature vector wptgt of ptgt asfollows:p

p

p

w ptgt = (wt1tgt , wt2tgt , · · · , wtmtgt ),(1)

where m is the number of unique terms in the Web page collection,and tk (k = 1, 2, · · · , m) denotes the each term. Using the tf-idf scheme,p
we also define the each element wtktgt of w ptgt as follows:t f (tk , ptgt )Nwebp
wtktgt = m· log,
d f (tk )s=1 t f (ts , ptgt )(2)

where t f (tk , ptgt ) is the frequency of term tk in the target page ptgt ,Nweb is the total number of Web pages in the collection, and d f (tk ) is
the number of Web pages in which term tk appears. Below, we refer
to w ptgt as the “initial feature vector.” Subsequently, we denote theimproved feature vector wptgt as follows:
p

p

p

wptgt = (wt1 tgt , wt2 tgt , · · · , wtmtgt ),(3)and refer to this wptgt as the “improved feature vector.” As we describe below, we propose three methods for improving the “initialfeature vector” based on the tf-idf scheme defined by Equation (2).

Method I
In this method, we reflect the contents of all Web pages at levels
up to L(in) th in the backward direction and levels up to L(out) th in theforward direction from the target page ptgt . Based on the ideas that(1) there are Web pages similar to the contents of ptgt in the neighborhood of ptgt ; and (2) since on one hand such Web pages exist rightnear ptgt , on the other hand they might exist far removed from ptgt
in the vector space, we reflect the distance between w ptgt and feature vector of in- and out-linked pages of ptgt in the vector space oneach element of initial feature vector w ptgt . For example, Figure 1(a)shows that wptgt is generated by reflecting the contents of all Web
pages at levels up to second in the backward and forward directions
from ptgt on w ptgt . In Figure 1(a), pi j(in) and pi j(out) correspond to thejth page in the ith level in the backward and forward directions from
ptgt , respectively. Additionally, Figure 1(b) shows that improved feature vector wptgt is generated by reflecting each feature vector of inand out-linked pages of ptgt on the initial feature vector w ptgt . In thispmethod, each element wtk tgt of wptgt is defined as follows:p

wtk tgtp

wtktgt=pi jL(in) Ni(in)
wtk (in)1   



pi j
p
Dim  i=1 j=1 dis(w tgt , w (in) ) 

+



pi j
L(out) Ni(out)wtk (out)
1   .
Dim  i=1 j=1 dis(w ptgt , w pi j(out) ) 

+

p

(4)

p

If the distance between w ptgt and w i j(in) , w i j(out) in the vector spaceis very close, the values of the second and third terms of Equationp(4) can be dominant compared with the first term wtktgt . Therefore,
in order to prevent this phenomenon, we also define Dim, which
denotes the number of unique terms in the Web page collection.
ppdis(w ptgt , w i j(in) ) and dis(w ptgt , w i j(out) ) are defined the following equations, respectively:
p

m


pi j

m


dis(w ptgt , w i j(in) ) =

pi j

(wtk

ptgt

− wtk (in) )2 ,ptgt

− wtk (out) )2 .

k=1

dis(w ptgt , w(out) ) =

(wtk

pi j

k=1

日本データベース学会 Letters Vol. 2, No. 1

論文

DBSJ Letters Vol. 2, No. 1

p

LN L

(in)

pi j

(in)

tm
p21

p2N

p22

(in)

2(in)

(in)

p11

p12

(in)

wptgt (initial feature vector of target page ptgt )

p1N

(in)

w’ tgt (improved feature vector of target pageptgt )

1(in)

p

ptgt
p

p

11

p

12

(out)

p

(out)

p22

21(out)

t3

1N1

(out)

feature vectors ofneighboring Web pages
hyperlinked from target page ptgt

p2N2(out)

(out)

t2
t1

(b)

pi j

(out)

p

LN L

(out)

(a)

Fig.1 The improvement of a feature vector as performed by Method I [(a) in the Web space, (b) in the vector space].
G

L(in)

pLN

L(in)

pi j

G

i (in)

(in)

G

2(in)

p

p

21

(in)

G

1(in)

tm

p

22

2N 2

(in)

(in)

p11

p12

(in)

(in)

p1N

p

w tgt (initial feature vector of target page ptgt )pw’ tgt (improved feature vector of target page p )

1(in)

tgt

clusters generated
from groups of Web pages
in each level from target page
t3
t2

ptgt
p11

G

1(out)

p21
G

(out)

(out)

p12

(out)

p22

p1N

1(out)

centroid vectorsof the clustersp2N

2(out)

(out)

t1

(b)

2(out)Gpi ji (out)

(out)

pLN

G

L

(out)

L(out)(a)Fig.2 The improvement of a feature vector as performed by Method II [(a) in the Web space, (b) in the vector space].
Method II
In this method, we first construct Web page groups G i(in) at eachlevel up to L(in) th in the backward direction, and Gi(out) at each levelup to L(out) th in the forward direction from the target page ptgt . Then,we generate wptgt by reflecting centroid vectors of clusters generated
from Gi(in) and G i(out) on initial feature vector w ptgt . This method isbased on the idea that Web pages at each level in the backward andforward directions from ptgt is classified into some topics in the eachlevel. In addition, we reflect the distance between w ptgt and the centroid vectors of the clusters in the vector space on each element of
the initial feature vector w ptgt . In other words, we first create Web
page groups G i(in) and G i(out) defined as follows:
Gi(in) = {pi1(in) , pi2(in) , · · · , piNi
Gi(out) = {pi1(out) , pi2(out) , · · · , piNi

(in)

(out)

},

(5)

},

(6)

(i = 1, 2, · · · , L),and then produce K clusters in each Web page group Gi(in) and G i(out)gby means of the K-means algorithm [9]. The centroid vectors w ic(in)g
and w ic(out) (c = 1, 2, · · · , K) are produced in Gi(in) and G i(out) , respectively. We generate an improved feature vector wptgt by reflecting theggdistance between each centroid vector, w ic(in) , w ic(out) and the initialfeature vector w ptgt on w ptgt . For instance, Figure 2(a) shows that weconstruct Web page groups G1(in) , G 2(in) , G1(out) , and G2(out) at each levelup to second in the backward and forward direction from ptgt , andgenerate an improved feature vector wptgt by reflecting the centroid
vectors of each cluster produced in each Web page group G1(in) , G 2(in) ,G 1(out) , and G2(out) on w ptgt . Moreover, Figure 2(b) shows that improved
feature vector wptgt is generated by reflecting the centroid vectors ofpeach cluster on w ptgt . In this method, we define each element wtk tgt ofwptgt as follows:

2

ptgt

wt k

ptgt

=

wt k



gic
L(in) K
wtk (in)1   



g
Dim  i=1 c=1 dis(w ptgt , w ic(in) ) 

+



gic
L(out) K
wtk (out)
1   


.
Dim  i=1 c=1 dis(w ptgt , wgic(out) ) +(7)

We introduce Dim for the purpose of preventing the values of the second and third terms from dominating compared with the first termgg
in Equation (7). dis(w ptgt , w ic(in) ) and dis(w ptgt , w ic(out) ) are defined asfollows:
g

m


gic

m


dis(w ptgt , w ic(in) ) =

p

gic

p

gic

(wtktgt − wtk (in) )2 ,k=1

dis(w ptgt , w(out) ) =(wtktgt − wtk (out) )2 .

k=1

Method III
This method is based on the idea that Web pages at levels up toL(in) th in the backward direction and levels up to L(out) th in the forward direction from the target page ptgt is composed of some topics.
According to this idea, we cluster the set of all Web pages at levels
up to L(in) th in the backward direction and levels up to L(out) th in theforward direction from ptgt , and generate wptgt by reflecting centroid
vectors of the clusters on the initial feature vector w ptgt . Furthermore, we reflect the distance between w ptgt and the centroid vectorof the cluster in the vector space on each element of w ptgt ; in otherwords, we create Web page groups Gi(in) and G i(out) as defined by Equation (8) and (9), respectively,

日本データベース学会 Letters Vol. 2, No. 1

論文

DBSJ Letters Vol. 2, No. 1

G

L(in)

p

LN L

(in)

p

G

ij

i(in)

(in)

G

p

2(in)

p

21

2N2

(in)

G

1(in)

tm

p

22

(in)

(in)

p11

p12

(in)

p1N

(in)

wptgt (initial feature vector of target page ptgt )pw’ tgt (improved feature vector of target page p )

1(in)

tgt

ptgt
p

G

p12

11
1(out) (out)

p

p1N

(out)

(out)

1(out)

pp22

21

clusters generated from groups of
Web pages in the backward andforward direction from ptgt
t3

centroid vectorsof the clusters

2N 2

(out)

(out)

G

t2
t1

2(out)

(b)

pi j

(out)

G

i(out)

pLN

L

(out)

G

(a)

L(out)

Fig.3 The improvement of a feature vector as performed by Method III [(a) in the Web space, (b) in the vector space].

Gi(in) = {p11(in) , p12(in) , · · · , p1N1(in)p21(in) , p22(in) , · · · , p2N2(in)pi1(in) , pi2(in) , · · · , piNi

(in)

,

Q = (qt1 , qt2 , · · · , qtm ),,},Gi(out) = {p11(out) , p12(out) , · · · , p1N1(out)

p21(out) , p22(out) , · · · , p2N2(out)

pi1(out) , pi2(out) , · · · , piNi

},

(out)

the “title” field in each Topics from 451 to 500 at the TREC WT10g
test collection. This query vector Q is denoted as follows:

(8)

,
,
(9)

(i = 1, 2, · · · , L),and produce K clusters in Gi(in) and G i(out) by means of the K-means alg
ggorithm. The centroid vectors w c(in) and w c(out) (c = 1, 2, · · · K) are produced in G i(in) and G i(out) , respectively. Then, we generate improved
feature vector wptgt by reflecting the distance between each centroidggvector w c(in) , w c(out) (c = 1, 2, · · · , K) and initial feature vector w ptgt on
w ptgt . For instance, Figure 3(a) shows that we construct Web pagegroups G2(in) and G 2(out) at levels up to second in the backward andforward direction from ptgt , and generate improved feature vectorwptgt by reflecting the centroid vectors of clusters produced in Web
page group G 2(in) and G 2(out) on the initial feature vector w ptgt . Furthermore, Figure 3(b) shows that improved feature vector wptgt is
generated by reflecting centroid vectors of each cluster on the initial
pfeature vector w ptgt . In this method, each element wtk tgt of wptgt isdefined as follows:p

wtk tgt=++p

wtktgt



gc
 K

wtk (in)1 gc(in) ptgt

Dim c=1 dis(w , w
) 



gc
 K

wtk (out)
1 


.
g
c
p
Dim  c=1 dis(w tgt , w (out) ) 

(10)

As mentioned in Method I and II, in order to prevent the value of thesecond and third term of equation (10) from becoming dominant comppared with the original term weight wtktgt , we introduce Dim, which
denotes the number of unique terms in the Web page collection. Weggalso define dis(w ptgt , w c(in) ) and dis(w ptgt , w c(out) ) as follows:gdis(w ptgt , w c(in) ) =

m


ptgt

(wtk

gc

− wtk (in) )2 ,k=1
gdis(w ptgt , w c(out) ) =

m


p

gc

(wtktgt − wtk (out) )2 .

k=1

3. Experiment
3. 1 Experimental Setup
The experiments to verify the retrieval accuracy were conducted using the TREC WT10g test collection [10]. Stop words were eliminated from all the Web pages in the collection and stemming was
performed. We formed query vector Q using the terms contained in

3

(11)

where m is the number of unique terms in the Web page collection,and tk (k = 1, 2, · · · , m) denotes the each term. Each element qtk of Q isdefined as follows:
Nweb
0.5 · Q f (tk )· log
qtk = 0.5 + m
d f (tk )s=1 Q f (t s )(k = 1, 2, · · · , m),(12)

where Q f (tk ), Nweb , and d f (tk ) is the number of index terms tk , the total number of Web pages in the test collection, and the number of
Web pages in which the term tk appears, respectively. As reported
in [11], Equation (12) is the element of a query vector that brings
the best search result. We then compute the similarity sim(wptgt , Q)
between improved feature vector wptgt and query vector Q. The
sim(wptgt , Q) is defined as follows:sim(wptgt , Q) =wptgt · Q.
|wptgt | · |Q|(13)

Based on the value of sim(wptgt , Q), we evaluate retrieval accuracy
using “precision at 11 standard recall levels” described in [12, 13].

3. 2 Experimental Results

We generated improved feature vector wptgt for initial feature vector w ptgt of target page ptgt using Method I, II, and III described in
Section 2 with respect to the following cases:
Method I(MI-a) where the contents of all Web pages at levels up to L(in) th in the
backward direction from ptgt reflect on the initial feature vector
w ptgt ,(MI-b) where the contents of all Web pages at levels up to L(out) th in theforward direction from ptgt reflect on the initial feature vector
w ptgt ,(MI-c) where the contents of all Web pages at levels up to L(in) th in
the backward direction and levels up to L(out) th in the forward
direction from ptgt reflect on the initial feature vector w ptgt ,Method II(MII-a) where the centroid vectors of clusters generated by the group of
Web pages at each level up to L(in) th in the backward direction
from ptgt reflect on the initial feature vector w ptgt ,(MII-b) where the centroid vectors of clusters generated by the groupof Web pages at each level up to L(out) th in the forward direction
from ptgt reflect on the initial feature vector w ptgt ,(MII-c) where the centroid vectors of clusters generated by the group of
Web pages at each level up to L(in) th in the backward directionand each level up to L(out) th in the forward direction from ptgt
reflect on the initial feature vector w ptgt ,Method III(MIII-a) where the centroid vectors of clusters generated by the groupof all Web pages at levels up to L(in) th in the backward direction
from ptgt reflect on the initial feature vector w ptgt ,日本データベース学会 Letters Vol. 2, No. 1

論文

DBSJ Letters Vol. 2, No. 1(MIII-b) where the centroid vectors of clusters generated by the groupof all Web pages at levels up to L(out) th in the forward direction
from ptgt reflect on the initial feature vector w ptgt ,(MIII-c) where the centroid vectors of clusters generated by the groupof all Web pages at levels up to L(in) th in the backward direction
and levels up to L(out) th in the forward direction from ptgt reflect
on the initial feature vector w ptgt .
In this paper, the space is limited, therefore, we show only the resultsthat illustrate the comparison of the best retrieval accuracy obtainedusing the Method I, II, and III. The detailed results obtained using
these methods and discussions on them are described in [8]. According to these results, we found that we could obtain the best retrieval
accuracy in comparison with the tf-idf scheme, in the case of generating improved feature vector by creating a group of all Web pages atlevels up to second in the backward direction from ptgt and producing three clusters from the group in Method III (MIII-a). In addition,
Figure 4 shows that, in any case of Method I, II, and III, the best retrieval accuracy is obtained using the contents of in-linked pages ofa target page. Therefore, it is assumed that more accurate feature
vectors of Web pages can be generated by assigning higher weight toin-linked pages rather than out-linked pages of a target page.
0.7
0.6’tfidf’’(MI-a), L(in)=3’’(MII-a), L(in)=3, K=3’’(MIII-a), L(in)=2, K=3’

improvement+0.029+0.029+0.032

precision

0.5

averageprecision
0.313
0.342
0.342
0.345

0.4
0.3
0.2
0.1
0

0

0.2

0.4

0.6

0.8

1

recallFig.4 Comparison of the best search accuracy obtained using
each Method I, II and III.

4. Conclusion
In this paper, in order to represent the contents of Web pages moreaccurately, we proposed three methods for improving tf-idf scheme
for Web pages using their hyperlinked neighboring pages. Our approach is novel in improving tf-idf based feature vector of target Web
page by reflecting the contents of its hyperlinked neighboring pages.
Then, we conducted experiments with regard to the following threemethods:• the method for reflecting the contents of all Web pages at levels
up to L(in) th in the backward direction and levels up to L(out) th in
the forward direction from the target page ptgt ,• the method for reflecting the centroid vectors of clusters generated from Web page groups created at each level up to L(in) th
in the backward direction and each level up to L(out) th in theforward direction from the target page ptgt ,• the method for reflecting the centroid vectors of clusters generated from Web page groups created at levels up to L(in) th in
the backward direction and levels up to L(out) th in the forward
direction from the target page ptgt ,and evaluated retrieval accuracy of improved feature vector obtained
from each method using recall precision curves. Compared with respective best retrieval accuracy obtained using these three methods,
we found that in-linked pages of a target page mainly affect for generating feature vector that represents the contents of the target page
more accurately. Consequently, it is assumed that more accuratefeature vector of Web pages can be generated by assigning higher
weight to in-linked pages rather than out-linked pages of a target
page. We plan to verify this assumption in future work.
In this paper, we used the K-means algorithm in order to classify
the features of in- and out-linked pages of a target page. However,since we have to set the number of clusters initially in the K-means
algorithm, we consider this algorithm to be inappropriate for classifying the features of Web pages that have various link environments.

4

Therefore, in future work, we plan to devise some clustering methods
appropriate for various link environments of Web pages. Moreover,in this paper, we focused on the hyperlink structures of the Web aiming at generating more accurate feature vectors of Web pages. However, in order to satisfy the user’s actual information need, it is more
important to find relevant Web page from the enourmous Web space.
Therefore, we plan to address the technique to provide users withpersonalized information.

[References][1] K. Tajima, Y. Mizuuchi, M. Kitagawa, and K. Tanaka. Cut as a
Querying Unit for WWW, Netnews, E-mail. In Proc. of the 9th
ACM Conference on Hypertext and Hypermedia (HYPERTEXT’98), pp. 235–244, 1998.
[2] K. Tajima, K. Hatano, T. Matsukura, R. Sano, and K. Tanaka.
Discovery and Retrieval of Logical Information Units in Web.
In Proc. of the 1999 ACM Digital Libraries Workshop on Organizing Web Space (WOWS ’99), pp. 13–23, 1999.
[3] W-S. Li, K. Selçuk Candan, Q. Vu, and D. Agrawal. Retrieving
and Organizing Web Pages by “Information Unit”. In Proc. of
the 10th International World Wide Web Conference (WWW10),
pp. 230–244, 2001.
[4] J. M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. In Proc. of the 9th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 1998), pp. 668–677, 1998.
[5] L. Page. The PageRank Citation Ranking: Bringing Order tothe Web.
http://google.stanford.edu/%7Ebackrub/pageranksub.ps, 1998.
[6] K. Sugiyama, K. Hatano, M. Yoshikawa, and S. Uemura. A
Method of Improving Feature Vector for Web Pages Reflecting
the Contents of their Out-Linked Pages. In Proc. of the 13th
International Conference on Database and Expert Systems Applications (DEXA2002), pp. 891–901, 2002.
[7] G. Salton and M.J. McGill. Introduction to Modern Information
Retrieval. McGraw-Hill, 1983.
[8] K. Sugiyama, K. Hatano, M. Yoshikawa, and S. Uemura. Refinement of TF-IDF Schemes for Web Pages using their Hyperlinked Neighboring Pages. In Proc. of the 14th Conference onHypertext and Hypermedia (HT’03) (to appear), 2003.
[9] J. MacQueen. Some Methods for Classification and Analysis ofMultivariate Observations. In Proc. of the 5th Berkeley Symposium on Mathmatical Statistics and Probability, pp. 281–297,
1967.
[10] D. Hawking. Overview of the TREC-9 Web Track. NIST Special Publication 500-249: The Ninth Text REtrieval Conference(TREC-9), pp. 87–102, 2001.
[11] G. Salton and C. Buckley. Term-weighting Approaches in Automatic Text Retrieval. Information Processing & Management,
Vol. 24(5), pp. 513–523, 1988.
[12] I. H. Witten and A. Moffatand T. C. Bell. Managing Gigabytes.
Van Nostrand Reinhold, pp. 149–150, 1994.
[13] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. ACM Press, 1999.

Kazunari SUGIYAMA
is currently a student of doctor course of Graduate School ofInformation Science, Nara Institute of Science and Technology. He has been working in information retrieval. He is a
student member of ACM, IEICE, IPSJ, JSAI.

Kenji HATANO
is an assistant professor of Graduate School of Information
Science, Nara Institute of Science and Technology. He has
been working in XML database and information retrieval.
He is a member of ACM, IPSJ.

Masatoshi YOSHIKAWA
is a professor of Information Technology Center, Nagoya University. He has been working in database system. He is amember of ACM, IEEE, IEICE, IPSJ.

Shunsuke UEMURA
is a professor of Graduate School of Information Science,
Nara Institute of Science and Technology. He has been working in database system. He is a fellow of IEEE, IEICE, IPSJ.

日本データベース学会 Letters Vol. 2, No. 1