(57)【要約】プロファイル測定機器によって収集されたデータからのリアルタイム・データ信号をマッチングするのに使用するための、改良されたプロファイル測定収集・分析システムであって、このシステムは、半導体チップ・ウェハーのプロファイルを表す、メモリー内に記憶されたライブラリ・データのクラスタリング分析を行うソフトウェアを採用する。入来リアルタイム・データ信号と、クラスタリングされたプロファイル・ライブラリ・データとの間でリアルタイムにより良好なマッチングを行い、クラスターから代表クラスター・データポイントを抽出する。クラスターの代表が一次メモリー（例えばＲＡＭ）に記憶されるのに対し、クラスターを形成するデータは二次メモリー（例えばハード・ドライブ）に記憶される。次いでリアルタイム・データ信号は先ず代表クラスター・データポイントと比較され、特定の代表クラスター・データポイントとのマッチングが行われると、代表クラスター・データポイントと関連するクラスターが、二次メモリーから一次メモリー内にローディングされる。次に更なるサーチが入来リアルタイム・データ信号により行われ、これによりこのデータとの最近似マッチがクラスター内に見出される。こうして、ライブラリ・データ全体が順次サーチされずにすみ、ライブラリ全体が一次メモリーに存在する必要もなく、これにより迅速なサーチが行われる。このことは時間および一次メモリー双方を節約する。ポイントがクラスターの境界に位置している特定の事例をさらに改良する技術が開示される。好ましい実施例では、クラスターのパーティショニング法は、Ｔ．ゴンザレスのアルゴリズムに基づいている。
2004528618.tif 000002
【特許請求の範囲】
【請求項１】
半導体チップ加工のための改良されたソフトウェア・プログラムであって、該プログラムが：
一次メモリーと二次メモリーとから成るコンピュータ・メモリーと；
機器から収集されたリアルタイム・データをリアルタイム・データ信号として表すためのソフトウェア・モジュールと；
多次元空間内のポイントのライブラリ・データ集合Ｓをクラスター集合にクラスタリングするためのソフトウェア・モジュールと；
前記リアルタイム・データ信号と、前記クラスター内の前記ポイントとの間で最近似マッチを見出すために、前記リアルタイム・データ信号を前記クラスター集合と比較するための比較ソフトウェア・モジュールと
から成ることを特徴とする、半導体チップ加工のための改良されたソフトウェア・プログラム。
【請求項２】
クラスタリングのための前記ソフトウェア・モジュールが、Ｔ．ゴンザレスのミニマックス・ヒューリスティック・クラスタリング・アルゴリズムに従って、前記クラスタリングを行う、請求項１に記載の方法。
【請求項３】
プロファイル測定のためのコンピュータ装置であって、該装置が：
プロセッサと、データを出入力し、かつ半導体集積回路を測定するのに使用される少なくとも１つの機器からデータを収集するための、前記プロセッサによって制御されたＩ／Ｏと、前記プロセッサと動作接続されかつ協働するメモリーと；
前記プロセッサによって実行されるソフトウェア・プログラムを形成する、前記メモリー内に記憶されたソフトウェア・モジュールと、
から成っており、該ソフトウェア・モジュールが、
前記Ｉ／Ｏ機器からリアルタイム・データ信号を収集し、かつ該リアルタイム・データ信号を所定のフォーマットで表すためのデータ収集ソフトウェア・モジュールと；
データ集合を、前記リアルタイム・データ信号と同じ所定のフォーマットで表されたデータから成る少なくとも２つのクラスター集合にクラスタリングするためのクラスタリング・ソフトウェア・モジュールと；
最近似マッチを見出すために、前記クラスター集合内の前記データを前記リアルタイム・データ信号と比較するための比較ソフトウェア・モジュールと
から成ることを特徴とする、プロファイル測定のためのコンピュータ装置。
【請求項４】
プロファイル測定で収集されたデータを、ライブラリ・データとリアルタイムにマッチングさせるためのコンピュータ法であって、該コンピュータ法が以下のステップ、つまり：
プロファイル測定機器からデータをリアルタイムで収集するステップと；
ライブラリ内のデータを、クラスタ代表を有する複数のクラスタにクラスタリングするステップと；
前記クラスター代表を一次メモリーにローディングするステップと；
最近似マッチを見出すために、前記リアルタイム・データを前記クラスター代表と比較するステップと
から成ることを特徴とする、コンピュータ法。
【発明の詳細な説明】
【０００１】
発明の分野
本発明は、積層、パターン化、ドーピングおよび熱処理という基本的なウェハー製造作業中のウェハー層の非破壊的測定分野におけるプロファイル測定法に関する。
【０００２】
発明の背景
ＩＣデバイスの物理的および光学的な特性と、例えばエリプソメータやスキャタロメータのような機器によってＩＣ上に照射された光からの情報との間には、ある関係が存在する。ウェハーの物理的および光学的な特性は、チップ製造業者によって充分に追及される。なぜならば、マイクロチップ加工機械は、好ましくはリアルタイムで動作する非破壊的技術を介してそのパラメータが知られるとすぐに、調和し最適化することができるからである。
【０００３】
残念ながら、ウェハー加工中に生産されるデータの量は、リアルタイムでプロセスを制御するためにチップ製造業者が容易に使用することができないほど夥しい。
【０００４】
本発明は、クラスター分析、つまり項目とこれらの項目に割り当てられた群との間の関連度を生成する多変量分析技術を利用して、生情報をマイクロチップ加工情報に迅速に変えることに取り組む。
【０００５】
発明の概要
本発明は、クラスタ分析が、プロファイル測定機器、例えばエリプソメータやスキャタロメータから収集された入来リアルタイム・データ信号を、コンピュータ・メモリーに記憶されたデータ・ライブラリとマッチングさせることを可能にするソフトウェアを備えたプロファイル測定システムを提供することにある。ライブラリ・データは先ず、クラスター代表データを有するクラスターによって表される。クラスター代表データは一次メモリー内に記憶されているのに対して、クラスターは二次メモリーに記憶されている。入来リアルタイム・データは初めは、一次メモリー内のクラスタ代表とマッチングさせられることにより、最近似マッチングするクラスタ代表を見出す。マッチが見出された場合、最近似マッチを有するクラスター代表と関連するクラスターが、二次メモリーから一次メモリーにローディングされる。このような技術は、先行技術に見られる過剰なディスク・スラッシングを回避する。本発明はさらに、チップ加工において一般的に見て、測定機器からの大型データがしばしば数学的に連続的であるという観察を利用する。
【０００６】
好ましい実施態様では、好ましいクラスタリング・パーティショニング法として、ティー．ゴンザレス（Ｔ．Ｇｏｎｚａｌｅｚ）のヒューリスティックなミニマックス・アルゴリズムが使用される、
さらに、種々の改良、例えばボーダライン・マッチの特定事例の原因となるような改良が導入される。
【０００７】
要約すると、本発明の利点は、好ましい一実施態様において多様である。第一に、入来する信号毎に行わなければならない比較数は、４００Ｋの比較数から１０Ｋ未満の比較数に、著しく減少する。従って、最小でも４０倍だけ速度の改良が得られる。このことは、最近似マッチ・クラスター代表のクラスターと関連する信号だけを選択的に比較することによって達成することができる。第二に、しばしば生じる事例であるが、ライブラリ全体をローディングするのに充分なＲＡＭがない場合に、本発明は、プロセス制御システムの重要な特徴を利用する。この特徴とはすなわち、入来信号の可変性が或る期間中、同様の条件下において小さいという特徴である。このような特徴は、或る期間中、全ての入来信号に対する最良マッチを、クラスタの単なる下位集合内に見出すことができることを示唆している。従って、ＲＡＭ内に既に存在するデータ中に、入来信号がその最良マッチを見出す可能性が高い。このことは、あらゆる所与の期間中に行われるスワッピング数を著しく減少させる。さらに、スワッピングに必要となるデータ量はライブラリのデータ・サイズ全体のうち僅かな部分なので、ハード・ドライブからＲＡＭにスワッピングすることにより経過する時間は、取るに足らないものであり、従って、入来信号をライブラリ信号にマッチングさせることにより経過する時間が影響されることもない。
【０００８】
好ましい実施例の詳細な説明
図１は、本発明を実施するプロファイル測定システムを示すブロック・ダイヤグラムである。本発明のソフトウェア・プログラムを走行させるプロセッサ１−２０を有するコンピュータ・システム１−１０は、一次メモリー（すなわちＲＡＭ）１−３０、二次メモリー（すなわちハード・ドライブ）１−４０、および複数のＩ／Ｏデバイス１−４５、例えばキーボード、マウスおよびモニター、ならびに、Ｉ／Ｏデバイス１−５０と協働する。このＩ／Ｏデバイス１−５０は、プロファイル測定に使用される１つまたは複数の機器１−５５、例えばエリプソメータ、スキャタロメータ、原子間力顕微鏡（ＡＦＭ）、走査型電子顕微鏡（ＳＥＭ）、透過型電子顕微鏡（ＴＥＭ）、分光計（ＳＥＭ−ＥＤＸ）などに接続されている。このような機器１−５５は、好ましくはリアルタイム測定機器、例えば、入来データ、例えば散乱または反射させられた波長をリアルタイムで収集するエリプソメータやスキャタロメータである。このデータはライブラリ・データと関連付けされることにより、ダイ加工における当該構成要件、例えば粒子サイズ、プロファイル輪郭、臨界寸法（ＣＤ）、膜層厚などが確かめられる。
【０００９】
本発明のコンピュータ・システムは好ましくは、非破壊的プロファイル測定機器１−５５からの入来リアルタイム・データ信号を収集し、一次メモリー（例えばＲＡＭ）内に入来リアルタイム・データ信号を、多次元ベクトルのようなフォーマットで記憶する。これにより、同一フォーマットのライブラリ・データとの比較が可能になる。次いで、入来リアルタイム・データとライブラリ・データとの間でマッチを見出すために、図１においてＲＡＭのデータ１−６０で示したメモリー内に記憶されたライブラリからのデータに対して、前記入来リアルタイム信号データが比較される。プロファイル測定機器によって収集された入来リアルタイム・データ信号と、ＲＡＭに記憶されたライブラリ・データとの間でマッチングを行うとき、本発明のオペレータは、ライブラリ・データと関連する特性が、収集された入来リアルタイム信号データとも関連することを知る。このような特徴は、ウェハー・プロファイルの横断面積を算出するのに用いられる。ウェハー・プロファイルの横断面積は、ウェハー加工において極めて重要である。プロファイル測定では、ＩＣ機器の物理的特性と光学的特性との間に関連性が存在することが判っている（厚さ、係数ｎおよびｋ、臨界寸法（ＣＤ）、およびパターン化された積層ウェハーの横断面プロファイル、および、エリプソメータのような機器によってＩＣデバイス上に照射された反射光の大きさ（ｔａｎψ）および位相（コサインΔ））。
【００１０】
しかし先行技術においては、大量のプロファイル測定データの記憶および比較に関連する潜在的な問題が生じる。本発明はこの問題に対処する。１つの問題は、最良のマッチを見出すために、機器から収集されたデータポイントと、ライブラリ内のデータとの間で行われるべき比較の純粋な数である。例えば、最良の適合を見出すために入来データにマッチングさせられなければならない４００，０００個のライブラリ・プロファイルから成るライブラリ・データを有することは、尋常ではない。このようなライブラリ・データをＲＡＭ内にローディングするために、コンピュータ内に充分なＲＡＭを持とうとするには、多くの費用がかかる。また、このように多量のＲＡＭを有するコンピュータ・システムを構成するのが不可能なシステムもある。典型的なウェハーテスト・評価機器、例えばエリプソメータにより収集された入来リアルタイム・データ信号は、ブロードバンド信号であり、この信号は１００個を超える成分、例えば波長から構成することができる。収集された入来リアルタイム・データと、ライブラリ・データとの間により完全なマッチングを保証するには、データの充分に大きなライブラリの記憶が必要となり、そのサイズは目下のところ最大１ＧＢであるが、しかし理論上は無制限である。将来はさらに大量のデータが収集され、記憶された信号データのいくつかのライブラリが採用されることが想定される。このデータをマッチングさせるために先行技術を使用する場合、このことは更なる潜在的ボトルネックを形成する。
【００１１】
最後に、ライブラリ・データを記憶するのにＲＡＭが採用される別の理由は、マイクロチップ加工装置がリアルタイムで最良に調節される以上、機器から収集された入来信号がライブラリ・データにリアルタイムでマッチングさせられなければならないことである。ライブラリ・データを一次メモリー（例えばＲＡＭ）ではなく二次メモリー（例えばハード・ドライブ）に記憶させることになると、または大きなライブラリを有することになると、行わなければならないリアルタイム計算が遅くなる。それというのもライブラリ・データが二次メモリーから一次メモリーに移動されなければならないからである。
【００１２】
ある時点で、プロファイル測定に関連するライブラリ・データ全てを記憶するのに充分に大きな量のＲＡＭを採用するのが、経済的に実行不可能になる。従って、ライブラリ・データはハード・ドライブに記憶されなければならず、コンピュータ・プログラムが要求したときにはいつでも、ＲＡＭの内外にＲＡＭがスワッピングされる。このような種類の「バーチャル・メモリー」は速度が遅いという欠点を有している。速度が遅いのは、Ｉ／Ｏ転送プロセスとのプロセッサ通信が、典型的にはＲＡＭとの通信よりも数オーダ低い大きさだからである。従って、収集された入来リアルタイム・データと、記憶されたライブラリ・データとの間にプログラムが最良マッチを見出そうとすると、ＲＡＭとハード・ドライブとの間に過剰なディスク・スラッシングが発生し、ボトルネックを形成する。
【００１３】
このような問題に対処するために、本発明はとりわけクラスタリング技術を採用する。この技術は、ライブラリ・データからクラスターを生成し、先ずクラスターの代表をＲＡＭ内にローディングし、これらのクラスター代表と入来リアルタイム・データとの最初のマッチングを行い、マッチングしたときのみ、最近似マッチングするクラスター代表に関連するクラスターを、ハード・ドライブからＲＡＭにローディングすることにより、サーチを完成させ、これにより、潜在的なディスク・スラッシングを低減する。このように本発明は、リアルタイム・データとライブラリ・データとの間で行わなければならない比較数およびマッチング数を最小化するために、クラスタリングを採用しようとする一方、同時に、リアルタイム・データとライブラリ・データとの間の最良のマッチングを保証する。
【００１４】
クラスタリングの背後にある理論を例示するために、図２（ａ）は、マイクロチップ加工プロセスから、本発明のシステムによって収集された到来リアルタイム・データ信号がどのように記憶されるかを示す。光学測定機器、例えばエリプソメータからの入来リアルタイム・データ信号から得られたデータは、ベクトル２−Ａ−１０で示したように、ベクトルとして表される（ベクトルは概ね、数値をｎタプルのような成分にパラメータ化表現したものと考えることができる）。それぞれのベクトルは複数の成分、この例では３つの成分、つまりＸ，Ｙ，Ｚ成分を有している。単に例示の目的で用いた図２（ａ）では、３つの成分（Ｘ，ＹおよびＺ）が示されている。実際には、入来リアルタイム・プロファイル測定信号（原理的にはリアルタイムに記録されるが、後の分析のために記憶された信号であってもよい）は、３次よりも高次のベクトル、すなわちｎ次元ベクトルによって表されるか、または同等に長さｎの数列（例えばｎタプルの数値）によって表される。この場合ｎは正の整数であり、通常は数列｛ｍ１，ｍ２，…，ｍｎ｝または同様の表記によって表される。ここでは、プロファイル測定機器から収集された到来リアルタイム・データ信号を記述するベクトルも、記憶されているライブラリ・データを記述するためのベクトルも、最大１０６個の成分（例えば｛Ｘ０，Ｘ１，…Ｘｎ｝からパラメータ化または構成されたベクトルである。このように、ライブラリ・データセットも入来リアルタイム・データ信号も、双方とも同一フォーマットで表される。ここでは、多次元ベクトルの各成分（例えばＸｎ）は、コンピュータ・メモリー内で二倍精度の数値によって表される。最大４００，０００個の信号がメモリー内に記憶され、プロファイル測定機器によって収集され、この場合、各信号は最大１０６個の成分（波長のような信号であってもよい）を有している。これらの成分は、ここでは４２，０００，０００を超える二倍精度バイトのメモリーを必要とする。
【００１５】
入来リアルタイム・データ信号に関して、プロファイル測定機器から収集された入来リアルタイム・データ信号と、コンピュータ・メモリーに記憶されたライブラリ信号との間には、しばしば通信が生じる。コンピュータは入来リアルタイム信号ベクトルを、メモリーに記憶されたライブラリ・データ・ベクトルとマッチングさせることにより、最良の適合を見出さなければならない。典型的には、最良の適合は統計学的な技術、例えばユークリッド距離または「最小二乗」適合によって見出される。入来リアルタイム・データ信号ベクトルを最良にマッチングさせるライブラリ・データ・ベクトルのマッチング域が見出されてもよい。
【００１６】
図２（ｂ）に注目すると、データポイントの二次元的な収集が示されている。これらのデータポイントは、Ｘ，Ｙ平面のような１平面図上への図２（ａ）の三次元ベクトルの投影として考えることができる。ポイント２ｂ−１０、２ｂ−２０、２ｂ−３０、２ｂ−４０、２ｂ−５０および２ｂ−６０のようなポイントが収集され、それぞれ円２ｂ−１００、２ｂ−１１０、２ｂ−１２０、２ｂ−１３０、２ｂ−１４０および２ｂ−１５０内のデータポイント全てがこれらのポイントによって形成される。これらのポイントを集合的にＮ個の項目のデータセットと呼ぶことができる。検査により、これらのポイントは群（例えば円内のポイント）を成してかたまるように見えることが判る。すなわちこれが「クラスタリング」である。本発明では、プロファイル測定で使用された１０６個の成分ｎ次元ベクトルにより、このようなクラスタリングがより高次元の空間内で発生するが、これを図示するのは容易ではない。
【００１７】
このクラスタリング現象を物理的に合理化する１つの方法は、加工中にウェハーから収集されたデータが一般的に云って、数学的に連続的であることに注目することである。このことは、時間「ｔ」内の時点において収集されたデータが、これより以前の或る小さな時間間隔「ｔ−Δｔ」において収集されたデータに類似しており、また、これより以降の或る時間間隔「ｔ＋Δｔ」において収集されたデータにも類似しているという点において云える。クラスタリングが生じ得る１つの理由は、ウェハーを形成する化学的かつ機械的なプロセスが連続的にウェハーを変化させる傾向を有することにあると云える。
【００１８】
クラスタリングの物理的根拠とは無関係に、クラスター群、例えば図２（ｂ）の２ｂ−１００、２ｂ−１１０、２ｂ−１２０、２ｂ−１３０、２ｂ−１４０および２ｂ−１５０を識別すると、各クラスター群から代表クラスター・データ中心ポイントを選択することができる。図２（ｂ）において、代表クラスター・データ中心ポイントは、群の幾何学的平均であってよく、または概念的には、図２（ｂ）に示した円の中心点、例えば中心データポイント２ｂ−１０、２ｂ−２０、２ｂ−３０、２ｂ−４０、２ｂ−５０および２ｂ−６０であってよい。各クラスター群からのこれらの代表クラスター・データポイントのそれぞれは、ＲＡＭメモリーに記憶され、次いで、それぞれの入来リアルタイム・データ信号が受信されると、データ信号は各クラスター群からのそれぞれのクラスター・データポイントと比較される。入来リアルタイム・データ信号と、ＲＡＭ内の各クラスタ群からの代表クラスター・データポイントとの間で、最近似マッチが見出される。最近似マッチが見出されると、特定の代表クラスター・データポイント（すなわちクラスタ中心）と関連する適切なクラスター（すなわち代表クラスター・データポイントと関連する特定データセット）が、ハード・ドライブからＲＡＭ内にローディングされ、マッチングのための第２のサーチが行われ、これにより、特定の入来リアルタイム・データ信号ベクトルに最も近似した、このクラスタ内のライブラリ・データが見出される。
【００１９】
先行技術を上回る本発明の利点は、全てのライブラリ・ポイントを考えるために、全てのライブラリ・ポイント（または、より高次元でこれらのポイントを表すベクトル；一般的には空間における「ポイント」はベクトルまたはｎタプルによって表すことができる）をローディングする必要はなく、または、ＲＡＭ内外にデータをスワッピングするより低速のバーチャル・メモリーに頼る必要はなく、先ず代表クラスター・データポイントを入来信号データポイントと比較し、次いでハード・ドライブからＲＡＭ内に、入来データポイントに最も近似する代表クラスター・データポイントに関連するクラスター群構成部分（または、本明細書中にさらに説明するような「ボーダライン・マッチ」のように、２つ以上の群を考えなければならない場合には、クラスター群）をスワッピングすればよいことである。従って本発明の技術は最良のマッチングのためのサーチをスピードアップし、ＲＡＭを節約する。
【００２０】
ただし上記にかかわらず、本発明は、全体的にＲＡＭから構成されたコンピュータ・システムによっても功を奏することに留意すべきである。本発明はこの場合、一次および二次メモリー相互のデータのスワッピングを採用する必要はない。
【００２１】
図２（ｂ）の簡略化された二次元空間を使用して例示するために、入来リアルタイム・データポイントつまり信号Ｓが、クラスター群２ｂ−１００の構成部分であるデータポイント２ｂ−１２と同一であると想定する。クラスター群２ｂ−１００は代表クラスター・データポイント中心２ｂ−１０を有している。信号Ｓは、本発明のソフトウェア・プログラムによって、クラスター２ｂ−１００、２ｂ−１１０、２ｂ−１２０、２ｂ−１３０、２ｂ−１４０および２ｂ−１５０の、ＲＡＭ内に記憶された代表クラスター・オブジェクト・データポイント中心２ｂ−１０、２ｂ−２０、２ｂ−３０、２ｂ−４０、２ｂ−５０および２ｂ−６０のそれぞれと比較される。クラスター２ｂ−１００、２ｂ−１１０、２ｂ−１２０、２ｂ−１３０、２ｂ−１４０および２ｂ−１５０の関連ライブラリ・データ構成部分は、ハード・ドライブ内に記憶されている。この簡略化された例の場合、信号Ｓとの最近似マッチは、クラスター群２ｂ−１００の代表クラスター・データポイント２ｂ−１０となる。この代表クラスター・データポイント２ｂ−１０は、信号Ｓとこのように唯６つの代表クラスター・データポイントを比較した後で、本発明のプログラムにより見出されるようになる。これが突き止められると、クラスター２ｂ−１００のデータポイント２ｂ−１０と関連するライブラリ・データ構成部分全てが、ハード・ドライブからＲＡＭ内にローディングされることになる。概念的には、クラスター２ｂ−１００のライブラリ・データ構成部分は、円２ｂ−１００内部のポイントである。検査によって明らかなように、このようなデータ収集群は、図２（ｂ）に示したポイント全ての単なる下位集合である。サーチは次いで、信号Ｓとクラスター２ｂ−１００のデータとの間の最近似マッチングのために続けられる。最近似マッチはこの例ではポイント２ｂ−１２である。このマッチが見出されると、サーチが終了する。従って、大規模なバーチャル・メモリーを利用せずにすみ、しかも記憶されたライブラリにおけるデータポイント全てのサーチに時間を費やす必要もない。
【００２２】
図３に目を転じると、本発明のトップレベル・フローチャートが示されている。本発明のソフトウェア・ツールは、いずれのコンピュータ言語で書かれていてもよく、汎用コンピュータ・システムによって走行させられてよい。このコンピュータ・システムはプロセッサと、このプロセッサと協働する一次および二次メモリーと、Ｉ／Ｏ手段、例えばモニター、マウス、キーボードと、プロファイル測定に使用される種類のデータ収集機器、または専門的なハードウェアまたはファームウェアとを有している。プロファイルに関するライブラリ・データのサイズが極めて大きいことがあり得るので、コンピュータは、充分な一次および二次メモリー・ストレージを有していることが好ましい。
【００２３】
ソフトウェアを構築して実行するのに使用される言語（Ｃ，Ｃ＋＋、パールまたはジャバなどのあらゆる言語であってよい）に応じて、ソフトウェアはあらゆる数のクラス、機能、オブジェクト、変数、テンプレート、コード行、コードおよび構成の部分（集合的または全体的、「プロセス・ステップ」、「ステップ」、「ブロック」、「ソフトウェア・プロセス」、「機能モジュール」または「ソフトウェア・モジュール」）を有していてよく、これにより、本明細書中に記載し教示するような連続的な段階で、本発明が実行される。さらにソフトウェアはスタンドアロン型ソフトウェア・アプリケーションであるか、または、別のソフトウェア・アプリケーションの内部に採用されるか、またはこのアプリケーションによって呼び出されてよい。ソフトウェア・プロセスまたはソフトウェア・モジュールは、アプリケーション内のコードの一部が、例えばオブジェクト指向プログラミング（例えばオーバロードされたプロセス）として複数の機能を発揮するように、構成されてよい。コードの複数の部分が複数の機能を発揮してもよく、これらの部分が機能的にはなおもコードの単一部分と同じであるという点で、逆もまた真である。本発明のプロセス・ステップのあらゆる段階で、中間の値、変数およびデータが、プログラムによって後で利用するために記憶されていてよい。
【００２４】
図３に目を転じると、ソフトウェア・モジュール・プロセスのステップ３−１０が示されている。このステップでは、本発明のプログラムが、プロファイル・データのライブラリを構成する全てのデータポイントの集合から、好ましくは非階層的パーティショニング技術を介して、２つ以上のデータ・クラスターを形成し、クラスター毎のライブラリ・データセットから代表クラスター・プロファイルを算出する。このことは、図４との関連とにおいて本明細書中にさらに説明したように、Ｔ．ゴンザレスの方法で行われる。このＴ．ゴンザレスの方法は、Ｔ．ゴンザレスによる刊行物論文「最大クラスター間距離を最小化するためのクラスタリング（Ｃｌｕｓｔｅｒｉｎｇ ｔｏ Ｍｉｎｉｍｉｚｅ ｔｈｅ Ｍａｘｉｍｕｍ Ｉｎｔｅｒｃｌｕｓｔｅｒ Ｄｉｓｔａｎｃｅ）」， Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ 第３８巻第２９３〜３０６頁（１９８５）に言及された通りである。この論文を参考のため本明細書中に引用する。
【００２５】
コンピュータは次いで、クラスター代表をＲＡＭ内にローディングする。これに対してクラスター（すなわちクラスター・ライブラリ群）自体はハード・ドライブに記憶される。始めはクラスター代表の計算が時間集中的に行われる一方、長い目で見た場合、プログラム全体が、リアルタイム・データ信号とのプロファイル・マッチングのより迅速な実行を可能にし、一次メモリーの使用を節約する。クラスターおよびクラスター代表に関する計算を実施するのに必要な時間が長いので、プロファイル測定機器からのリアルタイム・データの収集開始前に、この計算が実施される。
【００２６】
次に、ソフトウェア・モジュール・プロセス・ステップ３−２０において、本発明のプログラムは、プログラム測定機器、例えばエリプソメータから収集されたデータに関連する入来リアルタイム信号を集め、このデータを表す多成分ベクトルを形成する。このようなリアルタイムのデータについての解釈は半導体加工において重要であり、実際にはこれらの信号は「リアルタイム」であるが、理論上これらの信号は以前の時間に収集されて記憶されてもよい。従って「リアルタイム・データ」という言い回しは、このような時間シフトされたバッチデータを含むことができ、概ね、プロファイル測定、またはより一般的にはウェハー加工に使用される機器によって収集された現時点でのデータを意味する。典型的にはこれらのリアルタイム・データは、複数の波長を伴う光学的なブロードバンド信号であり、しかもこの場合、リアルタイム・データはそれぞれ、１００を超える成分のベクトルまたはｎタプルによって表される。
【００２７】
ソフトウェア・モジュール・プロセス・ステップ３−３０では、プログラムはループに入る。このループで、リアルタイム信号データは、ステップ３−２０からの代表クラスター・ライブラリ・データと比較されることにより、最近似マッチが見出される。
【００２８】
ソフトウェア・モジュール決定ブロック３−４０において、プログラムは、リアルタイム信号が、本明細書中でさらに説明するように、代表クラスター・プロファイル・データ中心ポイントと潜在的に「ボーダライン・マッチ」しているかどうかを見るためにチェックする。「ボーダライン・マッチ」は概ね、クラスター代表によって表されたクラスターの境界、または、より高次の球体の場合には、球体の半径Ｒによって画定された境界帯域に近接している。この場合Ｒは代表クラスター・プロファイル・データ中心ポイントからのクラスター半径のユークリッド距離である。図５（ｄ）の例との関連においてさらに説明するように、「ボーダライン・マッチ」の特定事例では、リアルタイム・データ信号との最近似マッチは、事実上、隣接するクラスター内に位置する場合がある。この隣接クラスターは、距離２＊（Ｒ＋Ｄ）内に位置している。この場合Ｄは、信号と最近似代表マッチとの間の距離である。さらにこの隣接クラスターも、ソフトウェア・モジュール・ボックス・ステップ３−５０によって示したように、クラスター代表と関連するクラスターと一緒にＲＡＭ内にローディングされなければならない。リアルタイム・データ信号がクラスターの境界にどのように近接しているかを、決定ボックス３−４０に対応して「Ｙｅｓ」（真）をトリガする前に明らかにするために、リアルタイム・データ信号と、リアルタイム・データ信号と最近似することが見出されたクラスター代表との間のユークリッド距離（本明細書中にさらに明らかにする）が、ＲおよびＲ−εの境界帯域（Ｒ＝クラスター半径、ε＝イプシロンつまり小さな許容誤差）の間にある場合にはいつでも、決定ボックスが「Ｙｅｓ」（真）としてトリガされるように、任意に選択することができる。従ってこのような「ボーダライン・マッチ」の場合、ステップ３−５０によって示すように、リアルタイム信号帯域の２＊Ｒ内に位置するクラスターが、ＲＡＭ内にローディングされ、プログラムは続いてソフトウェア・モジュール・ステップ３−７０に進む。
【００２９】
あるいは、決定ボックス３−４０内で「Ｎｏ」（偽）がトリガされた場合、プログラムはソフトウェア・モジュール・ステップ３−６０に制御を渡す。このステップでは、最近似代表クラスター・データ中心ポイントに関連するクラスタ・ライブラリ群がハード・ドライブからＲＡＭ内にローディングされる。
【００３０】
次に、ソフトウェア・モジュール・プロセス・ステップ３−７０において、プログラムは今度は、リアルタイム信号と、ステップ３−５０またはステップ３−６０において算出された、クラスター代表と関連するプロファイル・ライブラリ・データのクラスターとの間で、第２の比較を行う。最近似マッチ（単一の最近似マッチよりも最近似マッチ域を見出すのに有利な場合には、複数の最近似マッチ）が見出され、制御がソフトウェア・モジュール決定ブロック３−８０に渡される。このブロックにおいて、分析すべき信号がもはやない場合には、プログラムはステップ３−９０で終了され、さもなければ、プログラムはステップ３−３０に戻って繰り返す。
【００３１】
図４および図５に注目すると、図４は、本発明の好ましいクラスタリング技術の方法を示す高レベル・フローチャートである。これに対して、図５（ａ）〜（ｄ）は、簡略化された二次元データセットに関して、クラスタリングを図式的に示している。
【００３２】
好ましい実施例の場合、本発明のクラスタリング法は、Ｔ．ゴンザレスのアルゴリズムとして知られる方法である。このアルゴリズムは、Ｔ．ゴンザレス「最大クラスター間距離を最小化するためのクラスタリング（Ｃｌｕｓｔｅｒｉｎｇ ｔｏ Ｍｉｎｉｍｉｚｅ ｔｈｅ Ｍａｘｉｍｕｍ Ｉｎｔｅｒｃｌｕｓｔｅｒ Ｄｉｓｔａｎｃｅ）」， Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ 第３８巻第２９３〜３０６頁（１９８５）に言及されている（これを参考のため本明細書中に引用する）。データポイント集合内のデータをクラスタリングする他の多くの方法があり、これらの方法のいずれも本発明に使用することができる。Ｔ．ゴンザレスのアルゴリズムは、パーティショニングによってクラスタリングする好ましい方法である。なぜならば、このアルゴリズムは他の技術を上回るいくつかの利点を有するからである。その１つとして、この好ましいＴ．ゴンザレスのクラスタリング法は、パーティショニングとして知られる非階層的クラスタリング法であり、この場合、所与のデータポイント集合が、クラスター代表ポイントによって表されるクラスター群のいくつかの固有の集合にパーティショニングされ、クラスター同士がオーバラップすることはない（すなわち、データポイントが２つのクラスター群に属することはない）ことが挙げられる。パーティショニングは、下で説明するようにいわゆるミニマックス法則（ｍｉｎ−ｍａｘ ｒｕｌｅ）に従って実施され、単純な二次元の場合には、クラスター毎に半径Ｒを備えた円を有するＫ個の集合にデータをパーティショニングすることと考えることができる。この場合、Ｒは全てのクラスターに関して同じであり、クラスター代表ポイントは、半径Ｒの円の中心であり、さらに、以下のミニマックス法則が満足される：「集合Ｓｉにおけるいずれの代表クラスター・データ・ポイントに関しても（集合Ｓｉ（１≦ｉ≦Ｋ）、ただしＫ＝パーティションのサイズ、つまり、元の集合Ｓがパーティショニングされることにより形成される集合の最大数であり、元の集合が全体的に集合｛Ｓ１，Ｓ２…ＳＫ｝にパーティショニングされると仮定する）、集合Ｓｉのいずれのクラスターの代表クラスター・データポイントによって形成される最大半径をも最小化する。」
一般的に、Ｋ個の代表ポイントのそれぞれがどのポイントかを見出し、上記ミニマックス法則に相応する最適な「最大半径」を見出す際には、いわゆる「Ｎ−Ｐハード」問題という困難な計算の問題が生じる。上述のミニマックス・パーティション問題の解決に対するいわゆるヒューリステックなＴ．ゴンザレスのアルゴリズムの利点は、もしＮ−Ｐハードというミニマックス・クラスタリング・パーティションの問題に対する最適な解ＯＰＴＩ（ｉ）が存在し、かつＯＰＴＩ（ｉ）が最適半径ＲＯＰＴＩを有するならば、Ｔ．ゴンザレスのアルゴリズムは、最適半径ＲＯＰＴＩの２倍以下の半径Ｒｓｕｂ−ｏｐｔｉをもたらすことが判っていることである。このことは有意義である。それというのも、データセットがクラスターにパーティショニングされる際の最適な半径から遠ざかれば遠ざかるほど、代表クラスタリングできない可能性が高まり、エラーが発生しやすくなるからである。加えて、Ｔ．ゴンザレスのアルゴリズムは、いくつかのクラスタリング技術によるような非線形シーケンスとは異なり、計算上の資源および時間、またはＯ（ｋ＊Ｎ）に関して（ｋ＝クラスター数）、ほぼ線形プロセスなので、Ｔ．ゴンザレスのアルゴリズムを利用してＮ個の入力を解くのに所与の数のコンピュータ・クロック・サイクルまたはステップを要する場合、２倍多くの入力を解くには概ね２倍の時間がかかり、４倍多くの入力に対しては４倍の時間がかかるだけである。最後に、ミニマックス・クラスタリングのためのＴ．ゴンザレスのアルゴリズムは、解決に向かって適正かつ迅速に収束することが判っている。
【００３３】
クラスタリングの非階層的パーティショニング法が、Ｔ．ゴンザレス法に従って本発明の好ましい実施例に採用されたが、しかし、概ねあらゆるクラスタリング法、例えば単一リンク（ＳＬＩＮＫ、最小スパニング樹アルゴリズムを含む）、完全リンク、グループ平均リンク、グループ平均リンクのためのボールヒーズ・アルゴリズム、およびウォーズ法（ウォーズ法のための逆数最近傍アルゴリズムを含む）を、本発明の教示内容を用いて採用することができる。
【００３４】
図５（ａ）〜図５（ｃ）は、Ｔ．ゴンザレスのアルゴリズムを二次元空間において図示している。従って図５（ａ）〜図５（ｃ）は、データセット、つまりポイント集合の集団（図５（ａ）〜図５（ｃ）における黒点）、例えばプロファイル測定機器で捕捉されたリアルタイム信号に潜在的にマッチングするデータを表すライブラリ・データを示しており、各ポイントはベクトルとして表されている。データセット・ポイントは説明のために二次元で表されている。実際はデータはより高次、例えば上述の１０６成分次元ベクトルである。
【００３５】
図４のフローチャートに概略的に示したように、いかにしてデータをクラスタリングするかを見極める上で、Ｔ．ゴンザレスのアルゴリズムと連携する２つの原理的ステップがある。第１のステップは、どのような代表クラスター・データポイントが選択されるかを見極めるステップであり、これらのデータポイントはパーティショニング法則によって定められる。第２のステップは、これらの特定の代表クラスター・データポイントに全てのデータを割り当て、これによりクラスターを形成するステップである。
【００３６】
元のデータセットＳ、つまり、図５（ａ）において符号５−ａ−１００で示され、データポイント全てから成る元のデータセットＳ（図５（ａ）において黒点で示す）が「クラスタリング」されるようになっているか、または、または整数Ｋ個つまりパーティション・サイズの複数の集合に分けられるようになっていると仮定する。各データポイントが固有のクラスターに属し、どのデータポイントも２つ以上のクラスターには属さないという点でクラスタリングが非階層的であることを仮定する。Ｋ＝３個の集合、すなわち、ポイントのデータセット全体が３つのクラスターに分けられることをアプリオリに仮定する。注意すべきなのは、このようないずれのクラスターに関しても、Ｋの最小サイズはＫ＝１個の集合に等しく（Ｋが１に等しいことは無意味になってしまうので、これは極端な状況であり、この場合データポイントの集合全体は分割されない元のままの集合である）、これに対して、Ｋの最大サイズはデータポイント（図５（ａ）における黒点）の総数に等しく、これも極端な状況である。このようなクラスターにおけるＫの最適なサイズに関して、最適サイズＫを選択する上でのクラスタリング理論の文献がある。この理論によれば、Ｋのサイズを余りにも小さくすると、集合を大きすぎる「粒」の状態に、または粗くしたままにしてしまうのに対し、Ｋのサイズを余りにも大きくすると、過剰の計算を招いてしまう。さらに、計算時間または計算資源に関するＫの値をグラフに描くことができ、どのようなＫの値が最適かを検査によって知ることができる。ｎ次元データ空間（図５（ａ）〜５（ｃ）ではｎ＝２）に対応するパーティション・サイズを選択することは、図４のソフトウェア・モジュール・ステップ４−１０で行われ、人間の入力に頼ることができる。
【００３７】
ここで専門用語の簡単な説明に移り、集合Ｓのデータポイントの高次元ベクトルの性質について説明する。ユークリッドｎ次元空間、およびこの空間内の多次元ベクトルが、これを記述するｎタプルまたは単位ベクトル（例えば単位ベクトル＜ｉ，ｊ，ｋ，…ｎ＞）を有すると考えると、ｎ次元空間内の任意のポイント「Ｘ」は、単位ベクトル方向（例えば＜ｉ，ｊ，ｋ，…ｎ＞）に沿ったスカラー成分｛ｘ１，ｘ２，ｘ３，…ｘｎ｝を有するベクトルによって表すことができる。この場合「ｘ１」は単位ベクトルのうちの１つ（例えば三次元を扱う場合には「ｘ」方向と一般に呼ばれる「ｉ」単位ベクトル）に沿った多次元ベクトルのスカラー成分であり、「ｘ２」は第２の単位ベクトル（例えば、「ｙ」方向と一般に呼ばれる「ｊ」単位ベクトル）に沿った多次元ベクトルのスカラー成分であり、「ｘ３」は第３の単位ベクトル（例えば、「ｚ」方向と一般に呼ばれる「ｋ」単位ベクトル）に沿った多次元ベクトルのスカラー成分であり、以下同様である。しかもこの場合、ｘｎは、「ｎ」（最後の）単位ベクトルに沿った多次元ベクトルの最後のスカラー成分を表す。こうして、座標の記述に関して、所与のポイント「Ｘ」は、高次元Ｎ空間における多次元ベクトル＜Ｘ＞によって表すことができ、
＜Ｘ＞＝＜ｘ１，ｘ２，ｘ３，…ｘｎ＞
として示すことができる。
第２のポイント「Ｙ」は、多次元ベクトル＜Ｙ＞によって同様に：
＜Ｙ＞＝＜ｙ１，ｙ２，ｙ３，…ｙｎ＞
のように表すことができる。
【００３８】
ここで再び図４に戻ると、ソフトウェア・モジュール４−２０は、ステップ４−１０の後に続くステップであり、このソフトウェア・モジュール４−２０では、プログラムは集合Ｓ内のデータポイント間のユークリッド距離を算出し、こうして算出されたデータを後で利用するために、出力ファイル４−３０に記憶することができる。
【００３９】
多次元空間内におけるポイント「Ｘ」と「Ｙ」との間のユークリッド距離（Ｅ．Ｄ．）は、ベクトル差Ｅ．Ｄ．ＹＸ＝＜Ｙ＞−＜Ｘ＞、または、
【００４０】
【数１】
2004528618.tif 000003
【００４１】
によって表すことができる。
【００４２】
２つの次元の簡単な事例に関して明らかなように、このユークリッド距離方程式は、平面内の二点間の距離に関してよく知られた形になる。
【００４３】
ユークリッド距離がこれらのポイントに関して算出されると、クラスター・パーティション毎の代表データポイントが、以下の法則を満足させるように選択される。この法則はＴ．ゴンザレスのパーティション・ミニマックス法則と呼ぶことができる。
【００４４】
Ｔ．ゴンザレスのパーティション・ミニマックス法則：
集合Ｓｉにおけるいずれの代表クラスター・データ・ポイントに関しても（集合Ｓｉ（１≦ｉ≦Ｋ）、ただしＫ＝パーティションのサイズ、つまり、元の集合Ｓがパーティショニングされることにより形成される集合の最大数である。元の集合が全体的に集合｛Ｓ１，Ｓ２…ＳＫ｝にパーティショニングされると仮定する）、集合Ｓｉのいずれのクラスターの代表クラスター・データポイントによって形成される最大半径をも最小化する。
【００４５】
図５（ａ）〜５（ｃ）との関連において説明したように、これが図式的に意味するのは、あらゆるクラスター（「円」自体およびその中のポイント）の代表クラスター・データ・ポイント（円の「中心」、例えば図２（ｂ）参照）が、等しい半径を有する円を形成し、互いに接触しないことである。二次元空間では、このことは少しおおざっぱに言えば、カップの水の表面上で等しいサイズの石鹸泡が表面張力作用により押し寄せあっているときに形成されるパターンに似ている。
【００４６】
図５（ａ）に示したように、Ｔ．ゴンザレスの基準を満足させるような代表クラスター・データポイントの有力候補データポイントは、Ｋ＝２の場合、この集合の終端データポイント、例えば終端データポイント５−ａ−１０および５−ａ−２０となる。他の２つのデータポイント５−ａ−１０および５−ａ−２０から等距離の位置にあるデータポイント５−ａ−３０が別の候補となってもよいが、しかし、法則の適用と結びつける場合には、２つの候補のうちの一方が任意に選択されてよい（例えば適格な第１候補）。
【００４７】
図５（ｂ）は、代表クラスター・ポイントとしてデータポイント５−ａ−１０および５−ａ−２０を選択したあと、データポイントの集合Ｓを２つのクラスターにパーティショニングする状態を示している。図示のような二次元空間内では、データポイント５−ａ−１０および５−ａ−２０は、それぞれ等しい半径５−ｂ−１００および５−ｂ−２００を有する円の中心を形成する。これらの円は境界５−ｂ−１１０で互いに接触している。２つの代表クラスター・データポイント５−ａ−１０および５−ａ−２０は、全てのデータポイントの元の集合５−ｂ−０を２つの下位集合に分ける。これらの下位集合は、クラスター集合Ｉ（参照番号５−ｂ−５０）、および、クラスター集合ＩＩ（参照番号５−ｂ−６０）としてローマ数字で示したクラスターによって表される。この中に含有される全てのポイントは、代表クラスター・ポイント５−ａ−１０を有するクラスター集合Ｉ、または、代表クラスター・ポイント５−ａ−２０を有するクラスター集合ＩＩに属している。両クラスター・ポイントはそれぞれのクラスター集合Ｉ，ＩＩを代表する。なお、クラスター集合ＩおよびＩＩの円は、代表クラスター・データポイントを画定し、円外部のポイントはそれにもかかわらず、どちらの代表クラスター・データポイント５−ａ−１０または５−ａ−２０がそれぞれユークリッド距離において近接しているかに応じて、クラスター集合ＩまたはＩＩに割り当てられる。
【００４８】
いずれのクラスターにも属することができる境界上にポイント、例えば図５（ｂ）のポイント５−ｂ−１１２がある場合には、これらのポイントは２つのクラスターのうちのいずれかに任意に配置されてよい。
【００４９】
図４において、当初のクラスター代表ポイントを上述のように選択することに相当するプロセスは、プロセス・ステップ４−４０から成るソフトウェア・モジュールに相応することになる。クラスター代表のための候補ポイントは、決定ブロックソフトウェア・モジュール４−５０によって示すように、Ｔ．ゴンザレスのミニマックス法則に従ってヒューリスティックに見出される。このステップは、典型的には時間およびコンピュータ資源に関して集中的であり、代表クラスター・データポイント候補がＴ．ゴンザレス基準を満足させない場合、あらたなポイントが選択され、ステップ４−７０の「ＮＯ」分岐によって示すように、このプロセスが繰り返される。しかし典型的には、Ｔ．ゴンザレス法のアルゴリズムは、迅速に収束し、最適な半径の２倍以下の、代表クラスター・データ中心ポイントによって表される円の半径に関する誤り率を有することが判っている。
【００５０】
決定ブロック４−８０のソフトウェア・モジュールにおいて、本発明のソフトウェアは、Ｋの限界つまりパーティション・サイズに達しているかどうかを見るためにチェックを行う。図５（ａ）〜５（ｃ）の例では、Ｋ＝３なので、プログラムは「ＮＯ」分岐に沿って枝分かれし、ブロック４−４０でループを繰り返すことになる。このブロック４−４０では、第３のクラスターのために、別の代表クラスター・データポイント候補が選択される。このことは図５（ｃ）に図示されている。図５（ｃ）では、Ｔ．ゴンザレス・パーティション・ミニマックス法則を満足させるポイントは、データポイント５−ａ−３０である。このデータポイント５−ａ−３０は偶然、前の代表クラスター・データポイント５−ａ−１０および５−ａ−２０から等間隔をおいて位置している。これらの代表データポイント５−ａ−１０、５−ａ−２０および５−ａ−３０のそれぞれは、半径５−ｃ−１０００、５−ｃ−２０００、５−ｃ−３０００を有しており、これらの半径は、互いに境を接する円を形成し、元の集合Ｓ（５−ａ−１００）を３つのクラスター下位集合に分ける。これらの下位集合を、ローマ数字でクラスター集合Ｉ，クラスター集合ＩＩおよびクラスター集合ＩＩＩとして図示のように表す。これらのクラスターは、境界５−ｃ−３３３によって分離されており、これら３つのクラスターのそれぞれは、その内部に見出されるデータポイント（すなわち黒点）から構成されている。前述の通り、両クラスターに対するボーダライン・データポイント、例えばデータポイント５−ｃ−ｂｏｒｄは、いずれかのクラスターに割り当てられてよい。さらに、代表クラスター・データによって形成された円の外部に位置するデータポイントは、それにもかかわらず、当該データポイントと、近くの代表クラスター・データポイントとの間の最短ユークリッド距離を見出すことに基づいて、特定のクラスターに割り当てられる。これに伴い、このデータポイントは、最も近接したクラスター代表によって表されたクラスターに割り当てられる。従って元の集合Ｓ（５−ａ−１００）の全てのデータポイントは、固有のクラスターに割り当てられる。
【００５１】
決定ブロック・ステップ４−８０では、所定のパーティション・サイズに達していると仮定して、プログラムはプロセス・ステップ４−９０に分岐する。このステップでは、各クラスターに関連するデータセットが二次メモリー（例えばハード・ドライブ４−１００）に記憶されるのに対し、それぞれのクラスターを表す代表クラスター・データポイントは、本明細書中に教示したプログラムによって使用するために、一次メモリー（例えばＲＡＭ）に記憶される。
【００５２】
ソフトウェア・モジュール・プロセス・ブロック４−１０５において、任意の計算、例えば上述のように、ＲおよびＲ−εの境界帯域内にある各ポイントに関して計算を行うことができる。この場合、Ｒ＝クラスター半径、Ｄ＝信号と境界帯域から最も近接する代表マッチとの間の距離、およびε＝イプシロンつまり小さな許容誤差であり、クラスターはこの境界帯域内のポイントから２＊（Ｒ＋Ｄ）の距離内に位置している。この算出値は、クラスター代表からこのような境界帯域によって画定された距離であることに基づいて、この境界帯域内に「ボーダライン・マッチ」として生じるいずれのリアルタイム信号データにも対応する付加的なクラスターを取り込むのに用いることができる。ソフトウェア・モジュール・ブロック４−１０５は、エラーのチェックまたは他の任意のソフトウェア・ルーチンに用いることもできる。
【００５３】
図４に戻ると、さらなるアクティビティがないと仮定して、プログラムはステップ４−１１０で終了する。
【００５４】
さらに、図３のボックス３−４０との関連において本明細書中に説明したような「ボーダライン・マッチ」問題の点で、リアルタイム・データ信号と、最近似ライブラリ・プロファイル・データポイントとのマッチング問題は、リアルタイム・データ信号がクラスター集合の境界に位置する場合に悪化する。本明細書中に説明したように、このようなリアルタイム信号データがクラスターのボーダライン、例えば上で定義した「境界帯域」に近接している場合、リアルタイム信号との最近似マッチは、隣接するクラスター内（またはより一般的に云えば、境界帯域から２＊（Ｒ＋Ｄ）の距離内に位置するクラスタ内）のデータポイントと対応する場合がある。このような現象を簡略化された二次元の事例で例証するために、図５（ｄ）について考察する。図５（ｄ）は、図５（ｃ）の一部をクローズアップしている。この図では、クラスター集合ＩおよびＩＩを画定する円５−ｃ−１００，５−ｃ−２００が、互いに接している。入来リアルタイム・データ信号を、データポイント５Ｄ−１０によって画定されたポイントによって表すことができると仮定する。検査により、このリアルタイム・データ信号ポイント５Ｄ−１０が、厳密に言えばクラスター集合Ｉ内に位置することが判る。従って、リアルタイム・データ信号ポイント５Ｄ−１０を、クラスタ代表だけとマッチングさせようとすれば、マッチとしてクラスター集合Ｉが見出され、クラスター集合Ｉ内部での第２のサーチが、リアルタイム信号データポイント５Ｄ−１０との最近似クラスター・プロファイル・データポイントとして、クラスター・ポイント５Ｄ−４０または５Ｄ−４１のようなポイントを与えてしまう。しかし明らかにこれは間違いである。それというのも、検査によって判るように、リアルタイム・データ信号ポイント５Ｄ−１０との最近似マッチング（最小ユークリッド距離）は、５Ｄ−２０または５Ｄ−３０のようなポイントのうちの１つであり、このようなポイントはクラスター集合ＩＩ内に位置するからである。このように、５Ｄ−１０のような入来リアルタイム・データ信号が、或る境界帯域によって画定されたクラスタ集合の境界または境界線に充分に近接しているときはいつでも、「ボーダーライン・マッチ」事例が発生し、リアルタイム・データ信号との最近似マッチのために考えなければならないクラスターは、「半径Ｒプラス当該境界のＤ」の二倍の距離内に位置する全てのクラスターである。この場合Ｒはクラスターの半径に等しく、Ｄは、信号と、境界帯域から最も近接する代表マッチとの間の距離である。図５（ｃ）の例では、このような距離には、このような「ボーダライン・マッチ」事例の場合、クラスターＩ，ＩＩ，ＩＩＩが含まれる。２（Ｒ＋Ｄ）という距離は、考えられ得る潜在的な最近似ポイントを確保するための安全範囲として選択され、別の安全保守範囲を選択することもできる。より高次元の空間では、このような距離内には３つ以上のクラスターが含まれる場合もある。
【００５５】
さらに本発明に関連して、本明細書中に記載したクラスタリング技術は、好ましいクラスタリング・アルゴリズムとして、「最大クラスター間距離を最小化するためのクラスタリング（Ｃｌｕｓｔｅｒｉｎｇ ｔｏ Ｍｉｎｉｍｉｚｅ ｔｈｅ Ｍａｘｉｍｕｍ Ｉｎｔｅｒｃｌｕｓｔｅｒ Ｄｉｓｔａｎｃｅ）」， Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ 第３８巻第２９３〜３０６頁（１９８５）（これを参考のため本明細書中に引用する）に言及されたミニマックスＴ．ゴンザレス・アルゴリズムとして知られる、非階層的クラスタリング・アルゴリズムを採用するが、しかし、本発明の教示内容を用いて、いかなるクラスタリング法も採用することができる。さらに、Ｔ．ゴンザレスのアルゴリズムの代わりにあらゆるミニマックス・クラスタリング・アルゴリズム、例えばＴ． ＦｅｄｅｒおよびＤ． Ｇｒｅｅｎｅによって記載された論文「近似クラスタリングのための最適アルゴリズム（Ｏｐｔｉｍａｌ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ａｐｐｒｏｘｉｍａｔｅ Ｃｌｕｓｔｅｒｉｎｇ）」 Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ （ＳＴＯＣ）第４３４−４４４頁（１９８８）を採用することができる。この論文を参考のため、本明細書中に引用する。さらに、他のクラスタリング・アルゴリズムが採用されてよい。このように例えば、本発明に採用され得る他のクラスタリング・アルゴリズムは、階層的方法、例えば単一リンク（ＳＬＩＮＫ、最小スパニング樹アルゴリズムを含む）、完全リンク、グループ平均リンク、グループ平均リンクのためのボールヒーズ・アルゴリズム、およびウォーズ法（ウォーズ法のための逆数最近傍アルゴリズムを含む）を含んでよい。さらに、ミニマックス問題を解決するために、Ｔ．ゴンザレスのアルゴリズムの代わりに、他のヒューリスティック・アルゴリズム、例えば焼きなまし法または最急降下法が、たとえこのような方法がＴ．ゴンザレスのアルゴリズムよりも概して劣っているとしても、採用されてよい。
【００５６】
さらに本発明において、ポイント間の距離を算出するのにユークリッド距離は好ましい測定基準ではあるが、しかし、本発明の価値を下げることのない適正なものであるならば、いかなる測定基準が使用されてもよい。さらに、特定のクラスターを画定する幾何学的形状として、円、球体、または超球体（ｈｙｐｅｒ ｓｐｈｅｒｅｓ）を想定することができ、あらゆる特定の幾何学的形状およびあらゆる特定のトポロジーを使用することができる。
【００５７】
本発明の上述の実施例は、例示および説明として提供するものである。これらは、記載の通りの形に本発明を限定するものではない。具体的には、本明細書中に記載した本発明の機能的な実施は、ハードウェア、ファームウェアおよび／または他の利用可能な機能成分またはビルディング・ブロックにおいて同等に実現されると考えられる。他の変更形および実施例も上記教示内容に照らして可能であり、従って本発明の範囲はこの詳細な説明によってではなく、別記請求の範囲によって限定される。
【図面の簡単な説明】
【図１】
図１は、本発明を実施するプロファイル測定システムを示すブロック・ダイヤグラムである。
【図２ａ】
図２（ａ）は、プロファイル測定信号を表すベクトル・フィールドを示す図である。
【図２ｂ】
図２（ｂ）は、プロファイル測定信号を表すポイントの二次元クラスター・マップを簡略化して示す図である。
【図３】
図３は、本発明の好ましいクラスタリング法を示すトップ・レベル・フローチャートである。
【図４】
図４は、クラスタリング技術を用いて、データをパーティショニングする好ましい方法を示すトップ・レベル・フローチャートである。
【図５ａ】
図５（ａ）は、好ましいクラスタリング法を用いてパーティショニングされたデータ・ポイント集合を簡略化して示す二次元的な図である。
【図５ｂ】
図５（ｂ）は、好ましいクラスタリング法を用いてパーティショニングされたデータ・ポイント集合を簡略化して示す二次元的な図である。
【図５ｃ】
図５（ｃ）は、好ましいクラスタリング法を用いてパーティショニングされたデータ・ポイント集合を簡略化して示す二次元的な図である。
【図５ｄ】
図５（ｄ）は、「ボーダライン・マッチ」の問題を示す図５（ｃ）の拡大図である。
【図３】
2004528618.tif 000004
【図４】
2004528618.tif 000005
【国際公開パンフレット】
2004528618.tif 000006
2004528618.tif 000007
2004528618.tif 000008
2004528618.tif 000009
2004528618.tif 000010
2004528618.tif 000011
2004528618.tif 000012
2004528618.tif 000013
2004528618.tif 000014
2004528618.tif 000015
2004528618.tif 000016
2004528618.tif 000017
2004528618.tif 000018
2004528618.tif 000019
2004528618.tif 000020
2004528618.tif 000021
2004528618.tif 000022
2004528618.tif 000023
2004528618.tif 000024
2004528618.tif 000025
2004528618.tif 000026
2004528618.tif 000027
2004528618.tif 000028
2004528618.tif 000029
2004528618.tif 000030
2004528618.tif 000031
2004528618.tif 000032
2004528618.tif 000033
2004528618.tif 000034
2004528618.tif 000035
2004528618.tif 000036
2004528618.tif 000037
2004528618.tif 000038
2004528618.tif 000039
2004528618.tif 000040
2004528618.tif 000041
2004528618.tif 000042
2004528618.tif 000043
【国際公開パンフレット（コレクトバージョン）】
2004528618.tif 000044
2004528618.tif 000045
【国際調査報告】
2004528618.tif 000046
2004528618.tif 000047
2004528618.tif 000048