Web ディレクトリ構築のためのハイパーテキストの階層的分類
鈴木 祐介†

松原 茂樹‡†名古屋大学大学院情報科学研究科

吉川 正俊†‡名古屋大学情報連携基盤センター

suzuki@dl.itc.nagoya-u.ac.jp

1

はじめに学会

Web 上には大学サイトや趣味のサイトなど様々な分野のサイトが存在している．Web からこのような関連
言語処理学会
出版物
研究会
全国大会
したサイトを探す方法として，Yahoo!カテゴリ1 に代表
情報処理学会される Web ディレクトリの使用が挙げられる．しかし，
電子情報通信学会
このような Web ディレクトリは Web 全体を対象としているため，分類はサイト単位で行なわれることが多
会誌
論文投稿プログラム
く，特定分野の複数のサイトにまたがったページを見つけるためのツールとしては，必ずしも十分ではない．
そこで本論文では，複数の関連サイトのページを整図 1: 学会サイトによるサイト間 Web ディレクトリ
理したサイト間 Web ディレクトリの構築支援のために，Web ディレクトリの断片を生成する手法を提案する． に，概念的に上位-下位関係にある Web ページを対にしハイパーリンクをもとに概念的に上位-下位関係にある て抽出する．ここで，Web ページの概念的な上位-下位Web ページを対にして抽出し，階層的に分類する．分 関係とは，ページによる全体と部分，概要と詳細といっ類実験により，本手法の実現可能性を確認した．
た関係をいう．同じ内容のページ対をクラスタリングし2

サイト間 Web ディレクトリ

たのち，これをディレクトリの上位-下位関係とすることにより，ページが分類された上位-下位構造のディレクトリを作成する．内容が類似したディレクトリを統合してその構造を階層化することにより，部分グラフを生成し，各ディレクトリに対してラベルを付与する．以下の節では，手法の詳細について説明する．

図 1 の Web ディレクトリは，サイト間にまたがったページをその共通性に基づいてディレクトリとしてまとめ，階層化したものである．これにより，サイト間で関連したページの閲覧が容易になる，その分野のサイト内情報の全体像を把握できる，といった利点がある．
3.1 上位-下位関係の抽出
本論文では，このような特定分野のサイト群を対象に構複数の関連サイトから上位-下位関係にある Web ペー
築した Web ディレクトリをサイト間 Web ディレクトリと呼ぶ．しかし，その階層構造は対象分野によって異 ジを対として抽出する．これは，リンクで結ばれた同一なるため，開発者による階層構造の設計や，ディレクト サーバ上の 2 つのページに対して，以下の条件を満たすリンク元ページとリンク先ページを Web ページ対とリへのページの分類には多大な労力を要する．
本研究では，サイト間 Web ディレクトリの構築支援 して抽出する．のために，Web ディレクトリの部分グラフを生成する． 1. リンク先ページがリンク元ページの子孫フォルダ
部分グラフとは，木構造の Web ディレクトリをグラフに存在する．としたとき，その部分を構成するディレクトリ構造であ2. リンク先ページがリンク元ページと同一のフォルる．開発者は複数の部分グラフを組み合わせることによ
ダに存在する場合，り，対象とするサイト群に適した Web ディレクトリを(a) リンク元ページが中心ページである．中心ペー構築でき，その設計や分類にかかる負担を軽減できる．
ジとはファイル名が “index.html”であるペー
ジとし，もし，存在しなければ，同一フォルダ
3 部分グラフの生成内のページへのリンクが最多のページとする．
複数の関連サイトから部分グラフを生成する様子を図(b) リンク元ページは中心ページからリンクされ2 に示す．まず，Web ページ間のハイパーリンクをもとており，一方，リンク先ページは中心ページ
1 http://dir.yahoo.co.jp/からリンクされていない．

クラスタリング

上位ページ

全国大会

全国大会

論文投稿

論文投稿

全国大会
論文投稿

下位ページ
１．各サイトから上位-下位関係にあるWebページを対にして抽出（a） 上位ディレクトリの統合

２．同じ内容のページ対をまとめて，上位-下位構造のディレクトリを作成

統合

図 3: ディレクトリの統合

学会

全国大会 全国大会
論文投稿 プログラム

全国大会
論文投稿

出版物
プログラム

３．ディレクトリの統合を繰り返して部分グラフを構築（b） 上位ディレクトリと下位ディレクトリの統合

siminf (Ck , Cl ) =研究会

1 ∑ ∑(sim(diinf ,djinf )) (3)nk nlpi ∈Ck pj ∈Cl

会誌

なお，nk は Ck に含まれる Web ページ対の数を表す．

４．ディレクトリにラベルを付与

3.3

部分グラフの構築

図 2: 提案手法の概要

各クラスタは Web ページ対の集合であり，クラスタ内の上位ページ集合と下位ページ集合をそれぞれ 1 つの以下では，上位側の Web ページを dsup ，下位側のディレクトリとすることにより，ディレクトリの上位-下Web ページを dinf とし，その Web ページ対を p =位構造を形成する．上位側のディレクトリを Dsup ，下(dsup , dinf ) で表す．また，dsup を上位ページ，dinf を位側のディレクトリを Dinf とし，そのディレクトリ対下位ページと呼ぶ．
を P = (Dsup , Dinf ) で表す．以下では，Dsup を上位ディレクトリ，Dinf を下位ディレクトリと呼ぶ．
3.2 Web ページ対のクラスタリング
部分グラフはディレクトリを統合して構築する．ディサイト間で共通する内容のページをまとめるために，レクトリ対の上位ディレクトリを統合すると，図 3(a)各サイトから抽出したページ対のうち，同じ内容のペーのような親子関係にある階層構造が生成され，上位ディジ対をまとめる．ここで，ページ対の内容が同一であるレクトリと下位ディレクトリを統合すると，図 3(b) のとは，Web ページ対の上位ページ間の内容と下位ペーような 3 代の階層構造が生成される．
ジ間の内容がそれぞれ類似していることと定義する．なディレクトリ間の類似度にはベクトル空間モデル [3]お，Web ページは，その内容を端的に表現している箇を適用する．ディレクトリ Di 内の Web ページを参照
所として，そのページを参照しているアンカーテキス
するアンカーテキストの集合を Ai とした場合，Di はトを用いて表現する．ページ間の類似度は，各ページをAi 中の名詞の出現頻度を重みとした特徴ベクトルで表参照するアンカーテキスト間の Dice 係数の最大値とす現する．出現する名詞の集合を {e1 , · · · , eN } とし，名る．すなわち，ページ di を参照するアンカーテキスト
詞 ej の重み wij を式 (4) で定義すると，Di の特徴ベクを ais (1 ≤ s ≤ m)，ページ dj を参照するアンカーテキ
トルは，x~i = (wi1 , wi2 , · · · , wiN ) で表される．
ストを ajt (1 ≤ t ≤ n) とするとき，di と dj の類似度を
式 (1) で定義する．
wij = Fij
(4)

sim(di , dj ) =2Mis jt)
1≤s≤m,1≤t≤n Mis + Mjtmax((1)

なお，Fij は Ai における ej の頻度を表す．式 (4) を用いて，ディレクトリ対 Pi = (Disup , Diinf ) の上位ディ
なお，Mis は ais の名詞の数，Mis jt は ais ，ajt に共通 レクトリ Disup の特徴ベクトル ~xisup と下位ディレクト
して出現する名詞の数を表す．
リ Diinf の特徴ベクトル ~xiinf を求める．ディレクトリ
次に，Web ページ対 pi 自体からなる初期クラスタ Ci Di とディレクトリ Dj (i 6= j) の類似度を式 (5) で定義を作成する．クラスタリングは，クラスタの上位ページ する．
間の類似度と下位ページ間の類似度が共に閾値 α 以上
~xi • ~xj
Sim(Di , Dj ) =(5)で，その平均が最大となるものから順に行なう．なお，|~xi ||~xj |クラスタの類似度の計算には，上位ページ間と下位ペー
式 (5) を用いて，ディレクトリ対 Pi と Pj の上位ディレジ間それぞれに対して，群平均法 [2] を適用する．クラクトリ間の類似度 Sim(Disup , Djsup ) と上位ディレクト
スタ Ck と Cl の上位ページ間の類似度 simsup (Ck , Cl )リと下位ディレクトリ間の類似度 Sim(Disup , Djinf ) をと下位ページ間の類似度 siminf (Ck , Cl ) を式 (2)，及び，求める．
式 (3) でそれぞれ定義する．
ディレクトリの統合は，ディレクトリ間の類似度が閾
1 ∑ ∑値
β 以上で，その値が最大となるものから順に，部分simsup (Ck , Cl ) =(sim(disup ,djsup )) (2)nk nl
グラフが木構造になるように統合することにより実現すpi ∈Ck pj ∈Cl表 2: 正解 Web ディレクトリ

表 1: 実験に使用したサイトとデータ量サイト
北海道大学大学院情報科学研究科
東北大学大学院情報科学研究科
名古屋大学大学院情報科学研究科
京都大学大学院情報学研究科
九州大学システム情報科学研究院
電気通信大学情報システム学研究科
筑波大学システム情報工学研究科
奈良先端科学技術大学院大学情報科学研究科

ページ数118
256
140
69524
186
222148

ID
A
A-1
A-2
A-3
A-4
A-5A-6A-6-1
A-6-2
A-7A-8

ディレクトリ名情報系研究科研究科長挨拶
研究科紹介
専攻・講座一覧
教員一覧
講義一覧
入試情報
博士課程 (前期) 募集要項
博士課程 (後期) 募集要項
アクセス
サイトマップ

ページ数86101191016181786る．ディレクトリの統合により木構造が崩れる場合は， ある．そこで，実験には，分野の同じ関連サイトとしてディレクトリ間の類似度が次に高いディレクトリ対に処 8 つの国立大学の情報系研究科サイトを使用した．サイ
理を移して同様の操作を行なう．これをすべてのディレ ト名とその Web ページ数を表 1 に示す．実験では，各ページを表現するアンカーテキストは，各サイト内のクトリ間類似度が閾値 β 未満になるまで繰り返す．
類似度が閾値未満になった時点で，統合するディレク Web ページから取得する．なお，閾値の設定は，α = 0.6
トリをまとめて新たなディレクトリを作成する．統合す （3.2 節参照），β = 0.8（3.3 節参照）とし，Web ページるディレクトリを D1 , · · · , Dn ，新たに生成するディレ 対が 2 個未満のクラスタは処理の対象外とした．また，クトリを Dr とし，ディレクトリ Di に属する Web ペー 形態素解析器には「茶筌」[4] を使用した．
実験の評価値として分類の精度と再現率を定義する．
ジの集合を Wi とすると，Dr に属する Wr は式 (6) でこれは，あらかじめ正解の Web ディレクトリを作成し定義される．
∪Wi(6) ておき，各正解ディレクトリに対して，すべての部分Wr =グラフのディレクトリと比較することにより求める [1]．
1≤i≤n
正解ディレクトリ Ai に対して，部分グラフの各ディレ3.4 ディレクラベルの付与
クトリ Dj における F 値を求め，その最大値を Ai に対ディレクトリラベルは，そのディレクトリ内の Web する評価値とする．Ai に対する Dj の精度 Pij と再現率ページを参照するアンカーテキスト集合から作成する． Rij を式 (9) で定義し，その F 値を式 (10) で定義する．
まず，ディレクトリ Di に対するアンカーテキスト集合
xij
xij
Pij =， Rij =(9)Ai = {ai1 , · · · , aiM } からラベルとして適切な任意の部
djai
分形態素列 sij を抽出し，これらを Di のラベルの候補と2Pij Rij
F (Ai , Dj ) =(10)する．ここで，適切なラベルとは，形態素列の先頭や末Pij + Rij
尾に助詞や副詞などの品詞が出現しないものとする．抽出された sij に対して，Ai のアンカーテキスト aik にお ここで，dj は Dj に含まれるページ数，ai は Ai に含ける包含率 Cover(sij , aik ) を式 (7) より求め，式 (8) で まれるページ数，xij は Ai と Dj に含まれるページ数
定義する平均包含率 CoverAve (sij , Ai ) を計算する．平 を表す．さらに，正解ディレクトリの評価値をすべて足したものを正解 Web ディレクトリ全体の評価値とする．
均包含率が最大となる sij を Di のラベルとする．
i
これを式 (11) で定義する．また，このときの正解 Web{ Fjki(|sij | ≤ Fjk)
|aik |
ディレクトリに対する精度
P と再現率 R を式 (12) で定Cover(sij , aik ) =(7)0 (otherwise)
義する．
∑M
Cover(s,a)∑ aiijik(8)CoverAve (sij , Ai ) = k=1( ∑ ) max F (Ai , Dj ) (11)
T otalScore =Mji aiii∑∑
なお，|aik | は aik の形態素数，Fjk は sij と aik に共通
ai xikai xik
P =(∑ )
， R=(∑ )(12)
して出現する形態素数，|sij | は sij の形態素数，M はadki ii ai aiii
Ai 中のアンカーテキストの数を表す．
このとき，dk は対象とする Ai に対して F 値を最大とするディレクトリ Dk に含まれるページ数とする．
4 実験と評価
実験に使用した 8 つのサイトから人手で正解 Web ディ
4.1 実験方法レクトリを作成した．作成した正解 Web ディレクトリ
本研究で対象とするサイト間 Web ディレクトリは， を表 2 に示す．なお，表中で「ID」はディレクトリの階特定分野における関連サイトのページを分類したもので 層を表している．

表 3: ディレクトリへの分類結果
適合率 (%) 再現率 (%) F 値

72.9（2）（1）
判定30.340.5

表 4: 階層構造の適切さの評価結果
個数 割合 (%)

上位-下位関係がある

3443.6

同位の関係である

291537.219.2

上位-下位関係がない，逆転する（3）
図 4: 部分グラフの出力例

判定

表 5: ラベルの正しさの評価結果
個数 割合 (%)

ラベルが正確で理解できる

4.2

実験結果

ラベルが一部異なるが理解できる

64362750.428.321.3

ラベルが異なるため理解できない
実験の結果，生成された部分グラフの数は 33 個であった．また，部分グラフあたりの平均ディレクトリ数は4.7 個，ディレクトリあたりの平均ページ数は 3.4 ペー いる．これらのディレクトリのページをまとめることがジであった．生成された部分グラフの出力例を図 4 に示 できれば，分類の再現率向上に繋がると考えられる．
す．図中の (1) は各部分グラフのルートディレクトリ，(2) は選択された部分グラフの全体図，(3) は選択され 4.3.2 ディレクトリラベルの正確さたディレクトリに分類された Web ページへのリンクを 評価方法 すべての部分グラフの各ディレクトリに対それぞれ表している．
して，ラベルがそのディレクトリ内のページ内容を適切
正解 Web ディレクトリ全体に対する評価結果を表 3 に表現しているか，ラベルからページ内容を理解できるに示す．再現率は必ずしも高くはない．生成された部分 かを判定する．判定は，表 5 の判定基準のいずれかに分グラフを観察すると，同じ内容のページでまとまっては 類することにより行なう．
いるものの，複数のディレクトリに分散して存在してい 評価結果 評価結果を表 5 に示す．ラベルからページることが多く見られた．しかし，“A-8 サイトマップ” 内容が分かると判定されたものは 78.7%であり，多くがに対応するディレクトリには 4 サイトの正解ページが， ページ内容を反映したものであることが分った．
“A-1 情報系研究科”では 3 サイトの正解ページが分類されているように，複数の関連サイトのページが正しく 5まとめ分類されたディレクトリも存在する．
本論文では，サイト間 Web ディレクトリの部分グラフを生成する手法を提案した．また，実験により本手法
4.3 考察の実現可能性を確認した．今後の課題としては，現在，生成された部分グラフの妥当性を評価するために，「階上位-下位関係にある Web ページはリンクにより推定し層構造の適切さ」と「ラベルの正確さ」についても評価ているが，サイトによるリンク構造の違いから抽出できした．これらの評価は，0.7 以上の精度をもつディレクないページ対も存在する．テキスト情報も用いて上位トリを対象に行った．
下位関係を判定できれば，多くのページ対を抽出でき，分類の再現率の改善にも繋がると考える．
4.3.1 階層構造の適切さ
評価方法 すべての部分グラフで親子関係にあるディレクトリ内のページ内容を比較し，それらが適切な上位下位関係を形成しているかを判定する．判定は，表 4 の判定基準のいずれかに分類することにより行う．
評価結果 評価結果を表 4 に示す．上位-下位関係があると判定された割合が最も多いが，同位の関係であると判定された割合も多かった．同位の関係とは，親ディレクトリと子ディレクトリが共に同じ内容のページを含む関係である． この結果は，同じ内容のページが 1 つのディレクトリにまとまってない場合でも，それらは近くのディレクトリに位置している傾向があることを示して

参考文献[1] 小島 秀一，高須 淳宏，安達 淳: Web ページ群の構造解
析とグループ化，NII Journal, No.4, pp.23-35, 2002.
[2] Pang-Ning Tan, Michael Steinbach and Vipin Kumar:
Introduction to Data Mining. Addison-Wesley, 2005.
[3] Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval. Addison Wesley, 1999.
[4] 松本 裕治，北内 啓，山下 達雄，平野 善隆，松田 寛，高岡 一馬，浅原 正幸: 形態素解析システム『茶筌』, ver-sion2.2.9, 使用説明書 (2002).