[Tech] 机器学习之一. k-近邻算法

机器学习是人工智能发展的助燃剂，人工智能如同一辆迟迟不来的列车，然而一旦当其前来，便会以令人瞠目的速度驰骋。而在人工智能的洪流之中，人类却如苇草，渺小如你我，有且只有顺应时代的潮流。

一、特点

刚开始学k-近邻算法的时候，立马就想起高中学的求二象限及三象限中两点的距离。只不过k-近邻算法将象限值扩大了一些，但总的来说原理还是类似的。
k-近邻算法易于掌握（高中数学基础）就可以轻松理解其原理，但计算复杂度比较高，相对而言它的精度也比较高哦。

二、栗子

举一个栗子让大家更好的理解k-近邻算法。我喜欢喝Coco的金桔柠檬，主要就是因为它的甜度和酸度控制得非常合我口味，当我考量其它家的金桔柠檬时，就需要将其的甜度和酸度和Coco家的做个对比，对比结果越小，就越合我口味。
下面，我们来画一张图，横轴表示酸度，纵轴表示甜度，将Coco家的金桔柠檬的甜度和酸度都量化为5。

随便说说的评测

那么该如何评判其它家金桔柠檬在我心里的地位呢？学过函数的你一定会想到根据其他家金桔柠檬酸甜度的量化结果求与Coco家酸甜度的距离吧，以x代表酸度，y代表甜度，那么这个距离就是√[(x-5)^2 +(y-5)^2]
。距离越短就说明这个口味越合我意。
在实际的数据分析中，可能不止甜度和酸度两个特征值，这种情况下就需要算出多维度下亮点的距离了，如有5个特征值，则（1，0，2，1，0）与（3，2，1，5，6）的距离计算公式就是：
√[(3-1)^2 +(2-0)^2 +(1-2)^2 +(5-1)^2+ (6-0)^2]

三、更多的样本

在以上栗子中，我按照酸度和甜度与Coco家金桔柠檬的匹配程度去衡量我对其它品牌金桔柠檬的喜爱程度。这样的结果是否符合呢？

相信读者已经提出异议了吧。

首先，仅凭我对一家金桔柠檬的喜爱程度（一个样本）就去分析我对其它家金桔柠檬的喜爱未免太过武断，因为我对金桔柠檬的喜好程度并不仅仅取决于甜度与酸度，还会有其它干扰因素比如茶的颜色、包装之类，有可能我喜欢Coco家的金桔柠檬和它的甜度酸度没有太大关系，仅仅是因为它家的包装呢？

另一方面，我对甜度酸度均为5的金桔柠檬非常喜爱，也不能得出我对甜度为3酸度为4的金桔柠檬的喜爱程度。

所以，想让结果更准确的话，我们还需要做两个小小的改善：第一，多喝几家的金桔柠檬，并记录这些金桔柠檬的甜度酸度以及我对这些金桔柠檬的喜爱程度，样本扩大之后，就能够减少对某家非甜度和酸度两个因素影响的喜爱程度产生的结果偏差；第二，将喜爱程度量化或分类，量化就是指对金桔柠檬茶打分，分类就是指对金桔柠檬茶的喜好程度进行一个分类，比如“非常喜欢”，“一般喜欢”，“普通喜欢”，“不喜欢”。

于是乎，我又尝试了其它家的金桔柠檬茶，并记录下它们的甜度、酸度并且对它们进行了打分。

酸度	甜度	打分
5	5	5
7	3	4
5	6	5
3	6	3
2	3	3
6	5	5
7	8	3

以上的数据我们将其称为训练样本，接着我们就可以尝试测试一下我们的k-近邻算法啦，大致的思路是这样的，得到某个测试样本的酸度与甜度，并计算出其与所有品尝过的样本的距离，取出距离最小的前k个样本与其对应的标签，得到出现次数最多的标签，即为结果。

什么意思呢？比如说我得到一款新的金桔柠檬，然后测量出它的甜度与酸度，我用上述方法计算出其与所有品尝过的样本的酸甜度距离，然后得出酸甜度距离最小的前三家，也就是酸甜口味最相似的前三家，然后统计出那三家中喜好分数出现的次数，得出出现次数最多的那个分数，就是预测的我对这款新品的喜好程度。

四、上代码

第一步，我们将训练样本解析成特征值数组以及标签数组。

将训练样本的txt文件转换为 特征值数组returnMat 以及相应的同长度的标签数组 classLabelVector

def file_to_matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())  # get the number of lines in the file
    returnMat = zeros((numberOfLines, 2))  # prepare matrix to return
    classLabelVector = []  # prepare labels return
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:2]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
        

我们得到了两个数组：

returnMat = [[5,5], [7,3], [5,6], [3,6], [2,3], [6,5], [7,8]]  
classLabelVector = [5, 4, 5, 3, 3, 5, 3]

第二步，当得到了训练样本以及其对应标签后，我们就可以计算出测试数据与每个样本的距离，随后我们可以选取前k个距离最小的样本标签，取出现最多次数的标签作为结果。

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

其中，inX是输入的测试特征值数组，dataSet是训练特征值数组，labels是训练标签数组，k是用户定义的距离最小的样本标签数量。

我将新产品的甜度酸度[5,3]作为inX参数传入，dataSet和labels就是第一步得到的returnMat和classLabelVector，我取k为3，执行。

结果为5，非常喜欢，Done!

五、更多优化

使用上述方法，得到了结果，但是我们有没有可以优化的地方呢？
我的想法是，可以将打分结果从离散值转换为连续值，然后按照一定的权重去求得距离。
第二点就是，在这个栗子中我们的甜度和酸度的数值范围是相似的，如果我们以mg/L和ph值来定义甜度和酸度的时候，就需要做一个归一化处理。