之前提到过三种简单基础的监督学习算法，但是选择还有更多种：
KNN（思路易于理解，熟悉其结合KD-tree来其优化算法的时间性能）ADAboostRandom Forests请尝试使用scikit-learn来得到各类算法的准确度，与运行时间！
KNN的思路很容易理解，简单地说就是，给定N个样本空间，一个询问点p，求距离询问点最近的K个点（最后根据这K个点的类标号中占比最大的标号，即为询问点的类标号）。
优化：使用KD-tree 这种数据结构来优化，主要过程是 建树 + 询问前k小。
相关资料： - 很好懂的文章：KD树详解 - 一份KD-Tree的C++实现：HDOJ 4347
用于理解的C++代码：
//------------------------------------------------------------- #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 55555, K = 5; const int inf = 0x3f3f3f3f; #define sqr(x) (x)*(x) int k,n,idx; //k为维数,n为点数 struct point { int x[K]; bool operator < (const point &u) const { return x[idx] < u.x[idx]; } }po[N]; typedef pair<double,point> tp; priority_queue<tp> nq; struct kdTree { point pt[N<<2]; int son[N<<2]; void build(int l, int r, int rt = 1, int dep = 0) { if(l > r) return; son[rt] = r - l; son[rt*2] = son[rt*2+1] = -1; idx = dep % k; int mid = (l + r) / 2; nth_element(po + l, po + mid, po + r + 1); pt[rt] = po[mid]; build(l, mid - 1, rt * 2, dep + 1); build(mid + 1, r, rt * 2 + 1, dep + 1); } void query(point p, int m, int rt = 1,int dep = 0) { if(son[rt] == -1) return; tp nd(0, pt[rt]); for(int i = 0;i < k;i ++) nd.first += sqr(nd.second.x[i] - p.x[i]); int dim = dep % k, x = rt * 2, y = rt * 2 + 1, fg = 0; if(p.x[dim] >= pt[rt].x[dim]) swap(x, y); if(~son[x]) query(p, m, x, dep + 1); if(nq.size() < m) nq.push(nd), fg = 1; else { if(nd.first < nq.top().first) nq.pop(), nq.push(nd); if(sqr(p.x[dim] - pt[rt].x[dim]) < nq.top().first) fg = 1; } if(~son[y]&&fg) query(p, m, y, dep + 1); } }kd; void print(point &p) { for(int j = 0;j < k;j ++) printf("%d%c",p.x[j], j == k-1 ? '\n' : ' '); } int main() { while(scanf("%d%d", &n, &k) != EOF) { for(int i = 0;i < n;i ++) for(int j = 0;j < k;j ++) scanf("%d", &po[i].x[j]); kd.build(0, n-1); int t, m; for(scanf("%d", &t);t --;) { point ask; for(int j = 0;j < k;j ++) scanf("%d", &ask.x[j]); scanf("%d", &m); kd.query(ask, m); printf("the closest %d points are:\n", m); point pt[20]; for(int j = 0;!nq.empty();j ++) pt[j] = nq.top().second, nq.pop(); for(int j = m - 1;j >= 0;j --) print(pt[j]); } } return 0; }ADAboost（Adaptive boost 自适应增强），是一个不断更新迭代的过程。其算法步骤为： （1）、初始化各个样本点的权重为1/N，N为样本总数。训练得到初步的分类器： G1(x) ，计算出这个分类器的误差率：
em=∑i=1i=NWi∗I(G1(xi)!=yi) （其中 wi指第 i个样本的权值），计算这个分类器的权重： am=12log1−emem 。 可以看出，对于第一次的分类，如果误差率较高，那么这个分类器所占权重 am将会比较小。 （2）、进行第 m+1(m>=1)次迭代过程： 计算每个样本的权值： Wi,m+1=Wi,mZme−am⋅yi⋅Gm(xi) 得到新的权值集合。接下来重新训练样本的得到分类器 Gm+1(x) ，同理按照上述的公式去计算这个费类其的误差率，以及这个分类器的权重。 （3）、组合各个分类器，得到最终的分类器： f(x)=∑i=1i=MaM⋅GM(x) G(x)=sign(f(x))具体详细的文章，参考：Adaboost详细过程及证明
随机森林（Random Forests），由多棵决策树来投票选择最终的分类结果，而每一颗决策树是怎样构成的呢？ （1）、如果训练集大小为N，对于每颗决策树来说，随机且有放回的从训练集中抽取n个样本，作为该树的训练集。 （2）、每个样本的特征维度为M，随机地从M个特征维度中选择m个特征子集，构建决策树时，从这m个特征子集进行划分。 （3）、每棵树都尽最大程度的生长，并且没有剪枝过程。
思考： 一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。
随机森林分类效果（错误率）与两个因素有关：
（1）、森林中任意两棵树的相关性：相关性越大，错误率越大； 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。 （2）、减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。
结合实例详细的文章：讲解非常清晰的RF介绍
