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

[第1の実施の形態]
 図1を参照すると、本発明の第1の実施の形� �に関わるデータ分類装置100は、外れ値分類� �能付データ分類部110と、分類結果出力部120� �、記憶装置130と、分離面集合記憶装置140と� �備えている。データ分類装置100は、パーソ� �ルコンピュータなどのコンピュータによっ� �実現することができる。その場合、外れ値� �類機能付データ分類部110と分類結果出力部12 0とは、記憶装置に格納されたプログラムをCP Uなどの処理装置が読み出してそのプログラ� �に既述された手順に従って実行動作を行う� �とにより実現される。

 このデータ分類装置100は、分類対象デー� ��150を入力し、分類対象データ150が複数の分� ��面によって1以上のクラス領域(既知クラス� �域)とそれ以外の未知クラス領域とに分離さ� ��た特徴空間内のどの領域に属するかを計算� ��ることによって、分類対象データ150を既知� ��どのクラスに分類すべきか、または外れ値� ��分類すべきかを推定し、その推定結果を分� ��結果160として出力する。

 分類対象データ150は、分類が未知のベクト� ��データである。今、分類対象データ150に含� ��れる属性の数をdとし、分類対象データ150を 式(1)のようにd次元のベクトルとして表現す� �。式(1)において、右辺の括弧の右肩に付し� �記号´は転置を示す(記号´の代わりに記号 ^T を使う場合もある)。また、x ^j は分類対象データ150のj番目の属性を表し、� �数値であっても良いしシンボル値であって� �よい。また、xから特徴空間への写像をφと� �、xの特徴空間における像をφ(x)と表す。以� �で、分類対象データといった場合には、分� �対象データと特徴空間における像のどちら� �指してもかまわないものとする。

 分離面集合記憶装置140は、特徴空間を1以 上の既知クラスにそれぞれ対応する1以上の� �ラス領域とそれ以外の未知クラス領域とに� �離する複数の分離面を規定する情報を記憶� �る。分離面は、図2に示される超平面A~Dのよ� ��に特徴空間上で平面を成すものであっても� ��いし、図3に示される超球面E~Hのように特徴 空間上で球面を成すものであっても良く、そ の他、超円柱面、超錐面などであっても良い 。ただし、図2に示される互いに平行な超平� �A~D、図3に示される同心の超球面E~Hのように� ��複数の分離面は互いに交差しないことが必� ��である。また、図2ではクラス1の領域が2つ� ��超平面A,Bにより、クラス2の領域が2つの超� �面C,Dにより、図3におけるクラス3の領域が2� �の超球面E,Fにより、クラス4の領域が2つの超 球面G,Hにより、それぞれ境界が定められてい る。このように、既知の1クラス当たり2個以� ��の分離面によって各既知クラスの境界が定� ��られている。

 分離面集合記憶装置140に記憶する情報は、� ��離面を特定する情報であればどのような情� ��であっても良い。例えば、特徴空間のi番目 の基底関数をψiとすると、特徴空間における 分離面は基底関数を利用して記述することが 可能である。例えば、分離面がσw _i ψiφ(x)+b=0で表される超平面の場合には、基底 ψiおよび基底の重みw _i 、切片bを、超平面を規定する情報として記� �すればよい。この際、基底ψiは全ての超平� �で共通のため、例えば図4のように、重みw _i と切片bを表形式で各超平面毎に記憶し、基� �ψiは共通に記憶しておくことが可能である� �また、超球面の場合には、中心をc、半径をr とすると、|φ(x)-c| ² =rと表され、また中心cは特徴空間内の点のた め、c=σw _i ψiと表される。そのため、重みw _i と半径rを図5のように表形式で各超球面毎に� ��存し、基底ψiは共通に記憶しておくことが� ��能である。また、基底関数に関しては、任� ��の基底関数を利用することが可能であるが� ��頻繁に利用される基底としては、例えばxの 元空間における基底やカーネル関数などが挙 げられる。その場合、基底同士の内積が定義 されているものとする(カーネル関数とは、� �定の条件を満たす任意の基底関数に関する� �積を与える関数)。

 記憶装置130には、分類対象データ150と分� ��面集合記憶装置140に記憶された複数の分離� ��との位置関係から、分類対象データ150を分� ��するためのルールが記憶されている。例え� ��図2に示されるように複数の超平面によって データを分類する場合、記憶装置130には、例 えば「超平面Aより負の方向→外れ値へ分類� �、「超平面Cより正の方向かつ超平面Dより負 の方向→クラス2へ分類」などといったルー� �が記憶されている。また、図3に示されるよ� ��に複数の超球面によってデータを分類する� ��合、記憶装置130には、例えば「超球面Eより 内側→外れ値へ分類」、「超球面Gより外側� �つ超球面Hより内側→クラス4へ分類」などと いったルールが記憶されている。この例では 超平面と超球面の場合を説明したが、前述し たように分離面はその二つに限定されるもの ではない。分離面としてその他の形状の超曲 面を利用することも可能であるし、また異な る種類の分離面を組み合わせることも可能で ある。なお、記憶装置130には外れ値分類機能 付データ分類部110によって判定された分類結 果を記憶しておくことも可能である。

 外れ値分類機能付データ分類部110は、分� ��対象データ150および分離面集合記憶装置140� ��記憶された複数の分離面に関する情報を読� ��込み、分類対象データ150と複数の分離面と� ��位置関係を計算する。分離面は前述したよ� ��に、例えば超平面、超球面、超円柱面、超� ��面などである。位置関係とは、例えば超平� ��の場合にはデータが超平面上、正の側、負� ��側のどの位置にあるかであり、超球面の場� ��には超球面上、超球面の内側、超球面の外� ��のどの位置にあるかのことである。この位� ��関係からデータを分類するルールが前述し� ��ように記憶装置130に保存されており、外れ� ��分類機能付データ分類部110は、位置関係お� ��び分類ルールを利用してデータを分類する� ��

 分類結果出力部120は、外れ値分類機能付� ��ータ分類部110で判定された分類結果を、外� ��値分類機能付データ分類部110から直接受け� ��るか、記憶装置130に記憶された分類結果を� ��み出して出力する。出力先は、データ分類� ��置100に接続されたディスプレイ等の出力装� ��であっても良いし、ネットワークを介して� ��続された出力装置や端末装置であっても良� ��。

 次に本実施の形態に関わるデータ分類装� ��の全体の動作を説明する。

 図6を参照すると、データ分類装置100の外 れ値分類機能付データ分類部110は、d個の属� �を含む分類対象データ150を入力し(S100)、ま� �分離面集合記憶装置150から複数の分離面の� �報を入力する(S101)。

 次に、外れ値分類機能付データ分類部110は� ��入力された分類対象データ150および複数の� ��離面の情報を利用して、分類対象データ150� ��複数の分離面との位置関係を計算する(S102)� ��計算は、例えば図2および図4の超平面Aを例� ��すると、データxに対して、σw _i ^A ψiφ(x)+b ^A を計算し、その値の位置関係(0、正、負によ� ��て、それぞれ超平面A上、超平面Aより正側� �超平面Aより負側のいずれかに分類される)を 判定することができる。また図3および図5の� ��球面Eの場合でも、位置関係(データxに対し� ��|φ(x)-σw _i ^E ψi| ² がr ^E と等しいか、大きいか、小さいかによって、 それぞれ超球面E上、超球面Eより外側、超球� ��Eより内側のいずれかに分類される)を判定� �ることが可能である。

 次に、外れ値分類機能付データ分類部110� ��、記憶装置130に記憶されている分類ルール� ��読み込み、分類対象データ150がどのクラス� ��属するかを判定する(S103)。そして、分類結� ��出力部120は、外れ値分類機能付データ分類� ��110の分類結果を出力する(S104)。

 データ分類に関しては、既知のクラス数� ��1つ乃至は複数であり、1つの場合は外れ値� �類を行うデータ分類装置として機能する。

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

 本実施の形態によれば、識別と外れ値分� ��を同じ手順で同時に行うことができる。そ� ��理由は、特徴空間を1以上の既知クラスにそ れぞれ対応する1以上のクラス領域とそれ以� �の未知クラス領域とに分離する複数の分離� �と分類対象データ150との位置関係を計算し� �分類対象データ150が1以上のクラス領域とそ� ��以外の未知クラス領域とのうちのどの領域� ��属するかを計算することによって、分類対� ��データ150の分類を決定するためである。

 また本実施の形態によれば、信頼性の高� ��データ分類を行うことができる。その理由� ��、それぞれの既知クラスは2以上の分離面に よって境界が定められているため、1つの分� �面によって境界を定める場合と比較して、� �ータ分類の信頼性がより高まるからである� �

[第2の実施の形態]
 図7を参照すると、本発明の第2の実施の形� �に関わるデータ分類装置200は、図1に示した� ��1の実施の形態に関わるデータ分類装置100と 比較して、分離面集合記憶装置140に代えて分 離面集合記憶装置210を有する点、および分離 面集合計算装置220が接続されている点で相違 する。

 分離面集合計算装置220は、1以上の既知ク ラスに分類されている複数の学習データおよ びその分類に基づいて複数の分離面を計算す る。複数の分離面は、特徴空間を1以上の既� �クラスにそれぞれ対応する1以上のクラス領� ��とそれ以外の未知クラス領域とに分離する� ��1以上のクラス領域の各々は、この複数の分 離面のうちの互いに交差しない2以上によっ� �、他の領域と分離される。また、分離面集� �記憶装置210は、分離面集合計算装置220で計� �された複数の分離面を規定する情報を記憶� �る装置である。

 分離面集合計算装置220は、図8に示される ように、分離面集合最適化部221と記憶装置222 と分離面集合出力部223とを備える。分離面集 合最適化部221は、学習データ記憶装置224から 学習用のデータを入力する。分離面集合出力 部223は、最適化された分離面集合225を出力す る。

 学習データ記憶装置224には、分類対象デー� ��150と同じ属性を有するデータx _i と、データx _i の属するクラスラベルy _i の組の集合が記憶されている。ここで、iは� �習データのインデックスとし、Nを所定の整� ��とし、学習データはi=1,…,Nまで入力される� ��する。

 分離面集合最適化部221は、学習データに� ��する分類誤差の最小化、分離面集合の複雑� ��の最小化、および各クラス領域の大きさの� ��小化を同時に最適化する複数の分離面を計� ��する。利用する複数の分離面に関しては、� ��前に候補となる分離面の組み合わせを記憶� ��置222へ記憶しておき、最適化時に記憶装置2 22からそれらの候補を読み込んで利用しても� ��い。または任意の分離面の組み合わせに対� ��て最適化を行うことにより最適な分離面集� ��を選択してもよい。

 分類誤差は、任意の誤差を利用すること� ��可能であり、例としては誤分類データ数、� ��分類データに対する2乗損失、誤分類データ に対する絶対値損失、誤分類データに対する ヒンジ損失などが挙げられる。

 分離面集合の複雑性は、任意の複雑性の基� ��を利用することが可能である。例としては� ��j番目の分離面をf _j とすると、f _j のL1複雑性|f _j |、L2複雑性|f _j | ² 、L∞複雑性|f _j | ^∞ などが挙げられる。ここで、f _j のL1複雑性、L2複雑性、L∞複雑性とは、関数( 分離面)のノルム(大きさ)を表す量である。ベ クトルv=(v ₁ ,…,v _n )に関して言えば、L1複雑性とはσ|v _i |であり、L2複雑性とはσv _i ² であり、L∞複雑性とはmax|v _i |となる。

 各クラス領域の大きさは、例えば図2に示 されるクラス1の場合には超平面Aと超平面Bと で挟まれた領域の大きさ、例えば図3に示さ� �るクラス3の場合には超球面Eと超球面Fとで� �まれた領域の大きさのことである。それら� �大きさを表すために任意の基準を利用する� �とが可能である。

 一般的には分離面の複雑性を大きくする� ��ど学習データに対する分類誤差は小さくな� ��が、これは学習データに対して過学習をし� ��いるため未知の分類データに対する分類精� ��は低くなってしまう。したがって、分離面� ��複雑性を小さく保ったまま分類誤差を小さ� ��する分離面を学習するために、両者の和(さ らに各クラス領域の大きさの基準を加えた和 )が最も小さくなる分離面集合を選択する。

 次に本実施の形態の動作を説明する。

 本実施の形態の動作は、分離面集合計算� ��置220による分離面の計算処理と、この計算� ��れた分離面を利用した分類対象データ150の� ��類処理とに大別される。

 分離面集合計算装置220による分離面の計� ��処理では、分離面集合最適化部221によって� ��学習データ記憶装置224から分類が既知の学� ��データを読み込み、この学習データに対す� ��分類誤差の最小化、分離面集合の複雑性の� ��小化、および各クラス領域の大きさの最小� ��を同時に最適化する複数の分離面を計算し� ��、記憶装置222に記憶する。次に、分離面集� ��出力部223によって、記憶装置222から複数の� ��離面を規定するデータを読み出し、分離面� ��合225として分離面集合記憶装置210に記憶す� ��。

 本実施の形態のデータ分類装置200の動作� ��、図1に示した第1の実施の形態に関わるデ� �タ分類装置100の動作と基本的に同じである� �

 このように本実施の形態によれば、第1の 実施の形態と同様の効果が得られると同時に 、分離面集合計算装置220によって計算した最 新の複数の分離面で分離面集合記憶装置210に 記憶された複数の分離面を置き換えることが でき、学習データの充実にあわせて性能の向 上を図ることができる効果がある。

[第3の実施の形態]
 図9を参照すると、本発明の第3の実施の形� �に関わるデータ分類装置300は、図7に示した� ��2の実施の形態に関わるデータ分類装置200と 比較して、分離面集合記憶装置210に代えて超 平面集合記憶装置310を有する点、および分離 面集合計算装置220に代えて超平面集合計算装 置320が接続されている点で相違する。

 超平面集合計算装置320は、1以上の既知ク ラスに分類されている複数の学習データおよ びその分類に基づいて、特徴空間を1以上の� �知クラスにそれぞれ対応する1以上のクラス� ��域とそれ以外の未知クラス領域とに分離す� ��複数の超平面を計算する。1以上のクラス領 域の各々は、この複数の分離面のうちの互い に交差しない2以上によって、他の領域と分� �される。また、超平面集合記憶装置310は、� �平面集合計算装置320で計算された複数の超� �面を規定する情報を記憶する装置である。

 図10を参照すると、超平面集合計算装置32 0は、超平面集合最適化部321と、記憶装置222� �、数理計画問題計算装置322と、超平面集合� �力部323とを備える。超平面集合最適化部321� �、学習データ記憶装置224から学習用のデー� �を入力する。超平面集合出力部323は、最適� �された超平面集合324を出力する。すなわち� �超平面集合計算装置320は、データ分類のた� �に複数の互いに平行な超平面を計算する。� �って、本実施の形態のデータ分類装置300で� �、図2に示されるように平行する超平面によ� ��て各クラスの領域を区切ることによってデ� ��タ分類を実現する。

 以下で、超平面の具体的な計算手順に関� ��て、幾つかの例をもとに説明を行う。

 学習データ記憶装置224から入力されたデー� ��に関するクラスのインデックスをj=1,…,C(C� �1以上の整数)とする。以下では、x _i ^j をj番目のクラスに属するi番目のデータとし� ��各クラスに属する学習データの数をN _j とする。特徴空間における超平面は、或る重 みwおよび切片bに関して、w ^T φ(x)+b=0を満たす点の集合として記述される。 ここで、f(x)=w ^T φ(x)としておく。今、超平面は平行なため、� ��みwは共通であるから、wおよびj番目のクラ� ��の超平面に対する切片b _j ⁺ およびb _j ^- が、超平面集合最適化部321によって最適化さ れる。

 なお、φ(x)が線形の場合、特徴空間は、� �習データ(および分類対象データ)と同じ次元 数のベクトル空間になる。φ(x)が非線形の場� ��、特徴空間は、学習データ(および分類対象 データ)を非線形変換したベクトルデータと� �じ次元数のベクトル空間になる。

 最適化のための基準として、以下の3条件、
(a)分類誤差最小化
(b)f(x)の複雑性最小化
(c)各既知クラス領域の大きさ最小化
 を同時に最適化することによって、wおよび 各jに対するb _j ⁺ およびb _j ^- を計算する。

 上記3条件に加えて、
(d)原点周囲の未知領域の大きさ最大化
(e)各クラスの領域が重ならない(あるいは各� �ラス領域の重なりの最小化)
 の1つないしは双方をも同時に最適化するこ とによってwおよび各jに対するb _j ⁺ およびb _j ^- を計算しても良い。

 (c)の基準に関しては、超平面に対して各� ��知クラスの領域の大きさを最小化する。こ� ��によって、各クラス領域を両面からタイト� ��押さえることが要請される。

 (d)の基準は各超平面に対して原点付近が� ��知クラスの領域になることを要請する。こ� ��は、学習データの張る空間の補空間のデー� ��は未知クラスに属すると考えられるが、該� ��ータが学習データの張る空間へ射影された� ��合、必ず原点に射影されるためである。例� ��して3次元の場合を考える。学習データが全 てa(1,0,0)+b(0,1,0)と表されるように、1次元目と 2次元目のみに分布していると仮定する。こ� �場合、3次元目に分布する未知クラスのデー� ��c(0,0,1)は1次元目と2次元目の成分が0のため� �データの張る空間に対しては必ず原点に射� �される。

 (a)から(e)の複数の基準を同時に最適化す� ��具体的な例を幾つか挙げる。

[C=1の場合]
 学習データ記憶装置224から入力されたデー� ��に関するクラスが唯一の場合には、互いに� ��行な2つの超平面が計算される。そのような 2つの超平面は、例として(2)式に示される最� �化問題を解くことで求められる。

 (2)式では(a)から(d)の基準が、(a)第2項、(b)第 1項、(c)第3項、(d)第4項として表現されている 。(e)の基準に関しては1クラスの場合には考� �される必要がない。ν ₀ およびν ₁ はどの基準に重きをおくかを決定するパラメ ータで、0より大きく1より小さい実数値であ� ��。(2)式によって計算される2つの超平面は、 図11に示されるような超平面となる。以下、( 2)式における目的関数および制約条件につい� ��説明する。

 式(2)の目的関数における第1項は、最適化の 基準(b)のために必要な項であり、複雑性とし てL2複雑性を採用すると、f(x)のL2複雑性はこ� ��ように計算される。第2項は、最適化の基準 (a)のために必要な項であり、ξ _i ¹⁺ とξ _i ^1- は誤差を表すためのスラック変数である。第 3項は、最適化の基準(c)のために必要な項で� �り、b ₁ ^- ≦w’φ(x _i ¹ )≦b ₁ ⁺ のため、b ₁ ^- -b ₁ ⁺ を小さくすることによって既知クラスを包む 領域を最小化している。第4項は、最適化の� �準(d)のために必要な項である。原点周辺の� �知領域の大きさを最大化することは、すな� �ち既知領域を原点から遠ざけることを意味� �る。そのため、既知領域の中心(b ₁ ^- +b ₁ ⁺ )/2を原点から遠ざけることで(d)の基準が達成 される。

 式(2)の制約条件における、w’φ(x _i ¹ )-b ₁ ⁺ ≦ξ _i ¹⁺ 、w’φ(x _i ¹ )-b ₁ ^- ≧-ξ _i ^1- 、ξ _i ¹⁺ ≧0、ξ _i ^1- ≧0は、次の意味を持つ。すなわち、図11に示 されるように、クラス1に属するデータはb ₁ ⁺ とb ₁ ^- の間に入る必要がある(つまり、b ₁ ^- ≦w’φ(x _i ¹ )≦b ₁ ⁺ である)が、入らなかった分は誤差としてカ� �ントする。b ₁ ⁺ ≧b ₁ ^- は、b ₁ ^- ≦w’φ(x _i ¹ )≦b ₁ ⁺ のために必要な制約条件である。b ₁ ^- ≧0は、原点領域を未知領域とするために必� �な制約条件である。つまり、b ₁ ^- ≧0という制約条件がないと、b ₁ ^- ≦0≦b ₁ ⁺ となり得るためである。なお、b ₁ ^- ≧0の代わりに、b ₁ ⁺ ≦0でも良い。

 (2)式は標準的な凸2次計画問題であり、超 平面集合最適化部321および数理計画問題計算 装置322によって最適解が計算される。

 なお、特徴空間が非線形で、特徴空間へ� ��写像φが明示的に与えられていない場合に� �、一般には(2)式を直接解くことができない� �しかし、特徴空間における内積がカーネル� �数として定義されている場合には、(2)式の� �対問題を解くことで超平面が計算される。

 (2)式の双対問題は(3)式のようにラグラン� ��ュの未定乗数を導入することによって、(4)� ��となる。

 ラグランジュの未定乗数は、α _i ¹⁺ ,α _i ^1- ,μ ₀ ,μ ₁ ,γ _i ¹⁺ ,γ _i ^1- ,δである。ただし、k(x _i ¹ ,x _i ’ ¹ )=φ(x _i ¹ ) ^T φ(x _i ’ ¹ )は特徴空間での内積であり、双対問題ではφ (x)がどのような関数であっても、その内積φ( x _i ¹ ) ^T φ(x _i ’ ¹ )さえ計算できれば解くことが可能である。(4 )式で表される双対問題も凸2次計画問題であ� ��。

 双対問題に対して重みwは、(5)式と表される ため、f(x)=w ^T φ(x)は(6)式で表される。相対問題を解いた場� ��には、記憶する内容が図4のw _i とbの組でなくて、α _i とbの組になる。

[C=2の場合]
 学習データ記憶装置224から入力されたデー� ��に関するクラスが2つの場合、各クラスに対 して平行な2つの超平面が計算される。その� �うな複数の超平面は、例として(7)式に示さ� �る最適化問題を解くことで計算される。

 (7)式では(a)から(e)の基準が、(a)第2項、(b)第 1項、(c)第3項、(d)第4項として表現されている 。(e)の基準に関してはb ₁ ^- ≧b ₂ ⁺ が自動的に満たされるため、明示的に考慮す る必要はない。ν ₀ およびν ₁ およびν ₂ はどの基準に重きをおくかを決定するパラメ ータで、0より大きく1より小さい実数値であ� ��。(7)式によって計算される複数の超平面は� ��図12に示されるような超平面となる。以下� �(7)式における目的関数および制約条件につ� �て説明を補足する。

 式(7)の目的関数における第4項は、最適化の 基準(e)のために必要な項であり、絶対値記号 が付いている理由は、j=2はb ₂ ^- ,b ₂ ⁺ ともに負になるためである。式(7)の制約条件 における0≧b ₂ ⁺ は、2つあるクラスの双方とも原点0を跨がな� ��ようにするための制約条件である。つまり� ��b ₁ ^- ≦0≦b ₁ ⁺ やb ₂ ^- ≦0≦b ₂ ⁺ という状況を避けるためには、次の3通りが� �えられる。両方のクラスが正側(つまり、0≦ b ₁ ^- かつ0≦b ₂ ^- )、両方のクラスが負側(つまり、b ₁ ⁺ ≦0かつb ₂ ⁺ ≦0)、各クラスが原点0を挟んで互いに反対側 。式(7)では最後のケースを採用している。

 C=1の場合と同様に、(7)式は凸2次計画問題 である。また、(2)式から(4)式を得たのと同様 の手順で双対問題を導出し、双対問題を解く ことで最適化を行うことも可能である。(7)式 の双対問題も凸2次計画問題となる。

[C≧3の場合]
 学習データ記憶装置224から入力されたデー� ��に関するクラスが3以上の一般の場合に、平 行な複数の超平面の組を計算するには、入力 されたクラスの任意の2つの組み合わせに対� �てC=2の場合の最適化を実施し、得られた複� �の超平面の組を利用して多数決をとること� �考えられる。

 また例えば(8)式に示される最適化問題を� ��くことで、平行な複数の超平面の組を計算� ��ることもできる。

 (8)式では(a)から(e)の基準が、(a)第2項、(b) 第1項、(c)第3項、(d)第4項として表現されてい る。(e)の基準に関してはψに関する制約条件� ��よって表現されている。以下、(8)式におけ� ��目的関数および制約条件について説明を補� ��する。

 式(2)および式(7)で示した1クラスおよび2� �ラスの場合には、特徴空間におけるクラス� �領域の順序が決まっていたため、各クラス� �領域を原点から遠ざけるという方式で、基� �(e)を達成することができた。しかし、一般� �多クラスになるとクラスの領域の順序をど� �ようにすれば良いかは自明でない。一つの� �として、それを全ての組み合わせで解く方� �が考えられるが、計算量が多くなる欠点が� �る。(8)式による最適化は、組み合わせを考� �ること無しに、自動的に順序が最も良いも� �に決定されるようにしている。

 そのために、まず、図13に示されるように� �原点周りの未知クラスの領域がb ₀ ^- とb ₀ ⁺ に挟まれた領域とし、そのための制約条件と してb ₀ ⁺ ≧0、0≧b ₀ ^- を置き、目的関数の第4項で、その領域を最� �化している(第4項の符号はマイナスで、目的 関数が最小化だから最大化になる)。

 次に、既知クラスの領域(および原点周りの 未知クラス領域)が図14に示すようにオーバー ラップしてはいけないための制約が必要にな る。このような制約は、各クラスの領域の順 序と原点との位置関係が明示的に決まってい る場合には、b ₁ ^- ≦0、b ₂ ^- ≧0、b ₂ ⁺ ≦b ₃ ^- というように明示的に順序として重複しない 制約を書くことが可能である。全組み合わせ を考える場合にはこのような制約条件をつけ るが、(8)式は順序が事前にわからないことを 前提としているため、そのような制約は書け ない。そこで、b _j ^- ≧b _k ⁺ -ψ _jk ^- 、b _j ⁺ ≦b _k ^- +ψ _jk ⁺ 、ψ _jk ^- ψ _jk ⁺ =0および、b _j ^- ≧b ₀ ⁺ -ψ _j0 ^- 、b ₀ ^- ≦b _j ⁺ +ψ _j0 ⁺ 、ψ _j0 ^- ψ _j0 ⁺ =0という制約条件により、既知クラスの領域( および原点周りの未知クラス領域)がオーバ� �ラップしてはいけないための制約を課して� �る。

 また、b _j ^- ≧b _k ⁺ -ψ _jk ^- に関して、b _j ^- ≧b _k ⁺ が成り立つ場合(つまり、クラスjがクラスkよ り正の方向にある)には、ψ _jk ^- =0になる。逆に、b _j ⁺ ≦b _k ^- +ψ _jk ⁺ に関して、b _j ⁺ ≦b _k ^- が成り立つ場合(つまり、クラスjがクラスkよ り負の方向にある)には、ψ _jk ⁺ =0になる。クラス間の重複がないためには、b _j ^- ≧b _k ⁺ またはb _j ⁺ ≦b _k ^- とならなくてはならないので、ψ _jk ^- =0またはψ _jk ⁺ =0が成り立つ必要がある。したがって、ψ _jk ^- ψ _jk ⁺ =0という制約によって、各クラスの重複がな� ��という制約を課すことが可能である。

 ψ _j0 ⁺ ,ψ _j0 ^- に関する制約条件は、原点周りの領域と既知 クラスの領域に関する同様の制約を表す。

 次に本実施の形態の動作を説明する。

 本実施の形態の動作は、超平面集合計算� ��置320による超平面の計算処理と、この計算� ��れた超平面を利用した分類対象データ150の� ��類処理とに大別される。

 超平面集合計算装置320による超平面の計� ��処理では、超平面集合最適化部321によって� ��学習データ記憶装置224から分類が既知の学� ��データを読み込み、この学習データに対す� ��分類誤差の最小化、超平面集合の複雑性の� ��小化、および各クラス領域の大きさの最小� ��を同時に最適化する複数の超平面を計算し� ��、記憶装置222に記憶する。次に、超平面集� ��出力部323によって、記憶装置222から複数の� ��平面を規定するデータを読み出し、超平面� ��合324として超平面集合記憶装置310に記憶す� ��。

 本実施の形態のデータ分類装置300の動作� ��、図1に示した第1の実施の形態に関わるデ� �タ分類装置100の動作と基本的に同じである� �

 このように本実施の形態によれば、第1の 実施の形態と同様の効果が得られると同時に 、超平面集合計算装置320によって計算した最 新の複数の超平面で超平面集合記憶装置310に 記憶された複数の超平面を置き換えることが でき、学習データの充実にあわせて性能の向 上を図ることができる効果がある。

[第4の実施の形態]
 図15を参照すると、本発明の第4の実施の形� ��に関わるデータ分類装置400は、図7に示した 第2の実施の形態に関わるデータ分類装置200� �比較して、分離面集合記憶装置210に代えて� �球面集合記憶装置410を有する点、および分� �面集合計算装置220に代えて超球面集合計算� �置420が接続されている点で相違する。

 超球面集合計算装置420は、1以上の既知ク ラスに分類されている複数の学習データおよ びその分類に基づいて、特徴空間を1以上の� �知クラスにそれぞれ対応する1以上のクラス� ��域とそれ以外の未知クラス領域とに分離す� ��複数の超球面であって、1クラス当たり2個� �上で且つ互いに同心の複数の超球面を計算� �る装置である。また、超球面集合記憶装置41 0は、超球面集合計算装置420で計算された複� �の超球面を規定する情報を記憶する装置で� �る。

 図16を参照すると、超球面集合計算装置42 0は、超球面集合最適化部421と、記憶装置222� �、数理計画問題計算装置422と、超球面集合� �力部423とを備え、学習データ記憶装置224か� �学習用のデータを入力し、最適化された超� �面集合424を出力する。すなわち、超球面集� �計算装置420は、データ分類のために複数の� �心の超球面を計算する。従って、本実施の� �態のデータ分類装置400では、図3に示される� ��うに同心の超球面によって各クラスの領域� ��区切ることによってデータ分類を実現する� ��

 以下で、超球面の具体的な計算手順に関� ��て、幾つかの例をもとに説明を行う。

 学習データ記憶装置224から入力されたデー� ��に関するクラスのインデックスをj=1,…,Cと� ��る。以下では、x _i ^j をj番目のクラスに属するi番目のデータとし� ��各クラスに属する学習データの数をN _j とする。超球面の中心をc、半径をrとすると� ��超球面は|φ(x)-c| ² =rと書ける。今、超球面は同心であるため、� ��心cは各クラスで共通であるから、cおよびj� ��目のクラスに対する外側の半径r _j ⁺ および内側の半径r _j ^- が超球面集合最適化部421によって最適化され る。

 最適化のための基準としては、以下の3つの 条件を同時に最適化することによって、cお� �び各jに対するr _j ⁺ およびr _j ^- を計算する。
(a’)分類誤差最小化
(b’)cの複雑性最小化
(c’)各既知クラス領域の大きさ最小化。

 なお、上記以外にさらに、
(d’)原点周囲の未知領域の大きさ最大化
(e’)各クラスの領域が重ならない
 の1つないしは双方をも同時に最適化するこ とによってcおよび各jに対するr _j ⁺ およびr _j ^- を計算しても良い。

 (a’)から(e’)の複数の基準を同時に最適� ��する具体的な例は、例えば式(9)が挙げられ� ��。式(9)はクラスが幾つでも適用可能である� ��、クラスの順序が判っていることが前提と� ��っている。

 式(9)によって計算される超球面集合の一� ��を図17に示す。式(9)は目的関数および制約� �件の凹部分と凸部分が加算の形になってい� �ため、Concave-Convex Procedure(文献8参照)などを� ��用して効率的に最適解を計算することが可� ��である。以下、式(9)における目的関数およ� ��制約条件について説明する。

 式(9)の目的関数における第1項は、クラス jの領域の外半径-内半径という形なので、最� ��化の基準(c’)のために必要な項である。第2 項は、式(7)の第2項に相当し、最適化の基準(a ’)のために必要な項である。第3項は、最適� ��の基準(d’)のために必要な項である。その� ��由は次の通りである。

 まず、制約条件のc ² ≦min{r _j ^- } ² から、原点は一番小さい超球面の内側にある ことが制約として課される。c ² は原点と超球面の中心との距離で、min{r _j ^- } ² は超球面の中心と一番内側の超球面との距離 (つまり半径)であるためである。つまり、一� ��内側の球の内部が、原点周りの未知領域に� ��る。したがって、min{r _j ^- } ² を大きくすることによって、基準(d’)が達成 される。

 基準(b’)は式(9)の目的関数の中では明示的� ��は含まれておらず、制約条件の中に暗黙的� ��含まれている。基準(e’)は、r _j ⁺ ≧r _j ^- とr _j+1 ^- ≧r _j ⁺ によって制約されている。

 次に本実施の形態の動作を説明する。

 本実施の形態の動作は、超球面集合計算� ��置420による超球面の計算処理と、この計算� ��れた超球面を利用した分類対象データ150の� ��類処理とに大別される。

 超球面集合計算装置420による超球面の計� ��処理では、超球面集合最適化部421が、学習� ��ータ記憶装置224から分類が既知の学習デー� ��を読み込み、この学習データに対する分類� ��差の最小化、超球面集合の複雑性の最小化� ��および各クラス領域の大きさの最小化を同� ��に最適化する複数の超球面を計算して、記� ��装置222に記憶する。次に、超球面集合出力� ��323が、記憶装置222から複数の超球面を規定� ��るデータを読み出し、超球面集合424として� ��球面集合記憶装置410に記憶する。

 本実施の形態のデータ分類装置400の動作� ��、図1に示した第1の実施の形態に関わるデ� �タ分類装置100の動作と基本的に同じである� �

 このように本実施の形態によれば、第1の 実施の形態と同様の効果が得られると同時に 、超球面集合計算装置420によって計算した最 新の複数の超球面で超球面集合記憶装置410に 記憶された複数の超球面を置き換えることが できる。そのため、学習データの充実にあわ せて性能の向上を図ることができる効果があ る。

 以上本発明の実施の形態について説明し� ��が、本発明は以上の実施の形態にのみ限定� ��れず、その他各種の付加変更が可能である� ��また、本発明のデータ分類装置は、その有� ��る機能をハードウェア的に実現することは� ��論、コンピュータとプログラムとで実現す� ��ことができる。プログラムは、磁気ディス� ��や半導体メモリ等のコンピュータ可読記録� ��体に記録されて提供され、コンピュータの� ��ち上げ時などにコンピュータに読み取られ� ��そのコンピュータの動作を制御することに� ��り、そのコンピュータを前述した各実施の� ��態におけるデータ分類装置、分離面集合計� ��装置、超平面集合計算装置、超球面集合計� ��装置として機能させ、前述した処理を行わ� ��る。