人工智能机器学习深度学习【免费下载链接】mlpackmlpack: a fast, header-only C machine learning library项目地址https://gitcode.com/gh_mirrors/ml/mlpack点击查看免费下载MeanSplitBallTree是 mlpack 中基于球ball边界的二叉空间划分树专为低到中等维度下的高效距离查询如k近邻搜索而设计。本文以 mlpack 官方文档为骨架结合仓库源码深入讲解其模板参数、构造函数、节点属性、距离边界函数、树遍历器与完整可运行的示例代码帮助你掌握这一树结构从构建到实际应用的全链路用法。概述MeanSplitBallTree 与 BallTree 的异同MeanSplitBallTree是一种k维二叉空间划分树每个节点用一个球BallBound包围其下属的所有点。它是著名的用于高效距离运算如 KNN 近邻搜索的数据结构在低到中等维度下表现出色。与BallTree相比两者使用相同的BallBound边界结构但切分策略不同MeanSplitBallTree使用MeanSplit策略在方差实际为边界宽度最大的维度上以该维度均值作为切分点BallTree使用MidpointSplit策略在最大宽度维度上以中点切分。一般来说MeanSplitBallTree的树会更平衡、节点数更少。但一个反直觉的事实是更平衡的树在搜索任务如最近邻搜索中可能更差因为不平衡的节点更容易在搜索过程中被整体剪枝prune掉。因此多数数据集上使用BallTree做最近邻搜索更快但这并非对所有数据集和任务都成立——实际选型时应基于具体数据测试。从源码结构看MeanSplitBallTree只是通用BinarySpaceTree模板的一个便捷 typedef位于 src/mlpack/core/tree/binary_space_tree/typedef.hpptemplatetypename DistanceType EuclideanDistance, typename StatisticType EmptyStatistic, typename MatType arma::mat using MeanSplitBallTree BinarySpaceTreeDistanceType, StatisticType, MatType, BallBound, MeanSplit;即它等价于BinarySpaceTreeDistanceType, StatisticType, MatType, BallBound, MeanSplit。下面这张图展示了 mlpack 中球边界BallBound的几何含义——每个树节点用圆心加半径包围其全部后代点它是本文所有距离边界计算的几何基础模板参数遵循 TreeType API 模板参数要求更详细的说明见 TreeType 模板参数章节MeanSplitBallTree接受三个模板参数MeanSplitBallTreeDistanceType, StatisticType, MatType参数含义默认值DistanceType用于距离计算的距离度量见 distancesEuclideanDistanceStatisticType每个树节点中保存的辅助信息默认EmptyStatistic不保存任何信息EmptyStatisticMatType表示点的矩阵类型必须是符合 Armadillo API 的类型arma::matarma::fmat等亦可如果不显式指定模板参数则使用全部默认值MeanSplitBallTree MeanSplitBallTreeEuclideanDistance, EmptyStatistic, arma::matMeanSplit切分策略的源码位于 mean_split.hpp 与 mean_split_impl.hpp。其SplitNode实现逻辑是遍历各维度找出边界宽度或数据实际范围宽度最大的维度splitDimension然后在该维度上计算所有点的算术均值作为splitVal再通过AssignToLeftNode将point[splitDimension] splitVal的点分配到左子树// src/mlpack/core/tree/binary_space_tree/mean_split_impl.hpp // 找到最大宽度的维度 for (size_t d 0; d data.n_rows; d) { const double width bound[d].Width(); if (width maxWidth) { maxWidth width; splitInfo.splitDimension d; } } // 在该维度上按均值切分 splitInfo.splitVal 0.0; for (size_t i begin; i begin count; i) splitInfo.splitVal data(splitInfo.splitDimension, i); splitInfo.splitVal / count;当所有点在该维度上都相同时maxWidth 0节点无法切分返回false使其成为叶子节点。这正是文档所述“均值切分”与MidpointSplit“中点切分”的本质区别所在。构造函数MeanSplitBallTree通过一种类似快速排序quicksort的算法对数据集中的点进行排列来高效构建。因此构造后树内数据集通过node.Dataset()访问的点顺序可能与原data不同。node MeanSplitBallTree(data, maxLeafSize20)node MeanSplitBallTree(data, oldFromNew, maxLeafSize20)node MeanSplitBallTree(data, oldFromNew, newFromOld, maxLeafSize20)在给定data上构造MeanSplitBallTreemaxLeafSize是每个叶子中最多保存的点数。默认情况下data会被拷贝。使用std::move(data)如std::move(data)可避免拷贝此时data会被置为空矩阵。可选地构造从旧点到新点的映射。oldFromNew与newFromOld的长度均为data.n_cols且oldFromNew[i]表示树数据集中的点i原本是data中的点oldFromNew[i]即node.Dataset().col(i)是data.col(oldFromNew[i])newFromOld[i]表示data中的点i现在是树数据集中的点newFromOld[i]即node.Dataset().col(newFromOld[i])是data.col(i)。node MeanSplitBallTreeDistanceType, StatisticType, MatType(data, maxLeafSize20)node MeanSplitBallTreeDistanceType, StatisticType, MatType(data, oldFromNew, maxLeafSize20)node MeanSplitBallTreeDistanceType, StatisticType, MatType(data, oldFromNew, newFromOld, maxLeafSize20)使用自定义模板参数构造树行为同上。node MeanSplitBallTree()构造一棵空的球树没有子节点也没有点。注意事项此处使用node而非tree来命名对象是因为每个MeanSplitBallTree对象只是树中的一个节点构造函数返回的是树的根节点。在MeanSplitBallTree中不保证各节点的球边界互不相交它们可能重叠。因为对许多数据集而言几何上无法构造两个不相交的球覆盖全部点。不支持单点插入或删除因为这会通常导致球边界非常松散。更好的做法是在修改后的数据集上重新构建一棵新的MeanSplitBallTree。需要单点插入/删除的树请参考RectangleTree及其变体如RTree、RStarTree等。更多细节见 开发者文档中关于树构造函数的说明。这些构造函数签名与源码中的 BinarySpaceTree 构造函数声明 一一对应包括左值引用拷贝版本与右值引用std::move移动版本后者在传入MatType时不会复制数据矩阵。构造函数参数表nametypedescriptiondefaultdataarma::mat按列优先的矩阵用于建树。传入std::move(data)可避免拷贝矩阵。(N/A)maxLeafSizesize_t每个叶子中最多保存的点数。20oldFromNewstd::vectorsize_t从node.Dataset()中的点到data中点的映射。(N/A)newFromOldstd::vectorsize_t从data中的点到node.Dataset()中点的映射。(N/A)基本树属性构造完成后可以访问或检查树的各项属性。其中许多函数是 TreeType API 所要求的。树的导航node.NumChildren()返回node的子节点数量有子节点时为2是叶子时为0。node.IsLeaf()返回bool指示node是否为叶子。node.Child(i)返回MeanSplitBallTree即第i个子节点。i必须为0或1。仅当node.NumChildren() ! 0即node非叶子时才应调用。返回的引用是有效的MeanSplitBallTree可以像根节点一样继续使用。node.Left()与node.Right()是MeanSplitBallTree特有的便捷函数分别返回指向左右子节点的MeanSplitBallTree*指针若无子节点则返回NULL。node.Parent()返回指向node父节点的MeanSplitBallTree*若node是根节点则返回NULL。访问树成员node.Bound()返回表示node边界球的BallBound对象。它可能不是包围node所有后代点的最小边界球但是一个相当接近的近似。node.Stat()返回EmptyStatistic若指定了自定义StatisticType则为StatisticType保存树构造期间计算得到的节点统计信息。node.Distance()返回EuclideanDistance若指定自定义DistanceType则为DistanceType。BallBound类的实现位于 src/mlpack/core/tree/ballbound.hpp它封装了圆心与半径并提供MinDistance、MaxDistance、RangeDistance等几何查询方法是整棵树距离下界/上界计算的基础。访问树中保存的数据node.Dataset()返回const arma::mat即建树所用的数据集。注意这是传入构造函数的data矩阵的排列后版本。若使用了自定义MatType返回类型为const MatType而非const arma::mat。node.NumPoints()返回size_t指示node直接保存的点数。若node非叶子返回0MeanSplitBallTree只在叶子中直接保存点。若node是叶子点数小于等于构造时指定的maxLeafSize。node.Point(i)返回size_t指示node.Dataset()中第i个点的索引。i必须在[0, node.NumPoints() - 1]含范围内。node必须是叶子非叶子不保存点。第i个点可通过node.Dataset().col(node.Point(i))访问。由于构造期间的点排列MeanSplitBallTree中点索引是连续的对合法i、jnode.Point(i j)等于node.Point(i) j。访问第i个点本身可如node.Dataset().col(node.Point(i))。node.NumDescendants()返回size_t指示node所有后代叶子中保存的点数。若node是根节点则node.NumDescendants()等于node.Dataset().n_cols。node.Descendant(i)返回size_t指示node.Dataset()中第i个后代点的索引。i必须在[0, node.NumDescendants() - 1]含范围内。node不要求是叶子。第i个后代点可通过node.Dataset().col(node.Descendant(i))访问。同理由于点排列后代索引是连续的对合法i、jnode.Descendant(i j)等于node.Descendant(i) j。node.Begin()返回size_t指示node第一个后代点的索引等价于node.Descendant(0)。node.Count()返回size_t指示node的后代点数等价于node.NumDescendants()。这些排列映射的实际构造逻辑位于 binary_space_tree_impl.hpp初始化时oldFromNew[i] i切分后newFromOld[oldFromNew[i]] i从而建立新旧点序的双向对应关系。访问树的计算边界量以下量在MeanSplitBallTree中为每个节点缓存访问时无需重新计算。node.FurthestPointDistance()返回double表示node边界球中心到node直接保存的最远点的距离。若node非叶子返回0因为不直接保存点。若node是叶子等价于node.Bound().Radius()。node.FurthestDescendantDistance()返回double表示node边界球中心到node最远后代点的距离。该值小于等于node.Radius()。node.MinimumBoundDistance()返回double表示从节点中心到球边界任意边缘的最小可能距离等价于node.Bound().Radius()。node.ParentDistance()返回double表示node边界球中心与其父节点边界球中心之间的距离。若node是根节点返回0。注意事项若指定了自定义MatType每个方法的返回类型是MatType的元素类型而非double例如MatType为arma::fmat时返回float。关于各边界量的更多细节见 开发者文档中树边界量章节。其他功能node.Center(center)将node边界球的中心存入center。center应为arma::vec类型若指定自定义MatType则为对应列向量类型如arma::fvec。center的尺寸会被设置为node数据集的维度。等价于调用node.Bound().Center(center)。MeanSplitBallTree可通过Save()与Load()进行序列化。用树计算距离边界树在 mlpack 中的主要用途是为点或其它树节点提供距离边界。以下函数用于这类任务。node.GetNearestChild(point)/node.GetFurthestChild(point)返回size_t指示距point最近或最远的子节点索引0为左1为右依据MinDistance()或MaxDistance()函数判断。若出现平局返回0左子节点。若node是叶子返回0。point应为arma::vec类型自定义MatType时为对应列向量如arma::fvec。node.GetNearestChild(other)/node.GetFurthestChild(other)返回size_t指示距节点other最近或最远的子节点索引依据MinDistance()或MaxDistance()函数判断。若出现平局返回2非法索引。注意这与上面接收point的版本行为不同。若node是叶子返回0。node.MinDistance(point)/node.MinDistance(other)返回double表示node与point或节点other之间的最小可能距离。等价于node边界球内任意点与point之间的最小可能距离或node边界球内任意点与other边界球内任意点之间的最小可能距离。point应为arma::vec自定义MatType时为对应列向量返回类型为MatType元素类型如arma::fvec对应返回float。node.MaxDistance(point)/node.MaxDistance(other)返回double表示node与point或节点other之间的最大可能距离语义与MinDistance对称。node.RangeDistance(point)/node.RangeDistance(other)返回一个Range下界为node.MinDistance(...)上界为node.MaxDistance(...)。point应为arma::vec自定义MatType时返回元素类型相同的RangeType如arma::fmat对应RangeTypefloat。这些距离边界函数正是各类树算法剪枝的核心单树算法利用“节点到查询点的最小距离”判断能否剪掉整个子树双树算法则利用“两节点间最小距离”跳过不可能包含答案的点对。mlpack 测试中BallTreeTest见 tree_test.cpp会随机生成 200011000 个点、维度从 2 递增逐一验证排列映射正确性以及每个点都包含在其所有祖先节点的边界内从而保证了上述边界量的几何一致性。树遍历器Tree Traversals与 mlpack 中每棵树一样MeanSplitBallTree提供了 单树与双树遍历器可搭配RuleType类 实现单树或双树算法MeanSplitBallTree::SingleTreeTraverser实现深度优先的单树遍历器。MeanSplitBallTree::DualTreeTraverser实现深度优先的双树遍历器。除这两个 TreeType policy 要求的类之外还额外提供一个遍历器MeanSplitBallTree::BreadthFirstDualTreeTraverser实现广度优先的双树遍历器。注意该遍历器并非对所有任务都有用由于BallTree只在叶子中保存点这意味着在所有中间节点对完成评分之前不会调用任何基例base case即点与点的比较对应的实现文件位于 src/mlpack/core/tree/binary_space_tree/包括single_tree_traverser.hpp/impl.hpp、dual_tree_traverser.hpp/impl.hpp与breadth_first_dual_tree_traverser.hpp/impl.hpp。示例用法示例 1构建树并打印基本统计信息在cloud数据集上构建MeanSplitBallTree并打印树的基本统计信息// 数据见 https://datasets.mlpack.org/cloud.csv。 arma::mat dataset; mlpack::Load(cloud.csv, dataset, mlpack::Fatal); // 以叶子大小 10 构建球树。这意味着节点会持续切分直到每个节点含 10 个或更少的点。 // // 使用 std::move() 意味着此调用后 dataset 将为空且建树过程中不会拷贝数据。 // // 注意如果使用 C20或更新标准 不是必需的例如 // mlpack::MeanSplitBallTree tree(...) 在 C20 及更高版本下也能正常工作。 mlpack::MeanSplitBallTree tree(std::move(dataset), 10); // 打印根节点的边界球。 std::cout Bounding ball of root node: std::endl; std::cout - Center: tree.Bound().Center(); std::cout - Radius: tree.Bound().Radius(); std::cout std::endl; // 打印根节点及其两个子节点的后代点数。 std::cout Descendant points of root: tree.NumDescendants() . std::endl; std::cout Descendant points of left child: tree.Left()-NumDescendants() . std::endl; std::cout Descendant points of right child: tree.Right()-NumDescendants() . std::endl; std::cout std::endl;示例 2构建两棵树并计算节点间距离在 corel 数据集的两个子集上分别构建MeanSplitBallTree并计算树节点之间的最小/最大距离// 数据见 https://datasets.mlpack.org/corel-histogram.csv。 arma::mat dataset; mlpack::Load(corel-histogram.csv, dataset, mlpack::Fatal); // 在前一半和后一半点上分别构建球树。 mlpack::MeanSplitBallTree tree1(dataset.cols(0, dataset.n_cols / 2)); mlpack::MeanSplitBallTree tree2(dataset.cols(dataset.n_cols / 2 1, dataset.n_cols - 1)); // 计算两棵树之间的最大距离。 std::cout Maximum distance between tree root nodes: tree1.MaxDistance(tree2) . std::endl; // 获取第一棵树根节点的最左孙节点——如果存在的话。 if (!tree1.IsLeaf() !tree1.Child(0).IsLeaf()) { mlpack::MeanSplitBallTree node1 tree1.Child(0).Child(0); // 获取第二棵树根节点的最右孙节点——如果存在的话。 if (!tree2.IsLeaf() !tree2.Child(1).IsLeaf()) { mlpack::MeanSplitBallTree node2 tree2.Child(1).Child(1); // 打印两个节点之间的最小和最大距离。 mlpack::Range dists node1.RangeDistance(node2); std::cout Possible distances between two grandchild nodes: [ dists.Lo() , dists.Hi() ]. std::endl; // 打印第一个节点与第二个节点第一个后代点之间的最小距离。 const size_t descendantIndex node2.Descendant(0); const double descendantMinDist node1.MinDistance(node2.Dataset().col(descendantIndex)); std::cout Minimum distance between grandchild node and descendant point: descendantMinDist . std::endl; // node2 的哪个子节点更靠近 node1 const size_t closerIndex node2.GetNearestChild(node1); if (closerIndex 0) std::cout The left child of node2 is closer to node1. std::endl; else if (closerIndex 1) std::cout The right child of node2 is closer to node1. std::endl; else // closerIndex 2 in this case. std::cout Both children of node2 are equally close to node1. std::endl; // 而 node1 的哪个子节点离 node2 更远 const size_t furtherIndex node1.GetFurthestChild(node2); if (furtherIndex 0) std::cout The left child of node1 is further from node2. std::endl; else if (furtherIndex 1) std::cout The right child of node1 is further from node2. std::endl; else // furtherIndex 2 in this case. std::cout Both children of node1 are equally far from node2. std::endl; } }注意此示例展示了接收节点参数的GetNearestChild/GetFurthestChild在平局时返回2非法索引这一与点版本不同的行为。示例 3使用 32 位浮点数据构建并保存树在 32 位浮点数据上构建MeanSplitBallTree并保存到磁盘// 数据见 https://datasets.mlpack.org/corel-histogram.csv。 arma::fmat dataset; mlpack::Load(corel-histogram.csv, dataset); // 使用 32 位浮点矩阵类型构建 MeanSplitBallTree。 // 这里仍然使用默认的 EmptyStatistic 和 EuclideanDistance 参数 // 叶子大小使用 100。 mlpack::MeanSplitBallTreemlpack::EuclideanDistance, mlpack::EmptyStatistic, arma::fmat tree(std::move(dataset), 100); // 以名称 tree 将 MeanSplitBallTree 保存到磁盘。 mlpack::Save(tree.bin, tree); std::cout Saved tree with tree.Dataset().n_cols points to tree.bin. std::endl;示例 4从磁盘加载树并手动遍历加载 32 位浮点BallTree然后手动遍历并统计叶子数少于 10 个点的叶子节点个数// 这里假定树已按上面的示例保存到 tree.bin。 // 这个便捷 typedef 省去了一长串类型名 using TreeType mlpack::MeanSplitBallTreemlpack::EuclideanDistance, mlpack::EmptyStatistic, arma::fmat; TreeType tree; mlpack::Load(tree.bin, tree); std::cout Tree loaded with tree.NumDescendants() points. std::endl; // 以深度优先方式递归。统计叶子总数以及少于 10 个点的叶子数量。 size_t leafCount 0; size_t totalLeafCount 0; std::stackTreeType* stack; stack.push(tree); while (!stack.empty()) { TreeType* node stack.top(); stack.pop(); if (node-NumPoints() 10) leafCount; totalLeafCount; if (!node-IsLeaf()) { stack.push(node-Left()); stack.push(node-Right()); } } // 注意也可以使用 TreeType::SingleTreeTraverser 完成上面的递归 // 但它更适合需要剪枝等非平凡行为的复杂任务因此这里使用简单的 // 栈是更优的选择。 // 打印结果。 std::cout leafCount out of totalLeafCount leaves have fewer than 10 points. std::endl;示例 5新旧点序映射构建MeanSplitBallTree并在原始点与新点之间进行映射// 数据见 https://datasets.mlpack.org/cloud.csv。 arma::mat dataset; mlpack::Load(cloud.csv, dataset, mlpack::Fatal); // 构建树。 std::vectorsize_t oldFromNew, newFromOld; mlpack::MeanSplitBallTree tree(dataset, oldFromNew, newFromOld); // oldFromNew 和 newFromOld 会被设置为与数据集相同的大小。 std::cout Number of points in dataset: dataset.n_cols . std::endl; std::cout Size of oldFromNew: oldFromNew.size() . std::endl; std::cout Size of newFromOld: newFromOld.size() . std::endl; std::cout std::endl; // 查看树数据集中点 42 的原始位置。 std::cout Point 42 in the permuted trees dataset: std::endl; std::cout tree.Dataset().col(42).t(); std::cout Was originally point oldFromNew[42] : std::endl; std::cout dataset.col(oldFromNew[42]).t(); std::cout std::endl; // 查看原始数据集中点 7 映射到的新位置。 std::cout Point 7 in original dataset: std::endl; std::cout dataset.col(7).t(); std::cout Mapped to point newFromOld[7] : std::endl; std::cout tree.Dataset().col(newFromOld[7]).t();延伸阅读BallTree使用中点切分策略的球树与本文主题直接对比mlpack 树总览mlpack 中所有空间划分树的索引KNNMeanSplitBallTree最典型的应用场景mlpack 几何算法BinarySpaceTree通用二叉空间树基类与MeanSplit策略说明Tree-Independent Dual-Tree Algorithms双树算法背后的理论依据实现源码typedef.hpp、mean_split.hpp、mean_split_impl.hpp、binary_space_tree.hpp、ballbound.hpp相关测试tree_test.cpp 的 BallTreeTest赞分享人工智能机器学习深度学习【免费下载链接】mlpackmlpack: a fast, header-only C machine learning library项目地址https://gitcode.com/gh_mirrors/ml/mlpack点击查看免费下载相关推荐mlpack KDTree 完全指南k 维二分空间划分树的构造、遍历与距离边界计算mlpack KDTree 完全指南k 维二分空间划分树的构造、遍历与距离边界计算 mlpack 的 KDTree 是 k 维二分空间划分binary sp人工智能机器学习深度学习mlpack MaxRPTree 实战指南随机投影树Max-Split Random Projection Tree的构建、遍历与距离界计算mlpack MaxRPTree 实战指南随机投影树Max Split Random Projection Tree的构建、遍历与距离界计算 本篇技术指南人工智能机器学习深度学习二叉树遍历算法完全指南3种核心遍历方式详解二叉树遍历算法完全指南3种核心遍历方式详解 二叉树遍历是数据结构与算法中的基础操作也是面试高频考点。本文将系统讲解前序、中序、后序三种核心遍历方式的原理、实示例工程上一篇Nodeunit Sandbox工具详解安全测试私有函数与客户端代码下一篇Simple Live跨平台直播聚合应用开发实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
复杂度详解)
