2015-10-30

rubyでRANSAC

研究で必要になったから調べてみた

観測したデータから最小二乗法などでモデルを推定する際に、観測したデータに外れ値が混じっていた場合、推定したモデルは外れ値に引っ張られてしまいます。そこで、RANSACアルゴリズムを利用することで、外れ値を無視したモデルの推定を行うことが出来ます

RANSACアルゴリズム

1.観測データ群からランダムに幾つかのデータを取り出す
2.取り出したデータを用いてモデルを推定
3.推定したモデルに対して、観測データ群を適用し、モデルを評価する
4.1～3を複数回行い、一番評価が高いモデルを採用

意外とシンプルなアルゴリズムです。

実験

今回は、直線のモデルを最小二乗法で推定します。
直線のモデルなんで、
${Y = aX + b}$
のaとbの部分を推定します。

今回は正解のモデルを
${Y = X}$
っぽい直線としました。
正解データは

(1- rand() / 10) * x

また外れ値は

rand(0.0..5.0) * x

として生成しました。

ちなみにxは1から100までの整数です。
グラフの描画はgnuplotなるライブラリを使いました。

まずは外れ値なしの最小二乗法から

f:id:ogidow:20151030230915j:plain

なかなかよい感じ

続いて、外れ値ありの最小二乗法

f:id:ogidow:20151030231407j:plain

めっちゃ外れ値に引っ張られてます。

最後にRANSAC使った場合です。

f:id:ogidow:20151030231604j:plain

きれいに外れ値を無視してくれました。

RANSACは簡単に実装できて、強力なんですが、
複数回、モデルの推定を行って、それを更に観測データ群に適応させるので、
計算量がめっちゃ大きい感じがします。

実際にRANSACを使う場合には工夫が必要かもしれません

ちなみに今回書いたコードはこんな感じです。

2015-10-15

c++でイベント駆動っぽくTCPを書いた

プログラミング c++

github.com

思いつきでc++でイベント駆動っぽいTCPのクラス書いてみた

これでTCPのサーバーとクライアント両方ともイベント駆動っぽくかける

試しにエコーサーバ

サーバ

#include <iostream>
#include "TCPEventServer.h"

int main(void)
{

	eventTCP server(5432);

	server.on("connect", [](Socket *sock){
		std::cout << "connect" << std::endl;
		sock->on("echo", [sock](std::string data){
			std::cout << data << std::endl;
			sock->emit("echo", data);
		});

		sock->on("disconnect", [sock](std::string data){
			std::cout << "disconnect" << std::endl;
			sock->close();
		});
	});

	server.listen(5);
	
	return 0;
}

クライアント

#include <iostream>
#include "TCPEventClient.h"

int main(void)
{
	TCPEventClient client;

	client.connect("127.0.0.1", 5432);

	client.on("connect", [](Socket *sock){
		std::cout << "connect" << std::endl;
		sock->on("echo", [sock](std::string data){
			std::cout << data << std::endl;
		});

		sock->on("disconnect", [sock](std::string data){
			sock->close();
		});

		sock->emit("echo", "echo server");
	});

	return 0;
}

c++毛嫌いしてたけど、c++11からは結構よさげ

2015-10-08

rubyでオセロのコンソールアプリ作った

プログラミング ruby

rubyの勉強のためにオセロのコンソールアプリ作った

最近、C/C++しか書いてなかったから良い息抜きになった

できれば、webアプリまで発展させてオンライン対戦的なのも実装してみたい

その前に、ひどい実装になってしまったので時間あるときに直そう

github.com

2015-09-18

プロキシ切り替えるクロム拡張作った

プログラミングクロム拡張

学校のネットワークに繋いだら学校のプロキシに、家に戻ったらプロキシの自動検出に手動で切り替えてたのだけれども、
面倒くさかったから勉強も兼ねてクロム拡張を作った。

マニュフェストファイルはこんな感じ

{
  "manifest_version": 2,
  "name": "Proxy Changer",
  "version": "1.0",
  "description": "change http proxy",
  "browser_action": {
    "default_icon": "icon.png",
    "default_popup": "popup.html"
  },
  "permissions": [
    "tabs",
    "proxy"
  ],
  "icons" : {
    "128": "icon.png"
  }
}

続いてhtml

<!DOCTYPE HTML>

<html lnag="ja">
  <head>
    <meta charset="utf-8">
    <title>proxy changer</title>
  </head>
  <body>
    <button id="scholl">scholl proxy</button>
    <button id="outer">outer proxy</button>

    <script src="background.js"></script>
  </body>

</html>

window.onload=function(){
  document.getElementById("scholl").addEventListener("click", changeShollProxy);
  document.getElementById("outer").addEventListener("click", changeOuterProxy);
}

var config = {
    mode: "fixed_servers",
    rules: {
      proxyForHttp: {
        scheme: "http",
        host: "xx.xx.xx.xx",
        port: xxxx
      },
      bypassList: ["127.0.0.1"]
    }
  };


function changeShollProxy(){
  chrome.proxy.settings.set(
    {value: config, scope: "regular"},
    function(){}
  );
}

function changeOuterProxy(){
  config.mode = "auto_detect";
  chrome.proxy.settings.set(
    {value: config, scope: "regular"},
    function(){}
  );

}

html適当なのは許して
本当は

<button id="scholl" onclick="chagneSchollProxy">scholl</button>

みたいにしたかったけど、クロム拡張では出来ないみたい(違ってたらごめんなさい)。

参考
いまさらまとめるChrome ExtensionでのJavaScript挿入 - console.lealog();

https://developer.chrome.com/extensions/proxy

2015-09-18

バイト列の任意の位置から32ビット読み込んでint型として扱う

c言語プログラミング

TCPやUDPなどのネットワークプログラムを書いてると、受信したバイト列の任意の位置から32ビットを読み込んでint型として扱いたくなる時がある。

例えば、受信したバイト列に整数「123」が含まれているとする。

整数「123」はバイト列に直すと

00 00 00 7b

となる。実際には、バイト列には他のデータも含まれているので

00 00 00 64 00 00 00 7b 00 00 04 d2

みたいな感じになる(「00 00 00 7b」以外は適当)。

このバイト列から4バイト(00 00 00 7b)をうまく切り出してint型にキャストすると整数「123」を復元することができる。

c言語で書くとこんな感じ

#include <stdio.h>
typedef unsigend char UINT8;
typedef unsigned int UINT32;

UINT32 readUint32(UINT8 *bytes, int index){
  return (UINT32)((UINT32)(bytes[index] << 0) | ((UINT32)bytes[index + 1] << 8) | ((UINT32)bytes[index + 2] << 16) | ((UINT32)bytes[index + 3] << 24));
}

int main(void){
  UINT8 bytes[] ={0xd2m 0x04, 0x00, 0x00, 0x7b, 0x00, 0x00, 0x00, 0x64, 0x00, 0x00, 0x00};
  UINT32 temp;
  int *intVal;

  temp = readUint32(bytes, 4);
  intVal = (int *)&temp;

  printf("%d\n", *intVal);
  
  return 0;
}