聚类算法

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 条记录。

现在对其他簇重复此方法，直到table中不再有空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 for MS Sql 服务器的示例测试。

聚类算法

Clusterization algorithm

algorithm

cluster-analysis

sas