编程技术是改变世界的力量。
本站
当前位置:网站首页 > 后端语言 > 正文

如何利用 C# 实现 K-D Tree 结构?

gowuye 2024-05-16 14:16 3 浏览 0 评论

我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选,但她没有从中找到喜欢的人。经过一番总结,她发现曾交往过三种类型的人:

  • 不喜欢的人
  • 魅力一般的人
  • 极具魅力的人

尽管发现了上述规律,但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人,而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息,她认为这些数据更有助于匹配对象的归类。

海伦收集约会数据已经有一段时间,她把这些数据存放在文本文件datingTestSet.txt中,每个样本占据一行,总共有1000行。海伦的样本主要包含以下3种特征:

  • 每年获得的飞行常客里程数
  • 玩视频游戏所耗费时间百分比
  • 每周消费的冰激凌公升数

以上是《机器学习实战》中介绍 K 最邻近算法给出的示例,通过该示例我们可以了解到 K 最邻近算法应用的另一个场景:改善约会网站的配对效果。本次介绍 K-D 树是为了加速寻找给定节点的邻居节点,是提升 K 最邻近算法执行效率的一种改进。


我们首先介绍一下 K-D 树的基本原理,由于篇幅的限制,详细的理论部分可以参见对应的维基百科。

K-D

K-D 树(K 维树的简称)是一种用于在 K 维空间中组织点的空间划分数据结构。K-D 树是非常有用的一种数据结构,常用于涉及多维搜索键的搜索(比如,范围搜索和邻近搜索)。

K-D 树是一个二叉树,其中每个节点都是一个 K 维点。每个非叶节点都可以被认为是隐式生成一个分裂超平面,将空间分成两部分,称为半空间。该超平面左侧的点表示该节点的左子树,而该超平面右侧的点则表示为右子树。超平面方向的选择方法如下:树中的每个节点都与一个 K 维相关联,超平面垂直于该维的轴。因此,例如,如果对特定的拆分选择了 X 轴,则子树中所有 X 值小于节点的点都将显示在左子树中,而所有 X 值较大的点都将显示在右子树中。在这种情况下,超平面将由点的 X 值设置,其法向量为单位 X 轴。

更详细的介绍,见维基百科:

https://en.wikipedia.org/wiki/K-d_tree

K-D树

麦哈顿距离

更详细的介绍,见维基百科:

https://en.wikipedia.org/wiki/Taxicab_geometry

麦哈顿距离


有了以上的基础,我们首先来定义 K-D 树节点的结构,然后定义邻居节点的结构,以及麦哈顿距离,最后给出 K-D 树的结构以及具体应用。

1. 定义K-D 树节点的结构

public class KDTreeNode<T>
{
 //分割轴
 public int Axis { get; set; }
 //节点值
 public double[] Position { get; set; }
 //标签值
 public T Value { get; set; }
 //左子树
 public KDTreeNode<T> Left { get; set; }
 //右子树
 public KDTreeNode<T> Right { get; set; }
 //是否为叶子节点
 public bool IsLeaf
 {
 get { return Left == null && Right == null; }
 }
}

2. 定义邻居节点的结构

public struct KDTreeNodeDistance<T> : IComparable, IComparable<KDTreeNodeDistance<T>>, IEquatable<KDTreeNodeDistance<T>>
{
 public double Distance { get; }
 public KDTreeNode<T> Node { get; }
 public KDTreeNodeDistance(KDTreeNode<T> node, double distance)
 {
 this.Node = node;
 this.Distance = distance;
 }
 public int CompareTo(object obj)
 {
 return Distance.CompareTo((KDTreeNodeDistance<T>)obj);
 }
 public int CompareTo(KDTreeNodeDistance<T> other)
 {
 return Distance.CompareTo(other.Distance);
 }
 public bool Equals(KDTreeNodeDistance<T> other)
 {
 return Distance == other.Distance && Node == other.Node;
 }
}

3. 定义麦哈顿距离

public sealed class Manhattan : IMetric<double[]>
{
 public double Distance(double[] x, double[] y)
 {
 double sum = 0.0;
 for (int i = 0; i < x.Length; i++)
 sum += Math.Abs(x[i] - y[i]);
 return sum;
 }
}

4. 定义 K-D 树的结构

public class KDTree<T> : IEnumerable<KDTreeNode<T>>
{
 //距离
 public IMetric<double[]> Distance { get; set; } = new Euclidean();
 //树根
 public KDTreeNode<T> Root { get; }
 //节点个数
 public int Count { get; }
 //叶子节点个数
 public int Leaves { get; }
 //节点维数
 public int Dimensions { get; }
 public KDTree(double[][] points, T[] values, IMetric<double[]> distance, bool inPlace = false)
 {
 if (points == null)
 throw new ArgumentNullException();
 if (points.Length == 0)
 throw new ArgumentException("创建树的点数不足。");
 if (values == null)
 throw new ArgumentNullException();
 if (distance == null)
 throw new ArgumentNullException();
 int leaves;
 Root = CreateRoot(points, values, inPlace, out leaves);
 Leaves = leaves;
 Distance = distance;
 Dimensions = points[0].Length;
 Count = points.Length;
 }
 public KDTree(double[][] points, bool inPlace = false)
 {
 if (points == null)
 throw new ArgumentNullException();
 if (points.Length == 0)
 throw new ArgumentException("创建树的点数不足。");
 int leaves;
 Root = CreateRoot(points, null, inPlace, out leaves);
 Leaves = leaves;
 Dimensions = points[0].Length;
 Count = points.Length;
 }
 protected KDTreeNode<T> CreateRoot(double[][] points, T[] values, bool inPlace, out int leaves)
 {
 if (points == null)
 throw new ArgumentNullException();
 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 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);
 int half = start + length/2;
 int leftStart = start;
 int leftLength = half - start;
 int rightStart = half + 1;
 int rightLength = length - length/2 - 1;
 double[] median = points[half];
 T 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++;
 return new KDTreeNode<T>()
 {
 Axis = axis,
 Position = median,
 Value = value,
 Left = left,
 Right = right,
 };
 }
 private void Nearest(KDTreeNode<T> current, double[] position, KDTreeNodeCollection<T> list)
 {
 double d = Distance.Distance(position, current.Position);
 list.Add(current, d);
 double value = position[current.Axis];
 double median = current.Position[current.Axis];
 double u = value - median;
 if (u <= 0)
 {
 if (current.Left != null)
 Nearest(current.Left, position, list);
 if (current.Right != null && Math.Abs(u) <= list.Maximum)
 Nearest(current.Right, position, list);
 }
 else
 {
 if (current.Right != null)
 Nearest(current.Right, position, list);
 if (current.Left != null && Math.Abs(u) <= list.Maximum)
 Nearest(current.Left, position, list);
 }
 }
 private void Nearest(KDTreeNode<T> current, double[] position,double radius, ICollection<KDTreeNodeDistance<T>> list)
 {
 double d = Distance.Distance(position, current.Position);
 if (d <= radius)
 list.Add(new KDTreeNodeDistance<T>(current, d));
 double value = position[current.Axis];
 double median = current.Position[current.Axis];
 double u = value - median;
 if (u <= 0)
 {
 if (current.Left != null)
 Nearest(current.Left, position, radius, list);
 if (current.Right != null && Math.Abs(u) <= radius)
 Nearest(current.Right, position, radius, list);
 }
 else
 {
 if (current.Right != null)
 Nearest(current.Right, position, radius, list);
 if (current.Left != null && Math.Abs(u) <= radius)
 Nearest(current.Left, position, radius, list);
 }
 }
 public KDTreeNodeCollection<T> Nearest(double[] position, int neighbors)
 {
 KDTreeNodeCollection<T> list = new KDTreeNodeCollection<T>(neighbors);
 if (Root != null)
 Nearest(Root, position, list);
 return list;
 }
 public KDTreeNodeList<T> Nearest(double[] position, double radius)
 {
 KDTreeNodeList<T> list = new KDTreeNodeList<T>();
 if (Root != null)
 Nearest(Root, position, radius, list);
 return list;
 } 
 public IEnumerator<KDTreeNode<T>> GetEnumerator()
 {
 if (Root == null)
 yield break;
 Stack<KDTreeNode<T>> stack = new Stack<KDTreeNode<T>>(new[] {Root});
 while (stack.Count != 0)
 {
 KDTreeNode<T> current = stack.Pop();
 yield return current;
 if (current.Left != null)
 stack.Push(current.Left);
 if (current.Right != null)
 stack.Push(current.Right);
 }
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
} 

5. K-D 树的应用

假设我们拥有以下点的集合:

double[][] points =
{
 new double[] {2, 3},
 new double[] {5, 4},
 new double[] {9, 6},
 new double[] {4, 7},
 new double[] {8, 1},
 new double[] {7, 2},
};

从这些数据点中创建K-D 树:

KDTree<int> tree = new KDTree(points);

我们可以手动导航这颗树:

KDTreeNode<int> node = tree.Root.Left.Right;

或者自动遍历这棵树,由于 KDTree<T> 实现了枚举器也即实现了迭代器模式,所以可以用 foreach 来遍历这棵树的数据。但对于普通的二叉树来说,通常使用前序遍历、中序遍历、后序遍历或者层次遍历的方式进行。

foreach (KDTreeNode<int> n in tree)
{
 double[] location = n.Position;
 Console.WriteLine(@"({0},{1})", location[0], location[1]);
}

可以得到如下的结果:

(7,2)
(9,6)
(8,1)
(5,4)
(4,7)
(2,3)

给定一个查询点(例如:(5,3)),我们还可以查询半径(欧氏距离 4.0)内靠近该点的其它点。

double[] query = new double[] {5, 3};
KDTreeNodeList<int> result = tree.Nearest(query, 4.0);
for (int i = 0, len = result.Count; i < len; i++)
{
 KDTreeNode<int> node = result[i].Node;
 Console.WriteLine(@"({0},{1})", node.Position[0], node.Position[1]);
}

可以得到如下的结果:

(7,2)
(5,4)
(2,3)
(8,1)

我们也可以使用其它的距离度量,比如麦哈顿距离:

double[] query = new double[] {5, 3};
tree.Distance = new Manhattan();
KDTreeNodeList<int> result = tree.Nearest(query, 4.0);
for (int i = 0, len = result.Count; i < len; i++)
{
 KDTreeNode<int> node = result[i].Node;
 Console.WriteLine(@"({0},{1})", node.Position[0], node.Position[1]);
}

可以得到如下的结果:

(7,2)
(5,4)
(2,3)

以及查询固定数量的相邻点,比如

KDTreeNodeCollection<int> neighbors = tree.Nearest(query, 3);
for (int i = 0, len = neighbors.Count; i < len; i++)
{
 KDTreeNode<int> node = neighbors[i].Node;
 Console.WriteLine(@"({0},{1})", node.Position[0], node.Position[1]);
}

可以得到如下的结果:

(5,4)
(2,3)
(7,2)

到此为止,用 C# 实现 K-D 树就介绍完了。在后台回复 20190312 可以得到,本篇开头说的 网站约会信息的数据集。大家把上面的代码看懂后,可以尝试的写一下,然后用这个数据集来测试自己的代码。

今天就到这里吧!See You!

相关推荐

Nginx 响应提速10倍,你需要知道的缓存性能优化——FastCGI调优
Nginx 响应提速10倍,你需要知道的缓存性能优化——FastCGI调优

Nginx缓存优化是帮助大家提升网站性能的重要操作之一,proxy_cache主要用于反向代理时,对后端内容源服务器进行缓存;fastcgi_cache主要用于...

2024-05-20 14:44 gowuye

王者荣耀天魔缭乱和逐梦之音返场活动地址 3月22日开启返场活动
王者荣耀天魔缭乱和逐梦之音返场活动地址 3月22日开启返场活动

王者荣耀官方终于确定了天魔缭乱和逐梦之音的返场活动,这让不少小伙伴乐开了花,返场活动将会在3月22日开启,下面就带来王者荣耀天魔缭乱和逐梦之音返场活动地址!王者...

2024-05-20 14:44 gowuye

常见的嵌入式web服务器有哪些?

嵌入式WEB服务器常见的有:Lighttpd,Shttpd,Thttpd,Boa,Mini_httpd,Appweb,Goahead。Lighttpd地址:http://www.light...

简述几款常见的嵌入式web服务器
简述几款常见的嵌入式web服务器

嵌入式web服务器,是web服务器当中的一种,是基于嵌入式系统而实现的web服务器。指的是在嵌入式系统(通俗点就是单片机系统)上实现的一个web服务器,可以通过...

2024-05-20 14:44 gowuye

教你如何利用fastcgi_cache缓存加速WordPress

在使用nginx缓存之前,必须在nginx里面加载专门的模块,这个模块叫做ngx_cache_purge。添加ngx_cache_purge模块下载ngx_cache_purge模块ngx_cache...

扫描WordPress漏洞

检测已知漏洞WPScan是一款广泛使用的WordPress安全扫描工具,它的一项重要功能是检测已知漏洞。在这篇文章中,我们将深入探讨WPScan如何检测已知漏洞,并结合实际示例,帮助读者更好地理解和应...

消灭 Bug!推荐几个给力的开源 Bug 跟踪工具
消灭 Bug!推荐几个给力的开源 Bug 跟踪工具

在这个充满bug的世界里,最遥远的距离不是生与死,而是你亲手制造的bug就在你眼前,你却怎么都找不到它。因此本文准备了7款优秀的开源bug跟踪系...

2024-05-20 14:43 gowuye

生物信息分析入门全攻略

生物信息学是生命科学研究的重大前沿领域,未来将占据生命科学研究的半壁江山。已经有越来越多的小伙伴投入到生物信息的学习中,但是入门难、深入慢、摸不到方向等都成为持续学习的拦路虎。本文根据生物信息技术大牛...

elkb实践经验,再赠送一套复杂的配置文件
elkb实践经验,再赠送一套复杂的配置文件

原创:小姐姐味道(微信公众号ID:xjjdog),欢迎分享,转载请保留出处。宝剑锋从磨砺出,梅花香自苦寒来。诗人白居易,三月下江南,看到沿路开放的桃花,心潮澎湃...

2024-05-20 14:43 gowuye

超详细从0到1 搭建ELK监控
超详细从0到1 搭建ELK监控

监控分类?Metrics用于记录可聚合的数据。例如,1、队列的当前深度可被定义为一个度量值,在元素入队或出队时被更新;HTTP请求个数可被定义为一个计数器,...

2024-05-20 14:42 gowuye

嵌入式开发 之Web配置页面开发
嵌入式开发 之Web配置页面开发

1.PHP是最好的语言??开发动态页面首选的语言是PHP,村村不能在这里忽悠人,如果你的硬件性能允许切略懂PHP,看到这里就可以退出了。本文面向的受众是Linu...

2024-05-20 14:42 gowuye

Python开发一个网站目录扫描工具用来检测网站是否有漏洞?
Python开发一个网站目录扫描工具用来检测网站是否有漏洞?

开发一个网站目录扫描工具是用来检测网站是否有非法目录请求的一个常见需求之一,我们要通过这个扫描工具来找到通过某个域名可以访问到的网站路径,可能对于有些系统来讲,...

2024-05-20 14:42 gowuye

创建一个类似Youtube的Id——使用PHP/Python/JS/Java/SQL

id通常都是用数字,不巧的是只有10个数字来使用,所以如果你有很多的记录,id往往变得非常冗长。当然对于计算机来说无所谓,但我们更希望id尽可能短。所以我们如何能使id变短?我们可以利用字母让它们附加...

快速云:有助于移动应用安全开发的五条妙计
快速云:有助于移动应用安全开发的五条妙计

许多企业不断地向其开发团队提供培训。但是某些漏洞,如早在十多年前就发现的SQL注入,如今仍广泛存在于各种应用中。因而,安全培训永不过时。在开发移动应用时,开发者...

2024-05-20 14:41 gowuye

洛杉矶国际电影节最佳动画短片奖影片《G’DAY》正式全网上映
洛杉矶国际电影节最佳动画短片奖影片《G’DAY》正式全网上映

7月2日,由M&CSaatchi创作,由深受好评的澳大利亚导演迈克尔·格雷西执导的动画短片《G’day》,正式在全网上映。该影片因其出色的创意赢得了洛...

2024-05-20 14:41 gowuye

取消回复欢迎 发表评论: