Gephi,Rを用いた邦楽有名アーティストの歌詞類似度可視化
概要
日本で最も売れた邦楽アーティストの歌詞を対象に、頻出単語をランク付けしました。また、アーティスト間の類似度を求め、可視化してみました。
検証動機
- 売れているアーティストの歌詞の特徴を知りたい
- 歌詞の類似度が高いアーティストを知りたい
データ収集・類似度評価
http://chanz.jp/nitoru/artist.php?name=Mr.Children
ここで保存したデータを参照できます(例：Mr.Children)
- 各アーティスト間において、名詞列に対するコサイン類似度を求める
相関係数･COS類似度 - メモ帳の日記
コサイン類似度の詳細については上記参照
得られた結果
CD総売上Top100邦楽アーティストにおける総頻出単語 Top10
| 順位 | 単語 | 回数 |
|---|---|---|
| 1 | 君 | 15630 |
| 2 | あなた | 10192 |
| 3 | 人 | 8977 |
| 4 | 僕 | 7831 |
| 5 | 今 | 6104 |
| 6 | 心 | 6068 |
| 7 | 夢 | 6033 |
| 8 | 愛 | 5834 |
| 9 | 日 | 5612 |
| 10 | 何 | 5515 |
これ以降の詳細
http://chanz.jp/open_data/word_count_top
頻出ワードを使えば僕にも作詞ができる気がしてきた（できません）
類似度が高いアーティストTop 10
| 順位 | アーティスト | アーティスト | コサイン類似度 |
|---|---|---|---|
| 1 | v6 | 嵐 | 0.9650725424622 |
| 2 | TOKIO | 関ジャニ∞ | 0.96329616863073 |
| 3 | 中森明菜 | 工藤静香 | 0.96068893943338 |
| 4 | TOKIO | v6 | 0.95958524728511 |
| 5 | breakerz | 東方神起 | 0.95955742979729 |
| 6 | w-inds. | 山下智久 | 0.95897504543606 |
| 7 | CHEMISTRY | 嵐 | 0.95868950581346 |
| 8 | Lead | 嵐 | 0.95867019240138 |
| 9 | w-inds. | 東方神起 | 0.95831674701062 |
| 10 | v6 | 関ジャニ∞ | 0.95696708090147 |
J事務所の歌詞はだいぶ似通っている模様
これ以降の詳細
http://chanz.jp/open_data/cos_top
あるアーティストに似ているアーティストを検索できるようにしました
コサイン類似度検索
感想その他
名詞とコサイン類似度だけに頼って可視化したものの、アーティスト間の傾向がある程度把握できたかと思う。感覚を定量化して可視化するのはやっぱり面白い。あと、見せるデータを作るのは難しい。クラスタ分析はfuture work
ThinkPad x240 ディスプレイの分解
不具合
- 画面に何も表示されない。
- 電源は着く。
必要なもの
- 細いマイナスドライバー
- 勇気
手法
- ディスプレイのカバーの亀裂にマイナスドライバーを突っ込む
- 接触の確認
結果
- 治る
AWS EMR上でGiraphを動かそう
Version
- Hadoop 1.0.3
- Giraph 1.0
ローカル設定
mvnがなかったら入れる。versionが表示されれば良し。
$ mvn -version Apache Maven 3.2.2 Maven home: /path/to/maven Java version: 1.6.0_65, vendor: Apple Inc. Java home: /path/to/java Default locale: ja_JP, platform encoding: SJIS OS name: "mac os x", version: "10.8.5", arch: "x86_64", family: "mac"
ビルド
http://giraph.apache.org/Apache Download Mirrors
Giraph1.0を手に入れ解凍。Giraphディレクトリに移動。ビルド。
mvn package -P hadoop_1.0 -Dhadoop.version=1.0.3 -DskipTests
AWSの設定
- S3でログフォルダを作成する
- EC2でkeypairを作成する
EMRの設定
Create Cluster
- Cluster Configuration [S3ログフォルダを指定]
- Software Configuration [AMI version 2.4.7を選択] (Hadoop 1.0.3であれば良いはず）
- Hardware Configuration [Master,Core m1.small : 一台] (例)
- Security and Access [EC2 key pairで先に作ったkeyparを選択] (SSHするのに必要）
- IAM Roles [EC2 instance profile : Proceed without roleを選択]
- Bootstrap Actions [Configure Hadoop : Configure and Add]
--mapred-key-value mapreduce.job.counters.limit=1200 --mapred-key-value mapred.tasktracker.map.tasks.maximum=8 --mapred-key-value mapred.map.tasks=4
- 他はいじらずにCreate
Master public DNSをメモする
SSH
ビルドしたGiraphを圧縮してSCP(本当はS3にあげていたものをSSHして解凍すべきっぽい）
$scp -i yourkeypair.pem giraph.tar.gz hadoop@[Master public DNS]:
SSHしてPageRankBenchmarkを実行
$ ssh hadoop@[Master public DNS] -i yourkeypair.pem Welcome to Amazon Elastic MapReduce running Hadoop and Debian/Squeeze. ip-:~ $ tar zxvf giraph.tar.gz ip-:~ $ hadoop jar giraph/giraph-examples/target/giraph-examples-1.0.0-for-hadoop-1.0.3-jar-with-dependencies.jar org.apache.giraph.benchmark.PageRankBenchmark -e 1 -s 3 -v -V 50 -w 1
近々ShortestPathのサンプルでどれだけスケールするか試してみる。
ICPC 2014 国内予選参加記
★メンバー
@no15_rennne :M1
@inu_hir0shi :M1
@zr_4 :M1
という学内平均年齢最高チームで参加しました。
★タスクの割り当ては
@inu_hir0shi コーダー
@no15_rennne アルゴリズム、ペアプロ
@zr_4 アルゴリズム、ペアプロ
数年一緒にやってきて最適に近い配置になっているはず。
開始前に練習していた部屋が授業で使われているという軽アクシデントに見舞われるも無事スタート
☆A問題
16:56にAC。doubleにハマって涙目になってた。少し泣いた。
#include <iostream> #include <cmath> using namespace std; #define EPS 1e-9 int main () { int x, y, s; while (cin >> x >> y >> s, x||y||s) { int ans = 0; for (int i = 1; i <= s-1; i++) { for (int j = 1; j <= s-1; j++) { double p = ((100+x)/100.0); int pre = (int)floor(p*i+EPS) + (int)floor(p*j+EPS); //cout << i << " " << j << " " << pre << endl; if (pre == s) { double t = ((double)(100+y)/100.0); ans = max<int>(ans, (int)floor(t*i+EPS)+(int)floor(t*j+EPS)); } } } cout << ans << endl; } return 0; }
☆B問題
17:12にAC。特筆すべきことなし。
#include <iostream> #include <cmath> #include <vector> int H, W = 5; using namespace std; int main () { while(cin >> H, H){ vector< vector<int> > cells(H); for (int i = 0; i < H; i++) { for(int j = 0; j < W; j++){ int a; cin >> a; cells[i].push_back(a); } } int ans = 0; while (1) { /*cout << endl; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << cells[i][j] << " "; } cout << endl; } cout << endl;*/ bool ok = false; vector< vector<int> > next = cells; for(int i = 0; i < H; i++){ for(int j = 0; j < W-2; j++){ if (cells[i][j] != 0 && cells[i][j] == cells[i][j+1] && cells[i][j+1] == cells[i][j+2]) { next[i][j] = next[i][j+1] = next[i][j+2] = -1; ok = true; } } } if (!ok) break; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (next[i][j] == -1) { ans += cells[i][j]; next[i][j] = 0; } } } bool update = true; while (update) { update = false; for (int i = 0; i < H-1; i++) { for (int j = 0; j < W; j++) { if (next[i][j] != 0 && next[i+1][j] == 0) { next[i+1][j] = next[i][j]; next[i][j] = 0; update = true; } } } } cells = next; } cout << ans << endl; } return 0; }
☆C問題
18:15にAC。ぱっと見で軽実装な解法が浮かばなかったので完全に二人に任せました。
境界となる点を列挙して，円を0.0005刻みで可能な限り移動する．無駄な点省くのをさぼったら実行に時間がかかった。
#include <iostream> #include <cstdio> #include <complex> #include <vector> #include <map> #include <algorithm> using namespace std; typedef complex<double> P; bool bad (int r, double t, const vector<P> & vp) { P center(50, -r + t); for (int i = 0; i < vp.size(); i++) { if (abs(vp[i]-center) < r) { return true; } } return false; } int main () { int r, n; while (cin >> r >> n, r||n) { vector< vector<int> > field(100, vector<int>(100, 0)); for (int i = 0; i < n; i++) { int xl, xr, h; cin >> xl >> xr >> h; xl += 50; xr += 50; for (int i = 0; i <= h; i++) { for (int j = xl; j < xr; j++) { field[i][j] = 1; } } } /* for (int i = 0; i <= 5; i++) { for (int j = 40; j < 60; j++) { cout << field[i][j] << " "; } cout << endl; } */ vector<pair<int,int> > vp; int dx1[] = {1, 1, 0}; int dy1[] = {0, 1, 1}; int dx2[] = {0, -1, -1}; int dy2[] = {1, 1, 0}; for (int i = 0; i < field.size()-1; i++) { for (int j = 1; j < field[0].size()-1; j++) { bool ok = false; if (i != 0 && field[i][j] == 0) continue; for (int k = 0; k < 3; k++) { int ny = i + dy1[k]; int nx = j + dx1[k]; if (field[ny][nx] == 0) ok = true; } if (ok) vp.push_back(pair<int,int>(i, j+1)); ok = false; for (int k = 0; k < 3; k++) { int ny = i + dy2[k]; int nx = j + dx2[k]; if (field[ny][nx] == 0) ok = true; } if (ok) vp.push_back(pair<int,int>(j, i)); } } sort(vp.begin(), vp.end()); vp.erase(unique(vp.begin(), vp.end()), vp.end()); vector<P> vc; for (int i = 0; i < vp.size(); i++) { vc.push_back(P(vp[i].first, vp[i].second)); } for (double t = 0; ; t += 0.0005) { if (bad(r, t, vc)) { printf("%.5lf\n", t); break; } } } }
☆D問題
18:33にAC。C問題を二人が解いている時に解法を考えていた。
全探索してチェックするだけ。解法をすり合わせても@inu_hir0shiが腑に落ちないところがあるらしかったけどとりあえず実装。実装早かった。手元の実行は遅かったので多少ヒヤヒヤした。
#include <string> #include <set> #include <iostream> #include <cstdio> #include <complex> #include <vector> #include <map> #include <algorithm> using namespace std; typedef complex<double> P; int main () { string s; while (cin >> s, s!="#") { int n = s.size(); set<string> ss; vector<int> mask(26); for (int i = 0; i < 26; i++) { for (int j = 0; j < n; j++) { if (s[j] == char(i+'a')) { mask[i] |= 1<<j; } } } for (int i = 0; i < (1<<n); i++) { if (__builtin_popcount(mask[s[i]-'a'] & j string t; for (int j = 0; j < n; j++) { if ((1 << j) & i) { t += s[j]+1; } else { t += s[j]; } } ss.insert(t); //cout << t << endl; } vector<string> ans; for (set<string>::iterator it = ss.begin(); it != ss.end(); it++) { string tmp = *it; for (int i = 1; i <= 25; i++) { for (int j = 0; j < n; j++) { if (tmp[j] == char(i+'a')) { tmp[j] = char(i+'a'-1); break; } } } if (tmp == s) ans.push_back(*it); } cout << ans.size() << endl; if (ans.size() <= 10) { for (int i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } } else { for (int i = 0; i < 5; i++) { cout << ans[i] << endl; } for (int i = ans.size()-5; i < ans.size(); i++) { cout << ans[i] << endl; } } } }
この時点で、学内３位で予選通過が危ぶまれていた。E頑張ろうという雰囲気に。
☆E問題
終了６分前である19:24にAC。まず@inu_hir0shiが思いついた解法を実装する。その間に@no15_rennneと@zr_4がいろいろ意見を言い合う。そこで2点対経路長解法を発見。木上のパスは一意に定まるというそれ自明だけどグラフ理論ゼミで証明やった！という感じのやつ。実装はある程度できていたコードをくっつけて無事AC。喜びでPCの前で踊っていた。
#include <iostream> #include <map> #include <algorithm> #include <vector> using namespace std; struct E { int dst, cost; E (int d, int c) { dst = d; cost = c; } }; int dfs (const vector< vector<E> > &G, const vector<bool> &leaf, int v, int pre) { int res = 0; //cout << "v " << v << " pre" << pre << endl; for (int i = 0; i < G[v].size(); i++) { if (G[v][i].dst == pre) continue; if (leaf[G[v][i].dst]) res += G[v][i].cost; else { res += dfs(G, leaf, G[v][i].dst, v) + G[v][i].cost*3; } } return res; } int main () { int n; while (cin >> n, n) { vector< vector<E> > G(n); vector< vector<int> > d(n, vector<int>(n, 1<<28)); vector<int> t(n), v(n); for (int i = 1; i <= n-1; i++) { cin >> t[i]; t[i]--; } for (int i = 1; i <= n-1; i++) { cin >> v[i]; } for (int i = 1; i <= n-1; i++) { G[i].push_back(E(t[i], v[i])); G[t[i]].push_back(E(i, v[i])); d[i][t[i]] = d[t[i]][i] = v[i]; } for (int i = 0; i < n; i++) d[i][i] = 0; vector<bool> leaf(n); for (int i = 0; i < n; i++) { if (G[i].size() == 1) leaf[i] = true; } int sum = 0; for (int i = 0; i < n; i++) { if (!leaf[i]) { sum = dfs(G, leaf, i, -1); break; } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int ans = sum; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (leaf[i] || leaf[j]) continue; ans = min(ans, sum - d[i][j]); } } cout << ans << endl; } }
★結果
＞ http://icpc.iisf.or.jp/2014-waseda/domestic/results/
5完23位で恐らく国内予選通過。大学で２チーム国内予選通過が目標だったので目標達成。nekonyaso強い。
★所感
2年連続学内2位（共に30位くらい）で予選落ちしていたため、今年こそはという気分だった。@no15_rennneと@inu_hir0shiは今年が最後のICPCだったため、引退が伸びてよかったかなというところ。チーム戦は最高に楽しい！
Nonseparable Graphs
Cut Vertex:
ここで，c(G)はGの連結成分の個数
定理
頂点数が３以上の連結グラフがcut vertexを持たない⇔任意の二頂点がinternaly disjoint pathで連結
ここで，internaly disjoint pathとは，端点以外で共通の頂点を持たないpath
Separation:
ただ一つの頂点を共有して持つ非空で連結の二つの部分グラフへの分解のこと
定理
cut vertex⇒separating vertex
cut vertex⇔separating vertex (looplessの場合)
Nonseparable Graph:
連結かつseparating vertexが存在しないグラフのこと
定理
連結グラフがnonseparable⇔任意の二つの辺がある一つの共通のcycleに存在する
Blocks:
A subgraph which is nonseparable and is maximal with respect to the this property.
命題
a) Gの任意のブロックはたかだか一つの共有点を持つ
b) GのブロックはGの分解を成す
c) Gの各々のcycleは，Gのブロックに含まれる
ICFPC 2013 参加記
@perokugi,@inu_hir0shi,@zr_4でチーム参加しました。
メンバーの方は何か記事に不備があれば教えてください。
一日目
・開始直後
問題をなんとなく理解。
関数値を評価するコード、関数を生成するコードを書き始める。
関数の生成は、DPで全列挙していく方針。
関数値評価は、なんらかの関数言語とC++の２パターンで実装してみることに。
・昼頃
構文解析と関数生成するコードが割と書きあがる。
この時点でチーム内のプログラムはすべてC++で統一することが決定される。
かつ大でお弁当を買って場所を計算機室から@zr_4宅に移動。
・夕方頃
関数生成と値評価が成功。fold,tfoldの処理はこの時点では実装せず。
train,myproblemsが自動処理できるようになる。
二人の実装が爆速なため、コードを書く余地がなかった。
与えられるsizeと演算子でなくても正答することが判明する。
ヒューリスティック局所改善は難しそう、みたいな会話をする。
正攻法で突き進むことにする。
・21時頃
size10程度までなら正答が得られるようになるが限界が見える。
「foldとif0で枝出来るやろ」と希望的観測を持つ。
tfoldの実体が未だわからない。foldのサブセットっぽいからfoldの実装すればとりあえず動きそう。foldの処理を追加。でかい問題が解けるようになった。
・深夜
全列挙できない場合に上限以上の探索を打ち切るコードでsize30が解ける。式簡約の力。
いけるんじゃね！？みたいな雰囲気になる。
・3時頃
そろそろ回し始めないとlightningまでに５００問解き終わらなそう。
そもそも５００問じゃなくて、１０００問以上あった（絶望）
・5時頃
一台で実行し、落ちた問題をもう一台で救済しつつmyproblemsを解き始める。
fold,if0をねじ込む、探索上限を大きくすることで、大抵救済できた。良い緊迫感。
・7時頃
9時までに全て消化するために探索サイズを小さくして計算機3台で回し始める。
・9時頃
チームメイト二人寝てた。850点ちょいgot。結局200問近く解き残してしまった。
二日目
驚くべきことに（！）、何もしていない。どうしてこうなった。
三日目
・昼頃
自宅に再集合する。枝刈りと高速化について考える。
演算子を文字列ではなく、文字で置き換えることに。
ドモルガン、式展開の同値関数の枝刈りを考える。
ボーナス問題は値として枝刈りできそう、みたいな会話をする。
・夕方
高速化の実装を終える。式の体裁がとてもカオスであるが、割と速くなった。
ボーナス問題を倒しにかかる。
if0 (and e1 1) e2 e3の形をしているっぽい。
e2,e3の組み合わせがevalの値を全てみたしうるかどうかで枝刈り。
@inu_hiroshiが実家に帰る。
・20時頃
@perokugiが値としての枝刈りをクラスタリングとかいって実装する。
計算量むっちゃ落ちた。安定してボーナスsmallが解けそう。
・21時頃
解き残した問題と、ボーナスのsmallを解き始める。
・22時頃
ノーミスでボーナスsmallが解き終わる。残ってた問題も8割方解けた。強い。
・深夜
ボーナスlargeを倒しにかかる。
if0 e1 e2 e3のe2,e3がより多くのevalを被覆するように、e2,e3をヒューリスティックに保持。
上手くいかず。
どうやら、同じ性質をもった関数をたくさん保持してしまってるらしい。
大きいボーナスで全然大きいボーナスが得られない悲しみ。
・6時
「我々は、この7時間、なんの成果も得られませんでしたァ！！」
・7時
絶望しつつボーナスlargeを既存のコードで実行し始める。1/5くらいの確率で正答
・9時
終了。
反省点
lightningを精度が低いまま半端に解いて、得られる得点の上限を削ってしまった。
一度生成した式を保存、同値関数の削除を行うべきだった。
良かった点
チームとして意思疎通が取れていたため、停滞することがなかった（最後の7時間以外）
結果
lightning 850ちょい
本選 1250ちょい
追記
lightningで優勝したらしい
行列ベースのベルマンフォード法
A:コスト隣接行列
d:各頂点への最短距離
・メインコードから呼び出すminplus関数の定義
function x = minplus(d,A) [M,N] = size(A); for i = [1:N] x(i) = min(A(:,i)' + d); endfor endfunction
※以下の記法は通常の積をminplusとして置き換えて考える。
dn = d0*A^nを二通りのパターンで更新する。
1. dn = (d0*A^(n-1)) * Aとして(d0*A^(n-1)) を更新していくコード
function algebraicbellmanford(A,s) [M,N] = size(A); for i = [1:N] d(i) = inf; endfor d(s) = 0; for j = [1:N + 1] d = minplus(d,A); endfor if all(d == minplus(d,A)) == 0 "A negative-weight cycle exists" endif endfunction
2. A^nを先に更新するコード
A^nは全点対最短路の隣接行列が得られる。ワーシャルフロイドっぽくなる
三重ループ回さなくても、行列演算でもっと短くかけそう。
function algebraicsquarbellmanford(A,s) [M,N] = size(A); for i = [1:N] d(i) = inf; endfor d(s) = 0; for k = [1:N] for i = [1:N] for j = [1:N] A(i,j) = minplus(A(i,:),A(:,j)); endfor endfor endfor d = minplus(d,A); endfunction
