[go: up one dir, main page]

JP2006285419A - 情報処理装置および方法、並びにプログラム - Google Patents

情報処理装置および方法、並びにプログラム Download PDF

Info

Publication number
JP2006285419A
JP2006285419A JP2005101964A JP2005101964A JP2006285419A JP 2006285419 A JP2006285419 A JP 2006285419A JP 2005101964 A JP2005101964 A JP 2005101964A JP 2005101964 A JP2005101964 A JP 2005101964A JP 2006285419 A JP2006285419 A JP 2006285419A
Authority
JP
Japan
Prior art keywords
item
word
items
distance
target item
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Abandoned
Application number
JP2005101964A
Other languages
English (en)
Inventor
Hiroshi Tateno
啓 舘野
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sony Corp
Original Assignee
Sony Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sony Corp filed Critical Sony Corp
Priority to JP2005101964A priority Critical patent/JP2006285419A/ja
Priority to KR1020077025062A priority patent/KR20070118154A/ko
Priority to PCT/JP2006/306485 priority patent/WO2006106740A1/ja
Priority to US11/909,960 priority patent/US20090132229A1/en
Priority to EP06730433A priority patent/EP1868117A1/en
Priority to CNA2006800182766A priority patent/CN101185073A/zh
Publication of JP2006285419A publication Critical patent/JP2006285419A/ja
Abandoned legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/23—Clustering techniques

Landscapes

  • Engineering & Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Biology (AREA)
  • Evolutionary Computation (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

【課題】 クラスタ数やクラスタの代表が人間の認知モデルに即して決定されるように、クラスタリングするようにする
【解決手段】 プロトタイプ意味論における「典型的な例」と「周辺的な例」（図２Ａ）の考え方を発展させると、２つのアイテム間の認知におけるこのような方向性を、図２Ｂに示すように、「典型的な例」から「周辺的な例」へ向かう距離は、「周辺的な例」から「典型的な例」へ向かう距離よりも長いという非対称な距離尺度で表すことができる。２つのアイテム間に、２つのアイテム間の非対称な数理的な距離を対応付けて、２つアイテムを「典型的な例」と「周辺的な例」との関係で連結させるようにすることで、人間の認知モデルに即してクラスタ数やクラスタの代表が決定されるクラスタリングが実現する。
【選択図】 図２

Description

本発明は、情報処理装置および方法、並びにプログラムに関し、特に、クラスタリングを適切に行うことができるようにする情報処理装置および方法、並びにプログラムに関する。
クラスタリング技術は、機械学習やデータマイニングの分野で非常に重要な役割をもっている。例えば、画像認識、圧縮におけるベクトル量子化や、自然言語処理における単語シソーラスの自動生成などでは、クラスタリングの能力がその精度に直結する。
従来のクラスタリング技術は、大きく分けて階層型、分割最適化型に分類される。
階層型クラスタリングは、アイテム間の距離が定義できる場合に、１つのアイテムからなるクラスタから始まり、クラスタ同士をマージして徐々に大きなクラスタを生成する手法である。
分割最適化型クラスタリング(非特許文献１および２参照)は、距離と絶対位置が定義される空間上に配置されたアイテムが、事前に決めたクラスタ中心にどの程度帰属するかを求め、それに基づいてクラスタ中心を繰り返し計算する手法である。
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)が、式（１）に示すように定義されるスカラー量となるが、「なでらかな確率分布」から「偏った確率分布」への距離の方が、「偏った確率分布」から「なでらかな確率分布」への距離よりも長くなる傾向がある。一般的なアイテムの確率分布は「なでらかなもの」となり、特殊なアイテムの確率分布は「偏ったもの」となる。
Figure 2006285419
例えば、アイテムａ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距離（式（２））などでも良い。
Figure 2006285419
図１に戻り情報処理装置１の構成例を説明する。
なおこの例の場合、単語のクラスタリングを行うものとする。確率変数ｚ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アルゴリズムによって求められる。
Figure 2006285419
Figure 2006285419
図３には、ｋ＝４の場合の単語「温かい」、「優しい」、「ぬくもり」、「ワイルド」、「荒々しい」、「ガッツ」、および「荒削り」の単語モデル（PLSA等を利用した潜在変数の確率分布）の例が示されている。
単語モデルとしては、PLSAやSAMなどの確率モデルの他、文書ベクトルや共起ベクトル、LSA(Latent Semantic Analysis)などで次元圧縮された意味ベクトルなどがあり、いずれを採用するかは任意である。なおPLSAやSAMは、このように潜在的な確率変数の空間で単語が表現されるので、通常の共起ベクトルなどを利用するよりも、意味的な傾向を把握しやすいとされている。
図１に戻りクラスタリング部２５は、上述した原理に基づいて単語のクラスタリングを行い、クラスタリング結果を、クラスタリング結果記憶部２６に記憶する。
処理部２７は、クラスタリング結果記憶部２６に記憶されたクラスタリング結果を利用して所定の処理を実行する（後述）。
次に、本発明におけるクラスタリング処理を説明するが、はじめに、図４のフローチャートを参照してその概略を説明し、その後、具体例に基づいて再度説明する。
ステップＳ１において、クラスタリング部２５は、単語モデル記憶部２４に単語モデルが記憶されている単語の１つに注目し、その単語ｗiの単語モデルを選択する。
ステップＳ２において、クラスタリング部２５は、単語モデル記憶部２４に記憶されている単語モデルを利用して、単語ｗiに対してもっとも近接する（例えば共起しやすいまたは意味的に類似する）単語を、以下の処理で単語ｗiと連結する単語ｗj（対象単語）として選択する。
具体的には、クラスタリング部２５は、例えば、式（５）に示すように、単語ｗiから単語ｗjへの距離（例えば、KL距離）が最も小さい単語、または式（６）に示すように、単語ｗiから単語ｗjへの距離と、単語ｗjから単語ｗiへの距離との合計が最小となる単語を単語ｗjとする。
Figure 2006285419
Figure 2006285419
ステップＳ３において、クラスタリング部２５は、単語ｗ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の選択の条件とすることもできる。
Figure 2006285419
また親子関係を確実なものにするために、例えばアイテムが確率分布で表現される場合、エントロピー(式（８）)を一般性の指標とし、かならずエントロピーの大きいアイテムを親とするなどの制約も加えることができる（図４のステップＳ８およびステップＳ９）。
Figure 2006285419
例えばｐ(ｚ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距離の例を示す図である。 親子関係を示す図である。 他の親子関係を示す図である。 クラスタリング結果を示す図である。 パーソナルコンピュータの構成例を示す図である。
符号の説明
２１ 文書記憶部， ２２ 形態素解析部， ２３ 単語モデル生成部， ２４ 単語モデル記憶部， ２５ クラスタリング部， ２６ クラスタ結果記憶部， ２７ 処理部

Claims (8)

  1. クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択手段と、
    クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択手段と、
    前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出手段と、
    前記算出手段より算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結手段と
    を備えることを特徴とする情報処理装置。
  2. 前記連結手段は、前記算出手段により算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムの一方を親とし、他方を子として、前記注目アイテムと前記対象アイテムを親子関係で連結する
    ことを特徴とする請求項１に記載の情報処理装置。
  3. 前記第２の選択手段は、前記注目アイテムに最も近接する１個のアイテムを前記対象アイテムとして選択する
    ことを特徴とする請求項１に記載の情報処理装置。
  4. 前記第２の選択手段は、前記注目アイテムに近接する所定の数のアイテムを前記対象アイテムとして選択する
    ことを特徴とする請求項１に記載の情報処理装置。
  5. 前記連結手段は、前記注目アイテムが複数の親を有することを認めて、前記注目アイテムと前記対象アイテムを親子関係で連結する
    ことを特徴とする請求項１に記載の情報処理装置。
  6. 前記連結手段により、前記クラスタリングを行うアイテムの全てについての連結が行われた結果得られたクラスタのルートノードをクラスタの代表アイテムとする
    ことを特徴とする請求項１に記載の情報処理装置。
  7. クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、
    クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、
    前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、
    前記算出ステップより算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結ステップと
    を含むことを特徴とする情報処理方法。
  8. クラスタリング処理を行うプロセッサに実行させるプログラムにおいて、
    クラスタリングを行うアイテムを、注目アイテムとして順次選択する第１の選択ステップと、
    クラスタリングを行うアイテムの中から、前記注目アイテムに近接するアイテムを対象アイテムとして選択する第２の選択ステップと、
    前記注目アイテムと前記対象アイテム間の人間の認知における方向性に対応するそれらのアイテム間の距離を算出する算出ステップと、
    前記算出ステップより算出された前記距離に基づいて、前記注目アイテムと前記対象アイテムを連結する連結ステップと
    を含むことを特徴とするプログラム。
JP2005101964A 2005-03-31 2005-03-31 情報処理装置および方法、並びにプログラム Abandoned JP2006285419A (ja)

Priority Applications (6)

Application Number Priority Date Filing Date Title
JP2005101964A JP2006285419A (ja) 2005-03-31 2005-03-31 情報処理装置および方法、並びにプログラム
KR1020077025062A KR20070118154A (ko) 2005-03-31 2006-03-29 정보 처리 장치 및 방법, 및 프로그램 기록 매체
PCT/JP2006/306485 WO2006106740A1 (ja) 2005-03-31 2006-03-29 情報処理装置および方法、並びにプログラム記録媒体
US11/909,960 US20090132229A1 (en) 2005-03-31 2006-03-29 Information processing apparatus and method, and program storage medium
EP06730433A EP1868117A1 (en) 2005-03-31 2006-03-29 Information processing device and method, and program recording medium
CNA2006800182766A CN101185073A (zh) 2005-03-31 2006-03-29 信息处理装置和方法，以及程序存储介质

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2005101964A JP2006285419A (ja) 2005-03-31 2005-03-31 情報処理装置および方法、並びにプログラム

Publications (1)

Publication Number Publication Date
JP2006285419A true JP2006285419A (ja) 2006-10-19

Family

ID=37073303

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2005101964A Abandoned JP2006285419A (ja) 2005-03-31 2005-03-31 情報処理装置および方法、並びにプログラム

Country Status (6)

Country Link
US (1) US20090132229A1 (ja)
EP (1) EP1868117A1 (ja)
JP (1) JP2006285419A (ja)
KR (1) KR20070118154A (ja)
CN (1) CN101185073A (ja)
WO (1) WO2006106740A1 (ja)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5423676B2 (ja) * 2008-07-30 2014-02-19 日本電気株式会社 データ分類システム、データ分類方法、及びデータ分類プログラム
US9342589B2 (en) * 2008-07-30 2016-05-17 Nec Corporation Data classifier system, data classifier method and data classifier program stored on storage medium
JP5936698B2 (ja) * 2012-08-27 2016-06-22 株式会社日立製作所 単語意味関係抽出装置
CN108133407B (zh) * 2017-12-21 2021-12-24 湘南学院 一种基于软集决策规则分析的电子商务推荐技术及系统
CN114819518A (zh) * 2022-03-30 2022-07-29 广西电网有限责任公司南宁供电局 基于特征优化与辅助聚类的用户用电行为分析方法

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6442545B1 (en) * 1999-06-01 2002-08-27 Clearforest Ltd. Term-level text with mining with taxonomies
JP2004005337A (ja) * 2002-03-28 2004-01-08 Nippon Telegr & Teleph Corp <Ntt> 単語関係データベース構築方法および装置、単語関係データベースを用いた単語／文書処理方法および装置、説明表現妥当性検証方法、それらプログラム、それらプログラムを記録した記録媒体、単語の類似度計算方法、単語のグループ化方法、代表語の抽出方法、および単語概念の階層化方法
US7373102B2 (en) * 2003-08-11 2008-05-13 Educational Testing Service Cooccurrence and constructions
US20050154723A1 (en) * 2003-12-29 2005-07-14 Ping Liang Advanced search, file system, and intelligent assistant agent
US20060136245A1 (en) * 2004-12-22 2006-06-22 Mikhail Denissov Methods and systems for applying attention strength, activation scores and co-occurrence statistics in information management

Also Published As

Publication number Publication date
WO2006106740A1 (ja) 2006-10-12
CN101185073A (zh) 2008-05-21
KR20070118154A (ko) 2007-12-13
US20090132229A1 (en) 2009-05-21
EP1868117A1 (en) 2007-12-19

Similar Documents

Publication Publication Date Title
Hua et al. Short text understanding through lexical-semantic analysis
CN108681557B (zh) 基于自扩充表示和相似双向约束的短文本主题发现方法及系统
US9697475B1 (en) Additive context model for entity resolution
US9501569B2 (en) Automatic taxonomy construction from keywords
CN103150382A (zh) 基于开放知识库的短文本语义概念自动化扩展方法及系统
ElRafey et al. Recent advances in scaling‐down sampling methods in machine learning
JP2007241888A (ja) 情報処理装置および方法、並びにプログラム
CN109597995A (zh) 一种基于bm25加权结合词向量的文本表示方法
KR101545050B1 (ko) 정답 유형 자동 분류 방법 및 장치, 이를 이용한 질의 응답 시스템
US20140047091A1 (en) System and method for supervised network clustering
WO2016015267A1 (en) Rank aggregation based on markov model
CN112463914B (zh) 一种用于互联网服务的实体链接方法、装置及存储介质
JP2007219947A (ja) 因果関係知識抽出装置及びプログラム
Godara et al. Support vector machine classifier with principal component analysis and k mean for sarcasm detection
Udupa et al. An exploratory analysis of GSDMM and BERTopic on short text topic modelling
Basha et al. An improved similarity matching based clustering framework for short and sentence level text
WO2006106740A1 (ja) 情報処理装置および方法、並びにプログラム記録媒体
CN117435685A (zh) 文档检索方法、装置、计算机设备、存储介质和产品
US11468078B2 (en) Hierarchical data searching using tensor searching, fuzzy searching, and Bayesian networks
CN112084298B (zh) 基于快速btm的舆情主题处理方法和装置
Maylawati et al. Feature-based approach and sequential pattern mining to enhance quality of Indonesian automatic text summarization
Xin et al. Casie: Canonicalize and informative selection of the openie system
Akhgari et al. Sem-TED: semantic twitter event detection and adapting with news stories
Jeon et al. Random forest algorithm for linked data using a parallel processing environment
CN114625952A (zh) 一种基于VSM和AMMK-means的信息推荐方法及系统

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20070703

A762 Written abandonment of application

Free format text: JAPANESE INTERMEDIATE CODE: A762

Effective date: 20090818