AtCoder Beginner Contest 120をPythonで解く
A - Favorite Sound（100点）
- 満足する回数Cを無視すると、答えは(B//A)
- この数よりCが小さければ、答えはC
A, B, C = list(map(int, input().split())) ans = min((B//A), C) print(ans)
B - K-th Common Divisor（200点）
- K番目に「大きい」ことに注意
A, B, K = list(map(int, input().split())) ans = [] for i in range(1, min(A, B) + 1): if (A%i==0) and (B%i==0): ans.append(i) print(ans[-K])
C - Unification（300点）
- 少し考えると0と1が可能な限り打ち消し合うと分かる
S = input() num_0 = S.count('0') num_1 = S.count('1') print(min(num_0, num_1)*2)
D - Decayed Bridges（400点）
- Union Find Treeの拡張
class UnionFindTree(): def __init__(self, N): self.parent = [-1]*(N+1) self.rank = [1]*(N+1) self.size = [1]*(N+1) self.hubensa = N*(N-1)//2 def find(self, i): if self.parent[i] == -1: group = i else: group = self.find(self.parent[i]) self.parent[i] = group return group def unite(self, x, y): px = self.find(x) py = self.find(y) if px != py: if self.rank[px] == self.rank[py]: # rank is same self.rank[px] += 1 elif self.rank[px] < self.rank[py]: px, py = py, px self.parent[py] = px self.hubensa -= self.size[px] * self.size[py] self.size[px] += self.size[py] N, M = list(map(int, input().split())) A = [0 for _ in range(M)] B = [0 for _ in range(M)] for i in range(M): A[i], B[i] = list(map(int, input().split())) ans = [] UFT = UnionFindTree(N) # 後ろから処理 for i in range(M-1, -1, -1): ans.append(UFT.hubensa) UFT.unite(A[i], B[i]) print(*ans[::-1], sep="\n")
ABC015「C - 高橋くんのバグ探し」をPythonで解く
ABC014「C - 高橋くんのバグ探し」をPythonで解いた。
愚直に全通りをfor文で回す解答もあるが、競技プログラミングをPythonで解く上で、より汎用的な解法に落とし込めたので、まとめておく。
解答
import itertools from functools import reduce from operator import xor N, K = list(map(int, input().split())) T = [] for i in range(N): T.append(list(map(int, input().split()))) ans = 'Nothing' for pr in list(itertools.product(*T)): if not (reduce(xor, pr)): ans = 'Found' print(ans)
解説
- 何かと便利な itertools を使って全通りを列挙
- 今回興味があるのは組み合わせ一つに対応する真偽値なので reduce を使う
itertools
- 直積を計算してくれる itertools.product() を使う
- 多重リストの前に * を付けるとアンパックされる
print(T) print(*T)
[[1, 3, 5, 17], [2, 4, 2, 3], [1, 3, 2, 9]] [1, 3, 5, 17] [2, 4, 2, 3] [1, 3, 2, 9]
reduce
- reduceの第一引数に入れる演算子は、下記のdocumentationで調べた。
- docs.python.org
「Sports Analyst Meetup #1 」を開催＆発表しました #spoana
はじめに
「Sports Analyst Meetup #1」を昨日2月24日に開催しました。多くの方に「楽しかった」と言っていただき、運営冥利につきます。僕自身も非常に楽しいイベントでした。
開催の背景
私は同日別イベントでプレゼンしていたので参加できなかった「Japan.R」が、本イベント開催の契機になりました。
個人的にデータ分析・スポーツの両者は昔から興味があり、ぜひお手伝いしたいと考えて、運営メンバに加えていただきました。
当日の発表内容
私が担当した「初心者向けスポーツ分析チュートリアル」と、12人の方によるLTの構成でした。
LT
現時点で公開されている資料は、下記でご覧いただけます。
お品書きは、以下の通りです。どの発表もクオリティが高く、大満足でした。
| 競技名 | LTタイトル |
|---|---|
| F1 | なんちゃってF1ラップタイム分析 |
| サッカー | トラのアナ |
| 登山 | 登山って、つらくない？ ～標高とコースタイムから見るつらみ～ |
| 自転車 | 自転車競技におけるデータドリブンなアプローチ手法と実例 |
| サッカー | 優勝予測からサッカーW杯・アジアカップを振り返る |
| 野球 | よくわかる「フラレボ」 |
| 野球 | 大◯半端ないって！ |
| サッカー | 「アナリスト」が日本のサッカーを変える、のか︎ |
| バスケ | バスケットボールにおける選手の評価指標 |
| ゴルフ | はっは～ん、こうやってゴルフボールは飛ぶのか。と知ったかぶるためのLT |
| テニス | Tennis Analysis with R |
| フィギュアスケート | フィギュアスケートの◯を◯で判定してみた！ |
閉会後も・・・
バスケのLTの最後に「本日23時半から、バスケ日本代表のW杯をかけた戦いがあります！」という熱い宣伝がありました。
本日の #spoana でも話題に上がりましたが、バスケ日本代表のW杯をかけた戦いが11時半からです！！ https://t.co/PfvvwQd1Sv
— u++ (@upura0) February 24, 2019
バスケ日本代表の試合見るの初めてかもしれん #spoana pic.twitter.com/lV1DYRq9Em
— u++ (@upura0) February 24, 2019
私含めた参加者の方々がこの試合を観戦して盛り上がっている様子がTwitterで観測できました。私自身、これまでバスケの試合を真面目に見たことはなかったのですが、本イベントを契機に様々な競技の魅力に気づきました。本イベントの狙いの一つが達成できたようで、非常に嬉しく感じています。
AtCoder Beginner Contest 119をPythonで解く
「AtCoder Beginner Contest 119」に出て、3完でした。
C問題の実装に苦しみ、時間をほぼ使ってクソコードで通しました。
B - Digital Gifts（200点）
- 一つずつ、条件分岐して足し上げる
- [float, str]という入力列が来るので、取りあえず両方strで受け取って、計算時にfloatに戻してあげる
N = int(input()) A = [] for i in range(N): A.append(list(input().split())) ans = 0 for a in A: if a[1] == 'JPY': ans += float(a[0]) else: ans += float(a[0]) * 380000.0 print(ans)
C - Synthetic Kadomatsu（300点）
- 愚直に要件通りに実装する
- 1回目の提出で最後のテストケースだけREになったので、恐らくエラーの発生した箇所を特定し、try~exceptも使ったクソコード
import itertools import numpy as np import copy ansl = [] N, A, B, C = list(map(int, input().split())) a = [] for i in range(N): a.append(int(input())) def get_ptn(la): ptn = [] for i in range(1, len(la) + 1): ptn.append(list(itertools.combinations(la, i))) return ptn takes = list(itertools.permutations([A, B, C])) for take in takes: try: ta = copy.deepcopy(a) ans = 0 for k in range(3): ptn = get_ptn(ta) cost = [] tmp = [] for i in range(len(ptn)): tmp.append([abs(take[k] - sum(j)) for j in ptn[i]]) cost.append(min(tmp[i]) + 10 * i) ans += min(cost) ac = np.argmin(cost) at = np.argmin(tmp[ac]) for _ in ptn[ac][at]: ta.remove(_) ansl.append(ans) except: pass print(min(ansl))
Kaggleにおける「特徴量エンジニアリング」の位置づけ 〜『機械学習のための特徴量エンジニアリング』に寄せて〜
はじめに
このたび、『機械学習のための特徴量エンジニアリング』をご恵贈いただきました。
Kaggleと親和性が高い書籍名で、Twitterのタイムラインなどを見るに、Kaggleに興味がある層を中心に大きな注目を集めているようです。
本記事では本書の発売に寄せて、Kaggleの自分流のワークフローと「特徴量エンジニアリング」の位置づけについての私見を述べます。その上で本書がKaggleのワークフローのどの部分に寄与するかを説明します。最後に、Kaggle観点で本書をどういう方にオススメするかに触れて本記事を締めくくります。
なお下記の記事では、本書のより包括的なレビューが掲載されています。
『機械学習のための特徴量エンジニアリング』の書誌情報
- Alice Zheng (著), Amanda Casari (著), 株式会社ホクソエム (翻訳)
- 出版社: オライリージャパン
- 言語: 日本語
- 発売日: 2019/2/23
- 2018/4/14に発売された "Feature Engineering for Machine Learning" の日本語訳版
- サンプルコードはGitHubで公開されている
Kaggleのワークフロー
以下は、私が考えるKaggleのワークフローです。便宜上「Kaggleの」としていますが、より広義に「機械学習コンペティションの」と置き換えても良いと考えています。
- （探索的データ分析）
- ベースラインモデルの構築
- Validationの構築
- 特徴量エンジニアリング
- ハイパーパラメータ調整
- アンサンブル
このワークフローは、自分で何度かKaggleのコンペに参加する中で、感覚的につかみ始めたものでした。
本記事で言語化するに当たっては、2019年1月末にパリで開催された「Kaggle Days Paris」でのCPMPさんの発表を参考にしています。ワークフローの項目は同様ですが、個人的に探索的データ分析はKaggleの序盤においては必ずしも優先順位が高くないと考えており、括弧を付与しました。
CPMPさんの発表資料はこちらで閲覧できます。
1. （探索的データ分析）
探索的データ分析とは、コンペの課題設定を踏まえて与えられたデータを分析することです。
Kaggleの文脈においては、単に「各特徴の分布や欠損値の有無などを確認する」というより「データに隠された傾向をあばき、新しい特徴量につながる気付きを得る」という意味合いが大きいと思います。
探索的データ分析は他者との差異を生み出す上で非常に重要なことですが、一方で時間制約のある中での優先順位として思考停止で多くの特徴量を生成する方がスコア向上の期待値が高いという考え方もあります。
個人的なワークフローとしては、Voteが多い*1探索的データ分析のKernelを読む*2ことで取りあえずのデータ把握を終えて、次の「2. ベースラインモデルの構築」へ移ることが多いです。「4. 特徴量エンジニアリング」のアイディアが尽きた際に、単なるデータ把握の意味合いを超えた探索的データ分析に取り組むような優先順位を意識しています。
kaggler-ja-wikiの「よくある質問 > EDA(Exploratory Data Analysis - 可視化してデータを見ること)って何のためにやるの？」辺りも、興味があればご参照ください。
2. ベースラインモデルの構築
ベースラインモデルは「最初に与えられたデータを基に作成した、エラーなく提出してスコアが算出されるモデル」くらいの意です。
いわゆるデータの「前処理」にも相当する部分で、与えられたデータを機械学習モデルが扱える形式に最低限整えていきます。テーブルデータを扱うコンペの場合、学習器には欠損値をそのまま扱えるLightGBMを用いることが多いです。
ベースラインモデルの構築は、長期間取り組むコンペの中で再現性を保つ上で大切だと考えています。コンペが進む中でたくさんのコードを書くことになりますが「ベースラインモデルを徐々に補強していく」という視点を持つことで、差分や進捗の管理がしやすくなると思っています。
ちなみに、前処理については『前処理大全』という書籍が昨年発売されています。『機械学習のための特徴量エンジニアリング』の翻訳を担当した株式会社ホクソエムの監修です。
3. Validationの構築
取りあえず提出できるベースラインモデルを作成した後は、Validationの構築に移ります。
目的は「4. 特徴量エンジニアリング」に先立っての準備です。Validationの構築を疎かにしていると、たとえ新しい特徴量を作っても「この特徴量が効果的なのか分からない」という事態を招いてしまいます。
世界ランキング1位のbestfittingさんも、KaggleのインタビューでValidationの重要性を強調しています。
A good CV is half of success. I won’t go to the next step if I can’t find a good way to evaluate my model.
（良いCVが得られれば、成功の道半ばに到達したと言える。私は、モデルの良い評価方法が得られるまで、次のステップへ進まない）
Validationの構築は非常に難易度の高いタスクです。データや問題設定に依存する部分が大きく、また真に良いValidationが得られたかはコンペが終わるまで誰にも分かりません。
現実的には、discussionで他人の状況を確認*3しながら「4. 特徴量エンジニアリング」に遷移していくことになるかと思います。
Validationの構築が重要な理由については、下記の記事でも説明しています。
4. 特徴量エンジニアリング
Validationの構築後、いよいよ特徴量エンジニアリングに取り組みます。
CPMPさんは、大きく分けて2種類の特徴量エンジニアリングを紹介しています。
- 一般的に効果があるとされる特徴量エンジニアリング
- ドメイン知識に紐づく特徴量エンジニアリング
以降は私の解釈ですが、Kaggleコンペにおいて前者は「守り」、後者は「攻め」に分類できると思います。
この「攻め」「守り」という考え方は、まますさんが以前に呟いていたの見て気に入った表現です。
テーブルコンペ、何というか技術は全部守備みたいなところある(伝われ)
— まます (@mamas16k) February 8, 2019
前者の「守り」については、コンペの問題設定にあまり依存せず、一般的に効果が知られている技術が該当します。具体的には、カテゴリ変数のエンコードなど、コンペを問わず頻繁に登場するような技術です。
これらは、ある程度力を入れてKaggleに取り組んでいる人は過去のコードを使い回すなどで、ほぼ確実に試している特徴量エンジニアリングになります。その意味で、スコアを争う上で一人だけ遅れを取らないために取り組む「守り」の技術と称しています。
ただしこれまで、あまり日本語で読める体系的な書籍は私の観測する限りありませんでした*4。
いろいろなコンペに参加してKernelやWinner Solutionなどを読みながら「守り」の技術を磨いてきたのですが、今回『機械学習のための特徴量エンジニアリング』が発売されることで、この部分の習得がしやすくなるのではないかと期待しています。
後者の「攻め」については、コンペの問題設定の中で独自に有用な特徴量エンジニアリングです。CPMPの資料に記載されている具体例としては、例えば「TalkingData AdTracking Fraud Detection Challenge」コンペの話題がありました。
このようにドメイン知識に紐付いた考察で、汎用的に知られていない新しい特徴量を作っていくのが「攻め」の特徴量エンジニアリングです。
5. ハイパーパラメータ調整
ハイパーパラメータ調整は「3. Validationの構築」や「4. 特徴量エンジニアリング」に一定の区切りが付いた後など、コンペを通じて数回程度実施するような認識を持っています。
ここで強調したいのは、ハイパーパラメータ調整はあくまで「最後の一押し」という点です。スコアの上がり幅は、効果的な新しい特徴量を発見した方が一般的に大きいです。
個人的な戦略としては、まずは別のコンペで使った実績のある良さげなハイパーパラメータで固定して特徴量エンジニアリングを実施していき、最後の一押しとしてハイパーパラメータを調整しています。
6. アンサンブル
アンサンブルは、複数のモデルの予測を組み合わせて、全体の予測とする手法です。モデルの多様性を得ることで、未知のテストデータへの汎化性能を高める効果があります。
ここで強調したいのは「コンペ序盤でのアンサンブルは避けるべき」という点です。スコアが上がるので満足度は得やすいのですが、アンサンブルの効果を高めるためにも、コンペ終盤になるまでは多様な特徴量を作成する方面で努力すべきだと思います。
本筋から外れるため、アンサンブルの具体的な方法については、下記の記事に譲ります。
『機械学習のための特徴量エンジニアリング』の貢献箇所
ここまで長々と、自己流のKaggleのワークフローについて述べました。
- （探索的データ分析）
- ベースラインモデルの構築
- Validationの構築
- 特徴量エンジニアリング
- ハイパーパラメータ調整
- アンサンブル
『機械学習のための特徴量エンジニアリング』が最も貢献する箇所は、「4. 特徴量エンジニアリング」の中の「守り」の部分です。 一般的に効果があるとされる特徴量エンジニアリングを体系的に学ぶことができる点で、日本語の書籍として非常に素晴らしいと感じています。
さらに「守り」を一定レベルまで習得しておくことは「攻め」の特徴量エンジニアリングにも繫がるでしょう。「守り」の技術で一定の質が担保されているからこそ、腰を据えて積極的に「攻め」の挑戦ができると考えています。
Kaggle観点で本書をオススメする読者
繰り返しになりますが、特徴量エンジニアリングはKaggleのワークフローの流れの中で真価を発揮します。
本書は、自分の力で「1. （探索的データ分析）」「2. ベースラインモデルの構築」「3. Validationの構築」までをある程度やり切ることができる方にとって、自分の「守り」の技術を高めるのに大いに役立つ一冊になると思います。言い換えると、ある程度は力のある方が、「攻め」の特徴量エンジニアリングをして金メダル争いをしていくための下支えになるような書籍だと感じました。
冒頭で紹介したばんくしさんの記事で「Kaggle Expertくらいの人は買えば」とありました。私の説明も、細かい部分から議論していった結果として、似たようなところに落ち着いた印象があります。
自分自身は現状、本書のズバリ対象読者となるくらいの実力です（Kaggle Expert）。本書を読み進めながら、金メダル争いができるようなレベルまで精進していきたいと考えています。
おわりに
本記事では『機械学習のための特徴量エンジニアリング』の発売に寄せて、以下の3点を述べました。
- Kaggleの自分流のワークフローと「特徴量エンジニアリング」の位置づけ
- 本書がKaggleのワークフローのどの部分に寄与するか
- Kaggle観点で本書をどういう方にオススメするか
非常に長い文章になってしまいましたが、Kaggleにおける「特徴量エンジニアリング」の位置づけや、本書の購入に向けた判断材料をお伝えできていれば幸いです。
「全国統一プログラミング王決定戦」イベント＆懇親会に参加しました
本日開催された「全国統一プログラミング王決定戦」イベント＆懇親会に参加しました。
↓で出場した予選の201-500位の枠（イベント＆懇親会のみ参加可能）です。
会場は東京ドームホテル 大宴会場「天空」というとても豪勢な場所でした。
トークセッション
トークセッションは当然盛り上がる3人でした。
全国統一プログラミング王決定戦のトークセッション、満員御礼です。 pic.twitter.com/CAo0eUgpTj
— Preferred Networks JP (@PreferredNetJP) February 17, 2019
懇親会
懇親会では、強い方とお話できて刺激的でした。ネームプレートを見て声をかけてくださった方が4, 5人いて、とても嬉しかったです。
（早く水色にしたい・・・）
総じて、競プロ精進のお気持ちが高まる会でした。ありがとうございました。
ABC014「B - 価格の合計」をPythonで解く
ABC014「B - 価格の合計」をPythonで解いた。
解答
N, X = list(map(int, input().split())) a = list(map(int, input().split())) ans = 0 for i in range(N): if (X>>i)&1 == 1: ans += a[i] print(ans)
解説
- 問題文に書いてある通り、Xのk番目のビットが立っている価格を足し上げる
- 「Xのk番目のビットが立っている」という条件をどう書くかという問題
途中経過を含めて出力してみる。
N, X = list(map(int, input().split())) a = list(map(int, input().split())) ans = 0 print("===bin(X)===") print(bin(X)) print("===bin(1)===") print(bin(1)) print("===bin(X>>0)===") print(bin(X>>0)) print("===bin(X>>1)===") print(bin(X>>1)) print("===bin(X>>2)===") print(bin(X>>2)) print("===bin(X>>3)===") print(bin(X>>3)) print("===bin((X>>0)&1)===") print(bin((X>>0)&1)) for i in range(N): if (X>>i)&1 == 1: ans += a[i] print("===ans===") print(ans)
❯ python B.py 4 5 1 10 100 1000 ===bin(X)=== 0b101 ===bin(1)=== 0b1 ===bin(X>>0)=== 0b101 ===bin(X>>1)=== 0b10 ===bin(X>>2)=== 0b1 ===bin(X>>3)=== 0b0 ===bin((X>>0)&1)=== 0b1 ===ans=== 101
(X>>i)でXの桁がi個ズレていき、((X>>0)&1)の演算で、以下が返る。
- 元のXのi番目の値にビットが立っていれば1
- 元のXのi番目の値にビットが立っていれば0
競技プログラミングにおけるビット演算は下記の記事などが詳しい。
