LSA(latent semantics analysis)ともいわれる。 語彙の共起パタンによる語及び文書の分類もしくは概念空間の抽出技法。
まぁあれだ。要するに、そういう意味空間が線形だと仮定するところに そもそも無理があるんだけど、とりあえずここはそういう事にして。
線形だとすると、基底に分解できるのは当然で、 その操作は線形代数でいうところのスペクトル分解あるいは 特異値分解なわけですよ。 空間は基底の線形和で必要十分に表現できるわけですな。
とはいえ、基底を人間が解釈するとして、 さきに述べたような算術操作である以上 つねに自明な、あるいは有意味な解釈があるとは限らないわけで (これは主成分分析なんかと共有する問題ですな)、 そういう場合にぶち当たってしまった場合にどうするか、 というのは難しいですよね。 というかむしろどうしょうもないですよね。わはは。
そこで、俺は次のような手口を試してみましたよ。
よくありますよね、最初の生物が居て、ある時期にそれから魚がうまれて、 しばらくしてからハチュウ類がうまれて、ずっとあとになって猿ができて そこから人間が分かれた、みたいな。そういう話。
画にすると2分木になるわけです。n種類の生物が居たとして、 その分化は何とおりあるか？というと、これは n個の末端を持つ2分木は何とおりあるかという問題と同型ですが、 あきらかに factorial のオーダーになります。
n種類の生物の系統樹を考えるというのは、 だから、これだけを考えると計算機でやるのは不可能に思えるわけですが、 そこで諦めたらあきません。
魚と蛇と猿と人が居たとして、どれが最後に分化したか、 というと、そりゃ猿と人でしょう、という話になるわけです。 まぁ具体的に比べようとすると、比較可能な尺度をもってくるしかない。 その尺度は、 かならずしも整列可能集合上にそういう尺度がマップされている必要はないわけですが、 整列可能なら全部比較可能ですから、どれとどれが近いとか遠いとかいう話は できます。 もう面倒なので、大抵はその尺度が実数だったりするわけです。 最近流行りなのはなんといっても遺伝子で、 「遺伝子の配列の違いなんかを尺度にして計算してみたらこうなった」 みたいな結果が Nature とかに載ったりするわけです。
そこでは案外意外な結果が出たりするんですが、 それもどこの遺伝子を使うかでけっこう違ってたりするわけで、 ただちにどれが本当でどれが嘘、という事にもならないわけですが、 そもそもの発想としてはある程度自然で、しかも面白いものがありますよね。
だから、そいういう処理をするアルゴリズムにはどういうものがあるのか、 つまり factorial の罠をくぐりぬけて系統樹を生成するものにはどういうものが あるのか？というところが面白そうでちょっと調べてみましたよ。
ちなみに Nature vol. 320 27 の 1763 なんかは 鳥類の分類をやってみました、という一時期話題になった論文で、 (まえの研究所に居た時は読めた 笑) 葉ノード数169に対して計算を行っています。
いくつかあるアルゴリズムのうち、 とりあえず neighbour joining 法というのが簡単そうだったので、 実装してみました。こんな感じ
class Array
def n_j(nlist=Array.new(self.length){|i|i})
while self.length > 2
r=self.length
p nlist, r
rsum=self.map{|row|row.inject(0){|ret, v|ret+=v}}
qm=nil; qix, qiy =0, 0
q=self.map_with_index{|row, i|row.map_with_index{|c, ii|
if i == ii
ret= 0
else
ret= (r-2)*c - rsum[i] - rsum[ii]
end
if qm.nil? or ret < qm
if i != ii
qm= ret; qix, qiy = i, ii
end
end
ret
}}
qix, qiy = qiy, qix if qix > qiy
nlist[qix]= [nlist[qix], nlist[qiy]]
nlist.delete_at(qiy)
dfu=self[qix][qiy]/2.0 + (rsum[qix] - rsum[qiy])/(2*(r - 2.0))
dgu=self[qix][qiy]/2.0 + (rsum[qiy] - rsum[qix])/(2*(r - 2.0))
nd= self[qix].map_with_index{|v, i|(v - dfu)/2.0 + (self[qiy][i] - dgu)/2.0}
nd.delete_at(qiy);
self.delete_at(qiy);
self.each{|r|r.delete_at(qiy)};
self[qix]= nd;
self.each_with_index{|r, i|r[qix]=nd[i]}
end
nlist
end
end
距離行列(array の array)のメソッドとして実装しました。 引数は名前(種名とか)のリストで、引数ナシで index のリストが入ります。 出力は、ネストしたarrayで表現されるバイナリツリーで、 葉ノードは引数であたえた名前が入ります。使い方はこんな感じ。
irb(main):003:0> [[0, 1, 2, 3], [1, 0, 2, 3], [2, 2, 0, 1], [3, 3, 1, 0]].n_j(["ひと", "さる", "へび", "魚"]) ["ひと", "さる", "へび", "魚"] 4 [["ひと", "さる"], "へび", "魚"] 3 => [[["ひと", "さる"], "へび"], "魚"]
計算の進行が見えた方が面白いので、 そういう実装になっています。 まずは人と猿が分岐しただろ、だからそれをひとまとめにしちゃえ。 そうやった分類について、種類間の距離を計算し直して、 次は猿族と蛇が分岐しただろう、という話になって、 最後に(というか時間の流れとしては最初に)魚が分岐しただろう、 という計算方式です。 ひとまとめにして仮想的な種(猿族とか)をこしらえたあとの 距離行列の計算については、面倒なのでコードを見て下さい。
これは、分類上、一番最近に分岐したやつが、一番、距離が近いだろ、 という仮定に基づいた処理ですな。 これは greedy なアルゴリズムなので、かならずしも最適な系統樹がえられるとは かぎらず、 local minima に陥るおそれもあるわけで、 それに対していろんな改良というか検討がなされているそうですが、 それなりに良い感じの系統樹が今のところ得られています。 先の Nature の論文では 169種についての分析ですが、 上記の Ruby コードでも970種の分類が2時間くらいでできました。 変数qiのインデクスをいちいち参照しているのを、独立な変数に 割り当てたら、多少速くなるかもです。 (最初の版は再帰で書いたのでメモリが途中で足りなくなって死にましたw)
なお、上記コードは破壊的メソッドで元のデータは計算の進行とともに 書き変わります。元データは再帰的に dup するか、どっかにダンプするとかして とっておいたほうがいいかもです。
Tue Jun 02 17:27:28 2009 追記、某ハードウェアハカーより 行列が対称でないとの指摘をうけ訂正しました。ありがとうございます。