グラフ理論

Introduction

sorry, this page is Japanese only.

いよいよ私も三回生になり、グラフ理論の授業が始まりました。ということで、グラフ理論の基本的な定義を書いていこうと思います。

最後に説明する隣接行列については実装を行いましたので、以下の記事もよろしければご覧ください。

隣接行列の実装

グラフのイメージ
グラフ理論のグラフとは高校数学で習う二次関数などとは違います。
例えば駅などを創造してください。各駅間に線路が通っていますね。このような、駅、線路の集まりのことをグラフといいます。次の絵で確認してもらえるとイメージしやすいかと思います。

このようなものをグラフといいます。グラフは二点間がどうつながっているかだけを保存し、実際の距離や位置関係は保存しません。

このような向きのない（各駅を行き来でき、一方通行ではない）グラフを無向グラフをいいます。反対に向きのある（一方通行しかできない）グラフを有向グラフといいます。

グラフの定義

グラフではある空でない集合E,Vを考えます。Eの要素をedge(辺）、Vの要素をvertex(頂点)といいます。

ここで以下のような写像を考えます。

$$g:E \rightarrow V \times V$$

この時(E,V,g)で定義される空でない空間のことをグラフといいます。

写像で捉えるグラフ

写像gというのは、Eの要素、つまり辺を対応する(始点、終点)というV×Vの集合の要素に送ります。gは写像ですので、写像の定義より、Eのどの要素の始点と終点が対応していることになります。つまり、辺がどこにもつながっていないということはあり得ません。反対にすべてのV×Vの要素がEの要素のどれかに対応しているのであればgは全射になります。

隣接行列

隣接行列とはどのvertexと、どのvertexがつながっているかを行列で表します。例を見るのが理解するのには早いと思うので、例を挙げて説明します。

上のグラフのイメージで出てきたグラフの例を考えましょう。隣接行列は以下のようになります。

$$　\[

adj = \left(

\begin{array}{cccccc}

0 & 1 & 0 & 0 & 1 & 0 \\

1 & 0 & 1 & 1 & 0 & 0 \\

0 & 1 & 0 & 1 & 0 & 0 \\

0 & 1 & 1 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 1 \\

0 & 0 & 0 & 0 & 0 & 1 \\

石山駅 -> 一列目

山科駅 -> 二列目

京都駅 -> 三列目

三条京阪 -> 四列目

米原駅 -> 五列目

大垣駅 -> 六列目

として、[n,m]ではnの駅からmの駅へ線路がつながているのであれば1、そうでなければ0をとります。これが隣接行列です。

Reference

https://ja.wikipedia.org/wiki/グラフ理論

このブログの人気の投稿

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only. 今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　実装例以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。こちらにすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...

カーネルk-meansの実装

Introduction English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 # 理論編書きました。K-means 理論編概要 dataset ちょっとだけ理論の説明 k-means kernel k-means Dataset English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。 this page にデータセットを作ったコードを載せています。ちょっとだけ理論の説明 k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

大学院試験　-外部への道しるべ-

始めにこの度、京都大学大学院情報学研究科システム科学専攻に合格することができました！！！僕は現在、立命館大学という関西の私立大学に通っているので、外部受験をしたことになります。さらに、学部は数学専攻で、大学院からは情報学(の中でも機械学習)専攻になるので、専門も変えることになります。この記事では、外部の大学院、もしくは専攻替えを考えている人向けに書こうと思っているので、目次で気になった項目があれば、ぜひ、読んでいってくださいませ。( *´艸｀) ちなみに、予測点数は線形微積6~7割、専門科目満点、英語かなり低いので内緒です。（笑）得点開示を要求するので、得点がわかったら、また追記します。目次外部受験を目指すまで、目指したきっかけ外部受検の大変さ専攻替えの大変さ合格するために英語が苦手な人へ数学科の学部から情報学(機械学習)の大学院を目指す人へ応援外部受検を目指すまで、目指したきっかけここでは、自分の大学生活がどんなだったかを書いてるだけなので、興味のない人は飛ばしましょう。（笑）僕が学部二回生頃に、当時数理科には機械学習の研究をされている先生が一人だけ所属されていました。その先生に、直接弟子入りさせていただき、僕の機械学習への道は始まりました。。。(メインは遺伝統計学の研究でした。) 弟子入りした直後は、タイピングもなめくじのように遅かったですし、gitもpullする前にpushしたこともありました。。。しかし、その先生は、目的に最先端で届く道のりを用意してくださいました。プログラミングを初めて一か月ほどで、t-SNEの実装をしたり(遺伝統計学の研究で必要だった)、四か月ほどで、カーネルc-SVMの実装をしたり(やってみなとゆわれて（笑）)することができました。その後も、学部二回生、三回生ながら、論文を読んで実装してきました。学部二回生冬には、遺伝統計学の研究を株式会社パーソルキャリアさん主催のハッチングフェスというデータサイエンティストのためのイベントで、発表しました。このイベントでは、企業の方もたくさん来られて、知り合えるチャンスがかなりあります！！ (名刺を作っておくと、「えっ、学生なのに名刺持ってるの？！」ってなるので、覚えてもらえます。...

journey of Froakie (ケロマツの旅路)

このブログを検索