構造的類似性を持つ半構造化文書における頻度分析

Presentation on theme: "構造的類似性を持つ半構造化文書における頻度分析"— Presentation transcript:

1 構造的類似性を持つ半構造化文書における頻度分析
山田泰寛* 池田大輔** 廣川佐千男** *九州大学大学院システム情報科学府 **九州大学情報基盤センター

2 発表内容 背景 頻度分布 まとめ 今後の課題 共通パタン特定 自然言語文 共通テンプレートを持つ半構造化文書群
発表内容は以下のようになっています。 まず、背景について述べます。 背景では我々の目標である共通パタンの特定について述べます。 次に、頻度分布についてですが、本論文では共通パタン特定の予備実験として、 自然言語文と共通テンプレートを持つ半構造化文書群を対象として 頻度分析を行なったので、そのグラフをいくつかお見せします。 最後にまとめと今後の課題について述べます。 本研究では、難しいことは行なっておらず、 部分文字列の頻度をカウントし、グラフ化したものをお見せするだけなので、 簡単に理解していただけると思います。

3 背景 共通パタンの特定 文字列処理 パタン言語の学習 ゲノム テキストの圧縮 計算量が高い 最長共通部分文字列 最長共通部分列問題
与えられた例に共通するパタンの探索 ゲノム モチーフ発見 最大反復 テキストの圧縮 頻出するパタンの予測 複数の対象が与えられたときに、これらの多くに共通する性質、 あるいは頻出する部分を見つける問題を解くことは、 非常に一般的であり、様々な分野で研究されています。 例えば、。。。。 この他にも、自然言語処理、囲碁の棋譜からの定石の発見など 様々な分野で研究されています。 しかし、入力が個数が可変であったり、パタンが複雑であったりすると、 計算量が大きくなることが問題として上げられます。 計算量が高い

4 情報抽出(Web マイニング) ラッパー コンテンツ抽出プログラム 共通テンプレートを持つ文書群を対象
共通テンプレートの特定し、コンテンツを抽出するルールを生成 もう一つ共通パタン特定が研究されている分野に、セッションが「Webとデータベース」 ということで、Webマイニングの分野があります。 Webマイニングの研究の一つに、共通テンプレートを持つ文書群を対象とし、 そこからラッパーと呼ばれるコンテンツを抽出プログラムの生成 に関する研究が行なわれています。 （ＨＴＭＬ） 例えば新聞記事を対象として、見出しや本文などのコンテンツ部分を抽出したい場合、 このようあページは共通のテンプレートを用いて作成されていつので 共通テンプレート部分を特定すれば、コンテンツ部分を抽出することができます。 この後もテンプレートという言葉を使うのですが、テンプレートはタグだけでなく、 このような全文書中に共通している記号や文字列も含みます。

5 目的 共通パタン特定の予備実験として頻度分析 共通テンプレートを持つ半構造化文書群 頻度分布の差を用いた共通テンプレートの特定 自然言語文
構造的類似性（共通テンプレート）を持つ半構造化文書群 共通テンプレートを持つ半構造化文書群 テンプレート部分とコンテンツ部分で構成 コンテンツ部分は自然な文字列 頻度分布の差を用いた共通テンプレートの特定 部分文字列の出現頻度だけを使う 計算量が小さい 本研究では、最終的には、入力文字列からの共通パタンの特定が目的なのですが、 予備実験として頻度分析を行ないました。 対象として、自然言語文、具体的には小説と 構造的類似性を持つ半構造化文書群を対象として頻度分析を行ないました。

6 発表内容 背景 共通パタン特定 頻度分布 自然言語文 共通テンプレートを持つ半構造化文書群 まとめと今後の課題

7 テンプレートを持たないテキスト 夏目漱石「こころ」 これより、頻度の大きい部分文字文字列はほとんど存在しないことが分かります。
487KByte V(f) n : 部分文字列の長さ f : 出現頻度 V(f) :出現頻度 f を持つ部分文字列の種類数 入力として、コンテンツ部分の頻度分布を調べるために、自然言語文として 青空文庫から夏目漱石「こころ」を使用し、長さ３０まで頻度をカウントしました。 縦軸が部分文字列の長さ、横軸が出現頻度、 垂直軸が出現頻度 f を持つ部分文字列の種類数です。 ただし頻度が１の部分文字列は省略しています。 これより、頻度の大きい部分文字文字列はほとんど存在しないことが分かります。 また、長さが長くなれば、部分文字列の種類数が減っていることが分かります。 n f

8 テンプレートを持たないテキスト べき分布に従う 両軸を対数化しています。
種類数 V(f) 次に、横軸が出現頻度、縦軸が出現頻度 f を持つ部分文字列の種類数を表し、 両軸を対数化しています。 このグラフより、頻度と種類数がべき分布に従っていることが分かります。 頻度 f

9 テンプレートを持たないテキスト ジップの第２法則 テキスト中の単語の頻度分布、
特に低頻度部分において、頻度がfである単語の種類数V(f)は頻度fとの間に以下の関係が成り立つ log V(f) = - a (log f) + b 種類数 V(f) 頻度 f

10 共通テンプレートを持つテキスト 産経新聞 50ファイル 328KByte V(f) n f

11 テンプレートを持たないテキスト 夏目漱石「こころ」 487KByte V(f) n f n : 部分文字列の長さ f : 出現頻度
V(f) :出現頻度 f を持つ部分文字列の種類数 n f

12 共通テンプレートを持つテキスト 産経新聞 50ファイル 328KByte V(f) n f

13 頻度分布の差 (a) テンプレート部分 (b) コンテンツ部分

14 共通テンプレートを持つテキスト f vs. V(f) 種類数 V(f) 頻度 f

15 テンプレートを持たないテキスト f vs. V(f) 種類数 V(f) 頻度 f

16 共通テンプレートを持つテキスト f vs. V(f) べき分布からの乖離する点の出現 種類数 V(f) 頻度 f
このような点はテンプレート部分の部分文字列の頻度が影響している。 頻度 f

17 頻度分析 グラフ1 グラフ2 グラフ3 部分文字列の長さ n 出現頻度 f 出現頻度 f を持つ部分文字列の種類数 V(f)

18 テンプレートを持たないテキスト 夏目漱石「こころ」 f vs. f * V(f) 頻度 f*V(f) 頻度 f

19 共通テンプレートを持つテキスト 産経新聞 50ファイル ピークが出現 ５０ ファイル数 １００ ファイル数の２倍 頻度 f*V(f)
共通テンプレートを持つテキスト群を入力として与えた場合、 ファイル数のn倍にあたる頻度にピークが表れる傾向がありました。 また、このような頻度を持つ部分文字列はテンプレート上に出現する部分文字列でした。 １００　ファイル数の２倍 頻度 f

20 まとめ なし あり f vs. V(f) べき分布 べき分布からの乖離 f vs. f*V(f) ピークなし ピークあり 共通テンプ レート
　　　レート 頻度分布

21 今後の課題 共通パタンの発見 べき分布からの外れの数値化 他データへの応用 ゲノム

22 参考論文 文字列の頻度分布による共通パタン発見, 池田大輔, 山田泰寛, 廣川佐千男, 第72回情報学基礎研究会, 2003年9月29,30日 テンプレート発見問題の定義 f vs. f * V(f)

23

24 yahooの検索結果 f vs. f * V(f) ４６ 全ファイルに共通 頻度 f*V(f) カテゴリ名 ９１ ９１３ 検索結果 頻度 f

25 ノイズを含む入力 九州大学 トップページから深さ３まで 598ファイル ６２ 頻度 f

26 頻度62の部分文字列を持つページ

27 複数のテンプレート f vs. F(f) １４０ 産経：５０ 朝日：１０４ 読売：１４０ １０４ ４９，５０

28 部分文字列の長さによる頻度の差 (a) 長さ 2 (b) 長さ 5