データクラスタリング装置及び方法
【課題】より精度の良いクラスタリング結果を得ることができるようにする。
【解決手段】実施形態によれば、データクラスタリング装置において解析手段は、複数の要素から構成されるデータユニットの集合を含むデータセットに基づき、当該複数の要素を複数の要素グループに区分し、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元の特徴行列を生成する。結合手段は、特徴行列の同一次元の２つの特徴ベクトルの組み合わせのうち、２つの特徴ベクトルの間の結合指数が第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて特徴行列及び分類結果表を更新する処理を、更新後の特徴行列が第２の条件を満たすまで繰り返す。出力手段は、この繰り返しの後の分類結果表に基づいて、データセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する。
【解決手段】実施形態によれば、データクラスタリング装置において解析手段は、複数の要素から構成されるデータユニットの集合を含むデータセットに基づき、当該複数の要素を複数の要素グループに区分し、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元の特徴行列を生成する。結合手段は、特徴行列の同一次元の２つの特徴ベクトルの組み合わせのうち、２つの特徴ベクトルの間の結合指数が第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて特徴行列及び分類結果表を更新する処理を、更新後の特徴行列が第２の条件を満たすまで繰り返す。出力手段は、この繰り返しの後の分類結果表に基づいて、データセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、データクラスタリング装置及び方法に関する。
【背景技術】
【０００２】
従来から、例えばデータ共有サーバのような計算機において、ユーザがどのような操作をしたかの履歴を示すデータを保管し、このデータを解析し、各ユーザの不正な操作や異常な操作、操作の全体的な傾向などを、機械学習などを行うことによって抽出する技術が知られている。このような技術を用いる際、入力するデータの種類（操作の種類や操作の対象の種類など）が多い場合、元のデータをそのまま利用し機械学習を行うには計算量が膨大になるため、現実的な時間で有益な結果を導き出すことは難しい。
【０００３】
そこで、学習データの多様性を減らすために、データをクラスタリングすることが知られている。クラスタリング手法としては、データから多次元ベクトルを構成し、各ベクトル間の距離を導出し、それに基づいて例えばｋ平均法（ｋ−ｍｅａｎｓ法）などによりクラスタリングする方法が一般的である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−２２９３６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のクラスタリング手法では、そもそも多次元ベクトルとして構成する際、ベクトルの次元数や成分の取り方によって結果が大きく左右されるにも拘わらず、次元数や成分の取り方はクラスタリングとは直接関係の無い決め方がなされている。また、データのどの要素を特徴ベクトルの要素として採用するか否かを事前に設定しておく必要があり、データ全体を見て重要でないデータを削ぎ落としたり、似たような特徴のデータを統合したりするという作業はクラスタリングとは別に前処理として実施する必要がある。
【０００６】
そのため、前処理の実施方法が自明でない場合や前処理結果の評価が難しい場合、前処理をどのように実施するかを決定するのも難しくなる。
そこで、従来技術において前処理として切り離されていた、入力データを多次元ベクトルとして抽象化するような処理も総合的に考慮したクラスタリング手法が要求される。
【０００７】
本発明が解決しようとする課題は、複数の要素を持つデータユニットの集合を、特定の１要素ではなく、複数の要素を複合的に考慮してクラスタリングすることで、より精度の良いクラスタリング結果を得ることができるデータクラスタリング装置及び方法を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、データクラスタリング装置は、入力手段と、解析手段と、記憶手段と、判定手段と、結合手段と、出力手段とを具備する。入力手段は、複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力する。解析手段は、前記入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成する。記憶手段は、前記入力されたデータセット、前記多次元特徴行列、及び前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を格納する。判定手段は、前記多次元特徴行列の前記１つ以上の次元を対象に、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行する。結合手段は、前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行する。前記判定手段及び前記結合手段は、前記更新後の多次元特徴行列が第２の条件を満たすまで、それぞれ前記判定処理及び前記結合処理を繰り返す。前記出力手段は、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態に係るクラスタリングユニットを備えたデータ処理システムの構成を示すブロック図。
【図２】第１の実施形態においてクラスタリングの対象となるデータセットの一例を示す図。
【図３】図２に示されるデータセットに基づいて生成される特徴行列の一例を示す図。
【図４】第１の実施形態においてクラスタリング処理の過程で生成される分類結果表の一例を示す図。
【図５】第１の実施形態において結合部から出力部に渡される分類結果表の一例を示す図。
【図６】第１の実施形態におけるクラスタリング結果の一例を示す図。
【図７】第１の実施形態における上記クラスタリング処理の手順を示すフローチャート。
【図８】第１の実施形態における１回目の特徴ベクトル結合後の特徴行列を示す図。
【図９】第１の実施形態における１回目の特徴ベクトル結合前後の分類結果表を示す図。
【図１０】第１の実施形態における２回目の特徴ベクトル結合後の特徴行列を示す図。
【図１１】第１の実施形態における３回目の特徴ベクトル結合後の特徴行列を示す図。
【図１２】第２の実施形態における一連の特徴ベクトル結合完了後の分類結果表の一例を示す図。
【図１３】第２の実施形態におけるクラスタリング結果の一例を示す図。
【図１４】第３の実施形態における圧縮完了後の行の分類結果表及び列の分類結果表の一例を示す図。
【図１５】第３実施形態におけるクラスタリング結果の一例を示す図。
【図１６】図１４の行の分類結果表及び列の分類結果表で示される、第１の要素が結合された行及び第２の要素が結合された列の組み合わせとクラスを示す記号との関係を示す図。
【図１７】第４の実施形態においてクラスタリングの対象となるデータセットに基づいて生成される行圧縮特徴行列及び列圧縮特徴行列の例を示す図。
【図１８】第４の実施形態における１回目の圧縮完了後の行圧縮特徴行列を示す図。
【図１９】第４の実施形態における１回目の圧縮完了後の行の分類結果表を示す図。
【図２０】第４の実施形態における２回目の圧縮完了後の列圧縮特徴行列を示す図。
【図２１】第４の実施形態における２回目の圧縮完了後の列の分類結果表を示す図。
【図２２】第４の実施形態における３回目の圧縮完了後の行圧縮特徴行列を示す図。
【図２３】第４の実施形態における３回目の圧縮完了後の行の分類結果表を示す図。
【図２４】第４の実施形態におけるクラスタリング結果の一例を示す図。
【発明を実施するための形態】
【００１０】
以下、実施の形態につき図面を参照して説明する。
［第１の実施形態］
図１は第１の実施形態に係るクラスタリングユニットを備えたデータ処理システムの構成を示すブロック図である。
図１において、データ処理システム１０は、データ保管部１１及びクラスタリングユニット１２を備えている。データ処理システム１０は、例えばデータ共有サーバ計算機のような単一の計算機により構成されている。
【００１１】
データ保管部１１は、ユーザがどのような操作をしたかの履歴を示すデータ（操作履歴データ）を保管する。この操作履歴データは、例えば、データ処理システム１０を構成する計算機へのユーザの操作によるアクセスのログであり、図示せぬ手段によってデータ保管部１１に予め保存されているものとする。データ保管部１１は、例えばデータ処理システム１０を構成する計算機が有する、ディスク装置のような不揮発性記憶装置に置かれる。
【００１２】
クラスタリングユニット１２は、データクラスタリング装置として機能して、データ保管部１１に格納されているデータから特定の特徴を持ったデータセットを抽出する。即ちクラスタリングユニット１２は、データ保管部１１からクラスタリングの対象データを受け取り、受け取った対象データをある指定された数のクラスに分類する。
【００１３】
クラスタリングユニット１２は、入力部１２１、入力データ解析部１２２、判定部１２３、結合部１２４及び出力部１２５の各機能要素と、ワーキングメモリ１２６とを備えている。入力部１２１、入力データ解析部１２２、判定部１２３、結合部１２４及び出力部１２５は、データ処理システム１０を構成する計算機が、例えば、ディスク装置のような不揮発性記憶装置に格納されているプログラムを読み込んで実行することにより実現されるものとする。このプログラムが、外部の計算機から例えばネットワークを介してダウンロードされたものであっても構わない。このプログラムは、クラスタリングの対象となるデータから、ある特定の特徴を持つデータを識別する機能を持つ。
【００１４】
入力部１２１は、例えばデータ保管部１１から、クラスタリングの対象となるデータセットを受け取り、当該受け取ったデータセットを入力データ解析部１２２に渡す。第１の実施形態においてデータ保管部１１に格納されているデータは、前述したように、データ処理システム１０を構成する計算機へのユーザの操作によるアクセスのログであり、例えば、当該計算機内の同一機器または当該計算機内の同一プログラムに存在するデータである。しかし、データ保管部１１に格納されているデータが、外部の計算機内の機器や当該外部の計算機内のプログラムに存在するデータであっても構わない。また、外部の計算機の機器やプログラムから入力部１２１がデータを受け取っても構わない。
【００１５】
図２は、入力部１２１が受け取る、クラスタリングの対象となるデータセットの一例を示す。図２の例では、データセットは、２つの文字列の組を持つデータユニットの集合である。２つの文字列はそれぞれ異なる集合の要素である。図２の例において、データユニット内の一方の文字列である第１の要素（データ１）は英文中に出現する動詞であり、他方の文字列である第２の要素（データ２）は当該英文中に出現する名詞である。
【００１６】
再び図１を参照すると、入力データ解析部１２２は、入力部１２１が受け取ったデータセット（つまり入力データ）を解析し、上記２つの文字列のうち第１の要素（データ１）を縦軸（縦方向の次元、つまり行の次元）の要素（行要素）ｉ、第２の要素（データ２）を横軸（横方向の次元、つまり列の次元）の要素（列要素）ｊとし、出現回数を行列の要素（成分）ａijとする２次元の行列（以下、特徴行列と称する）を生成する。
【００１７】
図３は、図２に示されるデータセットに基づいて入力データ解析部１２２によって生成された特徴行列の一例を示す。図３に示す特徴行列の例えば第３（ｒｅａｄ）行、第２（ｂｏｏｋ）列の要素ａ32（値）は６である。この「６」は、「“ｒｅａｄ”，“ｂｏｏｋ”」という文字列を持つデータユニットが、入力されたデータセット内に６回出現していたということを意味する。入力データ解析部１２２は、生成した特徴行列をワーキングメモリ１２６に格納する。
【００１８】
なお、入力データ解析部１２２による入力データ（入力されたデータセット）の解析手法は、上述の例のみならず、各種方法が考えられる。入力データが、２つの文字列（要素）の組を持つデータユニットの集合の場合、結果としてクラスタリング対象の２要素の一方を行要素とし、他方を列要素とする、当該行要素及び列要素の組み合わせの特徴を表現する行列が構成されればよい。また、２要素が、動詞と名詞である必要はない。
【００１９】
判定部１２３は、ワーキングメモリ１２６から特徴行列を読み出し、当該特徴行列の任意の２つの行の要素（成分）の集合（以下、特徴ベクトルと称する）毎に、その２つの特徴ベクトルの間の結合指数を計算する。判定部１２３はまた、特徴行列の任意の２つの列の要素（成分）の集合（特徴ベクトル）毎に、その２つの特徴ベクトルの間の結合指数を計算する。そして判定部１２３は、結合指数が最小の組み合わせとなる２つの特徴ベクトルを抽出する。結合指数は２つの特徴ベクトルの相違度と重要度に正の相関を持つ値である。図３において、例えば第１行、つまり行１（ｉ＝１）の特徴ベクトル（行特徴ベクトル）は、（１，１，４）で表される。また、例えば第１列、つまり列１（ｊ＝１）の特徴ベクトル（列特徴ベクトル）は、（１，２，０，３）で表される。
【００２０】
相違度は特徴ベクトル同士の方向の違いの大きさを表す値であり、方向が異なるほど大きな値を示す。相違度として、例えば２つの特徴ベクトルのなす角度の大きさをθとした場合のｓｉｎθなどを用いることが考えられる。重要度は特徴ベクトルを構成する各要素が当該特徴ベクトルの他の要素と比較して、どのくらい特徴的な値であるか、各要素がどのくらい大きいかを表す値である。重要度は、特徴的であるほど大きな値を示し、各要素の値が大きいほど大きな値を示す。重要度として、例えば特徴ベクトルの絶対値（特徴ベクトルの長さ）を用いてもよい。この場合、例えば２つの特徴ベクトルの各々の重要度（絶対値）の積と前記２つの特徴ベクトルの前記相異度との積を結合指数として用いてもよい。
【００２１】
第１の実施形態では、結合指数として、２つの特徴ベクトルの外積の絶対値が用いられる。ここでは、特徴ベクトルａと特徴ベクトルｂの外積の絶対値の２乗が、｜ａ｜２｜ｂ｜２−（ａ・ｂ）２と定義される（ａ・ｂはａとｂの内積）。この場合、２つの特徴ベクトルａ及びｂの長さが小さく（つまり重要度が低く）、なす角度が小さい（つまり相違度が低い）ほど、結合指数が小さくなる。判定部１２３は、抽出した２つの特徴ベクトルのデータを結合部１２４に送る。
【００２２】
結合部１２４は、判定部１２３から受け取った２つの特徴ベクトルを結合し、１つのベクトルとして、ワーキングメモリ１２６に格納されている特徴行列を更新する。結合の方法としては例えば、２つの特徴ベクトルの各成分の和をそれぞれ新しいベクトルの成分とする方法などが考えられる。また結合部１２４は、結合の際、受け取った２つの特徴ベクトルが新しく生成されたベクトルのクラスに分類されたものとして分類結果表を更新する。分類結果表は、ワーキングメモリ１２６に格納して用いられるものとする。第１の実施形態では結合部１２４は、行の特徴ベクトルが結合された場合にのみ分類結果表を更新する。
【００２３】
図４は、分類結果表の一例を示す。第１の実施形態において、分類結果表は、行の各特徴ベクトルをクラスとして保持する。判定部１２３は、更新の際は結合した行をどちらかのクラスに統合する操作を行う。図４に示される分類結果表において、クラスの表記には、行要素の値が用いられている。しかし、クラスの表記は、行要素と直接関連する必要はない。例えば、図４に示すクラス１（ｒｉｄｅ）、クラス２（ｄｏ）、クラス３（ｒｅａｄ）を、それぞれ、単にクラスＡ、クラスＢ、クラスＣのような記号で表記しても良い。
【００２４】
結合部１２４は判定部１２３と協働して上述のような操作を繰り返す。結合部１２４は、この繰り返しの結果、特徴行列に残されている例えば行の特徴ベクトルの数が予め指定された数（クラスの数）まで減少した時点で、当該繰り返しを終了して、ワーキングメモリ１２６を介して分類結果表を出力部１２５に渡す。なお、特徴行列に残されている行及び列の両方の特徴ベクトルの数が予め指定された数まで減少した時点で、上述の繰り返しを終了しても構わない。
【００２５】
図５は、出力部１２５に渡される分類結果表の一例を示す。なお、図４は、上述の操作の繰り返しの途中の分類結果表（より詳細には、１回目の２つの行の特徴ベクトルの結合後の分類結果表）の一例を示したものである。
【００２６】
出力部１２５は、ワーキングメモリ１２６を介して結合部１２４から分類結果表を受け取ると、当該分類結果表と入力データセットとに基づき、データユニット毎にクラス分けをした結果（クラスタリング結果）を出力データとして出力する。
【００２７】
図６は出力データの一例を示す。図６に示す出力データは、入力データセットのデータユニット毎にそのデータユニットがどのクラスに属するかを記述した表形式のクラスタリング結果を示す。図６の出力データ（クラスタリング結果）において、クラスＡは図５におけるクラス１に、クラスＢは図５におけるクラス３に、それぞれ対応する。他にも入力データセットの種類毎にその種類のがどのクラスに属するかを出力データとする方法などが適用可能である。
【００２８】
第１の実施形態において上述のように特徴行列を生成した場合、当該特徴行列で示される各特徴ベクトルの絶対値（特徴ベクトルの長さ）は、対応する行または列の要素のデータとしての重要度を表している。また、特徴ベクトル同士のなす角度をθとした場合のｓｉｎθは、θが大きくなればなるほど大きくなり、特徴ベクトルの相異度（どのくらい異なるかの度合い）を表す。つまり、結合指数が小さい２つの特徴ベクトルを結合（統合）するということは、特徴行列を構成する特徴ベクトルとして重要度が低いものを、他の重要度が低く、似ている特徴ベクトル（ベクトルの方向が似ている特徴ベクトル）に統合することを意味する。
【００２９】
このように統合を行うことで、全体の特徴を失うことなく、全体の特徴とはあまり関係の無いデータをできるだけ影響が小さい形で統合することができる。つまり、このような「結合指数」を用いて統合を繰り返した結果、全体の特徴は失わず、重要でないデータはできるだけ似たもの同士統合したクラスタリング結果を得ることができる。
【００３０】
第１の実施形態によれば、予め定められたルールに基づいて多次元ベクトルを構成した後にクラスタリングを行う方法に比べ、特定の１要素ではなく、複数の要素を複合的に考慮して、つまり多次元ベクトルの各成分の類似度（相違度）や距離などを考慮した上で多次元ベクトルを構成することができ、より精度の良いクラスタリング結果を得ることができる。また、出現頻度の低い重要でないデータを削ぎ落としつつ、似た特徴を有するデータは統合し、他とは異なる特徴を持つデータを残したクラスタリング結果を得ることができる。
【００３１】
次に、第１の実施形態におけるクラスタリングユニット１２の動作の概要について説明する。
まず、クラスタリングユニット１２は、データ保管部１１から、例えば図２に示したようなクラスタリングの対象データを受け取り、当該対象データに対してクラスタリング処理を行う。このクラスタリング処理において、クラスタリングユニット１２の出力部１２５は、図５に示したような分類結果表と図２に示したようなクラスタリングの対象データ（入力データセット）とに基づき、データセット毎にクラス分けをした結果を出力データとして出力する。
【００３２】
次に、第１の実施形態における上記クラスタリング処理の手順について、図７のフローチャートを参照して説明する。
まず入力部１２１は、データ保管部１１から図２に示したようなクラスタリングの対象となるデータ（データセット）を受信する（ステップＳ１１）。入力部１２１が受信したデータは入力データ解析部１２２に渡される。
【００３３】
入力データ解析部１２２は、入力部１２１が受信したデータを当該入力部１２１から受け取ると、当該受信データ（入力データ）を解析することにより、図３に示したような特徴行列を生成する（ステップＳ１２）。このステップＳ１２において、入力データ解析部１２２は、生成された特徴行列に基づいて、当該特徴行列の行及び列の少なくとも一方、例えば行の各特徴ベクトルをクラスとして保持する分類結果表も生成する。生成された特徴行列及び分類結果表は、入力データと共に、ワーキングメモリ１２６に格納される。
【００３４】
判定部１２３は、入力データ解析部１２２によって生成された特徴行列の行及び列の少なくとも一方、例えば行及び列の両方を対象に、当該特徴行列から２つの特徴ベクトルの組み合わせを全て抽出する（ステップＳ１３）。即ち判定部１２３は、特徴行列の行を対象に、当該特徴行列から２つの行の特徴ベクトルの組み合わせを全て抽出する。また判定部１２３は、特徴行列の列を対象に、当該特徴行列から２つの列の特徴ベクトルの組み合わせを全て抽出する。
【００３５】
判定部１２３は、抽出された行及び列のそれぞれの２つの特徴ベクトルの組み合わせ毎に、その２つの特徴ベクトルの間の結合指数を計算する（ステップＳ１４）。そして判定部１２３は、計算した結合指数が第１の条件に合致する組み合わせの特徴ベクトル、例えば計算した結合指数が最も小さい組み合わせの特徴ベクトルを抽出する（ステップＳ１５）。
【００３６】
結合部１２４は、判定部１２３によって抽出された、結合指数が最も小さい組み合わせの特徴ベクトルを結合する（ステップＳ１６）。結合部１２４は、この特徴ベクトル結合結果に基づいて、特徴行列及び分類結果表を更新する（ステップＳ１７）。
【００３７】
上述のステップＳ１３〜Ｓ１７は、更新後の特徴行列が第２の条件を満たすまで、例えば更新後の特徴行列に残っている行の特徴ベクトルの数が、予め指定された数（ここでは、ユーザによって指定された数）に達するまで（ステップＳ１８）、繰り返される。そして、残っている行の特徴ベクトルの数が指定数に達すると、出力部１２５は、図６に示したようなクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００３８】
＜第１の実施形態の具体例＞
次に第１の実施形態における上述した図７のフローチャートに従う動作の流れを、図２乃至図６に加えて、図８乃至図１１を参照して、具体例を挙げて説明する。
以下の例では、特徴行列の２つの行の特徴ベクトルの全ての組み合わせ及び当該特徴行列の２つの列の特徴ベクトルの全ての組み合わせのうち、最小の結合指数を持つ組み合わせの特徴ベクトルを結合するものとする。結合の終了は行の特徴ベクトルの数が２となったタイミングとする。また、分類結果表は行の特徴ベクトルの圧縮が起こった際のみ更新され、結合指数にはベクトルの外積の絶対値が用いられるものとする。
【００３９】
まず、入力部１２１が、図２に示したような入力データ（データセット）をクラスタリング対象データとして受信したものとする（ステップＳ１１）。入力部１２１によって受信された入力データは入力データ解析部１２２に渡される。入力データ解析部１２２は、入力部１２１から渡された入力データを一旦ワーキングメモリ１２６に格納し、当該ワーキングメモリ１２６に格納された入力データ（図２参照）に基づいて、図３に示したような特徴行列（つまりクラスタリング開始時の特徴行列）を生成する（ステップＳ１２）。ここでは入力データ解析部１２２は、図２に示す入力データの第１要素（データ１）を行要素、第２要素（データ２）を列要素とし、当該入力データを構成するデータユニット毎に、そのデータユニットの第１要素及び第２要素がそれぞれ割り当てられる行要素ｉ及び列要素ｊに対応する、特徴行列の要素（成分）ａijをインクリメントすることにより、当該特徴行列（図３参照）を生成する。生成された特徴行列はワーキングメモリ１２６に格納される。
【００４０】
上記ステップＳ１２において入力データ解析部１２２は、図３に示す特徴行列に基づき、当該特徴行列の例えば行の各特徴ベクトルをクラスとして保持する分類結果表（図９（ａ）参照）も生成する。生成された分類結果表はワーキングメモリ１２６に格納される。
【００４１】
次に判定部１２３は、生成された特徴行列から、２つの行の特徴ベクトルの組み合わせ及び２つの列の特徴ベクトルの組み合わせを全て抽出し（ステップＳ１３）、それぞれの組み合わせ（２つの特徴ベクトルの間）の結合指数として、それぞれの組み合わせの外積の絶対値を計算する（ステップＳ１４）。図３の例における、行及び列それぞれの特徴ベクトルの組み合わせの外積の絶対値の２乗は、次のようになる。
【００４２】
（１）行の特徴ベクトルの組み合わせ
行１−行２：９８
行１−行３：５６６
行１−行４：２５１
行２−行３：１６４
行２−行４：１７
行３−行４：５２９
（２）列の特徴ベクトルの組み合わせ
列１−列２：５０９
列１−列３：１５３
列２−列３：９６３
このように第１の実施形態では結合指数として、便宜的に、外積の絶対値に代えて外積の絶対値の２乗が用いられる。ここで、外積の絶対値の２乗を用いても、結合指数が最小値となる組み合わせは同じである。
【００４３】
上記特徴ベクトルの組み合わせの外積（外積の２乗）のうち、最も小さい外積は１７であり、行２及び行４の特徴ベクトルの組み合わせの外積である。
【００４４】
この場合、結合部１２４は、行２及び行４の特徴ベクトルの組み合わせを、結合指数が最小の組み合わせとして抽出し（ステップＳ１５）、行２及び行４の特徴ベクトルを結合する（ステップ１６）。図３の例では、結合部１２４は、行２の特徴ベクトル（２，２，１）の各成文の値、、つまり行２の列毎の要素ａ2j（ｊ＝１，２，３）の値と、行４の特徴ベクトル（３，４，３）の各成文の値、つまり行４の列毎の要素ａ4j（ｊ＝１，２，３）の値とを加算することにより、行２及び行４の特徴ベクトルを結合する、この１回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（５，６，４）となる。
【００４５】
結合部１２４は、図３に示す特徴行列から、行２及び行４の特徴ベクトルを削除し、結合後の特徴ベクトル（５，６，４）を例えば行２の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図３に示す特徴行列から行４の特徴ベクトルを削除し、行２の特徴ベクトルを、結合後の特徴ベクトル（５，６，４）に更新する（ステップ１７）。これにより図３に示す特徴行列は、図８に示すように更新される。
【００４６】
結合部１２４による行２及び行４の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、行４の特徴ベクトル（３，４，３）の各成文の値を、行２の特徴ベクトル（２，２，１）の各成文の値に加算して、当該行４の特徴ベクトル（３，４，３）を削除することと等価である。
【００４７】
図８に示す特徴行列（つまり１回目の特徴ベクトル結合後の特徴行列）に残っている行の特徴ベクトルの数（つまり有効な行の数）は、図３に示す特徴行列と比較して、４から３に減少している。つまり特徴行列の行が圧縮されている。
【００４８】
第１の実施形態における具体例では、行のクラスタリングのみ行われる。したがって分類結果表は、特徴行列の行のみ、それらの行の特徴ベクトルそれぞれをクラスとして保持すればよい。そこで結合部１２４は、行の特徴ベクトルを結合した場合のみ分類結果表を更新する。つまり結合部１２４は、上述の例のように行４の特徴ベクトルを行２の特徴ベクトルに結合した場合、特徴行列だけでなく、ワーキングメモリ１２６に格納されている分類結果表も更新する（ステップＳ１７）。
【００４９】
図９は、１回目の特徴ベクトル結合前後の分類結果表を示す。つまり分類結果表は、１回目の特徴ベクトル結合後、図９（ａ）に示す状態から図９（ｂ）に示す状態に更新される。図９（ａ）に示す分類結果表、即ち１回目の特徴ベクトル結合前の分類結果表（クラスタリング開始時の分類結果表）のクラスは、１回目の特徴ベクトル結合前の特徴行列の全ての行の特徴ベクトル（行要素）、即ち行１〜３の要素（各データユニットの第１の要素）に対応する。ここでは、分類結果表は、クラスと、そのクラスに分類される行の特徴ベクトル（行要素）が属する行とを対応付けて示す。図９（ｂ）に示す分類結果表は、図４に示した分類結果表に相当する。図９（ｂ）に示す分類結果表では、図９（ａ）に示す分類結果表との比較から明らかなように、クラス２に分類される行の特徴ベクトルが、１回目の特徴ベクトル結合結果である、行２及び行４の特徴ベクトルの結合を反映するように、行２の特徴ベクトルから、行２及び行４の特徴ベクトルの結合後の特徴ベクトルに更新されている。
【００５０】
判定部１２３は、結合部１２４によって分類結果表が更新されると、その際の特徴行列に残っている行の特徴ベクトルの数が、予め指定された数である「２」であるかを判定する（ステップＳ１８）。このとき特徴行列に残っている行の特徴ベクトルの数は、図８から明らかなように３であるため、ステップＳ１８の判定はＮｏとなる。
【００５１】
この場合、判定部１２３は、最新の特徴ベクトル結合（ここでは１回目の特徴ベクトル結合）後の特徴行列（図８参照）に基づいて、再び上記ステップＳ１３〜Ｓ１５を実行する。これにより判定部１２３は、その時点における特徴行列の行及び列それぞれの特徴ベクトルの全ての組み合わせから、結合指数が最小の特徴ベクトルの組み合わせを抽出する。詳細は省略するが、２回目のステップＳ１３〜Ｓ１５の実行では、判定部１２３は、列１及び列３の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝１５３）の組み合わせとして抽出する。
【００５２】
すると結合部１２４は、列１の特徴ベクトル（１，５，０）の各成文の値、つまり列１の行毎の要素ａi1（ｉ＝１，２，３）の値と、列３の特徴ベクトル（４，４，１）の各成文の値、つまり列３の行毎の要素ａi3（ｉ＝１，２，３）の値とを加算することにより、列１及び列３の特徴ベクトルを結合する（ステップＳ１６）。この２回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（５，９，１）となる。
【００５３】
結合部１２４は、図８に示す特徴行列から、列１及び列３の特徴ベクトルを削除し、結合後の特徴ベクトル（５，９，１）を例えば列１の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図８に示す特徴行列から列３の特徴ベクトルを削除し、列１の特徴ベクトルを、結合後の特徴ベクトル（５，９，１）に更新する（ステップ１７）。これにより図８に示す特徴行列は、図１０に示すように更新される。
【００５４】
結合部１２４による列１及び列３の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、列３の特徴ベクトル（４，４，１）の各成文の値を、列１の特徴ベクトル（１，５，０）の各成文の値に加算して、当該列３の特徴ベクトル（４，４，１）を削除することと等価である。
【００５５】
図１０に示す特徴行列（つまり２回目の特徴ベクトル結合後の特徴行列）に残っている列の特徴ベクトルの数（つまり有効な列の数）は、図８に示す特徴行列と比較して、３から２に減少している。つまり特徴行列の列が圧縮されている。
【００５６】
図１０に示す特徴行列の例では、特徴行列に残っている行の特徴ベクトルの数は、１回目の特徴ベクトル結合後と比較して変化しておらず、「３」のままである。この場合、２回目の特徴ベクトル結合後のステップＳ１８の判定はＮｏとなり、判定部１２３は、当該２回目の特徴ベクトル結合後の特徴行列（図１０参照）に基づいて、３回目のステップＳ１３〜Ｓ１５を実行する。詳細は省略するが、３回目のステップＳ１３〜Ｓ１５の実行では、判定部１２３は、行１及び行２の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝４４１）の組み合わせとして抽出する。
【００５７】
すると結合部１２４は、行１の特徴ベクトル（５，１）の各成文の値と行２の特徴ベクトル（９，６）の各成文の値とを加算することにより、行１及び行２の特徴ベクトルを結合する（ステップＳ１６）。この３回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（１４，７）となる。
【００５８】
結合部１２４は、図１０に示す特徴行列から、行１及び行２の特徴ベクトルを削除し、結合後の特徴ベクトル（１４，７）を例えば行１の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図１０に示す特徴行列から行２の特徴ベクトルを削除し、行１の特徴ベクトルを、結合後の特徴ベクトル（１４，７）に更新する（ステップ１７）。これにより図１０に示す特徴行列は、図１１に示すように更新される。
【００５９】
結合部１２４による行１及び行２の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、行２の特徴ベクトル（９，６）の各成文の値を、行１の特徴ベクトル（５，１）の各成文の値に加算して、当該行２の特徴ベクトル（９，６）を削除することと等価である。
図１１に示す特徴行列に残っている行の特徴ベクトルの数は、図１０に示す特徴行列と比較して、３から２に減少している。つまり特徴行列の行が圧縮されている。
【００６０】
結合部１２４は、行の特徴ベクトルを結合したことから、この特徴ベクトル結合結果に基づいて、特徴行列だけでなく分類結果表も更新する（ステップＳ１７）。
図５は、３回目の特徴ベクトル結合後の分類結果表を示したものである。つまり分類結果表は、３回目の特徴ベクトル結合後、図９（ｂ）に示す状態から図５に示す状態に更新される。図５に示す分類結果表では、図９（ｂ）に示す分類結果表との比較から明らかなように、クラス１に分類される行の特徴ベクトルが、３回目の特徴ベクトル結合結果である、行１及び行３の特徴ベクトルの結合を反映するように、行１の特徴ベクトルから、行１及び行３の特徴ベクトルの結合後の特徴ベクトルに更新されている。このとき、図１１に示す３回目の特徴ベクトル結合後の特徴行列に残っている行の特徴ベクトルの数は予め指定された数「２」に一致する（ステップＳ１８のＹｅｓ）。
【００６１】
すると出力部１２５は、図５に示す最終的な分類結果表及び図２に示す入力データに基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する（ステップＳ１９）。ここでは、出力部１２５は、入力データのデータユニット毎にそのデータユニットが、どのクラスに属するかを分類結果表に基づいて分類し、分類されたクラスを示すデータを対応するデータユニットに付加することで、クラスタリング結果を生成する。図６は、このときのクラスタリング結果（出力データ）の一例を示したものである。
【００６２】
なお、第１の実施形態では、分類結果表は、行の各特徴ベクトルをクラスとして保持し、行の特徴ベクトルが結合された場合にのみ更新される。しかし、分類結果表が、列の各特徴ベクトルをクラスとして保持し、列の特徴ベクトルが結合された場合にのみ更新される構成としても構わない。このような構成では、特徴行列に残されている、列の特徴ベクトルの数、または行及び列の両方の特徴ベクトルの数が予め指定された数（クラスの数）まで減少した時点で、判定処理及び結合処理の繰り返しを終了してもよい。
【００６３】
［第２の実施形態］
次に第２の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第２の実施形態に係るデータ処理システムの構成は、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００６４】
第２の実施形態の特徴は、第１の実施形態と異なって、特徴行列における行及び列それぞれの結合指数を単純に比較するのではなく、例えば、特徴行列の行の圧縮を優先させるとか、特徴行列の行の圧縮のみを行うことにある。そのため第２の実施形態では、判定部１２３から結合部１２４に渡される特徴ベクトルを当該判定部１２３が抽出するための抽出基準として、第１の実施形態のそれとは異なるものが適用される。
【００６５】
例えば、第１の実施形態では判定部１２３は、行及び列それぞれ任意の特徴ベクトル間の結合指数を計算し、結合指数が最小の組み合わせを抽出していた。これに対し、第２の実施形態では、判定部１２３が結合指数を計算する対象が、行または列のいずれか一方の特徴ベクトルに限定される。
【００６６】
＜第２の実施形態の具体例＞
以下、第２の実施形態の具体例について、図７のフローチャートを援用して説明する。但し第２の実施形態では、特徴行列の列の圧縮は行われず、行の圧縮のみ行われるものとする。ここで、入力データは第１の実施形態と同様であるとする（図２参照）。この場合、特徴行列の生成までの動作は第１の実施形態と同様であり、１回目の特徴ベクトル結合に関しても第１の実施形態と同様である（図８参照）。
【００６７】
２回目の特徴ベクトル結合では、判定部１２３は、行１及び行３の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝５６６）の組み合わせとして抽出する（ステップＳ１５）。すると、結合部１２４は、例えば行３の特徴ベクトル（０，６，１）の各成文の値を、行１の特徴ベクトル（１，１，４）の各成文の値に加算して、当該行３の特徴ベクトル（０，６，１）を削除する（ステップＳ１６，Ｓ１７）。この結果、２回目の特徴ベクトル結合後の新たな行１の特徴ベクトルは（１，７，５）となる。特徴ベクトル結合は２回目で完了し、その時点での分類結果表に基づいて、入力データのデータユニット毎にそのデータユニットが、どのクラスに属するかが決定される。
図１２は一連の特徴ベクトル結合完了後の分類結果表の一例を示し、図１３は図１２に示す分類結果表及び図２に示す入力データに基づくクラスタリング結果の一例を示す。図１３のクラスタリング結果において、クラスＡは図１２におけるクラス１に、クラスＢは図１２におけるクラス２に、それぞれ対応する。
【００６８】
第２の実施形態によれば、第１の要素（データ１）と第２の要素（データ２）を同列に扱うのが適当でない場合や、第２の要素が第１の要素の従属要素である場合などに、そのような実態を加味したクラスタリングを行うことが可能となる。
【００６９】
なお、第２の実施形態において、行または列のいずれか一方の結合指数を例えばユーザによって指定された重みで重み付けして、その重み付けされた結合指数（つまり結合指数と重みとの積）を、他方の結合指数と比較し、最小のものを抽出してもよい。
【００７０】
また、上記一方の結合指数及び上記他方の結合指数に、いずれを重要視するかに応じてそれぞれ異なる重みを付してもよい。つまり判定部１２３は、特徴行列の行及び列を対象に、当該特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、行の２つの特徴ベクトルの間の結合指数を、当該行に対応する第１の重みで重み付けし、列の２つの特徴ベクトルの間の結合指数を、当該列に対応する第２の重みで重み付けし、重み付け後の結合指数が最小の２つの特徴ベクトルを抽出するようにしてもよい。重みが１の場合、重み付けしないことと等価である。
また、ユーザによって指定された数、或いは予め指定された数に結合されるまでは、行または列のいずれか一方のみ抽出を行い、その後、他方の抽出を行うことも可能である。
【００７１】
［第３の実施形態］
次に第３の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第３の実施形態に係るデータ処理システムの構成も、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００７２】
第３の実施形態の特徴は、結合部１２４が行及び列双方の分類結果表を記録し、特徴行列のゼロ以外の成分の残数が、例えばユーザによって指定された、クラスタリングしたい数（以下、クラスタリング数と称する）以下になった時点で、クラスタリング結果が出力される点にある。この場合、特徴行列の各成分をクラスタリング結果のクラスとし、各データユニットは第１の要素が結合された行と第２の要素が結合された列の交点（組み合わせ）に対応するクラスに分類されたものとする。
【００７３】
＜第３の実施形態の具体例＞
以下、第３の実施形態の具体例について、クラスタリング数が４であるものとして説明する。入力データが第１及び第２の実施形態と同様であるとすると（図２参照）、第２の実施形態と同様の経過を辿り、３回目の特徴ベクトル結合（つまり圧縮）が完了した時点で、特徴行列の行数は２で列数は２となる。この特徴行列のゼロ以外の成分の残数は４であり、クラスタリング数４以下である。そこで、圧縮（結合）処理は終了する。
【００７４】
図１４は、圧縮完了の時点における行の分類結果表及び列の分類結果表を示すもので、同図（ａ）は行の分類結果表を、同図（ｂ）は列の分類結果表を、それぞれ示す。行の分類結果表は、図５に示した第１の実施形態における分類結果表と同様である。
【００７５】
出力部１２５は、図１４（ａ）に示す行の分類結果表、図１４（ｂ）に示す列の分類結果表及び入力データ（図８参照）に基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００７６】
図１５は図１４（ａ）及び（ｂ）の分類結果表で示される、第１の要素が結合された行及び第２の要素が結合された列の組み合わせとクラスを示す記号との関係を示し、図１６は第３の実施形態におけるクラスタリング結果の一例を示す。図１５から明らかなように、図１６のクラスタリング結果において、クラスＡは図１４（ａ）の分類結果表のクラス１及び図１４（ｂ）の分類結果表のクラス１の組み合わせに、クラスＢは図１４（ａ）の分類結果表のクラス１及び図１４（ｂ）の分類結果表のクラス２の組み合わせに、クラスＣは図１４（ａ）の分類結果表のクラス３及び図１４（ｂ）の分類結果表のクラス１の組み合わせに、そしてクラスＤは図１４（ａ）の分類結果表のクラス３及び図１４（ｂ）の分類結果表のクラス２の組み合わせに、それぞれ対応する。
【００７７】
第３の実施形態によれば、第１の要素と第２の要素をそれぞれ独立の要素とみなし、第１及び第２の要素をそれぞれ主要素とする観点から行ったクラスタリング結果を取得することができる。このため第３の実施形態は、第１及び第２の要素をそれぞれクラスタリングしたいが、それぞれの要素は他方の要素で特徴付けられるような場合のデータに対して有効である。
なお、第３の実施形態に、第２の実施形態を組み合わせてもよい。
【００７８】
［第４の実施形態］
次に第４の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第４の実施形態に係るデータ処理システムの構成も、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００７９】
第４の実施形態の第１の特徴は、行の圧縮を記録する行圧縮特徴行列と、列の圧縮を記録する列圧縮特徴行列とを保持し、行の特徴ベクトルの結合指数の計算には行圧縮特徴行列を用い、列の特徴ベクトルの結合指数の計算には列圧縮特徴行列を用いる点にある。
第４の実施形態の第２の特徴は、行の特徴ベクトルの結合を行圧縮特徴行列で行い、列の特徴ベクトルの結合を列圧縮特徴行列で行う点にある。
【００８０】
第４の実施形態の第３の特徴は、行の分類結果表と、列の分類結果表とを保持し、行の特徴ベクトルの結合（行圧縮特徴行列の更新）に応じて行の分類結果表を更新し、列の特徴ベクトルの結合（列圧縮特徴行列の更新）に応じて列の分類結果表を更新する点にある。
【００８１】
＜第４の実施形態の具体例＞
以下、第４の実施形態の具体例について説明する。ここでは、行圧縮特徴行列の行の数が２となった時点で圧縮（結合）が終了するものとする。また、結合指数として、第１の実施形態等と同様に、特徴ベクトル同士の外積の絶対値が用いられる。
【００８２】
入力データ（クラスタリング対象データセット）が第１の実施形態と同様であるとすると（図２参照）、入力データ解析部１２２は、当該入力データに基づいて行圧縮特徴行列及び列圧縮特徴行列を生成する。生成された行圧縮特徴行列及び列圧縮特徴行列は、図３に示す特徴行列と同様である。生成された行圧縮特徴行列及び列圧縮特徴行列を、それぞれ図１７（ａ）及び（ｂ）に示す。なお、第３の実施形態では、入力データに基づいて行圧縮特徴行列が生成され、この生成された行圧縮特徴行列の複製が列圧縮特徴行列として生成される（用いられる）。
【００８３】
１回目の圧縮は第１の実施形態と同様であり、図１７（ａ）に示す行圧縮特徴行列において、行４の特徴ベクトルを行２の特徴ベクトルに結合することにより、当該行圧縮特徴行列の行が圧縮される。図１８は、１回目の圧縮が完了した後の行圧縮特徴行列を示す。列圧縮特徴行列は変化しない。
１回目の圧縮が完了すると、結合部１２４は、行の分類結果表を更新する。図１９は、１回目の圧縮完了後の行の分類結果表を示す。この図１９に示す行の分類結果表は、図９（ｂ）に示す分類結果表と同様である。
【００８４】
２回目の圧縮も第１の実施形態と同様であり、図１７（ｂ）に示す列圧縮特徴行列において、列３の特徴ベクトルを列１の特徴ベクトルに結合することにより、当該列圧縮特徴行列の列が圧縮される。図２０は、２回目の圧縮が完了した後の列圧縮特徴行列を示す。行圧縮特徴行列は変化しない。
２回目の圧縮が完了すると、結合部１２４は、列の分類結果表を更新する。図２１は、２回目の圧縮完了後の列の分類結果表を示す。
【００８５】
３回目の圧縮では、図１８に示す行圧縮特徴行列において、行３の特徴ベクトルを行１の特徴ベクトルに結合することにより、当該行圧縮特徴行列の行が圧縮される。図２２は、３回目の圧縮が完了した後の行圧縮特徴行列を示す。列圧縮特徴行列は変化しない。
３回目の圧縮が完了すると、結合部１２４は、行の分類結果表を更新する。図２３は、３回目の圧縮完了後の行の分類結果表を示す。この図２３に示す行の分類結果表は、図１２に示す分類結果表と同様である。この時点で、図２２に示す行圧縮特徴行列から明らかなように、行の特徴ベクトルの残りが２つとなる。そこで結合部１２４は、一連の結合処理を終了する。
【００８６】
すると出力部１２５は、図２３に示す行の分類結果表、図２１に示す列の分類結果表及び入力データ（図２参照）に基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００８７】
図２４は第４の実施形態におけるクラスタリング結果の一例を示す。図２４のクラスタリング結果において、クラスＡは図２３の行の分類結果表のクラス１及び図２１の列の分類結果表のクラス１の組み合わせに、クラスＢは図２３の行の分類結果表のクラス１及び図２１の列の分類結果表のクラス２の組み合わせに、クラスＣは図２３の行の分類結果表のクラス２及び図２１の列の分類結果表のクラス１の組み合わせに、そしてクラスＤは図２３の行の分類結果表のクラス２及び図２１の列の分類結果表のクラス２の組み合わせに、それぞれ対応する。
【００８８】
第４の実施形態によれば、行の圧縮と列の圧縮とが、それぞれ行圧縮行列及び列圧縮行列上で行われるため、行の圧縮結果と列の圧縮結果とが互いに干渉するのを防止でき、行及び列それぞれを一定の基準で独立にクラスタリングした結果を取得できる。このため第４の実施形態は、例えば入力データの態様を重視したクラスタリングに有効である。
なお、第４の実施形態に、第２の実施形態及び／または第３の実施形態を組み合わせてもよい。また、第１乃至第４の実施形態において、入力データ（データセット）の各データユニットは、２つの要素から構成されている。しかし、各データユニットが３つ以上の要素から構成されていても構わない。この場合、データユニットを構成する要素の数をｎ（ｎ≧３）とすると、入力データ解析部１２２は、ｎ次元（つまり多次元）の特徴行列を構成すればよい。また入力データ解析部１２２が、データユニットを構成するｎ個の要素の集合を、１つ以上の要素から構成される、上記ｎより少なく２より多いｍ個（ｎ＞ｍ＞２）の要素グループに区分して、当該ｍ個の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とするｍ次元特徴行列を構成してもよい。また、上記ｍが２であっても構わない。つまり、３つ以上の要素のうちの１つ以上の要素から構成される第１の要素グループを行（第１の次元）とし、３つ以上の要素のうちの残りの要素から構成される第２の要素グループを列（第２の次元）とする特徴行列（２次元の特徴行列）を構成して構わない。
【００８９】
以上説明した少なくとも１つの実施形態によれば、特定の１要素ではなく、複数の要素を複合的に考慮してクラスタリングすることで、より精度の良いクラスタリング結果を得ることができるデータクラスタリング装置及び方法を提供することができる。
【００９０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９１】
１０…データ処理システム、１１…データ保管部、１２…クラスタリングユニット（データクラスタリング装置）、１２１…入力部、１２２…入力データ解析部、１２３…判定部、１２４…結合部、１２５…出力部、１２６…ワーキングメモリ（記憶手段）。
【技術分野】
【０００１】
本発明の実施形態は、データクラスタリング装置及び方法に関する。
【背景技術】
【０００２】
従来から、例えばデータ共有サーバのような計算機において、ユーザがどのような操作をしたかの履歴を示すデータを保管し、このデータを解析し、各ユーザの不正な操作や異常な操作、操作の全体的な傾向などを、機械学習などを行うことによって抽出する技術が知られている。このような技術を用いる際、入力するデータの種類（操作の種類や操作の対象の種類など）が多い場合、元のデータをそのまま利用し機械学習を行うには計算量が膨大になるため、現実的な時間で有益な結果を導き出すことは難しい。
【０００３】
そこで、学習データの多様性を減らすために、データをクラスタリングすることが知られている。クラスタリング手法としては、データから多次元ベクトルを構成し、各ベクトル間の距離を導出し、それに基づいて例えばｋ平均法（ｋ−ｍｅａｎｓ法）などによりクラスタリングする方法が一般的である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−２２９３６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のクラスタリング手法では、そもそも多次元ベクトルとして構成する際、ベクトルの次元数や成分の取り方によって結果が大きく左右されるにも拘わらず、次元数や成分の取り方はクラスタリングとは直接関係の無い決め方がなされている。また、データのどの要素を特徴ベクトルの要素として採用するか否かを事前に設定しておく必要があり、データ全体を見て重要でないデータを削ぎ落としたり、似たような特徴のデータを統合したりするという作業はクラスタリングとは別に前処理として実施する必要がある。
【０００６】
そのため、前処理の実施方法が自明でない場合や前処理結果の評価が難しい場合、前処理をどのように実施するかを決定するのも難しくなる。
そこで、従来技術において前処理として切り離されていた、入力データを多次元ベクトルとして抽象化するような処理も総合的に考慮したクラスタリング手法が要求される。
【０００７】
本発明が解決しようとする課題は、複数の要素を持つデータユニットの集合を、特定の１要素ではなく、複数の要素を複合的に考慮してクラスタリングすることで、より精度の良いクラスタリング結果を得ることができるデータクラスタリング装置及び方法を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、データクラスタリング装置は、入力手段と、解析手段と、記憶手段と、判定手段と、結合手段と、出力手段とを具備する。入力手段は、複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力する。解析手段は、前記入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成する。記憶手段は、前記入力されたデータセット、前記多次元特徴行列、及び前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を格納する。判定手段は、前記多次元特徴行列の前記１つ以上の次元を対象に、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行する。結合手段は、前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行する。前記判定手段及び前記結合手段は、前記更新後の多次元特徴行列が第２の条件を満たすまで、それぞれ前記判定処理及び前記結合処理を繰り返す。前記出力手段は、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態に係るクラスタリングユニットを備えたデータ処理システムの構成を示すブロック図。
【図２】第１の実施形態においてクラスタリングの対象となるデータセットの一例を示す図。
【図３】図２に示されるデータセットに基づいて生成される特徴行列の一例を示す図。
【図４】第１の実施形態においてクラスタリング処理の過程で生成される分類結果表の一例を示す図。
【図５】第１の実施形態において結合部から出力部に渡される分類結果表の一例を示す図。
【図６】第１の実施形態におけるクラスタリング結果の一例を示す図。
【図７】第１の実施形態における上記クラスタリング処理の手順を示すフローチャート。
【図８】第１の実施形態における１回目の特徴ベクトル結合後の特徴行列を示す図。
【図９】第１の実施形態における１回目の特徴ベクトル結合前後の分類結果表を示す図。
【図１０】第１の実施形態における２回目の特徴ベクトル結合後の特徴行列を示す図。
【図１１】第１の実施形態における３回目の特徴ベクトル結合後の特徴行列を示す図。
【図１２】第２の実施形態における一連の特徴ベクトル結合完了後の分類結果表の一例を示す図。
【図１３】第２の実施形態におけるクラスタリング結果の一例を示す図。
【図１４】第３の実施形態における圧縮完了後の行の分類結果表及び列の分類結果表の一例を示す図。
【図１５】第３実施形態におけるクラスタリング結果の一例を示す図。
【図１６】図１４の行の分類結果表及び列の分類結果表で示される、第１の要素が結合された行及び第２の要素が結合された列の組み合わせとクラスを示す記号との関係を示す図。
【図１７】第４の実施形態においてクラスタリングの対象となるデータセットに基づいて生成される行圧縮特徴行列及び列圧縮特徴行列の例を示す図。
【図１８】第４の実施形態における１回目の圧縮完了後の行圧縮特徴行列を示す図。
【図１９】第４の実施形態における１回目の圧縮完了後の行の分類結果表を示す図。
【図２０】第４の実施形態における２回目の圧縮完了後の列圧縮特徴行列を示す図。
【図２１】第４の実施形態における２回目の圧縮完了後の列の分類結果表を示す図。
【図２２】第４の実施形態における３回目の圧縮完了後の行圧縮特徴行列を示す図。
【図２３】第４の実施形態における３回目の圧縮完了後の行の分類結果表を示す図。
【図２４】第４の実施形態におけるクラスタリング結果の一例を示す図。
【発明を実施するための形態】
【００１０】
以下、実施の形態につき図面を参照して説明する。
［第１の実施形態］
図１は第１の実施形態に係るクラスタリングユニットを備えたデータ処理システムの構成を示すブロック図である。
図１において、データ処理システム１０は、データ保管部１１及びクラスタリングユニット１２を備えている。データ処理システム１０は、例えばデータ共有サーバ計算機のような単一の計算機により構成されている。
【００１１】
データ保管部１１は、ユーザがどのような操作をしたかの履歴を示すデータ（操作履歴データ）を保管する。この操作履歴データは、例えば、データ処理システム１０を構成する計算機へのユーザの操作によるアクセスのログであり、図示せぬ手段によってデータ保管部１１に予め保存されているものとする。データ保管部１１は、例えばデータ処理システム１０を構成する計算機が有する、ディスク装置のような不揮発性記憶装置に置かれる。
【００１２】
クラスタリングユニット１２は、データクラスタリング装置として機能して、データ保管部１１に格納されているデータから特定の特徴を持ったデータセットを抽出する。即ちクラスタリングユニット１２は、データ保管部１１からクラスタリングの対象データを受け取り、受け取った対象データをある指定された数のクラスに分類する。
【００１３】
クラスタリングユニット１２は、入力部１２１、入力データ解析部１２２、判定部１２３、結合部１２４及び出力部１２５の各機能要素と、ワーキングメモリ１２６とを備えている。入力部１２１、入力データ解析部１２２、判定部１２３、結合部１２４及び出力部１２５は、データ処理システム１０を構成する計算機が、例えば、ディスク装置のような不揮発性記憶装置に格納されているプログラムを読み込んで実行することにより実現されるものとする。このプログラムが、外部の計算機から例えばネットワークを介してダウンロードされたものであっても構わない。このプログラムは、クラスタリングの対象となるデータから、ある特定の特徴を持つデータを識別する機能を持つ。
【００１４】
入力部１２１は、例えばデータ保管部１１から、クラスタリングの対象となるデータセットを受け取り、当該受け取ったデータセットを入力データ解析部１２２に渡す。第１の実施形態においてデータ保管部１１に格納されているデータは、前述したように、データ処理システム１０を構成する計算機へのユーザの操作によるアクセスのログであり、例えば、当該計算機内の同一機器または当該計算機内の同一プログラムに存在するデータである。しかし、データ保管部１１に格納されているデータが、外部の計算機内の機器や当該外部の計算機内のプログラムに存在するデータであっても構わない。また、外部の計算機の機器やプログラムから入力部１２１がデータを受け取っても構わない。
【００１５】
図２は、入力部１２１が受け取る、クラスタリングの対象となるデータセットの一例を示す。図２の例では、データセットは、２つの文字列の組を持つデータユニットの集合である。２つの文字列はそれぞれ異なる集合の要素である。図２の例において、データユニット内の一方の文字列である第１の要素（データ１）は英文中に出現する動詞であり、他方の文字列である第２の要素（データ２）は当該英文中に出現する名詞である。
【００１６】
再び図１を参照すると、入力データ解析部１２２は、入力部１２１が受け取ったデータセット（つまり入力データ）を解析し、上記２つの文字列のうち第１の要素（データ１）を縦軸（縦方向の次元、つまり行の次元）の要素（行要素）ｉ、第２の要素（データ２）を横軸（横方向の次元、つまり列の次元）の要素（列要素）ｊとし、出現回数を行列の要素（成分）ａijとする２次元の行列（以下、特徴行列と称する）を生成する。
【００１７】
図３は、図２に示されるデータセットに基づいて入力データ解析部１２２によって生成された特徴行列の一例を示す。図３に示す特徴行列の例えば第３（ｒｅａｄ）行、第２（ｂｏｏｋ）列の要素ａ32（値）は６である。この「６」は、「“ｒｅａｄ”，“ｂｏｏｋ”」という文字列を持つデータユニットが、入力されたデータセット内に６回出現していたということを意味する。入力データ解析部１２２は、生成した特徴行列をワーキングメモリ１２６に格納する。
【００１８】
なお、入力データ解析部１２２による入力データ（入力されたデータセット）の解析手法は、上述の例のみならず、各種方法が考えられる。入力データが、２つの文字列（要素）の組を持つデータユニットの集合の場合、結果としてクラスタリング対象の２要素の一方を行要素とし、他方を列要素とする、当該行要素及び列要素の組み合わせの特徴を表現する行列が構成されればよい。また、２要素が、動詞と名詞である必要はない。
【００１９】
判定部１２３は、ワーキングメモリ１２６から特徴行列を読み出し、当該特徴行列の任意の２つの行の要素（成分）の集合（以下、特徴ベクトルと称する）毎に、その２つの特徴ベクトルの間の結合指数を計算する。判定部１２３はまた、特徴行列の任意の２つの列の要素（成分）の集合（特徴ベクトル）毎に、その２つの特徴ベクトルの間の結合指数を計算する。そして判定部１２３は、結合指数が最小の組み合わせとなる２つの特徴ベクトルを抽出する。結合指数は２つの特徴ベクトルの相違度と重要度に正の相関を持つ値である。図３において、例えば第１行、つまり行１（ｉ＝１）の特徴ベクトル（行特徴ベクトル）は、（１，１，４）で表される。また、例えば第１列、つまり列１（ｊ＝１）の特徴ベクトル（列特徴ベクトル）は、（１，２，０，３）で表される。
【００２０】
相違度は特徴ベクトル同士の方向の違いの大きさを表す値であり、方向が異なるほど大きな値を示す。相違度として、例えば２つの特徴ベクトルのなす角度の大きさをθとした場合のｓｉｎθなどを用いることが考えられる。重要度は特徴ベクトルを構成する各要素が当該特徴ベクトルの他の要素と比較して、どのくらい特徴的な値であるか、各要素がどのくらい大きいかを表す値である。重要度は、特徴的であるほど大きな値を示し、各要素の値が大きいほど大きな値を示す。重要度として、例えば特徴ベクトルの絶対値（特徴ベクトルの長さ）を用いてもよい。この場合、例えば２つの特徴ベクトルの各々の重要度（絶対値）の積と前記２つの特徴ベクトルの前記相異度との積を結合指数として用いてもよい。
【００２１】
第１の実施形態では、結合指数として、２つの特徴ベクトルの外積の絶対値が用いられる。ここでは、特徴ベクトルａと特徴ベクトルｂの外積の絶対値の２乗が、｜ａ｜２｜ｂ｜２−（ａ・ｂ）２と定義される（ａ・ｂはａとｂの内積）。この場合、２つの特徴ベクトルａ及びｂの長さが小さく（つまり重要度が低く）、なす角度が小さい（つまり相違度が低い）ほど、結合指数が小さくなる。判定部１２３は、抽出した２つの特徴ベクトルのデータを結合部１２４に送る。
【００２２】
結合部１２４は、判定部１２３から受け取った２つの特徴ベクトルを結合し、１つのベクトルとして、ワーキングメモリ１２６に格納されている特徴行列を更新する。結合の方法としては例えば、２つの特徴ベクトルの各成分の和をそれぞれ新しいベクトルの成分とする方法などが考えられる。また結合部１２４は、結合の際、受け取った２つの特徴ベクトルが新しく生成されたベクトルのクラスに分類されたものとして分類結果表を更新する。分類結果表は、ワーキングメモリ１２６に格納して用いられるものとする。第１の実施形態では結合部１２４は、行の特徴ベクトルが結合された場合にのみ分類結果表を更新する。
【００２３】
図４は、分類結果表の一例を示す。第１の実施形態において、分類結果表は、行の各特徴ベクトルをクラスとして保持する。判定部１２３は、更新の際は結合した行をどちらかのクラスに統合する操作を行う。図４に示される分類結果表において、クラスの表記には、行要素の値が用いられている。しかし、クラスの表記は、行要素と直接関連する必要はない。例えば、図４に示すクラス１（ｒｉｄｅ）、クラス２（ｄｏ）、クラス３（ｒｅａｄ）を、それぞれ、単にクラスＡ、クラスＢ、クラスＣのような記号で表記しても良い。
【００２４】
結合部１２４は判定部１２３と協働して上述のような操作を繰り返す。結合部１２４は、この繰り返しの結果、特徴行列に残されている例えば行の特徴ベクトルの数が予め指定された数（クラスの数）まで減少した時点で、当該繰り返しを終了して、ワーキングメモリ１２６を介して分類結果表を出力部１２５に渡す。なお、特徴行列に残されている行及び列の両方の特徴ベクトルの数が予め指定された数まで減少した時点で、上述の繰り返しを終了しても構わない。
【００２５】
図５は、出力部１２５に渡される分類結果表の一例を示す。なお、図４は、上述の操作の繰り返しの途中の分類結果表（より詳細には、１回目の２つの行の特徴ベクトルの結合後の分類結果表）の一例を示したものである。
【００２６】
出力部１２５は、ワーキングメモリ１２６を介して結合部１２４から分類結果表を受け取ると、当該分類結果表と入力データセットとに基づき、データユニット毎にクラス分けをした結果（クラスタリング結果）を出力データとして出力する。
【００２７】
図６は出力データの一例を示す。図６に示す出力データは、入力データセットのデータユニット毎にそのデータユニットがどのクラスに属するかを記述した表形式のクラスタリング結果を示す。図６の出力データ（クラスタリング結果）において、クラスＡは図５におけるクラス１に、クラスＢは図５におけるクラス３に、それぞれ対応する。他にも入力データセットの種類毎にその種類のがどのクラスに属するかを出力データとする方法などが適用可能である。
【００２８】
第１の実施形態において上述のように特徴行列を生成した場合、当該特徴行列で示される各特徴ベクトルの絶対値（特徴ベクトルの長さ）は、対応する行または列の要素のデータとしての重要度を表している。また、特徴ベクトル同士のなす角度をθとした場合のｓｉｎθは、θが大きくなればなるほど大きくなり、特徴ベクトルの相異度（どのくらい異なるかの度合い）を表す。つまり、結合指数が小さい２つの特徴ベクトルを結合（統合）するということは、特徴行列を構成する特徴ベクトルとして重要度が低いものを、他の重要度が低く、似ている特徴ベクトル（ベクトルの方向が似ている特徴ベクトル）に統合することを意味する。
【００２９】
このように統合を行うことで、全体の特徴を失うことなく、全体の特徴とはあまり関係の無いデータをできるだけ影響が小さい形で統合することができる。つまり、このような「結合指数」を用いて統合を繰り返した結果、全体の特徴は失わず、重要でないデータはできるだけ似たもの同士統合したクラスタリング結果を得ることができる。
【００３０】
第１の実施形態によれば、予め定められたルールに基づいて多次元ベクトルを構成した後にクラスタリングを行う方法に比べ、特定の１要素ではなく、複数の要素を複合的に考慮して、つまり多次元ベクトルの各成分の類似度（相違度）や距離などを考慮した上で多次元ベクトルを構成することができ、より精度の良いクラスタリング結果を得ることができる。また、出現頻度の低い重要でないデータを削ぎ落としつつ、似た特徴を有するデータは統合し、他とは異なる特徴を持つデータを残したクラスタリング結果を得ることができる。
【００３１】
次に、第１の実施形態におけるクラスタリングユニット１２の動作の概要について説明する。
まず、クラスタリングユニット１２は、データ保管部１１から、例えば図２に示したようなクラスタリングの対象データを受け取り、当該対象データに対してクラスタリング処理を行う。このクラスタリング処理において、クラスタリングユニット１２の出力部１２５は、図５に示したような分類結果表と図２に示したようなクラスタリングの対象データ（入力データセット）とに基づき、データセット毎にクラス分けをした結果を出力データとして出力する。
【００３２】
次に、第１の実施形態における上記クラスタリング処理の手順について、図７のフローチャートを参照して説明する。
まず入力部１２１は、データ保管部１１から図２に示したようなクラスタリングの対象となるデータ（データセット）を受信する（ステップＳ１１）。入力部１２１が受信したデータは入力データ解析部１２２に渡される。
【００３３】
入力データ解析部１２２は、入力部１２１が受信したデータを当該入力部１２１から受け取ると、当該受信データ（入力データ）を解析することにより、図３に示したような特徴行列を生成する（ステップＳ１２）。このステップＳ１２において、入力データ解析部１２２は、生成された特徴行列に基づいて、当該特徴行列の行及び列の少なくとも一方、例えば行の各特徴ベクトルをクラスとして保持する分類結果表も生成する。生成された特徴行列及び分類結果表は、入力データと共に、ワーキングメモリ１２６に格納される。
【００３４】
判定部１２３は、入力データ解析部１２２によって生成された特徴行列の行及び列の少なくとも一方、例えば行及び列の両方を対象に、当該特徴行列から２つの特徴ベクトルの組み合わせを全て抽出する（ステップＳ１３）。即ち判定部１２３は、特徴行列の行を対象に、当該特徴行列から２つの行の特徴ベクトルの組み合わせを全て抽出する。また判定部１２３は、特徴行列の列を対象に、当該特徴行列から２つの列の特徴ベクトルの組み合わせを全て抽出する。
【００３５】
判定部１２３は、抽出された行及び列のそれぞれの２つの特徴ベクトルの組み合わせ毎に、その２つの特徴ベクトルの間の結合指数を計算する（ステップＳ１４）。そして判定部１２３は、計算した結合指数が第１の条件に合致する組み合わせの特徴ベクトル、例えば計算した結合指数が最も小さい組み合わせの特徴ベクトルを抽出する（ステップＳ１５）。
【００３６】
結合部１２４は、判定部１２３によって抽出された、結合指数が最も小さい組み合わせの特徴ベクトルを結合する（ステップＳ１６）。結合部１２４は、この特徴ベクトル結合結果に基づいて、特徴行列及び分類結果表を更新する（ステップＳ１７）。
【００３７】
上述のステップＳ１３〜Ｓ１７は、更新後の特徴行列が第２の条件を満たすまで、例えば更新後の特徴行列に残っている行の特徴ベクトルの数が、予め指定された数（ここでは、ユーザによって指定された数）に達するまで（ステップＳ１８）、繰り返される。そして、残っている行の特徴ベクトルの数が指定数に達すると、出力部１２５は、図６に示したようなクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００３８】
＜第１の実施形態の具体例＞
次に第１の実施形態における上述した図７のフローチャートに従う動作の流れを、図２乃至図６に加えて、図８乃至図１１を参照して、具体例を挙げて説明する。
以下の例では、特徴行列の２つの行の特徴ベクトルの全ての組み合わせ及び当該特徴行列の２つの列の特徴ベクトルの全ての組み合わせのうち、最小の結合指数を持つ組み合わせの特徴ベクトルを結合するものとする。結合の終了は行の特徴ベクトルの数が２となったタイミングとする。また、分類結果表は行の特徴ベクトルの圧縮が起こった際のみ更新され、結合指数にはベクトルの外積の絶対値が用いられるものとする。
【００３９】
まず、入力部１２１が、図２に示したような入力データ（データセット）をクラスタリング対象データとして受信したものとする（ステップＳ１１）。入力部１２１によって受信された入力データは入力データ解析部１２２に渡される。入力データ解析部１２２は、入力部１２１から渡された入力データを一旦ワーキングメモリ１２６に格納し、当該ワーキングメモリ１２６に格納された入力データ（図２参照）に基づいて、図３に示したような特徴行列（つまりクラスタリング開始時の特徴行列）を生成する（ステップＳ１２）。ここでは入力データ解析部１２２は、図２に示す入力データの第１要素（データ１）を行要素、第２要素（データ２）を列要素とし、当該入力データを構成するデータユニット毎に、そのデータユニットの第１要素及び第２要素がそれぞれ割り当てられる行要素ｉ及び列要素ｊに対応する、特徴行列の要素（成分）ａijをインクリメントすることにより、当該特徴行列（図３参照）を生成する。生成された特徴行列はワーキングメモリ１２６に格納される。
【００４０】
上記ステップＳ１２において入力データ解析部１２２は、図３に示す特徴行列に基づき、当該特徴行列の例えば行の各特徴ベクトルをクラスとして保持する分類結果表（図９（ａ）参照）も生成する。生成された分類結果表はワーキングメモリ１２６に格納される。
【００４１】
次に判定部１２３は、生成された特徴行列から、２つの行の特徴ベクトルの組み合わせ及び２つの列の特徴ベクトルの組み合わせを全て抽出し（ステップＳ１３）、それぞれの組み合わせ（２つの特徴ベクトルの間）の結合指数として、それぞれの組み合わせの外積の絶対値を計算する（ステップＳ１４）。図３の例における、行及び列それぞれの特徴ベクトルの組み合わせの外積の絶対値の２乗は、次のようになる。
【００４２】
（１）行の特徴ベクトルの組み合わせ
行１−行２：９８
行１−行３：５６６
行１−行４：２５１
行２−行３：１６４
行２−行４：１７
行３−行４：５２９
（２）列の特徴ベクトルの組み合わせ
列１−列２：５０９
列１−列３：１５３
列２−列３：９６３
このように第１の実施形態では結合指数として、便宜的に、外積の絶対値に代えて外積の絶対値の２乗が用いられる。ここで、外積の絶対値の２乗を用いても、結合指数が最小値となる組み合わせは同じである。
【００４３】
上記特徴ベクトルの組み合わせの外積（外積の２乗）のうち、最も小さい外積は１７であり、行２及び行４の特徴ベクトルの組み合わせの外積である。
【００４４】
この場合、結合部１２４は、行２及び行４の特徴ベクトルの組み合わせを、結合指数が最小の組み合わせとして抽出し（ステップＳ１５）、行２及び行４の特徴ベクトルを結合する（ステップ１６）。図３の例では、結合部１２４は、行２の特徴ベクトル（２，２，１）の各成文の値、、つまり行２の列毎の要素ａ2j（ｊ＝１，２，３）の値と、行４の特徴ベクトル（３，４，３）の各成文の値、つまり行４の列毎の要素ａ4j（ｊ＝１，２，３）の値とを加算することにより、行２及び行４の特徴ベクトルを結合する、この１回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（５，６，４）となる。
【００４５】
結合部１２４は、図３に示す特徴行列から、行２及び行４の特徴ベクトルを削除し、結合後の特徴ベクトル（５，６，４）を例えば行２の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図３に示す特徴行列から行４の特徴ベクトルを削除し、行２の特徴ベクトルを、結合後の特徴ベクトル（５，６，４）に更新する（ステップ１７）。これにより図３に示す特徴行列は、図８に示すように更新される。
【００４６】
結合部１２４による行２及び行４の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、行４の特徴ベクトル（３，４，３）の各成文の値を、行２の特徴ベクトル（２，２，１）の各成文の値に加算して、当該行４の特徴ベクトル（３，４，３）を削除することと等価である。
【００４７】
図８に示す特徴行列（つまり１回目の特徴ベクトル結合後の特徴行列）に残っている行の特徴ベクトルの数（つまり有効な行の数）は、図３に示す特徴行列と比較して、４から３に減少している。つまり特徴行列の行が圧縮されている。
【００４８】
第１の実施形態における具体例では、行のクラスタリングのみ行われる。したがって分類結果表は、特徴行列の行のみ、それらの行の特徴ベクトルそれぞれをクラスとして保持すればよい。そこで結合部１２４は、行の特徴ベクトルを結合した場合のみ分類結果表を更新する。つまり結合部１２４は、上述の例のように行４の特徴ベクトルを行２の特徴ベクトルに結合した場合、特徴行列だけでなく、ワーキングメモリ１２６に格納されている分類結果表も更新する（ステップＳ１７）。
【００４９】
図９は、１回目の特徴ベクトル結合前後の分類結果表を示す。つまり分類結果表は、１回目の特徴ベクトル結合後、図９（ａ）に示す状態から図９（ｂ）に示す状態に更新される。図９（ａ）に示す分類結果表、即ち１回目の特徴ベクトル結合前の分類結果表（クラスタリング開始時の分類結果表）のクラスは、１回目の特徴ベクトル結合前の特徴行列の全ての行の特徴ベクトル（行要素）、即ち行１〜３の要素（各データユニットの第１の要素）に対応する。ここでは、分類結果表は、クラスと、そのクラスに分類される行の特徴ベクトル（行要素）が属する行とを対応付けて示す。図９（ｂ）に示す分類結果表は、図４に示した分類結果表に相当する。図９（ｂ）に示す分類結果表では、図９（ａ）に示す分類結果表との比較から明らかなように、クラス２に分類される行の特徴ベクトルが、１回目の特徴ベクトル結合結果である、行２及び行４の特徴ベクトルの結合を反映するように、行２の特徴ベクトルから、行２及び行４の特徴ベクトルの結合後の特徴ベクトルに更新されている。
【００５０】
判定部１２３は、結合部１２４によって分類結果表が更新されると、その際の特徴行列に残っている行の特徴ベクトルの数が、予め指定された数である「２」であるかを判定する（ステップＳ１８）。このとき特徴行列に残っている行の特徴ベクトルの数は、図８から明らかなように３であるため、ステップＳ１８の判定はＮｏとなる。
【００５１】
この場合、判定部１２３は、最新の特徴ベクトル結合（ここでは１回目の特徴ベクトル結合）後の特徴行列（図８参照）に基づいて、再び上記ステップＳ１３〜Ｓ１５を実行する。これにより判定部１２３は、その時点における特徴行列の行及び列それぞれの特徴ベクトルの全ての組み合わせから、結合指数が最小の特徴ベクトルの組み合わせを抽出する。詳細は省略するが、２回目のステップＳ１３〜Ｓ１５の実行では、判定部１２３は、列１及び列３の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝１５３）の組み合わせとして抽出する。
【００５２】
すると結合部１２４は、列１の特徴ベクトル（１，５，０）の各成文の値、つまり列１の行毎の要素ａi1（ｉ＝１，２，３）の値と、列３の特徴ベクトル（４，４，１）の各成文の値、つまり列３の行毎の要素ａi3（ｉ＝１，２，３）の値とを加算することにより、列１及び列３の特徴ベクトルを結合する（ステップＳ１６）。この２回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（５，９，１）となる。
【００５３】
結合部１２４は、図８に示す特徴行列から、列１及び列３の特徴ベクトルを削除し、結合後の特徴ベクトル（５，９，１）を例えば列１の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図８に示す特徴行列から列３の特徴ベクトルを削除し、列１の特徴ベクトルを、結合後の特徴ベクトル（５，９，１）に更新する（ステップ１７）。これにより図８に示す特徴行列は、図１０に示すように更新される。
【００５４】
結合部１２４による列１及び列３の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、列３の特徴ベクトル（４，４，１）の各成文の値を、列１の特徴ベクトル（１，５，０）の各成文の値に加算して、当該列３の特徴ベクトル（４，４，１）を削除することと等価である。
【００５５】
図１０に示す特徴行列（つまり２回目の特徴ベクトル結合後の特徴行列）に残っている列の特徴ベクトルの数（つまり有効な列の数）は、図８に示す特徴行列と比較して、３から２に減少している。つまり特徴行列の列が圧縮されている。
【００５６】
図１０に示す特徴行列の例では、特徴行列に残っている行の特徴ベクトルの数は、１回目の特徴ベクトル結合後と比較して変化しておらず、「３」のままである。この場合、２回目の特徴ベクトル結合後のステップＳ１８の判定はＮｏとなり、判定部１２３は、当該２回目の特徴ベクトル結合後の特徴行列（図１０参照）に基づいて、３回目のステップＳ１３〜Ｓ１５を実行する。詳細は省略するが、３回目のステップＳ１３〜Ｓ１５の実行では、判定部１２３は、行１及び行２の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝４４１）の組み合わせとして抽出する。
【００５７】
すると結合部１２４は、行１の特徴ベクトル（５，１）の各成文の値と行２の特徴ベクトル（９，６）の各成文の値とを加算することにより、行１及び行２の特徴ベクトルを結合する（ステップＳ１６）。この３回目の特徴ベクトル結合の結果、生成された特徴ベクトル、つまり結合後の特徴ベクトルは、（１４，７）となる。
【００５８】
結合部１２４は、図１０に示す特徴行列から、行１及び行２の特徴ベクトルを削除し、結合後の特徴ベクトル（１４，７）を例えば行１の新たな特徴ベクトルとして、当該特徴行列に追加する。つまり結合部１２４は、図１０に示す特徴行列から行２の特徴ベクトルを削除し、行１の特徴ベクトルを、結合後の特徴ベクトル（１４，７）に更新する（ステップ１７）。これにより図１０に示す特徴行列は、図１１に示すように更新される。
【００５９】
結合部１２４による行１及び行２の特徴ベクトルの結合と特徴行列の更新とは、当該特徴行列上で、行２の特徴ベクトル（９，６）の各成文の値を、行１の特徴ベクトル（５，１）の各成文の値に加算して、当該行２の特徴ベクトル（９，６）を削除することと等価である。
図１１に示す特徴行列に残っている行の特徴ベクトルの数は、図１０に示す特徴行列と比較して、３から２に減少している。つまり特徴行列の行が圧縮されている。
【００６０】
結合部１２４は、行の特徴ベクトルを結合したことから、この特徴ベクトル結合結果に基づいて、特徴行列だけでなく分類結果表も更新する（ステップＳ１７）。
図５は、３回目の特徴ベクトル結合後の分類結果表を示したものである。つまり分類結果表は、３回目の特徴ベクトル結合後、図９（ｂ）に示す状態から図５に示す状態に更新される。図５に示す分類結果表では、図９（ｂ）に示す分類結果表との比較から明らかなように、クラス１に分類される行の特徴ベクトルが、３回目の特徴ベクトル結合結果である、行１及び行３の特徴ベクトルの結合を反映するように、行１の特徴ベクトルから、行１及び行３の特徴ベクトルの結合後の特徴ベクトルに更新されている。このとき、図１１に示す３回目の特徴ベクトル結合後の特徴行列に残っている行の特徴ベクトルの数は予め指定された数「２」に一致する（ステップＳ１８のＹｅｓ）。
【００６１】
すると出力部１２５は、図５に示す最終的な分類結果表及び図２に示す入力データに基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する（ステップＳ１９）。ここでは、出力部１２５は、入力データのデータユニット毎にそのデータユニットが、どのクラスに属するかを分類結果表に基づいて分類し、分類されたクラスを示すデータを対応するデータユニットに付加することで、クラスタリング結果を生成する。図６は、このときのクラスタリング結果（出力データ）の一例を示したものである。
【００６２】
なお、第１の実施形態では、分類結果表は、行の各特徴ベクトルをクラスとして保持し、行の特徴ベクトルが結合された場合にのみ更新される。しかし、分類結果表が、列の各特徴ベクトルをクラスとして保持し、列の特徴ベクトルが結合された場合にのみ更新される構成としても構わない。このような構成では、特徴行列に残されている、列の特徴ベクトルの数、または行及び列の両方の特徴ベクトルの数が予め指定された数（クラスの数）まで減少した時点で、判定処理及び結合処理の繰り返しを終了してもよい。
【００６３】
［第２の実施形態］
次に第２の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第２の実施形態に係るデータ処理システムの構成は、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００６４】
第２の実施形態の特徴は、第１の実施形態と異なって、特徴行列における行及び列それぞれの結合指数を単純に比較するのではなく、例えば、特徴行列の行の圧縮を優先させるとか、特徴行列の行の圧縮のみを行うことにある。そのため第２の実施形態では、判定部１２３から結合部１２４に渡される特徴ベクトルを当該判定部１２３が抽出するための抽出基準として、第１の実施形態のそれとは異なるものが適用される。
【００６５】
例えば、第１の実施形態では判定部１２３は、行及び列それぞれ任意の特徴ベクトル間の結合指数を計算し、結合指数が最小の組み合わせを抽出していた。これに対し、第２の実施形態では、判定部１２３が結合指数を計算する対象が、行または列のいずれか一方の特徴ベクトルに限定される。
【００６６】
＜第２の実施形態の具体例＞
以下、第２の実施形態の具体例について、図７のフローチャートを援用して説明する。但し第２の実施形態では、特徴行列の列の圧縮は行われず、行の圧縮のみ行われるものとする。ここで、入力データは第１の実施形態と同様であるとする（図２参照）。この場合、特徴行列の生成までの動作は第１の実施形態と同様であり、１回目の特徴ベクトル結合に関しても第１の実施形態と同様である（図８参照）。
【００６７】
２回目の特徴ベクトル結合では、判定部１２３は、行１及び行３の特徴ベクトルの組み合わせを、結合指数が最小（外積の２乗＝５６６）の組み合わせとして抽出する（ステップＳ１５）。すると、結合部１２４は、例えば行３の特徴ベクトル（０，６，１）の各成文の値を、行１の特徴ベクトル（１，１，４）の各成文の値に加算して、当該行３の特徴ベクトル（０，６，１）を削除する（ステップＳ１６，Ｓ１７）。この結果、２回目の特徴ベクトル結合後の新たな行１の特徴ベクトルは（１，７，５）となる。特徴ベクトル結合は２回目で完了し、その時点での分類結果表に基づいて、入力データのデータユニット毎にそのデータユニットが、どのクラスに属するかが決定される。
図１２は一連の特徴ベクトル結合完了後の分類結果表の一例を示し、図１３は図１２に示す分類結果表及び図２に示す入力データに基づくクラスタリング結果の一例を示す。図１３のクラスタリング結果において、クラスＡは図１２におけるクラス１に、クラスＢは図１２におけるクラス２に、それぞれ対応する。
【００６８】
第２の実施形態によれば、第１の要素（データ１）と第２の要素（データ２）を同列に扱うのが適当でない場合や、第２の要素が第１の要素の従属要素である場合などに、そのような実態を加味したクラスタリングを行うことが可能となる。
【００６９】
なお、第２の実施形態において、行または列のいずれか一方の結合指数を例えばユーザによって指定された重みで重み付けして、その重み付けされた結合指数（つまり結合指数と重みとの積）を、他方の結合指数と比較し、最小のものを抽出してもよい。
【００７０】
また、上記一方の結合指数及び上記他方の結合指数に、いずれを重要視するかに応じてそれぞれ異なる重みを付してもよい。つまり判定部１２３は、特徴行列の行及び列を対象に、当該特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、行の２つの特徴ベクトルの間の結合指数を、当該行に対応する第１の重みで重み付けし、列の２つの特徴ベクトルの間の結合指数を、当該列に対応する第２の重みで重み付けし、重み付け後の結合指数が最小の２つの特徴ベクトルを抽出するようにしてもよい。重みが１の場合、重み付けしないことと等価である。
また、ユーザによって指定された数、或いは予め指定された数に結合されるまでは、行または列のいずれか一方のみ抽出を行い、その後、他方の抽出を行うことも可能である。
【００７１】
［第３の実施形態］
次に第３の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第３の実施形態に係るデータ処理システムの構成も、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００７２】
第３の実施形態の特徴は、結合部１２４が行及び列双方の分類結果表を記録し、特徴行列のゼロ以外の成分の残数が、例えばユーザによって指定された、クラスタリングしたい数（以下、クラスタリング数と称する）以下になった時点で、クラスタリング結果が出力される点にある。この場合、特徴行列の各成分をクラスタリング結果のクラスとし、各データユニットは第１の要素が結合された行と第２の要素が結合された列の交点（組み合わせ）に対応するクラスに分類されたものとする。
【００７３】
＜第３の実施形態の具体例＞
以下、第３の実施形態の具体例について、クラスタリング数が４であるものとして説明する。入力データが第１及び第２の実施形態と同様であるとすると（図２参照）、第２の実施形態と同様の経過を辿り、３回目の特徴ベクトル結合（つまり圧縮）が完了した時点で、特徴行列の行数は２で列数は２となる。この特徴行列のゼロ以外の成分の残数は４であり、クラスタリング数４以下である。そこで、圧縮（結合）処理は終了する。
【００７４】
図１４は、圧縮完了の時点における行の分類結果表及び列の分類結果表を示すもので、同図（ａ）は行の分類結果表を、同図（ｂ）は列の分類結果表を、それぞれ示す。行の分類結果表は、図５に示した第１の実施形態における分類結果表と同様である。
【００７５】
出力部１２５は、図１４（ａ）に示す行の分類結果表、図１４（ｂ）に示す列の分類結果表及び入力データ（図８参照）に基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００７６】
図１５は図１４（ａ）及び（ｂ）の分類結果表で示される、第１の要素が結合された行及び第２の要素が結合された列の組み合わせとクラスを示す記号との関係を示し、図１６は第３の実施形態におけるクラスタリング結果の一例を示す。図１５から明らかなように、図１６のクラスタリング結果において、クラスＡは図１４（ａ）の分類結果表のクラス１及び図１４（ｂ）の分類結果表のクラス１の組み合わせに、クラスＢは図１４（ａ）の分類結果表のクラス１及び図１４（ｂ）の分類結果表のクラス２の組み合わせに、クラスＣは図１４（ａ）の分類結果表のクラス３及び図１４（ｂ）の分類結果表のクラス１の組み合わせに、そしてクラスＤは図１４（ａ）の分類結果表のクラス３及び図１４（ｂ）の分類結果表のクラス２の組み合わせに、それぞれ対応する。
【００７７】
第３の実施形態によれば、第１の要素と第２の要素をそれぞれ独立の要素とみなし、第１及び第２の要素をそれぞれ主要素とする観点から行ったクラスタリング結果を取得することができる。このため第３の実施形態は、第１及び第２の要素をそれぞれクラスタリングしたいが、それぞれの要素は他方の要素で特徴付けられるような場合のデータに対して有効である。
なお、第３の実施形態に、第２の実施形態を組み合わせてもよい。
【００７８】
［第４の実施形態］
次に第４の実施形態に係るクラスタリングユニットを備えたデータ処理システムについて説明する。この第４の実施形態に係るデータ処理システムの構成も、第１の実施形態と同様であるため、以下の説明では図１を援用する。
【００７９】
第４の実施形態の第１の特徴は、行の圧縮を記録する行圧縮特徴行列と、列の圧縮を記録する列圧縮特徴行列とを保持し、行の特徴ベクトルの結合指数の計算には行圧縮特徴行列を用い、列の特徴ベクトルの結合指数の計算には列圧縮特徴行列を用いる点にある。
第４の実施形態の第２の特徴は、行の特徴ベクトルの結合を行圧縮特徴行列で行い、列の特徴ベクトルの結合を列圧縮特徴行列で行う点にある。
【００８０】
第４の実施形態の第３の特徴は、行の分類結果表と、列の分類結果表とを保持し、行の特徴ベクトルの結合（行圧縮特徴行列の更新）に応じて行の分類結果表を更新し、列の特徴ベクトルの結合（列圧縮特徴行列の更新）に応じて列の分類結果表を更新する点にある。
【００８１】
＜第４の実施形態の具体例＞
以下、第４の実施形態の具体例について説明する。ここでは、行圧縮特徴行列の行の数が２となった時点で圧縮（結合）が終了するものとする。また、結合指数として、第１の実施形態等と同様に、特徴ベクトル同士の外積の絶対値が用いられる。
【００８２】
入力データ（クラスタリング対象データセット）が第１の実施形態と同様であるとすると（図２参照）、入力データ解析部１２２は、当該入力データに基づいて行圧縮特徴行列及び列圧縮特徴行列を生成する。生成された行圧縮特徴行列及び列圧縮特徴行列は、図３に示す特徴行列と同様である。生成された行圧縮特徴行列及び列圧縮特徴行列を、それぞれ図１７（ａ）及び（ｂ）に示す。なお、第３の実施形態では、入力データに基づいて行圧縮特徴行列が生成され、この生成された行圧縮特徴行列の複製が列圧縮特徴行列として生成される（用いられる）。
【００８３】
１回目の圧縮は第１の実施形態と同様であり、図１７（ａ）に示す行圧縮特徴行列において、行４の特徴ベクトルを行２の特徴ベクトルに結合することにより、当該行圧縮特徴行列の行が圧縮される。図１８は、１回目の圧縮が完了した後の行圧縮特徴行列を示す。列圧縮特徴行列は変化しない。
１回目の圧縮が完了すると、結合部１２４は、行の分類結果表を更新する。図１９は、１回目の圧縮完了後の行の分類結果表を示す。この図１９に示す行の分類結果表は、図９（ｂ）に示す分類結果表と同様である。
【００８４】
２回目の圧縮も第１の実施形態と同様であり、図１７（ｂ）に示す列圧縮特徴行列において、列３の特徴ベクトルを列１の特徴ベクトルに結合することにより、当該列圧縮特徴行列の列が圧縮される。図２０は、２回目の圧縮が完了した後の列圧縮特徴行列を示す。行圧縮特徴行列は変化しない。
２回目の圧縮が完了すると、結合部１２４は、列の分類結果表を更新する。図２１は、２回目の圧縮完了後の列の分類結果表を示す。
【００８５】
３回目の圧縮では、図１８に示す行圧縮特徴行列において、行３の特徴ベクトルを行１の特徴ベクトルに結合することにより、当該行圧縮特徴行列の行が圧縮される。図２２は、３回目の圧縮が完了した後の行圧縮特徴行列を示す。列圧縮特徴行列は変化しない。
３回目の圧縮が完了すると、結合部１２４は、行の分類結果表を更新する。図２３は、３回目の圧縮完了後の行の分類結果表を示す。この図２３に示す行の分類結果表は、図１２に示す分類結果表と同様である。この時点で、図２２に示す行圧縮特徴行列から明らかなように、行の特徴ベクトルの残りが２つとなる。そこで結合部１２４は、一連の結合処理を終了する。
【００８６】
すると出力部１２５は、図２３に示す行の分類結果表、図２１に示す列の分類結果表及び入力データ（図２参照）に基づいてクラスタリング結果を生成し、当該クラスタリング結果を出力データとして出力する。
【００８７】
図２４は第４の実施形態におけるクラスタリング結果の一例を示す。図２４のクラスタリング結果において、クラスＡは図２３の行の分類結果表のクラス１及び図２１の列の分類結果表のクラス１の組み合わせに、クラスＢは図２３の行の分類結果表のクラス１及び図２１の列の分類結果表のクラス２の組み合わせに、クラスＣは図２３の行の分類結果表のクラス２及び図２１の列の分類結果表のクラス１の組み合わせに、そしてクラスＤは図２３の行の分類結果表のクラス２及び図２１の列の分類結果表のクラス２の組み合わせに、それぞれ対応する。
【００８８】
第４の実施形態によれば、行の圧縮と列の圧縮とが、それぞれ行圧縮行列及び列圧縮行列上で行われるため、行の圧縮結果と列の圧縮結果とが互いに干渉するのを防止でき、行及び列それぞれを一定の基準で独立にクラスタリングした結果を取得できる。このため第４の実施形態は、例えば入力データの態様を重視したクラスタリングに有効である。
なお、第４の実施形態に、第２の実施形態及び／または第３の実施形態を組み合わせてもよい。また、第１乃至第４の実施形態において、入力データ（データセット）の各データユニットは、２つの要素から構成されている。しかし、各データユニットが３つ以上の要素から構成されていても構わない。この場合、データユニットを構成する要素の数をｎ（ｎ≧３）とすると、入力データ解析部１２２は、ｎ次元（つまり多次元）の特徴行列を構成すればよい。また入力データ解析部１２２が、データユニットを構成するｎ個の要素の集合を、１つ以上の要素から構成される、上記ｎより少なく２より多いｍ個（ｎ＞ｍ＞２）の要素グループに区分して、当該ｍ個の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とするｍ次元特徴行列を構成してもよい。また、上記ｍが２であっても構わない。つまり、３つ以上の要素のうちの１つ以上の要素から構成される第１の要素グループを行（第１の次元）とし、３つ以上の要素のうちの残りの要素から構成される第２の要素グループを列（第２の次元）とする特徴行列（２次元の特徴行列）を構成して構わない。
【００８９】
以上説明した少なくとも１つの実施形態によれば、特定の１要素ではなく、複数の要素を複合的に考慮してクラスタリングすることで、より精度の良いクラスタリング結果を得ることができるデータクラスタリング装置及び方法を提供することができる。
【００９０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９１】
１０…データ処理システム、１１…データ保管部、１２…クラスタリングユニット（データクラスタリング装置）、１２１…入力部、１２２…入力データ解析部、１２３…判定部、１２４…結合部、１２５…出力部、１２６…ワーキングメモリ（記憶手段）。
【特許請求の範囲】
【請求項１】
複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力する入力手段と、
前記入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成する解析手段と、
前記入力されたデータセット、前記多次元特徴行列、及び前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を格納する記憶手段と、
前記多次元特徴行列の前記１つ以上の次元を対象に、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行する判定手段と、
前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行する結合手段と、
出力手段とを具備し、
前記判定手段及び前記結合手段は、前記更新後の多次元特徴行列が第２の条件を満たすまで、それぞれ前記判定処理及び前記結合処理を繰り返し、
前記出力手段は、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する
データクラスタリング装置。
【請求項２】
前記結合手段は、前記第１の条件を満たす２つの特徴ベクトルを前記多次元特徴行列から削除し、且つ前記結合後の特徴ベクトルを前記多次元特徴行列に追加することにより、前記多次元特徴行列を更新する請求項１記載のデータクラスタリング装置。
【請求項３】
前記第２の条件は、前記更新後の多次元特徴行列における予め指定された次元の特徴ベクトルの数が予め指定されたクラス数に一致することであり、
前記１つ以上の次元は、前記予め指定された次元を含み、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記予め指定された次元の要素グループが分類されたクラスに分類する
請求項１または２に記載のデータクラスタリング装置。
【請求項４】
前記判定手段は、前記結合指数が最小の２つの特徴ベクトルを前記第１の条件を満たす２つの特徴ベクトルとして抽出する請求項１乃至３のいずれかに記載のデータクラスタリング装置。
【請求項５】
前記結合指数は、対応する前記２つの特徴ベクトルの各々の重要度の積が小さく、当該２つの特徴ベクトルのなす角度が小さいものほど小さくなる請求項１乃至４のいずれかに記載のデータクラスタリング装置。
【請求項６】
前記複数の要素グループは第１の要素グループ及び第２の要素グループから構成され、
前記多次元特徴行列は、前記第１の要素グループを行の次元とし、前記第２の要素グループを列の次元とする２次元特徴行列である
請求項１または２に記載のデータクラスタリング装置。
【請求項７】
前記第２の条件は、前記更新後の２次元特徴行列における前記予め指定された次元の特徴ベクトルの数が予め指定されたクラス数に一致することであり、
前記分類結果表は前記予め指定された次元の特徴ベクトルの結合を保持し、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記予め指定された次元の要素グループが分類されたクラスに分類する
請求項６記載のデータクラスタリング装置。
【請求項８】
前記１つ以上の次元は、前記２次元特徴行列の行及び列であり、
前記第２の条件は、前記更新後の２次元特徴行列の行数及び列数の積が予め指定されたクラス数に一致することであり、
前記分類結果表は前記行の特徴ベクトルの結合及び前記列の特徴ベクトルの結合を保持し、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記第１の要素グループが分類された行と前記第２の要素グループが分類された列との組み合わせに対応するクラスに分類する
請求項６記載のデータクラスタリング装置。
【請求項９】
前記２次元特徴行列は、前記第１の要素グループを行の次元とし、前記第２の要素グループを列の次元とする行圧縮特徴行列と、前記２次元特徴行列の更新前において前記行圧縮特徴行列に一致する内容の列圧縮特徴行列とから構成され、
前記分類結果表は、前記行圧縮特徴行列の行の各特徴ベクトルをクラスとして保持する第１の分類結果表と前記列圧縮特徴行列の列の各特徴ベクトルをクラスとして保持する第２の分類結果表とから構成され、
前記判定手段は、前記判定処理により、前記多次元特徴行列の前記１つ以上の次元を対象に、前記行圧縮特徴行列及び前記率圧縮特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が前記第１の条件を満たす２つの特徴ベクトルを抽出し、
前記結合手段は、前記第１の条件を満たす２つの特徴ベクトルを結合し、当該第１の条件を満たす２つの特徴ベクトルが行の特徴ベクトルである場合には、前記結合結果に応じて前記行圧縮特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記第１の分類結果表を更新し、当該第１の条件を満たす２つの特徴ベクトルが列の特徴ベクトルである場合には、前記結合結果に応じて前記列圧縮特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記第２の分類結果表を更新し、
前記出力手段は、前記第２の条件を満たした際の前記第１の分類結果表及び前記第２の分類結果表に基づいて前記入力されたデータセットの各データユニットを分類する
請求項６記載のデータクラスタリング装置。
【請求項１０】
入力手段、解析手段、判定手段、結合手段及び記憶手段を備えたデータクラスタリング装置におけるデータクラスタリング方法であって、
前記入力手段が、複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力するステップと、
前記解析手段が、前記入力されたデータセットを前記記憶手段に格納して、当該入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成し、且つ前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を生成して、それぞれ前記記憶手段に格納するステップと、
前記多次元特徴行列の前記１つ以上の次元を対象に、前記判定手段が、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行するステップと、
前記結合手段が、前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行するステップと、
前記更新後の多次元特徴行列が第２の条件を満たすまで、前記判定手段及び前記結合手段が、それぞれ前記判定処理及び前記結合処理を繰り返すステップと、
前記出力手段が、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力するステップと
を具備するデータクラスタリング方法。
【請求項１】
複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力する入力手段と、
前記入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成する解析手段と、
前記入力されたデータセット、前記多次元特徴行列、及び前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を格納する記憶手段と、
前記多次元特徴行列の前記１つ以上の次元を対象に、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行する判定手段と、
前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行する結合手段と、
出力手段とを具備し、
前記判定手段及び前記結合手段は、前記更新後の多次元特徴行列が第２の条件を満たすまで、それぞれ前記判定処理及び前記結合処理を繰り返し、
前記出力手段は、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力する
データクラスタリング装置。
【請求項２】
前記結合手段は、前記第１の条件を満たす２つの特徴ベクトルを前記多次元特徴行列から削除し、且つ前記結合後の特徴ベクトルを前記多次元特徴行列に追加することにより、前記多次元特徴行列を更新する請求項１記載のデータクラスタリング装置。
【請求項３】
前記第２の条件は、前記更新後の多次元特徴行列における予め指定された次元の特徴ベクトルの数が予め指定されたクラス数に一致することであり、
前記１つ以上の次元は、前記予め指定された次元を含み、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記予め指定された次元の要素グループが分類されたクラスに分類する
請求項１または２に記載のデータクラスタリング装置。
【請求項４】
前記判定手段は、前記結合指数が最小の２つの特徴ベクトルを前記第１の条件を満たす２つの特徴ベクトルとして抽出する請求項１乃至３のいずれかに記載のデータクラスタリング装置。
【請求項５】
前記結合指数は、対応する前記２つの特徴ベクトルの各々の重要度の積が小さく、当該２つの特徴ベクトルのなす角度が小さいものほど小さくなる請求項１乃至４のいずれかに記載のデータクラスタリング装置。
【請求項６】
前記複数の要素グループは第１の要素グループ及び第２の要素グループから構成され、
前記多次元特徴行列は、前記第１の要素グループを行の次元とし、前記第２の要素グループを列の次元とする２次元特徴行列である
請求項１または２に記載のデータクラスタリング装置。
【請求項７】
前記第２の条件は、前記更新後の２次元特徴行列における前記予め指定された次元の特徴ベクトルの数が予め指定されたクラス数に一致することであり、
前記分類結果表は前記予め指定された次元の特徴ベクトルの結合を保持し、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記予め指定された次元の要素グループが分類されたクラスに分類する
請求項６記載のデータクラスタリング装置。
【請求項８】
前記１つ以上の次元は、前記２次元特徴行列の行及び列であり、
前記第２の条件は、前記更新後の２次元特徴行列の行数及び列数の積が予め指定されたクラス数に一致することであり、
前記分類結果表は前記行の特徴ベクトルの結合及び前記列の特徴ベクトルの結合を保持し、
前記出力手段は、前記入力されたデータセットの各データユニットを、当該データユニットに含まれている前記複数の要素グループのうち前記第１の要素グループが分類された行と前記第２の要素グループが分類された列との組み合わせに対応するクラスに分類する
請求項６記載のデータクラスタリング装置。
【請求項９】
前記２次元特徴行列は、前記第１の要素グループを行の次元とし、前記第２の要素グループを列の次元とする行圧縮特徴行列と、前記２次元特徴行列の更新前において前記行圧縮特徴行列に一致する内容の列圧縮特徴行列とから構成され、
前記分類結果表は、前記行圧縮特徴行列の行の各特徴ベクトルをクラスとして保持する第１の分類結果表と前記列圧縮特徴行列の列の各特徴ベクトルをクラスとして保持する第２の分類結果表とから構成され、
前記判定手段は、前記判定処理により、前記多次元特徴行列の前記１つ以上の次元を対象に、前記行圧縮特徴行列及び前記率圧縮特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が前記第１の条件を満たす２つの特徴ベクトルを抽出し、
前記結合手段は、前記第１の条件を満たす２つの特徴ベクトルを結合し、当該第１の条件を満たす２つの特徴ベクトルが行の特徴ベクトルである場合には、前記結合結果に応じて前記行圧縮特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記第１の分類結果表を更新し、当該第１の条件を満たす２つの特徴ベクトルが列の特徴ベクトルである場合には、前記結合結果に応じて前記列圧縮特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記第２の分類結果表を更新し、
前記出力手段は、前記第２の条件を満たした際の前記第１の分類結果表及び前記第２の分類結果表に基づいて前記入力されたデータセットの各データユニットを分類する
請求項６記載のデータクラスタリング装置。
【請求項１０】
入力手段、解析手段、判定手段、結合手段及び記憶手段を備えたデータクラスタリング装置におけるデータクラスタリング方法であって、
前記入力手段が、複数の要素から構成されるデータユニットの集合を含むクラスタリング対象のデータセットを入力するステップと、
前記解析手段が、前記入力されたデータセットを前記記憶手段に格納して、当該入力されたデータセットに基づき、前記複数の要素を１つ以上の要素から構成される複数の要素グループに区分して、当該複数の要素グループの各々を次元とし、その次元の組み合わせに対応するデータユニットの出現回数を成分とする多次元特徴行列を生成し、且つ前記多次元特徴行列の１つ以上の次元の各特徴ベクトルをクラスとして保持する分類結果表を生成して、それぞれ前記記憶手段に格納するステップと、
前記多次元特徴行列の前記１つ以上の次元を対象に、前記判定手段が、前記多次元特徴行列から同一次元同士で２つの特徴ベクトルの組み合わせを逐次抽出して、当該２つの特徴ベクトルの組み合わせ毎にその２つの特徴ベクトルの間の結合指数を計算し、その結合指数が第１の条件を満たす２つの特徴ベクトルを抽出するための判定処理を実行するステップと、
前記結合手段が、前記第１の条件を満たす２つの特徴ベクトルを結合し、その結合結果に応じて前記多次元特徴行列を更新し、且つ当該第１の条件を満たす２つの特徴ベクトルが、結合後の特徴ベクトルに対応するクラスに分類されたことを示すように、前記分類結果表を更新するための結合処理を実行するステップと、
前記更新後の多次元特徴行列が第２の条件を満たすまで、前記判定手段及び前記結合手段が、それぞれ前記判定処理及び前記結合処理を繰り返すステップと、
前記出力手段が、前記第２の条件を満たした際の前記分類結果表に基づいて、前記入力されたデータセットのデータユニット毎にクラス分けしたクラスタリング結果を出力するステップと
を具備するデータクラスタリング方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【公開番号】特開２０１２−１１８５８４（Ｐ２０１２−１１８５８４Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２６４９４２（Ｐ２０１０−２６４９４２）
【出願日】平成２２年１１月２９日（２０１０．１１．２９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１１月２９日（２０１０．１１．２９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]