カテゴリー別アーカイブ: ITとデータマイニング

[解説]「再帰関数で逆順並べ替え」

問題文

再帰関数で逆順並べ替え
基本関数だけで逆順アルゴリズムを実現してみよう!
今回の問題は基本的な関数のみを使って、リスト項目を逆順にするアルゴリズムを考えてみます。

問題
4つの関数car, cdr, cons, nullpのみを使って、リストの項目を逆順にする関数reverse_auxとreverse2をつくってください。

例えば、reverse2は['A','B','C','D']を、逆順の['D','C','B','A']に並べ替えます。

reverse2()は1変数、reverse_aux()は2変数のリストを取ります。
最終的には、reverse2が必要なのですが、その前段階としてreverse_auxを作ってください。


reverse_aux(x, y)の性質は以下の通りです。

reverse_auxは、リストx, yを取ります。
例えば、

reverse_aux( [‘A’, ‘B’, ‘C’, ‘D’], [‘E’, ‘F’, ‘G’] )

= [‘D’, ‘C’, ‘B’, ‘A’, ‘E’, ‘F’, ‘G’]

 のように、リストxを逆順にして、リストyはそのままで連結します。 まず、reverse_auxを作ってください。 
●基本関数 使って良い関数はcar, cdr, cons, nullpのみです。
・carは先頭の項目を返す関数です。
例えば、

car([‘A’, ‘B’, ‘C’]) = ‘A’

・cdrは先頭項目を除いたリストを返す関数です。   例えば、

cdr([‘A’, ‘B’, ‘C’]) = [‘B’, ‘C’]

 ・consは一つの項目とリストを引数する関数です。consは項目xをリストyの最初に付け足したリストを返す関数です。
例えば、

cons(‘X’, [‘A’, ‘B’, ‘C’]) = [‘X’, ‘A’, ‘B’, ‘C’]

 ・nullp()は1変数の関数で、true <- nullp([]) となり、それ以外の時(アトムあるいは有限要素数のリストの場合)はfalseを返します。
reverse_auxを定義する前に、予め自分の処理系でcar, cdr, cons, nullpを定義してください。 その時は、どんな組み込み関数を使っても構いませんが、reverse_auxだけは、上記の基本関数のみを使ってください。ただし、ifなどの条件文やreturnなどはOKです。
最後に、reverse_auxを使って、reverse2を作ってください。 名前がreverse2なのは、built-in関数との競合を防ぐためです。問題なければ、reverseでも結構です。 作成したコードは、ファイル名を reverse.txt として、アップロードしてください。

その他注意事項 今回の問題は、純LISP に関する問題です。 LISPで解くと簡単にできますが、他の言語処理系だと基本関数定義の所で手間取るかもしれません。 結構大変かと思いますが、頑張ってください。 言語はPythonを希望しますが、解答の論理構造がわかるものであれば、どの言語処理系でも解答可能です。

解説

今回は純LISPに関する問題です。純LISPとはatom, eq, car, cdr, consとう5つの基本関数でプログラミング言語です。実際には、cond, quote, lambda, defineという関数も必要となりますが、必要最小限のもので、プログラミング言語を作ることができるというのは非常に面白い考えだと思います。まるで、数学の有限の公理で色々な証明を行うのに似ています。

Pythonでの解答例


#!/usr/bin/python

#
# reverse.py
#

def car(x): return x[0]

def cdr(x): return x[1:]

def cons(x, y): return [x] + y

def nullp(x): return len(x) == 0

def reverse_aux(x, y):

print x, y # Show variables
if nullp(x):
return y
else:
return reverse_aux(cdr(x), cons(car(x), y))

def reverse2(x):

return reverse_aux(x, [])

####
print reverse_aux([‘A’,’B’,’C’,’D’], [‘E’,’F’,’G’])


reverse_aux(X, Y) の解説をします。

diagram

X=[‘A’,’B’,’C’,’D’], Y=[‘E’,’F’,’G’] とすると、cdr(X)=[‘B,’C’,’D’]を次のreverse_auxのX’に引き継ぎます。更に、car(X)=’A’とY=[‘E’,’F’,’G’] をcons()で結合したものを次のreverse_auxのY’に引き継ぎます。処理がreverse_auxで再帰的に行われ、X部分の要素が逆順になります。

うまく、再帰関数で定義できたでしょうか。再帰関数を使うと、whileやfor文などを使わずに、繰返し処理が表現できますね。

統計学の興味は個別データではなく、集団に関する情報

以前、データジャーナリズムのイベントでジャーナリストと一緒に仕事をしたが、どうしてもデータに対する考え方の違いがあって、どうにもはっきりしなかった。しかし、量的研究エッセンシャルという記事を見て、自分の中のモヤモヤ感がはっきりした。

簡単に言うと、統計学・データサイエンティストは個別のデータに関心があるのではなく、個別データの背後にある一般的な仕組みや規則に興味がある。一方、ジャーナリストは個々のデータや事件に興味があるのだと思う。それで、両者のデータに関する考え方の違いでどうも通じ合えないのではないだろうか。

記事の内容をまとめてみた。元の記事を見たほうが分かりやすいかもしれないので、是非元記事をみるのをお勧めする。かなり丁寧に書かれた記事であり、更に連載記事なので他の記事も通して読んでみると統計学・データ解析の本質が分かると思う。

(要約)

量的研究での関心事は個別データの背後にある一般的な仕組みや規則を明らかにすることだ。

統計学では個別データは母集団という仮想世界から現実世界へ偶然に生じたものと考える。

データと説明可能なモデルとノイズに分けると確率的考えで変動をうまく説明できる。

量的研究の関心事は個別データではなく、集団に関する情報であり、個性はノイズとみなす。

世の中の現象は多数の要因が絡みあって生じるので予測は確率的にしかできない。

 

統計学・データサイエンスの勉強法

ここ数年、私はデータサイエンスについて学んでいます。おすすめの学習資料を紹介したいと思います。

教師用の教科書と初心者用の教科書

私自身、データサイエンスを学ぼうとして色々なソースを試してみました。残念なことに、日本語の良い学習資料は見つけられませんでした。どこかのブログで読んだことがありますが、教科書は教師用と学生用の二週類があるそうです。一つめは内容が既に分かっている教師の為の教科書で、日本はこのタイプです。もう一つのタイプの教科書は自学自習を目的に作られているので、教師なしで学ぶできる教科書になっているということで、アメリカはこのタイプの教科書が多いです。私自身、他の文系・理系の教科書を探した時もアメリカの教科書の方が分かりやすく、その本だけを読めば分かるようになっていると同じ印象を持ちました。

オンライン教育(MOOC)

アメリカは科学教育に熱心であり、最近はやりのMOOCでも豊富なコースが無料で受けることができます。有名なのはCoursera, Udacity, EdXがありますが、私はもっぱらCourseraのファンなのでCourseraのコースを紹介します。

1. Machine Learning by Andrew Ng

Courseraの創設者の一人Andrew NGが講師で、ビジュアル的に板書で説明してくれるので、計算の理屈がよく分かりました。Courseraのコースの中で最も授業が上手だと思います。最近、完全に日本語字幕もついたので、かなり受講しやすいです。

2. Johns Hopkins 大学のData Specialization

これは9つのData Science関連コースが合わさったものですが、中のRoger D. Pengのコースがお勧めです。Rの基礎やデータクレンジング等について丁寧に解説してくれます。しかし、Brian Caffoのコースは説明が下手なので、お勧めしません。

お勧めのコース

R Programming 統計プログラミング言語Rの初歩

Exploratory Data Analysis データ解析の予備的解析やデータ探索

Reproducible Research データ解析手順を再現可能にするための技術(ドキュメント化やパブリッシング)

Getting and Cleaning Data データ解析前のデータの整形や洗浄

3. Social Network by Lada Adamic

ソーシャルネットワークやネットワークグラフに興味のある人は取ってみたら良いとおもいます。

4. Mining Massive Datasets from Stanford大学

私はまだコースを受講していませんが、かなりきっちりとカリキュラムが組まれているようです。

授業内容は書籍が出版されているようで、PDF版は無料で見ることができます。良質の教材を惜しみなく無料提供するというStanford大学の太っ腹さには驚かされます。
http://www.mmds.org/

Khan Academy と CK-12

Courseraとは別に高校や大学教養学部レベルのものであれば、Khan AcademyとCK-12を覗いてみるのもよいでしょう。Courseraでは説明が不十分な基礎的な知識はこちらの二つのサイトの動画を見て学びました。

カーンアカデミー(Khan Academy)は講義の動画がYouTubeに載せてあります。

Khan Academyのprobability and statistics

CK-12はあまり有名ではありませんが、 高校レベルの講義資料や教科書を無料提供しており、高校レベルで教えてくれるのでとても助かります。

CK-12のFlexBookという教科書は、PDFやepubで読むことができ講義画像へのリンクもついています。

CK-12の統計コース一覧

CK-12の統計学初歩の教科書

CK-12には他のレベルの統計学の教科書もあります。

書籍

小島 寛之 完全独習 統計学入門 ダイヤモンド社

統計学の初歩として数式を多用せず、分かりやすいのでお勧めです。

涌井良幸 多変量解析がわかる 技術評論社

著者は高校の先生なので非常に丁寧に説明してくれるので、多変量解析のことがよく分かるようになります。

Foster Provost 戦略的データサイエンス入門

過学習等、実際にデータ解析を行う際のノウハウが収録されている。

Steven Bird 入門 自然言語処理

自然言語処理の入門書。Pythonでの自然言語処理方法を収録している。

勉強会

TokyoR

東京で開催されている統計プログラミング言語Rの勉強会です。

一人で勉強していると周りが見えなくなることもありますので、一緒に学ぶ人を見つけるのがよいでしょう。他にも多くの勉強会があるので、探してみましょう。

英語の教材が多くなってしまいました。統計学やデータサイエンスを学んでいくと、やはり欧米の科学教育に対する層の厚さをひしひしと感じます。英語という障壁はありますが、その障害を補っても余りある学習効果があると思いますので、是非英語の教材にも挑戦してみてください。

[問題解説12] 男性と女性の殺人被害者数の関係は?

かなり遅くなってしまいましたが、「男性と女性の殺人被害者数の関係は?」の問題解説をします。

今回の問題は、前回の問題「ヒストグラムと散布図を描いてみよう」の発展問題です。

データとプログラムは下記のGitHubリポジトリーにおいてあります。

問題

世界各国の殺人被害者データを用いて女性被害者数から男性被害者数を予測してみましょう。

UNODC(United Nations Office on Drugs and Crime : 国連薬物犯罪事務所)から公開されている世界176ヶ国の殺人被害者の男女別のデータがあります。女性被害者数から男性被害者数を予測してみましょう。

homicide_log.zipをダウンロードしてください。解凍して、homicide_log.csvを読み込んでください。
男性・女性の殺人被害者数のデータは10を底とする対数化してあります。
元データは下記のページから入手しました。
Global Study on Homicide(殺人に関するグローバル調査)

■課題

1.回帰分析を行ってください。

Rの回帰分析関数 lm() を使用して予測式を求める計算をしてください。

2.予測式の値を答えてください。

男性被害者数をM、女性被害者数をFとすると、以下の予測式が成り立ちます。
M = a * F + b
a, b を小数点3桁まで答えてください。解答方法はプログラムの最終行に以下のように記述してください。
# a = x.xxx
# b = y.yyy
3.散布図を作成し、予測式の直線を表示してください。 X軸は女性被害者、Y軸は男性被害者。2Dの散布図を作成してください。表示範囲はX軸、Y軸ともに[-1,3]とする。 その散布図に重ねて、予測式の直線を青色で表示してください。

■解答方法 R言語のプログラムを作成し、上記1~3の課題に答えてください。プログラムファイル名は predict.txt として、アップロードしてください。 散布図は predict.pdf というファイル名でPDFとして出力するプログラムにしてください。

[問題解説12] 男性と女性の殺人被害者数の関係は? の続きを読む

LinuxへのMeCabとRMeCabのインストール

Linuxに日本語形態素解析ツールのMeCabとRMeCabをインストールしてみた

1. Reference

http://mecab.googlecode.com/svn/trunk/mecab/doc/index.html

2. Download

mecab-0.994.tar.gz

mecab-ipadic-2.7.0-20070801.tar.gz

3. Installation

3.1 Excutable Installation

$ tar xvf mecab-0.994.tar.gz

$ cd mecab-0.994

$ ./configure –with-charset=utf8

$ make

$ make check

$ su

# make install

Installed in /usr/local/bin/mecab

3.3 Dictionary Installation

$ tar xvf mecab-ipadic-2.7.0-20070801.tar.gz

$ cd mecab-ipadic-2.7.0-20070801

$ ./configure –with-charset=utf8

$ make

$ su

# make install

Installed in /usr/lcoal/lib/mecab/dic

4. Check

$ mecab

すもももももももものうち

すもも 名詞,一般,*,*,*,*,すもも,スモモ,スモモ

も 助詞,係助詞,*,*,*,*,も,モ,モ

もも 名詞,一般,*,*,*,*,もも,モモ,モモ

も 助詞,係助詞,*,*,*,*,も,モ,モ

もも 名詞,一般,*,*,*,*,もも,モモ,モモ

の 助詞,連体化,*,*,*,*,の,ノ,ノ

うち 名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ

EOS

5. RMeCab from the following URL.

http://web.ias.tokushima-u.ac.jp/linguistik/u64.html

RMeCab_0.996_R_x86_64-unknown-linux-gnu.tar.gz

$ tar xvf RMeCab_0.996_R_x86_64-unknown-linux-gnu.tar.gz

$ sudo R CMD INSTALL RMeCab_0.996_R_x86_64-unknown-linux-gnu.tar.gz

5.1 Fix of lib linkage

$ sudo vi /etc/ld.so.conf.d/lib.conf

Add one line:

/usr/local/lib

$ sudo ldconfig

6. Reference Book

情報循環とお金循環

 吉川弘之氏のシンポジウム講演会をまとめた記事を見つけた。タイトルは「イノベーションと情報循環」。研究などの新規情報(知見)は、「観察型研究者→synthetic型研究者→行動者(実践者)→自然→観察型研究者」という情報伝達サイクルをぐるぐる回ることにより、情報が洗練され、進化して、ついにはイノベーションに到達するというものだ。

 情報は、循環してこそ生きてくるというものだ。このことは、前回にも紹介したツイッターノミクスでも語られているウッフィーの概念と似ていて、情報がユーザーによって使われる事により情報提供者がウッフィーを増やし、情報経済(?)的に自律して、存在できるとということと似ている。

 私は、同じようなことをお金に関しても考えていた。政府が多額の税金をつぎ込んで、経済的弱者にばら撒いたり、必要のない公共事業をしても、結果が出ないのと類似点があるように思う。ただのばら撒きでは、砂漠に水をまいているのと同じで、水は栄養とならず、作物は育たないのだ。少量でもいいから、水(お金)が循環するシステム作りが重要だ。少量の水(お金)が回れば、経済的砂漠化が減少し、経済的に自律して小さな経済圏が生まれるのだと思う。

 これまでの社会経済システムは、政府が国民から税金という水(お金)を吸い上げて、山の頂上から垂れ流して、既得権のある権力者のみが潤い、下層の貧乏人は汚い水を飲んでいると構図になっている。

 安売り競争は、かならずしも良いものではなく、一見消費者にとって良いことのように見えるが、安くて悪いものばかりを消費しているとある種の病気になり、消費者はいつかは購買意欲がなくなって、販売する側も商売が成り立たなくするのだ。ファーストフードはお手軽で安いかもしれないが、そればかり食べ続ければ、病気なったり、味覚異常になってしまう。医療費もかさむので、結局、高くても高品質で安全な食べ物を食べざるを得ないことになる。これは、最近、環境問題で語られている持続可能な生き方と符合する。

 しかしながら、これからの情報経済もマネー経済も循環型にならなければ、成立しないのではないかと思う。というよりも、そうなることを期待している。このことは、まるで仏教の縁の思想が現代に形を変えて現れたようである。つまり、全てのものは何らかのつながりを持って存在しているのである。

イノベーションと情報循環 PDF

ツイッターノミクス – スピード冒険野郎の操縦席