分类算法之knn
knn概念
本文从机器学习中的分类算法knn开始讲起，knn即k邻近算法，该算法就是将未分类的样本归为最相似的已分类样本中，而且该算法简单有效，对数据的分布不作任何要求。其核心思想是：通过计算未分类样本到已分类样本的距离，根据最近的k个距离，使用投票法，将未分类样本进行分类。
模型数据条件
已知该算法是基于距离来衡量邻近概念，这就对数据的要求比较严格，具体满足如下：
1）训练集和测试集中不能含有缺失值，如果原始数据含有缺失值，可以考虑删除缺失记录或是进行多重插补，具体可以查看公众号中的《缺失值处理方法》一文；
2）对于名义变量（如姓名，学历等）需要进行哑变量处理，如性别处理为0,1，学历初中、高中、大学处理为两个哑变量，分别用0,1表示；
3）变量之间如存在较大的量纲，如一个变量的范围是1~10，另一个变量的范围是-1000~1000，需考虑标准化处理。
k值选取
knn为k邻近算法，需要解决的一个问题是选择合适的k值，k值过小或过大都会影响模型的准确性，一般考虑将k值设为3~10，或是将k值设为训练集样本数量的平方根。还有一种选择k值的方法是结合训练集和测试集，循环k值，直到挑选出使测试集的误差率最小的k值，具体可参见下文的R脚本。
算法函数讲解
关于K最邻近算法的实现可以使用class包中的knn()函数。knn()函数的语法和参数如下：
knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)
train指定训练样本集；
test指定测试样本集；
cl指定训练样本集中分类变量；
k指定最邻近的k个已知分类样本点，默认为1；
l指定待判样本点属于某类的最少已知分类样本数，默认为0；
prob设为TRUE时，可以得到待判样本点属于某类的概率，默认为FALSE；
use.all控制节点的处理办法，即如果有多个第K近的点与待判样本点的距离相等，默认情况下将这些点都纳入判别样本点，当该参数设为FALSE时，则随机挑选一个样本点作为第K近的判别点。
案例应用
本案例使用UCI机器学习数据仓库的“威斯康星乳腺癌诊断”数据集，数据可从http://archive.ics.uci.edu/ml下载，该数据集包含569个样本和32个变量，具体数据可参见后文链接。
#数据读取
cancer <- read.table(file = file.choose(), header = FALSE,
sep = ',')
#编辑变量名
names(cancer) <- c('ID','Diagnosis','radius_mean','radius_sd','radius_worst',
'texture_mean','texture_sd','texture_worst',
'perimeter_mean','perimeter_sd','perimeter_worst',
'area_mean','area_sd','area_worst',
'smoothness_mean','smoothness_sd','smoothness_worst',
'compactness_mean','compactness_sd','compactness_worst',
'concavity_mean','concavity_sd','concavity_worst',
'concavepoints_mean','concavepoints_sd','concavepoints_worst',
'symmetry_mean','symmetry_sd','symmetry_worst',
'fractaldimension_mean','fractaldimension_sd','fractaldimension_worst')
#数据探索
dim(cancer)
[1] 569 32
发现数据集中含有569个样本和32个变量
str(cancer)
summary(cancer)
从汇总情况来看，数据集中不含有缺失值，除Diagnosis变量外，其余变量均为数值型变量，ID变量为编号，没有任何意义，故在建模过程中将删除该变量。发现各个变量间存在明显的量纲大小，需要进一步对原始数据进行标准化。
#构建标准化函数
standard <- function(x) {
(x-min(x))/(max(x)-min(x))
}
#将该函数应用到数据框cancer中的每一列（除Diagnosis变量）
cancer_standard <- sapply(X = cancer[,3:32], FUN = standard)
summary(cancer_standard)
此时数据框中的所有变量值范围落在0~1之间
#将数据框cancer中的Diagnosis变量合并到cancer_standard中
cancer_standard <- as.data.frame(cbind(cancer$Diagnosis,cancer_standard))
names(cancer_standard)[1] <- 'Diagnosis'
#构建训练集、测试集和验证集
set.seed(1234)
index <- sample(x = 1:3,size = nrow(cancer_standard), replace = TRUE, prob = c(0.7,0.2,0.1))
train <- cancer_standard[index == 1,]
test <- cancer_standard[index == 2,]
valid <- cancer_standard[index == 3,]
#查看三类样本的容量
dim(train);dim(test);dim(valid)
[1] 392 31
[1] 112 31
[1] 65 31
#构建模型，以循环的方式选择knn算法中的k值
library(class)
for (i in 1:round(sqrt(dim(train)[1]))){
model <- knn(train = train[,-1], test = test[,-1], cl = train$Diagnosis, k = i)
Freq <- table(test[,1], model)
print(1-sum(diag(Freq))/sum(Freq))
}
#发现k=16时，对应的分类误差率最低，为0.027，故取k=16
fit <- knn(train = train[,-1], test = valid[,-1], cl = train$Diagnosis, k = 16)
#查看模型预测与实际类别的列联表
Freq <- table(valid[,1], fit)
Freq
#预判正确率
sum(diag(Freq))/sum(Freq)
[1] 0.9692308
可见模型的正确分类率达到96%以上。
数据集和脚本下载
文中涉及到的数据集和脚本可到下方链接中下载：
http://yunpan.cn/c3kTUwpjMeagD 访问密码 56d1
参考资料
机器学习与R语言