カイ二乗値で単語間の関連の強さを調べる

カイ２乗値を使って単語間の関連度を調べる方法。
つまり、関連語を探すときに、χ二乗値を関連度として使う。

perl によるサンプルコード (chi.pl)。昔、勉強がてら作ったコード。

#!/usr/bin/perl
use strict;
use warnings;

my (%pair_OX, %pair_XO, %pair_OO);
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];
            $pair_OX{$list[$i]}++;
            $pair_XO{$list[$j]}++;
            $pair_OO{$list[$i]."\t".$list[$j]}++;
            $pair_num++;
        }
    }
}

my %chi_square_value;
foreach my $p (keys %pair_OO) {
    my ($w1, $w2) = split(/\t/, $p);
    my $o11 = $pair_OO{$p};
    my $o12 = $pair_XO{$w2} - $pair_OO{$p};
    my $o21 = $pair_OX{$w1} - $pair_OO{$p};
    my $o22 = $pair_num - $pair_OX{$w1} - $pair_XO{$w2} + $pair_OO{$p};
    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";
}

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


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

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

	cow	!cow
vache	59	6
!vache	8	570934

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

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

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


さて、下記のサンプルデータ (chi.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

これを chi.pl にかけると、つながりの強い順に単語ペアが出力される。

% ./chi.pl chi.txt | head
12.1933962264151        the     with
6.78237961851407        hello   is
6.46555555555556        pen     this
5.20576131687243        is      mine
4.58333333333333        a       hello
4.20283018867925        have    i
2.93572984749455        a       is
2.57450599287334        love    the
2.57450599287334        i       love
1.66062801932367        is      this

"the" と "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: 数式まわりの解説を追加した。