(57)【要約】  分離面集合記憶部は、特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を規定する情報を記憶する。各既知クラス領域は、互いに交差しない２以上の分離面によって分離される。データ分類装置は、特徴空間における内積が計算可能である分類対象データが、少なくとも１つの既知クラス領域と未知クラス領域とのうちのどの領域に属するかを計算することによって、分類対象データの分類を決定する。信頼性の高い識別と外れ値分類を同じ手順で同時に行うことができるデータ分類方法およびデータ分類装置が提供される。
2009041101.tif 000002
【特許請求の範囲】
【請求項１】
特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を規定する情報を記憶する分離面集合記憶部と、前記少なくとも１つの既知クラス領域の各々は前記複数の分離面のうちの互いに交差しない２以上によって外部領域と分離され、
内積が計算可能な分類対象データが、前記分離面記憶部に記憶された前記情報で規定される前記少なくとも１つの既知クラス領域と前記未知クラス領域とのうちのどの領域に属するかを計算することによって、前記分類対象データの分類を決定する分類部
とを具備するデータ分類装置。
【請求項２】
前記特徴空間における内積が計算可能であり前記少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データおよび前記複数の学習データの各々の分類に基づいて複数の分離面を計算し、前記複数の分離面を規定する情報を前記分離面集合記憶部に記憶する分離面集合計算部
を更に具備する請求の範囲１に記載のデータ分類装置。
【請求項３】
前記分離面集合計算部は、前記複数の学習データに対する分類誤差の最小化、前記複数の分離面の各々の複雑性の最小化、および前記少なくとも１つの既知クラス領域の大きさの最小化をそれぞれ最適化目的として前記複数の分離面を計算する請求の範囲２に記載のデータ分類装置。
【請求項４】
前記分離面集合計算部は、原点周囲の前記未知クラス領域の大きさの最大化をさらに最適化目的の一つとする請求の範囲３に記載のデータ分類装置。
【請求項５】
前記分離面集合計算部は、前記少なくとも１つの既知クラス領域の相互間の重なりの最小化をさらに最適化目的の一つとする請求の範囲３に記載のデータ分類装置。
【請求項６】
前記複数の分離面の各々が、前記特徴空間上で開いた超平面を成す請求の範囲１乃至５の何れか１項に記載のデータ分類装置。
【請求項７】
前記複数の分離面の各々が、前記特徴空間上で閉じた超平面を成す請求の範囲１乃至５の何れか１項に記載のデータ分類装置。
【請求項８】
前記特徴空間が、前記学習データおよび前記分類対象データと同じ次元数のベクトル空間である請求の範囲１乃至７の何れか１項に記載のデータ分類装置。
【請求項９】
前記特徴空間が、前記学習データおよび前記分類対象データに対する非線形変換によって特徴付けられる空間である請求の範囲１乃至７の何れか１項に記載のデータ分類装置。
【請求項１０】
（ａ）特徴空間における内積が計算可能な分類対象データを入力する工程と、
（ｂ）特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を分離面記憶部から入力する工程と、前記少なくとも１つの複数の既知クラス領域の各々は前記複数の分離面のうちの互いに交差しない２以上によって外部領域と分離され、
（ｃ）前記分類対象データが、少なくとも１つの既知クラス領域と前記未知クラス領域とのうちのどの領域に属するかを計算することによって、前記分類対象データの分類を決定する工程
とを具備するデータ分類方法。
【請求項１１】
（ｄ）前記特徴空間における内積が計算可能であり前記少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データおよび前記複数の学習データの各々の分類とに基づいて前記複数の分離面を計算し、前記複数の分離面を規定する情報を前記分離面集合記憶部に記憶する工程
を更に具備する請求の範囲１０に記載のデータ分類方法。
【請求項１２】
前記工程（ｄ）では、前記複数の学習データに対する分類誤差の最小化、前記複数の分離面の各々の複雑性の最小化、および前記少なくとも１つの既知クラス領域の最小化をそれぞれ最適化目的として前記複数の分離面を計算する請求の範囲１１に記載のデータ分類方法。
【請求項１３】
前記工程（ｄ）では、原点周囲の前記未知クラス領域の大きさの最大化をさらに最適化目的の一つとする請求の範囲１２に記載のデータ分類方法。
【請求項１４】
前記工程（ｄ）では、前記少なくとも１つの既知クラス領域の相互間の重なりの最小化をさらに最適化目的の一つとする請求の範囲１２に記載のデータ分類方法。
【請求項１５】
特徴空間における内積が計算可能であり少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データを記憶する学習データ記憶部と、
前記学習データ記憶部に記憶された前記複数の学習データおよび前記複数の学習データの各々の分類に基づいて、前記特徴空間を前記少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を計算する分離面集合計算部と、前記少なくとも１つの既知クラス領域の各々は前記複数の分離面のうちの互いに交差しない２以上によって外部領域と分離され、
前記複数の分離面を規定する情報を記憶する分離面集合記憶部
とを具備する分離面集合計算装置。
【請求項１６】
前記分離面集合計算部は、前記複数の学習データに対する分類誤差の最小化、前記複数の分離面の各々の複雑性の最小化、および前記少なくとも１つの既知クラス領域の大きさの最小化をそれぞれ最適化目的として前記複数の分離面を計算する請求の範囲１５に記載の分離面集合計算装置。
【請求項１７】
前記分離面集合計算部は、原点周囲の前記未知クラス領域の大きさの最大化をさらに最適化目的の一つとする請求の範囲１６に記載の分離面集合計算装置。
【請求項１８】
前記分離面集合計算部は、前記少なくとも１つの既知クラス領域の相互間の重なりの最小化をさらに最適化目的の一つとする請求の範囲１６に記載の分離面集合計算装置。
【請求項１９】
（ａ）特徴空間における内積が計算可能な分類対象データを入力する工程と、
（ｂ）特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を分離面記憶部から入力する工程と、前記少なくとも１つの複数の既知クラス領域の各々は前記複数の分離面のうちの互いに交差しない２以上によって外部領域と分離され、
（ｃ）前記分類対象データが、少なくとも１つの既知クラス領域と前記未知クラス領域とのうちのどの領域に属するかを計算することによって、前記分類対象データの分類を決定する工程
とを具備する方法をコンピュータに実行させるためのプログラム。
【請求項２０】
（ｄ）前記特徴空間における内積が計算可能であり前記少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データおよび前記複数の学習データの各々の分類とに基づいて前記複数の分離面を計算し、前記複数の分離面を規定する情報を前記分離面集合記憶部に記憶する工程
を更に具備する方法をコンピュータに実行させるための請求の範囲１９に記載のプログラム。
【請求項２１】
前記工程（ｄ）では、前記複数の学習データに対する分類誤差の最小化、前記複数の分離面の各々の複雑性の最小化、および前記少なくとも１つの既知クラス領域の最小化をそれぞれ最適化目的として前記複数の分離面を計算する請求の範囲２０に記載のプログラム。
【請求項２２】
前記工程（ｄ）では、原点周囲の前記未知クラス領域の大きさの最大化をさらに最適化目的の一つとする請求の範囲２１に記載のプログラム。
【請求項２３】
前記工程（ｄ）では、前記少なくとも１つの既知クラス領域の相互間の重なりの最小化をさらに最適化目的の一つとする請求の範囲２１に記載のプログラム。
【請求項２４】
（ａ）特徴空間における内積が計算可能であり少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データを記憶する工程と、
（ｂ）前記学習データ記憶部に記憶された前記複数の学習データおよび前記複数の学習データの各々の分類に基づいて、前記特徴空間を前記少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を計算する工程と、前記少なくとも１つの既知クラス領域の各々は前記複数の分離面のうちの互いに交差しない２以上によって外部領域と分離され、
（ｃ）前記複数の分離面を規定する情報を記憶する工程
とを具備する方法をコンピュータに実行させるためのプログラム。
【請求項２５】
前記（ｃ）計算する工程は、前記分離面集合計算部は、前記複数の学習データに対する分類誤差の最小化、前記複数の分離面の各々の複雑性の最小化、および前記少なくとも１つの既知クラス領域の大きさの最小化をそれぞれ最適化目的として前記複数の分離面を計算する請求の範囲２４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分類方法およびデータ分類装置に関し、特に、複数の分離面を利用することによって既知のクラスおよび外れ値を同時に分類可能なデータ分類方法およびデータ分類装置に関する。この出願は、２００７年９月２８日に出願された日本特許出願２００７−２５３７０３号を基礎とする。その日本特許出願の開示はこの参照により、ここに取り込まれる。
【背景技術】
【０００２】
データ分類は、未分類データが与えられた場合に、該データの属するクラスを推定する技術であり、データ解析の最も基本的な要素の一つである。特に、クラス間の分離面など、特徴空間を複数の領域に分ける分離面を利用したデータ分類技術は、モデル表現力が高い。そのため、画像データ、たんぱく質や遺伝子データをはじめとしたデータ分類はもちろん、クラスラベルを故障情報とした場合には故障診断、インターネットやソーシャルネットワークなどネットワーク間のリンクの有無をクラスラベルとした場合にはリンクの予測など幅広い問題およびデータ構造に対して応用が可能である。【０００３】
分離面を利用したデータ分類方法は、識別と外れ値分類の２つの技術に大別できる。前者は、クラスラベルの付いたデータからクラスを分離する分離面を学習し、分類対象データを既知のクラスへ分類する技術である。後者は学習データを１つのクラスとみなし、学習データの分布する領域とそれ以外の領域を分離する分離面を学習することで、分類対象データが該クラスに属するか、該クラスからは外れるかを分類する技術である。また、識別および外れ値分類を同時に実施するデータ分類方法としては、分離面を利用したデータ分類方法の組み合わせとして容易に類推することができる方法が幾つかある。【０００４】
まず、学習データに関するクラスの数が１つの場合、データ分類は外れ値分類となるため、１クラスサポートベクトルマシン（文献５第８章、文献３）などの公知の外れ値分類技術を利用することが考えられる。【０００５】
次に、学習データに関するクラスの数が２つ以上の場合、１クラスサポートベクトルマシンなどの外れ値分類方法を、各クラスに対して個々に学習し、分類対象データに対して全クラスに対して外れ値であると判定された場合には外れ値とし、１つまたは複数のクラスに対してそのクラスに属すると判定された場合には、それらのクラスの１つまたは複数に分類する方法が考えられる。【０００６】
学習データに関するクラスの数が２つ以上の場合の他の方法として、１クラスサポートベクトルマシンなどの外れ値分類方法と、サポートベクトルマシン（文献１、文献２、文献６）などの分離面を利用した識別方法を組み合わせ、まず全クラスをまとめて外れ値分類方法によって学習し、次に既知のクラスに関する識別方法を学習する方法が考えられる。この方法では、まず分類対象データを外れ値検出方法によって外れ値かどうかを判定し、外れ値ではない場合に識別方法によって、既知のどのクラスに属するかを分類する。【０００７】
他方、複数の分離面を利用した技術としては、多クラスサポートベクトルマシンがある。多クラスサポートベクトルマシンの実現方法は幾つかあるが、２クラスのサポートベクトルマシンをクラスの組み合わせごとに計算し多数決をとる方法と、文献７および文献４で提案する方法のように複数の超空間を同時に最適化する方法がある。【０００８】
以下に文献のリストを挙げる。
［文献１］特開２００７−１１５２４５号公報
［文献２］特開２００７−９５０６９号公報
［文献３］特開２００５−３４５１５４号公報
［文献４］特開２００７−５２５０７号公報
［文献５］Bernhard Scholkopf and Alex Smola. Learning with Kernels, Support Vector Machines, Regularization, Optimization and Beyond. MIT Press. 2002.
［文献６］Bernhard Scholkopf, Alex J. Smola, Robert C. Williamson and Peter L.Bartlett. New Support Vector Algorithms. Neural Computation. Vol.12: page1207-1245. 2000.
［文献７］Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, Yasemin Altun. Large Margin Methods for Structured and Interdependent Output Variables. Journal of Machine Learning Research Vol.6: page 1453-1484. 2005.
［文献８］A.L. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation. Vol.15: page 915-936. 2003.
【発明の開示】
【０００９】
従来の識別および外れ値分類を同時に実施するデータ分類方法には以下のような課題がある。
【００１０】
まず、１クラスサポートベクトルマシンやサポートベクトルマシンのような単一の分離面によってデータを分類する場合、データの片側の境界面のみを考慮することになり、逆側の境界を考慮できないため、分類が楽観的になるという問題点がある。
【００１１】
その理由は、図１８に示されるように、分離超平面（単に超平面とも称す）を利用した１クラスサポートベクトルマシンでは、データの片面の分離境界のみを考慮し、逆側の境界は考慮されないためである。また、図１９に示されるように、分離超球面（単に超球面とも称す）を利用した１クラスサポートベクトルマシンでは、データの外側の分離境界のみを考慮し、内側の境界は考慮されないためである。これはその他の、分離面を利用した公知のデータ分類装置に共通する課題である。
【００１２】
さらに、分離面を利用した公知のデータ分類技術を組み合わせた場合には、データ分類精度の信頼性が低下するという問題点がある。
【００１３】
その理由は、各クラスに対する外れ値分類を組み合わせた場合には、各クラスを独立に扱うため、クラス間の関係を考慮しないためである。また、外れ値分類と識別を組み合わせる場合には、異なるクラスを１つのクラスと考えるため、外れ値分類の精度が低下するためである。これは、上記の組み合わせ方法以外の組み合わせ方をした場合にも起こりうる課題である。
【００１４】
これら公知の技術を組み合わせた場合には、複数の分離面を利用しているが、それらは独立に計算され利用されているため、１つずつ分離面を利用していることと同義である。
【００１５】
さらに、従来の分離面を利用したデータ分類方法には、外れ値分類と識別を同時に行うという考え方がないため、同じモジュールによって外れ値分類と識別を同時に行うことができないという課題もある。
【００１６】
さらに、多クラスサポートベクトルマシンは複数の分離面を利用するが、外れ値分類を行うことができないという課題がある。
【００１７】
その理由は、多クラスサポートベクトルマシンでは、既知クラス間を分類する分離面のみを考慮し、未知のクラスと既知クラスの境界を考慮しないためである。換言すれば、既知のクラスは１つの分離面を挟んで他の既知のクラスと接しており、既知のクラスの間に未知のクラスを介在させるという考えがない。
【００１８】
本発明の目的は、信頼性の高い識別と外れ値分類を同じ手順で同時に行うことができるデータ分類方法およびデータ分類装置を提供することである。
【００１９】
本発明の一実施形態におけるデータ分類装置は、特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を規定する情報を記憶する分離面集合記憶部を備える。少なくとも１つの既知クラス領域の各々は複数の分離面のうちの互いに交差しない２以上によって外部領域と分離される。データ分類装置は更に、内積が計算可能な分類対象データが、分離面記憶部に記憶された情報で規定される少なくとも１つの既知クラス領域と未知クラス領域とのうちのどの領域に属するかを計算することによって、分類対象データの分類を決定する分類部を備える。
【００２０】
本発明の一実施形態におけるデータ分類方法は、（ａ）特徴空間における内積が計算可能な分類対象データを入力する工程と、（ｂ）特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を分離面記憶部から入力する工程とを備える。少なくとも１つの複数の既知クラス領域の各々は複数の分離面のうちの互いに交差しない２以上によって外部領域と分離される。データ分類方法は更に、（ｃ）分類対象データが、少なくとも１つの既知クラス領域と未知クラス領域とのうちのどの領域に属するかを計算することによって、分類対象データの分類を決定する工程を備える。
【００２１】
本発明の一実施形態における分離面集合計算装置は、特徴空間における内積が計算可能であり少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データを記憶する学習データ記憶部と、学習データ記憶部に記憶された複数の学習データおよび複数の学習データの各々の分類に基づいて、特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を計算する分離面集合計算部とを備える。少なくとも１つの既知クラス領域の各々は複数の分離面のうちの互いに交差しない２以上によって外部領域と分離される。分離面集合計算装置は更に、複数の分離面を規定する情報を記憶する分離面集合記憶部を備える。
【００２２】
本発明の一実施形態におけるプログラムは、以下の（ａ）〜（ｃ）を備える方法をコンピュータに実行させる。
（ａ）特徴空間における内積が計算可能な分類対象データを入力する工程。
（ｂ）特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を分離面記憶部から入力する工程。少なくとも１つの複数の既知クラス領域の各々は複数の分離面のうちの互いに交差しない２以上によって外部領域と分離される。
（ｃ）分類対象データが、少なくとも１つの既知クラス領域と未知クラス領域とのうちのどの領域に属するかを計算することによって、分類対象データの分類を決定する工程。
【００２３】
本発明の一実施形態におけるプログラムは、以下の（ａ）〜（ｃ）を備える方法をコンピュータに実行させる。
（ａ）特徴空間における内積が計算可能であり少なくとも１つの既知クラスのいずれかにそれぞれ分類されている複数の学習データを記憶する工程。
（ｂ）学習データ記憶部に記憶された複数の学習データおよび複数の学習データの各々の分類に基づいて、特徴空間を少なくとも１つの既知クラスにそれぞれ対応する少なくとも１つの既知クラス領域と未知クラス領域とに分離する複数の分離面を計算する工程。少なくとも１つの既知クラス領域の各々は複数の分離面のうちの互いに交差しない２以上によって外部領域と分離される。
（ｃ）複数の分離面を規定する情報を記憶する工程。
【００２４】
本発明によれば信頼性の高い識別と外れ値分類を同じ手順で同時に行うことができる。識別と外れ値分類を同じ手順で同時に行うことができる理由は、内積が計算可能であり１以上の既知クラスに分類されている特徴空間における複数の学習データおよび複数の学習データの分類に基づいて、特徴空間を１以上の既知クラスにそれぞれ対応する１以上の既知クラス領域と未知クラス領域とに分離する複数の分離面であって、１クラス当たり２個以上で且つ互いに交差しない複数の分離面を計算し、分類が未知である前記特徴空間における内積が計算可能な分類対象データの分類時には、分類対象データが、複数の分離面によって１以上のクラス領域とそれ以外の未知クラス領域とに分離された特徴空間内のうちのどの領域に属するかを計算することによって、その分類対象データの分類を決定するためである。また、信頼性の高いデータ分類を行える理由は、それぞれの既知クラスは２以上の分離面によって境界が定められているため、１つの分離面によって境界を定める場合と比較して、データ分類の信頼性がより高まるからである。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施の形態に係るデータ分類装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態に係る超平面を利用したデータ分類の一例である。
【図３】本発明の第１の実施の形態に係る超球面を利用したデータ分類の一例である。
【図４】本発明の第１の実施の形態に係る超平面を規定するデータの記憶方法の一例である。
【図５】本発明の第１の実施の形態に係る超球面を規定するデータの記憶方法の一例である。
【図６】本発明の第１の実施の形態に係るデータ分類装置の処理例を示すフローチャートである。
【図７】本発明の第２の実施の形態に係るデータ分類装置の構成を示すブロック図である。
【図８】本発明の第２の実施の形態に係る分離面集合計算装置の構成を示すブロック図である。
【図９】本発明の第３の実施の形態に係るデータ分類装置の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態に係る超平面集合計算装置の構成を示すブロック図である。
【図１１】本発明の第３の実施の形態に係るデータ分類装置によって、クラスの数が１つの場合に計算されるデータ分類の概念図である。
【図１２】本発明の第３の実施の形態に係るデータ分類装置によって、クラスの数が２つの場合に計算されるデータ分類の概念図である。
【図１３】本発明の第３の実施の形態に係るデータ分類装置によって、クラスの数が３つ以上の場合に計算されるデータ分類の概念図である。
【図１４】本発明の第３の実施の形態に係るデータ分類装置で使用するのが好ましくない超平面の説明図である。
【図１５】本発明の第４の実施の形態に係るデータ分類装置の構成を示すブロック図である。
【図１６】本発明の第４の実施の形態に係る超球面集合計算装置の構成を示すブロック図である。
【図１７】本発明の第４の実施の形態に係るデータ分類装置によって計算されるデータ分類の概念図である。
【図１８】本発明に関連する、超平面を利用したデータ分類技術の例である。
【図１９】本発明に関連する、超球面を利用したデータ分類技術の例である。
【発明を実施するための最良の形態】
【００２６】
次に、本発明の実施の形態について、図面を参照して詳細に説明する。【００２７】
［第１の実施の形態］
図１を参照すると、本発明の第１の実施の形態に関わるデータ分類装置１００は、外れ値分類機能付データ分類部１１０と、分類結果出力部１２０と、記憶装置１３０と、分離面集合記憶装置１４０とを備えている。データ分類装置１００は、パーソナルコンピュータなどのコンピュータによって実現することができる。その場合、外れ値分類機能付データ分類部１１０と分類結果出力部１２０とは、記憶装置に格納されたプログラムをＣＰＵなどの処理装置が読み出してそのプログラムに既述された手順に従って実行動作を行うことにより実現される。【００２８】
このデータ分類装置１００は、分類対象データ１５０を入力し、分類対象データ１５０が複数の分離面によって１以上のクラス領域（既知クラス領域）とそれ以外の未知クラス領域とに分離された特徴空間内のどの領域に属するかを計算することによって、分類対象データ１５０を既知のどのクラスに分類すべきか、または外れ値に分類すべきかを推定し、その推定結果を分類結果１６０として出力する。【００２９】
分類対象データ１５０は、分類が未知のベクトルデータである。今、分類対象データ１５０に含まれる属性の数をｄとし、分類対象データ１５０を式（１）のようにｄ次元のベクトルとして表現する。式（１）において、右辺の括弧の右肩に付した記号´は転置を示す（記号´の代わりに記号Ｔを使う場合もある）。また、ｘｊは分類対象データ１５０のｊ番目の属性を表し、実数値であっても良いしシンボル値であってもよい。また、ｘから特徴空間への写像をφとし、ｘの特徴空間における像をφ（ｘ）と表す。以下で、分類対象データといった場合には、分類対象データと特徴空間における像のどちらを指してもかまわないものとする。【００３０】
2009041101.tif 000003
【００３１】
分離面集合記憶装置１４０は、特徴空間を１以上の既知クラスにそれぞれ対応する１以上のクラス領域とそれ以外の未知クラス領域とに分離する複数の分離面を規定する情報を記憶する。分離面は、図２に示される超平面Ａ〜Ｄのように特徴空間上で平面を成すものであっても良いし、図３に示される超球面Ｅ〜Ｈのように特徴空間上で球面を成すものであっても良く、その他、超円柱面、超錐面などであっても良い。ただし、図２に示される互いに平行な超平面Ａ〜Ｄ、図３に示される同心の超球面Ｅ〜Ｈのように、複数の分離面は互いに交差しないことが必要である。また、図２ではクラス１の領域が２つの超平面Ａ，Ｂにより、クラス２の領域が２つの超平面Ｃ，Ｄにより、図３におけるクラス３の領域が２つの超球面Ｅ，Ｆにより、クラス４の領域が２つの超球面Ｇ，Ｈにより、それぞれ境界が定められている。このように、既知の１クラス当たり２個以上の分離面によって各既知クラスの境界が定められている。【００３２】
分離面集合記憶装置１４０に記憶する情報は、分離面を特定する情報であればどのような情報であっても良い。例えば、特徴空間のｉ番目の基底関数をψｉとすると、特徴空間における分離面は基底関数を利用して記述することが可能である。例えば、分離面がΣｗｉψｉφ（ｘ）＋ｂ＝０で表される超平面の場合には、基底ψｉおよび基底の重みｗｉ、切片ｂを、超平面を規定する情報として記憶すればよい。この際、基底ψｉは全ての超平面で共通のため、例えば図４のように、重みｗｉと切片ｂを表形式で各超平面毎に記憶し、基底ψｉは共通に記憶しておくことが可能である。また、超球面の場合には、中心をｃ、半径をｒとすると、｜φ（ｘ）−ｃ｜２＝ｒと表され、また中心ｃは特徴空間内の点のため、ｃ＝Σｗｉψｉと表される。そのため、重みｗｉと半径ｒを図５のように表形式で各超球面毎に保存し、基底ψｉは共通に記憶しておくことが可能である。また、基底関数に関しては、任意の基底関数を利用することが可能であるが、頻繁に利用される基底としては、例えばｘの元空間における基底やカーネル関数などが挙げられる。その場合、基底同士の内積が定義されているものとする（カーネル関数とは、特定の条件を満たす任意の基底関数に関する内積を与える関数）。【００３３】
記憶装置１３０には、分類対象データ１５０と分離面集合記憶装置１４０に記憶された複数の分離面との位置関係から、分類対象データ１５０を分類するためのルールが記憶されている。例えば図２に示されるように複数の超平面によってデータを分類する場合、記憶装置１３０には、例えば「超平面Ａより負の方向→外れ値へ分類」、「超平面Ｃより正の方向かつ超平面Ｄより負の方向→クラス２へ分類」などといったルールが記憶されている。また、図３に示されるように複数の超球面によってデータを分類する場合、記憶装置１３０には、例えば「超球面Ｅより内側→外れ値へ分類」、「超球面Ｇより外側かつ超球面Ｈより内側→クラス４へ分類」などといったルールが記憶されている。この例では超平面と超球面の場合を説明したが、前述したように分離面はその二つに限定されるものではない。分離面としてその他の形状の超曲面を利用することも可能であるし、また異なる種類の分離面を組み合わせることも可能である。なお、記憶装置１３０には外れ値分類機能付データ分類部１１０によって判定された分類結果を記憶しておくことも可能である。【００３４】
外れ値分類機能付データ分類部１１０は、分類対象データ１５０および分離面集合記憶装置１４０に記憶された複数の分離面に関する情報を読み込み、分類対象データ１５０と複数の分離面との位置関係を計算する。分離面は前述したように、例えば超平面、超球面、超円柱面、超錐面などである。位置関係とは、例えば超平面の場合にはデータが超平面上、正の側、負の側のどの位置にあるかであり、超球面の場合には超球面上、超球面の内側、超球面の外側のどの位置にあるかのことである。この位置関係からデータを分類するルールが前述したように記憶装置１３０に保存されており、外れ値分類機能付データ分類部１１０は、位置関係および分類ルールを利用してデータを分類する。【００３５】
分類結果出力部１２０は、外れ値分類機能付データ分類部１１０で判定された分類結果を、外れ値分類機能付データ分類部１１０から直接受け取るか、記憶装置１３０に記憶された分類結果を読み出して出力する。出力先は、データ分類装置１００に接続されたディスプレイ等の出力装置であっても良いし、ネットワークを介して接続された出力装置や端末装置であっても良い。【００３６】
次に本実施の形態に関わるデータ分類装置の全体の動作を説明する。【００３７】
図６を参照すると、データ分類装置１００の外れ値分類機能付データ分類部１１０は、ｄ個の属性を含む分類対象データ１５０を入力し（Ｓ１００）、また分離面集合記憶装置１５０から複数の分離面の情報を入力する（Ｓ１０１）。【００３８】
次に、外れ値分類機能付データ分類部１１０は、入力された分類対象データ１５０および複数の分離面の情報を利用して、分類対象データ１５０と複数の分離面との位置関係を計算する（Ｓ１０２）。計算は、例えば図２および図４の超平面Ａを例にすると、データｘに対して、ΣｗｉＡψｉφ（ｘ）＋ｂＡを計算し、その値の位置関係（０、正、負によって、それぞれ超平面Ａ上、超平面Ａより正側、超平面Ａより負側のいずれかに分類される）を判定することができる。また図３および図５の超球面Ｅの場合でも、位置関係（データｘに対して｜φ（ｘ）−ΣｗｉＥψｉ｜２がｒＥと等しいか、大きいか、小さいかによって、それぞれ超球面Ｅ上、超球面Ｅより外側、超球面Ｅより内側のいずれかに分類される）を判定することが可能である。【００３９】
次に、外れ値分類機能付データ分類部１１０は、記憶装置１３０に記憶されている分類ルールを読み込み、分類対象データ１５０がどのクラスに属するかを判定する（Ｓ１０３）。そして、分類結果出力部１２０は、外れ値分類機能付データ分類部１１０の分類結果を出力する（Ｓ１０４）。【００４０】
データ分類に関しては、既知のクラス数は１つ乃至は複数であり、１つの場合は外れ値分類を行うデータ分類装置として機能する。【００４１】
次に本実施の形態の効果を説明する。【００４２】
本実施の形態によれば、識別と外れ値分類を同じ手順で同時に行うことができる。その理由は、特徴空間を１以上の既知クラスにそれぞれ対応する１以上のクラス領域とそれ以外の未知クラス領域とに分離する複数の分離面と分類対象データ１５０との位置関係を計算し、分類対象データ１５０が１以上のクラス領域とそれ以外の未知クラス領域とのうちのどの領域に属するかを計算することによって、分類対象データ１５０の分類を決定するためである。【００４３】
また本実施の形態によれば、信頼性の高いデータ分類を行うことができる。その理由は、それぞれの既知クラスは２以上の分離面によって境界が定められているため、１つの分離面によって境界を定める場合と比較して、データ分類の信頼性がより高まるからである。【００４４】
［第２の実施の形態］
図７を参照すると、本発明の第２の実施の形態に関わるデータ分類装置２００は、図１に示した第１の実施の形態に関わるデータ分類装置１００と比較して、分離面集合記憶装置１４０に代えて分離面集合記憶装置２１０を有する点、および分離面集合計算装置２２０が接続されている点で相違する。【００４５】
分離面集合計算装置２２０は、１以上の既知クラスに分類されている複数の学習データおよびその分類に基づいて複数の分離面を計算する。複数の分離面は、特徴空間を１以上の既知クラスにそれぞれ対応する１以上のクラス領域とそれ以外の未知クラス領域とに分離する。１以上のクラス領域の各々は、この複数の分離面のうちの互いに交差しない２以上によって、他の領域と分離される。また、分離面集合記憶装置２１０は、分離面集合計算装置２２０で計算された複数の分離面を規定する情報を記憶する装置である。【００４６】
分離面集合計算装置２２０は、図８に示されるように、分離面集合最適化部２２１と記憶装置２２２と分離面集合出力部２２３とを備える。分離面集合最適化部２２１は、学習データ記憶装置２２４から学習用のデータを入力する。分離面集合出力部２２３は、最適化された分離面集合２２５を出力する。【００４７】
学習データ記憶装置２２４には、分類対象データ１５０と同じ属性を有するデータｘｉと、データｘｉの属するクラスラベルｙｉの組の集合が記憶されている。ここで、ｉは学習データのインデックスとし、Ｎを所定の整数とし、学習データはｉ＝１，…，Ｎまで入力されるとする。【００４８】
分離面集合最適化部２２１は、学習データに対する分類誤差の最小化、分離面集合の複雑性の最小化、および各クラス領域の大きさの最小化を同時に最適化する複数の分離面を計算する。利用する複数の分離面に関しては、事前に候補となる分離面の組み合わせを記憶装置２２２へ記憶しておき、最適化時に記憶装置２２２からそれらの候補を読み込んで利用しても良い。または任意の分離面の組み合わせに対して最適化を行うことにより最適な分離面集合を選択してもよい。【００４９】
分類誤差は、任意の誤差を利用することが可能であり、例としては誤分類データ数、誤分類データに対する２乗損失、誤分類データに対する絶対値損失、誤分類データに対するヒンジ損失などが挙げられる。【００５０】
分離面集合の複雑性は、任意の複雑性の基準を利用することが可能である。例としては、ｊ番目の分離面をｆｊとすると、ｆｊのＬ１複雑性｜ｆｊ｜、Ｌ２複雑性｜ｆｊ｜２、Ｌ∞複雑性｜ｆｊ｜∞などが挙げられる。ここで、ｆｊのＬ１複雑性、Ｌ２複雑性、Ｌ∞複雑性とは、関数（分離面）のノルム（大きさ）を表す量である。ベクトルｖ＝（ｖ１，…，ｖｎ）に関して言えば、Ｌ１複雑性とはΣ｜ｖｉ｜であり、Ｌ２複雑性とはΣｖｉ２であり、Ｌ∞複雑性とはｍａｘ｜ｖｉ｜となる。【００５１】
各クラス領域の大きさは、例えば図２に示されるクラス１の場合には超平面Ａと超平面Ｂとで挟まれた領域の大きさ、例えば図３に示されるクラス３の場合には超球面Ｅと超球面Ｆとで挟まれた領域の大きさのことである。それらの大きさを表すために任意の基準を利用することが可能である。【００５２】
一般的には分離面の複雑性を大きくするほど学習データに対する分類誤差は小さくなるが、これは学習データに対して過学習をしているため未知の分類データに対する分類精度は低くなってしまう。したがって、分離面の複雑性を小さく保ったまま分類誤差を小さくする分離面を学習するために、両者の和（さらに各クラス領域の大きさの基準を加えた和）が最も小さくなる分離面集合を選択する。【００５３】
次に本実施の形態の動作を説明する。【００５４】
本実施の形態の動作は、分離面集合計算装置２２０による分離面の計算処理と、この計算された分離面を利用した分類対象データ１５０の分類処理とに大別される。【００５５】
分離面集合計算装置２２０による分離面の計算処理では、分離面集合最適化部２２１によって、学習データ記憶装置２２４から分類が既知の学習データを読み込み、この学習データに対する分類誤差の最小化、分離面集合の複雑性の最小化、および各クラス領域の大きさの最小化を同時に最適化する複数の分離面を計算して、記憶装置２２２に記憶する。次に、分離面集合出力部２２３によって、記憶装置２２２から複数の分離面を規定するデータを読み出し、分離面集合２２５として分離面集合記憶装置２１０に記憶する。【００５６】
本実施の形態のデータ分類装置２００の動作は、図１に示した第１の実施の形態に関わるデータ分類装置１００の動作と基本的に同じである。【００５７】
このように本実施の形態によれば、第１の実施の形態と同様の効果が得られると同時に、分離面集合計算装置２２０によって計算した最新の複数の分離面で分離面集合記憶装置２１０に記憶された複数の分離面を置き換えることができ、学習データの充実にあわせて性能の向上を図ることができる効果がある。【００５８】
［第３の実施の形態］
図９を参照すると、本発明の第３の実施の形態に関わるデータ分類装置３００は、図７に示した第２の実施の形態に関わるデータ分類装置２００と比較して、分離面集合記憶装置２１０に代えて超平面集合記憶装置３１０を有する点、および分離面集合計算装置２２０に代えて超平面集合計算装置３２０が接続されている点で相違する。【００５９】
超平面集合計算装置３２０は、１以上の既知クラスに分類されている複数の学習データおよびその分類に基づいて、特徴空間を１以上の既知クラスにそれぞれ対応する１以上のクラス領域とそれ以外の未知クラス領域とに分離する複数の超平面を計算する。１以上のクラス領域の各々は、この複数の分離面のうちの互いに交差しない２以上によって、他の領域と分離される。また、超平面集合記憶装置３１０は、超平面集合計算装置３２０で計算された複数の超平面を規定する情報を記憶する装置である。【００６０】
図１０を参照すると、超平面集合計算装置３２０は、超平面集合最適化部３２１と、記憶装置２２２と、数理計画問題計算装置３２２と、超平面集合出力部３２３とを備える。超平面集合最適化部３２１は、学習データ記憶装置２２４から学習用のデータを入力する。超平面集合出力部３２３は、最適化された超平面集合３２４を出力する。すなわち、超平面集合計算装置３２０は、データ分類のために複数の互いに平行な超平面を計算する。従って、本実施の形態のデータ分類装置３００では、図２に示されるように平行する超平面によって各クラスの領域を区切ることによってデータ分類を実現する。【００６１】
以下で、超平面の具体的な計算手順に関して、幾つかの例をもとに説明を行う。【００６２】
学習データ記憶装置２２４から入力されたデータに関するクラスのインデックスをｊ＝１，…，Ｃ（Ｃは１以上の整数）とする。以下では、ｘｉｊをｊ番目のクラスに属するｉ番目のデータとし、各クラスに属する学習データの数をＮｊとする。特徴空間における超平面は、或る重みｗおよび切片ｂに関して、ｗＴφ（ｘ）＋ｂ＝０を満たす点の集合として記述される。ここで、ｆ（ｘ）＝ｗＴφ（ｘ）としておく。今、超平面は平行なため、重みｗは共通であるから、ｗおよびｊ番目のクラスの超平面に対する切片ｂｊ＋およびｂｊ−が、超平面集合最適化部３２１によって最適化される。【００６３】
なお、φ（ｘ）が線形の場合、特徴空間は、学習データ（および分類対象データ）と同じ次元数のベクトル空間になる。φ（ｘ）が非線形の場合、特徴空間は、学習データ（および分類対象データ）を非線形変換したベクトルデータと同じ次元数のベクトル空間になる。【００６４】
最適化のための基準として、以下の３条件、
（ａ）分類誤差最小化
（ｂ）ｆ（ｘ）の複雑性最小化
（ｃ）各既知クラス領域の大きさ最小化
を同時に最適化することによって、ｗおよび各ｊに対するｂｊ＋およびｂｊ−を計算する。【００６５】
上記３条件に加えて、
（ｄ）原点周囲の未知領域の大きさ最大化
（ｅ）各クラスの領域が重ならない（あるいは各クラス領域の重なりの最小化）
の１つないしは双方をも同時に最適化することによってｗおよび各ｊに対するｂｊ＋およびｂｊ−を計算しても良い。【００６６】
（ｃ）の基準に関しては、超平面に対して各既知クラスの領域の大きさを最小化する。これによって、各クラス領域を両面からタイトに押さえることが要請される。【００６７】
（ｄ）の基準は各超平面に対して原点付近が未知クラスの領域になることを要請する。これは、学習データの張る空間の補空間のデータは未知クラスに属すると考えられるが、該データが学習データの張る空間へ射影された場合、必ず原点に射影されるためである。例として３次元の場合を考える。学習データが全てａ（１，０，０）＋ｂ（０，１，０）と表されるように、１次元目と２次元目のみに分布していると仮定する。この場合、３次元目に分布する未知クラスのデータｃ（０，０，１）は１次元目と２次元目の成分が０のため、データの張る空間に対しては必ず原点に射影される。【００６８】
（ａ）から（ｅ）の複数の基準を同時に最適化する具体的な例を幾つか挙げる。【００６９】
［Ｃ＝１の場合］
学習データ記憶装置２２４から入力されたデータに関するクラスが唯一の場合には、互いに平行な２つの超平面が計算される。そのような２つの超平面は、例として（２）式に示される最適化問題を解くことで求められる。【００７０】
2009041101.tif 000004
【００７１】
（２）式では（ａ）から（ｄ）の基準が、（ａ）第２項、（ｂ）第１項、（ｃ）第３項、（ｄ）第４項として表現されている。（ｅ）の基準に関しては１クラスの場合には考慮される必要がない。ν０およびν１はどの基準に重きをおくかを決定するパラメータで、０より大きく１より小さい実数値である。（２）式によって計算される２つの超平面は、図１１に示されるような超平面となる。以下、（２）式における目的関数および制約条件について説明する。【００７２】
式（２）の目的関数における第１項は、最適化の基準（ｂ）のために必要な項であり、複雑性としてＬ２複雑性を採用すると、ｆ（ｘ）のＬ２複雑性はこのように計算される。第２項は、最適化の基準（ａ）のために必要な項であり、ξｉ１＋とξｉ１−は誤差を表すためのスラック変数である。第３項は、最適化の基準（ｃ）のために必要な項であり、ｂ１−≦ｗ’φ（ｘｉ１）≦ｂ１＋のため、ｂ１−−ｂ１＋を小さくすることによって既知クラスを包む領域を最小化している。第４項は、最適化の基準（ｄ）のために必要な項である。原点周辺の未知領域の大きさを最大化することは、すなわち既知領域を原点から遠ざけることを意味する。そのため、既知領域の中心（ｂ１−＋ｂ１＋）／２を原点から遠ざけることで（ｄ）の基準が達成される。【００７３】
式（２）の制約条件における、ｗ’φ（ｘｉ１）−ｂ１＋≦ξｉ１＋、ｗ’φ（ｘｉ１）−ｂ１−≧−ξｉ１−、ξｉ１＋≧０、ξｉ１−≧０は、次の意味を持つ。すなわち、図１１に示されるように、クラス１に属するデータはｂ１＋とｂ１−の間に入る必要がある（つまり、ｂ１−≦ｗ’φ（ｘｉ１）≦ｂ１＋である）が、入らなかった分は誤差としてカウントする。ｂ１＋≧ｂ１−は、ｂ１−≦ｗ’φ（ｘｉ１）≦ｂ１＋のために必要な制約条件である。ｂ１−≧０は、原点領域を未知領域とするために必要な制約条件である。つまり、ｂ１−≧０という制約条件がないと、ｂ１−≦０≦ｂ１＋となり得るためである。なお、ｂ１−≧０の代わりに、ｂ１＋≦０でも良い。【００７４】
（２）式は標準的な凸２次計画問題であり、超平面集合最適化部３２１および数理計画問題計算装置３２２によって最適解が計算される。【００７５】
なお、特徴空間が非線形で、特徴空間への写像φが明示的に与えられていない場合には、一般には（２）式を直接解くことができない。しかし、特徴空間における内積がカーネル関数として定義されている場合には、（２）式の双対問題を解くことで超平面が計算される。【００７６】
（２）式の双対問題は（３）式のようにラグランジュの未定乗数を導入することによって、（４）式となる。【００７７】
2009041101.tif 000005
【００７８】
2009041101.tif 000006
【００７９】
ラグランジュの未定乗数は、αｉ１＋，αｉ１−，μ０，μ１，γｉ１＋，γｉ１−，δである。ただし、ｋ（ｘｉ１，ｘｉ’１）＝φ（ｘｉ１）Ｔφ（ｘｉ’１）は特徴空間での内積であり、双対問題ではφ（ｘ）がどのような関数であっても、その内積φ（ｘｉ１）Ｔφ（ｘｉ’１）さえ計算できれば解くことが可能である。（４）式で表される双対問題も凸２次計画問題である。【００８０】
双対問題に対して重みｗは、（５）式と表されるため、ｆ（ｘ）＝ｗＴφ（ｘ）は（６）式で表される。相対問題を解いた場合には、記憶する内容が図４のｗｉとｂの組でなくて、αｉとｂの組になる。【００８１】
2009041101.tif 000007
【００８２】
2009041101.tif 000008
【００８３】
［Ｃ＝２の場合］
学習データ記憶装置２２４から入力されたデータに関するクラスが２つの場合、各クラスに対して平行な２つの超平面が計算される。そのような複数の超平面は、例として（７）式に示される最適化問題を解くことで計算される。【００８４】
2009041101.tif 000009
【００８５】
（７）式では（ａ）から（ｅ）の基準が、（ａ）第２項、（ｂ）第１項、（ｃ）第３項、（ｄ）第４項として表現されている。（ｅ）の基準に関してはｂ１−≧ｂ２＋が自動的に満たされるため、明示的に考慮する必要はない。ν０およびν１およびν２はどの基準に重きをおくかを決定するパラメータで、０より大きく１より小さい実数値である。（７）式によって計算される複数の超平面は、図１２に示されるような超平面となる。以下、（７）式における目的関数および制約条件について説明を補足する。【００８６】
式（７）の目的関数における第４項は、最適化の基準（ｅ）のために必要な項であり、絶対値記号が付いている理由は、ｊ＝２はｂ２−，ｂ２＋ともに負になるためである。式（７）の制約条件における０≧ｂ２＋は、２つあるクラスの双方とも原点０を跨がないようにするための制約条件である。つまり、ｂ１−≦０≦ｂ１＋やｂ２−≦０≦ｂ２＋という状況を避けるためには、次の３通りが考えられる。両方のクラスが正側（つまり、０≦ｂ１−かつ０≦ｂ２−）、両方のクラスが負側（つまり、ｂ１＋≦０かつｂ２＋≦０）、各クラスが原点０を挟んで互いに反対側。式（７）では最後のケースを採用している。【００８７】
Ｃ＝１の場合と同様に、（７）式は凸２次計画問題である。また、（２）式から（４）式を得たのと同様の手順で双対問題を導出し、双対問題を解くことで最適化を行うことも可能である。（７）式の双対問題も凸２次計画問題となる。【００８８】
［Ｃ≧３の場合］
学習データ記憶装置２２４から入力されたデータに関するクラスが３以上の一般の場合に、平行な複数の超平面の組を計算するには、入力されたクラスの任意の２つの組み合わせに対してＣ＝２の場合の最適化を実施し、得られた複数の超平面の組を利用して多数決をとることが考えられる。【００８９】
また例えば（８）式に示される最適化問題を解くことで、平行な複数の超平面の組を計算することもできる。【００９０】
2009041101.tif 000010
【００９１】
（８）式では（ａ）から（ｅ）の基準が、（ａ）第２項、（ｂ）第１項、（ｃ）第３項、（ｄ）第４項として表現されている。（ｅ）の基準に関してはψに関する制約条件によって表現されている。以下、（８）式における目的関数および制約条件について説明を補足する。【００９２】
式（２）および式（７）で示した１クラスおよび２クラスの場合には、特徴空間におけるクラスの領域の順序が決まっていたため、各クラスの領域を原点から遠ざけるという方式で、基準（ｅ）を達成することができた。しかし、一般に多クラスになるとクラスの領域の順序をどのようにすれば良いかは自明でない。一つの案として、それを全ての組み合わせで解く方法が考えられるが、計算量が多くなる欠点がある。（８）式による最適化は、組み合わせを考えること無しに、自動的に順序が最も良いものに決定されるようにしている。【００９３】
そのために、まず、図１３に示されるように、原点周りの未知クラスの領域がｂ０−とｂ０＋に挟まれた領域とし、そのための制約条件としてｂ０＋≧０、０≧ｂ０−を置き、目的関数の第４項で、その領域を最大化している（第４項の符号はマイナスで、目的関数が最小化だから最大化になる）。【００９４】
次に、既知クラスの領域（および原点周りの未知クラス領域）が図１４に示すようにオーバーラップしてはいけないための制約が必要になる。このような制約は、各クラスの領域の順序と原点との位置関係が明示的に決まっている場合には、ｂ１−≦０、ｂ２−≧０、ｂ２＋≦ｂ３−というように明示的に順序として重複しない制約を書くことが可能である。全組み合わせを考える場合にはこのような制約条件をつけるが、（８）式は順序が事前にわからないことを前提としているため、そのような制約は書けない。そこで、ｂｊ−≧ｂｋ＋−Ψｊｋ−、ｂｊ＋≦ｂｋ−＋Ψｊｋ＋、Ψｊｋ−Ψｊｋ＋＝０および、ｂｊ−≧ｂ０＋−Ψｊ０−、ｂ０−≦ｂｊ＋＋Ψｊ０＋、Ψｊ０−Ψｊ０＋＝０という制約条件により、既知クラスの領域（および原点周りの未知クラス領域）がオーバーラップしてはいけないための制約を課している。【００９５】
また、ｂｊ−≧ｂｋ＋−Ψｊｋ−に関して、ｂｊ−≧ｂｋ＋が成り立つ場合（つまり、クラスｊがクラスｋより正の方向にある）には、Ψｊｋ−＝０になる。逆に、ｂｊ＋≦ｂｋ−＋Ψｊｋ＋に関して、ｂｊ＋≦ｂｋ−が成り立つ場合（つまり、クラスｊがクラスｋより負の方向にある）には、Ψｊｋ＋＝０になる。クラス間の重複がないためには、ｂｊ−≧ｂｋ＋またはｂｊ＋≦ｂｋ−とならなくてはならないので、Ψｊｋ−＝０またはΨｊｋ＋＝０が成り立つ必要がある。したがって、Ψｊｋ−Ψｊｋ＋＝０という制約によって、各クラスの重複がないという制約を課すことが可能である。【００９６】
Ψｊ０＋，Ψｊ０−に関する制約条件は、原点周りの領域と既知クラスの領域に関する同様の制約を表す。【００９７】
次に本実施の形態の動作を説明する。【００９８】
本実施の形態の動作は、超平面集合計算装置３２０による超平面の計算処理と、この計算された超平面を利用した分類対象データ１５０の分類処理とに大別される。【００９９】
超平面集合計算装置３２０による超平面の計算処理では、超平面集合最適化部３２１によって、学習データ記憶装置２２４から分類が既知の学習データを読み込み、この学習データに対する分類誤差の最小化、超平面集合の複雑性の最小化、および各クラス領域の大きさの最小化を同時に最適化する複数の超平面を計算して、記憶装置２２２に記憶する。次に、超平面集合出力部３２３によって、記憶装置２２２から複数の超平面を規定するデータを読み出し、超平面集合３２４として超平面集合記憶装置３１０に記憶する。【０１００】
本実施の形態のデータ分類装置３００の動作は、図１に示した第１の実施の形態に関わるデータ分類装置１００の動作と基本的に同じである。【０１０１】
このように本実施の形態によれば、第１の実施の形態と同様の効果が得られると同時に、超平面集合計算装置３２０によって計算した最新の複数の超平面で超平面集合記憶装置３１０に記憶された複数の超平面を置き換えることができ、学習データの充実にあわせて性能の向上を図ることができる効果がある。【０１０２】
［第４の実施の形態］
図１５を参照すると、本発明の第４の実施の形態に関わるデータ分類装置４００は、図７に示した第２の実施の形態に関わるデータ分類装置２００と比較して、分離面集合記憶装置２１０に代えて超球面集合記憶装置４１０を有する点、および分離面集合計算装置２２０に代えて超球面集合計算装置４２０が接続されている点で相違する。【０１０３】
超球面集合計算装置４２０は、１以上の既知クラスに分類されている複数の学習データおよびその分類に基づいて、特徴空間を１以上の既知クラスにそれぞれ対応する１以上のクラス領域とそれ以外の未知クラス領域とに分離する複数の超球面であって、１クラス当たり２個以上で且つ互いに同心の複数の超球面を計算する装置である。また、超球面集合記憶装置４１０は、超球面集合計算装置４２０で計算された複数の超球面を規定する情報を記憶する装置である。【０１０４】
図１６を参照すると、超球面集合計算装置４２０は、超球面集合最適化部４２１と、記憶装置２２２と、数理計画問題計算装置４２２と、超球面集合出力部４２３とを備え、学習データ記憶装置２２４から学習用のデータを入力し、最適化された超球面集合４２４を出力する。すなわち、超球面集合計算装置４２０は、データ分類のために複数の同心の超球面を計算する。従って、本実施の形態のデータ分類装置４００では、図３に示されるように同心の超球面によって各クラスの領域を区切ることによってデータ分類を実現する。【０１０５】
以下で、超球面の具体的な計算手順に関して、幾つかの例をもとに説明を行う。【０１０６】
学習データ記憶装置２２４から入力されたデータに関するクラスのインデックスをｊ＝１，…，Ｃとする。以下では、ｘｉｊをｊ番目のクラスに属するｉ番目のデータとし、各クラスに属する学習データの数をＮｊとする。超球面の中心をｃ、半径をｒとすると、超球面は｜φ（ｘ）−ｃ｜２＝ｒと書ける。今、超球面は同心であるため、中心ｃは各クラスで共通であるから、ｃおよびｊ番目のクラスに対する外側の半径ｒｊ＋および内側の半径ｒｊ−が超球面集合最適化部４２１によって最適化される。【０１０７】
最適化のための基準としては、以下の３つの条件を同時に最適化することによって、ｃおよび各ｊに対するｒｊ＋およびｒｊ−を計算する。
（ａ’）分類誤差最小化
（ｂ’）ｃの複雑性最小化
（ｃ’）各既知クラス領域の大きさ最小化。【０１０８】
なお、上記以外にさらに、
（ｄ’）原点周囲の未知領域の大きさ最大化
（ｅ’）各クラスの領域が重ならない
の１つないしは双方をも同時に最適化することによってｃおよび各ｊに対するｒｊ＋およびｒｊ−を計算しても良い。【０１０９】
（ａ’）から（ｅ’）の複数の基準を同時に最適化する具体的な例は、例えば式（９）が挙げられる。式（９）はクラスが幾つでも適用可能であるが、クラスの順序が判っていることが前提となっている。【０１１０】
2009041101.tif 000011
【０１１１】
式（９）によって計算される超球面集合の一例を図１７に示す。式（９）は目的関数および制約条件の凹部分と凸部分が加算の形になっているため、Ｃｏｎｃａｖｅ−Ｃｏｎｖｅｘ  Ｐｒｏｃｅｄｕｒｅ（文献８参照）などを利用して効率的に最適解を計算することが可能である。以下、式（９）における目的関数および制約条件について説明する。【０１１２】
式（９）の目的関数における第１項は、クラスｊの領域の外半径−内半径という形なので、最適化の基準（ｃ’）のために必要な項である。第２項は、式（７）の第２項に相当し、最適化の基準（ａ’）のために必要な項である。第３項は、最適化の基準（ｄ’）のために必要な項である。その理由は次の通りである。【０１１３】
まず、制約条件のｃ２≦ｍｉｎ｛ｒｊ−｝２から、原点は一番小さい超球面の内側にあることが制約として課される。ｃ２は原点と超球面の中心との距離で、ｍｉｎ｛ｒｊ−｝２は超球面の中心と一番内側の超球面との距離（つまり半径）であるためである。つまり、一番内側の球の内部が、原点周りの未知領域になる。したがって、ｍｉｎ｛ｒｊ−｝２を大きくすることによって、基準（ｄ’）が達成される。【０１１４】
基準（ｂ’）は式（９）の目的関数の中では明示的には含まれておらず、制約条件の中に暗黙的に含まれている。基準（ｅ’）は、ｒｊ＋≧ｒｊ−とｒｊ＋１−≧ｒｊ＋によって制約されている。【０１１５】
次に本実施の形態の動作を説明する。【０１１６】
本実施の形態の動作は、超球面集合計算装置４２０による超球面の計算処理と、この計算された超球面を利用した分類対象データ１５０の分類処理とに大別される。【０１１７】
超球面集合計算装置４２０による超球面の計算処理では、超球面集合最適化部４２１が、学習データ記憶装置２２４から分類が既知の学習データを読み込み、この学習データに対する分類誤差の最小化、超球面集合の複雑性の最小化、および各クラス領域の大きさの最小化を同時に最適化する複数の超球面を計算して、記憶装置２２２に記憶する。次に、超球面集合出力部３２３が、記憶装置２２２から複数の超球面を規定するデータを読み出し、超球面集合４２４として超球面集合記憶装置４１０に記憶する。【０１１８】
本実施の形態のデータ分類装置４００の動作は、図１に示した第１の実施の形態に関わるデータ分類装置１００の動作と基本的に同じである。【０１１９】
このように本実施の形態によれば、第１の実施の形態と同様の効果が得られると同時に、超球面集合計算装置４２０によって計算した最新の複数の超球面で超球面集合記憶装置４１０に記憶された複数の超球面を置き換えることができる。そのため、学習データの充実にあわせて性能の向上を図ることができる効果がある。【０１２０】
以上本発明の実施の形態について説明したが、本発明は以上の実施の形態にのみ限定されず、その他各種の付加変更が可能である。また、本発明のデータ分類装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態におけるデータ分類装置、分離面集合計算装置、超平面集合計算装置、超球面集合計算装置として機能させ、前述した処理を行わせる。
【図１】
2009041101.tif 000012
【図２】
2009041101.tif 000013
【図３】
2009041101.tif 000014
【図４】
2009041101.tif 000015
【図５】
2009041101.tif 000016
【図６】
2009041101.tif 000017
【図７】
2009041101.tif 000018
【図８】
2009041101.tif 000019
【図９】
2009041101.tif 000020
【図１０】
2009041101.tif 000021
【図１１】
2009041101.tif 000022
【図１２】
2009041101.tif 000023
【図１３】
2009041101.tif 000024
【図１４】
2009041101.tif 000025
【図１５】
2009041101.tif 000026
【図１６】
2009041101.tif 000027
【図１７】
2009041101.tif 000028
【図１８】
2009041101.tif 000029
【図１９】
2009041101.tif 000030
【国際調査報告】
2009041101.tif 000031
2009041101.tif 000032