スキップしてメイン コンテンツに移動

グラフ理論

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/グラフ理論







Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。 カーネルは次のように定義されます。 $$K(x,y) = \phi(x)^T \phi(y)$$ $\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 プロトタイプは$\mu_i ~\forall k \in K$としま...
コメントを投稿
続きを読む

ロジスティック回帰 理論編

Introduction English ver 今日はロジスティック回帰について書こうと思います。ロジスティック回帰は機械学習の中でも基本とされています。ロジスティック回帰は二値を分類するためのアルゴリズム、モデルです。 概要 この記事はPRMLを参考に書かせていただいています。 最適化には反復再重みづけ最小二乗法を用いています。 シグモイド関数 分類のための確率を定義 交差エントロピー誤差関数 反復再重みづけ最小二乗法 シグモイド関数 初めにシグモイド関数を定義します。 以下のような関数です。 \[\sigma(a) = \frac{1}{1+\exp(a)}\] 後に扱うので、シグモイド関数の微分を計算しておきます。きれいな形をしています。 \begin{eqnarray*} \frac{d}{d a} \frac{1}{1+\exp(a)} &=& \frac{\exp(-a)}{(1+\exp(-a))^2} \\ &=& \frac{1}{1+\exp(-a)} \frac{\exp(-a)}{1+\exp(-a)}\\ &=& \frac{1}{1+\exp(-a)} \{ \frac{1+\exp(-a)}{1+\exp(-a)} - \frac{1}{1+\exp(-a)} \} \\ &=& \sigma(a)(1-\sigma(a)) \end{eqnarray*} シグモイド関数は機械学習において大事な役割を果たしています。 シグモイド関数は以下のような形をしています。 これを見てわかる通り、シグモイド関数は次のような性質を持っています。 シグモイド関数は 定義域は\((-\infty,\infty)\)で定義され、値域は\((0,1)\)で定義されています シグモイド関数は単調増加関数です シグモイド関数は(0,0.5)で点対称です シグモイド関数の値を確率として考えることができるようになります。 分類のための確率の定義 初めにデータが正しく分類されたかの確率を考えてみる。 この直線は超平面だと思ってください。 超平面は以下のように表されます。 \[w^T x= 0\] wは超平面に対する法線ベク...
コメントを投稿
続きを読む

Mahalanobis' Distance

Introduction 日本語 ver Today, I will write about Mahalanobis’ Distance. Mahalanobis’ Distance is used when each dimension has a relationship. This distance is fulfilled definition of distance. Mahalanobis’ Distance is important for Statics. If you interested in Statics or Machine Learning, Please see my this blog. Overview definition of distance deficition of Mahalanobis’ Distance image of Mahalanobis’ Distance definition of distance if d is distance function, d if fulfilled following condtion. \(d:X \times X -> R\) \(d(x,y) \geq 0\) \(d(x,y) = 0 \leftrightarrow x = y\) \(d(x,y) = d(y,x)\) \(d(x,z) \leq d(x,y) + d(y,z)\) Mahalanobis’ Distance Mahalanobis’ Distance is distance function. Mahalanobis’ Distance is defined by following from \[D_{M}(x) = \sqrt{(x-\mu)^T \Sigma^{-1} (x-\mu)}\] here, \(\mu\) is mean vector \[\mu = (\mu_1,\mu_2,....,\mu_n)\] and, \(\Sigma\) is variance-convariance matrix. Mahalanobis’ Distance between x and y is \begin{eqnarray...
コメントを投稿
続きを読む