ності»: у просторі об'єктів всі близькі об'єкти повинні ставитися до одного кластеру, а всі різні об'єкти відповідно повинні знаходитися в різних кластерах.
Формальна постановка задачі кластеризації звучить так: Нехай - безліч об'єктів, - безліч номерів (імен, міток) кластерів. Задана функція відстані між об'єктами. Мається кінцева навчальна вибірка об'єктів. Потрібно розбити вибірку на непересічні підмножини, які називаються кластерами, так, щоб кожен кластер складався з об'єктів, близьких за метрикою, а об'єкти різних кластерів істотно відрізнялися. При цьому кожному об'єкту приписується номер кластера.
Алгоритм кластеризації - це функція, яка будь-якому об'єкту ставить у відповідність номер кластера. Безліч в деяких випадках відомо заздалегідь, однак частіше ставиться завдання визначити оптимальне число кластерів, з погляду того чи іншого критерію якості кластеризації [7].
Кластеризація (навчання без учителя) відрізняється від класифікації (навчання з учителем) тим, що мітки вихідних об'єктів спочатку не задані, і навіть може бути невідомо саме безліч. Рішення завдання кластеризації принципово неоднозначно, і тому є кілька причин:
· не існує однозначно найкращого критерію якості кластеризації. Відомий цілий ряд евристичних критеріїв, а також ряд алгоритмів, які не мають чітко вираженого критерію, але здійснюють досить розумну кластеризацию «з побудови». Всі вони можуть давати різні результати. Отже, для визначення якості кластеризації потрібно експерт предметної області, який би міг оцінити осмисленість виділення кластерів.
· число кластерів, як правило, невідомо заздалегідь і встановлюється відповідно з деяким суб'єктивним критерієм. Це справедливо тільки для методів дискримінації, оскільки в методах кластеризації виділення кластерів йде за рахунок формалізованого підходу на основі заходів близькості.
· результат кластеризації істотно залежить від метрики, вибір якої, як правило, також суб'єктивний і визначається експертом. Але варто відзначити, що є ряд рекомендацій до вибору заходів близькості для різних завдань.
3.3.2 Нейронна мережа Кохонена
Нейронні мережі Кохонена - клас нейронних мереж, основним елементом яких є шар Кохонена.
Шар Кохонена складається з паралельно де?? ствующих адаптивних лінійних елементів. Всі вони мають однакове число входів і отримують на свої входи один і той же вектор вхідних сигналів.
На виході -го лінійного елемента отримуємо сигнал:
,
де - ваговий коефіцієнт -го входу -го нейрона, - пороговий коефіцієнт.
Після проходження шару лінійних елементів сигнали посилаються на обробку за правилом «переможець забирає все»: серед вихідних сигналів шукається максимальний;
його номер. Остаточно, на виході сигнал з номером дорівнює одиниці, інші - нулю. Якщо максимум одночасно досягається для декількох, то або приймають всі відповідні сигнали рівними одиниці, або тільки перший у списку (за угодою).
Геометрична інтерпретація мережі Кохонена полягає в тому, що при навчанні задане - мірний простір розбивається на відповідні багатогранники Вороного-Діріхле: багатогранник складається з точок, які ближче до, ніж до інших.
Малюнок 1 ілюструє розбиття площини на багатокутники Вороного-Діріхле для випадково вибраних точок (кожна точка вказана у своєму багатокутнику).
lt; # justify gt; Рисунок 1 - Розбиття Вороного-Діріхле
У даній роботі використовується різновид мережі Кохонена - мережі векторного квантування сигналів, тісно пов'язані з найпростішим базовим алгоритмом кластерного аналізу (метод динамічних ядер або K-середніх). Завдання векторного квантування з кодовими векторами для заданої сукупності вхідних векторів ставиться як завдання мінімізації спотворення при кодуванні, тобто при заміщенні кожного вектора з відповідним кодовою вектором [7]. У базовому варіанті мереж Кохонена використовується метод найменших квадратів та спотворення обчислюється за формулою:
де складається з тих точок, які ближче до, ніж до інших. Іншими словами, складається з тих точок, які кодуються кодовою вектором.
Якщо сукупність задана і зберігається в пам'яті, то стандартним вибором в навчанні відповідної мережі Кохонена є метод K-середніх. Це метод розщеплення:
· при даному виборі кодових векторів (вони ж вагові вектори мережі) мінімізацією знаходимо безлічі - вони складаються з тих точок, які ближче до, ніж до інших;
· при даному розбитті на безлічі мінімізацією знаходимо...
