• K-NN算法

    一、近邻算法(Nearest Neighbors)


    1、近邻算法的概念


    近邻算法(Nearest Neighbors)是一种典型的非参模型,与生成方法(generalizing method)不同的是,在近邻算法中,通过以实例的形式存储所有的训练样本,假设有m个训练样本:

    此时需要存储这m个训练样本,因此,近邻算法也称为基于实例的模型。

        对于一个需要预测的样本,通过与存储好的训练样本比较,以较为相似的样本的标签作为近邻算法的预测结果。


    2、近邻算法的分类


    在近邻算法中,根据处理的问题的不同,可以分为:
    • 近邻分类算法
    • 近邻回归算法
    在本篇博文中,主要介绍近邻分类算法。
    注意:除了上述的监督式近邻算法,在近邻算法中,还有一类非监督的近邻算法。

    二、近邻分类算法


    1、近邻分类算法的概念


        在近邻分类算法中,对于预测的数据,将其与训练样本进行比较,找到最为相似的K个训练样本,并以这K个训练样本中出现最多的标签作为最终的预测标签。
        在近邻分类算法中,最主要的是K-近邻算法。


    2、KNN算法概述


        K-NN算法是最简单的分类算法,主要的思想是计算待分类样本与训练样本之间的差异性,并将差异按照由小到大排序,选出前面K个差异最小的类别,并统计在K个中类别出现次数最多的类别为最相似的类,最终将待分类样本分到最相似的训练样本的类中。与投票(Vote)的机制类似。


    3、样本差异性


        比较常用的差异性计算方法为欧式距离。欧式距离:样本与样本之间的欧式距离为:

    4、KNN算法的流程

    • 求预测样本与训练样本之间的相似性
    • 依据相似性排序
    • 选择前K个最为相似的样本对应的类别
    • 得到预测的分类结果

    三、K-近邻算法实现


    1、Python实现



       以手写字体MNIST的识别为例,对于测试集中的每一个样本预测其类别,对于手写字体,如下图所示:

    k_nn.py

    # coding:UTF-8
    
    import cPickle as pickle
    import gzip
    import numpy as np
    
    def load_data(data_file):
    	with gzip.open(data_file, 'rb') as f:
    		train_set, valid_set, test_set = pickle.load(f)
    	return train_set[0], train_set[1], test_set[0], test_set[1]
    
    def cal_distance(x, y):
    	return ((x - y) * (x - y).T)[0, 0]
    
    def get_prediction(train_y, result):
    	result_dict = {}
    	for i in xrange(len(result)):
    		if train_y[result[i]] not in result_dict:
    			result_dict[train_y[result[i]]] = 1
    		else:
    			result_dict[train_y[result[i]]] += 1
    	predict = sorted(result_dict.items(), key=lambda d: d[1])
    	return predict[0][0]
    
    def k_nn(train_data, train_y, test_data, k):
    	# print test_data
    	m = np.shape(test_data)[0]  # 需要计算的样本的个数
    	m_train = np.shape(train_data)[0]
    	predict = []
    	
    	for i in xrange(m):
    		# 对每一个需要计算的样本计算其与所有的训练数据之间的距离
    		distance_dict = {}
    		for i_train in xrange(m_train):
    			distance_dict[i_train] = cal_distance(train_data[i_train, :], test_data[i, :])
    		# 对距离进行排序,得到最终的前k个作为最终的预测
    		distance_result = sorted(distance_dict.items(), key=lambda d: d[1])
    		# 取出前k个的结果作为最终的结果
    		result = []
    		count = 0
    		for x in distance_result:
    			if count >= k:
    				break
    			result.append(x[0])
    			count += 1
    		# 得到预测
    		predict.append(get_prediction(train_y, result))
    	return predict
    
    def get_correct_rate(result, test_y):
    	m = len(result)
    	
    	correct = 0.0
    	for i in xrange(m):
    		if result[i] == test_y[i]:
    			correct += 1
    	return correct / m	
    
    if __name__ == "__main__":
    	# 1、导入
    	print "---------- 1、load data ------------"
    	train_x, train_y, test_x, test_y = load_data("mnist.pkl.gz")
    	# 2、利用k_NN计算	
    	train_x = np.mat(train_x)
    	test_x = np.mat(test_x)
    	print "---------- 2、K-NN -------------"
    	result = k_nn(train_x, train_y, test_x[:10,:], 10)
    	print result
    	# 3、预测正确性
    	print "---------- 3、correct rate -------------"
    	print get_correct_rate(result, test_y)
    	
    	
    


    当取K=10时,对测试集中的10个数据样本的最终的预测准确性为:70%,预测值为:[7, 2, 1, 0, 9, 1, 9, 9, 8, 9],原始值为[7 2 1 0 4 1 4 9 5 9]

    2、Scikit-leanrn


    Scikit-learn库中对K-NN算法有很好的支持,核心程序为:

    clf = neighbors.KNeighborsClassifier(n_neighbors)
    clf.fit(X, y)


    四、K-NN算法中存在的问题及解决方


    1、计算复杂度的问题


           在K-NN算法中,每一个预测样本需要与所有的训练样本计算相似度,计算量比较大。比较常用的方法有K-D树,局部敏感哈希等等

    2、K-NN的均匀投票


           在上述的K-NN算法中,最终对标签的选择是通过投票的方式决定的,在投票的过程中,每一个训练样本的投票的权重是相等的,可以对每个训练样本的投票加权,以期望最相似的样本有更高的决策权。


    参考文献


    1、1.6. Nearest Neighbors点击打开链接

    对于本文有任何问题,欢迎邮件或者微博私信,具体联系方式见博客左侧。

    展开全文
  • 1-1 机器学习算法分类 一、基本分类: ①监督学习(Supervised learning) 数据集中的每个样本有相应的“正确答案”, 根据这些样本做出 预测, 分有两类: 回归问题和分类问题。 步骤1: 数据集的创建和...

    1-1 机器学习算法分类

    一、基本分类:

    ①监督学习(Supervised learning)

    数据集中的每个样本有相应的“正确答案”, 根据这些样本做出
    预测, 分有两类: 回归问题和分类问题。

    步骤1: 数据集的创建和分类
    步骤2: 训练
    步骤3: 验证
    步骤4: 使用

    ( 1) 回归问题举例
    例如: 预测房价, 根据样本集拟合出一条连续曲线。
    ( 2) 分类问题举例
    例如: 根据肿瘤特征判断良性还是恶性,得到的是结果是“良性”或者“恶性”, 是离散的。

    监督学习:从给定的训练数据集中学习出一个函数(模型参数), 当新的数据到来时,可以根据这个函数预测结果。监督学习的训练集要求包括输入输出,也可以说是特征和目标。训练集中的目标是由人标注的。
    PCA和很多deep learning算法都属于无监督学习

    ②无监督学习

    无监督学习:输入数据没有被标记,也没有确定的结果。样本数据类别未知, 需要根据样本间的相似性对样本集进行分类(聚类, clustering)试图使类内差距最小化,类间差距最大化。
    实际应用中, 不少情况下无法预先知道样本的标签,也就是说没有训练样本对应的类别,因而只能从原先没有样本标签的样本集开始学习分器设计

    有监督学习 无监督学习
    样本 必须要有训练集与测试样本。在训练集中找规律,而对测试样本使用这种规律。
    目标 方法是识别事物,识别的结果表现在给待识别数据加上了标签。 因此训练样本集必须由带标签的样本组成。

    ③半监督学习

    半监督学习: 即训练集同时包含有标记样本数据和未标记样本数据。

    ④强化学习

    实质是: make decisions问题,即自动进行决策,并且可以做连续决策。
    主要包含四个元素: agent, 环境状态, 行动, 奖励;
    强化学习的目标就是获得最多的累计奖励。

    小结:

    监督学习:
    In:有标签
    Out:有反馈
    目的:预测结果
    案例:学认字
    算法:分类(类别),回归(数字)

    无监督学习:
    In:无标签
    Out:无反馈
    目的:发现潜在结构
    案例:自动聚类
    算法:聚类,降维

    半监督学习:
    已知:训练样本Data和待分类的类别
    未知:训练样本有无标签均可
    应用:训练数据量过时,
    监督学习效果不能满足需求,因此用来增强效果。

    强化学习:
    In:决策流程及激励系统
    Out:一系列行动
    目的:长期利益最大化,回报函数(只会提示你是否在朝着目标方向前进的延迟反映)
    案例:学下棋
    算法:马尔科夫决策,动态规划

    2-1 KNN基本流程

    一、概念:

    KNN(K Near Neighbor):k个最近的邻居,即每个样本都可以用它最接近的k个邻居来代表。
    这里写图片描述
    最近邻 (k-Nearest Neighbors, KNN) 算法是一种分类算法, 1968年由 Cover和 Hart 提出, 应用场景有字符识别、 文本分类、 图像识别等领域。
    该算法的思想是: 一个样本与数据集中的k个样本最相似, 如果这k个样本中的大多数属于某一个类别, 则该样本也属于这个类别。

    二、距离度量

    在选择两个实例相似性时,一般使用的欧式距离
    Lp距离定义:

    Lp(xi,xj)=(l=1n|xi(l)xj(l)|p)1p

    其中xiRn,xjRn, 其中L∞定义为:
    L(xi,xj)=maxl|xi(l)xj(l)|

    其中p是一个变参数。
    当p=1时,就是曼哈顿距离(对应L1范数)
    曼哈顿距离对应L1-范数,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:|x1x2|+|y1y2|,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。
    曼哈顿距离:

    L1=k=1n|x1kx2k|

    L1范数表示为:
    L1|x|=i=1n|xi|x=[x1x2xn]Rn

    当p=2时,就是欧氏距离(对应L2范数)
    最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中。n维空间中两个点x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)间的欧氏距离
    欧氏距离:

    d12=k=1n(x1x2)2

    L2范数:

    L2|x|=i=1nxi2x=[x1x2xn]Rn

    当p→∞时,就是切比雪夫距离
    二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离:

    d12=max(|x1x2|,|y1y2|)

    n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的切比雪夫距离:
    d12=max(|x1ix2i|)

    三、k值选择

    如果选择较小的K值,就相当于用较小的邻域中的训练实例进行预测,学习的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用,单缺点是学习的估计误差会增大,预测结果会对近邻的实例点分成敏感。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,K值减小就意味着整体模型变复杂,分的不清楚,就容易发生过拟合。

    如果选择较大K值,就相当于用较大邻域中的训练实例进行预测,其优点是可以减少学习的估计误差,但近似误差会增大,也就是对输入实例预测不准确,K值得增大就意味着整体模型变的简单

    近似误差:可以理解为对现有训练集的训练误差。
    估计误差:可以理解为对测试集的测试误差。

    近似误差关注训练集,如果k值小了会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

    估计误差关注测试集,估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。

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

    流程:
    1) 计算已知类别数据集中的点与当前点之间的距离
    2) 按距离递增次序排序
    3) 选取与当前点距离最小的k个点
    4) 统计前k个点所在的类别出现的频率
    5) 返回前k个点出现频率最高的类别作为当前点的预测分类

    优点:
    1、简单有效
    2、重新训练代价低
    3、算法复杂度低
    4、适合类域交叉样本
    5、适用大样本自动分类

    缺点:
    1、惰性学习
    2、类别分类不标准化
    3、输出可解释性不强
    4、不均衡性
    5、计算量较大

    例子如下图:
    距离越近,就越相似,属于这一类的可能性就越大
    这里写图片描述
    这里写图片描述

    import math
    
    movie_data = {"宝贝当家": [45, 2, 9, "喜剧片"],
                  "美人鱼": [21, 17, 5, "喜剧片"],
                  "澳门风云3": [54, 9, 11, "喜剧片"],
                  "功夫熊猫3": [39, 0, 31, "喜剧片"],
                  "谍影重重": [5, 2, 57, "动作片"],
                  "叶问3": [3, 2, 65, "动作片"],
                  "伦敦陷落": [2, 3, 55, "动作片"],
                  "我的特工爷爷": [6, 4, 21, "动作片"],
                  "奔爱": [7, 46, 4, "爱情片"],
                  "夜孔雀": [9, 39, 8, "爱情片"],
                  "代理情人": [9, 38, 2, "爱情片"],
                  "新步步惊心": [8, 34, 17, "爱情片"]}
    
    # 测试样本  唐人街探案": [23, 3, 17, "?片"]
    #下面为求与数据集中所有数据的距离代码:
    x = [23, 3, 17]
    KNN = []
    for key, v in movie_data.items():
        d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
        KNN.append([key, round(d, 2)])
    
    # 输出所用电影到 唐人街探案的距离
    print(KNN)
    
    #按照距离大小进行递增排序
    KNN.sort(key=lambda dis: dis[1])
    
    #选取距离最小的k个样本,这里取k=5;
    KNN=KNN[:5]
    print(KNN)
    
    #确定前k个样本所在类别出现的频率,并输出出现频率最高的类别
    labels = {"喜剧片":0,"动作片":0,"爱情片":0}
    for s in KNN:
        label = movie_data[s[0]]
        labels[label[3]] += 1
    labels =sorted(labels.items(),key=lambda l: l[1],reverse=True)
    print(labels,labels[0][0],sep='\n')

    代码和例子来自:https://blog.csdn.net/saltriver/article/details/52502253

    2-2 K值的选择

    一、近似误差与估计误差:
    近似误差:对现有训练集的训练误差,关注训练集,如果近似误差过小可能会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
    估计误差:可以理解为对测试集的测试误差,关注测试集,估计误差小说明对未知数据的预测能力好,模型本身最接近最佳模型。
    二、K值确定标准:
    K值过小:k值小,特征空间被划分为更多子空间(模型的项越多),整体模型变复杂,容易发生过拟合,k值越小,选择的范围就比较小,训练的时候命中率较高,近似误差小,而用test的时候就容易出错,估计误差大,容易过拟合。
    K值=N:无论输入实例是什么,都将简单的预测他属于训练实例中最多的类。

    2-3 kd树

    一、原理:

    kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kd树是是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。 利用kd树可以省去对大部分数据点的搜索, 从而减少搜索的计算量。

    一个三维k-d树。 第一次划分(红色)把根节点(白色)划分成两个节点,然后它们分别再次被划分(绿色) 为两个子节点。最后这四个子节点的每一个都被划分(蓝色) 为两个子节点。 因为没有更进一步的划分, 最后得到的八个节点称为叶子节点
    这里写图片描述
    类比“二分查找”: 给出一组数据: [9 1 4 7 2 5 0 3 8], 要查找8。如果挨个查找(线性扫描),那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了: [0 1 2 3 4 5 6 7 8 9], 按前一种方式我们进行了很多没有必要的查找, 现在如果我们以5为分界点, 那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。

    因此, 根本久没有必要进入第一个簇,可以直接进入第二个簇进行查找。==把二分查找中的数据点换成k维数据点, 这样的划分就变成了用超平面对k维空间的划分==。空间划分就是对数据点进行分类, “挨得近”的数据点就在一个空间里面。

    二、构造方法:

    第一个问题简单的解决方法可以是选择随机选择某一维或按顺序选择,但是更好的方法应该是在数据比较分散的那一维进行划分(分散的程度可以根据方差来衡量)。好的划分方法可以使构建的树比较平衡, 可以每次选择中位数来进行划分, 这样问题2也得到了解决。
    这里写图片描述
    代码实现:

    # -*- coding: utf-8 -*-
    
    #from operator import itemgetter
    import sys
    reload(sys)
    sys.setdefaultencoding('utf8')
    
    
    # kd-tree每个结点中主要包含的数据结构如下 
    class KdNode(object):
        def __init__(self, dom_elt, split, left, right):
            self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)
            self.split = split      # 整数(进行分割维度的序号)
            self.left = left        # 该结点分割超平面左子空间构成的kd-tree
            self.right = right      # 该结点分割超平面右子空间构成的kd-tree
    
    
    class KdTree(object):
        def __init__(self, data):
            k = len(data[0])  # 数据维度
    
            def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
                if not data_set:    # 数据集为空
                    return None
                # key参数的值为一个函数,此函数只有一个参数且返回一个值用来进行比较
                # operator模块提供的itemgetter函数用于获取对象的哪些维的数据,参数为需要获取的数据在对象中的序号
                #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
                data_set.sort(key=lambda x: x[split])
                split_pos = len(data_set) // 2      # //为Python中的整数除法
                median = data_set[split_pos]        # 中位数分割点             
                split_next = (split + 1) % k        # cycle coordinates
    
                # 递归的创建kd树
                return KdNode(median, split, 
                              CreateNode(split_next, data_set[:split_pos]),     # 创建左子树
                              CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树
    
            self.root = CreateNode(0, data)         # 从第0维分量开始构建kd树,返回根节点
    
    
    # KDTree的前序遍历
    def preorder(root):  
        print root.dom_elt  
        if root.left:      # 节点不为空
            preorder(root.left)  
        if root.right:  
            preorder(root.right)  
    
    
    if __name__ == "__main__":
        data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
        kd = KdTree(data)
        preorder(kd.root)
    展开全文
  • interactiveknn, 基于JavaScript的交互式K 近邻机器学习算法 基于的交互式k 近邻用k 近邻算法与浏览器中的点进行视觉上的交互以对未知点进行分类。可以在 Lettier.com 播放。开始git clone git@github....
  • k近邻(k-Nearest Neighbor 简称KNN)学习是一种常用的监督学习算法,给定一个测试样本,基于某种距离度量来找出训练集的所有样本中与该样本最为靠近的k个样本,然后根据这k个邻居的信息进行预测。 什么时候用到KNN...

    介绍

    k近邻(k-Nearest Neighbor 简称KNN)学习是一种常用的监督学习算法,给定一个测试样本,基于某种距离度量来找出训练集的所有样本中与该样本最为靠近的k个样本,然后根据这k个邻居的信息进行预测。

    什么时候用到KNN?

    knn算法既能够处理分类任务也能进行回归分析,两种任务所采用的方法略有不同。

    • 分类任务:通常使用“投票法”,将选择出的k个邻居样本出现最多的类别标记作为最终的预测结果。
    • 回归任务:使用“平均法”,测试样本的最终输出为k个邻居样本的实值输出标记的平均值;或者按照加权平均的方式求得,距离越近,权重越大。

    KNN是如何工作的?

    KNN算法是懒惰学习的代表,因为它没有显示的训练过程。KNN算法是基于特征相似度的,因此确定K值是整个KNN算法的重中之重。下面举个例子说明KNN的预测过程。


    优缺点分析

    pros

    • 能够承担多任务,即可分类又可回归。
    • 可解释性极强,算法逻辑通俗易懂。
    • 整个预测过程的周期较短。

    cons

    • 计算成本十分昂贵,由于算法保留了所有的训练数据。
    • 高存储的要求。
    • 对于数据的规模和非相关的特征来说十分敏感。

    参考

    《机器学习》- 周志华

    Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

    A Quick Introduction to K-Nearest Neighbors Algorithm

     

    展开全文
  • 本篇主要是自己复习和总结机器学习算法中最基础入门的——k近邻(KNN)算法,内容由网上百度与摘抄唐宇迪老师的讲义。 k近邻介绍 k近邻参数 官网例子 k近邻实际应用 房租价格预测 k...

    机器学习-k近邻(KNN)
    本篇主要是自己复习和总结机器学习算法中最基础入门的——k近邻(KNN)算法,内容由网上百度与摘抄唐宇迪老师的讲义。

    k近邻介绍

    ——K最近邻(k-Nearest Neighbor,KNN),k近邻算法可以应用于分类场景与回归场景,是一个理论上比较不成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
    ——用官方的话来说,所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居), 这K个实例的多数属于某个类,就把该输入实例分类到这个类中。

    : 看图举例:
    这里写图片描述
    图形中有2种已知的图形,分别是蓝色的方块和红色的三角,绿色的未知图形。通过K近邻算法去判断未知的绿色图形是什么,取决于它周围距离最近的图形。
    比如把K近邻的近邻参数设置成3(图中实线圆圈),那么未知的绿色图形就是三角。如果近邻参数设置成5(图中虚线圆圈),那么未知的绿色图形就是方块。

    所以在K近邻算法中,设置近邻参数是会决定最后预测的结果准确性,那么怎么设置参数是多少呢?这个后面会给大家再进行介绍,本篇K近邻算法的实现主要是通过经典的机器学习库(sklearn)来完成。

    K近邻在sklearn里面的API为sklearn.neighbors,在该模块下由细分了13个小的模块。本文主要使用neighbors.KNeighborsRegressor基于k-最近邻居的回归来进行说明官方教程链接

    类型 描述
    neighbors.BallTree BallTree用于快速广义N点问题
    neighbors.DistanceMetric DistanceMetric类
    neighbors.KDTree KDTree用于快速广义N点问题
    neighbors.KernelDensity([bandwidth, …]) 核密度估计
    neighbors.KNeighborsClassifier([…]) 实现k近邻的分类器投票
    neighbors.KNeighborsRegressor([n_neighbors, …]) 基于k-最近邻居的回归
    neighbors.LocalOutlierFactor([n_neighbors, …]) 使用局部异常因子(LOF)的无监督异常值检测
    neighbors.RadiusNeighborsClassifier([…]) 在给定半径内的邻居之间实施投票的分类器
    neighbors.RadiusNeighborsRegressor([radius, …]) 基于固定半径内的邻居的回归
    neighbors.NearestCentroid([metric, …]) 最近的质心分类器
    neighbors.NearestNeighbors([n_neighbors, …]) 用于实现邻居搜索的无监督学习者
    neighbors.kneighbors_graph(X, n_neighbors[, …]) 计算X中点的k-邻居的(加权)图
    neighbors.radius_neighbors_graph(X, radius) 计算X中各点的邻居(加权)图

    k近邻参数

    sklearn.neighbors.KNeighborsRegressor默认参数:

    sklearn.neighbors.KNeighborsRegressor(n_neighbors = 5,weights =‘uniform’,algorithm =‘auto’,leaf_size = 30,p = 2,metric =‘minkowski’,metric_params = None,n_jobs = 1,** kwargs )

    参数说明:
    n_neighbors:int, optional (default = 5)

    使用默认的邻居数量kneighbors查询,默认是5

    weights : str or callable

    权函数用于预测,可能的值
    ‘uniform’ :统一的重量。权重分在每个社区都是一样的
    ‘distance’ :重量分距离的倒数。在这种情况下,接近邻居查询的点会有一个更大的影响力远比邻居
    [callable] :一个用户定义的函数接受一个数组的距离,并返回一个数组包含权重相同的形状

    algorithm : {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, optional

    算法用于计算最近的邻居
    ‘ball_tree’将使用BallTree
    ‘kd_tree’将使用KDTree
    'brute’将使用蛮力搜索
    ‘auto’将试图确定最合适的算法基于价值观传递给合适的方法

    leaf_size : int, optional (default = 30)

    叶大小BallTree或KDTree传递。这可能影响施工和查询的速度,以及所需的内存存储树。最优值取决于问题的性质。

    metric : string or callable, default ‘minkowski’

    指标用于树的距离。默认度量是闵可夫斯基,p = 2相当于欧几里得度量的标准。看到的DistanceMetric类的文档的列表可用指标。

    metric_params : dict, optional (default = None)

    额外的关键字参数的度量函数

    n_jobs : int, optional (default = 1)

    并行工作的数量的邻居搜索。如果1,那么就业人数将CPU核的数量。不影响健康的方法。

    官网例子

    X=[[0],[1],[2],[3]] #建一个List
    y=[0,0,1,1] #建一个List
    from sklearn.neighbors import KNeighborsRegressor #导入K近邻回归模块
    neigh=KNeighborsRegressor(n_neighbors=2) #近邻参数设置成2个相邻
    neigh.fit(X, y) #使用X作为训练数据,y作为目标值
    print(neigh.predict([[1.5]])) #给提供的数据预测对应的标签,当x=1.5的时候y应该是多少
    
    #最终输出当x=1.5的时候y=0.5
    
    类型 描述
    fit(X, y) 使用X作为训练数据,y作为目标值(类似于标签)来拟合模型。
    get_params([deep]) 获取估值器的参数。
    kneighbors([X, n_neighbors, return_distance]) 查找一个或几个点的K个邻居
    kneighbors_graph([X, n_neighbors, mode]) 计算在X数组中每个点的k邻居的(权重)图
    predict(X) 给提供的数据预测对应的标签
    predict_proba(X) 返回测试数据X的概率估值
    score(X, y[, sample_weight]) 返回给定测试数据和标签的平均准确值
    set_params(**params) 设置估值器的参数

    k近邻实际应用

    注:该实例出至唐宇迪老师,大家也可以百度查看
    案例数据下载
    案例背景:
    自己在美国有一套房子想要在Airbnb平台上进行短租,但是不知道自己的房子能租多少钱?设置多少钱才是最合理的呢?
    好吧,开始前我先说明一下我的房子情况:我的房子可以容纳6名旅客,有3个卧室,厕所每个卧室都有,有3张床,我想最短租1天我还是能接受的,最多租30天好像就差不多了。为了能收益最大我们直接来代码:

    房租价格预测

    导入所需要的Python模块

    import pandas as pd #导入pandas库
    from sklearn.neighbors import KNeighborsRegressor #导入机器学习库中的K近邻回归模型
    from sklearn.metrics import mean_squared_error #导入机器学习库中的均方误差回归损失模型
    

    导入数据及数据预处理

    dc_listings=pd.read_csv(r'C:\Users\huangjunwen\Desktop\listings.csv') #将数据导入,路径请根据自己的文件路径设置
    features = ['accommodates','bedrooms','bathrooms','beds','price','minimum_nights','maximum_nights','number_of_reviews'] #因数据太多设置只选取这8列
    dc_listings = dc_listings[features] #获取只需要的数据列,并覆盖原始数据
    dc_listings.head()#先查看一下数据情况,对数据有个初步了解
    dc_listings['price']=dc_listings.price.str.replace("\$|,",'').astype(float) #将价格price变成数字类型
    dc_listings=dc_listings.dropna() #过滤缺失数据
    normalized_listings = dc_listings #复制一下数据
    
    norm_train_df=normalized_listings.copy().iloc[0:2792] #创建训练集训练集取2792个样本
    norm_test_df=normalized_listings.copy().iloc[2792:] #创建测试集取879个样本
    

    数据列名说明 accommodates:可以容纳的旅客、bedrooms:卧室的数量、bathrooms:厕所的数量、beds:床的数量、price:每晚的费用、minimum_nights:客人最少租几天、maximum_nights:客人最多租几天、number_of_reviews:评论的数量

    创建K近邻模型

    cols = ['accommodates','bedrooms','bathrooms','beds','minimum_nights','maximum_nights','number_of_reviews'] #选择测试集的训练的列
    knn = KNeighborsRegressor(10) #模型近邻值手动设置成10,其他为默认参数
    knn.fit(norm_train_df[cols], norm_train_df['price']) #X放入训练集数据,Y放入目标输出数据
    two_features_predictions = knn.predict(norm_test_df[cols]) #输出测试集结果
    

    创建模型效果验证

    two_features_mse = mean_squared_error(norm_test_df['price'], two_features_predictions)
    two_features_rmse = two_features_mse ** (1/2)
    print(two_features_rmse) #输出模型验证结果,根据结果调整近邻参数
    

    调用模型设置实际值进行预测

    print(knn.predict([[6,3,3,3,1,30,0]])) #设置自己房子的信息,预测出对应的价格
    

    数字代表我房子与数量列对应的名称,容纳旅客数=6,卧室=3,厕所=3,床=3,最少租=1,最多租=30,评论=0

    好了,我房子的一晚上价格大概能租192美元,哇!感觉自己好有钱。。。。好吧,能先给我来一套房子吗?

    展开全文
  • 机器学习k近邻

    2017-12-08 16:54:32
    核心思想KNN算法假设给定的训练集中的实例都已经分好类了,对于新的实例,根据离它最近的k个训练实例的类别来预测它的类别。即这k个实例大多数属于某个类别则该实例就属于某个类别。比如k为5,离新实例a最近的5个...

    核心思想

    KNN算法假设给定的训练集中的实例都已经分好类了,对于新的实例,根据离它最近的k个训练实例的类别来预测它的类别。即这k个实例大多数属于某个类别则该实例就属于某个类别。比如k为5,离新实例a最近的5个样本的情况为,3个样本属于A类,1个样本属于B类,一个样本属于C类,那么新实例a属于A类。

    这里写图片描述

    常用距离

    • 欧氏距离
      d(x,y)=ni=1(xiyi)2
    • 曼哈顿距离
      d(x,y)=ni=1|(xiyi)|
    • 切比雪夫距离
      d(x,y)=max(|xiyi|)

    这里写图片描述

    k值的影响

    k值的选取可能会影响到分类结果,如下图,k=3和k=5时的分类结果是不同的。

    这里写图片描述

    1. k值小可能会导致预测结果对近邻的样本点敏感,如果刚好是噪音则会导致预测结果出错,容易发生过拟合。近似误差小,估计误差大。
    2. k值大可能会导致较远的样本也影响预测,也可能会导致预测错误。近似误差大,估计误差小。
    3. k值一般先取较小的数,再用交叉验证方法选择最优k值。

    算法实现

    两种方式:线性扫描和kd树。

    线性扫描

    KNN的最简单朴素的方法即直接线性扫描,大致步骤如下:
    1. 计算待预测数据与各训练样本之间的距离;
    2. 按照距离递增排序;
    3. 选择距离最小的k个点;
    4. 计算这k个点类别的频率,最高的即为待预测数据的类别。

    代码实现

    from numpy import *
    import pylab as pl
    
    dataSet = array([[11, 12], [12, 12], [11, 11], [11, 16], [12, 16], [17, 11], [17, 12]])
    classes = ['A', 'A', 'A', 'B', 'B', 'C', 'C']
    k = 3
    dot = [13, 13]
    type
    r = 0
    dataSize = dataSet.shape[0]
    diff = tile(dot, (dataSize, 1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff, axis=1)
    dist = squareDist ** 0.5
    sortedDistIndex = argsort(dist)
    classCount = {}
    for i in range(k):
        label = classes[sortedDistIndex[i]]
        classCount[label] = classCount.get(label,0) + 1
        if dist[i] > r:
            r = dist[i]
    maxCount = 0
    for key, value in classCount.items():
        if value > maxCount:
            maxCount = value
            type = key
    pl.plot(dot[0], dot[1], 'ok')
    circle = [i*pi/180 for i in range(0,360)]
    x = cos(circle)*r+dot[0]
    y = sin(circle)*r+dot[1]
    pl.plot(x, y, 'r')
    pl.plot([point[0] for point in dataSet[0:3]], [point[1] for point in dataSet[0:3]], 'og')
    pl.plot([point[0] for point in dataSet[3:5]], [point[1] for point in dataSet[3:5]], 'or')
    pl.plot([point[0] for point in dataSet[5:7]], [point[1] for point in dataSet[5:7]], 'oy')
    pl.show()
    

    这里写图片描述

    kd树

    线性扫描非常耗时,为了减少计算距离的次数提高效率,使用kd树方法,它能快速地找到查询点近邻。

    可以通过将搜索空间进行层次划分建立索引树以加快检索速度。

    对于二维空间,它最终要划分的空间类似如下,

    这里写图片描述

    决定在哪个维度上进行分割是由所有数据在各个维度的方差决定的,方差越大说明该维度上的数据波动越大,更应该再该维度上对点进行划分。例如x维度方差较大,所以以x维度方向划分。

    分割时一般取分割维度上的所有值的中值的点,比如下图,第一次计算方差较大的维度为x维度,中值点为A,以x=Ax分割,接着对分割后的点分别又继续分割,计算方差并寻找中值,以y=Cy、y=By分割,以此类推。

    这里写图片描述

    kd树查找

    从根节点开始查找,直到叶子节点,整个过程将最短距离d和相应的点记录下来。

    回溯,通过计算待预测的点到分割平面的距离l与最短距离d比较,看是否要进入节点的相邻空间去查找。回溯的过程是为了确认是否有必要进入相邻子空间去搜索,当待预测点到最近点的距离d大于待预测点到分割面的距离l时,则需要到相邻子空间查找,否则则没必要,直接往上一层回溯。

    ========广告时间========

    公众号的菜单已分为“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

    鄙人的新书《Tomcat内核设计剖析》已经在京东销售了,有需要的朋友可以购买。感谢各位朋友。

    为什么写《Tomcat内核设计剖析》

    =========================
    欢迎关注:

    这里写图片描述

    展开全文
  •     k近邻法(k-nearest neighbor, kNN)是一种基本分类与回归方法,其基本做法是:给定测试实例,基于某种距离度量找出训练集中与其最靠近的k个实例点,然后基于这k个最近邻的信息来进行预测。     通常,...
  • K最近邻(k-Nearest Neighbor,KNN),是一种常用于分类的算法,是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是:如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的...
  • 机器学习k近邻算法

    2018-02-11 10:42:42
    毕业10年,回过头看线性代数,全部还给了老师。翻看《Machine Learning in Action》做做笔记 1 欧式距离计算 # -*- coding: utf-8 -*- ''' Created on 2017年10月27日 @author: dzm ...from numpy import array, ...
  • k近邻法(K-NN)是一种基本的分类与回归方法。分类时,对新的实例,根据k个最近邻的训练实例的类别,通过多数表决等方式进行预测。k近邻的三要素:k值的选择、距离度量以及分类决策规则。k近邻算法简单、直观,给定...
  • 机器学习实战 K近邻算法 1.前言 k近邻是一种基本分类与回归方法。k近邻法的输入为实例的特征向量,对应于特征空间的点,输出为实例的类别,可以取多类。k近邻法假设给定一个训练数据集,其中的实例类别已定。分类...
  • 机器学习实战2--K近邻

    2016-02-24 15:59:01
    第二章的K近邻算法是一个简单的机器学习算法。 K近邻算法: 原理:收集一个样本数据集合,并且样本集中每个数据都存在标签。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后...
  • 可能有人会说,K近邻模型有什么好写的,那分明就是一个最简单的机器学习模型,哦,不,连机器学习也算不上的算法吧。但是这里,我想提醒的是,我们要讨论的,不仅仅是简单的K近邻模型,而是和它相关的一些有困惑的...
  • 机器学习算法与Python实践之(一)k近邻(KNN)zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习...
  • K近邻学习笔记

    2016-11-16 19:49:15
    但个人并不把它列入到机器学习中的学习算法,它本身并没有对数据进行理论建模的过程,而是根据现有的数据在n维空间的分布,来确定预测点的归属。这就好比,在现实世界的维度中,经常游走于男厕所的我们归为男性,而...
  • 参考文献:机器学习与数据挖掘参考文献 k近邻法是一种基本分类与回归方法。k近邻算法简单、直观:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最近邻的k个实例,这k个实例的多数属于某个类,...
  • 理论部分与“机器学习算法与python实践:k近邻(kNN)”这篇博文相同,实践数据也相同,差别为代码部分为作者用Matlab重新编写。 最近开始学习机器学习,理论部分主要参考周志华老师的《机器学习》这本书,实践部分...
  •  K-近邻算法是一种易于理解的机器学习算法,它的工作原理是:存在一个样本数据集合,并且样本中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征...
  • 机器学习实战》-Ch2-k-近邻算法-源代码,笔记链接见:https://blog.csdn.net/qq_34243930/article/details/84948770
  • 机器学习基础算法之K近邻,朴素贝叶斯,决策树与随机森林1.scikit-learn数据集API2.获取数据集的返回类型3.数据集分隔4.sklearn机器学习算法的实现-估计器5.K近邻6.朴素贝叶斯7.评估标准8.交叉验证和网格搜索9.决策...
1 2 3 4 5 ... 20
收藏数 14,942
精华内容 5,976