K-近邻算法(KNN)

基本信息
  外文名:k-NearestNeighbor
  中文名:k最邻近分类算法
  用途:用于分类、回归,对未知事物的识别。
工作原理
概述:
  如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
距离的计算方式:
  欧式距离、曼哈顿距离
图例说明:
    上图中,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。
优、缺点
优点:
  1、简单,易于理解,易于实现,无需估计参数,无需训练;
  2、适合对稀有事件进行分类;
  3、特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。
缺点:
  1、样本容量较小的类域采用这种算法比较容易产生误分。
    该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。
  2、该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。
  3、可理解性差,无法给出像决策树那样的规则。
算法实例
流程:
  1、计算距离
  2、选择距离最小的k个点
  3、通过投票方式,选择点最多的标签。
源码:
#-*- coding:utf-8 -*-
import numpy as np
import operator
def createDataset():
#四组二维特征
group = np.array([[5,115],[7,106],[56,11],[66,9]])
#四组对应标签
labels = (‘动作片’,’动作片’,’爱情片’,’爱情片’)
return group,labels
“””
KNN算法
“””
def classify(intX, dataSet, labels, k):
”’
numpy中shape[0]返回数组的行数,shape[1]返回列数
”’
dataSetSize = dataSet.shape[0]
“””
将intX在横向重复dataSetSize次,纵向重复1次
例如intX=([1,2])—>([[1,2],[1,2],[1,2],[1,2]])便于后面计算
“””
diffMat = np.tile(intX, (dataSetSize, 1)) – dataSet
“””
计算距离:欧式距离, 特征相减后乘方,然后再开方
“””
sqdifMax = diffMat**2
seqDistances = sqdifMax.sum(axis=1)
distances = seqDistances**0.5
#返回distance中元素从小到大排序后的索引
print (“distances:”,distances)
sortDistance = distances.argsort()
print (“sortDistance:”, sortDistance)
“””
取出前k个元素的类别
“””
classCount = {}
for i in range(k):
voteLabel = labels[sortDistance[i]]
s = “第{}个voteLabel={}”.format(i, voteLabel)
print(s)
classCount[voteLabel] = classCount.get(voteLabel,0)+1
#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
#计算类别次数
#key=operator.itemgetter(1)根据字典的值进行排序
#key=operator.itemgetter(0)根据字典的键进行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
#结果sortedClassCount = [(‘动作片’, 2), (‘爱情片’, 1)]
print (“sortedClassCount:”)
print(sortedClassCount)
return sortedClassCount[0][0]
if __name__ == ‘__main__’:
group,labels = createDataset()
test = [20,101]
test_class = classify(test,group,labels,3)
print (test_class)
运行结果 :
 
改进策略
  1、对样本属性进行约简。——删除对分类结果影响较小的属性。
  2、采用权值的方法(和该样本距离小的邻居权值大)来改进。——依照训练集合中各种分类的样本数量,选取不同数目的最近邻居,来参与分类。

发表评论

电子邮件地址不会被公开。 必填项已用*标注