трів кластерів (Q) має бути кінцевим. Ними можуть бути об'єкти кластеризації (рядки матриці), тоді. Другий спосіб вибору потенційних центрів кластерів полягає в дискретизації простору вхідних ознак. Для цього діапазони зміни вхідних ознак розбивають на кілька інтервалів. Проводячи через точки розбиття прямі, паралельні координатним осях, отримуємо "Гратковий" гиперкуб. Вузли цієї решітки і будуть відповідати центрам потенційних кластерів. Позначимо через - кількість значень, які можуть брати центри кластерів по-й координаті (). Тоді кількість можливих кластерів дорівнюватиме:.
На другому кроці алгоритму розраховується потенціал центрів кластерів за такою формулою:
,,
де - потенційний центр h-го кластера;
- позитивна константа
- відстань між потенційним центром кластера () і об'єктом кластеризації (). У евклідовому просторі це відстань розраховується за формулою:
.
У разі, коли об'єкти кластеризації задані двома ознаками (n = 2), графічне зображення розподілу потенціалу буде являти собою поверхню, нагадує гірський рельєф. Звідси і назва - гірський метод кластеризації. p> На третьому кроці алгоритму в якості центрів кластерів вибирають координати "гірських" вершин. Для цього, центром першого кластера призначають точку з найбільшим потенціалом. Зазвичай, найвища вершина оточена кількома досить високими піками. Тому призначення центром наступного кластера точки з максимальним потенціалом серед залишилися вершин призвело б до виділення великої кількості близько розташованих центрів кластерів. Щоб вибрати наступний центр кластера необхідно спочатку виключити вплив щойно знайденого кластера. Для цього значення потенціалу для залишилися можливих центрів кластерів перераховується таким чином: від поточних значень потенціалу віднімають внесок центру щойно знайденого кластера (тому кластеризацію за цим методом іноді називають субтрактивной). Перерахунок потенціалу відбувається за формулою:
,
де - потенціал на 1-й ітерації;
- потенціал на 2-й ітерації;
- центр першого знайденого кластера:
;
- позитивна константа.
Центр другого кластеру визначається по максимальному значенням оновленого потенціалу:
.
Потім знову перераховується значення потенціалів:
.
Ітераційна процедура перерахунку потенціалів і виділення центрів кластерів продовжується до тих пір, поки максимальне значення потенціалу перевищує деякий поріг.
5 Приклад використання методу на реальних даних
Для реалізації методу гірської кластеризації на реальних даних по показниками 3 (Atomic-radius-emp), 7 (Electron-affinity) і 14 (Electronegativity-AllredRochow) автором був використаний математичний пакет Matlab версії 7.10.0 (R2010a), в який були імпортовані дані з таблиці MS Excel за допомогою надбудови Spreadsheet Link EX 3.1.1. Виклик вбудованою в Matlab функції кластеризації subclust () і створення фігури для відображення одержані результатів записані в скрипті Cluster.m:
В
Результати:
В
У командному вікні Matlab виводяться координати трьох кластерів та їх радіуси:
centers =
155.0000 41.1000 1.2200
135.0000 118.4000 1.7500
220.0000 48.4000 0.9100
sigmas =
27.5772 37.0170 0.5834
В
Висновок
У підсумку аналізу методом гірської кластеризації за параметрами 3, 7 і 14 вихідних даних виділилися три кластери, дисперсія елементів досить висока. Таким чином, можна виявити три групи елементів, що мають одні й ті ж властивості.
В
Використана література
1. Гайдишев І. Аналіз та обробка даних: спеціальний довідник - СПб: Питер, 2001. p> 2. exponenta.ru
