Алгоритмическая сложность групповой средней кластеризации

Question

Я читал в последнее время о различных hierarchical clustering algorithms, таких как single-linkage clustering и group average clustering. В общем, эти алгоритмы не имеют тенденций хорошо масштабироваться. Наивные реализации большинства иерархических алгоритмов кластеризации - O(N^3), но односвязная кластеризация может быть реализована в O(N^2) времени.

Также заявлено, что групповая кластеризация может быть реализована в O(N^2 logN) времени. Вот о чем мой вопрос.

Я просто не понимаю, как это возможно.

Объяснение после объяснения, такие как:

http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-of-hac-1.html

http://nlp.stanford.edu/IR-book/completelink.html#averagesection

https://en.wikipedia.org/wiki/UPGMA#Time_complexity

... утверждают, что в среднем по группе иерархическую кластеризацию может быть сделано в O(N^2 logN) времени с использованием очередей приоритетов , Но когда я читаю фактическое объяснение или псевдокод, мне всегда кажется, что это ничего лучше, чем O(N^3).

По сути, алгоритм выглядит следующим образом:

For an input sequence of size N: 

Create a distance matrix of NxN #(this is O(N^2) time) 
For each row in the distance matrix: 
    Create a priority queue (binary heap) of all distances in the row 

Then: 

For i in 0 to N-1: 
    Find the min element among all N priority queues # O(N) 
    Let k = the row index of the min element 

    For each element e in the kth row: 
    Merge the min element with it's nearest neighbor 
    Update the corresponding values in the distance matrix 
    Update the corresponding value in priority_queue[e] 

---

Так что, что последний шаг, который, мне, казалось бы, сделать это O(N^3) алгоритм. Невозможно «обновить» произвольное значение в очереди приоритетов, не просматривая очередь в O(N) времени - при условии, что приоритетная очередь представляет собой двоичную кучу. (Двоичная куча дает вам постоянный доступ к элементу min и добавляет/удаляет log N, но вы не можете просто найти элемент по значению лучше, чем O(N)). И так как мы сканировали очередь приоритетов для каждого элемента строки, для каждой строки мы получаем (O(N^3)).

Очередь приоритет отсортированы по значения расстояния - но алгоритм в вопросе предусматривает удаление элемента в очереди приоритета, который соответствует k, индекс строки в матрице расстояния от элемента мин. Опять же, нет способа найти этот элемент в очереди без сканирования O(N).

Итак, я предполагаю, что я, вероятно, ошибаюсь, потому что все остальные говорят иначе. Может кто-нибудь объяснить, как этот алгоритм каким-то образом неO(N^3), но на самом деле, O(N^2 logN)?

Answer 1

Я думаю, вы говорите, что проблема в том, что для того, чтобы обновить запись в куче, вы должны ее найти, и для ее нахождения требуется время O (N). То, что вы можете сделать, чтобы обойти это, - это поддерживать индекс, который дает для каждого элемента i его местоположение heapPos [i] в ​​куче. Каждый раз, когда вы меняете два элемента для восстановления инварианта кучи, вам необходимо изменить две записи в heapPos [i], чтобы сохранить индекс правильно, но это всего лишь постоянный фактор работы, выполняемой в куче.

Answer 2

Нет, поскольку матрица расстояний симметрична.

Если первая запись в строке 0 соответствует столбцу 5, расстояние 1 и наименьшему в системе, то первая запись в строке 5 должна быть дополнительной записью в столбец 0 с расстоянием 1.

На самом деле вам нужна только половина матрицы.

Answer 3

Если вы сохраняете позиции в куче (которая добавляет другую память O (n)), вы можете обновлять кучу без сканирования только в измененных положениях. Эти обновления ограничиваются двумя путями в куче (одно удаление, одно обновление) и выполняются в O (log n). В качестве альтернативы вы можете выполнить двоичный поиск по старому приоритету, который, вероятно, будет и в O (log n), но (но медленнее, выше подход - O (1)).

Таким образом, IMHO вы действительно можете реализовать их в O (n^2 log n). Но реализация по-прежнему будет использовать много (O (n^2)) памяти, что-нибудь из O (n^2) делает не масштаб. Обычно у вас заканчивается , если у вас есть память O (n^2) ...

Реализация этих структур данных довольно сложная. И когда это плохо сделано, это может оказаться медленнее, чем теоретически худший подход. Например, кучи Фибоначчи. У них хорошие свойства на бумаге, но у них слишком высокие постоянные издержки, чтобы окупиться.