1、k-近邻算法

k-近邻算法简称kNN，是一种常用的监督学习方法，它的工作机制简单来说就是：在给定的测试样本中，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

• 在分类中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测的结果；
• 在回归中可使用“平均法”，即将这k个样本的实值输出标记值的平均值作为预测结果。

还可基于距离的远近进行加权平均和加权投票。

1.1、度量距离

设特征空间中X是n维实数向量Rⁿ, x_i, x_j∈X, x_i=(x_i¹,x_i²,...,x_iⁿ), x_j=(x_j¹,x_j²,...,x_jⁿ).

x_i,x_j的L_p距离为=(\sum_{l=1}^{n}|x_i{l}-x_j^{l}|{p})^{\frac{1}{p}},(p≥1)$$)

当p=2时，为欧式距离（Euclidean distance）

=(\sum_{l=1}^{n}|x_i{l}-x_j^{l}|{2})^{\frac{1}{2}}$$)

当p=1时，为曼哈顿距离（Manhattan distance）

=\sum_{l=1}^{n}|x_i{l}-x_j^{l}|$$)

当p=∞时，是各个坐标距离的最大值

=\max_{l}\sum_{l=1}^{n}|x_i{l}-x_j^{l}|$$)

1.2、k值的选取

k值的选取会对k近邻法的结果产生重大影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例相似的训练实例才会对预测结果产生作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰好是噪声，预测就会出错，亦即k值的减小就意味着整体的模型变复杂，容易发生过拟合。

如果选择较大的k值，就相当于用较大的邻域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例不相似的训练实例也会对预测产生作用，是预测发生错误。k的增大就意味着整体的模型变得简单。

2、算法实现

这次仍然使用学习决策树算法时候的数据集进行实验，

由于各种距离需要使用数值进行计算，上述“色泽”、“根蒂”、“敲声”、“纹理”、“脐部”和“触感”6个特征变量都是类别变量（factor），我们需要将其转化为哑变量（dummy variables）。

例如在“色泽”中，令数值0代表“乌黑”，数值1代表“青绿”，数值2代表“浅白”，以此进行转换。

其中数据集（data1.txt）中的格式如下图所示：

下述的代码即针对上述数据集进行哑变量转换的,

filename = 'data1.txt'
def factor2dummy_variable(filename):
    fr = open(filename,encoding = 'utf-8')#以utf-8读取文件
    dataColumns = fr.readline()#去除首行
    arrayLines = fr.readlines()#读取所有行
    lines = np.array([line.replace('\n','').split('\t') for line in arrayLines]).T#按行指定分隔符，并进行转置
    lines = lines[1:,:]#实际使用的数据部分
    setFactors = [set(line) for line in lines]#set操作，只保存一种分类的集合
    k = 0
    for i in setFactors:
        dummy_num = 0
        line = lines[k]
        for j in i:
            line[line == j] = dummy_num#哑变量转换
            dummy_num += 1
        k += 1
    lines = lines.T#转置
    return lines

将转换好的数据集保存到文件（data2.txt）,

lines = factor2dummy_variable(filename)
dataSet = lines
filename = 'data2.txt'
def data2txt(dataSet,filename):
    fw = open(filename,'w',encoding='utf-8')#以utf-8编码写入
    for line in dataSet:
        for element in line:
            fw.write(element)
            fw.write('\t')#tab键分割符号
        fw.write('\n')#换行
    fw.close()

转换好的数据集格式如下图所示：

处理完毕上述变量后，需要将转换好的数据文件转化成numpy可以使用的数据集形式，

filename = 'data2.txt'
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()#读取所有行
    numberOfLines = len(arrayOLines)#计算记录数量
    numberOfcloumns = len(arrayOLines[0].replace('\t\n','').split('\t')) - 1#计算变量数量
    returnMat = np.zeros((numberOfLines, numberOfcloumns))
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()#去除空格
        listFromLine = line.split('\t')#按tab键分割
        returnMat[index, :] = listFromLine[:-1]#得到分类变量数组
        classLabelVector.append(int(listFromLine[-1]))#类别变量数组
        index += 1
    return returnMat, classLabelVector

​ 注：有时候由于各类变量之间数值差别太大，同时量纲也各不相同，这时候就需要进行归一 化操作，将各变量的范围设置在0~1之间，以消除量纲影响，加快运算速度。

​ 其中归一化的式子如下：
​ }}{\min{(x)}-\max{(x)}}​$$)

​ 下述代码即进行归一化操作：

def autoNorm(dataSet):
    minValue = dataSet.min(0)#得到每列的最小值
    maxValue = dataSet.max(0)#每列最大值
    ranges = maxValue - minValue#分母
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]#行数
    normDataSet = dataSet - np.tile(minValue, (m,1))#分子
    normDataSet = normDataSet/np.tile(ranges, (m,1))
    return normDataSet, ranges, minValue

经过上述处理，这里通过计算欧式距离进行kNN分类，具体代码如下：

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]#得到行数
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#计算输入向量inX与训练样本的差
    sqDiffMat = diffMat**2#计算差值的平方
    sqDistances = sqDiffMat.sum(axis = 1)#距离平方和
    distances = sqDistances**0.5#开方得到距离
    sortedDistIndicies = distances.argsort()#距离进行排序,得到排序的下标
    classCount = {}
    for i in range(k):#确定前k个距离中最小元素所属分类
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#对出现的label进行计数
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),
                              reverse = True)#按照计数值进行降序排序
                              #operator.itemgetter(1)确定一个函数取出classCount中的第一个域的值，即将value取出
    return sortedClassCount[0][0]#返回最大的计数值的分类

由此，即进行了kNN的分类操作，下面通过以下代码对分类效果进行测试（测试数据集仍是训练数据集合）

dataLines, datalabels = file2matrix('data2.txt')
i=0
errorCount = 0.0
for line in dataLines:
    print('记录%s的原始分类是:%d，划分分类是:%d' %(str(line), datalabels[i], 
                                     classify0(line, dataLines ,datalabels, 1))) 
    if (datalabels[i] != classify0(line, dataLines ,datalabels, 1)):
        errorCount += 1.0
    i += 1
print('错误率为: %f' %(errorCount/float(len(dataLines))))

可以看出错误率为0.000000，正确率达到了100%。可以看出准确度不错，当然此准确度也与数据量的大小有关，后续可以将数据集扩大，或者使用不同的数据集进行训练测试，来验证分类效果。

下面代码是通过Scikit - Learn库进行数据集的训练和测试过程。

import numpy as np
from sklearn import neighbors

data = []
labels = []
with open('data2.txt') as ifile:
    for line in ifile:
        tokens = line.replace('\t\n','').split('\t')
        data.append([float(tk) for tk in tokens[:-1]])
        labels.append(tokens[-1])
x = np.array(data)
y = np.array(labels)

clf = neighbors.KNeighborsClassifier(algorithm = 'kd_tree', n_neighbors = 1)
clf.fit(x,y)

answer = clf.predict(x)
print('准确率为:%f' % float(np.mean(answer == y)))#正确率

其准确率可以达到100%。

值得注意的是，上述neighbors.KNeighborsClassifier()中，存在很多可以自行调节的参数，这里可以查看官方文档（http://scikit-learn.org/stable/documentation.html） 并进行相关操作。