JPH10307828A - クラスタリング処理方法およびクラスタリング処理システム - Google Patents

Abstract

(57)【要約】 【課題】 処理の対象となるデータあるいはその処理に
必要な中間データが主記憶に乗り切らなくてもクラスタ
リング処理をできるようにすること。 【解決手段】 ２次記憶装置２０上に、処理の対象とな
るレコードを格納するファイル６と、チェーンデータを
保存する一時ファイル１７を設け、また、主記憶装置１
０上に、上記レコードの一部を格納する入力バッファ
２、出力バッファ３と、上記ファイル６に格納される各
レコードを管理するレコード管理情報４と、チェーンデ
ータを格納するチェーンバッファ５とを設ける。クラス
タリング処理部１は処理を行うに際し、処理に必要なレ
コードが主記憶装置上ないとき、ファイル６から上記レ
コードを含むレコードを入力バッファに読み込んで処理
を行い、また、出力バッファが一杯になったら、出力バ
ッファに格納されたレコードをファイル６に保存し、処
理結果のレコードを出力バッファに格納する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ベクトルの形式で
記述されたデータ群を、類似するもの同士をまとめて塊
（クラスタ）を作る処理、すなわちクリスタリング処理
を行う処理方法およびクラスタリング処理システムに関
する。このように処理は、大量データがあり、その中に
構造を発見したいときに有効である。利用分野として
は、科学技術分野での恒星のデータベースを類似する複
数のクラスタに分類する処理や、事務処理分野での顧客
のプロフィール情報に従って顧客を分類する処理などが
考えられる。

【０００２】

【従来の技術】クラスタリング処理方法としては、例え
ば、Ed.W.B.Frankers and R.Baeza-Yaters,Prentice Ha
ll,1992 「Information Retrieval:Data Structure & A
lgorithms 」（参考文献１）に示される様々な手法が提
案されている。これらの中で実際に多く使われるのは、
例えば、H.C.Romesburg,共訳 西田英郎・佐藤嗣二・内
田老鶴圃,1992 「実例クラスター分析」（参考文献２）
に示されるように、階層クラスタリング手法に分類され
る手法、特に、Ｇｒｏｕｐ Ａｖａｒａｇｅ法とＷａｒ
ｄ法である。

【０００３】

【発明が解決しようとする課題】上記したＧｒｏｕｐ
Ａｖａｒａｇｅ法とＷａｒｄ法は、主記憶上での処理を
前提としている。これらの手法を利用するには、クラス
タリング処理の対象となるデータ或いは同処理に必要な
中間データが主記憶に乗ることになる。しかし、近年、
大規模なデータベース中に蓄えられた大量のデータをク
ラスタリング処理の対象とするケースが出てきている。
その場合、クラスタリング処理を行う計算機に大量の主
記憶を用意する必要があり、コストが高くなる。また、
システムが許す最大の主記憶を実装してもクラスタリン
グ処理を行うのに足りない場合は、クラスタリング処理
を諦めなければならない。

【０００４】本発明は上記した事情を考慮してなされた
ものであって、その目的とするところは、クラスタリン
グ処理の対象となるデータあるいはその処理に必要な中
間データが主記憶に乗り切らなくてもクラスタリング処
理を行うことができるクラスタリング処理方法およびク
ラスタリング処理システムを提供することである。

【０００５】

【課題を解決するための手段】本発明は、上記したＷａ
ｒｄ法、特に前記した参考文献１のＰ４３５〜Ｐ４３６
に記載されるReciprocal Nearest Neighbour法（以下Ｒ
ＮＮ法という）による実現をそのベースとして用いてお
り、以下、上記手法によるクラスタリング処理について
簡単に説明する。Ｗａｒｄ法のＲＮＮ法による実装で
は、以下の手順でクラスタリング処理を行う。ここで
は、クラスタリングの処理の対象となるデータは全て主
記憶上に乗っているとする。また、データはレコードの
集合として表現されているとする。各レコードは処理対
象ベクトルと同次元のベクトル情報と、そのレコードが
代表するベクトルの数と、そのレコードが代表するベク
トル群の分散を保持する。初期状態では、処理対象のベ
クトル数と同数のレコードが存在し、そのレコード群は
処理対象ベクトルと１対１に対応し、表現するベクトル
の数は１であり、表現するベクトル間の分散は０であ
る。

【０００６】（１）任意のレコードを一つ選びv1とす
る。 （２）v1とv1以外のレコードとの距離を、例えば前記し
た参考文献１の定義に従って計算し、v1と最も距離が近
いものをv2とする。 （３）v1からv2へチェーンを張る。 （４）v2とv2以外のレコードとの距離を、上記（２）と
同様に計算し、v2と最も近いものをv3とする。 （５）v2からv3にチェーンを張る。 （６）v1とv3が同じレコードを表しているかどうかチェ
ックする。これが同じレコードなら、下記の（８）に飛
ぶ。また、同じレコードでなければ、次の（７）に進
む。 （７）v2をv1とし、v3をv2とし、上記（４）へ飛ぶ。 （８）v1とv2を、例えば前記した参考文献１の定義に従
ってマージし、v1をその結果で置き換える。 （９）残りのレコードが２個以上あるなら、上記（１）
へ飛ぶ。無ければ終了する。

【０００７】以上のように、互いに最近傍のレコード同
士をマージし、さらに、互いに最近傍にあるレコードと
マージされたレコード同士、もしくは、マージされたレ
コード同士をマージしていくことにより、最終的にレコ
ードを複数のクラスタに分類することができる。なお、
実際の応用においては、上記流れの通りに動作すると、
クラスタリング処理の経緯が記録として残らないので、
上記（８）の処理の中で、どの２つのレコードをマージ
したかを何らかの形で外部に報告する様にする。しか
し、これはクラスタリング処理の本質ではないので、上
記説明ではその動作を省いている。

【０００８】本発明は上記処理を、レコード群が外部記
憶装置等の２次記憶装置上に存在する場合にも動作する
ように拡張したものであり、クラスタリング処理の対象
となるレコードあるいは同処理に必要な中間データを２
次記憶装置上に置き、主記憶装置上には、レコードの一
部とそのデータを管理するデータを置き、上記クスタリ
ング処理を行う。これにより、クラスタリング処理の対
象となるレコードあるいは同処理に必要な中間データの
全てが主記憶装置上に乗り切らなくても処理を完了する
ことができる。

【０００９】図１は本発明の原理説明図である。本発明
においては、上記したように２次記憶装置２０上に、処
理の対象となるレコードを格納するファイル６と、チェ
ーンバッファのチェーンデータを保存する一時ファイル
７を設け、また、主記憶装置１０上に上記レコードのク
ラスタリング処理を行うクラスタリング処理部１と、上
記レコードの一部を格納する入力バッファ２および出力
バッファ３と、上記２次記憶装置上のファイルに格納さ
れる各レコードに１対１に対応したレコード管理情報４
と、チェーン情報を格納するチェーンバッファ５とを設
ける。

【００１０】そして、クラスタリング処理部１が上記ク
ラスタリング処理を行うに際し、処理に必要なレコード
が主記憶装置１０上のバッファ２，３にないとき、２次
記憶装置２０上のファイル６から上記レコードを含む一
連のレコードを入力バッファ２に読み込んで処理を行
い、また、上記処理の結果得られたレコードを出力バッ
ファ３に格納するとき、出力バッファ３が一杯になった
ら、出力バッファ３に格納されたレコードを上記２次記
憶装置２０上のファイル６に保存したのち、上記レコー
ドを出力バッファ３に格納することにより、上記レコー
ドのクラスタリング処理を行うようにしたものである。

【００１１】また、処理の対象となるレコード数が多
く、主記憶装置１０上にチェーンバッファ５の領域を確
保できない場合には、２次記憶装置２０上にチェーンバ
ッファ５のデータを格納する一時ファイル７を設け、チ
ェーンバッファ５が一杯になったとき、チェーンバッフ
ァ５のデータを上記一時ファイル７に格納し、また、主
記憶装置１０上にチェーンバッファ５のデータがないと
き、上記一時ファイル７からデータを読み込んで主記憶
装置１０上のチェーンバッファ５に格納する。

【００１２】本発明の請求項１，２の発明においては、
上記のようにしてクラスタリング処理を行うようにした
ので、処理の対象となるレコード数が多く、主記憶装置
上にレコードが乗り切らなくてもクラスタリング処理を
行うことができる。また、比較的小さな主記憶装置の容
量で大量のレコードの処理を行うことができるので、コ
ストの削減を図ることができる。さらに、適切なサイズ
の入力バッファ、出力バッファを設けることにより、主
記憶装置へのアクセス回数を少なくでき、処理時間を短
縮することが可能となる。本発明の請求項３の発明にお
いては、２次記憶装置上にチェーンバッファのデータを
保存する一時ファイルを設けたので、処理の対象となる
レコード数が多い場合でもさらに小容量の主記憶装置で
クラスタリング処理を行うことが可能となる。

【００１３】

【発明の実施の形態】図２は本発明の実施例のシステム
構成を示す図である。同図において、１０は主記憶装置
であり、主記憶装置１０上には、クラスタリング処理を
行うクラスタリング処理部１、入力バッファ２、出力バ
ッファ３、レコード管理情報４、チェーンバッファ５が
設けられる。また、２次記憶装置２０上には、レコード
情報ファイル６と一時ファイル７が設けられており、レ
コード情報ファイル６には、クラスタリング処理の対象
となるレコードが格納される。また、一時ファイル７に
は、チェーンバッファ５のデータが保存される。レコー
ド情報ファイル６の大きさは、処理対象レコードの数を
Ｎ個とするとき、〔２Ｎ−１〕である。

【００１４】クラスタリング処理部１には、同図に示す
ように下記の変数を保持する作業領域が設けられる（以
下、下記作業領域とその領域に格納される変数を同じ名
前で呼ぶこととする）。 (a) v1 ：レコードを保持する領域、初期値なし (b) v2 ：レコードを保持する領域、初期値なし (c) wp ：レコードv1を指すポインタ、初期値なし (d) wpnext ：レコードv2を指すポインタ、初期値なし (e) wpprev ：レコードv1の一つ前のレコードを指すポ
インタ、初期値なし (f) irec ：最近傍レコードを番号を保持する領域、
初期値なし (g) imin ：最小距離を保持する領域、初期値なし (h) Obufp ：出力バッファの先頭レコードを保持する
領域、初期値recnum+1 (i) cbufp ：チェーンの長さを保持する領域、初期値
０ (j) 1rec ：最終レコードを保持する領域、初期値re
cnum (k) recnum ：処理対象レコード数 (l) mergecnt：マージカウント（マージ回数）、初期値
０ (m) inpfilenum：入力ファイル名

【００１５】入力バッファ３は、２次記憶装置２０上の
レコード情報ファイル６から読み込んだレコードを保持
し、また、出力バッファ１４はレコード情報ファイル６
へ書き出すレコードを保持するものであり、図３に示す
ようにレコードの分散値とベクトルの数と可変長の項目
とから構成されている。初期状態においては、前記した
ように上記ベクトル数は１、分散は０である。各バッフ
ァ２，３の大きさはｎ（ｎ＜Ｎ）であり、入力バッファ
３は、計算の対象のレコードがなくなったとき、そのレ
コードを含むｎ個のレコードをレコード情報ファイル６
から読み込む。また、出力バッファ３はマージされたレ
コードを格納し、このバッファが一杯になったとき、そ
の内容をレコード情報ファイル６に格納する。

【００１６】レコード管理情報４は、前記レコード情報
ファイル６に格納されるレコード数に対応した数のエン
トリを持ち、処理対象レコード数がＮ個の場合、図４に
示すように（２Ｎ−１）個のエントリを持つ。また、各
エントリは、３種類の値、０／１／２の内の一つを持
ち、これらのそれぞれは、そのエントリが管理するレコ
ードが以下の状態にあることを示す。 ０：有効であり、かつ、チェインにない。 １：有効であり、かつ、チェインにある。 ２：無効であり、かつ、チェインにない。 上記３種類の値を表現するには、２ビットがあれば足り
るので、レコード管理情報の総量は、（２Ｎ−１）×２
ビットとなる。したがって、処理対象となるレコード数
が１Ｍ個になったとしても、レコード管理データの総量
は高々５１２Ｋバイトであり、これを主記憶装置１０上
に持つことは可能である。

【００１７】チェーンバッファ５は、図５に示すように
Ｎ−１の大きさを持ち、各エントリには、レコード番号
がスタック形式で格納される。ここでレコード番号と
は、各レコードが２次記憶装置２０上で何番目のレコー
ドに当たるかを表す番号である。したがって、一つの番
号が４バイトを必要とするとき、レコード数が１Ｍ個に
なったとしても、チェーンバッファ５に格納されるデー
タの総量は高々４Ｍバイトである。これは、上記レコー
ド管理情報の数より多いが、やはり主記憶装置１０上に
持つことが可能な量である。なお、本実施例では、前記
したようにチェーンバッファ５のデータを一時保存する
ための一時ファイル７を設け、チェーンバッファ５が一
杯になったとき、一時ファイル７に保存する。そして、
チェーンバッファ５からレコードチェーンデータを取り
出そうとしたとき、チェーンバッファ５にデータがなか
ったらレコードチェーンデータを上記一時ファイル７か
ら取り出してくる。

【００１８】図６、図７は本実施例のメインフローであ
り、また、図８〜図１３は図６、図７中の示されるfunc
１〜func5 の処理フローを示す図であり、同図により本
実施例のクラスタリング処理について説明する。初期状
態では、処理対象ベクトル数と同数のレコード（＝Ｎ）
が２次記憶装置２０のレコード情報ファイル６上に存在
し、そのレコード群は処理対象ベクトルと１対１に対応
し、前記したように各レコードが表現するベクトル数は
１であり、表現する分散は０である。レコード管理情報
４の各エントリは０の値（有効であり、かつ、チェ−ン
にない）を持ち、チェーンバッファ５の全てのエントリ
はＮＵＬＬポインタを持つ。また、クラスタリング処理
部１の各作業領域には前記(a) 〜(m) に示した初期値が
格納される。

【００１９】図６において、まず、ステップＳ１におい
て、２次記憶装置２０上のファイルからレコード数recn
um、入力ファイル名inpfilenum等を読み込み、クラスタ
リング処理部１の各変数を設定する。次に、入力バッフ
ァ２、出力バッファ３、レコード管理情報４、チェーン
バッファ５の領域を確保し、レコード情報ファイル６、
一時ファイル７を開く（ステップＳ２，Ｓ３）。ステッ
プＳ４において、任意のレコードを選んでv1とし、v1の
指すポインタをクラスタリング処理部１のwpに設定す
る。また、チェーンバッファ５にwpを入れ、レコード管
理情報４の上記ポインタwpに対応したエントリを１にす
る。また、チェーンの長さcbufp （初期値は０）に１を
加える。

【００２０】上記ステップＳ４の処理において、上記し
たチェーンバッファ５にwpを入れる際、図８のfunc1 に
示すように次の処理を行う。まず、主記憶装置１０上の
チェーンバッファ５が一杯であるかを調べ（図８のステ
ップＴ１）、チェーンバッファ５が一杯でない場合に
は、上記のようにチェーンバッファ５にwpを入れる（ス
テップＴ３）。また、チェーンバッファ５が一杯の場合
には、チェーンバッファ５を２次記憶装置２０の一時フ
ァイル７に保存し（ステップＴ２）、チェーンバッファ
５にwpを入れる。

【００２１】図６に戻り、ステップＳ５において、出力
バッファ３に上記v1のレコードがあるかを調べ出力バッ
ファにない場合には、ステップＳ６に行き、入力バッフ
ァ２に上記v1のレコードがあるかを調べる。そして、出
力バッファ３にも入力バッファ２にもv1のレコードがな
い場合には、ステップＳ７において、２次記憶装置２０
のレコード情報ファイル６から入力バッファ２に上記v1
を含むレコードを読み込み、ステップＳ８に行く。ま
た、出力バッファ３もしくは入力バッファ２に上記v1の
レコードがある場合にはそのまま、ステップＳ８にい
く。ステップＳ８において、マージカウントmergecnt
（マージ回数）と〔レコード数recnum−１〕を比較し、
mergecnt＜〔レコード数recnum−１〕であれば、以下の
処理を繰り返す。また、mergecnt≧〔レコード数recnum
−１〕になると、出力バッファ３にある情報を２次記憶
装置２０上のレコード情報ファイル６に書き出し（ステ
ップＳ１０）、処理を終了する。

【００２２】mergecnt＜〔レコード数recnum−１〕の場
合には、ステップＳ９において、図９、図１０のfunc2
に示すようにwpと他のレコード間の距離をＷａｒｄ法に
基づいて計算する。図９、図１０の処理の詳細について
後述するが、上記ステップＳ９においては、前記したＲ
ＮＮ法における（２）、（４）に相当した処理を行う。
すなわち、上記v1の最近傍のレコードを求め（最近傍レ
コードを指すポインタがwpnextに設定される）、最近傍
レコード番号をクラスタリング処理部１の変数irecに設
定し、最小距離を変数iminに設定する。

【００２３】次に、図６のステップＳ１１において、チ
ェーンバッファ５のチェーンカウントchaincnt＜２であ
るかを調べ、チェーンカウントchaincnt＜２の場合に
は、図７のステップＳ１５に行く。また、チェーンカウ
ントchaincnt＜２でない場合には、ステップＳ１２にお
いて、レコードv1の一つ前のレコードを指すポインタwp
prevと上記wpnextが一致しているかを調べ、一致してい
る場合には、図７のステップＳ１３に行く。また、wppr
evとwpnextが一致していない場合には、図７のステップ
Ｓ１５に行く（前記ＲＮＮ法における（６）の処理に相
当）。

【００２４】図７のステップＳ１５においては、上記wp
nextの値をチェーンバッファ５に入れ、レコード管理情
報４の上記ポインタwpnextに対応したエントリを１にす
る。また、チェーンの長さcbufp に１を加える（前記Ｒ
ＮＮ法における（５）の処理に相当）。さらに、ポイン
タwpprevにwpの値を入れ、ポインタwpにwpnextの値を入
れ、図６のステップＳ８に戻る（前記ＲＮＮ法における
（７）の処理に相当）。ここで、上記処理において、前
記図８のfunc1 に示したように、主記憶装置１０上のチ
ェーンバッファ５が一杯の場合には、チェーンバッファ
５を２次記憶装置２０の一時ファイル７に保存したの
ち、チェーンバッファ５にwp,wpnext の値を入れる。

【００２５】図７のステップ１３において、ポインタwp
が指すレコードと、ポインタwpnextが指すレコードをマ
ージする。すなわち、図１１のfunc3 に示すように、ポ
インタwpが指すレコードとポインタwpnextが指すレコー
ドをＷａｒｄ法に基づいてマージし（図１１のステップ
Ｔ１）、マージ結果のレコードに含まれるレコードの数
とレコードの分散値を計算する（ステップＴ２）。さら
に、マージカウントmergecntを設定する（ステップＴ
３）（前記ＲＮＮ法における（８）の前半の処理に相
当）。

【００２６】ついで、ステップＳ１４において、マージ
結果を出力バッファ３に格納する。その際、図１２のfu
nc4 に示すように、出力バッファ３が一杯であるかを調
べ（図１２のステップＴ１）、出力バッファ３が一杯の
場合には、出力バッファ３の内容をレコード情報ファイ
ル６に書き出し（図１２のステップＴ２）、出力バッフ
ァの先頭レコード番号を保持する領域Obufp に最終レコ
ード番号1rec＋１の値（1recの初期値は処理対象のレコ
ード数recnum）を設定する（図１２のステップＴ３）。

【００２７】図７に戻り、ステップＳ１６において、最
終レコード番号1recに１を加え、レコード管理情報４の
1rec番目の値を有効、チェーンになしの状態（＝０）に
する。これにより、上記マージ結果が、新たなレコード
として追加されることとなる。次に、ステップＳ１７に
おいて、ポインタwp、wpnextが指すレコードのレコード
管理情報４を無効、チェーンになしの状態とする。これ
により、ポインタwp、wpnextが指すマージの対象となっ
たレコードは、処理対象レコードから外される。ステッ
プＳ１８において、マージカウントmergecntに１を加
え、ステップＳ１９において、前のポインタwpとwpprev
をチェーンバッファ５から外し、チェーンの長さcbufp
の値を−２する（ステップＳ１６〜ステップＳ１８の処
理は、前記ＲＮＮ法における（８）の後半の処理に相
当）。

【００２８】ステップＳ２０において、ポインタwpprev
とwpに入れる値を、チェーンバッファ５から取り出し
（前のポインタwpとwpprevが上記のようにチェーンバッ
ファ５から外されているので、その前のwpとwpprevの値
がチェーンバッファ５から取り出される）、取り出した
値をポインタwpprevとwpに入れ、前記図６のステップＳ
８に戻り上記処理を繰り返す。上記ステップＳ２０の処
理において、wpprevとwpに入れる値をチェーンバッファ
５から取り出す際、図１３に示すfunc5 の処理を行う。

【００２９】すなわち、チェーンバッファ５のレコード
チェーンデータが主記憶装置１０上にあるかを調べ（図
１３のステップＴ１）、レコードチェーンデータが２次
記憶装置２０上にある場合には、レコードチェーンデー
タを２次記憶装置２０から読み出し（図１３のステップ
Ｔ２）、ポインタwpprevとwpに値を設定する。なお、チ
ェーンバッファ５の長さが短くなり、チェーンバッファ
５からポインタwpprevとwpに設定する値が取り出せなく
なった場合には、上記ポインタwpprevとwpに−１のデフ
ォルト値を設定する。

【００３０】図９、図１０は前記したfunc2 における処
理を示すフローチャートであり、同図によりwpと他のレ
コード間の距離計算について説明する。まず、図９のス
テップＴ１において、変数ｉを１に設定し、最小距離im
inを無限大に設定する。ステップＴ２において、上記変
数ｉが最終レコード番号irecより大きいかを調べ、大き
い場合には、処理を終了する。変数ｉが最終レコード番
号irecより大きくない場合には、ステップＴ３に行き、
ｉ番目のレコードをv2として、v2を指すポインタをwpne
xtに設定する。ステップＴ４において、ポインタ値wpと
上記ポインタ値wpnextとが一致するかを調べ、一致して
いる場合にはステップＴ１０に行き、ｉに１を加えてス
テップＴ２に戻る。また、一致していない場合には、ス
テップＴ５に行き、wpnextが指すレコードのレコード管
理情報４の値が、有効、チェーンにない（＝０）である
かを調べ、レコード管理情報４の値が、有効、チェーン
にない（＝０）の場合には、ステップＴ７にいく。

【００３１】また、上記レコード管理情報４の値が、有
効、チェーンにある（＝１）の場合には、次のステップ
Ｔ６に行き、wpnextの値とwpprevの値が一致しているか
を調べ、一致している場合にはステップＴ７に行く。ま
た、一致していない場合には、ステップＴ１０に行き、
ｉに１を加えてステップＴ２に戻る。すなわち、wpnext
の値とwpprevの値が一致している場合、前記したように
wpprev（＝wpnext）が指すレコードのレコード管理情報
４の値は、有効、チェーンにある（＝１）となってい
る。そこで、上記ステップＴ８、Ｔ９の処理を行い、レ
コード管理情報４の値が、有効、チェーンにある（＝
１）の場合には、wpnextの値とwpprevの値が一致してい
るかを調べ、wpnextの値とwpprevの値が一致している場
合のみ、後述する距離計算を行うようにしている。

【００３２】次いで、ステップＴ７において、出力バッ
ファ３にレコードv2があるかを調べ出力バッファ３にな
い場合には、ステップＴ８に行き、入力バッファ２に上
記v2のレコードがあるかを調べる。そして、出力バッフ
ァ３にも入力バッファ２にもv2のレコードがない場合に
は、ステップＴ９において、２次記憶装置２０のレコー
ド情報ファイル６から入力バッファ２に上記v2を含むレ
コードを読み込み、図１０のステップＴ１１に行く。ま
た、出力バッファ３もしくは入力バッファ２に上記v2の
レコードがある場合にはそのまま、図１０のステップＴ
１１にいく。

【００３３】ステップＴ１１において、上記ポインタwp
が指すレコードv1とポインタwpnextが指すレコードv2の
距離idecを前記したＷａｒｄ法の定義に従い計算する。
そして、ステップＴ１２において、上記距離idecが最小
距離iminより小さいかを調べ、小さくない場合には前記
図９のステップＴ１０に行き、ｉに１を加えてステップ
Ｔ２に戻る。また、上記距離idecが最小距離iminより小
さい場合には、ステップＴ１３において、最小距離imin
を保持する領域に上記距離idecを入れ、最近傍レコード
番号irecを保持する領域にwpnextの値を入れて図９のス
テップＴ１０に戻り、上記処理を繰り返す。以上の処理
をｉが最終レコード番号irecになるまで繰り返すことに
より、v1に最も近いレコード番号を得ることができる。

【００３４】以上のように、本実施例においては、主記
憶装置１０上に入力バッファ２、出力バッファ３および
レコード管理情報４を設けるとともに、２次記憶装置２
０上に処理対象となるレコードを格納するレコード情報
ファイル６を設け、レコードv1，v2が入力バッファもし
くは出力バッファにない場合に、上記レコード情報ファ
イル６から該当するレコードを含むレコードを入力バッ
ファに読み込んで処理を行い、また、出力バッファが一
杯になったとき、上記レコード情報ファイル６に書き出
すようにしているので、処理の対象となるレコードある
いはその処理に必要な中間データが主記憶に乗り切らな
くてもクラスタリング処理を行うことが可能となる。

【００３５】また、２次記憶装置２０上のレコード情報
ファイル６からレコードの読み込みが行われるのは、前
記図６のステップＳ７およびステップＳ９だけであり、
また、２次記憶装置２０上のレコード情報ファイル６へ
のレコードの書き込みが行われるのは、図６のステップ
Ｓ１０および図７のＳ１４だけであり、この読み込み、
書き込みは入力バッファと出力バッファの単位で行われ
るので、適切なサイズの入力バッファと出力バッファを
設ければ、２次記憶装置２０へのアクセスを小さくする
ことができ、処理時間を短縮することができる。さら
に、２次記憶装置２０上にチェーンバッファ５を保存す
る一時ファイル７を設けることにより、レコード数が多
くチェーンバッファが大きくなる場合であっても、比較
的小さな主記憶容量で処理を行うことができる。

【００３６】

【発明の効果】以上説明したように、本発明において
は、以下の効果を得ることができる。 （１）２次記憶装置上に処理の対象となるレコードを格
納するファイルを設け、また、主記憶装置上に、上記レ
コードの一部を格納する入力、出力バッファと、２次記
憶装置上のファイルに格納される各レコードに１対１に
対応したレコード管理情報を格納する領域と、チェーン
情報を格納するチェーンバッファとを設けてクラスタリ
ング処理を行うようにしたので、処理の対象となるレコ
ード数が多く、主記憶装置上にレコードが乗り切らなく
てもクラスタリング処理を行うことができる。また、比
較的小さな主記憶装置の容量で大量のレコードの処理を
行うことができるので、コストの削減を図ることができ
る。さらに、適切なサイズの入力バッファ、出力バッフ
ァを設けることにより、主記憶装置へのアクセス回数を
少なくでき、処理時間を短縮することが可能となる。

【００３７】（２）２次記憶装置上にチェーンバッファ
のデータを保存する一時ファイルを設けることにより、
処理の対象となるレコード数が多い場合でも小容量の主
記憶装置でクラスタリング処理を行うことができる。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】本発明の実施例のシステム構成を示す図であ
る。

【図３】本発明の実施例の入力バッファ、出力バッファ
の構造を示す図である。

【図４】本発明の実施例のレコード管理情報を示す図で
ある。

【図５】本発明の実施例のチェーンバッファの構造を示
す図である。

【図６】本発明の実施例のメインフローを示す図である
（その１）

【図７】本発明の実施例のメインフローを示す図である
（その２）

【図８】メインフローにおけるｆｕｎｃ１の処理を示す
図である。

【図９】メインフローにおけるｆｕｎｃ２の処理を示す
図（その１）である。

【図１０】メインフローにおけるｆｕｎｃ２の処理を示
す図（その２）である。

【図１１】メインフローにおけるｆｕｎｃ３の処理を示
す図である。

【図１２】メインフローにおけるｆｕｎｃ４の処理を示
す図である。

【図１３】メインフローにおけるｆｕｎｃ５の処理を示
す図である。

【符号の説明】

１ クラスタリング処理部 ２ 入力バッファ ３ 出力バッファ ４ レコード管理情報 ５ チェーンバッファ ６ レコード情報ファイル ７ 一時ファイル １０ 主記憶装置 ２０ ２次記憶装置

Claims (3)

【特許請求の範囲】
1. 【請求項１】 ベクトル集合の集合に対して、ベクトル
   集合間の定義された距離に基づき、近傍にある２つのベ
   クトル集合をまとめて新しい一つのベクトル集合とする
   操作を繰り返し、最終的に一つのベクトル集合にまとめ
   上げるクラスタリング処理方法であって、 ２次記憶装置上に上記ベクトル集合に対応したレコード
   を格納するファイルを設け、 また、主記憶装置上に、上記レコードの一部を格納する
   入力バッファおよび出力バッファと、上記２次記憶装置
   上のファイルに格納される各レコードに１対１に対応し
   たレコード管理情報を設け、 任意の１レコードから開始して、上記主記憶装置上のレ
   コード管理情報を参照しながら最近傍にあるレコードを
   たどる処理を繰り返し、互いに最近傍にある２つのレコ
   ードを見つけたら、それらをまとめ上げたレコードを作
   成する処理を繰り返してクラスタリング処理を行い、 上記処理に必要となるレコードが主記憶装置上の入力バ
   ッファおよび出力バッファにないとき、２次記憶装置上
   のファイルから上記レコードを含む一連のレコードを入
   力バッファに読み込んで上記処理を行い、 また、上記処理の結果得られたレコードを出力バッファ
   に格納するとき、出力バッファが一杯になったら、出力
   バッファに格納されたレコードを上記２次記憶装置上の
   ファイルに保存したのち、上記レコードを出力バッファ
   に格納することにより、 比較的少ない２次記憶装置へのアクセスにより、主記憶
   装置上に乗り切らない大量のレコードのクラスタリング
   処理を行うことを特徴とするクラスタリング処理方法。
2. 【請求項２】 ベクトル集合の集合に対して、ベクトル
   集合間の定義された距離に基づき、近傍にある２つのベ
   クトル集合をまとめて新しい一つのベクトル集合とする
   操作を繰り返し、最終的に一つのベクトル集合にまとめ
   上げるクラスタリング処理を行うクラスタリング処理シ
   ステムであって、 ２次記憶装置上に上記ベクトル集合に対応したレコード
   を格納するファイルを設け、 また、主記憶装置上に、上記レコードの一部を格納する
   入力バッファおよび出力バッファと、 最近傍にあるレコードを順次登録するチェーンバッファ
   と、 上記２次記憶装置上のファイルに格納される各レコード
   に１対１に対応し、該レコードの有効／無効情報と、該
   レコードがチェーンバッファに登録されているか否かを
   示す情報からなるレコード管理情報とを設け、 クラスタリング処理部は、任意の１レコードから開始し
   て、上記主記憶装置上のレコード管理情報を参照しなが
   ら最近傍にあるレコードをたどる処理を繰り返して最近
   傍にあるレコードを順次チェーンバッファに登録し、互
   いに最近傍にある２つのレコードを見つけたら、それら
   をまとめ上げたレコードを作成する処理を繰り返してク
   ラスタリング処理を行い、 上記処理に必要なレコードが主記憶装置上のバッファに
   ないとき、２次記憶装置上のファイルから上記レコード
   を含む一連のレコードを入力バッファに読み込んで上記
   処理を行い、 また、上記処理の結果得られたレコードを出力バッファ
   に格納するとき、出力バッファが一杯になったら、出力
   バッファに格納されたレコードを上記２次記憶装置上の
   ファイルに保存したのち、上記レコードを出力バッファ
   に格納することにより、上記レコードのクラスタリング
   処理を行うことを特徴とするクラスタリング処理システ
   ム。
3. 【請求項３】 ２次記憶装置上にチェーンバッファのデ
   ータを格納する一時ファイルを設け、チェーンバッファ
   が一杯になったとき、チェーンバッファのデータを上記
   一時ファイルに格納し、また、主記憶装置上にチェーン
   バッファのデータがないとき、上記一時ファイルからデ
   ータを読み込んで、主記憶装置上のチェーンバッファに
   格納することを特徴とする請求項２のクラスタリング処
   理システム。