LINEbotのログインURLを出す

今回はみんな大好きPythonを用いてLINEのログインURLを出してみたいと思います

必要なもの

・Python3.6実行環境

準備

ログインURLを出すために、まず「linepy」というモジュールをインストールします。
pipが使える方は[pip install linepy]でインストールできます。

https://github.com/fadhiilrachman/li

実行してみる

モジュールをインストールし終わったら実行をしてみましょう

test.py

from linepy import*
cl = LINE()

実行結果

ログインURLが出ましたね。

ログインについて

LINEbotは自己責任でやりましょう。
アカウントが規制になっても自己責任です。

著者について

著者は学生です。ぜひTwitterフォローしてくださいね。

https://twitter.com/KMchan_xyz

はじめに

前回の記事でQiitaの全記事を取得したので、次は以下の記事を参考に前処理を行っていきます。

自然言語処理における前処理の種類とその威力

前処理をする

記事の抜き出し

Qiita APIで取得できる記事データには、rendered_bodyにHTML形式、bodyにマークダウン形式の記事情報が含まれています。

今回は、パースのしやすいHTML形式の方を使用します。

json_to_text.py

# --------------------------------------------------
# Qiita APIから取得したデータの記事部分を抜き出しファイル出力
# --------------------------------------------------
import json
from datetime import datetime, timedelta
from bs4 import BeautifulSoup
import os

start = datetime.strptime(os.getenv('START_DATE'), '%Y-%m-%d')  # 開始日を設定
end = datetime.strptime(os.getenv('END_DATE'), '%Y-%m-%d')  # 終了日を設定

for i in range((end - start).days):
    today = (start + timedelta(i)).strftime('%Y-%m-%d')
    print(today)

    # データ読み込み
    with open('data/qiita_' + today + '.json') as json_data:
        articles = json.load(json_data)

        # 記事の集約
        for article in articles:
            soup = BeautifulSoup(article['rendered_body'], 'html.parser')
            # 本文の抜き出し
            sentences = soup.find_all('p')
            for sentence in sentences:
                text = sentence.text + '\n'
                # ファイル書き込み
                with open('data/qiita.txt', 'a') as f:
                    f.write(text)

このプログラムを実行すると、dataフォルダの中に、HTMLからpタグ（段落）部分のみを抽出したqiita.txtが生成されます。

形態素解析

次に形態素解析を行います。日本語は英語のように単語同士が分かれていないので、単語ごとに分割する必要があるためです。

形態素解析器にはMeCabを使用しています。
注）MeCabは別途インストールが必要です。NEologd辞書と一緒に入れてしまうのが楽でオススメです。

text_to_wakati.py

# --------------------------------------------------
# テキストファイルを分かち書き
# --------------------------------------------------
import os
import MeCab


# データ読み込み
with open('data/qiita.txt') as text_data:
    tagger = MeCab.Tagger(
        '-Owakati -b ' + os.getenv('MECAB_BUFFER') + ' -d ' + os.getenv('MECAB_DIC_PATH'))
    line = text_data.readline()
    while line:
        # 分かち書き
        result = tagger.parse(line)
        line = text_data.readline()
        if result != None:
            # ファイル書き込み
            with open('data/qiita_wakati.txt', 'a') as f:
                f.write(result)

単語の正規化

最後に単語の正規化を行います。
今回は、以下の処理のみ行いました。

• 英字大文字を全て小文字に
• 日本語の半角を全角に
• 一部の記号を統一
• 数字を全て0に

数字を全て0にしてしまうのは、今回に限ってはやめた方が良いかもしれません。なぜなら、技術用語における数字は結構重要なケースも多いと考えられるからです（バージョンなど）。

preprocessing.py

# --------------------------------------------------
# 分かち書きされたテキストの前処理
# --------------------------------------------------
import os
import re
import jaconv


# データ読み込み
with open('data/qiita_wakati.txt') as wakati_data:
    data = wakati_data.read()
    # 大文字→小文字
    data = data.lower()
    # 半角→全角
    data = jaconv.h2z(data)
    # 記号（-など）の正規化
    data = jaconv.normalize(data)
    # 数字の置き換え
    data = re.sub(r'[0-9]+', '0', data)

    # ファイル書き込み
    with open('data/qiita_corpus.txt', 'w') as f:
        f.write(data)

おわりに

次回→Qiitaコーパスで単語埋め込みの様子をみてみる

この記事は古川研究室 Workout_calendar 12日目の記事です．

本記事は古川研究室の学生が学習の一環として書いたものです．内容が曖昧であったり表現が多少異なったりする場合があります．

概要

はじめに，私は今回のイベントで3本記事を出します．一貫して回帰がテーマになっていますが，それぞれ違うパラメータ推定方法でアプローチしているのが特徴です．具体的に，第1回では最尤推定，第2回ではMAP推定，第3回ではベイズ推定を用いて回帰を行います．もし，興味があれば本記事だけでなく第2回や第3回も見て頂けると嬉しいです．

本記事の内容をざっくり言うと，最尤推定を使用して回帰モデルのパラメータ$\mathbf w,\beta$を推定し，新規入力に対する出力の予測分布を求めたり，最尤推定で得られる結果が最小二乗法と等価になっていることを確認します．

この記事で行ったことをリスト化すると以下のようになっています．

「記事内で行ったこと」

• (理論)最尤推定を用いたモデルのパラメータと予測分布の導出
• (実装)最尤推定を用いた回帰のスクラッチ実装

まずは，簡単に用語などの説明を行いたいと思います

最尤推定，MAP推定，ベイズ推定について

データセット$X$が与えられている状況で，モデルのパラメータ$\mathbf{w}$を推定する統計的な手法に最尤推定，MAP推定，ベイズ推定があります．これらの手法は，最尤推定とMAP推定がモデルのパラメータ$\mathbf{w}$に関して，最も「良い」答えをただ一つ求める点推定（それ以外の他の可能性は全て切り捨てる）なのに対して，ベイズ推定はパラメータ$\mathbf{w}$に関して「良い」だけでなく，「まあまあ良い」答えなどあらゆる答え（可能性）を含んだ分布を推定できることが大きな違いです．ここで，ベイズの定理は次のような式になっています．

\begin{eqnarray}
p(\mathbf{w}|X)=\frac{p(X|\mathbf{w})p(\mathbf{w})}{p(X)}
\end{eqnarray}

以下は，この定理を使ったパラメータ推定方法です．

①最尤推定（事前知識なしで尤度$p(X|\mathbf{w})$を最大にするパラメータを選ぶ）

\begin{eqnarray}
\mathbf{w}_{ML}=\underset{w}{\arg \max \,}p(X|\mathbf{w})
\end{eqnarray}

②MAP推定（事前知識ありで事後分布$p(\mathbf{w}|X)$を最大にするパラメータを選ぶ）

\begin{eqnarray}
\mathbf{w}_{MAP}=\underset{w}{\arg \max \,}p(X|\mathbf{w})p(\mathbf{w})
\end{eqnarray}

③ベイズ推定（パラメータ$\mathbf{w}$の分布を推定する）

\begin{eqnarray}
p(\mathbf{w}|X)=\frac{p(X|\mathbf{w})p(\mathbf{w})}{p(X)}
\end{eqnarray}

尤度とは

本記事では，データセット$X$が与えられているとき，ベイズの定理から次の式が得られます．

\begin{eqnarray}
p(\mathbf{w}|X,\beta)=\frac{p(X|\mathbf{w},\beta)p(\mathbf{w})}{p(X)}
\end{eqnarray}

$\mathbf w$と$\mathbf \beta$はそれぞれパラメータです（詳細は後で出てきます）．このとき，$p(X|\mathbf w,\beta)$を尤度，$p(\mathbf w)$を事前分布，$p(X)$をエビデンス，$p(\mathbf w|X,\beta)$を事後分布といいます．ここで，$X$は与えられているので確率変数ではなく，$\mathbf w,\beta$は確率変数です．

尤度$p(X|\mathbf w,\beta)$は，既に手に入ったデータセット$X$からパラメータ$\mathbf w,\beta$を見て，$\mathbf w,\beta$が何か一意に決まったときの$X$に対する尤もらしさを表します．ここで，尤度は分布全てを足しても1にはならないため，確率ではありません．そのため尤度は，尤度関数とも呼ばれます．

もし文章で分からなければこちらの記事をご覧ください．視覚的に説明されていて，文章でイメージするよりも分かりやすいのでとてもおすすめです．

最尤推定による回帰のタスク設定

与えられているもの
入力$\mathbf x=(x_1,...,x_N), x\in\mathbf R$と出力$\mathbf y=(y_1,...,y_N), y\in\mathbf R$のデータセット

仮定
・$\mathbf x$と$\mathbf y$のデータセットは，独立同分布(i.i.d.)に従うとします．

・$y_i,f,\epsilon$を次のように仮定します（$\beta$はガウスノイズの精度です）．

\begin{eqnarray}
y_i&=&f(x_i;\mathbf w)+\epsilon_i
\end{eqnarray}

\begin{eqnarray}
f(x_i;\mathbf w)=\mathbf{w}^T\boldsymbol{\phi}(x_i)
\end{eqnarray}

\begin{eqnarray}
\epsilon_i&\sim& N(0,\beta^{-1})
\end{eqnarray}

$\;\;\;$ここで，基底関数$\boldsymbol{\phi}(x)$とパラメータ$\mathbf{w}$は$D$個あるので次のようになります．

\begin{eqnarray}
\boldsymbol{\phi}(x_i)&=&(\phi_1(x_i),...,\phi_{D}(x_i))^T
\end{eqnarray}

\begin{eqnarray}
\mathbf{w}&=&(w_1,...,w_{D})^T
\end{eqnarray}

タスク

尤度が最大となるパラメータ$\mathbf w_{ML},\beta_{ML}$を推定する．

\begin{eqnarray}
\mathbf w_{ML},\;\beta_{ML}
&=&\underset{\mathbf{w},\;\beta}{\arg \max\,}\left(p(\mathbf y|\mathbf x,\mathbf{w},\beta)\right)\\\
&=&\underset{\mathbf{w},\;\beta}{\arg \max\,}\left(\prod_{i=1}^{N}p(y_i|x_i,\mathbf{w},\beta)\right)\
\end{eqnarray}

推定した$\mathbf w_{ML},\beta_{ML}$から，新規入力$x^*$に対する出力$y^{*}$の予測分布$p(y^*|x^*,\mathbf
w_{ML},\beta_{ML})$を求めることができます．

解析解の導出

1. 対数尤度関数を最大化するパラメータ$\mathbf w_{ML},\mathbf{\beta}_{ML}$を求める

   1-1 尤度の式を変形して対数尤度関数を求める
   1-2 対数尤度関数を偏微分して，極値を求める

2. 推定したパラメータ$\mathbf w_{ML},\mathbf \beta_{ML}$から，新規入力$x^*$に対する出力$y^*$の予測分布を求める

1. 対数尤度関数を最大化するパラメータを求める

1-1 尤度の式を変形して対数尤度関数を求める

はじめに，観測データが$(x_i,y_i)$，出力が$y_i=f(x_i;\mathbf w)+\epsilon_i$とすると，尤度$p\left(y_i|x_i,\mathbf w,\beta\right)$を次のように仮定します．

\begin{eqnarray}
p\left(y_i|x_i,\mathbf{w},\beta\right)
&=&N\left(y_i|f(x_i;\mathbf w),\beta^{^-1}\right)\\
&=&\sqrt\frac{\beta}{{2\pi}}\exp\left(-\frac{\beta}{2}(y_i-f(x_i;\mathbf w))^{2}\right)\\
&=&\sqrt\frac{\beta}{{2\pi}}\exp\left(-\frac{\beta}{2}\left(y_i-\mathbf{w}^{T}\boldsymbol{\phi}\left(x_i\right)\right)^{2}\right)
\end{eqnarray}

次に，データセット全体の尤度を求めると，独立同分布（i.i.d.）に従うと仮定しているので次のようになります．

\begin{eqnarray}
\prod_{i=1}^{N} p\left(y_i|x_i,\mathbf{w},\beta\right)=p(y_1|x_1,\mathbf{w},\beta)\times \cdots \times p(y_N|x_N,\mathbf{w},\beta)
\end{eqnarray}

更に，対数尤度は次のように求められます．

\begin{eqnarray}
\ln \left(\prod_{i=1}^{N} p\left(y_i|x_i,\mathbf{w},\beta\right)\right)
&=&\sum_{i=1}^{N}\ln p(y_i|x_i,\mathbf{w},\beta)\\
&=&\sum_{i=1}^{N} \{ \frac{1}{2}\ln \frac{\beta}{2\pi}-\frac{\beta}{2}(y_i-\mathbf{w}^{T}\boldsymbol{\phi}(x_i))^{2} \} \\
&=&-\frac{\beta}{2}\sum_{i=1}^{N}(y_i-\mathbf{w}^{T}\boldsymbol{\phi}(x_i))^{2}+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}\\
&=&-\frac{\beta}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}
\end{eqnarray}

ここで，$N$，$D$はデータ数と基底関数の数を表しており，$\mathbf{y},\mathbf{w},\Phi$はそれぞれ次のようになっています．

\begin{eqnarray}
\mathbf{y}&=&\left(y_1,...,y_N\right)^{T}\\
\mathbf{w}&=&(w_1,...,w_D)^{T}\\
\Phi &=&
\left(
\begin{array}{cccc}
\phi_{1}(x_1) & \cdots & \phi_{D}(x_1)\\
\vdots & \ddots & \vdots\\ 
\phi_{1}(x_N) & \cdots & \phi_{D}(x_N)\\
\end{array}
\right)\\
\end{eqnarray}

求めた対数尤度はパラメータ$\mathbf{w},\beta$による関数とみなせるので，対数尤度関数$L(\mathbf{w},\beta)$とおくと次のようになります．

\begin{eqnarray}
L(\mathbf{w},\beta)&=&-\frac{\beta}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}\\
&=&-\beta\frac{1}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}\\
&=&-\beta E(\mathbf{w})+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}
\end{eqnarray}

ここで，$E(\mathbf{w})=\frac{1}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}$です．

この式のパラメータ$\mathbf{w}$について注目すると，第二項と第三項は定数であり，第一項は$\beta$（スカラー）倍された目的変数とモデルの出力の二乗誤差$E(\mathbf{w})$になっていることが分かります．つまり，パラメータ$\mathbf{w}$に関して尤度関数を最大化するということは二乗誤差を最小にするという問題と等価であることを示しています．このことから，回帰における最小二乗法を解くという行為は最尤推定という統計的手法によって妥当性が裏付けられた解き方であるということが分かります．ただし，ガウスノイズの仮定の下でのみ成り立つことに注意しなければいけません．

1-2 対数尤度関数を偏微分して，極値を求める

① $\mathbf{w}$で偏微分して，極値を求める
次に，先ほど導出した対数尤度関数$L(\mathbf{w},\beta)$を$\mathbf{w}$で偏微分し，$0$となる極値$\mathbf{w}_{ML}$を求めます．ここで，パラメータ$\mathbf{w}$に関係ないとみなせる定数項は全て$const$にまとめています．

\begin{eqnarray}
\frac{\partial L(\mathbf{w},\beta)}{\partial \mathbf{w}}
&=&\frac{\partial}{\partial \mathbf{w}}\{-\frac{\beta}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+const\}\\
&=&\frac{\partial}{\partial \mathbf{w}}\{-\frac{\beta}{2}(\mathbf{y}-\Phi\mathbf{w})^{T}(\mathbf{y}-\Phi\mathbf{w})+const\}\\
&=&\frac{\partial}{\partial \mathbf{w}}\left\{-\frac{\beta}{2}\left(\mathbf{y}^T\mathbf{y}-\mathbf{y}^T\Phi\mathbf{w}-\mathbf{w}^T\Phi^T\mathbf{y}+\mathbf{w}^T\Phi^T\Phi\mathbf{w}\right)+const\right\}\\
&=&\frac{\partial}{\partial \mathbf{w}}\left\{-\frac{\beta}{2}\left(\mathbf{y}^T\mathbf{y}-\mathbf{w}^T(\mathbf{y}^T\Phi)^T-\mathbf{w}^T\Phi^T\mathbf{y}+\mathbf{w}^T\Phi^T\Phi\mathbf{w}\right)+const\right\}\\
&=&\frac{\partial}{\partial \mathbf{w}}\left\{-\frac{\beta}{2}\left(\mathbf{y}^T\mathbf{y}-2\mathbf{w}^T\Phi^T\mathbf{y}+\mathbf{w}^T\Phi^T\Phi\mathbf{w}\right)+const\right\}\\
&=&-\frac{\beta}{2}(0-2\Phi^T\mathbf{y}+2\Phi^T\Phi\mathbf{w})+0\\
&=&0
\end{eqnarray}

ここで，上から3行目第2項に出てくる$\mathbf{y}^T\Phi\mathbf{w}$は，$\mathbf{a},\mathbf{b}$がベクトルの時に成り立つ$\mathbf{a}^T\mathbf{b}=\mathbf{b}^T\mathbf{a}$の関係を利用して，$\mathbf{a}^T=\mathbf{y}^T\Phi$，$\mathbf{b}=\mathbf{w}$と置いて式変形を行いました．

従って，式を整理すると次の式が得られます．

\begin{eqnarray}
\Phi^{T}\Phi\mathbf{w}=\Phi^{T}\mathbf{y}
\end{eqnarray}

よって，最尤推定で求められた$\mathbf{w}_{ML}$は，

\begin{eqnarray}
\mathbf{w}_{ML}
&=&(\Phi^{T}\Phi)^{-1}\Phi^T\mathbf{y}\\
&=&\Phi^{\dagger}\mathbf{y}
\end{eqnarray}

となります．この式は，最小二乗法の正規方程式として知られています．また，$N×D$行列$\Phi^{\dagger}$はムーア＝ペンローズの一般化逆行列もしくは疑似逆行列と呼ばれ，長方行列に対しての逆行列みたいなものと考えることができます．余談ですが，もし仮に$N=D$で$\Phi$が正則であるとすると，$(AB)^{-1}=B^{-1}A^{-1}$より，

\begin{eqnarray}
\Phi^{\dagger}
&=&(\Phi^{T}\Phi)^{-1}\Phi^T\\
&=&\Phi^{-1}(\Phi^T)^{-1}\Phi^T\\
&=&\Phi^{-1}
\end{eqnarray}

となって，$\Phi^{\dagger}=\Phi^{-1}$が成り立つことが分かります．

② $\beta$で偏微分して，極値を求める

次に，$\beta_{ML}$を求めます．ここで，対数尤度関数$L(\mathbf{w},\beta)$は以下の式となっており，

\begin{eqnarray}
L(\mathbf{w},\beta)
=-\frac{\beta}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+\frac{N}{2}\ln \beta-\frac{N}{2}\ln {2\pi}
\end{eqnarray}

この式を$\beta$について偏微分し，$0$となる極値を求めます．

\begin{eqnarray}
\frac{\partial L\left(\mathbf{w},\beta\right)}{\partial \beta}
&=&-\frac{1}{2}\|\mathbf{y}-\Phi\mathbf{w}\|^{2}+\frac{N}{2\beta_{ML}}+0
&=&0
\end{eqnarray}

得られた式を$\beta_{ML}$について整理すると次のようになります．

\begin{eqnarray}
\frac{1}{\beta_{ML}}
=\frac{1}{N}\sum_{i=1}^{N}(y_i-\mathbf{w}^{T}\boldsymbol{\phi}(x_i))^{2}
\end{eqnarray}

この式は，最尤推定で求めたガウスノイズの分散（$\beta_{ML}^{-1}$）は平均二乗誤差の値と等しくなるということを示しています．

2. 推定したパラメータから，新規入力に対する出力の予測分布を求める

推定した$\mathbf w_{ML},\beta_{ML}$から，予測分布$p(y^{*}|x^{*},\mathbf w_{ML},\beta_{ML})$は次のようになります．

\begin{eqnarray}
p(y^{*}|x^{*},\mathbf{w}_{ML},\beta_{ML})
&=&N\left(y^{*}|f(x^{*};\mathbf w_{ML}),\beta_{ML}^{-1}\right)\\
&=&N\left(y^{*}|\mathbf{w}_{ML}^{T}\boldsymbol{\phi}(x^{*}),\beta_{ML}^{-1}\right)
\end{eqnarray}

最尤推定を用いた回帰の実装

導出した式から，スクラッチで実装を行いました

# 最尤推定
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
np.set_printoptions(precision=3)

def Phi(X):
    # X      : [[x0],[x1],...]
    # phi    : e.g. [1, x, x**2]
    # return : [[phi_1(X),...,phi_n(X)]]
    result = np.array([[1, x[0], x[0]**2, x[0]**3] for x in X])
    return result

N = 10
beta = 0.3
np.random.seed(1111)
x = np.linspace(-1,1,N)
t = np.sin(np.pi*np.linspace(-1.5,1.5,100))
y = np.sin(np.pi*x) + np.random.normal(0,beta,N)
x_test = np.linspace(-1.5,1.5,100)
y_test = np.sin(np.pi*x_test) + np.random.normal(0,beta,len(x_test))

# 学習
x = np.array([[i] for i in x])
x_test = np.array([[i] for i in x_test])
y = np.array([[i] for i in y])

w_ML = np.dot(np.dot(np.linalg.inv(np.dot(Phi(x).T, Phi(x))), Phi(x).T), y.ravel())
w_ML = np.array([[w] for w in w_ML])

# テスト
predict = np.dot(w_ML.T, Phi(x_test).T).ravel()
variance_ML = np.sum(np.square(y-np.dot(Phi(x), w_ML))) / N
sigma = np.sqrt(variance_ML)

fig, ax = plt.subplots(1,2,figsize=(12,4))
ax[0].plot(np.linspace(-1.5,1.5,len(t)),t,label='sin',color='b')
ax[0].plot(x_test.ravel(), predict.ravel(),label='predict curve',color='r')
ax[0].scatter(x.ravel(), y, label='train_data',color='b')
ax[1].fill_between(x_test.ravel(), predict+sigma*3, predict-sigma*3, alpha=0.1, label='3sigma')
ax[1].fill_between(x_test.ravel(), predict+sigma, predict-sigma, alpha=0.1, label='sigma')
ax[1].plot(x_test.ravel(), predict.ravel(),label='predict curve',color='r')
ax[1].scatter(x_test.ravel()[::5],y_test[::5], label='test_data',color='0.1')
ax[0].set_title('train')
ax[1].set_title('test')
ax[0].set_xlim(-1.5,1.5)
ax[0].set_ylim(-1.5,1.5)
ax[1].set_xlim(-1.5,1.5)
ax[1].set_ylim(-1.5,1.5)
ax[0].legend(loc='upper right',fontsize=9)
ax[1].legend(loc='upper right',fontsize=9)
plt.show()

for i, w in enumerate(w_ML.ravel()):
    print('w{}: {:.2f}'.format(i,w),end=' ')

実験結果　3次多項式のとき

sin関数からサンプリングした10点の学習データに対して，3次多項式のモデルを使って回帰を行った結果がこれです．$x$の定義域が-1.5から1.5付近までは，学習データもテストデータもある程度上手くできてることが分かります．また，パラメータ$\mathbf{w}$は，あまり大きな値になっていない（過学習していない）ことが分かります．分散(sigma）については，ある程度広がりを持っていることが右図から分かります．

実験結果　9次多項式のとき

同じ条件で，9次多項式のモデルで回帰を行った結果がこれです．左図を見ると全ての学習データを通る曲線になっていることが分かりますが，一方で右図のテストデータには全然上手くいっていないことが分かります．パラメータ$\mathbf{w}$の値を見てみると3次多項式の結果と比べてかなり大きな値になっていることが分かり，このことから学習データに対して過学習していると考えられます．また，全ての学習データを通る曲線になっているので平均二乗誤差が$0$となり，分散（sigma）がないことが右図から分かります．

感想

数式の導出とスクラッチによる実装を行ったことで，最尤推定を使った回帰のイメージがつかめたと思います．

参考文献

[1] パターン認識と機械学習（上）　C.M. ビショップ

[2] 【統計学】尤度って何？をグラフィカルに説明してみる。

今回はコレを紹介しながら写経します。

データについて

試用するデータは保険料のデータ(と思われる)。

データには住所や年齢、喫煙、子供の数などと、保険料が入っている。

このデータをEDAで色々な角度から見ていってモデルの変数選択をして、
最終的に回帰で保険料を算出しようという試み。

早速はじめます

import numpy as np 
import pandas as pd 
import os
import matplotlib.pyplot as pl
import seaborn as sns
import warnings
warnings.filterwarnings('ignore')
data = pd.read_csv('C:/・・・/insurance.csv')

いつもの

data.head()
data.isnull().sum()

    age     sex     bmi     children    smoker  region  charges
0   19  female  27.900  0   yes     southwest   16884.92400
1   18  male    33.770  1   no  southeast   1725.55230
2   28  male    33.000  3   no  southeast   4449.46200
3   33  male    22.705  0   no  northwest   21984.47061
4   32  male    28.880  0   no  northwest   3866.85520

age         0
sex         0
bmi         0
children    0
smoker      0
region      0
charges     0
dtype: int64

データにNaNが含まれてない日はついている日です。
カテゴリカルデータをエンコードして、変数の相関を計算します。

from sklearn.preprocessing import LabelEncoder
#sex
le = LabelEncoder()
le.fit(data.sex.drop_duplicates()) 
data.sex = le.transform(data.sex)
# smoker or not
le.fit(data.smoker.drop_duplicates()) 
data.smoker = le.transform(data.smoker)
#region
le.fit(data.region.drop_duplicates()) 
data.region = le.transform(data.region)

カテゴリカルデータにフィルターをかけて重複しているものをファクターに変換しています。
regionのような変数にはonehotencorderなどを使用すべきなのでしょうが今回は怠慢にもlabelencorderで行くようです。

data.corr()['charges'].sort_values()

region     -0.006208
sex         0.057292
children    0.067998
bmi         0.198341
age         0.299008
smoker      0.787251
charges     1.000000

f, ax = pl.subplots(figsize=(10, 8))
corr = data.corr()
sns.heatmap(corr, mask=np.zeros_like(corr, dtype=np.bool), cmap=sns.diverging_palette(240,10,as_cmap=True),
            square=True, ax=ax)

相関を計算した結果、喫煙者であることと、保険料に正の相関がありそうです。
筆者はbmiと相関があると想定していたようです。

費用の分布を確認します。

from bokeh.io import output_notebook, show
from bokeh.plotting import figure
output_notebook()
import scipy.special
from bokeh.layouts import gridplot
from bokeh.plotting import figure, show, output_file
p = figure(title="Distribution of charges",tools="save",background_fill_color="#E8DDCB")
hist, edges = np.histogram(data.charges)
p.quad(top=hist, bottom=0, left=edges[:-1], right=edges[1:],fill_color="#036564", line_color="#033649")
p.xaxis.axis_label = 'x'
p.yaxis.axis_label = 'Pr(x)'

元のソースコードでは

show(gridplot(p,ncols = 2, plot_width=400, plot_height=400, toolbar_location=None))

なのですが、動かなかったので

show(p)

費用の分布をみるとべらぼうに高い値は少ないようです。
大体10000くらい。

f= pl.figure(figsize=(12,5))

ax=f.add_subplot(121)
sns.distplot(data[(data.smoker == 1)]["charges"],color='c',ax=ax)
ax.set_title('Distribution of charges for smokers')

ax=f.add_subplot(122)
sns.distplot(data[(data.smoker == 0)]['charges'],color='b',ax=ax)
ax.set_title('Distribution of charges for non-smokers')

喫煙者と非喫煙者での費用分布の違いを見ると、
喫煙者はふたこぶの分布で、さらに費用は高い傾向にある。
喫煙していなければ10000くらいで大体のデータが収まっています。

sns.catplot(x="smoker", kind="count",hue = 'sex', palette="pink", data=data)

女性は1,男性は0に相当します
喫煙者を確認してみると、男性のほうが喫煙者でありそうです。
この関係から、男性全体の治療費は女性よりも多くなりそうですね。

sns.catplot(x="sex", y="charges", hue="smoker",
            kind="violin", data=data, palette = 'magma')

バイオリンplotで治療費と人数の密度を見てみましょう
こっちのほうが分かりやすい視覚化ですよね

pl.figure(figsize=(12,5))
pl.title("Box plot for charges of women")
sns.boxplot(y="smoker", x="charges", data =  data[(data.sex == 1)] , orient="h", palette = 'magma')

喫煙者のboxplot 女性から

pl.figure(figsize=(12,5))
pl.title("Box plot for charges of men")
sns.boxplot(y="smoker", x="charges", data =  data[(data.sex == 0)] , orient="h", palette = 'rainbow')

男性も。

年齢との関係を見てみましょう。

pl.figure(figsize=(12,5))
pl.title("Distribution of age")
ax = sns.distplot(data["age"], color = 'g')

患者の最もヤングな年齢が18
シニアは64です
18歳で吸ってる人はいるのでしょうか？？

sns.catplot(x="smoker", kind="count",hue = 'sex', palette="rainbow", data=data[(data.age == 18)])
pl.title("The number of smokers and non-smokers (18 years old)")

あらま
18歳でも吸ってる人がいるんですね。
やはり18歳でも治療費は高くなるのでしょうか。

pl.figure(figsize=(12,5))
pl.title("Box plot for charges 18 years old smokers")
sns.boxplot(y="smoker", x="charges", data = data[(data.age == 18)] , orient="h", palette = 'pink')

18歳の金額分布。
18歳でも喫煙者は治療費が高くなっているようですね。

g = sns.jointplot(x="age", y="charges", data = data[(data.smoker == 0)],kind="kde", color="m")
g.plot_joint(pl.scatter, c="w", s=30, linewidth=1, marker="+")
g.ax_joint.collections[0].set_alpha(0)
g.set_axis_labels("$X$", "$Y$")
ax.set_title('Distribution of charges and age for non-smokers')

喫煙している人の金額分布
(若い人ほど単純にやすい)

g = sns.jointplot(x="age", y="charges", data = data[(data.smoker == 1)],kind="kde", color="c")
g.plot_joint(pl.scatter, c="w", s=30, linewidth=1, marker="+")
g.ax_joint.collections[0].set_alpha(0)
g.set_axis_labels("$X$", "$Y$")
ax.set_title('Distribution of charges and age for smokers')

喫煙者の金額分布
年齢と金額をみると金額は二こぶになっている。

#non - smokers
p = figure(plot_width=500, plot_height=450)
p.circle(x=data[(data.smoker == 0)].age,y=data[(data.smoker == 0)].charges, size=7, line_color="navy", fill_color="pink", fill_alpha=0.9)

show(p)

#smokers
p = figure(plot_width=500, plot_height=450)
p.circle(x=data[(data.smoker == 1)].age,y=data[(data.smoker == 1)].charges, size=7, line_color="navy", fill_color="red", fill_alpha=0.9)
show(p)

sns.lmplot(x="age", y="charges", hue="smoker", data=data, palette = 'inferno_r', size = 7)
ax.set_title('Smokers and non-smokers')

重ね合わせてplotみるとこんな感じ

喫煙者の2グループについて、それぞれのグループに分けて回帰をしている。

非喫煙者は直線が年齢と比例して増加していっている。
自然の摂理ですよね。健康第一!

喫煙者ではばらつきが大変大きく、単純に年齢を重ねたら高くなるのか？と聞かれると説明できない部分が多いデータになっている。

Bmiと比べてみましょう
治療費とbmiは関係があるのでしょうか？

pl.figure(figsize=(12,5))
pl.title("Distribution of bmi")
ax = sns.distplot(data["bmi"], color = 'm')

Bmiの分布は平均30のきれいな分布です。
30ってどんなもんなのかグーグルに聞いてみましょう
30は肥満の始まりらしいです。Bmiを30で切り分け、30以上以下で費用分布を見ましょう

pl.figure(figsize=(12,5))
pl.title("Distribution of charges for patients with BMI greater than 30")
ax = sns.distplot(data[(data.bmi >= 30)]['charges'], color = 'm')

30以上の分布

pl.figure(figsize=(12,5))
pl.title("Distribution of charges for patients with BMI less than 30")
ax = sns.distplot(data[(data.bmi < 30)]['charges'], color = 'b')

30以下の分布

Bmiが30を超えるほど高額を支払っています

g = sns.jointplot(x="bmi", y="charges", data = data,kind="kde", color="r")
g.plot_joint(pl.scatter, c="w", s=30, linewidth=1, marker="+")
g.ax_joint.collections[0].set_alpha(0)
g.set_axis_labels("$X$", "$Y$")
ax.set_title('Distribution of bmi and charges')

Bmiに関して治療費と合わせてみてみましょ

さらに喫煙者とbmiではどうなるでしょうか

pl.figure(figsize=(10,6))
ax = sns.scatterplot(x='bmi',y='charges',data=data,palette='magma',hue='smoker')
ax.set_title('Scatter plot of charges and bmi')

sns.lmplot(x="bmi", y="charges", hue="smoker", data=data, palette = 'magma', size = 8)

喫煙者であればbmiと治療費に関する直線の傾きが上がっていますね。

子供を持っていたら何か特徴はみられるのでしょうか？

sns.catplot(x="children", kind="count", palette="ch:.25", data=data, size = 6)

ほとんど子供を持っていないようです
子供を抱えていたら喫煙したりするのでしょうか？

sns.catplot(x="smoker", kind="count", palette="rainbow",hue = "sex",
            data=data[(data.children > 0)], size = 6)
ax.set_title('Smokers and non-smokers who have childrens')

子持ちに喫煙者がいますね。
でも喫煙してない親のほうがかなり多いことがわかります

それぞれの変数から回帰

from sklearn.linear_model import LinearRegression
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import PolynomialFeatures
from sklearn.metrics import r2_score,mean_squared_error
from sklearn.ensemble import RandomForestRegressor

x = data.drop(['charges'], axis = 1)
y = data.charges

x_train,x_test,y_train,y_test = train_test_split(x,y, random_state = 0)
lr = LinearRegression().fit(x_train,y_train)

y_train_pred = lr.predict(x_train)
y_test_pred = lr.predict(x_test)

print(lr.score(x_test,y_test))

0.7962732059725786

線形回帰してみました
予測値と実際の値を比較して精度を測定すると0.79でした
データが必ずしも綺麗とは限らないので参考程度にしましょう

X = data.drop(['charges','region'], axis = 1)
Y = data.charges

quad = PolynomialFeatures (degree = 2)
x_quad = quad.fit_transform(X)

X_train,X_test,Y_train,Y_test = train_test_split(x_quad,Y, random_state = 0)

plr = LinearRegression().fit(X_train,Y_train)

Y_train_pred = plr.predict(X_train)
Y_test_pred = plr.predict(X_test)

print(plr.score(X_test,Y_test))

0.8849197344147237

変数を減らしてシンプルにしています。
Regionを消すと、予測の精度は0.88まで上がりました。

ランダムフォレストを使ってみます

forest = RandomForestRegressor(n_estimators = 100,
                              criterion = 'mse',
                              random_state = 1,
                              n_jobs = -1)
forest.fit(x_train,y_train)
forest_train_pred = forest.predict(x_train)
forest_test_pred = forest.predict(x_test)

print('MSE train data: %.3f, MSE test data: %.3f' % (
mean_squared_error(y_train,forest_train_pred),
mean_squared_error(y_test,forest_test_pred)))
print('R2 train data: %.3f, R2 test data: %.3f' % (
r2_score(y_train,forest_train_pred),
r2_score(y_test,forest_test_pred)))

MSE train data: 3729086.094, MSE test data: 19933823.142
R2 train data: 0.974, R2 test data: 0.873

ランダムフォレストといえばclassifierをよく見る気がしますが、
こんかいはregressorを使用していきます。

二条平均平方根MSEとR二乗値を確認します

pl.figure(figsize=(10,6))

pl.scatter(forest_train_pred,forest_train_pred - y_train,
          c = 'black', marker = 'o', s = 35, alpha = 0.5,
          label = 'Train data')
pl.scatter(forest_test_pred,forest_test_pred - y_test,
          c = 'c', marker = 'o', s = 35, alpha = 0.7,
          label = 'Test data')
pl.xlabel('Predicted values')
pl.ylabel('Tailings')
pl.legend(loc = 'upper left')
pl.hlines(y = 0, xmin = 0, xmax = 60000, lw = 2, color = 'red')
pl.show()

X軸に予測値
Y軸に予測値と実際の値との差をplotしている
Trainとtestどちらもplotしている

以上

seabornやbokehはplotがとても分かりやすくなって素敵な資料が作成できそうです。
そこに時間を割くかは置いといても、見やすいplotは見にくいplotよりは理解を深めてくれるのでマスターしていきたいです。

個人的にはlabelencorderの使用例が見られたのがうれしかった。

こんな感じでランダムフォレストで回帰がうごくのかって勉強になりました。

はじめに

ノートテイキングアプリEvernoteのサードパーティアプリを開発するにあたり、アプリで利用するアクセストークンをOAuth認証により取得する方法を確立させたのでメモ。

まず、Evernoteのサードパーティアプリ利用時のユーザー認可の方法には以下の二通りの方法がある。¹

1. EvernoteとサードパーティアプリのOAuth認証により取得したCookieをクライアント側で保存し、以降サードパーティアプリ利用時の認可に利用
2. EvernoteとサードパーティアプリのOAuth認証により取得したアクセストークンをサーバー側で保存し、以降サードパーティアプリ利用時の認可に利用

1は不特定多数のユーザーが各ユーザー自身のEvernoteアカウント上のリソースをサードパーティアプリから利用することを想定した方法である。
2は管理者や特定の少数のユーザーが特定のEvernoteアカウント上のリソースをサードパーティアプリから利用することを想定した方法である。

本記事では2の利用方法を実現させるために、OAuth認証によりアクセストークンを取得する方法を紹介する。

手順

API Key取得

Evernoteのサードパーティアプリごとに必要となるAPI KeyをEvernote開発者用サイトを通じて取得する。

API Keyリクエスト

http://dev.evernote.com/doc/ にアクセスし、画面内の「GET AN API KEY」をクリック。

画面上部に下記フォームが表示されるので、入力欄に適当に入力して、「Full Access」を選択し、「I agree 〜」にチェックを入れて、「Request Key」をクリック。

画面が遷移し「Consumer Key」と「Consumer Secret」が表示されるので控えておく。

ここまでで取得したAPIキーはEvernoteのサンドボックス環境（Sandbox development server）では利用できるが、実際にコンシューマーが利用するEvernoteのプロダクション環境（production servers）で利用するためには次手順のAPI Keyアクティベートを行う必要がある。

API Keyアクティベート

http://dev.evernote.com/support/glossary.php#k にアクセスし、「this form」をクリック。

画面内に下記フォームが表示されるので先程控えた情報と合わせて入力し、「Submit」をクリック。

Evernote開発者サポートから下記のようなメールが届いたらサードパーティアプリのAPI Keyのアクティベートは完了（アクティベートをリクエストしてから完了するまでには数日要する）。

差出人: devsupport@evernote.com
送信日時: 2018年7月21日 2:37:03 (UTC+09:00) 大阪、札幌、東京
宛先: XXXXXXXX
件名: Re: xxxxxxxx

##- Please type your reply above this line -##

xxxxxxxx (Evernote Developer Relations)
Jul 20, 10:37 AM PDT
Hello xxxxxxxx,

 We have activated your API key (xxxxxxx) on our production service. If you have questions, please proceed to Stack Overflow and join the community discussion there: http://stackoverflow.com/questions/tagged/evernote

 Thank you for building with our API,

 Evernote Developer Relations

xxxxxxxx
Jul 19, 1:10 AM PDT
xxxxxxxx

[XXXXXX-XXXX]

アクセストークン取得

Evernote開発者用ドキュメントでは各開発言語向けのSDKが取り揃えられている。今回はそのうちのPython2向けのSDKを利用してアクセストークン取得を行う。²

また、Python2向けSDKではサンプルとして「client」、「django」、「pyramid」を利用した３種類のOAuth実装用のコードが含まれているが、今回はDjangoを利用した方法をもとにしたアクセストークン取得の手順を記載する。

前提

$ python -V
Python 2.7.10

SDKをローカル環境にgit clone

$ git clone https://github.com/evernote/evernote-sdk-python.git

各種モジュールをpip install

$ cd evernote-sdk-python/sample/django
$ pip install -r requirements.txt

views.py編集

evernote-sdk-python/sample/django/oauth内のviews.pyを下記のように編集する。（コード内①②③の箇所）

views.py

from evernote.api.client import EvernoteClient

from django.core.urlresolvers import reverse
from django.shortcuts import render_to_response
from django.shortcuts import redirect
# rename config.py.template to config.py and paste your credentials. 
from config import EN_CONSUMER_KEY, EN_CONSUMER_SECRET

def get_evernote_client(token=None):
    if token:
        return EvernoteClient(token=token, sandbox=True)
    else:
        return EvernoteClient(
            consumer_key=EN_CONSUMER_KEY,
            consumer_secret=EN_CONSUMER_SECRET,
            sandbox=False #・・・① True => False
        )


def index(request):
    return render_to_response('oauth/index.html')


def auth(request):
    client = get_evernote_client()
    callbackUrl = 'http://%s%s' % (
        request.get_host(), reverse('evernote_callback'))
    request_token = client.get_request_token(callbackUrl)

    # Save the request token information for later
    request.session['oauth_token'] = request_token['oauth_token']
    request.session['oauth_token_secret'] = request_token['oauth_token_secret']

    # Redirect the user to the Evernote authorization URL
    return redirect(client.get_authorize_url(request_token))


def callback(request):
    try:
        client = get_evernote_client()
        access_token = client.get_access_token( #・・・② client.get_access_token( => access_token = client.get_access_token(
            request.session['oauth_token'],
            request.session['oauth_token_secret'],
            request.GET.get('oauth_verifier', '')
        )
    except KeyError:
        return redirect('/')
    print('\n--*-- Access Token --*--\n' + access_token + '\n') #・・・③
    note_store = client.get_note_store()
    notebooks = note_store.listNotebooks()

    return render_to_response('oauth/callback.html', {'notebooks': notebooks})


def reset(request):
    return redirect('/')

config.py作成

evernote-sdk-python/sample/django/oauth内のconfig.py.templateをconfig.pyにリネームして、API Key取得手順で取得した「consumer key」と「consumer secret」を記載する。

config.py

EN_CONSUMER_KEY = 'your consumer key'
EN_CONSUMER_SECRET = 'your consumer secret'

OAuth認証実施、アクセストークン取得

evernote-sdk-python/sample/django/内のmanage.pyを実行してローカルでサーバーを起動。

$ python manage.py runserver

ブラウザからhttp://127.0.0.1:8000/にアクセス。
表示される画面内の「Click here」をクリック。

Evernoteのログイン画面が表示されるので、サードパーティアプリにアクセスさせたいEvernoteアカウントでログイン。

ログインをすると下記の承認画面に遷移するので、承認の有効期間を１日間、１週間、30日間、1年間から選択し、「承認する」をクリック。

ログインしたEvernoteアカウント内のノートブック一覧が画面に表示されたらサードパーティアプリのOAuth認証完了である。

manage.pyを実行したターミナル上で--*-- Access Token --*--の下にアクセストークンが表示される。
これでEvernoteのサードパーティ用のアクセストークンを取得することができた。

--*-- Access Token --*--
＜S=xxx:U=xxxxxxx:E=xxxxxxxxxxx:C=xxxxxxxxxxx:P=xxx:A=xxxxx:V=x:H=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx＞

次回、今回の手順で取得したアクセストークンを利用したサードパーティアプリの実装の一例を投稿予定。

補足

すでに同じEvernoteアカウント、同じサードパーティアプリ(＝API Key)で承認済みの場合は下記ような承認画面が表示されて再承認を求められる。再承認をすると新しいアクセストークンが取得でき、再承認前のアクセストークンと同様に利用することができる。

また、Evernoteのサードパーティ製アプリケーションにある通り、自分のEvernoteアカウントのサードパーティアプリごとの承認状況はアプリケーションページで管理できる。承認の取り消しを行うと、その承認時に取得したアクセストークンは無効となり利用できなくなる。

参考

https://myenigma.hatenablog.com/entry/2016/01/23/090212
https://stackoverflow.com/questions/46260328/evernote-sdk-how-can-i-get-the-permission-to-access-all-notebooks-metadata

---

1. 以前まではわざわざOAuth認証を利用しなくてもDeveloper Tokensにある通り開発者用トークンというアクセストークンを利用する方法もあったようだが、現在はサンドボックス環境向けのみ取得可能で、プロダクション環境向けは取得できなくなっている。 ↩

2. 残念なことに公式のPython向けSDKはPython2のみでPython3は未提供の様子（Python3向けSDKのページもあるにはあるが、作成中の様子で2017年9月から更新がされていないので公式は多分やる気なし）。ただしPython3向けのpypiパッケージevernote3は利用可能。 ↩

csv形式からjson形式へ

知り合いのおじさんが経営する学習塾で使用する英単語テスト作成システムの新調のため，csv形式で保存されていた単語のデータをjson形式に変換する必要がありました．

備忘録として初投稿しようと思います．

Pythonで変換

探せばフリーソフトなど見つかりそうでしたが，最近利用しているPandasの復習も兼ねてPythonで変換しました．

利用したモジュール

• json
• pandas
• argparse

csv形式のファイルの仕様

1行目に乱数，2行目に単語，3行目に意味が入力されています．

乱数はテスト作成でランダムに出題できるよう，マクロで並び替えを行う際に使用します．新しい環境では利用しないため削除します．

word_db.csv

random num, name, mean
0.93837248,apple,りんご
...
...

json形式のファイルの仕様

システム自体を製作したのは別の方なので，実際の仕様ではありませんが以下のようにします．

word_db.json

[
    {
        "name": "単語",
        "mean": "単語の意味",
        "id": "一意に設定する文字列",
        "rank": "習熟度を表す数値（int）",
    },
]

ソースコード

あれこれ書く前に結果だけ載せておきます．

細かい部分は変更しておりますが，おおまかな雰囲気はこんな感じです．

csv_to_json.py

import json
import argparse
import pandas as pd


def csv_to_json(src_file, dst_file):
    if dst_file:
        dst_file = dst_file
    else:
        dst_file = 'tmp.json'
    df = pd.read_csv(src_file)
    df['id'] = [None for _ in range(len(df.index))]
    df['rank'] = [0 for _ in range(len(df.index))]
    df.to_json(dst_file, force_ascii=False, orient='records')

    with open(dst_file, 'r', encoding='utf-8') as f:
        json_out = json.load(f)
    with open(dst_file, 'w', encoding='utf-8') as f:
        json.dump(json_out, f, ensure_ascii = False, indent = 4, separators = (',', ': '))


if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    # add argument: csv file name
    parser.add_argument('src', help='source csv file name')
    parser.add_argument('--dst', help='destination json file name')
    # analysis arguments
    args = parser.parse_args()
    csv_to_json(args.src, args.dst)

利用する際はこんな感じ．

$ python3 csv_to_json.py word_db.csv

この場合tmp.jsonというjson形式のファイルが作成されます．
ファイル名を指定したい場合は以下の通り．

$ python3 csv_to_json.py word_db.csv --dst (指定したいファイル名).json

2度も書き込んでいる理由

最初はリストを用いて適当に変換してしまおうと思っていましたが，列の追加・削除やデータの形式を保った状態での書き込みが面倒だったので，pandasを用いることにしました．

その際データの整形がうまくいかず1行で出力されてしまったので，なんとなく見栄えがいいと思い2回目に整形してDumpしています．

以上．

今後複数の単語データを変換する可能性があったため，コンソールによるファイル名の設定を行えるようにできたのは嬉しい！

Pythonペーペーですが楽しくて時間を忘れますね〜

初投稿で至らない部分も多くあると思いますので，改善点やご指摘お待ちしています．

継承時のメソッドのオーバーライドの禁止は，JavaやC++ではfinalキーワードで実現できますが，Pythonの標準機能としてはありません．
ということで，Python（勿論3系）においてどうやってやればよいかを調べたり，考えたりしました．

環境

• Ubuntu 18.04
• Python 3.6
• mypy: 0.720

mypy

• https://github.com/python/mypy

Python 3.5から型ヒントが導入されましたが，その型ヒントを使って静的に型チェックを行うためのツールです．
そんなmypyですが，@finalというデコレータを用いて，オーバーライドをしてはいけないメソッドであることを表明することができます．

使い方としては以下の通りです．@finalを使って，helloというfinalメソッドだと表明しています．

final.py

from typing_extensions import final

class Base:
    @final
    def hello(self) -> None:
        print("hello")

class Derived(Base):
    def hello(self) -> None:
        print("こんにちは")

Base().hello()
Derived().hello()

このファイルに対してmypyを使うと警告を出してくれます．

$ mypy final.py
final.py:9: error: Cannot override final attribute "hello" (previously declared in base class "Base")

ただ，Type Hintsと同様に実行時に影響は無いのでその点注意が必要です．

$ python3 final.py
hello
こんにちは

Pros

• pip install mypyするだけなので導入が楽．

Cons

• 実行時にエラーにならないし，警告も出ない．

参考

• https://mypy.readthedocs.io/en/latest/final_attrs.html

Metaclassの利用

mypyによる静的解析もよいのですが，実行時にチェックして例外が上がる方が自分としては嬉しいものです．
イメージとしては，標準ライブラリの抽象基底クラスモジュールであるabc (https://docs.python.org/ja/3/library/abc.html) のような感じでしょうか．

ということで，https://github.com/python/cpython/blob/3.7/Lib/abc.py を参考に実装してみたのがこれです（参考と言っても__isfinalmethod__くらいしか残っていない気がしますが）．
全てのメソッドを基底クラスと突き合わせているだけの単純な実装です．

import inspect

def final(funcobj):
    funcobj.__isfinalmethod__ = True
    return funcobj


class FinalMeta(type):

    def __new__(mcls, name, bases, namespace, **kwargs):
        cls = super().__new__(mcls, name, bases, namespace, **kwargs)
        # メンバ関数と@staticmethod
        for funcname, func in inspect.getmembers(cls, inspect.isfunction):
            for base in bases:
                base_func = getattr(base, funcname, None)
                if base_func and getattr(base_func, '__isfinalfunction__', False) and \
                   func != base_func:
                    raise TypeError("Overriding @final function: {}()".format(funcname))
        # @classmethod
        for funcname, func in inspect.getmembers(cls, inspect.ismethod):
            for base in bases:
                base_func = getattr(base, funcname, None)
                if base_func and getattr(base_func, '__isfinalfunction__', False) and \
                   func.__func__ != getattr(base_func, '__func__', None):
                    raise TypeError("Overriding @final method: {}()".format(funcname))
        return cls

自分は初めて知ったのですが，classmethodだけは，関数の実体が__func__にいるみたいです．第一引数のクラスは固定なので，引数を一つ減らす形でラップしているといったところでしょうか．

使用例

以下のような基底クラスを準備します．

class A(metaclass=FinalMeta):

    @final
    def final_member(self):
        pass

    @classmethod
    @final
    def final_class(cls):
        pass

    @staticmethod
    @final
    def final_static():
        pass

    def overridable(self):
        print("from A")

メンバ関数のオーバーライド

try:
    class B(A):
        def final_member(self):
            pass
except TypeError as e:
    print(e)
    print("prohibit overriding final member function")

#=> Overriding @final function: final_member()
#=> prohibit overriding final member function

classmethodのオーバーライド

try:
    class C(A):
        @classmethod
        def final_class(cls):
            pass
except TypeError as e:
    print(e)
    print("prohibit overriding final class method")

#=> Overriding @final function: final_class()
#=> prohibit overriding final class method

staticmethodのオーバーライド

try:
    class E(A):
        @staticmethod
        def final_static():
            pass
except TypeError as e:
    print(e)
    print("prohibit overriding final static method")

#=> Overriding @final function: final_static()
#=> prohibit overriding final static method

正常

class F(A):
    def overridable(self):
        print("from F")

F().overridable()
#=> from F

ぱっと見ちゃんと動いていそうです．

Pros

• 実行時にオーバーライドを検出して例外を起こせる．

Cons

• 実行時のオーバーヘッドは多分ある．
  • 個人的な興味外なので，計測はしていません．
  • かなり実装がナイーブなので，dict等使って管理すれば少しは速くなりそう．
  • まともな実装であれば，継承もメソッドの数も大したことにはならないので，多分誤差．この程度が気になるならそもそもPythonを使わない方がよさそう．

補足

abcの場合はインスタンス化時に例外が上がるが，これはクラス定義時に例外を上げるようにすると，抽象クラスを継承した抽象クラスの定義ができなくなる等の都合だと思います．
今回のfinalには関係のない都合なので，こちらはクラス定義時に例外が上がるようにしました．

まとめ

オーバーライドを抑制するための手段を二つ紹介しました．
抑制と書いているのは，結局 https://qiita.com/eduidl/items/99f856c9710ef10bfec0 と同じように，setattrを使ったりすれば，結局のところいくらでも抜け道があるからです．結局それがPython的ということなのでしょうか．

関連リンク

• 自分と同じようなことを考える人はいるようで先例がいくつかありました．（実装がどれも気に入らないまたは，ぱっと理解できなかったかで結局あまり参考にはしていません．）
  • https://stackoverflow.com/questions/3948873/prevent-function-overriding-in-python
  • https://stackoverflow.com/questions/321024/making-functions-non-override-able
  • https://stackoverflow.com/questions/2425656/how-to-prevent-a-function-from-being-overridden-in-python

3つ目のリンク先のこれが一番好き．

# We'll fire you if you override this method.

（ブログ記事からの転載）

[https://leetcode.com/problems/symmetric-tree/]

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

前回記事のSame Treeに続き、バイナリツリーを扱った問題。
今度はSymmetric、つまり左右対照の図形かどうかを判定します。
ボーナスポイントをくれるとのことですし、recursiveな解法とiterativeな解法の両方を探してみましょう。

解答・解説

解法1

recursiveな解法。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        else:
            return self.isMirror(root.left, root.right)
    def isMirror(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val == right.val:
            outPair = self.isMirror(left.left, right.right)
            inPiar = self.isMirror(left.right, right.left)
            return outPair and inPiar
        else:
            return False

2つ関数を定義していますが、前回のSame Treeと異なりバイナリツリー1つしかないので、もしツリーがない場合Trueを返す処理を挟んでいるだけです。
isMirror関数の処理はSame Treeに似ていますが、
（左側のツリーの左側と右側のツリーの右側）、（右側のツリーの左側と右側のツリーの左側）の各々が同一かどうかを判定するようにします。

解法2

Iterativeな解法。
せっかくなので前回記事でも取り扱った、deque型を使って書いてみます。

from collections import deque
class Solution:
    def isSymmetric(self, root):
        if not root:
            return True

        deq = deque([(root.left, root.right),])
        while deq:
            t1, t2 = deq.popleft()
            if not t1 and not t2:
                continue
            elif (not t1 or not t2) or (t1.val != t2.val):
                return False

            deq.append((t1.left, t2.right))
            deq.append((t1.right, t2.left))

        return True

以下にSame Treeの時のコードを再掲します。微妙な差異しかないのが分かるかと思います。

from collections import deque
class Solution:
    def isSameTree(self, p, q):
        def check(p, q):
            if not p and not q:
                return True
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True

        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False

            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))

        return True

■Rapidly-exploring random tree(PythonRobotics)
＊コード参考サイト
！！！PythonRobotics！！！
https://github.com/AtsushiSakai/PythonRobotics/tree/master/PathPlanning/RRT
?こちらのGitHub参考にしております。ものすごく良いコードがたくさんあるので、ぜひ覗いてみては、、、

?RRTのアルゴリズムの説明。
私のサイト：RRTアルゴリズム
https://meerobots.blogspot.com/2019/07/rapidly-exploring-random-treerrt.html

【Pythonコード説明】
説明の流れ
１．全体コード
２．メイン文
３．ＲＲＴのコード
ざっくり書いてます。少しでも参考になれば、、、また何かご指摘があれば宜しくお願い致します。
■注意
現在コード修正中なようです！！！！お気を付けください。

A1．コード全体

rrt.py

"""
Path planning Sample Code with Randomized Rapidly-Exploring Random Trees (RRT)
author: AtsushiSakai(@Atsushi_twi)
"""

import math
import random

import matplotlib.pyplot as plt

show_animation = True


class RRT:
    """
    Class for RRT planning
    """

    class Node():
        """
        RRT Node
        """

        def __init__(self, x, y):
            self.x = x
            self.y = y
            self.parent = None

    def __init__(self, start, goal, obstacle_list,
                 rand_area, expand_dis=1.0, goal_sample_rate=5, max_iter=500):
        """
        Setting Parameter
        start:Start Position [x,y]
        goal:Goal Position [x,y]
        obstacleList:obstacle Positions [[x,y,size],...]
        randArea:Ramdom Samping Area [min,max]
        """
        self.start = self.Node(start[0], start[1])
        self.end = self.Node(goal[0], goal[1])
        self.min_rand = rand_area[0]
        self.max_rand = rand_area[1]
        self.expand_dis = expand_dis
        self.goal_sample_rate = goal_sample_rate
        self.max_iter = max_iter
        self.obstacleList = obstacle_list
        self.node_list = []

    def planning(self, animation=True):
        """
        rrt path planning
        animation: flag for animation on or off
        """

        self.node_list = [self.start]
        for i in range(self.max_iter):
            rnd = self.get_random_point()
            nearest_ind = self.get_nearest_list_index(self.node_list, rnd)
            nearest_node = self.node_list[nearest_ind]

            new_node = self.steer(rnd, nearest_node)
            new_node.parent = nearest_node

            if not self.check_collision(new_node, self.obstacleList):
                continue

            self.node_list.append(new_node)
            print("nNodelist:", len(self.node_list))

            # check goal
            if self.calc_dist_to_goal(new_node.x, new_node.y) <= self.expand_dis:
                print("Goal!!")
                return self.generate_final_course(len(self.node_list) - 1)

            if animation and i % 5:
                self.draw_graph(rnd)

        return None  # cannot find path

    def steer(self, rnd, nearest_node):
        new_node = self.Node(rnd[0], rnd[1])
        d, theta = self.calc_distance_and_angle(nearest_node, new_node)
        if d > self.expand_dis:
            new_node.x = nearest_node.x + self.expand_dis * math.cos(theta)
            new_node.y = nearest_node.y + self.expand_dis * math.sin(theta)

        return new_node

    def generate_final_course(self, goal_ind):
        path = [[self.end.x, self.end.y]]
        node = self.node_list[goal_ind]
        while node.parent is not None:
            path.append([node.x, node.y])
            node = node.parent
        path.append([node.x, node.y])

        return path

    def calc_dist_to_goal(self, x, y):
        dx = x - self.end.x
        dy = y - self.end.y
        return math.sqrt(dx ** 2 + dy ** 2)

    def get_random_point(self):
        if random.randint(0, 100) > self.goal_sample_rate:
            rnd = [random.uniform(self.min_rand, self.max_rand),
                   random.uniform(self.min_rand, self.max_rand)]
        else:  # goal point sampling
            rnd = [self.end.x, self.end.y]
        return rnd

    def draw_graph(self, rnd=None):
        plt.clf()
        if rnd is not None:
            plt.plot(rnd[0], rnd[1], "^k")
        for node in self.node_list:
            if node.parent:
                plt.plot([node.x, node.parent.x],
                         [node.y, node.parent.y],
                         "-g")

        for (ox, oy, size) in self.obstacleList:
            plt.plot(ox, oy, "ok", ms=30 * size)

        plt.plot(self.start.x, self.start.y, "xr")
        plt.plot(self.end.x, self.end.y, "xr")
        plt.axis([-2, 15, -2, 15])
        plt.grid(True)
        plt.pause(0.01)

    @staticmethod
    def get_nearest_list_index(node_list, rnd):
        dlist = [(node.x - rnd[0]) ** 2 + (node.y - rnd[1])
                 ** 2 for node in node_list]
        minind = dlist.index(min(dlist))

        return minind

    @staticmethod
    def check_collision(node, obstacleList):
        for (ox, oy, size) in obstacleList:
            dx = ox - node.x
            dy = oy - node.y
            d = dx * dx + dy * dy
            if d <= size ** 2:
                return False  # collision

        return True  # safe

    @staticmethod
    def calc_distance_and_angle(from_node, to_node):
        dx = to_node.x - from_node.x
        dy = to_node.y - from_node.y
        d = math.sqrt(dx ** 2 + dy ** 2)
        theta = math.atan2(dy, dx)
        return d, theta


def main(gx=5.0, gy=10.0):
    print("start " + __file__)

    # ====Search Path with RRT====
    obstacleList = [
        (5, 5, 1),
        (3, 6, 2),
        (3, 8, 2),
        (3, 10, 2),
        (7, 5, 2),
        (9, 5, 2)
    ]  # [x,y,size]
    # Set Initial parameters
    rrt = RRT(start=[0, 0],
              goal=[gx, gy],
              rand_area=[-2, 15],
              obstacle_list=obstacleList)
    path = rrt.planning(animation=show_animation)

    if path is None:
        print("Cannot find path")
    else:
        print("found path!!")

        # Draw final path
        if show_animation:
            rrt.draw_graph()
            plt.plot([x for (x, y) in path], [y for (x, y) in path], '-r')
            plt.grid(True)
            plt.pause(0.01)  # Need for Mac
            plt.show()


if __name__ == '__main__':
    main()

B1. メイン文
1 : スタート、ゴール、障害物の位置、設定
2 : RRT実行

rrt.py

def main(gx=5.0, gy=10.0):
    print("start " + __file__)

    # ====Search Path with RRT====
    obstacleList = [
        (5, 5, 1),
        (3, 6, 2),
        (3, 8, 2),
        (3, 10, 2),
        (7, 5, 2),
        (9, 5, 2)
    ]  # [x,y,size]
    # Set Initial parameters
    rrt = RRT(start=[0, 0],
              goal=[gx, gy],
              rand_area=[-2, 15],
              obstacle_list=obstacleList)
    path = rrt.planning(animation=show_animation)

    if path is None:
        print("Cannot find path")
    else:
        print("found path!!")

        # Draw final path
        if show_animation:
            rrt.draw_graph()
            plt.plot([x for (x, y) in path], [y for (x, y) in path], '-r')
            plt.grid(True)
            plt.pause(0.01)  # Need for Mac
            plt.show()


if __name__ == '__main__':
    main()

C1．変数定義：位置XY

rrt.py

class RRT:
    """
    Class for RRT planning
    """

    class Node():
        """
        RRT Node
        """

        def __init__(self, x, y):
            self.x = x
            self.y = y
            self.parent = None

C2．定義：スタート、ゴール、障害物（位置とサイズ）、ゴール選ぶ割合、ノードのバス距離、

rrt.py

    def __init__(self, start, goal, obstacle_list,
                 rand_area, expand_dis=1.0, goal_sample_rate=5, max_iter=500):
        """
        Setting Parameter
        start:Start Position [x,y]
        goal:Goal Position [x,y]
        obstacleList:obstacle Positions [[x,y,size],...]
        randArea:Ramdom Samping Area [min,max]
        """
        self.start = self.Node(start[0], start[1])
        self.end = self.Node(goal[0], goal[1])
        self.min_rand = rand_area[0]
        self.max_rand = rand_area[1]
        self.expand_dis = expand_dis
        self.goal_sample_rate = goal_sample_rate
        self.max_iter = max_iter
        self.obstacleList = obstacle_list
        self.node_list = []

C3．アニメーション用データ

rrt.py

    def planning(self, animation=True):
        """
        rrt path planning
        animation: flag for animation on or off
        """

        self.node_list = [self.start]
        for i in range(self.max_iter):
            rnd = self.get_random_point()
            nearest_ind = self.get_nearest_list_index(self.node_list, rnd)
            nearest_node = self.node_list[nearest_ind]

            new_node = self.steer(rnd, nearest_node)
            new_node.parent = nearest_node

            if not self.check_collision(new_node, self.obstacleList):
                continue

            self.node_list.append(new_node)
            print("nNodelist:", len(self.node_list))

            # check goal
            if self.calc_dist_to_goal(new_node.x, new_node.y) <= self.expand_dis:
                print("Goal!!")
                return self.generate_final_course(len(self.node_list) - 1)

            if animation and i % 5:
                self.draw_graph(rnd)

        return None  # cannot find path

C4．現在の位置とランダム位置との関係から新しい位置を計算

rrt.py

    def steer(self, rnd, nearest_node):
        new_node = self.Node(rnd[0], rnd[1])
        d, theta = self.calc_distance_and_angle(nearest_node, new_node)
        if d > self.expand_dis:
            new_node.x = nearest_node.x + self.expand_dis * math.cos(theta)
            new_node.y = nearest_node.y + self.expand_dis * math.sin(theta)

        return new_node

C5．コース結果？

rrt.py

    def generate_final_course(self, goal_ind):
        path = [[self.end.x, self.end.y]]
        node = self.node_list[goal_ind]
        while node.parent is not None:
            path.append([node.x, node.y])
            node = node.parent
        path.append([node.x, node.y])

        return path

C6．ゴールまでの距離計算

rrt.py

    def calc_dist_to_goal(self, x, y):
        dx = x - self.end.x
        dy = y - self.end.y
        return math.sqrt(dx ** 2 + dy ** 2)

C7．ランダム位置生成　任意の回数後ゴール地点選ぶ

rrt.py

    def get_random_point(self):
        if random.randint(0, 100) > self.goal_sample_rate:
            rnd = [random.uniform(self.min_rand, self.max_rand),
                   random.uniform(self.min_rand, self.max_rand)]
        else:  # goal point sampling
            rnd = [self.end.x, self.end.y]
        return rnd

C8．グラフ生成

rrt.py

    def draw_graph(self, rnd=None):
        plt.clf()
        if rnd is not None:
            plt.plot(rnd[0], rnd[1], "^k")
        for node in self.node_list:
            if node.parent:
                plt.plot([node.x, node.parent.x],
                         [node.y, node.parent.y],
                         "-g")

        for (ox, oy, size) in self.obstacleList:
            plt.plot(ox, oy, "ok", ms=30 * size)

        plt.plot(self.start.x, self.start.y, "xr")
        plt.plot(self.end.x, self.end.y, "xr")
        plt.axis([-2, 15, -2, 15])
        plt.grid(True)
        plt.pause(0.01)

C9．ランダム点から近い点を探索

rrt.py

    @staticmethod
    def get_nearest_list_index(node_list, rnd):
        dlist = [(node.x - rnd[0]) ** 2 + (node.y - rnd[1])
                 ** 2 for node in node_list]
        minind = dlist.index(min(dlist))

        return minind

C10．衝突判定：この方法では点で見ている。
・障害物の位置と次の位置のから距離ｄ算出
・障害物を円として定義し、距離ｄが半径より小さいと衝突

rrt.py

    @staticmethod
    def check_collision(node, obstacleList):
        for (ox, oy, size) in obstacleList:
            dx = ox - node.x
            dy = oy - node.y
            d = dx * dx + dy * dy
            if d <= size ** 2:
                return False  # collision

        return True  # safe

C11．今の位置からランダム位置の距離と角度を算出
次の位置を計算するため

rrt.py

    @staticmethod
    def calc_distance_and_angle(from_node, to_node):
        dx = to_node.x - from_node.x
        dy = to_node.y - from_node.y
        d = math.sqrt(dx ** 2 + dy ** 2)
        theta = math.atan2(dy, dx)
        return d, theta

これにて終了！
最適性は担保してないけど、簡単に実装できそう。。。

Pythonの標準ライブラリには抽象基底クラス用のabcというモジュールがあります．もしかしてと思ってやってみたら，やはり抜け道があったので誰得だと思いますが投稿します．

TL;DR

delattrを使ってoverrideを取り消します．

環境

• Ubuntu 18.04
• Python 3.6, 3.7

通常の使い方

抽象クラス(Base)を継承したクラス(Derived)が@abstractmethodでデコレートされた関数（抽象関数）をoverrideしていないときは，以下のように例外になります．

from abc import ABC, abstractmethod

class Base(ABC):
    @abstractmethod
    def method(self):
        print("from Base")

class Derived(Base):
    pass

Derived()

Traceback (most recent call last):
  File "abc.py", line 13, in <module>
    Derived()
TypeError: Can't instantiate abstract class Derived with abstract methods method

overrideすると，ちゃんと実行できます．

# 上は同じ

class Derived(Base):
    def method(self):
        print("from Derived")

Derived()
Derived().method()

from Derived

抜け道

Pythonにはメタプログラミングに便利な組み込み関数がいくつかあります．hasattrやsetattrです．
そして今回使うのは，delattrです．その名の通り，attrをdelします．
ということで，一旦overrideした上でそのメソッドを消すことを考えてみます．

from abc import ABC, abstractmethod

class Base(ABC):
    @abstractmethod
    def method(self):
        print("from Base")

class Derived(Base):
    def method(self):
        print("from Derived")

delattr(Derived, 'method')
# del Derived.method でも可

Derived()
Derived().method()

from Base

ということで，抽象関数を呼び出すことに成功？しました．（実際には抽象関数は空か例外を上げるかのどちらかだと思うので何の意味も無いと思います．）

原理としては，ABCはMetaclassを使っているので，class定義時でのみチェックされているということだと思います．

感想

プライベート関数等の例もあるので，わざと抜け道を残している気もします ¹ ．setattrやdelattrは用法用量を守って正しく使いましょう（使わないのがベストだと思いますが）．

参考

• https://docs.python.org/ja/3/library/abc.html
• https://docs.python.org/ja/3/library/functions.html#delattr

---

1. Rubyにもsendとかあるし，そういうことができてこその動的型付け言語みたいなところはある． ↩

AtCoder Beginners Contest 過去問チャレンジ1

AtCoder Beginners Selection(以下 abs) を解いたので、AtCoder Beginners Contest (以下 abc)の準備は万端かと思いきや、abs には難易度 ABC 問題しかなく、abc には難易度 DEF の問題が出るようなので、過去問のD以上の問題にチャレンジ.

あと abs を解くときに input() が動かなくてひどい目にあって raw_input() に差し替えたが、Python 3 は input() で大丈夫らしいので、Python 2 から 3 に切り替えた. print に括弧を付けるのがめんどくさいなと思っていたが、map や range が list じゃないことのほうがめんどくさいかもしれない.

ABC133D - Rain Flows into Dams

山iに降った水の量をRiとすると

(R1+R2) / 2 = A1
(R2+R3) / 2 = A2
(R3+R4) / 2 = A3
(R4+R5) / 2 = A3
...
(RN+R1) / 2 = AN

になることが分かる.
この時 R1 を求めるのは中学で習う連立一次方程式が分かっていれば特に何も難しいことはない.

((R1+R2) / 2) - ((R2+R3) / 2) + ((R3+R4) / 2) - ((R4+R5) / 2) + ... + ((RN+R1) / 2) = A1 - A2 + A3 - A4 + ... + AN
R1 = A1 - A2 + A3 - A4 + ... + AN

(Ri+Ri+1) / 2 = Ai から Ri+1 = 2 * Ai - Ri なので、R1 一つ分かりさえすれば残りはドミノ倒し的に分かるので、後はこれを Python のコードに落とすだけ.

n = int(input())
a = [int(e) for e in input().split()]
result = [sum(a[::2])-sum(a[1::2])]
for i in range(len(a) - 1):
  result.append(2*a[i]-result[i])
print(' '.join(map(str, result)))

ABC132D - Blue and Red Balls

再帰的に定式化は出来たものの遅い. 再帰関数の切り札 memoize や、小さい数字の部分は一発で返るようにして高速化したものの、TLE は一つも減らずに敗退.

n, k = [int(e) for e in input().split()]
divisor = 10 ** 9 + 7
cache = {}
def memoize(f):
    global cache
    def _(*args):
        if not args in cache:
            cache[args] = f(*args)
        return cache[args]
    return _
@memoize
def f(n, x):
  if n == 0:
    return 1
  elif n == 1:
    return x
  elif x == 1:
    return 1
  elif x == 2:
    return n + 1
  elif x == 3:
    return (n + 1) * (n + 2) // 2
  else:
    return sum(f(i, x - 1) for i in range(n + 1)) % divisor
for i in range(1, k + 1):
  print(f(k - i, i) * f(n - k - i + 1, i + 1) % divisor)

ABC131D - Megalomania

締め切り時間でソートして、順番に制限時間を超過しないか確認していくだけ. かんたんすぎる感じで、D 問題って難易度に波があるなあという感想.

import sys
from functools import cmp_to_key
n = int(input())
data = [[int(j) for j in input().split()] for i in range(n)]
t = 0
data.sort(key = cmp_to_key(lambda x, y: x[1] - y[1]))
for d in data:
  t += d[0]
  if t > d[1]:
    print('No')
    sys.exit()
print('Yes')

ABC130D - Enough Array

素直に書き下ろしてみたが、予想通り TLE が出た. ウインドウをずらしながら計算するのって20年近く前に大学で習ったよなあと書き直したら通った. 要するに A[i..j] で初めて K を越えたなら A[i+1...j-1] は絶対 K 未満なので、この区間をチェックするだけ無駄なのだ. なので ai+1 を先頭とする部分列は、A[i+1..j] からチェックを開始すれば良い.

n, k = [int(e) for e in input().split()]
data = [int(e) for e in input().split()]
result = 0
i = 0
j = 0
v = 0
while True:
  v += data[j]
  if v < k:
    j += 1
  else:
    result += len(data) - j
    v -= data[i]
    if j > i:
      v -= data[j]
    i += 1
    if j < i:
      j += 1
  if j == len(data):
    print(result)
    break

Pythonで正規表現を使ってファイル名の末尾が.jpgかどうかをチェックするスクリプトを書いてみました。
Pythonでは正規表現中のエスケープシーケンスは[]を使います。

サンプル

script.py

import re

# ファイル名の末尾が.jpgもしくは.JPGとなっているかチェック
def is_jpg(file_name):
    result = re.match(r'.*[.]jpg', file_name, flags=re.IGNORECASE)
    print(result)
    if result is not None:
        print('matched')
    else:
        print('None. unmatched')


t1 = 'aaaa.jpg'
t2 = 'bbb.JPG'
t3 = 'ccc.jpg.'
t4 = 'ddd.JPG.'
t5 = 'aaaajpg'
t6 = 'JPGbbbb'

print('----')
print(t1)
is_jpg(t1)

print('----')
print(t2)
is_jpg(t2)

print('----')
print(t3)
is_jpg(t3)

print('----')
print(t4)
is_jpg(t4)

print('----')
print(t5)
is_jpg(t5)

print('----')
print(t6)
is_jpg(t6)

実行結果

$ python3 script.py
----
aaaa.jpg
<re.Match object; span=(0, 8), match='aaaa.jpg'>
matched
----
bbb.JPG
<re.Match object; span=(0, 7), match='bbb.JPG'>
matched
----
ccc.jpg.
<re.Match object; span=(0, 7), match='ccc.jpg'>
matched
----
ddd.JPG.
<re.Match object; span=(0, 7), match='ddd.JPG'>
matched
----
aaaajpg
None
None. unmatched
----
JPGbbbb
None
None. unmatched

個人的に、共有用のJupyterで出力したHTMLとか含め、Pandasで長いテーブルを表示する時があります。

そういった場合に、エクセルなどのようにカラム名のヘッダー部分を固定表示して、スクロールしてもどのカラムなのかが分かりやすいようにしたり・・・といったことがJupyterだとやり方がよく分かりません（Pandas関係とJupyter関係を軽く調べたくらいなのでもしかしたらもっと調べればあるのかもしれませんが・・・）。

そのため、2時間くらいあればPyPI登録まで含め終わるでしょ・・・という印象だったため、自分でライトなライブラリを書いてみました（Github）。

データフレームから生成されたテーブルの、対象のセルにマウスオーバーするとインデックスとカラムの情報をツールチップで表示してくれます。

これで縦横に長いデータフレームでも安心

インストール方法

pipでインストールができます。

$ pip install pandastabletooltip

使い方

インターフェイスは1つの関数だけで、データフレームを放り込むだけです。

from pandastabletooltip import make_table_html_with_tooltip
import pandas as pd

df = pd.DataFrame(data=[{
    'a': 100,
    'b': 200,
    'c': 300,
}, {
    'a': 1000,
    'b': 2000,
    'c': 3000,
}, {
    'a': 10000,
    'b': 20000,
    'c': 30000,
}])

make_table_html_with_tooltip(df=df)

息抜きにこういったライトなプログラミングもいいですね

Sesameとは

2018年末時点で世界５万台を売り上げているスマートロックのIotデバイスでCANDY HOUSEが開発、販売をしているプロダクト。

CANDY HOUSEについて: https://jp.candyhouse.co/
このプロダクトのすごいところは、他のスマートロックとは異なりWebAPIを提供しているので、自作プログラムからSesameを動かすことができる。

SesameのWebAPIを使ってみる

まず、SesamiのWebAPIを使う条件　参考(https://ameblo.jp/candyhouse-inc/entry-12352517694.html)
①自身がオーナーであるSesame本体
②SesamiがペアリングされているWiFiアクセスポイント
③インターネット接続のあるPC
※①の補足
Sesameへの登録は、
・オーナー
・マネージャー
・ゲスト
の３種類あり、オーナーにならないとAPIキーの発行が出来ない。また、オーナー登録は１人のユーザーしか出来ない。
(WiFIアクセスポイントも同様に１人しか登録出来ないようなので注意)

プログラムからSesameを動かすまでの流れ(今回はpython)

①Sesameのスマホアプリで、Sesameスマートロックの登録とWiFiアクセスポイントの登録(それぞれ別で設定して、最後のこの２つをペアリングする)
Sesameスマートロック の登録 参考(https://ameblo.jp/candyhouse-inc/entry-12343105491.html)
WiFiアクセスポイントの設定 参考(https://ameblo.jp/candyhouse-inc/entry-12332339299.html)

②Sesamiスマホアプリでの、ドアの解錠ボタンがある画面左下の'管理'ボタンから画面遷移し、「セサミの管理」に移動。そして、連携-クラウドの部分をアクティブにする。これをしないと、エラーが返ってくる。

③APIキーの発行
開発者用のWebページから行う。
サイト(https://my.candyhouse.co/#/distribution/0)
'Sesame List'に自分がオーナー権限を持っているSesameがあるかを確認し、APISettingsの画面で、APIKeyを発行。
④Sesame WebAPIのリファレンスを参考にAPIキーの認証状態を確認する

curl -H "Authorization: YOUR_AUTH_TOKEN" \ 
https://api.candyhouse.co/public/sesames

→https通信を許可するSSL照明の期限が切れているとSSLエラーが返ってくるので注意
その場合はこっちのコマンドで対応(本来は、証明書の再発行が必要)

curl --insecure -H  "Authorization: YOUR_AUTH_TOKEN" https://api.candyhouse.co/public/sesames

APIキーの使用承認が降りていると、登録しているSesameの情報が返ってくる。
ここまできたら下準備完了

⑤pythonのデモプログラムを起動
https://github.com/yagami-cerberus/pysesame2
基本的にpysesami2のライブラリを使えば、同期、非同期の任意の方法でSesameを動かせるようになる。

サンプルその１

鍵が閉まっていたら開けて、開いていたら閉じる

from uuid import UUID
import time
from pysesame2 import Sesame

def main():
    device_id = UUID('DEVICEID')
    sesame = Sesame(device_id, 'APIKEY')
    if sesame.get_status()['responsive'] == True:
        if sesame.get_status()['locked'] == True:
            task = sesame.async_unlock()
        else:
            task = sesame.async_lock()
        while task.pooling() is False:
            print('SesameProcessing...')
            time.sleep(1)
        print('SesameResult: {}'.format(task.is_successful))
    else:
        print('Sesame can not be found')

if __name__=='__main__':
    main()

サンプルその２

__鍵が閉じていたら開けて、3秒たったら閉める。

from uuid import UUID
import time
from pysesame2 import Sesame

def sesameOpen():
    device_id = UUID('DEVICEID')
    sesame = Sesame(device_id, 'APIKEY')
    if sesame.get_status()['responsive'] is True:
        if sesame.get_status()['locked'] is True:
            task = sesame.async_unlock()
            while task.pooling() is False:
                print("\033[32m{}\033[0m".format('SesameProcessing...'))
                time.sleep(1)
            print("\033[32mSesameResult: {}\033[0m".format(task.is_successful))
            ssm_cls=threading.Timer(3, sesameClose, args=[sesame])
            ssm_cls.start()
        else:
            print('Sesame is unlocked')
    else:
        print('Sesame can not be found')

def sesameClose(sesame):
    task = sesame.async_lock()
    print("\033[35m{}\033[0m".format('Called Sesame locked'))

if __name__=='__main__':
    sesameOpen()

その他参考サイト

Qiita: https://qiita.com/kt-sz/items/e8ccec02605584e62b53
APIリファレンス: https://docs.candyhouse.co/#introduction