Archives

char入力の先頭32bitをintに格納する

ビット演算とかほぼ初めてやったのでメモ


#include <stdio.h>

int main(void) {

	char* str = "1\n";

	int char_pos = 0; // 入力char配列の何番目を見ているか
    int bufint = 0x00000000;  // 右から8bitずつ押し込まれる配列

    while (char_pos < 4) {
        if ((0xff & str[char_pos]) == 0x0000000a) break; // 改行なら終了

        bufint = bufint << 8; // bufintを左に8bitシフト(右2つが00になる)
        // printf(": 0x%08x\n", (0xff & str[char_pos]));

        bufint = bufint | (0xff & str[char_pos]); // 32bitにしてOR演算
        ++char_pos;
    }

    printf("input: %s\n", str);
    printf("write: 0x%08x\n", bufint);

	return 0;
}

strが”1\n”なら結果は 0x00000031

“12121\n”なら”1212″までが格納されて0x31323132になる

4byteずつしかデータを送れない時とかに使う

visual studio 2013でx64構成でGoogle C++ Testing Framework(gtest)を使ってテストするまで

実はvisual studio 2013は学生なら無料で使えます。しかもvisual studio 2012から追加されたダークテーマはかっちょいい。フォントはゴミのようだけどMacTypeとRictyのおかげでどうにかなる。これは乗るしかない。

実はvisual studioは2013のバージョン名が12で2012のバージョン名が11でそれぞれ.NETのバージョンがあってとかそこに慣れるまでは殺意を覚えることも多々あるのですが、それはそれとして。

C++のテストはちょっと調べてみたところ、Boost.TestかGoogle C++ Testing Framework(gtest)が良さそうだった。テストのためだけにboostをムニャムニャするのは面倒くさそうなので、gtestを使う。以下はテストできるようになるまでの手順。

  • https://code.google.com/p/googletest/downloads/listから最新版gtestのzip(僕の場合はgtest-1.7.0.zipだった)をダウンロード
  • zipを適当な場所(C:\とか$(HOME)\とか)に展開
  • gtest-1.7.0\msvc\gtest.slnをvisual studio 2013で開く
  • 「一方向のアップグレード」とか言われる -> そのまま「OK」

スクリーンショット_121513_042923_PM

  • 何やらヤバそうな変換レポートがブラウザで開かれるが気にしない

スクリーンショット_121513_043151_PM

  • 「ソリューションエクスプローラー」から「ソリューション’gtest'(4プロジェクト)」を右クリック -> 「構成マネージャー」
  • 「アクティブソリューションプラットフォーム」 -> 「新規作成」
    • 「新しいプラットフォームを…」から「x64」を選択
    • 「設定のコピー元」は「Win32」のまんま
    • 「新しいプロジェクトプラットフォームを作成する」にチェックが入っていることを確認したら、「OK」

スクリーンショット_121513_044112_PM

  • プラットフォームが全部「x64」になっていることを確認して「閉じる」(ならない場合は、「設定のコピー元」を「<空>」にしている可能性がある)
  • いよいよ「メニュー」 -> 「ソリューションのビルド」を実行
  • もし下記のようなエラーが出たとしても、「gtestのテスト」(gtest_prod_testやgtest_unittest)が失敗しただけで肝心のgtestとgtest_mainは成功しているので無視して良い

「エラー 8 error C1041: プログラム データベース ‘HOGEHOGE\gtest-1.7.0\msvc\x64\debug\vc120.pdb’ を開けません。複数の CL.EXE が同じ .PDB ファイルに書き込む場合、/FS を使用してください。」

  • C:\Users\OHTA\Downloads\gtest-1.7.0\msvc\x64\Debugが出来て「gtest_maind.lib」と「gtestd.lib」が作成されていることを確認

これでライブラリファイルが作成されました。gtestソリューションを閉じます。次に、テストを実行したいプロジェクトを含んだソリューションをvisual studioで開きます。

  • アクティブソリューションプラットフォームはもちろん「x64」。なぜなら彼もまた特別な存在だからです
  • プロジェクトを右クリック -> 「プロパティ」 -> 「構成プロパティ」 -> 「C/C++」 -> 「コード生成」 -> 「ランタイムライブラリ」を「マルチスレッド デバッグ (/MTd)」にする
  • 「表示」 -> 「プロパティマネージャー」から「Debug | x64」をダブルクリック
    • 「共通プロパティ」 -> 「VC++ディレクトリ」の「インクルードディレクトリ」に「HOGEHOGE\gtest-1.7.0\include」を追加
    • 同様に「ライブラリディレクトリ」に「HOGEHOGE\gtest-1.7.0\msvc\x64\Debug」を追加
  • 「Release | x64」にも必要であれば同じパスを追加する

このプロジェクトは以下の3つのファイルから成り立っているとします。intをstringに変換して標準出力するだけです。

  • util.h
#ifndef _MYPROJECT_UTIL_H_
#define _MYPROJECT_UTIL_H_
#include <sstream>

std::string intToString(int number);

#endif
  • util.cpp
#include "util.h"
std::string intToString(int number)
{
  std::stringstream ss;
  ss << number;
  return ss.str();
}
  • main.cpp
#include <iostream>
#include "util.h"
using namespace std

int main()
{
  cout << intToString(2) << endl;
  return 0;
}

では、関数 intToString(int number)をテストしてみます。

まず新たにutilTest.cppファイルを追加します。

  • utilTest.cpp
#include <gtest/gtest.h>
#include "util.h"

#pragma comment( lib, "gtestd.lib" )
#pragma comment( lib, "gtest_maind.lib" )

TEST(IntToStringTest, Blackbox) {
  EXPECT_EQ("2", intToString(2)); // 成功するはず
  EXPECT_EQ("", intToString(2));  // 失敗するはず
}

そしたら、mainファイルに「テストしまっせ」と言ってもらいます。

#include <iostream>
#include <gtest/gtest.h>
#include "util.h"
using namespace std

int main(int argc, char **argv)
{
#ifdef _DEBUG
  ::testing::InitGoogleTest(&argc, argv);
  RUN_ALL_TESTS();
#endif

cout << intToString(2) << endl;
  return 0;
}

デバッグ時だけテストするようにしました。

これでF5でデバッグ開始します。

スクリーンショット_121513_061326_PM

IntToStringTestのBlackboxっていうテストが失敗しましたよ、と出てきます。失敗するはずのテストを書いているので当然です。main.cppがbaseAlgorithm.cppとなっていますがそういうこともあります。

今度は EXPECT_EQ(“”, intToString(2)); をコメントアウトしましょう。

スクリーンショット_121513_061707_PM

なんということでしょう。テストが通りました。

今まではassertだったので、これからテストの威力を実感したいところです。

C++で「はじめての機械学習」5章

5章は遺伝的アルゴリズムです。
ルーレット選択、一点交叉、突然変異、のsimpleGAです。最初は、目的関数最適化をめざすヒューリスティック。

/**
 * simpleGA:
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 **/

#include <iostream>
#include <string>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[], const int &lenGene)
{
    // 配列q中の数字を足すことで、最も499に近くなる組み合わせを探す。
    // 適応度が大きくなるほど最適となるように、1000から引いている。
    // このサンプルでは遺伝子数は20でなければならない。
    int q[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84,
        -62, -64, -33, -83, -27, -95, -2, -88, -41, -97};
    int fitness = 0;
    for(int i=0; i<lenGene; ++i){
        fitness += gene[i] * q[i];
    }

    return 1000 - abs(499 - fitness);
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], lenGene);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**真理値の反転(突然変異に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], lenGene);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度

    // 引数のチェック
    if(argc != 5){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "> (出力ファイル)" << endl;
        return -1;
    }
    if((lenGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の桁数が不適切です" << endl;
        return -1;
    }
    if((numGene=atoi(argv[2])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[3]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限" << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[4])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[4]);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

後半は、4章の論理式によるカテゴリ分類の組み合わせ最適化用にsimpleGAを書き換えます。

/**
 * gaml:
 * 各データの、特徴ごとの分類と含まれるカテゴリを入力データとして、
 * 最もデータを効率良く分類する特徴の組み合わせを探索する。
 * 遺伝子の桁数は、特徴数*2(否定)に分類回数をかけたものとなる。
 * 評価値は、分類率を%で表す。つまり100点満点。
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の数) (終了条件スイッチ) (終了条件)
 *              < (入力ファイル) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 * 入力ファイル(例):
 *  3        <-分類回数
 *  4        <-特徴数
 *  1 0 1 1 1   <-各特徴に対する分類と、最後にカテゴリ
 *  0 1 0 0 1
 *      :
 *      :
 **/

#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**真理値の反転(突然変異と論理式評価に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**特定のデータに対する分類が正しいかを返す**/
int evaluate(const int gene[],
                const vector<int> &dataField,
                const int &numTerm, const int &numAttribute)
{
    int orValue, andValue, result;
    andValue = 1;
    // 論理積で項を結んだ、式全体の評価
    for(int i=0; i<numTerm; ++i){
        orValue = 0;
        // 論理和で結んだ項の評価
        for(int j=0; j<numAttribute*2; ++j){
            if((j%2) == 0) orValue += dataField[j/2] * gene[i*numAttribute*2+j];
            else orValue += notVal(dataField[j/2]) * gene[i*numAttribute*2+j];
        }
        if(orValue == 0) andValue = 0;
        else andValue += 1;
    }

    // 結果がカテゴリと不一致
    if(andValue == gene[numAttribute]) return 1;
    // 一致
    else return 0;
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[],
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute)
{
    int point = 0; // 正しく分類されたデータの個数
    for(int i=0; i<data.size(); ++i){
        point += evaluate(gene, data[i], numTerm, numAttribute);
    }
    // 評価値(100点満点)を返す
    return 100*point / data.size();
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene,
            const vector< vector<int> > &data,
            const int &numTerm, const int &numAttribute)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], data, numTerm, numAttribute);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], data, numTerm, numAttribute);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度
    int     numTerm;             // 論理式の論理和項の個数
    int     numAttribute;        // 属性値の個数
    vector< vector<int> > data;  // 入力データ

    // 引数のチェック
    if(argc != 4){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "< (入力ファイル) > (出力ファイル)" << endl;
        return -1;
    }
    if((numGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[2]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限"   << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[3])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[3]);
    }

    // データ入力
    cin >> numTerm;
    cin >> numAttribute;
    lenGene = numTerm*(numAttribute*2);
    while(true){
        // データをdataBufferに読み込む
        int dataBuffer[numAttribute+1];
        cin >> dataBuffer[0];
        if(cin.eof()) break;
        for(int i=1; i<numAttribute+1; ++i){
            cin >> dataBuffer[i];
        }
        // dataBufferをrowBufferにコピー
        vector<int> rowBuffer;
        for(int i=0; i<numAttribute+1; ++i){
            rowBuffer.push_back(dataBuffer[i]);
        }
        // rowBufferをdataに追加
        data.push_back(rowBuffer);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene,
                            data, numTerm, numAttribute, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, data,
                            numTerm, numAttribute, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

習作やるかなーやらない気がするが

C++で「はじめての機械学習」6章

与えられたデータセットと評価値に近づくように重みとしきい値を
バックプロパゲーションで調整する3層パーセプトロン

2章と3章
4章

/**
 * バックプロパゲーションによるニューラルネットの学習
 * 使い方
 *  $./backPropagation (変数の数) (中間層のセル数) (誤差の上限値) < (学習データセットのファイル名)
 *誤差の推移や、学習結果となる結合係数などを出力します
 **/

#include <iostream>
#include <vector>
#include <cstdlib>
#include <float.h>
#include <ctime>
#include <cmath>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

/**シグモイド関数**/
inline double sigmoid(double u)
{
    return 1.0 / (1.0+exp(-u));
}

/**-1.0 - 1.0の実数乱数の生成**/
inline double randDouble()
{
    return (2.0 / RAND_MAX * rand())-1.0;
}

/**中間層の重みと出力層の重みを初期化(ランダム)**/
void initWeight(const int &n, const int &numAlliance,
                double **weightAlliance,  double *weightReaction)
{
    initRand();
    for(int i=0; i<numAlliance; ++i){
        for(int j=0; j<n+1; ++j){
            weightAlliance[i][j] = randDouble();
        }
        weightReaction[i] = randDouble();
    }
    weightReaction[numAlliance] = randDouble();
}

/**学習データをdataに読み込む**/
void readData(vector< vector<double> > &data, const int &n)
{
    // [n]は評価値
    double *buffer = new double [n+1];
    while(true){
        for(int i=0; i<n+1; ++i) cin >> buffer[i];
        if(cin.eof()) break;

        vector<double> bufferVector;
        for(int i=0; i<n+1; ++i) bufferVector.push_back(buffer[i]);

        data.push_back(bufferVector);
    }
}

/**順方向の出力の計算**/
double forward(double **weightAlliance, const double *weightReaction,
                double *outAlliance, const vector<double> &dataField,
                const int &n, const int &numAlliance)
{
    double out = 0.0;
    // outAllianceの計算
    for(int i=0; i<numAlliance; ++i){
        double u = 0; // 重み付き和
        for(int j=0; j<n; ++j){
            u += dataField[j] * weightAlliance[i][j];
        }
        u -= weightAlliance[i][n]; // しきい値の処理
        outAlliance[i] = sigmoid(u);
    }
    // outの計算
    for(int i=0; i<numAlliance; ++i)
        out += outAlliance[i] * weightReaction[i];
    out -= weightReaction[numAlliance]; // しきい値の処理

    return sigmoid(out);
}

/**出力層の重みの調整**/
void learnReaction(double *weightReaction, double *outAlliance,
                    const vector<double> &dataField, double outReaction,
                    const int &n, const int &numAlliance, const int &ALPHA)
{
    double diff; // 誤差
    diff = (dataField[n] - outReaction) * outReaction * (1 - outReaction);
    // 結合荷重の調整
    for(int i=0; i<numAlliance; ++i)
        weightReaction[i] += ALPHA * outAlliance[i] * diff;
    // しきい値の調整
    weightReaction[numAlliance] += ALPHA * (-1.0) * diff;
}

/**中間層の重みの調整**/
void learnAlliance(double **weightAlliance, double *weightReaction,
                    double *outAlliance, const vector<double> &dataField, double outReaction,
                    const int &n, const int &numAlliance, const int &ALPHA)
{
    double diff; // 重みが考慮された誤差
    // i番目の中間層セルについて
    for(int i=0; i<numAlliance; ++i){
        diff = outAlliance[i] * (1 - outAlliance[i]) * weightReaction[i] *
                (dataField[n] - outReaction) * outReaction * (1 - outReaction);
        // j番目の重みを調整
        for(int j=0; j<n; ++j)
            weightAlliance[i][j] += ALPHA * dataField[j] * diff;
        weightAlliance[i][n] += ALPHA * (-1.0) * diff; // しきい値の調整
    }
}

/**結合荷重の出力**/
void printWeight(double **weightAlliance, double *weightReaction,
                    const int &n,  const int &numAlliance)
{
    for(int i=0; i<numAlliance; ++i){
        for(int j=0; j<n+1; ++j)
            cout << weightAlliance[i][j] << " ";
    }
    cout << endl;
    for(int i=0; i<numAlliance+1; ++i)
        cout << weightReaction[i];
    cout << endl;
}

int main(int argc, char *argv[])
{
    // 定数
    const int                ALPHA = 10;           // 学習係数

    // 変数
    int                      n;                    // 変数の数=入力層の数
    int                      numAlliance;          // 中間層のセル数
    double                   errorLimit;           // 誤差の上限値
    vector< vector<double> > data;                 // 学習データセット
    double                   **weightAlliance = 0; // 中間層層の重み
    double                   *weightReaction = 0;  // 出力層の重み
    double                   *outAlliance = 0;     // 中間層の出力
    double                   outReaction = 0;      // 出力層の出力
    double                   error = DBL_MAX;      // データとの誤差
    int                      count = 0;            // 繰り返し回数のカウンタ

    // 引数のチェック
    if(argc != 4){
        cerr << "使い方 $./backPropagation "
             << "(変数の数) (中間層のセル数) (誤差の上限値) "
             << "< (入力ファイル)" << endl;
        return -1;
    }
    if((n=atoi(argv[1])) < 1){
        cerr << "変数の数の値が不適切です" << endl;
        return -1;
    }
    if((numAlliance=atoi(argv[2])) < 1){
        cerr << "中間層のセル数が不適切です" << endl;
        return -1;
    }
    if((errorLimit=atof(argv[3])) == 0.0){
        cerr << "収束しない可能性があります" << endl;
    }

    // get memory
    weightAlliance = new double * [numAlliance];
    weightReaction = new double [numAlliance+1]; // [numAlliance]はしきい値
    for(int i=0; i<numAlliance; ++i) weightAlliance[i] = new double [n+1];
    outAlliance = new double [numAlliance];

    initWeight(n, numAlliance, weightAlliance, weightReaction);
    readData(data, n);

    // 学習
    while(error > errorLimit){
        error = 0.0;
        for(int i=0; i<data.size(); ++i){
            // 順方向の計算
            outReaction = forward(weightAlliance, weightReaction, outAlliance,
                                    data[i], n, numAlliance);
            // 出力層の重みの調整
            learnReaction(weightReaction, outAlliance,
                            data[i], outReaction, n, numAlliance, ALPHA);
            // 中間層の重みの調整
            learnAlliance(weightAlliance, weightReaction, outAlliance,
                            data[i], outReaction, n, numAlliance, ALPHA);
            // 誤差の積算
            error += (outReaction - data[i][n]) *
                        (outReaction - data[i][n]);
        }
        ++count;
        // 誤差の出力
        cout << count << "t" << error << endl;
    } // 学習終了

    // 結果の出力
    // 1.結合荷重の出力
    printWeight(weightAlliance, weightReaction, n, numAlliance);
    // 2.学習データに対する結果の出力
    for(int i=0; i<data.size(); ++i){
        cout << i << " ";
        for(int j=0; j<n+1; ++j)
            cout << data[i][j] << " ";
        outReaction = forward(weightAlliance, weightReaction, outAlliance,
                                data[i], n, numAlliance);
        cout << outReaction << endl;
    }

    // memory release
    for(int i=0; i<numAlliance; ++i) delete [] weightAlliance[i];
    delete [] weightAlliance;
    delete [] weightReaction;
    delete [] outAlliance;

    return 0;
}

5章はちょっと習作を思いついたのでまた今度になるかも

C++で「はじめての機械学習」4章

昨日の記事の続きです。
4章は判断木の構成で、データの属するカテゴリと各属性に対する判別結果を入力データとして与え、どの判断を用いて分類すればよいかの選択を支援するプログラムと、後半ではそれを確率探索しています。
後半はまあいいかと思ったので前半部だけ。

/**
  判断木の構成を支援するプログラム
  (判断木を構成するためには、与えられたデータセットを
  適切に分類する属性を選択しなければならない。そこで
  ある属性を選んだ場合にどのように分類されるかを計算
  する。)
  入力は標準入力から与え、出力は標準出力に出力します
  使い方:
    $./decision < (入力ファイル名) > (出力ファイル名)
  入力ファイルでは、属性とカテゴリを0/1で記述します
  出力ファイルには、分類結果を表示します
 **/

#include <iostream>
#include <vector>
#include <sstream>
#include "utf8Func.hpp"
using namespace std;

int stringToInt(const string &str)
{
    int num;
    stringstream ss;
    ss << str;
    ss >> num;
    return num;
}

/**データを読み込んでvectorに格納**/
void readData(vector< vector<int> > &data)
{
    string line;
    while(getline(cin,  line)){
        vector<string> bufferString = split_utf8(line);
        vector<int>    bufferInt;
        for(int i=0; i<bufferString.size(); ++i){
            bufferInt.push_back(stringToInt(bufferString[i]));
        }
        data.push_back(bufferInt);
    }
}

/**属性の評価**/
void evaluateProperty(const vector< vector<int> > &data, const int &i, const int &answer)
{
    int numTotal = 0;
    int numCorrect = 0;
    for(int j=0; j<data.size(); ++j){
        // 求める解答をしているデータがあれば
        if(data[j][i] == answer){
            ++numTotal;
            // 解答が正しい分類に合致していたら
            if(data[j][i] == data[j].back()) ++numCorrect;
        }
    }
    cout << numCorrect << "/" << numTotal << "t"
         << (double)numCorrect/numTotal << endl;
}

int main()
{
    // 解答番号
    const int yes = 1;
    const int no  = 0;

    vector< vector<int> > data;
    readData(data);

    // 各属性による分類
    for(int i=0; i<data[0].size()-1; ++i){
        cout << "property" <<  i+1 << endl;
        // Yesに対応した学習データの数え上げ
        cout << "Yes" << "t";
        evaluateProperty(data,  i,  yes);
        // Noに対応した学習データの数え上げ
        cout << "No" << "t";
        evaluateProperty(data,  i,  no);
        cout << endl;
    }

    return 0;
}

utf8Func.hppはこれ

#ifndef __UTF8FUNC_HPP__
#define __UTF8FUNC_HPP__

#include <vector>
#include <string>

/**utf-8のstringを一文字ずつ分割する**/
std::vector<std::string> split_utf8(const std::string& str) {
    std::vector<std::string> result;
    std::string              tmp;
    bool                     first = true;

    for (size_t i=0; i<=str.size(); ++i) {
        // 各バイトがutf-8の先頭かどうかをチェック
        if (first ||
                (i != str.size() && (str.at(i) & 0xC0) == 0x80)) {
            tmp += str.at(i);
            first = false;
            continue;
        }
        result.push_back(tmp);
        tmp.clear();
        if (i == str.size()) break;
        tmp += str.at(i);
    }
    return result;
};

#endif

5章は遺伝的アルゴリズムはいったん飛ばして、たぶん次は6章のニューラルネットワークのつもり

C++で「はじめての機械学習」2章, 3章

はじめての機械学習という機械学習の基本をC言語のソース付きで学べる書籍を読んでいるのだけど、しーぷらぷらーの僕としてはむず痒さを感じることもあるので、C++で実装をしてみることにする。

2章 最小二乗法

/**
  最小二乗法による計算式の決定
  y = a0 + a1*x の a0, a1を出力
 **/

#include <iostream>
using namespace std;

int main()
{
    double xi, yi;                                        // 入力データ
    double sxi=0, syi=0, sxiyi=0, sxi2=0; // 各項の計算結果
    double a0, a1;                                      // 係数
    int    n = 0;                                           // データの個数

    // データの入力
    cout << "データの組を入力:xi yi" << endl
         << "(ctrl+d で入力終了)" << endl;
    while (true){
        cin >> xi >> yi;
        if(cin.eof()) break;
        if(cin.good()==false){
            cout << "無効なデータです" << endl;
            cin.clear();
            cin.ignore(256, 'n');
        } else {
            sxi   += xi;
            syi   += yi;
            sxiyi += xi*yi;
            sxi2  += xi*xi;
            ++n;
        }
    }

    if(n<2){
        cout << "データは2組以上必要です" << endl;
        return -1;
    }

    // 係数の計算
    a0 = (sxi2*syi-sxiyi*sxi) / (n*sxi2-sxi*sxi);
    a1 = (n*sxiyi-sxi*syi) / (n*sxi2-sxi*sxi);

    cout << "y = " << a1 << "x + " << a0 << endl;

    return 0;
}

3章 n-gram

utf-8テキストからn-gramを生成
/**
  ngramを作成するプログラム(utf-8)
  入力は標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ngram (nの値) < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、テキストファイルを指定します
  出力ファイルには、ngramを出力します
 **/

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;

/**utf-8のstringを一文字ずつ分割する**/
vector<string> split_utf8(const string& str) {
    vector<string> result;
    string         tmp;
    bool           first = true;

    for (size_t i=0; i<=str.size(); ++i) {
        // 各バイトがutf-8の先頭かどうかをチェック
        if (first ||
                (i != str.size() && (str.at(i) & 0xC0) == 0x80)) {
            tmp += str.at(i);
            first = false;
            continue;
        }
        result.push_back(tmp);
        tmp.clear();
        if (i == str.size()) break;
        tmp += str.at(i);
    }
    return result;
}

/**ngramの出力**/
void printNgram(int n, const vector<string> &data)
{
    // 各文字についてその(n-1)文字後までbufferに追加
    for(int i=0; i<data.size()-n; ++i){
        string buffer;
        for(int j=i; j<i+n; ++j){
            buffer += data[j];
        }
        cout << buffer << endl;
    }
    cout << endl;
}

int main(int argc, char *argv[])
{
    int            n;       // ngramの長さ
    string         line;    // 行を格納
    vector<string> data;    // 全文章を一文字ずつ格納

    // 引数のチェック
    if(argc != 2){
        cerr << "使い方 $./ngram (nの値) "
            << "< (入力ファイル名) > (出力ファイル名)" << endl;
        return -1;
    }
    if((n=atoi(argv[1])) < 1){
        cerr << "nの値が不適切です" << endl;
        return -1;
    }

    // 一行ずつ取り出して各文字に分割
    while(getline(cin,  line)){
        vector<string> buffer = split_utf8(line);
        for(int i=0; i<buffer.size(); ++i){
            data.push_back(buffer[i]);
        }
    }

    // ngrmを生成
    printNgram(n,  data);

    return 0;
}
n-gramを集計
/**
  ngramの頻度分布を作成します
  標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ranking < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、ngramのファイルを指定します
  出力ファイルには、頻度分布を出力します
 **/

#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

string intToString(int num)
{
    stringstream ss;
    ss << num;
    return ss.str();
}

/**重複するngramを数えてresultに書き込む**/
map<int, string> countNgrams(const vector<string> &ngrams)
{
    map<int, string> result;                // <重複数, ngram>
    string           lastNgram = ngrams[0];
    int              numDuplicated = 1;

    // 辞書順にngramがソートされているので、
    // 一つ前のngramと同じなら重複数をインクリメントし、
    // 違えば一つ前のngramをresultに追加する
    for(int i=1; i<ngrams.size(); ++i){
        if(ngrams[i] == lastNgram) ++numDuplicated;
        else {
            // write result
            result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );
            lastNgram = ngrams[i];
            numDuplicated = 1;
        }
    }
    // write result(the last)
    result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );

    return result;
}

int main()
{
    vector<string>   ngrams;
    map<int, string> result; // <重複数, ngram>
    string           line;

    // read ngram
    while(getline(cin, line)) ngrams.push_back(line);

    sort(ngrams.begin(), ngrams.end());
    result = countNgrams(ngrams);

    // 降順で出力
    map<int, string>::iterator it = result.end();
    while(it != result.begin()){
        --it;
        cout << (*it).first << "t" << (*it).second << endl;
    }

    return 0;
}

 

ngramとかは結構おもしろい
続きはまた今度

※10月27日追記:n-gramの集計はmapだと回数が同じやつが許されないのでmultimapでやるべきでした。multimapバージョンは↓

/**
  ngramの頻度分布を作成します
  標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ranking < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、ngramのファイルを指定します
  出力ファイルには、頻度分布を出力します
 **/

#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

string intToString(int num)
{
    stringstream ss;
    ss << num;
    return ss.str();
}

/**重複するngramを数えてresultに書き込む**/
multimap<int, string> countNgrams(const vector<string> &ngrams)
{
    multimap<int, string> result;                // <重複数, ngram>
    string           lastNgram = ngrams[0];
    int              numDuplicated = 1;

    // 辞書順にngramがソートされているので、
    // 一つ前のngramと同じなら重複数をインクリメントし、
    // 違えば一つ前のngramをresultに追加する
    for(int i=1; i<ngrams.size(); ++i){
        if(ngrams[i] == lastNgram) ++numDuplicated;
        else {
            // write result
            result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );
            lastNgram = ngrams[i];
            numDuplicated = 1;
        }
    }
    // write result(the last)
    result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );

    return result;
}

int main()
{
    vector<string>   ngrams;
    multimap<int, string> result; // <重複数, ngram>
    string           line;

    // read ngram
    while(getline(cin, line)) ngrams.push_back(line);

    sort(ngrams.begin(), ngrams.end());
    result = countNgrams(ngrams);

    // 降順で出力
    map<int, string>::iterator it = result.end();
    while(it != result.begin()){
        --it;
        cout << (*it).first << "t" << (*it).second << endl;
    }

    return 0;
}

OpcnCV用alias

.profileに

alias makecv='g++ -O2 -Wall `pkg-config --cflags opencv` `pkg-config --libs opencv`'

 

としておけば、例えば hogeee.cppをコンパイルする場合

makecv hogeee.cpp -o hogeee

 

で実行ファイルhogeeeが作成されます。
さっとテストするためには必要ですね。

OpenGL(freeglut)ラッパーつくったよー

ここに上げてます。

github初公開レポジトリです。

win/mac/linいけます。openGL素晴らしい。

winではcygwinがfreeglutがなぜかダメだったのでvisualstudioで使って下さい。
あとmacもfreeglutがうまくいかないので、OpenGLWindow.cppの61行目”glutMouseWheelFunc(mouseWheelFunc)”をコメントアウトして下さい。
macports用のMakefileになってるので通常のmacでやりたい方は書き換えて下さい。

linはubuntu12.04で動作確認。でもvirtualbox上だからかもしれんがマウスホイールを拾ってくれませんでした。

とりあえず使い方は、

・OpenGLBase.cppの変数DIMENSIONを変えると平行投影、遠近法が切り替わります。(2で並行、3で遠近)
・同じくOpenGLBase.cppのmain内のwindowコンストラクタの引数でウインドウサイズと背景色決定(width, height, DIMENSION, red, green, blue)
・描画はDrawerクラスのdraw関数内に。
・時間変化はDrawerクラスのupdate関数内に。

・q or ESCで終了。
・sでアニメーションスタート。
・マウスホイール使えない時もzでズームイン、xでズームアウト。

だいたいこんな感じです。
ただのみんな持ってるラッパークラスなので機能は無いです。

詳しいこととか改善はまた気が向けば。

f:id:Drunkar:20120602051311p:image
謎すぎるサンプル画像。

netbeansでC++でOpenGL(GLUT)を動作させるまで

いままで初心者なりにvc++でコーディングをしていたのですが、windowsに特化した環境に慣れてしまうのはどうもなあ、と思ったのでとりあえず人気と言われるIDEのnetbeansを使ってみることにした。その導入の備忘録です。

まず、netbeansのサイトに行ってnetbeansをダウンロード&インストール。c++入のやつ。

それで次はcygwinのダウソ&インスコ。環境変数PATHにC:cygwinbinを追加。
ここで重要なのはOpenGL, GLUT関係のものと、X11をインストールすることと、すでにBorlandのC++コンパイラとかをインストールしている場合は、環境変数PATHに、C:borlandbcc55binよりも前にC:cygwinbinを置くこと。でないとErrorになります。

ここでnetbeansのツール>オプション>C/C++を見て

ベースディレクトリ:C:cygwinbin

Cコンパイラ:C:cygwinbingcc.exe

C++コンパイラ:C:cygwinbing++.exe

アセンブラ:C:cygwinbinas.exe

makeコマンド:c:cygwinbinmake.exe

となっていることを確認してください。

そしてnetbeansでC++アプリケーションを作って<GL/glut.h>をincludeして、ここで左上のウインドウのプロジェクトフォルダ(名前を付けなければCppApplication_1となるやつ)を右クリック>プロパティ>リンカー>ライブラリ>ライブラリを追加でGL.dllとかGLUT.dllとかglutを追加します。(ライブラリは通常C:cygwinlibにある)

あと、これが一番大事ですが同じく右クリック>実行>環境の、名前にDISPLAY、値に:0.0を追加します。これをしないとfailed to open display ‘ ‘というエラーが出ます。

そしてC++コードを実行する前に、スタートメニューに登録されていると思われるXWin Serverを起動し、タスクバーにアイコンが表示されていることを確認します。

これで、netbeansでOpenGL(GLUT)が実行できるはずです。winとmacとlinuxを使いこなせるね!(使いこなせたらいいな!)