隣接行列の実装

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-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 今日は、変分法の可視化を実装しました。変分法は、汎関数を最小化させるために使われます。汎関数とは、関数の関数のようなものです。変分法については、 [1] , [2] , [3] , [5] , [6] などを参考にしてください。概要汎関数実装可視化汎関数今回は、次のような汎関数を使います。

$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$

$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$ l(u)はu(x)という曲線の長さです。.

$u(0)=a$ and

$u(1)=b$ という制約のもと、

$l(u)$ を最小化したいといます。最適な

$l(u)$ は

$u(x) = (b-a)x+a$ となります。 (0,a) から (1,b)への直線になっているのがわかります。これは、

$l(u)$ は

$u$ の曲線の長さなので、これを最小化するためには直線が一番であることが直観的にわかります。変分法での導出は、 [5] を参考にしてください。実装変分法における最適な曲線とそうでない曲線の違いを可視化する実装をしました。

$u_A$ を

$u_A = (b-a)x+a + A sin(8t)$ とします。

$A sin(8t)$ は

$u$ から話す役割を持ちます。.

$A \in [0,0.5]$ であり、もし

$A=0$ であれば、

$u_A=u$ です。 github でcodeを公開しています。可視化上側の画像は

$u_A(x)$ を表しています。下側の画像は

$l(u_A)$ の値を表しています。

$u_A(x)$ が

$u$ に近づくほど、

$l(u_A)$ が小さくなることがわかります。 Reference [1] http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-4.pdf [2] http://hooktail.sub.jp/mathInPhys/brach...

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...

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

このブログを検索