统计学习方法：K近邻
K-NN 方法
K近邻（k-nearest neighbors）算法是一个简单、直观的算法。它没有显式的学习过程，但是物理意义与思路都非常容易理解。
K-NN思路
K-NN的思路用一句老话来说就是：近朱者赤，近墨者黑。它认为物以类聚、人以群分。具有类似性质的事物在空间上聚在一起的（这里的空间上不是简单的欧氏空间）。 从数据的角度来看，对于某一样本，它的标签应该与它附近的其它样本的标签相同。
实际上，K-NN的思路本质上就是对特征空间进行划分。这个划分就是数据集的模型。 从它的思路可以看到，它不像感知机，有一个不断迭代更新分类超平面的过程，它的划分从数据集产生的开始并确定规则后就已经是唯一确定的了，因此它没有显式的学习过程。个人见解，对于某一样本，它在观察其周围值的时候就是一个学习过程。
模型
K-NN的模型用数学不太好表达。。。 上面说到划分即模型，听着可能有点抽象，这里的划分其实是一个略为抽象的概念。 个人认为从代码层面能比较好的理解模型。那就到下面讲到KD树的时候再说明。
策略
K-NN的K的意义就是：K个距离最近的邻居。 那么K-NN的模型决策策略也非常明显：只要找到距离最近的K个样本，根据它们的分类情况，决定该样本的分类。 一般情况下，直接根据K个样本中类别出现次数最多的类别作为该样本的类别。从这里可以预见到，这里K的取值最好是奇数，且最好不等于类别个数的倍数。否则会出现不太好决定的情况，当然也可以选择出现次数最多且平均距离最近的类别，但是这样就多一个计算步骤了。 既然要计算距离，那么问题来了，距离该如何计算呢？距离的计算方式也是老生常谈了…有很多，这里就不列举了。原则就是：根据问题情况选择距离空间。为了简单，这里就先用最常见的欧氏距离了。
K-NN的决策方案通常使用上文所述的方法，一般叫它多数表决规则。它有如下解释： 设其分类函数为：
f:Rn→{c1,c2,…,ck}
则其被误分类的概率为：
P(Y≠f(X))=1−P(Y=f(X))
易知，当选择多数类为该样本的类别时，其值能够最小。这一点它等价于经验风险最小化。（从数学上证明少数服从多数在概率分布相同的时候是一种稳健的方法）。
算法
根据K-NN的思路，我们可以看到，只有能够快速找到某个样本点的最近邻，这个方法才有实用价值。为了达到这个目的，需要构造一个数据结构，来实现对最近邻的快速查找。
kd树
注意，kd树的k与K-NN的K意义不同。k表示的是k维，K表示的是K个。
kd树本质上是一颗二叉树，它表示对一个k维空间的划分。通过上文的描述，个人认为，这里的kd树就是模型(如果用kd树来存储样本集的话)。
平衡kd树构造算法伪代码：
# T为训练数据集 # xij为T中第i个样本的第j维 # node为一个树节点 # mid( x, i)为取x的第i 维中位数 # l为当前选中的维度 def createTree( T, node, l, k) if T.count() == 0: return None num, dim = T.shape() t_T = T.transpose() mid_value = mid(t_T[l]) node.mid_value = mid_value next_l = ( ( l % k ) + 2 ) % k leftchild, rightchild = NewTree(), NewTree() node.leftchild = createTree( T - t_T[:](v<mid_value), leftchild, next_l, k) node.rightchild = createTree(T - t_T[:](v>=mid_value,) rightchild, next_l, k ) node.leftchild.parent = node node.rightchild.parent = node return node |
|---|
构造好了树，就进入K-NN的最后一个环节了——搜索。 kd树搜索算法伪代码：
defclassify( x, kdTree, K ): depth = 0 node = kdTree.root # 找到样本点本身所在的子空间 whileTrue: if node.isLeaf == False: dim = ( depth % kdTree.k ) + 1 if x[dim] < node.mid_value : node = node.leftchild depth += 1 else: node = node.rightchild depth += 1 else: break # 寻找到样本点的K个最近点 vector = newVector(K) # 初始化一个只能保存K个元素的容器，加入新元素的时候自动扔掉距离值最大的样本点...(这地方略偷懒，但其实实现也很简单，实际上它是个什么数据结构大家都知道的) # - - 额...假定每个节点都有个方法提供没被搜索过的节点，先判断左子树再判断右子树，若左子树没被搜索过则只返回左子树，否则若右子树没被搜索过则返回右子树，否则返回parent.parent并标记parent为已被搜索过的节点，根节点的parent为None # 再给节点添个方法...懒得写函数了...node.leaf(), 返回node下最深的叶节点，若有两个则返回左叶节点 another_node = node.parent.not_searched_node() while another_node != None: leaf_node = another_node.leaf() vector.add(leaf_node) another_node = leaf.parent.not_searched_node() # 额...这样应该完成了吧，有问题看官们提醒俺一下俺马上改 return vector.most_class |
|---|
欢迎转发，关注，评论。
腾讯云开发者
