(57)【要約】    【課題】      不特定のウェブサイトのページから、ある検索語に関する特定の情報をブロック単位で抽出すること。    【解決手段】  本情報抽出装置は、ＨＴＭＬなどで記述された半構造化情報における検索語と検索語に関する特定情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、ウェブページの集合から検索語に関する特定情報の候補をブロック単位で抽出し、抽出された特定情報の候補の中から情報分類技術を用いて特定情報を選択する。  【選択図】      図１
2007047974.tif 000002
【特許請求の範囲】
【請求項１】
指示された検索語に関する情報をウェブページの集合から抽出する情報抽出装置であって、
前記ウェブページの半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出する情報候補抽出手段と、
前記情報候補抽出手段によって抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類する情報分類手段と、
を有する情報抽出装置。
【請求項２】
前記情報候補抽出手段は、
前記各ウェブページの半構造化情報をＤＯＭ木に変換する手段を有し、
前記ＤＯＭ木を前記パターン集合の各パターンとパターンマッチングを行って前記情報候補のノードを特定することにより、情報候補を抽出する、
請求項１記載の情報抽出装置。
【請求項３】
前記情報候補抽出手段は、
前記パターンマッチングの際に、二つのノードが隣接する場合とその間に他ノードが介在する場合との双方を同一の構造的位置関係とする、
請求項２記載の情報抽出装置。
【請求項４】
前記情報候補のうち、前記情報分類手段によって抽出するべき情報と分類された情報を選択する情報選択手段と、
前記情報選択手段によって選択された情報に、
選択された情報に対する情報分類技術による評価値と、半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係における距離と、を合わせた尺度に基づいて優先度を付与し、
前記選択された情報を前記優先度に基づいて表示する情報出力手段と、
をさらに有する請求項１記載の情報抽出装置。
【請求項５】
教師データ集合を構成する各教師データから、半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を特定し、
前記構造的位置関係を表すパターン木から成るパターン集合学習データを作成する、
パターン集合学習データ作成手段と、
前記パターン集合学習データを構成する複数の前記パターン木における頻出のパターンを複数求め、
求めた複数の前記頻出のパターンから成る前記パターン集合を生成する、
抽出パターン生成手段と、
をさらに有する請求項１記載の情報抽出装置。
【請求項６】
教師データ集合を構成する各教師データから、半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を特定し、前記構造的位置関係を表すパターン木を作成し、
作成したそれぞれの前記パターン木を根ノードのタグおよび前記検索語に関する情報を含むノードのタグの両方が共通するパターン木ごとに各々分類したパターン木集合を有するパターン集合学習データを作成する、
パターン集合学習データ作成手段と、
前記パターン集合学習データの前記パターン木集合のそれぞれにおいて飽和パターンを求め、求めたパターンを前記パターン木集合ごとに各々分類した予備パターン集合を生成し、
前記予備パターン集合それぞれから、サポートの最も高いパターンを選び出し、選び出された複数の前記パターンを格納したパターン集合を生成する、
抽出パターン生成手段と、
をさらに有する請求項１記載の情報抽出装置。
【請求項７】
教師データ集合を構成する各教師データから、半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を特定し、
前記構造的位置関係を表すパターン木から成るパターン集合学習データを作成する、
パターン集合学習データ作成手段と、
前記パターン集合学習データを構成する複数の前記パターン木における頻出のパターンを複数求め、
求めた複数の前記頻出のパターンの前記教師データ集合に対する適合度をそれぞれ算出し、
前記教師データ集合に対する適合度が所定の閾値より高いパターンだけで構成される前記パターン集合を生成する、
抽出パターン生成手段と、
をさらに有する請求項１記載の情報抽出装置。
【請求項８】
教師データ集合を構成する各教師データから、半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を特定し、前記構造的位置関係を表すパターン木を作成し、
作成したそれぞれの前記パターン木を根ノードのタグおよび前記検索語に関する情報を含むノードのタグの両方が共通するパターン木ごとに各々分類したパターン木集合を有するパターン集合学習データを作成する、
パターン集合学習データ作成手段と、
前記パターン集合学習データの前記パターン木集合のそれぞれにおいて飽和パターンを求め、得られたパターンを前記パターン木集合ごとに各々分類した予備パターン集合を生成し、
前記予備パターン集合それぞれから、サポートの最も高いパターンを選び出し、選び出された複数の前記パターンを格納したパターン集合を生成し、
前記パターン集合を構成する前記パターンの前記教師データに対する適応度をそれぞれ求め、最も適応度が低い前記パターンの適応度が所定の閾値より低かった場合、前記最も適応度が低いパターンが格納されていた前記予備パターン集合に格納されている前記パターンのうち、次にサポートの高い前記パターンを前記パターン集合の前記最も適応度が低いパターンと置換する、という処理を、前記パターン集合に格納された全ての前記パターンの前記教師データに対する適応度が所定の閾値より高くなるまで繰り返し、
前記教師データ集合に対して適合率が所定の閾値より高いパターンだけで構成されるパターン集合を生成する、
抽出パターン生成手段と、
をさらに有する請求項１記載の情報抽出装置。
【請求項９】
前記抽出パターン生成手段で生成された前記パターンと前記教師データとの間でパターンマッチングを行い、マッチした情報が抽出されるべき情報であったかどうかを学習することによって、前記情報分類器を求める情報分類器学習手段、
をさらに有する請求項５から請求項８のいずれかに記載の情報抽出装置。
【請求項１０】
指示された検索語に関する情報をウェブページの集合から抽出する情報抽出方法であって、
前記ウェブページの半構造化情報における前記検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出する情報候補抽出ステップと、
前記情報候補抽出ステップで抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類する情報分類ステップと、
を有する情報抽出方法。
【請求項１１】
コンピュータに、
ウェブページの半構造化情報における検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出させ、
抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェブページから、ある検索語に関する評判情報などの特定の情報を自動的に抽出する情報抽出装置および情報抽出方法に関する。
【背景技術】
【０００２】
従来、ウェブページから、ある検索語に関する評判情報などの特定の情報を自動的に抽出する技術としては、ＬＲラッパー（非特許文献１）やＴｒｅｅラッパー（非特許文献２）などの方法がある。これらは、ＨＴＭＬで記述されたタグ構造を利用しており、抽出したい情報の周囲に見られる共通構造を取り出し、それを抽出規則とする。特定のウェブサイト内のページからある検索語に関する評判情報を抽出する場合、サイト内でＨＴＭＬの記述フォーマットが決まっており、タグ構造が共通であることが多いため、これらの方法を用いることで検索語と評判情報の組を抽出できる。
【０００３】
また、これとは別の方法として、特許文献１の方法などの自然言語処理を用いた方法がある。この方法では、特定の情報の抽出にタグ構造などのＨＴＭＬ特有の特徴は用いず、ウェブページ中の文章の部分句や意味構造などの言語的特徴を用いる。特許文献１の方法について、ある検索語（例えば、書籍名）に関する評判情報を抽出する場合を例にして説明する。まず、「良い」「最高だ」「面白い」などの評価表現を格納した評価表現辞書を作成しておく。ユーザが検索語と文章を特許文献１の装置に入力すると、この装置は、検索語、および評価表現辞書に格納された表現が、文章内に存在するかどうかを検索する。そして、評価表現および検索語が共に存在した場合、これら両方を含む文を抽出することで、ある検索語に関する評判情報を抽出する。
【特許文献１】特開２００２−１７５３３０号公報
【非特許文献１】N. Kushmerick, "Wrapper Induction: Efficiency and expressiveness", Artificial Intelligence, 2000, 118, p.15-68.
【非特許文献２】村上義継、外４名,「ＨＴＭＬからのテキストの自動切り出しアルゴリズムと実装」，情報処理学会論文誌：数理モデル化と応用，2001，vol.42，no.SIG14-006，p.39-49.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、ＬＲラッパーやＴｒｅｅラッパーなどの抽出したい情報の周囲の共通構造を取り出す方法では、基本的に教師データと同一サイトのページにしか適用できず、ＨＴＭＬなどの記述フォーマットがそれぞれ異なる不特定サイトのページには拡張できないという問題がある。これらの手法は、抽出すべき情報の周囲の構造に共通のパターンを求めるが、不特定のサイトのページには共通のパターンが存在しないためである。また、自然言語処理を用いた特許文献１の方法では、抽出単位がブロックではなく文になってしまう、という問題がある。この手法は、半構造化情報の構造を認識しておらず、情報をブロック単位に分けることができないためである。
【０００５】
本発明はかかる点に鑑みてなされたものであり、不特定のウェブサイトのページから、ある検索語に関する特定の情報をブロック単位で抽出することができる、情報抽出装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の情報抽出装置は、ウェブページの半構造化情報における検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出する情報候補抽出手段と、前記情報候補抽出手段によって抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類する情報分類手段と、を有する構成を採る。
【０００７】
本発明の情報抽出方法は、ウェブページの半構造化情報における検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出する情報候補抽出ステップと、前記情報候補抽出ステップで抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類する情報分類ステップと、を有するようにした。
【０００８】
本発明の情報抽出プログラムは、コンピュータに、ウェブページの半構造化情報における検索語と前記検索語に関する情報との間の構造的位置関係を表すパターンから成るパターン集合に基づいて、前記ウェブページの集合から前記検索語に関する情報候補をブロック単位で抽出させ、抽出されたブロック単位の前記情報候補を情報分類技術によって評価し、前記ブロック単位の情報候補を抽出するべき情報と抽出するべき情報以外にそれぞれ分類させるようにした。
【発明の効果】
【０００９】
本発明によれば、不特定のウェブサイトのページから、ある検索語に関する特定の情報をブロック単位で抽出することができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１１】
図１は、本発明の一実施の形態に係る情報抽出装置の構成を示すブロック図である。
【００１２】
図１に示す情報抽出装置１００は、インターネット２００を経由して検索サイト３００に接続できるコンピュータシステムで構成されており、情報抽出装置１００は、大別して、入力装置１１０、コンピュータ本体１２０、および出力装置１３０を有する。
【００１３】
入力装置１１０は、例えば、キーボードやマウスなどである。出力装置１３０は、例えば、ディスプレイやプリンタなどである。このとき、入力装置１１０および出力装置１３０はインターネット経由の接続でも構わない。この場合、例えば、ユーザは、別の場所にあるコンピュータからインターネットを介して情報抽出装置１００のコンピュータ本体１２０に入力し、その抽出結果をユーザの使用しているコンピュータに出力することができる。
【００１４】
コンピュータ本体１２０は、大別して、検索処理部１４０、学習処理部１５０および記憶部１６０からなる。
【００１５】
検索処理部１４０は、検索語入力部１４１、ウェブページ取得部１４２、情報候補抽出部１４３、情報候補分類部１４４、情報選択部１４５、情報出力部１４６、を有し、ウェブページから特定の情報を抽出する。
【００１６】
学習処理部１５０は、学習用検索語入力部１５１、学習用ウェブページ取得部１５２、情報範囲入力部１５３、パターン集合学習データ作成部１５４、抽出パターン生成部１５５、情報分類器学習部１５６、を有し、教師データから情報抽出規則を学習する。
【００１７】
記憶部１６０は、検索処理部１４０および学習処理部１５０で生成された各種データを記憶し、必要に応じて読み出す。
【００１８】
まず、検索処理部１４０の各構成要素について説明する。
【００１９】
検索語入力部１４１は、ユーザによって操作される入力装置１１０と検索処理部１４０とを接続するインターフェースとしての機能を有し、入力装置１１０からユーザにより入力される検索語を入力処理して検索処理部１４０が処理可能なデータ形式に変換する。変換された検索語は、記憶部１６０の検索語データベース１６１へ格納されるとともにウェブページ取得部１４２へ渡される。
【００２０】
ウェブページ取得部１４２は、検索語入力部１４１から取得した検索語を使ってインターネット２００を経由して一般の検索サイト３００で検索を行い、検索語に関するウェブページの集合を取得する。取得したウェブページは、記憶部１６０のウェブページデータベース１６２へ格納されるとともに情報候補抽出部１４３へ渡される。
【００２１】
情報候補抽出部１４３は、ウェブページ取得部１４２によって取得されたウェブページの集合から、検索語に関する特定情報の候補（以下「情報候補」という）を抽出する。抽出規則には、学習処理部１５０によって生成されたパターン集合を構成する各パターンを用いる。パターンとは、ＨＴＭＬやＸＭＬなどで記述された半構造化情報における検索語とその検索語に関する特定情報との構造的位置関係を指定する規則である。ウェブページに対してパターンを当てはめてみれば、そのウェブページ中における特定情報と思われる情報（情報候補）の特定および抽出ができる（後述する）。以後、パターンを当てはめる処理を「パターンマッチング」といい、パターンが当てはまることを「マッチする」という。抽出された情報候補は、情報候補分類部１４４へ渡される。
【００２２】
以下、ＨＴＭＬで記述されたウェブページを例にして、情報候補の抽出原理について具体的に説明する。まず、取得されたウェブページは、ＨＴＭＬパーサによりタグ構造に基づいてＤＯＭ木（ＤＯＭ：Document Object Model）に変換される。例えば、図２（Ａ）のＨＴＭＬテキストは、図２（Ｂ）のＤＯＭ木に変換される。ＤＯＭ木は、ＨＴＭＬのタグをノードのラベルとして持つほか、テキストノード（#text）は、その位置に置かれたテキスト情報をさらに持つ。なお、"#text"というタグはＨＴＭＬにはないが、本発明ではテキストノードはこのタグの値を持つことにする。
【００２３】
図３（Ａ）は、パターンの一例（Ｐ,５）である。パターン（Ｐ,ｒ）は、パターン木Ｐと、葉ノード間の距離の制限ｒと、からなっている。パターン木Ｐは、根ノードと葉ノードを結ぶ二つのパスからなっている。一つはキーワードノードと呼ぶ、検索語が含まれる葉ノードへのパス、キーワードパスであり（図３（Ｂ））、もう一つはターゲットノードと呼ぶ、検索語に関する特定の情報が含まれる葉ノードへのパス、ターゲットパスである（図３（Ｃ））。ＤＯＭ木におけるノード間の距離は、深さ優先の木のなぞりにおける訪問順（前順）をノードのＩＤとした場合のＩＤの差で定義する（図２（Ｂ）の各ノードの番号を参照）。例えば、図２（Ｂ）のＤＯＭ木において、左下のテキストノード（Little Sapporo: My…）は、ＩＤが４番、右下のノード（tel: 000-…）は、ＩＤが１５番なので、これらのノード間の距離は、１５−４＝１１となる。葉ノード間の距離の制限ｒは、キーワードノードとターゲットノードにマッチするノードがＤＯＭ木にあった場合における、それら二つのノード間のＩＤの差に対しての制限である。例えば、図３（Ａ）のパターンでは、ｒ＝５なので、ＤＯＭ木におけるキーワードノードとターゲットノードにマッチする二つのノードがあったとしても、これらのノードのＩＤの差は５以下でなければならない。制限値ｒの決め方は、後述する。
【００２４】
情報候補抽出部１４３は、変換されたＤＯＭ木に対し、パターン集合内の各パターンとのパターンマッチングを行い、情報候補と思われるノード（ターゲットノードにマッチしたノード）を特定し、情報候補の抽出を行う。検索語が"Little Sapporo"、パターンが図３（Ａ）のパターン（Ｐ,５）、ＤＯＭ木が図２（Ｂ）の場合を例にして、情報候補抽出の流れを図４で説明する。
【００２５】
最初に、与えられた検索語が出現するテキストノードを探索することにより、キーワードノードのマッチングを行う。図２（Ｂ）のＤＯＭ木では、４番と８番のノードに"Little Sapporo"が含まれているので、これら二つのノードがキーワードノードにマッチする。以降、図４（Ａ）のように、８番のノードがキーワードノードにマッチしたとして、情報候補抽出の流れを説明する。
【００２６】
次に、キーワードパスのマッチングを行う。パスは、タグが一致するノードが同じ順（先祖と子孫の関係を保つ順）で出現する場合のみマッチする。ここでは、ＨＴＭＬの記述フォーマットの違いを吸収し、不特定サイトに対応できるように、二つのノードが隣接する場合とその間に他ノードが介在する場合との双方を同一の構造的位置関係とみなす。すなわち、図４（Ｂ）のように不連続（親と子の関係ではなく先祖と子孫の関係）でマッチしても構わないようにする。
【００２７】
次に、ターゲットパスのマッチングを行う。キーワードパスのマッチングで、パターン木の根ノードとマッチするノードが一つ定まるので、そこからターゲットパスのマッチングを行う。これもキーワードパスのときと同様、図４（Ｃ）のように不連続（親と子の関係ではなく先祖と子孫の関係）でマッチしても構わない。ターゲットノードにマッチするノードが見つかった場合、キーワードノードにマッチしたノードのＩＤとターゲットノードにマッチしたノードのＩＤの差を求め、それがｒ以下であれば、そのノードはパターン（Ｐ,ｒ）とマッチしたものとみなす。図３（Ａ）のパターン（Ｐ,５）はｒ＝５だが、図４（Ｃ）ではキーワードノートおよびターゲットノードにマッチした二つのノードのＩＤの差が４（＝１２−８）なので、パターン（Ｐ,５）とマッチすることになる。
【００２８】
最後に、情報候補を抽出する。パターン（Ｐ,ｒ）がマッチした場合は、図４（Ｄ）のように、ターゲットノードとマッチしたノードを根とする部分木に含まれる情報を抽出し、それを情報候補とする。パターン集合には複数のパターンが含まれているが、いずれかのパターンにマッチする情報は、全て情報候補とする。そのため、情報候補は、１ページから複数抽出されることがある。
【００２９】
情報候補分類部１４４は、学習処理部１５０によって生成された情報分類器に、情報候補抽出部１４３によって抽出された情報候補を一つずつかけ、それぞれの内容を情報分類技術によって評価して、抽出するべき情報と抽出するべきではない情報とに分類する。抽出するべき情報には「ターゲット情報（＋１）」と、抽出するべきではない情報には「ターゲット情報以外（−１）」とラベル付けする。ラベル付けされた情報候補は、情報選択部１４５へ渡される。
【００３０】
情報分類器にはいかなる分類器も利用できるが、本実施の形態では、情報分類器としてＳＶＭ（support vector machines）を用い、分類器の特徴ベクトルとして索引語ベクトルを用いる。索引語とは、情報の内容を特徴付けるうえで重要な単語のことを呼び、この索引語の重みを要素とするベクトルで情報を表現する。ここで用いる重みとしては、例えば、二進重み、索引語頻度、およびＴＦ−ＩＤＦ重み、などが挙げられる。
【００３１】
情報選択部１４５は、情報候補およびそれに付けられたラベルに基づいて、検索語に関する特定の情報と分類された情報を選択する。「ターゲット情報」とラベル付けされた情報候補が一つもないページには、抽出するべき情報は存在しないものと判断する。「ターゲット情報」とラベル付けされた情報候補が複数あるページでは、その中でターゲットノードとキーワードノードにマッチしたノード間の距離が最小のノードの情報を一つだけ選択する。この場合、もっと単純に、ラベルが「ターゲット情報」であるノードでＩＤが最小のものを選択する方法も考えられる。選択された情報は、情報出力部１４６へ渡される。
【００３２】
情報出力部１４６は、選択された情報を出力装置１３０が表示できるようなデータ形式に変換する。例えば、ウェブブラウザに表示できるように、ＨＴＭＬテキストへ変換する。変換されたデータは、出力装置１３０へ渡される。
【００３３】
選択された情報は、そのまま列挙したものを表示してもよいが、情報に優先度をつけ、優先度の高い結果から順に表示するようにしてもよい。優先度に情報の信頼度をうまく反映させることができれば、ユーザはその値も判断基準に使うことができるようになるので、判断を誤る可能性が減ると考えられる。
【００３４】
本実施の形態では、優先度を構成するものとして二つの基準を用いる。
【００３５】
一つ目の基準は、情報候補分類部１４４において情報に対して出力されたＳＶＭの値である。情報候補分類部１４４で分類器として用いたＳＶＭは、特徴ベクトルを入力すると実数値（識別境界からのマージン）を出力する。情報候補分類部１４４で情報候補のノードに付加するラベルは、分類器ＳＶＭの出力をｍとした時、ｍが正ならば＋１（ターゲット情報）、負ならば−１（ターゲット情報以外）である。しかし、ここでは、優先度の基準としてこのＳＶＭの出力である実数値ｍを用いる。この値が大きいノードの情報は、小さいものよりも分類器によってより抽出するべき情報らしいとされた情報となる。
【００３６】
二つ目の基準は、キーワードノードおよびターゲットノードにマッチした、二つのノード間のＩＤの差ｒである。これは、ＤＯＭ木において二つのノードがどれだけ離れているかを示す。この値が小さいノードはＤＯＭ木において検索語の近くにあるため、検索語に関する抽出するべき情報である可能性が高い。
【００３７】
本実施の形態では、これら二つの基準値を組み合わせた優先度を用いる。抽出結果のノードｏの集合をＯとし、ｏ∈ＯのＳＶＭの出力値をｍo、ＩＤの差をｒoとする。ただし、ｍo≧１の場合は、ｍo＝１とする。ｒmax＝ｍａｘo∈Oｒoとし、ｏの優先度＝ｍo＋（１−ｒo／ｒmax）、と定義する。このように定義した優先度を全ての抽出結果に対して求め、優先度の高い結果から順に表示する。なお、このように定義したｒmaxの値は、抽出結果のノードの集合Ｏに依存するため、依存しない方がよい場合には他の値に変えてもよい。例えば、学習処理部での学習時に使用した教師データ（後述）におけるキーワードノードとターゲットノードのＩＤの差の最大値をｒmaxとし、ｒo≧ｒmaxの場合はｒo＝ｒmaxとするという方法が挙げられる。
【００３８】
次に、学習処理部１５０の各構成要素について説明する。
【００３９】
学習用検索語入力部１５１は、ユーザによって操作される入力装置１１０と学習処理部１５０とを接続するインターフェースとしての機能を有し、入力装置１１０から入力される学習用検索語を入力処理して学習処理部１５０が処理可能なデータ形式に変換する。変換された学習用検索語は、教師データを作成するためのものであり、記憶部１６０の学習用検索語データベース１６３へ格納されるとともに学習用ウェブページ取得部１５２へ渡される。
【００４０】
学習用ウェブページ取得部１５２は、ユーザによって入力された学習用検索語を使ってインターネット２００を経由して一般の検索サイト３００で検索を行い、学習用検索語に関するウェブページの集合を取得する。取得したウェブページは、教師データを作成するためのものであり、記憶部１６０の学習用ウェブページデータベース１６４へ格納されるとともに情報範囲入力部１５３へ渡される。
【００４１】
情報範囲入力部１５３は、学習用ウェブページ取得部１５２によって取得された各学習用ウェブページ中における、学習用検索語に関する情報の位置を指定し、教師データを作成する。例えば、ＤＯＭ木の各テキストノードに対応する部分をクリックできるように変換したウェブページ上で、ユーザが学習用検索語に関する情報の位置を入力できるツールを用いることにより、ユーザが入力装置１１０を通して学習用検索語に関する情報の開始部分と終了部分を指定することができる。学習用検索語に関する情報の位置を指定されたウェブページは、ＨＴＭＬパーサによってＤＯＭ木に変換され、指定された情報に対応するノードをターゲットノードとする教師データ（学習用検索語、ＤＯＭ木、ターゲットノード）となる。このようにして得られた複数の教師データは、教師データ集合Ｄとしてまとめられ、記憶部１６０の教師データデータベース１６５へ格納されるとともにパターン集合学習データ作成部１５４へ渡される。
【００４２】
教師データは、（学習用検索語、ＤＯＭ木、ターゲットノード）の３つ組のデータである。例えば、図２（Ｂ）のデータであれば、（"Little Sapporo",Ｔ,ノード１２）が教師データとなる。ターゲットノードは、情報範囲入力部１５３によって指定された、学習用検索語に関する特定情報を含むノードであるが、複数ある場合にはそれらのＬＣＡ（Least Common Ancestor：最も近い共通祖先）とする。ターゲットノードがないページでは、ターゲットノードをＮＵＬＬ（値なし）として教師データを作成する。
【００４３】
パターン集合学習データ作成部１５４は、作成された教師データ集合Ｄを構成する各々の教師データから、学習用検索語と学習用検索語に関する情報との間の位置関係のパターン木を抽出し、パターン集合学習データを作成する。作成されたパターン集合学習データは、抽出パターン生成部１５５へ渡される。
【００４４】
具体的には、ターゲットノードの先祖ノード各々に対してそのノードを基点とするキーワードパスを探索し、キーワードパスを見つけたら、そのキーワードパスとその先祖ノードの位置を起点とするターゲットパスとから成るパターン木をパターン木集合Ｅl,tに格納する。このとき、ｌは先祖ノード（根ノード）のタグ、ｔはターゲットノードのタグである。図５（Ａ）および図５（Ｂ）は、図２（Ｂ）のデータによる教師データ（"Little Sapporo",Ｔ,ノード１２）から抽出されたパターン集合学習データである。この例では、Ｅ"html","#text"（図５（Ａ））およびＥ"body","#text"（図５（Ｂ））に属するパターン木が１つずつ抽出される。このように、パターン集合学習データは、複数の集合からなるデータである。あるいは、ターゲットノードに一番近いキーワードノードを含むパターン木のみ使用するという方法もある。
【００４５】
抽出パターン生成部１５５は、パターン集合学習データ作成部１５４によって作成された各々の集合Ｅl,tから抽出規則に用いるパターンを生成し、それらを集めてパターン集合Ｐとする。パターン集合Ｐは、教師データの集合Ｄにおいて頻出するパターン（Ｐ,ｒ）の集合である。生成されたパターン集合は、記憶部１６０のパターン集合データベース１６６に格納されるとともに情報分類器学習部１５６へ渡される。
【００４６】
具体的には、集合Ｅl,tごとに共通パターンを求める（図６の具体例を参照）。「共通の」ということは、データマイニングの分野の言葉では、「サポート１.０の」ということに相当するが、ここではサポートは、Ｅl,tに格納された各パターン木の抽出元のＤＯＭ木の数で計算するため、サポート１.０でも集合Ｅl,tに格納された全パターン木に出現しなくてもよい。ZakiのTreeMinerアルゴリズムのサポートのカウント法をこのように変えたものを実行することにより、抽出パターン生成部１５５の実現が可能である。また、キーワードパスとターゲットパスに分ければ、シークエンスマイニングのアルゴリズム（例えば、AgrawalとSrikantのAprioriAll等）を適用することもでき、より効率的に実現することができる。
【００４７】
図６は、抽出パターン生成部１５５により生成されるパターン（Ｐ,ｒ）の例である。図６では、集合Ｅ"tr","#text"が３つのパターン木Ｓ11（図６（Ａ））、Ｓ12（図６（Ｂ））、Ｓ2（図６（Ｃ））、から成っており、そのうちＳ11およびＳ12は同じＤＯＭ木から抽出されたものとする。抽出されたパターン木Ｐ（図６（Ｄ））は、Ｓ11には部分木として存在しないが、同じＤＯＭ木から抽出されたＳ12内に存在するため、パターン木Ｐは共通パターンとなる。キーワードノードとターゲットノードの間の距離の制限ｒは、このパターンが出現する２つの木Ｓ12、Ｓ2における二つのノード間の距離の最大値７（＝１６−９）とする。最終的に、集合Ｅ"tr","#text"の共通パターンとして（Ｐ,７）が得られる。同様の処理を全ての集合Ｅl,tに対して行い、集合Ｅl,tごとの共通パターンを求め、それらを集めて「パターン集合」とする。
【００４８】
情報分類器学習部１５６は、抽出パターン生成部１５５で求まったパターン集合Ｐおよび教師データ集合Ｄを使って、検索語に関する情報を分類する情報分類器を求める。パターン集合Ｐを用いて教師データ集合Ｄから情報を自動的に抽出すると、抽出された情報には、抽出するべき情報だけでなく、抽出するべきではない情報も含まれる。しかし、全ての情報について抽出するべきかどうかはわかっているので（情報範囲入力部で指定している）、これら抽出するべき情報および抽出するべきでない情報を教師データとすることによって、情報分類器を学習させることができる。求められた情報分類器は、記憶部１６０の情報分類器データベース１６７に格納される。
【００４９】
具体的には、まず、パターン集合Ｐを用いて情報候補抽出部１４３と同じ手段で教師データ集合から全ての情報候補を抽出する。このように抽出された情報候補のうち、抽出するべきである検索語に関する特定情報（ターゲットノード）が含まれていない教師データから抽出された情報は、全て「ターゲット情報以外（−１）」とする。また、ターゲットノードが含まれている教師データから抽出された情報のうち、抽出するべき情報の前に出現した（ターゲットノードのＩＤより小さいＩＤのノードに対応する）ものは全て「ターゲット情報以外（−１）」とし、抽出するべき情報は「ターゲット情報（＋１）」とし、その他のものは捨てる。このようにして得られた情報分類器学習データを既存の情報分類器学習アルゴリズムに与えることで、情報分類器を求める。
【００５０】
次いで、上記構成を有する情報抽出装置１００の動作について、図７〜図９に示すフローチャートを用いて説明する。全体の流れとしては、教師データを作成し、パターン集合と情報分類器を生成する段階（学習処理部１５０：図７、図８）と、検索語を入力し、その検索語に関するウェブページからその検索語に関する情報を抽出する段階（検索処理部１４０：図９）と、の二つに大きく分けられる。
【００５１】
まず、学習処理部１５０での動作について、図７に示すフローチャートを用いて説明する。
【００５２】
まず、ステップＳ１０００では、ユーザが学習用検索語入力部１５１に教師データ作成用の学習用検索語を入力する。学習用検索語入力部１５１は、入力された学習用検索語を学習処理部１５０が処理可能なデータ形式に変換する。変換された学習用検索語は、学習用検索語データベース１６３に格納されるとともに学習用ウェブページ取得部１５２へ渡される。
【００５３】
ステップＳ１１００では、学習用ウェブページ取得部１５２が、ステップＳ１０００で変換された学習用検索語を使って、インターネット２００を経由して一般の検索サイト３００で検索を行い、学習用検索語に関するウェブページの集合を取得する。取得されたウェブページの集合は、学習用ウェブページデータベース１６４に格納されるとともに情報範囲入力部１５３へ渡される。
【００５４】
ステップＳ１２００では、情報範囲入力部１５３が、ステップＳ１１００で取得された各学習用ウェブページ中における、学習用検索語に関する情報の位置を指定し、複数の教師データ（検索語、ＤＯＭ木、ターゲットノード）を作成する。作成された複数の教師データから成る教師データ集合Ｄは、教師データデータベース１６５に格納されるとともにパターン集合学習データ作成部１５４へ渡される。
【００５５】
ステップＳ１３００では、パターン集合学習データ作成部１５４が、ステップＳ１２００で作成された教師データ各々から、キーワードノードとターゲットノードの位置関係を示すパターン木を抽出し、パターン集合学習データを作成する。作成されたパターン集合学習データは、抽出パターン生成部１５５へ渡される。
【００５６】
ステップＳ１４００では、抽出パターン生成部１５５が、ステップＳ１３００で得られたパターン木の共通パターン（Ｐ,ｒ）を求め、パターン集合Ｐを生成する。
【００５７】
ステップＳ１５００では、必要に応じて、抽出パターン生成部１５５が、後述するＰＳアルゴリズムを用いて、パターン集合Ｐが教師データＤに対して適合率の高いパターン（Ｐ,ｒ）だけから成るように適合率の低いパターンを別のパターンと置換する。生成された新しいパターン集合Ｐは、パターン集合データベース１６６に格納されるとともに情報分類器学習部１５６へ渡される。
【００５８】
なお、このＰＳアルゴリズム処理はオプションであり、この処理を行わなくてもよい。ＰＳアルゴリズム処理を用いた方がよいかどうかは、後述する適合率と再現率のトレードオフの問題で、どちらを重視するかによる。ＰＳアルゴリズム処理を用いない場合には、ステップＳ１４００で生成されたパターン集合Ｐがそのままパターン集合データベース１６６に格納されるとともに情報分類器学習部１５６へ渡される。
【００５９】
ステップＳ１６００では、情報分類器学習部１５６が、パターン集合Ｐを用いて教師データ集合Ｄから情報を抽出し、そのデータに基づいて情報分類器学習データを生成する。情報分類器学習部１５６は、求まった情報分類器学習データを既存の情報分類器学習アルゴリズムに与え、情報分類器を求める。求まった情報分類器は、情報分類器データベース１６７に格納される。
【００６０】
以上のように、学習処理部１５０では、学習用検索語を入力し、学習用検索語に関する特定の情報の範囲を指定すると、パターン集合Ｐおよび情報分類器が自動的に生成される。ここで生成されたパターン集合Ｐおよび情報分類器は、この後説明する検索処理部１４０での検索処理に使用される。
【００６１】
ここで、ステップＳ１５００でオプションとして用いられるＰＳアルゴリズムについて説明する。
【００６２】
あるパターン（Ｐ,ｒ）の教師データ集合Ｄに対する適合率を、パターンにマッチしたノード総数に占める正解ノード数、と定義すると、ステップＳ１４００で生成されたパターン集合Ｐに含まれるパターンには、集合Ｄに対して適合率の高いパターンと低いパターンがあることがわかる。
【００６３】
本実施の形態では、この抽出結果全体の適合率の向上を目的として、パターン集合Ｐを教師データ集合Ｄに対して適合率の高いパターンだけから構成する方法（以下「ＰＳアルゴリズム」という）を必要に応じて用いる。ＰＳアルゴリズムは、閾値α（０≦α≦１）を設定し、あるパターン（Ｐ,ｒ）の教師データ集合Ｄに対する適合率がα未満である時、そのパターンをより特殊なパターンと置き換える方法である。
【００６４】
具体的には、教師データ集合Ｄに対して最も適合率が低く、かつ適合率がα未満であるパターン（Ｐ*,ｒ*）を、ＬＣＡおよびターゲットノードのタグが同じパターンの中でパターン（Ｐ*,ｒ*）の次にサポートが高いパターンと置換する。この操作を適合率がα以下のパターンがなくなるまで繰り返す。パターンのサポートとは、教師データ集合Ｄの中で、あるパターン（Ｐ,ｒ）がターゲットノードを候補としてあげることができる教師データの数である。
【００６５】
以下、図８のフローチャートを用いて動作を説明する。ここで、飽和パターンとは、パターン（Ｐ,ｒ）のパターン木Ｐにおいて、パターン木Ｐを構成するノードを一つでも加えるとサポートが小さくなるようなパターンのことをいう。また、αを適合率の閾値とする。なお、ステップＳ１５１０およびステップＳ１５２０は、ステップＳ１４００内で処理できる作業であるが、ＰＳアルゴリズムの動作を説明する便宜上、ステップＳ１５００内に含めて説明する。
【００６６】
まず、ステップＳ１５１０では、パターンリストを生成する。具体的には、抽出パターン生成部１５５が、ステップＳ１３００で作成された集合Ｅl,tごとに飽和パターンを求め、予備パターン集合Ｐl,tにそれぞれ格納する。このとき、ｌは、パターンの根ノードのタグ、ｔはターゲットノードのタグである。そして、抽出パターン生成部１５５は、集合Ｐl,tに含まれるパターンをサポートの高い順に格納したリストＱl,tを生成する。あまりにもサポートの低い飽和パターンは、効果が小さいため、しきい値βを設定して、サポートがβ以上のパターンのみを求めてもよい。これは、計算時間削減の効果もある。
【００６７】
ステップＳ１５２０では、パターン集合を初期化する。具体的には、抽出パターン生成部１５５が、（ｌ,ｔ）の全ての組み合わせにおいて、各リストＱl,tについて先頭の要素（一番サポートの高いパターン）を選び出し、パターン集合Ｐを生成する。
【００６８】
ステップＳ１５３０では、抽出パターン生成部１５５が、パターン集合Ｐを用いた情報抽出装置（ラッパー）を構築する。
【００６９】
ステップＳ１５４０では、各パターンの適合率を算出する。具体的には、抽出パターン生成部１５５が、教師データ集合Ｄに対して、ステップＳ１５３０で構築したラッパーを用いて情報抽出を行い、集合Ｐを構成する各パターン（Ｐ,ｒ）の集合Ｄに対する適合率を求める。
【００７０】
ステップＳ１５５０では、最も適合率の低いパターンを選択する。具体的には、抽出パターン生成部１５５が、パターン集合Ｐに含まれるパターンのうち、最も適合率の低いパターンを求める。
【００７１】
ステップＳ１５６０では、抽出パターン生成部１５５が、選択されたパターンの適合率が閾値α未満かどうかを判定する。この時、適合率がα以上だった場合は、ＰＳアルゴリズムは終了する。適合率がα未満の場合はステップＳ１５７０に進む。
【００７２】
ステップＳ１５７０では、抽出パターン生成部１５５が、ステップＳ１５５０で選択されたパターンをそのパターンが格納されていたリストＱl,tから削除し、残った２番目以降の各パターンの順位を一つ上げる。削除が終わったら、ステップＳ１５２０へ戻り、全ての適合率がα以上になるまで、ステップＳ１５２０からステップＳ１５７０までの各ステップを繰り返す。
【００７３】
以上の処理により、パターン集合Ｐは、適合率が閾値α以上となるパターンのみから構成されるようになる。しかしながら、この処理では、サポートが高いが適合率が低いパターンを、サポートが低いが適合率が高いパターンに置き換えるので、再現率が低くなる。上述したように、ＰＳアルゴリズム処理を用いた方がよいかどうかは、適合率と再現率のトレードオフの問題で、どちらを重視するかによる（実施例１参照）。
【００７４】
次いで、検索処理部１４０での動作について、図９に示すフローチャートを用いて説明する。
【００７５】
まず、ステップＳ２０００では、ユーザが検索語入力部１４１に検索語を入力する。検索語入力部１４１は、入力された検索語を検索処理部１４０が処理可能なデータ形式に変換する。変換された検索語は、検索語データベース１６１に格納されるとともにウェブページ取得部１４２へ渡される。
【００７６】
ステップＳ２１００では、ウェブページ取得部１４２が、検索語に関するウェブページの集合を取得する。本実施の形態では、ウェブページ取得部１４２が、インターネット２００を経由して一般の検索サイト３００で検索を行い、ウェブページを取得する。取得されたウェブページの集合は、ウェブページデータベース１６２に格納されるとともに情報候補抽出部１４３へ渡される。
【００７７】
ステップＳ２２００では、情報候補抽出部１４３が、ウェブページ取得部１４２で取得されたウェブページの集合に対し、学習処理部１５０で生成されたパターン集合Ｐを構成する各パターンとパターンマッチングを行い、情報候補を抽出する。抽出された情報候補は、情報候補分類部１４４へ渡される。
【００７８】
ステップＳ２３００では、情報候補分類部１４４が、学習処理部１５０によって生成された情報分類器に、情報候補を一つずつかけ、それぞれを「ターゲット情報（＋１）」と「ターゲット情報以外（−１）」にラベル付けする。ラベル付けされた情報候補は、情報選択部１４５へ渡される。
【００７９】
ステップＳ２４００では、情報選択部１４５が、情報候補からラベルに基づいて抽出するべき情報と思われる情報を選択する。選択された情報は、情報出力部１４６へ渡される。
【００８０】
ステップＳ２５００では、情報出力部１４６が、選択された情報を出力装置１３０が表示できるようなデータ形式に変換する。また、ここで、優先度に基づいて優先度の高い順に表示するようにしてもよい。変換されたデータは出力装置１３０へ渡される。
【００８１】
本実施の形態によれば、半構造化情報のＤＯＭ木のパターンマッチングにおいて、親子関係を拡張した先祖と子孫の関係でも一致するとみなすようにすることによってサイト間の構造の違いを吸収し、不特定サイトに対応することができる。
【００８２】
また、本実施の形態によれば、パターンマッチングの後に、情報分類器を用いて抽出された情報候補を「ターゲット情報」と「ターゲット情報以外」に分類し、目的とする情報のみを抽出することができる。上記のようにパターンマッチングの条件を緩くしてしまうと、より多くの情報候補を抽出することができるが、目的とする情報以外とも数多くマッチしてしまう。しかし、この情報分類器を用いることによって、抽出される情報に対する目的とする情報の割合を高めることができる。
【００８３】
さらに、本実施の形態によれば、抽出規則に相当する「パターン集合の作成」と「情報分類器の学習」を、少ない教師データから自動的に行うことができる。特許文献１の方法では、教師データの作成のほかに評価表現辞書を人手で作成しなければならないが、本実施の形態によれば、このような手間がかかることはない。
【００８４】
このように、本実施の形態によれば、不特定のウェブサイトのページからある検索語に関する特定の情報をブロック単位で抽出することができ、また、教師データから完全に自動的に抽出規則を学習することができる。
【００８５】
なお、本実施の形態における情報抽出装置は、実施例のように検索語に関する評判情報を抽出する装置として利用できる。しかし、何らかの分類器を用いて「ターゲット情報」と「ターゲット情報以外」に分類できれば、評判ではなくても本手法を用いてラッパーを構築することが可能である。例えば、Ｅメールアドレスや電話番号、住所などが考えられる。
【００８６】
さらに、本実施の形態では、半構造化情報としてＨＴＭＬで記述されたウェブページを例にして説明したが、これに限定されることはなく、ＸＭＬなどの他の半構造化情報についても本発明を適用することができる。
【００８７】
以下では、本実施の形態に係る情報抽出装置の動作の具体例を実施例として示す。
【実施例】
【００８８】
本発明の有効性を検証するために、ラーメン屋の評判情報を抽出することを想定して以下の実験を行った。なお、本発明に係る情報抽出装置、情報抽出方法、および情報抽出プログラムは、便宜上いずれも「ラッパー」という。
【００８９】
使用するデータは、ラーメン屋に関する情報が記述されたＨＴＭＬテキストである。地方タウン情報誌に記載されていた「人気ラーメン店ランキングトップ１００」に含まれる店について、検索サイトを用いて「店の名前」と「電話番号」でＡＮＤ検索した。そして、検索結果のページ数が１５以上であるとき、そのページを実験データとし、これをランキング上位から１０店分収集した（店番号１から店番号１０の１０店）。データは合計３０１ページ、このうち評判が書かれていたのは１８９ページであった。ラッパーに入力する検索語はラーメン屋の名前であり、抽出する情報はその店の評判情報である。実験では、データを店ごとに分割し、クロスバリデーションにより適合率と再現率を求めた。
【００９０】
テキスト分類法に利用した索引語は、名詞、動詞、形容詞、副詞の四つである。また、索引語の切り出しには、形態素解析エンジン「茶筌」（http://chasen.aist-nara.ac.jp/hiki/ChaSen）を用いた。索引語ベクトルの要素の重みには索引語の頻度を用い、ベクトルの正規化にはユークリッドノルムを用いた。分類器のＳＶＭとして「SVMTorchII」（http://www.idiap.ch/bengio/projects/SVMTorch.html）を用い、カーネルとして三次元の多項式カーネルＫ（ｘ,ｙ）＝（ｘｙ＋１）３を用いた。
【００９１】
ＰＳアルゴリズム処理では、最小サポートを０.１としたときの飽和パターンを用い、閾値α＝０.９でラッパーを構築した。
【００９２】
実験結果を図１０に示す。テストデータに対する適合率と再現率の列で、括弧のついていない値は、教師データ（検索語、ＤＯＭ木、ターゲットノード）でターゲットノードと指定したノードの情報だけを正解として求めた。括弧内は、上記の精度の求め方では不正解とされた情報に関し、以下に示す基準Ａのいずれかを満たしていれば正解とした値である。
「基準Ａ」
１．抽出すべき評判情報の一部である。すなわち、ターゲットノードの子孫のノードである場合。
２．抽出すべき評判情報を含み、検索語に関する情報以外を含まない。すなわち、ターゲットノードの先祖ノードであり、検索語に関係しない余計な情報を含まない場合。
３．抽出すべき評判情報を含んでいないが、検索語に関する情報であり、評判情報とみることもできる。すなわち、ターゲットノードとはＤＯＭ木上で先祖・子孫関係ではないノードであるが、内容を調べると、検索語に関する評判情報とみることができる場合。
【００９３】
基準Ａで考えると、ＰＳアルゴリズムなしでも適合率約８０％、再現率約５５％であり、実用的に使える精度であるといえる。ＰＳアルゴリズムを使うと適合率が９０％以上になるが、再現率は５０％以下に低下する。したがって、誤った情報が表示されることを嫌う場合には、ＰＳアルゴリズムを使用し、少しでも多くの情報を得たい場合にはＰＳアルゴリズムを使わない方がよいことがわかる。
【００９４】
図１１の表は、ＰＳアルゴリズム（α＝０.９）を用いたときの出力結果に優先順位を付けた場合の不正解の順位に関する結果を示す。この表においては、基準Ａを満たさないものは不正解とした。ここでは、優先度として、ＳＶＭの出力値ｍoおよびノードのＩＤの差（１−ｒo／ｒmax）を組み合わせて用いる方法（ｍo＋（１−ｒo／ｒmax））の他に、ｍoまたは（１−ｒo／ｒmax）のみ用いた場合の結果も示す。２つの値を組み合わせたものを優先度とした場合、不正解は全体的に下位にランク付けられており、上位から数えて不正解が含まれない割合の上限は、抽出結果全体の６０％であった。優先度としてｍoのみ利用したときのこの割合は約３０％であり、（１−ｒo／ｒmax）のみ利用したときは不正解が一位となることがあった。したがって、これらの値を組み合わせることで、優先度の信頼性が増したことがわかる。特に店番号６番、１０番の結果では、不正解のの情報が最下位となっており、二つの値を組み合わせた優先度は有効に働いている。
【００９５】
ラッパーの出力結果の例を図１２に示す。これは、ＰＳアルゴリズム（α＝０.９）を用いて、店番号１０番についての評判情報を抽出した結果であり、優先順位の上位から順に記述した。○は正解、△は基準Ａを満たすもの、×は不正解を示している。図１２では、店名および地名をアステリスクで置換したが、実際の出力結果では完全に表示されている。本発明に係る情報抽出装置および情報抽出方法によって、ある検索語（この場合、ラーメン屋の店名）に関する評判情報が、不特定のウェブサイトのページからブロック単位で抽出されていることがわかる。
【産業上の利用可能性】
【００９６】
本発明に係る情報抽出装置および情報抽出方法は、不特定のウェブサイトのページからある検索語に関する特定の情報をブロック単位で抽出することができ、また、教師データから完全に自動的に抽出規則を学習することができる、情報抽出装置および情報抽出方法として有用である。
【図面の簡単な説明】
【００９７】
【図１】本発明の一実施の形態に係る情報抽出装置の構成を示すブロック図
【図２】本実施の形態におけるＨＴＭＬパーサによるウェブページのＤＯＭ木への変換を示す図であり、（Ａ）は、変換前のＨＴＭＬテキストを示す図、（Ｂ）は、変換後のＤＯＭ木を示す図
【図３】本実施の形態におけるパターンの一例を示す図であり、（Ａ）は、パターン（Ｐ,５）およびパターン木Ｐを示す図、（Ｂ）は、パターン木Ｐにおけるキーワードパスを示す図、（Ｃ）は、パターン木Ｐにおけるターゲットパスを示す図
【図４】本実施の形態におけるパターンマッチングを示す図であり、（Ａ）は、キーワードマッチングを示す図、（Ｂ）は、キーワードパスのマッチングを示す図、（Ｃ）は、ターゲットパスのマッチングを示す図、（Ｄ）は、抽出された情報候補を示す図
【図５】本実施の形態におけるパターン集合学習データの一例を示す図であり、（Ａ）は、Ｅ"html","#text"に属するパターン集合学習データの一例を示す図、（Ｂ）は、Ｅ"body","#text"に属するパターン集合学習データの一例を示す図
【図６】本実施の形態におけるパターン生成の一例を示す図であり、（Ａ）および（Ｂ）は、同じＤＯＭ木から抽出された２つの木をそれぞれ示す図、（Ｃ）は、（Ａ）および（Ｂ）とは別のＤＯＭ木から抽出された木を示す図、（Ｄ）は、２つのＤＯＭ木から抽出された共通パターンを示す図
【図７】本実施の形態における学習処理部の動作を示すフローチャート
【図８】本実施の形態におけるＰＳアルゴリズムの動作を示すフローチャート
【図９】本実施の形態における検索処理部の動作を示すフローチャート
【図１０】実施例１の実験結果を示す表
【図１１】ＰＳアルゴリズムを用いたときのラッパーの出力に優先順位を付けた結果を示す表
【図１２】ラッパーの出力結果の例を示す図
【符号の説明】
【００９８】
１００  情報抽出装置
１１０  入力装置
１２０  コンピュータ本体
１３０  出力装置
１４０  検索処理部
１４１  検索語入力部
１４２  ウェブページ取得部
１４３  情報候補抽出部
１４４  情報候補分類部
１４５  情報選択部
１４６  情報出力部
１５０  学習処理部
１５１  学習用検索語入力部
１５２  学習用ウェブページ取得部
１５３  情報範囲入力部
１５４  パターン集合学習データ作成部
１５５  抽出パターン生成部
１５６  情報分類器学習部
１６０  記憶部
１６１  検索語データベース
１６２  ウェブページデータベース
１６３  学習用検索語データベース
１６４  学習用ウェブページデータベース
１６５  教師データデータベース
１６６  パターン集合データベース
１６７  情報分類器データベース
２００  インターネット
３００  検索サイト
【図１】
2007047974.tif 000003
【図２】
2007047974.tif 000004
【図３】
2007047974.tif 000005
【図４】
2007047974.tif 000006
【図５】
2007047974.tif 000007
【図６】
2007047974.tif 000008
【図７】
2007047974.tif 000009
【図８】
2007047974.tif 000010
【図９】
2007047974.tif 000011
【図１０】
2007047974.tif 000012
【図１１】
2007047974.tif 000013
【図１２】
2007047974.tif 000014