精华内容
下载资源
问答
  • k近邻法
    2020-08-07 19:06:54

    k 近邻法

    k近邻算法

    k近邻算法:对于新的输入实例,在训练数据集中寻找最接近的k个实例,这k个实例的多数属于某个类,则将输入实例分到某个类中。

    k近邻法没有显式的学习过程

    k近邻模型

    k近邻法中,当训练集,距离度量,k值以及分类决策规则确定后,对于每个新的输入实例,其所属实例唯一确定

    距离度量

    我们可以选用Lp距离,其定义如下:
    L P ( x i , x j ) = ( Σ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_P(x_i,x_j)=(\Sigma_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}p} LP(xi,xj)=(Σl=1nxi(l)xj(l)p)p1
    p=1,为曼哈顿距离;p=2,为欧氏距离;p=∞,为各个坐标距离的最大值。

    k值的选择

    k值的选择对k近邻法的结果会产生很大影响,k值较小会使模型变得复杂,容易过拟合;较大会使模型变得简单,容易欠拟合;我们一般选择较小的k值,使用交叉验证的方法来选取最优的k值

    分类决策规则

    分类决策规则:多数表决规则

    对于给定的实例x,其最近邻的k个训练实例点构成集合N_k(x)。如果涵盖N_k(x)的区域类别是c_j,那么误分类率是
    1 k Σ x i ∈ N k ( x ) I ( y i ≠ c j ) = 1 − 1 k Σ x i ∈ N k ( x ) I ( y i = c j ) \frac{1}{k}\Sigma_{x_i\in N_k(x)}I(y_i\ne c_j) = 1-\frac{1}k \Sigma_{x_i\in N_k(x)}I(y_i= c_j) k1ΣxiNk(x)I(yi=cj)=1k1ΣxiNk(x)I(yi=cj)
    要使误分类率最小即经验风险最小,只需使
    Σ x i ∈ N k ( x ) I ( y i = c j ) \Sigma_{x_i\in N_k(x)}I(y_i= c_j) ΣxiNk(x)I(yi=cj)
    最大,因此多数表决规则等价于经验风险最小化

    k近邻算法的实现:kd树

    k近邻法最简单的实现方法使线性扫描,但这样时间复杂度为线性,使用树结构可以将时间复杂度降低至O(log n)

    kd树的构造

    构造kd树的算法:
    在这里插入图片描述

    kd树的搜索

    在这里插入图片描述

    更多相关内容
  • MATLAB实现K近邻法分类

    2020-09-30 22:30:16
    K近邻法分类待测样本点,模式识别实验内容之一,用MATLAB生成随机样本点作为样本集,用样本集将考试集分类。 K近邻法分类待测样本点,模式识别实验内容之一,用MATLAB生成随机样本点作为样本集,用样本集将考试集...
  • k近邻法(k-NN)是一种基本分类与回归方法。算法思想:给定一个数据集,对新的输入实例,在训练数据集中找到与其最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为哪个类。 k近邻的特殊情况是k=1的...
  • k近邻法matlab原始码无花果树 作者:Vlad I. Morariu电子邮件:morariu(at)umd(.edu)日期:2007-06-26修改:2014-10-18 FIGTree是一个提供C / C ++和MATLAB接口的库,用于加快Gauss变换的计算。 其作者是弗拉德...
  • K近邻法分类实验

    2017-05-31 11:36:47
    KNN实验 ,自带数据,对应商务智能(刘红岩)第48页第一题。 VS2010C# .NET4.0下编译通过
  • K近邻法是一种基本分类与回归方法。K近邻法的输入为实例的特征向量(特征空间的点),输出为实例的类别,可以取多类。 K近邻算法假设给定一个训练数据集,其训练数据集实例的类别已定,对新的输入实例,找出新实例K...
  • k 近邻法k-nearest-neighbor, KNN)是一种基本的分类和回归方法。现在只讨论其分类方面的应用,它不具备明显的学习过程,实际上是利用已知的训练数据集对输入特征向量空间进行划分,并作为其分类的“模型”。 其中...
  • 基本概念 最近邻法对于未知样本 x 比较 x 与 N 个已知类别的样本之间的欧式距离并决策 x 与 距离它最近的样本同类 K 近邻法取未知样本 x 的 k 个近邻看这 k 个近邻中多数属于哪一类就把 x 归为哪一 类 K 取奇数为了...
  • k近邻法(k-nearest neighbor,k-NN)是一种基本分类与回归方法。 输入:实例的特征向量,对应于特征空间的点 输出:实例的类别,可以取多类 假设:给定一个训练数据集,其中的实例类别已定。 分类:对新的实例,...
  • 基于自适应模糊k近邻法的破产预测模型
  • 最近邻法语k近邻法的例子,基于matlab平台,有助于初学者学习。
  • 将两类不可分样本剪辑成可分样本
  • 模式识别,fisher判别法,近邻法,k近邻法matlab例程
  • k近邻法算法与模型

    千次阅读 2021-09-21 14:33:20
    kkk近邻法k−nearest neighbor,k−NNk-nearest \ neighbor,k-NNk−nearest neighbor,k−NN)是一种基本分类与回归方法。 输入:实例的特征向量,对应于特征空间的点; 输出:实例的类别,可以取多类...

    k k k近邻法介绍与算法

    参考文献:【KNN算法原理以及代码实现】【KNN算法原理及实现】【python 实现KNN算法】

    1. 综述

    k k k近邻法( k − n e a r e s t   n e i g h b o r , K N N k-nearest \ neighbor,KNN knearest neighborKNN)是一种基本分类与回归方法。

    • 输入:实例的特征向量,对应于特征空间的点;
    • 输出:实例的类别,可以取多类。

    k k k近邻法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其 k k k最近邻的训练实例的类别,通过多数表决等方式进行预测。
    k k k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的”模型“。
    k近邻法的三个基本要素:

    1. k k k值的选择
    2. 距离度量
    3. 分类决策规则

    形象解释
    比如一个一定范围的平面随机分布着两种颜色的样本点,在这个平面内有个实例点不知道它是什么颜色,因此通过它周边的不同颜色的点分布情况进行推测,假设取 k = 3 k=3 k=3,意思是在离这个实例点最近的样本点中去前三个最近的, 然后看这三个当中那种类别占比大,就判断该实例点属于那个类别的,当 k = 5 k=5 k=5的时候也一样这样判断,因此 k k k的取值很关键,通常不会超过20。当然,因为每个样本有多个特征,因此实际工作中,这个平面就是三维甚至是多维的,道理是一样的。
    在这里插入图片描述

    2. 算法

    k k k近邻算法的一大优点是简单、直观:
    给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k k k个实例,这 k k k实例的多数属于某个类,就把该输入实例分为这个类。

    2.1 标准解释

    输入:训练数据集
    T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } (1) T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \tag 1 T={(x1,y1),(x2,y2),...,(xN,yN)}(1)

    其中, x i ∈ χ ⊆ R n x_i \in \chi \subseteq R^n xiχRn为实例的特征向量, y i ∈ γ = { c 1 , c 2 , . . . , c K } y_i \in \gamma = \{c_1,c_2,...,c_K\} yiγ={c1,c2,...,cK}为实例的类别, i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N;实例特征向量 x x x

    输出:实例 x x x所属的类 y y y

    1. 根据给定的距离度量,在训练集 T T T中找出与 x x x最近邻的 k k k个点,涵盖这 k k k个点的 x x x的领域记作 N k ( x ) N_k(x) Nk(x)
    2. N k ( x ) N_k(x) Nk(x)中根据分类决策规则(如多数表决)决定 x x x的类别 y y y
      y = arg ⁡   max ⁡ c j ∑ x i ∈ N k ( x ) I ( y i = c j ) , i = 1 , 2 , . . . , N ; j = 1 , 2 , . . . , K (2) y=\arg \ \max_{c_j} \sum_{x_i \in N_k(x)} I(y_i=c_j),i=1,2,...,N;j=1,2,...,K \tag 2 y=arg cjmaxxiNk(x)I(yi=cj),i=1,2,...,N;j=1,2,...,K(2)

    ( 2 ) (2) (2)中, I I I为指示函数,即当 y i = c j y_i=c_j yi=cj I I I为1,否则 I I I为0。
    特殊情况
    k = 1 k=1 k=1的情形,称为最近邻算法。对于输入的实例点(特征向量) x x x,最近邻法将训练数据集中与 x x x最近邻的类作为 x x x的类。

    2.2 形象解释

    在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前 K K K个数据,则该测试数据对应的类别就是 K K K个数据中出现次数最多的那个分类,其算法的描述为:

    1. 计算测试数据与各个训练数据之间的距离;
    2. 按照距离的递增关系进行排序;
    3. 选取距离最小的 K K K个点;
    4. 确定前 K K K个点所在类别的出现频率;
    5. 返回前 K K K个点中出现频率最高的类别作为测试数据的预测分类。

    2.3 优缺点以及改进

    优缺点

    1. 简单,易于理解,是一个天然的多分类器;
    2. 不需要庞大的样本数据也可以完成一个简单的分类;
    3. 不需要训练和求解参数(既是优点也是缺点);
    4. 数据量大的时候,计算量也非常大(样本多,特征多);
    5. 不平衡样本处理能力差;
    6. 并没有学习和优化的过程,严格来说不算是机器学习。

    改进
    进行加权平均,离得近的样本给予更大的权重离得远的样本使其权重变小

    3. 模型

    k k k近邻法中,当训练集、距离度量、 k k k值及分类决策规则(如多数表决)确定后,对于任何一个新的输入实例,它所属的类唯一地确定。

    3.1 距离度量

    特征空间中两个实例点的距离是两个实例点相似程度的反映。 k k k近邻模型的特征空间一般是 n n n维实数向量空间 R n R^n Rn。使用的距离欧氏距离,也可以是更一般的 L p L_p Lp距离( L p L_p Lp distance)或(Minkowski distance)。
    设特征空间 χ \chi χ n n n维实数向量空间 R n R^n Rn x i , x j ∈ χ , x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) T x_i,x_j \in \chi,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T xi,xjχ,xi=(xi(1),xi(2),...,xi(n))T x j = ( x j ( 1 ) , x j ( 2 ) , . . . , x j ( n ) ) T x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T xj=(xj(1),xj(2),...,xj(n))T x i , x j x_i,x_j xi,xj L p L_p Lp距离定义为:
    L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p (3) L_p(x_i,x_j)=(\sum_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}} \tag 3 Lp(xi,xj)=(l=1nxi(l)xj(l)p)p1(3)
    这里 p ≥ 1 p \geq 1 p1
    p = 2 p=2 p=2时,称为欧氏距离(Euclidean distance),即:
    L 2 ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 (4) L_2(x_i,x_j)=(\sum_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}} \tag 4 L2(xi,xj)=(l=1nxi(l)xj(l)2)21(4)
    p = 1 p=1 p=1时,称为曼哈顿距离(Manhattan distance),即:
    L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ (5) L_1(x_i,x_j)=\sum_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}| \tag 5 L1(xi,xj)=l=1nxi(l)xj(l)(5)
    p = ∞ p=\infty p=时,它是各个坐标距离的最大值,即:
    L ∞ ( x i , x j ) = max ⁡ l ∣ x i ( l ) − x j ( l ) ∣ (6) L_{\infty}(x_i,x_j)=\max_{l}|x_i^{(l)}-x_j^{(l)}| \tag 6 L(xi,xj)=lmaxxi(l)xj(l)(6)
    p p p取不同值时,二维空间中,与原点的 L p L_p Lp距离为1( L p = 1 L_p=1 Lp=1)的点的图形。

    例题
    已知二维空间的3个点 x 1 = ( 1 , 1 ) T x_1=(1,1)^T x1=(1,1)T x 2 = ( 5 , 1 ) T x_2=(5,1)^T x2=(5,1)T x 3 = ( 4 , 4 ) T x_3=(4,4)^T x3=(4,4)T,试求在 p p p取不同值时, L p L_p Lp距离下 x 1 x_1 x1的最近邻点。

    因为 x 1 x_1 x1 x 2 x_2 x2只有第一维的值不同,所以无论 p p p取什么值, L p ( x 1 , x 2 ) = 4 L_p(x_1,x_2)=4 Lp(x1,x2)=4。而
    L 1 ( x 1 , x 3 ) = 6 , L 2 ( x 1 , x 3 ) = 4.24 , L 3 ( x 1 , x 3 ) = 3.78 , L 4 ( x 1 , x 3 ) = 3.57 L_1(x_1,x_3)=6,L_2(x_1,x_3)=4.24,L_3(x_1,x_3)=3.78,L_4(x_1,x_3)=3.57 L1(x1,x3)=6,L2(x1,x3)=4.24,L3(x1,x3)=3.78,L4(x1,x3)=3.57
    于是得到: p p p等于1或2时, x 2 x_2 x2 x 1 x_1 x1的最近邻点; p p p大于等于3时, x 3 x_3 x3 x 1 x_1 x1的最近邻点。

    3.2 k k k值的选择

    • k k k值过小,相当于用较小的领域中的训练实例进行预测,”学习“的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用。但缺点是”学习“的估计误差会增大,预测结果会对近邻的实例点非常敏感。如果邻近的实例恰好是噪声,预测就会出错。( k k k值得减小就意味着整体模型变得复杂,容易发生过拟合)。
    • k k k值过大,相当于用较大的领域中的训练实例进行预测,可以减少估计误差,但是缺点是学习的近似误差会增大。这时与输入实例较远的训练实例也会对预测起作用,使预测发生错误。( k k k增大,模型会比较简单)。
    • 通常采用交叉验证法来选取最优的 k k k

    3.3 分类决策规则

    k k k近邻法中的分类决策规则往往是多数表决,即由输入实例的 k k k个邻近的训练实例中的多数表决决定输入实例的类。
    多数表决(majority voting rule)有如下解释:如果分类的损失函数为0-1损失函数,分类函数为:
    f :   R n → { c 1 , c 2 , . . . , c K } (7) f: \ R^n \rightarrow \{c_1,c_2,...,c_K\} \tag 7 f: Rn{c1,c2,...,cK}(7)
    那么误分类的概率是:
    P ( Y ≠ f ( X ) ) = 1 − P ( Y = f ( X ) ) (8) P(Y \not= f(X))=1- P(Y=f(X)) \tag 8 P(Y=f(X))=1P(Y=f(X))(8)
    对于给定的实例 x ∈ χ x \in \chi xχ,其最近邻的 k k k个训练实例点构成集合 N k ( x ) N_k(x) Nk(x)。如果涵盖 N k ( x ) N_k(x) Nk(x)的区域的类别是 c j c_j cj,那么误分类率是:
    1 k ∑ x i ∈ N k ( x ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N k ( x ) I ( y i = c j ) (9) \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i \not= c_j)=1- \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i=c_j) \tag 9 k1xiNk(x)I(yi=cj)=1k1xiNk(x)I(yi=cj)(9)
    要使误分类最小即经验风险最小,就要使 ∑ x i ∈ N k ( x ) I ( y i = c j ) \sum_{x_i \in N_k(x)} I(y_i=c_j) xiNk(x)I(yi=cj)最大,所以多数表决规则等价于经验风险最小化。

    4. 基于鸢尾花数据集的KNN分类分析

    4.1 简介

    鸢尾花数据集包括鸢尾花的测量数据(特征属性)以及其所属的类别。
    测量数据特征包括: 萼片长度、萼片宽度、花瓣长度、花瓣宽度。
    所属类别有三类: Iris SetosaIris VersicolourIris Virginica ,用数字0,1,2表示。

    4.2 导包

    import numpy as np
    from sklearn import datasets
    from sklearn.neighbors import KNeighborsClassifier
    from sklearn.model_selection import train_test_split
    

    4.3 导入鸢尾花数据

    iris = datasets.load_iris()
    print('数据量',iris.data.shape)
    

    4.4 拆分数据

    拆分属性数据

    iris_X = iris.data
    

    拆分类别数据

    iris_Y = iris.target
    

    拆分数据集为训练集和测试集
    方法一:使用python的train_test_split库进行数据集拆分

    iris_X_train , iris_X_test, iris_Y_train ,iris_Y_test = train_test_split(iris_X, iris_Y, test_size=0.2,random_state=0)
    

    使用help(train_test_split)查看详细用法

    方法二:随机选择部分数据(20%)作为测试集

    np.random.seed(0)
    # permutation随机生成0-150的系列
    indices = np.random.permutation(len(iris_Y))
    iris_X_train = iris_X[indices[:-30]]
    iris_Y_train = iris_Y[indices[:-30]]
    iris_X_test = iris_X[indices[-30:]]
    iris_Y_test = iris_Y[indices[-30:]]
    

    4.5 分类器的初始化

    knn = KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
     metric_params=None, n_jobs=1, n_neighbors=5, p=2,
     weights='uniform')
    

    参数介绍:

    • n_neighbors=5,就是KNN中的k,默认为5。
    • weights=‘uniform’,是距离计算中使用的权重,默认为uniform 是等权加权,也可以选distance是按照距离的倒数进行加权,也可以自己设置其他加权方式。(给距离增加权重,如果越近的距离权重越高,能在一定程度上避免样本分布不平均的问题)
    • metric=‘minkowski’p=2,表示采用的是欧氏距离的计算。
    • algorithm=‘auto’,是分类时采取的算法,有brutekd_treeball_tree,三种默认按照数据特征从这三种中选择最合适的。其中kd-tree基于欧氏距离的特性可以快速处理20维以内的数据集,ball_tree基于更一般的距离特性,适合处理高维数据。
    • leaf_size=30,是kd_treeball_tree生成的树的树叶(二叉树中未分枝的节点)的大小。
    • n_job=1,是并行计算的线程数量,默认是1,输入-1则设为CPU的内核数。

    4.6 训练预测

    提供数据集进行训练

    knn.fit(iris_X_train,iris_Y_train)
    

    预测测试集数据鸢尾花类型

    predict_result = knn.predict(iris_X_test)
    print('预测结果',predict_result)
    

    计算预测的准确率

    print('预测准确率',knn.score(iris_X_test, iris_Y_test))
    

    4.7 训练结果

    数据量 (150, 4)
    预测结果 [2 1 0 2 0 2 0 1 1 1 2 1 1 1 2 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0]
    预测准确率 0.9666666666666667
    

    5. 基于欧式距离的KNN算法及代码分析

    5.1 自定义数据及算法

    import numpy as np
    import operator
    import matplotlib.pyplot as plt
    
    def kNN(inX, dataSet, labels, k):
        '''
        kNN算法
        :param inX: 需要分类的数据
        :param dataSet: 样本数据集
        :param labels: 样本数据的标签
        :param k: 需要取出的前k个
        :return: 最有可能的分类
        '''
        # 获取样本数据的个数
        dataSetSize = dataSet.shape[0]
        # np.tile函数将待分类的数据inX"广播"成和样本数据dataSet一样的形状
        # 获取待分类数据inX与样本数据集中的每个数据之间的差
        diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
        # 平方
        sqDiffMat = diffMat**2
        # 按行累加
        sqDistances = sqDiffMat.sum(axis=1)
        # 开方,得出距离(欧氏距离)
        distances = sqDistances**0.5
        # 从小到大排序,得到的是数据的index
        sortedDistIndicies = distances.argsort()
        classCount={}
        # 取出前k个距离最小的
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            # 累计距离出现的次数,并做成字典
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        # 将字典按值的大小排序,大的在前
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        # 返回最有可能的预测值
        return sortedClassCount[0][0]
        
    def createDataSet():
        group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        labels = ['A','A','B','B']
        return group, labels
     
    if __name__ == '__main__':
        group, labels = createDataSet()
        predict = kNN([0.1,0.1], group, labels, 3)
        print(predict) # 预测结果为B
    

    5.2 改进约会网站的配对效果

    数据集介绍
    总共1000条,包含三个特征

    • 每年获得的飞行常客里程数;
    • 玩视频游戏所耗时间百分比;
    • 每周消费的冰淇淋公升数;

    标签类型为:

    • 1代表“不喜欢的人”
    • 2代表“魅力一般的人”
    • 3代表“极具魅力的人”

    代码

    import numpy as np
    import pandas as pd
    import operator
    import matplotlib.pyplot as plt
    
    def file_Matrix(filename):
        '''
        将源数据规整为所需要的数据形状
        :param filename: 源数据
        :return: returnMat:规整好的数据;classLabelVector:数据类标签
        '''
        data = pd.read_csv(filename, sep='\t').as_matrix()
        returnMat = data[:,0:3]
        classLabelVector = data[:,-1]
        return returnMat, classLabelVector
     
    def autoNorm(dataSet):
        '''
        数据归一化
        :param dataSet:
        :return:
        '''
        # 每列的最小值
        minVals = dataSet.min(0)
        # 每列的最大值
        maxVals = dataSet.max(0)
        ranges = maxVals - minVals
        # normDataSet = np.zeros(np.shape(dataSet))
        m = dataSet.shape[0]
        # np.tile(minVals,(m,1))的意思是将一行数据广播成m行
        normDataSet = (dataSet - np.tile(minVals, (m,1))) / np.tile(ranges, (m,1))
        # print(normDataSet)
        return normDataSet, ranges, minVals
     
    def kNN(inX, dataSet, labels, k):
        '''
        kNN算法
        :param inX: 需要分类的数据
        :param dataSet: 样本数据集
        :param labels: 样本数据的标签
        :param k: 需要取出的前k个
        :return: 最有可能的分类
        '''
        # 获取样本数据的个数
        dataSetSize = dataSet.shape[0]
        # np.tile函数将待分类的数据inX“广播”成和样本数据dataSet一样的形状
        # 获取待分类数据inX与样本数据集中的每个数据之间的差
        diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
        # 平方
        sqDiffMat = diffMat**2
        # 按行累加
        sqDistances = sqDiffMat.sum(axis=1)
        # 开方,得出距离(欧氏距离)
        distances = sqDistances**0.5
        # 从小到大排序,得到的是数据的index
        sortedDistIndicies = distances.argsort()
        classCount={}
        # 取出前k个距离最小的
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            # 累计距离出现的次数,并做成字典
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        # 将字典按值的大小排序,大的在前
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        # 返回最有可能的预测值
        return sortedClassCount[0][0]
     
    def datingClassTest():
        hoRatio = 0.10      #hold out 10%
        datingDataMat,datingLabels = file_Matrix('datingTestSet2.txt')       #load data setfrom file
        normMat, ranges, minVals = autoNorm(datingDataMat)
        # print(normMat)
        m = normMat.shape[0]
        numTestVecs = int(m * hoRatio)
        errorCount = 0.0
        for i in range(numTestVecs):
            classifierResult = kNN(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],4)
            print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
            if (classifierResult != datingLabels[i]): errorCount += 1.0
        print("测试集个数为%d ,分类错误的个数为%d"%(numTestVecs, errorCount))
        print("the total error rate is: %f" % (errorCount/float(numTestVecs)))
        print("accuracy: %f" % ((1-errorCount/float(numTestVecs))*100))
     
    if __name__ == '__main__':
        datingClassTest()
    

    训练结果

    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 3
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 1, the real answer is: 1
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 3, the real answer is: 3
    the classifier came back with: 2, the real answer is: 2
    the classifier came back with: 2, the real answer is: 1
    the classifier came back with: 1, the real answer is: 1
    测试集个数为99 ,分类错误的个数为4
    the total error rate is: 0.040404
    accuracy: 95.959596
    

    数据集下载地址

    链接:https://pan.baidu.com/s/1UErV8D4Hrw557tjj9fyjlQ
    提取码:o80d

    展开全文
  • K近邻思想物以类聚K近邻没有显式的训练过程(新样本与原来样本计算距离度量)距离度量(1)欧式距离两点之间直线(2)曼哈顿距离城市街区距(3)切比雪夫距离棋盘距离分类决策规则多数表决httpshttpshttps。......

    image-20220728192147156

    第三章 k近邻法

    1.同一标签的样本通常有很多相似的特征,所以同一类别的可能有扎堆现象,也就是物以类聚。

    2.每进来一个样本,我们查看它周围的样本是什么类别的,那它也有极大可能属于该类别。

    距离度量Distance measure

    首先令 $ x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right), x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \ldots, x_{j}^{(n)}\right) $

    欧式距离(也称二范数):

    L 2 ( x i , x j ) = ( ∑ i = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{i=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}} L2(xi,xj)=(i=1n xi(l)xj(l) 2)21

    曼哈顿距离(也称一范数):

    L 1 ( x i , x j ) = ∑ i = 1 n ∣ x i ( l ) − x j ( l ) ∣ L_{1}\left(x_{i}, x_{j}\right)=\sum_{i=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right| L1(xi,xj)=i=1n xi(l)xj(l)

    P范数:

    L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_{\mathrm{p}}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}} Lp(xi,xj)=(l=1n xi(l)xj(l) p)p1

    切比雪夫距离(类似于国际象棋的后)

    p = ∞ p=\infty p= 时, 它是各个坐标距离的最大值, 即

    L ∞ ( x i , x j ) = max ⁡ l ∣ x i ( l ) − x j ( l ) ∣ L_{\infty}\left(x_{i}, x_{j}\right)=\max _{l}\left|x_{i}^{(l)}-x_{j}^{(l)}\right| L(xi,xj)=maxl xi(l)xj(l)

    image-20220728192739172

    image-20220728192829362

    k值的选择

    k值的选择会对k近邻法的结果产生重大影响。
    如果选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差(approximation error)会减小,只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是“学习”的估计误差(estimation error)会增大,预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合。

    如果选择较大的k值,就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误。k值的增大就意味着整体的模型变得简单。

    如果k =N,那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类。这时,模型过于简单,完全忽略训练实例中的大量有用信息,是不可取的。

    在应用中,k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

    分类决策规则

    k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

    多数表决规则(majority voting rule)有如下解释:如果分类的损失函数为0-1损失函数.分类函数为:

    f : R n → { c 1 , c 2 , ⋯   , c K } f: \mathbf{R}^{n} \rightarrow\left\{c_{1}, c_{2}, \cdots, c_{K}\right\} f:Rn{c1,c2,,cK}

    那么误分类的概率是

    P ( Y ≠ f ( X ) ) = 1 − P ( Y = f ( X ) ) P(Y \neq f(X))=1-P(Y=f(X)) P(Y=f(X))=1P(Y=f(X))

    对给定的实例 $x \in \mathcal{X} $, 其最近邻的 k 个训练实例点构成集合 $ N_{k}(x) $ 。如果涵盖 $N_{k}(x) $ 的区域的类别是 c j c_{j} cj , 那么误分类率是

    1 k ∑ x i ∈ N k ( x ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N k ( x ) I ( y i = c j ) \frac{1}{k} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i} \neq c_{j}\right)=1-\frac{1}{k} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right) k1xiNk(x)I(yi=cj)=1k1xiNk(x)I(yi=cj)

    要使误分类率最小即经验风险最小, 就要使 $ \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right) $ 最大, 所以多数表决规则等价于经验风险最小化。

    注意: I ( x ) I\left(x\right) I(x)为指示函数,即x条件为真,则函数值为1,x条件为假,则函数值为0。

    总结Summarization

    1. K近邻思想:物以类聚

    2. K近邻没有显式的训练过程(新样本与原来样本计算距离度量)

    3. 距离度量:
      (1)欧式距离:两点之间直线

      (2)曼哈顿距离:城市街区距

      (3)切比雪夫距离:棋盘距离

    4. 分类决策规则:多数表决

    展开全文
  • 机器学习算法中,常见的十大算法之一,k 近邻法算法,资料是一个PDF文件,有原理,案例,解说。
  • K近邻法(KNN)

    2021-06-11 08:46:49
    K近邻法(k-nearest neighbor,k-NN) 1 K近邻定义 1、一句话定义:       给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该...

    更多机器学习方法总结请到我这个博客链接

    K近邻法(k-nearest neighbor,KNN)

    1 K近邻定义

    1、一句话定义
          给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。

    2、三要素:距离度量,k值的选取,分类决策规则的选取。

    1. 距离度量一般采用欧氏距离,也可以是其他距离(Lp距离)
    2. k值选取将会对结果产生巨大的影响。如果k值较小,整体模型变的复杂,容易发生过拟合;如果k值过大,不相关的点也对预测产生影响,导致预测精度较低。一般可以采用交叉验证进行k值得选取。
    3. 分类决策规则:往往是多数表决。

    2 k近邻的实现-kd树

          实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。最简单是的就是线性扫描,但对于高维数据不可取,因此采用特殊的存储结构kd树进行搜索。

    2.1 kd树的构建

    更多详情请见:kd树构建详解

          kd树是二叉树,和分治法思想一样,利用已有数据进行空间切分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
          需要注意的是,每一刀都要切在数据点上面。主要考虑切分域和切分点的选择(分别使用方差最大优先和中位优先)
    算法流程:
    kd树构造算法
    对于例子:构造一个平衡kd树。
    在这里插入图片描述
    结果如下:

    在这里插入图片描述在这里插入图片描述

    2.2 ball tree 和其他树类型介绍

          在kd tree 中,我们看到一个导致性能下降的最核心因素是因为kd树的平面是一个个的方形,求最近邻时使用的是圆形。方形平面跟圆形相交的可能性是极高的,如果方形的交汇点多的话,圆形和几个平面相交的可能性就变得更大。这样,凡是相交的平面,都需要进行检查,大大的降低运行效率。
    在这里插入图片描述
          为了解决这一个问题,ball tree抛弃了kd树画的方形,而建立球形,去掉棱角。简而言之,就是使用超球面而不是超矩形划分区域。
    在这里插入图片描述

    3 搜索kd树

          用目标数据在kd树中寻找最近邻时,最核心的两个部分是:

    1. 寻找近似点-寻找最近邻的叶子节点作为目标数据的近似最近点。

    2. 回溯-以目标数据和最近邻的近似点的距离沿树根部进行回溯和迭代。

    展开全文
  • K近邻法算法.txt

    2020-09-16 21:23:11
    K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:在特征空间中,如果一个样本附近的k个最近(即特征空间中最邻近)样本的大多数属于某一个...
  • k近邻法(KNN)原理小结1. k 近邻法算法2. k 近邻法模型2.1 k值的选择2.2 距离度量2.3 分类决策规则3. k 近邻法实现:kd(k-dimension)树3.1 构造kd树3.2 搜索kd树3.3 kd 树预测4. 代码示例5. 模型评价完整代码地址...
  • 机器学习分两大类,有监督学习(supervised learning)和无监督学习(unsupervised learning)。有监督学习又可分两类:分类(classification.)和回归(regression),分类的任务就是把一个样本划为某个已知类别,每个...
  • k近邻法(KNN)

    2019-11-05 19:10:27
    k近邻法(k-Nearest Neighbor,简称kNN)学习是一种常用的监督式学习方法。 给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。通常,在分类任务中可...
  • 最近邻法,k近邻法,及最小错误率分析,快速搜索算法,压缩紧邻法,基本原理,内容及应用
  • 机器学习算法之K近邻法-Python实现

    千次阅读 2021-03-03 15:42:27
    一、算法简介k近邻法(k-nearest neighbor,k-NN)是一种基本的分类方法,输入的是实例的特征向量,对应于特征空间的点,输出结果为实例的类别,可以取多类。对于训练集来说,每个实例的类别已定,当分类时,对于新的...
  • 通过利用matlab对IRIS数据集的K近邻法分类
  • K近邻法相关

    2018-05-20 21:20:04
    K近邻法
  • 本文介绍k近邻法(k-nearest neighbor, k-NN) 0x01、k近邻法简介 k近邻法是基本且简单的分类与回归方法。k近邻法的基本做法是:对给定的训练实例点和输入实例点,首先确定输入实例点的k个最近邻训练实例点,...
  • k近邻法matlab原始码SNFpy 该软件包提供了Python的相似性网络融合(SNF)实现,该技术可将多个数据源组合到一个表示样本关系的图形中。 目录 如果您知道要去哪里,请随时跳转: 要求和安装 此软件包需要Python 3.5或...
  • k近邻法

    2017-08-25 21:14:40
    本文介绍KNN算法,包括距离度量,k值的选择,及分类决策规则。kd树待补充。
  • K近邻法

    2018-12-15 21:44:00
    k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法(此处讨论的是分类问题的K近邻算法)。 k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”,不具有显式的学习过程。 k近邻...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,041
精华内容 6,016
关键字:

k近邻法