k-means++法

k-means法ではセントロイドの初期値が不適切である場合, クラスタリングが上手く行かなかったり収束に時間がかかる場合がある.
この問題の対策としては

  • k-meansアルゴリズムを一つのデータセットで複数回実行し,誤差平方和から最も性能が良いモデルを選択する.
  • 初期のセントロイドを互いに離れた位置に置くこと(k-means++法)

k-means++法での初期化

  1. 選択の対象となるk個のセントロイドを格納するために空のデータセットMを初期化する
  2. 入力サンプルから初期のセントロイド \muをランダムに選択しMに割り当てる
  3. Mに含まれていないサンプル x^{i}ごとにMのセントロイドに対して距離の2乗が最小となるセントロイドを求める
  4. 次のセントロイド \mu をランダムに選択するには各サンプルの距離の重みを等しく以下の確立分布を使用する

 \frac{d(\mu^{p},M)^{2}}{\sum_{i}d(x^{i},M)^{2}}

  1. k個のセントロイドが選択されるまでステップ3-4を繰り返す
  2. 従来のk-means法を使って引き続き処理を行う

【Python】【スクレイピング】HTMLデータのスクレイピング

import urllib.request
url = 'http://umashika5555.hatenablog.com/'
response = urllib.request.urlopen(url)
data = response.read()
decoded_data = data.decode('utf_8')
print(decoded_data)
import urllib.request
import bs4
url = 'http://umashika5555.hatenablog.com/'
soup = bs4.BeautifulSoup(urllib.request.urlopen(url).read())
print(str(soup))

参考
minus9d.hatenablog.com

【ネットワーク】お勉強19

フロー制御TCPプロトコルで, 相手のバッファが溢れないようにするもの.
相手のバッファに溜まっている量を見て満杯そうだったらあまり送らないようにする.
逆に空いているときは一気に送りつける.
一気に送りつけれる量のことをウィンドウサイズという.

TCPではスロースタートアルゴリズムを用いる.
これはルータなど中継するデバイスは基本的に第3層以下の運ぶことを目的にできているので, ホスト側から処理する.
ホスト計算機は閾値まで指数的に送るデータを増やしていき, 閾値になったら徐々にデータを増やしていく.
一度にたくさん送ると渋滞するかもしれないので様子を見ている.
輻輳が発生した場合, 確認応答が1つでも帰ってこなかった場合,いったん送る数を減らす.

TCPではフロー制御でバッファオーバーフローをスロースタートアルゴリズム輻輳制御をしている!!!

TCPまとめ
スリーウェイハンドシェイクでコネクションを確率.
コネクションを確立して互いに確実に送受信ができることを示す.

送るときはフロー制御と輻輳制御を行う.
パケットの破棄が起きないように確実に送るため.

【Python】【OpenCV】n*m のランダムな色の画像を作成

# vim: set fileencoding=utf-8 :
import numpy as np
import cv2
from random import randint
import numpy as np

cols = 320
rows = 320

#イメージ生成
image = np.zeros((rows, cols, 3), np.uint8)

div = 16 # 縦横の分割数 
w = cols / div # 分割された領域の横幅
h = rows / div # 分割された領域の縦幅
for segrow in xrange(div):
    y1 = segrow * h # 分割領域上
    y2 = y1 + h     # 分割領域下
    for segcol in xrange(div):
        x1 = segcol * w #分割領域左
        x2 = x1 + w     #分割領域右
        b = randint(0,255)
        g = randint(0,255)
        r = randint(0,255) 
        c1 = np.array([b,g,r])
        #(x1,y1)-(x2,y2)の矩形を塗りつぶす
        image[y1:y2, x1:x2] = c1


# 表示して[ESC]が押されるまで待つ
cv2.imshow("image", image)
while cv2.waitKey(33) != 27:
    pass

参考
takamints.hatenablog.jp

【並行処理】【Python】プロセスについて

Processクラス
multiprocessingクラスでのプロセスの手順

  1. Processのオブジェクトを作成
  2. start()メソッドの呼び出し
  3. join()で処理が完全に終わるまで待つ

Process()クラスの呼び出しで引数はtargetに実行したい関数名,argsにtargetに入れる引数を入れる.一つとは限らないので最後に,をつける.

from multiprocessing import Process

def f(name):
    print("hello",name)

if __name__ == '__main__':
    p = Process(target=f,args=('bob',))
    p.start()
    p.join()


hello bob
上のコードについて実行されたプロセスのIDを表示するために拡張したコード

from multiprocessing import Process
import os

def info(title):
    print(title)
    print('module name:',__name__)
    print('parent process:',os.getppid())
    print('process id:',os.getpid())

def f(name):
    info('function f')
    print('hello',name)

if __name__ == '__main__':
    info('main line')
    print("-"*20)
    p = Process(target=f,args=('bob',))
    p.start()
    p.join()

os.getppid()は親プロセスのID,os.getpid()は現在のプロセスのIDを取得する.


main line
module name: __main__
parent process: 13055
process id: 18154

function f
module name: __main__
parent process: 18154
process id: 18155
hello bob

mainでの現プロセスと関数fでの親プロセスが一致することに注意

コンテキストと開始方式

import multiprocessing as mp

def foo(q):
    q.put("hello")

if __name__ == "__main__":
    mp.set_start_method("spawn")
    q = mp.Queue()
    p = mp.Process(target=foo,args=(q,))
    p.start()
    print(q.get())
    p.join()

hello

プロセス間でのオブジェクト交換
キュー
Queueクラスはqueue.Queueクラスとほぼ同じ使い方ができる.

from multiprocessing import Process,Queue
def f(q):
    q.put([42,None,"hello"])

if __name__ == "__main__":
    q = Queue()
    p = Process(target=f,args=(q,))
    p.start()
    print(q.get())
    p.join()


[42,None,'hello']

パイプ
Pipe()関数はコネクションオブジェクトのペアを返す.
デフォルトでは双方向性パイプを返す.

【Python】コマンドライン引数

コマンドライン引数はsys.argvで操作することができる.
先頭は自身のプログラムの名前となることに注意.

#sample.py
import sys
print("コマンドライン引数:",sys.argv)
$python sample.py a b c
コマンドライン引数:['sample.py','a','b','c']

【ネットワーク】お勉強18

【第40回】TCP シーケンス番号
MSS
TCP/IPではデータが長い場合は分割して送信する.
その分割するサイズがMSS.
送信は元のデータと同じ順序で送る.
この時に使うのがシーケンス番号.
データを転送する際にはシーケンス番号に送るデータの先頭番号を入れる.
確認応答を送る際には確認応答番号に次に受け取るデータの先頭番号(シーケンス番号+MSS分)を入れる.
エラーが起きたかどうかを判定するには確認応答が一定時間(RTT)帰ってこなかったことによって判定する.

【ネットワーク】お勉強17

【第31回】Layer3 Routing
ルーティング
ルータは最適なルートを見つけるために他のネットワークへのルートを知る必要がある.
更に知ったルートの中から最適なものを選んでルーティングテーブルを作成する.
ルートの知り方は2種類あり静的ルーティング動的ルーティング.

静的ルーティング
静的ルーティングは管理者が手動でルートを定義する.
欠点としてルータの故障があった場合, 他の道をたどるという有痛が効かない.

動的ルーティング
ルータ同士が情報を交換し合っていてルータが故障したとき,あるルータに障害があった場合,それを自動的に切り離すことができる.
3 Minutes Networking No.31Figure31-04
ルータ同士が情報を交換するということはデータを送り合うということでその分帯域幅を使用するということである.よってデータ転送に使われる帯域幅が減ってしまうことが欠点.
また最適ルートを計算するという処理があるのでルータの処理能力が必要.
すべてのルータが同一のルート情報を持つことが必要.
3 Minutes Networking No.31Figure31-05
すべてのルータが同一のルート情報を持っている状態のことをコンバージェンスという.
動的ルーティングはルーティングプロトコルによって実現される.
ルーティングプロトコルとはルータ同士の情報の交換の方法や最適ルートの決定法などを定めたプロトコル.

【ネットワーク】お勉強16

【第27回】 プロトコル帯域幅
通信には4つのアドレスが必要でそのアドレスの確認方法は以下である.

アドレス 取得方法
送信元のMACアドレス 既に決まっている
送信元のIPアドレス DHCP
宛先IPアドレス DNS
宛先MACアドレス ARP


【第28回】Layer3 Router
ルータによるネットワークの接続
ルータを使わない場合,同じネットワーク内にしかデータは転送できない.


【第29回】Layer3 デフォルトゲートウェイ
ブロードキャストドメイン
動的にIPアドレスを貰うときのDHCPDISCOVERなどは全てのホストに届くブロードキャスト,これをほかネットワークに送り出さにようにルータがある.
ブロードキャストが届く範囲のことをブロードキャストドメインという.
衝突ドメインはブリッジ,スイッチが区分けし, ブロードキャストドメインはルータが区分けする.

ARPとルータ
ARPで違うネットワーク上のホストのMACアドレスを知りたい時,ARPはブロードキャストなのでルータが遮ってしまう.
これを防ぐためにインターネットワークではデフォルトゲートウェイが必要となる.
デフォルトゲートウェイは他ネットワークとの接続点に位置するデバイス.

デフォルトゲートウェイ
他のネットワークへデータ転送を希望するホストは一度デフォルトゲートウェイにデータを送り他ネットワークに転送してもらう.
3 Minutes Networking No.29Figure29-03
デフォルトゲートウェイを設定しないとARPが通らないので異なるネットワーク間の通信が出来ない.
宛先のネットワークを見る方法はサブネットマスクのネットワーク部の範囲
3 Minutes Networking No.30Figure30-01
ルータの動作,サブネットマスクによる通信の流れ
3 Minutes Networking No.30Figure30-02
宛先IPアドレスが無い場合はルータは破棄する.(スイッチは全てのポートから送り出す)

【ネットワーク】お勉強15

【第25回】Layer7 DHCP
自分のIPアドレスを動的に取得する場合に必要
DHCP概論
DHCP割り当てるIPアドレスを管理し,実際に割り当て作業を行うサーバー割り当ててもらうクライアントから成り立つ.
DHCPを行うサーバーをDHCPサーバーという.DHCPサーバーソフトを実行しているホストのこと.
クライアントはDHCPクライアントという.

DHCP 承前
DHCPサーバーでは管理者が事前に割り当てるアドレスの範囲を決めておく必要がある.
管理者が決めた範囲のことをIPアドレスのプールという.
管理者はIPアドレスを貸出という形で割り当てることができる.
この割当期間をリース期間という.

DHCP Message
3 Minutes Networking No.25Layer7のカプセル化される前のデータであるDHCPメッセージ
重要なところはクライアントIPアドレス, 割当IPアドレス, オプション

DHCP 割当動作
IPアドレス(ホスト部)がまだ割り当てられていないDHCPクライアントもIPアドレスを割り当てられるようなプロトコルを使うが眠いので頭に入ってこない.
省略.

【Linux】 自分の端末のMACアドレスを知る

MACアドレスNICについている世界でユニークなアドレスである.
上位24bits=3bytesがベンダー番号
下位24bits=3bytesが製造番号
Linuxで調べるには

$ifconfig

Ubuntuの場合は「ハードウェアアドレス」として見ることができる.

【ネットワーク】お勉強14

【第23回】Layer3 サブネットマスク
プライベートアドレス
インターネットでのIPアドレスICANNNICがネットワーク番号を割り振っている.
裏を返せば,インターネットへの接続を考えないネットワークならばICANNのクラスフルアドレッシングに従う必要はない.
しかしネットワーキングデバイスはクラスフルアドレッシングに対応して設計されているので結局必要.
内部LANではプライベートIPアドレスを使う.
プライベートIPアドレスはクラスAの10.0.0.0,クラスBの172.16.0.0-172.31.0.0,クラスCの192.1680.0-192.168.255.0はプライベート用に用意されているのでNICは割り当てない.
内部LANではこれらのアドレスを使う.
これらのプライベートIPアドレスはインターネットに接続しない環境で使われるアドレスで万が一インターネットと接続できる状況になってもルータがインターネットに流さないように止める.
なぜプライベートIPアドレスも通常のIPアドレスと同じような理論で扱うのかというと,もしプライベートIPアドレスのホストがインターネットにつながった場合に元からあったIPアドレスと重複するという事態を防ぐため.

小さなネットワーク
例えばクラスAはホスト番号部が3オクテット=24bits,2^24-2台のホストを管理できる.
これを先頭から順に番号をふるのは管理上良くない.
論理アドレスが階層型であるという性質を利用して小さなネットワークをいくつか作ることを目指す.
この小さなネットワークをサブネットワークという.

サブネットワーク
3 Minutes Networking No.23Figure23-01のようにホスト番号の一部をサブネット番号の領域にする.
ex:
クラスBのネットワークの172.16.0.0というIPアドレス,これをサブネット番号6bits,ホスト番号10bitsに分割する.
この状態でのサブネットワーク1番の1番ホストは
10101100 | 00010000 | 000001 | 0000000001
となり172.16.4.1となる.オクテット単位で考えているので十進数表記でサブネットワーク1番は4になることに注意.
10101100 | 00010000 | 00000100 | 00000001
サブネット番号部に割り当てるbit数は任意だがホストの無いサブネットは無意味なのでホスト部に2bitsは割り当てる.
この場合,ホスト番号が全て0をネットワークアドレス,ホスト番号が全て1なのをブロードキャストアドレスでホストは1bit分の2台登録できる.

サブネットマスク
どのネットワークに属しているかという問題は経路選択の際に重要となる.
サブネットワークは管理者が任意で決めるので経路探索の際にルータが決めるのに障害となる.そこでサブネットを使用する際にはサブネットマスクIPアドレスと同時に表記する.
サブネットマスクとはどこまでがサブネット番号かを示すもの.
10101100 | 00010000 | 00000100 | 00000001 IP addr
11111111 11111111 11111100 00000000 サブネットマスク
3オクテット目の6bits目までがサブネット番号だとわかる.
3 Minutes Networking No.23Figure23-03


【第24回】Layer3 4つのアドレス
データ転送に必要なもの
データ送信には送信元,宛先のMACアドレス,IPアドレスの4つのアドレスが必要

送信元MACアドレス
MACアドレスNICをつけた段階で決定される.
Ubuntuでは$ifconfigで「ハードウェアアドレス」として見ることができる.

送信元IPアドレスの静的な決定
IPアドレスは管理者から渡されたものを使う.
こちらが変更しない限り変わらないので静的という.
IPアドレスを静的な割り振りで決める場合の欠点としてはまず人為的なミスが起こりうるということだ.
人為的なミスとは管理者に割り当てられたアドレスを間違って入力した場合である.
またデバイスの移動の際にIPアドレスをその都度入力し直すとう問題が発生する.

送信元IPアドレスの動的な決定
ある程度の台数を管理するようなLANやデバイスの移動が多いLANでは動的なIPアドレスの割当が一般的.
ネットワークに接続された時点で自動的にIPアドレスを取得する形になる.
IPアドレスを管理しているサーバーに対して「IPアドレスをください」と言ってもらう.
この際, 送信元のIPアドレスがない状態なのに通信できるのはDHCPというプロトコルのため.

【ネットワーク】お勉強13

【第20回】レイヤ3 Internet Protocol
TCP/IP
TCP/IPという現在標準で使われているプロトコルではレイヤ3はIPが受け持つ.

Layer3 Protocol
TCP/IP以外でよく用いられているプロトコルはIPX/SPXやAppleTalk.
レイヤ3プロトコルがパケットの転送を受け持つ.
まず論理アドレスを決定する.
論理アドレスが決まったら経路を決定する(ルーティング).
転送はベストエフォートである.ベストエフォートとは「保証しない」という送信方式である.
「送りますよ?」「はいわかりました」という連絡もなしに送るコネクションレス型通信である.

IPヘッダ
IPヘッダはセグメントの先頭に20-60バイトのIPヘッダをつける.
3 Minutes Networking No.20Table20-21
※フレームでは前後にヘッダとトレーラをつけたがIPパケットはヘッダのみ.
IPパケットには色々な情報があるが最も重要なのは宛先IPアドレスと送信元IPアドレスがあるということ.


【第21回】レイヤ3 IP Addressing
論理アドレス
物理アドレスはユニークなビット列に過ぎないが論理アドレスはそのアドレス自体に意味がある.
論理アドレスはネットワークの管理者がつける.
MACアドレスIEEEがつけたベンダコードとベンダーがつけた割当コードからなる.使用する側は変更不可能.
論理アドレスは管理者が必要に応じて自由につけることができる.
論理アドレスNICではなく各デバイスのネットワークとの接続点ごとにつける.(NICが故障して違うNICに変えても同じ論理アドレスを持つ.)
論理アドレス所属するネットワークの番号+ホストの番号という形になっている.
ネットワークの番号は接続されている全てのネットワークでユニークでなければならない.(孤立したネットワーク内であれば右のネットワークと同じ論理アドレスを持っていてもよい.)
ホストの番号は所属するネットワーク内でユニークでなければならない.

IPアドレス
32bits
32bitsの8bits=1byteごとに区切って十進数表記ができる.
3 Minutes Networking No.21
この1バイトごとの区切りをIPアドレスではオクテットという.
IPアドレスのうち先頭16bitsがネットワーク番号,残り16bitsがホスト番号


【第22回】レイヤ3 クラスフルアドレッシング
インターネットの管理者
IPアドレスは32bitsで4つのオクテットに分かれている.
ネットワーク番号は接続されている全てのネットワークでユニークでなければならない.
インターネットを管理する団体ICANNIPアドレスを管理するのにクラスという概念を用いている.

クラスフルアドレッシング
クラスとはネットワーク番号とホスト番号の比によってIPアドレスを分類した集合である.
3 Minutes Networking No.22Table22-01
IPアドレスの先頭の何ビットかでそのIPアドレスのクラスがどこに属しているのかを判断できる.
3 Minutes Networking No.22Table22-02
電話番号で東京と大阪の市外局番が2桁なのはネットワーク番号の大きさを減らして,ホストの大きさを確保するため.
このように国家に割り当てられるIPアドレスはホストが多いのでネットワーク番号が小さくホスト番号の多いクラスAのものが与えられ, 中小企業はクラスCのものが割り当てられたりする.
このようにクラスに分けてIPアドレスを割り振る方式をクラスフルアドレッシングという.
NIC(Network Informatino Center)が割り当てるのはネットワーク番号までで各ホストのIPアドレスはそのネットワークの管理者が割り当てる.

予約済みアドレス
特別な意味を持つためホスト番号として使ってはいけないアドレス
ホスト番号のビットが全て0か1になるアドレス
ホスト番号が全て0のアドレスをネットワークアドレス
ホスト番号が全て1のアドレスをブロードキャストアドレス
という.
ネットワークアドレスはそのネットワーク自体を表す.
ブロードキャストアドレスはそのネットワーク内の全員が受け取るアドレス.
よって各ネットワークで保有できるホスト数はホスト番号がnビットだとすると2^n-2個