NTU-Coursera機器學習:HomeWork 1 Q15-20

NTU-Coursera機器學習:HomeWork 1 Q15-20

Question15

訓練數據格式如下：

輸入有4個維度，輸出為{-1，+1}。共有400條數據。

題目要求將權向量元素初始化為0，然後使用“Naive Cycle”遍歷訓練集，求停止迭代時共對權向量更新了幾次。

所謂“Naive Cycle”指的是在某數據條目x(i)上發現錯誤並更新權向量後，下次從x(i+1)繼續讀數據，而不是回到第一條數據x(0)從頭開始。

#include 
#include 
#include 
 
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 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>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 = "< 文件打開失敗"<測試結果如下所示:
多次運行程序，迭代次數均為45次。
Question16
vc/C0rvC1rzGy+O/qsq81NnW2NDCxcXQ8qOs1ti4tDIwMDC0zqOsx/O21Mioz/LBv7XExr2++dDe1f20zsr9oaM8YnIgLz48L3A+PHA+PHByZSBjbGFzcz0="brush:java;">#include 
#include 
#include 
#include 
 
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 &trainingSet, vector &randIndexes)
{
    srand((unsigned)time(NULL)); 
    int length = trainingSet.size();
    vector assignedIndexes(length,false);    
 
    for(int i=0;i &trainingSet)
{
    while(!dataFile.eof()){
        record curRecord;
        curRecord.input[0] = 1;      
        for(int i=1;i>curRecord.input[i]; }
        dataFile>>curRecord.output;
        trainingSet.push_back(curRecord);
    }
    dataFile.close();  
}
 
 
void PLA(vector &trainingSet, vector &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 trainingSet;     //訓練數據
        vector randIndexes;        //訪問數據的隨機索引列表
        ifstream dataFile(file);
 
        step = 0;            
        index = 0;               
        isFinished = false;   
 
        if(dataFile.is_open()){
            getData(dataFile,trainingSet); 
            setRandomOrder(trainingSet,randIndexes);
        }else{
            cerr<<"ERROR ---> 文件打開失敗"<
Question17
本題要求在更新權向量時乘以一個0.5的系數，代碼變動很少。
測試結果:
Question18
第18題要求在第16題 Random PLA 算法的基礎上使用 Pocket 算法對數據做二元劃分。Pocket算法在博文NTU-Coursera機器學習:機器學習問題與二元分類        介紹過，通常用來處理有雜質的數據集，在每一次更新 Weights（權向量）之後，把當前犯錯最少的Weights放在pocket中，直至達到指定迭代次數(50次)，pocket中的Weights即為所求。然後用測試數據驗證W(pocket)的錯誤率，進行2000次計算取平均。
#include 
#include 
#include 
#include 
 
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 &trainingSet, vector &randIndexes)
{
    //同Q16
}
 
//讀取數據
void getData(ifstream & dataFile, vector &data)
{
    //同Q16
}
 
//錯誤統計及Pocket向量更新
void errCountAndPocketUpdate(vector &trainingSet, vector &randIndexes, 
        double *weights, double *pocketWeights, double &trainingErrRate, int dataLength)
{
    int errCount = 0;
    double curTrainingErrRate = 1.0;
 
    for(int i=0;i &trainingSet, vector &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 &testSet, double *pocketWeights, int dataLength)
{
    int errCount = 0;
 
    for(int i=0;i trainingSet;             //訓練數據
        vector testSet;                 //測試數據
        vector 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 ---> 文件打開失敗"<

Question19
題19要求用經過50次更新的W(50)進行驗證，而不是W(pocket)，由於W(50)未必是當下最優，所以平均錯誤率一定會升高。代碼幾乎沒有改動，只需在調用 getTestErrRate 函數是傳入W(50)的指針即可。
測試結果:
Question20
本題要求把 Weights 的更新次數從50增加到100，可以預計平均錯誤率是降低的。
測試結果:


關於Machine Learning更多討論與交流，敬請關注本博客和新浪微博songzi_tea.