k 临近 机器学习_机器学习k-means聚类中k的选取 - CSDN
  • kNNk邻近,k-Nearest Neighbor,kNN;是懒惰学习(lazy learning)的代表。所谓懒惰学习就是没有没有显式训练过程,只是把训练数据保存起来,用的时候直接再算出结果就行了。具体算法如下: 给定测试样本,基于某种...

    kNN

    k邻近,k-Nearest Neighbor,kNN;是懒惰学习(lazy learning)的代表。所谓懒惰学习就是没有没有显式训练过程,只是把训练数据保存起来,用的时候直接再算出结果就行了。具体算法如下:
    给定测试样本,基于某种距离度量找出训练集中与最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测;若是分类问题就可以用投票法确定最后的结果,若是回归问题就可以用平局法。但是最后结果跟k选取有关系:
    这里写图片描述
    可以看出k=1的时候,判定为+,为3的时候判定为-,为5的时候判定又为+。
    给定测试样本x,若其最近邻样本为z,则最近邻分类器的出错概率为:

    P(err)=1cYP(c|x)P(c|z)

    假设样本独立同分布,且对任意x和任意小的正数δ,在x附近δ距离范围内总能找到一个训练样本。令c=argmaxcYP(c|x)表示贝叶斯最优分类器的结果,有
    P(err)=1cYP(c|x)P(c|z)1cYP2(c|x)1P2(c|x)=(1+P(c|x))(1P(c|x))2×(1P(c|x))

    怎么样是不是有点惊讶,最近邻分类器虽然简单,但是它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。

    低维嵌入

    我们讨论错误率的时候有个假设,在样本x附近δ内总能找到一个训练样本。这就要求训练样本的采样密度足够大。若δ=0.001则单个属性就要1000个样本啦。若是20个属性则要(1000)20个样本。天了噜,这怎么算,你需要降维(姜维,雾)!
    这里写图片描述
    如图所示我们把三维空间中的点降维成了两维。可以直观的感受到,我们这样的降维对分类任务来说没有一丝影响反而更加好算了。即人们观察到数据虽是高位的,但是与学习任务密切相关的也许仅是一个低维分布,即高维空间中的一个低维“嵌入”。我们下一讲说说降维最经典,我最喜欢的算法PCA(Principal Component Analysis)。

    展开全文
  • 机器学习K临近算法

    2019-07-24 22:01:42
    什么是K临近算法,其实可以根据字面上了解,若我现在有一堆点,根据它们的特征我把它们分成若干类,现在再加入一个点,求出这个点是属于哪一个类,我们可以取K个点,然后我们再计算所有点到这个点的欧式距离或者某...

    1.概念:

           什么是K临近算法,其实可以根据字面上了解,若我现在有一堆点,根据它们的特征我把它们分成若干类,现在再加入一个点,求出这个点是属于哪一个类,我们可以取K个点,然后我们再计算所有点到这个点的欧式距离或者某一种距离,然后选出离它最近的K个点,看这K个点中那种点比较多,然后就把这个点归为哪一类。

          什么是分类,分类是离散的,我们上面说的点的归类也是一种分类。

          什么是回归,回归是连续的,例如在二维坐标系中我们给出若干个点,求一条直线,这就是回归。

     

    2.KNN实现分类

             1.我们用sklearn先生成一堆点,然后再用matplotlib将图像显示出来

               

                

    2.再把它放进我们生成的KNN分类器中,图像就是我们的分类结果,不同颜色就是不同的类别,y2放的才是这个点正确的分类

     

    3.答案

    3.KNN实现回归 

    生成点

     

    展开全文
  • 本篇是基于机器学习实战>并参考西瓜书>以及李航的统计机器学习>这三本书所记的笔记,所有代码均是由python缩写,且有相对详细的中文注释,其中加入了自己的一些想法.k近邻算法(k-nearest neighbor)也...

    趁着暑假的档期,总结一下机器学习的一些算法,如有表达不清,或者错误的地方,欢迎指导.本篇是基于<机器学习实战>并参考<西瓜书>以及李航的<统计机器学习>这三本书所记的笔记,所有代码均是由python缩写,且有相对详细的中文注释,其中加入了自己的一些想法.

    k近邻算法(k-nearest neighbor)也可以叫做KNN,是一种基本的分类和回归方法.输入是训练数据的特征向量,当然,KNN是不具备显式的学习过程.假定给定一个训练数据集,且每个数据都有对应的类别,分类时,对新的数据,根据K个最近的数据类别,通过多数表达等方式进行预测.最简单的说法,找K个离的最近的训练数据,哪种类别占的多,就用哪种方法.

    K近邻的三个基本要素:K值的选择、距离度量、以及分类决策规则.

    先简单提下一距离度量,这篇文章讲的不错,下面就复制粘贴了,想了解距离度量的直接点下面传送门,这里就简单介绍一下.

    曼哈顿距离,欧式距离,明式距离,切比雪夫距离区别

    最熟悉的欧式距离:最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中,如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为:


    曼哈顿距离,我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:

    切比雪夫距离,若二个向量或二个点p 、and q,其座标分别为,则两者之间的切比雪夫距离定义如下:

        这也等于以下Lp度量的极值:,因此切比雪夫距离也称为L∞度量


    这里我使用了四个例子,第一个是构建一个最简单的2维特征向量以及对应的实例,然后输入一个测试向量,离谁近,就是分类结果就是谁'第二个例子是机器学习实战里的例子,使用kNN改进约会网站的配对效果,数据是由txt文本的样式给出,前三列分别对应着每年获得的飞行常客里程数、玩视频游戏所消耗时间的百分比、每周消费的冰淇淋公升数,最后一列是标签,如不喜欢约会,大量约会,少量约会,数据如下:

    40920    8.326976    0.953952    largeDoses
    14488    7.153469    1.673904    smallDoses
    26052    1.441871    0.805124    didntLike
    75136    13.147394    0.428964    didntLike
    38344    1.669788    0.134296    didntLike

    72993    10.141740    1.032955    didntLike

    这里,我们发现,如果计算距离,第一列每年飞行里程数的特征值很大,会占有很大比重,但是,玩游戏消耗的时间和吃冰淇淋同样是评估约会的重要特征,这时候就需要对特征数据进行标准化,本篇当中我选择的是将数值归一化到0-1之间

    而选择的标准化算法为 new = (old-min)/(max-min),其中old为旧的特征值,new为新的特征值,min和max分别对应特征中的最小值和最大值.

    第三个例子是关于手写数字识别的,采用的数据也由机器学习实战提供的,只不过这里我的看到的手写数字已经转换成了文本形式,如下对应的是3这个值

    00000000000011111111100000000000
    00000000000111111111110000000000
    00000000001111111111110000000000
    00000000001111111111111000000000
    00000000001111111111111100000000
    00000000001111111111111100000000
    00000000001111100001111100000000
    00000000000011100001111110000000
    00000000000001000011111110000000
    00000000000000000111111100000000
    00000000000000011111111100000000
    00000000000000111111111100000000
    00000000000111111111111000000000
    00000000001111111111110000000000
    00000000001111111111000000000000
    00000000000111111111000000000000
    00000000000111111111100000000000
    00000000000011111111110000000000
    00000000000000011111111000000000
    00000000000000000111111100000000
    00000000000000000011111100000000
    00000000000000000001111110000000
    00000000011000000000011111000000
    00000000111100000000111111000000
    00000000111100000001111111000000
    00000000111100000011111111000000
    00000000011111111111111111000000
    00000000011111111111111110000000
    00000000011111111111111110000000
    00000000001111111111111100000000
    00000000000011111111111000000000
    00000000000001111111110000000000

    第四个例子我采用的mnist数据,数据样本是png单通道图像,我将图像矩阵转换成1*784的特征矩阵,同样,错误仅有0.0334,并没有采取最优化的算法,所以这边计算时间有点长.值得注意的是,我将所有png的路径以txt的文件形式表示,前面是路径,空格后面是标签,样式如下:

    mnist/train/5/00000.png 5
    mnist/train/0/00001.png 0
    mnist/train/4/00002.png 4
    mnist/train/1/00003.png 1
    mnist/train/9/00004.png 9
    mnist/train/2/00005.png 2
    mnist/train/1/00006.png 1

    四个例子简单介绍后,详细讲解代码实现过程,请看代码的具体注释,test1-test4分别对应这四个列子

    #!/usr/bin/env python2
    # -*- coding: utf-8 -*-
    """
    Created on Mon Jul  9 14:19:59 2018
    
    @author: hjxu
    """
    
    import numpy as np
    import os
    import operator
    import scipy
    from scipy import misc #这是我用来打开图像的一个库,有兴趣的可以了解一下
    
    
    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
    
    def classify(inX, dataSet, labels, k): #我们整个数据都在这边处理
        '''
        inX:输入参数
        dataSet:训练样本集
        labels:训练样本标签向量
        K:最近邻参数的个数
        '''
    
        dataSetSize = dataSet.shape[0]  # shape是array的一个查看数组大小的函数,返回高和宽
        diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  # tile是将inX的纵向扩展dataSetSize倍,
                                                            # 横向扩展1倍,为了能直接和dataSet相减
        sqDiffMat = diffMat**2
        sqDistance = sqDiffMat.sum(axis=1)  # axis=1指横向求内和,如果axis=0则纵向求内和,如果没有这个参数,则所有值求和
        distance = sqDistance**0.5
        sortDistanceIndicies = distance.argsort()  # 按照从小到大排序,输出每个值对应的下标
        classCount = {}  # 创建一个字典
    
        for i in range(k):  # 选择距离最小的k个点
            votelabel = labels[sortDistanceIndicies[i]]
            classCount[votelabel] = classCount.get(votelabel, 0) + 1 # 对每一个字典的key后面对应的int加一
    
        #下面就需要将字典进行排序,要按照第二列排序
        sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
        return sortedClassCount[0][0]
    
    def file2matrix(filename): #第二个列子的数据处理,主要是打开txt文件,然后转换成特征向量
        fr = open(filename)#打开文件
        numbersOfLines = len(fr.readlines())#查看有多少行,注意,readlines和readline是有很大区别的
        resMat = np.zeros((numbersOfLines, 3))#生成矩阵
        reslabels = []
        print numbersOfLines
        fr = open(filename)
        index = 0
        for line in fr.readlines():
            line = line.strip()#去掉回车字符
            # print line
            listFromLine = line.split('\t')#按照空格分割
            # print listFromLine[0:3]
            resMat[index, :] = listFromLine[0:3]#给矩阵赋值,前三列对应这特征
            reslabels.append(int(listFromLine[-1])) #最后一列则是标签,注意,这里标签我都转换成了数字
            index += 1
        return resMat, reslabels
    
    def Norm(DataSet): #特征归一化
        minval = DataSet.min(0) ##能返回每列对应的最小值
        maxval = DataSet.max(0)
        ranges = maxval - minval
        normalDataSet = np.zeros(DataSet.shape)  # 新建立一个数组用来存放归一化后的data
        numOfData = DataSet.shape[0]
        normalDataSet = DataSet - np.tile(minval, (numOfData, 1))  # tile是将inX的纵向扩展numOfData倍,
        normalDataSet = normalDataSet/np.tile(ranges, (numOfData, 1))  # 方便直接相减和相除
        return normalDataSet, ranges, minval
    
    def img2vector(filename): #这是第三个例子,需要将手写数字的txt文件转换成列向量
        resVect = np.zeros((1,1024))
        fr = open(filename)
        for i in range(32):  # 按照行展开
            lineStr = fr.readline()
            for j in range(32):
                resVect[0, 32*i+j] = int(lineStr[j])
        return resVect
    
    def png2vector(filename):  #这个是第四个例子,其中folder + filename对应着图片所在的对峙
        folder = '/home/hjxu/PycharmProjects/tf_examples/hjxu_mnist/mnist_img_data/'
        resVect = np.zeros((1,784))
        fr =misc.imread(folder + filename) #读取图像
        for i in range(28):  # 按照行展开
            for j in range(28):
                resVect[0, 28*i+j] = float(1.0 * fr[i, j] / 255) #图像中的值是0-255的,所以归一化可以选择除以255
        return resVect
    
    
    def mnistClassTest(train_patch, test_patch): #第三个例子的测试,参数分别对应这训练集和测试集所在的文件夹路径
        trainLabels = [] 
        trainFileList = os.listdir(train_patch) #os库的用法,返回当前目录下的子文件
        mTrain = len(trainFileList)#查看有多少子文件
        trainMat = np.zeros((mTrain, 1024)) #建立空的特征向量
        for i in range(mTrain):
            fileName = trainFileList[i] #对应这每个子文件
            labels = int(fileName.split('_')[0]) #因为标签的是按照2_6.txt这种形式命名的,所以在'_'前的数字就是对应的手写数字标签
            trainLabels.append(labels)
            trainMat[i, :] = img2vector(train_patch + '/' + fileName) #转换成特征向量
    #测试同上
        testfileList = os.listdir(test_patch)
        m_Test = len(testfileList)
        error = 0
        for i in range(m_Test):
            fileName = testfileList[i]
            testLabel = int(fileName.split('_')[0])
            vectorTest = img2vector(test_patch + '/' + fileName)
            classResult = classify(vectorTest, trainMat, trainLabels, 10)
            print "predict: %d, label: %d" % (classResult, testLabel)
            if(classResult != testLabel):
                error = error + 1
        print "The predicted erroe: %f" % (1.0 * error/(m_Test))
    
    
    def mnistPngClassTest(train_list, test_list):#对应这两个txt文件所在的路径
        fr = open(train_list)  # 打开文件
        mTrain = len(fr.readlines())  # 查看有多少行,注意,readlines和readline是有很大区别的
        trainMat = np.zeros((mTrain, 784))  # 生成矩阵,由于我的图像是28*28的,所以展开有784列
        trainLabels = []
        fr = open(train_list)#注意,这里需要重新打开一次,具体为啥,我也不是很清楚,应该和文件打开的数据流有关
        i = 0
        for line in fr.readlines():
            line = line.strip()  # 去掉回车字符
            # print line
            listFromLine = line.split(' ')  # 按照空格分割
            filepath = listFromLine[0]
            label = int(listFromLine[1])
            trainMat[i, :] = png2vector(filepath)
            trainLabels.append(label)
            i = i + 1
    
        #测试
        frtest = open(test_list)
        mTest = len(frtest.readlines())
        print mTest
        error = 0
        frtest = open(test_list)
        for line in frtest.readlines():
            line = line.strip()  # 去掉回车字符
            # print line
            listFromLine = line.split(' ')  # 按照空格分割
            filepath = listFromLine[0]
            testLabel = int(listFromLine[1])
    
            vectorTest = png2vector(filepath)
            classResult = classify(vectorTest, trainMat, trainLabels, 10)
            print "predict: %d, label: %d" % (classResult, testLabel)
            if (classResult != testLabel):
                error = error + 1
        print "The predicted error: %f" % (1.0 * error / (mTest))
    
    
    
    
    def test1():
        testa = [[0, 0]]
        groups, labels = createDataSet()
        testalabels = classify(testa, groups, labels, 3)
        print "the predicted result of testa is ", testalabels
    
    def test2():
        Ratio = 0.1
        dataMat, labels = file2matrix('./datingTestSet2.txt')
        norMat, _,_ = Norm(dataMat)
        m = norMat.shape[0]
        numOfTest = int(Ratio * m)
        errorCount = 0.0
    
        for i in range(numOfTest):
            classResult = classify(norMat[i,:],norMat[numOfTest:m,:], labels[numOfTest:m],5)
            print "predict: %d, label: %d" % (classResult,labels[i])
            if(classResult == labels[i]):
                errorCount += 1.0
        print "The predicted erroe: %f" %(1.0 * errorCount/(numOfTest))
    
    def test3():
        train_patch = '/home/hjxu/MLProject/KNN/digits/trainingDigits'
        test_path = '/home/hjxu/MLProject/KNN/digits/testDigits'
        mnistClassTest(train_patch, test_path)
    
    def test4():
        train_patch = '/home/hjxu/PycharmProjects/tf_examples/hjxu_mnist/mnist_img_data/train.txt'
        test_path = '/home/hjxu/PycharmProjects/tf_examples/hjxu_mnist/mnist_img_data/test.txt'
        mnistPngClassTest(train_patch, test_path)
    
    if __name__ == '__main__':
        # test1()
        # test2()
        # test3()
        test4()

    本代码中用KNN直接对图像进行手写数据识别所消耗的时间较长,但是准确率还是很高的,错误率仅为0.0334

    代码输出如下

    predict: 2, label: 2
    predict: 3, label: 3
    predict: 4, label: 4
    predict: 5, label: 5
    predict: 6, label: 6

    The predicted error: 0.033400

    到这里,简单回顾一下knn算法,以及算法的简单实现,有时间会利用比较好的数据结构来实现KNN算法,如K-D树等.


    Process finished with exit code 0

    展开全文
  • 一、k-临近算法 是一种标准的分类方法,简单来说就是通过测量不同特征值之间的距离方法进行分类。 优点:精度高、对异常值不敏感、无数据输入假定。 缺点:计算复杂度高、空间复杂度高。 适用数据范围:数值型和标称...

    楼主自学python,自我总结发博客,这样可以更加掌握
    华丽的分割线------------------------------------------------------------------------------

    一、k-临近算法
    是一种标准的分类方法,简单来说就是通过测量不同特征值之间的距离方法进行分类。

    优点:精度高、对异常值不敏感、无数据输入假定。
    缺点:计算复杂度高、空间复杂度高。 适用数据范围:数值型和标称型

    二、k-临近算法一般流程:
    (1) 收集数据:可以使用任何方法,这里推荐标准数据库。
    (2) 准备数据:距离计算所需要的数值,最好是结构化的数据格式。
    (3) 分析数据:可以使用任何方法。
    (4) 训练算法:此步骤不适用于k-近邻算法。
    (5) 测试算法:计算错误率。
    (6) 使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输 入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理

    from numpy import*
    import operator
    from os import listdir
    
    
    
    def classify0(inX,dataSet,labels,k):
        dataSetSize = dataSet.shape[0]
        diffMat = tile(inX,(dataSetSize,1)) - dataSet
        sqDiffMat = diffMat**2
        sqDistances = sqDiffMat.sum(axis=1)
        distances = sqDistances**0.5
        sortedDistIndicies = distances.argsort() #计算距离
        classCount={}
        for i in range(k):  #选择距离最短的K个点
            vorteIlael = labels[sortedDistIndicies[i]]
            classCount[vorteIlael] = classCount.get(vorteIlael,0) + 1
            sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) #排序
            return sortedClassCount[0][0]
    
    展开全文
  • 机器学习与python实践(一)k临近(knn)knn算法分析 k最邻近分类算法是最简单的机器学习算法,它采用测量不同特征值之间的距离进行分类,想法很简单:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)...
  • 机器学习之路——K邻近法详解

    千次阅读 2018-03-31 17:07:41
    统计学习方法第三章——knn算法首先要明确的第一个重点是,k邻近不具有显示的学习过程,它是基于实例的一种学习方法,简单来说就是给定一堆西瓜的数据,然后输入一个新西瓜的数据,找到与这个新西瓜最近的k个西瓜,...
  • k-临近算法学习

    2019-07-22 23:58:58
    k-临近算法是通过对象本身的特征将对象划分到某一类型中去,比如电影中的题材类型的分类是,可能就会考虑到电影中出现的镜头出现的次数的多少将电影划分为动作电影,爱情电影等等,本次的随笔参考了《机器学习实战》...
  • 机器学习(5): k-近邻算法(kNN) 小结及实验

    千次阅读 多人点赞 2019-07-23 10:50:34
    k-近邻(k-Nearest Neighbor,kNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别...
  • 1.目前技能状态 主要做web开发,有一定的服务器项目部署经验,使用的数据库有:mysql/sqlite/redis   2.优点 精度高 对异常值不敏感 ...此算法的要点就是测量不同特征之间的距离(上面的公式是两个维度的计算公式...
  • K-临近算法 从今天开始,开始挖个坑。学习《机器学习实战》这本书,然后将学习的笔记记录下来。相关代码请参考: https://github.com/pbharrin/machinelearninginaction。里面有数据集和源码。但是这是基于python2...
  • 本文将从k-邻近算法的思想开始讲起,使用python3一步一步编写代码进行实战训练。并且,我也提供了相应的数据集,对代码进行了详细的注释。除此之外,本文也对sklearn实现k-邻近算法的方法进行了讲解。实战实例:电影...
  • K Nearest Neighbor算法又叫KNN算法,这个算法是机器学习里面一个比较经典的算法, 总体来说KNN算法是相对比较容易理解的算法 ***定义*** 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本...
  • 官方用书:机器学习实战(Machine Learning in Action) 好了,下面继续。 第2章主要讲述了k临近(k-NearestNeighbor)算法,所以关于算法本身的思想就不在赘述,不了解的同学请参考下面的百度百科链接:...
  • #-*-coding:utf-8-*- from numpy import * import operator import matplotlib import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D def file2matrix(filename): ...a
  • 1.什么是K临近算法 Cover 和 Hart在1968年提出了最初的临近算法 属于分类(classification)算法 邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。 所谓K最近...
  • 原理:采用测量不同特征值之间的距离进行分类. 计算复杂度:n*n 优点:精度高,对异常值不敏感,五数据输入假定.... 缺点:计算复杂度高,空间复杂度高. 适用数据范围:数值型和标称型 ...标称型:一般在有限的数据中取,而且只...
  • 今天我开始第一课--K临近算法。 一、k-临近的基础概念理解 学习开始前,我将用最简单的话来解释k-临近算法的思想。 K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器...
  • 机器学习系列笔记三:K近邻算法与参数调优[下] 文章目录机器学习系列笔记三:K近邻算法与参数调优[下]网格搜索超参 Grid Search数据归一化最值归一化Normalization均值方差归一化 Standardization对数据集进行归一化...
  • K-临近算法介绍和实践

    千次阅读 2017-11-23 09:55:47
    K-临近算法概述KNN算法(K-Nearest Neighbors)算法是机器学习领域广泛使用的分类算法之一,所谓KNN,说的就是每个样本的分类都可以用它最接近的K个邻居来代表...
  • 学习彭亮《深度学习基础介绍:机器学习》课程 最邻近规则分类(K-Nearest Nerghbor),KNN算法概念 是分类(classification)算法 步骤 为了判断未知实例的类别,以所有已知实例的类别作为参考 选取参数K,选取...
1 2 3 4 5 ... 20
收藏数 2,818
精华内容 1,127
关键字:

k 临近 机器学习