satomacoto: 12/2012

December 15, 2012

政党と政策の距離の可視化

政党間の類似度の可視化で使ったデータを標準化して特異値分解して可視化．双対尺度法とか数量化理論III類とかコレスポンデンス分析とか言われている．たしか．

図 ◆政策，■政党．政策とそれに賛成する政党が近くにある…はず

以下コード

政党間の類似度の可視化

日本政治.comの投票マッチングから各政党の政策に関する質問に対する姿勢から，政党間の距離を計算し可視化してみた．

各質問に対して賛成・中立・反対を 1, 0, -1 で表し各政党をベクトル化
ベクトル間のユークリッド距離を計算
多次元尺度構成法で可視化（Pythonで多次元尺度構成法を実装してみる，Excelの散布図のデータにラベルをつける）

ただし以下に注意

各質問の重みは考慮していない
距離の定義を変えればまったく異なる見え方に

さらに政党と政策との距離も可視化してみた→政党と政策の距離の可視化

以下コード

やっつけなのでてきとう
あとで双対尺度法試してみる
一つ前に書いた要約プログラムで連立政権について考えてみる

December 14, 2012

インストール

Homebrewでインストール

brew install mongodb
==> Downloading http://fastdl.mongodb.org/osx/mongodb-osx-x86_64-2.2.2.tgz
######################################################################## 100.0%
==> Caveats
To have launchd start mongodb at login:
    ln -sfv /usr/local/opt/mongodb/*.plist ~/Library/LaunchAgents
Then to load mongodb now:
    launchctl load ~/Library/LaunchAgents/homebrew.mxcl.mongodb.plist
Or, if you don't want/need launchctl, you can just run:
    mongod
/usr/local/Cellar/mongodb/2.2.2-x86_64: 20 files, 170M, built in 98 seconds

上にあるようにログイン時に起動してロードするには

ln -sfv /usr/local/opt/mongodb/*.plist ~/Library/LaunchAgents
launchctl load ~/Library/LaunchAgents/homebrew.mxcl.mongodb.plist

起動

mongod

接続

mongo

チュートリアル

> use mydb
switched to db mydb
> db
mydb
> j = {name: 'mongo'};
{ "name" : "mongo" }
> k = {x: 3}
{ "x" : 3 }
> db.things.insert(j)
> db.things.insert(k)
> show collections
system.indexes
things
> db.things.find()
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
{ "_id" : ObjectId("50caeb29dab5ce4e84a41f79"), "x" : 3 }

ループで挿入

> for (var i = 1; i <= 20; i++) db.things.insert({x:4, j:i})
> db.things.find()
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
{ "_id" : ObjectId("50caeb29dab5ce4e84a41f79"), "x" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7a"), "x" : 4, "j" : 1 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7b"), "x" : 4, "j" : 2 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7c"), "x" : 4, "j" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7d"), "x" : 4, "j" : 4 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7e"), "x" : 4, "j" : 5 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7f"), "x" : 4, "j" : 6 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f80"), "x" : 4, "j" : 7 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f81"), "x" : 4, "j" : 8 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f82"), "x" : 4, "j" : 9 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f83"), "x" : 4, "j" : 10 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f84"), "x" : 4, "j" : 11 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f85"), "x" : 4, "j" : 12 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f86"), "x" : 4, "j" : 13 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f87"), "x" : 4, "j" : 14 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f88"), "x" : 4, "j" : 15 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f89"), "x" : 4, "j" : 16 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8a"), "x" : 4, "j" : 17 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8b"), "x" : 4, "j" : 18 }
Type "it" for more
> it
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8c"), "x" : 4, "j" : 19 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8d"), "x" : 4, "j" : 20 }

カーソル操作

> var c = db.things.find()
> while (c.hasNext()) printjson(c.next())
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
{ "_id" : ObjectId("50caeb29dab5ce4e84a41f79"), "x" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7a"), "x" : 4, "j" : 1 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7b"), "x" : 4, "j" : 2 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7c"), "x" : 4, "j" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7d"), "x" : 4, "j" : 4 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7e"), "x" : 4, "j" : 5 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7f"), "x" : 4, "j" : 6 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f80"), "x" : 4, "j" : 7 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f81"), "x" : 4, "j" : 8 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f82"), "x" : 4, "j" : 9 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f83"), "x" : 4, "j" : 10 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f84"), "x" : 4, "j" : 11 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f85"), "x" : 4, "j" : 12 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f86"), "x" : 4, "j" : 13 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f87"), "x" : 4, "j" : 14 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f88"), "x" : 4, "j" : 15 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f89"), "x" : 4, "j" : 16 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8a"), "x" : 4, "j" : 17 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8b"), "x" : 4, "j" : 18 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8c"), "x" : 4, "j" : 19 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8d"), "x" : 4, "j" : 20 }

カーソルで配列の操作

> var c = db.things.find()
> printjson(c[4])
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7c"), "x" : 4, "j" : 3 }
> c.toArray()
[
 {
  "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"),
  "name" : "mongo"
 },
 {
  "_id" : ObjectId("50caeb29dab5ce4e84a41f79"),
  "x" : 3
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7a"),
  "x" : 4,
  "j" : 1
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7b"),
  "x" : 4,
  "j" : 2
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7c"),
  "x" : 4,
  "j" : 3
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7d"),
  "x" : 4,
  "j" : 4
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7e"),
  "x" : 4,
  "j" : 5
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f7f"),
  "x" : 4,
  "j" : 6
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f80"),
  "x" : 4,
  "j" : 7
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f81"),
  "x" : 4,
  "j" : 8
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f82"),
  "x" : 4,
  "j" : 9
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f83"),
  "x" : 4,
  "j" : 10
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f84"),
  "x" : 4,
  "j" : 11
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f85"),
  "x" : 4,
  "j" : 12
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f86"),
  "x" : 4,
  "j" : 13
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f87"),
  "x" : 4,
  "j" : 14
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f88"),
  "x" : 4,
  "j" : 15
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f89"),
  "x" : 4,
  "j" : 16
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f8a"),
  "x" : 4,
  "j" : 17
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f8b"),
  "x" : 4,
  "j" : 18
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f8c"),
  "x" : 4,
  "j" : 19
 },
 {
  "_id" : ObjectId("50caeee0dab5ce4e84a41f8d"),
  "x" : 4,
  "j" : 20
 }
]

クエリ

> db.things.find({name : "mongo"})
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
> db.things.find({x : 4}, {j : true})
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7a"), "j" : 1 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7b"), "j" : 2 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7c"), "j" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7d"), "j" : 4 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7e"), "j" : 5 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7f"), "j" : 6 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f80"), "j" : 7 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f81"), "j" : 8 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f82"), "j" : 9 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f83"), "j" : 10 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f84"), "j" : 11 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f85"), "j" : 12 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f86"), "j" : 13 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f87"), "j" : 14 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f88"), "j" : 15 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f89"), "j" : 16 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8a"), "j" : 17 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8b"), "j" : 18 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8c"), "j" : 19 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f8d"), "j" : 20 }

数の指定

> db.things.findOne()
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
> db.things.find().limit(3)
{ "_id" : ObjectId("50caeb1fdab5ce4e84a41f78"), "name" : "mongo" }
{ "_id" : ObjectId("50caeb29dab5ce4e84a41f79"), "x" : 3 }
{ "_id" : ObjectId("50caeee0dab5ce4e84a41f7a"), "x" : 4, "j" : 1 }

参考になりそうな

Getting Started with the MongoDB JavaScript Shell — MongoDB Manual http://docs.mongodb.org/manual/tutorial/getting-started/
MongoDBの薄い本(The Little MongoDB Book) - cuspy diary http://www.cuspy.org/diary/2012-04-17

December 10, 2012

PythonでDocument Summarization based on Data Reconstruction (AAAI 2012)の実装

Zhanying He, Zhejiang University, et al., Document Summarization based on Data Reconstructionを実装してみる。AAAI-12 Outstanding Paper Awards。

概要

従来の要約は冗長性を最小化するようなメイントピックを含む文を抽出することによって実現。
本手法はオリジナルのドキュメント全体を再現できるような文集合を抽出して再構成。そのために抽出した文集合を評価するために再構成関数 reconstruction function の提案。

線形的再構成 linear reconstruction。文の線形的な組み合わせによってドキュメントの近似。貪欲法 greedy strategy で最適化。
非負線形的再構成 nonnegative linear construction 。文の線形的な組み合わせを足し算で再構成。乗算型重み更新 multiplicative updating で最適化。

提案するフレームワークをDSDR (Document Summarization based on Data Reconstruction)と呼ぶ。
DUC 2006とDUC 2007で実験。ランダム、Lead、LSA、ClusterHITS、SNMFと比較。

DSDR

要約文がなるべくドキュメント全体の内容を含むようにする。再構成誤差（reconstruction error）を小さくするようにする。

ドキュメントの各文について重み付き語頻度ベクトル weighted term-frequency vector で表現。ステミングをしておいたり、ストップワードを取り除いたりしておく。候補文集合 the candidate set 。
再構成関数により候補文集合から選ばれた文集合の評価。
再構成誤差を最小にするような最適な組み合わせを探索。

コンセプト

まずオリジナルドキュメントと要約の再構成誤差を
$$L({\mathbf v}_i - f(X; {\mathbf a}_i))$$
と考える。ただし、候補文集合$V$、要約文集合$X$、全単語数$d$として、$V=[{\mathbf v}_1,...,{\mathbf v}_n]^T$ where ${\mathbf v}_i \in R^d$, $X=[{\mathbf x}_1,...,{\mathbf x}_m]^T$, $n > m$とする。${\mathbf v}_i$は語頻度ベクトル、また$f(\cdot)$を再構成関数とする。このとき再構成誤差を最小とするように$X, A$を定めれば目的関数は
$$\min_{X,A} \sum_{i=1}^n ||{\mathbf v}_i - f(X; {\mathbf a}_i)||^2$$
となる。これに対して2つの手法で解く。

本論文では再構成関数は
$$f_i(X;{\mathbf a}_i)=\sum_{i=1}^m{\mathbf x}_j a_{ij}$$
と表し、候補文集合が
$${\mathbf v}_i\approx\sum_{i=1}^m{\mathbf x}_j a_{ij}$$
と選ばれた文集合の線形結合で近似されるとする。

詳細は論文参照。

線形的再構成 linear reconstruction

$$\begin{aligned}\min_{X, A} & \sum_{i=1}^n||{\mathbf v}_i-X^TA||^2+\lambda||{\mathbf a}_i||^2\\s.t. & X \subset V, |X|=m \\& A = [{\mathbf a}_1, \cdots, {\mathbf a}_n]^T \in R^{n\times m}\end{aligned}$$

非負線形的 nonnegative linear reconstruction

$$\begin{aligned}\min_{{\mathbf a}_i, \beta} & \sum_{i=1}^n\{ ||{\mathbf v}_i -V^T {\mathbf a}_i||^2+\sum_{j=1}^n\frac{a_{ij}^2}{\beta_j} \} + \gamma||\beta||_1 \\s.t. & \beta_j \ge0, a_{ij} \ge 0, {\mathbf a}_i \in R^n\end{aligned}$$

実装

論文に疑似コードが載っているのでPythonで実装。要NumPy。

V = [[1,0,0,0],
     [0,1,0,0],
     [1,1,0,0],
     [0,0,1,0],
     [0,0,1,1]]

というドキュメント（行が文、列が語）に対して、

線形的再構成では3番目と5番目の[1,1,0,0], [0,0,1,1]という文が選ばれた。
非負線形的再構成ではそれぞれに[ 0.49301097 0.49301097 0.6996585 0.49301097 0.70211699]という重みがつき、同様に3番目と5番目の文が選ばれやすいことを示している。

それぞれトレードオフパラメータは尖りやすさ。これが小さいと過学習しがち。

実験

あとで。

メモ

報知的要約。（cf. 指示的要約）
LSAと似てる気がする。制約ついてるのがちょっと違うのかな。
おもしろい。でも実装してみただけ。あとでちゃんと読む。
テストの書き方がわからない。
訳し方がわからない。