JP3761868B2

JP3761868B2 - Data classification apparatus, data classification method, and program for causing computer to execute the method

Info

Publication number: JP3761868B2
Application number: JP2003074367A
Authority: JP
Inventors: 尚中川
Original assignee: 株式会社ジャストシステム
Priority date: 2003-03-18
Filing date: 2003-03-18
Publication date: 2006-03-29
Anticipated expiration: 2023-03-18
Also published as: JP2004280712A

Description

【０００１】
【発明の属する技術分野】
この発明は、入力データが第１の分類あるいは第２の分類のいずれに分類されるかを判別する２値分類器を複数使用して前記入力データの多値分類を行うデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムに関する。
【０００２】
【従来の技術】
サポートベクターマシン（ＳＶＭ：ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅ）は汎化能力の高い２値分類器であるが、複数のＳＶＭを組み合わせることで多値分類器へと拡張した場合に、処理速度の遅さがネックとなっている。
【０００３】
ＳＶＭを利用した多値分類アルゴリズムとして、代表的なものにｏｎｅｖｓｒｅｓｔ法、ｐａｉｒｗｉｓｅ法、ＤＤＡＧ（ＤｅｃｉｓｉｏｎＤｉｒｅｃｔｅｄＡｃｙｃｌｉｃＧｒａｐｈ）法などがある。このうち最も分類が高速なＤＤＡＧ法は、「ＪｏｈｎＣ．Ｐｌａｔｔ，ＮｅｌｌｏＣｒｉｓｔｉａｎｉ，ＪｏｈｎＳｈａｗｅ−Ｔａｙｌｏｒ（２０００）ＬａｒｇｅＭａｒｇｉｎＤＡＧｓｆｏｒＭｕｌｔｉｃｌａｓｓＣｌａｓｓｉｆｉｃａｔｉｏｎ．ＩｎＡｄｖａｎｃｅｓｉｎＮＩＰＳ１２，ＭＩＴＰｒｅｓｓ．」で発表している通り、ｐａｉｒｗｉｓｅ法の高速化手法である。
【０００４】
図６は、ＤＤＡＧ法による多値分類の手順を模式的に示す説明図である。ＤＤＡＧ法ではまず分類（分類先となるカテゴリ）、すなわち同図の例では「Ａ」「Ｂ」「Ｃ」「Ｄ」の４つを一列に並べる。次に分類対象である入力データが、列の先頭の分類「Ａ」と末尾の分類「Ｄ」のいずれに分類されるかをＳＶＭで判別する（図中「Ａ／Ｄ判別」）。そして判別されなかったほうの分類、たとえば上記ＳＶＭでＡと判別された場合には、Ｄを列から棄却（削除）して、次に入力データが当該列の先頭「Ａ」と末尾「Ｃ」のいずれに分類されるかを他のＳＶＭで判別する（図中「Ａ／Ｃ判別」）。
【０００５】
以後は上記と同様の処理を、列内の分類が１つになるまで繰り返し、最終的に残った分類を多値分類の結果として出力する。ｎ値分類に必要な２値分類の回数が、ｐａｉｒｗｉｓｅ法ではｎＣ２回であるのに対し、ＤＤＡＧ法ではｎ−１回となるので、そのぶん処理時間を短縮できる。
【０００６】
【発明が解決しようとする課題】
しかしながらＤＤＡＧ法をもってしても、実用上十分な速度での多値分類を実現できない場合がある。そしてその原因としては、ＳＶＭそのものの遅さもさることながら、上記手法が個々の２値分類にかかる時間の長短を考慮していないことが挙げられる。
【０００７】
たとえば図６で示した例において、多値分類にかかる平均時間（平均多値分類時間）は、
平均多値分類時間＝（Ａ／Ｄ判別時間）＋｛ｐ（Ａ／Ｃ判別時間）＋（１−ｐ）（Ｂ／Ｄ判別時間）｝＋｛ｑ（Ａ／Ｂ判別時間）＋ｒ（Ｂ／Ｃ判別時間）＋（１−ｑ−ｒ）（Ｃ／Ｄ判別時間）｝
ただしｐ：Ａ／Ｃ判別が実行される確率（０≦ｐ≦１）
ｑ：Ａ／Ｂ判別が実行される確率（０≦ｑ≦１）
ｒ：Ｂ／Ｃ判別が実行される確率（０≦ｒ≦１）
である。
【０００８】
したがって、Ａ〜Ｄの任意の２つの組み合わせのうち、たとえばＡとＤとの判別が最も時間のかかる２値分類だったとすると、それだけ上記時間は大きくなってしまう。言い換えれば、分類を１列に並べたときにたまたまＡが先頭、Ｄが末尾にあったというだけで、多値分類の都度この最も時間のかかるＡ／Ｄ判別を必ず経由することになり、無駄が大きい。
【０００９】
この発明は上記従来技術による問題を解決するため、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムを提供することを目的とする。
【００１０】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、この発明にかかるデータ分類装置は、入力データが第１の分類あるいは第２の分類のいずれに分類されるかを判別する２値分類器を複数使用して前記入力データの多値分類を行うデータ分類装置において、前記各２値分類器の特徴値を算出する特徴値算出手段と、前記特徴値算出手段により算出された特徴値にもとづいて前記各２値分類器の優先順位を決定する優先順位決定手段と、前記優先順位決定手段により決定された優先順位の高い順に前記２値分類器を使用して前記入力データの多値分類を行う多値分類手段と、を備えたことを特徴とする。
【００１１】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００１２】
また、この発明にかかるデータ分類装置は、上記に記載の発明において、前記２値分類器がＳＶＭであり、前記特徴値算出手段が前記各２値分類器の特徴値を、各ＳＶＭにおけるＳＶの個数あるいは各ＳＶＭにおけるすべてのＳＶの０でない要素の総数にもとづいて算出することを特徴とする。
【００１３】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはＳＶの個数などから算出されたその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００１４】
また、この発明にかかるデータ分類装置は、上記に記載の発明において、前記優先順位決定手段が、前記特徴値算出手段により算出された特徴値の昇順にソートしたときの各２値分類器の順位を前記優先順位として決定することを特徴とする。
【００１５】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値が小さいものから順に使用される。
【００１６】
また、この発明にかかるデータ分類装置は、上記に記載の発明において、前記多値分類手段が、前記第１の分類および前記第２の分類がいずれも棄却されていない２値分類器のうち、前記優先順位決定手段により決定された優先順位が最も高い２値分類器を使用して前記入力データの２値分類を行うとともに、前記第１の分類または前記第２の分類のうち、前記２値分類において前記入力データが分類されなかったものを棄却することを、所定の条件が満足されるまで繰り返すことを特徴とする。
【００１７】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００１８】
また、この発明にかかるデータ分類装置は、上記に記載の発明において、前記条件が、棄却された分類の個数が所定の個数に達したか、あるいは次に使用する２値分類器につき前記特徴値算出手段により算出された特徴値が所定の閾値に達したことであることを特徴とする。
【００１９】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用されるとともに、ある程度以上にコスト高となる２値分類器は使用されない。
【００２０】
また、この発明にかかるデータ分類方法は、入力データが第１の分類あるいは第２の分類のいずれに分類されるかを判別する２値分類器を複数使用して前記入力データの多値分類を行うデータ分類方法において、前記各２値分類器の特徴値を算出する特徴値算出工程と、前記特徴値算出工程で算出された特徴値にもとづいて前記各２値分類器の優先順位を決定する優先順位決定工程と、前記優先順位決定工程で決定された優先順位の高い順に前記２値分類器を使用して前記入力データの多値分類を行う多値分類工程と、を含んだことを特徴とする。
【００２１】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００２２】
また、この発明にかかるデータ分類方法は、上記に記載の発明において、前記２値分類器がＳＶＭであり、前記特徴値算出工程では前記各２値分類器の特徴値を、各ＳＶＭにおけるＳＶの個数あるいは各ＳＶＭにおけるすべてのＳＶの０でない要素の総数にもとづいて算出することを特徴とする。
【００２３】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはＳＶの個数などから算出されたその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００２４】
また、この発明にかかるデータ分類方法は、上記に記載の発明において、前記優先順位決定工程では、前記特徴値算出工程で算出された特徴値の昇順にソートしたときの各２値分類器の順位を前記優先順位として決定することを特徴とする。
【００２５】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値が小さいものから順に使用される。
【００２６】
また、この発明にかかるデータ分類方法は、上記に記載の発明において、前記多値分類工程では、前記第１の分類および前記第２の分類がいずれも棄却されていない２値分類器のうち、前記優先順位決定工程で決定された優先順位が最も高い２値分類器を使用して前記入力データの２値分類を行うとともに、前記第１の分類または前記第２の分類のうち、前記２値分類において前記入力データが分類されなかったものを棄却することを、所定の条件が満足されるまで繰り返すことを特徴とする。
【００２７】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用される。
【００２８】
また、この発明にかかるデータ分類方法は、上記に記載の発明において、前記条件が、棄却された分類の個数が所定の個数に達したか、あるいは次に使用する２値分類器につき前記特徴値算出工程で算出された特徴値が所定の閾値に達したことであることを特徴とする。
【００２９】
この発明によれば、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用されるとともに、ある程度以上にコスト高となる２値分類器は使用されない。
【００３０】
また、この発明にかかるプログラムによれば、上記に記載された方法がコンピュータによって実行される。
【００３１】
【発明の実施の形態】
以下に添付図面を参照して、この発明によるデータ分類装置、データ分類方法およびその方法をコンピュータに実行させるプログラムの好適な実施の形態を詳細に説明する。
【００３２】
図１は、この発明の実施の形態によるデータ分類装置のハードウエア構成の一例を示す説明図である。図中、１０１は装置全体を制御するＣＰＵを、１０２は基本入出力プログラムを記憶したＲＯＭを、１０３はＣＰＵ１０１のワークエリアとして使用されるＲＡＭを、それぞれ示している。
【００３３】
また、１０４はＣＰＵ１０１の制御にしたがってＨＤ（ハードディスク）１０５に対するデータのリード／ライトを制御するＨＤＤ（ハードディスクドライブ）を、１０５はＨＤＤ１０４の制御にしたがって書き込まれたデータを記憶するＨＤを、それぞれ示している。
【００３４】
また、１０６はＣＰＵ１０１の制御にしたがってＦＤ（フレキシブルディスク）１０７に対するデータのリード／ライトを制御するＦＤＤ（フレキシブルディスクドライブ）を、１０７はＦＤＤ１０６の制御にしたがって書き込まれたデータを記憶する着脱自在のＦＤを、それぞれ示している。
【００３５】
また、１０８はＣＰＵ１０１の制御にしたがってＣＤ−ＲＷ１０９に対するデータのリード／ライトを制御するＣＤ−ＲＷドライブを、１０９はＣＤ−ＲＷドライブ１０８の制御にしたがって書き込まれたデータを記憶する着脱自在のＣＤ−ＲＷを、それぞれ示している。
【００３６】
また、１１０はカーソル、メニュー、ウィンドウ、あるいは文字や画像などの各種データを表示するディスプレイを、１１１は文字、数値、各種指示などの入力のための複数のキーを備えたキーボードを、１１２は各種指示の選択や実行、処理対象の選択、マウスポインタの移動などを行うマウスを、それぞれ示している。
【００３７】
また、１１３は通信ケーブル１１４を介してＬＡＮやＷＡＮなどのネットワークに接続され、当該ネットワークとＣＰＵ１０１とのインターフェースとして機能するネットワークＩ／Ｆを、１００は上記各部を接続するためのバスを、それぞれ示している。
【００３８】
次に、図２はこの発明の実施の形態によるデータ分類装置の構成を機能的に示す説明図である。本発明によるデータ分類装置は、１日前と現在の天気・気温および気圧を入力データとし、そこから予想される１日後の天気を出力データとする。すなわち、データの分類として「晴れ」「曇り」「雨」の３つを用意し、上記入力がいずれの分類に該当するかを特定して、分類結果すなわち「晴れ」「曇り」「雨」のいずれかを出力する。
【００３９】
まず、２００はデータ入力部であり、後述する多値分類部２０２による分類の対象となるデータを取り込んで、後述するベクトル変換部２０１に出力する機能部である。上記データはキーボード１１１から入力されるのでも、ＨＤ１０５やＣＤ−ＲＷ１０９から読み出されるのでも、あるいはネットワークＩ／Ｆ１１３を介して他の情報処理装置などから受信されるのであってもよい。
【００４０】
データ入力部２００により取り込まれるデータは、具体的には
▲１▼１日前の天気（晴れ／曇り／雨のいずれか一つ）
▲２▼１日前の気温
▲３▼１日前の気圧
▲４▼現在の天気（晴れ／曇り／雨のいずれか一つ）
▲５▼現在の気温
▲６▼現在の気圧
の６つであるものとする。
【００４１】
２０１はベクトル変換部であり、データ入力部２００から入力したデータにもとづいて、当該データに代わる入力ベクトルを生成する機能部である。ここでは上記データを、下記１０個の要素からなるベクトルに変換するものとする。ベクトル内の各要素の意味はそれぞれ下記の通りである。なお、ｘ４やｘ５などで数値を変換しているのは、一般に、数値のスケールを揃えたほうが学習の効率が上がるためである。
【００４２】
入力ベクトル：（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）
ただしｘ１：１日前の天気が晴れの場合１、その他の場合０
ｘ２：１日前の天気が曇りの場合１、その他の場合０
ｘ３：１日前の天気が雨の場合１、その他の場合０
ｘ４：１日前の気温（摂氏）／１００
ｘ５：１日前の気圧（ｈＰａ）／１００−１０
ｘ６：現在の天気が晴れの場合１、その他の場合０
ｘ７：現在の天気が曇りの場合１、その他の場合０
ｘ８：現在の天気が雨の場合１、その他の場合０
ｘ９：現在の気温（摂氏）／１００
ｘ１０：現在の気圧（ｈＰａ）／１００−１０
【００４３】
たとえば、１日前の天気が晴れ、気温が２４℃、気圧が１０２０ｈＰａであり、現在の天気が曇り、気温が２２℃、気圧が１０１０ｈＰａであった場合は、当該データにつき生成される入力ベクトルは（１，０，０，０．２４，０．２０，０，１，０，０．２２，０．１０）となる。
【００４４】
次に、２０２は多値分類部であり、ベクトル変換部２０１から入力した入力ベクトルの分類を判定する機能部である。多値分類部２０２は、分類が「晴れ」か「曇り」かを判別するＳＶＭ甲２０２ａ、「晴れ」か「雨」かを判別するＳＶＭ乙２０２ｂ、「曇り」か「雨」かを判別するＳＶＭ丙２０２ｃ、および後述する手順により上記いずれかのＳＶＭを選択するＳＶＭ選択部２０２ｄを備えている。なお、ここでは分類が３つのため、ＳＶＭの数はそのうち任意の２つの組み合わせ（ペア）の数、すなわち₃Ｃ₂＝３であるが、一般に分類がｎ個ある場合、ＳＶＭの個数は_nＣ₂となる。
【００４５】
後述する手順による多値分類の前に、あらかじめ、多値分類部２０２内の個々のＳＶＭについて学習を行っておく必要がある。本発明では学習の方法は問わないため、たとえば「ＪｏｈｎＣ．Ｐｌａｔｔ（１９９８）ＳｅｑｕｅｎｔｉａｌＭｉｎｉｍａｌＯｐｔｉｍｉｚａｔｉｏｎ：ＡＦａｓｔＡｌｇｏｒｉｔｈｍｆｏｒＴｒａｉｎｉｎｇＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅｓ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔＭＳＲ−ＴＲ−９８−１４．」などに記載された任意の学習方法を取ればよい。
【００４６】
ここでは各ＳＶＭについて、ｐａｉｒｗｉｓｅ法に準じた学習を行うものとする。すなわち、あらかじめ分類が得られている教師データを用意しておき、ＳＶＭごとにそれぞれ下記のような学習を行う。
▲１▼教師データ中、出力が「晴れ」となる入力ベクトル群を正例、「曇り」となる入力ベクトル群を負例として、ＳＶＭ甲２０２ａを学習させる。
▲２▼教師データ中、出力が「晴れ」となる入力ベクトル群を正例、「雨」となる入力ベクトル群を負例として、ＳＶＭ乙２０２ｂを学習させる。
▲３▼教師データ中、出力が「曇り」となる入力ベクトル群を正例、「雨」となる入力ベクトル群を負例として、ＳＶＭ丙２０２ｃを学習させる。
【００４７】
なお、ＳＶＭのパラメータ（後述するｋｅｒｎｅｌ関数として何を利用するか、どの程度のエラーを許容するか、など）の選択方法については、本発明は特に関知しないが、たとえば「工藤拓、松本裕治（２０００）ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅを用いたＣｈｕｎｋ同定、情報処理学会研究報告ＮＬ−１４０」で示されているように、交差検定（ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ）法などの既知の方法によって、最適なパラメータを求めることが考えられる。
【００４８】
次に、２０３は特徴値算出部であり、多値分類部２０２内の個々のＳＶＭについて、その性能やパフォーマンスを示す特徴値を算出する機能部である。ここではＳＶＭの特徴値を、当該ＳＶＭを使用することのコストの観点からとらえ、コストとして具体的にはその処理時間、すなわち各ＳＶＭにおける２値分類にかかる時間を考えるものとする。処理時間が短いＳＶＭほど、当該ＳＶＭを使用することのコストは低く、逆に処理時間が長いＳＶＭほどコストは高い。
【００４９】
周知のように、一般にＳＶＭは下記の式を計算することにより２値分類を行う。
【数１】

ただしｓｇｎ：正負を判定する関数
Ｓｎ：ＳＶ（サポートベクター）の集合（学習によって得られる）
αｉ：ＳＶごとの重み（学習によって得られる）
ｙｉ：ＳＶが正例か負例かによって定まる数値
ｈ：定数（学習によって得られる）
【００５０】
なお、Ｋ（ｘｉ，ｘ）はＳＶ（ｘｉ）と入力ベクトル（ｘ）により算出されるｋｅｒｎｅｌ関数である。一般には、以下のようなｋｅｒｎｅｌ関数が利用される（ａ、ｂは適当な定数）。
Ｋ１（ｘ，ｙ）＝（＜ｘ，ｙ＞＋１）２
Ｋ２（ｘ，ｙ）＝ｅｘｐ（−｜｜ｘ−ｙ｜｜２／ａ）
Ｋ３（ｘ，ｙ）＝ｔａｎｈ（ａ＜ｘ，ｙ＞−ｂ）
【００５１】
上記（１）式から、分類時の計算時間を左右するのはＳＶの数、すなわちｋｅｒｎｅｌ関数Ｋを通る回数であることが分かる。そこで、あるＳＶＭの処理時間の指標として、当該ＳＶＭにおけるＳＶの個数が利用できる。
【００５２】
また、個々のＳＶを利用したｋｅｒｎｅｌ関数Ｋの処理時間が予測できる場合、ＳＶの個数の代わりに、その和をもってＳＶＭによる処理時間の指標として用いることもできる。たとえば標準的な実装の場合、ＳＶ中の０でない要素数が多ければ多いほど、上記のｋｅｒｎｅｌ関数の計算時間は長くなる。そこで、すべてのＳＶの、０でない要素数の和を、ＳＶＭによる処理時間の指標として用いることができる。
【００５３】
特徴値算出部２０３は、上記の指標により推定した各ＳＶＭの処理時間、すなわち各ＳＶＭを使用することのコストを、特徴値として後述する優先順位決定部２０４に出力する。ここでは、ＳＶＭ甲２０２ａ／乙２０２ｂ／丙２０２ｃのＳＶの個数が、それぞれ１５／１０／３０であり、これに比例して各ＳＶＭの特徴値が、それぞれ下記のように算出されたものとする。
ＳＶＭ甲２０２ａ（晴れ／曇り判別）の特徴値：１５
ＳＶＭ乙２０２ｂ（晴れ／雨判別）の特徴値：１０
ＳＶＭ丙２０２ｃ（曇り／雨判別）の特徴値：３０
【００５４】
次に、２０４は優先順位決定部であり、多値分類部２０２内の各ＳＶＭの優先順位、すなわちどのＳＶＭを他のＳＶＭより優先的に使用するかを決定する機能部である。具体的には、特徴値算出部２０３で算出された特徴値の小さいＳＶＭが、特徴値の大きいＳＶＭよりも優先的に使用されるよう、ＳＶＭを特徴値の昇順にソートしたときの順位を各ＳＶＭの優先順位とする。なお、ソートの手法は特に問わないので、クイックソート法・マージソート法など、既知のアルゴリズムを利用すればよい。
【００５５】
上記の例では、特徴値（すなわちコスト、より具体的には処理時間）の最も小さいＳＶＭ乙２０２ｂの優先順位が１位、次に特徴値の小さいＳＶＭ甲２０２ａの優先順位が２位、特徴値の最も大きいＳＶＭ丙２０２ｃの優先順位が３位となる。
【００５６】
なお、特徴値算出部２０３で算出された処理時間（絶対処理時間）をそのまま利用するのでなく、下記式により相対処理時間を算出し、その順にソートするようにしてもよい。
【数２】

ただしＴｒ（ａ，ｂ）：分類ａと分類ｂとへの２値分類器の相対処理時間
Ｔａ（ａ，ｂ）：分類ａと分類ｂとへの２値分類器の絶対処理時間
Ｇ：多値分類器の結果となりうるすべての分類の集合
ｎ：Ｇの要素数（多値分類の分類数）
【００５７】
上記（２）式により、絶対処理時間が同一と予測された２値分類器でも、より関連する分類（上記式の場合、分類ａや分類ｂ）の平均処理時間が長いほうが、相対処理時間としては短くなる。これによって、処理時間の長い２値分類器（上記式の場合、分類ａ・分類ｂとその他の分類を判別する２値分類器）の代わりに、処理時間の短い２値分類器（上記式の場合、分類ａと分類ｂを判別する２値分類器）の利用が促進されることになる。
【００５８】
次に、図３はこの発明の実施の形態によるデータ分類装置における、２値分類の組み合わせによる多値分類処理の手順を示すフローチャートである。図示する処理に入る前に、あらかじめ以下のものを用意しておく。
ａ：優先順位の順にソートされたＳＶＭ（上記例ではＳＶＭ乙２０２ｂ、ＳＶＭ甲２０２ａ、ＳＶＭ丙２０２ｃの順）
ｂ：ａの中の位置を１つだけ保持できる機構（初期状態では先頭のＳＶＭ、上記例ではＳＶＭ乙２０２ｂを指す）
ｃ：２値分類で棄却された分類を複数保持できる機構（初期状態では空）
【００５９】
多値分類部２０２のＳＶＭ選択部２０２ｄは、ｂが指し示すＳＶＭに指示して２値分類を実行させ、判別された分類ｄと棄却された分類ｅを得る（ステップＳ３０１）。上記例では、まずＳＶＭ乙２０２ｂが呼び出されて「晴れ」または「雨」の判別が行われる。ここではたとえば判別された分類ｄが「雨」、棄却された分類ｅが「晴れ」であったものとする。
【００６０】
次に、ＳＶＭ選択部２０２ｄはステップＳ３０１で棄却された分類ｅを、上述のｃに追加する（ステップＳ３０２）。この時点で、ｃにはＳＶＭ乙２０２ｂにより棄却された「晴れ」のみが入っている状態となる。
【００６１】
そして、ＳＶＭ選択部２０２ｄはｃの要素数が、多値分類の分類数−１に達したかどうかを判定する（ステップＳ３０３）。ここでは分類の総数が「晴れ」「曇り」「雨」の３個であるため、ｃの要素数が２個に達したかどうかを判定することになる。そして、現時点ではｃの要素数は「晴れ」の１個のみであり、２個に満たないので（ステップＳ３０３：Ｎｏ）、次はステップＳ３０５に分岐する。
【００６２】
ｃの要素数が分類の総数−１に満たない場合、ＳＶＭ選択部２０２ｄは上記ｂが指し示す位置をａの中で１つ進める（ステップＳ３０５）。ここではｂの指し示す位置が、先頭のＳＶＭ乙２０２ｂから２番目のＳＶＭ甲２０２ａに切り替えられることになる。
【００６３】
そして、ＳＶＭ選択部２０２ｄはｂにより指し示されるＳＶＭが判別する２つの分類（ｆ・ｇ）を得る（ステップＳ３０６）。ここではＳＶＭ甲２０２ａは、「晴れ」または「曇り」を判別するので、ｆは「晴れ」ｇは「曇り」となる。なお、ｆとｇとは逆であってもよい。
【００６４】
次にＳＶＭ選択部２０２ｄは、ｆまたはｇのいずれかがｃの中にあるかどうか、すなわちｆまたはｇがすでに棄却された分類であるか否かを判定する（ステップＳ３０７）。ここではｆが「晴れ」で、ｃに格納された「晴れ」と一致するため（ステップＳ３０７：Ｙｅｓ）、ステップＳ３０５に戻ってさらにｂを１つ進める（ステップＳ３０５）。
【００６５】
そして、次のＳＶＭ丙２０２ｃではｆが「曇り」ｇが「雨」となり（ステップＳ３０６）、そのいずれもまだｃの中にはないので（ステップＳ３０７：Ｎｏ）、ステップＳ３０１に戻ってＳＶＭ丙２０２ｃに「曇り」または「雨」の判別を行わせる（ステップＳ３０１）。
【００６６】
ここで判別された分類ｄが「曇り」、棄却された分類ｅが「雨」であったとすると、ＳＶＭ選択部２０２ｄは棄却された分類ｅをｃに追加するとともに（ステップＳ３０２）、ｃの要素数が分類の総数−１、すなわち２に達したかどうかを判定する（ステップＳ３０３）。
【００６７】
そして、この時点でｃの要素数は「晴れ」および「雨」の２個に達したので（ステップＳ３０３：Ｙｅｓ）、ＳＶＭ選択部２０２ｄは分類結果出力部２０２ｅに多値分類の終了を通知し、これを受けた分類結果出力部２０２ｅでは、現時点でのｄ、すなわち「曇り」を多値分類の結果として出力する（ステップＳ３０４）。
【００６８】
上記手順は要するに、優先順位の高い順に並べたＳＶＭの中から、過去の２値分類で棄却されていない分類の組み合わせのＳＶＭを順次検索し、最初に見つかったＳＶＭで２値分類を行うとともに、この繰り返しをまだ棄却されていない分類が１つとなるまで続けるものである。
【００６９】
そして、優先順位は上述のようにＳＶＭの処理時間に応じて定められているので、上記手順により、処理時間の短いＳＶＭが優先的に選択されて使用されることになる。言い換えれば、処理時間の長いＳＶＭが使われる確率を下げることができ、たとえばＳＶＭ乙２０２ｂで晴れ、ＳＶＭ甲２０２ａでも晴れと判別された場合は、最も時間のかかるＳＶＭ丙２０２ｃの曇り／雨判別を経由しないで、多値分類の結果を得ることができる。
【００７０】
図４は、分類が４個だった場合の６個（＝₄Ｃ₂）のＳＶＭの使用確率を示すグラフ、図５は、分類が１０個だった場合の４５個（＝₁₀Ｃ₂）のＳＶＭの使用確率を示すグラフである。図示するように、「速い」すなわち処理時間の短いＳＶＭほど使用確率が高く、「遅い」すなわち処理時間の長いＳＶＭほど使用確率が低くなるので、全体として多値分類にかかる平均時間を短縮することができる。
【００７１】
なお、上述した実施の形態では２値分類器としてもっぱらＳＶＭを考えたが、２値分類器としてはこれに限らず、たとえばニューロンネットワークにおけるパーセプトロンなど、２つの分類を判別できるものなら何であってもよい。
【００７２】
また、上述した実施の形態では２値分類器の使用コストを、もっぱら時間の観点から把握したが、コストとしてはこれ以外にも、たとえば分類で発生するエラーなどを考えてもよい。
【００７３】
一例としてＳＶＭのエラー率の上限値は、教師データ中のＳＶの割合に比例することが知られている。そこで、時間が多少かかるとしてもできるだけ正確な分類結果が欲しいような場合は、エラー率が低く信頼できるＳＶＭを優先的に使用するため、「ＳＶの個数／教師データ数」を指標として各ＳＶＭの特徴値（信頼度の観点からとらえた特徴値）を算出するようにしてもよい。
【００７４】
また、コストとして２値分類器の使用料などを考えてもよい。たとえば、ある２値分類器による判別サービスが１回１０万円、別の２値分類器による判別サービスが１回５万円、というように、それぞれの２値分類の費用が異なる場合、より安価な２値分類が優先的に行われるよう、特徴値を上記費用に応じて算出する。
【００７５】
また、上述した実施の形態では棄却された分類がｎ−１個になるまで２値分類を続けたが、途中のどこかの２値分類器で分類を停止し、当該２値分類器による判別結果を多値分類の結果として出力するようにしてもよい。
【００７６】
一般に、データ数に対するＳＶの個数が少ないほど、ＳＶＭの汎化能力が高まることが知られている。つまりＳＶの数が多く、判別に時間がかかるＳＶＭほど、信頼性も低くなる傾向にある。そこで、ＳＶの数が少ない（信頼性が高い）ＳＶＭを利用できるうちは、上記の方法で分類の候補を絞り、
▲１▼上述のｂにより指し示されるＳＶＭのＳＶの数が一定の個数に達した場合
▲２▼上述のｃの要素数が一定の個数（具体的にはｎ−１）に達した場合
のいずれかの条件が満たされる場合に、多値分類を終了するようにしてもよい。
【００７７】
なお、上述したデータ入力部２００、ベクトル変換部２０１、多値分類部２０２、特徴値算出部２０３および優先順位決定部２０４は、具体的にはＨＤ１０５からＲＡＭ１０３に読み出されたプログラムをＣＰＵ１０１が実行することにより実現される。このプログラムはＨＤ１０５のほか、ＦＤ１０７、ＣＤ−ＲＷ１０９、ＭＯなどの各種の記録媒体に格納して配布することができ、ネットワークを介して配布することも可能である。
【００７８】
【発明の効果】
以上説明したようにこの発明は、入力データが第１の分類あるいは第２の分類のいずれに分類されるかを判別する２値分類器を複数使用して前記入力データの多値分類を行うデータ分類装置において、前記各２値分類器の特徴値を算出する特徴値算出手段と、前記特徴値算出手段により算出された特徴値にもとづいて前記各２値分類器の優先順位を決定する優先順位決定手段と、前記優先順位決定手段により決定された優先順位の高い順に前記２値分類器を使用して前記入力データの多値分類を行う多値分類手段と、を備えたので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置が得られるという効果を奏する。
【００７９】
また、この発明は、上記に記載の発明において、前記２値分類器がＳＶＭであり、前記特徴値算出手段が前記各２値分類器の特徴値を、各ＳＶＭにおけるＳＶの個数あるいは各ＳＶＭにおけるすべてのＳＶの０でない要素の総数にもとづいて算出するので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはＳＶの個数などから算出されたその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置が得られるという効果を奏する。
【００８０】
また、この発明は、上記に記載の発明において、前記優先順位決定手段が、前記特徴値算出手段により算出された特徴値の昇順にソートしたときの各２値分類器の順位を前記優先順位として決定するので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値が小さいものから順に使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置が得られるという効果を奏する。
【００８１】
また、この発明は、上記に記載の発明において、前記多値分類手段が、前記第１の分類および前記第２の分類がいずれも棄却されていない２値分類器のうち、前記優先順位決定手段により決定された優先順位が最も高い２値分類器を使用して前記入力データの２値分類を行うとともに、前記第１の分類または前記第２の分類のうち、前記２値分類において前記入力データが分類されなかったものを棄却することを、所定の条件が満足されるまで繰り返すので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置が得られるという効果を奏する。
【００８２】
また、この発明は、上記に記載の発明において、前記条件が、棄却された分類の個数が所定の個数に達したか、あるいは次に使用する２値分類器につき前記特徴値算出手段により算出された特徴値が所定の閾値に達したことであるので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用されるとともに、ある程度以上にコスト高となる２値分類器は使用されず、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類装置が得られるという効果を奏する。
【００８３】
また、この発明は、入力データが第１の分類あるいは第２の分類のいずれに分類されるかを判別する２値分類器を複数使用して前記入力データの多値分類を行うデータ分類方法において、前記各２値分類器の特徴値を算出する特徴値算出工程と、前記特徴値算出工程で算出された特徴値にもとづいて前記各２値分類器の優先順位を決定する優先順位決定工程と、前記優先順位決定工程で決定された優先順位の高い順に前記２値分類器を使用して前記入力データの多値分類を行う多値分類工程と、を含んだので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類方法が得られるという効果を奏する。
【００８４】
また、この発明は、上記に記載の発明において、前記２値分類器がＳＶＭであり、前記特徴値算出工程では前記各２値分類器の特徴値を、各ＳＶＭにおけるＳＶの個数あるいは各ＳＶＭにおけるすべてのＳＶの０でない要素の総数にもとづいて算出するので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはＳＶの個数などから算出されたその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類方法が得られるという効果を奏する。
【００８５】
また、この発明は、上記に記載の発明において、前記優先順位決定工程では、前記特徴値算出工程で算出された特徴値の昇順にソートしたときの各２値分類器の順位を前記優先順位として決定するので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値が小さいものから順に使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類方法が得られるという効果を奏する。
【００８６】
また、この発明は、上記に記載の発明において、前記多値分類工程では、前記第１の分類および前記第２の分類がいずれも棄却されていない２値分類器のうち、前記優先順位決定工程で決定された優先順位が最も高い２値分類器を使用して前記入力データの２値分類を行うとともに、前記第１の分類または前記第２の分類のうち、前記２値分類において前記入力データが分類されなかったものを棄却することを、所定の条件が満足されるまで繰り返すので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用され、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類方法が得られるという効果を奏する。
【００８７】
また、この発明は、上記に記載の発明において、前記条件が、棄却された分類の個数が所定の個数に達したか、あるいは次に使用する２値分類器につき前記特徴値算出工程で算出された特徴値が所定の閾値に達したことであるので、多値分類器を構成する複数の２値分類器は、それぞれの２値分類器を使用することのコスト（具体的にはその処理時間やエラー率など）を示す特徴値の大小に応じた順序で使用されるとともに、ある程度以上にコスト高となる２値分類器は使用されず、これによって、複数の２値分類器を効率的な順序で使用して多値分類を高速に行うことが可能なデータ分類方法が得られるという効果を奏する。
【００８８】
また、この発明によれば、上記に記載された方法をコンピュータに実行させることが可能なプログラムが得られるという効果を奏する。
【図面の簡単な説明】
【図１】この発明の実施の形態によるデータ分類装置のハードウエア構成の一例を示す説明図である。
【図２】この発明の実施の形態によるデータ分類装置の構成を機能的に示す説明図である。
【図３】この発明の実施の形態によるデータ分類装置における、２値分類の組み合わせによる多値分類処理の手順を示すフローチャートである。
【図４】この発明の実施の形態によるデータ分類装置において、分類が４個だった場合のＳＶＭの使用確率を示すグラフである。
【図５】この発明の実施の形態によるデータ分類装置において、分類が１０個だった場合のＳＶＭの使用確率を示すグラフである。
【図６】ＤＤＡＧ法による多値分類の手順を模式的に示す説明図である。
【符号の説明】
１００バス
１０１ＣＰＵ
１０２ＲＯＭ
１０３ＲＡＭ
１０４ＨＤＤ
１０５ＨＤ
１０６ＦＤＤ
１０７ＦＤ
１０８ＣＤ−ＲＷドライブ
１０９ＣＤ−ＲＷ
１１０ディスプレイ
１１１キーボード
１１２マウス
１１３ネットワークＩ／Ｆ
１１４通信ケーブル
２００データ入力部
２０１ベクトル変換部
２０２多値分類部
２０２ａＳＶＭ甲
２０２ｂＳＶＭ乙
２０２ｃＳＶＭ丙
２０２ｄＳＶＭ選択部
２０３特徴値算出部
２０４優先順位決定部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data classification device for performing multi-level classification of the input data by using a plurality of binary classifiers for determining whether the input data is classified into the first classification or the second classification, and data classification The present invention relates to a method and a program for causing a computer to execute the method.
[0002]
[Prior art]
A support vector machine (SVM: Support Vector Machine) is a binary classifier with a high generalization ability, but when it is expanded to a multi-value classifier by combining multiple SVMs, the slow processing speed is the bottleneck. It has become.
[0003]
Typical examples of multi-value classification algorithms using SVM include the one vsrest method, the pairwise method, and the DDAG (Decision Directed Acrylic Graph) method. Among them, the fastest DDAG method is “John C. Platt, Nello Christian, John Shawe-Taylor (2000) Large Margin DAGs for Multiclass Classification. In Advanced IP. , A method of speeding up the pairwise method.
[0004]
FIG. 6 is an explanatory diagram schematically showing the procedure of multi-value classification by the DDAG method. In the DDAG method, first, classification (category to be a classification destination), that is, four “A”, “B”, “C”, and “D” in the example of FIG. Next, it is determined by SVM whether the input data to be classified is classified into the first classification “A” or the last classification “D” of the column (“A / D determination” in the figure). If it is determined that the classification is not determined, for example, A in the SVM, D is rejected (deleted) from the column, and then the input data is the first “A” and the last “C” of the column. Which SVM is classified is determined by another SVM (“A / C determination” in the figure).
[0005]
Thereafter, the same processing as described above is repeated until the number of classifications in the column becomes one, and finally the remaining classification is output as the result of the multi-level classification. Since the number of binary classifications required for the n-value classification is nC2 times in the pairwise method, but n-1 times in the DDAG method, the processing time can be shortened.
[0006]
[Problems to be solved by the invention]
However, even with the DDAG method, there are cases in which multi-value classification at a practically sufficient speed cannot be realized. The reason is that the above method does not take into account the length of time required for individual binary classification, as well as the slowness of the SVM itself.
[0007]
For example, in the example shown in FIG. 6, the average time required for multi-level classification (average multi-level classification time) is
Average multilevel classification time = (A / D discrimination time) + {p (A / C discrimination time) + (1−p) (B / D discrimination time)} + {q (A / B discrimination time) + r (B / C discrimination time) + (1-q−r) (C / D discrimination time)}
However, p: probability that A / C discrimination is executed (0 ≦ p ≦ 1)
q: Probability that A / B discrimination is executed (0 ≦ q ≦ 1)
r: Probability of executing B / C discrimination (0 ≦ r ≦ 1)
It is.
[0008]
Therefore, if the discrimination between A and D is the most time-consuming binary classification among any two combinations of A to D, the time is increased accordingly. In other words, when the classifications are arranged in one column, it happens that A happens to be at the top and D is at the end, and every time a multi-level classification is made, the most time-consuming A / D discrimination must be made. Is big.
[0009]
In order to solve the above-described problems due to the prior art, the present invention provides a data classification apparatus, a data classification method, and a method for performing multi-level classification at high speed using a plurality of binary classifiers in an efficient order. An object is to provide a program to be executed by a computer.
[0010]
[Means for Solving the Problems]
In order to solve the above-mentioned problems and achieve the purpose, This invention The data classifying apparatus according to the present invention performs multi-level classification of the input data by using a plurality of binary classifiers that determine whether the input data is classified into the first class or the second class. The feature value calculating means for calculating the feature value of each binary classifier and the priority order determining means for determining the priority order of each binary classifier based on the feature value calculated by the feature value calculating means And multi-value classification means for performing multi-value classification of the input data using the binary classifier in descending order of priority determined by the priority determination means.
[0011]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in order according to size.
[0012]
Also, This invention The data classification device according to the above The binary classifier is an SVM, and the feature value calculation means calculates the feature value of each binary classifier as the number of SVs in each SVM or a non-zero element of all SVs in each SVM. It is characterized in that it is calculated based on the total number of.
[0013]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier have the cost of using each binary classifier (specifically, the processing time and error calculated from the number of SVs, etc.). Used in the order according to the magnitude of the feature value indicating the rate).
[0014]
Also, This invention The data classification device according to the above In the invention described in (2), the priority order determining means determines the order of each binary classifier when sorting in ascending order of the feature values calculated by the feature value calculating means as the priority order. .
[0015]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier have characteristic values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in ascending order.
[0016]
Also, This invention The data classification device according to the above In the invention according to claim 2, the priority determined by the priority determining means is a binary classifier in which neither the first classification nor the second classification is rejected. The binary classification of the input data is performed using the highest binary classifier, and the first classification or the second classification in which the input data is not classified in the binary classification The rejection is repeated until a predetermined condition is satisfied.
[0017]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in order according to size.
[0018]
Also, This invention The data classification device according to the above In the invention described in (2), the condition is that the number of rejected classifications reaches a predetermined number or the characteristic value calculated by the characteristic value calculating means for a binary classifier to be used next is a predetermined threshold value. It is characterized by having reached.
[0019]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. A binary classifier that is used in the order according to the size and is more expensive than a certain level is not used.
[0020]
Also, This invention The data classification method according to the present invention is a data classification method for performing multi-level classification of the input data using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification. A feature value calculating step for calculating a feature value of each binary classifier, and a priority order determining step for determining a priority order of each binary classifier based on the feature value calculated in the feature value calculation step And a multi-level classification step of performing multi-level classification of the input data using the binary classifier in descending order of priority determined in the priority determination step.
[0021]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in order according to size.
[0022]
Also, This invention The data classification method for the above In the invention described in the above, the binary classifier is an SVM, and in the feature value calculating step, the feature value of each binary classifier is set to the number of SVs in each SVM or a non-zero element of all SVs in each SVM. It is characterized in that it is calculated based on the total number of.
[0023]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier have the cost of using each binary classifier (specifically, the processing time and error calculated from the number of SVs, etc.). Used in the order according to the magnitude of the feature value indicating the rate).
[0024]
Also, This invention The data classification method for the above In the invention according to claim 1, in the priority order determining step, the order of each binary classifier when sorting in ascending order of the feature values calculated in the feature value calculating step is determined as the priority order. .
[0025]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier have characteristic values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in ascending order.
[0026]
Also, This invention The data classification method for the above In the invention according to claim 1, in the multi-level classification step, among the binary classifiers in which neither the first classification nor the second classification is rejected, the priority determined in the priority determination step is The binary classification of the input data is performed using the highest binary classifier, and the first classification or the second classification in which the input data is not classified in the binary classification The rejection is repeated until a predetermined condition is satisfied.
[0027]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Used in order according to size.
[0028]
Also, This invention The data classification method for the above In the invention described in (2), the condition is that the number of rejected classifications reaches a predetermined number, or the characteristic value calculated in the characteristic value calculation step for a binary classifier to be used next is a predetermined threshold value. It is characterized by having reached.
[0029]
This Departure According to Ming, a plurality of binary classifiers constituting a multi-level classifier are feature values indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. A binary classifier that is used in the order according to the size and is more expensive than a certain level is not used.
[0030]
Also, This invention According to the program the above Is executed by a computer.
[0031]
DETAILED DESCRIPTION OF THE INVENTION
Exemplary embodiments of a data classification device, a data classification method, and a program for causing a computer to execute the method according to the present invention will be described below in detail with reference to the accompanying drawings.
[0032]
FIG. 1 is an explanatory diagram showing an example of a hardware configuration of a data classification device according to an embodiment of the present invention. In the figure, 101 indicates a CPU that controls the entire apparatus, 102 indicates a ROM that stores basic input / output programs, and 103 indicates a RAM that is used as a work area of the CPU 101.
[0033]
Reference numeral 104 denotes an HDD (hard disk drive) that controls reading / writing of data with respect to the HD (hard disk) 105 according to the control of the

CPU

101, and 105 denotes an HD that stores data written according to the control of the HDD 104. Yes.
[0034]
Reference numeral 106 denotes an FDD (flexible disk drive) that controls reading / writing of data with respect to the FD (flexible disk) 107 according to the control of the

CPU

101, and 107 denotes a detachable FD that stores data written according to the control of the FDD 106. Respectively.
[0035]
Reference numeral 108 denotes a CD-RW drive that controls reading / writing of data with respect to the CD-RW 109 according to the control of the CPU 101, and reference numeral 109 denotes a removable CD-ROM that stores data written according to the control of the CD-RW drive 108. RW is shown respectively.
[0036]
Reference numeral 110 denotes a cursor, menu, window, or display for displaying various data such as characters and images, 111 denotes a keyboard having a plurality of keys for inputting characters, numerical values, various instructions, and the like, and 112 denotes various types. A mouse for selecting and executing instructions, selecting a processing target, moving a mouse pointer, and the like is shown.
[0037]
Reference numeral 113 denotes a network I / F that is connected to a network such as a LAN or a WAN via a communication cable 114, and functions as an interface between the network and the CPU 101. Reference numeral 100 denotes a bus for connecting the above-described units. ing.
[0038]
FIG. 2 is an explanatory diagram functionally showing the configuration of the data classification apparatus according to the embodiment of the present invention. The data classification apparatus according to the present invention uses the weather, temperature, and atmospheric pressure one day before and the current as input data, and the weather one day after that as the output data. In other words, three types of data “sunny”, “cloudy”, and “rain” are prepared, and the classification corresponding to the above input is specified, and the classification result, that is, “sunny” “cloudy” “rainy” Output one of them.
[0039]
First, reference numeral 200 denotes a data input unit, which is a functional unit that takes in data to be classified by a multilevel classification unit 202 described later and outputs the data to a vector conversion unit 201 described later. The data may be input from the keyboard 111, read from the HD 105 or CD-RW 109, or received from another information processing apparatus via the network I / F 113.
[0040]
Specifically, the data captured by the data input unit 200 is
(1) Weather one day ago (any one of sunny / cloudy / rainy)
▲ 2 ▼ The temperature one day ago
(3) Atmospheric pressure one day ago
▲ 4 ▼ Current weather (Sunny / Cloudy / Rain)
▲ 5 ▼ Current temperature
(6) Current barometric pressure
It is assumed that there are six.
[0041]
A vector conversion unit 201 is a functional unit that generates an input vector in place of the data based on data input from the data input unit 200. Here, it is assumed that the data is converted into a vector composed of the following 10 elements. The meaning of each element in the vector is as follows. The reason why numerical values are converted by x4, x5, etc. is because learning efficiency generally increases when the numerical values are scaled.
[0042]
Input vector: (x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
X1: 1 if the weather is clear 1 day ago, 0 otherwise
x2: 1 if the weather is cloudy one day ago, 0 otherwise
x3: 1 if rainy day before rain, 0 otherwise
x4: Temperature one day ago (Celsius) / 100
x5: Atmospheric pressure (hPa) / 100-10 before 1 day
x6: 1 if the current weather is clear, 0 otherwise
x7: 1 if the current weather is cloudy, 0 otherwise
x8: 1 if the current weather is rainy, 0 otherwise
x9: Current temperature (Celsius) / 100
x10: Current atmospheric pressure (hPa) / 100-10
[0043]
For example, if the weather one day ago is clear, the temperature is 24 ° C., and the atmospheric pressure is 1020 hPa, the current weather is cloudy, the temperature is 22 ° C., and the atmospheric pressure is 1010 hPa, the input vector generated for the data is ( 1, 0, 0, 0.24, 0.20, 0, 1, 0, 0.22, 0.10).
[0044]
Next, reference numeral 202 denotes a multi-value classification unit, which is a function unit that determines the classification of the input vector input from the vector conversion unit 201. The multi-value classifying unit 202 determines whether the classification is “sunny” or “cloudy”, SVM A 202a, “Sunny” or “rainy”, and SVM O 202b, “cloudy” or “rainy”. The SVM selection unit 202d that selects one of the SVMs according to the procedure described later is provided. Since there are three classifications here, the number of SVMs is the number of any two combinations (pairs) of them, that is, _Three C ₂ = 3, but if there are generally n classifications, the number of SVMs is _n C ₂ It becomes.
[0045]
Prior to multi-value classification according to the procedure described later, it is necessary to learn each SVM in the multi-value classification unit 202 in advance. In the present invention, the learning method does not matter, and is described in, for example, “John C. Platt (1998) Sequential Minimal Optimization: A Fast Algorithm for Training-SupportRector Machines. The learning method should be taken.
[0046]
Here, learning according to the pairwise method is performed for each SVM. That is, teacher data in which classification is obtained in advance is prepared, and the following learning is performed for each SVM.
(1) In the teacher data, the SVM A 202a is trained by taking an input vector group whose output is “clear” as a positive example and an input vector group where “cloudy” is a negative example.
(2) In the teacher data, the SVM B 202b is trained by taking an input vector group whose output is “clear” as a positive example and an input vector group whose output is “rain” as a negative example.
(3) In the teacher data, the SVM 丙 202c is learned by taking an input vector group whose output is “cloudy” as a positive example and an input vector group whose output is “rain” as a negative example.
[0047]
The present invention is not particularly concerned with the method of selecting SVM parameters (what to use as a kernel function, which will be described later, how much error is allowed, etc.), but for example, “Taku Kudo, Yuji Matsumoto ( 2000) As shown in Chunk identification using Support Vector Machine, Information Processing Society of Japan Research Report NL-140, an optimal parameter can be obtained by a known method such as a cross-validation method. Conceivable.
[0048]
Next, reference numeral 203 denotes a feature value calculation unit, which is a function unit that calculates the performance value and the feature value indicating the performance of each SVM in the multi-value classification unit 202. Here, the feature value of the SVM is taken from the viewpoint of the cost of using the SVM, and specifically, the processing time, that is, the time required for binary classification in each SVM is considered. The SVM with a shorter processing time has a lower cost for using the SVM. Conversely, the SVM with a longer processing time has a higher cost.
[0049]
As is well known, SVM generally performs binary classification by calculating the following equation.
[Expression 1]

However, sgn: a function for judging positive / negative
Sn: SV (support vector) set (obtained by learning)
αi: Weight for each SV (obtained by learning)
yi: Value determined by whether SV is positive or negative
h: Constant (obtained by learning)
[0050]
K (xi, x) is a kernel function calculated from SV (xi) and the input vector (x). In general, the following kernel function is used (a and b are appropriate constants).
K1 (x, y) = (<x, y> +1) 2
K2 (x, y) = exp (-|| xy- || 2 //)
K3 (x, y) = tanh (a <x, y> −b)
[0051]
From the above equation (1), it can be seen that it is the number of SVs, that is, the number of passes through the kernel function K, that affects the calculation time during classification. Therefore, the number of SVs in the SVM can be used as an index of the processing time of a certain SVM.
[0052]
Further, when the processing time of the kernel function K using each SV can be predicted, the sum thereof can be used as an index of the processing time by the SVM instead of the number of SVs. For example, in the standard implementation, the more the number of non-zero elements in the SV, the longer the calculation time of the above kernel function. Therefore, the sum of the number of non-zero elements of all SVs can be used as an index of processing time by SVM.
[0053]
The feature value calculation unit 203 outputs the processing time of each SVM estimated based on the above-described index, that is, the cost of using each SVM, as a feature value to the priority determination unit 204 described later. Here, it is assumed that the number of SVs of SVM A 202a / B 202b / Kin 202c is 15/10/30, respectively, and the characteristic value of each SVM is calculated as follows in proportion to this number. .
Feature value of SVM A 202a (clear / cloudy discrimination): 15
Feature value of SVM B 202b (sunny / rain discrimination): 10
SVM 丙 202c (cloud / rain discrimination) feature value: 30
[0054]
Next, reference numeral 204 denotes a priority order determining unit, which is a functional unit that determines the priority order of each SVM in the multi-value classifying unit 202, that is, which SVM is used preferentially over other SVMs. Specifically, the rankings when the SVMs are sorted in ascending order of feature values are used so that SVMs with small feature values calculated by the feature value calculation unit 203 are used preferentially over SVMs with large feature values. SVM priority order. The sorting method is not particularly limited, and a known algorithm such as a quick sort method or a merge sort method may be used.
[0055]
In the above example, the priority of the SVM B 202b with the smallest feature value (that is, the cost, more specifically the processing time) is first, the priority of the SVM A 202a with the next smallest feature value is second, and the feature value The highest priority of the SVM 丙 202c is 3rd.
[0056]
Instead of using the processing time (absolute processing time) calculated by the feature value calculation unit 203 as it is, the relative processing time may be calculated by the following formula and sorted in that order.
[Expression 2]

However, Tr (a, b): Relative processing time of the binary classifier for classification a and classification b
Ta (a, b): Absolute processing time of the binary classifier for classification a and classification b
G: the set of all classifications that can result in a multi-value classifier
n: Number of elements of G (number of classifications of multi-value classification)
[0057]
Even in the binary classifier predicted to have the same absolute processing time according to the above equation (2), the longer the average processing time of the more related classification (in the case of the above equation, classification a and classification b), the relative processing time Becomes shorter. Thus, instead of a binary classifier having a long processing time (in the case of the above formula, a binary classifier for discriminating between classification a / b and other classifications), a binary classifier having a short processing time (of the above formula) In this case, the use of a binary classifier for discriminating between classification a and classification b is promoted.
[0058]
Next, FIG. 3 is a flowchart showing a procedure of multi-value classification processing by a combination of binary classifications in the data classification apparatus according to the embodiment of the present invention. Before starting the processing shown in the figure, the following items are prepared in advance.
a: SVM sorted in order of priority (in the above example, SVM B 202b, SVM A 202a, SVM 丙 202c)
b: A mechanism capable of holding only one position in a (initial SVM in the initial state, SVM B 202b in the above example)
c: Mechanism that can hold multiple classifications rejected in binary classification (empty in the initial state)
[0059]
The SVM selection unit 202d of the multi-level classification unit 202 instructs the SVM indicated by b to execute the binary classification, and obtains the determined classification d and the rejected classification e (step S301). In the above example, the SVM B 202b is first called to determine “clear” or “rain”. Here, for example, it is assumed that the determined classification d is “rain” and the rejected classification e is “sunny”.
[0060]
Next, the SVM selection unit 202d adds the category e rejected in step S301 to the above-described c (step S302). At this point, c is in a state where only “sunny” rejected by the SVM B 202b is included.
[0061]
Then, the SVM selection unit 202d determines whether or not the number of elements of c has reached the number of classifications −1 of the multilevel classification (Step S303). Here, since the total number of classifications is “sunny”, “cloudy”, and “rainy”, it is determined whether or not the number of elements of c has reached two. At this time, the number of elements of c is only “sunny” and is less than two (step S303: No), so the process branches to step S305.
[0062]
When the number of elements of c is less than the total number of classifications−1, the SVM selection unit 202d advances the position indicated by b by one in a (step S305). Here, the position indicated by b is switched from the first SVM B 202b to the second SVM A 202a.
[0063]
Then, the SVM selection unit 202d obtains two classifications (f · g) determined by the SVM indicated by b (step S306). Here, the SVM A 202a discriminates “sunny” or “cloudy”, so that “sunny” and “g” are “cloudy”. Note that f and g may be reversed.
[0064]
Next, the SVM selection unit 202d determines whether either f or g is in c, that is, whether f or g is a classification that has already been rejected (step S307). Here, since f is “sunny” and matches “sunny” stored in c (step S307: Yes), the process returns to step S305 and further advances b by one (step S305).
[0065]
Then, in the next SVM 丙 202c, f becomes “cloudy” and g becomes “rain” (step S306), and none of them is still in c (step S307: No). Is discriminated as “cloudy” or “rainy” (step S301).
[0066]
If the determined category d is “cloudy” and the rejected category e is “rain”, the SVM selection unit 202d adds the rejected category e to c (step S302), and an element of c It is determined whether or not the number has reached the total number of classifications -1, that is, 2 (step S303).
[0067]
At this time, the number of elements of c has reached two, “sunny” and “rain” (step S303: Yes), so the SVM selection unit 202d notifies the classification result output unit 202e of the end of the multi-value classification. In response to this, the classification result output unit 202e outputs the current d, that is, “cloudiness” as the result of the multi-value classification (step S304).
[0068]
In short, the above procedure is to sequentially search SVMs of combinations of classifications that have not been rejected in the past binary classification from among the SVMs arranged in descending order of priority, perform binary classification with the first SVM found, This repetition is continued until one classification has not yet been rejected.
[0069]
Since the priority is determined according to the processing time of the SVM as described above, the SVM with a short processing time is preferentially selected and used by the above procedure. In other words, it is possible to reduce the probability that an SVM with a long processing time will be used. The result of multi-value classification can be obtained without going through.
[0070]
FIG. 4 shows six cases (== _Four C ₂ FIG. 5 is a graph showing the use probability of SVM of FIG. _Ten C ₂ It is a graph which shows the use probability of SVM. As shown in the figure, “fast”, that is, SVM with a short processing time has a higher use probability, and “slow”, that is, an SVM with a long processing time, has a lower use probability. Can do.
[0071]
In the above-described embodiment, SVM is exclusively considered as a binary classifier. However, the binary classifier is not limited to this, and any classifier that can discriminate between two classes, such as a perceptron in a neuron network, for example. Good.
[0072]
In the above-described embodiment, the use cost of the binary classifier is grasped exclusively from the viewpoint of time. However, other than this, for example, an error caused by classification may be considered.
[0073]
As an example, it is known that the upper limit value of the error rate of SVM is proportional to the ratio of SV in teacher data. Therefore, even if it takes some time, if you want accurate classification results as much as possible, SVM with low error rate and reliability is preferentially used. A feature value (a feature value taken from the viewpoint of reliability) may be calculated.
[0074]
Moreover, you may consider the usage fee of a binary classifier, etc. as cost. For example, if the binary classification costs are different, such as a discrimination service with one binary classifier is 100,000 yen once and a discrimination service with another binary classifier is 50,000 yen once, it is cheaper. The characteristic value is calculated according to the cost so that the binary classification is preferentially performed.
[0075]
In the above-described embodiment, the binary classification is continued until the number of rejected classifications reaches n−1. However, the classification is stopped at some binary classifier in the middle, and the determination by the binary classifier is performed. The result may be output as a result of multi-level classification.
[0076]
In general, it is known that the smaller the number of SVs relative to the number of data, the higher the generalization ability of the SVM. That is, as the number of SVs increases and the time required for discrimination increases, the reliability tends to decrease. Therefore, as long as the SVM with a small number of SVs (high reliability) can be used, the classification candidates are narrowed down by the above method,
(1) When the number of SVMs indicated by b above reaches a certain number
(2) When the number of elements c above reaches a certain number (specifically n-1)
The multi-value classification may be terminated when any one of the above conditions is satisfied.
[0077]
Note that the data input unit 200, vector conversion unit 201, multi-value classification unit 202, feature value calculation unit 203, and priority order determination unit 204 described above are specifically executed by the CPU 101 by the program read from the HD 105 to the RAM 103. It is realized by doing. This program can be stored and distributed in various recording media such as the FD 107, the CD-RW 109, and the MO in addition to the HD 105, and can also be distributed via a network.
[0078]
【The invention's effect】
As explained above This invention Is a data classification apparatus that performs multi-level classification of the input data using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification. Feature value calculating means for calculating a feature value of the value classifier, priority order determining means for determining a priority order of each binary classifier based on the feature value calculated by the feature value calculating means, and the priority order Multi-level classifying means for performing multi-level classification of the input data using the binary classifier in descending order of priority determined by the determining means, so that a plurality of 2 constituting the multi-level classifier The value classifiers are used in an order according to the magnitude of the feature value indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Use value classifiers in an efficient order There is an effect that the data classification apparatus capable of performing high-speed multi-level classification can be obtained Te.
[0079]
Also, This invention Is the above The binary classifier is an SVM, and the feature value calculation means calculates the feature value of each binary classifier as the number of SVs in each SVM or a non-zero element of all SVs in each SVM. The number of binary classifiers constituting the multi-level classifier is calculated based on the cost of using each binary classifier (specifically, the number calculated from the number of SVs, etc.). This is used in the order according to the size of the feature value indicating the processing time, error rate, etc.), so that multi-level classification can be performed at high speed using a plurality of binary classifiers in an efficient order. There is an effect that a data classification device can be obtained.
[0080]
Also, This invention Is the above In the invention described in the above, since the priority order determining means determines the order of each binary classifier when the feature values calculated by the feature value calculating means are sorted in ascending order, the multi-value classification A plurality of binary classifiers constituting a classifier are used in order from the smallest feature value indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Thus, there is an effect that a data classification device capable of performing multi-level classification at high speed using a plurality of binary classifiers in an efficient order can be obtained.
[0081]
Also, This invention Is the above In the invention according to claim 2, the priority determined by the priority determining means is a binary classifier in which neither the first classification nor the second classification is rejected. The binary classification of the input data is performed using the highest binary classifier, and the first classification or the second classification in which the input data is not classified in the binary classification Since the rejection is repeated until a predetermined condition is satisfied, the plurality of binary classifiers constituting the multi-level classifier are required to use the cost of using each binary classifier (specifically, the processing thereof) Data that can be used for multiple-value classification at high speed using multiple binary classifiers in an efficient order. Once a classification device is obtained Achieve the cormorant effect.
[0082]
Also, This invention Is the above In the invention described in (2), the condition is that the number of rejected classifications reaches a predetermined number or the characteristic value calculated by the characteristic value calculating means for a binary classifier to be used next is a predetermined threshold value. Therefore, the plurality of binary classifiers constituting the multi-level classifier indicate the cost (specifically, processing time, error rate, etc.) of using each binary classifier. A binary classifier that is used in the order according to the magnitude of the feature value and that is more expensive than a certain level is not used, thereby using multiple binary classifiers in an efficient order to achieve multiple values. There is an effect that a data classification device capable of performing classification at high speed can be obtained.
[0083]
Also, This invention In the data classification method for performing multi-value classification of the input data using a plurality of binary classifiers for determining whether the input data is classified into the first classification or the second classification, each of the 2 A feature value calculating step for calculating a feature value of a value classifier, a priority determining step for determining a priority of each binary classifier based on the feature value calculated in the feature value calculating step, and the priority A multi-level classification step of performing multi-level classification of the input data using the binary classifier in descending order of priority determined in the determination step, so that a plurality of 2 constituting the multi-level classifier The value classifiers are used in an order according to the magnitude of the feature value indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Multivalue using value classifier in efficient order Data classification method capable of performing class at high speed an effect that can be obtained.
[0084]
Also, This invention Is the above In the invention described in the above, the binary classifier is an SVM, and in the feature value calculation step, the feature value of each binary classifier is set to the number of SVs in each SVM or a non-zero element of all SVs in each SVM. The number of binary classifiers constituting the multi-level classifier is calculated based on the cost of using each binary classifier (specifically, the number calculated from the number of SVs, etc.). This is used in the order according to the size of the feature value indicating the processing time, error rate, etc.), so that multi-level classification can be performed at high speed using a plurality of binary classifiers in an efficient order. The data classification method can be obtained.
[0085]
Also, This invention Is the above In the invention according to claim 2, in the priority order determination step, the order of each binary classifier when sorted in ascending order of the feature values calculated in the feature value calculation step is determined as the priority order. A plurality of binary classifiers constituting a classifier are used in order from the smallest feature value indicating the cost (specifically, processing time, error rate, etc.) of using each binary classifier. Thus, there is an effect that a data classification method capable of performing multi-level classification at high speed using a plurality of binary classifiers in an efficient order can be obtained.
[0086]
Also, This invention Is the above In the invention according to claim 1, in the multi-level classification step, among the binary classifiers in which neither the first classification nor the second classification is rejected, the priority determined in the priority determination step is The binary classification of the input data is performed using the highest binary classifier, and the first classification or the second classification in which the input data is not classified in the binary classification Since the rejection is repeated until a predetermined condition is satisfied, the plurality of binary classifiers constituting the multi-level classifier are required to use the cost of using each binary classifier (specifically, the processing thereof) Data that can be used for multiple-value classification at high speed using multiple binary classifiers in an efficient order. When a classification method is obtained An effect.
[0087]
Also, This invention Is the above In the invention described in (2), the condition is that the number of rejected classifications reaches a predetermined number, or the characteristic value calculated in the characteristic value calculation step for a binary classifier to be used next is a predetermined threshold value. Therefore, the plurality of binary classifiers constituting the multi-level classifier indicate the cost (specifically, processing time, error rate, etc.) of using each binary classifier. A binary classifier that is used in the order according to the magnitude of the feature value and that is more expensive than a certain level is not used, thereby using multiple binary classifiers in an efficient order to achieve multiple values. There is an effect that a data classification method capable of performing classification at high speed can be obtained.
[0088]
Also, This invention According to the above It is possible to obtain a program capable of causing a computer to execute the method described in 1).
[Brief description of the drawings]
FIG. 1 is an explanatory diagram showing an example of a hardware configuration of a data classification device according to an embodiment of the present invention.
FIG. 2 is an explanatory diagram functionally showing the configuration of the data classification device according to the embodiment of the present invention.
FIG. 3 is a flowchart showing a procedure of multi-value classification processing by a combination of binary classifications in the data classification device according to the embodiment of the present invention.
FIG. 4 is a graph showing the use probability of SVM when there are four classifications in the data classification apparatus according to the embodiment of the present invention;
FIG. 5 is a graph showing the use probability of SVM when the classification is 10 in the data classification device according to the embodiment of the present invention;
FIG. 6 is an explanatory diagram schematically showing a procedure of multi-value classification by the DDAG method.
[Explanation of symbols]
100 buses
101 CPU
102 ROM
103 RAM
104 HDD
105 HD
106 FDD
107 FD
108 CD-RW drive
109 CD-RW
110 display
111 keyboard
112 mouse
113 Network I / F
114 Communication cable
200 Data input part
201 Vector converter
202 Multi-value classification part
202a SVM A
202b SVM B
202c SVM 丙
202d SVM selector
203 feature value calculator
204 Priority determining unit

Claims

In a data classification device that performs multi-level classification of the input data using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification,
Feature value calculating means for calculating the feature value of each binary classifier;
Priority order determining means for determining the priority order of each of the binary classifiers based on the feature value calculated by the feature value calculating means;
Multi-value classification means for performing multi-value classification of the input data using the binary classifier in descending order of priority determined by the priority order determination means;
With
The binary classifier is an SVM, and the feature value calculation means calculates the feature value of each binary classifier based on the number of SVs in each SVM or the total number of non-zero elements of all SVs in each SVM. features and to Lud over data classification device to.

The priority determining means, according to claim 1, characterized in that to determine the binary classifier ranking when sorted in ascending order of the feature value calculated by the feature value calculating means as the priority Data classification device.

In a data classification device that performs multi-level classification of the input data using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification,
Feature value calculating means for calculating the feature value of each binary classifier;
Priority order determining means for determining the priority order of each of the binary classifiers based on the feature value calculated by the feature value calculating means;
Multi-value classification means for performing multi-value classification of the input data using the binary classifier in descending order of priority determined by the priority order determination means;
With
The multi-level classifying means is a binary classifier having the highest priority determined by the priority determining means among binary classifiers in which neither the first classification nor the second classification is rejected. And performing the binary classification of the input data using, and rejecting the first classification or the second classification, in which the input data is not classified in the binary classification, features and to Lud over data classifier repeating until the condition is satisfied.

The condition is that the number of rejected classifications has reached a predetermined number, or that the characteristic value calculated by the characteristic value calculation means for a binary classifier to be used next has reached a predetermined threshold. The data classification apparatus according to claim 3 , wherein

The said priority order determination means determines the order of each binary classifier when sorting in ascending order of the feature values calculated by the feature value calculation means as the priority order. Item 5. The data classification device according to Item 4.

In a data classification method for performing multi-level classification of the input data using a computer using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification,
The computer is
A feature value calculating step for calculating a feature value of each of the binary classifiers;
A priority determining step for determining the priority of each binary classifier based on the feature value calculated in the feature value calculating step;
A multilevel classification step of performing multilevel classification of the input data using the binary classifier in descending order of priority determined in the priority determination step;
Run
The binary classifier is an SVM, and in the feature value calculation step, the computer calculates the feature value of each binary classifier as the number of SVs in each SVM or non-zero elements of all SVs in each SVM. features and to Lud over data classification method to be calculated based on the total number.

In the priority order determining step, the computer determines the order of each binary classifier when sorting in ascending order of the feature values calculated in the feature value calculating step as the priority order. Item 7. The data classification method according to Item 6 .

In a data classification method for performing multi-level classification of the input data using a computer using a plurality of binary classifiers that determine whether the input data is classified into the first classification or the second classification,
The computer is
A feature value calculating step for calculating a feature value of each of the binary classifiers;
A priority determining step for determining the priority of each binary classifier based on the feature value calculated in the feature value calculating step;
A multilevel classification step of performing multilevel classification of the input data using the binary classifier in descending order of priority determined in the priority determination step;
Run
In the multilevel classification step, the computer has the highest priority determined in the priority determination step among binary classifiers in which neither the first classification nor the second classification is rejected. The binary classification of the input data is performed using a binary classifier, and the first classification or the second classification in which the input data is not classified in the binary classification is rejected things, features and to Lud over data classification method to be repeated until a predetermined condition is satisfied.

The condition is that the number of rejected classifications has reached a predetermined number, or that the feature value calculated in the feature value calculation step for a binary classifier to be used next has reached a predetermined threshold. The data classification method according to claim 8 , wherein:

In the priority order determining step, the computer determines the order of each binary classifier when sorting in ascending order of the feature values calculated in the feature value calculating step as the priority order. The data classification method according to claim 8 or 9.

A data classification program that causes a computer to execute all the steps of the method according to any one of claims 6 to 10.