Алгоритм кластеризации - PullRequest
Новая
       15

Алгоритм кластеризации

0 голосов
/ 11 марта 2019

У меня проблема с кластеризацией клиентов.

У меня есть набор данных с такими столбцами, как 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

Спасибо за любую помощь.

1 Ответ

1 голос
/ 11 марта 2019

Возможный способ - повторять обновления для пустого X.

Начните с cluster_id 1. Например, используя переменную.

SET @CurrentClusterID = 1

Возьмите первую 1 запись и обновите ее X до 1.

Теперь зациклите обновление для всех записей с пустым X, и это можно связать с записью с X= 1 и имеет тот же A или B или C

Отказ от ответственности:
Заявление будет варьироваться в зависимости от СУБД.
Это просто подразумевается как псевдокод. 

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) Увеличьте @CurrentClusterID на 1
2) Обновитеследующая верхняя 1 запись с пустой буквой X для нового @ CurrentClusterID
3) Зацикливать обновление до тех пор, пока обновления не будут выполнены.

Пример теста db <> fiddle здесь для MS Sql Server.

...