(57)【特許請求の範囲】
【請求項１】
プロセッサと、前記プロセッサに接続される主記憶装置と、前記プロセッサに接続され、データを入出力する入出力装置とを備え、入力された前記データを分析し、類似するデータ毎に分類するデータ分析装置であって、
前記入出力装置は、処理対象のデータを要素とする集合である複数のオブジェクトの入力を受け付け、
前記データ分析装置は、
所定のハッシュ関数を用いて前記各オブジェクトのハッシュ値を算出するハッシュ値算出部と、
前記算出されたハッシュ値に基づいて、前記算出されたハッシュ値が同一である前記オブジェクトから構成される初期クラスタを生成するクラスタリング部と、
前記算出されたハッシュ値に基づいて、前記各初期クラスタが取り得る前記ハッシュ値の範囲を特定し、前記特定されたハッシュ値の範囲に基づいて類似する前記初期クラスタを検索し、前記検索された初期クラスタから構成される最終クラスタを生成するクラスタマージ部と、
を備え、
前記ハッシュ値算出部は、集合に含まれる要素が所定数以上一致する類似関係を満たすオブジェクトのハッシュ値の種類が限定され、かつ、前記類似関係を満たさないオブジェクトに対しては異なるハッシュ値を算出する前記ハッシュ関数を用いることを特徴とするデータ分析装置。
【請求項２】
前記データ分析装置は、
さらに、異なる二つの集合に含まれる要素を比較することによって前記異なる二つの集合が前記類似関係を満たすか否かを判定する類似性判定部を備え、
前記クラスタリング部は、
前記算出されたハッシュ値が同一であるオブジェクトを収集して集合を生成し、
前記生成された集合の中から二つの前記オブジェクトを選択し、前記選択された二つのオブジェクトが前記類似関係を満たすか否かを前記類似性判定部を用いて判定し、
前記選択された二つのオブジェクトが前記類似関係を満たす場合には、前記選択された二つのオブジェクトに含まれる前記要素をマージすることによって前記初期クラスタを生成し、
前記クラスタマージ部は、
処理対象となる第１の初期クラスタを選択し、
前記選択された第１の初期クラスタに含まれる前記オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定し、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第２の初期クラスタを特定し、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たすか否かを前記類似性判定部を用いて判定し、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たす場合には、前記第１の初期クラスタに含まれる前記要素と、前記第２の初期クラスタに含まれる前記要素とをマージすることによって前記最終クラスタを生成することを特徴とする請求項１に記載のデータ分析装置。
【請求項３】
前記オブジェクトをＳと定義し、前記オブジェクトに含まれる前記要素の識別番号をＳ［ｉ］と定義し、０より大きく１以下のパラメータとして与えられる実数をｑと定義し、実数ｘ以上の最小の整数値を算出する関数をｃｅｉｌ（ｘ）と定義した場合に、前記ハッシュ値算出部は、式（１）のように定義されるハッシュ関数ｈ（Ｓ）を用いることを特徴とする請求項２に記載のデータ分析装置。
【数１】
0005716966.tif 000034
【請求項４】
前記入出力装置は、特定の事柄を表すノードと、二つの前記ノード間を接続するエッジとを含むＲＤＦ（Ｒｅｓｏｕｒｃｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ）の入力を受け付け、
前記要素は、前記ノード及び前記エッジのそれぞれに付与されたＵＲＩ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｉｄｅｎｔｉｆｉｅｒ）であり、
前記最終クラスタは、類似する事柄を表す前記ノードがグループ化された集合であることを特徴とする請求項３に記載のデータ分析装置。
【請求項５】
前記データ分析装置は、
前記最終クラスタが生成された後に、新規オブジェクトの入力を受け付けた場合に、前記ハッシュ値算出部を用いて前記入力された新規オブジェクトのハッシュ値を算出し、
前記クラスタマージ部が、
前記新規オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定し、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第３の初期クラスタを特定し、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たすか否かを前記類似性判定部を用いて判定し、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たす場合には、前記第３の初期クラスタに対して、前記新規オブジェクトに含まれる前記要素をマージすることによって前記最終クラスタを生成することを特徴とする請求項３に記載のデータ分析装置。
【請求項６】
プロセッサと、前記プロセッサに接続される主記憶装置と、前記プロセッサに接続され、データを入出力する入出力装置とを備え、入力された前記データを分析し、類似するデータ毎に分類するデータ分析装置におけるデータ分析方法であって、
前記方法は、
前記データ分析装置が、所定のハッシュ関数を用いて、前記入力装置が受け付け、処理対象のデータを要素とする集合である複数のオブジェクトのそれぞれのハッシュ値を算出する第１のステップと、
前記データ分析装置が、前記算出されたハッシュ値に基づいて、前記算出されたハッシュ値が同一である前記オブジェクトから構成される初期クラスタを生成する第２のステップと、
前記データ分析装置が、前記算出されたハッシュ値に基づいて、前記各初期クラスタが取り得る前記ハッシュ値の範囲を特定し、前記特定されたハッシュ値の範囲に基づいて類似する前記初期クラスタを検索し、前記検索された初期クラスタから構成される最終クラスタを生成する第３のステップと、
を含み、
前記第１のステップでは、集合に含まれる要素が所定数以上一致する類似関係を満たすオブジェクトのハッシュ値の種類が限定され、かつ、前記類似関係を満たさないオブジェクトに対しては異なるハッシュ値を算出する前記ハッシュ関数を用いることを特徴とするデータ分析方法。
【請求項７】
前記第２のステップは、
前記算出されたハッシュ値が同一であるオブジェクトを収集して集合を生成するステップと、
前記生成された集合の中から二つの前記オブジェクトを選択し、前記選択された二つのオブジェクトに含まれる前記要素を比較することによって、前記選択された二つのオブジェクトが前記類似関係を満たす否かを判定するステップと、
前記選択された二つのオブジェクトが前記類似関係を満たす場合には、前記選択された二つのオブジェクトに含まれる前記要素をマージすることによって前記初期クラスタを生成するステップと、
を含み、
前記第３のステップは、
処理対象となる第１の初期クラスタを選択するステップと、
前記選択された第１の初期クラスタに含まれる前記オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定するステップと、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第２の初期クラスタを特定するステップと、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たすか否かを判定するステップと、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たす場合には、前記第１の初期クラスタに含まれる前記要素と、前記第２の初期クラスタに含まれる前記要素とをマージすることによって前記最終クラスタを生成するステップと、
を含むことを特徴とする請求項６に記載のデータ分析方法。
【請求項８】
前記オブジェクトをＳと定義し、前記オブジェクトに含まれる前記要素の識別番号をＳ［ｉ］と定義し、０より大きく１以下のパラメータとして与えられる実数をｑと定義し、実数ｘ以上の最小の整数値を算出する関数をｃｅｉｌ（ｘ）と定義した場合に、前記第１のステップでは、式（２）のように定義されるハッシュ関数ｈ（Ｓ）を用いることを特徴とする請求項７に記載のデータ分析方法。
【数２】
0005716966.tif 000035
【請求項９】
前記入出力装置は、特定の事柄を表すノードと、二つの前記ノード間を接続するエッジとを含むＲＤＦ（Ｒｅｓｏｕｒｃｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ）の入力を受け付け、
前記要素は、前記ノード及び前記エッジのそれぞれに付与されたＵＲＩ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｉｄｅｎｔｉｆｉｅｒ）であり、
前記最終クラスタは、類似する事柄を表す前記ノードがグループ化された集合であることを特徴とする請求項８に記載のデータ分析方法。
【請求項１０】
前記方法は、さらに、
前記最終クラスタが生成された後に、新規オブジェクトの入力を受け付けた場合に、前記入力された新規オブジェクトのハッシュ値を算出するステップと、
前記新規オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定するステップと、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第３の初期クラスタを特定するステップと、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たすか否かを判定するステップと、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たす場合には、前記第３の初期クラスタに対して、前記新規オブジェクトに含まれる前記要素をマージすることによって前記最終クラスタを生成するステップと、
を含むことを特徴とする請求項８に記載のデータ分析方法。
【請求項１１】
プロセッサと、前記プロセッサに接続される主記憶装置と、前記プロセッサに接続され、データを入出力する入出力装置とを備え、入力された前記データを分析し、類似するデータ毎に分類するデータ分析装置が実行するプログラムであって、
前記プログラムは、
所定のハッシュ関数を用いて、前記入出力装置が受け付け、処理対象のデータを要素とする集合である複数のオブジェクトのそれぞれのハッシュ値を算出する第１の手順と、
前記算出されたハッシュ値に基づいて、前記算出されたハッシュ値が同一である前記オブジェクトから構成される初期クラスタを生成する第２の手順と、
前記算出されたハッシュ値に基づいて、前記各初期クラスタが取り得る前記ハッシュ値の範囲を特定し、前記特定されたハッシュ値の範囲に基づいて類似する前記初期クラスタを検索し、前記検索された初期クラスタから構成される最終クラスタを生成する第３の手順と、
を前記プロセッサに実行させるためのプログラムであって、
前記第１の手順では、集合に含まれる要素が所定数以上一致する類似関係を満たすオブジェクトのハッシュ値の種類が限定され、かつ、前記類似関係を満たさないオブジェクトに対しては異なるハッシュ値を算出する前記ハッシュ関数を用いて前記ハッシュ値を前記プロセッサに算出させることを特徴とするプログラム。
【請求項１２】
前記第２の手順は、
前記算出されたハッシュ値が同一であるオブジェクトを収集して集合を生成する手順と、
前記生成された集合の中から二つの前記オブジェクトを選択し、前記選択された二つのオブジェクトに含まれる前記要素を比較することによって、前記選択された二つのオブジェクトが前記類似関係を満たす否かを判定する手順と、
前記選択された二つのオブジェクトが前記類似関係を満たす場合には、前記選択された二つのオブジェクトに含まれる前記要素をマージすることによって前記初期クラスタを生成する手順と、
を含み、
前記第３の手順は、
処理対象となる第１の初期クラスタを選択する手順と、
前記選択された第１の初期クラスタに含まれる前記オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定する手順と、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第２の初期クラスタを特定する手順と、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たすか否かを判定する手順と、
前記第１の初期クラスタ及び前記第２の初期クラスタが前記類似関係を満たす場合には、前記第１の初期クラスタに含まれる前記要素と、前記第２の初期クラスタに含まれる前記要素とをマージすることによって前記最終クラスタを生成する手順と、
を含むことを特徴とする請求項１１に記載のプログラム。
【請求項１３】
前記オブジェクトをＳと定義し、前記オブジェクトに含まれる前記要素の識別番号をＳ［ｉ］と定義し、０より大きく１以下のパラメータとして与えられる実数をｑと定義し、実数ｘ以上の最小の整数値を算出する関数をｃｅｉｌ（ｘ）と定義した場合に、前記第１の手順では、式（３）のように定義されるハッシュ関数ｈ（Ｓ）を用いることを特徴とする請求項１２に記載のプログラム。
【数３】
0005716966.tif 000036
【請求項１４】
前記入出力装置は、特定の事柄を表すノードと、二つの前記ノード間を接続するエッジとを含むＲＤＦ（Ｒｅｓｏｕｒｃｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ）の入力を受け付け、
前記要素は、前記ノード及び前記エッジのそれぞれに付与されたＵＲＩ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｉｄｅｎｔｉｆｉｅｒ）であり、
前記最終クラスタは、類似する事柄を表す前記ノードがグループ化された集合であることを特徴とする請求項１３に記載のプログラム。
【請求項１５】
前記プログラムは、さらに、
前記最終クラスタが生成された後に、新規オブジェクトの入力を受け付けた場合に、前記入力された新規オブジェクトのハッシュ値を算出する手順と、
前記新規オブジェクトと前記類似関係を満たす他の前記オブジェクトが取り得る前記ハッシュ値の範囲を特定する手順と、
前記特定されたハッシュ値の範囲に含まれるハッシュ値と一致する前記オブジェクトを含む第３の初期クラスタを特定する手順と、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たすか否かを判定する手順と、
前記新規オブジェクトと前記第３の初期クラスタとが前記類似関係を満たす場合には、前記第３の初期クラスタに対して、前記新規オブジェクトに含まれる前記要素をマージすることによって前記最終クラスタを生成する手順と、
を前記プロセッサに実行させることを特徴とする請求項１３に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の要素から構成される集合を多数含むデータを分析する装置、方法及びプログラムに関する。
【背景技術】
【０００２】
今日、社会のあらゆる分野において、様々な電子データが生み出されている。そうした膨大なデータの中から有用な知識を発見することは、データ分析技術の重要な課題である。
【０００３】
データの種類は多種多様であるが、頻繁に使用されるデータの種類の１つとして、複数の要素から成る集合が多数集まって構成されるデータがある。前述したデータの一例を図７を用いて説明する。
【０００４】
図７は、従来のデータの一例を示す説明図である。
【０００５】
まず、データに含まれる要素７０４から構成される集合Ｕ７０１がある。そして、集合Ｕ７０１の部分集合Ｓｉ７０２を多数集めた集合Ｓ７０３が下式（１）のように与えられる。ここでｎは、集合Ｓ７０３に含まれる部分集合の数である。図７に示す例では、ｎは「４」である。
【０００６】
【数１】
0005716966.tif 000002
【０００７】
本明細書では、各部分集合Ｓｉを「オブジェクト」、集合Ｕに属する要素を「属性」と呼ぶ。
【０００８】
オブジェクトＳｉ７０２は、集合Ｕ７０１に属する属性の集合であり、当該オブジェクトを構成する属性７０４によってオブジェクトＳｉ７０２が特徴づけられる。
【０００９】
前述したデータの一例として、商店において顧客が購入した商品を記録したｐｏｉｎｔ  ｏｆ  ｓａｌｅｓ  （ＰＯＳ）データがある。ＰＯＳデータの場合、集合Ｕは全商品の集合であり、オブジェクトＳｉは個々の決済に相当する。このとき、各オブジェクトＳｉは購入した商品の集合によって特徴づけられる。
【００１０】
また、大規模な文書データにおいて、特定の動詞と共起しやすい名詞の集合、医療における患者の遺伝子変異及び疾患の有無の情報なども、同様なデータの例である。
【００１１】
さらに、明示的に集合となっていないデータでも、前述したようなモデルに帰着させ、解析できる場合がある。一例としては、様々な事物の関係を柔軟に表現するために考案された枠組みであるｒｅｓｏｕｒｃｅ  ｄｅｓｃｒｉｐｔｉｏｎ  ｆｒａｍｅｗｏｒｋ（ＲＤＦ）のデータである。ここで、ＲＤＦについて図８Ａ及び図８Ｂを用いて説明する。
【００１２】
図８Ａ及び図８Ｂは、従来のＲＤＦデータを示す説明図である。
【００１３】
図８Ａに示すように、ＲＤＦは、事物とそれらの関係とを有向グラフで表現したものである。ここで、有向グラフとは、点と点とを、向きがある線で結んだものである。有向グラフにおいて、点はノード８０１、線はエッジ８０２と呼ばれる。
【００１４】
ＲＤＦの有向グラフでは、事物を区別することための識別子８０３であるｕｎｉｆｏｒｍ  ｒｅｓｏｕｒｃｅ  ｉｄｅｎｔｉｆｉｅｒ（ＵＲＩ）がノード８０１及びエッジ８０２に付与される。ノード８０１のＵＲＩは、当該ノード８０１に対応する事物を表し、エッジ８０２のＵＲＩは結ばれている事物がどのような関係にあるかを表す。
【００１５】
例えば、図８Ａ及び図８Ｂに示す例では、「ある人２」は、「花子」という名前であり、「ある人１」と友達であり、かつ、犬を飼っていることが表現されている。
【００１６】
このとき、ＲＤＦにおいて各ノード８０１をオブジェクト、エッジ８０２のＵＲＩ８０３を属性とみると、図９Ａに示すように表現できる。なお、図９Ａにおいて「１、２、３、４」といった数字は、各ＵＲＩに割り当てられた番号である。したがって、ＲＤＦは、ノード８０１、すなわち、事物を、当該事物に関連する属性の集合によって特徴づけることができ、図９Ｂに示すように前述したモデルに帰着できる。なお、Ｓ１〜Ｓ４はオブジェクトを表し、Ｓ１〜Ｓ４に含まれる数字はＵＲＩに対応する。
【００１７】
前述したようなデータを解釈するためには、与えられたオブジェクト集合Ｓ７０３を網羅的に分析し、類似するオブジェクトを特定し、収集するデータ処理が必要である。
【００１８】
集合Ｕ７０１の部分集合であるオブジェクトＳｉ７０３は、集合Ｕ７０１の属性を無作為に含むわけではなく、多くの場合、いくつかのカテゴリに分かれている。そのため、同一のカテゴリに属するオブジェクトは互いに類似する属性を持つことが期待される。
【００１９】
本発明では、式（１）に示すような集合Ｓが与えられたとき、集合に含まれるオブジェクトを相互に比較して、類似するオブジェクトのカテゴリを推定する技術について説明する。
【００２０】
図８Ａに示す例では、「ｐｒｏｐ：ｎａｍｅ」、「ｐｒｏｐ：ａｄｄｒｅｓｓ」、及び「ｐｒｏｐ：ｆｒｉｅｎｄ」を属性として持つため、「ｒｅｓｏｕｒｃｅ：Ｔａｒｏ」及び「ｒｅｓｏｕｒｃｅ：Ｈａｎａｋｏ」を類似オブジェクトと見なすことができる。前述したようなカテゴリを見つけることによって、人間に相当するカテゴリを発見できる。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００８−２２５６２９号公報
【非特許文献】
【００２２】
【非特許文献１】岡田孝・元田浩、相関ルールとその周辺、オペレーションズ・リサーチ：経営の科学 47(9):565-571、2002年
【非特許文献２】石橋徹夫他、Locality-Sensitive Hashingを用いた階層的クラスタ解析手法の高速化、情報処理学会研究報告(CVIM) 2003(109):57-62
【発明の概要】
【発明が解決しようとする課題】
【００２３】
類似するオブジェクトを網羅的に分析するためには、式（１）に示すような集合Ｓに含まれるオブジェクトＳｉを相互に比較し、類似するものを探し出す必要がある。このとき、集合Ｓの要素間のペアの数は下式（２）で与えられる。
【００２４】
【数２】
0005716966.tif 000003
【００２５】
式（２）から分かるように、ｎが大きいとき、全ペアの比較を行うことは非現実的である。このため、前述の分析処理を実用化するためには高速な計算手法が必要である。
【００２６】
前述したデータの分析方法に関する技術として、データマイニングにおけるバスケット分析が知られている（例えば、非特許文献１参照）。
【００２７】
以下では、集合Ｘの大きさ、すなわち、集合Ｘの要素数を｜Ｘ｜、空集合をφと記載する。
【００２８】
式（１）に示す集合Ｓを入力とした場合に、バスケット分析によって、相関ルールと呼ばれる情報が得られる。ここで、相関ルールとは、下式（３）〜（５）を満たす集合Ｕの部分集合Ｘ及び部分集合Ｙに対して、下式（６）を満たすならば、下式（７）を満たすような関係をいう。言い換えると、集合Ｓの要素である部分集合Ｓｉが部分集合Ｘを含むならば部分集合Ｙを含む関係をいう。
【００２９】
【数３】
0005716966.tif 000004
【００３０】
【数４】
0005716966.tif 000005
【００３１】
【数５】
0005716966.tif 000006
【００３２】
【数６】
0005716966.tif 000007
【００３３】
【数７】
0005716966.tif 000008
【００３４】
バスケット分析は、産業上広い応用分野を持ち、例えば特許文献１のようなユーザが関心を持つ可能性のある事物を推薦するシステムに応用される。
【００３５】
しかし、バスケット分析は、データに含まれる顕著な特徴を探索する技術であって、データをカテゴリに分類する技術ではない。特に、低頻度のカテゴリを認識するには不向きな分析方法である。
【００３６】
顕著な特徴を抽出するだけでなく、データをカテゴリごとに分類するためには、オブジェクト間の類似度を算出し、類似するオブジェクトをまとめる技術が必要である。しかし、要素数ｎ、すなわち、データ数が非常に大きい場合、前述したように、全オブジェクト間を相互に比較する処理は、現実的な処理時間では実現が困難となる。
【００３７】
そこで、類似する可能性があるオブジェクトを事前に集め、比較範囲を限定する方法が知られている。具体的には、以下の手順に従って処理が実行される。
【００３８】
（１）関数ｈを定義する。
【００３９】
当該関数ｈは、オブジェクトＳｉを変数とする関数であって、類似するオブジェクトＳｉに対しては同一の値を与え、類似しないオブジェクトＳｉに対しては異なる値を与えるように定義される。ここでは、集合Ｓの要素である各オブジェクトＳｉに対して、値ｈ（Ｓｉ）を算出する。以下、関数ｈをハッシュ関数と呼び、値ｈ（Ｓｉ）をハッシュ値と呼ぶ。
【００４０】
（２）ハッシュ値ｈ（Ｓｉ）が等しいオブジェクトを収集する。
【００４１】
（３）収集されたオブジェクトを相互比較する。
前述した手順で処理を実行することによって、類似度の算出対象となるオブジェクトを限定できる（図１０参照）。
【００４２】
図１０は、従来のオブジェクトの分類方法を示す説明図である。図１０の（ａ）は、全てのオブジェクト間を比較する場合の概念図を表し、図１０の（ｂ）は、前述したハッシュ値を用いてオブジェクト間を比較する場合の概念図を表す。
【００４３】
前述した方法に用いられるハッシュ関数ｈの算出方法として、ｌｏｃａｌｉｔｙ  ｓｅｎｓｉｔｉｖｅ  ｈａｓｈｉｎｇと呼ばれる手法が知られている（例えば、非特許文献２参照）。
【００４４】
しかし、非特許文献２に記載の手法は、ハッシュ値が等しい類似オブジェクトを高速に探索できるが、ハッシュ値が異なる場合には類似度を比較する対象から除かれるため、精度のよい解析には対応できない。
【００４５】
本発明では、オブジェクトの類似度の算出処理を高速化するために、類似する可能性のあるオブジェクトを高速に特定する手段を提供することによって、類似オブジェクトを網羅的に探索可能とする手段を提供する。
【課題を解決するための手段】
【００４６】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、プロセッサと、前記プロセッサに接続される主記憶装置と、前記プロセッサに接続され、データを入出力する入出力装置とを備え、入力された前記データを分析し、類似するデータ毎に分類するデータ分析装置であって、前記入出力装置は、処理対象のデータを要素とする集合である複数のオブジェクトの入力を受け付け、前記データ分析装置は、所定のハッシュ関数を用いて前記各オブジェクトのハッシュ値を算出するハッシュ値算出部と、二つの前記オブジェクトが類似するか否かを判定する類似判定部と、前記算出されたハッシュ値に基づいて、前記算出されたハッシュ値が同一である前記オブジェクトから構成される初期クラスタを生成する初期クラスタリング部と、前記算出されたハッシュ値に基づいて、前記各初期クラスタが取り得る前記ハッシュ値の範囲を特定し、前記特定されたハッシュ値の範囲に基づいて類似する前記初期クラスタを検索し、前記検索された初期クラスタから構成される最終クラスタを生成するクラスタマージ部と、を備え、前記ハッシュ値算出部は、集合に含まれる要素が所定数以上一致する類似関係を満たすオブジェクトのハッシュ値の種類が限定され、かつ、前記類似関係を満たさないオブジェクトに対しては異なるハッシュ値を算出する前記ハッシュ関数を用いることを特徴とする。
【発明の効果】
【００４７】
本発明によれば、複数のオブジェクトを含むデータから、類似するオブジェクトから構成されるクラスタを高精度かつ高速に生成できる。
【図面の簡単な説明】
【００４８】
【図１】本発明の第１の実施形態のデータ分析装置の構成例を示すブロック図である。
【図２】本発明の第１の実施形態におけるデータ分析装置の各構成の連携を説明するシーケンス図である。
【図３】本発明の第１の実施形態におけるデータ分析装置の処理の流れを示すフローチャートである。
【図４】本発明の第１の実施形態における初期クラスタの生成処理を説明するフローチャートである。
【図５】本発明の第１の実施形態における最終クラスタの生成処理を説明するフローチャートである。
【図６】本発明の第２の実施形態におけるデータ分析装置の構成例を示すブロック図である。
【図７】従来のデータの一例を示す説明図である。
【図８Ａ】従来のＲＤＦデータを示す説明図である。
【図８Ｂ】従来のＲＤＦデータを示す説明図である。
【図９Ａ】従来のＲＤＦデータの想定モデルへの対応を示す説明図である。
【図９Ｂ】従来のＲＤＦデータの想定モデルへの対応を示す説明図である。
【図１０】従来のオブジェクトの分類方法を示す説明図である。
【発明を実施するための形態】
【００４９】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００５０】
（第１の実施形態）
図１は、本発明の第１の実施形態のデータ分析装置１００の構成例を示すブロック図である。
【００５１】
データ分析装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１、主記憶装置１０２、補助記憶装置１０３、リムーバブルドライブ１０４、ユーザインタフェース１０６及びネットワークインタフェース１０７を備える。各構成は、内部バス等によって互いに接続される。
【００５２】
また、データ分析装置１００は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等のネットワーク１４０を介して外部記憶装置１３０と接続される。なお、本発明は、ネットワーク１４０の種別に限定されず、有線及び無線いずれの接続方法を用いてもよい。
【００５３】
ＣＰＵ１０１は、主記憶装置１０２に格納されたプログラムを実行する演算装置である。ＣＰＵ１０１が、主記憶装置１０２に格納されるプログラムを実行することによって、データ分析装置１００が有する機能を実現することができる。以下では、プログラムを主語にして処理を説明するときには、ＣＰＵ１０１によって当該プログラムが実行されていることを表す。
【００５４】
主記憶装置１０２は、ＣＰＵ１０１によって実行されるプログラム及び当該プログラムの実行に必要な情報を格納する。主記憶装置１０２は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  アクセス  Ｍｅｍｏｒｙ）等のメモリが考えられる。
【００５５】
主記憶装置１０２には、プログラムとして、ハッシュ値算出部１１０、類似性判定部１１１、初期クラスタリング部１１２及びクラスタマージ部１１３を格納し、また、情報としてオブジェクト集合１２０、初期クラスタ１２１及び最終クラスタ１２２を格納する。
【００５６】
ハッシュ値算出部１１０は、ハッシュ関数を用いて入力されたオブジェクトのハッシュ値を算出する。本実施形態では、ハッシュ値算出部１１０は、予め所定の条件を満たすハッシュ関数を保持しているものとする。なお、ハッシュ関数については後述する。類似性判定部１１１は、オブジェクト間の類似性を判定する。
【００５７】
初期クラスタリング部１１２は、ハッシュ値算出部１１０及び類似性判定部１１１の処理結果に基づいて、ハッシュ値が同一、かつ、類似性のあるオブジェクトから構成される初期クラスタ１２１を生成する。
【００５８】
クラスタマージ部１１３は、ハッシュ値算出部１１０及び類似性判定部１１１の処理結果に基づいて、ハッシュ値が類似する２以上の初期クラスタをマージして、最終クラスタ１２２を生成する。
【００５９】
オブジェクト集合１２０は、各プログラムに対する入力データである。初期クラスタ１２１は、初期クラスタリング部１１２によって生成されるクラスタの情報である。また、最終クラスタ１２２は、クラスタマージ部１１３によって生成されるクラスタの情報である。
【００６０】
なお、オブジェクト集合１２０は、主記憶装置１０２に格納される必要はなく、例えば、補助記憶装置１０３、リムーバブルメディア又は外部記憶装置１３０に格納されていてもよい。この場合、ＣＰＵ１０１が、補助記憶装置１０３、リムーバブルメディア又は外部記憶装置１３０からオブジェクト集合１２０を読み出し、読み出されたオブジェクト集合１２０を主記憶装置１０２に格納する。
【００６１】
また、初期クラスタ１２１及び最終クラスタ１２２は、主記憶装置１０２に格納される必要はなく、例えば、補助記憶装置１０３及びリムーバブルメディアに格納されてもよい。この場合、ＣＰＵ１０１は、必要に応じて、補助記憶装置１０３及びリムーバブルメディアから初期クラスタ１２１及び最終クラスタ１２２を読み出すことができる。
【００６２】
また、本実施形態では、ハッシュ値算出部１１０、類似性判定部１１１、初期クラスタリング部１１２及びクラスタマージ部１１３をプログラムによって実現していたが、本発明はこれに限定されない。例えば、ハッシュ値算出部１１０、類似性判定部１１１、初期クラスタリング部１１２及びクラスタマージ部１１３が備える機能を専用のハードウェアとして実現してもよい。すなわち、データ分析装置１００が、ハッシュ値関数算出装置、類似性判定装置、初期クラスタリング装置及びクラスタマージ装置を備える構成であってもよい。
【００６３】
補助記憶装置１０３は、情報を永続的に保持することが可能な装置であり、例えば、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等が考えられる。リムーバブルドライブ１０４は、リムーバブルメディアへのデータの書込処理及び読出処理を実行する装置である。ここで、リムーバブルメディアには、ＣＤ−ＲＯＭ、ＤＶＤなどの光学ディスク、及びフロッピーディスク（フロッピーは登録商標、以下同じ）などの磁気ディスクが含まれる。
【００６４】
なお、リムーバブルメディアには、オブジェクト集合１２０、初期クラスタ１２１及び最終クラスタ１２２を記録することができる。
【００６５】
ユーザインタフェース１０６は、データ分析装置１００の利用者がデータを入力し、また、処理の結果を出力するためのインタフェースである。ユーザインタフェース１０６は、ディスプレイ、キーボード及びマウスなどが含まれる。ネットワークインタフェース１０７は、ネットワーク１４０を介して外部の装置と接続するためのインタフェースである。
【００６６】
次に、データ分析装置１００の具体的な処理の内容について説明する。ただし、以下では、オブジェクト集合１２０は、補助記憶装置１０３に格納されているものとする。
【００６７】
図２は、本発明の第１の実施形態におけるデータ分析装置１００の各構成の連携を説明するシーケンス図である。
【００６８】
データ分析装置１００の利用者が、ユーザインタフェース１０６を用いて、処理の開始を指示する（ステップＳ２００）。
【００６９】
処理の開始指示を受け付けたＣＰＵ１０１は、補助記憶装置１０３からオブジェクト集合１２０を読み出す（ステップＳ２０１）。読み出されたオブジェクト集合１２０は、主記憶装置１０２に格納される。
【００７０】
次に、ＣＰＵ１０１は、初期クラスタ１２１を生成し（ステップＳ２０２）、生成された初期クラスタ１２１を補助記憶装置１０３に出力する（ステップＳ２０３）。これによって、補助記憶装置１０３に初期クラスタ１２１が格納される。
【００７１】
次に、ＣＰＵ１０１は、初期クラスタ１２１を補助記憶装置１０３から読み出し（ステップＳ２０４）、読み出された初期クラスタ１２１を用いて最終クラスタ１２２を生成する（ステップＳ２０５）。
【００７２】
さらに、ＣＰＵ１０１は、生成された最終クラスタ１２２を補助記憶装置１０３に出力する（ステップＳ２０６）。これによって、補助記憶装置１０３に最終クラスタ１２２が格納される。
【００７３】
最後に、ＣＰＵ１０１は、ユーザインタフェース１０６を介して利用者に処理の終了を通知する（ステップＳ２０７）。
【００７４】
なお、ステップＳ２００では、直接利用者がオブジェクト集合１２０を入力してもよい。この場合、ステップＳ２０１の処理を省略してもよい。また、オブジェクト集合１２０は、外部記憶装置１３０から読み出されてもよい。
【００７５】
図３は、本発明の第１の実施形態におけるデータ分析装置１００の処理の流れを示すフローチャートである。
【００７６】
ＣＰＵ１０１は、オブジェクト集合１２０が入力されると、初期クラスタリング部１１２を実行する。
【００７７】
初期クラスタリング部１１２は、ハッシュ値算出部１１０及び類似性判定部１１１を呼び出す。呼び出されたハッシュ値算出部１１０及び類似性判定部１１１は、それぞれ所定の処理を実行し、処理の結果を初期クラスタリング部１１２に出力する。なお、ハッシュ値算出部１１０及び類似性判定部１１１が実行する処理については後述する。
【００７８】
初期クラスタリング部１１２は、出力された結果に基づいて、初期クラスタ１２１を生成する。なお、初期クラスタリング部１１２が実行する処理の詳細については後述する。
【００７９】
ＣＰＵ１０１は、初期クラスタリング部１１２の処理が完了すると、次に、クラスタマージ部１１３を実行する。
【００８０】
クラスタマージ部１１３は、類似性判定部１１１を呼び出す。呼び出された類似性判定部１１１は、所定の処理を実行し、処理の結果をクラスタマージ部１１３に出力する。クラスタマージ部１１３は、出力された結果と初期クラスタとを用いて、最終クラスタ１２２を生成する。なお、クラスタマージ部１１３が実行する処理については後述する。
【００８１】
ここで、ハッシュ値算出部１１０が用いるハッシュ値関数ｈについて説明する。本実施形態では、ハッシュ関数は、入力されるオブジェクト集合１２０の特性に合わせて予めデータ分析装置１００に登録されている。
【００８２】
本実施形態におけるハッシュ関数ｈは、互いに類似するオブジェクトを検索するために使用される。したがって、ハッシュ関数ｈは、以下の条件を満たすものが望ましい。
条件１：類似しないオブジェクトＳ１、Ｓ２に対し、高い確率で下式（８）を満たす。
【００８３】
【数８】
0005716966.tif 000009
【００８４】
条件２：下式（９）を満たすオブジェクトＳ１、Ｓ２に対し、必ず下式（１０）を満たす。
【００８５】
【数９】
0005716966.tif 000010
【００８６】
【数１０】
0005716966.tif 000011
【００８７】
条件３：類似するオブジェクトＳｉは、ハッシュ値ｈ（Ｓｉ）が異なっても値の種類が限られる。
【００８８】
あらゆるデータに対し、前述した全ての条件を満たすハッシュ関数ｈを設計するのは難しいが、本発明では一例として、以下に述べるデータが与えられたとき、前述の条件１〜３を満たすハッシュ関数を示す。
【００８９】
まず、任意の集合Ｕから無作為に選択されたｍ個の要素から成る集合Ｇがｇ個あるものとする。以下では当該集合をグループと呼ぶ。また、各オブジェクトＳｉは、いずれか一つのグループＧから、最大Ｒ個の要素を無作為に除去して得られる集合とする。ただし、整数ｍ及びＲは下式（１１）及び下式（１２）を満たすものとする。
【００９０】
【数１１】
0005716966.tif 000012
【００９１】
【数１２】
0005716966.tif 000013
【００９２】
このとき、同一グループの要素であるオブジェクトＳｉが、類似オブジェクトとなる。
【００９３】
また、入力されたオブジェクト集合Ｓに含まれる属性にはＩＤ番号が割り当てられ、割り当てられたＩＤ番号の昇順にオブジェクトＳｉに含まれる属性がソートされているものとする。図７に示す例では、下記のようなものになる。
Ｓ１：［１，２，３］
Ｓ２：［１，２，３］
Ｓ３：［５，６，７］
Ｓ４：［１，２，３，４］
以下では、オブジェクトＳｉに含まれる属性がＩＤ番号の順にソートされた後のＳｉにおけるｊ番目の属性のＩＤ番号をＳｉ［ｊ］と記載する。すなわち、Ｓｉ［１］はオブジェクトＳｉに含まれる属性のうちＩＤ番号が最小の属性を示し、Ｓｉ［｜Ｓｉ｜］はオブジェクトＳｉに含まれる属性のうちＩＤ番号が最大の属性を表す。
【００９４】
また、以下では、変数ｑを０より大きく１以下の実数とする。さらに、ｃｅｉｌ（ｘ）は実数ｘ以上の最小の整数とする関数であり、天井関数とも呼ばれる。
【００９５】
このとき、本発明のハッシュ関数ｈを下式（１３）に示すように定義する。
【００９６】
【数１３】
0005716966.tif 000014
【００９７】
ここで、例えば、変数ｑが「０．５」のとき、図７に示すオブジェクトＳ１〜Ｓ４のハッシュ値は、下式（１４）〜（１７）に示すように算出される。なお、変数ｑの値は一例であって、０より大きく１以下の実数であればどのような値でもよく、本発明のデータ分析装置１００の利用者がパラメータとして与える値である。
【００９８】
【数１４】
0005716966.tif 000015
【００９９】
【数１５】
0005716966.tif 000016
【０１００】
【数１６】
0005716966.tif 000017
【０１０１】
【数１７】
0005716966.tif 000018
【０１０２】
このとき、式（１３）にように定義したハッシュ関数ｈ（Ｓｉ）が、前述のようなオブジェクトＳｉを要素とするオブジェクト集合Ｓに対し、条件１〜３を満足する。以下、具体的に理由を述べる。
【０１０３】
（条件１について）
二つのオブジェクトＳ１、Ｓ２が、異なるグループから得られたオブジェクトであるとする。このとき、ハッシュ値ｈ（Ｓ１）は、オブジェクトＳ１に含まれる属性のＩＤ番号であり、下式（１８）を満たす。したがって、ハッシュ値ｈ（Ｓ１）がＳ２に含まれる確率、すなわち、下式（１９）を満たす確率は高々ｍ／｜Ｕ｜である。前述のように、式（１１）を満たすため当該確率は低い。
【０１０４】
【数１８】
0005716966.tif 000019
【０１０５】
【数１９】
0005716966.tif 000020
【０１０６】
よって、高い確率で式（８）を満たす。
【０１０７】
（条件２について）
式（９）を満たす二つのオブジェクトＳ１、Ｓ２において、下式（２０）及び下式（２１）を満たすことはない。なぜなら、ハッシュ値ｈは式（１３）に示すようにＩＤ番号であり、属性が異なればＩＤ番号も異なるためである。したがって、式（１０）を満たす。
【０１０８】
【数２０】
0005716966.tif 000021
【０１０９】
【数２１】
0005716966.tif 000022
【０１１０】
（条件３について）
前述のようにオブジェクトＳｉは、グループＧからＲ個の要素（属性）をランダムに除去して得られたオブジェクトである。このとき、ハッシュ値ｈ（Ｓｉ）は、グループＧの限られた要素のいずれかであることを説明する。以下では、ハッシュ値ｈ（Ｓｉ）の、Ｇにおける順位をａとする。
【０１１１】
まず、順位ａが最大値をとるのは、オブジェクトＳｉがグループＧの下位Ｒ個の要素を削除した集合である場合である。この場合、順位ａの値は、下式（２２）から下式（２３）のように算出できる。
【０１１２】
【数２２】
0005716966.tif 000023
【０１１３】
【数２３】
0005716966.tif 000024
【０１１４】
一方、順位ａが最小値をとるのは、オブジェクトＳｉがグループＧの上位Ｒ個の要素を削除した集合である場合である。この場合、順位ａの値は、式（２２）から、下式（２４）のように算出できる。すなわち、順位ａの値は、下式（２５）を満たす。
【０１１５】
【数２４】
0005716966.tif 000025
【０１１６】
【数２５】
0005716966.tif 000026
【０１１７】
したがって、順位ａの取り得る値の種類は高々（Ｒ＋１）個である。
【０１１８】
以上がハッシュ関数の説明である。
【０１１９】
次に、オブジェクトの類似性の判定方法について説明する。
【０１２０】
オブジェクトの類似性は、類似性判定部１１１によって判定される。具体的には、類似性判定部１１１は、二つのオブジェクトＳ１、Ｓ２が与えられたとき、二つのオブジェクトの類似性を示す数値を算出する。二つのオブジェクト（集合）の類似性を数値化する方法は、さまざまな公知の方法を用いることができる。
【０１２１】
例えば、オブジェクトＳ１、Ｓ２の異なる要素の数Ｄ１を用いる方法が知られている。なお、Ｄ１は、下式（２６）のように与えられる。
【０１２２】
【数２６】
0005716966.tif 000027
【０１２３】
この場合、類似性判定部１１１は、Ｄ１が閾値（例えば、２Ｒ）以下のとき、オブジェクトＳ１とオブジェクトＳ２とが類似すると判定する。
【０１２４】
しかし、前述したＤ１を用いた場合、要素数が小さいオブジェクトＳ１、Ｓ２に対して、要素の違いが大きくても類似性があると判定されてしまうことがある。例えば、要素数が「１００」のオブジェクトＳ１、Ｓ２に対して、閾値が「６０」と設定された場合に、Ｄ１が「５０」ならばオブジェクトＳ１、Ｓ２は類似オブジェクトと判定される。しかし、両オブジェクトは半分の要素が異なり類似するオブジェクトとして扱うのは誤りがある可能性がある。すなわち、要素数に対して、Ｄ１が十分小さくないと誤った判定結果が出力される可能性がある。
【０１２５】
そこで、前述したような判定を防ぐために、下式（２７）を用いる方法が考えられる。
【０１２６】
【数２７】
0005716966.tif 000028
【０１２７】
式（２７）は、オブジェクトＳ１、Ｓ２の和集合の要素数に対する、異なる要素の数Ｄ１の相対的な割合を算出するための数式である。
【０１２８】
この場合、類似性判定部１１１は、Ｄ２と新たな閾値ｐとを比較し、Ｄ１及びＤ２の両方が条件を満たす場合にのみ、オブジェクトが類似すると判定する。ここで、閾値ｐは、０以上１以下の実数値である。
【０１２９】
また、Ｄ１及びＤ２を算出するときに、オブジェクトＳ１、オブジェクトＳ２、オブジェクトＳ１とＳ２との共通部分、及び、オブジェクトＳ１とＳ２との和集合のそれぞれの要素数を単に数えるだけでなく、各集合の要素ｕ（ｕは集合Ｕの要素）に実数値の重みｗ（ｕ）を定義し、個数を数える代わりに、重みｗ（ｕ）の和を算出してもよい。なお、任意の要素ｕに対して重みｗ（ｕ）を「１」とした場合は、Ｄ１及びＤ２は、個数を数えた場合の値と一致する。
【０１３０】
次に、初期クラスタ１２１を生成処理について説明する。
【０１３１】
図４は、本発明の第１の実施形態における初期クラスタ１２１の生成処理を説明するフローチャートである。
【０１３２】
当該処理では、初期クラスタリング部１１２が、ハッシュ値が同一のオブジェクトを集めて、相互にオブジェクトを比較し、類似性のある複数のオブジェクトをマージする。なお、オブジェクトの類似性は、類似性判定部１１１によって判定される。ここで、複数のオブジェクトをマージするとは、各オブジェクトの和集合を生成することを示す。
【０１３３】
以下では、初期クラスタリング部１１２が、算出されたハッシュ値を取得した後の処理について説明する。なお、ハッシュ値算出部１１０は、以下のような処理を実行するものとする。すなわち、ハッシュ値算出部１１０は、入力されたオブジェクト集合１２０に含まれる属性のＩＤ番号を算出し、算出されたＩＤ番号の昇順に属性をソートする。さらに、ハッシュ値算出部１１０は、登録されたハッシュ関数ｈを用いて、オブジェクト集合１２０に含まれる各オブジェクトＳｉのハッシュ値ｈ（Ｓｉ）を算出する。本発明におけるハッシュ関数ｈ（Ｓｉ）の定義は、前述した通りである。
【０１３４】
本実施形態における初期クラスタ１２１は、ハッシュ値が同一であり、かつ、類似性のあるオブジェクトをマージすることによって生成されるオブジェクトである。したがって、ハッシュ値が同一であるが、類似性のないオブジェクトは異なる初期クラスタ１２１となる。そのため、同一のハッシュ値である初期クラスタ１２１が複数存在することとなる。
【０１３５】
以下では、ハッシュ値がｘである初期クラスタ１２１の集合をＣ０（ｘ）と記載する。
【０１３６】
初期クラスタリング部１１２は、変数ｉを「１」を設定し、ステップＳ４０２に進む（ステップＳ４０１）。すなわち、まず、オブジェクトＳ１が処理対象として選択される。最初にオブジェクトＳ１がどの初期クラスタに所属するかが判定され、以下、変数ｉを１ずつ加算して、全てのオブジェクトＳｉについて同様の処理が実行される。
【０１３７】
次に、初期クラスタリング部１１２は、変数ｉがオブジェクト集合Ｓの要素数より大きいか否か、すなわち、すべてのオブジェクトに対して処理が終了したか否かを判定する（ステップＳ４０２）。変数ｉがオブジェクト集合Ｓの要素数より大きいと判定された場合、初期クラスタリング部１１２は、処理を終了する。
【０１３８】
変数ｉがオブジェクト集合Ｓの要素数以下と判定された場合、初期クラスタリング部１１２は、集合Ｃ０（ｈ（Ｓｉ））が存在するか否かを判定する（ステップＳ４０３）。
【０１３９】
ここで、ハッシュ値ｈ（Ｓｉ）は、処理対象であるオブジェクトＳｉのハッシュ値である。すなわち、集合Ｃ０（ｈ（Ｓｉ））は、ハッシュ値がｈ（Ｓｉ）である初期クラスタの集合である。したがって、ステップＳ４０３では、処理対象のオブジェクトＳｉのハッシュ値ｈ（Ｓｉ）が、初めて処理されるハッシュ値であるか否かが判定される。
【０１４０】
集合Ｃ０（ｈ（Ｓｉ））が存在すると判定された場合、初期クラスタリング部１１２は、ステップＳ４０５に進む。
【０１４１】
集合Ｃ０（ｈ（Ｓｉ））が存在しない、すなわち、初めて処理されるハッシュ値であると判定された場合、初期クラスタリング部１１２は、集合Ｃ０（ｈ（Ｓｉ））を空集合として設定して、ステップＳ４０５に進む（ステップＳ４０４）。
【０１４２】
初期クラスタリング部１１２は、集合Ｃ０（ｈ（Ｓｉ））を集合Ｃとして設定し、さらに、変数ｊを「１」に設定する（ステップＳ４０５）。ステップＳ４０５の処理は、処理対象のオブジェクトＳｉを追加する初期クラスタとして、ハッシュ値が同一である初期クラスタを選択したことを意味する。なお、変数ｊは、１から｜Ｃ｜までの実数を表す。
【０１４３】
次に、初期クラスタリング部１１２は、変数ｊが集合Ｃの要素数より大きいか否かを判定する（ステップＳ４０６）。すなわち、集合Ｃに含まれるすべての初期クラスタに対して処理が終了したか否かが判定される。
【０１４４】
変数ｊが集合Ｃの要素数以下と判定された場合、初期クラスタリング部１１２は、集合Ｃに含まれる初期クラスタの中から、比較対象の初期クラスタＳ’を選択し、また、変数ｊを「１」加算する（ステップＳ４０７）。
【０１４５】
ここで、初期クラスタＳ’は、オブジェクトをマージした集合、すなわち、複数のオブジェクトの和集合であり、当該初期クラスタＳ’は属性の集合である。したがって、初期クラスタＳ’もオブジェクトと同様に扱うことができる。
【０１４６】
次に、初期クラスタリング部１１２は、処理対象のオブジェクトＳｉと選択された初期クラスタＳ’とが類似するか否かを判定する（ステップＳ４０８）。具体的には、以下のような処理が実行される。
【０１４７】
まず、初期クラスタリング部１１２は、オブジェクトＳｉと選択された初期クラスタＳ’とを入力として類似性判定部１１１を呼び出す。呼び出された類似性判定部１１１は、前述した判定方法に基づいて、オブジェクトＳｉと選択された初期クラスタＳ’とが類似するか否かを判定する。さらに、類似性判定部１１１は、判定の結果を初期クラスタリング部１１２に出力する。
【０１４８】
初期クラスタリング部１１２は、入力された判定の結果に基づいて、オブジェクトＳｉと選択された初期クラスタＳ’とが類似するか否かを判定する。オブジェクトＳｉと選択された初期クラスタＳ’とが類似しないと判定された場合、初期クラスタリング部１１２は、ステップＳ４０６に戻り同様の処理を実行する。
【０１４９】
オブジェクトＳｉと選択された初期クラスタＳ’と類似すると判定された場合、初期クラスタリング部１１２は、初期クラスタＳ’にオブジェクトＳｉをマージし（ステップＳ４０９）、変数ｉを「１」加算し（ステップＳ４１１）、ステップＳ４０２に戻り同様の処理を実行する。具体的には、初期クラスタリング部１１２は、初期クラスタＳ’とオブジェクトＳｉとの和集合を新たな初期クラスタＳ’として生成する。
【０１５０】
ステップＳ４０６において、変数ｊが集合Ｃの要素数より大きいと判定された場合、初期クラスタリング部１１２は、オブジェクトＳｉを新たな初期クラスタとして集合Ｃに追加し（ステップＳ４１０）、変数ｉを「１」加算し（ステップＳ４１１）、ステップＳ４０２に戻り同様の処理を実行する。具体的には、集合ＣとオブジェクトＳとを加えた集合を新たな集合Ｃとする。
【０１５１】
ステップＳ４１０の処理は、オブジェクトＳｉに追加するクラスタがないため、当該オブジェクトＳｉを新たなクラスタとして設定するための処理である。
【０１５２】
なお、集合Ｃが大きくなり処理に時間を要する場合は、ｑの値を変更した別のハッシュ関数ｈを用いて、オブジェクトＳｉに類似する可能性のある初期クラスタを絞り込んでもよい。
【０１５３】
前述した処理によって、互いに類似するオブジェクトのうち、ハッシュ値ｈ（Ｓｉ）が同一のオブジェクトがマージされた初期クラスタ１２１が生成される。
【０１５４】
次に、最終クラスタ１２２の生成処理について説明する。
【０１５５】
図５は、本発明の第１の実施形態における最終クラスタ１２２の生成処理を説明するフローチャートである。
【０１５６】
当該処理では、クラスタマージ部１１３が、類似するハッシュ値ｈ（Ｓｉ）を取り得るオブジェクトを含む、複数の初期クラスタ１２１をマージすることによって、最終クラスタ１２２を生成する。ここで、複数の初期クラスタ１２１をマージするとは、各初期クラスタ１２１の和集合を生成することを表す。
【０１５７】
クラスタマージ部１１３は、初期クラスタ１２１の中から、処理対象とする初期クラスタＳ０を選択し、選択された初期クラスタＳ０に対して、以下で説明する処理を実行する。
【０１５８】
クラスタマージ部１１３は、初期クラスタＳ０を選択した後、変数ｉを「１」に設定し、さらに、当該初期クラスタＳ０が取り得るハッシュ値の集合Ｈ（Ｓ０）を変数Ｈに設定する（ステップＳ５０１）。ステップＳ５０１の処理は、クラスタＳ０のハッシュ値と類似する範囲を特定することに対応する。
【０１５９】
集合Ｈは、初期クラスタＳ０において、順位ａが下式（２８）を満たす属性のＩＤ番号を要素とする集合である。
【０１６０】
【数２８】
0005716966.tif 000029
【０１６１】
このとき、初期クラスタＳ０とは別の初期クラスタＳ’が、初期クラスタＳ０と共通のグループＧから生成され、かつ、ハッシュ値ｈ（Ｓ’）が初期クラスタＳ０に含まれる場合、ハッシュ値ｈ（Ｓ’）は集合Ｈに含まれる。その理由を以下で説明する。
【０１６２】
任意の二つの初期クラスタＳ０、Ｓ’が、共通のグループＧから高々Ｒ個の要素を削除して得られた集合である場合、前述のようにハッシュ値ｈ（Ｓ０）とハッシュ値ｈ（Ｓ’）とは、グループＧの高々Ｒ個の要素のいずれかの値となる。ハッシュ値ｈ（Ｓ０）、ｈ（Ｓ’）の、グループＧにおける順位をそれぞれａ１、ａ２とした場合、順位ａ１、ａ２は、下式（２９）を満たす。
【０１６３】
【数２９】
0005716966.tif 000030
【０１６４】
一方、グループＧの（ａ１−Ｒ）番目から（ａ１＋Ｒ）番目までの値は、クラスタＳ０において（ｃｅｉｌ（ｑ×｜Ｓ０｜）−Ｒ）番目から（ｃｅｉｌ（ｑ×｜Ｓ０｜）＋Ｒ）番目の値のいずれかとなる。
【０１６５】
したがって、ハッシュ値ｈ（Ｓ’）がクラスタＳ０の要素である場合、ハッシュ値ｈ（Ｓ’）は初期クラスタＳ０において（ｃｅｉｌ（ｑ×｜Ｓ０｜）−Ｒ）番目から（ｃｅｉｌ（ｑ×｜Ｓ０｜）＋Ｒ）番目の値のいずれかであり、これらの値の集合Ｈ（Ｓ０）を集合Ｈとすればよい。
【０１６６】
ただし、ハッシュ値ｈ（Ｓ０）が初期クラスタＳ’の要素でなく、かつ、ハッシュ値ｈ（Ｓ’）が初期クラスタＳ０の要素でない場合、初期クラスタＳ０と初期クラスタＳ’は共通のグループＧに由来することが見落とされてしまう。
【０１６７】
しかし、ハッシュ値ｈ（Ｓ０）が初期クラスタＳ’の要素でない確率、及び、ハッシュ値ｈ（Ｓ’）が初期クラスタＳ０の要素でない確率は、共に下式（３０）に示すようになる。そのため、前述した両方の条件が成立する確率は、下式（３１）のようになる。したがって、Ｒが下式（３２）を満たすならば、前述の両方の条件が成立する確率を小さい。
【０１６８】
【数３０】
0005716966.tif 000031
【０１６９】
【数３１】
0005716966.tif 000032
【０１７０】
【数３２】
0005716966.tif 000033
【０１７１】
また、データ量が多いとき、初期クラスタＳ０、Ｓ’はいずれも多くのオブジェクトがマージされたものであるため、グループＧの多くの要素を含むことが期待される。したがって、前述の両方の条件が成立しない確率は、式（３１）よりはるかに小さいことが期待される。
【０１７２】
図５の説明に戻る。
【０１７３】
クラスタマージ部１１３は、変数ｉが集合Ｈの要素数より大きいか否か、すなわち、すべてのハッシュ値について処理が完了したか否かを判定する（ステップＳ５０２）。変数ｉが集合Ｈの要素数より大きいと判定された場合、クラスタマージ部１１３は、処理を終了する。
【０１７４】
変数ｉが集合Ｈの要素数以下と判定された場合、クラスタマージ部１１３は、集合Ｈの要素Ｈｉを一つ選択して、集合Ｃ０（Ｈｉ）を集合Ｃとして設定し、変数ｉを「１」加算し、さらに、変数ｊを「１」に設定する（ステップＳ５０３）。
【０１７５】
次に、クラスタマージ部１１３は、変数ｊが集合Ｃの要素数より大きいか否かを判定する（ステップＳ５０４）。すなわち、集合Ｃ０（Ｈｉ）に含まれるすべての初期クラスタに対して処理が終了したか否かが判定される。
【０１７６】
変数ｊが集合Ｃの要素数より大きいと判定された場合、クラスタマージ部１１３は、ステップＳ５０２に戻り同様の処理を実行する。
【０１７７】
変数ｊが集合Ｃの要素数以下と判定された場合、クラスタマージ部１１３は、集合Ｃ（Ｈｉ）に含まれる要素である初期クラスタＣ［ｊ］を選択して、処理対象となるクラスタＳ’として設定し、さらに、変数ｊを「１」加算する（ステップＳ５０５）。
【０１７８】
次に、クラスタマージ部１１３は、初期クラスタＳ０と初期クラスタＳ’とが類似するか否かを判定する（ステップＳ５０６）。なお、ステップＳ５０６の処理は、ステップＳ４０８と同一の方法を用いる。
【０１７９】
初期クラスタＳ０と初期クラスタＳ’とが類似しないと判定された場合、クラスタマージ部１１３は、ステップＳ５０４に戻り同様の処理を実行する。
【０１８０】
初期クラスタＳ０と初期クラスタＳ’とが類似すると判定された場合、クラスタマージ部１１３は、初期クラスタＳ０と初期クラスタＳ’とが類似することを示す集合Ｌを生成する（ステップＳ５０７）。
【０１８１】
すべての初期クラスタに対して処理が実行された後、集合Ｌにはすべての類似する初期クラスタが記録される。クラスタマージ部１１３は、集合Ｌに基づいて、例えば、公知の単連結法（ｓｉｎｇｌｅ  ｌｉｎｋａｇｅ  ｃｌｕｓｔｅｒｉｎｇ）を適用することによって、互いに類似する初期クラスタをまとめて最終クラスタ１２２を生成できる。
【０１８２】
なお、集合Ｌに含まれる初期クラスタの類似関係を示す情報の探索方法には、公知の２分探索、及び前記ハッシュ関数等を用いることができる。
【０１８３】
なお、図４及び図５の示す処理は一例であって、本発明はこれに限定されない。例えば、データ分析装置１００は、算出されたハッシュ値に基づいて、ハッシュ値が同一のオブジェクトを収集して集合を生成する処理と、生成された集合に含まれるオブジェクトを比較し、類似するオブジェクトをマージする処理とを実行すれば初期クラスタ１２１を生成できる。また、データ分析装置１００は、ハッシュ値が所定の範囲内にある初期クラスタ１２１を収集して集合を生成する処理と、生成された集合に含まれる初期クラスタ１２１を比較し、類似する初期クラスタ１２１をマージする処理とを実行すれば最終クラスタ１２２を生成できる。
【０１８４】
本実施形態では、ハッシュ値が同一であり、かつ、類似するオブジェクトの和集合を初期クラスタ１２１としたが、本発明はこれに限定されない。例えば、ハッシュ値が同一のオブジェクトを初期クラスタ１２１として定義してもよい。これによって、処理の高速化を実現できる。この場合、ステップＳ４０５の処理が実行された後、ステップＳ４１０の処理を実行すればよい。
【０１８５】
なお、本実施形態で例示した種々のソフトウェアは、電磁的、電子的及び光学式等の種々の記録媒体に格納可能であり、インターネット等の通信網を通じて、コンピュータにダウンロード可能である。
【０１８６】
以上のように、第１の実施形態では、ハッシュ値が同一のものに限らず、ハッシュ値が類似するクラスタをさらにまとめることによって、類似する可能性のあるオブジェクトを高速に特定できる。
【０１８７】
（第２の実施形態）
第２の実施形態では、ＲＤＦに対してデータ分析装置１００を適用した場合について説明する。以下、第１の実施形態との差異を中心に説明する。
【０１８８】
前述したように、ＲＤＦグラフの各ノードＮは、エッジのＵＲＩ集合によって特徴づけられるオブジェクトとみなすことができる。このとき、図８Ａに示すように、エッジのＵＲＩが属性に対応し、集合ＵはすべてのエッジのＵＲＩの集合に対応する。
【０１８９】
図６は、本発明の第２の実施形態におけるデータ分析装置１００の構成例を示すブロック図である。
【０１９０】
データ分析装置１００のハードウェア構成は、第１の実施形態と同一であるため説明を省略する。第２の実施形態ではソフトウェア構成が異なる。具体的には、データ分析装置１００は、新たにＲＤＦ変換部６００を備える。その他のソフトウェア構成は第１の実施形態と同一であるため説明を省略する。
【０１９１】
ＲＤＦ変換部６００は、ＲＤＦにおける各ノードＮをオブジェクトに変換する。各オブジェクトの要素は、ノードＮから伸びるエッジのＵＲＩとする。
【０１９２】
したがって、第２の実施形態では、ＲＤＦ変換部６００によって変換されたオブジェクト集合を入力とし、最終クラスタ１２２が生成される。
【０１９３】
なお、最終クラスタ１２２を生成するための方法は、第１の実施形態と同一であるため説明を省略する。
【０１９４】
（第３の実施形態）
処理対象とするデータは永続的なものとは限らず、応用によっては、新規データが次々に出現することも考えられる。そこで、第３の実施形態では、初期クラスタ１２１及び最終クラスタ１２２が生成された後に、新たなオブジェクトが入力された場合に、当該オブジェクトと類似するオブジェクトを含む初期クラスタ１２１及び最終クラスタ１２２を高速に特定する。
【０１９５】
なお、データ分析装置１００の構成は、第１の実施形態と同一であるため説明を省略する。
【０１９６】
第３の実施形態では、新たに初期クラスタ１２１を生成する必要は無いため図４に示す処理を省略できる。
【０１９７】
新規オブジェクトｓが入力されると、まず図４のステップＳ４０３〜Ｓ４０９においてＳｉをｓに置き換えた処理によって、ｓに類似する初期クラスタを特定し、ｓをマージする。この初期クラスタをＳ０とみなして図５に示す処理が実行される。これによって、新規オブジェクトｓに類似するオブジェクトを含む初期クラスタ１２１を特定でき、また集合Ｌによって、最終クラスタも特定できる。
【０１９８】
以上、本発明の各実施形態について説明したが、前述した実施形態は本発明の適用例を示したものであり、本発明の技術的範囲を前述した各実施形態の具体的構成に限定する趣旨ではない。本発明の要旨を逸脱しない範囲において種々変更可能である。
【符号の説明】
【０１９９】
１００  データ分析装置
１０１  ＣＰＵ
１０２  主記憶装置
１０３  補助記憶装置
１０４  リムーバブルドライブ
１０６  ユーザインタフェース
１０７  ネットワークインタフェース
１１０  ハッシュ値算出部
１１１  類似性判定部
１１２  初期クラスタリング部
１１３  クラスタマージ部
１２０  オブジェクト集合
１２１  初期クラスタ
１２２  最終クラスタ
１３０  外部記憶装置
１４０  ネットワーク
６００  ＲＤＦ変換部
【図１】
0005716966.tif 000037
【図２】
0005716966.tif 000038
【図３】
0005716966.tif 000039
【図４】
0005716966.tif 000040
【図５】
0005716966.tif 000041
【図６】
0005716966.tif 000042
【図７】
0005716966.tif 000043
【図８Ａ】
0005716966.tif 000044
【図８Ｂ】
0005716966.tif 000045
【図９Ａ】
0005716966.tif 000046
【図９Ｂ】
0005716966.tif 000047
【図１０】
0005716966.tif 000048