DEIM Forum 2012 E2-6

文書集合の話題俯瞰のためのクラスタリング手法
横本

大輔†

鈴木

浩子†

牧田

健作†

福原

知宏††††

宇津呂武仁††

河田容英†††† 筑波大学大学院システム情報工学研究科 〒 305-8573 茨城県つくば市天王台 1-1-1†† 筑波大学システム情報系知能機能工学域 〒 305-8573 茨城県つくば市天王台 1-1-1††† (株) ナビックス 〒 141-0031 東京都品川区西五反田 8-3-6†††† 独立行政法人 産業技術総合研究所 サービス工学研究センター 〒 135-0064 東京都江東区青梅 2-3-26
あらまし

本論文では，複数の話題の間の冗長性を考慮して，文書集合における最適な話題俯瞰を実現するための文書クラスタリング手法を確立することを目的とする．本論文の枠組みにおいては，まず，Wikipedia を知識源として，各文書の内容と Wikipedia 中の記述を照合しながら，各文書の内容に密接に関連した話題ラベルを複数個付与する．
次に，話題ラベルが付与された文集集合に対して，複数の話題の間の冗長性を考慮して，文書集合における最適な話
題俯瞰を実現するための文書クラスタリングを行う．以上の枠組みを，特定のクエリに対して関連するブログ記事を収集した文書集合に対して適用し，その有効性を評価した．
キーワード クラスタリング，話題，俯瞰，冗長性

A Clustering Method for Overview of Topics in a Document Set
Daisuke YOKOMOTO† , Hiroko SUZUKI† , Kensaku MAKITA† , Takehito UTSURO†† , Yasuhide
KAWADA††† , and Tomohiro FUKUHARA††††† Grad. Sch. of Systems and Information Engineering, University of Tsukuba, Tsukuba, 305-8573, Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba 305-8573 Japan††† Navix Co., Ltd. Tokyo 141-0031, Japan†††† Center for Service Research, National Institute of Advanced Industrial Science and Technology,
Tokyo, 135-0064, Japan

Key words clustering, topic, overview, redundancy

1. は じ め に
現代の情報社会においては，情報の氾濫の問題が顕著であり，として，Wikipedia を知識源として話題の体系を構築し．この Wikipedia の体系を元に，ブロガーのブログ記事集合に対して話題を対応付ける (ここで，話題として対応付けられた

このことは，いわゆる情報爆発の問題を引き起こしている．そWikipedia エントリを観点と呼ぶ) 方式を提案した．また，そして，そのように爆発的に増大する情報の集約や，俯瞰をするのほか，複数の言語間で話題の分布を比較分析する方式 [3], [7]，ための技術の開発が強く望まれている．中でも，情報爆発が最あるいは，時系列方向の話題の分布を分析する方式 [4] 等を提も顕著に現れているのはウェブである．ウェブ上の情報の一例

案した．

として，近年，一般個人が自由に情報を発信するツールであしかし，文書集合を効率よく俯瞰するためには，文書を話題るブログが世界中で普及し，各地域の人々がそれぞれインターに分類するだけではなく，複数の話題の間の類似関係を把握し，ネット上で個人の意見や主観を発信することが可能になった．

類似した冗長な話題を省き，代表的な話題に集約した上で閲覧

それに伴い，様々な情報がブログに記載され，様々な人々の意する必要がある．この点において，我々のこれまでに提案した

見や主観が Web 上に氾濫している．

手法では，複数の話題の間の関連性を考慮した枠組みとなってこのような状況を鑑みて，本論文の前段として，我々は，ブいなかった．そこで，本論文では，複数の話題の間の冗長性をログ空間における多種多様な話題を俯瞰的に閲覧する方式の研考慮して，文書集合における最適な話題俯瞰を実現するための究を提案した [3], [4], [7], [10]．具体的には，基本的な方式 [10]文書クラスタリング手法を確立する．

図 1 文書への話題ラベルの付与および文書集合の話題俯瞰の枠組み

本論文における文書集合の話題俯瞰の全体的な枠組みを図 1

枠組みとして，クエリ尤度モデル [6] に基づく方法 (2. 節) を用に示す．この枠組みにおいては，まず，個々の文書に対して，話いる（注 1）．一例として，図 1 では，バンクーバー五輪の橋本聖

題ラベルを複数個付与する．この話題ラベル付与の処理におい子選手団長の記者会見の記事に対して「橋本聖子」，「バンクーては，図 1 に示すように，Wikipedia を知識源として，各文書

バーオリンピック」，「スキー」などの話題ラベルが付与されての内容と Wikipedia 中の記述を照合しながら，各文書の内容に密接に関連した話題ラベルを複数個付与する．この話題ラベル付与の処理においては，各文書をクエリとして，Wikipedia のエントリを順位付けする問題として定式化し，特に，理論的な（注 1）：文献 [10] においては，文書の内容と Wikipedia エントリ中の記述の間の関連性を測定するために，文書類似度に基づく方法を用いていたが，文献 [9]の結果においては，本論文で用いるクエリ尤度モデルに基づく手法の方が高い性能を示したため，本論文ではクエリ尤度モデルに基づく手法を用いる．

図 2 クラスタ間の冗長性を考慮した話題俯瞰のためのクラスタリングアルゴリズムの考え方

いる．同様にして，すべての対象文書に対して話題ラベルの付だけ代表的で，かつ，すでに選定された上位のクラスタとは類与を行う．

似しないクラスタを順に選定する．

次に，話題ラベルが付与された文集集合に対して，複数の話

本論文では，以上の枠組みを，特定のクエリに対して関連す

題の間の冗長性を考慮して，文書集合における最適な話題俯瞰

るブログ記事を収集した文書集合に対して適用し，その有効性を実現するための文書クラスタリングを行う (3. 節)．このクラを評価した．本論文の範囲では，特に，選定された上位のクラスタリングにおいては，図 2 に示すように，各クラスタに属す

スタの正解率，および，上位クラスタ間の冗長性の除去に重点る文書に付与された話題ラベルに基づいて，クラスタ間の冗長を置いてアルゴリズムの調整を行い，一部，既存研究 [5] を模性を測定するとともに，各クラスタの代表性を測定し，できる倣した手法，および，語の頻度を用いた tf-idf による手法等のここで，文書コレクション C は，検索対象の文書集合である．

性能を上回る性能を達成した．

式 (3)，および，式 (4) と，補間の度合いを表現する定数

2. 文書への話題ラベルの付与

λ ∈ [0, 1] を用いて，線形補間法による推定値は次のように定義

本節では，提案手法，比較対象として用いた tf-idf による手法，および，一部，既存研究 [5] を模倣した手法について述べる．

2. 1 Wikipedia を知識源とする文書への話題ラベルの付与

される．

P (wi | θD ) = λPM L (wi | θD ) + (1 − λ)PM L (wi | θC )(5)

2. 1. 1 クエリ尤度モデル
本節では，情報検索の手法の 1 つであり，本研究で用いているクエリ尤度モデル [6] について説明する．

ことができる．

クエリと文書集合が与えられ，クエリに適合する度合いに従って文書を順位付けしたい場合，文書 D (∈ 文書コレクション C)
がクエリ Q に適合する確率 P (D | Q) を求めることができれば，これに従って順位付けを行うことができる．このとき，ベイズの定理を用いることにより，次式を得ることができる．

P (D | Q) =P (Q | D)P (D)P (Q)上式を用いることで，式 (2) のクエリ尤度 P (Q|θD ) を求める

(1)

2. 1. 2 文書への話題ラベルの付与
本節では，前節で述べたクエリ尤度モデルの考え方を用いて，対象文書集合の個々の文書に対して話題ラベルを付与する手法について説明する．なお本節以降では，文書を表す記号としてA を用いる．
本研究では，文書中に出現する Wikipedia エントリタイトル
から，文書の話題ラベルとして相応しいものを自動選定する．

P (Q) は文書 D に依存しないので定数とみなせる．また 文書

そのために，文書をクエリとみなして，文書中にエントリタイ

D に関しての何らかの事前知識がない限り，P (D) は一様であトルが出現した Wikipedia エントリ集合のランキングを行う．

るとみなす．このとき，式 (1) を次のように簡略化できる．

P (D | Q) =はじめに，対象文書集合の個々の文書 A ∈は，文書中に出現した Wikipedia エントリタイトルの集合として表現さ

P (Q | D)P (D)
P (Q)

れる．

∝ P (Q | D)P (D)A = t(E1 ), . . . , t(En )∝ P (Q | D)

まず，対象文書集合
上式に基づく情報検索手法をクエリ尤度モデルと呼ぶ．

において，エントリタイトル t(E) が10 個以上の文書に出現した Wikipedia エントリを集めて，次に，文書中の単語は独立に生起すると仮定して，文書をユニ

Wikipedia エントリ集合 ( ) を作成する．

グラム言語モデルとして表現する．このとき，文書 D におけるユニグラム言語モデル θD からクエリ Q が生成される尤度，すなわちクエリ尤度 P (Q|θD ) は，語彙 w ∈ V = {w1 , . . . , w|V | }のクエリ Q における出現頻度 c(wi , Q) を用いて次式のように定義される．

( ) =E

df( , t(E) ) >= 10

次 に ，文 書 A に エ ン ト リ タ イ ト ル t(E) が 出 現 し ，か つ ，Wikipedia エントリ集合 ( ) に含まれる Wikipedia エントリ
E を抽出し，文書 A に対する話題ラベルの候補集合に対応す

P (Q | θD ) =P (w | θD )c(wi ,Q)

(2)

wi ∈V

上式を求めるためには，文書モデルのパラメータ θD を推定る Wikipedia エントリ集合 (A) を作成する．

(A) =E∈ ( )

t(E) ∈ A

しなければならない．そのための推定方法の 1 つとしては，文そして，クエリ尤度モデルに基づいて，文書 A をクエリとみ

書 D における最尤推定値 PM L (wi | θD ) と，文書コレクショ

なして，Wikipedia エントリ集合 (A) の順位付けを行う．具

ン C における最尤推定値 PM L (wi | θC ) を線形補間するという体的には，Q = A，D = E ∈ (A)，C = ( ) として，式 (2)手法がある．まず，文書 D における最尤推定値 PM L (wi | θD )の P (A | θE ) を求める．
以上のように推定した P (A | θE ) を用いることで，文書 A

は，相対頻度を用いて以下のように定義される．

PM L (wi | θD ) =c(wi , D)|D|に付与する話題ラベル集合 L(A) を以下の手順で決定する．具(3)

ここで，c(wi , D) は文書 D において語 wi が出現する頻度，

体的には，Wikipedia エントリ集合 (A) における P (A | θE )の最大値 maxE  ∈ (A)に対して，その α 倍以上の P (A | θE ) を持つ|D| は 文書 D の文書長すなわち総語数を示す．一方，文書コ

Wikipedia エントリのタイトル t(E) を，文書 A の話題ラベル

レクション C における最尤推定値 PM L (wi | θC ) は次のようにとして抽出する．また，1 文書に付与する話題ラベルの数は最して推定できる．

エントリを選定し，そのタイトルを L(A) の要素とした．以上

c(wi , D)
PM L (w | θC ) =

D∈C

|D|
D∈C

大 10 個とし，P (A | θE ) の大きいものから順に上位 10 個まで
より，t(E) ∈ L(A) となる Wikipedia エントリ E の満たすべ(4)

き条件は以下となる．

•

E ∈ (A)•P (A | θE  )P (A | θE ) >= α × max•

P (A | E) の大きいものから順に 10 個 E を選ぶ．

3. 話題俯瞰のためのクラスタリング手順

E ∈ (A)

3. 1 定 式 化

なお，本論文では α = 0.6 とした．

2. 2 比較手法：tf-idf

まず，話題ラベル l を持つ文書の集合 (l) を以下で定義する．

本節では，比較手法として，Wikipedia の知識を用いず，単(l) =

語頻度と文書頻度を用いた tf-idf により話題ラベルを付与する
手法について説明する．
具体的には，tf(A, E) を，文書 A においてエントリタイトル

t(E) が出現する頻度，df( , E) を，文書集合においてエン

トリタイトル t(E) が出現する文書数，| | を総文書数として，A∈l ∈ L(A)さらに，これを拡張して，話題ラベル集合 L の要素であるラベルを全て持つ文書の集合 (L) を，各要素であるラベルを持つ文書の集合の積集合として，以下で定義する．

A∈

(L) =

tf-idf の値が下限値以上となるエントリタイトル t(E) を最大l ∈ L(A)l∈L

10 個選定する．以上より，話題ラベル集合 L(A) の要素 t(E)この表記を用いれば，ラベル l を持つ文書の集合は， ({l}) との満たすべき条件は以下となる．

表現される．同様に，ラベルの組 l1 および l2 を持つ文書の集•••合は， ({l1 , l2 }) と表現される．

E ∈ (A)|
tf(A, t(E)) · log2 df( |,t(E))| |tf(A, t(E)) · log2 df( ,t(E))>=kの大きいものから順に 10

そして，文書に付与するラベルとして，10 個以上の文書に付与される必要があるという条件を課すと，話題ラベルの候補集個まで選ぶ．

合としては，一つの話題ラベルの場合は，以下のまた，本論文では，tf-idf の下限値を k = 10.0 とした．

題ラベルの組の場合は，以下の

2. 3 比較手法：話題ラベルの出現確率の差を用いる手法
最後に，先行研究 [5] で提案されている手法について説明する．この手法では，対象文書集合における出現確率が，一般の文書集合における出現確率に比べて大きい語が，対象文書集合

1

=

{l}

1 ，二つの話

2 で記述される．

L(A), | ({l})| >
= 10

l∈
A∈

2

=

{l1 , l2 }

l1 , l 2 ∈({l1 , l2 })| >
= 10

1, |

において話題になっている語であると考え，そのような語を話

ここで， 1 ，あるいは， 2 は，実際には，前節で述べた各手

題ラベルして抽出する．

法によって文書 A に付与された話題ラベルの集合を L(A) とし具体的には，まず語 w の出現確率の距離 δw (p || q) として，次式で定義される pointwise KL ダイバージェンスを用いる．

δw (p || q) = p(w) log

スタ間の重複が少なくなるように，クラスタを抽出することで次に，対象文書集合と一般的な文書集合における出現確率のpointwise KL ダイバージェンスを求める．本論文では，一般的な文書集合として，Wikipedia の全エントリの集合をとして，の全文書集合を用いた．また，式 (4) の PM L (wi | C) において，文書コレクション C を，それぞれ，C = ，C =として推定した最尤推定値を PM L (t(E) | )，および，PM L (t(E) |大きいものから降順に上位 300 個のエントリタイトル t(E) をに対する話題ラベルの候補集合 L0 ( ) を

作成する．

t(E)

き線形和をコストとして，貪欲アルゴリズムによりコストをできるだけ小さくするラベルを順に選定する（注 2）．

•

各文書におけるラベルと文書の関係の強さの平均を表す純度項

rel(A, l)Crel (L) = −A∈ (L) l∈L) ) ( = φとおく)

次に， ( ) 中の Wikipedia エントリのタイトルのうち，φ のL0 ( ) =ある．そこで，本論文においては，以下に述べる各項の重み付)として，以下の pointwise KL ダイバージェンスを求める．

収集し，文書集合

本研究のタスクは，これらの話題ラベルで定義されるクラス
タから，できるだけ文書集合を被覆し，かつ，できるだけクラ

p(w)
q(w)

δw ( PM L (t(E) | ) || PM L (t(E) |て，それらの L(A) を上記の式に適用することにより求める．

E ∈ ( ), t(E) ∈ L0 ( )rel(A, l) =•log 2 P (A | E)

(クエリ尤度モデル)|
tf(A, l) · log2 df(| ,E)(tf-idf)

クラスターの大きさを表す項

Csize (L) = −•| (L) |

| (L)|| |候補クラスター集合

内における重複度を表す項
そして，各文書 A に対する話題ラベルとして，文書中に出現したエントリタイトル t(E) のうち L0 ( ) に含まれるものを収集し話題ラベル集合 L(A) とする．

L(A) =

t(E) ∈ A

t(E) ∈ L0 ( )J( (L), (L ))Cdup−rst (L) =L ∈ −{L}

|

|−1

（注 2）
：これの項のうち，「各文書におけるラベルと文書の関係の強さの総和を表す純度項」を除いては，文献 [5] で提案されたものを参考にしているが，符合の正負などは本論文において経験的に設定した．

•

既に選択したクラスタ集合に対する重複度を表す項

実験に用いるデータセットとしては，クエリ t0 に対して，関L ∈ slt

ただし，J(S1 , S2 ) は次式で定義される Jaccard 係数を示す．

J(S1 , S2 ) =価

4. 1 データセット

J( (L), (L ))Cdup−slt (L) =4. 評|S1 ∩ S2 ||S1 ∪ S2 |連するブログ記事集合を収集した結果を用いた．クエリ t0 を含む日本語ブログの収集においては，Yahoo! Search BOSS

API（注 3） を利用し，日本語ブログホスト大手 6 社（注 4）のドメインを対象としてブログ記事の収集を行った．検索の際には，複数

また，各項の重み付き線形和を次式で定義する．

のドメインを一度に指定して検索し，1,000 件の記事を取得す

cost(L) =る．次に，ブログ記事検索後，検索結果の URL をブログサイ

λ1 · Crel +λ2 · Csize + λ3 · Cdup−rst + λ4 · Cdup−slt

ト単位にまとめる．その結果，一つの検索クエリあたり約 200

本論文では，コストができるだけ小さくなるような順にラベ

前後のブログサイトが取得される．次に，各ブログサイトをドルを選定する手順として以下の「話題ラベル選択手順」を用

メイン指定し，初期クエリ t0 を検索クエリとすることにより，いる．

各ブログサイト中において初期クエリ t0 を含むブログ記事をを作成する．

収集し，ブログ記事集合「話題ラベル選択手順」
手法ごとに決められている話題ラベルの候補集合
あるいは， 2 を
ベルの集合

1，

の初期値とし，選択された話題ラ

slt の初期値を空集合とする．

(1) 各ラベル候補 L ∈本論文においては，「原子力発電所」をクエリ t0 とし，8,051
記事を収集した．

4. 2 評 価 手 順
前節で作成したブログ記事集合を対象文書集合について，cost(L) を

計算

として，

3. 2 節で述べた手法により，50 個のクラスタを抽出した結果を評価した．評価手順としては，ラベルを人手により評価し，「適(2) score(ln ) が最大のラベルを選択

切」，「やや適切」，「やや適切でない」，「適切でない」の 4 段階のLmin = argmin cost(L)

適合度を付与した．そして，「適切」な場合の適合度を 100%とL∈(2a) 選択したラベル Lmin をし，以下，段階的に 66%，33%，0%とし，上位 50 個のクラス

slt に追加(2b) 選択したラベル Lmin を候補ラベル集合

タにおけるラベルの適合度の平均として，正解率を評価した．
から除外(2c) Lmin の順位 rank(Lmin ) = | slt | を記録|Lslt | >= N を満たすまで，(1)，(2) の処理を繰り返す．
3. 2 評価対象手法•

ラベル数が 1 の場合
50

適合度 (li1 )
正解率 =

•

クエリ尤度モデルに基づいて話題ラベルの付与を行う．話50

ラベル数が 2 の場合

評価手法の一覧を表 1 に示す．

(ID=1) 2. 1 節の手法により，Wikipedia を知識源として，

i=1

50

適合度 (li1 ) + 適合度 (li2 )
正解率 =

i=1

50 × 2

題 ラ ベル 数は 2．コ ス ト cost(L) の 各項 の 重み は 経験 的に

ここで，lij は i 番目に抽出されたクラスタの話題ラベルを表す．

λ1 = λ2 = λ3 = 0.3, λ4 = 0.1 とした．

話題ラベル数が 1 の場合，i 番目のクラスタの話題ラベルは li1(ID=2) 話 題 ラ ベ ル 数 に よ る 違 い の 比 較 ，分 析 の た め ，(ID=1) と同様の手法で，話題ラベル数のみ 1 とする．

のみである．話題ラベル数が 2 の場合，i 番目のクラスタは 2
つの話題ラベル li1 ，li2 を持つ．そして，上位 50 個のクラスタ(ID=3) 純 度 項 の 有 無 に よ る 違 い の 比 較 ，分 析 の た め ，が持つすべての話題の適合度の平均として，正解率を定義した．

(ID=1) におけるコスト cost(L) において，純度項を考慮しまた，50 個のクラスタによって被覆した文書の割合と，収集ないように λ1 = 0 とする．それ以外の重みは，暫定的に，された文書の重複率を求めた．

λ2 = 0.7, λ3 = 0.2, λ4 = 0.1 とした．
(ID=4) 文 書 に 対 す る 話 題 ラ ベ ル の 付 与 に お い て ，Wikipedia の 知 識 を 用 い る こ と の 有 効 性 を 確 認 す る た め ，

50

(Li )
被覆率 =

i=1

Wikipedia の知識を用いない話題ラベルの付与手法を用いる．具体的には，2. 2 節の手法により，tf-idf に基づいて話題ラベルを付与する．

| |
50

(Li )
重複率 = 1 −i=150

| (Li ) |(ID=5) Wikipedia の知識を用いずに話題ラベルの付与をi=1行う手法として，2. 3 節の手法により，確率の差を用いて話題
ラベルの候補集合を作成する．また，文献 [5] の手法を模倣し，純度項は用いない．

（注 3）：http://developer.yahoo.com/search/boss/（注 4）：fc2.com，yahoo.co.jp，ameblo.jp，goo.ne.jp，livedoor.jp，hatena.

ne.jp

さらに，適合度とは別に，ラベルの粒度が大きすぎるもの (適の場合であっても，内容の把握は容易になっている．

合度は「やや適切でない」)，小さすぎるもの (適合度は「やや手法 1 および手法 2 と手法 3 の比較を以下に述べる．手法 3

適切でない」) の数を集計し，ラベル数 2 の場合については，2の，純度の項がを用いない手法の場合も，正解率は 60.0%であつのラベルが冗長かどうかについても判定を付与した．

り，手法 1 および手法 2 の Wikipedia を知識源として用いる手

ここで，2 個の話題ラベルを用いた際には，一方のラベルの法に比べ，15%ほど低い正解率を示した．正解率を下げる要因

粒度が大きい，または小さい場合でも，もう一方のラベルが適としては，「日本 政治」や「原子炉 システム」など，粒度の大切であれば，ユーザはクラスタの内容を把握することができる

きい話題ラベルが多く抽出されていることが挙げられる．これと考えられる．そこで，提案手法における正解率の上限値としは，純度項を考慮せずに，重複の少ないものから，できる限りて，一方のラベルの粒度が不適切な場合でも，もう一方のラベ大きいクラスタを選ぶことになるため，多くの文書を持つ粒度

ルと同じ適合度を付与した場合の正解率を求めた．

の大きな話題ラベルが収集する傾向が強くなっているものと考4. 3 評 価 結 果えられる．これに対して，純度項を用いた場合，話題ラベルの評価の結果を表 1 に示す．また，各手法において抽出されたまとまりの良さを捉えることで，そのような話題ラベルが選ば

上位 5 個の話題ラベルを表 2 に示す．
まず，手法 1 および手法 2 と手法 4 の比較を以下に述べる．

れる問題を解決できていると考えられる．
最後に，手法 1 と手法 2 の比較を以下に述べる．手法 1 の，手法 1 および手法 22 の Wikipedia を知識源として話題ラベル「東海地震，地震予知」，「再生可能
ラベル数 2 の場合において，の付与を行い，コスト cost(L) において純度項を用いた手法は，エネルギー，ドイツ」など，2 つの話題ラベルがあることで文ラベル数によらず，約 75%という高い正解率を示した．これに書集合の内容が的確に表現されているものが確認できた．しか対して，手法 4 の Wikipedia を知識源として用いず，tf-idf にし，両手法の正解率はほぼ同程度という結果になっている．ラ

基づいて話題ラベルの付与を行った場合，正解率は 59.3%と，ベル数 2 の場合では，2 つのラベルのうち一方が適切であって15%程度の差がみられた．tf-idf による手法は，単語の出現頻も，それと包含関係にある粒度の大きいラベルが，もう一つの度のみに基づいて話題ラベルを付与しているため，「時事通信

ラベルに選ばれているものがあり，それらが正解率を下げる原社」，「出版社」といった，その新聞社のニュースを引用してい因となっていた．2 つのラベルの冗長性を考慮して，そのようれば出現する単語や，ブログ記事のヘッダ部，フッター部に出なラベル組を選ばないようにすることで，精度の改善が期待で現しているだけの単語などを話題ラベルとして抽出してしまっ

きると思われる．そのための手法の 1 つとして，Wikipedia のており，これらが正解率を大きく下げる原因となっていた．ま知識源を用いてラベル間の上位下位関係を判定するといった方

た，抽出された適切な話題ラベルの傾向として，tf-idf による法が考えられる．また，手法 1 の正解率の上限値として，一方手法は「首相，野田」や「東電，損害賠償」といった，ある程のラベルが適切であれば，もう片方に粒度が不適切なラベルが度一般的で，文書において出現しやすい Wikipedia エントリ

選ばれることを許容するという基準で評価を行った結果，正解

タイトルが選ばれる傾向にあった．これに対して，Wikipedia

率は 80.0%となり，単独のラベルを用いる手法 2 よりも高い正を知識源として用いる手法では，「国際原子力事象評価尺度，原解率を示した．

子力安全委員会」，「非常用炉心冷却装置」など，具体性の高い

Wikipedia エントリタイトルが話題ラベルとして多く選ばれて

5. 関 連 研 究いた．これらの話題ラベルは，文書の主題になっていても，文

文献 [5] では，本論文と同様に文書集合をできるだけ冗長性

書中の出現頻度があまり多くならず，そのため単語頻度の情報を排してクラスタリングするタスクを集合被覆問題として定式だけを用いている手法では収集できなかったと考えられる．

化している．対象文書集合と一般的な文書集合における単語の次に，手法 1 および手法 2 と手法 5 の比較を以下に述べる．

出現確率の差に基づいて，話題ラベルとなる n グラムを抽出手法 5 の，確率の差を用いて話題ラベルの候補を制限する手法

し，貪欲法によって集合被覆問題を解く手法を提案し，確率のも，正解率は 61.3%であり，手法 1，2 の Wikipedia を知識源

差のみに基づいてクラスタリングする場合に比べて高い性能をとして用いる手法に比べ，15%ほど低い正解率を示した．正解発揮することを示している．この手法に対して，本論文では，率を下げる要因としては，科学者や反原発活動家の人名といっ

Wikipedia を知識源として文書に話題ラベルを付与することた，粒度の小さい話題ラベルが収集される傾向にあることが挙で，より適切な話題ラベルを抽出できることを示した．また，げられる．それらの粒度が小さい Wikipedia エントリタイトル

文献 [5] では単一の話題ラベルを用いているのに対し，本論文は一般的な文書集合における出現確率が小さく，確率の差が大ではこれを拡張して複数のラベルを付与することを提案した．

きくなりやすいため，話題ラベルの候補として抽出されやすい．

一方，文献 [2] は，Web ページの検索結果を分類し，各分類

そのため，そのような粒度の小さい話題ラベルが抽出される傾に対して適切な要約文を付与するという手法を提案している．

向が強くなっていると考えられる．また，話題ラベルを 1 つしまた，文献 [1], [8] では，検索された個々の Web ページに対しか提示していないため，
「報酬」，
「牛肉」，
「ロボット」といった，てラベルの付与を行い，付与されたラベルに基づいて分類を行

それだけではどのような話題なのか把握できないものが多く見う手法を提案している．これらの手法では，我々のこれまでのられた．これに対して，Wikipedia を知識源とする手法では具

手法 [10] と同様に，複数のクラスタ間の冗長性を陽に検出し，体性の高い話題ラベルが選ばれているため，話題ラベルが 1 つ

抑制する方式を採用していない点が本論文の方式とは異なる．

表 1 各評価対象手法の評価結果
話題
手法

ラベルの

粒度大

粒度小

冗長

被覆された

被覆率

重複率

ID

正解率

(個数)

(個数)

(個数)

述べ文書数

(%)

(%)

(%)

表2

1

75.6

16

2

10

710

8.8

7.6

2

75.3

1

4

-

3,727

46.3

28.0

3

60.0

12

5

14

3,257

40.5

17.6

4

59.3

7

0

9

661

8.2

12.9

5

61.3

2

2

-

7,776

96.6

75.4

1

80.0

上限値

( +4.4 )

16

2

-

710

8.8

7.6

12

5

-

3,257

40.5

17.6

7

0

-

661

8.2

12.9

3

64.0

上限値

( +4.0 )

4

66.7

上限値

( +7.4 )各手法において抽出された上位 5 個の話題ラベル

手法 ID

ログ記事を収集した文書集合に対して適用し，その有効性を評

新党日本，政党

価した．今後は，被覆率を改善するために，LDA 等の既存のト

原子力事故，チェルノブイリ原子力発電所事故

1

津波，リスク
石炭，再生可能エネルギー2

河内原子力発電所

モデルによって推定されたトピックにおいても一定の冗長性が原子力存在するという設定のもとで，トピック集合の俯瞰を実現する．

高速鉄道
原子力発電，原子力福島第一原子力発電所，東京電力
放射能，放射性物質
原子炉，原子力
津波，地震復興，ボランティア
歯科，インプラント
時事通信社，小説
検察官，小沢一郎
岩手県，宮城県
原子力発電
原子炉

5

より俯瞰性の高いクラスタリング手法を実現する．その手法においては，文献 [11] 等とは異なり，LDA 等の既存のトピック

新党日本

4

ピックモデルによって推定されたトピックと提案手法を併用し，発電所，揚水発電

広野火力発電所

3を行った．以上の枠組みを，特定のクエリに対して関連するブ

話題ラベル

原子力
放射能
東京電力

6. お わ り に
本論文では，複数の話題の間の冗長性を考慮して，文書集合における最適な話題俯瞰を実現するための文書クラスタリング
手法を確立することを目的とした．本論文の枠組みにおいては，
まず，Wikipedia を知識源として，各文書の内容と Wikipedia
中の記述を照合しながら，各文書の内容に密接に関連した話題
ラベルを複数個付与する．次に，話題ラベルが付与された文集集合に対して，複数の話題の間の冗長性を考慮して，文書集合における最適な話題俯瞰を実現するための文書クラスタリング

文献[1] 馬場康夫, 黒橋禎夫. キーワード蒸留型クラスタリングによる大規模ウェブ情報の俯瞰. 情報処理学会論文誌, Vol. 50, No. 4,
pp. 1399–1409, 2009.
[2] 原島純, 黒橋禎夫. PLSI を用いたウェブ検索結果の要約. 言語処理学会第 16 回年次大会論文集, pp. 118–121, 2010.
[3] 牧田健作, 横本大輔, 鈴木浩子, 宇津呂武仁, 河田容英, 福原知宏.
Wikipedia を多言語知識源とするブログ集合の話題分析. 電子
情報通信学会技術研究報告, NLC2011-18, pp. 95–100, 2011.
[4] 牧田健作, 横本大輔, 宇津呂武仁, 福原知宏. トピックに関する話
題の時系列分布に着目したブログ分析. 第 3 回 DEIM フォーラ
ム論文集, 2011.
[5] P. Muthukrishnan, J. Gerrish, and D. R. Radev. Detecting
multiple facets of an event using graph-based unsupervised
methods. In Proc. 22nd COLING, pp. 609–616, 2008.
[6] J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In Proc. 21st SIGIR, pp.
275–281, 1998.
[7] 鈴木浩子, 横本大輔, 牧田健作, 宇津呂武仁, 河田容英, 福原知宏. Wikipedia を知識源とする日英ブログ記事集合の観点分
類と言語間対照分析. 情報処理学会研究報告, Vol. 2011, No.
(2011–DBS–153), 2011.
[8] 戸田浩之, 中渡瀬秀一, 片岡良治. 特徴的な固有表現を用いたラベル指向ナビゲーション手法の提案. 情報処理学会論文誌：デー
タベース, Vol. 46, No. SIG 13(TOD 27), pp. 40–52, 2005.
[9] D. Yokomoto, K. Makita, H. Suzuki, D. Koike, T. Utsuro,
Y. Kawada, and T. Fukuhara. LDA-based topic modelingin labeling blog posts with Wikipedia entries. In Proc. 1st
IDP, 2012.
[10] 横本大輔, 林東權, 牧田健作, 宇津呂武仁, 河田容英, 福原知宏,
神門典子, 吉岡真治, 中川裕志, 清田陽司. 特定トピックに関するブログ記事集合の観点分類における Wikipedia の利用. 第 3 回
DEIM フォーラム論文集, 2011.
[11] Y. Yue and C. Guestrin. Linear submodular bandits andtheir application to diversiﬁed retrieval. In Advances in
Neural Information Processing Systems 24, pp. 2483–2491.
2011.