深圳市建设局官方网站,刚刚刚刚刚刚刚刚刚刚刚刚刚刚刚,短视频赚钱app软件,做推广哪个网站好本内容将介绍机器学习中的 k k k 近邻法#xff08; k k k-NN#xff09; 的原理及暴力和 k d kd kd 树实现。
一、 k k k 近邻算法介绍 k k k 近邻法#xff08;K-nearest neighbor, k k k-NN#xff09;1968 年由 Cover 和 Hart 提出#xff0c;是一种基本分类与回… 本内容将介绍机器学习中的 k k k 近邻法 k k k-NN 的原理及暴力和 k d kd kd 树实现。
一、 k k k 近邻算法介绍 k k k 近邻法K-nearest neighbor, k k k-NN1968 年由 Cover 和 Hart 提出是一种基本分类与回归方法。使用 k k k 近邻法进行分类预测时对新的实例根据其 k k k 个最近邻的训练实例的类别通过多数表决法等方式进行预测这 k k k 个实例的多数属于某个类就把该新实例分为这个类。因此 k k k 近邻法不具有显式的学习过程。 k k k 近邻法实际上利用训练数据集对特征向量空间进行划分并作为其分类的“模型”。 k k k 近邻法进行分类和回归预测的主要区别进行预测时的决策方式不同。进行分类预测时通常采用多数表决法而进行回归预测时通常采用平均法。由于两者区别不大所以本内容仅介绍使用 k k k 近邻进行分类预测。
二、 k k k 近邻模型 k k k 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、 k k k 值的选择和分类决策规则决定。
2.1 距离度量 特征空间中两个实例点的距离是两个实例点相似程度的反映。 k k k 近邻模型的特征空间一般是 n n n 维实数向量空间 R n \mathbf R^n Rn。通常使用的距离是欧式距离但也可以选择其他距离如更一般的 L p L_p Lp 距离 L p L_p Lp distance或 Minkowski 距离Minkowski distance。 设特征空间 X \mathcal X X 是 n n n 维实数向量空间 R n \mathbf R^n Rn x i , x j ∈ X x_i,x_j\in\mathbf X xi,xj∈X x i ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( n ) ) T x_i(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T xi(xi(1),xi(2),⋯,xi(n))T x i ( x j ( 1 ) , x j ( 2 ) , ⋯ , x j ( n ) ) T x_i(x_j^{(1)},x_j^{(2)},\cdots,x_j^{(n)})^T xi(xj(1),xj(2),⋯,xj(n))T x i , x j x_i,x_j xi,xj 的 L P L_P LP 距离定义为 L p ( x i , x j ) ( ∑ l 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_p(x_i,x_j)\Big(\sum_{l1}^{n}|x_i^{(l)}-x_j^{(l)}|^p\Big)^{\frac{1}{p}} Lp(xi,xj)(l1∑n∣xi(l)−xj(l)∣p)p1 这里 p ≥ 1 p\geq1 p≥1。当 p 2 p2 p2 时称为欧式距离Euclidean distance当 p 1 p1 p1 时称为曼哈顿距离Manhattan distance。
2.2 k k k 值的选择 k k k 值的选择会对 k k k 近邻法的结果产生重大影响。 如果选择较小的 k k k 值就相当于用较小的邻域中的训练实例进行预测训练误差会减小只有与输入实例较近的相似的训练实例才会对预测结果起作用。但缺点是泛化误差会增大预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声预测就会出错。 如果选择较大的 k k k 值就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少泛化误差。但缺点是训练会增大。这时与输入实例较远的不相似的训练实例也会对预测起作用是预测发生错误。 如果 k k k N那么无论输入什么实例都将简单地预测它属于在训练实例中最多的类。这是不可取的。 在应用中 k k k 值一般取一个较小的数值通常为小于 20 的整数。通常采用交叉验证法来选取最优的 k k k 值。
2.3 分类决策规则 k k k 近邻法中的分类决策规则通常采用多数表决法即由输入实例的 k k k 个邻近的训练实例中的多数类决定实例的类。
三、 k k k 近邻法的实现 实现 k k k 近邻法时主要考虑的问题是如何对训练数据进行快速 k k k 近邻搜索。
3.1 暴力实现 首先计算输入实例与训练集中所有实例的距离然后采用线性扫描方法找出最小的 k k k 个距离最后采用多数表决法进行预测。这种方法非常简单当训练集样很小时可以采用。但是当训练集很大时计算会非常耗时不能采用。 Python 代码实现如下
import numpy as np
import operatorclass KNNClassification:def __init__(self, method):self.method methodself.train_data_set Nonepass# 加入测试数据集def fit(self, train_data_set):self.train_data_set train_data_setpass# 对测试实例进行预测def predict(self, k, test_data):# 计算两点之间的欧式距离def euclidean_dist(vec01, vec02):mat_vec01 np.mat(vec01)mat_vec02 np.mat(vec02)return np.sqrt((mat_vec01-mat_vec02)*(mat_vec01-mat_vec02).T)# 查找出最近的 k 个近邻def get_k_nearest_neighbors(train_data_set, k, test_data):distances []# 计算测试实例与训练集中的所有实例的欧式距离for x in range(len(train_data_set)):dist euclidean_dist(test_data[0], train_data_set[x][0])distances.append((train_data_set[x], dist))# 进行排序distances.sort(keyoperator.itemgetter(1))neighbors []for x in range(k):neighbors.append(distances[x][0])return neighbors# 从 k 个近邻中返回数量最大的typedef get_type(neighbors):class_votes {}for x in range(len(neighbors)):type neighbors[x][-1]if type in class_votes:class_votes[type] 1else:class_votes[type] 1# 排序对字典 sorted_votes 中的第二个字符进行排序即对 value 排序sorted_votes sorted(class_votes.items(), keyoperator.itemgetter(1), reverseTrue)return sorted_votes[0][0]if self.train_data_set is None:return Noneneighbors get_k_nearest_neighbors(self.train_data_set, k, test_data)return get_type(neighbors)if __name__ __main__:data_set np.array([[[2, 3], 1],[[5, 4], 1],[[9, 6], 0],[[4, 7], 1],[[8, 1], 0],[[7, 2], 0]])# 实例化一个 KNN 分类器KNN KNNClassification(BruteForce)KNN.fit(data_set)# 进行预测predict_type KNN.predict(3, [[6, 6], 1])print(predict_type)predict_type KNN.predict(3, [[10, 4], 0])print(predict_type)为了提高 k k k 近邻搜索的效率需要考虑使用特殊的结构存储训练数据。实现的方法有很多下面将介绍其中的一种 k d kd kd 树实现。
3.2 k d kd kd 树实现 k d kd kd 树是一种对 k k k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 k d kd kd 树是二叉树表示对 k k k 维空间的一个划分partition。构造 k d kd kd 树相当于不断地用垂直于坐标轴的超平面将 k k k 维空间划分构成一系列的 k k k 维超矩形区域。 k d kd kd 树的每个结点对应于一个 k k k 维超矩形区域。
3.2.1 构造 k d kd kd 树 构造 k d kd kd 树的方法构造根结点使根结点对应于 k k k 维空间中包含所有实例点的超矩形区域通过下面的递归方法不断地对 k k k 维空间进行切分生成子结点当子结点内没有实例时结束。 具体递归方法在超矩形区域父结点上选择一个坐标轴和在此坐标轴上的一个切分点确定一个超平面这个超平面通过选定的切分点并垂直于选定的坐标轴通过这个超平面将当前超矩形区域分为左右两个子区域子结点左子结点对应小于切分点的子区域右子结点对应大于切分点的子区域落在超平面上的实例点保存在父结点。 上面的选定坐标轴实际上就是选定一个实例特征。坐标轴选择方法通常是轮流选择所有特征也可以选择当前超矩形区域中方差最大的特征。切分点选择方法选择当前超矩形区域中所有实例在选定特征上的中位数将实例按照选定特征值大小进行排序出在中间位置的特征值或者中间两个的平均值。 假如我们存在这样一个二维空间的数据集 T { ( 2 , 3 ) T , ( 5 , 4 ) T , ( 9 , 6 ) T , ( 4 , 7 ) T , ( 8 , 1 ) T , ( 7 , 2 ) T } T\{(2,3)^T,(5,4)^T,(9,6)^T,(4,7)^T,(8,1)^T,(7,2)^T\} T{(2,3)T,(5,4)T,(9,6)T,(4,7)T,(8,1)T,(7,2)T}构造 k d kd kd 树的具体步骤根结点对应包含数据集 T T T 的矩形选择 x x x 轴中位数为 7即确定分割平面为 x 7 x7 x7。 { ( 2 , 3 ) , ( 4 , 7 ) , ( 5 , 4 ) } \{(2,3),(4,7),(5,4)\} {(2,3),(4,7),(5,4)} 分入左子区域 { ( 8 , 1 ) , ( 9 , 6 ) } \{(8,1),(9,6)\} {(8,1),(9,6)} 分入右子区域。用同样的方法分别划分左右子区域最终得到如下的特征空间划分和 k d kd kd 树 图特征空间划分 图 k d kd kd 树 Python 代码实现如下
class KdNode:def __init__(self, sample, order, parent):self.sample sample # 保存在该结点中的实例点self.order orderself.parent parentself.left None # 左子结点self.right None # 右子结点passdef set_child(self, left, right):self.left leftself.right rightclass KdTree:def __init__(self, date_set):self.root self.create_kd_tree(date_set)pass# 创建 kd 树def create_kd_tree(self, data_set):return self.create_node(data_set, 0, None)# 创建 kd 树的结点def create_node(self, data_set, order, parent):if len(data_set) 0:return None# 对数据集进行排序data_set sorted(data_set, keylambda x: x[order])# 获取中位数位置split_pos len(data_set) // 2median data_set[split_pos]order_next (order1) % (len(data_set[0]))node KdNode(median, order, parent)left_child self.create_node(data_set[:split_pos], order_next, node)right_child self.create_node(data_set[split_pos1:], order_next, node)node.set_child(left_child, right_child)return node3.2.2 搜索 k d kd kd 树 下面以最近邻为例进行介绍同样的方法可以应用到 k k k 近邻。在 k d kd kd 树中搜索最近邻步骤
在 k d kd kd 树中找到包含目标点的叶结点并将此叶结点保存的实例点作为“当前最近点”。具体查找方法从根结点出发递归地向下访问 k d kd kd 树若目标点当前维的值小于切分点的值则移动到左子结点否则移入右子结点直到子结点为叶结点为止。向上返回到父结点如果父结点保存的实例点比“当前最近点”距离目标点更近则将父结点保存的实例点作为“当前最近点”。以目标点为圆心以目标点到“当前最近点”的距离为半径得到一个超球体检查父结点的另一个子结点对应的超矩形区域是否与此超球体相交。如果相交就在这个子结点中查找是否存在更近的实例点如果有就更新“当前最近点”。不断执行步骤 2直到返回到父结点结束。 通过上面的描述我们可以看到利用 k d kd kd 树可以省去对大部分实例点的搜索从而减少搜索的计算量。 如果实例点是随机分布的 k d kd kd 树搜索的平均计算复杂度是 O ( l o g N ) O(logN) O(logN)这是 N N N 是训练实例树。 k d kd kd 树更适用于训练实例树远大于空间维数时的 k k k 近邻搜索。当空间维数接近训练实例树时它的效率会迅速下降几乎接近线性扫描。
参考
[1] 李航《统计学习方法》
[2] https://www.cnblogs.com/pinard/p/6061661.html
[3] https://www.cnblogs.com/21207-iHome/p/6084670.html
[4] https://blog.csdn.net/gamer_gyt/article/details/51232210
