三、K-D树的构造
首先，K-D树是一种空间划分树，根据已知的一些数据点（训练样本集）将空间不断划分成不同的越来越小的区域，来使查找邻近元素更加的快速。对空间的划分方式就像选取好某一个维度，然后拿刀整齐的划分为两半一样，这样整个空间就在某个维度的某个值处，被一个超平面‘一刀’切成了两个子空间。
举个例子清楚些，先直观的感受下整个构造K-D树的流程，具体细节下面讲。我们取K=2，来看一下最简单的2维数据的情况。假设我们的训练样本集inputs={（2,3）、（5,4）、（9,6）、（4,7）、（8,1）、（7,2）}。则根据样本集构造的k-d树及对应的空间划分示意图如下所示：
例子中，样本的特征数k = 2，首先算法要根据目前整个平面的样本点，选择一个维度进行分裂操作，即在某个维度上将平面用一条直线一分为二。如图所示，算法选出的维度是x轴（后面会说如何选取分裂维度），然后算法将所有样本点按照x轴的取值进行排序，选出排序后的中点作为分裂的节点（int half = start + length / 2;），同时每个分裂点也会成为K-D树中的一个节点。显然，算法选出了点（7,2），于是（7,2）也成为了K-D树的根节点，沿垂直与x轴方向且过点（7,2）的加粗直线将平面分成了两部分。然后，对于分开的两个部分，仍然按照上面的步骤进行，算法恰巧都选择了y轴作为分裂维度，且分裂节点选择的分别是（5,4）和（9,6），其对空间所做的分割如上图细黑线所示。重复步骤直到无法再进行分割。
看了上面的例子，应该能够看出些端倪了，我们可以看到K-D树的构造过程是一个递归的过程，在构造中，我们不断地通过在某个维度上进行“二分”来对整个空间进行越来越细致的划分。应该能够感觉到，在一个新的数据点到来时，这种利用K-D树划分区域的结构，可以缩小我们搜索的范围。比如，如果来了一个新的点（2,4），我们的第一直觉肯定是往由（7,2）节点所分割的左半平面去寻找最近邻点，这样（可能）一下子省去一半样本点的搜索。
下面准备详细的给出K-D树的构造过程了，首先给出K-D树节点的数据结构。
KDTreeNode<T>的数据结构：
属性名称 | 属性类型 | 属性含义 |
Axis | int | 获取或设置拆分的维度索引。此值表示位置向量的索引号，因此应大于零并且小于位置向量元素的个数。 |
IsLeaf | bool | 获取这个节点是否是一片叶子（没有孩子）。 |
Left | KDTreeNode<T> | 获取或设置该节点的左子树。 |
Position | double[] | 获取或设置节点在空间坐标中的位置（描述样本点的特征值数组）。 |
Right | KDTreeNode<T> | 获取或设置该节点的右子树。 |
Value | T | 获取或设置此节点中存储的值，通常是类别标签。 |
可以看到，这样定义后的每一个K-D树节点，记录了从哪一个维度或坐标轴（Axis维）的哪一个取值处（Position[Axis]）定义了一个超平面对空间进行划分，并且该节点对应的样本数据是Position。最后，超平面分割的左子空间的信息可以通过左孩子节点Left来获取，右子空间的信息通过右孩子节点Right来获取。
了解了节点的结构，如何给当前节点的这些属性赋值呢？
如何选择分裂维度（为Axis赋值）：
方法1：对于当前的数据样本集合inputs而言，计算每一个特征的样本方差（注意样本方差是无偏估计的哪个，分母除以的是n-1，虽然其实没什么太大差别）。选出方差最大的哪个特征出来，这表征了这个特征各个样本间数据的差别较大，就选择这个维度作为分裂维度，为Axis赋值。至于为什么要选择方差最大的哪个特征维度呢？相信大家和我一样能够感觉到其合理性，方差越大说明样本间越分散，在越分散的维度进行分割效率就会越高，这一点在介绍完最邻近搜索后就能感觉出来了。
方法2：对于数据分布比较均匀的样本集来说，随便选取一个维度来进行分裂就可以了，因为计算方差没有太大的效果提升（各个维度方差都差不多），反而还浪费了许多时间。但是有一点要注意，随便选取并不是随机选取，假设算法最开始时随机从第i维进行了一次分裂后，被分割后的两个子数据集在第i维上特征值的分散程度会低于其他维度，即第i个特征的样本方差和其他的特征已经不是一个数量等级了，所以应该避免再次选择在第i维上进行分裂。最简单的实现方法是对根节点（树的第0层），设置分裂维度为0，树的第一层设置分裂维度维1，第二层为2，……第x层的分裂维度为x%k（x对特征维数k取余，intaxis = comparer.Index = depth % k;）。这个策略反映的也就是随机非随便的含义。
这两个方法如何取舍呢？一般情况下，除非训练样本集分布极不均匀（例如：inputs=｛（2,3），（5,3），（9,3），（4,3），（8,3），（7，3）｝），或者对于构造树的时间并不关心且十分在意k邻近点的搜索速度时，使用方法1的策略来选择分裂维度即可，否则就使用方法2。
如何选择分裂节点（为Position赋值）：
现在假设我们在当前数据集inputs下已经选出了在第Axis维上进行分裂，如何选择分割超平面呢？或者说我们已知分割超平面要垂直Axis轴了，但是过Axis轴上哪个点呢？将当前样本集inputs依照第Axis维的取值由小到大排序，选择排序后中间（int half = start + length / 2;）的样本作为分裂节点，即double[] Position = inputs[half]，于是inputs就被垂直于Axis维且过点Position的超平面分割成两个部分了，其中左半部分（int leftStart = start; int leftLength = half - start;）的样本在第Axis维的值均小于Position[Axis]，右半部分（int rightStart = half + 1; int rightLength = length - length / 2 - 1;）样本在第Axis维的值均大于Position[Axis]。由于构造K-D树是一个递归的过程，当前节点赋值完成了，对当前节点的左子树，右子树，我们使用同样的方法即可，见下面函数。
KDTree<T>的数据结构：
属性名称 | 属性类型 | 属性含义 |
Count | int | 获取样本数据集中样本的数量。 |
Dimensions | int | 获取样本数据的特征数（维数）。 |
Distance | Func< double[],double[],double> | 获取或设置测量所用的距离。 |
Leaves | int | 获取叶子节点的数量。 |
Root | KDTreeNode<T> | 获取K-D树的根节点。 |
public static KDTree<T> FromData<T>(double[][]points, T[] values,
Func<double[], double[],double> distance, bool inPlace = false)
{
if(values == null)
throw new ArgumentNullException("values");
if(distance == null)
throw new ArgumentNullException("distance");
int leaves;
var root = KDTree<T>.CreateRoot(points, values,inPlace, out leaves);
return new KDTree<T>(points[0].Length, root, points.Length, leaves)
{
Distance = distance,
};
}
protected static KDTreeNode<T> CreateRoot(double[][]points, T[] values, bool inPlace, out int leaves)
{
if(points == null)
throw new ArgumentNullException("points");
if(values != null && points.Length !=values.Length)
throw new DimensionMismatchException("values");
if(!inPlace)
{
points = (double[][])points.Clone();
if (values != null)
values = (T[])values.Clone();
}
leaves = 0;
int dimensions = points[0].Length;
ElementComparer comparer = new ElementComparer();
KDTreeNode<T> root = create(points, values, 0, dimensions, 0,points.Length, comparer, ref leaves);
return root;
}
private static KDTreeNode<T> create(double[][]points, T[] values,
int depth, int k, int start, int length, ElementComparer comparer, ref int leaves)
{
if(length <= 0)
return null;
int axis = comparer.Index = depth % k;
Array.Sort(points, values, start, length, comparer);
in thalf = start + length / 2;
int leftStart = start;
int leftLength = half - start;
int rightStart = half + 1;
int rightLength = length - length / 2 - 1;
var median = points[half];
var value = values != null ? values[half] : default(T);
depth++;
KDTreeNode<T> left = create(points, values, depth, k,leftStart, leftLength, comparer, ref leaves);
KDTreeNode<T> right = create(points, values, depth, k,rightStart, rightLength, comparer, ref leaves);
if(left == null && right == null)
leaves++;
returnnewKDTreeNode<T>()
{
Axis = axis,
Position = median,
Value = value,
Left = left,
Right = right,
};
}
参考阅读：
通过微信学习的知识只能是碎片化的知识，作为新时代的我们希望能够构建自己的知识结构，使我们的知识体系化，系统化，以后在遇到碎片化的知识，我们做的只是融合到自己的知识结构中，故我们将推出“与LSGO一起学”系列课程，帮助大家来构建知识框架，初步规划有：
“与LSGO一起学C++”；
“与LSGO一起学C#”；
“与LSGO一起学Matlab”；
“与LSGO一起学数据结构”；
“与LSGO一起学设计模式”；
“与LSGO一起学可视化建模语言（UML）”；
“与LSGO一起学线性代数”；
“与LSGO一起学高等数学”
“与LSGO一起学概率论与数理统计”；
“与LSGO一起学抽象代数；
“与LSGO一起学点集拓扑”
“与LSGO一起学数字图像处理”；
“与LSGO一起学智能计算”；
如果对这些内容感兴趣，可以一起来学习讨论。
我们的官网： www.lsgogroup.com
联系客服
