1、k近邻算法的理解
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
可以简单的理解为是通过测量与不同特征值之间的距离来进行分类。书中采用欧式距离实现k近邻算法。
2、书中例子的Python实现与注释
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 1 09:56:34 2016
@file kNN.py
@brief k-近邻算法的实现
@version V1.0
@author:
-# 2016-09-01 创建此文件
"""
from numpy import * # 导入科学计算包 NumPy
import operator # 导入运算符模块
import os
from os import listdir
"""
@brief k-近邻算法的实现 实现中采用欧氏距离公式
@param [in] inX 用于分类的输入向量，需要计算此向量属于哪一类
@param [in] dataSet 输入的训练样本集
@param [in] labels 训练样本集的标签向量
@param [in] 用于选择最近邻居的数目
@return 返回输入向量所属类别
"""
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] #读取矩阵第一维的长度 即计算矩阵的行数 ；shape[1] 表示计算矩阵的列数
#进行欧氏距离计算
diffMat = tile(inX, (dataSetSize,1)) - dataSet #将输入向量inX重复 (dataSetSize,1)次是的与数据集一致，构成一个新的数组
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis = 1) #sum(axis = 1)就是将一个矩阵的每一行向量相加
distances = sqDistances ** 0.5
soredDistIndicies = distances.argsort() #将距离按升序排列 返回原始索引值
classCount = {}
#选出距离最近的k个值
for i in range(k):
voteIlabel = labels[soredDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#按照计数进行逆序排序（从大到小的顺序）
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
"""
@brief 将文本记录转换为NumPy的解析函数 解决输入格式的问题
@param [in] filename 表示读入文件名
@return 返回样本矩阵和类标签向量
"""
def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines() #读取文本数据
numberOfLines = len(arrayOLines) #获得文本行数
returnMat = zeros((numberOfLines,3)) #初始化返回的样本矩阵 numberOfLines行 3列
classLabelVector = [] #初始化返回的标签
index = 0
for line in arrayOLines:
line = line.strip() #删除首尾空格
listFromLine = line.split('\t') #将字符串进行分割
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
"""
@brief 将特征值进行归一化处理 函数实现自动将数字特征值转化为0到1的区间
@param [in] dataSet 输入样本数据 特征值集
@return [out] normDataSet 归一化后的数据特征集
@return [out] ranges 变化范围
@return [out] minVals 最小变量值
"""
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals #变化范围
normDataSet = zeros(shape(dataSet)) #初始化一个矩阵跟原数据集一样的大小的值为0的矩阵
m = dataSet.shape[0]#获得矩阵的行数
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals
"""
@brief 测试算法
"""
def datingClassTest():
hoRatio = 0.50 #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):
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)3、k近邻算法优缺点总结
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
k-近邻算法是分类数据最简单最有效的算法，通过例子中可以看出，k近邻算法必须保存全部的数据集、如果训练数据集的很大，必须使用大量的存储空间。由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。
通过本节代码的学习，加入了大量的代码注释，让刚刚接触Python的编程人员来说是很重要的。通过查阅Python中提供函数的使用，加强了对Python使用技巧。所以我把自己对代码的理解写出来，希望大家一起学习，有不正确的地方还望大家给于指点。