Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
KERNEL FUNCTION GENERATING METHOD AND DEVICE AND DATA CLASSIFICATION DEVICE
Document Type and Number:
WIPO Patent Application WO/2008/084842
Kind Code:
A1
Abstract:
[PROBLEMS TO BE SOLVED] Kernel functions, the number of which is set in advance, are linearly coupled to generate the most suitable Kernel function for a data classification. [MEANS FOR SOLVING THE PROBLEMS] An element Kernel generating unit (102) generates a plurality of element Kernel functions (k1-kp)by using a plurality of distance functions (distance scales) (d1-dp) prepared in advance. A Kernel optimizing unit (103) generates an integrated Kernel function (K) with which the element Kernel functions (k1-kp) are linearly coupled, determines coupling constants to optimally separate teacher data (z), and optimizes the integrated Kernel function (K). A Kernel component display unit (104) displays each of the element Kernel functions (k1-kp), its coupling constant, and a distance scale corresponding to each of the element Kernel functions on a display device (150).

Inventors:
HIROSE SHUNSUKE (JP)
MORINAGA SATOSHI (JP)
FUJIMAKI RYOHEI (JP)
Application Number:
PCT/JP2008/050242
Publication Date:
July 17, 2008
Filing Date:
January 11, 2008
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
NEC CORP (JP)
HIROSE SHUNSUKE (JP)
MORINAGA SATOSHI (JP)
FUJIMAKI RYOHEI (JP)
International Classes:
G06N3/00; G06F17/30
Foreign References:
JP2006085426A2006-03-30
Other References:
NGUYEN H.-N. ET AL.: "Unified Kernel Function and Its Training Method for SVM", LECTURE NOTES IN COMPUTER SCIENCE, vol. 4232, 2006, pages 792 - 800, XP019046492
SADOHARA K.: "Boolean Function no Gakushu ni Okeru Boolean Kernel o Mochiita Tokucho Sentaku ni Tsuite", INFORMATION PROCESSING SOCIETY OF JAPAN KENKYU HOKOKU, vol. 2004, no. 29, 17 March 2004 (2004-03-17), pages 187 - 192
Attorney, Agent or Firm:
TAKAHASHI, Isamu (Shinoda Bldg.10-7, Higashi Kanda 1-chom, Chiyoda-ku Tokyo 31, JP)
Download PDF:
Claims:
複数の距離尺度ごとに要素カーネル関数を生成するカーネル生成部と、
 前記生成された複数の要素カーネル関数を結合係数で線形結合して生成した統合カーネル関数を生成し、入力する教師データを用いて前記結合係数を決めることで前記統合カーネル関数を最適化するカーネル最適化部とを備えたことを特徴とするカーネル関数生成装置。
前記カーネル最適化部は、前記統合カーネル関数が前記教師データを最適に分離するように前記結合係数を決定する請求項1に記載のカーネル関数生成装置。
記憶装置から距離尺度およびそれに対応する要素カーネル関数の少なくとも一方とそれに対応する結合係数とを読み出して出力装置に出力するカーネル成分出力部を備える請求項1記載のカーネル関数生成装置。
前記複数の距離尺度は、複数の属性を持つデータ間の距離を定義するそれぞれ異なる複数の距離関数である請求項1記載のカーネル関数生成装置。
異なる距離関数は、考慮する属性の種類が相違する請求項4記載のカーネル関数生成装置。
異なる距離関数は、距離の種類が相違する請求項4記載のカーネル関数生成装置。
異なる距離関数は、距離のスケールが相違する請求項4記載のカーネル関数生成装置。
前記教師データは、同じクラスタに属するデータには同じラベルを付加し、異なるクラスタに属するデータには異なるラベルを付加したデータである請求項1記載のカーネル関数生成装置。
前記カーネル最適化部は、異なるクラスタ間の一致度が最小となるように結合係数の値を決定する請求項8記載のカーネル関数生成装置。
前記カーネル最適化部は、異なるラベルを持つデータ間の類似度の和を、等しいラベルを持つデータ間の類似度の和で割った値を最小化する結合係数の値を決定する請求項9記載のカーネル関数生成装置。
 前記統合カーネル関数を用いて教師無データの分類を行う教師無データ分類部を備請求項9記載のカーネル関数生成装置。
統合カーネル関数の結合係数を閾値と比較して閾値以下の結合係数に対応する属性を削除対象属性に決定し、圧縮対象データから前記削除対象属性を削除する次元圧縮を行うデータ圧縮部を備えた請求項9記載のカーネル関数生成装置データ圧縮装置。
統合カーネル関数の結合係数を閾値と比較して閾値以上の結合係数に対応する属性を、前記教師データを複数のグループに分類する原因となる属性であると推定する原因推定部を備えた請求項9記載のカーネル関数生成装置。
前記複数の要素カーネル関数を結合係数で線形結合して統合カーネル関数を生成し、教師データを用いて前記結合係数を決めることにより前記統合カーネル関数を最適化するカーネル関数生成方法。
前記統合カーネル関数が前記教師データを最適に分離するように前記結合係数を決定する請求項13記載のカーネル関数生成方法。
記憶装置から距離尺度およびそれに対応する要素カーネル関数の少なくとも一方とそれに対応する結合係数とを読み出して出力する請求項13記載のカーネル関数生成方法。
コンピュータに、
 複数の距離尺度ごとに要素カーネル関数を生成する機能と、
 前記生成された複数の要素カーネル関数を結合係数で線形結合して統合カーネル関数を生成し、入力する教師データを用いて前記結合係数を決めることで前記統合カーネル関数を最適化する機能とを実行させることを特徴とするカーネル関数生成プログラム。
前記コンピュータに、前記統合カーネル関数が前記教師データを最適に分離するように前記結合係数を決定する機能を実行させる請求項17に記載のカーネル関数生成プログラム。
前記コンピュータに、距離尺度およびそれに対応する要素カーネル関数の少なくとも一方とそれに対応する結合係数とを読み出して出力する機能を実行させる請求項17記載のカーネル関数生成プログラム。
前記複数の距離尺度を、複数の属性を持つデータ間の距離を定義するそれぞれ異なる複数の距離関数として設定した請求項17記載のカーネル関数生成プログラム。
 異なる距離関数は、考慮する属性の種類が相違する請求項20記載のカーネル関数生成プログラム。
 異なる距離関数は、距離の種類が相違する請求項20記載のカーネル関数生成プログラム。
 異なる距離関数は、距離のスケールが相違する請求項20記載のカーネル関数生成プログラム。
 前記教師データは、同じクラスタに属するデータには同じラベルを付加し、異なるクラスタに属するデータには異なるラベルを付加したデータである請求項17記載のカーネル関数生成プログラム。
 前記コンピュータに、異なるクラスタ間の一致度が最小となるように結合係数の値を決定する機能を実行させる請求項24記載のカーネル関数生成プログラム。
 前記コンピュータに、異なるラベルを持つデータ間の類似度の和を、等しいラベルを持つデータ間の類似度の和で割った値を最小化する結合係数の値を決定する機能を実行させる請求項25記載のカーネル関数生成プログラム。
前記コンピュータに、統合カーネル関数を用いて教師無データの分類を行う機能を実行させる請求項17記載のカーネル関数生成プログラム。
前記コンピュータに、統合カーネル関数の結合係数を閾値と比較して閾値以下の結合係数に対応する属性を圧縮対象属性に決定し、圧縮対象データから前記圧縮対象属性を削除する次元圧縮を行う機能を実行させる請求項17記載のカーネル関数生成プログラム。
前記コンピュータに、統合カーネル関数の結合係数を閾値と比較して閾値以上の結合係数に対応する属性を、前記教師データを複数のグループに分類する原因となる属性と推定する機能を実行させる請求項17記載のカーネル関数生成プログラム。
Description:
カーネル関数生成方法および装 、データ分類装置

 本発明は、カーネル関数の生成装置およ 生成したカーネル関数を用いてデータを分 する装置に関する。

 複数の属性を持つデータを分類する手法 一種に、データを或る空間上のベクトルと 做した際のベクトル間の内積(類似度)を定 するカーネル関数を用いる方法がある。

 カーネル関数としては、ガウシアンカー ルや多項式カーネル等が一般的に知られて る。しかし、これら既存のカーネル関数は れぞれ一長一短があるため、目的とするデ タの分類に適さない場合がある。

 そこで、特許文献1では、既存のカーネル 関数を複数線形結合して、所望のデータの分 類に適したカーネル関数を生成している。

 以下、特許文献1に記載されたカーネル関 数の生成方法を説明する。なお、互いに線形 結合される個々のカーネル関数と、線形結合 によって生成されるカーネル関数とを区別す るために、本明細書では、前者を要素カーネ ル関数、後者を統合カーネル関数と呼ぶ。

 特許文献1では、i番目の教師データをz i とすると、まず、数1で示されるガウシアン のカーネル関数を初期生成する。

[数1]
  K(z i ,z j )≡exp(-β|z i -z j | 2 )
 ここで、β=1/(2σ 2 )、σ 2 は入力ベクトル(教師データ)の共分散行列の 大固有値である。

 次に、教師データと所定の評価基準とに基 いて、カーネル関数K(z i ,z j )が一定の基準を満足するかどうかを調べ、 足しない場合、数2に示すように、現在のカ ネル関数K(z i ,z j )に、現在のパラメータβを1.5倍にした別のガ ウシアン型のカーネル関数を加算することに より、統合カーネル関数を更新する。

[数2]
  K(z i ,z j )≡K(z i ,z j )+exp(-β|z i -z j | 2 )

 以上の処理を、所定の評価基準を満足す 統合カーネル関数が生成されるまで、繰り す。

 他方、カーネルに関する他の文献として 論理カーネルというカーネルを定義して{0,1 }のビット列のデータを分類する方法を記載 た特許文献2、カーネルを指定したときの分 平面の設定の仕方に関する技術を記載した 許文献3があるが、いずれもカーネル自体の 最適化には触れていない。

特開2006-085426号公報

特開2003-256801号公報

特開2004-341959号公報

 一般に何れか1つの要素カーネル関数を用 いるよりは、それらの線形結合として表現さ れる統合カーネル関数を用いた方が、より高 い分類性能が実現される。その理由は、複数 の要素カーネル関数の総和に対応する再生核 ヒルベルト空間は、個々の要素カーネル関数 に対応する再生核ヒルベルト空間すべてを包 含するので、個々の要素カーネル関数よりも それらの和の統合カーネル関数の方が高い表 現力を持つからである。従って、特許文献1 提案されているカーネル関数の最適化方法 、所望のデータの分類に適したカーネル関 を生成する上で、それなりに有効な方法と えられる。しかしながら、以下のような課 がある。

 第1の課題は、最適なカーネル関数が得ら れるまでに幾つの要素カーネル関数が線形結 合されるか、事前に決まらないことである。 線形結合される要素カーネル関数の数が増え れば、それだけ最終的な統合カーネル関数が 複雑になり、その分だけ計算コストが増える 。計算コストを或る値以下に抑えるために、 結合数を制限したくても、その結合数の範囲 内でカーネル関数の最適化が行えない。

 第2の課題は、最適な統合カーネル関数を 構成する個々の要素カーネル関数の寄与が不 明なことである。例えば、複数の属性を持つ データ間の距離を定義するそれぞれ異なる複 数の距離尺度として、考慮する属性の種類が 相違する距離尺度を使用し、それらの各距離 尺度に対応する要素カーネルを線形結合した 統合カーネル関数を考えた場合、個々の要素 カーネル関数の寄与の大きさが判明すると、 分類に寄与する属性と寄与しない属性の区別 が可能になり、次元圧縮などに利用できるが 、特許文献1ではその実現は困難である。

 本発明の目的は、事前に設定した数の要 カーネル関数を線形結合してデータ分類に 適な統合カーネル関数を生成することにあ 。

 本発明の別の目的は、最適な統合カーネ 関数を構成する個々の要素カーネル関数の 与を明らかにすることにある。

 本発明の他の目的は、生成した統合カー ル関数を用いて、データ分類、データ圧縮 るいは原因推定を行うことにある。

 前記目的を達成するため、本発明に係る ーネル関数生成装置は、記憶装置から読み した複数の距離尺度ごとに要素カーネル関 を生成し記憶装置に書き込むカーネル生成 と、前記生成された複数の要素カーネル関 を記憶装置から読み出し線形結合して生成 た統合カーネル関数が、教師データを最適 分離するように、その結合係数を決定して 憶装置に書き込むカーネル最適化部とを備 たことを特徴とする。

 本発明に係るカーネル関数生成方法は、 ンピュータを用いてカーネル関数を生成す 方法であって、前記コンピュータが、記憶 置から複数の距離尺度を読み出し、各距離 度ごとに要素カーネル関数を生成し、記憶 置に書き込む第1のステップと、前記コンピ ュータが、記憶装置から読み出した複数の要 素カーネル関数を線形結合して統合カーネル 関数を生成し、該生成した統合カーネル関数 が、記憶装置から読み出した教師データを最 適に分離するように結合係数を決定して記憶 装置に書き込む第2のステップとを含むこと 特徴とする。

 本発明によれば、以下のような効果が奏 れる。

 第1の効果は、事前に設定した数の要素カ ーネル関数を使用して最適な統合カーネル関 数が生成できることである。その理由は、複 数の要素カーネル関数の線形結合が教師デー タを最適に分離するように結合定数を決定す るという方法によって、最適な統合カーネル 関数を生成しているからである。

 第2の効果は、最適な統合カーネル関数に おける個々の要素カーネル関数の寄与が明ら かになることである。その理由は、最適化さ れた統合カーネル関数において、寄与の小さ な要素カーネル関数の結合係数は小さく、寄 与の大きな要素カーネル関数の結合係数は大 きくなるためである。

 次に、本発明の実施の形態について図面 参照して詳細に説明する。

『第1の実施の形態』
 図1を参照すると、本発明の第1の実施の形 にかかるカーネル関数生成装置は、プログ ム制御により動作する処理装置100と、磁気 ィスクや半導体メモリ等で構成された教師 ータ記憶部110、距離関数記憶部120、要素カ ネル記憶部130および統合カーネル記憶部140 、液晶ディスプレイ等で構成された表示装 150と、キーボード等で構成された入力装置16 0とを備えている。

 教師データ記憶部110は、複数の教師データz を記憶する。教師データzは、複数の属性a 1 ,a 2 ,…,a m から構成される。すなわち、教師データzはa 1 ,a 2 ,…,a m を要素とするベクトルデータとして扱える。 複数の教師データのうちのi番目の教師デー をziと記す。また、教師データzには、ラベ 値yが付加されている。ラベル値yは教師デー タzがどのクラスタに属するかを示す。本実 の形態の場合、ラベル値は+1と-1の何れかの をとる。

 例えば、入退室の回数やwebのアクセス容 などを記録したデータを正常な行動に対応 るデータと不正な行動に対応するデータと 分類したい場合、教師データzは入退室の回 数やwebのアクセス容量などを記録したデータ であり、正常な行動に対応するデータには+1 不正な行動に対応するデータには-1という ベルが付与されているものが考えられる。

 距離関数記憶部120は、複数の距離関数d 1 ~d p を記憶する。各距離関数d 1 ~d p は、距離の尺度であり、複数の属性a 1 ,a 2 ,…,a m を持つデータz間の距離を定義する。本実施 形態の場合、それぞれの距離関数d 1 ~d p は、考慮する属性の種類が相違する。具体的 には、距離関数d 1 は属性a 1 の値に関してデータz間の距離を定義する。 た、距離関数d 2 は属性a 2 の値に関してデータz間の距離を定義する。 らに、距離関数の個数は属性数に等しくな ており(即ちm=p)、距離関数d p は属性a m の値に関してデータz間の距離を定義する。

 一般にデータ間の距離には、ユークリッド 離、ミンコフスキー距離、編集距離、ハミ グ距離、発生頻度間の差、発生頻度の対数 失間の差など様々な種類がある。本実施の 態の場合、距離関数d 1 ~d p が示す距離の種類はすべて同じであり、前記 のうちの何れか1つが使用される。ここで、 ータxの発生確率を何らかのモデルで学習し いるとして、その発生確率をp(x)としたとき 、|p(x)-p(y)|をデータxとデータyとの発生頻度 の差、|-log[p(x)]-(-log[p(y)])|を発生頻度の対数 失間の差と呼んでいる。

 また、同じ種類の距離でも、その距離の2倍 や2乗をとると言ったようにスケールを変え ことができるが、本実施の形態の場合、す ての距離関数d 1 ~d p のスケールは同じになっている。

 要素カーネル記憶部130は、距離関数d 1 ~d p のそれぞれに対応して生成された要素カーネ ル関数K 1 ~K p を記憶する。

 統合カーネル記憶部140は、要素カーネル関 K 1 ~K p を線形結合して生成した統合カーネル関数K 記憶する。

 入力装置160は、ユーザからの起動指示な の指示やデータを処理装置100に与えるため 使用される。

 表示装置150は、処理装置100の処理結果や 理過程のデータをユーザに出力するために 用される。ここでは、処理結果等をユーザ 出力する装置の一例として表示装置150を使 しているが、他の種類の出力装置、たとえ プリンタ等であっても良い。

 処理装置100は、教師データ入力部101と、 素カーネル生成部102と、カーネル最適化部1 03と、カーネル成分表示部104とを有する。

 教師データ入力部101は、教師データ記憶 110から複数の教師データzを順に読み出し、 カーネル最適化部103に伝達する。

 要素カーネル生成部102は、距離関数記憶部1 20から複数の距離関数d 1 ~d p を順に読み出し、各距離関数d 1 ~d p に1対1に対応する要素カーネル関数K 1 ~K p を生成し、要素カーネル記憶部130に保存する 。

 カーネル最適化部103は、要素カーネル記憶 130から要素カーネル関数K 1 ~K p を読み出し、それらを線形結合して生成した 統合カーネル関数Kが、教師データzを最適に 離するように、その結合係数を決定し、最 化した統合カーネル関数Kを統合カーネル記 憶部140に保存する。

 カーネル成分表示部104は、統合カーネル記 部140から読み出した統合カーネル関数Kにお ける各要素関数K 1 ~K p の結合係数、距離関数記憶部120から読み出し た距離関数d 1 ~d p 、要素カーネル記憶部130から読み出した要素 カーネル関数K 1 ~K p を表示装置150に表示する。距離関数d 1 ~d p および要素カーネル関数K 1 ~K p の何れか一方は表示を省略しても良い。

 本発明の実施形態にあっては、予め用意 た複数の距離尺度から、複数の要素カーネ 関数を生成し、これらを線形結合した統合 ーネル関数が、教師データを最適に分離す ように結合係数を決定する。結合係数は、 々の要素カーネル関数の重みであり、例え 0以上、1以下の値をとり、その総和が1にな 。要素カーネル関数の個数をp個とすると、 各々の結合係数の値を変化させることによっ て、統合カーネル関数の構造が変化する。そ の取り得る構造の数は、p個の要素カーネル 数を同じ重みで加算する従来方法に比べて 加するため、より最適な統合カーネル関数 生成することが可能になる。また、決定さ た結合係数によって要素カーネル関数の寄 の度合いが明らかになる。

 次に本実施の形態にかかるカーネル関数 成装置の動作を説明する。

 ユーザが、教師データ記憶部110に複数の教 データzを、距離関数記憶部120に複数の距離 関数d 1 ~d p をそれぞれ格納し、入力装置160からカーネル 関数の生成指示を入力すると、処理装置100は 、図2に示される処理の実行を開始する。

 まず、処理装置100の要素カーネル生成部102 、距離関数d 1 ~d p を距離関数記憶部120から入力し、それらに対 応する要素カーネル関数K 1 ~K p を生成して、要素カーネル記憶部130に記憶す る(S101)。距離関数に対応する要素カーネル関 数の生成方法としては、例えば数3に示すよ な方法が挙げられる。

[数3]
  K 1 (z i ,z j )≡exp[-d 1 (z i -z j ) 2 ]
  K 2 (z i ,z j )≡exp[-d 2 (z i -z j ) 2 ]
  …
  K p (z i ,z j )≡exp[-dp(z i -z j ) 2 ]

 ここでは、ガウシアン型のカーネルを用 たが、常に正の値をとるようなカーネル関 であれば、他の種類のカーネル関数を用い ことも可能である。

 次に、カーネル最適化部103は、要素カーネ 関数K 1 ~K p を結合係数c 1 ~c p で線形結合して、数4に示すような統合カー ル関数Kを生成し、統合カーネル記憶部140に 憶する(ステップS102)。そして、教師データ 力部101を通じて入力した教師データzを用い て、結合係数c 1 ~c p を適切に決めることにより、統合カーネル関 数Kを最適化する(ステップS103)。

[数4]
  K(z i ,z j )≡σ n =1 p  c n k n (z i ,z j )

 データを或る空間上のベクトルと見做した のベクトル間の内積(類似度)を定義する関 がカーネル関数で表現される空間をカーネ 空間と呼ぶ。すべての結合係数c 1 ~c p は、カーネル関数が数4で表されるカーネル 間において、ラベルが+1である教師データz クラスタとラベルが-1である教師データzの ラスタとの一致度が最小となるように決め 。一致度としては、大きいほど両者が似て り、小さいほど両者が良く分離されている とを示すような値を用いる。

 例えば、一致度としては数5に示すQのよ な量を用いることができる。

 このQは、異なるラベルを持つデータ間の類 似度の和を、等しいラベルを持つデータ間の 類似度の和で割った商であり、Qの値が小さ ことは、ラベルが+1であるデータのクラスタ とラベルが-1であるデータのクラスタとの類 度が低いことに対応する。この例の場合に 、ラベルが+1であるデータの数をM、ラベル -1であるデータの数をN、要素カーネル関数 数をPとして、数6の2つの条件の下で、数5の Qを最小化するc 1 ~c p を求めれば良い。

[数6]
  σn=1 p  c n =1
  c n ≧0
 ただし、n=1,…,P

 次にカーネル成分表示部104は、カーネル最 化部103で求められた結合係数c 1 ~c p と対応する距離関数d 1 ~d p および要素カーネル関数K 1 ~K p を表示装置150に表示する(S104)。

 次に本実施の形態の効果について説明す 。

 本実施の形態によれば、データ分類に最 な統合カーネル関数を生成することができ かつ、統合カーネル関数を構成する個々の 素カーネル関数の寄与を明らかにすること できる。

 また、データの属性と距離関数d 1 ~d p 、および距離関数d 1 ~d p と要素カーネル関数K 1 ~K p がそれぞれ1対1に対応しているため、要素カ ネル関数の寄与が明らかになることにより データの各属性がデータ分類に与える寄与 調べることができる。

 このため、結合係数c n の値が小さい要素カーネル関数k n に対応する属性a n は、データの分類には小さな寄与しかしない ということなので、その属性a n をデータから削除することでデータの次元圧 縮を行うことができる。また、大きい値を持 つ結合係数c n と対応する距離関数dnおよび要素カーネル関 k n を見ることで、教師データを+1のラベルのク スタと-1のラベルのクラスタとに分類する に大きな寄与をする属性が何であるかを認 でき、それらクラスタを分けている原因の 定を行うことができる。

『第1の実施の形態の変形』
 以上の第1の実施の形態では、距離関数d 1 ~d p は、データz間の距離をデータ内の1つの属性 値に関しての距離として定義したが、デー z内の複数の属性の組み合わせに関しての距 離として定義することもできる。また、距離 関数d 1 ~d p は、上記のように属性の組み合わせ方を変え て作る方法(これを第1の方法と言う)以外に、 以下のような第2、第3の方法も考えられる。

 第2の方法は、距離の種類を変えて作る方法 で、ユークリッド距離、ミンコフスキー距離 、編集距離、ハミング距離、発生頻度間の差 、発生頻度の対数損失間の差などの様々な種 類の距離を用いて、データ間の距離を定義す る。例えば、距離関数d 1 はデータz間のユークリッド距離、距離関数d 2 は教師データz間のミンコフスキー距離を定 するといった如きものである。

 第3の方法は、スケールのとり方を変えて 作る方法で、第1または第2の方法で定義した 離の1倍を距離とするか2倍を距離とするか 若しくは2乗を距離とするか3乗を距離とする か、といったスケールの採り方を変えて距離 を定義する。

 また、第1、第2および第3の方法を組み合 せた方法で距離関数を作ることも可能であ 。

『第2の実施の形態』
 図3を参照すると、本発明の第2の実施の形 にかかるデータ分類装置は、プログラム制 により動作する処理装置200と、磁気ディス や半導体メモリ等で構成された教師データ 憶部110、距離関数記憶部120、要素カーネル 憶部130、統合カーネル記憶部140、教師無デ タ記憶部210および分類結果記憶部220と、液 ディスプレイ等で構成された表示装置150と キーボード等で構成された入力装置160とを えている。

 教師データ記憶部110、距離関数記憶部120 要素カーネル記憶部130、統合カーネル記憶 140、表示装置150および入力装置160は、第1の 実施の形態と同じものである。

 教師無データ記憶部210は、分類対象とす 複数の教師無データ211を記憶する。教師無 ータ211は、教師データzと同じ型(属性の数 各属性の内容の定義が同じ)のデータであり かつ、+1、-1のラベルが付いていないデータ である。

 分類結果記憶部220は、教師無データ211を 類した結果221を記憶する。

 処理装置200は、第1の実施の形態における ものと同一の教師データ入力部101、要素カー ネル生成部102、カーネル最適化部103およびカ ーネル成分表示部104に加えてさらに、教師無 データ入力部201と、教師無データ分類部202と 、分類結果表示部203とを有する。

 教師無データ入力部201は、教師無データ 憶部210から教師無データ211を順に読み出し 、教師無データ分類部202に伝達する。

 教師無データ分類部202は、統合カーネル 憶部140から最適化された統合カーネル関数K を読み出し、この統合カーネル関数Kに基づ て、教師無データ211を分類し、その分類結 221を分類結果記憶部220に保存する。

 分類結果表示部203は、分類結果記憶部220 ら分類結果221を読み出し、表示装置150に表 する。

 次に本実施の形態にかかるデータ分類装置 動作を説明する。教師データ入力部101、要 カーネル生成部102、カーネル最適化部103お びカーネル成分表示部104によって、距離関 d 1 ~d p から教師データzを用いて最適な統合カーネ 関数Kを生成する際の動作は第1の実施の形態 と同じなので、その説明は省略する。生成さ れた統合カーネル関数Kを用いて教師無デー 211を分類する際の動作は以下のようになる

 教師無データ分類部202は、統合カーネル 憶部140から統合カーネルKを読み出し、また 教師無データ入力部201を通じて教師無データ 記憶部210から教師無データ211を読み出し、教 師無データの2クラス分類問題を解き、その 果を分類結果221として保存する。

 ここで行う2クラス分類は、カーネル関数 を用いて行える手法を用いる。用いる手法と しては、教師無の分類手法と教師付の分類手 法とがあり、本実施の形態では、教師無の分 類手法を用いる。教師無の分類手法としては 、例えばカーネルk-means法が挙げられる。教 無の分類手法では、教師無データ211が2つの ループに分けられる。

 分類結果表示部203は、分類結果記憶部220 ら分類結果221を読み出し、表示装置150に表 する。

 次に本実施の形態の効果を説明する。

 本実施の形態によれば、第1の実施の形態 と同様にして生成された最適化された統合カ ーネル関数Kを用いて、教師無データ211を分 することができる。

 また本実施の形態によれば、教師無の分 手法を用いているので、データ分類時に教 データzを必要としない利点がある。

『第3の実施の形態』
 図4を参照すると、本発明の第3の実施の形 にかかるデータ分類装置は、処理装置200の 師無データ分類部202が教師無データ分類部20 4に置き換えられている点で、図3に示した第2 の実施の形態にかかるデータ分類装置と相違 する。

 教師無データ分類部204は、統合カーネル 憶部140から読み出した最適化された統合カ ネル関数Kと、教師データ入力部101を通じて 教師データ記憶部110から読み出した教師デー タzと、教師無データ入力部201を通じて教師 データ記憶部210から読み出した教師無デー 211とに基づいて、教師無データ211を分類し その分類結果221を分類結果記憶部220に保存 る。すなわち、教師無データ分類部204は、 師無データの2クラス分類問題を教師付の分 手法を用いて解く点で、第2の実施の形態の 教師無データ分類部202と相違する。

 教師付の分類手法としては、例えばSVM(Sup port Vector Machine)やカーネル判別分析が挙げ れる。教師付の分類手法では、教師無デー 211が+1のラベルの付いたデータのグループと -1のラベルの付いたデータのグループに分け れる。

 次に本実施の形態の効果を説明する。

 本実施の形態によれば、第1の実施の形態 と同様にして生成された最適化された統合カ ーネル関数Kを用いて、教師無データ211を分 することができる。

 また本実施の形態によれば、教師付の分 手法を用いているので、教師無データ211を+ 1のラベルの付いたデータのグループと-1のラ ベルの付いたデータのグループに分類するこ とができる。

『第4の実施の形態』
 図5を参照すると、本発明の第4の実施の形 にかかるデータ圧縮装置は、プログラム制 により動作する処理装置300と、磁気ディス や半導体メモリ等で構成された教師データ 憶部110、距離関数記憶部120、要素カーネル 憶部130、統合カーネル記憶部140、圧縮対象 ータ記憶部310および圧縮結果記憶部320と、 晶ディスプレイ等で構成された表示装置150 、キーボード等で構成された入力装置160と 備えている。

 教師データ記憶部110、距離関数記憶部120 要素カーネル記憶部130、統合カーネル記憶 140、表示装置150および入力装置160は、第1の 実施の形態と同じものである。

 圧縮対象データ記憶部310は、圧縮対象と る複数のデータ311を記憶する。圧縮対象デ タ311は、教師データzと同じ型(属性の数と 属性の内容の定義が同じ)のデータである。+ 1、-1のラベルが付いているか否かは問わない 。

 圧縮結果記憶部320は、圧縮対象データ311 圧縮した結果321を記憶する。

 処理装置300は、第1の実施の形態における ものと同一の教師データ入力部101、要素カー ネル生成部102、カーネル最適化部103およびカ ーネル成分表示部104に加えてさらに、圧縮対 象データ入力部301と、データ圧縮部302と、圧 縮結果表示部303とを有する。

 圧縮対象データ入力部301は、圧縮対象デ タ記憶部310から圧縮対象データ311を順に読 出して、データ圧縮部302に伝達する。

 データ圧縮部302は、統合カーネル記憶部140 ら最適化された統合カーネル関数Kの結合係 数c 1 ~c p を読み出し、予め設定された閾値と比較する ことにより削除する属性を決定し、この決定 した属性を圧縮対象データ311から削除するこ とで次元圧縮を行い、その結果321を圧縮結果 記憶部320に保存する。

 圧縮結果表示部303は、圧縮結果記憶部320 ら圧縮結果321を読み出し、表示装置150に表 する。

 次に本実施の形態にかかるデータ圧縮装置 動作を説明する。教師データ入力部101、要 カーネル生成部102、カーネル最適化部103お びカーネル成分表示部104によって、距離関 d 1 ~d p から教師データzを用いて最適な統合カーネ 関数Kを生成する際の動作は第1の実施の形態 と同じなので、その説明は省略する。生成さ れた統合カーネル関数Kを用いて圧縮対象デ タ311の次元圧縮を行う際の動作は以下のよ になる。

 データ圧縮部302は、まず、統合カーネル関 Kの結合係数c 1 ~c p を予め設定された閾値と比較することにより 、削除する属性を決定する。第1の実施の形 で説明したように、教師データzの各属性a 1 ,a 2 ,…,a m と、各距離関数d 1 ,d 2 ,…,d p と、要素カーネル関数k 1 ,k 2 ,…,k p と、結合係数c 1 ,c 2 ,…,c p とが1対1の関係にある場合、閾値より小さな 合係数に対応する属性は一意に定まる。今 閾値より小さな結合係数が例えばc 1 ,c 2 の2つであるとすると、a 1 ,a 2 の2つの属性が削除対象になる。

 次にデータ圧縮部302は、圧縮対象データ 力部301を通じて圧縮対象データ記憶部310か 圧縮対象データ311を順に読み出し、圧縮対 データ311から削除対象の属性を削除したデ タを圧縮結果321として圧縮結果記憶部320へ 存する。

 圧縮結果表示部303は、圧縮結果記憶部320 ら圧縮結果321を読み出し、表示装置150に表 する。

 次に本実施の形態の効果を説明する。

 本実施の形態によれば、第1の実施の形態 と同様にして生成された最適化された統合カ ーネル関数Kを用いて、圧縮対象データ311の 元圧縮を行うことができる。

『第5の実施の形態』
 図6を参照すると、本発明の第5の実施の形 にかかる原因推定装置は、プログラム制御 より動作する処理装置400と、磁気ディスク 半導体メモリ等で構成された教師データ記 部110、距離関数記憶部120、要素カーネル記 部130、統合カーネル記憶部140および推定結 記憶部410と、液晶ディスプレイ等で構成さ た表示装置150と、キーボード等で構成され 入力装置160とを備えている。

 教師データ記憶部110、距離関数記憶部120 要素カーネル記憶部130、統合カーネル記憶 140、表示装置150および入力装置160は、第1の 実施の形態と同じものである。

 推定結果記憶部410は、教師データ記憶部1 10に記憶されている教師データzを、+1のラベ の付いたデータのグループと-1のラベルの いたデータのグループとの2つのグループに 類する原因となった属性の推定結果411を記 する。

 処理装置400は、第1の実施の形態における ものと同一の教師データ入力部101、要素カー ネル生成部102、カーネル最適化部103およびカ ーネル成分表示部104に加えてさらに、原因推 定部401と推定結果表示部402とを有する。

 原因推定部401は、統合カーネル記憶部140 ら最適化された統合カーネル関数Kの結合係 数c1~cpを読み出し、予め設定された閾値と比 することにより、教師データzを2つのグル プに分類する原因となった属性を決定し、 の決定した属性を推定結果411として推定結 記憶部410に保存する。

 推定結果表示部402は、推定結果記憶部410 ら推定結果411を読み出し、表示装置150に表 する。

 次に本実施の形態にかかる原因推定装置の 作を説明する。教師データ入力部101、要素 ーネル生成部102、カーネル最適化部103およ カーネル成分表示部104によって、距離関数d 1 ~d p から教師データzを用いて最適な統合カーネ 関数Kを生成する際の動作は第1の実施の形態 と同じなので、その説明は省略する。生成さ れた統合カーネル関数Kを用いて原因の推定 行う際の動作は以下のようになる。

 原因推定部401は、統合カーネル関数Kの結合 係数c 1 ~c p を予め設定された閾値と比較し、閾値以上の 結合係数に対応する属性を原因属性とする。 第1の実施の形態で説明したように、教師デ タzの各属性a 1 ,a 2 ,…,a m と、各距離関数d 1 ,d 2 ,…,d p と、要素カーネル関数k 1 ,k 2 ,…,k p と、結合係数c 1 ,c 2 ,…,c p とが1対1の関係にある場合、閾値より大きな 合係数に対応する属性は一意に定まる。原 推定部401は、推定結果411を推定結果記憶部4 11へ保存する。

 推定結果表示部402は、推定結果記憶部410 ら推定結果411を読み出し、表示装置150に表 する。

 次に本実施の形態の効果を説明する。

 本実施の形態によれば、第1の実施の形態 と同様にして生成された最適化された統合カ ーネル関数Kを用いて、教師データzを2つのグ ループに分類する原因となった属性を推定す ることができる。

 さらに、本発明の他の実施形態について 明する。本発明のの他の実施形態に係るカ ネル関数生成装置は、記憶装置から読み出 た複数の距離尺度ごとに要素カーネル関数 生成し記憶装置に書き込むカーネル生成部 、前記生成された複数の要素カーネル関数 記憶装置から読み出し線形結合して生成し 統合カーネル関数が、教師データを最適に 離するように、その結合係数を決定して記 装置に書き込むカーネル最適化部とを備え 構成としてもよいものである。

 前記カーネル関数生成装置において、記 装置から距離尺度およびそれに対応する要 カーネル関数の少なくとも一方とそれに対 する結合係数とを読み出して出力装置に出 するようにしてもよいものである。また、 記複数の距離尺度は、複数の属性を持つデ タ間の距離を定義するそれぞれ異なる複数 距離関数であることが望ましい。異なる距 関数は、考慮する属性の種類が相違するこ が望ましい。異なる距離関数は、距離の種 が相違することが望ましい。異なる距離関 は、距離のスケールが相違することが望ま い。

 前記教師データは、同じクラスタに属す データには同じラベルを付加し、異なるク スタに属するデータには異なるラベルを付 したデータであることが望ましい。前記カ ネル最適化部は、異なるクラスタ間の一致 が最小となるように結合係数の値を決定す ようにしてもよい。前記カーネル最適化部 、異なるラベルを持つデータ間の類似度の を、等しいラベルを持つデータ間の類似度 和で割った値を最小化する結合係数の値を 定するようにしてもよい。

 生成された統合カーネル関数を用いて教 無データの分類を行う教師無データ分類部 備えるようにしてもよいものである。統合 ーネル関数の結合係数を閾値と比較して閾 以下の結合係数に対応する属性を削除対象 性に決定し、圧縮対象データから前記削除 象属性を削除する次元圧縮を行うデータ圧 部を備えるようにしてもよい。統合カーネ 関数の結合係数を閾値と比較して閾値以上 結合係数に対応する属性を、前記教師デー を複数のグループに分類する原因となる属 であると推定する原因推定部を備えるよう してもよい。

 本発明の他の実施形態に係るカーネル関 生成方法は、コンピュータを用いてカーネ 関数を生成する方法であって、前記コンピ ータが、記憶装置から複数の距離尺度を読 出し、各距離尺度ごとに要素カーネル関数 生成し、記憶装置に書き込む第1のステップ と、前記コンピュータが、記憶装置から読み 出した複数の要素カーネル関数を線形結合し て統合カーネル関数を生成し、該生成した統 合カーネル関数が、記憶装置から読み出した 教師データを最適に分離するように結合係数 を決定して記憶装置に書き込む第2のステッ とを含む構成としてもよいものである。

 前記コンピュータが、記憶装置から距離 度およびそれに対応する要素カーネル関数 少なくとも一方とそれに対応する結合係数 を読み出して出力装置に出力する第3のステ ップを含むようにしてもよい。

 以上本発明の実施の形態について説明し が、本発明は以上の実施の形態にのみ限定 れず、その他各種の付加変更が可能である また、本発明のカーネル関数生成装置、デ タ分類装置、データ圧縮装置、原因推定装 は、その有する機能をハードウェア的に実 することは勿論、コンピュータとプログラ とで実現することができる。プログラムは 磁気ディスクや半導体メモリ等のコンピュ タ可読記録媒体に記録されて提供され、コ ピュータの立ち上げ時などにコンピュータ 読み取られ、そのコンピュータの動作を制 することにより、そのコンピュータを前述 た各実施の形態におけるカーネル関数生成 置、データ分類装置、データ圧縮装置、原 推定装置として機能させ、前述した処理を わせる。

以上、実施形態(及び実施例)を参照して本 発明を説明したが、本願発明は上記実施形 (及び実施例)に限定されるものではない。 願発明の構成や詳細には、本願発明のスコ プ内で当業者が理解し得る様々な変更をす ことができる。

 この出願は2007年1月12日に出願された日本 出願特願2007-004306を基礎とする優先権を主張 、その開示の全てをここに取り込む。

本発明の第1の実施の形態にかかるカー ネル関数生成装置のブロック図である。 本発明の第1の実施の形態にかかるカー ネル関数生成装置の動作を示すフローチャー トである。 本発明の第2の実施の形態にかかるデー タ分類装置のブロック図である。 本発明の第3の実施の形態にかかるデー タ分類装置のブロック図である。 本発明の第4の実施の形態にかかるデー タ圧縮装置のブロック図である。 本発明の第5の実施の形態にかかる原因 推定装置のブロック図である。

符号の説明

100…処理装置
101…教師データ入力部
102…要素カーネル生成部
103…カーネル最適化部
104…カーネル成分表示部
110…教師データ記憶部
120…距離関数記憶部
130…要素カーネル記憶部
140…統合カーネル記憶部
150…表示装置
160…入力装置