天色グラフィティ

機械学習やプログラミングでいろいろ作って遊ぶブログ

Golangでどうでもいい知識を教えてくれるCLIツールを作った

Golang

f:id:ejinote:20181006195046p:plain

最近ghqの作者@motemenさんのインタビューや pecoの作者@lestrratさんのインタビューを読んでいてCLIツールを作りたい欲がむらむらと湧いていました。

@motemenさんのインタビューによると、普段から「これ不便だな。ツールにならないかな」とアンテナを貼っていることがツール作成においては大事だそうです。これを読んで僕もアンテナ高くしようと思った次第なのですが、思ってすぐに役に立つツールのアイデアが湧いてきたら苦労しないわけでして。

今回はCLIツールを作る練習として、「そんなに役には立たないけど、面白い」みたいなツールを作ってみました。 成果物はこちらです。

github.com

trivia コマンドを打つとWikipediaからランダムに単語を引っ張ってきて説明をしてくれます。日本語版Wikipediaを検索してるのにカウ高校とパハラ小学校(ハワイの学校)とか出てきて結構面白いです。

使う言語は勉強も兼ねてGolangを選択しました。 go get で簡単にインストールできるので配布もしやすいですし、何より書いててちょっと楽しいです。

インストールは

$ go get -u github.com/amaotone/trivia

でOKです。デフォルトの言語設定が(ちょっとイキった結果)英語になっているので、

$ trivia set -l ja

で日本語に変えて

$ trivia

でどうでもいい知識を教えてくれます。

続きを読む

KaggleのHome Creditコンペで銀メダルを取った話と、チームで動く際のノウハウとか

Kaggle データ解析

書く書くといっておきながらなかなか書かないでいたらGoogle Analyticsコンペが始まってしまいました。慌ててこの参戦記を書いています。

Home Credit Default Riskコンペに参加し、166位で銀メダルを取りました！

僕は同じ研究室の@sugawarya、東大松尾研のみなさまとチームを組んで参戦しました。

f:id:ejinote:20180917002544p:plain

僕は2枚めの銀メダルを獲得し、Kaggle Masterまであと金メダル1枚というところに来ました。就職するまでにKaggle Masterになっていたいものです。

さて、ここからコンペの振り返りをしていくのですが、ありがたいことにKaggle始めたての方も多少見てくださっているようですので、少し丁寧に書こうと思います。また、今回はじめての大きなチーム戦で試行錯誤したので、チームで進める際にこんなことをするといいんじゃないかなーと思うことも最後に書きました。

  • コンペ概要
  • 僕(たち)がやったこと
    • 前処理
    • 特徴量作成
    • モデル
    • アンサンブル
  • 上位の解法まとめ
    • 特徴量
    • モデル
    • アンサンブル
    • その他面白かった解法
    • 反省まとめ
  • チームでの動き方
    • 目的を共有する
    • 情報を共有する
    • 役割を分担する
  • まとめと感想

コンペ概要

Home Credit Default RiskコンペはKaggleで行われたコンペのひとつです。 Home Credit社は、信用の積み重ねが足りずに融資を受けることができない顧客にも融資を行う会社で、今回のコンペは債務不履行(デフォルト, default)になる顧客を予測する、というものです。

与えられたデータは、

  • application_train/test
    • それぞれの行が融資の申込みを表し、それが不履行になるかどうかを予測するのが今回のタスク
  • bureau
    • Home Credit社以外のクレジットビューローでの融資情報
  • bureau balance
    • bureauの負債残高の履歴
  • previous applications
    • Home Credit社における過去の融資情報
  • installment payments
    • 過去の融資の残高履歴
  • credit card balance
    • Home Credit社のカードの残高履歴
  • POS cash balance
    • Home Credit社の店頭融資の残高履歴

など、多数のファイルに分けて与えられています。

applicationの1行に対しbureauやpreviousなどのサブファイルが複数行対応付けられているため、サブファイルの情報をどうやって抽出するかがキモとなったコンペと言えるでしょう。

続きを読む

Kaggleで使えるFeather形式を利用した特徴量管理法

データ解析 Kaggle Python

みなさま、Kaggle楽しんでいますでしょうか。 僕は現在Home Credit Default RiskとSantander Value Prediction Challengeに参加しています。

前回のKaggle記事ではpandasのテクニックについてまとめました。 多くのアクセスをいただき、人生初のホッテントリ入りまで経験してたいそう嬉しかったです。ありがとうございました！

amalog.hateblo.jp

さて。みなさんはKaggleをやっているとき、どのようにして特徴量を管理していますか？

Titanicくらいならその都度計算すれば十分ですが、 ある程度データのサイズが大きくなり、さまざまな特徴量を取捨選択するようになると特徴量のシリアライズ(保存)が欠かせません。

そこで、今回は僕が行っている特徴量管理方法を紹介したいと思います。 僕の方法はTalkingdata Adtracking Fraud Detectionコンペの1位、flowlightさんのリポジトリを参考にしています。

概要

主要なポイントをまとめると以下のとおりです。

目次

  • 概要
  • 目次
  • Feather形式でのシリアライズ
  • 基底クラスの実装
    • timer()
    • Featureクラス
  • argparseを利用したコマンドラインツール化
    • get_arguments()
    • get_features()
    • generate_features()
  • 利用例
  • 特徴量の読み込み
  • まとめ
続きを読む

ARC100に参加した(510位)

競プロ

f:id:ejinote:20180705221406p:plain

ARC100に参加しました。結果は510位で、レートは1429→1427と微減しました。

問題としてはC問題を1WAしながらACし、D問題が解けませんでした。久しぶりにDで手こずった気がします。

今回から、解けなかった問題については典型要素の抽出をやってみたいと思います。

前回の記事：

amalog.hateblo.jp

振り返り

C - Linear Approximation

数列 Aと整数 bについて \sum_{i} | A_{i} - (b - i) |の最小値を求める問題。

予め数列から iを引いておけば、あとはL1ノルムを最小化する代表値(=中央値)を bに設定すればよい。

思いつくためには、横軸 i、縦軸 A_{i}-iのプロットを書いてみるとよい。横線を一本引いたときに、その横線より上に来てる点と下に来てる点が同じ数のところが最善であることに気がつくはず。

#!/usr/bin/env python
N = int(input())
A = list(map(int, input().split()))
A = sorted([a-(i+1) for i, a in enumerate(A)])
m = A[N//2]
ans = 0
for a in A:
    ans += abs(a-m)
print(ans)

D - Equal Cut

数列を4つに分けて、それぞれの和の最大と最小の差を最小化する問題。

端から貪欲でやるのはNG。たとえば1, 1, 1, 1, 10000とかのとき、1つの部分の合計は理想的には合計/4=2501だけど、2501になるように貪欲でとっていくと4つに分けられない。

解法は以下の通り。

  1. まず2つに分け終わったとする
  2. それぞれの部分については、理想的な分割箇所(=2つの合計ができるだけ近くなるとこ)は一意に定まる
  3. なので、最初の分割点を全探索して、それぞれの部分は理想的な分割にすれば、トータルの理想的な分割も定まるはず
  4. ちなみに、最初の分割点を右にずらすと、2段階目の分割点はそれぞれ変わらないor右にずれるのいずれかになるので、探索を減らせる

こんな感じ。これはできてもよかったな……

典型要素としては、

  • 区間の累積和は予め全体の累積和を取っておけば差を利用することで O(1)で求まる
  • 「ここさえ探索すればあとは一意に定まる」みたいな感じで探索すべき場合の数を減らす

ってなところか。

#!/usr/bin/env python
from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
Acum = list(accumulate([0] + A))

def cumsum(left, right):
    # [i, j)
    return Acum[right] - Acum[left]

def find_best_cut(left, right, prev):
    prev = max(prev, left+1)
    now = prev
    res = now
    best = abs(cumsum(left, prev) - cumsum(prev, right))
    while True:
        now += 1
        score = abs(cumsum(left, now) - cumsum(now, right))
        if score < best:
            best = score
            res = now
        else:
            return res

left = 0
right = 0
best = float('inf')
for center in range(1, N-1):
    left = find_best_cut(0, center, left)
    right = find_best_cut(center, N, right)
        
    t = [cumsum(0, left), cumsum(left, center), cumsum(center, right), cumsum(right, N)]
    score = max(t) - min(t)
    if score < best:
        best = score
    
print(best)

気づいたこと

D問題まではPythonで書いて、E以降はC++で書こうと思っていたけど、E問題が解ける頻度はまだ少ないからC++で書く練習がなかなか積めないという問題点に気づいた。

ARC099に参加した(210位)

競プロ

f:id:ejinote:20180624151041p:plain

ARC099に参加しました。210位でレートは1304→1429になりました。 久しぶりのコンテスト参加で緊張しましたが、Dをそれなりに早く解いたのがよかったっぽいです。

そういえば先日書いた記事がホッテントリに載りました。結構うれしいものですね。

amalog.hateblo.jp

振り返り

C - Minimization

  • 最小値が1なので、全要素を1にすればよい
  • 1回適用すると1がK-1個増える

1を中心に左右に1を広げていくイメージで解きました。1の左右それぞれについて端から最適な回数で処理をして、1の周りの余りはよしなにやる感じ。

import math
n, k = map(int, input().split())
A = list(map(int ,input().split()))
print(math.ceil((n-k)/(k-1)+1))

D - Snuke Numbers

手で書いても全く分からなかったので実験しました。

import matplotlib.pyplot as plt
%matplotlib inline

def digit_sum(i):
    return sum(map(int, list(str(i))))

scores = [i/digit_sum(i) for i in range(1, 50000)]
plt.figure(figsize=(10, 5))
plt.scatter(list(range(1, 50000)), scores, s=1)
plt.show()

f:id:ejinote:20180625171837p:plain

規則性があることがわかります。ちなみにスコアがジャンプするのは繰り上がりが起きるときなので、XXX999みたいな数にだけ着目すればよいと分かります。

XXX999みたいな数それぞれについて、次のやつとの比較を行って、だめだったら消せば良いと思います。

実装は鬼汚いです。

def digit_sum(i):
    return sum(map(int, list(str(i))))

def score(head, tail):
    return num(head, tail)/digit_sum(num(head, tail))

def num(head, tail):
    return int(str(head)+tail)

k = int(input())
tail = ''
head = 0
cnt = 0
last = 0
while True:
    head += 1
    if score(head, tail) <= score(head+1, tail):
        if num(head, tail) > last:
            print(str(head)+tail)
            last = num(head, tail)
            cnt += 1
            if cnt == k:
                break
    else:
        head = 0
        tail += '9'

E - Independence

  • 辺をできるだけ少なく切断して2つのクリーク(部分グラフがすべて完全なグラフ)に分割すればよい
  • 補グラフを取ると少し見通しが良くなって、補グラフにできるだけたくさん辺を足して完全二部グラフにする問題に変換することができる
  • 補グラフをとった時点で二部グラフでなければ達成不可能。
  • 辺はいくつでも足していいので、補グラフを連結成分分解して成分の集合を2つにまとめて完全二部グラフにすることができる。
  • クリークの辺の数は頂点数で決まり、辺を多くするなら頂点を多くすれば良い。ただ、頂点集合が2つあるので、2つをできるだけ同じサイズにすればよい。
  • うまいまとめかたを探すためにDP

みたいな感じで解けると思います。僕は実装が間に合いませんでした。

感想

Dが早く解けたのでレートもあがり万々歳です。たのしいですね。

そろそろ証明からは逃れられなそうなので、普段から軽く証明することは意識したいと思います。

Kaggleで使えるpandasテクニック集

Python データ解析 Kaggle

f:id:ejinote:20190112195735j:plain

PythonでKaggleなどのデータ分析を行う際、pandasでゴリゴリ作業をすることが多いかと思います。

最近知って「めっちゃ便利やん！」ってなったものをまとめておきたいと思います。 全部の関数にドキュメントへのリンクを付けたので参考にしてください。

今回も検証にはTitanicのデータセットを用います。また、文中でのdf.hoge()はpandasのDataFrameのメソッドであることを、pd.hoge()はpandasの関数であることを表します。

df = read_csv('input/train.csv', index_col=0)
print(df.shape)
df.head()

f:id:ejinote:20180530220813p:plain

続きを読む

ARC098に参加しました (726位)

競プロ

f:id:ejinote:20180527175257p:plain

ARC098に参加しました。C問題を1回TLEしてD問題が解けず無事死亡しました。 レートは1334→1298ということで、微減ですね。 D問題が解けなかったのは久しぶりなので練習不足を感じます。 最近Kaggleが忙しくて過去問埋めもあまりできていません。

前回の記事

amalog.hateblo.jp

続きを読む