数据分析与挖掘 - R语言:KNN算法

一个简单的例子!
环境:CentOS6.5
Hadoop集群、Hive、R、RHive,具体安装及调试方法见博客内文档。

KNN算法步骤:
需对所有样本点(已知分类+未知分类)进行归一化处理。然后,对未知分类的数据集中的每个样本点依次执行以下操作:
1、计算已知类别数据集中的点与当前点(未知分类)的距离。
2、按照距离递增排序
3、选取与当前距离最小的k个点
4、确定前k个点所在类别的出现频率
5、返回前k个点出现频率最高的类别作为当前点的预测类别

编写R脚本:

#!/usr/bin/Rscript
#1、对iris进行归一化处理
iris_s <- data.frame(scale(iris[, 1:4]))
iris_s <- cbind(iris_s, iris[, 5])
names(iris_s)[5] = "Species" #2、对iris数据集随机选择其中的100条记录作为已知分类的样本集
sample.list <- sample(1:150, size = 100)
iris.known <- iris_s[sample.list, ] #3、剩余50条记录作为未知分类的样本集(测试集)
iris.unknown <- iris_s[-sample.list, ] #4、对测试集中的每一个样本,计算其与已知样本的距离,因为已经归一化,此处直接使用欧氏距离
length.known <- nrow(iris.known)
length.unknown <- nrow(iris.unknown) #5、计算
for (i in 1:length.unknown) {
dis_to_known <- data.frame(dis = rep(0, length.known))
for (j in 1:length.known) {
dis_to_known[j, 1] <- dist(rbind(iris.unknown[i, 1:4], iris.known[j,1:4]), method = "euclidean")
dis_to_known[j, 2] <- iris.known[j, 5]
names(dis_to_known)[2] = "Species"
} dis_to_known <- dis_to_known[order(dis_to_known$dis), ] k <- 5
type_freq <- as.data.frame(table(dis_to_known[1:k, ]$Species))
type_freq <- type_freq[order(-type_freq$Freq), ]
iris.unknown[i, 6] <- type_freq[1, 1]
} names(iris.unknown)[6] = "Species.pre" #7、输出分类结果
iris.unknown[, 5:6]

输出结果:略,结果集中,Species为样本实际分类,Species.pre为Knn算法的分类,正确率达90%以上。

KNN是有监督的学习算法,其特点有:
1、精度高,对异常值不敏感
2、只能处理数值型属性
3、计算复杂度高(如已知分类的样本数为n,那么对每个未知分类点要计算n个距离)

KNN算法存在的问题:
1、k值的确定是个难题。
2、如果距离最近的k个已知分类样本中,频数最高的类型有多个(频数相同),如何选择对未知样本的分类?目前看是随机的。
3、如果有n个未知类型样本,m个已知类型样本,则需要计算n*m个距离,计算量较大,且需存储全部数据集合,空间复杂度也较大。
4、能否把预测的样本分类加入到已知类别集合中,对剩余的未知类型样本进行分类?
5、归一化放在所有处理的最前面,这样需要知道全部的样本集合(已知分类+未知分类)来构建分类器,而实际上未知分类的样本并不一定能事先获得,这样如何进行归一化处理?

上一篇:C# 通过WebService方式 IIS发布网站 上传文件到服务器[转]


下一篇:Html5的一些引擎使用感触