Python实现KNN邻近算法

简介

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

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

本文将采用Python和numpy库实现KNN的核心算法,并使用一个简单的例子进行验证。

KNN核心算法的实现

对于KNN算法实现,首先我们计算欧式空间距离,然后根据距离排序,找到k个紧邻,找出最相近的分类。

from numpy import tile
import operator 

def do_knn_classifier(in_array, data_set, labels, k):
 '''''
 classify the in_array according the data set and labels
 ''' 

 #计算距离适量
 data_set_size = data_set.shape[0]
 diff_matrix = tile(in_array, (data_set_size, 1)) - data_set
 sq_diff_matrix = diff_matrix ** 2
 sq_distance = sq_diff_matrix.sum(axis=1)
 distances = sq_distance ** 0.5 

 #argsort函数返回的是数组值从小到大的索引值, 距离排序
 sorted_dist_indicies = distances.argsort() 

 # 选择K个紧邻
 class_count = {}
 for i in range(k):
 vote_label = labels[sorted_dist_indicies[i]]
 class_count[vote_label] = class_count.get(vote_label, 0) + 1 

 #排序,并返回最相邻的分类
 sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True) 

 return sorted_class_count[0][0]

数值的归一化

多数情况下,由于选择的特征值取值范围比较大。在处理这种不同取值范围的特征值时,通常需要采用的方法就是将数值归一化,如将取值范围处理到0到1或-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1的区间内的值:
newValue = (oldValue - min) / (max - min)
其中min和max分别是数据集中的最小特征值和最大特征值。

from numpy import tile
import operator 

def auto_normalize_data(data_set):
 '''''
 对数据集进行归一化操作
 '''
 # 参数0使函数可以从列中选取最小值,而不是当前行的最小值
 min_vals = data_set.min(0)
 max_vals = data_set.max(0)
 ranges = max_vals - min_vals 

 # 归一化处理
 m = data_set.shape[0]
 norm_data_set = data_set - tile(min_vals, (m, 1))
 norm_data_set = norm_data_set / tile(ranges, (m, 1)) 

 return norm_data_set, ranges, min_vals

实例

以一个简单的例子来结束本文的介绍。在这里并不需要实现数据的归一化处理。

from numpy import array
from knn.knn_classifier import do_knn_classifier 

def get_data_set():
 '''''
 Get data set and labels
 '''
 group = 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__':
 data_set, labels = get_data_set() 

 t = do_knn_classifier(array([0.2, 0.1]), data_set, labels, 3)
 print t 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python代码实现KNN算法

    kNN算法是k-近邻算法的简称,主要用来进行分类实践,主要思路如下: 1.存在一个训练数据集,每个数据都有对应的标签,也就是说,我们知道样本集中每一数据和他对应的类别. 2.当输入一个新数据进行类别或标签判定时,将新数据的每个特征值与训练数据集中的每个数据进行比较,计算其到训练数据集中每个点的距离(下列代码实现使用的是欧式距离). 3.然后提取k个与新数据最接近的训练数据点所对应的标签或类别. 4.出现次数最多的标签或类别,记为当前预测新数据的标签或类别. 欧式距离公式为: distance=

  • Python语言描述KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

  • python机器学习之KNN分类算法

    本文为大家分享了python机器学习之KNN分类算法,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距离,一

  • kNN算法python实现和简单数字识别的方法

    本文实例讲述了kNN算法python实现和简单数字识别的方法.分享给大家供大家参考.具体如下: kNN算法算法优缺点: 优点:精度高.对异常值不敏感.无输入数据假定 缺点:时间复杂度和空间复杂度都很高 适用数据范围:数值型和标称型 算法的思路: KNN算法(全称K最近邻算法),算法的思想很简单,简单的说就是物以类聚,也就是说我们从一堆已知的训练集中找出k个与目标最靠近的,然后看他们中最多的分类是哪个,就以这个为依据分类. 函数解析: 库函数: tile() 如tile(A,n)就是将A重复n次

  • 使用python实现knn算法

    本文实例为大家分享了python实现knn算法的具体代码,供大家参考,具体内容如下 knn算法描述 对需要分类的点依次执行以下操作: 1.计算已知类别数据集中每个点与该点之间的距离 2.按照距离递增顺序排序 3.选取与该点距离最近的k个点 4.确定前k个点所在类别出现的频率 5.返回前k个点出现频率最高的类别作为该点的预测分类 knn算法实现 数据处理 #从文件中读取数据,返回的数据和分类均为二维数组 def loadDataSet(filename): dataSet = [] labels

  • python机器学习实战之最近邻kNN分类器

    K近邻法是有监督学习方法,原理很简单,假设我们有一堆分好类的样本数据,分好类表示每个样本都一个对应的已知类标签,当来一个测试样本要我们判断它的类别是, 就分别计算到每个样本的距离,然后选取离测试样本最近的前K个样本的标签累计投票, 得票数最多的那个标签就为测试样本的标签. 源代码详解: #-*- coding:utf-8 -*- #!/usr/bin/python # 测试代码 约会数据分类 import KNN KNN.datingClassTest1() 标签为字符串 KNN.datingC

  • python实现kNN算法

    kNN(k-nearest neighbor)是一种基本的分类与回归的算法.这里我们先只讨论分类中的kNN算法. k邻近算法的输入为实例的特征向量,对对应于特征空间中的点:输出为实例的类别,可以取多类,k近邻法是建设给定一个训练数据集,其中的实例类别已定,分类时,对于新的实例,根据其k个最邻近的训练实例的类别,通过多数表决等方式进行预测.所以可以说,k近邻法不具有显示的学习过程.k临近算法实际上是利用训练数据集对特征向量空间进行划分,并作为其分类的"模型" k值的选择,距离的度量和分类

  • 以Python代码实例展示kNN算法的实际运用

    邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一.所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表. kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别. kNN方法在类别决策时,只与极少量的相邻样本有关.由于kNN方法主

  • 纯python实现机器学习之kNN算法示例

    前面文章分别简单介绍了线性回归,逻辑回归,贝叶斯分类,并且用python简单实现.这篇文章介绍更简单的 knn, k-近邻算法(kNN,k-NearestNeighbor). k-近邻算法(kNN,k-NearestNeighbor),是最简单的机器学习分类算法之一,其核心思想在于用距离目标最近的k个样本数据的分类来代表目标的分类(这k个样本数据和目标数据最为相似). 原理 kNN算法的核心思想是用距离最近(多种衡量距离的方式)的k个样本数据来代表目标数据的分类. 具体讲,存在训练样本集, 每个

  • Python KNN分类算法学习

    本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距

随机推荐