(57)【特許請求の範囲】
【請求項１】
複数のデータ点を複数のクラスタにクラスタリングするクラスタリング装置であって、
前記複数のデータ点の各々について、前記データ点の位置と前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する所属クラスタ中心探索部と、
前記複数のクラスタの各々について、前記所属クラスタ中心探索部により前記クラスタに所属すると決定されたデータ点の位置に基づいて、前記クラスタの中心位置を更新し、更新前と更新後の前記クラスタの中心位置の移動距離を計算し、
前記複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、前記データ点についての前記所属クラスタ中心探索部により所属するクラスタを決定する処理を行う頻度を決定するクラスタ中心更新部と、
予め定められた収束条件を満たすまで、前記所属クラスタ中心探索部による決定と、前記クラスタ中心更新部による決定とを繰り返す収束判定部と、
を含み、
前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記クラスタ中心更新部によって前記データ点について決定された前記頻度に基づいて、所属するクラスタを決定するか否かを判定し、所属するクラスタを決定すると判定された前記データ点の各々について、前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する
クラスタリング装置。
【請求項２】
前記クラスタ中心更新部は、データ点ｘｉの係数をｋiとし、前記データ点ｘｉの前記決定する処理を行う頻度を
【数１】
0006334454.tif 000093
とし、前記データ点ｘｉの所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値を分母とし、予め定められた値を分子とした比率が
【数２】
0006334454.tif 000094
以上、かつ前記所属クラスタ中心探索部の処理回数ｔの値が
【数３】
0006334454.tif 000095
に対して余剰を持たない場合には、前記ｋiをｋi＋１と更新し、前記比率が
【数４】
0006334454.tif 000096
以上であって、かつ、
【数５】
0006334454.tif 000097
未満の場合には、前記ｋiをｋi−γと更新し、前記比率が、
【数６】
0006334454.tif 000098
以上であって、かつ、
【数７】
0006334454.tif 000099
未満の場合には、前記ｋiを更新しないことにより、前記データ点ｘｉについての前記頻度を決定する請求項１記載のクラスタリング装置。
【請求項３】
前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、前記データ点が所属するクラスタの中心位置と、前記所属するクラスタの中心位置と最も近い中心位置を有するクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の上限値の２倍以上である場合、前記データ点と前記複数のクラスタの各々の中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定する請求項１又は２記載のクラスタリング装置。
【請求項４】
前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、
前記データ点が所属するクラスタの中心位置と、前記データ点が属さないクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の上限値の２倍以上である場合、又は、前記距離の上限値が、前記データ点と、前記属さないクラスタの中心位置との距離の下限値以下の場合、
前記データ点と、前記属さないクラスタの中心位置との距離、及び前記データ点と前記データ点が属するクラスタの中心位置との距離を計算せず、
前記データ点が所属するクラスタの中心位置と、前記データ点が属さないクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の２倍以上である場合、又は、前記データ点と前記所属するクラスタの中心位置との距離が、前記距離の下限値以下である場合、前記データ点と、前記属さないクラスタの中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定する請求項３記載のクラスタリング装置。
【請求項５】
前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、
前記データ点と、前記データ点に２番目に近いクラスタの中心位置との距離の下限値が、前記データ点と前記所属するクラスタの中心位置との距離の上限値以上である場合、又は、前記データ点が所属するクラスタの中心位置と、前記所属するクラスタの中心位置と最も近い中心位置を有するクラスタの中心位置との距離が、前記データ点と、前記データ点が所属するクラスタの中心位置との距離の２倍以上である場合、又は前記データ点と、前記データ点が所属するクラスタの中心位置との距離が、前記距離の下限値以下である場合、前記データ点と前記複数のクラスタの各々の中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定する請求項３記載のクラスタリング装置。
【請求項６】
所属クラスタ中心探索部と、クラスタ中心更新部と、収束判定部と、を含む、複数のデータ点を複数のクラスタにクラスタリングするクラスタリング装置における、クラスタリング方法であって、
前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記データ点の位置と前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定し、
前記クラスタ中心更新部は、前記複数のクラスタの各々について、前記所属クラスタ中心探索部により前記クラスタに所属すると決定されたデータ点の位置に基づいて、前記クラスタの中心位置を更新し、更新前と更新後の前記クラスタの中心位置の移動距離を計算し、
前記複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心の位置の移動距離とを重み付けした値に基づいて、前記データ点についての前記所属クラスタ中心探索部により所属するクラスタを決定する処理を行う頻度を決定し、
前記収束判定部は、予め定められた収束条件を満たすまで、前記所属クラスタ中心探索部による決定と、前記クラスタ中心更新部による決定とを繰り返す、
ことを含み、
前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記クラスタ中心更新部によって前記データ点について決定された前記頻度に基づいて、所属するクラスタを決定するか否かを判定し、所属するクラスタを決定すると判定された前記データ点の各々について、前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する
クラスタリング方法。
【請求項７】
コンピュータを、請求項１〜請求項５の何れか１項記載のクラスタリング装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、方法、及びプログラムに係り、特に、データ点が所属するクラスタを決定するクラスタリング装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
図２８に示すように、分類対象である複数のデータ点の各々を、複数のクラスタに分類する際に、クラスタ中心の探索とクラスタ中心の更新とを交互に行うことにより最適化し、クラスタの各々について、複数のデータを分類し、当該クラスタ中心を出力する。
【０００３】
クラスタ中心の探索は、図２９に示すように、複数のデータ点の各々について、当該データ点から最も距離が近いクラスタ中心を探索し、当該クラスタに当該データ点を所属させる。図２９の例においては、クラスタ（２）のクラスタ中心の方が、処理対象となるデータ点に近いため、クラスタ（１）に所属していたデータ点が１つクラスタ（２）に移動することとなる。
【０００４】
クラスタ中心の更新処理は、各クラスタに所属するデータ点の重心を新たなクラスタ中心として再設定する。そして、上記のクラスタ中心の探索処理と、クラスタ中心の更新処理とを収束するまで交互に最適化する。
【０００５】
従来は、Ｌｌｏｙｄ法（非特許文献１）、Ｅｌｋａｎ法（非特許文献２）、及びＨａｍｅｒｌｙ法（非特許文献３）等が用いられている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Least squares quantization in PCM, IEEE Transaction on Information Theory, 1982
【非特許文献２】Using the Triangle Inequality to Accelerate k-Means, ICML 2003, 2003
【非特許文献３】Making k-means even faster, SDM 2010, 2010
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、所属するクラスタ中心の探索処理における距離計算のコストは、データ数Ｎ、クラスタ数Ｃ、及びデータ次元数Ｄに比例する。
【０００８】
そのため、データ数、クラスタ数、及びデータ次元数が多ければ多いほど、結果の出力までに多大な計算量、すなわち、計算時間を要するという問題がある。
【０００９】
本発明では、上記問題点を解決するために成されたものであり、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができるクラスタリング装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、第１の発明のクラスタリング装置は、複数のデータ点を複数のクラスタにクラスタリングするクラスタリング装置であって、前記複数のデータ点の各々について、前記データ点の位置と前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する所属クラスタ中心探索部と、前記複数のクラスタの各々について、前記所属クラスタ中心探索部により前記クラスタに所属すると決定されたデータ点の位置に基づいて、前記クラスタの中心位置を更新し、更新前と更新後の前記クラスタの中心位置の移動距離を計算し、前記複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、前記データ点についての前記所属クラスタ中心探索部により所属するクラスタを決定する処理を行う頻度を決定するクラスタ中心更新部と、予め定められた収束条件を満たすまで、前記所属クラスタ中心探索部による決定と、前記クラスタ中心更新部による決定とを繰り返す収束判定部と、を含んで構成されており、前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記クラスタ中心更新部によって前記データ点について決定された前記頻度に基づいて、所属するクラスタを決定するか否かを判定し、所属するクラスタを決定すると判定された前記データ点の各々について、前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する。
【００１１】
第２の発明のクラスタリング方法は、所属クラスタ中心探索部と、クラスタ中心更新部と、収束判定部と、を含む、複数のデータ点を複数のクラスタにクラスタリングするクラスタリング装置における、クラスタリング方法であって、前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記データ点の位置と前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定し、前記クラスタ中心更新部は、前記複数のクラスタの各々について、前記所属クラスタ中心探索部により前記クラスタに所属すると決定されたデータ点の位置に基づいて、前記クラスタの中心位置を更新し、更新前と更新後の前記クラスタの中心位置の移動距離を計算し、前記複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とに基づいて、前記データ点についての前記所属クラスタ中心探索部により所属するクラスタを決定する処理を行う頻度を決定し、前記収束判定部は、予め定められた収束条件を満たすまで、前記所属クラスタ中心探索部による決定と、前記クラスタ中心更新部による決定とを繰り返す、ことを含み、前記所属クラスタ中心探索部は、前記複数のデータ点の各々について、前記クラスタ中心更新部によって前記データ点について決定された前記頻度に基づいて、所属するクラスタを決定するか否かを判定し、所属するクラスタを決定すると判定された前記データ点の各々について、前記複数のクラスタの各々の中心位置との距離を計算し、前記計算された距離の各々に基づいて、前記データ点の所属するクラスタを決定する。
【００１２】
第１及び第２の発明によれば、所属クラスタ中心探索部により、複数のデータ点の各々について、データ点の位置と複数のクラスタの各々の中心位置との距離を計算し、計算された距離の各々に基づいて、データ点の所属するクラスタを決定し、クラスタ中心更新部は、複数のクラスタの各々について、所属クラスタ中心探索部によりクラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、データ点についての所属クラスタ中心探索部により所属するクラスタを決定する処理を行う頻度を決定し、収束判定部は、予め定められた収束条件を満たすまで、所属クラスタ中心探索部による決定と、クラスタ中心更新部による決定とを繰り返す。
【００１３】
このように、複数のデータ点の各々について、データ点の所属するクラスタを決定し、複数のクラスタの各々について、クラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、計算されたデータ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、データ点についての所属するクラスタを決定する処理を行う頻度を決定し、予め定められた収束条件を満たすまで、所属するクラスタの決定と、データ点についての所属するクラスタを決定する処理を行う頻度の決定とを繰り返すことにより、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができる。
【００１４】
また、第１の発明において、前記クラスタ中心更新部は、データ点ｘｉの係数をｋiとし、前記データ点ｘｉの前記決定する処理を行う頻度を
【００１５】
【数１】
0006334454.tif 000002
【００１６】
とし、前記データ点ｘｉの所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値を分母とし、予め定められた値を分子とした比率が
【００１７】
【数２】
0006334454.tif 000003
【００１８】
以上、かつ前記所属クラスタ中心探索部の処理回数ｔの値が
【００１９】
【数３】
0006334454.tif 000004
【００２０】
に対して余剰を持たない場合には、前記ｋiをｋi＋１と更新し、前記比率が
【００２１】
【数４】
0006334454.tif 000005
【００２２】
以上であって、かつ、
【００２３】
【数５】
0006334454.tif 000006
【００２４】
未満の場合には、前記ｋiをｋi−γと更新し、前記比率が、
【００２５】
【数６】
0006334454.tif 000007
【００２６】
以上であって、かつ、
【００２７】
【数７】
0006334454.tif 000008
【００２８】
未満の場合には、前記ｋiを更新しないことにより、前記データ点ｘｉについての前記頻度を決定してもよい。
【００２９】
また、第１の発明において、前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、前記データ点が所属するクラスタの中心位置と、前記所属するクラスタの中心位置と最も近い中心位置を有するクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の上限値の２倍以上である場合、前記データ点と前記複数のクラスタの各々の中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定してもよい。
【００３０】
また、第１の発明において、前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、前記データ点が所属するクラスタの中心位置と、前記データ点が属さないクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の上限値の２倍以上である場合、又は、前記距離の上限値が、前記データ点と、前記属さないクラスタの中心位置との距離の下限値以下の場合、前記データ点と、前記属さないクラスタの中心位置との距離、及び前記データ点と前記データ点が属するクラスタの中心位置との距離を計算せず、前記データ点が所属するクラスタの中心位置と、前記データ点が属さないクラスタの中心位置との距離が、前記データ点と前記所属するクラスタの中心位置との距離の２倍以上である場合、又は、前記データ点と前記所属するクラスタの中心位置との距離が、前記距離の下限値以下である場合、前記データ点と、前記属さないクラスタの中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定してもよい。
【００３１】
また、第１の発明において、前記クラスタ中心更新部は、所属するクラスタを決定すると判定された前記データ点の各々について、前記データ点と、前記データ点に２番目に近いクラスタの中心位置との距離の下限値が、前記データ点と前記所属するクラスタの中心位置との距離の上限値以上である場合、又は、前記データ点が所属するクラスタの中心位置と、前記所属するクラスタの中心位置と最も近い中心位置を有するクラスタの中心位置との距離が、前記データ点と、前記データ点が所属するクラスタの中心位置との距離の２倍以上である場合、又は前記データ点と、前記データ点が所属するクラスタの中心位置との距離が、前記距離の下限値以下である場合、前記データ点と前記複数のクラスタの各々の中心位置との距離を計算せずに、前記データ点の所属するクラスタを決定してもよい。
【００３２】
また、本発明のプログラムは、コンピュータを、上記のクラスタリング装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００３３】
以上説明したように、本発明のクラスタリング装置、方法、及びプログラムによれば、複数のデータ点の各々について、データ点の所属するクラスタを決定し、複数のクラスタの各々について、クラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、前記計算された前記データ点の所属するクラスタの中心位置の移動距離と前記所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、データ点についての所属するクラスタを決定する処理を行う頻度を決定し、予め定められた収束条件を満たすまで、所属するクラスタの決定と、データ点についての所属するクラスタを決定する処理を行う頻度の決定とを繰り返すことにより、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができる。
【図面の簡単な説明】
【００３４】
【図１】各クラスタ中心の移動距離にはばらつきが生じる一例を示す図である。
【図２】更新頻度におけるクラスタの更新処理と周期との関係の一例を示す図である。
【図３】第１の実施形態に係るクラスタリング装置の機能的構成を示す図である。
【図４】第１の実施形態に係るクラスタリング装置におけるクラスタリング処理のフローチャート図である。
【図５】第１の実施形態に係るクラスタリング装置における初期化処理のフローチャート図である。
【図６】第１の実施形態に係るクラスタリング装置における所属クラスタ中心探索処理のフローチャート図である。
【図７】第１の実施形態に係るクラスタリング装置におけるクラスタ中心更新処理のフローチャート図である。
【図８】第１の実施形態に係るクラスタリング装置におけるクラスタ中心更新処理のフローチャート図である。
【図９】省略された回数の一例を示す図である。
【図１０】Ｅｌｋａｎ法により計算を省略する一例を示す図である。
【図１１】Ｅｌｋａｎ法により計算を省略する一例を示す図である。
【図１２】Ｅｌｋａｎ法により計算を省略する一例を示す図である。
【図１３】Ｅｌｋａｎ法により計算を省略する一例を示す図である。
【図１４】Ｅｌｋａｎ法により計算を省略する一例を示す図である。
【図１５】第２の実施形態に係るクラスタリング装置の機能的構成を示すブロック図である。
【図１６】第２の実施形態に係るクラスタリング装置におけるクラスタリング処理のフローチャート図である。
【図１７】第２の実施形態に係るクラスタリング装置における初期化処理のフローチャート図である。
【図１８】第２の実施形態に係るクラスタリング装置における所属クラスタ中心探索処理のフローチャート図である。
【図１９】第２の実施形態に係るクラスタリング装置におけるクラスタ中心更新処理のフローチャート図である。
【図２０】第２の実施形態に係るクラスタリング装置におけるクラスタ中心更新処理のフローチャート図である。
【図２１】Ｈａｍｅｒｌｙ法により計算を省略する一例を示す図である。
【図２２】Ｈａｍｅｒｌｙ法により計算を省略する一例を示す図である。
【図２３】Ｈａｍｅｒｌｙ法により計算を省略する一例を示す図である。
【図２４】第３の実施形態に係るクラスタリング装置の機能的構成を示す図である。
【図２５Ａ】第３の実施形態に係るクラスタリング装置におけるクラスタリング処理のフローチャート図である。
【図２５Ｂ】第３の実施形態に係るクラスタリング装置における初期化処理のフローチャート図である。
【図２６】第３の実施形態に係るクラスタリング装置における所属クラスタ中心探索処理のフローチャート図である。
【図２７】第３の実施形態に係るクラスタリング装置におけるクラスタ中心更新処理のフローチャート図である。
【図２８】クラスタリングの一例を示す図である。
【図２９】クラスタにデータ点を所属させる一例を示す図である。
【発明を実施するための形態】
【００３５】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００３６】
＜本実施形態の概要＞
データ点が所属するクラスタ中心を探索する処理において、距離計算のコストを削減する方法は、（１）アルゴリズムが収束するまでの周期数を削減する方法、（２）距離計算１回あたりの計算コストを削減する方法、及び（３）１周期あたりの距離計算の回数を削減するという方法がある。なお、本実施形態においては上記（３）の方法を用いる。
【００３７】
本実施形態においては、図１に示すように、各クラスタ中心の移動距離にはばらつきが生じやすく、直前の移動距離が小さいクラスタ中心に所属するデータ点は、所属クラスタ中心が変わる可能性が相対的に低いことに着目する。そのため、本実施形態においては、データ点が所属するクラスタ中心の移動距離に応じて、所属するクラスタ中心が変わるかどうかの判定頻度を調整し、アルゴリズムの効率化を図っている。
【００３８】
具体的には、データ点ｘｉの各々について設定されている更新頻度（階層的時間刻み）Δｔｉに基づいて、各データ点ｘｉについてクラスタの所属判定を行う。なお、更新頻度Δｔｉは、下記（１）式に示すように、データ点ｘｉの所属するクラスタ中心の１周期前からの移動距離と当該所属するクラスタとは異なるクラスタ中心の１周期前からの移動距離とを重み付けした値fi,t(p)に応じた更新頻度である。クラスタ数はＣであるとする。
【００３９】
【数８】
0006334454.tif 000009
【００４０】
ここで、クラスタ中心Cjの移動距離は、
【００４１】
【数９】
0006334454.tif 000010
で表す。また、fi,t(p)は例えば以下のように設定し、データ点ｘｉの所属するクラスタ中心の１周期前からの移動距離と所属するクラスタに最近傍となる他のクラスタ中心の１周期前からの移動距離とを重み付けした値とする。
【数１０】
0006334454.tif 000011
【００４２】
また、ａｉは、データ点ｘｉが所属するクラスタを表す変数であり、ａｉはＣに含まれる。また、係数ｋｉ（＝０,１,...,ｋｍａｘ）は、下記（２）、（３）、及び（４）式によって更新される。なお、γは整数であり、ηは定数、及びｔは周期を表す。また、ｄ（ｅ，ｆ）はユークリッド空間上の２点ｅ，ｆの距離を表す。
【００４３】
【数１１】
0006334454.tif 000012
【００４４】
上記（２）〜（４）式は、現在のデータ点ｘｉのクラスタの更新処理の頻度を更新する式である。上記（２）式は、関数値fi,t(p,u)を分母とする変数η/ fi,t(p,u)が一定閾値２ki-γ以上２ki-γ+1（γ=１,２,３,…）未満の範囲に含まれる関係を満たす場合には、データ点ｘｉの所属クラスタの更新処理の頻度を上げる処理を行うことを表す。上記（３）式は、変数η/ fi,t(p,u)が一定閾値である２ki+1以上の範囲に含まれ、かつ、周期tに対する２ki+1の剰余が0となる関係を満たす場合には、データ点ｘｉの所属クラスタの更新処理の頻度を下げる処理を行うことを表す。上記（４）式は、上記（２）式、（３）式の条件のいずれも満たさない場合に、現在の所属クラスタの更新処理の頻度を維持する処理を行うことを表す。
図２にΔｔｉが１、２、及び４の値である場合の、クラスタの更新処理を行う頻度と、周期との関係を示す。
【００４５】
以下、第１の実施形態に係るクラスタリング装置について詳細に説明する。なお、第１の実施形態においては、Ｌｌｏｙｄ法に追加の処理を加える。また、Ｌｌｏｙｄ法の１周期当たりの計算の回数は、追加の処理を加えない場合には、データ数Ｎ、及びクラスタ数ＣであるとするとＮＣ回となる（非特許文献１：S.P. Lloyd. Least squares quantization in PCM, IEEE Transaction on Information Theory, 1982.）。なお、Ｌｌｏｙｄ法は、周期毎に全データと全クラスタ中心との距離を計算する手法である。
【００４６】
＜第１の実施形態に係るクラスタリング装置の構成＞
次に、第１の実施形態に係るクラスタリング装置の構成について説明する。図３に示すように、第１の実施形態に係るクラスタリング装置１００は、ＣＰＵと、ＲＡＭと、後述するクラスタ処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このクラスタリング装置は、機能的には図３に示すように入力部１０と、演算部２０と、出力部９０とを含んで構成されている。
【００４７】
クラスタリング装置１００には、ユークリッド空間上のＮ個のデータ次元数Ｄのデータ点の集合Ｘと、集合Ｘを分割するクラスタの数Ｃ（Ｃ＜Ｎ）とが入力として与えられる。クラスタリング装置１００は、入力された集合Ｘに含まれるデータ点ｘｉの各々を、Ｃ個のクラスタに分割し、分割結果を出力する。なお、データ点の各々は、データ点ｘｉ（ｉ＝１〜Ｎ）で表し、クラスタの各々は、クラスタｊ（ｊ＝１〜Ｃ）で表し、クラスタｊの中心位置をクラスタ中心ｃｊとして表す。
【００４８】
入力部１０は、データ点の集合Ｘと、クラスタの数Ｃと、更新頻度係数の上限値ｋｍａｘとを受け付ける。また、入力部１０は、受け付けたデータ点の集合Ｘに含まれるデータ点ｘｉの各々のＤ次元座標位置と、更新頻度係数の上限値ｋｍａｘとをパラメータ記憶部２２に記憶する。
【００４９】
演算部２０は、パラメータ記憶部２２と、初期化部２４と、所属クラスタ中心探索部２６と、クラスタ中心更新部２８と、収束判定部３０と、を含んで構成されている。
【００５０】
パラメータ記憶部２２には、入力部１０において受け付けたデータ点ｘｉの各々のＤ次元座標位置、及び更新頻度係数の上限値ｋｍａｘと、後述する初期化部２４又はクラスタ中心更新部２８により計算されたクラスタ中心ｃｊの各々の位置のＤ次元座標位置と、後述する初期化部２４又はクラスタ中心更新部２８により計算されたデータ点ｘｉの各々の更新頻度Δｔｉ、及び更新頻度係数ｋｉと、後述するクラスタ中心更新部２８により計算されたクラスタ中心ｃｊの各々の移動距離ｐｊ,ｔと、後述する所属クラスタ中心探索部２６において計算された周期ｔにおけるデータ点ｘｉの各々と、クラスタ中心ｃｊとの各々との距離が記憶されている。なお、周期ｔとは、所属クラスタ中心探索部２６による処理、クラスタ中心更新部２８の処理、及び収束判定部３０の処理の繰り返し回数を表し、周期ｔの初期値は１となり、当該処理の繰り返し毎に周期ｔの値に１を加算していくものとする。
【００５１】
初期化部２４は、入力部１０において受け付けたデータ点ｘｉの各々から、ランダムにＣ個を選択し、選択したデータ点ｘｉのＤ次元座標位置を、クラスタｊのクラスタ中心ｃｊのＤ次元座標位置とし、パラメータ記憶部２２に記憶する。また、初期化部２４は、データ点ｘｉの各々についての更新頻度Δｔｉの値を１としてパラメータ記憶部２２に記憶する。また、初期化部２４は、データ点ｘｉの各々についての更新頻度係数ｋｉの値を０としてパラメータ記憶部２２に記憶する。
【００５２】
所属クラスタ中心探索部２６は、入力部１０において受け付けたデータ点の集合Ｘに含まれる複数のデータ点ｘｉの各々について、当該データ点ｘｉについて、パラメータ記憶部２２に記憶されている当該データ点ｘｉの更新頻度Δｔｉと現在の周期ｔとに基づいて、当該データ点ｘｉの所属するクラスタａｉを探索するために、当該データ点ｘｉとクラスタ中心ｃｊの各々との距離を計算する処理を省略できるか否かを判定する。
【００５３】
また、所属クラスタ中心探索部２６は、計算する処理を省略できないと判定されたデータ点ｘｉの各々について、パラメータ記憶部２２に記憶されている当該データ点ｘｉのＤ次元座標位置、及びクラスタ中心ｃｊの各々のＤ次元座標位置との距離に基づいて、当該データ点ｘｉと、クラスタ中心ｃｊとの距離を計算する。そして、データ点ｘｉの各々について、所属するクラスタａｉを決定する。
【００５４】
具体的には、まず、パラメータ記憶部２２に記憶されているデータ点ｘｉの更新頻度Δｔｉと、周期ｔとに基づいて、下記（５）式を満たすか否かを判定する。
【００５５】
【数１２】
0006334454.tif 000013
【００５６】
当該データ点ｘｉの更新頻度Δｔｉが、上記（５）式を満たす場合、当該データ点ｘｉについて、当該データ点ｘｉとクラスタ中心ｃｊの各々との距離を計算する処理を省略できないと判定する。一方、当該データ点ｘｉの更新頻度Δｔｉが、上記（５）式を満たさない場合、当該データ点ｘｉとクラスタ中心ｃｊの各々との距離を計算する処理を省略することができると判定し、当該データ点ｘｉが現在所属するクラスタａｉにそのまま属するとする。
【００５７】
次に、当該データ点ｘｉとクラスタ中心ｃｊの各々との距離を計算する処理を省略できないと判定されたデータ点ｘｉの各々について、パラメータ記憶部２２に記憶されている当該データ点ｘｉのＤ次元座標位置、及びクラスタ中心ｃｊの各々のＤ次元座標位置に基づいて、当該データ点ｘｉと、クラスタ中心ｃｊの各々との距離の各々を計算する。ここで、周期ｔにおけるデータ点ｘｉと、クラスタ中心ｃｊとの距離をｄ（ｘｉ,ｃｊ,ｔ）と表す。
【００５８】
そして、当該データ点ｘｉとクラスタ中心ｃｊの各々との距離を計算する処理を省略できないと判定されたデータ点ｘｉの各々について、計算された距離ｄ（ｘｉ,ｃｊ,ｔ）の各々に基づいて、下記（６）式に従って、当該データ点ｘｉが所属するクラスタａｉを更新する。
【００５９】
【数１３】
0006334454.tif 000014
【００６０】
クラスタ中心更新部２８は、所属クラスタ中心探索部２６において取得したデータ点ｘｉの各々の所属するクラスタａｉと、パラメータ記憶部２２に記憶されているデータ点ｘｉの各々のＤ次元座標位置とに基づいて、クラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置を更新する。また、クラスタ中心更新部２８は、クラスタｊの各々について、周期ｔ−１から周期ｔにおいて、クラスタ中心ｃｊのＤ次元座標位置の移動距離ｐｊ,ｔを計算する。また、クラスタ中心更新部２８は、データ点ｘｉの各々について、所属クラスタ中心探索部２６において取得したデータ点ｘｉの各々の所属するクラスタａｉの各々と、計算したクラスタｊの各々についての移動距離ｐｊ,ｔとに基づいて、更新頻度係数ｋｉを更新し、当該更新した更新頻度係数ｋｉに基づいて、更新頻度Δｔｉを更新する。
【００６１】
具体的には、まず、クラスタｊの各々について、所属クラスタ中心探索部２６において取得したデータ点ｘｉの各々の所属するクラスタａｉに基づいて、当該クラスタｊに所属するデータ点ｘｉの各々を取得する。次に、クラスタｊの各々について、パラメータ記憶部２２に記憶されている、取得した当該クラスタｊに含まれるデータ点ｘｉのＤ次元座標位置に基づいて、下記（７）式に従って、当該クラスタｊの、周期ｔにおけるクラスタ中心ｃｊ,ｔのＤ次元座標位置を更新し、パラメータ記憶部２２に記憶する。
【００６２】
【数１４】
0006334454.tif 000015
【００６３】
次に、クラスタｊの各々について、パラメータ記憶部２２に記憶されている周期ｔ−１のクラスタ中心ｃｊ,ｔ−１のＤ次元座標位置と、計算した周期ｔのクラスタ中心ｃｊ,ｔのＤ次元座標位置とに基づいて、クラスタ中心の移動距離ｐｊ,ｔを計算し、パラメータ記憶部２２に記憶する。
次に、データ点ｘｉの各々について、計算された当該データ点ｘｉの所属するクラスタａｉのクラスタ中心
【００６４】
【数１５】
0006334454.tif 000016
【００６５】
の移動距離と、当該データ点ｘｉの所属するクラスタａｉとは異なるクラスタ中心
【００６６】
【数１６】
0006334454.tif 000017
の移動距離で決まる関数値fi,t(p,u)に基づいて、上記（２）〜（４）式に基づいて、更新頻度係数ｋｉを更新し、パラメータ記憶部２２に記憶する。ここで、計算された更新頻度係数ｋｉの値が、パラメータ記憶部２２に記憶されているｋｍａｘよりも大きい値となる場合には、更新頻度係数ｋｉ＝ｋｍａｘとし、計算された更新頻度係数ｋｉの値が、０より小さくなる場合には、更新頻度係数ｋｉ＝０とする。そして、データ点ｘｉの各々について、計算された当該データ点ｘｉの更新頻度係数ｋｉに基づいて、上記（１）式に従って、当該データ点ｘｉの更新頻度Δｔｉを更新し、パラメータ記憶部２２に記憶する。
【００６７】
収束判定部３０は、予め定められている収束条件を満たすか否かを判定する。第１の実施の形態においては、周期ｔ−１の評価関数Ｆｔ−１と、周期ｔの評価関数Ｆｔとの差の絶対値｜Ｆｔ−Ｆｔ−１｜が予め定められた閾値以下であれば収束条件を満たすと判定する。
【００６８】
また、収束判定部３０は、収束条件を満たすと判定した場合には、周期ｔにおいて、所属クラスタ中心探索部２６で取得した、データ点ｘｉの各々の所属するクラスタａｉの分類結果と、クラスタ中心更新部２８で計算されたクラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置とを出力部９０に出力する。一方、収束判定部３０は、収束条件を満たしていないと判定した場合には、所属クラスタ中心探索部２６の処理と、クラスタ中心更新部２８の処理と、収束判定部３０の処理とを繰り返す。
【００６９】
なお、評価関数Ｆｔは、下記（８）式に従って計算されパラメータ記憶部２２に記憶される。
【００７０】
【数１７】
0006334454.tif 000018
【００７１】
ここで、データ点ｘｉについて、周期ｔにおける
【００７２】
【数１８】
0006334454.tif 000019
【００７３】
が、パラメータ記憶部２２に存在しない場合には、パラメータ記憶部２２に記憶されている、当該データ点ｘｉについてのｔの値が最も大きい
【００７４】
【数１９】
0006334454.tif 000020
【００７５】
を用いることとする。
【００７６】
＜第１の実施形態に係るクラスタリング装置の作用＞
次に、第１の実施形態に係るクラスタリング装置１００の作用について説明する。まず、入力部１０において、データ点の集合Ｘと、更新頻度係数の上限値ｋｍａｘとを受け付け当該データ点の集合Ｘに含まれるデータ点ｘｉの各々のＤ次元座標位置と、更新頻度係数の上限値ｋｍａｘとをパラメータ記憶部２２に記憶する。そして、入力部１０においてクラスタ数Ｃを受け付けると、クラスタリング装置１００によって図４〜図８に示すクラスタリング処理ルーチンを実行する。
【００７７】
まず、図４のステップＳ１００で、初期化部２４は、各種パラメータの初期値を設定する。
【００７８】
次に、ステップＳ１０２で、所属クラスタ中心探索部２６は、入力部１０において受け付けたデータ点ｘｉの各々について、当該データ点ｘｉの所属するクラスタａｉを探索する。
【００７９】
次に、ステップＳ１０４で、クラスタ中心更新部２８は、クラスタｊの各々について、当該クラスタｊのクラスタ中心ｃｊ,ｔを更新する。また、ステップＳ１０４で、クラスタ中心更新部２８は、データ点ｘｉの各々について、当該データ点ｘｉの更新頻度係数ｋｉを更新し、更新された更新頻度係数ｋｉに基づいて、当該データ点ｘｉの更新頻度Δｔｉを更新する。
【００８０】
次に、ステップＳ１０６で、収束判定部３０は、パラメータ記憶部２２に記憶されているデータ点ｘｉの各々についての
【００８１】
【数２０】
0006334454.tif 000021
【００８２】
に基づいて、収束条件を満たすか否かを判定する。収束判定部３０が、収束条件を満たすと判定した場合には、クラスタリング処理は、ステップＳ１０８へ移行する。一方、収束判定部３０が、収束条件を満たさないと判定した場合には、クラスタリング処理は、ステップＳ１０２へ移行し、ステップＳ１０２〜ステップＳ１０６までの処理を繰り返す。
【００８３】
次に、ステップＳ１０８で、収束判定部３０は、ステップＳ１０２において取得したデータ点ｘｉの各々の所属するクラスタａｉの分類結果と、ステップＳ１０４において取得したクラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置とを出力部９０に出力してクラスタリング処理を終了する。
【００８４】
上記ステップＳ１００の初期化処理について、図５について詳細に説明する。
【００８５】
図５のステップＳ２００で、初期化部２４は、パラメータ記憶部２２に記憶されているデータ点ｘｉの各々のＤ次元座標位置、及び更新頻度係数の上限値ｋｍａｘを読み込む。
【００８６】
次に、ステップＳ２０２で、初期化部２４は、周期ｔの値を０と設定する。
【００８７】
次に、ステップＳ２０４で、初期化部２４は、入力部１０において受け付けたＮ個のデータ点ｘｉから、Ｃ個のデータ点ｘｉを選択し、ステップＳ２００において取得した、選択されたデータ点の各々のＤ次元座標位置をクラスタｊの各々のクラスタ中心ｃｊ,ｔのＤ次元座標位置として決定し、パラメータ記憶部２２に記憶する。
【００８８】
次に、ステップＳ２０６で、初期化部２４は、ｉの値を１と設定する。
【００８９】
次に、ステップＳ２０８で、初期化部２４は、データ点ｘｉの更新頻度Δｔｉを１と設定し、パラメータ記憶部２２に記憶する。
【００９０】
次に、ステップＳ２１０で、初期化部２４は、データ点ｘｉの更新頻度係数ｋｉを０と設定し、パラメータ記憶部２２に記憶する。
【００９１】
次に、ステップＳ２１２で、初期化部２４は、ｉの値がＮであるか否かを判定する。初期化部２４が、ｉの値がＮ未満であると判定した場合には、初期化処理は、ステップＳ２１４へ移行する。一方、初期化部２４が、ｉの値がＮであると判定した場合には、初期化処理を終了する。
【００９２】
次に、ステップＳ２１４で、初期化部２４は、ｉの値をｉ＋１と設定し、ステップＳ２０８へ移行する。
【００９３】
上記ステップＳ１０２の所属クラスタ中心探索処理について、図６について詳細に説明する。
【００９４】
図６のステップＳ３００で、所属クラスタ中心探索部２６は、ｉの値を１に設定する。
【００９５】
次に、ステップＳ３０２で、所属クラスタ中心探索部２６は、ｔの値をｔ＋１と設定する。
【００９６】
次に、ステップＳ３０４で、所属クラスタ中心探索部２６は、ｊの値を１に設定する。
【００９７】
次に、ステップＳ３０６で、所属クラスタ中心探索部２６は、ｉの値がＮより大きいか否かを判定する。所属クラスタ中心探索部２６が、ｉの値がＮ以下であると判定した場合には、所属クラスタ中心探索処理は、ステップＳ３０８へ移行する。一方、所属クラスタ中心探索部２６が、ｉの値がＮよりも大きいと判定した場合には、所属クラスタ中心探索処理は終了する。
【００９８】
次に、ステップＳ３０８で、所属クラスタ中心探索部２６は、ステップＳ３０２において取得したｔの値と、ステップＳ２０８、又は前回のクラスタリング処理におけるステップＳ５０９において取得したデータ点ｘｉの更新頻度Δｔｉとに基づいて、上記（５）式を満たすか否かを判定する。所属クラスタ中心探索部２６が、上記（５）式を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１０へ移行する。一方、所属クラスタ中心探索部２６が、上記（５）式を満たさないと判定した場合には、データ点ｘｉが現在所属するクラスタａｉにそのまま属するとして、ステップＳ３１８へ移行する。
【００９９】
次に、ステップＳ３１０で、所属クラスタ中心探索部２６は、ｊの値がＣ以下であるか否かを判定する。所属クラスタ中心探索部２６が、ｊの値がＣ以下であると判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１２へ移行する。一方、所属クラスタ中心探索部２６が、ｊの値がＣよりも大きいと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１６へ移行する。
【０１００】
次に、ステップＳ３１２で、所属クラスタ中心探索部２６は、ステップＳ２００において取得したデータ点ｘｉのＤ次元座標位置と、ステップＳ２０２、又は前回のクラスタリング処理のステップＳ４０４において取得したクラスタｊのクラスタ中心ｃｊのＤ次元座標位置とに基づいて、距離ｄ（ｘｉ,ｃｊ,ｔ）を計算する。
【０１０１】
次に、ステップＳ３１４で、所属クラスタ中心探索部２６は、ｊの値をｊ＋１に設定し、所属クラスタ中心探索処理は、ステップＳ３１０へ移行する。
【０１０２】
ステップＳ３１６で、所属クラスタ中心探索部２６は、ステップＳ３１２において取得した、データ点ｘｉと、クラスタ中心ｃｊ,ｔの各々との距離ｄ（ｘｉ,ｃｊ,ｔ）とに基づいて、上記（６）式に従って、当該データ点ｘｉの所属するクラスタａｉを更新する。
【０１０３】
次に、ステップＳ３１８で、所属クラスタ中心探索部２６は、ｉの値をｉ＋１に設定し、ステップＳ３０４へ移行する。
【０１０４】
上記ステップＳ１０４のクラスタ中心更新処理について、図７、及び図８について詳細に説明する。
【０１０５】
図７のステップＳ４００で、クラスタ中心更新部２８は、ｊの値を１に設定する。
【０１０６】
次に、ステップＳ４０２で、クラスタ中心更新部２８は、パラメータ記憶部２２に記憶されている周期ｔ−１におけるクラスタ中心ｃｊ,ｔ−１のＤ次元座標位置を読み込む。
【０１０７】
次に、ステップＳ４０４で、クラスタ中心更新部２８は、ステップＳ２００において取得した、ステップＳ３０８、及びステップＳ３１６において取得したクラスタｊに所属するデータ点ｘｉの各々のＤ次元座標位置に基づいて、上記（７）式に従って、クラスタ中心ｃｊ,ｔのＤ次元座標位置を計算し、パラメータ記憶部２２に記憶する。
【０１０８】
次に、ステップＳ４０６で、クラスタ中心更新部２８は、ステップＳ４０２において取得したクラスタ中心ｃｊ,ｔ−１のＤ次元座標位置と、ステップＳ４０４において取得したクラスタ中心ｃｊ,ｔのＤ次元座標位置とに基づいて、周期ｔ−１から周期ｔまでにおけるクラスタ中心ｃｊの移動距離ｐｊ,ｔを計算する。
【０１０９】
次に、ステップＳ４０８で、クラスタ中心更新部２８は、ｊの値がＣの値よりも小さいか否かを判定する。クラスタ中心更新部２８が、ｊの値がＣの値よりも小さいと判定した場合には、ステップＳ４１０へ移行する。一方、クラスタ中心更新部２８が、ｊの値がＣの値以上であると判定した場合には、ステップＳ４１２へ移行する。
【０１１０】
ステップＳ４１０で、クラスタ中心更新部２８は、ｊの値をｊ＋１としてステップＳ４０２へ移行する。
【０１１１】
次に、ステップＳ４１２で、クラスタ中心更新部２８は、ｉの値を１に設定する。
【０１１２】
次に、ステップＳ４１４で、クラスタ中心更新部２８は、ステップＳ４０６において取得した各クラスタの移動距離によって算出された関数値fi,t(p,u)が上記（３）式の条件を満たすか否かを判定する。クラスタ中心更新部２８が、上記（３）式の条件を満たすと判定した場合には、クラスタ中心更新処理は、ステップＳ４１６へ移行する。一方、クラスタ中心更新部２８が、上記（３）式の条件を満たしていないと判定した場合には、クラスタ中心更新処理は、ステップＳ４１９へ移行する。
【０１１３】
次に、ステップＳ４１６で、クラスタ中心更新部２８は、データ点ｘｉの更新頻度係数ｋｉをｋｉ＋１に更新する。
【０１１４】
次に、ステップＳ４１７で、クラスタ中心更新部２８は、ステップＳ４１６において取得したデータ点ｘｉの更新頻度係数ｋｉがステップＳ２００において取得したｋｍａｘの値より大きいか否かを判定する。クラスタ中心更新部２８が、データ点ｘｉの更新頻度係数ｋｉがステップＳ２００において取得したｋｍａｘの値以下と判定した場合には、クラスタ中心更新処理は、ｋｉをパラメータ記憶部２２に記憶し、図８のステップＳ５０９へ移行する。一方、クラスタ中心更新部２８が、データ点ｘｉの更新頻度係数ｋｉがステップＳ２００において取得したｋｍａｘの値より大きい場合には、クラスタ中心更新処理は、ステップＳ４１８へ移行する。
【０１１５】
次に、ステップＳ４１８で、クラスタ中心更新部２８は、ステップＳ４１６において取得したデータ点ｘｉの更新頻度係数ｋｉの値をステップＳ２００において取得したｋｍａｘの値とし、パラメータ記憶部２２に記憶する。
【０１１６】
ステップＳ４１９で、ステップＳ４０６において取得した各クラスタの移動距離によって算出された関数値fi,t(p,u)が上記（４）式の条件を満たすか否かを判定する。クラスタ中心更新部２８が、上記（４）式の条件を満たすと判定した場合には、クラスタ中心更新処理は、ステップＳ４２０へ移行する。一方、クラスタ中心更新部２８が、上記（４）式の条件を満たしていないと判定した場合には、クラスタ中心更新処理は、図８のステップＳ５００へ移行する。
【０１１７】
次に、ステップＳ４２０で、クラスタ中心更新部２８は、データ点ｘｉの更新頻度係数ｋｉをｋｉとし、パラメータ記憶部２２に記憶し、クラスタ中心更新処理は、図８のステップＳ５０９へ移行する。
【０１１８】
図８のステップＳ５００で、クラスタ中心更新部２８は、γの値を１に設定する。
【０１１９】
次に、ステップＳ５０２で、クラスタ中心更新部２８は、ステップＳ４０６において取得した各クラスタの移動距離によって算出された関数値fi,t(p,u)が上記（２）式の条件を満たすか否かを判定する。クラスタ中心更新部２８が、上記（２）の条件を満たすと判定した場合には、クラスタ中心更新処理は、ステップＳ５０６へ移行する。一方、クラスタ中心更新部２８が、上記（２）式の条件を満たしていないと判定した場合には、クラスタ中心更新処理は、ステップＳ５０４へ移行する。
【０１２０】
次に、ステップＳ５０４で、クラスタ中心更新部２８は、γの値をγ＋１に設定する。
【０１２１】
次に、ステップＳ５０６で、クラスタ中心更新部２８は、データ点ｘｉの更新頻度係数ｋｉをｋｉ−γとする。
【０１２２】
次に、ステップＳ５０７で、クラスタ中心更新部２８は、ステップＳ５０６において取得したデータ点ｘｉの更新頻度係数ｋｉが０の値より小さいか否かを判定する。クラスタ中心更新部２８が、データ点ｘｉの更新頻度係数ｋｉが０の値より小さいと判定した場合には、クラスタ中心更新処理は、ステップＳ５０８へ移行する。一方、クラスタ中心更新部２８が、データ点ｘｉの更新頻度係数ｋｉが０の値以上である場合には、クラスタ中心更新処理は、ｋｉをパラメータ記憶部２２に記憶し、ステップＳ５０９へ移行する。
【０１２３】
ステップＳ５０８で、クラスタ中心更新部２８は、ステップＳ５０６において取得した、データ点ｘｉの更新頻度係数ｋｉを０とし、パラメータ記憶部２２に記憶する。
【０１２４】
次に、ステップＳ５０９で、クラスタ中心更新部２８は、ステップＳ４１６、ステップＳ４１８、ステップＳ４２０、ステップＳ５０６、又はステップＳ５０８において取得したデータ点ｘｉの更新頻度係数ｋｉに基づいて、上記（１）式にしたがって、データ点ｘｉの更新頻度Δｔｉを更新し、パラメータ記憶部２２に記憶する。
【０１２５】
次に、ステップＳ５１０で、クラスタ中心更新部２８は、ｉの値がＮより小さいか否かを判定する。クラスタ中心更新部２８が、ｉの値がＮより小さいと判定した場合には、クラスタ中心更新処理は、ステップＳ５１２へ移行する。一方、クラスタ中心更新部２８が、ｉの値がＮより小さいと判定した場合には、クラスタ中心更新処理は終了する。
【０１２６】
ステップＳ５１２で、クラスタ中心更新部２８は、ｉの値をｉ＋１に設定し、図７のステップＳ４１４へ移行する。
【０１２７】
以上説明したように、第１の実施形態に係るクラスタリング装置によれば、複数のデータ点の各々について、データ点の所属するクラスタを決定し、複数のクラスタの各々について、クラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、計算されたデータ点の所属するクラスタの中心位置の移動距離と当該所属するクラスタとは異なるクラスタの中心の位置の移動距離とを重み付けした値に基づいて、データ点についての所属するクラスタを決定する処理を行う頻度を決定し、予め定められた収束条件を満たすまで、所属するクラスタの決定と、データ点についての所属するクラスタを決定する処理を行う頻度の決定とを繰り返すことにより、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができる。
【０１２８】
また、従来のＬｌｏｙｄ法の１周期当たりの計算回数はＮＣ回であり、データ点の所属するクラスタの中心位置の移動距離のみに基づいて頻度を決定する場合の１周期当たりの計算回数はＮＩＣＥＤ回であるのに対し、第１の実施形態に係るクラスタリング装置１００を用いることで、１周期当たりの計算回数をＮＩＡＣにすることができる。ただし、ＮＩA＜ＮＩ＜Ｎである。
図９に従来の方法から省略された回数の例を示す。
【０１２９】
また、アルゴリズムの実行時間の短縮、及び計算の高速化を実現することができる。
【０１３０】
また、所属するクラスタの中心位置の移動距離と当該所属するクラスタとは異なるクラスタの中心の位置の移動距離とを重み付けした値に基づいて、距離計算の対象とするかどうかの制約を加えることで、距離計算を行うデータ点の数を減らし、全体の距離計算の回数削減を実現している。
【０１３１】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１３２】
例えば、第１の実施形態においては、収束条件を評価関数に基づいて満たしているか否かを判定する場合について説明したが、これに限定されるものではなく、周期数等、他の収束条件を用いてもよい。
【０１３３】
次に、第２の実施形態に係るクラスタリング装置について説明する。
【０１３４】
第２の実施形態においては、三角不等式を利用したｋ−ｍｅａｎｓ高速化手法であるＥｌｋａｎ法に追加の処理を加える点が第１の実施形態と異なる。なお、第１の実施形態に係るクラスタリング装置と同様の構成及び作用については、同一の符号を付して説明を省略する。
【０１３５】
＜第２の実施形態の概要＞
まず、Ｅｌｋａｎ法による計算の省略について説明する。
【０１３６】
第１の計算の省略については、図１０に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１３７】
【数２１】
0006334454.tif 000022
【０１３８】
、及び所属クラスタ中心
【０１３９】
【数２２】
0006334454.tif 000023
【０１４０】
から最近傍のクラスタ中心ｃｊが存在する場合、下記（９）式を満たすならば、所属クラスタａｉのクラスタ中心
【０１４１】
【数２３】
0006334454.tif 000024
【０１４２】
が、データ点ｘｉに最も近いといえる。そのため、当該データ点ｘｉと全てのクラスタ中心間との距離計算を省略することができる。なお、下記（１０）式に示すｕ（ｉ）は、更新前の所属クラスタ中心
【０１４３】
【数２４】
0006334454.tif 000025
【０１４４】
とデータ点ｘｉとの距離に、更新後の所属クラスタ中心
【０１４５】
【数２５】
0006334454.tif 000026
【０１４６】
の移動距離を足したものであり、データ点ｘｉと所属クラスタ中心間の距離の上限値を表す。
【０１４７】
【数２６】
0006334454.tif 000027
0006334454.tif 000028
【０１４８】
第２の計算の省略については、図１１に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１４９】
【数２７】
0006334454.tif 000029
【０１５０】
、及び所属クラスタ以外の他のクラスタ中心ｃｊが存在する場合、下記（１１）式を満たすならば、所属クラスタａｉのクラスタ中心
【０１５１】
【数２８】
0006334454.tif 000030
【０１５２】
が、他のクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。そのため、当該データ点ｘｉと他のクラスタ中心間との距離計算を省略することができる。
【０１５３】
【数２９】
0006334454.tif 000031
【０１５４】
第３の計算の省略については、図１２に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１５５】
【数３０】
0006334454.tif 000032
【０１５６】
、及び所属クラスタ以外の他のクラスタ中心ｃｊが存在する場合、下記（１２）式を満たすならば、所属クラスタａｉのクラスタ中心
【０１５７】
【数３１】
0006334454.tif 000033
【０１５８】
が、他のクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。そのため、当該データ点ｘｉと他のクラスタ中心間との距離計算を省略することができる。なお、下記（１３）式に示すｌ（ｉ,ｊ）は、更新前の他のクラスタ中心ｃｊとデータ点ｘｉとの距離に、更新後の他のクラスタ中心の移動距離を引いたものであり、データ点ｘｉと所属クラスタ中心間の距離の下限値を表す。
【０１５９】
【数３２】
0006334454.tif 000034
0006334454.tif 000035
【０１６０】
第４の計算の省略については、図１３に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１６１】
【数３３】
0006334454.tif 000036
【０１６２】
、及び所属クラスタ以外の他のクラスタ中心ｃｊが存在する場合、下記（１４）式を満たすならば、所属クラスタａｉのクラスタ中心
【０１６３】
【数３４】
0006334454.tif 000037
【０１６４】
が、他のクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。そのため、当該データ点ｘｉと他のクラスタ中心間との距離計算を省略することができる。
【０１６５】
【数３５】
0006334454.tif 000038
【０１６６】
第５の計算の省略については、図１４に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１６７】
【数３６】
0006334454.tif 000039
【０１６８】
、及び所属クラスタ以外の他のクラスタ中心ｃｊが存在する場合、下記（１５）式を満たすならば、所属クラスタａｉのクラスタ中心
【０１６９】
【数３７】
0006334454.tif 000040
【０１７０】
が、他のクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。そのため、当該データ点ｘｉと他のクラスタ中心間との距離計算を省略することができる。
【０１７１】
【数３８】
0006334454.tif 000041
【０１７２】
＜第２の実施形態に係るクラスタリング装置の構成＞
次に、第２の実施形態に係るクラスタリング装置の構成について説明する。図１５に示すように、第２の実施形態に係るクラスタリング装置２００は、ＣＰＵと、ＲＡＭと、後述するクラスタリング処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このクラスタリング装置は、機能的には図１５に示すように入力部１０と、演算部２２０と、出力部９０とを含んで構成されている。
【０１７３】
演算部２２０は、パラメータ記憶部２２２と、初期化部２２４と、所属クラスタ中心探索部２２６と、クラスタ中心更新部２２８と、収束判定部３０とを含んで構成されている。
【０１７４】
パラメータ記憶部２２２には、入力部１０において受け付けたデータ点ｘｉの各々のＤ次元座標位置、及び更新頻度係数の上限値ｋｍａｘと、後述する初期化部２２４又はクラスタ中心更新部２２８により計算されたクラスタ中心ｃｊの各々の位置のＤ次元座標位置、全てのクラスタの組み合わせのクラスタ中心ｃｊ間の各々の距離、及び全てのクラスタｊの各々についての最近傍のクラスタとのクラスタ中心ｃｊ間の距離ｓ（ｊ）と、後述する初期化部２２４又はクラスタ中心更新部２２８により計算されたデータ点ｘｉの各々の更新頻度Δｔｉ、更新頻度係数ｋｉ、所属するクラスタａｉのクラスタ中心と当該データ点ｘｉとの距離の上限値ｕ（ｉ）、及びクラスタｊの各々のクラスタ中心と当該データ点ｘｉとの距離の下限値ｌ（ｉ,ｊ）の各々と、後述するクラスタ中心更新部２２８により計算されたクラスタ中心ｃｊの各々の周期ｔ−１から周期ｔまでの移動距離ｐｊ,ｔと、後述する所属クラスタ中心探索部２２６において計算された周期ｔにおけるデータ点ｘｉの各々と、クラスタ中心ｃｊとの各々との距離が記憶されている。
【０１７５】
初期化部２２４は、入力部１０において受け付けたデータ点ｘｉの各々から、ランダムにＣ個を選択し、選択したデータ点ｘｉのＤ次元座標位置を、クラスタｊのクラスタ中心ｃｊのＤ次元座標位置とし、パラメータ記憶部２２２に記憶する。また、初期化部２２４は、データ点ｘｉの各々についての更新頻度Δｔｉの値を１としてパラメータ記憶部２２２に記憶する。また、初期化部２２４は、データ点ｘｉの各々についての更新頻度係数ｋｉの値を０としてパラメータ記憶部２２２に記憶する。また、初期化部２２４は、全てのクラスタｊの各々のクラスタ間のクラスタ中心距離ｄ（ｃｊ,ｃｊ´）を計算し（ｊ´≠ｊ）、パラメータ記憶部２２２に記憶する。また、初期化部２２４は、クラスタｊの各々について、計算したクラスタ中心距離ｄ（ｃｊ,ｃｊ´）のうち一番距離が小さいものを当該クラスタｊの最近傍のクラスタ中心との距離ｓ（ｊ）としてパラメータ記憶部２２２に記憶する。また、初期化部２２４は、データ点ｘｉの各々について、所属するクラスタａｉをランダムに設定する。
【０１７６】
次に、初期化部２２４は、パラメータ記憶部２２２に記憶されている入力部１０において受け付けたデータ点ｘｉの各々のＤ次元座標位置、及びクラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置に基づいて、データ点ｘｉの各々について、当該データ点ｘｉとクラスタｊの各々との距離ｄ（ｘｉ,ｃｊ）を計算する。次に、データ点ｘｉの各々について、当該データ点ｘｉが所属するクラスタａｉとの距離ｄ（ｘｉ,ａｉ）を、当該データ点ｘｉと所属クラスタ中心間との距離の上限値ｕ（ｉ）としてパラメータ記憶部２２２に記憶する。次に、データ点ｘｉの各々について、当該データ点ｘｉとクラスタｊのクラスタ中心ｃｊとの距離ｄ（ｘｉ,ｃｊ）を、当該データ点ｘｉとクラスタｊの各々のクラスタ中心ｃｊとの距離の下限値ｌ（ｉ,ｊ）の各々としてパラメータ記憶部２２２に記憶する。
【０１７７】
所属クラスタ中心探索部２２６は、入力部１０において受け付けたデータ点の集合Ｘに含まれる複数のデータ点ｘｉの各々について、当該データ点ｘｉについて、パラメータ記憶部２２２に記憶されている当該データ点ｘｉの更新頻度Δｔｉと現在の周期ｔとに基づいて、上記（５）式の条件を満たすか否かを判定する。また、所属クラスタ中心探索部２２６は、データ点ｘｉの各々について、パラメータ記憶部２２２に記憶されている当該データ点ｘｉの当該データ点ｘｉと所属クラスタ中心
【０１７８】
【数３９】
0006334454.tif 000042
【０１７９】
との距離の上限値ｕ（ｉ）、及び所属クラスタａｉの最近傍のクラスタ中心ｃｊとの距離ｓ（ａｉ）に基づいて、上記（９）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６は、上記（５）式の条件を満たさない、又は上記（９）式の条件を満たすデータ点ｘｉについては、当該データ点ｘｉと全てのクラスタ中心ｃｊとの距離計算を省略することができると判定する。この場合、当該データ点ｘｉは、現在所属するクラスタａｉにそのまま所属する。
【０１８０】
次に、所属クラスタ中心探索部２２６は、上記（５）式の条件を満たす、又は上記（９）式の条件を満たさない処理対象となるデータ点ｘｉの各々について、取得した当該データ点ｘｉの当該データ点ｘｉと所属クラスタ中心
【０１８１】
【数４０】
0006334454.tif 000043
【０１８２】
との距離の上限値ｕ（ｉ）、及びパラメータ記憶部２２２に記憶されている所属クラスタａｉと特定のクラスタｊとの中心位置間の距離
【０１８３】
【数４１】
0006334454.tif 000044
【０１８４】
とに基づいて、上記（１１）式の条件を満たすか否かを判定する。また、所属クラスタ中心探索部２２６は、処理対象となるデータ点ｘｉの各々について、パラメータ記憶部２２２に記憶されている当該データ点ｘｉの当該データ点ｘｉと特定のクラスタ中心との間の距離の下限値ｌ（ｉ,ｊ）と、取得した当該データ点ｘｉの当該データ点ｘｉと所属クラスタ中心
【０１８５】
【数４２】
0006334454.tif 000045
【０１８６】
との距離の上限値ｕ（ｉ）とに基づいて、上記（１２）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６は、上記（１１）式、又は上記（１２）式の条件を満たすデータ点ｘｉとクラスタｊとの組み合わせについては、当該データ点ｘｉと、当該クラスタｊのクラスタ中心ｃｊとの距離計算を省略する。
【０１８７】
次に、所属クラスタ中心探索部２２６は、上記（５）式の条件を満たし、かつ、上記（９）式の条件を満たさないデータ点ｘｉの各々であって、更に、上記（１１）式、及び上記（１２）式の条件を満たさないクラスタｊとの組み合わせの各々について、パラメータ記憶部２２２に記憶されている当該データ点ｘｉのＤ次元座標位置、及び当該データ点ｘｉの所属しているクラスタａｉのクラスタ中心
【０１８８】
【数４３】
0006334454.tif 000046
【０１８９】
のＤ次元座標位置に基づいて、データ点と所属クラスタ中心
【０１９０】
【数４４】
0006334454.tif 000047
【０１９１】
との距離を計算する。ここで、計算した距離を当該データ点ｘｉのｕ（ｉ）としてパラメータ記憶部２２２に記憶する。
【０１９２】
次に、所属クラスタ中心探索部２２６は、上記（５）式を満たし、かつ、上記（９）式の条件を満たさないデータ点ｘｉの各々であって、更に、上記（１１）式、及び上記（１２）式の条件を満たさないクラスタｊとの組み合わせの各々について、計算したデータ点ｘｉと所属クラスタ中心
【０１９３】
【数４５】
0006334454.tif 000048
【０１９４】
との距離と、パラメータ記憶部２２２に記憶されているデータ点ｘｉが所属するクラスタａｉのクラスタ中心
【０１９５】
【数４６】
0006334454.tif 000049
【０１９６】
と特定のクラスタ中心ｃｊとの距離とに基づいて、上記（１４）式の条件を満たすか否かを判定する。また、所属クラスタ中心探索部２２６は、上記（５）式の条件を満たし、かつ、及び上記（９）式の条件を満たさないデータ点ｘｉの各々であって、更に、上記（１１）式、及び上記（１２）式の条件を満たさないクラスタｊとの組み合わせの各々について、計算したデータ点ｘｉと所属クラスタ中心
【０１９７】
【数４７】
0006334454.tif 000050
【０１９８】
との距離と、パラメータ記憶部２２２に記憶されている当該データ点ｘｉと特定のクラスタ中心ｃｊとの間の距離の下限値ｌ（ｉ,ｌ）とに基づいて、上記（１５）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６は、上記（１４）式、又は上記（１５）式の条件を満たすデータ点ｘｉとクラスタｊとの組み合わせについては、当該データ点ｘｉとクラスタ中心ｃｊとの間の距離計算を省略する。
【０１９９】
次に、所属クラスタ中心探索部２２６は、上記において計算処理を省略しないと判定されたデータ点ｘｉとクラスタｊとの組み合わせの各々について、パラメータ記憶部２２に記憶されている当該データ点ｘｉのＤ次元座標位置、及びクラスタ中心ｃｊの各々のＤ次元座標位置とに基づいて、当該データ点ｘｉと、クラスタ中心ｃｊの各々との距離を計算する。ここで、計算された距離を、当該データ点ｘｉと特定のクラスタ中心ｃｊとの間の距離の下限値ｌ（ｉ,ｌ）としてパラメータ記憶部２２２に記憶する。
【０２００】
そして、データ点ｘｉの各々のうち、少なくとも１つのクラスタ中心ｃｊとの距離を計算したデータ点ｘｉの各々について、計算された当該データ点ｘｉと、クラスタ中心ｃｊの各々との距離、及び当該データ点ｘｉと、更新前の所属するクラスタ中心
【０２０１】
【数４８】
0006334454.tif 000051
【０２０２】
との距離とに基づいて、上記（６）式に基づいて、当該データ点ｘｉが所属するクラスタａｉを更新する。なお、当該データ点ｘｉと、更新前の所属するクラスタ中心
【０２０３】
【数４９】
0006334454.tif 000052
【０２０４】
との距離は、他のクラスタ中心ｃｊと当該データ点ｘｉとの距離の計算の省略の判定の処理途中において計算した距離を用いる。
【０２０５】
クラスタ中心更新部２２８は、所属クラスタ中心探索部２２６において取得したデータ点ｘｉの各々の所属するクラスタａｉと、パラメータ記憶部２２２に記憶されているデータ点ｘｉの各々のＤ次元座標位置に基づいて、クラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置を更新する。また、クラスタ中心更新部２２８は、クラスタｊの各々について、周期ｔ−１から周期ｔにおいて、クラスタ中心ｃｊのＤ次元座標位置の移動距離を計算する。また、クラスタ中心更新部２２８は、データ点ｘｉの各々について、所属クラスタ中心探索部２２６において取得したデータ点ｘｉの各々の所属するクラスタａｉと、計算したクラスタｊの各々についての移動距離とに基づいて、更新頻度係数ｋｉを更新し、当該更新した更新頻度係数ｋｉに基づいて、更新頻度Δｔｉを更新する。
【０２０６】
また、クラスタ中心更新部２２８は、更新後の全てのクラスタ中心ｃｊ間の距離を計算し、パラメータ記憶部２２２に記憶する。また、クラスタ中心更新部２２８は、クラスタｊの各々について、計算された全てのクラスタ中心ｃｊ間の距離のうち一番小さい距離を当該クラスタｊのｓ（ｊ）としてパラメータ記憶部２２２に記憶する。また、クラスタ中心更新部２２８は、データ点ｘｉの各々について、当該データ点ｘｉのｕ（ｉ）、及びクラスタ中心ｃｊの各々とのｌ（ｉ,ｊ）を更新する。
【０２０７】
具体的には、まず、データ点ｘｉの各々について、周期ｔ−１と周期ｔとにおいて所属するクラスタａｉが変更されたか否かを判定する。ここで、所属するクラスタａｉが変更されている場合には、当該データ点ｘｉのｕ（ｉ）を、所属クラスタ中心探索部２２６において計算された当該データ点ｘｉと当該所属クラスタ中心
【０２０８】
【数５０】
0006334454.tif 000053
【０２０９】
との距離と、計算された所属するクラスタ中心の移動距離
【０２１０】
【数５１】
0006334454.tif 000054
【０２１１】
との和を、当該データ点ｘｉのｕ（ｉ）と設定し、パラメータ記憶部２２２に記憶する。一方、所属するクラスタａｉが変更されていない場合には、パラメータ記憶部２２２に記憶されている当該データ点ｘｉのｕ（ｉ）と、計算された所属するクラスタ中心
【０２１２】
【数５２】
0006334454.tif 000055
【０２１３】
の移動距離
【０２１４】
【数５３】
0006334454.tif 000056
【０２１５】
との和を、当該データ点ｘｉのｕ（ｉ）としてパラメータ記憶部２２２に記憶する。次に、データ点ｘｉのクラスタ中心ｃｊの各々との距離の下限値ｌ（ｉ,ｊ）の各々を、当該下限値ｌ（ｉ,ｊ）から、当該クラスタ中心ｃｊの移動距離ｐｊ,ｔを引いた値を当該下限値ｌ（ｉ,ｌ）としてパラメータ記憶部２２２に記憶する。
【０２１６】
＜第２の実施形態に係るクラスタリング装置の作用＞
次に、第２の実施形態に係るクラスタリング装置２００の作用について説明する。まず、入力部１０において、データ点の集合Ｘと、更新頻度係数の上限値ｋｍａｘとを受け付け当該データ点の集合Ｘに含まれるデータ点ｘｉの各々のＤ次元座標位置と、更新頻度係数の上限値ｋｍａｘとをパラメータ記憶部２２２に記憶する。そして、入力部１０においてクラスタ数Ｃを受け付けると、クラスタリング装置２００によって図１６〜図２０に示すクラスタリング処理ルーチンを実行する。
【０２１７】
まず、図１６のステップＳ６００で、初期化部２２４は、各種パラメータの初期値を設定する。
【０２１８】
次に、ステップＳ６０２で、所属クラスタ中心探索部２２６は、入力部１０において受け付けたデータ点ｘｉの各々について、当該データ点ｘｉの所属するクラスタａｉを探索する。
【０２１９】
次に、ステップＳ６０４で、クラスタ中心更新部２２８は、クラスタｊの各々について、当該クラスタｊのクラスタ中心ｃｊ,ｔを更新する。また、ステップＳ６０４で、クラスタ中心更新部２２８は、データ点ｘｉの各々について、当該データ点ｘｉの更新頻度係数ｋｉを更新し、更新された更新頻度係数ｋｉに基づいて、当該データ点ｘｉの更新頻度Δｔｉを更新する。
【０２２０】
上記ステップＳ６００の初期化処理について、図１７について詳細に説明する。
【０２２１】
図１７のステップＳ２０４で、初期化部２２４は、入力部１０において受け付けたＮ個のデータ点ｘｉから、Ｃ個のデータ点ｘｉを選択し、ステップＳ２００において取得した、選択されたデータ点の各々のＤ次元座標位置をクラスタｊの各々のクラスタ中心ｃｊ,ｔのＤ次元座標位置として決定し、パラメータ記憶部２２に記憶する。また、データ点ｘｉの各々の所属するクラスタａｉ、及び所属クラスタ中心
【０２２２】
【数５４】
0006334454.tif 000057
【０２２３】
を決定し、パラメータ記憶部２２２に記憶する。
【０２２４】
ステップＳ７００で、初期化部２２４は、ステップＳ２０４において取得したクラスタｊの各々のクラスタ中心ｃｊ,ｔのＤ次元座標位置に基づいて、クラスタｊの全てのクラスタ間の組み合わせのクラスタ中心間の距離を計算し、パラメータ記憶部２２２に記憶する。
【０２２５】
次に、ステップＳ７０２で、初期化部２２４は、ステップＳ７００において取得した、クラスタｊの全ての組み合わせのクラスタ中心間の距離に基づいて、クラスタｊの各々について、当該クラスタｊについて最小となる距離をクラスタ中心間の距離ｓ（ｊ）として取得し、パラメータ記憶部２２２に記憶する。
【０２２６】
ステップＳ７０４で、初期化部２２４は、ｊの値を１と設定する。
【０２２７】
次に、ステップＳ７０６で、初期化部２２４は、ｊの値がＣ以下か否かを判定する。初期化部２２４が、ｊの値がＣ以下であると判定した場合には、ステップＳ７０８へ移行する。一方、初期化部２２４が、ｊの値がＣよりも大きいと判定した場合には、ステップＳ７１４へ移行する。
【０２２８】
次に、ステップＳ７０８で、初期化部２２４は、ステップＳ２００において取得したデータ点ｘｉのＤ次元座標位置と、ステップＳ２０４において取得したクラスタｊのクラスタ中心ｃｊのＤ次元座標位置とに基づいて、データ点ｘｉとクラスタ中心ｃｊとの距離ｄ（ｘｉ,ｃｊ）を計算する。
【０２２９】
次に、ステップＳ７１０で、初期化部２２４は、ｊの値をｊ＋１に設定し、ステップＳ７０６へ移行する。
【０２３０】
次に、ステップＳ７１４で、初期化部２２４は、ステップＳ７０８において取得したデータ点ｘｉとクラスタ中心ｃｊの各々との距離の各々、及びステップＳ２０４において取得した当該データ点ｘｉの所属するクラスタａｉ、及び所属クラスタ中心
【０２３１】
【数５５】
0006334454.tif 000058
【０２３２】
に基づいて、当該データ点ｘｉのｕ（ｉ）を取得し、パラメータ記憶部２２２に記憶する。
【０２３３】
次に、ステップＳ７１６で、初期化部２２４は、ｊの値を１に設定する。
【０２３４】
次に、ステップＳ７１７で、初期化部２２４は、ｊ≠ａｉか否かを判定する。初期化部２２４が、ｊ≠ａｉと判定した場合には、初期化処理は、ステップＳ７１８へ移行する。一方、初期化部２２４は、ｊ＝ａｉと判定した場合には、初期化処理は、ステップＳ７２２へ移行する。
【０２３５】
次に、ステップＳ７１８で、初期化部２２４はｊの値がＣ以下か否かを判定する。初期化部２２４が、ｊの値がＣ以下であると判定した場合には、初期化処理はステップＳ７２０へ移行する。一方、初期化部２２４が、ｊの値がＣよりも大きいと判定した場合には、初期化処理は、ステップＳ２１２へ移行する。
【０２３６】
ステップＳ７２０で、初期化部２２４は、ステップＳ７０８において取得したデータ点ｘｉとクラスタ中心ｃｊの各々との距離ｄ（ｘｉ,ｃｊ）に基づいて、当該データ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）を決定する。
【０２３７】
次に、ステップＳ７２２で、初期化部２２４は、ｊの値をｊ＋１と設定して、ステップＳ７１７へ移行する。
【０２３８】
上記ステップＳ６０２の所属クラスタ中心探索処理について、図１８について詳細に説明する。
【０２３９】
図１８のステップＳ８００で、所属クラスタ中心探索部２２６は、ステップＳ７１４、又は周期ｔ−１の処理におけるステップＳ９０４、若しくはステップＳ９１４において取得した当該データ点ｘｉのｕ（ｉ）と、ステップＳ７０２、又は周期ｔ−１の処理におけるステップＳ９２８において取得したｓ（ａｉ）とに基づいて、上記（９）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６が、上記（９）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、データｘｉの現在所属しているクラスタａｉにそのまま所属するとして、ステップＳ３１８へ移行する。一方、所属クラスタ中心探索部２２６が、上記（９）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８０１へ移行する。
【０２４０】
次に、ステップＳ８０１で、所属クラスタ中心探索部２２６は、ｊの値がａｉか否かを判定する。所属クラスタ中心探索部２２６が、ｊの値がａｉでないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１０へ移行する。一方、所属クラスタ中心探索部２２６が、ｊの値がａｉであると判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１４へ移行する。
【０２４１】
ステップＳ８０２で、所属クラスタ中心探索部２２６は、ステップＳ７００、又は周期ｔ−１の処理におけるステップＳ９２６の処理において取得したデータ点ｘｉの所属するクラスタ中心
【０２４２】
【数５６】
0006334454.tif 000059
【０２４３】
と、クラスタ中心ｃｊとの距離
【０２４４】
【数５７】
0006334454.tif 000060
【０２４５】
を取得する。
【０２４６】
次に、ステップＳ８０４で、所属クラスタ中心探索部２２６は、ステップＳ７１４、又は周期ｔ−１の処理におけるステップＳ９０４、若しくはステップＳ９１４において取得した当該データ点ｘｉのｕ（ｉ）と、ステップＳ８０２において取得した距離
【０２４７】
【数５８】
0006334454.tif 000061
【０２４８】
とに基づいて、上記（１１）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６が、上記（１１）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１４へ移行する。一方、所属クラスタ中心探索部２２６が、上記（１１）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８０６へ移行する。
【０２４９】
ステップＳ８０６で、所属クラスタ中心探索部２２６は、ステップＳ７１４、又は周期ｔ−１の処理におけるステップＳ９０４、若しくはステップＳ９１４において取得した当該データ点ｘｉのｕ（ｉ）と、ステップＳ７２０、又は周期ｔ−１の処理におけるステップＳ９１０、若しくはステップＳ９２０において取得したデータ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）とに基づいて、上記（１２）式を満たすか否かを判定する。所属クラスタ中心探索部２２６が、上記（１２）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１４へ移行する。一方、所属クラスタ中心探索部２２６が、上記（１２）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８０８へ移行する。
【０２５０】
ステップＳ８０８で、所属クラスタ中心探索部２２６は、ステップＳ２００において取得したデータ点ｘｉのＤ次元座標位置と、ステップＳ２０４、又は周期ｔ−１の処理におけるステップＳ４０４において取得した所属クラスタａｉのクラスタ中心
【０２５１】
【数５９】
0006334454.tif 000062
【０２５２】
のＤ次元座標位置とに基づいて、データ点ｘｉと、当該データ点ｘｉの所属するクラスタａｉのクラスタ中心
【０２５３】
【数６０】
0006334454.tif 000063
【０２５４】
との距離
【０２５５】
【数６１】
0006334454.tif 000064
【０２５６】
を計算する。
【０２５７】
次に、ステップＳ８１０で、所属クラスタ中心探索部２２６は、ステップＳ８０８において取得した距離
【０２５８】
【数６２】
0006334454.tif 000065
【０２５９】
を、当該データ点ｘｉのｕ（ｉ）とし、パラメータ記憶部２２２に記憶する。
【０２６０】
次に、ステップＳ８１２で、所属クラスタ中心探索部２２６は、ステップＳ８０８において取得した距離
【０２６１】
【数６３】
0006334454.tif 000066
【０２６２】
と、ステップＳ８０２において取得した距離
【０２６３】
【数６４】
0006334454.tif 000067
【０２６４】
とに基づいて、上記（１４）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６が、上記（１４）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１４へ移行する。一方、所属クラスタ中心探索部２２６が、上記（１４）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８１４へ移行する。
【０２６５】
次に、ステップＳ８１４で、所属クラスタ中心探索部２２６は、ステップＳ８０８で取得した距離
【０２６６】
【数６５】
0006334454.tif 000068
【０２６７】
と、ステップＳ７２０、又は周期ｔ−１の処理におけるステップＳ９１０、若しくはステップＳ９２０において取得したデータ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）とに基づいて、上記（１５）式の条件を満たすか否かを判定する。所属クラスタ中心探索部２２６が、上記（１５）式の条件を満たすと判定した場合には、ステップＳ３１４へ移行する。一方、所属クラスタ中心探索部２２６が、上記（１５）式の条件を満たさないと判定した場合には、ステップＳ３１２へ移行する。
【０２６８】
ステップＳ８１６で、所属クラスタ中心探索部２２６は、ステップＳ３１２において取得したｄ（ｘｉ,ｃｊ,ｔ）を当該データ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）としてパラメータ記憶部２２２に記憶する。
【０２６９】
ステップＳ８１８で、所属クラスタ中心探索部２２６は、ステップＳ３１２において取得した距離ｄ（ｘｉ,ｃｊ,ｔ）の各々と、ステップＳ８０８において取得した距離
【０２７０】
【数６６】
0006334454.tif 000069
【０２７１】
とに基づいて、上記（６）式に従って、データ点ｘｉの所属するクラスタａｉを決定する。
【０２７２】
上記ステップＳ６０４のクラスタ中心更新処理について、図１９、及び図２０について詳細に説明する。
【０２７３】
図１９のステップＳ８９９で、クラスタ中心更新部２２８は、ステップＳ２００において取得した、ステップＳ３０８、ステップＳ８００、及びステップＳ８１８において取得したクラスタｊに所属するデータ点ｘｉの各々のＤ次元座標位置に基づいて、上記（７）式に従って、クラスタ中心ｃｊ,ｔのＤ次元座標位置を計算し、パラメータ記憶部２２２に記憶する。
【０２７４】
ステップＳ９００で、クラスタ中心更新部２２８は、ｉの値がＮ以下か否かを判定する。クラスタ中心更新部２２８が、ｉの値がＮ以下であると判定した場合には、クラスタ中心更新処理は、ステップＳ９０２へ移行する。一方、クラスタ中心更新部２２８が、ｉの値がＮより大きいと判定した場合には、クラスタ中心更新処理は、ステップＳ９２６へ移行する。
【０２７５】
次に、ステップＳ９０２で、クラスタ中心更新部２２８は、ステップＳ８１８においてデータ点ｘｉの所属するクラスタａｉが、周期ｔ−１から変更されたか否かを判定する。クラスタ中心更新部２２８が、変更されたと判定した場合には、クラスタ中心更新処理は、ステップＳ９０４へ移行する。一方、クラスタ中心更新部２２８が、変更されていないと判定した場合には、クラスタ中心更新処理は、ステップＳ９１４へ移行する。
【０２７６】
次に、ステップＳ９０４で、クラスタ中心更新部２２８は、ステップＳ３１２において取得したデータ点ｘｉと所属するクラスタａｉのクラスタ中心との距離と、ステップＳ４０６において取得した当該クラスタａｉのクラスタ中心の移動距離との和を、当該ｘｉのｕ（ｉ）とし、パラメータ記憶部２２２に記憶する。
【０２７７】
次に、ステップＳ９０６で、クラスタ中心更新部２２８は、ｊの値を１に設定する。
【０２７８】
次に、ステップＳ９０７で、クラスタ中心更新部２２８は、ｊの値がａｉでないか否かを判定する。クラスタ中心更新部２２８が、ｊの値がａｉでないと判定した場合には、ステップＳ９０８へ移行する。一方、クラスタ中心更新部２２８が、ｊの値がａｉであると判定した場合には、ステップＳ９１２へ移行する。
【０２７９】
次に、ステップＳ９０８で、クラスタ中心更新部２２８は、ｊの値がＣ以下であるか否かを判定する。クラスタ中心更新部２２８が、ｊの値がＣ以下であると判定した場合には、クラスタ中心更新処理は、ステップＳ９１０へ移行する。一方、クラスタ中心更新部２２８が、ｊの値がＣよりも大きいと判定した場合には、クラスタ中心更新処理は、ステップＳ９２４へ移行する。
【０２８０】
次に、ステップＳ９１０で、クラスタ中心更新部２２８は、パラメータ記憶部２２２に記憶されているデータ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）と、ステップＳ４０６において取得したクラスタｊのクラスタ中心ｃｊの移動距離とに基づいて、データ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）を更新し、パラメータ記憶部２２２に記憶する。なお、クラスタｊがデータ点ｘｉの周期ｔ−１における所属クラスタａｉである場合には、図１８のステップＳ８０８において取得した距離
【０２８１】
【数６７】
0006334454.tif 000070
【０２８２】
と、ステップＳ４０６において取得した対応するクラスタｊのクラスタ中心ｃｊの移動距離とに基づいて、データ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）として、パラメータ記憶部２２２に記憶する。
【０２８３】
次に、ステップＳ９１２で、クラスタ中心更新部２２８は、ｊの値をｊ＋１に設定してステップＳ９０７へ移行する。
【０２８４】
ステップＳ９１４で、クラスタ中心更新部２２８は、パラメータ記憶部２２２に記憶されているデータ点ｘｉの上限値ｕ（ｉ）と、ステップＳ４０６において取得したクラスタａｉの移動距離とに基づいて、データ点ｘｉの上限値ｕ（ｉ）を更新し、パラメータ記憶部２２２に記憶する。
【０２８５】
次に、ステップＳ９１６で、クラスタ中心更新部２２８は、ｊの値を１に設定する。
【０２８６】
次に、ステップＳ９１７で、クラスタ中心更新部２２８は、ｊの値がａｉでないか否かを判定する。クラスタ中心更新部２２８が、ｊの値がａｉでないと判定した場合には、ステップＳ９１８へ移行する。一方、クラスタ中心更新部２２８が、ｊの値がａｉであると判定した場合には、ステップＳ９２２へ移行する。
【０２８７】
次に、ステップＳ９１８で、クラスタ中心更新部２２８は、ｊの値がＣ以下であるか否かを判定する。クラスタ中心更新部２２８が、ｊの値がＣ以下であると判定した場合には、クラスタ中心更新処理は、ステップＳ９２０へ移行する。一方、クラスタ中心更新部２２８が、ｊの値がＣよりも大きいと判定した場合には、クラスタ中心更新処理は、ステップＳ９２４へ移行する。
【０２８８】
次に、ステップＳ９２０で、クラスタ中心更新部２２８は、パラメータ記憶部２２２に記憶されているデータ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）と、ステップＳ４０６において取得したクラスタｊのクラスタ中心ｃｊの移動距離とに基づいて、データ点ｘｉとクラスタｊとの組み合わせのｌ（ｉ,ｊ）を更新し、パラメータ記憶部２２２に記憶する。
【０２８９】
次に、ステップＳ９２２で、クラスタ中心更新部２２８は、ｊの値をｊ＋１と設定し、ステップＳ９１７へ移行する。
【０２９０】
ステップＳ９２４で、クラスタ中心更新部２２８は、ｉの値をｉ＋１に設定してステップＳ９００へ移行する。
【０２９１】
ステップＳ９２６で、クラスタ中心更新部２２８は、ステップＳ８９９において取得したクラスタｊの各々のＤ次元座標位置に基づいて、全てのクラスタｊの組み合わせのクラスタ中心間の距離の計算をし、パラメータ記憶部２２２に記憶する。
【０２９２】
次に、ステップＳ９２８で、クラスタ中心更新部２２８は、クラスタｊの各々について、ステップＳ９２６において取得した全てのクラスタｊの組み合わせのクラスタ中心間の距離に基づいて、ｓ（ｊ）を取得し、パラメータ記憶部２２２に記憶し、図２０のステップＳ４１４へ移行する。
【０２９３】
以上説明したように、第２の実施形態に係るクラスタリング装置によれば、複数のデータ点の各々について、データ点の所属するクラスタを決定し、複数のクラスタの各々について、クラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、計算されたデータ点の所属するクラスタの中心位置の移動距離と当該所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、データ点についての所属するクラスタを決定する処理を行う頻度を決定し、予め定められた収束条件を満たすまで、所属するクラスタの決定と、データ点についての所属するクラスタを決定する処理を行う頻度の決定とを繰り返すことにより、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができる。
【０２９４】
また、従来のＥｌｋａｎ法の１周期当たりの計算回数はＮＥＣＥＤ回、データ点の所属するクラスタの中心位置の移動距離のみに基づいて頻度を決定する場合の１周期当たりの計算回数はＮＩ,ＥＣＥＤ回であるのに対し、第２の実施形態に係るクラスタリング装置２００を用いることで、１周期当たりの計算回数をＮＩA,ＥＣＥＤ回にすることができる。ただし、ＮＩA,Ｅ＜ＮＩ,Ｅ＜ＮＥ＜Ｎ、ＣＥ＜Ｃである。
【０２９５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０２９６】
次に、第３の実施形態に係るクラスタリング装置について説明する。
【０２９７】
第３の実施形態においては、三角不等式を利用したｋ−ｍｅａｎｓ高速化手法であるＨａｍｅｒｌｙ法に追加の処理を加える点が第１、及び第２の実施形態と異なる。なお、第１、及び第２の実施形態に係るクラスタリング装置と同様の構成及び作用については、同一の符号を付して説明を省略する。
【０２９８】
＜第３の実施形態の概要＞
まず、Ｈａｍｅｒｌｙ法による計算の省略について説明する。Ｈａｍｅｒｌｙ法は、三角不等式を利用しつつ、Ｅｌｋａｎ法を省メモリ化したｋ−ｍｅａｎｓ高速化手法である。
【０２９９】
第１の計算の省略については、図１０に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０３００】
【数６８】
0006334454.tif 000071
【０３０１】
、及び所属クラスタ中心
【０３０２】
【数６９】
0006334454.tif 000072
【０３０３】
から最近傍のクラスタ中心ｃｊが存在する場合、上記（９）式を満たすならば、所属クラスタａｉのクラスタ中心
【０３０４】
【数７０】
0006334454.tif 000073
【０３０５】
が、データ点ｘｉに最も近いといえる。そのため、当該データ点ｘｉと全てのクラスタ中心間との距離計算を省略することができる。なお、上記（１０）式に示すｕ（ｉ）は、更新前の所属クラスタ中心
【０３０６】
【数７１】
0006334454.tif 000074
【０３０７】
とデータ点ｘｉとの距離に、更新後の所属クラスタ中心
【０３０８】
【数７２】
0006334454.tif 000075
【０３０９】
の移動距離を足したものであり、データ点ｘｉと所属クラスタ中心間の距離の上限値を表す。
【０３１０】
第２の計算の省略については、図２１に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０３１１】
【数７３】
0006334454.tif 000076
【０３１２】
、及び所属クラスタ以外のデータ点ｘｉに２番目に近いクラスタ中心ｃｊが存在する場合、下記（１６）式を満たすならば、所属クラスタａｉのクラスタ中心
【０３１３】
【数７４】
0006334454.tif 000077
【０３１４】
が、２番目に近いクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。
【０３１５】
【数７５】
0006334454.tif 000078
【０３１６】
そのため、当該データ点ｘｉと全てのクラスタ中心間との距離計算を省略することができる。なお、上記（１６）式に示すｌ（ｉ）は、更新前のデータ点ｘｉと２番目に近いクラスタ中心ｃｊとデータ点ｘｉとの距離に、更新後のデータ点ｘｉと２番目に近いクラスタ中心の移動距離を引いたものであり、データ点ｘｉとデータ点ｘｉと２番目に近いクラスタ中心間との距離の下限値を表す。
【０３１７】
第３の計算の省略については、図２２に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０３１８】
【数７６】
0006334454.tif 000079
【０３１９】
、及び所属クラスタ中心
【０３２０】
【数７７】
0006334454.tif 000080
【０３２１】
と最近傍のクラスタ中心ｃｊが存在する場合、下記（１７）式を満たすならば、所属クラスタａｉのクラスタ中心
【０３２２】
【数７８】
0006334454.tif 000081
【０３２３】
が、最近傍のクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。そのため、当該データ点ｘｉと全てのクラスタ中心間との距離計算を省略することができる。
【０３２４】
【数７９】
0006334454.tif 000082
【０３２５】
第４の計算の省略については、図２３に示すように、データ点ｘｉ、当該データ点ｘｉが所属するクラスタａｉのクラスタ中心
【０３２６】
【数８０】
0006334454.tif 000083
【０３２７】
、及びデータ点ｘｉに２番目に近いクラスタ中心ｃｊが存在する場合、下記（１８）式を満たすならば、所属クラスタａｉのクラスタ中心
【０３２８】
【数８１】
0006334454.tif 000084
【０３２９】
が、２番目に近いクラスタ中心ｃｊよりもデータ点ｘｉに近いといえる。
【０３３０】
【数８２】
0006334454.tif 000085
【０３３１】
そのため、当該データ点ｘｉと全てのクラスタ中心間との距離計算を省略することができる。
【０３３２】
＜第３の実施形態に係るクラスタリング装置の構成＞
次に、第３の実施形態に係るクラスタリング装置の構成について説明する。図２４に示すように、第３の実施形態に係るクラスタリング装置３００は、ＣＰＵと、ＲＡＭと、後述するクラスタリング処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このクラスタリング装置は、機能的には図２４に示すように入力部１０と、演算部３２０と、出力部９０とを含んで構成されている。
【０３３３】
演算部３２０は、パラメータ記憶部３２２と、初期化部３２４と、所属クラスタ中心探索部３２６と、クラスタ中心更新部３２８と、収束判定部３０とを含んで構成されている。
【０３３４】
パラメータ記憶部３２２には、入力部１０において受け付けたデータ点ｘｉの各々のＤ次元座標位置、及び更新頻度係数の上限値ｋｍａｘと、後述する初期化部３２４又はクラスタ中心更新部３２８により計算されたクラスタ中心ｃｊの各々の位置のＤ次元座標位置、全てのクラスタの組み合わせのクラスタ中心ｃｊ間の各々の距離、及び全てのクラスタｊの各々についての最近傍のクラスタとのクラスタ中心ｃｊ間の距離ｓ（ｊ）と、後述する初期化部３２４又はクラスタ中心更新部３２８により計算されたデータ点ｘｉの各々の更新頻度Δｔｉ、更新頻度係数ｋｉ、所属するクラスタａｉのクラスタ中心と当該データ点ｘｉとの距離の上限値ｕ（ｉ）、及びデータ点ｘｉと２番目に近いクラスタ中心と当該データ点ｘｉとの距離の下限値ｌ（ｉ）の各々と、後述するクラスタ中心更新部３２８により計算されたクラスタ中心ｃｊの各々の周期ｔ−１から周期ｔまでの移動距離ｐｊ,ｔと、後述する所属クラスタ中心探索部３２６において計算された周期ｔにおけるデータ点ｘｉの各々と、クラスタ中心ｃｊとの各々との距離が記憶されている。
【０３３５】
初期化部３２４は、入力部１０において受け付けたデータ点ｘｉの各々から、ランダムにＣ個を選択し、選択したデータ点ｘｉのＤ次元座標位置を、クラスタｊのクラスタ中心ｃｊのＤ次元座標位置とし、パラメータ記憶部３２２に記憶する。また、初期化部３２４は、データ点ｘｉの各々についての更新頻度Δｔｉの値を１としてパラメータ記憶部３２２に記憶する。また、初期化部３２４は、データ点ｘｉの各々についての更新頻度係数ｋｉの値を０としてパラメータ記憶部３２２に記憶する。また、初期化部３２４は、全てのクラスタｊの各々のクラスタ間のクラスタ中心距離ｄ（ｃｊ,ｃｊ´）を計算し（ｊ´≠ｊ）、パラメータ記憶部３２２に記憶する。また、初期化部３２４は、クラスタｊの各々について、計算したクラスタ中心距離ｄ（ｃｊ,ｃｊ´）のうち一番距離が小さいものを当該クラスタｊの最近傍のクラスタ中心との距離ｓ（ｊ）としてパラメータ記憶部３２２に記憶する。また、初期化部３２４は、データ点ｘｉの各々について、所属するクラスタａｉをランダムに設定する。
【０３３６】
次に、初期化部３２４は、パラメータ記憶部３２２に記憶されている入力部１０において受け付けたデータ点ｘｉの各々のＤ次元座標位置、及びクラスタｊの各々のクラスタ中心ｃｊのＤ次元座標位置に基づいて、データ点ｘｉの各々について、当該データ点ｘｉとクラスタｊの各々との距離ｄ（ｘｉ,ｃｊ）を計算する。次に、データ点ｘｉの各々について、当該データ点ｘｉが所属するクラスタａｉとの距離ｄ（ｘｉ,ａｉ）を、当該データ点ｘｉと所属クラスタ中心間との距離の上限値ｕ（ｉ）としてパラメータ記憶部２２２に記憶する。次に、データ点ｘｉの各々について、当該データ点ｘｉと２番目に近いクラスタ中心ｃｊとの距離ｄ（ｘｉ,ｃｊ）を、当該データ点ｘｉと２番目に近いクラスタ中心ｃｊとの距離の下限値ｌ（ｉ）としてパラメータ記憶部３２２に記憶する。
【０３３７】
所属クラスタ中心探索部３２６は、入力部１０において受け付けたデータ点の集合Ｘに含まれる複数のデータ点ｘｉの各々について、当該データ点ｘｉについて、パラメータ記憶部３２２に記憶されている当該データ点ｘｉの更新頻度Δｔｉと現在の周期ｔとに基づいて、上記（５）式の条件を満たすか否かを判定する。また、所属クラスタ中心探索部３２６は、データ点ｘｉの各々について、パラメータ記憶部３２２に記憶されている当該データ点ｘｉの当該データ点ｘｉと所属クラスタ中心
【０３３８】
【数８３】
0006334454.tif 000086
【０３３９】
との距離の上限値ｕ（ｉ）、及び所属クラスタａｉの最近傍のクラスタ中心ｃｊとの距離ｓ（ａｉ）に基づいて、上記（９）式の条件を満たすか否かを判定する。
【０３４０】
また、所属クラスタ中心探索部３２６は、データ点ｘｉの各々について、取得した当該データ点ｘｉと所属クラスタ中心間の距離の上限値ｕ（ｉ）と、パラメータ記憶部３２２に記憶されている、初期化部３２４又は前回の処理のクラスタ中心更新部３２８において取得したデータ点ｘｉと２番目に近いクラスタｊと当該データ点ｘｉとの距離の下限値ｌ（ｉ）とに基づいて、上記（１６）式の条件を満たすか否かを判定する。所属クラスタ中心探索部３２６は、上記（５）式を満たさない場合、又は、上記（９）式、若しくは上記（１６）式の条件を満たすデータ点ｘｉについては、全てのクラスタ中心ｃｊとの距離計算を省略することができると判定する。この場合、当該データ点ｘｉは、現在所属するクラスタａｉにそのまま所属する。
【０３４１】
ここで、２番目に近いクラスタｊをどのように特定するかということを説明する。まず、１回目の処理においては、初期化部３２４において計算され、パラメータ記憶部３２２に記憶されているデータ点ｘｉの各々と、クラスタ中心ｃｊの各々との距離のうち２番目に小さい距離に対応するクラスタｊがデータ点ｘｉに２番目に近いクラスタｊとなる。一方、２回目以降の処理においては、特定のデータ点ｘｉの２番目に近いクラスタｊが変更されるタイミングは、特定のデータ点ｘｉの所属するクラスタａｉが変更されるタイミングである。そのため、当該処理において、当該データ点ｘｉと、全てのクラスタ中心ｃｊとの距離は計算されるため、計算された特定のデータ点ｘｉと、クラスタ中心ｃｊとの距離のうち２番目に小さい距離に対応するクラスタｊを２番目に近いクラスタｊとして特定する。
【０３４２】
次に、所属クラスタ中心探索部３２６は、上記（５）式の条件を満たし、かつ、上記（９）式及び上記（１６）式の条件を満たさないデータ点ｘｉの各々について、パラメータ記憶部３２２に記憶されている、当該データ点ｘｉのＤ次元座標位置、及び当該データ点ｘｉの所属しているクラスタａｉのクラスタ中心のＤ次元座標位置に基づいて、データ点ｘｉと所属クラスタ中心との距離を計算する。ここで、計算した距離を当該データ点ｘｉのｕ（ｉ）としてパラメータ記憶部３２２に記憶する。
【０３４３】
次に、所属クラスタ中心探索部３２６は、上記（５）式の条件を満たし、かつ、上記（９）式及び上記（１６）式の条件を満たさないデータ点ｘｉの各々について、パラメータ記憶部３２２に記憶されている、当該データ点ｘｉの所属するクラスタａｉのｓ（ａｉ）と、計算されたデータ点ｘｉと所属クラスタ中心
【０３４４】
【数８４】
0006334454.tif 000087
【０３４５】
との距離とに基づいて、上記（１７）式の条件を満たすか否かを判定する。また、所属クラスタ中心探索部３２６は、上記（５）式の条件を満たし、かつ、上記（９）式及び上記（１６）式の条件を満たさないデータ点ｘｉの各々について、パラメータ記憶部３２２に記憶されている、初期化部３２４又は前回の処理のクラスタ中心更新部３２８において取得した当該データ点ｘｉと２番目に近いクラスタｊと当該データ点ｘｉとの距離の下限値ｌ（ｉ）と、計算されたデータ点ｘｉと所属クラスタ中心
【０３４６】
【数８５】
0006334454.tif 000088
【０３４７】
との距離とに基づいて、上記（１８）式の条件を満たすか否かを判定する。所属クラスタ中心探索部３２６は、上記（１８）式、又は上記（１７）式の条件を満たすデータ点ｘｉについては、全てのクラスタ中心ｃｊとの距離計算を省略することができると判定する。この場合、当該データ点ｘｉは、現在所属するクラスタａｉにそのまま所属する。
【０３４８】
次に、所属クラスタ中心探索部３２６は、上記において計算処理を省略しないと判定されたデータ点ｘｉについて、パラメータ記憶部２２に記憶されている当該データ点ｘｉのＤ次元座標位置、及びクラスタ中心ｃｊの各々のＤ次元座標位置とに基づいて、当該データ点ｘｉと、クラスタ中心ｃｊの各々との距離を計算する。
【０３４９】
そして、データ点ｘｉの各々のうち、クラスタ中心ｃｊの各々との距離を計算したデータ点ｘｉの各々について、計算された当該データ点ｘｉと、クラスタ中心ｃｊの各々との距離と、当該データ点ｘｉと、更新前の所属するクラスタ中心
【０３５０】
【数８６】
0006334454.tif 000089
【０３５１】
との距離とに基づいて、上記（６）式に基づいて、当該データ点ｘｉが所属するクラスタａｉを更新する。なお、当該データ点ｘｉと、更新前の所属するクラスタ中心
【０３５２】
【数８７】
0006334454.tif 000090
【０３５３】
との距離は、他のクラスタ中心ｃｊと当該データ点ｘｉとの距離の計算の省略の判定の処理途中において計算した距離を用いる。
【０３５４】
＜第３の実施形態に係るクラスタリング装置の作用＞
次に、第３の実施形態に係るクラスタリング装置３００の作用について説明する。まず、入力部１０において、データ点の集合Ｘと、更新頻度係数の上限値ｋｍａｘとを受け付け当該データ点の集合Ｘに含まれるデータ点ｘｉの各々のＤ次元座標位置と、更新頻度係数の上限値ｋｍａｘとをパラメータ記憶部２２２に記憶する。そして、入力部１０においてクラスタ数Ｃを受け付けると、クラスタリング装置３００によって図２０、図２５Ａ、図２５Ｂ、図２６、図２７に示すクラスタリング処理ルーチンを実行する。
【０３５５】
図２５ＡのステップＳ９５０で、初期化部３２４は、各種パラメータの初期値を設定する。
【０３５６】
次に、ステップＳ１０００で、所属クラスタ中心探索部３２６は、入力部１０において受け付けたデータ点ｘｉの各々について、当該データ点ｘｉの所属するクラスタａｉを探索する。
【０３５７】
次に、ステップＳ１００２で、クラスタ中心更新部３２８は、クラスタｊの各々について、当該クラスタｊのクラスタ中心ｃｊ,ｔを更新する。また、ステップＳ１００２で、クラスタ中心更新部３２８は、データ点ｘｉの各々について、当該データ点ｘｉの更新頻度係数ｋｉを更新し、更新された更新頻度係数ｋｉに基づいて、当該データ点ｘｉの更新頻度Δｔｉを更新する。
【０３５８】
上記ステップＳ９５０の初期化処理について、図２５Ｂにおいて詳細に説明する。
【０３５９】
図２５ＢのステップＳ９５２で、初期化部３２４は、ステップＳ７０８において取得した距離ｄ（ｘｉ,ｃｊ）の各々に基づいて、データ点ｘｉとクラスタ中心ｃｊが、２番目に近いクラスタ中心ｃｊとの距離ｄ（ｘｉ,ｃｊ）を当該データ点ｘｉのｌ（ｉ）として、パラメータ記憶部３２２に記憶する。
【０３６０】
上記ステップＳ１０００の所属クラスタ中心探索処理について、図２６において詳細に説明する。
【０３６１】
図２６のステップＳ１１０２で、所属クラスタ中心探索部３２６は、ステップＳ７１４、又は周期ｔ−１の処理におけるステップＳ９０４、若しくはステップＳ９１４において取得した当該データ点ｘｉのｕ（ｉ）と、パラメータ記憶部３２２に記憶されている当該データ点ｘｉのｌ（ｉ）とに基づいて、上記（１６）式の条件を満たすか否かを判定する。所属クラスタ中心探索部３２６が、上記（１６）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１８へ移行する。一方、所属クラスタ中心探索部３２６が、上記（１６）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８０８へ移行する。
【０３６２】
ステップＳ１１０４で、所属クラスタ中心探索部３２６は、ステップＳ８０８において取得した距離
【０３６３】
【数８８】
0006334454.tif 000091
【０３６４】
と、パラメータ記憶部２２２に記憶されている所属するクラスタａｉのｓ（ｊ）とに基づいて、上記（１７）式の条件を満たすか否かを判定する。所属クラスタ中心探索部３２６が、上記（１７）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１８へ移行する。一方、所属クラスタ中心探索部３２６が、上記（１７）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ１１０６へ移行する。
【０３６５】
次に、ステップＳ１１０６で、所属クラスタ中心探索部３２６は、ステップＳ８０８において取得した距離
【０３６６】
【数８９】
0006334454.tif 000092
【０３６７】
と、パラメータ記憶部３２２に記憶されている当該データ点ｘｉのｌ（ｉ）とに基づいて、上記（１８）式の条件を満たすか否かを判定する、所属クラスタ中心探索部３２６が、上記（１８）式の条件を満たすと判定した場合には、所属クラスタ中心探索処理は、ステップＳ３１８へ移行する。一方、所属クラスタ中心探索部３２６が、上記（１８）式の条件を満たさないと判定した場合には、所属クラスタ中心探索処理は、ステップＳ８０１へ移行する。
【０３６８】
上記ステップＳ１００２のクラスタ中心更新処理について、図２７、及び図２０について詳細に説明する。
【０３６９】
図２７のステップＳ１１９９で、クラスタ中心更新部２２８は、ステップＳ２００において取得した、ステップＳ３０８、ステップＳ８００、ステップＳ８１８、ステップＳ１１０２、ステップＳ１１０４、及びステップＳ１１０６において取得したクラスタｊに所属するデータ点ｘｉの各々のＤ次元座標位置に基づいて、上記（７）式に従って、クラスタ中心ｃｊ,ｔのＤ次元座標位置を計算し、パラメータ記憶部３２２に記憶する。
【０３７０】
図２７のステップＳ１２００で、クラスタ中心更新部３２８は、ステップＳ３１２において取得した距離ｄ（ｘｉ,ｃｊ）のうち２番目に小さい距離となるクラスタｊを、当該データ点ｘｉに２番目に近いクラスタ中心ｃｊとし、ステップＳ３１２において取得した当該データ点ｘｉと当該クラスタ中心ｃｊとの距離ｄ（ｘｉ,ｃｊ）と、ステップＳ４０６において取得した当該クラスタ中心ｃｊの移動距離とに基づいて、当該データ点ｘｉのｌ（ｉ）を更新して、パラメータ記憶部３２２に記憶する。
【０３７１】
ステップＳ１２０２で、クラスタ中心更新部３２８は、周期ｔ−１のステップＳ１２００、又はステップＳ１２０２において取得した当該データ点ｘｉのｌ（ｉ）と、ステップＳ４０６において取得した、対応する当該データ点ｘｉと２番目に近いクラスタ中心ｃｊとの移動距離とに基づいて、当該データ点ｘｉのｌ（ｉ）を更新して、パラメータ記憶部３２２に記憶する。
【０３７２】
図２７のステップＳ９２８で、クラスタ中心更新部３２８は、クラスタｊの各々について、ステップＳ９２６において取得した全てのクラスタｊの組み合わせのクラスタ中心間の距離に基づいて、ｓ（ｊ）を取得し、パラメータ記憶部２２２に記憶し、図２０のステップＳ４１４へ移行する。
【０３７３】
以上説明したように、第３の実施形態に係るクラスタリング装置によれば、複数のデータ点の各々について、データ点の所属するクラスタを決定し、複数のクラスタの各々について、クラスタに所属すると決定されたデータ点の位置に基づいて、クラスタの中心位置を更新し、更新前と更新後のクラスタの中心位置の移動距離を計算し、複数のデータ点の各々について、計算されたデータ点の所属するクラスタの中心位置の移動距離と当該所属するクラスタとは異なるクラスタの中心位置の移動距離とを重み付けした値に基づいて、データ点についての所属するクラスタを決定する処理を行う頻度を決定し、予め定められた収束条件を満たすまで、所属するクラスタの決定と、データ点についての所属するクラスタを決定する処理を行う頻度の決定とを繰り返すことにより、データ点の数及びクラスタの数が大きな値であっても、複数のデータ点を高速にクラスタリングすることができる。
【０３７４】
また、従来のＨａｍｅｒｌｙ法の１周期当たりの計算回数はＮＨＣＨＤ回、データ点の所属するクラスタの中心位置の移動距離のみに基づいて頻度を決定する場合の１周期当たりの計算回数はＮＩ,ＨＣＨＤ回であるのに対し、第３の実施形態に係るクラスタリング装置３００を用いることで、１周期当たりの計算回数をＮＩA,ＨＣＨＤ回にすることができる。ただし、ＮＩA,Ｈ＜ＮＩ,Ｈ＜ＮＨ＜Ｎ、ＣＨ＜Ｃである。
【０３７５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０３７６】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０３７７】
１０   入力部
２０   演算部
２２   パラメータ記憶部
２４   初期化部
２６   所属クラスタ中心探索部
２８   クラスタ中心更新部
３０   収束判定部
９０   出力部
１００ クラスタリング装置
２００ クラスタリング装置
２２０ 演算部
２２２ パラメータ記憶部
２２４ 初期化部
２２６ 所属クラスタ中心探索部
２２８ クラスタ中心更新部
３００ クラスタリング装置
３２０ 演算部
３２２ パラメータ記憶部
３２４ 初期化部
３２６ 所属クラスタ中心探索部
３２８ クラスタ中心更新部
【図１】
0006334454.tif 000100
【図２】
0006334454.tif 000101
【図３】
0006334454.tif 000102
【図４】
0006334454.tif 000103
【図５】
0006334454.tif 000104
【図６】
0006334454.tif 000105
【図７】
0006334454.tif 000106
【図８】
0006334454.tif 000107
【図９】
0006334454.tif 000108
【図１０】
0006334454.tif 000109
【図１１】
0006334454.tif 000110
【図１２】
0006334454.tif 000111
【図１３】
0006334454.tif 000112
【図１４】
0006334454.tif 000113
【図１５】
0006334454.tif 000114
【図１６】
0006334454.tif 000115
【図１７】
0006334454.tif 000116
【図１８】
0006334454.tif 000117
【図１９】
0006334454.tif 000118
【図２０】
0006334454.tif 000119
【図２１】
0006334454.tif 000120
【図２２】
0006334454.tif 000121
【図２３】
0006334454.tif 000122
【図２４】
0006334454.tif 000123
【図２５Ａ】
0006334454.tif 000124
【図２５Ｂ】
0006334454.tif 000125
【図２６】
0006334454.tif 000126
【図２７】
0006334454.tif 000127
【図２８】
0006334454.tif 000128
【図２９】
0006334454.tif 000129