部分资料下载地址: 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-近邻算法到底是个什么鬼。首先,如下示例图:
假设这图是标准坐标系第一象限的一些点,黑色和蓝色分别代表点的不同状态,下面我们需要预测箭头指向的绿色的点的状态,应该是黑色还是蓝色呢?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; } |
博主家的项目运行结果为这样:
后记:实现机器学习挺简单的,貌似我说的比较麻烦了。这儿只是原理的介绍,实际上机器学习算法并不需要手工造轮子,网上很多语言都已实现。比如Python的Scikit-Learn,C++的mlpack,还有R语言、MatLab等等都是封装好的库,只需要简单调用就行了,记得在使用前了解原理以避免在装逼失败时被人打:)