u++の備忘録

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, holds = 5)
可視化

f:id:upura:20180623164646p: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:20180623184450p:plain

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

どんなもの?

グノシーにおけるユーザ行動履歴を用い、政治に関するニュース記事の閲覧傾向が世代によってどのように異なるのかを分析。最初に世代ごとの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.

勾配ブースティング決定木を用いたマーケティング施策の選定

はじめに

今回は、勾配ブースティング決定木(Gradient Boosting Decision Tree, GBDT)を用いて、マーケティング施策を選定する枠組みについて解説します。具体的には、説明変数 X=[x_0, x_1, ..., x_{n-1}]から目的変数 yを予測するモデルを構築し、各説明変数の重要度を算出することで、どの説明変数がマーケティング施策の対象になり得るかを検討します。

例えば Xとして製品のステータス、 yを製品の打ち上げとすると、製品のステータスのうち、どの要素が売上に貢献しているか示唆する情報が得られます。この情報を利用することで「どの要素に注力して売り出すか」「どの要素に注力して改善を目指すか」など、適切な施策の選定につながります。

勾配ブースティング決定木とは

勾配ブースティング決定木は、単純な「決定木」というモデルを拡張した、高精度かつ高速な予測モデルです。

理論の全体像については、以下のブログ記事がとても良くまとまっていました。本記事では、マーケティング施策の選定に活かすという観点で必要な部分のみを概観します。
hiyoko9t.hatenadiary.jp

決定木とは

決定木とは、 Xのとある要素に対して次々と分岐点を見つけていくことで yを分類しようとするモデルです。視覚的にも結果が理解しやすいという利点があります。

f:id:upura:20180526211510p:plain

原田達也: 画像認識 (機械学習プロフェッショナルシリーズ), 講談社, p.149, 2017.

アンサンブルとは

アンサンブルとは、決定木のような単純なモデルを複数組み合わせ、複雑で非線形なモデルを構築する手法です。個々のモデルは単純なため高速に実行できるにもかかわらず、「3人よれば文殊の知恵」ということで高い精度も実現できる枠組みとされています。

代表的な手法としては、以下の二つが挙げられます。

  • バギング
  • ブースティング

決定木を「バギング」で拡張したモデルの一つに「ランダムフォレスト」があります。そして「ブースティング」で拡張したモデルが、勾配ブースティング決定木です。

バギング

バギングは、訓練データから重複を許して何度もデータセットを作成し、それぞれで学習した複数のモデルの結果を利用する手法です。「訓練データから重複を許して何度もデータセットを作成」するのは「ブートストラップ法」と呼ばれています。

f:id:upura:20180526212458p:plain

ブースティング

バギングはデータセットを複数個作り、それぞれ独立で学習させています。そのため、せっかく何回も学習しているのに、過去の間違いを「反省」して次のモデル構築に活かせていません。

ブースティングは、先に学習したモデルで分類に失敗した訓練データを積極的に分類できるよう、後段のモデルを修正していく手法です。逐次的にモデルを作成し、最終的には個々のモデルの精度を用いた重み付き多数決を実施します。

f:id:upura:20180526212951p:plain

ここまで説明したように「勾配ブースティング」は「決定木」という「 Xのとある要素に対して次々と分岐点を見つけていくことで yを分類しようとするモデル」を、過去の失敗を活かすように複数作成していくモデルです。

決定木がベースになっているので、最終的には Xのどの要素での分岐が yの予測に寄与しているか、つまりは各説明変数の重要度を算出できるモデルとなっています。

Pythonでの実装例

最後に以下では、有名なirisのデータセットを用いたPython実装例を示します。 Xを花の情報、 yを花の種類としています。

実装例は、GitHubでも公開しています。
github.com

データの準備

import pandas as pd
import numpy as np

from sklearn.datasets import load_iris
iris_dataset = load_iris()
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(iris_dataset['data'], iris_dataset['target'], test_size=0.1,  random_state=0)

データの可視化

X_trainの次元を削減して、花の種類で色分けしてみます。現実のデータだと、ここまで綺麗に分かれていることは無いかと思います。

%matplotlib inline
import matplotlib.pyplot as plt
from sklearn.manifold import TSNE

X_reduced = TSNE(n_components=2, random_state=0).fit_transform(X_train)
plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=y_train)

f:id:upura:20180526210011p:plain

モデルの構築(クロスバリデーション)

from sklearn.model_selection import GridSearchCV
from sklearn.ensemble import GradientBoostingClassifier

learning_rate = [0.05, 0.1, 0.02]
max_depth = [2, 3, 4]
min_samples_leaf =  [5, 9, 17]
max_features = [1.0, 0.3, 0.1]

hyperparams = {'learning_rate': learning_rate, 'max_depth': max_depth, 'min_samples_leaf': min_samples_leaf, 'max_features': max_features}
gd = GridSearchCV(estimator = GradientBoostingClassifier(n_estimators=30), param_grid = hyperparams, verbose=True, cv=10, scoring = "accuracy", n_jobs=10)
gd.fit(X_train, y_train)

print(gd.best_score_)
print(gd.best_estimator_)

クロスバリデーションの結果、以下の結果が得られました。

0.9703703703703703
GradientBoostingClassifier(criterion='friedman_mse', init=None,
              learning_rate=0.05, loss='deviance', max_depth=4,
              max_features=0.1, max_leaf_nodes=None,
              min_impurity_decrease=0.0, min_impurity_split=None,
              min_samples_leaf=17, min_samples_split=2,
              min_weight_fraction_leaf=0.0, n_estimators=30,
              presort='auto', random_state=None, subsample=1.0, verbose=0,
              warm_start=False)

テストデータに適用

構築した予測モデルをテストデータに適用したところ、全て的中しました。

from sklearn.metrics import confusion_matrix
clf = gd.best_estimator_
clf.fit(X_train, y_train)
confusion_matrix(y_test, clf.predict(X_test))
array([[3, 0, 0],
       [0, 8, 0],
       [0, 0, 4]], dtype=int64)

説明変数の重要度の算出

説明変数の重要度を可視化した結果を、以下に示します。petal lengthが一番重要で、sepal widthが一番重要でないと分かります。

今回の場合は説明変数が四つしかないこともあり「だから何?」という印象も受けますが、説明変数が膨大な場合などでも重要な要素を機械的に選定できる点で価値がある手法です。

feature_importance = clf.feature_importances_
feature_importance = 100.0 * (feature_importance / feature_importance.max())

label = iris_dataset.feature_names

plt.xlabel('feature importance')
plt.barh(label,feature_importance, tick_label=label, align="center")

f:id:upura:20180526210547p:plain