HTMLタグを用いたWebページのクラスタリング手法

全文

(1)情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). 1. はじめに. HTML タグを用いた Web ページのクラスタリング手法. 今日 Web 上には膨大な量の多種多様な情報が存在し，様々な要求を満たす情報を Web 上より得ることが可能である．その膨大な情報の中から必要な情報を探し出すための情報検索技術は，いまや必要不可欠となっている．Web 情報検索の一般的な方法として Yahoo!. 折原. 大†1. 内海. 彰†2. や Google などに代表される検索エンジンがよく用いられるが，その検索結果には必要な情報とともに不必要な情報も多い．. 本論文は，検索結果を自動分類することで検索支援を行う 1 つの手法として，Web ページのタイプに着目したページのクラスタリング手法を提案する．本論文では， HTML タグの木構造の情報を用いたクラスタリング手法と HTML タグの n-gram と出現位置を考慮した頻度情報を用いたクラスタリング手法の 2 つを提案する．アンケートにより作成した正解データセットを用いた評価実験において，単語の分布（Bag-of-Words, BoW）に基づくクラスタリング手法や新聞などのテキストを対象とし文書タイプに分類を行う Multi-way Distributional Clustering（MDC）よりも， 2 つの提案手法のほうがクラスタリング精度において良い結果となった．また 2 つの提案手法間では，クラスタリング精度については分類傾向による差はあるものの全体では同等の精度であり，処理時間においては HTML タグの頻度情報を用いたクラスタリング手法が良好な結果となった．. そこで，検索結果として得られた情報を自動分類しユーザに提示することで検索支援を行う手法が多く研究されている．代表的なものに，Web ページの内容で文書クラスタリングを行う研究2),5),9),16),19) や，あらかじめ設定した Web ページのジャンルに自動分類する研究6),7),11),12),14),15),17),18) などがある．これらの研究に対して，本論文では Web ページの見た目や形式，スタイルといった「タイプに基づく分類」を文書クラスタリング手法を用いて行うことを目的とする．この「タイプに基づく分類」とは，Web ページの内容による分類とは違い Web ページの構成やレイアウト，見た目などに注目した分類であり，たとえば次のような分類である．. • 一般的にジャンルといわれるカテゴリに基づく分類 • 画像の有無やリンクなどに基づく分類. Web Document Clustering Using HTML Tags. • Web ページの全体的なレイアウトに基づく分類一般的にジャンルといわれるカテゴリに基づく分類では，「リンク集」「掲示板」「FAQ」と. Hiroshi Orihara†1 and Akira Utsumi†2. いったジャンルへ分類されることを意図している．たとえば，図 1 に示すような「米」というクエリに対する Web ページの検索結果の文書集合を分類対象とした場合，内容に基づく. In this paper, we propose two clustering methods based on HTML tags. These methods cluster Web pages according to their type or style, rather than classifying them into predefined genres. The one method is based on the tree structure of HTML tags, and the other is based on the frequency of HTML tags considering the n-gram of tags and the location of tags. In evaluation experiment, our methods achieved better performance than the Bag-Of-Words method and the Multi-way Distributional Clustering (MDC) method. The frequency method achieved as a good performance as the tree-structured method. In evaluation experiment of the overall processing time, the frequency method was faster than the tree-structured method.. 2910. 分類では「お米」に関する Web ページや「アメリカ」に関する Web ページなどトピックごとに Web ページを分類するが，タイプに基づく分類では「ニュースサイト」「blog サイト」「ショッピングサイト」といったジャンルへ分類する．このような分類は，特定のジャンルの情報が欲しい，もしくは逆に特定のジャンルの情報は必要ない場合などに有用である．画像の有無やリンク数などに基づく分類では，たとえば画像の有無で分類することで †1 電気通信大学大学院電気通信学研究科システム工学専攻 Department of Systems Engineering, Graduate School of Electro-Communications, The University of Electro-Communications †2 電気通信大学電気通信学部システム工学科 Department of Systems Engineering, Faculty of Electro-Communications, The University of Electro-Communications. c 2008 Information Processing Society of Japan .

(2) 2911. HTML タグを用いた Web ページのクラスタリング手法. 図 1 分類カテゴリの例 Fig. 1 An example of classified (or clustered) categories.. 図 2 クラスタリングを使ったタイプに基づく分類の例 Fig. 2 An example of clustered categories by page type.. 「ある料理のレシピを写真付きで紹介されている Web ページが欲しい」という場合に有用. 較や，単語の分布（BoW）に基づく手法や Bekkerman ら3) の手法との比較を行い，提案. である．Web ページの全体的なレイアウトに基づく分類では，たとえば Web ページにサイ. 手法の有用性を検証する．. トのメニュー（「ホーム」や「お問い合わせ」など）があるかどうかで分類することを意図. 2. 関連研究との比較. している．このようなタイプに基づく分類に関する研究は多く行われているが 6),7),11),12),14),15),17),18)，. 1 章でも述べたように，検索結果として得られた情報を自動分類する手法に関する研究は. これらの研究は，あらかじめ設定したカテゴリに分類しており，またそのカテゴリはそれぞ. 多く，これらは (1) どのようなカテゴリに分類するかという「分類カテゴリ」と，(2) どの. れの研究で異なり統一されたものがないという問題点がある．このような問題点に対して，. ような手法を用いて分類するかという「分類手法」の 2 つの観点から分けることができる．. あらかじめ用意したカテゴリに分類する静的な分類ではなく文書クラスタリング手法を使い. この 2 つの観点で分けた関連研究の分類を表 1 に示す．. 動的な分類を行うことで，Web ページの集合に応じた分類を行うことができ，また，図 2 に示すような階層的な分類や，たとえば同じニュースサイトでも写真付きの記事かそうでないかなど状況に応じたより詳細な分類へも対応できると考える．. まず，(1) の分類カテゴリに着目すると，(1a) の「何が書かれているのか」という文書（または Web ページ）の内容やトピックに基づき自動分類を行う「内容に基づく分類」と，. (1b) の「どのような種類，形式か」という文書（または Web ページ）のタイプに基づき自. そこで本論文では，文書クラスタリングを用いたタイプに基づく分類手法を提案する．形. 動分類を行う「タイプに基づく分類」の 2 つに大別することができる．この 2 つの手法の大. 式，スタイルといった Web ページのタイプは Web ページの見た目に表れることが多く，. きな違いは，どのような基準で分類を行うかという点である．なお，Finn ら6),7) や Meyer. Web ページの見た目は HTML タグにより記述されていることが多い．よって，この HTML. zu Eissen ら17) は，この「内容」と「タイプ」という 2 つの概念を互いに直交する概念と. タグの情報を用いることで Web ページのタイプによる分類を行うことができると考え，本. して考えており，本論文でも，この 2 つの概念を互いに直交するものとして分類している．. 論文では HTML タグ情報を用いて文書クラスタリングを行う．HTML タグを用いた文書. 一方，(2) の分類手法に着目すると，(2a) のあらかじめ分類カテゴリを作成し，それらの. クラスタリング手法として，本論文では HTML タグの頻度に基づく手法と，HTML タグ. カテゴリに文書を振り分けていく「テキスト分類手法（Text categorization, Text classifi-. の木構造に基づく手法を提案する．そして，評価実験で本論文で提案する 2 つの手法間の比. cation）」と，(2b) の文書クラスタリング手法を用いて文書集合から分類カテゴリを動的に. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). c 2008 Information Processing Society of Japan .

(3) 2912. HTML タグを用いた Web ページのクラスタリング手法表 1 関連研究の分類 Table 1 Classification of related studies.. (2) 分類手法. (2a) テキスト分類手法 (2b) 文書クラスタリング手法. (1) 分類カテゴリ (1a) 内容に (1b) タイプに基づく分類基づく分類文献 1)，8)，20) 文献 6)，7)，11)， 12)，14)，15)， 17)，18) 文献 2)，5)，9)，文献 3) 16)，19). ど）14),15),17) これらの関連研究に対して，本論文で提案する手法では Web 特有の情報である HTML タグの出現頻度を用いている．同じく HTML タグの出現頻度を用いている関連研究12),14),15),17),18) では，HTML タグの単純な出現情報，もしくは特定のタグの出現頻度を用いているが，本論文では，特徴ベクトルの構成においてこれらの研究とは異なる新たな 3 つの属性を提案する．HTML タグの頻度に基づくクラスタリング手法では，HTML タグが文書中のどの位置に出現したかを考慮する「分割数」と，HTML タグを単独で扱わずに n-gram をとることで前後のタグも考慮する「n-gram」の 2 つの属性を提案し，この 2 つを組み合わせた手法を提案する．HTML タグの木構造に基づくクラスタリング手法では，. 作成し自動分類を行う「文書クラスタリング手法（Document clustering）」の 2 つに大別. HTML タグが木構造を持つことに着目し，この木構造に基づく属性を提案する．これらの. することができる．この 2 つの手法の大きな違いは，自動分類結果の分類カテゴリが，テキ. 提案する属性については，それぞれ 3.1.1，3.1.2 項で詳しく述べる．. スト分類手法はあらかじめ用意された静的な分類（classification）であり，文書クラスタリング手法は文書集合ごとに作られる動的な分類（clustering）であるという点である．これらの関連研究に対して，本論文では (2b) の文書クラスタリング手法を用いた (1b) の. 3. HTML タグを用いたクラスタリング手法本論文で提案する HTML タグを用いたクラスタリング手法は，次の 3 つのステップから. タイプに基づく分類を目的とする．表 1 に示したように，本論文と同じく文書クラスタリン. なる．. グ手法を用いたタイプに基づく分類を行う関連研究はほとんどない．その中でも，文献 3). Step.1 ［特徴ベクトルの構成］クラスタリングの対象となる各 Web ページを HTML タ. は本論文と同じ目的であるが，分類対象の文書が一般的な文書であり，本論文と同じ Web. グの情報を用いた特徴ベクトルで表現する．本論文では，HTML タグの頻度に基づく. ページを対象とした関連研究はない．. 特徴ベクトルの構成方法と，HTML タグの木構造に基づく特徴ベクトルの構成方法の. 次に，分類に用いる素性について述べる．一般的に (1b) のタイプに基づく分類であげた関連研究においては，分類に次のような素性が用いられている．. • 語に基づく情報. 2 つの手法を提案する． Step.2 ［距離の計算］Step.1 の特徴ベクトルを用いて，各 Web ページ間の距離を計算する．. – 単語の出現頻度（Bag-of-Words，BoW）3),6),7),14),15),17) – 品詞の出現頻度（Part-of-Speech，PoS）3),6),7),14),15),17) – 各カテゴリに固有のキーワード6),7),11),12),17),18) • 文書に基づく情報. Step.3 ［クラスタの生成］Step.2 で求めた Web ページ間の距離に基づき，Ward 法による階層的クラスタリングを行いクラスタを生成する．. 3.1 特徴ベクトルの構成クラスタリングの対象となる各 Web ページ i に対して，特徴ベクトル Di を構成する．本. – 疑問文，命令文などの文型や，名詞句，動詞句などの句の出現頻度14),15). 論文では，特徴ベクトル Di の構成方法として，HTML タグの頻度に基づく特徴ベクトル. – 文や段落の平均の長さなどの統計的情報（Text Statistics）6),7),14),15),17). と HTML タグの木構造に基づく特徴ベクトルの 2 つの構成方法を提案する．以下に各特徴. • Web 特有の情報. ベクトルの構成方法について述べる．. – HTML タグの出現頻度 – タイトルに関する情報. 12),14),15),17),18). 12),14),15). – URL に関する情報（深さ，ドキュメントタイプ（html，pdf など），ドメインな. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). 3.1.1 HTML タグの頻度に基づく特徴ベクトルの構成 HTML タグの頻度に基づく特徴ベクトルは，Web ページ（HTML 文書）に出現する HTML タグの出現順や出現位置の情報を用いて構築する．ここで，本論文では HTML タ. c 2008 Information Processing Society of Japan .

(4) 2913. HTML タグを用いた Web ページのクラスタリング手法. グの出現順を考慮したタグの「n-gram n」と HTML タグの出現位置を考慮した「分割数. m」という 2 つの属性を提案する．「n-gram n」では，HTML タグを個々で扱うのではなく，連続する n 個のタグの並びを. トル Di の属性値 Dik を，以下の式を用いて求める．. Dik = lik · gk. (1). 1 つの属性として扱う．たとえば，ニュース記事一覧やリンク集のようなページにはリンク. 本論文では，属性値の計算方法（local weight）lik と idf 値の考慮の有無（global weight）. が箇条書きなどの形で書かれることが多い．この場合，リンクを表す <A> タグとリストを. gk という 2 種類の重み付けの方法を組み合わせて属性値 Dik を求める．. 表す <LI> タグや改行を表す <BR> タグと連続しているかどうかを見ることで，このよ. 属性値の計算方法（local weight）lik. lik. うな特徴をとらえることができる．「分割数 m」では，HTML タグが HTML 文書中のだいたいどの位置に出現しているかを属性として扱う．HTML 文書中の HTML タグの出現位置と実際にブラウザに表示される位置は必ずしも一致しないが，本論文では HTML 文書中の HTML タグの出現順と Web ページの表示される位置はおおよそ同じ順序であると考える．たとえば，HTML 文書の冒. Web ページ i の各属性 k に対する local weight. を，その Web ページ i の中での出現頻度とする式 (2)，または出現の有無（出. 現すれば 1，出現しなければ 0 の 2 値）とする式 (3) のどちらかで求める．. lik = tfik. (2). . lik =. 頭部分には Web ページ全体のレイアウトや構成に関する情報などが出現しやすい．そこで，. 1 0. (tfik (tfik. > 0). (3). = 0). HTML 文書の冒頭部分に出現する HTML タグの出現傾向から Web ページ全体のレイアウ. 式 (2)，(3) において，tfik は Web ページ i に対する属性 k の出現頻度である．. トや構成の類似度をとらえることができる．. 図 3 (e) に属性値の計算方法による属性値 lik の例を示す．. この 2 つの属性を用いて，本論文では次のようにして HTML タグの頻度に基づく特徴ベ. IDF 値の考慮の有無（global weight）gk. 属性 k が全 Web ページのうちどれだけ. クトルを構成する．. 特徴的かを表す IDF 値を，考慮する場合は global weight gk を式 (4) とし，考慮. Step.1F-1 対象となる Web ページに対して HTML タグを抽出する．ただし，以下のタ. しない場合は式 (5) とする．. グについては抽出の対象としない．. • 各タグの終了タグ（</H1>，</P> など） • コメントタグ（<!- -）およびコメントタグに含まれているタグ. . gk = idf k =. log. N +1 df k. (4). gk = 1. (5) k. 図 3 (a) は Web ページの例であり，図 3 (b) は (a) より抽出される HTML タグの例で. 式 (4) において，N はクラスタリング対象となる Web ページ数を表し，df は属. ある．. 性 k が出現する Web ページ数を表す．. Step.1F-2 クラスタリングの対象となるすべての Web ページに対して，HTML タグの n-gram n と分割数 m を用いて特徴ベクトル Di の属性 k を決定する． n-gram n 抽出されたタグを，連続する n 個のタグの並びで組合せで 1 つの属性とする．図 3 (c) は，2-gram（n = 2）の場合の例である．分割数 m. Step.1F-4 Web ページ間の属性数の違いによる影響をなくすために，各特徴ベクトル Di の長さが 1 となるように正規化する．. 3.1.2 HTML タグの木構造に基づく特徴ベクトルの構成 HTML タグは入れ子構造を持っており，これを木構造として考えることができる．この. 抽出されたタグを，タグの並びで m 個の範囲に等分割し，それぞれの出現. HTML タグの木構造を用いることで，たとえば，Web ページの全体的なレイアウトとし. 位置ごとに属性とする．図 3 (d) は，Web ページを 2 つ（m = 2）に等分割した場. て使われている <TABLE> タグと表形式のデータを表すために使われている <TABLE>. 合の例である．. タグを，<TABLE> タグの子の数を見ることで区別することができる．このような場合を. 抽出された特徴ベクトル Di の属性 k の例を図 3 (e) に示す．. Step.1F-3 Step.1F-2 で抽出された各属性 k をもとに，Web ページ i に対する特徴ベク. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). 含め，HTML タグの木構造を考慮することで単純な HTML タグの頻度を用いるよりも分類精度が向上すると考える．そこで，HTML タグの木構造に基づく特徴ベクトルは，Web. c 2008 Information Processing Society of Japan .

(5) 2914. HTML タグを用いた Web ページのクラスタリング手法. 図 3 HTML タグの頻度に基づく特徴ベクトルの求め方の例．(a) 対象となる Web ページ（HTML 文書）．(b) (a) より抽出された HTML タグ．(c) ngram n = 2 の場合．(d) 分割数 m = 2 の場合．(e) 抽出された特徴ベクトルの属性，および属性値の計算方法 lik の計算結果 Fig. 3 Example of calculating a feature vector based on the HTML tag frequency. (a) Example of Web page. (b) HTML tags extracted from (a). (c) When two consecutive tags (i.e., n = 2) are assumed to be an attribute. (d) When a Web page is divided into two parts (i.e., m = 2). (e) Obtained attributes from this Web page, and the result of local weight lik calculation.. ページ（HTML 文書）に含まれている HTML タグから木構造を抽出し，この木構造の情. (1) すべての兄弟ノードをリンクで結び，(2) 各ノードの最初の子ノード（子ノードの. 報を用いて特徴ベクトルを構築する．. うちの左端のノード）とのリンクを除くすべてのリンクを削除する，ことで求められ. 一般的に木構造間の類似度（または距離）を求める手法には，主にボトムアップ最大共通部. る．図 4 (c) は木 Ti を 2 分木 B(Ti ) に変換した結果である．ここではさらに，木 Ti の. 分木による類似度，トップダウン最大共通部分木による類似度，編集距離（Edit Distance）. すべてのノード u について，子ノードが 2 つに満たない場合にという子ノードを付. など様々な手法がある. 21). ．その中で，Yang ら. 22). は，木構造を Binary Branch Vector と. 加し全二分木（full binary tree）とする．. いうベクトルで表現することで，編集距離の近似的で効率的な計算方法を提案している．本. Step.1T-3 Step.1T-2 により変換された 2 分木 B(Ti ) に対して Binary Branch b を定義. 論文では，Step.3 のクラスタの生成において Ward 法を用いており，Ward 法ではクラスタ. する．Binary Branch b は 2 分木 B(T ) のうちの任意のノードとその子ノードのみを. リングの対象が特徴ベクトルで表されている必要がある．このため，本論文では Yang ら22). 取り出したものであり，k 番目の Binary Branch bk は任意のノード u とその左の子. の Binary Branch Vector を用いて，次のようにして HTML タグの木構造に基づく特徴ベ. ノード ul ，右の子ノード ur を用いて bk = uul ur として表す．次に，Binary Branch. クトルを構成する．. Vector BRV を定義する．Binary Branch Vector BRV (Ti ) は，Binary Branch bk. Step.1T-1 対象となる Web ページから，HTML タグが持つ入れ子構造をノードの親子. を用いて BRV (Ti ) = (b1i , b2i , · · · , bi ) として表す．ここで bki は，ある 2 分木 Ti に. |Γ|. k. 関係として表した，HTML タグの木構造を抽出する．ただし，コメントタグ（<!- -）. おける Binary Branch b の出現回数とし，|Γ| はクラスタリング対象の文書集合中. およびコメントタグに含まれているタグについては抽出の対象としない．図 4 (a) は. の Binary Branch b の総数を表す．図 4 (d) は (c) の 2 分木 B(Ti ) を Binary Branch. Web ページの例であり，図 4 (b) は (a) より抽出される HTML タグの木 Ti である．. Vector BRV (Ti ) に変換した結果である．. Step.1T-2 Step.1T-1 で抽出された HTML タグの木 Ti を 2 分木 B(Ti ) に置き換える． 2 分木への変換の一般的な手法として，自分の兄弟ノードのうちの右隣のノードと自. Step.1T-4 Web ページ i に対する特徴ベクトル Di とその要素 Dik は，Binary Branch Vector BRV (Ti ) を使って次のように定義する．. 分の子ノードのうちの左端のノードを新たに自分の子とする表現方法がある．これは，. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). c 2008 Information Processing Society of Japan .

(6) 2915. HTML タグを用いた Web ページのクラスタリング手法. 図 4 Binary Branch Vector BRV への変換と HTML タグの木構造に基づく特徴ベクトルの求め方の例．(a) 対象となる Web ページ（HTML 文書）．(b) (a) より抽出された HTML タグの木構造 Ti ．(c) 木 Ti から全 2 分木 B(Ti ) へ変換．(d) 全 2 分木 B(Ti ) から Binary Branch Vector BRT (Ti ) へ変換 Fig. 4 Example of Binary Branch Vector representation and calculating a feature vector based on the HTML tag tree. (a) Example of Web page. (b) HTML tag tree Ti constructed from (a). (c) Conversion from the tree Ti to full binary tree B(Ti ). (d) Conversion from full binary tree B(Ti ) to Binary Branch Vector BRT (Ti ).. Di = BRV (Ti ). (6). 法，最長距離法，群平均法，重心法，Ward 法など様々な手法が提案されている．これらの. Dik. (7). 手法にはそれぞれ固有の癖があるが，本論文のように対象データに関する性質が未知の場合. =. bki. Step.1T-5 Step.1F-4 と同様に，各 Web ページ間でのドキュメントサイズの違い（タグ木の大きさの違い）による影響をなくすために，各特徴ベクトル Di の長さが 1 となるように正規化する．. には，一般的に Ward 法が最も良いとされている10) ．そこで，本論文でも Ward 法を用いてクラスタリングを行う1 ．. 4. 評. 3.2 距離の計算 3.1 節で求めた特徴ベクトル Di を用いて，各 Web ページ間の距離 d(Di , Dj ) を求める．. 価. 本論文で提案する 2 つの手法について既存手法との比較を含む評価実験を行った．比較対象の既存手法は，文書クラスタリング手法で一般的な文書中の単語の分布（BoW）. 本論文では，多次元ユークリッド空間の距離を用いる．. d(Di , Dj ) = |Di − Dj |. に基づく手法と，本論文と同じタイプに基づく分類を行う文書クラスタリング手法である. n (Dil − Djl )2 =. Bekkerman ら3) の手法を用いた． (8). l=1. ここで，比較対象とした 2 つの手法について簡単に述べる．BoW に基づく手法では，Web ページの HTML 文書からコメントや HTML タグを取り除いた本文に対して tf-idf による. 3.3 クラスタの生成. 重み付けを行った特徴ベクトルを構成し，提案手法と同じ距離の計算，クラスタの生成を. 3.2 節で求めた各 Web ページ間の距離 d(Di , Dj ) を用いて，クラスタリングを行う．本. 行った．次に，Bekkerman ら3) の手法（MDC）について簡単に述べる．文献 3) では，新. 論文では，文書集合の個々の文書をクラスタとする初期状態から距離の小さい 2 つのクラスタを順次併合していく，凝集型階層的クラスタリング法を用いる．ここで，併合されたクラスタと他のクラスタとの距離の再計算手法については，最短距離. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). 1 なお，本論文においてもこれら 5 つの再計算手法を実装し予備実験を行ったところ，直感的に最も良好な結果が得られたのが Ward 法であった．. c 2008 Information Processing Society of Japan .

(7) 2916. HTML タグを用いた Web ページのクラスタリング手法. 聞記事など一般的な文書を対象とした場合の文書のタイプに基づくクラスタリング手法について述べており，BoW に基づく手法や単語の品詞の分布（Part-of-Speech，PoS）に基づく手法よりも BoW と PoS を組み合わせた手法が最も良い結果となったことを示している．BoW と PoS の組合せには Multi-way Distributional Clustering（MDC）4) を用いており，文書集合 D と文書集合中の出現単語集合 W との相互情報量 I(D; W ) と文書集合 D と文書集合中の出現品詞集合 S との相互情報量 I(D; S) の和が最大になるように MDC を行っている．. max (I(D; W ) + I(D; S)). (9). {D}. そこで，本論文では BoW に基づく手法と同様に HTML 文書からコメントや HTML タ. 表 2 評価データのページ数と分類カテゴリ数 Table 2 The number of pages and categories of evaluation dataset. ページ数. カテゴリ数. 55 47 49 44 51 36 46 35 45 44 43. 4 8 6 5 9 3 4 5 7 4 6. Data01 Data02 Data03 Data04 Data05 Data06 Data07 Data08 Data09 Data10 Data11. Data12 Data13 Data14 Data15 Data16 Data17 Data18 Data19 Data20 Data21. ページ数. カテゴリ数. 43 51 40 74 93 47 99 68 54 56. 5 8 3 3 9 4 6 3 3 3. グを取り除いた本文を対象として，MDC を行いクラスタの生成を行った．表 3 データの分類例 Table 3 An example of categories.. 4.1 評価データ評価用のデータは，実際の検索においてユーザが求める分類を正解データとすることを目的として，人手による正解データの作成を行った．正解データの作成は，19 名の大学生に. 検索クエリ. 分類カテゴリに付けられたラベル. Data07. 最近，人気，映画. Data21. ロボット，学習，制御. · · · · · · ·. 次の手順により作成してもらった．初めに，検索エンジン goo（http://www.goo.ne.jp/）を用いて検索を行った．このときの検索要求は実験者が用意したものではなく自由に決めさせた．その検索結果の中から PDF ファイルなどを除く HTML 文書形式のページのみを 50 ページから 100 ページほど実際に. 映画関連のニュースサイト映画の内容，人物などの紹介映画製品 DVD などの紹介ブログなどの個人の意見，感想学校機関系書籍関係解説系. 見た後，実験者から「見た目やスタイルが似ているページに分類してください」と教示を行ったうえで，被験者は見たページを自由なカテゴリに排他的に分類し，各分類カテゴリにまれているドキュメント数による重み付けを行いその総和をクラスタ群どうしの F 値とし，. ラベル付けをした．こうして得られた評価データの各ページ数と被験者が分類したカテゴリ数を表 2 に示す．. この値によりクラスタ群の近さを評価している．しかし，この手法ではシステムが出力した. ページ数が異なるのは検索結果の中に HTML 文書形式のページ数が異なるためである．な. 複数のクラスタに対して正解データから同一のクラスタが対応付けられる可能性があり，た. お，2 名に 2 セット作成してもらったため，全部で 21 セットとなっている．また，実際の. とえば正解データのクラスタ内に要素数がとても大きなクラスタが存在する場合などにク. 分類カテゴリの例を表 3 に示す．. ラスタ群の近さを正しく評価できない．そこで本論文では，システムが出力したクラスタと. 4.2 評価基準. 正解データのクラスタを 1 対 1 に対応付けるよう修正した次の指標を用いて比較を行った．. 評価用システムが出力するクラスタ群と正解データのクラスタ群がどの程度近いかの指標として，再現率と適合率からなる F 値を用いて評価を行う．. Larsen ら13) や Zhao ら23) もクラスタ群どうしの評価として F 値を用いている．これら. まず，各クラスタ対の F 値を次のようにして求める．正解クラスタ群を L = {L1 , · · · , Lc }，システムが出力したクラスタ群を S = {S1 , · · · , Sc } とする．ここで，システムが出力するクラスタ数は正解クラスタ数 c と同数と設定しクラスタリングを行う．全 Web ページの数. は，まずシステムが出力した各クラスタに対して正解データのクラスタの中から最も F 値. を N ，正解クラスタ Lr に含まれるページ数を lr ，クラスタ Si に含まれるページ数を si と. が高いクラスタとの対応付けを行い，その F 値に対してシステムが出力したクラスタに含. し，Lr と Si の両方に含まれるページ数を nri とする．このとき，任意のクラスタ Lr と Si. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). c 2008 Information Processing Society of Japan .

(8) 2917. HTML タグを用いた Web ページのクラスタリング手法. との F 値 F (Lr , Si ) は，再現率 R(Lr , Si ) と適合率 P (Lr , Si ) より次のように求める．. 2 ∗ R(Lr , Si ) ∗ P (Lr , Si ) R(Lr , Si ) + P (Lr , Si ) nri R(Lr , Si ) = lr nri P (Lr , Si ) = si. F (Lr , Si ) =. (10) (11) (12). 表 4 から，2 種類の重み付けの方法については，属性値のカウント方法を「有無」とし，. IDF 値の考慮の有無を「IDF なし」とした場合が最も良い結果となった．単語の出現頻度情報を用いる一般的な文書クラスタリングにおいては tf-idf による重み付けが良いとされているが，HTML タグを用いた Web ページのタイプに基づくクラスタリングではまったく異なる結果となった．. 次に，正解クラスタ群 L とシステムが出力したクラスタ群 S を 2 つの頂点集合 VL ，VS とし，それぞれの頂点をすべて結んだ完全 2 部グラフ Kc,c を作成する．. VL = {vL1 , vL2 , . . . , vLc }. および分割数について 1 から 5 まで変化させた場合のすべての組合せでの平均を示している．. この理由として，次の 2 点が考えられる．1 つは，HTML タグはその種類が限定されており頻繁に用いられるタグとそうでないタグがはっきり分かれることや，タグの Web ページ. (13). の見た目への影響（重要度）の大きさと出現頻度の関係が単語などによる場合と大きく異な. VS = {vS1 , vS2 , . . . , vSc }. (14). ることが考えられる．たとえば <A> タグや <IMG> タグなどは影響が大きくかつ出現頻. E = {(vLr , vSi )|vLr ∈ VL , vSi ∈ VS }. (15). 度も多いが，<FORM> タグは影響が大きいが出現頻度は多くない．もう 1 つは，HTML. このとき，頂点集合 VL , VS の各頂点 vLr ，vSi は，それぞれ正解クラスタ群 L のクラスタ Lr ，. タグにはすでに廃止されているものや廃止予定のもの（たとえば <BLINK> など）があり，. システムが出力したクラスタ群 S のクラスタ Si に対応させる．また，各辺 e = (vLr , vSi ). このようなタグが使われている場合に IDF 値を考慮することが悪影響を与えることが考え. の重みとして，クラスタ Lr と Si との F 値 F (Lr , Si ) を全 Web ページ数 N に対する正解. られる．. クラスタ Lr の文書数 lr の割合で重み付けした値を与える．. (辺 e = (vLr , vSi ) の重み) =. lr F (Lr , Si ) N. 本論文の以下では，属性値の求め方として，属性値のカウント方法は「有無」とし，IDF. (16). こうして得られた完全 2 部グラフ Kc,c の重み付き最大マッチング問題を解くことで，F 値の総和が最も大きくなる組合せを決定し，その F 値の総和をクラスタ群対の F 値とした．. 4.3 評価結果. 値の考慮の有無を「IDF なし」とした場合についての結果について述べていく．. 4.3.2 n-gram による結果次に，属性の求め方について，まず n-gram を n = 1 から n = 5 まで変化させた場合の結果を表 5 に示す．F 値は，分割数について 1 から 5 まで変化させた場合の全データでの平均 F 値を示している．. 本論文ではまず初めに，3.1.1 項で述べた HTML タグの頻度に基づく特徴ベクトルの構. 表 5 から，n-gram については 2-gram が最良の結果となった．まず，2-gram が 1-gram. 成方法について，2 つの属性決定の要素と 2 種類の重み付けの方法について，最良のパラ. よりも良い結果となった1 ことから，HTML タグの組合せを考慮した場合のほうが考慮し. メータ値を求めた．次に，3.1.2 項で述べた HTML タグの木構造に基づく特徴ベクトルの構成方法と，最良なパラメータでの HTML タグの頻度に基づく特徴ベクトルの構成方法の比較を行い，また先に述べた既存手法との比較を行った．. HTML タグの頻度に基づく特徴ベクトルの構成方法での各パラメータの値は，属性値の. 表 4 2 種類の重み付けの方法の違いによる F 値 Table 4 F-scores for the four combinations of methods for local weight and global weight. 属性値のカウント方法頻度有無 . カウント方法は「頻度」と「有無」について，IDF の考慮は「IDF あり」と「IDF なし」について，n-gram および分割数は 1 から 5 まで変化させた場合について評価を行った．. 4.3.1 属性値の求め方の結果属性値の求め方に対する 2 種類の重み付けの方法，属性値のカウント方法（local weight）と IDF 値の考慮の有無（global weight）についての評価結果を表 4 に示す．F 値は n-gram. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). IDF 値の考慮の有無. IDF あり IDF なし. 0.444 0.444. 0.445 0.450. 1 なお，n-gram および分割数の全 25 通りの組合せについて比較を行った場合でも n-gram が 2-gram かつ分割数が 3 の場合が最も良い結果となった．. c 2008 Information Processing Society of Japan .

(9) 2918. HTML タグを用いた Web ページのクラスタリング手法表 5 n-gram による F 値 Table 5 F-scores for the n-gram of tags.. n-gram 1-gram 2-gram 3-gram 4-gram 5-gram. 平均 F 値. m m m m m. = = = = =. 1 2 3 4 5. 平均 F 値. 0.460 0.462 0.457 0.438 0.433. 表 6 分割数 m による F 値（n = 2 の場合） Table 6 F-scores for the division of a Web page m (n = 2). 分割数. 表 7 提案手法と既存手法との比較 Table 7 Comparison of the proposed methods with the existing methods.. 平均 F 値. 0.457 0.460 0.477 0.454 0.464. タグ木タグ頻度 MDC BoW. 0.478 0.477 0.459 0.451. 果となった．このことから，Web ページの形式・タイプに着目した文書クラスタリングを行うには，単語の分布に基づく手法よりも HTML タグに基づく手法が有用であることがいえる．たとえば，ニュース系サイトかブログ系サイトかを分類するのにそれぞれのサイトに特徴的な単語（たとえば「政治」や「経済」など）によっても分類できるが，このような単語情報よりも HTML タグの情報のほうがより Web ページの形式・タイプに分類できるといえる．また，Bekkerman ら3) の提案するクラスタリング手法（MDC）よりも良い結果となった．このことから，単語の出現頻度や品詞の出現頻度の情報を用いるよりも HTML. ない場合よりも Web ページの形式をとらえることができるといえる．また，4-gram 以上. タグの情報を用いることが，Web ページの形式・タイプに着目したクラスタリングにおい. の場合には明らかに結果が悪くなることから，組合せを考慮したほうが良いものの，せいぜ. て有用であるといえる．. い隣り合う 2 つまたは 3 つまでを考慮すべきであるといえる．本論文の以下では，n-gram を 2 とした場合の結果について述べていく．. またここでは，提案する両手法間での計算時間について考察を行った．2 つの手法間での計算時間の違いは 3.1 節で述べた特徴ベクトルの構築の部分にあたる．どちらの手法も計. 4.3.3 分割数による結果. 算量ではタグの述べ総数を n としたときに O(n) であるが，タグ木に基づく手法はその木. 次に，分割数 m を m = 1 から m = 5 まで変化させた場合の結果を表 6 に示す．F 値は，. 構造を解析するために若干ステップ数が必要となるため時間がかかる．実測値においては，. 全データでの平均 F 値を示している．. タグ頻度に基づく手法はおおむね 2 秒から 10 秒ほどかかるのに対して，タグ木に基づく手. 分割数が 3 の場合が最も良い結果となったことから，HTML タグの出現位置をページ分. 法はおおむね 7 秒から 40 秒ほどかかっていた．また，タグ頻度に基づく手法に比べてタグ. 割により考慮した場合のほうが考慮しないよりも Web ページの形式をとらえることができ. 木に基づく手法が平均で 3.8 倍計算時間を要した．よって，計算時間について考慮した場合. るといえる．. はタグ頻度に基づく手法のほうがタグ木に基づく手法よりも優れているといえる．. 本論文の以下では，分割数を 3 とした場合について述べていく．. 4.3.4 各手法間での評価結果の比較. 5. 考. 察. 次に，これまでの結果で求められた最良のパラメータ値を用いた HTML タグの頻度に基. 4.3.4 項で Web ページの形式・タイプによる分類では提案手法が既存手法よりも分類精. づく特徴ベクトルの構成方法（タグ頻度）と HTML タグの木構造に基づく特徴ベクトルの. 度が良いことを示したが，ここでは，評価データの分類カテゴリを詳細に分析し，どのよう. 構成方法（タグ木）とを比較した結果を表 7 に示す．F 値は全データでの平均 F 値を示し. な分類カテゴリに対して提案手法が有効であるかを検討することで，提案手法の適用範囲な. ている．. らびに限界について考察を行った．. まず初めに，提案する両手法において，単語の頻度に基づく手法（BoW）よりも良い結. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). また，本論文の背景としてタイプに基づく分類を行うことで検索支援を行うことを目的と. c 2008 Information Processing Society of Japan .

(10) 2919. HTML タグを用いた Web ページのクラスタリング手法表 8 評価データの分類カテゴリ別による手法間の比較 Table 8 Comparison of the proposed methods with the existing methods focused on difference of categories between each evaluation data.. 分類の視点ニュースサイト，blog オフィシャルサイト，個人のサイト画像の有無やリンク情報広告の有無文章の形式内容の形式. Data 01, 02, 02, 08, 03, 05, 05, 11 08, 09, 08, 10,. タグ木. 03, 04, 06, 07, 09, 11, 12, 14, 15, 16 10, 12, 13, 18, 20, 21 09, 11, 17, 19 12 16. 0.500 0.474 0.479 0.448 0.501 0.441. 平均 F 値タグ頻度 MDC. 0.498 0.464 0.512 0.497 0.513 0.422. 0.451 0.474 0.403 0.434 0.529 0.587. BoW 0.453 0.455 0.456 0.418 0.484 0.465. しているが，そのときにクラスタリングによる分類結果をどのようにしてユーザに提示する. なり，タグ木に基づく手法は最も向いているといえるが，タグ頻度に基づく手法はあまり向. かが有用性に関わってくる．そこで，タイプに基づく分類結果をどのようにユーザに提示す. かないといえる．この 2 つの分類視点は，既存研究でもたびたび提案されている分類カテゴリであり，Web ページのジャンルによる分類に相当すると考えられる．このような分類の. るかの指針について述べる．. 5.1 分類の視点の違いによる各手法間での評価結果の比較. 場合には，タグ木に基づく手法が最も有効であるといえる．. ここでは，個々の評価データで得られた分類カテゴリから，実験者が各カテゴリのラベル. 次に，3 番目に分類カテゴリとして多かった「テキストのみの解説 or 画像つきで解説 or. とそのカテゴリに含まれている Web ページを見て，複数のデータセットに共通して出現し. リンク付きで解説」のような画像の有無やリンク情報に注目した分類カテゴリについて，結. た 6 つの分類視点を抽出し，提案手法の適用範囲と限界について考察を行った．表 8 に，抽. 果を表 8 の「画像の有無やリンク情報」に示す．ここではタグ頻度に基づく手法が最も良い. 出した 6 つの分類視点と，その分類視点を持つ評価データでの平均 F 値を示す．なお，評. 結果となった．また，「画像の有無」とは別に，「広告がある/ない」といった分類カテゴリが. 価データの分類カテゴリは被験者が自由に決めたものであるので複数の視点を持つ場合も. 2 つのデータセットで見られ，表 8 の「広告の有無」に示すように，この場合もタグ頻度に. あるが，ここでは該当する分類視点を持つデータをすべて含めることとした．まず初めに，最も多くの評価データに現れた「ニュースサイト」と「blog」を分類カテゴリに持つ場合について，結果を表 8 の「ニュースサイト，blog」に示す．表 8 に示したよ. 基づく手法が最も良い結果となった．この 2 つの分類視点は，主に HTML タグの <A> タグや <IMG> タグから判断できる分類である．このような特徴的なタグから判断可能な分類視点においては，タグ頻度に基づく手法が最も有効であるといえる．. うに，評価データ 21 セット中 12 セットと 5 割以上このカテゴリが出現していた．この分. 一方で，提案手法の分類精度が比較手法よりも劣る分類視点もあった．その 1 つに，「リス. 類視点においては，提案手法が既存手法よりも良い結果となり，提案手法はこのような分類. トのような短文形式」「データリスト」といったテキストの書き方による分類があった．こ. に向いているといえ，2 つの提案手法間では，ほとんど差がなくどちらも向いているといえ. の結果を表 8 の「文章の形式」に示しているが，MDC による手法が最も良い結果となり，. る．次に，2 番目に多く現れた「オフィシャルサイト」か「個人のサイト」を分類カテゴリ. 提案手法はこのような分類には向かないといえる．この理由として，HTML タグでリスト. に持つ場合について，結果を表 8 の「オフィシャルサイト，個人のサイト」に示す．ここで. 形式に書くにはリストを表す <LI> タグ以外にも <BR> タグや <TABLE> タグなどと. いう「オフィシャルサイト」とは，メーカなどの企業が作成している Web ページや大学な. 様々なタグの表記方法があることが考えられ，このような分類は HTML タグの情報のみで. どの公共機関が作成している Web ページなどを意味している．また「個人のサイト」とは，. は分類が難しいといえる．また，「意見や感想が書かれている」や「個人体験記」といった. 一個人が作成しているホームページなどを意味し，「blog」は「個人のサイト」としては含め. Web ページの「内容の形式」で分類されているカテゴリがいくつか見られた．このような. ない．表 8 に示したように，評価データ 21 セット中 8 セットとこのカテゴリも多く出現し. 分類カテゴリを持つデータで見ると，結果を表 8 の「内容の形式」に示したように，MDC. ていた．この分類視点においては，タグ木に基づく手法と MDC による手法が良い結果と. による手法が最も良い結果となり，当然のことながら提案手法はこのような分類には向かな. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). c 2008 Information Processing Society of Japan .

(11) 2920. HTML タグを用いた Web ページのクラスタリング手法. いといえる．これらの結果から，Web ページのテキストのスタイルによる分類や「意見や. リング手法と組み合わせることにより提案手法では適用できない分類への対応などを行い，. 感想」のような内容の形式には提案手法は向かないといえる．. さらに良い手法の開発を行うことがあげられる．評価手法の課題としては，人手により作成. 5.2 タイプに基づく分類結果のユーザへの見せ方. した正解データを用いたために規模が小さかったので，大規模な正解データによる評価があ. ここでは，提案手法により求められた分類結果をどのようにユーザに提示すればよいかに. げられる．そして，本手法を実装した検索支援システムを構築すること，また検索支援シス. ついて検討を行った．. テムとしての有用性について評価を行うことを考えている．. 関連研究であげた内容に基づくクラスタリング手法による検索支援手法では，一般的にクラスタの代表となる語をユーザに提示する手法が用いられ，これによりユーザは各クラスタの内容を推測することが可能である．これに対してタイプに基づく分類では，1 つの提案として各クラスタの代表となる Web ページのキャプチャ画像をユーザに提示する方法が考えられる．Web ページのキャプチャ画像をユーザに提示することでそのクラスタがどのような Web ページの種類・形式かという情報を一目で分かりやすく提示することができ，各クラスタのタイプを推測する手助けになると考える．またもう 1 つの提案として，HTML タグの情報のうちユーザが直感的に分かりやすり指標，たとえば <A> タグをもとにリンクの数，<IMG> タグをもとにイメージの数，<FORM> タグをもとに入力フォームの有無など，といった情報を数値化してユーザに提示することにより各クラスタのタイプを推測する手助けになると考える．. 6. おわりに本論文では，Web ページのタイプに基づくクラスタリング手法として，HTML タグの木構造の情報を用いた手法と HTML タグの頻度の情報を用いた手法を提案し，その評価を行った．既存手法との比較を行った結果から，Web ページのタイプに基づくクラスタリングでは単語の出現頻度や品詞の出現頻度を用いるよりも HTML タグの情報を用いるほうがクラスタリングの精度が良いことを示した．また，2 つの提案手法の比較を行ったところ，全体ではほぼ同等のクラスタリング精度であるが，Web ページの分類傾向により 2 つの手法を使い分けることでクラスタリング精度が向上することを示した．また，処理時間を考慮した場合，タグの頻度に基づく手法のほうがタグの木構造に基づく手法よりも効率的であることを示した．今後の課題として，評価実験で得られた結果に対して統計的検定を行ったがいずれの結果も 5%水準での有意差を得ることができなかったので，よりクラスタリング精度を向上させるために，Web ページのタイプを判断するのに有用な HTML タグと有用でない HTML タグを考慮することによる手法の改善や，提案手法と Web ページの内容に基づくクラスタ. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). 参考. 文献. 1) 相澤彰子：低頻度語の利用によるテキスト分類性能の改善と評価，情報処理学会論文誌，Vol.44, No.7, pp.1720–1730 (2003). 2) 馬場康夫，笹田鉄郎，新里圭司，黒橋禎夫：構造的言語処理による大規模ウェブ情報のクラスタリング，言語処理学会第 13 回年次大会発表論文集（NLP2007），pp.562–565 (2007). 3) Bekkerman, R., Eguchi, K. and Allan, J.: Unsupervised Non-topical Classification of Documents, UMass CIIR Technical Report, No.IR-472 (2006). 4) Bekkerman, R., El-Yaniv, R. and McCallum, A.: Multi-Way Distributional Clustering via Pairwise Interactions, Proc. 22nd International Conference on Machine Learning, pp.41–48 (2005). 5) 江口浩二，伊藤秀隆，隈元昭，金田彌吉：漸次的に拡張されたクエリを用いた適応的，Vol.J82-D-I, No.1, pp.140–149 文書クラスタリング法，電子情報通信学会論文誌（D-I） (1999). 6) Finn, A. and Kushmerick, N.: Learning to Classify Documents According to Genre, IJCAI-03 Workshop on Computational Approaches to Style Analysis and Synthesis, pp.35–45 (2003). 7) Finn, A., Kushmerick, N. and Smyth, B.: Genre Classification and Domain Transfer for information filtering, Proc. 24th BCS-IRSG European Colloquium on IR Research, pp.353–362 (2002). 8) 藤野昭典，上田修功，斉藤和巳：最大エントロピー原理に基づく付加情報の効果的な利用によるテキスト分類，情報処理学会論文誌，Vol.47, No.10, pp.2929–2937 (2006). 9) K¨ aki, M.: Findex: Search Result Categories Help Users when Document Ranking Fails, Proc. SIGCHI Conference on Human Factors in Computing Systems, pp.131– 140 (2005). 10) 神嶌敏弘：データマイニング分野のクラスタリング手法（1），人工知能学会誌，Vol.18, No.1, pp.59–65 (2003). 11) 金子大輔，高山毅，池田哲夫，長内亘：Web 文書のページタイプを用いた適応約分類と試作システムの評価（＜特集＞ Web インテリジェンスとインタラクション），知能と情報：日本知能情報ファジィ学会誌：journal of Japan Society for Fuzzy Theory and Intelligent Informatics，Vol.18, No.2, pp.319–336 (2006).. c 2008 Information Processing Society of Japan .

(12) 2921. HTML タグを用いた Web ページのクラスタリング手法. 12) 久野高志，安形輝，石田栄美，上田修一：Web ページのタイプ判別法，2000 年度日本図書館情報学会春季研究大会発表要綱，pp.55–58 (2000). 13) Larsen, B. and Aone, C.: Fast and Effective Text Mining Using Linear-time Document Clustering, Proc. 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.16–22 (1999). 14) Lee, K.-J.: Document Genre Classification for User Interface of Web Search Engine (Natural Language Processing), IEICE Trans. Information and Systems, Vol.E87D, No.7, pp.1982–1986 (2004). 15) Lim, C.S., Lee, K.J. and Kim, G.C.: Multiple Sets of Features for Automatic Genre Classification of Web Documents, Information Processing and Management: an International Journal, Vol.41, No.5, pp.1263–1276 (2005). 16) Lingpeng, Y., Donghong, J., Li, T. and Zhengyu, N.: Chinese Information Retrieval Based on Terms and Relevant Terms, ACM Trans. Asian Language Information Processing (TALIP 2005 ), Vol.4, No.3, pp.357–374 (2005). 17) Meyer zu Eissen, S. and Stein, B.: Genre Classification of Web Pages: User Study and Feasibility Analysis, Vol.3238, pp.256–269 (2005). 18) Rehm, G.: Towards Automatic Web Genre Identification, Proc. 35th Annual Hawaii International Conference on System Sciences (HICSS 2002 ), Vol.4, p.101 (2002). 19) Toda, H. and Kataoka, R.: A Search Result Clustering Method using Informatively Named Entities, Proc. 7th Annual ACM International Workshop on Web Information and Data Management, pp.81–86 (2005). 20) 上嶋宏，三浦孝夫，塩谷勇：同義語，多義語の考慮による文書分類の精度向上，電子情報通信学会論文誌（D-I），Vol.J87-D-I, No.2, pp.137–144 (2004). 21) Valiente, G.: Algorithms on Trees and Graphs, Springer-Verlag (2002). 22) Yang, R., Kalnis, P. and Tung, A.K.H.: Similarity Evaluation on Tree-structured Data, Proc. 2005 ACM SIGMOD International Conference on Management of. Data, pp.754–765 (2005). 23) Zhao, Y. and Karypis, G.: Evaluation of Hierarchical Clustering Algorithms for Document Datasets, Proc. 11th International Conference on Information and Knowledge Management, pp.515–524 (2002). (平成 19 年 11 月 28 日受付) (平成 20 年 5 月 8 日採録) 折原. 大（学生会員）. 1979 年生．2002 年電気通信大学電気通信学部電子情報学科卒業．2004 年同大学大学院電気通信学研究科電子情報学専攻博士前期課程修了．同年. NTT アドバンステクノロジ株式会社入社．2005 年 3 月同社を退職し，同年 4 月電気通信大学大学院電気通信学研究科システム工学専攻博士後期課程に入学，現在に至る．情報検索，自然言語処理，ウェブ工学の研究に従事．. 内海. 彰（正会員）. 1965 年生．1993 年東京大学大学院工学系研究科情報工学専攻博士課程修了．博士（工学）．東京工業大学大学院総合理工学研究科助手，講師を経て，2000 年から電気通信大学電気通信学部システム工学科准教授．言語の認知科学や言語情報処理の研究に従事．最近の個人的な関心は認知修辞学，意味空間，ウェブ工学．人工知能学会，日本認知科学会，言語処理学会，Cognitive Science Society 等各会員．. 情報処理学会論文誌. Vol. 49. No. 8. 2910–2921 (Aug. 2008). c 2008 Information Processing Society of Japan .

(13)