(57)【要約】精度を維持しつつ速度低下を抑えたデータのクラスタリングを行う。ブロック分割部３は、ＤＢアクセス部２から提供されたブロックを、それぞれのブロックが充分に小さくなるまで分割してゆく。ブロック記憶部８は、ブロック分割部３から提供される、分割されたブロックとそれらの階層関係を記憶する。ブロック統合部５は、記憶されたブロックの階層構造に基づきながら、階層の深い位置から浅い位置へとブロック及びグループを統合する。【特許請求の範囲】
【請求項１】
少なくとも一つのデータを含むブロックとブロック生成条件とを受け取って前記ブロック生成条件に基づいて前記ブロックを分割する簡易類似度計算部と、前記簡易類似度計算部にブロックとブロック生成条件とを渡して分割させる処理を繰り返すことによりブロック間の階層関係を作成するブロック分割部と、前記ブロック間の階層関係とブロックとを記憶するブロック記憶部と、データの組合せについての類似度を計算する類似度計算部と、ブロックに含まれるデータの組合せにかかる類似度を前記類似度計算部に計算させ、前記類似度計算部の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記ブロック記憶部に記憶されたブロック間の階層関係に沿って実行するブロック統合部と、を有することを特徴とするデータのクラスタリングシステム。
【請求項２】
前記ブロック分割部は、
前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いることを特徴とする請求項１に記載のデータのクラスタリングシステム。
【請求項３】
前記簡易類似度計算部は、
精度は低くても計算負荷の少ない方法でデータの簡易類似度を計算し、
前記類似度計算部は、
計算負荷が高くても精度が高い方法でデータ間の類似度を計算することを特徴とする請求項１または２に記載のデータのクラスタリングシステム。
【請求項４】
前記ブロック統合部は、
グループの代表データを用いて前記類似度を計算させ、前記グループが統合できるかどうかを判断することを特徴とする請求項１、２または３に記載のデータのクラスタリングシステム。
【請求項５】
前記類似度計算部は、前記データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする請求項４に記載のデータのクラスタリングシステム。
【請求項６】
前記ブロック統合部は、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算部にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする請求項１、２、３、４または５に記載のデータのクラスタリングシステム。
【請求項７】
前記データは、データベースシステムのレコードであることを特徴とする請求項１、２、３、４、５または６に記載のデータのクラスタリングシステム。
【請求項８】
少なくとも一つのデータを含むブロックをブロック生成条件に基づいて分割する処理を繰り返してブロック間の階層関係を作成するステップと、
前記ブロック間の階層関係とブロックとを記憶するステップと、
ブロックに含まれるデータの組合せにかかる類似度を計算し、前記計算の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記記憶されたブロック間の階層関係に沿って実行するステップと、を有することを特徴とするデータのクラスタリング方法。
【請求項９】
前記ブロック間の階層関係を作成するステップは、
前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いることを特徴とする請求項８に記載のデータのクラスタリング方法。
【請求項１０】
前記ブロック間の階層関係を作成するステップは、精度は低くても計算負荷の少ない方法で得られる簡易類似度とブロック生成条件とによってブロックを分割し、
前記統合するステップは、計算負荷が高くても精度が高い方法で類似度を計算することを特徴とする請求項８または９に記載のデータのクラスタリングシステム。
【請求項１１】
前記統合するステップは、
グループの代表データを用いて前記類似度を計算し、前記グループが統合できるかどうかを判断することを特徴とする請求項８、９または１０に記載のデータのクラスタリング方法。
【請求項１２】
前記統合するステップは、データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする請求項１１に記載のデータのクラスタリング方法。
【請求項１３】
前記統合するステップは、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算部にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする請求項８、９、１０、１１または１２に記載のデータのクラスタリング。
【請求項１４】
前記データは、データベースシステムのレコードであることを特徴とする請求項８、９、１０、１１、１２または１３に記載のデータのクラスタリング方法。
【請求項１５】
少なくとも一つのデータを含むブロックとブロック生成条件とに基づいて前記ブロックを分割する簡易類似度計算処理と、前記簡易類似度計算処理にブロックとブロック生成条件とを渡して分割させる処理を繰り返すことによりブロック間の階層関係を作成するブロック分割処理と、前記ブロック間の階層関係とブロックとを記憶するブロック記憶処理と、データの組合せについての類似度を計算する類似度計算処理と、ブロックに含まれるデータの組合せにかかる類似度を前記類似度計算部に計算させ、前記類似度計算部の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記ブロック記憶部に記憶されたブロック間の階層関係に沿って実行するブロック統合処理と、をコンピュータに実行させるためのデータのクラスタリング用プログラム。
【請求項１６】
前記ブロック分割処理は、
前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いることを特徴とする請求項１５に記載のデータのクラスタリング用プログラム。
【請求項１７】
前記簡易類似度計算処理は、
精度は低くても計算負荷の少ない方法でデータの簡易類似度を計算し、
前記類似度計算処理は、
計算負荷が高くても精度が高い方法でデータ間の類似度を計算することを特徴とする請求項１５または１６に記載のデータのクラスタリングシステム。
【請求項１８】
前記ブロック統合処理は、
グループの代表データを用いて前記類似度を計算し、前記グループが統合できるかどうかを判断することを特徴とする請求項１５、１６または１７に記載のデータのクラスタリング用プログラム。
【請求項１９】
前記類似度計算処理は、前記データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする請求項１７に記載のデータのクラスタリング用プログラム。
【請求項２０】
前記ブロック統合処理は、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算処理にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする請求項１５、１６、１７、１８または１９に記載のデータのクラスタリング用プログラム。
【請求項２１】
前記データは、データベースシステムのレコードであることを特徴とする請求項１５、１６、１７、１８、１９または２０に記載のデータのクラスタリング用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データのクラスタリング装置、クラスタリング方法及びクラスタリング用プログラムに関する。
【背景技術】
【０００２】
複数のデータをある基準によって分類するクラスタリング方式および装置において、以下では、実質的に同じデータをグルーピングすることを重複レコード照合と呼ぶ。実質的に同じとは、例えば、「NEC」と「エヌイーシー」、「一丁目二番地」と「１−２」のような表記のゆれなどによって、データとして完全に一致しなくても人が見れば同じと判断できるものを指すものとする。単一データベース内のレコードの重複や、複数データベース間でのレコードの重複を調べる場合に、厳密に全ての組合せを調べるとすれば、レコード数の増加につれて組合せ爆発が起こり、膨大な時間がかかってしまう。【０００３】
従来は、精度は落ちるが処理の軽い手法（おおよその絞込み）と、処理は重いが精度が良い手法（詳細な絞込み）を組み合わせることによって重複レコードの照合を行っていた。【０００４】
例えば、10万件のレコードの重複を調べる場合には、おおよその絞込みによって、例えば数千件から数万件程度のレコードをブロックにしたものを大量に作り、ブロックの中で詳細な絞込みを行い、重複レコードの照合を行う。【０００５】
おおよその絞込みを行うための技術としては、例えば、非特許文献１に記載されているSorted Neighborhood Method等がある。【０００６】
詳細な絞込みを行う技術として、非特許文献２に記載の編集距離を用いる方法等がある。編集距離は文字列間の類似を測るためのもので、類似の技術として編集距離の他に音声距離、入力（タイプライター）距離などがある。【０００７】
詳細な絞込みでは、例えば、レコード間の類似度や距離を計算し、ある閾値を設定することでレコードをグルーピングする。グループ化されたレコード群は、重複レコード候補として人が判断する場合もあるし、グループ化されたレコード群をそのまま重複レコードとみなすこともある。おおよその絞込みと詳細な絞込みを組み合わせることにより、重複レコード照合処理の効率化を図っていた。【０００８】
【非特許文献１】M.A.Hernandez、他１名、Real-world Data is Dirty: Data Cleansing and the Merge/Purge Problem、Journal of Data Mining and Knowledge Discovery、第１巻、1998年
【０００９】
【非特許文献２】M.Hernandez、他１名、The Merge/Purge Problem for Large Databeses、Proceedings of the 1995 ACM SIGMOD International Conference of DATA (SIGMOD 1995)、1995年、１２７〜１３８頁
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、おおよその絞込みは処理が速いが精度が低く、詳細な絞込みは精度は高いが処理が遅いという傾向がある。したがって、照合対象レコード数が増加するにつれて、処理時間の増加を抑えるためにはおおよその絞込みにおいてより多くのレコードを絞り込む必要があり、精度が低下してしまう。また、精度を維持するためには、おおよその絞込みであまり多くのレコードを絞り込むことができず、処理時間の増大を招いてしまう。【００１１】
すなわち、第一の問題点は、照合対象レコード数が増加するにつれて、精度を維持しつつ速度低下を抑えることが困難であるという点である。【００１２】
第二の問題点は、おおよその絞込みにおいて、絞込みのための閾値を適切に決定することが難しく、試行錯誤が必要であったという点である。その理由は、おおよその絞込みの閾値が小さすぎれば、その後の詳細な絞込みにおいて多くの組合せを調べなければならず、おおよその絞込みの効果が少なくなり、また、おおよその絞込みの閾値が大きすぎれば、詳細に調べれば同じグループと判断されるはずのレコードがおおよその絞込みの段階で除かれてしまうからである。【００１３】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、照合対象レコード数が増大した場合であっても精度を維持しつつ速度低下を抑えることにある。【００１４】
また、本発明の他の目的は、おおよその絞込みにおける閾値を決定するための試行錯誤を不要にすることにある。
【課題を解決するための手段】
【００１５】
上記課題を解決する第１の発明は、データのクラスタリングシステムであって、少なくとも一つのデータを含むブロックとブロック生成条件とを受け取って前記ブロック生成条件に基づいて前記ブロックを分割する簡易類似度計算部と、前記簡易類似度計算部にブロックとブロック生成条件とを渡して分割させる処理を繰り返すことによりブロック間の階層関係を作成するブロック分割部と、前記ブロック間の階層関係とブロックとを記憶するブロック記憶部と、データの組合せについての類似度を計算する類似度計算部と、ブロックに含まれるデータの組合せにかかる類似度を前記類似度計算部に計算させ、前記類似度計算部の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記ブロック記憶部に記憶されたブロック間の階層関係に沿って実行するブロック統合部と、を有することを特徴とする。【００１６】
上記課題を解決する第２の発明は、上記第１の発明において、前記ブロック分割部は、前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いることを特徴とする。【００１７】
上記課題を解決する第３の発明は、上記第１または第２の発明において、前記簡易類似度計算部は、精度は低くても計算負荷の少ない方法でデータの簡易類似度を計算し、前記類似度計算部は、計算負荷が高くても精度が高い方法でデータ間の類似度を計算することを特徴とする。【００１８】
上記課題を解決する第４の発明は、上記第１、第２または第３の発明において、前記ブロック統合部は、グループの代表データを用いて前記類似度を計算させ、前記グループが統合できるかどうかを判断することを特徴とする。【００１９】
上記課題を解決する第５の発明は、上記第４の発明において、前記類似度計算部は、前記データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする。【００２０】
上記課題を解決する第６の発明は、上記第１、第２、第３、第４または第５の発明において、前記ブロック統合部は、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算部にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする。【００２１】
上記課題を解決する第７の発明は、上記第１、第２、第３、第４、第５または第６の発明において、前記データは、データベースシステムのレコードであることを特徴とする。【００２２】
上記課題を解決する第８の発明は、データのクラスタリング方法であって、少なくとも一つのデータを含むブロックをブロック生成条件に基づいて分割する処理を繰り返してブロック間の階層関係を作成するステップと、前記ブロック間の階層関係とブロックとを記憶するステップと、ブロックに含まれるデータの組合せにかかる類似度を計算し、前記計算の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記記憶されたブロック間の階層関係に沿って実行するステップと、を有することを特徴とする。【００２３】
上記課題を解決する第９の発明は、上記第８の発明において、前記ブロック間の階層関係を作成するステップは、前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いることを特徴とする。【００２４】
上記課題を解決する第１０の発明は、上記第８または第９の発明において、精度は低くても計算負荷の少ない方法で得られる簡易類似度とブロック生成条件とによってブロックを分割し、前記統合するステップは、計算負荷が高くても精度が高い方法で類似度を計算することを特徴とする。【００２５】
上記課題を解決する第１１の発明は、上記第８、第９または第１０の発明において、前記統合するステップは、グループの代表データを用いて前記類似度を計算し、前記グループが統合できるかどうかを判断することを特徴とする。【００２６】
上記課題を解決する第１２の発明は、上記第１１の発明において、前記統合するステップは、データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする。【００２７】
上記課題を解決する第１３の発明は、上記第８、第９、第１０、第１１または第１２の発明において、前記統合するステップは、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算部にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする。【００２８】
上記課題を解決する第１４の発明は、上記第８、第９、第１０、第１１、第１２または第１３の発明において、前記データは、データベースシステムのレコードであることを特徴とする。【００２９】
上記課題を解決する第１５の発明は、データのクラスタリング用プログラムであって、少なくとも一つのデータを含むブロックとブロック生成条件とに基づいて前記ブロックを分割する簡易類似度計算処理と、前記簡易類似度計算処理にブロックとブロック生成条件とを渡して分割させる処理を繰り返すことによりブロック間の階層関係を作成するブロック分割処理と、前記ブロック間の階層関係とブロックとを記憶するブロック記憶処理と、データの組合せについての類似度を計算する類似度計算処理と、ブロックに含まれるデータの組合せにかかる類似度を前記類似度計算部に計算させ、前記類似度計算部の結果に基づいて少なくとも一つのデータを含むグループを統合する処理を前記ブロック記憶部に記憶されたブロック間の階層関係に沿って実行するブロック統合処理と、をコンピュータに実行させることを特徴とする。【００３０】
上記課題を解決する第１６の発明は、上記第１５の発明において、前記ブロック分割処理は、前記分割させる処理を繰り返すとき、新たなブロック生成条件として前記ブロック条件よりも厳しいブロック生成条件を用いる、ことを特徴とする。【００３１】
上記課題を解決する第１７の発明は、上記第１５または第１６の発明において、前記簡易類似度計算処理は、精度は低くても計算負荷の少ない方法でデータの簡易類似度を計算し、前記類似度計算処理は、計算負荷が高くても精度が高い方法でデータ間の類似度を計算することを特徴とする。【００３２】
上記課題を解決する第１８の発明は、上記第１５、第１６または第１７の発明において、前記ブロック統合処理は、グループの代表データを用いて前記類似度を計算し、前記グループが統合できるかどうかを判断することを特徴とする。【００３３】
上記課題を解決する第１９の発明は、上記第１７の発明において、前記類似度計算処理は、前記データの組合せにかかる類似度に基づいて、統合可能、統合不可または継続調査と判定し、継続調査と判定したときであってかつ前記データが代表データであるときは前記代表データを含むグループに含まれる他のデータとの組合せについて改めて類似度を計算し、統合可能または統合不可と判定することを特徴とする。【００３４】
上記課題を解決する第２０の発明は、上記第１５、第１６、第１７、第１８または第１９の発明において、前記ブロック統合処理は、前記ブロック間の階層関係に沿ってブロックを移るときにデータが一つだけのグループにチェック済マークを付加し、前記類似度計算処理にブロックに含まれるデータの組合せにかかる類似度を計算させるときにチェック済マークが付加されているグループの代表データを用いないことを特徴とする。【００３５】
上記課題を解決する第２１の発明は、上記第１５、第１６、第１７、第１８、第１９または第２０の発明において、前記データは、データベースシステムのレコードであることを特徴とする。【００３６】
このような構成を採用し、条件を段階的に厳しくしながらデータを小さいブロックに分割し、その後、統合の可否を判断しながら統合していくので、統合される可能性の高い組合せから順に調べていくことになり、精度を維持しつつ調べる組合せの数を減らすことができ、本発明の第一及び第二の目的を達成することができる。
【発明の効果】
【００３７】
第一の効果は、精度を維持しつつ速度低下を抑えることができることである。条件を段階的に厳しくしながらデータを小さいブロックに分割し、分割されたのと逆の順序で分割されたブロック同士を統合できるか判断しながら統合していくので、統合される可能性の高い組合せから順に調べていくことになり、精度を維持しつつ調べる組合せの数を減らすことができるからである。【００３８】
第二の効果は、クラスタリングのためのパラメータをあまり試行錯誤しなくても済むことである。条件を段階的に厳しくしながらデータを小さいブロックに分割し、分割されたのと逆の順序で統合できるか判断しながら統合していくので、従来の手法のようにおおよその絞込みでどれだけ条件を厳しくしなければならないかを最初に決める必要がなくなるからである。
【図面の簡単な説明】
【００３９】
【図１】本発明の第一の実施の形態の機能構成を示すブロック図である。
【図２】ブロック分割部の分割により生じる階層関係の一例を示す図である。
【図３】ブロック、グループ及びデータの関係の一例を示す図である。
【図４】ブロック、グループ及びデータの関係の一例を示す図である。
【図５】第一の実施の形態の動作を表すフローチャートの一例を示す図である。
【図６】第一の実施の形態のブロック分割部３の動作を表すフローチャートの一例を示す図である。
【図７】第一の実施の形態のブロック統合部５の動作を表すフローチャートの一例を示す図である。
【図８】第一の実施の形態の類似度計算部６の動作を表すフローチャートの一例を示す図である。
【図９】本発明の第二の実施の形態の機能構成を示すブロック図である。
【図１０】第二の実施の形態のブロック統合部５の動作を表すフローチャートの一例を示す図である。
【図１１】データベースに登録されているデータの一例を示す図である。
【図１２】本発明による動作のフローチャートの一例を示す図である。
【図１３】ブロック分割部で分割されたデータの一例を示す図である。
【図１４】ブロック分割部で分割されたデータの一例を示す図である。
【図１５】ブロック分割部でデータをどう分割していったかを保持するデータの一例を示す図である。
【図１６】ブロック統合部で分割されたデータがどう統合されるかの一例を示す図である。
【図１７】ブロック統合部で分割されたデータがどう統合されるかの一例を示す図である。
【図１８】ブロック統合部で分割されたデータがどう統合されるかの一例を示す図である。
【符号の説明】
【００４０】
１  データベース
２  ＤＢアクセス部
３  ブロック分割部
４  簡易類似度計算部
５  ブロック統合部
６  類似度計算部
７  プログラム記憶媒体
【発明を実施するための最良の形態】
【００４１】
［第一の実施の形態］
本発明を実施するための第一の実施の形態について、図面を参照して詳細に説明する。【００４２】
以下では、データベースをＤＢと略する場合がある。【００４３】
図１は、本発明を実施するための最良の形態に関するブロック図である。本発明を実施するための最良の形態によるクラスタリング装置は、ＤＢアクセス部２、ブロック分割部３、簡易類似度計算部４、ブロック統合部５、類似度計算部６及びブロック記憶部８を有する。【００４４】
対象データベース１は、いわゆるデータベースであり、複数のデータが記憶されている。単一のデータベースであっても、複数のデータベースを仮想的にマージしたデータベースであってもよい。【００４５】
ＤＢアクセス部２は、対象データベース１とデータの入出力を行う。対象データベース１からデータを読み込んだときは、読み込んだデータを一つのブロックにまとめブロック分割部３に提供する。一つのブロックは、一つ以上のデータを含むものである。また、ＤＢアクセス部２は、後述するブロック統合部５から情報が提供されたときは、対象データベース１に書き込む動作を行う。【００４６】
ここで、ブロックについて説明する。本発明では、一つ以上のデータを含むものとしてブロックとグループを用いる。グループは、後述するブロック統合部５及び類似度計算部６の処理によって作成されるもので、一つ以上のデータを含むものである。グループに含まれるデータの内一つは代表データとされる。また、ブロックは、一つ以上のデータ、一つ以上のグループ又はそれらの組合せとして構成されるものである。【００４７】
ブロック分割部３は、ＤＢアクセス部２から提供されたブロックを、それぞれのブロックが充分に小さくなるまで分割してゆく。ブロックの分割は、簡易類似度計算部４にブロックとブロック生成条件とを渡すことにより行われる。簡易類似度計算部４は、ブロックとブロック生成条件とを受け取ると、ブロックを構成しブロック分割部３に返却する（後述）。ブロック分割部３は、返却されたブロックのそれぞれを調べ、それらが充分に小さくないときは、ブロック生成条件を一段階厳しくし、そのブロックと新たなブロック生成条件とを類似度計算部４に渡し、再び分割を行う。【００４８】
ブロックが充分に小さいかどうかを判断するために、例えば、ブロックに属するデータ数を用いることができる。例えば、ブロックに属するデータ数が２０件以上ならばブロックは充分に小さくないと判断する等である。また、この判断は、データの全件数に対する割合で行ってもよい。例えば、ブロックのデータ件数が全件数の１％以上ならば分割する等である。また、これらに限定されるものではない。さらに、この判断基準は、ユーザが入力してもよいし、設定ファイルから読み込んでもよいし、あらかじめ決められているものとしてもよい。【００４９】
ブロック生成条件は、簡易類似度の計算方法に応じて適宜指定するものである。例えば、簡易類似度を数値として算出する計算方法を用いる場合は、ブロック生成条件として一定の閾値を与え、閾値を越えるデータ同士を同じブロックに纏めるようにすることができる。この場合、ブロック生成条件を一段階厳しくするには、閾値として一段階大きな値を用いることとなる。【００５０】
簡易類似度計算部４は、ブロック分割部３からブロックとブロック生成条件とを受取って、ブロックに含まれるデータ同士の簡易類似度を計算し、計算結果とブロック生成条件に基づいてブロックを構成し、ブロック分割部３に返却する。ここで、簡易類似度計算部４は、おおよその絞込み、すなわち、速度が速く精度が低い方法を用いて簡易類似度を計算する。簡易類似度の計算には従来の方法を用いることができる。【００５１】
そして、ブロック分割部３は、分割の結果として生じる階層関係とブロックとをブロック記憶部８に記憶させる。図２に、分割の過程で生じる階層関係の一例を示す。ブロック分割部３は、ブロックが充分に小さくなるまでブロック生成条件を段階的に厳しくしながら分割を繰り返すので、階層の深いほど分割されたときのブロック生成条件が厳しくなっている。【００５２】
ブロック統合部５及び類似度計算部６の詳細を説明する前に、これらの処理に用いられるグループについて説明する。前述の通り、グループは一つ以上のデータを含むものである。また、グループに含まれるデータの一つはそのグループの代表データとなる。【００５３】
代表データの選び方は様々な方法を用いることができる。例えば、グループのデータを何らかのキーでソートして中央のデータを選ぶという方法でもよいし、先頭のデータを選ぶのでもよい。データが１件しかないグループはそのデータが代表データとなる。また、代表データの選択をグループの構成と同時に行わずに、計算のために代表データが必要となるときに行うこととしても良い。【００５４】
ブロック統合部５は、ブロック記憶部８に記憶されたブロックの階層関係に基づきながら、階層の深い位置から浅い位置へとブロック及びグループを統合する。【００５５】
ここで、ブロック統合部５は、ブロックに含まれるグループが統合できるかどうかを調べるために、それらのグループの代表データの組合せを類似度計算部６に渡す。類似度計算部６は、データの組合せについて類似度を計算し、それらが統合できるときは「統合可能」、統合できないときは「統合不可」のようにブロック統合部５に返却する。ブロック統合部５は、類似度計算部６から結果を受取ると、「統合可能」と示されたデータの組合せに係るグループを統合する。【００５６】
ブロック統合部５によるブロックの統合の一例について、図３及び図４を用いて説明する。図３には、ブロックＢ３００がグループＧ３０１とグループＧ３０２とを要素にもち、ブロックＢ３０１がグループＧ３０３とグループＧ３０４とを要素にもつという、ブロック、グループ及びデータの関係の一例を示している。また、ブロックＢ３００及びブロックＢ３０１は、共にブロックＢ２００を親としている。ブロック統合部５は、Ｂ３００及びＢ３０１におけるグループの構成が終了すると、Ｂ３００及びＢ３０１を統合し、Ｂ２００での処理に移る。Ｂ３００又はＢ３０１に属するグループＧ３０１及びＧ３０２又はＧ３０３及びＧ３０４は、Ｂ２００へと纏められる（図４）。その後、グループ統合部５はＢ２００におけるグループの構成を行うため、Ｇ３０１、Ｇ３０２、Ｇ３０３及びＧ３０４の代表データの組合せを類似度計算部６へと渡す。【００５７】
類似度計算部６は、ブロック統合部５からデータの組合せについて受け取って、類似度を計算し、その組合せに係るデータが統合できるかどうかを判断し、統合できるときは「統合可能」、統合できないときは「統合不可」のようにブロック統合部５に応答する。ここで、類似度計算部６は詳細な絞込み、すなわち、精度が高く処理が遅いという方法を用いて類似度を計算する。類似度の計算は従来の方法を用いることができる。例えば、編集距離を用いる等である。類似度計算部６の動作については後に説明する。【００５８】
統合すべきブロックがなくなると、ブロック統合部５は処理を終了する。このとき、類似するデータはグループに纏められているので、これらをクラスタとする。【００５９】
ブロック記憶部８は、ブロック分割部３から提供される、分割されたブロックとそれらの階層関係を記憶する。また、ブロック統合部５は、記憶された階層関係を参照して処理を行い、ブロック統合時にはブロック間の階層関係を適宜修正する。【００６０】
次に、第一の実施の形態の動作について詳細に説明する。【００６１】
図５は、第一の実施の形態の動作を表すフローチャートである。ＤＢアクセス部２によって読み込まれたデータの全体はブロック分割部３によって分割され、ブロック間の階層関係と共にブロック記憶部８に記憶される（ステップＳ１）。その後、ブロック統合部５は、ブロック記憶部８に記憶された階層関係を参照しながら、ブロック及びデータを統合する（ステップＳ２）。【００６２】
次に、図６を用いて、ブロック分割部３の動作について説明する。ブロック分割部３は、簡易類似度計算部４にブロックとブロック生成条件とを指定してブロックを分割させる（ステップＫ１）。簡易類似度計算部４は、供給されたブロックから、ブロック生成条件に基づいて、一つ以上のブロックを構成し、ブロック分割部３へ返却する（ステップＫ２）。簡易類似度計算部４の動作については後に説明する。【００６３】
ブロック分割部３は、簡易類似度計算部４から返却された各ブロックを調査し、ブロックが分割されたか確認する（ステップＫ３）。ブロックが分割されているときは、返却されたブロックの大きさをそれぞれ確認する（ステップＫ４）。返却されたブロックが大きいときはブロック生成条件を一段階厳しくし（ステップＫ５）、そのブロックと新たなブロック生成条件とを簡易類似度計算部４に再び渡す（ステップＫ１）。ブロック分割部３は、簡易類似度計算部４から返却されるブロックが充分に小さくなるまで上記の動作を繰り返す。ブロックが充分に小さいときは、もとのブロックがどのように分割されたかという情報をブロックの階層関係として記憶する（ステップＫ７）とともに、次のブロックへと処理を移す（ステップＫ９）。分割すべきブロックがなくなると、ブロック分割部３の処理は終了する（ステップＫ１０）。【００６４】
次に、簡易類似度計算部４の動作について説明する。簡易類似度計算部４は、ブロック生成条件に基づいて、供給されたブロックに属するデータからブロックを構成する。例えば、ブロック生成条件に示されたデータとの簡易類似度が閾値を超えるデータ群を一つのブロックに纏める等である。或いは、ブロック生成条件を満たすデータ群が同じブロックに属するようにブロックを構成してもよい。或いは、ブロック生成条件を満たすデータを供給されたブロックに属するデータから検索して構成してもよい。この時、新たなブロックが必要となる場合は新たなブロックを構成する。なお、簡易類似度計算部４は、一つのデータが複数のブロックに属するようにブロックを構成して良い。【００６５】
以上のように、ブロック分割部３及び簡易類似度計算部４によって、たとえば図２に示すようなブロックの階層関係が構成される。ブロック分割部３は、このブロックの階層関係とブロックとをブロック記憶部８に記憶させる。ブロック統合部５及び類似度計算部６は、この階層関係に基づき、階層の深いブロックに属するデータから順番にデータ同士をグループとして構成する。【００６６】
図７は、ブロック統合部５の動作を表すフローチャートである。ブロック統合部５は、処理対象のブロックに属するデータ同士の組合せを類似度計算部６に渡す（ステップＴ１）。該ブロックにグループが属しているときは、そのグループに属するデータの代表として代表データを用いる。例えば、図４に例示するブロックＢ２００については、Ｇ３０１、Ｇ３０２、Ｇ３０３、Ｇ３０４のそれぞれの代表データ同士の組合せである６通りの組合せを類似度計算部６に渡す。【００６７】
類似度計算部６は、ブロック統合部５からデータの組合せの集合を受け取ると、それぞれについて、類似度を計算して統合可能であるか統合不可であるかを返却する。【００６８】
ブロック統合部５は、類似度計算部６からの結果を調べ（ステップＴ２）、結果に基づいてグループを構成する。すなわち、「統合可能」であるときはグループ同士を纏める（ステップＴ３）。【００６９】
ブロック統合部５は、処理対象のブロックについてのグループの構成が終了すると、ブロックを統合する（ステップＴ４）。そして、次のブロックへと処理を移す（ステップＴ７）。ここで、ブロック統合部５はブロック記憶部８に記憶された図２のようなブロック間の階層関係に基づき、深い階層から浅い階層へとブロックを処理する。ブロックの階層がなくなるとブロック統合部５は処理を終了する（ステップＴ６）。【００７０】
ブロック統合部５は、処理を終了すると、グループの構成結果をＤＢアクセス部２に渡す。ＤＢアクセス部２は、受取った結果をデータベース１に登録する。【００７１】
類似度計算部６の動作の一例は、図８のようである。類似度計算部６は、ブロック統合部５からデータの組合せの集合を取得すると、それぞれの類似度を計算する（ステップＪ１）。類似度計算部６は、計算された類似度を「統合可能」、「継続調査」または「統合不可」に分類する（ステップＪ２）。【００７２】
類似度計算部６は、「継続調査」と分類したデータの組合せがあるときは、その組合せの要素が代表データかどうかを調査する（ステップＪ３）。代表データであるときは、その代表データを含むグループが統合可能であるか否かをより詳細に調査する（ステップＪ４）。すなわち、そのグループに含まれる全データの組合せについて類似度を計算する。そして、結果について再び分類する（ステップＪ７）。このようにして、類似度計算部６は、代表データを含むグループ同士が「統合可能」であるか「統合不可」であるかを算出し、ブロック統合部５へと返却する（ステップＪ５、Ｊ６）。【００７３】
第一の実施の形態におけるブロック記憶部８は、例えば、半導体メモリによって実現される。ＤＢアクセス部２、ブロック分割部３、簡易類似度計算部４、ブロック統合部５、類似度計算部６は、それぞれの機能を有するハードウェアによって実現してもよい。あるいは、データクラスタリング用プログラムに従って動作するコンピュータによって、ＤＢアクセス部２、ブロック分割部３、簡易類似度計算部４、ブロック統合部５、類似度計算部６を実現してもよい。例えば、データクラスタリング用プログラムが磁気ディスクや半導体メモリ等のコンピュータ可読媒体によって提供され、コンピュータの立ち上げ時等にコンピュータに読み取られ、コンピュータがデータクラスタリング用プログラムに従って動作することで、ＤＢアクセス部２、ブロック分割部３、簡易類似度計算部４、ブロック統合部５、類似度計算部６として機能してもよい。【００７４】
以上のように、第一の実施の形態によれば、ブロック分割部３がブロック生成条件を段階的に厳しくしながらブロックを階層的に分割し、ブロック統合部５がブロックの階層を深い方から浅い方へ処理しながら、グループ同士の統合の可否を判断しながら統合していく。その統合の際には、詳細な調査が必要なときにのみグループに含まれるデータ同士について類似度を計算する。よって、統合される可能性の高い組合せから順に調べてゆくこととなるし、詳細な調査が不要なものについては計算を省略できる。従って、クラスタリングの精度を維持しつつ、組合せの数を減らすことができる。【００７５】
従来は、おおよその絞込みと詳細な絞込みとを組み合わせて用いる際には、おおよその絞込みにおいて絞込みのための閾値を決定することが難しく試行錯誤が必要であった。それに対し、本発明では、ブロック生成条件を段階的厳しくしながら分割したブロックの階層にもとづいてグループ同士の統合の可否を判断しながら統合してゆくので、おおよその絞込みにおいて絞込みのための閾値について試行錯誤を行わなくて良い。【００７６】
また、ブロック統合部５において、「継続調査」と分類された組合せについて詳細な調査をするときに、二つのグループ間の全データの組合せを調べるのでなく、類似度閾値を超える組合せがあればそれ以上調べないことにして良い。グループ内の組合せでは類似度の値が大きいことを期待できるので、全データの組合せではなく、一方の代表データと他方の全データとの組合せを相互に調べるようにしても良い。このような方法によれば、類似度を計算する組合せの数をさらに減らすことができ、処理速度の低下を抑えることができる。【００７７】
［第二の実施の形態］
図９は、本発明の第二の実施の形態を示すブロック図である。第一の実施の形態と同様の構成部については、図１と同一の符号を付し、説明を省略する。第二の実施の形態では、図１に例示する第一の実施の形態の構成と比較すると、ブロック統合部５がブロック統合部５００となっている点で、第一の実施の形態と異なる。【００７８】
第二の実施の形態におけるグループは、「チェック済マーク」を付加できる点で、第一の実施の形態におけるグループと異なる。「チェック済マーク」は、グループが新たに構成されたときは付加されないが、ブロック統合部５００の処理の過程で付加されるものである。【００７９】
図１０を用いて、ブロック統合部５００の動作について説明する。ブロック統合部５００は、ステップＭ１及びステップＭ４において「チェック済マーク」を利用する点が、第一の実施の形態と大きく異なる。すなわち、ブロック統合部５００は、ブロックを統合してブロックの階層を移動する際に、ブロックに属するグループのデータの件数を調べ、データの件数が１つだけのグループには「チェック済マーク」を付加する。その後、ブロック統合部５００がデータの組合せについて類似度を調べるときに、「チェック済マーク」がついているグループの組合せについては類似度の調査を行わない（ステップＭ１）。【００８０】
本発明の第二の実施の形態によれば、ブロック統合部５００は、ブロックの統合を進める際にデータが１件のままのグループに関しては「チェック済マーク」を付加し、他の代表データとの組合せを調べないとしている。ブロックの階層が浅くなるに従って、ブロック分割部３における分割条件は緩やかになるから、ブロックの統合時に新たに組合せ先となるデータは類似度が低いものである。したがって、ブロックの統合を進める際に、新たに組合せ先となるデータとの類似度の調査を省略しても、クラスタリングの精度は落ちず、類似度を調べる組合せをさらに大幅に減らすことができ、処理時間を短縮できる。【００８１】
また、「チェック済マーク」を付加する対象は、１階層以上統合されなかったものである必要は無く、２階層以上や３階層以上であっても良い。さらに、予め決められていなくとも良く、ユーザが入力しても良いし、設定ファイルから読み込んでも良い。
【実施例】
【００８２】
次に、本発明の第一の実施例を、図面を参照して説明する。かかる実施例は本発明の第一の実施の形態に対応するものである。【００８３】
本実施例では、データは図１１に示すようなデータベースに記憶されている。図１１に示したデータベースは、ID、名称、住所の３つのフィールドを持つデータベースであり、１０００件のレコードが登録されているものとする。重複レコードのクラスタリングの処理は、図１２に示すような手順で行われる。【００８４】
本実施例の簡易類似度計算部４は、「名称」と「住所」のフィールドを使用して簡易類似度を計算する。しかしながら、簡易類似度を計算するために、どのデータベースのどのフィールドを使用するかは、ユーザが入力してもよいし、設定ファイルから読み込んでもよいことは言うまでもない。同様に、全フィールドを使用するようにしてもよいし、例えば「名称」「住所」「電話番号」などあらかじめ決められたフィールドだけを使用するようにしてもよい。【００８５】
また、簡易類似度計算部４における簡易類似度計算の方法として従来の方法を用いてもよいことは第一の実施の形態で説明したとおりである。本実施例では、あるフィールドの先頭から何文字かが一致するレコードをブロックにするという方法を用いる。例えば、名称フィールドの先頭１文字が一致するブロック、住所フィールドの先頭１文字が一致するブロックなどである。一つのレコードが別々の複数のブロックに含まれても良い。【００８６】
DBアクセス部２は、例えば図１１に示すようなデータベースをデータベース１から読み込み、１つのブロックとしてブロック分割部３に渡す。ブロック分割部３は、受け取ったブロックとブロック生成条件とを簡易類似度計算部４に渡し、簡易類似度計算部４は生成しブロックをブロック分割部３に返す。【００８７】
本実施例におけるブロック生成条件とは、例えば、「名称フィールドの先頭１文字が一致」や「住所フィールドの先頭１文字が一致」などである。簡易類似度計算の方法が異なれば、ブロック生成条件として別の与え方をしてもよい。【００８８】
本実施例の簡易類似度計算部４は、図１３に例示するように、「「名称」の先頭１文字が「A」のブロック」、「「名称」の先頭１文字が「D」のブロック」、「「住所」の先頭１文字が「大」のブロック」などのようなブロックを生成し、ブロック分割部３に返す。【００８９】
ブロック分割部３は、簡易類似度計算部４から返されたブロックが充分に小さいかどうかを調べる。本実施例では、「ブロックのレコード数が１００件以上」ならばさらにブロックを分割するものとして説明する。すなわち、本実施例において、ブロック分割部３は、簡易類似度計算部４から返された各ブロックの件数を調べ、１００件以上ならば、そのブロックと、一段階厳しくしたブロック生成条件とを再び簡易類似度計算部４に渡し、簡易類似度計算部４は渡されたブロックを分割したブロックをブロック分割部３に返す。一段階厳しくしたブロック生成条件とは、この場合は例えば、「そのフィールドの先頭２文字が一致」「別のフィールドの先頭１文字が一致」などである。条件をどのように厳しくしていくかは、ユーザが入力してもよいし、設定ファイルから読み込んでもよいし、あらかじめ決められているものとしてもよい。【００９０】
また、条件を一段階厳しくしてもブロックが分割されない場合は、さらに条件を厳しくして分割を試みる。もし、条件を厳しくしてもそれ以上分割できない場合は、簡易類似度計算部４は分割できないことをブロック分割部３に通知することで、ブロック分割部３がそれ以上そのブロックを分割しないようにする。条件を厳しくしてもそれ以上分割できない場合とは、例えば、「そのフィールドの値が完全一致」「全フィールドの値が完全一致」等の場合である。【００９１】
例えば、図１３に示された「「住所」の先頭１文字が「大」のブロック」のレコード件数が１１１件であるとする。ブロック分割部３は、「「住所」の先頭１文字が「大」のブロック」と「「住所」の先頭２文字が一致」というブロック生成条件を簡易類似度計算部４に渡し、簡易類似度計算部４は渡されたブロックを分割したブロックをブロック分割部３に返す。もし「「住所」の先頭２文字が一致」というブロック生成条件では、ブロックが分割されずに、ブロックの全レコードが同じブロックになる場合には「「住所」の先頭３文字が一致」、「「住所」の先頭４文字が一致」というようにブロック生成条件を段階的に厳しくして分割する。例えば、「「住所」の先頭２文字が一致」というブロック生成条件で分割した場合には、「「住所」の先頭２文字が「大阪」のブロック」１１０件と、「「住所」の先頭２文字が「大東」のブロック」１件に分割されたとする。「「住所」の先頭２文字が「大阪」のブロック」１１０件は１００件以上なので、再び分割される。例えば、「「住所」の先頭３文字が一致」というブロック生成条件で分割した場合には、「「住所」の先頭３文字が「大阪府」のブロック」１０１件と、「「住所」の先頭３文字が「大阪市」のブロック」９件に分割されたとする。「「住所」の先頭３文字が「大阪府」のブロック」１０１件は１００件以上なので、再び分割される。例えば、「「住所」の先頭４文字が一致」というブロック生成条件で分割した場合に分割できなければ、「「住所」の先頭５文字が一致」というブロック生成条件で試みる。「「住所」の先頭３文字が「大阪府」のブロック」１０１件は、「「住所」の先頭４文字が「大阪府大」のブロック」９０件（大阪府大阪市などのデータ）と、「「住所」の先頭４文字が「大阪府守口市」のブロック」１１件（大阪府守口市などのデータ）に分割されたとする。このようにして、「「住所」の先頭１文字が「大」のブロック」１１１件が、例えば図１４のように、「「住所」の先頭４文字が「大阪府大」のブロック」９０件、「「住所」の先頭４文字が「大阪府守」のブロック」１１件、「「住所」の先頭３文字が「大阪市」のブロック」９件、「「住所」の先頭２文字が「大東」のブロック」１件に分割される。【００９２】
ブロック分割部３は、ブロックがどのように分割されていったかという情報をブロック間の階層関係として、ブロック記憶部８に記憶させる。例えば、図１５のように木構造で保持するようにする。この木構造の各要素は、それぞれその要素のブロックに含まれるレコードが何であるかを記憶する。このようなブロック記憶部８は、例えば、半導体メモリとして実現される。【００９３】
ブロック分割部３によるブロックの分割が終わると、ブロック統合部５は処理を開始する。ブロック統合部５は、ブロック記憶部８に記憶されたブロックに属するレコードの組合せを類似度計算部６に渡し、類似度計算部６は受け取ったレコード間の類似度を計算し、類似度が閾値以上ならそれらのレコードが同じグループになると応答する。【００９４】
類似度の計算は、従来、編集距離を用いるものなど様々な方法が知られており、それらの方法のいずれかを用いて同様に計算するものとする。類似度の閾値は、ユーザが入力してもよいし、設定ファイルから読み込んでもよいし、あらかじめ決められているものとしてもよい。一度類似度の計算を行ったレコードの組合せに関しては、その類似度の値、または類似度が閾値を超えないという情報を記録しておき、同じ計算を行わなくて済むようにする。【００９５】
ここでは例えば、IDが００１のレコードと００２のレコードの類似度が閾値以上であり、００２のレコードと００３のレコードの類似度が閾値以上であれば、００１のレコードと００３のレコードの類似度が閾値以下であっても、００１と００２と００３のレコードは同一グループとなるものとする。【００９６】
以下、説明を簡単にするため、図１５に例示する木構造における「「住所」の先頭１文字が「大」のブロック」に含まれるグループに絞って詳細に説明する。「「住所」の先頭４文字が「大阪府大」のブロック」のレコード９０件に、説明のため仮に１〜９０の番号を振ったとし、「「住所」の先頭４文字が「大阪府守」のブロック」１１件に９１〜１０１の番号を、「「住所」の先頭３文字が「大阪市」のブロック」９件に１０２〜１１０の番号を、「「住所」の先頭２文字が「大東」のブロック」１件に１１１の番号を振ったとする（これらのブロックについては図１４を参照されたい）。【００９７】
ここで、「「住所」の先頭４文字が「大阪府大」のブロック」における処理に着目して説明するが、１〜７０までが同じグループにできるとする。同様に「「住所」の先頭４文字が「大阪府守」のブロック」において、９１〜９５までが同じグループにできるとし、それ以外はそれぞれ１件ずつのグループになるとする。【００９８】
「「住所」の先頭４文字が「大阪府大」のブロック」においてブロック統合部５は、１と２、２と３のように１〜９０までのレコードの組合せを類似度計算部６に渡し、類似度を計算させる。類似度計算部６は、ブロック統合部５に、受け取ったレコード同士が同じグループになるかどうかという情報を返す。例えば、「「住所」の先頭４文字が「大阪府大」のブロック」に関しては、１と２が同じグループになり、２と３が同じグループになり、というように１〜７０のレコードの組合せについて同じグループになるという情報が返される。同様に、「「住所」の先頭４文字が「大阪府守」のブロック」に関しては、９１と９２が同じグループになり、９２と９３が同じグループになり、というように９１〜９５のレコードの組合せについて同じグループになるという情報が返される。ブロック統合部５は、このような情報を得て、「「住所」の先頭４文字が「大阪府大」のブロック」に属するレコードを図１６に示すような２１個のグループにまとめ、「「住所の先頭４文字が「大阪府守」のブロック」に属するレコードを図１７に示すような７個のグループにまとめる。【００９９】
ブロック統合部５はグループを構成すると、グループごとに代表レコードを選ぶ。代表レコードの選び方は任意でもよい。例えば、重複候補グループのレコードを何らかのキーでソートして中央のレコードを選ぶという方法でもよいし、先頭のレコードを選ぶのでもよい。１件しかないグループではそのレコードを代表レコードとする。例えば、１〜７０までのグループからは１を、９１〜９５までのグループからは９１を代表レコードとして選んだとする。それ以外の１件ずつのグループではそのレコード自身が代表レコードとなる。【０１００】
ブロック統合部５はグループを統合できるかを調べるとき、代表レコード同士の組合せを類似度計算部６に渡す。類似度計算部６はその代表レコード同士の組合せの類似度が閾値を超えるかを計算し、その代表レコード同士が同じグループになるかどうかという情報をブロック統合部５に返す。【０１０１】
ブロック統合部５は、「「住所」の先頭４文字が「大阪府大」のブロック」、「「住所」の先頭４文字が「大阪府守」のブロック」での処理を終えるとブロックを統合し、次に、木構造においてその親である「「住所」の先頭３文字が「大阪府」のブロック」での統合を行う。例えば、「「住所」の先頭４文字が「大阪府大」のブロック」に関して図１６のようであり、「「住所」の先頭４文字が「大阪府守」のブロック」に関して図１７のようであったとすると、これらは統合され「「住所」の先頭３文字が「大阪府」のブロック」として図１８に示すようになる。「「住所」の先頭３文字が「大阪府」のブロック」における処理では、ブロック統合部５は２８個（２１＋７）の代表レコード同士の組合せで、かつまだ計算していない組合せを、類似度計算部６に渡す。【０１０２】
このように、ブロック統合部５は木構造の深い階層から順にグループを統合していく。ここで、深い階層から浅い階層に移るにしたがって、ブロック分割部３での分割条件が緩やかになっていくことになる。したがって、例えば、ブロックの統合を進める際に２階層以上統合されずに１レコードのままのグループに関しては、他の代表レコードとの組合せを調べないということにしてもよい。【０１０３】
また、２階層以上でなく、１階層以上や３階層以上であってもよく、あらかじめ決めておくのでなく、ユーザが入力してもよいし、設定ファイルから読み込んでもよい。１レコードのグループの代表レコードとの組合せを調べないことにすれば、調べる組合せを大幅に減らすことができ、処理時間を短縮できる。逆に、グループになるべき組合せが漏れてクラスタリングの精度が落ちる危惧はあるが、深い階層、つまり分割時の条件がより厳しい組合せから調べているので、従来のおおよその絞込みと詳細な絞込みを組み合わせた手法と比べても同等以上の精度が期待できる。【０１０４】
また、例えば、住所のフィールドに関しての統合では、１レコードのグループになってしまい、他の代表レコードとの組合せを調べられなかったとしても、そのレコードが他のレコードと重複候補グループに含まれるべきならば、例えば、名称のフィールドなどでそのレコードとグループになる可能性は高い。そのため、１レコードのグループの代表レコードとの組合せを調べなくても、精度はあまり落ちないと考えられる。【０１０５】
ブロック統合部５は、代表レコード同士の類似度が閾値を超えていれば、それらのグループを一つにまとめる。しかし、代表レコード同士の類似度は閾値を超えてなくても、それらのグループに含まれる別のレコード同士の類似度が閾値を超えることは起こりうる。グループ内のレコード同士は、類似度が閾値を超える組合せが存在するはずである。ほとんどの場合は、グループ内のあらゆるレコードの組合せで、閾値を超えずともそれなりに類似度の値が大きくなると考えられる。したがって、代表レコード同士の類似度が閾値を超えない場合は、ある程度類似度の値が大きい場合だけより詳細に調べる。ある程度大きい類似度の値とは、ユーザが入力してもよいし、設定ファイルから読み込んでもよいし、あらかじめ決められているものとしてもよい。また、例えば、類似度閾値の２倍の余裕を持たせるようにしてもよい。例えば、類似度が０〜１００の値を取り、類似度閾値が９０とすれば、閾値は１０の余裕を持つことになり、ある程度大きい類似度の値として２０の余裕を持たせた８０に決定する。何倍の余裕を持たせるかは、ユーザが入力してもよいし、設定ファイルから読み込んでもよいし、あらかじめ決められているものとしてもよい。【０１０６】
ブロック統合部５はグループを統合できるかを調べるため、代表レコード同士の組合せを類似度計算部６に渡す。類似度計算部６はその代表レコード同士の組合せの類似度が閾値を超えるかを計算し、類似度が閾値を超えないがある程度値が大きい場合には、その代表レコード同士が同じグループになる可能性があると判定し、その代表レコードが属する二つのグループ間での全レコードの組合せについて類似度を計算する。【０１０７】
このとき、類似度計算部６は二つのグループ間での全レコードの組合せを調べるのでなく、類似度閾値を超える組合せがあればそれ以上調べないことにしてよい。また、グループ内の組合せでは類似度の値が大きいことが期待できるので、全レコードの組合せでなく、代表レコードともう一方のグループのレコードとの組合せを調べるようにしてもよい。また、類似度計算部６は類似度が閾値を超えないがある程度値が大きい場合にその代表レコード同士が同じグループになる可能性があるという情報をブロック統合部５に返し、ブロック統合部５はその代表レコード同士が同じグループになる可能性があるという情報を受け取るとそれら二つのグループ間での全レコードの組合せを類似度計算部６に渡すようにしてもよい。【０１０８】
以上のようにして、ブロックの統合が終了すれば、ブロック統合部５は結果をDBアクセス部２を通じてデータベース１に登録する。データベース１への登録は、グループの統合結果を重複レコードと解釈して元のデータベースを上書きするようにしてもよいし、新たなデータベースを作成するようにしてもよい。
【図１】
2007026870.tif 000002
【図２】
2007026870.tif 000003
【図３】
2007026870.tif 000004
【図４】
2007026870.tif 000005
【図５】
2007026870.tif 000006
【図６】
2007026870.tif 000007
【図７】
2007026870.tif 000008
【図８】
2007026870.tif 000009
【図９】
2007026870.tif 000010
【図１０】
2007026870.tif 000011
【図１１】
2007026870.tif 000012
【図１２】
2007026870.tif 000013
【図１３】
2007026870.tif 000014
【図１４】
2007026870.tif 000015
【図１５】
2007026870.tif 000016
【図１６】
2007026870.tif 000017
【図１７】
2007026870.tif 000018
【図１８】
2007026870.tif 000019
【国際調査報告】
2007026870.tif 000020
2007026870.tif 000021
2007026870.tif 000022
2007026870.tif 000023