説明

サポート・ベクタ・マシンおよび変数選択を使用する分類

アイテムの特徴についての複数の変数を使用して、アイテムを分類するための分類機を得る方法であって、前記分類機における使用のために変数の代表的なサブセットを決定することを含む方法。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、分類における改善に関する。本発明は、銀行券またはコインなどの通貨または価値のアイテムの分類に特に適用可能である。
【背景技術】
【0002】
本発明は、その内容が参照によって本明細書に組み込まれる同時係属出願EP1217589AおよびEP1516293Aに関する。
【0003】
以下において、SVMは、サポート・ベクタ・マシン(Support vector machine)を表し、FVSは、特徴ベクタ選択(Feature Vector Selection)(上述されたEP1516293Aを参照)を表し、かつ用語ビルウエイ(billway)は、一方向の鑑別機における紙幣の供給を表す。したがって、命名毎に4つのビルウエイが存在する。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】同時係属出願EP1217589A
【特許文献2】同時係属出願EP1516293A
【非特許文献】
【0005】
【非特許文献1】Vapnik V.、「The Nature of Statistical Learning Theory」、Springer Verlag、1995年
【非特許文献2】Fukunaga K.、「Introduction to Statistical Pattern Recognition」、Academic Press,INC、2nded.1990年
【発明の概要】
【発明が解決しようとする課題】
【0006】
輸送手段、センサ手段、メモリ、および処理手段を備える紙幣受容機において、多くのセンサおよび多くの波長を用いる文書の走査は、文書を識別しかつ認証するため、かつ銀行券受容機の場合に紙幣を命名するために使用されることができるメモリ内に格納された大量の多変数データを結果として生じる。このプロセスが高速であることが望ましく、データのサブセットが、より良好な結果を達成するために十分であり得ることが知られている。この応用は、データを表す変数の最適なサブセットを見出すことに関連する。
【課題を解決するための手段】
【0007】
本発明の態様は、添付の請求項に示される。
【0008】
この新規な命名アルゴリズムは、SVM(サポート・ベクタ・マシン)アルゴリズムに与えられた入力データの選択を扱う。
【0009】
変数選択の目的は、分類目的のために無関係またはほぼ関係の無い変数を除去し、かつ同時に高い分離性能を維持することである。着想は、全ての変数でトレーニングされたとき、SVMで得られた分離ベクタ上に投影されたデータと高い相関性を有する一組の変数を見出すことである。
【0010】
プロセスは、クラスを含む事前に規定された紙幣のセットから紙幣を命名するのために使用する紙幣鑑別機のためのデータ入力を生成するために使用されることができる。クラスは、単一の命名および/または他の命名の4つのビルウエイであり得る。選択された変数およびプロセスによって生成された識別軸が、鑑別機のメモリ内にロードされることができる。それらは、クラスの1つのメンバであるとして、ユニットに提示される新たなサンプルを後で鑑別するために鑑別機によって使用される。
【0011】
本発明の実施形態は、紙幣の命名に関連して記載されるが、プロセスは、例えば紙幣鑑別に関連する認証問題を含む、変数選択の任意の問題に広範に適用されることができる。
【0012】
本発明の実施形態が、添付の図面を参照して記載される。
【図面の簡単な説明】
【0013】
【図1】銀行券検知システムの概略図である。
【図2】図1の検知システムのセンサ・アレイの上部から見た平面図である。
【図3】図1の検知システムの光源アレイの下部から見た平面図である。
【図4】分類を示すグラフである。
【発明を実施するための形態】
【0014】
本発明の実施形態による銀行券検知システムは、図1に概略的に示される。システムは、銀行券輸送経路の一方側に配置された光源アレイ2と、光源アレイ2とは反対側の銀行券輸送経路の他方側に配置された光センサ・アレイ4とを含む。システムは、光源アレイ2と光センサ・アレイ4との間の輸送経路に沿って銀行券8を輸送するために、4つの組のローラ6の形態の銀行券輸送手段を含む。光源アレイ4は、プロセッサ10に接続され、システムは、コントローラ12によって制御される。光源アレイ2から放出される光を拡散しかつ混合する拡散器14が、光源アレイ2と銀行券輸送経路との間に配置される。
【0015】
図2は、光源アレイ2の下部から見た平面図である。示されるように、光源アレイは、複数の光源9の線形アレイである。アレイは、6個の光源のグループ11に配置され、グループの各光源は、通常は青および赤の種類である、適用に適切なように選択された異なる波長の光を放出する。各波長の光源が、輸送経路を横切って配置されるように、複数のそのようなグループ11は、輸送経路を横切って線形に配置される。
【0016】
図3は、光センサ・アレイ4の上部から見た平面図である。示されるように、光センサ・アレイは、輸送経路を横切るラインに配置された8個の円形光センサを含む。センサは、7mmの直径であり、センサが並ぶように、中心は、ラインにおいて7mm離間される。
【0017】
図2および図3は、同一縮尺ではなく、光源および光センサ・アレイは、ほぼ同じサイズである。
【0018】
動作において、銀行券は、光源アレイ2とセンサ・アレイ4との間の輸送経路に沿って、コントローラ12の制御下でローラ6によって輸送される。銀行券は、所定の距離だけ輸送され、次いで停止される。1つの波長の全て光源が動作され、銀行券の幅にわたって均一に光を広げるために拡散器14内の光を混合した後、光は、銀行券に当たる。銀行券を透過する光は、センサ・アレイ4によって検知され、信号が、各センサに対応する銀行券上の各測定スポットについてセンサから得られる。同様に全ての他の波長の光源は、連続して同様に動作され、測定値が、対応するラインについて各波長についてセンサから得られる。
【0019】
次に、ローラ6は、事前決定された距離だけ再び銀行券を移動するために作動され、銀行券を照明しかつ各センサについて各波長で測定値を取るシーケンスが繰り返される。
【0020】
ラインずつ銀行券の長さにわたって上記ステップを繰り返すことによって、測定値が、銀行券が移動される事前決定された距離によって決定される、銀行券の各ラインに対して各センサについて6個の各波長で得られる。
【0021】
上述のように、文書は、幅および長さにおける事前規定された走査解像度で複数の波長について文書上の複数のスポットを測定する、線形センサ・アレイによって走査される。文書は、異なる寸法を有することがあるので、完全な走査は、異なるサイズのデータ・セットを技術的に生じる。識別アルゴリズムは、共通サイズであるべき測定値ベクタを使用して対象物を比較することによって作用する。原理的に、文書は異なるサイズを有することができるので、たとえ公差の理由だけがあるとしても、命名のために全てのサイズに共通である走査最大領域が画定される。この共通サイズは、目標の紙幣セットとともに変化する。
【0022】
SVM分類機は、設計によって2つのクラスで動作する。識別および変数選択は、2つのクラスを使用して実行され、第1のクラスは、参照クラスであり、第2のクラスは、クラス1以外の全ての紙幣を含む。命名の場合および実際の目的のために、クラス2で使用される文書は、それらの寸法にしたがってクラス1の文書に近い。これは、それらが、クラス1の長さおよび幅試験を通過することを意味する(それは、そうでなければ、異なる寸法の文書を分離するために些細なことである)。SVM分類機のさらなる詳細は、従来技術の文献に見出されることができる。
【0023】
基準クラスおよび第2のクラスのための試験サンプルは、上述のセンサ・アレイを使用して測定され、測定された値は、低減された変数のセットを用いてSVMを生成するために、以下に記載されるように処理される。
【0024】
Xが、データのセットX=xij、i=1・・・M、j=1・・・Nであるとする。ここで、Mは、紙幣の数であり、Nは、変数の数である。変数は、所定のスポット位置および所定の波長である。換言すれば、各紙幣iについて、1つのベクタxij、j=1・・・Nにおける全ての変数(長さ×幅×波長)。所定の紙幣iについて、変数jは、関連する波長において4つのトラックの平均を減算することによって、正規化を受ける。
【0025】
より詳細には、正規化のために使用されるスポットは、4つのトラックによって画定される。4つのトラックの平均は、各波長について計算され、かつ例えば6個の波長についてベクタ{m、m、m、m、m、m}に格納される。次に、関連する波長kの各測定値xijは、mを減算することによって正規化される。
【0026】
便宜のために、データの全体セットは、変数選択アルゴリズムを適用する前に正規化される。
【0027】
上記正規化は、各変数から、紙または埃または経時変化などの紙幣の全体的効果を取り除く。他方、スケーリング・プロセスは、紙幣の全体セットの分散を扱う。データのセットXは、2つのセットからなり、基準クラス1に関連するデータと、クラス2の関連するデータであり、X=(X、X)である。データの2つのセットは、平均およびクラス1の標準分散を使用してスケーリングされる。スケーリングは、
【0028】
【数1】

によって与えられ、ここで、
【0029】
【数2】

および
【0030】
【数3】

である。
【0031】
線形SVMは、全ての変数Xを用いてトレーニングされ、結果として生じる識別軸W1は、W1=SVs1*Alpha1によって与えられ、ここで、SVs1は、L個のサポート・ベクタのマトリクス(L、N)であり、Alpha1は、サイズLのラグランジェ乗算器のベクタである。さらなる詳細について、Vapnik V.、「The Nature of Statistical Learning Theory」、Springer Verlag、1995年を参照されたい。データは、W1上に投影される。目標は、識別軸W1上に投影されたデータとともに高く相関する変数を見出すことである。
【0032】
この実施形態において、最良のS変数を見出す問題は、フォワード・シーケンシャル選択によって解決される。アルゴリズムは、変数の空のセットで開始し、S変数が選択されるまで変数を追加する。適合基準は、既に選択された変数と現在の変数を組み合わせる変数のセットについて評価される。最大適合性を与えるものは、選択された変数のセットに追加される。
【0033】
フォワード・シーケンシャル選択は、バックワードまたはステップ状選択などの使用されることができる多くの選択アルゴリズムのまさに1つであることに留意されたい。選択アルゴリズムに関するさらなる詳細は、例えば、Fukunaga K.、「Introduction to Statistical Pattern Recognition」、Academic Press,INC、2nded.1990年を参照されたい。
【0034】
識別軸をW1と命名し、クラス1およびクラス2の投影データ
【0035】
【数4】

、およびS={s、・・・、s}の選択された変数Xを有するデータのセットは、
P=X*W1 (4)
=(xij)i=1・・・M,j=s、・・・、sである。
【0036】
まず第1に、投影PおよびデータのセットXが、それらの平均を減算することによって中心に集められる。
P=P−mean(P) (5)
X=X−mean(X) (6)
次に、ベクタPは、スケーリングされる。
P=P/norm(P) (7)
【0037】
既にS={s、・・・、s}変数が選択され、かつまだ取られていない変数j
【0038】
【数5】

の相関性を評価すると仮定する。適合性は、S=S∪{j}とPとの間の一種の相関性を規定する。
【0039】
【数6】

ここで、
【0040】
【数7】

である。
【0041】
最良の適合性を与える変数が、選択された変数のセットに追加される。適合性が所定の値(0.998)に達するとき、または変数の選択された事前に規定された数を有するなら、変数の選択を停止する。
【0042】
アルゴリズムのステップは、以下に示すように要約されることができる。
1.正規化された変数の全体のセットを構築する。
2.次に、(3)にしたがってデータをスケーリングする。
3.SVMを変数の全体のセットを用いてトレーニングする。SVMは、識別ベクタW1を構築するために使用されるサポート・ベクタを戻す。
4.W1に全てのデータを投影する。P=X*W1
5.(5)にしたがってベクタPを中心に集める。
6.その基準を使用してベクタPをスケーリングする。P=P/norm(P)
7.(6)にしたがってXをスケーリングする。
8.選択を初期化する。R={1・・・N}、S={}
9.選択された変数の数または適合性が、所定値に到達するまで、以下を繰り返す。
a)Rにおける全ての残る変数について、変数jの適合性基準
【0043】
【数8】

を評価する。Fは、全ての適合性のリストである。
【0044】
【数9】

b)適合性を最大化する最良の変数を見出す。best=argmax(F)
c)変数bestを、選択された変数のセットに追加する。S=S∪{best}
d)変数の残るリストから変数bestを除去する。R={1・・・、best−1、best+1、・・・N}
10.選択された変数を有するSVMを維持し、最終識別機としてW2=SVs2*Alpha2によって与えられる識別軸W2を維持する。SVs2およびAlpha2は、サポート・ベクタおよびSVMの第2のランのラグランジェ乗算器である。
【0045】
上述の議論は、銀行券試験機で使用されるべき変数のサブセットを選択することに関する。選択された変数および識別軸を表すパラメータは、銀行券試験機のメモリに格納され、以降の試験(認証、命名など)のために使用される。
【0046】
より詳細には、銀行券を試験するために、銀行券は、センサ・アレイによって検知され、選択された変数について測定値は、SVMによって処理される。測定値は、識別ベクタW2上に投影された試験ベクタを構築するために使用される。これは、1つ以上の閾値と比較されることができるスカラー値を結果として生じる。例えば、スカラー値が、所定の閾値より小さいまたは大きいなら、基準クラスに属するまたはそうでないと処理されることができる。同様に、2つの閾値について。スカラー値が、2つの閾値の間にあるなら、基準クラスに属するまたはそうでないとして処理されることができる。
【0047】
変数のサブセットおよび識別軸を得る処理は、銀行券試験機自体において、または別個のデバイスにおいて実行されることができ、選択された変数および識別軸を表すパラメータは、後の使用のために銀行券試験機のメモリ内にその後に格納される。
【0048】
上述のように、このアプローチは、元の数Nの変数を使用するが、より少ない処理およびしたがってより高速の結果であるように、より少ない変数を実際に使用して、性能に関して同様の結果を与える。
【0049】
Pを基準にせず、適合性基準について他の範囲を使用することも可能である。適合性の値がより高いと、投影されたデータの再構築はより良好である。この値を、数値の問題を避けるために1より小さな所定のレベル、例えば0.998に固定し、この値が到達されるとき選択を停止することが便利である。
【0050】
様々な命名のための紙幣鑑別機における実際の試験は、いくつかの他の変数が、より多い、例えば64個の変数などを必要とするとき、ほぼ20から40の変数が、より高い性能を維持するのに十分であることを示した。
【0051】
図4は、全ての変数、この場合357個の変数(上部)および16個の変数(下部)で2つの特定の命名の命名のためのSVMの結果を示す。
【0052】
この場合に、全ての2番目のクラスの対象物が、基準クラスの一方側にあり、クラスは、単一の閾値によって分離されることができることが理解され得る。代わりに、基準クラスは、外部の対象物が、基準クラスの他方側に分類されることがある可能性を包含するために、許容ウインドウを規定する2つの値間に囲まれることができる。
【0053】
実施形態において、変数のサブセットは、SVM分類機を使用して選択され、次に選択された変数のサブセットは、他のSVM分類機を使用する分類のために使用される。しかしながら、一旦、元の変数を表しかつ入力データに対応する相関変数が選択されると、任意の適切なタイプの分類が、当業者に知られているように、LDA(線形識別解析)またはMahalanobis距離または類似物などの相関変数を使用して実行されることができる。代表的なサブセットは、変数の数を低減するように選択され、一方、選択された変数が元の変数をおよび対応するデータを表すように、分類に関して適切な性能を維持する。これは、上述の適合関数を使用するなどの様々な方法で評価されることができる。
【0054】
銀行券に対する参照は、クーポン、チケットなどの他の類似するタイプの価値のあるシートを含み、かつそのような文書の本物の実施例および偽物の実施例を含む。システムは、例えば、輸送方向および/またはセンサ・アレイまたは固定ポイントに対する銀行券のスキューおよびオフセットなどの方位を検出するための、縁部検出器などの手段の使用を伴うことができる。代わりにシステムは、縁部が、輸送方向に平行、または輸送方向および/またはセンサ・アレイに対して所望の角度の状態で、輸送経路に沿って紙幣の長さなどの所望の方位に銀行券を位置付けるための手段を含むことができる。
【0055】
記載された実施形態は、銀行券試験機である。しかしながら、本発明は、コイン試験機などの他のタイプの通貨試験機に適用されることもできる。例えば、コインを横切る連続するポイントで、材料などのコイン特徴の測定値を取るコイン試験機からの信号は、コインを横切る特徴を表す信号を生成するために挿入されることができる。
【0056】
用語「コイン」が、任意のコイン(有効であるまたは偽物である)、トークン、スラッグ、ワッシャまたは他の金属対象物あるいはアイテム、および特に、コインで動作するデバイスまたはシステムを動作する試みで個々に使用されることができる任意の金属対象物またはアイテムを意味するために用いられる。「有効なコイン」は、認証コイン、トークンなど、または特に、そのシステム内で、コインで動作するデバイスまたはシステムが動作することが意図される貨幣システムの認証コイン、およびそのシステムとともに、そのようなコインで動作するデバイスまたはシステムが、価値のアイテムとして選択的に受容しかつ処理することが意図される命名の認証コインであると考慮される。

【特許請求の範囲】
【請求項1】
アイテムの特徴についての複数の変数を使用して、前記アイテムを分類するための分類機を得る方法であって、前記分類機における使用のために前記変数の代表的なサブセットを決定することを含む方法。
【請求項2】
第1のセットの変数の代表的なサブセットを決定するために、第1の分類機および第1のセットの変数を使用することを含む請求項1に記載の方法。
【請求項3】
前記代表的なサブセットを決定するために、前記第1の分類機としてSVM分類機を使用することを含む請求項2に記載の方法。
【請求項4】
適合性基準を使用して前記変数のサブセットを選択することを含む請求項1乃至3のいずれか1項に記載の方法。
【請求項5】
前記適合性基準が、前記第1のSVM分類機の識別軸上への入力データの投影に基づく請求項3に従属する請求項4に記載の方法。
【請求項6】
前記適合性基準が、変数の相関に基づく請求項4または5に記載の方法。
【請求項7】
前記適合性基準が、本明細書の前文で規定された式(8)に基づく請求項4乃至6のいずれか1項に記載の方法。
【請求項8】
変数のサブセットを選択するステップは、変数の第1のサブセットを選択することと、前記変数のサブセットを増大または低減することとを含む請求項1乃至7のいずれか1項に記載の方法。
【請求項9】
適合性基準を使用して各サブセットを評価することを含む請求項8に記載の方法。
【請求項10】
変数の事前決定された数および/または事前決定された適合性レベルが到達されるまで、前記サブセットを増大または低減することを含む請求項8または9に記載の方法。
【請求項11】
S={s、・・・、s}変数のセットを選択することと、セットS=S∪{j}を作ることによって、まだ取られていない変数j
【数1】

の相関性を評価することと、Sを評価することとを含む請求項8乃至10のいずれか1項に記載の方法。
【請求項12】
入力データをスケーリングすることを含む請求項1乃至11のいずれか1項に記載の方法。
【請求項13】
スケーリングが、入力データのサブセットに基づく請求項12に記載の方法。
【請求項14】
前記スケーリングが、基準クラスに関する入力データに基づく請求項13に記載の方法。
【請求項15】
スケーリングが、平均および標準偏差に基づく請求項14に記載の方法。
【請求項16】
スケーリングが、前記平均を減算することと、前記標準偏差によって除算することとを含む請求項14に記載の方法。
【請求項17】
前記スケーリングされたデータの絶対値をとることを含む請求項12乃至16のいずれか1項に記載の方法。
【請求項18】
正規化された変数の全体のセットを構築するステップと、(3)にしたがって前記データをスケーリングするステップと、SVM分類機を実質的に前記変数の全体のセットを用いてトレーニングするステップと、識別ベクタW1を構築するステップと、P=X*W1であるようにW1に全ての前記データを実質的に投影するステップと、(5)にしたがって前記ベクタPを中心に集めるステップと、P=P/norm(P)であるようにその基準を使用して前記ベクタPをスケーリングするステップと、(6)にしたがってXをスケーリングするステップと、前記変数を初期化するR={1・・・N}、S={}ステップと、シーケンスを、前記選択された変数の数または前記適合性が、所定値に到達するまで、
a)Rにおける全ての残る変数について、変数jの適合性基準
【数2】

を評価し、Fは、全ての適合性のリストであり、
【数3】

b)前記適合性を最大化する最良の変数を見出し、best=argmax(F)、
c)変数bestを、選択された変数の前記セットS=S∪{best}に追加し、
d)変数の残るリストR={1・・・、best−1、best+1、・・・N}から変数bestを除去することを繰り返し、
選択された変数を有する前記SVMを維持し、最終識別機としてW2=SVs2*Alpha2によって与えられる前記識別軸W2を維持するステップとを含み、ここで、SVs2およびAlpha2は、前記サポート・ベクタおよびSVMの第2のランのラグランジェ乗算器である請求項1乃至17のいずれか1項に記載の方法。
【請求項19】
通貨のアイテムを分類するための請求項1乃至18のいずれか1項に記載の方法。
【請求項20】
命名の1つのビルウエイである基準クラスと、同一の命名の少なくとも3つの他のビルウエイを含む第2のクラスとの間で紙幣を分類するための請求項19に記載の方法。
【請求項21】
前記第2のクラスが、複数の他の命名をさらに含む請求項20に記載の方法。
【請求項22】
第1の命名のコインである基準クラスと、他の命名の少なくとも1つのコインである第2のクラスとの間でコインをさらに分類するための請求項19に記載の方法。
【請求項23】
請求項1乃至22のいずれか1項に記載の方法を使用して得られた分類機を使用する通貨のアイテムを試験する方法。
【請求項24】
前記通貨アイテムが、前記分類機を得るために使用される前記データ・セットとは異なる請求項2に記載の方法。
【請求項25】
前記通貨アイテムを測定することと、前記選択された変数についてのデータを抽出することと、スカラー値を得るために前記選択された変数および前記分類機について前記データを使用することとを含む請求項24または25に記載の方法。
【請求項26】
前記スカラー値を得るために、前記選択された変数についてのデータを識別軸上に投影することを含む請求項25に記載の方法。
【請求項27】
前記スカラー値を閾値と比較することを含む請求項25または26に記載の方法。
【請求項28】
前記スカラーが前記閾値より上か下かに応じて、前記通貨アイテムを受け入れまたは除去することを含む請求項27に記載の方法。
【請求項29】
前記スカラー値を2つの閾値と比較することを含む請求項25または26に記載の方法。
【請求項30】
前記スカラーが前記閾値間にあるなら前記通貨アイテムを受け入れることと、そうでなければ前記通貨アイテムを除去することとを含む請求項29に記載の方法。
【請求項31】
鑑別機において、請求項1乃至22のいずれか1項に記載の方法を使用して得られた前記分類機の表示を格納することを含む通貨鑑別機を製造する方法。
【請求項32】
前記分類関数および前記変数のサブセットの表示を格納することを含む請求項31に記載の方法。
【請求項33】
サポート・ベクタおよび識別軸を表す1つ以上のファクタ、および前記変数のサブセットを格納することを含む請求項31に記載の方法。
【請求項34】
請求項1乃至22のいずれか1項に記載の方法を実行するためのコンピュータ・プログラム。
【請求項35】
請求項1乃至22のいずれか1項に記載の方法を使用して得られたSVM分類機の表示を格納する通貨鑑別機。
【請求項36】
請求項1乃至30のいずれか1項に記載の方法を実行する装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate


【公表番号】特表2009−545049(P2009−545049A)
【公表日】平成21年12月17日(2009.12.17)
【国際特許分類】
【出願番号】特願2009−521356(P2009−521356)
【出願日】平成18年7月28日(2006.7.28)
【国際出願番号】PCT/IB2006/002398
【国際公開番号】WO2008/015489
【国際公開日】平成20年2月7日(2008.2.7)
【出願人】(506258187)エムイーアイ インコーポレーテッド (27)
【Fターム(参考)】