2.1 概述
1) k-近邻算法采用测量不同特征值之间 距离 的办法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定；泛化错误率不超过不超过贝叶斯最优分类的两倍。
缺点：计算复杂度高、空间复杂度高
适用范围： 数值型 和 标称型
2)k-近邻算法原理：
1. 已知 训练样本集 和 样本集中数据的标签。
2. 输入 没有标签的 数据集 并将 新数据集中的数据的特征 与 训练集 的 特征 进行比较
3 算法提取最接近数据集的样本集的标签。
3) python算法实现(py3.6)
# coding:utf-8 # 准备 # 使用python导入数据 # 导入科学计算包numpy 和 运算符模块
#createDataSet 创建数据集 和 标签
from numpy import * import operator def createDataSet(): group = array([[1.0,0.9], [1.1,0.8],[0.2,0.3],[0,0]]) labels = ('A','A','B','B') return group,labels
验证模板是否创建成功
#在cmd中输入以下代码验证上述模块是否插入成功
>>>import kNN >>>group,labels = kNN.createDataSet() >>>group array([[1. , 0.9], [1.1, 0.8], [0.2, 0.3], [0. , 0. ]]) >>>labels ('A', 'A', 'B', 'B')
程序清单2-1 k-近邻算法
# 程序清单2-1 # k-近邻算法 # 分类代码 # 四个参数的意义： # inX：用来分类的测试集 # dataSet : 用来训练的数据集属性 # labels: 用来分类的数据集标签 # k: k-近邻算法的k,表示选取k个有效数 def classify0 (inX, dataSet, labels, k): # shape[0], 返回data的行数 0- 按0维变化方向shape[i][] dataSetSize = dataSet.shape[0] # tile函数实现矩阵重复，在列方向重复1次，行方向重复dataSetSize次； # 对应值相减存放在 列表 diffMat中 diffMat = tile(inX, (dataSetSize,1)) - dataSet # 平方 sqDiffMat = diffMat ** 2 # sum求和，axis = 1为按1即维变化方向操作sum[][j]，axis = 0 为按0维方向操作sum[i][] sqDistances = sqDiffMat.sum(axis=1) # 开方 distances = sqDistances ** 0.5 # distances.argsort(),将distances中元素即距离，从小到大排序，并返回索引值，存放在sortedDistIndicies sortedDistIndicies = distances.argsort() # 创建一个空字典 ClassCount = {} for i in range(k): # 返回距离排名第i的标签 voteIlabel = labels[sortedDistIndicies[i]]
# 用字典记录 键（标签）出现的 次数 # dict.get(key,default= None），字典中 get() 返回字典中指定 键 的 值
# dict.get() 若字典中没有该标签则创建并将其值置为1，若已有标签则返回其值并将值加1 # 如果 key不在字典中，则返回默认值default的值 ClassCount[voteIlabel] = ClassCount.get(voteIlabel, 0) + 1 # 将 ClassCouNt 中的值进行排序 # sorted(iterable,cmp= None,key = None,reverse = false) # iterable 待排序的可迭代类型的容器 # cmp:用于比较函数；key = operator,itemgetter(1)根据字典的值进行排序 # key=operator.itemgetter(1)根据字典的键进行排序 # reverse = True 降序 or reverse = False 升序|（默认） sortedClassCount = sorted(ClassCount.items(), key=operator.itemgetter(1), reverse=True) # 返回要分类的类别的标签 return sortedClassCount[0][0]
程序清单 2-2 将文本程序转化为Numpy的解析程序
# 2.2.1 # 准备数据：从文本中解析数据 # 程序清单2-2 # 将文本记录转化为Numpy的解析程序 def file2matrix(filename): # 打开文件 fr = open(filename) # readlines()方法用于读取所有行(直到结束符 EOF)并返回 列表 ;如果碰到结束符 EOF 则返回 空字符串 arrayOLines = fr.readlines() # 返回文件行数 numberOFLines = len(arrayOLines) # 创建返回特定形状的以0填充的 numpy 矩阵(n 行 * 每行 m 列) returnMat = zeros((numberOFLines, 3)) # 创建空列表 存储标签 classLabelVector = [] index = 0 for line in arrayOLines: # 去掉字符串前后的空格 line = line.strip() # split() 通过指定 分隔符(" ") 对字符串进行切片，如果参数 num 有指定值，则仅分隔 num 个子字符串 listFromLine = line.split(" ") # 填充 returnMat 用切片好的 listFromLines returnMat[index, :] = listFromLine[0:3] # 将 listFromLines 中的标签输入字典 classLabelVetor 中 classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat, classLabelVector
2.2.3 归一化数值
当数据集和样本集中的 某一个属性的 数值差值过大时 会影响 到各个属性的权重值。所以采用归一化的方法来解决这个问题。
公式： newValue = (oldValue - min) / (max - min)
# 2.2.3 # 数据归一化 def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = zeros(shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - tile(minVals, (m, 1)) normDataSet = normDataSet / tile(ranges, (m,1)) return normDataSet, ranges, minVals
遇到的一些问题
Numpy 包的下载与安装：直接用的 Anaconda ，配置环境变量后可以直接使用
kNN 模板路径问题 ：1.可以直接放在 python.exe 所在的文件夹 如我的是 C:Anaconda3
2.如上使用 import sys 方法
datingTestSet.txt 路径问题 ： 1. 引用时使用绝对路径 2.命名为 datingTestSet 而不是 datingTestSet.txt