NTU-Coursera机器学习:HomeWork 1 Q15-20

Question15

训练数据格式如下：

输入有4个维度，输出为{-1，+1}。共有400条数据。

题目要求将权向量元素初始化为0，然后使用“Naive Cycle”遍历训练集，求停止迭代时共对权向量更新了几次。

所谓“Naive Cycle”指的是在某数据条目x(i)上发现错误并更新权向量后，下次从x(i+1)继续读数据，而不是回到第一条数据x(0)从头开始。

#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
#define DEMENSION 5                //数据维度
 
double weights[DEMENSION];         //权重向量
int step= 0;                       //迭代次数
int length = 0;                    //数据条目个数
int index = 0;                     //当前数据条目索引
bool isFinished = false;           //迭代终止状态
char *file = "training_data.txt";
 
struct record {
    double input[DEMENSION];   //输入
    int output;                //输出   
};
vector<record> trainingSet;        //训练数据
 
int sign(double x)
{
    if(x<0)       return -1;
    else if(x>0) return 1;
    else         return -1;
}
 
//两个向量相加，更新第一个向量
void add(double *v1, double *v2, int demension)
{
    for(int i=0;i<demension;++i){ v1[i] = v1[i] + v2[i]; }
}
 
//两个向量相乘,返回内积
double multiply(double *v1, double *v2, int demension)
{
    double innerProd = 0.0;
    for(int i=0;i<demension;++i){
        innerProd += v1[i] * v2[i];
    }
    return innerProd;
}
 
//向量与实数相乘，结果通过*result返回，不改变参与计算的向量
void multiply(double *result, double *v, double num, int demension)
{
    for(int i=0;i<demension;++i){ result[i] = v[i] * num; }
}
 
//读取所有训练数据
void getData(ifstream & dataFile)
{
    while(!dataFile.eof()){
        record curRecord;
        curRecord.input[0] = 1;      
        for(int i=1;i<DEMENSION;++i){ dataFile>>curRecord.input[i]; }
        dataFile>>curRecord.output;
        trainingSet.push_back(curRecord);
    }
    dataFile.close();
    length = trainingSet.size();
}
 
void PLA()
{
    int start = index;
    double curInput[DEMENSION];
         
        //找到下一个错误记录的index
    while( trainingSet[index].output == 
    sign(multiply(weights,trainingSet[index].input,DEMENSION)) )
    {  
        if(index==length-1) {index = 0;}
        else            {index++;}
        if(index==start)    {isFinished = true; break;}  //没发现错误，迭代结束
    }
 
    if(isFinished){
        cout<<"计算结果：step = "<<step<<", weights = \n";
        for(int i=0;i<DEMENSION;++i){ cout<<weights[i]<<endl; }  
        return;
    }else{
        step++;
                 
                //更新: weights = weights + curOutput * curInput
        multiply( curInput, trainingSet[index].input, 
            trainingSet[index].output, DEMENSION );  
        add( weights, curInput, DEMENSION );   
 
        if(index==length-1) {index = 0;}
        else            {index++;}
 
        PLA(); 
    }
    return;
}
 
void main()
{  
    ifstream dataFile(file);
 
    if(dataFile.is_open()){
        getData(dataFile);     
    }else{
        cerr<<"ERROR ---> 文件打开失败"<<endl;
        exit(1);
    }
 
    for(int i=0;i<DEMENSION;++i){ weights[i] = 0.0; }
 
    PLA();
}

多次运行程序，迭代次数均为45次。

Question16

该题要求使用“fixed,pre-determined random cycle”对数据进行遍历，即对400条数据进行随机排序，然后在这轮计算中始终使用这一排序，直到下一轮计算开始再重新排序，重复2000次，求对权向量的平均修正次数。

#include <fstream>
#include <iostream>
#include <vector>
#include <ctime>
 
using namespace std;
 
#define DEMENSION 5                //数据维度
 
int step= 0;                       //迭代次数
int index = 0;                     //当前数据条目索引
bool isFinished = false;           //迭代终止状态
char *file = "training_data.txt";
 
struct record {
    double input[DEMENSION];   //输入
    int output;                //输出   
};
 
 
 
int sign(double x)
{
    //同Q15
}
 
void add(double *v1, double *v2, int demension)
{
    //同Q15
}
 
//两个向量相乘,返回内积
double multiply(double *v1, double *v2, int demension)
{
    //同Q15
}
 
//向量与实数相乘，结果通过*result返回，不改变参与计算的向量
void multiply(double *result, double *v, double num, int demension)
{
    //同Q15
}
 
//对 traininig set 创建一个随机排序
void setRandomOrder(vector<record> &trainingSet, vector<int> &randIndexes)
{
    srand((unsigned)time(NULL)); 
    int length = trainingSet.size();
    vector<bool> assignedIndexes(length,false);    
 
    for(int i=0;i<length;++i){
        int randIndex = rand()%length;
        while(assignedIndexes[randIndex]==true){
            randIndex = rand()%length;   
        }
        randIndexes.push_back(randIndex); 
        assignedIndexes[randIndex] = true;       
    }
}
 
//读取所有训练数据
void getData(ifstream & dataFile, vector<record> &trainingSet)
{
    while(!dataFile.eof()){
        record curRecord;
        curRecord.input[0] = 1;      
        for(int i=1;i<DEMENSION;++i){ dataFile>>curRecord.input[i]; }
        dataFile>>curRecord.output;
        trainingSet.push_back(curRecord);
    }
    dataFile.close();  
}
 
 
void PLA(vector<record> &trainingSet, vector<int> &randIndexes, double *weights)
{
    int length = trainingSet.size();
    int start = index;  
    double curInput[DEMENSION];
         
        //找到下一个错误记录的index
    while( trainingSet[randIndexes[index]].output == 
        sign(multiply(weights,trainingSet[randIndexes[index]].input,DEMENSION)) ){
        if(index==length-1) {index = 0;}
        else                {index++;}
        if(index==start)    {isFinished = true; break;}  //没发现错误，迭代结束
    }
 
    if(isFinished){
        return;
    }else{
        step++;
                 
                //更新: weights = weights + curOutput * curInput
        multiply( curInput, trainingSet[randIndexes[index]].input, 
            trainingSet[randIndexes[index]].output, DEMENSION ); 
        add( weights, curInput, DEMENSION );   
 
        if(index==length-1) {index = 0;}
        else                {index++;}
 
        PLA(trainingSet, randIndexes, weights);  
    }
    return;
}
 
void main()
{
    int totalSteps = 0;
 
    for(int i=0;i<2000;++i){
 
        double weights[DEMENSION];      //权重向量
        vector<record> trainingSet;     //训练数据
        vector<int> randIndexes;        //访问数据的随机索引列表
        ifstream dataFile(file);
 
        step = 0;            
        index = 0;               
        isFinished = false;   
 
        if(dataFile.is_open()){
            getData(dataFile,trainingSet); 
            setRandomOrder(trainingSet,randIndexes);
        }else{
            cerr<<"ERROR ---> 文件打开失败"<<endl;
            exit(1);
        }
 
        for(int i=0;i<DEMENSION;++i){ weights[i] = 0.0; }
 
        PLA(trainingSet, randIndexes, weights);
        totalSteps += step;
    }
 
    cout<<"Average Step = "<<totalSteps/2000<<endl;
}

Question17

本题要求在更新权向量时乘以一个0.5的系数，代码变动很少。

测试结果:

Question18

第18题要求在第16题 Random PLA 算法的基础上使用 Pocket 算法对数据做二元划分。Pocket算法在博文NTU-Coursera机器学习:機器學習問題与二元分類 介绍过，通常用来处理有杂质的数据集，在每一次更新 Weights（权向量）之后，把当前犯错最少的Weights放在pocket中，直至达到指定迭代次数(50次)，pocket中的Weights即为所求。然后用测试数据验证W(pocket)的错误率，进行2000次计算取平均。

#include <fstream>
#include <iostream>
#include <vector>
#include <ctime>
 
using namespace std;
 
#define DEMENSION 5                    //数据维度
 
int index = 0;                         //当前数据条目索引
int step = 0;                          //当前权向量更新次数
char *file = "training_data.txt";
char *file_test = "test_data.txt";
 
struct record {
    double input[DEMENSION];       //输入
    int output;                    //输出   
};
 
 
 
int sign(double x)
{
    //同Q16
}
 
//两个向量相加，更新第一个向量
void add(double *v1, double *v2, int demension)
{
    //同Q16
}
 
//两个向量相乘,返回内积
double multiply(double *v1, double *v2, int demension)
{
    //同Q16
}
 
//向量与实数相乘，结果通过*result返回，不改变参与计算的向量
void multiply(double *result, double *v, double num, int demension)
{
    //同Q16
}
 
//对 traininig set 创建一个随机排序
void setRandomOrder(vector<record> &trainingSet, vector<int> &randIndexes)
{
    //同Q16
}
 
//读取数据
void getData(ifstream & dataFile, vector<record> &data)
{
    //同Q16
}
 
//错误统计及Pocket向量更新
void errCountAndPocketUpdate(vector<record> &trainingSet, vector<int> &randIndexes, 
        double *weights, double *pocketWeights, double &trainingErrRate, int dataLength)
{
    int errCount = 0;
    double curTrainingErrRate = 1.0;
 
    for(int i=0;i<dataLength;++i){
        if(trainingSet[randIndexes[i]].output 
            != sign(multiply(weights,trainingSet[randIndexes[i]].input,DEMENSION))){
            errCount++;
        }  
    }
 
    curTrainingErrRate = double(errCount)/double(dataLength);
 
    if(curTrainingErrRate < trainingErrRate){
        trainingErrRate = curTrainingErrRate;
        for(int j=0; j<DEMENSION; ++j){
            pocketWeights[j] = weights[j];   
        }  
    }
}
 
 
void Pocket(vector<record> &trainingSet, vector<int> &randIndexes, double *weights, 
        double *pocketWeights, double &trainingErrRate)
{
    int length = trainingSet.size();
    double curInput[DEMENSION];   
 
    errCountAndPocketUpdate(trainingSet, randIndexes, weights, 
        pocketWeights, trainingErrRate, length);
         
        //找到下一个错误记录的index
    while( trainingSet[randIndexes[index]].output == 
        sign(multiply(weights,trainingSet[randIndexes[index]].input,DEMENSION)) ){
        if(index==length-1) {index = 0;}
        else                {index++;}
    }
     
    if(step<50){
        step++;
         
        //更新: weights = weights + curOutput * curInput
        multiply( curInput, trainingSet[randIndexes[index]].input, 
            trainingSet[randIndexes[index]].output, DEMENSION ); 
        add( weights, curInput, DEMENSION );   
 
        if(index==length-1) {index = 0;}
        else            {index++;}
 
        Pocket(trainingSet, randIndexes, weights, pocketWeights, trainingErrRate); 
    }else{     
        return;
    }
}
 
//统计 W(pocket) 在测试数据集上的错误率
double getTestErrRate(vector<record> &testSet, double *pocketWeights, int dataLength)
{
    int errCount = 0;
 
    for(int i=0;i<dataLength;++i){
        if(testSet[i].output != 
            sign(multiply(pocketWeights,testSet[i].input,DEMENSION))){
            errCount++;
        }  
    }
 
    return double(errCount)/double(dataLength);
}
 
 
void main()
{
    double totalTestErrRate = 1.0;
 
    for(int i=0;i<2000;++i){
 
        double weights[DEMENSION];              //当前权重向量
        double pocketWeights[DEMENSION];        //当前最优权重向量
        vector<record> trainingSet;             //训练数据
        vector<record> testSet;                 //测试数据
        vector<int> randIndexes;                //访问数据的随机索引列表
        ifstream dataFile(file);
        ifstream testDataFile(file_test);
        double trainingErrRate = 1.0;           //训练集中的错误率[0.0, 1.0]
        double testErrRate = 1.0;               //测试集中的错误率[0.0, 1.0]
 
        step = 0;            
        index = 0;                
 
        if( dataFile.is_open() && testDataFile.is_open() ){
            getData(dataFile,trainingSet); 
            getData(testDataFile,testSet); 
            setRandomOrder(trainingSet,randIndexes);
        }else{
            cerr<<"ERROR ---> 文件打开失败"<<endl;
            exit(1);
        }
 
        for(int j=0;j<DEMENSION;++j){ 
            weights[j] = 0.0; 
            pocketWeights[j] = 0.0;
        }
 
        Pocket(trainingSet, randIndexes, weights, pocketWeights, trainingErrRate);
 
        testErrRate = getTestErrRate(testSet,pocketWeights,testSet.size());
        totalTestErrRate += testErrRate;
 
        cout<<"\n  ********************   第 "<<i+1
        <<" 次计算结束   *************************  \n"<<endl;
    }
 
    cout<<"Average Perportion = "<<totalTestErrRate/2000<<endl;
}

测试结果:

Question19

题19要求用经过50次更新的W(50)进行验证，而不是W(pocket)，由于W(50)未必是当下最优，所以平均错误率一定会升高。代码几乎没有改动，只需在调用 getTestErrRate 函数是传入W(50)的指针即可。

测试结果:

Question20

本题要求把 Weights 的更新次数从50增加到100，可以预计平均错误率是降低的。

测试结果:

关于Machine Learning更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.

NTU-Coursera机器学习:HomeWork 1 Q15-20

原文：http://blog.csdn.net/songzitea/article/details/43921789