当前位置:   article > 正文

欧式聚类详解(点云数据处理)

欧式聚类

欧式聚类详解(点云数据处理)

欧式聚类是一种基于欧氏距离度量的聚类算法。基于KD-Tree的近邻查询算法是加速欧式聚类算法的重要预处理方法。

KD-Tree最近邻搜索

Kd-树是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构;Kd-树是一种平衡二叉树。为了能有效的找到最近邻,Kd-树采用分而治之的思想,即将整个空间划分为几个小部分。k-d树算法的应用可以分为两方面,一方面是有关k-d树本身这种数据结构建立的算法,另一方面是在建立的k-d树上如何进行最邻近查找的算法。
k-d tree是每个节点均为k维数值点的二叉树,其上的每个节点代表一个超平面,该超平面垂直于当前划分维度的坐标轴,并在该维度上将空间划分为两部分,一部分在其左子树,另一部分在其右子树。即若当前节点的划分维度为d,其左子树上所有点在d维的坐标值均小于当前值,右子树上所有点在d维的坐标值均大于等于当前值,本定义对其任意子节点均成立。
构建开始前,对比数据点在各维度的分布情况,数据点在某一维度坐标值的方差越大分布越分散,方差越小分布越集中。从方差大的维度开始切分可以取得很好的切分效果及平衡性。

KD-Tree构建原理

常规的k-d tree的构建过程为:循环依序取数据点的各维度来作为切分维度,取数据点在该维度的中值作为切分超平面,将中值左侧的数据点挂在其左子树,将中值右侧的数据点挂在其右子树。递归处理其子树,直至所有数据点挂载完毕。

KD-Tree近邻查询

给定点p,查询数据集中与其距离最近点的过程即为最近邻搜索
在这里插入图片描述
图中对于给定的查询数据点m,须从KD-Tree的根结点开始进行比较,其中m(k)为当前结点划分维度k上数据点m对应的值,d为当前结点划分的阈值。若 m(k)小于d,则访问左子树;否则访问右子树,直至到达叶子结点Q。此时Q就是当m前最近邻点,而m与Q之间的距离就是当前最小距离Dmin 。随后沿着原搜索路径回退至根结点,若此过程中发现和m之间距离小于 Dmin的点,则须将未曾访问过的子节点均纳入搜索范畴,并及时更新最近邻点,直至所有的搜索路径都为空,整个基于KD-Tree结构的最近邻点查询过程便告完成。

欧式聚类

在这里插入图片描述
对于欧式聚类来说,距离判断准则为前文提到的欧氏距离。对于空间某点P,通过KD-Tree近邻搜索算法找到k个离p点最近的点,这些点中距离小于设定阈值的便聚类到集合Q中。如果Q中元素的数目不在增加,整个聚类过程便结束;否则须在集合Q中选取p点以外的点,重复上述过程,直到Q中元素的数目不在增加为止。

《基于KDTree树和欧式聚类的越野环境下行人识别的研究》_范晶晶
https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/790144
推荐阅读
相关标签
  

闽ICP备14008679号