Часова складність

Складність “наївного” алгоритму агломеративної ієрархічної кластеризації становить Θ (N₃), оскільки, щоб знайти елементи з найбільшою подібністю на кожній з N - 1 ітерацій необхідно здійснити повний перебір елементів матриці С, що має розмірність N x N.

Для чотирьох методів, розглянутих у цій роботі, більш ефективним є алгоритм, що використовує черги з пріоритетом.

На рис. 13 показано, що стійкість по відношенню до найкращого об'єднання не зберігається в алгоритмі кластеризації методом повного зв'язку. Це означає, що ми не можемо використовувати масив для прискорення кластеризації. Після об'єднання кластера d₂, найкращого кандидата на об'єднання з кластером з кластером d₃ окремий кластер d₁ стає найкращим кандидатом на об'єднання з кластером d₃. Це пояснюється тим, що критерій повного зв'язку є нелокальним і залежить від точок, що знаходяться на великій відстані від області дотику двох кандидатів на об'єднання.

Рис. 14. Кластеризація методом повної зв'язку не є стійкою по відношенню до найкращого об'єднання. Спочатку найкращим кандидатом на об'єднання з кластером d3 є документ d2. Однак після об'єднання кластерів d1 до d2 найкращим кандидатом на об'єднання є кластер d4. У стійкому алгоритмі, такому як алгоритм методу одиночної зв'язку, найкращим кандидатом на об'єднання з d3 був би кластер {d1, d2}

На практиці зниження ефективності алгоритму зі складністю Θ (N²logN) порівняно з алгоритмом методу одиночного зв'язку, що має складність Θ (N²), невелика, оскільки обчислення міри подібності між двома документами виконується на порядок повільніше, ніж порівняння двох чисел при сортуванні. Всі алгоритми в цій главі мають складність Θ (N²) з урахуванням обчислення міри подібності. Отже, відмінності по складності на практиці рідко беруться до уваги при виборі алгоритму.