プログラミングが少しできる人がkaggle(機械学習)を始める方法

皆さん、機械学習は好きですか？好きですよね？
ということで機械学習を楽しんでできるサイト、kaggleを始める方法を書いていきます。

前提条件

プログラミングのソースコードが割と読める(そうでないとソースが読めない可能性)
atcoder緑ぐらいのプログラミング力があると良い(競プロer間での便利な指標)

1、まずはkaggleに行って登録しよう

サイトに行ってメールアドレスとニックネームを入れて登録しましょう。
(考えるよりも動いた方が自分は楽でした)

2、環境構築

難しいことは考えずanacondaを入れましょう。
一つのパッケージみたいなもので、jupyter notebook(エディター)やpythonなど、必要なものが一通りそろいます。
これは適当に「anaconda python」とかで検索すればうまくいくと思います。
コマンドプロンプトを使ったcondaでのinstallなどを駆使するのもありです。

3、サイトを探索してチュートリアルの機械学習をやろう

kaggleのチュートリアルとして使えるものにタイタニックでの生存の推定があります。
しかし、kaggleが英語なので結構サイト内で迷子になります。competitionをクリックしてリストからtitanicを探しましょう。
最初自分はサイトに慣れるだけで体力なくなりかけました。

カテゴリーの参考(タイタニックはget started)
KaggleのCompetitions Categoriesを整理してみた - Qiita

4、他人のブログのコードをコピーしてでも理解しながら頑張ろう

anacondaからjupyterを使ってコードをテストしたら色々な方のブログを参考にしましょう。
はっきり言って機械学習の単語はどれも難しいです。
むしろコードから読み取った方が簡単なものもあり、実際に動かしながら一行一行見ていくのが良いです。
以下はタイタニックで参考にした記事です。コピーしてもエラーを吐くものがあるので注意しましょう。

しっかり動くし流れがわかるのでおすすめ(出力がindexの変更なので少し強引かも。)
【Kaggle初心者入門編】タイタニック号で生き残るのは誰？

５、4をしている間に困りそうなことへの解説(pandas,numpy)

機械学習ではpandasというpythonのライブラリを使うことになります。これは入力で渡されるcsvを読み取るのに適していたり、
行列形式のデータを簡単にDataFrame型という型などに持ち込んで見やすくしてくれます。
このデータとnumpyの行列を行き来してモデルを作ります。pythonは型が見えないのでエラーを起こしがちです。気をつけましょう。
また、ファイルの読み込み時ですが、csvファイルと作成した.jupnbの場所が同じになるようにすると、df.read_csv('test.csv')とファイルの場所を簡単に書けます。
(結構困ったけど記事がなかったので自分で書くスタイル)(この記事の存在意義)

6、House Priceもやろう

タイタニックと同じくtutorialでHouse Priceというチュートリアルがあります。
入力がとても多く、特徴量の扱いが難しいですが、これは以下のカーネルなどを参考にするとよいです。

動く。それだけでありがたい
Kaggle 日本語チュートリアル:Prediction(予測) House Prices

流れがわかってとても良い(だけど手元の環境だと動かない)
Kaggleの練習問題（Regression）を解いてKagglerになる - Qiita

7、ディープラーニングをやろう

digit recoginizerという画像認識のチュートリアルがkaggleにあります。
自分も挑戦予定です。現在多分バージョンが違って動かないので泣きそうです。

参考にしようとした記事
Kaggle Digit Recognizer Tutorial: chainer_sklearn を使ったお手軽ディープラーニング - Qiita

8、おすすめの記事

未完成ですが流れがとてもよくわかる
Kaggleに登録したら次にやること ～ これだけやれば十分闘える！Titanicの先へ行く入門 10 Kernel ～ - Qiita

9、まとめ

いかがでしたでしょうか。エラーから抜け出せなくなりがちなのでとにかくたくさんの記事を読むのが重要です。
多分ここまでやるのに一週間～二週間ぐらいかかると思います。
しかし、現在私は割と機械学習について割と知れたような気がします。よってその価値はあるのではないでしょうか。
これであなたもkagglerだ！(適当)

追記
どうやら自分の環境のpipとcondaが混ざっており、動かないコードが多かった模様です。
なので環境をどちらかに統一すればうまくいくかもしれません。

Q# 書き方メモ（多分初心者向け）

Q#初心者の自分が躓いたところを忘れないようまとめたものです。まだまだQ#の記事は少ないから少しでも役に立てればなって。ただ、エラーの表示など今後変わる可能性も多いので参考程度に。

インストール

visual studioは最新にしておく。
最新の状態でQ#standard kitインストール完了できれば大体大丈夫。
新規作成してC#の欄のところにQ#の項目がある。

量子操作における定型文

１、元から書いてあるのはoperationとbodyで、bodyの中に構造を書く。
２、using(regi = Qubit[N])で使いたい量子を配列(regi)に持ち込む。
３、letして配列の量子(regi[0])などを量子変数(A)に送り込む。
４、使った量子が一つならばletしたものをReset(A)、二つ以上ならusingした配列をResetAll(regi)する。
５、戻り値を持つならreturnしてあげればよい。

参考
量子は引数として持ち込める。

注意点
量子を用いた場合、必ずResetなどを行わないとエラーが発生する。（コメントアウトをはさむとなぜか回避できるが操作できない）

実数における定型文

１、mutableで通常の変数を扱う。
２、先ほどの変数をsetし、A = A + 1 などの操作を行う。インクリメントは実装されていない。
３、mutable変数はreturnで返すことが出来る。

注意点
毎回setをしないとmutable変数の変更が出来ない。

C#との入出力関係

１、using (var sim = new QuantumSimulator())を用いる。変数simにより起動出来る。
２、C#側から、Q#のどの関数をRunさせたいのかはっきりさせる。
３、var recived = (HelloWorld.Run(sim).Result;)とすることにより、狙った関数から戻り値を受け取れる。tupleもいける。
４、あとはC#の出力を使ってあげればいい。Console.WriteLine($"zero = { couzero} one = {couone}"); など。

注意点
変数simは引数扱いにならない
なので何かC#側から送りたいときは、C#で(sim ,10)とした場合、呼び起こした関数の部分に引数を(cou)と一つ書いてあげればよい

量子操作（最低限）

スピンの確率ベクトル変更(X-gate,Y-gate,Z-gate)
X(qub);
Y(qub);
Z(qub);

重ね合わせ状態などに使える(Hadamard-gate)
H(qub);

観測(measure)
M(qub);

量子もつれの生成(CNOT-gate)
CNOT(qub);

よく使う文法(最低限)

for in
if
else if
else
Reset
ResetAll
などの機能がある
if(M(q)==Zero)やif(M(q)==One)などとかくと0や1の状態の量子の測定が出来る

未確認操作

Qubitを返すとどうなるのかよくわからない
配列などもまだやっていない

よくやるエラー

letするときに0-indexedを忘れる
関数を作る時にbodyを忘れる（関数作ったときに起こるよくわからないエラーは大体これ）

おかしなエラー集

適当なコメントアウトを挟むと、letしたものをResetしなくてもなぜか成り立ってしまう
operation関数からoperation関数を呼び出す場合、空の場合は引数、戻り値を設定してもエラーにならないが、関数内にコメントアウトをはさむと突然エラーする

おしまい。

AtCoder緑色になるまでにやったこと

AGC026にて狙っていた早解きを決めて無事緑色になれました！(2018/7/14)

前もAGC一完で茶色になったので何か縁を感じます。(気のせい)
冗談はさておき、少しずつ精進の結果が出ている感じがしますね。よかったよかった。

緑色になるまでやったこと

実は、自分は人よりも何もかも遅れている状態であると知ったため、少しだけ手間を加えながら精進しています。
その工夫がこちら。

茶色の時の問題管理状況。今はもう少し埋まっている。

色の基準は以下の通り。

解説無しでAC→黄色
解説を読んで理解してAC→銀色
解説を読んだがほぼ理解できなかったがACした→茶色
全く歯が立たなかった→濃いピンク色

といった色分けです。これは自分が昔やっていた音ゲーなどからアイデアを借りました。結構いい感じです。
また、中央の左にある数字はその問題の点数、その右にあるのが解いた時に感じた難易度です。
そのさらに右には問題のジャンルやポイントなどを書いてあります。一応ネタバレ？になりかねないので伏せてあります。

ちなみに作り方は、atcoder problemさんの問題のページを、open officeに張り付けて作っています。
あのサイト素晴らしくて感謝しかない。

緑色になるまでに出来るようになったアルゴリズムや実装

・set,map
・string型のSTL(substr,eraseなど)
・簡単なDP
・グラフの入出力の実装
・DFS、BFS、グラフDFS、グラフBFS
・union-find
・ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法
・いもす法、累積和（ともに一次元）
・しゃくとり法
・bitの基礎
・中央値、期待値

自分はプログラミングの理解のために競プロを勉強しているので、今のところかなり学習効果が出ていると思います。競プロ素晴らしい。

これからに向けて

実は少し困っていて、D問題の精進がなかなか進まないです。
何が問題かというと、問題文、解説文がほぼ理解できないパターンがいくつか出てきました。
こうなってしまってから精進のペースがかなり落ちており、しばらくは緑色で停滞しそうです。
なので英語を勉強して、もうしばらくしたらcodeforceの方にも手を伸ばす予定です。
それまではAGCのA問題、ARCの昔のB問題などを頑張っていきたいです。
(最近Q#に手を伸ばしてて精進していないのは言ってはいけない）

グラフDFSについてのまとめ

今回はDFSのまとめです。グラフにおけるDFSではどのようなことを行えるのかまとめました。

↓今までのグラフに関する記事
（初心者向け）グラフの実装について - bplain’s blog
（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法 - bplain’s blog
（初級者競プロer向け) グラフDFS問題編 その１ - bplain’s blog
グラフDFS問題編 その２ (ABC087-D) - bplain’s blog
グラフDFS問題編 その３ (ABC075-C) - bplain’s blog

今回はまとめですので、いきなりですが結論に入ります。

DFSで出来ること

１、各頂点にとある1点からの距離を置ける。(引数にdist、配列にd[i]の使用）
２、とある1点と連結している頂点を探せる。(配列visited[i]の使用）
３、全ての頂点からDFSを行うことにより、DFS開始の頂点の番号を、その頂点に連結している全ての頂点に書くことが出来る。(par[i]=startv)

といった感じです。正直ここまで書いておいて何ですが、これらはunion-findで内部に実装可能です。
ただ、こういった場面ではDFS特有の強さを誇れそうです。

４、各頂点に固有の特徴を付けることが出来る（一つ前の頂点を引数に用いることが可能なため）
例題：D - 辺彩色 （これはアルゴリズムの難易度が高く紹介しきれませんでした。解説の方をご覧あれ。）

また、各頂点に特有のbitを立て、組み合わせの確認用のマスクビットを作り、それによりその頂点の状況、またその頂点付近の状況を判断する。
果たしてどういった問題に適用できるか分かりませんが、何か問題に使えそうな気がします。

要点はこんなところでしょうか。実装についてもまとめようと思ったのですが、取り上げた問題の中でほぼ要所を書いてしまっている気がしたので、その３つの記事を見比べした方が分かりやすそうです。まだ感覚のつかめない方は是非見比べてみてください。あるいはtwitterで質問でも送ってください。

おわりに

グラフDFSについての内容は以上となります。恐らくですがほとんど網羅したのではないでしょうか。
次回からはunion-find編となります。ここまで読んだ方であればunion-findの中身は簡単に理解できると思うので、よく使われる実装の形についてまた書いていこうと思います。今回はここまで。

あとがき

自分の中では初めての長い記事となりました。今回の記事をまとめるにあたって、取り上げやすい問題を探したり、また解説を見たりと色々行いました。その際、色々探したつもりではあるのですが、グラフDFSの実装に気を使った記事は見当たらなかったので、その部分を埋めることはできたかなと思っています。
自分はアルゴリズムの方は理解するのが楽しいのですが、実際に問題に対してどう実装するのかといった部分が少し苦手です。そういった人のために記事を書けるよう頑張っていきたいです。

グラフDFS問題編 その３ (ABC075-C)

まだまだ続くよグラフDFS第三回。早速問題に入っていきましょう

今回の問題

C - Bridge
C問題なのに難易度がD問題相当に見えるのは気のせいでしょうか。次から解説です。

解説

1、入力について考える

今までは距離について扱っていましたが、今回は連結のみ。そして辺を消すといった動作が加わっています。この部分を上手く済ませることが出来れば簡単になりそうです。
辺を消すといった動作の場合、隣接リストだと毎回格納しているリストを参照する必要があり、少々大変です。
また、連結判定はbool値を用いるため、メモリ消費量が抑えられる可能性が高いです。さらにグラフのサイズも小さいため、今回は隣接行列を用います。

いつも通り入力から入ります。

#include <iostream>
#include <vector>

using namespace std;

int N;//隣接行列の場合は頂点数はグローバルに置いた方が楽なことが多い
int a[60], b[60];

bool G[60][60];
bool vis[60];


int main() {
    int M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の作成
    }//グラフ作成完了

}

代入演算子は右結合のため、上記のような書き方が出来るようです。

2、処理の実装

今回の問題は操作どうりに動かすことが可能です。すなわち、

１、一つ辺を消す。
２、頂点0からのDFSで全ての頂点を訪れることが出来るか試す。
３、全ての頂点に訪れているかvisited配列をforループで確認。訪れていない場合はカウントする。
４、消した辺を復元する。

以上のことを全ての辺にやってあげることで解けます。こういった全探索の場合は一回目の処理を適当にでもいいので書くと書きやすい気がします。

今回もコードに解説がてんこ盛りなのでそちらをご覧ください

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int a[60], b[60];

bool G[60][60];
bool vis[60];

void dfs(int v) {
    vis[v] = true;
    for (int i = 0; i < N; ++i) {
        if (G[v][i] == false) continue;//今回はNが小さいので遠慮しない
        if (vis[i] == true) continue;//既に訪れている 
        dfs(i);
    }
}

int main() {
    int M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の作成
    }//グラフ作成完了

    int cou = 0;//橋の個数
    for (int i = 0; i < M; ++i) {
        G[a[i]][b[i]] = G[b[i]][a[i]] = false;//辺の消去
        fill(vis, vis + N, false);//連結判定のため初期化

        dfs(0);//頂点0から訪れることが出来ないということは非連結

        bool no_connect = false;//辺であるか否か
        for (int j = 0; j < N; ++j) {//N個の頂点全てに訪れているはず
            if (vis[j] == false) no_connect = true;
        }
        if (no_connect) cou++;

        G[a[i]][b[i]] = G[b[i]][a[i]] = true;//辺の復元
    }

    cout << cou << endl;
}

こうしてみるとNが小さい場合は隣接行列の方が使い勝手がいいですね。自分ももっと使うことにします。今回はここまで。

ということでまさかの第三回まで続きました。ここまで来たらatcoderでDFSで解けそうなグラフ問題は全て記事にしていきたいです。おしまい。
6/22追記:まだDFSで解ける問題はあると思っていたのですが、なんとABC100回までには300点や400点にDFSが使いやすい問題はもうありませんでした。よって次回はまとめです。

グラフDFS問題編 その２ (ABC087-D)

ここら辺から初級者の範囲を抜けると思うのでタイトルから消しております。なんか深いところに入っていっている気分ですね。
今回もとてもいい問題なのでやっていきましょう。取り扱う問題はこちら。

ABC087 D - People on a Line
比較的読みやすい問題だと思います。考えたい方はぜひ考えてみてください。
以下解説です。

解説

1、入力部まで

今回の問題はx軸上に並んでいますが、距離が必要になることからグラフに持ち込めそうです。L-R間のcostと考えれば今までの形で入力出来そうですね。 というわけで入力を行っていきます。

入力までのコード

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int L, R, D;
        cin >> L >> R >> D;
        L--; R--;
        G[L].push_back({ R,D });
        G[R].push_back({ L,-D });//解法に向きが必要なので負で入力
    }
}

今回は一つの頂点からの総合距離を判定しないといけないので入力が負になっています。深く考えなくても大丈夫です。
後はもはや定番の形となりました。隣接リストは優秀ですね。

2、DFSなどの全探索における強み

DFSなどの全探索の強みとして、すべての頂点に一つのある頂点からの距離を、別の配列を用いて全て保存することが出来ます。(例えば0-3-5なら頂点0からの距離はd[3]やd[5]とすることで保存できる)
よって始点を決めることですべての頂点に始点からの距離を保存することが出来ます。

そして改めて考えると、今回の問題で距離に矛盾が生じるならば、それは二つ以上の頂点から一つの頂点に行くことが出来る状態のみです。これを用いて実装を考えると、連結しているグラフにおいて、その頂点に再び訪れることがあった場合に、距離が矛盾しているか否かだけで解くことが可能です。

ということで頂点0からの全探索を行い、頂点0と連結している部分の全ての全探索を行ってしまいます。そしてたどり着いた頂点に一つ一つフラグを立てます。 もしフラグの立てた頂点に訪れた場合、矛盾の判定をそこで行う必要があるので、保存しておいた一度目の探索の距離と、現在引数に取り込んであるdistを比較すれば正しいかどうかが分かります。これにて頂点0に連結しているすべての頂点の探索は終了するので、以下頂点0に連結していない頂点などに同様に行っていけば答えを出すことが出来ます。

以下実装例です。いつも通りソースコードに解説をまとめておきました。

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

vector<edge> G[200010];
bool vis[100010];
int d[100010];

bool dfs(int v, int dist) {
    if (vis[v]) {
        if (d[v] != dist) {
            return true;
        }
        else {
            return false;
        }
    }
    vis[v] = true;
    d[v] = dist;
    for (int i = 0; i < (int)G[v].size(); i++) {
        if (dfs(G[v][i].to, d[v] + G[v][i].cost)) {
            return true;//その頂点における判定で一つでも矛盾があれば、全てtrueを返して強制終了。
        }
        //何も矛盾が無ければ次のリストを見る。
    }
    return false;//連結している頂点が最後まで探索できたという証。
}

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int L, R, D;
        cin >> L >> R >> D;
        L--; R--;
        G[L].push_back({ R,D });
        G[R].push_back({ L,-D });
    }
    for (int i = 0; i < N; i++) {//連結していない頂点があった場合に探索していく
        if (!vis[i] && dfs(i, 0)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

今回の実装の見どころは、bool型の再帰関数にif文を用いてtrueで返し続ける方法です。再帰関数の強制終了の形として知っておくと役立ちそうです。
といったところで今回は終了です。

最近ちょこちょこグラフの問題を探しているのですが、どれもいい問題で改めてatcoderさんの凄さを感じています。あと調べるたびにグラフのDFSの記事が少ない気がするのでこれからも頑張って書いていこうかなと思っています。
おしまい。

（初級者競プロer向け) グラフDFS問題編 その１

この間グラフDFSの初級編の記事を書きました。
（初心者向け）グラフの実装について - bplain’s blog
（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法 - bplain’s blog

さて次は何やろうと思いましたが、よく考えたらまだグラフDFSの具体的な問題をやっていないことに気づきました。
なので良さそうな問題を一つずつ挙げてやっていきます。難易度はD問題相当になりますが、前に書いたグラフの記事がわかる方ならいけると思います。それでは問題に入っていきましょう。

ABC070　D - Transit Tree Path

今回とりあげるのはこちらの問題。400点というと何か大変そうなイメージがある方もいらっしゃるかもしれませんが、実は正解コードのほとんどの行が入力部分で構成されています。なのでまずは入力部分をきちんと書けるようにしていきましょう。

さて、この問題の答えをほぼ言わないと実装に入れないので、自力で考えたい方はこの先はまだ見ないようにしてください。以下解説です。

解説

まず、今回のような単純な木構造にはとある特徴があります。それはどの頂点も根ノードとすることが出来るという点です。(根ノード：木の一番親の部分)
自分も調べて知ったので、知らなかった人は覚えておきましょう。
そして、改めて問題を考えると実はとても単純で、頂点Kを根として考え、そこからの距離をすべて保存し、Kからx、Kからyの距離を足せば終了です。とてもシンプルですね。
しかし初級者の私たちにとっては実装するのも重要です。やっていきましょう。

1、入力部分の実装を行う

最初に言いましたが、グラフの問題は入力部分だけでもかなりの量となります。とりあえず書いていきましょう。
(わからない方は以前の記事をご覧ください)

#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
    int to;
    ll cost;
};

vector<edge> tree[100010];


int main() {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }

    int Q, K;
    cin >> Q >> K;
    K--;

    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;

    }
}

今回は隣接リストの形。

2、DFSの実装を行う

次にDFSの実装です。必要な引数の確認をしていきます。とりあえず始点Kの番号と、Kからの距離は引数に必要そうです。
これでコードを書きたいところですが、今回は無向グラフで、隣接リストに戻る頂点も取り込んでしまっているため、このままでは途中で親ノードに帰ってきてしまい上手くいきません。
そこで引数に親ノードを取り込んでおきます。そうすることで、もし一つ前の頂点と次の行き先が同じであるならばDFSを行わないように実装することが出来ます。

以下が実装例です。

#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
    int to;
    ll cost;
};

vector<edge> tree[100010];
ll cost_k[100010];//Kからのコスト

void dfs(int v, int par, ll dist) {//parは親ノード(一つ前の頂点)
    cost_k[v] = dist;

    for (int i = 0; i < (int)tree[v].size(); i++) {
        if (tree[v][i].to == par)continue;
        dfs(tree[v][i].to, v, dist + tree[v][i].cost);//行き先、今いる頂点、距離
    }
}

int main(void) {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }
    int Q, K;
    cin >> Q >> K;
    K--;

    dfs(K, -1, 0);//Kに親ノードはないので-1とする

    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << cost_k[x] + cost_k[y] << endl;
    }
}

今回は以上となります。無向グラフのDFSには引数に戻ってくる頂点も必要であると覚えておくといいかもしれません。

よかったらtwitterでふぁぼでもくださいな。