KNN算法

一、KNN算法概述

1、kNN算法又称为k近邻分类(k-nearest neighbor classification)算法。
最简单平凡的分类器也许是那种死记硬背式的分类器，记住所有的训练数据，对于新的数据则直接和训练数据匹配，如果存在相同属性的训练数据，则直接用它的分类来作为新数据的分类。这种方式有一个明显的缺点，那就是很可能无法找到完全匹配的训练记录。
kNN算法则是从训练集中找到和新数据最接近的k条记录，然后根据他们的主要分类来决定新数据的类别。该算法涉及3个主要因素：训练集、距离或相似的衡量、k的大小。

二、KNN算法步骤
1）算距离：给定测试对象，计算它与训练集中的每个对象的距离
2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻
3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类

三、算法优缺点
1、优点
简单，易于理解，易于实现，无需估计参数，无需训练
适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）
特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好

2、缺点
懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢
可解释性较差，无法给出决策树那样的规则。

四、KNN算法实现代码
实现最基本的KNN形式非常简单。给定训练样本集和对应的标记列表，下面的代码可以用来完成这一工作。 这些训练样本和标记可以在一一个 数组里成行摆放或者千脆摆放列表里，训练样本可能是数字、字符串等任何你喜欢的形状。将定义的类对象添加到名为knn.py的文件里:

class KnnClassifier(object):
    
    def __init__(self,labels,samples):
        """ Initialize classifier with training data.使用训练数据初始化分类器  """
        
        self.labels = labels
        self.samples = samples
    
    def classify(self,point,k=3):
        """ Classify a point against k nearest 
            in the training data, return label. 
             在训练数据上采用 k 近邻分类，并返回标记
        """
        
        # compute distance to all training points 计算所有训练数据点的距离
        dist = array([L2dist(point,s) for s in self.samples])
        
        # sort them 对它们进行排序  
        ndx = dist.argsort()
        
        # use dictionary to store the k nearest   用字典存储 k 近邻
        votes = {}
        for i in range(k):
            label = self.labels[ndx[i]]
            votes.setdefault(label,0)
            votes[label] += 1
            
        return max(votes, key=lambda x: votes.get(x))

定义一个类并用训练数据初始化非常简单;每次想对某些东西进行分类时，用KNN方法，我们就没有必要存储并将训练数据作为参数来传递。用一个字典来存储邻近标记，我们便可以用文本字符串或数字来表示标记。在这个例子中，我们用欧式距离(L2)进行度量，当然，如果你有其他的度量方式，只需要将其作为函数添加到上面代码的最后。

我们首先建立一些简单的二维示例数据集来说明并可视化分类器的工作原理，下面的脚本将创建两个不同的二维点集，每个点集有两个类，用pickle模块来保存创建的数据：

# -*- coding: utf-8 -*-
from numpy.random import randn
import pickle
from pylab import *

# create sample data of 2D points
n = 200
# two normal distributions
class_1 = 0.6 * randn(n,2)
class_2 = 1