Группировать / кластеризовать объекты по нескольким свойствам / ключам и объединить пересекающиеся группы - PullRequest
Новая
       16

Группировать / кластеризовать объекты по нескольким свойствам / ключам и объединить пересекающиеся группы

0 голосов
/ 01 мая 2020

Цель состоит в том, чтобы сгруппировать (кластеризовать) объекты в непересекающиеся множества (кластеры) на основе множества свойств. Однако не комбинацией свойств. Вот алгоритм, объясненный на человеческом языке.

  • Существует массив объектов.
  • В объектах есть два специальных свойства, по которым все объекты должны быть сгруппированы / сгруппированы .
  • Сначала сгруппируйте объекты по первому свойству p1.
  • Таким образом, мы разделили исходный массив на несколько непересекающихся кластеров.
  • Если какой-либо объект * Свойство 1013 * соответствует любому объекту из другого кластера, два кластера должны быть объединены в один.

Вот пример: 

const items = [
      { a: 'file1', b: 'D1', s: 'S0' },
      { a: 'file2', b: 'D1', s: 'S1' },
      { a: 'file3', b: 'D1', s: 'S2' },
      { a: 'file4', b: 'D1', s: 'S2' },
      { a: 'file5', b: 'D2', s: 'S1' },
      { a: 'file6', b: 'D2', s: 'S5' },
      { a: 'file7', b: 'D3', s: 'S6' },
      { a: 'file8', b: 'D3', s: 'S7' },
    ];

Здесь первое свойство b, а второе свойство s.

  • Группировка по b дает нам кластеры file1-file4, file5-file6, file7-file8.
  • file2 имеет s=S1 и file5 имеет. Они находятся в разных кластерах, поэтому кластеры должны быть объединены вместе. Теперь у нас есть объединенный большой кластер file1-file6.
  • Кластер file7-file8 не пересекает любой другой кластер в свойстве s, поэтому он остается изолированным.

Вот графическое c представление основной специальности алгоритма:

Algoritm

Q1 : есть ли известный алгоритм для такой задачи / задачи?

Q2 : Какой подход будет предложен для реализации описанного алгоритма?

Язык программирования проекта Node.js, однако ответ на любом языке программирования приветствуется.

1 Ответ

0 голосов
/ 01 мая 2020

Проблема кажется ad-ho c и может не иметь стандартного алгоритма, хотя структура данных с несвязным множеством (алгоритм поиска объединения) кажется полезной.

Прежде всего, число кластеров k - это <= уникальные значения b свойств.

Итак, мы можем создать наш clusters с размером k. Нам необходимо назначить элементы из элементов этим k кластерам (некоторые кластеры могут быть пустыми).

Сначала мы можем запустить линейное сканирование объектов b, чтобы назначить каждый из них кластеру. O(n)

Теперь для каждого кластера мы вычисляем SF = set(s features).

Например, для кластера 1: (file1-4) будет иметь SF set(s features) = {S0, S1, S2}, поскольку это уникальные параметры s в этом кластере.

Затем мы ищем для каждого элемента в каждом кластере, совпадает ли параметр s этого элемента с любым элементом из любого другого SF кластеров, затем мы объединяем их, делая обоих их родителей одинаковыми (поиск объединений). Этот шаг будет иметь сложность O (n. K. Log (K)).

...