(57)【特許請求の範囲】
【請求項１】
ストリーミングクラスタリングにおけるデータクラスタリングの方法において、コンピュータが、
入力データ点を配置する特徴量空間を局所領域に分割し、
データ点が１点以上存在する局所領域に対し、それぞれ独立に代表点を決定し、
次に代表点が存在する局所領域にデータ点が追加された場合に、代表点と追加されたデータ点に基づいて重み付けを行い新たな代表点を決定し、
新たな代表点を用いてクラスタ数を制御する
各処理を実行することを特徴とするデータクラスタリング方法。
【請求項２】
前記分割する処理は、前記特徴量空間を、λ／√ｄ（λ：クラスタの粒度を定める閾値、ｄ：前記特徴量空間の次元数）を一辺の長さとするｄ次元超立方体である局所領域に分割する
ことを特徴とする請求項１に記載のデータクラスタリング方法。
【請求項３】
前記分割する処理は、前記特徴量空間を、クラスタの粒度を定める閾値λを直径としたｄ次元超球（ｄ：前記特徴量空間の次元数）である局所領域に分割する
ことを特徴とする請求項１に記載のデータクラスタリング方法。
【請求項４】
前記代表点を決定する処理および前記新たな代表点を決定する処理は、前記局所領域に保持する最大の保持点数を、前記次元数ｄとする
ことを特徴とする請求項２または請求項３に記載のデータクラスタリング方法。
【請求項５】
前記新たな代表点を決定する処理は、時分割されたデータ点に対して、既に決定された代表点と前記時分割されたデータ点に基づいて前記新たな代表点を決定する
ことを特徴とする請求項１から請求項４のいずれか１つに記載のデータクラスタリング方法。
【請求項６】
前記代表点を決定する処理および前記新たな代表点を決定する処理は、前記局所領域に保持する最大の保持点数を３×ｄ×ｌｏｇ（ｄ）とする
ことを特徴とする請求項２または請求項３に記載のデータクラスタリング方法。
【請求項７】
前記新たな代表点に含まれるデータ点の範囲を保持し、
新たな代表点の重み付けが、前記新たな代表点が含むデータ点の範囲を示すパラメータの２乗に反比例する値以上となった場合に、前記新たな代表点を異なるクラスタとなるように分割する
ことを特徴とする請求項１に記載のデータクラスタリング方法。
【請求項８】
前記新たな代表点に対し、前記代表点を１点とした場合の目的関数の期待値が、前記代表点を２点に分割した場合の目的関数の期待値以上となった場合に、前記代表点を分割する
ことを特徴とする請求項１に記載のデータクラスタリング方法。
【請求項９】
前記新たな代表点に対し、前記代表点の重み付けおよび前記代表点に含まれるデータ点と前記代表点との距離の期待値の積から得られる値が、前記代表点を分割した場合の第１代表点の重み付けおよび前記第１代表点に含まれるデータ点と前記第１代表点との距離の期待値の積と、前記代表点を分割した場合の第２代表点の重み付けおよび前記第２代表点に含まれるデータ点と前記第２代表点との距離の期待値の積と、クラスタの粒度を定める閾値から計算される項との和から得られる値以上となった場合に、前記代表点を分割する
ことを特徴とする請求項１に記載のデータクラスタリング方法。
【請求項１０】
前記分割する処理によって分割された代表点を含む代表点群を用いてクラスタリング処理を行う際に、同一のクラスタとして許容するクラスタ中心との距離の閾値を、代表点の重み付けの平方根に反比例した値とする
ことを特徴とする請求項７〜請求項９のいずれか１つに記載のデータクラスタリング方法。
【請求項１１】
前記分割する処理によって分割された代表点を含む代表点群を用いてクラスタリング処理を行う際に、２つの代表点を選択し、前記２つの代表点を１点に統合した場合の目的関数の期待値が、前記２つの代表点を１点に統合しない場合の目的関数の期待値より小さくなる場合に、前記２つの代表点を１点に統合する
ことを特徴とする請求項７〜請求項９のいずれか１つに記載のデータクラスタリング方法。
【請求項１２】
前記２つの代表点を選択する処理は、前記２つの代表点を１点に統合した場合の目的関数の期待値から、前記２つの代表点を１点に統合しない場合の目的関数の期待値を減じた値を持つコスト関数を定義し、前記コスト関数の値が最小値となる前記２つの代表点を選択する
ことを特徴とする請求項１１に記載のデータクラスタリング方法。
【請求項１３】
前記選択する処理によって選択された前記２つの代表点の前記コスト関数の値が０以下の場合に、前記２つの代表点を１点に統合する
ことを特徴とする請求項１２に記載のデータクラスタリング方法。
【請求項１４】
前記２つの代表点を１点に統合した場合の目的関数の期待値として、前記２つの代表点の重みの和と、前記２つの代表点に含まれるデータ点および統合先の代表点の距離の期待値との積と、クラスタ粒度を定める閾値から計算される項とを用い、前記２つの代表点を１点に統合しない場合の目的関数の期待値として、第１代表点の重み付けおよび前記第１代表点に含まれるデータ点と前記第１代表点との距離の期待値の積と、第２代表点の重み付けおよび前記第２代表点に含まれるデータ点と前記第２代表点との距離の期待値の積との和と、前記クラスタ粒度を定める閾値から計算される項と、を用いる
ことを特徴とする請求項１１または請求項１２に記載のデータクラスタリング方法。
【請求項１５】
前記コスト関数は、前記２つの代表点の重みと、前記２つの代表点の座標および前記２つの代表点の統合を行った場合の代表点の座標の距離との積から、閾値から計算される項を減じるものである
ことを特徴とする請求項１２に記載のデータクラスタリング方法。
【請求項１６】
前記代表点の重みと、前記代表点および所定のデータ点との距離の期待値との積の計算方法として、統合が生じた場合でも、ある代表点に統合された統合前の代表点の情報を記憶し、前記統合前の代表点および前記所定のデータ点の距離と統合後の代表点および前記所定のデータ点の距離との誤差を用いる
ことを特徴とする請求項１４または請求項１５に記載のデータクラスタリング方法。
【請求項１７】
前記２つの代表点を１点に統合した場合の目的関数の期待値として、前記２つの代表点の重みの和と、前記２つの代表点に含まれるデータ点および統合先の代表点の距離の期待値との積と、クラスタ粒度を定める閾値から計算される項とを用い、前記２つの代表点を１点に統合しない場合の目的関数の期待値として、第１代表点の重み付けおよび前記第１代表点に含まれるデータ点と前記第１代表点との距離の期待値の積と、第２代表点の重み付けおよび前記第２代表点に含まれるデータ点と前記第２代表点との距離の期待値の積との和と、前記クラスタ粒度を定める閾値から計算される項と、を用い、
前記コスト関数は、統合される代表点の重みと、前記統合される代表点と前記統合先の代表点との距離との積から、閾値から計算される項を減じるものであり、
選択される前記２つの代表点のうちいずれかの代表点を統合先の代表点として選択し、さらに、統合操作が終了すると、前記統合先の代表点の情報を用いて、前記統合先の代表点の座標を再計算する
ことを特徴とする請求項１２に記載のデータクラスタリング方法。
【請求項１８】
入力データ点を配置する特徴量空間を局所領域に分割する分割部と、
データ点が１点以上存在する局所領域に対し、それぞれ独立に代表点を決定する第１の決定部と、
次に代表点が存在する局所領域にデータ点が追加された場合に、代表点と追加されたデータ点に基づいて重み付けを行い新たな代表点を決定する第２の決定部と、
新たな代表点を用いてクラスタ数を制御する制御部と、を
有することを特徴とする情報処理装置。
【請求項１９】
ストリーミングクラスタリングにおけるデータクラスタリングプログラムにおいて、コンピュータに、
入力データ点を配置する特徴量空間を局所領域に分割し、
データ点が１点以上存在する局所領域に対し、それぞれ独立に代表点を決定し、
次に代表点が存在する局所領域にデータ点が追加された場合に、代表点と追加されたデータ点に基づいて重み付けを行い新たな代表点を決定し、
新たな代表点を用いてクラスタ数を制御する
処理を実行させることを特徴とするデータクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データクラスタリング方法などに関する。
【背景技術】
【０００２】
クラスタリング処理は、画像処理、音声認識、自然言語処理、センサデータ処理、ＤＮＡのシーケンスマイニング等、人工知能的な情報処理の基礎となる重要な手法である。かかるクラスタリング処理は、自己組織化写像やＷａｒｄ法に代表される階層型クラスタリング手法と、ｋ−ｍｅａｎｓ法に代表される非階層型クラスタリング手法に大別される。
【０００３】
階層型クラスタリング手法に関し、自己組織化写像は演算の収束保障が得られず取扱いが困難であるという欠点があり、Ｗａｒｄ法は全てのデータ点どうしの距離を演算する必要があり、特に大規模なデータに対しては計算困難であるという欠点がある。
【０００４】
他方、非階層型クラスタリング手法に関し、ｋ−ｍｅａｎｓ法は、クラスタ数を事前に与えておく必要があり、未知の環境に対して適用が困難であるという問題があった。近年、確率モデルであるノンパラメトリックベイズ法を基とし、データの複雑さに応じてクラスタ数を自動的に決定するＤＰ−ｍｅａｎｓ法が提案された。かかる手法は、非階層型クラスタリング手法でありながら、クラスタ数を動的に決定でき、かつ階層型クラスタリング方法とは異なり取扱いが容易であるという利点がある。
【０００５】
ここで、ＤＰ−ｍｅａｎｓ法の概要を、図３５を参照して説明する。図３５は、ＤＰ−ｍｅａｎｓ法の概要を示す図である。図３５に示すように、ＤＰ−ｍｅａｎｓ法は、それぞれのデータ点を最近傍のクラスタに割り振る。そして、データ点と最近傍クラスタとの距離がλ以上であるならば、新規クラスタを生成する。そして、クラスタ毎、割り振られたデータ点の重心を計算し、各クラスタの重心を更新する。
【０００６】
ＤＰ−ｍｅａｎｓ法は、以下の式（１）で示す目的関数値φ（ｘ，λ）を最適化するように、クラスタの重心を更新し、クラスタ数を更新する。但し、ｘは入力されるｄ次元のデータ点群、ｋはクラスタ数、λはクラスタ数を決定するハイパーパラメータである。
φ（ｘ，λ）＝ΣＤ（ｘ，ｕ）＋λ２ｋ・・・（１）
Ｄ（ｘ，ｕ）は、距離関数であり、例えば、以下の式（２）で示す二乗ユークリッド距離が該当する。
【数１】
0006707946.tif 000002
【０００７】
ところが、ＤＰ−ｍｅａｎｓ法は、目的関数値φ（ｘ，λ）の最適化を行う際に、全てのデータ点を使うため、全てのデータ点を保持しておく必要がある。また、計算処理の計算量は、保持するデータ点の数に比例して増大するため、大量のデータ点に対してクラスタリング処理を行う場合、計算量が非常に大きくなってしまう。このように全てのデータ点を保持した状態でクラスタリング処理を行う方法は、「バッチクラスタリング」と称する。
【０００８】
これに対して、全てのデータ点から代表点を抽出し、代表点を使ってクラスタリング処理を行う方法は、「ストリーミングクラスタリング」と称する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】国際公開第２０１１／１４２２２５号
【特許文献２】特開２００２−３０４６２６号公報
【特許文献３】特開２０１０−１３４６３２号公報
【特許文献４】特開２０１３−１８２３４１号公報
【特許文献５】特開平１０−１７１８２３号公報
【非特許文献】
【００１０】
【非特許文献１】B.Kulis  and  M.Jordan,“Revisiting  k-means:  New      Algorithms  via  Bayesian  Nonparametrics”,In  ICML2012.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、ストリーミングクラスタリングを行うためには、何らかの手段で代表点を選択することが必要であるが、単純にランダムに代表点を選択（ランダムサンプリング）すると、クラスタリングの精度が低下するという問題がある。これは、ランダムサンプリングでは、入力されるデータ点に不均衡が生じ、データ点が少ないクラスタが存在する場合、このクラスタの情報が失われやすいからである。
【００１２】
ストリーミングクラスタリングでクラスタリング精度が低下する例を、図３６を参照して説明する。図３６は、ストリーミングクラスタリングでクラスタリング精度が低下する例を示す図である。図３６では、各クラスタに含まれるデータ点が不均衡に存在する場合であり、各クラスタが８９８点、１００点、２点のデータ点を保持する場合とする。ここでは、全てのクラスタに対して等しい割合で１／１０のデータ点を代表点として選択した場合とする。すると、２点しかデータ点を含まないクラスタは、１点も選択されず、クラスタの情報が失われる。したがって、バッチクラスタリングを行った場合と異なるクラスタ数が出力されてしまい、クラスタリングの精度が大きく低下してしまう。
【００１３】
本発明は、１つの側面では、ストリーミングクラスタリングにおいて、精度の低下を抑制することを目的とする。
【課題を解決するための手段】
【００１４】
１つの態様では、データクラスタリング方法は、ストリーミングクラスタリングにおけるデータクラスタリングの方法において、入力データ点を配置する特徴量空間を局所領域に分割し、データ点が１点以上存在する局所領域に対し、それぞれ独立に代表点を決定し、次に代表点が存在する局所領域にデータ点が追加された場合に、代表点と追加されたデータ点に基づいて重み付けを行い新たな代表点を決定し、新たな代表点を用いてクラスタ数を制御する、各処理を実行する。
【発明の効果】
【００１５】
１実施態様によれば、ストリーミングクラスタリングにおいて、精度の低下を抑制することができる。
【図面の簡単な説明】
【００１６】
【図１】図１は、実施例１に係る情報処理装置の構成を示す機能ブロック図である。
【図２】図２は、グリッドを説明する図である。
【図３】図３は、グリッドリストのデータ構造の一例を示す図である。
【図４】図４は、実施例１に係る代表点リストのデータ構造の一例を示す図である。
【図５】図５は、実施例１に係る代表点更新処理を説明する図である。
【図６】図６は、実施例１に係る代表点更新処理を用いたクラスタリングを説明する図である。
【図７Ａ】図７Ａは、グリッドの一例を示す図である。
【図７Ｂ】図７Ｂは、グリッドの別の例を示す図である。
【図８】図８は、最大保持点数の決定方法の一例を示す図である。
【図９】図９は、実施例１に係る代表点更新処理のフローチャートを示す図である。
【図１０】図１０は、実施例１に係る代表点圧縮処理のフローチャートを示す図である。
【図１１】図１１は、実施例１に係る代表点更新処理を用いたクラスタリング処理のフローチャートを示す図である。
【図１２】図１２は、実施例１に係るクラスタリング処理のフローチャートを示す図である。
【図１３】図１３は、実施例１に係る代表点更新処理を用いたオンラインクラスタリングを説明する図である。
【図１４】図１４は、代表点を分割する場合を説明する図である。
【図１５】図１５は、実施例２に係る情報処理装置の構成を示す機能ブロック図である。
【図１６】図１６は、実施例２に係る代表点リストのデータ構造の一例を示す図である。
【図１７】図１７は、実施例２に係る代表点範囲を説明する図である。
【図１８】図１８は、実施例２に係る代表点を分割する条件を説明する図である。
【図１９】図１９は、実施例２に係る代表点分割処理のフローチャートを示す図である。
【図２０】図２０は、実施例２に係るクラスタリング処理のフローチャートを示す図である。
【図２１】図２１は、実施例３に係る情報処理装置の構成を示す機能ブロック図である。
【図２２】図２２は、実施例３に係るコスト関数表のデータ構造の一例を示す図である。
【図２３】図２３は、実施例３に係る代表点／クラスタ対応表のデータ構造の一例を示す図である。
【図２４】図２４は、実施例３に係るクラスタ中心集合のデータ構造の一例を示す図である。
【図２５】図２５は、実施例３に係るクラスタリング処理の流れの一例を示す図である。
【図２６】図２６は、実施例３に係る代表点を統合する条件を説明する図である。
【図２７】図２７は、実施例３に係るコスト関数の導出の前提を示す図である。
【図２８】図２８は、実施例３に係るクラスタリング処理のフローチャートを示す図である。
【図２９】図２９は、実施例４に係るクラスタリング処理の概要を示す図である。
【図３０】図３０は、実施例４に係るクラスタリング処理の流れの一例を示す図である。
【図３１】図３１は、実施例４に係るコスト関数の導出の前提を示す図である。
【図３２】図３２は、実施例４に係るクラスタリング処理のフローチャートを示す図である。
【図３３】図３３は、データクラスタリングプログラムを実行するコンピュータの一例を示す図である。
【図３４】図３４は、ＤＰ−ｍｅａｎｓ法の概要を示す図である。
【図３５】図３５は、ストリーミングクラスタリングでクラスタリング精度が低下する例を示す図である。
【発明を実施するための形態】
【００１７】
以下に、本願の開示するデータクラスタリング方法、情報処理装置およびデータクラスタリングプログラムの実施例を図面に基づいて詳細に説明する。なお、本発明は、実施例により限定されるものではない。
【実施例１】
【００１８】
［実施例１に係る情報処理装置の構成］
図１は、実施例１に係る情報処理装置の構成を示す機能ブロック図である。図１に示す情報処理装置１は、入力されたデータ点を配置する特徴量空間を局所領域（以降、「グリッド」という）に分割し、データ点が存在するグリッド領域で最低１点以上の代表点を保持する。情報処理装置１は、局所領域毎に、代表点が一定個数を超えているか否かを判定し、代表点が一定個数を超えている局所領域内の代表点を圧縮する（間引く）。これにより、情報処理装置１は、各クラスタが存在する箇所において最低１点が確保されるため、点の数が少ないクラスタの情報が失われることを防ぐことができる。さらに、情報処理装置１は、各クラスタが存在する箇所において代表点が一定個数を超えないため、保持する代表点数を一定個数に抑えられる。この結果、情報処理装置１は、全てのデータ点を常時保持することなく、精度良いクラスタリングを行うことができる。
【００１９】
情報処理装置１は、制御部１０と、記憶部２０とを有する。
【００２０】
制御部１０は、ＣＰＵ（Central  Processing  Unit）などの電子回路に対応する。そして、制御部１０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部１０は、データ取得部１１と、代表点更新部１２と、代表点圧縮部１３と、クラスタリング部１４とを有する。
【００２１】
記憶部２０は、例えば、ＲＡＭ、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。記憶部２０は、グリッドリスト２１と、代表点リスト２２とを有する。グリッドリスト２１は、代表点を保持するグリッドの情報を示す。代表点リスト２２は、グリッドに保持される代表点の情報を示す。代表点の情報には、例えば、代表点の座標と重みが含まれる。なお、グリッドリスト２１および代表点リスト２２のデータ構造は、後述するものとする。
【００２２】
ここで、グリッドを、図２を参照して説明する。図２は、グリッドを説明するための図である。図２に示すように、グリッドは、入力されたデータ点が配置された特徴量空間を所定の大きさで分割された局所領域である。グリッドは、データ点が存在する部分に生成される。生成されたグリッドは、後述するグリッドリスト２１に記憶される。入力されたデータ点の中から代表点が選択される。代表点の座標とは、入力されたデータ点の中から選択された代表点の特徴量としてのパラメータのことをいう。代表点の重みとは、他のデータ点が代表点にマージされるときに増加するパラメータである。代表点の座標および代表点の重みは、後述する代表点リスト２２に記憶される。一例として、代表点ｐ１では、代表点の座標が（ｘｉ、ｙｉ）であり、代表点の重みが１０．０である。
【００２３】
代表点の重みは、代表点圧縮処理を行っても処理の前後で重心位置が変わらないようにするためのパラメータであり、代表点の情報に付加される。図２の例では、ｐ２１，ｐ２２，ｐ２３，ｐ２４を圧縮する際に、圧縮されるデータ点の情報として代表点ｐ２（ｐ２２）の情報に重みを示すパラメータが付加される。重みは、一例として、データ点の個数に相当する。したがって、ここでは、代表点ｐ２の情報には、重みｗのパラメータとして「４」が付加される。この重みのパラメータを用いることで、データ点を圧縮（間引き）した後の重心位置は、全データ点を用いた重心位置とほぼ変わらない。
【００２４】
ここで、グリッドリスト２１のデータ構造を、図３を参照して説明する。図３は、グリッドリストのデータ構造の一例を示す図である。図３に示すように、グリッドリスト２１は、グリッドＩＤ２１ａおよびグリッド座標２１ｂを対応付けて記憶する。グリッドＩＤ（IDentfier）２１ａは、グリッドを一意に識別する識別子である。グリッド座標２１ｂは、グリッドの特徴量空間における局所領域の位置（座標）を示す。
【００２５】
代表点リスト２２のデータ構造を、図４を参照して説明する。図４は、代表点リストのデータ構造の一例を示す図である。図４に示すように、代表点リスト２２は、代表点座標２２ｂおよび代表点重み２２ｃをグリッドＩＤ２２ａに対応付けて記憶する。グリッドＩＤ２２ａは、グリッドの識別ＩＤである。代表点座標２２ｂは、代表点の座標である。代表点重み２２ｃは、代表点の重みである。
【００２６】
図１に戻って、データ取得部１１は、クラスタリングの対象となるデータ点を取得する。例えば、データ取得部１１は、外部から入力されたデータ点を取得する。クラスタリングの対象となるデータ点は、一例として、１６ｋＨｚ、１６ｂｉｔで量子化された音響信号（以降、音データという）であるが、音データに限定されるものではない。
【００２７】
代表点更新部１２は、グリッドに代表点が一定個数を超えないように、代表点を更新する。ここでいう一定個数とは、グリッドに保持可能なデータ点の個数を示し、以降、「最大保持点数」というものとする。例えば、代表点更新部１２は、データ取得部１１によって取得されたデータ点を受け付ける。受け付けるデータ点は、１点でも良いし、複数点でも良い。代表点更新部１２は、グリッドリスト２１に記憶されたグリッドの中に、受け付けたデータ点の座標を含むグリッドが存在するか否かを判定する。代表点更新部１２は、グリッドリスト２１に記憶されたグリッドの中に、データ点の座標を含むグリッドが存在すると判定した場合には、当該グリッドにこのデータ点を追加する。このとき、代表点更新部１２は、データ点の重みを１に設定する。代表点更新部１２は、グリッドリスト２１に記憶されたグリッドの中に、データ点の座標を含むグリッドが存在しないと判定した場合には、このデータ点の座標を含むグリッドを新たに生成し、生成したグリッドにこのデータ点を追加する。このとき、代表点更新部１２は、データ点の重みを１に設定するとともに、新たに生成されたグリッドをグリッドリスト２１に追加する。代表点更新部１２は、受け付けたデータ点をグリッドに追加した後、グリッドリスト２１に記憶されたそれぞれのグリッドに対して、代表点の個数が最大保持点数を超えているか否かを判定する。代表点更新部１２は、代表点の個数が最大保持点数を超えている場合には、対象のグリッドに代表点の個数が最大保持点数を超えないように、代表点圧縮処理を実行し、代表点を更新する。代表点圧縮処理は、代表点圧縮部１３によって実行される。
【００２８】
代表点圧縮部１３は、グリッドに代表点の個数が最大保持点数を超えた場合には、グリッドに代表点の個数が最大保持点数を超えないように代表点を圧縮する。例えば、代表点圧縮部１３は、グリッドに含まれる代表点の中から新規の代表点を選択する。代表点圧縮部１３は、グリッドに含まれる代表点の中から、新規の代表点に最も近い代表点を選択する。代表点圧縮部１３は、新規の代表点の重みを１加算し、最も近い代表点を削除する。すなわち、代表点圧縮部１３は、新規の代表点と新規の代表点に最も近い代表点とを圧縮していくことで、最終的に、グリッドに代表点の個数が最大代表点個数以下となるようにする。なお、新規の代表点の選択方法としては、グリッドに含まれる代表点をランダムにサンプリングする方法や、ｋ−ｍｅａｎｓ法のようなクラスタ数を固定値とした場合の代表点の選択方法を用いても良い。また、最大保持点数は、グリッド毎に異なる固定数にしても良いし、グリッド毎に同じ固定数にしても良い。最大保持点数の決定方法の例は、後述するものとする。
【００２９】
ここで、代表点更新部１２による代表点更新処理を、図５を参照して説明する。図５は、実施例１に係る代表点更新処理を説明する図である。図５に示すように、代表点更新部１２は、新規のデータ点を、代表点リスト２２に記憶されている代表点のグリッドに併合（マージ）する。代表点更新部１２は、グリッドがない部分に新規データ点が入ったら、新しくグリッドを生成する。
【００３０】
すなわち、代表点更新部１２は、グリッドリスト２１に記憶されたグリッドの中に、新規のデータ点の座標を含むグリッドが存在すれば、当該グリッドに新規のデータ点を追加する。そして、代表点更新部１２は、グリッドリスト２１に記憶されたグリッドの中に、新規のデータ点の座標を含むグリッドが存在しなければ、新たにグリッドを生成し、新たに生成されたグリッドに新規のデータ点を追加する。ここでは、符号ｐ１００の新規データ点群は、グリッドｇ１にマージされ、符号ｐ２００の新規データ群は、グリッドｇ２にマージされる。そして、符号ｐ３００の新規データ点群は、新たに生成されるグリッドｇ４に追加される。
【００３１】
そして、代表点更新部１２は、新規のデータ点をグリッドにマージした後、それぞれのグリッドに対して、代表点の個数が最大保持点数を超えているか否かを判定し、最大保持点数を超えているグリッドを選択する。ここでは、最大保持点数は、グリッド毎に同じ固定数である１０点であるとする。グリッドｇ１、ｇ３、ｇ４は、最大保持点数１０を超えていないと判定されるとする。グリッドｇ２は、２０点であり、最大保持点数１０を超えていると判定されるとする。すると、最大保持点数を超えているグリッドとして、グリッドｇ２が選択される。
【００３２】
そして、代表点圧縮部１３は、最大代表点数を超えているグリッドで代表点を選択し、選択された代表点と、選択された代表点に最も近い代表点とを圧縮する。代表点圧縮部１３は、選択された代表点の重みを１加算し、最も近い代表点を削除する。代表点圧縮部１３は、グリッド内の代表点の数が最大代表点数になるまで圧縮処理を繰り返す。ここでは、代表点圧縮部１３は、グリッドｇ４内の代表点ｐ４を選択し、選択された代表点ｐ４と、代表点ｐ４に最も近い代表点ｐ５とを圧縮する。代表点圧縮部１３は、代表点ｐ４の重みを１加算し、代表点ｐ５を削除する。この結果、代表点ｐ４の重みは２となる。
【００３３】
図１に戻って、クラスタリング部１４は、グリッドリスト２１の中のグリッドに含まれる代表点を入力としてバッチクラスタリング処理を実行する。例えば、クラスタリング部１４は、グリッドリスト２１の中のグリッドに含まれる代表点を代表点リスト２２から取得し、取得した代表点を入力としてＤＰ−ｍｅａｎｓ法を実行する。ＤＰ−ｍｅａｎｓ法は、重みが付けられた代表点を使用するので、ここでいうＤＰ−ｍｅａｎｓ法を「重み付きＤＰ−ｍｅａｎｓ法」というものとする。なお、クラスタリング部１４は、クラスタリング処理としてＤＰ−ｍｅａｎｓ法を適用するものとしたが、ＤＰ−ｍｅａｎｓ法に限定されるものではなく、クラスタ数を可変とするクラスタリング方法に適用可能である。例えば、ハードクラスタリング方法として、例えばＫ−ｍｅａｎｓ法のようなクラスタ数を固定とするクラスタリング方法を複数のクラスタ数に対して適用し、それらの中の一つを結果として採用する方法が適用可能である。また、クラスタの階層関係を仮定するＨＤＰ−ｍｅａｎｓ法が適用可能である。確率的なソフトクラスタリング方法として、ＤＰＭ（Dirichlet  Process  Mixture）、ＨＤＰ（Hierarchical  Dirichlet  Process）やＮＤＰ（Nested  Dirichlet  Process）が適用可能である。
【００３４】
ここで、クラスタリング部１４によるクラスタリング処理を、図６を参照して説明する。図６は、実施例１に係るクラスタリング処理を説明する図である。図６に示すように、まず、代表点更新部１２が、データ点の一部を取得して代表点を更新し、再度データ点の一部を取得して代表点を更新する処理を繰り返す。そして、クラスタリング部１４は、最終的に更新された代表点に対してバッチクラスタリング処理を行う。クラスタリング部１４は、クラスタ中心集合に、全代表点の重心を代入する。クラスタリング部１４は、代表点がクラスタ中心集合の中で最も距離が近い中心を取り出す。なお、ここで述べる「距離」とは、例えばユークリッド距離を指す。クラスタリング部１４は、代表点と取りだした中心との距離が閾値λ（クラスタの粒度を定めるパラメータ）より小さければ、この中心を有するクラスタにこの代表点を割り振る。クラスタリング部１４は、代表点と取りだした中心との距離が閾値λ以上であれば、新規のクラスタ中心としてこの代表点をクラスタ中心集合に代入する。そして、クラスタリング部１４は、クラスタ中心集合からクラスタ中心を取り出し、取り出したクラスタ中心の座標値を代表点の重み付きの重心値に更新する。
【００３５】
ここで、グリッドの一例を、図７Ａを参照して説明する。図７Ａは、グリッドの一例を示す図である。図７Ａに示すグリッドの例は、特徴量空間におけるｄ次元の超立方体である。すなわち、２次元の場合には、グリッドは正方形となり、３次元の場合には、グリッドは立方体となり、４次元の場合には、グリッドは正八胞体となる。λがクラスタの粒度を定めるパラメータ、例えばクラスタの直径であるとすると、グリッドの一辺の長さはλ／√ｄ以下とするのが望ましい。前提条件として、データ点同士の距離がλ以上離れた場合に新規のクラスタが生成されるとする。すると、グリッドの一辺の長さがλ／√ｄ以下であれば、同一のグリッドに含まれるデータ点同士が取り得る距離はλ以下であることが保証される。つまり、グリッドに含まれる点で最大距離となる点は対角線上に位置する場合であり、このときの対角線の長さは、（超立方体の一辺の長さλ√ｄ×√ｄ＝）λとなる。したがって、１つのグリッドに含まれるデータ点同士はλ以下であるので、１つのクラスタに含まれることとなり、別のクラスタに含まれない。この結果、代表点圧縮部１３がそれぞれのグリッドで代表点圧縮処理を行っても、クラスタリング処理でクラスタが消失しないことが保証される。すなわち、グリッドの一辺の長さはλ／√ｄ以下であれば、グリッドにデータ点を１点残しておけば、クラスタが消失しない。
【００３６】
グリッドの別の例を、図７Ｂを参照して説明する。図７Ｂは、グリッドの別の例を示す図である。図７Ｂに示すグリッドの例は、特徴量空間におけるｄ次元の超球である。λがクラスタの粒度を定めるパラメータ、例えばクラスタの直径であるとすると、グリッドの直径がλ以下とするのが望ましい。前提条件として、データ点同士がλ以上離れた場合に新規のクラスタが生成されるとする。すると、グリッドの直径がλ以下であれば、同一のグリッドに含まれるデータ点同士が取り得る距離はλ以下であることが保証される。つまり、グリッドに含まれる点で最大距離となる点は直径上に位置する場合であり、このときの直径の長さはλとなる。したがって、１つのグリッドに含まれるデータ点同士はλ以下であるので、１つのクラスタに含まれることとなり、別のクラスタに含まれない。この結果、代表点圧縮部１３がそれぞれのグリッドで代表点圧縮処理を行っても、クラスタリング処理でクラスタが消失しないことが保証される。すなわち、グリッドの直径はλ以下であれば、グリッドにデータ点を１点残しておけば、クラスタが消失しない。
【００３７】
次に、最大保持点数の決定方法の一例を、図８を参照して説明する。図８は、最大保持点数の決定方法の一例を示す図である。各グリッドの最大保持点数は、任意の数として定めることができるが、特徴量空間における次元数ｄが１であれば２、次元数ｄが２以上であればｄ（次元数）とすることが望ましい。図８に示すように、２次元以上であれば、グリッドに含まれるクラスタの最大の中心個数は次元数ｄ＋１個未満であることが保証されるからである。但し、１次元の場合には、２個以下、すなわち次元数ｄ＋１個以下である。これは、以下のように再帰的に示すことができる。まず、次元数ｄが１である場合には、数値直線上にｄ離してクラスタの中心をおく場合が最適であるため、自明である。次元数ｄが２以上である場合には、ｄ次元で仮定（クラスタの中心がｄであること）が成立し、ｄ＋１次元でクラスタの中心がｄ＋２個以上含まれる場合があるとする。すると、ある部分空間でクラスタの中心個数がｄ＋１個以上存在してしまい、仮定に矛盾する。したがって、各グリッドに次元数個の代表点が保持されれば良い。
【００３８】
言い換えると、図８に示すように、２次元の場合は、１個のグリッドに正三角形の３頂点をクラスタの中心とするクラスタが配置し得る。ところが、かかる場合には、クラスタが重なってしまう。したがって、クラスタが重ならないようするために、グリッドに含まれる最大のクラスタの中心は３個未満、すなわち２個以下である必要がある。これは、２次元以上であっても同様である。したがって、２次元以上の場合には、グリッドに最大保持点数として次元数ｄだけ代表点を残しておけば、代表点圧縮処理を行っても、クラスタが消失しないことが保証される。この結果、クラスタリング処理の精度悪化を防ぐことができる。
【００３９】
なお、さらに、上記で示したように、グリッド内で保持される代表点の最大保持点数はｄ個であれば十分であることから、グリッド内にｄ個の固定クラスタが存在すると仮定したクラスタリング処理を行うことで、クラスタ重心の精度悪化を防ぐことができる。例えば、ｋ−ｍｅａｎｓ法など、クラスタ数を固定とした場合にはクラスタの重心位置の誤差が定数倍に抑えられる方法が既知であるため、一例として圧縮アルゴリズムとしてｋ−ｍｅａｎｓ法を用い、クラスタの個数をｄ個として圧縮処理を行えば、精度良くクラスタリング処理を行うことができる。このとき、ｋ−ｍｅａｎｓ法で保持される代表点の最大保持点数は３ｄ×ｌｏｇ（ｄ）個とすれば良い。
【００４０】
［代表点更新処理のフローチャート］
次に、実施例１に係る代表点更新処理のフローチャートを、図９を参照して説明する。図９は、実施例１に係る代表点更新処理のフローチャートを示す図である。なお、代表点更新部１２は、入力パラメータとして、データ点群Ｘ、クラスタの粒度を定めるパラメータλ、グリッドリスト２１を取得する。なお、ここでのデータ点群Ｘとは、最終的なクラスタリング処理に用いるデータ全てであるとは限らず、最終的なクラスタリング処理に用いるデータの一部分であってもよい。
【００４１】
まず、代表点更新部１２は、データ点群Ｘからデータ点ｘを取り出す（ステップＳ１１）。代表点更新部１２は、グリッドリスト２１中にデータ点ｘを範囲に含むグリッドがあるか否かを判定する（ステップＳ１２）。データ点ｘを範囲に含むグリッドがないと判定した場合には（ステップＳ１２；Ｎｏ）、代表点更新部１２は、データ点ｘを範囲に含む新たなグリッドを生成し、生成したグリッドのグリッド座標２１ｂをグリッドリスト２１に追加する（ステップＳ１３）。そして、代表点更新部１２は、ステップＳ１４に移行する。
【００４２】
一方、データ点ｘを範囲に含むグリッドがあると判定した場合には（ステップＳ１２；Ｙｅｓ）、代表点更新部１２は、当該グリッドに重みを１．０としたデータ点ｘを追加する（ステップＳ１４）。代表点更新部１２は、データ点群Ｘから全てのデータ点ｘを取り出したか否かを判定する（ステップＳ１５）。全てのデータ点ｘを取り出していないと判定した場合には（ステップＳ１５；Ｎｏ）、代表点更新部１２は、次のデータ点を取り出すべく、ステップＳ１１に移行する。
【００４３】
一方、全てのデータ点ｘを取りだしたと判定した場合には（ステップＳ１５；Ｙｅｓ）、代表点更新部１２は、必要であれば、グリッドの最適化処理を行う（ステップＳ１６）。代表点更新部１２がグリッドを生成する際に、グリッドの中心が最適でない場合がある。そうすると、グリッドが多く保存されてしまうことがあり、不必要に記憶領域を必要とする可能性があるからである。
【００４４】
続いて、代表点更新部１２は、グリッドリスト２１からグリッドを取り出す（ステップＳ１７）。代表点更新部１２は、グリッドに含まれる代表点の個数が最大保持点数以下であるか否かを判定する（ステップＳ１８）。グリッドに含まれる代表点の個数が最大保持点数以下であると判定した場合には（ステップＳ１８；Ｙｅｓ）、代表点更新部１２は、代表点圧縮処理を実行しないで、ステップＳ２０に移行する。
【００４５】
グリッドに含まれる代表点の個数が最大保持点数以下でない、すなわち最大保持点数より大きいと判定した場合には（ステップＳ１８；Ｎｏ）、代表点更新部１２は、代表点圧縮処理を実行する（ステップＳ１９）。なお、代表点圧縮処理のフローチャートは、後述する。そして、代表点更新部１２は、ステップＳ２０に移行する。
【００４６】
ステップＳ２０において、代表点更新部１２は、グリッドリスト２１から全てのグリッドを取り出したか否かを判定する（ステップＳ２０）。全てのグリッドを取り出していないと判定した場合には（ステップＳ２０；Ｎｏ）、代表点更新部１２は、次のグリッドを取り出すべく、ステップＳ１７に移行する。
【００４７】
一方、全てのグリッドを取り出したと判定した場合には（ステップＳ２０；Ｙｅｓ）、代表点更新部１２は、代表点更新処理を終了し、出力パラメータとしてグリッドリスト２１を出力する。
【００４８】
［代表点圧縮処理のフローチャート］
次に、実施例１に係る代表点圧縮処理のフローチャートを、図１０を参照して説明する。図１０は、実施例１に係る代表点圧縮処理のフローチャートを示す図である。なお、代表点圧縮部１３は、入力パラメータとして、最大保持点数より大きいと判定されたグリッドに含まれる代表点の座標、代表点の重みおよび最大保持点数を取得する。
【００４９】
代表点圧縮部１３は、入力パラメータとして取得された代表点から、最大保持点数の新規代表点を選択する（ステップＳ２１）。新規代表点の選択方法には、例えば、ランダムサンプリング、ｋ−ｍｅａｎｓ法などが挙げられる。そして、代表点圧縮部１３は、新規代表点の重みを０にクリアする（ステップＳ２２）。
【００５０】
続いて、代表点圧縮部１３は、グリッドに保持されていた旧代表点ｘを順次選択する（ステップＳ２３）。代表点圧縮部１３は、選択された旧代表点ｘに最も近い新規代表点を選択する（ステップＳ２４）。代表点圧縮部１３は、選択された新規代表点の代表点の重みを１加算する（ステップＳ２５）。そして、代表点圧縮部１３は、選択された旧代表点ｘを代表点リスト２２から削除する（ステップＳ２６）。
【００５１】
続いて、代表点圧縮部１３は、全ての旧代表点を選択したか否かを判定する（ステップＳ２７）。全ての旧代表点を選択していないと判定した場合には（ステップＳ２７；Ｎｏ）、代表点圧縮部１３は、次の旧代表点を選択すべく、ステップＳ２３に移行する。一方、全ての旧代表点を選択したと判定した場合には（ステップＳ２７；Ｙｅｓ）、代表点圧縮部１３は、代表点圧縮処理を終了し、出力パラメータとして新規代表点の座標、重みを出力する。
【００５２】
［クラスタリング処理のフローチャート］
次に、実施例１に係る代表点更新処理を用いたクラスタリング処理のフローチャートを、図１１を参照して説明する。図１１は、実施例１に係る代表点更新処理を用いたクラスタリング処理のフローチャートを示す図である。なお、情報処理装置１は、入力パラメータとして、データ点群Ｘ、クラスタの粒度を定めるパラメータλを取得する。
【００５３】
まず、情報処理装置１は、グリッドリスト２１を空集合に設定する（ステップＳ３１）。そして、情報処理装置１は、代表点更新処理でグリッドリスト２１を更新する（ステップＳ３２）。なお、代表点更新処理のフローチャートは、図９で示したものである。
【００５４】
そして、情報処理装置１は、グリッドリスト２１中の代表点（座標、重み）を入力としてクラスタリング処理を実行する（ステップＳ３３）。クラスタリング処理は、例えば、重み付きＤＰ−ｍｅａｎｓ法を適用する。なお、クラスタリング処理のフローチャートは、後述する。
【００５５】
そして、情報処理装置１は、代表点更新処理を用いたクラスタリング処理を終了し、出力パラメータとしてクラスタリング結果を出力する。
【００５６】
図１２は、実施例１に係るクラスタリング処理のフローチャートを示す図である。なお、図１２では、重み付きＤＰ−ｍｅａｎｓ法を適用し、クラスタの追加を判定する際に用いる距離関数として二乗ユークリッド距離を用いた場合について説明する。クラスタリング部１４は、入力パラメータとして、代表点群Ｘ、代表点の重みｗおよびクラスタの粒度を定めるパラメータλを取得する。
【００５７】
クラスタリング部１４は、クラスタの中心集合Ｕに全ての代表点の重心を代入する（ステップＳ４１）。クラスタリング部１４は、収束したか否かを判定する（ステップＳ４２）。収束していないと判定した場合には（ステップＳ４２；Ｎｏ）、クラスタリング部１４は、代表点群Ｘから代表点ｘを取り出す（ステップＳ４３）。そして、クラスタリング部１４は、クラスタの中心集合Ｕの中で最も距離が近い中心ｕを取り出す（ステップＳ４４）。
【００５８】
クラスタリング部１４は、代表点ｘと中心ｕとの距離がλ２以上であるか否かを判定する（ステップＳ４５）。代表点ｘと中心ｕとの距離がλ２以上であると判定した場合には（ステップＳ４５；Ｙｅｓ）、クラスタリング部１４は、クラスタの中心集合Ｕに代表点ｘを追加する（ステップＳ４６）。そして、クラスタリング部１４は、ステップＳ４７に移行する。
【００５９】
一方、代表点ｘと中心ｕとの距離がλ２以上でない、すなわちλ２より小さいと判定した場合には（ステップＳ４５；Ｎｏ）、クラスタリング部１４は、ステップＳ４７に移行する。ステップＳ４７において、クラスタリング部１４は、代表点ｘのラベルを最近傍クラスタのラベルに更新する（ステップＳ４７）。
【００６０】
続いて、クラスタリング部１４は、代表点群から全ての代表点ｘを取り出したか否かを判定する（ステップＳ４８）。全ての代表点ｘを取り出していないと判定した場合には（ステップＳ４８；Ｎｏ）、クラスタリング部１４は、次の代表点を取り出すべく、ステップＳ４３に移行する。
【００６１】
一方、全ての代表点ｘを取り出したと判定した場合には（ステップＳ４８；Ｙｅｓ）、クラスタリング部１４は、クラスタの中心集合Ｕからクラスタの中心ｕを取り出す（ステップＳ４９）。クラスタリング部１４は、取り出したｕの座標値を、ｕに対応するラベルがついた代表点の重み付き重心値に更新する（ステップＳ５０）。
【００６２】
そして、クラスタリング部１４は、クラスタの中心集合Ｕから全てのクラスタの中心ｕを取り出したか否かを判定する（ステップＳ５１）。全てのクラスタの中心ｕを取り出していないと判定した場合には（ステップＳ５１；Ｎｏ）、クラスタリング部１４は、次のクラスタの中心を取り出すべく、ステップＳ４９に移行する。一方、全てのクラスタの中心ｕを取り出したと判定した場合には（ステップＳ５１；Ｙｅｓ）、クラスタリング部１４は、収束判定をすべく、ステップＳ４２に移行する。
【００６３】
ステップＳ４２において、収束したと判定した場合には（ステップＳ４２；Ｙｅｓ）、クラスタリング部１４は、クラスタの中心集合Ｕを出力し（ステップＳ５２）、クラスタリング処理を終了する。
【００６４】
なお、情報処理装置１は、実施例１に係る代表点更新処理によって更新される代表点を用いて、一定時間ごとに（独立して）クラスタリング処理を行えば、オンラインのクラスタリング処理を行うことができる。実施例１に係る代表点更新処理を用いたオンライクラスタリングを、図１３を参照して説明する。図１３は、実施例１に係る代表点更新処理を用いたオンラインクラスタリングを説明する図である。
【００６５】
図１３に示すように、時点ｔが０であるとき、情報処理装置１は、入力データ点を受け付ける。受け付けた入力データ点について、情報処理装置１は、代表点更新処理を行う。すなわち、情報処理装置１は、入力データ点を範囲に含むグリッドが既に存在すれば、このグリッドにこの入力データ点を代表点として追加する。情報処理装置１は、入力データ点を範囲に含むグリッドが存在しなければ、新たなグリッドを生成し、新たに生成したグリッドにこの入力データ点を代表点として追加する。情報処理装置１は、それぞれのグリッドに代表点の個数が最大保持点数を超えないように、代表点圧縮処理を行い、代表点を更新する。そして、情報処理装置１は、更新された代表点を入力としてバッチクラスタリング処理を行う。
【００６６】
時が経過し、時点ｔが１になったとき、情報処理装置１は、入力データ点を受け付ける。受け付けた入力データ点と、時点ｔが０であったときに更新された代表点とについて、情報処理装置１は、代表点更新処理を行う。すなわち、情報処理装置１は、入力データ点を範囲に含むグリッドが既に存在すれば、このグリッドにこの入力データ点を代表点として追加する。情報処理装置１は、入力データ点を範囲に含むグリッドが存在しなければ、新たなグリッドを生成し、新たに生成したグリッドにこの入力データ点を代表点として追加する。情報処理装置は、それぞれのグリッドに代表点の個数が最大保持点数を超えないように、代表点圧縮処理を行い、代表点を更新する。そして、情報処理装置１は、更新された代表点を入力としてバッチクラスタリング処理を行う。
【００６７】
時が経過し、時点ｔが２になったとき、情報処理装置１は、入力データ点を受け付ける。受け付けた入力データ点と、時点ｔが１であったときに更新された代表点とについて、情報処理装置１は、代表点更新処理を行う。すなわち、情報処理装置１は、入力データ点を範囲に含むグリッドが既に存在すれば、このグリッドにこの入力データ点を代表点として追加する。情報処理装置１は、入力データ点を範囲に含むグリッドが存在しなければ、新たなグリッドを生成し、新たに生成したグリッドにこの入力データ点を代表点として追加する。情報処理装置は、それぞれのグリッドに代表点の個数が最大保持点数を超えないように、代表点圧縮処理を行い、代表点を更新する。そして、情報処理装置１は、更新された代表点を入力としてバッチクラスタリング処理を行う。
【００６８】
このように、情報処理装置１は、時分割して入力されるデータ点について、各時点で独立してクラスタリング処理を行うことで、オンラインのクラスタリング処理を行うことができる。
【００６９】
［実施例１の効果］
上記実施例１によれば、情報処理装置１は、ストリーミングクラスタリングを以下のように行う。すなわち、情報処理装置１は、入力データ点を配置する特徴量空間をグリッドに分割する。情報処理装置１は、データ点が１点以上存在するグリッドに対し、それぞれ独立に代表点を決定し、次に代表点が存在するグリッドにデータ点が追加された場合に、代表点と追加されたデータ点に基づいて重み付けを行い新たな代表点を決定する。そして、情報処理装置１は、新たな代表点を用いてクラスタ数を制御する。かかる構成によれば、情報処理装置１は、ストリーミングクラスタリングにおいて、クラスタリング精度の低下を抑制できる。すなわち、情報処理装置１は、ランダムにデータ点を減らす場合と比べて、入力データ点の代表として重みを付けた代表点を決定し、クラスタリングを行うことで、クラスタリングの精度の低下が抑制可能となる。
【００７０】
また、上記実施例１によれば、情報処理装置１は、特徴量空間を、λ／√ｄ（λ：クラスタの粒度を定める閾値、ｄ：特徴量空間の次元数）を一辺の長さとするｄ次元超立方体であるグリッドに分割する。かかる構成によれば、情報処理装置１は、ｄ次元超立方体の対角線の長さが（クラスタの粒度を定める閾値）λとなるので、グリッドにデータ点が含まれれば、クラスタが消えないこととなる。この結果、情報処理装置１は、ランダムに代表点を決定した場合に、クラスタが消失してしまい、クラスタ個数の誤差が大きくなることを回避できる。
【００７１】
また、上記実施例１によれば、情報処理装置１は、特徴量空間を、クラスタの粒度を定める閾値λを直径としたｄ次元超球（ｄ：前記特徴量空間の次元数）であるグリッドに分割する。かかる構成によれば、情報処理装置１は、ｄ次元超球の直径の長さが（クラスタの粒度を定める閾値）λとなるので、グリッドにデータ点が含まれれば、クラスタが消失しないことが保証される。この結果、情報処理装置１は、ランダムに代表点を決定した場合に、クラスタが消失してしまい、クラスタ個数の誤差が大きくなることを回避できる。
【００７２】
また、上記実施例１によれば、情報処理装置１は、グリッドに保持する最大保持点数を次元数ｄとする。かかる構成によれば、情報処理装置１は、グリッドに最大保持点数として次元数ｄだけ代表点を残しておけば、代表点圧縮処理を行っても、代表点が残るので、クラスタが消失しないことが保証される。この結果、情報処理装置１は、ランダムに代表点を決定した場合に、クラスタが消失してしまい、クラスタ個数の誤差が大きくなることを回避できる。
【００７３】
また、上記実施例１によれば、情報処理装置１は、時分割されたデータ点に対して、既に決定された代表点と時分割されたデータ点に基づいて新たな代表点を決定する。かかる構成によれば、情報処理装置１は、代表点更新処理を用いたオンラインクラスタリング処理を行うことができ、オンラインクラスタリングの精度の低下を抑制できる。
【００７４】
また、上記実施例１によれば、情報処理装置１は、グリッドに保持する最大の保持点数を３×ｄ×ｌｏｇ（ｄ）とする。かかる構成によれば、情報処理装置１は、ｋ−ｍｅａｎｓ法で保持される代表点の最大保持点数を３ｄ×ｌｏｇ（ｄ）個とすれば、精度良くクラスタリング処理を行うことができる。
【実施例２】
【００７５】
ところで、実施例１では、情報処理装置１は、代表点同士の距離がλ以上離れた場合に新規のクラスタを生成する場合を説明した。しかしながら、情報処理装置１は、これに限定されず、局所解に陥る場合には、代表点を分割し、クラスタが分割されるようにしても良い。局所解とは、最適解に辿り着かない状態のことをいう。
【００７６】
［代表点を分割する場合］
ここで、代表点を分割する場合を、図１４を参照して説明する。図１４は、代表点を分割する場合を説明する図である。まず、ＤＰ−ｍｅａｎｓ法は、目的関数の値が最小値になるように、クラスタの重心を更新し、クラスタ数を更新する。ここでいう目的関数は、以下の式（３）で表わされる。なお、ｘは入力されるｄ次元のデータ点群Ｘに属するデータ点、ｕはクラスタ中心集合Ｃに属するクラスタ中心、ｋはクラスタ数、λはクラスタの粒度を定めるパラメータである。λは、図１４ではクラスタの直径であるとする。
【数２】
0006707946.tif 000003
【００７７】
なお、クラスタ中心ｕとデータ点ｘで表わされる距離関数は、二乗ユークリッド距離を用いているが、これに限定されるものではない。例えば、距離関数は、マンハッタン距離、Ｌ∞距離のような対称性を満たすものや、ＫＬダイバージェンス、マハラノビス距離または板倉斉藤距離などの対称性を満たさないものであっても良い。
【００７８】
図１４に示すように、クラスタが１個の場合、クラスタ中心ｕは（０，０）になるので、入力データ点（−１，０）とクラスタ中心ｕとの距離は１であり、入力データ点（１，０）のクラスタ中心ｕとの距離は１である。入力データ点（−１，０）の重みは１００００であり、入力データ点（１，０）の重みは１００００である。すると、目的関数Ｌ（Ｘ，Ｃ）（＝２００００×１２＋１０２×１）は、２０１００となる。
【００７９】
これに対して、クラスタが２個の場合、クラスタ中心ｕは（−１，０），（１，０）になる。入力データ点としての（−１，０），（１，０）はそれぞれ最近傍クラスタに割り振られるので、入力データ点（−１，０）とクラスタ中心ｕとの距離は０であり、入力データ点（１，０）とクラスタ中心ｕとの距離は０である。すると、目的関数Ｌ（Ｘ，Ｃ）（＝２００００×０２＋１０２×２）は、２００となる。クラスタが２個の場合は、クラスタが１個の場合より目的関数値は小さくなる。クラスタが１個の場合は、目的関数が最小値に辿り着かず、局所解に陥っている。
【００８０】
仮に、入力データ点（−１，０）の重みが１０であり、入力データ点（１，０）の重みが１０であるとする。すると、クラスタが１個の場合、目的関数Ｌ（Ｘ，Ｃ）（＝２０×１２＋１０２×１）は、１２０となる。これに対して、クラスタが２個の場合、目的関数Ｌ（Ｘ，Ｃ）（＝２００×０２＋１０２×２）は、２００となる。クラスタが１個の場合は、クラスタが２個の場合より目的関数値は小さくなる。クラスタが１個の場合に、最適解に辿り着く。つまり、クラスタに含まれる代表点の重みが増えると、局所解に陥る場合があるので、クラスタを分割する方が良い場合がある。
【００８１】
そこで、実施例２では、情報処理装置１が、重み付き代表点を用いたクラスタリングにおいて、代表点の重みが増えてきたら、代表点を分割する場合について説明する。
【００８２】
［実施例２に係る情報処理装置の構成］
図１５は、実施例２に係る情報処理装置の構成を示す機能ブロック図である。なお、図１に示す情報処理装置１と同一の構成については同一符号を示すことで、その重複する構成および動作の説明については省略する。実施例１と実施例２とが異なるところは、代表点分割部３１を追加した点にある。また、実施例１と実施例２とが異なるところは、クラスタリング部１４をクラスタリング部１４Ａに変更した点にある。さらに、実施例１と実施例２とが異なるところは、代表点リスト２２を代表点リスト２２Ａに変更した点にある。
【００８３】
代表点リスト２２Ａのデータ構造を、図１６を参照して説明する。図１６は、代表点リストのデータ構造の一例を示す図である。図１６に示すように、代表点リスト２２Ａは、代表点座標２２ｂ、代表点重み２２ｃおよび代表点範囲２２ｄをグリッドＩＤ２２ａに対応付けて記憶する。グリッドＩＤ２２ａは、グリッドの識別ＩＤである。代表点座標２２ｂは、代表点の座標である。代表点重み２２ｃは、代表点の重みである。そして、代表点範囲２２ｄは、代表点に含まれるデータ点の範囲を示す。代表点範囲２２ｄは、代表点の次元の最大値／最小値であっても良いし、分散であっても良い。以降では、代表点範囲２２ｄを、代表点の次元の最大値／最小値として説明する。
【００８４】
ここで、代表点範囲２２ｄを、図１７を参照して説明する。図１７は、実施例２に係る代表点範囲を説明する図である。図１７に示すように、データ点から代表点が選択される際に、代表点に対して、座標および重み以外に代表点に含まれる複数のデータ点の範囲（代表点範囲）が代表点リスト２２Ａに追加される。ここでは、一例として、代表点に対して、中心として（０，０）、重みとして５点、範囲としてｘ軸方向では−５〜５、ｙ軸方向では−２〜２が設定される。すなわち、代表点は、ｘ軸方向では−５〜５、ｙ軸方向では−２〜２のデータ点を含んでいる。なお、代表点は、後述する代表点分割部３１によって代表点リスト２２Ａに追加される。
【００８５】
図１５に戻って、代表点分割部３１は、重みがｗの代表点に対し、次元ｎでの範囲が以下の式（４）の条件を満たした場合に、この次元ｎで代表点を２つに分割する。なお、ｗは重み、λはクラスタの粒度を定めるパラメータであるとする。σｎは、ｎ次元での範囲であり、σｎ＝ｐｎ−ｑｎであるとする（ｐｎ，ｑｎ：次元ｎでの最大値、最小値）。
ｗ≧１６（λ／σｎ）２・・・（４）
【００８６】
代表点を分割する条件を式（４）とする理由は、かかる条件が満たされたとき、目的関数の期待値について、分割後の方が分割前より小さくなるためである。ここで、代表点を分割する条件を、図１８を参照して説明する。図１８は、代表点を分割する条件を説明する図である。
【００８７】
図１８に示すように、左図は、代表点を分割する前の状態であり、代表点が１個の場合である。かかる場合では、クラスタに含まれるデータ点が一様分布であるとすると、各次元の誤差項の期待値は、σｎ２／１２となる。ここでいう誤差項とは、式（１８）で示す目的関数のΣｍｉｎ（ｘ−ｕ）２の部分項を示す。誤差項の期待値は、以下の一様分布の期待値の公式で求められる。
Ｖ（ｘ）＝（ｂ−ａ）２／１２（ａ:下限，ｂ：上限）
【００８８】
右図は、代表点を分割した後の状態であり、代表点が２個の場合である。かかる場合では、クラスタに含まれるデータ点が一様分布であるとすると、一様分布の期待値の公式を用いると、分割された方向の誤差項の期待値は、σｎ２／４８（＝（σｎ／２）２／１２）となる。代表点が２個の場合の誤差項の期待値が、代表点が１個の場合の期待値より小さくなる条件は、以下の式（５）より、上記の式（４）となる。なお、式（５）では、各次元の誤差項の期待値を加算している。
ｗ（σ１２／１２＋・・・＋σｎ２／１２＋・・・）＋λ２≧ｗ（σ１２／１２＋・・・＋σｎ２／４８＋・・・）＋２λ２・・・（５）
【００８９】
なお、上記の式（５）は、以下の式（３２）により表わせる。式（３２）において、ｗ１は、分割された場合の一方のクラスタの代表点１の重みであり、ｗ２は、分割された場合の他方のクラスタの代表点２の重みである。
ｗ（データ点と代表点との距離の期待値）≧ｗ１（分割後の代表点１に含まれるデータ点の距離の期待値）＋ｗ２（分割後の代表点２に含まれるデータ点の距離の期待値）＋λ２・・・（３２）
【００９０】
図１５に戻って、代表点分割部３１が式（４）の条件を満たした場合に、条件が満たされた次元ｎで、代表点を中心に代表点を２つに分割する例を以下に示す。例えば、元の代表点の（中心，重み，最大値，最小値）が（ｕｏｌｄ，ｗｏｌｄ，ｐｏｌｄ，ｑｏｌｄ）であるとする。ｕｏｌｄは、１次元の値ｕ（１）〜ｄ次元の値ｕ（ｄ）を含む。ｐｏｌｄは、１次元の値ｐ（１）〜ｄ次元の値ｐ（ｄ）を含む。ｑｏｌｄは、１次元の値ｑ（１）〜ｄ次元の値ｑ（ｄ）を含む。
【００９１】
ｎ次元目で代表点を２つに分割したとする。このとき、分割後の２つの代表点の値（ｕ１，ｗ１，ｐ１，ｑ１）、（ｕｒ，ｗｒ，ｐｒ，ｑｒ）は、それぞれｎ次元目の値だけ以下の式（６）〜式（１３）に更新され、ｎ次元目以外では元の代表点の値を引き継ぐ。
ｕ１（ｎ）＝（ｕ（ｎ）＋ｑ（ｎ））／２・・・（６）
ｗ１＝ｗｏｌｄ（ｕ（ｎ）−ｑ（ｎ））／（ｐ（ｎ）−ｑ（ｎ））・・・（７）
ｐ１（ｎ）＝ｕ（ｎ）・・・（８）
ｑ１（ｎ）＝ｑ（ｎ）・・・（９）
ｕｒ（ｎ）＝（ｕ（ｎ）＋ｐ（ｎ））／２・・・（１０）
ｗｒ＝ｗｏｌｄ（ｐ（ｎ）−ｕ（ｎ））／（ｐ（ｎ）−ｑ（ｎ））・・・（１１）
ｐｒ（ｎ）＝ｐ（ｎ）・・・（１２）
ｑｒ（ｎ）＝ｕ（ｎ）・・・（１３）
【００９２】
また、代表点分割部３１は、ある代表点にデータ点を追加する場合、代表点の逐次更新を行う。例えば、代表点の（中心，重み，最大値，最小値）が（ｕｏｌｄ，ｗｏｌｄ，ｐｏｌｄ，ｑｏｌｄ）であるとする。入力データ点がｘであるとする。すると、更新後の代表点の（中心，重み，最大値，最小値）は（ｕｎｅｗ，ｗｎｅｗ，ｐｎｅｗ，ｑｎｅｗ）となる。ｕｎｅｗ，ｗｎｅｗ，ｐｎｅｗ，ｑｎｅｗは、それぞれ以下の式（１４）〜式（１７）で表わされる。
ｕｎｅｗ＝（ｗｏｌｄｕｏｌｄ＋ｘ）／（ｗｏｌｄ＋１）・・・（１４）
ｗｎｅｗ＝ｗｏｌｄ＋１・・・（１５）
ｐｎｅｗ＝ｍａｘ（ｐｏｌｄ，ｘ）・・・（１６）
ｑｎｅｗ＝ｍｉｎ（ｑｏｌｄ，ｘ）・・・（１７）
【００９３】
クラスタリング部１４Ａは、グリッドリスト２１の中のグリッドに含まれる重み付きの代表点を入力としてバッチクラスタリング処理を実行する。ただし、重み付きの代表点の場合、目的関数が式（３）から以下の式（１８）に変化する。なお、ｘは入力されるｄ次元のデータ点群、ｕはクラスタ中心、ｋはクラスタ数、λはクラスタの粒度を定めるパラメータである。そして、ｗは、重みである。
【数３】
0006707946.tif 000004
【００９４】
このように、目的関数が変化するので、新規クラスタを生成する条件が、ユークリッド距離がλ／√ｗ以上離れた時に新規クラスタを生成するように変わる。すなわち、クラスタリング部１４Ａは、代表点と、クラスタの中心集合の中の最も距離が近い中心との距離がλ／√ｗ以上の場合に、クラスタの中心集合にこの代表点を追加する。すなわち、クラスタリング１４Ａは、この代表点を中心とした新規クラスタを生成する。なお、上記条件は、クラスタ追加条件を判定する距離関数としてユークリッド距離を用いた場合であり、他関数を用いた場合でも等価な条件が存在する。例えば、距離関数として二乗ユークリッド距離を用いた場合には新規クラスタを生成する条件はλ２／ｗとなるが、二乗ユークリッド距離はユークリッド距離の二乗を取ったものであるので、上記のユークリッド距離を用いた条件と等価である。
【００９５】
［代表点分割処理のフローチャート］
次に、実施例２に係る代表点分割処理のフローチャートを、図１９を参照して説明する。図１９は、実施例２に係る代表点分割処理のフローチャートを示す図である。なお、代表点分割部３１は、入力パラメータとして、代表点点群Ｘ、代表点重みｗ、代表点範囲Ｒ、クラスタの粒度を定めるパラメータλ、入力データ点ｘを取得する。
【００９６】
まず、代表点分割部３１は、対応代表点候補ｘ＿ａを初期値としてｎｕｌｌに設定し、最近傍距離ｄ＿ａをλ２に設定する（ステップＳ６１）。なお、対応代表点候補とは、分割対応すべき代表点の候補を意味する。
【００９７】
代表点分割部３１は、代表点群Ｘから全ての代表点を取り出したか否かを判定する（ステップＳ６２）。全ての代表点を取り出していないと判定した場合には（ステップＳ６２；Ｎｏ）、代表点分割部３１は、代表点群Ｘから１つの代表点の座標ｘ＿ｃ、重みｗ＿ｃ、範囲ｒ＿ｃを取り出す（ステップＳ６３）。
【００９８】
代表点分割部３１は、代表点の座標ｘ＿ｃと入力データ点ｘとの距離を算出し、算出した距離をｄ＿ｃに設定する（ステップＳ６４）。代表点分割部３１は、距離ｄ＿ｃが最近傍距離ｄ＿ａより小さいか否かを判定する（ステップＳ６５）。距離ｄ＿ｃが最近傍距離ｄ＿ａより小さくないと判定した場合には（ステップＳ６５；Ｎｏ）、代表点分割部３１は、次の代表点を取り出すべく、ステップＳ６２に移行する。
【００９９】
一方、距離ｄ＿ｃが最近傍距離ｄ＿ａより小さいと判定した場合には（ステップＳ６５；Ｙｅｓ）、代表点分割部３１は、現在の代表点に入力データ点ｘを加えたもので、更新後の範囲ｒ＿ａを計算する（ステップＳ６６）。例えば、代表点分割部３１は、式（１６）、式（１７）を利用して、現在の代表点を更新した場合の更新後の範囲を算出する。
【０１００】
代表点分割部３１は、更新後の範囲ｒ＿ａから代表点の直径σ＿ａを計算し（ステップＳ６７）、計算した直径σ＿ａの中から最大直径を取り出す（ステップＳ６８）。そして、代表点分割部３１は、ｗ＿ｃ＋１≧１６（λ／σ＿ａ）２  且つ  入力データ点ｘが現在の代表点の範囲ｒ＿ｃの外部であるか否かを判定する（ステップＳ６９）。ｗ＿ｃ＋１≧１６（λ／σ＿ａ）２  且つ  入力データ点ｘが現在の代表点の範囲ｒ＿ｃの外部であると判定した場合には（ステップＳ６９；Ｙｅｓ）、代表点分割部３１は、次の代表点を取り出すべく、ステップＳ６２に移行する。すなわち、代表点分割部３１は、ｗ＿ｃ＋１≧１６（λ／σ＿ａ）２であっても、現在の代表点の範囲ｒ＿ｃが外部であれば、対応代表点候補としないようにすべく、ステップＳ６２に移行する。
【０１０１】
一方、ｗ＿ｃ＋１＜１６（λ／σ＿ａ）２  または  入力データ点ｘが現在の代表点の範囲ｒ＿ｃの外部でないと判定した場合には（ステップＳ６９；Ｎｏ）、代表点分割部３１は、対応代表点候補ｘ＿ａを現在の代表点ｘ＿ｃに設定する（ステップＳ７０）。そして、代表点分割部３１は、次の代表点を取り出すべく、ステップＳ６２に移行する。
【０１０２】
ステップＳ６２において、全ての代表点を取り出したと判定した場合には（ステップＳ６２；Ｙｅｓ）、代表点分割部３１は、対応代表点候補ｘ＿ａがｎｕｌｌであるか否かを判定する（ステップＳ７１）。対応代表点候補ｘ＿ａがｎｕｌｌであると判定した場合には（ステップＳ７１；Ｙｅｓ）、代表点分割部３１は、代表点群Ｘに入力データ点ｘを代表点として追加する。このとき、代表点分割部３１は、この代表点の重みｗを１に設定し、この代表点の範囲Ｒを最大値としてｘ、最小値としてｘに設定する（ステップＳ７２）。そして、代表点分割部３１は、代表点分割処理を終了する。
【０１０３】
一方、対応代表点候補ｘ＿ａがｎｕｌｌでないと判定した場合には（ステップＳ７１；Ｎｏ）、代表点分割部３１は、対応代表点候補ｘ＿ａの座標、重み、範囲を更新する（ステップＳ７３）。すなわち、代表点分割部３１は、対応代表点候補ｘ＿ａに入力データ点ｘを追加する。例えば、代表点分割部３１は、式（１４）を利用して、対応代表点候補ｘ＿ａに入力データ点ｘを追加し、対応代表点候補ｘ＿ａの座標を更新する。代表点分割部３１は、式（１５）を利用して、対応代表点候補ｘ＿ａに入力データ点ｘを追加し、対応代表点候補ｘ＿ａの重みｗ＿ａを更新する。代表点分割部３１は、式（１６）を利用して、対応代表点候補ｘ＿ａに入力データ点ｘを追加し、対応代表点候補ｘ＿ａの最大値を更新する。代表点分割部３１は、式（１７）を利用して、対応代表点候補ｘ＿ａに入力データ点ｘを追加し、対応代表点候補ｘ＿ａの最小値を更新する。
【０１０４】
そして、代表点分割部３１は、更新後の重みｗ＿ａ、直径σ＿ａが、ｗ＿ａ≧１６（λ／σ＿ａ）２を満たすか否かを判定する（ステップＳ７４）。更新後の重みｗ＿ａ、直径σ＿ａが、ｗ＿ａ≧１６（λ／σ＿ａ）２を満たすと判定した場合には（ステップＳ７４；Ｙｅｓ）、代表点分割部３１は、対応代表点候補ｘ＿ａの代表点を分割する（ステップＳ７５）。例えば、代表点分割部３１は、式（６）〜式（１３）を利用して、対応代表点候補ｘ＿ａの代表点を分割する。そして、代表点分割部３１は、代表点分割処理を終了する。
【０１０５】
更新後の重みｗ＿ａ、直径σ＿ａが、ｗ＿ａ≧１６（λ／σ＿ａ）２を満たさないと判定した場合には（ステップＳ７４；Ｎｏ）、代表点分割部３１は、対応代表点候補ｘ＿ａの代表点を分割しないで、代表点分割処理を終了する。
【０１０６】
［クラスタリング処理のフローチャート］
図２０は、実施例２に係るクラスタリング処理のフローチャートを示す図である。なお、図２０では、重み付きＤＰ−ｍｅａｎｓ法を適用し、クラスタの追加を判定する際に用いる距離関数としてユークリッド距離を用いた場合について説明する。クラスタリング部１４Ａは、入力パラメータとして、代表点群Ｘ、代表点の重みｗおよびクラスタの粒度を定めるパラメータλを取得する。
【０１０７】
クラスタリング部１４Ａは、クラスタの中心集合Ｕに全ての代表点の重心を代入する（ステップＳ８１）。クラスタリング部１４Ａは、収束したか否かを判定する（ステップＳ８２）。収束していないと判定した場合には（ステップＳ８２；Ｎｏ）、クラスタリング部１４Ａは、代表点群から代表点ｘを取り出す（ステップＳ８３）。そして、クラスタリング部１４Ａは、クラスタの中心集合Ｕの中で最も距離が近い中心ｕを取り出す（ステップＳ８４）。
【０１０８】
クラスタリング部１４Ａは、代表点ｘとｕとの距離がλ／√ｗ以上であるか否かを判定する（ステップＳ８５）。代表点ｘとｕとの距離がλ／√ｗ以上であると判定した場合には（ステップＳ８５；Ｙｅｓ）、クラスタリング部１４Ａは、クラスタの中心集合Ｕに代表点ｘを追加する（ステップＳ８６）。そして、クラスタリング部１４Ａは、ステップＳ８７に移行する。
【０１０９】
一方、代表点ｘとｕとの距離がλ／√ｗ以上でない、すなわちλ／√ｗより小さいと判定した場合には（ステップＳ８５；Ｎｏ）、クラスタリング部１４Ａは、ステップＳ８７に移行する。ステップＳ８７において、クラスタリング部１４Ａは、代表点ｘのラベルを最近傍クラスタのラベルに更新する（ステップＳ８７）。
【０１１０】
続いて、クラスタリング部１４Ａは、代表点群から全ての代表点ｘを取り出したか否かを判定する（ステップＳ８８）。全ての代表点ｘを取り出していないと判定した場合には（ステップＳ８８；Ｎｏ）、クラスタリング部１４Ａは、次の代表点を取り出すべく、ステップＳ８３に移行する。
【０１１１】
一方、全ての代表点ｘを取り出したと判定した場合には（ステップＳ８８；Ｙｅｓ）、クラスタリング部１４Ａは、クラスタの中心集合Ｕからクラスタの中心ｕを取り出す（ステップＳ８９）。クラスタリング部１４Ａは、取り出したｕの座標値を、ｕに対応するラベルがついた代表点の重み付き重心値に更新する（ステップＳ９０）。
【０１１２】
そして、クラスタリング部１４Ａは、クラスタの中心集合Ｕから全てのクラスタの中心ｕを取り出したか否かを判定する（ステップＳ９１）。全てのクラスタの中心ｕを取り出していないと判定した場合には（ステップＳ９１；Ｎｏ）、クラスタリング部１４Ａは、次のクラスタの中心を取り出すべく、ステップＳ８９に移行する。一方、全てのクラスタの中心ｕを取り出したと判定した場合には（ステップＳ９１；Ｙｅｓ）、クラスタリング部１４Ａは、収束判定をすべく、ステップＳ８２に移行する。
【０１１３】
そして、クラスタリング部１４Ａは、収束判定をすべく、ステップＳ８２に移行する。ステップＳ８２において、収束したと判定した場合には（ステップＳ８２；Ｙｅｓ）、クラスタリング部１４Ａは、クラスタの中心集合Ｕを出力し（ステップＳ９２）、クラスタリング処理を終了する。
【０１１４】
［実施例２の効果］
上記実施例２によれば、情報処理装置１は、新たな代表点に含まれるデータ点の範囲を保持する。情報処理装置１は、新たな代表点の重み付けが、新たな代表点が含むデータ点の範囲を示すパラメータの２乗に反比例する値を超えた場合に、前記新たな代表点を異なるクラスタとなるように分割する。かかる構成によれば、情報処理装置１は、データ点の数値が所定値を超えた場合に、代表点を異なるクラスタとなるように分割することで、目的関数値が小さくなるようなクラスタリングを行うことができる。すなわち、情報処理装置１は、代表点を利用した場合であっても、精度を下げないで、クラスタリングを行うことができる。
【０１１５】
また、上記実施例２によれば、情報処理装置１は、重み付け代表点を用いてクラスタリング処理を行う際に、同一のクラスタとして許容するクラスタ中心との距離の閾値を、代表点の重み付けの平方根に反比例した値とする。かかる構成によれば、情報処理装置１は、重み付けクラスタリングを行う場合に、同一のクラスタとして許容するクラスタ中心との距離の閾値を、重み付けを考慮した閾値にすることで、精度の良いクラスタリングを行うことができる。
【実施例３】
【０１１６】
ところで、実施例２では、クラスタリング部１４Ａは、重み付きの代表点を入力として、目的関数を式（３）から式（１８）に変えてバッチクラスタリング処理を実行すると説明した。すなわち、クラスタリング部１４Ａは、それぞれの代表点を最近傍のクラスタに割り振り、入力された重み付きの代表点と最近傍のクラスタの中心との距離がλ／√ｗ以上ならば、新規クラスタを生成する。なお、ｗは入力された代表点の重み、λはクラスタの粒度を定めるパラメータである。しかしながら、クラスタリング部１４Ａは、これに限定されず、近くの２つの重み付きの代表点をクラスタリング（統合）しても良い。
【０１１７】
そこで、実施例３では、重み付き代表点を用いたクラスタリングにおいて、近くにある重み付きの代表点をクラスタリング（統合）する場合を説明する。
【０１１８】
［実施例３に係る情報処理装置の構成］
図２１は、実施例３に係る情報処理装置の構成を示す機能ブロック図である。なお、図１５に示す情報処理装置１と同一の構成については同一符号を示すことで、その重複する構成および動作の説明については省略する。実施例２と実施例３とが異なるところは、クラスタリング部１４Ａをクラスタリング部１４Ｂに変更した点にある。実施例２と実施例３とが異なるところは、記憶部２０にコスト関数表２３、代表点／クラスタ対応表２４およびクラスタ中心集合２５を追加した点にある。
【０１１９】
クラスタリング部１４Ｂは、複数の代表点の中から２つの代表点を選択して統合する。例えば、クラスタリング部１４Ｂは、複数の代表点の中からコスト関数を用いて２つの代表点を選択し、２つの代表点を統合する条件に合致する場合には、この２つの代表点を統合する。ここでいうコスト関数とは、２つの代表点を仮に統合した場合の改善幅を計算する関数である。なお、コスト関数および２つの代表点を統合する条件の詳細は、後述するものとする。また、２つの対象を選択して統合する処理は、Ｍｅｒｇｅアルゴリズムにより実現できる。Ｍｅｒｇｅアルゴリズムは、一例として、「J.Lee  ｅt  al.，“Online  video  segmentation  by  Bayesian  split-merge  clustering”，In  ECCV2012．」に記載の技術を用いることができる。
【０１２０】
ここで、コスト関数表２３のデータ構造を、図２２を参照して説明する。図２２は、実施例３に係るコスト関数表のデータ構造の一例を示す図である。図２２に示すように、コスト関数表２３は、２つの代表点ＩＤに対するコスト関数値を記憶する。代表点ＩＤは、代表点を識別するＩＤ（Identifier）である。一例として、「１」および「２」の２つの代表点ＩＤに対するコスト関数値は、−０．５である。「１」および「３」の２つの代表点ＩＤに対するコスト関数値は、０．３である。コスト関数値は、コスト関数の設計によるが、例えば、小さい程、改善幅が大きい。
【０１２１】
代表点／クラスタ対応表２４のデータ構造を、図２３を参照して説明する。図２３は、実施例３に係る代表点／クラスタ対応表のデータ構造の一例を示す図である。図２３に示すように、代表点／クラスタ対応表２４は、代表点ＩＤおよびクラスタＩＤを対応付けて記憶する。代表点ＩＤは、代表点を識別するＩＤである。クラスタＩＤは、クラスタを識別するＩＤである。一例として、代表点ＩＤが「１」である場合に、クラスタＩＤとして「１」と記憶している。代表点ＩＤが「２」である場合に、クラスタＩＤとして「１」と記憶している。すなわち、代表点ＩＤが「１」と「２」のクラスタは、同一であることを示す。
【０１２２】
クラスタ中心集合２５のデータ構造を、図２４を参照して説明する。図２４は、実施例３に係るクラスタ中心集合のデータ構造の一例を示す図である。図２４に示すように、クラスタ中心集合２５は、クラスタＩＤおよびクラスタ中心を対応付けて記憶する。クラスタＩＤは、クラスタを識別するＩＤである。クラスタ中心は、クラスタの中心座標である。一例として、クラスタＩＤが「１」である場合に、クラスタ中心として（０．１，０．２，０．３，・・・）と記憶している。
【０１２３】
［クラスタリング処理の流れの一例］
図２５は、実施例３に係るクラスタリング処理の流れの一例を示す図である。なお、改善幅が大きければ大きい程、コスト関数の値は小さくなるように設計されているとする。
【０１２４】
図２５左図に示すように、クラスタリング部１４Ｂは、２つの代表点を仮に統合した場合のコスト関数の改善幅を計算する。一例として、クラスタリング部１４Ｂは、代表点番号として「１」の代表点ｄ１１と「３」の代表点ｄ１３を選択し、選択した２つの代表点を統合した場合のコスト関数の改善幅を計算する。ここでは、代表点番号「１」の代表点ｄ１１および代表点番号「３」の代表点ｄ１３のコスト関数の値は、０．３である。クラスタリング部１４Ｂは、代表点番号として「１」の代表点ｄ１１と「２」の代表点ｄ１２を選択し、選択した２つの代表点を統合した場合のコスト関数の改善幅を計算する。ここでは、代表点番号「１」の代表点ｄ１１および代表点番号「２」の代表点ｄ１２のコスト関数の値は、−０．５である。同様に、クラスタリング部１４Ｂは、他の２つの代表点を仮に統合した場合のコスト関数の改善幅を計算する。
【０１２５】
図２５中図に示すように、クラスタリング部１４Ｂは、コスト関数の改善幅が最大の２つの代表点を選択する。ここでは、コスト関数の改善幅が最大の２つの代表点は、代表点番号「１」の代表点ｄ１１および代表点番号「２」の代表点ｄ１２で示される２つの代表点である。
【０１２６】
図２５右図に示すように、クラスタリング部１４Ｂは、選択した２つの代表点が統合する条件に合致する場合には、この２つの代表点を統合する。ここでは、クラスタリング部１４Ｂは、代表点番号「１」の代表点ｄ１１と代表点番号「２」の代表点ｄ１２を統合し、代表点番号「２」の代表点ｄ１２を代表点番号「１」の代表点ｄ１１に統合するとする。すると、クラスタリング部１４Ｂは、代表点番号「１」の代表点ｄ１１を、２つの代表点の重み付き重心であってクラスタＩＤが「１」となる重み付き重心ｄ１１´に更新する。そして、クラスタリング部１４Ｂは、統合を行った代表点ｄ１１´と、その他の代表点のコスト関数を再計算する。
【０１２７】
そして、クラスタリング部１４Ｂは、再計算した結果を用いて、コスト関数の改善幅が最大の２つの代表点を選択し、選択した２つの代表点が統合条件を満たさなくなるまで、クラスタリング処理を継続する。
【０１２８】
［代表点を統合する条件］
ここで、代表点を統合する条件を、図２６を参照して説明する。図２６は、実施例３に係る代表点を統合する条件を説明する図である。
【０１２９】
図２６に示すように、左図は、代表点を統合する前の状態であり、代表点が２個の場合である。右図は、代表点を統合した後の状態であり、代表点が１個の場合である。かかる場合に、代表点を統合する条件は、代表点を分割する条件と同様の議論により、目的関数の期待値について、代表点を統合した方が代表点を統合する前より小さくなることである。すなわち、２つの代表点を１個に統合した場合の目的関数の期待値が、２つの代表点そのままの目的関数の期待値より小さければ、２つの代表点を統合した方が良い。
【０１３０】
なお、代表点が重み付きである場合には、目的関数の期待値は、式（１８）により、代表点の重みと距離の期待値の積を用いて計算される。すなわち、２つの代表点を１点に統合した場合の目的関数の期待値は、２つの代表点の重みの和と、２つの代表点に含まれるデータ点および統合先の代表点の距離の期待値との積と、クラスタ粒度を定めるパラメータから計算される項とを用いて計算される。２つの代表点を１点に統合しない場合の目的関数の期待値は、一方の代表点（第１代表点）の重みおよび第１代表点に含まれるデータ点と第１代表点との距離の期待値の積と、他方の代表点（第２代表点）の重みおよび第２代表点に含まれるデータ点と第２代表点との距離の期待値の積との和と、クラスタ粒度を定めるパラメータから計算される項とを用いて計算される。
【０１３１】
［コスト関数］
ここで、代表点が一様分布である場合のコスト関数は、例えば、以下の式（１９）で表される。なお、Ｃ１およびＣ２は、それぞれ代表点である。ｗ１は、Ｃ１の重みであり、ｗ２は、Ｃ２の重みである。ｄ１は、統合後の代表点（Ｃ１およびＣ２の重み付き重心）とＣ１との距離であり、ｄ２は、統合後の代表点（Ｃ１およびＣ２の重み付き重心）とＣ２との距離である。λは、クラスタの粒度を定めるパラメータである。
ＳＣＯＳＴ（Ｃ１，Ｃ２）＝ｗ１×ｄ１２＋ｗ２×ｄ２２−λ２・・・（１９）
【０１３２】
式（１９）で表されるコスト関数の導出を、図２７を参照して説明する。図２７は、実施例３に係るコスト関数の導出の前提を示す図である。
【０１３３】
図２７に示すように、左図は、代表点を統合する前の状態であり、代表点が２個の場合である。Ｃ１は、重みをｗ１とする代表点である。σ１ｎは、代表点Ｃ１のｎ次元での範囲である。Ｃ２は、重みをｗ２とする代表点である。σ２ｎは、代表点Ｃ２のｎ次元での範囲である。このような前提の下、代表点Ｃ１に含まれるデータ点の誤差の期待値は、以下の式（２０）で表される。なお、式（２０）では、各次元の誤差項の期待値を加算している。
データ点の誤差の期待値ｋ１＝（σ１１２／１２＋・・・＋σ１ｎ２／１２＋・・・）・・・（２０）
【０１３４】
同様に、代表点Ｃ２に含まれるデータ点の誤差の期待値は、以下の式（２１）で表される。なお、式（２１）では、各次元の誤差項の期待値を加算している。
データ点の誤差の期待値ｋ２＝（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）・・・（２１）
【０１３５】
右図は、代表点を統合した後の状態であり、代表点が１個の場合である。Ｃ１およびＣ２は、左図と同様である。σ’１ｎは、ｎ次元の統合後の代表点と代表点Ｃ１との間の範囲であり、ｄ１は、統合後の代表点とＣ１との距離である。σ’２ｎは、ｎ次元の統合後の代表点と代表点Ｃ２との間の範囲であり、ｄ２は、統合後の代表点とＣ２との距離である。このような前提の下、代表点Ｃ１に含まれるデータ点のある次元ｎの誤差の期待値は、以下の式（２２）で表される。
【数４】
0006707946.tif 000005
【０１３６】
したがって、代表点Ｃ１に含まれるデータ点の誤差の期待値は、以下の式（２３）で表される。なお、式（２３）では、各次元の誤差項の期待値を加算している。
データ点の誤差の期待値ｇ１＝（σ‘１１２＋・・・＋σ‘１ｎ２＋・・・）＋（σ１１２／１２＋・・・＋σ１ｎ２／１２＋・・・）・・・（２３）
なお、（σ‘１１２＋・・・＋σ‘１ｎ２＋・・・）は、統合後の代表点とＣ１との距離を示すｄ１２に対応する。
【０１３７】
同様に、代表点Ｃ２に含まれるデータ点の誤差の期待値は、以下の式（２４）で表される。なお、式（２４）では、各次元の誤差項の期待値を加算している。
データ点の誤差の期待値ｇ２＝（σ‘２１２＋・・・＋σ‘２ｎ２＋・・・）＋（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）・・・（２４）
なお、（σ‘２１２＋・・・＋σ‘２ｎ２＋・・・）は、統合後の代表点とＣ２との距離を示すｄ２２に対応する。
【０１３８】
代表点が１点の場合の目的関数の期待値Ｍ１は、式（２３）および式（２４）を式（１８）で示した重み付きの代表点の場合の目的関数に代入すると、式（２５）で表される。
Ｍ１＝ｗ１×ｇ１＋ｗ２×ｇ２＋λ２＝｛ｄ１２＋（σ１１２／１２＋・・・＋σ１ｎ２／１２＋・・・）｝＋ｗ２×｛ｄ２２＋（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）｝＋λ２・・・（２５）
【０１３９】
代表点が２点の場合の目的関数の期待値Ｍ２は、式（２０）および式（２１）を式（１８）で示した重み付きの代表点の場合の目的関数に代入すると、式（２６）で表される。
Ｍ２＝ｗ１×ｋ１＋ｗ２×ｋ２＋２λ２＝ｗ１×（σ１１２／１２＋・・・＋σ１ｎ２／１２＋・・・）｝＋ｗ２×（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）＋２λ２・・・（２６）
【０１４０】
コスト関数ＳＣＯＳＴ（Ｃ１，Ｃ２）は、代表点が１点の場合の目的関数の期待値Ｍ１式（２５）から代表点が２点の場合の目的関数の期待値Ｍ２式（２６）を減じて得られる式であるから、式（１９）で表すことができる。すなわち、コスト関数ＳＣＯＳＴ（Ｃ１，Ｃ２）が０以下であれば、２つの代表点Ｃ１およびＣ２を統合した方が良い。
【０１４１】
なお、データ点の誤差の期待値は、統合後の代表点と代表点Ｋとの距離ｄを用いて計算すると説明した。データ点の誤差の期待値は、これに限定されず、統合前の代表点の情報を記憶しておき、代表点Ｋおよび統合前の代表点の距離と代表点Ｋおよび統合後の代表点の距離との誤差を計算するようにしても良い。このようなデータ点の誤差の期待値を用いる場合のコスト関数ＳＣＯＳＴ（Ｃ１，Ｃ２）は、以下の式（２７）で表される。なお、ｄｏｌｄ，Ｋは、代表点Ｋと統合前の代表点（クラスタ中心）との距離を示し、ｄｎｅｗ，Ｋは、代表点Ｋと統合後の代表点（クラスタ中心）との距離を示す。
【数５】
0006707946.tif 000006
【０１４２】
これにより、データ点の誤差の期待値として、統合された場合の統合前後の代表点の情報を利用することにより、統合前の代表点が失われることにより誤差が蓄積してしまうことを防止できる。
【０１４３】
［クラスタリング処理のフローチャート］
図２８は、実施例３に係るクラスタリング処理のフローチャートを示す図である。なお、図２８では、Ｍｅｒｇｅアルゴリズムを適用し、クラスタの追加を判定する際に用いる距離関数としてユークリッド距離を用いた場合について説明する。クラスタリング部１４Ｂは、入力パラメータとして、代表点群Ｘ、代表点の重みｗおよび最大許容クラスタ径λを取得する。最大許容クラスタ径は、クラスタの粒度を定めるパラメータに対応する。
【０１４４】
クラスタリング部１４Ｂは、代表点ｘｉ，ｘｊを統合した場合のコスト関数値ＳＣＯＳＴを計算し、計算した結果をコスト関数表２３に代入する（ステップＳ１０１）。なお、ｉ，ｊは、代表点ＩＤ（代表点番号）である。クラスタリング部１４Ｂは、クラスタの中心集合Ｕに代表点群Ｘを代入する（ステップＳ１０２）。そして、クラスタリング部１４Ｂは、代表点／クラスタ対応表２４の各クラスタＩＤの値を代表点ＩＤで初期化する（ステップＳ１０３）。
【０１４５】
続いて、クラスタリング部１４Ｂは、コスト関数表２３からコスト関数が最小となる時の代表点ＩＤのペア（ｉ，ｊ）を取得する（ステップＳ１０４）。クラスタリング部１４Ｂは、コスト関数値（ｉ，ｊ）が０以上であるか否かを判定する（ステップＳ１０５）。コスト関数値（ｉ，ｊ）が０以上であると判定した場合には（ステップＳ１０５；Ｙｅｓ）、クラスタリング部１４Ｂは、ステップＳ１１０に移行する。
【０１４６】
一方、コスト関数値（ｉ，ｊ）が０未満であると判定した場合には（ステップＳ１０５；Ｎｏ）、クラスタリング部１４Ｂは、代表点／クラスタ対応表２４の中で、代表点ＩＤが「ｊ」であるクラスタＩＤを「ｉ」に変更する（ステップＳ１０６）。なお、クラスタリング部１４Ｂは、代表点ＩＤが「ｉ」であるクラスタＩＤを「ｊ」に変更しても良い。
【０１４７】
そして、クラスタリング部１４Ｂは、クラスタ中心集合２５の中のクラスタＩＤが「ｉ」となるクラスタの重心を、代表点／クラスタ対応表２４でクラスタＩＤが「ｉ」となる代表点の重み付き重心に更新する（ステップＳ１０７）。クラスタリング部１４Ｂは、クラスタ中心集合２５の中のクラスタＩＤが「ｊ」となるクラスタ（代表点）を削除する（ステップＳ１０８）。
【０１４８】
そして、クラスタリング部１４Ｂは、更新されたクラスタ情報からコスト関数値ＳＣＯＳＴを再計算し、コスト関数表２３の値を更新する（ステップＳ１０９）。そして、クラスタリング部１４Ｂは、ステップＳ１０４に移行する。
【０１４９】
ステップＳ１１０において、クラスタリング部１４Ｂは、クラスタ中心集合２５を出力する（ステップＳ１１０）。そして、クラスタリング部１４Ｂは、クラスタリング処理を終了する。
【０１５０】
［実施例３の効果］
上記実施例３によれば、情報処理装置１は、代表点を用いてクラスタリング処理を行う際に、２つの代表点を選択し、２つの代表点を１点に統合した場合の目的関数の期待値が、２つの代表点を１点に統合しない場合の目的関数の期待値より小さくなる場合に、２つの代表点を１点に統合する。かかる構成によれば、情報処理装置１は、代表点を利用した場合であっても、精度を下げないで、クラスタリングを行うことができる。
【実施例４】
【０１５１】
ところで、実施例３では、クラスタリング部１４Ｂは、２つの代表点が統合する条件に合致する場合には、この２つの代表点を統合し、統合先の代表点を２つの代表点の重み付き重心に更新する。しかしながら、クラスタリング部１４Ｂは、これに限定されず、２つの代表点が統合する条件に合致する場合には、統合先の代表点をどちらか一方の代表点に更新しても良い。
【０１５２】
そこで、実施例４に係るクラスタリング部１４Ｂは、２つの代表点が統合する条件に合致する場合には、この２つの代表点を統合し、統合先の代表点をどちらか一方の代表点に更新する場合を説明する。
【０１５３】
［実施例４に係る情報処理装置の構成］
実施例４に係る情報処理装置１の構成は、実施例３に係る情報処理装置１と同一の構成であるので、同一符号を示すことで、その重複する構成の説明については省略する。
【０１５４】
［クラスタリング処理の概要］
図２９は、実施例４に係るクラスタリング処理の概要を示す図である。図２９に示すように、クラスタリング部１４Ｂは、２つの代表点を統合する際、２つの代表点の重心に統合するのではなく、２つの代表点のうちどちらか一方の代表点に統合する。ここでは、クラスタリング部１４Ｂは、代表点ｄ２１および代表点ｄ２２を統合する場合に、代表点ｄ２１，ｄ２２のうち代表点ｄ２１に統合する。これにより、クラスタリング部１４Ｂは、統合を行っても、統合先の代表点は動かないので、統合により代表点の座標が移動してしまい本来統合されるべき代表点が統合されないという問題を生じない。すなわち、クラスタリング部１４Ｂは、統合操作で代表点が移動すると、仮に移動しなければ統合条件が満たされていたところ、移動することにより満たされなくなるという問題が生じない。
【０１５５】
［クラスタリング処理の流れの一例］
図３０は、実施例４に係るクラスタリング処理の流れの一例を示す図である。なお、改善幅が大きければ大きい程、コスト関数の値は小さくなるように設計されているとする。
【０１５６】
図３０上段左図に示すように、クラスタリング部１４Ｂは、２つの代表点を仮に統合した場合のコスト関数の改善幅を計算する。一例として、クラスタリング部１４Ｂは、代表点番号として「１」の代表点ｄ１１と「３」の代表点ｄ１３を選択し、選択した２つの代表点を統合した場合のコスト関数の改善幅を計算する。ここでは、代表点番号「１」の代表点ｄ１１および代表点番号「３」の代表点ｄ１３のコスト関数の値は、０．３である。クラスタリング部１４Ｂは、代表点番号として「１」の代表点ｄ１１と「２」の代表点ｄ１２を選択し、選択した２つの代表点を統合した場合のコスト関数の改善幅を計算する。ここでは、代表点番号「１」の代表点ｄ１１および代表点番号「２」の代表点ｄ１２のコスト関数の値は、−０．５である。同様に、クラスタリング部１４Ｂは、他の２つの代表点を仮に統合した場合のコスト関数の改善幅を計算する。
【０１５７】
図３０上段中図に示すように、クラスタリング部１４Ｂは、コスト関数の改善幅が最大の２つの代表点を選択する。ここでは、コスト関数の改善幅が最大の２つの代表点は、代表点番号「１」の代表点ｄ１１および代表点番号「２」の代表点ｄ１２で示される２つの代表点である。
【０１５８】
図３０上段右図に示すように、クラスタリング部１４Ｂは、選択した２つの代表点が統合する条件に合致する場合には、この２つの代表点を統合する。ここでは、クラスタリング部１４Ｂは、代表点番号「１」の代表点ｄ１１および代表点番号「２」の代表点ｄ１２を統合し、代表点番号「２」の代表点ｄ１２を代表点番号「１」の代表点ｄ１１に統合するとする。すると、クラスタリング部１４Ｂは、コスト関数表２３において、統合により消滅する代表点番号「２」の代表点をどちらか一方とするコスト関数の値だけを更新する。ここでは、コスト関数表２３で、代表点番号「２」の代表点をどちらか一方とするコスト関数の値が「∞」に更新される。すなわち、クラスタリング部１４Ｂは、このタイミングで、代表点番号「１」の代表点ｄ１１を、２つの代表点の重み付き重心であってクラスタＩＤが「１」となる重み付き重心に更新しない。そして、クラスタリング部１４Ｂは、さらに、コスト関数の改善幅が最大の２つの代表点を選択し、選択した２つの代表点が統合条件に満たさなくなるまで、クラスタリング処理を継続する。
【０１５９】
図３０下段左図に示すように、クラスタリング部１４Ｂは、統合が１回でも起こった場合には、同一の代表点に統合された代表点の重み付き重心を新しい代表点の座標として採用する。ここでは、クラスタリング部１４Ｂは、同一の代表点に統合された、代表点番号「１」の代表点ｄ１１の重み付き重心を、クラスタＩＤが「１」となる座標ｇ０に更新する。
【０１６０】
［コスト関数］
ここで、実施例４に係る、代表点が一様分布である場合のコスト関数は、例えば、以下の式（２８）で表される。なお、Ｃ１およびＣ２は、それぞれ代表点である。ｗ１は、Ｃ１の重みであり、ｗ２は、Ｃ２の重みである。ｄは、代表点Ｃ１と代表点Ｃ２との距離である。λは、クラスタの粒度を定めるパラメータである。
ＳｍＣＯＳＴ（Ｃ１，Ｃ２）＝ｗ２×ｄ２−λ２・・・（２８）
【０１６１】
式（２８）で表されるコスト関数の導出を、図３１を参照して説明する。図３１は、実施例４に係るコスト関数の導出の前提を示す図である。
【０１６２】
図３１に示すように、左図は、代表点を統合する前の状態であり、代表点が２個の場合である。Ｃ１は、重みをｗ１とする代表点である。σ１ｎは、代表点Ｃ１のｎ次元での範囲である。Ｃ２は、重みをｗ２とする代表点である。σ２ｎは、代表点Ｃ２のｎ次元での範囲である。このような前提の下、代表点Ｃ１に含まれるデータ点の誤差の期待値は、式（２０）と同様である。同様に、代表点Ｃ２に含まれるデータ点の誤差の期待値は、式（２１）と同様である。
【０１６３】
右図は、代表点を統合した後の状態であり、代表点が１個の場合である。Ｃ１およびＣ２は、左図と同様である。σ’ｎは、ｎ次元における代表点Ｃ１と代表点Ｃ２との間の範囲であり、ｄは、代表点Ｃ１と代表点Ｃ２との距離である。このような前提の下、代表点Ｃ２に含まれるデータ点のある次元ｎの誤差の期待値は、以下の式（２９）で表される。
【数６】
0006707946.tif 000007
【０１６４】
したがって、代表点Ｃ２に含まれるデータ点の誤差の期待値は、以下の式（３０）で表される。なお、式（３０）では、各次元の誤差項の期待値を加算している。
データ点の誤差の期待値ｇ３＝（σ‘１２＋・・・＋σ‘ｎ２＋・・・）＋（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）・・・（３０）
なお、（σ‘１２＋・・・＋σ‘ｎ２＋・・・）は、代表点Ｃ１と代表点Ｃ２との距離を示すｄ２に対応する。
【０１６５】
代表点Ｃ１に含まれるデータ点の誤差の期待値は、式（２０）と同様である。
【０１６６】
代表点が１点の場合の目的関数の期待値Ｍ３は、式（３０）および式（２０）を式（１８）で示した重み付きの代表点の場合の目的関数に代入すると、式（３１）で表される。
Ｍ３＝ｗ１×ｋ１＋ｗ２×ｇ３＝ｗ１×（σ１１２／１２＋・・・＋σ１ｎ２／１２＋・・・）｝＋ｗ２×｛ｄ２＋（σ２１２／１２＋・・・＋σ２ｎ２／１２＋・・・）｝＋λ２・・・（３１）
【０１６７】
代表点が２点の場合の目的関数の期待値は、式（２６）で表わされるＭ２と同様である。
【０１６８】
コスト関数ＳｍＣＯＳＴ（Ｃ１，Ｃ２）は、代表点が１点の場合の目的関数の期待値Ｍ３（式（３１）から代表点が２点の場合の目的関数の期待値Ｍ２式（２６）を減じて得られる式であるから、式（２８）で表すことができる。すなわち、コスト関数ＳｍＣＯＳＴ（Ｃ１，Ｃ２）が０以下であれば、２つの代表点Ｃ１およびＣ２を統合した方がよい。
【０１６９】
［クラスタリング処理のフローチャート］
図３２は、実施例４に係るクラスタリング処理のフローチャートを示す図である。なお、図３２では、Ｍｅｒｇｅアルゴリズムを適用し、クラスタの追加を判定する際に用いる距離関数としてユークリッド距離を用いた場合について説明する。クラスタリング部１４Ｂは、入力パラメータとして、代表点群Ｘ、代表点の重みｗおよび最大許容クラスタ径λを取得する。最大許容クラスタ径は、クラスタの粒度を定めるパラメータに対応する。
【０１７０】
クラスタリング部１４Ｂは、代表点ｘｉ，ｘｊを統合した場合のコスト関数値ＳｍＣＯＳＴを計算し、計算した結果をコスト関数表２３に代入する（ステップＳ１２１）。なお、ｉ，ｊは、代表点ＩＤ（代表点番号）である。クラスタリング部１４Ｂは、クラスタの中心集合Ｕに代表点群Ｘを代入する（ステップＳ１２２）。そして、クラスタリング部１４Ｂは、代表点／クラスタ対応表２４の各クラスタＩＤの値を代表点ＩＤで初期化する（ステップＳ１２３）。
【０１７１】
続いて、クラスタリング部１４Ｂは、コスト関数表２３からコスト関数が最小となる時の代表点ＩＤのペア（ｉ，ｊ）を取得する（ステップＳ１２４）。クラスタリング部１４Ｂは、コスト関数値（ｉ，ｊ）が０以上であるか否かを判定する（ステップＳ１２５）。コスト関数値（ｉ，ｊ）が０以上であると判定した場合には（ステップＳ１２５；Ｙｅｓ）、クラスタリング部１４Ｂは、ステップＳ１２９に移行する。
【０１７２】
一方、コスト関数値（ｉ，ｊ）が０未満であると判定した場合には（ステップＳ１２５；Ｎｏ）、クラスタリング部１４Ｂは、代表点／クラスタ対応表２４の中で、代表点ＩＤが「ｊ」であるクラスタＩＤを「ｉ」に変更する（ステップＳ１２６）。なお、クラスタリング部１４Ｂは、代表点ＩＤが「ｉ」であるクラスタＩＤを「ｊ」に変更しても良い。
【０１７３】
そして、クラスタリング部１４Ｂは、クラスタ中心集合２５の中のクラスタＩＤが「ｊ」となるクラスタを削除する（ステップＳ１２７）。クラスタリング部１４Ｂは、コスト関数表２３で添字の何れかに「ｊ」が含まれるものの値を「∞」に更新する（ステップＳ１２８）。そして、クラスタリング１４Ｂは、ステップＳ１２４に移行する。
【０１７４】
ステップＳ１２９において、クラスタリング部１４Ｂは、統合が１回以上起こったか否かを判定する（ステップＳ１２９）。統合が１回以上起こったと判定した場合には（ステップＳ１２９；Ｙｅｓ）、クラスタリング部１４Ｂは、統合が起こった代表点に対応するクラスタについて、以下の処理を行う。すなわち、クラスタリング部１４Ｂは、クラスタ中心集合２５の中のクラスタ中心を、代表点／クラスタ対応表２４でそのクラスタに割振られた代表点の重み付き重心に更新する（ステップＳ１３０）。
【０１７５】
そして、クラスタリング部１４Ｂは、更新されたクラスタ情報からコスト関数値ＳｍＣＯＳＴを再計算し、コスト関数表２３の値を更新する（ステップＳ１３１）。そして、クラスタリング部１４Ｂは、ステップＳ１２４に移行する。
【０１７６】
一方、統合が１回以上起こらなかったと判定した場合には（ステップＳ１２９；Ｎｏ）、クラスタリング部１４Ｂは、クラスタリング部１４Ｂは、クラスタ中心集合２５を出力する（ステップＳ１３２）。そして、クラスタリング部１４Ｂは、クラスタリング処理を終了する。
【０１７７】
［実施例４の効果］
上記実施例４によれば、情報処理装置１は、２つの代表点のうちいずれかの代表点を統合先の代表点として選択し、さらに、統合操作が終了すると、統合先の代表点の情報を用いて、統合先の代表点の座標を再計算する。かかる構成によれば、情報処理装置１は、統合操作が終了するまで、統合先の代表点の座標を移動しない。この結果、情報処理装置１は、統合操作で代表点の座標を移動してしまうと、本来統合されたであろう代表点が統合されなくなることを防止できる。また、情報処理装置１は、代表点を利用した場合であっても、精度を下げないで、クラスタリングを行うことができる。
【０１７８】
ここで、実施例３〜４で説明したそれぞれのクラスタリング処理により最適化される目的関数の値は、実験により、以下のように計算される。まず、ＤＰ−ｍｅａｎｓ法によるクラスタリング処理により最適化される目的関数の値は、７．３３×１０１１であり、計算時間は、３２１．１２１９秒である。実施例３に係るクラスタリング処理により最適化される目的関数の値は、３．３２×１０１１であり、計算時間は、４３５．４８６４秒である。実施例４に係るクラスタリング処理により最適化される目的関数の値は、３．２４×１０１１であり、計算時間は、４３４．２８３７秒である。
【０１７９】
これにより、実施例３および実施例４のクラスタリング処理により最適化される目的関数の値が、他の方法と比べて小さくなる。すなわち、Ｍｅｒｇｅアルゴリズムを利用した統合操作を行った場合の方が小さい目的関数が得られる。つまり、Ｍｅｒｇｅアルゴリズムを利用した統合操作を行った場合の方が目的関数の値が改善される。
【０１８０】
［その他］
なお、実施例１では、クラスタリング部１４は、グリッドリスト２１中の重み付きの代表点を入力としてバッチクラスタリング処理を実行する。このとき、クラスタリング部１４は、目的関数を式（３）として実行すると説明した。しかしながら、クラスタリング部１４は、これに限定されず、目的関数を式（１８）として実行しても良い。
【０１８１】
また、実施例１では、代表点圧縮部１３は、グリッドに代表点の個数が最大保持点数を超えないようにするために、グリッドに含まれる代表点の中から選択された代表点に他の代表点をマージして、新規の代表点とすると説明した。しかしながら、代表点圧縮部１３は、これに限定されず、近傍の代表点を選択し、選択した代表点の位置の平均を算出して、平均の位置を新規の代表点としても良い。
【０１８２】
また、図示した情報処理装置１の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、情報処理装置１の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、代表点更新部１２と、代表点圧縮部１３とを１つの部として統合しても良い。また、代表点更新部１２をグリッドを生成する生成部と、データ点をグリッドに追加する追加部と、代表点圧縮部１３にデータを圧縮させる圧縮部とに分散しても良い。また、記憶部２０を情報処理装置１の外部装置としてネットワーク経由で接続するようにしても良い。
【０１８３】
また、上記実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１に示した情報処理装置１と同様の機能を実現するデータクラスタリングプログラムを実行するコンピュータの一例を説明する。図３３は、データクラスタリングプログラムを実行するコンピュータの一例を示す図である。
【０１８４】
図３３に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０３と、ユーザからのデータの入力を受け付ける入力装置２１５と、表示装置２０９を制御する表示制御部２０７とを有する。また、コンピュータ２００は、記憶媒体からプログラムなどを読取るドライブ装置２１３と、ネットワークを介して他のコンピュータとの間でデータの授受を行う通信制御部２１７とを有する。また、コンピュータ２００は、各種情報を一時記憶するメモリ２０１と、ＨＤＤ２０５を有する。そして、メモリ２０１、ＣＰＵ２０３、ＨＤＤ２０５、表示制御部２０７、ドライブ装置２１３、入力装置２１５、通信制御部２１７は、バス２１９で接続されている。
【０１８５】
ドライブ装置２１３は、例えばリムーバブルディスク２１１用の装置である。ＨＤＤ２０５は、データクラスタリングプログラム２０５ａおよびデータクラスタリング関連情報２０５ｂを記憶する。
【０１８６】
ＣＰＵ２０３は、データクラスタリングプログラム２０５ａを読み出して、メモリ２０１に展開し、プロセスとして実行する。かかるプロセスは、情報処理装置１の各機能部に対応する。データクラスタリング関連情報２０５ｂは、グリッドリスト２１および代表点リスト２２に対応する。そして、例えばリムーバブルディスク２１１が、データクラスタリングプログラム２０５ａなどの各情報を記憶する。
【０１８７】
なお、データクラスタリングプログラム２０５ａについては、必ずしも最初からＨＤＤ２０５に記憶させておかなくても良い。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に当該プログラムを記憶させておく。そして、コンピュータ２００がこれらからデータクラスタリングプログラム２０５ａを読み出して実行するようにしても良い。
【符号の説明】
【０１８８】
１  情報処理装置
１０  制御部
１１  データ取得部
１２  代表点更新部
１３  代表点圧縮部
１４，１４Ａ、１４Ｂ  クラスタリング部
２０  記憶部
２１  グリッドリスト
２２，２２Ａ  代表点リスト
２３  コスト関数表
２４  代表点／クラスタ対応表
２５  クラスタ中心集合
３１  代表点分割部
【図１】
0006707946.tif 000008
【図２】
0006707946.tif 000009
【図３】
0006707946.tif 000010
【図４】
0006707946.tif 000011
【図５】
0006707946.tif 000012
【図６】
0006707946.tif 000013
【図７Ａ】
0006707946.tif 000014
【図７Ｂ】
0006707946.tif 000015
【図８】
0006707946.tif 000016
【図９】
0006707946.tif 000017
【図１０】
0006707946.tif 000018
【図１１】
0006707946.tif 000019
【図１２】
0006707946.tif 000020
【図１３】
0006707946.tif 000021
【図１４】
0006707946.tif 000022
【図１５】
0006707946.tif 000023
【図１６】
0006707946.tif 000024
【図１７】
0006707946.tif 000025
【図１８】
0006707946.tif 000026
【図１９】
0006707946.tif 000027
【図２０】
0006707946.tif 000028
【図２１】
0006707946.tif 000029
【図２２】
0006707946.tif 000030
【図２３】
0006707946.tif 000031
【図２４】
0006707946.tif 000032
【図２５】
0006707946.tif 000033
【図２６】
0006707946.tif 000034
【図２７】
0006707946.tif 000035
【図２８】
0006707946.tif 000036
【図２９】
0006707946.tif 000037
【図３０】
0006707946.tif 000038
【図３１】
0006707946.tif 000039
【図３２】
0006707946.tif 000040
【図３３】
0006707946.tif 000041
【図３４】
0006707946.tif 000042
【図３５】
0006707946.tif 000043