集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体
【課題】意味的に同一のカテゴリに含まれる語を選択するのに好適な集合拡張処理装置等を提供する。
【解決手段】受付部１０１がシード文字列を受け付ける。検索部１０２がシード文字列を含む文書のスニペットを得る。セグメント取得部１０３が当該スニペットをセグメント区切文字列で区切ってセグメントを得る。セグメント要素取得部１０４がセグメントをセグメント要素区切文字列で区切ってセグメント要素を得る。セグメントスコア計算部１０５がセグメントのセグメントスコアをセグメント要素の長さの標準偏差から計算する。セグメント要素スコア計算部１０６がセグメント要素のセグメント要素スコアをシード文字列の位置とセグメント要素の位置との距離とセグメントスコアから計算する。選択部１０７がセグメント要素スコアに基づいてセグメント要素からいずれかをシード文字列の拡張集合に含まれるインスタンスの候補として選択する。
【解決手段】受付部１０１がシード文字列を受け付ける。検索部１０２がシード文字列を含む文書のスニペットを得る。セグメント取得部１０３が当該スニペットをセグメント区切文字列で区切ってセグメントを得る。セグメント要素取得部１０４がセグメントをセグメント要素区切文字列で区切ってセグメント要素を得る。セグメントスコア計算部１０５がセグメントのセグメントスコアをセグメント要素の長さの標準偏差から計算する。セグメント要素スコア計算部１０６がセグメント要素のセグメント要素スコアをシード文字列の位置とセグメント要素の位置との距離とセグメントスコアから計算する。選択部１０７がセグメント要素スコアに基づいてセグメント要素からいずれかをシード文字列の拡張集合に含まれるインスタンスの候補として選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体に関し、特に、意味的に同一のカテゴリに含まれる語の獲得に関するものである。
【背景技術】
【０００２】
ネットショッピングにおいて、ショッピングサイトで取り扱われる商品はカテゴリ分けされて、ユーザに提示される。例えば、特許文献１には、商品を掲載するページにおいて、商品のカテゴリ“家電商品”、“書籍”、“コンピュータ”等を表示する情報送受信システムが開示されている。ユーザは、これらのカテゴリの中から購入を希望する商品のカテゴリを選択することにより、容易に商品を絞り込むことができる。
【０００３】
一方、人名、地名、あるいは、商品名などの固有表現を体系的に構築・維持するには膨大なコストがかかる。そのため、固有表現の意味的関係性を計算機により自動的に獲得する自動獲得手法が盛んに研究されている。例えば、非特許文献１には、分かち書き文から意味的語彙カテゴリを抽出するアルゴリズム（「ｇ−Ｅｓｐｒｅｓｓｏアルゴリズム」という）が開示されている。また、非特許文献２には、非分かち書き文から意味的語彙カテゴリを抽出するアルゴリズム（「ｇ−Ｍｏｎａｋａアルゴリズム」という）が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−４８２２６号公報
【非特許文献】
【０００５】
【非特許文献１】Mamoru Komachi, Taku Kudo, Masahi Shimbo, and Yuji Matsumoto, "Graph-based analysis of semantic drift in espresso-like bootstrapping algorithms." In Proc. of the EMNLP 2008, pp. 1011-1020, 2008.
【非特許文献２】萩原正人、小川泰弘、外山勝彦、「グラフカーネルに基づく非分かち書き文からの意味的語彙カテゴリの抽出」、言語処理学会第１５回年次大会講演論文集、ｐｐ．６９７−７００、２００９年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のようなショッピングサイトにおいて、日々新たな商品が登場するため、手動では商品のカテゴリの登録作業が追いつかなく、多くのユーザが検索する商品であっても、その商品が属するカテゴリが設けられていない場合がある。しかしながら、店舗側にとっては、新たな商品が登場する度に登録すべきカテゴリを調査するのは負担が大きく、登録すべきカテゴリの候補を自動的に選択してもらいたいという要望があった。
【０００７】
本発明は、上記のような課題を解決するもので、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の観点に係る集合拡張処理装置は、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
を備えることを特徴とする。
【０００９】
また、上記観点に係る集合拡張処理装置において、
前記インスタンスの候補を用いて検索することにより得られたスニペットから、前記抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成し、当該接続グラフにおける前記受け付けられたシード文字列の前後の文脈と当該インスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスの候補との類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する抽出部
をさらに備えることを特徴とする。
【００１０】
また、上記観点に係る集合拡張処理装置において、
前記得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、前記セグメントスコアならびに前記セグメント要素スコアは、当該セグメントに含まれるセグメント要素が前記インスタンスの候補として前記選択部により選択されることがないような値となる
ことを特徴とする。
【００１１】
また、上記観点に係る集合拡張処理装置において、
前記得られたセグメントのそれぞれに出現するセグメント要素のそれぞれのセグメント要素スコアは、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との最短距離に対して指数的に減衰する
ことを特徴とする。
【００１２】
本発明の第２の観点に係る集合拡張処理方法は、
受付部と、検索部と、セグメント取得部と、セグメント要素取得部と、セグメントスコア計算部と、セグメント要素スコア計算部と、選択部と、を備える集合拡張処理装置が実行する集合拡張処理方法であって、
前記受付部が、シード文字列を受け付ける受付工程、
前記検索部が、前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索工程、
前記セグメント取得部が、前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得工程、
前記セグメント要素取得部が、前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得工程、
前記セグメントスコア計算部が、前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算工程、
前記セグメント要素スコア計算部が、前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算工程、
前記選択部が、前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択工程、
を備えることを特徴とする。
【００１３】
本発明の第３の観点に係るプログラムは、
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とする。
【００１４】
本発明の第４の観点に係るコンピュータ読み取り可能な記録媒体は、
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラムを記録する。
【００１５】
上記プログラムは、プログラムが実行されるコンピュータとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記記録媒体は、コンピュータとは独立して配布・販売することができる。
【発明の効果】
【００１６】
本発明によれば、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態に係る集合拡張処理装置と、ショッピングサーバとの関係を示す図である。
【図２】本発明の実施形態に係る集合拡張処理装置が実現される典型的な情報処理装置の概要構成を示す図である。
【図３】実施形態１の集合拡張処理装置の概要構成を説明するための図である。
【図４】検索された文書を説明するための図である。
【図５】セグメントを説明するための図である。
【図６】セグメント要素を説明するための図である。
【図７】セグメントスコア及びセグメント要素スコアを説明するための図である。
【図８】選択されたインスタンスの候補を説明するための図である。
【図９】実施形態１に係る集合拡張処理装置の各部が行う集合拡張処理を説明するためのフローチャート図である。
【図１０】実施形態２の集合拡張処理装置の概要構成を説明するための図である。
【図１１】接続グラフを説明するための図である。
【図１２】抽出されたインスタンスを説明するための図である。
【図１３】実施形態２に係る集合拡張処理装置の各部が行う集合拡張処理を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１８】
本発明の実施形態に係る集合拡張処理装置１００は、図１に示すように、ショッピングサーバ２００に接続される。ショッピングサーバ２００はインターネット３００に接続される。インターネット３００には、ユーザが操作する複数の端末装置４０１、４０２〜４０ｎが接続されている。ショッピングサーバ２００は、インターネット３００を介し、端末装置４０１〜４０ｎに、ショッピングサーバ２００に登録されている商品の情報を提示し、端末装置４０１〜４０ｎから商品の注文を受け付ける。一般的に、ショッピングサーバ２００に登録されている商品は、商品の種類に基づいてカテゴリ分けされて、端末装置４０１〜４０ｎのユーザに提示される。集合拡張処理装置１００は、ショッピングサーバ２００で扱う商品について集合拡張処理を行い、商品のカテゴリの候補を提示するものである。
【００１９】
ここで、「集合拡張」とは、少数の正解セットをシードとして与え、シードと意味的に同一のカテゴリに属する語の集合を獲得するタスクをいう。例えば、キッチン用品の“中華鍋”、“圧力鍋”をシードとした場合、意味的に同一のカテゴリに属する語とは“土鍋”、“雪平鍋”、及び“タジン鍋”等である。すなわち、集合拡張処理装置１００は、“中華鍋”、“圧力鍋”がシードとして与えられると、それらと同一のカテゴリ“鍋”に属する語として、“土鍋”、“雪平鍋”や“タジン鍋”等を獲得する。
【００２０】
以下、本発明の実施形態に係る集合拡張処理装置１００が実現される典型的な情報処理装置５００について説明する。
【００２１】
（１．情報処理装置の概要構成）
情報処理装置５００は、図２に示すように、ＣＰＵ（Central Processing Unit）５０１と、ＲＯＭ（Read only Memory）５０２と、ＲＡＭ（Random Access Memory）５０３と、ＮＩＣ（Network Interface Card）５０４と、画像処理部５０５と、音声処理部５０６と、ＤＶＤ−ＲＯＭ（Digital Versatile Disc ROM）ドライブ５０７と、インターフェース５０８と、外部メモリ５０９と、コントローラ５１０と、モニタ５１１と、スピーカ５１２と、を備える。
【００２２】
ＣＰＵ ５０１は、情報処理装置５００全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
【００２３】
ＲＯＭ ５０２には、電源投入直後に実行されるＩＰＬ（Initial Program Loader）が記録され、これが実行されることにより、所定のプログラムをＲＡＭ ５０３に読み出してＣＰＵ ５０１による当該プログラムの実行が開始される。また、ＲＯＭ ５０２には、情報処理装置５００全体の動作制御に必要なオペレーティングシステムのプログラムや各種のデータが記録される。
【００２４】
ＲＡＭ ５０３は、データやプログラムを一時的に記憶するためのもので、ＤＶＤ−ＲＯＭから読み出したプログラムやデータ、その他、通信に必要なデータ等が保持される。
【００２５】
ＮＩＣ ５０４は、情報処理装置５００をインターネット３００等のコンピュータ通信網に接続するためのものであり、ＬＡＮ（Local Area Network）を構成する際に用いられる１０ＢＡＳＥ−Ｔ／１００ＢＡＳＥ−Ｔ規格にしたがうものや、電話回線を用いてインターネットに接続するためのアナログモデム、ＩＳＤＮ（Integrated Services Digital Network）モデム、ＡＤＳＬ（Asymmetric Digital Subscriber Line）モデム、ケーブルテレビジョン回線を用いてインターネットに接続するためのケーブルモデム等と、これらとＣＰＵ ５０１との仲立ちを行うインターフェース（図示せず）により構成される。
【００２６】
画像処理部５０５は、ＤＶＤ−ＲＯＭ等から読み出されたデータをＣＰＵ ５０１や画像処理部５０５が備える画像演算プロセッサ（図示せず）によって加工処理した後、これを画像処理部５０５が備えるフレームメモリ（図示せず）に記録する。フレームメモリに記録された画像情報は、所定の同期タイミングでビデオ信号に変換され、モニタ５１１に出力される。これにより、各種のページ表示が可能となる。
【００２７】
音声処理部５０６は、ＤＶＤ−ＲＯＭ等から読み出した音声データをアナログ音声信号に変換し、これに接続されたスピーカ５１２から出力させる。また、ＣＰＵ ５０１の制御の下、情報処理装置５００が行う処理の進行の中で発生させるべき音を生成し、これに対応した音声をスピーカ５１２から出力させる。
【００２８】
ＤＶＤ−ＲＯＭドライブ５０７に装着されるＤＶＤ−ＲＯＭには、例えば、実施形態に係る集合拡張処理装置１００を実現するためのプログラムが記憶される。ＣＰＵ ５０１の制御によって、ＤＶＤ−ＲＯＭドライブ５０７は、これに装着されたＤＶＤ−ＲＯＭに対する読み出し処理を行って、必要なプログラムやデータを読み出し、これらはＲＡＭ ５０３等に一時的に記憶される。
【００２９】
インターフェース５０８には、外部メモリ５０９、コントローラ５１０、モニタ５１１、及びスピーカ５１２が、着脱可能に接続される。
【００３０】
外部メモリ５０９には、ユーザの個人情報に関するデータなどが書き換え可能に記憶される。
【００３１】
コントローラ５１０は、情報処理装置５００の各種の設定時などに行われる操作入力を受け付ける。情報処理装置５００のユーザは、コントローラ５１０を介して指示入力を行うことにより、これらのデータを適宜外部メモリ５０９に記録することができる。
【００３２】
モニタ５１１は、画像処理部５０５により出力されたデータを情報処理装置５００のユーザに提示する。
【００３３】
スピーカ５１２は、音声処理部５０６により出力された音声データを情報処理装置５００のユーザに提示する。
【００３４】
この他、情報処理装置５００は、ハードディスク等の大容量外部記憶装置を用いて、ＲＯＭ ５０２、ＲＡＭ ５０３、外部メモリ５０９、ＤＶＤ−ＲＯＭドライブ５０７に装着されるＤＶＤ−ＲＯＭ等と同じ機能を果たすように構成してもよい。
【００３５】
以下、上記情報処理装置５００において実現される実施形態に係る集合拡張処理装置１００の概要構成について、図１乃至１３を参照して説明する。情報処理装置５００の電源を投入することにより、実施形態に係る集合拡張処理装置１００として機能させるプログラムが実行され、実施形態に係る集合拡張処理装置１００が実現される。
【００３６】
（２．実施形態１の集合拡張処理装置の概要構成）
実施形態１の集合拡張処理装置１００は、シード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補を選択するものである。
【００３７】
本実施形態に係る集合拡張処理装置１００は、図３に示すように、受付部１０１と、検索部１０２と、セグメント取得部１０３と、セグメント要素取得部１０４と、セグメントスコア計算部１０５と、セグメント要素スコア計算部１０６と、選択部１０７と、から構成される。
【００３８】
以下、集合拡張処理装置１００が、キッチン商品の鍋のカテゴリに属する語として適当な語（インスタンス）の候補の提示を行う場合を例に説明する。
【００３９】
受付部１０１は、シード文字列を受け付ける。シード文字列とは、例えば、“鍋”のカテゴリに属する語の集合に含まれる正解の語（“中華鍋”や“圧力鍋”等）である。例えば、図４に示すように、ユーザがＷＥＢページの検索エンジンの検索欄６０１に、全てのシード文字列をスペース区切りで連結させたものをクエリとして入力し、検索ボタン６０２を押圧する。この場合、受付部１０１は、検索欄６０１に入力された“中華鍋”及び“圧力鍋”をシード文字列として受け付ける。なお、検索エンジンの種類は任意である。
【００４０】
本実施形態では、ＣＰＵ ５０１及びコントローラ５１０が協働して、受付部１０１として機能する。
【００４１】
検索部１０２は、受け付けられたシード文字列を含む文書を検索し、スニペットを得る。ここで、スニペットとは、例えば、ＷＥＢページの検索エンジンを使用した際に、検索結果として表示されるクエリを含むテキスト部分である。検索部１０２は、ＷＥＢページの検索エンジンに対して、全てのシード文字列をスペース区切りで連結させたものをクエリとして入力し、検索結果の、例えば、上位３００件のスニペットのリストを得る。例えば、検索部１０２は、“中華鍋 圧力鍋”をクエリとして検索エンジンを用いてＷＥＢページの検索を行い、与えられたシード文字列“中華鍋”及び“圧力鍋”を含む図４のスニペット１、２、３〜３００（図示せず）を得る。なお、検索部１０２は、上記のように外部装置を利用して文書を得ることに限らず、内部に検索機能を備えるようにしてもよい。例えば、検索部１０２は、Ｗｅｂ検索ＡＰＩを使用してスニペットを得ることとしてもよい。
【００４２】
本実施形態では、検索部１０２は、ＣＰＵ ５０１及びＮＩＣ ５０４が協働して、検索部１０２として機能する。
【００４３】
セグメント取得部１０３は、得られたスニペットを所定のセグメント区切文字列で区切ることにより、シード文字列の前後に出現する文字列と、シード文字列とを出現順に並べた文字列からなるセグメントを得る。スニペットは、検索語が含まれるページにおいて当該検索語がどのように用いられているかがユーザにとって一目で分かるように、所定の区切文字列で区切られているのが一般的である。例えば、所定のセグメント区切文字列を“・・・”とする。例えば、セグメント取得部１０３は、得られたスニペット１、２、３〜３００をＵｎｉｃｏｄｅのＮＦＫＣにより正規化して、小文字に統一し、セグメント区切文字列“・・・”によって複数の文字列に分割する。そして、セグメント取得部１０３は、分割された文字列のうち重複している文字列は除外し、残りの文字列をセグメントとして得る。得られたスニペットを小文字に統一することにより、例えば、型番等の文字列が大文字・小文字で統一されていない場合に対応することができる。図５に、セグメント取得部１０３がスニペット１から得たセグメント１−１〜１−３を示す。
【００４４】
なお、セグメント区切文字列は、“・・・”の文字列に限らない。検索部１０２が使用する検索エンジン又はＷｅｂ検索ＡＰＩが提示するスニペットが、例えば、“−−−”や“＃＃”の文字列で区切られている場合、セグメント区切文字列を“−−−”や“＃＃”の文字列とする。また、セグメントを得る手法は、セグメント区切文字列を用いてセグメントを得る手法に限らない。セグメントは、使用する検索エンジン又はＷｅｂ検索ＡＰＩが提示するスニペットに応じて、適宜取得される。例えば、１つのスニペットが、“・・・”等の記号により区切られずに提示される場合は、当該スニペットを１つのセグメントとする。また、予め、スニペット内のセグメントに相当する部分が箇条書き等で提示される場合は、箇条書きの１行に該当する部分を１つのセグメントとする。
【００４５】
本実施形態では、ＣＰＵ ５０１がセグメント取得部１０３として機能する。
【００４６】
セグメント要素取得部１０４は、得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることによりセグメント要素を得る。例えば、所定のセグメント要素区切文字列とは、句読点や記号（“、”、“，”、“。”、“！”、“［”、“］”等）であり、これらのセグメント要素区切文字列によりセグメントを区切り、セグメント要素を得る。例えば、セグメント要素取得部１０４は、図５のセグメント１−１、１−２、１−３をセグメント要素区切文字列で区切ると、図６のセグメント要素群１−１Ｐ（セグメント要素Ｐｉ（ｉ＝１〜５））、１−２Ｐ（セグメント要素Ｐｉ（ｉ＝１〜１２））、１−３Ｐ（セグメント要素Ｐｉ（ｉ＝１〜５））を得る。
【００４７】
本実施形態では、ＣＰＵ ５０１がセグメント要素取得部１０４として機能する。
【００４８】
セグメントスコア計算部１０５は、得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算する。ここで、得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、セグメントスコアならびに後述のセグメント要素スコアは、当該セグメントに含まれるセグメント要素がインスタンスの候補として選択部１０７により選択されることがないような値となるとする。本実施形態では、セグメント要素の長さを、Ｕｎｉｃｏｄｅの文字数で定義するが、これに限られない。例えば、セグメント要素の長さとして、その他の文字コードにおけるバイト数を採用することも可能である。
【００４９】
例えば、図５に示すように、セグメント１−１、１−３は、通常の文を含んでいるが、セグメント１−２は、通常の文を含んでいない。そして、セグメント１−１、１−３に含まれるセグメント要素の長さのばらつきは、セグメント１−２に含まれるセグメント要素の長さのばらつきよりも大きい。すなわち、通常の文を含んでいるセグメントは、一般的に、通常の文を含んでいないセグメントよりも、セグメントに含まれる各セグメント要素の長さが揃っていないという傾向がある。そして、通常の文を含むセグメントには、シード文字列と同じ意味範囲に属するインスタンスが含まれていないことが多いので、インスタンスの候補を得るセグメントとして適当ではない。したがって、以下では、セグメント要素の長さの標準偏差が所定の閾値を越えるセグメントは、インスタンスの候補を得るセグメントから除外することとする。
【００５０】
本実施形態では、所定の閾値を５．００とする。また、セグメントスコア計算部１０５は、セグメント要素の長さの標準偏差が５．００未満の場合は、標準偏差の値そのものを、セグメントスコアとし、標準偏差が５．００以上の場合は、セグメントスコアを５．００とする。
【００５１】
図７に、セグメントスコア計算部１０５が計算したセグメントスコアを示す。図７のテーブルには、シード文字列をクエリとして得た「スニペット７０１ａ」と、スニペット７０１ａに含まれる「セグメント７０２ａ」と、セグメント７０２ａに含まれる「セグメント要素７０３ａ」と、セグメント要素７０３ａの「長さ７０４ａ」と、長さ７０４ａの「標準偏差７０５ａ」と、標準偏差７０５ａに基づいて計算される「セグメントスコア７０６ａ」と、後述するセグメント要素スコア計算部１０６により計算される「セグメント要素スコア７０７ａ」と、が対応づけて記載されている。
【００５２】
例えば、セグメントスコア計算部１０５は、図７の７０４ａに示すように、セグメント１−１に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）、セグメント１−２に含まれるセグメント要素Ｐｉ（ｉ＝１〜１２）、及び、セグメント１−３に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さを求める。そして、セグメントスコア計算部１０５は、図７の７０５ａに示すように、セグメント１−１に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さの標準偏差を“５．８９”、セグメント１−２に含まれるセグメント要素Ｐｉ（ｉ＝１〜１２）の長さの標準偏差を“１．３４”、セグメント１−３に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さの標準偏差を“５．２７”と求める。したがって、セグメントスコア計算部１０５は、図７の７０６ａに示すように、セグメント１−１のセグメントスコアを“５．００”、セグメント１−２のセグメントスコアを“１．３４”、セグメント１−３のセグメントスコアを“５．００”と求める。
【００５３】
本実施形態では、ＣＰＵ ５０１がセグメントスコア計算部１０５として機能する。
【００５４】
セグメント要素スコア計算部１０６は、得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算する。
【００５５】
例えば、前述のように、セグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、セグメント要素スコアを、セグメント要素がインスタンスの候補として選択部１０７により選択されないような値になるとする。例えば、セグメント要素スコア計算部１０６は、セグメントスコアが“５．００”の場合は、セグメント要素スコアを“０”とする。一方、セグメントスコアが“５．００”未満の場合は、セグメント要素スコア計算部１０６は、セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離に基づいてセグメント要素スコアを計算する。ここで、セグメントにおいてシード文字列が出現する位置ｓｊ（ｊ：シード文字列の数）、及びセグメントにおいてセグメント要素が出現する位置ｐｉとは、図６に示すように、セグメントにおいて出現順にセグメント要素を並べた時のセグメント内での出現順位であり、距離とは位置ｓｊと位置ｐｉとの出現順位の差である。すなわち、シード文字列が“中華鍋”及び“圧力鍋”とすると、セグメント１−２においてシード文字列“中華鍋”（Ｐ８）が出現する位置ｓ１は“８”番目であり、シード文字列“圧力鍋”（Ｐ４）が出現する位置ｓ２は“４”番目である。また、セグメント１−２においてセグメント要素“親子鍋”（Ｐ５）が出現する位置ｐ５は“５”番目であり、シード文字列“中華鍋”（Ｐ８）とセグメント要素“親子鍋”（Ｐ５）との距離は３となる。
【００５６】
そして、セグメント要素スコア計算部１０６は、セグメント要素スコアＳｉを、セグメントにおいてシード文字列が出現する位置ｓｊと、セグメントにおいてセグメント要素が出現する位置ｐｉとから、以下の式（数１）に基づいて計算する。この式（数１）によれば、最も近いシード文字列との距離に従い指数的に減衰するスコアが、各セグメント要素のセグメント要素スコアとされる。本実施形態ではα＝０．８とする。計算結果を図７のセグメント要素スコア７０７ａに示す。
【００５７】
【数１】
上記においては、最も近いシード文字列との距離に従い指数的に減衰するスコアを求めることとしたが、スコアの求め方には様々な変形が可能である。例えば、シード文字列が複数存在する場合に、各シード文字列とセグメント要素との距離をそれぞれ求め、求めた距離の平均値に従い線形的に減衰するスコアを各セグメント要素のセグメント要素スコアとしてもよい。
以上、セグメント内にシード文字列が出現する場合の一例を記載したが、シード文字列の類似語が出現する場合も同様に計算できる。具体的には、“中華鍋”及び“圧力鍋”をシード文字列とした場合に、検索部ではシード文字列に加えてシード文字列の類似語で検索を行うと、“中華なべ”や“圧力なべ”といったシード文字列の類似語が含まれるスニペットが得られる。このような場合には、セグメント要素スコア計算部１０６において、公知の漢字かな文字変換プログラム等を用いることで、シード文字列の類似語をシード文字列として同様に取り扱うことができる。このように、シード文字列の類似語がセグメント内に出現した場合であっても、数１に従ってセグメント要素スコアＳｉを計算できる。
【００５８】
本実施形態では、ＣＰＵ ５０１がセグメント要素スコア計算部１０６として機能する。
【００５９】
選択部１０７は、得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する。ここで、拡張集合とは、集合拡張処理を施した後に得られる集合であり、シード文字列と意味的に同一のカテゴリに含まれる語の集合である。例えば、選択部１０７は、セグメント要素スコアの値が“０．１０”未満のセグメント要素をインスタンスの候補から除外し、残りのセグメント要素をインスタンスの候補として選択する。すなわち、選択部１０７は、セグメント１−１、１−３から得たセグメント要素のセグメント要素スコアがすべて“０”なので（図７）、セグメント１−１、１−３から得たセグメント要素を候補から除外する。そして、選択部１０７は、図８に示すように、セグメント１−２から得たセグメント要素のうち、セグメント要素スコアが“０．１０”未満の“パスタマシーン”、“その他”、及び、“さらに価格が”のセグメント要素を除外し、残りのセグメント要素を、“中華鍋”及び“圧力鍋”と意味的に同一のカテゴリに含まれるインスタンスの候補として選択する。なお、本実施形態では、１つのスニペットを例に、インスタンスの候補を選択する手法について説明したが、実際には多数のスニペットからセグメント要素を得てセグメント要素スコアを求め、インスタンスの候補を選択する。この場合、同じセグメント要素に、異なるスニペットからそれぞれセグメント要素スコアが求められることがある。特に、シード文字列と意味的に同じカテゴリに含まれるセグメント要素は、複数のスニペットに含まれることが多いと考えられるので、複数のセグメント要素スコアが得られる可能性が高い。したがって、複数のセグメント要素スコアが得られた場合、それらの和や最大値等を当該セグメント要素のセグメント要素スコアの値とする。このように処理することにより、より適当なインスタンスの候補を選択することができる。
【００６０】
本実施形態では、ＣＰＵ ５０１が選択部１０７として機能する。
【００６１】
（３．実施形態１の集合拡張処理装置の動作）
次に、本実施形態の集合拡張処理装置１００の各部が行う動作について図９のフローチャートを用いて説明する。集合拡張処理装置１００に電源が入れられ、所定の操作が行われると、ＣＰＵ ５０１は図９のフローチャートに示す集合拡張処理を開始する。
【００６２】
まず、受付部１０１は、シード文字列を受け付ける（ステップＳ１０１）。例えば、受付部１０１は、図４に示すように、ＷＥＢページの検索エンジンの検索欄６０１にクエリとして入力された“中華鍋”及び“圧力鍋”を、シード文字列として受け付ける。
【００６３】
次に、検索部１０２は、受け付けられたシード文字列を含む文書を検索し、スニペットを得る（ステップＳ１０２）。例えば、検索部１０２は、シード文字列“中華鍋”及び“圧力鍋”をクエリとして検索し、図４に示すように、検索結果の上位３００件のスニペット１、２、３〜３００を得る。なお、検索部１０２が得るスニペットの数は、任意であるが、およそ１００件以上のスニペットを得ることにより、より適当なインスタンスの候補を選択することができる。
【００６４】
次に、セグメント取得部１０３は、検索部１０２が得たスニペットを、セグメント区切文字列で区切ることによりセグメントを得る（ステップＳ１０３）。例えば、セグメント取得部１０３は、スニペット１、２、３〜３００をセグメント区切文字列“・・・”で区切り、セグメントを得る。例えば、セグメント取得部１０３は、スニペット１から、図５に示すように、セグメント１−１〜１−３を得る。
【００６５】
セグメントが得られると（ステップＳ１０３）、セグメント要素取得部１０４は、当該セグメントを所定のセグメント要素区切文字列で区切ることによりセグメント要素を得る（ステップＳ１０４）。例えば、セグメント１−１〜１−３を、セグメント要素区切文字列（“、”、“，”、“。”、“！”、“［”、“］”等）で区切り、図６のセグメント要素（セグメント要素群１−１Ｐ、１−２Ｐ、１−３Ｐ）を得る。
【００６６】
セグメント要素が得られると（ステップＳ１０４）、セグメントスコア計算部１０５は、当該セグメントのそれぞれのセグメントスコアをセグメントが含むセグメント要素の長さの標準偏差に基づいて計算する（ステップＳ１０５）。例えば、セグメントスコア計算部１０５は、セグメント要素の長さの標準偏差が５．００未満の場合は、標準偏差の値そのものをセグメントスコアとし、セグメント要素の長さの標準偏差が５．００以上の場合は、セグメントスコアを５．００とする。すなわち、セグメントスコア計算部１０５は、標準偏差が“５．８９”のセグメント１−１のセグメントスコアを“５．００”、標準偏差が“１．３４”のセグメント１−２のセグメントスコアを“１．３４”、標準偏差が“５．２７”のセグメント１−３のセグメントスコアを“５．００”と求める。
【００６７】
次に、セグメント要素スコア計算部１０６は、セグメント要素のセグメント要素スコアを、セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算する（ステップＳ１０６）。例えば、セグメント要素スコア計算部１０６は、セグメントスコアが“５．００”の場合は、セグメント要素スコアを“０”とし、セグメントスコアが“５．００”未満の場合は、セグメントにおいてシード文字列が出現する位置とセグメント要素が出現する位置との距離を用いた式（数１）に基づいて、セグメント要素スコア７０７ａ（図７）を計算する。
【００６８】
そして、選択部１０７は、得られたセグメント要素についてのセグメント要素スコアに基づいて、シード文字列と意味的に同一のカテゴリに属するインスタンスの候補を選択する（ステップＳ１０７）。例えば、選択部１０７は、図８に示すように、セグメント要素スコアの値が“０．１０”以上のセグメント要素をインスタンスの候補として選択する。
【００６９】
本実施形態によれば、“親子鍋”や“タジン鍋”は、シード文字列の“中華鍋”や“圧力鍋”と同じ“鍋”のカテゴリに含まれる用語であるので、意味的に同一のカテゴリに属する語の候補を選択することができる。
【００７０】
（４．実施形態２の集合拡張処理装置の概要構成）
実施形態２の集合拡張処理装置１００は、拡張集合に含まれるインスタンスの候補について、文脈に基づいてフィルタをかけることにより、意味的に無関係な語を排除するものである。
【００７１】
本実施形態に係る集合拡張処理装置１００は、図１０に示すように、受付部１０１と、検索部１０２と、セグメント取得部１０３と、セグメント要素取得部１０４と、セグメントスコア計算部１０５と、セグメント要素スコア計算部１０６と、選択部１０７と、抽出部１０８と、から構成される。本実施形態の受付部１０１、検索部１０２、セグメント取得部１０３、セグメント要素取得部１０４、セグメントスコア計算部１０５、セグメント要素スコア計算部１０６、及び、選択部１０７は、実施形態１と同様の機能を有する。以下、異なる機能を有する抽出部１０８について説明する。
【００７２】
まず、インスタンスの候補は、シード文字列の前後の文脈とインスタンスの候補の前後の文脈とが類似するほど、シード文字列と意味的に類似していると考えられる。そこで、実施形態２の集合拡張処理装置１００は、シード文字列の前後の文脈とインスタンスの候補の前後の文脈とに基づいてシード文字列とインスタンスの候補との類似度を求め、当該類似度に基づき、インスタンスの候補の中からインスタンスを抽出する。これにより、意味的に無関係な語を排除することができる。以下、集合拡張装置１００は、ｇ−Ｍｏｎａｋａアルゴリズムに基づいて計算した類似度から、インスタンスの候補をランク付けし、所定の値以上の類似度を有するものをインスタンスとして抽出する。なお、類似度を求める手法はｇ−Ｍｏｎａｋａアルゴリズムに限らない。例えば、ｇ−Ｅｓｐｒｅｓｓｏアルゴリズムを用いてもよい。
【００７３】
抽出部１０８は、インスタンスの候補を用いて検索することにより得られたスニペットから、抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成する。そして、抽出部１０８は、当該接続グラフにおける、受け付けられたシード文字列の前後の文脈とインスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスとの類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する。以下、ｇ−Ｍｏｎａｋａアルゴリズムに基づく類似度の計算手法を詳細に説明する。
【００７４】
抽出部１０８は、選択部１０７が選択したインスタンスの候補のそれぞれを、ＷＥＢページの検索エンジンに対してクエリとして入力し、検索結果の上位３００件のスニペットのリストを得る。そして、抽出部１０８は、得られたスニペットに対して、ＵｎｉｃｏｄｅのＮＦＫＣにより正規化して、小文字に統一し、重複を取り除く。また、日本語の割合が極端に少ない、記号が多いなど、スニペットとして適当でないものを除外する。
【００７５】
次に、抽出部１０８は、残ったスニペットの集合に含まれるすべての文字ｎグラムについて、接続行列Ｍ（ｕ，ｖ）を構築する。接続行列Ｍ（ｕ，ｖ）は、式（数２）で表される。
【００７６】
【数２】
【００７７】
ここで、｜ｕ，ｖ｜は、ｎグラムｕの後にｎグラムｖが続く頻度であり、｜ｕ，＊｜、｜＊，ｖ｜はそれぞれ、ｎグラムｕ、ｎグラムｖそのものの出現頻度である。本実施形態では、｜ｕ，ｖ｜、｜ｕ，＊｜、｜＊，ｖ｜は、それら自体をクエリとして検索した場合の検索結果数であり、ｐｍｉ（ｕ，ｖ）は、それらの検索結果数の自然対数をとったものを用いている。
【００７８】
次に、抽出部１０８は、全てのｎグラムの集合Ｖを節点集合とし、Ｍを接続行列として表現される有向重み付きグラフ（以下、「接続グラフ」という）ＧＭを生成する。生成した接続グラフＧＭの例を図１１に示す。このグラフにおいて、ｎグラムｕ及びｎグラムｖのそれぞれの右側文脈及び左側文脈が類似しているほど、それらの意味は類似しているとみなすことができる。
【００７９】
ここで、まず、ｎグラムｕの右側文脈とｎグラムｖの右側文脈とが類似しているか否かは、引用解析手法の書誌結合の概念に対応付けて考えることができる。書誌結合とは、文献ｘ、ｙが同じ文献を引用することをいう。すなわち、書誌結合は、ｎグラムｕとｎグラムｖが同じｎグラムに接続しているか否かということに対応付けて考えることができる。一方、ｎグラムｕの左側文脈とｎグラムｖの左側文脈とが類似しているか否かは、引用解析手法の共引用の概念に対応付けて考えることができる。共引用とは、文献ｘ、ｙが同じ文献により引用されることをいう。すなわち、ｎグラムｕとｎグラムｖが同じｎグラムから接続されているか否かということに対応付けて考えることができる。
【００８０】
したがって、ｎグラムｕ及びｎグラムｖの右側文脈及び左側文脈が類似しているか否かを示す類似度行列ＡＲ、ＡＬを、書誌結合行列及び共引用行列にそれぞれ対応させて求めることとする。右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬは、接続行列Ｍを用いて、式（数３）で表すことができる。
【００８１】
【数３】
【００８２】
抽出部１０８は、全てのｎグラムについて右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬを求める。
【００８３】
また、ｎグラムｕとｎグラムｖとが意味的に類似しているとみなすためには、右側文脈及び左側文脈の両者が類似している必要がある（以下、「両側近接制約」という）。そこで、抽出部１０８は、式（数４）に示すように、要素毎の重み付き一般化平均によって、ｎグラムｕとｎグラムｖとの類似度を示す類似度行列Ａを求める。ここで、ｍは、この両側近接制約の強さを調節するパラメータであり、本実施形態では、ｍ＝０．１とする。
【００８４】
【数４】
【００８５】
そして、抽出部１０８は、この類似度行列Ａを用いてラプラシアンカーネルＲβ（Ａ）を、数５、数６の式から求める。
【００８６】
【数５】
【００８７】
【数６】
【００８８】
Ｒβ（Ａ）の（ｉ，ｊ）要素が、ｎグラムｉとｎグラムｊとの類似度に対応する。そこで、抽出部１０８は、シードベクトルｖ０（シード文字列に対応する要素が１、それ以外が０となっているようなベクトル）を用いて、Ｒβ（Ａ）ｖ０計算し、計算された値を類似度とする。βの値は、任意であり、例えば、１．０−２である。
【００８９】
例えば、図１１の接続グラフＧＭにおいて、“中華鍋”は“の”に接続し、“調理はさみ”、“タジン鍋”は両者とも“の”に接続している。また、“中華鍋”に接続する“の”は、“タジン鍋”に接続しているが、“調理はさみ”には接続していない。このような場合において、“調理はさみ”の“中華鍋”に対する類似度Ｒβ（Ａ）ｖ０は、“タジン鍋”の“中華鍋”に対する類似度Ｒβ（Ａ）ｖ０よりも小さい値となる。
【００９０】
抽出部１０８は、例えば、計算した類似度が所定の値を超えたものを、インスタンスとして抽出する。例えば、図１２に示すように類似度が求められ、所定の値を“０．１０”とすると、抽出部１０８は、“圧力鍋”、“中華鍋”、“親子鍋”、“タジン鍋”、“伊賀焼”を、インスタンスとして抽出する。
【００９１】
本実施形態では、ＣＰＵ ５０１が抽出部１０８として機能する。
【００９２】
（５．実施形態２の集合拡張処理装置の動作）
次に、本実施形態の集合拡張処理装置１００の各部が行う動作について図１３のフローチャートを用いて説明する。集合拡張処理装置１００に電源が入れられ、所定の操作が行われると、ＣＰＵ ５０１は図１３のフローチャートに示す集合拡張処理を開始する。なお、図１３のフローチャートにおいて、図９のフローチャートと同じステップ番号が付されているステップは、図９のフローチャートにおける処理と同様の処理を行う。したがって、これらの説明は省略する。
【００９３】
選択部１０７によりインスタンスの候補が選択されると（ステップＳ１０７）、抽出部１０８は、インスタンスの候補を用いて検索エンジンで検索することによりスニペットを取得する（ステップＳ２０８）。例えば、抽出部１０８は、インスタンスの候補をクエリとしてＷＥＢページの検索エンジンに入力し、検索結果の上位３００件のスニペットのリストを得る。
【００９４】
次に、抽出部１０８は得られたスニペットからインスタンスの候補を含むｎグラムの接続グラフを生成する（ステップＳ２０９）。例えば、抽出部１０８は、３００件のスニペットから、不適当なものを除外し、残ったスニペットの集合に含まれるすべての文字のｎグラムについて、接続行列Ｍを求める。そして、図１１に示すように、すべてのｎグラムの集合Ｖを節点集合とし、Ｍ（数２）を接続行列として表現される接続グラフＧＭを生成する。
【００９５】
抽出部１０８は、接続グラフにおける、シード文字列の前後の文脈と、インスタンスの候補の前後の文脈とに基づいて、シード文字列とインスタンスの候補との類似度を計算する（ステップＳ２１０）。例えば、抽出部１０８は、式（数３）に基づいて、右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬを求め、式（数４）に示すように、要素毎に重み付き一般化平均を行った類似度行列Ａを求める。さらに、式（数５、６）に基づいて、類似度行列Ａを用いたラプラシアンカーネルＲβ（Ａ）を求め、シードベクトルｖ０を乗じることにより、シード文字列に対するインスタンスの候補の類似度を求める。
【００９６】
抽出部１０８は、類似度に基づいてインスタンスを抽出する（ステップＳ２１１）。例えば、抽出部１０８は、計算した類似度が“０．１０”を超えたものを、図１２に示すように、インスタンスとして抽出する。また、あるいは、抽出部１０８は、類似度の高いものから所定の個数だけ抽出することとしてもよい。例えば、インスタンスの候補が図１２に示すように９個有る場合、所定の個数を４個とすると、抽出部１０８は、類似度において上位４個の“圧力鍋”、“中華鍋”、“親子鍋”、及び、“タジン鍋”をインスタンスとして抽出する。
【００９７】
本実施形態によれば、意味的に無関係な語を排除することができ、意味的に同一のカテゴリに含まれるとみなすのにより適当な用語を抽出することができる。
【００９８】
なお、実施形態１、２では、集合拡張処理装置１００は、ショッピングサイトの商品のカテゴリ生成に適用する例を示したが、これに限らない。例えば、固有表現獲得や辞書構築等に応用可能である。
【産業上の利用可能性】
【００９９】
本発明によれば、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することができる。
【符号の説明】
【０１００】
１００ 集合拡張処理装置
１０１ 受付部
１０２ 検索部
１０３ セグメント取得部
１０４ セグメント要素取得部
１０５ セグメントスコア計算部
１０６ セグメント要素スコア計算部
１０７ 選択部
１０８ 抽出部
２００ ショッピングサーバ
３００ インターネット
４０１、４０２〜４０ｎ 端末装置
５００ 情報処理装置
５０１ ＣＰＵ
５０２ ＲＯＭ
５０３ ＲＡＭ
５０４ ＮＩＣ
５０５ 画像処理部
５０６ 音声処理部
５０７ ＤＶＤ−ＲＯＭドライブ
５０８ インターフェース
５０９ 外部メモリ
５１０ コントローラ
５１１ モニタ
５１２ スピーカ
６０１ 検索欄
６０２ 検索ボタン
【技術分野】
【０００１】
本発明は、集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体に関し、特に、意味的に同一のカテゴリに含まれる語の獲得に関するものである。
【背景技術】
【０００２】
ネットショッピングにおいて、ショッピングサイトで取り扱われる商品はカテゴリ分けされて、ユーザに提示される。例えば、特許文献１には、商品を掲載するページにおいて、商品のカテゴリ“家電商品”、“書籍”、“コンピュータ”等を表示する情報送受信システムが開示されている。ユーザは、これらのカテゴリの中から購入を希望する商品のカテゴリを選択することにより、容易に商品を絞り込むことができる。
【０００３】
一方、人名、地名、あるいは、商品名などの固有表現を体系的に構築・維持するには膨大なコストがかかる。そのため、固有表現の意味的関係性を計算機により自動的に獲得する自動獲得手法が盛んに研究されている。例えば、非特許文献１には、分かち書き文から意味的語彙カテゴリを抽出するアルゴリズム（「ｇ−Ｅｓｐｒｅｓｓｏアルゴリズム」という）が開示されている。また、非特許文献２には、非分かち書き文から意味的語彙カテゴリを抽出するアルゴリズム（「ｇ−Ｍｏｎａｋａアルゴリズム」という）が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−４８２２６号公報
【非特許文献】
【０００５】
【非特許文献１】Mamoru Komachi, Taku Kudo, Masahi Shimbo, and Yuji Matsumoto, "Graph-based analysis of semantic drift in espresso-like bootstrapping algorithms." In Proc. of the EMNLP 2008, pp. 1011-1020, 2008.
【非特許文献２】萩原正人、小川泰弘、外山勝彦、「グラフカーネルに基づく非分かち書き文からの意味的語彙カテゴリの抽出」、言語処理学会第１５回年次大会講演論文集、ｐｐ．６９７−７００、２００９年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のようなショッピングサイトにおいて、日々新たな商品が登場するため、手動では商品のカテゴリの登録作業が追いつかなく、多くのユーザが検索する商品であっても、その商品が属するカテゴリが設けられていない場合がある。しかしながら、店舗側にとっては、新たな商品が登場する度に登録すべきカテゴリを調査するのは負担が大きく、登録すべきカテゴリの候補を自動的に選択してもらいたいという要望があった。
【０００７】
本発明は、上記のような課題を解決するもので、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の観点に係る集合拡張処理装置は、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
を備えることを特徴とする。
【０００９】
また、上記観点に係る集合拡張処理装置において、
前記インスタンスの候補を用いて検索することにより得られたスニペットから、前記抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成し、当該接続グラフにおける前記受け付けられたシード文字列の前後の文脈と当該インスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスの候補との類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する抽出部
をさらに備えることを特徴とする。
【００１０】
また、上記観点に係る集合拡張処理装置において、
前記得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、前記セグメントスコアならびに前記セグメント要素スコアは、当該セグメントに含まれるセグメント要素が前記インスタンスの候補として前記選択部により選択されることがないような値となる
ことを特徴とする。
【００１１】
また、上記観点に係る集合拡張処理装置において、
前記得られたセグメントのそれぞれに出現するセグメント要素のそれぞれのセグメント要素スコアは、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との最短距離に対して指数的に減衰する
ことを特徴とする。
【００１２】
本発明の第２の観点に係る集合拡張処理方法は、
受付部と、検索部と、セグメント取得部と、セグメント要素取得部と、セグメントスコア計算部と、セグメント要素スコア計算部と、選択部と、を備える集合拡張処理装置が実行する集合拡張処理方法であって、
前記受付部が、シード文字列を受け付ける受付工程、
前記検索部が、前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索工程、
前記セグメント取得部が、前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得工程、
前記セグメント要素取得部が、前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得工程、
前記セグメントスコア計算部が、前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算工程、
前記セグメント要素スコア計算部が、前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算工程、
前記選択部が、前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択工程、
を備えることを特徴とする。
【００１３】
本発明の第３の観点に係るプログラムは、
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とする。
【００１４】
本発明の第４の観点に係るコンピュータ読み取り可能な記録媒体は、
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラムを記録する。
【００１５】
上記プログラムは、プログラムが実行されるコンピュータとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記記録媒体は、コンピュータとは独立して配布・販売することができる。
【発明の効果】
【００１６】
本発明によれば、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態に係る集合拡張処理装置と、ショッピングサーバとの関係を示す図である。
【図２】本発明の実施形態に係る集合拡張処理装置が実現される典型的な情報処理装置の概要構成を示す図である。
【図３】実施形態１の集合拡張処理装置の概要構成を説明するための図である。
【図４】検索された文書を説明するための図である。
【図５】セグメントを説明するための図である。
【図６】セグメント要素を説明するための図である。
【図７】セグメントスコア及びセグメント要素スコアを説明するための図である。
【図８】選択されたインスタンスの候補を説明するための図である。
【図９】実施形態１に係る集合拡張処理装置の各部が行う集合拡張処理を説明するためのフローチャート図である。
【図１０】実施形態２の集合拡張処理装置の概要構成を説明するための図である。
【図１１】接続グラフを説明するための図である。
【図１２】抽出されたインスタンスを説明するための図である。
【図１３】実施形態２に係る集合拡張処理装置の各部が行う集合拡張処理を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１８】
本発明の実施形態に係る集合拡張処理装置１００は、図１に示すように、ショッピングサーバ２００に接続される。ショッピングサーバ２００はインターネット３００に接続される。インターネット３００には、ユーザが操作する複数の端末装置４０１、４０２〜４０ｎが接続されている。ショッピングサーバ２００は、インターネット３００を介し、端末装置４０１〜４０ｎに、ショッピングサーバ２００に登録されている商品の情報を提示し、端末装置４０１〜４０ｎから商品の注文を受け付ける。一般的に、ショッピングサーバ２００に登録されている商品は、商品の種類に基づいてカテゴリ分けされて、端末装置４０１〜４０ｎのユーザに提示される。集合拡張処理装置１００は、ショッピングサーバ２００で扱う商品について集合拡張処理を行い、商品のカテゴリの候補を提示するものである。
【００１９】
ここで、「集合拡張」とは、少数の正解セットをシードとして与え、シードと意味的に同一のカテゴリに属する語の集合を獲得するタスクをいう。例えば、キッチン用品の“中華鍋”、“圧力鍋”をシードとした場合、意味的に同一のカテゴリに属する語とは“土鍋”、“雪平鍋”、及び“タジン鍋”等である。すなわち、集合拡張処理装置１００は、“中華鍋”、“圧力鍋”がシードとして与えられると、それらと同一のカテゴリ“鍋”に属する語として、“土鍋”、“雪平鍋”や“タジン鍋”等を獲得する。
【００２０】
以下、本発明の実施形態に係る集合拡張処理装置１００が実現される典型的な情報処理装置５００について説明する。
【００２１】
（１．情報処理装置の概要構成）
情報処理装置５００は、図２に示すように、ＣＰＵ（Central Processing Unit）５０１と、ＲＯＭ（Read only Memory）５０２と、ＲＡＭ（Random Access Memory）５０３と、ＮＩＣ（Network Interface Card）５０４と、画像処理部５０５と、音声処理部５０６と、ＤＶＤ−ＲＯＭ（Digital Versatile Disc ROM）ドライブ５０７と、インターフェース５０８と、外部メモリ５０９と、コントローラ５１０と、モニタ５１１と、スピーカ５１２と、を備える。
【００２２】
ＣＰＵ ５０１は、情報処理装置５００全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。
【００２３】
ＲＯＭ ５０２には、電源投入直後に実行されるＩＰＬ（Initial Program Loader）が記録され、これが実行されることにより、所定のプログラムをＲＡＭ ５０３に読み出してＣＰＵ ５０１による当該プログラムの実行が開始される。また、ＲＯＭ ５０２には、情報処理装置５００全体の動作制御に必要なオペレーティングシステムのプログラムや各種のデータが記録される。
【００２４】
ＲＡＭ ５０３は、データやプログラムを一時的に記憶するためのもので、ＤＶＤ−ＲＯＭから読み出したプログラムやデータ、その他、通信に必要なデータ等が保持される。
【００２５】
ＮＩＣ ５０４は、情報処理装置５００をインターネット３００等のコンピュータ通信網に接続するためのものであり、ＬＡＮ（Local Area Network）を構成する際に用いられる１０ＢＡＳＥ−Ｔ／１００ＢＡＳＥ−Ｔ規格にしたがうものや、電話回線を用いてインターネットに接続するためのアナログモデム、ＩＳＤＮ（Integrated Services Digital Network）モデム、ＡＤＳＬ（Asymmetric Digital Subscriber Line）モデム、ケーブルテレビジョン回線を用いてインターネットに接続するためのケーブルモデム等と、これらとＣＰＵ ５０１との仲立ちを行うインターフェース（図示せず）により構成される。
【００２６】
画像処理部５０５は、ＤＶＤ−ＲＯＭ等から読み出されたデータをＣＰＵ ５０１や画像処理部５０５が備える画像演算プロセッサ（図示せず）によって加工処理した後、これを画像処理部５０５が備えるフレームメモリ（図示せず）に記録する。フレームメモリに記録された画像情報は、所定の同期タイミングでビデオ信号に変換され、モニタ５１１に出力される。これにより、各種のページ表示が可能となる。
【００２７】
音声処理部５０６は、ＤＶＤ−ＲＯＭ等から読み出した音声データをアナログ音声信号に変換し、これに接続されたスピーカ５１２から出力させる。また、ＣＰＵ ５０１の制御の下、情報処理装置５００が行う処理の進行の中で発生させるべき音を生成し、これに対応した音声をスピーカ５１２から出力させる。
【００２８】
ＤＶＤ−ＲＯＭドライブ５０７に装着されるＤＶＤ−ＲＯＭには、例えば、実施形態に係る集合拡張処理装置１００を実現するためのプログラムが記憶される。ＣＰＵ ５０１の制御によって、ＤＶＤ−ＲＯＭドライブ５０７は、これに装着されたＤＶＤ−ＲＯＭに対する読み出し処理を行って、必要なプログラムやデータを読み出し、これらはＲＡＭ ５０３等に一時的に記憶される。
【００２９】
インターフェース５０８には、外部メモリ５０９、コントローラ５１０、モニタ５１１、及びスピーカ５１２が、着脱可能に接続される。
【００３０】
外部メモリ５０９には、ユーザの個人情報に関するデータなどが書き換え可能に記憶される。
【００３１】
コントローラ５１０は、情報処理装置５００の各種の設定時などに行われる操作入力を受け付ける。情報処理装置５００のユーザは、コントローラ５１０を介して指示入力を行うことにより、これらのデータを適宜外部メモリ５０９に記録することができる。
【００３２】
モニタ５１１は、画像処理部５０５により出力されたデータを情報処理装置５００のユーザに提示する。
【００３３】
スピーカ５１２は、音声処理部５０６により出力された音声データを情報処理装置５００のユーザに提示する。
【００３４】
この他、情報処理装置５００は、ハードディスク等の大容量外部記憶装置を用いて、ＲＯＭ ５０２、ＲＡＭ ５０３、外部メモリ５０９、ＤＶＤ−ＲＯＭドライブ５０７に装着されるＤＶＤ−ＲＯＭ等と同じ機能を果たすように構成してもよい。
【００３５】
以下、上記情報処理装置５００において実現される実施形態に係る集合拡張処理装置１００の概要構成について、図１乃至１３を参照して説明する。情報処理装置５００の電源を投入することにより、実施形態に係る集合拡張処理装置１００として機能させるプログラムが実行され、実施形態に係る集合拡張処理装置１００が実現される。
【００３６】
（２．実施形態１の集合拡張処理装置の概要構成）
実施形態１の集合拡張処理装置１００は、シード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補を選択するものである。
【００３７】
本実施形態に係る集合拡張処理装置１００は、図３に示すように、受付部１０１と、検索部１０２と、セグメント取得部１０３と、セグメント要素取得部１０４と、セグメントスコア計算部１０５と、セグメント要素スコア計算部１０６と、選択部１０７と、から構成される。
【００３８】
以下、集合拡張処理装置１００が、キッチン商品の鍋のカテゴリに属する語として適当な語（インスタンス）の候補の提示を行う場合を例に説明する。
【００３９】
受付部１０１は、シード文字列を受け付ける。シード文字列とは、例えば、“鍋”のカテゴリに属する語の集合に含まれる正解の語（“中華鍋”や“圧力鍋”等）である。例えば、図４に示すように、ユーザがＷＥＢページの検索エンジンの検索欄６０１に、全てのシード文字列をスペース区切りで連結させたものをクエリとして入力し、検索ボタン６０２を押圧する。この場合、受付部１０１は、検索欄６０１に入力された“中華鍋”及び“圧力鍋”をシード文字列として受け付ける。なお、検索エンジンの種類は任意である。
【００４０】
本実施形態では、ＣＰＵ ５０１及びコントローラ５１０が協働して、受付部１０１として機能する。
【００４１】
検索部１０２は、受け付けられたシード文字列を含む文書を検索し、スニペットを得る。ここで、スニペットとは、例えば、ＷＥＢページの検索エンジンを使用した際に、検索結果として表示されるクエリを含むテキスト部分である。検索部１０２は、ＷＥＢページの検索エンジンに対して、全てのシード文字列をスペース区切りで連結させたものをクエリとして入力し、検索結果の、例えば、上位３００件のスニペットのリストを得る。例えば、検索部１０２は、“中華鍋 圧力鍋”をクエリとして検索エンジンを用いてＷＥＢページの検索を行い、与えられたシード文字列“中華鍋”及び“圧力鍋”を含む図４のスニペット１、２、３〜３００（図示せず）を得る。なお、検索部１０２は、上記のように外部装置を利用して文書を得ることに限らず、内部に検索機能を備えるようにしてもよい。例えば、検索部１０２は、Ｗｅｂ検索ＡＰＩを使用してスニペットを得ることとしてもよい。
【００４２】
本実施形態では、検索部１０２は、ＣＰＵ ５０１及びＮＩＣ ５０４が協働して、検索部１０２として機能する。
【００４３】
セグメント取得部１０３は、得られたスニペットを所定のセグメント区切文字列で区切ることにより、シード文字列の前後に出現する文字列と、シード文字列とを出現順に並べた文字列からなるセグメントを得る。スニペットは、検索語が含まれるページにおいて当該検索語がどのように用いられているかがユーザにとって一目で分かるように、所定の区切文字列で区切られているのが一般的である。例えば、所定のセグメント区切文字列を“・・・”とする。例えば、セグメント取得部１０３は、得られたスニペット１、２、３〜３００をＵｎｉｃｏｄｅのＮＦＫＣにより正規化して、小文字に統一し、セグメント区切文字列“・・・”によって複数の文字列に分割する。そして、セグメント取得部１０３は、分割された文字列のうち重複している文字列は除外し、残りの文字列をセグメントとして得る。得られたスニペットを小文字に統一することにより、例えば、型番等の文字列が大文字・小文字で統一されていない場合に対応することができる。図５に、セグメント取得部１０３がスニペット１から得たセグメント１−１〜１−３を示す。
【００４４】
なお、セグメント区切文字列は、“・・・”の文字列に限らない。検索部１０２が使用する検索エンジン又はＷｅｂ検索ＡＰＩが提示するスニペットが、例えば、“−−−”や“＃＃”の文字列で区切られている場合、セグメント区切文字列を“−−−”や“＃＃”の文字列とする。また、セグメントを得る手法は、セグメント区切文字列を用いてセグメントを得る手法に限らない。セグメントは、使用する検索エンジン又はＷｅｂ検索ＡＰＩが提示するスニペットに応じて、適宜取得される。例えば、１つのスニペットが、“・・・”等の記号により区切られずに提示される場合は、当該スニペットを１つのセグメントとする。また、予め、スニペット内のセグメントに相当する部分が箇条書き等で提示される場合は、箇条書きの１行に該当する部分を１つのセグメントとする。
【００４５】
本実施形態では、ＣＰＵ ５０１がセグメント取得部１０３として機能する。
【００４６】
セグメント要素取得部１０４は、得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることによりセグメント要素を得る。例えば、所定のセグメント要素区切文字列とは、句読点や記号（“、”、“，”、“。”、“！”、“［”、“］”等）であり、これらのセグメント要素区切文字列によりセグメントを区切り、セグメント要素を得る。例えば、セグメント要素取得部１０４は、図５のセグメント１−１、１−２、１−３をセグメント要素区切文字列で区切ると、図６のセグメント要素群１−１Ｐ（セグメント要素Ｐｉ（ｉ＝１〜５））、１−２Ｐ（セグメント要素Ｐｉ（ｉ＝１〜１２））、１−３Ｐ（セグメント要素Ｐｉ（ｉ＝１〜５））を得る。
【００４７】
本実施形態では、ＣＰＵ ５０１がセグメント要素取得部１０４として機能する。
【００４８】
セグメントスコア計算部１０５は、得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算する。ここで、得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、セグメントスコアならびに後述のセグメント要素スコアは、当該セグメントに含まれるセグメント要素がインスタンスの候補として選択部１０７により選択されることがないような値となるとする。本実施形態では、セグメント要素の長さを、Ｕｎｉｃｏｄｅの文字数で定義するが、これに限られない。例えば、セグメント要素の長さとして、その他の文字コードにおけるバイト数を採用することも可能である。
【００４９】
例えば、図５に示すように、セグメント１−１、１−３は、通常の文を含んでいるが、セグメント１−２は、通常の文を含んでいない。そして、セグメント１−１、１−３に含まれるセグメント要素の長さのばらつきは、セグメント１−２に含まれるセグメント要素の長さのばらつきよりも大きい。すなわち、通常の文を含んでいるセグメントは、一般的に、通常の文を含んでいないセグメントよりも、セグメントに含まれる各セグメント要素の長さが揃っていないという傾向がある。そして、通常の文を含むセグメントには、シード文字列と同じ意味範囲に属するインスタンスが含まれていないことが多いので、インスタンスの候補を得るセグメントとして適当ではない。したがって、以下では、セグメント要素の長さの標準偏差が所定の閾値を越えるセグメントは、インスタンスの候補を得るセグメントから除外することとする。
【００５０】
本実施形態では、所定の閾値を５．００とする。また、セグメントスコア計算部１０５は、セグメント要素の長さの標準偏差が５．００未満の場合は、標準偏差の値そのものを、セグメントスコアとし、標準偏差が５．００以上の場合は、セグメントスコアを５．００とする。
【００５１】
図７に、セグメントスコア計算部１０５が計算したセグメントスコアを示す。図７のテーブルには、シード文字列をクエリとして得た「スニペット７０１ａ」と、スニペット７０１ａに含まれる「セグメント７０２ａ」と、セグメント７０２ａに含まれる「セグメント要素７０３ａ」と、セグメント要素７０３ａの「長さ７０４ａ」と、長さ７０４ａの「標準偏差７０５ａ」と、標準偏差７０５ａに基づいて計算される「セグメントスコア７０６ａ」と、後述するセグメント要素スコア計算部１０６により計算される「セグメント要素スコア７０７ａ」と、が対応づけて記載されている。
【００５２】
例えば、セグメントスコア計算部１０５は、図７の７０４ａに示すように、セグメント１−１に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）、セグメント１−２に含まれるセグメント要素Ｐｉ（ｉ＝１〜１２）、及び、セグメント１−３に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さを求める。そして、セグメントスコア計算部１０５は、図７の７０５ａに示すように、セグメント１−１に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さの標準偏差を“５．８９”、セグメント１−２に含まれるセグメント要素Ｐｉ（ｉ＝１〜１２）の長さの標準偏差を“１．３４”、セグメント１−３に含まれるセグメント要素Ｐｉ（ｉ＝１〜５）の長さの標準偏差を“５．２７”と求める。したがって、セグメントスコア計算部１０５は、図７の７０６ａに示すように、セグメント１−１のセグメントスコアを“５．００”、セグメント１−２のセグメントスコアを“１．３４”、セグメント１−３のセグメントスコアを“５．００”と求める。
【００５３】
本実施形態では、ＣＰＵ ５０１がセグメントスコア計算部１０５として機能する。
【００５４】
セグメント要素スコア計算部１０６は、得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算する。
【００５５】
例えば、前述のように、セグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、セグメント要素スコアを、セグメント要素がインスタンスの候補として選択部１０７により選択されないような値になるとする。例えば、セグメント要素スコア計算部１０６は、セグメントスコアが“５．００”の場合は、セグメント要素スコアを“０”とする。一方、セグメントスコアが“５．００”未満の場合は、セグメント要素スコア計算部１０６は、セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離に基づいてセグメント要素スコアを計算する。ここで、セグメントにおいてシード文字列が出現する位置ｓｊ（ｊ：シード文字列の数）、及びセグメントにおいてセグメント要素が出現する位置ｐｉとは、図６に示すように、セグメントにおいて出現順にセグメント要素を並べた時のセグメント内での出現順位であり、距離とは位置ｓｊと位置ｐｉとの出現順位の差である。すなわち、シード文字列が“中華鍋”及び“圧力鍋”とすると、セグメント１−２においてシード文字列“中華鍋”（Ｐ８）が出現する位置ｓ１は“８”番目であり、シード文字列“圧力鍋”（Ｐ４）が出現する位置ｓ２は“４”番目である。また、セグメント１−２においてセグメント要素“親子鍋”（Ｐ５）が出現する位置ｐ５は“５”番目であり、シード文字列“中華鍋”（Ｐ８）とセグメント要素“親子鍋”（Ｐ５）との距離は３となる。
【００５６】
そして、セグメント要素スコア計算部１０６は、セグメント要素スコアＳｉを、セグメントにおいてシード文字列が出現する位置ｓｊと、セグメントにおいてセグメント要素が出現する位置ｐｉとから、以下の式（数１）に基づいて計算する。この式（数１）によれば、最も近いシード文字列との距離に従い指数的に減衰するスコアが、各セグメント要素のセグメント要素スコアとされる。本実施形態ではα＝０．８とする。計算結果を図７のセグメント要素スコア７０７ａに示す。
【００５７】
【数１】
上記においては、最も近いシード文字列との距離に従い指数的に減衰するスコアを求めることとしたが、スコアの求め方には様々な変形が可能である。例えば、シード文字列が複数存在する場合に、各シード文字列とセグメント要素との距離をそれぞれ求め、求めた距離の平均値に従い線形的に減衰するスコアを各セグメント要素のセグメント要素スコアとしてもよい。
以上、セグメント内にシード文字列が出現する場合の一例を記載したが、シード文字列の類似語が出現する場合も同様に計算できる。具体的には、“中華鍋”及び“圧力鍋”をシード文字列とした場合に、検索部ではシード文字列に加えてシード文字列の類似語で検索を行うと、“中華なべ”や“圧力なべ”といったシード文字列の類似語が含まれるスニペットが得られる。このような場合には、セグメント要素スコア計算部１０６において、公知の漢字かな文字変換プログラム等を用いることで、シード文字列の類似語をシード文字列として同様に取り扱うことができる。このように、シード文字列の類似語がセグメント内に出現した場合であっても、数１に従ってセグメント要素スコアＳｉを計算できる。
【００５８】
本実施形態では、ＣＰＵ ５０１がセグメント要素スコア計算部１０６として機能する。
【００５９】
選択部１０７は、得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する。ここで、拡張集合とは、集合拡張処理を施した後に得られる集合であり、シード文字列と意味的に同一のカテゴリに含まれる語の集合である。例えば、選択部１０７は、セグメント要素スコアの値が“０．１０”未満のセグメント要素をインスタンスの候補から除外し、残りのセグメント要素をインスタンスの候補として選択する。すなわち、選択部１０７は、セグメント１−１、１−３から得たセグメント要素のセグメント要素スコアがすべて“０”なので（図７）、セグメント１−１、１−３から得たセグメント要素を候補から除外する。そして、選択部１０７は、図８に示すように、セグメント１−２から得たセグメント要素のうち、セグメント要素スコアが“０．１０”未満の“パスタマシーン”、“その他”、及び、“さらに価格が”のセグメント要素を除外し、残りのセグメント要素を、“中華鍋”及び“圧力鍋”と意味的に同一のカテゴリに含まれるインスタンスの候補として選択する。なお、本実施形態では、１つのスニペットを例に、インスタンスの候補を選択する手法について説明したが、実際には多数のスニペットからセグメント要素を得てセグメント要素スコアを求め、インスタンスの候補を選択する。この場合、同じセグメント要素に、異なるスニペットからそれぞれセグメント要素スコアが求められることがある。特に、シード文字列と意味的に同じカテゴリに含まれるセグメント要素は、複数のスニペットに含まれることが多いと考えられるので、複数のセグメント要素スコアが得られる可能性が高い。したがって、複数のセグメント要素スコアが得られた場合、それらの和や最大値等を当該セグメント要素のセグメント要素スコアの値とする。このように処理することにより、より適当なインスタンスの候補を選択することができる。
【００６０】
本実施形態では、ＣＰＵ ５０１が選択部１０７として機能する。
【００６１】
（３．実施形態１の集合拡張処理装置の動作）
次に、本実施形態の集合拡張処理装置１００の各部が行う動作について図９のフローチャートを用いて説明する。集合拡張処理装置１００に電源が入れられ、所定の操作が行われると、ＣＰＵ ５０１は図９のフローチャートに示す集合拡張処理を開始する。
【００６２】
まず、受付部１０１は、シード文字列を受け付ける（ステップＳ１０１）。例えば、受付部１０１は、図４に示すように、ＷＥＢページの検索エンジンの検索欄６０１にクエリとして入力された“中華鍋”及び“圧力鍋”を、シード文字列として受け付ける。
【００６３】
次に、検索部１０２は、受け付けられたシード文字列を含む文書を検索し、スニペットを得る（ステップＳ１０２）。例えば、検索部１０２は、シード文字列“中華鍋”及び“圧力鍋”をクエリとして検索し、図４に示すように、検索結果の上位３００件のスニペット１、２、３〜３００を得る。なお、検索部１０２が得るスニペットの数は、任意であるが、およそ１００件以上のスニペットを得ることにより、より適当なインスタンスの候補を選択することができる。
【００６４】
次に、セグメント取得部１０３は、検索部１０２が得たスニペットを、セグメント区切文字列で区切ることによりセグメントを得る（ステップＳ１０３）。例えば、セグメント取得部１０３は、スニペット１、２、３〜３００をセグメント区切文字列“・・・”で区切り、セグメントを得る。例えば、セグメント取得部１０３は、スニペット１から、図５に示すように、セグメント１−１〜１−３を得る。
【００６５】
セグメントが得られると（ステップＳ１０３）、セグメント要素取得部１０４は、当該セグメントを所定のセグメント要素区切文字列で区切ることによりセグメント要素を得る（ステップＳ１０４）。例えば、セグメント１−１〜１−３を、セグメント要素区切文字列（“、”、“，”、“。”、“！”、“［”、“］”等）で区切り、図６のセグメント要素（セグメント要素群１−１Ｐ、１−２Ｐ、１−３Ｐ）を得る。
【００６６】
セグメント要素が得られると（ステップＳ１０４）、セグメントスコア計算部１０５は、当該セグメントのそれぞれのセグメントスコアをセグメントが含むセグメント要素の長さの標準偏差に基づいて計算する（ステップＳ１０５）。例えば、セグメントスコア計算部１０５は、セグメント要素の長さの標準偏差が５．００未満の場合は、標準偏差の値そのものをセグメントスコアとし、セグメント要素の長さの標準偏差が５．００以上の場合は、セグメントスコアを５．００とする。すなわち、セグメントスコア計算部１０５は、標準偏差が“５．８９”のセグメント１−１のセグメントスコアを“５．００”、標準偏差が“１．３４”のセグメント１−２のセグメントスコアを“１．３４”、標準偏差が“５．２７”のセグメント１−３のセグメントスコアを“５．００”と求める。
【００６７】
次に、セグメント要素スコア計算部１０６は、セグメント要素のセグメント要素スコアを、セグメントにおいて受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算する（ステップＳ１０６）。例えば、セグメント要素スコア計算部１０６は、セグメントスコアが“５．００”の場合は、セグメント要素スコアを“０”とし、セグメントスコアが“５．００”未満の場合は、セグメントにおいてシード文字列が出現する位置とセグメント要素が出現する位置との距離を用いた式（数１）に基づいて、セグメント要素スコア７０７ａ（図７）を計算する。
【００６８】
そして、選択部１０７は、得られたセグメント要素についてのセグメント要素スコアに基づいて、シード文字列と意味的に同一のカテゴリに属するインスタンスの候補を選択する（ステップＳ１０７）。例えば、選択部１０７は、図８に示すように、セグメント要素スコアの値が“０．１０”以上のセグメント要素をインスタンスの候補として選択する。
【００６９】
本実施形態によれば、“親子鍋”や“タジン鍋”は、シード文字列の“中華鍋”や“圧力鍋”と同じ“鍋”のカテゴリに含まれる用語であるので、意味的に同一のカテゴリに属する語の候補を選択することができる。
【００７０】
（４．実施形態２の集合拡張処理装置の概要構成）
実施形態２の集合拡張処理装置１００は、拡張集合に含まれるインスタンスの候補について、文脈に基づいてフィルタをかけることにより、意味的に無関係な語を排除するものである。
【００７１】
本実施形態に係る集合拡張処理装置１００は、図１０に示すように、受付部１０１と、検索部１０２と、セグメント取得部１０３と、セグメント要素取得部１０４と、セグメントスコア計算部１０５と、セグメント要素スコア計算部１０６と、選択部１０７と、抽出部１０８と、から構成される。本実施形態の受付部１０１、検索部１０２、セグメント取得部１０３、セグメント要素取得部１０４、セグメントスコア計算部１０５、セグメント要素スコア計算部１０６、及び、選択部１０７は、実施形態１と同様の機能を有する。以下、異なる機能を有する抽出部１０８について説明する。
【００７２】
まず、インスタンスの候補は、シード文字列の前後の文脈とインスタンスの候補の前後の文脈とが類似するほど、シード文字列と意味的に類似していると考えられる。そこで、実施形態２の集合拡張処理装置１００は、シード文字列の前後の文脈とインスタンスの候補の前後の文脈とに基づいてシード文字列とインスタンスの候補との類似度を求め、当該類似度に基づき、インスタンスの候補の中からインスタンスを抽出する。これにより、意味的に無関係な語を排除することができる。以下、集合拡張装置１００は、ｇ−Ｍｏｎａｋａアルゴリズムに基づいて計算した類似度から、インスタンスの候補をランク付けし、所定の値以上の類似度を有するものをインスタンスとして抽出する。なお、類似度を求める手法はｇ−Ｍｏｎａｋａアルゴリズムに限らない。例えば、ｇ−Ｅｓｐｒｅｓｓｏアルゴリズムを用いてもよい。
【００７３】
抽出部１０８は、インスタンスの候補を用いて検索することにより得られたスニペットから、抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成する。そして、抽出部１０８は、当該接続グラフにおける、受け付けられたシード文字列の前後の文脈とインスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスとの類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する。以下、ｇ−Ｍｏｎａｋａアルゴリズムに基づく類似度の計算手法を詳細に説明する。
【００７４】
抽出部１０８は、選択部１０７が選択したインスタンスの候補のそれぞれを、ＷＥＢページの検索エンジンに対してクエリとして入力し、検索結果の上位３００件のスニペットのリストを得る。そして、抽出部１０８は、得られたスニペットに対して、ＵｎｉｃｏｄｅのＮＦＫＣにより正規化して、小文字に統一し、重複を取り除く。また、日本語の割合が極端に少ない、記号が多いなど、スニペットとして適当でないものを除外する。
【００７５】
次に、抽出部１０８は、残ったスニペットの集合に含まれるすべての文字ｎグラムについて、接続行列Ｍ（ｕ，ｖ）を構築する。接続行列Ｍ（ｕ，ｖ）は、式（数２）で表される。
【００７６】
【数２】
【００７７】
ここで、｜ｕ，ｖ｜は、ｎグラムｕの後にｎグラムｖが続く頻度であり、｜ｕ，＊｜、｜＊，ｖ｜はそれぞれ、ｎグラムｕ、ｎグラムｖそのものの出現頻度である。本実施形態では、｜ｕ，ｖ｜、｜ｕ，＊｜、｜＊，ｖ｜は、それら自体をクエリとして検索した場合の検索結果数であり、ｐｍｉ（ｕ，ｖ）は、それらの検索結果数の自然対数をとったものを用いている。
【００７８】
次に、抽出部１０８は、全てのｎグラムの集合Ｖを節点集合とし、Ｍを接続行列として表現される有向重み付きグラフ（以下、「接続グラフ」という）ＧＭを生成する。生成した接続グラフＧＭの例を図１１に示す。このグラフにおいて、ｎグラムｕ及びｎグラムｖのそれぞれの右側文脈及び左側文脈が類似しているほど、それらの意味は類似しているとみなすことができる。
【００７９】
ここで、まず、ｎグラムｕの右側文脈とｎグラムｖの右側文脈とが類似しているか否かは、引用解析手法の書誌結合の概念に対応付けて考えることができる。書誌結合とは、文献ｘ、ｙが同じ文献を引用することをいう。すなわち、書誌結合は、ｎグラムｕとｎグラムｖが同じｎグラムに接続しているか否かということに対応付けて考えることができる。一方、ｎグラムｕの左側文脈とｎグラムｖの左側文脈とが類似しているか否かは、引用解析手法の共引用の概念に対応付けて考えることができる。共引用とは、文献ｘ、ｙが同じ文献により引用されることをいう。すなわち、ｎグラムｕとｎグラムｖが同じｎグラムから接続されているか否かということに対応付けて考えることができる。
【００８０】
したがって、ｎグラムｕ及びｎグラムｖの右側文脈及び左側文脈が類似しているか否かを示す類似度行列ＡＲ、ＡＬを、書誌結合行列及び共引用行列にそれぞれ対応させて求めることとする。右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬは、接続行列Ｍを用いて、式（数３）で表すことができる。
【００８１】
【数３】
【００８２】
抽出部１０８は、全てのｎグラムについて右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬを求める。
【００８３】
また、ｎグラムｕとｎグラムｖとが意味的に類似しているとみなすためには、右側文脈及び左側文脈の両者が類似している必要がある（以下、「両側近接制約」という）。そこで、抽出部１０８は、式（数４）に示すように、要素毎の重み付き一般化平均によって、ｎグラムｕとｎグラムｖとの類似度を示す類似度行列Ａを求める。ここで、ｍは、この両側近接制約の強さを調節するパラメータであり、本実施形態では、ｍ＝０．１とする。
【００８４】
【数４】
【００８５】
そして、抽出部１０８は、この類似度行列Ａを用いてラプラシアンカーネルＲβ（Ａ）を、数５、数６の式から求める。
【００８６】
【数５】
【００８７】
【数６】
【００８８】
Ｒβ（Ａ）の（ｉ，ｊ）要素が、ｎグラムｉとｎグラムｊとの類似度に対応する。そこで、抽出部１０８は、シードベクトルｖ０（シード文字列に対応する要素が１、それ以外が０となっているようなベクトル）を用いて、Ｒβ（Ａ）ｖ０計算し、計算された値を類似度とする。βの値は、任意であり、例えば、１．０−２である。
【００８９】
例えば、図１１の接続グラフＧＭにおいて、“中華鍋”は“の”に接続し、“調理はさみ”、“タジン鍋”は両者とも“の”に接続している。また、“中華鍋”に接続する“の”は、“タジン鍋”に接続しているが、“調理はさみ”には接続していない。このような場合において、“調理はさみ”の“中華鍋”に対する類似度Ｒβ（Ａ）ｖ０は、“タジン鍋”の“中華鍋”に対する類似度Ｒβ（Ａ）ｖ０よりも小さい値となる。
【００９０】
抽出部１０８は、例えば、計算した類似度が所定の値を超えたものを、インスタンスとして抽出する。例えば、図１２に示すように類似度が求められ、所定の値を“０．１０”とすると、抽出部１０８は、“圧力鍋”、“中華鍋”、“親子鍋”、“タジン鍋”、“伊賀焼”を、インスタンスとして抽出する。
【００９１】
本実施形態では、ＣＰＵ ５０１が抽出部１０８として機能する。
【００９２】
（５．実施形態２の集合拡張処理装置の動作）
次に、本実施形態の集合拡張処理装置１００の各部が行う動作について図１３のフローチャートを用いて説明する。集合拡張処理装置１００に電源が入れられ、所定の操作が行われると、ＣＰＵ ５０１は図１３のフローチャートに示す集合拡張処理を開始する。なお、図１３のフローチャートにおいて、図９のフローチャートと同じステップ番号が付されているステップは、図９のフローチャートにおける処理と同様の処理を行う。したがって、これらの説明は省略する。
【００９３】
選択部１０７によりインスタンスの候補が選択されると（ステップＳ１０７）、抽出部１０８は、インスタンスの候補を用いて検索エンジンで検索することによりスニペットを取得する（ステップＳ２０８）。例えば、抽出部１０８は、インスタンスの候補をクエリとしてＷＥＢページの検索エンジンに入力し、検索結果の上位３００件のスニペットのリストを得る。
【００９４】
次に、抽出部１０８は得られたスニペットからインスタンスの候補を含むｎグラムの接続グラフを生成する（ステップＳ２０９）。例えば、抽出部１０８は、３００件のスニペットから、不適当なものを除外し、残ったスニペットの集合に含まれるすべての文字のｎグラムについて、接続行列Ｍを求める。そして、図１１に示すように、すべてのｎグラムの集合Ｖを節点集合とし、Ｍ（数２）を接続行列として表現される接続グラフＧＭを生成する。
【００９５】
抽出部１０８は、接続グラフにおける、シード文字列の前後の文脈と、インスタンスの候補の前後の文脈とに基づいて、シード文字列とインスタンスの候補との類似度を計算する（ステップＳ２１０）。例えば、抽出部１０８は、式（数３）に基づいて、右側文脈の類似度行列ＡＲ、及び、左側文脈の類似度行列ＡＬを求め、式（数４）に示すように、要素毎に重み付き一般化平均を行った類似度行列Ａを求める。さらに、式（数５、６）に基づいて、類似度行列Ａを用いたラプラシアンカーネルＲβ（Ａ）を求め、シードベクトルｖ０を乗じることにより、シード文字列に対するインスタンスの候補の類似度を求める。
【００９６】
抽出部１０８は、類似度に基づいてインスタンスを抽出する（ステップＳ２１１）。例えば、抽出部１０８は、計算した類似度が“０．１０”を超えたものを、図１２に示すように、インスタンスとして抽出する。また、あるいは、抽出部１０８は、類似度の高いものから所定の個数だけ抽出することとしてもよい。例えば、インスタンスの候補が図１２に示すように９個有る場合、所定の個数を４個とすると、抽出部１０８は、類似度において上位４個の“圧力鍋”、“中華鍋”、“親子鍋”、及び、“タジン鍋”をインスタンスとして抽出する。
【００９７】
本実施形態によれば、意味的に無関係な語を排除することができ、意味的に同一のカテゴリに含まれるとみなすのにより適当な用語を抽出することができる。
【００９８】
なお、実施形態１、２では、集合拡張処理装置１００は、ショッピングサイトの商品のカテゴリ生成に適用する例を示したが、これに限らない。例えば、固有表現獲得や辞書構築等に応用可能である。
【産業上の利用可能性】
【００９９】
本発明によれば、意味的に同一のカテゴリに属する語の候補を選択するのに好適な集合拡張処理装置、集合拡張処理方法、プログラム、及び、記録媒体を提供することができる。
【符号の説明】
【０１００】
１００ 集合拡張処理装置
１０１ 受付部
１０２ 検索部
１０３ セグメント取得部
１０４ セグメント要素取得部
１０５ セグメントスコア計算部
１０６ セグメント要素スコア計算部
１０７ 選択部
１０８ 抽出部
２００ ショッピングサーバ
３００ インターネット
４０１、４０２〜４０ｎ 端末装置
５００ 情報処理装置
５０１ ＣＰＵ
５０２ ＲＯＭ
５０３ ＲＡＭ
５０４ ＮＩＣ
５０５ 画像処理部
５０６ 音声処理部
５０７ ＤＶＤ−ＲＯＭドライブ
５０８ インターフェース
５０９ 外部メモリ
５１０ コントローラ
５１１ モニタ
５１２ スピーカ
６０１ 検索欄
６０２ 検索ボタン
【特許請求の範囲】
【請求項１】
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
を備えることを特徴とする集合拡張処理装置。
【請求項２】
請求項１に記載の集合拡張処理装置であって、
前記インスタンスの候補を用いて検索することにより得られたスニペットから、前記抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成し、当該接続グラフにおける前記受け付けられたシード文字列の前後の文脈と当該インスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスの候補との類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する抽出部
をさらに備えることを特徴とする集合拡張処理装置。
【請求項３】
請求項１又は２に記載の集合拡張処理装置であって、
前記得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、前記セグメントスコアならびに前記セグメント要素スコアは、当該セグメントに含まれるセグメント要素が前記インスタンスの候補として前記選択部により選択されることがないような値となる
ことを特徴とする集合拡張処理装置。
【請求項４】
請求項１乃至３のいずれか１項に記載の集合拡張処理装置であって、
前記得られたセグメントのそれぞれに出現するセグメント要素のそれぞれのセグメント要素スコアは、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との最短距離に対して指数的に減衰する
ことを特徴とする集合拡張処理装置。
【請求項５】
受付部と、検索部と、セグメント取得部と、セグメント要素取得部と、セグメントスコア計算部と、セグメント要素スコア計算部と、選択部と、を備える集合拡張処理装置が実行する集合拡張処理方法であって、
前記受付部が、シード文字列を受け付ける受付工程、
前記検索部が、前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索工程、
前記セグメント取得部が、前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得工程、
前記セグメント要素取得部が、前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得工程、
前記セグメントスコア計算部が、前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算工程、
前記セグメント要素スコア計算部が、前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算工程、
前記選択部が、前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択工程、
を備えることを特徴とする集合拡張処理方法。
【請求項６】
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラム。
【請求項７】
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
を備えることを特徴とする集合拡張処理装置。
【請求項２】
請求項１に記載の集合拡張処理装置であって、
前記インスタンスの候補を用いて検索することにより得られたスニペットから、前記抽出されたインスタンスの候補を含むｎグラムの接続グラフを生成し、当該接続グラフにおける前記受け付けられたシード文字列の前後の文脈と当該インスタンスの候補の前後の文脈とに基づいて当該シード文字列と当該インスタンスの候補との類似度を計算し、当該類似度に基づいて、当該インスタンスの候補から、当該シード文字列を含む集合を拡張した拡張集合に含めるべきインスタンスを抽出する抽出部
をさらに備えることを特徴とする集合拡張処理装置。
【請求項３】
請求項１又は２に記載の集合拡張処理装置であって、
前記得られたセグメントのそれぞれについて、当該セグメントに出現するセグメント要素のそれぞれの長さの標準偏差が所定の閾値を超える場合、前記セグメントスコアならびに前記セグメント要素スコアは、当該セグメントに含まれるセグメント要素が前記インスタンスの候補として前記選択部により選択されることがないような値となる
ことを特徴とする集合拡張処理装置。
【請求項４】
請求項１乃至３のいずれか１項に記載の集合拡張処理装置であって、
前記得られたセグメントのそれぞれに出現するセグメント要素のそれぞれのセグメント要素スコアは、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との最短距離に対して指数的に減衰する
ことを特徴とする集合拡張処理装置。
【請求項５】
受付部と、検索部と、セグメント取得部と、セグメント要素取得部と、セグメントスコア計算部と、セグメント要素スコア計算部と、選択部と、を備える集合拡張処理装置が実行する集合拡張処理方法であって、
前記受付部が、シード文字列を受け付ける受付工程、
前記検索部が、前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索工程、
前記セグメント取得部が、前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得工程、
前記セグメント要素取得部が、前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得工程、
前記セグメントスコア計算部が、前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算工程、
前記セグメント要素スコア計算部が、前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算工程、
前記選択部が、前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択工程、
を備えることを特徴とする集合拡張処理方法。
【請求項６】
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラム。
【請求項７】
コンピュータを、
シード文字列を受け付ける受付部、
前記受け付けられたシード文字列を含む文書を検索して、当該検索された文書のスニペットを得る検索部、
前記得られたスニペットを所定のセグメント区切文字列で区切ることにより、前記受け付けられたシード文字列の前後に出現する文字列と、当該シード文字列とを出現順に並べた文字列からなるセグメントを得るセグメント取得部、
前記得られたセグメントのそれぞれを、所定のセグメント要素区切文字列で区切ることにより、セグメント要素を得るセグメント要素取得部、
前記得られたセグメントのそれぞれのセグメントスコアを、当該セグメントに出現するセグメント要素のそれぞれの長さの分散もしくは標準偏差に基づいて計算するセグメントスコア計算部、
前記得られたセグメントのそれぞれに含まれるセグメント要素のそれぞれのセグメント要素スコアを、当該セグメントにおいて前記受け付けられたシード文字列が出現する位置と当該セグメントにおいて当該セグメント要素が出現する位置との距離、ならびに、当該セグメントについて計算されたセグメントスコアに基づいて計算するセグメント要素スコア計算部、
前記得られたセグメント要素のそれぞれについて計算されたセグメント要素スコアに基づいて、当該セグメント要素からいずれかを、前記受け付けられたシード文字列を含む集合を拡張した拡張集合に含まれるインスタンスの候補として選択する選択部、
として機能させることを特徴とするプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１８５６６６（Ｐ２０１２−１８５６６６Ａ）
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願番号】特願２０１１−４８１２４（Ｐ２０１１−４８１２４）
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（３９９０３７４０５）楽天株式会社 (416)
【Ｆターム（参考）】
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（３９９０３７４０５）楽天株式会社 (416)
【Ｆターム（参考）】
[ Back to top ]