(57)【要約】【課題】意味の近い単語の集合をクラスタとして適切に抽出することを目的とする。【解決手段】各単語ベクトルの各成分値を成分値の和で割ることにより確率ベクトルに変換し、その確率ベクトルのエントロピー、または、エントロピーを正規化した値を確率ベクトルの重みとする。その各確率ベクトルを初期クラスタとし、クラスタＡ，Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値とする。そして、最小の距離をとるクラスタＡ、Ｂを結合する。この処理を繰り返して、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとする。【選択図】図４
2011039977.tif 000002
【特許請求の範囲】
【請求項１】
単語とその意味表現としてのベクトルの対の集合を入力とし、
各単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換し、該確率ベクトルのエントロピー、または、該エントロピーを正規化した値を、該確率ベクトルの重みとする確率ベクトル取得手段と、
各確率ベクトルを初期クラスタとし、クラスタＡ，Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値として、最小の距離をとるクラスタＡ、Ｂを結合し、Ａの重みとＢの重みの和を、結合して得られるクラスタの重みとする操作を繰り返すことにより、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとするクラスタリング手段と、
を備えたことを特徴とする単語クラスタリング装置。
【請求項２】
単語とその意味表現としてのベクトルの対の集合を入力とし、
確率ベクトル取得手段が、各単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換し、該確率ベクトルのエントロピー、または、該エントロピーを正規化した値を、該確率ベクトルの重みとする確率ベクトル取得ステップと、
クラスタリング手段が、各確率ベクトルを初期クラスタとし、クラスタＡ，Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値として、最小の距離をとるクラスタＡ、Ｂを結合し、Ａの重みとＢの重みの和を、結合して得られるクラスタの重みとする操作を繰り返すことにより、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとするクラスタリングステップと、
を有することを特徴とする単語クラスタリング方法。
【請求項３】
請求項２記載の単語クラスタリング方法をコンピュータに実行させるためのプログラム。
【請求項４】
請求項３に記載の単語クラスタリングプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、意味の近い単語の集合をクラスタとして抽出する単語クラスタリング装置及び方法及びプログラム及びプログラムを格納した記録媒体に関する。
【背景技術】
【０００２】
単語の意味表現としてのベクトルを生成する手法として、非特許文献１の手法がある。この手法では、テキストの所定の範囲（典型的には１文）において、任意の単語の対が共起する頻度を算出して単語間共起行列を作成する。該行列の各行ベクトルは、該行に対応する単語が、どのような単語と共起しているか（すなわちどのような単語を隣人として持っているか）を表している。一般に、意味の近い単語は、共通の隣人となる単語を持っており、対応する行ベクトルが近くなる。そこで、単語の概念を、対応する行ベクトルで表す。
【０００３】
非特許文献２の手法では、単語に意味属性が付随した辞書を用いて、テキストの所定の範囲（典型的には１文）において、任意の単語と、該範囲中の単語に対応付けられた任意の意味属性とが共起する頻度を算出して単語・意味属性間共起行列を作成する。該行列の各行ベクトルは、該行に対応する単語が、どのような意味属性と共起しているかを表している。一般に、意味の近い単語は、共通の意味属性と共起し、対応する行ベクトルが近くなる。そこで、単語の概念を、対応する行ベクトルで表す。
【０００４】
また、以下のような手法もある。各単語に、Ｎ個の成分番号の内のいくつかを、単語ごとに異なる成分番号集合が対応付けられるように対応付ける。テキストの所定の範囲（典型的には１文）において、任意の単語と、該範囲中の単語に対応付けられた任意の成分番号とが共起する頻度を算出して単語・成分番号間共起行列を作成する。該行列の各行ベクトルは、該行に対応する単語が、どのような成分番号と共起しているかを表している。一般に、意味の近い単語は、共通の成分番号と共起し、対応する行ベクトルが近くなる。そこで、単語の概念を、対応する行ベクトルで表す。
【０００５】
上記各手法で生成された単語のベクトルは、高頻度の単語程、各成分値が大きく、ベクトルの長さが大きい。このため任意の単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換することを行うことがある。
【０００６】
図１は、各単語の異なりを番号１，２，・・・，Ｍで表し、ベクトルの各成分を成分番号１，２，・・・，Ｎとしたときの、単語とその確率ベクトルの対の集合の例である。単語ｐの確率ベクトルはｖp：＝（ｘp1，ｘp2，・・・，ｘpN）と表される。
【０００７】
単語ｐ，ｑ間の意味的類似性は、対応する確率ベクトルｖp，ｖqの間の距離ｄ（ｖp，ｖq）で表される。ｄ（ｖp，ｖq）として、以下のようなユークリッド距離の自乗をとることがある。
【０００８】
【数１】
2011039977.tif 000003
【０００９】
意味の近い単語の集合をクラスタとして抽出する単語クラスタリングのやり方として、単語を確率ベクトルで表し、単語間の距離を、対応する確率ベクトル間の距離とした上で、確率ベクトル群をクラスタリングするというやり方がある。確率ベクトル群のクラスタリングにより、確率ベクトル群を、いくつかの、その部分集合としてのクラスタへ分割し、クラスタ内の確率ベクトルに対応する単語の集合をクラスタとする。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｈ．Ｓｃｈｕｔｚｅ，Ｄｉｍｅｎｓｉｏｎｓ  ｏｆ  Ｍｅａｎｉｎｇ，Ｐｒｏｃ．ｏｆ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ’９２，ｐｐ．７８６−７９６，１９９２．
【非特許文献２】別所克人，内山俊郎、内山匡，片岡良治，奥雅博，“単語・意味属性間共起に基づくコーパス概念ベースの生成方式，”情報処理学会論文誌，Ｖｏｌ．４９，Ｎｏ．１２，ｐｐ．３９９７−４００６，Ｄｅｃ．２００８．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上記、確率ベクトル間の距離をユークリッド距離の自乗とした上で、確率ベクトル群をクラスタリングする手法は、意味の近い単語をクラスタ化するという目的に対し、以下のような問題がある。
【００１２】
単語のＮ次元確率ベクトルは、図２に示すように、どれか一つの成分のみ１で、残りの成分は０であるようなＮ個のベクトルの張る（Ｎ−１）次元平面上にある。
【００１３】
一般に高頻度語は、どの単語とも高頻度で共起するので、対応するベクトルの各成分の値は似通っている。そのため、高頻度語のベクトルは、各成分の値が１／Ｎで等しいベクトルＶ0：＝（１／Ｎ，…，１／Ｎ）の近くに位置する。図２においては、「野球」や「サッカー」のような高頻度語のベクトルは、Ｖ0の近くに位置する。
【００１４】
一方、低頻度語は、共起する単語が偏っているため、対応するベクトルの各成分の値にばらつきがある。そのため、低頻度語のベクトルは、Ｖ0からは遠くに位置する。図２においては、「野球」と意味的に近い「ピッチャー」や「キャッチャー」のような低頻度語のベクトルは、「サッカー」ベクトルよりは「野球」ベクトルの方が近くなるものの、Ｖ0からは遠くに位置する。同様に、「サッカー」と意味的に近い「キーパー」や「ドリブル」のような低頻度語のベクトルは、「野球」ベクトルよりは「サッカー」ベクトルの方が近くなるものの、Ｖ0からは遠くに位置する。
【００１５】
このため、ベクトル間の距離をユークリッド距離の自乗として、ベクトル群をクラスタリングすると、「野球」と「サッカー」のような意味的に遠い高頻度語が、ともにＶ0の近くに位置するがために、距離が近くなり、それらの単語がクラスタを形成するという問題がある。また、「野球」のような高頻度語と意味的に近い「ピッチャー」や「キャッチャー」のような低頻度語は、Ｖ0からは遠くに位置するがために、当該高頻度語とは距離が遠くなり、当該高頻度語との間でクラスタを形成できないという問題がある。
【００１６】
本発明は、この問題を解決するために考え出されたものであり、意味の近い単語の集合をクラスタとして適切に抽出することを可能とする単語クラスタリング装置及び方法及びプログラム及びプログラムを格納した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の一態様は、単語とその意味表現としてのベクトルの対の集合を入力とし、各単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換し、該確率ベクトルのエントロピー、または、該エントロピーを正規化した値を、該確率ベクトルの重みとする確率ベクトル取得手段と、各確率ベクトルを初期クラスタとし、クラスタＡ，Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値として、最小の距離をとるクラスタＡ、Ｂを結合し、Ａの重みとＢの重みの和を、結合して得られるクラスタの重みとする操作を繰り返すことにより、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとするクラスタリング手段と、を備える。
【００１８】
本発明の他の態様は、単語とその意味表現としてのベクトルの対の集合を入力とし、確率ベクトル取得手段が、各単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換し、該確率ベクトルのエントロピー、または、該エントロピーを正規化した値を、該確率ベクトルの重みとする確率ベクトル取得ステップと、クラスタリング手段が、各確率ベクトルを初期クラスタとし、クラスタＡ，Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値として、最小の距離をとるクラスタＡ、Ｂを結合し、Ａの重みとＢの重みの和を、結合して得られるクラスタの重みとする操作を繰り返すことにより、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとするクラスタリングステップと、を有する。
【００１９】
なお、本発明は、前記各ステップをコンピュータに実行させるためのプログラムとしても構成することができる。このプログラムは、ネットワークを通じた態様で提供してもよく、記録媒体に格納した態様で提供してもよい。
【発明の効果】
【００２０】
本発明では、単語ｐの確率ベクトルｖp：＝（ｘp1，ｘp2，…，ｘpN）の重みをそのエントロピーｅ（ｖp）、または、該エントロピーを正規化した値とする。エントロピーｅ（ｖp）は以下の式で表される。
【００２１】
【数２】
2011039977.tif 000004
【００２２】
０≦ｅ（ｖp）≦ｌｏｇＮであり、ｖ0：＝（１／Ｎ，…，１／Ｎ）のときｅ（ｖp）は最大値ｌｏｇＮをとる。
【００２３】
ｅ（ｖp）を正規化した値とは、ｅ（ｖp）をｌｏｇＮで割ってｅ（ｖp）／ｌｏｇＮとすることにより、0以上１以下の値をとるようにしたものである。
【００２４】
ｖpの重みをｗpと表す。
【００２５】
エントロピーは、確率ベクトルの各成分の値が一様であるほど、値が大きい。したがって、高頻度語の確率ベクトルの重みは大きくなり、低頻度語の確率ベクトルの重みは小さくなる。
【００２６】
本発明では、各単語の確率ベクトルｖpから、ただ一つの要素からなる初期クラスタ｛ｖp｝を生成し、初期クラスタ｛ｖp｝の重みをｗpとする。
【００２７】
クラスタＡを確率ベクトルの集合｛ｖpj｜１≦ｊ≦ｋ｝とする。添数ｐjが異なれば、ｖpjは値が同じであっても、要素としては別物とする。
【００２８】
Ａの重み｜Ａ｜を下記（３）式と定義する。
【００２９】
【数３】
2011039977.tif 000005
【００３０】
Ａの重み付き重心ベクトルＧ（Ａ）を下記（４）式と定義する。
【００３１】
【数４】
2011039977.tif 000006
【００３２】
クラスタＡ，Ｂ間の距離を下記（５）式と定義する。
【００３３】
【数５】
2011039977.tif 000007
【００３４】
本発明では、ｄ（Ａ，Ｂ）が最小となるクラスタＡ，Ｂを結合し、クラスタＣ：＝Ａ∪Ｂを生成する。｜Ｃ｜＝｜Ａ｜＋｜Ｂ｜となる。
【００３５】
ｄ（Ａ，Ｂ）は、ユークリッド距離の自乗に、下記（６）式を係数として乗じている。
【００３６】
【数６】
2011039977.tif 000008
【００３７】
｜Ｂ｜≠０のとき下記（７）式であり、｜Ａ｜を固定したとき｜Ｂ｜が小さい程、この係数は小さくなる。
【００３８】
【数７】
2011039977.tif 000009
【００３９】
したがって、クラスタＡに対し、重みの大きいクラスタとは距離が大きく結合しにくくなり、重みの小さいクラスタとは距離が小さく結合しやすくなる。
【００４０】
本発明では、各初期クラスタの重みを一律にせず、エントロピーに基づき軽重をつけている。図３のように、「野球」のような高頻度語のベクトルに対し、「サッカー」のような高頻度語のベクトルは重みが大きいため結合しにくくなり、「ピッチャー」や「キャッチャー」のような当該高頻度語と意味的に近い低頻度語のベクトルは、重みが小さいため結合しやすくなる。
【００４１】
従来の距離に基づくクラスタリングでは、高頻度語はベクトル空間の中央に集中しがちで、高頻度語同士は意味的には遠くとも距離的に近くにあるがために統合されてしまう欠点があった。また、低頻度語はベクトルの各成分値にばらつきがあるためベクトル空間の中央からは遠くに位置し、高頻度語と低頻度語は意味的に近くとも距離的に遠いために統合されない欠点があった。そこで本願では、エントロピーによる重み付きで距離を求める。ここでは、高頻度語（ベクトル空間の中央にくるもの）のエントロピー（重み）を高めて統合し難くする。逆にいえば、低頻度語（ベクトル空間の中央にこないもの）のエントロピー（重み）を低くして統合し易くする。
【００４２】
このようにして本発明では、エントロピーに基づく重みを考慮することにより、従来手法よりも、意味の近い単語の集合をクラスタとして、より適切に抽出することが可能となる。
【図面の簡単な説明】
【００４３】
【図１】単語とその確率ベクトルの対の集合の例を示す図。
【図２】従来のクラスタリング方法における単語のＮ次元確率ベクトルを示す図。
【図３】本発明のクラスタリング方法における単語のＮ次元確率ベクトルを示す図。
【図４】本発明のクラスタリング装置の構成例を示す図。
【図５】単語とその意味表現としてのベクトルの対の集合の例を示す図。
【図６】クラスタリング手段の処理のフローチャートの一例を示す図。
【発明を実施するための形態】
【００４４】
以下、図面とともに本発明の一実施例を説明する。
【００４５】
図４は、本発明の単語クラスタリング装置１０の構成例である。
【００４６】
確率ベクトル取得手段１１は、単語とその意味表現としてのベクトルの対の集合を入力とし、各単語のベクトルに対し、該ベクトルの各成分値を、該成分値の和で割ることにより、該ベクトルを確率ベクトルに変換し、該確率ベクトルのエントロピー、または、該エントロピーを正規化した値を、該確率ベクトルの重みとする。
【００４７】
図５は、入力となる単語とその意味表現としてのベクトルの対の集合の例であり、各単語の異なりを番号１，２，・・・，Ｍで表し、ベクトルの各成分を成分番号１，２，・・・，Ｎとしている。単語ｐのベクトルはｕp：＝（ｙp1，ｙp2，…，ｙpN）と表される。一般に、ｙpi≧０（１≦ｉ≦Ｎ）である。
【００４８】
ベクトルｕpを、確率ベクトルｖp：＝（ｘp1，ｘp2，…，ｘpN）に変換する。ここで、下記（８）式である。
【００４９】
【数８】
2011039977.tif 000010
【００５０】
ｖpのエントロピーｅ（ｖp）を下記（９）式により算出する。
【００５１】
【数９】
2011039977.tif 000011
【００５２】
０≦ｅ（ｖp）≦ｌｏｇＮであり、ｖ0：＝（１／Ｎ，…，１／Ｎ）のときｅ（ｖp）は最大値ｌｏｇＮをとる。
【００５３】
ｅ（ｖp）を正規化した値とは、ｅ（ｖp）をｌｏｇＮで割ってｅ（ｖp）／ｌｏｇＮとすることにより、０以上１以下の値をとるようにしたものである。
【００５４】
ｖpの重みをｗpと表す。
【００５５】
クラスタリング手段１２は、各確率ベクトルを初期クラスタとし、クラスタＡ、Ｂ間の距離を、Ａの重み付き重心ベクトルとＢの重み付き重心ベクトルの各成分の差の自乗の和に、Ａの重みと、Ｂの重みと、Ａの重みとＢの重みの和の逆数と、を乗じた値として、最小の距離をとるクラスタＡ、Ｂを結合し、Ａの重みとＢの重みの和を、結合して得られるクラスタの重みとする操作を繰り返すことにより、確率ベクトル群のクラスタリングを行い、クラスタリングの結果得られたクラスタ内の確率ベクトルに対応する単語の集合をクラスタとする。
【００５６】
クラスタリング手段１２は、確率ベクトルの集合｛ｖp｜１≦ｐ≦Ｍ｝（添数ｐが異なれば、ｖpは値が同じであっても、要素としては別物とする）を、いくつかの、その部分集合としてのクラスタへ分割する。得られたクラスタ内の各確率ベクトルに対応する単語の集合を、クラスタとして抽出する。
【００５７】
クラスタリング手段１２では、クラスタリングを停止する基準として、クラスタ数Ｈ´か、クラスタ間距離ｄ´をあらかじめ定めておく。停止基準がクラスタ数Ｈ´の場合、クラスタ数ＨがＨ≦Ｈ´となった時点でクラスタリングを停止する。停止基準がクラスタ間距離ｄ´の場合、クラスタ間距離ｄがｄ≧ｄ´となった時点でクラスタリングを停止する。
【００５８】
図６は、クラスタリング手段１２の処理のフローチャートである。
【００５９】
ステップ１２１）
各確率ベクトルｖp（１≦ｐ≦Ｍ）から、ただ一つの要素からなる初期クラスタ｛ｖp｝を生成し、初期クラスタ｛ｖp｝の重みをｗpとする。クラスタ数ＨをＨ＝Ｍとする。
【００６０】
任意のベクトルの対ｖp，ｖq（１≦ｐ＜ｑ≦Ｍ）に対し、ｖp，ｖqの間の距離ｄ（ｖp，ｖq）を、課題を解決するための手段で述べたクラスタＡ，Ｂ間の距離ｄ（Ａ，Ｂ）に基づき算出する。ｄ（ｖp，ｖq）は以下のように算出される。
【００６１】
【数１０】
2011039977.tif 000012
【００６２】
ステップ１２２へ移行する。
【００６３】
ステップ１２２）
クラスタ数ＨがＨ＝１であれば、本フローチャートを終了する。また、停止基準がクラスタ数Ｈ´の場合、Ｈ≦Ｈ´であれば、本フローチャートを終了する。以上の条件を満たさなければ、ステップ１２３へ移行する。
【００６４】
ステップ１２３）
任意の異なるクラスタの対Ａ，Ｂの距離ｄ（Ａ，Ｂ）の最小値ｄminと、ｄminをとるクラスタ対Ａ，Ｂを求める。ステップ１２４へ移行する。
【００６５】
ステップ１２４）
停止基準がクラスタ間距離ｄ´の場合、ｄmin≧ｄ´であれば、本フローチャートを終了する。以上の条件を満たさなければ、ステップ１２５へ移行する。
【００６６】
ステップ１２５）
ｄminをとるクラスタ対Ａ，Ｂを結合し、クラスタＣ：＝Ａ∪Ｂを生成する。ここで添数ｐが異なれば、ｖpは値が同じであっても、要素としては別物とする。｜Ｃ｜＝｜Ａ｜＋｜Ｂ｜とする。クラスタＡ，Ｂをクラスタ集合から除く。クラスタ数Ｈを1だけ減じる。ステップ１２６へ移行する。
【００６７】
ステップ１２６）
クラスタＣと、クラスタ集合内のＣ以外の任意のクラスタＤとの距離ｄ（Ｃ，Ｄ）を算出する。ｄ（Ｃ，Ｄ）は、以下の（１１）式により、クラスタＡ，Ｂ，Ｄの重みと、それらの間の距離から、効率的に算出できる。
【００６８】
【数１１】
2011039977.tif 000013
【００６９】
ステップ１２２へ移行する。
【００７０】
これまで述べた処理をプログラムとして構築し、当該プログラムを通信回線または記録媒体からインストールし、ＣＰＵ等の手段で実施することが可能である。
【００７１】
単語クラスタリング装置１０は、ハードディスク、ＲＡＩＤ装置、ＣＤ−ＲＯＭなどの記録媒体を利用する形態、またはネットワークを介してリモートなデータ資源を利用する形態でもどちらでも構わない。また、単語クラスタリング装置１０は、コンピュータのハードウェア資源（ＣＰＵ，メモリ，ハードディスクドライブ装置，通信インターフェイス等）とソフトウェアとの協同の結果、確率ベクトル取得手段１１，クラスタリング手段１２として機能している。
【００７２】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【００７３】
本発明は、意味の近い単語の集合をクラスタとして抽出する単語クラスタリング技術に適用可能である。
【符号の説明】
【００７４】
１０…単語クラスタリング装置
１１…確率ベクトル取得手段
１２…クラスタリング手段
【図１】
2011039977.tif 000014
【図２】
2011039977.tif 000015
【図３】
2011039977.tif 000016
【図４】
2011039977.tif 000017
【図５】
2011039977.tif 000018
【図６】
2011039977.tif 000019