机器学习-KNN

参考书籍《机器学习实战》,《机器学习》。
KNN算法

kNN也叫k-近邻算法是一种分类与回归算法，属于监督学习算法。工作原理是：存在一个训练样本集，其中的每一个数据都有一个对应的标签，这个标签就是它所属分类的对应关系。我们输入一个新数据后，将新数据的特征与训练集中的特征进行比较，然后算法根据其特征，提取样本中最相似(最近邻)的分类标签。就拿爱情片和动作片来说，其中接吻镜头和打斗场面就相当于其特征，爱情片和动作片就相当于分类标签。我们只选择样本数据中的前k个最相似的数据，通常k不大于20，然后根据这k个相似数据中出现的最多的分类，作为新数据的分类。

k近邻算法的一般流程
(1)收集数据：可以使用任何方法
(2)准备数据：计算距离，最好是结构化的数据格式
(3)分析数据：可以使用任何方法
(4)训练算法：此步骤不适用kNN
(5)测试算法：计算错误率
(6)使用算法：首先输入样本数据和结构化的输出结果，然后运行kNN 判定输入的数据属于哪个分类，最后应用对计算出的分类执行后续的处理。

用python实现

python

from numpy import *
import operator #导入numpy 和 运算符模块
def createDataSet():
    group = array([[1.0,1.1],[1.0,1.1],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group, labels

import kNN
group,labels = kNN.createDataSet()
group
out[]:array([[1. , 1.1],
       [1. , 1.1],
       [0. , 0. ],
       [0. , 0.1]])
labels
out[]
['A', 'A', 'B', 'B']

以上是一些准备工作，我们解析并加载了数据。接下来进行进一步实现

Code

伪代码
1，计算已知类别数据集中的点与当前点的距离
2，按照距离递增次序排序
3，选取与当前距离最小的k个点
4，确定前k个点所在类别的出现频率
5，返回前k个点出现频率最高的类别作为当前点的预测分类

inX为待分类数据，dataSet为训练数据集，labels对应dataSet每一行数据的标签(类型),k表示用于选择最近邻居的数目
shape[0]表示最外围的数组的维数,如果是二维，shape[0]表示行数，shape[1]表示列数
tile(inX, (dataSetSize,1)) 创建一个numpy的array，dataSetSize行，每行数据是inX
-dataSet 矩阵减法 mn矩阵A - mn矩阵B详细函数说明戳这

距离公式：$d=\sqrt{(xA_0-xB_0)^{2}+(xA_1-xB_1)^{2}}$

python

def classify0(inX, dataSet, labels, k): 
    dataSetsize = dataSet.shape[0]   
    diffMat = tile(inX, (dataSetSize,1)) - dataSet    
    sqDiffMat = diffMat**2
    sqDiffMat = diffMat.sum(axis = 1) #横向求和，得到一个新的矩阵
    distances = sqDistances**0.5 #至此完成距离计算

    sortdDistIndicies = distance.argsort() 
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortdDistIndicies[i]]
        clssCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #选择距离最小的k个点
    sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)  #完成排序
    return sortedClassCount[0][0]

为了预测数据所在分类
kNN.classify0([0,0],group,labels,3)
输出B为正确结果
之后我又将《机器学习实战》中的示例1：使用kNN改进约会网站的配对效果码了一遍放在我的github了
当然了其中也读了一些人的博客。
更多详细说明看dalao博客