寻找算法：通过“相似性”聚类

我有一组“向量”，我需要根据它们的“相似性”对它们进行排序。寻找算法：通过“相似性”聚类

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

A和B之间的度量标准是max（abs（A [i] -B [i]）），但是什么样的算法可以根据相对比较来分类？

UPD：输入：N矢量的阵列
输出中：N矢量，其中通过索引向量最接近（ARR [I] ARR [I + 1]例如）都是 'similiar'=度量之间ARR [阵列i]和arr [i + 1]对于任何i，j来说都尽可能低。
指标 - 矢量分量的最大区别

UPD2：因为现在看来，@jogojapan是对的 - 我需要按组

2012-04-16 ShPavel

定义“排序”是什么意思...你有一个指标吗？你想最小化相邻向量之间的距离之和吗？ – 2012-04-16 12:51:10

也许你的意思是[集群]（http://en.wikipedia.org/wiki/Cluster_analysis）（即分组），而不是排序？ – jogojapan 2012-04-16 12:56:59

让我改述我的评论：如果你有两个订单，你怎么能决定哪一个更好？ “应该接近每个”是不是一个定义... – 2012-04-16 13:06:00

这是一个集群的载体之后，在一些线性顺序打印出来，组由max norm (aka sup norm or l-infinity norm)引起的距离。如果按顺序排序意味着排序，则距离不足以创建线性排序。

2012-04-16 12:53:20 Memming

没有理由不能按距离原点排序。 – Marcin 2012-04-16 12:55:01

@Marcin可能。但我怀疑这是user286215想要的。他说'相对比较'。 – Memming 2012-04-16 12:56:37

-1

任何排序算法可以给你你想要的结果。

问题是你如何比较你的载体。你只是想比较它们的大小？或者是其他东西？

2012-04-16 12:54:13 Marcin

这就是问题所在，我无法比较矢量，但是对于任何给定的对，我可以告诉他们'相似'是他们 – ShPavel 2012-04-16 12:59:49

@ user286215所以，你没有问题。只要您可以测试它们是否更大，更小或相等，则任何排序算法都可以工作。 – Marcin 2012-04-16 13:01:22

“只要你能测试它们是更大，更小还是相等” - 好吧，这就是比较的定义。他只是说他无法比较......或者从另外一个角度来看：如果他比较他们，那么他肯定不会达到他的目标。 – 2012-04-16 13:04:24

排序本质上是一个一维问题。你在这里描述的听起来更像一个加权图，但目前还不清楚你的目标是什么。如果您试图识别与已知矢量“最接近”的矢量，您也可以从信息论中找到一些概念，例如Hamming Distance。

2012-04-16 12:56:33

那么，显而易见的方法是（层出不穷的）“层次聚类”，它总是合并那些距离最短的聚类。你可以在那里插入你的指标。大多数实现都在O（n^3）中，因此对于大型数据集无用。另外，你会得到一个难以阅读的巨大树状图。

您可能想给OPTICS一个尝试。在维基百科上查找它。它可能会满足你的需求相当好，因为它实际上排序的点。它将从一个集群走到另一个集群，实际上可以产生一个分层结构（如“嵌套”）集群。一个好的实现应该在不带索引结构的O（n^2）中运行，并且在带索引加速的O（n log n）中运行。

2012-04-18 04:31:43

回答