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

せかいらぼ

 

4 Pockets

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; ...

せかいらぼ

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

４章は判断木の構成で、データの属するカテゴリと各属性に対する判別結果を入力データとして与え、どの判断を用いて分類すればよいかの選択を支援するプログラムと、後半ではそれを確率探索しています。後半はまあいいかと思ったので前半部だけ。/** 判断木の構成を支援するプログラム (判断木を構成するためには、与えられたデータセットを 適切に分類する属性を選択しなければならない。そこで ある属性を選んだ場合にどのように分類されるかを計算 する。） 入力は標準入力から与え、出力は標準出力に出力します 使い方： ...

せかいらぼ

 

1 Pocket

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

与えられたデータセットと評価値に近づくように重みとしきい値をバックプロパゲーションで調整する３層パーセプトロン/** * バックプロパゲーションによるニューラルネットの学習 * 使い方 * $./backPropagation (変数の数) (中間層のセル数) (誤差の上限値) < (学習データセットのファイル名) *誤差の推移や、学習結果となる結合係数などを出力します **/#include <iostream>#include <vector>#include <cstdlib>#include <float.h>#include <ctime>#include <cmath>using namespace std;inl...

www.amazon.co.jp

はじめての機械学習 | 小高 知宏 |本 | 通販 | Amazon

Amazonで小高 知宏のはじめての機械学習。アマゾンならポイント還元本が多数。小高 知宏作品ほか、お急ぎ便対象商品は当日お届けも可能。またはじめての機械学習もアマゾン配送商品なら通常配送無料。

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;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の２遺伝子の交叉(一点交叉)**/
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;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の２遺伝子の交叉(一点交叉)**/
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;
}

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