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」.




関連