古い記事
ランダムジャンプ
新しい記事
カイ2乗値を使って単語間の関連度を調べる方法。
つまり、関連語を探すときに、χ二乗値を関連度として使う。

perl によるサンプルコード (chiword.pl)。昔、勉強がてら作ったコード。
#!/usr/bin/perl
use strict;
use warnings;

my %cnt;
my $pair_num;

while (<>) {
    chomp;
    next if /^\s*$/;
    my @list = sort split(/,/, $_);
    for (my $i = 0; $i < @list; $i++) {
        for (my $j = $i + 1; $j < @list; $j++) {
            next if $list[$i] eq $list[$j];
            $cnt{word}{$list[$i]}++;
            $cnt{word}{$list[$j]}++;
            $cnt{pair}{join("\t", sort $list[$i], $list[$j])}++;
            $pair_num++;
        }
    }
}

my %chi_square_value;
foreach my $p (keys %{$cnt{pair}}) {
    my ($w1, $w2) = split(/\t/, $p);
    my $o11 = $cnt{pair}{$p};
    my $o12 = $cnt{word}{$w2} - $o11;
    my $o21 = $cnt{word}{$w1} - $o11;
    my $o22 = $pair_num - $cnt{word}{$w1} - $cnt{word}{$w2} + $o11;
    my $n = $pair_num;
    $chi_square_value{$p} = ($n * ($o11*$o22 - $o12*$o21)**2) /
        (($o11+$o12)*($o11+$o21)*($o12+$o22)*($o21+$o22));
}

foreach (sort {$chi_square_value{$b} <=> $chi_square_value{$a}}
         keys %chi_square_value) {
    print "$chi_square_value{$_}\t$_\n";
}

χ二乗値は下記の式で計算する。
chi

添え字つきの O (オー) はプログラム中では $o11, $o12, $o21, $o22。

例えば、単語 cow と vache について考える。
対象のデータに対して、
それぞれが単体で現れる頻度、共起する頻度、どちらも表れない頻度を
カウントしたのが下記の表。

cow!cow
vache596
!vache8570934

cow と vache が同時に現れるドキュメントの数 ($o11) は 56。
cow は現れるが vache は含まれていないドキュメントの数 ($o21) は 8。
その逆のドキュメントの数 ($o12) は 6。
どちらも含まれていないドキュメントの数 ($o22) は 57930。

この4つの値でχ二乗値が計算できるというわけ。

以上、式の説明は、
"Foundations of Statistical Natural Language Processing" より。


さて、下記のサンプルデータ (chiword-samp.txt) でプログラムを実行。
1行1ドキュメント。フォーマットは CSV。
各行には、同じドキュメントに現れた単語が含まれている。
ドキュメントに現れた単語がカンマ区切りで並んでいると考えれば良い。
hello,this,is,a,pen
i,love,a,pen
i,have,the,pen,with,love
the,cat,with,love
this,pen,is,hello
this,pen,is,mine
a,pen,is,love

これを chiword.pl にかけると、つながりの強い順に単語ペアが出力される。
% ./chiword.pl chiword-samp.txt
2.83051588365177        is      love
2.61597458132189        pen     the
2.61597458132189        pen     with
2.23322255731561        love    pen
0.901101336606656       cat     with
0.901101336606656       cat     the
0.823194884563151       the     with
0.7703081232493         have    pen
0.689179927290065       i       pen
0.582010582010582       hello   this
0.55                    a       this
0.489672364672365       mine    this
0.396299545459209       is      pen
0.346638655462185       a       pen
0.346638655462185       pen     this
0.313854708550087       hello   pen
0.274216524216524       is      this
0.203161938534279       a       i
0.191637630662021       a       love
0.165304780689396       is      mine
0.131648936170213       have    i
0.131648936170213       have    the
0.131648936170213       have    with
0.108227585906157       hello   is
0.103803716608595       cat     love
0.0895400895400895      a       is
0.0862369337979094      have    love
0.0818452380952381      a       hello
0.031602384543561       mine    pen
0.0315117134449977      i       the
0.0315117134449977      i       with
0.00101934909926607     love    the
0.00101934909926607     i       love
0.00101934909926607     love    with


参考:
Christopher D. Manning and Hinrich Schutze, Foundations of Statistical Natural Language Processing, MIT Press. Cambridge, MA: May 1999.
[2006-04-11-2]

相互情報量を使う場合はこちらを参考に。
- [を] Blog Hackers Conference 2005[2005-05-27-1]

手軽にシンプソン係数[2006-03-08-2]でもよいかも。


追記070920: 数式まわりの解説を追加した。
追記140109: プログラムに間違いがあったため全面改訂。出力結果を head してたのをやめて全部出した。