(57)【要約】【課題】大分類処理と詳細分類処理の２段階処理により大規模データ集合をクラスタリングする場合、大分類処理の結果得られる各部分クラスタの局所的な密度に関する属性を詳細分類処理において適切に扱い、これによって高精度なクラスタリング結果を得ることができるデータ処理システム及びデータ処理プログラムを提供する。【解決手段】データ処理システムのデータ処理装置は、大分類手段としてデータ集合（入力データ集合）をＳ１０で部分クラスタの集合に変換し、詳細分類手段として、部分クラスタの集合をクラスタリングするにあたり、Ｓ２０で部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行う。【選択図】図２
2010134632.tif 000002
【特許請求の範囲】
【請求項１】
所定次元数のベクトルデータの集合として与えられる入力データ集合をクラスタリングするデータ処理システムであって、
入力データ集合を部分クラスタの集合に変換する大分類手段と、
前記大分類手段が変換した前記部分クラスタの集合をクラスタリングする詳細分類手段とを備え、
前記詳細分類手段は前記大分類手段が変換した前記部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行うことを特徴とするデータ処理システム。
【請求項２】
前記大分類手段は、
前記入力データ集合を部分クラスタの集合に変換された後の該部分クラスタの集合を記憶する記憶手段を備え、
さらに前記大分類手段は、
前記記憶手段が記憶している部分クラスタの集合の中から、処理対象のデータに最も近い部分クラスタである最近隣部分クラスタを探索する最近隣部分クラスタ探索手段と、
前記処理対象のデータを前記最近隣部分クラスタに追加するべきか否かを判定する追加可否判定手段と、
前記追加可否判定手段による判定結果に基づいて前記最近隣部分クラスタへの前記処理対象のデータの追加処理及び前記処理対象のデータについて新規の部分クラスタの生成処理のいずれかの処理を行う部分クラスタ集合更新手段とを備え、
前記追加可否判定手段は、前記入力データ集合から前記処理対象のデータを１個読み出すたびに最近隣部分クラスタ探索と追加可否判定を行い、前記部分クラスタ集合更新手段は、前記いずれかの処理を行うことを特徴とする請求項１に記載のデータ処理システム。
【請求項３】
前記詳細分類手段は、
各部分クラスタの重心位置座標を該各部分クラスタの代表点とし、この代表点を起点として確率密度関数の極大点を探索する極大点探索手段と、  前記極大点探索手段による極大点探索が収束したかどうかを極大点探索を行った前回値と今回値の各部分クラスタに対する局所平均ベクトル間の距離情報に基づいて判定する収束判定手段と、
同一または近傍の極大点に収束した部分クラスタ群を同じクラスタに属するものとして分類する部分クラスタ分類手段とを備え、
前記極大点探索手段は、前記各部分クラスタに属するサンプル数を当該各部分クラスタの重みとして極大点探索を行うことを特徴とする請求項１または請求項２に記載のデータ処理システム。
【請求項４】
前記極大点探索手段において、局所近傍範囲を定めるパラメータを前記各部分クラスタごとに可変とし、前記各部分クラスタのうち、局所的な密度が大きい部分クラスタに対しては前記パラメータを小さく、局所的な密度が小さい部分クラスタに対しては前記パラメータを大きくするように制御することを特徴とする請求項３に記載のデータ処理システム。
【請求項５】
前記極大点探索手段は、入力データの各次元に対し個別に局所的な密度を算出し、この密度に応じて各次元に対し個別に前記パラメータを制御することを特徴とする請求項４に記載のデータ処理システム。
【請求項６】
所定次元数のベクトルデータの集合として与えられる入力データ集合をクラスタリングするデータ処理システムのプログラムであって、
コンピュータを、
入力データ集合を部分クラスタの集合に変換する大分類手段として機能させ、
さらに、前記大分類手段が変換した前記部分クラスタの集合をクラスタリングする詳細分類手段として機能させ、
かつ、前記詳細分類手段として機能させる際に、前記大分類手段が変換した
前記部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行わせることを特徴とするデータ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ集合のクラスタリングに関し、詳細には大規模データ集合をクラスタリングするデータ処理システム及びデータ処理プログラムに関する。
【背景技術】
【０００２】
与えられたデータ集合を、クラスタの種類や数などの外的基準なしに分類する技術はクラスタリングまたはクラスタ分析と呼ばれ、代表的アルゴリズムとしてk−平均法（c-平均法とも呼ばれる）や併合型階層的クラスタリング（非特許文献１）がよく知られている。
【０００３】
一方、非特許文献１の正規混合分布モデル（Gaussian Mixture Model）はデータ集合から確率密度関数を推定する一手法であるが、確率密度関数から各データのクラスタ所属確率を計算することができるため、クラスタリング手法の一つとみなせる。確率密度推定に基づくクラスタリング手法としては、他に平均移動法（Mean Shift：非特許文献２）や、これを改良した拡張平均移動法（Extended Mean Shift:非特許文献３）も知られている。
【０００４】
これら従来のクラスタリング手法では、実行にあたってまずデータ集合全体をメモリ上に読み込む必要がある。個々のデータが所定次元数（＝Ｄ）のベクトルとして表現されている場合、Ｎ個のデータからなるデータ集合を保持するメモリ容量はＤ×Ｎに比例するため、対象とするデータ集合が大規模になると全データをメモリ上に保持することが不可能となる。例えば５００次元・１００万個のデータ集合を３２ビット倍精度で保持するのに必要なメモリ容量は４ＧＢであり、一般的なパーソナルコンピュータでは扱うことができない。対象がここまで大規模でなくても、上述した既存クラスタリング手法の多くは計算時間がＮ2に比例して増加するため、大規模データに対しては実用的な時間で処理が終えられない状況に陥る。
【０００５】
このような大規模データを扱うための技術として、データスカッシングと呼ばれる技術が開発されている。データスカッシングでは、メモリに収まらないような大規模なデータ集合を１個ずつ順次読み出しながら、１パスで元のデータ集合より大幅に小規模なデータ集合に変換する。そして、変換後のデータに対して既存の各種アルゴリズムを適用する。すなわち、データスカッシングは大規模データに対する一種の前処理技術である。
【０００６】
データスカッシングの代表的な手法の一つとしてＢＩＲＣＨ（Balanced Iterrative Reducing and Clusterring using Hierarchies:非特許文献４）が知られている。ＢＩＲＣＨでは、元のデータ集合であるＸ＝｛x1,x2,...,xN｝を部分クラスタ（すなわちクラスタの一部）の集合Ｖ＝｛v1,v2,...,vM｝に変換する。Ｎ>>Ｍであるため、Ｖに対して既存クラスタリング手法を適用することが可能である。特許文献１では、データスカッシングと既存クラスタリング手法を組み合わせた方式が記載されている。この方式は、ＢＩＲＣＨによる大分類処理（特許文献１ではオンライン・マイクロクラスタリングと称している）とk−平均法による詳細分類処理（特許文献１ではオフライン・マクロクラスタリングと称している）から構成されている。なお、非特許文献５は、本発明の出願時の技術水準を示す。
【特許文献１】特開２００５−１００３６３号公報
【非特許文献１】宮本定明、「クラスター分析入門」、森北出版、1999
【非特許文献２】ケー・フクナガ(K.Fukunaga)，「スタティスティカル  パターン  レコグニション（セカンド  エディション）(Statistical Pattern Recognition (second edition)」、Academic Press、1990
【非特許文献３】若原徹  他、「拡張平均移動法による階層的クラスタリング」、電子情報通信学会技術研究報告  PRMU98-38、1998
【非特許文献４】ティ・ツァング(T. Zang)他、「バーチ：ア  ニュー  データ  クラスタリング  アルゴリズム  アンド  イッツ  アプリケーションズ(BIRCH:A New Data Clustering Algorithm and its Applications)」、Jounal of DAta Mining and Knowledge Discovery,vol.1,pp.103-114,1996
【非特許文献５】エム・ピー・ワンド(M.P. Wand )他、「カーネル  スムーズシング(Kernel Smoothing)」、Chapman&Hall,1995
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述のように、既存のクラスタリング手法は単独では大規模データへの適用が困難であるという問題があった。前処理（大分類処理）としてデータスカッシングを用いることによって既存のクラスタリング手法を適用することが可能となるが、特許文献１に記載されているような従来の方式では、クラスタの形状なサイズが不均一な場合に、高精度な分類結果を得ることができないという課題があった。
【０００８】
これは大分類処理によって得られた個々の部分クラスタの局所的な密度や分布の形状に関する情報を詳細分類処理で利用していないことに起因する。例えば、ＢＩＲＣＨによって生成される個々の部分クラスタはＣＦベクトル（Cluster Feature ベクトル）と呼ばれ、各部分クラスタに属するデータ数、属するデータの和ベクトルおよび２乗和からなり、各部分クラスタの局所的な分布に関する情報を含んでいる。しかしながら、k−平均法により詳細分類処理を行う場合、k−平均法が対象とする個々のデータはＤ次元空間内の１点として表されるＤ次元ベクトルである必要があるため、各部分クラスタの重心位置（すなわち、ＣＦベクトル中の和ベクトルを当該部分クラスタに属するデータ数で除したベクトル）を対象として詳細分類処理を行っていた。
【０００９】
これは、各部分クラスタの位置のみを用いて詳細分類処理を行っていることに相当し、各部分クラスタの分布形状や属するデータ数に関する情報が全く考慮されていない。
詳細分類処理として他の既存クラスタリング手法を用いる場合においても、基本的に各クラスタリング手法はＤ次元ベクトル（すなわち、Ｄ次元空間内の点）を処理対象とするため、単純に既存手法をそのまま詳細分類処理に用いた場合、同様に部分クラスタの局所的な密度や分布の形状は考慮されない。
【００１０】
本発明の目的は、上述の課題を解消するために、大分類処理と詳細分類処理の２段階処理により大規模データ集合をクラスタリングする場合、大分類処理の結果得られる各部分クラスタの局所的な密度に関する属性を詳細分類処理において適切に扱い、これによって高精度なクラスタリング結果を得ることができるデータ処理システム及びデータ処理プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記問題点を解決するために、本発明は、所定次元数のベクトルデータの集合として与えられる入力データ集合をクラスタリングするデータ処理システムであって、入力データ集合を部分クラスタの集合に変換する大分類手段と、前記大分類手段が変換した前記部分クラスタの集合をクラスタリングする詳細分類手段とを備え、前記詳細分類手段は前記大分類手段が変換した前記部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行うことを特徴とするデータ処理システムを要旨とするものである。
【００１２】
このようにデータ処理システムが構成されていると、計算時間やメモリ容量などのための制約のため単一の手法では処理不可能な大規模データ集合をクラスタリングする場合において、高精度なクラスタリング結果を得ることが可能なデータ処理システムを提供できる。特に、クラスタの形状やサイズが不均一な大規模データをクラスタリングの対象とする場合、従来よりも分類精度を向上することができる。
【００１３】
ここで、前記大分類手段は、前記入力データ集合を部分クラスタの集合に変換された後の該部分クラスタの集合を記憶する記憶手段を備え、さらに前記大分類手段は、前記記憶手段が記憶している部分クラスタの集合の中から、処理対象のデータに最も近い部分クラスタである最近隣部分クラスタを探索する最近隣部分クラスタ探索手段と、前記処理対象のデータを前記最近隣部分クラスタに追加するべきか否かを判定する追加可否判定手段と、前記追加可否判定手段による判定結果に基づいて前記最近隣部分クラスタへの前記処理対象のデータの追加処理及び前記処理対象のデータについて新規の部分クラスタの生成処理のいずれかの処理を行う部分クラスタ集合更新手段とを備え、前記追加可否判定手段は、前記入力データ集合から前記処理対象のデータを１個読み出すたびに最近隣部分クラスタ探索と追加可否判定を行い、前記部分クラスタ集合更新手段は、前記いずれかの処理を行うようにしてもよい。
【００１４】
このように大分類手段が構成されていると、入力データ集合全体をメモリ上に保持する必要がないため、メモリ上で保持できないような大規模データを扱うことが可能となる。
また、前記詳細分類手段は、各部分クラスタの重心位置座標を該各部分クラスタの代表点とし、この代表点を起点として確率密度関数の極大点を探索する極大点探索手段と、前記極大点探索手段による極大点探索が収束したかどうかを極大点探索を行った前回値と今回値の各部分クラスタに対する局所平均ベクトル間の距離情報に基づいて判定する収束判定手段と、同一または近傍の極大点に収束した部分クラスタ群を同じクラスタに属するものとして分類する部分クラスタ分類手段とを備え、前記極大点探索手段は、前記各部分クラスタに属するサンプル数を当該各部分クラスタの重みとして極大点探索を行うようにしてもよい。
【００１５】
このように詳細分類手段が構成されていると、クラスタの分布形状が不規則な形状をしている場合であっても、対応でき、分類精度を向上させることができる。
また、前記極大点探索手段において、局所近傍範囲を定めるパラメータを前記各部分クラスタごとに可変とし、前記各部分クラスタのうち、局所的な密度が大きい部分クラスタに対しては前記パラメータを小さく、局所的な密度が小さい部分クラスタに対しては前記パラメータを大きくするように制御するようにしてもよい。
【００１６】
また、前記極大点探索手段は、入力データの各次元に対し個別に局所的な密度を算出し、この密度に応じて各次元に対し個別に前記パラメータを制御するようにしてもよい。
また、本発明のデータ処理プログラムは、所定次元数のベクトルデータの集合として与えられる入力データ集合をクラスタリングするデータ処理システムのプログラムであって、コンピュータを、入力データ集合を部分クラスタの集合に変換する大分類手段として機能させ、さらに、前記大分類手段が変換した前記部分クラスタの集合をクラスタリングする詳細分類手段として機能させ、かつ、前記詳細分類手段として機能させる際に、前記大分類手段が変換した前記部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行わせることを要旨とする。本発明のプログラムによれば、計算時間やメモリ容量などのための制約のため単一の手法では処理不可能な大規模データ集合をクラスタリングする場合において、高精度なクラスタリング結果を得ることが可能なデータ処理システムのデータ処理プログラムを提供することができる。特に、クラスタの形状やサイズが不均一な大規模データをクラスタリングの対象とする場合、従来よりも分類精度を向上することができるデータ処理プログラムを提供できる。
【発明の効果】
【００１７】
本発明によれば、計算時間やメモリ容量などのための制約のため単一の手法では処理不可能な大規模データ集合をクラスタリングする場合において、高精度なクラスタリング結果を得ることが可能なデータ処理システムを提供できる。特に、クラスタの形状やサイズが不均一な大規模データをクラスタリングの対象とする場合、従来よりも分類精度を向上することができる。
【発明を実施するための最良の形態】
【００１８】
（第１実施形態）
以下、本発明を具体化した第１実施形態を図１〜７を参照して説明する。図１はデータ処理システム１０を構成するブロック図を示し、データ処理システム１０の内部構成は機能ブロックを示している。
【００１９】
図１に示すように、データ処理システム１０は、キーボード等の入力装置１１と、各種プログラムにより動作するデータ処理装置１２を備えている。データ処理装置１２には、各種データを記憶する記憶手段としての記憶装置１３と、出力装置１４とが接続されている。出力装置１４は、例えばディスプレイやプリンタが含まれている。なお、記憶装置１３は、コンピュータの内部装置としてもよく、或いは外部記憶装置として構成されていてもよい。
【００２０】
データ処理装置１２は、ＲＯＭ１２ａ及びＲＡＭ１２ｂを備えたコンピュータ１６からなり、ＲＯＭ１２ａに格納されたデータ処理プログラムにより後述する各種処理を行う。
データ処理装置１２は、最近隣部分クラスタ探索部２２、追加可否判定部２４、及び部分クラスタ集合更新部２６を機能として備える大分類処理部２０と、極大点探索部３２、収束判定部３４及び部分クラスタ分類部３６を機能として備える詳細分類処理部３０を構成する。又、データ処理装置１２は、大分類手段、詳細分類手段に相当する。
【００２１】
（作用）
さて、上記のように構成されたデータ処理システム１０の作用を説明する。
図２は、データ処理装置１２が行う大分類処理のフローチャートである。
【００２２】
なお、データ処理装置１２には、入力装置１１等の入力手段により、処理対象のデータ集合が入力されていて、予め記憶装置１３に格納されており、前記データ処理プログラムにて後述する処理が行われるものとする。前記データ集合は、所定次元数のベクトルデータの集合として与えられる入力データ集合に相当する。
【００２３】
図２は、データ処理装置１２による処理の概要のフローチャートであり、Ｓ１０では、大分類処理部２０はN個のデータからなる処理対象のデータ集合X={x1, x2, …, xN}を部分クラスタの集合V={v1, v2, …, vM}に変換することにより、M個の部分クラスタに分類する。続いて、Ｓ２０では、詳細分類処理部３０は部分クラスタの集合VをC個のクラスタに分類する。ここで一般にN＞＞Mであり、M＞＞Cである。ただし通常、真のクラスタ数Cは未知である。また部分クラスタ数Mは大分類処理部の動作を制御することにより適切に決める必要があるが、この点については後述する。
【００２４】
図３は、大分類処理部２０の処理の一例のフローチャートである。
大分類処理部２０では、データ集合Xから処理対象のデータxi（1≦i≦N）を１個読み込むたびに図３に示す手順を繰り返すことにより、大分類処理を行う。
【００２５】
同図に示すように、Ｓ１１で、大分類処理部２０は、処理対象のデータxiを読み込むと、Ｓ１２において、記憶装置１３が記憶している現在の部分クラスタ集合Vの中でxiに最も近い部分クラスタvkを探索する。
【００２６】
そして、Ｓ１３において、大分類処理部２０は、vkにxiを追加した場合の直径T(vk∪xi)を計算し、Ｓ１４において、この値をあらかじめ定めたしきい値T0と比較する。大分類処理部２０は、T(vk∪xi)がT0より小さいと判定（「ＹＥＳ」と判定）すると、Ｓ１５において、xiを部分クラスタvkに追加する。大分類処理部２０は、T(vk∪xi)がT0以上であると判定（「ＮＯ」と判定）すると、Ｓ１６において、xiのみからなる新規の部分クラスタを作成する。以上の処理を大分類処理部２０は、X内の全データに対して行うことにより、最終的に得られた部分クラスタ集合が大分類処理結果として得られる。
【００２７】
ここで、Ｓ１２は、最近隣部分クラスタ探索部２２の処理であり、最近隣部分クラスタ探索部２２は最近隣部分クラスタ探索手段に相当する。Ｓ１４は、追加可否判定部２４の処理であり、追加可否判定部２４は追加可否判定手段に相当する。Ｓ１５及びＳ１６は、部分クラスタ集合更新部２６の処理であり、部分クラスタ集合更新部２６は部分クラスタ集合更新手段に相当する。記憶装置１３は、部分クラスタの集合を記憶する記憶手段に相当する。
【００２８】
なお、部分クラスタvは下記のようにn, LS, SSの３要素によって記述される。
v = (n, LS, SS)
n  : vを構成するデータ数
LS : vを構成するn個のデータの和ベクトル(linear sum)
SS : vを構成するn個のデータの２乗和(square sum)
部分クラスタvの直径T(v)はvを構成する全データ間のユークリッド距離の平均値であり、(n, LS, SS)から次式（１）により得られる。
【００２９】
【数１】
2010134632.tif 000003
ここで、式（１）の導出について説明する。
【００３０】
n個の個体{xi} (1≦i≦n)からなる部分クラスタvのCFベクトルの要素LS (linear sum)およびSS (square sum)は以下のように表わされる（d: 次元数）。
【００３１】
【数２】
2010134632.tif 000004
また、部分クラスタvの直径T(v)はvに属するすべての個体間のユークリッド距離の平均値として定義される。
したがって、
【００３２】
【数３】
2010134632.tif 000005
より、T(v)はn, LS, SSのみから計算される。
【００３３】
話を元に戻して、前記部分クラスタvとデータxとの距離d(v, x)はvを構成する全データとxとのユークリッド距離の平均値であり、次式（４）により得られる。読み込んだデータに最も近い部分クラスタはこの距離尺度に基づいて決定する。
【００３４】
【数４】
2010134632.tif 000006
なお、上式（４）は、下記のようにして導出される。すなわち、ＣＦベクトルからの部分クラスタ間距離dの計算方法は、下記の通りである。部分クラスタva, vb間の距離d(va, vb)は次式（５）で定義される。(na, nbはva, vbの個体数)
【００３５】
【数５】
2010134632.tif 000007
T(v)の定義より
【００３６】
【数６】
2010134632.tif 000008
であり、和クラスタ(va∪vb)のCFベクトルはva, vbのCFベクトルから計算できるため、結局d(va, vb)はva, vbのCFベクトルのみから求められる。
【００３７】
ある単一データxと部分クラスタv間の距離d(v, x)は、xを1個のデータのみからなる部分クラスタと見なすことにより上式（６）から導かれる次式（７）から計算できる。
【００３８】
【数７】
2010134632.tif 000009
ここで、大分類処理部２０による処理結果の例を以下に説明する。図４（ａ）〜（ｃ）は処理対象となる３種類のデータ集合をプロットした図である。同図中、（ａ）〜（ｃ）の３種類とも、次元数D=2, データ数N=300000, クラスタ数C=3であり、各データが属するクラスタを色の濃淡で表現している。図中、N1, N2, N3はそれぞれ、各クラスタc1,c2,c3に属するデータ数である。
【００３９】
図５（ａ）〜（ｃ）はそれぞれ、図4（ａ）〜（ｃ）に示したデータ集合に対する大分類処理結果の例である。ひとつひとつの円が部分クラスタを表し、円の大きさと色の濃さがそれぞれ、部分クラスタの直径T(v)と部分クラスタに属するデータ数を示している。部分クラスタの数Mはしきい値T0によって変化するが、ここでは（ａ）〜（ｃ）においてMがほぼ300となるようT0の値を制御した。
【００４０】
次に、図１に示す詳細分類処理部３０について以下に説明する。
本実施形態における詳細分類処理部３０は、非特許文献２，３に示されている平均移動法（Mean Shift）を基本としている。公知の平均移動法では、各データ点に対して定義される局所平均ベクトルを逐次移動することにより、密度分布の極大点を並列探索し、同じ極大点に収束したデータが同じクラスタに属すると判定する。平均移動法における極大点探索の概念図を、図１０に示す。同図に示すように、同じ極大点に収束した個体群がクラスタを形成する。
【００４１】
図１０の場合、各データ点（例えば、ｘｉ，ｘｊ，ｘｋ）を局所平均ベクトルの初期値とし、これを起点として探索している状態が示されている。
前記公知の平均移動法を部分クラスタの集合V={v1, v2, …, vM}に対してそのまま適用する場合、各部分クラスタの重心位置座標g(vk)=LSk／nk（なお、LSk, nkはそれぞれ部分クラスタvkの和ベクトル,データ数）を各部分クラスタの代表点として、これを処理対象データと見なし、次式（８）の手順により各部分クラスタに対する局所平均ベクトルmk(l)を逐次移動する。
【００４２】
【数８】
2010134632.tif 000010
ここで、ｌ（=1,2,….）は移動操作の反復回数、ω(x, x’; h) = exp(−|| x−x’||2／h2)は局所近傍を定義するカーネル関数であり、hは別途定めるバンド幅パラメータである。非特許文献３に示されているように、式（８）の操作による移動方向は確率密度関数p(x)の最急勾配方向∇p(x)に等しく、その大きさは極大点から遠い（（=p(x)）が小さい）ほど大きい。ここでの確率密度関数p(x)は、ω(x, x’; h)をカーネル関数とするカーネル密度推定法による確率密度関数であり、次式（９）で表わされる。上記の詳細分類処理部３０の処理は、極大点探索部３２で行う。
【００４３】
【数９】
2010134632.tif 000011
次に、詳細分類処理部３０の収束判定部３４では、全部分クラスタに対する移動操作が完了するたび次式（１０）により収束判定を行う。式（１０）は、全部分クラスタにおいて、局所平均ベクトルmk(l)、mk(l−１)間のユークリッド２乗距離の総和が求められて、該総和がしきい値Ｔｈ未満の場合に収束したと判定することを意味する。本実施形態では、前記局所平均ベクトルmk(l)、mk(l-1)間のユークリッド２乗距離が、局所平均ベクトルの移動操作の反復における前回値と今回値の各部分クラスタに対する局所平均ベクトル間の距離情報に相当する。なお、前記距離情報としてユークリッド２乗距離の代わりに他の距離尺度、例えばユークリッド距離や市街区距離を用いてもよい。
【００４４】
【数１０】
2010134632.tif 000012
詳細分類処理部３０の収束判定部３４は、式（１０）により収束と判定した場合（すなわち、上記式（１０）が成立する場合）、この処理を終了する。そして、部分クラスタ分類部３６は、同一の極大点（又は、極めて近い座標点、すなわち、近傍の極大点）に収束したデータ群を同じクラスタに属するもの、すなわち、１つのクラスタとする。
【００４５】
なお、後で示すように公知の平均移動法をそのまま適用した場合、望ましい分類結果が得られない場合がある。
そこで本実施形態では、大分類処理によって得られる各部分クラスタの局所的な分布に関する情報を適切に扱うことにより高精度な詳細分類結果を得る。具体的には、各部分クラスタに対する局所平均ベクトルmk(l)を次式（１１）の手順により逐次移動する。
【００４６】
【数１１】
2010134632.tif 000013
上記式（１１）の第１式は、各部分クラスタの重心位置座標ｇ（ｖｋ）を各部分クラスタの代表点として、これを局所平均ベクトルの初期値、すなわち、起点とすることを表わしている。
【００４７】
なお、njは部分クラスタvjに属するサンプル数、hjは局所密度に応じて部分クラスタごとに定めるバンド幅パラメータであり、部分クラスタvjに対応するhj2がT(vｊ)2に比例し、かつサンプル数njで重み付けしたhj2の平均がh2に一致するように次式（１２）で定義する。
【００４８】
【数１２】
2010134632.tif 000014
なお、式（１２）の導出は下記の通りである。
【００４９】
部分クラスタvjの半径をT(vｊ)2, バンド幅パラメータをhjと表す。
hj2がT(vｊ)2に比例し、かつnjで重み付けしたhj2の平均がh2に一致するよう以下のようにhjを定める。すなわち、
【００５０】
【数１３】
2010134632.tif 000015
を満たすような定数αを求める。ここでnjはvjに属するサンプル数、Nは全サンプル数であり、
【００５１】
【数１４】
2010134632.tif 000016
である。上記式（１３）、式（１４）から
【００５２】
【数１５】
2010134632.tif 000017
となり、
【００５３】
【数１６】
2010134632.tif 000018
が得られる。従って、式（１７）（＝式（１２））
【００５４】
【数１７】
2010134632.tif 000019
となる。
【００５５】
話を元に戻して、式(１２)のようにバンド幅パラメータを可変とすることは、ある局所平均ベクトルに着目した場合、式（１１）において半径が大きい（すなわち、局所的な密度が小さい）部分クラスタとのカーネル関数の前記パラメータの値をより小さく、また半径が小さい（すなわち、局所的な密度が大きい）部分クラスタとのカーネル関数の前記パラメータの値をより大きくする作用をもたらす。この結果、極大点探索において局所平均ベクトルは密度がより大きい部分クラスタに向かって移動していく。なお、上記のように部分クラスタ毎にバンド幅パラメータの可変する処理は、極大点探索部３２が行う。
【００５６】
又、式（１１）では、カーネル関数の値に各部分クラスタに属するサンプル数njを乗じて加算している。これはサンプル数njを各部分クラスタの重みとして極大点探索を行っていることに相当する。
【００５７】
バンド幅パラメータhの基準値はデータ全体の分布を考慮して適切に決める必要があり、基準値の値によって詳細分類の結果得られるクラスタ数が変化する。非特許文献３では全サンプルの最近隣接点間距離の平均値を基準値の初期値として漸増する方法が示されている。また、平均移動法におけるバンド幅選択はカーネル密度推定法と本質的に同じ問題であり、非特許文献５の p.71〜72に示されているプラグイン・ルールによりhを定めてもよい。
【００５８】
上記のようにして、大分類処理によって得られた図５（ａ）〜（ｃ）の部分クラスタ集合に対して、本実施形態の詳細分類処理部により詳細分類を行った結果を図６（ａ）〜（ｃ）に示す。ここでは、hの値を変化させてクラスタ数が真のクラスタ数３に一致したときの結果を示しており、同じクラスタに分類された部分クラスタを同じ明度で図示している。
【００５９】
又、図７（ａ）〜（ｃ）は、図５（ａ）〜（ｃ）の大分類処理結果に対して公知の平均移動法により詳細分類を行った結果を示している。図６では（ａ）〜（ｃ）すべてで望ましい分類結果が得られているのに対して、図７では（ｂ），（ｃ）のように各クラスタの形状・サンプル数が不均一な場合に正しい分類結果が得られていない。これは、本実施形態では各部分クラスタの局所的な密度を考慮して詳細分類を行うことにより、従来技術よりも高精度な分類結果が得られることを示している。
【００６０】
以上のように構成されたデータ処理システム１０は、下記の特徴がある。
（１）本実施形態のデータ処理システムのデータ処理装置１２は、大分類手段としてデータ集合（入力データ集合）を部分クラスタの集合に変換し、詳細分類手段として、前記大分類手段が変換した前記部分クラスタの集合をクラスタリングするにあたり、部分クラスタの局所的な密度に関する属性を考慮して詳細分類を行うようにした。
【００６１】
この結果、計算時間やメモリ容量などのための制約のため単一の手法では処理不可能な大規模データ集合をクラスタリングする場合において、高精度なクラスタリング結果を得ることが可能なデータ処理システムを提供できる。特に、クラスタの形状やサイズが不均一な大規模データをクラスタリングの対象とする場合、従来よりも分類精度を向上することができる。
【００６２】
（２）本実施形態のデータ処理装置１２は、大分類手段として、入力データ集合を部分クラスタの集合に変換された後の該部分クラスタ集合を記憶する記憶装置１３（記憶手段）と、前記記憶装置１３が記憶している部分クラスタの集合の中から、処理対象のデータに対し最も近い部分クラスタである最近隣部分クラスタを探索する最近隣部分クラスタ探索部２２（最近隣部分クラスタ探索手段）と、前記処理対象のデータを該最近隣部分クラスタに追加するべきか否かを判定する追加可否判定部２４（追加可否判定手段）を備える。又、データ処理装置１２は、判定結果に基づいて前記最近隣部分クラスタへの前記処理対象のデータの追加処理及び前記処理対象のデータについて新規の部分クラスタの生成処理のいずれかの処理を行う部分クラスタ集合更新部２６（部分クラスタ集合更新手段）を備える。そして、追加可否判定部２４は、データ集合（入力データ集合）からデータを１個読み出すたびに最近隣部分クラスタ探索と追加可否判定を行い、部分クラスタ集合更新部２６は、前記最近隣部分クラスタへの前記処理対象のデータの追加処理及び前記処理対象のデータについて新規の部分クラスタの生成処理のいずれかの処理を行うようにした。この結果、このように大分類手段が構成されていると、入力データ集合全体をメモリ上に保持する必要がないため、メモリ上で保持できないような大規模データを扱うことが可能となる。
【００６３】
（３）  又、本実施形態のデータ処理装置１２は、詳細分類手段として、各部分クラスタの重心位置座標を該各部分クラスタの代表点とし、この代表点を起点として確率密度関数の極大点を探索する極大点探索部３２（極大点探索手段）と、極大点探索部３２による極大点探索が収束したかどうかを極大点探索を行った前回値と今回値の各部分クラスタに対する局所平均ベクトル間の距離情報に基づいて判定する収束判定部３４（収束判定手段）と、同一または近傍の極大点に収束した部分クラスタ群を同じクラスタに属するものとして分類する部分クラスタ分類部３６（部分クラスタ分類手段）とを備える。又、極大点探索部３２は、各部分クラスタに属するサンプル数を当該各部分クラスタの重みとして極大点探索を行う。この結果、クラスタの分布形状が不規則な形状をしている場合であっても対応でき、分類精度を向上させることができる。
【００６４】
（４）  又、本実施形態のデータ処理装置１２は、極大点探索部３２（極大点探索手段）において、局所近傍範囲を定めるパラメータ（バンド幅パラメータ）を各部分クラスタごとに可変とし、前記各部分クラスタのうち、局所的な密度が大きい部分クラスタに対しては前記パラメータを小さく、局所的な密度が小さい部分クラスタに対しては前記パラメータを大きくするように制御するようにしている。この結果、上記（１）、（２）、（３）の効果を容易に実現できる。
【００６５】
（第２実施形態）
次に、第２実施形態を図８を参照して説明する。なお、第１実施形態と同一構成については、同一符号を付して、異なる構成について説明する。
【００６６】
第２実施形態では、第１実施形態における大分類処理部２０の処理を別の方式に置き替えたものである。
具体的には、第２実施形態の方式では各部分クラスタを(n, LS, SS)の３要素で記述するかわりに、各部分クラスタの重心位置座標とサンプル数の２要素で記述する。この方式は、データxと部分クラスタとの距離を求める際に部分クラスタの直径Tに相当する量を用いず重心位置座標のみを用いる簡略版である。直径Tは大分類終了時に一括して算出する。
【００６７】
図８は大分類処理部２０が処理するフローチャートである。同図に示すようにこの大分類処理部２０では、データ集合Xからデータxi（1≦i≦N）を１個読み込むたびに図８に示す手順を繰り返す。Ｓ１１でデータxiが読み込まれると、と１２において、まず現在の部分クラスタ集合Vの中でxiに最も近い部分クラスタvkを探索する。そして、Ｓ１３Ａにおいて、vkとxiとの距離d(vk, xi)を計算する。続くＳ１４Ａにおいて、vkとxiとの距離d(vk, xi)をあらかじめ定めたしきい値ｄ0と比較する。
【００６８】
Ｓ１４Ａにおいて、d(vk, xi)がd0より小さい場合には、Ｓ１５Ａに移行して、xiを部分クラスタvkに追加し、vkの重心g(vk)を更新する。又、Ｓ１４Ａにおいて、d(vk, xi)がd0以上の場合には、Ｓ１６において、xiのみからなる新しい部分クラスタを作成する。以上の処理をX内の全データに対して行うことにより、最終的に得られた部分クラスタ集合が大分類処理結果として得られる。
【００６９】
この方式では部分クラスタvは下記のようにn, g(v)の２要素によって記述される。
v = (n, g(v))
n    : vを構成するデータ数
g(v)  : vを構成するn個のデータの重心位置座標
部分クラスタv重心g(v)はvを構成する全データの平均ベクトルであり、次式（１８）により得られる。
【００７０】
【数１８】
2010134632.tif 000020
又、部分クラスタvとデータxとの距離d(v, x)はg(v)とxとのユークリッド距離であり、次式（１９）により得られる。読み込んだデータに最も近い部分クラスタはこの距離尺度に基づいて決定する。
【００７１】
【数１９】
2010134632.tif 000021
全データに対して部分クラスタへの割り当てが終了したら、各部分クラスタに対して直径Tを算出する。部分クラスタvの直径T(v)はvに属する全データ間のユークリッド距離の平均値であり、各データの座標値から直接、次式（２０）により算出する。
【００７２】
【数２０】
2010134632.tif 000022
この第２実施形態において、Ｓ１２は、最近隣部分クラスタ探索部２２の処理であり、最近隣部分クラスタ探索部２２は最近隣部分クラスタ探索手段に相当する。Ｓ１４Ａは、追加可否判定部２４の処理であり、追加可否判定部２４は追加可否判定手段に相当する。Ｓ１５Ａ及びＳ１６は、部分クラスタ集合更新部２６の処理であり、部分クラスタ集合更新部２６は部分クラスタ集合更新手段に相当する。記憶装置１３は、部分クラスタ集合を記憶する記憶手段に相当する。
（第３実施形態）
次に、第３実施形態を図９を参照して説明する。本実施形態では、各部分クラスタのサンプル数のみを考慮する。すなわち、第１実施形態では式（１１）の更新式により各部分クラスタのサンプル数と半径の両方を考慮して極大点探索を行っているが、サンプル数のみを考慮するよう簡略化することも可能である。この場合、局所平均ベクトルの移動操作における更新式は次式（２１）で表わされる。
【００７３】
【数２１】
2010134632.tif 000023
この方式を用いて詳細分類処理を行った結果を図９に示す。図６の結果にはやや劣るものの、従来方式に比べ大幅に改善している。
（第４実施形態）
次に、請求項５に対応する第４実施形態を説明する。本実施形態は、詳細分類処理部３０の極大点探索部３２がバンド幅パラメータhを入力データの各次元ごとに独立に制御することが特徴である。
【００７４】
以下詳説すると、本実施形態では、CFベクトルのSS(Square Sum)を、各次元ごとの2乗和を要素とするベクトルとすることにより、バンド幅パラメータhを非等方性に拡張している（非対角要素がゼロのbandwidth matrix H）。
【００７５】
ここで、ｎ個の個体{xi} (1≦i≦n)からなる部分クラスタvのCFベクトルの要素LS (linear sum)およびSS (square sum)は以下のように表わされる（d: 次元数）。
【００７６】
【数２２】
2010134632.tif 000024
上記のうちSS を以下のようにd次元のベクトルSSに変更する。
【００７７】
【数２３】
2010134632.tif 000025
SS（スカラー量）はベクトルSSの各要素の和として求められるので、従来のCFベクトルの拡張となっている。すなわち、部分クラスタが超球状と仮定した場合の直径T, ２つの部分クラスタ間の距離、２つの部分クラスタの和は従来同様に計算できる。
【００７８】
ここでSSをベクトルに拡張したCFベクトルvで表わされる部分クラスタが超楕円体であると考え、各次元k(1≦k≦d)ごとに部分クラスタvの直径Tk( v)を考える。
直径Tk( v)はSSがスカラーの場合と同様に以下のように算出できる。
【００７９】
【数２４】
2010134632.tif 000026
（バンド幅マトリックスＨ（bandwidth matrix H）の算出）
ここで、CFベクトルvjに対応するバンド幅パラメータを非対角要素がゼロのbandwidth matrix Hjとし、Hjの(k,k)要素をhjk2と書く。
【００８０】
【数２５】
2010134632.tif 000027
そして、hjkを第k次元方向の局所的な密度に応じて以下のように定める（1≦k≦d）。すなわち、hjk2がTk(vj)2に比例し、かつvjに属するサンプル数を考慮したhjk2の平均が第k次元方向の固定バンド幅の2乗hk2に一致するよう次式（２６）で定義する。
【００８１】
【数２６】
2010134632.tif 000028
（バンド幅マトリックスＨを用いた平均移動法（mean shift）クラスタリング）
そして、CFベクトルの重心g(vi)に対する局所平均ベクトルmiを以下の次式（２７）の手順により逐次移動し、極大点を探索する。
【００８２】
【数２７】
2010134632.tif 000029
ここでωH(x, x’; H)は局所近傍を定義する非等方性のカーネル関数であり、
【００８３】
【数２８】
2010134632.tif 000030
と表される。
【００８４】
なお、本発明の実施形態は以下のように変更してもよい。
○  第１実施形態では、大分類処理部２０の処理によって得られる部分クラスタは(n, LS, SS)の３要素で記述されているが、必ずしもこの構成である必要はなく、部分クラスタの重心位置座標と分散に相当する量が得られるよう構成されていればよい。極論すれば全データの座標点と部分クラスタとの対応さえ与えられていれば重心と分散を計算できる。ただし、大規模データ集合に対して効率良く大分類を行うためには上述のような構成であることが望ましい。これは、部分クラスタvとデータxとの距離d(v, x)の算出、部分クラスタの直径T(v)の算出、部分クラスタvにデータxを追加した場合のパラメータ更新が効率良く行えるためである。
【００８５】
○  第１実施形態の構成中、詳細分類処理部３０において部分クラスタごとにバンド幅パラメータhjを定める方法は上記実施例の方法（=式（１２）式）に限定されるものではない。例えば、部分クラスタの半径が大きい（すなわち局所密度が小さい）ときにはhjが大きく、半径が小さい（すなわち局所密度が大きい）ときにはhjが小さくなるような任意の方式を用いることもできる。さらに、詳細分類処理において、局所近傍を定義するカーネル関数はガウシアン関数に限らず任意のカーネル関数を用いてもよい。
【００８６】
○  第１実施形態では、１つのコンピュータからなるデータ処理装置１２により、大分類手段、詳細分類手段を構成したが、２台のコンピュータでそれぞれ大分類手段、詳細分類手段を構成してもよい。又、最近隣部分クラスタ探索部２２、追加可否判定部２４、部分クラスタ集合更新部２６、詳細分類処理部３０の極大点探索部３２、収束判定部３４、部分クラスタ分類部３６をそれぞれコンピュータで構成してもよい。
【００８７】
本明細書において、請求項以外に把握できる技術的思想を以下に列挙する。
（１）  請求項６において、コンピュータを、前記大分類手段として機能させる際に、
さらに、該コンピュータを、
前記入力データ集合が部分クラスタの集合に変換された後の該部分クラスタの集合を記憶する記憶手段と、
前記記憶手段が記憶している部分クラスタの集合の中から、処理対象のデータに最も近い部分クラスタである最近隣部分クラスタを探索する最近隣部分クラスタ探索手段と、
前記処理対象のデータを該最近隣部分クラスタに追加するべきか否かを判定する追加可否判定手段と、
前記追加可否判定手段による判定結果に基づいて前記最近隣部分クラスタへの前記処理対象のデータ追加処理及び前記処理対象のデータについて新規の部分クラスタの生成処理のいずれかの処理を行う部分クラスタ集合更新手段として機能させ、
前記コンピュータが、前記追加可否判定手段として、前記処理対象のデータを１個読み出すたびに最近隣部分クラスタ探索と追加可否判定を行うとともに、前記部分クラスタ集合更新手段として、前記何れかの処理行うことを特徴とするデータ処理システムのプログラム。
【００８８】
（２）  請求項６又は前記（１）において、
コンピュータを、前記詳細分類手段として機能させる際に、
さらに、該コンピュータを、
各部分クラスタの重心位置座標を該各部分クラスタの代表点とし、この代表点を起点として確率密度関数の極大点を探索する極大点探索手段と、
極大点探索が収束したかどうかを極大点探索を行った前回値と今回値の各部分クラスタに対する局所平均ベクトル間の距離情報に基づいて判定する収束判定手段と、
同一または近傍の極大点に収束した部分クラスタ群を同じクラスタに属するものとして分類する部分クラスタ分類手段として機能させ、
前記極大点探索手段として機能させる際に、前記各部分クラスタに属するサンプル数を当該各部分クラスタの重みとして極大点探索を行わせることを特徴とするデータ処理システムのプログラム。
【００８９】
（３）  前記（２）において、
コンピュータを、前記極大点探索手段として機能させる際に、
局所近傍範囲を定めるパラメータを前記各部分クラスタごとに可変とし、前記各部分クラスタのうち、局所的な密度が大きい部分クラスタに対しては前記パラメータを小さく、局所的な密度が小さい部分クラスタに対しては前記パラメータを大きくするように制御させることを特徴とするデータ処理システムのプログラム。
【００９０】
（４）  前記（３）において、
コンピュータを、前記極大点探索手段として機能させる際に、
入力データの各次元に対し個別に局所的な密度を算出し、この密度に応じて各次元に対し個別に前記パラメータを制御させることを特徴とするデータ処理システムのプログラム。
【図面の簡単な説明】
【００９１】
【図１】データ処理システム１０を構成するブロック図。
【図２】データ処理装置１２による処理の概要のフローチャート。
【図３】大分類処理部２０の処理の一例のフローチャート。
【図４】（ａ）〜（ｃ）は処理対象となる３種類のデータ集合をプロットした図。
【図５】（ａ）〜（ｃ）は、図4（ａ）〜（ｃ）に示したデータ集合に対する大分類処理結果の例の説明図。
【図６】（ａ）〜（ｃ）は、大分類処理によって得られた図５（ａ）〜（ｃ）の部分クラスタ集合に対して、第１実施形態の詳細分類処理部により詳細分類を行った結果の説明図。
【図７】（ａ）〜（ｃ）は、図５（ａ）〜（ｃ）の大分類処理結果に対して公知の平均移動法により詳細分類を行った結果の説明図。
【図８】第２実施形態の分類処理部２０が処理するフローチャート
【図９】（ａ）〜（ｃ）は第３実施形態において、詳細分類処理を行った結果の説明図。
【図１０】平均移動法における極大点探索の概念図。
【符号の説明】
【００９２】
１０…データ処理システム、
１１…入力装置、
１２…データ処理装置（大分類手段、詳細分類手段）、
１２ａ…ＲＯＭ、
１２ｂ…ＲＡＭ、
１３…記憶装置（記憶手段）、
１４…出力装置、
２０…大分類処理部、
２２…探索部最近隣部分クラスタ探索部、
２４…追加可否判定部、
２６…部分クラスタ集合更新部、
３０…詳細分類処理部、
３２…極大点探索部、
３４…収束判定部、
３６…部分クラスタ分類部。
【図１】
2010134632.tif 000031
【図２】
2010134632.tif 000032
【図３】
2010134632.tif 000033
【図８】
2010134632.tif 000034
【図４】
2010134632.tif 000035
【図５】
2010134632.tif 000036
【図６】
2010134632.tif 000037
【図７】
2010134632.tif 000038
【図９】
2010134632.tif 000039
【図１０】
2010134632.tif 000040