оміщають в різні кластери. [2] [3]
2.4 Основні алгоритми
За способом розбиття на кластери алгоритми бувають двох типів: ієрархічні і неієрархічні.
Класичні ієрархічні алгоритми працюють тільки з категорійними атрибутами, коли будується повне дерево вкладених кластерів. Тут поширені агломеративні методи побудови ієрархій кластерів - в них проводиться послідовне об'єднання вихідних об'єктів і відповідне зменшення числа кластерів. Ієрархічні алгоритми забезпечують порівняно високу якість кластеризації і не вимагають попереднього завдання кількості кластерів. Більшість з них мають складність. p> Неієрархічні алгоритми грунтуються на оптимізації деякої цільової функції, що визначає оптимальне в певному сенсі розбиття множини об'єктів на кластери. У цій групі популярні алгоритми сімейства k-середніх (k-means, fuzzy c-means, Густафсон-Кесселя), які в якості цільової функції використовують суму квадратів зважених відхилень координат об'єктів від центрів шуканих кластерів. Кластери шукаються сферичної або еліпсоїдної форми. У канонічній реалізації мінімізація функції проводиться на основі методу множників Лагранжа і дозволяє знайти тільки найближчий локальний мінімум. Використання методів глобального пошуку (генетичні алгоритми) значно збільшить обчислювальну складність алгоритму. p> Серед неієрархічних алгоритмів, не базованих на відстані, слід виділити EM-алгоритм (Expectation-Maximization). У ньому замість центрів кластерів передбачається наявність функції щільності ймовірності для кожного кластеру з відповідним значенням математичного очікування і дисперсією. [6]
.4.1 K-means
Однією з широко використовуваних методик кластеризації є розділова кластеризація , відповідно до якої для вибірки даних, що містить n записів, задається число кластерів k , яке має бути сформоване. Потім алгоритм розбиває всі об'єкти вибірки на k груп ( k ), які і являють собою кластери.
До найбільш простим і ефективним алгоритмам кластеризації відноситься k-means (k-середніх). Він складається з чотирьох кроків:
. Здається число кластерів k , яке має бути сформоване з об'єктів вихідної вибірки.
2. Випадковим чином вибирається k записів, які будуть служити початковими центрами кластерів. Початкові точки, з яких потім виростає кластер, часто називають В«насіннямВ». Кожна така запис являє со...
