机器学习之KNN(k-nearest-neighbor)算法
knn算法简介
有句话叫近墨者黑近朱者赤,就是你是啥样的人,看看你周围的人就知道了。其实kNN算法从原理上和这个是一致的,这里的k指的是离需要预测的点的最近的k个实例。当我们采用knn算法进行训练的时候,所有的训练集数据都是算法的参数,这也叫做无参数模型。模型训练出来之后,将需要预测的点和其最近的k个点进行比较。如果做分类,就是这k个中类别最多的类型作为结果,如果是回归,可以采用k个实例的均值。
给定一个训练集
算法
1. 根据给定的距离计算公式,在训练集中,找出与x最近的k个点,组成一个集合,记为:
2. 根据决策规则,决定x的类别,一般采用多数表决法。
其中
如下图所示,如果k=4,取该点最近的4个点,决策规则为多数表决,则该点被判断为红色:
kd树
kNN算法总体来说很简单的,没有任何的难度。关键点在于计算一个点周围的k个点,如果数据很少的情况,比如只有几万条,那你随便用啥排序算法都搞定了;如果是几亿条记录呢?那不死翘翘了。
所以如何搜索一个点周围的k个点?让人想到了索引,b+树之类的东东。在多维空间中搜索,采用的是kd树进行存储已有的训练集数据,便于查找新的点的k个数据。
训练数据:
构造kd树的算法如下:
1. 从第一个特征开始,找到数据集在第一个特征的中位数,然后将小于中位数的放在结点左边,反之放右边。
2. 对于其他的特征依次重复第一个步骤,其中树的深度为
可以将特征想象成一个环,从第一特征进行划分,依次执行。
3. 直到叶子结点只有一个元素
如下图所示:
最后点被如下的切分:
不断的进行空间的切分,直到每一个样本点。
kd树构造好了,就可以采用这一数据结构进行搜索了。至于如何搜索,就留给读者吧。哈哈哈哈