多算法聚类结果的合并策略与SQL实现：基于连通分量的传递闭包方法

-- 创建示例数据表
CREATE TABLE Clustering1 (cluster_key INT, id INT);
INSERT INTO Clustering1 VALUES (3,1), (3,2), (3,3), (6,4), (6,5), (6,6), (8,7), (8,8);

CREATE TABLE Clustering2 (cluster_key INT, id INT);
INSERT INTO Clustering2 VALUES (1,1), (2,2), (5,3), (5,4), (5,5), (6,6), (8,7), (8,8);

-- 步骤1：标准化集群数据
-- 为每个原始集群分配一个唯一的 original_cluster_id
-- 这里我们假设 original_cluster_id 可以通过 (source_table, cluster_key) 唯一标识
-- 或者更简单地，直接生成一个序列号
WITH AllClustersRaw AS (
    SELECT 'C1' AS source, cluster_key, id FROM Clustering1
    UNION ALL
    SELECT 'C2' AS source, cluster_key, id FROM Clustering2
),
ClusteredItems AS (
    SELECT
        ROW_NUMBER() OVER (ORDER BY source, cluster_key) AS original_cluster_id,
        source,
        cluster_key,
        id
    FROM (
        SELECT DISTINCT source, cluster_key, id FROM AllClustersRaw
    ) AS distinct_clusters_and_items
)
SELECT * FROM ClusteredItems;

-- 步骤2：识别直接连接的集群对
WITH AllClustersRaw AS (
    SELECT 'C1' AS source, cluster_key, id FROM Clustering1
    UNION ALL
    SELECT 'C2' AS source, cluster_key, id FROM Clustering2
),
ClusteredItems AS (
    SELECT
        DENSE_RANK() OVER (ORDER BY source, cluster_key) AS original_cluster_id,
        source,
        cluster_key,
        id
    FROM (
        SELECT DISTINCT source, cluster_key, id FROM AllClustersRaw
    ) AS distinct_clusters_and_items
)
SELECT DISTINCT
    c1.original_cluster_id AS cluster_a,
    c2.original_cluster_id AS cluster_b
FROM ClusteredItems c1
JOIN ClusteredItems c2 ON c1.id = c2.id AND c1.original_cluster_id < c2.original_cluster_id;

-- 概念性SQL迭代更新（不推荐用于生产环境，尤其大型数据集）
-- 假设我们有一个临时表 ComponentRoots (original_cluster_id INT, root_id INT)
-- 初始化：每个集群是自己的根
-- INSERT INTO ComponentRoots SELECT original_cluster_id, original_cluster_id FROM (SELECT DISTINCT original_cluster_id FROM ClusteredItems);

-- 迭代更新：
-- WHILE EXISTS (SELECT 1 FROM ComponentRoots cr1 JOIN ComponentRoots cr2 ON ... WHERE cr1.root_id != cr2.root_id)
-- BEGIN
--     UPDATE ComponentRoots SET root_id = LEAST(cr1.root_id, cr2.root_id)
--     FROM ComponentRoots cr1 JOIN ComponentRoots cr2 ON ... (using the overlap relationships)
--     WHERE cr1.root_id != cr2.root_id;
-- END;

class UnionFind:
    def __init__(self, elements):
        self.parent = {e: e for e in elements}
        self.rank = {e: 0 for e in elements} # Optional: for optimization (union by rank)

    def find(self, i):