如何确定数据点的两个分区（聚类）是否相同？

小能豆

如何确定数据点的两个分区（聚类）是否相同？

我在某个任意空间中拥有n数据点，并将它们聚类。
我的聚类算法的结果是一个分区，由l长度为的int 向量表示n，将每个点分配给一个聚类。的值范围l从 0 到（可能）n-1。

例子：

l_1 = [ 1 1 1 0 0 2 6 ]

将点划分n=7为 4 个簇：前三个点聚集在一起，第四个和第五个点聚集在一起，最后两个点形成两个不同的单簇。

我的问题：

假设我有两个分区l_1，l_2如何有效地确定它们是否代表相同的分区？

例子：

l_2 = [ 2 2 2 9 9 3 1 ]

等同于，l_1因为它表示点的相同分区（尽管簇的“数字”/“标签”并不相同）。
另一方面

l_3 = [ 2 2 2 9 9 3 3 ]

由于它将最后两点组合在一起，因此不再相同。

我正在寻找 C++、python 或 Matlab 的解决方案。

不需要的方向

一种简单的方法是比较共现矩阵

c1 = bsxfun( @eq, l_1, l_1' );
c2 = bsxfun( @eq, l_2, l_2' );
l_1_l_2_are_identical = all( c1(:)==c2(:) );

共现矩阵的c1大小为nx，n如果true点k和m位于同一簇中，则为，false否则为（无论簇“编号”/“标签”如何）。
因此，如果共现矩阵c1和c2相同，则l_1和l_2代表相同的分区。

然而，由于点的数量n可能非常大，因此我想避免 O( n^2) 解决方案......

有什么想法吗？

谢谢！

阅读 28

2024-11-16

共1个答案

小能豆

为了有效判断两个分区是否相同，而无需使用 ( O(n^2) ) 的共现矩阵方法，可以通过 标准化标签 的方式实现 ( O(n \log k) ) 或 ( O(n) ) 的复杂度，其中 ( k ) 是簇的数量（通常 ( k \ll n )）。以下是解决方案：

核心思路

标准化标签：
将每个分区的簇标签重新映射为一个固定顺序的规范形式。例如，将 [1, 1, 1, 0, 0, 2, 6] 标准化为 [0, 0, 0, 1, 1, 2, 3]，这样不同分区的标签顺序无关，便于直接比较。
直接比较：
标准化后的两个分区可以通过简单的逐元素比较来判断是否相同。

Python 实现

import numpy as np

def normalize_labels(labels):
    """将簇标签标准化为固定顺序的形式"""
    _, normalized_labels = np.unique(labels, return_inverse=True)
    return normalized_labels

def are_partitions_identical(l1, l2):
    """判断两个分区是否相同"""
    # 将分区标签标准化
    normalized_l1 = normalize_labels(l1)
    normalized_l2 = normalize_labels(l2)
    # 比较标准化后的分区
    return np.array_equal(normalized_l1, normalized_l2)

# 示例
l1 = [1, 1, 1, 0, 0, 2, 6]
l2 = [2, 2, 2, 9, 9, 3, 1]
l3 = [2, 2, 2, 9, 9, 3, 3]

print(are_partitions_identical(l1, l2))  # 输出: True
print(are_partitions_identical(l1, l3))  # 输出: False

C++ 实现

在 C++ 中，可以使用 std::unordered_map 来实现类似的标签标准化：

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

std::vector<int> normalize_labels(const std::vector<int>& labels) {
    std::unordered_map<int, int> label_map;
    std::vector<int> normalized_labels;
    int next_label = 0;

    for (int label : labels) {
        if (label_map.find(label) == label_map.end()) {
            label_map[label] = next_label++;
        }
        normalized_labels.push_back(label_map[label]);
    }

    return normalized_labels;
}

bool are_partitions_identical(const std::vector<int>& l1, const std::vector<int>& l2) {
    if (l1.size() != l2.size()) return false;
    return normalize_labels(l1) == normalize_labels(l2);
}

// 示例
int main() {
    std::vector<int> l1 = {1, 1, 1, 0, 0, 2, 6};
    std::vector<int> l2 = {2, 2, 2, 9, 9, 3, 1};
    std::vector<int> l3 = {2, 2, 2, 9, 9, 3, 3};

    std::cout << std::boolalpha;
    std::cout << "l1 和 l2 是否相同: " << are_partitions_identical(l1, l2) << std::endl; // 输出: true
    std::cout << "l1 和 l3 是否相同: " << are_partitions_identical(l1, l3) << std::endl; // 输出: false

    return 0;
}

Matlab 实现

在 Matlab 中，可以使用 unique 函数来标准化标签：

function identical = are_partitions_identical(l1, l2)
    % 将标签标准化为固定形式
    normalized_l1 = normalize_labels(l1);
    normalized_l2 = normalize_labels(l2);
    % 比较标准化后的标签
    identical = isequal(normalized_l1, normalized_l2);
end

function normalized_labels = normalize_labels(labels)
    [~, ~, normalized_labels] = unique(labels, 'stable');
end

% 示例
l1 = [1 1 1 0 0 2 6];
l2 = [2 2 2 9 9 3 1];
l3 = [2 2 2 9 9 3 3];

disp(are_partitions_identical(l1, l2)); % 输出: true
disp(are_partitions_identical(l1, l3)); % 输出: false

复杂度分析

时间复杂度：
标签标准化：使用 np.unique 或类似的哈希映射，复杂度为 ( O(n \log k) ) 或 ( O(n) )（具体取决于实现）。
标签比较：( O(n) )。
总复杂度：( O(n \log k) ) 或 ( O(n) )。
空间复杂度：
需要 ( O(n) ) 的额外空间存储标准化后的标签。

总结

这种方法避免了 ( n \times n ) 共现矩阵的构造，适用于大规模数据。无论是 Python、C++ 还是 Matlab 实现，都具有清晰的逻辑和较高的效率。

2024-11-16