1、k-近邻算法
k-近邻算法简称kNN，是一种常用的监督学习方法，它的工作机制简单来说就是：在给定的测试样本中，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。
- 在分类中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测的结果；
- 在回归中可使用“平均法”，即将这k个样本的实值输出标记值的平均值作为预测结果。
还可基于距离的远近进行加权平均和加权投票。
1.1、度量距离
设特征空间中X是n维实数向量Rn, xi, xj∈X, xi=(xi1,xi2,...,xin), xj=(xj1,xj2,...,xjn).
xi,xj的Lp距离为=(\sum_{l=1}{n}|x_i{l}-x_j{l}|{p})^{\frac{1}{p}},(p≥1)$$)
当p=2时，为欧式距离（Euclidean distance）
=(\sum_{l=1}{n}|x_i{l}-x_j{l}|{2})^{\frac{1}{2}}$$)
当p=1时，为曼哈顿距离（Manhattan distance）
=\sum_{l=1}{n}|x_i{l}-x_j^{l}|$$)
当p=∞时，是各个坐标距离的最大值
=\max_{l}\sum_{l=1}{n}|x_i{l}-x_j^{l}|$$)
1.2、k值的选取
k值的选取会对k近邻法的结果产生重大影响。
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例相似的训练实例才会对预测结果产生作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰好是噪声，预测就会出错，亦即k值的减小就意味着整体的模型变复杂，容易发生过拟合。
如果选择较大的k值，就相当于用较大的邻域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例不相似的训练实例也会对预测产生作用，是预测发生错误。k的增大就意味着整体的模型变得简单。
2、算法实现
这次仍然使用学习决策树算法时候的数据集进行实验，
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 乌黑 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 乌黑 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 4 | 青绿 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 浅白 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青绿 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 是 |
| 7 | 乌黑 | 稍蜷 | 浊响 | 稍糊 | 稍凹 | 软粘 | 是 |
| 8 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 乌黑 | 稍蜷 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 10 | 青绿 | 硬挺 | 清脆 | 清晰 | 平坦 | 软粘 | 否 |
| 11 | 浅白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 软粘 | 否 |
| 13 | 青绿 | 稍蜷 | 浊响 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 14 | 浅白 | 稍蜷 | 沉闷 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 否 |
| 16 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青绿 | 蜷缩 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
由于各种距离需要使用数值进行计算，上述“色泽”、“根蒂”、“敲声”、“纹理”、“脐部”和“触感”6个特征变量都是类别变量（factor），我们需要将其转化为哑变量（dummy variables）。
例如在“色泽”中，令数值0代表“乌黑”，数值1代表“青绿”，数值2代表“浅白”，以此进行转换。
其中数据集（data1.txt）中的格式如下图所示：
下述的代码即针对上述数据集进行哑变量转换的,
filename = 'data1.txt'
def factor2dummy_variable(filename):
fr = open(filename,encoding = 'utf-8')#以utf-8读取文件
dataColumns = fr.readline()#去除首行
arrayLines = fr.readlines()#读取所有行
lines = np.array([line.replace('\n','').split('\t') for line in arrayLines]).T#按行指定分隔符，并进行转置
lines = lines[1:,:]#实际使用的数据部分
setFactors = [set(line) for line in lines]#set操作，只保存一种分类的集合
k = 0
for i in setFactors:
dummy_num = 0
line = lines[k]
for j in i:
line[line == j] = dummy_num#哑变量转换
dummy_num += 1
k += 1
lines = lines.T#转置
return lines
将转换好的数据集保存到文件（data2.txt）,
lines = factor2dummy_variable(filename)
dataSet = lines
filename = 'data2.txt'
def data2txt(dataSet,filename):
fw = open(filename,'w',encoding='utf-8')#以utf-8编码写入
for line in dataSet:
for element in line:
fw.write(element)
fw.write('\t')#tab键分割符号
fw.write('\n')#换行
fw.close()
转换好的数据集格式如下图所示：
处理完毕上述变量后，需要将转换好的数据文件转化成numpy可以使用的数据集形式，
filename = 'data2.txt'
def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines()#读取所有行
numberOfLines = len(arrayOLines)#计算记录数量
numberOfcloumns = len(arrayOLines[0].replace('\t\n','').split('\t')) - 1#计算变量数量
returnMat = np.zeros((numberOfLines, numberOfcloumns))
classLabelVector = []
index = 0
for line in arrayOLines:
line = line.strip()#去除空格
listFromLine = line.split('\t')#按tab键分割
returnMat[index, :] = listFromLine[:-1]#得到分类变量数组
classLabelVector.append(int(listFromLine[-1]))#类别变量数组
index += 1
return returnMat, classLabelVector
注：有时候由于各类变量之间数值差别太大，同时量纲也各不相同，这时候就需要进行归一 化操作，将各变量的范围设置在0~1之间，以消除量纲影响，加快运算速度。
其中归一化的式子如下：
}}{\min{(x)}-\max{(x)}}$$)
下述代码即进行归一化操作：
def autoNorm(dataSet):
minValue = dataSet.min(0)#得到每列的最小值
maxValue = dataSet.max(0)#每列最大值
ranges = maxValue - minValue#分母
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]#行数
normDataSet = dataSet - np.tile(minValue, (m,1))#分子
normDataSet = normDataSet/np.tile(ranges, (m,1))
return normDataSet, ranges, minValue
经过上述处理，这里通过计算欧式距离进行kNN分类，具体代码如下：
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]#得到行数
diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#计算输入向量inX与训练样本的差
sqDiffMat = diffMat**2#计算差值的平方
sqDistances = sqDiffMat.sum(axis = 1)#距离平方和
distances = sqDistances**0.5#开方得到距离
sortedDistIndicies = distances.argsort()#距离进行排序,得到排序的下标
classCount = {}
for i in range(k):#确定前k个距离中最小元素所属分类
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#对出现的label进行计数
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),
reverse = True)#按照计数值进行降序排序
#operator.itemgetter(1)确定一个函数取出classCount中的第一个域的值，即将value取出
return sortedClassCount[0][0]#返回最大的计数值的分类
由此，即进行了kNN的分类操作，下面通过以下代码对分类效果进行测试（测试数据集仍是训练数据集合）
dataLines, datalabels = file2matrix('data2.txt')
i=0
errorCount = 0.0
for line in dataLines:
print('记录%s的原始分类是:%d，划分分类是:%d' %(str(line), datalabels[i],
classify0(line, dataLines ,datalabels, 1)))
if (datalabels[i] != classify0(line, dataLines ,datalabels, 1)):
errorCount += 1.0
i += 1
print('错误率为: %f' %(errorCount/float(len(dataLines))))
可以看出错误率为0.000000，正确率达到了100%。可以看出准确度不错，当然此准确度也与数据量的大小有关，后续可以将数据集扩大，或者使用不同的数据集进行训练测试，来验证分类效果。
下面代码是通过Scikit - Learn库进行数据集的训练和测试过程。
import numpy as np
from sklearn import neighbors
data = []
labels = []
with open('data2.txt') as ifile:
for line in ifile:
tokens = line.replace('\t\n','').split('\t')
data.append([float(tk) for tk in tokens[:-1]])
labels.append(tokens[-1])
x = np.array(data)
y = np.array(labels)
clf = neighbors.KNeighborsClassifier(algorithm = 'kd_tree', n_neighbors = 1)
clf.fit(x,y)
answer = clf.predict(x)
print('准确率为:%f' % float(np.mean(answer == y)))#正确率
其准确率可以达到100%。
值得注意的是，上述neighbors.KNeighborsClassifier()中，存在很多可以自行调节的参数，这里可以查看官方文档（http://scikit-learn.org/stable/documentation.html） 并进行相关操作。
网友评论