TF-IDFとは
よく知らんが文章中の単語の重要度を測る指標らしい。
なぜTF-IDFなのか
一番簡単そうだったから。実装に時間がかからなそうな気がしたので。
材料
- MeCab
- bash
- awk
作り方 捕捉
一応並列処理屋さんのはしくれなので並列処理をしました。
文章の単語のリストを作る
作り方はかんたんに言うと
TF=[cat 文章|MeCab|sort|uniq -c]を作ります
こんな感じ
cat 文章 | 前処理 | MeCab | sort | uniq -c | awk -f tf.awk > TFの一覧
{
c = "" ; for(i=2;i<=NF;i++) c=c $i" "
DIC[c] +=$1
}
END {
for (str in DIC) N+=DIC[str]
for (str in DIC) printf "%10.9f %s\n",DIC[str]/N,str
}
要するに、uniq -c の処理で出て来た出現回数 単語の詳細という列を取り出しそれを基にTFを求めます。
一例を出すとするとこんな感じ
12928 ある 助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
この集合を単語帳TFとします。
次に、
DF=[cat 文章 | MeCab|sort|uniq]で得られる各文章の単語一覧を単語帳TFで出て来た単語と照らし合わせて単語帳TFに出て来た単語と一致するものをカウントしていきます。
ここで並列化をします。対象になっている文章ファイルたちを並列で処理します。こんな感じ
find ${文章の入っているディレクトリ} -name \*.txt | xargs -I {} -P 並列数 TF計測プログラム {}
そしたら、単語帳TFに入っている単語一覧を並列数でsplitします。
split -n l/並列数 単語帳TF tfidf_tmp.
こうすると並列数の数に分割されたファイルができます。
あとは、DFを計算するためにもう一度並列化します。
find ./ -name tfidf_tmp.\* | xargs -I {} -P 並列数 ./tf-idf_p {} 全文章の一覧 一時ファイル置き場
こうすることで、一時ファイル置き場に全文章から単語帳TFに記載されているものと一致した単語が記載されたファイルが書かれるようにします。
あとは、
while read FILE
do
cat < ${FILE} >> DF一覧
done <一時ファイル置場にある一時ファイル
ビバ!!連想配列
ここで連想配列が効果を発揮してくれます。
たとえば、
11228 自分 名詞,一般,*,*,*,*,自分,ジブン,ジブン
の様に「出現回数 単語」の順で並んでいるデータを扱っていきます。
while read LINE
do
l=$(echo ${LINE} | cut -d " " -f2-)
df=$(echo ${LINE} | cut -d " " -f1)
DF["${l}"]=${df}
done < ${TMPFILE}
ご覧になればわかるかと思いますが、連想配列のインデックスは単語で、その持つ値は全文章での出現回数になります。
これを単語帳TFの単語とすると、こう計算されます、
TF=単語帳TFの持っているTF
DF=単語帳TFの持っている単語と一致したDF(連装配列で取ってくる)
N=総文章数
TFIDF=TF×log((N+1)/(DF+1))
DF+1はDFが0の時除算できないのを防ぐためです。
これでTF-IDFが計算できます。時間は青空文庫
に登録されている文章全体とその文章からひとつ適当に選んだ文章をつかって計算させると
Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
を使用して8並列で行った時に
Making TF-IDF from 17161 Text file(s)(8 proc(s)).
real 15m21.721s
user 109m8.239s
sys 7m32.863s
となりました。チャンチャン、ではないのです。
これで終わりだと思うなよ。AWK満載のTF-IDFの作り方。
先の方法でもまぁまぁ速いですが、もう少し頑張ってみます。
AWKでもう少し早くならんかなぁと思ったので、書いてみました。
やっぱりビバ!!連想配列
ここでも連装配列が役に立ちます。
#!/usr/bin/awk -f
{
str = "" ; for ( i=2 ; i <= NF ; i++ ) str = str" "$i
MOR[str]+=$1
}
END {
for ( str in MOR ) N += MOR[str]
for ( str in MOR ) printf "%10.9f %s\n", MOR[str]/N,str
}
前半部分で単語と詳細な情報をすべて半角スペースで区切って書き出します。もちろん値はuniq -cで取ってきた値を入れておいてENDの部分で連装配列による加算をしています。
これを応用すると素晴らしく簡単にいろいろ書けます。
まずは、DFの求め方。
#!/usr/bin/awk -f
BEGIN {
while ((getline < "/dev/stdin") > 0) {str =""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i;WORDS[str]=0;}
for ( arg in ARGV ){ while ( ( getline < ARGV[arg] )>0){str = ""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i; if (str in WORDS){WORDS[str]+=1;}}}
for ( word in WORDS) printf "%d %s\n",WORDS[word],word
}
標準入力から単語帳TFのデータを取得し、DFの計算に使います。そして引数に全文章を羅列する様にします。どうやるかは以下の通りです。
split -n l/並列数 単語帳TF 一時フォルダ/target.part.
find 全文章が入ったフォルダ -name \*.txt -type f | xargs -I {} -P 並列数 ./bin/mkwords {}
find 一時フォルダ -name target.part.\* -type f | xargs -I {} -P 並列数 ./bin/dfpart {}
#!/bin/bash
cat 文章ファイル | mecab | sort | uniq > $(mktemp 一時フォルダ/words.XXXXXX.txt)
#!/bin/bash
cat 単語帳TF | ./bin/df.awk $(find 一時フォルダ -name words.\*.txt) > $(mktemp 一時フォルダ/dfparts.XXXXXX.txt)
そしてdf.awkで連装配列を使ってデータを取りまとめます。
#!/usr/bin/awk -f
BEGIN {
while ((getline < "/dev/stdin") > 0) {str =""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i;WORDS[str]=0;}
for ( arg in ARGV ){ while ( ( getline < ARGV[arg] )>0){str = ""; for ( i=1 ; i <= NF ; i++ ) str = str" "$i; if (str in WORDS){WORDS[str]+=1;}}}
for ( word in WORDS) printf "%d %s\n",WORDS[word],word
}
ざっとこんな感じです。これを実行すると…。
Calc TF-IDF from 17161 files in 8 parallels.
real 6m2.957s
user 42m19.169s
sys 3m41.690s
ほら、短くなった。速くなりましたね。
まだまだ改良の余地はありますが、最初1日でも終わらない気がしていた15000オーバーの文章からのTF-IDFの計算が10分もしないうちに終えることができるなんて夢にも思っていませんでした。
ちなみに、ここまで到達するに何日かかかりました。orz
今回のミソは、
単語帳TFを分割して並列化させたところ
です。
何故かというと、照合する文章群を分割したところで、その後のマージに時間がかかるからです。
単語帳TFのデータを分割したら、各文章から出来上がるDFのパーツをあとでマージするときに、
while read FILE
do
cat < ${FILE} >> ${DF}
done < DFの元ファイル群
だけで済むからです。
改良したらまた書きます。もう少し速くできるかと思います。
まだだ、まだ終わらんよ
実行していて気がつきました。後半の処理より前半の処理に時間がかかっていることを、
そこで、ちょっと計測しました。
プログラムはこんな感じ
#!/bin/bash
LIST=$(mktemp)
find ${1} -type f -name \*.txt > ${LIST}
./test2.sh ${LIST}
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
#mecab -b $(wc -c ${tmp}) ${tmp} > /dev/null #|sort|uniq >/dev/null
done < ${1}
この実行時間は
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.iTu7SpdAD0
real 0m20.389s
user 0m11.735s
sys 0m8.602s
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
mecab -b $(wc -c ${tmp}) ${tmp} > /dev/null #|sort|uniq >/dev/null
done < ${1}
この実行時間は
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.tGDGBx3rnZ
real 3m30.766s
user 2m35.250s
sys 0m57.698s
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
mecab -b $(wc -c ${tmp}) ${tmp} |sort >/dev/null #|uniq >/dev/null
done < ${1}
この実行時間は
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.26ap8fTWtw
real 33m39.201s
user 32m52.530s
sys 1m24.546s
あひゃ、ってことは…
ソートに相当時間がかかっていました
もう、uniqやるまでもないですね、たぶん。これ以上時間を費やさないためにも、このsortコマンドをなんとかせにゃなりません。
そこで考えました。
「必要なのはソート機能ではなくてこの文章でユニークな形態素示す機能である」と。
ですので、sort|uniqに変わる機能をAWKで作成しました。
それが、これです。もうお馴染みですよね？
#!/usr/bin/awk -f
BEGIN{
while((getline < "/dev/stdin") > 0)
{
str = $1"\t";
for(i=2;i<=NF;i++)
{
str = str $i" ";
}
UNIQ[str]+=1
}
for( str in UNIQ )
{
printf "%s\n",str;
}
}
これで実行してみましょう。
さきほどのスクリプトを改造してこうします。
#!/bin/bash
tmp=$(mktemp)
wc -l ${1}
while read FILE
do
iconv -f SHIFT_JISX0213 -t UTF-8 ${FILE}> ${tmp}
mecab -b $(wc -c ${tmp}) ${tmp} |./uniq.awk >/dev/null
done < ${1}
…、さて、実行時間は…？
$ time ./test.sh aozorabunko_text-master/cards/
17161 /tmp/tmp.XbLP8OousD
real 3m39.679s
user 4m41.474s
sys 1m9.672s
おぉ、10倍くらい速い。
ってことでsortコマンドは捨てawkスクリプトに交換してTF-IDFを再度計測。
$ time ./tfidf
Calc TF-IDF from 17161 text file(s) in 8 proc(s).Temp dir is /tmp/nlp.zaawXQG
real 1m54.402s
user 10m53.186s
sys 3m33.032s
あひゃ、3倍近く速くなった。ってことでだいぶ速くなりました。