menu 李昊天的个人博客
KNN(K近邻)
29 浏览 | 2020-01-23 | 分类:机器学习 | 标签:算法,机器学习

百度百科

邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。

KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时,只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

优点

  1. 简单,易于理解,易于实现,无需估计参数,无需训练;
  2. 适合对稀有事件进行分类;
  3. 特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。

缺点

该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。

该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。

核心公式

实现

import numpy as np
from collections import  Counter
from math import sqrt

class KNNClass:
    ## 构造时传入K即比较周围的K个元素
    def __init__(self,k):
        self.k=k
        self._X_train=None
        self._Y_train=None
        
    ## 训练模型,传入特征与结果,要求其个数必须一样,我未加判断    
    def fit(self,X_train,Y_train):
        self._X_train=X_train
        self._Y_train=Y_train
        return self
    
    ## 传入要推断的模型(可以多个),返回推断的结果
    def predict(self,X_predict):
        ## 调用_predict方法,测试模型空间中的每一个
        y_predict=[self._predict(x) for x in X_predict]
        return y_predict

    def _predict(self,x):
        ## 计算传入的一个模型的结果
        ## 计算所有训练模型和传入模型的距离
        distances =[sqrt(np.sum((x_train - x)**2) )for x_train in self._X_train]
        ## 排序下标
        nearest = np.argsort(distances)
        ## 取前K个元素(距离最短)
        topK_y=[self._Y_train[i] for i in nearest[:self.k]]
        ## 统计最短的元素的各类个数
        votes = Counter(topK_y)
        ## 返回最多的那个为结果
        return votes.most_common(1)[0][0]

    def __repr__(self):
        return "KNN(k=%d)" %self.k
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!