(57)【要約】【課題】距離空間の次元数が大きい情報探索集合に対しても、少ない探索コストで、効率的に情報を探索することを目的とする。【解決手段】任意の２つの要素間を、直接的、または、間接的にリンク結合することにより、１コンポーネントの近傍要素ネットワークを生成し、クエリが入力されると、最近傍要素ネットワークΓ（ｘ０）のうち、クエリとの類似度が最も大きい要素を要素ｘ１として選択し、要素ｘ１とクエリとの類似度が、所定の設定類似度よりも大きいならば、当該類似度を新たな設定類似度として更新し、要素ｘ１に対する最近傍要素ネットワークΓ（ｘ１）の要素のうち、過去に要素ｘ１になったことのない要素であり、かつ、クエリとの類似度が最も大きい要素を選択し、新たな要素ｘ１とし、当該新たな要素ｘ１に対して、同様の処理を行うことにより、クエリと類似した要素を探索することを特徴とする。【選択図】図５
2008293444.tif 000002
【特許請求の範囲】
【請求項１】
記憶部に保持されている情報探索集合からクエリと類似した情報を探索する情報探索装置における情報探索方法であって、
前記情報探索方法は、ネットワーク生成処理と、情報探索処理とを含んでなり、
前記ネットワーク生成処理は、
前記情報探索装置のネットワーク生成部が、
前記情報探索集合における任意の２つの要素間を、直接的、または、前記２つの要素以外の要素を介して間接的にリンク結合することにより、１コンポーネントのネットワークを生成し、前記記憶部に保持させ、
前記情報探索処理は、
前記情報探索装置の探索処理部が、
（ａ１）前記ネットワークの所定の第1の要素に直接的にリンク結合された要素を、前記記憶部から取得し、当該要素のうち、前記クエリとの類似度が最も大きい要素を第２の要素として選択し、
（ａ２）当該第２の要素と前記クエリとの類似度が、前記記憶部に保持されている所定の設定類似度よりも大きいならば、前記第２の要素と前記クエリとの類似度を新たな設定類似度として、前記記憶部に保持し、
（ａ３）前記第２の要素を第３の要素とし、当該第３の要素に直接的にリンク結合された要素を、前記記憶部から取得し、
（ａ４）前記第３の要素に直接的にリンク結合された要素のうち、過去に前記第２の要素になったことのない要素であり、かつ、前記クエリとの類似度が最も大きい要素を選択し、新たな第２の要素とし、当該新たな第２の要素に対して、前記（ａ２）の処理を行うことにより、前記クエリと類似した要素を探索する情報探索処理と、
を実行することを特徴とする情報探索方法。
【請求項２】
前記ネットワーク生成処理は
前記ネットワーク生成部が、
前記情報探索集合における任意の要素である要素ｘと、前記要素ｘ以外の要素それぞれとの類似度を算出し、
前記要素ｘ以外の要素のうち、前記要素ｘとの前記類似度が大きい順に、予め設定された所定数の要素を取得し、当該取得した要素と、前記要素ｘとの間をリンク結合することによって、前記要素ｘに対する最近傍要素ネットワークΓ（ｘ）を生成する処理を、前記情報探索集合におけるすべての要素に対して行うことを特徴とする請求項１に記載の情報探索方法。
【請求項３】
前記情報探索処理は、
前記探索処理部が、
前記情報探索集合における任意の要素である要素ｘ０に対する前記最近傍要素ネットワークΓ（ｘ０）と、任意の要素であるｘｍａｘとを前記記憶部から取得し、
前記入力部を介して、前記クエリｑが入力されると、
（ｂ１）Ａ＝Γ（ｘ０）∪｛ｘ０｝，Ｂ＝｛ｘ０｝である集合Ａおよび集合Ｂを算出し、
（ｂ２）次の式（８）を満たす要素ｘ１を、集合Ａ−Ｂから取得し、
【数１】
2008293444.tif 000010
ただし、ρ（ａ，ｂ）は、前記情報探索集合内の要素であるａと、ｂとの類似度、｜Ａ｜は、集合Ａにおける要素数、Ａ―Ｂは、要素Ａと要素Ｂとの差集合、Γ（ａ）は、要素ａに対する最近傍要素ネットワーク
（ｂ３）ρ（ｘ１，ｑ）＞ρ（ｘｍａｘ，ｑ）であれば、要素ｘ１を新たな要素ｘｍａｘとし、
（ｂ４）ＡにＡ∪Γ（ｘ１）を代入し、ＢにＢ∪｛ｘ１｝を代入し、
（ｂ５）前記（ｂ２）〜（ｂ４）の処理を繰り返し、
｜Ａ｜が所定の値βを超える、または、前記クエリと前記要素ｘ１とが一致するとき、要素ｘｍａｘを最終出力要素として出力する
ことを特徴とする請求項２に記載の情報探索方法。
【請求項４】
請求項１から請求項３のいずれか一項に記載の情報探索方法を、コンピュータに実行させることを特徴とする情報探索プログラム。
【請求項５】
記憶部に保持されている情報探索集合からクエリと類似した情報を探索する情報探索装置であって、
前記情報探索装置は、ネットワーク生成部と、探索処理部とを有してなり、
前記ネットワーク生成部は、
前記情報探索集合における任意の２つの要素間を、直接的、または、前記２つの要素以外の要素を介して間接的にリンク結合することにより、１コンポーネントのネットワークを生成し、前記記憶部に保持させる機能を有し、
前記探索処理部は、
（ａ１）前記ネットワークの所定の第1の要素に直接的にリンク結合された要素を、前記記憶部から取得し、当該要素のうち、前記クエリとの類似度が最も大きい要素を第２の要素として選択し、
（ａ２）当該第２の要素と前記クエリとの類似度が、前記記憶部に保持されている所定の設定類似度よりも大きいならば、前記第２の要素と前記クエリとの類似度を新たな設定類似度として、前記記憶部に保持し、
（ａ３）前記第２の要素を第３の要素とし、当該第３の要素に直接的にリンク結合された要素を、前記記憶部から取得し、
（ａ４）前記第３の要素に直接的にリンク結合された要素のうち、過去に前記第２の要素になったことのない要素であり、かつ、前記クエリとの類似度が最も大きい要素を選択し、新たな第２の要素とし、当該新たな第２の要素に対して、前記（ａ２）の処理を行うことにより、前記クエリと類似した要素を探索する機能を有することを特徴とする情報探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報探索方法、情報探索プログラムおよび情報探索装置に関する。
【背景技術】
【０００２】
情報である要素の間の関係が距離、非類似度または類似度により定義される集合を情報空間Ωとする。情報空間Ωの任意の２つの要素ｘ，ｙ∈Ωの距離を距離関数ｄ（ｘ，ｙ）により定義する。情報空間Ωにおける距離関数は、次の式を充足する。
ｄ（ｘ，ｙ）≧０・・・式（１）
ｄ（ｘ，ｙ）＝ｄ（ｙ，ｘ）・・・式（２）
ｄ（ｘ，ｙ）＝０  ｉｆ  ｘ＝ｙ・・・式（３）
式（１）を非負数条件、式（２）を対称性条件という。情報空間の部分集合でもある情報探索集合（被探索集合、探索対象集合とも呼ぶ。）Ｘ⊂Ωにおいて、当該情報空間の要素であるクエリｑ∈Ωと最も距離の小さい要素の集合Ｒ（ｑ）⊂Ｘは、式（４）により表される。
【０００３】
【数２】
2008293444.tif 000003
【０００４】
情報空間のうち要素間の距離が、非負数条件および対称条件に加えて、次の式（５）および式（６）を充足するものを距離空間Ωｄとする。
ｄ（ｘ，ｙ）＝０  ｉｆｆ  ｘ＝ｙ・・・式（５）
ｄ（ｘ，ｙ）＋ｄ（ｙ，ｚ）≧ｄ（ｘ，ｙ）・・・式（６）
式（５）を反射条件とよび、式（６）を三角不等式とよぶ。
【０００５】
従来、距離空間の要素（情報）であるクエリに類似する要素を情報探索集合から、入力されたクエリに類似する情報を探索する情報探索方法として、ＴＬＡＥＳＡ（Tree Linear Approximating and Eliminating Search Algorithm）がある（例えば、非特許文献１）。ＴＬＡＥＳＡは、クエリが入力される前の事前処理と、クエリが入力された後の事後処理とを行うことで、情報の探索を行う。事前処理は、情報探索集合（被探索集合）における複数の要素（ベースプロトタイプと呼ぶ）を選択し、それらと他の全て要素との距離を算出する工程と、情報探索集合の全ての要素からなる二分木を構築する工程とから成る。事後処理は、クエリが入力された直後に、当該クエリと、選択されたベースプロトタイプとの距離を算出する工程、距離空間の性質の1つである３つの要素間の距離の大小関係を表す三角不等式と二分木とを利用し、探索空間を削減しながら探索する工程とから成る。ＴＬＡＥＳＡは、三角不等式を有効利用し探索空間を削減し、探索コストを低減している。ここで、探索コストとは、情報探索の効率を評価する際に用いられる値であり、クエリと探索対象集合の要素との類似度計算または距離計算の回数である。
【０００６】
このように、三角不等式を用いて、探索空間を削減する情報探索方法としては、ＴＬＡＥＳＡの他に、ＬＡＥＳＡ（Linear Approximationg and Eliminating Search Algorithm：例えば、非特許文献２参照）や、ＡＥＳＡ（Approximating and Eliminating Search Algorithm：例えば、非特許文献３参照）などが提案されている。
【非特許文献１】「A fast branch & bound nearest neighbour classifier in metric space」,Luisa Mico,Jose Oncina, Rafael C. Carrasco, Pattern Recognition Letters vol.17,p.731-p.739 1996年
【非特許文献２】「A new version of the Nearest-Neighbour Approximating and Eliminating Search Algorithm(AESA) with linear preprocessing time and memory requirements」,Luisa Mico,Jose Oncina, Pattern Recognition Letters vol.15,p.9-p.7 1994年1月
【非特許文献３】「An algorithm for finding nearest neighbours in (approximately) constant average time」,E. Vidal Pattern Recognition Letters vol.4,p.145-p.157 1986年7月
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、例えば、入力された文書に類似の文書を文書ファイル群から探索する場合、すなわち、文書を被探索集合とした場合、文書間の関係性を規定する類似度や、距離を算出する際に用いられる文書から抽出される特徴量が高次元になる場合がある。これは、文書の特徴量として、文書中に出現する異なる単語から成る単語ベクトルを用い、その単語ベクトルの1要素を１次元とするため、情報探索集合（探索対象集合または被探索集合とも呼ぶ。）中の全文書ファイルに生じる単語の異なり数だけ次元が生じるためである。
【０００８】
次に、図１７および図１８に沿って、ＴＬＡＥＳＡにおける問題点を説明する。
なお、図１７および図１８における情報探索集合は、１０年分の新聞記事の文書ファイルを要素とする集合である。
ここで、情報探索集合における要素間の距離は、以下の手順で算出される。まず、各文書ファイル中に記載されている文書を形態素解析し、不要なストップワードを削除した上で、単語を文書（文書ファイル）から抽出する。ここで、ストップワードとは、情報探索において、ありふれた単語であるため検索語としては不適切なため、検索語としては無視される語である。日本語では、ひらがなやカタカナの１文字の語などがストップワードとなる。そして、抽出された単語に対し、ｔｆ−ｉｄｆ（term frequency-inverted document frequency）法で各単語に対し、重み付けを行う。この結果、生じる重み付け単語ベクトルを、該文書ファイルの特徴量とする。その上で、情報探索集合の文書ファイルを要素とし、特徴量に対するコサイン距離を用いて、要素間の距離を規定する。単語ベクトルを特徴量とした場合、前記コサイン類似度は、類似または非類似の尺度として広く用いられている。
この例で用いた要素数（文書ファイル数）は、６４５８５個であり、特徴量である重み付け単語ベクトルは、５１０３０次元となった。これは距離空間の次元が５１０３０であるとも言える。
【０００９】
図１７は、この情報探索空間から、無作為に１×１０６個のペア要素（２つの要素）を選択し、このペア要素間の距離の累積分布を示す図である。
図１７において、横軸は、ペア要素間の距離を示し、縦軸は、対応する距離を有するペア要素の全体のペア要素に対する割合の累積値である。
なお、距離は、コサイン距離を用い、かつ情報探索集合内で最も遠い要素間の距離が１．０となるよう規格化されている。
図１７では、距離が０．８以下である要素数は、非常に少なく、１．０付近にほとんどのペア要素が存在することが示されている。詳細には、距離が０．９８以上のペア要素の割合は、全体の９０％であることが示されている（図１７の太線）。
すなわち、図１７から、この１０年分の新聞記事の文書ファイルを要素とする情報探索集合では、各要素間が疎になっていることがわかる。
【００１０】
図１８は、図１７と同様の条件下における距離の下界の累積分布を示す図である。
距離の下界は、図１７と同じペア要素と、ランダムに選択した２００個の要素（ＴＬＡＥＳＡのベースプロトタイプに相当）とを用いて、距離の下界を算出した。
図１８において、横軸は、このような方法で算出した距離の下界の値を示し、縦軸は、距離の下界の値が、算出したすべての距離の下界に対する割合の累積値である。
図１８では、０．４以下に、距離の下界のほとんどが入っていることが示されている。特に、０．１３８以下の距離の下界が、全体の９０％を占めている。探索空間の削減は、情報探索過程のある時点でのクエリとある要素との距離と比較して、距離の下界が大きい要素を探索対象集合、すなわち、クエリとの距離を計算する対象の要素の集合から除くことによりなされる。情報探索過程のある時点でのクエリとある要素との距離が０．９８であったと仮定する。図１８より、距離の下界が０．９８よりも大きい要素はほとんど存在しないので、この時点で削減される要素はほとんどない。このように、要素における特徴量が高次元になる場合、情報探索集合におけるある要素とクエリとの距離を計算し、距離の下界が比較対象の距離より大きい要素を情報探索集合から除き、探索空間を削減する方法は有効に機能しない。
【００１１】
このように、文書ファイルなど距離空間の次元数が大きくなる情報探索集合では、三角不等式から算出される距離の下界を用いた探索空間の削減が有効に機能しない。
すなわち、文書ファイルなど距離空間の次元数が大きくなる情報探索集合に対し、ＴＬＡＥＳＡや、ＬＡＥＳＡや、ＡＥＳＡなどを適用しても、探索空間の削減がほとんどなされず、結果として、１つ１つの要素ごとにクエリとの距離を算出することになり、効率的な情報探索が行われないという問題が生じる。
さらに、ＴＬＡＥＳＡなどでは、前述の通り三角不等式を用いるが、これは距離空間が情報探索集合であることが前提となる。従って、距離空間ではない情報に関して、ＴＬＡＥＳＡなどの三角不等式を利用し探索空間を削減する枝刈り方法に基づくアルゴリズムを、直接適用することは困難である。
【００１２】
本発明は、情報探索集合が高次元距離空間である場合または情報空間である場合であっても、情報を探索できることを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、前記課題を解決するために創案されたものであり、請求項１に記載の情報探索方法は、記憶部に保持されている情報探索集合からクエリと類似した情報を探索する情報探索装置における情報探索方法であって、前記情報探索方法は、ネットワーク生成処理と、情報探索処理とを含んでなり、前記ネットワーク生成処理は、前記情報探索装置のネットワーク生成部が、前記情報探索集合における任意の２つの要素間を、直接的、または、前記２つの要素以外の要素を介して間接的にリンク結合することにより、１コンポーネントのネットワークを生成し、前記記憶部に保持させ、前記情報探索処理は、前記情報探索装置の探索処理部が、（ａ１）前記ネットワークの所定の第1の要素に直接的にリンク結合された要素を、前記記憶部から取得し、当該要素のうち、前記クエリとの類似度が最も大きい要素を第２の要素として選択し、（ａ２）当該第２の要素と前記クエリとの類似度が、前記記憶部に保持されている所定の設定類似度よりも大きいならば、前記第２の要素と前記クエリとの類似度を新たな設定類似度として、前記記憶部に保持し、（ａ３）前記第２の要素を第３の要素とし、当該第３の要素に直接的にリンク結合された要素を、前記記憶部から取得し、（ａ４）前記第３の要素に直接的にリンク結合された要素のうち、過去に前記第２の要素になったことのない要素であり、かつ、前記クエリとの類似度が最も大きい要素を選択し、新たな第２の要素とし、当該新たな第２の要素に対して、前記（ａ２）の処理を行うことにより、前記クエリと類似した要素を探索する情報探索処理と、を実行する方法とした。
【００１４】
このような方法によれば、要素間がリンクによって、結合した１コンポーネントのネットワークを用いて探索を行い、距離空間の性質である三角不等式を用いていないため、情報探索集合が、高次元距離空間である場合や、情報探索集合が、距離空間でない場合であっても、情報探索を行うことができる。
【００１５】
さらに、請求項２に記載の情報探索方法は、請求項１に記載の情報探索方法において、前記ネットワーク生成処理は前記ネットワーク生成部が、前記情報探索集合における任意の要素である要素ｘと、前記要素ｘ以外の要素それぞれとの類似度を算出し、前記要素ｘ以外の要素のうち、前記要素ｘとの前記類似度が大きい順に、予め設定された所定数の要素を取得し、当該取得した要素と、前記要素ｘとの間をリンク結合することによって、前記要素ｘに対する最近傍要素ネットワークΓ（ｘ）を生成する処理を、前記情報探索集合におけるすべての要素に対して行う方法とした。
【００１６】
このような方法によれば、情報探索集合内の要素間のネットワークを、任意の要素ｘの近傍に存在する所定数の要素にリンクを張った最近傍要素ネットワークの集まりとすることができるため、平均最短パス長の小さいネットワークを生成することができる。このようなネットワークを情報探索に用いることにより、探索コストの削減が可能となる。
【００１７】
また、請求項３に記載の情報探索方法は、請求項２に記載の情報探索方法であって、前記情報探索処理は、前記探索処理部が、前記情報探索集合における任意の要素である要素ｘ０に対する前記最近傍要素ネットワークΓ（ｘ０）と、任意の要素であるｘｍａｘとを前記記憶部から取得し、前記入力部を介して、前記クエリｑが入力されると、（ｂ１）Ａ＝Γ（ｘ０）∪｛ｘ０｝，Ｂ＝｛ｘ０｝である集合Ａおよび集合Ｂを算出し、（ｂ２）次の式（８）を満たす要素ｘ１を、集合Ａ−Ｂから取得し、
【００１８】
【数３】
2008293444.tif 000004
【００１９】
（ただし、ρ（ａ，ｂ）は、前記情報探索集合内の要素であるａと、ｂとの類似度、｜Ａ｜は、集合Ａにおける要素数、Ａ―Ｂは、要素Ａと要素Ｂとの差集合、Γ（ａ）は、要素ａに対する最近傍要素ネットワーク（ｂ３）ρ（ｘ１，ｑ）＞ρ（ｘｍａｘ，ｑ）であれば、要素ｘ１を新たな要素ｘｍａｘとし、（ｂ４）ＡにＡ∪Γ（ｘ１）を代入し、ＢにＢ∪｛ｘ１｝を代入し、（ｂ５）前記（ｂ２）〜（ｂ４）の処理を繰り返し、｜Ａ｜が所定の値βを超える、または、前記クエリと前記要素ｘ１とが一致するとき、要素ｘｍａｘを最終出力要素として出力する方法とした。
【００２０】
このような方法によれば、１コンポーネントかつ平均最短パス長の小さいネットワークを使用して、情報探索を行うことができるため、探索コストの削減が可能となる。
【００２１】
また、請求項４に記載の情報探索プログラムは、請求項１から請求項３のいずれか一項に記載の情報探索方法をコンピュータに実行させるプログラムとした。
【００２２】
このようなプログラムによれば、要素間がリンクによって、結合した１コンポーネントのネットワークを用いて探索を行い、距離空間の性質である三角不等式を用いていないため、情報探索集合が、高次元距離空間である場合や、情報探索集合が、距離空間でない場合であっても、情報探索を行うことができる。また、情報探索集合内の要素間のネットワークを、任意の要素ｘの近傍に存在する所定数の要素にリンクを張った最近傍要素ネットワークの集まりとすることができるため、平均最短パス長の小さいネットワークを生成することができる。このようなネットワークを情報探索に用いることにより、探索コストの削減が可能となる。
【００２３】
そして、請求項５に記載の情報探索装置は、記憶部に保持されている情報探索集合からクエリと類似した情報を探索する情報探索装置であって、前記情報探索装置は、ネットワーク生成部と、探索処理部とを有してなり、前記ネットワーク生成部は、前記情報探索集合における任意の２つの要素間を、直接的、または、前記２つの要素以外の要素を介すことにより、間接的にリンク結合することにより、１コンポーネントのネットワークを生成し、前記記憶部に保持させる機能を有し、前記探索処理部は、（ａ１）前記ネットワークの所定の第1の要素に直接的にリンク結合された要素を、前記記憶部から取得し、当該要素のうち、前記クエリとの類似度が最も大きい要素を第２の要素として選択し、（ａ２）当該第２の要素と前記クエリとの類似度が、前記記憶部に保持されている所定の設定類似度よりも大きいならば、前記第２の要素と前記クエリとの類似度を新たな設定類似度として、前記記憶部に保持し、（ａ３）前記第２の要素を第３の要素とし、当該第３の要素に直接的にリンク結合された要素を、前記記憶部から取得し、（ａ４）前記第３の要素に直接的にリンク結合された要素のうち、過去に前記第２の要素になったことのない要素であり、かつ、前記クエリとの類似度が最も大きい要素を選択し、新たな第２の要素とし、当該新たな第２の要素に対して、前記（ａ２）の処理を行うことにより、前記クエリと類似した要素を探索する機能を有する装置とした。
【００２４】
このような情報探索装置によれば、要素間がリンクによって、結合した１コンポーネントのネットワークを用いて探索を行い、距離空間の性質である三角不等式を用いていないため、情報探索集合が、高次元距離空間である場合や、情報探索集合が、距離空間でない場合であっても、情報探索を行うことができる。
【発明の効果】
【００２５】
本発明によれば、情報探索集合が高次元距離空間である場合または情報空間である場合であっても、情報を探索することが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、図面を参照して、本発明を実施するための最良の形態（以下、「実施形態」という）について詳細に説明する。
【００２７】
（システム構成）
図１は、本実施形態に係る情報探索システムの構成例を示す図である。
情報探索システム１２は、情報の探索を行う情報探索装置１と、情報探索装置１に対してクエリを送信する端末１１とが、ＷＡＮ（Wide Area Network）や、ＬＡＮ（Local Area Network）などの物理的ネットワーク１０を介して接続している。
【００２８】
情報探索装置１は、情報の処理を行う処理部２と、探索対象の情報などが格納されている記憶部３と、情報が入力される入力部４と、情報探索の結果などを出力する出力部５とを含んでなる。記憶部３は、ＨＤ（Hard Disk）、不揮発性メモリ，ＲＡＭ（Random Access Memory）等の種々の記憶媒体の少なくとも１つから構成され、プログラムが実装される計算機の構成形態に依存した前記記憶媒体の組合せで構なされる。
端末１１から送信されたクエリは、物理的ネットワーク１０および入力部４を介して、処理部２へと送られる。また、ユーザが、入力部４を介して直接処理部２へクエリを入力してもよい。
処理部２は、ネットワーク生成処理を行うネットワーク生成部２１と、情報探索処理を行う探索処理部２２とを含んでなる。ここで、ネットワークとは、情報探索集合内における要素が、リンクによって結合しているときの、要素間のネットワークを指す。
【００２９】
処理部２と、処理部２内のネットワーク生成部２１および探索処理部２２とは、図示しないＨＤやＲＯＭ（Read Only Memory）などの記憶装置に格納されている情報探索プログラムが、図示しないＲＡＭに展開され、図示しないＣＰＵ（Central Processing Unit）によって実行されることで具現化する。
【００３０】
（近傍要素ネットワークの生成処理）
まず、図１を参照しつつ、図２に沿って、ネットワーク生成処理の概要を説明する。
図２は、本実施形態に係るネットワーク生成処理の概要を示す図である。
図２において、符号１００は、情報探索集合における要素、すなわち、記憶部３に格納され、探索対象となる情報である。ここで、要素とは、具体的には、例えば、新聞、特許公報等のテキストファイル、または、ＸＭＬ（Extensive Markup Language）による文書ファイル等である。
まず、ネットワーク生成部２１は、各要素１００間の類似度を算出する。本実施形態において、類似度は、コサイン類似度を指すものとするが、これに限らず、ミンコフスキー距離に代表される一般的な距離定義に基づく計算式や、コサイン類似度以外の類似度に基づく計算式を用いてもよい。
そして、図２（ａ）に示すように、ネットワーク生成部２１は、要素１００のうち、任意の要素１００（符号ｘ）を選択する。
そして、図２（ｂ）に示すように、ネットワーク生成部２１は、この要素ｘとの類似度が大きい要素１００を、予め入力されている近傍要素数ｋ個選択する。すなわち、ネットワーク生成部２１は、要素ｘ以外の要素１００から、要素ｘとの類似度が大きい順に、ｋ個の要素１００を選択する。近傍要素数ｋとは、生成するネットワークにおける全要素１００がリンクによって結合している１コンポーネントのネットワークとなるために必要なパラメータである。
【００３１】
ここで、コンポーネントとは、情報探索集合の部分集合であり、ある集合の任意の２つの要素１００間が少なくとも１つのリンクまたはリンクの連結により接続されているものである。但し、リンクの連結とは、第１の要素１００と第２の要素１００との間のリンク、第２の要素１００と第３の要素１００との間のリンク、…、第（ｎ−１）の要素１００と第ｎの要素１００との間のリンクのように、リンクの連なりのことをいう。このような場合、第１の要素１００と第ｎの要素１００とはリンクの連結により、間接的に接続されている。
例えば、「ネットワークが１コンポーネントである」とは、「任意の２つの要素１００間がリンクまたはリンクの連結により互いに接続されているネットワーク」であることをいう。
【００３２】
近傍要素数ｋは、テストデータなどを用い、探索コストを評価関数とすることで、求められる（図７、図８、図１２および図１３で後記）。図２では、ｋ＝３としている。
図２（ｂ）に示すように、ネットワーク生成部２１は、選択されたｋ個の要素１００と、要素ｘとの間にリンクを張ることにより、要素ｘに対する要素群Ｎｋ（ｘ）を形成する。
【００３３】
この処理を、各々の要素１００に対して行った後、ネットワーク生成部２１は、図２（ｃ）に示すように、要素ｘ以外の要素ｙに対する要素群Ｎｋ（ｙ）を参照し、この要素群Ｎｋ（ｙ）に要素ｘが含まれている要素ｙを抽出する。
そして、ネットワーク生成部２１は、図２（ｂ）および図２（ｃ）に示す要素ｘと、要素ｙにリンクを張ることにより、要素群Ｎｋ（ｘ）と、要素ｙとの和集合を算出する。この手順を無向化という。この和集合が、図２（ｄ）に示す要素ｘに対する最近傍要素ネットワークΓ（ｘ）となる。このような手順で生成された最近傍要素ネットワークΓ（ｘ）は、請求項におけるネットワークであり、無向性を有するネットワークである。ここで、無向性を有するネットワークとは、始点および終点の規定のないリンクである無向リンクにより結合された要素からなるネットワークである。
【００３４】
このよう手順によって、ネットワーク生成部２１が、各要素１００に対して最近傍要素ネットワークを算出すると、この最近傍要素ネットワークには以下のような性質が備わることとなる。
すなわち、任意の要素ｘ０に対する最近傍要素ネットワークΓ（ｘ０）を取得し、その最近傍要素ネットワークΓ（ｘ０）内における要素ｘ０以外の要素ｘ１を取得する。そして、取得した要素ｘ１に対する最近傍要素ネットワークΓ（ｘ１）を取得し、その最近傍要素ネットワークΓ（ｘ１）内における要素ｘ１以外の要素ｘ２を取得する。次に、取得した要素ｘ２に対する最近傍要素ネットワークΓ（ｘ２）を取得し、その最近傍要素ネットワークΓ（ｘ２）内における要素ｘ２以外の要素ｘ３を取得する、といった手順を繰り返すことにより、情報探索集合内の全要素１００をたどることができる。すなわち、図２（ｄ）の破線で示すように、情報探索集合内の全要素１００がリンクによって、直接的または間接的に連結した１コンポーネントのネットワークを生成することができる。ここで、要素ｘに対する最近傍要素ネットワークΓ（ｘ）を構成する要素は、要素ｘに直接的にリンク結合している要素となる。例えば、図２（ｄ）において、要素１０１と、要素１０２とは、直接的にリンク結合している。そして、要素１０１と、要素１０４とは、要素１０２および要素１０３を介することによって間接的に結合している。このように、生成されたネットワークの任意の２つの要素は、直接的または間接的にリンク結合している。このように、最近傍要素ネットワークを連結することによって、生なされる１コンポーネントのネットワークを近傍要素ネットワークΓ（図示せず）と記載することとする。
【００３５】
このように、近傍要素ネットワークΓでは、情報探索集合内のすべての前記要素１００間をリンクによって結合させているため（１コンポーネント）、リンクに従って、任意の要素１００よりクエリに近い要素１００を順に取得することにより、情報探索を行う際に、情報探索が途絶することがない。
【００３６】
次に、図１および図２を参照しつつ、図３を参照してネットワーク生成処理の流れを説明する。
図３は、本実施形態に係るネットワーク生成処理の流れを示すフローチャートである。
なお、図３の処理は、例えば、新たな情報探索集合を探索対象とする場合、または、新しい情報（要素）が情報探索集合に加わった場合に行われる処理である。
まず、情報探索装置１の入力部４を介して、近傍要素数ｋと、要素１００（図２参照）および要素１００の特徴量のリストとが、情報探索装置１へ入力され（Ｓ１０１）、記憶部３に格納される。
ネットワーク生成部２１は、記憶部３から、要素１００の特徴量を取得し、探索対象集合Ｘの要素１００である各要素ｘ（ｘ∈Ｘ）に対し、他の要素１００との類似度を、取得した特徴量を使用することによって算出する（Ｓ１０２）。
そして、ネットワーク生成部２１は、記憶部３から、近傍要素数ｋを取得すると、算出した類似度を基に、各要素ｘに対して、類似度の高いｋ個の要素群Ｎｋ（ｘ）を生成し（Ｓ１０３：図２（ｂ）参照）、記憶部３に記憶する。すなわち、要素ｘと、要素群Ｎｋ（ｘ）を構成する各要素とをリンク結合する。要素群Ｎｋ（ｘ）は、要素ｘに対し類似度の最も高い要素から降順にｋ個の要素の集合になる。
次に、ネットワーク生成部２１は、探索対象集合Ｘ中のすべての要素ｘに対して、ステップＳ１０３の処理を行ったか否かを判定する（Ｓ１０４）。判定は、例えば、ステップＳ１０３の処理を行った要素ｘにフラグを付し、このフラグがすべての要素１００に対し付されているか否かを、ネットワーク生成部２１が判定することによって行われる。
ステップＳ１０４の結果、すべての要素ｘに対して、ステップＳ１０３の処理を行っていないと判定された場合（Ｓ１０４→Ｎｏ）、ネットワーク生成部２１は、ステップＳ１０３の処理へ戻る。
ステップＳ１０４の結果、すべての要素ｘに対して、ステップＳ１０３の処理を行っていると判定された場合（Ｓ１０４→Ｙｅｓ）、ネットワーク生成部２１は、ステップＳ１０５の処理へ進む。
【００３７】
次に、ネットワーク生成部２１は、要素ｙ（ｙ∈Ｘ）に関して、記憶部３に記憶されている要素群Ｎｋ（ｙ）を取得し、要素ｙ自身は、Ｎｋ（ｘ）に含まれないが、要素ｘは、Ｎｋ（ｙ）に含まれている要素ｙを求める（図２（ｃ）参照）。そして、ネットワーク生成部２１は、このような要素ｙを、Ｎｋ（ｘ）と対応付けて記憶部３に記憶させることによって、要素ｘと、要素ｙとをリンク結合し、要素ｘに対する無向リンクを設定する（Ｓ１０５：図２（ｄ）参照）。
すなわち、式（７）に示す最近傍要素ネットワークΓ（ｘ）を算出する。
【００３８】
【数４】
2008293444.tif 000005
【００３９】
そして、ネットワーク生成部２１は、探索対象集合Ｘ中のすべての要素ｙに対して、ステップＳ１０５の処理を行ったか否かを判定する（Ｓ１０６）。判定は、例えば、ステップＳ１０５の後に、要素ｙにフラグを付し、このフラグがすべての要素１００に対し付されているか否かを、ネットワーク生成部２１が判定することによって行われる。
ステップＳ１０６の結果、すべての要素ｙに対して、ステップＳ１０５の処理を行っていないと判定された場合（Ｓ１０６→Ｎｏ）、ネットワーク生成部２１は、ステップＳ１０５の処理へ戻る。
ステップＳ１０６の結果、すべての要素ｙに対して、ステップＳ１０５の処理を行ったと判定された場合（Ｓ１０６→Ｙｅｓ）、ネットワーク生成部２１は、処理を終了する。
【００４０】
図４は、ネットワーク生成部によって算出された近傍要素ネットワークの記憶部での記憶状態を示す図である。
図４において、符号２００は、最近傍要素ネットワークの中心となる要素（中心要素：図２（ｄ）における要素ｘ。ただし、中心要素自身は、最近傍要素ネットワークに含まれない）の要素番号であり、符号２０１は、この中心要素に対して最近傍要素ネットワークを構成している要素（図２（ｄ）における符号Γ（ｘ））の要素番号である。なお、ここでは、要素毎に一意の要素番号を予め付されているものとする。
例えば、要素番号「１」の要素に対して最近傍要素ネットワークを構成している要素は、要素番号「３」，「５」，「７」である。そして、要素番号「２」の要素に対して最近傍要素ネットワークを構成している要素は、要素番号「３」，「６」，「８」，「９」，「１１」である。また、要素番号「３」の要素に対して最近傍要素ネットワークを形成している要素は、要素番号「１」，「２」，「９」，「１０」である。
最近傍要素ネットワークを構成する要素の数が異なるのは、図２（ｃ）における要素ｙの数がそれぞれの要素毎に異なるためである。
【００４１】
このようなネットワーク生成処理によれば、所定数の近傍要素の集合である最近傍要素ネットワークの集合として、近傍要素ネットワークを生成するため、平均最短パス長の小さいネットワークの生成が可能となる。ここで、パス長とは、情報探索集合内における任意の２つのノード間のリンクの数である。また、このようなネットワーク生成処理によれば、情報探索集合内のすべての要素に対し、各要素を中心要素とした最近傍要素ネットワークが存在するため、任意の要素を中心要素とする最近傍ネットワークを取得していくことで、情報探索集合内のすべての要素がリンクによって結合している最近傍要素ネットワークを生成することができる。
【００４２】
また、情報探索集合内における要素ｘとは異なる任意の要素である要素ｙを取得し、要素ｙとは異なる要素のうち、要素ｙとの類似度が高い順に、所定数の要素を取得し、当該取得した要素の集合を最近傍要素ネットワークΓ（ｙ）とし、最近傍要素ネットワークΓ（ｙ）の要素に、要素ｘが含まれている場合、要素ｙと、最近傍要素ネットワークΓ（ｘ）との和集合を、要素ｘに対する最近傍要素ネットワークとすることにより、無向リンクが設定される。この無向リンクが設定されることにより、要素ｘが、要素ｙに対する最近傍要素ネットワークに含まれるが、要素ｘに対する最近傍要素ネットワークに、要素ｙが含まれない状態となることを避けることができ、確実に情報探索集合内のすべての要素がリンクによって結合している近傍要素ネットワークを生成することができる。
【００４３】
（情報探索処理）
次に、図１を参照しつつ、図５に沿って、情報探索処理の概要について説明する。
図５は、本実施形態に係る情報探索処理の概要を示す図である。
図５において、符号は、図２と同様に、情報探索集合における要素（白丸または黒丸にて表現）、すなわち、記憶部３に格納され、探索対象となる情報である。
また、図５における破線で示すリンクによって全要素が連結した１コンポーネントの近傍要素ネットワークがネットワーク生成処理部２によって生成されているものとする。
探索処理部２２は、予め定められている要素、または、任意の要素を起点要素ｘ０とする。そして、当該起点要素ｘ０に対する最近傍要素ネットワークΓ（ｘ０）を記憶部３から取得する。
続いて、探索処理部２２は、起点要素ｘ０を展開要素集合Ｂの要素とし（Ｂ＝｛ｘ０｝）、取得した最近傍要素ネットワークΓ（ｘ０）と展開要素集合Ｂとの和集合を類似度計算要素集合Ａ（Ａ＝Γ（ｘ０）∪｛ｘ０｝）として求める。ここで、展開要素集合とは、ある要素ｘに対する最近傍要素ネットワークΓ（ｘ）の要素とクエリとの類似度計算を実行する場合の要素ｘから構なされる集合である。要素ｘから直接リンク結合されている要素を要素ｘの子要素と表現するときは、子要素とクエリとの類似度が計算される要素の集合である。一方、類似度計算要素集合とは、クエリとの類似度計算が実行される要素の集合である。以降、展開要素集合Ａを集合Ａと、類似度計算要素集合Ｂを集合Ｂと簡略し表現する。
そして、探索処理部２２は、集合Ａと集合Ｂとの差集合を構成する要素のうち、図示しないクエリとの類似度が最も大きい要素を抽出する。前記差集合は、既にクエリとの類似度計算を実行された要素であって、未だ展開されていない（子要素とクエリとの類似度計算が実行されていない）要素からなる集合である。
この場合、図５（ｂ）に示すように、要素ｘ１が、探索処理部２２によって抽出されたとする。
【００４４】
次に、類似度ρ（ｘ１，ｑ）＞類似度ρ（ｘｍａｘ，ｑ）を満たしているとしたとき、探索処理部２２は、図５（ｃ）に示すように、要素ｘ１を要素ｘｍａｘ（図示せず）とし、要素ｘｍａｘを更新し保持する。また、要素ｘ１が前記条件を充足しない場合は、要素ｘｍａｘの更新は行われない。探索処理部２２は、要素ｘ１に対して最近傍要素ネットワークΓ（ｘ１）（図５（ｃ）において実線で示されるリンクで結合している要素）を記憶部３から取得する。ここで、類似度ρ（ｘｍａｘ，ｑ）が、請求項における設定類似度であり、情報探索部が、要素ｘｍａｘを保持することにより、設定類似度も保持することになる。
そして、探索処理部２２は、要素ｘ１に対する最近傍要素ネットワークを構成する要素群Γ（ｘ１）の要素からなる集合と集合Ａとの和集合を新たな集合Ａとする。さらに、探索処理部２２は、要素ｘ１を、図５（ａ）に示す集合Ｂの要素に加え、新たな集合Ｂとする。そして、探索処理部２２は、新たな集合Ａと、集合Ｂとの差集合を構成する要素の中で、クエリとの類似度が最も大きい要素を抽出し、当該要素を新たな要素ｘ１とする（図５（ｃ）：Γ（ｘ１→ｘ１）。すなわち、図５（ｃ）に示すように、探索処理部２２は、新たな要素ｘ１を抽出する。
【００４５】
そして、そして、類似度ρ（ｘ１，ｑ）＞類似度ρ（ｘｍａｘ，ｑ）を満たしているとしたとき、探索処理部２２は、この要素ｘ１を新たな要素ｘｍａｘ（図示せず）として保持する。そして、探索処理部２２は、要素ｘ１に対する最近傍要素ネットワークΓ（ｘ１）の要素（図５（ｄ）中、実線で示されるリンクで結合している要素）からなる集合と集合Ａとの和集合を新たな集合Ａとし、要素ｘ１を、図５（ａ）に示す集合Ｂの要素に加え、新たな集合Ｂとする。そして、新たな集合Ａと、集合Ｂとの差集合を構成する要素の中で、クエリとの類似度が最も大きい要素を抽出する（図５（ｄ））。
このような処理を繰り返し、集合Ａの要素数が上限コストβを超えたとき（第１終了条件）、または、要素ｘ１とクエリとの類似度が１となった（クエリと一致する要素を抽出した：第２終了条件）とき、要素ｘｍａｘを最終出力要素とする。ただし、第２終了条件の設定の有無は情報探索集合に依存する。
【００４６】
次に、図１および図５を参照しつつ、図６に沿って、情報探索処理の流れを説明する。
図６は、本実施形態に係る情報探索処理の流れを示すフローチャートである。
情報探索装置１の記憶部３には、予め入力部４を介して入力されたコスト上限βと、要素と特徴量のリストと、起点要素ｘ０と、ネットワーク生成処理で算出された最近傍要素ネットワークΓ（ｘ）が要素ごとに格納されている。
まず、探索処理部２２は、起点要素ｘ０（ｘ０∈Ｘ）を記憶部から取得し、この起点要素ｘ０に対する最近傍要素ネットワークΓ（ｘ０）を記憶部３から取得する（Ｓ２０１）。すなわち、情報探索装置１は、最近傍要素ネットワークΓ（ｘ０）をＲＡＭなどのメモリ上に常駐させている。
次に、入力部４を介して、クエリｑが情報探索装置１に入力される（Ｓ２０２）。クエリの入力は、端末１１から物理的ネットワーク１０を介することによって、入力されてもよいし、直接入力部４から入力されてもよい。また、本実施形態では、探索処理部２２が、起点要素ｘ０を対する最近傍要素ネットワークΓ（ｘ０）を記憶部３から取得した後に、クエリｑが入力されたが、これに限らず、クエリｑが入力されてから、探索処理部２２が、起点要素ｘ０に対する最近傍要素ネットワークΓ（ｘ０）を記憶部３から取得してもよい。
次に、探索処理部２２は、起点要素ｘ０とクエリｑとの類似度ρ（ｘ０，ｑ）を算出し（Ｓ２０３）、記憶部３に格納する。なお、探索処理部２２は、この時点で、起点要素ｘ０に対する最近傍要素ネットワークΓ（ｘ０）を記憶部３から取得してもよい。ここで、ρ（・）は、例えば、コサイン類似度関数などの類似度関数であり、ρ（ａ，ｂ）＝ρ（ｂ，ａ）∈［０，１］、ａ，ｂ∈Ｘの性質を有する。ただし、任意の要素ａは、自分自身との類似度が最も大きくρ（ａ，ａ）＝１である。
【００４７】
そして、探索処理部２２は、集合Ａ＝Γ（ｘ０）∪｛ｘ０｝および集合Ｂ＝｛ｘ０｝を算出する（Ｓ２０４：図５（ａ））。
次に、探索処理部２２は、集合Ａの要素の数｜Ａ｜を算出し、｜Ａ｜＞上限コストβ、または、クエリｑと要素ｘｍａｘとの類似度（設定類似度）が１であること、すなわちρ（ｘｍａｘ，ｑ）＝１（クエリと要素とが一致していること）を満たしているか否かを判定する（Ｓ２０５）。ここで、｜・｜は、該当する集合の要素の数である。なお、要素ｘｍａｘの初期要素は、特に限定しないが、要素ｘ０などを代入しておいてもよい。ここで、算出されたρ（ｘｍａｘ，ｑ）は、記憶部３に格納される。
ステップＳ２０５の結果、｜Ａ｜＞β、または、ρ（ｘｍａｘ，ｑ）＝１を満たしている場合（Ｓ２０５→Ｙｅｓ）、探索処理部２２は、要素ｘｍａｘを最終出力要素ｘ２として出力し（Ｓ２０６）、処理を終了する。なお、本実施形態では、ステップＳ２０４の処理において、｜Ａ｜＞上限コストβ、または、クエリｑと要素ｘｍａｘとの類似度が１であることを判定しているが、これに加え、探索処理部２２が、図示しないタイマなどを監視し、所定の計算時間を越えているか否かを判定してもよい。
【００４８】
ステップＳ２０５の結果、条件を満たしていない場合（Ｓ２０４→Ｎｏ）、探索処理部２２は、集合Ａと集合Ｂとの差集合を算出し（Ｓ２０７）、当該差集合の要素ｙとクエリｑとの類似度ρ（ｙ，ｑ）を算出する（Ｓ２０８）。
そして、探索処理部２２は、集合Ａと、集合Ｂとの差集合におけるすべての要素ｙ（ｙ∈Ｘ）に対して、ステップＳ２０８の処理を行ったか否かを判定する（Ｓ２０９）。判定は、例えば、ステップＳ２０８の後に、要素ｙにフラグを付し、このフラグがすべての要素に対し付されているか否かを、探索処理部２２が判定することによって行われる。
【００４９】
ステップＳ２０９の結果、すべての要素ｙについて、ステップＳ２０８の処理を行っていないと判定された場合（Ｓ２０９→Ｎｏ）、探索処理部２２は、ステップＳ２０８の処理へ戻る。
ステップＳ２０９の結果、すべての要素ｙについて、ステップＳ２０８の処理を行っていると判定された場合（Ｓ２０９→Ｙｅｓ）、探索処理部２２は、ステップＳ２１０の処理へ進む。
【００５０】
次に、探索処理部２２は、式（８）の要素ｘ１を求める（Ｓ２１０：図５（ｂ））。
【００５１】
【数５】
2008293444.tif 000006
【００５２】
すなわち、探索処理部２２は、最大の類似度ρ（ｗ，ｑ）を有する要素ｗを算出し、この要素ｗを要素ｘ１（ｘ１∈Ｘ）とする。同時に、探索処理部２２は、ステップＳ２１０における式（８）で求めた要素ｘ１に係る類似度ρ（ｘ１，ｑ）を記憶部３に格納する。
そして、探索処理部２２は、記憶部３から類似度ρ（ｘｍａｘ，ｑ）および類似度ρ（ｘ１，ｑ）を取得し、類似度ρ（ｘ１，ｑ）＞類似度ρ（ｘｍａｘ，ｑ）であるか否かを判定する（Ｓ２１１）。
ステップＳ２１１の結果、類似度ρ（ｘ１，ｑ）＞類似度ρ（ｘｍａｘ，ｑ）ではない場合（Ｓ２１１→Ｎｏ）、探索処理部２２は、ステップＳ２１３の処理へ進む。
ステップＳ２１１の結果、類似度ρ（ｘ１，ｑ）＞類似度ρ（ｘｍａｘ，ｑ）である場合（Ｓ２１１→Ｙｅｓ）、探索処理部２２は、探索処理部２２は、要素ｘ１を、新たな要素ｘｍａｘとして保持する（Ｓ２１２：図５（ｃ））。前記したように、類似度ρ（ｘｍａｘ，ｑ）が、請求項における設定類似度であり、情報探索部が、要素ｘｍａｘを保持することにより、設定類似度も保持することになる。
次に、探索処理部２２は、要素ｘ１に対する最近傍要素ネットワークΓ（ｘ１）を記憶部３から取得すると、集合Ａ’＝Ａ∪Γ（ｘ１）および集合Ｂ’＝Ｂ∪｛ｘ１｝を算出し、集合Ａ’を新たなＡとし、Ｂ’を新たなＢとする（Ａ←Ａ’、Ｂ←Ｂ’：Ｓ２１３：図５（ｃ））。すなわち、集合Ａに集合Ａ’を代入し、集合Ｂに集合Ｂ’を代入する。
そして、探索処理部２２は、ステップＳ２０５の処理へ戻る。
【００５３】
なお、本実施形態において、情報探索集合の要素内に同一の情報が存在するようなクエリを入力してもよいし、情報探索集合の要素内に同一の情報が存在しないようなクエリを入力してもよい。
【００５４】
本実施形態に係る情報探索処理は、要素間の平均最短パス長が小さいスモールワールドネットワークを使用して情報探索を行うため、情報探索集合に対して距離空間を定義すると、要素間の距離が大きい、すなわち要素同士が疎となり、三角不等式などによる探索空間の削減が不可能な情報探索集合に対しても、探索コストの小さい情報探索を行うことができる。すなわち、探索空間を小さくすることができる。
また、要素間における距離の定義を前提としていないため、距離空間を定義不可能な情報探索集合に対しても効率的な情報探索を行うことが可能となる。例えば、任意の２つの要素間の類似度を、コサイン類似度で定義した情報探索集合は、距離空間ではない。さらに、局所的な要素の集合である最近傍要素ネットワークを連結した近傍要素ネットワークを用いており、全体の情報探索を、処理の軽い最近傍要素ネットワークにおける探索の集まりとすることができ、全体的な処理の負担を軽減することができる。
そして、１度探索した要素は、次回以降の探索対象から外した情報探索を行うため、効率的な情報探索を行うことができる。
【００５５】
（ネットワークの特性）
ここで、本実施形態に好適なネットワークの性質について説明する。
まず、本実施形態におけるネットワークは、情報探索を効率よく行うため、近傍要素数ｋと強い相関を有する値である次数が、比較的小さいネットワークであることが望ましい。次数を比較的小さくすることで、情報探索集合内の全要素が結合した１コンポーネントのネットワークであり、次数が比較的小さいことが望ましい。本実施形態で用いた近傍要素ネットワークにおける平均次数は、式（９）で定義される。
【００５６】
【数６】
2008293444.tif 000007
【００５７】
さらに、本実施形態におけるネットワークは、任意の起点要素と、最終出力要素との間に、比較的短いリンクで連結されていることが必要である。探索コストの小さい情報探索を行うためである。
本実施形態で用いた近傍要素ネットワーク全体における平均値である平均最短パス長は、式（１０）で定義される。
【００５８】
【数７】
2008293444.tif 000008
【００５９】
ここで、ｄΓ（ｘ，ｙ）は、ネットワークにおける任意の要素における最短パス長である。
【００６０】
また、最終出力要素ｘ２における近傍の要素群ｙ∈Γ（ｘ２）のそれぞれと、クエリｑとの類似度が比較的低い場合、情報探索が困難になる。なぜならば、起点要素ｘ０から最終出力要素ｘ２へ到達するためには、最終出力要素ｘ２における近傍の要素ｙを経由することが必須となるためである。すなわち、類似度ρ（ｘ２，ｑ）と類似度ρ（ｘ２，ｙ）が高い値を示すときには、類似度ρ（ｙ，ｑ）もまた高い値を示すことが望ましい。これを一般化すると、３つの要素ｘ，ｙ，ｚにおいて、ｙ∈Γ（ｘ）かつｚ∈Γ（ｙ）において、類似度ρ（ｘ，ｙ）と類似度ρ（ｙ，ｚ）が高い値を示すとき、ｘ∈Γ（ｚ）となるような高い値の類似度ρ（ｚ，ｘ）（ｘ∈Γ（ｚ））が高い値を示すこと好ましい。すなわち、３つの要素ｘ，ｙ，ｚにおける任意のペア要素間にリンクが存在することが望ましい。
このような、３つの要素間の関係を定量的に評価する尺度であるネットワークのクラスタ係数は、式（１１）で定義される。クラスタ係数が高い値であるほど、任意の３つの要素間における任意のペア要素間にリンクが存在する率が高い。
【数８】
2008293444.tif 000009
【００６１】
本実施形態に好適なネットワークの特性として、１．式（９）で示される平均次数が小さく、かつ１コンポーネントのネットワークであること、２．平均最短パス長が比較的小さいネットワークであること、３．クラスタ係数が比較的大きいネットワークであることが望ましい。
このような特性を備えるネットワークをスモールワールドネットワークと記載する。スモールワールドネットワークには、本実施形態で記載した近傍要素ネットワークが含まれる。本実施形態で使用する近傍要素ネットワークにおける平均最短パス長と、クラスタ係数とに関する考察は、図１５および図１６を参照して後記する。
【００６２】
次に、図７から図１４に沿って、本実施形態における実施形態例を示す。
なお、図７から図１１は、クエリと同一の情報が情報探索集合の要素に含まれている探索問題に対する図であり、図１２から図１４は、クエリと同一の情報が情報探索集合の要素に含まれていない探索問題に対する図である。
【００６３】
図７は、近傍要素数ｋに対するコンポーネント数の変化を示す図である。
図７において、横軸は、近傍要素数ｋの値を示し、縦軸は、コンポーネント数に対し常用対数を適用した値である。
なお、図７における情報探索集合は、１０年分の新聞の記事における文書ファイルを要素とする集合である。そして、要素間の類似度は、以下の手順によって算出した。すなわち、各文書ファイルを形態素解析し、不要なストップワードを削除した上で、単語を抽出する。そして、抽出された単語に対し、ｔｆ−ｉｄｆ法で各単語に対し、重み付けを行う。この結果、生じる重み付け単語ベクトルを、該文書ファイルの特徴量とする。
その上で、文書ファイルを要素とし、コサイン類似度関数を用いて、要素間の類似度を規定する。
この例で用いた要素数（文書ファイル数）は、６４５８５個であり、距離空間の次元数は、５１０３０となった。
図７において示されるようにｋ＝６において、コンポーネント数は、１となる。すなわち、ｋ＝６で、１コンポーネントの近傍要素ネットワークの生成が可能となる。すなわち、ｋ≧６以上であれば、１コンポーネントの近傍要素ネットワークを生成することができる。
【００６４】
図８は、近傍要素数ｋに対する平均探索コストの変化を示す図である。
図８において、横軸は、近傍要素数ｋの値を示し、縦軸は、平均探索コストである。
図８では、前記した１０年分の新聞記事の文書ファイルの要素から、ランダムに１０００００個のペア要素（クエリと、起点要素のペア）を選択し、前記した情報探索集合に対して、本実施形態における情報探索処理を行った結果を示す。
コスト上限値は、無限大に設定されている。また、平均探索コストとは、同一の情報探索集合に対し、クエリと、起点要素とを変化させて、情報探索をおこなったときの探索コストの平均値である。
図８で示されるように近傍要素数ｋ＝２０において、平均探索コストは、最小の３６５．３８となった。この値は、全要素を探索した場合の探索コストの０．５７％である。
【００６５】
平均コストが、最小値をもつ理由として、次の理由が考えられる。本実施形態における探索コストは、平均次数と平均ステップ数との積にほぼ近い値となる。ここで、ステップ数とは、最終出力要素を算出するまでにたどった起点要素ｘ０と要素ｘ１（図５）との数である。すなわち、図５における黒丸の数である。
一般に、近傍要素数ｋは、図７および図８の手順によって、決定される。
【００６６】
図９は、近傍要素数ｋに対する平均次数の変化を示す図であり、図１０は、近傍要素数ｋに対するステップ数の変化を示す図である。
図９において、横軸は、近傍要素数ｋを示し、縦軸は、平均次数を示す。
また、図１０において、横軸は、近傍要素数ｋを示し、縦軸は、ステップ数の平均値（Ａｖｅｒａｇｅ）または中央値（Ｍｅｄｉａｎ）を示す。
図９および図１０の各ｋにおいて、平均次数の値と、ステップ数の平均値または中央値を乗算すると、ｋ＝２０において、平均探索コストが最小となることがわかる。
【００６７】
図１１は、各近傍要素数ｋにおける探索コストと、クエリへの到達率を示す図である。
図１１において、横軸は、探索コストを示し、縦軸は、到達率を示す。
到達率とは、前記したようなペア要素（クエリと、起点要素のペア）を１０００００個選択したとき、そのうち、該当する探索コストでクエリに到達したペア要素の割合である。
グラフは、それぞれｋ＝１０，２０，４０，６０の場合について記載する。図８において、最も平均探索コストが小さかったｋ＝２０に注目すると、探索コストが２９１で到達率５０％であり、探索コストが６３３で９０％の到達率となっている。すなわち、選択したペア要素のうち、探索コストが２９１でクエリへ到達したペア要素は、選択したペア要素のうちの５０％であり、探索コストが６３３でクエリへ到達したペア要素は、選択したペア要素のうちの９０％であることを示す。
【００６８】
本実施形態例における全要素数は、前記したように６４５８５個であり、そのうちの１％がほぼ６４６個である。すなわち、本実施形態の情報探索処理に、本実施形態例の情報探索空間に、本実施形態の情報探索処理を適用すると、上限コストβを全要素数の１％程度の値に設定したとしても、９０％の確率で探索が成功することがわかる。
【００６９】
次に、図１２から図１４に沿って、本実施形態をクエリと同一の情報が情報探索集合の要素に含まれていない探索問題に適用した際の実施形態例を説明する。
なお、図１２から図１４における各用語の定義は、図７から図１１における用語と同様である。
図１２は、近傍要素数ｋに対するコンポーネント数の変化を示す図である。
図１２における条件は、以下の通りである。
図７から図１１において、用いた情報探索集合（要素数：６４５８５個）の中から、一様ランダムに６４５８要素を選択し、これをクエリとした。そして、残りの５８１２７個の要素を情報探索集合とした。
図１２において、横軸は、近傍要素数ｋの値を示し、縦軸は、コンポーネント数に対し常用対数を適用した値である。
図１２において示されるようにｋ＝７において、コンポーネント数は、１となる。すなわち、ｋ＝７で、１コンポーネントの近傍要素ネットワークの生成が可能となる。すなわち、ｋ≧７以上であれば、１コンポーネントの近傍要素ネットワークを生成することができる。
【００７０】
図１３は、近傍要素数ｋに対する平均探索コストの変化を示す図である。
図１３において、横軸は、近傍要素数ｋの値を示し、縦軸は、平均探索コストである。
なお、図１３における条件は、図８における条件と同様である。
平均探索コストとは、同一の情報探索集合に対し、クエリと、起点要素とを変化させて、情報探索をおこなったときの探索コストの平均値である。
図８で示されるようにｋ＝４０において、平均探索コストは、最小の９３９．８８となった。この値は、全要素を探索した場合の探索コストの１．６２％である。
一般に、近傍要素数ｋは、図１２および図１３の手順によって、決定される。
【００７１】
図１４は、各近傍要素数ｋにおける探索コストと、クエリへの到達率を示す図である。
図１４において、横軸は、探索コストを示し、縦軸は、到達率を示す。
到達率とは、現在探索中の要素とクエリとの距離を起点要素と、クエリとの距離で除算したものである。
グラフは、それぞれｋ＝１０，２０，４０，６０の場合について記載する。図１３において、最も平均探索コストが小さいｋ＝４０に注目すると、探索コストが４９４で到達率５０％であり、探索コストが１５４０で９０％の到達率となっている。
【００７２】
本実施形態例における全要素数は、５８１２７個であり、この３％がほぼ１７４４個である。すなわち、本実施形態の情報探索処理に、本実施形態例の情報探索空間に、本実施形態の情報探索処理を適用すると、上限コストβ（図６参照）を全要素数の３％程度の値に設定したとしても、９０％の確率で探索が成功することがわかる。
【００７３】
次に、図１５および図１６に沿って、本実施形態で用いた近傍要素ネットワークの特性を説明する。
図１５は、ランダムネットワーク、近傍要素ネットワークおよびレギュラーネットワークにおける近傍要素数ｋに対する平均最短パス長の変化を示す図である。
ここで、ランダムネットワークとは、情報探索集合中の任意の要素と、要素との結合をランダムに行ったネットワークである。レギュラーネットワークとは、情報探索集合中の要素間の結合を、所定の規則に従って結合したネットワークである。
図１５の横軸は、近傍要素数ｋを示し、縦軸は、平均最短パス長を示す。
図１５に示すように、各近傍要素数ｋにおける近傍要素ネットワーク（ｋ−ＮＮ  ＮＷ）の平均最短パス長は、レギュラーネットワーク（Ｒｅｇｕｌａｒ  ＮＷ）の平均最短パス長よりかなり小さく、ランダムネットワーク（Ｒａｎｄｏｍ  ＮＷ）の平均最短パス長に近い値を有する。
一般に、スモールワールドネットワークにおける平均最短パス長は、式（１２）を見たすオーダであることが望ましい。
ｌｏｇ１０（スモールワールドネットワークの平均最短パス長／ランダムネットワークの平均最短パス長）＜１・・・式（１２）
【００７４】
図１６は、ランダムネットワーク、近傍要素ネットワークおよびレギュラーネットワークにおける近傍要素数ｋに対するクラスタ係数の変化を示す図である。
図１６の横軸は、近傍要素数ｋを示し、縦軸は、クラスタ係数を示す。
図１６に示すように、各ｋにおける近傍要素ネットワーク（ｋ−ＮＮ  ＮＷ）のクラスタ係数は、ランダムネットワーク（Ｒａｎｄｏｍ  ＮＷ）のクラスタ係数より大きく、レギュラーネットワーク（Ｒｅｇｕｌａｒ  ＮＷ）のクラスタ係数に近い値を有する。
【図面の簡単な説明】
【００７５】
【図１】本実施形態に係る情報探索システムの構成例を示す図である。
【図２】本実施形態に係るネットワーク生成処理の概要を示す図である。
【図３】本実施形態に係るネットワーク生成処理の流れを示すフローチャートである。
【図４】ネットワーク生成部によって算出された近傍要素ネットワークの記憶部での記憶状態を示す図である。
【図５】本実施形態に係る情報探索処理の概要を示す図である。
【図６】本実施形態に係る情報探索処理の流れを示すフローチャートである。
【図７】近傍要素数ｋに対するコンポーネント数の変化を示す図である。
【図８】近傍要素数ｋに対する平均探索コストの変化を示す図である。
【図９】近傍要素数ｋに対する平均次数の変化を示す図である。
【図１０】近傍要素数ｋに対するステップ数の変化を示す図である。
【図１１】各近傍要素数ｋにおける探索コストと、クエリへの到達率を示す図である。
【図１２】近傍要素数ｋに対するコンポーネント数の変化を示す図である。
【図１３】近傍要素数ｋに対する平均探索コストの変化を示す図である。
【図１４】各近傍要素数ｋにおける探索コストと、クエリへの到達率を示す図である。
【図１５】ランダムネットワーク、近傍要素ネットワークおよびレギュラーネットワークにおける近傍要素数ｋに対する平均最短パス長の変化を示す図である。
【図１６】ランダムネットワーク、近傍要素ネットワークおよびレギュラーネットワークにおける近傍要素数ｋに対するクラスタ係数の変化を示す図である。
【図１７】情報探索空間から、無作為に１×１０６個のペア要素（２つの要素）を選択し、このペア要素間の距離の累積分布を示す図である。
【図１８】図１７と同様の条件下における距離の下界の累積分布を示す図である。
【符号の説明】
【００７６】
１      情報探索装置
２      処理部
２      ネットワーク生成処理部
３      記憶部
４      入力部
５      出力部
１０    ネットワーク
１１    端末
１２    情報探索システム
２１    ネットワーク生成部
２２    探索処理部
【図１】
2008293444.tif 000011
【図２】
2008293444.tif 000012
【図３】
2008293444.tif 000013
【図４】
2008293444.tif 000014
【図５】
2008293444.tif 000015
【図６】
2008293444.tif 000016
【図７】
2008293444.tif 000017
【図８】
2008293444.tif 000018
【図９】
2008293444.tif 000019
【図１０】
2008293444.tif 000020
【図１１】
2008293444.tif 000021
【図１２】
2008293444.tif 000022
【図１３】
2008293444.tif 000023
【図１４】
2008293444.tif 000024
【図１５】
2008293444.tif 000025
【図１６】
2008293444.tif 000026
【図１７】
2008293444.tif 000027
【図１８】
2008293444.tif 000028