KNN算法


作者 李智慧

KNN算法,即K近邻(K nearest neighbour)算法,是一种基本的分类算法。其主要原理是:对于一个待分类的数据,将其和一组已经分类标注好的样本集合进行比较,得到距离最近的K个样本,K个样本最多归属的类别,就是待分类数据的类别。其原理如下图:

image

图中,红蓝绿三种颜色的点为样本数据,分属三种类别 w{1} 、 w{2} 、 w{3} 。对于待分类点 X{u} ,计算和它距离最近的5个点(即K为5),这5个点最多归属的类别为 w{1} (4个点归属w{1} ,1个点归属 w{3} ),那么 X{u} 的类别预测为 w_{1} 。

KNN算法是一种非常简单实用的分类算法,可用于各种分类的场景,比如新闻分类、商品分类等,甚至可用于简单的文字识别。KNN的算法流程也非常简单,如下图:

image

空间距离

KNN算法的关键是要比较待分类数据与样本数据之间的距离,机器学习中通常的做法是:提取数据的特征值,根据特征值组成一个n维实数向量空间(这个空间也被称作特征空间),然后计算向量之间的空间距离。空间之间的距离计算方法有很多种,常用的有欧氏距离、余弦距离等。

对于数据 x_{i}x_{j} ,若其特征空间为n维实数向量空间 image

image, image ,则其欧式距离的计算公式为:

image

在文本数据的机器学习中,更常用的距离计算方法是余弦相似度:

image

余弦相似度的值越接近1表示其越相似,越接近0表示其差异越大,使用余弦相似度可以消除数据的某些冗余信息,某些情况下更贴近数据的本质。

文本特征 机器学习的算法需要计算距离,计算距离需要知道数据的特征向量,因此提取数据的特征向量是机器学习工程师们的重要工作,有时候甚至是最重要的工作。不同的数据以及不同的应用场景需要提取不同的特征值,我们以比较常见的文本数据为例,看如何提取文本特征向量。

文本数据提取特征值就是提取文本关键词,TF-IDF算法是比较常用又直观的一种文本关键词提取算法。算法由TF和IDF两部分构成。

词频:

image

逆文档频率:

image

词频TF(term frequency)表示某个单词在该文档中出现的频率,一个单词在一个文档中出现的越频繁,TF值越高。逆文档频率IDF(inverse document frequency)表示该单词在所有文档中的稀缺程度,越少文档出现这个词,IDF值越高。TF与IDF的乘积就是TF-IDF。

image

所以如果一个词在某个文档中出现的很频繁,而在所有文档中出现的不频繁,那么这个词很可能就是这个文档的关键词。比如一篇关于原子能的技术文章,『核裂变』、『放射性』、『半衰期』等词汇会在这篇文档中频繁出现,即TF很高;但是在所有文档中出现的频率却比较低,即IDF也比较高,这些词的TF-IDF值就会很高,就可能是文档的关键词。如果这是一篇关于中国原子能的文章,也许『中国』这个词也会频繁出现,即TF也很高,但是『中国』会在大多数文档中出现,那么IDF就会比较低,最后『中国』这个词的TF-IDF就很低,不会成为文档的关键词。

提取出关键词以后,就可以利用关键词的词频构造特征向量,再利用前面提到的空间距离计算公式计算与其他文档的距离,结合KNN算法就可以实现文档的自动分类。

https://zhuanlan.zhihu.com/p/35529612?group_id=969600589810802688