k-近邻算法

机器学习实战

废话

在实际工作中，我们经常会碰到需要对一些数据进行简单分类，举几个例子：

• 我们经常会对一些评论内容进行情感分析，分析出评论内容是高兴、悲伤、表扬或是批评；
• 在医疗行业我们会对一些患者的医学影响进行分析，分析出该患者是几级伤残、是否患有癌症、癌症程度等等；
• 在音乐方面我们要对音乐进行归类，分析出该音乐属于经典、民谣、流行、伤感中的哪一种；
• 垃圾邮件过滤；
• 在电影方面我们要对电影属于爱情片、动作片、科幻片中的哪一种进行分类；
• 在视频直播中需要对视频直播中的内容进行分类，以更加准确的监控直播内容的合法性；

那么今天给大家介绍的k-近邻算法是分类数据最简单、最基础、最有效的算法。

概述

k-近邻即kNN（k-NearestNeighbor）k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。

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

场景

我们回到上面将电影分类的例子中， 我们想一想爱情片和动作片中哪些特点会有明显的不同。kiss镜头数、打斗镜头数是两种类型电影里很明显的差异，那么我们将kiss镜头数和打斗镜头数作为区分两种类型影片的依据之一。

数据准备

有了上面的场景分析，我们要对两种类型的电影进行区分，就需要对大量的已知分类电影数据进行标注，形成我们的标注数据。

电影名称	打斗镜头数	kiss镜头数	电影类型
California Man	3	104	爱情片
He 's Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
RoboSlayer 3000	99	5	动作片
Amped II	98	2	动作片
？	18	90	？

通过以上表格很清晰的发现，爱情片中kiss镜头数明显较多，而动作片中打斗镜头数明显较多，同时我们要分析的则是打斗镜头数为18，kiss镜头数为90的影片类型是什么？

代码实现

1.首先进行数据准备
 '''
  基础数据
 '''
def createDataSet():
group = arry([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
return group,labels

'''
分类算法
:param inX:分类输入向量，即[18,90] 
:param dataSet:准备的矩阵数据集
:param labels:对应影片类型
:param k:最邻近数目
: return:分类类型
'''
def classify(inX,dataSet,labels,k) :
    dataSetSize = dataSet.shape[0]#获取矩阵长度6
    #1.在列方向上重复6次，行上一次，即arry([[18,90],[18,90],[18,90],[18,90],[18,90],[18,90]])
    #2.两个矩阵相减
    diffMat = tile(inX,(dataSet,1))-dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)#矩阵的平方
    distances = sqDistances**0.5#开根号
    sortedDistIndicies = distances.argsort()#返回distances从小到大的索引值
    classCount = {}
    #选择距离最小的几个点
    for i in range(k) :
        voteILabel = labels[sortedDistIndicies[i]]#输出对应索引的类型
        classCount[voteILabel] = classCount.get(voteILabel,0)+1#向字典添加该类型
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0] #返回前3个近邻对应类型出现最多的类型名称

group,labels=createDataSet()
print(classify([18,90],group,labels,3))

###输出结果为“爱情片”

在classify函数中影片距离是通过了欧式距离公式进行计算,当然计算距离的方式还有“编辑距离“、“余弦相似度”等等，根据应用场景选择相应的计算公式。

欧式距离公式 ：d = √(x1-x2)² +(y1-y2)²

| 电影名称 | 与未知电影距离 |
| :-----------: | :------------: | :-------------: | :----------------: |
| California Man | 20.5 |
| He 's Not Really into Dudes | 18.7 |
| Beautiful Woman | 19.2 |
| Kevin Longblade | 115.3 |
| RoboSlayer 3000 | 117.4 |
| Amped II | 118.9 |

总结

在分类算法中，kNN是最简单也是最有效的算法，但也有很多缺点，我们在使用时必须有接近实际数据的训练样本数据，同时训练数据过大时会消耗大量的计算时间，因为要跟每个数据进行距离的计算。所以每种算法在时间或空间上都有自己的优缺点，大家在选择分类算法时还得根据具体的业务场景和需要选择适合的算法。