October 26, 2013

極大2部クリーク

グラフ $G = (V = V_1 \cup V_2, A)$ の任意の枝が$V_1$と$V_2$の頂点を結ぶ枝であるとき,$G$は2部グラフとよばれる.$G$の頂点部分集合 $H\subseteq V_1$, $K\subseteq V_2$ に対して,$H$の任意の頂点と$K$の任意の頂点の間に枝があるとき,$H$と$K$を合わせた頂点集合を2部クリークとよぶ.$K=\emptyset$, $H=V_1$ である場合,あるいはその逆である場合も2部クリークである.ある2部クリークが他の2部クリークに含まれないとき,その2部クリークを極大2部クリークとよぶ (via 宇野 毅明, 有村 博紀, 浅井 達哉, 極大2部クリークの高速列挙法とデータマイニングへの応用, 夏のLAシンポジウム, 2003年7月)


(v0,v1,v2,v5,v6), (v2,v5,v6,v8), (v2,v3,v8), (v3,v7,v8,v9), (v3,v4,v9)がそれぞれ極大2部クリーク.

program codesよりLCM ver. 5.3をダウンロード.使い方はlcm readmeに.ここでは極大2部クリークの計算だけ利用する.以下上図の例.各行は各ノードの隣接リスト.たとえばノード0には5,6へのエッジがあることを示す.

% cat input
% ./lcm53/lcm CI input 1 output
5 6
5 6
5 6 8
7 8 9
9

結果は以下.最初の2行はHが空集合の場合か.これら以降をみると「6,5」と「0,1,2」などが極大2部クリークになっていることがわかる.

% cat output

 0 1 2 3 4
6 5
 0 1 2
9
 3 4
8
 2 3
8 6 5
 2
7 9 8
 3

April 27, 2013

KDD Cup 2013 - Author-Paper Identification Challengeのメモ

KDD Cup 2013のタスクは2つ。その1つはMicrosoft Academic Search (MAS)の文献検索での著者の名前の曖昧性がテーマ。

MASの文献は

- 同じ著者が色んな名前で登録されてる
- 違う著者が同じ名前で登録されてる

という名前の曖昧性のせいで文献に対して著者がちゃんと割り当てられない。そこでタスクは、ノイズを含んだ著者と論文の組み合わせを入力して、本物の著者と論文の組み合わせを出力するというもの。

色々準備されてるのでとっかかりやすい。

- 説明 / Description - KDD Cup 2013 - Author-Paper Identification Challenge - Kaggle
- チュートリアル / git://github.com/benhamner/Kdd2013AuthorPaperIdentification.git
- もう一方 / Data - KDD Cup 2013 - Author Disambiguation - Kaggle

データ


詳細はData - KDD Cup 2013 - Author-Paper Identification Challenge - Kaggle



- paperauthor : 12775821
- trainconfirmed : 123447
- traindeleted : 112462
- validpaper : 90088

- author : 247203
- paper : 2257249
- journal : 15151
- conference : 4545

入出力


入力

著者のIDと文献のIDのリスト

# SELECT * FROM validpaper LIMIT 5;
 authorid | paperid 
----------+---------
       55 |    2507
       55 |   15471
       55 |   19294
       55 |   20444
       55 |   24074
(5 rows)

出力

著者のIDとスペース区切りの文献のID

% head -n2 Submissions/basicCoauthorBenchmarkRev2.csv
AuthorId,PaperIds
2080775,2200312 1047104 280462 1467879


チュートリアル


benhamner/Kdd2013AuthorPaperIdentification · GitHubに載っているチュートリアルで。scikit-learnRandom forestの実装を使っている。trainconfirmedを正例、traindeletedを負例として学習し、validpaperを判別している。

PostgreSQLのバックアップを配布してくれているので、PostgreSQLのインストール。
brew install postgresql
データベース作成。
createdb Kdd2013AuthorPaperIdentification
復元。
pg_restore -Fc -U [ユーザ名] -d Kdd2013AuthorPaperIdentification dataRev2.postgres
起動。
postgres -D /usr/local/var/postgres
確認。
psql -l
接続。
psql Kdd2013AuthorPaperIdentification

PythonBenchmark内のSETTINGS.jsonのファイル出力先とuser名を変更しておく。

実行のために必要なpsycopg2のような必要なモジュールはエラーを見て何が足りないか確認して適宜pipでインストール。
sudo pip install psycopg2

- 8.7.1. sklearn.ensemble.RandomForestClassifier — scikit-learn 0.14-git documentation

特徴量

authoridとpaperidを基に以下の値をテーブルから取ってくる。

- AuthorJournalCounts (著者のジャーナル数)
- AuthorConferenceCounts (著者の会議数)
- AuthorPaperCounts (著者の文献数)
- PaperAuthorCounts (文献の著者数)
- SumPapersWithCoAuthors (共著者との文献数の和)

ターゲット

trainconfirmedが1、traindeletedが0。

パラメータ
RandomForestClassifier(n_estimators=50, 
                       verbose=2,
                       n_jobs=1,
                       min_samples_split=10,
                       random_state=1)

結果

0.85078

ちなみに何も学習せずだと

0.67551

April 5, 2013

PythonでWebサイトのビデオを抽出してYouTube Data APIクライアントでプレイリストに登録する

YouTube系まとめサイトの動画を流しっぱなしにしておくために,以前herokuにRailsでpost-tube.satomacoto.comというのを自分用につくった.が,無料で使えるデータベースの制限を超えちゃってたので,WebサイトのYouTubeへのリンクを抽出してYouTubeのPlaylistに登録するPythonのスプリクトをやっつけで書いてみた.こんな風にプレイリストを作成する→http://www.youtube.com/user/stmct/videos.忘れたときのためにメモ.


Google Data API


Google Data APIを使ってYouTubeのプレイリスト作成や動画登録を行う.Pythonから操作するためにgdata-python-clientが用意されている.このサイトからダウンロードした gdata-...zip を解凍したら

sudo python setup.py install

でインストール.

使い方は

Developer's Guide: Python - YouTube — Google Developers


APIキーの取得


http://code.google.com/apis/youtube/dashboard/でAPIキーを取得する.


ClientLogin


ローカルで動かすのでClientLoginで認証する.認証はPlaylistの作成や動画の登録に必要.下記のスクリプトでは以下の部分を設定する.YouTubeのアカウント名は http://www.youtube.com/user/stmct だったらstmctにあたるところ.Googleを2段階認証にしている場合はアプリケーション固有のパスワードを生成する.

username = 'YouTubeのアカウント名'
email = 'APIキーを取得したGoogleのアカウント名'
password = 'Googleのパスワード'
developer_key = '取得したAPIキー'


コード


使い方

python youtube_gdata_create_playlist.py http://...

汚いコードだな…




...


  • NAVERみたいに次のページがある場合に対応するか
  • 人がまとめたものを使うってのはまずいのかな
  • post-tube.satomacoto.comってどうやってつくったんだっけかな
  • 連続再生だけが目的じゃなくてサイトごとにどんなビデオが貼り付けられているかとか自分の再生履歴やらお気に入りやらで何かしようとか思ってたんだっけ
  • プレイリストの履歴は取れないからな…

April 2, 2013

語/語の組み合わせの大人らしさ

検索エンジンにクエリを投げて,セーフサーチのオン/オフを切り替えたときに返ってきた件数をうまいことして,語/語の組み合わせの大人度合いが測れないかと思ったけどあんまりうまくいかなかった.


イメージ


すっごく単純にすると

  • 大人な語
    • 語がどれほど大人か
    • $$大人(眼球) = \log \frac{n(眼球, off)}{n(眼球, strict)}$$
    • ただしn(q,a)はクエリqのセーフサーチの設定aのoff/moderate/strictのとき結果件数.検索結果が0件の場合もあるだろうから分母には1足しておいてもいい.
  • 大人な組み合わせ
    • 語を組み合わせることでどれくらい大人っぽくなるか
    • $$大人組(目玉, 玉子) = \log \frac{n(目玉 and 玉子, off)}{n(目玉 and 玉子, strict)} - 大人(目玉) - 大人(玉子)$$

みたいな感じ.あんま考えてないのでこれで比較ができるかわかんないけど.大人がゲシュタルト崩壊…


でも


普通に考えてセーフサーチが強いほうが検索結果少ないだろ,と思ってたら,
眼球 - Google 検索
セーフサーチ: オフ
約 57,800,000 件 (0.20 秒) 
眼球 - Google 検索
セーフサーチ: 強
約 71,800,000 件 (0.19 秒) 
セーフサーチ強のほうが多いこともある…どういうことだってばよ



Bingもあんま変わらん.そういうもんなのかな.


ちなみにWebの検索結果件数を使って人間関係を抽出している論文(件数だけじゃないけど)→Web 上の情報からの人間関係ネットワークの抽出


XVIDEOS' Entire Video Databaseでk近傍法

k近傍法(k-NN)はクエリと似ているk個の訓練データからクラスを決定する手法.最近傍探索のアプリケーションのひとつ.すごく単純.実装もすごく簡単.回帰や次元削減にも使える.ただ,単純に線形探索する場合,データの数が増えるとその分計算も大変(O(Nd); Nは訓練データ数, dは次元数).なので色々高速化・効率化のアルゴリズムも提案されている(→最近傍探索2011 | Preferred Research).

が,250万件くらいなので線形探索でk近傍法を試してみる.クロスバリデーションしようと思ったら大変だけど...結果が面白そうだったら改良手法も試す.

k近傍法.k=3だったら赤,k=5だったら青に分類される(Wikipediaより)

  • 類似度はJaccard係数を使います.
    $$J(A,B)=\frac{|A \cap B|}{|A \cup B|}$$
  • データはMongoDBに突っ込んでからpymongoで操作します.

MongoDBとpymongo


まずターミナルからMongoDBの起動.

$ mongod

pymongoでxvideosデータベースのvideosコレクションにxvideos.com-db.csvのタイトルとタグ,ジャンルをぶち込む.



k近傍法


この例だと,['shower', 'morning', 'toy', 'sexy']というタグに対して近いデータ10件を集めて,多数決でのジャンルを決める.ちなみに結果は「Sexy」.




関連


March 31, 2013

XVIDEOS' Entire Video Databaseのタグの頻度と共起

こういう単語載せたらブログ消されんのかな.まあいいか.2013/3/29にダウンロードしたファイル.関連→XVIDEOS' Entire Video Databaseのタグからトピックモデルの構築

XVIDEOS' Entire Video Database
http://info.xvideos.com/db/

xvideos.com-db.csvは「;」区切りで「video URL;title;duration;thumb URL;embed code;tags;genre」.tagsは「,」区切り.

頻度上位20件



共起頻度上位20件



頻度の計算



共起頻度の計算


XVIDEOS' Entire Video Databaseのタグからトピックモデルの構築

xvideos.com-db.csvのタグからLDAでトピックモデルを構築してみた.

XVIDEOS' Entire Video Database
http://info.xvideos.com/db/

xvideos.com-db.csvは「;」区切りで「video URL;title;duration;thumb URL;embed code;tags;genre」.tagsは「,」区切り.2013/3/29にダウンロードしたものでタグが付いているものの数は以下.

文書数: 2,561,079
単語種類数: 90,926

タグをドキュメントとしてLDAでトピックモデルを構築.最初MALLETを使ってみようとしたけどOutOfMemoryErrorで断念.今回は

GibbsLDA++ A C C++ Implementation of Latent Dirichlet Allocation (LDA) using Gibbs Sampling for Parameter Estimation and Inference
http://gibbslda.sourceforge.net/

を利用.つかいかたはsatomacoto: LDAの実装を試してみる

まずドキュメントを整形.trndocs.datを作る.フォーマットは以下.tagsの「,」をスペースに置き換えた.

% head trndocs.dat
2561079
gay
montenegro andrea
gay
sexy masturbation asian what waiting
lesbian movie brunettes most sensitive
porno amateur casero guarras
blonde babe masturbating movie sunset
blonde masturbation shower megan morning
teen hardcore blowjob amateur

モデル構築.trndocs.datはmodels/xvideos以下に置く.

src/lda -est -alpha 0.5 -beta 0.1 -ntopics 100 -niters 1000 -savestep 100 -twords 20 -dfile models/xvideos/trndocs.dat

途中で止めちゃったので再開.

src/lda -estc -dir models/xvideos -model model-00100 -niters 1000 -savestep 100 -twords 20

14時間位かかった.2.7GHz Intel Core i7.

結果は以下リンク先に.トピックの代表的な語だけ.

https://gist.github.com/satomacoto/5275776#file-model-final-twords

うまくいってるのかな...とりあえず,たとえば36番目のトピックに日本が多かったり,たとえば素人は全体的に出現しているけど同じトピックで強い語が若かったり熟れてたり,みたいな傾向は見られる.モデル構築を行うことで$P(word|topic)$,$P(topic|document)$も取れるので分類にはもちろん他のことにも...匿名でいいからユーザの履歴も公開されたら推薦やらにも...

ジャンルも付いているようなので教師データとして使えるかも.ちなみにジャンルらしきものは45種類あった.各ドキュメントに対してジャンルが振られている.ただし結構な割合でUnknow.

lesbian,toying,masturbating,from,teenies;Only;Girls
mature,garden,downblouse;Mature
milf,nikki,ex,payback;Milf
montenegro,andrea;Unknow
panties,brunette,fetish,pretty,girlgasms;Brunette

たとえばlesbian,toying,masturbating,from,teeniesってタグにはOnly Girlsというジャンルが付いている.あ,トピック数適当に決めちゃったけど,ここらへんも考慮すればよかったか.ユニークなジャンル名もリンク先に.

Pythonの辞書をvalue値でソートするコードの実行時間の比較

get,lambda,itemgetter,zipを使ったvalue値でのソートを比較してみた.
以下コード.



timeitで計測.

>>> import timeit
>>> timeit.timeit(stmt='get.sort_test()', setup='import get', number=10000)
0.6642911434173584
>>> timeit.timeit(stmt='itemgetter.sort_test()', setup='import itemgetter', number=10000)
0.6961650848388672
>>> timeit.timeit(stmt='zip.sort_test()', setup='import zip', number=10000)
0.6995840072631836
>>> timeit.timeit(stmt='lamb.sort_test()', setup='import lamb', number=10000)
0.7502970695495605

ただし
  • zipの場合(value, key)のリストになる
  • getの場合keyのリストになる(value値は返さない)
に注意.

よく見かけるのはlambdaを使うものだが,同じ結果を得たかったらoperator.itemgetterを使うほうが少し早い.上位だけ取ってきたいときはgetが早いかも.

他にもやり方があるだろうか.

March 27, 2013

bl.ocks.orgで青空文庫で変なルビ使いをする作者の関係の可視化

bl.ocks.orgを使って,青空文庫のルビを抽出し,「漢字《ひらがな》」でないルビを見つけ,同じようなルビの使い方をしている作者の関係を可視化してみた.「変な」は語弊があるかも.D3.js.


Authors Relationships based upon Not-kanji-hiragana Rubis
http://bl.ocks.org/satomacoto/5251189
このページは以下のGistから生成
https://gist.github.com/satomacoto/5251189

bl.ocks.orgはGitHub Gistビューア.Gistにいくつかのファイルを置くとwebページとして見れるようになる.Gistの基本構成は以下.

  • index.html
  • README.md
  • thumbnail.png

index.htmlに表示させるソースコード,README.mdにMarkdown形式で説明を記述,thumbnail.pngGist一覧のためのサムネール画像.Gistに他のファイルを置くと相対的にリンクを張ることができる.絶対パスも記述可能.Gistをブログのように使えるかも.


作者の同じようなルビ使い関係は,たとえば「亜米利加《アメリカ》」というルビを二人の作者が振っていたらその作者同士に関係がある,と定義した.重み付けなど詳細はまた他で.可視化したのはすべての関係ではない.同じようなルビの使い方をしている作者の関係からなんか他の作者の関係(同じ時代とか思想とか)見えないかなと考えていたのだけどどうだろうか.ちなみに変わったルビ使いの例を少しだけ挙げると
003659 000050 仏蘭西 フランス
046340 001234 亜米利加人 ヤンキー
048416 000050 遍路芸人 ジプシイ
050424 001421 辯證的な性質 デイヤレクテイツシエナツール
000085 000879 童貞聖麻利耶様 ビルゼンサンタマリヤさま
001317 000125 吾れ直ちに悪魔と一つになるを誰が妨ぎ得べきや ヴァス・ヒエルテ・ミッヒ・ダス・イヒス・ニヒト・ホイテ・トイフェル
といったようなものがある.クラスタリングして色変えればよかったかも.


あと4日で無職\(^o^)/

February 26, 2013

機械学習に関するメモ

機械学習の目的は与えられたデータ$\mathcal{D}$から関数$$y = f(\mathbf{x})$$を求めること。ただし、$\mathbf{x}$は入力、$y$は出力(ターゲット)。




分類



Classification



クラスタリング



Clustering

回帰



Regression




次元削減



Dimension Reduction



TODO


  • 具体的な手法の追記
  • 詳細の追記
  • アプリケーションの追記
  • 実装例
  • 各手法を特徴に応じて表に整理

Bloggerの画像をRetinaディスプレイに対応させる

デフォルトのツールを使ってPicasaウェブアルバムにアップした場合、画像のサイズを指定して、サムネイル画像アドレスの.../s(.*?)/...の数値を指定したサイズの倍くらいにしたら綺麗になった。

width="320"と指定したら、.../s640/...とする。

違い、

変更前

変更後

わかりにくいか。

Resolutionの設定はBest for Retina display。ScaledのLarger Textに対応するためには3倍くらいの数値を使った方がいいかも。Change Resolution.appなどを使ってたら別に問題ないのかな。

January 18, 2013

Macで京都大学テキストコーパスの変換

京都大学テキストコーパス - KUROHASHI-KAWAHARA LAB

でKyotoCorpus4.0.tar.gzをダウンロードして解凍してREADME通りに実行.

でもMac OS X 10.7.5だとそのままコーパスをつくろうとすると
euc-jp "\xA4" does not map to Unicode at ./src/dupli.pl line 9, line 163.
みたいなエラーが出ちゃう.そこで以下の手順でちょっと手を加えます.

1. 同じフォルダにmai1995.txtをコピー.毎日新聞1995年版CD-ROMのファイルはmai1995.txt (Oct 6, 2011 11:37AM)でした.

2. 文字コードと改行コードとファイル名の変換

nkf -s -Lu mai1995.txt > mai95.txt

3. src/format.plsrc/num2KNP.plについてuse open ":std";を追加

...
use open IO => ':encoding(euc-jp)';
use open ":std";
...

4. 実行

./auto_conv -d .


参考
- mizlog 京都大学テキストコーパス on Lion