4

如何对一堆 N x M 二进制矩阵进行排序，以便最相似的是双向链表中的邻居？

我有一组二维二进制矩阵，我需要有效地对某些数据结构中的矩阵集进行排序，以便彼此最相似的矩阵在数据结构中是彼此的“邻居”。我认为地图结构不会高效，因为我有近 40,000 个矩阵需要有效查找。

我的两个矩阵之间距离的公式是

getSimilarity(matrix toCompare)
    //initialize variable "sum" to 0
    //for each rowT in this and each rowC in toCompare
      //sum += max(rowT,rowC) - bitwiseAnd(rowT,rowC)
    // return sum

我什至不需要你给我一个数据结构，我所需要的只是一种比较两个矩阵的方法，它可以让我得到相似矩阵尽可能靠近彼此聚集的结果。

编辑：2012 年 12 月 19 日下午 1:52 我的行代表用户属性，我的列代表页面属性。每个矩阵表示用户具有哪些属性同时还具有某些页面属性（例如用户的年龄小于 42 并且他们访问过第 4 页）

4

3 回答 3

4

我注意到矩阵上的相似性运算符定义了一个度量空间。那是：

  • D(M1, M2) = 0 当且仅当 M1 = M2
  • 对于任何 M1、M2，D(M1, M2) ≥ 0。
  • D(M1, M2) = D(M2, M1)，并且
  • D(M1, M3) ≤ D(M1, M2) + D(M2, M3)（三角不等式）

因此，可以想象存储所有数据的一种方法是在度量空间树中，这是一种用于在度量空间中存储对象的数据结构，可以轻松查找“接近”某个初始值的所有元素元素。

您的数据还有一个额外的优势，即它是一个离散的度量空间，这意味着您提供的距离函数始终输出一个完整的答案。也就是说，你不会有两个相距 1.5 的矩阵，也不能有两个相距 π 的矩阵

因此，您可能希望将矩阵存储在BK-tree中。BK-tree 通常用于存储字符串，但更普遍的是可以将元素存储在任何离散的度量空间中。这使得可以合理有效地对单个矩阵进行最近邻搜索（通常无需查看集合中的所有矩阵），尽管不可否认，它不会将双向链表穿过所有元素。

直观地说，BK-tree 的结构如下。选择您选择的矩阵作为“根节点”。然后，将集合中的每个矩阵与根矩阵进行比较，并根据它们与根矩阵的距离将它们分配到子树中。然后，您以相同的方式递归地细分这些子树中的每一个。由于三角不等式，您可以使用简单的递归算法在 BK 树中搜索附近的矩阵。

希望这可以帮助！

于 2012-12-18T01:16:07.433 回答
1

我不明白你的相似函数。不应该将行与行进行比较吗？此外，一般来说，更高的 bitwiseAnd 意味着更高的相似性，而对于你来说，它有减号。

通常使用局部敏感散列来解决像您这样的问题。例如，您可以想象您的矩阵是黑白图像，并且您想快速找到相似的图像。散列函数的设计使相似的图像具有相似的散列。所以你散列你的项目数据库，然后在散列空间中找到附近的项目作为候选者，然后对你的候选者进行更昂贵的完整相似性检查。

还有更高级的技术称为放大，您可以使用多个不同的 LSH，然后要求某些项目在至少两个 LSH 中接近，以保证进行全面比较。挖掘海量数据集的第 3 章对您的问题进行了彻底的阐述。

于 2012-12-18T05:27:30.800 回答
0

您可能希望将“Voronoi 图”视为一种处理具有两个或多个维度的最近邻情况的技术。

您的相似性度量是否只是标量（= 一维）距离？总是积极的？或者使用二维或更多维向量距离是否有意义？

按位与对于获得差异并没有真正的用处。按位 EXOR 会更有意义。如果所有位都具有相同的重要性，您可能需要计算 EXOR 中的 1 位，这将是两个无符号整数之间的汉明距离。

布尔矩阵的差值计数距离函数：

int getSimilarity(matrix other) {
  int sum = 0;

  for(int col = 1; col < M; col++) {
    for (int row = 1; row < N; row++) {
       sum += (this[row, col] != other[row, col]) ? +1 : 0;
    }
  }

  return sum;
}

这个距离函数可以通过将行/列距离乘以权重因子来调整。

于 2012-12-18T07:40:11.563 回答