JP7020331B2 - クラスタリング装置、方法、及びプログラム - Google Patents

Description

本発明は、クラスタリング装置、方法、及びプログラムに係り、特に、データ集合をクラスタリングするためのクラスタリング装置、方法、及びプログラムに関する。

音声、音楽などの音響信号や画像信号などディジタル信号を分類する方法に関する技術がある。データ点の集合が複数の部分空間の集合の上に属すると見なせる場面が存在する。そのようなデータ点の集合を、同じ部分空間上のデータ点同士に分類する問題は部分空間クラスタリングと呼ばれる。図１に部分空間クラスタリングの概念図を示す。部分空間クラスタリングは画像クラスタリングやデータマイニングに用いられる重要な問題である。

図１左に示すデータ集合を、図１右に示すように、左斜線上の点を同一クラスタに、右斜線上の点を同一クラスタに、平面上の点を同一クラスタにまとめ上げることができた場合が正解となる。

従来、部分空間クラスタリングのために多様な枠組みが提案されてきたが、特にスペクトラルクラスタリングベースの枠組みが扱いやすさや精度の観点から有望視されている。スペクトラルクラスタリングベースの部分空間クラスタリングは、初めに、（１）同一の部分空間に属する点ほど類似度が大きくなるような基準を用いて類似度行列を構成する（図２を参照）。次に、（２）得られた類似度行列を元にスペクトラルクラスタリングによりクラスタリングを実行する、という二段階のステップから構成される枠組みである。

ここで、（１）の類似度行列を作るステップにおいて、類似度はどのように計算するべきかを検討する。類似度行列をＭ∈Ｒ^ＮｘＮとし、Ｍ_ｉｊにはｉ番目とｊ番目のデータの類似度が格納されているものとする。類似度の計算方法としては、同一の部分空間に属するデータの点同士は類似度がなるべく大きくなり、異なる部分空間に属する点同士は類似度がゼロもしくはなるべく小さくなるような方法を採用するべきである。類似度の定義方法としては複数のものが提案されてきたが、近年では自己表現アプローチと呼ばれるアプローチが主流になっており、以下、自己表現アプローチに基づいた手法を説明する。

自己表現アプローチは、「データの各点は同一の部分空間に属する少数個の点の線形結合で表現することができる」という考えに基づいたアプローチである。例えば、図３において、一つの丸で囲われている点について考える。この点を、なるべく少ない数の他の点の線形結合で再構成したい場合、例えば、同一の部分空間に属する丸で囲われた２点だけを用いて表現することができるだろう。このように、なるべく少ない点の線形結合で各点を再構成しようとすると、その点と同じ部分空間に属する点だけが選択されて線形結合のために用いられるのである。この性質を利用して類似度を計算するのが自己表現アプローチである。

以下、自己表現アプローチのより具体的な説明を述べる。自己表現アプローチでは、はじめに次の（１）式の目的関数を解く。

・・・（１）

ここでＸ∈Ｒ^Ｄ×Ｎはデータ集合の各データを要素とするデータ行列である。Ｚ∈Ｒ^Ｎ×Ｎは線形結合の重みに相当する行列であり、自己表現行列と呼ばれる。自己表現行列は、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする。Ｘ－ＸＺはＸをＸの線形結合ＸＺで表現した場合の残差であり、ｈ（Ｘ－ＸＺ）は残差に罰則をかける項である。ｒ（Ｚ）は、Ｘの各点を他の点の線形結合で表現する際に、なるべく少ない数の点だけが用いられるようにするための正則化項である。つまりＺの要素のうちなるべく多くの要素がゼロになるように促す項である。λは二つの項のバランスを取るためのパラメータである。ＣはＺの条件となる行列集合である。

自己表現アプローチでは自己表現行列Ｚを計算した後に、得られたＺを元に類似度行列Ｍを計算する。代表的な類似度行列の定義方法としてはＭ_ｉｊ＝｜Ｚ_ｉｊ｜＋｜Ｚ_ｊｉ｜とすることでＭを定義する方法などが挙げられる。そして、計算した類似度行列Ｍをスペクトラルクラスタリングといったグラフクラスタリングのためアルゴリズムにより分類することでクラスタリング結果を得る。図４に自己表現アプローチのフローの一例を示す。

非特許文献１に記載の手法では（１）式において、ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ、ｒ（Ｚ）＝｜｜Ｚ｜｜^２ _Ｆを、そして条件集合ＣにはＣ＝Ｒ^ＮｘＮもしくはＣ＝｛Ｚ｜Ｚ∈Ｒ^ＮｘＮ，Ｚ_ｉｉ＝０｝を用いることを提案している。行列集合Ｃとしてどちらを用いた場合においてもＺに閉じた解が存在するため、（１）式が高速に計算可能である。

Can-Yi Lu, Hai Min, Zhong-Qiu Zhao Lin Zhu, De-Shuang Huang, and Shuicheng Yan. "Robust and Efficient Subspace Segmentation via Least Squares Regression", ECCV2012

従来技術では、他のデータ全てを線形結合の候補として用いて再構成を行う。実世界データの集合には大きな外乱（例えばスパイクノイズや全く異なるカテゴリのデータ）の乗ったデータが混じることがしばしば起こることが考えられる。そのため、再構成の際にデータ集合中の全てのデータを考慮する場合、大きな外乱の乗ったデータも全て考慮されることになり、これらのデータから結果が悪影響を受ける可能性がある。例えば図５の（ａ）のような１次元部分空間から生成されたデータ集合において、（ａ）の丸で囲われたデータを他の点の線形結合によって表現することを考える。全ての点を線形結合の候補として使う場合、例えば図５（ｂ）に示すように少し１次元部分空間から外れたところにあるデータを用いて表現することができてしまう。このような場合、図５（ｂ）の点線の部分にも１次元部分空間があるのではないかと誤認識してしまう恐れがある。

本発明は、上記問題点を解決するために成されたものであり、ノイズの影響を抑えた自己表現行列を用いて、クラスタリングをすることができるクラスタリング装置、方法、及びプログラムを提供することを目的とする。

上記目的を達成するために、第１の発明に係るクラスタリング装置は、予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、前記データ集合におけるデータの各点と、前記自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みをかけた、前記自己表現行列においてユークリッドノルムの大きな前記データの各点の線形重みを小さくするための第１正則化項と、前記自己表現行列に関する第２正則化項とによって表される目的関数を最小化するような前記自己表現行列を算出する自己表現行列算出部と、算出された前記自己表現行列で定義される類似度行列を計算する類似度計算部と、前記類似度行列に基づいて前記データ集合をクラスタリングしたクラスタリング結果を得るクラスタリング部と、を含んで構成されている。

第２の発明に係るクラスタリング方法は、自己表現行列算出部が、予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、前記データ集合におけるデータの各点と、前記自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みをかけた、前記自己表現行列においてユークリッドノルムの大きな前記データの各点の線形重みを小さくするための第１正則化項と、前記自己表現行列に関する第２正則化項とによって表される目的関数を最小化するような前記自己表現行列を算出するステップと、類似度計算部が、算出された前記自己表現行列で定義される類似度行列を計算するステップと、クラスタリング部が、前記類似度行列に基づいて前記データ集合をクラスタリングしたクラスタリング結果を得るステップと、を含んで実行することを特徴とする。

第３の発明に係るプログラムは、コンピュータを、第１の発明に記載のクラスタリング装置の各部として機能させるためのプログラムである。

本発明のクラスタリング装置、方法、及びプログラムによれば、予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、データ集合におけるデータの各点と、自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みをかけた、自己表現行列においてユークリッドノルムの大きなデータの各点の線形重みを小さくするための第１正則化項と、自己表現行列に関する第２正則化項とによって表される目的関数を最小化するような自己表現行列を算出し、算出された自己表現行列で定義される類似度行列を計算し、類似度行列に基づいてデータ集合をクラスタリングしたクラスタリング結果を得ることにより、ノイズの影響を抑えた自己表現行列を用いて、クラスタリングをすることができる、という効果が得られる。

データ集合のクラスタリングの一例を示す図である。 同一の部分空間に属する点ほど類似度が大きくなるようにすることの一例を示す概念図である。 点を同一の部分空間に属する２点の線形結合で再構成する場合の一例を示す概念図である。 自己表現アプローチのフローの一例を示す図である。 部分空間におけるデータ集合について線形結合を表現した場合の概念図である。 本発明の実施の形態に係るクラスタリング装置の構成を示すブロック図である。 本発明の実施の形態に係るクラスタリング装置におけるクラスタリング処理ルーチンを示すフローチャートである。

以下、図面を参照して本発明の実施の形態を詳細に説明する。

＜本発明の実施の形態に係る概要＞

まず、本発明の実施の形態における概要を説明する。

前述の問題を解決するために、データ集合の中から一部のデータをランダムサンプリングし、それだけを用いて（１）式を解く方法を検討する。図５の例を元に説明する。図５（ｃ）は図５（ａ）のデータからランダムサンプリングした場合の一例である。大きなノイズの乗ったデータの数がそうでないデータと比べて少ない場合、ランダムサンプリングをすることでノイズの乗ったデータの大部分を無視することができるようになり、データの各点が実際の部分空間上からあまりずれていないデータによって表現される傾向を強めることができるようになる。図５（ｄ）は同一の部分空間上の線形結合によってデータの点を表すことを想定した一例である。

まず、本発明の実施の形態の具体的な構成を説明する前に、本発明の実施の形態に係る手法の着想の経緯を述べる。以下では、ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆを用いることを考える。はじめに各データを確率α∈（０，１）のベルヌーイ分布に従って選択し、その結果選択されたデータだけを用いて（１）式を定義し直すと次の（２）式のようになる。

・・・（２）

ここでＰ～ｐ（Ｐ）は各データを確率αで選択する選択行列である。（２）式をそのまま用いるとＰによって選択されなかったデータに相当する部分のデータは選ばれない。そこでＦの部分で期待値をとることを考える。

・・・（３）

更に、Ｅ［｜｜Ｆ｜｜^２ _Ｆ］は次のように変形できる。

・・・（４）

ここでｄｉａｇ（ｘ）はベクトルｘを対角成分にもつ対角行列を返す演算子、Ｄｉａｇ（Ｘ）は正方行列Ｘの対角成分だけを抜き出してベクトルとする演算子、ｔｒａｃｅ（Ｘ）はｔｒａｃｅ演算子（つまり対角成分の和）である。そしてＺ’＝αＺである。

更に、Ｚの条件である行列集合ＣとしてＣ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ，Ｚ_ｉｉ＝０｝を選択すると（３）式は次のように変形できる。

・・・（５）

（５）式から、新たな正則化項｜｜Ｄｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５Ｚ’｜｜^２ _Ｆが自然と導出できる。この項を導入することにより、Ｚの各要素に重み付けをすることができる。以上の式変形による導出を元に、以下、本発明の実施の形態の構成を説明する。

＜本発明の実施の形態に係るクラスタリング装置の構成＞

本発明の実施の形態に係るクラスタリング装置の構成について説明する。図６に示すように、本発明の実施の形態に係るクラスタリング装置１００は、ＣＰＵと、ＲＡＭと、後述するクラスタリング処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このクラスタリング装置１００は、機能的には図６に示すように入力部１０と、演算部２０と、出力部５０とを備えている。

入力部１０は、処理の対象とするデータ集合を受け付ける。

演算部２０は、自己表現行列算出部３０と、類似度計算部３２と、クラスタリング部３４とを含んで構成されている。

自己表現行列算出部３０は、受け付けたデータ集合について、予め定められた行列集合Ｃのうち、以下（６）式の目的関数を最小化するような自己表現行列を算出する。

・・・（６）

上記（６）式によって表される目的関数は、行列集合Ｃに含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列Ｚを求めるための目的関数である。目的関数は次の各項によって表される。ｈ（Ｘ－ＸＺ）は、データ集合における各データを要素とするデータ行列Ｘのデータの各点と、自己表現行列Ｚを用いた各点の線形結合で表現されたデータの各点との残差を求める項である。｜｜Ｄｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５Ｚ｜｜^２ _Ｆは、自己表現行列Ｚにおいて、ユークリッドノルムの大きなデータの各点の線形重みを小さくするための第１正則化項である。第１正則化項には、所定の重みβをかける。ｒ（Ｚ）は、自己表現行列に関する第２正則化項である。

ただし、λは第２正則化項に対する重みであり、ｄｉａｇ（ｘ）はベクトルｘを対角成分にもつ対角行列を返す演算子であり、Ｄｉａｇ（ｘ）は行列ｘの対角成分を抜き出してベクトルとする演算子であり、第１正則化項はデータ集合の行列の転置とデータ集合の行列の積により計算される行列に対して、行列の対角成分を抜き出してベクトルとする演算子Ｄｉａｇ（ｘ）を適用した結果に対して、ベクトルを対角成分にもつ対角行列を返す演算子ｄｉａｇ（ｘ）を適用した結果を用いて表される。ＣはＣ＝Ｒ^Ｎ×Ｎ又はＣ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ、Ｚ_ｉｉ＝０｝とし、ｈ（・）は、以下のＬｐノルムのｑ乗とする。

ｐとｑは何らかの正の数である。

また、第２正則化項のｒ（Ｚ）には様々なものを用いることができる。例えば何も用いないこと、つまりｒ（Ｚ）＝０や、フロベニウスノルムｒ（Ｚ）＝｜｜Ｚ｜｜_Ｆ、フロベニウスノルムの二乗ｒ（Ｚ）＝｜｜Ｚ｜｜^２ _Ｆ、又はＬ１ノルムｒ（Ｚ）＝｜｜Ｚ｜｜_１を用いることなどが考えられる。

類似度計算部３２は、自己表現行列算出部３０で算出された自己表現行列Ｚで定義される類似度行列Ｍを計算する。例えばＭ_ｉｊ＝｜Ｚ_ｉｊ｜＋｜Ｚ_ｊｉ｜としてＭを定義するといった方法などを用いることができる。

クラスタリング部３４は、類似度計算部３２で計算された類似度行列Ｍに基づいてデータ集合をクラスタリングしたクラスタリング結果を得る。クラスタリング手法には、例えばスペクトラルクラスタリングを用いることや最大カット法を用いることができる。

＜本発明の実施の形態に係るクラスタリング装置の作用＞

次に、本発明の実施の形態に係るクラスタリング装置１００の作用について説明する。入力部１０において処理の対象とするデータ集合を受け付けると、クラスタリング装置１００は、図７に示すクラスタリング処理ルーチンを実行する。

まず、ステップＳ１００では、受け付けたデータ集合について、予め定められた行列集合Ｃのうち、上記（６）式の目的関数を最小化するような自己表現行列を算出する。上記（６）式によって表される目的関数は、行列集合Ｃに含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列Ｚを求めるための目的関数である。目的関数は次の各項によって表される。ｈ（Ｘ－ＸＺ）は、データ集合における各データを要素とするデータ行列Ｘのデータの各点と、自己表現行列Ｚを用いた各点の線形結合で表現されたデータの各点との残差を求める項である。｜｜Ｄｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５Ｚ｜｜^２ _Ｆは、自己表現行列Ｚにおいて、ユークリッドノルムの大きなデータの各点の線形重みを小さくするための第１正則化項である。第１正則化項には、所定の重みβをかける。ｒ（Ｚ）は、自己表現行列に関する第２正則化項である。

次に、ステップＳ１０２では、ステップＳ１００で算出された自己表現行列Ｚで定義される類似度行列Ｍを計算する。

ステップＳ１０４では、ステップＳ１０２で計算された類似度行列Ｍに基づいてデータ集合をクラスタリングしたクラスタリング結果を得て出力部５０に出力し、処理を終了する。

以上説明したように、本発明の実施の形態に係るクラスタリング装置によれば、予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、データ集合におけるデータの各点と、自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みβをかけた、自己表現行列においてユークリッドノルムの大きなデータの各点の線形重みを小さくするための第１正則化項と、自己表現行列に関する第２正則化項とによって表される上記（６）式の目的関数を最小化するような自己表現行列を算出し、算出された自己表現行列で定義される類似度行列を計算し、類似度行列に基づいてデータ集合をクラスタリングしたクラスタリング結果を得ることにより、ノイズの影響を抑えた自己表現行列を用いて、クラスタリングをすることができる。

［実験例の検証］

実施の形態の提案手法における正則化項｜｜Ｄｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５Ｚ｜｜^２ _Ｆはｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆとした場合においてランダムサンプリングを適用することにより導出されたものである。そのため、この正則化項はノイズに対する頑健性を有していると予想できる。また、既存研究で用いられている正則化項｜｜Ｚ｜｜^２ _Ｆと比較すると正則化項｜｜Ｄｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５Ｚ｜｜^２ _ＦはＺにＤｉａｇ（ｄｉａｇ（Ｘ^ＴＸ））^０．５による重み付けがなされており、この結果ユークリッドノルムの大きいデータ点が自己表現行列に大きすぎる影響を及ぼすことを防ぐ効果があることも期待される。

また、特定の場合において高速計算が可能である。特に、「ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ、ｒ（Ｚ）＝０、Ｃ＝Ｒ^Ｎ×Ｎ」とした場合、「ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ、ｒ（Ｚ）＝０、Ｃ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ，Ｚ_ｉｉ＝０｝」とした場合、「ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ、ｒ（Ｚ）＝｜｜Ｚ｜｜^２ _Ｆ、Ｃ＝Ｒ^Ｎ×Ｎ」とした場合、又は「ｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ、ｒ（Ｚ）＝｜｜Ｚ｜｜^２ _Ｆ、Ｃ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ，Ｚ_ｉｉ＝０｝」とした場合に関してはＺに閉じた解が存在し、Ｚを高速に計算することができる。

以下、本手法が実験的に優れた効果を有していることを示す実験例を述べる。

本手法の有効性を部分空間クラスタリング研究においてよく用いられる実世界データセットであるＣＯＩＬ１００、ＭＮＩＳＴ－ＲＢを用いたクラスタリング実験を通じて実証する．ＣＯＩＬ１００はそれぞれ７２枚の画像からなる１００種のカテゴリについての３２ｘ３２の画像データセットである。ＭＮＩＳＴ－ＲＢは０から９までの２８×２８の手書き数字データセットであるＭＮＩＳＴの背景にＲａｎｄｏｍにノイズを加えたデータセットである。公平性のためＣＯＩＬ１００、ＭＮＩＳＴ－ＲＢそれぞれのうち半分をパラメータ調整のためのＶａｌｉｄａｔｉｏｎ用、もう半分をＴｅｓｔ用に用いることとした。ＣＯＩＬ１００ではＶａｌｉｄａｔｉｏｎ／Ｔｅｓｔ用のスプリットでそれぞれランダムに１０クラスを選ぶことを２０回繰り返して２０セットの評価セットを作って用いた。ＭＮＩＳＴ－ＲＢではＶａｌ／Ｔｅｓｔ用のスプリットでそれぞれランダムに１００個ずつのデータを数字ごとに選択することを２０回繰り返して２０セットの評価セットを作って用いた。また、評価指標としては次の式に記載されたＡｃｃｕｒａｃｙを用いる。

Ａｃｃｕｒａｃｙ＝（正しくクラスタリングされた点の数）／（全体の点の数）、とした。

行列Ｚを計算する場合にｈ（Ｘ－ＸＺ）＝｜｜Ｘ－ＸＺ｜｜^２ _Ｆ，Ｃ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ，Ｚ_ｉｉ＝０｝，ｒ（Ｚ）＝０とした場合の結果を次の表１に示す。従来法より本手法が高い精度が出ていることがわかる。

なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

１０ 入力部
２０ 演算部
３０ 自己表現行列算出部
３２ 類似度計算部
３４ クラスタリング部
５０ 出力部
１００ クラスタリング装置

Claims (7)

1. 予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、
   前記データ集合におけるデータの各点と、前記自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みをかけた、前記自己表現行列においてユークリッドノルムの大きな前記データの各点の線形重みを小さくするための第１正則化項と、前記自己表現行列に関する第２正則化項とによって表される目的関数を最小化するような前記自己表現行列を算出する自己表現行列算出部と、
   算出された前記自己表現行列で定義される類似度行列を計算する類似度計算部と、
   前記類似度行列に基づいて前記データ集合をクラスタリングしたクラスタリング結果を得るクラスタリング部と、
   を含むクラスタリング装置。
2. 前記第１正則化項は、データ集合の行列の転置とデータ集合の行列の積により計算される行列に対して、行列の対角成分を抜き出してベクトルとする演算子を適用した結果に対して、ベクトルを対角成分にもつ対角行列を返す演算子を適用した結果を用いて表される請求項１に記載のクラスタリング装置。
3. 前記自己表現行列算出部は、予め定められた行列集合Ｃのうち、以下（１）式の前記目的関数を最小化するような前記自己表現行列を算出する請求項１又は請求項２に記載のクラスタリング装置。
   

   

   
   ・・・（１）
   ただし、Ｘは前記データ集合の各データを要素とするデータ行列、Ｚは前記自己表現行列、βは前記第１正則化項に対する所定の重み、ｒ（Ｚ）は前記第２正則化項、λは前記第２正則化項に対する重みであり、ｄｉａｇ（ｘ）はベクトルｘを対角成分にもつ対角行列を返す演算子であり、Ｄｉａｇ（ｘ）は行列ｘの対角成分を抜き出してベクトルとする演算子であり、ＣはＣ＝Ｒ^Ｎ×Ｎ又はＣ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ、Ｚ_ｉｉ＝０｝とし、ｈ（・）は、Ｌｐノルムのｑ乗とし、ｐとｑは何らかの正の数とする。
4. 自己表現行列算出部が、予め定められた行列集合に含まれる行列のうち、データ集合におけるデータの各点を、各点の線形結合で表現する際の線形重みを要素とする自己表現行列を求めるための目的関数であって、
   前記データ集合におけるデータの各点と、前記自己表現行列を用いた各点の線形結合で表現されたデータの各点との残差を求める項と、所定の重みをかけた、前記自己表現行列においてユークリッドノルムの大きな前記データの各点の線形重みを小さくするための第１正則化項と、前記自己表現行列に関する第２正則化項とによって表される目的関数を最小化するような前記自己表現行列を算出するステップと、
   類似度計算部が、算出された前記自己表現行列で定義される類似度行列を計算するステップと、
   クラスタリング部が、前記類似度行列に基づいて前記データ集合をクラスタリングしたクラスタリング結果を得るステップと、
   を含むクラスタリング方法。
5. 前記第１正則化項は、データ集合の行列の転置とデータ集合の行列の積により計算される行列に対して、行列の対角成分を抜き出してベクトルとする演算子を適用した結果に対して、ベクトルを対角成分にもつ対角行列を返す演算子を適用した結果を用いて表される請求項４に記載のクラスタリング方法。
6. 前記自己表現行列算出部は、予め定められた行列集合Ｃのうち、以下（１）式の前記目的関数を最小化するような前記自己表現行列を算出する請求項４又は請求項５に記載のクラスタリング方法。
   

   

   
   ・・・（２）
   ただし、Ｘは前記データ集合の各データを要素とするデータ行列、Ｚは前記自己表現行列、βは前記第１正則化項に対する所定の重み、ｒ（Ｚ）は前記第２正則化項、λは前記第２正則化項に対する重みであり、ｄｉａｇ（ｘ）はベクトルｘを対角成分にもつ対角行列を返す演算子であり、Ｄｉａｇ（ｘ）は行列ｘの対角成分を抜き出してベクトルとする演算子であり、ＣはＣ＝Ｒ^Ｎ×Ｎ又はＣ＝｛Ｚ｜Ｚ∈Ｒ^Ｎ×Ｎ、Ｚ_ｉｉ＝０｝とし、ｈ（・）は、Ｌｐノルムのｑ乗とし、ｐとｑは何らかの正の数とする。
7. コンピュータを、請求項１～請求項３のいずれか１項に記載のクラスタリング装置の各部として機能させるためのプログラム。

Images