(57)【要約】【目的】多数事例からなるデータベースを対象として、任意の事例相互間の類似性尺度を高速に推定するプログラム、記録媒体及び装置を提供する。【構成】本発明に係る類似性尺度推定プログラムは、多数事例からなる事例集合の設定と、その１事例を選択して選択事例集合の設定と、前記選択事例と他の全事例間の類似性尺度からなる準正定類似性尺度行列の計算と、前記行列の修正コレスキー分解の計算と、前記分解行列により他の全事例の固有値計算と、前記固有値の最大値と固有値閾値の大小判定と、最大値が大きい場合に他の事例の前記選択事例集合への追加とからなり、各ステップの反復により最大値が閾値より小さくなった場合に反復を完了し、前記選択事例集合以外の任意の２事例に関する事例ベクトルの内積により前記２事例の類似性尺度を推定する各ステップ群から構成される。このプログラムを保存した記録媒体及び推定装置も提供される。【選択図】図２０
2008198080.tif 000002
【特許請求の範囲】
【請求項１】
多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値の最大値と固有値閾値の大小を判定するステップと、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記各ステップを反復しながら前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから構成されることを特徴とする類似性尺度推定プログラム。
【請求項２】
前記反復完了ステップ後に、前記固有値を大小にソートするステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップを設け、前記弱類似性組合せを除いて前記２事例の類似性尺度を推定する請求項１に記載の類似性尺度推定プログラム。
【請求項３】
多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値を大小にソートするステップと、ソートされた最大固有値と固有値閾値の大小を判定するステップと、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップと、前記各ステップを反復しながら前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記弱類似性組合せを除いて前記選択事例集合以外から選択されるの任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから構成されることを特徴とする類似性尺度推定プログラム。
【請求項４】
多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値の最大値と固有値閾値の大小を判定するステップと、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記各ステップを反復しながら前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから類似性尺度推定プログラムを構成し、この類似性尺度推定プログラムを記録媒体に保存したことを特徴とする類似性尺度推定プログラム記録媒体。
【請求項５】
前記反復完了ステップ後に、前記固有値を大小にソートするステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップを設けた前記類似性尺度推定プログラムを、前記記録媒体に保存した請求項４に記載の類似性尺度推定プログラム記録媒体。
【請求項６】
多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値を大小にソートするステップと、ソートされた最大固有値と固有値閾値の大小を判定するステップと、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップと、前記各ステップを反復しながら前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記弱類似性組合せを除いて前記選択事例集合以外から選択されるの任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから類似性尺度推定プログラムを構成し、この類似性尺度推定プログラムを記録媒体に保存したことを特徴とする類似性尺度推定プログラム記録媒体。
【請求項７】
多数の事例からなる事例集合を設定する手段と、前記事例集合から１事例を選択して選択事例集合を設定する手段と、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算する手段と、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算する手段と、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算する手段と、前記固有値の最大値と固有値閾値の大小を判定する手段と、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加する手段と、前記反復により前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了する手段と、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定する手段から構成されることを特徴とする類似性尺度推定装置。
【請求項８】
前記反復完了手段に、前記固有値を大小にソートする手段と、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除する手段を設けた請求項７に記載の類似性尺度推定装置。
【請求項９】
多数の事例からなる事例集合を設定する手段と、前記事例集合から１事例を選択して選択事例集合を設定する手段と、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算する手段と、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算する手段と、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算する手段と、前記固有値を大小にソートする手段と、ソートされた最大固有値と固有値閾値の大小を判定する手段と、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加する手段と、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除する手段と、前記反復により前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了する手段と、前記弱類似性組合せを除いて前記選択事例集合以外から選択されるの任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定する手段から構成されることを特徴とする類似性尺度推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量の事例（以下、変数をも含む一般概念として使用する）からなるデータベースに対し、事例相互間の類似性を示す類似性尺度を高速に推定する類似性尺度推定プログラム、類似性尺度推定プログラム記録媒体及び類似性尺度推定装置に関する。
【背景技術】
【０００２】
本発明は、データマイニングと呼ばれる分野を対象とする。データマイニングとは、巨大なデータベースから人間にとって有用な知識を高速に獲得する技術である。計算機の計算能力が飛躍的に発達し、その能力を最大限に活用できるデータマイニングは、今日の情報化社会において非常に注目され、実際に多くの分野で活用されている。
【０００３】
例えば，社会統計学の分野では、その目的に応じて、様々なデータを蓄積している。このようなデータから、「事例Ａ、Ｂ、Ｃが原因で事例Ｄ が発生する。」といった知識が得られれば、社会の情勢を系統的に把握できる。また、最新の発電所では、システムの異常を検知するため、膨大な数のセンサを発電所内に設置している。例えば、これらのセンサ群から、「故障Ｘが発生すれば、センサＹ、Ｗ、Ｚの値に対してのみ多大な影響を及ぼす。」といった傾向が得られれば、膨大なセンサ群の中から、センサＹ、Ｗ、Ｚのみに着目するだけで故障Ｘの発生を予測できる。
【０００４】
従って、このようなデータマイニングの分野においては、事例間の類似性尺度を導出して、事例間の因果関係を簡易に推論することが重要になる。社会、自然、産業などには多数の種類の事例が存在する。例えば、身長、体重、都市、予算、建築物、自動車、電車、バス、河川、天気、雨量、風速、産地、温度、圧力、容積、センサ、生産量、原料、生産コスト、消費量、流通量など、無数の事例が存在する。また、これらの事例間の類似性尺度には、例えば、相関係数、ユークリッド距離、共分散、同時生起確率などがあり、事例相互間の特質に応じて、相互関係を特徴的に表現する類似性尺度が選択される。
【０００５】
事例間の類似性尺度を導出することによって、類似性尺度の大きな事例同士は高い因果関係を有すると判断でき、他の雑音から離れて両事例間の関係性に注力することが可能になる。また、類似性尺度の小さな事例同士は因果関係が小さく、判断の対象から排除して、現象理解を簡明化することができる。しかし、考察の対象とする全事例の個数をＮとすると、事例相互間の組合せはオーダーがＮ２になり、これをＯ（Ｎ２）と書く。Ｎが１０３程度であれば、Ｎ２＝１０６であるから、コンピュータで高速計算することは可能である。しかし、Ｎ＝１０６になると、Ｎ２＝１０１２になり、コンピュータ計算でも、数日から数ヶ月を要することになり、とても高速に計算できる分野ではなくなる。
【０００６】
例えば、特許文献１（特開２００５−１８１１６８）に開示されているように、多数のアンテナから電波が到来し、これらの受信電波をＡ／Ｄ変換して、相関行列が類似性尺度行列として計算される。また、特許文献２（特開２００６−３１３５２３）では、患者（年齢、性別、生年月日を含む）、薬名、用量、用法、処方時刻、処方日時、処方医師、診療科、医療機関、薬剤師、受付時刻、受付日時、処方日数、調剤日数、病名、過去に発生した事故・過誤などを事例として、例えば相関値を類似性尺度として行列演算が行われている。
【０００７】
【特許文献１】特開２００５−１８１１６８公報
【特許文献１】特開２００６−３１３５２３公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１では、特定設備に存在する多数のアンテナの夫々が事例であり、アンテナの総本数が事例総数Ｎとなる。特定設備に限定されたアンテナの本数Ｎには当然にして限界があり、Ｎ２個の類似性尺度の計算でも、総数Ｎが小さいが故に、コンピュータで行えば、短時間に終了することは明らかである。しかし、全地球上のアンテナ総数Ｎとなれば、ほぼ無数に近いから、Ｎ２個の相関係数からなる相関行列を完全に計算するには、通常のパソコンでは途方もない時間を要することは明らかである。
【０００９】
特許文献２の場合でも、１病院内の事例に限定すれば、事例総数Ｎは小さいから、Ｎ２個の相関値を求めることはパソコンでも短時間に実行できる。しかし、日本全域に拡大すると、患者数が無数に増大し、病気や薬剤量なども急激に増えるから、計算量が爆発的に増大し、パソコンでは不可能になる。また、スーパーコンピュータを使用しても、時間が掛かるだけでなく、その設備費用の増大により、予算的に実現不能の事態に陥ることは明らかである。
【００１０】
また、特殊な分野では、ＮｌｏｇＮに比例する計算時間で、コンピュータ処理するアルゴリズムが開発されている。例えば、ユークリッド距離のように、三角不等式を満たす距離について、データ内にある１つの事例から許容距離εの範囲にある全事例を検索するには、ＭＴｒｅｅに代表されるように近接事例を階層的にグループ化して、グループ内計算とグループ間計算に分解する方法が開発されている。その他、ｂｋ−ｔｒｅｅに代表される様に、複数の参照点から各事例までの距離を用いて階層的に枝狩りする方法も開発されている。更には、事例が座標を有する場合には、ｓｐａｇｈｅｔｔｉｓに代表されるように、事例を各座標軸に射影してソートしてから範囲を絞り込む方法が開発されている。しかし、これらの方法はあくまで三角不等式を満たす場合に限られた方法である。相関係数など、三角不等式を満たさないより一般的な類似性尺度に関する計算方法は、いまだに確立されていない。
【００１１】
従って、本発明は、大量の事例からなるデータベースを対象として、任意の事例相互間の類似性尺度を高速に推定し、しかも推定精度を同時的に導出できる類似性尺度推定プログラム、類似性尺度推定プログラム記録媒体及び類似性尺度推定装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は上記課題を解決するためになされたものであり、本発明の第１の形態は、多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値の最大値と固有値閾値の大小を判定するステップと、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記各ステップを反復しながら前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから構成される類似性尺度推定プログラムである。
【００１３】
本発明の第２の形態は、前記第１の形態において、前記反復完了ステップ後に、前記固有値を大小にソートするステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップを設け、前記弱類似性組合せを除いて前記２事例の類似性尺度を推定する類似性尺度推定プログラムである。
【００１４】
本発明の第３の形態は、多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値を大小にソートするステップと、ソートされた最大固有値と固有値閾値の大小を判定するステップと、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップと、前記各ステップを反復しながら前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記弱類似性組合せを除いて前記選択事例集合以外から選択されるの任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから構成される類似性尺度推定プログラムである。
【００１５】
本発明の第４の形態は、多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値の最大値と固有値閾値の大小を判定するステップと、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記各ステップを反復しながら前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから類似性尺度推定プログラムを構成し、この類似性尺度推定プログラムを記録媒体に保存した類似性尺度推定プログラム記録媒体である。
【００１６】
本発明の第５の形態は、前記反復完了ステップ後に、前記固有値を大小にソートするステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップを設けた前記類似性尺度推定プログラムを、前記記録媒体に保存した類似性尺度推定プログラム記録媒体である。
【００１７】
本発明の第６の形態は、多数の事例からなる事例集合を設定するステップと、前記事例集合から１事例を選択して選択事例集合を設定するステップと、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算するステップと、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算するステップと、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算するステップと、前記固有値を大小にソートするステップと、ソートされた最大固有値と固有値閾値の大小を判定するステップと、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加するステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップと、前記各ステップを反復しながら前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了するステップと、前記弱類似性組合せを除いて前記選択事例集合以外から選択されるの任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定するステップから類似性尺度推定プログラムを構成し、この類似性尺度推定プログラムを記録媒体に保存した類似性尺度推定プログラム記録媒体である。
【００１８】
本発明の第７の形態は、多数の事例からなる事例集合を設定する手段と、前記事例集合から１事例を選択して選択事例集合を設定する手段と、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算する手段と、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算する手段と、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算する手段と、前記固有値の最大値と固有値閾値の大小を判定する手段と、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加する手段と、前記反復により前記固有値の最大値が前記固有値閾値より小さくなった場合に前記反復を完了する手段と、前記選択事例集合以外の任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定する手段から構成される類似性尺度推定装置である。
【００１９】
本発明の第８の形態は、前記反復完了手段に、前記固有値を大小にソートする手段と、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除する手段を設けた類似性尺度推定装置である。
【００２０】
本発明の第９の形態は、多数の事例からなる事例集合を設定する手段と、前記事例集合から１事例を選択して選択事例集合を設定する手段と、前記選択事例と他の全事例間の類似性尺度からなる準正定性を満足する類似性尺度行列を計算する手段と、前記選択事例の類似性尺度に対し修正コレスキー分解行列を計算する手段と、前記修正コレスキー分解行列に基づいて前記他の全事例の固有値を計算する手段と、前記固有値を大小にソートする手段と、ソートされた最大固有値と固有値閾値の大小を判定する手段と、前記最大固有値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加する手段と、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除する手段と、前記反復により前記最大固有値が前記固有値閾値より小さくなった場合に前記反復を完了する手段と、前記弱類似性組合せを除いて前記選択事例集合以外から選択される任意の２事例に関し前記類似性尺度行列から得られる事例ベクトルの内積により前記２事例の類似性尺度を推定する手段から構成される類似性尺度推定装置である。
【発明の効果】
【００２１】
本発明の第１の形態に係る類似性尺度推定プログラムによれば、選択された１事例と他の全事例間の類似性尺度を準正定性条件下で計算し、この類似性尺度行列に対し修正コレスキー分解を施して前記他の全事例の固有値を計算し、これらの固有値の最大値と事前に与えられる固有値閾値のとの大小を判定し、前記固有値の最大値が前記固有値閾値を越える場合に前記１事例以外の他の事例を前記選択事例集合に追加して、上記全ステップを反復計算するから、追加数が増大するに従って、固有値が急速に小さくなり、計算時間を短縮できる効果を有する。前記固有値の内、大きな固有値を示す事例を選択事例集合に追加すると、固有値閾値との関係で計算時間は急速に低下し、計算時間の短縮効果が顕著になる。特に、前記固有値の最大値を示す事例を選択事例集合に追加した場合には、収斂速度は最大に達し、計算時間の短縮効果も最大になる。前記固有値閾値は事前に設定され、小さな固有値閾値を与えるほど計算時間はやや増大するが、事例集合の種類にも依存して固有値閾値を適宜変更することが可能である。
収斂した修正コレスキー分解行列と固有値を基礎にして、前記選択事例集合以外の任意の２事例を選定すると、この２事例について前記修正コレスキー分解により、この２事例に対する事例ベクトルが計算でき、前記２事例間の類似性尺度が前記事例ベクトルの内積として計算できる。しかも、前記類似性尺度の信頼幅が前記２事例の固有値の積の平方根として導出できるから、前記２事例間の類似性尺度の存在許容区間が[内積−平方根，内積＋平方根]として与えられ、平方根が小さい程、推定値である内積の推定精度を高める結果となる。つまり、前記固有値閾値を小さく設定すれば、前記平方根も急速に小さくなり、また固有値の単調減少性から選択事例数が増大すると固有値も急速に小さくなり、前記平方根も急速に小さくなって推定精度が格段に向上する。従って、本発明により、選択事例集合に含まれない任意の２事例の類似性尺度を、高速度且つ高精度の下で推定することが可能になる。しかも、この方法は、事例の種類を問わないから、一般事例に対する類似性尺度を導出する包括的方法であり、計算時間は全事例数Ｎに対してＮ〜ＮｌｏｇＮと極めて短時間であることが特徴である。従来の計算時間Ｎ２と比較すれば、パソコンで十分に短時間計算できるアルゴリズムであることが明らかである。また、背景技術で説明したＭＴｒｅｅ、ｂｋ−ｔｒｅｅ、Ｓｐａｇｈｅｔｔｉｓ等の方法では計算時間がＮｌｏｇＮであるが、類似性尺度がユークリッド距離に限定された特殊性を有している。他方、本発明方法は、一般の類似性尺度をＮ〜ＮｌｏｇＮの計算時間で推定する普遍的方法を与えており、広範囲且つ多種類に及ぶ事例に対し、普遍的に適用できる一般性を有している点で優れている。
【００２２】
本発明の第２の形態に係る類似性尺度推定プログラムによれば、前記第１形態の前記反復完了ステップ後に、前記固有値を大小にソートするステップと、前記ソートされた固有値の２個から計算される最大類似性尺度が類似性尺度閾値より小さい場合には前記２個の固有値に対応する事例間の組合せを弱類似性組合せとして排除するステップを設けているから、前記弱類似性組合せを除いて前記２事例の類似性尺度を推定することができ、類似性の小さな組合せに対する推定を排除することによって、推定速度を格段に向上することが可能になる。
前述したように、２事例間の類似性尺度の信頼区間は、[内積−平方根，内積＋平方根]として与えられる。内積の性質により、２事例ベクトルの内積は２事例ベクトルの大きさの積より小さいから、しかも事例ベクトルの大きさは（１−固有値）の平方根で与えられることが本発明者等によって証明されている。従って、事例ｉ，ｊ間の類似性尺度ｘｉｊは、固有値をλｉ、λｊで表記すると、ｘｉｊ≦（１−λｉ）１／２（１−λｊ）１／２＋（λｉλｊ）１／２となり、右辺を類似性尺度上限値ｘｉｊｍａｘと定義する。この類似性尺度上限値が事前に設定される類似性尺度閾値λｔｈより小さいならば、類似性尺度ｘｉｊも当然に小さいから、ｉ，ｊ間には殆んど類似性が無く、これらの組合せを弱類似性組合せとして、類似性尺度の推定処理から排除できる。従って、排除された組合せ以外の有効な事例間の類似性尺度を高速に推定することを可能にする。
特に、前記固有値閾値を比較的大きめに設定すると、修正コレスキー分解、ソート処理と類似性尺度閾値処理により、多数の弱類似性組合せの排除を実現でき、収斂するまでのループ回数が減少して、弱類似性の組合せに対する推定処理を高速度且つ効率的に排除することが可能になる。これらの固有値を大〜小にソートするステップには、一般のソート法を用いることができるが、バケットソート法やクイックソート法が有効であり、特に固有値を有効数字化したバケットソート法が、データ数Ｎに比例するＯ（Ｎ）で極めて高速に処理できる点で優れている。固有値が０〜１の小数で導出される場合に、例えば小数４桁目以下を切り捨てて小数３桁の有効数字にすると、１．０００〜０．０００の１００１個のバケットに事例を分類することになり、バケット数Ｍ（＝１００１）の処理に限定されるため、ソート及び排除処理が短縮できる効果を有する。
【００２３】
本発明の第３の形態に係る類似性尺度推定プログラムによれば、修正コレスキー分解ステップと固有値計算ステップに続いてソートステップを導入し、ソートステップにより導出される最大固有値を判定に使用して、ソートステップと固有値判定ステップを一体化でき、演算速度を速める効果がある。その後、選択事例の追加ステップの前又は後に第２形態で説明した類似性尺度閾値判定を行えば、弱類似性組合せの排除を行うことができる。しかも、このループが収斂するまで排除ステップを反復するから、多数の弱類似性組合せを排除でき、類似性尺度の推定ステップを有効な組合せに対してのみ実施することができ、推定効率を向上させることが可能になる。本形態は、弱類似性組合せの排除と有効な類似性尺度の推定を、効率的にリンクさせたアルゴリズムを提供するもので、実用性において最も顕著な効果を有する。また、追加ステップで、固有値の大きな事例を追加事例とし、特にソートされた最大固有値の事例を選択事例集合に追加すれば、最高速の推定プログラムを提供することができる。
ソートステップには、一般のソート法を用いることができるが、バケットソート法やクイックソート法が有効であり、特に固有値を有効数字化したバケットソート法が最短時間で処理できる点で優れている。
【００２４】
本発明の第４の形態に係る類似性尺度推定プログラム記録媒体によれば、第１形態で提供される類似性尺度推定プログラムを保存した記録媒体が提供される。従って、第４形態の記録媒体は、第１形態で説明した全てのプログラム上の効果を有する。記録媒体としては、フロッピーディスク、磁気ディスク、光ディスク、ＣＤ、ＭＯ、ＤＶＤ、ハードディスク等、コンピュータで読み取り可能な記録媒体が選ばれる。これらの記録媒体をコンピュータにインストールするだけで、コンピュータを動作させることができ、多数の個人、家庭、業務において類似性尺度推定プログラムを実行させることが可能になる。
【００２５】
本発明の第５の形態に係る類似性尺度推定プログラム記録媒体によれば、第２形態で提供される類似性尺度推定プログラムを保存した記録媒体が提供される。従って、第５形態の記録媒体は、第２形態で説明した全てのプログラム上の効果を有する。記録媒体としては、フロッピーディスク、磁気ディスク、光ディスク、ＣＤ、ＭＯ、ＤＶＤ、ハードディスク等、コンピュータで読み取り可能な記録媒体が選ばれる。これらの記録媒体をコンピュータにインストールするだけで、コンピュータを動作させることができ、多数の個人、家庭、業務において類似性尺度推定プログラムを実行させることが可能になる。
【００２６】
本発明の第６の形態に係る類似性尺度推定プログラム記録媒体によれば、第３形態で提供される類似性尺度推定プログラムを保存した記録媒体が提供される。従って、第６形態の記録媒体は、第３形態で説明した全てのプログラム上の効果を有する。記録媒体としては、フロッピーディスク、磁気ディスク、光ディスク、ＣＤ、ＭＯ、ＤＶＤ、ハードディスク等、コンピュータで読み取り可能な記録媒体が選ばれる。これらの記録媒体をコンピュータにインストールするだけで、コンピュータを動作させることができ、多数の個人、家庭、業務において類似性尺度推定プログラムを実行させることが可能になる。
【００２７】
本発明の第７の形態に係る類似性尺度推定装置には、第１形態の類似性尺度推定プログラムをインストールしたコンピュータだけでなく、このコンピュータを内蔵する電子装置など、第１形態の類似性尺度推定処理を実行する電子装置の全てが包含される。従って、第７形態の類似性尺度推定装置は、第１形態で説明した全ての効果を有する。
【００２８】
本発明の第８の形態に係る類似性尺度推定装置には、第２形態の類似性尺度推定プログラムをインストールしたコンピュータだけでなく、このコンピュータを内蔵する電子装置など、第２形態の類似性尺度推定処理を実行する電子装置の全てが包含される。従って、第８形態の類似性尺度推定装置は、第２形態で説明した全ての効果を有する。
【００２９】
本発明の第９の形態に係る類似性尺度推定装置には、第３形態の類似性尺度推定プログラムをインストールしたコンピュータだけでなく、このコンピュータを内蔵する電子装置など、第３形態の類似性尺度推定処理を実行する電子装置の全てが包含される。従って、第９形態の類似性尺度推定装置は、第３形態で説明した全ての効果を有する。
【発明を実施するための最良の形態】
【００３０】
以下に、本発明に係る類似性尺度推定プログラム、類似性尺度推定プログラム記録媒体及び類似性尺度推定装置の実施形態を添付図面を参照して詳細に説明する。
【００３１】
図１は本発明に係る類似性尺度の説明図である。事例Ｘｉは事例と称し、例えば、身長、体重、都市、予算、建築物、自動車、電車、バス、河川、天気、雨量、風速、産地、温度、圧力、容積、センサ、生産量、原料、生産コスト、消費量、流通量など、社会、自然、産業などに見られる無数の事例が包含される。（１）式のように、事例総数Ｎ個の事例Ｘｉからなる集合を事例集合と呼ぶ。類似性尺度Ｓｉｊは、事例Ｘｉと事例Ｘｊの間の類似性の程度を表す量で、例えば相関係数、ユークリッド距離、共分散、同時生起確率、その他の量である。（２）式は、平面上で類似性尺度を説明したものである。例えば、事例Ｘ１と事例Ｘ２の類似性尺度をＳ１２と表している。
【００３２】
図２は準正定性を有したＮ行、Ｎ列の類似性尺度行列Ｓの説明図である。（３）式により、Ｎ個の事例Ｘ１〜ＸＮに対し付与されるＮ×Ｎ個の類似性尺度Ｓｉｊを成分とする類似性尺度行列Ｓが定義される。この類似性尺度行列Ｓは、（６）式で定義される準正定性を満足する行列で、準正定行列と称される。ｘはゼロベクトルでない任意の列ベクトルで、Ｔは転置を意味する。類似性尺度行列Ｓが準正定行列であるが、（４）式の可換条件と（５）式の同値条件を満足する場合と、満足しない場合が存在する。（４）式や（５）式を満足しない場合には、（４）及び（５）を満足するように行と列の入れ替え変換や正則な線形変換を施すことができ、（４）式及び（５）式を満足する準正定行列に変換して本発明の推定補完を実行する。推定補完後に逆変換して元の形式に戻すことが可能である。従って、（４）式により、類似性尺度行列Ｓは対称行列になり、（５）式により、対角成分Ｓｉｉは１≦ｉ≦Ｎの範囲で同一値を有する。本発明では、（５）式のように、前記同一値は正であると定義する。
【００３３】
図３は準正定行列に変換される全ての行列が本発明の類似性尺度行列Ｓに用いられることを説明する変換説明図である。（７）式のように、非準正定行列Ｓに対し変換ｆを作用させたとき、（８）式によりその成分ｆ（Ｓｉｊ）が準正定条件・可換条件・同値条件を満足する場合には、（１０）式によりｆ（Ｓｉｊ）を新たにＳｉｊと定義して、準正定な類似性尺度行列Ｓを（９）式により定義する。このような行列変換を行った場合には、本発明の推定補完を実行した後に、逆変換して元の形式に戻す操作が必要になる。
【００３４】
例として、ユークリッド距離Ｕｉｊは（１１）式の可換条件を満足するが、（１２）式のように、同一値Ｕｉｉはゼロになり、（１３）式のようにＵｉｊを成分とする行列は準負定行列となる。しかし、（１４）式のｆ＝ｅｘｐ（−λ）の変換を作用させると、（１７）式のＳｉｊ＝ｅｘｐ（−λＵｉｊ）は正になり、（１５）式の変換行列により、（１６）式の準正定な類似性尺度行列Ｓが定義されることができる。従って、本発明には、準正定行列でなくても変換により準正定行列に変換される行列が全て包含される。
【００３５】
図４は類似性尺度行列Ｓを対角規格化する手順を説明した対角規格化説明図である。（１８）式により、一般に対角成分が１ではない類似性尺度行列Ｓを対角規格化して、対角規格化類似性尺度行列Ａを定義する。今後、この行列Ａも類似性尺度行列と称する。(１９)式により対角規格化された類似性尺度ａｉｊが定義される。（２０）式により、対角成分ａｉｉは１になり、（２１）式により、非対角成分ａｉｊについては可換条件が満足されている。
【００３６】
対角規格化の操作は（２２）式により説明される。類似性尺度行列Ｓの第ｉ行をＳｉｉの平方根で割り、第ｊ列をＳｊｊの平方根で割れば、対角規格化が実現する。この操作の結果、（１９）式で示されるように、対角規格化された類似性尺度ａｉｊが定義される。その結果、（２３）式に示されるような、対角規格化された類似性尺度行列Ａが導出される。対角成分ａｉｉは１と表示されている。
【００３７】
図５は、本発明の推定手順を対角規格化された類似性尺度行列Ａについて説明した推定手順説明図である。前述したように、Ｎ個の事例の全てに対し、類似性尺度ａｉｊを導出するには、計算時間がＮ２に比例してしまい、計算時間爆発問題に直面して操作不可能になってしまう。
【００３８】
そこで、通常はｎ＝１から始めるが、例えばｎ個の事例Ｘ１〜Ｘｎを選択する。ｎは１０個でも１００個でもよい。この選択事例Ｘｉ、Ｘｊに対し、類似性尺度ａｉｊを何とかして導出する。導出方法は実験、測定、計算など何でも良いが、とに角、何らかの手段でａｉｊをｎ×ｎ個だけ求めることができたとする。
【００３９】
次に、事例Ｘｎ＋１と事例Ｘｎ＋２の類似性尺度ａｎ＋１，ｎ＋２を導出したいとする。これをｎ×ｎ個の既知のａｉｊから如何に導出するかが問題である。本発明では、先に事例Ｘｎ＋１とＸｉ（ｎ＝１〜ｎ）の類似性尺度ａｉ，ｎ＋１と、事例Ｘｎ＋２とＸｉ（ｎ＝１〜ｎ）の類似性尺度ａｉ，ｎ＋２を何とかして求める。この導出操作も実験、測定、計算など何でも良い。これらの類似性尺度ａｉ，ｎ＋１とａｉ，ｎ＋２から、目的とする類似性尺度ａｎ＋１，ｎ＋２を導出することになる。この導出アルゴリズムが本発明者等の鋭意研究によって完成したのである。
【００４０】
図６は、図５で説明したａｎ＋１，ｎ＋２の導出手順をグラフ化した導出手順図である。実線で示されたｎ×ｎ個の類似性尺度ａｉｊは既知である。点線で示された類似性尺度ａｉ，ｎ＋１とａｉ，ｎ＋２を与えることによって、事例Ｘｎ＋１と事例Ｘｎ＋２の間の類似性尺度ａｎ＋１，ｎ＋２を導出する。つまり、図６は、図５と全く同じ内容を説明している、
【００４１】
図７は、全事例Ｎ個と選択事例ｎ個から導出されるｎ行Ｎ列の類似性尺度行列Ｂ（ｎ，Ｎ）の計算説明図である。全事例Ｎ個と、そこから選択されたｎ個の事例の間で類似性尺度ａｉｊ（ｉ＝１〜ｎ、ｊ＝１〜Ｎ）が計算され、その行列は、（２４）式で与えられるように、ｎ行Ｎ列の類似性尺度行列Ｂ（ｎ，Ｎ）である。このＢ（ｎ，Ｎ）の中で、正方行列である類似性尺度行列Ａ（ｎ，ｎ）＝｛ａｉｊ｝（１≦ｉ，ｊ≦ｎ）が次述される修正コレスキー分解の対象となる。Ａ（ｎ，ｎ）は対角成分ａｉｉが１の対称行列である。
【００４２】
図８は、修正コレスキー分解法による分解形の説明図である。（２５）式で示すように、Ａ（ｎ，ｎ）がＬＤＬＴの形に分解されたとき、Ａ（ｎ，ｎ）は特異値分解又は固有値分解されたと云う。行列Ｌは対角成分がゼロの下三角行列であり、行列ＡＴは行列Ａの転置行列である上三角行列である。行列Ｄは対角成分ｄｉが特異値（又は固有値）となる対角行列である。後述する固有値λと混同するので、ここでは特異値と称しておく。結局、前述した類似性尺度行列Ａ（ｎ，ｎ）を修正コレスキー分解して（２５）式の形に分解する。換言すれば、特異値と上三角行列Ｌが求まれば、分解が完了したことになる。
【００４３】
図９は、Ａ（ｎ，ｎ）の修正コレスキー分解法の具体的手順図である。簡略のために、前記Ａ（ｎ，ｎ）をＡと書いている。(２６)式に示すように、行列ＡをＡ（１）とし、これに修正コレスキー分解を１回施すとＡ（２）になり、（ｎ−１）回施すとＡ（ｎ）になる。(２７)式により、ａｉｊ（１）はａｉｊに等しく、対角規格化によりａｉｉ（１）＝１であることは自明である。ａｉｊ（ｋ＋１）とａｉｊ（ｋ）の間の変換式は（２８）式で与えられる。（ｋ＋１）はｋ回の修正コレスキー分解を行ったことを意味している。(２８)式の変換の添え字ｉ、ｊの範囲は、ｋ＋１≦ｉ≦ｎ、ｋ≦ｊ≦Ｎである。即ち、Ａ（ｎ，ｎ）に含まれないＢ（ｎ，Ｎ）の部分にも（２８）式が適用される。
【００４４】
（２９）式で示すように、（ｋ−１）回の修正コレスキー分解を受けると、Ａ（ｎ，ｎ）はＡ（ｋ）になり、Ｂ（ｎ，Ｎ）はＢ（ｋ）へと変化する。この変化過程を詳細に述べる。Ｂ（ｋ）の第１行はＢ（ｎ，Ｎ）の第１行と全く同じで、変換を受けていない。１回目の分解により、Ｂ（ｎ，Ｎ）の第２行目以上が変換される。Ａ（ｎ，ｎ）の第２行目成分であるａ２１、ａ２２〜ａ２ｎは、０、ａ２２（２）〜ａ２ｎ（２）へと変換され、更に延長上にあるａ２，ｎ＋１〜ａ２Ｎもａ２，ｎ＋１（２）〜ａ２Ｎ（２）へと変換される。勿論、この段階で第３行〜第ｎ行まで変換を受けている。次に、２回目の分解により第３行目以上が変換を受けるが、第２行目は全く変換を受けない。この変換を反復しながら（ｋ−１）回目の分解で、第ｋ行目以上が変換される。(２９)式は（ｋ−１）回目の分解を受けた後の行列を示す。この段階で、行列Ａ（ｋ）のｋ行ｋ列の行列が修正コレスキー分解を受け、対角成分が特異値になり、上三角成分が上三角行列の成分になることが分かる。
【００４５】
図１０は、行列Ａ（ｎ，ｎ）及び行列Ｂ（ｎ，Ｎ）の具体形の変化説明図である。（３０）式で示されるように、Ａ（１）の全成分はＡ（ｎ，ｎ）の全成分と、Ｂ（１）の全成分はＢ（ｎ，Ｎ）の全成分と全く同一である。（３１）式で示すように、Ａ（２）の第１行目はＡ（ｎ，ｎ）の第１行目と、Ｂ（２）の第１行目はＢ（ｎ，Ｎ）の第１行目と全く同一であるが、第２行目以上は全て変化している。これを繰り返すと、（３２）式に示すように、（ｎ−１）回の修正コレスキー変換により、Ａ（ｎ）は修正コレスキー分解が完了し、対角成分行列が特異値行列Ｄを示し、上三角成分行列が上三角行列ＬＴに対応する。同時に、（ｎ＋１）列〜Ｎ列までの成分も変換を受け、Ｂ（ｎ，Ｎ）がＢ（ｎ）に変化している。
【００４６】
図１１は、行列Ａ（ｎ）によりＡの修正コレスキー分解が完了したことを示す分解完了説明図である。（３３）式は（２５）式に対応するように描かれている。図（１０）の（３２）式に示される行列Ａ（ｎ）から、対角行列Ｄと上三角行列ＬＴと下三角行列Ｌが求まり、（３３）式が得られる。
【００４７】
図１２は、事例ベクトルｖと固有値λの定義図である。（３４）式に示されるように、事例ベクトルｖは列ベクトルで、Ｔは転置行列を意味する。（３５）式は、事例ベクトルｖによって定義される固有値λの式で、事例ベクトルｖの二乗値が正であるから、λは１以下の値を示す。添字ｉはｎ＋１〜Ｎの範囲である。Ｂ（ｎ）を示す（３７）式において、ｎ＋１≦ｉ≦Ｎにある第ｉ列の各成分をｎ次修正コレスキー分解行列Ａ（ｎ）の特異値ａ１１（１）〜ａｎｎ（ｎ）の平方根で割った値が事例ベクトルｖの各成分に相当する。対応関係は（３７）式に示されている。
【００４８】
図１３は、事例第Ｉ列・第II列を第（ｎ＋１）列・第（ｎ＋２）列に移動する２列移動図である。（３７）式において、事例ｎ＋１〜Ｎの中から、類似性尺度を求めたい２列Ｉ、IIを選択する。（３８）式に示すように、この第Ｉ列と第II列を第（ｎ＋１）列と第（ｎ＋２）列に夫々移動し、対応する固有値λＩ、λIIも夫々移動する。そして、Ｉをｎ＋１、IIをｎ＋２と書き換える。（３９）式は、書き換え後の行列Ｂ（ｎ）を示している。
【００４９】
図１４は、事例Ｉ、II間の類似性尺度ｘを導出する修正コレスキー分解図である。（２０）式より、対角成分ａｎ＋１，ｎ＋１とａｎ＋２，ｎ＋２は１である。（２１）式より、類似性尺度ａｎ＋１，ｎ＋２とａｎ＋２，ｎ＋１は可換であるから、共にｘと書かれる。（４０）式が出発行列を示し、（４１）式は２段階分解後の行列を示している。
【００５０】
図１５は、ａｎ＋１，ｎ＋１（ｎ＋１）とａｎ＋１，ｎ＋２（ｎ＋１）とａｎ＋２，ｎ＋２（ｎ＋２）の計算図である。（ｎ＋２）次修正コレスキー分解行列Ａ（ｎ＋２）の四角枠で囲まれた３成分の解析解が本発明者等によって初めて導出された。（４２）式はａｎ＋１，ｎ＋１（ｎ＋１）を与え、（４４）式はａｎ＋１，ｎ＋２（ｎ＋１）を与え、（４５）式はａｎ＋２，ｎ＋２（ｎ＋２）を与える。
【００５１】
図１６は、類似性尺度ｘの範囲を不等式から決定する類似性尺度決定図である。（４６）式は準正定性により特異値（固有値）が０以上であるから、ａｎ＋２，ｎ＋２（ｎ＋２）が０以上であることを示す。（４５）式を変換して（４７）式の左辺が得られ、これが０以上である。（４７）式はｘの２次不等式であり、ｘについて解くと、（４８）式が得られる。変換により（４９）式が得られる。（４９）式を、事例ベクトルｖと固有値λで書き換えると、（５１）式が導出される。（５０）式で示されるよう、ｘ＝ａｎ＋１，ｎ＋２であるから、事例（ｎ＋１）と事例（ｎ＋２）の類似性尺度である。換言すれば、ｘは事例Ｉと事例IIの類似性尺度である。
【００５２】
（５１）式は、本発明者等によって初めて証明された式で、重要な結果を与える。＜ｖｉ（ｎ），ｖｊ（ｎ）＞は（３４）式で定義されるｎ個の成分からなる事例ベクトルｖｉ（ｎ），ｖｊ（ｎ）の内積であり、λｉ（ｎ）λｊ（ｎ）は固有値λの積であることを示している。同時に、上添字（ｎ）はｎ次修正コレスキー分解行列Ａ（ｎ）から得られることを示す。前記内積は類似性尺度ｘｉｊの推定値であり、固有値λの積の平方根は類似性尺度ｘｉｊの範囲、即ち推定精度を表す。前記範囲が推定値よりもかなり小さければ推定精度が高いことを意味する。ｎ次分解により導出される（３８）式のＢ（ｎ）により、ｎ＋１≦ｉ，ｊ≦Ｎの範囲にある任意のｉ列、ｊ列のｎ個の成分から事例ベクトルｖｉ（ｎ）、ｖｊ（ｎ）を（３４）式により定義すれば、類似性尺度ｘｉｊの推定値は＜ｖｉ（ｎ），ｖｊ（ｎ）＞として計算でき、範囲は（３５）式で定義される固有値λｉ、λｊで計算できることになる。（４０）式〜（４９）式は、（５１）式の不等式を証明する手順を示すだけに過ぎない。
【００５３】
図１７は、固有値λの単調減少性を証明する証明図である。（５２）式はｎ次分解の固有値、（５３）式は（ｎ＋１）次分解の固有値の解析式である。（５３）式により、λｉ（ｎ＋１）はλｉ（ｎ）より正値だけ小さいことを示している。前記正値は（５４）式で与えられる。（５６）式で示されるように、その分母は準正定性により正である。また、（５５）式で示されるように、その分子は平方値であるから正である。従って、（５４）式の値は正値になる。即ち、（５３）式は、λｉ（ｎ＋１）≦λｉ（ｎ）を意味している。分解次数が増加するに従い、固有値λは次第に小さくなり、固有値λは分解次数ｎに対して単調減少であることが証明された。従って、（５７）式で示されるように、分解次数ｎの増加に従って、λ（ｎ）は単調に減少する。
【００５４】
図１８は、選択事例数ｎの増加によりＩ・II間類似性尺度ｘの精度が向上することを示す精度向上図である。（５１）式で既に説明したように、（５８）式は、類似性尺度ｘｉｊの範囲を示す存在許容区間式である。（５９）式は、分解次数ｎの増加により固有値λｉ（ｎ）が減少するから、範囲｛λｉ（ｎ）λｊ（ｎ）｝１／２が減少することを示している。従って、（６０）式で示すように、分解次数ｎが増加すると、類似性尺度ｘｉｊは急速に＜ｖｉ（ｎ），ｖｊ（ｎ）＞に収斂する性質を有する。このようにして、本発明者等によって、目的とする事例間の類似性尺度を高精度に導出するアルゴリズムが発見されたのである。
【００５５】
図１９は、固有値閾値λｔｈによる収斂判定と類似性尺度ｘの推定方式を示す簡略フロー図である。固有値λがどこまで小さくなれば収斂したと判断するかが重要であり、そのために固有値の閾値λｔｈを設定する。この固有値閾値λｔｈは、事例集合（Ｘ１、Ｘ２・・・ＸＮ）の組合せに依存し、場合により自在に設定される。具体的には０．０１、０．１、０．２等の値が選択される。
【００５６】
出発事例（選択事例）はｎ＝１として１個から始め、（３４）式及び（３５）式により事例ベクトルｖ及び固有値λを計算する。その結果、事例Ｉ・II間の類似性尺度を（５８）式により推定する。固有値λが前記固有値閾値λｔｈより大きければｎ＝ｎ＋１として他の事例を選択事例に追加し、ｎ＝２として同様に反復計算する。これを計算する中で、固有値λが前記固有値閾値λｔｈより小さくなった段階で、収斂したと判断して、その段階の類似性尺度ｘを推定値として出力する。同時に範囲も出力し、推定値ｘの推定精度が導出される。
【００５７】
図２０は、固有値閾値λｔｈによる収斂判定と類似性尺度ｘの推定方式を示す詳細フロー図である。ステップｔ１では、多数の事例からなる事例集合（Ｘ１・・ＸＮ）が設定される。ステップｔ２では、前記事例集合から１事例が選択され、ｎ＝１の出発事例とする。ステップｔ３では、選択事例と他の全事例間の類似性尺度が計算され、類似性尺度行列Ａが導出される。この類似性尺度は、実験、試験、測定、計算などの手段で導出される。
【００５８】
ステップｔ５では、前記類似性尺度行列Ａに対し修正コレスキー分解が施され、修正コレスキー分解行列が導出される。ステップｔ６では、選択事例以外のＮ−ｎ個の全事例に関し、事例ベクトルｖと固有値λが計算される。ステップｔ７では、固有値λＮ−ｎ・・λＮの最大値と固有値閾値λｔｈの比較が行われ、固有値閾値より大きければ、ステップｔ８により最大固有値の事例が選択事例として始めの１事例に追加され、同じ計算が反復される。この反復計算を繰り返すと、選択事例数ｎが次第に増加し、固有値の単調減少性により、ある段階で固有値λの最大値が固有値閾値λｔｈより小さくなる。
【００５９】
この反復計算を繰り返すと、選択事例数ｎが次第に増加し、固有値の単調減少性により、ある段階で固有値λの最大値λｍａｘが固有値閾値λｔｈより小さくなる。ステップｔ７により、λｍａｘ＜λｔｈになったときステップｔ９に飛び、ループ内で計算されている事例ベクトルｖが出力される。この事例ベクトルｖにより、推定値＜ｖｉ，ｖｊ＞及び範囲（λｉλｊ）１／２が導出される。最後に、ステップｔ１０により推定結果が出力される。
【００６０】
図２０に示される詳細フロー図に従って、類似性尺度推定プログラムが所定のプログラム言語により書き下され、磁気記録媒体や光記録媒体などの記録媒体に保存される。プログラム言語は各種の言語が利用でき、機械語やアセンブリなどの低水準言語や高水準言語が利用できる。高水準言語としては、ＣＯＢＯＬ等の事務処理用言語、ＦＯＲＴＲＡＮなどの技術計算用言語、ＢＡＳＩＣなどの汎用言語、ＣやＣ＋＋等のシステム記述用言語、ＬＩＳＰやＰｒｏｌｏｇ等の人工知能開発用言語、ＬＯＧＯ等の教育用言語、その他現在使用できる言語が利用できることは云うまでもない。
【００６１】
図２１は本発明を実行するために組み立てられた類似性尺度推定装置のブロック図である。この類似性尺度推定装置は類似性尺度推定プログラムをインストールしたコンピュータなどの汎用機器でもよいし、類似性尺度を推定する専用電子機器でもよい。類似性尺度推定装置１は、事例集合設定部１ａ、事例選択部２、類似性尺度計算部３、コレスキー分解行列計算部４、事例固有値計算部５、最大固有値・閾値比較部６、事例ベクトル内積計算部７、推定結果計算部８及び推定結果出力部９から構成されている。各部の作用は、図２０の詳細フローで説明した通りであるから、その説明を省略する。
【００６２】
図２２は類似性尺度行列の推定領域を説明する推定領域説明図である。事例集合（Ｘ１・・ＸＮ）の中で、（ｎ，ｎ）の正方行列要素は全て計算される。同時に、（ｎ，Ｎ−ｎ）行列の行列要素も全て計算される。（Ｎ−ｎ，ｎ）行列は（ｎ，Ｎ−ｎ）行列の対称行列であり、（Ｎ−ｎ，ｎ）行列が求まれば自動的に求まる。残った（Ｎ−ｎ，Ｎ−ｎ）行列の行列要素を、本発明の類似性尺度推定アルゴリズムにより推定補完することが本発明の目的である。
【００６３】
図２３は、類似性尺度推定プログラムを実行するコンピュータのブロック図である。入力装置１１により類似性尺度推定プログラムが入力され、バス１０を介してメインメモリ装置１３の中にプログラム１６としてインストールされる。このプログラム１６に従って、ＣＰＵ１８に演算制御されながら推定計算が続行され、バス１０を介してデータメモリ装置１２に推定計算途中及び推定結果のデータが記録されてゆく。これらの推定データはバス１０を介して出力装置１４により外部に出力される。出力形式は、紙、ファイル、電子データその他がある。
【００６４】
図２４は、類似性尺度行列の中で弱類似性しか示さない組合せを排除して残組合せを推定する推定領域説明図である。図２２と同一部分については同一内容であるからその説明は省略し、それ以外の部分について説明する。計算された領域データから、推定補完領域の類似性尺度を推定するわけであるが、この推定補完領域の全てを推定補完する必要が無い場合が多い。一般のデータ解析において、一定以上似ていない事例同士の関係は興味の対象とはされない。従って、全ての事例同士の類似性尺度を求める推定をせずに、一定以上に類似性尺度が大きくはなり得ない事例同士の組合せについては推定計算を排除することが、有効領域の推定速度を増大する要因となる。
【００６５】
一定以上に類似性尺度が大きくはなり得ない事例同士の組合せを、本発明では弱類似性組合せと呼ぶ。図２４において、（Ｎ−ｎ，Ｎ−ｎ）行列で示される推定補完領域から、弱類似性組合せを何らかの方法で見つけ出し、弱類似性組合せを排除した推定補完領域に対して本発明の推定作業を実行すれば、全体に対する推定時間の短縮効果を生む。弱類似性組合せが多くなるほど、短縮効果は大きくなる。以下では、弱類似性組合せの発見手法について詳細に説明する。
【００６６】
図２５は、事例ｉ，ｊ間の類似性尺度ｘｉｊの上限値を説明する上限値説明図である。（５８）式は既に説明した類似性尺度ｘｉｊの範囲不等式である。この中で、事例ベクトルｖｉ，ｖｊの内積は、（６１）式で示されるように、ベクトルの大きさと交角θｉｊのｃｏｓで表現される。ｃｏｓθｉｊ≦１であるから、＜ｖｉ，ｖｊ＞≦│ｖｉ│・│ｖｊ│は明らかである。（３５）式から（６２）式が成立する。（６１）式と（６２）式を（５８）式に代入すると、（６３）式が導出される。右辺の｛（１−λｉ）(１−λｊ)｝１／２＋（λｉλｊ）１／２をｘｉｊｍａｘと定義し、このｘｉｊｍａｘを類似性尺度上限値と呼ぶ。類似性尺度ｘｉｊは理論的に類似性尺度上限値ｘｉｊｍａｘを超えることはない。この関係性が（６４）式で表現されている。
【００６７】
図２６は、固有値λと類似性尺度上限値ｘｍａｘとの関係図である。（６５）式は類似性尺度上限値ｘｍａｘの定義式であり、ｘｍａｘの大小関係の性質について検討する。（６６）式に示すように、λｉ＝λｊ＝１又は０のときにｘｍａｘは１になり、（６８）式に示すように、λｉ＝１、λｊ＝０のときにｘｍａｘは０になる。即ち、（６７）式のようにλｉとλｊが近い値ではｘｍａｘは大きくなり、（６９）式のようにλｉとλｊが離れた値ではｘｍａｘは小さくなる性質がある。
【００６８】
図２７は、類似性尺度計算の高速化のため弱類似性の組合せを排除する論理手法説明図である。類似性尺度が一定以下の事例組合せを弱類似性組合せと呼ぶ。図２６で説明したように、弱類似性組合せは、事例ｉ，ｊの固有値λｉ、λｊの差が大きい組合せである。固有値差が大きな組合せは類似性尺度上限値ｘｉｊｍａｘが小さく、実際の類似性尺度はその類似性尺度上限値を越えないから、この事例組合せ（Ｘｉ，Ｘｊ）を弱類似性組合せとして排除すればよいことになる。
【００６９】
図２８は、全事例を固有値の大小順にバケットソートするバケットソート説明図である。事例Ｘ１〜ＸＮに対して固有値λ１〜λＮが与えられたとする。固有値λは０〜１の実数であり、バケット処理をするために、固有値λを有効数字化する。有効桁数は目的と精度に応じて自在に設定される。例えば、λ＝０．８９２６・・とすると、小数３桁以下切捨て・四捨五入、小数４桁以下切捨て・四捨五入などが行われる。具体的には、有効数字２桁のバケットソート法が示されている。バケットは０〜１までの１０１個が用意される。この場合には、バケット数Ｍ＝１０１となる。多数の事例Ｘ１〜ＸＮの固有値λ１〜λＮが小数２桁で示されている。前記１０１個のバケットに対応する事例を順次配列する。バケットは固有値の大小順に配列されており、固有値差の大きな組合せは弱類似性組合せであり、配列された事例間は弱類似性組合せとして一気に排除されることになる。この排除の計算時間は最大でもＭで処理でき、事例毎に処理する場合の計算時間Ｎ２と比較すれば遥かに短時間に終了する。
【００７０】
図２９は、全事例を固有値の大小順にクイックソートするクイックソート説明図である。事例Ｘ１〜ＸＮに対して固有値λ１〜λＮが与えられたとする。固有値λは０〜１の実数であり、この実数を大小順に公知のクイックソート法により並べ替える。その結果、事例Ｘが固有値の大小順に並べ替えられる。この並べ替えられた順列に対し、固有値の差が大きい組合せを選択して、弱類似性組合せとして排除すればよい。
【００７１】
図３０は、弱類似性組合せ排除計算のために導入される類似性尺度閾値ｘｔｈの説明図である。（６４）式は既に説明した類似性尺度上限値ｘｉｊｍａｘの定義式である。（７０）により、類似性尺度ｘに対し類似性尺度閾値ｘｔｈを設定する。この類似性尺度閾値ｘｔｈは事例集合（Ｘ１・・ＸＮ）の種類や性質に依存し、推定対象に応じて自在に設定できる。（７１）式に示されるように、類似性尺度上限値ｘｉｊｍａｘが類似性尺度閾値ｘｔｈより小さな組合せを弱類似性組合せとし、この組合せ（ｉ，ｊ）を計算対象から排除すればよい。これによって、弱類似性組合せが計算対象から除外されるので、有効な組合せに対してのみ類似性尺度を推定することができ、計算時間の短縮効果が大きくなる。
【００７２】
図３１は、バケットソートに対する弱事例組合せ排除プログラムのフロー図である。バケットｍに対しバケット固有値λｍが一対一に対応している。そのバケットｍには有効数字化された固有値λｍを有する事例が包含されている。ステップｗ１により、最初のバケット１がｍとされ、最後のバケットＭがｐとして初期設定される。ステップｗ２により、λｍとλｐから類似性尺度上限値ｘｍｐが計算される。ステップｗ３では、類似性尺度上限値ｘｍｐと類似性尺度閾値ｘｔｈの値が比較され、ｘｍｐが小さい場合にはステップｗ４によりｐ＝ｐ−１としてステップｗ２に帰還してこの計算を反復する。そしてｘｍｐがｘｔｈより大きくなったときにステップｗ５に移動する。その結果、（１、ｐ＋１）〜（１、Ｍ）に対応する組合せを弱類似性組合せとして一気に排除する。次に、ステップｗ６でｍ＝ｍ＋１として一つ繰り上げ、ステップｗ２に移動する。このループを繰り返すことによって、類似性尺度上限値が類似性尺度閾値以下の組合せが全て排除されることになる。
【００７３】
図３１に示すフロー図は、クイックソートに対しても適用できる。クイックソートでは、全事例が固有値の大小順に並べ替えられている。このとき、バケット数Ｍを全事例数Ｎと読み替え、パラメータｍは全事例に対するパラメータと考える。そして、排除されるバケット（ｍ，ｐ＋１）〜（ｍ，Ｍ）を、排除される組合せ（Ｘｍ，Ｘｐ＋１）〜（Ｘｍ，ＸＭ）と読み替えればよいだけである。
【００７４】
図３２は、ソート法を図２０に組み込んだ収斂判定と類似性尺度ｘの推定方式を示す詳細フロー図である。図２０と同一のステップの説明は図２０の説明と同様であるから割愛し、異なるステップだけを以下に説明する。ステップｕ１〜ｕ６はステップｔ１〜ｔ６と同一である。ステップｕ７では、固有値（λｎ＋１〜λＮ）を大小順にソートする。このソート法ではバケットソート法やクイックソート法、その他のソート法などが利用できるが、その中でもバケットソート法が特に高速である。ステップｕ８では、ソートされた最大固有値λｍａｘと固有値閾値λｔｈとが比較され、最大固有値が大きい場合にはステップｕ９で弱類似性組合せ排除計算が行われる。その後その最大固有値の事例が選択され、選択事例集合に追加されてステップｕ３に移動する。このループを反復計算しながら、最大固有値が固有値閾値より小さくなったときに、ステップｕ１１、ｕ１２に移動する。ステップｕ１１，ｕ１２はステップｔ９、ｔ１０と同一である。
【００７５】
図３３は、本発明を実行するために組み立てられた図３２に対応する類似性尺度推定装置のブロック図である。この類似性尺度推定装置は類似性尺度推定プログラムをインストールしたコンピュータなどの汎用機器でもよいし、類似性尺度を推定する専用電子機器でもよい。類似性尺度推定装置２１は、事例集合設定部２１ａ、事例選択部２２、類似性尺度計算部２３、コレスキー分解行列計算部２４、事例固有値計算部２５、固有値ソート部３０、最大固有値・閾値比較部２６、事例ベクトル内積計算部２７、推定結果計算部２８、推定結果出力部２９及び弱類似性排除部３１から構成されている。各部の作用は、図３３及び図２１の詳細フローで説明した通りであるから、その説明を省略する。
【００７６】
本発明は上記実施例及び実施形態に限定されるものではなく、本発明の技術的思想から逸脱しない技術的範囲内の全ての変形例、設計変更を包含するものであることは言うまでもない。
【産業上の利用可能性】
【００７７】
本発明に係る類似性尺度推定プログラム及び類似性尺度推定装置は、巨大なデータベースから人間にとって有用な知識を高速に獲得するデータマイニング技術
分野で利用できる。多種類の事例相互間の類似性を判定し、事例間の因果関係を明確にして、最短時間及び最小コストで問題解決を図る多数の分野に利用できる。事例として、身長、体重、都市、予算、建築物、自動車、電車、バス、河川、天気、雨量、風速、産地、温度、圧力、容積、センサ、生産量、原料、生産コスト、消費量、流通量など無数の量が選択されるので、社会科学分野、自然科学分野、工学分野、産業技術分野、人文科学分野、医療科学分野、医薬科学分野などの広範囲の分野に適用できる。また、類似性尺度として、相関係数のみならずユークリッド距離、共分散、同時生起確率など、準正定行列を構成する尺度が対象となる。また、前記類似性尺度推定プログラムを保存した記録媒体も本発明に包含され、情報処理分野にも多大に貢献することができる。
【図面の簡単な説明】
【００７８】
【図１】本発明に係る類似性尺度の説明図である。
【図２】準正定性を有したＮ行、Ｎ列の類似性尺度行列Ｓの説明図である。
【図３】準正定行列に変換される全ての行列が本発明の類似性尺度行列Ｓに用いられることを説明する変換説明図である。
【図４】類似性尺度行列Ｓを対角規格化する手順を説明した対角規格化説明図である。
【図５】本発明の推定手順を類似性尺度行列Ｓについて説明した推定手順説明図である。
【図６】図５で説明したＳｎ＋１，ｎ＋２の導出手順をグラフ化した導出手順図である。
【図７】全事例Ｎ個と選択事例ｎ個から導出されるｎ行Ｎ列の類似性尺度行列Ｂ（ｎ，Ｎ）の計算説明図である。
【図８】修正コレスキー分解法による分解形の説明図である。
【図９】Ａ（ｎ，ｎ）の修正コレスキー分解法の具体的手順図である。
【図１０】行列Ａ（ｎ，ｎ）及び行列Ｂ（ｎ，Ｎ）の具体形の変化説明図である。
【図１１】行列Ａ（ｎ）によりＡの修正コレスキー分解が完了したことを示す分解完了説明図である。
【図１２】事例ベクトルｖと固有値λの定義図である。
【図１３】事例第Ｉ列・第II列を第（ｎ＋１）列・第（ｎ＋２）列に移動する２列移動図である。
【図１４】事例Ｉ、II間の類似性尺度ｘを導出する修正コレスキー分解図である。
【図１５】ａｎ＋１，ｎ＋１（ｎ＋１）とａｎ＋１，ｎ＋２（ｎ＋１）とａｎ＋２，ｎ＋２（ｎ＋２）の計算図である。
【図１６】類似性尺度ｘの範囲を不等式から決定する類似性尺度決定図である。
【図１７】固有値λの単調減少性を証明する証明図である。
【図１８】選択事例数ｎの増加によりＩ・II間類似性尺度ｘの精度が向上することを示す精度向上図である。
【図１９】固有値閾値λｔｈによる収斂判定と類似性尺度ｘの推定方式を示す簡略フロー図である。
【図２０】固有値閾値λｔｈによる収斂判定と類似性尺度ｘの推定方式を示す詳細フロー図である。
【図２１】本発明を実行するために組み立てられた類似性尺度推定装置のブロック図である。
【図２２】類似性尺度行列の推定領域を説明する推定領域説明図である。
【図２３】類似性尺度推定プログラムを実行するコンピュータのブロック図である。
【図２４】類似性尺度行列の中で弱類似性しか示さない組合せを排除して残組合せを推定する推定領域説明図である。
【図２５】事例ｉ，ｊ間の類似性尺度ｘｉｊの上限値を説明する上限値説明図である。
【図２６】固有値λと類似性尺度上限値ｘｍａｘとの関係図である。
【図２７】類似性尺度計算の高速化のため弱類似性の組合せを排除する論理手法説明図である。
【図２８】全事例を固有値の大小順にバケットソートするバケットソート説明図である。
【図２９】全事例を固有値の大小順にクイックソートするクイックソート説明図である。
【図３０】弱類似性組合せ排除計算のために導入される類似性尺度閾値ｘｔｈの説明図である。
【図３１】バケットソートに対する弱事例組合せ排除プログラムのフロー図である。
【図３２】ソート法を図２０に組み込んだ収斂判定と類似性尺度ｘの推定方式を示す詳細フロー図である。
【図３３】本発明を実行するために組み立てられた図３３に対応する類似性尺度推定装置のブロック図である。
【符号の説明】
【００７９】
１        類似性尺度推定装置
１ａ      事例集合設定部
２        事例選択部
３        類似性尺度計算部
４        コレスキー分解行列計算部
５        事例固有値計算部
６        最大固有値・閾値比較部
７        事例ベクトル内積計算部
８        推定結果計算部
９        推定結果出力部
１０      バス
１１      入力装置      
１２      データメモリ装置
１３      メインメモリ装置
１４      出力装置
１６      プログラム
１８      ＣＰＵ
２１      類似性尺度推定装置
２１ａ    事例集合設定部
２２      事例選択部
２３      類似性尺度計算部
２４      コレスキー分解行列計算部
２５      事例固有値計算部
２６      最大固有値・閾値比較部
２７      事例ベクトル内積計算部
２８      推定結果計算部
２９      推定結果出力部
３０      固有値ソート部
３１      弱類似性排除部
【図１】
2008198080.tif 000003
【図２】
2008198080.tif 000004
【図３】
2008198080.tif 000005
【図４】
2008198080.tif 000006
【図５】
2008198080.tif 000007
【図６】
2008198080.tif 000008
【図７】
2008198080.tif 000009
【図８】
2008198080.tif 000010
【図９】
2008198080.tif 000011
【図１０】
2008198080.tif 000012
【図１１】
2008198080.tif 000013
【図１２】
2008198080.tif 000014
【図１３】
2008198080.tif 000015
【図１４】
2008198080.tif 000016
【図１５】
2008198080.tif 000017
【図１６】
2008198080.tif 000018
【図１７】
2008198080.tif 000019
【図１８】
2008198080.tif 000020
【図１９】
2008198080.tif 000021
【図２０】
2008198080.tif 000022
【図２１】
2008198080.tif 000023
【図２２】
2008198080.tif 000024
【図２３】
2008198080.tif 000025
【図２４】
2008198080.tif 000026
【図２５】
2008198080.tif 000027
【図２６】
2008198080.tif 000028
【図２７】
2008198080.tif 000029
【図２８】
2008198080.tif 000030
【図２９】
2008198080.tif 000031
【図３０】
2008198080.tif 000032
【図３１】
2008198080.tif 000033
【図３２】
2008198080.tif 000034
【図３３】
2008198080.tif 000035