k-means法

k-means法はプロトタイプベース(prototype-based)クラスタリングというカテゴリに属している.
アルゴリズムは以下の通りである.

1.クラスタの中心の初期値として,サンプル点からk個のセントロイドをランダムに選びだす.
2.各サンプルを最も近いセントロイドに割り当てる.
3.セントロイドに割り当てられたサンプルの中心にセントロイドを移動する.
4.サンプル点へのクラスタの割当が変化しなくなるか,ユーザー定義の許容値またはイテレーションの最大回数に達するまでステップ2-3を繰り返す.

ステップ4について,オブジェクトの類似度を測定するにはm次元空間にある2つの点
xベクトルとyベクトルのユークリッド距離の2乗は

パターン識別

LBG+splitting
εはセントロイドから最も遠い特徴ベクトルの1/100倍したベクトルの場合

【Calc】セル内改行

LibreOfficeCalcのセル内改行をするショートカット
Ctrl + Enter

ABC022_C

頂点1を含まないグラフを考えてその最短経路を作れば良いと思ったが
頂点1を含まないグラフの作り方 == 頂点1に隣接している頂点の選び方O(N^2)
dijkstra法O(N^2)
よって全体でO(N^4)掛かってしまい案の定TLEだった.

#include <bits/stdc++.h>
using namespace std;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
static const int INF = 1<<21;
static const int MAX_N = 300;
static const int MAX_M = 45000;
int n,m;
int res = INF;
int u[MAX_M],v[MAX_M],l[MAX_M];
int M[MAX_N][MAX_N];
int color[MAX_N],d[MAX_N];

void dijkstra(int s){//最短経路を求める
    int mincost;
    //初期化：全ての頂点uに対してcolor[u]をWHITE,d[u]をINF,d[s]=0,p[s]=-1;
    for(int u=0;u<n;u++){
        color[u] = WHITE;
        d[u] = INF;
    }
    d[s] = 0;
    color[s] = GRAY;

    while(1){
        mincost = INF;
        int u = -1;
        for(int i=0;i<n;i++){
            if(color[i]!=BLACK && d[i]<mincost){
                mincost = d[i];
                u = i;
            }
        }
        if(u==-1){
            break;
        }
        color[u] = BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK && M[u][v]!=INF){
                if(d[v]>d[u]+M[u][v]){
                    d[v] = d[u]+M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u[i]>>v[i]>>l[i];//家u[i]から家v[i]までの距離がl[i]
    }
    //隣接グラフにする
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            M[i][j] = INF;
        }
    }
    for(int i=0;i<m;i++){
        M[u[i]-1][v[i]-1] = l[i];
        M[v[i]-1][u[i]-1] = l[i];
    }
    //始点1に隣接する接点を2つ選ぶ
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(M[0][i]!=INF && M[0][j]!=INF){//始点に2つ隣接する頂点があったら
                int tmp1 = M[0][i];
                int tmp2 = M[0][j];
                M[0][i] = INF;
                M[0][j] = INF;
                dijkstra(i);
                res = min(res,tmp1 + tmp2 + d[j]);
                M[0][i] = tmp1;
                M[0][j] = tmp2;
            }
        }
    }
    if(res==INF)res = -1;
    cout<<res<<endl;
    return 0;
}

そこでwarshall_froyd法を用いた.
warshall_floyd法はグラフの全ての頂点の間の最短路を見つけるアルゴリズム.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<vector<int> > Matrix;

const int INF = 1<<21;
Matrix d;//隣接行列

void warshall_floyd(int n){//n：頂点数
    for(int i=0;i<n;i++){//経由する頂点
        for(int j=0;j<n;j++){//開始頂点
            for(int k=0;k<n;k++){//終端
                d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n;
    d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF
    for(int i=0;i<n;i++){
        d[i][i] = 0;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int from,to,cost;
        cin>>from>>to>>cost;
        d[from][to] = cost;
        d[to][from] = cost;
    }

    warshall_floyd(n);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && d[i][j]!=INF){
                cout<<i<<"から"<<j<<"へのコスト："<<d[i][j]<<endl;
            }
        }
    }
    return 0;
}

最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会
abc022.contest.atcoder.jp
解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static const int MAX_N = 300;
typedef vector<vector<int> > Matrix;

const int INF = 1<<29;
Matrix d;//隣接行列

void warshall_floyd(int n){//n：頂点数
    for(int i=1;i<n;i++){//経由する頂点
        for(int j=1;j<n;j++){//開始頂点
            for(int k=1;k<n;k++){//終端
                d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n;
    d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF
    for(int i=0;i<n;i++){
        d[i][i] = 0;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int from,to,cost;
        cin>>from>>to>>cost;
        d[from-1][to-1] = cost;
        d[to-1][from-1] = cost;
    }

    //WFで頂点1以外の最短経路を更新
    warshall_floyd(n);

    //頂点1から隣接した2点に
    int res = INF;
    for(int i=1;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            res = min(res,d[0][i]+d[0][j]+d[i][j]);
        }
    }
    cout<<(res!=INF?res:-1)<<endl;
    return 0;
}

ABC007_C

幅優先探索の問題
queueにいれて順番に計算していく.
座標を扱う際にtypedefが便利

typedef pair<int,int> P;
que.push(P(x,y));

#include <bits/stdc++.h>
using namespace std;
int r,c,sx,sy,gx,gy;
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
static const int MAX_R =50;
static const int INF = 1<<21;
char M[MAX_R][MAX_R+1];
int D[MAX_R][MAX_R];
typedef pair<int,int> P;

int main()
{
    queue<P> que;
    cin>>r>>c>>sy>>sx>>gy>>gx;
    sy--;sx--;gy--;gx--;
    string tmp;
    for(int y=0;y<r;y++){
        cin>>tmp;
        for(int x=0;x<c;x++){
            M[y][x] = tmp[x];
            D[y][x] = INF;
        }
    }
    D[sy][sx] = 0;
    que.push(P(sx,sy));
    while(!que.empty()){
        P p = que.front();que.pop();
        int x = p.first;
        int y = p.second;
        if(x==gx && y==gy)break;
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<c && 0<=ny && ny<r && M[ny][nx]=='.' && D[ny][nx]==INF){
                que.push(P(nx,ny));
                D[ny][nx] = D[y][x] + 1;
            }    
        }
    }
    cout<<D[gy][gx]<<endl;
    return 0;
}

【c++】vectorの重複要素の削除

unique()は配列の長さは変わらないため重複で削除された空きの場所にゴミが入る

#include <bits/stdc++.h>
using namespace std;
void printVector(vector<int> &v){
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<endl;
    }
}
int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(3);
    vec.push_back(3);
    printVector(vec);
    unique(vec.begin(),vec.end());
    cout<<"-----------------------"<<endl;
    printVector(vec);
    return 0;
}
/*
1
2
2
3
3
3
-----------------------
1
2
3
3//ゴミ
3//ゴミ
3//ゴミ
*/

あらかじめソートして,vec.erase()で重複部分を消す.
unique(vec.begin(),vec.end())はゴミの前を指している.
そこからvec.end()までのゴミ部分を削除するとうまく重複部分を消すことができる.

#include <bits/stdc++.h>
using namespace std;
void printVector(vector<int> &v){
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<endl;
    }
}
int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(3);
    vec.push_back(3);
    printVector(vec);
    sort(vec.begin(),vec.end());//ソート
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    cout<<"-----------------------"<<endl;
    printVector(vec);
    return 0;
}
/*
1
2
2
3
3
3
-----------------------
1
2
3
*/

重複していない部分のサイズを取得するには

int* a = unique(vec.begin(),vec.end());//ゴミの手前を指す
int* b = vec.begin();//配列の先頭を指す
cout<<a-b<<endl;//重複していないサイズ

ABC019_C

2で割り切れたら割り続けて集合に入れる.
2で割り切るのは右ビットシフトと同義

a[i] /= 2;
a[i] = a[i]>>1;

a[i] =>>1;//これはダメ
a[i]>>1;//これもダメ

解答

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
static const int MAX_N = 100000;
set<int> S;
int a[MAX_N];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        while(a[i]>1 && !(a[i]%2)){//2で割り続ける
            a[i]=a[i]>>1;
        }
        S.insert(a[i]);
    }
    cout<<(int)S.size()<<endl;
    return 0;
}

ABC030_C

飛行機で何往復できるかという問題
普通にやると大変なのでlower_bound()による二分探索を使った.
lower_bound(a,a+n,value)はvalue以上の値の位置を返す.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[5] = {1,3,5,7,9};
    int* pos = lower_bound(a,a+5,8);//8を初めて越すのはa[4]:9
    cout<<pos-a<<endl;//4
    cout<<*pos<<endl;//9
    return 0;
}

配列aの範囲内に有るか無いかを条件文で判断するには

if(pos-a<n)//ある
else //ない

を用いた.
もっと良い方法がありそうだが…
解答

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x,y;
    int a[100000],b[100000];
    cin>>n>>m>>x>>y;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    int cur = 0;
    int *pos;
    int res = 0;
    int flag = 1;//flag = 1ならばAにいる
    while(1){
        if(flag){
            pos = lower_bound(a,a+n,cur);//curより大きい最初の位置
            if(pos-a<n){
                cur = *pos+x;//飛行機に乗る
                flag = 0;
            }else{
                break;
            }
        }else{
            pos = lower_bound(b,b+m,cur);
            if(pos-b<m){
                cur = *pos+y;
                res++;
                flag = 1;
            }else{
                break;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

アニメop顔検出器+分類器

うまく分類できないな
もっと精度あげたい pic.twitter.com/nEsDQc7Vio

— 雨宿まち (@vocky_Zn) 2017年3月31日

今後すること

• トレーニング画像の種類を増やす.
• 出力層の出力を増やして分類の数を増やす.

【python】ファイルの書き込み

追記でテキストファイルに書き込み

f = open("test.txt","a")
f.write("hoge\n")
f.close()

qiita.com

【python】ファイルやディレクトリの有無を調べる

import os.path
os.path.exists(path)#True or False

ファイルやディレクトリの有無を調べる - Python Tips

【Python】namedtupple

>>>from collections import *
>>> # Basic example
>>> Point = namedtuple('Point', ['x', 'y'])
>>> p = Point(11, y=22)     # instantiate with positional or keyword arguments
>>> p[0] + p[1]             # indexable like the plain tuple (11, 22)
33
>>> x, y = p                # unpack like a regular tuple
>>> x, y
(11, 22)
>>> p.x + p.y               # fields also accessible by name
33
>>> p                       # readable __repr__ with a name=value style
Point(x=11, y=22)

8.3. collections — コンテナデータ型 — Python 3.6.1 ドキュメント

tensorflowのdata_input()でMNISTを読み込んだ時のMNISTのデータ型

print(type(mnist))
<class 'tensorflow.contrib.learn.python.learn.datasets.base.Datasets'>

TensorFlow内での定義

Datasets = collections.namedtuple('Datasets', ['train', 'validation', 'test'])#line 37

github.com

CNNで画像の前処理

判定処理を行う入力画像の前処理
1.画像の周囲を切り落とす(Cropping)
2.画像のダイナミックレンジを平準化する(Whitening)

トレーニングデータとして入力する画像にする前処理
1.画像の周囲をランダムに切り落とす(Random Cropping)
2.画像をランダムに左右反転する(Random Flipping)
3.画像の明るさとコントラストをランダムに変更する
4.画像のダイナミックレンジを平準化する(Whitening)

【python】【機械学習】Jupyterの起動方法

jupyterはanacondaに入っている.

$jupyter notebook
$ipython notebook

右上の選択画面からpython2を選んでコードを書く.

【ubuntu】管理者権限について

Ubuntuではデフォルトで一般ユーザとなるので新たに管理者権限を設定しなくてはいけない.

$sudo passwd