(57)【特許請求の範囲】
【請求項１】
テキストを意味的なまとまりの単位であるトピックに分割し、該トピック間の境界を決定するトピック境界決定装置であって、
前記テキストを形態素解析して、単語に分割する形態素解析手段と、
単語の意味を表現するベクトルが格納されている記憶手段である概念ベースと、
前記概念ベースを検索することによって、前記形態素解析手段で得られた各単語に対応するベクトルを取得する単語ベクトル取得手段と、
単語ベクトルの系列において、ある単語からまたは文から、それ以降のある単語または文までの範囲の単語ベクトルの系列である区間に対し、該区間内の単語ベクトルの重心ベクトルと各単語ベクトルとの間のユークリッド距離の自乗の和を含むコストを求め、任意の分割数に対し、該分割数の分割を構成する各区間のコストの和の最小値及び該最小値をとる分割を求める最小コスト分割取得手段と、
からなることを特徴とするトピック境界決定装置。
【請求項２】
分割数に対応する各区間のコストの和の最小値Ｅｊは、分割数ｊに対して単調減少という理論の上で、最小値Ｅｊに対する最小値Ｅｊ−１の比を求め、該比が所定の値以上となる最大の分割数ｊを求め、該最大の分割数ｊに対応した分割を最適な分割と認定する最適分割取得手段と、
を更に合わせ持つ
請求項１記載のトピック境界決定装置。
【請求項３】
請求項１または請求項２記載のトピック境界決定装置を構成する各手段としてコンピュータを機能させるトピック境界決定プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、トピック境界決定装置及びプログラムに係り、特に、複数の文もしくは、単語からなるテキストを意味的なまとまりの単位であるトピック区間に分割し、トピック間の境界を決定するトピック境界決定装置及びプログラムに関する。
【０００２】
【従来の技術】
従来技術として、テキストをトピック単位に分割するHearst法がある（例えば、非特許文献１，非特許文献２参照。）。Hearst法では、テキストを単語に分割し、不要語を除去した後、各単語境界の前後に一定の単語数の単語列の窓をとり、各窓毎に窓に含まれる単語の出現頻度ベクトルをとり、前後の窓に対応するベクトル間の余弦測度を当該単語境界の結束度として計算する。結束度が極小となる単語境界あるいはその直近の文境界をトピック境界と認定する。
【０００３】
また、形態素解析処理で得られた各単語に対応するベクトルを取得し、単語の境界の前後にある個数の集合である単語列をとり、各単語列を構成する単語のベクトルの情報から前後の単語列の類似尺度、または、距離尺度である単語列結束度を算出し、単語列結束度が類似尺度である場合、極小である単語境界を、距離尺度である場合、極大である単語境界を、テキストの意味段落の境界とする方法がある（特許文献１参照。）。
【０００４】
【特許文献１】
特開２００２−３４２３２４号公報
【０００５】
【非特許文献１】
Hearst, M.A.: Multi-Paragraph Segmentation of Expository Text, 32nd Annual Meeting of the Association for Computational Linguistics, pp.9-16 (1994).
【０００６】
【非特許文献２】
Hearst, M.A.: TextTiling: Segmenting Text into Multi-paragraph Subtopic Passages, Computational Linguistics, Vol.23, No.1, pp.33-64 (1997).
【０００７】
【発明が解決しようとする課題】
しかしながら、上記従来のHearst法や単語ベクトルに基づく結束度を用いる方法においては、一定の大きさの窓を各単語境界の前後にとるが、トピック区間が窓幅よりも小さい場合、窓に対応するベクトルは、該トピックの意味を適切に表せず、結果として結束度も適切なものではないため、小さいトピック区間の検出が困難であるという問題がある。
【０００８】
また、Hearst法や単語ベクトルに基づく結束度を用いる方法では、テキストの局所的な範囲でトピックの変わり目を判断しているため、大きなトピック区間も細かく分断されていくつかのトピック区間として検出されることがあり、大きなトピック区間の検出が困難であるという問題もある。
【０００９】
本発明は、上記の点に鑑みなされたもので、小さなトピック区間と大きなトピック区間の双方の検出の精度を向上させることが可能なトピック境界決定装置及びプログラムを提供することを目的とする。
【００１０】
【課題を解決するための手段】
図１は、本発明の原理構成図である。
【００１１】
本発明（請求項１）は、テキストを意味的なまとまりの単位であるトピックに分割し、該トピック間の境界を決定するトピック境界決定装置であって、
テキストを形態素解析して、単語に分割する形態素解析手段と、
単語の意味を表現するベクトルが格納されている記憶手段である概念ベースと、
概念ベースを検索することによって、形態素解析手段で得られた各単語に対応するベクトルを取得する単語ベクトル取得手段と、
単語ベクトルの系列において、ある単語からまたは文から、それ以降のある単語または文までの範囲の単語ベクトルの系列である区間に対し、該区間内の単語ベクトルの重心ベクトルと各単語ベクトルとの間のユークリッド距離の自乗の和を含むコストを求め、任意の分割数に対し、該分割数の分割を構成する各区間のコストの和の最小値及び該最小値をとる分割を求める最小コスト分割取得手段と、からなる。
【００１３】
また、本発明（請求項２）は、分割数に対応する各区間のコストの和の最小値Ｅｊは、分割数ｊに対して単調減少という理論の上で、最小値Ｅｊに対する最小値Ｅｊ−１の比を求め、該比が所定の値以上となる最大の分割数ｊを求め、該最大の分割数ｊに対応した分割を最適な分割と認定する最適分割取得手段と、を更に合わせ持つ。
【００１４】
本発明（請求項３）は、請求項１または請求項２記載のトピック境界決定装置を構成する各手段としてコンピュータを機能させるトピック境界決定プログラムである。
【００１５】
上記のように、本発明は、任意の区間列のクラスタ群としての妥当性をもとに最尤の分割を決定することを可能とする。本発明では、任意の区間を考慮しており、テキストの局所的な範囲も大局的な範囲も同時にみて判断を行うことにより、小さなトピック区間と大きなトピック区間の双方の検出の精度が向上する。
【００１６】
【発明の実施の形態】
以下に、図面と共に本発明の実施の形態を説明する。
【００１７】
図２は、本発明の一実施の形態におけるトピック境界決定装置の構成を示す。同図に示すトピック境界決定装置は、形態素解析部１０、単語ベクトル取得部２０、該念ベース３０、最小コスト分割取得部４０、最適分割取得部５０から構成される。
【００１８】
なお、形態素解析部１０、単語ベクトル取得部２０、最小コスト分割取得部４０、最適分割取得部５０は、ＣＰＵ等の制御手段で行い、単語と対応付けられた単語ベクトル、計算されたコストを分割（区間）の組み合わせと対応付けて記憶手段に格納するものとする。
【００１９】
形態素解析部１０は、入力されたテキストを形態素解析して品詞付きの単語に分解する。形態素解析の結果得られた単語の内、付属語等の単語はトピック境界認定に無関係と考えられるので、形態素解析の後、このような不要語を削除してもよい。
【００２０】
単語ベクトル取得部２０は、各単語に対応して意味を示すベクトル値が格納されている概念ベース３０を検索することにより、形態素解析部１０で分解された単語に対する単語ベクトルを取得する。
【００２１】
図３は、本発明の一実施の形態における概念ベース例を示す。同図に示す概念ベース３０は、ハードディスク等の記憶手段に格納され、各単語毎に、ｆ次元のベクトル値が付与されている。概念ベース３０中の単語は、名詞や動詞、形容詞等の自立語である。概念ベース３０における単語ベクトルは、意味的に類似している単語間ほど距離が近く、意味的に類似していない単語間ほど距離が遠くなるように値が設定されている。
【００２２】
概念ベースの例としては、特開平６−１０３３１５の「類似性判別装置」や、特開平７−３０２２６５の「類似性判別用データ精錬方法およびこの方法を実施する装置」で開示されているデータベースがある。
【００２３】
また、Deerwesterの論文(Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., and Harshman, R.: Indexing by Latent Semantic Analysis, Journal of the American Society for Information Science, pp.391-407(1990)) では、単語の文書における頻度を記録した単語・文書間の共起行列を特異値分解により次元数を縮退させた行列に変換しているが、この変換後の行列も概念ベースの一例である。Schutze の論文(Schutze,H.: Dimensions of Meaning, Proc. of Supercomputing '92,pp.786-796 (1992))では、コーパス中の単語間の共起頻度を記録した単語・単語間の共起行列を特異値分析により次元数を縮退させた行列に変換しているが、この変換後の行列も概念ベースの一例である。
【００２４】
最小コスト分割取得部４０は、単語ベクトルの系列において、ある単語または文から、それ以降のある単語または文までの範囲の単語ベクトルの系列である区間に対し、区間内の単語ベクトルの重心ベクトルと各単語ベクトルとの間のユークリッド距離の自乗の和等のコストを求め、任意の分割数に対し、当該分割数の分割を構成する各区間のコストの和の最小値及び当該最小値をとる分割を求める。また、最小値としては、一定の制約条件下における最小値を用いることもある。
【００２５】
最適分割取得部５０は、各分割数に対応する最小コスト値間の比を含む、各分割数に対応する最小コストに関係する値及び分割数が一定の条件を満足する分割を最適な分割と認定する。
【００２６】
次に、上記の構成における動作を説明する。
【００２７】
図４は、本発明の一実施の形態におけるトピック境界決定のフローチャートである。
【００２８】
ステップ１０１）  形態素解析部１０において、入力テキストを形態素解析して単語に分割する。形態素解析の結果得られた単語のうち、付属語等の単語は、トピック境界認定に無関係と考えられるので、形態素解析の後、このような不要語を削除してもよい。
【００２９】
ステップ１０２）  単語ベクトル取得部２０において、単語の意味を表現するベクトルが格納されている概念ベース３０を検索し、形態素解析部１０で得られた各単語に対応するベクトルを取得する。
【００３０】
ステップ１０３）  最小コスト分割取得部４０において、単語ベクトルの系列において、ある単語または文から、それ以降のある単語または文までの範囲の単語ベクトルの系列である区間に対し、区間内の単語ベクトルの重心ベクトルと各単語ベクトルとの間のユークリッド距離の自乗の和等のコストを求め、任意の分割数に対し、該分割数の分割を構成する各区間のコストの和の、または、一定の制約条件下における最小値及び該最小値をとる分割を求める。例えば、入力テキストの単語ベクトルの系列を、
ｗ1 ，ｗ2 ，…，ｗx                     …（数１）
とする。
【００３１】
また、入力テキストの文の系列を、
ｓ1 ，ｓ2 ，…，ｓg                     …（数２）
とする。
【００３２】
トピック境界は常に文境界であると仮定した場合、入力テキストを分割する任意の区間列は、文番号１≦ｈ≦ｇの分割
Ｔ1 ＝（１，２，…，ｎ2 −１），
Ｔ2 ＝（ｎ2 ，ｎ2 ＋１，…，ｎ3 −１），
・
・
Ｔi ＝（ｎi ，ｎi ＋１，…，ｎi+1 −１），
・
・
Ｔj ＝（ｎj ，ｎj ＋１，…，ｇ）                      …（数３）
という形になる。各文ｓh は、単語ベクトルの系列
【００３３】
【数１】
0003925418.tif 000002
から成り立っているものとする。
【００３４】
ここで、トピック境界は文境界とは限らないと仮定したときは、上記の（数２）において各文を単語とみなせばよい。
【００３５】
区間Ｔi ＝（ｎi ，ｎi ＋１，…，ｎi+1 −１）のコストｃ（ｎi ，ｎi+1 −１）を、
【００３６】
【数２】
0003925418.tif 000003
【００３７】
【数３】
0003925418.tif 000004
と定義する。ここで、
【００３８】
【数４】
0003925418.tif 000005
は、区間Ｔi 内の単語ベクトルの重心ベクトルであり、ｃ（ｎi ，ｎi+1 −１）は、当該重心ベクトルと各単語ベクトルとの間のユークリッド距離の自乗和である。
【００３９】
分割Ｔ1 ，Ｔ2 ，…，Ｔj のコストｅ（Ｔ1 ，Ｔ2 ，…，Ｔj ）を、
【００４０】
【数５】
0003925418.tif 000006
と定義する。各区間をクラスタとみたとき、ｅ（Ｔi ，Ｔ2 ，…，Ｔj ）は、いわゆるクラスタ内変動である。
【００４１】
クラスタ内変動とクラスタ間変動の和は常に全変動に等しいという性質がある。ここでこのことについて説明する。
【００４２】
全変動及びクラスタ間変動の算出は、本発明では必ずしも必要ではない。
【００４３】
入力テキストの単語ベクトルの系列（数１）の全変動Ａは、
【００４４】
【数６】
0003925418.tif 000007
【００４５】
【数７】
0003925418.tif 000008
と定義される。
【００４６】
また、区間列（数３）のクラスタ間変動Ｂ（Ｔ1 ，Ｔ2 ，…，Ｔj ）は、
【００４７】
【数８】
0003925418.tif 000009
と定義される。
【００４８】
任意の区間列（数３）に対し、
Ａ＝Ｂ（Ｔ1 ，Ｔ2 ，…，Ｔj ）＋ｅ（Ｔ1 ，Ｔ2 ，…，Ｔj ）
…（数１０）
が成立する。
【００４９】
全変動Ａは一定であるので、クラスタ内変動ｅ（Ｔ1 ，Ｔ2 ，…，Ｔj ）が小さいほど、クラスタ間変動Ｂ（Ｔ1 ，Ｔ2 ，…，Ｔj ）は大きくなり、各区間の間はクラスタとしてよく分離されているといえる。
【００５０】
上記の（数１０）の式から分かることは、ある区間列を更に細分割して得られる区間列のコストは、分割前の区間列のコスト以下となるということである。クラスタ内変動ｅ（Ｔ1 ，Ｔ2 ，…，Ｔj ）は、分割数が一つの場合（ｊ＝１）、最も大きく、各区間が一文の場合（ｊ＝ｇ）、最も小さくなる。従って、クラスタ群として妥当かどうかは、分割数を固定した場合に意味がある。
【００５１】
任意の分割数ｊに対し、分割数ｊの分割のコストの最小値及び当該最小値をとる分割を求める。
【００５２】
文の系列ｓ1 ，ｓ2 ，…，ｓh （１≦ｈ≦ｇ）をｑ個に分割する分割で、最小のコストをとる分割をＰ（ｈ，ｑ）と表すことにする。
【００５３】
Ｐ（ｈ，ｑ）：Ｔ1 ＝（１，２，…，ｎ2 −１），…，
Ｔq-1 ＝（ｎq-1 ，ｎq-1 ＋１，…，ｎq −１），
Ｔq ＝（ｎq ，ｎq ＋１，…，ｈ）              …  （数１１）
としたとき、区間列のコストは、各区間のコストの和なので、
Ｐ（ｎq −１，ｑ−１）：Ｔ1 ＝（１，２，…ｎ2 −１），…，
Ｔq-1 ＝（ｎq-1 ，ｎq-1 ＋１，…ｎq −１）
…（数１２）
となる。
【００５４】
この性質を用いて、任意の分割数ｊに対し、Ｐ（ｇ，ｊ）及びｅ（Ｐ（ｇ，ｊ））を、以下のダイナミック・プログラミングで効率的に求めることができる。
（１）  １≦ｒ≦ｓ≦ｇなる全てのｒ，ｓに対して、区間（ｒ，ｒ＋１，…，ｓ）のコストＣ（ｒ，ｓ）を計算する。
【００５５】
（２）  ｅ（Ｐ（ｈ，２））（２≦ｈ≦ｇ）を、
【００５６】
【数９】
0003925418.tif 000010
として求める。
【００５７】
【数１０】
0003925418.tif 000011
として記憶しておく。
【００５８】
（３）  分割数３≦ｑ≦ｇに対し、ｅ（Ｐ（ｈ，ｑ））（ｑ≦ｈ≦ｇ）を、
【００５９】
【数１１】
0003925418.tif 000012
として求める。
【００６０】
【数１２】
0003925418.tif 000013
として記憶しておく。
【００６１】
（４）  分割数２≦ｊ≦ｇに対し、分割Ｐ（ｇ，ｊ）を求める。
【００６２】
Ｐ（ｈ，２）＝（１，…，ｔh,2 −１），（ｔh,2 ，…，ｈ）（２≦ｈ≦ｇ）
…（数１７）
Ｐ（ｈ，ｑ）＝ｐ（ｔh,q −１，ｑ−１），（ｔh,q ，…，ｈ）
（３≦ｑ≦ｇ，ｑ≦ｈ≦ｇ）
…（数１８）
より求めようとする区間列の一番最後の区間の最初の文番号を取得できることから、分割Ｐ（ｇ，ｊ）の区間列を得ることができる。
【００６３】
ステップ１０４）  最適分割取得部５０において、各分割数に対応する最小コスト値間の比を含む、各分割数に対応する最小コストに関係する値及び分割数が一定の条件を満足する分割を最適な分割と認定する。
【００６４】
分割数ｊの最小コストｅ（Ｐ（ｇ，ｊ））をＥj と表すことにする。上記の（数１０）の式により、ｊが増えるにつれ、Ｅj は、単調減少していく。
【００６５】
最適分割認定の一例として、Ｅj の平均をμ、標準偏差をσとしたときに、閾値α＝μ＋ｚσ（ｚ：例えば、１．５）をとり、
【００６６】
【数１３】
0003925418.tif 000014
となるｊで、最大のｊに対応する分割Ｐ（ｇ，ｊ）を最適分割と認定する。
【００６７】
最小コスト値の間の比
【００６８】
【数１４】
0003925418.tif 000015
は一般に、ｊが増えるにつれ単調減少していく傾向がある。分割がトピック分割とほぼ一致しているとき、それ以上分割数が増えてもコストは殆ど減少することなく変わらず、比の値は１に近くなる。最適分割認定の別の一例として、閾値α（α:例えば１．０００５）をとり、Ｒｊ≧αとなるｊで、最大のｊに対応する分割Ｐ（ｇ，ｊ）を最適分割と認定する。
【００６９】
また、別の一例として、Ｒj の平均をμ、標準偏差をσとしたときに、閾値α＝μ＋ｚσ（ｚ：例えば０．８）をとり、
【００７０】
【数１５】
0003925418.tif 000016
となるｊで、最大のｊに対応する分割Ｐ（ｇ，ｊ）を最適分割と認定する。
【００７１】
以上、一連の各過程の説明を行ったが、上記のステップ１０３において、区間Ｔi ＝（ｎi ，ｎi ＋１，…，ｎi+1 −１）のコストＣ（ｎi ，ｎi+1 −１）として、以下のように区間内の単語ベクトルのメディアン（各座標毎に中央値をとって得られるベクトル）と各単語ベクトルとの間のマンハッタン距離（各座標毎に値の差の絶対値をとり、それを全ての座標にわたって足し合わせた値）の和をとることもできる。
【００７２】
【数１６】
0003925418.tif 000017
【００７３】
【数１７】
0003925418.tif 000018
また、上記のステップ１０３において、任意の分割数に対し、当該分割数で、コストが最小ではないが、一定の制約条件下で最小となる分割及びそのコストを、先に述べたダイナミック・プログラミングよりも短い時間で求めることができる。例えば、以下の（１）、（２）の方法が挙げられる。
【００７４】
（１）  文番号列１≦ｈ≦ｇを２分割するコスト最小の分割を求める。次に、先に２分割した分割位置は固定のまま、文番号列１≦ｈ≦ｇを３分割するコスト最小の分割を求める。以降同様に、これまで得られた分割位置を固定したまま、１回分割してコストが最小となる分割を求めていく。
【００７５】
（２）  文番号列１≦ｈ≦ｇをｇ分割されたｇ個のクラスタとする。隣接する２個のクラスタを結合して１つのクラスタにすることによって、コストが最小となる分割を求める。以降同様に、これまで得られたクラスタは分割することなく、隣接する２個のクラスタを結合して１つのクラスタにすることによって、コストが最小となる分割を求めていく。
【００７６】
なお、上記の形態素解析、単語ベクトル取得、コスト計算、分割取得等の処理をプログラムとして構築し、当該プログラムを通信回線または、記憶媒体からインストールし、ＣＰＵ等の制御手段で実施することが可能である。
【００７７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００７８】
【発明の効果】
上述のように、本発明によれば、任意の区間列のクラスタ群としての妥当性をもとに最尤の分割を決定し、また、任意の区間を考慮しており、テキストの局所的な範囲も大局的な範囲も同時にみて判断を行うことにより、小さなトピック区間と大きなトピック区間の双方の検出の精度が向上する。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の一実施の形態におけるトピック境界決定装置の構成図である。
【図３】本発明の一実施の形態における概念ベースの例である。
【図４】本発明の一実施の形態におけるトピック境界決定のフローチャートである。
【符号の説明】
１０  形態素解析手段、形態素解析部
２０  単語ベクトル取得手段、単語ベクトル取得部
３０  概念ベース
４０  最小コスト分割取得手段、最小コスト分割取得部
５０  最適分割取得手段、最適分割取得部
【図１】
0003925418.tif 000019
【図２】
0003925418.tif 000020
【図３】
0003925418.tif 000021
【図４】
0003925418.tif 000022