Loading web-font TeX/Math/Italic

October 26, 2013

極大2部クリーク

グラフ G = (V = V_1 \cup V_2, A) の任意の枝がV_1V_2の頂点を結ぶ枝であるとき,Gは2部グラフとよばれる.Gの頂点部分集合 H\subseteq V_1, K\subseteq V_2 に対して,Hの任意の頂点とKの任意の頂点の間に枝があるとき,HKを合わせた頂点集合を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://...

汚いコードだな…

#!/usr/bin/env python
# -*- coding:utf-8 -*-
'''
まとめサイトなどURLに含まれるYouTubeをプレイリストに保存する
$ python youtube_gdata_playlist.py http://...
'''
# 以下要設定
# cf. YouTubeクライアント
# https://developers.google.com/youtube/1.0/developers_guide_python#ClientLogin
####
username = ''
email = ''
password = ''
developer_key = ''
####
import sys
import time
import re
import urllib2
import gdata.youtube
import gdata.youtube.service
from BeautifulSoup import BeautifulSoup
class YouTube(object):
"""
YouTube Data API
https://code.google.com/p/gdata-python-client/
https://developers.google.com/youtube/1.0/developers_guide_python
"""
def __init__(self, username, email, password, developer_key):
self.yt_service = gdata.youtube.service.YouTubeService()
self.yt_service.ssl = True
self.username = username
# ClientLogin for installed applications
self.yt_service.email = email
self.yt_service.password = password
self.yt_service.developer_key = developer_key
self.yt_service.ProgrammaticLogin()
def AddPlaylist(self, title, description=""):
'''
プレイリストを追加する
https://developers.google.com/youtube/1.0/developers_guide_python#AddingPlaylists
Parameters
==========
- title : str
- description : str
Returns
=======
playlist_uri : str
'''
# タイトルと説明を表示
limit = 0
for i in range(len(title)):
if limit > 60:
break
if ord(title[i]) > 255:
limit += 3
else:
limit += 1
tmp_title = title[:i] if i != len(title) - 1 else title
print title # 20字
print description
new_public_playlistentry = self.yt_service.AddPlaylist(tmp_title, description)
if isinstance(new_public_playlistentry, gdata.youtube.YouTubePlaylistEntry):
print 'New playlist added'
return 'http://gdata.youtube.com/feeds/playlists/' + new_public_playlistentry.id.text.split('/')[-1]
else:
return None
def AddVideoToPlaylist(self, playlist_uri, video_id):
'''
プレイリストにビデオを追加する
Parameters
==========
- playlist_uri : str
- video_id : str
'''
playlist_video_entry = self.yt_service.AddPlaylistVideoEntryToPlaylist(
playlist_uri, video_id)
if isinstance(playlist_video_entry, gdata.youtube.YouTubePlaylistVideoEntry):
print video_id
def get_video_ids(url):
'''
urlに含まれるYouTubeのvideo idを抽出する
'''
page = urllib2.urlopen(url)
soup = BeautifulSoup(page)
title = soup('title')[0].string
video_ids = []
targets = [['embed', 'src', 'v\/([-\w]+)'],
['iframe', 'src', 'youtube.com\/embed\/([-\w]+)'],
['a', 'href', 'youtube.com\/watch\?v=([-\w]+)'],
['a', 'href', 'youtu\.be\/([-\w]+)']]
for tag, attr, exp in targets:
for element in soup(tag):
src = element.get(attr)
if src:
result = re.search(exp, src)
if result:
video_ids.append(result.group(1))
tmp = []
for video_id in video_ids:
if video_id not in tmp:
tmp.append(video_id)
return title, tmp
if __name__ == '__main__':
try:
# コマンドライン引数から取得先のURL
url = sys.argv[1]
except:
exit()
# urlのタイトルと含まれるビデオの取得
title, video_ids = get_video_ids(url)
print len(video_ids)
# YouTubeクラスインスタンス
yt = YouTube(username, email, password, developer_key)
# プレイリストの作成
playlist_uri = yt.AddPlaylist(title, title + " - " + url)
# 失敗
failed = []
# リトライ回数
retry = 0
# ビデオ番号
n = 0
# ビデオがあってリトライ回数が10を超えない限り継続
while video_ids and retry < 10:
n += 1
print n,
video_id = video_ids.pop(0)
try:
yt.AddVideoToPlaylist(playlist_uri, video_id)
time.sleep(1)
except gdata.service.RequestError as e:
print video_id
print type(e), e
# 短期間にアクセスしすぎないように...
if 'too_many_recent_calls' in str(e):
video_ids = [video_id] + video_ids
time.sleep(40) # 40秒待機
retry += 1
n -= 1
except:
failed.append(video_id)
print video_id
print sys.exc_info()
# 残り
print 'rest: %s' % ','.join(video_ids)
# エラー
print 'failed: %s' % ','.join(failed)
# プレイリストURI
print playlist_uri



...


  • 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 上の情報からの人間関係ネットワークの抽出


March 31, 2013

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

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

import random
def sort_test():
a = [random.random() for i in range(100)]
b = [random.random() for i in range(100)]
c = dict(zip(a, b))
sorted(c, key=c.get)
view raw get.py hosted with ❤ by GitHub
import random
import operator
def sort_test():
a = [random.random() for i in range(100)]
b = [random.random() for i in range(100)]
c = dict(zip(a, b))
sorted(c.iteritems(), key=operator.itemgetter(1))
view raw itemgetter.py hosted with ❤ by GitHub
import random
def sort_test():
a = [random.random() for i in range(100)]
b = [random.random() for i in range(100)]
c = dict(zip(a, b))
sorted(c.items(), key=lambda x:x[1])
view raw lamb.py hosted with ❤ by GitHub
import random
def sort_test():
a = [random.random() for i in range(100)]
b = [random.random() for i in range(100)]
c = dict(zip(a, b))
d = zip(c.values(), c.keys())
sorted(d)
view raw zip.py hosted with ❤ by GitHub


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は出力(ターゲット)。




分類


  • 入力\mathbf{x}に対する出力(クラス)yを求める関数を訓練データ\mathcal{D} = \{(\mathbf{x}_1, y_1), ..., (\mathbf{x}_n, y_n)\}から学習する。
  • パラメトリックな手法とノンパラメトリックな手法に分けられる(パラメトリックな手法というのはデータの母集団の母数を仮定するもの)。
  • 決定木、ナイーブベイズ分類器、k近傍法、アンサンブル学習...
  • http://en.wikipedia.org/wiki/Statistical_classification
  • http://en.wikipedia.org/wiki/Category:Classification_algorithms

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