多文書間の共通性分析による文書クラスタリング

全文

(1)自然言語処理 154−14 （２００３．３．７）. 多文書間の共通性分析による文書クラスタリング川谷隆彦日本ヒューレット･パッカード㈱. ヒューレット･パッカード研究所. [email protected] 本報告では、多文書間の共通性分析による非階層的な文書クラスタリング法を提案する。文書クラスタリングでは同じトピックを述べた文書がグループ化される。従って、同じクラスターに属する文書群には何らかの共通性があるはずである。また、各トピックにはトピック特有の単語や単語対が存在する。提案手法はこれらの点に着目し、各文書の着目クラスターへの近さを求めるときに、着目クラスターに特有でない単語や単語対の影響を排除しつつ着目クラスターの共通情報を用いるようにする。TDT2 のコーパスを用いた実験により、適切な数のクラスターが求められること、各文書が高い精度でクラスタリングされることを確認した。. Document Clustering via Commonality Analysis of Multiple Documents Takahiko KAWATANI Hewlett-Packard Labs Japan, Hewlett-Packard Japan [email protected] This paper proposes a non-hierarchical clustering method through multi-document commonality analysis. In document clustering, documents with the same topic are grouped so that document in a cluster should have some commonalities. Furthermore, each topic has its own specific terms or term pairs. Based on these points, the proposed method obtains closeness of a given document to a cluster by matching the given document with common information among the documents in the cluster avoiding impacts from non-specific term and term-pairs of the cluster. Through experiments using TDT2 as corpus, it was confirmed that a proper number of clusters were obtained and that clustering accuracy is significantly high. 1. まえがき文書クラスタリングはテキスト処理における重要な技術のひとつであり、情報検索、文書要約、 TDT(Topic Detection and Tracking)などに応用されている。クラスタリング技術そのものについてはこれまでに様々な方法が提案されている[1][2]。クラスタリングは、各文書が各クラスターに帰属する確率を求めるソフトタイプ、各クラスターに帰属するか否かを求めるハードタイプに大別されるが、本報告では後者について議論する。後者は、さらに、階層的な手法と非階層的な手法とに分類される。前者には大きなクラスターの分割が繰り返されるトップダウンと、小さなクラスターのマージが繰り返されるボトムアップのアプローチが. ある。これらでは、クラスター間の類似度を図る方法として単一リンク法、完全リンク法、グループ平均法が知られている。非階層的な手法としては、K-means 法、Gaussian Mixture Model (GMM) 法などある。また、TDT におけるトピック検出では時系列的に入力されるニュースストーリーから新しいトピックを述べたものを種として検出し、それ以後入力されるニュースストーリーから種に近いものを検出してグループ化するというクラスタリングが行われている[3]。ところで、文書クラスタリングは各文書が記述するトピックによって文書をグループ化するものであるから、ひとつのクラスターに属する文書（クラスター文書集合と呼ぶ）は同じトピックについ. 1 −93−.

(2) て述べている筈である。従って、クラスター文書集合は何らかの共通性を有する筈である。また、各トピックにはトピック特有の単語や単語対が存在する筈であり、各クラスターには単語や単語対の出現傾向に違いが存在する筈である。このようなことから、クラスタリングの過程で、 • 着目クラスター文書集合の共通情報を抽出し、この共通情報との近さにより各文書の着目クラスターに対する近さを表す。 • 上記においては、着目クラスターに特有でない単語や単語対の影響を排除する。ような処理を行うことにより性能の向上が期待できる。また、各クラスター文書集合の共通情報の抽出結果はクラスター処理の結果を用いる際に有用な情報となるものと考えられる。本報告で目指すクラスタリングはこのようなものである。翻って従来のクラスタリング法を見てみると、階層的なクラスタリング処理では、多くの場合 2 文書間の余弦類似度を基にクラスター間の類似度を求め、マージや分割を決定しているため、クラスターの共通情報を算出する余地はなかった。また、非階層的な手法において代表的な k-means 法では、クラスターの中心ベクトルと着目文書ベクトルとのマハラノビス距離が用いられ、やはりクラスターの共通情報が用いられることはなかった。また、これらの手法では各クラスターに特有でない単語や単語対の影響を排除しないまま余弦類似度やマハラノビス距離が求められていたため、クラスターに本質的でない単語や単語対の存在がクラスタリング結果に影響を及ぼし得た。Liu らは、非階層的な手法によるクラスタリング処理を行ったのち各クラスターに特有な単語を求め、特有単語の投票によりクラスタリングの結果をリファインするという処理を行って、精度を向上させることに成功している[4]。この方法は、各クラスターに特有でない単語の影響の排除という点で提案手法と共通しているが、提案手法ではクラスタリングの過程でこの処理を行う点が異なっている。このようなクラスタリング法の実現に際し、大きな問題が２つ存在する。ひとつは文書集合の共通性分析の方法であるが、これについては前報[5]で述べた方法を踏襲したうえで、文書数が多いときに発生する問題に対して対策を講ずる。二つ目はクラスタリングにどのようなアプローチを採用するかの問題である。階層的な処理では、クラスターのマージや分割が頻繁に繰り返される。また、非階層的な処理では、クラスターのメンバーがや. はり頻繁に入れ替わる。このような状況では各クラスターの共通情報、クラスターに非特有な単語や単語対の検出には無理がある。そこで、先ずクラスターの種となる文書をひとつ取り出し、ついでその種と同じトピックを記述する文書を検出して種を成長させるというアプローチを取ることとする。これは種を成長させるという点で TDT におけるトピック検出と共通性があるが、ここではトピック検出が目的でないので文書入力の時系列性は考慮しない。以下、2.では、前報で提案した多文書間の共通性分析法の概要を紹介する。3.では文書数が非常に多い場合にも対応できるよう上記共通性分析法の改善を図る。4.では、各クラスターに特有でない単語や単語対の検出法も含め、新しいクラスタリング法の提案を行う。5.では、コーパスとして TDT2 を用いたときの実験結果を報告する。 2. 共通性分析法の概要 2.1 目的とアプローチ共通性分析の目的は次の 2 点にある。 A) 与えられた文書集合における各文書の話題がどの程度共通しているか数値で示す。 B) 文書集合の共通の話題への近さに応じて各文書、または各文にスコア−を与える。また、アプローチは以下のとおりである。いま、 R 個の文書から成る文書集合 D を考え、各文書から一つづつ文を取り出して R 個の文からなる文の組を作ったとする。このような文の組は各文書の文の数の積通り存在することになる。本報告では、着目する文の組において、R 個の文のうちの A 個の文に現れる単語を共通単語と呼ぶこととする。厳密に云えば全ての文に現れる文を共通単語と呼ぶべきであるが、R が大きい時にはたとえ文書集合Dが同じ話題を述べていたにしても共通単語は現れないこともありうるのでこのような定義を採用する。このような共通単語を各組で求め、その和もしくは 2 乗和を求めたとすると、その値は各文書が共通に有する情報量に応じていると考えられる。そこでこれらの値を、文書数や各文書のサイズで正規化して、各文書の話題がどの程度共通しているかの尺度とする。この尺度を文書集合共通度と呼ぶこととする。また、ある文の組における共通単語で構成された文を共通文と呼ぶこととする。ここで、全ての文の組で共通文を作り、共通文の集合を構成したとする。このような共通文の集合は文書集合の共通の話題の内容を示すものと考えられる。従って、. 2 −94−.

(3) 各文書、もしくは文と共通文集合との間で何らかの手段で類似度を求めることができれば、それは各文書、または各文の共通話題への近さを表わすものと考えられる。これらが本報告の基本的な考え方である。 2.2 文書、及び共通文集合の共起行列現れる単語集合が{w1,…,wM}で与えられる文書集合 D を考える。D は R 個の文書から成るものとし、r 番目の文書を Dr とする。さらに、Dr は Yr 個の文からなるものとし、y 番目の文及びその文ベクトルを Dry、 dry=(dry1,.., dryM)T で表す。ここで、 T は転置を表す。dry はバイナリベクトルであり、 drym は m 番目の単語の有無を表す。次に、次式で定義される行列 S r を考える。 S r = ∑Yyr=1 d ry d ry T. (1). 式 (1) から分かるように、 Sr の mn 成分は S r mn = ∑Yyr=1 d rym d ryn により与えられる。従って、. S rmm は文書 Dr において単語 m が生起する文の数、 S rmn は単語 m と n とが共起する文の数を表すことになる。そこで、行列 S r を文書 Dr の生起・共起行列、または簡単に共起行列と呼ぶこととする。共起行列には次のような性質がある。ここでは同じ単語は同じ文で 2 回以上現れないものとする。 (1) S r の対角成分の和は文書 Dr に現れる単語の総数に等しく、従って、各文に現れる単語数の和とも等しくなる。 (2) S r の全成分の和は文書 Dr の各文に現れる単語の数の 2 乗和に等しい。これは、文書 Dr の文 y における単語数を fry とすると、下記により示される。 2 2 ∑Yyr=1 f ry = ∑Yyr=1 (d ry1 + ⋅ ⋅ + d ryM ) M M = ∑Yyr=1 ∑ m =1 ∑ n =1 d rym d ryn. (2). r M M = ∑m =1 ∑ n =1 S mn. 次に、共通文集合の共起行列を求める。簡単な例として 3 文書 D1、D2、D３で A=3 とした場合を考えてみる。D1、D2、D３のそれぞれの i、j、k 番目のベクトル d1i、d2j、d3k の共通文ベクトルを cijk =(cijkm)で表すと、cijkm は (3) cijkm= d1imd2jmd3km により表わすことができる。共起行列を SC とすると、その mn 成分は. S C mn = ∑Yi=1 1 ∑Yj2=1 ∑Yk3=1 c ijk m c ijk n = ∑Yi=1 1 ∑Yj2=1 ∑Yk3=1 d1im d1in d 2 jm d 2 jn d 3km d 3kn (4) = S 1mn S 2 mn S 3 mn. となり、文書 D1、D2、D３の共起行列の対応する成分同士の積として求められる。これは文書の数とは無関係に成り立ち、文書数が R の場合は S C mn = ∏ rR=1 S r mn. (5). で与えられる。結局、共通文ベクトル集合の共起行列は共通文ベクトルを実際に求めることなく得ることができる。また、R個の文のうちのA個の文に現れる単語を共通単語とする場合の共起行列TAは次のように求められる行列T、Uを用いて定義する。式(5)では各文書の共起行列の同じ成分の積が求められたが、行列Tの各成分は同じ成分の値がゼロでない成分の間で積を求めるようにする。つまり、S rmnが0 の場合はその値を一時的に1としたうえで式(5)が用いられる。但し、全てのSrmnが0の場合はT A mn は0とする。従って、各単語、単語共起が文書集合 Dに必ず現れる限り、行列Tの対応する成分は0以外の値をとる。また、Uは各単語、単語共起の文書頻度を格納した行列である。即ち、Umm、Umn はそれぞれ単語mの出現する文書数、単語m、nの共起する文書数となる。行列TAはAを閾値として以下のように決定される。 T A mn= T mn, if U mn ≥ A, otherwise. (6) T A mn= 0 これにより A 文書以上で生起した単語、共起した単語対が選択されたことになり、TA はそれらに対応する成分のみが値を有し得る。TA mm は単語 m の出現する共通文の数、TA mn は単語 m、n の共起する共通文の数となる。 2.3 文書集合共通度行列 TA も共起行列である以上、文書の共起行列と同じ性格を持つ。従って、行列 TA の対角成分の総和は全共通文の共通単語数の総和と等しくなり、行列 TA の全成分の総和は各共通文の共通単語数の全共通文に対する 2 乗和となる。従って、これらの値は各文書が共通に有する情報量（共通情報量）となるので、2.1 で述べたように文書数や各文書のサイズで正規化して文書集合共通度を定義する。共通単語数の総和をベースとする場合を線形モデル、共通単語数の 2 乗和をベースとする場合を 2 次モデルと呼び、文書集合共通度をそれぞれ. 3 −95−.

(4) coml(D;T A)、comq(D;T A)と表すと、これらは  M TA ∑m mm =1 coml ( D; T A ) =  R R M r R  ∏ r =1 ∑ m =1 ( S mm ).    . 対象とする文書を P として、P が文書集合 D の共通の話題にどれだけ近いかを示す尺度として、文書共通度を定義する。文書共通度は着目文書と共通文集合との類似度として式(9)(10)をもとに以下のように定義することができる。但し、SP は文書 P の共起行列である。. 1 /( R −1).  A M M ∑m =1 ∑ n =1 T mn comq ( D; T ) =  R R M r R M  ∏ r =1 ∑ m =1 ∑ n =1 ( S mn ) A. (7)    . 1 /( R −1). (8). のように定義することができる。正規化のポイントは、全文書が同一で A=R の場合の共通度は 1 になるようにしたこと、及び、R 文書のときは R-1 回の文書の突合わせが行われるので R-1 乗根を求めるようにしたことにある。次に、文書数が 2(R=2)の場合を考えると、2 文書の文書集合共通度は文書間の類似度と見なすことができる。式(7)、(8)で A= R=2 とすると、これらは coml ( D; T R ) =. comq ( D; T R ) =. M S ∑m =1 M S ∑m =1. 1 2 mm S mm. 1 mm. M S ∑m =1. (9) 2. M M ∑m =1 ∑ n =1 S 1 2 M M ∑m =1 ∑ n =1 ( S mn ). mm. 1 2 mn S mn. (10). 2 2 M M ∑m =1 ∑ n =1 ( S mn ). と書くことができる。 2.1 で述べたように、各文書の共起行列の対角成分は対応する単語を含む文の数を表す。従って、同じ単語が同じ文に 2 回以上現れないと仮定すると、式(9)で与えられる 2 文書の線形モデルでの文書集合共通度は文書内の単語頻度を成分とする文書ベクトルの余弦類似度と全く同じとなる。また、式(10)は 2 文書間の類似度はそれぞれの文書の共起行列の対応する成分同士の積和をもとに与えられることを示している。この場合、2 つの文書の類似度が高いためには、2 つの文書の間で単語の出現傾向だけではなく、単語共起の傾向まで似ている必要がある。2 つの文 D1i, D2j, の共通単語数は d1iTd2j と表すことが出来るので、共通単語数の 2 乗和は ∑Yi=1 1 ∑Yj2=1 (d1iT d 2 j )2 によっても表される。従って、式(10)は comq ( D; T R ) =. coml ( D, P; T A ) =. comq ( D, P; T A ) =. M T ∑m =1. A. A. 2. M (T ∑m =1. mm ). P mm S mm M (S ∑m =1. M M ∑m =1 ∑ n =1 T M M ∑m =1 ∑ n =1 (T. A. mn ). 2. A. (12) P. mn ). 2. P mn S mn. M M ∑m =1 ∑ n =1 ( S. P. mn ). 2. (13) 3. 文書集合共通度、文書共通度の改善前報でも述べているが、文書数が多く、特定の単語が各文書で非常に高い頻度で現れる場合にはその単語のみで文書集合共通度、文書共通度がほぼ決まってしまうという問題が発生する。例えば、 10 文書の場合、単語 1 の頻度が最も高く各文書で 3 つの文に、単語 2 が 2 番目に頻度が高く 2 つの文に現れたとする。行列 T の単語 1 に対応する対角成分は 310＝19683、単語 2 に対応する対角成分は 210＝1024 となり、単語 1 の文書集合共通度、文書共通度に対する寄与が圧倒的に大きくなってしまう。このような状況を阻止するためには、高頻度単語の情報共通量への寄与を抑えるようにすればよい。そこで、行列 QA を if TAmn>1 QAmn= log(TAmn) =0 otherwise (14) により定義し、情報共通量への寄与を QAmn で与えることとする。その結果、式(7)、(8)に対応する文書集合共通度は、全文書が同一で A=R の場合は 1 になるようにすることにより、  M QA ∑m mm =1 coml ( D; Q A ) =  R R M r R  ∏ r =1 ∑ m =1 log(S mm ).    . (15).  A M M ∑m =1 ∑ n =1 Q mn comq ( D; Q A ) =  R R M r R M  ∏ r =1 ∑ m =1 ∑ n =1 log(S mn ).    . (16). で定義される。また、式(11)、(12)に対応する文書共通度は. T 2 ∑Yi=1 1 ∑Yj2=1 (d1i d 2 j ) T T 2 2 ∑Yi=1 1 ∑Yj1=1 (d1i d1 j ) ∑Yi=21 ∑Yj2=1 (d 2i d 2 j ). A. (11) と表すこともできる。式(11)から対象となる文書間の全ての文ベクトルの組み合わせから求められる内積の 2 乗和をベースにしていることが分かる。 2.5 文書共通度. coml ( D, P; Q A ) =. P. M Q ∑m mm S mm =1 A. M (Q ∑m mm ) =1. 2. A. comq ( D, P; Q A ) =. 4 −96−. (17) P. M (S ∑m mn ) =1. 2. P. M M ∑m =1 ∑ n =1 Q mn S mn A. M M ∑m =1 ∑ n =1 (Q mn ). 2. P. M M ∑m =1 ∑ n =1 ( S mn ). 2.

(5) (18) により与えられる。 4. クラスタリングの方法本章では、 (a)各文書は必ずどれかひとつのクラスターに属する。 (b)入力文書集合は複数のトピックを含んでおり、各トピックには、出現頻度が着目トピックでは高く他のトピックでは非常に低い単語、単語対（トピック特有単語、単語対と呼ぶ）が存在する。ことを前提にクラスタリング法を提案する。 4.1 手順の概略処理の流れの概略は以下の通りである。ステップ１：クラスターの種の候補となる文書を検出する。ステップ 2：先ず、クラスターの種の候補文書と全文書との類似度（式(9)もしくは式(10)）を求め、一定値以上の類似度を有する文書を抽出する。その文書数が最も大きくなる文書をクラスターの種とし、その文書集合によりクラスターを形成する。ステップ 3：その時点でのクラスター文書集合と全文書との間で文書共通度を求め、一定値以上の文書共通度を有する文書をそのクラスターに仮に帰属させることによりクラスターを成長させる。クラスターに仮に属する文書数が一定になればステップ 4 へ。そうでなければ本ステップを繰返す。ステップ 4：終了条件（後述）を満たせばステップ5へ。そうでなければステップ1に戻って続行。ステップ 5：各文書について各クラスターへの文書共通度を求め、文書共通度の最も高くなるクラスターに帰属させる。ステップ 6：1 つのトピックに 2 つ以上のクラスターが対応していないかどうかを検出。そのようなクラスターがあれば冗長なクラスターとして削除し、各文書の帰属するクラスターを求めなおす。 4.2 手法の詳細 4.2.1 クラスターの種となる文書の検出クラスターの種となる文書はどのトピックの文書が選ばれようと、そのトピックの中では中心的な文書であることが望ましい。最初の検出では入力文書集合を用いて、2 回目以降の繰り返しの時には仮決定結果でどのクラスターにも属さない文書の集合を用いて、行列 T、U を求める。次に、A を適当に決め、行列 T、U を求めた文書集合中の文書 P に対して、入力文書集合との共通情報量を A r M M coms ( D, P) = ∑ m =1 ∑ n =1 Q mn S mn. (19). 5 −97−. により求める。式(19)を最大にする文書は入力文書集合全体の中心に近いはずであるが、もし、異なるトピックには異なる単語が出現するのであれば、その文書と同じトピックの文書集合の中でも中心付近に位置するはずである。しかしながら、複数のトピックに共通に現れる単語、単語対も存在するので、選択される文書は文書集合全体の中心の方向にずれる。しかし、単語に比べ単語対は複数のトピックに共通に出現する頻度は少ないと考えられるので、式(19)において行列 QA の非対角成分のみを用いれば、トピックの中心からのずれの少ない文書が選択されると考えられる。さらにこの処理を確実にするため、式（19）の共通情報量の大きい複数個（例えば 5 個）選択し、クラスターの種の候補とする。 4.2.2 クラスターとの文書共通度の算出クラスター文書集合と全文書との間での文書共通度は式(17)もしくは(18)を用いて求められる。種の文書がトピック i を述べている着目クラスターの成長の過程で、クラスター文書集合にはトピック i について述べた文書ばかりではなく、その他のトピックについて述べた文書も混入していると考えられる。従って、その文書集合には (a)トピック i に特有な単語、単語対 (b)i 以外のトピックに特有な単語、単語対 (c)トピック i に特有でない単語、単語対、即ち複数のトピックに共通に出現する単語、単語対が現れうる。従って、トピック i について述べた文書を精度高く選択するためには、文書共通度の算出において(b)(c)に属する単語や単語対の影響を排除することが重要となる。このうち(b)については、式(17)もしくは(18)において A の値を適切に選択することにより影響を排除することが可能となる。また、(c)のトピック i に特有でない単語、単語対についても後述の方法で検出して式(17)もしくは(18)に用いないようにする。単語 m、及び単語対 m、 n がトピック i に特有でないと判断された場合には、式(17)もしくは(18)において QAmm=0.0、 QAmn=0.0 とした。 4.2.3 終了条件ステップ 4 における終了条件は次の通りである。ひとつのクラスターの成長処理が終了した時点で、それまでに求められた全クラスターとの文書共通度を全文書について求め、全クラスターと文書共通度がゼロとなる文書数を求める。もしそのような文書数がゼロになればステップ 5 の処理に移行する。また、そのような文書数がゼロに近い値に.

(6) なった時には（例えば 4 以下）、ステップ 1 からの処理を一巡繰り返す。その処理の終了後、最後のクラスターも含め全クラスターとの文書共通度を全文書について求め、最後のクラスターに対してのみ文書共通度が一定値より大きく、他の全クラスターに対して文書集合度が一定値より小さくなる文書数を求める。もしそのような文書数が一定値より少なければ（例えば 2）、最後のクラスターの存在意義はないことになるのでこれを除去したうえでステップ 5 の処理に移行する。多ければこのクラスターは残したうえで改めて終了条件を満たすか否かを検証する。 4.2.4 冗長なクラスターの検出ステップ 1 における 2 つ目以上のクラスターの種の検出において、それまでに求められているクラスターの種の文書と異なるトピックを述べている文書が常に選択される保証はない。同じトピックに対して複数の種文書が検出されれば冗長なクラスターが生ずることになる。冗長クラスターの検出のためには、先ず、各クラスターに対し、着目クラスターに対してのみ文書共通度が一定値よりも大きくなる文書数をクラスター重要度として求める。クラスター重要度が一定値よりも小さいクラスターがひとつ存在する場合は、そのクラスターに存在する文書の数がいくら多くとも冗長なクラスターとみなし、除去する。そのようなクラスターが複数存在すれば、クラスター重要度が最も小さいクラスターを先ず除去する。このような処理を冗長なクラスターが存在しなくなるまで繰り返す。 4.3 トピックに特有でない単語、単語対の検出法種文書がトピック i の着目クラスターの成長の過程を考える。U、Ui、U0 を入力文書集合全体、入力文書集合におけるトピック i の文書、その時点での着目クラスター文書集合から求められた文書頻度行列とする。また、トピック i を述べている文書数は、文書集合全体には c0 個、着目クラスター文書集合には c 個存在したとする。その時点での着目クラスター文書集合ではトピック i の文書が大多数を占めると仮定すると、単語 m、及び単語 m、n の対がトピック i の特有単語、単語対の時には、U 0 mm. ≈ U i mm. 、U 0 mn. ≈ U i mn. なので U 0 mm U mm > U i mm U mm ≈ c0 c U 0 mn U mn > U i mn U mn ≈ c0 c. となる筈である。従って、c0 /c を適当な方法で求めることができれば単語 m、及び単語 m、n の対がトピック i に特有が否かを判断することができる。本報告では、クラスター文書集合における最も頻度の高い単語 30 個のうち、U0mm/ U mm の値の小さな 10 個はトピック i の特有単語とみなし、これらの単語の U0mm/ U mm の平均 C を c0 /c の推測値とした。結局、αをパラメータとして U 0 mm U mm > αC U 0 mn U mn > αC. を満たす単語 m、及び単語対 m、n をトピック i には特有な単語ではないと判断するようにした。 αは後述の実験においては 1.2 に設定された。 5. 実験 5.1 実験データ用いたコーパスは TDT2 である。TDT2 は 1998 年の 1 月から 6 月の間の 100 個のイベントに関するニュースストーリーの集合であり、6 個のニュースソースから採取されている。本報告では同じく TDT2 を用いて行われた Liu らの非階層型のクラスタリング[4]の結果と比較するため、Liu らが行ったように ABC、CNN、VOA から採取された表1 実験データの概要 Event. なので、. No. of Documents. ID. Event Subject. 01. Asian Economic Crisis. 27. 90. 289. 406. 02. Monica Lewinsky Case. 102 497. 96. 695. 13. 1998 Winter Olympic. 21. 81. 108. 210. 15. Current Conflict with Iraq. 77. 438 345. 860. 18. Bombing AL Clinic. 9. 73. 5. 87. 23. Violence in Algeria. 1. 1. 60. 62. 32. Sgt. Gene McKinney. 6. 91. 3. 100. 39. India Parliamentary Election. 1. 1. 29. 31. 44. National Tobacco Settlement. 26. 163. 17. 206. 48. Jonesboro shooting. 13. 73. 15. 101 251. ABC CNN VOA Total. 70. India, A Nuclear Power?. 24. 98. 129. U 0 mm U mm ≈ U i mm U mm ≈ c 0 c. 71. Israeli-Palestinian Talks. 5. 62. 48. 115. U mn U mn ≈ U mn U mn ≈ c 0 c. 76. Anti-Suharto Violence. 13. 55. 114. 182. 77. Unabomer. 9. 66. 6. 81. 86. GM Strike. 14. 83. 24. 121. 0. i. となり、非特有の時にはU 0 mm. > U i mm. 、U 0 mn. > U i mn. 6 −98−.

(7) 15 イベントに関するニュースストーリーの集合を実験対象とした。表 1 にそれらの詳細を示す。 5.2 実験条件前処理としては、文切り出しの後、品詞付け、 lemmatizing を行い、ストップワード除去を行った。クラスタリング処理には固有名詞を含む名詞、動詞、形容詞に品詞付けされた単語を用いた。クラスタリング処理においては、対象となる入力文書集合の各単語の文書頻度を求め、出現頻度が文書数の 1%以下の単語は棄却した。さらに、全文書のステップ 2 における各クラスターの種との類似度の算出、ステップ 3、5 におけるクラスター文書集合との文書共通度の算出においては線形モデルと 2 次モデルの両方を用い、結果を比較することとした。クラスターの種文書の共起行列や行列 QA の非対角成分の値は対角成分のそれに比べ通常は小さい。従って 2 次モデルを用いたにしても対角成分が支配的になり非対角成分が有効に働かないことが起こり得る。そこで、2 次モデルで類似度を算出するときは非対角成分の値を一定倍（例えば 5 倍）して用いた。また、クラスタリングの結果は精度で比較された。ステップ 6 の結果を用いて、ある文書のイベントラベルとその文書が帰属するクラスターの種となった文書のイベントラベルとが一致するときクラスタリングの結果は正しいとされる。また、全てのクラスターに対して文書共通度が 0 の文書は誤りとする。精度は正しくクラスタリングされた文書数の全文書数に対する比により求める。 5.3 実験結果表 2 に実験に用いられた 14 種類の文書グループとそれに対する提案手法の結果、Liu らの結果を示す。Liu らの方法は、混合ガウス分布モデル（Gaussian Mixture Model）に基づき非階層形のクラスタリングを行った後、各クラスターの特有単語を求め、特有単語の voting によって結果を修正している。表 2 で示される voting 前の結果は非階層形クラスタリングの典型的な結果を示しているものと考えられるが、voting によって著しく精度が改善されていることが分かる。また、提案手法に対しては、ステップ3では2次モデルを採用し、ステップ 5 で線形モデル（”linear”）と 2 次モデル（”quadratic”）を採用したときの結果を示している。この時、A の値はクラスター文書集合中の全文書数の 10%としている。また、他のパラメータについても値を変えながら実験を行って適切な値を決めている。ステップ 3 における平均繰り返し. 7 −99−. 表2 実験結果 Liu's method. Proposed method. Test Data. before voting. after voting. linear. quadratic. 1 ABC-01-02-15. 0.9011. 1.0000. 0.9806. 0.9806. 2 ABC-02-15-44. 0.9659. 0.9902. 0.9805. 0.9951. 3 ABC-01-13-44-70. 0.7449. 1.0000. 1.0000. 1.0000. 4 ABC-01-44-48-70. 0.8000. 1.0000. 1.0000. 1.0000. 5 CNN-01-02-15. 0.9795. 0.9756. 0.9932. 0.9844. 6 CNN-02-15-44. 0.9927. 0.9964. 0.9964. 0.9863. 7 VOA-01-02-15. 0.8438. 0.9896. 0.9986. 1.0000. 8 VOA-01-13-76. 0.9479. 0.9583. 0.8943. 0.9043. 9 VOA-01-23-70-76. 0.9297. 0.9453. 0.9206. 0.9155. 10 VOA-12-39-48-71 0.8061 VOA-44-48-70-7111 76-77-86 0.7734. 0.9898. 1.0000. 1.0000. #. 0.8527. 1.0000. 0.9972. ABC+CNN-01-1312 18-32-48-70-7177-86 0.9633. 0.9704. 0.9917. 0.9905. CNN+VOA-01-1313 48-70-71-76-77-86 0.9431. 0.9262. 0.9500. 0.9545. ABC+CNN+VOA14 44-48-70-71-7677-86 0.8768. 0.9938. 1.0000. 0.9991. 数はクラスター当り 5.1 回であった。表から、精度の高い文書グループの数は、Liu らの方法よりも提案手法の方が多く、提案手法が優ることが分かる。また、ステップ 3 において線形モデルを採用した実験においても表 2 とほぼ同等の結果が得られている。しかし、2 次モデルでは冗長クラスターは発生しなかったのに対し、線形モデルの場合には、冗長クラスターが 2、 3 の文書グループで生じており、2 次モデルの方が安定な処理が期待できる。 6. 考察 (i)表 2 においてグループ 8、9、13 の精度が他に比べて著しく低くなっている。結果の観察によると、誤ったニュースストーリーの殆どは、イベント "01"（アジア経済危機）の内のインドネシアの経済危機について述べたニュースストーリーがイベント"76"（反スハルト暴動）のニュースストーリーを含むクラスター（"76"の関連クラスターと呼ぶ）に帰属するとされたものである。インドネシア反スハルト暴動はインドネシアの経済危機が引き金となって起きたイベントであり、ニュースストーリーの内容もインドネシアの経済危機に関するニュースストーリーと非常に似通っている。そのため、イベント"76"の関連クラスターにおいて、イベント"01"に特有な単語や単語対とイベント.

(8) "76"のそれらとを区別し、イベント"01"と共通する単語や単語対の影響を排除することが難しくなり、イベント"01"のインドネシア関連のニュースストーリーはイベント"01"だけでなく、イベント "76"のクラスター文書集合とも大きな文書共通度を取ってしまう。しかも、イベント"01"のニュースストーリー集合においてインドネシア関連は全体の中の一部に過ぎないが、イベント"76"はインドネシアに関連するニュースストーリーが主である。そのため、イベント"01"のインドネシア関連のニュースストーリーはイベント"01"関連のクラスターよりもイベント"76"関連のクラスターに対して大きな文書共通度を取りがちになる。以上がグループ 8、9、13 の精度が他に比べて著しく低くなる理由である。事実、グループ 8、9、13 において、イベント"01"関連のクラスターに対する文書共通度を 3 倍すると、線形モデルの場合、精度はグループ 8 で 0.9344 に、グループ 9 で 0.9476 に、グループ 13 で 0.9620 に向上する。しかし、この倍率を決定する合理的な方法は見出されてない。 (ii)提案手法においてキーとなる処理はトピックに特有でないステップ 3、5 における単語、単語対の検出にある。本処理を行わなかった場合、ステップ 3 における閾値、及び終了条件を適切に決めることができず、クラスタリングは正常に動作しなかった。また、ステップ 3、5 における文書共通度の算出において A の値を大きくとると、より単語を選択的に用いたことになる。一方、0 とすれば全ての単語を用いたことになり、文書共通度の定義は通常の文書間類似度に近いものとなる。A の値を変えて行った実験の結果では、A の値はクラスター文書集合中の全文書数の10%よりも大きくなると精度は低下し、これよりも小さくすると大部分のデータグループでは結果は殆ど変わらなかったが、グループ 8、9 ではそれぞれ 0.8571、 0.8919 に低下した（線形モデルの場合）。前述のようにグループ 8、9 に含まれるイベント"01"、"76" には互いに内容の近いニュースストリーが存在する。上記の事実は、紛らわしいニュースストリーが含まれるときには、クラスター文書集合で頻度の高い単語を選択的に用いることが有効であることを示している。 (iii)従来の非階層的なクラスタリングにおいては、クラスター数を予め与える必要があった。しかし、これはコーパスに関する先見的な知識なしには実質的には不可能な要求であり、クラスター数を推測することは重要な課題となっている。提案手法. では、表 2 の例だけではなく、[4]で挙げられている 12 種類のデータに対してもクラスター数は正しく求められている（Liu らの方法では 3 種類のデータに対して失敗）。クラスター数が正しく求められることは本手法のメリットの一つである。 7. まとめ以上、多文書間の共通性分析を用いた非階層のクラスタリング手法を提案した。提案手法はクラスターの種となる文書を見出した後、その文書と同じ内容の文書を検出してクラスターを成長させるというものであり、ポイントは、他のトピックに特有な単語、他のトピックと共有する単語の影響を排除しつつ、途中段階のクラスターに含まれる文書集合との内容の共通度を求める点にある。実験の結果、本手法のクラスタリングの精度における優位性が確認された。クラスタリングは TDT において重要な技術となっていること、トピックトラッキングにおいては種となる少数の文書と同じ内容の文書を抽出することが課題であるが、これは提案手法のアプローチと非常に近いことなどから、提案手法は TDT においても有効ではないかと考えられる。また、共通性分析において提案された文書集合共通度はクラスターの纏まり具合の評価尺度となりうるので、クラスター分析一般に応用できる可能性がある。これらは今後の重要な課題である。参考文献 [1] C. D Manning and H. Schutze. Foundations of Statistical Natural Language Processing, The MIT Press, 1999. [2] 徳永健伸. 情報検索と言語処理. 東京大学出版会(1999). [3] J. Allan, editor. Topic Detection and racking: Event-based Information Organization. Kluwer Academic Publishers, Boson, 2002. [4] X. Liu, Y. Gong, W. Xu and S.Zhu. Document Clustering with Cluster Refinement and Model Selection Capabilities. In Proceedings of the 25th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, pp.191-198. Tampere, Finland, August, 2002. [5] 川谷隆彦. 多文書間の共通性の分析．情報処理学会自然言語処理研究報告，2002-NL-152， pp.85-92(2002)．. 8 −100−.

(9)