机器学习中分类算法之K近邻分类
物以类聚，人以群分，相似的东西很可能具有相似的属性。利用这个原理，我们可以对数据进行分类，将其划分到最相近的类别或者最接近的邻居。本期给大家分享机器学习中五种常见分类算法之一：K近邻（K-Nearest Neighbors，KNN）。
近邻分类器就是把未标记的案例归类为与它们最相似的带有标记的案例所在的类，其特点可归纳为如下：
①从技术上来说，没有抽象化的步骤；
②训练阶段进行得较快，预测的过程往往相对较慢；
③高度依赖于训练案例，又称为基于案例的学习（instance-based learning）或机械学习（rote learning）；
④允许学习算法发现数据中的自然模式，但不会试图将数据拟合为一个预先设定的形式，即不会建立模型，因而属于非参数学习方法。
虽然近邻分类器被认为是“懒惰”学习器，但其功能极其强大，已成功运用于计算机模式识别、基因数据模式识别、癌症的自动化筛查等领域。
简单地说，KNN算法就是，对于测试集中每一条记录，确定训练集中与该记录相似度“最近”的k条记录，其中k是一个预先指定的整数，未标记的测试实例被分配到k个近邻中占比最大的那个类中。
例如：指定k=5，对于一个新的待分类对象，其有3个近邻在A类，1个在B类，1个在C类，则A占比最大为3/5，该对象就被分到A类。
由上面的定义我们发现需要解决两大问题：
其一，如何衡量相似度？
传统上KNN算法采用的是欧氏距离(Euclidean distance)，度量最短的直线距离。假设p和q是待比较的案例，各自有n个特征，分别为(p1,p2,…,pn)和(q1,q2,…,qn)，则欧氏距离公式如下：
另外一些常见的距离度量有：曼哈顿距离(Manhattan distance)，最大距离(Maximum distance)，堪培拉距离(Canberra distance)，二项距离(Binary distance)，闵可夫斯基距离(Minkowski distance)。
其二，如何选择一个合适的k？
确定邻居数量将决定把模型推广到未来数据时分类性能的好坏，选择一个大的k会减少噪声导致的模型波动，但会使得分类器产生偏差，举一个极端的例子：k等于训练集中案例条数，由于每一个案例都会在最终的投票表决中出现，所以最常见的训练类总会获得大多数的票。选择较小的k则可以更精细地拟合训练数据，但会使得噪声数据或异常值过度影响案例的分类，也即方差较大，举一个极端的例子：k=1时的单一近邻，如果一些训练案例被意外地贴错了标签，而待分类的案例恰好最接近被错误标记的训练案例，那么它就会被分到错误的类别中。
因而，过度拟合和低度拟合训练数据之间的平衡问题称为偏差-方差权衡(bias-variance tradeoff)，通常k取值在3~10之间，常见的做法是令k等于训练集中案例数量的平方根；另一种做法是基于各种测试集来测试选取可以提供最佳分类性能的k值。有研究者称，“更大的、更具有代表性的训练集可以使得k值选择并不那么重要”，然而正如本号之前的一篇文章“样本量达到多少才算大？”所探讨的，“够大、够代表性”很难界定，小编认为最好还是通过测试集来选取k值。
其实还有一个潜在的问题需要解决，即数据准备。
在应用KNN算法之前，通常将特征转换到一个标准的范围内，由上述公式我们也可以看出，如果某个特征的值相较于其他特征很大，则距离的度量会强烈地被这个特征的值所支配。
转换方法常见有两种：
(1)min-max标准化，使所有值落在0-1范围内:
(2)z-score标准化:
对于特征是名义变量的，则需要事先哑元化。
实例演练
1.数据准备
数据集包括569例细胞活检案例，第一列为病人ID编号，第二列为癌症诊断结果，其他30个特征是数值型的实验室测量结果。癌症诊断结果用M表示恶性，B表示良性。
#设置工作目录
setwd("D:\\学海拾贝之统计\\数据源")
#读取数据
data=read.delim("wisc_bc_data.txt",sep=",",header=F)
#查看数据条目
str(data)
#重命名数据集
names(data)=c("id","diagnosis",paste0("v",seq(1:30)))
#查看良恶性案例的大致分布
table(data$diagnosis)
#将诊断结果转化为因子并为其赋予标签
data$diagnosis=factor(data$diagnosis,levels=c("B","M"),labels=c("Benign","Malignant"))
#将30个特征数据标准化
install.packages("chipPCR")
library(chipPCR)
#可将“minm”换成“zscore”
standardize=function(x)data_n=as.data.frame(lapply(data[,c(3:32)],standardize))
summary(data_n)
#选取前469行案例作为训练集，后100例作为测试集，实际操作应随机选取
train=data_n[1:469, ]
test=data_n[470:569, ]
train_labels=data[1:469,2]
test_labels=data[470:569,2]
2.训练模型并预测
#安装class添加包并调用
install.packages("class")
library(class)
#使用knn( )函数来给测试集分类，这里k选取469开平方的近似值21
test_pred=knn(train=train,test=test,cl=train_labels,k=21)
3.评估模型性能
install.packages("gmodels")
library(gmodels)
CrossTable(x=test_labels,y=test_pred,prop.chisq=F)
结果如下：
仅有2%的案例被分错，几行代码即可达到98%的准确度，你难道不想拿你的数据试试么？
4.提高模型性能
①改用不同的数据标准化方法，如：z-score转换；
②测试其他k值。
这里不再探讨细化，有待感兴趣的童鞋来探索！
参考文献：
【1】http://archive.ics.uci.edu/ml/index.php
【2】BrettLantz,兰兹,李洪成,等.机器学习与R语言[M].机械工业出版社, 2015.
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20180523G0FSGI00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
