Asial Blog

Recruit! Asialで一緒に働きませんか?

「似ている」を探そう

カテゴリ :
バックエンド(プログラミング)
タグ :
Tech
形態素解析
MeCab
コサイン類似度
類似度
今日から8月ですね!我が家の猫も夏毛に生え替わるようで、私も毛だらけです。志田です。

さて、今回は「似ている」を探したいと思います。なにかとなにかがどのくらい似ているのか、という情報があれば、それが役に立つシーンはたくさんありますよね。
ブログの似ている記事を探したり、趣味の似ているユーザを探したり、用途は様々です。
「何が似ているのか」という尺度にも様々あるように、類似度というのはいろいろな観点から調べることができます。

今回は、アシアルブログから似ている記事を探してみたいと思います。
手順としては、Mecabというライブラリを使って記事を形態素解析し、単語に分けます。
そして、元となる記事とその他の記事全体を見て、コサイン類似度という手法を用いて記事同士の類似度を測定し、似ている記事を3件見つけます。

(1) ブログ記事を取得する


ブログ記事を取得し、ディレクトリに保存しておきます。
アシアルブログですと、URLの後ろについた番号が記事のIDとなっているので、entry/ID.htmlというような形式で保存しました。総数757件!
結構な量だったので、50件ずつダウンロード保存しました。(門脇さん、ブログに負担がかかってたらゴメンナサイ…)

(2) ブログ記事から本文をスクレイピングする


先ほど取得したブログ記事には、HTMLヘッダや再度メニューなど、類似度の分析に必要のない部分まで含まれています。
これを、本文だけ取得(スクレイピング)していきたいと思います。
また、ソースコードが含まれていると「if」「$i」といった構文が多く出現して本文の類似度に結びつかなくなると考え、ソースコード部分も省くことにしました。

  1. include('parser/simple_html_dom.php');
  2. for($i=1; $i<839; $i++){
  3.   $file = "entry/$i.html";
  4.   if(is_file($file)){
  5.     $html = file_get_html($file);
  6.     //本文抜き出し
  7.     $div = $html->find('div[class=item-paragraph]');
  8.     $string = $div[0]->outertext;
  9.     //本文からソースコードを消す
  10.     $div = $html->find('ol[class=boxcode-main]');
  11.     foreach($div as $d){
  12.       $string = str_replace($d->outertext, '', $string);
  13.     }
  14.     //ファイルに保存
  15.     file_put_contents($file, $string);
  16.   }
  17. }

HTMLのパースには、PHP Simple Html Dom Perserを利用しました。
PHP Simple Html Dom Perser
これを利用することで、本文からクラスがitem-paragraphであるdivを取得(アシアルブログの本文です)し、本文からboxcode-mainというolタグ(ソースコード)を削除します。
(後で気づいたけれど、番号なしソースコードは省けていないかもしれません…)

(3) 本文を形態素解析する


形態素解析をすると、文章を意味のある単語で区切ることができます。
例えば、「すもももももももものうち」という文章ならば、「すもも:名詞」「も:助詞」「もも:名詞」「も:助詞」…というように、単語と品詞、その他の情報というように分割してくれます。
今回は、形態素解析エンジンにMeCabを使いました。

PHPでMeCabを利用するには、MeCab本体とphp-mecabをインストールする必要があります。
インストールは下記のブログが非常にわかりやすかったです。
PHPでMecab利用 - リハビリ日記
また、PHP5.3系を使っている方は、下記のブログを参考にphp_mecab0.4.1をインストールしてください。
2010-07-06 - なんというていたらく

  1. $mecab = new Mecab_Tagger();
  2. $search = array(' ', '<', '>', '"');
  3. for($i = 1; $i < 100; $i++){
  4.   $file = 'entry/'.$i.'.html';
  5.   if(is_file($file)){
  6.     $body = str_replace($search, '', strip_tags(file_get_contents($file)));
  7.     $node = $mecab->parseToNode($body);
  8.     while($node){
  9.       //品詞ID38、41、47のものだけ取得
  10.       if($node->posid == 38 || ($node->posid >= 41 && $node->posid <= 47) ){
  11.         $result[] = $node->surface;
  12.       }
  13.       $node = $node->getNext();
  14.     }
  15.     //出現回数が10回以上の単語のみにする
  16.     $omomi = omomi($result, 10);
  17.    
  18.     $omomi_str = '';
  19.     if(is_array($omomi)){
  20.       foreach($omomi as $key => $value){
  21.         $omomi_str .= $key.",";
  22.       }
  23.       $omomi_str = mb_convert_encoding($omomi_str, 'UTF-8', "auto");
  24.       $sql = "INSERT INTO blog_test VALUES($i, '$omomi_str')";
  25.       mysql_query($sql);
  26.       $result = array();
  27.     }
  28.   }
  29. }

形態素解析した結果、品詞ID38(一般名詞)、41(固有名詞:一般)、47(固有名詞:地名)のものだけ取得するようにしました。
この品詞IDを指定することで、助詞がむやみにキーワード化するのを避けます。
品詞IDリストは、MeCab 品詞IDを参考にしてください。
途中、omomi(名前がダサい)という関数にかけ、出現頻度が10回以上の単語を抽出しています。
出現頻度が高い単語で類似度をとった方がより似ているというのと、出現頻度が低いものまで含めてしまうと、長い記事のときたくさんキーワードがとれてしまい、
コサイン類似度を求めるときに処理が重くなるからです。

  1. function omomi($ary, $limit = 1){
  2.   $return = array();
  3.   foreach($ary as $a){
  4.     if(isset($return[$a])){
  5.       $return[$a]++;
  6.     } else {
  7.       $return[$a] = 1;
  8.     }
  9.   }
  10.   arsort($return);
  11.   reset($return);
  12.   if(current($return) >= $limit){
  13.     foreach($return as $key => $r){
  14.       if($r < $limit){
  15.         unset($return[$key]);
  16.       }
  17.     }
  18.   }
  19.   return $return;
  20. }

関数omomiでは、受け取った配列の出現回数をカウントし、第二引数で渡された出現頻度以上の単語のみの配列を返します。
こうして、各記事の形態素解析と、出現頻度による単語の抽出、DBに保存までを行いました。

(4) コサイン類似度を求める


それでは、ある記事に対する似ている記事を、記事全件から探していきます。
ここで用いるのが、文書の類似度を求めるときなどに利用されるコサイン類似度というものです。
これは、2つの記事のベクトルがどれだけ似ているかというものを調べます。

コサイン類似度では特定の計算式を用い、1に近づくほど似ているという結果になります。(1だと全く同一の内容、0.8~0.9だとかなり似ている、といったように)
今回ですと、ブログから形態素解析を行って意味のある名詞を多く取り出したので、文書の成分が似ているものがヒットするはずです。

コサイン類似度の計算関数は、下記のようになっています。

  1. function cosSim($w1 = null, $w2 = null){
  2.     $w = array_values(array_unique(array_merge($w1, $w2)));
  3.     for($i=0; $i<count($w); $i++){
  4.         $m1[$i] = false;
  5.         $m2[$i] = false;
  6.     }
  7.     //$wが$m1にあるか調べる
  8.     foreach($w1 as $wi){
  9.         $key = array_search($wi, $w);
  10.         if($key !== FALSE)
  11.             $m1[$key] = true;
  12.     }
  13.     //$wが$m2にあるか調べる
  14.     foreach($w2 as $wi){
  15.         $key = array_search($wi, $w);
  16.         if($key !== FALSE)
  17.             $m2[$key] = true;
  18.     }
  19.     //Cos類似度用計算
  20.     //分子
  21.     $and = 0;
  22.     for($i=0; $i<count($m1); $i++){
  23.         if($m1[$i] && $m2[$i])
  24.             $and++;
  25.     }
  26.      
  27.     //分母
  28.     $m1and = 0;
  29.     foreach($m1 as $m){
  30.         if($m)
  31.             $m1and++;
  32.     }
  33.     $m2and = 0;
  34.     foreach($m2 as $m){
  35.         if($m)
  36.             $m2and++;
  37.     }
  38.    
  39.     $m1and = sqrt($m1and);
  40.     $m2and = sqrt($m2and);
  41.    
  42.     if($and == 0 || $m1and == 0 || $m2and == 0){
  43.         return 0;
  44.     } else {
  45.         return $and/($m1and * $m2and);
  46.     }
  47. }

コサイン類似度の関数では、元となる記事の単語配列$w1と、比べたい記事の単語配列$w2を渡し、配列をマージ・ユニーク化します。
マージされた配列を元に、元記事と比べたい記事のどちらにも存在する単語を検索し、そのヒット数を調べます。
最後に、コサイン類似度の計算式に当てはめます。

似ている記事は、下記のようにして求めました。
($_POST['number']で元記事の番号を指定した場合のプログラムです)

  1. //似ている記事を探す
  2. if(isset($_POST['number'])){
  3.   $result = mysql_query('select * from blog_test', $con);
  4.   while($row = mysql_fetch_row($result)){
  5.     $blog[$row[0]] = $row[1];
  6.   }
  7.   //カンマで区切って配列にする
  8.   foreach($blog as $key => $value){
  9.     $row = explode(",", $value);
  10.     $blog[$key] = $row;
  11.   }
  12.   echo "<table border=1><tr><th>記事番号</th><th>記事のキーワード</th>";
  13.   echo "<th>似ている記事番号</th><th>似ている記事のキーワード</th></tr>";
  14.   $moto_key = intval($_POST['number']);
  15.   $result = array();
  16.   foreach($blog as $key2 => $value2){
  17.     if($moto_key != $key2 && count($blog[$moto_key]) != 0 && count($value2) != 0){
  18.       $result[$key2] = cosSim($blog[$moto_key], $value2);
  19.     }
  20.   }
  21.   arsort($result);
  22.   echo "<tr><th>".$moto_key.".html</th><td>".aryToStr($blog[$moto_key]).'</td><td>';
  23.   //似ている記事番号と類似度を3つ表示
  24.   $i=0;
  25.   foreach($result as $k => $v){
  26.     echo "<b>".$k.".html</b> : ".$v."<BR>";
  27.     $i++;
  28.     if($i == 3){
  29.       break;
  30.     }
  31.   }
  32.   echo '</td><td>';
  33.   //似ている記事のキーワードを3つ表示
  34.   $i=0;
  35.   foreach($result as $k => $v){
  36.     echo aryToStr($blog[$k])."<HR>";
  37.     $i++;
  38.     if($i == 3){
  39.       break;
  40.     }
  41.   }
  42.   echo '</td></tr>';
  43.   echo '</table>';
  44. }
  45. //配列を渡すとカンマ区切りで表示する
  46. function aryToStr($ary){
  47.   $str = '';
  48.   foreach($ary as $r){
  49.     $str .= $r.", ";
  50.   }
  51.   return $str;
  52. }

上記のプログラム、ちょっとテーブルタグが入っていて汚いですが;結果は$resultに3件入っています。

これを実行し、824番の記事(【デザイナー必見】iPhone/AndroidアプリをHTML+Javascriptで作成(PhoneGapのススメ))と似ている記事を検索します。
824番の記事からは、「PhoneGap」「アプリ」というキーワードがとれました。
検索した結果、下記のような類似記事を3件見つけることができました!



421番(iPhone 開発合宿@伊香保)キーワード:アプリ 類似度:0.82
828番(【PhoneGap】Xcode4でPhoneGapプロジェクトを作成する方法)キーワード:プロジェクト、PhoneGap、Xcode 類似度:0.58
738番(iPhoneアプリ開発開始時に気をつけるべきファイルの取り扱い (2))キーワード:ID、App、アプリ 類似度:0.58

このように、記事の本文からも似たものを探すことができます。場合によっては、ブログ記事に自分でつけたカテゴリやキーワードといったタグ情報よりも、より似ている記事が見つけられるかと思います。

ブログの内容によっては、MeCabの辞書ファイルに独自の単語を入れた方がいい場合や、キーワードの出現頻度(重み)を増減させたほうがいいものなど、あると思います。
動かしながらベストな数値を見つけてみて下さい。

似ているといっても、何がどのくらい似ているのかという尺度はいろいろあります。
音楽ならアーティスト、ジャンルといったタグから、曲調、テンポといった曲の成分まで、どれを比べるかによって類似度を調べる分類器が違ってきます。
こうして見つかった類似性をどのように活かしていくかによっても、楽しみが広がりますね。

参考
MeCab: Yet Another Part-of-Speech and Morphological Analyzer
PHP Simple Html Dom Perser
PHPでMecab利用 - リハビリ日記
2010-07-06 - なんというていたらく
PHPエクステンションのリポジトリ始めました - 讃容日記