トップ :: G 物理学 :: G06 計算;計数

【発明の名称】 判別方法
【発明者】 【氏名】鷲澤 輝芳
【課題】判別分析を行うとき、判別効率を低下させずに変数の数を減少させる方法を提供する。

【解決手段】Ｎ個のインデクス集合に対してＮ−１個の要素を持つ部分集合族を生成する工程と、それぞれの部分集合に対して判別効率を計算する工程と、判別効率が最大の部分集合をＮ−１個のインデクス集合として採用し、Ｎ個のインデクス集合と置き換える工程と、要求仕様が満足されたかどうかを判定する工程とで構成される判別分析法であり、判別効率をＫＬＤで計算することを特徴とする。
【特許請求の範囲】
【請求項１】
d個の変数により表現されるサンプルx=(x(1),x(2),...,x(d))Tと、それが属するクラス番号yのＮ個の組{(xj,yj)|j=1,...,N}に対して、Ｎ個の変数からＮ-1個の変数の全ての組み合わせを生成する工程１と、該全てのＮ-1個の変数で表現される該クラスのパラメタを推定する工程２と、該工程２で推定されたパラメタを用いて任意の２つのクラス間の相違度を算出する工程３と、該任意の２つのクラス間の相違度より全てのクラスの分布に対する相違度を算出する工程４とより構成され、該工程１から該工程４は、Ｎがｄから1個ずつ減少させ予め設定された値になるまで繰り返す事を特徴とするデータ判別方法であり、該工程３は、任意の２個のクラス間の相違度をKullback-Leiblerダイバージェンスを用いて算出し、該工程４は，クラスmとクラスnの間の相違度を(m,n)成分とする行列の行列式として算出することを特徴とするデータ判別方法。
【請求項２】
上記工程２は、最尤推定法を用いてパラメタを推定する事を特徴とする、請求項１に記載のデータ判別方法。
【発明の詳細な説明】【技術分野】
【０００１】
複数の異なる対象を観測した結果として得られたデータから各対象を特徴付けるパラメタを推定し、今後該複数の対象が混在した現象を観測して得られるデータがどの現象から得られたものかを判別する技術であり、パターン分類・認識全般に関する。
【背景技術】
【０００２】
判別分析は測定等によって得られたサンプルベクトルを分類するために必須の技術である。２値変数に対する判別分析は非特許文献１で紹介されている以下の１３個の従来技術が存在する。
１ 線形判別方法
1.1 独立２値モデル（independent binary model （IBM） ）
独立な２値変数に対する方法であり，独立性の仮定は現実的でない。
【０００３】
1.2 線形判別関数 （ linear discriminant function （LDF） ）
同じ分散共分散行列を持つ多次元正規分布に対して有効な方法。
【０００４】
1.3 ロジスティック判別（ logistic discrimination ）
セミパラメトリック法．条件付き確率にロジスティック関数を仮定することによって，密度推定の手間を省いた。
【０００５】
1.4 混合整数プログラミング （ Mixed integer programming （MIP） ）
２ 次判別方法
2.1 ２次判別関数（ quadratic discriminant function （QDF） ）
異なる分散共分散行列を持つ多次元正規分布に対して最適な分類方法はSmithのQDFである。
【０００６】
2.2 ２次の対数線形モデル（ 2nd order log-linear model （LLM） ）
contingency tableの分析としてよく知られている対数線形モデル
2.3 ２次のBahadurモデル（ 2nd order Bahadur model （Bahadur ） ）
３ 最近接判別方法
3.1 Hillの近接予測方法（ Hill's kNN-Hills ）
適応的重み付け近接予測方法
４ 他のノンパラメトリック判別方法
4.1 カーネル予測方法
4.2 Fourier方法
4.3 多重パーセプトロンニューラルネット
4.4 学習ベクトル量子化ニューラルネット
ただし、上記全ての方法は判別効率を向上させるために変数選択を行うためのものではない。
【０００７】
特許文献１では判別効率を向上させるために、逐次的に判別部分空間を選択する技術が開示されている。これによって、N回目までに選択された判別部分空間で判別できなかった部分集合の一部がN+1回目に選択された判別部分空間で判別可能となる。
【０００８】
非特許文献２及び非特許文献３では、平均が異なり（μi， μj） 、分散共分散行列Vが同じ確率密度分布間の相違度を表わす量として（式01）で与えられる判別効率Dij（Mahalanobis Distance）を用いて変数選択する技術を開示している。
【０００９】
（式01） Dij = （μi-μj）TV-1（μi-μj）
一方、二つの異なる確率密度関数間の相違度を計る量として、Kullback-Leiblerダイバージェンス（KLD）が知られている（非特許文献４等を参照）。
【特許文献１】特開平５−１４３６３６号公報
【非特許文献２】OK. Asparouknov， WJ. Krzanowski， “A comparison of discriminant procedures for binary variables，” Computational Statistics & Data Analysis， 38， pp.139-160 （2001）.
【非特許文献３】永田，棟近：“多変量解析法入門，”サイエンス社（2001）.
【非特許文献４】柳井，高根：“新版 多変量解析法，”朝倉書店（1987）.
【非特許文献５】坂井 利之：“パターン認識の理論，”情報科学講座E.19.1，共立出版（1967）.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら従来技術には以下に述べるような課題があった。
【００１１】
特許文献１に開示の技術は判別部分空間として全ての説明変数が張る空間の超平面として与えられるので、この判別部分空間から判別に寄与しない説明変数を特定することは困難であった。
【００１２】
また非特許文献２及び非特許文献３に記載の変数選択技術は比較する分布の分散共分散行列が同じであると仮定しており、分散共分散行列が異なる場合には適用できなかった。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明では、d個の変数により表現されるサンプルx=（x（1），x（2），…，x（d））Tと、それが属するクラス番号yのＮ個の組{（xj，yj）|j=1，…，N}に対して、Ｎ個の変数からＮ-1個の変数の全ての組み合わせを生成する工程１と、該全てのＮ-1個の変数で表現される該クラスのパラメタを推定する工程２と、該工程２で推定されたパラメタを用いて任意の２つのクラス間の相違度を算出する工程３と、該任意の２つのクラス間の相違度より全てのクラスの分布に対する相違度を算出する工程４とより構成され、該工程１から該工程４は、Ｎがｄから1個ずつ減少させ予め設定された値になるまで繰り返す事を特徴とするデータ判別方法であり、該工程３は、任意の２個のクラス間の相違度をKullback-Leiblerダイバージェンスを用いて算出し、該工程４は、クラスmとクラスnの間の相違度を（m，n）成分とする行列の行列式として算出することを特徴とするデータ判別方法を提供し、特に、該工程3において、分散共分散行列が異なる２つの確率密度分布間の相違度を、非特許文献４で開示されている（式02）のKLDで算出する。
【００１４】
（式02）KLDij = （1/2）tr{（Vi-Vj）（Vj-1-Vi-1）}+（1/2）tr{（Vi-1-Vj-1）（μi-μj）（μi-μj）T}
上式中、tr{}は行列のトレースを表わす。KLDを用いることによって、平均ベクトル、分散共分散行列のどちらも異なる確率密度関数の相違度が比較できるようになった。
【００１５】
ちなみに（式01）で与えられるMahalanobis Distanceは、分散共分散行列が
等しい２つの分布間のKLDであることが非特許文献４に示されている。
【００１６】
また、クラス数が２を超える場合の相違度を算出するために工程４において、上記工程３で計算されたKLDを（i，j）成分とする行列を形成する。
【００１７】
【数１】


【００１８】
（式03）で与えられる行列の行列式、或いはトレースを相違度として算出する。
【発明の効果】
【００１９】
以上説明したように、本発明によれば、簡単な方法で、所望の要求仕様満たす判別部分空間を得る事が出来た。
【発明を実施するための最良の形態】
【００２０】
実施例1の処理の流れ図を図１に、構成図を図２に示す。図中、２０１はＣＰＵ、２０２は表示装置、２０３は入力装置、２０４は1次記憶装置、２０５は２次記憶装置、２０６は通信装置、２０７はバスラインである。
【００２１】
本発明における工程は，プログラムとして予め２次記憶装置２０５に格納されており、入力装置２０３、或いは通信装置２０６等からのコマンド入力によって、１次記憶装置にロードされ、実行されるものである。
【００２２】
図中、１０１ではＮ個のインデクスからＮ-1個のインデクスの全ての組み合せを生成する。例えばＮ=3のときは以下の3通りである。
【００２３】
（式04） {（1，2）， （1，3）， （2，3）}
組み合せの数は一般にNCN-1=Nである。
【００２４】
Ｎは初期値として与えられた変数の数ｄが設定される。
【００２５】
１０２では（式04）のように与えられたインデクスの組み合せに対応した変数が張る部分空間での各クラスのパラメタ（平均ベクトルμi及び分散共分散行列Vi）を推定する．推定方法として、「柴田：“確率・統計，”理工系の基礎数学」等に最尤推定法が開示されている。
【００２６】
１０３では上記パラメタを用いて（式02）でKLDを算出する。
【００２７】
１０４では上記KLDを用いて（式03）でKLD行列を構成し、KLD行列式或いはトレースを算出する。
【００２８】
１０５では最大のKLDを持つインデクスの組を部分空間の基底として採用する。例えば（式04）のうち、（1，3）が最大のKLDを持つなら、変数２を棄却し、変数１と３が張る部分空間を判別に供する空間とする。
【００２９】
以下、予め定められた要求条件を満たすまで、１０１から１０５を繰り返す。ここで要求条件とは、例えば以下のものが考えられる。
【００３０】
１．部分空間の次元を指定する。
【００３１】
２．KLDの値を指定する。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施例１の流れ図である。
【図２】本発明の構成図である。
【出願人】 【識別番号】０００００１００７
【氏名又は名称】キヤノン株式会社
【出願日】 平成１７年１０月１１日（２００５．１０．１１）
【代理人】 【識別番号】１０００９０５３８
【弁理士】
【氏名又は名称】西山 恵三

【識別番号】１０００９６９６５
【弁理士】
【氏名又は名称】内尾 裕一
【公開番号】 特開２００７−１０８８５４（Ｐ２００７−１０８８５４Ａ）
【公開日】 平成１９年４月２６日（２００７．４．２６）
【出願番号】 特願２００５−２９６４８６（Ｐ２００５−２９６４８６）