感知机学习算法实现

原始形式

/**
 *  感知机学习算法的原始形式
 */
#include 
#include 
#include 

using namespace std;

// 计算y_i(w*x_i+b)
double calSign(int y, vector w, vector x, double b)
{
    double wx = 0;
    for (int i = 0; i < w.size(); ++i)
    {
        wx += w[i] * x[i];
    }
    return y * (wx + b);
}

// 更新w, w <- w + eta*y_i*x_i void updatew(vector &w, int y, vector x, double eta)
{
    for (int i = 0; i < w.size(); ++i)
    {
        w[i] = w[i] + eta * y * x[i];
    }
}

// 更新b, b <- b + eta*y_i double updateb(double b, y, eta) { return eta * y; } void perceptron(vector> x, vector y)
{
    if (x.size() == 0)
    {
        return;
    }
    if (x.size() != y.size())
    {
        return;
    }

    vector w(x[0].size(), 0);
    double b = 0;
    double eta = 1;

    for (int i = 0; i < x.size(); ++i)
    {
        double flag = calSign(y[i], w, x[i], b);
        if (flag <= 0) { updatew(w, y[i], x[i], eta); b="updateB(b," } for (auto i: w) cout << i endl; void addpoint(vector>& x, double x1, double x2, vector& y, int yy)
{
    vector xx;
    xx.push_back(x1);
    xx.push_back(x2);
    x.push_back(xx);

    y.push_back(yy);
}

int main(int argc, char* argv[])
{
    //readFile("x.txt");
    vector> x;
    vector y;

    addPoint(x, 3, 3, y, 1);
    // (4,3)这个点是正确分类的点，不会更新w、b
    //addPoint(x, 4, 3, y, 1);
    addPoint(x, 1, 1, y, -1);
    addPoint(x, 1, 1, y, -1);
    addPoint(x, 1, 1, y, -1);
    addPoint(x, 3, 3, y, 1);
    addPoint(x, 1, 1, y, -1);
    addPoint(x, 1, 1, y, -1);
    // 结果已经开始收敛
    //addPoint(x, 1, 1, y, -1);

    perceptron(x, y);
    return 0;
}

对偶形式

/**
 *  感知机学习算法的对偶形式
 */
#include 
#include 
#include 
#include 
#include 

using namespace std;

// 计算格拉姆矩阵
vector> calGram(vector> & x)
{
    if (x.size() == 0 || x[0].size() == 0)
    {
        vector> g;
        return g;
    }
    int m = x.size();
    int n = x[0].size();
    vector> gram;
    for (int i = 0; i < m; ++i)
    {
        vector row;
        for (int j = 0; j < m; ++j)
        {
            double add = 0;
            for (int k = 0; k < n; ++k)
            {
                add += x[i][k] * x[j][k];
            }
            row.push_back(add);
        }
        gram.push_back(row);
    }
    return gram;
}

void printGram(vector> gram)
{
    cout << "gram size: " << gram.size() << endl;
    for (auto i: gram)
    {
        for (auto j: i)
        {
            cout << j << " ";
        }
        cout << endl;
    }
}

double perceptron(vector> x, vector y)
{
    vector> gram = calGram(x);
    printGram(gram);

    vector alpha(x.size(), 0);
    int eta = 1;
    double b = 0;
    // 计算误分条件
    default_random_engine e(time(0));
    uniform_int_distribution<> u(0, x.size());
    cout << "update:" << endl;
    int rd[] = {1, 3, 3, 3, 1, 3, 3};
    for (int k = 0; k < 7; ++k)
    {
        // 随机选取迭代的点(梯度下降)
        int i = u(e);
        // 为了和书上的结果一致，手动指定了迭代次序
        //int i = rd[k]-1;
        double sign = 0;
        for (int j = 0; j < x.size(); ++j)
        {
            sign += alpha[j] * y[j] * gram[j][i];
        }
        sign = y[i] * (sign + b);
        if (sign <= 0) { cout << i " ; alpha[i] +="eta;" b } endl; "alpha:" for (auto a : alpha) "; endl "b=" << b << endl;
    vector w(x[0].size(), 0);
    for (int i = 0; i < w.size(); ++i)
    {
        for (int j = 0; j < x.size(); ++j)
        {
            w[i] += alpha[j] * y[j] * x[j][i];
        }
    }

    cout << " w="(";" i: w) ")" return b; void addpoint(vector>& x, double x1, double x2, vector& y, int yy)
{
    vector xx;
    xx.push_back(x1);
    xx.push_back(x2);
    x.push_back(xx);

    y.push_back(yy);
}

int main(int argc, char* argv[])
{
    //readFile("x.txt");
    vector> x;
    vector y;

    addPoint(x, 3, 3, y, 1);
    addPoint(x, 4, 3, y, 1);
    addPoint(x, 1, 1, y, -1);

    perceptron(x, y);
    return 0;
}