(57)【要約】【課題】クラスタリングを高速に行うことができるようにする。【解決手段】入力部１０が、データ点の集合と、クラスタの数とを受け付ける。そして、クラスタリング部２２が、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点とピボットとの間の距離、及びピボット中心距離記憶部４４に記憶された、複数のクラスタの中心の各々とピボットとの間の距離に基づいて、データ点が所属するクラスタを決定する。そして、分割結果処理部４８が、複数のクラスタの中心の各々について、当該中心に所属するデータ点を出力する。そして、出力部５０が、分割結果処理部４８によって出力されたデータ点を結果として出力する。【選択図】図１
2016042237.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ点をクラスタリングするクラスタリング装置であって、
複数のデータ点の各々と、前記データ点を表す空間上の点であるピボットとの間の距離を記憶したピボットデータ点距離記憶部と、
複数のクラスタの中心の各々と、前記ピボットとの間の距離を記憶したピボット中心距離記憶部と、
前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、前記データ点が所属する前記クラスタを決定するクラスタリング部と、
を含むクラスタリング装置。
【請求項２】
前記クラスタリング部は、
前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、距離の三角不等式を用いて、前記データ点が所属する前記クラスタを変更するか否かを判定し、前記データ点が所属する前記クラスタを変更すると判定された場合に、前記データ点が所属する前記クラスタを変更する所属変更判定部を含み、
前記所属変更判定部によって前記複数のデータ点の各々について前記データ点が所属する前記クラスタを変更しないと判定されるまで、前記所属変更判定部による判定及び変更を繰り返すことにより、前記複数のデータの各々について、前記データ点が所属する前記クラスタを決定する請求項１記載のクラスタリング装置。
【請求項３】
前記複数のデータ点、又は前記複数のクラスタの中心に基づいて、前記空間上の点から、前記ピボットを選択するピボット選択部を更に含む
請求項１又は請求項２に記載のクラスタリング装置。
【請求項４】
複数のデータ点の各々と、前記データ点を表す空間上の点であるピボットの各々との間の距離を記憶したピボットデータ点距離記憶部と、複数のクラスタの中心の各々と、前記ピボットとの間の距離を記憶したピボット中心距離記憶部と、クラスタリング部とを含み、前記複数のデータ点をクラスタリングするクラスタリング装置におけるクラスタリング方法であって、
前記クラスタリング部が、前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、前記データ点が所属する前記クラスタを決定するステップを含む
クラスタリング方法。
【請求項５】
前記クラスタリング部によって前記クラスタを決定するステップは、
所属変更判定部が、前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、距離の三角不等式を用いて、前記データ点が所属する前記クラスタを変更するか否かを判定し、前記データ点が所属する前記クラスタを変更すると判定された場合に、前記データ点が所属する前記クラスタを変更するステップを含み、
前記所属変更判定部によって前記複数のデータ点の各々について前記データ点が所属する前記クラスタを変更しないと判定されるまで、前記所属変更判定部による判定及び変更を繰り返すことにより、前記複数のデータの各々について、前記データ点が所属する前記クラスタを決定する
請求項４記載のクラスタリング方法。
【請求項６】
ピボット選択部が、前記複数のデータ点、又は前記複数のクラスタの中心に基づいて、前記空間上の点から、前記ピボットを選択するステップを更に含む
請求項４又は請求項５に記載のクラスタリング方法。
【請求項７】
コンピュータを、請求項１〜請求項３の何れか１項記載のクラスタリング装置の各部として機能させるためのプログラム。
【請求項８】
複数のデータ点をクラスタリングするクラスタリング装置であって、
前記複数のデータ点の各々について、複数のクラスタの中心間の距離、又は前記データ点の所属する前記クラスタの決定に応じて前記クラスタの中心の位置が変更されたか否かに基づいて、前記データ点が所属する前記クラスタを決定するクラスタリング部を含むクラスタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、方法、及びプログラムに係り、特に、データ点が所属するクラスタを決定するクラスタリング装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
情報通信技術の発展に伴い、日々多種多量の大規模データ（ビッグデータ）が生成・収集・蓄積されている。ビッグデータの効果的な活用のためには、与えられたデータを教師データなしに自動的に分類するクラスタリング技術は不可欠である。Ｌｌｏｙｄ法は非階層型のクラスタリング手法として知られるｋ−ｍｅａｎｓ法の典型であり、データマイニングにおいて主要なアルゴリズムの一つに位置付けられている。
【０００３】
Ｌｌｏｙｄ法の詳細なアルゴリズムは非特許文献１のとおりである。Ｌｌｏｙｄ法は、ユークリッド空間上のＮ個のデータ点の集合Ｘとその集合を分割するクラスタの数ｋ（ｋ＜Ｎ）を入力として、互いに素なｋ個の集合
【０００４】
【数１】
2016042237.tif 000003
【０００５】
を出力する。ただし、Ｙｉ（ｉ＝１，２，... ，ｋ）は、
【０００６】
【数２】
2016042237.tif 000004
【０００７】
である。ここで、Ｘを分割する際に、Ｎ個のデータ点について、ｋ個のクラスタの中心（セントロイド）のうち最も近い中心を求めるためにＮ×ｋ回の距離計算を繰り返し行う必要がある。そのため、Ｎが大きな値を持つビッグデータにＬｌｏｙｄ法を適用した場合、結果出力までに多大な計算量、即ち、計算時間を要するという問題が生じる。この問題を解決するため、距離計算の一部を省略することで高速化を行う種々の高速化手法が提案されている。
【０００８】
たとえば、下記の非特許文献２で、Ｅｌｋａｎは距離の三角不等式を利用して算出した中心とデータ点の距離の下限を用いて不必要な距離計算を避ける手法が提案している。
【０００９】
Ｅｌｋａｎの手法では、まずｋ個の中心それぞれとＮ個のデータ点との距離の下限値を記憶するために記憶領域を確保する。実計算を行うたびに距離の下限値は、実距離によって置換され、中心座標が更新される毎に中心座標の移動距離分だけ減算される（減算によって０以下になる場合は０に置換される）。
【００１０】
図２４を用いてＥｌｋａｎの方法における距離計算の省略方法を示す。データ点ｘが所属している中心をｃＸとし、ｃＸ以外の中心ｃＹについて一反復前にｘとｃＹとの距離Ｄが計算されていたとする（このとき、ｘとｃＹとの距離の下限値はＤに置換される。）。中心の座標が更新された後、ｘの所属がｃＸからｃＹに変更されるか否かを考える。以下、ｄ（ａ，ｂ）はユークリッド空間上の２点ａ，ｂの距離を表す。ｘとｃＹとの距離の下限値は、ｃＹの移動距離ｄ分減算され、Ｄ−ｄとなる。このとき、ｘとｃＸとの距離ｄ（ｘ，ｃＸ）がｄ（ｘ，ｃＸ）＜Ｄ−ｄ（距離の省略判定不等式）を満たせばｄ（ｘ，ｃＹ）の計算を行うことなく、ｘの所属がｃＸからｃＹに変更されないことが分かる。つまり、ｄ（データ点，所属する中心）とｄ（更新前の中心，更新後の中心）の計算を行うことでｄ（データ点，所属していない中心）の計算の一部を省略できる。
【００１１】
下記の通り、距離の省略判定不等式に必要なｄ（データ点，所属する中心）とｄ（更新前の中心，更新後の中心）に比べ、省略される距離であるｄ（データ点，所属していない中心）の個数が多いので、距離計算の割合によってはｋ−ｍｅａｎｓクラスタリングの大幅な高速化が達成される。
【００１２】
ｄ（データ点，所属する中心）：Ｎ個
ｄ（更新前の中心，更新後の中心）：ｋ個
ｄ（データ点，所属していない中心）：Ｎ×（ｋ−１）個
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Bishop.ChristopherM.（著）, and 元田浩、栗田多喜夫、樋口知之、松本裕治、村田 昇 （監訳）、「パターン認識と機械学習上・下」、２００７、ｐ.１４０−１４６
【非特許文献２】Elkan, Charles.，“Using the triangle inequality to accelerate k-means.”，2003，ICML. Vol. 3.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかし、上述のＥｌｋａｎの手法は距離の下限値を格納するためにＯ（Ｎ×ｋ）の記憶容量を必要とする。このため、汎用の計算機を用いてＮが大きな値を持つビッグデータを大きなｋで分割することは困難である。
【００１５】
本発明は上記事情に鑑みてなされたものであり、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量でデータ点が所属するクラスタを高速に決定することができるクラスタリング装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、第１の発明に係るクラスタリング装置は、複数のデータ点をクラスタリングするクラスタリング装置であって、複数のデータ点の各々と、前記データ点を表す空間上の点であるピボットとの間の距離を記憶したピボットデータ点距離記憶部と、複数のクラスタの中心の各々と、前記ピボットとの間の距離を記憶したピボット中心距離記憶部と、前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、前記データ点が所属する前記クラスタを決定するクラスタリング部と、を含んで構成されている。
【００１７】
また、第２の発明に係るクラスタリング方法は、複数のデータ点の各々と、前記データ点を表す空間上の点であるピボットの各々との間の距離を記憶したピボットデータ点距離記憶部と、複数のクラスタの中心の各々と、前記ピボットとの間の距離を記憶したピボット中心距離記憶部と、クラスタリング部とを含み、前記複数のデータ点をクラスタリングするクラスタリング装置におけるクラスタリング方法であって、前記クラスタリング部が、前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、前記データ点が所属する前記クラスタを決定するステップを含んで構成されている。
【００１８】
また、前記クラスタリング部は、前記複数のデータ点の各々について、前記ピボットデータ点距離記憶部に記憶された、前記データ点と前記ピボットとの間の距離、及び前記ピボット中心距離記憶部に記憶された、前記複数のクラスタの中心の各々と前記ピボットとの間の距離に基づいて、距離の三角不等式を用いて、前記データ点が所属する前記クラスタを変更するか否かを判定し、前記データ点が所属する前記クラスタを変更すると判定された場合に、前記データ点が所属する前記クラスタを変更する所属変更判定部を含み、前記所属変更判定部によって前記複数のデータ点の各々について前記データ点が所属する前記クラスタを変更しないと判定されるまで、前記所属変更判定部による判定及び変更を繰り返すことにより、前記複数のデータの各々について、前記データ点が所属する前記クラスタを決定するようにすることができる。
【００１９】
また、第１又は第２の発明は、前記複数のデータ点、又は前記複数のクラスタの中心に基づいて、前記空間上の点から、前記ピボットを選択するピボット選択部を更に含むようにすることができる。
【００２０】
また、第３の発明に係るプログラムは、コンピュータを、本発明のクラスタリング装置の各部として機能させるためのプログラムである。
【００２１】
第４の発明に係るクラスタリング装置は、複数のデータ点をクラスタリングするクラスタリング装置であって、前記複数のデータ点の各々について、複数のクラスタの中心間の距離、又は前記データ点の所属する前記クラスタの決定に応じて前記クラスタの中心の位置が変更されたか否かに基づいて、前記データ点が所属する前記クラスタを決定するクラスタリング部を含んで構成されている。
第４の発明に係るクラスタリング装置によれば、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。
【発明の効果】
【００２２】
以上説明したように、本発明のクラスタリング装置、方法、及びプログラムによれば、複数のデータ点の各々について、ピボットデータ点距離記憶部に記憶された、データ点とピボットとの間の距離、及びピボット中心距離記憶部に記憶された、複数のクラスタの中心の各々とピボットとの間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる、という効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】第１の実施の形態に係るクラスタリング装置の構成を示すブロック図である。
【図２】ピボットを用いた距離計算の省略の概要を説明するための説明図である。
【図３】第１の実施の形態におけるデータ分割処理ルーチンの内容を示すフローチャートである。
【図４】第１の実施の形態におけるピボット選択処理ルーチンの内容を示すフローチャートである。
【図５】第１の実施の形態における第２ピボット選択処理ルーチンの内容を示すフローチャートである。
【図６】第１の実施の形態における第２ピボット選択処理ルーチンの内容を示すフローチャートである。
【図７】第１の実施の形態における所属変更判定処理ルーチンの内容を示すフローチャートである。
【図８】第１の実施の形態における所属変更判定処理ルーチンの内容を示すフローチャートである。
【図９】第２の実施の形態における第２ピボット選択処理ルーチンの内容を示すフローチャートである。
【図１０】第３の実施の形態に係るクラスタリング装置の構成を示すブロック図である。
【図１１】第３の実施の形態におけるデータ分割処理ルーチンの内容を示すフローチャートである。
【図１２】第３の実施の形態におけるピボット選択処理ルーチンの内容を示すフローチャートである。
【図１３】第４の実施の形態におけるピボット選択処理ルーチンの内容を示すフローチャートである。
【図１４】第５の実施の形態におけるピボット選択処理ルーチンの内容を示すフローチャートである。
【図１５】第５の実施の形態におけるピボット選択処理ルーチンの内容を示すフローチャートである。
【図１６】第６の実施の形態に係るクラスタリング装置の構成を示すブロック図である。
【図１７】第６の実施の形態に係るクラスタリング装置の処理の概要を示す概念図である。
【図１８】第６の実施の形態におけるデータ分割処理ルーチンの内容を示すフローチャートである。
【図１９】第６の実施の形態における所属変更判定処理ルーチンの内容を示すフローチャートである。
【図２０】第７の実施の形態に係るクラスタリング装置の構成を示すブロック図である。
【図２１】第７の実施の形態に係るクラスタリング装置の処理の概要を示す概念図である。
【図２２】第７の実施の形態におけるデータ分割処理ルーチンの内容を示すフローチャートである。
【図２３】第７の実施の形態における所属変更判定処理ルーチンの内容を示すフローチャートである。
【図２４】従来技術を説明するための説明図である。
【発明を実施するための形態】
【００２４】
以下、図面を参照して本発明の実施の形態を詳細に説明する。本発明の実施の形態は、複数のデータ点をクラスタリングするクラスタリング装置に本発明を適用させた場合を例に説明する。
【００２５】
＜概要＞
まず、第１〜第５の実施の形態の概要について説明する。第１〜第５の実施の形態は、ユークリッド空間上のＮ個のデータ点の集合Ｘと、集合Ｘを分割するクラスタの数ｋ（ｋ＜Ｎ）を入力として、集合Ｘをｋ個に分割し、ｋ個の集合Ｙｉ（ｉ＝１，２，...，ｋ）を出力するにあたり、次の２つの処理を行うことを特徴とする。第１〜第５の実施の形態では、データ点を表す空間上に存在する点であって、かつ当該空間上において移動しない点である不動点を用いて、複数のデータ点をクラスタリングする。第１〜第５の実施の形態では、不動点としてピボットを用いる場合を例に説明する。
【００２６】
１．本実施の形態に係るクラスタリング装置は、ユークリッド空間上に存在するピボットをｊ個（ｊ＜ｋ）選択し、ピボットの座標を記憶部に記憶させる処理を行う。ここで、ピボットとは、データ点を表す空間上の点である。なお、ピボットはデータ点と一致してもしなくともよい。また、本実施の形態では、複数のピボットを用いる場合を例に説明するが、ピボットは１つであってもよい。また、距離計算の省略（第１の実施の形態において後述する）の割合向上の点から、ピボットは以下の二つの性質を有することを望まれる。
【００２７】
（ア）ユークリッド空間中でデータ点の密な領域に存在すること。
（イ）同一の領域に複数のピボットが存在しないこと。
【００２８】
２．ピボットを用いて距離計算の不要な計算を省略しながら、ｋ個のクラスタの中心のうちでデータ点に最も近い中心を選出し、選出された中心を表す識別子を記憶部に記憶させる処理を行う。中心を表す識別子は各中心に対して付与した通し番号や記号であってもよいし、中心の座標を記憶した記憶部中の各中心座標の格納位置を示すパスやＵＲＬの文字列であってもよい。
【００２９】
［第１の実施の形態］
＜クラスタリング装置の構成＞
第１の実施の形態に係るクラスタリング装置１００は、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、後述する各処理ルーチンを実行するための情報提示プログラムを記憶したＲＯＭ（Read Only Memory）とを備えたコンピュータで構成されている。ＣＰＵがプログラムを、内部記憶装置であるＲＯＭから読み込んで実行することにより、コンピュータがクラスタリング装置１００として機能する。
【００３０】
クラスタリング装置１００には、ユークリッド空間上のＮ個のデータ点の集合Ｘと、集合Ｘを分割するクラスタの数ｋ（ｋ＜Ｎ）とが入力として与えられる。クラスタリング装置１００は、入力された集合Ｘを、ｋ個のクラスタに分割し、分割結果を出力する。
【００３１】
図１に示すように、クラスタリング装置１００は、機能的には、入力部１０と、演算部２０と、出力部５０とを含んだ構成で表すことができる。
【００３２】
入力部１０は、データ点の集合Ｘと、クラスタの数ｋとを受け付ける。
【００３３】
演算部２０は、クラスタリング部２２と、データ点座標記憶部２６と、中心座標記憶部２８と、ピボット座標記憶部３２と、中心ＩＤ記憶部３４と、ピボットデータ点距離記憶部３８と、ピボット中心距離記憶部４４と、分割結果処理部４８とを備えている。
【００３４】
クラスタリング部２２は、入力部１０によって受け付けたデータ点の集合Ｘに含まれる複数のデータ点の各々について、当該データ点と複数のピボットの各々との間の距離、及び複数のクラスタの中心の各々と複数のピボットの各々との間の距離とに基づいて、当該データ点が所属するクラスタを決定する。なお、ピボットとは、データ点を表すユークリッド空間上の点である。クラスタリング部２２は、データ・分割数処理部２４と、ピボット選択部３０と、ピボットデータ点距離計算部３６と、中心座標更新部４０と、ピボット中心距離計算部４２と、所属変更判定部４６とを備えている。
【００３５】
データ・分割数処理部２４は、入力部１０によって受け付けたユークリッド空間上のＮ個のデータ点の集合Ｘと、集合Ｘを分割するクラスタの数ｋ（ｋ＜Ｎ）とに基づいて、次の処理を行う。
データ・分割数処理部２４は、入力部１０によって受け付けた集合Ｘに含まれる全てのデータ点のユークリッド座標を、データ点座標記憶部２６に記憶させる。また、データ・分割数処理部２４は、入力部１０によって受け付けたクラスタの数ｋに基づいて、ｋ個のクラスタの各々について、当該クラスタの中心の仮の中心座標（ランダムに決めてもよいし、全て原点でもよい）を中心座標記憶部２８に記憶させる。
【００３６】
データ点座標記憶部２６には、データ・分割数処理部２４によって格納された集合Ｘに含まれる全てのデータ点ｘのユークリッド座標が記憶される。
【００３７】
中心座標記憶部２８には、データ・分割数処理部２４によって格納されたｋ個のクラスタの各々についてのクラスタの中心の仮の中心座標、後述するピボット選択部３０によって得られたｋ個のクラスタの各々についてのクラスタの中心の中心座標、又は後述する中心座標更新部４０によって更新されたｋ個のクラスタの各々についてのクラスタの中心の中心座標が記憶される。
【００３８】
ピボット選択部３０は、データ点座標記憶部２６に記憶された複数のデータ点に基づいて、複数のピボットを選択する。具体的には、ピボット選択部３０は、データ点座標記憶部２６に記憶されたデータ点ｘの座標から、ｊ個（ｊ＜ｋ）のピボットを選択し、選択されたピボットの座標をピボット座標記憶部３２に記憶させる。なお、ピボットの個数ｊは、予め定められている。
【００３９】
第１の実施の形態では、複数のデータ点から複数のクラスタの中心を決定し、複数のクラスタの中心に基づいて、データ点を表す空間上の点から、複数のピボットを選択する場合を例に説明する。ピボット選択部３０は、以下の処理を行い、ピボットを選択する。なお、既に選択されたピボットの集合を既存ピボット集合という。
【００４０】
第１の実施の形態では、ピボット選択部３０は、まず、ピボットの選択処理が早期に終了するように、後述する終了条件（下記（１）にて後述）を設定したＬｌｏｙｄ法（上記非特許文献１を参照。）と同様の手順を集合Ｘに適用し、適用した結果得られたｋ個の中心のうち、所属するデータ点の数が最大の中心を最初のピボットとして選択する。
【００４１】
次に、ピボット選択部３０は、ピボットとして選択されていないクラスタの中心の各々について、当該クラスタに所属するデータ点の各々に対し、既存ピボット集合を用いて距離の三角不等式に従って距離計算の省略（省略方法については後述）が行えていない回数を求め、ピボットとして選択されていないクラスタの中心から、距離計算の省略が行えていない回数が多い中心を、ピボットとして再帰的にｊ−１個選択する。そして、ピボット選択部３０は、選ばれたｊ個のピボットの座標を、ピボット座標記憶部３２に記憶させる。第１の実施の形態における具体的なピボットの選択方法は以下の（１）〜（３）に示す通りである。
【００４２】
（１）ピボット選択部３０は、データ点の集合Ｘに対し、Ｌｌｏｙｄ法と同様の手順を分割数ｋで１反復だけ適用する。第１の実施の形態では、ピボットの選択処理を早期で終了させるための終了条件として反復回数を１回としたが、複数回であってもよいし、中心座標の移動距離に閾値を設けてそれを下回ったときに、終了とする終了条件としてもよい。
【００４３】
ここで、データ点の集合Ｘに対しＬｌｏｙｄ法と同様の手順を分割数ｋで１反復だけ適用させる場合には、まず、データ点の集合Ｘの全データ点の所属を、それぞれランダムにｋ個の中心に割り振る。そして、複数のクラスタの中心の各々について、当該クラスタの中心の初期座標を、当該クラスタの中心に所属しているデータ点の重心に設定する。そして、データ点の集合Ｘの各データ点について、ｋ個のクラスタの中心と当該データ点との距離を計算し、最も距離が近い中心に当該データ点の所属を変更する。そして、ピボット選択部３０は、データ点の集合Ｘの複数のデータ点の各々について、当該データ点が所属するクラスタの中心のＩＤを、中心ＩＤ記憶部３４に記憶させる。
【００４４】
（２）ピボット選択部３０は、上記（１）で得られたｋ個の中心のうち、所属するデータ点の数が最も大きい中心の初期座標を最初のピボットとし、最初のピボットの座標をピボット座標記憶部３２に記憶させる。
【００４５】
（３）ピボット選択部３０は、以降、２個目からｊ個目のピボットについて、ピボットとして選択されていない中心のうち、既存ピボット集合を用いて距離の三角不等式によって「距離計算の省略が行えていない回数が多い中心」をピボットとして選択する。第１の実施の形態では、例えば、２個目からｊ個目のピボットとして、以下の式（１）を満たす中心ｃを再帰的にピボットとして選択し、選択された中心ｃの座標をピボット座標記憶部３２に記憶させる。
【００４６】
【数３】
2016042237.tif 000005
【００４７】
ただし、Ｃ，Ｐはそれぞれ、ｋ個の中心の集合、既存ピボット集合である。上記（３）の処理は、各中心ｃＡについて、ｃｏｕｎｔ（ｃＡ）を０に初期化した後、下記疑似コードの手順で計算される（ただし、Ｘ（ｃＡ）は中心ｃＡに所属するデータ点の集合である。）。
【００４８】
ｆｏｒ  ｘ∈Ｘ（ｃＡ）
ｆｏｒ  ｃＢ∈Ｃ＼｛ｃＡ｝
ｆｌａｇ＝０
ｆｏｒ  ｐ∈Ｐ
ｉｆ  ｄ（ｘ，ｃＡ）＜｜ｄ（ｐ，ｃＢ）−ｄ（ｐ，ｘ）｜
ｆｌａｇ＝１
ｂｒｅａｋ
ｉｆ  ｆｌａｇ＝０
ｃｏｕｎｔ（ｃＡ）＝ｃｏｕｎｔ（ｃＡ）＋１
ｃｏｕｎｔ（ｃＢ）＝ｃｏｕｎｔ（ｃＢ）＋１
【００４９】
ピボット座標記憶部３２には、ピボット選択部３０によって選択された複数のピボットの座標が記憶される。
【００５０】
中心ＩＤ記憶部３４には、データ点の集合Ｘの複数のデータ点の各々について、当該データ点が所属するクラスタの中心のＩＤ番号が記憶される。
【００５１】
ピボットデータ点距離計算部３６は、データ点座標記憶部２６に記憶された複数のデータ点の座標と、ピボット座標記憶部３２に記憶された複数のピボットの座標とを取得し、複数のデータ点の各々と複数のピボットの各々との間の距離を計算する。具体的には、ピボットデータ点距離計算部３６は、全てのピボットとデータ点との組み合わせについて、ピボットとデータ点とのユークリッド距離を計算し、ピボットデータ点距離記憶部３８に記憶させる。
【００５２】
ピボットデータ点距離記憶部３８には、全てのデータ点とピボットとの組み合わせについて、複数のデータ点の各々と複数のピボットの各々との間の距離が記憶されている。
【００５３】
中心座標更新部４０は、複数のクラスタの中心の各々について、当該中心に所属しているデータ点を中心ＩＤ記憶部３４から読み込み、当該中心に所属しているデータ点を調べる。そして、中心座標更新部４０は、複数のクラスタの中心の各々について、当該中心に所属するデータ点の座標をデータ点座標記憶部２６から読み込み、読み込まれた複数のデータ点の重心を算出し、算出された重心を、当該中心の新たな座標として中心座標記憶部２８に記憶させる。
【００５４】
ピボット中心距離計算部４２は、中心座標記憶部２８に記憶された複数のクラスタの中心の座標と、ピボット座標記憶部３２に記憶された複数のピボットの座標とを取得し、複数のクラスタの中心の各々と、複数のピボットの各々との間の距離を計算する。具体的には、ピボット中心距離計算部４２は、全ての中心とピボットとの組み合わせについて、中心とピボットとのユークリッド距離を計算し、ピボット中心距離記憶部４４に記憶させる。
【００５５】
ピボット中心距離記憶部４４は、全ての中心とピボットとの組み合わせについて、複数のクラスタの中心の各々と、複数のピボットの各々との間の距離が記憶されている。
【００５６】
所属変更判定部４６は、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、当該データ点と複数のピボットの各々との間の距離、及びピボット中心距離計算部４２に記憶された、複数のクラスタの中心の各々と複数のピボットの各々との間の距離に基づいて、距離の三角不等式を用いて、データ点が所属するクラスタを変更するか否かを判定する。そして、所属変更判定部４６は、データ点が所属するクラスタを変更すると判定された場合には、データ点が所属するクラスタを変更する。
また、所属変更判定部４６は、複数のデータ点の各々について当該データ点が所属するクラスタを変更しないと判定されるまで、所属変更判定部４６による判定及び変更を繰り返すことにより、複数のデータの各々について、当該データ点が所属するクラスタを決定する。
【００５７】
具体的には、所属変更判定部４６は、データ点の集合Ｘの全てのデータ点について、下記の手順（１）〜（４）に従って、当該データ点と最も近い距離に存在する中心に、当該データ点を所属させる。この際、一つでも所属する中心に変更があったデータ点が存在した場合、中心座標更新部４０に戻る。一方、一つも存在しなかった場合、分割結果処理部４８に進む。
【００５８】
（１）データ点ｘの所属する中心ｃＸを中心ＩＤ記憶部３４から取得する。
【００５９】
（２）データ点ｘの座標と、当該データ点ｘが所属する中心ｃＸの座標とを、それぞれデータ点座標記憶部２６と中心座標記憶部２８とから読み込む。
【００６０】
（３）データ点ｘと中心ｃＸとの距離ｄ（ｘ，ｃＸ）を算出する。
【００６１】
（４）中心ｃＸ以外のすべての中心ｃＹについて下記を行う。
【００６２】
１．全てのピボットｐについて下記を行う。
【００６３】
（ア）ピボットｐとデータ点ｘとの距離ｄ（ｐ，ｘ）をピボットデータ点距離記憶部３８から読み込み、ピボットｐと中心ｃＹとの距離ｄ（ｐ，ｃＹ）をピボット中心距離記憶部４４から読み込む。
【００６４】
（イ）｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜を算出する。（距離の三角不等式より、これはｄ（ｘ，ｃＹ）の距離の下限である。）
【００６５】
（ウ）ｄ（ｘ，ｃＸ）と｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜とを比較し、ｄ（ｘ，ｃＸ）＜｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜であればｄ（ｘ，ｃＹ）を計算するまでもなくｄ（ｘ，ｃ）＜ｄ（ｘ，ｃＹ）であるので、所属の変更は起こらない。次の中心ｃＹについて（４）１．に進む。
【００６６】
２．ｃＹの座標を中心座標記憶部２８から読み込み、ｄ（ｘ，ｃＹ）を算出する。
【００６７】
３. ｄ（ｘ，ｃＸ）とｄ（ｘ，ｃＹ）との距離の大きさを比べ、ｄ（ｘ，ｃＸ）＞ｄ（ｘ，ｃＹ）であれば、ｘの所属をｃＹに変更し、中心ＩＤ記憶部３４に記憶させる。
【００６８】
図２に、所属変更判定部４６による処理の概念図を示す。図２に示すように、本発明の実施の形態では、距離計算の省略を判定するにあたり、ｄ（ｐ，ｘ）とｄ（ｐ，ｃＹ）とについて、全てのピボットとデータ点及び中心との組み合わせ数だけ記憶している。記憶する個数はｄ（ｐ，ｘ）、ｄ（ｐ，ｃＹ）それぞれについてｊ×Ｎ個，ｊ×ｋ個の計ｊ×（Ｎ＋ｋ）個である。一方、Ｅｌｋａｎの方法は距離計算の省略用に全てのデータ点と中心との組み合わせについて「データ点と中心との距離の下限」を計Ｎ×ｋ個記憶していた。Ｎ，ｋがともに大きな数である場合、本発明の実施の形態は、ピボットの数ｊがクラスタの数ｋより小さいため、記憶個数についてＥｌｋａｎの方法に比べて効率的になる。なお、ピボットの数ｊがクラスタの数ｋに比べ十分小さいほど、少ない記憶容量で済むが、距離計算の省略率は低くなる。また、ピボットの数ｊがクラスタの数ｋに近づくほど、大きな記憶容量が必要となり、距離計算の省略率は高くなる。そのため、ピボットの数ｊは、記憶容量と距離計算の省略率とのかねあいに基づき、決定してもよい。
【００６９】
分割結果処理部４８は、複数のクラスタの中心ｃｉ（ｉ＝１，２，...，ｋ）の各々について、当該中心に所属するデータ点を中心ＩＤ記憶部３４から取得する。そして、分割結果処理部４８は、複数のクラスタの中心の各々について、当該中心に所属するデータ点の集合Ｙｉ（ｉ＝１，２，...，ｋ）を出力する。
【００７０】
出力部５０は、分割結果処理部４８によって出力されたデータ点の集合Ｙｉ（ｉ＝１，２，...，ｋ）を結果として出力する。
【００７１】
＜クラスタリング装置１００の作用＞
次に、本実施の形態に係るクラスタリング装置１００の作用について説明する。クラスタリング装置１００にデータ点の集合Ｘとクラスタの数ｋとが入力されると、図３に示すデータ分割処理ルーチンが実行される。
【００７２】
＜データ分割処理ルーチン＞
ステップＳ１００において、入力部１０によって、データ点の集合Ｘと、クラスタの数ｋとを受け付ける。
【００７３】
次に、ステップＳ１０２において、データ・分割数処理部２４によって、上記ステップＳ１００で受け付けた集合Ｘに含まれる全てのデータ点のユークリッド座標を、データ点座標記憶部２６に記憶させる。また、データ・分割数処理部２４によって、上記ステップＳ１００で受け付けたクラスタの数ｋに基づいて、ｋ個のクラスタの各々について、当該クラスタの中心の仮の中心座標を中心座標記憶部２８に記憶させる。
【００７４】
ステップＳ１０４において、ピボット選択部３０によって、ピボット選択処理が行われる。ステップＳ１０４は、図４に示すピボット選択処理ルーチンによって実現される。
【００７５】
＜ピボット選択処理ルーチン＞
ステップＳ２００において、データ点の集合Ｘの複数のデータ点の各々について、データ点の所属を、ランダムにクラスタの中心に割り振る。
【００７６】
ステップＳ２０２において、複数のクラスタの中心の各々について、中心の初期座標を、当該中心に所属しているデータ点の重心に設定し、中心座標記憶部２８に記憶させる。
【００７７】
ステップＳ２０４において、データ点の集合Ｘの複数のデータ点の各々について、ｋ個の中心と当該データ点との距離を計算し、最も距離が近い中心に当該データ点の所属を変更する。また、データ点の集合Ｘの複数のデータ点の各々について、当該データ点が所属するクラスタの中心のＩＤを、中心ＩＤ記憶部３４に記憶させる。
【００７８】
ステップＳ２０６において、上記ステップＳ２０２で得られたｋ個の中心の初期座標のうち、所属するデータ点の数が最も大きい中心の初期座標を最初のピボットとし、最初のピボットの座標をピボット座標記憶部３２に記憶させる。
【００７９】
ステップＳ２０８において、ピボット選択部３０によって、第２ピボット選択処理が行われる。ステップＳ２０８は、図５及び図６に示す第２ピボット選択処理ルーチンによって実現される。
【００８０】
＜第２ピボット選択処理ルーチン＞
ステップＳ３００において、全てのクラスタの中心ｃについて、ｃｏｕｎｔ（ｃ）を初期化する。なお、中心の集合Ｃから既存ピボット集合Ｐを除いた集合に含まれる中心ｃについて、ｃｏｕｎｔ（ｃ）を初期化してもよい。
【００８１】
ステップＳ３０２において、上記ステップＳ２０６又は後述するステップＳ３３２でピボットとして選択された中心とは異なる中心ｃＡを設定する。
【００８２】
ステップＳ３０４において、データ点の集合Ｘから、上記ステップＳ３０２で設定された中心ｃＡに所属する１つのデータ点ｘを設定する。
【００８３】
ステップＳ３０６において、上記ステップＳ３０４で設定されたデータ点ｘが所属していない中心ｃＢを設定する。
【００８４】
ステップＳ３０８において、既存ピボット集合Ｐから、１つのピボットｐを設定する。
【００８５】
ステップＳ３１０において、ｆｌａｇに０を代入する。
【００８６】
ステップＳ３１２において、上記ステップＳ３０４で設定されたデータ点ｘと当該データ点ｘが所属する中心ｃＡとの間の距離ｄ（ｘ，ｃＡ）を算出する。また、上記ステップＳ３０８で設定されたピボットｐと上記ステップＳ３０６で設定された中心ｃＢとの間の距離ｄ（ｐ，ｃＢ）を算出する。そして、上記ステップＳ３０８で設定されたピボットｐと上記ステップＳ３０４で設定されたデータ点ｘとの間の距離ｄ（ｐ，ｘ）を算出する。
【００８７】
ステップＳ３１４において、上記ステップＳ３１２で算出された各距離に基づいて、ｄ（ｘ，ｃＡ）＜｜ｄ（ｐ，ｃＢ）−ｄ（ｐ，ｘ）｜であるか否かを判定する。ｄ（ｘ，ｃＡ）＜｜ｄ（ｐ，ｃＢ）−ｄ（ｐ，ｘ）｜である場合には、距離計算の省略が行えていると判定し、ステップＳ３１６へ進む。一方、ｄ（ｘ，ｃＡ）＜｜ｄ（ｐ，ｃＢ）−ｄ（ｐ，ｘ）｜でない場合には、距離計算の省略が行えていないと判定し、ステップＳ３１８へ移行する。
【００８８】
ステップＳ３１６において、ｆｌａｇに１を代入する。
【００８９】
ステップＳ３１８において、既存ピボット集合に含まれる全てのピボットについて、上記ステップＳ３０８〜Ｓ３１４の各処理を実行したか否かを判定する。既存ピボット集合に含まれる全てのピボットについて、上記ステップＳ３０８〜Ｓ３１４の各処理を実行した場合には、ステップＳ３２０へ進む。一方、上記ステップＳ３０８〜Ｓ３１４の各処理を実行していないピボットが存在する場合には、ステップＳ３０８へ戻る。
【００９０】
ステップＳ３２０において、ｆｌａｇは０であるか否かを判定する。ｆｌａｇが０である場合には、ステップＳ３２２へ移行する。一方、ｆｌａｇが０でない場合には、ステップＳ３０６へ戻る。
【００９１】
ステップＳ３２２において、ｃｏｕｎｔ（ｃＡ）を１インクリメントする。
【００９２】
ステップＳ３２４において、ｃｏｕｎｔ（ｃＢ）を１インクリメントする。
【００９３】
ステップＳ３２６において、上記ステップＳ３０４で設定したデータ点ｘが所属していない中心の全てについて、上記ステップＳ３０６〜Ｓ３２４の各処理を実行したか否かを判定する。データ点ｘが所属していない中心の全てについて、上記ステップＳ３０６〜Ｓ３２４の各処理を実行した場合には、ステップＳ３２８へ進む。一方、上記ステップＳ３０６〜Ｓ３２４の各処理を実行していない中心が存在する場合には、ステップＳ３０６へ戻る。
【００９４】
ステップＳ３２８において、データ点の集合Ｘに含まれる全てのデータ点について、上記ステップＳ３０４〜ステップＳ３２６の各処理を実行したか否かを判定する。データ点の集合Ｘに含まれる全てのデータ点について、上記ステップＳ３０４〜ステップＳ３２６の各処理を実行した場合には、ステップＳ３３０へ進む。一方、上記ステップＳ３０４〜ステップＳ３２６の各処理を実行していないデータ点が存在する場合には、ステップＳ３０４へ戻る。
【００９５】
ステップＳ３３０において、ピボットとして選択されていない中心の全てについて、上記ステップＳ３０２〜Ｓ３２８の各処理を実行したか否かを判定する。ピボットとして選択されていない中心の全てについて、上記ステップＳ３０２〜Ｓ３２８の各処理を実行した場合には、ステップＳ３３２へ進む。一方、上記ステップＳ３０２〜Ｓ３２８の各処理を実行していない中心が存在する場合には、ステップＳ３０２へ戻る。
【００９６】
ステップＳ３３２において、上記式（１）を満たす中心ｃを、ピボットとして選択し、選択されたピボットの座標を、ピボット座標記憶部３２に記憶させる。
【００９７】
ステップＳ３３４において、ｊ−１個のピボットが選択されたか否かを判定する。ｊ−１個のピボットが選択された場合には、第２ピボット選択処理ルーチンを終了する。一方、ｊ−１個のピボットが選択されていない場合には、ステップＳ３００へ戻る。
【００９８】
次に、データ分割処理ルーチンに戻り、ステップＳ１０６において、ピボットデータ点距離計算部３６によって、上記ステップＳ１０２でデータ点座標記憶部２６に記憶された複数のデータ点の座標と、上記ステップＳ３２２でピボット座標記憶部３２に記憶された複数のピボットの座標とを取得し、複数のデータ点の各々と複数のピボットの各々との間の距離を計算する。そして、ピボットデータ点距離計算部３６によって、全てのピボットとデータ点との組み合わせについて、計算されたピボットとデータ点との距離を、ピボットデータ点距離記憶部３８に記憶させる。
【００９９】
ステップＳ１０８において、中心座標更新部４０によって、複数のクラスタの中心の各々について、当該中心に所属しているデータ点を中心ＩＤ記憶部３４から読み込む。そして、中心座標更新部４０によって、複数のクラスタの中心の各々について、当該中心に所属するデータ点の座標をデータ点座標記憶部２６から読み込み、読み込まれた複数のデータ点の重心を算出し、算出された重心を、当該中心の新たな座標として中心座標記憶部２８に記憶させる。
【０１００】
ステップＳ１１０において、ピボット中心距離計算部４２によって、上記ステップＳ１０８で中心座標記憶部２８に記憶された複数のクラスタの中心の座標と、上記ステップＳ３２２でピボット座標記憶部３２に記憶された複数のピボットの座標とを取得し、複数のクラスタの中心の各々と、複数のピボットの各々との間の距離を計算する。具体的には、ピボット中心距離計算部４２は、全ての中心とピボットとの組み合わせについて、中心とピボットとのユークリッド距離を計算し、ピボット中心距離記憶部４４に記憶させる。
【０１０１】
ステップＳ１１２において、所属変更判定部４６によって、所属変更判定処理が行われる。ステップＳ１１２は、図７及び図８に示す所属変更判定処理ルーチンによって実現される。
【０１０２】
＜所属変更判定処理ルーチン＞
ステップＳ４００において、データ点の集合Ｘから、１つのデータ点ｘを設定する。
【０１０３】
ステップＳ４０２において、上記ステップＳ４００で設定されたデータ点ｘの所属する中心ｃＸを中心ＩＤ記憶部３４から取得する。
【０１０４】
ステップＳ４０４において、上記ステップＳ４００で設定されたデータ点ｘの座標を、データ点座標記憶部２６から取得する。また、上記ステップＳ４０２で取得された中心ｃＸの座標を中心座標記憶部２８から取得する。
【０１０５】
ステップＳ４０６において、上記ステップＳ４０４で取得されたデータ点ｘの座標及び中心ｃＸの座標に基づいて、データ点ｘと中心ｃＸとの間の距離ｄ（ｘ，ｃＸ）を算出する。
【０１０６】
ステップＳ４０８において、上記ステップＳ４０２で取得された中心ｃＸとは異なる中心ｃＹを設定する。
【０１０７】
ステップＳ４１０において、既存ピボット集合Ｐから、１つのピボットｐを設定する。
【０１０８】
ステップＳ４１２において、上記ステップＳ４００で設定されたデータ点ｘと、上記ステップＳ４１０で設定されたピボットｐとの距離ｄ（ｐ，ｘ）を、ピボットデータ点距離記憶部３８から取得する。
【０１０９】
ステップＳ４１４において、上記ステップＳ４０８で設定された中心ｃＹと、上記ステップＳ４１０で設定されたピボットｐとの距離ｄ（ｐ，ｃＹ）を、ピボット中心距離記憶部４４から取得する。
【０１１０】
ステップＳ４１６において、上記ステップＳ４１２で取得されたｄ（ｐ，ｘ）と、上記ステップＳ４１４で取得されたｄ（ｐ，ｃＹ）とに基づいて、｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜を算出する。
【０１１１】
ステップＳ４１８において、上記ステップＳ４０６で算出されたｄ（ｘ，ｃＸ）と、上記ステップＳ４１６で算出された｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜とに基づいて、ｄ（ｘ，ｃＸ）＜｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜を満たすか否かを判定する。ｄ（ｘ，ｃＸ）＜｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜を満たす場合には、ステップＳ４０８へ戻る。一方、ｄ（ｘ，ｃＸ）＜｜ｄ（ｐ，ｘ）−ｄ（ｐ，ｃＹ）｜を満たさない場合には、ステップＳ４２０へ進む。
【０１１２】
ステップＳ４２０において、上記ステップＳ４０８で取得された中心ｃＹの座標を、中心座標記憶部２８から取得する。
【０１１３】
ステップＳ４２２において、上記ステップＳ４０４で取得されたデータ点ｘの座標と、上記ステップＳ４２０で取得されたた中心ｃＹの座標とに基づいて、データ点ｘと中心ｃＹとの間の距離ｄ（ｘ，ｃＹ）を算出する。
【０１１４】
ステップＳ４２４において、上記ステップＳ４０６で算出されたｄ（ｘ，ｃＸ）と、上記ステップＳ４２２で算出されたｄ（ｘ，ｃＹ）とに基づいて、ｄ（ｘ，ｃＸ）＞ｄ（ｘ，ｃＹ）を満たすか否かを判定する。ｄ（ｘ，ｃＸ）＞ｄ（ｘ，ｃＹ）を満たす場合には、ステップＳ４２６へ進む。一方、ｄ（ｘ，ｃＸ）＞ｄ（ｘ，ｃＹ）を満たさない場合には、ステップＳ４２８へ移行する。
【０１１５】
ステップＳ４２６において、上記ステップＳ４００で設定されたデータ点ｘの所属を、上記ステップＳ４０８で設定された中心ｃＹに対応するクラスタへ変更し、中心ＩＤ記憶部３４に記憶させる。
【０１１６】
ステップＳ４２８において、上記ステップＳ４０２で取得された中心ｃＸ以外の全ての中心ｃＹについて、上記ステップＳ４０８〜Ｓ４２６の各処理を実行したか否かを判定する。全ての中心ｃＹについて、上記ステップＳ４０８〜Ｓ４２６の各処理を実行した場合には、ステップＳ４３０へ進む。一方、上記ステップＳ４０８〜Ｓ４２６の各処理を実行していない中心ｃＹが存在する場合には、ステップＳ４０８へ戻る。
【０１１７】
ステップＳ４３０において、データ点の集合Ｘに含まれる全てのデータ点について、上記ステップＳ４００〜Ｓ４２８の各処理を実行したか否かを判定する。データ点の集合Ｘに含まれる全てのデータ点について、上記ステップＳ４００〜Ｓ４２８の各処理を実行した場合には、所属変更判定処理ルーチンを終了する。一方、上記ステップＳ４００〜Ｓ４２８の各処理を実行していないデータ点が存在する場合には、ステップＳ４００へ戻る。
【０１１８】
次に、データ分割処理ルーチンに戻り、ステップＳ１１４において、上記ステップＳ１１２でクラスタの変更があったデータ点が存在するか否かを判定する。クラスタの変更があったデータ点が存在しない場合には、ステップＳ１１６へ進む。一方、クラスタの変更があったデータ点が存在する場合には、ステップＳ１０８へ戻る。
【０１１９】
ステップＳ１１６において、分割結果処理部４８によって、複数のクラスタの中心ｃｉ（ｉ＝１，２，...，ｋ）の各々について、当該中心に所属するデータ点を中心ＩＤ記憶部３４から取得する。そして、分割結果処理部４８によって、複数のクラスタの中心の各々について、当該中心に所属するデータ点の集合Ｙｉ（ｉ＝１，２，...，ｋ）を出力する。
【０１２０】
ステップＳ１１８において、出力部５０によって、分割結果処理部４８によって出力されたデータ点の集合Ｙｉ（ｉ＝１，２，...，ｋ）を結果として出力して、データ分割処理ルーチンを終了する。
【０１２１】
以上のように、ユーザは、本発明の実施の形態に係るクラスタリング装置を用いて、ユークリッド空間上のＮ個のデータ点の集合Ｘと、集合Ｘを分割するクラスタの数ｋ（ｋ＜Ｎ）を入力し、ｋ個の集合Ｙｉ（ｉ＝１，２，...，ｋ）を出力として得ることができる。
【０１２２】
以上説明したように、第１の実施の形態に係るクラスタリング装置によれば、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点と複数のピボットの各々との間の距離、及びピボット中心距離記憶部４４に記憶された、複数のクラスタの中心の各々と複数のピボットの各々との間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、距離計算の省略が行えていない回数が多い中心をピボットとして選択することにより、上述したピボットとして望まれる性質「（イ）同一の領域に複数のピボットが存在しないこと。」を満たしやすいピボットが選択される。
【０１２３】
また、データ点の数Ｎとデータ点の分割数ｋが共に大きい場合に高速にｋ−ｍｅａｎｓクラスタリングを実行することができる。大規模データは多数のクラスタから形成される可能性が高いため、Ｎ，ｋがともに大きな場合に高速にｋ−ｍｅａｎｓクラスタリングを実行できることは重要である。
【０１２４】
また、データ点の数Ｎと、データ点の分割数ｋがともに大きな数である場合、記憶個数については、上記非特許文献２のＥｌｋａｎの方法に比べて効率的になる。
【０１２５】
また、本実施の形態は、データ点とクラスタ中心の経由点であるピボットを用いることを特徴とする。Ｎをデータ点の数、ｋをクラスタ数、ｊをピボット数とし、ｊ＜ｋ＜Ｎとする。クラスタリング手法の１つであるＥｌｋａｎ法は、Ｏ（Ｎ×ｋ）の記憶領域を必要とする。一方、本実施の形態の手法は、Ｏ（（Ｎ＋ｋ）×ｊ）の記憶領域を必要とする。
【０１２６】
例えば、データ点数を１つ記憶するのに８バイトが必要（ｄｏｕｂｌｅ型を想定）で、データ点数が１０億個であり、１，０００個のクラスタに分割しようとすると、Ｅｌｋａｎ法では８テラバイトのメモリが必要だが、ピボットの個数を１０個とすると本実施の形態の手法では８０ギガバイトのメモリで済む。これにより、これまでＥｌｋａｎ法が現実的には取り扱えなかった大規模なデータを、本実施の形態の手法は取り扱うことができる。
【０１２７】
本実施の形態の手法がこのような効果を生み出すことができるのは、ピボットを導入したためである。Ｅｌｋａｎ法と本実施の形態の手法の両方とも、距離計算を省略することにより計算時間の短縮を図っている。Ｅｌｋａｎ法は、データ点と移動前のクラスタ中心と移動後のクラスタ中心の３点間について、距離の三角不等式を用いて距離計算の省略を図っている。これに対し本実施の形態の手法は、データ点とクラスタ中心とピボットの３点間について、距離の三角不等式を用いて距離計算の省略を図る。この工夫により、上述のようなメモリ節減の効果が生み出される。
【０１２８】
［第２の実施の形態］
次に、本発明の第２の実施の形態について説明する。なお、第２の実施の形態に係るクラスタリング装置の構成は、第１の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１２９】
第２の実施の形態では、クラスタの中心とデータ点との間の距離の下限と、クラスタの中心とデータ点との間の実距離との誤差が大きい中心を、ピボットとして選択する点が、第１の実施の形態と異なっている。
【０１３０】
上記第１の実施の形態では、２個目からｊ個目のピボットは、ピボットに選ばれていない中心のうち、既存のピボットを用いて距離の三角不等式によって「距離計算の省略が行えていない回数が多い中心」をピボットとして採用したが、第２の実施の形態では「距離の三角不等式によって得られる中心とデータ点との距離の下限と実距離との誤差が大きい中心」をピボットとして選択する。
【０１３１】
＜クラスタリング装置の構成＞
第２の実施の形態に係るクラスタリング装置のピボット選択部３０は、上記第１の実施の形態と同様の手法により、最初のピボットを選択する。ピボット選択部３０は、２個目からｊ個目のピボットについて、複数のデータ点の各々について、データ点と当該データ点が所属するクラスタの中心との距離と、ピボットとデータ点との距離と、ピボットとデータ点が所属するクラスタの中心との距離とに基づいて、以下の式（２）を満たす中心ｃを再帰的にピボットとして選択する。
【０１３２】
【数４】
2016042237.tif 000006
【０１３３】
＜クラスタリング装置の作用＞
次に、第２の実施の形態に係るクラスタリング装置の作用について説明する。第２の実施の形態に係るクラスタリング装置では、上記図３に示すデータ分割処理ルーチンと同様の処理ルーチンが実行される。
【０１３４】
なお、以下の処理における「ｅｒｒｏｒ（ｃ）」は、上記式（２）における
【０１３５】
【数５】
2016042237.tif 000007
【０１３６】
に対応する。
【０１３７】
データ分割処理ルーチンのステップＳ１０４において、ピボット選択部３０によって、ピボット選択処理が行われる。ステップＳ１０４は、上記図４に示すピボット選択処理ルーチンによって実現される。
【０１３８】
ピボット選択処理ルーチンのステップＳ２０８において、ピボット選択部３０によって、第２ピボット選択処理が行われる。ステップＳ２０８は、図９に示す第２ピボット選択処理ルーチンによって実現される。
【０１３９】
＜第２ピボット選択処理ルーチン＞
ステップＳ５００において、１つのクラスタの中心ｃを設定する。
【０１４０】
ステップＳ５０２において、上記ステップＳ５００で設定されたクラスタの中心ｃに対するｅｒｒｏｒ（ｃ）に０を代入する。
【０１４１】
ステップＳ５０４において、上記ステップＳ５００で設定された中心ｃに所属する１つのデータ点ｘを設定する。
【０１４２】
ステップＳ５０６において、既存ピボット集合に含まれるピボットｐの各々について、ｄ（ｘ，ｃ）−｜ｄ（ｐ，ｃ）−ｄ（ｐ，ｘ）｜の値を算出し、算出された値の各々のうち、最小となるｄ（ｘ，ｃ）−｜ｄ（ｐ，ｃ）−ｄ（ｐ，ｘ）｜の値を選択する。
【０１４３】
ステップＳ５０８において、上記ステップＳ５０２で初期化されたｅｒｒｏｒ（ｃ）又は前回の本ステップＳ５０８で更新されたｅｒｒｏｒ（ｃ）に、上記ステップＳ５０６で選択されたｄ（ｘ，ｃ）−｜ｄ（ｐ，ｃ）−ｄ（ｐ，ｘ）｜の最小値を加算して、ｅｒｒｏｒ（ｃ）を更新する。
【０１４４】
ステップＳ５１０において、上記ステップＳ５００で設定された中心ｃに所属する全てのデータ点について、上記ステップＳ５０４〜Ｓ５０８の各処理を実行したか否かを判定する。上記ステップＳ５００で設定された中心ｃに所属する全てのデータ点について、上記ステップＳ５０４〜Ｓ５０８の各処理を実行した場合には、ステップＳ５１２へ進む。一方、上記ステップＳ５０４〜Ｓ５０８の各処理を実行していないデータ点が存在する場合には、ステップＳ５０４へ戻る。
【０１４５】
ステップＳ５１２において、全てのクラスタの中心について上記ステップＳ５００〜Ｓ５１０の各処理を実行したか否かを判定する。全てのクラスタの中心について上記ステップＳ５００〜Ｓ５１０の各処理を実行した場合には、ステップＳ５１４へ進む。一方、上記ステップＳ５００〜Ｓ５１０の各処理を実行していないクラスタの中心が存在する場合には、ステップＳ５００へ戻る。
【０１４６】
ステップＳ５１４において、上記式（２）を満たす中心ｃを、ピボットとして選択し、選択されたピボットの座標を、ピボット座標記憶部３２に記憶させる。
【０１４７】
ステップＳ５１６において、ｊ−１個のピボットが選択されたか否かを判定する。ｊ−１個のピボットが選択された場合には、第２ピボット選択処理ルーチンを終了する。一方、ｊ−１個のピボットが選択されていない場合には、ステップＳ５００へ戻る。
【０１４８】
以上説明したように、第２の実施の形態に係るクラスタリング装置によれば、距離の三角不等式によって得られる中心とデータ点との間の距離の下限と実距離との差が大きい中心をピボットとして選択し、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点と複数のピボットの各々との間の距離、及びピボット中心距離記憶部４４に記憶された複数のクラスタの中心の各々と、複数のピボットの各々との間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、距離の三角不等式によって得られる中心とデータ点との間の距離の下限と実距離との差が大きい中心をピボットとして選択することにより、上述したピボットとして望まれる性質「（イ）同一の領域に複数のピボットが存在しないこと。」を満たしやすいピボットが選択される。
【０１４９】
［第３の実施の形態］
次に、本発明の第３の実施の形態について説明する。なお、第１又は第２の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１５０】
第３の実施の形態では、Ｌｌｏｙｄ法を適用することなくピボット選択を行う点が、第１又は第２の実施の形態と異なっている。
【０１５１】
第１又は第２の実施の形態では、Ｌｌｏｙｄ法を１反復適用し、得られた中心に基づいてピボットを選択したが、第３の実施の形態では、Ｌｌｏｙｄ法を適用することなくピボットを選択する。
【０１５２】
＜クラスタリング装置の構成＞
図１０に示すように、第３の実施の形態に係るクラスタリング装置３００は、機能的には、入力部１０と、演算部２０と、出力部５０とを含んだ構成で表すことができる。
【０１５３】
演算部２０は、クラスタリング部３２２と、データ点座標記憶部２６と、中心座標記憶部２８と、ピボット座標記憶部３２と、ピボットデータ点距離記憶部３８と、中心ＩＤ記憶部３４と、ピボット中心距離記憶部４４と、分割結果処理部４８とを備えている。
【０１５４】
クラスタリング部３２２は、データ・分割数処理部２４と、ピボット選択部３０と、ピボットデータ点距離計算部３６と、初期所属中心決定部３２９と、中心座標更新部４０と、ピボット中心距離計算部４２と、所属変更判定部４６とを備えている。
【０１５５】
初期所属中心決定部３２９は、中心座標記憶部２８に記憶されている中心の数から分割数ｋを取得する（または、データ・分割数処理部２４から直接取得してもよい）。そして、初期所属中心決定部３２９は、データ点の集合Ｘのデータ点の各々について、当該データ点の所属をそれぞれランダムにクラスタの中心に割り振り、当該データ点が所属する中心のＩＤ番号を中心ＩＤ記憶部３４に記憶させる。
【０１５６】
第３の実施の形態に係るクラスタリング装置３００のピボット選択部３０は、たとえば、データ点の集合Ｘから、ランダムに初期ピボットを選択し、以降、既存ピボット集合から最も遠いデータ点を再帰的にｊ−１回選択する。そして、ピボット選択部３０は、選択されたピボットの座標をピボット座標記憶部３２に記憶させる。
【０１５７】
＜クラスタリング装置の作用＞
次に、第３の実施の形態に係るクラスタリング装置の作用について説明する。第３の実施の形態に係るクラスタリング装置では、図１１に示すデータ分割処理ルーチンが実行される。なお、図１１に示すデータ分割処理ルーチンにおける、第１の実施の形態におけるデータ分割処理ルーチンと同一の処理については、同一符号を付して、詳細な説明を省略する。
【０１５８】
ステップＳ１０３において、初期所属中心決定部３２９によって、データ点の集合Ｘのデータ点の各々について、当該データ点の所属をそれぞれランダムにクラスタの中心に割り振り、当該データ点が所属する中心のＩＤ番号を中心ＩＤ記憶部３４に記憶させる。
【０１５９】
ステップＳ１０４において、ピボット選択部３０によって、ピボット選択処理が行われる。ステップＳ１０４は、図１２に示すピボット選択処理ルーチンによって実現される。
【０１６０】
＜ピボット選択処理ルーチン＞
ステップＳ６００において、データ点の集合Ｘから、１つのピボットを選択する。
【０１６１】
ステップＳ６０２において、データ点の集合Ｘから、上記ステップＳ６００で選択された最初のピボットと前回までの本ステップＳ６０２で選択されたピボットとを含むピボット集合から最も遠いデータ点を、ピボットとして選択する。
【０１６２】
ステップＳ６０４において、ｊ個のピボットが選択されたか否かを判定する。ｊ個のピボットが選択された場合には、ピボット選択処理ルーチンを終了する。一方、ｊ個のピボットが選択されていない場合には、ステップＳ６００へ戻る。
【０１６３】
なお、第３の実施の形態に係るクラスタリング装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１６４】
以上説明したように、第３の実施の形態に係るクラスタリング装置によれば、既存ピボット集合から最も遠いデータ点を再帰的にピボットとして選択し、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点と複数のピボットの各々との間の距離、及びピボット中心距離記憶部４４に記憶された、複数のクラスタの中心の各々と複数のピボットの各々との間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、既存ピボット集合から最も遠いデータ点を再帰的にピボットとして選択することにより、上述したピボットとして望まれる性質「（イ）同一の領域に複数のピボットが存在しないこと。」を満たしやすいピボットが選択される。
【０１６５】
［第４の実施の形態］
次に、本発明の第４の実施の形態について説明する。なお、第４の実施の形態に係るクラスタリング装置の構成は、第３の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１６６】
第４の実施の形態では、確率的にピボットの選択を行う点が、第１〜第３の実施の形態と異なっている。
【０１６７】
上記第１〜第３の実施の形態では、決定論的にピボットの選択を行ったが、第４の実施の形態では、確率的にピボットの選択を行う。
【０１６８】
＜クラスタリング装置の構成＞
第４の実施の形態に係るクラスタリング装置のピボット選択部３０は、ランダムに最初のピボットを選択する。ピボット選択部３０は、２個目からｊ個目のピボットについて、データ点の集合Ｘから既存ピボット集合Ｐを除いた集合から、以下の式（３）に示す確率に従って、ｘ’∈Ｘ＼Ｐをピボットとして選択する。
【０１６９】
【数６】
2016042237.tif 000008
【０１７０】
なお、Ｄ（ｘ）は既存ピボット集合のうち、最もデータ点ｘと近い距離に存在するピボットと、データ点ｘとの間の距離を表す。
【０１７１】
＜クラスタリング装置の作用＞
次に、第４の実施の形態に係るクラスタリング装置の作用について説明する。第４の実施の形態に係るクラスタリング装置では、上記図１１に示すデータ分割処理ルーチンと同様の処理ルーチンが実行される。
【０１７２】
ステップＳ１０４において、ピボット選択部３０によって、ピボット選択処理が行われる。ステップＳ１０４は、図１３に示すピボット選択処理ルーチンによって実現される。
【０１７３】
＜ピボット選択処理ルーチン＞
ステップＳ７００において、ランダムに１つ目のピボットを選択し、ピボット座標記憶部３２に記憶させる。
【０１７４】
ステップＳ７０２において、データ点の集合Ｘから、１つのデータ点ｘを設定する。
【０１７５】
ステップＳ７０４において、ピボット座標記憶部３２から、既存ピボット集合に含まれるピボットの各々の座標を取得し、上記ステップＳ７０２で設定されたデータ点ｘと最も近い距離に存在するピボットとデータ点ｘとの間の距離Ｄ（ｘ）を算出する。
【０１７６】
ステップＳ７０６において、データ点の集合Ｘに含まれる全てのデータ点について、上記ステップＳ７０２〜Ｓ７０４の各処理を実行したか否かを判定する。全てのデータ点について、上記ステップＳ７０２〜Ｓ７０４の各処理を実行した場合には、ステップＳ７０８へ進む。一方、上記ステップＳ７０２〜Ｓ７０４の各処理を実行していないデータ点が存在する場合には、ステップＳ７０２へ戻る。
【０１７７】
ステップＳ７０８において、データ点の集合Ｘから既存ピボット集合Ｐを除いた集合について、上記ステップＳ７０４で算出されたＤ（ｘ）の各々の和を算出する。
【０１７８】
ステップＳ７１０において、データ点の集合Ｘから、上記式（３）に示す確率に従って、ｘ’∈Ｘ＼Ｐをピボットとして選択し、選択されたピボットの座標を、ピボット座標記憶部３２に記憶させる。
【０１７９】
ステップＳ７１２において、ｊ個のピボットが選択されたか否かを判定する。ｊ個のピボットが選択された場合には、ピボット選択処理ルーチンを終了する。一方、ｊ個のピボットが選択されていない場合には、ステップＳ７１０へ戻る。
【０１８０】
なお、第４の実施の形態に係るクラスタリング装置の他の構成及び作用については、第１又は第３の実施の形態と同様であるため、説明を省略する。
【０１８１】
以上説明したように、第４の実施の形態に係るクラスタリング装置によれば、確率的にピボットを選択し、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点と複数のピボットの各々との間の距離、及びピボット中心距離記憶部４４に記憶された、複数のクラスタの中心の各々と複数のピボットの各々との間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、確率的にピボットを選択することにより、データ点の疎な領域に存在するデータ点がピボットとして選択されにくくなるため、上述したピボットとして望まれる性質「（ア）ユークリッド空間中でデータ点の密な領域に存在すること。」を満たしやすいピボットが選択される。
【０１８２】
［第５の実施の形態］
次に、本発明の第５の実施の形態について説明する。なお、第５の実施の形態に係るクラスタリング装置の構成は、第３又は第４の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１８３】
第５の実施の形態では、距離計算の省略が行えていない回数が多く、かつ既存のピボットから遠い中心を確率的にピボットとして選択する点が、第１〜第４の実施の形態と異なっている。
【０１８４】
上記第１の実施の形態では、ｃｏｕｎｔ（ｃ）を用いて「距離計算の省略が行えていない回数が多い中心」をピボットとして選択したが、第５の実施の形態では、ピボットの選択にピボット同士の距離の要素を加味することで、ピボットが遠くの領域に配置されやすくする。
【０１８５】
＜クラスタリング装置の構成＞
第５の実施の形態に係るクラスタリング装置のピボット選択部３０は、上記第１の実施の形態と同様の手法により、最初のピボットを選択する。ピボット選択部３０は、２個目からｊ個目のピボットについて、複数のデータ点の各々について、データ点と当該データ点が所属するクラスタの中心との距離と、ピボットとデータ点との距離と、ピボットとデータ点が所属するクラスタの中心との距離とに基づいて、中心の集合Ｃから既存ピボット集合Ｐを除いた集合から、以下の式（４）に示す確率に従って、中心ｃＴ∈Ｃ＼Ｐをピボットとして選択する。
【０１８６】
【数７】
2016042237.tif 000009
【０１８７】
なお、Ｄ（ｃ）は既存のピボットのうち最も中心ｃと近い距離に存在するピボットと、中心ｃとの間の距離を表す。
【０１８８】
＜クラスタリング装置の作用＞
次に、第５の実施の形態に係るクラスタリング装置の作用について説明する。第５の実施の形態に係るクラスタリング装置では、上記図１１に示すデータ分割処理ルーチンと同様の処理ルーチンが実行される。
【０１８９】
データ分割処理ルーチンのステップＳ１０４において、ピボット選択部３０によって、ピボット選択処理が行われる。ステップＳ１０４は、図１４及び図１５に示すピボット選択処理ルーチンによって実現される。
【０１９０】
＜ピボット選択処理ルーチン＞
ステップＳ８００において、ピボット座標記憶部３２から、既存ピボット集合に含まれるピボットの各々の座標を取得し、ステップＳ３０２で設定された中心ｃと最も近い距離に存在するピボットと中心ｃとの間の距離Ｄ（ｃＸ）を算出する。
【０１９１】
ステップＳ８０２において、中心の集合Ｃから既存ピボット集合Ｐを除いた集合について、上記ステップＳ８００で算出されたＤ（ｃ）の各々の和を算出する。
【０１９２】
ステップＳ８０４において、中心の集合Ｃから、上記式（４）に示す確率に従って、ｃＴ∈Ｃ＼Ｐをピボットとして選択し、選択されたピボットの座標を、ピボット座標記憶部３２に記憶させる。
【０１９３】
ステップＳ８０６において、ｊ個のピボットが選択されたか否かを判定する。ｊ個のピボットが選択された場合には、ピボット選択処理ルーチンを終了する。一方、ｊ個のピボットが選択されていない場合には、ステップＳ３００へ戻る。
【０１９４】
なお、第５の実施の形態に係るクラスタリング装置の他の構成及び作用については、第４の実施の形態と同様であるため、説明を省略する。
【０１９５】
以上説明したように、第５の実施の形態に係るクラスタリング装置によれば、距離計算の省略が行えていない回数が多く、かつ既存のピボットから遠い中心を確率的にピボットとして選択し、複数のデータ点の各々について、ピボットデータ点距離記憶部３８に記憶された、データ点と複数のピボットの各々との間の距離、及びピボット中心距離記憶部４４に記憶された複数のクラスタの中心の各々と、複数のピボットの各々との間の距離に基づいて、データ点が所属するクラスタを決定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、距離計算の省略が行えていない回数が多く、かつ既存のピボットから遠い中心を確率的にピボットとして選択することにより、上述したピボットとして望まれる性質「（ア）ユークリッド空間中でデータ点の密な領域に存在すること。」及び「（イ）同一の領域に複数のピボットが存在しないこと。」を満たしやすいピボットが選択される。
【０１９６】
［第６の実施の形態］
次に、本発明の第６の実施の形態について説明する。なお、第１〜第５の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１９７】
第６の実施の形態では、複数のデータ点をクラスタリングする際に、クラスタリングの繰り返し計算においてクラスタの中心が移動しない場合に、データ点とクラスタの中心との間の距離計算を省略する点が第１〜第５の実施の形態と異なっている。
【０１９８】
＜クラスタリング装置の構成＞
図１６に示すように、第６の実施の形態に係るクラスタリング装置６００は、機能的には、入力部１０と、演算部６２０と、出力部５０とを含んだ構成で表すことができる。
【０１９９】
演算部６２０は、クラスタリング部６２２と、データ点座標記憶部２６と、中心座標記憶部２８と、中心ＩＤ記憶部３４と、分割結果処理部４８とを備えている。
【０２００】
クラスタリング部６２２は、複数のデータ点の各々について、当該データ点の所属するクラスタの決定に応じて当該クラスタの中心の位置が変更されたか否かに基づいて、データ点が所属するクラスタを決定する。クラスタリング部６２２は、データ・分割数処理部２４と、初期所属中心決定部３２９と、中心座標更新部６４０と、所属変更判定部６４６とを備えている。
【０２０１】
中心座標更新部６４０は、複数のクラスタの中心の各々について、当該中心に所属しているデータ点を中心ＩＤ記憶部３４から読み込み、当該中心に所属しているデータ点を調べる。そして、中心座標更新部６４０は、複数のクラスタの中心の各々について、当該中心に所属するデータ点の座標をデータ点座標記憶部２６から読み込み、読み込まれた複数のデータ点の重心を算出し、算出された重心を、当該中心の新たな座標として中心座標記憶部２８に記憶させる。
また、中心座標更新部６４０は、複数のクラスタの中心の各々について、上記更新処理によって、当該クラスタの中心が移動したか否かを所属変更判定部６４６へ出力する。
【０２０２】
所属変更判定部６４６は、複数のクラスタの中心の各々の中心が移動したか否かに基づいて、複数のデータ点の各々に対し、当該データ点と複数のクラスタの中心の各々との間の距離を計算するか否かを判定する。そして、所属変更判定部６４６は、複数のデータ点の各々について、計算されたデータ点とクラスタの中心との間の距離に基づいて、データ点が所属するクラスタを変更するか否かを判定する。
【０２０３】
図１７に所属変更判定部６４６の処理の概念図を示す。図１７（Ａ）に示すように、データ点ｘと中心ｃＸ，ｃＹとが空間上に存在していると仮定する。なお、添え字「’」が付与された中心ｃ’は、中心ｃが中心座標更新部６４０によって更新された後の中心を表す。また、データ点ｘが中心ｃＸに所属していると仮定する。
【０２０４】
図１７（Ｂ）に示すように、中心座標更新部６４０による更新処理によって、中心ｃＸ及び中心ｃＹが移動しない場合には、データ点ｘの所属は中心ｃＸのままであるため、データ点ｘとクラスタの中心ｃＹとの間の距離計算を省略することができる。
【０２０５】
一方、図１７（Ｃ）に示すように、中心座標更新部６４０による更新処理によって、中心ｃＸ及び中心ｃＹの少なくとも一方が移動した場合には、データ点ｘと中心ｃＸ’との間の距離ｄ（ｘ，ｃＸ’）、及びデータ点ｘと中心ｃＹ’との間の距離ｄ（ｘ，ｃＹ’）を計算し、計算した距離ｄ（ｘ，ｃＸ’）及び距離ｄ（ｘ，ｃＹ’）に基づいて、データ点が所属するクラスタを変更するか否かを判定する。
【０２０６】
＜クラスタリング装置の作用＞
次に、第６の実施の形態に係るクラスタリング装置の作用について説明する。第６の実施の形態に係るクラスタリング装置では、図１８に示すデータ分割処理ルーチンが実行される。なお、図１８に示すデータ分割処理ルーチンにおける、第１〜第５の実施の形態におけるデータ分割処理ルーチンと同一の処理については、同一符号を付して、詳細な説明を省略する。
【０２０７】
ステップＳ１１２において、所属変更判定部６４６によって、所属変更判定処理が行われる。ステップＳ１１２は、図１９に示す所属変更判定処理ルーチンによって実現される。
【０２０８】
ステップＳ９００において、ステップＳ１０８での更新処理によって中心ｃＸ及び中心ｃＹの少なくとも１つの中心が移動したか否かを判定する。少なくとも１つの中心が移動した場合には、ステップＳ４２０へ進む。一方、全ての中心が移動していない場合には、ステップＳ４２８へ移行する。
【０２０９】
なお、第６の実施の形態に係るクラスタリング装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０２１０】
以上説明したように、第６の実施の形態に係るクラスタリング装置によれば、複数のクラスタの中心の各々について、当該クラスタの中心が移動したか否かに基づいて、複数のデータ点の各々に対し、当該データ点と複数のクラスタの中心の各々との間の距離を計算するか否かを判定し、複数のクラスタの中心の各々について、当該クラスタの中心が移動した場合には、当該データ点と複数のクラスタの中心の各々との間の距離に基づいて、データ点が所属するクラスタを変更するか否かを判定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。また、データ点が所属するクラスタの中心ｃＸと、データ点が所属するクラスタ以外のクラスタの中心ｃＹとが移動したか否かの計算コストＯ（ｋ２）は、Ｅｌｋａｎの手法の計算コストＯ（ｋ×Ｎ）に比べて、高効率である。
【０２１１】
また、第６の実施の形態に係るクラスタリング装置は、クラスタの中心があまり移動しなくなる、クラスタリングの繰り返し計算の終盤において、効果的である。
【０２１２】
［第７の実施の形態］
次に、本発明の第７の実施の形態について説明する。なお、第１〜第６の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０２１３】
第７の実施の形態では、複数のデータ点をクラスタリングする際に、データ点が所属するクラスタの中心ｃＸと、データ点が所属するクラスタの中心ｃＸ以外の中心ｃＹとの間の距離に基づいて、データ点と中心ｃＹとの間の距離計算の省略を行う点が第１〜第６の実施の形態と異なっている。
【０２１４】
＜クラスタリング装置の構成＞
図２０に示すように、第７の実施の形態に係るクラスタリング装置７００は、機能的には、入力部１０と、演算部７２０と、出力部５０とを含んだ構成で表すことができる。
【０２１５】
演算部７２０は、クラスタリング部７２２と、データ点座標記憶部２６と、中心座標記憶部２８と、中心ＩＤ記憶部３４と、中心間距離記憶部７３５と、分割結果処理部４８とを備えている。
【０２１６】
クラスタリング部７２２は、複数のデータ点の各々について、複数のクラスタの中心間の距離に基づいて、当該データ点が所属するクラスタを決定する。クラスタリング部７２２は、データ・分割数処理部２４と、初期所属中心決定部３２９と、中心座標更新部７４０と、中心間距離算出部７４５と、所属変更判定部７４６とを備えている。
【０２１７】
第７の実施の形態に係るクラスタリング装置の中心座標更新部７４０は、複数のクラスタの中心の各々について、当該中心に所属しているデータ点を中心ＩＤ記憶部３４から読み込み、当該中心に所属しているデータ点を調べる。そして、中心座標更新部７４０は、複数のクラスタの中心の各々について、当該中心に所属するデータ点の座標をデータ点座標記憶部２６から読み込み、読み込まれた複数のデータ点の重心を算出し、算出された重心を、当該中心の新たな座標として中心座標記憶部２８に記憶させる。
【０２１８】
中心間距離算出部７４５は、複数のクラスタの中心のペアの各々について、中心と他の中心との間の距離を算出し、算出された距離を、中心間距離記憶部７３５へ記憶させる。
【０２１９】
中心間距離記憶部７３５には、複数のクラスタの中心のペアの各々について、中心と他の中心との間の距離が記憶される。
【０２２０】
所属変更判定部７４６は、複数のデータ点の各々について、複数のクラスタの各々に対し、中心間距離記憶部７３５に記憶された、当該データ点と当該データ点が所属するクラスタの中心と当該データ点が所属するクラスタ以外のクラスタの中心との間の距離に基づいて、当該データ点と複数のクラスタの中心の各々との間の距離を計算するか否かを判定する。そして、所属変更判定部７４６は、複数のデータ点の各々について、計算されたデータ点とクラスタの中心との間の距離に基づいて、データ点が所属するクラスタを変更するか否かを判定する。
【０２２１】
図２１に所属変更判定部７４６の処理の概念図を示す。図２１に示すように、データ点ｘと、中心座標更新部７４０による更新処理後の中心ｃＸ，ｃＹとが空間上に存在していると仮定する。また、データ点ｘは中心ｃＸに所属していると仮定する。
【０２２２】
所属変更判定部７４６は、図２１（Ａ）に示すように、データ点ｘと当該データ点が所属するクラスタの中心ｃＸとの間の距離ｄ（ｘ，ｃＸ）を算出する。次に、所属変更判定部７４６は、データ点が所属するクラスタの中心ｃＸと、当該データ点が所属するクラスタ以外のクラスタの中心ｃＹとの間の距離ｄ（ｃＸ，ｃＹ）を、中心間距離記憶部７３５から取得する。そして、所属変更判定部７４６は、ｄ（ｘ，ｃＸ）≦ｄ（ｃＸ，ｃＹ）／２である場合には、データ点ｘと中心ｃＹとの間の距離ｄ（ｘ，ｃＹ）の計算を省略する。この場合には、データ点ｘは、中心ｃＸ半径ｄ（ｃＸ，ｃＹ）／２の円内に存在し、データ点ｘの所属は中心ｃＸのままであるため、データ点ｘと中心ｃＹとの間の距離ｄ（ｘ，ｃＹ）の計算は省略することができる。
【０２２３】
一方、所属変更判定部６４６は、図２１（Ｂ）に示すように、ｄ（ｘ，ｃＸ）＞ｄ（ｃＸ，ｃＹ）／２である場合には、データ点ｘと中心ｃＹとの間の距離ｄ（ｘ，ｃＹ）の計算を行う。データ点ｘが中心ｃＸ半径ｄ（ｃＸ，ｃＹ）／２の円内に存在しないため、データ点ｘと中心ｃＹとの間の距離ｄ（ｘ，ｃＹ）の計算を行い、データ点ｘの所属を決定する。
【０２２４】
＜クラスタリング装置の作用＞
次に、第７の実施の形態に係るクラスタリング装置の作用について説明する。第７の実施の形態に係るクラスタリング装置では、図２２に示すデータ分割処理ルーチンが実行される。なお、図２２に示すデータ分割処理ルーチンにおける、第１〜第６の実施の形態におけるデータ分割処理ルーチンと同一の処理については、同一符号を付して、詳細な説明を省略する。
【０２２５】
ステップＳ１０００において、中心間距離算出部７４５によって、複数のクラスタの中心のペアの各々について、当該中心と他の中心との間の距離を算出し、算出された距離を、中心間距離記憶部７３５へ記憶させる。
【０２２６】
ステップＳ１１２において、所属変更判定部７４６によって、所属変更判定処理が行われる。ステップＳ１１２は、図２３に示す所属変更判定処理ルーチンによって実現される。
【０２２７】
ステップＳ１００２において、ステップＳ４０２で取得した中心ｃＸと、ステップＳ４０８で設定された中心ｃＹとに基づいて、中心ｃＸと中心ｃＹとの間の距離ｄ（ｃＸ，ｃＹ）を中心間距離記憶部７３５から取得する。
【０２２８】
ステップＳ１００４において、ステップＳ４０６で算出したデータ点ｘと中心ｃＸとの間の距離ｄ（ｘ，ｃＸ）と、上記ステップＳ１００２で取得した中心ｃＸと中心ｃＹとの間の距離ｄ（ｃＸ，ｃＹ）とに基づいて、ｄ（ｘ，ｃＸ）＞ｄ（ｃＸ，ｃＹ）／２であるか否かを判定する。ｄ（ｘ，ｃＸ）＞ｄ（ｃＸ，ｃＹ）／２である場合には、ステップＳ４２０へ進む。一方、ｄ（ｘ，ｃＸ）＞ｄ（ｃＸ，ｃＹ）／２でない場合には、ステップＳ４２８へ進む。
【０２２９】
なお、第７の実施の形態に係るクラスタリング装置の他の構成及び作用については、第６の実施の形態と同様であるため、説明を省略する。
【０２３０】
以上説明したように、第７の実施の形態に係るクラスタリング装置によれば、複数のデータ点の各々について、複数のクラスタの各々に対し、当該データ点と当該データ点が所属するクラスタの中心と、当該データ点が所属するクラスタ以外のクラスタの中心との間の距離に基づいて、当該データ点と複数のクラスタの中心の各々との間の距離を計算するか否かを判定することにより、データ点の数及びクラスタの数が大きな値であっても、少ない記憶容量で複数のデータ点を高速にクラスタリングすることができる。
【０２３１】
また、データ点が所属するクラスタの中心ｃＸと、データ点が所属するクラスタ以外のクラスタの中心ｃＹとの間の距離ｄ（ｃＸ，ｃＹ）の計算コストは、メモリ、計算量共にＯ（ｋ２）であり、Ｅｌｋａｎの手法の計算コストＯ（ｋ×Ｎ）に比べて、高効率である。
【０２３２】
なお、本発明は、上記実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０２３３】
例えば、上記第６及び第７の実施の形態では、ピボットを用いずに、データ点の所属するクラスタの中心を変更するか否かを判定する場合を例に説明したが、これに限定されるものではなく、ピボットを用いた処理と組み合わせてもよい。
なお、上記第６又は第７の実施の形態においてピボットを用いた処理と組み合わせる場合には、ピボットによる距離計算の省略の判定処理と、クラスタの中心間の情報に基づく距離計算の省略の判定処理とは、何れを先に実行してもよい。
また、ピボットによる距離計算の省略の判定処理とクラスタの中心間の情報に基づく距離計算の省略の判定処理との２つの処理を適応的に組み合わせてもよい。
例えば、ピボットがｊ個存在する場合に、ピボットによる距離計算の省略の判定処理の回数は、最小１回最大ｊ回であり、クラスタの中心間の情報に基づく距離計算の省略の判定処理は１回であるという性質に基づいて、クラスタの中心間の情報に基づく判定処理を行った後にピボットによる判定処理を行ってもよい。
また、例えば、クラスタリングの繰り返し計算の前半ではクラスタの中心の移動が頻繁に起こり、後半ではクラスタの中心の移動が収束に向かうというクラスタリング処理の性質に基づいて、繰り返し計算の前半では、ピボットによる判定処理を行った後にクラスタの中心間の情報に基づく判定処理を行い、繰り返し計算の後半では、クラスタの中心間の情報に基づく判定処理を行った後にピボットによる判定処理を行ってもよい。
また、ピボットを用いた処理を組み合わせる場合には、データ点ｘと中心ｃＸとの間の距離ｄ（ｘ，ｃＸ）は、ピボットを用いた処理において算出されるため、再度算出しなくともよい。
【０２３４】
また、本実施の形態では、ユークリッド空間を対象としたが、他の空間を対象としてもよい。
【０２３５】
また、上記実施の形態では、データ点座標記憶部２６、中心座標記憶部２８、ピボット座標記憶部３２、中心ＩＤ記憶部３４、ピボットデータ点距離記憶部３８、及びピボット中心距離記憶部４４を備えている場合について説明したが、例えばデータ点座標記憶部２６、中心座標記憶部２８、ピボット座標記憶部３２、中心ＩＤ記憶部３４、ピボットデータ点距離記憶部３８、及びピボット中心距離記憶部４４の少なくとも１つがクラスタリング装置の外部装置に設けられ、クラスタリング装置は、外部装置と通信手段を用いて通信することにより、データ点座標記憶部２６、中心座標記憶部２８、ピボット座標記憶部３２、中心ＩＤ記憶部３４、ピボットデータ点距離記憶部３８、及びピボット中心距離記憶部４４の少なくとも１つを参照するようにしてもよい。
【０２３６】
また、上述のクラスタリング装置は、内部にコンピュータシステムを有しているが、コンピュータシステムは、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０２３７】
また、本願明細書中において、プログラムが予めインストールされている実施の形態として説明したが、外部の記憶装置や記録媒体等に格納されたプログラムを随時読み込んで、またインターネットを介してダウンロードして実行するようにしてもよい。また、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０２３８】
２０，６２０，７２０ 演算部
１０   入力部
２２，３２２，６２２，７２２  クラスタリング部
２４   データ・分割数処理部
２６   データ点座標記憶部
２８   中心座標記憶部
３０   ピボット選択部
３２   ピボット座標記憶部
３４   中心ＩＤ記憶部
３６   ピボットデータ点距離計算部
３８   ピボットデータ点距離記憶部
４０，６４０，７４０ 中心座標更新部
４２   ピボット中心距離計算部
４４   ピボット中心距離記憶部
４６，６４６，７４６ 所属変更判定部
４８   分割結果処理部
５０   出力部
１００，３００，６００，７００  クラスタリング装置
３２９ 初期所属中心決定部
７３５ 中心間距離記憶部
７４５ 中心間距離算出部
【図１】
2016042237.tif 000010
【図３】
2016042237.tif 000011
【図４】
2016042237.tif 000012
【図５】
2016042237.tif 000013
【図６】
2016042237.tif 000014
【図７】
2016042237.tif 000015
【図８】
2016042237.tif 000016
【図９】
2016042237.tif 000017
【図１０】
2016042237.tif 000018
【図１１】
2016042237.tif 000019
【図１２】
2016042237.tif 000020
【図１３】
2016042237.tif 000021
【図１４】
2016042237.tif 000022
【図１５】
2016042237.tif 000023
【図１６】
2016042237.tif 000024
【図１８】
2016042237.tif 000025
【図１９】
2016042237.tif 000026
【図２０】
2016042237.tif 000027
【図２２】
2016042237.tif 000028
【図２３】
2016042237.tif 000029
【図２】
2016042237.tif 000030
【図１７】
2016042237.tif 000031
【図２１】
2016042237.tif 000032
【図２４】
2016042237.tif 000033