algorithm - 聚类算法

Question

我对客户端集群化有疑问。

我有一个数据集，其中包含 name、address、email、phone 等列(在示例 A、B、C 中)。每行都有唯一标识符 (ID)。我需要为每一行分配 CLUSTER_ID (X)。在一个集群中，所有行都具有一个或多个与其他行相同的属性。因此，ID=1,2,3 的客户端具有相同的 A 属性，而 ID=3,10 的客户端具有相同的 B 属性然后 ID=1,2,3,10 应该在同一个集群中。

如何使用 SQL 解决这个问题？如果不可能如何编写算法(伪代码)？性能非常重要，因为数据集包含数百万行。

示例输入:

ID  A   B   C
1   A1  B3  C1
2   A1  B2  C5
3   A1  B10 C10
4   A2  B1  C5
5   A2  B8  C1
6   A3  B1  C4
7   A4  B6  C3
8   A4  B3  C5
9   A5  B7  C2
10  A6  B10 C3
11  A8  B5  C4

示例输出:

ID  A   B   C   X
1   A1  B3  C1  1
2   A1  B2  C5  1
3   A1  B10 C10 1
4   A2  B1  C5  1
5   A2  B8  C1  1
6   A3  B1  C4  1
7   A4  B6  C3  1
8   A4  B3  C5  1
9   A5  B7  C2  2
10  A6  B10 C3  1
11  A8  B5  C4  1

感谢您的帮助。

Answer 1

一种可能的方法是对空的 X 重复更新。

从 cluster_id 1 开始。F.e.通过使用一个变量。

SET @CurrentClusterID = 1

取出前 1 条记录，并将其 X 更新为 1。

现在循环更新所有带有空 X 的记录，并且可以链接到 X = 1 且具有相同 A 或 B 或 C 的记录

免责声明:
该语句将根据 RDBMS 而有所不同。
这只是伪代码。

WHILE (<<some check to see if there were records updated>>) 
BEGIN
  UPDATE yourtable t
  SET t.X = @CurrentClusterID
  WHERE t.X IS NULL
    AND EXISTS (
      SELECT 1 FROM yourtable d 
      WHERE d.X =  @CurrentClusterID
        AND (d.A = t.A OR d.B = t.B OR d.C = t.C)
  );
END

循环直到更新 0 条记录。

现在对其他簇重复该方法，直到表中不再有空X。

1) Increase the @CurrentClusterID by 1
2) Update the next top 1 record with an empty X to the new @CurrentClusterID
3) Loop the update till no-more updates were done.

db<>fiddle 上的示例测试 here 用于 MS SQL Server。