机器学习(四)：K-近邻(KNN)算法原理及案例分析
2019-12-14 本文已影响0人
风之舟
一、算法简介
k-近邻算法(K-NearestNeighbor,简称KNN)是1967年由Cover T和Hart P提供的一种基本分类方法，数据挖掘分类技术中最简单的方法之一。KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则样本也属于这个类别，并具有这个类别上样本的特性。
如上图所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例是2/3,绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
二、原理
1、距离公式：
欧氏距离:欧几里得距离或欧几里得度量是欧几里得空间中两点之间“普通”（即直线）距离。使用这个距离，欧式空间成为度量空间。相关联的范数成为欧几里得范数。较早的文献称之为毕达哥拉斯度量。
-
二维空间公式：
-
三维空间的公式：
-
n维空间的公式
2、算法说明
通俗地讲，就是计算一个点与样本空间所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则该点就属于这个占比最大的分类。
一般流程：
- 收集数据：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。
- 准备数据：可以使用python解析，预处理数据
- 分析数据：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
- 特征工程：标准化，KNN数据需要进行标准化
- 进行算法流程：得出预测结果，计算准确率
- 使用算法：准确率在可接受的范围，就可以运行K-近邻算法进行分类
三、实战分析
1、约会网站配对效果判定
1.1背景
海伦女士一直使用在线约会网站寻找适合自己的约会对象，尽管约会网站会推荐不同的选择，但是她并不是喜欢每一个人，经过一番总结，她发现自己交往过的人可以进行如下分类：
- 不喜欢的人(didntLike)
- 魅力一般的人(smallDoses)
- 极具魅力的人(largeDoses)
经过一段时间的数据收集，她把这些数据放在文本文件datingTestSet.txt中，每个样本占据一行，总共有1000行。
数据特征： - 每年获得的飞行常客里程数
- 玩视频游戏所消耗时间百分比
-
每周消费的冰激凌公升数
数据集
1.2准备数据：数据解析
给出的数据包括了特征值与分类标签向量，我们先将数据处理一下，将特征值与分类标签分开：
# -*- coding: UTF-8 -*-
import matplotlib.pyplot as plt
import matplotlib.lines as mlines
import numpy as np
import operator
def dataset():
"""
打开并解析文件，对数据进行分类:
1代表不喜欢
2代表魅力一般
3代表极具魅力
:return:
"""
#numpy矩阵的形式
#打开文件
fr = open('../../数据集/机器学习/分类算法/海伦约会/datingTestSet.txt')
#读取文件的所有内容
arrayOne = fr.readlines()
#得到文件行数
numoflines = len(arrayOne)
#返回numpy矩阵，解析完成的数据：numoflines
returnMat = np.zeros((numoflines,3))
#返回分类标签向量
classLabelVector = []
#行的索引
index = 0
for line in arrayOne:
# s.strip(rm)，当rm空时,默认删除空白符(包括'\n','\r','\t',' ')
line = line.strip()
# 使用s.split(str="",num=string,cout(str))将字符串根据'\t'分隔符进行切片。
listFromLine = line.split('\t')
# 将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵
returnMat[index,:] = listFromLine[0:3]#每三个赋值给矩阵的每一行
if listFromLine[-1] == 'didntLike':
classLabelVector.append(1)
elif listFromLine[-1] == 'smallDoses':
classLabelVector.append(2)
elif listFromLine[-1] == 'largeDoses':
classLabelVector.append(3)
index += 1
return returnMat,classLabelVector
if __name__ == "__main__":
returnMat,classLabelVector = dataset()
print(returnMat)
print(classLabelVector)
1.3 分析数据：数据可视化
简单的处理一下数据之后，我们对数据进行可视化,看一下特征之间的关系，
def showdatas(x,y):
"""
数据可视化
:return:
"""
fig = plt.figure(figsize=(15,15))
#第一张散点图显示视频游戏与飞机里程数占比关系
ax1 = fig.add_subplot(2,2,1)
colors = []
#设置图例
didntLike = mlines.Line2D([], [], color='black', marker='.',markersize=6, label='didntLike')
smallDoses = mlines.Line2D([], [], color='orange', marker='.',markersize=6, label='smallDoses')
largeDoses = mlines.Line2D([], [], color='red', marker='.',markersize=6, label='largeDoses')
for i in y:
if i == 1:
colors.append('black')
if i == 2:
colors.append('orange')
if i == 3:
colors.append('red')
ax1.scatter(x=x[:,0],y=x[:,1],color=colors,s=15)
ax1.set_title('每年获得的飞行常客里程数与玩视频游戏所消耗时间占比')
ax1.set_xlabel('每年获得的飞行常客里程数')
ax1.set_ylabel('玩视频游戏所消耗时间占比')
# 添加图例
ax1.legend(handles=[didntLike,smallDoses,largeDoses])
#第二张散点图显示视频游戏与冰激凌之间的关系
ax2 = fig.add_subplot(2,2,2)
ax2.scatter(x=x[:,1],y = x[:,2],color=colors,s=15)
ax2.set_title('视频游戏消耗时间与每周消费的冰激凌公升数')
ax2.set_xlabel('玩视频游戏消耗时间')
ax2.set_ylabel('每周消费的冰激凌公升数')
# 添加图例
ax2.legend(handles=[didntLike,smallDoses,largeDoses])
# plt.show()
# print(colors)
#第三张散点图显示飞机里程数与冰激凌公升数的关系
ax3 = fig.add_subplot(2,2,3)
ax3.scatter(x = x[:,0],y = x[:,2],color=colors,s = 15)
ax3.set_title('每年飞机飞行里程数与每周消费的冰激凌公升数')
ax3.set_xlabel('每年获得的飞行常客里程数')
ax3.set_ylabel('每周消费的冰激凌公升数')
# 添加图例
ax3.legend(handles=[didntLike, smallDoses, largeDoses])
plt.show()
return None
通过图像进行简单的分析我们发现，如果考虑玩游戏消耗时间占比与每年获得的飞行常客里程数的话，感觉海伦喜欢有生活质量的男人，毕竟能经常飞，还有时间玩游戏，并且占有一定时间比例，大概率是一个生活悠闲，追求质量的人。
1.4、数据归一化
通过1.1我们发现数字差值比较大的属性对计算结果的影响比较大，为了消除这种不同取值范围的特征值影响过大的问题，我们通常采用的方法是将数值归一化，如将取值范围处理为[0,1]之间，前提是我们认为这三种特征是同等重要的。
-
归一化的计算公式：
def autoNorm(x):
"""
数据归一化
newValue = (oldValue - min) / (max - min)
:param x:
:return:
"""
#这边还可以做一些改进，筛掉一些数据
#获得数据的最小值
minvals = x.min(0)
maxvals = x.max(0)
#最大值和最小值的范围
ranges = maxvals - minvals
#shape（x）返回x的矩阵行列数
normx = np.zeros(np.shape(x))
#返回x的行数
m = x.shape[0]
#原始值减去最小值
normx = x - np.tile(minvals,(m,1))
#除以最大和最小值的差，得到归一化的数据
normx = normx / np.tile(ranges,(m,1))
#返回归一化数据结果，数据范围，最小值
return normx,ranges,minvals
if __name__ == "__main__":
returnMat,classLabelVector = dataset()
normx, ranges, minvals = autoNorm(returnMat)
# classifyDataset(normx,classLabelVector)
# showdatas(returnMat,classLabelVector)
print(normx)
归一化后的结果
1.5 测试算法
将数据进行归一化后，我们先将数据集划分出测试集与训练集，然后进行测试算法的工作，这里我们选择90%的数据为训练集，10%的数据为测试集，
def classify(x_data,y_data,labels,k):
"""
Knn算法，分类器
x_data：训练集
y_data:测试集
labels:分类标签
k：选取的分类区域
:return:
"""
#返回训练集的行数
xdatasize = y_data.shape[0]
#将测试集在行列上进行复制，并减去训练集
diffMat = np.tile(x_data,(xdatasize,1)) - y_data
#求特征矩阵差的平方
sqdiffMat = diffMat**2
#平方求和
sqDistance = sqdiffMat.sum(axis=1)
#开方计算距离
distance = sqDistance ** 0.5
#返回距离从小到大排序后的索引值
sortedDistance = distance.argsort()
#定一个记录类别次数的字典
classified = {}
#将排序后的类别记录
for i in range(k):
#选出前k个元素的类别
votedlabels = labels[sortedDistance[i]]
# dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
# 计算类别次数
classified[votedlabels] = classified.get(votedlabels,0) + 1
# python3中用items()替换python2中的iteritems()
# key=operator.itemgetter(1)根据字典的值进行排序
# key=operator.itemgetter(0)根据字典的键进行排序
# reverse降序排序字典
sortedCounts = sorted(classified.items(), key=operator.itemgetter(1), reverse=True)
#第一个存放的就是出现次数最多的类别
return sortedCounts[0][0]
def classifyDataset(normx,labels):
"""
划分测试集与训练集
将训练集的10%划分为测试集
:return:
"""
alpha = 0.1
#获得归一化后数据集的行数
m = normx.shape[0]
#10%的数据为测试集
numtest = int (m * alpha)
#分类错误计数
errorcount = 0.0
#调用算法 进行分类
for i in range(numtest):
# 前numtest为测试集，后m-numtest为训练
classfyresult = classify(normx[i,:],normx[numtest:m,:],labels[numtest:m],4)
print("分类结果:%d\t真实类别:%d" % (classfyresult,labels[i]))
if (classfyresult != labels[i]):
errorcount += 1
print("错误率为：%f%%" % (errorcount / float(numtest)* 100))
return None
if __name__ == "__main__":
returnMat,classLabelVector = dataset()
normx, ranges, minvals = autoNorm(returnMat)
classifyDataset(normx,classLabelVector)
# showdatas(returnMat,classLabelVector)
# print(normx)
运行结果
通过上图的运行结果我们发现，错误率为4%，这是一个相当不错的结果。如果改变alpha与k值，错误率随着变脸值的变化而变化。大家可以下去试一下。
2、预测一个人签到的地方（Kaggle比赛项目）
这个比赛是由facebook与kaggle联合举行的一场比赛，目的是预测一个人想签到哪个地方，为了比赛的目的，Facebook创建了一个人工世界，由10万×10公里的正方形中的100000个地方组成，对于给定的一组坐标，我们的任务是返回最可能的位置的排名列表，数据被制作成类似于来自移动设备的位置信号，从而更具真实性。
首先，我们来看一下数据，
数据相对较大，有几百万行，这里只展示一小部分。
第二个案例我们将不再把算法的具体步骤写出来，sklearn有专门封装好的KNN算法，我们只需要调用一下，改变一下参数即可
-
数据预处理
先导入一下需要用到的包，
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
1、数据量问题
一方面数据量过大，另一方面，有些数据值较小，研究价值不大，我们将这部分数据进行删除。
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
print(data.count(axis=0))
# 数据预处理
#缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
print(data.count(axis=0))
if __name__ == "__main__":
knn()
我们看一下结果：
也就是说原先由29118021条数据，经过处理后，数据有62594条。
2、时间处理
这里的时间是时间戳，我们将其转成标准格式，并分割，以此添加一些特征值，
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
#print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
print(data.head())
if __name__ == "__main__":
knn()
处理完之后可以发现，多出了day,hour,weekday等几列数据。
3、删除一些没用的数据
经过上面时间处理之后，time这一列已经变成了三列(day,hour,weekday)数据，time时间戳的数据就用不到了，我们可以将它删掉，
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
# print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
# print(data.head())
#4、删除没用的数据
data = data.drop(['time'],axis=1)
print(data.head())
if __name__ == "__main__":
knn()
5、筛选掉不符合条件的值
这里我们将签到次数少于3次的筛掉。
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
# print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
# print(data.head())
#4、删除没用的数据
data = data.drop(['time'],axis=1)
# print(data.head())
#5、将签到位置少于n个用户的删除
place_count = data.groupby('place_id').count()
print(place_count)
tf = place_count[place_count.row_id > 3].reset_index()
data = data[data['place_id'].isin(tf.place_id)]
print(data)
if __name__ == "__main__":
knn()
上面是根据条件筛选的结果，下面是删掉数据后的结果。
6、取特征值与目标值，并分割测试集与训练集
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
# print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
# print(data.head())
#4、删除没用的数据
data = data.drop(['time'],axis=1)
# print(data.head())
#5、将签到位置少于n个用户的删除
place_count = data.groupby('place_id').count()
# print(place_count)
tf = place_count[place_count.row_id > 3].reset_index()
data = data[data['place_id'].isin(tf.place_id)]
# print(data)
#
#取出数据当中的特征值和目标值
y=data['place_id']
x=data.drop(['place_id'],axis=1)
x=data.drop(['row_id'],axis=1)
#
#进行数据集的分割
x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)
if __name__ == "__main__":
knn()
这里没有把分割后的测试集与训练集展示出来，有兴趣的同学可以输出看一下。
7、特征标准化
特征归一化与特征标准化是特征预处理的重要方法，目的是降低某特征值过大对结果的影响，特征标准化是KNN算法最常用的特征处理方法，它将原始特征值处理为服从均值为0，方差为1的正态分布。
-
标准化公式：
关于特征标准化，sklearn中封装有标准化的API，scikit-learn.preprocessing.StandardScaler,我们直接调用就可以，
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
# print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
# print(data.head())
#4、删除没用的数据
data = data.drop(['time'],axis=1)
# print(data.head())
#5、将签到位置少于n个用户的删除
place_count = data.groupby('place_id').count()
# print(place_count)
tf = place_count[place_count.row_id > 3].reset_index()
data = data[data['place_id'].isin(tf.place_id)]
# print(data)
#
#取出数据当中的特征值和目标值
y=data['place_id']
x=data.drop(['place_id'],axis=1)
x=data.drop(['row_id'],axis=1)
#
#进行数据集的分割
x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)
# 特征工程(标准化)
std=StandardScaler()
# 对测试集和训练集的特征值进行标准化
x_train = std.fit_transform(x_train)
x_test = std.fit_transform(x_test)
print(x_train)
print(x_test)
if __name__ == "__main__":
knn()
8、进行算法流程，得出预测结果和准确率
KNN算法在sklearn提供的
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm='auto')中，
| 参数 | 说明 |
|---|---|
| n_neighbors，int,可选（默认=5） | k_neighbors查询默认使用的邻居数 |
| algorithm，{'auto','ball_tree','kd_tree','brute'} | 'ball_tree'将会使用BallTree,'kd_tree'将使用KDTree.'auto'将尝试根据传递给fit方法的值来决定最适合的算法。（不同实现方式影响效率 ） |
我们来看一下测试结果，
def knn():
"""
knn预测分类
:return:
"""
# 读取数据
data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
# print(data.count(axis=0))
# 数据预处理
#1、缩小数据范围
data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
# print(data.count(axis=0))
#2、处理时间数据
data['time'] = pd.to_datetime(data['time'], unit='s')
#把日期格式转换成 字典格式
time_value = pd.DatetimeIndex(data['time'])
# print(time_value)
#3、增加分割的日期数据
data['day'] = time_value.day
data['hour']= time_value.hour
data['weekday'] = time_value.weekday
# print(data.head())
#4、删除没用的数据
data = data.drop(['time'],axis=1)
# print(data.head())
#5、将签到位置少于n个用户的删除
place_count = data.groupby('place_id').count()
# print(place_count)
tf = place_count[place_count.row_id > 3].reset_index()
data = data[data['place_id'].isin(tf.place_id)]
# print(data)
#
#取出数据当中的特征值和目标值
y=data['place_id']
x=data.drop(['place_id'],axis=1)
x=data.drop(['row_id'],axis=1)
#
#进行数据集的分割
x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)
# 特征工程(标准化)
std=StandardScaler()
# 对测试集和训练集的特征值进行标准化
x_train = std.fit_transform(x_train)
x_test = std.fit_transform(x_test)
# 进行算法流程
knn = KNeighborsClassifier(n_neighbors=7)
#fit predict score
knn.fit(x_train,y_train)
#得出预测结果
y_predict = knn.predict(x_test)
print("预测的目标签到位置为：",y_predict)
#得出准确率
print("预测的准确率：",knn.score(x_test,y_test))
return None
if __name__ == "__main__":
knn()
预测结果是62.8%，结果并不是很理想，还有很多可以改进的地方，比如数据集的筛选可以重新设置一下，n_neighbors可以设置为5...等等，大家可以下去试一下。KNN算法的实例分析到这里就结束了，最后我们总结一下KNN算法的优缺点。
四、算法总结
1、优点
- 简单，易于理解，易于实现，无需估计参数，无需训练
- 适合对稀有事件进行分类
- 特别适合于多分类（对象具有多个类别标签），KNN比SVM的表现要好。
- 可用于数值型数据和离散型数据
- 对异常值不敏感
2、缺点 - 计算复杂性高，空间复杂性高
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）
- 一般数值很大的时候不用这个，计算量太大；但是单个样本又不能太少，否则容易发生误分
- 最大的缺点是无法给出数据的内在含义
KNN算法到这里就讲完了，文中的第一个案例是参考的非常优秀的博主Jack-Cui : http://blog.csdn.net/c406495762的博客，有兴趣的同学可以看一下。
接下来的这段时间，主要是更新机器学习的算法，希望有兴趣的同学可以关注评论，一起学习。
