k临近法
(k-Nearest Neighbor, kNN)是最简单的机器学习算法之一,但它仍然被广泛应用在面部识别,电影/音乐推荐,检测疾病等方面.如果一个概念很难定义,但是当你看到它的时候知道它是什么,那么kNN算法就可能是合适的方法.
kNN算法源于这样一个事实:
它使用关于一个案例的k个近邻的信息来分类无标记的例子,字母k是一个可变选项,表示任意数目的近邻.在选定k之后,kNN算法需要一个已经分好类的训练数据集,然后对没有分类(没有标记)的记录进行分类,kNN确定训练数据集中与该记录相似度"最近"的k条记录,将无标记的测试例子分配到k个近邻中占比最大的那个类中.
下面通过一个例子来形象表示kNN近邻分类算法的原理(来源网络博客):
从上图中我们可以看到，图中的数据集都有了自己的标签，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。
如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形.
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形.
我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。
KNN是一种基于记忆的学习
(memory-based learning)，也是基于实例的学习(instance-based learning)，属于惰性学习(lazy learning)。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。
衡量近似度的方法:
最常用的是采用欧式距离(Euclidean distance),欧式距离是通过直线距离(as the crow flies)来度量,即最短的直线路线.另一种常见的距离度量是曼哈顿距离(anhattan distance),即两点在南北方向上的距离加上在东西方向上的距离.
下图中红线代表曼哈顿距离，绿色`代表欧氏距离，蓝色和黄色代表等价的曼哈顿距离.
曼哈顿距离和欧式距离
对于名义特征，如 性别，类别或其他属性需要将其转换为数值型格式。一种典型的解决方法就是利用哑变量编码（dummy coding）,其中1表示一个类别,0表示其他类别，例如，可以构建性别变量的哑变量编码：
乳腺癌案例样本数据
可以看出各个特征的范围相差较大，直接使用原始数据计算距离将使分类器出现问题，所以应该使用标准化方法重新调整特征的值。
首先使用R读入数据并进行整理，代码及注释如下：
rm(list=ls())
setwd("D:\\OTHER\\R_ML\\Knn")
# 读入数据：
wbcd<-read.table("./wdbc.data.txt",stringsAsFactors = F,header = T)
# 删除ID：
wbcd<-wbcd[,-1]
# 查看肿瘤和良性的比例：
prop.table(table(wbcd$Diagnosis))
# 将Diagnosis转为因子并给标签
wbcd$Diagnosis<-factor(wbcd$Diagnosis,levels=c("B","M"),labels = c("Benign","Malignant"))
prop.table(table(wbcd$Diagnosis))
可以看出数据案例中恶性肿瘤占62.7%，良性占37.2%：
良性和恶性肿瘤所占比例
接着进行min-max标准化：
# 由于不同特征的范围差别很大，所以需要Min-Max归一化：
normalize<-function(x){
return((x-min(x))/(max(x)-min(x)))
}
# 使用lapply对每一列进行标准化
wbcd_n<-as.data.frame(lapply(wbcd[,2:31],normalize))
将数据分为两部分：一部分是训练集（随机抽取469条）；一部分是是评估模型准确性的测试集（剩下的100条）
# 随机取样100个作为测试集：
test_100<-sample(1:nrow(wbcd_n),100)
# 剩下的469个是训练集：
train_w<-setdiff(1:nrow(wbcd_n),test_100)
# 提取测试集数据：
wbcd_test<-wbcd_n[test_100,]
# 提取训练集数据：
wbcd_train<-wbcd_n[train_w,]
# 测试集诊断结果标签：
wbcd_test_labels<-wbcd[test_100,1]
# 训练集诊断结果标签：
wbcd_train_labels<-wbcd[train_w,1]
使用class包的knn()函数来实现本次训练和预测：
# 使用class包的knn()函数：
# 载入包，没有安装的使用 install.packages("class")进行安装：
library(class)
# 进行训练预测：
wbcd_test_pred<-knn(train = wbcd_train,test=wbcd_test,cl=wbcd_train_labels,k=21)
创建双向交叉表（gmodels包的CrossTable()函数）来评估模型的性能：
library(gmodels)
CrossTable(x=wbcd_test_labels,y=wbcd_test_pred,prop.chisq = F)
双向交叉表
上图左上角的格子表示真阴性(True Negative)，这里表示分类器结果和临床结果一致认为是良性的情况，100个预测中有54个真阴性结果。相反，右下角就是真阳性(True Positive)结果，有43个案例分类器和临床一致认为是恶性的。左下的3个是假阴性(False Negative)，预测为良性实际是恶性，这可能导致病人错过治疗，这是最糟糕的预测结果。右上角的是假阳性(False Positive)，预测是恶性实际是良心，会导致病人虚惊一场。
其他评估模型预测结果的方法如敏感性、特异性、ROC曲线及检验以后介绍。有兴趣的可以看看之前推送的#方法杂谈# ROC曲线含义及绘制。
更多原创精彩视频敬请关注生信杂谈:
网友评论