u++の備忘録

【書評】コンピュータサイエンス探偵の事件簿 ―データ構造と探索アルゴリズムが導く真実

https://www.amazon.co.jp/dp/4873118433/

あらすじ(「BOOK」データベースより)

警察署で発生した書類盗難事件の解明を依頼された私立探偵フランク・ランタイム。さまざまなデータ構造と探索アルゴリズムを駆使して、事件の謎に迫る。事件を追ううちに、その背後にある国家転覆を謀る魔術師たちの存在に気づくフランク。彼は魔術師たちの陰謀を阻止し国の平和を守ることができるのか―。探偵もののストーリーにのせて、コンピュータサイエンスの基本、「探索アルゴリズムとデータ構造」を紹介。取り上げる探索アルゴリズムは、線形探索、二分探索、幅優先探索深さ優先探索、並列探索、反復深化、最良優先探索、そしてデータ構造は、配列、スタック、キュー、二分探索木など。推理小説を楽しみながらコンピュータサイエンスの基本を身に付けることができます。

書籍の概要

2016年8月に発売された下記の本の翻訳版。カスタマーレビューは星5が5件、星1が1件と、件数が少ないながらも高評価を受けています。

https://www.amazon.co.jp/CS-Detective-Algorithmic-Conspiracy-Computation/dp/1593277490/

探偵もののストーリーを楽しみながら、コンピュータサイエンスの基本「探索アルゴリズムとデータ構造」の概要に触れられる本書。私立探偵フランク・ランタイムが警察署で発生した事件を、探索アルゴリズムを駆使して解明していきます。

扱う内容を抜粋すると下記の通りで、基礎的な部分が網羅されていると思います。

アルゴリズム
データ構造
  • 配列
  • スタック
  • キュー
  • 二分探索木

所感

章ごとに、ストーリー部分と講義部分が別立てになっているのが好印象でした。ストーリーの中で触れられたトピックについて、改めて章の末尾で解説をする構成になっています。もちろん講義部分は読み飛ばしてもストーリーの理解には影響がないです。

(僕は最後の方、ストーリーの展開が気になって講義部分をいくつか読み飛ばしてしまいました笑)

最後に、章の見出しをいくつか上げておきます。この見出しを見て心躍る方には、ぜひ一読をオススメしたいです。

  • 3. 無法者たちの牧場にある配列とインデックス
  • 9. 探索を進めるためのバックトラック
  • 11. 朽ち果てた牢獄での深さ優先探索
  • 12. カフェテリアのスタックとキュー
  • 27. 政略と学会におけるヒープ

KaggleのWinner solutionにもなった「K近傍を用いた特徴量抽出」のPython実装

今回は、KaggleのWinner solutionにもなった「K近傍を用いた特徴量抽出」を紹介します。

Rでの実装は公開されていますが、Pythonでの実装は確認できなかったので、自前のPython実装も公開しています。

github.com

アルゴリズムの概要

近傍数を k、分類するクラス数を cとした場合に、アルゴリズム k \times c個の特徴量を生成します。生成される特徴量は下記のように、観測値と各クラス内の k最近傍点との間の距離から計算されます。

  1. とあるクラスに属する訓練データの中の第1近傍までの距離を1つ目の特徴量とする
  2. とあるクラスに属する訓練データの中の第2近傍までの距離の和を2つ目の特徴量とする
  3. とあるクラスに属する訓練データの中の第3近傍までの距離の和を3つ目の特徴量とする
  4. 以上を kに関して繰り返す

上記の手順を全てのクラスについて繰り返すことで、 k \times c個の特徴量が生成されます。実際は過学習を避けるため、n-foldで分割して特徴量を生成しています。

Pythonでの例

Notebook version can be seen [here](https://github.com/upura/knnFeat/blob/master/demo.ipynb).

可視化のためのパッケージ読み込み
import numpy as np
%matplotlib inline
import matplotlib.pyplot as plt
サンプルデータの生成
x0 = np.random.rand(500) - 0.5
x1 = np.random.rand(500) - 0.5
X = np.array(list(zip(x0, x1)))
y = np.array([1 if i0 * i1 > 0 else 0 for (i0, i1)  in list(zip(x0, x1))])
可視化

f:id:upura:20180623164523p:plain

K近傍を用いた特徴量抽出
from knnFeat import knnExtract
newX = knnExtract(X, y, k = 1, folds = 5)
可視化

f:id:upura:20180624233211p:plain

ほぼ線形分離可能な特徴量が抽出できています。

iris での例

定番のiris データセットでも、うまく分離できています(irisは3クラス分類なので特徴は3つ得られていますが、うち2つだけでプロットしています)。

from sklearn import datasets
iris = datasets.load_iris()
y = iris.target
X = iris.data

f:id:upura:20180623184422p:plain
f:id:upura:20180624233235p:plain

追記20180624

実装の修正

初回公開時、n-foldで分割においてX_testではなくX_trainから特徴量を抽出する実装となっていました。ご指摘いただき、ありがとうございます。

【論文メモ】世代による政治ニュース記事の閲覧傾向の違いの分析

どんなもの?

グノシーにおけるユーザ行動履歴を用い、政治に関するニュース記事の閲覧傾向が世代によってどのように異なるのかを分析。最初に世代ごとのPVランキングを作成し、後に順位の差分が大きい記事を取り上げることで、若い世代は政策に中高年は政局に関心があるといった世代ごとの傾向が示唆された。

論文リンク

https://confit.atlas.jp/guide/event-img/jsai2018/3O2-OS-1b-04/public/pdf?type=in

著者/所属機関

関 喜史1 (1. 株式会社Gunosy)

媒体

2018年度人工知能学会全国大会

投稿日付

先行研究と比べてどこがすごい?

アンケートを用いたような調査は存在するものの,若年層の政治的関心がどのように他の世代と異なるのかについて,実際の行動に基づいた調査はほとんど行われていない

技術や手法のキモはどこ?

どうやって有効だと検証した?

議論はある?

今回の分析はあくまでグノシー内の行動であり,一般化できるものではない.

次に読むべき論文は?

所感

順位の単なる差分ではなく、TF-IDF的なアプローチをしても面白いのではと思った。

論文管理GitHubリポジトリ

github.com

matplotlib.pyplot.histとseaborn.distplotの違い

seaborn.distplotの公式ドキュメントには「matplotlib.pyplot.histを使っている」と記載がある。

This function combines the matplotlib hist function (with automatic calculation of a good default bin size) with the seaborn kdeplot() and rugplot() functions.

seaborn.distplot — seaborn 0.8.1 documentation

実際にseabornのソースコードを追うと、matplotlib.pyplot.histのパラメータで“normed=True”として実行している。
github.com

matplotlib.pyplot.histのデフォルト設定は“normed=None”なので、その部分だけmatplotlib.pyplot.histとseaborn.distplotで違いが生じる。
matplotlib.pyplot.hist — Matplotlib 2.2.2 documentation

【書籍メモ】実践Node.jsプログラミング|第1章 Node.js に、ようこそ!

www.shoeisha.co.jp

この章で扱う概念

  • サーバサイド開発に、なぜJavaScriptが重要なのか
  • ブラウザはJavaScriptを使って、どのようにI/Oを処理するのか
  • サーバ上のNodeは、どのようにI/Oを処理するのか
  • DIRTyアプリケーションとは何を提供するのか。どうしてそれがNodeに適しているのか
  • 基礎的なNodeプログラムのサンプル

サーバサイド開発に、なぜJavaScriptが重要なのか

  • サーバサイドもJavaScriptを用いることで、開発者はただ一つの言語でWebアプリケーションが書ける。クライアント開発とサーバ開発の間で発生するコンテクストの切り替えが削減される。
  • JavaScriptはさまざまなNoSQLデータベースで使われている言語なので、それらのインターフェースとの相性が良い。

など

ブラウザはJavaScriptを使って、どのようにI/Oを処理するのか

  • イベント駆動で、入出力でブロックしない(非同期I/Oを使う)
  • ほかに対話処理があっても、そのページで別の要求が発生しても、それに応答できる
  • この仕組みによって、クライアントに素早く反応し、そのページにおける大量のインタラクションを処理できる

サーバ上のNodeは、どのようにI/Oを処理するのか

  • ブラウザの場合と似ている
  • Nodeではほとんど常に入出力がメインのイベントループの外側で実行されるので、サーバは高い効率と応答性を保つことができる

DIRTyアプリケーションとは何を提供するのか。どうしてそれがNodeに適しているのか

  • DIRT = Data-Intensive Real-Time(大量のデータを扱うリアルタイムな)
  • DIRTyアプリケーションには、同時に利用する数多くのユーザに対して、ほとんど即時に応答できる性能が必要だから

基礎的なNodeプログラムのサンプル

var fs = require(‘fs’);
fs.readFile(‘.resource.json’, function (err, data) {
    console.log(‘data’);
})

まとめ

  • JavaScriptの上に構築されている
  • イベント駆動で非同期
  • データ量の多いリアルタイムアプリケーションのために構築された

"Uncaught SyntaxError: Unexpected token u in JSON at position 0"の対処法

Uncaught SyntaxError: Unexpected token u in JSON at position 0
      at JSON.parse (<anonymous>)

環境

Node.js (v8.10.0)

対処法

上記のエラーが出た時は、どこかでundefinedのものをJSON.parse()してしまっている。丁寧に処理を追いかけ、原因発生箇所を見つける。

【Python, networkx】max_weight_matchingの裏側

はじめに

以下の記事で用いた "max_weight_matching()" について、ザッとまとめた。
upura.hatenablog.com

max_weight_matching() について

どういう関数?

  • どのノードも一度以上エッジの端点にならないようなマッチングのパターンの中で、全てのエッジの重みの合計が最も大きい組み合わせを返す関数
  • 計算量は  O(number of nodes ** 3)

アルゴリズムの詳細

Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.
http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf

bipartite.maximum_matching() について

どういう関数?

  • 二部グラフ向けの似たような関数に見えるが、こちらはエッジの数が最大になる組み合わせを返す
  • Wikiには、以下のような記述がある*1

A maximum matching (also known as maximum-cardinality matching[1]) is a matching that contains the largest possible number of edges.

グラフ理論のマッチングアルゴリズムの紹介スライド

以下の資料がよくまとまっていた

*1:Matching (graph theory) - Wikipedia, 2018.06.01 available.