30分ぐらいでAmazonの注文履歴をjavascriptの勉強をしながら取得する方法

年の瀬が迫っている中、ふと、「僕ってどれぐらいAmazonの売り上げに貢献しているんだろう」という疑問がわいた。

Amazonのサイトでアカウントログインして、注文履歴を追っていけば、把握はできるが操作の手間がある。これをスクレイビング的にスクリプトで抽出することはそんなに難しくないはず。先人が居られるだろうと思って検索したら、案の定、次のようなサイトが見つかった。

すばらしい!!っと思って、早速これらを実行をしようとしたのだが、うまく履歴を取得できないようだった。スクリプトが作られた時期は2013年の半ば。今から一年半程度前のことで、きっと、その間にAmazonサイトのHTMLスタイルの改変などが行われたために、スクリプトの情報取得がうまく機能しなくなっているのだと考えられる。

この手の情報取得スクリプトはどうしても賞味期限がある。重要な情報を持っているサイトのスタイルが改変されると、せっかく作ったスクリプトは使い物にならなくなってしまうことが多い。例えば、10年ほど前に購入した以下の本(Amazonで購入)

Spidering hacks―ウェブ情報ラクラク取得テクニック101選

Spidering hacks―ウェブ情報ラクラク取得テクニック101選

 

は、掲載されているスクリプトのうち今でも機能するのがどれほどあるのか、怪しいもんだ。(確認していないけどね)(でも、とってもよい本です)

では、どうすべきかと考えると、更新頻度の高いサイトから情報取得する方法は、使い捨てのスクリプトになることを許容して、最小限の手間でプログラミングをするしかない、と思う。

というわけで、ここでは、先人様のサイトのスクリプトを参考にしつつ、2014年12月現在のAmazonの注文履歴の画面を分析しながら、javascriptコンソールで最小限のコマンド入力によって情報取得する方法を紹介したい。

注意事項

Webブラウザのjavascriptコンソールを利用するので、実行は自己責任でお願いします。

実際のところ、ログイン状態でのブックマークレットの利用は、注意しておいたほうがよい。例えば、amazonにログインした状態で別サイトのjavascriptを実行することは、そのスクリプトの中でログインのcookie情報を扱えるということなので、セキュリティには注意が必要である。

事前準備

適当なブラウザ、(Chrome or firefox)で、次のURLにアクセスして、Amazonにログインする。

https://www.amazon.co.jp/gp/css/order-history

でもってその画面で、javascriptコンソールを開く。

jQueryを使えるようにする

javascriptコンソールから以下のコマンドを入力する。

(function(s){s.src='https://ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js';document.body.appendChild(s)})(document.createElement('script'));

jQueryのライブラリのscriptタグを追加して、jQueryの文法が使えるようになる。

htmlから注文データを抽出する

jQueryの文法を利用してhtmlのデータから注文データを取得する方法を考える。先のURLにログイン・アクセスすると以下の画面が出るはずである。(Chromeの場合)

f:id:skzy:20141223011411j:plain

今回は、簡単のため注文頻度と注文金額を把握したい。一回の注文単位の日付と注文金額は、上の画面の赤い枠の中を取得すればいい。

javascriptコンソールのElementsタブを開いて、htmlのタグにマウスをあわせるとその対象のオブジェクトが画面で選択表示される。これを用いて、上画面の赤枠に該当するタグ or クラスを調べていく。

すると、class="order-info"が赤枠を示していることがわかる。この中のvalueクラスが日付や金額などの文字列を表してそうである(※2014年12月現在の状態)。試しに、javascriptコンソールで次のように打ってみる。(事前に前項のjQueryライブラリ読み込みを行わないとエラーになるので注意。)

$(".order-info").map(function(i,s){return $(".value",s).map(function(i,s){return $.trim(s.textContent);});});

jQueryセレクターを使ってorder-infoクラスとvalueクラスのテキストを2重配列で抜き出す。うまく抽出していれば、2重配列の中に赤枠の情報が含まれているはずである。これを関数化するために、以下をjavascriptコンソールで入力する。

function getOrder(html){
  return $.merge([],
    $(".order-info",html).map(function(i,s){
      return $(".value",s).map(function(j,t){
        return $.trim(t.textContent);
      });
    })
  );
}

※$.mergeはjQueryのオブジェクトを配列に変換するもの。配列のほうが個人的に扱いやすいため。

別のURLにアクセスする

前項では今表示されているhtmlに対してしか、情報抽出できていない。過去の年の注文にアクセスするには、javascriptでURLへのアクセスをしなければならない。XMLHttpRequestのGETを使おう。

function getOrderHtml(urlstr) {
  http = new XMLHttpRequest();
  http.open('GET',urlstr,false);
  http.setRequestHeader("Content-Type","text/html");
  http.send(null);
  return http.responseText;
}

同期にすると厄介なので、http.openでfalseの非同期設定にして実際にアクセスが終わってからresponseTextを返すようにしている。そのためちと時間がかかるが、たかだか個人のデータを取得するのにそんな性能要件は必要ない。

※ちなみに、jQueryの$.getも試したけれどうまくいかなかったのでXMLHttpRequestを使ってます。

データのあるURLを繰り返し取得する再帰処理

Amazonの注文履歴表示は、(※2014年12月現在)10件以上の注文がある場合、複数ページに分かれて下のページ番号で選択するようになっている。そのため、注文履歴を全部取得するためのURLアクセスは、"年の選択...orderFilter"と、"何ページ目か？...startIndex(0が1ページ目,10が2ページ目...)"をパラメータで指定して取得することができる。

つぎの関数を定義したい。

  • 年を指定すると、その年の注文をすべて取得する
  • 注文はgetOrder関数の結果のconcatにする
  • 再帰を使う。(短くしたいので)
function getDataOfYear(yy,idx){
  console.log(yy+","+idx);
  var urlstr="https://www.amazon.co.jp/gp/css/order-history?ie=UTF8&orderFilter="+yy+"&startIndex="+idx;
  var rowd=getOrder(getOrderHtml(urlstr));
  if (rowd.length==0 || !(idx<999) ) { return [];
  } else { return getDataOfYear(yy,idx+10).concat(rowd);
  }
}

getOrderの結果が0になるまで、startIndexのページを増やしてconcatする再帰関数である。console.logで、今のURL取得状況を確認する。これでたとえば、

getDataOfYear("year-2014",0);

と実行してみると、2014年の注文を全部取ってきた結果を返してくれる。

全データをタブ区切りで文字列化する

さて、年を表すパラメータは"year-YYYY"というフォーマットなので、必要なだけデータを作ればいいけれど、ここでは画面のhtmlから取得する。上のほうのドロップダウンのアイテムが年のパラメータを選択しているので、

YEARS=$(".a-dropdown-container option").map(function(i,s){return s.value;}).filter(function(j,t){return j>1;});

と入力すると、"year-2014","year-2013",...という配列が取得できる。

このYEARS配列と、さっきほど用意したgetDataOfYear関数を使えば、すべての年の注文情報を得られる。

TSVDATA=YEARS.map(function(i,s){
  return getDataOfYear(s,0).map(function(t){
    return t[0]+"	"+t[1];}).join("
");
  });

getOrder関数で取得したデータのid=0が日付でid=1が金額である。これをtsvにしてリストを改行区切りで文字列化する。実行すると、すべての注文データをとりに行くため少々時間がかかる。console.logで進捗を見ながらしばし待つこと。

tsvを表示する

最後に、さっき取得したTSVDATAをlocation.hrefで表示させる。

location.href = 'data:text/plain;charset=utf-8,' + encodeURIComponent($.merge([],TSVDATA).join("
"));

ずどーんと取得したデータが表示されるので、あとはこぴぺして煮るなり焼くなり好きにするがよい。

まとめ

実行したjavascriptの全貌：

(function(s){s.src='https://ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js';document.body.appendChild(s)})(document.createElement('script'));

function getOrder(html){
  return $.merge([],
    $(".order-info",html).map(function(i,s){
      return $(".value",s).map(function(j,t){
        return $.trim(t.textContent);
      });
    })
  );
};

function getOrderHtml(urlstr) {
  http = new XMLHttpRequest();
  http.open('GET',urlstr,false);
  http.setRequestHeader("Content-Type","text/html");
  http.send(null);
  return http.responseText;
}

function getDataOfYear(yy,idx){
  console.log(yy+","+idx);
  var urlstr="https://www.amazon.co.jp/gp/css/order-history?ie=UTF8&orderFilter="+yy+"&startIndex="+idx;
  var rowd=getOrder(getOrderHtml(urlstr));
  if (rowd.length==0 || !(idx<999) ) { return [];
  } else { return getDataOfYear(yy,idx+10).concat(rowd);
  }
}

YEARS=$(".a-dropdown-container option").map(function(i,s){return s.value;}).filter(function(j,t){return j>1;});

TSVDATA=YEARS.map(function(i,s){
  return getDataOfYear(s,0).map(function(t){
    return t[0]+"	"+t[1];}).join("
");
  });

location.href = 'data:text/plain;charset=utf-8,' + encodeURIComponent($.merge([],TSVDATA).join("
"))

※これをそのままjavascriptコンソールこぴぺしても成功しない。scriptファイルにしてブックマークレットとすることはできると思う。

最後に

取得したtsvを適当に修正したあと、Tableau でグラフ化してみた。

f:id:skzy:20141223113533j:plain

年間で5万から20万、多いとして22万円利用している。明らかにAmazon依存症。2012年ごろから、注文頻度が急激に上昇しているのは、kindleを導入したため、無料の注文が多く発生したからである。

わりと、妥当なことがわかりました。

30分ぐらいで raspberry pi にtheanoを入れる

raspberry piと機械学習が気になって、とにかく、できそうなことを、さくっとやってみたメモ。

 

raspberry pi を手に入れる

アマゾンで検索すれば5000円前後で手に入る。今回は type B である。

 

手持ちのSDカードにOSを焼く

raspberry pi の推奨OS は raspbian これを以下からダウンロードする。

Downloads | Raspberry Pi

さらに、手持ちのパソコンに手持ちのSDカードを指して、fedora-arm-installerのツールを使ってOSを焼く。

Fedora ARM Installer - FedoraProject

ちなみに、僕が導入したのは2014-6-20のraspbian。焼き方はこんな感じ。

 f:id:skzy:20140826004741j:plain

 

raspberry pi のsetup

ネットワークにつないでDHCPでIP振り出してもらって、sshで接続すると、デフォルトではpi / raspberry でログインできる。このあと、

$ sudo raspi-config

とたたいて、raspbianのセットアップを行う。

やっておきたいこと：

  • Expand Filesystem ... SD cardの拡張
  • Overclock  ...  とりあえず、最初はModestぐらい？

これでreboot。

 

swap領域を増やす

raspberry pi type B のメモリサイズは512MB。いまどき心もとない(十数年前が懐かしい)のだが、swapのdefaultの設定が100MBしか設定されていないみたい。これを変更する。

いったんswapプロセスをとめて

$ sudo /etc/init.d/dphys-swapfile stop

次に設定ファイル /etc/dphys-swapfile をいじる

CONF_SWAPSIZE=1000

MB単位らしいので1GBぐらいに。swapプロセス再起動。

$ sudo /etc/init.d/dphys-swapfile start

topコマンドでswapが増えているか確認しておく。

 

関連パッケージの導入

この辺あたりから怪しい。とりあえず、apt-getをupdate

$ sudo apt-get update

theanoの最低必要パッケージ

$ sudo apt-get install  python-numpy python-scipy python-nose g++ libatlas-dev libatlas3gf-base git

本当にこいつらで大丈夫なの？と思いつつ、次へ進む。

 

theanoをgitからsetup.pyする

マニュアルではpipを使っているけれど、こちらのほうが確実っぽい。gitでtheanoのソースを持ってきて

$ git clone git://github.com/Theano/Theano.git

setup.pyする

$ cd Theano
$ python setup.py build
$ sudo python setup.py install --record setup_file.txt

uninstallするときのために、setup_file.txtにコピーしたファイルのレコードをとっておく。さて、importできるかな？

$ python
>>> import theano
～
Exception: Compilation failed (return status=1): cc1plus: error: unrecognized command line option ‘-m32’. 
～

ありゃりゃ？

どうも以下で修正されているコードが関係しているみたい。

Add ARM architecture check for Raspberry Pi · 70e761e · vdumoulin/Theano · GitHub

というわけで、環境変数を入れる。

$ export THEANO_FLAGS=gcc.cxxflags=-march=armv6j

これで再import

$ python
>>> import theano
WARNING (theano.gof.cmodule): WARNING: your Theano flags `gcc.cxxflags` specify an `-march=X` flags.
         It is better to let Theano/g++ find it automatically, but we don't do it now

なにやらwarningがでたがimportはできたみたい。めでたしめでたし。

括弧付の構文をパースする簡単なスクリプト /w python

プレーンファイルのデータ変換をいろいろとやっていると、表題のようなことが必要になることがある。

たとえば、

  • 各種設定ファイル
  • ログファイル
  • SQLとか、言語
  • そのほか ...

最近はxmlのものも多くて、その場合はxmlライブラリ(pythonならbeautifulsoupか)を使って組める。beautifulsoupはインターフェースがかなり直感的に書けて、何も考えないでも、書いた後 try & error でスクリプトを調整すれば割と要件を満たせる。

xmlではなく、言語のような独自の構文であったりする場合、データとして取り込むときに、とりあえず、文字列の中の括弧の構造を木構造にしたい。

例えば、次のような文があったとする。

  • 本日(今日のこと(日曜日だね))は晴天（[めちゃ日差し強いよ]晴れのこと）なり。

括弧とその中の文を、"子の文"として、リストに入れる。元の文には別の文字を置き換える。pythonらしく"%"で置き換えるとすると、次の3タプル構造で文を表現する。

  • (  ""  ,  "本日%は晴天%なり。" ,  [...]  )

 タプルの1番目は、文全体がどんな括弧にくくられているかを示すもので、""の場合は地の文となる。タプルの2番目は置き換えた後の本文で、3番目は子の文のリストである。3番目のリストをちゃんと書くと、

  • [("(","今日のこと%",[("(","日曜日だね",)]),("(","%晴れのこと",[("[","めっちゃ日差し強いよ",)])]

となる。

下準備

parseするかっこの種類を辞書式でセットしておく。これのキーがタプル構造の1番目にはいる。また、文字列のどの部分までをparseしたかを取り出せるように、一文の3タプル構造を引数として、parseされた文字列の長さを返す関数を用意しておく。

bracketPair={u'（':u'）','(':')','[':']',u'［':u'］'}

def countlen(d):
    l= len(d[1]) -len(d[2])
    if d[0]!="":l+=len(d[0] + bracketPair[d[0]])
    return l+sum(map(countlen, d[2]))

直感的に書く

いずれにしても再帰を使うのだが、ある程度、手続き的に直感で書くとこんな感じ。whileで途中までたどる。

def parseBracket(hd,st):
    d=[hd,"",[]]
    idx=0
    while idx<len(st):
        if hd!="" and st[idx]==bracketPair[hd]:
            break
        if st[idx] in bracketPair:
            c =parseBracket(st[idx],st[idx+1:])
            d[2].append(c)
            d[1]+= "%"
            idx += countlen(c)
        else:
            d[1]+= st[idx]
            idx += 1
    return tuple(d)

再帰的

再帰だけで書くとこうなる。

def parseBracket(hd,st):
    if st=="" or ( hd!="" and st[0]==bracketPair[hd] ):
        return (hd,"",[])
    if st[0] in bracketPair:
        c=parseBracket(st[0],st[1:])
        n=parseBracket(hd,st[countlen(c):])
        return (n[0],"%"+n[1],[c]+n[2])
    n=parseBracket(hd,st[1:])
    return (n[0],st[0]+n[1],n[2])

どっちがお好みかな？

boids algorithm 実装方法についての簡単なメモ

D3.js アルゴリズム

boids algorithm とは、群れをシミュレーションするマルチエージェントプログラム。各エージェントは、次の3つのルールで動作する。

  • 分離（Separation）エージェントが他のエージェントとぶつからないように距離をとる。
  • 整列（Alignment） エージェントが他のエージェントと概ね同じ方向に飛ぶように合わせる。
  • 結合（Cohesion) エージェントが他のエージェントが集まっている群れの中心方向へ向かうように方向を変える。

これだけのルールで、魚や鳥の群れをよくシミュレーションできるといわれていて、映画などのCGにもよく利用されているとのこと。 各エージェントはシンプルなルールながら、全体としては複雑に振る舞うことから、複雑系、自己組織化的な現象が垣間見れるといわれている。

 

いろいろな実装が考えられるようだが、特にシンプルな、各エージェントの速度が一定で、2次元空間の進行角度が変化する場合の実装について、"参考"の情報を参考にしながら、javascript & D3.jsで表現した。

事前準備

 まず、各エージェント(node)は、場所(x,y)と進行方向の角度(deg)、さらにエージェントの行動に影響を与える、距離の近い他のエージェントのリスト(neighbors)で構成する。

node =[ {x:0,y:0,deg:0,neighbors=[] },... ];

でもって、neighborsを作成するため、総当りで各エージェント間の距離を調べる。$N$個のエージェントなら、${}_n \mathrm{C}_2 = N(N-1)/2$を調べることになる。ただし、neighborsにリスト化するのは、そのエージェントが見える範囲、ということでパラメータvisionを距離の値として、それより近い距離にあるエージェントをneighborsリストに追加する。

for (i=0;i<node.length;i++) {
    for (j = i+1;j<node.length;j++) {
        d = (※node[i]とnode[j]の距離);
        if (d < node[i]のvision )
            node[i].neighbors.push({dist:d,deg:node[j].deg,x:node[j].x, y:node[j].y});
        if (d < node[j]のvision )
            node[j].neighbors.push({dist:d,deg:node[i].deg,x:node[i].x, y:node[i].y});
    }
}

node[i].neighborsのリストはあらかじめ大きい順にsortしておく。

    node[i].neighbors.sort(function(a,b){return a.dist-b.dist;});

分離の実装

さて、ここからが本題。

"分離"のルールは、「他のエージェントと近づき過ぎないように距離をとる」というもの。パラメータminimum-separationを距離の値として、エージェントのリストneighborsのうちもっとも近いエージェントがこの距離より小さかったら、離れるように動くことにする。

今回の実装では、各エージェントはスピード一定で、変更できるのは進行角度だから、この近づきすぎてしまったエージェントの進行方向と逆方向に自分の進行角度を向けば離れられる。つまり、

  • (今の進行角度 ) → (最近傍のエージェントの進行角度) + 180°
  • $\delta \theta$ = (最近傍のエージェントの進行角度) + 180° - (今の進行角度)

微少時間の動作としては、この$\delta \theta$を今の進行角度との変位として加算して推移するようにする。

ところが、この右側の角度の差が、若干厄介である。例えば、260° - 100°=160°である。では、-100°-100°=-200°か？ 260°=-100°だから同じ結果になってくれないと困るし、方向転換をするための計算なのだから、次の図のように、なるべく回りやすい方の角度(160°)を出力としたい。

レイヤ 1 a=260° b=100° a'=-100° 160° -200°

つまり、角度aと角度bの差(a-b)は、角度bを足して角度aと等しくなる、もっとも絶対値が小さいほう(つまり -180～180の間)であってほしい。(a-b)を横軸において、縦軸が角度の差の出力としたグラフは、

Layer 1 (a-b) 角度の差 360° 180° -360° -180°

 となるような実装とある。この引き算の仕方は、別に角度に限ったわけではなく、同じような周期境界条件をもつ場合(有限加群)に適用できる。360°を周期periodに変えればよいわけで、このグラフをコードにすると、次のようになる。

function diffCyclic(deg1,deg2,period) {
	var deg = (deg1 - deg2) % period;
	if ( Math.abs(deg) <= period/2 ) return deg;
	else {
		if ( deg > 0 ) return -period + deg;
		else return period + deg;
	}
}

この関数を使って、

\[ \delta \theta = \textrm{diffCyclic} ((最近傍のエージェントの進行角度) + 180° , (今の進行角度),360 ) \]

と書けば進行角度の変位$\delta \theta$が求められる。

※今回の場合はx,y空間も周期的な境界(つまりトーラス空間)を持つことにした。なので、事前準備で、各エージェントの距離を算出するときもこの差の関数diffCyclicを利用する。

整列の実装

次に、整列の実装である。"整列"は、「周辺のエージェントの角度と同じ方向にあわせる」わけなので、リストneighborsの各エージェントの進行角度の平均を取得して、その差分を変位とすればよい。

ところがこれまた厄介で、角度の平均というのは一般に難しい。例えば、10°と20°の平均は(10+20)/2 = 15°でよいが、345°と5°の平均は、(345+5)/2=180°となってしまう。

そこで、いったん角度を半径1の円上の点の(x,y)に展開して、xとyについて合計を取り、最後に(sum x,sum y)に対して$\tan^{-1}$をとるようにして、求めたい、各エージェントの進行角度の平均を取得する。取得した平均進行角度にあわせるように変位$\delta \theta$を決める。これを三角法と言うらしい。

var ax = 0,ay = 0;
for (j=0;j<node[i].neighbors.length;j++) {
    ax += Math.cos(node[i].neighbors[j].deg/degrees); // degrees = 180 / Math.PIで割戻し
    ay += Math.sin(node[i].neighbors[j].deg/degrees);
}
da = diffCyclic(Math.atan2(ay,ax)*degrees,node[i].deg,360); //例の差の関数を使って角度の差分を求める。

結合の実装

最後に結合の実装。"結合"は「群れの中心方向へ向かうように方向を変える」ので、neighborsの平均位置の方へ向くように進行角度を変更すればよい。

x,y空間は周期境界条件をつけていた。

境界をはさんだエージェントの位置の平均をそのまま計算してしまうと、えらい間違いがおこってしまう。ここでは、先ほどの差の関数diffCyclicを使って、自分自身のエージェントとの相対位置の平均を取ることにすればよい。

var cx = 0,cy = 0;
for (j=0;j<node[i].neighbors.length;j++) {
	cx += diffCyclic(node[i].neighbors[j].x,node[i].x,width); // 自分エージェントとの相対位置を差の関数で得る
	cy += diffCyclic(node[i].neighbors[j].y,node[i].y,height);
}
dc = diffCyclic(Math.atan2(cy,cx)*degrees,node[i].deg,360);  // cohere rule

相対位置の合計(cx,cy)から、$\tan^{-1}$で角度を求めている。

パラメータ

さて、最後に、それぞれのルールに対する強度のパラメータを定義することで、パラメータの差異によるエージェントの振る舞いの違いを検討できるようにする。

  • max-separate-turn... "分離(Separation)"が発生したときの変更される進行角度の最大絶対値。これが大きいと"分離"しやすくなる。
  • max-align-turn... "整列（Alignment)"ルールで変更される進行角度の最大絶対値。これが大きいと"整列"しやすくなる。
  • max-cohere-turn... "結合（Cohesion)"ルールで変更される進行角度の最大絶対値。これが大きいと"結合"しやすくなる。

それぞれのルールで算出した$\delta \theta$の絶対値を上記のパラメータで比較して、変位が上記のパラメータより大きくならないように制限する。

...
deltad = compDegree(max-separate-turn,deltad);
...
function compDegree(maxd,deg) {
	if (Math.abs(deg) < maxd) return deg;
	else {
		if (deg > 0 ) return maxd;
		else return -maxd;
	}
}

以上の実装をD3.jsを加味したり省略整理などしたものが以下。

こんな感じ

そのまんまだと面白みが無いので、ここではエージェントにグループを複数設定できて、グループごとにエージェントの数と各種パラメータを設定できるようにした。デフォルトの設定だとグループ0のminimum-separationが小さくて、だんだんグループ0が固まりとなってクラスタ化していき、それに対してグループ1,2は比較的ばらける様子が伺える。(ちゃんと定量的な評価が必要なんでしょうね)

参考

複雑系科学で有名なサンタフェ研究所 (Santa Fe Institude)が主催しているComplexity Explorer というHPがある。ここでは、複雑系科学に関する free online course を受講できる。

Complexity Explorer

実装は講義 "Introduction To Complexity"で紹介されていたboids algorithmを参考にした。NetLogoでのboidsライブラリも紹介されていて、パラメータの設定はその実装を参考にした。(アルゴリズムも実はほぼ同じ)

NetLogo Home Page

安定結婚問題をD3.js force layout で表示

D3.js アルゴリズム

D3.jsで表現するシリーズ。以前、安定結婚問題のブログを書いたけれど、

安定結婚問題のアルゴリズム - skzy's diary ... もろもろ書きのこす

安定結婚問題のアルゴリズムをD3.jsのforce layoutのノードの動きで表現してみました。

アルゴリズムそのまんまではなく、ノードの動作に沿って実装しているので、若干の不備があるかも知れないが、試してみると結構動きが面白い。

各人の好みの順序リストは均一なランダムで作成しているけれど、実際には人気は少数に集中していたりする。実装の中の、

var x=aveRandom(n-j,1);

というところの1を大きくすると、列の真ん中にいる人(例えば、10人だったら、5,6番目)に人気が偏る好みの順序リストができる。

これでアルゴリズムを実行してみると、当たり前なんだけれど、人気者同士がカップルになる、という社会の縮図を感じてしまう。

すべてを平等にはできない。しかし完全な階層化ではなく、多少は多様性があったほうが面白いわけで、じゃあ、階層的な順序に対し、どれぐらいのランダムな多様性が入ると、社会によい影響を与えるのか、っていうことに興味がある今日この頃である。

というわけで、D3.jsすばらしい。

N bitブール代数をD3.jsのforce layoutで表示

D3.js ブール代数

前回、ブール代数の基本を確認したときに、ブール代数の束としての半順序構造をsvgを使って図で説明した。

 

せっかくなのでD3.jsを使って、Nビットのブール代数 ( N個の集合代数)をforce layoutのネットワーク図を使って表示してみる。

入力フォームにビット数(=集合代数のN個)を入力してVisualizeボタンを押せば、図が表示される。各ノードの操作の実装は以下のコードをほとんどそのまま。

Sticky Force Layout

ドラッグすることでノードが固定される(固定中のノードは赤枠)。固定されたノードはダブルクリックで元に戻る。

 また、ドラッグのタイミングでノードが選択されると、Choice欄にノードの番号が選択される。これに対し、FilterやIdealボタンを押すと、選択されたノードで生成されるフィルターやイデアルが濃い太枠で表示される仕組みを追加している。

D3.jsすばらしい!!

 

ブール代数からストーン表現(ストーン双対)まで

ストーン双対 圏論 ブール代数 位相

ブール代数の仕組みについて大まかに説明して、ストーン表現について軽く説明する。まず、束の定義、ブール代数の定義、から始める。

 

[束とは]

束(lattice)とは、半順序(partial order) $(L,\le)$に対して、任意の$x,y \in L$に上限、下限が存在するもののことをいう。半順序は、順序関係に$a,b,c \in L$で次の三つが成り立つもののこと。

  • 反射律 ... $ a \le a $
  • 推移律 ... $a \le b $かつ$ b \le c$ならば、$a \le c$
  • 反対称律 ... $ a \le b $かつ$ b \le a$ならば、$a=b$

たとえば、下記のような下から上に向けての半順序構造があるとする。

レイヤ 1

赤い丸が元で線でつないだ関係が半順序関係であり、$下の丸 \le 上の丸 $である。どちらも半順序構造をなしている図なんだけど、右の図は束になり得るが、左の図は束ではない。左図では、上限(or下限)が複数...2個、見つかる組が存在するためである。

2つの元から先の上限、下限を得る演算を結び(join)、および、交わり(meet)と呼ぶ。結びと交わりは、それぞれ$x \vee y$ , $x \land y $と表記されて、束は元の集合$L$とこれら演算の組 $(L,\vee,\land)$と表記される。束は、joinやmeetのような演算を含む構造のことである。

この定義で言うと、束には必ず半順序構造を含んでいて、$a,b \in L$の順序関係は、束の演算に対して以下が成り立つ。

  • $ a \le b $のとき、$ a \vee b = b  ,  a \land b = a $。 (逆も成り立つ)

一方、束は、次のような代数的な定義もある。それぞれの2項演算$\vee$、$\land$に対して、以下の式を満たすのが束といえる。

  • 可換律 ... $x \vee y = y \vee x   ,   x \land y = y \land x $
  • 結合律 ... $(x \vee y) \vee z = x \vee ( y \vee z )    ,   (x \land y) \land z = x \land ( y \land z ) $
  • 吸収律 ... $(x \vee y) \land x = x    ,    (x \land y) \vee x = x$
  • 冪等律 ... $ x \vee x = x \land x = x$

 

[ブール代数]

 ブール代数(Bool algebra)は、束$(B,\vee,\land)$であって次の条件を満たすもののことである。

  • 分配束である。すなわち、任意の元$a,b,c \in B$に対して、次の分配律が成り立つこと。$ a \vee ( b \land c) = (a \vee b) \land (a \vee c)   ,   a \land ( b \vee c) = (a \land b) \vee (a \land c) $ ... ※この二つの式は同値である。
  • 任意の元$\forall a \in B$で $ a \vee 1 = 1 $ となる"1"、および、$ a \land 0 = 0$となる"0"なる元が存在すること。
  • 任意の元$\forall a \in B$で、$ a \vee \lnot a = 1$かつ、 $ a \land \lnot a = 0$なる演算$\lnot$による元(補元と呼ぶ)が存在すること。つまり$\lnot a \in B$

以上によって、ブール代数は$(B,\vee,\land,\lnot,"0","1")$と表記する。

 

[ブール代数の例]

トリビアルなブール代数

ブール代数の例として、もっとも単純なのは、$\textbf{2}=(\{0,1\},\vee,\land,\lnot,0,1)$である。つまり、0と1しかない1ビットの2進演算で、結びと交わりはそれぞれ論理和と論理積に対応する。これは"トリビアルなブール代数”という。

集合代数

さらに、集合$S$の部分集合族$\mathcal{P}(S)$を元とした、$(\mathcal{P}(S),\vee,\land,\lnot,\emptyset,S)$の集合代数もブール代数となる。この場合、結び(meet)が和集合、交わり(join)が積集合に対応する。たとえば、集合$S=\{0,1,2,3\}$の4つだったとすると、半順序構造の図として書くと、以下のようになる。

Layer 1 φ {0} {1} {2} {3} {0,1} {0,2} {0,3} {1,2} {1,3} {2,3} {0,1,2} {0,1,3} {0,2,3} {1,2,3} S

これは集合のそれぞれの元を"含む"or"含まない"を"1"or"0"で対応させた4ビットの演算と同型になる。(4つのトリビアルなブール代数の積ともいえる)ここでは詳しく説明しないが、無限集合でも同じブール代数になる。

(ストーン表現はこれを位相空間に拡大して示したものなのだけど、詳細は後で...)

 

自由ブール代数

ある文に対して"真"か"偽"を判断できるものを命題とする。他に影響を与えない独立な命題(独立命題)$P$と$Q$があった場合、この二つから"$P$ または $Q$"とか、"$P$ かつ $Q$"、"$P$ではない"として、別の命題を作ることができる。さらに、作成された命題から"または"や"かつ"で命題を作っていく。"または"や"かつ"をブール代数の$\vee$、$\land$とみなし、"ではない"というのを$\lnot$と考えれば、ここで生成された命題群はブール代数となる。これを、「P,Qで生成された自由ブール代数(free boolean algebra)」と呼ぶ。生成する独立命題集合を$X(：例ではX=\{P,Q\})$としたとき、このブール代数を$\textrm{F}(X)$と表す。

例として、上記の場合の順序集合の図を以下に示す。

Layer 1 FALSE PandQ Pand(notQ) (notP)andQ (notP)and(notQ) P Q PiffQ Piff(notQ) (notQ) (notP) PorQ Q→P P→Q (notP)or(notQ) TRUE

生成される独立命題が有限のN個の場合、$2^{2^n}$個の元のブール代数となる。これの詳細は、英語のwikipediaに詳しい。

Free Boolean algebra - Wikipedia, the free encyclopedia

 "自由"という概念自体は、普遍代数にも適用でき、さまざまな場面で検討できるので興味深い。

[ブール環]

ブール環(bool ring)は、環$R=(R,+,・,-,0,1)$で、任意の元$\forall x \in R$に対し、冪等式が満たされるものを言う。

\[ x^2 \simeq x \]

この条件の追加だけで、ブール環は可換環であり、さらに次も成り立つ。(加群に対しての逆元が自分自身に等しい)

\[ x + x = 0 \]

さらに、ブール代数とブール環は演算の変換をすることで、同型になる。

  • $a・b=a \land b   ,   \lnot a = - a  $ ... ブール代数←→ブール環
  • $a+b = (a \land \lnot b) \vee ( \lnot a \land b)$ ... ブール代数→ブール環
  • $a \vee b = a+b + a・b $ ... ブール環→ブール代数

 

[ブール代数の準同型]

ブール代数$B=(B,\vee_B,\land_B,\lnot_B,0_B,1_B)$と$B'=(B',\vee_{B'},\land_{B'},\lnot_{B'},0_{B'},1_{B'})$があったとして、$B$の元から$B'$の元への関数$f:B \to B'$が、次のように演算結果を保存するとき、$f$を準同型(homomorphism)と呼ぶ。$a,b \in B$として、

  • $f(a \vee_B b) = f(a) \vee_{B'} f(b)$
  • $f(a \land_B b) = f(a) \land_{B'} f(b)$
  • $f( \lnot_B a) = \lnot_{B'} f(a)$

 ブール代数は束であり、半順序構造なので、当然、束や半順序の準同型でもある。さらに、同型のブール環に対しても演算が保存されるので、環についての準同型とも言える。さらにさらに、後で述べるストーン表現は、ブール代数と(ある条件の)位相空間との同型を示している。

 

[ブール代数のイデアルとフィルター]

環論や順序の理論でイデアル(ideal)はよく出てくる。ブール代数においては、イデアルとフィルター(filter)が双対的な関係なのでまとめて定義を見る。

ブール代数$(B,\vee,\land,\lnot,0,1)$において、イデアル：$I \subseteq B$ 、フィルター：$F \subseteq B$は、Bの部分集合で、次の3つの条件を満たすものである。

[イデアル$I$の条件]
  • $0 \in I $
  • $a \in I , b \in B $ならば、$a \land b \in I$  (つまり、$a' \le a$なら、$a' \in I$ )
  • $a , b \in I $ならば、$ a \vee b \in I$
[フィルター$F$の条件]
  • $1 \in F$
  • $a \in F , b \in B $ならば、$a \vee b \in I$  (つまり、$a \le a'$なら、$a' \in F$ )
  • $a , b \in F $ならば、$ a \land b \in F$

あるイデアルに対して、それぞれの元の補元を集めるとフィルターになる。逆も同じなので、いわばコインの裏表の関係である。

たとえば、さっきの4つの元の集合代数によるブール代数であれば、"$\{2,3\}$の部分集合すべて"はイデアルに、"$1$を含む$B$の部分集合すべて"はフィルターとなる。

[principal or free]

イデアル：$I$ / フィルター：$F$ の要素すべてに対し 結び/交わり をとることができる。この値が "1"/"0" の場合、フリーイデアル(free ideal) /フリーフィルター(free filter)または、non-principal ideal / non-principal filterと呼ぶ。

  • イデアルの場合 ... \[ \bigvee_{i \in I} i  = 1 \]
  • フィルターの場合... \[ \bigwedge_{f \in F} f  = 0  \]

"1"/"0" ではない場合、principal ideal / principal filter、主イデアル / 主フィルターと呼ぶ。前述した例で言うと、"$\{2,3\}$の部分集合すべて"、"$1$を含む$B$の部分集合すべて"いずれも、主イデアル、主フィルターで、要素すべての結び / 交わりの値は、定義から"$\{2,3\}$"、"$\{1\}$"となる。

[フリーイデアル(フィルター)の例]

自然数の集合$\mathbb{N}$の集合代数$\mathcal{P}(\mathbb{N})$を考える。このブール代数の元のうち、有限個の集合であるものを$I_{fin}$とする。

\[  I_{fin} = \{a|a \in \mathcal{P}(\mathbb{N}) , a   \textrm{is finite} \} \]

これは、フリーイデアルになる。このコインの裏側、つまり、各要素の補集合の集合を考えると、これもフリーフィルターとなり、フレチェフィルター(Frechet filter)：$\mathcal{F}_f$と呼ばれる。

\[   \mathcal{F}_f = \{a|a \in \mathcal{P}(N) , \lnot a   \textrm{is finite} \} \]

有限集合のブール代数のイデアルは、基本的に主イデアルである。無限集合の場合に、フリーイデアル(フリーフィルター)が現れる。

 

[準同型とイデアルとフィルター]

イデアルは準同型と非常に重要な係わり合いをする。

ブール代数$B$,$B'$において、準同型$f:B \to B'$が有るとする。このとき、

  • $f$のカーネル(kernel)：$\textrm{ker}(f)$ (f(x)=0を満たすx)は、B代数上のイデアルである。逆に、B代数上のイデアルであれば、それをカーネルとした準同型が存在する。
  • $f$のコカーネル(cokernel)：$\textrm{coker}(f)$ (f(x)=1を満たすx)は、B代数上のフィルターである。逆に、B代数上のフィルターであれば、それをコカーネルとした準同型が存在する。

これにより、イデアルやフィルターは、対象のブール代数に対して"割る"ことができる。たとえば、イデアル$I$に対して

\[   f:B \to B/I ... fは、  \textrm{ker}(f)=I  なる準同型    \]

となる 剰余代数(商代数)$B/I$のブール代数をつくることができる。(フィルターも同様)

たとえば、自然数の集合$\mathbb{N}$の集合代数$\mathcal{P}(\mathbb{N})$を$I_{fin}$で割って、$\mathcal{P}(\mathbb{N})/I_{fin}$というブール代数を考えることができる。これは、有限集合(finite)はすべて"0"に、補有限集合(cofinite)(補集合が有限な集合)はすべて"1"にマッピングされ、補集合をとっても無限な無限集合(例えば：2の倍数)に対して、それぞれのブール代数の要素が位置づけられる、かなりイメージしにくいブール代数となる。

 

[極大イデアルと極大フィルター]

 極大イデアル、または、極大フィルターを次のように定義する。

ブール代数$B$のイデアル：$I$  , フィルター：$F$ で、その剰余代数$B/I$  ,  $B/F$が、"トリビアルなブール代数”であるとき、極大イデアル(maximal ideal)  ,  極大フィルター(ultrafilter)という。

\[ B/I_{max}  \simeq  \textbf{2}    ,    B/F_{max}  \simeq  \textbf{2}   \]

 この定義から、$B$のどの元$\forall a \in B$も、$a$または、$\lnot a$のどちらか一方が$I_{max}$,$F_{max}$に含まれることになる。(両方とも含まれることはない)(これは逆も成り立つ)

 

さらに、あるイデアルやフィルタが存在すれば、それを含んで上記を満たす極大イデアル , 極大フィルターを見つけることができることが、選択公理を用いて、示されている。

 

たとえば、前出の"$\{2,3\}$の部分集合すべて"というイデアルは、

  • "$\{0,2,3\}$の部分集合すべて"
  • "$\{1,2,3\}$の部分集合すべて"

の二つが、それを含む極大イデアルとなる。"$1$を含む$B$の部分集合すべて"は、これ自体が極大フィルターである。

フリーイデアルはどうか？前出の$I_{fin}$は、極大イデアルではない。自然数の集合$N$の部分集合で、例えば"2の倍数の自然数すべての集合"というのは、無限集合であり、補集合も無限集合であるため、「どちらか一方がイデアルに含まれ」ていないため、極大イデアルではない。フレチェフィルターも同様である。それを含む極大イデアル/極大フィルターは存在することは(選択公理を用いて)証明できるのだが、具体的に構成することできない(非常に難しい)。このあたり、"選択公理"と関連し、"具体的に構成できない"点がバナッハ・タルスキーパラドクスを思い出す。

 

[ストーン表現とは]

さて、やっとここまできて、ストーン表現が説明できる。

 位相空間で、

  1. コンパクトで、
  2. ハウスドルフで、
  3. 完全非連結 (あるいは開かつ閉集合を基底にもつ ... これは同値)な、

なものをブール空間という。ブール空間$S$から、開かつ閉集合族を得る関数を$\textrm{B}(S)$と書くことにする。

ブール代数$B$から、その極大フィルターの集合を得る関数を$\textrm{S}(B)$と書くことにする。

すると、ある任意のブール代数$B$の極大フィルターの集合$\textrm{S}(B)$は、ブール空間となる。また、任意のブール空間$S$の開かつ閉集合族$\textrm{B}(S)$は、ブール代数となる。それぞれ対応するブール代数、ブール空間が存在して、

\[ f:B \to \textrm{B}(\textrm{S}(B))        f(a)=\{ U \in \textrm{S}(B):a \in U \} \]

 というマッピングが可能である。これがストーン表現である。$S$からも同様に一対一の対応関数が可能となる。

[例]

有限集合(finite boolean algebra)の集合代数に対応するブール代数については、直感的にも理解できる。有限集合は離散位相なので、集合$X$に対して、$B \simeq \mathcal{P}(X)$、$X \simeq \textrm{S}(B)$となる。有限集合代数の超フィルターはすべて主フィルターで、集合の要素ごとに定められることを考えると想像がつく。

ところが、無限集合の集合代数や、無限個の変数を持つ自由ブール代数については、ややこしい。

自然数$\mathbb{N}$の集合代数(infinite boolean algebra)は、非可算で連続体濃度の$\mathcal{P}(\mathbb{N})$となる。これの超フィルターは、自然数の主フィルターだけでなく、フリーな超フィルターも含んでいる。

可算無限個の変数$X$を持つ自由ブール代数$\textrm{F}(X)$については、対応するブール空間は、カントール集合$K$となる。(有限個の変数の場合の自由ブール代数の超フィルターがどうなっているかを確認すればよい。)しかし、principalな超フィルターは存在しないで、すべてフリーな超フィルターとなる。

以上を簡単に表でまとめると、以下のようになる。

 

ブール代数 $B$ ブール空間 超フィルター $S(B)$  そのほか

有限集合$X$の集合代数$B \simeq \mathcal{P}(X)$

有限集合$X$の通常の位相
  • 有限集合$X$の要素に対応する主な超フィルター
  

可算無限集合$\mathbb{N}$の集合代数$B \simeq \mathcal{P}(\mathbb{N})$

たとえば$ [ 0,\frac{1}{n} ]$?
  • $\mathbb{N}$の元に対応する主な超フィルター
  • フレチェフィルターを含むフリーな超フィルター
  • 連続体濃度
  • $\mathcal{P}(\mathbb{N})/I_{fin}$では主な超フィルターがなくなる

可算無限集合$X$を変数にもつ自由ブール代数$B \simeq \textrm{F}(X)$

カントール集合$K$
  • すべてフリーな超フィルター
  • 可算濃度!!!(有限個の変数の場合は$2^{2^{|n|}}$であるにもかかわらず!!)
  • 可算なブール代数は集合代数とは必ずしも一致しないが、$\textrm{F}(X)$の商代数と一致する。(論理式を評価する形で対応づけられる)

[ゲーデルの不完全性定理の代数化]

ところで、wikipediaのゲーデルの不完全性定理 - Wikipediaという記事の中に"不完全性定理の代数化”という章があって、

( Q ) を含む再帰的可算（RE）素イデアル p ⊂ B は存在しない。

とある。これとの対応を、ざっくりと考えてみると、

するのではないかと、素人考えで勘ぐっているが、正しいのかは定かでない。

 

[参考]

 

群の表現のさわり ... フーリエ変換まで

群の表現 線形代数 フーリエ変換

フーリエ変換とは、

\[ \hat{f}(k) = \sum_{x=0}^{n-1} e^{-2 \pi i k x/n} f(x)     ,     k \in {0,1,2,\cdots,n-1} \]

とか、

\[ \hat{f}(k) = \frac{1}{2\pi} \int e^{- i k x} f(x) dx     ,     k \in \mathbb{Z} \]

とかの有名な変換である。解析的には、関数を周期的な $ \sin , \cos $ の三角関数で分解すると一様収束する、などで直感的に理解するのだが、代数的な理解として群の表現という道具立てを使った解釈がある。

そのサワリの部分を調べた。

definition (群の表現)

群を$G$とする。群$G$の表現$(\rho,V)$とは、ベクトル空間$V$上の線形群$GL(V)$に対する対応：$\rho：G \to GL(V) $ で、次を満たす。

  • $\rho(gg') = \rho(g)\rho(g')   ,   g,g' \in G $
  • $\rho(e) = I $  ,   $e$は$G$の単位元、$I$は単位行列

$V$を$G$加群と呼ぶ。 ベクトル空間$V$に対し、表現が作用することを$\rho(g) v $とか、$\rho v$と書く。要するに、ベクトル空間$V$に作用する正則な行列で、群の演算と行列の積が自然に対応するもののことである。

 

たとえば、すべての群の元を単位行列に割り当てると、表現となる。これを自明表現と呼ぶ。
 

$V$の部分空間$W$で、

\[ w \in W  \rightarrow  \rho w \in W , \forall w \in W \]

なら、$W$も$G$加群である。この$W$を$V$の部分$G$加群と呼ぶ。(群$G$の部分群ではない。表現として展開された空間側の部分空間である。)

 

ベクトル空間$V$と$W$で、$V$から$W$への線形変換を

\[ \mu \in \textrm{Hom}(V,W)  \]

 と書く。$V$と$W$の表現があれば、これも$G$加群として表現とみなせる。$V$が$n$,$W$が$m$次元ベクトル空間とすると、$m \times n$の行列で$V^* \otimes W$と同型である。

具体的にどう表現が記述されるかというと、$( \rho_V,V )$と$( \rho_W,W )$で、

\[ \rho_W(g)  \mu  \rho_V(g^{-1}) \rightarrow \mu'  \in \textrm{Hom}(V,W) \]

と書けばよい。$\rho_V(g^{-1}) = \rho_V(g)^{-1}$で、下記の図の$v$から$w$への線形変換について、ぐるっと$v'$,$w'$を経由する作用となる。

\[  \begin{array}{ccc} v'  &  \xrightarrow{\mu}  &  w' \\  {\scriptsize \rho_V(g)}  \downarrow \quad  & &  \quad \downarrow {\scriptsize \rho_W(g)} \\ v & \xrightarrow{\mu'} & w  \end{array} \]

なお、$W=\mathbb{C}$である場合、この線形変換は$V$の双対空間$V^* = \textrm{Hom}(V,\mathbb{C})$とみなせて、この場合を特に双対表現と呼ぶ。(*はエルミート共役。エルミート内積を扱いたいのである。)


definition (既約表現、可約表現)

部分$G$加群を自身と{0}以外に持たない表現を既約表現という。(持つものを可約表現という)

 

definition ($G$線形写像)

$\mu\in \textrm{Hom}(V,W)ですべての $ g \in G $ に対して不変なものを、

\[ \mu\in  \textrm{Hom}_G(V,W) \]

と書いて、これを$G$線形写像という。これは、先の図の→矢印$\mu$と$\mu'$が同じ(不変) で$\mu(\rho_V(g)v)=\rho_W(g) \mu(v)  \in W $ になるということである。このとき、

  • $\textrm{ker}  \mu  \subseteq  V $は$V$の部分$G$加群
  • $\textrm{Im}  \mu  \subseteq  W $は$W$の部分$G$加群

 である。

 

群が有限群なら、任意の表現は既約表現の直和で表される。(これを完全可約という)

 

schr's Lemma

$V$,$W$が既約な$G$加群とすると、$G$線形写像 $\phi  \in  \textrm{Hom}_G(V,W)$は、以下が成り立つ。

  1. $\phi $は同型(つまり$V \simeq W$)、または$\phi=0$
  2. $V \simeq W$ならば、$\phi = \lambda I  (\exists \lambda \in \mathbb{C}) $ ($I$は単位行列)

 ※既約なので部分$G$加群が無く、$\textrm{ker}  \phi,\textrm{Im} \phi $が部分$G$加群でない→同型

 ※固有値$\lambda$を一つ考えて、$\phi -\lambda I$を検討すればよい

 

完全可約な任意の表現$(\rho,V)$は、既約表現$(\rho_i,V_i)$を使って、

\[ V = \bigoplus V_i^{a_i}   ,    (a_iは多重度)  \]

と分解できる。$\rho$のほうはというと、適当な変換行列$P$を使って、

\[ \rho(g) = P^{-1} \begin{pmatrix} \rho_1(g) &   &   &   \\   & \rho_2(g) &   &   \\  &  & \ddots  &   \\   &   &  & \rho_i(g)  \end{pmatrix} P \]

と、 対角成分にそれぞれの既約表現を多重度を含めて並べたものに変換できる。※既約表現は1次元とは限らず、$V_i$の次元を$n_i$とすると、$V$の次元は $\sum a_i n_i$となる。

 

definition (指標)

群$G$の表現$(\rho,V)$に対し、指標($\chi_V(g)$とは、

\[ \chi_V(g) = \textrm{tr}(\rho(g))      ,        ※\textrm{tr}は行列のトレース   \]

という、 $\chi$：$G \to \mathbb{C}$の関数である。

 行列のトレースの性質 $ \textrm{tr}(AB)=\textrm{tr}(BA)$ より、

\[ \chi_V(hgh^{-1}) = \chi_V(g) \]

が成り立つ。このことから、指標は群$G$の共役類上の類関数である。(共役類で同じ値を持つ)

※行列$A$の固有値が$\lambda_i$なら、$\textrm{tr}(A)=\sum_i(\lambda_i)$

また、関数$\chi$は次を満たす。

  • $\chi_{V \oplus W} = \chi_V + \chi_W$
  • $\chi_{V \otimes W} = \chi_V  \chi_W$

 先の完全可約の既約分解から、指標をとると、

\[  \chi_V = \sum_i a_i \chi_{V_i}   ,    (a_iは多重度)    \]

と既約表現の指標の和でかける。

 

definition (自明表現への射影公式)

$G$の表現$(\rho,V)$があったとき、$G$上で$V$への作用を”平均”した射を考える。

\[ \psi = \frac{1}{|G|} \sum_{g \in G} g = \frac{1}{|G|} \sum_{g \in G} \rho(g)  \]

これは、次の性質を持つ。

  • $V$から、V内のすべての自明表現の和($V^G$と書く)への射影で$G$線形写像である。
  • $\textrm{tr}(\psi)$は、自明表現の重複度($V^G$の次元)が得られる。

$V$と$W$を既約$G$加群としたときの線形変換$\textrm{Hom}(V,W)$について考えると、この自明表現は、$G$線形写像$\textrm{Hom}_G(V,W)$に他ならない。この次元=重複度は、schr's lemmaから、

\[ \textrm{dim}  \textrm{Hom}_G(V,W) =\left \{ \begin{array}{rl} 1  & if    V \simeq W \\ 0  & if   V \not\simeq W \end{array} \right. \]

 である。

definition ($G$不変エルミート内積)

類関数がなすベクトル空間を$\mathbb{C}_{class}(G)$として、$G$上の$\mathbb{C}$値関数空間の内積を

\[ (\alpha  ,  \beta) = \frac{1}{|G|}  \sum_{g \in G} \overline{\alpha(g)} \beta(g)  \]

と、$G$の元で平均を取る(つまり$G$不変)ものを定義する。( $\alpha,\beta \in \mathbb{C}_{class}(G)$ )※$\overline{\alpha}$は、エルミート共役

$V$と$W$を既約$G$加群としたときの線形変換$\textrm{Hom}(V,W)$にたいして、自明表現の射影公式を作用して指標をとる。$\textrm{Hom}(V,W)$は$V^* \otimes W$と同型であるから、

\[ \textrm{tr}(\psi) = \frac{1}{|G|} \sum_{g \in G} \chi_{V^* \otimes W}(g) = \frac{1}{|G|} \sum_{g \in G} \chi_{V^*}(g) \chi_{W}(g) = ( \chi_{V} , \chi_{W} )  \]

となって、定義した内積となる。$V$と$W$が既約の場合で、同型なら内積が1,そうでなければ0ということから次がいえる。

指標の正規直交性

有限群$G$の既約表現の指標は、上記内積に関して、直交している。

 

表現$V$が既約なら、かつそのときに限り、内積$(\chi_V,\chi_V) = 1$となる。

表現$V$で分解される既約表現$V_i$の重複度$a_i$は、次のように、指標の内積で表せられる。

\[ a_i = ( \chi_V, \chi_{V_i} ) \]

また、任意の表現$V$について、次が成り立つ。

\[ ( \chi_V, \chi_V ) = \sum_i a_i^2      , ※a_iは、既約表現の多重度\]

 

置換表現、正則表現

有限群$G$が、有限集合$X=(x_1,x_2,\dots,x_n)$の置換群として作用するとき、$V=\mathbb{C}e_{x_1} + \mathbb{C}e_{x_2} + \dots + \mathbb{C}e_{x_n}$という、$n$次元のベクトル空間を定義して、

\[ \rho(g): V \to V   ,   \rho(g) e_{x_i} = e_{gx_i} \]

と作用するものを置換表現という。たとえば、対称群$\mathbb{S}_3$に対して、$n=3$の置換表現が作れる。特に、$X=G$として、$n=|G|$としたものを「正則表現」$R_G$と呼ぶ。

 

正則表現$R_G$の指標は、$G$の単位元とそうでない場合で場合分けできる。

 \[ \chi_{R_G}(g) =\left \{ \begin{array}{rl} 0  & if    g = e  \\ |G|   & if   g \not= e \end{array} \right. \]

 正則表現の既約分解を考える。任意の既約表現$V_i$について指標の内積をとると、

\[ ( \chi_{V_i},\chi_{R_G} ) = \frac{1}{|G|} \chi_{V_i}(e) \chi_{R_G}(e) = \textrm{dim}  V_i \]

これは、対象の既約表現の重複度に等しい。

この結果から、

\[ |G| = \textrm{dim}(R_G) = \sum_g \textrm{dim} V_i  \chi_{V_i}(e) = \sum_i (\textrm{dim} V_i)^2 \]

また、$\chi_{R_G}(g) =0  , g\not=e $より、

\[ \sum_i ( \textrm{dim} V_i) \chi_{V_i}(g) =0   ,   if      g \not= e  \]

が得られる。これらから、後で述べるフーリエ変換の逆変換が成り立つことがわかる。

 

群環

有限群$G$の群環(group algebra)$\mathbb{C}G$とは、$G$の元を基底とみなした$\mathbb{C}$上のベクトル空間

\[ \sum_{g \in G} a_g g            g_g \in \mathbb{C} \]

であり、この積は、基底間の積を群の演算としたものである。

\[ \bigl( \sum_{g \in G} a_g  g \bigr) \bigl( \sum_{h \in G} b_h  h \bigr) = \sum_{gh} a_g b_h  gh      gh \in G  \]

群上$\mathbb{C}$値関数空間$f(g)$は、上記の係数$a_g=f(g)$と割り当てれば、自然と対応付けられる。このときの関数$f(g)$の積は、

\[ f * f'(g) = \sum_{g \in G} f( g h^{-1} ) f'(h)  \]

という、畳み込みになる。$f$は畳み込みで代数になる。これを$(\mathbb{C}(G),*)$と書く。

さらに、$G$の表現$(\rho,V)$があれば、群環から$V$の自己写像への自然な対応(これを群環の表現という)　$\rho:\mathbb{C}G \to \textrm{End}(V) $ が得られる。次のように対応付けられる。

\[ \sum_{g \in G} a_g \rho(g)  \in \textrm{End}(V) \]

これも要するに、群環の各基底を$G$の表現$rho$に置き換えて行列演算することでえられる。

 

環同型

以下が成り立つ。

\[ (\mathbb{C}(G),*)  \simeq \mathbb{C}G \simeq  \bigoplus \textrm{End}(W_i)  \]

※G上代数が成り立つ$f$は、既約表現の和空間と同型

※$f$が類関数なら$f(hgh^{-1})=f(g)$で、群環の中心となる。

 

フーリエ変換とは

フーリエ変換とは、上記の環同型、群上$\mathbb{C}$値関数空間を既約表現の分解に変換したものなのである。

\[ \hat{f}(\rho) = \sum_{g \in G} f(g) \rho(g)    ,  \hat{f}(\rho) \in \textrm{End}(V) \]

群が可換群なら$\hat{f}$は1次元になって、有限のフーリエ変換と一致する。

非可換ならとり得る引数の表現$\rho$による行列が得られて、これは、$V$の自己写像$\textrm{End}(V)$である。

逆変換は、

\[ f(x)=\frac{1}{|G|}\sum_{\rho \in \hat{G}} \textrm{dim}  V_\rho  \textrm{tr} \bigl( \rho(g^{-1})\hat{f}(\rho) \bigr) \]

とかけるらしい。※$\hat{G}$は$G$の既約表現の同値類全体

 

連続の場合

これまで、群は暗黙のうちに有限群である想定で書いたが、これを局所コンパクト群の場合でも、ほぼ同じような議論ができるらしい。

definition (局所コンパクト群)

群#G#が局所コンパクト位相空間で、直積位相空間$G \times G$から、$G$への写像、および$G$から$G$への写像

\[ (a,b) \mapsto ab     および     a \mapsto a^{-1}   , a,b, \in G \]

が位相連続であるものをいう。

 

この場合の群$G$の表現は、対象が有限次元ベクトル空間とは限らなくなる。ので今までの議論がざっくり、こんな感じで変わる。(厳密ではない)

  • ベクトル空間$V$  $\rightarrow$  複素ヒルベルト空間  $\cal{H}$
  • 線形群$\rho$  $\rightarrow$  $\cal{H}$上の有界線形作用素  $B(\cal{H}) $
  • 群の表現の定義に写像$T:G \to \cal{H}$が強連続、つまり、$ x \mapsto T(x) v  ( x \in G , \forall v \in \cal{H} )$が$G$上連続

といった感じ。そうすると、

  • 局所コンパクト群の有限次元ユニタリ表現は既約表現の直和に分解される
  • コンパクト群の既約ユニタリ表現はすべて有限次元で、任意のユニタリ表現は既約ユニタリ表現の直和に分解される
  • 可換群の既約ユニタリ表現はすべて1次元で、指標となる

みたいな結果が得られるとのこと。最後のが積分形式のフーリエ変換に対応する。

 

参考：

線形代数のキソ ... 三角化とLU分解

線形代数

線形代数 ... 要するに行列計算についての簡単なメモ。

三角化

$ n $次正方行列の $ X $ があるとする。これに適当な正則行列$ P $を使って、

\[ P^{-1}  A  P  = \begin{pmatrix} a'_{11} & a'_{12} & \cdots & a'_{1n} \\ 0 & a_{22} & \cdots & a'_{2n} \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & a'_{nn}  \end{pmatrix} \]

と、三角行列(上の場合は上三角行列)にすることを、三角化(上三角化)という。

これは、いわゆる固有値問題

\[ A \mathbf{x} = \lambda \mathbf{x}  \]

の解である、固有値と固有ベクトルを解くことで得ることができる。すなわち、$P$が固有ベクトルを(正規化して)並べたもので、三角化された行列の対角成分が、

\[ P^{-1}  A  P  = A' = \begin{pmatrix} \lambda_1 & a'_{12} & \cdots & a'_{1n} \\ 0 & \lambda_2 & \cdots & a'_{2n} \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix} \]

と、固有値によって三角化される。

三角化された行列$A'$が対角行列(上側も下側も0)になる場合を対角化という。

\[ P^{-1}  A  P  = A' = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix} \]

この方が、固有値問題からの帰結はイメージしやすい。両辺に左から$ P $をかけてやれば、

\[ A P = P A' = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & & \vdots \\ x_{n1} & x_{n2} & \cdots & x_{nn}  \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix}  \]

各固有値$ \lambda_i $ に対して、固有ベクトル $ \mathbf{x}_i = ( x_{i1},x_{i2},\cdots,x_{in} )^t $ を割り当てると、それぞれの列で成り立つことがわかる。

 ただし、"場合もある"といったように、任意の行列$ A $は必ずしも対角化できない。それは、$ P $が正則でなくなる場合である。すなわち、固有ベクトルが一次従属であり、多重固有値による固有ベクトルを考えて、その一次独立性を検討すればこれを確認できる。

固有値問題

 固有値問題は、以下を満たす$ \lambda $ と $ \mathbf{x} $ を求める問題あった。

\[ A \mathbf{x} = \lambda \mathbf{x}  \]

 これを解くのに、行列式を使って解くのであった。

\[\det( A - \lambda  I)  = 0  \]

n次$ \lambda $係数の代数方程式になるのであるが、代数学の基本定理より「n次方程式は，複素数の中にn個の解を持つ」ので、$\lambda$の解は$\mathbb{C}$ の中に$n$個見つかるはずである。逆に言うと、$n$次の正方行列$A$が、そもそも体$\mathbb{C}$上の行列であれば、$ n $個の$ \lambda $ を使って、三角化が必ず可能だけれども、複素数$\mathbb{C}$体上の行列でないのであれば、そもそも三角化もできない場合もありうる、ということに注意が必要である。

ここでは$\mathbb{C}$体上の行列として話を続ける。

固有値の解を$ \lambda_1,\lambda_2,\cdots,\lambda_n $とすると、同じ値を固有値が複数表れる場合もある。これを多重固有値と呼ぶ。それぞれ固有値の多重度を$ \textrm{r}( \lambda_i ) $ とすると、

\[ \sum_{i=1}^n \textrm{r} ( \lambda_i ) = \textrm{rank}(A) = n \]

 と、行列の階数に等しくなる。これに対し、固有値$\lambda_i$の固有ベクトル$ \mathbf{x}_i $の自由度を$ f_i $とすると、

\[ 1 \le f_i  \le \textrm{r}(\lambda_i) \]

が成り立つ。

もともとの固有値問題 $ A \mathbf{x} = \lambda \mathbf{x} $は、両辺スカラー倍しても成り立つから、固有ベクトル $ \mathbf{x} $ は、少なくとも1の自由度(スカラー倍)をもつ。

さらに、固有ベクトル $ \mathbf{x} $ は、$ (A-\lambda_i I)\mathbf{x}=0 $が成り立つ。$ ( A-\lambda_i I) $の階数は、 $\lambda_i $の重複度 $ \textrm{r}(\lambda_i) $ により、$ n - \textrm{r}(\lambda_i) \le \textrm{rank}(A-\lambda_i I)  \le  n $ であることから、上記の不等式が成り立つのである。

 直感的には、固有値の重複度と固有ベクトルの自由度は一致しそうなのだが、そうではない。そして、そうではない場合が、対角化不可能となる。たとえば、

\[ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 &-1 \\ 0 & 1 & 3 \end{pmatrix} と \begin{pmatrix} 2 & 0 & 0 \\ 0 &-1 &-3 \\ 0 & 2 & 4 \end{pmatrix} \]

左は対角化不可能だが、右は対角化可能である。これらはどちらも特性方程式が、

\[ \det(A - \lambda I ) = (\lambda-2)^2(\lambda-1) \]

である。固有値$ \lambda=1,2,2 $となり、固有値2の場合の固有ベクトルの自由度で確認できる。※特性方程式は行列のすべてを表してはいないのである。

ちなみに、左側の行列の2行目以降の2行2列の行列

\[ \begin{pmatrix} 1 &-1 \\ 1 & 3 \end{pmatrix} \]

は、固有値2が重複して対角化できないのに対し、右側の行列の同じ部分は

\[ \begin{pmatrix}-1 &-3 \\ 2 & 4 \end{pmatrix} \]

は、別々の固有値$\lambda=1,2$で対角化できる。固有値2は、1行1列の対角成分”2"と重複しているからで、これと分離しているから対角化が可能なのである。

もう一つ、

\[ \begin{pmatrix} 2 & 1 & 0 \\ 0 &-1 &-3 \\ 0 & 2 & 4 \end{pmatrix} \]

の場合は、対角化ができない。上三角側に追加した成分"1"が影響するからだ。

まとめると、

  • 複素数体$\mathbb{C}$上の任意の行列であれば、適当な変換行列を用いて三角化が可能。これは固有値問題を解くことで得られる。
  • このうち対角化が可能なのは、特別な場合で、固有値問題の解の固有ベクトルがすべて一次独立の場合に対角化可能となる。
  • 固有値問題の解自体、複素数体$\mathbb{C}$上でないと解けない場合がある。固有値が得られなければ三角化もできない。

LU分解

最後に、LU分解について少し。 "三角化"という言葉とLU分解の仕組みのせいでごっちゃになってしまうことがある。

LU分解は、任意の行列$ A $ を、下三角行列 $ L $ と上三角行列 $ U $ の分解することである。

\[ A = LU \]

 シンプルである。これは、今までの"三角化"とは若干スジメが異なっていて、固有値問題ではなく、

\[ A \mathbf{x} = \mathbf{b}  \]

 いわゆる連立方程式を解くときに現れる手法である。

\[ A \mathbf{x} = L U \mathbf{x} = \mathbf{b}  \]

として、$ U \mathbf{x}=\mathbf{y} $ と新たにおいて、

\[ L U \mathbf{x} = L \mathbf{y} = \mathbf{b}  \]

を解く。これが連立方程式を解くときの有名なガウスの消去法である。Aが正則であれば、LU分解できる。

 

特定秘密保護法案のコメントを簡易テキストマイニング

データマイニング D3.js python テキストマイニング

特定秘密保護法案が先週の金曜日(12/6)可決された。いろいろな問題が指摘されているが、ここでは、ネットで公開されているアンケート結果を元に、簡易的なテキストマイニングを試みてみた。

分析対象

某有名新聞社 A新聞のHPでは、特定秘密保護法案のトピックスの中で、投稿マップというイベントを行っていた。これは、

  • 横に、この法案に賛成 or 反対の軸
  • 縦に、"日本の安全が脅かされていると感じるか"どうか、の軸

のマップがセルボタンで構成されていて、その中で自分の意見に一致する場所をクリックし自分のコメントを残せる、という仕組みである。投稿されたコメントは、すべて閲覧することができるので、マッピングの意見と、それに対応するコメントの傾向を調べることができる。テキストマイニングでは、コメントなり何なりの単語の数を数えたりする。(文の論旨、論理の把握というのはとても難しい)ので、マッピング軸に対応するコメントの議題(論旨ではなく)を、単語の分布傾向によって推し量ってみよう、というのが今回の主旨である。

マッピングはタテヨコに10段階 ... 100個のボックスに意見を記入できる仕組みだったのだが、ここでは、"法案に賛成・反対"の軸(横軸)に絞る。法案に対する意見とそれに対応する"コメントの中の単語分布"がどうなるか？ ... 今回調査するデータは、法案成立直前、2013/12/06 20:19 更新時のものを利用する。(特に理由は無く、ちょうどそのタイミングでデータを取ったから。)

ちなみに、僕の意見をあらかじめ言っておく。科学的調査をするにあたっては、客観性が最も重要なので、僕もそのようにおこなうつもりだが、人間である以上、完全に客観的になれるものでもないと思う。だから、調査者は、先に自分の立ち居地について事前に表明していたほうがよいという考えである。僕は、この法案についてどちらかというと慎重論者である。

データ抽出方法

さて、ではどう分析するか？まずデータがなければ始まらない。データを集めて精製するのはそんなに難しくない。

  1. 事前にツール環境を作る。簡易DB ... sqliteを導入
  2. python でHTMLを扱うので、HTML分析用Beautifulsoup導入
  3. 日本語の形態素解析...Mecab を導入 & python-mecabドライバ
  4. A新聞社からコメントのHTMLをファイルにして保存(webブラウザでできる)
  5. Beautifulsoupでコメント抽出(by python)
  6. Mecabで分かち書き、単語単位に分ける
  7. sqliteにデータベースとしてぶっこむ。
  8. あとはSQLをたたいて平均なり何なりを確認

以上。これには虎の巻(というかカンペ)があって、

集合知プログラミング

集合知プログラミング

 

 先の手順のうち、2と6の日本語形態素解析関連以外は、この本にやり方が載っているのでお勧め。Mecabまわりについてもそんなに難しくない。たとえばこんな感じ。

import MeCab as mc
stoppos=[u'助詞',u'助動詞',u'副詞',u'接続詞',u'連体詞',u'記号']
stopwrd=[u'する',u'いる',u'ある',u'てる',u'思う',u'こと',u'これ',u'あれ',u'それ',u'れる',u'なる']
LANG_MODE='utf-8'
def getWordsList(text):
    pttrn=re.compile('[a-z]+$')
    tmc=mc.Tagger()
    wl=[ ]
    parse_str=tmc.parse(text)
    if isinstance(parse_str,str):
        for w in parse_str.split('\n'):
            v=w.split(',')
            word=unicode(v[0].split('\t')[0],LANG_MODE)
            pos=unicode(v[0].split('\t')[-1],LANG_MODE)
            if pttrn.match(word)==None and len(v)>=3 and pos not in stoppos:
                k1=unicode(v[1],LANG_MODE)
                k2=unicode(v[2],LANG_MODE)
                uw=unicode(v[-3],LANG_MODE)
                if len(uw)>=2 and k1 not in stoppos and k2 not in stoppos:
                    if (uw,pos) not in wl and uw not in stopwrd:
                        wl.append( (uw,pos) )
    return wl

 textで入力された文を形態素解析して、stopposとstopwrdで調査対象としない品詞と単語を外し、そのtextに含まれていた単語のリストを返す。(同じ単語で違う品詞の場合も有りうるので品詞と組にして返している)

今回の分析では、一つのコメントの中で同一単語の数は数えないことにする。つまり、あるコメントにその単語が含まれるか否か、"有無"をDB化した。コメント自体が短いのと、後の分析する指標の見通しを良くするためである。

分析-評価の方法

さあDBができた。じゃ平均とって見るか...って何の平均を取るんだっけ？

説明し忘れていることがある。対象のコメントは、それぞれ縦と横に10段階、100セルのマッピングで意見が表現されているのであった。このマッピングを数値化しておかねばならない。ここでは単純に、-1～1 までの区間で数値化する。今回は横軸についての調査なので、マップの左側、もっとも反対が-1 、以降0.2ずつ増えて、右側のもっとも賛成が1になる。この数値(インデクスと呼ぼう)で、実際のコメント数の分布状況を確認してみると、

意見 反対 ← ← ← ← → → → → 賛成
数値(インデクス) -1.0 -0.8 -0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1.0
コメント数合計 2788 121 43 23 39 62 44 100 205 4879

 賛成意見のほうがかなり多いことがわかる。ここで、各コメント数とインデクスを掛け合わせ、インデクスとしての平均を取る。

コメント数合計 インデクスの平均 インデクスの分散
8304 0.26558 0.88586

 賛成意見のほうが多いので、インデクスの平均は正の数になる。0.26という数値は、全体の大体26%増しで賛成意見のが多い、という解釈ができる。(分散はとりあえず気にしないこと)

さて、コメントの単語の有無に対するデータベース化をすでに行っているので、「ある単語が含まれるコメントについてのコメント数合計・インデクス平均・分散」を、上記で全体に対して行ったのと同じように、計算することができる。各単語のインデクス平均を調べて、それが1.0に近ければ、賛成のコメントにより多く使われている単語で、-1.0に近ければ、反対のコメントにより多く使われている単語、というわけである。(単語のインデクス平均は、-1.0～1.0の間を取る)

ただし、この評価の注意点として、単語の数が非常に少ない場合がある。たとえば、一回しか出現しない単語で、その一回が数値インデクス-1.0の反対コメントであれば、その単語のインデクス平均は-1.0で、"反対のコメントに多く使われる単語"となってしまう。これを避けるために、全体の単語の出現数がある一定以上のものを調査対象とする。

結果

さて、後は計算してリスト化するだけだ。単語の出現数の閾値は、ここでは、100コメント以上のものを調査対象にする。(全体コメント数が8000超なのでこれで十分か)

まず「賛成派側のコメントにより多く使われる単語」を20個リストしよう。

単語 品詞 含まれるコメント数 インデクス平均 母集団平均値との差(標準偏差単位)
スパイ 名詞 915 0.856 18.988
必要 名詞 1496 0.672 16.682
賛成 名詞 905 0.783 16.530
マスコミ 名詞 742 0.811 15.771
朝日新聞 名詞 301 0.923 12.117
報道 名詞 589 0.706 11.364
防止 名詞 343 0.821 10.929
天国 名詞 272 0.878 10.730
機密 名詞 581 0.682 10.654
反日 名詞 202 0.950 10.343
当たり前 名詞 193 0.950 10.106
朝日 名詞 214 0.915 10.093
国益 名詞 219 0.847 9.135
無い 形容詞 422 0.671 8.851
偏向 名詞 116 0.972 8.088
中国 名詞 546 0.572 7.611
早い 形容詞 143 0.856 7.501
不思議 名詞 113 0.927 7.475
普通 名詞 176 0.795 7.469
日本人 名詞 262 0.682 7.156

つぎは、「反対派側のコメントにより多く使われる単語」20個。

単語　　 品詞 含まれるコメント数 インデクス平均 母集団平均値との差(標準偏差単位)
国民 名詞 1666 -0.261 22.820
秘密 名詞 1688 -0.219 21.172
主義 名詞 430 -0.687 20.987
政府 名詞 451 -0.610 19.761
民主 名詞 356 -0.675 18.861
戦前 名詞 261 -0.764 17.672
安倍 名詞 255 -0.740 17.068
政治 名詞 314 -0.612 16.524
憲法 名詞 220 -0.748 15.976
権力 名詞 186 -0.827 15.830
戦争 名詞 348 -0.521 15.595
政権 名詞 420 -0.447 15.509
隠す 動詞 213 -0.716 15.227
しまう 動詞 295 -0.555 14.967
悪法 名詞 137 -0.917 14.704
廃案 名詞 173 -0.754 14.245
自民党 名詞 163 -0.780 14.188
維持 名詞 185 -0.703 13.993
治安 名詞 164 -0.759 13.934
官僚 名詞 147 -0.780 13.464

いかがだろうか？割といろいろな傾向が見えてきていると思う。マスコミ関連の単語が多いのは、このアンケートの主催自体が新聞社だからか...

この結果の細かい分析については、ここでは見送ろうと思う。

補足

※それぞれの順位は、インデクス平均ではなく、"どれだけ母集団(全体のコメント)から偏っているか"の基準を示す"母集団平均値との差*1"で、20個をリストしている。これについての詳細は脚注に記す。

最後に

 せっかくなので、得られた単語のリストを使い、勉強中のD3.jsで単語雲(word-cloud)を作ってみた。言及しているコメントが多いほど文字を大きく、賛成派は赤、反対派は青で表示している。(D3.jsはIE8と古いブラウザでは表示できませんあしからず)

こうゆうことがすぐできるD3.jsすばらしい。

*1:母集団の平均を $ m $ 、母分散を$\sigma^2$であるとする。そこから、ランダムに十分多い$n$個データを取得して標本としたとき、この標本の平均は、平均 $ m $ (母集団と同じ)、分散$\sigma^2/n$で表される。そこで、この標本分散による標準偏差$\sigma/\sqrt{n}$をつかって\[母集団平均値との差=\frac{|m-標本平均|\sqrt{n}}{\sigma} \]として計算している。つまり1で、標準偏差程度の差がある、ということ。