Разработать алгоритм кластеризации и построения дендрограммы на с++
имплементировать алгоритм кластеризации и построения дендрограммы.
Формат входных данных CSV файл:
pid,tid,aid
1,1231731025,0|1|2
2,1231742025,3|4
3,1231753025,5|6|7
4,1231764025,0|1|3
5,1231775025,5|6|8
6,1231786025,2|4|8|5
7,1231797025,9|0
...
pid и tid можно игнорировать на данный момент, aid - массив идентификаторов разделенных | чертой, по которым строится дерево.
можно считать что изначально каждый aid принадлежит отдельному кластеру, (множеству из одного
aid). Если в строке есть несколько aid принадлежащие к разным кластерам, то мы их обьединяем в один кластер.
На данных, которые приведены в примере входного формата это будет выглядеть так:
aid 0, 1, 2 мы видим впервые, поэтому считаем, что они принадлежат кластерам 1, 2, 3,
соответственно объединяем их в кластер 4.
aid 3 и 4 тоже видим впервые, считаем, что они принадлежат кластерам 5 и 6 объединяем их в
кластер 7.
Аналогично до строки 4.
В строке 4 обнаруживаем, что у нас есть aid 0 и 1, которые принадлежат кластеру 4, и aid 3,
который принадлежит кластеру 7. Соответственно объединяем кластера 6 и 3 в новый кластер.
Ниже дендрограмма для данных из примера
http://prntscr.com/iudd1z
Необходимо реализовать следующие методы:
1) Получение cluster_id по aid, по примеру выше если мы спрашиваем кластер для aid 2, то ответ будет 17.
2) Получение всех aid которые входят в кластер
Ограничения:
1) Важна скорость выполнения (запросы получения кластера или списка всех aid в кластеры должны отрабатываться за ms, исключения очень большие кластера, но и их скорость должна быть в пределах секунд)
2) Структура должна храниться в оперативной памяти.
3) Количество уникальных aid около 400 миллионов, количество строк в csv файле около 200 миллионов. некоторые кластера могут иметь до 15 миллионов aid.
4) Код пишется под платформу linux ubuntu 64.