k-近邻算法（kNN）：采用测量不同特征值之间的距离方法进行分类
-
优点：
- 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于数值型数据和离散型数据；
- 训练时间复杂度为O(n)；无数据输入假定；
- 对异常值不敏感。
-
缺点：
- 计算复杂性高；空间复杂性高；
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
- 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
- 最大的缺点是无法给出数据的内在含义。
使用数据范围：数值型和标称型
-
工作原理
- 使用无标签数据的每个特征与样本集中数据对应的特征比较，
- 算法提取样本集中特征最相似数据（最近邻）的分类标签，
- 只选择样本数据集中前k个最相似的数据，
- 选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
-
算法详解：
- k近邻法
输入：训练数据集
其中，
为实例的特征向量，
为实例的类别，
；实例特征向量
输出：实例
所属的类
。
（1）根据给定的距离度量，在训练集
中找出与
个点，涵盖这
；
（2）在
式中，
为指示函数，即当
时
- 线性扫描：最简单的实现方法式
- kd树：一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。二叉树
相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。通常选定坐标轴上的中位数，得到的kd树是平衡的输入：
其中
,
；
输出
树的算法。
（1）开始：构造根结点，根结点对应于包含
选择为坐标轴，以
由根结点生成深度为1的左、右子结点：左子结点对应坐标
将落在切分超平面上的实例点保存在根结点。（2）重复：对深度为
的结点，选择
为切分的坐标轴，
，以该结点的区域中所有实例的
由该结点生成深度为的左、右子结点：左子结点对应坐标
将落在切分超平面上的实例点保存在该结点。（3）直到两个子区域没有实例存在时停止。从而形成
- 用kd树的最近邻搜索：平均计算复杂度是
输入：已构造的
输出：
（1）在
（2）以此叶结点为“当前最近点”。
-
（3）递归地向上回退，在每个结点进行以下操作：
（a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
（b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。
（4）当回退到根结点时，搜索结束。最后的“当前最近点”即为
- k近邻法
-
参数选择
- k值
- 较小：近似误差（对现有训练集的训练误差）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。估计误差（对测试集的测试误差）会增大
- 较大：估计误差减少，近似误差会增大，模型趋于简单
- k=N：完全却决于训练集中类的多少，
- 一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
- k值
-
一般流程
- 收集数据：可以使用任何方法。
- 准备数据：距离计算所需要的数值，最好是结构化的数据格式。
- 分析数据：可以使用任何方法。
- 训练算法：此步骤不适用于k-近邻算法。
- 测试算法：计算错误率。
- 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。
手写重要代码
#导入库
import numpy as np
import operator
#创建数据集合
def createDataSet():
group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
#欧式距离的k-近邻算法
def classify0(inX, dataSet, labels, k):
"""
欧式距离的k-近邻算法
params inX：单一输入值，list or np.array
params dataSet：样本集，np.array
params labels：样本集标签，list or np.array
params k：int
returns sortedClassCount[0][0]：分类的类别
"""
# 计算输入值与样本集的距离——基于欧式距离
#numpy函数shape[0]返回dataSet的行数
dataSetSize = dataSet.shape[0]
#在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
#二维特征相减后平方
sqDiffMat = diffMat**2
#sum()所有元素相加，sum(0)列相加，sum(1)行相加
sqDistances = sqDiffMat.sum(axis=1)
#开方，计算出距离
distances = sqDistances**0.5
#返回distances中元素从小到大排序后的索引值
sortedDistIndicies = distances.argsort()
#定一个记录类别次数的字典
classCount = {}
for i in range(k):
#取出前k个元素的类别
voteIlabel = labels[sortedDistIndicies[i]]
#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
#计算类别次数
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
#key=operator.itemgetter(1)根据字典的值进行排序
#key=operator.itemgetter(0)根据字典的键进行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
#返回次数最多的类别,即所要分类的类别
return sortedClassCount[0][0]
#输入归一化
def autoNorm(dataSet):
"""
newValue=(oldValue-min)/(max-min) 将认一取值范围的特征值转化为[0,1]
params dataSet：归一化数集
returns normDataSet：归一化后的特征矩阵
returns ranges：数据范围
returns minVals：数据最小值
"""
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m, 1))
normDataSet = normDataSet/np.tile(ranges, (m, 1)) #element wise divide
return normDataSet, ranges, minVals
#算法测试
def handwritingclasstest(data_test,data_test_label,data_train,data_train_label,k):
"""
算法测试函数
params data_test：测试数集
params data_test_label：测试集的标签
params data_train：训练数集
params data_train_label：训练集的标签
params k：k近邻算法的k
"""
errorCount = 0.0
for i in range(data_test.shape[0]):
classifierResult = classify0(data_test[i, :], data_train, data_train_label, k)
print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, data_test_label[i]))
if (classifierResult != data_test_label[i]): errorCount += 1.0
print("错误率:%f%%" %(errorCount/float(numTestVecs)*100))
print(errorCount)
- sklearn实现算法
- sklearn.neighbors模块实现kNN
- sklearn.neighbors.KNeighborsClassifier
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)- 参数
- params n_neighbors - 默认为5，就是k-NN的k的值，选取最近的k个点。
- params weights - 默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
-
params algorithm - 快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。
- ball_tree将使用
sklearn.neighbors.BallTree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体; - kd_tree将使用
sklearn.neighbors.KDTree构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高; - brute将使用蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时
- ball_tree将使用
- params leaf_size - 默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
- params metric - 用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
- params p - p=1曼哈顿距离；p=2欧式距离
- params metric_params - 距离公式的其他关键参数，这个可以不管，使用默认的None即可
- params n_jobs - 并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。
- 方法
-
methods fit(X, y) - 使用X作为训练数据并将y作为目标值来拟合模型 参数
- params X- {阵列式，稀疏矩阵，BallTree，KDTree} - 训练数据。 如果数组或矩阵，如果metric ='precomputed'，则形成[n_samples，n_features]或[n_samples，n_samples]。
- params y - {数组式，稀疏矩阵} - shape的目标值= [n_samples]或[n_samples，n_outputs]
-
methods predict(X) - 预测提供的数据的类别标签
- params X - 测试样本；类似数组，形状（n_query，n_features）或（n_query，n_indexed）如果metric =='precomputed'
- ruturns y - 每个数据样本的类标签；形状数组[n_samples]或[n_samples，n_outputs]
-
methods get_params(deep=True) - 获取此估算工具的参数
- params deep - 如果为True，将返回此估计器的参数并包含作为估算器的子对象；布尔值，可选
- returns params - 映射到其值的参数名称。将字符串映射到任何字符串
-
methods kneighbors(X=None, n_neighbors=None, return_distance=True) - 找到一个点的K邻居。返回每个点的邻居的索引和距离。
- params X:类似数组，形状（n_query，n_features）或（n_query，n_indexed）如果metric ='''precomputed' - 查询点或点。如果未提供，则返回每个索引点的邻居。在这种情况下，查询点不被视为自己的邻居。
- params n_neighbors ： int - 要获取的邻居数（默认值是传递给构造函数的值）。
- params return_distance - 布尔值，可选。默认为True。 如果为False，则不会返回距离
- returns dist：数组 - 表示点数长度的数组，仅在return_distance = True时出现
- returns ind：数组 - 矩阵中最近点的指数。
- methods kneighbors_graph(X=None, n_neighbors=None, mode=’connectivity’) - 计算X中点的k-邻居的（加权）图
- methods predict_proba(X) - 测试数据X的返回概率估计。
- methods score(X, y, sample_weight=None) - 返回给定测试数据和标签的平均精度。
- methods set_params(**params) - 设置此估算器的参数。
-
methods fit(X, y) - 使用X作为训练数据并将y作为目标值来拟合模型 参数
- 参数
- sklearn.neighbors.KNeighborsClassifier
- sklearn.neighbors模块实现kNN
from sklearn.neighbors import KNeighborsClassifier as kNN
def kNNClassTest(data_test,data_test_label,data_train,data_train_label,k):
"""
params data_test：测试数集
params data_test_label：测试集的标签
params data_train：训练数集
params data_train_label：训练集的标签
params k：k近邻算法的k
"""
#构建kNN分类器
neigh = kNN(n_neighbors = k, algorithm = 'auto')
#拟合模型, data_train为训练数集,data_train_label为训练集的标签
neigh.fit(data_train, data_train_label)
#错误检测计数
errorCount = 0.0
#测试数据的数量
mTest = data_test.shape[0]
#从文件中解析出测试集的类别并进行分类测试
#获得预测结果
classifierResult = neigh.predict(data_test)
for i in range(mTest):
print("分类返回结果为%d\t真实结果为%d" % (classifierResult[i], data_test_label[i]))
if(classifierResult[i] != data_test_label[i]):
errorCount += 1.0
print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount/mTest * 100))
- 案例实现
- 案例1：约会网站配对
# 导入数据
def file2matrix(filename):
love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1}
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines) #get the number of lines in the file
returnMat = np.zeros((numberOfLines, 3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
index = 0
for line in arrayOLines:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
if(listFromLine[-1].isdigit()):
classLabelVector.append(int(listFromLine[-1]))
else:
classLabelVector.append(love_dictionary.get(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
#测试函数
def datingClassTest():
path = r'E:\C_all\Desktop\ML仓库\机器学习实战\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
hoRatio = 0.50 #hold out 10%
datingDataMat, datingLabels = file2matrix(path) #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)
datingClassTest()
the total error rate is: 0.068000
34.0
#应用
def classifyPerson():
path = r'E:\C_all\Desktop\ML仓库\机器学习实战\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(input(\
"percentage of time spent playing video games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix(path)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([
ffMiles,
percentTats,
iceCream,
])
classifierResult = classify0((inArr - minVals) / ranges, normMat,
datingLabels, 3)
print("You will probably like this person: %s" %
resultList[classifierResult - 1])
classifyPerson()
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person: in small doses
- 案例2：手写数字分类
#数据导入
from tensorflow.examples.tutorials.mnist import input_data
# 利用tensorflow代码下载MNIST
mnist = input_data.read_data_sets("/MNIST_data/", one_hot=False)
# 代码中的one_hot=True，表示将样本标签转化为one_hot编码
#测试函数
def handwritingclasstest():
errorCount = 0.0
for i in range(mnist.test.images.shape[0]):
classifierResult = classify0(mnist.test.images[i, :], mnist.train.images, mnist.train.labels, 10)
print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, mnist.test.labels[i]))
if (classifierResult != mnist.test.labels[i]): errorCount += 1.0
print("the total error rate is: %f" % (errorCount / float(mnist.test.images.shape[0])))
print(errorCount)
handwritingclasstest()
the total error rate is: 0.033200
332.0
