寻找算法:按“相似度”聚类

Question

我有一组“向量”，我需要根据它们的“相似性”对它们进行排序。

像这样:向量{1, 0，0} {1,1,0} { 0，1,0}非常相似，最后应该彼此接近，但向量{1，0，0} {8，0，0} {0，5，0} -不是。

A和B之间的度量是max(abs(Ai-Bi))，但是什么样的算法可以基于相对比较对事物进行排序？

upd:输入:N个向量的数组

输出:N个向量的数组，其中最近的索引向量(例如arri arri+1 )是'similiar‘=arri和arri+1之间的度量对于任何i，j都尽可能低。

度量-向量分量的最大差

upd2:现在看来，@jogojapan是对的--我需要对向量进行聚类，然后按线性顺序逐组打印它们

Answer 1

这是由max norm (aka sup norm or l-infinity norm)引起的距离。如果排序是指序列中的排序，那么距离不足以创建线性排序。

Answer 2

排序本质上是一个一维问题。你在这里描述的听起来更像是一个加权图，但它不清楚你的目标是什么。如果您试图识别与已知向量“最接近”的向量，您可能还会发现信息论中的一些概念(如Hamming Distance )非常有用。

Answer 3

嗯，最明显的方法是(名字不好)“层次聚类”，它总是合并距离最小的集群。您可以在那里插入您的指标。大多数实现都是O(n^3)，因此对大型数据集没有用处。另外，你会得到一个很难读懂的巨大的树状图。

你可能想尝试一下光学技术。在维基百科上查一查。它可能会很好地满足您的需求，因为它实际上对点进行了排序。它将从一个集群遍历到另一个集群，并且实际上可以产生分层(如“嵌套”)的集群。一个好的实现应该在没有索引结构的O(n^2)和具有索引加速的O(n log n)中运行。