(57)【特許請求の範囲】
【請求項１】
複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
乱数系列を用いてクラスタを初期化して前記処理対象記憶手段から取得した前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング手段でクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算手段と、
前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の相加平均、相乗平均、調和平均のいずれかが最小となるクラスタリング結果群を選択する選択手段と、
を有することを特徴とするデータマイニング装置。
【請求項２】
複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
乱数系列を用いてクラスタを更新するデータ集合を前記処理対象記憶手段から取得してクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング手段でクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算手段と、
前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の和が最小となるクラスタリング結果群を選択する選択手段と、を有することを特徴とするデータマイニング装置。
【請求項３】
複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
前記処理対象記憶手段の前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング結果記憶手段に格納されている、前記クラスタリング手段を繰り返し行った前回までのクラスタリング結果についてクラスタラベルの出現を表す確率変数とデータの特徴を表す任意の要素の出現の有無を表す確率変数との相互情報量を計算し、該相互情報量の和を求める相互情報量計算手段と、
前記相互情報量の和に基づいて、データの特徴に重み付けする重み付け手段と、
重み付けされた特徴を用いてクラスタリングを行う重みクラスタリング手段と、
を有することを特徴とするデータマイニング装置。
【請求項４】
複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
前記処理対象記憶手段の前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング結果記憶手段に格納されている、前記クラスタリング手段を繰り返し行った前回までのクラスタリング結果についてデータの特徴を表す任意の要素に関するクラスタ間分散とクラスタ内分散の比を計算し、その和を求める分散比計算手段と、
前記クラスタ間分散と前記クラスタ内分散の比の和に基づいてデータの特徴に重み付けする重み付け手段と、
重み付けされた特徴を用いてクラスタリングする重みクラスタリング手段と、
を有することを特徴とするデータマイニング装置。
【請求項５】
複数の観点でデータ集合をクラスタリングするデータマイニング方法であって、
クラスタリング手段が、乱数系列を用いてクラスタを初期化して処理対象記憶手段から取得した前記データ集合をクラスタリングし、クラスタリング結果記憶手段に格納するクラスタリングステップと、
相互情報量計算手段が、前記クラスタリングステップでクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算ステップと、
選択手段が、前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の相加平均、相乗平均、調和平均のいずれかが最小となるクラスタリング結果群を選択する選択ステップと、
を行うことを特徴とするデータマイニング方法。
【請求項６】
複数の観点でデータ集合をクラスタリングするデータマイニング方法であって、
クラスタリング手段が、乱数系列を用いてクラスタを更新するデータ集合を処理対象記憶手段から取得してクラスタリングし、クラスタリング結果記憶手段に格納するクラスタリングステップと、
相互情報量計算手段が、前記クラスタリングステップでクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算ステップと、
選択手段が、前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の和が最小となるクラスタリング結果群を選択する選択ステップと、
を行うことを特徴とするデータマイニング方法。
【請求項７】
複数の観点でデータ集合をクラスタリングするデータマイニング方法であって、
クラスタリング手段が、処理対象記憶手段から取得したデータ集合をクラスタリングし、クラスタリング結果記憶手段に格納するクラスタリングステップと、
相互情報量計算手段が、前記クラスタリング結果記憶手段に格納されている、前記クラスタリングステップを繰り返し行った前回までのクラスタリング結果についてクラスタラベルの出現を表す確率変数とデータの特徴を表す任意の要素の出現の有無を表す確率変数との相互情報量を計算し、該相互情報量の和を求める相互情報量計算ステップと、
重み付け手段が、前記相互情報量の和に基づいて、データの特徴に重み付けする重み付けステップと、
重みクラスタリング手段が、重み付けされた特徴を用いてクラスタリングを行う重みクラスタリングステップと、
を行うことを特徴とするデータマイニング方法。
【請求項８】
複数の観点でデータ集合をクラスタリングするデータマイニング方法であって、
クラスタリング手段が、処理対象記憶手段の前記データ集合をクラスタリングし、クラスタリング結果記憶手段に格納するクラスタリングステップと、
分散比計算手段が、前記クラスタリング結果記憶手段に格納されている前記クラスタリングステップを繰り返し行った前回までのクラスタリング結果についてデータの特徴を表す任意の要素に関するクラスタ間分散とクラスタ内分散の比を計算し、その和を求める分散比計算ステップと、
重み付け手段が、前記クラスタ間分散と前記クラスタ内分散の比の和に基づいてデータの特徴に重み付けする重み付けステップと、
重みクラスタリング手段が、重み付けされた特徴を用いてクラスタリングする重みクラスタリングステップと、
を行うことを特徴とするデータマイニング方法。
【請求項９】
コンピュータを、
請求項１乃至４記載のいずれか１項に記載のデータマイニング装置の各手段として機能させるためのデータマイニングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データマイニング装置及び方法及びプログラムに係り、特に、何らかの観点（軸）で似通っているデータをクラスタとしてまとめるクラスタリングのためのデータマイニング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
クラスタリングとは、似通っているデータを一括りのクラスタとして纏めることであり、データマイニング手法の一つである（例えば、非特許文献１，２参照）。クラスタリング手法には、階層的な手法、非階層的（分割最適化）手法などがある。いずれの手法においてもある共通したクラスタラベル集合から一つ（ハードクラスタリングの場合）あるいは確率的にいくつかのクラスタラベルを選び、各データに付与することと言える。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】神嶌敏弘、"データマイニング分野のクラスタリング手法（１）"，人工知能学会誌１８巻１号、2003年１月．
【非特許文献２】神嶌敏弘、"データマイニング分野のクラスタリング手法（２）" 人工知能学会誌１８巻１号、2003年３月．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術においては、データに付与するクラスタラベル集合は一つと考えている。しかし、一般にデータを分割する観点（軸）は複数ある。例えば、映像には｛映画、邦画、ドラマ、…｝という軸と｛ドキュメンタリ、サスペンス、アドベンチャー、…｝が考えられる。それぞれの軸は異なる切り口を示しており、データ解析において有用な情報である。クラスタリングは教師なし学習であるゆえ、予めクラスタにこのような名前は付いていないが、発見すべき分割軸が上記のように複数あることは多い。このような時に、従来技術では、データを分割すべき複数の軸、及び、それぞれの軸で見たときにデータが属するクラスタを発見することはできない。
【０００５】
本発明は、上記の点に鑑みなされたもので、互いに独立な複数の観点（軸）でデータ集合をクラスタリングでき、データを分割する複数の軸、及びそれぞれの軸で見たときにデータが属するクラスタを発見することが可能なデータマイニング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の課題を解決するため、本発明（請求項１）は、複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
乱数系列を用いてクラスタを初期化して前記処理対象記憶手段から取得した前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング手段でクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算手段と、
前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の相加平均、相乗平均、調和平均のいずれかが最小となるクラスタリング結果群を選択する選択手段と、
を有することを特徴とする。
【０００７】
本発明（請求項２）は、複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
乱数系列を用いてクラスタを更新するデータ集合を前記処理対象記憶手段から取得してクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング手段でクラスタリングされた任意の２つのクラスタリング結果から、それぞれの結果毎にクラスタラベルの出現を表す確率変数に基づく相互情報量を計算する相互情報量計算手段と、
前記クラスタリング結果記憶手段から、異なる乱数系列を用いたクラスタリング結果を取得して互いの相互情報量の和が最小となるクラスタリング結果群を選択する選択手段と、を有することを特徴とする。
【０００８】
本発明（請求項３）は、複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
前記処理対象記憶手段の前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング結果記憶手段に格納されている、前記クラスタリング手段を繰り返し行った前回までのクラスタリング結果についてクラスタラベルの出現を表す確率変数とデータの特徴を表す任意の要素の出現の有無を表す確率変数との相互情報量を計算し、該相互情報量の和を求める相互情報量計算手段と、
前記相互情報量の和に基づいて、データの特徴に重み付けする重み付け手段と、
重み付けされた特徴を用いてクラスタリングを行う重みクラスタリング手段と、
を有することを特徴とする。
【０００９】
本発明（請求項４）は、複数の観点でデータ集合をクラスタリングするデータマイニング装置であって、
処理対象のデータ集合が格納された処理対象記憶手段と、
クラスタリング結果を格納するクラスタリング結果記憶手段と、
前記処理対象記憶手段の前記データ集合をクラスタリングし、前記クラスタリング結果記憶手段に格納するクラスタリング手段と、
前記クラスタリング結果記憶手段に格納されている、前記クラスタリングステップを繰り返し行った前回までのクラスタリング結果についてデータの特徴を表す任意の要素に関するクラスタ間分散とクラスタ内分散の比を計算し、その和を求める分散比計算手段と、
前記クラスタ間分散と前記クラスタ内分散の比の和に基づいてデータの特徴に重み付けする重み付け手段と、
重み付けされた特徴を用いてクラスタリングする重みクラスタリング手段と、
を有することを特徴とする。
【発明の効果】
【００１０】
上記のように本発明によれば、ベクトルで表されるデータをクラスタリングすることにより、そのクラスに大きく寄与している要素を求め、異なる要素の重みを上げて分類し、２つの分類が互いに独立な事象となるようにすることで、互いに独立な複数の観点（軸）でデータ集合をクラスタリングでき、データを分割する複数の軸、及びそれぞれの軸で見たデータが属するクラスタを発見することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第１の実施の形態におけるデータマイニング装置のハードウェア構成図である。
【図２】本発明の第１の実施の形態におけるデータマイニング処理のフローチャートである。
【図３】本発明の第１の実施の形態における特徴ｍの出現有無についてのクロス表である。
【図４】本発明の第２の実施の形態における２つのクラスタリング結果のクロス表である。
【図５】本発明の第３の実施の形態における特徴の重みを変更することによる効果の説明図である。
【発明を実施するための形態】
【００１２】
以下図面と共に、本発明の実施の形態を説明する。
【００１３】
本発明の基本的な考え方は、複数の観点（軸）によるクラスタリング結果が互いに独立になるようにすることで、異なる観点（軸）を発見することである。すなわち、任意の２つのクラスタリング結果を見たとき、それぞれの結果ごとにクラスタラベルの出現を表す確率変数Ｘ，Ｙを定義して同時確率分布と周辺確率分布とを考えたとき、この２つの確率変数の相互情報量をゼロあるいはなるべく小さくするようにクラスタリングを行うということである。
【００１４】
図１は、本発明の一実施の形態におけるデータマイニング装置のハードウェア構成を示す。
【００１５】
同図に示すデータマイニング装置１００は、ＣＰＵ１１、メモリ１２、ディスプレイ１３、キーボード１４、処理プログラム１５、処理値対象記憶部１６、オペレーティングシステム（ＯＳ）１７、クラスタリング結果記憶部１８から構成される。処理値対象記憶部１６、クラスタリング結果記憶部１８は、ハードディスク等の記憶媒体である。
【００１６】
処理対象記憶部１６には、クラスタリング対象であるデータ集合が格納されている。
【００１７】
クラスタリング結果記憶部１８は、処理プログラム１５によってクラスタリングされた結果が格納される。
【００１８】
また、メモリ１２には、キーボード１４から入力された値（クラスタリングを行う観点（軸）の数、クラスタ数）、処理プログラム１５で処理された中間データが格納される。
【００１９】
本実施の形態では、各特長の重みをクラスタリング結果記憶部１８に格納されているクラスタリング結果への依存度に応じて変化させてからクラスタリングを行う。
【００２０】
以下に、処理プログラム１５をCPU１１で実行する処理を説明する。
【００２１】
図２は、本発明の一実施の形態におけるデータマイング処理のフローチャートである。
【００２２】
ステップ１０１）  まず、CPU１１は、処理プログラム１５により、初期設定を行う。クラスタリング対象となるデータを処理対象記憶部１６から読み込む。データは確率分布Ｐ＝｛ｐ1，…，ｐM｝で表されるものとする。ここで、Mは確率変数の取り得る値の数である。クラスタリングを行う観点（軸）の数がキーボード１４から入力されると、これをRと表し、また、クラスタ数がキーボード１４から入力されると、これをKと表す。
【００２３】
ステップ１０２）  クラスタリング結果の数をrと定義し、値を０に初期化する。
【００２４】
ステップ１０３）  データの特徴を表す確率変数の取り得る値m＝（1，…，M）毎に既に求められたクラスタへの依存度合いを表す変数Vmを定義し、値を０に初期化する。また、ｍ番目（1≦m≦M）の特徴が出現の有無（１／０）を表す確率変数Zmを定義する。
【００２５】
ステップ１０４）  処理対象記憶部１６に格納されている特徴m（＝１，…，M）とクラスタリング結果記憶部１８に格納されている既クラスタリング結果ｊ(＝１，…，r)の全組合せについて、以下の処理を行う。もし、クラスタリング結果記憶部１８に既クラスタリング結果がない（ｒ＝０）の場合は、ステップ１０５に移動する。ｊ番目のクラスタリング結果におけるクラスタラベルの出現を表す出現確率変数Xｊを定義し、２つの確率変数ZmとXjについてのクロス表を図３のように作成し、メモリ１２に格納する。ここで、クロス表とは、異なる系統のクラスタラベルの組合せ毎のクラスタラベルの出現個数である。同図中に示しているように、（Zm＝1,X＝Ck）の時の値は、
【００２６】
【数１】
0005613615.tif 000002
である。このクロス表により、この２つの確率変数について相互情報量I(Zm；Xj)を計算してその和をとる。すなわち、
【００２７】
【数２】
0005613615.tif 000003
という処理を行う。
【００２８】
なお、クラスタリング対象であるデータ集合の各データの特徴がx＝｛x1，…，xm，…，xM｝のように実数ベクトルで表されるときのVmの計算は下記のようにしてもよい。
【００２９】
あるクラスタリング結果において、クラスがCkに含まれるデータ数がNkで平均ベクトルがμｋ、クラスタ数画K、全ベクトルの平均がμと表されるとき、第m次元目の要素についてのクラスタ間分散とクラスタ内分散の比
【００３０】
【数３】
0005613615.tif 000004
を求める。この値が大きいほどｍ次元目の特徴がクラスタの分離に寄与している。すなわち、依存していると言える。既に実施したクラスタリングがｒ個ある場合、これらのクラスタリング結果のクラスタに対する依存度Vmを
【００３１】
【数４】
0005613615.tif 000005
とする。ここで
【００３２】
【数５】
0005613615.tif 000006
はｊ番目のクラスタリング結果におけるｍ次元目の特徴についてのクラスタ間分散とクラスタ内分散の比である。
【００３３】
ステップ１０５）  ステップ１０４の繰り返しにより得られた依存度Vmを用い、全てのデータについて、重み付け処理を行う。具体的には、各データの確率分布Pの各確率値を、
【００３４】
【数６】
0005613615.tif 000007
としてから、確率値の和
【００３５】
【数７】
0005613615.tif 000008
が１になるような係数を掛ける。
【００３６】
ステップ１０６）  必要な重み付けが施された確率分布を用い、クラスタ数をKとするクラスタリングを実施する。クラスタリングアルゴリズムとしては、文献１「内山俊郎、江田毅晴、別所克人、内山匡、田邊勝義"競合学習を用いたエントロピー最小基準クラスタリング法"、電子情報通信学会 信学技報, vol. 110, no. 27, PRMU2010-27, pp. 139-144, 2010年5月」が示すエントロピー基準の競合学習を用いてもよい。クラスタリング処理後、クラスタリング結果の数rに１を足す。
【００３７】
ステップ１０７）  終了チェックを行う。クラスタリング結果の数ｒがRに達していれば終了し、達していなければステップ１０３に移行する。
【実施例】
【００３８】
以下、図面と共に本発明の実施例を説明する。
【００３９】
以下の実施例におけるデータマイニング装置の構成は図１と同様である。
【００４０】
［第１の実施例］
以下に、処理プログラム１５の処理を説明する。
【００４１】
本実施例では、処理プログラム１５において、異なる乱数系列を用いることで異なるクラスタリング結果が得られるクラスタリング手法を用い、多数の乱数系列によりクラスタリングを行い、クラスタリング結果記憶部１８に格納されたクラスタリング結果集合から、互いに独立な（あるいは独立に近い）クラスタリング結果群を選択する。
【００４２】
２つのクラスタリング結果が独立な度合いは以下のようにして評価する。
【００４３】
ある２つのクラスタリングで得られたクラスタ（２系統）を｛ｘ１，…，ｘK1}、｛ｙ1，…，ｙK2｝とすると、各データには、それぞれの系統のクラスタラベルが付与されているので、異なる系統のクラスタラベルの組合せ毎に出現個数をカウントすることができる。その結果を図４に示す。図４は、２つのクラスタリング結果のクロス表に示す。同図においてＮ（）はカウント数を示す。それぞれの系統ごとにクラスタラベルの出現を表す確率変数Ｘ，Ｙを定義し、図４のクロス表より、各マスのカウント数の全カウント数に対する割合から同時確率分布関数ｐ（ｘ，ｙ）（ｘ∈ＵＸ，ｙ∈ＵＹ）、各行、各列のカウント数の和の全カウント数に対する割合から周辺確率分布関数ｐ（ｘ）、ｐ（ｙ）を求める。ここで、ＵＸ，ＵＹは、それぞれ確率変数ＸとＹが取り得る値の集合である。すると、２つの確率変数Ｘ，Ｙの相互情報量I（X，Y）は、
I(X；Y)＝H(X) + H(Y) − H(X,Y)                （６）
と書ける。この値が０であればこれら確率分布は独立であり、小さいほど独立に近いといえる。ここでＨ（）は確率分布の平均情報量（エントロピー）であり、確率分布Ｘのエントロピーは、
【００４４】
【数８】
0005613615.tif 000009
と書くことができる。
【００４５】
例えば、２０個のクラスタリング結果を生成し、そこから３つの結果を選択する場合、組合せは20Ｃ3（1140）個あり、それぞれの組合せにおいて、全ペア、すなわち、３通りの相互情報量I(X,Y)（式６）を計算して相加平均を求め、それを最も小さくする組合せを選択する。相加平均の代わりに、相乗平均、調和平均などを用いてもよい。
【００４６】
［第２の実施例］
本実施の形態におけるハードウェア構成は実施の形態と同様である。
【００４７】
本実施例では、１個目のクラスタリングから順に実施し、２個目以降のクラスタリングでは、そこまでに実施したクラスタリング結果のクラスタに対して依存度合いが低い特徴を選択、あるいは、重みを増して用いる方法である。
【００４８】
図５は、本発明の第２の実施例における特徴の重みを変更することによる効果の説明図である。
【００４９】
図５（ａ）は、クラスタリング結果記憶部１８から読み出された１個目のクラスタリング（第１系統のクラスタリング）の様子を表している。同図から分かるように、１番目の特徴の違いが顕著であり、これに基づいて縦方向のデータが類似しているとしてクラスタリングされている。例えば、「洋画、邦画、ドラマ」のようなクラスタが形成されるとする。次に、このクラスタに依存度が低い特徴の重みを増す処理を行う。同図の例では、２番目の特徴がクラスタと無関係（依存度が低い）であるので、この特徴の重みを増したのが図５（ｂ）である。今度は、２番目の特徴の違いが強調されており、これに基づいてクラスタリングすると横方向のデータが類似しているとしてクラスタリングが行われ、クラスタリング結果記憶部１８に格納される。例えば、「ドキュメンタリー、サスペンス、アドベンチャー」のように、第１系統のクラスタとは異なる観点のクラスタが形成される。
【００５０】
なお、本発明は上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５１】
１１  ＣＰＵ
１２  メモリ
１３  ディスプレイ
１４  キーボード
１５  処理プログラム
１６  処理対象記憶部
１７  オペレーティングシステム（ＯＳ）
１８  クラスタリング結果記憶部
１００  データマイニング装置
【図１】
0005613615.tif 000010
【図２】
0005613615.tif 000011
【図３】
0005613615.tif 000012
【図４】
0005613615.tif 000013
【図５】
0005613615.tif 000014