首页所有驱动分类下载数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

K-D树结构原理与实例详解,可用于机器学习k邻近算法

2020-02-21 数据结构, AI机器学习 浏览次数:83
 
KD树是二叉树数据结构,同时也运用了排序二叉树的思想,主要用于范围式的查找,KD树最擅长的是能够对多维属性进行查找,此数据结构与K邻近分类算法搭配使用,能很好的实现对未知事物的分类工作,这里有些知识不再重复,例如:在多维空间里,如何计算连个点之间的距离?什么是K邻近分类算法?如果这些都没懂的话,希望先看另一篇文章,“K邻近分类算法详解”。

回到正题,假设现在有7个点,每个点都是一个二维数据,代表X,Y两个轴向,它们的值是:[3,0],[6,0],[8,1],[7,4],[5,8],[7,8],[5,9]。

现在想在这堆数据里找出与[3,9]最接近的一个点,最简单的方法就是逐个计算,然后按顺序排列,就得到以下结果:



这种方法虽然简单有效,效率很差,如果数据有很多的话,计算量是非常大的,而KD树可以很好的解决效率问题,它思想是:根据轴向,将数据进行区域划分。

1 首先选定某个轴向作为初始划分轴,在这个轴向上对数据进行排序,取中间位置的数据作为树节点,在这轴向上,小于节点轴向值的一律放左边,大于或等于的一律放右边(其实是将数据对半划分)。
2 然后选下一个轴向,继续对剩余的数据进行划分,根据步骤1的规则,将数据对半划分。
3 反复循环1和2步骤,直到没有数据为止。

用上面的7个数值进行划分,取X轴作为初始划分轴(其实选Y轴也可以,随便~~),按照X轴从小到大的排列顺序是:[3,0],[5,9],[5,8],[6,0] ,[7,8],[7,4],[8,1]。在这个队列里排在中间位置的数据是[6,0],这里需要注意,很多资料笼统的说是中间值,更准确的说法应该是:排在中间位置的数据,以这个位置作为节点,然后将剩余的所有数据一分为二,一半排左边,一半排右边。

经过这么一划分,[3,0],[5,9],[5,8]这三个点在[6,0]左边,[7,8],[7,4],[8,1]这三个点在右边,得到的数据,左边图是坐标图,右边是树结构图:

-

现在,继续对左边和右边的剩余数据进行划分,因为上次选的是X轴,所以这次得选Y轴。

左边剩余的数据是:[3,0],[5,9],[5,8],既然这次选的是Y轴,所以当然要以Y轴的值作为排序标准,排序后的点:[3,0],[5,8],[5,9],中间位置的数据是[5,8],所以[3,0]被分在左边,[5,9]被分在右边。由于左边和右边都只有一个数据点,所以就不用再分了。得到的图如下:

-

同样的方法,对右边的另一个数据集[7,8],[7,4],[8,1],以Y轴作为划分轴,进行排序后:[8,1],[7,4],[7,8]。中间位置的数据是[7,4],所以[8,1]被分在左边,[7,8]被分在右边。由于左边和右边都只有一个数据点,所以就不用再分了。得到的图如下:

-

从上面的建立过程,也看出来了,其实上面的过程和规则,就是KD树的建立规则,无非就是:选个初始划分轴,按照划分轴上的值,将数据排序,选个中间位置的数据作为节点,然后把数据一分为二往左右两边放;然后选下一个划分轴,把剩余的数据继续这样分,一直分到最后只剩一个数据为止。
现在有个数据点[3,9],这个点称为查询点,如何找到跟这个节点最近的节点呢?

从KD树的跟节点开始,从上往下找,规则如下:

一开始,将当前最近距离设为无限大

1 每到一个节点,都计算跟查询点的距离,如果距离比当前最近距离还要小,就将此值设置为当前最近距离

2 在当前节点的划分轴上,计算当前节点与查询点在此轴上的值的差,然后将差变成绝对值,这个值我将其称为轴距差,然后根据以下三种情况分别处理:

情况1:轴距差大于当前最近距离,并且当前节点在此轴上的值小于查询点的轴上值,就不再进入其左子节点,但要进入其右子节点继续查找。

情况2:轴距差大于当前最近距离,并且当前节点在此轴上的值大于查询点的轴值,不再进入其右子节点,但要进入其左子节点继续查找。

情况3:轴距差小于或等于当前最近距离值,要进入其左右两个子节点继续查找。

就这样,反复重复上面的步骤,一直查到底部,最后就会得到一个最近距离点。

现在开始实践,对上面的KD树进行查询,查询点是[3,9],要求查出与[3,9]最邻近的点。

初始化,将当前最近距离设置为无限大,程序里可以设置为负数。然后从根节点开始,[3,9]与根节点[6,0]的距离为9.48,然后将9.48这个值设置成当前最近距离,同时也认为[6,0]这个节点到目前为止,是和查询点最近的,然后再看[6,0]这个节点,建立这个点的时候是以X轴为划分轴的,在X坐标轴上,它和查询点的轴距差=3=|3-6|(取绝对值),看来符合情况3:


情况3:轴距差小于或等于当前最近距离值,要进入其左右两个子节点继续查找。


所以要进入这个节点的左右两个子节点继续查。那接下来先进入左子节点吧,左子节点是[5,8],跟查询点[3,9]的距离是2.23,比之前的最近距离还小,那么将2.23设置成当前最近距离,同时也认为[5,8]这个点到目前为止与查询点是最近的,然后再看[5,8]这个节点,建立这个节点的时候是以Y轴为划分轴的,在Y坐标轴上,它和查询点的轴距差=1=|9-8|,看来符合情况3,继续查这个节点的左右两个子节点。

依然先进入左子节点[3,0],这个节点以X轴作为划分轴,与查询点[3,9]的距离是9,轴距差=0=|3-3|,符合情况3,但由于这个节点是一个叶子节点,没有子节点,而且与查询点的距离又比当前最近距离大,所以这个节点可以不用理会了,然后递归返回查看它的兄弟节点[5,9],这个节点跟查询点的距离是2,比之前的值还要小,所以要将当前最近距离设置成2,同时也认为[3,0]这个点到目前为止与查询点是最近的,接下来看轴距差=2=|3-5|,符合情况3,由于是叶子节点,所以不用继续往下找了。

然后通过递归层层回溯到了根节点[6,0],继续进入它的右子树,查看[7,4]这个节点的划分轴是Y轴,与查询点的距离是6.4,轴距差=5=|9-4|,看来符合情况1:


情况1:轴距差大于当前最近距离,并且当前节点在此轴上的值小于查询点的轴上值,就不再进入其左子节点,但要进入其右子节点继续查找。


轴距差5大于当前最近距离2,并且在划分轴Y轴上的值是4,小于查询点Y轴上的9,所以只需要进入它的右子节点[7,8]。

进入[7,8]这个节点,此点划分轴是X轴,与查询点的距离是4.12,轴距差=4=|3-7|,看来符合情况2:


情况2:轴距差大于当前最近距离,并且当前节点在此轴上的值大于查询点的轴值,不再进入其右子节点,但要进入其左子节点继续查找。


轴距差4大于当前最近距离2,并且在划分轴X轴上的值是7,大于查询点X轴上的3,需要进入它的左子节点,但由于这个是叶子节点,所以程序到此结束。

函数执行完毕最后,在最邻近节点这个变量里保存的是[5,9],最近距离这个变量里保存的是2。

其实为什么要用轴距差和当前最近距离做对比,这是根据排序二叉树的特点进行工作,看下图就知道了。



当程序递归执行到某一个点的时候,例如:[5,9]这个节点,由于它与查询点的距离是2,那么以[3,9]作为中心点,以2作为半径画个红色圆,很容易的看出,如果还有其他的点比[5,9]更加靠近[3,9]的话,那么肯定是在红圈之内。

对于[5,9]这个点,换而言之:

凡是X轴上的值大于5或者小于1的,都不需要考虑了。
5=3(查询点的X轴值)+ 2(与查询点的距离)
1=3(查询点的X轴值)- 2(与查询点的距离)

凡是Y轴上的值大于11或者小于7的点,都不需要考虑了。

11=9(查询点的Y轴值)+ 2(与查询点的距离)
7=9(查询点的Y轴值)- 2(与查询点的距离)

具有以上任意一种情况的,都是不会在圆圈之内。但是,是不是说,具有以上任意一种情况的点,也不需要进入其子节点查找了呢?当然不是!


将[7,4]节点沿着X轴平移过去,一看图就知道了,虽然可忽略[7,4]这个节点了,但是因为这个节点的划分轴是Y轴,也就说[7,4]这个节点的左子树的所有点在Y轴上的值都是小于4的,右子树都在Y轴上的值都是大于4的。

那么也就是说,[7,4]的左子树可以忽略了,因为小于4只会让点越来越远离查询点,只有Y轴大于4才有可能靠近查询点,所以得继续查[7,4]的右子树。

好了,整个查询思路就是这样了。其实这里距离的是二维数据的应用,实际上可以应用到很多维数据,我的代码就是可以扩展到多维数据,可以自己调参数。

另外要补充的是,如果要找出与查询点最邻近的N个节点,其实就是在查询过程中得到的结果进行对比,只保存最邻近的5个。

关于往KD树添加新节点

添加节点很简单,每进入一个节点,就按照当前的划分轴,用查询点和节点各自在轴上的值进行对比,查询点的轴值小于节点的轴值的话,就往左子节点继续移动,否则(大于或等于)就往右子节点移动。这样一直查询下去,直到遇到叶子节点,就在叶子节点上加入新值。这个代码我也写好了。

值得注意的是,如果添加太多的数据,接近原数据的三分之一的话,我建议还是从新建立KD树吧,否则会大大降低查询效率,因为这样逐个添加数据生成的树结构,是非常不均衡的。

删除KD树里的节点

实际上删除有点复杂,频繁删除数据的话,搞不好还不如重新建立KD树还快。我建议是将删除节点做个标记,当做已作废,但不需要真正的删除这个节点。当已作废数据有相当多的时候,重新建立KD树。

这里的文字已经够多了,由于代码太多,想要代码的就到我的站点去拿吧,免费~~

另外,下面有些疑问也曾经困惑着我,经过实践,我已经得到了答案了。

建立KD树的过程中,是否一定要将数据对半划分呢?

不是,将数据对半划分,是为了建立一颗比较饱满的树,有利于提高查询速度,如果不将数据对半划分,一样不影响查询结果,只影响查询速度。

建立KD树的过程中,遇到两个或多个完全相同的节点怎么办?

没什么怎么办,根据实际应用场景处理,需要就要,不需要就不要,树里面有多个完全相同的节点,并不影响查询结果的正确性。

建立KD树的过程中,如果不是一次性的将数据全部导入建立,而是将数据分批次,随机的输入建立,会怎么样?

完全没问题,这样做有可能会产生一颗形状比较古怪的树,也有可能会产生一颗比较饱满的树,这些都是无法预料的。我们可以一次拿若干个数据建立一颗KD树,然后再拿一些数据往KD树里面添加,随便~~~最终依然不会影响查询结果的正确性,只影响查询速度

什么?你不信?不信你等着看,就拿上面的数据打乱后,以X轴作为初始划分轴,逐个输入,输入顺序为:[5,9],[3,0],[7,8],[6,0],[5,8],[8,1],[7,4],最终产生的树结构是:



对查询结果的正确性有什么影响吗?毫无问题~~就这样~~程序输出:



如何快速的建立一个饱满合理的KD树?

方法很多,有预先对每一维的数值进行排列,也有随机抽取数据,一批批的添加,也有利用堆栈树来做,等等,目前我也没试过这些,我以后试出来之后再分享出来,目前我的代码里采用最原始的方法去建立KD树,速度是比较慢的。

另外,整棵树的根节点的初始划分轴,最好是选方差最大的维度,方差越大代表数据越分散,这有利于查询。

代码如下:

#include <stdlib.h>
#include <memory.h>
#include <stdio.h>
#include <iostream.h>
#include <time.h>
#include <math.h>


// 三维数组,可改成多维数组 aryValue[4],aryValue[6]等等
typedef int aryValue[3];

// 树节点结构
typedef struct _TreeNode{
aryValue NodeKey; // 节点值
int Depth; // 子树的最大深度值
_TreeNode* left; // 左子节点
_TreeNode* right; // 右子节点
}TTreeNode, *PTreeNode;

// 对数组里的某个属性计算方差
double GetTheVariance(aryValue* lparyValue, int aryValueCount, int x)
{
double floatResult=0;

if (!lparyValue) return floatResult;

// 先获取总值
unsigned int D=0;
int N=0;
while (N < aryValueCount){
D=D+lparyValue[N][x];
N++;
}

// 再取平均值
int P=D/aryValueCount;

// 累计每一个数跟平均值的差的平方
unsigned int T=0;
unsigned int H=0;
N=0;
while (N < aryValueCount){
int K=lparyValue[N][x] - P;
T=T+K*K;
N++;
// 为防止溢出,累计大于30亿的数值,将提前计算一次,但会带来微小的误差
if (T > 3000000000){
H=H+T/aryValueCount;
T=0;
}
}

if (T > 0) H=H+T/aryValueCount;

floatResult=sqrt(H);

return floatResult;
}


// 计算两个点的距离的平方
int TowPointDistance(aryValue p1,aryValue p2)
{
int intResult=0;

int S=sizeof(aryValue) / sizeof(int);

int N=0;
while (N < S){
int A=p1[N] - p2[N];
intResult=intResult+A*A;
N++;
}

// 注释掉这句话,是因为开方计算耗时,实际上,程序主要是利用距离的长度做对比,没必要进行开方
// intResult=sqrt(intResult);

return intResult;
}

// 将数组按照某个属性进行排序
void SortAryData(aryValue* aryData, int aryDataCount, int x)
{
int L=sizeof(aryValue);

int N=aryDataCount;
while (N > 0){
int M=0;
while (M < N){
int T=aryData[M][x];
int K=M+1;
if (K < N){
if (T > aryData[K][x]){
aryValue S;
memcpy(&S,aryData[M],L);
memcpy(aryData[M],aryData[K],L);
memcpy(aryData[K],&S,L);
}
}
M++;
}
N--;
}
}

/*
采用最原始的方法,逐个对比,找到对近的 K 个数据
*/
typedef struct _ListData{
int D; // 距离
int indx; // 原始数据所在数值的原位置
void* pdata; // 指向数据的指针
_ListData* next; // 指向下一个指针
}TListData, *PListData;

void getNearNode_2(aryValue* lparyValue,int lparyValueCount,aryValue unKnowData, int K)
{
printf("与未知数据的距离 - 样本数据\r\n");

PListData FirstListData=0;

int S=sizeof(aryValue) / sizeof(int);
int N=0;
while (N < lparyValueCount){
// 两点之间的距离
int D=TowPointDistance(unKnowData,lparyValue[N]);

PListData lpListData=new TListData;
lpListData->D=D;
lpListData->indx=N;
lpListData->pdata=lparyValue[N];
lpListData->next=0;

if (FirstListData){
bool bolAdd=false;
PListData P=FirstListData;
PListData P2=0;
while (P){
if (lpListData->D <= P->D){
lpListData->next=P;
if (P2){
P2->next=lpListData;
}
else{
FirstListData=lpListData;
}
bolAdd=true;
break;
}
P2=P;
P=P->next;
}
if (!bolAdd) P2->next=lpListData;
}
else{
FirstListData=lpListData;
}

N++;
}

N=0;
PListData P=FirstListData;
while (P){
N++;
// printf("%lf - ",sqrt(P->D));
printf("%d - ",P->D);
aryValue* pData=(aryValue*)P->pdata;
printf("Data[%d]:",P->indx);
int T=0;
while (T < S) printf(" %d",(*pData)[T++]);
printf("\r\n");
P=P->next;
if (N > 30){
printf("只输出前30位距离最近的数据\r\n");
break;
}
}

}

/*
构建KD树

参数:
lpTreeRootNode: 根节点
Depth: 节点所在层
lparyValue: 存储数据样本的缓冲区
lparyValueCount: 数据样本数量
Dimension: 维度
*/
void KDTreeCreate(PTreeNode* lpTreeRootNode,int Depth,aryValue* lparyValue,int lparyValueCount,int Dimension)
{
Depth++;

// 将集合排序
if (lparyValueCount > 1) SortAryData(lparyValue,lparyValueCount,Dimension);

// 计算中间位置值
int Median=lparyValueCount / 2;

// 但是还不行,因为某维度的数值可能存在多个相同的数值
int C=lparyValue[Median][Dimension];
int N=Median;
while (N > 0){
N--;
if (lparyValue[N][Dimension] >= C){
Median--;
}
else{
break;
}
}

// 得到的中间值成为根节点
PTreeNode lpTreeNode=new TTreeNode;
lpTreeNode->left=0;
lpTreeNode->right=0;
lpTreeNode->Depth=Depth;
memcpy(&lpTreeNode->NodeKey,lparyValue[Median],sizeof(aryValue));
*lpTreeRootNode=lpTreeNode;

// 从下一维度数据开始划分
Dimension++;
if (Dimension >= sizeof(aryValue) / sizeof(int)) Dimension=0;

// 从此数组的中间位置,分成两组

// 小于中间值的成为左边一组
int LeftAryValueCount=Median;
if (LeftAryValueCount > 0){
aryValue* LeftAryValue=lparyValue;
KDTreeCreate(&lpTreeNode->left,Depth,LeftAryValue,LeftAryValueCount,Dimension);
}

// 大于中间值的成为右边一组
int RightAryValueCount=lparyValueCount-Median-1;
if (RightAryValueCount > 0){
aryValue* RightAryValue=lparyValue+Median+1;
KDTreeCreate(&lpTreeNode->right,Depth,RightAryValue,RightAryValueCount,Dimension);
}
}


// 将最近距离值保存进查找结果数组
void AddNearDistance(PListData* ListData,int Distance,PTreeNode lpTreeRootNode,int K)
{
// 找出存储结果数组中的最大值的下标
int ListDataCount=0;
int MaxDistance=0;
int MaxIndx=0;
PListData lpListData=*ListData;
while (lpListData){
if (lpListData->D > MaxDistance){
MaxDistance=lpListData->D;
MaxIndx=ListDataCount;
}
lpListData=lpListData->next;
ListDataCount++;
}

// 数组最多只存储一定量的数据
if (ListDataCount < K){
PListData NewListData=new TListData;
NewListData->D=Distance;
NewListData->indx=0;
NewListData->pdata=lpTreeRootNode;
NewListData->next=*ListData;
*ListData=NewListData;
}
else{
// 大于 K 个,看当前距离值是否小于数组里的最大值,如果大于,替换
if (Distance < MaxDistance){
int T=0;
PListData lpListData=*ListData;
while (lpListData){
if (T==MaxIndx){
lpListData->D=Distance;
lpListData->pdata=lpTreeRootNode;
break;
}
lpListData=lpListData->next;
T++;
}
}
}

}

/*
从 K-d树里找到距离最近的几个节点

参数:
lpTreeRootNode: 树根节点
SearchData: 要查询的数据
Dimension: 查询维度
MinD: 当前最近距离

// 下面的参数在实际项目中可有可无,自己设计更好的数据保存方法
ListData: 用于保存最靠近查询点的几个节点
Se: 用于统计递归执行次数
K: 保存多少个最近的距离
*/
int KDTreeSearchNode(PTreeNode lpTreeRootNode,aryValue SearchData,int Dimension,PListData* ListData,int* MinD,int *Se,unsigned int K)
{
int intResult=0;

if (!lpTreeRootNode || !SearchData) return intResult;

// 累计执行次数
*Se=*Se+1;

// 下一个节点所代表的属性划分点
int L=sizeof(aryValue) / sizeof(int);
int NextDimension=Dimension+1;
if (NextDimension >= L) NextDimension=0;

// 当前节点的属性值
int NodeDimensionValue=lpTreeRootNode->NodeKey[Dimension];
// 查询点的属性值
int SearchDimensionValue=SearchData[Dimension];

// 计算当前节点与查询点的距离
int Distance=TowPointDistance(lpTreeRootNode->NodeKey,SearchData);

// 将当前点的距离放入数组里
AddNearDistance(ListData,Distance,lpTreeRootNode,K);

// 如果当前节点距离小于等于最短距离,那么将当前点设置为最近点,MinD 值为负数表示无限大
if ((*MinD < 0) || (Distance <= *MinD)) *MinD=Distance;

// 当前节点对应的维度,与查询点对应的维度的距离
int D=SearchDimensionValue - NodeDimensionValue;
D=D*D;

// 查看左右子节点是否有在范围内
if (D <= *MinD){
if (lpTreeRootNode->left) KDTreeSearchNode(lpTreeRootNode->left,SearchData,NextDimension,ListData,MinD,Se,K);
if (lpTreeRootNode->right) KDTreeSearchNode(lpTreeRootNode->right,SearchData,NextDimension,ListData,MinD,Se,K);
}
else{
if ((NodeDimensionValue < SearchDimensionValue) && lpTreeRootNode->right)
KDTreeSearchNode(lpTreeRootNode->right,SearchData,NextDimension,ListData,MinD,Se,K);

if ((NodeDimensionValue > SearchDimensionValue) && lpTreeRootNode->left)
KDTreeSearchNode(lpTreeRootNode->left,SearchData,NextDimension,ListData,MinD,Se,K);
}

return intResult;
}

/*
增加节点,有一个特殊情况需要根据实际需要处理,如果新添加的数据与某个节点完全相同,应该根据实际应用场景来决定是否允许,
但是无论如何处理,都不会影响程序的运算结果的正确性。
*/

void KDTreeAddData(PTreeNode* RootNode,aryValue newData,int Dimension)
{
if (!*RootNode){
PTreeNode lpTreeNode=new TTreeNode;
lpTreeNode->left=0;
lpTreeNode->right=0;
lpTreeNode->Depth=1;
memcpy(&lpTreeNode->NodeKey,newData,sizeof(aryValue));
*RootNode=lpTreeNode;
return;
}

// 下一个节点所代表的属性划分点
int L=sizeof(aryValue) / sizeof(int);
int NextDimension=Dimension+1;
if (NextDimension >= L) NextDimension=0;

PTreeNode lpTreeRootNode=*RootNode;

// 当前节点的属性值
int NodeDimensionValue=lpTreeRootNode->NodeKey[Dimension];
// 查询点的属性值
int newDimensionValue=newData[Dimension];

bool bolAdd=false;
PTreeNode* AddRootNode=0;
if (newDimensionValue < NodeDimensionValue){
// 新数据的属性值小于当前节点的属性值,进入左子树
if (lpTreeRootNode->left){
KDTreeAddData(&lpTreeRootNode->left,newData,NextDimension);
}
else{
bolAdd=true;
AddRootNode=&lpTreeRootNode->left;
}
}
else{
// 新数据的属性值大于或等于当前节点的属性值,进入右子树
if (lpTreeRootNode->right){
KDTreeAddData(&lpTreeRootNode->right,newData,NextDimension);
}
else{
bolAdd=true;
AddRootNode=&lpTreeRootNode->right;
}
}

if (bolAdd){
PTreeNode lpTreeNode=new TTreeNode;
lpTreeNode->left=0;
lpTreeNode->right=0;
lpTreeNode->Depth=lpTreeRootNode->Depth + 1;
memcpy(&lpTreeNode->NodeKey,newData,sizeof(aryValue));
*AddRootNode=lpTreeNode;
}
}

// 将整颗树的数据显示出来
typedef struct _NodeLink{
int FValue; // 父节点的编号
int Depth; // 层次
int location; // 位置,1 左边;2 右边
_TreeNode* TreeNode; // 指向一个树的节点
_NodeLink* next; // 下一个结构 TNodeLink
}TNodeLink, *PNodeLink;

void PrintfTree(PTreeNode RootNode)
{
// 采用广度优先遍历

if (!RootNode) return;

printf("当前树结构\r\n");

PNodeLink lpNodeLink=new TNodeLink;
lpNodeLink->Depth=0;
lpNodeLink->next=0;
lpNodeLink->FValue=0;
lpNodeLink->TreeNode=RootNode;

int NodeCount=0;

int N=0;
while (lpNodeLink){
if (N != lpNodeLink->Depth){
N=lpNodeLink->Depth;
printf("\r\n");
}

char strLocation[32]={0};
if (lpNodeLink->location==1) sprintf(strLocation,"-Left");
if (lpNodeLink->location==2) sprintf(strLocation,"-Right");

printf("[#%d%s,(",lpNodeLink->FValue,strLocation);

int T=0;
while (T < (sizeof(aryValue) / sizeof(int))) printf("%d ",lpNodeLink->TreeNode->NodeKey[T++]);
printf("),#%d,%d] ",NodeCount,lpNodeLink->TreeNode->Depth);

// 将树节点的左右子节点加入队列后面
if ( (lpNodeLink->TreeNode->left) || (lpNodeLink->TreeNode->right) ){

PNodeLink LeftNodeLink=0;
if (lpNodeLink->TreeNode->left){
LeftNodeLink=new TNodeLink;
LeftNodeLink->Depth=lpNodeLink->Depth + 1;
LeftNodeLink->next=0;
LeftNodeLink->FValue=NodeCount;
LeftNodeLink->location=1;
LeftNodeLink->TreeNode=lpNodeLink->TreeNode->left;
}

PNodeLink RightNodeLink=0;
if (lpNodeLink->TreeNode->right){
RightNodeLink=new TNodeLink;
RightNodeLink->Depth=lpNodeLink->Depth + 1;
RightNodeLink->next=0;
RightNodeLink->FValue=NodeCount;
RightNodeLink->location=2;
RightNodeLink->TreeNode=lpNodeLink->TreeNode->right;
}

if (LeftNodeLink){
LeftNodeLink->next=RightNodeLink;
}
else{
LeftNodeLink=RightNodeLink;
}

if (LeftNodeLink){
PNodeLink NextNodeLink=lpNodeLink;
while (NextNodeLink){
if (!NextNodeLink->next){
NextNodeLink->next=LeftNodeLink;
break;
}
NextNodeLink=NextNodeLink->next;
}
}

NodeCount++;
}


PNodeLink DelNodeLink=lpNodeLink;
lpNodeLink=lpNodeLink->next;
/*
之所以注释掉下面这句话,是因为Windows系统,频繁的申请和释放小内存块,会造成内存泄漏,
从而导致程序崩溃,在实际开发中,应考虑内存池的方法
*/
// delete DelNodeLink;
}


printf("\r\n========================================\r\n");
}

int main()
{
// 随机生成若干个多维数据,作为样本
printf("输入要生成的随机样本数量:");
int lparyValueCount=0;
cin>>lparyValueCount;
if (lparyValueCount <= 0) return 0;

aryValue* lparyValue=new aryValue[lparyValueCount];

int MaxNumber=9000;
srand(time(0));
int L=sizeof(aryValue) / sizeof(int);
int N=0;
while (N < lparyValueCount){
int T=0;
while (T < L) lparyValue[N][T++]=rand()%MaxNumber;
N++;
}

// 对样本数据,计算每个维度的方差,最终选择方差最大的维度,作为切分点
N=0;
double MinF=0;
int SelectN=0;
while (N < L){
double F=GetTheVariance(lparyValue,lparyValueCount,N);
if (F > MinF){
SelectN=N;
MinF=F;
}
N++;
}

// 再随机生成一个未知数据
printf("要查询的数据(%d维度,用%d属性作为起始分割):",L,SelectN);
aryValue unKnowData={0};
N=0;
while (N < L){
unKnowData[N]=rand()%MaxNumber;
printf(" %d",unKnowData[N]);
N++;
}
printf("\r\n");


// 构造KD树
PTreeNode TreeRootNode=0;
KDTreeCreate(&TreeRootNode,0,lparyValue,lparyValueCount,SelectN);

// 往KD树添加数据
// aryValue newData={1,2,3};
// KDTreeAddData(&TreeRootNode,newData,SelectN);

// 显示树结构
// PrintfTree(TreeRootNode);

// 采用最原始的方法,逐个计算对比,得出的结果按距离从小到大进行排序
getNearNode_2(lparyValue,lparyValueCount,unKnowData,10);

// 查询KD树
PListData ListData=0;
int MinD=-1;
int Se=0;
KDTreeSearchNode(TreeRootNode,unKnowData,SelectN,&ListData,&MinD,&Se,5);

// 打印查询结果
printf("\r\n方式2查询次数%d次,查询结果:\r\n",Se);
while (ListData){
printf("%d ",ListData->D);
ListData=ListData->next;
}


delete[] lparyValue;

int inputvalue=0;
cin>>inputvalue;

return 0;
}
留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

名称

Email

内容

预览(只读), 点击返回编辑.

 
最新文章
 
留言
版权所有 © 2020 mypcrun.com.
桂ICP备19002156号桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。