(57)【要約】【課題】クラスタリングの再計算が不要で且つ既存のクラスタリング結果に影響を及ぼすことなく適切なデータの分類を行う。【解決手段】新規データＺを訓練データＸから学習した変換行列Ｍによって固有空間に変換するデータ分類装置１であって、訓練データＸ間の類似度行列Ｋを計算する類似度計算部５と、類似度行列Ｋと訓練データＸに対応した固有ベクトルＱとに基づき類似度行列Ｋをその固有空間に変換するための変換行列Ｍを算出する固有空間学習部６と、新規データＺの分類処理時に類似度計算部５によって算出された訓練データＸと新規データＺとの類似度行列Ｈと固有空間学習部６によって算出された変換行列Ｍとから新規データＺを固有空間に変換する固有空間変換部７と備える。【選択図】図１
2012088972.tif 000002
【特許請求の範囲】
【請求項１】
新規データを訓練データから学習した変換行列によって固有空間に変換するデータ分類装置であって、
訓練データ間の類似度行列を計算する類似度計算手段と、
前記類似度行列と当該訓練データに対応した固有ベクトルとに基づき当該類似度行列をその固有空間に変換するための変換行列を算出する固有空間学習手段と、
新規データの分類処理時に前記類似度計算手段によって算出された前記訓練データと当該新規データとの類似度行列と前記固有空間学習手段によって算出された変換行列とから当該新規データを固有空間に変換する固有空間変換手段と
を備えた
を特徴とするデータ分類装置。
【請求項２】
前記訓練データとその類似度、クラスタ数及びクラスタリングの繰返し数に基づき当該訓練データのスペクトラルクラスタリングを行うことにより前記訓練データに対応した固有ベクトル、クラスタ中心を算出するスペクトラルクラスタリング手段をさらに備えたこと
を特徴とする請求項１に記載のデータ分類装置。
【請求項３】
前記固有空間変換手段によって算出された固有空間のデータを当該データと最も距離の近い前記クラスタ中心に割当てるデータ割当て手段をさらに備えたこと
を特徴とする請求項２に記載のデータ分類装置。
【請求項４】
新規データを訓練データから学習した変換行列によって固有空間に変換するデータ分類方法であって、
類似度計算手段が訓練データ間の類似度行列を計算するステップと、
固有空間学習手段が前記類似度行列と当該訓練データに対応した固有ベクトルとに基づき当該類似度行列をその固有空間に変換するための変換行列を算出するステップと、
前記類似度計算手段が新規データと前記訓練データとの類似度行列を計算するステップと、
固有空間変換手段が前記類似度行列と前記変換行列とから新規データを固有空間に変換するステップと
を有することを特徴とするデータ分類方法。
【請求項５】
スペクトラルクラスタリング手段が前記訓練データとその類似度、クラスタ数及びクラスタリングの繰返し数に基づき当該訓練データのスペクトラルクラスタリングを行うことにより前記訓練データに対応した固有ベクトル、クラスタ中心を算出するステップ
をさらに有すること
を特徴とする請求項４に記載のデータ分類方法。
【請求項６】
データ割当て手段が前記固有空間変換手段によって算出された固有空間のデータを当該データと最も距離の近い前記クラスタ中心に割当てるステップ
をさらに有すること
を特徴とする請求項５に記載のデータ分類方法。
【請求項７】
請求項１から３のいずれか１項に記載のデータ分類装置を構成する各手段としてコンピュータを機能させることを特徴とするデータ分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、教師なしデータ分類技術に関し、特にテキストや画像などのデータをクラスタリングした後に未知のデータを既に生成したクラスタに分類するデータ分類する技術に関する。
【背景技術】
【０００２】
従来、教師なしデータ分類手法として、例えば非特許文献１に示すようなスペクトラルクラスタリングという手法が知られている。
【０００３】
スペクトラルクラスタリングは、表１に示したＡｌｇｏｒｉｔｈｍ１のように、ｎ組のデータｘi∈Ｒm及びパラメーターデータ間の類似度τ，クラスタ数ｋ，ｋ‐ｍｅａｎｓクラスタリングの繰り返し回数Ｔが与えられた場合、ｎ組のデータをｋ個のクラスタに分類するデータ分類手法である。尚、ｋ‐ｍｅａｎｓクラスタリングは非特許文献２に示されている。
【０００４】
【表１】
2012088972.tif 000003
【０００５】
スペクトラルクラスタリングは入力データをノード、入力データ間の親和度をエッジの重みとするグラフとみなして、これをｋ個に分割する。切断するエッジの重みの総和を小さく、かつ、分割後のノード数が均等になるような分割が選ばれる。
【０００６】
８個のデータ間に重み１のエッジが付けられたグラフの例を図１３に示した。このグラフを２つに分割すると図１４に示したような結果となる。切断されたエッジは２と小さく、分割後のノード数は共に４と均等になっている。スペクトラルクラスタリングは、入力データの親和行列から固有ベクトルを計算して、入力データを図１３に示したように固有空間にマッピングし、この空間で表２に示したＡｌｇｏｒｉｔｈｍ２のｋ‐ｍｅａｎｓ法を行うことで実現する。
【０００７】
【表２】
2012088972.tif 000004
【０００８】
より具体的な例として、ｋ＝２、τ＝２００、Ｔ＝２００でスペクトラルクラスタリングした例を図５に示す。
【０００９】
Ａｌｇｏｒｉｔｈｍ１の手順２〜５で入力データｘiが固有空間のデータｙiに変換される。固有空間のデータの分布は図６に示されたようなデータＹの分布となる。次に、この固有空間のデータをクラスタ数ｋ＝２，繰り返し数Ｔ＝２００で表２に示されたＡｌｇｏｒｉｔｈｍ２の手順１〜６によってｋ−ｍｅａｎｓクラスタリングを実行する。この結果、図７に示されたｃｅｎｔｒｏｉｄで示すクラスタ中心、及び、クラスタインデクスｇで分類されたデータｇi＝０とｇi＝１が得られる。
【００１０】
クラスタインデクスで元のデータを分類した結果は図８に示したようなクラスタリング結果となる。螺旋状のデータが適切に２つに分離されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Andrew Y.Ng,Michael I.Jordan, and Yair Weiss.“On spectral clustering: analysis and an algorithm.”Neural Information Processing Symposium 14, 2001.
【非特許文献２】Ｃ.Ｍ.ビショップ，「パターン認識と機械学習 下」，シュプリンガー・ジャパン株式会社，２００８年７月１日，ｐｐ.１４０−１４２
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述のスペクトラルクラスタリングでは、訓練データ−クラスタリング時に与えられたｘi以外のデータを分類できないという問題があった。
【００１３】
スペクトラルクラスタリングで求められたクラスタ中心ｃj（ｊ＝１，…，ｋ）は、元のデータとは異なる空間にあり、新規のデータを分類するにはこの空間への変換手段が必要となる。
【００１４】
例えば、図１４に示されたクラスタリング結果に新規データを割当てようとしても、スペクトラルクラスタリングには図１５に示した固有空間に新規データをマッピングする方法が用意されていないため、分類することができない。そのため新規データを追加してスペクトラルクラスタリングをやり直す必要がある。
【００１５】
また、新規データの影響でクラスタリング結果が異なる場合もある。例えば、図１６に示されたサンプルグラフのように新規データ９が追加されると、図１７に示したように元の分割では切断エッジ数が４となる。切断エッジ数が３の新たな分割が選ばれ、元のデータのクラスタリング結果も変わる。
【００１６】
本発明は、上記問題を解決するものであり、新規のデータを訓練データで作成したクラスタリング結果に分類する際に、クラスタリングの再計算が不要で且つ既存のクラスタリング結果に影響を及ぼさない適切なデータの分類を目的とする。
【課題を解決するための手段】
【００１７】
そこで、本発明は、図２に示したように、訓練データＸの処理の際、訓練データＸ間の類似度行列Ｋを計算し、この類似度行列と訓練データＸの固有値Ｑに対応する固有ベクトルに基づき変換行列Ｍを算出する。次いで、新規データＺの処理の際、新規データＺと訓練データＸとの類似度行列Ｈを計算し、この類似度行列Ｈと変換行列Ｍとから新規データＺを固有空間に変換したデータを算出する。これにより新規データＺの固有空間のデータＶへの変換が可能となる。
【００１８】
すなわち、本発明のデータ分類装置の態様としては、新規データを訓練データから学習した変換行列によって固有空間に変換するデータ分類装置であって、訓練データ間の類似度行列を計算する類似度計算手段と、前記類似度行列と当該訓練データに対応した固有ベクトルとに基づき当該類似度行列をその固有空間に変換するための変換行列を算出する固有空間学習手段と、新規データの分類処理時に前記類似度計算手段によって算出された前記訓練データと当該新規データとの類似度行列と前記固有空間学習手段によって算出された変換行列とから当該新規データを固有空間に変換する固有空間変換手段とを備える。
【００１９】
また、本発明のデータ分類方法の態様としては、新規データを訓練データから学習した変換行列によって固有空間に変換するデータ分類方法であって、類似度計算手段が訓練データ間の類似度行列を計算するステップと、固有空間学習手段が前記類似度行列と当該訓練データに対応した固有ベクトルとに基づき当該類似度行列をその固有空間に変換するための変換行列を算出するステップと、前記類似度計算手段が新規データと前記訓練データとの類似度行列を計算するステップと、固有空間変換手段が前記類似度行列と前記変換行列とから新規データを固有空間に変換するステップとを有する。
【００２０】
尚、本発明は上記データ分類装置を構成する各手段としてコンピュータを機能させるデータ分類プログラムの態様とすることもできる。
【発明の効果】
【００２１】
以上の発明によれば新規のデータを訓練データで作成したクラスタリング結果に分類する際にクラスタリングの再計算が不要となると共に既存のクラスタリング結果に影響を及ぼすことなく適切なデータ分類が行える。
【図面の簡単な説明】
【００２２】
【図１】発明の実施形態に係るデータ分類装置のブロック図。
【図２】発明に係るデータ分類処理の概要を説明した概要図。
【図３】発明の実施形態に係る訓練データの処理手順を示したチャート図。
【図４】発明の実施形態に係る新規データの分類手順を示したチャート図。
【図５】入力データの一例。
【図６】固有空間のデータｙiの分布の一例を示した図。
【図７】固有空間でのクラスタリングの一例を示した図。
【図８】クラスタインデクスの一例を示した図。
【図９】新規データの一例を示した図。
【図１０】固有空間に変換された新規データの一例を示した図。
【図１１】固有空間で分類された新規データの一例を示した図。
【図１２】分類結果の一例を示した図。
【図１３】サンプルグラフの一例を示した図。
【図１４】サンプルグラフの分割結果を示した図。
【図１５】固有空間の一例を示した図。
【図１６】新規データが追加されたサンプルグラフの一例を示した図。
【図１７】新規データが追加されたサンプルグラフの分割結果の一例を示した図。
【発明を実施するための形態】
【００２３】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００２４】
（概要）
図１に示された本発明の実施形態に係るデータ分類装置１は、訓練データＸの処理の際、訓練データＸ間の類似度行列Ｋを計算し、この類似度行列と訓練データＸの固有値に対応する固有ベクトルＱに基づき変換行列Ｍを算出する。次いで、新規データＺの処理の際、新規データＺと訓練データＸとの類似度行列Ｈを計算し、この類似度行列Ｈと変換行列Ｍとから新規データＺを固有空間に変換したデータを算出する。これにより新規データＺの固有空間のデータＶへの変換が可能となる。
【００２５】
（装置の構成）
データ分類装置１は、図１に示されたように、データ入力部２、スペクトラルクラスタリング部３、蓄積部４、類似度計算部５、固有空間学習部６、固有空間変換部７、データ割当て部８、結果出力部９を備える。
【００２６】
データ分類装置１の各機能部２〜９は例えばコンピュータのハードウェアリソースによって実現される。すなわち、データ分類装置１はＣＰＵ、メモリ、記憶装置（例えば、ハードディスクドライブ装置）、Ｉ／Ｏデバイス（例えば、ネットワークデバイス、ＵＳＢ等）等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソース（ＯＳ、アプリケーション等）と協働することにより機能部２〜９が実装される。
【００２７】
データ入力部２はネットワークまたはファイル等からＩ／Ｏデバイスを介して訓練データｘi∈Ｒm（ｉ＝１，…，ｎ）、クラスタ数ｋ、訓練データｘi間の類似度τ及びｋ‐ｍｅａｎｓクラスタリングの繰り返し数Ｔの入力を受ける。また、前記Ｉ／Ｏデバイスを介して新規データｚj∈Ｒm（ｊ＝１，…，ｌ）の入力を受ける。
【００２８】
スペクトラルクラスタリング部３は訓練データｘiのスペクトラルクラスタリングを行い、訓練データｘiの固有ベクトルｑi、クラスタ中心ｃi、及びクラスタインデクスｇを算出する。前記スペクトラルクラスタリングには例えば前述の表１のＡｌｇｏｒｉｔｈｍ１を用いた非特許文献１のスペクトラルクラスタリング手法が適用される。
【００２９】
蓄積部４は前記入力された訓練データｘi、上記パラメータｋ，τ，Ｔ、固有ベクトルＱ、クラスタ中心ｃi及び変換行列Ｍ（訓練データｘiから得られたもの）を蓄積する。
【００３０】
類似度計算部５は、訓練データｘiの処理の際に、蓄積部４から訓練データｘi、パラメータτを引き出して下記の式（１）による訓練データｘi間の類似度行列Ｋ(＝ｋij)の計算を行う。
【００３１】
【数１】
2012088972.tif 000005
【００３２】
また、類似度計算部５は、新規データｚjの処理の際に、蓄積部４から訓練データｘi、パラメータτを引き出して下記の式（２）による訓練データｘiと新規データｚjの類似度行列Ｈ(＝ｈij)の計算を行う。
【００３３】
【数２】
2012088972.tif 000006
【００３４】
固有空間学習部６は、訓練データｘiの処理の際に、前記算出された訓練データｘiの類似度行列Ｋと蓄積部４から引き出した固有ベクトルＱとから下記の式（３）のｋ組の連立一次方程式を作る。そして、この方程式をガウスの消去法などで解き、変換行列Ｍ＝（ｍ1，…，ｍk）を計算する。尚、式（３）のｑiは固有ベクトルＱの成分である。
【００３５】
【数３】
2012088972.tif 000007
【００３６】
固有空間変換部７は、新規データｚiの処理の際に、下記の式（４）のように訓練データｘiと新規データｚjとの類似度行列Ｈと蓄積部４に蓄積された変換行列Ｍとの積Ｕを計算する。
【００３７】
【数４】
2012088972.tif 000008
【００３８】
そして、固有空間変換部７は、積Ｕの全ての行を単位ベクトルに正規化し、さらに転置した後、下記の式（５）による演算によって固有空間のデータＶ＝（ｖ1，…，ｖl），ｖi＝（ｖil，…，ｖik）を算出する。
【００３９】
【数５】
2012088972.tif 000009
【００４０】
データ割当て部８は固有空間変換部７によって算出されたデータｖ1，…，ｖlを下記の式（６）（７）のように当該データと最も距離の近いクラスタ中心ｃjに割当てる。
【００４１】
【数６】
2012088972.tif 000010
【００４２】
結果出力部９はＩ／Ｏデバイスを介してネットワークまたはファイルなどに訓練データｘiのクラスタインデクスｇ及び新規データｚiの割当てｂを出力する。
【００４３】
（処理手順の説明）
図３を参照しながらデータ分類装置１による訓練データの具体的な処理手順Ｓ１０１〜Ｓ１０４について説明する。
【００４４】
Ｓ１０１：データ入力部２はＩ／Ｏデバイスを介して図５に例示した訓練データ、及び、パラメータ（ｋ＝２，τ＝２００，Ｔ＝２００）の入力を受けると、これらのデータを蓄積部４に蓄積される。
【００４５】
Ｓ１０２：スペクトラルクラスタリング部３は蓄積部４から訓練データＸ及びパラメータ（ｋ＝２，τ＝２００，Ｔ＝２００）を引き出し、上述のスペクトラルスタリングによって図６に示されたＹの分布からなる訓練データをその固有空間である固有ベクトルＱに変換し、図７に示したｃｅｎｔｒｏｉｄのクラスタ中心ｃiを計算する。さらに、図８に示したクラスタインデクスｇを算出する。以上の算出されたｋ個の固有ベクトルＱ＝（ｑ1，…，ｑk）、クラスタ中心ｃi、クラスタインデクスｇは蓄積部４に蓄積される。尚、前記訓練データのクラスタインデクスｇは結果出力部９によって出力される。
【００４６】
Ｓ１０３：類似度計算部５は蓄積部４に蓄積された訓練データＸから前記（１）式による演算によって類似度行列Ｋを算出する。この類似度行列Ｋは蓄積部４に蓄積する。
【００４７】
Ｓ１０４：固有空間学習部６は蓄積部４から訓練データＸの類似度行列Ｋを引き出し、この類似度行列Ｋが適用された前記式（３）から固有ベクトルＱへの変換行列Ｍを算出する。この変換行列Ｍは蓄積部４に蓄積される。
【００４８】
次に図４を参照しながら新規データの具体的な分類手順Ｓ２０１〜Ｓ２０４について説明する。
【００４９】
Ｓ２０１：データ入力部２がＩ／Ｏデバイスを介して図９に例示された新規データＺの入力を受けると類似度計算部５に供する。
【００５０】
Ｓ２０２：類似度計算部５はデータ入力部２から供された新規データＺと蓄積部４から引き出した訓練データＸとから前記（２）式の演算によって当該新規データＺと当該訓練データＸとの類似度行列Ｈを計算し、蓄積部４に蓄積する。
【００５１】
Ｓ２０３：固有空間変換部７は、蓄積部４から類似度行列Ｈと変換行列Ｍとを引き出し、前記（４）（５）式の演算を行う。この演算によって前記新規データＺは固有空間に変換される。その結果、図１０に示されたデータＶの分布が得られる。
【００５２】
Ｓ２０４：データ割当て部８はＳ２０３で固有空間に変換された新規データＺを前記（６）（７）式の演算によりクラスタ中心に割当てる。その結果、図１１に示したようにデータＶがクラスタ０とクラスタ１に分けられる。
【００５３】
結果出力部９はＳ２０４で得られた新規データＺの割当てｂを出力する。図１２に示されたように新規データＺがスペクトラルクラスタリングの結果に従って適切に割当てられている。
【００５４】
（本実施形態の効果）
以上のようにデータ分類装置１は訓練データおよびそれに対応する固有ベクトルから固有空間への変換方法を学習して新規データにその変換を適用する。したがって、スペクトラルクラスタリングで得られたクラスタに新規のデータを適切に割当てることができる。
【００５５】
また、従来技術（スペクトラルクラスタリング）は親和行列（類似度行列）の固有ベクトルを計算するため、データ数に応じた大量の計算を必要とする。これに対して本発明の実施形態に係るデータ分類装置１は、入力データをサンプリングした少数のデータでスペクトラルクラスタリングを行い、残りのデータをクラスタリング結果に分類することで、データ分類に要する計算量を削減できる。
【００５６】
特に、本実施形態では、訓練データの処理の過程で、スペクトラルクラスタリング部３が前記訓練データとその類似度、クラスタ数及びクラスタリングの繰返し数に基づく当該訓練データのスペクトラルクラスタリングによって前記訓練データに対応した固有ベクトルを算出する。これにより、固有空間学習部６での変換行列の算出を効率的に行える。また、前記スペクトラルスタリングによって前記訓練データのクラスタ中心が算出されるのでデータ割当て部８での新規データの固有空間での割当てを効率的に行える。
【００５７】
さらに、データ割当て部８によって前記固有空間のデータが当該データと最も距離の近い前記クラスタ中心に割当てられるので新規データが当該固有空間において明確に分類される。
【００５８】
本実施形態のデータ分類技術は例えばテキストデータや画像データの分類に有効である。
【００５９】
（本発明のプログラムとしての態様）
本発明は上記の実施形態のデータ分類装置１に係る各機能部２〜９の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータによって実行して本発明を実現することができる。また、本実施形態の処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができる。さらに、コンピュータで前記機能を実現するためのプログラムをそのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００６０】
１…データ分類装置
３…スペクトラルクラスタリング部（スペクトラルクラスタリング手段）
５…類似度計算部（類似度計算手段）
６…固有空間学習部（固有空間学習手段）
７…固有空間変換部（固有空間変換手段）
８…データ割当て部（データ割当て手段）
【図１】
2012088972.tif 000011
【図２】
2012088972.tif 000012
【図３】
2012088972.tif 000013
【図４】
2012088972.tif 000014
【図５】
2012088972.tif 000015
【図６】
2012088972.tif 000016
【図７】
2012088972.tif 000017
【図８】
2012088972.tif 000018
【図９】
2012088972.tif 000019
【図１０】
2012088972.tif 000020
【図１１】
2012088972.tif 000021
【図１２】
2012088972.tif 000022
【図１３】
2012088972.tif 000023
【図１４】
2012088972.tif 000024
【図１５】
2012088972.tif 000025
【図１６】
2012088972.tif 000026
【図１７】
2012088972.tif 000027