(57)【要約】【課題】  データベース等に格納される複数の要素から互いの関連が強いメンバ要素をクラスタとして選択する。【解決手段】  複数の要素の何れかを選択して生成したクラスタについて、当該クラスタの選択の自己コンフィデンス値を算出する評価装置は、基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数を算出し、全てのメンバ要素の組み合わせについての当該割合の平均を自己コンフィデンス値として出力するコンフィデンス値算出部とを備える。【選択図】図１
2005301786.tif 000002
【特許請求の範囲】
【請求項１】
互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する評価装置であって、
予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部と
を備える評価装置。
【請求項２】
前記コンフィデンス値算出部は、前記基準要素との関係がより強い前記基準個数の要素の何れかを中継要素として、当該中継要素との関係がより強い前記基準個数の要素の各々について、当該要素に達するために選択可能な全ての前記中継要素の数を算出し、当該要素に達するために選択可能な全ての中継要素のうち２つの中継要素の組み合わせの総数を算出し、各要素について算出した当該組み合わせの総数の合計に基づく値を前記自己コンフィデンス値として出力する
請求項１記載の評価装置。
【請求項３】
互いに関連の強さが定められた複数の要素から何れかを選択してクラスタを生成するクラスタ生成装置であって、
予め定められた基準要素について、当該基準要素との関係がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記クラスタから選択可能な２つのメンバ要素の組の各々について、当該組の一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全ての組について算出した当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部と、
前記自己コンフィデンス値が予め定められた基準値より大きい場合に、評価対象の前記クラスタを、生成すべきクラスタと判断する要素クラスタ生成部と
を備えるクラスタ生成装置。
【請求項４】
前記クラスタ生成装置は、複数の文書を前記複数の要素として、文書に含まれるキーワードに基づいてクラスタを生成する装置であり、
前記評価対象クラスタ選択部は、予め定められた文書について、当該文書と比較して含んでいるキーワードの組がより類似する前記基準個数の文書の集合である隣接要素集合を、前記評価対象のクラスタとして選択し、
前記隣接要素集合選択部は、前記クラスタに含まれる各々の文書について、当該文書と比較して含んでいるキーワードの組がより類似する前記基準個数の文書の集合である隣接要素集合を選択し、
前記コンフィデンス値算出部は、前記クラスタから選択可能な２つの文書の組み合わせについて、当該組み合わせの一方の文書の隣接要素集合及び他方の文書の隣接要素集合に共通して含まれる文書の数の、前記基準個数に対する割合を算出し、全ての組み合わせについて算出した当該割合の合計に基づく値を前記自己コンフィデンス値として出力し、
前記要素クラスタ生成部は、前記自己コンフィデンス値が予め定められた基準値より大きい場合に、評価対象の前記クラスタを、生成すべきクラスタと判断する
請求項３記載のクラスタ生成装置。
【請求項５】
互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を算出する評価装置であって、
予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、
前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、
自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部と
を備える評価装置。
【請求項６】
前記コンフィデンス値算出部は、前記複数のメンバ要素の各々について、前記クラスタに含まれる要素のうち当該メンバ要素の隣接要素集合に含まれる要素の割合を算出し、各メンバ要素について算出した前記割合の合計に基づく値を前記自己コンフィデンス値として出力する
請求項５記載の評価装置。
【請求項７】
前記コンフィデンス値算出部は、前記クラスタから選択可能な２つのメンバ要素の組み合わせの各々について、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全ての組について算出した当該割合の合計に基づく値を前記自己コンフィデンス値として算出する
請求項５記載の評価装置。
【請求項８】
互いに関連の強さが定められた複数の要素から何れかを選択してクラスタを生成するクラスタ生成装置であって、
予め定められた基準要素との関係がより強い予め定められた基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、
前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、
自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部と、
前記基準個数を予め定められた範囲で変更した各クラスタについて、前記評価値を前記評価値算出部により算出させ、算出させた当該評価値を最大にするクラスタを選択して生成する要素クラスタ生成部と
を有するクラスタ生成装置。
【請求項９】
各々が複数の属性のうち少なくとも１つを有する複数の要素からクラスタを生成するクラスタ生成装置であって、
前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択部と、
前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出部と、
算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成部と、
前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成部と
を備えるクラスタ生成装置。
【請求項１０】
互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する評価装置として、コンピュータを機能させるプログラムであって、
前記コンピュータを、
予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部と
して機能させるプログラム。
【請求項１１】
互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を算出する評価装置として、コンピュータを機能させるプログラムであって、
前記コンピュータを、
予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、
前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、
前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、
自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部と
して機能させるプログラム。
【請求項１２】
各々が複数の属性のうち少なくとも１つを有する複数の要素からクラスタを生成するクラスタ生成装置として、コンピュータを機能させるプログラムであって、
前記コンピュータを、
前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択部と、
前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出部と、
算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成部と、
前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成部と
して機能させるプログラム。
【請求項１３】
請求項１０から１２の何れかに記載のプログラムを記録した記録媒体。
【請求項１４】
互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を、コンピュータにより算出する評価方法であって、
前記コンピュータにより、
予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択段階と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択段階と、
前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出段階と
を備える評価方法。
【請求項１５】
互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を、コンピュータにより算出する評価方法であって、
前記コンピュータにより、
予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択段階と、
前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択段階と、
前記隣接要素集合選択段階において選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出段階と、
前記隣接要素集合選択段階において、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出段階において算出される自己コンフィデンス値の理論値を算出する理論値算出段階と、
自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出段階と
を備える評価方法。
【請求項１６】
各々が複数の属性のうち少なくとも１つを有する複数の要素から、コンピュータによりクラスタを生成するクラスタ生成方法であって、
前記コンピュータにより、
前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択段階と、
前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出段階と、
算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成段階と、
前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成段階と
を備えるクラスタ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、評価装置、クラスタ生成装置、プログラム、記録媒体、評価方法、及びクラスタ生成方法に関する。特に、本発明は、互いの関連の強さが予め定まっている複数の要素からクラスタを生成する評価装置、クラスタ生成装置、プログラム、記録媒体、評価方法、及びクラスタ生成方法に関する。
【背景技術】
【０００２】
近年、コンピュータの発達・普及に伴い、様々なデータが電子化されるようになってきている。電子化されたデータは、様々な産業において利用される。例えば、商品の購買行動を電子化したデータからマーケティング・リサーチを行ったり、経済指標等を電子化したデータから株価変動を予測したりすることが提案されている。しかしながら、電子化したデータが膨大な場合には、有効なデータのみを適切に選択することは難しい。そこで、従来、データマイニング等の技術が注目されている。
【０００３】
データマイニングの基礎となる技術として、本願発明者は、データベースを構成する複数の要素から基準個数のメンバ要素を選択したクラスタについて、そのメンバ要素の選択の確信度を評価する方法を提案している（非特許文献２参照。）。この技術は、クラスタ内の所定の基準要素に対して、その基準要素と他の各々のメンバ要素との関連の強さの平均値を、確信度として評価する。
【０００４】
また、本願発明者は、上記確信度を用いてクラスタを決定する技術を提案している。この技術によると、まず、ある基準要素との関連がより強い基準個数の要素の集合をクラスタの候補として選択する。次に、基準個数を変化させて得られる複数のクラスタの候補の各々について、そのクラスタの候補と、そのクラスタの候補より多いメンバ要素を含む集合との、上記確信度の差分を算出する。そして、算出した差分が最大となるクラスタの候補を、生成すべきクラスタとして決定する。
【０００５】
なお、関連技術として、カイ２乗検定値をデータマイニングに応用する技術が提案されている（非特許文献１及び３参照。）。
非特許文献４及び非特許文献５については後述する。
【非特許文献１】S. Brin, R. Motwani and C. Silverstein, Beyond market baskets: generalizing association rules to correlations, Proc. ACM SIGMOD International Conference on Management of Data, Tucson, U.S.A, 1997, pp. 265-276.
【非特許文献２】Michael E. Houle, Navigating massive data sets via local clustering, Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, U.S.A, 2003, pp. 547-552.
【非特許文献３】G. V. Kass, An exploratory technique for investigating large quantities of categorical data, J. Applied Statistics 29:119-129, 1980.
【非特許文献４】E. S. Keeping, Introduction to Statistical Inference, Dover Publications, New York, USA, 1995.
【非特許文献５】Gerald Salton, The SMART Retrieval System - Experiments in Automatic Document Processing, Prentice-Hall, Englewood Cliffs, NJ, USA, 1971.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、クラスタの評価において、ある基準要素と他の各々のメンバ要素との関連が強い場合であっても、他の各々のメンバ要素が相互に強く関連しない場合には、クラスタ内の各メンバ要素が相互に強く関連するとは言えない。例えば、あるデータベースが、基準要素として文章「その研究所は、携帯電話の為のビデオ送信制御技術を開発している」を含む場合を例に説明する。
【０００７】
このデータベースが、他の要素として、「ビデオ送信制御技術」に関連し、かつ「携帯電話」と無関係な文章を有している場合には、この要素と基準要素とは共にキーワード「ビデオ送信制御技術」を含むので、類似しており関連が強いと考えられる。同様に、このデータベースが、更に他の要素として、「携帯電話」に関連し、かつ「ビデオ送信制御技術」と無関係な文章を有している場合には、この要素と基準要素とは共にキーワード「携帯電話」を含むので、類似しており関連が強いと考えられる。
【０００８】
しかしながら、「ビデオ送信制御技術」に関連しかつ「携帯電話」と無関係な文章と、「携帯電話」に関連しかつ「ビデオ送信制御技術」と無関係な文章とは、共通のキーワードを有しておらず、類似していない。上記非特許文献２に記載の技術によれば、このような無関係な複数の要素を同一のクラスタに含めてしまう場合があった。
【０００９】
また、クラスタの決定において、基準個数を順次変更した場合であっても、確信度が徐々に変化して急激な変化点は検出されない場合がある。このような場合には、ある確信度の差分が、他の確信度の差分と比較して僅かに大きいからといって、その確信度を有する要素の集合をクラスタとして決定するのは適切ではない。更に、基準個数を変化させる毎に、その基準個数より大きい所定の個数の要素の集合について確信度を算出する必要があり、計算量が大きくなってしまう。
【００１０】
また、従来のデータマイニングによると、２５個程度のメンバ要素をクラスタとして選択することはできるものの、１〜２個程度の互いに非常に強く関連するメンバ要素をクラスタとして選択することはできない。このような比較的小さなクラスタであっても、有用な情報を含む場合は多い。また、利用者は、データマイニングによらず利用者の経験・知識等に基づいて、２５個程度のメンバ要素をクラスタとして容易に選択できる場合が多い。一方、１〜２個程度の要素を含むクラスタを発見するのは、困難な場合が多い。従って、このような発見困難かつ有用クラスタを適切に選択することが課題である。
【００１１】
そこで本発明は、上記の課題を解決することのできる評価装置、クラスタ生成装置、プログラム、記録媒体、評価方法、及びクラスタ生成方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明の第１の形態においては、互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する評価装置であって、予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を自己コンフィデンス値として出力するコンフィデンス値算出部とを備える評価装置、評価装置を用いたクラスタ生成装置、評価方法、クラスタ生成方法、コンピュータを評価装置又はクラスタ生成装置として機能させるプログラム、及びプログラムを記録した記録媒体を提供する。
【００１３】
本発明の第２の形態においては、互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、複数の要素全体に対するクラスタの特殊性の評価値を算出する評価装置であって、予め定められた基準要素との関係がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、隣接要素集合選択部により選択された隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、隣接要素集合選択部が、隣接要素集合に代えて、複数の要素から無作為に基準個数の要素の集合を選択したと仮定した場合における、コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、自己コンフィデンス値の理論値に対する自己コンフィデンス値のカイ２乗検定値を、評価値として算出して出力する評価値算出部とを備える評価装置、評価装置を用いたクラスタ生成装置、評価方法、クラスタ生成方法、コンピュータを評価装置又はクラスタ生成装置として機能させるプログラム、及びプログラムを記録した記録媒体を提供する。
【００１４】
本発明の第３の形態においては、各々が複数の属性のうち少なくとも１つを有する複数の要素からクラスタを生成するクラスタ生成装置であって、複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択部と、複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出部と、算出した関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成部と、属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成部とを備えるクラスタ生成装置、クラスタ生成方法、コンピュータをクラスタ生成装置として機能させるプログラム、及びプログラムを記録した記録媒体を提供する。
【００１５】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１６】
本発明によれば、データベース等に格納される複数の要素から互いの関連が強いメンバ要素をクラスタとして選択することができる。
【発明を実施するための最良の形態】
【００１７】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【実施例１】
【００１８】
図１は、文書データベース１０及びクラスタ生成装置２０の機能ブロック図である（実施例１）。クラスタ生成装置２０は、文書データベース１０における互いに関連の強さが定められた複数の要素の何れかを選択したクラスタの候補について、そのクラスタの候補に含まれるメンバ要素の選択の確信度であるコンフィデンス値を算出することを目的とする。更に、クラスタ生成装置２０は、クラスタの各候補について算出したコンフィデンス値に基づいて、生成すべき適切なクラスタを決定することを目的とする。
【００１９】
文書データベース１０は、互いに関連の強さが定められた複数の要素として、複数の文書を格納する。複数の文書の各々は、予め定められた複数の属性の何れか、例えば、複数のキーワードの何れかを有する。一例として、文書１は、キーワード１を含み、キーワード２を含まない。より詳細には、本図の例において、各要素の属性の組は、属性の値を配列したベクトルとして表される。そして、属性の値は、キーワードを有するか否かを示す２値である。このような２値の属性のベクトルを有するデータのモデルを、ブーリアンモデルと呼ぶ。
【００２０】
これに代えて、各属性の値は、大きさを持った連続値であってもよい。例えば文書の例において、各属性は、その属性に対応するキーワードが、文書において用いられた回数・頻度・出現場所に基づく値を有してもよい。より詳細には、ある属性は、その属性のキーワードが、文書の章・節のタイトルで使われた場合に、その他の場所で使われた場合と比較して、より高い値を有してもよい。このような属性ベクトルの生成方法は、TF-IDF技術として従来公知であるので、より詳細な説明を省略する。
【００２１】
そして、複数の文書が互いに関連する関連度は、複数の文書が共通して含んでいるキーワードの組に基づいて予め定められている。例えば、ある２つ文書は、共通して含むキーワードの数がより多い場合に、当該キーワードの数がより少ない場合と比較してより強く関連する。より詳細には、ある２つの文書の関連度は、一方の文書における属性の値を配列したベクトルが示す座標と、他方の文書における属性の値を配列したベクトルが示す座標との間の距離に基づいて定められてもよい。但し、この場合の距離とは、三角不等式を満たさない場合も含む。
【００２２】
更に他の例として、ある２つの文書の関連度は、各々の文書の属性ベクトル間の角度に基づいて定められてもよい。この場合、当該角度がより小さい場合に関連度はより高く、角度がより大きい場合に関連度はより低い。角度に基づく関連度の生成方法は、非特許文献５に例示されているので、本実施例における説明を省略する。
【００２３】
他の例として、文書データベース１０は、互いの関連の強さが定められた複数の要素として、複数のマルチメディアデータを有していてもよい。マルチメディアデータとは、例えば、動画、静止画、音声、又は映像等である。この場合、属性は、例えば、所定の映像・音声を含むか否かを示してもよい。この場合も、ブーリアンモデルに限定されるものではなく、属性は、大きさを有する値を採ってもよい。そして、この例における関連度は、マルチメディアデータの類似性を示す値である。
【００２４】
クラスタ生成装置２０は、評価装置３０と、要素クラスタ生成部４０とを有する。評価装置３０は、評価対象クラスタ選択部３００と、隣接要素集合選択部３１０と、コンフィデンス値算出部３２０と、理論値算出部３３０と、評価値算出部３４０とを有する。評価対象クラスタ選択部３００は、予め定められた文書を基準要素として、その基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する。例えば、評価対象クラスタ選択部３００は、その文書と比較して含んでいるキーワードの組がより類似する基準個数の文書の集合を隣接要素集合として選択する。
【００２５】
隣接要素集合選択部３１０は、そのクラスタに含まれる各々のメンバ要素について、そのメンバ要素との関連がより強い基準個数の要素の集合である隣接要素集合を選択する。例えば、クラスタに含まれる各々の文書について、その文書と比較して含んでいるキーワードの組がより類似する基準個数の文書の集合を、その文書の隣接要素集合として選択する。
【００２６】
コンフィデンス値算出部３２０は、隣接要素集合選択部３１０により選択された隣接要素集合に基づいて、評価対象のクラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する。具体的には、まず、コンフィデンス値算出部３２０は、評価対象のクラスタから選択可能な２つのメンバ要素（例えば文書）の全ての組み合わせについて、各組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数を算出する。
【００２７】
次に、コンフィデンス値算出部３２０は、その要素の数の、基準個数に対する割合を算出する。そして、コンフィデンス値算出部３２０は、メンバ要素の全ての組み合わせについての当該割合の合計に基づく値、例えば、当該割合の平均値を、自己コンフィデンス値として算出し、評価値算出部３４０に出力する。続いて、理論値算出部３３０は、隣接要素集合選択部３１０が、隣接要素集合に代えて、文書データベース１０に格納された全ての要素から無作為に基準個数の要素の集合を選択したと仮定した場合における、コンフィデンス値算出部３２０により算出される自己コンフィデンス値の理論値を算出する。
【００２８】
評価値算出部３４０は、文書データベース１０における複数の要素全体に対する、評価対象のクラスタの特殊性の評価値を算出する。具体的には、評価値算出部３４０は、理論値算出部３３０により算出された自己コンフィデンス値の理論値に対する、コンフィデンス値算出部３２０により算出された自己コンフィデンス値のカイ２乗検定値を、評価値として算出し、要素クラスタ生成部４０に出力する。
【００２９】
要素クラスタ生成部４０は、基準個数を予め定められた範囲で変更して得られる複数の各クラスタの各々について、評価値算出部３４０により評価値を算出させ、算出させたその評価値を最大にするクラスタを選択する。そして、要素クラスタ生成部４０は、選択したクラスタをクラスタリング結果として利用者に出力する。これに代えて、要素クラスタ生成部４０は、基準個数を変更して得られる各クラスタについて、そのクラスタの評価値又は自己コンフィデンス値が予め定められた基準値より大きい場合に、評価対象のそのクラスタを、生成すべきクラスタと判断してもよい。
【００３０】
図２は、クラスタ生成装置２０がメンバ要素を選択してクラスタを生成する処理フローを示す（実施例１）。評価装置３０は、予め定められたa以上b以下の範囲で変化させた基準個数kの各々について、以下の処理を繰り返す（Ｓ２００）。まず、評価対象クラスタ選択部３００は、予め定められた基準要素との関係がより強いk個の要素の集合である隣接要素集合を、評価対象のクラスタにおけるメンバ要素として選択する（Ｓ２１０）。
【００３１】
ここで、ある要素の集合であるドメインDについて、Dのうち文書データベース１０に格納される要素の集合をSとし、Sのうち本実施例において評価の対象となる要素の集合をRとし、予め定められた基準要素をq∈Dとする。そして、評価対象のクラスタを、NN(R, q, k)とする。即ち、評価対象のクラスタは、Rのうちqと関連の強いk番目までの要素の集合である。
【００３２】
この場合、qに対して、NN(R, q, k)は一意に定まる。また、NN(R, q, k)は、以下の性質を満たす。
q∈Rならば、NN(R, q, 1)={q}
1＜k≦|R|を満たす全てのkについて、NN(R, q, k-1)⊂NN(R, q, k)
更に、あるqi、kiについて、NN(R, qi, ki)をCiと表記する。同様に、あるqj、kjについて、NN(R, qj, kj)をCjと表記する。
【００３３】
続いて、隣接要素集合選択部３１０は、評価対象のクラスタに含まれる各々のメンバ要素について、そのメンバ要素との関連がより強いk個の要素の集合である隣接要素集合を選択する（Ｓ２２０）。次に、コンフィデンス値算出部３２０は、自己コンフィデンス値を算出する（Ｓ２３０）。
【００３４】
自己コンフィデンス値は、クラスタ内の複数の要素が互いに関連する強さに基づく値であるから、単純に計算すると、クラスタ内の要素数の３乗に比例する計算量を要する。これに対して、自己コンフィデンス値を、クラスタ内の要素数の２乗の計算量で計算する計算方法を説明する。
【００３５】
図３は、Ｓ２３０における処理の詳細を説明する図である（実施例１）。まず、コンフィデンス値算出部３２０が算出するべき自己コンフィデンス値は、式（１）で表される。以降、このコンフィデンス値を、AASCONFと呼ぶ。
【数１】
2005301786.tif 000003
【００３６】
この式によると、クラスタから２つのメンバ要素を選択する全ての組み合せの総数は、クラスタ内の要素数の２乗である。そして、各組み合わせに共通に含まれている要素を数えるには、クラスタ内の要素数に比例する計算量を要すると考えられる。従って、計算量は、メンバ要素の数の３乗に比例する。このように計算量が大きい場合には、計算効率が悪いだけでなく、データサイズの大きいデータベースへの拡張性（スケーラビリティ）が悪い。
【００３７】
これに対して、本実施例においては、以下に説明する方法により自己コンフィデンス値を計算する。まず、ρ(u,t)を、ある要素ｕと関連の強い方から数えてｔ番目の要素とする。即ち、ρは以下の式（２）を満たす。
【数２】
2005301786.tif 000004
【００３８】
次に、δ(u,s,t)を、ある基準要素qと関連の強い方から数えてs番目の要素を中継要素として、その中継要素との関連の強い方から数えてt番目の要素が、ある要素uである場合は１、そうでない場合には０をとるパラメータとする。次に、S(u,s,t)を、以下の値１と値２との合計とする。まず、値１は、基準要素qとより関連の強いs個の要素の何れかを中継要素として、当該中継要素との関連が強いs個の要素の何れかが要素uである場合において、中継要素として選択可能な要素の数である。値２は、基準要素qと関連の強い方から数えてs+1番目の要素を中継要素として、当該中継要素との関連が強いt個の要素のうち何れかがuである場合に１をとり、当該t個の要素の何れもuでない場合に０を採る値である。具体的には、以下の式（３）により定義される。
【数３】
2005301786.tif 000005
【００３９】
本図は、ある要素uについての中継要素を示す。本図の横軸は、要素qと中継要素との関連を示す。そして、本図の縦軸は、中継要素と要素uとの関連を示す。この例によると、斜線部まで計算が行なわれた段階で、コンフィデンス値算出部３２０は、要素uの出現回数を５と算出する。
【００４０】
次に、T(u,s,t)を、ある要素uについて、その要素uに到達しうる全ての中継要素から、２つの中継要素を選択する組み合わせの総数とする。具体的には、T(u,s,t)=S(u,s,t)*[S(u,s,t)-1]/2と定義される。以上の定義により、自己コンフィデンス値は、以下の式（４）として表される。
【数４】
2005301786.tif 000006
ここで、u∈Rについて、S及びTは、以下の各々の性質を満たす。
・S(u, 1, 0) = 1 if u = q, and S(u, 1, 0) = 0 if u≠ q.
・For all s ＞ 1, 
S(u, s, 0) = S(u, s?1, s?1) + 1 if u∈NN(R, u, s), and
S(u, s, 0) = S(u, s?1, s-1) if not(u∈NN(R, u, s)).
・For all s ＞ 1 and 0 ＜ t ≦ s, S(u, s, t) = S(u, s, t-1) + ?(u, s+1, t).
・T(u, 1, 0) = 0 for all u.
・For all s ＞ 1, 
T(u, s, 0) = T(u, s?1, s-1) + S(u, s?1, s-1) if u ∈ NN(R, u, s), and
T(u, s, 0) = T(u, s?1, s-1) if not(u ∈ NN(R, u, s)).
・For all s ＞ 1 and 0 ＜ t ≦ s,
T(u, s, t) = T(u, s, t-1) + S(u, s, t-1) if ?(u, s+1, t) = 1, and
T(u, s, t) = T(u, s, t-1) if ?(u, s+1, t) = 0.
【００４１】
これにより、自己コンフィデンス値は、以下の式（５）に示すアルゴリズムにより算出される。ここで、このアルゴリズムによる処理の終了時に、S(u)は、S(u,s,t)を格納し、TTは、Σu∈RT(u,s,t)を格納する。
【数５】
2005301786.tif 000007
【００４２】
このアルゴリズムにより、コンフィデンス値算出部３２０は、ある基準要素qについて、その基準要素との関係がより強いk個の何れかを中継要素として、その中継要素との関係がより強いk個の要素の各々について、その要素に達するために選択可能な全ての中継要素の数を、S(u)として算出することができる。また、コンフィデンス値算出部３２０は、u∈Rを満たす各要素uに到達するために選択可能な全ての中継要素のうち、２つの中継要素の組み合わせの総数を、TTに算出することができる。そして、コンフィデンス値算出部３２０は、step3により、メンバ要素の各組み合わせについて、一方のメンバ要素及び他方のメンバ要素の隣接要素集合が互いに共通して有する要素数の、基準個数に対する割合を算出できる。
【００４３】
なお、コンフィデンス値算出部３２０は、step2-iiの終了時点で、基準個数がsである場合についての中継要素の総数をS(u)として算出できる。また、コンフィデンス値算出部３２０は、この時点で、TTをk2(k-1)/2で除することにより、基準個数がsである場合についての自己コンフィデンス値を算出することができる。従って、コンフィデンス値算出部３２０は、Ｓ２００からＳ２６０に至る繰り返し処理毎に、上記step2-i及びstep2-iiを一度ずつ処理することが望ましい。
【００４４】
以上の処理に代えて、コンフィデンス値算出部３２０は、評価対象のクラスタにおける複数のメンバ要素の各々について、そのクラスタに含まれる要素のうちそのメンバ要素にも含まれる要素の割合を算出し、各メンバ要素について算出したその割合の合計に基づく値を自己コンフィデンス値として算出してもよい。このコンフィデンス値をA1SCONFと呼ぶ。具体的には，以下の式（６）により定義される。
【数６】
2005301786.tif 000008
【００４５】
図２に戻る。続いて、理論値算出部３３０は、隣接要素集合選択部３１０が、隣接要素集合に代えて、文書データベース１０に格納された全ての要素から無作為に基準個数の要素の集合を選択したと仮定した場合における、コンフィデンス値算出部３２０により算出される自己コンフィデンス値の理論値を算出する。（Ｓ２４０）。そして、評価値算出部３４０は、自己コンフィデンス値の理論値に対する、自己コンフィデンス値のカイ２乗検定値を評価値として算出する（Ｓ２５０）。
【００４６】
この処理について詳細を説明する。まず、カイ２乗検定値は、以下の式（７）により定義される。
【数７】
2005301786.tif 000009
【００４７】
ここで、XSは、ｎ回の試行のうち成功した試行の回数を示し、E[XS]は、試行が成功する回数の期待値を示す。また、XFは、ｎ回の試行のうち失敗した試行の回数を示し、E[XF]は、試行が失敗する回数の期待値を示す。カイ２乗検定値の詳細については、非特許文献４に例示されているので、説明を省略する。
【００４８】
この定義に基づいて、コンフィデンス値算出部３２０により算出される自己コンフィデンス値がA1SCONFである場合についてまず説明する。評価値算出部３４０は、XSとして、クラスタの各メンバ要素（基準要素を除く）の隣接要素集合（当該メンバ要素を除く）と、クラスタのメンバ要素の集合とに共通して含まれる要素の総数を算出する。例えば、以下の式（８）により算出される。同様に、評価値算出部３４０は、XFとして、クラスタの各メンバ要素の隣接要素集合と、クラスタのメンバ要素の集合との少なくとも一方に含まれない要素の総数を算出する。例えば、式（９）により算出される。
【数８】
2005301786.tif 000010
【００４９】
【数９】
2005301786.tif 000011
そしてこの場合、理論値算出部３３０は、自己コンフィデンス値の理論値として、NN(R, v, k)がR-{v}から無作為に選択されたと仮定した場合におけるXsの期待値Ｅ[Ｘｓ]を算出する。具体的には、以下の式（１０）により算出される。
【数１０】
2005301786.tif 000012
【００５０】
以上により、評価値算出部３４０は、以下の式（１１）によりカイ２乗検定値を算出する。但し、式（１１）において式（１２）の定義を用いる。
【数１１】
2005301786.tif 000013
【数１２】
2005301786.tif 000014
なお、このカイ２乗検定値の、Ｒを無限大とした場合の極限値は、（Ｒ−１）に比例する値となる。従って、評価値算出部３４０は、このカイ２乗検定値を（Ｒ−１）で除した値を、評価値とすることが更に好ましい。これにより、Ｒの値が異なる複数の母集団からそれぞれ選択したクラスタについて、何れのクラスタがより適切であるか比較することもできる。
【００５１】
次に、コンフィデンス値算出部３２０により算出される自己コンフィデンス値がAASCONFである場合について説明する。評価値算出部３４０は、XSとして、クラスタから選択可能な２つのメンバ要素の全ての組み合わせについて、その組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の合計を算出する。但し、あるメンバ要素の隣接要素集合にそのメンバ要素自身が含まれる場合を除く。具体的には、以下の式（１３）により算出される。同様に、評価値算出部３４０は、XFとして、上記各組み合わせについて、一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合の少なくとも一方に含まれないメンバ要素の総数を算出する。例えば、式（１４）により算出される。
【数１３】
2005301786.tif 000015
【００５２】
【数１４】
2005301786.tif 000016
【００５３】
そしてこの場合、理論値算出部３３０は、自己コンフィデンス値の理論値として、NN(R, v, k)がR-{v}から無作為に選択されたと仮定した場合におけるXsの期待値Ｅ[Ｘｓ]を算出する。具体的には、以下の式（１５）により算出される。
【数１５】
2005301786.tif 000017
【００５４】
以上により、評価値算出部３４０は、以下の式（１６）によりカイ２乗検定値を算出する。
【数１６】
2005301786.tif 000018
なお、このカイ２乗検定値の、Ｒを無限大とした場合の極限値は、Ｒに比例する値となる。従って、評価値算出部３４０は、このカイ２乗検定値を、更にＲを除した数を、評価値とすることが更に好ましい。これにより、Ｒの値が異なる複数の母集団から選択したクラスタについて、何れのクラスタがより適切であるか比較することもできる。
【００５５】
評価装置３０は、以上の処理を基準個数kの各々について繰り返す（Ｓ２６０）。続いて、要素クラスタ生成部４０は、算出されたカイ２乗検定値を最大とする基準個数を求める（Ｓ２７０）。そして、要素クラスタ生成部４０は、カイ２乗検定値を最大とする基準個数のクラスタを、基準要素を中心として生成するべき最適なクラスタと判断し、クラスタリング結果として出力する。
【００５６】
以上、本図に示すように、クラスタ生成装置２０は、クラスタ選択の確信度である自己コンフィデンス値を、各メンバ要素が互いに関連する強さに基づいて算出することができる。更に、クラスタ生成装置２０は、この自己コンフィデンス値を、メンバ要素の数の２乗に比例する計算量で算出することができる。更に、クラスタ生成装置２０は、カイ２乗検定値を最大とするクラスタを、生成するべきクラスタとして決定する。これにより、クラスタ決定の精度を高めることができる。
【実施例２】
【００５７】
図４は、文書データベース１０及びクラスタ生成装置２０の機能ブロック図である（実施例２）。本例におけるクラスタ生成装置２０は、各々が複数の属性のうち少なくとも１つを有する複数の要素から、１〜２個程度の互いに強く関連する要素の集合、又は、他の全ての要素との関連が極めて弱い要素の集合を選択することを目的とする。文書データベース１０は、互いに関連の強さが定められた複数の要素として、複数の文書を格納する。複数の文書の各々は、予め定められた複数の属性の何れか、例えば、複数のキーワードの何れかを有する。一例として、文書nは、キーワードlを含み、キーワードl+1を含み、途中を省略して、キーワードl+kを含む。
【００５８】
２０は、要素集合選択部４００と、関連度算出部４１０と、属性クラスタ生成部４２０と、要素クラスタ生成部４３０とを有する。要素集合選択部４００は、複数の属性の各々について、その属性を有する要素の集合を選択する。例えば、要素集合選択部４００は、キーワードlを含む文書の集合として、文書n、文書n+1、文書n+2、及び文書m+2を選択する。
【００５９】
そして、関連度算出部４１０は、複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する。例えば，関連度算出部４１０は、キーワードlと、キーワードl+kとが関連する関連度を、これらのキーワードを共通して含む文書の数、即ち、文書n〜(n+2)及び文書m+2の4個に基づいて算出する。例えば、関連度算出部４１０は、共通して含む文書の数が多い場合に、その数が少ない場合と比較してより高い関連度を算出してもよい。
【００６０】
更に、文書データベース１０における複数の要素がブーリアンモデルでなく、TF-IDF技術によって関連の強さが定められている場合には、以下の何れかの方法を用いてもよい。
１．関連度算出部４１０は、複数の要素を列とし、複数の属性を行として、TF-IDF技術により定まる値を行列状に配列し、配列したこれらの値を、各属性についての要素ベクトルとしてそのまま用いる。
２．関連度算出部４１０は、複数の要素を列とし、複数の属性を行として、TF-IDF技術により定まる値を行列状に配列し、配列したこれらの値を、各属性を有する要素に基づいて変更する。
【００６１】
この場合、関連度算出部４１０は、この要素ベクトルに基づいて、属性間の関連度を算出する。例えば、関連度算出部４１０は、要素ベクトル間の角度がより小さい場合には、より高い関連度を算出する。
【００６２】
属性クラスタ生成部４２０は、算出したその関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する。例えば本例においては、属性クラスタ生成部４２０は、キーワードlからキーワードl+kまでを選択して属性クラスタを生成する。処理の具体例としては、属性クラスタ生成部４２０は、要素のクラスタを生成するための既存の方法を属性のクラスタに適用すればよい。
【００６３】
そして、要素クラスタ生成部４３０は、属性クラスタに含まれる全ての属性を有する要素の集合を求めて、クラスタリング結果として出力する。例えば、文書n、文書n+2、及び文書m+2が出力される。これに代えて、要素クラスタ生成部４３０は、属性クラスタに含まれる何れかの属性を有する要素の集合を求めて、クラスタリング結果として出力してもよい。
【００６４】
図５は、クラスタ生成装置２０がメンバ要素を選択してクラスタを生成する処理フローを示す（実施例２）。要素集合選択部４００は、複数の属性の各々について、その属性を有する要素の集合を選択する（Ｓ５００）。そして、関連度算出部４１０は、複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する（Ｓ５１０）。
【００６５】
次に、属性クラスタ生成部４２０は、算出したその関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する（Ｓ５２０）。そして、要素クラスタ生成部４３０は、属性クラスタに含まれる全ての属性を有する要素の集合を求めて、要素クラスタとして出力する（Ｓ５３０）。
【００６６】
以上、本実施例によれば、クラスタ生成装置２０は、属性及び要素の役割を交換して、２５個程度の所定の数の属性の集合を属性クラスタとして選択する。そして、これらの属性を含む要素をクラスタとして選択する。この結果、２５個程度の所定の数の要素を選択する方法を利用して、当該所定の数より少ない要素をクラスタとして選択することができる。これにより、利用者が経験・知識に基づいて発見することが困難な非常に小さいクラスタを適切に検出することができる。
【００６７】
図６は、クラスタ生成装置２０として機能するコンピュータ５００のハードウェア構成の一例を示す（実施例１及び２）。コンピュータ５００は、ホストコントローラ６８２により相互に接続されるＣＰＵ６００、ＲＡＭ６２０、グラフィックコントローラ６７５、及び表示装置６８０を有するＣＰＵ周辺部と、入出力コントローラ６８４によりホストコントローラ６８２に接続される通信インターフェイス６３０、ハードディスクドライブ６４０、及びＣＤ−ＲＯＭドライブ６６０を有する入出力部と、入出力コントローラ６８４に接続されるＢＩＯＳ６１０、フレキシブルディスクドライブ６５０、及び入出力チップ６７０を有するレガシー入出力部とを備える。
【００６８】
ホストコントローラ６８２は、ＲＡＭ６２０と、高い転送レートでＲＡＭ６２０をアクセスするＣＰＵ６００及びグラフィックコントローラ６７５とを接続する。ＣＰＵ６００は、ＢＩＯＳ６１０及びＲＡＭ６２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ６７５は、ＣＰＵ６００等がＲＡＭ６２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置６８０上に表示させる。これに代えて、グラフィックコントローラ６７５は、ＣＰＵ６００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００６９】
入出力コントローラ６８４は、ホストコントローラ６８２と、比較的高速な入出力装置である通信インターフェイス６３０、ハードディスクドライブ６４０、及びＣＤ−ＲＯＭドライブ６６０を接続する。通信インターフェイス６３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ６４０は、コンピュータ５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ６６０は、ＣＤ−ＲＯＭ６９５からプログラム又はデータを読み取り、ＲＡＭ６２０を介して入出力チップ６７０に提供する。
【００７０】
また、入出力コントローラ６８４には、ＢＩＯＳ６１０と、フレキシブルディスクドライブ６５０や入出力チップ６７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ６１０は、コンピュータ５００の起動時にＣＰＵ６００が実行するブートプログラムや、コンピュータ５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ６５０は、フレキシブルディスク６９０からプログラム又はデータを読み取り、ＲＡＭ６２０を介して入出力チップ６７０に提供する。入出力チップ６７０は、フレキシブルディスク６９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００７１】
コンピュータ５００に提供されるプログラムは、フレキシブルディスク６９０、ＣＤ−ＲＯＭ６９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ６７０及び/又は入出力コントローラ６８４を介して、記録媒体から読み出されコンピュータ５００にインストールされて実行される。コンピュータ５００にインストールされて実行される生成プログラムがコンピュータ５００に働きかけて行わせる動作は、図１から図５において説明したコンピュータ５００における動作と同一であるから、説明を省略する。
【００７２】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク６９０、ＣＤ−ＲＯＭ６９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ５００に提供してもよい。
【００７３】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００７４】
以上に示す実施例によると、以下の各項目に示す評価装置、クラスタ生成装置、プログラム、記録媒体、評価方法、及びクラスタ生成方法が実現される。
（項目１）  互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する評価装置であって、予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部とを備える評価装置。
【００７５】
（項目２）  前記コンフィデンス値算出部は、前記基準要素との関係がより強い前記基準個数の要素の何れかを中継要素として、当該中継要素との関係がより強い前記基準個数の要素の各々について、当該要素に達するために選択可能な全ての前記中継要素の数を算出し、当該要素に達するために選択可能な全ての中継要素のうち２つの中継要素の組み合わせの総数を算出し、各要素について算出した当該組み合わせの総数の合計に基づく値を前記自己コンフィデンス値として出力する項目１記載の評価装置。
（項目３）  互いに関連の強さが定められた複数の要素から何れかを選択してクラスタを生成するクラスタ生成装置であって、予め定められた基準要素について、当該基準要素との関係がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記クラスタから選択可能な２つのメンバ要素の組の各々について、当該組の一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全ての組について算出した当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部と、前記自己コンフィデンス値が予め定められた基準値より大きい場合に、評価対象の前記クラスタを、生成すべきクラスタと判断する要素クラスタ生成部とを備えるクラスタ生成装置。
【００７６】
（項目４）  前記クラスタ生成装置は、複数の文書を前記複数の要素として、文書に含まれるキーワードに基づいてクラスタを生成する装置であり、前記評価対象クラスタ選択部は、予め定められた文書について、当該文書と比較して含んでいるキーワードの組がより類似する前記基準個数の文書の集合である隣接要素集合を、前記評価対象のクラスタとして選択し、前記隣接要素集合選択部は、前記クラスタに含まれる各々の文書について、当該文書と比較して含んでいるキーワードの組がより類似する前記基準個数の文書の集合である隣接要素集合を選択し、前記コンフィデンス値算出部は、前記クラスタから選択可能な２つの文書の組み合わせについて、当該組み合わせの一方の文書の隣接要素集合及び他方の文書の隣接要素集合に共通して含まれる文書の数の、前記基準個数に対する割合を算出し、全ての組み合わせについて算出した当該割合の合計に基づく値を前記自己コンフィデンス値として出力し、前記要素クラスタ生成部は、前記自己コンフィデンス値が予め定められた基準値より大きい場合に、評価対象の前記クラスタを、生成すべきクラスタと判断する項目３記載のクラスタ生成装置。
（項目５）  互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を算出する評価装置であって、予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部とを備える評価装置。
【００７７】
（項目６）  前記コンフィデンス値算出部は、前記複数のメンバ要素の各々について、前記クラスタに含まれる要素のうち当該メンバ要素の隣接要素集合に含まれる要素の割合を算出し、各メンバ要素について算出した前記割合の合計に基づく値を前記自己コンフィデンス値として出力する項目５記載の評価装置。
（項目７）  前記コンフィデンス値算出部は、前記クラスタから選択可能な２つのメンバ要素の組み合わせの各々について、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全ての組について算出した当該割合の合計に基づく値を前記自己コンフィデンス値として算出する項目５記載の評価装置。
【００７８】
（項目８）  互いに関連の強さが定められた複数の要素から何れかを選択してクラスタを生成するクラスタ生成装置であって、予め定められた基準要素との関係がより強い予め定められた基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部と、前記基準個数を予め定められた範囲で変更した各クラスタについて、前記評価値を前記評価値算出部により算出させ、算出させた当該評価値を最大にするクラスタを選択して生成する要素クラスタ生成部とを有するクラスタ生成装置。
【００７９】
（項目９）  各々が複数の属性のうち少なくとも１つを有する複数の要素からクラスタを生成するクラスタ生成装置であって、前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択部と、前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出部と、算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成部と、前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成部とを備えるクラスタ生成装置。
（項目１０）  互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出する評価装置として、コンピュータを機能させるプログラムであって、前記コンピュータを、予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出部として機能させるプログラム。
【００８０】
（項目１１）  互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を算出する評価装置として、コンピュータを機能させるプログラムであって、前記コンピュータを、予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択部と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択部と、前記隣接要素集合選択部により選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出部と、前記隣接要素集合選択部が、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出部により算出される自己コンフィデンス値の理論値を算出する理論値算出部と、自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出部として機能させるプログラム。
（項目１２）  各々が複数の属性のうち少なくとも１つを有する複数の要素からクラスタを生成するクラスタ生成装置として、コンピュータを機能させるプログラムであって、前記コンピュータを、前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択部と、前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出部と、算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成部と、前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成部として機能させるプログラム。
（項目１３）  項目１０から１２の何れかに記載のプログラムを記録した記録媒体。
【００８１】
（項目１４）  互いに関連の強さが定められた複数の要素の何れかを選択して生成したクラスタについて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を、コンピュータにより算出する評価方法であって、前記コンピュータにより、予め定められた基準要素について、当該基準要素との関連がより強い基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択段階と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択段階と、前記クラスタから選択可能な２つのメンバ要素の組み合わせについて、当該組み合わせの一方のメンバ要素の隣接要素集合及び他方のメンバ要素の隣接要素集合に共通して含まれる要素の数の、前記基準個数に対する割合を算出し、全てのメンバ要素の組み合わせについての当該割合の合計に基づく値を前記自己コンフィデンス値として出力するコンフィデンス値算出段階とを備える評価方法。
（項目１５）  互いに関連の強さが定められた複数の要素の中から予め定められた基準個数の要素を選択して生成したクラスタについて、前記複数の要素全体に対する前記クラスタの特殊性の評価値を、コンピュータにより算出する評価方法であって、前記コンピュータにより、予め定められた基準要素との関係がより強い前記基準個数の要素の集合である隣接要素集合を、評価対象のクラスタとして選択する評価対象クラスタ選択段階と、前記クラスタに含まれる各々のメンバ要素について、当該メンバ要素との関連がより強い前記基準個数の要素の集合である隣接要素集合を選択する隣接要素集合選択段階と、前記隣接要素集合選択段階において選択された前記隣接要素集合に基づいて、当該クラスタに含まれるメンバ要素の選択の確信度を示す自己コンフィデンス値を算出するコンフィデンス値算出段階と、前記隣接要素集合選択段階において、前記隣接要素集合に代えて、前記複数の要素から無作為に前記基準個数の要素の集合を選択したと仮定した場合における、前記コンフィデンス値算出段階において算出される自己コンフィデンス値の理論値を算出する理論値算出段階と、自己コンフィデンス値の前記理論値に対する自己コンフィデンス値のカイ２乗検定値を、前記評価値として算出して出力する評価値算出段階とを備える評価方法。
【００８２】
（項目１６）  各々が複数の属性のうち少なくとも１つを有する複数の要素から、コンピュータによりクラスタを生成するクラスタ生成方法であって、前記コンピュータにより、前記複数の属性の各々について、当該属性を有する要素の集合を選択する要素集合選択段階と、前記複数の属性の各々が他の属性の各々と関連する強さを示す関連度を、当該属性及び当該他の属性を共通して含む要素の数に基づいて算出する関連度算出段階と、算出した前記関連度に基づいて、互いの関連度が基準以上である複数の属性を有する属性クラスタを生成する属性クラスタ生成段階と、前記属性クラスタに含まれる属性の少なくとも１つを有する要素の集合を求めてクラスタとして出力する要素クラスタ生成段階とを備えるクラスタ生成方法。
【図面の簡単な説明】
【００８３】
【図１】図１は、文書データベース１０及びクラスタ生成装置２０の機能ブロック図である（実施例１）。
【図２】図２は、クラスタ生成装置２０がメンバ要素を選択してクラスタを生成する処理フローを示す（実施例１）。
【図３】図３は、Ｓ２３０における処理の詳細を説明する図である（実施例１）。
【図４】図４は、文書データベース１０及びクラスタ生成装置２０の機能ブロック図である（実施例２）。
【図５】図５は、クラスタ生成装置２０がメンバ要素を選択してクラスタを生成する処理フローを示す（実施例２）。
【図６】図６は、クラスタ生成装置２０として機能するコンピュータ５００のハードウェア構成の一例を示す（実施例１及び２）。
【符号の説明】
【００８４】
１０  文書データベース
２０  クラスタ生成装置
３０  評価装置
４０  要素クラスタ生成部
３００  評価対象クラスタ選択部
３１０  隣接要素集合選択部
３２０  コンフィデンス値算出部
３３０  理論値算出部
３４０  評価値算出部
４００  要素集合選択部
４１０  関連度算出部
４２０  属性クラスタ生成部
４３０  要素クラスタ生成部
５００  コンピュータ
【図１】
2005301786.tif 000019
【図２】
2005301786.tif 000020
【図３】
2005301786.tif 000021
【図４】
2005301786.tif 000022
【図５】
2005301786.tif 000023
【図６】
2005301786.tif 000024