特許ウォッチ

公開番号2025123835
公報種別公開特許公報(A)
公開日2025-08-25
出願番号2024019551
出願日2024-02-13
発明の名称情報処理装置、情報処理方法及びプログラム
出願人NTT株式会社,国立大学法人筑波大学
代理人弁理士法人志賀国際特許事務所
主分類G06F 16/906 20190101AFI20250818BHJP(計算;計数)
要約【課題】クラスタリングに要する時間を軽減すること。
【解決手段】本発明の一態様は、追加対象のデータポイントである追加データポイントが追加される前のデータポイントの集合、に対する階層的なクラスタリングによって生じたI個の階層のうち、クラスタの数がi番目に多いd次元の距離空間である第i階層における追加データポイントの最近傍のデータポイントを推定する第i最近傍データポイント推定処理を、クラスタリングによって生じた階層に対して実行する制御部、を備え、第i最近傍データポイント推定処理では、(d-1)次元の部分空間であって、属する第j階層のクラスタが同一である第i階層のデータポイントの集合それぞれに対して定められる部分空間であって、対応する集合を囲む部分空間それぞれを示す境界空間情報、に基づき第i階層における最近傍のデータポイントが推定される、情報処理装置である。
【選択図】図1
特許請求の範囲【請求項１】
追加対象のデータポイントである追加データポイントが追加される前のデータポイントの集合である追加前データポイント集合、に対する階層的なクラスタリングによって生じたＩ個（Ｉは１以上の整数）の階層のうち、ｉが２以上（ｉは１以上Ｉ以下の整数）の場合には第（ｉ－１）階層におけるクラスタの代表点がデータポイントとして分布しｉが１の場合には前記追加前データポイント集合の各データポイントが分布するｄ次元の距離空間（ｄは２以上の整数）であってクラスタの数がｉ番目に多いｄ次元の距離空間である第ｉ階層、における前記追加データポイントの最近傍のデータポイントである最近傍データポイントを推定する第ｉ最近傍データポイント推定処理を、前記クラスタリングによって生じたＩ個の階層の一部又は全部に対して実行する制御部、
を備え、
前記第ｉ最近傍データポイント推定処理では、距離空間における（ｄ－１）次元の部分空間であって、属する第ｊ階層（ｊはｉ以上Ｉ以下の整数）のクラスタが同一である第ｉ階層のデータポイントの集合それぞれに対して定められる部分空間であって、対応する前記集合を前記距離空間において囲む部分空間であって、空間の形状に関する所定の条件である形状条件を満たす部分空間それぞれを、少なくとも第ｉ階層から第（Ｉ－１）階層までの各階層について示す境界空間情報、に基づき前記第ｉ階層における前記最近傍データポイントが推定される、
情報処理装置。
続きを表示（約 3,500 文字）【請求項２】
前記第ｉ最近傍データポイント推定処理では、
前記境界空間情報が示す第（Ｉ－１）階層における部分空間のうち最も前記追加データポイントに近い部分空間を推定する事前第１処理と、
前記境界空間情報に基づき、前記境界空間情報が示す第ｋ階層（ｋはｉ以上Ｉ未満の整数）における部分空間のうち第ｋ階層における判定対象とされた部分空間の中では最も前記追加データポイントに近いと推定された部分空間、に囲まれる第ｉ階層のデータポイント、を囲む前記境界空間情報が示す第（ｋ－１）階層の部分空間、を第（ｋ－１）階層における判定対象として推定する第１種判定対象推定処理、を第（Ｉ－２）階層から第（ｉ－１）階層まで順に実行する第１処理と、
第（ｉ－１）層における第１種判定対象推定処理の実行によって第ｉ階層における判定対象として推定された前記境界空間情報が示す第ｉ階層における部分空間のうち、前記追加データポイントに最も近い部分空間である最近傍候補空間を判定する第２処理と、
前記最近傍候補空間に含まれる第ｉ階層のデータポイントと前記追加データポイントとの距離が最も短いデータポイント、と前記追加データポイントとの間の距離である最近傍候補距離を得る最近傍候補距離取得処理と、
前記最近傍候補距離に基づいて、前記第ｉ階層における最近傍データポイントを推定する第３処理と、
が実行され、
第（Ｉ－１）階層における前記判定対象は、前記事前第１処理の推定結果である、
請求項１に記載の情報処理装置。
【請求項３】
前記第３処理では、
前記第１種判定対象推定処理によって第（ｐ－１）階層（ｐは（ｉ＋１）以上Ｉ以下の整数）における判定対象とされた境界空間のうちの第（ｐ－１）階層対象空間以外の境界空間である第ｐ見落とし空間それぞれと前記追加データポイントとの間の距離を取得し、予め定められた距離であって更新可能な距離である基準距離よりも短い距離を与える第ｐ見落とし空間である第ｐ検討候補空間、があるか否かを取得した距離に基づいて判定する処理である第ｐ見落とし判定処理、を実行し、
第ｗ見落とし判定処理（ｗは（ｉ＋１）以上Ｉ未満の整数）によって第ｗ検討候補空間が無い、と判定された場合には、基準距離を更新することなく、第（ｗ＋１）見落とし判定処理を実行し、
前記第ｗ見落とし判定処理によって第ｗ検討候補空間があると判定された場合には、前記第ｗ検討候補空間によって囲まれる第ｉ階層のデータポイントを囲む第（ｗ－１）階層から第ｉ階層までの各境界空間、と前記追加データポイントと、の距離のうちの最小の距離へと基準距離を更新し、
第Ｉ見落とし判定処理によって第Ｉ検討候補空間が無い、と判定された場合に終了する、
第４処理と、
前記境界空間情報が示す境界空間のうちの前記追加データポイントからの距離が前記第４処理の結果得られた基準距離であるという境界空間条件を満たす境界空間に囲まれる第ｉ階層のデータポイントのうち、前記追加データポイントとの距離が最小のデータポイントを第ｉ階層における最近傍データポイントと推定する処理である第５処理と、
が実行され、
第ｉ見落とし判定処理における基準距離は、最近傍候補距離である、
請求項２に記載の情報処理装置。
【請求項４】
前記制御部は更に、前記境界空間情報に基づき、前記追加データポイントを最近傍とするデータポイントである第ｉ階層における被最近傍データポイント、を推定する、
請求項１に記載の情報処理装置。
【請求項５】
追加対象のデータポイントである追加データポイントが追加される前のデータポイントの集合である追加前データポイント集合、に対する階層的なクラスタリングによって生じたＩ個（Ｉは１以上の整数）の階層のうち、ｉが２以上（ｉは１以上Ｉ以下の整数）の場合には第（ｉ－１）階層におけるクラスタの代表点がデータポイントとして分布しｉが１の場合には前記追加前データポイント集合の各データポイントが分布するｄ次元の距離空間（ｄは２以上の整数）であってクラスタの数がｉ番目に多いｄ次元の距離空間である第ｉ階層、における前記追加データポイントを最近傍とするデータポイントである被最近傍データポイントを推定する第ｉ被最近傍データポイント推定処理を、前記クラスタリングによって生じたＩ個の階層の一部又は全部に対して実行する制御部、
を備え、
前記第ｉ被最近傍データポイント推定処理では、前記距離空間における（ｄ－１）次元の部分空間であって、属する第ｊ階層（ｊはｉ以上Ｉ以下の整数）のクラスタが同一である第ｉ階層のデータポイントの集合それぞれに対して定められる部分空間であって、対応する前記集合を前記距離空間において囲む部分空間であって、空間の形状に関する所定の条件である形状条件を満たす部分空間それぞれを、少なくとも第ｉ階層から第（Ｉ－１）階層までの各階層について示す境界空間情報、に基づき前記第ｉ階層における前記被最近傍データポイントが推定される、
情報処理装置。
【請求項６】
追加対象のデータポイントである追加データポイントが追加される前のデータポイントの集合である追加前データポイント集合、に対する階層的なクラスタリングによって生じたＩ個（Ｉは１以上の整数）の階層のうち、ｉが２以上（ｉは１以上Ｉ以下の整数）の場合には第（ｉ－１）階層におけるクラスタの代表点がデータポイントとして分布しｉが１の場合には前記追加前データポイント集合の各データポイントが分布するｄ次元の距離空間（ｄは２以上の整数）であってクラスタの数がｉ番目に多いｄ次元の距離空間である第ｉ階層、における前記追加データポイントの最近傍のデータポイントである最近傍データポイントを推定する第ｉ最近傍データポイント推定処理を、前記クラスタリングによって生じたＩ個の階層の一部又は全部に対して実行する制御ステップ、
を有し、
前記第ｉ最近傍データポイント推定処理では、距離空間における（ｄ－１）次元の部分空間であって、属する第ｊ階層（ｊはｉ以上Ｉ以下の整数）のクラスタが同一である第ｉ階層のデータポイントの集合それぞれに対して定められる部分空間であって、対応する前記集合を前記距離空間において囲む部分空間であって、空間の形状に関する所定の条件である形状条件を満たす部分空間それぞれを、少なくとも第ｉ階層から第（Ｉ－１）階層までの各階層について示す境界空間情報、に基づき前記第ｉ階層における前記最近傍データポイントが推定される、
情報処理方法。
【請求項７】
追加対象のデータポイントである追加データポイントが追加される前のデータポイントの集合である追加前データポイント集合、に対する階層的なクラスタリングによって生じたＩ個（Ｉは１以上の整数）の階層のうち、ｉが２以上（ｉは１以上Ｉ以下の整数）の場合には第（ｉ－１）階層におけるクラスタの代表点がデータポイントとして分布しｉが１の場合には前記追加前データポイント集合の各データポイントが分布するｄ次元の距離空間（ｄは２以上の整数）であってクラスタの数がｉ番目に多いｄ次元の距離空間である第ｉ階層、における前記追加データポイントを最近傍とするデータポイントである被最近傍データポイントを推定する第ｉ被最近傍データポイント推定処理を、前記クラスタリングによって生じたＩ個の階層の一部又は全部に対して実行する制御ステップ、
を備え、
前記第ｉ被最近傍データポイント推定処理では、前記距離空間における（ｄ－１）次元の部分空間であって、属する第ｊ階層（ｊはｉ以上Ｉ以下の整数）のクラスタが同一である第ｉ階層のデータポイントの集合それぞれに対して定められる部分空間であって、対応する前記集合を前記距離空間において囲む部分空間であって、空間の形状に関する所定の条件である形状条件を満たす部分空間それぞれを、少なくとも第ｉ階層から第（Ｉ－１）階層までの各階層について示す境界空間情報、に基づき前記第ｉ階層における前記被最近傍データポイントが推定される、
情報処理方法。
【請求項８】
請求項１から５のいずれか一項に記載の情報処理装置としてコンピュータを機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
クラスタリングはデータ集合に内在する性質の類似した部分集合を検出する手法であり、データ分析において重要な要素技術となっている。
【０００３】
＜ＦＩＮＣＨ＞
近年、ＦＩＮＣＨという階層型のクラスタリング手法が提案された（非特許文献１）。ＦＩＮＣＨでは、与えられたデータポイントごとに最近傍探索が行われ、最も近くにあるデータポイントとそのデータポイントを最近傍とするデータポイントとの間にエッジが張られグラフが構築される。そして各連結成分を一つのクラスタとすることが行われる。得られたクラスタの数が２以上である場合は各クラスタのデータの平均が新しいデータポイントとされ、ひとつ上の階層における入力として新たにクラスタが計算される。ＦＩＮＣＨではこれらの処理をクラスタの数が１になるまで行われる。その結果、粒度の異なるいくつかの階層からなるクラスタ階層が得られる。
【０００４】
ＦＩＮＣＨはｋ－ｍｅａｎｓ法などの他のクラスタリング手法と比較して少なくとも以下の４つの利点を有する。１つ目の利点は、高い精度で真のクラスタを自動的に決定できる点である。２つ目の利点は、ハイパーパラメータを必要としない点である。３つの目の利点は、異なるドメインのデータでも一般的に利用できる点である。４つ目の利点は、膨大なデータセットに拡張できる点である。
【０００５】
しかしながらＦＩＮＣＨは、蓄積されたデータ向けのクラスタリング手法であり、データが次々と流れてくるデータストリーミングに対してクラスタリングを行おうとすると膨大な計算時間を要するという問題がある。これはＦＩＮＣＨがデータ全体に対して最近傍探索を行うことでクラスタリングを行う手法であるため、データが追加されたときにはデータ全体に対して一から最近傍探索を行う必要があるからである。
【０００６】
＜ＦＩＮＣＨのより詳細＞
ＦＩＮＣＨのより詳細を説明する。ＦＩＮＣＨはデータストリームではなく静的に格納されたデータポイントに対する階層型のクラスタリング手法である（非特許文献１）。ＦＩＮＣＨでは、図１２に示すように、データセットから近傍グラフを生成し近傍グラフにおける各連結成分を１つのクラスタとする、ことが行われる。生成されたクラスタの数が１ではないとき、すなわち近傍グラフが２個以上の連結成分を持つとき、図１３に示す処理が実行される。すなわち、上の階層におけるデータポイントとしてクラスタの構成要素となる各データポイントの平均（すなわち重心）を用いて階層的なクラスタ構造を再帰的に得る、という計算が、クラスタの数が１になるまで実行される。
【０００７】
一つの階層においてデータセットからクラスタを計算することを１つのステップとし、ＦＩＮＣＨはこのステップを繰り返すことで階層的なクラスタ構造を得る。なお図１２において、同じデータポイントを最近傍に持つデータポイント間のエッジは表示されていない。この理由は、同じデータポイントを最近傍に持つデータポイントそれぞれは最近傍データポイントを介して互いに連結成分になるため、共有の最近傍間に張られるエッジの有無は連結成分に関係しないためである。
【０００８】
ＦＩＮＣＨでは、データセットの各データポイント間の距離を計算し、最近傍のデータポイントである最近傍データポイントと被最近傍のデータポイントである被最近傍データポイントとを求め、以下の式（１）で与えられる隣接行列から近傍グラフを構築する、ということが行われる。
【０００９】
TIFF
2025123835000002.tif
17
170
【００１０】
ここでκ
u
１
は、u番目のデータポイントに対して最近傍であるデータポイント（すなわちｕ番目のデータポイントにとっての最近傍データポイント）の識別子である。したがってＡ（ｕ，ｖ）は、ｕ番目のデータポイントにとってｖ番目のデータポイントが最近傍のデータポイントであるときと、ｕ番目のデータポイントがｖ番目のデータポイントにとっての被最近傍のデータポイントであるときと、ｕ番目のデータポイントの最近傍のデータポイントがｖ番目のデータポイントの最近傍のデータポイントであるときと、のいずれかの場合に、値が１である。一方、Ａ（ｕ，ｖ）はそれ以外の場合には、値が０である。
（【００１１】以降は省略されています）

関連特許