如何进行n维空间划分？
我正在尝试将矢量量化的实现设计为 C++ 模板类，它可以处理不同类型和维度的向量（例如字节的 16 维向量或双精度的 4d 向量等）。
我一直在阅读算法，并且了解其中的大部分：
我想实现 Linde-Buzo-Gray (LBG) 算法，但我很难弄清楚用于分区集群的通用算法。我想我需要定义一个平面（超平面？），它将向量分割成一个簇，这样平面的每一侧都有相同的数量。
[编辑以添加更多信息] 这是一个迭代过程，但我想我首先找到所有向量的质心，然后使用该质心定义分割平面，获取平面每条边的质心，继续直到获得簇数VQ 算法所需（迭代以优化以减少失真）。上面第一个链接中的动画很好地展示了这一点。
我的问题是：
一旦有了质心，找到平面的算法是什么？
如何测试矢量以查看它是否位于该平面的任一侧？
I'm trying to design an implementation of Vector Quantization as a c++ template class that can handle different types and dimensions of vectors (e.g. 16 dimension vectors of bytes, or 4d vectors of doubles, etc).
I've been reading up on the algorithms, and I understand most of it:
I want to implement the Linde-Buzo-Gray (LBG) Algorithm, but I'm having difficulty figuring out the general algorithm for partitioning the clusters. I think I need to define a plane (hyperplane?) that splits the vectors in a cluster so there is an equal number on each side of the plane.
[edit to add more info]
This is an iterative process, but I think I start by finding the centroid of all the vectors, then use that centroid to define the splitting plane, get the centroid of each of the sides of the plane, continuing until I have the number of clusters needed for the VQ algorithm (iterating to optimize for less distortion along the way). The animation in the first link above shows it nicely.
My questions are:
What is an algorithm to find the plane once I have the centroid?
How can I test a vector to see if it is on either side of that plane?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您从一个质心开始，那么您必须将其分割，基本上是通过将其加倍并在任意方向上稍微移动点分开。该平面就是与该方向正交的平面。
但您不需要计算该平面。
更一般地，区域(i)被定义为比任何其他质心更接近质心c_i的点的集合。当有两个质心时，每个区域都是半空间，因此由（超）平面分隔。
如何测试向量 x 以查看它在平面的哪一侧？ （有两个质心）
只需计算距离 ||x-c1||和 ||x-c2||，最小值的索引（1 或 2）将给出点 x 属于哪个区域。
更一般地，如果您有 n 个质心，您将计算所有距离 ||x-c_i||，并且最接近的质心 x（即距离最小）将为您提供 x 所属的区域。
If you start with one centroid, then you'll have to split it, basically by doubling it and slightly moving the points apart in an arbitrary direction. The plane is just the plane orthogonal to that direction.
But you don't need to compute that plane.
More generally, the region (i) is defined as the set of points which are closer to the centroid c_i than to any other centroid. When you have two centroids, each region is a half space, thus separated by a (hyper)plane.
How to test on a vector x to see on which side of the plane it is? (that's with two centroids)
Just compute the distance ||x-c1|| and ||x-c2||, the index of the minimum value (1 or 2) will give you which region the point x belongs to.
More generally, if you have n centroids, you would compute all the distances ||x-c_i||, and the centroid x is closest to (i.e., for which the distance is minimal) will give you the region x is belonging to.
我不太明白这个算法，但第二个问题很简单：
让我们称V为一个向量，它从平面上的任何点延伸到 > 问题点。那么问题点位于（超）平面与法线 N 的同一侧，当且仅当 V·N > 0
I don't quite understand the algorithm, but the second question is easy:
Let's call V a vector which extends from any point on the plane to the point-in-question. Then the point-in-question lies on the same side of the (hyper)plane as the normal N iff V·N > 0