(57)【要約】【課題】半教師ありクラスタリングに用いるマハラノビス距離のパラメータを、学習データから反復演算を行わずに推定することが可能なクラスタリング装置を提供する。【解決手段】クラスタリング装置１は、クラスタごとに、データの特徴量空間におけるクラスタ中心の値を記憶する記憶手段２１と、どのクラスタに属するかが既知のデータである学習データを入力する学習データ入力手段２２と、マハラノビス距離を計算するための行列と当該行列の転置行列との積の対角成分の和に予め定めた拘束条件を設け、学習データ入力手段２２で入力された学習データと、当該学習データのクラスタに対応するクラスタ中心記憶手段に記憶されているクラスタ中心とに基づいて、行列をパラメータとして演算するパラメータ演算手段２４と、を備える。【選択図】図２
2010198518.tif 000002
【特許請求の範囲】
【請求項１】
データの特徴量の類似度である距離により複数のデータをクラスタリングする際に用いるマハラノビス距離のパラメータを学習するクラスタリング距離学習装置であって、
クラスタごとに、前記データの特徴量空間におけるクラスタ中心の値を記憶するクラスタ中心記憶手段と、
どのクラスタに属するかが既知のデータである学習データを入力する学習データ入力手段と、
前記マハラノビス距離を計算するための行列と当該行列の転置行列との積の対角成分の和に予め定めた拘束条件を設け、前記学習データ入力手段で入力された学習データと、当該学習データのクラスタに対応する前記クラスタ中心記憶手段に記憶されているクラスタ中心とに基づいて、前記行列を前記パラメータとして演算するパラメータ演算手段と、
を備えることを特徴とするクラスタリング距離学習装置。
【請求項２】
前記行列をＡとしたとき、当該行列Ａに対する前記拘束条件をｔｒ（ＡＴＡ）＝１とし、
前記パラメータ演算手段が、
前記学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、前記クラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、前記行列Ａを、
【数１９】
2010198518.tif 000021
により演算することを特徴とする請求項１に記載のクラスタリング距離学習装置。
【請求項３】
データの特徴量の類似度である距離により複数のデータをクラスタリングする際に用いるマハラノビス距離のパラメータを学習するために、コンピュータを、
どのクラスタに属するかが既知のデータである学習データを入力する学習データ入力手段、
前記マハラノビス距離を計算するための行列をＡとしたとき、当該行列Ａに対する拘束条件をｔｒ（ＡＴＡ）＝１とし、
前記学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、クラスタ中心記憶手段に記憶されている前記データの特徴量空間におけるクラスタごとのクラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、前記行例Ａを、
【数２０】
2010198518.tif 000022
により演算するパラメータ演算手段、
として機能させることを特徴とするクラスタリング距離学習プログラム。
【請求項４】
データの特徴量の類似度にマハラノビス距離を用いて、複数のデータをクラスタリングするクラスタリング装置において、
前記マハラノビス距離のパラメータを学習する距離学習手段を備え、
前記距離学習手段は、
クラスタごとに、前記データの特徴量空間におけるクラスタ中心の値を記憶するクラスタ中心記憶手段と、
どのクラスタに属するかが既知のデータである学習データを入力する学習データ入力手段と、
前記マハラノビス距離を計算するための行列と当該行列の転置行列との積の対角成分の和に予め定めた拘束条件を設け、前記学習データ入力手段で入力された学習データと、当該学習データのクラスタに対応する前記クラスタ中心記憶手段に記憶されているクラスタ中心とに基づいて、前記行列を前記パラメータとして演算するパラメータ演算手段と、
を備えることを特徴とするクラスタリング装置。
【請求項５】
前記行列をＡとしたとき、当該行列Ａに対する前記拘束条件をｔｒ（ＡＴＡ）＝１とし、
前記パラメータ演算手段が、
前記学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、前記クラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、前記行列Ａを、
【数２１】
2010198518.tif 000023
により演算することを特徴とする請求項４に記載のクラスタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリングを行う際に類似度として用いるデータ間の距離のパラメータを学習するクラスタリング距離学習装置およびそのプログラム、ならびに、それを用いたクラスタリング装置に関する。
【背景技術】
【０００２】
従来、画像処理、言語処理等において、分類範疇が未知の複数のデータを、類似した同一のクラスタに分類するクラスタリングの手法が知られている（例えば、特許文献１参照）。このようなクラスタリングの手法においては、データが類似しているか否かの判定に、類似度としてデータ間の距離を用いている。この距離としては、ユークリッド距離やコサイン距離を用い、距離尺度を固定にするのが一般的である。
【０００３】
また、従来のクラスタリングは、教師データを用いずに分類を行う教師なし手法が確立されていたが、近年、教師あり手法が用いられ、半教師ありクラスタリングとして研究がなされている（非特許文献１参照）。この半教師ありクラスタリングとは、クラスタリング対象のデータのいくつかに、予めクラスタに関する情報を与えることで、事前にクラスタリングに関する学習を行い、その学習結果に応じて他のクラスタリング対象のデータをクラスタリングするものである。この学習においては、よりよいクラスタリング性能を得るために、距離尺度を学習データに応じて設定することが望ましい。
そのため、従来、この学習において、距離としてマハラノビス距離を用い、距離尺度、すなわち、マハラノビス距離のパラメータを反復解法により推定する手法が提案されている（非特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第２９６７３１２号公報
【非特許文献】
【０００５】
【非特許文献１】S. Basu, M.Bilenko and R. J.Mooney:“A probabilistic framework for semi-supervised clustering”, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 59-68(2004).
【非特許文献２】E. P.Xing, A. Y.Ng, M. I.Jordan and S. Russell:“Distance metric learning, with application to clustering with side-information”, Neural Information Processing Systems(NIPS)(2003).
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来のユークリッド距離やコサイン距離を用い、距離尺度を固定にしてクラスタリングを行う手法では、学習データに応じて調整するパラメータが存在しない。そのため、従来の手法では、クラスタリング対象のデータに応じた（例えば、データ分散の特性等に応じた）最適なクラスタリングを行うことができないという問題がある。
また、従来のマハラノビス距離を用い、学習データにより、予めマハラノビス距離のパラメータを推定する手法では、その推定を行う際に反復演算を行っている。そのため、従来の手法では、マハラノビス距離のパラメータ推定に時間がかかってしまうという問題がある。
【０００７】
本発明は、以上のような問題点に鑑みてなされたものであり、半教師ありクラスタリングに用いるマハラノビス距離のパラメータを、学習データから反復演算を行わずに推定することが可能なクラスタリング距離学習装置およびそのプログラム、ならびに、クラスタリング装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のクラスタリング距離学習装置は、データの特徴量の類似度である距離により複数のデータをクラスタリングする際に用いるマハラノビス距離のパラメータを学習するクラスタリング距離学習装置であって、クラスタ中心記憶手段と、学習データ入力手段と、パラメータ演算手段と、を備える構成とした。
【０００９】
かかる構成において、クラスタリング距離学習装置は、クラスタ中心記憶手段に、クラスタごとに、データの特徴量空間におけるクラスタ中心の値を記憶する。このクラスタ中心は、データをクラスタリングする際のクラスタごとの特徴量空間における座標値である。また、特徴量空間とは、データの１つ以上の特徴量をベクトルとした座標空間である。ここで、データの特徴量とは、各データを分類するための指標となるものであって、例えば、言語処理の場合、音声データを分析することで抽出したケプストラム係数、文書データを形態素解析することで抽出した形態素の出現頻度等である。
【００１０】
そして、クラスタリング距離学習装置は、学習データ入力手段によって、どのクラスタに属するかが既知のデータである学習データを入力する。ここで学習データは、クラスタリング対象のデータと同種のデータであって、マハラノビス距離のパラメータを推定するために使用される。なお、学習データのクラスタを既知とするためには、学習データ入力手段が、クラスタを指定された後に、学習データをクラスタごとにまとめて入力することとしてもよいし、学習データそのものにクラスタの情報を付加して入力することとしてもよい。
【００１１】
そして、クラスタリング距離学習装置は、パラメータ演算手段によって、マハラノビス距離を計算するための行列と当該行列の転置行列との積の対角成分の和に予め定めた拘束条件を設け、学習データ入力手段で入力された学習データと、当該学習データのクラスタに対応するクラスタ中心記憶手段に記憶されているクラスタ中心とに基づいて、行列をマハラノビス距離のパラメータとして演算する。すなわち、クラスタリング距離学習装置は、パラメータ演算手段において、予め定めた拘束条件を設けることで、マハラノビス距離を計算するためのパラメータである行列を、反復演算することなく特定する。
【００１２】
また、請求項２に記載のクラスタリング距離学習装置は、請求項１に記載のクラスタリング距離学習装置において、前記行列をＡとしたとき、当該行列Ａに対する前記拘束条件をｔｒ（ＡＴＡ）＝１とし、パラメータ演算手段が、前記学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、前記クラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、前記行例Ａを、
【００１３】
【数１】
2010198518.tif 000003
【００１４】
により演算する構成とした。
【００１５】
かかる構成において、拘束条件を設けることで、マハラノビス距離のパラメータの推定を、学習データにおけるマハラノビス距離が最小となる拘束条件付最小化問題として解くことができる。そこで、クラスタリング距離学習装置は、パラメータ演算手段によって、この拘束条件付最小化問題の解である行例Ａを演算することで、マハラノビス距離のパラメータ（行列）を推定する。
このように、クラスタリング距離学習装置は、固有の式によりマハラノビス距離のパラメータ（行列）を推定するため、反復演算を行う必要がない。
【００１６】
さらに、請求項３に記載のクラスタリング距離学習プログラムは、データの特徴量の類似度である距離により複数のデータをクラスタリングする際に用いるマハラノビス距離のパラメータを学習するために、コンピュータを、学習データ入力手段、パラメータ演算手段、として機能させる構成とした。
【００１７】
かかる構成において、クラスタリング距離学習プログラムは、学習データ入力手段によって、どのクラスタに属するかが既知のデータである学習データを入力する。そして、クラスタリング距離学習プログラムは、パラメータ演算手段によって、マハラノビス距離を計算するための行列をＡとしたとき、当該行列Ａに対する拘束条件をｔｒ（ＡＴＡ）＝１とし、学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、クラスタ中心記憶手段に記憶されているデータの特徴量空間におけるクラスタごとのクラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、行例Ａを、
【００１８】
【数２】
2010198518.tif 000004
【００１９】
により演算する。
【００２０】
また、請求項４に記載のクラスタリング装置は、データの特徴量の類似度にマハラノビス距離を用いて、複数のデータをクラスタリングするクラスタリング装置において、前記マハラノビス距離のパラメータを学習する距離学習手段を備え、前記距離学習手段が、クラスタ中心記憶手段と、学習データ入力手段と、パラメータ演算手段と、を備える構成とした。
【００２１】
かかる構成において、クラスタリング装置は、クラスタ中心記憶手段に、クラスタごとに、データの特徴量空間におけるクラスタ中心の値を記憶する。また、クラスタリング装置は、学習データ入力手段によって、どのクラスタに属するかが既知のデータである学習データを入力する。そして、クラスタリング装置は、パラメータ演算手段によって、マハラノビス距離を計算するための行列と当該行列の転置行列との積の対角成分の和に予め定めた拘束条件を設け、学習データ入力手段で入力された学習データと、当該学習データのクラスタに対応するクラスタ中心記憶手段に記憶されているクラスタ中心とに基づいて、行列をマハラノビス距離のパラメータとして演算する。
【００２２】
さらに、請求項５に記載のクラスタリング装置は、請求項４に記載のクラスタリング装置において、前記行列をＡとしたとき、当該行列Ａに対する前記拘束条件をｔｒ（ＡＴＡ）＝１とし、パラメータ演算手段が、前記学習データをｘ、当該学習データを識別するｘの添字をｎ，ｎ′、前記クラスタ中心をμ、当該クラスタ中心のクラスタを識別するμの添字をｋ，ｋ′、添字ｎ，ｎ′の学習データｘが添字ｋ，ｋ′のクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる属性値をｒｎｋ，ｒｎ′ｋ′で表したとき、前記行例Ａを、
【００２３】
【数３】
2010198518.tif 000005
【００２４】
により演算する構成とした。
【００２５】
かかる構成において、拘束条件を設けることで、マハラノビス距離のパラメータの推定を、学習データにおけるマハラノビス距離が最小となる拘束条件付最小化問題として解くことができる。そこで、クラスタリング装置は、パラメータ演算手段によって、この拘束条件付最小化問題の解である行例Ａを演算することで、マハラノビス距離のパラメータ（行列）を推定する。
【発明の効果】
【００２６】
本発明は、以下に示す優れた効果を奏するものである。
請求項１〜３に記載の発明によれば、クラスタリングに用いるマハラノビス距離のパラメータ（行列）を、学習データに応じて調整することができる。これによって、クラスタリング装置において、クラスタリング対象のデータを精度よくクラスタリングすることが可能なパラメータを推定することができる。また、請求項１〜３に記載の発明によれば、マハラノビス距離のパラメータ（行列）の推定を、反復演算することなく求めることができる。これによって、ＣＰＵ負荷を軽減することができるとともに、パラメータの推定時間を短縮することができる。
【００２７】
請求項４，５に記載の発明によれば、クラスタリングに用いるマハラノビス距離のパラメータ（行列）を、学習データに応じて調整することができ、クラスタリング対象のデータを精度よくクラスタリングすることができる。また、請求項４，５に記載の発明によれば、マハラノビス距離のパラメータ（行列）の推定を、反復演算することなく求めることができる。これによって、ＣＰＵ負荷を軽減することができるとともに、パラメータの推定時間を短縮することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態に係るクラスタリング装置の全体構成を示す概略ブロック図である。
【図２】本発明の実施形態に係るクラスタリング装置の全体構成を示す詳細ブロック図である。
【図３】本発明の実施形態に係るクラスタリング装置の距離学習手段における学習動作（パラメータ推定動作）を示すフローチャートである。
【図４】本発明の実施形態に係るクラスタリング装置のクラスタリング実行手段におけるクラスタリング実行動作を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について図面を参照して説明する。
［クラスタリング装置の概要］
最初に、図１を参照して、本発明の実施形態に係る距離学習手段（クラスタリング距離学習装置）を含んだクラスタリング装置の概要について説明する。
図１に示したクラスタリング装置１は、距離学習手段２によって、学習データから、データの特徴量の類似度である距離に用いるマハラノビス距離のパラメータ（対称正定値行列）を推定する。
なお、ベクトルａ，ｂ間のマハラノビス距離Ｍ（ａ，ｂ）は、行列（対称正定値行列）Ａを用いて、以下の（１）式により定義される距離である。また、Ｔは転置行列を示す。
【００３０】
【数４】
2010198518.tif 000006
【００３１】
すなわち、マハラノビス距離は、行列Ａにより特定される距離である。そこで、クラスタリング装置１は、距離学習手段２によって、学習データからマハラノビス距離を算出するために用いる行列Ａをパラメータとして推定する。
このとき、距離学習手段２は、パラメータ（対称正定値行列）に対して予め拘束条件を設けることで、反復演算を行わずにパラメータを推定する。
【００３２】
そして、クラスタリング装置１は、クラスタリング実行手段３によって、特徴量空間におけるクラスタ中心とデータとの距離に、距離学習手段２で推定したパラメータ（行列Ａ）を有するマハラノビス距離を用い、ｋ−平均（ｋ−ｍｅａｎｓ）法により、データをクラスタごとにクラスタリングする。
【００３３】
このように、クラスタリング装置１は、予め与えられた学習データから、マハラノビス距離のパラメータ（対称正定値行列）を推定し、当該マハラノビス距離を用いてクラスタリングを行う半教師ありクラスタリング手法を実現するものである。
以下、本発明の実施形態に係るクラスタリング装置の構成および動作について順次説明する。
【００３４】
［クラスタリング装置の構成］
まず、図２を参照して、本発明の実施形態に係るクラスタリング装置の構成について説明する。このクラスタリング装置１は、データの特徴量の類似度にマハラノビス距離を用いて、複数のデータをクラスタリングするものである。ここでは、クラスタリング装置１は、距離学習手段２と、クラスタリング実行手段３と、を備えている。
【００３５】
距離学習手段（クラスタリング距離学習装置）２は、後記するクラスタリング実行手段３において使用するマハラノビス距離のパラメータを学習（推定）するものである。ここでは、距離学習手段２は、記憶手段２１と、学習データ入力手段２２と、特徴量抽出手段２３と、パラメータ演算手段２４と、を備えている。
【００３６】
記憶手段（クラスタ中心記憶手段）２１は、予め定めたデータの分類数（クラスタ数）ごとに、クラスタ中心の値を記憶するものであって、ハードディスク等の一般的な記憶装置である。
この記憶手段２１に記憶するクラスタ中心の値は、予め定めたクラスタの数（Ｋ個とする）だけ準備すれば、その値は特に限定するものではない。例えば、すべてのクラスタ中心μｋ（ｋ＝１，２,…，Ｋ）を以下の（２）式に示すように、特徴量空間上の原点とする。
【００３７】
【数５】
2010198518.tif 000007
【００３８】
なお、この記憶手段２１には、後記するパラメータ演算手段２４により演算されたマハラノビス距離の行例（パラメータ）Ａも記憶されるものとする。
【００３９】
学習データ入力手段２２は、外部からマハラノビス距離のパラメータを学習するための学習データを入力するものである。この学習データは、どのクラスタに属するデータであるかが既知のデータである。例えば、学習データ入力手段２２は、クラスタを指定された後に、学習データをクラスタごとにまとめて入力することとしてもよいし、学習データそのものにクラスタの情報を付加して入力することとしてもよい。
【００４０】
また、この学習データは、クラスタリング実行手段３においてクラスタリングするデータと同種のデータである。なお、この学習データは、画像データ、音声データ、文書データ等、その特徴量において分類可能なデータであれば、どのようなデータであっても構わない。この学習データ入力手段２２は、入力した学習データを特徴量抽出手段２３に出力する。
【００４１】
特徴量抽出手段２３は、学習データ入力手段２２で入力された学習データの特徴量を抽出するものである。なお、この特徴量抽出手段２３は、学習データから抽出する特徴量の種類を、予め学習データの種類に応じて定めておく。あるいは、学習データの種類が固定の場合は、予め定めた固有の特徴量を抽出するものであってもよい。
例えば、特徴量抽出手段２３は、学習データが、画像データである場合、色分布、動きベクトル等を特徴量として抽出することができる。また、学習データが、音声データの場合、ケプストラム係数等、文書データの場合、形態素の出現頻度等を特徴量とすることができる。
【００４２】
この特徴量抽出手段２３で抽出された１以上の特徴量は、特徴量空間上のベクトルで表される。すなわち、１つの学習データは、特徴量空間上の１点で表される。そして、特徴量抽出手段２３は、学習データごとに抽出した特徴量をパラメータ演算手段２４に出力する。なお、以降の説明においては、学習データごとに抽出した特徴量をベクトルとし、特徴量のベクトルで表される学習データをｘｎ（ｎ＝１，２,…，Ｎ）と表記する。
【００４３】
パラメータ演算手段２４は、学習データ入力手段２２で入力され、特徴量抽出手段２３で特徴量が抽出された学習データｘｎ（ｎ＝１，２,…，Ｎ）と、当該学習データのクラスタに対応して記憶手段２１に記憶されているクラスタ中心μｋ（ｋ＝１，２,…，Ｋ）とに基づいて、マハラノビス距離の行列をパラメータとして演算するものである。
【００４４】
このパラメータ演算手段２４は、演算により求めた行列を記憶手段２１に書き込み、記憶する。なお、この記憶手段２１に記憶された行列Ａは、クラスタリング実行手段３において、データをクラスタリングする際に、クラスタ中心μｋからのマハラノビス距離を算出するために使用される。
具体的には、パラメータ演算手段２４は、以下の（３）式によりマハラノビス距離の行列Ａを演算する。
【００４５】
【数６】
2010198518.tif 000008
【００４６】
この（３）式では、学習データをベクトル表記であるｘｎで表す。なお、添字ｎは、当該学習データを識別する情報であって、｛１，２，…，Ｎ｝とする。また、クラスタ中心をベクトル表記であるμｋで表す。なお、添字ｋは、クラスタを識別する情報であって、｛１，２，…，Ｋ｝とする。さらに、ここでは、属性値をｒｎｋで表す。この属性値は、添字ｎのデータが添字ｋのクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる１−ｏｆ−ｋ表記法で表記することとする。なお、この（３）式において、添字ｎ′およびｋ′は、それぞれ添字ｎおよびｋと同じ意味を示し、二重の総和記号Σの変数を区別するために用いている。また、Ｔは転置行列を示し、ｔｒ（・）は括弧内の行列における対角成分の和（トレース）を表している。
【００４７】
このように、パラメータ演算手段２４は、学習データｘｎと、クラスタ中心μｋとを用いて、反復演算を行わずに演算を行い行列Ａを算出する。なお、この演算により、マハラノビス距離の行列を推定することができる理由については、後で説明を行うこととする。
【００４８】
クラスタリング実行手段（クラスタリング実行装置）３は、距離学習手段２で推定されたマハラノビス距離のパラメータ（行列）を用いて、クラスタリング対象のデータを、ｋ−平均（ｋ−ｍｅａｎｓ）法によりクラスタリングするものである。ここでは、クラスタリング実行手段３は、データ入力手段３１と、特徴量抽出手段３２と、クラスタ生成手段３３と、クラスタ中心更新手段３４と、クラスタ判定手段３５と、を備えている。
【００４９】
データ入力手段３１は、外部からクラスタリング対象のデータを入力するものである。このデータは、距離学習手段２においてマハラノビス距離のパラメータを学習するために用いた学習データと同種のデータである。すなわち、このデータは、画像データ、音声データ、文書データ等、その特徴量において分類可能なデータであれば、どのようなデータであっても構わない。このデータ入力手段３１は、入力したデータを特徴量抽出手段３２に出力する。
【００５０】
特徴量抽出手段３２は、データ入力手段３１で入力されたデータの特徴量を抽出するものである。この特徴量抽出手段３２は、データから抽出する特徴量の種類を、予めデータの種類に応じて定めておく。あるいは、データの種類が固定の場合は、予め定めた固有の特徴量を抽出するものであってもよい。なお、特徴量抽出手段３２が抽出する特徴量は、距離学習手段２の特徴量抽出手段３２が抽出する特徴量と同種のものとする。
【００５１】
この特徴量抽出手段３２で抽出された１以上の特徴量は、特徴量空間上のベクトルで表される。すなわち、１つのデータは、特徴量空間上の１点で表される。そして、特徴量抽出手段３２は、データごとに抽出した特徴量をクラスタ生成手段３３に出力する。なお、以降の説明においては、データごとに抽出した特徴量をベクトルとし、特徴量のベクトルで表されるデータをｚｍ（ｍ＝１，２,…，Ｍ）と表記する。
【００５２】
クラスタ生成手段３３は、データ入力手段３１で入力され、特徴量抽出手段３２で特徴量が抽出されたデータｚｍ（ｍ＝１，２,…，Ｍ）について、距離学習手段２で推定されたマハラノビス距離のパラメータ（行列Ａ）を用いて、クラスタを生成するものである。
【００５３】
ここでは、クラスタ生成手段３３は、クラスタ中心μｋとデータｚｍとの距離を、距離学習手段２で推定された行列Ａを用いて前記（１）式により計算し、データｚｍを、最も近いクラスタ中心μｋに割り当てる（分類する）ことで、Ｋ個のクラスタを生成する。このクラスタ生成手段３３は、生成したＫ個のクラスタを、クラスタ中心μｋとデータｚｍとを対応付けて図示を省略したメモリに展開することとする。なお、クラスタ生成手段３３におけるクラスタ中心の初期値は、データｚｍをクラスタ数Ｋで分割して割り当てたクラスタの中心とする。例えば、それぞれのクラスタに属するデータの特徴量空間上の平均とする。
【００５４】
また、クラスタ生成手段３３は、後記するクラスタ判定手段３５において、クラスタ生成の終了が指示された場合に、メモリ（不図示）に展開されているクラスタをクラスタ結果として出力する。なお、クラスタ生成手段３３は、後記するクラスタ判定手段３５から、クラスタ生成の継続が指示された場合、後記するクラスタ中心更新手段３４において、更新されたクラスタ中心を用いてデータｚｍのクラスタリングを行う。
【００５５】
クラスタ中心更新手段３４は、クラスタ生成手段３３で生成されたクラスタに基づいて、クラスタ中心を更新するものである。すなわち、クラスタ中心更新手段３４は、クラスタ生成手段３３で生成されたクラスタごとに、クラスタに属するデータｚｍの特徴量空間における重心を求めることで、当該クラスタの新たなクラスタ中心とする。なお、クラスタ中心更新手段３４は、新たなクラスタ中心を、旧クラスタ中心と対応付けてメモリ（不図示）に書き込む。
【００５６】
クラスタ判定手段３５は、クラスタ中心更新手段３４で更新されたクラスタ中心と、旧クラスタ中心との距離（ユークリッド距離）に基づいて、クラスタリングの終了を判定するものである。このクラスタ判定手段３５は、例えば、更新されたクラスタ中心と、旧クラスタ中心との距離（更新量）が予め定めた距離（閾値）以下となった場合に、クラスタリングが終了したものと判定する。また、このクラスタ判定手段３５は、クラスタリングが終了したと判定した場合、クラスタ生成手段３３にクラスタ生成の終了を指示する。
なお、クラスタ判定手段３５は、クラスタ生成手段３３において、更新されたクラスタ中心でデータをクラスタリングし、割り当てるクラスタに変化がなくなった場合に、クラスタリングが終了したものと判定することとしてもよい。
【００５７】
以上説明したように、クラスタリング装置１は、半教師ありクラスタリングとして、学習データに基づいて、マハラノビス距離のパラメータを推定し、そのパラメータを用いて、クラスタリング対象のデータをクラスタリングすることができる。このとき、クラスタリング装置１は、距離学習手段２において、マハラノビス距離のパラメータを、反復演算することなく推定することができ、学習データから高速にパラメータの推定を行うことができる。
【００５８】
また、クラスタリング装置１は、図示を省略したＣＰＵやメモリを搭載した一般的なコンピュータで実現することができる。このとき、クラスタリング装置１は、コンピュータを、前記した各手段として機能させるクラスタリングプログラムにより動作させることができる。
【００５９】
以上、本発明の実施形態について説明したが、本発明は、この実施形態に限定されるものではない。例えば、ここでは、クラスタリング装置１が、距離学習手段２と、クラスタリング実行手段３とでそれぞれ特徴量抽出手段２３，３２を備える構成としたが、１つの手段として構成し、入力データ（学習データ、クラスタ対象のデータ）に応じて、出力先（パラメータ演算手段２４またはクラスタ生成手段３３）を切り替える構成としてもよい。
また、この特徴量抽出手段２３，３２は、予め特徴量が抽出された学習データやクラスタ対象のデータが外部から入力される場合は、構成から省略してもよい。
【００６０】
また、ここでは、記憶手段２１に記憶するクラスタ中心μｋの値を前記（２）式に示したように、特徴量空間上の原点としたが、以下の（４）式に示すように、学習データｘｎ全体の特徴量空間上の平均（大域的平均）としてもよい。
【００６１】
【数７】
2010198518.tif 000009
【００６２】
あるいは、クラスタ中心μｋの値を、以下の（５）式に示すように、クラスタｋごとの学習データｘｎの特徴量空間上の平均（クラスタ平均）としてもよい。
【００６３】
【数８】
2010198518.tif 000010
【００６４】
また、ここでは、クラスタリング装置１を、距離学習手段２とクラスタリング実行手段３とで構成したが、これらの各手段を、別個独立した装置（クラスタリング距離学習装置、クラスタリング実行装置）として構成してもよい。
【００６５】
この場合、クラスタリング距離学習装置（距離学習手段２）、クラスタリング実行装置（クラスタリング実行手段３）は、それぞれ図示を省略したＣＰＵやメモリを搭載した一般的なコンピュータで実現することができる。また、クラスタリング距離学習装置（距離学習手段２）は、コンピュータを、距離学習手段２で説明した各手段として機能させるクラスタリング距離学習プログラムにより動作させることができる。また、クラスタリング実行装置（クラスタリング実行手段３）は、コンピュータを、クラスタリング実行手段３で説明した各手段として機能させるクラスタリング実行プログラムにより動作させることができる。
【００６６】
［クラスタリング装置の動作］
次に、図３，４を参照して、本発明の実施形態に係るクラスタリング装置の動作について説明する。なお、ここでは、クラスタリング装置１の動作として、距離学習手段２において行われる学習動作（パラメータ推定動作）と、クラスタリング実行手段３において行われるクラスタリング実行動作とに分けて説明する。
【００６７】
（学習動作）
最初に、図３を参照（構成については適宜図２参照）して、クラスタリング装置１（距離学習手段２）の学習動作（パラメータ推定動作）について説明する。なお、ここでは、記憶手段２１に、Ｋ個のクラスタ中心μｋとして、予め特徴量空間上の原点が記憶されているものとする。
【００６８】
まず、クラスタリング装置１は、距離学習手段２の学習データ入力手段２２によって、外部からマハラノビス距離のパラメータを学習するためのクラスタが既知の学習データを入力する（ステップＳ１０）。
そして、クラスタリング装置１は、距離学習手段２の特徴量抽出手段２３によって、ステップＳ１０で入力した学習データの特徴量を抽出する（ステップＳ１１）。
【００６９】
その後、クラスタリング装置１は、距離学習手段２のパラメータ演算手段２４によって、ステップＳ１１で特徴量が抽出された学習データｘｎ（ｎ＝１，２,…，Ｎ）と、当該学習データのクラスタに対応して記憶手段２１に記憶されているクラスタ中心μｋ（ｋ＝１，２,…，Ｋ）とに基づいて、前記（３）式により、マハラノビス距離の行列Ａを演算する（ステップＳ１２）。
そして、クラスタリング装置１は、距離学習手段２のパラメータ演算手段２４によって、ステップＳ１２で演算により求めたマハラノビス距離の行列Ａを、記憶手段２１に書き込み、記憶する（ステップＳ１３）。
【００７０】
以上の動作によって、クラスタリング装置１は、マハラノビス距離を算出するために使用される行列Ａを、学習によって推定することができる。
なお、ここでは、記憶手段２１に、Ｋ個のクラスタ中心μｋが予め記憶されているものとして説明したが、前記した（４）式や（５）式に示すように、学習データに応じてクラスタ中心の値を算出し記憶手段２１に記憶することとしてもよい。この場合、クラスタリング装置１は、ステップＳ１１以降に、距離学習手段２のパラメータ演算手段２４によって、ステップＳ１１で特徴量が抽出された学習データｘｎに基づいて、前記した（４）式や（５）式に示す演算を行うことでクラスタ中心μｋを算出し、記憶手段２１に書き込み、記憶する。
【００７１】
（クラスタリング実行動作）
次に、図４を参照（構成については適宜図２参照）して、クラスタリング装置１（クラスタリング実行手段３）のクラスタリング実行動作について説明する。
まず、クラスタリング装置１は、クラスタリング実行手段３のデータ入力手段３１によって、外部からクラスタリング対象のデータを入力する（ステップＳ２０）。
そして、クラスタリング装置１は、クラスタリング実行手段３の特徴量抽出手段３２によって、ステップＳ２０で入力したデータの特徴量を抽出する（ステップＳ２１）。
【００７２】
その後、クラスタリング装置１は、クラスタリング実行手段３のクラスタ生成手段３３によって、ステップＳ２１で特徴量が抽出されたデータｚｍ（ｍ＝１，２,…，Ｍ）をクラスタ数Ｋで分割し、それぞれのクラスタに属するデータの特徴量空間上の平均を求めることで、クラスタ中心の初期値を算出する（ステップＳ２２）。
【００７３】
そして、クラスタリング装置１は、クラスタリング実行手段３のクラスタ生成手段３３によって、クラスタ中心μｋと、ステップＳ２１で特徴量が抽出されたデータｚｍ（ｍ＝１，２,…，Ｍ）との距離を、距離学習手段２で推定され、記憶手段２１に記憶されている行列Ａを用いて前記（１）式により計算し、データｚｍを、最も近いクラスタ中心μｋに割り当てる（分類する）ことで、Ｋ個のクラスタを生成する（ステップＳ２３）。
【００７４】
そして、クラスタリング装置１は、クラスタリング実行手段３のクラスタ中心更新手段３４によって、ステップＳ２３で生成されたクラスタごとに、クラスタに属するデータｚｍの特徴量空間上の重心を求めることで、クラスタ中心を新たなクラスタ中心に更新する（ステップＳ２４）。
ここで、クラスタリング装置１は、クラスタリング実行手段３のクラスタ判定手段３５によって、ステップＳ２４で更新されたクラスタ中心と、旧クラスタ中心との距離差（更新量）が予め定めた距離（閾値）以下となったか否かを判定する（ステップＳ２５）。
【００７５】
そして、距離差（更新量）が閾値以下となった場合（ステップＳ２５でＹｅｓ）、クラスタリング装置１は、クラスタリング実行手段３のクラスタ生成手段３３によって、クラスタ結果を出力する（ステップＳ２６）。一方、距離差（更新量）が閾値より大きい場合（ステップＳ２５でＮｏ）、クラスタリング装置１は、ステップＳ２３に戻って、クラスタ生成手段３３によって、更新されたクラスタ中心によりクラスタを生成する動作を実行する。
以上の動作によって、クラスタリング装置１は、マハラノビス距離を用いて、ｋ−平均（ｋ−ｍｅａｎｓ）法により、データをクラスタごとにクラスタリングすることができる。
【００７６】
なお、ここでは、更新されたクラスタ中心と、旧クラスタ中心との距離差（更新量）が予め定めた距離（閾値）以下となったか否かにより、ステップＳ２５においてクラスタ生成の終了判定を行ったが、この手法に限定されるものではない。例えば、ステップＳ２３において、更新されたクラスタ中心でクラスタを生成する際に、割り当てるクラスタに変化がなくなった場合に終了と判定することとしてもよい。
【００７７】
［マハラノビス距離のパラメータ推定手法の説明］
次に、クラスタリング装置１が、距離学習手段２のパラメータ演算手段２４において、マハラノビス距離の算出に用いるパラメータ（行列）を、反復演算を行うことなく、前記（３）式の演算により求めることができる理由について説明する。
【００７８】
学習データｘｎを最も精度よくクラスタリングするマハラノビス距離Ｍ（前記（１）式参照）の学習は、以下の（６）式に示す行列Ａとクラスタ中心μｋの関数Ｊを最小にする問題と捉えることができる。
【００７９】
【数９】
2010198518.tif 000011
【００８０】
この関数Ｊは、クラスタｋのクラスタ中心μｋと、当該クラスタｋに属する学習データｘｎとのマハラノビス距離Ｍの和を、すべてのクラスタｋ（ｋ＝１，２,…，Ｋ）について総和する関数である。なお、ｒｎｋは、添字ｎの学習データが添字ｋのクラスタに属する場合に値“１”、それ以外の場合に値“０”をとる。
ここで、関数Ｊ（Ａ，μｋ）を、行列Ａで偏微分すると、以下の（７）式を得る。
【００８１】
【数１０】
2010198518.tif 000012
【００８２】
この（７）式の右辺は、共分散行列である。つまり、その共分散行列の対角成分は、ｘｎ＝μｋでない限り正であり、前記（７）式の値は増大し続けるため、最小解が存在しないことになる。そこで、行列Ａの大きさを制限する拘束条件として、以下の（８）式を導入する。
【００８３】
【数１１】
2010198518.tif 000013
【００８４】
なお、Ｔは転置行列を示し、ｔｒ（・）は括弧内の行列の対角成分の和（トレース）を表している。
この（８）式の拘束条件の下で、前記（６）式を最小にする行列Ａを決定する問題は、拘束条件付最小化問題であるため、ラグランジュの未定乗数αを導入して、以下の（９）式を最小化すればよいことになる。
【００８５】
【数１２】
2010198518.tif 000014
【００８６】
ここで、この（９）式を行列Ａで偏微分すると、以下の（１０）式を得る。
【００８７】
【数１３】
2010198518.tif 000015
【００８８】
この（１０）式が値“０”となる行列Ａは、以下の（１１）式で求められる。
【００８９】
【数１４】
2010198518.tif 000016
【００９０】
ここで、前記（８）式の拘束条件に、この（１１）式で求められた行列Ａを代入すると、以下の（１２）式を得る。
【００９１】
【数１５】
2010198518.tif 000017
【００９２】
この（１２）式を変形することで、以下の（１３）式を得る。
【００９３】
【数１６】
2010198518.tif 000018
【００９４】
この（１３）式の結果を、前記（１１）式に代入することで、前記（３）式の行列Ａを得ることができる。
以上説明したように、行列Ａに拘束条件を設けることで、前記（３）式に示した行列Ａは、学習データｘｎを最も精度よくクラスタリングするマハラノビス距離Ｍを算出するための行列となる。これによって、図２で説明した距離学習手段２のパラメータ演算手段２４は、行列Ａを反復演算することなく、前記（３）式の演算により、学習データを精度よくクラスタリングする行列を学習することができる。
【００９５】
なお、ここでは、拘束条件として、ｔｒ（ＡＴＡ）の値を“１”としたが、この値は“１”である必要はなく、任意の定数であればよい。
すなわち、定数をｃとしたとき、拘束条件は、以下の（１４）式となる。
【００９６】
【数１７】
2010198518.tif 000019
【００９７】
この場合、前記（１２）式、（１３）式と同様の式の変形を行うことで、（１５）式に示す行列Ａを得ることができる。
【００９８】
【数１８】
2010198518.tif 000020
【００９９】
よって、図２で説明した距離学習手段２のパラメータ演算手段２４は、前記（３）式の代わりに、この（１５）式を用いて、行列Ａを演算することとしてもよい。ただし、（１５）式において、１／ｃにより小数点演算が行われることから、ＣＰＵの負荷を軽減するため、定数ｃは“１”であることが望ましいといえる。
【符号の説明】
【０１００】
１      クラスタリング装置
２      距離学習手段（クラスタリング距離学習装置）
２１    記憶手段（クラスタ中心記憶手段）
２２    学習データ入力手段
２３    特徴量抽出手段
２４    パラメータ演算手段
３      クラスタリング実行手段（クラスタリング実行装置）
３１    データ入力手段
３２    特徴量抽出手段
３３    クラスタ生成手段
３４    クラスタ中心更新手段
３５    クラスタ判定手段
【図１】
2010198518.tif 000024
【図２】
2010198518.tif 000025
【図３】
2010198518.tif 000026
【図４】
2010198518.tif 000027