机器学习 | KNN(K – 最近邻算法)

  • A+
所属分类:头条
摘要

(optional)7. KNN的缺点KNN可能需要大量的内存或空间来存储所有的数据,但只有在需要预测时才会执行计算(或学习). 你还可以…

广告也精彩

K Nearest Neighbors(KNN)

KNN is a simple algorithm that stores all available instances and classifies new instances based on a distance metric to the available ones.

KNN is also called

–Case-based learning

–Memory-based learning

–Lazy learning

–Instance-based learning

1.KNN 的时间复杂度和空间复杂度都是O(n).

2.KNN例子:根据词频表进行文本分类。

3.Bayes Error:binary classifier. 因为二分类,计算得到两种结果的条件概率,采用概率高的,则犯错误的风险就是另一个条件的概率。

r(x)=min

Bayes error is the lower bound of probability of classification error.

    4. KNN Algorithm

    •Training process:

    –Store the available training instances

    •Predicting process:

    –Find the K training instances that are closest to the query instance

    –For classification, return the most frequent class label among those K instances

    –For regression, return the average of those K instances

    5.Performance Measure

    •Time and space complexity is both O(K)

    •KNN is conceptually simple, yet able to solve complex problems

    •Can work with relatively little information

    •Learning is extremely simple (no learning at all!)

    •Does not explicitly compute a generalization or category prototypes

    •KNN is close to optimal!

    Asymptotically, the error rate of 1-nearest-neighbor classification is less than twice the Bayes error (error rate of classifier knowing model that generated data)

    6.KNN三个细节要点

    KNN Is an Instance-based Learning. What determines an instance-based learning?

    (1)距离A distance metric: 常用欧氏距离,也包括其他距离。

    机器学习 | KNN(K – 最近邻算法)

    (2)neighbor数量K:How many neighbors to look at?

    机器学习 | KNN(K – 最近邻算法)

    用词频为文本分类,已知一个文本的词频,该给什么标签?用k=5的KNN算法,3/5认为是Sports,2/5认为是Science,采用概率最高的标签:Sports。

    • In practice, using a value of K somewhere between 5 and 10 gives good results for most low-dimensional data sets

    • A good K can also be chosen by using cross-validation

    低纬数据用5-10即可,或者用cross-validation确定k。

    (3)A weighing function (optional)

    7. KNN的缺点

    KNN可能需要大量的内存或空间来存储所有的数据,但只有在需要预测时才会执行计算(或学习)。 你还可以随时更新和管理你的训练集,以保持预测的准确性。

    距离或紧密度的概念可能会在高维环境(大量输入变量)下崩溃,这会对算法造成负面影响。这类事件被称为维度诅咒。它也暗示了你应该只使用那些与预测输出变量最相关的输入变量。

    在选择使用 KNN 之前,你需要考虑的事情:

    • KNN 的计算成本很高。

    • 变量应该先标准化(normalized),不然会被更高范围的变量偏倚。

    • 在使用KNN之前,要在野值去除和噪音去除等前期处理多花功夫。

    8.实例

    knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all= TRUE)

    train 指定训练样本集;

    test 指定测试样本集;

    cl 指定训练样本集中分类变量;

    指定最邻近的k个已知分类样本点,默认为1;

    指定待判样本点属于某类的最少已知分类样本数,默认为0;

    prob 设为TRUE时,可以得到待判样本点属于某类的概率,默认为FALSE;

    use.all 控制节点的处理办法,即如果有多个第K近的点与待判样本点的距离相等,默认情况下将这些点都纳入判别样本点,当该参数设为FALSE时,则随机挑选一个样本点作为第K近的判别点。

    #######

    # KNN 可以直接进行多分类问题。

    #引入数据,就是换个短名字

    x=iris

    #探索数据:数据结构分析

    dim(x);head(x)

    str(x)

    table(x$Species)

    round(prop.table(table(x$Species))*100,digits=1 )

    summary(x)

    summary(x[c("Petal.Width","Sepal.Width")])

    #探索数据:图形

    library(ggplot2)

    ggplot(x,aes(Sepal.Length, Sepal.Width,color=Species))+geom_point()

    ggplot(x,aes(Petal.Length, Petal.Width,color=Species))+geom_point()

    #引入包

    library(class)

    #数据归一化处理:标准化方法,主要有两种,即Z标准化或0-1标准化处理

    #本文用2做归一化函数,最大-最小化归一化

    normalize <- function(x){

      num <- x - min(x)

      span <- max(x) - min(x)

      return(num/span)

    }

    #标准化函数1(未使用)

    standard <- function(x) {

      (x-mean(x))/sd(x)

    }

    #1

    x_norm <- as.data.frame(lapply(x[,1:4], normalize))

    head(x_norm)

    summary(x_norm)

    #2

    #将该函数应用到数据框cancer中的每一列(除Diagnosis变量)

    # cancer_standard <- sapply(X = cancer[,3:32], FUN = standard)

    # summary(cancer_standard)

    #生成抽样序列

    set.seed(100)

    ind=sample(2,nrow(x_norm),replace=TRUE,prob=c(0.8,0.2));ind

    #取80%作为训练集,20为测试集

    x_train=x_norm[ind==1,];dim(x_train) #121

    x_test=x_norm[ind==2,];dim(x_test) #29 去掉标签

    #fitting model

    fit <-knn(train=x_train, test=x_test, cl=x[ind==1,]$Species, k=5)

    summary(fit)

    #模型评价:采用交叉联表

    table(fit, x[ind==2,]$Species)

    #

    机器学习 | KNN(K – 最近邻算法)

    # 问题:knn中的k怎么选择呢?遍历后用最优

    accs=c()

    for(i in 1:round(sqrt(nrow(x_train)))){

      fit <-knn(train=x_train, test=x_test, cl=x[ind==1,]$Species, k=i)

      Freq=table(fit, x[ind==2,]$Species)

      acc <- sum(diag(Freq))/sum(Freq)

      accs=c(accs, acc)

    }

    #可视化

    plot(1:round(sqrt(nrow(x_train))),accs,type = 'b', pch = 20, col= 'blue',

         main = 'k vs. accuracy',

         xlab = 'k', ylab = 'accuracy')

    #所以取7 8 10 11结果最好

    fit.best <-knn(train=x_train, test=x_test, cl=x[ind==1,]$Species, k=7)

    Freq=table(fit.best, x[ind==2,]$Species)

    #预判正确率

    sum(diag(Freq))/sum(Freq) #0.9310345

    #简单而易用的knn算法能够有93%的把握,给出分类信息。

    机器学习 | KNN(K – 最近邻算法)

    refer:

    人工智能之K近邻算法(KNN)

    • 微信
    • 扫一扫
    • weinxin
    • 微信公众号
    • 扫一扫
    • weinxin
    广告也精彩
    iPhone 配件
    高帮鞋
    羊绒茧型大衣
    女短靴
    广告也精彩

    发表评论

    :?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: