python - 查找整数列表中的簇数

Question

让我们考虑距离 d(a, b) = a 和 b 中成对不同的数字的数量，例如:

d(1003000000, 1000090000) = 2   #   the 4th and 6th digits don't match

(我们只处理 10 位数字)和这个列表:

L = [2678888873,
     2678878873,  # distance 1 from L[0]
     1000000000,  
     1000040000,  # distance 1 from L[2]
     1000300000,  # distance 1 from L[2], distance 2 from L[3]
     1000300009,  # distance 1 from L[4], distance 2 from L[2]
    ]

我想找到最小数量的点 P，使得列表中的每个整数与 P 中的一个点的距离 <= 1。

这里我认为这个数字是 3:列表中的每个数字的距离 <= 2678888873、1000000000 或 1000300009 中的第一个。

我想 O(n^2) 算法是可能的，首先计算一个距离矩阵，即 M[i, j] = d(L[i], L[j])。

有没有更好的方法来做到这一点，尤其是使用 Numpy？(也许 Numpy/Scipy 中有内置算法？)

---

PS:如果我们将这些 10 位整数视为字符串，我们将接近于在具有 Levenshtein 距离的许多单词列表中找到最少数量的聚类。

PS2:我知道这个距离在字符串上有一个名字:Hamming distance .

Answer 1

让我们看看我们从距离度量中知道了什么。给定一个数字 P(不一定在 L 中)，如果 L 的两个成员在 P 的距离 1 内，它们各自与P共享9位，但不一定相同，所以它们只保证彼此共享8位。因此，任何两个距离为 2 的数字都保证有两个唯一的 P，它们彼此之间的距离为 1(彼此之间的距离也为 2)。您可以使用此信息来减少优化 P 的选择所需的蛮力工作量。

假设您有一个距离矩阵。您可以立即丢弃条目不小于 3 的行(或列):它们自动成为自己的集群。对于等于 2 的剩余条目，构造一个可能的 P 值列表。查找 L 中 P(另一个距离矩阵)每个元素在 1 以内的元素数。按邻居的数量对 P 进行排序，然后选择。您将需要在每次迭代中更新矩阵，因为您删除具有最大邻居的成员以避免由于重叠导致的低效分组(L 的成员靠近 P 的多个成员) .

您可以先将 L 转换为二维数字数组，然后在 numpy 中计算距离矩阵:

L = np.array([2678888873, 2678878873, 1000000000, 1000040000, 1000300000, 1000300009])

z = 10     # Number of digits
n = len(L) # Number of numbers

dec = 10**np.arange(z).reshape(-1, 1).astype(np.int64)
digits = (L // dec) % 10

digits 现在是一个 10xN 数组:

array([[3, 3, 0, 0, 0, 9],
       [7, 7, 0, 0, 0, 0],
       [8, 8, 0, 0, 0, 0],
       [8, 8, 0, 0, 0, 0],
       [8, 7, 0, 4, 0, 0],
       [8, 8, 0, 0, 3, 3],
       [8, 8, 0, 0, 0, 0],
       [7, 7, 0, 0, 0, 0],
       [6, 6, 0, 0, 0, 0],
       [2, 2, 1, 1, 1, 1]], dtype=int64)

您可以使用 != 和 sum< 计算 digits 与其自身或 digits 与任何其他 10xM 数组之间的距离 沿右轴:

distance = (digits[:, None, :] != digits[..., None]).sum(axis=0)

结果:

array([[ 0,  1, 10, 10, 10, 10],
       [ 1,  0, 10, 10, 10, 10],
       [10, 10,  0,  1,  1,  2],
       [10, 10,  1,  0,  2,  3],
       [10, 10,  1,  2,  0,  1],
       [10, 10,  2,  3,  1,  0]])

我们只关心该矩阵的上(或下)三角形，因此我们可以立即屏蔽掉另一个三角形:

distance[np.tril_indices(n)] = z + 1

查找 P 的所有候选值:L 的所有元素，以及距离为 2 的元素之间的所有对:

# Find indices of pairs that differ by 2
indices = np.nonzero(distance == 2)
# Extract those numbers as 10xKx2 array
d = digits[:, np.stack(indices, axis=1)]
# Compute where the difference is nonzero (Kx2)
locs = np.diff(d, axis=2).astype(bool).squeeze()
# Find the index of the first digit to replace (K)
s = np.argmax(locs, axis=0)

P 的额外值由 d 的每一半构成，用 k 表示的数字替换另一半:

P0 = digits[:, indices[0]]
P1 = digits[:, indices[1]]
k = np.arange(s.size)
tmp = P0[s, k]
P0[s, k] = P1[s, k]
P1[s, k] = tmp

Pextra = np.unique(np.concatenate((P0, P1), axis=1)

现在您可以计算 P 的全部可能性:

P = np.concatenate((digits, Pextra), axis=1)
distance2 = (P[:, None, :] != digits[..., None]).sum(axis=0)

您可以根据距离丢弃 Pextra 中与 digits 元素匹配的任何元素:

mask = np.concatenate((np.ones(n, bool), distance2[:, n:].all(axis=0)))
P = P[:, mask]
distance2 = distance2[:, mask]

现在您可以迭代地确定 P 与 L 的距离，并选择 P 的最佳值，从距离矩阵。从 P 中进行的贪婪选择不一定是最优的，因为由于重叠，替代组合可能需要更少的元素，但这是简单(但有些昂贵)的图遍历算法的问题。以下代码片段仅显示了一个简单的贪婪选择，这对您的玩具示例来说效果很好:

distMask = distance2 <= 1
quality = distMask.sum(axis=0)

clusters = []
accounted = 0
while accounted < n:
    # Get the cluster location
    best = np.argmax(quality)
    # Get the cluster number
    clusters.append(P[:, best].dot(dec).item())
    # Remove numbers in cluser from consideration
    accounted += quality[best]
    quality -= distMask[distMask[:, best], :].sum(axis=0)

最后几个步骤可以使用集合和图表进行优化，但这显示了有效方法的起点。这对于大数据来说会很慢，但可能不会太慢​​。做一些基准测试来决定你想花多少时间来优化而不是仅仅运行算法。