python实现最简单的机器学习算法之一-----K-近邻算法

比眉伴天荒 2022-06-06 03:48 164阅读 0赞

今天在刘峤的《知识图谱构建技术综述》看到了K-近邻算法：  
就进行了简单的了解；  
首先，我们来了解一下什么是K-近邻算法。

概念：所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

来个简单的案例介绍：  
有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。  
![这里写图片描述][SouthEast]  
我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：

如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。  
如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。  
于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

下面就来具体的代码：

1 #knn-k-最临近算法
     2 #inX为待分类向量，dataSet为训练数据集
     3 #labels为训练集对应分类，k最邻近算法
     4 def classify0(inX, dataSet, labels, k):
     5     dataSetSize = dataSet.shape[0]#获得dataSet的行数
     6     
     7     diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#对应的差值
     8     sqDiffMat = diffMat**2                           #差的平方
     9     sqDistances = sqDiffMat.sum(axis=1)              #差的平方的和
    10     distances = sqDistances**0.5                     #差的平方的和的平方根
    11     #计算待分类向量与每一个训练数据集的欧氏距离   
    12     
    13     sortedDistIndicies = distances.argsort() #排序后，统计前面K个数据的分类情况
    14     
    15     classCount={}#字典
    16     for i in range(k):
    17         voteIlabel = labels[sortedDistIndicies[i]]#labels得是字典才可以如此
    18         classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    19         
    20     sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)#再次排序
    21     
    22     return sortedClassCount[0][0]#第一个就是最多的类别

通俗一点就是：在一个特定的区域内，看所需要匹配的数据所占的全体集合的比例。

[SouthEast]: /images/20220606/a46ddfc1ab274e058d2da57b319dfe92.png