机器学习算法--KNN近邻分类算法

KNN近邻分类算法

算法思想：

存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类对应的关系。输入没有标签的数据后，将新数据中的每个特征与样本集中数据对应的特征进行比较，提取出样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类作为新数据的分类。

给定一组样本数据以及分类信息，给定一组新样本，求出新样本的类别情况。

算法伪代码：

对未知类别属性的数据集中每个点依次执行以下操作：

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

1.距离计算

当给定一组样本数据时，当样本的特征属性是有序属性，可以直接进行数值计算来度量两个样本之间的距离。如果样本属性是有序的可以度量的，把样本抽象成空间的点，可以采用欧式距离来度量点与点之间的距离。

对于一个函数dist,若其表示距离度量，则应满足一下性质：

非负性：dist(xi, xj)>=0

同一性：dist(xi, xj)=0,当且仅当xi=xj

对称性：dist(xi,xj)=dist(xj,xi)

直递性：dist(xi,xj)<=dist(xi,xk)+dist(xk,xj)

对于样本Xi=(xi1,xi2...xin),Xj=(xj1,xj2...xjn),常用距离闵科夫斯基距离：

当p=2时，即欧式距离：

当p=1时，即曼哈顿距离：

对于无序属性，不能直接在属性值上进行距离计算，可采用VDM方式：

mua 属性u上取值为a大的样本数 muai 第i个样本簇在属性u上取值为a的样本数，k为总簇数

假定有nc个有序属性 n-nc个无序属性

当样本中属性权重不同是，可以采用加权距离：

在这里，为了便于计算，采用欧式距离进行计算

2.数据处理

以机器学习实战样例数据为准，

对于一个人的分类有不喜欢的人1，魅力一般的人2，极具魅力的人3。

主要与以下因素有关：每年飞行里程数玩游戏所耗时间比每周消费冰淇淋数

将数据文件中数据处理，分别读取到特征属性数值矩阵以及类别矩阵，前三列为特征属性数值最后一列为类别数值

def file2matrix(filename):
    #打开文件
	fr = open(filename)
	#获取数据的总行数
	numberOfLines = len(fr.readlines())
	#生成一个[numberOfLines][3]二维矩阵存放特征属性值
	returnMat = zeros((numberOfLines, 3))
	#分类属性存放
	classLabelVector = []
	fr = open(filename)
	index = 0
	#遍历每一行
	for line in fr.readlines():
		#去掉回车
		line = line.strip()
		#以tab进行切分
		listFromLine = line.split('\t')
		#前三个元素复制到特征数据矩阵
		returnMat[index,:] = listFromLine[0:3]
		#最后一个元素放入类别矩阵
		classLabelVector.append(int(listFromLine[-1]))
		index += 1
	return returnMat, classLabelVector

3.分析数据

使用Matplotlib创建原始数据散点图，观察类别信息

查看python已经安装module

安装matplotlib

python -m pip install matplotlib

以特征属性矩阵二三列显示如下：

重新加载kNN

>>> import kNN  
>>> from numpy import *   
>>> import matplotlib   
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> mat,lab = kNN.file2matrix('datingTestSet.txt')
>>> ax.scatter(mat[:,1], mat[:,2], 15.0*array(map(int,lab)),15.0*array(map(int,lab))) 
>>> plt.show()

第二三列以及第一二列的显示结果，可知数据具有明显的分类概念

4.归一化特征属性矩阵

归一化属性值，消除不同量纲对于结果的影响，常见的归一化方法有：

4.1 min-max标准化(Min-max normalization)

也叫离差标准化，是对原始数据的线性变换，使结果落到[0,1]区间，转换函数如下：

其中max为样本数据的最大值，min为样本数据的最小值。

def Normalization(x):
return [(float(i)-min(x))/float(max(x)-min(x)) for i in x]

如果想要将数据映射到[-1,1]，则将公式换成：

x∗=x−xmeanxmax−xmin x_mean表示数据的均值。

def Normalization2(x):
return [(float(i)-np.mean(x))/(max(x)-min(x)) for i in x]

这种方法有一个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义。

4.2 log函数转换

通过以10为底的log函数转换的方法同样可以实现归一下，具体方法如下：

看了下网上很多介绍都是x*=log10(x)，其实是有问题的，这个结果并非一定落到[0,1]区间上，应该还要除以log10(max)，max为样本数据最大值，并且所有的数据都要大于等于1。

4.3 atan函数转换

用反正切函数也可以实现数据的归一化。

使用这个方法需要注意的是如果想映射的区间为[0,1]，则数据都应该大于等于0，小于0的数据将被映射到[-1,0]区间上，而并非所有数据标准化的结果都映射到[0,1]区间上。

4.4 z-score 标准化(zero-mean normalization)

最常见的标准化方法就是Z标准化，也是SPSS中最为常用的标准化方法，spss默认的标准化方法就是z-score标准化。

也叫标准差标准化，这种方法给予原始数据的均值（mean）和标准差（standard deviation）进行数据的标准化。

经过处理的数据符合标准正态分布，即均值为0，标准差为1，其转化函数为：

x∗=x−μσ 其中μ为所有样本数据的均值，σ为所有样本数据的标准差。

z-score标准化方法适用于属性A的最大值和最小值未知的情况，或有超出取值范围的离群数据的情况。

标准化的公式很简单，步骤如下

　　1.求出各变量（指标）的算术平均值（数学期望）xi和标准差si ；
　　2.进行标准化处理：
　　zij=（xij－xi）/si
　　其中：zij为标准化后的变量值；xij为实际变量值。
　　3.将逆指标前的正负号对调。
　　标准化后的变量值围绕0上下波动，大于0说明高于平均水平，小于0说明低于平均水平。

def z_score(x, axis):
    x = np.array(x).astype(float)
    xr = np.rollaxis(x, axis=axis)
    xr -= np.mean(x, axis=axis)
    xr /= np.std(x, axis=axis)
    # print(x)
    return x

这里采用min-max归一化方法

def autoNorm(dataSet):
	#取出每一列的最小值 1x3
    minVals = dataSet.min(0)
	#取出每一列的最大值
    maxVals = dataSet.max(0)
	#每一列的最大和最小之差
    ranges = maxVals - minVals
	#生成归一化数组
    normDataSet = zeros(shape(dataSet))
	#行数
    m = dataSet.shape[0]
	#扩充minVals矩阵为mx3,以原先1x3复制m行
    normDataSet = dataSet - tile(minVals, (m,1))
	#进行矩阵对应位置相除归一化
    normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals

5.KNN算法实现

计算每个待分类样本与已分类样本的距离，排序，选取最小的k个样本，统计其中每种类别的出现次数排序，返回出现次数最多的类别作为待分类样本的类别

具体实现如下所示：

def classify0(inX, dataSet, labels, k):
	#样本数据矩阵的行数
    dataSetSize = dataSet.shape[0]
	#把待计算行向量复制成dataSetSize，与样本数据矩阵相减
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
	#计算矩阵的平方
    sqDiffMat = diffMat**2
	#矩阵每一行相加，组成一个dataSetSize维数组
    sqDistances = sqDiffMat.sum(axis=1)
	#开平方，计算距离
    distances = sqDistances**0.5
	#将distances中的元素从小到大排列，提取其对应的index(索引)，然后输出到sortedDistIndicies
    sortedDistIndicies = distances.argsort()   
	#定义一个字典  key 类别  value 该类别总次数
    classCount={}
    #计算最近的k个样本类别出现的次数	
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
		#不存在对应key返回0
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	#按照第二个元素降序排列
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

python3 dict.items方法，而非dict.iteritems

其中

1.shape[0]表示矩阵行数

2.tile函数：

tile(a,x): 结果是一维数组，x是控制a重复次数
tile(a,(x,y))：结果是一个二维矩阵，其中行数为x，列数是一维数组a的长度和y的乘积
tile(a,(x,y,z)): 结果是一个三维矩阵，其中矩阵的行数为x，矩阵的列数为y，而z表示矩阵每个单元格里a重复的次数

3.**表示次方

4.argsort() 从小到大排序返回对应索引

5.sorted函数：sorted 可以对所有可迭代的对象进行排序操作

sorted(iterable[, cmp[, key[, reverse]]])

参数说明：

iterable -- 可迭代对象。
cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
reverse -- 排序规则，reverse = True 降序， reverse = False 升序（默认）

返回排序之后的对象列表。

6.测试算法

给定数据集，一部分用于作为样本数据，一部分作为待测试数据，测试比例为0.1。代码如下：

def datingClassTest():
    #测试数据的比例
    hoRatio = 0.10      #hold out 10%
	#从文件中读取数据
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
	#归一化处理数据
    normMat, ranges, minVals = autoNorm(datingDataMat)
	#样本总数
    m = normMat.shape[0]
	#测试样本的数量
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
	    #前1--numTestVecs作为待分类样本   numTestVecs--m作为标准样本数据
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print ("the total error rate is: %f" % (errorCount/float(numTestVecs)))
    print (errorCount)

结果如下所示：

7.使用实例--手写识别系统

trainingDigits中存放样本数据 testDigits存放测试数据，其中数字8示例如下：

每个数字由32x32二维数组来表示

第一步进行数据处理，将32x32数组读取到一个1x1024的一维数组中，便于进行计算。

def img2vector(filename):
    #产生一个1024数组
    returnVect = zeros((1,1024))
    fr = open(filename)
	#读取每一行
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
		    #进行坐标变换  第i行第j个元素  放入到32*i+j一维数组中
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

进行训练和测试：

加载训练集，处理训练集数据，产生训练集数据矩阵以及类别矩阵

加载测试集，对于每个测试样本利用KNN算法计算类别结果，并与标准结果进行比较，统计分类失败的个数

def handwritingClassTest():
    hwLabels = []
	#加载训练集
    trainingFileList = listdir('trainingDigits')           #load the training set
	#训练样本总数
    m = len(trainingFileList)
	#存放训练样本总数矩阵mx1024
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
		#取出该文件数据的类别
        hwLabels.append(classNumStr)
		#将数据放入到特征值数据矩阵
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print ("\nthe total number of errors is: %d" % errorCount)
    print ("\nthe total error rate is: %f" % (errorCount/float(mTest)))

8.总结

KNN算法属于监督学习中的分类，KNN没有显示的训练过程，它是“懒惰学习”的代表，它在训练阶段只是把数据保存下来，训练时间开销为0，等收到测试样本后进行处理。

优点：精度高对异常值不敏感无数据假定输入。

缺点：计算复杂度，空间复杂度很高。无法给出任何数据的基础结构信息，无法知晓平均实例和典型实例的特征。