C++机器学习(1)k-近邻算法

部分资料下载地址: http://pan.baidu.com/s/1bpsgt5t 提取码fwxf
源码下载地址:https://github.com/fawdlstty/hm_ML

又是一个神秘的领域,对于C++程序猿来说,机器学习就像小白对C++一样。什么手写识别,什么自动驾驶,对于C++程序猿来说,几乎是不可能的实现。但如果了解原理之后,机器学习也就这么回事。这篇文章简要介绍机器学习以及用C++实现一个简单的机器学习算法——k-近邻算法。
首先说一下变种病毒。变种病毒的核心实现是动态随机修改指令,用于绕过几乎所有的特征码杀毒引擎,实现上并不是病毒自身会进化,而是仅仅修改了实现方式。从汇编角度上来说,比如以下代码:

1
mov eax, 10h

以上代码的含义是,将16这个立即数放在eax寄存器里面。变种核心模块将以上代码替换为如下形式

1
2
3
4
5
push ebx
mov ebx, 12h
sub ebx, 2h
mov eax, ebx
pop ebx

以上代码的实现效果与上面那一行代码完全相同。如果之前的代码是杀毒引擎标记的特征的话,那么变种病毒经过这次变种后,杀毒引擎就找不到特征了,于是实现了过杀毒引擎的效果。虽然变种病毒听起来很恐怖,但实际上病毒所实现的效果并不会改变,也就是说,以前没有的功能,病毒并不会在自我升级中产生。

上面的代码如果看不懂,那么我再帖一个例子,变种病毒会将自身以下代码:

1
int i = 16;

替换为以下形式

1
int i=18-2;

以上代码仅仅是示例,由此可见变种病毒自身并不会进化。机器学习其实也类似,机器学习的原理是,从一堆已有数据中,找出最匹配的数据,然后返回结果,这东西并不会自我升级(可能以后它会自我升级,但从目前情况上看来,暂时还不可能)。
然后,我来说说k-近邻算法到底是个什么鬼。首先,如下示例图:
201604281430
假设这图是标准坐标系第一象限的一些点,黑色和蓝色分别代表点的不同状态,下面我们需要预测箭头指向的绿色的点的状态,应该是黑色还是蓝色呢?k-近邻算法的含义就是,取离目标点最近的k个点,如果黑色点多,那就预测这个点的颜色为黑色,如果蓝色点多,那就预测这个点的颜色为蓝色。
上面这句话应该能看懂吧?下面我换一种说法,每一个点都有两个特征,分别为x轴与y轴坐标,每个点对应一个标签(状态),黑色或蓝色。现在需要求每个点距目标点的距离(方差),也就是x轴差的平方加y轴差的平方,然后再开根。然后,对所有方差进行排序,取方差最小的k个点(离得最近的k个点),计算标签(颜色),如果黑色点数量超过蓝色点数量,那么预测目标点为黑色点;如果蓝色点数量超过黑色点数量,那么预测目标为蓝色点。


以下进入正题。
下面我将介绍k-近邻算法实现,以及解决实际问题的示例。假如有四个水果,两个苹果两个香蕉,含糖量与热量分别为:
苹果1(含糖量:30毫克,热量:400焦)
苹果2(含糖量:35毫克,热量:380焦)
香蕉1(含糖量:52毫克,热量:280焦)
香蕉2(含糖量:55毫克,热量:250焦)
以上数据纯属搞笑,不要当真,仅仅是一个示例而已。
然后,下面有一个水果是以上两种水果中的一种,我们并不知道这是什么水果,只知道(含糖量:32毫克,热量:410焦),需要求出这是什么水果。从人的角度来看,可能一眼就能猜出这是苹果,但从计算机角度就麻烦了,因为事先并没有完全相同的数据,只能通过小的可怜的数据集中的数据来进行推算。这个示例中一个水果有两个特征(含糖量与热量),每个特征对应一个数值。
下面开始实现:(以下代码并未加入错误判断,本人也是新手,高手就不要说我写的差了)

1
2
3
4
5
6
7
8
9
10
11
12
13
 
//#ifdef UNICODE
//typedef std::string string_t;
//#else
//typedef std::wstring string_t;
//#endif
 
//下面用于计算两个双精度浮点类型数据是否相等
bool double_is_equal (double a, double b) {
    static const double double_error = 0.000001;
    if (a == 0 || b == 0) return fabs (a + b) < double_error;
    return fabs (fabs (a) < fabs (b) ? ((b - a) / a) : ((a - b) / b)) < double_error;
}

以上代码还是撸上,后面的代码可能会调用。
基本数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//特征类,一个类对象代表单个数据的特征集
class Feature_Data {
public:
    Feature_Data (std::initializer_list<double> dat) {
        data.assign (dat.begin (), dat.end ());
    }
 
    Feature_Data (std::vector<double> dat) {
        data.swap (dat);
    }
 
    //获取特征数量
    ptrdiff_t get_size () {
        return data.size ();
    }
 
    //重载[]运算符,后面将会以奇怪的方式访问数据
    double operator[](ptrdiff_t index) {
        return data [index];
    }
 
private:
    //特征集
    std::vector<double> data;
};

代码比较简单,以上代码基本可以实现特征的存储。下面的代码给特征加上标签,用于标明这特征集是什么东西(比如苹果与香蕉)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//数据类,一个类对象代表一个特征集与一个标签
class Feature_Object : public Feature_Data {
public:
    Feature_Object (std::string _label, std::initializer_list<double> dat) : Feature_Data (dat) {
        label = _label;
    }
 
    //如果想知道特征数据所对应的品牌,那么就调用这函数咯
    std::string get_label () {
        return label;
    }
 
    private:
        std::string label;
};

以上代码可以标明一个物品的特征了。比如苹果的两个特征。但特征数据集不止一个数据,比如上面的示例就有4个数据。这时候就需要一种结构来存储数据集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//数据组类,一个类对象代表一组数据类类对象
class Feature_Object_Collection {
public:
    //这个主要是为了方便构建测试数据而弄的,比较方便
    Feature_Object_Collection (std::initializer_list<Feature_Object> list) {
        data.assign (list.begin (), list.end ());
    }
 
    Feature_Object_Collection (const Feature_Object_Collection &o) {
        data.assign (o.data.begin (), o.data.end ());
    }
 
    //...
    //(○´・д・)ノ  可恶的博主,到底省略了什么代码??
 
    ptrdiff_t get_size () {
        return data.size ();
    }
 
    //又是以奇怪的方式访问数据
    Feature_Object& operator[](ptrdiff_t index) {
        return data [index];
    }
 
protected:
    std::vector<Feature_Object> data;
};

中间省略了部分代码,反正你我他都用不上。
接下来是最激动人心的时刻:算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//K-近邻算法实现
class KNN : public Feature_Object_Collection {
public:
    KNN (std::initializer_list<Feature_Object> list) : Feature_Object_Collection (list) {}
 
    KNN (Feature_Object_Collection& o) : Feature_Object_Collection (o) {}
 
    KNN (const KNN &o) : Feature_Object_Collection (o) {}
 
    std::string calc (Feature_Data dat, ptrdiff_t k) {
        //k-近邻算法含义是,从给定数据集中找出与目标数据最近的k个数据集
        //如果标签都一样,那么就返回标签。如果标签不同,那么计算后给出
        //标签出现次数最多的标签。由于只保留距离最近的k个数据,所以...
        pFeature_Object *o = new pFeature_Object [k];
        double *sqc = new double [k];
 
        ptrdiff_t i, j, used, count = data.size (), size = dat.get_size ();
        double squared = 0;
        遍历所有特征
        for (i = used = 0; i < count; ++i, squared = 0) {
            //求方差
            for (j = 0; j < size; ++j)
                squared += (pow (data [i] [j] - dat [j], 2));
            squared = ::pow (squared, 0.5);
 
            if (used < k) {
                //好险,数据还不够k个,可以安心插入
                ++used;
                j = used - 1;
            } else if (sqc [k - 1] <= squared) {
                //哦豁,方差比已有的k个数据中方差最大的还大,只能做个无辜的路人
                j = -1;
            } else {
                j = used - 1;
            }
            //在插入数据时为了不把大小顺序弄乱,所以遍历一下,找到最佳插入点
            for (; j > 0; o [j] = o [j - 1], sqc [j] = sqc [j - 1], --j) {
                if (sqc [j - 1] < squared) {
                    sqc [j] = squared;
                    o [j] = &data [i];
                    break;
                }
            }
            //我去,方差够小哇,可以排第零了
            if (j == 0) {
                o [0] = &data [i];
                sqc [0] = squared;
            }
        }
 
        //下面已经有了used个数据了,那么就全部塞入map里面吧,找到出现次数最多的标签
        std::map<std::string, ptrdiff_t> m;
        std::string s;
        for (i = 0; i < used; ++i) ++m [o [i]->get_label ()];
        for (i = 0; i < used; ++i) {
            if (i == 0 || j < m [o [i]->get_label ()]) {
                j = m [s = o [i]->get_label ()];
            }
        }
 
        delete sqc;
        delete o;
        return s;
    }
};

实现代码已经(还没有)撸完,下面就给出调用方式:

1
2
3
4
5
6
7
8
9
10
11
int main(int argc, char* argv[]) {
    KNN k ({
        { "Apple", { 30, 400 } },
        { "Apple", { 35, 380 } },
        { "Banana", { 52, 280 } },
        { "Banana", { 55, 250 } }
    });
    cout << "Calc value is: " << k.calc ({ 32, 410 }, 2);
 
    return 0;
}

博主家的项目运行结果为这样:
20160418154752
后记:实现机器学习挺简单的,貌似我说的比较麻烦了。这儿只是原理的介绍,实际上机器学习算法并不需要手工造轮子,网上很多语言都已实现。比如Python的Scikit-Learn,C++的mlpack,还有R语言、MatLab等等都是封装好的库,只需要简单调用就行了,记得在使用前了解原理以避免在装逼失败时被人打:)

Published by

fawdlstty

又一只萌萌哒程序猿~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注