(Microsoft PowerPoint - \203|\203X\203^\201[\224\255\225\\\227p\216\221\227\ ppt)

Size: px

Start display at page:

Download "(Microsoft PowerPoint - \203|\203X\203^\201[\224\255\225\\\227p\216\221\227\ ppt)"

やすはるうえや
5 years ago
Views:

Web ページタイプによるクラスタリングを用いた検索支援システム折原大内海彰電気通信大学システム工学専攻はじめに背景

などジャンルによる分類画像や動画の有無による分類企業大学などのオフィシャルサイトかどうかによる分類 008/09/ NLP 若手の会第

レシピ ( 画像つき ) レシピ ( 文字のみ ) 分類例例 : 年金問題についてのニュース記事 / 個人的な意見が知りたい!

ページタイプ ) による分類用意されたカテゴリへの分類 (classification) ではなく,

- 分類手法トピックによる分類予め用意したカテゴリへの静的な分類 (classification) 同義語,

構造的言語処理による大規模ウェブ情報のクラスタリング [ 馬場,07] A Search Result Clustering Method

(classification) Learning to Classify Documents According to Genre

1 Web ページタイプによるクラスタリングを用いた検索支援システム折原大内海彰電気通信大学システム工学専攻はじめに背景文書クラスタリングを用いた検索支援システム Clusty( KartOO( Carrot( これらはすべてトピックによる分類を行っている動機ユーザが望む分類はトピックだけではないニュースサイト /blog などジャンルによる分類画像や動画の有無による分類企業大学などのオフィシャルサイトかどうかによる分類 008/09/ NLP 若手の会第回シンポジウム分類例例 : カルボナーラのレシピを写真つきで欲しい! レシピ ( 画像つき ) レシピ ( 文字のみ ) 分類例例 : 年金問題についてのニュース記事 / 個人的な意見が知りたい! ニュースサイト blog サイト本研究の目的本研究の目的 HTML タグを用いることで, トピックによる分類ではなく,Web ページの形式 ( ページタイプ ) による分類用意されたカテゴリへの分類 (classification) ではなく, クラスタリング手法を用い検索結果に応じた動的な分類 (clustering) HTML タグの出現頻度情報を元にした素性の提案関連研究との比較 - 分類手法トピックによる分類予め用意したカテゴリへの静的な分類 (classification) 同義語, 多義語の考慮による文書分類の精度向上 [ 上嶋,0] クラスタリングによる動的な分類 (clustering) 構造的言語処理による大規模ウェブ情報のクラスタリング [ 馬場,07] A Search Result Clustering Method using Informatively Named Entities [Toda,0] ページタイプによる分類予め用意したカテゴリへの静的な分類 (classification) Learning to Classify Documents According to Genre [Finn,0] Multiple Sets of Features for Automatic Genre Classification of Web Documents [Lim,0] クラスタリングによる動的な分類 (clustering) Unsupervised Non-topical Classification of Documents [Bekkerman,0](note: 新聞記事を対象としている ) 本研究では Web ページタイプによるクラスタリング手法を提案

2 関連研究との比較 - 素性関連研究で扱われている素性語に基づく情報単語の出現頻度 (Bag-of-Wards, BoW) 品詞の出現頻度 (Part-of-Speech, PoS) 各カテゴリに固有のキーワード文書に基づく情報疑問文, 命令文などの文型や, 名詞句や動名詞句などの句の出現頻度文や段落の平均の長さなどの統計的情報 (Text Statistics) Web 特有の情報 HTML タグの出現頻度タイトルに関する情報 URL に関する情報 ( 深さ, ドキュメントタイプ (html,pdf など ), ドメインなど ) 本研究では HTML タグの出現頻度を元にした関連研究とは異なる新しい素性を提案ページタイプによるクラスタリングを用いた検索支援システム. Live Search より検索結果上位 n 件を取得. 各ページの HTML ソースを取得. 次のつの Step でクラスタリングを行う Step- 特徴ベクトルの構成 Step-F HTML タグの頻度に基づく特徴ベクトル Setp-T HTML タグの木構造に基づく特徴ベクトル Step- 類似度の計算 Step- クラスタの生成. 各クラスタの重心に最も近いページをクラスタの代表とし, キャプチャ画像をユーザに提示 7 Step-F 頻度に基づく特徴ベクトル各 Web ページを HTML タグの頻度に基づく特徴ベクトルで表現. HTML タグを抽出. 分割数と n-gram による特徴ベクトルの属性を決定. 属性値のカウント方法と IDF 値の考慮の有無による属性値を計算. 各特徴ベクトルの長さをに正規化 Step-F. 属性の決定分割数タグがどの位置に出現しているかを考慮する要素抽出されたタグを分割数 m で等分し各範囲でつの属性とみなす n-gram 連続するタグの組み合わせを考慮する要素抽出されたタグを連続する n 個の組み合わせでつの属性とみなす 8 9 Step-F. 属性の決定 ( 分割数 ) Step-F. 属性の決定 (n-gram) <H> <H> <H> <H> A B つに分割分割数がの場合 A B <H> 0 <H> 0 0 <H> <H> <H> <H> <H> n-gram がの場合 <H> <H> <H> 0

3 Step-F. 属性の決定 Step-F. 属性値の計算 <H> <H> <H> <H> -gram <H> <H> <H> <H> <H> A B 分割数が, かつ, n-gram がの場合 <H> <H> <H> A B 0 0 属性値のカウント方法一般的な出現回数をカウントする頻度その属性が出現したかどうかの値をとる有無 IDF 値の考慮の有無 IDF 値の考慮あり IDF 値の考慮なし Step-F. 属性値の計算 ( 頻度有無 ) Step-T 木構造に基づく特徴ベクトル <H> <H> <H> <H> 頻度と有無頻度有無 <H> <H> <H> 0 0 各 Web ページを HTML タグの木構造に基づく特徴ベクトルで表現. HTML タグの木構造を分木に置き換える. 分木に対応する Binary Branch を定義する. Binary Branch を用いて Binary Branch Vector を求めこれを特徴ベクトルとする. 各特徴ベクトルの長さをに正規化する Step-T. 分木へ置き換え Step-T. 分木へ置き換え HTML 文書から HTML タグの木構造を取り出し次の方法で分木へ置き換える. すべての兄弟のノードをリンクで結ぶ. 各ノードの最初の子ノードとのリンクを除く全てのリンクを削除する変換後に該当する子ノードがない場合はノードを付加する 7

4 Step-T. 分木へ置き換え Step-T. 分木へ置き換え. 全ての兄弟ノードをリンクで結ぶ. 最初の子とのリンクを除く全てのリンクを削除 8 9 Step-T. 分木へ置き換え子ノードがない場合はノードを付加 Step-T. Binary Branch を定義 Step-. で作成された分木のうち階層分を取り出したものを Binary Branch とする Binary Branch 0 Step-T. Binary Branch Vector Step-. で求めた Binary Branch を要素とし各要素の値は頻度とする Binary Branch Vector を求めるこれを特徴ベクトルをする Binary Branch 特徴ベクトル = (,,,, ) Step- 類似度の計算 Step- クラスタの生成類似度多次元ユークリッド空間の距離を利用クラスタリング手法クラスタリングアルゴリズム : 階層的手法クラスタ間の類似度の計算手法 :Ward 法停止条件 : ページ総数の割を超えるクラスタが作成される直前

検索支援システム出力例 C# により作成評価実験提案する手法を実装し, 有用性を検証分類精度による評価データアンケートにより作成した分類正解データ ( 件 ) 比較手法単語の分布に基づく手法 (BoW) Bekkerman らの手法 [Bekkerman,0] 検索支援システムとしての評価データ名のユーザに試用してもらい, 回答となるページを取得するまでの早さ, 多さを比較

5 検索支援システム出力例 C# により作成評価実験提案する手法を実装し, 有用性を検証分類精度による評価データアンケートにより作成した分類正解データ ( 件 ) 比較手法単語の分布に基づく手法 (BoW) Bekkerman らの手法 [Bekkerman,0] 検索支援システムとしての評価データ名のユーザに試用してもらい, 回答となるページを取得するまでの早さ, 多さを比較比較手法 Live Search による検索と比較評価データ - 分類精度 (/) 評価データ - 分類精度 (/) 以下の手順で正解データを作成. 各人が検索エンジンを用いて自由に検索. 得られた検索結果の上位 00 件を全て閲覧 PDF, XML などは対象外とする分類が難しいページはその他に分類してもらい評価データからは対象外とする. 見た目やスタイルが似ているものどうしに分類してくださいと教示し. で閲覧したページを自由に分類 Data0 Data0 Data0 Data0 Data0 Data0 Data07 Data08 Data09 Data0 Data 表 : アンケートにより作成した評価データのページ数およびグループ数ページ数 7 9 グループ数 Data Data Data Data Data Data7 Data8 Data9 Data0 Data ページ数グループ数評価データ - 分類精度 (/) 正解データ例 Date07 検索クエリ : 最近, 人気, 映画ユーザが付けた分類グループ名映画関連のニュースサイト映画の内容, 人物などの紹介映画製品 DVD などの紹介ブログなどの個人の意見, 感想 Data 検索クエリ : ロボット, 学習, 制御ユーザが付けた分類グループ名学校機関系書籍関係解説系評価基準 - 分類精度 F 値の考え方をもとにクラスタ群対の F 値を計算完全部グラフの重みつき最大マッチング問題を解くことでクラスタ群対の F 値とするシステムが出力したクラスタ群 ( 辺の重み )= クラスタ対の F 値ここではシステムが出力するクラスタ数は正解データのグループ数と同数とする S S S Sc 正解データのクラスタ群 L L L Lc 8 9

6 評価結果 - 分類精度 (/) 評価結果 - 分類精度 (/) HTML タグの頻度に基づく特徴ベクトルの構築では, 以下のパラメータが最適分割数 : 比較手法よりも本研究で提案するつの手法において分類精度が向上 n-gram: 表 : 提案手法と既存手法との比較属性値のカウント方法 : 有無 IDF 値の考慮の有無 : なしタグの木構造木構造に基づくづく特徴特徴ベクトル平均 F 値 0.78 表 :n-gram による平均 F 値表 : 分割数による平均 F 値タグの頻度頻度に基づくづく特徴特徴ベクトル ( 最適なパラメータ ) 0.77 表 : 属性値,IDF の考慮の違いによる平均 F 値属性値 n-gram -gram 平均 F 値 0.0 分割数平均 F 値 0.7 Bekkerman らの手法 Bag-of-Words (BoW) 頻度有無 -gram IDF の考慮ありなし gram -gram gram 評価結果検索支援システム今後の課題名のユーザに試用してもらった次のような検索要求において本システムが有用であった料理のレシピを検索した際に, 画像付きで解説されているページが欲しい文書クラスタリング手法を検索した際に, 具体的な内容が書かれているページが欲しい学会のプログラムが書かれているページが分別された今後, 検索要求タスクを設定し本評価を行う検索支援システムとしての問題点を改良検索結果 ( クラスタリング結果 ) 出力までの時間がかかりすぎる 0 件の検索結果をクラスタリングするのに約 0 クラスタリング結果の提示方法クラスタの代表となるページのキャプチャ画像を提示しているがトピックとページタイプを組み合わせたクラスタリング手法の提案

nlp1-12.key

nlp1-12.key 自然言語処理論 I 12. テキスト処理 ( 文字列照合と検索 ) 情報検索 information retrieval (IR) 広義の情報検索情報源からユーザの持つ問題 ( 情報要求 ) を解決できる情報を見つけ出すこと狭義の情報検索文書集合の中からユーザの検索質問に適合する文書を見つけ出すこと適合文書 : 検索質問の答えが書いてある文書テキスト検索 (text retrieval)