Python机器学习算法之KNN算法

KNN算法

1.算法概述

  • k最近邻算法(k-NearestNeighbor,kNN),顾名思义,即由某样本k个邻居的类别来推断出该样本的类别。
  • 给定测试样本,基于特定的某种距离度量方式找到与训练集中最接近的k个样本,然后基于这k个样本的类别进行预测。

2.算法步骤

Python机器学习算法之KNN算法

  1. 准备数据,对数据进行预处理
  2. 选用合适的测试元组和合适的数据存储结构训练数据
  3. 维护一个大小为k,按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列
  4. 遍历训练元组集,计算当前训练元组与测试元组的距离。之后将所得距离L与优先级队列中的最大距离L_max进行比较。若L≥L_max,则舍弃该元组,遍历下一个元组。若L<L_max,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列
  5. 遍历完毕后,计算优先级队列中k 个元组的多数类,并将其作为测试元组的类别
  6. 测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k值

3.算法实现

  • 自定义实现

    from numpy import *
    
    def createDataSet():
        # 构造训练集
        group = array([[90, 100], [88, 90], [85, 95], [10, 20], [30, 40], [50, 30]])
        # 样本点数据
        labels = ['A', 'A', 'A', 'D', 'D', 'D']
    
        return group, labels
    
    
    def KNNClassify(newInput, dataSet, labels, k):
        # 记录训练集个数
        nums = dataSet.shape[0]
    
        # 计算欧氏距离
        diff = tile(newInput, (nums, 1)) - dataSet  # 计算元素属性值得差
        squaredDiff = diff ** 2  # 对差值取平方
        squaredDist = sum(squaredDiff, axis=1)  # 按行求和
        distance = squaredDist ** 0.5  # 计算距离
    
        # 对距离进行排序(升序)
        sortedDistIndices = argsort(distance)
    
        classCount = {}
        for i in range(k):
            # 选择k个最短距离
            voteLabel = labels[sortedDistIndices[i]]
            # 记录累计的出现次数
            classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    
        # 投票数最多的分类
        maxCount = 0
        maxIndex = 0
    
        for key, value in classCount.items():
            if value > maxCount:
                maxCount = value
                maxIndex = key
    
        return maxIndex
    
    
    # 创建训练集和样本点
    dataSet, labels = createDataSet()
    
    # 测试集1
    testX = array([15, 50])
    k = 3
    outputLabel = KNNClassify(testX, dataSet, labels, k)
    print("第一组测试数据为:", testX, ",分类结果为:", outputLabel)
    
    # 测试集2
    testX = array([80, 70])
    k = 3
    outputLabel = KNNClassify(testX, dataSet, labels, k)
    print("第二组测试数据为:", testX, ",分类结果为:", outputLabel)
    
  • 利用Sklearn库实现

    from sklearn import neighbors, datasets
    
    # 初始化K近邻分类器
    knn = neighbors.KNeighborsClassifier()
    
    # 加载数据集
    iris = datasets.load_iris()
    print(iris)
    
    # 讲训练数据集和标签种类进行归类学习
    knn.fit(iris.data, iris.target)
    
    # 测试样本预测
    predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])
    print(predictedLabel)
    

4.算法优化

  • 引入邻居权值

    为了优化KNN的分类效果,可以在其中引入权值机制作为对样本距离机制的补充。

    基本思想是:为与测试样本距离更小的邻居设置更大的权值,衡量权值累积以及训练样本集中各种分类的样本数目,来对算法中的K值进行调整,进而达到更合理或者平滑的分类效果。

  • 特征降维与模式融合

    KNN算法的主要缺点是,当训练样本数量很大时将导致很高的计算开销。

    为了对KNN的分类效率进行优化,可以在数据预处理阶段利用一些降维算法或者使用特征融合算法,对KNN训练样本集的维度进行简化,排除对分类结果影响较小的属性。通过优化训练样本集的分类,提高得出待分类样本类别的效率。该改进经常在类域的样本容量比较大时使用。

上一篇:CGAN的基本理论和代码


下一篇:深度学习之新闻多分类问题