南宁网站建设找建站通,上海企业营销型网站建设,有哪些网站可以做家教,优秀包装设计案例距离度量
欧氏距离(Euclidean distance) 欧几里得度量#xff08;Euclidean Metric#xff09;#xff08;也称欧氏距离#xff09;是一个通常采用的距离定义#xff0c;指在#x1d45a;维空间中两个点之间的真实距离#xff0c;或者向量的自然长度#xff08;即该点…距离度量
欧氏距离(Euclidean distance) 欧几里得度量Euclidean Metric也称欧氏距离是一个通常采用的距离定义指在维空间中两个点之间的真实距离或者向量的自然长度即该点到原点的距离。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
曼哈顿距离(Manhattan distance) 想象你在城市道路里要从一个十字路口开车到另外一个十字路口驾驶距离是两点间的直 线距离吗显然不是除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源 曼哈顿距离也称为城市街区距离(City Block distance)
切比雪夫距离(Chebyshev distance) 二个点之间的距离定义是其各坐标数值差绝对值的最大值。国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。
闵可夫斯基距离(Minkowski distance) 取1或2时的闵氏距离是最为常用的 2即为欧氏距离 1时则为曼哈顿距离。 当取无穷时的极限情况下可以得到切比雪夫距离
汉明距离(Hamming distance) 汉明距离是使用在数据传输差错控制编码里面的汉明距离是一个概念它表示两个相同长度字对应位不同的数量我们以表示两个字之间的汉明距离。对两个字符串进行异或运算并统计结果为1的个数那么这个数就是汉明距离。
余弦相似度
两个向量有相同的指向时余弦相似度的值为1两个向量夹角为90°时余弦相似度的值为0两个向量指向完全相反的方向时余弦相似度的值为-1。 假定和是两个维向量是 1, 2, … , 是1,2, … , 则和的夹角的余弦等于
KNN算法
近邻法k-Nearest Neighbor,kNN是一种比较成熟也是最简单的机器学习算法可以用于基本的分类与回归方法。
算法的主要思路
如果一个样本在特征空间中与个实例最为相似(即特征空间中最邻近)那么这个实例中大多数属于哪个类别则该样本也属于这个类别。 对于分类问题 对新的样本根据其个最近邻的训练样本的类别通过多数表决等方式进行预测。 对于回归问题 对新的样本根据其个最近邻的训练样本标签值的均值作为预测值
近邻法的三要素
• 值选择。 • 距离度量。 • 决策规则。
算法流程
1.计算测试对象到训练集中每个对象的距离 2.按照距离的远近排序 3.选取与当前测试对象最近的k的训练对象作为该测试对象的邻居 4.统计这k个邻居的类别频次 5.k个邻居里频次最高的类别即为测试对象的类
以上图中绿点位置的分类问题为例图中有正方形和三角形两类K3即选取距离绿点最近的三个对象这三个对象中三角形的类别较多因此将绿点位置归为三角形类而当K5时选取距离绿点位置最近的五个对象此时正方形的数量较多则此时绿点为正方形类
KD树划分
KD树(K-Dimension Tree)也可称之为K维树可以用更高的效率来对空间进行划分并且其结构非常适合寻找最近邻居和碰撞检测。 假设有 6 个二维数据点构建KD树的过程 (2,3), (5,7), (9,6), (4,5), (6,4), (7,2) 。 ①从轴开始划分根据轴的取值2,5,9,4,6,7得到中位数为6 因此切分线为 6 。 ②可以根据轴和轴上数据的方差选择方差最大的那个轴作为第一轮划分轴。 左子空间记做 1包含点 (2,3),(4,5),(5,7)切分轴轮转从轴开始划分切分线为 5 右子空间记做 2 包含点 (9,6),(7,2)切分轴轮转从轴开始划分切分线为 6 。 ③1的左子空间记做 3包含点(2,3)切分轴轮转从x 轴开始划分切分线为 2。 其左子空间记做 7 右子空间记做 8 。由于 7,8都不包含任何点因此对它们不再继续拆分。 1 的右子空间记做 4 包含点(5,7)切分轴轮转从x 轴开始划分切分线为 5。 其左子空间记做 9右子空间记做 10 。由于9,10都不包含任何点因此对它们不再继续拆分。 ④2的左子空间记做 5 包含点(7,2)切分轴轮转从x 轴开始划分切分线为 7。 其左子空间记做 11右子空间记做 12 。由于11,12 都不包含任何点因此对它们不再继续拆分。 2的右子空间记做 6不包含任何点停止继续拆分。
KD树搜索
1.首先要找到该目标点的叶子节点然后以目标点为圆心目标点到叶子节点的距离为半径建立一个超球体我们要找寻的最近邻点一定是在该球体内部。 搜索4,4的最近邻时。首先从根节点6,4出发将当前最近邻设为6,4对该KD树作深度优先遍历。以4,4为圆心其到6,4的距离为半径画圆多维空间为超球面可以看出7,2右侧的区域与该圆不相交所以7,2的右子树全部忽略。 2.返回叶子结点的父节点检查另一个子结点包含的超矩形体是否和超球体相交如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。 接着走到6,4左子树根节点4,5与原最近邻对比距离后更新当前最近邻为4,5。以4,4为圆心其到4,5的距离为半径画圆发现6,4右侧的区域与该圆不相交忽略该侧所有节点这样6,4的整个右子树被标记为已忽略 3.如果不相交直接返回父节点在另一个子树继续搜索最近邻。 4.当回溯到根节点时算法结束此时保存的最近邻节点就是最终的最近邻。遍历完4,5的左右叶子节点发现与当前最优距离相等不更新最近邻。所以4,4的最近邻为4,5。
