ІЄРАРХІЧНА КЛАСТЕРИЗАЦІЯ

Постановка завдання ієрархічної кластеризації

Плоскі алгоритми кластеризації (саме до них відноситься алгоритм кластеризації ^-середній) виконують тільки розбиття вихідного безлічі об'єктів на кластери, кожен кластер якого видається неструктурованих безліччю об'єктів. Більш того, в сил} 'рандомізують ініціалізації алгоритм ^ -середня може давати різні відповіді при різних запусках на одному і тому ж наборі даних, тобто даний алгоритм є недетермінованим. Ієрархічні алгоритми кластеризації позбавлені недоліку малої інформативності - за рахунок додаткових тимчасових витрат на виході таких алгоритмів все безліч об'єктів представляється у вигляді ієрархії вкладених один в одного кластерів, що може дати досліднику даних додаткову корисну інформацію про структуру даних. Також більшість алгоритмів ієрархічної кластеризації є детермінованими, що в деяких випадках є цінність.

Алгоритми ієрархічної кластеризації можна поділити на дві великі групи ^[1] :

• 1) алгоритми висхідній ієрархічної кластеризації;
• 2) алгоритми низхідній кластеризації.

Перша група алгоритмів працює за принципом первісного об'єднання окремо розташованих об'єктів в близькі один друг} 'пари об'єктів, потім пари об'єднуються з іншими за тим же принципом і т.д., поки не залишиться всього один кластер, який містить в собі всі точки вихідного безлічі об'єктів . Алгоритми низхідній ієрархічної кластеризації діють за зворотним принципом - спочатку вибирається максимально великий кластер, що містить всі об'єкти вибірки, який потім поступово розбивається на безліч кластерів-нащадків.

Об'єкти вибірки представляються у вигляді ієрархії кластерів, званої також Дендрограмма ( dendrogram ) (рис. 6.2).

Мал. 6.2. приклад дендрограмми

Як видно з рис. 6.2, для вхідних вибірки може бути побудовано будь-яку кількість кластерів - на найнижчому рівні містяться тільки об'єкти в якості кластерів, далі вони по одному приєднуються до найближчих кластерів, і якщо задати правило, за яким можна зробити перетин дендрограмми, тобто «Відрізати» нижні гілки, то такий алгоритм кластеризації сам зможе визначити число кластерів для мінімізації цільової функції.

• [1] Див .: Маннинг К. Д., Рагхаван П. Введення в інформаційний пошук.