数据挖掘中的KNN

  K最近邻算法是分类问题中经常使用的一种非参数方法。算法的思路清晰简洁：对于待分类的样本，找出与其最近的K个样本（即训练样本中的K个）。然后对这K个样本进行投票，待分样本与多数样本的类别一致。

 在该算法中有两个最主要的问题：1、最近怎么评价？2、到底K等于多少？

 对于第一个问题，我们分三种情况讨论：

 A.标称属性：如果样本的属性值相同，则两个样本的距离为0，否则为1。举例:有两个样本，其中有个属性是性别，如果两个样本的性别都是男，则距离为0，若一个为男一个为女，则距离为1。

 B.序数属性：如考虑学生的成绩评定有如下的等级{poor,fair,ok,good,perfect}。我们可以这样处理，将每个等级映射到从0开始的相继整数{poor=0,fair=1,ok=2,good=3,perfect=4}。如何两个学生的成绩分别是good和fair,我们可以定义距离distance=3-1=2。

 C.连续属性：可以用欧氏距离来衡量√∑(〔x-y〕(x-y))。如两个点（1,2）和（3,4）之间的距离distance = √((1-3)*(1-3) + (2-4)*(2-4)) = √8 = 2√2 .

 假如一个样本中包含以上三种属性，我们需要对各属性做归一化之后再求距离。或者是选择其他算法如决策树、朴素贝叶斯等。

 对于第二个问题，我觉得比较好的办法就是试探。设立一个确认样本集，然后试探看看选定哪个K值的效果比较好。当然对于大规模数据这种方法可能不太行，这时工程师的经验和判断就显得尤为重要了。很多资料建议K值在3-10之间，经验显示这样的K值能较好的控制噪声的干扰。

 K最近邻算法的特点：a.不需要建立模型（也称消极学习方法），但是计算开销很大，每次判断一个样本都要计算该样本到所有训练样本的距离。

 b.可以生成任意形状的边界，而像决策树算法只能生成线性的边界。

 c.适当的距离度量准则非常重要。