豪鬼メモ

一瞬千撃

k-means法による英単語クラスタリングの改良

k-means法で英単語をクラスタリングして、「連想英単語集」を作ったという話を前回したが、そのアルゴリズムを改良して精度を向上させた話。主に疎な特徴量に起因する問題を解決すべく、特徴量フィルタ、レベリング、総当り置換、k-means++法を導入した。

特徴量フィルタ

英単語の特徴を表すのに、WordNetから抽出した類義語と日本語WordNetから抽出した訳語とWebコーパスから取得した共起語を使っている。いずれも、かなり疎な特徴量となる。すなわち、同じ特徴量ラベルを共有する語が無かったり少なかったりして、行列として表現するならほとんどの要素がゼロになってしまう。

真面目に次元削減みたいなことを考えると結構面倒くさそうだ。なので、非常に手抜きしたヒューリスティックを考えた。その特徴量ラベルを持つ語数が、各クラスタ内が含むべき要素の数に近いほど識別力が高いと考えるのだ。例えば、10000語を1000クラスタに分けるなら、1クラスタは10語を含むことになる。そうすると、もしその10語だけに現れる特徴量ラベルがあるなら、寄与率は大きい傾向にあるだろう。S回をその理想値として、N回を実際の出現回数すると、abs(log(N/S)) が小さいほど良いとみなしてもよさそうだ。

実際の特徴量の値は1と0のバイナリではなく、共起率やIDFなどから算定した0から1までの実数値を持っている。クラスタリングの計算中に全てのデータを使うと遅すぎるし、ノイズをたくさん読ませても精度に貢献しないので、個々の語で値が上位40位までのものを代表として用いる。特徴量の値に想定寄与率の重み 1 / (abs(math.log(n/s)) + 1) を書けた値の上位40位を採用したいわけだが、その想定寄与率は上位40位の選択によって決まるという循環依存関係があるので、上位100位、上位60位、上位48位、上位40位と狭めながら特徴量を絞り込んでいくことにした。また、全体で1語にしか現れない特徴量ラベルはクラスタリングには全く無意味なので無条件で削除する。結果として、以下のような特徴量が抽出できた。

  • earch : ground=1.000, world=0.895, land=0.831, globe=0.690, worldwide=0.560, soil=0.545, ...
  • moon : month=1.000, idle=0.933, lunation=0.825, daydream=0.776, exhibit 0.665, satellite=0.664, ..
  • pizza : hut=1.000, restaurant=0.934, domino=0.882, dish=0.877, cheese=0.792, pizza pie=0.783, ...
  • jump : spring=1.000, bound=0.883, leap=0.862, skip=0.822, rise=0.732, hop=0.709, move=0.708, ...
  • beat : pulse=1.000, defeat=0.949, overcome=0.850, exceed=0.848, pound=0.815, move=0.808, ...
  • love : sex=1.000, fuck=0.701, darling=0.690, eros=0.619, honey=0.548, mate=0.541, cherish=0.529, ...

いずれも、特徴量ラベルのリストだけ聞けば元の単語を言い当てられる程度には妥当な感じがする。値は最大値が1になるように正規化している。実際のTSVデータはこちらに置いておく。

レベリング

有効な特徴量が抽出できたら、あとはk-means法をぶん回すことになるのだが、疎な特徴量であることでまた別の問題が出てくる。k-means法のイテレーションの途中で、特定のクラスタに要素が集中したり、要素が空になるクラスタが出現したりする問題がある。多くの語と共通した特徴量を持つハブとなるような語が集まってクラスタを作ってしまうと、次のイテレーションで非常に多くの要素がそのクラスタを選択してしまう。また、少数の語でしか通用しない特徴量を持つクラスタは、次のイテレーションでも選択されにくい。

大きすぎるクラスタを分割する方法も考えたが、それはもはやk-means法ではなくなってしまう。それよりは、そもそもクラスタが大きくなりすぎないようにペナルティをかけることを考えた方が良い。ところで、今回のアルゴリズムでは、クラスタと要素の距離の判定にコサイン距離を用い、それを1から引いた値を「類似度」として、個々の要素にとって類似度が最高のクラスタを選択するようにしている。クラスタ間で次元が異なる場合でも比較できるからだ。さて、各クラスタが含むべき要素の数のSとした場合、各クラスタの下位S件の要素の類似度を算出して、その平均を次のイテレーションの際の個々の語のコストの重みにする。大きいクラスタほど、下位の要素は類似度が低くなる傾向にあるので、これでうまいこと負のフィードバックがかけられる。

空のクラスタができてしまった場合、特徴量が算出できなくて以後のイテレーションで空になり続けてしまうことになる。それだと困るので、毎回のイテレーションで、前回のイテレーションで使った特徴量と現在の要素から抽出した特徴量を混ぜることにした。前回から0.2、現在から1の割合で合成する。これによって、空になった場合でも過去の特徴量を使って復活できるし、上述のペナルティとも相性が良い。

とはいえ、いかなる重み付け方法をもってしても、各クラスタのサイズを常に同じにすることはできない。しかし、単語集である以上、各章の収録語数は同じにしたいし、章ごとに意味のまとまりがある方が使いやすいから、最終的には各クラスタのサイズを同じにしたい。

最終的に帳尻を合わせるには、上位S件から溢れた要素の各々について、現状のサイズがS以下のクラスタで類似度が最も高いものに強制的に移住させればよい。しかし、この方法にも課題がある。例えば、Sが3で、「blue」「green」「red」「white」という色関係のクラスタと、「movie」「theater」「actor」「film」という映画関係のクラスタと、「camera」「lens」というカメラ関係のクラスタがある場合に、「white」と「film」を強制移住させるとする。「film」はカメラ関係のクラスタに入れたいところだが、「white」の方が先にそこに入れられてしまうかもしれない。「film」の方を先に解決すればマシになるだろうが、それをどう判定するかが問題だ。余剰要素と空きクラスタの可能な組み合わせとその類似度を全て列挙して、類似度の合計が最高になるように計らうことが考えられる。それでも、既にクラスタに入れられた要素を入れ替えることはしないので、全体最適には程遠い。

とりあえず、簡単に実装できる方法を採用した。余剰要素と空きクラスタの全ての組み合わせで類似度を算出し、類似度でソートして、先頭から可能なものを適用していく。これだと総計を追求にすることにはならないが、現実的な計算量で済む範囲ではマシな方だろう。

上述のレベリング処理によって、全てのクラスタが同数の要素を持つことを保証できるようになったが、精度は犠牲になっている。余剰要素の既存クラスタへの再分配を行っても、既存クラスタの再クラスタリングは行わないからだ。10000語のクラスタリングをする場合、全要素の30%くらいは余剰要素になるっぽいが、それらの精度がいまいちなのはもったいない。ならば、十分な規模になったクラスタを凍結した上で、余剰要素と残りのクラスタの要素でk-meansのイテレーションを継続すればよさそうだ。それでも余剰要素は出るのだが、もともとの余剰要素の数よりは少なくなる。よって、段階的に凍結を行えば、最終的に余剰要素の数を非常に少なくすることできる。

思いつきのヒューリスティクスにに最適解を求めてもあまり意味がないので、以下のようなスケジュールをハードコードした。

これで、強制移住される要素は3.75%にまで減ることになる。4%くらいの語は、どのクラスタに入れても違和感が残るボッチ語なので、仕方ないと割り切る。ボトムアップ型のクラスタリングアルゴリズムであればボッチが発生することはないのだが、その反面、「大して仲良くない人たちを無理やりくっつけてる感」が出てしまうので、痛し痒しだ。章ごとの語の類似度を最大化するという観点では、k-means法の方が優れている。

総当り置換

レベリングと強制移住の結果として各クラスタの下位の語の精度は悪化する。これを少しでも改善すべく、クラスタの要素数と特徴量を固定したまま、クラスタ間で要素を交換する処理を実装した。各クラスタにおいて各要素の重心からの類似度を測定しておき、それが別のクラスタに移動した際のそのクラスタでの重心からの類似度も計算する。任意の二つの要素をクラスタ間で交換した場合に、元の類似度の合計よりも新しい類似度の合計の方が上回る場合、交換を行った方が全体最適に寄与すると考えられる。そこで、各要素に対して交換可能な全ての組み合わせを列挙した上で、最も差分の大きいものを選択する。バーター経済による功利主義の実現である。

言うのは簡単だが、この処理の計算量はエグい。全体の要素数をNすると、O(N^2) となる。10000語のクラスタリングであれば、1億回の比較が必要になる。実際にはABを比較すればBAの比較は必要ないので、半分の5000万回になる（同じクラスタ内の要素とは比較しないので、それよりもちょっと小さくなる）。類似度の計算はクラスタ内の特徴量の数に比例するが、それは160なので、80億回のテーブルルックアップが発生することになる。これは流石に遅すぎるので、各クラスタにおいて類似度が下位の定数個だけを扱うようにする。そうすれば、計算量はクラスタ数をNとした O(N^2) に改善する。1000クラスタの下位3個ずつを扱うなら、3000^2 / 2 で900万回の比較で済む。テーブルルックアップは14億回くらいか。それでも遅いが、最近のマシンならなんとかなるレベルだ。

総当り置換の結果としてもクラスタの内容が変わる。また特徴量を計算しなおして、総当り置換を繰り返せば、各クラスタの規模を保ったまま収束が目指せる。ただ、遅い割には効果が薄いので、10回くらいのイテレーションで切ってしまうことにした。

k-means++法

k-means法の欠点は、初期値によって最終結果が大きく左右されることだ。例えば、「alcohol」が飲み物関係のクラスタに入るのか、化合物関係のクラスタに入るのかは、先にどちらのクラスタが発生するかによる。あるいは、どちらのクラスタも発生せずに、余剰要素として仕方なく関係の薄いクラスタに入れられてしまうかもしれない。それは全て初期値によって決まる。旧来の実装では各クラスタの初期値は、インデックスの剰余で適当に選んだ要素の特徴量を合成することで生成していた。したがって、運悪く、明確な特徴のない初期クラスタが多数生成されてしまうと、最終結果も芳しいものではなくなる。

k-means++法では、k-means法とほぼ同じアルゴリズムだが、クラスタの初期値の設定方法に改良がなされている。すなわち、クラスタの初期値を設定する際に、全要素の中から互いに離れたものをクラスタの数だけ選び、その特徴量をクラスタに設定するのだ。要素をまず一つ乱択し、既存の選ばれたどの要素よりも遠いものを距離で重み付けしながら次の要素を乱択する処理をクラスタの数だけ繰り返す。ランダム性を導入するのは外れ値に対する耐性のためらしい。

今回はそれを少し改変する。最初に要素を特徴量の想定寄与率の合計でソートする。つまり、識別能力が高い特徴量を多く備えていそうな要素が上位に来る。その上位の中から、クラスタ数の定数倍（4倍とか）の要素を取り出す。それらは、ハブとなるような語だ。異なる意味のハブになる語がたまたま同じクラスタに入ってしまうと厄介であることは既に述べた。よって、ハブになる語の中からk-means++法と同じようにクラスタの初期値を選んでやれば、ハブの重複のない初期クラスタが設定されるはずだ。また、外れ値は事前に取り除かれるだろうから、乱択もしない。1位の要素を最初に選び、それと最も遠いものを次に選び、それらと最も遠いものを次に選び、というのを繰り返す。

k-means++の計算量は、候補となる要素数Nとクラスタ数Mに対して O(NM) になる。上述のように、候補となる要素をMの定数倍にすることでO(M^2)にはなるが、それでもまだ遅い。今回の場合、距離として扱われるベクトル間の類似度の計算が遅いので、愚直に1000クラスタとかを初期化しようとすると、現実的な時間で終わらない。よって、ここでも簡便法を用いる。直近に確定した100個のクラスタの初期値を合成したベクトル空間と、個々の候補の要素の類似度を取ることで、既存のクラスタ全てとの距離の合計の近似値とする。クラスタを確定する度にベクトルの合成をやると遅いが、ローリングハッシュ的に、101個前のクラスタの特徴量を引くことで高速化できる。結果として、多少精度は悪化するが、計算量は O(M) になる。

結果

上述の全てを適用して、重要英単語3200語を200クラスタに、重要英単語9600を400クラスタにそれぞれ分類してみた。k-meansのイテレーションは200回、総当り置換のイテレーションは10回行った。このTSV（3200）とこのTSV（9600）が結果だ。いくつか抜粋しよう。

  • anniversary, birthday, today, tomorrow, yesterday, day, afternoon, even, holiday, overnight
  • window, weekend, decade, school, tide, week, century, reign, past, dawn
  • copy, reproduce, double, repeat, twice, dual, clone, fork, multiple, triple

k-means++法の適用により、雑多な語が混じった「駄目クラスタ」みたいなのは発生しにくくなった印象がある。特徴量フィルタの効果はよくわからないが、少なくとも悪影響はなさそうだ。そして、レベリングの工夫と総当り置換によって、各クラスタのサイズを合わせつつも、クラスタ内の下位の語の納得感が多少上がった気がする。とはいえ、クラスタを同じサイズにするという制約は厳しすぎて、焼け石に水な感はある。

3200語と9600語の結果を比較すると、9600語の結果の方がよくできている感じがする。候補となる語が多い方が類義語を探しやすいので、当然といえば当然だ。また、3200語の方は1クラスタあたり16語だが、9600語の方は1クラスタあたり24語なのも効いている。k-means方をはじめとするトップダウンのクラスタリング手法では、類義語の集合を確実に見つけ出すというよりは、ざっくり意味が似た語の集合を集めるのに向いている。その意味では、クラスタの粒度が細かすぎない方がよい。1クラスタあたり24語というのは絶妙な設定だろう。

この結果を使って連想英単語集も作り直してみた。個々の章の意味のまとまりが良くなったことで、だいぶ覚えやすさが向上した気もする。

とはいえ、そもそも、クラスタのサイズを同じにしなければいいのではと思い始めてきた。あと、レベリングはヒープ木を使えばもっと簡単にできそうだと今気づいた。