(57)【特許請求の範囲】
【請求項１】
薄板に発生する表面欠陥の分布形態を解析する表面欠陥の分布形態解析装置において、
少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力手段と、
前記入力手段によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成手段と、
生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出手段と、
前記初期クラスタ生成手段によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離手段と、
前記分離手段によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合手段とを備え、
前記分離手段においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、
前記分離手段は、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とする表面欠陥の分布形態解析装置。
【請求項２】
前記各手段によって生成されたクラスタの重心位置、空間サイズ及び個数密度のうち少なくともいずれか一つを特徴量として算出する特徴量算出手段と、
前記特徴量算出手段による算出結果を表示する解析結果表示手段とを更に備えたことを特徴とする請求項１に記載の表面欠陥の分布形態解析装置。
【請求項３】
前記分離手段は、集中的な分布をなす座標データを選択する手順として、個々の座標データについて集中的か散発的な分布に属するかを指定して得られる組み合わせから選択することを特徴とする請求項１又は２に記載の表面欠陥の分布形態解析装置。
【請求項４】
前記分離手段は、前記重み行列に行列要素が２つの変数を用いて平均からの偏差の積を求めた値の調整平均である行列の逆行列を用いることを特徴とする請求項１〜３のいずれか１項に記載の表面欠陥の分布形態解析装置。
【請求項５】
前記分離手段は、前記重み行列を固有行列と固有値を対角要素とする行列とに分解し、前記圧縮コスト算出時に用いるクラスタの分布形態に応じた関数により固有値を変換した値を用いて再構成した行列を用いることを特徴とする請求項１〜４のいずれか１項に記載の表面欠陥の分布形態解析装置。
【請求項６】
前記結合手段は、結合するクラスタの候補をクラスタの隣接関係を示すドロネー図に基づいて決めることを特徴とする請求項１〜５のいずれか１項に記載の表面欠陥の分布形態解析装置。
【請求項７】
薄板に発生する表面欠陥の分布形態を解析する表面欠陥の分布形態解析方法において、
少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力手順と、
前記入力手順によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成手順と、
生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出手順と、
前記初期クラスタ生成手順によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離手順と、
前記分離手順によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合手順とを有し、
前記分離手順においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、
前記分離手順では、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とする表面欠陥の分布形態解析方法。
【請求項８】
薄板に発生する表面欠陥の分布形態を解析する処理をコンピュータに実行させるためのプログラムにおいて、
少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力処理と、
前記入力処理によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成処理と、
生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出処理と、
前記初期クラスタ生成処理によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離処理と、
前記分離処理によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合処理とをコンピュータに実行させ、
前記分離処理においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、
前記分離処理では、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、薄板の表面欠陥の分布形態解析装置、方法、プログラムに関し、例えば自動車や家電製品の外板等、良好な外観を要求される薄板製品に発生する疵や汚れ等の表面欠陥について、その発生個数や発生位置、更にはその分布形態から、表面欠陥の発生要因を分析するために用いて好適な技術に属する。
【背景技術】
【０００２】
薄板コイルのような鉄鋼製品に発生する疵や汚れ等の表面欠陥の発生要因を分析するために、例えば光学式の自動疵検査装置を用いて、プロセスラインを通過するコイルの表面欠陥を検出し、検出した表面欠陥に関する情報を保存することが行われている。
【０００３】
特許文献１には、薄板コイルに発生し、自動疵検査装置等によって収集・蓄積された少なくとも発生位置を含む疵データから、疵の分布形態に関する情報を定量的な指標として自動的に抽出し、提示するようにした薄板の表面欠陥の分布形態解析手法について開示されている。
【０００４】
特許文献１に開示された薄板の表面欠陥の分布形態解析手法では、自動疵検出装置で採取された疵データに基づいて、疵同士を自動的にグループ化する。その場合に、直線状の分布と楕円状の分布とが混在した状況を統一した指標で扱うことができれば有用であることから、直線と楕円とを近似的に表現し得る手法として、各疵グループの分布形態を二次元のガウス関数で表現するようにしている。
【０００５】
非特許文献１に開示されたクラスタリング手法では、ノイズと考えられる部分を分離したクラスタを生成する方法である。
【０００６】
【特許文献１】特開２００５−２５７６６０号公報
【非特許文献１】C.Bohm,C.Faloutsos,J.Pan,and C.Plant. Robust Information-theoretic Clustering. In KDD Conference,pages 65-75,2006.
【非特許文献２】D.Chakrabarti,S.Papafimitriou,D.S.Modha,and C.Faloutsos.Fully automatic cross-associations.In KDD Conference,pages 79-88,2004.
【非特許文献３】D.A.Huffman,"A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., sept 1952, pp 1098-1102
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、薄板コイルにおいては密集する分布形態と散発的な分布形態を区別して扱う必要がある。疵同士のグループ化の際に、上述したような散発的な分布形態を別個に扱えないクラスタリングの手法をそのまま利用すると、発生要因分析で誤った解析結果となることになる。非特許文献１の手法を適用することで、薄板コイルにおいて区別して扱う必要がある密集する分布形態と散発的な分布形態を表わすことができるが、初期クラスタ数が少なければ適切なクラスタが生成されない、多ければ計算時間がクラスタ数の３乗のオーダーで増加する問題がある。
【０００８】
本発明は、散発的な分布形態を区別し、自然な形で薄板の表面欠陥をグループ化する際に、初期クラスタ数が異なっていても適切なクラスタを生成することができるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の表面欠陥の分布形態解析装置は、薄板に発生する表面欠陥の分布形態を解析する表面欠陥の分布形態解析装置において、少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力手段と、前記入力手段によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成手段と、生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出手段と、前記初期クラスタ生成手段によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離手段と、前記分離手段によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合手段とを備え、前記分離手段においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、前記分離手段は、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とする。
本発明の表面欠陥の分布形態解析方法は、薄板に発生する表面欠陥の分布形態を解析する表面欠陥の分布形態解析方法において、少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力手順と、前記入力手順によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成手順と、生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出手順と、前記初期クラスタ生成手順によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離手順と、前記分離手順によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合手順とを有し、前記分離手順においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、前記分離手順では、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とする。
本発明のプログラムは、薄板に発生する表面欠陥の分布形態を解析する処理をコンピュータに実行させるためのプログラムにおいて、少なくとも解析対象の薄板の表面欠陥の発生位置に関する座標データを入力する入力処理と、前記入力処理によって入力された集中的な分布と散発的な分布が混在した表面欠陥の座標データに基づいて、所定のクラスタリング手法を用いて、前記薄板の表面欠陥の分布形態を表わす初期クラスタを生成する初期クラスタ生成処理と、生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出処理と、前記初期クラスタ生成処理によって生成された初期クラスタを、前記圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組み合わせに分離したクラスタを生成する分離処理と、前記分離処理によって生成された集中的な分布をなす座標データを含むクラスタ同士を、前記圧縮コストを結合判断基準に用いて結合する結合処理とをコンピュータに実行させ、前記分離処理においてクラスタから分離された散発的な分布をなす座標データを、新規の又は別のクラスタの集中的な分布をなす座標データとして組み入れ、前記分離処理では、クラスタ内の座標データの調整平均によって求めた座標を中心とし、クラスタ内の座標データのばらつきを示す重み行列として、クラスタ内の全点の座標データの調整平均により生成される分散共分散行列の逆行列を用いて中心からの距離を定め、集中的な分布をなす座標データを距離が短い順に選択することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、分布の疎密に応じた自然な形で薄板の表面欠陥をグループ化することができる。また、初期クラスタ数が異なっていても適切なクラスタを生成することができる。これにより、薄板の表面欠陥の分布形態の解析精度を高めるとともに、例えば表面欠陥グループの重心位置、空間サイズ、表面欠陥個数密度といった表面欠陥の分布に係わる特徴量抽出を高速かつ大量に、そして正確に行うことが可能になる。
【発明を実施するための最良の形態】
【００１１】
以下、添付図面を参照して、本発明の好適な実施形態について説明する。
図１は、本実施の形態の薄板の表面欠陥の分布形態解析装置の構成の一例を示す図である。以降では、欠陥を疵と記す。１０１は疵データ入力部であり、鉄鋼製品である薄板コイルのプロセスラインや検査ラインに設置された自動疵検査装置で測定された少なくとも発生位置情報（座標データ）を含む疵データを、コンピュータネットワークやコンピュータ読み取り可能な記録媒体を介して本装置に入力するための入力手段として機能する。疵データには、薄板コイルの二次元平面内のある基準位置を原点とする疵の発生位置に関する座標データが含まれる。薄板コイルの圧延方向の座標をｘ、幅方向の座標をｙとし、当該薄板コイル内にＮ個の欠陥が発生した場合、座標データは、Ｎ行２列の行列で表現することができる。また、疵データには、各疵が薄板コイルの表面、及び裏面のいずれに発生しているかを識別するための情報や、薄板コイルの圧延方向の長さや幅等、疵が発生したコイルに関する寸法情報が含まれている。更に、疵の圧延方向の寸法値と幅方向の寸法値、疵の種類、及び疵の有害度等の情報が含まれる場合もある。
【００１２】
１０２は疵データ蓄積部であり、疵データ入力部１０１によって入力された疵データを保存、蓄積する。そして、解析を行う際に、外部から入力される疵分布出力指示に応じて、コイル単位で疵データを取り出す機能を有する。また、薄板コイルの表面と裏面とで、疵データをそれぞれ別個に解析したい場合には、各疵の発生面情報（疵が表面及び裏面のいずれにあるかに関する情報）を用いて疵データを分離することによって、解析したい面の情報のみを取り出す。
【００１３】
１０３は演算部であり、疵データ入力部１０１によって入力され、疵データ蓄積部１０２に蓄積された疵データに基づいてクラスタリングを行い、得られたクラスタから疵の分布形態を特徴量化する演算処理を実行する。演算部１０３は、初期クラスタ生成部１０３ａと、圧縮コスト算出部１０３ｂと、分離部１０３ｃと、結合部１０３ｄとを含み、これら各部１０３ａ〜１０３ｄによって疵同士をグループ化（クラスタリング）し、更にはそれら疵グループ（クラスタ）の重心位置、空間サイズ、個数密度といった疵の分布に係わる特徴量を求める特徴量算出手段としても機能する。なお、疵グループの重心位置、空間サイズ、個数密度の求め方については、例えば特許文献１に開示されているように、重心位置を座標データの平均により求め、空間サイズを分布するデータを覆う重心位置を中心とした二次元ガウス関数のパラメータである２つの標準偏差とし、個数密度をグループ内の疵個数を空間サイズを示すそれぞれの標準偏差で除算した値とするように、既存の技術を用いればよい。
【００１４】
初期クラスタ生成部１０３ａは、疵データ入力部１０１によって入力され、疵データ蓄積部１０２に蓄積された疵データに基づいて、例えばＫ-ｍｅａｎｓ法といったクラスタリング手法を用いて、期待するクラスタ数を下限として、疵の分布形態を表わす初期クラスタを生成する初期クラスタ生成手段として機能する。Ｋ-ｍｅａｎｓ法の詳細な説明は省略するが、Ｋ-ｍｅａｎｓ法は、各クラスタの中心点を定め、クラスタ内の各疵データと中心点との距離を求め、その距離の２乗の総和を最小化するように疵データの各クラスタへの再割り当てと再割り当てによるクラスタの中心点の修正を繰り返し行う方法である。
【００１５】
圧縮コスト算出部１０３ｂは、詳細は後述するが、生成したクラスタの良さを評価する指標である圧縮コストを、クラスタの分布形態に応じて座標データの情報圧縮を行った際の情報量として算出する圧縮コスト算出手段として機能する。
【００１６】
分離部１０３ｃは、詳しくは後述するが、初期クラスタ生成部１０３ａによって生成された初期クラスタを、圧縮コストに基づいて、集中的な分布と散発的な分布をなす座標データの組みに分離したクラスタを生成する分離手段として機能する。
【００１７】
結合部１０３ｄは、詳細は後述するが、分離部１０３ｃによって生成された集中的な分布をなす座標データを含むクラスタ同士を、圧縮コストを結合判断基準に用いて結合する結合手段として機能する。
【００１８】
１０４は解析結果表示部であり、指定された薄板コイルに関する演算部１０３による演算結果に基づいて、クラスタリングされた疵の分布に係わる特徴量を表示する解析結果表示手段として機能する。
【００１９】
ここで、本発明で導入するクラスタリング手法の概要について説明する。
【００２０】
あるデータ集合を考えた場合、図２（ａ）は、多くの人間の感覚として良いと思われるクラスタリングの例を示し、ガウス分布状の１つのクラスタ、直線分布状の１つのクラスタ及び散発的に発生している点（以降、外れ点と呼ぶ）が含まれている。それに対して、図２（ｂ）は、一般的なクラスタリング手法（例えばＫ-ｍｅａｎｓ法）によるクラスタリングの例を示し、散発的に発生している外れ点を含むガウス分布状の５つのクラスタが生成されている。
【００２１】
本発明で導入するクラスタリング手法は、教師なしクラスタ分割法であり、図２（ａ）に示すようなクラスタリングを実現すべく、圧縮コストなる新たな指標を導入する。圧縮コストは、１つの点が２つのクラスタのいずれに属するのが適当であるかを表わす指標として用いる。そして、例えばＫ-ｍｅａｎｓ法（クラスタ数ｋを指定）によるグループ化の後、圧縮コストに基づいて、外れ点分離及びクラスタ結合というアルゴリズムを実行する。
【００２２】
換言すれば、クラスタの良さを示す圧縮コストなる指標を使用して、
（Ｍ１）外れ点の存在下におけるクラスタ形状のロバストな評価
（Ｍ２）圧縮コストに基づく外れ点の識別、分離
（Ｍ３）圧縮コストに従った結合によるクラスタの構築
というアルゴリズムを実行する。
【００２３】
＜圧縮コスト＞
圧縮コストは、情報量圧縮方法の１つのハフマン符号化（非特許文献３を参照）を利用し、圧縮前の符号の出現確率を用いて圧縮した場合に平均符号長（単位はビット）が最小となる特長を応用したものである。
【００２４】
クラスタ内の発生位置の出現確率の代わりに予め用意した複数の確率分布（例えば、ガウス分布、ラプラス分布、一様分布等の任意の分布）を用いて符号化を行った場合、符号長が最小となった確率分布がクラスタの形状（特徴）を最も良く表わしている分布である
ことを示す。
【００２５】
更に、個々のクラスタの確率分布による圧縮コストに加え、クラスタの中心位置、確率分布の形態を示す情報、平均や分散等の確率分布を示すパラメータ、クラスタ内のデータ個数等といった複数のクラスタを識別するための情報も符号化及び情報圧縮を行い圧縮コストに加える。これにより過度に複数のクラスタに分離されることを防ぐことができる。
【００２６】
本発明では、クラスタの形状を示す確率分布の利用によって情報量圧縮を行い、その際のクラスタ番号及びデータ点の座標のための符号長と符号化に必要なその他の情報量に相当する符号長を合わせて圧縮コストとして定義し、圧縮コストを最小化することで所望のクラスタを生成する手法を提示するものである。
【００２７】
符号化に必要なその他の情報量に相当する圧縮コストには、クラスタ数ｋを示す符号長、各クラスタの形状を示すパラメータ（例えばそれがガウス分布形状のクラスタである場合、平均及び分散）を示す符号長等が含まれる。詳細は以下で触れて行く。
【００２８】
ここで扱う座標データはすべて有限精度しか取り扱わないので、整数であると仮定して符号化を行う。すなわち、データ点はｄ次元のグリッド上に存在するものとする。グリッドの分解能は任意に選択できる。例えば、座標データの有効数字が小数点第１桁までであった場合は、グリッド定数で表わすグリットの分解能を、小数点第1桁の最小値である０．１とするとよい。
【００２９】
以下の本願の手法は、（ａ）整数の符号化手法、（ｂ）一旦クラスタに属するとされた点の符号化手法からなる。
【００３０】
いま、図２に示したデータ集合を持っているとする。ここでは、ガウス分布及び一様分布（最小外接長方形を範囲とした一様分布）といった２つの分布が利用可能であるものとする。一旦、点をクラスタに割り当てれば、クラスタ中心からの偏差に対し、ハフマン符号化（非特許文献３を参照）を適用することにより、少ないデータ量で効率的に記録する
ことができる。
【００３１】
（整数の符号化）
小さい整数にはより少ないビット数で、大きい整数にはより多いビット数で符号化を行う為に１進数表記にて整数の符号化を行う。１進数表記における基本の表記方法は、自然数の大きさに応じて零を並べるものである。本願では０と１を用いた１進数表記法であるイライアスコード或いはSelf-delimiting法と呼ばれる１進数符号化（非特許文献２を参照）を用いる。これらの符号化の方法では、正の整数ｉをＯ（ｌｏｇ(ｉ)）のビット数を使用して表わすために、整数値が一定量変化しても符号化後のビット数の変化は変化前の整数値が小さいほど大きく変化する。下記の表１に示すように符号化できる。１進数表記では、整数ｉの符号化した長さ（符号長）を示す部分と、符号化した値（符号値）を示す部分からなる。ここで注意すべきことは、符号値の最初のビットを常に「１」で示すことである。整数ｉの符号化後の長さを示す符号長は連続する零のビット数で示すために、符号値を示す部分はビットが最初に「１」となる部分から符号長の零と同じビット数の範囲である。正の整数ではない零を扱うためには、値に１を加えて符号化を行うことで扱える。また、負の数を扱うためには、値の正負を示すビットを追加することで拡張できる。
【００３２】
【表１】
0005262582.tif 000002
【００３３】
（点の符号化）
各クラスタＣには、クラスタ無相関化の必要性の有無を示すフラグＲと、無相関化を行う行列Σ*、クラスタのデータ分布の形状を示すフラグＴ（形状は任意の確率分布を予め用意する。例えば、ガウス分布、ラプラス分布、一様分布）とその中心座標及びデータ分布のパラメータが関係する。一旦、点ＰがクラスタＣに属すると決定すれば、点ＰがクラスタＣの分布に従うことを利用して、点の座標を符号化できる。点Ｐのi番目の座標Ｐｉの確率の値がｐである場合、座標の符号化によってＯ（ｌｏｇ(１／ｐ)）ビットを必要とする。
【００３４】
確率が一定値となる一様分布にて符号化した際のビット数を、最小外接長方形（第i次元目が下限ｌｂiと、上限ｕｂiで表わされる範囲）の範囲を定め、最小外接長方形の範囲に比例するＯ（ｌｏｇ(１／（ｕｂi−ｌｂi）)）のビット数で定める。
【００３５】
点の符号化の目的は、点がクラスタ部分空間及びクラスタ特有の確率分布に従う場合に、圧縮コストが最小となるクラスタＣの点ｘ→（本明細書においてａ→との表記はａの上に→が付され、ベクトルであることを意味するものとする）の符号化手法を提案することである。後述するが、正しい選択により圧縮コストを最小化する確率密度関数を得ることになる。
【００３６】
ここでは、クラスタの点の座標が主成分分析（ＰＣＡ）による座標変換によって無相関化され、各座標から対応するパラメータと共に確率分布が既に選択されているとする。図３の例については、横座標をラプラス分布とし、縦座標をガウス分布とする。両分布は、平均μ＝３．５及び標準偏差σ＝１を仮定している。座標値を符号化し必要なビット数を割り当てる必要がある。すなわち、高い確率（例えば３＜ｘ＜４）に相当する座標値には短いビット数（符号）を割り当て、低い確率（極端な例としてｙ＝１２）に相当する座標値には長いビット数（符号）を割り当てる。
【００３７】
クラスタのデータ分布の形状を示すフラグＴで示される確率分布がデータの分布に一致していれば、ハフマン符号化によるビット数（符号長＝圧縮コスト）が最小化される。ハフマン符号化は、Ｐ(ｘi)が各座標値の確率密度関数の値である場合、個々の座標ｘiに長さｌｏｇ2(１／Ｐ(ｘi))のビット数を割り当てる。
【００３８】
（圧縮コストの算出方法）
ここで、クラスタＣの圧縮コストを以下の４つの定義に沿って定義する。
・定義１（点ｘ→の圧縮コストＥ）
ｘ→∈ＲdがクラスタＣに属するとし、ｐｄｆ→(ｘ→)はクラスタＣの確率密度関数のｄ次元のベクトルである。各座標の確率密度関数ｐｄｆi(ｘi)は、対応するパラメータ（すなわち、ＰＤＦ＝｛ｐｄｆカ゛ウス(ui,σi)，ｐｄｆ一様(lbi,ubi)，ｐｄｆラフ゜ラス(ai,bi)，・・・｝、平均ｕi、下限ｌｂi、上限ｕｂi、片側平均ａi∈Ｒ、標準偏差σi、√２の標準偏差ｂi∈Ｒ+）を有する１セットの予め定められた確率密度関数から選択される。γをグリッド定数（グリッドの分解能、すなわちグリッド間の距離）とし、点ｘ→の座標軸ｉでの圧縮コストＥiは下式（１）で表わされ、点ｘ→の圧縮コストは下式（２）で表わされる。
【００３９】
【数１】
0005262582.tif 000003
【００４０】
図３のハッチングした例示位置において、ｘ座標（２と３の間）の確率は１９％であり、ハフマン符号化ではｌｏｇ2（１／０．１９）＝２．３ビットが必要となる。ｙ座標はより低い確率（５％）にあり、より大きいビット数（４．３ビット）が必要となる。点ｘ→の圧縮コストは、ｘ座標とｙ座標のビット数の合計である６．６ビットに加えて、どのクラスタに所属するかをハフマン符号化されたクラスタ番号を表わすｌｏｇ2(ｎ／｜Ｃ｜)ビットが加えられる。
【００４１】
（クラスタに適合する確率密度関数の決定）
次に、クラスタＣにどの確率密度関数を割り当てるかを示す。最終的な目的は圧縮コスト（ビット数）の最小化である。従って、各座標軸にクラスタの圧縮コストを最小化する確率密度関数ｐｄｆ（及び対応するパラメータ）を選択する必要がある。ガウス分布等の確率密度関数ｐｄｆについては、最適なパラメータがデータ集合の統計量（例えば平均、分散σi2、上下限値）に相当することが知られている。
【００４２】
したがって、座標軸ｉの確率密度関数ｐｄｆとしてガウス分布を選択する場合、確率密度関数のパラメータとして、点の座標軸ｉの平均ｕi及び分散σi2を使用する。同様に、ラプラス分布については、平均ｕi及び分散２σi2を適用する。一様分布については、座標値の範囲の上限ｕｂiと下限ｌｂiを適用する。予め用意したガウス分布、ラプラス分布、一様分布等、これらの確率密度関数ＰＤＦの中からクラスタの圧縮コストが最小となる確率密度関数を選択する。
【００４３】
・定義２（クラスタＣのｐｄｆ→(ｘ→)）
Ｃを点ｘ→∈Ｃからなるクラスタとする。Stat＝（ｕi、σi、ｌｂi、ｕｂi・・・）を予め用意した確率密度関数ＰＤＦで必要とされる統計量とする。このとき、ｐｄｆ→は下式（３）に示すように、ｐｄｆi∈ＰＤＦから圧縮コストが最小となる確率密度関数が選択される。
【００４４】
【数２】
0005262582.tif 000004
【００４５】
図３のｘ座標について、統計として平均（３．５）、分散（１．０）、上下限（１．４、６．２）を計算する。その後、ｘ座標の圧縮コストＥxは予め用意した確率密度関数に適切な統計量を適用したｐｄｆ一様(1.4,6.2)、ｐｄｆカ゛ウス(3.5,1.0)、ｐｄｆラフ゜ラス(3.5,0.7)の中から最小の圧縮コストＥxとなる確率密度関数を選択する。ｙ座標についての圧縮コストＥyについても同様の手順で確率密度関数を選択する。なお、ここでは、ガウス分布、ラプラス分布、一様分布といった３つの分布を取り上げているが、他の確率密度関数も用いることができる。
【００４６】
（無相関化行列を用いた符号化）
クラスタが異なる座標軸で互いに相関のあるクラスタである場合、すなわち、クラスタの点のある座標値が少なくとも１つの他の座標値に依存する場合、無相関化行列により新たな座標軸に変換することで圧縮コストを縮小することができる場合がある。無相関化行列は、例えばクラスタの分散共分散行列Σの主成分分析（ＰＣＡ）で算出する主成分からなる行列やクラスタの分散共分散行列Σの固有行列Ｖとして計算することができる。外れ点（1つの座標軸に着目すれば外れ値）に影響されにくいロバストな方法での分散共分散行列の評価方法は後述する。
【００４７】
データを無相関化することは、クラスタの圧縮コストを縮小させるために必要である。大きい分散及び高い相関のある２つの座標を持つ代わりに、互いに相関のない２つの新しい座標を生成し、例えば一方の新しい座標が０に近い分散を持つ座標値に変換できれば、1つのグリッドの確率が大きくなるため、平均符号長がほぼ０ビットの圧縮コストとなることが期待される。そのため、圧縮コストの改善を考慮する場合、無相関化行列を使用する。
【００４８】
・定義３（クラスタの無相関化）
無相関化行列は、Ｃを点ｘ（無相関化を行っていない元々の座標）から成るクラスタとし、クラスタＣの共分散行列Σとしたときに、クラスタＣの主成分分析（ＰＣＡ）で算出する主成分（Σ＝ＶΛＶT）からなる行列ＶΛ-1/2とする。若しくは、クラスタＣの分散共分散行列Σの固有値と固有行列による対角化（Σ＝ＶΛＶT）で得られた行列を無相関化行列Ｖと定めるとする。Ｙを無相関化された点ｙの集合、すなわちｙ→∈Ｙ：ｙ→＝ＶT・ｘ→として表わされるものとする。ｐｄｆ→(ｘ→)を元々の座標系の、ｐｄｆ→(ｙ→)を無相関化された集合Ｙを特徴付ける確率密度関数（確率分布）とする。最終的に用いられる無相関化行列は、圧縮コストを基準に定まり、クラスタＣの無相関化行列dec(C)は下式（４）で、それに対応する圧縮コストは下式（５）で表わされる。
【００４９】
【数３】
0005262582.tif 000005
【００５０】
ｄ行×ｄ列の無相関化行列Ｖを符号化する際に、少数を符号長ｆビットで表わすとすると、各要素を合計ｄ2ｆビットで符号化する。そのため、無相関化による圧縮コストの減少分がこれを上回った場合に無相関化を行う。無相関化不要の場合は、無相関化行列の代わりに単位行列を用いて、無相関化の有無を表わすフラグに相当する１ビットだけを圧縮コストに加える。
【００５１】
・定義４（クラスタの圧縮コスト）
定義４は上述した事項を総括したものである。クラスタＣを符号化する際には無相関化行列ｄｅｃ(Ｃ)及び無相関化された各座標ｙ→を代表する確率密度関数ｐｄｆ→(ｙ→)を用いて行う。クラスタＣの圧縮コストは、下式（６）で表わす。
【００５２】
【数４】
0005262582.tif 000006
【００５３】
圧縮コスト算出部１０３ｂは、以上説明したように、疵データ入力部１０１によって入力され、疵データ蓄積部１０２に蓄積された疵データに基づいて、上式（６）等に示した圧縮コストを算出する。
【００５４】
＜外れ点の分離＞
本願では、従来手法で得られるクラスタを２つの部分集合からなるとして捉える。一つは集中的な分布の中核をなすを示すデータ（中核点）の集合、もう一方は散発的な分布をなすデータ（外れ点）の集合である。
【００５５】
一般的なクラスタリング手法のＫ-ｍｅａｎｓ法やＫ-ｍｅｄｏｉｄｓ法では、中核点と外れ点とが混合したクラスタが生成されてしまい、特徴を捉え難いクラスタとなるおそれがある。
【００５６】
そこで、一旦生成したクラスタ（初期クラスタ）から外れ点を分離する。
【００５７】
最も確実な方法は、Ｎ点の座標データがあった場合、中核点と外れ点に分類する組み合わせは２N通りある。それぞれの組み合わせに対して圧縮コストを算出し、圧縮コストが最小となる中核点と外れ点の組み合わせを採用することである。しかしながら、計算量は、座標データ数に対して指数関数的に増加する為に、ある程度の数を超えると現実的な時間で計算を終了することは困難になる。
【００５８】
以降では、ある程度の数を超えても現実的な時間で計算を終了するように、座標データに中核点に取り入れる順位付けを行い、中核点と外れ点の分離に要する計算量をＮに比例する方法を提供する。
【００５９】
順位付けの方法として中核点の中心からの距離を元に算出する方法である。以下では順位の代わりに距離で定めた境界によって中核点と外れ点を選択している。距離の定義は、中核点の外形を決めるために複数の定義を用いる。
【００６０】
クラスタ内の座標データの分布のばらつきを示す重み行列による距離によって中核点と外れ点の分離をする方法は、任意のクラスタリング手法（例えばＫ-ｍｅａｎｓ法）により算出したクラスタ群C＝｛Ｃ1，・・・，Ｃk｝のクラスタＣiについて部分空間を定める正規直交行列Ｖ（「無相関化行列Ｖ」と称する）を算出する。無相関化行列Ｖを用いた重み行列を算出し、中核点と外れ点とを分離する境界を決定する距離を定めるものである。クラスタＣi中の中核点と外れ点の圧縮コストの合計が最小値となるクラスタの中心から等距離となる境界（楕円）を選択し、その結果、クラスタから外れ点を分離した新たなクラスタを生成する。このときのクラスタの中心は、座標データの平均又は、調整平均によって求めた座標を用いる。
【００６１】
以下、更に距離を定めるための重み行列について詳しく説明する。まず重み行列の評価方法の１つについて述べる。クラスタＣiの重み行列は、クラスタＣiに属する点が含まれる空間を定めるものとして分散共分散行列の逆行列（Σ-1＝Ｖ∧-1ＶT）を用いる。逆
行列が直接算出できない場合は、主成分分析（ＰＣＡ）による主成分を用いる等して、これに変わる行列を算出する。また、別の方法としてクラスタＣiに属する点の分散共分散行列Σを固有値による対角行列を用いて表すと、固有ベクトルからなる正規直交行列Ｖが
得られる。この行列Ｖが上記で述べた無相関化行列である。無相関化行列Ｖは、クラスタＣiの点が含まれる空間（新たな座標軸）を定め、固有値は後で述べる等距離からなる境界の楕円（楕円球）の形状を決める。また、対角行列∧の全固有値は正である為、分散共分散行列Σ及びその逆行列Σ-1は半正定行列である。すなわち、２点間を結ぶベクトルを
ｘとしたときにｘtΣ-1ｘの様に、２次形式で表した際に必ず正となり、多次元空間にお
いても、あたかも２点間の距離ような値（擬距離）を定めることができる。例えば、クラスタの構造（共分散）を考慮して、２つの点であるｘ→及びｙ→間の距離を、下式（７）に示すようにマハラノビス距離として定義できる。
【００６２】
【数５】
0005262582.tif 000007
【００６３】
クラスタＣの中心をμ→として与えると、分散共分散行列Σは、下式（８）により行列ΣCを計算することで評価することができる。なお、｜Ｃ｜はクラスタＣのデータ点数である。（ｘ→−μ→）・（ｘ→−μ→）Tはベクトルの外積であり、ｄ×ｄの行列となる。ｘ→（∈Ｃ）すべてについて計算し、クラスタＣのデータ点数｜Ｃ｜で平均化するので、ΣCは、行列のｉ行ｊ列の要素（ΣC）ijは第ｉの座標と第ｊの座標の共分散であって、（ｘi−ｕi）・（ｘj−ｕj）となる。
【００６４】
【数６】
0005262582.tif 000008
【００６５】
ここで、上記計算法で外れ点が含まれることにより、中核点と外れ点を希望通りに分離できない問題が生じる。希望通りの分割を行うためには、詳細は後述するが中核点の中心と分散共分散行列を的確に推定する必要がある。しかしながら、単純な平均で計算されるクラスタＣの中心は、外れ点の存在により中核点の中心からずれることがある。また、中心核点の中心と異なる中心に従えば分散共分散行列による無相関化行列Ｖによって生成される空間、すなわち中核点と外れ点の境界の候補となる「中核点の広がり」を評価する楕円の方向にも外れ点が影響することがある。外れ点の数が１つの場合でも、推定する中核点の中心や無相関化行列に大きく影響を与えることがある。図４には、従来の評価により中心が間違って推定され、データの共分散を表わす楕円が中核点とずれている様子を示す。
【００６６】
（中核点のロバストな中心μR→の推定方法）
中心を定めるに際して、外れ点に影響されにくいという意味でのロバストさのある中心を、各座標のα調整平均を独立して決定する。ここでα調整平均は、対象データからデータ数の上位α／２％と下位α／２％に相当するデータを除いた部分を用いて平均を行う方法である。すなわち中央値はαを１００に近づけてゆき最後の１点だけが残る場合に相当する。αの値は、想定される初期クラスタに占める中核点の比率に設定するとよい。これにより、中央値によるデータの原点（μR→）が、全点の中心（μ→）に比べて、クラスタの中核点の中心の近傍となる。
【００６７】
（中核点のロバストな重み行列（分散共分散行列）ΣR推定方法）
同様に、ロバスト分散共分散行列（ΣR）ijは、クラスタの全点ｘ→についての（ｘi−μRi）・（ｘj−μRj）のα調整平均により生成されるようにしている。調整平均とは、平均を算出しようとする数値を大きさ順に並べ、先頭又は最後尾から一定割合αのデータを除き中央値付近のデータを用いて求める平均である。αの値は、初期クラスタに占める中核点の想定される割合の２乗に設定するとよい。行列ΣRには、算術平均による共分散行列と比較して、中核点の共分散が反映されることが期待できる。
【００６８】
算術平均による共分散行列ΣCは対角優勢（＝正定行列）である。すなわち、各対角成分Σi,iが他の要素Σ*，ｉの合計よりも大きい。また、対応する対角行列Λの全固有値は正となる。
【００６９】
一方、ロバスト分散共分散行列ΣRが対角優勢行列ではない場合は、２次形式で表した値が負となる場合が発生し、距離を定義できなくなる。そのためにφ倍された単位行列φ・Ｉを付加することで、無相関化行列Ｖに影響を与えることなく計算を可能とする。φは、下式（９）に示すように与えられる。φの値は、縦列の合計と対角成分との極大差（１０％程度の値を付加してもよい）で表わされる。
【００７０】
【数７】
0005262582.tif 000009
【００７１】
行列φ・Ｉを付加することにより、固有値には影響を与えるが、固有ベクトルに影響を与えない。Σ＝ＶΛＶTである場合、Σ＋φ・Ｉ＝ＶΛＶT＋φ・Ｉとなる。Ｖは正規直交であるので、φ・ＩもまたＶφＩＶTと記述でき、また、分配則に従えば、Σ＋φ・Ｉ＝Ｖ（Λ＋φ・Ｉ）ＶTとなる、すなわち各固有値が増加しても、無相関化行列Ｖには影響を与えない。
【００７２】
（重み行列に中核点の特徴を反映させる変換）
上記では、分散共分散行列を元に距離を定めて中核点を距離の短い順に選択する為、クラスタ（中核点）の外形となる境界が楕円（楕円球）となる。そのため、直線等、楕円で表現しにくい形状のクラスタ（中核点）を分離する際に、外れ点を一部分離しきれない場合がある。本願では、クラスタ（中核点）の圧縮コスト算出に用いる確率分布に応じた重み行列の変換方法を提供する。
【００７３】
楕円状以外の形状をしたクラスタを抽出する為に、重み行列を修正することで抽出する方法を示す。重み行列の固有値は、クラスタの外形を示す楕円の長軸と短軸の長さに比例する値となる。そのため、固有値を変化させて長軸と短軸の長さの比を変化させることで、境界の形状を変化させることで、外れ点としたい点の中核点への、又は中核点としたい点の外れ点への混入を減らす。
【００７４】
重み行列を対角化によって分解し、クラスタの分布形態に応じた関数により変換した対角要素を用いて重み行列の再構成を行った行列を用いて距離を定め中核点の候補を選択する。具体的には、重み行列を固有行列と固有値を対角要素とする行列とに分解し、圧縮コスト算出時に用いるクラスタの分布形態に応じた関数により固有値を変換する。変換した値を新たな対角行列の要素として、重み行列を再構成し、距離算出に用いる。
【００７５】
重み行列Σを対角化した場合、固有値を対角要素とする行列∧と、固有行列Ｖを用いて
下式（１０）と示す。
Σ＝Ｖ∧ＶT・・・（１０）
【００７６】
このとき、重み行列Σが対角優位でなければ固有値を対角要素とする行列∧にφ倍され
た単位行列φ・Ｉを付加する。値φは、この操作で各固有値間の比率が、それほど変化しない程度にする。
【００７７】
圧縮コスト算出時には、固有値に対応する固有ベクトル毎に確率分布を定めている。固有値の比率を変化させる際に、圧縮コスト算出時に用いる確率分布に応じて固有値を変化させる。このとき、中核点を選択する順序を決める距離を算出する場合には重み行列の逆行列を用いるため、重み行列の固有値が大きい程固有値の逆数が小さくなり、対応する方向への距離の変化が小さくなる。
【００７８】
比率を変化させる場合に正規分布を基準としたときに、一様分布であれば平均からの偏差が大きい場合でも確率が変わらないすなわち距離の差が無くしたいので、距離の算出に必要な分散を単調増加する関数（例えば１次関数で定数倍すること）で見かけの分散を大きくするか、さらには影響しないように距離の算出に用いないことで、一様分布の両端においても距離を短く見積もることができる。ラプラス分布であれば、平均から僅かに外れた場合に確率が大きく変化する、すなわち距離を大きく変えたいため、見かけの分散を単調減少する関数で変換する（例えば定数で徐算し小さくする）ことで、平均から僅かに外れた場合でも大きく距離を変化させることができる。ここで定数は１を超える正の実数であり、抽出したい中核点の形状に応じて設定する。場合により定数を確率分布毎に定めてもよい。
【００７９】
また、固有値を変換する別の方法として圧縮コスト算出時に用いるクラスタの分布形態に依らずに共通した関数を用意し適用する方法がある。圧縮コストが最小となる場合、おおよそ分散（又は固有値）の大小によって適用される確率分布が決まる傾向がある。その為、大きい固有値をさらに大きく、小さな固有値をさらに小さくなるように比率が変化する関数を用意すればよい。例えば冪関数ｆ（ｘ）＝ｘrを用いてよい。累乗の係数ｒは１より大きい正の実数に決める。
【００８０】
以上によって、重み行列に中核点の特徴を反映させる変換を行うことができる。
【００８１】
図７に直線のクラスタ（４００点）とそれ以外の外れ値（１００点）が分布している３次元の座標データを２次元で示す。まず上記の方法で中核点と外れ点の分離を行い、圧縮コストを算出する際の中核点に適用すべき確率分布を決める。
【００８２】
以上のロバストな評価手法により、図４に示すように、中心を正確に定め、分散共分散行列により表わされる楕円を中核点の分布とすることができる。図５に示すように、適正な無相関化行列Ｖは、クラスタの中核点の分散方向を示す固有ベクトルにより構成される。ＶTの乗算により座標の変換を行い座標間の相関を取り除くことができる。
【００８３】
（中核点と外れ点との分離）
次に、中核点と外れ点との分離について述べる。上述した各種分散共分散行列を重み行列として用いて距離を定める。次に、中心から定めた距離（境界）までを中核点、それ以外を外れ点として仮に定め、それぞれ境界を変化させた場合において圧縮コストを算出することを繰り返す。その中で、最も圧縮コストが最小となる境界を用いて中核点と外れ点に分離する。
【００８４】
以下に詳細を述べる。まずは、境界を定める適正な無相関化行列を求める。すなわち、候補となる分散共分散行列から、圧縮コストが最適となる１つを選択する。候補となる分散共分散行列には、通常の分散共分散行列に加え、上述したロバストな手法による行列ΣR、従来の手法による行列ΣC、それぞれを確率分布に応じた変換を行った重み行列が含まれる。
【００８５】
更に、ロバストに評価された中心μR→とロバストな分散共分散行列ΣRで定義されたマハラノビス距離を用いて、クラスタの中心に近い点を選択した上で、無相関化行列算出の元となる分散共分散行列として算出し、候補に加える。対象のクラスタから中心μR→に近い点よりクラスタ内のある割合（例えば５０％）に相当する数を選択し、選択した点を元に従来の共分散による候補である行列ΣC,50とロバストなα調整平均による候補である行列ΣR,50を算出する。更に無相関化を行わない場合の無相関化行列の候補として単位行列Ｉがある。これらの行列｛ΣC、ΣR、ΣC,50、ΣR,50、Ｉ｝の中で、最適な（最小の）圧縮コストを与える行列Σ*が選択される。図４の例では、従来の評価では圧縮コストの最小値が１６００であるのに対して、ロバストな評価では圧縮コストの最小値が１４８０となる。
【００８６】
続いて、クラスタ内の外れ点を見つける。ここまでに中核点の中心μR→を求めると共に、候補となる分散共分散行列Σ*（対応する無相関化行列Ｖ*）を選択している。最終的な目的は、クラスタを新たな２つの集合、すなわち中核点の集合（クラスタ）Ｃ中核点と外れ点の集合Ｃ外レ点に分けることである。分散共分散行列Σ*により定められるマハラノビス距離に基づいて両者の境界を定め、２つの集合に分割する。最初に全点を外れ点として（Ｃ外レ点＝Ｃ，Ｃ中核点＝｛｝）、マハラノビス距離に基づいて、中核点の中心μR→に近い距離にある点ｘ→を集合Ｃ外レ点から取り除き、集合Ｃ中核点に取り入れていくことを繰り返す。その際に、点ｘ→の移動前後における圧縮コストを算出する。
【００８７】
各繰り返しにおいて、集合Ｃ外レ点から集合Ｃ中核点に移動した点ｘ→は、選択された無相関化行列Ｖ*により定められる空間に移る。そして、集合の新たな分割（Ｃ中核点∪｛ｘ→｝，Ｃ外レ点−｛ｘ→｝）による圧縮コストは、最小の圧縮コストを導く確率分布を使用して決定する。外れ点に対する圧縮コストは一様分布を用いて符号化する。
【００８８】
このような集合の選び方は、中核点と外れ点を分離する境界を無相関化行列によるマハラノビス距離が一定となる楕円として定め、その内外に分けることで２つの集合を定める。図４では、最小（１４８０）にて中核点が２４個、外れ点が６個となる集合からなる。
【００８９】
図４には、従来の無相関化行列Ｖc及びロバストな無相関化行列ＶRに対応する２つの圧縮コストの推移を示す。初期段階では、全点が外れ点とされ、いずれの圧縮コストも１８００程度となっている。集合Ｃ外レ点から集合Ｃ中核点に点が移動するに従って、圧縮コストは減少する。ロバストな無相関化行列ＶRに対応する圧縮コストでは、中核点が２４個となったときに、最小値である１４８０になる。その後、圧縮コストは再び１８００程度まで増加する。
【００９０】
分離部１０３ｃは、以上説明したように、圧縮コストに基づいて、初期クラスタ生成部１０３ａによって生成された初期クラスタを分離して、集中的な分布をなすデータ（中核点）を含む集合Ｃ中核点と、散発的な分布をなすデータ（外れ点）を含む集合Ｃ外レ点とを生成する。
【００９１】
＜クラスタ結合＞
クラスタの結合は、任意のクラスタリング・アルゴリズム（例えばＫ-ｍｅａｎｓ法）による分割位置及び分割数を変更することである。アルゴリズムに起因するクラスタの欠点により、本来は別のクラスタの一部である点を含んだクラスタが生成されることがある。そこで、従来のクラスタリング手法に起因する間違った分割をクラスタ結合により修正する手法について説明する。
【００９２】
例えばＫ-ｍｅａｎｓ法では、本来は１つであるはずのクラスタを誤って複数に分離することがある。提案する方法のアルゴリズムでは、クラスタ結合を行うことにより誤った分離を正すものである。
【００９３】
ここでも、２つのクラスタを結合する際に圧縮コストを利用し、一対のクラスタを結合させることにより圧縮コストが減少するかどうかを判定する。すなわち、一対のクラスタ（Ｃi，Ｃj）について、下式（１１）に示すようにクラスタ結合による圧縮コストの低減量ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）を定義する。
【００９４】
【数８】
0005262582.tif 000010
【００９５】
クラスタ結合による圧縮コストの低減量ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）＞０である場合、一対のクラスタ（Ｃi，Ｃj）に結合の可能性があるものとする。
【００９６】
この手順は欲張り法に従い、圧縮コストの低減量がある限り繰り返し行われる。各繰り返しにおいて、ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）が最大となる２つのクラスタを結合し、圧縮コストが最小コストとなるクラスタリングを探索する。更には、局所的な最小により計算が行き詰るのを避けるために、ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）の減少がなくなっても計算をすぐには止めない。すなわち、ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）≦０となってもアルゴリズムを止めず、その代わりに、アルゴリズムを別のｔの繰り返しにおいて続け、ｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）が負になって、つまりＣi及びＣjの結合により圧縮コストが増加する場合でも、最大のｒｅｄｕｃｅｃｏｓｔ（Ｃi，Ｃj）でクラスタ（Ｃi，Ｃj）の結合を継続する。
【００９７】
結合部１０３ｄは、以上説明したように、圧縮コストに基づいて、分離部１０３ｃによって生成された集中的な分布をなすデータを含むクラスタＣ中核点同士を結合する。
【００９８】
また、初期クラスタ数が適切な初期クラスタ数に比べ多い場合において計算時間を減少させるための本願独自のアルゴリズムとして、上述した計算によるクラスタ結合の前段階で、結合するクラスタの候補をドロネー図に基づいて隣接するクラスタの組を決めることを行う。本発明で取り扱う薄板の表面欠陥は２次元上に分布しているので、ドロネー図を利用することが可能である。具体的には、クラスタの中心を母点として用いて、最初に母点を４点選び２つの三角形を作る、それぞれの三角形がドロネー三角分割であることを外接円に他の三角形の頂点が入っていないことで確認し、そうでなければ三角形の分割方法を変える。さらに１点加え、加えた１点を含む三角形に着目し三角形に分割しドロネー三角分割であること確認する。そうでなれば三角形の分割方法を変える。さらに逐次母点を追加し、追加すべき母点がなくなり、ドロネー三角分割となるまで繰り返すことでドロネー図を生成する。そのドロネー図に表われるドロネー辺によりつながる母点に相当するクラスタ同士を結合の候補とする。このようにドロネー図を利用して候補を決めることで、計算量を大幅に軽減させることができる。
【００９９】
また、初期クラスタ数が適切な初期クラスタ数に比べ少ない場合において本願発明の独自のアルゴリズムとして、外れ点の分離やクラスタ結合の段階でクラスタから分離した外れ点を別のクラスタに組み入れるようにする。そのために、外れ点として分離されたものを集め仮想的な新たなクラスタとして扱い、中核点に組み入れ可能な点があるかを、仮想的なクラスタと中核点からなるクラスタの圧縮コストの低減量ｒｅｄｕｃｅｃｏｓｔにて判断し、これが大きくなれば外れ点の一部を別クラスタの中核点として再度取り入れる。また、仮想的なクラスタから中核点からなるクラスタが生成できれば新たなクラスタとすることができる。
【０１００】
以上に述べたように、自動疵検査装置で採取された疵データの発生位置に関する座標データに基づいて、疵同士を自動的にグループ化することができ、例えば疵グループの重心位置、空間サイズ、疵個数密度といった疵の分布に係わる特徴量抽出を高速かつ大量に行うことが可能になる。この場合に、指標に基づいて最適となるように計算処理が行われるので、人間による分析処理に比べて、再現性の高い客観的かつ定量的な特徴量を抽出することが可能である。したがって、例えば疵の発生位置と操業条件の相関解析等、大量の疵の分布データを用いた解析を迅速に行うことができる。
【０１０１】
しかも、上述したように初期クラスタから散発的な分布をなすデータ（外れ点）を分離して、集中的な分布をなすデータを含むクラスタを生成し、クラスタ同士を結合する手法により、外れ点を除いた自然な形で疵同士をグループ化することができる。これにより、疵の分布形態の解析精度を高めるとともに、疵の分布に係わる特徴量抽出を高速かつ大量に、そして正確に行うことが可能になる。
【０１０２】
図６には薄板コイルに発生した疵の分布の一例を示す図であり、横軸が薄板コイルの長手方向位置、縦軸が幅方向位置を示す。図６（ａ）が特許文献１に開示された手法による結果であり、□を中心とする３つの楕円状の分布が抽出されている。それに対して、図６（ｂ）が本発明を適用した手法による結果であり、集中的な分布をなす中核点・と、散発的な分布をなす外れ点×とに分離され、直線状に発生する疵グループを的確に抽出することができている。これに基づいて、疵の発生の原因となる工程で対策を行い、大量の品質不良品を出すことを防ぐことができた。
【０１０３】
（本発明の他の実施形態）
上述した実施形態の機能を実現するべく各種のデバイスを動作させるように、該各種デバイスと接続された装置あるいはシステム内のコンピュータに対し、前記実施形態の機能を実現するためのソフトウェアのプログラムコードを供給し、そのシステム或いは装置のコンピュータ（ＣＰＵ又はＭＰＵ）に格納されたプログラムに従って前記各種デバイスを動作させることによって実施したものも、本発明の範疇に含まれる。
【０１０４】
また、この場合、上記ソフトウェアのプログラムコード自体が上述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えば、かかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【０１０５】
また、コンピュータが供給されたプログラムコードを実行することにより、上述の実施形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等と共同して上述の実施形態の機能が実現される場合にもかかるプログラムコードは本発明の実施形態に含まれることは言うまでもない。
【産業上の利用可能性】
【０１０６】
本技術は、主として、鉄鋼製品の薄板製品の製造における表面欠陥起因の不良品発生原因を解析することに利用される。
【図面の簡単な説明】
【０１０７】
【図１】本実施の形態の薄板の表面欠陥の分布形態解析装置の構成の一例を示す図である。
【図２】クラスタリングの例を示す図である。
【図３】圧縮コストの例を説明するための図である。
【図４】従来の手法とロバストな手法とを比較した結果を示す図であり、（ａ）がデータとその共分散を表わす楕円との関係を示す図、（ｂ）が中核点の数と圧縮コストとの関係を示す特性図である。
【図５】無相関化行列を説明するための図である。
【図６】薄板コイルに発生した疵の分布の一例を示す図である。
【図７】直線のクラスタ（４００点）とそれ以外の外れ値（１００点）が分布している３次元の座標データを表す図である。
【符号の説明】
【０１０８】
１０１    疵データ入力部
１０２    疵データ蓄積部
１０３    演算部
１０３ａ  初期クラスタ生成部
１０３ｂ  圧縮コスト算出部
１０３ｃ  分離部
１０３ｄ  結合部
１０４    解析結果表示部
【図１】
0005262582.tif 000011
【図２】
0005262582.tif 000012
【図３】
0005262582.tif 000013
【図４】
0005262582.tif 000014
【図５】
0005262582.tif 000015
【図６】
0005262582.tif 000016
【図７】
0005262582.tif 000017