(57)【要約】【課題】隣接要素集合を効率的に求める。【解決手段】  複数の要素の中から、予め定められた基準要素との関連の強さが予め定められた条件を満たす要素の集合である隣接要素集合を選択する選択装置１０は、隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補の各々として、複数の要素の中から、基準要素との関連がより強いと判断した要素の集合を選択する隣接要素集合候補選択部１１０と、複数の隣接要素集合候補の和集合の中から、基準要素との関連の強さが予め定められた条件を満たす要素の集合を、隣接要素集合として選択する隣接要素集合選択部１３０とを備える。【選択図】図１
2005322161.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素の中から、予め定められた基準要素との関連の強さが予め定められた条件を満たす要素の集合である隣接要素集合を選択する選択装置であって、
前記隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補の各々として、前記複数の要素の中から、前記基準要素との関連がより強いと判断した要素の集合を選択する隣接要素集合候補選択部と、
前記複数の隣接要素集合候補の和集合の中から、前記基準要素との関連の強さが前記予め定められた条件を満たす要素の集合を、前記隣接要素集合として選択する隣接要素集合選択部と
を備える選択装置。
【請求項２】
前記複数の要素の各々をノードとし、複数の当該ノードを、複数の階層の何れかに分類したデータ構造である階層構造データを複数生成し、複数の前記階層構造データの各々について、前記複数の階層の各々に分類されたノードと、当該階層に隣接する他のノードとの間に、当該ノードと、当該他のノードとの関連の強さに基づいてエッジを生成する階層構造データ生成部を更に備え、
前記隣接要素集合候補選択部は、前記複数の階層構造データの各々について、当該階層構造データに基づいて、一の前記隣接要素集合候補を選択する
請求項１記載の選択装置。
【請求項３】
前記階層構造データ生成部は、前記階層構造データ毎に異なる乱数の種を用いて、前記複数のノードの各々を、前記複数の階層の何れかに無作為に分類することにより、互いに異なる前記複数の階層構造データを生成する
請求項２記載の選択装置。
【請求項４】
前記複数の階層構造データの各々において、
前記階層構造データ生成部は、複数の階層の各々に分類された処理対象の各ノードについて、当該階層の上位に隣接する階層に位置するノードのうち、当該処理対象のノードとの関連がより強いと判断した予め定められた数のノードを親ノードとして選択し、当該処理対象のノードと、選択した当該親ノードの各々との間にエッジを生成し、
前記階層構造データ生成部は、更に、複数の階層の各々に分類された処理対象の各ノードについて、当該階層の下位に隣接する階層に位置するノードのうち、当該処理対象のノードを親ノードとして有するノードの集合を選択し、選択した当該集合の中から、当該処理対象のノードとの関連がより強いと判断した予め定められた数のノードを子ノードとして選択し、当該処理対象のノードと、選択した当該子ノードの各々との間にエッジを生成し、
前記隣接要素集合候補選択部は、複数の階層の各々について、既に上位の階層において選択したノードの子ノードの中から、前記基準要素との関連がより強い予め定められた数以内の子ノードの組を選択し、各階層について選択したノードの中から、前記基準要素との関連がより強い予め定められた数のノードを、前記隣接要素集合候補として選択する
請求項２記載の選択装置。
【請求項５】
前記隣接要素集合候補選択部が、前記基準要素との関連がより強い要素を選択するために算出した、前記基準要素と他の各々の要素との関連の強さをキャッシュするキャッシュ部を更に備え、
前記隣接要素集合候補選択部は、前記基準要素との関連がより強い要素を選択する場合において、前記基準要素と選択対象の各要素との関連の強さが前記キャッシュ部にキャッシュされていない場合に、前記基準要素と当該要素との関連の強さを算出して前記キャッシュ部にキャッシュさせ、前記基準要素と選択対象の各要素との関連の強さが前記キャッシュ部にキャッシュされている場合に、キャッシュされた関連の強さに基づいて、前記基準要素との関連がより強い要素を選択する
請求項２記載の選択装置。
【請求項６】
前記隣接要素集合候補選択部は、前記基準要素と他の各々の要素との間の関連の強さを算出する回数が、予め定められた基準回数に達するまで、複数の隣接要素集合候補を順次選択する
請求項２記載の選択装置。
【請求項７】
前記隣接要素集合選択部は、前記複数の隣接要素集合候補の和集合の中から、前記基準要素との関連が予め定められた基準より強い要素の集合を、前記隣接要素集合として選択する
請求項１記載の選択装置。
【請求項８】
前記隣接要素集合選択部は、前記複数の隣接要素集合候補の和集合の中から、前記基準要素との関連がより強い、予め定められた基準個数の要素の集合を、前記隣接要素集合として選択する
請求項１記載の選択装置。
【請求項９】
前記隣接要素集合候補選択部は、前記複数の隣接要素集合候補の各々として、前記基準要素との関連がより強いと判断した前記基準個数以上の要素の集合を選択する
請求項８記載の選択装置。
【請求項１０】
前記隣接要素集合候補選択部は、既に選択した隣接要素集合候補の和集合の要素数が、前記基準個数以上の値に予め定められた和集合基準数量に達するまで、複数の隣接要素集合候補を順次選択する
請求項８記載の選択装置。
【請求項１１】
前記隣接要素集合候補選択部は、前記複数の要素の中から、含んでいる要素の組が互いに異なる複数の要素の集合を生成し、生成した当該複数の要素の集合の各々について、当該集合の中で前記基準要素との関連がより強い要素の組を、前記隣接要素集合候補として選択する
請求項１記載の選択装置。
【請求項１２】
当該選択装置は、複数の文書の中から、予め定められた基準文書との関連が強い文書の集合を前記隣接要素集合として選択する装置であり、
前記隣接要素集合候補選択部は、前記複数の隣接要素集合候補の各々として、前記複数の文書の中から、前記基準文書と共通して含むキーワードの数がより多いと判断した文書の集合を選択し、
前記隣接要素集合選択部は、前記複数の隣接要素集合候補の和集合の中から、前記基準文書と共通して含むキーワードの数が予め定められた条件を満たす文書を前記隣接要素集合として選択する
請求項１記載の選択装置。
【請求項１３】
当該選択装置は、複数の動画の中から、予め定められた基準動画との関連が強い動画の集合を前記隣接要素集合として選択する装置であり、
前記隣接要素集合候補選択部は、前記複数の隣接要素集合候補の各々として、前記複数の動画の中から、前記基準動画とより類似すると判断した動画の集合を選択し、
前記隣接要素集合選択部は、前記複数の隣接要素集合候補の和集合の中から、前記基準動画との類似の程度が予め定められた条件を満たす動画を前記隣接要素集合として選択する
請求項１記載の選択装置。
【請求項１４】
複数の要素の中から、予め定められた基準要素との関連の強さが予め定められた条件を満たす要素の集合である隣接要素集合を選択する選択方法であって、
前記隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補の各々として、前記複数の要素の中から、前記基準要素との関連がより強いと判断した要素の集合を選択する隣接要素集合候補選択段階と、
前記複数の隣接要素集合候補の和集合の中から、前記基準要素との関連の強さが前記予め定められた条件を満たす要素の集合を、前記隣接要素集合として選択する隣接要素集合選択段階と
を備える選択方法。
【請求項１５】
複数の要素の中から、予め定められた基準要素との関連の強さが予め定められた条件を満たす要素の集合である隣接要素集合を選択する選択装置として、コンピュータを機能させるプログラムであって、
前記コンピュータを、
前記隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補の各々として、前記複数の要素の中から、前記基準要素との関連がより強いと判断した要素の集合を選択する隣接要素集合候補選択部と、
前記複数の隣接要素集合候補の和集合の中から、前記基準要素との関連の強さが予め定められた条件を満たす要素の集合を、前記隣接要素集合として選択する隣接要素集合選択部と
して機能させるプログラム。
【請求項１６】
請求項１５に記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、選択装置、選択方法、プログラム、及び記録媒体に関する。特に、本発明は、データベース等に格納された複数の要素の中から予め定められた基準要素との関連が強い要素の集合を選択する選択装置、選択方法、プログラム、及び記録媒体に関する。
【背景技術】
【０００２】
近年、コンピュータの発達・普及に伴い、様々なデータが電子化されるようになってきている。電子化されたデータは、様々な産業において利用される。例えば、商品の購買行動を電子化したデータからマーケティング・リサーチを行ったり、経済指標等を電子化したデータから株価変動を予測したりすることが提案されている。しかしながら、電子化したデータが膨大な場合には、所望のデータのみを適切に選択することは難しい。そこで、従来、データ探索等の技術が用いられている。
【０００３】
従来、データ探索の基本的な課題として、与えられたクエリに近接するｋ個のデータを探索するｋ−隣接探索（k-nearest neighbor探索）が知られている。ｋ−隣接探索において、探索の対象とするデータの集合が膨大な場合や、データの性質を示すパラメータの次元数が多い場合に、クエリに最も近いｋ個のデータを正確に求めるには、膨大な計算時間を要する。このため、ｋ−隣接探索を現実的な計算時間で近似的に処理する近似解法が提案されている（特許文献１、非特許文献２、非特許文献６参照。）。例えば、特許文献１の技術は、非特許文献１において指摘された「次元の呪い」に対して有効な方法として提案されている。
【０００４】
一方、実行する毎に処理結果の異なる非決定的なアルゴリズムについて、アルゴリズムの実行により得られた結果を改善する方法として、正解率増幅法（amplification technique）が知られている。例えば、行列Aおよび行列Bの積が行列Cであるか否かを判定する計算において、非特許文献３および４による方法では、ある確率で誤った答えを返す可能性があるが、その確率を非常に小さく設定することが可能で、確実に正解を返す方法と比較して、より少ない計算量で判定できる。
【０００５】
非特許文献５、及び非特許文献７から９については後述する。
【特許文献１】特開２００３−２５６４７７号公報
【非特許文献１】V. Pestov, On the geometry of similarity search: dimensionality curse and concentration of measure, Information Processing Letters, 73:47-51, 2000.
【非特許文献２】Michael E. Houle, SASH: a spatial approximation sample hierarchy for similarity search, IBM Tokyo Research Laboratory Research Report RT-0446, 18 pages, Feb. 18, 2002.
【非特許文献３】渡辺  治  著「乱拓アルゴリズムの世界へ、確率的アルゴリズムによる情報処理予稿集」、インターネットホームページ「http://www.statp.is.tohoku.ac.jp/kazu/SMAPIP/2003/tutorial/index.html」
【非特許文献４】R. Motwania and P. Raghavan,  Randomized Algorithms, Cambridge 1995年
【非特許文献５】Y. Yang and X. Liu, A re-examination of text categorization, Proc. Of the 22nd Annual International ACM SIGIR Conf. On research and development in Information Retrieval, Morgan Kaufman, 1999
【非特許文献６】Michael E. Houle, Navigating Massive Data Sets via Local Clustering, IBM Tokyo Research Laboratory Research Report RT-0518, 15 pages, Mar. 5, 2002.
【非特許文献７】G.Salton, The SMART Retrieval System-Experiments in Automatic Document Processing, Prentice-Hall, Englewood Cliffs, NJ, USA, 1971.
【非特許文献８】Chavez, E., Navarro G., Baeza-yates, R. and Marroquin, J. L, Satisfying general proximity/similarity queries with metric trees, Inf. Proc. Lett. 40, pp. 175-179, 1991
【非特許文献９】Navvarro, G., Searching in metric spaces by spatial approximation, IN Proc. Of String Processing and Information Retrieval, pp. 141-148, 1999
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１等に記載された技術によれば、クエリに最も近いｋ個のデータを探索する範囲を、実際に探索するべきデータ全体と比較して狭めることにより、計算時間を節約する。従って、計算時間と、近似の精度とはトレードオフの関係にあり、トレードオフ比は略一定である。このため、例えば近似の精度を高めるには、探索する範囲を広げて計算時間を増やさなければならない。これに対して、本発明は、このトレードオフ比を改善すること、即ち例えば、計算時間を増やすことなく近似の精度を高めることを課題とする。
【０００７】
そこで本発明は、上記の課題を解決することのできる選択装置、選択方法、プログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明の第１の形態においては、複数の要素の中から、予め定められた基準要素との関連の強さが予め定められた条件を満たす要素の集合である隣接要素集合を選択する選択装置であって、隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補の各々として、複数の要素の中から、基準要素との関連がより強いと判断した要素の集合を選択する隣接要素集合候補選択部と、複数の隣接要素集合候補の和集合の中から、基準要素との関連の強さが予め定められた条件を満たす要素の集合を、隣接要素集合として選択する隣接要素集合選択部とを備える選択装置、当該選択装置を用いた選択方法、当該選択装置としてコンピュータを機能させるプログラム、及び当該プログラムを記録した記録媒体を提供する。
【０００９】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群の組み合わせもまた、発明となりうる。
【発明の効果】
【００１０】
本発明によれば、隣接要素集合を効率的に求めることができる。
【発明を実施するための最良の形態】
【００１１】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１２】
図１は、選択装置１０の機能ブロック図である。選択装置１０は、複数の要素、例えば複数の文書の中から、予め定められた基準要素との関連が強い予め定められた基準個数の要素の集合である隣接要素集合を、効率的に選択することを目的とする。ここで、基準要素とは、例えば、データベースを探索するためのクエリであり、複数の要素とは、データベースに格納されているデータの集合である。即ち例えば、選択装置１０は、データベースに対するクエリに対して、クエリに類似するデータを効率的に選択することを目的とする。
【００１３】
選択装置１０は、階層構造データ生成部１００と、隣接要素集合候補選択部１１０と、キャッシュ部１２０と、隣接要素集合選択部１３０とを備える。階層構造データ生成部１００は、選択対象である複数の要素として、複数の文書を入力する。そして、階層構造データ生成部１００は、複数の要素の各々をノードとし、複数のそのノードを、予め定められた複数の階層の何れかに分類した階層構造データを複数生成する。この階層構造データは、例えば、特許文献１に記載の方法により生成されたSASHである。そこで、以降の説明において、これらの複数の階層構造データを、SASH1からSASHnと呼ぶ。
【００１４】
次に、階層構造データ生成部１００は、各SASHについて、複数の階層の各々に分類されたノードと、その階層に隣接する他のノードとの間に、当該ノードと、当該他のノードとの関連の強さに基づいてエッジを生成する。続いて、隣接要素集合候補選択部１１０は、SASH1からSASHnに基づいて、隣接要素集合の互いに異なる複数の候補である複数の隣接要素集合候補を選択する。具体的には、隣接要素集合候補選択部１１０は、SASH1からSASHnの各々について、複数の要素の中から、そのSASHに基づいて基準要素との関連がより強いと判断した要素の集合を、一の隣接要素集合候補として選択する。選択したこれらの隣接要素集合候補を、NN1からNNnとする。
【００１５】
ここで、隣接要素集合(k-nearest neighbor)とは、ある基準要素との関連が最も強いk個の要素の集合をいう。一方、選択装置１０は、隣接要素集合を近似的に求めるので、選択装置１０が求める隣接要素集合は、実際の隣接要素集合と異なる場合がある。以降の説明においては、便宜上、選択装置１０が求める近似的な隣接要素集合を「隣接要素集合」と呼び、実際の隣接要素集合を「真の隣接要素集合」と呼ぶ。
【００１６】
続いて、キャッシュ部１２０は、隣接要素集合候補選択部１１０が、基準要素との関連がより強い要素を選択するために算出した、基準要素と他の各々の要素との関連の強さをキャッシュする。例えば、キャッシュ部１２０は、当該他の各々の要素を識別するノードＩＤと、基準要素と当該要素との関連の強さを示す関連度とを対応付けて格納する。そして、隣接要素集合候補選択部１１０は、キャッシュ部１２０にキャッシュされた関連の強さに基づいて、隣接要素集合候補を選択してもよい。続いて、隣接要素集合選択部１３０は、NN1からNNnの和集合の中から、基準要素との関連の強さが予め定められた条件を満たす要素の集合を、隣接要素集合として選択し、選択結果を出力する。
【００１７】
図２は、選択装置１０が隣接要素集合を選択する処理の動作フローを示す。階層構造データ生成部１００は、複数のSASHを生成する（Ｓ２００）。これに代えて、階層構造データ生成部１００は、階層構造データとして、VPT又はSATを生成してもよい。VPTの生成方法については、非特許文献８に記載されているので本実施例における説明を省略する。SATの生成方法については、非特許文献９に記載されているので本実施例における説明を省略する。
【００１８】
次に、選択装置１０は、各SASHについて、以下の処理を繰り返す（Ｓ２１０）。まず、隣接要素集合候補選択部１１０は、当該SASHに基づいて、１つの隣接要素集合候補を選択する（Ｓ２２０）。次に、隣接要素集合候補選択部１１０は、既に選択された各隣接要素集合の和集合と、新たに選択したこの隣接要素集合候補との和集合を生成する（Ｓ２３０）。次に、隣接要素集合候補選択部１１０は、生成したこの和集合の要素数が、基準個数以上の値に予め定められた和集合基準数量に達したか否かを判断する（Ｓ２４０）。
【００１９】
和集合基準数量に達した場合に（Ｓ２４０：ＹＥＳ）、選択装置１０は、この繰り返し処理を終了してＳ２７０に処理を移す。即ち、隣接要素集合候補選択部１１０は、生成した和集合の要素数が、和集合基準数量に達するまで、複数の隣接要素集合候補を順次選択する。一方、和集合基準数量に達していない場合に（Ｓ２４０：ＮＯ）、隣接要素集合候補選択部１１０は、隣接要素集合候補を選択するために基準要素と他の各々の要素との間の関連の強さを算出する回数が、予め定められた基準回数に達したか否かを判断する（Ｓ２５０）。
【００２０】
基準回数に達した場合に（Ｓ２５０：ＹＥＳ）、選択装置１０は、Ｓ２７０に処理を移す。即ち、隣接要素集合候補選択部１１０は、関連の強さを算出する回数が基準回数に達するまで、複数の隣接要素集合候補を順次選択する。一方、基準回数に達していない場合に（Ｓ２５０：ＮＯ）、選択装置１０は、Ｓ２２０に処理を戻して、他のSASHについての処理に移る。
【００２１】
選択装置１０は、以上の処理を各SASHについて繰り返す（Ｓ２６０）。続いて、隣接要素集合選択部１３０は、複数の隣接要素集合候補の和集合の中から、基準要素との関連がより強い基準個数の要素の集合を、隣接要素集合として選択する（Ｓ２７０）。具体的には、隣接要素集合選択部１３０は、当該和集合に含まれる各々の要素を、基準要素との関連が強い順に並び替える。そして、隣接要素集合選択部１３０は、並び替えたこれらの要素の先頭から重複する要素を除いた基準個数の要素を、隣接要素集合として選択する。
【００２２】
これに代えて、隣接要素集合選択部１３０は、基準要素との関連が予め定められた基準より強い全ての要素を、隣接要素集合として選択してもよい。即ち、隣接要素集合選択部１３０は、基準要素との関連の強さについて、何らかの予め定められた条件を適用することにより、基準要素と関連の強い要素を選択する。
【００２３】
ここで、各要素が文書である場合について、要素間の関連の強さを示す関連度を算出する処理の一例を更に詳しく説明する。
隣接要素集合選択部１３０は、基準要素である基準文書と、隣接要素集合候補の和集合に含まれる他の各々の文書との関連度を、当該基準文書と、当該他の文書とが共通して含むキーワードの数に基づいて算出する。具体的には、まず、隣接要素集合選択部１３０は、文書毎に、当該文書が含むキーワードの組を示すベクトルを生成する。ベクトルの各要素は、対応する文書がキーワードを含む旨を示す１、又は、キーワードを含まない旨を示す０の２値をとる。
【００２４】
これに代えて、ベクトルの各要素は、大きさを持った連続値であってもよい。例えば各要素は、その要素に対応するキーワードが、文書において用いられた回数・頻度・出現場所に基づく値を有してもよい。より詳細には、あるベクトルの要素は、その要素のキーワードが、文書の章・節のタイトルで使われた場合に、その他の場所で使われた場合と比較して、より高い値を有してもよい。このようなベクトルの生成方法は、TF/IDF技術として従来公知であるので、より詳細な説明を省略する。
【００２５】
そして、隣接要素集合選択部１３０は、ある文書に対応するベクトルvと、他の文書に対応するベクトルwとに基づいて、これらの文書の関連の強さを示す関連度を生成する。本例において、関連度は、以下の式（１）により算出された文書間の距離に基づく値である。算出された距離がより長い場合と比較して、距離がより短い場合に、関連度はより大きくなる。
【数１】
2005322161.tif 000003
【００２６】
この結果、隣接要素集合選択部１３０は、複数の隣接要素集合候補の和集合の中から、基準文書と共通して含むキーワードの数が予め定められた条件を満たす文書を隣接要素集合として選択することができる。
【００２７】
なお、他の例として、各要素は動画等のマルチメディアデータであってもよい。この場合、隣接要素集合候補選択部１１０は、複数の隣接要素集合候補の各々として、複数の動画の中から、基準要素である基準動画とより類似すると判断した動画の集合を選択する。そして、隣接要素集合選択部１３０は、複数の隣接要素集合候補の和集合の中から、基準動画との類似の程度が予め定められた条件を満たす動画を隣接要素集合として選択する。このように、本実施例における選択装置１０は、互いの関連の強さを算出できる様々なデータに対して適用することができる。
【００２８】
図３は、図２のＳ２００における処理の動作フローを示す。階層構造データ生成部１００は、互いに異なる複数の乱数の種を生成する（Ｓ３００）。そして、階層構造データ生成部１００は、各乱数の種について以下の処理を繰り返す（Ｓ３１０）。まず、階層構造データ生成部１００は、その乱数の種を用いて、複数の要素を表す複数のノードの各々を、複数の階層の何れかに無作為に分類する（Ｓ３２０）。
【００２９】
次に、階層構造データ生成部１００は、複数の階層の各々に分類されたノードと、その階層に隣接する他のノードとの間に、ノード間の関連の強さに基づいてエッジを生成する（Ｓ３３０）。具体的には、階層構造データ生成部１００は、複数の階層の各々に分類された処理対象の各ノードについて、その階層の上位に隣接する階層に位置するノードのうち、その処理対象のノードとの関連がより強いと判断した予め定められた数のノードを親ノードとして選択し、その処理対象のノードと、選択したその親ノードの各々との間にエッジを生成する。
【００３０】
更に、階層構造データ生成部１００は、複数の階層の各々に分類された処理対象の各ノードについて、その階層の下位に隣接する階層に位置するノードのうち、その処理対象のノードを親ノードとして有するノードの集合を選択する。そして、階層構造データ生成部１００は、選択した当該集合の中から当該処理対象のノードとの関連がより強いと判断した予め定められた数のノードを子ノードとして選択し、その処理対象のノードと、選択したその子ノードの各々との間にエッジを生成する。
【００３１】
より詳細には、階層構造データ生成部１００は、以下の性質を有する有向グラフをSASHとして生成する。
・ 各ノードは、各要素に対応している
・ SASHは階層構造を有し、各ノードは階層を表す何れかのレベルに属している。最上位階層のレベルには１つのノードのみが属し、そのノードをルートノードと呼ぶ。最下位階層のレベルには、要素全体をn個とした場合にn/2個のノードが属している。SASHのレベルは、最上位階層を１とし、最下位階層をhとする。
・ エッジは、隣接したレベルに属するノード間のみに張られる。ここで、例えばレベルlに属するノードvに着目する。レベル(l-1)に属し、vにエッジで接続されたノードを、vの親ノードと呼ぶ。vから親ノードへのエッジは高々p本とする。また、レベル(l+1)に属し、vにエッジで接続されたノードを子ノードと呼ぶ。vから子ノードへのエッジは高々c本とする。
・ ルートノード以外の全てのノードは少なくとも１つの親ノードを持つ。ルートノードを除く全てのノードは必ずguarantorと呼ばれる親を１つ有する。vのguarantorであるg(v)は、vを子ノードとして有している。このときvをdependentと呼ぶ。
次に、レベル1からレベル(l-1)まで構築されたSASHに、レベルlのノードを接続するアルゴリズムを以下に示す。
【００３２】
アルゴリズム：ConnectSASHLevel(l)
ステップ１：もしl=2ならば、レベル２の全てのノードはルートノードを親ノードかつguarantorとして接続する。ルートノードはレベル２の全てのノードを子ノードかつdependentとして接続する。
ステップ２：もしl>2ならば、レベルlの各ノードvについて、レベル１≦ｉ＜ｌの各レベルから、隣接要素集合Pi (v, p)を以下の方法により算出する。
ステップ2(a)：もしi=1ならばPi(v,p)はルートノードである
ステップ2(b)：もしi>1ならば、Ｐi´(v)をPi-1 (v,p)に含まれる各ノードの子ノードの集合として選択する。但し、同一のノードを重複して選択しない。
ステップ2(c)：i>1であるＰi´(v)からvに最も近いp個のノードを選び、Pi(v,p)とする。もし|Pi´(v)|<pならば、Pi(v,p)=Pi´(v)とする。
ステップ3：ノードvの親ノードをPi-1(v, p)とする。レベルlの各ノードvは、p個の異なる親をそれぞれ持つ。
【００３３】
ステップ4：レベル(l-1)における各ノードuについて、子ノードへのエッジを以下の手順で生成する。
ステップ4(a)：レベル(l-1)の各ノードuについて、uを親ノードとして選択したレベルlのノードをC(u)とする。
ステップ4(b)：C(u)をuとの関連の強さの順にソートする。
ステップ4(c)：もしC(u)がc個以上あれば、c+1番目以降のC(u)の要素を破棄する。
ステップ4(d)：uの子ノードをC(u)とする。
ステップ5：レベルlの各ノードvについて、そのノードvが、レベル(l-1)の何れかのノードの子ノードであるかを判断する。子ノードであれば、ノードvの親ノードのうち、vに最も関連の強い親ノードをguarantorとする。何れのノードの子ノードにもならないと判断した場合に、ノードvを孤児ノードとする。
【００３４】
ステップ6：レベルlの各孤児ノードについて、以下の手順により、レベル(l-1)の何れかのノードをguarantorとして選択する。ここで、c個未満の子ノードを持つ親ノードをunencumberedなノードと呼ぶ。
ステップ6(a)：i=1とする。
ステップ6(b)：Pi-1(v, 2ip)を計算する。
ステップ6(c)：もしPl-1(v,2ip)がunencumberedなノードを含まないなら、iをインクリメントしてステップ6(b)に処理を戻す。
ステップ6(d)：そうでなければ、ノードvに最も近いunencumberedなノードをPl-1(v, 2ip)から選び、これをguarantorとする。また、ノードvを個ノードとして設定する。更に、ノードvをg(v)のdependentとして設定し、ノードvとの関連が最も弱い親ノードをg(v)と置き換える。
【００３５】
階層構造データ生成部１００は、以上の処理を、各乱数の種について繰り返すことにより、互いに異なる複数のSASHを生成する（Ｓ３４０）。
【００３６】
図４は、階層構造データ生成部１００が生成したＳＡＳＨの一例を示す。丸印は、各ノードを示す。また、レベルl+1のノード数は、レベルlのノード数の２倍である。同様に、レベルlのノード数は、レベルl-1のノード数の２倍である。各ノードを結ぶ矢印は、親ノード及び子ノードの関係を示す。点線の矢印で示すように、各子ノードは、最大２個の親ノードを有する。また、実線の矢印で示すように、各親ノードは、最大４個の子ノードを有する。
【００３７】
図５は、図２のＳ２２０における処理の動作フローを示す。隣接要素集合候補選択部１１０は、SASHの各階層について、以下の処理を繰り返す（Ｓ５００）。なお、各階層のレベルを1からhとし、処理対象の階層のレベルをiとする。まず、隣接要素集合候補選択部１１０は、処理対象の階層がレベル1である場合に（Ｓ５１０：ＹＥＳ）、処理対象のSASHにおけるルートノードを、選択対象集合に加え（Ｓ５１５）、Ｓ５８０に処理を移して次の繰り返し処理に移る。
【００３８】
一方、処理対象の階層がレベル1でない場合に（Ｓ５１０：ＮＯ）、まず、隣接要素集合候補選択部１１０は、処理対象の階層の上位に隣接する階層のうち、選択対象集合に含まれるノードを選択する（Ｓ５２０）。次に、隣接要素集合候補選択部１１０は、上位階層から選択したこれらのノードの各子ノードについて、基準要素とそのノードとの関連の強さを示す関連度がキャッシュ部１２０にキャッシュされているか否かを判断する（Ｓ５３０）。
【００３９】
関連度がキャッシュ部１２０にキャッシュされている場合に、隣接要素集合候補選択部１１０は、キャッシュされている関連度をキャッシュ部１２０から取得し（Ｓ５４０）、Ｓ５７０に処理を移す。一方、関連度がキャッシュ部１２０にキャッシュされていない場合に、隣接要素集合候補選択部１１０は、基準要素とそのノードとの関連度を算出する（Ｓ５５０）。そして、隣接要素集合候補選択部１１０は、算出した関連度をキャッシュ部１２０にキャッシュさせる（Ｓ５６０）。
【００４０】
続いて、隣接要素集合候補選択部１１０は、キャッシュ部１２０から取得した関連度、又は、新たに算出した関連度に基づいて、基準要素との関連が強い所定の数の要素を選択対象集合に加える（Ｓ５７０）。隣接要素集合候補選択部１１０が選択対象集合に加える要素の数は、例えば、階層のレベルに応じて異なってもよい。そこで、各階層iにおいて隣接要素集合候補選択部１１０が選択対象集合に加える要素の数をkiとする。
この場合、好ましくは、kiは、例えば、以下の式（２）で表される。
【数２】
2005322161.tif 000004
【数３】
2005322161.tif 000005
【数４】
2005322161.tif 000006
ここで、式（３）の項により、隣接要素集合候補選択部１１０は、各階層に含まれる要素の数が多い場合に、その数が少ない場合と比較して、より多い要素を選択対象集合として選択する。そして、式（４）の項は、各階層から選択対象集合として選択される個数の下限を規定する。即ち、隣接要素集合候補選択部１１０は、選択対象の階層が比較的上位の階層であっても、式（４）に規定される数を下限として要素を選択する。
【００４１】
隣接要素集合候補選択部１１０は、以上の処理を、SASHの各階層について繰り返す（Ｓ５８０）。続いて、隣接要素集合候補選択部１１０は、選択対象集合の中から、基準要素との関連がより強い予め定められた数のノードを、隣接要素集合候補として選択する（Ｓ５９０）。好ましくは、隣接要素集合候補選択部１１０は、選択対象集合の中から、基準要素との関連がより強い、基準個数以上の値に予め定められた数の要素を、隣接要素集合候補として選択する。この場合、隣接要素集合候補選択部１１０は、隣接要素集合候補を選択するために、キャッシュ部１２０にキャッシュされた関連度を用いてもよい。
【００４２】
以上、本図に示したように、隣接要素集合候補選択部１１０は、SASH毎に、そのSASHの構造に基づいて選択対象集合を選択する。これにより、隣接要素集合候補選択部１１０は、複数の要素全体の中から、含んでいる要素の組が互いに異なる複数の選択対象集合を生成することができる。そして、隣接要素集合候補選択部１１０は、生成した複数の選択対象集合の各々について、その選択対象集合の中で基準要素との関連がより強い要素の組を、隣接要素集合候補として選択する。これにより、隣接要素集合は、互いに異なる複数の隣接要素集合候補を求めることができる。
【００４３】
図６は、選択対象集合の概念を示す図である。（ａ）は、各階層から選択対象集合として選択される要素の数であるkiを変化させた場合における、選択対象集合の変化を示す。なお、kiを定めるパラメータをスケールファクタとする。本図の白い三角形全体は、SASH全体を示す。斜線の三角形は、選択対象集合を示す。本図から明らかなように、スケールファクタを増やしてkiを増加させることにより、選択対象集合の要素数が増加する。
【００４４】
（ｂ）は、スケールファクタに応じて変化する関連度の算出回数と、隣接要素集合候補の正確さとを示す。スケールファクタを増加させると、選択対象集合が増加するので、関連度の算出回数が増加する。また、スケールファクタを増加させると、選択対象集合が増加するので、隣接要素集合候補の正確さが高まる。即ち、関連度の算出回数と、隣接要素集合候補の正確さとの間には、トレードオフの関係がある。これに対し、本実施例における選択装置１０によると、複数の隣接要素集合候補に基づき隣接要素集合を算出することにより、トレードオフ比を改善できる。
【００４５】
図７は、本実施例の効果を説明する図である。本実施例に示す選択装置１０を用いて、関連度の算出回数に対する隣接要素集合の正確さを実験により計測した。実験における選択対象の文書は、TREC-6 L.A.Timesデータベースにおけるニュース記事である。このデータベースは、127738個の6590次元の実数値特徴量ベクトルで構成される。ベクトルの座標軸の重み付けには、TF/IDF(Term Frequency/Inverse Document Frequency)を用いる（非特許文献７参照。）。
【００４６】
そして、次の５つの場合について、隣接要素集合の正確さを計測する。
１． ある１つのみのSASHに基づいて隣接要素集合を選択(sash1.data)
２． ２つのSASHに基づいて２つの隣接要素集合候補を選択し、これらの隣接要素集合に基づいて隣接要素集合を選択(sash2.data)
３． 上記２に加えて、更に隣接要素集合候補を選択するために算出した関連度をキャッシュ(sash2_share.data)
４． ３つのSASHに基づいて３つの隣接要素集合候補を選択し、これらの隣接要素集合に基づいて隣接要素集合を選択(sash3.data)
５． 上記４に加えて、更に隣接要素集合候補を選択するために算出した関連度をキャッシュ(sash3_share.data)
【００４７】
本図から明らかなように、１つのみのSASHに基づいて隣接要素集合を選択した場合と比較して、選択装置１０は、より正確な隣接要素集合をより少ない計算時間で算出することができる。
【００４８】
続いて、本実施例における選択装置１０が隣接要素集合をより正確に選択できる理由を以下に述べる。上述のように、隣接要素集合候補選択部１１０は、複数の互いに異なる隣接要素集合候補を選択する。これらの隣接要素集合候補を、A1、A2、…Arとする。即ち、隣接要素集合の和集合は、A1∪A2∪…∪Arである。また、基準個数をk個とする。いま、真の隣接要素集合をA*とする。更に、A1、A2、…Arの各々が有する要素のうち、A*に含まれる要素の割合の期待値をpとする。但し、pは0以上１以下の値である。このとき、Ai∩A*がA*から一様に選択されると仮定すると、以下の事実が導かれる。
＜|A∩A*|＞i=pk  …（５）
＜|(A1∪A2∪…∪Ar)∩A*|＞ i=(1−(1−p) r)k  …（６）
【００４９】
ここで、＜・＞ iは、SASH生成時の乱数に対する期待値を表す演算子である。式（５）は、SASHに基づいて選択した隣接要素集合候補に、真の隣接要素集合の要素が平均pk個含まれることを示している。また、式（６）は、SASHをr個生成し、各々のSASHに基づいて隣接要素集合候補を選択した場合に、真の隣接要素集合の要素が、隣接要素集合候補の和集合に平均(1−(1−p) r)k個含まれていることを示す。この式から明らかなように、rを増やすことにより、隣接要素集合候補の和集合に含まれる真の隣接要素の割合を増加させることができる。
【００５０】
ここで、Ai∩A*がA*から一様に選択されるとは限らない。しかしながら、選択装置１０は、乱数の種を隣接要素集合毎に異ならせることにより、A*からAi∩A*を近似的に一様に選択させることができる。即ち、必ずしも正確さが式（６）に示した理論値に従うわけではないが、選択装置１０は、隣接要素集合候補の数に応じて隣接要素集合の正確さを高めることができる。
【００５１】
なお、好ましくは、SASHの生成処理を以下のように工夫することにより、隣接要素集合の正確さを高められる。具体的には、階層構造データ生成部１００は、複数のSASHを順次生成する場合に、既に生成したSASHにおいて互いに隣接する階層に配置したノードの組を、新たに生成するSASHにおいて隣接した階層に配置しない。また、更に好ましくは、階層構造データ生成部１００は、既に生成したSASHにおいて互いに隣接する階層に配置したノードの組のうち、新たに生成するSASHにおいて隣接した階層に配置するノードの組の割合が基準値以下となるように制御する。これにより、より少ないSASHにより隣接要素集合の正確さを効率的に高めることができる。
【００５２】
図８は、選択装置１０として機能するコンピュータ５００のハードウェア構成の一例を示す。コンピュータ５００は、ホストコントローラ８８２により相互に接続されるＣＰＵ８００、ＲＡＭ８２０、及びグラフィックコントローラ８７５を有するＣＰＵ周辺部と、入出力コントローラ８８４によりホストコントローラ８８２に接続される通信インターフェイス８３０、ハードディスクドライブ８４０、及びＣＤ−ＲＯＭドライブ８６０を有する入出力部と、入出力コントローラ８８４に接続されるＢＩＯＳ８１０、フレキシブルディスクドライブ８５０、及び入出力チップ８７０を有するレガシー入出力部とを備える。
【００５３】
ホストコントローラ８８２は、ＲＡＭ８２０と、高い転送レートでＲＡＭ８２０をアクセスするＣＰＵ８００及びグラフィックコントローラ８７５とを接続する。ＣＰＵ８００は、ＢＩＯＳ８１０及びＲＡＭ８２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ８７５は、ＣＰＵ８００等がＲＡＭ８２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置８８０上に表示させる。これに代えて、グラフィックコントローラ８７５は、ＣＰＵ８００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００５４】
入出力コントローラ８８４は、ホストコントローラ８８２と、比較的高速な入出力装置である通信インターフェイス８３０、ハードディスクドライブ８４０、及びＣＤ−ＲＯＭドライブ８６０を接続する。通信インターフェイス８３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ８４０は、コンピュータ５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ８６０は、ＣＤ−ＲＯＭ８９５からプログラム又はデータを読み取り、ＲＡＭ８２０を介して入出力チップ８７０に提供する。
【００５５】
また、入出力コントローラ８８４には、ＢＩＯＳ８１０と、フレキシブルディスクドライブ８５０や入出力チップ８７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ８１０は、コンピュータ５００の起動時にＣＰＵ８００が実行するブートプログラムや、コンピュータ５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ８５０は、フレキシブルディスク８９０からプログラム又はデータを読み取り、ＲＡＭ８２０を介して入出力チップ８７０に提供する。入出力チップ８７０は、フレキシブルディスク８９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００５６】
コンピュータ５００に提供されるプログラムは、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ８７０及び/又は入出力コントローラ８８４を介して、記録媒体から読み出されコンピュータ５００にインストールされて実行される。コンピュータ５００にインストールされて実行されるプログラムがコンピュータ５００に働きかけて行わせる動作は、図１から図７において説明したコンピュータ５００における動作と同一であるから、説明を省略する。
【００５７】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ５００に提供してもよい。
【００５８】
以上、本実施例に示すように、選択装置１０は、複数の階層構造データの各々に基づいて、複数の隣接要素集合候補の各々を選択する。そして、隣接要素集合候補の和集合の中から、隣接要素集合を選択する。これにより、１つの階層構造データから隣接要素集合候補を選択する場合における、計算時間と正確さとのトレードオフ比を改善することができる。即ち例えば、選択装置１０は、隣接要素集合の正確さを、計算時間を増やすことなく高めることができる。
【００５９】
更に、本実施例に示す選択装置１０は、隣接要素集合(k-near neighbor)を用いて要素を分類する分類装置（例えば、非特許文献５参照。）に適用可能である。即ち、この分類装置において隣接要素集合を求めるモジュールを、本実施例に示す選択装置１０にそのまま置き換えることができる。これにより、従来の分類装置の分類精度を容易に高めることができる。
【００６０】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００６１】
【図１】図１は、選択装置１０の機能ブロック図である。
【図２】図２は、選択装置１０が隣接要素集合を選択する処理の動作フローを示す。
【図３】図３は、図２のＳ２００における処理の動作フローを示す。
【図４】図４は、階層構造データ生成部１００が生成したＳＡＳＨの一例を示す。
【図５】図５は、図２のＳ２２０における処理の動作フローを示す。
【図６】図６は、選択対象集合の概念を示す図である。
【図７】図７は、本実施例の効果を説明する図である。
【図８】図８は、選択装置１０として機能するコンピュータ５００のハードウェア構成の一例を示す。
【符号の説明】
【００６２】
１０  選択装置
１００  階層構造データ生成部
１１０  隣接要素集合候補選択部
１２０  キャッシュ部
１３０  隣接要素集合選択部
５００  コンピュータ
【図１】
2005322161.tif 000007
【図２】
2005322161.tif 000008
【図３】
2005322161.tif 000009
【図４】
2005322161.tif 000010
【図５】
2005322161.tif 000011
【図６】
2005322161.tif 000012
【図７】
2005322161.tif 000013
【図８】
2005322161.tif 000014