[一点一点入门机器学习] k近邻算法

本文主要是介绍[一点一点入门机器学习] k近邻算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

k-近邻算法

概要：k-近邻算法采用测量不同特征值之间的距离方法进行分类。
优点：精度高，对异常值不敏感，无数据输入假定。
缺点：计算复杂度高，空间复杂度高。

工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集合中每一个数据与所属分类的对应关系。

简单例子

k-近邻算法其实就是计算预测点与所有已知点（算法样本集）的距离（近似值），然后根据近似值就小的来判断与预测点的属性。

举个简单的例子，来说明这个算法。
假设有四个已知值，他们的特征值分别为[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]，他们标签分别为['A', 'A', 'B', 'B']，现在我们给定一个二维坐标，预测他所属的标签。

这其实是个简化的问题，可以向外扩展。例如，我们需要做一个垃圾邮件的过滤器，对于该邮件的信息我们可以根据不同的特征值进行标注，然后计算出该邮件属于垃圾邮件的可能性。真正的困难的地方就在于如何规划特征值，但这里不做讨论。

核心代码

from numpy import *
import operatordef create_data_set():group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])labels = ['A', 'A', 'B', 'B']return group, labels# inX 为需要预测的向量# group为算法样本集
def classify0(inX, group, labels, k):# 计算矩阵大小dataSetSize = group.shape[0]# 形参4维矩阵diffMat = tile(inX, (dataSetSize, 1)) - group# 矩阵内元素取平方sqDiffMat = diffMat ** 2# 矩阵中x, y相加sqDistance = sqDiffMat.sum(axis=1)distances = sqDistance ** 0.5# 返回数组值从小到大的索引sortedDistIndicies = distances.argsort()classCount = {}for i in range(k):voteLabel = labels[sortedDistIndicies[i]]classCount[voteLabel] = classCount.get(voteLabel, 0) + 1# key是一个函数，用来表明对哪一个值进行排序。sortedDistIndicies = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)return sortedDistIndicies[0][0]

以上的代码实际上对任意维度的向量都是可行的。使用下面的公式来计算预测点与已知的权值。

对于多维数据

上面提到了，对于多维向量，这个算法仍然是可行的。接下来我们通过以下数据来使用k-近邻算法。1-3 是不同的特性值 4 是标签。

0.8 400 0.5 1
12 134000 0.9 3
0 20000 1.1 2
67 32000 0.1 2

读取数据

首先我们需要把数据从文件中读出。

    file = open(filename)# 生成一个数组，记录每一行的数据。arrayOLines = file.readlines()numberOfLines = len(arrayOLines)# 生成一个n * 3维零矩阵，returnMat = zeros((numberOfLines, 3))classLabelVector = []index = 0for line in arrayOLines:# 去除换行符line = line.strip()# 用空格做分隔符listFromLine = line.split()# returnMat矩阵的[index][:]returnMat[index, :] = listFromLine[0: 3]classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat, classLabelVector

归一化数值

目标是将一个含有任意数值的列转换为只有[0,1]的列。

def autoNorm(dataSet):# 获得每列的最小值minValue = dataSet.min(0)# 获得每列的最大值maxValue = dataSet.max(0)# 获得每列的范围ranges = maxValue - minValuenormDataSet = zeros(shape(dataSet))m = dataSet.shape[0]# 每列数据减去最小值，再除以范围，获得一个[0,1]之间的特征值normDataSet = dataSet - tile(minValue, (m, 1))normDataSet = normDataSet/tile(ranges, (m, 1))return normDataSet, ranges, minValue

测试


def datingClassTest():datingDataMat, datingLabels = file2Matrix("DatingData.txt")normMat, ranges, minValues = autoNorm(datingDataMat)m = normMat.shape[0]errorCount = 0.0numTest = 3for i in range(numTest):classifierResult = classify0(normMat[i, :], normMat[0:m, :], datingLabels[0:m], 3)print('The test come back with {0}, and real result is {1}'.format(classifierResult, datingLabels[i]))if datingLabels[i] != classifierResult:errorCount += 1print("test ended!", errorCount)