nuget
Barnes-Hut 空间划分树（2^dim 叉树）
SPTree
00 Remarks
移植自 L. van der Maaten 的 bh_tsne 参考实现（SPTree）。
t-SNE 梯度中的斥力项需要对所有 N² 个点对求和，这是 O(N²) 复杂度的根源。 Barnes-Hut 的做法是把当前的低维嵌入组织成一棵空间划分树， 当某个 cell 的角宽度（宽度 / 到质心的距离）小于阈值 theta 时， 就用该 cell 的质心一次性近似整棵子树，从而把单次遍历降到 O(log N)， 整体降到 O(N log N)。theta 越大近似越激进、速度越快、精度越低， theta = 0 时退化为精确计算。
建树过程对点索引数组做原地重排，使得任意节点的子树都对应一段连续区间， 因此节点数仅为 O(N / leafSize)，内存开销相对 N 可以忽略。
01 Syntax
Microsoft.VisualBasic.MachineLearning.tSNE.SPTree
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| .ctor | 1 | 依据当前的低维嵌入构建空间划分树 |
| Build | 1 | 建树：广度优先细分 + 自底向上汇总质心 |
| Subdivide | 1 | 把当前节点的点集按各维度的中点分配到 2^dim 个子节点之中 |
| ComputeBounds | 1 | 计算 [start, finish) 区间内所有点的包围盒 |
| ComputeCenterOfMass | 1 | 依据子节点（或叶子自身的点）汇总出本节点的质心 |
| ComputeNonEdgeForces | 1 | 计算指定点的远场（斥力）作用力，结果累加到 negF |
03 Properties
| Name | Overloads | Summary |
|---|---|---|
| NodeCount | 1 | 当前树上的节点总数（调试与性能诊断用） |
04 Fields
| Name | Overloads | Summary |
|---|---|---|
| DEFAULT_LEAF_SIZE | 1 | 叶子节点最多容纳的点数；超过则继续细分 |
| idx | 1 | 点索引的排列，建树过程中被就地重排 |
| nodes | 1 | 按 BFS 顺序收集的全部节点；逆序遍历即为后序遍历 |
05 Members
#ctor(
Int32, Double(), Int32, Int32)依据当前的低维嵌入构建空间划分树
Parameters
| Name | Type | Description |
|---|---|---|
[dim] | Int32 | 嵌入维度，通常为 2 或 3 |
Y | Double() | 低维坐标，行主序的一维数组，长度为 N * dim（借用，内部不复制） |
N | Int32 | 样本数量 |
leafSize | Int32 | 叶子节点容量 |
Build
建树：广度优先细分 + 自底向上汇总质心
Subdivide(SPNode)
把当前节点的点集按各维度的中点分配到 2^dim 个子节点之中
ComputeBounds(
Int32, Int32, Double(), Double())计算 [start, finish) 区间内所有点的包围盒
ComputeCenterOfMass(SPNode)
依据子节点（或叶子自身的点）汇总出本节点的质心
ComputeNonEdgeForces(
Int32, Double, Double(), Double)计算指定点的远场（斥力）作用力，结果累加到 negF
Parameters
| Name | Type | Description |
|---|---|---|
pointIndex | Int32 | 目标点索引 |
theta | Double | Barnes-Hut 阈值：当 cell 的最大宽度 / 到质心的距离 < theta 时， 用质心近似整棵子树。取值越大越快越粗糙，取 0 退化为精确计算。 |
negF | Double() | 斥力累加器，长度为 N * dim |
sumQ | Double | 配分函数 Z 的累加器（线程本地，调用方负责最终合并） |
NodeCount
当前树上的节点总数（调试与性能诊断用）
DEFAULT_LEAF_SIZE
叶子节点最多容纳的点数；超过则继续细分
Remarks
取 1 时叶子只装一个点，此时 theta = 0 会退化为精确计算（误差仅来自重合点）。 取值越大树越浅、遍历越快，但叶内的点会被质心所替代，近似误差越大。
idx
点索引的排列，建树过程中被就地重排
nodes
按 BFS 顺序收集的全部节点；逆序遍历即为后序遍历