і, меншої, ніж k.
1.1.4 Ієрархічні кластер - процедури
Ієрархічні (деревообразние) процедури є найбільш поширеними алгоритмами кластерного аналізу з їх реалізації на ЕОМ. Вони бувають двох типів: агломеративні і дівізімние. У агломратівних процедурах початковим є розбиття, що складається з n одноелементних класів, а кінцевим з одного класу; в дівізімних навпаки. p> Принцип роботи ієрархічних агломеративного (дівізімних) процедур полягає в послідовному об'єднанні (поділі) груп елементів спочатку найближчих (далеких), а потім все більш віддалених (близьких) один від одного. Більшість цих алгоритмів виходить з матриці відстаней (подібності). p> До недоліків ієрархічних процедур слід віднести гpомоздкость їх обчислювальної реалізації. Алгоритми вимагають на кожному кроці матриці обчислення відстаней, а отже, ємною машинної пам'яті і великої кількості часу. У цьому зв'язку реалізація таких алгоритмів при числі спостережень, більшому декількох сотень, недоцільна, а в ряді випадків і неможлива. p> Наведемо приклад агломеративного ієрархічного алгоритму. На першому кроці кожне спостереження (i = 1,2, .., n) розглядається як окремий кластер. Надалі на кожному кроці роботи алгоритму відбувається об'єднання двох найближчих кластерів, і, з урахуванням прийнятого відстані, за формулою перераховується матриця відстаней, розмірність якої, очевидно, знижується на одиницю. Робота алгоритму закінчується, коли всі спостереження об'єднані в один клас. Більшість пpoгpaмм, що реалізують алгоритм ієрархічної класифікації, передбачають графічне представлення класифікації у вигляді дeндpoгpaмми. p> Приклад 1
Провести класифікацію n = 6 об'єктів, кожен їх яких характеризується двома ознаками:
Номер об'єкта i123456
5
7
Розташування об'єктів у вигляді точок на площині показано на малюнку 1.
В
Рисунок 1 - Класифікація об'єктів
Рішення
Скористаємося агломеративного ієрархічним алгоритмом класифікації. В якості відстані між об'єктами візьмемо звичайне евклідова відстань. Тоді згідно з формулою (2) відстань між першим і другим об'єктами
В
а між першим і третім об'єктами
В
Очевидно, що
В
Аналогічно знаходимо відстані між шістьма об'єктами і будуємо матрицю відстаней
В
З матриці відстаней випливає, що четвертий і п'ятий об'єкти найбільш близькі і тому об'єднуються в один кластер.
Після об'єднання об'єктів маємо п'ять кластерів:
Номер кластера12345Состав кластера (1) (2) (3) (4,5) (6)
Відстань між кластерами визначимо за принципом "найближчого сусіда", скориставшись формулою перерахунку (11). Так відстань між об'єктом і кластером <...
