CodingBatで自然言語処理の勉強~その1~

codingBatのつまづいた所のメモです。

Warmup-1 

  • missing_char

Given a non-empty string and an int n, return a new string where the char at index n has been removed. The value of n will be a valid index of a char in the original string (i.e. n will be in the range 0..len(str)-1 inclusive).

ex)

missing_char(‘kitten’, 1) → ‘ktten’
missing_char(‘kitten’, 0) → ‘itten’
missing_char(‘kitten’, 4) → ‘kittn’

要するに、「二つ目の引数で与えられた数字番目の文字を抜かせ」ということだ。

sliceを使って、抜かした文字列の前と後ろで分けて、足してやれば良い

実行するとこんな感じ。

 

  • front_back

Given a string, return a new string where the first and last chars have been exchanged.

ex)
front_back(‘code’) → ‘eodc’
front_back(‘a’) → ‘a’
front_back(‘ab’) → ‘ba’

要するに、与えた文字列の最初と最後を入れ替えろということ

 

答えの文字列を「最後の文字」+「最後と最初以外の真ん中の文字列」+ 「最初の文字」と分割して考えているところがみそ。

実行するとこんな感じ。

 

  • front3

Given a string, we’ll say that the front is the first 3 chars of the string. If the string length is less than 3, the front is whatever is there. Return a new string which is 3 copies of the front.

ex)
front3(‘Java’) → ‘JavJavJav’
front3(‘Chocolate’) → ‘ChoChoCho’
front3(‘abc’) → ‘abcabcabc’

要は、与えられた文字列の前文字を三回繰り返すものを作成しろということ。

特に難しくない.

実行結果はこんな感じ。

 

Warmup-2

 

  • string_splosion

Given a non-empty string like “Code” return a string like “CCoCodCode”.

ex)
string_splosion(‘Code’) → ‘CCoCodCode’
string_splosion(‘abc’) → ‘aababc’
string_splosion(‘ab’) → ‘aab’

要は、与えられた文字列の「前1文字抜き出す+前2文字抜き出し+前3文字抜き出し…+最終文字まで抜き出す」 というのを繰り返した文字列を生成しろということ。

for文で最終文字(lenで長さを取得する)番目まで抜き出すのを繰り返し、それまでのを足していくだけ。

実行結果はこんな感じ。

 

  • last2
Given a string, return the count of the number of times that a substring length 2 appears in the string and also as the last 2 chars of the string, so “hixxxhi” yields 1 (we won’t count the end substring).

last2(‘hixxhi’) → 1
last2(‘xaxxaxaxx’) → 1
last2(‘axxxaaxx’) → 2

要は、最後2文字と同じものが「最後2文字をのぞいたところで、見つかればそれをカウントする」

以下の例であれば、「SS」は「1文字目+2文字目」「2文字目+3文字目」「3文字目+4文字目」と合計三回見つかるので、3が出力されれば正解である。

 

2文字のngramなので、与えられた文字列を2文字ごとに最終文字である「SS」とあっているか確認すれば良い。

実行結果がいかになれば良い。

 


Coding Bat PythonのWarmup1の途中からWarmup2の途中までやりました。

また勉強したら更新しようと思います。



スポンサードリンク

 

記事が役に立ったらシェア!

pythonでランダム・ウォークのシミュレーションを作った



スポンサードリンク

モンテカルロ法→ブラウン運動→ランダムウォークにたどり着いたので、これくらいなら秒殺できるかも!と思い、作って見ました。

ついでに前回書いた記事(モンテカルロ法)も見たい方はこちら。

 

ランダムウォーク

事象Xnの次に現れる事象Xn+1が確率的にランダムに決まるものをいう。

数学的に説明するならば、確率変数X1が以下の分布
\begin{eqnarray}
P\{X_{n} = 1\} = p , P\{X_{n} = -1\} = 1-p
\end{eqnarray}

に従うとき、確率変数Xnの分布は、n=1, =2の時、
\begin{eqnarray}
P\{S_{1}\} = P\{X_{1}\} = p\\
P\{S_{2}\} = P\{X_{1}\}P\{X_{2}\} = p^2
\end{eqnarray}

となる。この確率分布の時は「単純ランダムウォーク」という。

特に\(p = \frac{1}{2}\)の場合を対称ランダムウォークという。

 

シミュレーション動画

グラフを更新するたびに色が変わるのですがお許しください。

計算に用いたコードは以下です。

 

list内の要素をランダムに取得するchoice関数というものがあるので、それを使います。他の方も結構使ってるみたいなので、オーソドックスなようです。

今回はランダムウォークさせる回数分、for文で処理していますがfor文を使わず、random.choice(plus,size=100)というようにrandom.choice()を実行する回数を直接指定する方法もあるそうです。こちらの方がインデントもなくなり、綺麗になるので試しにやってみてください。

 

動画保存の部分で少々手間取ったので今回はQuicktimeplayerの画面収録で保存しました。

動画保存にはffmpeg?というものをインストールしてパスを通してと、やらなければいけないことがあるそうで。pythonで動画保存ができ次第、また更新します。

 



スポンサードリンク

おまけ

100回までランダムウォークした時の挙動がこんな感じ。確かに株価の挙動に似てますね!

勉強材料には以下を使いました。

 

記事が役に立ったらシェア!

モンテカルロ法で円周率を計算する。(python)



スポンサードリンク

モンテカルロ法の勉強の一貫として、円周率を導出するプログラムを書いたので載せます。

今回はこちらの本を用いて勉強しました。数値計算の基本的な手法について網羅されております。

 

 

モンテカルロ法とは?

乱数を用いてサンプル分布の情報を得る手法の総称です。乱数を用いていれば、その乱数の分布がなんであろうが、全てモンテカルロ法になるわけです。

かなり広義な意味です。さらにその乱数の確率分布に正規分布とかベルヌーイ分布、コーシー分布、指数分布とかがあるわけです。

円周率の計算

使用したコードです。

 

擬似乱数を用いていますので、プログラムを動かすたびに違う結果になります。

ちなみに500回円周率を計算した時の平均値は3.141804799999997になりました。グラフから見てもあってそうです。

さすがにデータ点10000点×500回なので、ほぼ真の値に収束しています。

計算回数を増やせば増やすほど、値が収束する現象は「大数の法則」として知られています。

 


 

各回数での円周率の計算値がどれくらい真の値からずれているのか、ずれに頻度はどれくらいかを視覚化するためヒストグラムを作成しました。

横軸が(円周率-計算で求めた円周率)、縦軸が各範囲における頻度です。今回はビン数を40(x軸の範囲内で何等分するか)にしました。

 



スポンサードリンク

乱数プロットの画像描画

モンテカルロ法のwiki風な画像を作成しました。試しにデータ点が10000と1000の時で計算しました。左側がデータ点10000、右側がデータ点1000の時です。半径1の円内にあるものが赤、それ以外が青です。

 

  

 

 

 

 

 

 

上の図を作成するために使用したコードを載せます。

 

本当はwikiみたいにデータ点数を変えた時のプロット描画を見たかったので、for文を回して各データ点数ごとにグラフを作成し、それを動画にするプログラムも書きたかったのですが、疲れたので今回はここまでにします。

wiki風動画作成は別途記事にしようと思います。

記事が役に立ったらシェア!

pythonで線形最適化問題を解いてみた



スポンサードリンク

pythonで線形最適化問題を解いたので記録しておきます。

参考にしたサイトはこちら。

ラグランジュの未定乗数法

関数の最適化問題を解くのに知っておかないといけないのは「ラグランジュの未定乗数法」です。

自然言語処理等の機械学習の分野ではこれを知るのと知らないのでは、論文の理解度も全く変わってくるそうです。

こちらの文献にも書いております。

 

条件

  • 目的関数(最適化したい関数)をf(x,y)とする
  • 制約条件(境界条件)をg(x,y)=0とする
  • \(\frac{\partial f}{\partial x}\neq 0\)
  • \(\frac{\partial f}{\partial y}\neq 0\)

の時、未定数\(\lambda\)を考えると以下が成り立つ。
\begin{eqnarray}
\left\{ \begin{array}{ll}
\frac{\partial f}{\partial x}+\lambda\frac{\partial g}{\partial x} = 0 \\
\frac{\partial f}{\partial y}+\lambda\frac{\partial g}{\partial y} = 0 \\
g(x,y) = 0
\end{array} \right.
\end{eqnarray}

以上の三式を満たす(x,y,\(\lambda\))を求める方法が「ラグランジュの未定乗数法」です。

そしてこれが制約条件の元での「最適解」ということです。

別途記事にして書こうと思いますが、この式はナイーブベイズやサポートヴェクターマシン等の最適問題を解く際に必須になる式です。

 

 



スポンサードリンク

pythonを用いて線形最適問題を解く。

pythonで線形計画問題を解く場合、pulpというライブラリを用います。非線形の場合は「open opt」というライブラリを用いるみたいです。今回はpulpの紹介のみで終わりにします。

まずはpulpをpipでインストール

今回の線形最適化問題を示します。

  • 目的関数 \(2x +3 y + 10\)
  • 制約条件 \( x + y = 0.5\)

以上の条件でpulpを用いて計算します。

problem で目的関数と制約条件を定義しています。problem.solve()で解きます。

実行結果

と結果が出ました。x = 0.5 ,y = 0 がどうやら最適解のようです。軽くラグランジュの未定乗数法の復習と、pulpの勉強ができました。
次は非線形問題の最適化についてpythonで勉強していきます。



スポンサードリンク

 

 

 

記事が役に立ったらシェア!

mac版python3にMecabをインストール<2017年9月時点>



スポンサードリンク

python3にmecabをインストールしたので、記録して起きます。2017年9月時点です。

記事更新から時間が立っていたら違うかもしれません。

pipを使用する

上記コマンドを使用するだけです。

念のため、インストール時の環境を書きます。

  • python3.6.1
  • anaconda 4.4.0
  • mecab-0.996
  • mecab-ipadic-2.7.0
  • mac-os-sierra(10.12.5)

以上です。

 

記事が役に立ったらシェア!

ダイクストラ法についてまとめる



スポンサードリンク

アルゴリズムクイックリファレンスで2点間の最短ルートを求める「ダイクストラ法」について勉強したのでまとめます。

参考ドキュメントはこちらです。ウルトラ参考になりました。

 

応用的には飛行機の最短経路、電車の最短ルートの検索、カーナビとかの経路探索にも使われているアルゴリズムだろう。日常的におせわになっているアルゴリズムと言っても過言ではない。

ダイクストラ法(単一始点の最短経路アルゴリズム)

今回解く問題は以下の問題です。参考サイトに一つノードを加えました。

開始点(スタート)は1、終了点(ゴール)は6。上の図のような重み(距離)が与えられているときの1→6の最短経路を解きます。

ダイクストラ法の解説

ここでは一般的な説明ではなく、上記の解法の説明をします。いきなり一般論を述べるより具体的な問題から入った方が後のアルゴリズムも理解しやすいかと思います。

  1. スタート地点を1番とする(当然)
  2. 地点1から地点(2と3)に移動できるので、地点2と3の重みを更新します。(まだ地点2と地点3への最短経路は決定していません)
  3. 番号の小さい方(ここでは2)に移動します。(これが初めての移動なので、地点2への最短経路は1→2で決定です)
  4. 地点2から移動できる地点(3,4,6)があるので、重みを更新します。
  5. 3,4,6のうち最小番号の3に移動します。
  6. すでに3には1→3の重み80が存在しますが、今辿ってきた経路1→2→3が70なのでこちらの方が近いということになります。なので3の重みを70で更新します。とりあえずここまでの状態を図に示します。決定項目(最短経路)が青で未決定(現状では決定できない)事項が黄緑です。
  7. 最初の図に戻ります。地点3から移動できるのは4と5なので、重みを更新します。そうすると今回の経路(1→2→3→4)での重みは70+10=80ですが、すでにある経路(1→2→4)の方が重みが小さいのでこちらが最短経路ということになります。なので今回は重みは更新しません。
  8. そして3から移動できる最小番号(地点4)に行きます。
  9. 地点4から移動できるのは5と6です。今回の経路(1→2→3→4)の重みで更新すると、地点5での重みは4→5が30なので95、地点6での重みは4→6が10なので75となります。現時点での仮の経路は以下です。
  10. この時点で最小経路は(1→2→4 →6)となるのが自明なのですが、練習のため最後までやりましょう。地点4からいける最小番号は5なので、地点5に移動。
  11. 地点5はこれが初めての重みなので95で更新する。地点5から移動できる地点は地点6のみ。今回の経路(1→2→4→5)で重みを更新すると5→6が15なので95+15で110となる。すでにある経路(1→2→4→6)の重みが75なので今回は更新されずに最短経路が1→2→4→6で決定する。

このような解き方がダイクストラ法です。別名「貪欲法」と言います。残っている値(この場合は接点の数)が最小のものを選ぶという意味で貪欲です。なおダイクストラ法は重みが非負数の場合のみ使えます。非負数の場合はベルマン-フォード法を用います。これについては別途説明します。

コードを書いてみる

全体をいくつかの部分に分けて説明します。


隣接行列を定義します。隣接行列についてはこちらを参考にしてください。ここでは2重リストを用いて隣接行列の成分を表しています。

接点数をlen()関数で定義しています。未探索の接点をlist(range(node_num))で定義。これで未探索接点の初期条件(0,1,2,3,4,5)を設定します。

[math.inf]は正の無限大を表すので全ての接点の初期距離を∞(到着可能か不明)とする。

移動前の接点を[-1]*node_numで定義します。

接点0までの距離は開始点なので0とする。


次に最小のインデックス番号を取得する部分の関数です。

接点番号の初期値は0なのでstart = 0

indexに未探索ノード(ある地点から移動できる点)がある場合、index (接点)はそのまま。移動できる点がなくなった場合(接点1の場合2も3も計算した場合)、もうないのでelseとなり次の接点番号2へ移る。


ここはダイクストラ法の根本部分です。

while文は未探索接点がなくなるまで繰り返します(len(unserched_nodes) !=0)

最初の接点間の重みは無限大(math.inf)と定義する。ここから、上記で説明した1番にたどり着く(プログラミングは前提条件与えるのにやっとですね笑)

for文は未探索ノードにおけるループです。posible_min_distance=distance[node_index]の部分で最短距離が小さければ更新します。

そして先ほど説明したget_target_min_index関数で接点から次の接点へ移動する際の最小番号を更新する。(移動できる場合は更新せずにそのまま)

そして、この点は探索終了なので未探索接点(unserched_node)から削除する(remove(target_min_index))

経路の重み計算にはその時の接点番号を用いる(ターゲットから伸びる接点)のでtarget_edgeとして定義する。

そしてif文内で過去に更新した重み(距離)よりも小さければ(重みが少なければ)それをdistance[index]として更新する。

最後に一つ前の接点に到達する接点のリストを更新する。


正直ここが全然わかりません。

previous_nodeとprevious_nodesの違いがいまいち。二行目のnode_num-1もなんの意味が。

node_numは接点数のはず。接点数は一定で6-1で5のはず。そしたらelse文とか意味ないじゃんて思ってしまう。

難しい。

実行結果

上で手計算で解いた時と同じ結果になります。しかし自分で0から書いたコードではないので、どこで何が起きているのか不明です。まさにブラックボックスの状態ですね。

以上、一応ダイクストラ法のアルゴリズムについて勉強してみましたがやはりコードに落としこむことができないm(_ _)m

今回はオライリーの「アルゴリズムクイックリファレンス」とgoogle先生を頼りに勉強しました。

正直この本は初心者には嫌われてますが、これを理解するための入門書チラ見しながらとかgoogle先生に聞きながらなら、かろうじて読めるかなと行ったところ。論文読んでるような感じです。時間はかかるけど、しっかり理解しながら読めば気付いた時にはそこらへんの入門書程度なら余裕だなって感じの知識はつきます。

たまには難しめの本から入りたいという変わり者にはおすすめです。



スポンサードリンク

 

 

 

 

記事が役に立ったらシェア!

言語処理100本ノック(第3章前半)



スポンサードリンク

第2章後半の続きです。どうやらここからが本番のようです。正規表現という初めて触れるので他の方のサイトを参考にしながらゆっくりやっていきたいです。

参考にさせていただいたサイトはこちら

 

Wikipediaの記事を以下のフォーマットで書き出したファイルjawiki-country.json.gzがある.

  • 1行に1記事の情報がJSON形式で格納される
  • 各行には記事名が”title”キーに,記事本文が”text”キーの辞書オブジェクトに格納され,そのオブジェクトがJSON形式で書き出される
  • ファイル全体はgzipで圧縮される

以下の処理を行うプログラムを作成せよ.


20. JSONデータの読み込み

Wikipedia記事のJSONファイルを読み込み,「イギリス」に関する記事本文を表示せよ.問題21-29では,ここで抽出した記事本文に対して実行せよ.

ファイルを読み込み、一行ずつ処理するところはこれまでもやってきたので問題ないと思います。

ファイルがjson形式なので、json.loads()関数を用いてjson形式に変換しています。

問題はarticle_dict[“title”]==[“イギリス”]の部分です。

どうやらこれは記事内で利用されている、htmlタグを指定するときに利用するらしい。htmlファイルには

実際に

みたいな感じでいろいろなタグが使われている。

今回は要するにファイル内の

となっている部分について読むということであろう。

実行結果:

とこんな感じになっていればおっけー。

 

21. カテゴリ名を含む行を抽出

『記事中でカテゴリ名を宣言している行を抽出せよ.』

 

特に難しい処理はしていないが、自分的には11行目の”Category” in line:のところが気になった。

lineはlinesの時点で文字列として扱われているので”Category”としていきなりif文の中で宣言して構わないみたいだ。

if の条件文で””を使うことがなかったので、慣れないが自然言語処理なら普通のことなのだろう。

実行結果:

for文を使っているためlineがリスト型になってしまうのは否めない。

 



スポンサードリンク

22. カテゴリ名の抽出

『記事のカテゴリ名を(行単位ではなく名前で)抽出せよ.』

module化しなくてもいけるが、インデントが多くなるのでモジュール化しました。

正規表現を扱うためにreモジュールをインポートします。正規表現とは文字列の並びやパターンを特定するもの。

どんな使い方するのだろうかとかは、こちらの方のサイトを見ていただけるとわかると思います。

ちょっとこれは新しい情報が多すぎて混乱しそうです。そもそもなんでこんなめんどいことしなきゃいけないのか?など聞きたいことは山ほどあります。

compileというコマンドで正規表現パターンを定義してやるぞって意味。

findall()は上で指定した正規表現パターンを()内の引数から抽出するための関数。

正直なところ^とか. とか意味がわからない。おそらく今回のデータが文章構造になっていて一行ごとに読み込み、処理をするようになっているので行頭を指定してやる必要があるのだと思う。

.*で任意の文字0回以上と指定しています。どんな文字でも何回でもおっけーよってことだと思うが、それ指定する必要ねーじゃんって思ってしまう。

独学の限界を少々感じるが、理解できたらおいおい更新していきます。

 

23. セクション構造

『記事中に含まれるセクション名とそのレベル(例えば”== セクション名 ==”なら1)を表示せよ.』

セクションとは記事の見出しです。第1章とか通常の文章部分よりもでかい文字で書いたりする部分のことです。なのでセクション構造とはその文章の章構成とか目次みたいなもんです。

レベルというのはその章とか目次がどの階層にいるかというのを表したものです。一番上の階層が「1」ということです。

正規表現部分は慣れませんが、実際に自分でやった方が早いのでしょう。一発でなんか絶対うまく行かないと思いますが笑

の部分はセクション名が==セクション名==という形式で書かれているため、2個以上という意味で2が入ります。もう一個階層が下がると=== サブセクション名===という感じでしょうか。

これがないと、例えば

==セクション構造== ===サブセクション=== ====サブサブセクション====みたいな階層構造の場合、最後まで一気に読み込んでしまうということだろうか。?は直前の正規表現で指定したパターンの最小回数(1回)でのマッチングを意味するものなので、次に==が出てきた瞬間とこまでしかマッチングしない。

こちらのサイトを参考にすると理解できそうです。

後方参照というものらしく、終わりと開始が同じパターンならそれを利用して\numberで開始を指定してマッチングさせることができるものらしい。

== セクション名 ==みたいな感じで空白があるものがデータに含まれていたため以下のような空白除去が必要らしい

実行結果:

こんな感じ。

 

24. ファイル参照の抽出

『記事から参照されているメディアファイルをすべて抜き出せ.』

メディアファイルが何を意味しているのかわからなかったのですが、jpgとかsvgファイルのことらしいです。そしてそれらのファイルの前にファイルとかfileとか書かれているのでそれを指定する正規表現が上の一行です。

verboseは正規表現を便利に書きやすくするための関数です。公式ドキュメントにも

「パターンの論理的なセクションを視覚的に区切り、コメントも入れることができます。」と書かれています。

今回はこれまでのができていれば簡単にできる問題です。

実行結果:

とこんな感じです。

次は第3章後半です。


スポンサードリンク

 

 

記事が役に立ったらシェア!

django チュートリアルの備忘録



スポンサードリンク

最近djangoの勉強の一貫として公式tutirialを始めたのですが、思わぬところでつまづいたのでメモ。

めんどくさがらずに最初から丁寧にやっておけばこんなことにはならなかったと思う笑。

参考にしているドキュメント

一つ目のがdjangoの公式ドキュメントで、二つ目がその公式ドキュメントを元に作成されたtutorialなのでチュートリアルのチュートリアルみたいな感じになってます。

ついでに私のコードはgithubに置いておきます。

問題点

参考にしているドキュメント(チュートリアル(4))では以下のような画面になるといっていますが、ここまで順番通りにやってきたはずなのになぜか選択肢のラジオボタンが表示されない。

 

上のような感じで表示されるはずが、

自分の場合こんな感じに。(質問名が違うのは適当に自分で名付けたので気にしないでください。)

というよりその選択肢の文章どこで設定してんだよって感じで、本家チュートリアル(一つ目の参考ドキュメント)をくまなく探す。

一箇所飛ばしていることに気づく笑。


スポンサードリンク

飛ばしていた箇所

本家チュートリアル(2)の真ん中らへん「APIで遊んでみる」というところ。

APIなんかで今は遊んでらんねぇ、と当初はすっ飛ばしていましたがここがこんなに重要だとは。

pythonシェルを起動し以下をコピペしていく。

これでもう一度.以下を実行。

いけました!!

しかし選択してvoteを押すと

 

なに?

本来ならば投票がカウントされボタンを押した回数分数値が反映されるはずなのですが、反映されないどころかエラー。念のため、

http://192.168.33.15:8000/polls/1/results/で結果画面を確認すると

やはり0のまま。どこが違うのかわからない。当分はここのバグを見つけるで時間を費やしそう。

解決できたらまた更新します。

 

 

 

記事が役に立ったらシェア!

Rで学ぶグラフ理論(第4回)



スポンサードリンク

前回の続きでグラフ構造の評価方法について述べていきます。

相互性

有向グラフにおいて、頂点間の関係のうち有向辺がお互いに向いているものの割合です。言い換えると両思いの割合です。

以下の図に示すように、頂点には4パターンの関係が考えられます。

そして上の図で言えば、相互性は次のように定義されます。

\begin{eqnarray}
\mathrm{reciprocity} = \frac{a}{a+c+d}
\end{eqnarray}

しかし上記の定義は一部である。上の定義式の分子にbを加えた場合の定義も存在する。

両者の区別は、分析の目的に応じて異なる。企業間の株式のネットワークにおいてはaとbは全く別の状態であるが、集団における贈与のネットワークにおいて、互酬性の規範がどの程度守られているかを知りたいときには、aとbは同等のものとして扱うべきである。

なぜなら、互酬性の規範に反するのは、贈与が一方向に行われている場合(図のcとd)であり、お互いに無関係(b)の場合は、規範に反していない。一応その場合の定義を以下に示す。
\begin{eqnarray}
\mathrm{reciprocity} = \frac{a+b}{a+b+c+d}
\end{eqnarray}

階層的構造

出-木構造の必要十分条件として以下の4つが定義されている。

連結性、階層性、効率性、最小上界性である。これらに違反している程度からある有向グラフが階層的構造を持っているかどうかを評価する。

連結性

辺の方向を無視した時グラフ全体で相互に到達可能な頂点の組みがどれくらいあるかによって連結性を定義できる。辺の方向を無視しても相互に到達不可能な頂点の組の数をVとすると、全ての頂点間の組みの数に対するその比率を1から引くことで求める。

\begin{eqnarray}
\mathrm{connectedness} &=& 1 – \frac{V}{\frac{n(n-1)}{2}}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}

階層性

上の図のように、上から下へ一方向ではなく、相互に到達可能な関係があるとすれば、それは上下関係とは呼べず、階層性に違反していることになる。

よって、双方向に到達可能な頂点の組みの数V、少なくとも一方から他方へ到達可能な頂点の組数でをMaxVとすると以下の式で表現できる。

\begin{eqnarray}
\mathrm{hierarchy} &=& 1 – \frac{V}{\mathrm{Max}V}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}

上の図の場合、双方向に到達可能な組みがないので、階層性は0になる。


スポンサードリンク

弱連結

上のグラフでいうと頂点1,2,3,のような関係。

離散数学的な定義

  • • 任意の頂点u, v間が、弧ではつながっている

図で示すと

みたいな感じである。

効率性

出-木構造は上位の頂点から下位の頂点へと必ず一つの経路を通って到達できるという意味で効率的である。しかしそのような経路が複数ある場合それは無駄であるため、そのような効率がどの程度実現しているかを表す指標が効率性である。

今、n個の頂点とm個の有向辺からなる弱連結の有向グラフを考える。もしこの有向グラフが出-木構造なら有向辺の数は、m = n -1 となる。

よって出-木構造でない実際の有向グラフに含まれる冗長な有向辺の数はm-(n-1)となる。

mの理論的な最大値はn(n-1)となるから、冗長な有向辺の数の理論的最大値はn(n-1)-(n-1)である。

これらを用いて、効率性は次のように定義できる。ただしVは冗長な有向辺の数、MaxVは冗長な有向辺の理論的最大値である。

\begin{eqnarray}
\mathrm efficiensy &=& 1 – \frac{V}{\mathrm{Max}V}\\
&=& 1 – \frac{m-(n-1)}{n(n-1)-(n-1)}\\
&=& 1 – \frac{m-(n-1)}{(n-1)^2}
\end{eqnarray}

弱連結でない場合(すいませんがここからよく理解できていません)

文章も砕けた感じになります。

私が参考にしている本では

「この場合は、いくつかの連結成分に分かれている場合がある。この場合、それぞれの連結成分が出- 木構造となっているのがもっとも効率的である。」と書いてあります。

????

まず言葉の定義から

連結成分

以下の図を考えます。

連結成分とは同値関係におけるグラフGの部分グラフである。

{1,2,3},{4},{5,6,7}は連結成分を誘導するという。

でこの連結成分が、上の{1,2,3}のように閉ループを構成するのではなく、

こんな感じになってれば、良いと言っています。

要は、全体で」見たと時に弱連結でなくとも、部分グラフ単体で見た時に、出-木構造になっている時に、もっとも効率が良いということだろう。

弱連結でない時の定義

直感的に十分理解できる。別れている部分グラフのごとに先ほどの定義式を使うだけである。そしてシグマを取れば良い。

有向グラフがN個の連結成分に別れている時、i番目の連結成分に含まれる頂点の数をniとすると、効率性は以下のように定義できる。
\begin{eqnarray}
\mathrm{efficiensy} &=& 1 – \frac{m-\sum^{N}_{i=1}(n_{i}-1)}{\sum^{N}_{i=1}n_{i}(n_{i}-1)-(n_{i}-1)}\\
&=& 1 – \frac{m-\sum_{i=1}^{N}(n_{i}-1)}{\sum_{i=1}^{N}(n_{i}-1)^2}
\end{eqnarray}

実際に計算してみる

階層構造の4つの指標について実際に計算してみることにする。

計算する有向グラフを以下に示す。

計算の簡便化のために以下のような表を作成する。条件に当てはまるものが1、当てはまらないものが0である。

頂点のペア 一方向に到達可能 双方向に到達可能 最小上界をもつ
1-2 0 0 0
1-3 1 0 1
1-4 1 0 1
1-5 0 0 0
2-3 0 0 0
2-4 1 0 1
2-5 1 1 1
3-4 1 0 1
3-5 0 0 0
4-5 1 0 1

連結性

この有向グラフは弱連結であるので、全ての頂点間で到達可能であるため連結性は1である。

階層性

有向辺を辿って少なくとも一方向に到達可能なペアに対する双方向に到達可能なペアの比率を1から引いて求めるられる。一方向に到達可能なペアは6つ、両方向に到達可能なペアは1つなので

\begin{eqnarray}
1-\frac{1}{6} = 0.833333
\end{eqnarray}

効率性

効率性は「階層性のうち冗長な経路の数の多さ」を評価しているので、上の表は関係ない。頂点の数と有向辺の数に依存するので、
\begin{eqnarray}
1-\frac{6-(5-1)}{(5-1)^2} = 0.875
\end{eqnarray}

最小上界性

上の表より最小上界を持たないペアの数は4ペア。最小上界性を求める式を用いて計算すると
\begin{eqnarray}
1-\frac{2 \times 4}{(5-1) \times (5-2)} = 0.33333
\end{eqnarray}

となる。


以上でネットワーク構造の評価法の相互性と階層構造について述べてきた。

次は、前回と前々回にやったColemanの高校生の友人ネットワークのデータを用いて、これまで述べてきた指標について計算し、その結果とそこから導かれる背景について論じていこうと思う。



スポンサードリンク

記事が役に立ったらシェア!

Pythonのクラスとかインスタンスとかなるべくむずい単語使わないで説明してみる。



スポンサードリンク

よくネットを見ているとPythonのクラスやらインスタンスやらメソッドやらの記事を見かけますが、どれも初心者の自分には敷居が高すぎます。まず、文章が長いし、言葉も専門用語の説明なのでむずい。

今回はこのドキュメントを使って自分なりに理解したことをpython初心者の方のために書いていこうと思います。

クラスがどうとかインスタンスがどうとかの前に…

習うより慣れろの概念で、まず下のコードを見てください。

classで何かを宣言していて、その中に詳細を記述しています。ここでは関数を書いています。

今は中身がどうとかはほっときます。

そしてclassの外で今度は、

「太郎、君の情報は Useinfoの東京、1986、タロウだね。」と宣言されています。

そして最後に

「太郎、名前を書いてくれ」「太郎、生まれた年代を書いてくれ」「太郎、住所を書いてくれ」と言われいます(print文)

以上から言えるのは、

  • classの中身を使う(太郎の詳細を知る)ために、そのツール(Userinfoというclass)を宣言しなければいけないということ.
  • 誰に対してそれを使うのか(ここではtaro)を書かなければいけないということ.

もう少し理解するために別の例を。以下はこのドキュメントの演習4の答えです。

上で述べたことから推測すると、今度は使いたい人が三人(taro,jiro,saburo)いるようです。しかも今回使うツールはScore(クラス)というもの。

なので、コードにちゃんと

が、場所は離れていますが宣言されています。

最初の例では、ツール(クラス)を宣言する際に、ツールを使って何の情報がいるのかも()の中で引数として宣言しています。こちらの方が行数が少なくてすむのですが、今回(2つ目の例)は違う書き方をしています。

要するに、jiroの名前、jiroの数学、jiroの英語、jiroの国語と別々に宣言しています。

コードで表すと、今は

となっている部分を

と直接ツール(クラス)を宣言する時に、値を代入して何の情報を得るか指定することができるわけです。

これを可能にするため、最初のdef __init__(self)の部分に引数を追加し

と書き直します。

コード全体を書き換えると、

def __init__の部分で、self~にnameだのmathだの,englishだの保持しておこうってことです。

そしてこれがまさしくインスタンス化です。今の自分の知識ではこれの恩恵が理解できないですが、二つ目の例のように冗長なコードが短くなっています。言い換えると、何かわからんがセットに(コンパクトに)なっている。

これが僕が参考にしているドキュメント

「構造体とクラスの違いについて取り扱います。簡単に言ってしまうと、構造体は内部にデータだけを持ちますが、クラスはデータに加えて処理も内部に持っているというのが両者の違いです。」

と書かれている部分の「クラスはデータに加えて処理も内部に持っている」と言うことなのでしょう。


スポンサードリンク

お相手はあくまでpcです。

しかしここで問題が生じる。

なんで

の部分を

これじゃいかんのよと。だってすでに名前わかってんじゃん(誰の情報欲しいかわかってんじゃん)って。確かにだからこそツール(クラス)を宣言する際に、taroとかjiroとかsanburoとか使ってんじゃんってなります。

それはtaroさんやjiroさんやsaburoさんの情報にもちろん本人の名前も含まれるからです。なのでそれをちゃんと明記してあげる必要があるわけです。

こちらは自明でもプログラムを処理するpcはtaroさんの名前が本当に”taro”かどうかわかりません。なのでそれが自明な我々からしたらアホみたいなことしてるように見えますが、相手はpcなのでしっかり教えてあげましょう。


次回はインスタンス化の利便性、使い所についてもう少し深めて理解してみたいと思います。

どうでしょうか。インスタンス、クラスとかの理解に助けになれば幸いです。あと個人の理解を記したものなので、書き方、異なる解釈をしていると感じた方はコメントをいただけると大変ありがたいです。

是非とも一緒に理解を深めましょう。

 

 

記事が役に立ったらシェア!