甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

動的計画法でテキストセグメンテーション

いやいや、お久しぶりです。
実に半年以上も更新が滞ってました。
ちゃんと生きてます。

以前、動的計画法によるシーケンシャルデータのセグメンテーションという記事を書きましたが、
今回はそれを応用して、テキストセグメンテーションを行おうと思います。

テキストセグメンテーションって?

テキストセグメンテーションとは、文章を意味的な段落に分割することを言います。
例えば、ある1つの文章が、野球の話題→サッカーの話題→尿道結石の話題→また野球の話題
といった具合に話題が推移したとします。
この文章を、これを下図のように話題ごとのセグメントに分割しようってのが、
テキストセグメンテーションです。

-----------------------------------------------------
今年もペナントレースが始まりました。
去年、セリーグは巨人、パリーグ楽天が優勝。
・・・
何はともあれ頑張ってもらいたいものです。
-----------------------------------------------------
そういえば、今年はサッカーワールドカップの年。
・・・
どの国が優勝するか注目です。
-----------------------------------------------------
ところで、私、尿道結石になってしまいました。
・・・
とても辛いので、早く治したいです。
-----------------------------------------------------
話を元に戻しますが、去年優勝した楽天は、
エースだった田中投手が抜け、
・・・
今から楽しみです。
-----------------------------------------------------

テキストセグメンテーションは様々な手法が提案され、
LDAのような潜在トピックモデルを利用した手法や接続詞に着目した手法などがあります。
今回は、セグメント内の単語のまとまり具合をスコアとし、
その合計スコアを動的計画法により最大化するという手法でセグメンテーションを行います。
探してみると以下の論文がやりたいことと一致しているので、こちらを参考にしました。
A. Kehagias, P. Fragkou, V. Petridis. 2003. Linear text segmentation using a dynamic programming algorithm. In Proceedings of the EACL, 171–178.

動的計画法でセグメンテーションを行う関数自体は以前の記事で作成したものを踏襲するので、
テキストデータクラスを定義し、そのメソッドとして、セグメント内のスコアを計算するh(t1,t2)と
長さを返すGetLength()さえ定義すれば実現できます。

前提

前提として、セグメントを考える際の最小単位は、センテンスとします。
つまり、シーケンスデータで言うところの1つのデータポイントは、
今回の場合は、1つのセンテンスとなります。
従って、文章に含まれるセンテンス数をTとすると、GetLengthメソッドは、
このTを返すことになります。
また、セグメントのスコアを計算する際、単語単位で計算しますが、
今回はストップワードを除いた名詞のみを抽出して利用します。
文章に含まれる名詞数(ストップワード除く)をLとします。

セグメントのスコア

まず、センテンス間の類似度を考えます。
この類似度は、センテンス間で共通の単語を含んでいれば、その個数分類似すると考えます。
そのため、次のようなL \times Tの行列{\bf F}を定義し(元論文と行と列が逆転してるので注意)、

F_{lt} = \begin{eqnarray}
 \left\{ \begin{array}{ll} 1 & \mbox{l-th word is in t-th sentence} \\ 0 & \mbox{else.}  \end{array} \right.
  \end{eqnarray}

次の式で計算される行列{\bf D}はセンテンス間の類似度を表す行列となります。

{\bf D} = {\bf F}^T {\bf F} (ただし、D_{ii} = 0

つまり、センテンスiとセンテンスjの類似度はD_{ij}となります。
なお、元論文はセンテンス間で共通の単語を複数含んでても、
その個数に限らずD_{ij} = 1となっています。

この行列{\bf D}を用いて、セグメント内のスコアを計算します。
今、セグメントの始点をt1、終点をt2とすると、
そのセグメントに含まれるセンテンスの番号tt1 \leq t < t2になります
t2番目のセンテンスはそのセグメントに含まれない)。
そしてそのスコア計算は以下のようになります。

J = \frac{\sum_{i=t1}^{t2-1} \sum_{j=t1}^{t2-1} D_{ij}}{(t2 - t1)}

要は、セグメントに含まれるセンテンスそれぞれの類似度を全部足し合わせ、
セグメントの長さで割ったものをスコアとしています。
元論文はセグメント長の平均や分散を予め用意した学習データから学習したり、
分母をr乗したりとか、もっと工夫していますが面倒なのでそこまでやりません。

ソースコード

単語の抽出

何はともあれ、単語を抽出しなければ始まりません。
MeCabを利用して形態素解析を行い、名詞を抽出します。
MeCabなど形態素解析は初挑戦で戸惑いましたが、
TaggerクラスのParseToNodeメソッドの戻り値であるnodeインスタンス
featureを利用すれば品詞とその細分類が簡単に得られるとわかったので、これを利用します。
ストップワードとしては、品詞の細分類が代名詞、非自立、数、接尾のものとしています。
ということで、この操作を行い、抽出した単語のリストを返す関数を以下に示します。

import MeCab

def GetListOfWord(text):
    tagger = MeCab.Tagger('-Ochasen')
    encoded_text = text.encode('utf-8')
    node = tagger.parseToNode(encoded_text)
    WordList = []
    while node:
        if(node.feature.split(",")[0] == "名詞" and
            node.feature.split(",")[1] != "代名詞" and
            node.feature.split(",")[1] != "非自立" and
            node.feature.split(",")[1] != "数" and
            node.feature.split(",")[1] != "接尾"):
            if WordList.count(node.surface.decode('utf-8')) == 0:
                WordList.append(node.surface.decode('utf-8'))
        node = node.next
    return WordList

調べたところによると、半角記号が名詞のサ変接続になってしまうようですが、
とりあえず今回は気にしないことにします。

センテンスの抽出

特別なことはしません。
読点「。」、感嘆符「!」、疑問符「?」があれば、
そこがセンテンスの区切りとして抽出します。
センテンスのリストを返す関数は以下の通りです。

def GetSentenceList(text):
    sentence = u""
    SentenceList = []
    for t in text:
        sentence = sentence + t
        if t == u"。" or t == u"?" or t == u"!":
            SentenceList.append(sentence)
            sentence=u""
    return SentenceList
行列Fの計算

行列\bf{F}は疎な行列なので、
scipyのスパース行列クラスの1つlil_matrixとして扱います。
まず、上記の2関数を用いて、単語のリストとセンテンスのリストを取得します。
その後、forループを用い、各々センテンスで単語を抽出、
そのセンテンスに含まれる単語のインデックスを取得、
行列\bf{F}におけるそのインデックスの行に1を代入という流れになります。

import scipy.sparse as sp

def GetFMatrix(text):
    WordList = GetListOfWord(text)
    SentenceList = GetSentenceList(text)
    F = sp.lil_matrix((len(WordList) , len(SentenceList) ))
    i = 0
    for sentence in SentenceList:
        idx = [WordList.index(w) for w in GetListOfWord(sentence) if w in WordList]
        F[idx , i] = 1
        i += 1
    return (F , WordList , SentenceList)
テキストデータクラス

先述のとおり、テキストデータクラスのメソッドとして、
GetLength()とh(t1 , t2)さえ定義すれば、
前回作成した動的計画法プログラムがそのまま使えます。
まず、__init__メソッド内で、上述のGetFMatrix(text)関数を呼び、
行列\bf{F}と単語リスト、センテンスリストを得ます。
そして、行列\bf{D}を計算します。
後は、GetLength()はセンテンスの個数を返し、h(t1 , t2)は上述のスコア計算値を返せばOK。

import numpy as np

class TextSequence:
    def __init__(self , text):
        (F , self.WordList , self.SentenceList) = GetFMatrix(text)
        D = (F.T * F).toarray()
        D -= np.diag(np.diag(D))
        self.F = F
        self.D = D

    def GetLength(self):
        return len(self.SentenceList)

    def h(self , t1 , t2):
        return np.sum(np.sum(self.D[t1:t2][: , t1:t2])/(t2-t1))

実験

青空文庫から芥川龍之介羅生門トロッコ黒衣聖母の4作品を引っ張ってきて、
これらを連結した文章を一つ作成しました(akutagawa.txtとしています)。
全部で543個のセンテンスで構成されています。
この文章に対し、セグメント数を4としてセグメンテーションを行い、
キチンと作品と作品の境にセグメントの区切りが来れば成功。
ということで、次のように実行しました。

>>> import DPSegmentation
>>> text =codecs.open('akutagawa.txt', 'r', 'utf-8').read()
>>> Seq=TextSequence(text)
>>> (T , score) = DPSegmentation.SequenceSegmentation(Seq , 4)

結果としては、綺麗に各作品セグメントで分割することに成功。
分割したテキストデータをここに貼るわけにもいかないので(貼ってもあまり意味ないし)、
各セグメントに対する単語のスコア(その単語がどれだけ、そのセグメントに関わるか)を
算出し、その上位5件を示すことにします。
このスコア算出のために以下に示すGetWordScore(t1 , t2)メソッドを
TextSequenceクラスに追加しました。

    def GetWordScore(self, t1 , t2):
        W=((self.F[: , t1:t2] * self.F[: , t1:t2].T).toarray()).sum(0)
        WordScoreList=[]
        for idx in W.argsort()[-1::-1]:
            WordScoreList.append((self.WordList[idx] , W[idx]))
        return WordScoreList

やってることは、ある単語がセンテンス間で共通する場合1、しない場合0となる操作を、
それがセグメント内の全センテンス間の組み合わせで求め、
その合計値を各々の単語のスコアとするというもの。

で、そのスコアを算出した結果は以下の通りです。

・セグメント1(羅生門セグメント)
(u'下人', 283.0),(u'老婆', 170.0),(u'死骸', 88.0),(u'雨', 79.0),(u'男', 70.0)

・セグメント2(鼻セグメント)
(u'供', 484.0),(u'鼻', 445.0),(u'弟子', 165.0),(u'僧', 165.0),(u'顔', 112.0)

・セグメント3(トロッコセグメント)
(u'良平', 240.0),(u'トロッコ', 200.0),(u'線路', 88.0),(u'土工', 77.0),(u'今', 46.0)

・セグメント4(黒衣聖母セグメント)
(u'利', 233.0),(u'麻', 233.0),(u'祖母', 218.0),(u'耶観', 191.0),(u'栄', 146.0)

それっぽい単語がキーワードとして抽出できているかなと思います。
やはり、タイトルの名詞や主人公の名前がセグメントに寄与してるようです。
また、黒衣聖母の「麻利耶観音」はどうやら形態素解析で、
「麻」と「利」と「耶観」と「音」にわけられてしまってますね・・・

所感

今回用いたセグメンテーション手法の特徴を挙げてみると、

・事前学習用データを一切使わない
・利用した単語は名詞のみ
・セグメント間の非類似度などは考慮していない
・スコア計算も至ってシンプル

と比較的お手軽な方法ですが、割と良い感じにセグメンテーション出来てるのかなと思います。
まぁ、別々の文章を無理やりくっつけて、さぁわけろと言ってるので、
うまい具合にできてもらわないと、困ると言えば困るのですが・・・

この手法の欠点を挙げると、kT^2オーダーの計算量なので、
長い文章だとかなり時間がかかります。
また、トピック分析をしてるわけでもないので、
各セグメントがどの話題について言及してるかは、見ることができません。
上記のように、セグメント内で共通する単語とかを見れば、
それなり話題が見えますが、やっぱり微妙かなと思います。

と言う訳で、pLSIやLDAなどの潜在トピックモデルを用いたセグメンテーション手法も
いずれは試してみたいと思います。