(57)【要約】【課題】  クラスタ数やクラスタの代表が人間の認知モデルに即して決定されるように、クラスタリングするようにする【解決手段】  プロトタイプ意味論における「典型的な例」と「周辺的な例」（図２Ａ）の考え方を発展させると、２つのアイテム間の認知におけるこのような方向性を、図２Ｂに示すように、「典型的な例」から「周辺的な例」へ向かう距離は、「周辺的な例」から「典型的な例」へ向かう距離よりも長いという非対称な距離尺度で表すことができる。２つのアイテム間に、２つのアイテム間の非対称な数理的な距離を対応付けて、２つアイテムを「典型的な例」と「周辺的な例」との関係で連結させるようにすることで、人間の認知モデルに即してクラスタ数やクラスタの代表が決定されるクラスタリングが実現する。【選択図】  図２
2006285419.tif 000002
【特許請求の範囲】
【請求項１】
クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択手段と、
クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択手段と、
前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出手段と、
前記算出手段より算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記連結手段は、前記算出手段により算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムの一方を親とし、他方を子として、前記注目アイテムと前記対象アイテムを親子関係で連結する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記第２の選択手段は、前記注目アイテムに最も近接する１個のアイテムを前記対象アイテムとして選択する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記第２の選択手段は、前記注目アイテムに近接する所定の数のアイテムを前記対象アイテムとして選択する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記連結手段は、前記注目アイテムが複数の親を有することを認めて、前記注目アイテムと前記対象アイテムを親子関係で連結する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記連結手段により、前記クラスタリングを行うアイテムの全てについての連結が行われた結果得られたクラスタのルートノードをクラスタの代表アイテムとする
ことを特徴とする請求項１に記載の情報処理装置。
【請求項７】
クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、
クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、
前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、
前記算出ステップより算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結ステップと
を含むことを特徴とする情報処理方法。
【請求項８】
クラスタリング処理を行うプロセッサに実行させるプログラムにおいて、
クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、
クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、
前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、
前記算出ステップより算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および方法、並びにプログラムに関し、特に、クラスタリングを適切に行うことができるようにする情報処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
クラスタリング技術は、機械学習やデータマイニングの分野で非常に重要な役割をもっている。例えば、画像認識、圧縮におけるベクトル量子化や、自然言語処理における単語シソーラスの自動生成などでは、クラスタリングの能力がその精度に直結する。
【０００３】
従来のクラスタリング技術は、大きく分けて階層型、分割最適化型に分類される。
【０００４】
階層型クラスタリングは、アイテム間の距離が定義できる場合に、１つのアイテムからなるクラスタから始まり、クラスタ同士をマージして徐々に大きなクラスタを生成する手法である。
【０００５】
分割最適化型クラスタリング(非特許文献１および２参照)は、距離と絶対位置が定義される空間上に配置されたアイテムが、事前に決めたクラスタ中心にどの程度帰属するかを求め、それに基づいてクラスタ中心を繰り返し計算する手法である。
【０００６】
【非特許文献１】MacQueen, J., “Some Methods for Classification and Analysis of Multivariate Observations,” Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability, pp.281-297, 1967.
【非特許文献２】Zhang, B. et al., “K-Harmonic Means - a Data Clustering Algorithm,” Hewlett-Packard Labs Technical Report HPL-1999-124, 1999.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、階層型クラスタリングでは、クラスタ間の距離の定義（例えば、最短距離法、最長距離法、群平均法によって定義された距離）によって様々な形態のクラスタが生成され、その選択基準は明確ではない。
【０００８】
また、通常、クラスタが１個になるまでマージが行われるが、所定の数のクラスタが生成された時点で停止したい場合、通常、予めアドホックに決めたクラスタ数や距離の閾値で停止するようになされている。MDL基準やAICなどが利用されることもあるが、実際上有用であるという報告は得られていない。
【０００９】
分割最適化型クラスタリングも、やはりクラスタ数は事前に決定しておかなければならない。
【００１０】
また、階層型クラスタリングおよび分割最適化型クラスタリングのいずれにおいても、生成された各クラスタにおいてそれを代表するアイテムを取り出す基準は存在しない。例えば分割最適化型クラスタリングであれば、通常、最終的なクラスタ中心に最も近いアイテムがそのクラスタの代表とされるが、それが人間の認知おいて意味するところは明らかではない。
【００１１】
本発明は、このような状況に鑑みてなされたものであり、人間の認知モデルに即してクラスタの数やクラスタの代表が決定されるようにクラスタリングするものである。
【課題を解決するための手段】
【００１２】
本発明の情報処理装置は、クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択手段と、クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択手段と、注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出手段と、算出手段より算出された距離に基づいて、注目アイテムと対象アイテムを連結する連結手段とを備えることを特徴とする。
【００１３】
連結手段は、算出手段により算出された距離に基づいて、注目アイテムと対象アイテムの一方を親とし、他方を子として、注目アイテムと対象アイテムを親子関係で連結することができる。
【００１４】
第２の選択手段は、注目アイテムに最も近接する１個のアイテムを対象アイテムとして選択することができる。
【００１５】
第２の選択手段は、注目アイテムに近接する所定の数のアイテムを対象アイテムとして選択することができる。
【００１６】
連結手段は、注目アイテムが複数の親を有することを認めて、注目アイテムと対象アイテムを親子関係で連結することができる。
【００１７】
連結手段により、クラスタリングを行うアイテムの全てについての連結が行われた結果得られたクラスタのルートノードをクラスタの代表アイテムとすることができる。
【００１８】
本発明の情報処理方法は、クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、算出ステップより算出された距離に基づいて、注目アイテムと対象アイテムを連結する連結ステップとを含むことを特徴とする。
【００１９】
本発明のプログラムは、クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、算出ステップより算出された距離に基づいて、注目アイテムと対象アイテムを連結する連結ステップとを含むことを特徴とする。
【００２０】
本発明の情報処理装置および方法、並びにプログラムにおいては、クラスタリングを行うアイテムが、注目アイテムとして順次選択され、クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムが対象アイテムとして選択され、注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離が算出され、算出された距離に基づいて、注目アイテムと対象アイテムが連結される。
【発明の効果】
【００２１】
本発明によれば、人間の認知モデルに即してクラスタの数やクラスタの代表が決定されるクラスタリングを実現することができる。
【発明を実施するための最良の形態】
【００２２】
以下に本発明の最良の形態を説明するが、開示される発明と実施の形態との対応関係を例示すると、次のようになる。明細書中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００２３】
さらに、この記載は、明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により出現し、追加される発明の存在を否定するものではない。
【００２４】
請求項１の情報処理装置は、
クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択手段（例えば、図１のクラスタリング部２６）と、
クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択手段（例えば、図１のクラスタリング部２６）と、
注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出手段（例えば、図１のクラスタリング部２６）と、
算出手段より算出された距離に基づいて、注目アイテムと対象アイテムを連結する連結手段（例えば、図１のクラスタリング部２６）と
を備えることを特徴とする。
【００２５】
請求項２の情報処理装置は、
連結手段は、算出手段により算出された距離に基づいて、注目アイテムと対象アイテムの一方を親とし、他方を子として、注目アイテムと対象アイテムを親子関係で連結する（例えば、図４のステップＳ８またはステップＳ９）
ことを特徴とする。
【００２６】
請求項３の情報処理装置は、
第２の選択手段は、注目アイテムに最も近接する１個のアイテムを対象アイテムとして選択する（例えば、図４のステップＳ２）
ことを特徴とする
【００２７】
請求項４の情報処理装置は、
第２の選択手段は、注目アイテムに近接する所定の数のアイテムを対象アイテムとして選択する（例えば、図４のステップＳ２）
ことを特徴とする。
【００２８】
請求項５の情報処理装置は、
連結手段は、注目アイテムが複数の親を有することを認めて、注目アイテムと対象アイテムを親子関係で連結する（例えば、ステップＳ８またはステップＳ９）
ことを特徴とする。
【００２９】
請求項６の情報処理装置は、
連結手段により、クラスタリングを行うアイテムの全てについての連結が行われた結果得られたクラスタ（例えば、図８）のルートノード（例えば、「温かい」および「ワイルド」）をクラスタの代表アイテムとする（例えば、図４のステップＳ１１）
ことを特徴とする。
【００３０】
請求項７の情報処理方法は、
クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップ（例えば、図４のステップＳ１）と、
クラスタリングを行うアイテムの中から、注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップ（例えば、図４のステップＳ２）と、
注目アイテムと対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップ（例えば、図４のステップＳ４）と、
算出ステップより算出された距離に基づいて、注目アイテムと対象アイテムを連結する連結ステップ（例えば、図４のステップＳ８またはステップＳ９）と
を含むことを特徴とする。
【００３１】
請求項８に記載のプログラムの各ステップの具体例も、請求項７に記載の情報処理方法の各ステップの発明の実施の形態における具体例と同様である。
【００３２】
図１は、本発明の情報処理装置１の構成例を示している。この情報処理装置１は、人間の認知モデルに即してクラスタ数やクラスタの代表が決定されるように、与えられたアイテムをクラスタリングする。
【００３３】
はじめに本発明におけるクラスタリングの原理について説明する。本発明におけるクラスタリングは、認知心理学におけるプロトタイプ意味論に基づく認知モデルを利用して行われる。
【００３４】
プロトタイプ意味論とは、人間によるあるカテゴリー内にある概念（例えば、あるカテゴリー内の単語）の認知においては、「典型的な例」と「周辺的な例」が存在するというものである。
【００３５】
例えば鳥類というカテゴリー内にある「スズメ」、「ダチョウ」、「ペンギン」を例にとり、
質問１：「スズメ」は「ダチョウ」に似ているか
質問２：「ダチョウ」は「スズメ」に似ているか
という、似ているかを問う対象を入れ替えた２つの質問をすると、
図２Ａに示すように、質問１に対しては、「似ていない」、質問２に対しては、「似ている」という結果が得られる。「スズメ」と「ペンギン」についても同様に、質問１（「スズメ」は「ペンギン」に似ているか）に対しては、「似ていない」、質問２（「ペンギン」は「スズメ」に似ているか）に対しては、「似ている」という結果が得られる。
【００３６】
すなわち「スズメ」は、鳥類において「典型的な例」であり、「ダチョウ」と「ペンギン」は、「周辺的な例」となる。
【００３７】
ここでこのプロトタイプ意味論における「典型的な例」と「周辺的な例」の考え方を発展させると、２つのアイテム間の認知におけるこのような方向性（似ているか否かの対象を入れ替えることによってその回答が異なるような性質）を、図２Ｂに示すように、「典型的な例」から「周辺的な例」へ向かう距離（「典型例な例」が「周辺的な例」に似ているという度合い）は、「周辺的な例」から「典型的な例」へ向かう距離（「周辺的な例」が「典型的な例」に似ているという度合い）よりも長い（小さい）という非対称な距離尺度で表すことができる。
【００３８】
アイテム間のこのような方向性に対応する非対称な距離尺度として、Kullback-Leibler Divergence(以下、KL距離と称する)が存在する。
【００３９】
KL距離では、アイテムａiとａjが確率分布ｐi (x)とｐj (x)で表現される場合において、距離Ｄ(ａi ||ａj)が、式（１）に示すように定義されるスカラー量となるが、「なでらかな確率分布」から「偏った確率分布」への距離の方が、「偏った確率分布」から「なでらかな確率分布」への距離よりも長くなる傾向がある。一般的なアイテムの確率分布は「なでらかなもの」となり、特殊なアイテムの確率分布は「偏ったもの」となる。
【００４０】
【数１】
2006285419.tif 000003
【００４１】
例えば、アイテムａiとａjに対して、確率変数ｚk (k=0,1,2)が定義される場合であって、確率分布ｐ(ｚk|ａi)= (0.3, 0.3, 0.4) で、確率分布ｐ(ｚk|ａj)= (0.1, 0.2, 0.7)であり、確率分布ｐ(ｚk|ａi)の方が確率分布ｐ(ｚk|ａj)よりなでらかなとき（アイテムａiとアイテムａjの対比において、アイテムａiが一般的なアイテム（典型的な例）で、アイテムａjが特殊なアイテム（周辺的な例）であるとき）、KL(ｐi||ｐj)=0.0987＞KL(ｐj||ｐi)=0.0872とうい結果が得られる。
【００４２】
このようにKL距離は、「一般性の高いアイテム（典型的な例）」から「一般性の低いアイテム(周辺的な例)」への距離Ｄ(一般的なアイテム||周辺的なアイテム)の方が、その逆の距離Ｄ(周辺的なアイテム||一般的なアイテム)よりも大きくなるという、プロトタイプ意味論の認知モデルにおける「典型的な例」と「周辺的な例」の非対称の距離関係に対応している。
【００４３】
すなわち本発明は、２つのアイテム間に、２つのアイテム間の、非対称な数理的な距離（例えば、KL距離）を対応付けて、２つアイテムを「典型的な例」と「周辺的な例」との関係で連結させるようにすることで、人間の認知モデルに即してクラスタ数やクラスタの代表が決定されるクラスタリングを実現するものである。
【００４４】
KL距離は、任意の分布ｐ,ｑに対してKL(ｐ||ｑ)≧0であるが、一般にKL(ｐ||ｑ)≠KL(ｑ||ｐ)で、また一般の距離で成り立つ三角不等式も成り立たないため、厳密な意味での距離ではない。
【００４５】
なおこのKL距離を利用して、方向性のあるアイテム間の類似度を定義することができる。例えばexp(-KL(ｐi||ｐj))や、KL(ｐi||ｐj)-1など、距離に対して単調減少するものであれば、任意である。
【００４６】
また２つのアイテムに対応付ける距離の条件は、「一般性の高いアイテム（典型的な例）」から「一般性の低いアイテム(周辺的な例)」への距離の方が、その逆の距離よりも大きくなるという、プロトタイプ意味論の認知モデルに一致する非対称性を持つものであれば、KL距離以外でも、他の情報論的なスカラー量や、ベクトル空間上でのベクトルの大きさを重みとした方向性を持つ修正Euclid距離（式（２））などでも良い。
【００４７】
【数２】
2006285419.tif 000004
【００４８】
図１に戻り情報処理装置１の構成例を説明する。
【００４９】
なおこの例の場合、単語のクラスタリングを行うものとする。確率変数ｚk(k=0,1,...,M-1)を、たとえば共起単語の出現確率やPLSA(Probabilistic Latent Semantic Analysis)の潜在変数とした場合、特殊な単語（周辺的な例）の確率分布は「偏りが大きいもの」となり、一般的な単語（典型的な例）の確率分布は「なだらかなもの」となる傾向があるので、対比する２つの単語の数理的な距離（例えば、KL距離）に応じて、一方を「典型的な例」（この例のでは親）とし、他方を「周辺的な例」（子）として連結することができる。
【００５０】
例えば単語ｗi、ｗjに対してKL距離によって定義される距離Ｄにおいて、Ｄ(ｗi||ｗj)(=KL(ｐi||ｐj))＞Ｄ(ｗj||ｗi) (=KL(ｐj ||ｐi))となれば単語ｗiが「典型的な例」で、単語ｗjが「周辺的で例」あるので、単語ｗiは親とされ、単語ｗjは子とされて、両者が連結される。
【００５１】
文書記憶部２１には、クラスタリングされるアイテム（この例の場合、単語）を含む元データとしての文章（テキストデータ）が記憶されている。
【００５２】
形態素解析部２２は、文書記憶部２１に記憶されているテキストデータ（文書）を、単語（例えば、「温かい」、「優しい」、「ぬくもり」、「ワイルド」、「荒々しい」、「ガッツ」、「荒削り」など）に切り分けて、単語モデル生成部２３に供給する。
【００５３】
単語モデル生成部２３は、形態素解析部２２から供給された各単語を、単語間の関連性（距離）を見るために数理モデル化し、その結果得られた単語モデルを、単語モデル記憶部２４に記憶する。
【００５４】
単語モデルとしては、PLSAやSAM(Semantic Aggregate Model)などの確率モデルがある。これらは、文章と単語または単語と単語の共起の背後に潜在的な変数が存在し、その確率的な生起によって個々の表出が決定される。
【００５５】
PLSAは、「Hofmann, T., “Probabilistic Latent Semantic Analysis,” Proc. of Uncertainty in Artificial Intelligence, 1999.」に、SAMは、「持橋大地, 松本裕治, “意味の確率的表現,” 情処研報2002-NL-147, pp.77-84, 2002.」に紹介されている。
【００５６】
例えばSAMの場合、単語ｗiと単語ｗjの共起確率は、潜在的な確率変数ｃ（予め決められたｋ個のｃ0，ｃ1,・・・ｃk-1の値を取りうる変数）を用いて、式（３）で表され、式（３）から式（４）に示すように、単語ｗに対する確率分布P(ｃ|ｗ)を定義することができ、それが単語モデルとなる。式（３）中、確率変数ｃは潜在的な変数であり、確率分布P(ｗ|ｃ)および確率分布P(ｃ)は、EMアルゴリズムによって求められる。
【００５７】
【数３】
2006285419.tif 000005
【００５８】
【数４】
2006285419.tif 000006
【００５９】
図３には、ｋ＝４の場合の単語「温かい」、「優しい」、「ぬくもり」、「ワイルド」、「荒々しい」、「ガッツ」、および「荒削り」の単語モデル（PLSA等を利用した潜在変数の確率分布）の例が示されている。
【００６０】
単語モデルとしては、PLSAやSAMなどの確率モデルの他、文書ベクトルや共起ベクトル、LSA(Latent Semantic Analysis)などで次元圧縮された意味ベクトルなどがあり、いずれを採用するかは任意である。なおPLSAやSAMは、このように潜在的な確率変数の空間で単語が表現されるので、通常の共起ベクトルなどを利用するよりも、意味的な傾向を把握しやすいとされている。
【００６１】
図１に戻りクラスタリング部２５は、上述した原理に基づいて単語のクラスタリングを行い、クラスタリング結果を、クラスタリング結果記憶部２６に記憶する。
【００６２】
処理部２７は、クラスタリング結果記憶部２６に記憶されたクラスタリング結果を利用して所定の処理を実行する（後述）。
【００６３】
次に、本発明におけるクラスタリング処理を説明するが、はじめに、図４のフローチャートを参照してその概略を説明し、その後、具体例に基づいて再度説明する。
【００６４】
ステップＳ１において、クラスタリング部２５は、単語モデル記憶部２４に単語モデルが記憶されている単語の１つに注目し、その単語ｗiの単語モデルを選択する。
【００６５】
ステップＳ２において、クラスタリング部２５は、単語モデル記憶部２４に記憶されている単語モデルを利用して、単語ｗiに対してもっとも近接する（例えば共起しやすいまたは意味的に類似する）単語を、以下の処理で単語ｗiと連結する単語ｗj（対象単語）として選択する。
【００６６】
具体的には、クラスタリング部２５は、例えば、式（５）に示すように、単語ｗiから単語ｗjへの距離（例えば、KL距離）が最も小さい単語、または式（６）に示すように、単語ｗiから単語ｗjへの距離と、単語ｗjから単語ｗiへの距離との合計が最小となる単語を単語ｗjとする。
【００６７】
【数５】
2006285419.tif 000007
【００６８】
【数６】
2006285419.tif 000008
【００６９】
ステップＳ３において、クラスタリング部２５は、単語ｗjが単語ｗiの親または子であるか否かを判定する。
【００７０】
後述するステップＳ８またはステップＳ９で、２つの単語の距離関係から「典型的な例」となる単語が親とされ、「周辺的な例」となる単語が子とされるので、ここでは、単語ｗjが、先に行われたその処理で、既に、単語ｗiの親または子とされているかが判定される。
【００７１】
ステップＳ３で、単語ｗjが単語ｗiの親でも子でもないと判定された場合、ステップＳ４に進む。
【００７２】
ステップＳ４において、クラスタリング部２５は、相互の、距離Ｄ(ｗi|| ｗj)（=KL (ｐi||ｐj)）と距離Ｄ(ｗj|| ｗi)（=KL (ｐj ||ｐi)）を求めるとともに、距離Ｄ(ｗi||ｗj)＞距離Ｄ(ｗj||ｗi)であるか否かを判定する。
【００７３】
ステップＳ４で、距離Ｄ(ｗi ||ｗj)＞距離Ｄ(ｗj ||ｗi)であると判定された場合、すなわち、単語ｗiと単語ｗjとの対比において、単語ｗiが「典型的な例」で、単語ｗjが「周辺的な例」であるとき（図２）、ステップＳ５に進む。
【００７４】
ステップＳ５において、クラスタリング部２５は、単語ｗj（いまの場合子となり得る単語）に親が存在するか（単語ｗjが他の単語ｗkの子になっているか）否かを判定し、親が存在すると判定した場合、ステップＳ６に進む。
【００７５】
ステップＳ６において、クラスタリング部２５は、単語ｗjから単語ｗiへの距離Ｄ(ｗj||ｗi)と、単語ｗjから単語ｗkへの距離Ｄ(ｗj||ｗk)をそれぞれ求めるとともに、距離Ｄ(ｗj||ｗi)＜距離Ｄ(ｗj||ｗk)であるか否かを判定し、その式が成り立つと判定した場合（単語ｗiへの距離の方が、単語ｗkへの距離より短い場合）、ステップＳ７に進み、 単語ｗjと単語ｗkの親子関係を解消する。
【００７６】
ステップＳ５で、単語ｗjに親が存在しないと判定されたとき、またはステップＳ７で単語ｗjと単語ｗkとの親子関係が解消されたとき、ステップＳ８に進み、クラスタリング部２５は、単語ｗiを単語ｗjの親とし、単語ｗjを単語ｗiの子として、単語ｗiと単語ｗjを連結する。
【００７７】
ステップＳ４で、距離Ｄ(ｗi||ｗj)＞距離Ｄ(ｗj||ｗi)ではないと判定されたとき、ステップＳ９に進み、クラスタリング部２５は、単語ｗiを単語ｗjの子とし、単語ｗjを単語ｗiの親として、単語ｗiと単語ｗjを連結する。
【００７８】
ステップＳ３で、単語ｗjが単語ｗiの親または子である場合（すでに単語ｗiと単語ｗjが連結されている場合）、ステップＳ６で距離Ｄ(ｗj||ｗi)＜距離(ｗj||ｗk)でないと判定されたとき（単語ｗkへの距離の方が、単語ｗiへの距離より短い場合）、またはステップＳ８若しくはステップＳ９で、単語ｗiと単語ｗjとが連結されたとき、すなわち単語ｗiが単語ｗjまたは単語ｗkと連結された場合、ステップＳ１０に進む。
【００７９】
ステップＳ１０において、クラスタリング部２５は、単語モデル記憶部２４に記憶されている全単語モデル（単語）を選択したか否かを判定し、選択していない単語が残っていると判定した場合、ステップＳ１に戻り、次の単語を選択して、ステップＳ２以降の処理を同様に実行する。
【００８０】
ステップＳ１０で、全単語を選択したと判定された場合、ステップＳ１１に進み、ステップＳ１乃至ステップＳ１０の処理を繰り返すことで形成されたクラスタのルートノードのアイテム（単語）をそのクラスタの代表アイテム（単語）として抽出し、形成されたクラスタとともに、クラスタ結果記憶部２６に記憶する。
【００８１】
次に、単語モデル記憶部２４に記憶されている、図３に示したような、「温かい」等の単語モデルを例として、クラスタリング処理を具体的に説明する。なお「温かい」、「優しい」、「ぬくもり」、「ワイルド」、「荒々しい」、「ガッツ」、および「荒削り」の単語のそれぞれに対するKL距離は、図５に示すようになっているものとする。図５中、各セルに示される数値が、表中の行要素から列要素へのKL距離である。
【００８２】
はじめに単語「温かい」が単語ｗiして選択される（その単語モデルが選択される）（ステップＳ１）。なおステップＳ１では、「温かい」、「優しい」、「ぬくもり」、「ワイルド」、「荒々しい」、「ガッツ」、そして「荒削り」の順で各単語の単語モデルが選択されるものとする。
【００８３】
「温かい」ｗiが選択されると、「温かい」ｗiの最近接単語ｗjが選択される（ステップＳ２）。なお、ここで最近接単語は、距離Ｄ（=KL(単語ｗi ||単語ｗj)）（式（５））が最も短い単語が単語ｗjとして選択されるものとする。
【００８４】
図５に示す、「温かい」ｗiと、他の単語との距離から、「ぬくもり」への距離Ｄ（=KL(「温かい」||「ぬくもり」)）が0.0125で最小であるので、「ぬくもり」が単語ｗjとして選択される。
【００８５】
いまの場合、「ぬくもり」ｗjは、単語「温かい」ｗiの親でもなく子でもないので（ステップＳ３）、次に両者の親子関係が判定される（ステップＳ４）。
【００８６】
距離Ｄ（＝KL(「温かい」ｗi ||「ぬくもり」ｗj)）が0.0125で、距離Ｄ（=KL(「ぬくもり」ｗj||「温かい」ｗi)）が0.0114で、距離Ｄ(「温かい」ｗi ||「ぬくもり」ｗj)＞距離Ｄ(「ぬくもり」ｗj||「温かい」ｗi)となるので（図６Ａ）、次に「ぬくもり」ｗjに親があるか否かが判定される（ステップＳ５）。
【００８７】
いまの場合、「ぬくもり」ｗjに親はいないので、「温かい」ｗiが「ぬくもり」ｗjの親とされ、「ぬくもり」ｗjが「温かい」ｗiの子とされて、「温かい」と「ぬくもり」が連結される（図６Ｂ）（ステップＳ８）。図６に示す矢印の根元が「子」となる単語を、矢印の先が「親」となる単語を示している。図７Ｂにおいても同様である。
【００８８】
次に「優しい」（図３）が単語ｗiとして選択され（ステップＳ１）、「優しい」ｗiの最近接単語ｗjが選択される（ステップＳ２）。
【００８９】
図５に示す、「優しい」ｗiと、他の単語との距離から、「温かい」への距離Ｄ（=KL(「優しい」||「温かい」)が0.0169で最小となるので、「温かい」が単語ｗjとして選択される。
【００９０】
いまの場合、「温かい」ｗjは「優しい」ｗiの親でもなく子でもないので（ステップＳ３）、次に親子関係が判定される（ステップＳ４）。
【００９１】
距離Ｄ(「優しい」ｗi ||「温かい」ｗj)が0.0169で、距離Ｄ(「温かい」ｗj ||「優しい」ｗi)が0.0174で、距離Ｄ(「優しい」ｗi ||「温かい」ｗj)＜距離Ｄ(「温かい」ｗj ||「優しい」ｗi)となるので（図７Ａ）、「優しい」ｗiが「温かい」ｗjの子とされ、「温かい」ｗjが「優しい」ｗiの親とされて、「優しい」と「温かい」が連結される（図７Ｂ）（ステップＳ９）。
【００９２】
次に「ぬくもり」（図３）が単語ｗiとして選択され（ステップＳ１）、「ぬくもり」ｗiの最近接単語ｗjが選択される。
【００９３】
図５に示す、「ぬくもり」ｗiと、他の単語との距離から、「温かい」への距離Ｄが0.0114で最小となるので、「温かい」が単語ｗjとして選択される。
【００９４】
しかしいまの場合、「温かい」ｗjは、先の処理で「ぬくもり」ｗiの親されているので（親子関係が成立しているので）（図６Ｂ）、その親子関係はそのまま維持され、次の「ワイルド」が単語ｗiとして選択される（ステップＳ１）。
【００９５】
「ワイルド」、並びにその後に選択される「荒々しい」、「ガッツ」、および「荒削り」（図３）に対しても同様な処理が行われる。
【００９６】
以上のように、「温かい」乃至「荒削り」（図３）に対してクラスタリング処理が行われると、図８に示すような、「温かい」、「ぬくもり」、および「優しい」からなるクラスタと、「ワイルド」、「荒々しい」、「ガッツ」、および「荒削り」からなるクラスタが形成される。すなわちこの７個の単語からは２個のクラスタが形成され、それぞれのクラスタの代表語は「温かい」と「ワイルド」となる。
【００９７】
クラスタのルートノードの単語（「温かい」、「ワイルド」）は、その単語に近接する単語(１個以上の単語)は自分の子にしかならず、かつ親も持っていないという状態になり、ルートノード周辺の空間において子方向以外に疎になるので、クラスタが自動的に区切られる。
【００９８】
また、抽象度(一般性)の高い単語ほど親になりやすいので、ルートノードをクラスタの代表とすることで、そのクラスタの中でもっとも抽象度(一般性)の高い単語をクラスタの代表とすることができる。
【００９９】
このように人間の認知に即してクラスタ数やクラスタの代表が決定される。
【０１００】
なお以上においては、アイテムｗiと親子関係を結ぶアイテムｗjを、最近接アイテムの１個にしたが（図４のステップＳ２）、上位N個(Nは全アイテム数より小さい)をアイテムｗjとして選択することができる。このように複数のアイテムをアイテムｗjとし、アイテムｗiとそれらとの親子関係を成立させれば、クラスタの裾を広げることができる（換言すれば、その数によりクラスタの広がりを調整することができる）。なお、Nを大きくとりすぎると全てのアイテムが１つのクラスタに含まれるような結果が得られてしまう場合がある。
【０１０１】
また、複数の近接アイテムｗjに対する関係を見るときに、注目しているアイテムｗiが複数のアイテムの子になる(即ちアイテムｗiが複数の親を持つ)ことを許せば（例えば、図４のステップＳ５乃至ステップＳ７の処理を省略すれば）、ひとつのアイテムが複数のクラスタにまたがって所属することになる。この場合、ルートノード以外での親子関係の接続はクラスタ同士の接続とはせずに、ルートから子方向へたどれるアイテムをそのルートノードを代表アイテムとするクラスタの成員とすることができる（例えば、図４のステップＳ１１）。これにより、あるアイテムが複数のクラスタへの帰属を持つソフトクラスタリングが実現される。その帰属度は、等価、直上の単語への類似度、またはルートとなる単語への類似度などで定義できる。
【０１０２】
さらに上述したクラスタリング処理において以下のような制約条件を加えることができる。
【０１０３】
全く類似しないアイテム同士が親子関係を結ばないように、アイテムｗjを選択する際に（図４のステップＳ２）、距離の閾値を決め、それ以上の距離となるアイテムをアイテムｗjとして選択しないようにすることもできる。
【０１０４】
また類似性をより確実なものとするために、アイテム内の最大成分が同じ要素となるなどの制約を加えることもできる。
【０１０５】
例えば、アイテムｗikをアイテムｗiのｋ番目の要素(単語ベクトルのｋ番目の要素やｐ(ｚk|ｗi))として、それが一致することを（式（７））、アイテムｗjの選択の条件とすることもできる。
【０１０６】
【数７】
2006285419.tif 000009
【０１０７】
また親子関係を確実なものにするために、例えばアイテムが確率分布で表現される場合、エントロピー(式（８）)を一般性の指標とし、かならずエントロピーの大きいアイテムを親とするなどの制約も加えることができる（図４のステップＳ８およびステップＳ９）。
【０１０８】
【数８】
2006285419.tif 000010
【０１０９】
例えばｐ(ｚk|ｗi)=(0.3, 0.3, 0.4)、ｐ(ｚk|ｗj)=(0.1, 0.2, 0.7)の場合、エントロピーはそれぞれ0.473と0.348となり、一般的な分布を持つアイテムｗiの方が、エントロピーが大きくなる。この場合、この２個の単語が親子関係を結べるとき(いずれかの最近接単語がもう片方となるとき)、アイテムｗiが必ず親となる。
【０１１０】
またアイテムをベクトル表現した場合は、一般性の尺度として例えば単語なら総出現頻度や、文書に対するχ2値の逆数などを利用することができる。
【０１１１】
なおχ2値は、「長尾 et al, “日本語文献における重要語の自動抽出,” 情報処理, Vol.17, No.2, 1976.」に紹介されている。
【０１１２】
次に、図１の処理部２７の、以上のようにして得られたクラスタリング結果に基づく処理の具体例を説明する。
【０１１３】
例えば、文書記憶部２１に音楽ＣＤのレビュー文が記憶され、レビュー文を構成する単語についてクラスタリングされて、その結果がクラスタリング結果記憶部２６に記憶されている場合、処理部２７は、クラスタリング結果記憶部２６に記憶されているクラスタを利用して、ユーザより入力されたキーワードに応じたＣＤを検索する処理を行う。
【０１１４】
具体的には、処理部２７は、入力されたキーワードが属するクラスタを検出し、そのクラスタに属する単語を、レビュー文の特徴的な単語（ＣＤの内容を端的に表す単語）とするＣＤを検索する。なおレビュー文のＣＤの内容を端的に表す単語は予め決められているものとする。
【０１１５】
レビュー文の筆者の違い、または微妙な表記や表現の揺れによって同じような内容の音楽ＣＤであっても、そのＣＤの内容を端的に表す単語が異なる場合があるが、本発明によるクラスタリング結果を利用すれば、同じような内容の音楽ＣＤの内容を端的に表す単語は通常同じクラスタに属するものと考えられるので、同じような内容の音楽ＣＤを適切に検索することができる。
【０１１６】
なお検索したＣＤを紹介する際に、キーワードが属するクラスタの代表単語をユーザに提供することもできる。
【０１１７】
また文書記憶部２１にコンテンツのメタデータ（コンテンツに関連する文書）が記憶され、そのメタデータを構成する単語についてクラスタリングされて、その結果がクラスタリング結果記憶部２６に記憶されている場合、処理部２７は、ユーザの嗜好情報とメタデータのマッチングを行って、そのマッチング結果に基づいて、ユーザが好むと思われるコンテンツを推薦する処理を行う。
【０１１８】
具体的には、処理部２７は、マッチングをとる際に、意味的に類似した単語（同じクラスタに属する単語）を１種類のメタデータとして扱ってマッチングを行う。
【０１１９】
メタデータに出現する単語をそのまま利用すると非常にスパースになってアイテム同士のマッチングが上手くいかない場合が生じるが、このように、意味的に類似した単語を１種類のメタデータとして扱えば、そのようなスパースネスが解消される。さらにアイテム同士のマッチングに強く寄与したメタデータをユーザに提示するような場合でも、代表的な(一般性の高い)単語（クラスタの代表単語）を提示するようにすれば、ユーザは直感的にアイテムを把握できるようになる。
【０１２０】
上述したクラスタリング処理などの一連の処理は、専用のハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。一連の処理をソフトウエアによって行う場合、例えば、その一連の処理は、図９に示されるような（パーソナル）コンピュータにプログラムを実行させることにより実現することができる。
【０１２１】
図９において、CPU（Central Processing Unit）１１１は、ROM（Read Only Memory）１１２に記憶されているプログラム、またはハードディスク１１４からRAM（Random Access Memory）１１３にロードされたプログラムに従って各種の処理を実行する。RAM１１３にはまた、CPU１１１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１２２】
CPU１１１、ROM１１２、およびRAM１１３は、バス１１５を介して相互に接続されている。このバス１１５にはまた、入出力インタフェース１１６も接続されている。
【０１２３】
入出力インタフェース１１６には、キーボード、マウス、入力端子などよりなる入力部１１８、CRT(Cathode Ray Tube)，LCD(Liquid Crystal display)などよりなるディスプレイ、出力端子、並びにスピーカなどよりなる出力部１１７、ターミナルアダプタ、ADSL（Asymmetric Digital Subscriber Line）モデムや、LAN (Local Area Network)カード等より構成される通信部１１９が接続されている。通信部１１９は、インターネットなどの各種のネットワークを介しての通信処理を行う。
【０１２４】
入出力インタフェース１１６にはまた、ドライブ１２０が接続され、磁気ディスク（フロッピディスクを含む）１３１、光ディスク（CD-ROM(Compact Disk-Read Only Memory) DVD Digital Versatile Disk）を含む）１３２、光磁気ディスク（MD（Mini-Disk）を含む）１３３、或いは半導体メモリなどのリムーバブルメディア（記録媒体）１３４が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じてハードディスク１１４にインストールされる。
【０１２５】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１２６】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【図面の簡単な説明】
【０１２７】
【図１】本発明の情報処理装置１の構成例を示すブロック図である。
【図２】本発明におけるクラスタリング処理の原理を説明する図である。
【図３】単語モデルの例を示す図である。
【図４】本発明におけるクラスタリング処理を説明するフローチャートである。
【図５】単語間のKL距離の例を示す図である。
【図６】親子関係を示す図である。
【図７】他の親子関係を示す図である。
【図８】クラスタリング結果を示す図である。
【図９】パーソナルコンピュータの構成例を示す図である。
【符号の説明】
【０１２８】
２１  文書記憶部，  ２２  形態素解析部，  ２３  単語モデル生成部，  ２４  単語モデル記憶部，  ２５  クラスタリング部，  ２６  クラスタ結果記憶部，  ２７  処理部
【図１】
2006285419.tif 000011
【図２】
2006285419.tif 000012
【図３】
2006285419.tif 000013
【図４】
2006285419.tif 000014
【図５】
2006285419.tif 000015
【図６】
2006285419.tif 000016
【図７】
2006285419.tif 000017
【図８】
2006285419.tif 000018
【図９】
2006285419.tif 000019