2011年11月30日水曜日

tf-idfを実装した結果

【これまでの流れ】
① はてぶのようなサイトから持ってきた文書群と
任意の文書を比較して、似ているものをランク付けする
プログラムを書いている。

② 大まかな流れは、文書群から単語を抽出し、
  それを変数とした特徴ベクトルを文書毎に作成する。
  そして、比較したい文書の特徴ベクトル間のコサインをとり、
文書間の関連性とする。

③ この文書比較の精度を上げるため、
  tf-idfを使って文書毎に重要な単語を抽出し、
  特徴ベクトルの変数としてみる。


【今回やったこと】
今回、tfidfを実装してみたので、以下を載せる。
① tfidfによって抽出される重要単語の確認。
② tfidfを利用した場合としなかった場合の文書比較結果

※ 対象にした文書群
lifehackerの記事 : 15件
スゴレンの記事 : 11件
「原子力」って調べたときの検索結果 : 10件

※ ちなみに抽出された単語のフィルタリングは、
高い順にソートし累積値が全体の35%になった時点で切り捨てた。



【tfidfによって抽出される重要単語の確認】
まずは、この記事。
風知草:曲がり角からどこへ?

抽出された重要そうな単語はこれ。
0.17808383571585        もんじゅ
0.10330111288117        政策
0.084143345761451       原発
0.076321643878219       細野
0.06351958877225        円
0.050881095918813       現実
0.050881095918813       仕分け人
0.050881095918813       首相
0.050881095918813       表面
0.050881095918813       抜本
0.050881095918813       トン
0.050881095918813       核のゴミ
0.050881095918813       ムダ
0.050881095918813       使用済み燃料
0.050881095918813       曲がり角
0.043022928448548       基本

うん。確かにそれっぽい単語をとってきている。

つぎはこれ。
女の子の「あなたに興味がない!」という遠回しなNGサイン9パターン

抽出された重要そうな単語はこれ。
0.21558386420146        ナシ
0.21558386420146        脈
0.20183899990487        女の子
0.10091949995243        興味
0.094058059817577       女性

わかりやすいw。
そして前の例と比べて、計算されたtfidf値が高い。
つまり、
文書を見てみると、「脈ナシ」って単語が10個あった。
1つ目の記事に「もんじゅ」は10個。
つまり、ほかの文書に「脈ナシ」って単語が少なかったため、
重要だと判断されたと。
あと、単語が分割されてしまった。mecab辞書をもっとよくしなきゃ。


最後はこの記事。
寝る前の飲酒を控えて、いびきをストップ!?

抽出された重要そうな単語はこれ。

0.34947279038974        いびき
0.11649093012991        びき
0.054531940325175       酒
0.054531940325175       空気
0.038830310043305       適切
0.038830310043305       生理学
0.038830310043305       身体
0.038830310043305       通り道
0.038830310043305       睡眠時無呼吸症候群
0.038830310043305       医療機関
0.038830310043305       症状
0.038830310043305       医学
0.038830310043305       空気抵抗

いびきのtfidf値が高い。
記事を見ると「いびき」という単語が27個出てきている。
このせいか。




【tfidfを利用した場合としなかった場合の文書比較結果】
抽出した重要単語を変数とした特徴ベクトルを作成し、
記事と似た文章を、文書群のなかから抽出してみる。
コサインが0.7以上のものを抽出。
比較対象として、tfidfを利用しない場合も載せる。

まずは、この記事。
風知草:曲がり角からどこへ?

(1) tfidfを利用しない場合。
0.92011443      東芝が原発機器輸出へ、米34年ぶり原発新設再開 | Reuters
0.90298215      契約更新しない!第1原発1月に保険切れ - 経済ニュース : nikkansports.com
0.87446821      原子力防災など強化分野 エネ研拠点化会議で確認 福井・敦賀 - MSN産経ニュース
0.74048286      原子力は重要な電源=橋下氏の原発縮小路線に―関電社長 - WSJ日本版 - jp.WSJ.com
(2) tfidfを利用した場合。
0.9941724       原子力は重要な電源=橋下氏の原発縮小路線に―関電社長 - WSJ日本版 - jp.WSJ.com
0.98811356      原子力安全高度化へ技術開発を JEMA会長が必要強調 - 産業・技術 - ニュース - 電気新聞
0.9902511       契約更新しない!第1原発1月に保険切れ - 経済ニュース : nikkansports.com
0.9833529       外部電源で2回線以上 原子力安全委が喪失対策 - MSN産経ニュース
0.97699438      原子力防災など強化分野 エネ研拠点化会議で確認 福井・敦賀 - MSN産経ニュース
0.96333347      東芝が原発機器輸出へ、米34年ぶり原発新設再開 | Reuters

どちらも似通った記事をとってきていることがわかるが、
tfidfを利用した場合のほうが、コサインが顕著に分かれている。


もうひとつ、この記事。
女の子の「あなたに興味がない!」という遠回しなNGサイン9パターン

(1) tfidfを利用しない場合。(0.7以上が全然なかったので、0.1以上を表示)
0.67150338      「これを始めたらモテ出した」というモテる男の行動習慣9パターン|スゴレン
0.3456989       クリスマス当日に、滑り込みで女の子を誘う口実9パターン|スゴレン
0.23763611      女性が「ひそかに自信をもっている個性」をさりげなく褒める一言9パターン|スゴレン
0.15194308      「私に告白してよ!」という裏メッセージが含まれている女性のセリフ9パターン|スゴレン
0.14351136      女性がグラッとくる男性のスペック9パターン|スゴレン

(2) tfidfを利用した場合。
0.76842209      「これを始めたらモテ出した」というモテる男の行動習慣9パターン|スゴレン
0.43482185      クリスマス当日に、滑り込みで女の子を誘う口実9パターン|スゴレン
0.30439966      [Androidアプリレビュー]子どもの成長記録に便利!?(浮気の追及にも!?) 寝言を録音できる『NEGOTO Recorder』 #TABROID
0.27703564      女性が「ひそかに自信をもっている個性」をさりげなく褒める一言9パターン|スゴレン
0.27239949      失敗した時は、うまくいく方法を見つける過程だと考えよう [gReader]
0.20112109      「私に告白してよ!」という裏メッセージが含まれている女性のセリフ9パターン|スゴレン
0.18463171      女性がグラッとくる男性のスペック9パターン|スゴレン

意外にコサインの値が低くなる。
特徴ベクトルの変数を「重要単語」に絞ったため、
近い変数が少なくなったのかな。
なんで、Androidアプリレビューが入ってるんだw。


ついでにこの記事も。
寝る前の飲酒を控えて、いびきをストップ!?

(1) tfidfを利用しない場合。
0.91099372      コワーキングを楽しむ3つのススメ [gReader]
0.90791908      [Androidアプリレビュー]子どもの成長記録に便利!?(浮気の追及にも!?) 寝言を録音できる『NEGOTO Recorder』 #TABROID
0.89963271      聞いている音楽にぴったりのカクテルレシピを教えてくれる新感覚サイト「Drinkify」 [gReader]
0.85027147      失敗した時は、うまくいく方法を見つける過程だと考えよう [gReader]
0.83635293      90分の「集中タイム」と30分の「完全な休憩」を交互に取る生産性向上メソッド [gReader]
0.78096475      不眠症を回避するための一日の過ごし方
0.72454513      ソーシャルゲームがパチンコよりも優れている理由 - ぼくはまちちゃん!(Hatena) [gReader]

(2) tfidfを利用した場合。
0.94035399      コワーキングを楽しむ3つのススメ [gReader]
0.81401848      プログラマーは"一線"を超えると急激に伸びる - Linux/Ruby 小崎氏(後編) | エンタープライズ | マイナビニュース [gReader]

いまいちつながりがわからん。



【思ったこと】
1、重要単語に絞ったため、特徴ベクトルが一致しにくくなった。
コサインの値が高くなるかどうかは、特徴ベクトルの変数がどれだけ近くなるかによる。
つまり、同じ単語が一切なければ、
ゴミ単語が多いと精度は下がる。しかし特徴を表す単語が少なくても精度は下がる。

より文書の特徴をうまく反映した単語を抽出するために。

① mecab辞書
やっぱりゴミみたいな単語まで含まれている。
mecab辞書の見直しと抽出する品詞を限定しよう。

② ifidfの重要単語の基準値
tfidf値から重要単語を判断する基準値はどうしよう?
今回適用に全体の35%としたが。

③ 別の重要単語の抽出方法
統計情報に基づき重要語を抽出もやってみたい。

④ 単語間の意味的つながり
単語どうしの意味的なつながりを加味する。

(1) 単語同士の意味的なつながりを表すデータを準備しておいて、
重みづけをする際、それを加味する。
全然やり方検討つかんけど。
論文探してみよう。

(2) 特異値分解をしているから、
2つの文書間に直接共通する単語がなくても、
それらをつなぐ文章があれば意味的なつながりは加味されるはず。

じゃ、抽出したい文書群に加え、
単語同士の意味的なつながりを表す文書群を加えては?。


2、文章群の範囲をもうすこし考えよう。
「原子力」や「スゴレン」のようにテーマがはっきり決まっているものは、
うまく抽出できるが、「ライフハッカー」のように1つ1つの記事のテーマがばらばらだと
うまく抽出できてない。文書の範囲を狭くしたほうがいいのかな。
でも逆に、「母数がすくないから、似たような記事がなかった」とも考えられる。
それに、文書の範囲を狭めると文書の差異が細かくなって、区別するのが難しいかも。
要検討。


3、もう少し定量的に結果を比較する方法がほしいな。

2011年11月25日金曜日

bzr の処理中にエラーが発生しました。

apt-get installを実行したとき、
「 bzr の処理中にエラーが発生しました」と出た。


① エラーの内容確認

dpkg: bzr の処理中にエラーが発生しました (--configure):
 サブプロセス インストール済みの post-installation スクリプト はエラー終了ステータス 1 を返しました
configured to not write apport reports
                                      dpkg: 依存関係の問題により bzrtools の設定ができません:
 bzrtools は以下に依存 (depends) します: bzr (>= 2.1~) ...しかし:
  パッケージ bzr はまだ設定されていません。
 bzrtools は以下に依存 (depends) します: bzr (<= 2.2) ...しかし:
  パッケージ bzr はまだ設定されていません。
dpkg: bzrtools の処理中にエラーが発生しました (--configure):
 依存関係の問題 - 設定を見送ります
liberror-perl (0.17-1) を設定しています ...
configured to not write apport reports
                                      git (1:1.7.2.5-3) を設定しています ...
以下のパッケージの処理中にエラーが発生しました:
 bzr
 bzrtools
bzrの処理ってなんだろう。。 その前に、not foundってエラーがいっぱい出てる。
・・・
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml4.py not found.
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml5.py not found.
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml6.py not found.
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml7.py not found.
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml8.py not found.
   dpkg: /usr/lib/python2.5/site-packages/bzrlib/xml_serializer.py not found.
② pythonの再インストール python2.5、入ってないんじゃないかな。 そんなこともない。 /usr/lib/python2.5/site-packages/bzrlib/ ~ がないんじゃないかな。 そんなこともない。 ③ bzr再インストール
$ apt-get remove bzr
$ apt-get install bzr

治った。
bzrがちゃんとインストールされていなかっただけかな。

やっぱりべたにtf-idfでやろうかな。

語の共起の統計情報に基づく文書からのキーワード抽出アルゴリズム
を読んだ。

精度としては、tf-idfと同じくらいのものらしい。
違いとしては、tf-idfでは比較対象となる文章群が必要になること。
この論文の方法では、比較対象が必要ない。

なんか重みづけとの区別なくなってきたが。
この辺とか役に立ちそう。
TFIDFを使ってwikipediaの各キーワードの特徴量を抽出
形態素解析と検索APIとTF-IDFでキーワード抽出


基本的なtf-idfの式で計算できる。

tf : 対象となる文書中の単語出現数 / 文書の総単語数
N :全てのドキュメント数
df :代表キーワード候補が含まれるドキュメントの数 (DF)、

・tfの意味は、文章中の対象の単語がいっぱい出てくれば、
その単語は重要とみなすということ。
・log~の意味は、対象の単語が他の文章になければ、
その単語の重要度を上げようということ。

つまり、得られたwの値が高いほど、N個の文書群の中で、
重要な単語であると考えられる。

※ tfの取り方はいくつかやり方が見つかったが、
文章の長さを考慮したこのやり方がいいと思った。
(長い文書ほど、重要語が出やすいだろうということ)



ということで、特徴ベクトルの変数の取り出し方
① tf-idfで重要語を抽出、それを特徴ベクトルの変数とする。
② 統計情報に基づき重要語を抽出、それを特徴ベクトルの変数とする。

どっちがいいんだろう。
わかりやすいtf-idfのほうからやってみるか。

2011年11月24日木曜日

文章の長さが特徴ベクトルに与える影響の軽減 ~背景~

はてぶのようなサイトからテキストデータを持ってきて、
任意の文章と似ているものをランク付けするプログラムを書いてみた。
が、精度がいまいち。

文章の類似性を測る方法として、
いくつかの論文を読んで使われていた、
以下の方法を使っている。
形態素解析で文章中の単語を抽出。
その単語を変数とした特徴ベクトルを作成し、
測りたい2つの文章の特徴ベクトル間のコサインをとって
2つの文章の類似性とする。

検討しなければならないポイントは次の2つ。

① 比較したい文章の特徴をうまく特徴ベクトルに反映させるため、
特徴ベクトルの変数を何にするか検討する。

② さらに、文章の特徴をより強く反映させるため、
特徴ベクトルの重みづけをする。


今現在、精度に大きな影響を与えているのは、
①の特徴ベクトルの変数の選び方だと思う。
だって、はてぶからとった文章の名詞を全部、
特徴ベクトルの変数にしてるんだから。

つまり、同じ内容の文章でも、その文章の長さによって、
特徴ベクトルが変わってしまう。
これはいまいちいけてない。

で、調べてみたら、以下の論文が目に付いた。
語の共起の統計情報に基づく文書からのキーワード抽出アルゴリズム

まだちゃんと読んでないが、
「単語Aの文章中における出現確率」と
「単語Bが含まれる文中に、単語Aが出現する確率」とを比較し、
偏りが見られれば、単語Aと単語Bの意味的なつながりが
大きいと判断できるというもの。


これを使えば、ある1つの文章の中で重要な単語を、
ほかの文章と関係なく抽出することができる。
そうやって抽出した単語を特徴ベクトルの変数として使えば、
文章をその内容的に近いものを抽出できるようになるのでは?
ちょっと作ってみよう。

2011年11月20日日曜日

河野君が作ったReadItLater.phpを使ってみる。

1、Zend frameworkのインストール
ここに書いてある感じで。
Programer's Reference Guide

Zend Frameworkのダウンロード
アカウントを作る必要がある。

②phpのincludeパスにを通す。
; Zend Framework 
include_path = "/usr/local/share/ZendFramework-1.11.11/library"



2、ReadItLater.phpをダウンロード
$ git clone git://github.com/aoiaoi/ReadItLater.git


また、ReadItLaterのAPIについては
API Documentationを参照。


3、自分のRILからリストを取得する。
get();
    $response_body = $response->getBody();

    // 
    $jobj = json_decode($response_body);  
    foreach($jobj->list as $item){
        echo "title : " . $item->title . "\r\n";
        echo "url   : " . $item->url   . "\r\n";
    }
?>

参考
戻りリストの取得


4、テキストの取得
text($url,$text_options);
    $text_response_body = decUnicode($text_response->getBody(),"UTF-8");   

?>

RILから返ってくるレスポンスはUnicodeで書かれているため、
UTF8に変換する必要がある(最後の行)。
Unicode変換ツール(PHP編)
これで行くか。

URLによっては、テキストを取得できない場合があった。。

2011年11月18日金曜日

read it laterに関する設定

Read It Laterを使おうと思った。
とりあえず設定できそうなことをいろいろ設定してみた。
全部使うかは怪しいが。。

ひとつの使い方として参考になる


1、アカウントを作成
こんな感じ


2、ブックマークレットの追加
ここからとる


3、google readerの送信先を追加する
やり方
画面右上の[設定]→[リーダー設定]→[Send To(送信先)]→[Create a custom link(カスタムリンクを作成)]

① APIキーの取得
まず、APIきーを取得

② Read It Later
Name:RIL
URL:https://readitlaterlist.com/edit?username=<ユーザー名>&password=<パスワード>&apikey=<API KEY>&url=${url}&title=${title}
Icon URL:http://readitlaterlist.com/favicon.ico

③ ついでにはてブを設定
Name:はてブ
URL:http://b.hatena.ne.jp/add?mode=confirm&title=${title}&url=${url}
Icon URL:http://b.hatena.ne.jp/images/append.gif


4、Galaxyからgoogle reader読んでるときは。
gReaderを使えば、ReaditLaterにポストできる。


5、GalaxyからRead It Laterを読むときは。
Read It Laterのアプリ使う。


今度、evernoteの使い方も見直そう。

2011年11月17日木曜日

phpでCARTアルゴリズムを使った決定木を作成する。

PHPで,CARTアルゴリズムを使った決定木の作成をやってみた。
CARTアルゴリズムは、こんなかんじ

とりあえず、
①ある変数で2つに分類したノードそれぞれで、目的変数に対するジニ係数を計算する。
②ルートノードのジニ係数と、分類したノードのジニ係数の差を計算する。
③すべての変数に対して、その差を計算し、差が最大のものを分岐条件とする。
④これを繰り返していく。
こんな感じで。


1、渡すデータ
必要なデータを入れた配列を、さらに配列に入れた形。
// 渡すデータ構造
    $data = array();
    $data[0]  = array("生死"=>"生還","年齢"=>"35","性別"=>"男","等級"=>"1等");
    $data[1]  = array("生死"=>"生還","年齢"=>"12","性別"=>"女","等級"=>"1等");
    $data[2]  = array("生死"=>"生還","年齢"=>"35","性別"=>"女","等級"=>"2等");
    $data[3]  = array("生死"=>"死亡","年齢"=>"34","性別"=>"女","等級"=>"2等");
    $data[4]  = array("生死"=>"生還","年齢"=>"23","性別"=>"男","等級"=>"3等");
    $data[5]  = array("生死"=>"死亡","年齢"=>"31","性別"=>"男","等級"=>"3等");
    $data[6]  = array("生死"=>"死亡","年齢"=>"32","性別"=>"男","等級"=>"3等");
    $data[7]  = array("生死"=>"死亡","年齢"=>"23","性別"=>"男","等級"=>"乗組員");
    $data[8]  = array("生死"=>"死亡","年齢"=>"25","性別"=>"男","等級"=>"乗組員");
    $data[9]  = array("生死"=>"死亡","年齢"=>"29","性別"=>"女","等級"=>"乗組員");
    $data[10] = array("生死"=>"死亡","年齢"=>"40","性別"=>"女","等級"=>"乗組員");
データ : 船が難破したときの乗客の生還死亡リスト
目的変数 : 生死
カテゴリ変数 : 年齢、性別、等級



2、多値変数、連続変数をすべて、二値変数に変換する
決定木は二分木なので、
持っている変数の中で値が3種類以上あるもの(多値変数:等級)、
値が連続であるもの(連続変数:年齢)を、
二値変数に置きなおす必要がある。

① 多値変数を二値変数に変換する
多値変数の取りうる値を2つのグループに分け、
二値変数とする。
この時も、CARTアルゴリズムを使い、
どの分け方が、もっとも目的変数の影響を反映するかを
確定する。

多値変数「等級」が、以下の感じの二値変数となる。
グループ1 : 1等
グループ2 : 2等3等乗務員


② 連続変数を二値変数に変換する
連続変数の値が昇順になるよう並び替え、
どこで区切るともっとも目的変数の影響を反映するかを、
またCARTアルゴリズムを使って確定する。

連続変数「年齢」が、以下の感じの二値変数となる。
グループ1 : 30 以下
グループ2 : 30 より大きい



3、木の生成

① 分岐
CART使って分岐条件になる変数を決め、データを分ける。
そのデータでさらに分岐条件を決め、またデータを分ける。
これを繰り返して、木構造を作成する。


② 分岐の終了、枝刈り
なんかいろいろ方法あるみたいだけど、
とりあえず、最後までやればいいや。



4、木の利用
入力したデータから目的変数を除いた形式で配列を渡すと、
想定される目的変数の値を返すようにした。

// 渡すデータ構造
    $target = array("年齢"=>"40","性別"=>"女","等級"=>"乗組員");



なんとなくできたが、
なんちゃってデータマイニングになっている感は
否めない。

拙いコードだけどさらしてみる。

https://github.com/kokukuma/php-decision-tree

2011年11月16日水曜日

重複しない数字を2つのグループに分割する。

全組み合わせを抽出したあと、
重複しているものを取り除く形で作った。
一方のグループを要素の配列として出力。

長すぎる。
絶対もっときれいな書き方あると思う。


 $value) {
        echo implode($value)."\n";
        //echo var_dump($value);
        //echo "--------------\n";
    }

    function split_data($data)
    {
        $result = array();
        $return = array();

        // 組み合わせを抽出 
        for ($i=0; $i < count($data)-1; $i++) {
            $res = conbination($data , $i+1);
            foreach ($res as $key => $value) {
                array_push($result,$value);
            }
        }

        // 重複を排除
        $length = floor( count($data) / 2);
        $flg    = count($data) % 2;

        foreach ($result as $key => $value) {
            if(count($value) <= $length){
                switch ($flg) {
                case 0:
                    $max = max($data);
                    if(!array_search($max, $value)){
                        array_push($return,$value);
                    }
                    break;
                case 1:
                    array_push($return,$value);
                    break;
                }
            }
        }
        return $return;
    }

    function conbination($array,$num)
    {
        $arrnum = count($array);
        if($arrnum < $num){
            return;
        }else if ($num==1) {
            for ($i=0; $i < $arrnum; $i++) {
                $arrs[$i] = array($array[$i]);
            }
        }elseif ($num>1) {
            $j=0;
            for ($i=0; $i < $arrnum-$num+1; $i++) {
                $ts = conbination(array_slice($array,$i+1),$num-1);
                foreach ($ts as $t ) {
                    array_unshift($t,$array[$i]);
                    $arrs[$j]= $t;
                    $j++;
                }
            }
        }
        return $arrs;
    }
?>

2011年11月13日日曜日

Rで決定木を作成する。

Rで決定木を作成してみる。

1、mvpartをインストール.
$ sudo wget http://cran.r-project.org/src/contrib/mvpart_1.4-0.tar.gz
$ sudo tar -xvzf mvpart_1.4-0
$ sudo R
> install.packages("mvpart_1.4-0.tar.gz",destdir=".",repos=NULL)
> library(mvpart)


2、木の基本
① 「read.csv」でデータ読み込んで、「rpart」で木を作る。
② 木には、分類木と回帰木がある。
  分類木は分類、回帰木は数値を返す。
③ 「cp (complexity parameter)」で木の複雑さを表す。
  mvpartのデフォルトでは、CP=0.01
  CPが高いほど、木は単純になるが誤差が大きくなる。
  小さいほど、木は複雑になるが誤差は小さくなる。
  で、誤差が十分小さく、単純な木がほしい。
  最適なCPを図る方法も必要。


3、mvpartを使って、木を作ってみる。
① 偽札のCSVデータ(真偽、下部マージンの長さ、対角線の長さ、)
> nd <- read.csv("nisesatsu.csv",header=T)
> nt <- rpart(真偽~. , data=nd,type="class")
> print(ht)

② 不動産価格のCSVデータ(価格、犯罪率、部屋数、築年数、等)
> hd <- read.csv("house.csv",header=T)
> ht <- rpart(真偽~. , data=hd,type="anova")
> print(ht)

③ 不動産価格のCSVデータ、CP変更
> hd <- read.csv("house.csv",header=T)
> ht <- rpart(真偽~. , data=hd,type="anova", cp=0)
> print(ht)
> ht2 <- prune(ht, cp=0.03)
> print(ht2)

2011年11月11日金曜日

ソーシャルグラフに関する論文を読んだときのメモ

ソーシャルグラフについての論文を読んだメモ。

グラフデータを使い、ユーザの特徴をどう表現すればいいかが知りたくて調べてみた。ぶっちゃけそれは最初の論文だけで、後はソーシャルグラフの応用例的な。なんか長くなったので、読んだ論文のリストを書く。

1、ソーシャルネットワークにおけるリンク構造を用いた重複クラスタリング手法の提
2、MAKOTO:ソーシャルグラフを用いたコミュニケーション支援システムの提案
3、Twitter Catches the Flu: 事実性判定を用いたインフルエンザ流行予測
4、目的地にいる人々とのコミュニケーションを促進するシステムの開発



1、ソーシャルネットワークにおけるリンク構造を用いた重複クラスタリング手法の提
「プロフィール」からだけでなく、
「リンク」からもユーザの特徴を抽出し、
複数のクラスタに所属させようという研究。
「プロフィール」ではなく、「発言」だけど、
プロフィールのほうがイメージしやすかったので、
そっちで書く。


この研究では、
そのユーザが受けている「リンク」は、「リンク元ユーザの関心」を表し、
「リンク元ユーザの関心はリンク先ユーザ(対象ユーザ)の特徴を表す」
と考える。

そのため、対象ユーザの特徴を、
対象ユーザの「プロフィール」から抽出される特徴と、
対象ユーザの「リンク元ユーザとかのプロフィール」から抽出される特徴の
2種類からなる。(どちらもプロフィールを基に定義した特徴ベクトルなので、
その評価軸は同じにできる)

そのため、対象ユーザの特徴ベクトルは、
1+リンク数だけ持つことになり、
最大で、その数だけ別のクラスタに所属することになる。

さらに、リンク元ユーザが「どんな関心」をもって対象ユーザに
リンクをしているのかを定義づける必要がある。
それには、リンク元ユーザと対象ユーザが、
「共通している持っているリンク先の特徴」を使う。
これに重みづけをして、
1つの対象ユーザの特徴ベクトルを作成する。


なんかややこしい。
リンクの特徴をリンク元ユーザとかのプロフィールを使って、
表現するのは面白いと思った。


2、MAKOTO:ソーシャルグラフを用いたコミュニケーション支援システムの提案
とりあえず、写真見るだけでも一見の価値があると思う。
やっていることは、twitterから自分のついーと引っ張ってきて、
単語抽出して、ほかの人のそれと比較しているだけ。
でも、その利用方法、見せ方がすごく面白い。


3、Twitter Catches the Flu: 事実性判定を用いたインフルエンザ流行予測
タイトルまんま。twitterの発言内容からインフルエンザの流行を予測しようって研究。
同じようにインフルエンザを予測しようという研究は多くあるみたい。
「医療アドバイスコールセンターへの問い合わせ数」、「インフルエンザ市販薬の販売量、
「インフルエンザに関するGoogleの検索クエリ数」。
この研究では、「インフルエンザにかかっていると思われるツイート数」

この際問題になるのが、「発言者がインフルエンザにかかっているかどうか」を
どうやって判断するか。インフルエンザを含むツイートすべての集計では、
「インフルエンザじゃなかったw」といった発言までカウントしてしまう。
それを判別するために使われているのが、サポートベクターマシン(SVM)。

サポートベクターマシンは、
ニューラルネットワークの一種だとか。
詳しいとこまで理解できてないが、
要は、決定木と同じように、入出力のルールを
抽出するものだと思う。

この研究では、あらかじめ、
ツイート内容とインフルエンザ陰性・陽性のセットを準備して、
(人がツイート内容を読んで判断)
SVMにより、インフルエンザという単語の周辺の単語から、
発言者やその周辺の人がインフルエンザにかかっているかどうかを判断する
ルールを抽出する。

この結果、google flu trendと同じくらいの精度が出たとか。。
ただし、加熱報道時には大きく精度が悪くなるとか。
twitterっぽいw。

同じように、twitterを使った地震予知とかもある。
Earthquake Shakes Twitter Users:
Real-time Event Detection by Social Sensors




4、目的地にいる人々とのコミュニケーションを促進するシステムの開発
こっちが作りたいと思っていたものとよく似ている。
「知っている人にメッセージを送る」という意味で。
ここでは、質問内容を場所に関するものに限定し、
(情報を知っている人)=(その場所にいる人)としている。
さらにメッセージを送るための仕組みとして、
自分らでtwitterクライアントを作成することで何とかしようとしてる。
やはり問題は、「質問内容を知っている人の絞り込み」と
「メッセージ送信方法」か。

2011年11月10日木曜日

決定木に関する論文を読んだ時のメモ

決定木の応用方法について調べた。

1、系列パターンを利用した決定木による自然言語における選択ルール獲得
ある文章中に「結構」という単語が出てきたとき、
それがどんな意味で使われているか
(論文中では、「かまわない」、「いらない」、「すばらしい」の3つ)を、
前後に現れる単語によって判断するためのルールを抽出する研究。

ルールの抽出には、決定木を利用する。
決定木とは、入力と出力の組み合わせを計算するもの。
入力が「AかつB」なら、出力は「X」
入力が「AかつBかつC」なら、出力は「Y」
みたいな選択ルールを抽出してくれる。

この論文では、前後に現れる単語の出現する順序の組み合わせを、
決定木の入力とし、系列パターンと呼んでいる(PrefixSpanというアルゴリズムで抽出)。
さらにこれを単語そのものだけでなく、単語の読み,原形,品詞,活用,型、
それぞれにおいて、系列パターンを抽出し、決定木の入力とする。
この結果、「結構の意味を分類する選択ルール」を決めることができる。

この選択ルールを使えば、「結構」を含む任意の文章から、
どの意味でつかわれているかを機械的に判断することができる。

この論文ではさらに、「話しているのが男か女かを判断するルール」を抽出している。
この決定木の入力には、文章の終助詞、代名詞を利用している。


2、決定木分析による都市型アミューズメント施設の来訪者特性評価
決定木の説明がよくされている。
この論文でやっているのは、
「どんな人がラーメンスタジアムに来るかを判断するルール」を作成している。
決定木の入力としては、過去に来訪した人の特徴を使っている。
具体的には、性別、年齢、職業、自宅からの距離などを使う。



3、決定木とQM法による職業意思決定過程分析
学生のうち「どんな人が自分の職業を決められているかのルール」を作成している。
決定木の入力には、学生の心理的状態を使っている。
これは、学生からとったアンケートを基に、
「未熟」、「混乱」、「猶予」、「模索」、「安直」と、
職業を決める際にありそうな心理的状態を数値化して利用している。


4、そのほか読んでないが。。
・健康維持のための室内温熱環境制御法の一提案
・データマイニングの手法を用いた定期歯科受診者の受診中断に関わる要因の分析
・ネットオークションの商品情報を用いた決定木学習による出品者の行動パターンの分類

すげー面白そうw。
つまり決定木を使ってできることは、
「経験的に因果関係のありそうな事柄を、定量的に評価する」ことか。
そういった意味では、ニューラルネットワークと近しいものを感じる。

2011年11月8日火曜日

PHPで潜在的意味解析

芸能人の相関関係を探ってみる。

redsvdのチュートリアル

誰かの論文

単語と意味属性との共起に基づく概念ベクトル生成手法


これをニュースの記事でやってみる。
基本的に、PHPを使う。


1、ニュースのタイトルと本文を取得
① phpの関数simplexml_load_fileで、rssからタイトルとかURLとか取得できる。
PHPでRSSを読み込む方法

② 下記のサービスをつかえば、全文配信にしてくれる。
http://fulltextrssfeed.com/
※ 本文はdescriptionタグに入れられる。

余計なタグは、「strip_tags」という関数で除去することができる。



2、共起行列の作成

① mecabを使い、本文からキーワードを抽出。
しかし、でふぉの辞書ではいまいち。下記をやってみる。
mecabのユーザ辞書でwikipediaとhatenaキーワードを利用する
辞書の場所 : /usr/local/lib/mecab/dic/ipadic
使う辞書の設定 : /usr/local/etc/mecabrc


② RMecabを使う。

(1)CentOS5.5で、yumでRをインストール
※1 urlは「http://rm.mirror.garr.it/mirrors/CRAN/bin/linux/redhat/el5/x86_64/」二変更
※2 「libtcl」「libtk」を入れる。
※3 どうやら「R-core2.0」は最新ではないらしい。
rpmforgeをいれ、yum listすると「R-core2.3」がインストールできた。

(2)RMecabをインストールする。
※1 tar.gzは、R-2.13.0用からダウンロードする。
※2 wgetでダウンロードできなかったから、別マシンで落として、winscpで送った。
$ sudo tar -xvzf RMeCab_0.95.tar.gz
$ sudo R
> install.packages("RMeCab_0.95.tar.gz", destdir=".", repos=NULL)
> library(RMeCab)    ↓(3)を忘れるとエラーが出る。


(3)libmecab.so.1: 共有オブジェクトファイルを開けません
※1 /etc/ld.so.conf.d/mecab.conf を作成。
※2 /usr/local/libのままでよい。
※3 $ sudo /sbin/ldconfig を実行。


(4)RMeCabを使う。

$ R
> library(RMeCab)
> RMeCabC("すもももももももものうち")
> res <- docMatrix("doc", pos = c("名詞", "形容詞", "助詞"), weight = "tf*idf")
> res
> q()


③ phpで書く。
RMeCabをPHPから使うのはめんどくさそうだったので、
PHPで直接書いた。
行に文章、列に抽出した全語句を割り当て、
共起行列を作成した。



2、特異値分解処理(次元圧縮)
PHPで行列の計算をするのはめんどくさそう。
考えた選択肢としては、

① PHP行列計算ライブラリを使う。

見つからないかった。


② redsvdを使い、行列計算用 PHP Extensionを作成する。
redsvdを使うためには、eigen3をインストールする必要がある。
また、c++なので、Extensionを作成し、PHPから使えるようにする必要がある。
つまり、作ろうとしている潜在意味解析モジュールを使おうとしたら、
Extensionのいんすとーる、eigen3のいんすとーる、redsvdのいんすとーるを
する必要がある。
ちょっとめんどい。

③ eigen3を使い、行列計算用 PHP Extensionを作成する。
redsvdを使わなくても、eigen3だけでも特異値分解は可能。
これなら、
Extensionのいんすとーる、eigen3のいんすとーる、だけでよい。
まだまし。
そのためには、

・ eigen3の使い方調べる。
・ C++でphp extensinoを作る方法の調査
・ PHP extensionで、配列を受け渡す方法を調べる。

c++でphp extensionを作成する。


また、次元圧縮は、引数で、その割合を指定できるようにする。

てかそもそも、全部 PHP Extensionに押し込めるか。
共起行列の作成とかも、全部、PHP Extensionに押し込めないかな。。
ただ、データの受け渡しがチョイ不安なので、
今は、行列計算の部分だけにしとく。



3、特徴ベクトルの作成
共起行列Aを特異値分解すると、以下の3つに分解される。

A = U * S * V.transpose

U : 左特異行列 (文書の特徴を表す)
S : 特異値行列
V : 右特異行列 (語句の特徴を表す)
※ transposeは転置行列

括弧内は、行を文書、列を語句としたときの、
行列が表す意味。
この分解の特徴として、
特異行列の次元を小さくして、Aを復元すると、
Aを近似した行列を求められる点。


① 文書同士を比較したい場合は、
Uの1行を文書の特徴ベクトルとして、コサインをとれば、
1~-1の範囲で、文書の特徴を評価できる。

② 語句であれば、Vのベクトル。

③ 文書と語句の関連性は、復元したAの近似行列の
各要素の大きさで評価できる。

④ 特異分解するときAに含まれていない文書を評価したいときは、
V, Sを使って、Uの特徴ベクトルを作成することができる。

U_Vector = T_Vector.transpose() * V * S.inverse
※ transposeは逆行列

このU_Vectorと、Uの特徴ベクトルでコサインを計算すれば、
①と同様に評価できる。



4、コサインの計算
計算する。


5、感想
ここまで作って見たが、
ニュース同士の関連を数値化することはできたが、
その精度には疑問が残る。

・ もっと対象とする文書、語句を大きくして、潜在意味空間を広げるか。
・ 文書、語句の範囲を絞り、潜在意味空間の質を上げるか。

もうちょっと検討の必要あり。

2011年11月7日月曜日

c++でphp extensionを作成する。

なにはともあれ、

C++でPHP extensionを作成する。


1、スケルトンを作成
# ./ext_skel --extname=eigen
# cd eigen


2、config.m4を修正

① PHP_ARG_WITHのコメントアウトを外す。

② コンパイラの環境変数を設定

CC=/usr/bin/gcc
CXX=/usr/bin/g++


追記 : のちに、以下もつける必要があるとわかった。

CFLAGS="-g -O2 -lstdc++"
CXXFLAGS=-fPIC


③ 拡張子を「c」から「cc」 or 「cpp」にする。
PHP_NEW_EXTENSION(eigen, eigen.cc, $ext_shared)



3、ソースファイルを修正

① 名前の拡張子を修正
# mv eigen.c eigen.cc
② 中身の #includeを extern "C"で囲む

extern "C"{
    #include "php.h"
    #include "php_ini.h"
    #include "ext/standard/info.h"
    #include "php_eigen.h"
}


4、phpizeでconfigure作成
# phpize

5、configure実行
# ./configure

6、makeを実行
# make

※1 ここで「.libs/eigen.o: could not read symbols: Bad value」というエラーが発生した。

(1)config.m4の「CCをg++」にてみた。


CC=/usr/bin/gcc
CXX=/usr/bin/g++
CC=/usr/bin/g++


ダメ。

(2) php_eigen.hも extern "C"を付けた。

ダメ。

(3) ちゃんとエラーを読んでみた。
「/usr/bin/ld: .libs/eigen.o: relocation R_X86_64_32 against `eigen_module_entry' can not be used when making a shared object; recompile with -fPIC」

なるほど。-fPICオプションをつけてコンパイルし直せと。
Makefile or config.m4に追記。
CXXFLAGS=-fPIC

よしできた。

7、make installを実行
# make install

開発するときはいちいちめんどいので、
シンボリックリンクのほうがいいかも。

# sudo ln -s /usr/local/share/php-5.3.8/ext/eigen/modules/eigen.so /usr/lib64/20090626/



8、php.iniの修正
extension=eigen.so

9、実行を確認。

helloworld
?>
できない!?。

※1 「PHP Warning:  PHP Startup: Unable to load dynamic library '/usr/lib64/20090626/eigen.so' - /usr/lib64/20090626/eigen.so: undefined symbol: __gxx_personality_v0 in Unknown on line 0」
と出る。
ちょっと調べてみると、gccでコンパイルすると出るエラーだと。
確かにsoをコンパイルするとき、gcc使ってたな。

(1) Makefile の CC=gcc を CC=g++にしてみた。
なんか変なエラー出た。

(2) Makefile の CCFLAGS に -lstdc++をつけてみた。
-lstdc++はc++をコンパイルするよってオプション。
g++ は gcc -lstdc++みたいなもんか。

よしできた。



続いて、eigen.cc の中で、eigen3を実行してみる。

9、前作ったサンプルをそのままコピペしてみる。
→ 動いた。

2011年11月5日土曜日

eigen3でsvd

1、cmakeのインストール
クロスプラットフォームのconfigureだと。。
$ sudo yum install cmake

cmakeの使い方


2、eigen3のインストール
$ wget http://bitbucket.org/eigen/eigen/get/3.0.3.tar.gz
$ tar -xvzf 3.0.3.tar.gz
$ cd eigen-eigen
$ mkdir build
$ cd build
$ cmake -G "Unix Makefiles" ../
$ make
$ sudo make install

※1 makeした後、make checkしたら
すごく時間かかったから途中でやめた。


3、c++のソースを書いてコンパイルしてみた。
eigen3 - getting started
C++の行列計算ライブラリ

$ cat sample.cc

#include
#include
#include
using Eigen::MatrixXd;

int main(int argc, char const* argv[])
{

    MatrixXd X(2,2);
    X(0,0)=5;
    X(1,0)=5;
    X(0,1)=5;
    X(1,1)=1;
    X(1,1)=X(1,0) + X(0,1);
    std::cout << X << std::endl;
    //printf("karino : %d\n",X(1,2));
    return 0;
}

$ g++ -I/usr/local/include/eigen3 sample.cc (eigen3のヘッダファイルを読み込む)
$ ./a.out
 5  5
 5 10



4、特異値分解

以下みたいな雰囲気で行けた。


    MatrixXf m = MatrixXf::Random(4,3);
    cout << "---------------------" << endl;
    cout << "A:" << endl << m << endl;
    JacobiSVD svd(m, ComputeThinU | ComputeThinV);

    MatrixXf S = svd.singularValues();
    MatrixXf U = svd.matrixU();
    MatrixXf V = svd.matrixV();
    MatrixXf SD = S.asDiagonal();

    cout << "---------------------" << endl;
    cout << "U:" << endl << U << endl;
    cout << "S:" << endl << S << endl;
    cout << "Diag:" << endl << SD << endl;
    cout << "V:" << endl << V << endl;


    //cout << "A:" << endl << U * S.transpose() * V << endl;
    cout << "---------------------" << endl;
    cout << "A:" << endl << U * SD *V.transpose() << endl;



5、次元圧縮
したみたいな感じで部分行列を取り出せばよい。
どれだけの部分を抽出するかは自分で決めなきゃならない。



    MatrixXf UB  = U.block(0,0,4,2);
    MatrixXf SDB = SD.block(0,0,2,2);
    MatrixXf VB  = V.block(0,0,3,2);

    cout << "---------------------" << endl;
    cout << "UB:" << endl << UB << endl;
    cout << "SDB:" << endl << SDB << endl;
    cout << "VB:" << endl << VB << endl;

    cout << "---------------------" << endl;
    cout << "A:" << endl << UB * SDB *VB.transpose() << endl;




6、ベクトルの内積。
後で調べる。
こことかいいと思う。

redsvdを使ってみる。

行列分解ライブラリredsvd


1、cmakeのインストール
クロスプラットフォームのconfigureだと。。
$ sudo yum install cmake

cmakeの使い方


2、eigen3のインストール
$ wget http://bitbucket.org/eigen/eigen/get/3.0.3.tar.gz
$ tar -xvzf 3.0.3.tar.gz
$ cd eigen-eigen
$ mkdir build
$ cd build
$ cmake -G "Unix Makefiles" ../
$ make
$ sudo make install

※1 makeした後、make checkしたら
すごく時間かかったから途中でやめた。





3、redsvdのインストール
$ wget http://redsvd.googlecode.com/files/redsvd-0.2.0.tar.bz2
$ tar -xvjf redsvdd-0.2.0.tar.bz2
$ cd redsvd
$ ./waf configure
$ ./waf make
$ sudo ./waf install

※1、「./waf configure」の段階で、「gtest」と「eigen3」がないといわれた。


4、redsvdをコマンドラインから使ってみる。
適当な行列を書いたファイルfile1を準備.

$ redsvd -i file1 -o file1 -r 2

参考にしたサイトに書いてある通り、
3つのファイルが作成された。


5、C++のソースで特異値分解するには?
redsvd-0.2.0/sampleに入っているやつ、
コマンドラインから実行するためのプログラムっぽい。
lsa.cppで定義されている「LSA::processFileList」のなかに、
ぽい部分があったが、うまくいかず・・・。

octaveでもsvdができるらしい。

1、octaveをインストールする。
どうやらEPELレポジ鳥にパッケージあるらしい。

① Centos6にEPEL
$ wget http://ftp.riken.jp/Linux/fedora/epel/6/x86_64/epel-release-6-5.noarch.rpm
$ sudo rpm -ivh epel-release-6-5.noarch.rpm

② octaveをインストール
$ sudo yum install octave


実質ここまで。。



2、octaveを使ってみる。
liboctaveの基礎

いまいちまだ使えん。


3、octaveで特異値分解
Octave C++で数値計算

※1 SVDを入れると、
「undefined reference to~」ってエラーが要所要所で出る。


※2 octaveをコマンドラインから実行すると、
「octave: error while loading shared libraries: libhdf5.so.6: cannot open shared object file: No such file or directory」というエラーが出る。


yumprovidesで調べても見たが・・・、よくわからん。
$ yum provides \*/libhdf5.so.6
hdf5は最新が入ってる。



調べてみると、同じ症状の人がいた。
シンボリックリンク張ったらとりあえず動いたが。
いいのかこれ。
$ sudo ln -s /usr/lib64/libhdf5.so.7 /usr/lib64/libhdf5.so.6

2011年11月2日水曜日

テキストマイニングに関する論文を読んだ時のメモ

1、文書クラスタリングによるトピック抽出および課題発見
東工大橋本らが行っている研究。
ここでは、大量の文書をクラスタリングソフト(cluto)で系統樹を作成し、
さらにそれを分類することで、大量の情報をわかりやすい形にしようとしている。。

各文章毎に文章から代表的な単語を抽出して単語ベクトルを作成する。

クラスタリングソフトには、文書毎の単語の出現頻度(共起行列?)をわたし、
潜在的意味解析を行っているものと思われる。
bayonとかの中でもそれを行っているんだろうか。

2、社会課題発見のための文書クラスタリングとクラスタ評価指標
1の研究と同じ。「密度」や「中心度」に関してもう少し詳しく説明されている。


3、単語と意味属性との共起に基づく概念ベクトル生成手法
1で使われる単語ベクトルの概念が結構わかりやすく示されている。


4、新聞記事内容と株価変動の関連性の定量的分析
過去の新聞記事内容と株価の変動をひもづけておいて、
今の新聞記事の中から、株価の変動にかかわりそうな
記事を抽出する研究。
共起語に新聞から抽出した単語をそのまま使うのではなく、
単語間の意味的な依存関係を使っているみたい。


5、 主題語からの話題語自動抽出と、これに基づく Web 情報検索
1つの検索キーワード(主題語)から、一定の法則で話題語を抽出し、
主題語と話題語から検索されるWebページの特徴ベクトルと
主題語のみから検索されるWebページの特徴ベクトルを比較し、
近いものを検索結果とする研究。
これによりどの程度精度がよくなるかはわからないが、
面白い研究。

phpからRを使う

方法として見つけたのは2つ。

1、R-php エクステンションを入れる
2、proc_open()でRを呼び出す。


1、R-php エクステンションを入れる
R-phpをインストール・使ってみた

① mysqlとImagemagickを追加する。
$ sudo yum install php-mysql mysql mysql-server ImageMagick ImageMagick-devel

② Rのインストール
CentOS5.5で、yumでRをインストール


③ R-phpをダウンロード・インストール
# wget --content-disposition 'http://dssm.unipa.it/R-php/?cmd=downPack&pack=R-php-1.tar.gz'
# tar -xvzf R-php-1.tar.gz

④ 解凍したディレクトリをapacheのドキュメントルートに移動。。

・・・

これは、phpmyadminみたいなソフトと考えたほうがいい。
やる前にちゃんと読め。。

Rを実行している部分を探した。
(1)R-php/R/pages/home/index.phpで、テキストエリア(codice)にRコードを打たせる。
(2)R-php/R/pages/result/index.phpで、postされたcodiceを受け取り、ファイルに格納。
(3)R-php/R/pages/result/index.phpで、execコマンドをつかい、Rを実行する。

exec("$R_command -q --no-save < codice.txt > result 2>&1");



2、proc_openでRを呼び出す。
R言語とPHPの連携

proc_openでRを実行して、
fwrite、freadでRとやり取りしているみたい。

2011年11月1日火曜日

centos6でrpmforge

RPMforgeをインストール


$ wget http://pkgs.repoforge.org/rpmforge-release/rpmforge-release-0.5.2-2.el6.rf.x86_64.rpm
$ sudo rpm -i rpmforge-release-0.5.2-2.el6.rf.x86_64.rpm

必要に応じて、
$ sudo vim /etc/yum.repo.d/rpmforge.~ 
を修正。