隣接行列の実装

Introduction

sorry, this page is Japanese only.

ここでは隣接行列の実装を行っていきます。Python3を使っています。OSはwindows10です。隣接行列の説明は以下の記事の下の方をご覧ください。

グラフ理論の基礎

実装例

扱うグラフ

コマンドでの結果

Code
defファイル

import numpy as np

class directed_Gragh():
    def __init__(self,E,V,gragh_map):
        self.edge = E;
        self.vertex = V;
        self.map = gragh_map;

    def Adjacency_matrix(self):
        adjacency_matrix = np.zeros((self.vertex.shape[0],self.vertex.shape[0]))
        for ed in self.edge:
            P_ = self.map(ed)
            start = P_[0]
            end = P_[1]
            row = np.where(self.vertex == start)
            column = np.where(self.vertex == end)
            adjacency_matrix[row,column] = 1
            adjacency_matrix[column,row] = 1
        return adjacency_matrix

mainファイル

import numpy as np
from Gragh_def import directed_Gragh

def main():

    vertex = np.array(['house','station','school','hospital'])
    edge = np.array([1,2,3,4])

    def gragh_map(edge):
        if edge == 1:
            vertexs = np.array(['house','school'])
        elif edge == 2:
            vertexs = np.array(['school','station'])
        elif edge == 3:
            vertexs = np.array(['house','station'])
        else:
            vertexs = np.array(['station','hospital'])
        return vertexs

    test_gragh = directed_Gragh(edge,vertex,gragh_map)
    print('vertex is %s \n'%test_gragh.vertex)

    adjacency_matrix = test_gragh.Adjacency_matrix()

    print('adjacency_matrix = \n %s \n'%adjacency_matrix)

if __name__ == '__main__':
        main()

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

このブログの人気の投稿

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事はカーネルK-meansの実装を御覧ください。この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。概要 1 of K 符号化法プロトタイプ歪み尺度最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。こののような表現の仕方を1 of K符号化法と呼びます。プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。歪み尺度プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...

カーネル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-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

Bayes' theorem

Introduction sorry, this page is Japanese only. 今回はベイズの定理について書こうと思います。ベイズの定理とは、イギリスのトーマス・ベイズによって発見された、条件付き確率に関する定理です。現在のベイズ推定で用いられる重要な定理です。どのような定理かを解説していこうと思います。ベイズの定理ベイズの定理とは確率P(B|A):事象Aが起こった後での事象Bの確率（事後確率）確率P(B):事象Aが起こる前の事象Bの確率（事前確率）とするとき以下が成り立つことを示しています。 $$P(B|A) = \frac{P(A|B) P(B)}{P(A)}$$ 例例えば、次のように事象A、事象Bwo定義します。事象A:あるYoutuberが動画を投稿したとき、再生回数が100万回を超える事象B:あるYoutuberがお金を50万円以上使う動画を投稿するこの時確率P(A|B)、つまり50万円以上を使った動画が再生回数100万回を超える確率は、youtube内の50万円以上使っている動画を根こそぎ集め、その再生回数を得ることによって推定できそうです。では確率P(A|B)がわかった時、確率P(B|A)もわかる。これがベイズの定理の強みです。（当然確率P(A)とP(B)がわかっている必要はあります。）確率P(B|A)とはあるYoutuberの動画が再生回数100万回を超えたとき、その同がで50万円以上使っている確率となります。これがわかれば、100万回動画が再生される原因は本当に50万円以上お金を使うことなのかがわかります。確率P(A|B)が低い時を考えてみましょう。つまり、50万円以上使った動画は再生回数100万回を超える確率は高い。しかし、100万回再生回数を突破したとき、その動画が50万円以上使っている可能性は低い。この状況はベイズの定理の式を考えいると理解しやすいです。ベイズの定理の式を見てみると、P(B|A)は低く、P(A|B)が高いということは、確率P(A)が著しく高い。もしくは、P(B)が著しく低い。この二つがあげられます。つまり、あるYouruberが100万回再生を突破する確率がかなり、高い。もしくは、あるYoutuber...

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

このブログを検索