【机器学习算法】K近邻算法总结
算法基础 . 2019/12/11发布 . shanyonggang_web . 我要评论 . 718阅读

前言

K近邻算法算是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。日常应用场景如下:

  • 根据学生德智体美成绩,将学生分为几类
  • 根据一个县城的GDP、人口密度等数据,将全国的县城分为多个类别
  • 根据客户的信用、收入、生活习惯将客户分为多个类别
  • 根据电影场景中的亲吻数、打斗数等判断电影的类型
  • ......

基本原理

KNN算法相对比较简单,给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类(多数表决argmax),就把该输入实例分为这个类。

KNN算法的优缺点:

  • 优点:易于实现,无需估计参数,无需训练,支持增量学习,能对超多边形的复杂决策空间建模
  • 缺点:计算量较大,分析速度慢(因为要扫描全部训练样本并计算距离)

KNN的三要素:

  • K值选择:一般先选小的K值,然后进行交叉验证验证法选取最优K值
  • 距离度量:参考距离度量完整版
  • 分类决策规则:多数表决、加权表决

代码实现

首先创建训练数据集,如下:

import numpy as np
def createDataSet():
    group = np.array([[108,5],[115,8],[5,89],[1,101]])
    labels = ['动作片','动作片','爱情片','爱情片']
    return group,labels

编写分类函数代码,如下:

import operator
def classify0(inx,dataset,labels,k):
    # 获取数据的行数
    dataSetSize = dataset.shape[0]
    # 设计与dataset同样的行数(重复inx)
    new_inx = np.tile(inx,(dataSetSize,1))
    # 求取两个矩阵向量的差值
    diff = dataset - new_inx
    # 求取其平方值
    diffMat = diff ** 2
    # 将每行数据相加便于求距离,sum(0)列相加,sum(1)行相加
    sqDistances = diffMat.sum(axis=1)
    # 求取距离(开方求距离)
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndices = distances.argsort()
    #定一个记录类别次数的字典
    classCount = {}
    for i in range(k):
        #取出前k个元素的类别
        voteIlabel = labels[sortedDistIndices[i]]
        print(voteIlabel)
        #计算类别次数
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    print(sortedClassCount)
    return sortedClassCount[0][0]

输入预测数据进行分类预测,如下:

test = np.array([101,20])
group, labels = createDataSet()
movie_style = classify0(test, group, labels, 3)
print('需要判断的电影类型是:%s'% movie_style)

K近邻算法的一般流程为:

  • 收集数据:可以使用爬虫进行数据的收集,也可以使用第三方提供的免费或收费的数据。一般来讲,数据放在txt文本文件中,按照一定的格式进行存储,便于解析及处理。
  • 清洗数据:使用Python对数据进行解析、预处理。
  • 分析数据:可以使用很多方法对数据进行分析,例如使用Matplotlib将数据可视化。
  • 测试算法:计算错误率。
  • 使用算法:错误率在可接受范围内,就可以运行k-近邻算法进行分类。

skleran库

首先介绍sklearn库的安装:

在安装sklearn之前,需要安装两个库,即numpy+mkl和scipy。不要使用pip3直接进行安装,因为pip3默安装的是numpy,而不是numpy+mkl。第三方库下载地址:https://www.lfd.uci.edu/~gohlke/pythonlibs/

找到对应python版本的numpy+mkl和scipy,下载安装即可,如下图所示。

下载完成后使用如下命令进行安装

pip install C:\Users\Administrator\Downloads\scipy-1.4.0rc1-cp37-cp37m-win_amd64.whl

安装完依赖包后,使用如下命令安装sklearn库:

pip install scikit-learn

sklearn库中的knn算法简介:

官方文档:https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

主要使用sklearn.neighbors模块

from sklearn.neighbors import KNeighborsClassifier as kNN

可以引用如上方法引入KNN算法,KNN类中的方法如下:

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 )
  • n_neighbors int,可选(默认= 5),其为KNN算法中的K值

  • weights:默认是uniform,参数可以是uniform、distance,也可以是用户自己定义的函数。uniform是均等的权重,就说所有的邻近点的权重都是相等的。distance是不均等的权重,距离近的点比距离远的点的影响大。用户自定义的函数,接收距离的数组,返回一组维数相同的权重。

  • algorithm:快速k近邻搜索算法,默认参数为auto,可以理解为算法自己决定合适的搜索算法。除此之外,用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索,brute是蛮力搜索,也就是线性扫描,当训练集很大时,计算非常耗时。kd_tree,构造kd树存储数据以便对其进行快速检索的树形数据结构,kd树也就是数据结构中的二叉树。以中值切分构造的树,每个结点是一个超矩形,在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的,其构造过程是以质心C和半径r分割样本空间,每个节点是一个超球体。

  • leaf_size:默认是30,这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度,同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。

  • p :距离度量公式。这个参数默认为2,也就是默认使用欧式距离公式进行距离度量。也可以设置为1,使用曼哈顿距离公式进行距离度量。

  • metric::用于距离度量,默认度量是minkowski,也就是p=2的欧氏距离(欧几里德度量)。

  • metric_params:距离公式的其他关键参数,这个可以不管,使用默认的None即可。

  • n_jobs:并行处理设置。默认为1,临近点搜索并行工作数。如果为-1,那么CPU的所有cores都用于并行工作。

实际案例

本次我们以癌症检测作为实际案例,对KNN算法进行验证学习(引用sklearn库进行计算),其中数据集采用github找的数据,数据和源码均已存放至我的github

首先进行数据的读取,如下:

# 数据来源于github,第一列为病人id号,第二列为癌症诊断类型(良性和恶性两种),其余列为与发病率相关的特征
import pandas as pd
import numpy as np
from sklearn.neighbors import KNeighborsClassifier as KNN
from pandas import Series,DataFrame
data = pd.read_csv(r'E:\github\Machine__Learning\data\2.KNN\cancer_data\data.csv')

提取目标数据和特征数据,如下:

# 获取目标值(即诊断结果)
label = data['diagnosis']
# 训练数据,特征,即第三列之后的特征
char_value = data.iloc[:,2:]

划分数据集(将其划分为训练数据和测试数据),如下:

# 划分数据,其中10%作为测试集、90%作为训练集
# 第一种方法:
num = data.shape[0]
print(num*90//100)
train_data = data[:512]
test_data = data[512:]
# 第二种方法
from sklearn.model_selection import train_test_split
label_train,label_test,char_value_train,char_value_test = train_test_split(label,char_value,test_size=0.2)
# 本次使用第二种方法

构建KNN算法并进行数据预测,如下:

# 构建knn算法
knn = KNN(n_neighbors=5, algorithm='ball_tree')
# 算法训练数据
knn.fit(char_value_train,label_train)
# 使用算法进行预测()
predict_result = knn.predict(char_value_test)

结果对比,将预测数据与实际数据进行比对,并计算正确率,如下:

# 预测结果与实际结果的对比
predict_result == label_test.values
# 求正确率
(predict_result == label_test.values).mean()
# 结果
0.9298245614035088

结果如下图所示:

最终我们得出结果为:0.9298245614035088,效果还是比较满意的。

补充知识

训练集和测试集的数据划分:

from sklearn.model_selection import train_test_split
x_train,x_test,y_train,y_test = train_test_split(x,y, test_size=0.29, random_state=42)
# 其中x,y为numpy数组;x为样本集\y为样本标签;
# test_size:如果是浮点数,在0-1之间,表示样本占比;如果是整数的话就是样本的数量
# random_state:是随机数的种子

KNN中的交叉验证:

参考文档:https://www.cnblogs.com/lzhc/p/9175707.html

交叉验证优点:

  • 交叉验证用于评估模型的预测性能,尤其是训练好的模型在新数据上的表现,可以在一定程度上减小过拟合。
  • 还可以从有限的数据中获取尽可能多的有效信息。
from sklearn.model_selection import cross_val_score
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
estimator = KNeighborsClassifier()
scores = cross_val_score(estimator,x,y,scoring='accuracy')
np.mean(scores)

数据预处理:

from sklearn.preprocessing import MinMaxScaler
# 基于特征的规范化
X_transformed = MinMaxScaler().fit_transform(x)
estimator = KNeighborsClassifier()
# estimator 估计器
# transform 转换器
transformed_score = cross_val_score(estimator,X_transformed,y,scoring='accuracy')
print('The average accuracy is {0:.1f}%'.format(np.mean(transformed_score)*100))

 


  • 有疑问请在下方评论区留言,我会尽快回复。
  • Email私信我: 511248513@qq.com 或添加博主 微信
本文作者:shanyonggang_web
发布时间:2019年12月11日 14:55
许可协议: 署名-非商业性使用 4.0 国际许可协议
知识共享许可协议     转载请保留原文链接及作者
正在加载今日诗词....
您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的


登录 后回复

当前暂无评论,点击登录来做第一个吃螃蟹的人吧!