(57)【要約】【課題】新たな頂点を近傍グラフに追加するために要する時間計算量を削減すること。【解決手段】グラフ更新装置において、近傍グラフと、当該近傍グラフに追加頂点として追加するオブジェクトとに基づいて、前記近傍グラフにおける前記追加頂点のK近傍頂点集合を探索し、当該K近傍頂点集合を出力するK近傍頂点探索部と、前記近傍グラフと、前記追加頂点と、前記追加頂点のK近傍頂点集合とに基づいて、当該近傍グラフ中の頂点であって、当該頂点のK近傍頂点集合に前記追加頂点が含まれる可能性のある頂点の集合である頂点候補集合を選択し、当該頂点候補集合を出力する頂点選択部と、前記頂点候補集合の各頂点のK近傍頂点集合を用いて前記近傍グラフの全頂点に関するK近傍頂点集合を再構築し、前記追加頂点のK近傍頂点集合を前記再構築したK近傍頂点集合に追加することにより、更新された近傍グラフを作成する近傍グラフ更新部とを備える。【選択図】図１
2019197438.tif 000002
【特許請求の範囲】
【請求項１】
近傍グラフと、当該近傍グラフに追加頂点として追加するオブジェクトとに基づいて、前記近傍グラフにおける前記追加頂点のK近傍頂点集合を探索し、当該K近傍頂点集合を出力するK近傍頂点探索部と、
前記近傍グラフと、前記追加頂点と、前記追加頂点のK近傍頂点集合とに基づいて、当該近傍グラフ中の頂点であって、当該頂点のK近傍頂点集合に前記追加頂点が含まれる可能性のある頂点の集合である頂点候補集合を選択し、当該頂点候補集合を出力する頂点選択部と、
前記頂点候補集合の各頂点のK近傍頂点集合を用いて前記近傍グラフの全頂点に関するK近傍頂点集合を再構築し、前記追加頂点のK近傍頂点集合を前記再構築したK近傍頂点集合に追加することにより、更新された近傍グラフを作成する近傍グラフ更新部と
を備えることを特徴とするグラフ更新装置。
【請求項２】
前記頂点選択部は、前記近傍グラフの頂点の集合から、前記追加頂点をK近傍頂点としない頂点を除外するためのフィルターを適用することで前記頂点候補集合を選択する
ことを特徴とする請求項１に記載のグラフ更新装置。
【請求項３】
前記近傍グラフ更新部は、前記更新された近傍グラフとして、近似次数低減K最近傍グラフを作成する
ことを特徴とする請求項１又は２に記載のグラフ更新装置。
【請求項４】
グラフ更新装置が実行するグラフ更新方法であって、
近傍グラフと、当該近傍グラフに追加頂点として追加するオブジェクトとに基づいて、前記近傍グラフにおける前記追加頂点のK近傍頂点集合を探索し、当該K近傍頂点集合を出力するK近傍頂点探索ステップと、
前記近傍グラフと、前記追加頂点と、前記追加頂点のK近傍頂点集合とに基づいて、当該近傍グラフ中の頂点であって、当該頂点のK近傍頂点集合に前記追加頂点が含まれる可能性のある頂点の集合である頂点候補集合を選択し、当該頂点候補集合を出力する頂点選択ステップと、
前記頂点候補集合の各頂点のK近傍頂点集合を用いて前記近傍グラフの全頂点に関するK近傍頂点集合を再構築し、前記追加頂点のK近傍頂点集合を前記再構築したK近傍頂点集合に追加することにより、更新された近傍グラフを作成する近傍グラフ更新ステップと
を備えることを特徴とするグラフ更新方法。
【請求項５】
前記頂点選択ステップにおいて、前記グラフ更新装置は、前記近傍グラフの頂点の集合から、前記追加頂点をK近傍頂点としない頂点を除外するためのフィルターを適用することで前記頂点候補集合を選択する
ことを特徴とする請求項４に記載のグラフ更新方法。
【請求項６】
前記近傍グラフ更新ステップにおいて、前記グラフ更新装置は、前記更新された近傍グラフとして、近似次数低減K最近傍グラフを作成する
ことを特徴とする請求項４又は５に記載のグラフ更新方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のグラフ更新装置における各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械学習や探索アルゴリズム等の分野において使用される近傍グラフを更新する技術に関連するものである。
【背景技術】
【０００２】
近傍グラフは多様な形態があり、その形態に応じて種々な分野で応用されている。近傍グラフの典型は、オブジェクト又は空間中の点を頂点とし、2頂点の関係性の疎密又は遠近に基づき、その2頂点間に辺を設けるものである。特に、関係性を有る頂点からの類似度又は距離（又は非類似度）と定義し、その類似度や距離（非類似度）に基づき最も近い又は類似のK個の頂点に辺を張るK最近傍グラフ（K-nearest neighbor graph、K-NN graph）や、ボロノイ図（Voronoi diagram）の双対であるドロネー三角形分割（Delaunay triangulation、DT）、DTの部分グラフである相対近傍グラフ（relative neighborhood graph, RNG）又はRNGの一般化グラフであるβスケルトングラフ、RNGの部分グラフである最小全域木（minimum spanning tree, MST）はパターン認識や探索において利用されている。
【０００３】
探索法に着目すると、K最近傍グラフやその部分グラフである次数低減K最近傍グラフ（degree-reduced k-nearest neighbor graph、K-DR graph）を探索の索引に利用し、探索を高速に実行するグラフ索引型探索法が提案されている（非特許文献１）。また、グラフ索引を用いた探索法には、近似探索法（非特許文献２）又は発見的方法（特許文献１、２、非特許文献１、３）があり、種々のメディアに対して高速探索を実現してきた。
【０００４】
グラフ索引型探索法は、探索時は高速であるものの、索引構築時には多大な計算量を要する。例えば、探索対象のオブジェクト（頂点）数がn個のオブジェクト集合に対して、最も素朴な方法を用いて厳密なK最近傍グラフを構築すると、非類似度計算にO(n2)の時間計算量を要する。この計算負荷を緩和するため、近似K最近傍グラフを構築する発見的方法が提案されている（非特許文献４）。これらの方法は、与えられた探索対象オブジェクト集合（頂点集合）に対して、一括処理でK最近傍グラフを構築する方法である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第4774016号公報
【特許文献２】特許第4774019号公報
【非特許文献】
【０００６】
【非特許文献１】K. Aoyama, K. Saito, T. Yamada, and N. Ueda, "Fast similarity search in small-world networks," Int. Workshop Complex Networks (CompleNet 2009), pp. 185-196, 2009.
【非特許文献２】K. Aoyama, K. Saito, H. Sawada, and N. Ueda, "Fast approximate similarity search based on degree-reduced neighborhood graphs," ACM SIGKDD Conf. Knowledge Discovery and Data Mining, 2011.
【非特許文献３】K. Aoyama, A. Ogawa, T. Hattori, T. Hori, and A. Nakamura, "Graph index based query-by-example search on a large speech data set" Proc. Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), pp. 8520-8524, 2013.
【非特許文献４】W. Dong, M. Charikar, and K. Li, "Efficient K-nearest neighbor graph construction for generic similarity measures," Int. World Wide Web Conf., 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
構築されたK最近傍グラフに、新たな1つのオブジェクト（頂点）を追加する際には、n+1個のオブジェクトを対象に一括処理をする必要があり、多大な計算量を要するという問題があった。即ち、1つの新たなオブジェクト（頂点）を追加するオンライン処理方法又は逐次処理方法が求められていた。
【０００８】
以下、厳密又は近似K最近傍グラフ、及び、厳密又は近似K最近傍グラフと類似構造のグラフを近傍グラフと称し、オブジェクトと頂点との用語を、特に指定しない場合は、区別なく使用する。つまり、オブジェクトと頂点とを同一視する。また、各頂点についてK個の頂点との間に辺を張る近傍グラフを、厳密なK最近傍グラフ及び近似的なK最近傍グラフを含め、総じてK近傍グラフと称する。
【０００９】
本発明は上記の点に鑑みてなされたものであり、新たな頂点を近傍グラフに追加するために要する時間計算量を削減することを目的とする。
【課題を解決するための手段】
【００１０】
開示の技術によれば、近傍グラフと、当該近傍グラフに追加頂点として追加するオブジェクトとに基づいて、前記近傍グラフにおける前記追加頂点のK近傍頂点集合を探索し、当該K近傍頂点集合を出力するK近傍頂点探索部と、
前記近傍グラフと、前記追加頂点と、前記追加頂点のK近傍頂点集合とに基づいて、当該近傍グラフ中の頂点であって、当該頂点のK近傍頂点集合に前記追加頂点が含まれる可能性のある頂点の集合である頂点候補集合を選択し、当該頂点候補集合を出力する頂点選択部と、
前記頂点候補集合の各頂点のK近傍頂点集合を用いて前記近傍グラフの全頂点に関するK近傍頂点集合を再構築し、前記追加頂点のK近傍頂点集合を前記再構築したK近傍頂点集合に追加することにより、更新された近傍グラフを作成する近傍グラフ更新部と
を備えることを特徴とするグラフ更新装置が提供される。
【発明の効果】
【００１１】
開示の技術により、新たな頂点を近傍グラフに追加するために要する時間計算量を削減することができる。
【図面の簡単な説明】
【００１２】
【図１】近傍グラフ更新装置１００の構成図である。
【図２】近傍グラフ更新装置１００のハードウェア構成図である。
【図３】頂点選択部１２０の動作例を説明するためのフローチャートである。
【図４】第１のフィルターを説明するための図である。
【図５】第２のフィルターを説明するための図である。
【図６】第３のフィルターを説明するための図である。
【図７】第４のフィルターを説明するための図である。
【図８】近傍グラフ更新部１３０の動作例を説明するためのフローチャートである。
【図９】近傍グラフ更新部１３０の機能詳細例を示す図である。
【図１０】近傍グラフ更新部１３０の動作例を説明するためのフローチャートである。
【図１１】K-DRグラフ構築法を説明するための図である。
【図１２】近似K-DRグラフを更新する場合の速度性能を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態（本実施の形態）を詳細に説明する。以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１４】
（システム構成、動作概要）
図１は、本実施の形態における近傍グラフ更新装置１００の構成図である。図１を用いて近傍グラフ更新装置１００の構成及び動作概要を説明する。
【００１５】
図１に示すとおり、近傍グラフ更新装置１００は、K近傍頂点探索部１１０と頂点選択部１２０と近傍グラフ更新部１３０とを主な構成要素として含む。近傍グラフ更新装置１００の各部の動作概要は次のとおりである。
【００１６】
K近傍頂点探索部１１０には、近傍グラフ（ここではK近傍グラフ）、追加するオブジェクト（K近傍グラフに対して追加する新たな頂点に相当）等が入力される。K近傍頂点探索部１１０は、新たな頂点を探索のクエリとみなし、当該頂点が追加されるK近傍グラフをグラフ索引とするグラフ索引型探索を実施し、追加する頂点のK近傍頂点をK近傍グラフの中から見つける。例えば、K近傍頂点探索部１１０は、追加する頂点から最も近いK個の頂点の集合（索引であるグラフの頂点の部分集合）を見つける。
【００１７】
頂点選択部１２０は、追加する頂点が現時点でのK番目に近い近傍頂点よりも近くなる可能性のある頂点をn個の全頂点の中から選択する。頂点選択部１２０は、追加する頂点とn個の頂点各々との距離計算を避けるために、フィルターを用いる。このフィルターにより、m（<n）個の頂点とのみ距離計算を実行することにより、時間計算量を低減する。当該フィルターは、例えば、入力されたK近傍グラフの全頂点の集合から、追加する頂点をK近傍頂点としない頂点を除外するフィルターである。ここで、「追加する頂点をK近傍頂点としない頂点を除外する」とは、追加する頂点をK近傍頂点としない頂点のみを除外するような厳密な除外であってもよいし、除外する頂点に、追加する頂点をK近傍頂点としない頂点に加えて、追加する頂点をK近傍頂点とする頂点が含まれるような近似的な除外であってもよい。このように、追加する頂点をK近傍頂点としない頂点を除外することで、頂点を追加した近傍グラフを作成する際に、追加する頂点との距離計算を行う対象とする頂点の数を削減でき、時間計算量を低減できる。
【００１８】
近傍グラフ更新部１３０は、頂点選択部１２０により選択された頂点集合等を用いることで、新たな頂点が追加された近傍グラフを生成し、出力する。当該近傍グラフは、例えば、近似次数低減K最近傍グラフ（近似K‐DRグラフ）である。
【００１９】
（ハードウェア構成例）
上述した近傍グラフ更新装置１００は、コンピュータ等の装置に本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、近傍グラフ更新装置１００が有する機能は、コンピュータに内蔵されるＣＰＵやメモリ等のハードウェア資源を用いて、近傍グラフ更新装置１００で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メール等、ネットワークを通して提供することも可能である。
【００２０】
図２は、近傍グラフ更新装置１００のハードウェア構成例を示す図である。図２の近傍グラフ更新装置１００は、それぞれバスＢで相互に接続されているドライブ装置１０００、補助記憶装置１００２、メモリ装置１００３、ＣＰＵ１００４、インタフェース装置１００５、表示装置１００６、及び入力装置１００７等を有する。なお、表示装置１００６及び入力装置１００７を備えないこととしてもよい。
【００２１】
近傍グラフ更新装置１００での処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ又はメモリカード等の記録媒体１００１によって提供される。プログラムを記憶した記録媒体１００１がドライブ装置１０００にセットされると、プログラムが記録媒体１００１からドライブ装置１０００を介して補助記憶装置１００２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１００１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１００２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２２】
メモリ装置１００３は、プログラムの起動指示があった場合に、補助記憶装置１００２からプログラムを読み出して格納する。ＣＰＵ１００４は、メモリ装置１００３に格納されたプログラムに従って近傍グラフ更新装置１００に係る機能を実現する。インタフェース装置１００５は、ネットワークに接続するためのインタフェースとして用いられる。表示装置１００６はプログラムによるＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）等を表示する。入力装置１００７はキーボード及びマウス、ボタン、又はタッチパネル等で構成され、様々な操作指示を入力させるために用いられる。
【００２３】
以下、図１に示した近傍グラフ更新装置１００の処理動作をより詳細に説明する。
【００２４】
（近傍グラフ更新装置１００への入力データ）
近傍グラフ更新装置１００には下記の1)〜3)に示すデータが入力される。
【００２５】
1) 更新される近傍グラフG=(V,E)。但しVは頂点集合、Eは辺集合を表す。また、K近傍グラフの場合はKの値も必然的にデータとして含まれるとする。
【００２６】
2) 近傍グラフに追加する頂点に相当するオブジェクトデータ。なお、オブジェクトデータを単に「オブジェクト」と称してもよい。
【００２７】
3) 上記近傍グラフを構成する頂点に対応するオブジェクトと辺の生成に利用されるオブジェクト間の関係性の尺度。オブジェクト間の関係性の尺度として、例えば、ユークリッド距離、マンハッタン距離などの距離、カルバックライブラーダイバージェンス：Kullback-Leibler divergenceに代表される非類似度、コサイン類似度のような類似度、などがある。
【００２８】
入力データとして、近傍グラフと追加するオブジェクト（これを近傍グラフでの"クエリ頂点"とも呼ぶ）とは必須であるが、3)のオブジェクト等は、1)の近傍グラフに繰り込むこともできるので、1)と3)の入力を合わせて、近傍グラフとすることもできる。以降、一例として、2つのオブジェクト（頂点）の関係性の尺度として距離を選択した場合を用いる。但し、非類似度等への一般化のために、スケーリング因子（scaling factor）を導入する例も説明する。
【００２９】
なお、本実施の形態で説明する処理内容は、関係性の尺度に依存せずに基本的に同様であるため、本明細書及び特許請求の範囲における「距離」を、上述した各種の関係性の尺度を総称した用語と解釈してもよい。
【００３０】
（近傍グラフ更新装置１００からの出力）
近傍グラフ更新装置１００は、1)〜3)の入力データに基づいて、2)の追加する頂点が含まれ、更新された近傍グラフを出力する。
【００３１】
（近傍グラフ更新装置１００の動作の詳細）
図１に示したとおり、近傍グラフ更新装置１００は、K近傍頂点探索部１１０と頂点選択部１２０と近傍グラフ更新部１３０とを含む。
【００３２】
K近傍頂点探索部１１０は、上述した3種類のデータを入力とし、追加する頂点（vq）のK近傍頂点集合を出力する。即ち、K近傍頂点探索部１１０は、近傍グラフにおけるvqに最も近い頂点から距離の昇順にK個の頂点を探索し、探索したK個の頂点の集合であるK近傍頂点集合を出力する。
【００３３】
頂点選択部１２０は、1)の近傍グラフ、2)の追加する頂点、及びK近傍頂点探索部１１０の出力である追加頂点のK近傍頂点集合を入力とし、自らのK近傍頂点集合が修正される可能性のある頂点を近傍グラフの全頂点から選択し、選択された頂点集合を出力する。自らのK近傍頂点集合が修正される可能性のある頂点の集合は、自らのK近傍頂点集合に新たな頂点（＝追加する頂点）が含まれる可能性のある頂点の集合と称することもできる。
【００３４】
近傍グラフ更新部１３０は、1)の近傍グラフ、2)の追加する頂点、K近傍頂点探索部１１０の出力である追加する頂点のK近傍頂点集合、及び頂点選択部１２０の出力である選択された頂点集合を入力とし、新たな頂点が追加された近傍グラフを作成し、出力する。
【００３５】
以下、各構成部の処理動作の例をより詳細に説明する。
【００３６】
＜K近傍頂点探索部１１０＞
図１に示すとおり、K近傍頂点探索部１１０には前述したデータ1)〜3)が入力される。K近傍頂点探索部１１０は、例えばグラフ索引型類似探索法を用いて、追加する頂点のK近傍頂点を探索する。すなわち、グラフ索引型類似探索法を用いる場合において、K近傍頂点探索部１１０は、追加する頂点を探索のクエリとみなし、当該頂点が追加されるK近傍グラフをグラフ索引とするグラフ索引型探索を実施する。探索アルゴリズムとして、例えば、非特許文献１に記載の(a)最良優先探索（Best-first search: BSと略す）や、非特許文献２に記載の(b)多初期頂点開始貪欲探索（Multi-start greedy search: MSGSと略す）などの高速グラフ探索アルゴリズムを用いることができる。
【００３７】
(a)のBSは、与えられた初期頂点から貪欲探索（現頂点の隣接頂点のうち最もクエリ頂点に近い頂点を次の現頂点とし、この探索を繰り返し、現頂点が最もクエリ頂点に近くなった時点で終了する方法）を実行し、貪欲探索が終了した時点で、今までクエリ頂点と距離計算を実行した頂点のうち、隣接頂点がクエリとの距離を計算されていない頂点であって、現頂点の次にクエリ頂点に近い頂点を次の現頂点とする方法であり、予め設定された計算コストに達した時点で終了する探索法である。
【００３８】
一方、(b)のMSGSは並列処理を利用し、予め設定した数の複数初期頂点から貪欲探索を開始し、貪欲探索が終了した時点で終了し、複数の探索経路の各々で発見したクエリ頂点に近い頂点集合の合併集合に対し、距離に基づき昇順に最も近い頂点からK個の頂点をK近傍頂点とする。また、MSGSにおいては、貪欲探索が終了したものから、終了時の頂点を起点とし、予め設定した終了条件に基づき、幅優先探索（Breadth-first search: BFS）を実行しても良い。BFSの終了条件としては、計算コスト、探索深さ、K近傍頂点集合不変などがある。
【００３９】
なお、ここで説明したグラフ索引型類似探索法は、発見的方法又は近似探索法であるため、求める解（K近傍頂点集合）の精度は時間計算量（例えば、距離計算コスト）に依存する。例えば、最良優先探索法（BS）で計算コストをn（近傍グラフの頂点数）に設定すると、全探索（linear scan法、brute-force法）と一致し、厳密なK近傍頂点集合を得ることができる。
【００４０】
＜頂点選択部１２０＞
次に、頂点選択部１２０の入出力及び処理内容を説明する。図１に示したように、頂点選択部１２０には、K近傍グラフ、追加する新たな頂点（vq）、及び、K近傍頂点探索部１１０の出力である、新たな頂点（vq）のK近傍頂点集合が入力される。これら入力データに基づいて、頂点選択部１２０は、図３のフローチャートに沿った手順を実行することにより、新たな頂点（vq）が、自らのK近傍になる可能性のある（K近傍頂点候補である）頂点（vx）を、入力されたK近傍グラフの頂点集合（V, |V|=n）の要素である頂点の中から選択する（vx∈V）。
【００４１】
なお、図３に示すように、第４のフィルターについては、挿入箇所例１〜３として示されるＡ、Ｂ、Ｃのいずれかの箇所で適用される。また、第４のフィルターを用いないこととしてもよい。また、ここでは、第１〜第４のフィルターを使用しているが、これは例であり、これらのうちの１つ又は２つ又は３つのフィルターを適用してもよいし、第１〜第４のフィルターに加えて、更なるフィルターを適用してもよい。
【００４２】
図３のＳ１０１において、頂点選択部１２０は、第１のフィルターを適用する。ここでは、頂点選択部１２０は、新たな頂点（vq ）のK近傍頂点集合（Bq）の要素であって（vx∈Bq）、自ら（vx）のK番目近傍頂点までの距離（max_dist）が、vqとvxとの距離（dist(vq,vx)）よりも小さい頂点（vx）を候補から除く。
【００４３】
第１のフィルターの適用の具体例を図４に示す。図４（ａ）は、第１のフィルターにより、頂点（vx）が頂点候補から除外される場合の例を示している。図４（ａ）に示す頂点（vx）について、図示されるように、dist(vq,vx)は、頂点（vx）と自ら（vx）のK番目近傍頂点との距離（max_dist）よりも大きい。よって、頂点（vx）が選択候補から除外される。この場合、新たな頂点（vq ）は当該頂点（vx）のK近傍頂点になり得ないからである。
【００４４】
図４（ｂ）は、頂点（vx）が第１のフィルターを通過する場合の例を示している。図示されるように、dist(vq,vx)は、頂点（vx）と自ら（vx）のK番目近傍頂点との距離（max_dist）よりも小さい。よって、頂点（vx）は第１のフィルターを通過する。
【００４５】
第１のフィルターは、距離空間が定義される場合、即ち、頂点間の関係性が距離公理を充足する場合、dist(vq,vx)>max_distならば、vqはvxのK近傍頂点ではないことに基づくものである。
【００４６】
図３のＳ１０２において、頂点選択部１２０は、第２のフィルターを適用する。ここでは、頂点選択部１２０は、新たな頂点（vq）のK近傍頂点集合（Bq）と自ら（vx）のK近傍頂点集合（Bx）との共通集合（intersection）が空集合である（Bq∩Bx =空集合）頂点（vx）を選択候補から除く。
【００４７】
第２のフィルターの適用の具体例を図５に示す。図５（ａ）は、第２のフィルターにより、頂点（vx）が頂点候補から除外される場合の例を示している。図示されるように、この場合、新たな頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合は空である。よって、当該頂点（vx）は頂点候補から除外される。
【００４８】
図５（ｂ）は、頂点（vx）が第２のフィルターを通過する場合の例を示している。図示されるように、この場合、新たな頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合は空集合ではなく、この例では２つの頂点を有している。よって、当該頂点（vx）は選択候補から除外されない。ただし、図５（ｂ）の例の場合、頂点（vx）は第２のフィルターを通過するが、新たな頂点（vq）は当該頂点（vx）のK近傍頂点ではない。
【００４９】
第２のフィルターの適用方法は、"A neighbor of a neighbor is also likely to be a neighbor."の考え方を利用した発見的方法であり、データ分布に依存して、第２フィルターで除去される頂点であっても、厳密に計算した場合、vqがvxのK近傍頂点である場合がある。 
図３のＳ１０３において、頂点選択部１２０は、第３のフィルターを適用する。なお、第３のフィルターは、第２のフィルターの後に適用される。従って、第３のフィルターの判断対象となる頂点（vx）に関し、新たな頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合は空集合ではない。
【００５０】
ここでは、頂点選択部１２０は、新たな頂点（vq）のK近傍頂点集合（Bq）の要素ではなく、自ら（vx）のK番目近傍頂点までの距離（max_dist）が、頂点（vq）と頂点（vx）との距離の下限値（LB(vq,vx)）よりも小さいか等しい頂点（vx）を候補から除く。
【００５１】
頂点（vq）と頂点（vx）との距離の下限値（LB(vq,vx)）とは、頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合の頂点が複数ある場合においては、当該複数の頂点のうち、｜（頂点（vq）との距離）‐（頂点（vx）との距離）|が最大となる頂点について当該｜（頂点（vq）との距離）‐（頂点（vx）との距離）|の値である。頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合の頂点が１つである場合においては、当該頂点についての｜（頂点（vq）との距離）‐（頂点（vx）との距離）|が下限値（LB(vq,vx)）となる。
【００５２】
なお、頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合の頂点が複数ある場合において、｜（頂点（vq）との距離）‐（頂点（vx）との距離）|が最大となる頂点について当該｜（頂点（vq）との距離）‐（頂点（vx）との距離）|をLB(vq,vx)とすることは一例である。例えば、頂点（vq）のK近傍頂点集合（Bq）と、頂点（vx）のK近傍頂点集合（Bx）との共通集合の頂点が複数ある場合において、当該複数の頂点のうちの任意の頂点についての｜（頂点（vq）との距離）‐（頂点（vx）との距離）|をLB(vq,vx)としてもよい。
【００５３】
第３のフィルターの適用の具体例を図６に示す。図６（ａ）は、第３のフィルターにより、頂点（vx）が頂点候補から除外される場合の例を示している。図６（ａ）に示す頂点（vx）について、図示されるように、LB(vq,vx)=|dist(vq,v1 )−dist(vx,v1)|は、max_distよりも大きいので、当該頂点（vx）は選択候補から除外される。
【００５４】
図６（ｂ）は、頂点（vx）が第３のフィルターを通過する場合の例を示している。図６ｂａ）に示す頂点（vx）について、図示されるように、LB(vq,vx)=maxJ=1,2{|dist(vq, vj)−dist(vx,vj)|}（図６（ｂ）の例ではLB(vq,vx)=|dist(vq,v1)−dist(vx,v1)|）は、max_distよりも小さいので、当該頂点（vx）は第３のフィルターを通過する。なお、図６（ｂ）の例は、頂点（vx）は第３のフィルターを通過するが、vqはvxのK近傍頂点ではない例を示している。
【００５５】
第３のフィルターは、距離空間が定義される場合、即ち、頂点間の関係性が距離公理を充足する場合、LB(vq,vx)≧max_distならば、vqはvxのK近傍頂点ではないことに基づいている。
【００５６】
図３のＡ、Ｂ、あるいはＣにおいて第４のフィルターを適用してもよい。第４のフィルター適用において、頂点選択部１２０は、対象頂点（vx）が追加頂点（vq ）のK近傍の外側にあり、追加頂点（vq ）のK番目近傍頂点までの距離（K近傍球半径）よりも対象頂点（vx）のK近傍球半径が小さい場合、対象頂点（vx）を選択しない。つまり、フィルターで除去される。第４のフィルターの第３のフィルターとの相違は、第４のフィルターでは、共通集合に含まれる頂点の有無に依存せず、距離の下限値ではなく、球の半径の大小関係で判定するという点である。
【００５７】
第４のフィルターの適用の具体例を図７に示す。図７（ａ）は、第４のフィルターにより、頂点（vx）が頂点候補から除外される場合の例を示している。図７（ａ）に図示されるように、追加頂点（vq ）のK近傍球半径（（dist(vq,vqK)）は、対象頂点（vx）のK近傍球半径よりも大きい。よって、頂点（vx）は選択候補から除去される。
【００５８】
図７（ｂ）は、頂点（vx）が第４のフィルターを通過する場合の例を示している。図７（ｂ）に図示されるように、追加頂点（vq ）のK近傍球半径（（dist(vq,vqK)）は、対象頂点（vx）のK近傍球半径よりも小さい。よって、頂点（vx）は第４のフィルターを通過する。
【００５９】
第１のフィルターを通過した頂点（vx）は、既にvqとvxとの厳密距離（dist(vq,vx)）を計算済であり、追加頂点（vq ）のK近傍頂点集合の要素であるから、図３のＳ１０４における頂点集合に加える。一方、第２、第３、第４のフィルターを通過した頂点（vx）は、厳密に追加頂点（vq ）のK近傍にあるかどうか不明である。よって、図３のＳ１０４において、頂点選択部１２０は、第２、第３のフィルター（あるいは第２、第３、第４のフィルター）を通過した頂点（vx）に関して、新たに追加する頂点（vq）との厳密距離を計算し、新たな頂点（vq）が自らのK近傍内の距離にあるならば、当該頂点（vx）を選択し、選択された頂点として頂点集合に加える。
【００６０】
＜近傍グラフ更新部１３０＞
次に、近傍グラフ更新部１３０の入出力及び処理内容を説明する。図１に示したように、近傍グラフ更新部１３０には、近傍グラフ（K近傍グラフ）、追加する新たな頂点、K近傍頂点探索部１１０の出力である新たな頂点のK近傍頂点集合、及び、頂点選択部１２０の出力である、自らのK近傍頂点集合に新たな頂点が含まれる可能性のある頂点の集合が入力される。これら入力データに基づいて、近傍グラフ更新部１３０は、図８のフローチャートに沿った手順を実行することにより、新たな頂点が追加された近傍グラフを作成し、出力する。
【００６１】
図８のＳ２０１において、近傍グラフ更新部１３０は、選択された頂点集合の各頂点のK近傍頂点集合に基づき、入力された近傍グラフの全頂点に関するk近傍頂点集合を再構築する。より詳細には、一例として、近傍グラフ更新部１３０は、入力された近傍グラフにおける選択された頂点集合の各頂点について、追加された新たな頂点を含む他の各頂点との間の距離を計算し、K近傍頂点集合を求める。そして、近傍グラフ更新部１３０は、当該K近傍頂点集合と、入力された近傍グラフにおける選択された頂点集合以外の各頂点のK近傍頂点集合（近傍グラフのデータとして既に有しているもの）とを合わせることにより、入力された近傍グラフの全頂点に関するK近傍頂点集合を再構築する。
【００６２】
Ｓ２０２において、近傍グラフ更新部１３０は、新たな頂点のK近傍頂点集合をＳ２０１で再構築された頂点集合に追加し、近似有向近傍グラフを構築する。
【００６３】
Ｓ２０３において、近傍グラフ更新部１３０は、入力された近傍グラフが、有向近傍グラフでない場合は、必要に応じ、当該入力された近傍グラフと同じ構造の近傍グラフを、当該近似有向近傍グラフを基に再構築する。
【００６４】
Ｓ２０４において、近傍グラフ更新部１３０は、新たな頂点が追加された近傍グラフを出力する。
【００６５】
なお、Ｓ２０３において、近傍グラフ更新部１３０が無向K近傍グラフを構築する場合は、Ｓ２０２までに近似有向K近傍グラフを構築し、当該有向K近傍グラフを、無向化の定義に従って、無向K近傍グラフとする。無効化の定義とは、例えば、相互辺（mutual edge）の場合は無向辺とする、出力辺又は入力辺の何れかが存在する場合は、無向辺を張るなどのルールである。
【００６６】
また、Ｓ２０３において、近傍グラフ更新部１３０が、非特許文献１、２、３で使用されている次数低減K最近傍グラフ（degree-reduced K nearest neighbor graph：K-DR graph）を構築する場合は、Ｓ２０２までに構築した近似有向K近傍グラフに既存のK-DRグラフ構築アルゴリズムを適用する。
【００６７】
このように、近傍グラフ更新部１３０は、Ｓ２０２で構築される近似有向近傍グラフを利用することで、種々の近傍グラフを構築することができる。
【００６８】
＜近傍グラフ更新部１３０の具体例＞
次に、近傍グラフ更新部１３０のより具体的な例として、近傍グラフ更新部１３０が近似次数低減K最近傍グラフを構築する場合の構成及び処理内容の例を説明する。
【００６９】
図９は、近傍グラフ更新部１３０が近似次数低減K最近傍グラフを構築する場合における近傍グラフ更新部１３０の構成を示す図である。図９に示すように、入力データについては、前述した近傍グラフ更新部１３０に入力される入力データと同じである。図９の場合には、近傍グラフ更新部１３０は、近似次数低減K最近傍グラフを出力する。
【００７０】
図９に示すように、当該近傍グラフ更新部１３０は、有向K近傍グラフ生成部１３１と、次数低減K最近傍グラフ生成部１３２（以降、K-DRグラフ生成部１３２と称する）とを有する。当該近傍グラフ更新部１３０の動作を図１０、及び図１１のフローチャートを参照して説明する。
【００７１】
図１０のＳ３０１において、有向K近傍グラフ生成部１３１は、選択された頂点集合の各頂点のK近傍頂点集合に基づき、入力近傍グラフの全頂点に関するK近傍頂点集合を再構築する。より詳細には、一例として、有向K近傍グラフ生成部１３１は、入力された近傍グラフにおける選択された頂点集合の各頂点について、追加された新たな頂点を含む他の各頂点との間の距離を計算し、K近傍頂点集合を求める。そして、近傍グラフ更新部１３０は、当該K近傍頂点集合と、入力された近傍グラフにおける選択された頂点集合以外の各頂点のK近傍頂点集合（近傍グラフのデータとして既に有しているもの）とを合わせることにより、入力された近傍グラフの全頂点に関するK近傍頂点集合を再構築する。ここでは、入力近傍グラフに含まれる頂点のうちに、out-going edge（出力辺）の接続先として新たな頂点を含む頂点が存在する。
【００７２】
Ｓ３０２において、有向K近傍グラフ生成部１３１は、新たな頂点のK近傍頂点集合を、Ｓ３０１で再構築された全頂点に関するK近傍頂点集合に追加し、近似有向K近傍グラフ（又は近似有向K近傍リスト）を作成する。
【００７３】
Ｓ３０３において、K-DRグラフ生成部１３２は、有向K近傍グラフ生成部１３１により作成された近似有向K近傍グラフ（又は近似有向K近傍リスト）を入力として、例えば非特許文献１、２に記載のアルゴリズムを適用することで、新たな頂点が追加された近似K-DRグラフを生成する。
【００７４】
Ｓ３０４において、K-DRグラフ生成部１３２は、新たな頂点が追加された近似K-DRグラフを出力する。
【００７５】
Ｓ３０２で作成される近似有向K近傍リストは、各頂点について、距離の昇順にK個の近傍頂点が並べられたリストである。当該近似有向K近傍リストのことを近似有向K近傍グラフと称してもよい。
【００７６】
非特許文献１、２に記載のアルゴリズムを適用して近似K-DRグラフを作成する場合における概要処理手順を図１１のフローチャートを参照して説明する。
【００７７】
Ｓ４０１において、K-DRグラフ生成部１３２は、有向K近傍グラフ生成部１３１により生成された近似有向K近傍リストを用い、各頂点について最近傍頂点（k=1の頂点、1<= k<=K）に無向辺を張り、1-NNグラフを構築する。k=2とする。
【００７８】
Ｓ４０２において、K-DRグラフ生成部１３２は、各頂点（起点と呼ぶ）について、2番目に近い頂点を、辺を張る頂点候補とする。当該2番目に近い頂点から起点へ、既存の辺をより近い頂点の方へ辿ることで到達できる（即ち、貪欲探索法で到達可能である）ならば無向辺を生成せず、到達できない場合に限り無向辺を生成する。この操作を全ての頂点に行うことにより、2-DRグラフを構築する。
【００７９】
Ｓ４０３において、kをk+1とする。Ｓ４０４において、(k-1)-DRグラフが構築されているとする（繰り返しの最初であれば2-DRグラフが構築されている）。K-DRグラフ生成部１３２は、各頂点についてk番目に近い頂点を、辺を張る候補頂点とする。当該k番目に近い頂点から起点へ、貪欲探索法で到達可能ならば、無向辺を生成せず、到達できないときに限り無向辺を起点と当該k番目に近い頂点の間に生成する。この操作を全ての頂点に行うことにより、k-DRグラフを構築する。
【００８０】
K-DRグラフ生成部１３２は、Ｓ４０３とＳ４０４の処理をk=Kになるまで繰り返す（Ｓ４０５）。Ｓ４０５においてk=Kであれば処理を終了する。
【００８１】
（関係性尺度として非類似度等を用いる場合）
ここまでは、2頂点間の関係性の尺度として距離を用いた場合について説明した。距離公理を充足しないダイバージェンスのような非類似度を用いる場合も多々ある。そのような場合、正数であるスケーリング因子（α>0）を導入する。特に、スケーリング因子の導入により、頂点選択部１２０の第１のフィルターと第３のフィルターと判定条件は次のようになる。
【００８２】
第１のフィルターで除去される場合：dist(vq,vx)>max_dist×α1
第３のフィルターで除去される場合：LB(vq,vx)≧max_dist×α3
各フィルターのαは異なっても良く。必ずしも一致させる必要はない。つまり、上記の例でいえば、α1とα3は同じでもよいし、異なってもよい。
【００８３】
（評価結果）
本実施の形態で説明した近傍グラフ更新装置１００を用いて実験を行った。実験には、手書き数字画像データベースMNISTのデータを使用した（http://yann.lecun.com/exdb/mnist/、Y.LeCun, L.Bottou, Y.Bengio, and P.Haffner.、
"Gradient-based learning applied to document recognition." Proceedings of the IEEE, 86(11):2278-2324, November 1998）。
【００８４】
対象データ、関係性尺度、入力グラフ、追加頂点、近傍グラフ更新装置１００として使用した計算機、及び評価法は下記のとおりである。
【００８５】
対象データ： 60,000画像の各々から抽出された60,000特徴ベクトル（784次元）、単位超球上の点として扱う；
距離： ユークリッド距離；
入力グラフ： K-DRグラフ（K=20,40,60,80,100)；
追加頂点：対象データには含まれない20個の特徴ベクトル（単位超球上の点）；
計算機：Intel Xeon E5-2697v3 2.6GHz, single thread実行；
評価法：1頂点追加の際に全頂点のK近傍頂点を更新する方法を基準法とし、20個の各々の頂点を追加に要する時間の平均を基準法と発明法（本発明を用いた方法）で求めた際の発明法が要した平均時間の基準法の平均時間に対する比率。
【００８６】
図１２は、上記の実験により評価結果を示す図である。すなわち、図１２は、近似K-DRグラフを更新する場合の速度性能を実験により評価した際の結果を表す図である。
【００８７】
図１２に示すように、Kが２０の場合には発明法は基準法よりも１０倍以上高速であり、K=100の場合であっても２倍程度高速である。このように本発明に係る技術により新たな頂点を近傍グラフに追加するための時間計算量を大幅に削減することができることがわかる。
【００８８】
（実施の形態の効果）
本実施の形態に係る近似グラフ更新装置１００のK近傍頂点探索部１１０は、グラフ索引型探索を行うため、実験的にO(log n)の時間計算量である。頂点選択部１２０は、フィルター機能が頂点数に直接関係していないため、O(1)の時間計算量である。従って、O(log n)の非常に少ない時間計算量で近傍グラフに頂点を追加し、近傍グラフを更新することができる。
【００８９】
また、対象データ数n以外に時間計算量に関係する変数となり得るKに関し、Kを変数として、頂点追加処理時間を実験により求めた。その結果、出力辺数Kの実用上の適用可能範囲で基準法よりも高速であった。
【００９０】
（実施の形態のまとめ）
以上、説明したように、本実施の形態によれば、近傍グラフと、当該近傍グラフに追加頂点として追加するオブジェクトとに基づいて、前記近傍グラフにおける前記追加頂点のK近傍頂点集合を探索し、当該K近傍頂点集合を出力するK近傍頂点探索部と、前記近傍グラフと、前記追加頂点と、前記追加頂点のK近傍頂点集合とに基づいて、当該近傍グラフ中の頂点であって、当該頂点のK近傍頂点集合に前記追加頂点が含まれる可能性のある頂点の集合である頂点候補集合を選択し、当該頂点候補集合を出力する頂点選択部と、前記頂点候補集合の各頂点のK近傍頂点集合を用いて前記近傍グラフの全頂点に関するK近傍頂点集合を再構築し、前記追加頂点のK近傍頂点集合を前記再構築したK近傍頂点集合に追加することにより、更新された近傍グラフを作成する近傍グラフ更新部とを備えることを特徴とするグラフ更新装置が提供される。
【００９１】
前記頂点選択部は、例えば、前記近傍グラフの頂点の集合から、前記追加頂点をK近傍頂点としない頂点を除外するためのフィルターを適用することで前記頂点候補集合を選択する。
【００９２】
前記近傍グラフ更新部は、前記更新された近傍グラフとして、近似次数低減K最近傍グラフを作成することとしてもよい。
【００９３】
また、本実施の形態により、コンピュータを、上述したグラフ更新装置における各部として機能させるためのプログラムが提供される。
【００９４】
以上、本実施の形態について説明したが、本発明はかかる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００９５】
１００  近傍グラフ更新装置
１１０  K近傍頂点探索部
１２０  頂点選択部
１３０  近傍グラフ更新部
１３１  有向K近傍グラフ生成部
１３２  次数低減K最近傍グラフ生成部
１０００  ドライブ装置
１００１  記録媒体
１００２  補助記憶装置
１００３  メモリ装置
１００４  ＣＰＵ
１００５  インタフェース装置
１００６  表示装置
１００７  入力装置
【図１】
2019197438.tif 000003
【図２】
2019197438.tif 000004
【図３】
2019197438.tif 000005
【図４】
2019197438.tif 000006
【図５】
2019197438.tif 000007
【図６】
2019197438.tif 000008
【図７】
2019197438.tif 000009
【図８】
2019197438.tif 000010
【図９】
2019197438.tif 000011
【図１０】
2019197438.tif 000012
【図１１】
2019197438.tif 000013
【図１２】
2019197438.tif 000014