複数クラス分類装置、複数クラス分類方法および複数クラス分類プログラム
【課題】適切な二元符合表を生成し、分類精度を向上させた分類装置を提供する。
【解決手段】訓練データおよび学習の繰り返し回数を入力するデータ入力部１２と、前記訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化部１５と、前記二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習部１６と、前記個々の学習結果の係数を計算する係数計算部１７と、前記訓練データ、繰り返し回数、二元符号表、学習器および係数を蓄積する蓄積部１３と、前記蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力部１８と、前記各部で使用される作業情報の初期化、更新と、前記各部の動作管理を行う管理部１４と、を備える。
【解決手段】訓練データおよび学習の繰り返し回数を入力するデータ入力部１２と、前記訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化部１５と、前記二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習部１６と、前記個々の学習結果の係数を計算する係数計算部１７と、前記訓練データ、繰り返し回数、二元符号表、学習器および係数を蓄積する蓄積部１３と、前記蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力部１８と、前記各部で使用される作業情報の初期化、更新と、前記各部の動作管理を行う管理部１４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、教師あり機械学習に関し、特にテキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置、方法、プログラムに関する。
【背景技術】
【０００２】
従来、複数クラス分類を行うには、個々のクラスのラベルを二元符合表で符号化し、符号化した各列を２クラス学習器で学習し、その学習結果を係数で統合する手法があった。
【０００３】
例えば非特許文献１では、表１の手順でＮ個の訓練データ｛（ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝を学習する。
【０００４】
ここでｘnは入カベクトル、 ｙn∈｛１，・・・，Ｋ｝はどのクラスに属するかのラベルである。
【０００５】
【表１】
【０００６】
従来法の学習結果でクラス分類を行う際には、分類したいデータｘと各クラスとの距離
【０００７】
【数１】
【０００８】
を計算し、距離が一番近いクラスを選択する。すなわち、ｘのクラスはａｒｇk∈Kｍｉｎ△（ｋ，ｘ）となる。
【０００９】
また、２クラス学習器としてはｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ，決定木，ｐｅｒｃｅｐｔｒｏｎ等を用いる。
【００１０】
例えば、ｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓは
【００１１】
【数２】
【００１２】
の形式の学習器である（図３で表現される学習器）。
【００１３】
ここで、ｘ(j)はｘのｊ番目の属性値，ｐ∈｛１，−１｝，ｑは閾値であり、与えられたデータからｊ，ｐ，ｑを求める。
【００１４】
従来のクラス分類法の動作は以下のとおりである。
【００１５】
下記の、表２のような訓練データ、および（３）に示す二元符合表が与えられたとする。
【００１６】
【表２】
【００１７】
【数３】
【００１８】
１回目のループでは、二元符合表の一列目の値により、クラス１、２が符合１、クラス３、４が符合−１となる。すなわち、ｎ＝１，・・・，８のデータが符合１，ｎ＝９，・・・，１６が−１になる。
【００１９】
この条件により、２クラス学習器は下記のように学習する：
【００２０】
【数４】
【００２１】
また、その係数は、α1＝１１．５１２９２５４６４９２０２２８となる。
【００２２】
２回目のループでは、２クラス学習器は下記のように学習する：
【００２３】
【数５】
【００２４】
また、その係数は、α1＝１１．５１２９２５４６４９２０２２８となる。
【００２５】
学習結果で△（ｋ，ｘn）を計算すると、表３に示すように正しく分類されていることが分かる。
【００２６】
【表３】
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】Ｒ．Ｅ．Ｓｃｈａｐｉｒｅ，“Ｕｓｉｎｇ ｏｕｔｐｕｔ ｃｏｄｅｓ ｔｏ ｂｏｏｓｔ ｍｕｌｔｉｃｌａｓｓ ｌｅａｒｎｉｎｇ ｐｒｏｂｌｅｍｓ”， Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｏｕｒｔｅｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ， １９９７
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上述した従来の複数クラス分類方法では、与える二元符合表によって分類精度が変動する問題があった。
【００２９】
例えば表４に示す訓練データが与えられたとする。
【００３０】
【表４】
【００３１】
そして、下記数６に示す二元符号表Ａ、数７に示す二元符号表Ｂで学習を行ったとする。
【００３２】
数６の二元符合表Ａでの学習結果Ａは表５となり、２４個中８個が正しく学習できない。しかし、数７の二元符合表Ｂで学習すると、表６の学習結果Ｂに示すように全て正しく学習できる。
【００３３】
このように与える二元符合表によって分類精度が大きく変動する。
【００３４】
【数６】
【００３５】
【表５】
【００３６】
【数７】
【００３７】
【表６】
【００３８】
本発明は、上記課題を解決するものであり、その目的は、適切な二元符合表を生成し、分類精度を向上させた複数クラス分類装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３９】
上記課題を解決するための本発明の複数クラス分類装置は、テキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置であって、訓練データおよび学習の繰り返し回数を入力するデータ入力手段と、前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化手段と、前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習手段と、前記２クラス学習手段の個々の学習結果の係数を計算する係数計算手段と、前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積手段と、前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力手段と、前記クラス符号化手段、２クラス学習手段および係数計算手段で使用される作業情報の初期化、更新と、前記クラス符号化手段、２クラス学習手段、係数計算手段および学習結果出力手段の各動作を管理する管理手段と、を備えたことを特徴としている。
【発明の効果】
【００４０】
本発明によれば、適切な二元符合表を生成することができ、これによって少ない繰り返し回数、すなわち、２クラス学習器の個数が少なくても、分類精度を向上させることができる。
【図面の簡単な説明】
【００４１】
【図１】本発明の複数クラス分類装置の構成図。
【図２】本発明の複数クラス分類方法のフローチャート。
【図３】従来の２クラス学習器としてのｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓの説明図。
【図４】本発明のクラス符号化手段の作用の説明図（その１）。
【図５】本発明のクラス符号化手段の作用の説明図（その２）。
【図６】本発明のクラス符号化手段の作用の説明図（その３）。
【発明を実施するための形態】
【００４２】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００４３】
図１は本発明の複数クラス分類装置の実施形態例を示す構成図である。本実施形態例の複数クラス分類装置は、入力端末１１と、データ入力手段としてのデータ入力部１２と、蓄積手段としての蓄積部１３と、管理手段としての管理部１４と、クラス符号化手段としてのクラス符号化部１５と、２クラス学習手段としての２クラス学習部１６と、係数計算手段としての係数計算部１７と、学習結果出力手段としての学習結果出力部１８と、出力端末１９とを有する。
【００４４】
前記各部１２〜１８の後述する各機能は、例えばコンピュータによって達成される。
【００４５】
データ入力部１２は、入力端末１１からの訓練データおよび繰り返し回数Ｔを入力する。
【００４６】
蓄積部１３は、前記入力された訓練データ、繰り返し回数、および、クラス符号化部１５で計算される二元符合表、２クラス学習部１６で学習された学習器、係数計算部１７で計算された係数を蓄積する。
【００４７】
管理部１４は、クラス符号化部１５、２クラス学習部１６、係数計算部１７で使用される作業情報の初期化・更新を行う。また、クラス符号化部１５、２クラス学習部１６、係数計算部１７を繰り返し回数だけ呼び出し、最後に学習結果出力部１８を呼び出す。
【００４８】
クラス符号化部１５は、前記訓練データが他のクラスに誤って分類されている程度を集計してクラス間で分類が上手く行っていない程度を示す非分離度を計算する。
【００４９】
次に、この非分離度を基に二元符合列（二元符合表の現在の繰り返し数で指定された列）を生成するが、非分離度の高いクラス対に異なる符合、すなわち、１と−１、を割り当て、かつ、同じ符合が割り当てられたグループのクラス対の非分離度は低くしたい。
【００５０】
このため、まず、０という割り当てを保留した値を導入する。次に、０の値を持つグループのクラスは無視し、１，−１の値を持つグループでは、異なる値のクラス間で非分離度が大きくなるように、同一値のクラス間で非分離度が小さくなるように分割度を定め、この分割度が高くなるように分割候補を作成する。
【００５１】
さらに、前記分割候補に従って２クラス学習部１６と同様の学習器で予備学習を行い、予備学習の結果に整合する、すなわち、各クラスの符合と訓練データの予備学習の結果の符合とが等しくなる割合が高くなるように、二元符合列を作成する。
【００５２】
このようにクラス符号化部１５は、非分離度を基に、０という割り当てを保留した値を導入し、分割度が高くなるように分割候補を作成することで優先して分離すべきクラス群、すなわち、１や−１が割り振られたグループ、を選択する。こうすることで学習が難しい符合化を避けることができる。
【００５３】
例えば図４のように、訓練データに対し、二元符合列を［１，−１，１，−１］Tとして与えると、ｘ(1)，ｘ(2)のどちらの属性を使っても上手く分離できず、前記図３、式（２）に示すｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ等では学習が難しい。
【００５４】
これに対し、本発明のクラス符号化部１５は、［１、−１，０，０］Tの分割候補を作成し、図５のように予備学習を行う。その後、図６のように予備学習結果に整合する符合を割り振ることで適切な二元符合列が生成できる。
【００５５】
このように本発明のクラス符号化部１５は、適切な二元符合表を生成することができる。
【００５６】
２クラス学習部１６は、前記作成された二元符合表および重み付きの訓練データを用いて２クラスの学習器を学習する。
【００５７】
係数計算部１７は、前記学習した２クラス学習部１６の係数を計算する。
【００５８】
学習結果出力部１８は、前記蓄積部１３に蓄積された情報に基づいて、分類したいデータｘとクラスｋとの距離を計算する関数（複数クラスを分類するための関数）を出力する。
【００５９】
出力端末１９は、学習結果出力部１８から出力された前記関数を例えばディスプレイに表示する。
【００６０】
図２は本発明の複数クラス分類方法の実施形態例のフローチャートであり、図１の装置の各部が実施する処理の手順を示している。
【００６１】
図２において、
ｓｔｅｐ１１： データ入力部１２が訓練データ、および、繰り返し回数Ｔを入力する。
ｓｔｅｐ１２： 管理部１４が作業情報を初期化する。
ｓｔｅｐ１３： クラス符号化部１５がクラス符合化を行う。
ｓｔｅｐ１４： ２クラス学習部１６が２クラス学習器の学習を行う。
ｓｔｅｐ１５： 係数計算部１７が係数計算を行う。
ｓｔｅｐ１６： 管理部１４が作業情報を更新する。
ｓｔｅｐ１７： ｔ≦Ｔか否かを判定し、ｔ≦Ｔならば（繰り返し回数Ｔを超えていないとき）ｓｔｅｐ１３へ戻る。
ｓｔｅｐ１８： 学習結果出力部１８が学習結果を出力する。
【００６２】
次に図１の装置の構成の具体例を以下に説明する。
【００６３】
データ入力部１２は、訓練データ｛（Ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝、および、繰り返し数Ｔを入力し、蓄積部１３に蓄積する。
【００６４】
蓄積部１３は、前記データ入力部１２により入力された訓練データ｛（Ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝、および、繰り返し数Ｔと、クラス符号化部１５により作成された二元符合表Ｍ（ｋ，ｔ）と、２クラス学習部１６により学習された２クラス学習器列ｆtと、係数計算部１７により計算された係数列ａtとを蓄積する。
【００６５】
管理部１４は、下記の初期化を行う：
【００６６】
【数８】
【００６７】
また、ｔ≦Ｔの間（繰り返し回数Ｔを超えていない間）、クラス符号化部１５、２クラス学習部１６、係数計算部１７を呼び出す。
【００６８】
さらにｔ≦Ｔの間、下記の更新を行う：
【００６９】
【数９】
【００７０】
クラス符号化部１５は、蓄積部１３の蓄積情報に基づいて、まず非分離度表Ｌt（ｉ，ｊ），ｉ，ｊ＝１，・・・，Ｋを計算する：
【００７１】
【数１０】
【００７２】
次にクラス符号化部１５は、分割候補ｓ（ｋ），ｋ＝１，・・・，Ｋを下記の手順で生成する：
ｓｔｅｐ １３１： 分割候補の初期化
ｓ（ｋ）＝０，ｋ＝１，・・・，Ｋ
ｓｔｅｐ １３２： 非分離度表で最大値を持つクラス対（ａ、ｂ）を取得し、１、−１を割り当てる。
【００７３】
（ａ、ｂ）＝ａｒｇ(i,j)ｍａｘＬt（ｉ，ｊ）
ｓ（ａ）＝ １
ｓ（ｂ）＝−１
ｓｔｅｐ １３３： 未選択のクラス集合Ｉを作成する。
【００７４】
Ｉ＝｛１，・・・，Ｋ｝−｛ａ、ｂ｝
ｓｔｅｐ １３４： 未選択のクラスから値を割り当てたとき分割度ｃｕｔが最大となるクラスと値を選択する。
【００７５】
【数１１】
【００７６】
ｓｔｅｐ １３５： 選択したクラスｕに値ｃを割り当て、未選択クラスから除く。
【００７７】
【数１２】
【００７８】
ｓｔｅｐ １３６： Ｉ≠φならｓｔｅｐ４へ。
【００７９】
次にクラス符号化部１５は、前記生成された分割候補で以下のように予備学習を行う：
【００８０】
【数１３】
【００８１】
２クラス学習器ｇを重みｗ（ｎ）付きのデータ｛（Ｘn，ｓ（ｙn）｜ｎ＝１，・・・，Ｎ｝で学習する。この学習には、２クラス学習部１６と同じものを用いる。ｓ（ｋ）＝０となるクラスのデータは、ｗ（ｎ）＝０となるので、この学習では無視されることになる。
【００８２】
次にクラス符号化部１５は、前記予備学習の結果に整合する二元符合列を作成する：
Ｍ（ｋ，ｔ）＝ｓｇｎ（μ（ｋ，ｔ）），ｋ＝１，・・・，Ｋ …（１６）
ここで、
【００８３】
【数１４】
【００８４】
２クラス学習部１６は、Ｕt,および、Ｄt（ｎ）の更新を次のようにして行い、２クラス学習器ｆtの学習を行う。
【００８５】
【数１５】
【００８６】
ｆtを重みＤt（ｎ）付きのデータ｛（ｘn，Ｍ（ｙn，ｔ））｝用いて学習させる。
【００８７】
２クラス学習器はｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ を用いる。すなわち、
【００８８】
【数１６】
【００８９】
の形式で、与えられたデータからｊ，ｐ，ｑを求める。
【００９０】
ここで、ｘ(j)はｘのｊ番目の属性値，ｐ∈｛１，−１｝，ｑは閾値である。
【００９１】
係数計算部１７は、以下の計算を行なってεtおよびαtの更新を行う。
【００９２】
【数１７】
【００９３】
ここで、ε0は１０-10等の値を用いる。
【００９４】
学習結果出力部１８は、学習結果として、データｘとクラスｋとの距離
【００９５】
【数１８】
【００９６】
を計算する関数（複数クラスを分類するための関数）を出力する。
【００９７】
次に図１の装置の動作の具体例を以下に説明する。
【００９８】
まず、表４の訓練データ｛（ｘn，ｙn）｝と繰り返し数Ｔ＝４がデータ入力部１２から入力され、蓄積部１３に蓄積される。
【００９９】
【表７】
【０１００】
そして、クラス符号化部１６で生成される分割候補は、［１，−１，０，０］Tとなる。
【０１０１】
また、クラス符号化部１５で行なわれた予備学習の結果は、
【０１０２】
【数１９】
【０１０３】
となる。
【０１０４】
そしてμ（ｋ，１）＝［２２．０，−２６．０，−１０．０，１４．０］Tと求まるので、蓄積部１３の二元符合表の１列目を［１，−１，−１，１］Tとして、クラス符合化部１５から管理部１４の処理に戻る。
【０１０５】
次に管理部１４は２クラス学習部１６を呼び出す。２クラス学習部１６は、蓄積部１３の二元符合表の１列目の［１，−１，−１，１］Tを用いて学習を行い、
【０１０６】
【数２０】
【０１０７】
を得る。これを蓄積部１３に蓄積して管理部１４の処理に戻る。
【０１０８】
続いて管理部１４は係数計算部１７を呼び出す。係数計算部１７は、式（２２）、（２３）を用いて、α1＝１．１９８９４７６３６３９９１８５１を計算し、蓄積部１３に蓄積して管理部１４の処理に戻る。
【０１０９】
【数２１】
【０１１０】
、α2＝１１．５１２９２５４６４９２０２２８が蓄積部１３に蓄積される。
【０１１１】
【数２２】
【０１１２】
、α3＝０．８３２４９４９１８１６０６１０９が蓄積部１３に蓄積される。
【０１１３】
【数２３】
【０１１４】
ｔ＝５≦Ｔではないので管理部１４は、学習結果出力部１８を呼び出す。学習結果出力部１８は△（ｋ，ｘ）を計算する関数を出力し、終了する。
【０１１５】
この学習結果を用いて訓練データを分類すると、表８のように全て正しく分類される。
【０１１６】
【表８】
【０１１７】
本実施例では、２クラス学習器にｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓを用いたが、決定木やｐｅｒｃｅｐｔｒｏｎ等の様々な学習器を利用することもできる。
【０１１８】
また、本実施形態の複数クラス分類装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の複数クラス分類方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【０１１９】
１１…入力端末
１２…データ入力部
１３…蓄積部
１４…管理部
１５…クラス符合化部
１６…２クラス学習部
１７…係数計算部
１８…学習結果出力部
１９…出力端末
【技術分野】
【０００１】
本発明は、教師あり機械学習に関し、特にテキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置、方法、プログラムに関する。
【背景技術】
【０００２】
従来、複数クラス分類を行うには、個々のクラスのラベルを二元符合表で符号化し、符号化した各列を２クラス学習器で学習し、その学習結果を係数で統合する手法があった。
【０００３】
例えば非特許文献１では、表１の手順でＮ個の訓練データ｛（ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝を学習する。
【０００４】
ここでｘnは入カベクトル、 ｙn∈｛１，・・・，Ｋ｝はどのクラスに属するかのラベルである。
【０００５】
【表１】
【０００６】
従来法の学習結果でクラス分類を行う際には、分類したいデータｘと各クラスとの距離
【０００７】
【数１】
【０００８】
を計算し、距離が一番近いクラスを選択する。すなわち、ｘのクラスはａｒｇk∈Kｍｉｎ△（ｋ，ｘ）となる。
【０００９】
また、２クラス学習器としてはｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ，決定木，ｐｅｒｃｅｐｔｒｏｎ等を用いる。
【００１０】
例えば、ｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓは
【００１１】
【数２】
【００１２】
の形式の学習器である（図３で表現される学習器）。
【００１３】
ここで、ｘ(j)はｘのｊ番目の属性値，ｐ∈｛１，−１｝，ｑは閾値であり、与えられたデータからｊ，ｐ，ｑを求める。
【００１４】
従来のクラス分類法の動作は以下のとおりである。
【００１５】
下記の、表２のような訓練データ、および（３）に示す二元符合表が与えられたとする。
【００１６】
【表２】
【００１７】
【数３】
【００１８】
１回目のループでは、二元符合表の一列目の値により、クラス１、２が符合１、クラス３、４が符合−１となる。すなわち、ｎ＝１，・・・，８のデータが符合１，ｎ＝９，・・・，１６が−１になる。
【００１９】
この条件により、２クラス学習器は下記のように学習する：
【００２０】
【数４】
【００２１】
また、その係数は、α1＝１１．５１２９２５４６４９２０２２８となる。
【００２２】
２回目のループでは、２クラス学習器は下記のように学習する：
【００２３】
【数５】
【００２４】
また、その係数は、α1＝１１．５１２９２５４６４９２０２２８となる。
【００２５】
学習結果で△（ｋ，ｘn）を計算すると、表３に示すように正しく分類されていることが分かる。
【００２６】
【表３】
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】Ｒ．Ｅ．Ｓｃｈａｐｉｒｅ，“Ｕｓｉｎｇ ｏｕｔｐｕｔ ｃｏｄｅｓ ｔｏ ｂｏｏｓｔ ｍｕｌｔｉｃｌａｓｓ ｌｅａｒｎｉｎｇ ｐｒｏｂｌｅｍｓ”， Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｏｕｒｔｅｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ， １９９７
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上述した従来の複数クラス分類方法では、与える二元符合表によって分類精度が変動する問題があった。
【００２９】
例えば表４に示す訓練データが与えられたとする。
【００３０】
【表４】
【００３１】
そして、下記数６に示す二元符号表Ａ、数７に示す二元符号表Ｂで学習を行ったとする。
【００３２】
数６の二元符合表Ａでの学習結果Ａは表５となり、２４個中８個が正しく学習できない。しかし、数７の二元符合表Ｂで学習すると、表６の学習結果Ｂに示すように全て正しく学習できる。
【００３３】
このように与える二元符合表によって分類精度が大きく変動する。
【００３４】
【数６】
【００３５】
【表５】
【００３６】
【数７】
【００３７】
【表６】
【００３８】
本発明は、上記課題を解決するものであり、その目的は、適切な二元符合表を生成し、分類精度を向上させた複数クラス分類装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３９】
上記課題を解決するための本発明の複数クラス分類装置は、テキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置であって、訓練データおよび学習の繰り返し回数を入力するデータ入力手段と、前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化手段と、前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習手段と、前記２クラス学習手段の個々の学習結果の係数を計算する係数計算手段と、前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積手段と、前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力手段と、前記クラス符号化手段、２クラス学習手段および係数計算手段で使用される作業情報の初期化、更新と、前記クラス符号化手段、２クラス学習手段、係数計算手段および学習結果出力手段の各動作を管理する管理手段と、を備えたことを特徴としている。
【発明の効果】
【００４０】
本発明によれば、適切な二元符合表を生成することができ、これによって少ない繰り返し回数、すなわち、２クラス学習器の個数が少なくても、分類精度を向上させることができる。
【図面の簡単な説明】
【００４１】
【図１】本発明の複数クラス分類装置の構成図。
【図２】本発明の複数クラス分類方法のフローチャート。
【図３】従来の２クラス学習器としてのｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓの説明図。
【図４】本発明のクラス符号化手段の作用の説明図（その１）。
【図５】本発明のクラス符号化手段の作用の説明図（その２）。
【図６】本発明のクラス符号化手段の作用の説明図（その３）。
【発明を実施するための形態】
【００４２】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００４３】
図１は本発明の複数クラス分類装置の実施形態例を示す構成図である。本実施形態例の複数クラス分類装置は、入力端末１１と、データ入力手段としてのデータ入力部１２と、蓄積手段としての蓄積部１３と、管理手段としての管理部１４と、クラス符号化手段としてのクラス符号化部１５と、２クラス学習手段としての２クラス学習部１６と、係数計算手段としての係数計算部１７と、学習結果出力手段としての学習結果出力部１８と、出力端末１９とを有する。
【００４４】
前記各部１２〜１８の後述する各機能は、例えばコンピュータによって達成される。
【００４５】
データ入力部１２は、入力端末１１からの訓練データおよび繰り返し回数Ｔを入力する。
【００４６】
蓄積部１３は、前記入力された訓練データ、繰り返し回数、および、クラス符号化部１５で計算される二元符合表、２クラス学習部１６で学習された学習器、係数計算部１７で計算された係数を蓄積する。
【００４７】
管理部１４は、クラス符号化部１５、２クラス学習部１６、係数計算部１７で使用される作業情報の初期化・更新を行う。また、クラス符号化部１５、２クラス学習部１６、係数計算部１７を繰り返し回数だけ呼び出し、最後に学習結果出力部１８を呼び出す。
【００４８】
クラス符号化部１５は、前記訓練データが他のクラスに誤って分類されている程度を集計してクラス間で分類が上手く行っていない程度を示す非分離度を計算する。
【００４９】
次に、この非分離度を基に二元符合列（二元符合表の現在の繰り返し数で指定された列）を生成するが、非分離度の高いクラス対に異なる符合、すなわち、１と−１、を割り当て、かつ、同じ符合が割り当てられたグループのクラス対の非分離度は低くしたい。
【００５０】
このため、まず、０という割り当てを保留した値を導入する。次に、０の値を持つグループのクラスは無視し、１，−１の値を持つグループでは、異なる値のクラス間で非分離度が大きくなるように、同一値のクラス間で非分離度が小さくなるように分割度を定め、この分割度が高くなるように分割候補を作成する。
【００５１】
さらに、前記分割候補に従って２クラス学習部１６と同様の学習器で予備学習を行い、予備学習の結果に整合する、すなわち、各クラスの符合と訓練データの予備学習の結果の符合とが等しくなる割合が高くなるように、二元符合列を作成する。
【００５２】
このようにクラス符号化部１５は、非分離度を基に、０という割り当てを保留した値を導入し、分割度が高くなるように分割候補を作成することで優先して分離すべきクラス群、すなわち、１や−１が割り振られたグループ、を選択する。こうすることで学習が難しい符合化を避けることができる。
【００５３】
例えば図４のように、訓練データに対し、二元符合列を［１，−１，１，−１］Tとして与えると、ｘ(1)，ｘ(2)のどちらの属性を使っても上手く分離できず、前記図３、式（２）に示すｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ等では学習が難しい。
【００５４】
これに対し、本発明のクラス符号化部１５は、［１、−１，０，０］Tの分割候補を作成し、図５のように予備学習を行う。その後、図６のように予備学習結果に整合する符合を割り振ることで適切な二元符合列が生成できる。
【００５５】
このように本発明のクラス符号化部１５は、適切な二元符合表を生成することができる。
【００５６】
２クラス学習部１６は、前記作成された二元符合表および重み付きの訓練データを用いて２クラスの学習器を学習する。
【００５７】
係数計算部１７は、前記学習した２クラス学習部１６の係数を計算する。
【００５８】
学習結果出力部１８は、前記蓄積部１３に蓄積された情報に基づいて、分類したいデータｘとクラスｋとの距離を計算する関数（複数クラスを分類するための関数）を出力する。
【００５９】
出力端末１９は、学習結果出力部１８から出力された前記関数を例えばディスプレイに表示する。
【００６０】
図２は本発明の複数クラス分類方法の実施形態例のフローチャートであり、図１の装置の各部が実施する処理の手順を示している。
【００６１】
図２において、
ｓｔｅｐ１１： データ入力部１２が訓練データ、および、繰り返し回数Ｔを入力する。
ｓｔｅｐ１２： 管理部１４が作業情報を初期化する。
ｓｔｅｐ１３： クラス符号化部１５がクラス符合化を行う。
ｓｔｅｐ１４： ２クラス学習部１６が２クラス学習器の学習を行う。
ｓｔｅｐ１５： 係数計算部１７が係数計算を行う。
ｓｔｅｐ１６： 管理部１４が作業情報を更新する。
ｓｔｅｐ１７： ｔ≦Ｔか否かを判定し、ｔ≦Ｔならば（繰り返し回数Ｔを超えていないとき）ｓｔｅｐ１３へ戻る。
ｓｔｅｐ１８： 学習結果出力部１８が学習結果を出力する。
【００６２】
次に図１の装置の構成の具体例を以下に説明する。
【００６３】
データ入力部１２は、訓練データ｛（Ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝、および、繰り返し数Ｔを入力し、蓄積部１３に蓄積する。
【００６４】
蓄積部１３は、前記データ入力部１２により入力された訓練データ｛（Ｘn，ｙn）｜ｎ＝１，・・・，Ｎ｝、および、繰り返し数Ｔと、クラス符号化部１５により作成された二元符合表Ｍ（ｋ，ｔ）と、２クラス学習部１６により学習された２クラス学習器列ｆtと、係数計算部１７により計算された係数列ａtとを蓄積する。
【００６５】
管理部１４は、下記の初期化を行う：
【００６６】
【数８】
【００６７】
また、ｔ≦Ｔの間（繰り返し回数Ｔを超えていない間）、クラス符号化部１５、２クラス学習部１６、係数計算部１７を呼び出す。
【００６８】
さらにｔ≦Ｔの間、下記の更新を行う：
【００６９】
【数９】
【００７０】
クラス符号化部１５は、蓄積部１３の蓄積情報に基づいて、まず非分離度表Ｌt（ｉ，ｊ），ｉ，ｊ＝１，・・・，Ｋを計算する：
【００７１】
【数１０】
【００７２】
次にクラス符号化部１５は、分割候補ｓ（ｋ），ｋ＝１，・・・，Ｋを下記の手順で生成する：
ｓｔｅｐ １３１： 分割候補の初期化
ｓ（ｋ）＝０，ｋ＝１，・・・，Ｋ
ｓｔｅｐ １３２： 非分離度表で最大値を持つクラス対（ａ、ｂ）を取得し、１、−１を割り当てる。
【００７３】
（ａ、ｂ）＝ａｒｇ(i,j)ｍａｘＬt（ｉ，ｊ）
ｓ（ａ）＝ １
ｓ（ｂ）＝−１
ｓｔｅｐ １３３： 未選択のクラス集合Ｉを作成する。
【００７４】
Ｉ＝｛１，・・・，Ｋ｝−｛ａ、ｂ｝
ｓｔｅｐ １３４： 未選択のクラスから値を割り当てたとき分割度ｃｕｔが最大となるクラスと値を選択する。
【００７５】
【数１１】
【００７６】
ｓｔｅｐ １３５： 選択したクラスｕに値ｃを割り当て、未選択クラスから除く。
【００７７】
【数１２】
【００７８】
ｓｔｅｐ １３６： Ｉ≠φならｓｔｅｐ４へ。
【００７９】
次にクラス符号化部１５は、前記生成された分割候補で以下のように予備学習を行う：
【００８０】
【数１３】
【００８１】
２クラス学習器ｇを重みｗ（ｎ）付きのデータ｛（Ｘn，ｓ（ｙn）｜ｎ＝１，・・・，Ｎ｝で学習する。この学習には、２クラス学習部１６と同じものを用いる。ｓ（ｋ）＝０となるクラスのデータは、ｗ（ｎ）＝０となるので、この学習では無視されることになる。
【００８２】
次にクラス符号化部１５は、前記予備学習の結果に整合する二元符合列を作成する：
Ｍ（ｋ，ｔ）＝ｓｇｎ（μ（ｋ，ｔ）），ｋ＝１，・・・，Ｋ …（１６）
ここで、
【００８３】
【数１４】
【００８４】
２クラス学習部１６は、Ｕt,および、Ｄt（ｎ）の更新を次のようにして行い、２クラス学習器ｆtの学習を行う。
【００８５】
【数１５】
【００８６】
ｆtを重みＤt（ｎ）付きのデータ｛（ｘn，Ｍ（ｙn，ｔ））｝用いて学習させる。
【００８７】
２クラス学習器はｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓ を用いる。すなわち、
【００８８】
【数１６】
【００８９】
の形式で、与えられたデータからｊ，ｐ，ｑを求める。
【００９０】
ここで、ｘ(j)はｘのｊ番目の属性値，ｐ∈｛１，−１｝，ｑは閾値である。
【００９１】
係数計算部１７は、以下の計算を行なってεtおよびαtの更新を行う。
【００９２】
【数１７】
【００９３】
ここで、ε0は１０-10等の値を用いる。
【００９４】
学習結果出力部１８は、学習結果として、データｘとクラスｋとの距離
【００９５】
【数１８】
【００９６】
を計算する関数（複数クラスを分類するための関数）を出力する。
【００９７】
次に図１の装置の動作の具体例を以下に説明する。
【００９８】
まず、表４の訓練データ｛（ｘn，ｙn）｝と繰り返し数Ｔ＝４がデータ入力部１２から入力され、蓄積部１３に蓄積される。
【００９９】
【表７】
【０１００】
そして、クラス符号化部１６で生成される分割候補は、［１，−１，０，０］Tとなる。
【０１０１】
また、クラス符号化部１５で行なわれた予備学習の結果は、
【０１０２】
【数１９】
【０１０３】
となる。
【０１０４】
そしてμ（ｋ，１）＝［２２．０，−２６．０，−１０．０，１４．０］Tと求まるので、蓄積部１３の二元符合表の１列目を［１，−１，−１，１］Tとして、クラス符合化部１５から管理部１４の処理に戻る。
【０１０５】
次に管理部１４は２クラス学習部１６を呼び出す。２クラス学習部１６は、蓄積部１３の二元符合表の１列目の［１，−１，−１，１］Tを用いて学習を行い、
【０１０６】
【数２０】
【０１０７】
を得る。これを蓄積部１３に蓄積して管理部１４の処理に戻る。
【０１０８】
続いて管理部１４は係数計算部１７を呼び出す。係数計算部１７は、式（２２）、（２３）を用いて、α1＝１．１９８９４７６３６３９９１８５１を計算し、蓄積部１３に蓄積して管理部１４の処理に戻る。
【０１０９】
【数２１】
【０１１０】
、α2＝１１．５１２９２５４６４９２０２２８が蓄積部１３に蓄積される。
【０１１１】
【数２２】
【０１１２】
、α3＝０．８３２４９４９１８１６０６１０９が蓄積部１３に蓄積される。
【０１１３】
【数２３】
【０１１４】
ｔ＝５≦Ｔではないので管理部１４は、学習結果出力部１８を呼び出す。学習結果出力部１８は△（ｋ，ｘ）を計算する関数を出力し、終了する。
【０１１５】
この学習結果を用いて訓練データを分類すると、表８のように全て正しく分類される。
【０１１６】
【表８】
【０１１７】
本実施例では、２クラス学習器にｄｅｃｉｓｉｏｎ ｓｔｕｍｐｓを用いたが、決定木やｐｅｒｃｅｐｔｒｏｎ等の様々な学習器を利用することもできる。
【０１１８】
また、本実施形態の複数クラス分類装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の複数クラス分類方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【０１１９】
１１…入力端末
１２…データ入力部
１３…蓄積部
１４…管理部
１５…クラス符合化部
１６…２クラス学習部
１７…係数計算部
１８…学習結果出力部
１９…出力端末
【特許請求の範囲】
【請求項１】
テキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置であって、
訓練データおよび学習の繰り返し回数を入力するデータ入力手段と、
前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化手段と、
前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習手段と、
前記２クラス学習手段の個々の学習結果の係数を計算する係数計算手段と、
前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積手段と、
前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力手段と、
前記クラス符号化手段、２クラス学習手段および係数計算手段で使用される作業情報の初期化、更新と、前記クラス符号化手段、２クラス学習手段、係数計算手段および学習結果出力手段の各動作を管理する管理手段と、
を備えたことを特徴とする複数クラス分類装置。
【請求項２】
前記クラス符号化手段は、前記非分離度を基に、符号の割り当てを保留した値を利用して前記分割候補を生成することを特徴とする請求項１に記載の複数クラス分類装置。
【請求項３】
テキストや画像などのデータを２以上のクラスに分類する複数クラス分類方法であって、
データ入力手段が、訓練データおよび学習の繰り返し回数を入力するデータ入力ステップと、
クラス符号化手段が、前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化ステップと、
２クラス学習手段が、前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習ステップと、
係数計算手段が、前記２クラス学習手段の個々の学習結果の係数を計算する係数計算ステップと、
管理手段が、前記クラス符号化手段、２クラス学習手段および係数計算手段の呼び出しと、該各手段で使用される作業情報の初期化および更新を行うステップと、
蓄積手段が、前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積ステップと、
管理手段が、学習結果出力手段を呼び出すステップと、
学習結果出力手段が、前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力ステップと、
を備えたことを特徴とする複数クラス分類方法。
【請求項４】
前記クラス符号化ステップは、前記非分離度を基に、符号の割り当てを保留した値を利用して前記分割候補を生成することを特徴とする請求項３に記載の複数クラス分類方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させることを特徴とする複数クラス分類プログラム。
【請求項１】
テキストや画像などのデータを２以上のクラスに分類する複数クラス分類装置であって、
訓練データおよび学習の繰り返し回数を入力するデータ入力手段と、
前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化手段と、
前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習手段と、
前記２クラス学習手段の個々の学習結果の係数を計算する係数計算手段と、
前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積手段と、
前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力手段と、
前記クラス符号化手段、２クラス学習手段および係数計算手段で使用される作業情報の初期化、更新と、前記クラス符号化手段、２クラス学習手段、係数計算手段および学習結果出力手段の各動作を管理する管理手段と、
を備えたことを特徴とする複数クラス分類装置。
【請求項２】
前記クラス符号化手段は、前記非分離度を基に、符号の割り当てを保留した値を利用して前記分割候補を生成することを特徴とする請求項１に記載の複数クラス分類装置。
【請求項３】
テキストや画像などのデータを２以上のクラスに分類する複数クラス分類方法であって、
データ入力手段が、訓練データおよび学習の繰り返し回数を入力するデータ入力ステップと、
クラス符号化手段が、前記データ入力手段によって入力された訓練データがクラス間で上手く分類されていない程度を示す非分離度を計算し、該非分離度を基に分割候補を生成し、該分割候補に従って予備学習を行い、該予備学習の結果に整合する符合を割り振って二元符号表を生成するクラス符号化ステップと、
２クラス学習手段が、前記クラス符号化手段によって生成された二元符号表および重み付の訓練データを用いて２クラスの学習器を学習する２クラス学習ステップと、
係数計算手段が、前記２クラス学習手段の個々の学習結果の係数を計算する係数計算ステップと、
管理手段が、前記クラス符号化手段、２クラス学習手段および係数計算手段の呼び出しと、該各手段で使用される作業情報の初期化および更新を行うステップと、
蓄積手段が、前記データ入力手段により入力された訓練データ、繰り返し回数、前記クラス符号化手段により生成された二元符号表、前記２クラス学習手段により学習された学習器および前記係数計算手段により計算された係数を蓄積する蓄積ステップと、
管理手段が、学習結果出力手段を呼び出すステップと、
学習結果出力手段が、前記蓄積手段に蓄積された情報に基づいて複数クラスを分類するための関数を出力する学習結果出力ステップと、
を備えたことを特徴とする複数クラス分類方法。
【請求項４】
前記クラス符号化ステップは、前記非分離度を基に、符号の割り当てを保留した値を利用して前記分割候補を生成することを特徴とする請求項３に記載の複数クラス分類方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させることを特徴とする複数クラス分類プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−１０７９７５（Ｐ２０１１−１０７９７５Ａ）
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願番号】特願２００９−２６２１９１（Ｐ２００９−２６２１９１）
【出願日】平成２１年１１月１７日（２００９．１１．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願日】平成２１年１１月１７日（２００９．１１．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]