JPH0934862A - パターン学習方法および装置 - Google Patents

Abstract

(57)【要約】 【目的】パターン認識の効率を向上する。 【構成】学習パターンを減少させ、学習時には連続的に
同一のクラスタの併合が起きないよう併合処理を分散さ
せ、学習の終了後には認識結果をもとに不必要な辞書を
除去または辞書にペナルティを設定する。 【効果】学習時間を減少させ、かつ鎖効果と呼ばれる悪
影響を排除でき、効率よくパターン認識用辞書を作成で
きる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、パターン認識の分野に
おいて、パターンをクラスタリング（分類）することに
よって学習し、パターン認識のための辞書（学習したク
ラスタ）を作成する方法および装置に係り、特に、大量
パターンの効率的な学習を可能とする学習方法および装
置に関する。

【０００２】

【従来の技術】従来、パターンを学習する方法には、パ
ターン、またはパターン集合を一つのクラスタ（グルー
プ）とみなし、このクラスタ間の類似性をある尺度に基
づいて数値化し、最大の類似性、あるいはより一般的に
類似性がある値以上のクラスタどうしを併合して一つの
クラスタとする操作を繰り返すことによって、パターン
を分類する方法（「認識工学−パターン認識とその応
用」（鳥脇純一郎著，コロナ社，１９９３年）の８５ペ
ージに記載の「階層的クラスタリング」）がある。

【０００３】

【発明が解決しようとする課題】上述した従来の「階層
的クラスタリング」を膨大な量のパターン学習に適用す
る場合、すべてのパターンを一括して学習に用いていた
ので、繰り返しの処理が非常に多くなり、膨大な処理時
間がかかっていた。そのため学習パターンを効率的に減
らすことが課題となっている。

【０００４】類似性の高いクラスタが３個以上存在する
場合、それらのクラスタを併合する順序が具体的に示さ
れていなかった。

【０００５】類似性の高いクラスタの併合を繰り返す場
合、一般に鎖効果と呼ばれる欠点が現れる。学習パター
ンが膨大な場合は、パターンが密集することが多く、こ
の鎖効果が顕著に現れるため問題となる。

【０００６】クラスタリングによって大量のパターンを
学習した場合、少数個のパターンからなるクラスタ（辞
書）が大量に生成されるが、これらの中には認識精度に
関係の無い、言わば不必要な辞書が大量に存在する。こ
れらを除外するなどして効率の高い辞書を作成すること
が課題となる。

【０００７】

【課題を解決するための手段】本発明の方法または装置
は、類似性の極めて高い学習パターンを学習前にまとめ
ておく等して、学習パターン数をあらかじめ削減してお
く処理または手段、クラスタの代表点を中心とした放射
状の領域にパターン空間を分割し、該領域の中でクラス
タの代表点からの距離が最も遠いパターンのみをクラス
タ内のパターンとして記憶する処理または手段、類似性
の高いクラスタの併合を非連続的にするような制限を設
ける処理または手段、認識結果を利用して不必要な辞書
を除いたり、あるいはペナルティを設定する処理または
手段からなる。

【０００８】

【作用】学習パターン数を削減することにより、学習時
間を短縮できる。クラスタの併合に制限を設けることに
より、特に学習初期のクラスタを分散化させることがで
きるので、鎖効果が起こりにくく、膨大なパターンの学
習が可能となる。同時に、具体的な併合の方法も示され
る。また、認識結果を用いることにより、不必要な辞書
の判定が容易になる。

【０００９】

【実施例】クラスタリングについて説明する。パターン
空間に有限個のパターンのサンプルが与えられている場
合、この空間の中で、パターンの分布が密集している箇
所をクラスタ（パターン集合）と呼ぶ（図２参照）。図
２は特徴軸が２種類の場合を示している。このクラスタ
を見つける操作をクラスタリングと呼ぶ。クラスタリン
グの代表的な手法は、類似性のあるパターンどうしの併
合を繰り返す処理である（一般に、最近隣法と呼ばれて
いる）。

【００１０】パターン間の類似性を表す尺度としては距
離や類似度等がある。距離には、いわゆる市街距離，ユ
ークリッド距離，ミンコフスキー距離，マハラノビス距
離などがあり、類似度にはいわゆる単純類似度，方向類
似度，複合類似度，重み付き類似度などがある。類似度
が高い時には類似性が高く、類似度が低い時には類似性
は低い。逆に、距離を用いる場合は、距離が短い時には
類似性が高く、距離が遠いときには類似性は低くなる。

【００１１】パターンあるいはクラスタ併合処理には、
代表的手法として、 （１）併合するパターンのパターン空間上の位置を保存
しない手法 （２）併合するパターンのパターン空間上の位置を保存
する手法 の２種類がある。

【００１２】上記（１）は、パターン空間の特徴軸のそ
れぞれに対して特徴値の累積を取り、平均を取る，重心
を取る、あるいはある閾値で正規化する等して、クラス
タを代表するパターンを作成し、以降の併合処理では、
この代表パターンとの類似性を比較し、併合に用いると
いう手法である。代表パターンを作成することによっ
て、併合されたパターンのパターン空間上の位置は消滅
する。

【００１３】これに対し上記（２）は、代表パターンを
作成することなく、クラスタ内の個々のパターンとの類
似性を比較し、併合処理を繰り返す手法である。従って
(２)の手法は、併合するパターンのパターン空間上の位
置を保存する必要があるので、大量パターンの学習には
不適である。

【００１４】以降で併合処理といった場合は、上記
（１）の手法を用いることとする。ただし、計算機の発
展により、上記（２）の手法を取るのも不可能ではな
い。

【００１５】従来方法である「階層的クラスタリング」
について説明する。クラスタリングの対象となるｎ個の
パターン集合をＰ＝{ｐ０，ｐ１，...，ｐｎ−１｝とす
る。パターンｐｉとｐｊの距離または類似度を第ｉ行ｊ
列とする行列を、それぞれ、類似度行列，距離行列と呼
ぶことにする。この行列はあらかじめ表（リスト）の形
式で計算機上に実現してもよいが、大量のパターンを学
習させる場合には、表のサイズが巨大となるため、必要
になる度に逐次計算することにしてもよい。以降で用い
られている「距離」は、これらの距離に加えて上述の類
似度も含むこととし、パターン間の類似性を表す尺度を
表現する言葉として用いる。

【００１６】図５は従来の「階層的クラスタリング」を
説明する図である。初期のクラスタはそれぞれの学習パ
ターンであるとする（処理６０１）。処理６０２におけ
る閾値Ｔは、クラスタの併合を決定するための距離の閾
値である。処理６０４におけるｄｊｋは、クラスタＣｊ
とクラスタＣｋとの距離である。処理６０４において、
距離ｄｊｋが閾値Ｔ以下なら、クラスタＣｋをクラスタ
Ｃｊに併合する（処理６０５）。処理６０６においてｋ
をインクリメント（１増加）し、クラスタ数を越えなけ
れば、この処理を繰り返す（処理６０７）。次に、処理
６０８において、ｋをゼロと置くとともに、ｊをインク
リメントし、クラスタ数を越えなければ、さらにこれら
の処理を繰り返す（処理６０９）。閾値Ｔをあらかじめ
設定した増加分だけ増加させ（処理６１０）、最終値を
越えなければ、さらにこの処理を繰り返す（処理６１
１）。このような処理の繰り返しによって、小さなクラ
スタから徐々に大きなクラスタへと成長して行き、学習
が実行される。

【００１７】ここで、前記（２）の手法は、併合するパ
ターンのパターン空間上の位置を保存する必要があるの
で、大量パターンの学習には不適であると述べたが、以
下のような方法を用いることにより学習が可能となる。
この方法では、いわゆる最近隣法，最遠隣法，ウォード
法，重心法を用いて高性能なクラスタリング処理が可能
となるので、大量パターンの学習に不可欠の方法であ
る。

【００１８】パターン空間が２次元の場合を例として、
図３を用いて説明する。図３は、クラスタ代表点（中心
点や平均点や重心点）３０１の周辺のみを拡大して示し
てある。学習パターンのパターン空間上の点は、点３０
２や点３０３が示すように×印で示してある。学習パタ
ーンが膨大な場合は、クラスタ代表点の周辺に、千個と
か一万個とか、あるいはそれ以上のオーダーでパターン
が集中することがある。このようなパターンのパターン
空間上の点をすべて保存しておくための記憶容量は膨大
となり、場合によっては計算機の能力を越えるため、学
習処理の実現が不可能となる場合がある。

【００１９】本方法は、すべての位置を記憶しなくて
も、従来と同等のクラスタリングが可能となる方法であ
る。それは、図３において、クラスタの代表点を中心と
して、３０６のような線引きをし、領域を角度（クラス
タ中心点とのベクトルの方向）でもって分割し、各領域
の中で、クラスタ代表点から最も遠い位置にあるパター
ンのみを記憶する方法である。つまり、例えば、分割を
１度ごとに行えば、360等分することになるが、最大３
６０個のパターンのパターン空間上の位置を覚えるだけ
で済む。

【００２０】図３では、距離３０５がこの領域の中で最
も遠いためパターン位置３０２は記憶されるが、距離３
０４はクラスタ代表点３０１により近いパターン位置３
０３を記憶する必要はない。なお、記憶する必要のない
パターンは単純に消去し学習しないことにしてもよい
し、クラスタの代表点と併合してもよい。この方法によ
り、一クラスタあたり数千，数万、あるいはそれ以上の
パターンが集中し、学習ができないような場合であって
も、数百程度のパターンの処理で学習が実行できる。

【００２１】例えば手書き文字や、オムニフォント（多
種類の印刷文字）は、文字の変形が非常に多くなるた
め、膨大な学習パターンを用意し学習する必要がある。
従来通りすべてのパターンを学習させようとすると、膨
大な処理時間がかかってしまう。そのため、学習前に、
何らかの処理によって学習パターンを減らすことが必要
になる。

【００２２】もちろん、単にパターンを減らせばよいと
いうわけではなく、学習すべきパターンを単に除外して
しまうようなことがあってはならない。学習パターンを
減らすことによって、繰り返しの処理がパターン数のべ
き乗で少なくなっていく。図５ではループが３重のた
め、３乗で減少する。

【００２３】学習パターンを減らすには、 （１）カテゴリに分割する （２）学習パターンを単純に分割する （３）距離が極めて隣接しているパターンどうしをあら
かじめまとめておく （４）距離が極めて隣接しているパターンの中で、１個
のみまたは数個のパターンを代表パターンとして残し、
残りを除外する （５）構造解析結果を用いて分割する などの方法がある。ここで、カテゴリとは、例えば、数
字の場合は「０」から「９」まで、ひらがなの場合は
「あ」から「ん」までを指す。

【００２４】上記（１）や（２）や（５）に示すように
学習パターンを分割することによって、複数の計算機に
学習処理を分散し、並列的に処理し、学習時間を短縮で
きるという利点もある。あらかじめ分割し、クラスタリ
ングしたそれぞれのクラスタリング結果を纏めて、再度
クラスタリングすれば、分割しなかった場合と同等のク
ラスタリング結果を短時間の処理で得ることができる。

【００２５】上記（３）は、通常のクラスタリング手法
を用いてもよい。この場合は、ごく初期の内に処理を中
断する形となる。（４）は、膨大な学習パターンがある
場合は、ほとんど同じ形状のパターンが確率的に多く存
在するという考えに基づいている。つまり、ほとんど同
じ形状のパターンをいくつも学習に用いるのは無駄であ
り、１個だけ用いればよいという考えである。この１個
のパターンの選び方は、中心，平均，重心のパターンを
選ぶとか、ランダムに選べばよい。

【００２６】大量のパターンを学習する場合、パターン
空間上にパターンが密集することになり、図４に示した
いわゆる鎖効果が現れることとなる。図４は、パターン
空間上のあるクラスタの中心点（あるいはクラスタの代
表点）５０１（図の×印）とその近辺に存在する別のク
ラスタが併合されて、クラスタ中心が５０２に移動する
様子を示している。同様にして、クラスタ中心が、５０
３まで移動している。符号５０４はクラスタ中心の移動
の軌跡を示している。この鎖効果は、従来の「階層的ク
ラスタリング」においては、図５の符号６０４，６０
５，６０６，６０７が示す一連の繰り返し処理によっ
て、発生する。鎖効果は、本来あるべきクラスタの中心
が移動してしまい、本来併合されてはならないクラスタ
との併合を引き起こすという点で、あってはならない現
象である。この鎖効果をなるべく引き起こさないような
クラスタリング手法が必要である。

【００２７】鎖効果が起こらないようにするためには、
例えば図６に示すような、併合処理を連続的に行わない
よう、併合処理に制限を設けることによって解決でき
る。図５と図６の各処理は、ほぼ対応しており、処理６
０５と処理７０５が終わった後のみが異なっている。つ
まり、処理７０５において、クラスタの併合処理を行っ
た場合、このクラスタとの併合処理を一旦中止し、別の
クラスタとの併合処理へと移行させる。このように併合
を連続的に行わないようにすることによって、特に学習
の初期状態において、極小のクラスタが点在することに
なり、このクラスタを種（中心）として、クラスタが徐
々に成長することになる。結果として、パターンの変形
を適度に吸収し、バリエーションも豊富で、認識精度に
有効な辞書が作成される。

【００２８】パターンを大量に集めると、様々な変形を
含んだパターンが必然的に多くなるが、変形の度合いに
応じてその絶対数は少なくなる。つまり、変形の少ない
標準的な形状のパターンは多く、変形の大きいパターン
の個数は少ない。従って、大量のパターンをクラスタリ
ングした場合、少数個のパターンからなるクラスタ（辞
書）が大量に生成されることになる。このような辞書
は、認識の精度を高めるためにはある程度の個数が必要
であるが、これらの中には、言わば不必要な辞書も大量
に存在する。この不必要な辞書を正確に判定し、除外す
るなどして、辞書の絶対数を少なく、かつ高精度な認識
の可能な、効率の高い辞書を作成することが重要であ
る。

【００２９】そのためには、 （１）正解が少なく、不正解の多い辞書を削除する（図
７） （２）正解が少なく、不正解の多い辞書にペナルティを
設ける（図８） （３）形状が似ていることにより不必要と判定された辞
書を削除する などの方法が有効である。

【００３０】上記（１）は、図７に示すように、学習
（本発明の方法を含むどのような方法でもよい）処理９
０１の後、認識処理９０２を行う。認識処理はどのよう
な方法でもよいが、通常は、別に用意したテストパター
ンとすべての学習した辞書との類似度または距離を計算
し、認識判定９０５において最大の類似性を示した辞書
を認識結果とする。認識結果は正解の場合もあれば、不
正解の場合もある。例えば、数字の０を認識させる場合
に、認識結果は０（ゼロ）にならなければならないが、
認識結果が６となってしまった場合は、不正解となる。
この正解と不正解をそれぞれの辞書毎に個別に数えあげ
て、正解が少なく、不正解が多い辞書を削除し（９０
４）、この処理を繰り返すという方法である。

【００３１】具体的には、正解がゼロで、不正解が１以
上の辞書を消去，認識を再度行って、やはり、正解がゼ
ロで不正解が１以上の辞書を削除する。もし、削除する
辞書がなければ、正解が１個以下で不正解が１以上の辞
書を削除する。この処理を繰り返し、正解の個数を１個
ずつ増やしていき、例えば、正解が１０個以下で不正解
が１個以上となるまで繰り返す。これは非常に丁寧な方
法である。例えば、正解が１０個以下で不正解が１個以
上の辞書を削除するという処理をいきなり繰り返しても
よい。

【００３２】認識精度の限界に達した時は、この繰り返
し処理を終了する（９０３）。認識処理９０２を行うご
とに認識精度が計算できるので、認識精度の限界点は、
例えば、認識精度の上昇が鈍ったとき、認識精度が下降
した時、認識精度の上昇の度合いがある基準値を下回っ
た場合等となる。

【００３３】上記（２）は辞書そのものは消去しない
が、ペナルティを付加することによって、正解となるべ
き辞書が認識結果として上がってくるような方法であ
る。各辞書毎にペナルティを設ける。

【００３４】ペナルティの付加には、 （ａ）類似度減算型 （ｂ）類似度積算型 のような方法がある。

【００３５】上記（ａ）は、ペナルティの初期値はゼロ
である。認識処理の後、各辞書ごとに数え上げた正解と
不正解の個数をもとに、ペナルティを加算する。例え
ば、不正解数／正解数÷ｋを加算する。再度行う認識処
理において、実際に計算された類似度からこのペナルテ
ィを、認識判定１００５において減算する。類似度は通
常０から１の間の小数値を取るので、ｋは百とか千とか
いう一定値である。ｋは必ずしも一定値である必要はな
く、学習の進展具合に応じて変化させてもよい。

【００３６】上記（ｂ）は、ペナルティの初期値は１で
ある。認識処理の後、各辞書ごとに数え上げた正解と不
正解の個数をもとに、ペナルティを積算する。例えば、
正解数／（正解数＋不正解数）×ｋをペナルティに積算
する。ｋは定数または、上述のような変化する値であ
る。不正解数が多いほど、ペナルティは１より小さな値
となり、再度行う認識処理において、実際に計算された
類似度にこのペナルティを積算すれば、不必要な辞書の
類似度を相対的に下げることができる。ペナルティが充
分大きな辞書は、除去してもよい。

【００３７】上記（３）での判定は、類似度または距離
を計算することにより、類似性が高いと判定された辞書
に対しては、その中の一つ、あるいは数個の辞書があれ
ばよい場合がありえる。（３）に示したように、それ以
外の辞書を単純に消去してもよいし、一つずつ消去する
毎に認識処理を繰り返して、消去による影響を調べなが
ら、悪影響のない辞書のみを選択して消去してもよい。

【００３８】

【発明の効果】以上に説明した通り、本発明は、大量の
パターンを効率的に学習することが可能となる効果があ
る。

【図面の簡単な説明】

【図１】本発明を実現するシステム構成の一例を示すブ
ロック図。

【図２】クラスタリングの概念的説明図。

【図３】学習パターンの減少方法の説明図。

【図４】鎖効果の説明図。

【図５】従来の「階層的クラスタリング」のフロー図。

【図６】鎖効果を無くすクラスタリング手法の実施例の
フロー図。

【図７】不必要な辞書を除去する手法のフロー図。

【図８】不必要な辞書にペナルティを設定する手法のフ
ロー図。

【符号の説明】

１０１…入力制御部、１０２…表示制御部、１０５…ク
ラスタリング前処理制御部、１０６…クラスタリング制
御部、１０７…クラスタリング後処理制御部、１０８…
パターン認識制御部、１１１…辞書（クラスタリング結
果）、１１２…学習パターン、３０２，３０３…学習パ
ターンのパターン空間上での位置、304,３０５…クラス
タの代表点からの距離、５０１，５０２，５０３…学習
パターンのパターン空間上での位置、５０４…鎖効果を
説明するための軌道。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 嶋 好博 東京都国分寺市東恋ケ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 鈴木 和美 神奈川県小田原市国府津2880番地 株式会 社日立製作所ストレージシステム事業部内

Claims (12)

【特許請求の範囲】
1. 【請求項１】パターンをクラスタリングすることにより
   学習する装置であって、学習のためのパターンを入力す
   る手段と、該パターンを記憶する手段と、クラスタリン
   グ結果である辞書を記憶する手段と、クラスタリング前
   に該パターンの個数を調整するクラスタリングの前処理
   手段と、該パターンをクラスタリングするクラスタリン
   グ手段と、該クラスタリング手段によって作成されたク
   ラスタリング結果である辞書を調整するクラスタリング
   の後処理手段と、該辞書を用いてパターンを認識するパ
   ターン認識手段とを具備することを特徴とするパターン
   学習装置。
2. 【請求項２】請求項１記載のクラスタリングの前処理手
   段は、学習パターンをカテゴリ毎に分割することを特徴
   とするクラスタリングの前処理装置。
3. 【請求項３】請求項１記載のクラスタリングの前処理手
   段は、学習パターンを単純に分割することを特徴とする
   クラスタリングの前処理装置。
4. 【請求項４】請求項１記載のクラスタリングの前処理手
   段は、学習パターンをパターンの構造解析結果をもとに
   分割することを特徴とするクラスタリングの前処理装
   置。
5. 【請求項５】請求項１記載のクラスタリングの前処理手
   段は、学習パターンを類似性の高いパターンをあらかじ
   め纏めておき、学習パターン数を減らすことを特徴とす
   るクラスタリングの前処理装置。
6. 【請求項６】請求項１記載のクラスタリングの前処理手
   段は、学習パターンを類似性の高いパターンの中から代
   表パターンを選ぶことによって、学習パターン数を減ら
   すことを特徴とするクラスタリングの前処理装置。
7. 【請求項７】請求項２または請求項３または請求項４に
   記載のクラスタリングの前処理装置において、あらかじ
   め分割して学習したそれぞれのクラスタリング結果を纏
   めて、再度クラスタリングすることにより分割しなかっ
   た場合と同等のクラスタリング結果を得ることを特徴と
   するパターン学習装置。
8. 【請求項８】請求項１記載のクラスタリング手段におい
   て、クラスタの併合を分散化させる手段を具備すること
   を特徴とするパターン学習装置。
9. 【請求項９】請求項１記載のクラスタリング手段におい
   て、クラスタの代表点を中心とした放射状の領域にパタ
   ーン空間を分割し、該領域の中でクラスタの代表点から
   の距離の最も遠いパターンのみをクラスタ内のパターン
   として記憶することを特徴とするパターン学習装置。
10. 【請求項１０】請求項１記載のクラスタリングの後処理
    手段は、請求項１記載のパターン認識手段の結果を用い
    て、不必要と判定された辞書を削除することを特徴とす
    るクラスタリングの後処理装置。
11. 【請求項１１】請求項１記載のクラスタリングの後処理
    手段は、請求項１記載のパターン認識手段の結果を用い
    て、不必要と判定された辞書にペナルティを設定するこ
    とを特徴とするクラスタリングの後処理装置。
12. 【請求項１２】学習のためのパターンを入力する処理
    と、該パターンを記憶する処理と、クラスタリング結果
    である辞書を記憶する処理と、クラスタリング前に該パ
    ターンの個数を調整するクラスタリングの前処理と、該
    パターンをクラスタリングする処理と、作成されたクラ
    スタリング結果である辞書を調整するクラスタリングの
    後処理と、該辞書を用いてパターンを認識するパターン
    認識処理とを具備することを特徴とするパターン学習方
    法。