(57)【要約】  複数の要素を含むデータ集合の集合間距離を要素間距離の線形和として算出する装置と計算方法を提供する。２つの集合AとBが与えられると、AとBの差集合、AとBの積集合、BとAの差集合の３つの部分集合に分け、各部分集合間で要素間距離の和を計算し、AとBとその和集合の各要素数の逆数から計算される係数を掛けて線形和を算出し、その値をAとBの距離とする。要素間距離が擬距離ならば、この集合間距離も擬距離となり、データ集合間の類似性を比較するための正確な評価基準として利用できる。文書データ、画像データ、音声データ、映像データ、化学物質データ、生物の遺伝子データ、経済指標データ、位置情報データ、気象データ、観測データなどの様々な種類のデータ集合に対して、類似データの検索、分類、パターン認識、クラスタ解析、データマイニング、機械学習などに応用可能である。【特許請求の範囲】
【請求項１】
データ集合に含まれる要素の要素間距離を利用してデータ集合の集合間距離を算出するデータ集合間距離算出装置であって、
データ集合の要素と要素間距離を記憶する記憶装置と
データ集合同士の集合演算と距離の数値計算を行う演算装置を備え、
前記演算装置は、
第１のデータ集合と第２のデータ集合の積集合と、前記第１のデータ集合と前記第２のデータ集合の第１の差集合と、前記第２のデータ集合と前記第１のデータ集合の第２の差集合を計算する手段と、
前記第１の差集合の要素から前記第２の差集合の要素への要素間距離の第１の和と、前記積集合の要素から前記第２の差集合の要素への要素間距離の第２の和と、前記第１の差集合の要素から前記積集合の要素への要素間距離の第３の和を計算する手段と、
前記第１の和と前記第２の和と前記第３の和の線形和を算出してその値を前記第１のデータ集合と前記第２のデータ集合の集合間距離として算出する手段
を有することを特徴とするデータ集合間距離算出装置。
【請求項２】
請求項１のデータ集合間距離算出装置の演算装置において、
第１の要素を含む集合を要素として含む第１の集合族と第２の要素を含む集合を要素として含む第２の集合族との集合族間距離を計算し、その値を前記第１の要素と前記第２の要素の要素間距離として算出する手段をさらに有することを特徴とするデータ集合間距離算出装置。
【請求項３】
データ集合に含まれる要素の要素間距離を利用してデータ集合の集合間距離を算出するデータ集合間距離算出方法であって、
第１のデータ集合と第２のデータ集合の積集合と、前記第１のデータ集合と前記第２のデータ集合の第１の差集合と、前記第２のデータ集合と前記第１のデータ集合の第２の差集合を求めるステップと、
前記第１の差集合の要素から前記第２の差集合の要素への要素間距離の第１の和と、前記積集合の要素から前記第２の差集合の要素への要素間距離の第２の和と、前記第１の差集合の要素から前記積集合の要素への要素間距離の第３の和を算出するステップと、
前記第１の和と前記第２の和と前記第３の和の線形和を算出してその値を前記第１のデータ集合と前記第２のデータ集合の集合間距離として算出するステップ
を有することを特徴とするデータ集合間距離算出方法。
【請求項４】
請求項３のデータ集合間距離算出方法の線形和の算出において、
前記第２の和の係数が第１の積因子として前記第１のデータ集合と前記第２のデータ集合の和集合の濃度の逆数を含み、かつ、第２の積因子として前記第１のデータ集合の濃度の逆数を含み、
前記第３の和の係数が前記第１の積因子を含み、かつ、第３の積因子として前記第２のデータ集合の濃度の逆数を含み、
前記第１の和の係数が前記第２の和の係数と前記第３の和の係数の和に等しいことを特徴とするデータ集合間距離算出方法。
【請求項５】
請求項３のデータ集合間距離算出方法の線形和の算出において、
前記第１の和の係数と前記第２の和の係数と前記第３の和の係数がともに前記第１のデータ集合の濃度と前記第２のデータ集合の濃度との積の逆数を積因子として含むことを特徴とするデータ集合間距離算出方法。
【請求項６】
請求項３のデータ集合間距離算出方法において、
第１の要素を含むすべての集合を要素として含む第１の集合族と第２の要素を含むすべての集合を要素として含む第２の集合族との集合族間距離を計算し、その値を前記第１の要素と前記第２の要素の要素間距離として算出するステップをさらに有することを特徴とするデータ集合間距離算出方法。
【請求項７】
データ集合に含まれる要素の要素間距離を利用してデータ集合の集合間距離を算出するデータ集合間距離算出方法であって、
第１のデータ集合と第２のデータ集合の和集合から一部の要素を取り出して標本を抽出するステップと、
その標本を、前記第１のデータ集合と前記第２のデータ集合の第１の差集合に含まれる第１の部分集合と、前記第１のデータ集合と前記第２のデータ集合の積集合に含まれる第２の部分集合と、前記第２のデータ集合と前記第１のデータ集合の第２の差集合に含まれる第３の部分集合の３つの部分集合に分割するステップと、
前記第１の部分集合の要素から前記第３の部分集合の要素への要素間距離の第１の和と、前記第２の部分集合の要素から前記第３の部分集合の要素への要素間距離の第２の和と、前記第１の部分集合の要素から前記第２の部分集合の要素への要素間距離の第３の和を算出するステップと、
前記第１の和と前記第２の和と前記第３の和の線形和を算出してその値を前記第１のデータ集合と前記第２のデータ集合の集合間距離として算出するステップを備えたことを特徴とするデータ集合間距離算出方法。
【請求項８】
請求項７のデータ集合間距離算出方法の線形和の算出において、
前記第２の和の係数が第１の積因子として前記標本に含まれる要素の数の逆数を含み、かつ、第２の積因子として前記第１の部分集合と前記第２の部分集合の和集合の濃度の逆数を含み、
前記第３の和の係数が前記第１の積因子を含み、かつ、第３の積因子として前記第２の部分集合と前記第３の部分集合の和集合の濃度の逆数を含み、
前記第１の和の係数が前記第２の和の係数と前記第３の和の係数の和に等しいことを特徴とするデータ集合間距離算出方法。
【請求項９】
請求項７のデータ集合間距離算出方法において、さらに、
前記第１のデータ集合と前記第２のデータ集合の和集合からすでに標本抽出された要素とは異なる一部の要素を取り出して標本に追加する第１のステップと、
その追加分の要素の中で、前記第１の差集合にも含まれる要素を前記第１の部分集合に、前記積集合にも含まれる要素を前記第２の部分集合に、前記第２の差集合にも含まれる要素を前記第３の部分集合に追加配分する第２のステップと、
前記第１の部分集合の要素から前記第３の部分集合の要素への要素間距離の第１の和と、前記第２の部分集合の要素から前記第３の部分集合の要素への要素間距離の第２の和と、前記第１の部分集合の要素から前記第２の部分集合の要素への要素間距離の第３の和を更新する第３のステップと、
前記第１の和と前記第２の和と前記第３の和の線形和を算出してその値を前記第１のデータ集合と前記第２のデータ集合の集合間距離として算出する第４のステップと、
標本を追加する前の集合間距離の算出値と追加した後の集合間距離の算出値について収束判定を行う第５のステップとを備え、
第５のステップにおいて終了条件を満たしていない場合には前記第１のステップから前記第５のステップまでを繰り返すことを特徴とするデータ集合間距離算出方法。
【請求項１０】
請求項３、４、５、６、７、８、９のいずれか１項に記載のデータ集合間距離算出方法の各ステップをコンピュータに実行させるためのプログラムとしたことを特徴とするデータ集合間距離算出プログラム。
【請求項１１】
請求項１０に記載のプログラムを当該コンピュータが読み取りできる記録媒体に記録したことを特徴とするデータ集合間距離算出プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータを要素とするデータ集合、例えば、複数の単語や文を要素とするテキストデータ集合、複数の文章や画像を要素とするハイパーテキストデータ集合、複数の音素を要素とする音声データ集合、複数の画素やセグメント画像を要素とする画像データ集合や映像データ集合、複数の原子特性や分子特性を要素とする化学データ集合、複数のDNA断片情報や遺伝子情報を要素とする生命情報データ集合、などに対して、データ集合の類似性判定、検索、順位付け、分類、クラスタリング、データベース構築などを行うための判断基準となるデータ集合間距離を算出する装置と方法、プログラムに関するものである。
【背景技術】
【０００２】
複数のデータを要素とするデータ集合としては様々な種類のものがあるが、ここでは、文書データの場合を一例として従来技術を説明する。文書データの基本構成要素を単語とすると、単語の集合が句や文となる。さらに、文を要素とする集合が段落となり、段落の集合が一つの文書となり、複数の文書がさらに上位階層の集合を構成する。それぞれの階層において、様々なデータ集合の集合間距離を算出し、その値の大小に基づいて類似文書検索や分類などを行う文書処理技術が開発されている。なお、データの表現形式としては単純な集合の他に、集合族（集合の集合）、ベクトル、グラフなども処理内容に応じて利用されているが、集合は最も基本的なデータ表現形式であり、複雑なデータ構造を集合の形式で表現することも可能である。【０００３】
集合間距離の算出方法の一つとして、２つの集合 A と B の対称差の濃度に着目して、次式により算出する方法がある。
【数１】
2012029152.tif 000002
【数２】
2012029152.tif 000003
ここで、A∪B はAとBの和集合、A∩B はAとBの積集合、A＼B はAとBの差集合、A△B はAとBの対称差を表し、|A| はAの濃度を表す。Aが有限集合の場合、Aの濃度はAの要素の個数を表す。すなわち、集合間距離 Dsyd(A, B) は A∪B に含まれる要素から A∩B に含まれる要素を除いた差集合 (A∪B)＼(A∩B) の要素の数、いいかえると、AとBのいずれか片方にのみ含まれる要素の数を表す。この値の A∪B の要素数に対する比率をとると Djcd(A, B) になる。これらの方法の欠点は、各要素の有無のみが計数されており、各要素の重要性の違いが反映されていないことである。【０００４】
集合はベクトルに対応付けることもできるので、対応するベクトル間距離を集合間距離とみなすこともできる。例えば、全体集合 {e1, e2, e3, …} の各要素に対応する成分を持つベクトル(v1, v2, v3, …)を対応させる場合、Aがeiを含む（ei ∈ A）ならば vi = 1、含まなければ vi = 0 とする。こうすると、上記の Dsyd(A, B) はAとBのそれぞれに対応する0と1からなる２つの数値ベクトル同士のハミング距離と等しい。この観点から比較すべき従来技術として、文書データの検索や分類に利用されるTFIDF法がある。この方法では、各集合に含まれる要素に対応する成分の値は0と1の２値のみではなく、その要素の重要度を表す数値が設定されており、各要素の重要度の違いが反映されたベクトル間距離を計算する。しかし、異なる成分間すなわち異なる要素間の相互関係（文書データの場合は単語間の類似性や距離）が反映されていないことがこの方法の欠点である。【０００５】
同種のデータ集合のクラスタに関する特徴分析や分類を行うクラスタ解析の従来技術においては、集合間の距離を集合に含まれる要素の要素間距離を利用して算出する方法が利用されている。例えば、２つの集合AとBに含まれる要素をそれぞれ a∈A、b∈B、その要素間距離を d(a, b) とすると、AとBの集合間距離を d(a, b) の最小値と定義する最短距離：
【数３】
2012029152.tif 000004
あるいは、 d(a, b) の最大値と定義する最長距離：
【数４】
2012029152.tif 000005
として算出する方法がある。この２つの方法の欠点は、集合間距離が要素間距離の最小値または最大値に関係する一部の要素のみの性質に依存し、集合に含まれる全要素の全体的な性質をあまり反映していないことである。それに対して、集合の全要素の性質を反映させる距離の算出方法として、要素間距離の平均値と定義する群平均距離：
【数５】
2012029152.tif 000006
を利用する方法もある。数式５では、Σ記号はその下部に示された集合の全要素について和をとることを表し、集合Aの要素と集合Bの要素との組み合わせのすべてに対する要素間距離の和をその組み合わせの総数で割る計算をしている。この計算式ではすべての要素が関係しているが、AとBが同じ集合であっても、多くの場合、その距離が0にならないという欠点がある。【０００６】
一般に、距離の概念は自然法則における空間中の２点間の距離の性質に基づいている。例えば、「２点が同じ位置ならばその間の距離は0である」、「異なる３点を結ぶ三角形の各辺の長さを各辺の端点間距離とすると、２つの辺の長さの合計は残りの辺の長さより長いかまたは等しい（三角不等式）」などの性質がある。このような性質を利用するためには、集合間距離が任意の集合A、B、Cに対して、下記の４つの性質をすべて満たすことが望まれる。
（性質１）： D(A, B) ≧ 0
（性質２）： D(A, A) = 0
（性質３）： D(A, B) = D(B, A)
（性質４）： D(A, B) + D(B, C) ≧ D(A, C)
これら４つの性質を満たすDは擬距離と呼ばれている。要素間距離 d(a, b) が擬距離である場合、前記の Dmin(A, B) と Dmax(A, B) は性質１、２、３を満たすが、性質４を満たさず、Davg(A, B) は性質１，３、４を満たすが、性質２を満たさない。集合間距離がこれらの性質を満たさない場合は、多数の集合間の遠近関係で不整合を生じやすく、それを基に集合の順位付けや分類を行うと、矛盾する結果を生じる可能性が高いという欠点がある。【０００７】
画像データや音声データなどの類似性評価の従来技術としては、上記の性質のすべてを満たすハウスドルフ距離がよく利用されている。この距離の計算式は集合の要素が有限個の場合、下記の式で表される。
【数６】
2012029152.tif 000007
この式は、Aの要素 a を行に配置し、Bの要素 b を列に配置して、要素間距離 d(a, b) を距離行列として表現した場合、各行内での最小値を行間で比較したときの最大値と各列内での最小値を列間で比較したときの最大値の２つの最大値のいずれか大きい方の値を求めることを意味する。このため、ハウスドルフ距離では、最小値や最大値を求める過程で多くの要素間距離の平均的な情報が切り捨てられ、集合全体の詳細な性質が距離に反映されず、ノイズやはずれ値などの異常なデータの影響を受けやすいという欠点がある。【０００８】
上記の従来技術に関しては、様々な距離算出方法の事例が非特許文献１に網羅的に解説されている。また、特許文献１（特許第4356347号）にはTFIDF法を利用した文書クラスタリング、特許文献２（特許第4314271号）には単語の共起頻度に基づく距離の算出方法、特許文献３（特許第4305836号）には最短距離法、最長距離法、群平均法等によるクラスタリングを利用したコンテンツ検索法、特許文献４（特許第4225812号）にはハウスドルフ距離を用いた音楽データの比較、特許文献５（特許第4098845号）と特許文献６（特許第3766186号）にはハウスドルフ距離を用いた文書画像データの比較、特許文献７（特許第3561345号）には遺伝アルゴリズム評価のための群平均法によるクラスタ解析、特許文献８（米国特許7672952）にはハウスドルフ距離を用いた文書データの内容比較、特許文献９（米国特許6625585）には化学物質データの階層型クラスタリング、特許文献１０（米国特許6246982）には音声データ分布間の距離計算、特許文献１１（米国特許5999653）にはハウスドルフ距離を用いた画像検索、特許文献１２（米国特許5832182）には各種の距離関数を利用した大規模データベースのクラスタリングが記載されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第4356347号
【特許文献２】特許第4314271号
【特許文献３】特許第4305836号
【特許文献４】特許第4225812号
【特許文献５】特許第4098845号
【特許文献６】特許第3766186号
【特許文献７】特許第3561345号
【特許文献８】米国特許 7672952
【特許文献９】米国特許 6625585
【特許文献１０】米国特許 6246982
【特許文献１１】米国特許 5999653
【特許文献１２】米国特許 5832182
【非特許文献】
【００１０】
【非特許文献１】M. M. Deza & E. Deza ”Encyclopedia of Distances” Springer, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
解決しようとする問題点は、集合間距離を集合に含まれる要素の要素間距離に基づいて決定する方法において、自然法則における距離の性質を満たすとともに、集合に含まれる要素全体についての要素間距離の平均的特徴を反映した距離を算出する方法がなかった点である。
【課題を解決するための手段】
【００１２】
本発明は前記課題を解決するために、集合AとBの集合間距離 D(A, B) の計算式において、集合AとBを積集合 A∩B と２つの差集合 A＼B、B＼A の３つの部分集合に分割し、各部分集合間の要素間距離 d(a, b) に重み係数を掛けて荷重平均を求める計算式を用いて集合AとBの距離を算出することを最も主要な特徴とする。その典型的な計算式を次式で示す。
【数７】
2012029152.tif 000008
ここで、w1、w2、w3 は正の値を持つ重み係数を表す。右辺第１項では差集合 A＼B と B＼A の各要素の組み合わせのすべてに対応する要素間距離の和を計算し、右辺第２項では積集合 A∩B と B＼A の各要素の組み合わせのすべてに対応する要素間距離の和を計算し、右辺第３項では差集合 A＼B と積集合 A∩B の各要素の組み合わせのすべてに対応する要素間距離の和を計算し、それぞれに重み係数を掛けて総和をとっている。【００１３】
要素間距離 d(a, b) が擬距離の性質を満たす場合、D(A, B) は非負の値をとり、前記性質１を満たす。また、AとBが等しいとき、すなわち A = B のとき、差集合 A＼B と B＼A はともに空集合になるので、D(A, B) = 0 となり、前記性質２を満たす。AとBを入れ替えても同じ式になるので、性質３も満たす。さらに、重み係数 w1、w2、w3 を集合AとBならびに和集合 A∪B の各要素数 |A|、|B|、|A∪B| を用いて、
【数８】
2012029152.tif 000009
とすると前記性質４を満たす。すなわち、AとBの和集合の濃度の逆数を第１の積因子、Aの濃度の逆数を第２の積因子、Bの濃度の逆数を第３の積因子とすると、第２項の係数 w2 は第１の積因子と第２の積因子を含み、第３項の係数 w3 は第１の積因子と第３の積因子を含み、第1項の係数 w1 は第２項の係数と第３項の係数の和とする。あるいは、各重み係数に同じ正定数を掛けた計算式を用いても良い。なお、数式７、８は下記の数式と同等である。
【数９】
2012029152.tif 000010
この数式は、集合Aから差集合 B＼A までの要素間距離の群平均距離と集合Bから差集合 A＼B までの要素間距離の群平均距離にそれぞれ係数として |B＼A|/|A∪B| と |A＼B|/|A∪B| を掛けて和をとった値が集合間距離として計算されることを表している。ただし、数式９の計算では差集合 A＼B から差集合 B＼A までの要素間距離の和の計算が第１項と第２項で重複しているので、数式７の計算式を用いた方が計算の無駄が少なく、効率がよい。【００１４】
厳密な数値を算出する必要がない場合は、D(A, B) の近似計算でもよい。例えば、集合AとBの交わりが比較的に小さく、|A∩B|≪|A∪B| となるときには、３つの重み係数をともにAとBの各濃度の積の逆数として次式を使用してもよい。
【数１０】
2012029152.tif 000011
【００１５】
集合の要素数が多い場合は統計学に基づくサンプリングによる近似計算を行ってもよい。すなわち、和集合 A∪B に含まれる要素の一部を取り出して標本 S を抽出し、それを差集合 A＼B の部分集合 S1、積集合 A∩B の部分集合 S2、差集合 B＼A の部分集合 S3 に分割して次式を計算する。
【数１１】
2012029152.tif 000012
ここで、S ⊂ A∪B、S1 = S∩A＼B、S2 = S∩A∩B、S3 = S∩B＼A であり、重み係数は
【数１２】
2012029152.tif 000013
すなわち、Sの濃度の逆数を第１の積因子、S1とS2の和集合の濃度の逆数を第２の積因子、S2とS3の和集合の濃度の逆数を第３の積因子とすると、第２項の係数 w2 は第１の積因子と第２の積因子を含み、第３項の係数 w3 は第１の積因子と第３の積因子を含み、第1項の係数 w1 は第２項の係数と第３項の係数の和とする。あるいは、それぞれに同じ正定数を掛けた値でも良い。【００１６】
要素間距離 d(a, b) の値は従来技術を利用して事前に与えられたものであってもよいが、事前に与えられていない場合は、集合の具体的事例データに基づいて要素間距離を算出してもよい。例えば、要素 a を含む集合 A の集合族 c(a) = {A|a∈A} と要素 b を含む集合 B の集合族 c(b) = {B|b∈B} をそれぞれ集合を要素とする上位の集合とみなして
【数１３】
2012029152.tif 000014
により計算された値を用いてもよい。あるいは、上記 d(a, b) の値に正定数を乗じた値や、計算式 d(a, b)/|c(a)∪c(b)| または d(a, b)/(1 + d(a, b)) の値、さらにはそれらの線形和の値を要素間距離としても良い。【００１７】
集合間距離の値が与えられれば、c(a) と c(b) の距離は数式７を応用して次式のように算出することができる。
【数１４】
2012029152.tif 000015
この値を a と b の要素間距離とみなして、dc(a, b) = D(c(a), c(b)) により集合間距離から要素間距離を算出し、元々の要素間距離 d(a, b) を dc(a, b) で置き換えても良い。さらに、数式７で要素間距離から集合間距離を算出することと、数式１４で集合間距離から要素間距離を算出することを交互に数回繰り返して各距離の値を更新してもよい。【００１８】
本発明の装置はこのような集合間の距離を算出するために演算装置と記憶装置を備える。記憶装置は集合とそれに含まれる要素の関係を表すデータを記憶するとともに、異なる２つの要素とそれらの要素間距離を表す数値データを記憶する。演算装置は数式７〜１２に示すような数式を用いて集合間の距離を計算する。計算に必要な集合の要素と要素間距離は記憶装置から読み出される。要素間距離の数値データとしては外部から与えられた数値データ、または、記憶装置内の集合と要素の関係データから数式１３，１４に示すような数式を基に演算装置で計算された数値データを利用できる。
【発明の効果】
【００１９】
本発明のデータ集合間距離算出装置および方法はデータ集合に含まれる要素の要素間距離の加重平均値をデータ集合間距離として算出するので、データ集合に含まれるすべての要素の遠近関係の平均的特徴をよく反映し、データのノイズやはずれ値の影響が少ないという利点がある。また、その値が自然法則の距離の性質を満たすことにより、類似性が高いデータ集合同士の距離関係にほとんど矛盾が生じないので、距離の大小に基づいてデータ集合の類似データ検索や分類、クラスタ分析を行う場合に、本発明によるデータ集合間距離は正確な評価基準として利用できるという利点がある。【００２０】
本発明によれば、集合間距離を集合に含まれる要素の要素間距離から算出するので、この方法で得られた集合間距離を利用して、集合を要素とする上位階層の集合族の集合族間距離を算出することができる。例えば、単語の集合としての文、文の集合としての文書、文書の集合としての文書集合など、階層化された複雑な情報を表すデータ集合に対しても、下位のデータ集合間距離を基に上位のデータ集合間距離を算出することができる。また取り扱うことのできる情報の種類としては、文書情報に限らず、画像情報、音声情報、化学物質の特性情報、生物の遺伝情報、各種観測データ、政治・経済・文化・社会分野における各種データなど、広範囲の情報の分析に利用できる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施例の装置構成と動作を示す模式図である。
【図２】本発明の第２の実施例の装置構成と動作を示す模式図である。
【図３】本発明の第３の実施例の方法を示すフローチャートである。
【図４】本発明の第４の実施例の方法を示すフローチャートである。
【図５】本発明の第６の実施例の方法を示すフローチャートである。
【図６】本発明の第７の実施例の方法を示すフローチャートである。
【図７】本発明の第８の実施例の方法を示すフローチャートである。
【発明を実施するための形態】
【００２２】
実施形態を大きく場合分けすると、データ集合を構成する要素の要素間距離が事前に与えられている場合と与えられていない場合がある。そこで、まず前者の場合の装置を実施例１に示し、方法を実施例３に示す。後者の装置は実施例２に示し、その方法は実施例４に示す。次に、集合間距離の近似値を算出する方法として、重み係数を簡単化した場合を実施例５に、要素をサンプリングして統計的な推定値を計算する方法を実施例６，７，８に示す。さらに、本発明の応用例を実施例９，１０，１１に示す。
【実施例１】
【００２３】
図１は本発明装置の構成図と機能の一例を示す。この装置は演算装置 101 と記憶装置 102 からなる。記憶装置 102 には集合とそれに含まれる要素の対応関係、および、異なる要素の組合せとその要素間距離の対応関係を記憶させておく。集合と要素の記憶内容としてはそれらの具体的な情報がすべて記録されている必要はなく、各集合や各要素と一対一に対応する識別記号や識別番号が記憶されていればよい。図１では集合の識別子をA，Bで表し、要素の識別子を a, b, g, h などで表し、要素 a, b の要素間距離を d(a, b) と表している。【００２４】
要素間距離の具体的数値としては、要素に対応づけられている情報の内容や性質に基づいて従来技術を用いて事前に算出された値を記憶させておく。例えば、文書データの集合の要素が単語である場合、すべての要素が N 個あるとき、それらを順番に並べて、e1, e2, …, eN とすると、ある要素 ej に関して、他の要素 ek が同じ集合に属する共起頻度または共起確率の数値 f(ej, ek) を成分とする N 次元数値ベクトル Vj =（vj,1, vj,2, …, vj,N) = (f(ej, e1), f(ej, e2), …, f(ej, eN)) を対応させることができる。そうすると、ある２つの単語間の距離 d(ej, ek) はそれらに対応するベクトル間距離として次式で計算できる。
【数１５】
2012029152.tif 000016
ここで、p は1以上の実数である。また、性質１〜４のすべてを満たす必要がなければ、コサイン距離、マハラノビス距離、カルバック・ライブラー情報量などを要素間距離の計算に用いても良い。【００２５】
集合が他の情報、例えば、画像、音声、映像、遺伝子情報、物性、化学組成、経済指標など、どのような分野の情報を表す場合であっても、それらの要素の特徴は複数の記号または数値あるいはそれらを複合化した組み合わせで表現される。画像や音声、映像情報の場合、それらのコンテンツの特徴を複数のキーワードで表せば、上記の単語を要素とする集合と同じように取り扱うことができる。また、画素の色情報は３原色の明度を表すＲＧＢ値などの数値ベクトルで表すことができ、全画像は画素の２次元配列として表すことができる。形状は円や四角などのキーワードとその位置や大きさを表す数値ベクトルで表される。音声情報は音素、発音記号、単語などに記号化された時系列データや、周波数スペクトル強度の数値ベクトルで表される。遺伝子、物性、化学組成などはそれらの特徴を表す複数の属性データで表される。経済状況や社会現象などは各種の統計データを用いて複数の記号や数値で特徴付けられている。各要素が数値ベクトルに対応づけられていれば、要素間距離は数式１５で示されるようなベクトル間距離で表すことができる。いずれにせよ、実施例１で計算に使用する要素間距離は外部から与えられた数値であって、様々な種類の情報に対応させることができるものである。【００２６】
演算装置 101 では距離を算出する対象となる２つの集合AとBのそれぞれの要素を記憶装置 102 から読み出し、数式７の計算を行うため、それらの要素を積集合 A∩B と２つの差集合 A＼B と B＼A の３つの部分集合に分割する。例えば、A = {a, g, h}、B = {b, g} とすると、A∩B = {g}、A＼B = {a, h}、B＼A = {b} となる。次に、数式７の右辺第１項の A＼B と B＼A の要素間距離の和として Sum1 = d(a, b) + d(h, b)、数式７の右辺第２項の A∩B と B＼A の要素間距離の和として Sum2 = d(g, b)、数式７の右辺第３項の A＼B と A∩B の要素間距離の和として Sum3 = d(a, g) + d(h, g) を計算する。次に、数式８を利用して、それぞれの重み係数を w1 = w2 + w3、w2 = 1/|A∪B||A| = 1/12、w3 = 1/|A∪B||B| = 1/8 として、数式７の線形和 w1×Sum1＋w2×Sum2＋w3×Sum3 を計算してその値を集合間距離として出力する。
【実施例２】
【００２７】
図２は要素間距離が事前に与えられていない場合の実施例を示す。演算装置 201 は記憶装置 202 に記憶されている集合とその要素の組み合わせを読み出して、数式１３を用いて要素間距離を算出し、記憶装置 202 に記憶する。例えば、A = {a, g, h}、B = {b, g}、C = {c, g, h} とすると、数式１３から d(a, b) = 2、d(a, c) = 2、d(a, g) = 2、d(a, h) = 1、d(b, c) = 2、d(b, g) = 2、d(b, h) = 3、d(c, g) = 2、d(c, h) = 1、d(g, h) = 1 となる。その後、実施例１に従うと、D(A, B) = 19/12、D(A, C) = 5/6、D(B, C) = 19/12 と算出される。さらに、数式１４を用いると新たな要素間距離 dc(a, b) = 19/12、dc(a, c) = 5/6、dc(a, g) = 29/36、dc(a, h) = 5/12、dc(b, c) = 19/12、dc(b, g) = 19/18、dc(b, h) = 19/12、dc(c, g) = 29/36、dc(c, h) = 5/12、dc(g, h) = 19/36 が得られる。
【実施例３】
【００２８】
図３は実施例１の演算装置内 101 の数式７の計算に関する処理手続きとして利用される方法のフローチャートを表したものである。すなわち、ステップ 301 では集合AとBを部分集合 A＼B，A∩B，B＼A に分割し、ステップ 302 では A＼B と B＼A の要素間距離の和 Sum1 と、A∩B と B＼A の要素間距離の和 Sum2 と、A＼B と A∩B の要素間距離の和 Sum3 を算出し、ステップ 303 で要素間距離の和 Sum1，Sum2，Sum3 の線形和を集合間距離として算出する。
【実施例４】
【００２９】
図４は実施例２の演算装置内 201 で利用される処理方法のフローチャートを表したものである。すなわち、ステップ 400 で、要素 a を含む集合と要素 b を含む集合の各集合族の対称差から要素間距離 d(a, b) を算出し、その後、実施例３と同様のステップ 401，402，403 を実行する。要素間距離を算出する計算式としては数式１３を用いる。あるいは、この d(a, b) の値に正定数を乗じた値や、計算式 d(a, b)/|c(a)∪c(b)| または d(a, b)/(1 + d(a, b)) の値、それらの線形和の値を要素間距離としても良い。さらには数式１４を用いても良い。
【実施例５】
【００３０】
厳密な数値を必要としない場合には、近似値を算出してもよい。例えば、集合AとBの和集合の要素数に対してその積集合の要素数の割合が十分に少ない場合はステップ 303, 403 の Sum1，Sum2，Sum3 の線形和の計算において、すべての重み係数の値を数式１０で示す一つの同じ値で計算しても良い。
【実施例６】
【００３１】
集合AとBの和集合 A∪B の要素数が多い場合は、ステップ 302, 402 の Sum1，Sum2，Sum3 の算出において、数式７の計算の対象となる要素間距離のすべてを計算することをせず、A∪B に含まれる要素の中から一部の要素を取り出して標本（サンプル）を抽出し、統計的な推定値で近似してもよい。すなわち、図５に示すように、まずステップ 500 において、A∪B の要素から無作為抽出した標本 S（A∪Bの部分集合）を抽出する。次にステップ 501 において、Sを差集合 A＼B の部分集合 S1、積集合 A∩B の部分集合 S2、差集合 B＼A の部分集合 S3 に分割する。それからステップ 502 において、S1 の要素と S3 の要素の組み合わせのすべてに対する要素間距離の和 Sum1、S2 の要素と S3 の要素の組み合わせのすべてに対する要素間距離の和 Sum2、S1 の要素と S2 の要素の組み合わせのすべてに対する要素間距離の和 Sum3 を算出する。その後のステップ 503 において、数式１１に示すように、Sum1，Sum2，Sum3 の線形和 w1×Sum1＋w2×Sum2＋w3×Sum3 を計算する。ここで、重み係数 w1、w2、w3の値としては例えば数式１２を用いた計算値、あるいは、それに正定数を掛けた値でもよい。
【実施例７】
【００３２】
実施例６において、大数の法則が成り立つ場合、標本数が多いほど集合間距離の近似精度が高くなるので、標本を追加しながら、要素間距離の推定値の変化を測定し、変化量が小さくなる条件を満たすまで標本の追加を繰り返す。すなわち、図５に示された実施例６において集合間距離が算出された後に、さらに続いて、図６に示すように、ステップ 600 において、集合AとBの和集合 A∪B の要素から標本を無作為に抽出してSに追加する。次に、ステップ 601 において、Sに追加された要素を差集合 A＼B の部分集合S1、積集合 A∩B の部分集合S2、差集合 B＼A の部分集合S3に追加的に配分する。次にステップ 602 において、S1の要素とS3の要素の組み合わせのすべてに対する要素間距離の和 Sum1、S2の要素とS3の要素の組み合わせのすべてに対する要素間距離の和 Sum2、S1の要素とS2の要素の組み合わせのすべてに対する要素間距離の和 Sum3 を算出する。ただし、ここでは追加配分された要素に関する要素間距離の追加変更分を計算して Sum1，Sum2，Sum3 を更新すればよい。次に、ステップ 603 において、数式１１に示すように、Sum1，Sum2，Sum3 の線形和を新たな集合間距離として算出する。次に、ステップ 604 において、集合間距離の前回までの算出値と新たな算出値とを比較して、それらの値が後述の収束判定条件を満たさなければ、再度ステップ 600 に戻ってステップ 600 から 603 までを繰り返す。もし、それらの値が収束判定条件を満たせば、繰返し処理を終了する。また、集合AとBの和集合の要素のすべてが標本として抽出され、残りが一つもない場合も繰返し処理を終了する。この他に繰返し回数の制限なども加えて、繰返し処理の終了条件としてもよい。【００３３】
収束判定条件としては、集合間距離の最初の算出値を D0、繰返し処理後の最新の n 回目の算出値を Dn と記述すると、例えば、非負定数 x、y、z を含む次に示す不等式が成立するとき収束したと判定する方法がある。
【数１６】
2012029152.tif 000017
より具体的な数値として、x = y = 0とすると、集合間距離の推定値の変化量の絶対値がzよりも小さくなった場合を意味し、y = z = 0 とすると、集合間距離の推定値の変化量の割合がxよりも小さくなった場合を意味する。あるいは、集合間距離のk回分の推定値の分散が一定値x未満となる次に示す不等式を用いても良い。
【数１７】
2012029152.tif 000018
なお、平均値 En は重み付き移動平均値として次式で計算できる。
【数１８】
2012029152.tif 000019
ただし、重み r0, r1, …, rk-1 は総和が1、すなわち r0 + r1 + … + rk-1 = 1 となる1以下の非負定数とする。
【実施例８】
【００３４】
実施例７の方法において、標本となる要素を一つずつ追加する場合のフローチャートを図７に示す。まず、ステップ 600 において標本として e∈(A∪B)＼S を抽出し、それをSに追加する。次に、ステップ 601 において、e∈Aの条件判定と e∈Bの条件判定を行い、もし e∈Aでなければ e をS3に追加し、e∈Aの場合は e∈Bでなければ e をS1に追加し、e∈Aかつ e∈Bの場合は e をS2に追加する。ステップ 602 では、e∈S1の場合は、e とS3の要素との要素間距離の和を Sum1 に、e とS2の要素との要素間距離の和を Sum3 に追加し、e∈S2の場合は、e とS3の要素との要素間距離の和を Sum2 に、e とS1の要素との要素間距離の和を Sum3 に追加し、e∈S3の場合は、e とS1の要素との要素間距離の和を Sum1 に、e とS2の要素との要素間距離の和を Sum2 に追加する。ステップ 603 では、重み係数と w1、w2、w3 を更新し、集合間距離として D(A, B) = w1×Sum1＋w2×Sum2＋w3×Sum3 を計算する。
【実施例９】
【００３５】
文書データにおいて、各文書が単語を要素とする集合として表され、要素間距離すなわち単語間距離が単語の非類似性を表している場合、実施例１〜８で算出される集合間距離すなわち文書間距離は文書間の非類似性の評価尺度として利用できる。これを文書検索に利用するためには、入力された検索語を要素とする集合 X と文書データベースに記憶されている複数の文書との文書間距離を算出し、文書間距離が小さい順番に各文書を整列させる。整列させた文書を順番に A1, A2, …, AN と表すと、D(X, A1) ≦ D(X, A2) ≦ … ≦ D(X, AN) となるので、この順番に表示すれば、文書 X と類似性の高い文書から順番に表示することができる。
【実施例１０】
【００３６】
複数の文書 A1, A2, …, AN に対して、相互間の文書間距離を算出し、D(Ai, Aj) を第i行第j列の行列成分とする大きさN×Nの文書間距離行列を作成する。ただし、距離行列が対称行列の場合は上三角成分または下三角成分のみを計算して対称成分に同じ値を設定すればよい。この文書間距離行列を基にして、類似した内容を持つ文書を要素とする集合（クラスタ）を作成することができる。そのため、まず、各文書に対して、その文書だけを要素として含む単集合の文書集合 B1 = {A1}, B2 = {A2}, …, BN = {AN} を用意し、文書間距離行列を複製した文書集合間距離行列 D(Bi, Bj) = D(Ai, Aj) を作成する。この文書集合間距離行列に対して、従来技術における階層型クラスタリングの手法を利用し、文書集合間距離行列の非対角成分において距離が最小となる文書集合同士を統合して文書集合を変更するステップ１と、その変更に応じて文書集合間距離行列を再計算するステップ２とを交互に繰返し実行することにより、階層的に分類された文書集合を作成できる。【００３７】
各ステップを詳細に説明すると、ステップ１では、文書集合間距離行列の非対角成分の中で最小値となる行列成分を抽出し、それが第k行第m列（ただし、k≠m）であれば、Bk = {Ak}と Bm = {Am} の２つの文書集合を統合して一つの文書集合BN+1 = Bk∪Bm = {Ak, Am} とする。その後、統合前のBkとBmを削除する。次のステップ２では、実施例１〜８のいずれかの方法またはその組み合わせを利用して、新しく追加された文書集合BN+1とその他の文書集合Biの文書集合間距離D(Bi, BN+1) を計算し、文書集合間距離行列に第(N+1)行と第(N+1)列を追加する。その後、添え字を付け直して整理すると、文書集合間距離行列は(N-1)次正方行列になる。もし、ステップ１で文書集合間距離が最小値となる組み合わせが複数個ある場合、例えば、D(Bk, Bm) = D(Bq, Bt) であれば、BN+1 = Bk∪Bm と BN+2 = Bq∪Bt を追加したのち、Bk, Bm, Bq, Bt を削除し、ステップ２で文書集合 BN+1 と BN+2 を含む文書集合間距離行列を更新する。
【実施例１１】
【００３８】
画像データがその特徴を言語的に表現したデータ集合に対応付けられている場合、例えば、画像の説明文や、画像の特徴を表すキーワード：｛風景写真、抽象絵画、書画、・・・｝、｛山、川、空、雲、・・・｝、｛街、自然、人物、・・・｝、｛直線、四角、円、・・・｝、｛アルファベット、漢字、数字、・・・｝、｛上、下、右、左、手前、奥・・・｝、｛黒、白、赤、青、黄、・・・｝などの組み合わせデータが対応付けられている場合は実施例９，１０を応用して類似画像検索や分類ができる。また、画像の要素となるセグメント画像に対して、各種の特徴点、例えば、顔画像の場合は目、鼻、口、耳などの相対位置座標や輪郭線の形状、色情報などの数値データで表される特徴ベクトルが対応付けられている場合は、特徴ベクトル間の距離をセグメント画像の要素間距離として、画像の類似画像検索や分類ができる。映像データは画像データの時系列的集合であり、集合を要素とするさらに上位の集合とみなして、実施例９、１０と同様に類似映像検索や分類ができる。音声データに対しても同様に応用可能である。
【産業上の利用可能性】
【００３９】
本発明は、複数の要素からなるデータ集合について、異なるデータ集合同士の非類似性を距離として計算する装置と計算方法を改善したものである。算出される値が距離の自然な性質を満たすとともに、データ集合間の距離の平均的な特徴を適切に表しており、従来技術に比べて異常値の影響を受けにくいという特徴がある。また、平均値の算出において統計的なサンプリングで効率よく計算できる場合が多いという利点もある。データ集合の種類としては、文書データ、画像データ、音声データ、映像データ、化学物質データ、生物の遺伝子データ、経済指標データ、位置情報データ、気象データ、観測データなど、様々なデータ集合に対して利用可能である。それらのデータ集合において、類似データの検索、類似データの分類、パターン認識、クラスタ解析、データマイニング、機械学習などに利用できる。
【符号の説明】
【００４０】
101  201  演算装置
102  202  記憶装置
【図１】
2012029152.tif 000020
【図２】
2012029152.tif 000021
【図３】
2012029152.tif 000022
【図４】
2012029152.tif 000023
【図５】
2012029152.tif 000024
【図６】
2012029152.tif 000025
【図７】
2012029152.tif 000026