高次元データを塊に分割する装置
【課題】 クラスタリング対象のデータ数、及び最終的なクラスタ数の制限を受けず、従来の手法に比較して、高速にクラスタリングが行えるクラスタリングシステムを提供する。
【解決手段】 本発明のクラスタリングシステムは、類似性閾値範囲の類似性を有するデータの組合せを抽出する類似集合抽出部と、各データポイントにおけるデータ密度が、密度閾値以上のデータを対象として抽出するデータ抽出部と、クラスタの最小のデータ番号を抽出し、クラスタラベル番号とし、クラスタラベル番号及びクラスタ内のデータ番号の対応表を生成する対応表生成部と、クラスタラベル番号のデータが、他に属することを検出すると、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と複数の閾値組に対するクラスタリング結果を再構成し、適切なクラスタを抽出するクラスタリング再構成部とを有している。
【解決手段】 本発明のクラスタリングシステムは、類似性閾値範囲の類似性を有するデータの組合せを抽出する類似集合抽出部と、各データポイントにおけるデータ密度が、密度閾値以上のデータを対象として抽出するデータ抽出部と、クラスタの最小のデータ番号を抽出し、クラスタラベル番号とし、クラスタラベル番号及びクラスタ内のデータ番号の対応表を生成する対応表生成部と、クラスタラベル番号のデータが、他に属することを検出すると、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と複数の閾値組に対するクラスタリング結果を再構成し、適切なクラスタを抽出するクラスタリング再構成部とを有している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似性または非類似性を基準にして、大量のデータを高速に分類するためのクラスタリングシステムに関する。
【背景技術】
【０００２】
近年、大規模データベースから、様々なデータ解析手法を用いて、データベースに内在する、新しい、有用な、理解しやすいパターンを発掘し、得られたパターンを専門化の知識と照合して新しい知識を発見する「データベースからの知識発見、およびデータマイニング」が注目を浴びている。
その中でも、特性が似ている（類似性のある）もの、及び違っている（非類似性のある）ものにより、システムが分類のための演算を行い、場合分けをする基準を作り出すクラスタリング方法がある。
【０００３】
このクラスタリング方法を用いて、膨大なデータから、類似性の高いデータを抽出することで同じクラスタ（塊）として認識する。
このクラスタリング方法にも幾つかの手法があり、以前から知られているクラスタリングのアルゴリズムとしては非階層的クラスタリング法であるｋ−ｍｅａｎｓ法，ＥＭ法，階層的クラスタリング法（非特許文献２）、及び密度ベース法（非特許文献１）などがある。
ｋ−ｍｅａｎｓ法及びＥＭ法は、アルゴリズムが比較的簡単であり、ある初期分割から始めて、各手法毎に定められた任意の評価基準において良い分割結果が得られる様に、対象を分類し直すことを繰り返して最終的な分割結果を得る。
【０００４】
階層的クラスタリング法は、各対象をバラバラの１つのクラスタと見なして、近いクラスタを次々と統合することにより、最終的な分類結果を得るものであり、比較的に性質の良い分類結果が得られる。
また、密度ベース法は、所定のデータの密度を有し、距離が近いデータ同士を結合していくものである。
【非特許文献１】A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise（ http://ifsc.ualr.edu/xwxu/publications/kdd-96.pdf）
【非特許文献２】Data Clustering: A Review. ACM Computer Surveys, 31(3), Sept 1999（http://citeseer.nj.nec.com/jain99data.html）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のクラスタリング方法には、それぞれ長所及び短所が有り、以下に示す理由により、多くのクラスタを抽出する場合に適用するのが困難である。
（１）ｋ−ｍｅａｎｓ法及びＥＭ法においては、最終的に分類されるクラスタの数を、クラスタリング開始時に指定することが必要であり、その指定数を特定することが困難であった。
例えば、最も良いクラスタの数として、１００が良いのかまたは１０１が良いのかを、実際にクラスタリングする時点において設定することができず、クラスタリングの結果を解析して再設定等を行う必要がある。特に、最終的なクラスタの数が、平均的なクラスタ内の点の数を上回るような場合には、クラスタの数を決定することは不可能であった。
【０００６】
（２）階層的クラスタリング法においては、クラスタの個数を事前に決定せずに用いることができ、有効なクラスタリングを行うことができるが、各データをツリー構造により類似性のあるデータ同士を結合させてクラスタを作成するため、演算に時間がかかる手法であり、データ数が多くなるにつれ、現実的な時間内では終了できない欠点を有している。
【０００７】
（３）密度ベースにおいては、密度・非類似度を満足するクラスタを際限なく結合していくため、生成されるクラスタの大きさを制限することができない欠点を有している。
また、地理情報・空間情報などの２次元及び３次元のデータに対するクラスタリングには適しているが、より高次元データに対しては、各データ毎に近傍のデータ密度の演算を行うため、クラスタリングの処理に長い時間がかかる。
【０００８】
本発明は、このような事情に鑑みてなされたもので、クラスタリング対象のデータ数、及び最終的なクラスタ数の制限を受けず、かつ従来の手法に比較して、高速にクラスタリングが行えるクラスタリングシステム、クラスタリング方法及びクラスタリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明のクラスタリングシステムは、クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出部と、各々のデータを対象データとし、この対象データを中心として、この中心から前記閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出部と、各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成部と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と、を有し、前記リスト入替部が、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とする。
【００１０】
本発明のクラスタリングシステムは、前記リスト入替部がクラスタラベルを書き換えることにより生成されたクラスタ間において、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする。
【００１１】
本発明のクラスタリングシステムは、前記収束判定部が、前記検出処理において、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする。
【００１２】
本発明のクラスタリングシステムは、前記リスト入替部におけるクラスタラベルの書き換え処理と、閾値範囲内のデータが異なったクラスタに含まれているか否かの検出処理とを、双方の処理結果が収束するまで行うことを特徴とする。
【００１３】
本発明のクラスタリングシステムは、前記類似性閾値及び密度閾値の閾値組が複数設定され、条件の厳しい閾値組から緩い閾値組へ順次、組毎の条件によりクラスタリングを実施するクラスタリング制御部を有することを特徴とする。
【００１４】
本発明のクラスタリングシステムは、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成することを特徴とする。
本発明のクラスタリングシステムは、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とするクラスタリング再構成部を有することを特徴とする。
【００１５】
本発明のクラスタリング方法は、クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出過程と、各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出過程と、各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成過程と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替過程と、を有し、前記リスト入替過程において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理が行うことを特徴とする。
【００１６】
本発明のクラスタリング方法は、前記リスト入替過程において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定過程を有することを特徴とする。
本発明のクラスタリング方法は、前記収束判定過程において、前記検出処理のとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする。
【００１７】
本発明のクラスタリング方法は、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成過程を有することを特徴とする。
本発明のクラスタリング方法は、クラスタリング結果再構成過程において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする。
【００１８】
本発明のプログラムは、複数のデータに対して、各々のデータの類似性に基づいてクラスタリングを行うクラスタリングプログラムであり、クラスタリング対象のデータから、所定の閾値範囲の類似性を有するデータの組合わせの集合を抽出する組合集合抽出処理と、各々のデータを対象データとし、この対象データを中心として、この中心から前記閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出処理と、各クラスタに含まれる対象データから閾値以内に存在する対象データの中の最も小さな番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成処理と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替処理と、を有し、前記リスト入替処理において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするコンピュータが実行可能なプログラムである。
【００１９】
本発明のプログラムは、前記リスト入替処理において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有するコンピュータの実行可能なプログラムである。
本発明のプログラムは、前記収束判定処理において、前記検出処理を行うとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とするコンピュータが実行可能なプログラムである。
【００２０】
本発明のプログラムは、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成処理を有することを特徴とするコンピュータが実行可能なプログラムである。
本発明のプログラムは、前記クラスタリング結果再構成処理において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とするコンピュータが実行可能なプログラムである。
【発明の効果】
【００２１】
以上説明したように、本発明によれば、クラスタラベル番号と、このクラスタラベル番号に含まれるデータのデータ番号との対応を示す表を用い、データが共有されるクラスタを順次結合し、新たなクラスタとして生成するため、類似性を演算してクラスタを結合させる従来例とことなり、特別に複雑な演算をすることなく、設定された閾値組に対応したクラスタリングを高速に行うことができるという効果が得られる。
【００２２】
また、本発明によれば、複数の閾値組（類似性閾値，密度閾値）を用いて、各閾値組毎にクラスタリングを行うことにより、各閾値組に対応するクラスタを生成し、これらのクラスタを閾値組の順番、すなわち緩い閾値から厳しい閾値まで順に並べることにより、階層構造クラスタリングに比較して短い時間で、容易にツリー構造を構成するという効果が得られる。
【発明を実施するための最良の形態】
【００２３】
本発明のクラスタリングシステムは、分類対象の各データの類似性の基準を用い、この基準に対する閾値を設定してクラスタリングを行うものである。
この類似性の基準としては、２つのデータが似ているか否かを測るための指標として、類似度または非類似度が用いられる。
データ間の類似性を示す距離は非類似度を表すための典型的な例であり、一方、相関係数は類似度の典型的な例である。
本発明のクラスタリングシステムは、類似性を示す基準として、類似度及び非類似度いずれを使用しても構わず、種々の類似性の定義を用いて、クラスタリングを行うことができる。
以降の説明において、非類似度の表現を用いるが、非類似度の閾値に対する大小関係を逆にすることにより、類似度に置き換えても同様である。
【００２４】
以下、本発明の一実施形態によるクラスタリングシステムを図面を参照して説明する。図１は同実施形態の構成例を示すブロック図である。
データベースＤＢは、大容量のデータの取り扱いに対応できるＲＤＢＭＳ（Relational DataBase Management System）が用いられており、クラスタリングの対象となるデータを格納している。
今まで、多くのクラスタリングシステムには、主記憶装置を使用することが前提とされていた。しかしながら、主記憶装置は高速にアクセス可能であるが、容量としては限られてしまう。
一方、本発明のクラスタリングシステムは、ＲＤＢＭＳを用いるために、主記憶容量の制限を受けることがない。
【００２５】
この図において、クラスタリング制御部１は、非類似度閾値ε及び密度閾値ρの閾値組を、厳しい閾値から緩い閾値まで、複数の段階に分割された閾値組｛（ε1，ρ1），（ε2，ρ2），…，（εｍ，ρｍ）｝が予め設定され、クラスタリングに際して、各閾値組を選択して、類似度集合抽出部２へ非類似度閾値εを出力し、データ抽出部４へ密度閾値ρを出力する。
ここで、クラスタリング制御部１は、厳しい非類似度閾値及び密度閾値の閾値組から、緩い非類似度閾値及び密度閾値の閾値組まで、各閾値組におけるクラスタリングが終了すると、次の閾値組を選択して、類似度集合抽出部２へ非類似度閾値を出力し、データ抽出部４へ密度閾値ρを出力し、対応表生成部６に初期クラスタを出力する。
【００２６】
類似度集合抽出部２は、入力される非類似度閾値εにより、データベースＤＢにおけるクラスタリング対象の全データポイント（データの有する複数の評価値をそれぞれ次元として、この評価値の次元の空間におけるデータの座標位置）の集合Ｘから、２つのデータポイント同士の値の非類似度の集合Ｄを生成する。
Ｘ：＝｛ｘ1，ｘ2，…，ｘn｝
Ｄ≡｛ｄ(ｉ，ｊ)｜ｉ，ｊ∈Ｘ｝
また、類似度集合抽出部２は、上記集合Ｄにおいて、所定の非類似度閾値ε範囲の類似性を有するデータポイントの組み合わせ、例えば、非類似度が上記非類似度閾値以下となるデータポイントの組合せのデータの集合Ｄεを抽出する。
Ｄε≡｛ｄ(ｉ，ｊ)∈Ｄ｜ｄ(ｉ，ｊ)≦ε｝
【００２７】
データ抽出部４は、集合Ｘに含まれる各々のデータを対象データとし、この対象データを中心として、この中心のデータポイントから上記非類似度閾値εの範囲内で計算可能なデータ密度が、所定の密度閾値ρ以上である対象データの集合ＸCOREを抽出する。
ＸCORE≡｛ｘ∈Ｘ｜ρ｜ε(ｘ)≧ρ｝
クラスタリング制御部１は、データ抽出部４の結果を受け取り、直前に行われた閾値組のクラスタリング結果と結合して初期のクラスタＱを生成し、対応表生成部６へ出力する。
【００２８】
対応表生成部６は、各クラスタに含まれる対象データから非類似度閾値ε以内に存在する対象データの中の最も小さい番号をクラスタラベル番号として、このクラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータポイントのデータ番号の対応表（図３参照）を生成する。
リスト入替部７は、上記対応表により、クラスタラベル番号であるデータポイントが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号（すなわち、現在のクラスタにおいて最も小さいが、他のクラスタに属していることが検出されたデータポイントのデータ番号）を、上記他のクラスタのクラスタラベル番号に書き換える。
【００２９】
ここで、あるクラスタＣ1のクラスタラベル番号となっているデータポイントが、他のクラスタラベル番号のクラスタＣ2に属しているとき、他のクラスタＣ2のクラスタラベル番号が当然にクラスタＣ1のクラスタラベル番号より小さい構造となっている。
また、リスト入替部７は、書き換え前と書き換え後との対応表が同一、すなわち対応表に変化が無くなることを検出するまで書き換え処理を行う。
収束判定部８は、上記リスト入替部７がクラスタラベル番号を書き換えることにより生成されたクラスタ間において、非類似度閾値ε範囲内のデータポイントが異なったクラスタに含まれているか否かを検出する。
【００３０】
また、収束判定部８は、上記検出処理において、非類似度閾値ε範囲内のデータポイントが異なったクラスタに含まれていることを検出した場合、これらのデータポイントの含まれるクラスタ同士を結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とする。
クラスタリング制御部１は、リスト入替部７におけるクラスタラベルの書き換え処理と、収束判定部８における閾値ε範囲内のデータが異なったクラスタに含まれているか否かの検出処理とが、双方の処理結果が収束するまで行わせる。
また、クラスタリング再構成部５は、各非類似度閾値ε及び密度閾値ρの閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、上記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組のクラスタをクラスタリング結果とする。
すなわち、クラスタリング再構成部５は、クラスタに属するデータ間の非類似度の比較を行うことで、設定された非類似度範囲内にないデータポイントを含むクラスタを淘汰し、得られた複数の閾値組に対するクラスタリング結果を再構成し、再構成された各閾値組におけるクラスタリング結果を、全体として一つのクラスタリング結果として抽出する。
【００３１】
次に、図１に示すクラスタリングシステムのクラスタリングの動作を図２を参照して説明する。図２は、図１のクラスタリングシステムの動作例を示すフローチャートである。
クラスタリングを行うために、２つのデータが似ているか否かを判定するのに、類似度及び非類似度のいずれを用いても同様な処理を行うことが可能であるが、以下の説明においては、非類似度を用いたクラスタリングについて
ステップＳ１において、クラスタリング制御部１は、まず、複数の非類似度閾値と密度閾値の閾値組｛（ε１，ρ１），（ε２，ρ２），．．．，（εｍ，ρｍ）｝を、設定する。この各閾値組の非類似度閾値と密度閾値は後述するツリー構造を作成するための基準を満たしている必要がある。
そして、クラスタリング制御部１は、このなかから、厳しい条件の閾値組を選択して、順次、厳しい条件の閾値組から順番に、クラスタリングの処理を実施していく。
【００３２】
ステップＳ２において、類似集合抽出部２は、クラスタリング制御部１の選択した非類似度閾値εが入力されると、
全データポイント
Ｘ：＝｛ｘ1，ｘ2，…，ｘn｝
に含まれるデータポイント同士の非類似度の集合Ｄ
Ｄ≡｛ｄ(ｉ，ｊ)｜ｉ，ｊ∈Ｘ｝
を生成する。
そして、類似集合抽出部２は、非類似度が非類似度閾値ε以下となるデータ間の組み合わせの集合Ｄε
Ｄε≡｛ｄ(ｉ，ｊ)∈Ｄ｜ｄ(ｉ，ｊ)≦ε｝
を、集合Ｄから抽出する。
【００３３】
データ抽出部４は、クラスタリング制御部１から入力される密度閾値ρにより、各データポイントにおけるデータ密度が密度閾値ρ以上のデータポイントを抽出する。ここで、密度定義の例として、「半径ε（非類似度閾値）以内に含まれるデータポイントの数」を採用することもできる。
すなわち、
ρ｜ε（ｘ）≧ρ
であり、左辺の密度ρはεを母数（パラメータ）とする密度計算のための関数であり、右辺のρは設定された密度閾値であり、密度計算は、ε以内の非類似度のみが影響を及ぼすような計算方法を用いる。
【００３４】
そして、データ抽出部４は、周囲に所定の密度を有するデータポイントとして、Ｘの部分集合ＸCOREを、
ＸCORE≡｛ｘ∈Ｘ｜ρ｜ε (ｘ)≧ρ｝
として求める。
これにより、非類似度が大きいもの、及び周囲に他のデータポイントが少なく、クラスタが生成される可能性がないデータポイントを排除する。
【００３５】
次に、ステップS３において、クラスタリング制御部１は、クラスタリングに対する初期値、すなわち初期のクラスタを定義することとなる。
ここで、クラスタリング制御部１は、データ抽出部４の抽出した各データポイントの所属するクラスタを表現するため、各クラスタに対してクラスタラベルを与える。
また、クラスタリング制御部１は、クラスタの初期値として、直前に実行された閾値組に対する結果を初期クラスタとする。また、この中に含まれておらず、ＸCOREに含まれているデータポイントは、おのおの一つのクラスタとする。
【００３６】
そして、対応表生成部６は、クラスタリング対象のデータポイントの集合ＸCOREにおいて、クラスタに所属するデータポイントから、非類似度が非類似度閾値ε以内のデータポイントの集合を見つけ出し、この集合に含まれる最も小さなデータポイント番号をクラスタのラベル番号（クラスタを代表する番号）として、図３に示す対応表を生成する（ステップＳ３）。
ここで、対応表生成部６は、クラスタラベル番号を付加することにより、すなわち最も小さいデータポイント番号を代表してクラスタラベル番号としたクラスタをクラスタＱとする。
【００３７】
次にステップＳ４において、リスト入替部７は、図３に示す対応表を用いて、類似するクラスタＱ間の接続処理を行う。
この時点において、クラスタと見なされているクラスタＱは、上記クラスタラベル番号により代表されるデータポイントの集合である。
次に、図４を用いて、リスト入替部７によるクラスタＱ間の接続処理を説明する。
図４においては、右の表のデータポイント番号をＡ、クラスタラベル番号をＢとし、また左の表のデータポイント番号をＣ、クラスタラベル番号をＤとする。なお、図４の右及び左の２つの表は全く同一のデータの対応、すなわち図３の表を示すものである。
【００３８】
そして、リスト入替部７は、図３における上記クラスタラベル番号を参照しつつ、図４に示すように、右の表のクラスタラベル番号（B）をデータポイント番号と見なして、左の表のデータポイント番号（C）と比較し、そのデータポイント番号（C）に対応する左のテーブルのクラスタラベル番号（D）を読みとり、クラスタラベル番号（B）をこのクラスタラベル番号（D）に変更する処理を行う。
例えば、リスト入替部７は、データポイント番号３（Ａ）がクラスタラベル番号１（Ｂ）に対応していることを検出し、そして、このクラスタラベル番号１（Ｂ）が左のテーブルにおいて、データポイント番号１（Ｃ）に対応していることを検出し、さらに、このデータポイント番号１（Ｃ）がクラスタラベル番号１（Ｄ）に対応していることを検出する。
【００３９】
そして、リスト入替部７は、クラスタラベル番号１（Ｂ）及びクラスタラベル番号１（Ｄ）の番号が一致しているため、すなわち、すでに同一のクラスタに属しているとして番号を変更する必要がないことを検出する。
一方、リスト入替部７は、データポイント番号４（Ａ）がクラスタラベル番号３（Ｂ）に対応していることを検出し、これは、クラスタラベル番号３（Ｂ）が左のテーブルにおいてデータポイント番号３（Ｃ）に対応していることを検出する。
さらに、リスト入替部７は、データポイント番号３（Ｃ）がクラスタラベル番号１（Ｄ）に対応していることを検出する。
これにより、リスト入替部７は、クラスタラベル番号３（Ｂ）とクラスタラベル番号１（Ｄ）が相違しているため、同一のクラスタに属していないことを検出して、データポイント番号４（Ａ）に対応するクラスタ番号を１（Ｄ）に変更する。
これにより、リスト入替部７は、クラスタＱが複数結合されたクラスタＲを作成する。
【００４０】
次に、ステップＳ５において、リスト入替部７は、テーブルにおける全てのクラスタラベル番号（Ｂ）が変化しない状態となることを検出すると、すなわち、データポイント番号３（Ｂ）のように、対応表を辿っていっても、その先のクラスタラベル番号（Ｄ）が、対象となるデータポイントの含まれるクラスタにおける最も小さなデータポイント番号であると、ステップＳ５の処理を停止し、処理をステップＳ６へ進める。
一方、リスト入替部７は、対応表において、１つでもクラスタラベル番号（Ｂ）が変化した場合、ステップＳ４の処理を繰り返す。
【００４１】
上述したステップＳ４及びステップＳ５において、表におけるリストの入れ替え処理により、データ番号を辿っていくことによりたどり着けるもっとも小さな番号をクラスタラベル番号として持つことになる。すなわち、あるクラスタＱ１に含まれていたデータポイントと他のクラスタＱ２に含まれていたデータポイントが接続されているという状況があった場合に、この２つのクラスタＱ１，Ｑ２が結合され、より大きなクラスタＲに成長していくこととなる。
しかしながら、上述したステップＳ４の処理は、単なる図３の対応表を用いた番号の操作なので、複雑な形状のクラスタに対しては、十分な収束をせず、非類似度の小さなデータポイントを有したクラスタＱが分割された状態のままとなる可能性がある。
たとえば、データポイント番号が大きいデータポイント同士がまとまり、クラスタが接続されている場合、上述したように、ステップＳ４及びＳ５の操作では収束しない。
【００４２】
上述した収束しない場合を検討すると、隣接しているクラスタ間において、図５の様に、データポイント１，３及び５がクラスタＱ１を形成し、また、データポイント２，４及び６がクラスタＱ２を形成しているとする。
このとき、データポイント５及び６が、非類似度において、非類似度閾値εより小さく、類似しているため、この２つのクラスタＱ１及びＱ２は結合処理されなければならないが、クラスタＱ１はクラスタラベル番号１に収束しており、クラスタＱ２はクラスタラベル番号２に収束している。
このため、ステップＳ４及び５における処理では、大きなデータポイント番号が小さなデータポイント番号に置き換えられてしまうため、直接データポイント５及び６が直接に非類似度の検出が行われず、また置き換えられたデータポイント番号１及び２が非類似度閾値εより大きな非類似度であるため、直接の対応関係になく、クラスタＱ１及びＱ２がリスト入れ替え処理のみで結合されることはない。
【００４３】
上述したクラスタが無くなるように、ステップＳ６においては、本来、結合するデータポイントを有するクラスタの検出処理を行う。
すなわち、ステップＳ６において、収束判定部８は、集合Ｄεに含まれるデータポイント番号の組み合わせにおいて、異なったクラスタラベル番号と対応関係となっているデータポイント番号の有無の検出を行う。
これにより、収束判定部８は、非類似度が非類似度閾値より小さなデータポイント同士が異なったクラスタに属していることを検出すると、全体としてクラスタリングの処理が収束していないとして、処理をステップＳ７へ進める。
一方、収束判定部８は、非類似度が非類似度閾値より小さなデータポイント番号の組み合わせにおいて異なったクラスタに属していないことを検出すると、全体としてクラスタリングの処理が収束しているとして、処理をステップＳ８へ進める。
【００４４】
次に、ステップＳ７において、収束判定部８は、ステップＳ６において検出された、異なったクラスタ間で、それぞれ有するデータポイントの間の非類似度が非類似度閾値より小さなデータポイントの組み合わせを検出した場合、これらのデータポイントを含むクラスタＱを結合させ、新たなクラスタＲを生成する。
このとき、このクラスタＲに含まれるデータポイントにおいて、最も小さなデータポイント番号を、このクラスタＲを代表するクラスタラベル番号とし、テーブルのデータポイント番号（Ｃ）に対応するクラスタラベル番号（Ｄ）を書き換え、処理をステップＳ４へ戻し、再度、図３の対応表を用いたリスト入替処理を行う。
【００４５】
例えば、図５において、クラスタＱ１及びクラスタＱ２が合成されることにより、クラスタＲが生成され、このクラスタＲのクラスタラベル番号はクラスタＱ１及びＱ２双方における最も小さなデータポイント番号１とされる。
つまり、図３に示すテーブルにおいて、データポイント番号１，２，３，４，５，６のデータポイント各々が、クラスタラベル番号１のクラスタに属するように書き換えられる。
【００４６】
上述したように、図４に示す表を用いて、各データポイントのデータポイント番号に対応するクラスタラベル番号を、このデータポイントが属しているクラスタのクラスタラベル番号（クラスタ内で最も小さなデータポイント番号）に変更する処理（ステップＳ４及び５）と、図３のテーブル及び集合Ｄεを用いた収束判定の処理（ステップＳ６）と、収束判定において収束されていない場合に行うクラスタの結合処理と、の３つの操作を、ステップＳ６の収束判定で収束されていることが検出されるまで繰り返すことにより、集合Ｄεの非類似度の集合に関連するデータポイントの集合を、非類似度閾値εで設定された範囲での類似度を有するクラスタに分類することができる。
【００４７】
次に、ステップＳ８において、クラスタリング制御部１は、あらかじめ設定されている閾値組｛（ε１，ρ１），（ε２，ρ２），……，（εｍ，ρｍ）｝の全てが終了したか否かの検出を行う。
そして、クラスタリング制御部１は、閾値組（εｉ，ρｉ）が終了したことを検出すると、全ての閾値組のクラスタリングが終了していないことを検出して、処理をステップＳ２に戻し、次に設定された閾値組に対応したクラスタリングの処理を行う。
このとき、閾値組の非類似度閾値及び密度閾値が序々に緩くなるように、（εｍ，ρｍ）→…→（ε２，ρ２）→（ε１，ρ１）と順次設定して、各非類似度閾値毎にステップＳ２からステップＳ８の処理を行い、各比類似度閾値及び密度閾値の組毎のクラスタリングを行う。
一方、クラスタリング制御部１は、予め設定した閾値の組み合わせ（例えば、｛（ε１，ρ１），（ε２，ρ２），……，（εｍ，ρｍ）｝）における全ての閾値に対してクラスタリングが行われたことを検出すると、処理をステップＳ９へ進める。
【００４８】
各々の閾値組において生成されたクラスタは、図６に示すように、各々他の閾値組により生成されたクラスタと交わることはなく、各々のクラスタはより緩い閾値組で生成されたクラスタに含まれるようにできる。
すなわち、緩い閾値を有する閾値組で生成されたクラスタと、厳しい閾値を有する閾値組で生成されたクラスタとは包含関係（緩い閾値を有する閾値組のクラスタが厳しい閾値を有する閾値組のクラスタを包含する）にできる。これは、密度関数・閾値の与え方に依存する。
例えば、非類似度として距離を、密度関数として、「半径ε以内に存在するデータポイントの数」を採用した場合には、密度閾値として一定値を採用し、非類似度閾値として、厳しい方として小さい値を使用し、緩い方として大きい値を採用する。
次に、ステップＳ９において、クラスタリング結果再構成部５は、閾値組が緩くなる方向に順次並べることにより、各閾値組で生成されたクラスタを上記包含関係とすることができ、図６に示すようにツリー構造を構成する。
すなわち、クラスタリング結果再構成部５は、複数の閾値組（閾値，密度閾値）を用い、各閾値組毎にクラスタリングが行われることにより得られた、クラスタを閾値組の順番に、すなわち緩い閾値から厳しい閾値まで順に並べることにより、階層構造クラスタリングに比較して短い時間で、ツリー構造を容易に構成する。
【００４９】
このツリー構造において、多くの閾値を設定することにより、クラスタの分類を細かくして、微妙なツリー構造を確認することもでき、また、大雑把なクラスタの状態を確認するために、閾値を所定の幅を有する間隔で区切って設定することもできる。
上述した閾値は、クラスタの生成状態を確認してユーザが設定しても良いし、また、以下の様に集合Ｄにおいて、含まれるデータポイントの組み合わせにおける非類似度を求め、順位（Rank）という考え方を用いて、システムにより設定するようにしても良い。
【００５０】
ここで順位は、例えば、
Rank：＝１０Ｎ／６
で定義され、上記式において、Ｎ＝１，２，…である。
ε10＝（１０１／６ ≒１番目に小さな非類似度）
ε9＝（１０２／６ ≒２番目に小さな非類似度）
ε8＝（１０３／６ ≒３番目に小さな非類似度）
ε7＝（１０４／６ ≒４番目に小さな非類似度）
ε6＝（１０５／６ ≒６番目に小さな非類似度）
ε5＝（１０６／６ ≒１０番目に小さな非類似度）
ε4＝（１０７／６ ≒１４番目に小さな非類似度）
ε3＝（１０８／６≒２１番目に小さな非類似度）
ε2＝（１０９／６ ≒３１番目に小さな非類似度）
ε1＝（１０１０／６≒４６番目に小さな非類似度）
のように、各々何番目に小さい非類似度により（非類似度の順位を基準として）設定しても良い。
ε10は「１.４６７７…」、ε9は「２.１５４４…」となり、非類似度閾値が設定されることとなる。
【００５１】
ツリー構造を作成した結果、図７に示すように、非常に複雑な形状をしたクラスタが生成されることがある。図７は、類似度を演算する次元が２次元の場合に、平面にクラスタ形状を示す画像が表示されている図である。
等高線のように示される表示の濃さは、各非類似度閾値におけるクラスタ形状を示すものであり、上述したように包含関係にあるため、色の濃い部分はより小さな非類似度閾値によりクラスタリングされたものである。
【００５２】
図７に示すように、非常に複雑な形状を示すクラスタが生成される場合もあり、複雑な形状を認める場合にはこの状態で構わないが、より含まれるデータポイント相互の関連性が高いクラスタを得たい場合には、より円（高次元の場合は超球）に近い単純な形状のクラスタを得ることが必要なため、クラスタリング結果再構成部５は、複数の非類似度閾値により得られたツリー構造のなかから、概略の直径（クラスタに含まれるデータポイントの組合せで最も類似性がないものの非類似度または類似度）が制限値（クラスタの大きさを制限するために予め設定されている非類似度または類似度のクラスタ閾値）以下のクラスタを適切なクラスタとして抽出する。
具体的には、クラスタリング結果再構成部５は、一つのデータポイントに着目し、閾値の厳しい方から順番に処理を行い、上記制限値を超える直前の閾値におけるクラスタリング結果を適切なクラスタとして抽出する。
【００５３】
なお、図１に示すクラスタリングシステムの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりクラスタリングを行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００５４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００５５】
【図１】本発明の一実施形態によるクラスタリングシステムの構成を示すブロック図である。
【図２】図１のクラスタリングシステムの動作例を示すフローチャートである。
【図３】図１の対応表生成部６により生成される対応表の構造を示す概念図である。
【図４】図１のリスト入替部７の動作を説明するための概念図である。
【図５】図１の収束判定部８のクラスタの結合動作を説明するための概念図である。
【図６】図１のクラスタリングシステムによるツリー構造生成処理を説明する概念図である。
【図７】図１のクラスタリングシステムにより生成されたクラスタの形状を示すものであり、緩い閾値組で生成されたクラスタがより厳しい閾値組で生成されたクラスタを包含していることを示す概念図である。
【符号の説明】
【００５６】
１…クラスタリング制御部
２…類似度集合抽出部
４…データ抽出部
５…クラスタリング結果再構成部
６…対応表生成部
７…リスト入替部
８…収束判定部
ＤＢ…データベース
【技術分野】
【０００１】
本発明は、類似性または非類似性を基準にして、大量のデータを高速に分類するためのクラスタリングシステムに関する。
【背景技術】
【０００２】
近年、大規模データベースから、様々なデータ解析手法を用いて、データベースに内在する、新しい、有用な、理解しやすいパターンを発掘し、得られたパターンを専門化の知識と照合して新しい知識を発見する「データベースからの知識発見、およびデータマイニング」が注目を浴びている。
その中でも、特性が似ている（類似性のある）もの、及び違っている（非類似性のある）ものにより、システムが分類のための演算を行い、場合分けをする基準を作り出すクラスタリング方法がある。
【０００３】
このクラスタリング方法を用いて、膨大なデータから、類似性の高いデータを抽出することで同じクラスタ（塊）として認識する。
このクラスタリング方法にも幾つかの手法があり、以前から知られているクラスタリングのアルゴリズムとしては非階層的クラスタリング法であるｋ−ｍｅａｎｓ法，ＥＭ法，階層的クラスタリング法（非特許文献２）、及び密度ベース法（非特許文献１）などがある。
ｋ−ｍｅａｎｓ法及びＥＭ法は、アルゴリズムが比較的簡単であり、ある初期分割から始めて、各手法毎に定められた任意の評価基準において良い分割結果が得られる様に、対象を分類し直すことを繰り返して最終的な分割結果を得る。
【０００４】
階層的クラスタリング法は、各対象をバラバラの１つのクラスタと見なして、近いクラスタを次々と統合することにより、最終的な分類結果を得るものであり、比較的に性質の良い分類結果が得られる。
また、密度ベース法は、所定のデータの密度を有し、距離が近いデータ同士を結合していくものである。
【非特許文献１】A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise（ http://ifsc.ualr.edu/xwxu/publications/kdd-96.pdf）
【非特許文献２】Data Clustering: A Review. ACM Computer Surveys, 31(3), Sept 1999（http://citeseer.nj.nec.com/jain99data.html）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のクラスタリング方法には、それぞれ長所及び短所が有り、以下に示す理由により、多くのクラスタを抽出する場合に適用するのが困難である。
（１）ｋ−ｍｅａｎｓ法及びＥＭ法においては、最終的に分類されるクラスタの数を、クラスタリング開始時に指定することが必要であり、その指定数を特定することが困難であった。
例えば、最も良いクラスタの数として、１００が良いのかまたは１０１が良いのかを、実際にクラスタリングする時点において設定することができず、クラスタリングの結果を解析して再設定等を行う必要がある。特に、最終的なクラスタの数が、平均的なクラスタ内の点の数を上回るような場合には、クラスタの数を決定することは不可能であった。
【０００６】
（２）階層的クラスタリング法においては、クラスタの個数を事前に決定せずに用いることができ、有効なクラスタリングを行うことができるが、各データをツリー構造により類似性のあるデータ同士を結合させてクラスタを作成するため、演算に時間がかかる手法であり、データ数が多くなるにつれ、現実的な時間内では終了できない欠点を有している。
【０００７】
（３）密度ベースにおいては、密度・非類似度を満足するクラスタを際限なく結合していくため、生成されるクラスタの大きさを制限することができない欠点を有している。
また、地理情報・空間情報などの２次元及び３次元のデータに対するクラスタリングには適しているが、より高次元データに対しては、各データ毎に近傍のデータ密度の演算を行うため、クラスタリングの処理に長い時間がかかる。
【０００８】
本発明は、このような事情に鑑みてなされたもので、クラスタリング対象のデータ数、及び最終的なクラスタ数の制限を受けず、かつ従来の手法に比較して、高速にクラスタリングが行えるクラスタリングシステム、クラスタリング方法及びクラスタリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明のクラスタリングシステムは、クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出部と、各々のデータを対象データとし、この対象データを中心として、この中心から前記閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出部と、各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成部と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と、を有し、前記リスト入替部が、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とする。
【００１０】
本発明のクラスタリングシステムは、前記リスト入替部がクラスタラベルを書き換えることにより生成されたクラスタ間において、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする。
【００１１】
本発明のクラスタリングシステムは、前記収束判定部が、前記検出処理において、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする。
【００１２】
本発明のクラスタリングシステムは、前記リスト入替部におけるクラスタラベルの書き換え処理と、閾値範囲内のデータが異なったクラスタに含まれているか否かの検出処理とを、双方の処理結果が収束するまで行うことを特徴とする。
【００１３】
本発明のクラスタリングシステムは、前記類似性閾値及び密度閾値の閾値組が複数設定され、条件の厳しい閾値組から緩い閾値組へ順次、組毎の条件によりクラスタリングを実施するクラスタリング制御部を有することを特徴とする。
【００１４】
本発明のクラスタリングシステムは、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成することを特徴とする。
本発明のクラスタリングシステムは、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とするクラスタリング再構成部を有することを特徴とする。
【００１５】
本発明のクラスタリング方法は、クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出過程と、各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出過程と、各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成過程と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替過程と、を有し、前記リスト入替過程において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理が行うことを特徴とする。
【００１６】
本発明のクラスタリング方法は、前記リスト入替過程において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定過程を有することを特徴とする。
本発明のクラスタリング方法は、前記収束判定過程において、前記検出処理のとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする。
【００１７】
本発明のクラスタリング方法は、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成過程を有することを特徴とする。
本発明のクラスタリング方法は、クラスタリング結果再構成過程において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする。
【００１８】
本発明のプログラムは、複数のデータに対して、各々のデータの類似性に基づいてクラスタリングを行うクラスタリングプログラムであり、クラスタリング対象のデータから、所定の閾値範囲の類似性を有するデータの組合わせの集合を抽出する組合集合抽出処理と、各々のデータを対象データとし、この対象データを中心として、この中心から前記閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出処理と、各クラスタに含まれる対象データから閾値以内に存在する対象データの中の最も小さな番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成処理と、前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替処理と、を有し、前記リスト入替処理において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするコンピュータが実行可能なプログラムである。
【００１９】
本発明のプログラムは、前記リスト入替処理において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有するコンピュータの実行可能なプログラムである。
本発明のプログラムは、前記収束判定処理において、前記検出処理を行うとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とするコンピュータが実行可能なプログラムである。
【００２０】
本発明のプログラムは、複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成処理を有することを特徴とするコンピュータが実行可能なプログラムである。
本発明のプログラムは、前記クラスタリング結果再構成処理において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とするコンピュータが実行可能なプログラムである。
【発明の効果】
【００２１】
以上説明したように、本発明によれば、クラスタラベル番号と、このクラスタラベル番号に含まれるデータのデータ番号との対応を示す表を用い、データが共有されるクラスタを順次結合し、新たなクラスタとして生成するため、類似性を演算してクラスタを結合させる従来例とことなり、特別に複雑な演算をすることなく、設定された閾値組に対応したクラスタリングを高速に行うことができるという効果が得られる。
【００２２】
また、本発明によれば、複数の閾値組（類似性閾値，密度閾値）を用いて、各閾値組毎にクラスタリングを行うことにより、各閾値組に対応するクラスタを生成し、これらのクラスタを閾値組の順番、すなわち緩い閾値から厳しい閾値まで順に並べることにより、階層構造クラスタリングに比較して短い時間で、容易にツリー構造を構成するという効果が得られる。
【発明を実施するための最良の形態】
【００２３】
本発明のクラスタリングシステムは、分類対象の各データの類似性の基準を用い、この基準に対する閾値を設定してクラスタリングを行うものである。
この類似性の基準としては、２つのデータが似ているか否かを測るための指標として、類似度または非類似度が用いられる。
データ間の類似性を示す距離は非類似度を表すための典型的な例であり、一方、相関係数は類似度の典型的な例である。
本発明のクラスタリングシステムは、類似性を示す基準として、類似度及び非類似度いずれを使用しても構わず、種々の類似性の定義を用いて、クラスタリングを行うことができる。
以降の説明において、非類似度の表現を用いるが、非類似度の閾値に対する大小関係を逆にすることにより、類似度に置き換えても同様である。
【００２４】
以下、本発明の一実施形態によるクラスタリングシステムを図面を参照して説明する。図１は同実施形態の構成例を示すブロック図である。
データベースＤＢは、大容量のデータの取り扱いに対応できるＲＤＢＭＳ（Relational DataBase Management System）が用いられており、クラスタリングの対象となるデータを格納している。
今まで、多くのクラスタリングシステムには、主記憶装置を使用することが前提とされていた。しかしながら、主記憶装置は高速にアクセス可能であるが、容量としては限られてしまう。
一方、本発明のクラスタリングシステムは、ＲＤＢＭＳを用いるために、主記憶容量の制限を受けることがない。
【００２５】
この図において、クラスタリング制御部１は、非類似度閾値ε及び密度閾値ρの閾値組を、厳しい閾値から緩い閾値まで、複数の段階に分割された閾値組｛（ε1，ρ1），（ε2，ρ2），…，（εｍ，ρｍ）｝が予め設定され、クラスタリングに際して、各閾値組を選択して、類似度集合抽出部２へ非類似度閾値εを出力し、データ抽出部４へ密度閾値ρを出力する。
ここで、クラスタリング制御部１は、厳しい非類似度閾値及び密度閾値の閾値組から、緩い非類似度閾値及び密度閾値の閾値組まで、各閾値組におけるクラスタリングが終了すると、次の閾値組を選択して、類似度集合抽出部２へ非類似度閾値を出力し、データ抽出部４へ密度閾値ρを出力し、対応表生成部６に初期クラスタを出力する。
【００２６】
類似度集合抽出部２は、入力される非類似度閾値εにより、データベースＤＢにおけるクラスタリング対象の全データポイント（データの有する複数の評価値をそれぞれ次元として、この評価値の次元の空間におけるデータの座標位置）の集合Ｘから、２つのデータポイント同士の値の非類似度の集合Ｄを生成する。
Ｘ：＝｛ｘ1，ｘ2，…，ｘn｝
Ｄ≡｛ｄ(ｉ，ｊ)｜ｉ，ｊ∈Ｘ｝
また、類似度集合抽出部２は、上記集合Ｄにおいて、所定の非類似度閾値ε範囲の類似性を有するデータポイントの組み合わせ、例えば、非類似度が上記非類似度閾値以下となるデータポイントの組合せのデータの集合Ｄεを抽出する。
Ｄε≡｛ｄ(ｉ，ｊ)∈Ｄ｜ｄ(ｉ，ｊ)≦ε｝
【００２７】
データ抽出部４は、集合Ｘに含まれる各々のデータを対象データとし、この対象データを中心として、この中心のデータポイントから上記非類似度閾値εの範囲内で計算可能なデータ密度が、所定の密度閾値ρ以上である対象データの集合ＸCOREを抽出する。
ＸCORE≡｛ｘ∈Ｘ｜ρ｜ε(ｘ)≧ρ｝
クラスタリング制御部１は、データ抽出部４の結果を受け取り、直前に行われた閾値組のクラスタリング結果と結合して初期のクラスタＱを生成し、対応表生成部６へ出力する。
【００２８】
対応表生成部６は、各クラスタに含まれる対象データから非類似度閾値ε以内に存在する対象データの中の最も小さい番号をクラスタラベル番号として、このクラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータポイントのデータ番号の対応表（図３参照）を生成する。
リスト入替部７は、上記対応表により、クラスタラベル番号であるデータポイントが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号（すなわち、現在のクラスタにおいて最も小さいが、他のクラスタに属していることが検出されたデータポイントのデータ番号）を、上記他のクラスタのクラスタラベル番号に書き換える。
【００２９】
ここで、あるクラスタＣ1のクラスタラベル番号となっているデータポイントが、他のクラスタラベル番号のクラスタＣ2に属しているとき、他のクラスタＣ2のクラスタラベル番号が当然にクラスタＣ1のクラスタラベル番号より小さい構造となっている。
また、リスト入替部７は、書き換え前と書き換え後との対応表が同一、すなわち対応表に変化が無くなることを検出するまで書き換え処理を行う。
収束判定部８は、上記リスト入替部７がクラスタラベル番号を書き換えることにより生成されたクラスタ間において、非類似度閾値ε範囲内のデータポイントが異なったクラスタに含まれているか否かを検出する。
【００３０】
また、収束判定部８は、上記検出処理において、非類似度閾値ε範囲内のデータポイントが異なったクラスタに含まれていることを検出した場合、これらのデータポイントの含まれるクラスタ同士を結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とする。
クラスタリング制御部１は、リスト入替部７におけるクラスタラベルの書き換え処理と、収束判定部８における閾値ε範囲内のデータが異なったクラスタに含まれているか否かの検出処理とが、双方の処理結果が収束するまで行わせる。
また、クラスタリング再構成部５は、各非類似度閾値ε及び密度閾値ρの閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、上記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より条件の一つ厳しい閾値組のクラスタをクラスタリング結果とする。
すなわち、クラスタリング再構成部５は、クラスタに属するデータ間の非類似度の比較を行うことで、設定された非類似度範囲内にないデータポイントを含むクラスタを淘汰し、得られた複数の閾値組に対するクラスタリング結果を再構成し、再構成された各閾値組におけるクラスタリング結果を、全体として一つのクラスタリング結果として抽出する。
【００３１】
次に、図１に示すクラスタリングシステムのクラスタリングの動作を図２を参照して説明する。図２は、図１のクラスタリングシステムの動作例を示すフローチャートである。
クラスタリングを行うために、２つのデータが似ているか否かを判定するのに、類似度及び非類似度のいずれを用いても同様な処理を行うことが可能であるが、以下の説明においては、非類似度を用いたクラスタリングについて
ステップＳ１において、クラスタリング制御部１は、まず、複数の非類似度閾値と密度閾値の閾値組｛（ε１，ρ１），（ε２，ρ２），．．．，（εｍ，ρｍ）｝を、設定する。この各閾値組の非類似度閾値と密度閾値は後述するツリー構造を作成するための基準を満たしている必要がある。
そして、クラスタリング制御部１は、このなかから、厳しい条件の閾値組を選択して、順次、厳しい条件の閾値組から順番に、クラスタリングの処理を実施していく。
【００３２】
ステップＳ２において、類似集合抽出部２は、クラスタリング制御部１の選択した非類似度閾値εが入力されると、
全データポイント
Ｘ：＝｛ｘ1，ｘ2，…，ｘn｝
に含まれるデータポイント同士の非類似度の集合Ｄ
Ｄ≡｛ｄ(ｉ，ｊ)｜ｉ，ｊ∈Ｘ｝
を生成する。
そして、類似集合抽出部２は、非類似度が非類似度閾値ε以下となるデータ間の組み合わせの集合Ｄε
Ｄε≡｛ｄ(ｉ，ｊ)∈Ｄ｜ｄ(ｉ，ｊ)≦ε｝
を、集合Ｄから抽出する。
【００３３】
データ抽出部４は、クラスタリング制御部１から入力される密度閾値ρにより、各データポイントにおけるデータ密度が密度閾値ρ以上のデータポイントを抽出する。ここで、密度定義の例として、「半径ε（非類似度閾値）以内に含まれるデータポイントの数」を採用することもできる。
すなわち、
ρ｜ε（ｘ）≧ρ
であり、左辺の密度ρはεを母数（パラメータ）とする密度計算のための関数であり、右辺のρは設定された密度閾値であり、密度計算は、ε以内の非類似度のみが影響を及ぼすような計算方法を用いる。
【００３４】
そして、データ抽出部４は、周囲に所定の密度を有するデータポイントとして、Ｘの部分集合ＸCOREを、
ＸCORE≡｛ｘ∈Ｘ｜ρ｜ε (ｘ)≧ρ｝
として求める。
これにより、非類似度が大きいもの、及び周囲に他のデータポイントが少なく、クラスタが生成される可能性がないデータポイントを排除する。
【００３５】
次に、ステップS３において、クラスタリング制御部１は、クラスタリングに対する初期値、すなわち初期のクラスタを定義することとなる。
ここで、クラスタリング制御部１は、データ抽出部４の抽出した各データポイントの所属するクラスタを表現するため、各クラスタに対してクラスタラベルを与える。
また、クラスタリング制御部１は、クラスタの初期値として、直前に実行された閾値組に対する結果を初期クラスタとする。また、この中に含まれておらず、ＸCOREに含まれているデータポイントは、おのおの一つのクラスタとする。
【００３６】
そして、対応表生成部６は、クラスタリング対象のデータポイントの集合ＸCOREにおいて、クラスタに所属するデータポイントから、非類似度が非類似度閾値ε以内のデータポイントの集合を見つけ出し、この集合に含まれる最も小さなデータポイント番号をクラスタのラベル番号（クラスタを代表する番号）として、図３に示す対応表を生成する（ステップＳ３）。
ここで、対応表生成部６は、クラスタラベル番号を付加することにより、すなわち最も小さいデータポイント番号を代表してクラスタラベル番号としたクラスタをクラスタＱとする。
【００３７】
次にステップＳ４において、リスト入替部７は、図３に示す対応表を用いて、類似するクラスタＱ間の接続処理を行う。
この時点において、クラスタと見なされているクラスタＱは、上記クラスタラベル番号により代表されるデータポイントの集合である。
次に、図４を用いて、リスト入替部７によるクラスタＱ間の接続処理を説明する。
図４においては、右の表のデータポイント番号をＡ、クラスタラベル番号をＢとし、また左の表のデータポイント番号をＣ、クラスタラベル番号をＤとする。なお、図４の右及び左の２つの表は全く同一のデータの対応、すなわち図３の表を示すものである。
【００３８】
そして、リスト入替部７は、図３における上記クラスタラベル番号を参照しつつ、図４に示すように、右の表のクラスタラベル番号（B）をデータポイント番号と見なして、左の表のデータポイント番号（C）と比較し、そのデータポイント番号（C）に対応する左のテーブルのクラスタラベル番号（D）を読みとり、クラスタラベル番号（B）をこのクラスタラベル番号（D）に変更する処理を行う。
例えば、リスト入替部７は、データポイント番号３（Ａ）がクラスタラベル番号１（Ｂ）に対応していることを検出し、そして、このクラスタラベル番号１（Ｂ）が左のテーブルにおいて、データポイント番号１（Ｃ）に対応していることを検出し、さらに、このデータポイント番号１（Ｃ）がクラスタラベル番号１（Ｄ）に対応していることを検出する。
【００３９】
そして、リスト入替部７は、クラスタラベル番号１（Ｂ）及びクラスタラベル番号１（Ｄ）の番号が一致しているため、すなわち、すでに同一のクラスタに属しているとして番号を変更する必要がないことを検出する。
一方、リスト入替部７は、データポイント番号４（Ａ）がクラスタラベル番号３（Ｂ）に対応していることを検出し、これは、クラスタラベル番号３（Ｂ）が左のテーブルにおいてデータポイント番号３（Ｃ）に対応していることを検出する。
さらに、リスト入替部７は、データポイント番号３（Ｃ）がクラスタラベル番号１（Ｄ）に対応していることを検出する。
これにより、リスト入替部７は、クラスタラベル番号３（Ｂ）とクラスタラベル番号１（Ｄ）が相違しているため、同一のクラスタに属していないことを検出して、データポイント番号４（Ａ）に対応するクラスタ番号を１（Ｄ）に変更する。
これにより、リスト入替部７は、クラスタＱが複数結合されたクラスタＲを作成する。
【００４０】
次に、ステップＳ５において、リスト入替部７は、テーブルにおける全てのクラスタラベル番号（Ｂ）が変化しない状態となることを検出すると、すなわち、データポイント番号３（Ｂ）のように、対応表を辿っていっても、その先のクラスタラベル番号（Ｄ）が、対象となるデータポイントの含まれるクラスタにおける最も小さなデータポイント番号であると、ステップＳ５の処理を停止し、処理をステップＳ６へ進める。
一方、リスト入替部７は、対応表において、１つでもクラスタラベル番号（Ｂ）が変化した場合、ステップＳ４の処理を繰り返す。
【００４１】
上述したステップＳ４及びステップＳ５において、表におけるリストの入れ替え処理により、データ番号を辿っていくことによりたどり着けるもっとも小さな番号をクラスタラベル番号として持つことになる。すなわち、あるクラスタＱ１に含まれていたデータポイントと他のクラスタＱ２に含まれていたデータポイントが接続されているという状況があった場合に、この２つのクラスタＱ１，Ｑ２が結合され、より大きなクラスタＲに成長していくこととなる。
しかしながら、上述したステップＳ４の処理は、単なる図３の対応表を用いた番号の操作なので、複雑な形状のクラスタに対しては、十分な収束をせず、非類似度の小さなデータポイントを有したクラスタＱが分割された状態のままとなる可能性がある。
たとえば、データポイント番号が大きいデータポイント同士がまとまり、クラスタが接続されている場合、上述したように、ステップＳ４及びＳ５の操作では収束しない。
【００４２】
上述した収束しない場合を検討すると、隣接しているクラスタ間において、図５の様に、データポイント１，３及び５がクラスタＱ１を形成し、また、データポイント２，４及び６がクラスタＱ２を形成しているとする。
このとき、データポイント５及び６が、非類似度において、非類似度閾値εより小さく、類似しているため、この２つのクラスタＱ１及びＱ２は結合処理されなければならないが、クラスタＱ１はクラスタラベル番号１に収束しており、クラスタＱ２はクラスタラベル番号２に収束している。
このため、ステップＳ４及び５における処理では、大きなデータポイント番号が小さなデータポイント番号に置き換えられてしまうため、直接データポイント５及び６が直接に非類似度の検出が行われず、また置き換えられたデータポイント番号１及び２が非類似度閾値εより大きな非類似度であるため、直接の対応関係になく、クラスタＱ１及びＱ２がリスト入れ替え処理のみで結合されることはない。
【００４３】
上述したクラスタが無くなるように、ステップＳ６においては、本来、結合するデータポイントを有するクラスタの検出処理を行う。
すなわち、ステップＳ６において、収束判定部８は、集合Ｄεに含まれるデータポイント番号の組み合わせにおいて、異なったクラスタラベル番号と対応関係となっているデータポイント番号の有無の検出を行う。
これにより、収束判定部８は、非類似度が非類似度閾値より小さなデータポイント同士が異なったクラスタに属していることを検出すると、全体としてクラスタリングの処理が収束していないとして、処理をステップＳ７へ進める。
一方、収束判定部８は、非類似度が非類似度閾値より小さなデータポイント番号の組み合わせにおいて異なったクラスタに属していないことを検出すると、全体としてクラスタリングの処理が収束しているとして、処理をステップＳ８へ進める。
【００４４】
次に、ステップＳ７において、収束判定部８は、ステップＳ６において検出された、異なったクラスタ間で、それぞれ有するデータポイントの間の非類似度が非類似度閾値より小さなデータポイントの組み合わせを検出した場合、これらのデータポイントを含むクラスタＱを結合させ、新たなクラスタＲを生成する。
このとき、このクラスタＲに含まれるデータポイントにおいて、最も小さなデータポイント番号を、このクラスタＲを代表するクラスタラベル番号とし、テーブルのデータポイント番号（Ｃ）に対応するクラスタラベル番号（Ｄ）を書き換え、処理をステップＳ４へ戻し、再度、図３の対応表を用いたリスト入替処理を行う。
【００４５】
例えば、図５において、クラスタＱ１及びクラスタＱ２が合成されることにより、クラスタＲが生成され、このクラスタＲのクラスタラベル番号はクラスタＱ１及びＱ２双方における最も小さなデータポイント番号１とされる。
つまり、図３に示すテーブルにおいて、データポイント番号１，２，３，４，５，６のデータポイント各々が、クラスタラベル番号１のクラスタに属するように書き換えられる。
【００４６】
上述したように、図４に示す表を用いて、各データポイントのデータポイント番号に対応するクラスタラベル番号を、このデータポイントが属しているクラスタのクラスタラベル番号（クラスタ内で最も小さなデータポイント番号）に変更する処理（ステップＳ４及び５）と、図３のテーブル及び集合Ｄεを用いた収束判定の処理（ステップＳ６）と、収束判定において収束されていない場合に行うクラスタの結合処理と、の３つの操作を、ステップＳ６の収束判定で収束されていることが検出されるまで繰り返すことにより、集合Ｄεの非類似度の集合に関連するデータポイントの集合を、非類似度閾値εで設定された範囲での類似度を有するクラスタに分類することができる。
【００４７】
次に、ステップＳ８において、クラスタリング制御部１は、あらかじめ設定されている閾値組｛（ε１，ρ１），（ε２，ρ２），……，（εｍ，ρｍ）｝の全てが終了したか否かの検出を行う。
そして、クラスタリング制御部１は、閾値組（εｉ，ρｉ）が終了したことを検出すると、全ての閾値組のクラスタリングが終了していないことを検出して、処理をステップＳ２に戻し、次に設定された閾値組に対応したクラスタリングの処理を行う。
このとき、閾値組の非類似度閾値及び密度閾値が序々に緩くなるように、（εｍ，ρｍ）→…→（ε２，ρ２）→（ε１，ρ１）と順次設定して、各非類似度閾値毎にステップＳ２からステップＳ８の処理を行い、各比類似度閾値及び密度閾値の組毎のクラスタリングを行う。
一方、クラスタリング制御部１は、予め設定した閾値の組み合わせ（例えば、｛（ε１，ρ１），（ε２，ρ２），……，（εｍ，ρｍ）｝）における全ての閾値に対してクラスタリングが行われたことを検出すると、処理をステップＳ９へ進める。
【００４８】
各々の閾値組において生成されたクラスタは、図６に示すように、各々他の閾値組により生成されたクラスタと交わることはなく、各々のクラスタはより緩い閾値組で生成されたクラスタに含まれるようにできる。
すなわち、緩い閾値を有する閾値組で生成されたクラスタと、厳しい閾値を有する閾値組で生成されたクラスタとは包含関係（緩い閾値を有する閾値組のクラスタが厳しい閾値を有する閾値組のクラスタを包含する）にできる。これは、密度関数・閾値の与え方に依存する。
例えば、非類似度として距離を、密度関数として、「半径ε以内に存在するデータポイントの数」を採用した場合には、密度閾値として一定値を採用し、非類似度閾値として、厳しい方として小さい値を使用し、緩い方として大きい値を採用する。
次に、ステップＳ９において、クラスタリング結果再構成部５は、閾値組が緩くなる方向に順次並べることにより、各閾値組で生成されたクラスタを上記包含関係とすることができ、図６に示すようにツリー構造を構成する。
すなわち、クラスタリング結果再構成部５は、複数の閾値組（閾値，密度閾値）を用い、各閾値組毎にクラスタリングが行われることにより得られた、クラスタを閾値組の順番に、すなわち緩い閾値から厳しい閾値まで順に並べることにより、階層構造クラスタリングに比較して短い時間で、ツリー構造を容易に構成する。
【００４９】
このツリー構造において、多くの閾値を設定することにより、クラスタの分類を細かくして、微妙なツリー構造を確認することもでき、また、大雑把なクラスタの状態を確認するために、閾値を所定の幅を有する間隔で区切って設定することもできる。
上述した閾値は、クラスタの生成状態を確認してユーザが設定しても良いし、また、以下の様に集合Ｄにおいて、含まれるデータポイントの組み合わせにおける非類似度を求め、順位（Rank）という考え方を用いて、システムにより設定するようにしても良い。
【００５０】
ここで順位は、例えば、
Rank：＝１０Ｎ／６
で定義され、上記式において、Ｎ＝１，２，…である。
ε10＝（１０１／６ ≒１番目に小さな非類似度）
ε9＝（１０２／６ ≒２番目に小さな非類似度）
ε8＝（１０３／６ ≒３番目に小さな非類似度）
ε7＝（１０４／６ ≒４番目に小さな非類似度）
ε6＝（１０５／６ ≒６番目に小さな非類似度）
ε5＝（１０６／６ ≒１０番目に小さな非類似度）
ε4＝（１０７／６ ≒１４番目に小さな非類似度）
ε3＝（１０８／６≒２１番目に小さな非類似度）
ε2＝（１０９／６ ≒３１番目に小さな非類似度）
ε1＝（１０１０／６≒４６番目に小さな非類似度）
のように、各々何番目に小さい非類似度により（非類似度の順位を基準として）設定しても良い。
ε10は「１.４６７７…」、ε9は「２.１５４４…」となり、非類似度閾値が設定されることとなる。
【００５１】
ツリー構造を作成した結果、図７に示すように、非常に複雑な形状をしたクラスタが生成されることがある。図７は、類似度を演算する次元が２次元の場合に、平面にクラスタ形状を示す画像が表示されている図である。
等高線のように示される表示の濃さは、各非類似度閾値におけるクラスタ形状を示すものであり、上述したように包含関係にあるため、色の濃い部分はより小さな非類似度閾値によりクラスタリングされたものである。
【００５２】
図７に示すように、非常に複雑な形状を示すクラスタが生成される場合もあり、複雑な形状を認める場合にはこの状態で構わないが、より含まれるデータポイント相互の関連性が高いクラスタを得たい場合には、より円（高次元の場合は超球）に近い単純な形状のクラスタを得ることが必要なため、クラスタリング結果再構成部５は、複数の非類似度閾値により得られたツリー構造のなかから、概略の直径（クラスタに含まれるデータポイントの組合せで最も類似性がないものの非類似度または類似度）が制限値（クラスタの大きさを制限するために予め設定されている非類似度または類似度のクラスタ閾値）以下のクラスタを適切なクラスタとして抽出する。
具体的には、クラスタリング結果再構成部５は、一つのデータポイントに着目し、閾値の厳しい方から順番に処理を行い、上記制限値を超える直前の閾値におけるクラスタリング結果を適切なクラスタとして抽出する。
【００５３】
なお、図１に示すクラスタリングシステムの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりクラスタリングを行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００５４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００５５】
【図１】本発明の一実施形態によるクラスタリングシステムの構成を示すブロック図である。
【図２】図１のクラスタリングシステムの動作例を示すフローチャートである。
【図３】図１の対応表生成部６により生成される対応表の構造を示す概念図である。
【図４】図１のリスト入替部７の動作を説明するための概念図である。
【図５】図１の収束判定部８のクラスタの結合動作を説明するための概念図である。
【図６】図１のクラスタリングシステムによるツリー構造生成処理を説明する概念図である。
【図７】図１のクラスタリングシステムにより生成されたクラスタの形状を示すものであり、緩い閾値組で生成されたクラスタがより厳しい閾値組で生成されたクラスタを包含していることを示す概念図である。
【符号の説明】
【００５６】
１…クラスタリング制御部
２…類似度集合抽出部
４…データ抽出部
５…クラスタリング結果再構成部
６…対応表生成部
７…リスト入替部
８…収束判定部
ＤＢ…データベース
【特許請求の範囲】
【請求項１】
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出部と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出部と、
各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成部と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と、
を有し、
前記リスト入替部が、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするクラスタリングシステム。
【請求項２】
前記リスト入替部がクラスタラベルを書き換えることにより生成されたクラスタ間において、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする請求項１記載のクラスタリングシステム。
【請求項３】
前記収束判定部が、前記検出処理において、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項２記載のクラスタリングシステム。
【請求項４】
前記リスト入替部におけるクラスタラベルの書き換え処理と、閾値範囲内のデータが異なったクラスタに含まれているか否かの検出処理とを、双方の処理結果が収束するまで行うことを特徴とする請求項２または請求項３に記載のクラスタリングシステム。
【請求項５】
前記類似性閾値及び密度閾値の閾値組が複数設定され、条件の厳しい閾値組から緩い閾値組へ順次、組毎の条件によりクラスタリングを実施するクラスタリング制御部を有することを特徴とする請求項１から請求項４のいずれかに記載のクラスタリングシステム。
【請求項６】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成することを特徴とする請求項５に記載のクラスタリングシステム。
【請求項７】
各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似性が所定の設定非類似性より大きいか否かの検出を行い、前記設定非類似性より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とするクラスタリング再構成部を有することを特徴とする請求項６に記載のクラスタリングシステム。
【請求項８】
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出過程と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出過程と、
各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成過程と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替過程と、
を有し、
前記リスト入替過程において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするクラスタリング方法。
【請求項９】
前記リスト入替過程において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定過程を有することを特徴とする請求項８記載のクラスタリング方法。
【請求項１０】
前記収束判定過程において、前記検出処理のとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項９記載のクラスタリング方法。
【請求項１１】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成過程を有することを特徴とする請求項１０記載のクラスタリング方法。
【請求項１２】
前記クラスタリング結果再構成過程において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする請求項１１に記載のクラスタリング方法。
【請求項１３】
複数のデータに対して、各々のデータの類似性に基づいてクラスタリングを行うクラスタリングプログラムであり、
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する組合集合抽出処理と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出処理と、
各クラスタに含まれる対象データから類似性閾値範囲以内に存在する対象データの中の最も小さな番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成処理と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替処理と、
を有し、
前記リスト入替処理において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理とを有することを特徴とするコンピュータが実行可能なプログラム。
【請求項１４】
前記リスト入替処理において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする請求項１３記載のコンピュータが実行可能なプログラム。
【請求項１５】
前記収束判定処理において、前記検出処理を行うとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項１４記載のコンピュータが実行可能なプログラム。
【請求項１６】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成処理を有することを特徴とする請求項１５記載のコンピュータが実行可能なプログラム。
【請求項１７】
前記クラスタリング結果再構成処理に措いて、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする請求項１６に記載のコンピュータが実行可能なプログラム。
【請求項１】
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出部と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出部と、
各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成部と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替部と、
を有し、
前記リスト入替部が、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするクラスタリングシステム。
【請求項２】
前記リスト入替部がクラスタラベルを書き換えることにより生成されたクラスタ間において、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする請求項１記載のクラスタリングシステム。
【請求項３】
前記収束判定部が、前記検出処理において、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項２記載のクラスタリングシステム。
【請求項４】
前記リスト入替部におけるクラスタラベルの書き換え処理と、閾値範囲内のデータが異なったクラスタに含まれているか否かの検出処理とを、双方の処理結果が収束するまで行うことを特徴とする請求項２または請求項３に記載のクラスタリングシステム。
【請求項５】
前記類似性閾値及び密度閾値の閾値組が複数設定され、条件の厳しい閾値組から緩い閾値組へ順次、組毎の条件によりクラスタリングを実施するクラスタリング制御部を有することを特徴とする請求項１から請求項４のいずれかに記載のクラスタリングシステム。
【請求項６】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成することを特徴とする請求項５に記載のクラスタリングシステム。
【請求項７】
各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似性が所定の設定非類似性より大きいか否かの検出を行い、前記設定非類似性より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とするクラスタリング再構成部を有することを特徴とする請求項６に記載のクラスタリングシステム。
【請求項８】
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する類似集合抽出過程と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出過程と、
各クラスタに含まれるデータから類似性閾値範囲以内に存在するデータのデータポイント番号の中から最も小さな番号を抽出し、このデータのデータ番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成過程と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替過程と、
を有し、
前記リスト入替過程において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理を行うことを特徴とするクラスタリング方法。
【請求項９】
前記リスト入替過程において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定過程を有することを特徴とする請求項８記載のクラスタリング方法。
【請求項１０】
前記収束判定過程において、前記検出処理のとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項９記載のクラスタリング方法。
【請求項１１】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成過程を有することを特徴とする請求項１０記載のクラスタリング方法。
【請求項１２】
前記クラスタリング結果再構成過程において、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする請求項１１に記載のクラスタリング方法。
【請求項１３】
複数のデータに対して、各々のデータの類似性に基づいてクラスタリングを行うクラスタリングプログラムであり、
クラスタリング対象のデータから、所定の類似性閾値範囲の類似性を有するデータの組合わせの集合を抽出する組合集合抽出処理と、
各々のデータを対象データとし、この対象データを中心として、この中心から前記類似性閾値範囲内から計算可能なデータ密度が、所定の密度閾値以上である対象データの集合を抽出するデータ抽出処理と、
各クラスタに含まれる対象データから類似性閾値範囲以内に存在する対象データの中の最も小さな番号をクラスタラベル番号として、クラスタラベル番号及びこのクラスタラベル番号の示すクラスタに含まれるデータのデータポイント番号の対応表を生成する対応表生成処理と、
前記対応表により、クラスタラベル番号であるデータが、他のクラスタに属しているか否かの検出を行い、他のクラスタに属していることが検出されると、このクラスタラベル番号を、他のクラスタのクラスタラベル番号に書き換えるリスト入替処理と、
を有し、
前記リスト入替処理において、書き換え前と書き換え後との表が同一となることを検出するまで書き換え処理とを有することを特徴とするコンピュータが実行可能なプログラム。
【請求項１４】
前記リスト入替処理において、クラスタラベルを書き換えることにより生成されたクラスタ間に、前記閾値範囲内のデータが異なったクラスタに含まれているか否かを検出する収束判定部を有することを特徴とする請求項１３記載のコンピュータが実行可能なプログラム。
【請求項１５】
前記収束判定処理において、前記検出処理を行うとき、異なったクラスタに含まれていることを検出した場合、これらのクラスタを結合させ、結合により生成されたクラスタのクラスタラベル番号を、結合したクラスタのクラスタラベル番号の内、最も小さなクラスタラベル番号とすることを特徴とする請求項１４記載のコンピュータが実行可能なプログラム。
【請求項１６】
複数の閾値組で生成されたクラスタを、順次、閾値組の条件が緩くなる方向に並べることにより、クラスタのツリー構造を生成するクラスタリング結果再構成処理を有することを特徴とする請求項１５記載のコンピュータが実行可能なプログラム。
【請求項１７】
前記クラスタリング結果再構成処理に措いて、各閾値組で生成されたクラスタにおいて、それぞれのクラスタで最も類似性のないデータ間の非類似度が所定の設定非類似度より大きいか否かの検出を行い、前記設定非類似度より大きいクラスタを検出した場合、検出されたクラスタが生成された閾値組より一つ条件の厳しい閾値組におけるクラスタリング結果を目的の結果とすることを特徴とする請求項１６に記載のコンピュータが実行可能なプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−３９９７０（Ｐ２００６−３９９７０Ａ）
【公開日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願番号】特願２００４−２１９２８５（Ｐ２００４−２１９２８５）
【出願日】平成１６年７月２７日（２００４．７．２７）
【出願人】（５９７１２８００４）国立医薬品食品衛生研究所長 (22)
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【Ｆターム（参考）】
【公開日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願日】平成１６年７月２７日（２００４．７．２７）
【出願人】（５９７１２８００４）国立医薬品食品衛生研究所長 (22)
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【Ｆターム（参考）】
[ Back to top ]