Python之K最近邻算法

- 日理万妓 2022-02-19 00:09 321阅读 0赞

**K最近邻（k-nearest neighbours，KNN）算法：**  
是指给定一个训练数据集，将新输入的实例，在训练数据集中找到与该实例最邻近的K个实例（K表示指定的最近邻的数量，K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

**关于K的经验规则是**：如果有N位用户，应考虑sqrt(N)个邻居。

**KNN算法用于分类和回归，需要考虑最近的邻居：**  
1、分类就是编组；  
2、回归就是预测结果（如一个数字）。

**特征提取：**  
1、将物品（如水果或用户）转换为一系列可比较的数字。  
2、挑选合适的特征，必须考虑到各种需要考虑的因素。  
3、能否挑选合适的特征事关KNN算法的成败。

**计算相似度（余弦相似度更好）：公式有很多，根据需求选择**  
1、勾股定理（毕达哥拉斯公式，√为平方根在计算机中的显示符号）：计算两点的距离，√(a₁-a₂)²+(b₁-b₂)²。  
2、余弦相似度（cosine similarity）：是通过计算两个向量的夹角余弦值来评估他们的相似度。  
3、朴素贝叶斯分类器（Naive Bayes classifier）：用于获得目标概率值的方法。

**例：影片推荐系统，值为喜爱度**

黄一		赵二		张三		李四		王五		刘六（待测人）
    喜剧片		  3 	  4 	  2 	  3 	  3 	  4
    动作片		  4 	  3 	  5       4 	  5 	  4
    生活片		  4 	  5 	  1 	  2 	  1 	  1
    恐怖片		  1 	  1 	  3 	  4 	  5 	  5
    爱情片		  4 	  5 	  1 	  1 	  1 	  1
    最终结果为：[5.9, 7.0, 3.0, 1.7, 1.4]，刘六与李四、王五的值差距最小，判断他们的喜好更相似。

# 分类
    import math
    
    # 计算2人的距离（非实际距离）
    def knn(one, two):
    	res = [] 										#最终各人对比距离
    	for ren in two: 								#各人依次对比
    		zhi = 0
    		for i in range(length):
    			zhi += math.pow((one[i]-ren[i]), 2)     #pow(x, y)返回x的y次幂
    		result = math.sqrt(zhi)						#sqrt(x)返回x的平方根
    		res.append((result, zhi))
    	return res
    
    # 各人对各类影片的喜爱度，中文也可做变量名
    黄一 = [3, 4, 4, 1, 4]
    赵二 = [4, 3, 5, 1, 5]
    张三 = [2, 5, 1, 3, 1]
    李四 = [3, 4, 2, 4, 1]
    王五 = [3, 5, 1, 5, 1]
    刘六 = [4, 4, 1, 5, 1]
    
    # 多个参照物
    num = [黄一, 赵二, 张三, 李四, 王五]
    
    length = len(刘六)
    print(knn(刘六, num))

**结果为：**

[(5.916079783099616, 35.0), (7.0, 49.0), (3.0, 9.0), (1.7320508075688772, 3.0), (1.4142135623730951, 2.0)]

**回归（预测）：K个最近邻的值相加，再平分即是预测结果。**  
如：根据5个最近邻的打分预测刘六的打分

黄一 = 5	
    赵二 = 4	
    张三 = 4	
    李四 = 5	
    王五 = 4
    
    刘六 = (黄一 + 赵二 + 张三 + 李四 + 王五)/5
    print(刘六)

**结果为：**

4.4