十大经典算法之KNN

数据挖掘十大经典算法：KNN、C4.5、Naive Bayes、CART、SVM、Kmeans、PageRank、AdaBoost、EM、Apriori

---

KNN（K-Nearest Neighbor）

最近邻规则，一个有监督的分类算法，也是最简单的算法之一。 核心思想：若一个未知样本在特征空间中的k个最相近的样本（训练集）中大多数属于某一个类别，则该样本也属于这个类别

先上图解释：（需懂监督学习基本概念） 输入：已知类别{w1,w2,w3}的一系列数据集、一个未知类别的点 输出： 点X的所属类别（上述类别的一种） 过程： 1. 对X计算其与上面所有点的距离（欧式距离） 2. 排序，取排名前K的点 3. 对k个点，一般选择投票法：k个点所属类别次数最多的类别。此类别即为X的类别（如下图）

当k=3时，图上与绿色最近的3个点为：两个红色和一个蓝色。根据投票法：将红色所属类别赋予给绿色 由上知：虽然K最终的类别只与它最近的k个样本决定，但是它一样要与整个数据集进行计算。

距离计算

KNN算法中，常用的距离有三种，分别为曼哈顿距离、欧式距离和闵可夫斯基距离。 设特征空间是n维实数向量空间：Xi为第i维数值 * 闵可夫斯基距离 * 曼哈顿距离（Manhattan distance）:Lp中P=1 * 欧式距离（Euclidean distance）: p=2 * 切比雪夫距离（Chebyshev distance） : p= ∞

将做一篇所有距离计算博文

评估指标

分类指标：混淆矩阵、ROC与AUC、召回率与准确率及F1、kappa系数 将做一篇所有分类评估指标介绍博文

应用场景

分类 用户产品推荐： 基于用户最近邻，查看待推荐用户的最相似k个用户买了什么，进行推荐 一些分类场景：文本分类、搜索引擎（网页分类）回归 通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性

优缺点

优点： 1. 逻辑简单、有效 2. 计算时间和空间线性于训练集的规模 3. 对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 4. 特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好（待验证） 5. 适合对稀有事件（统计学概念）进行分类； 缺点： 1. 对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不是很理想 2. 样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数

改进

knn本身提出较早，因此也有一些优化思想。 * 效率 事先对样本属性进行约简，删除对分类结果影响较小的属性；但样本容量较小的类域采用这种算法比较容易产生误分。 * 效果 采用权值的方法（样本距离成正比）来改进：WAKNN (weighted adjusted k nearest neighbor)，以促进分类效果。（没用过）

改进算法：KD树 （后期扩展）

实践

KNN分类算法Iris实例:http://blog.csdn.net/michael_728/article/details/50976345

参考博文： [1] http://blog.csdn.net/app_12062011/article/details/51986805