部分资料下载地址： 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等等都是封装好的库，只需要简单调用就行了，记得在使用前了解原理以避免在装逼失败时被人打:)
