Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

НАВЧАННЯ БЕЗ ВЧИТЕЛЯ

В результаті освоєння даного розділу навчається буде: знати

  • • цілі та завдання алгоритмів машинного навчання без вчителя; вміти
  • • застосовувати отримані знання в задачах вилучення знань; володіти
  • • базовими концепціями, що лежать в основі алгоритмів навчання без учителя.

Кластеризація / г-середніми

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

Перш ніж перейти до опису конкретного алгоритму кластеризації, дамо постановку задачі кластеризації і охарактеризуємо основні методи оцінки якості даних алгоритмів.

Всі алгоритми кластеризації призначені для поділу безлічі об'єктів на підмножини, або кластери {cluster), так, щоб об'єкти всередині кластера були максимально однорідні і сильно відрізнялися від об'єктів з інших кластерів [1] .

Цікаво, що завдання кластеризації можна розглядати як задачу пошуку невідомих класів для об'єктів навчальної вибірки. Саме ця особливість робить кластеризацию особливо цінним інструментом в аналізі даних, навіть при вирішенні завдань навчання з учителем. Так, на практиці перед навчанням фінального класифікатора проводиться попередня обробка ознак. Кластеризація може бути використана з цією метою - перш ніж класифікувати весь набір ознак, можна спробувати автоматично згенерувати мітки класів для деякої підгрупи ознак, тим самим спростивши завдання фінального класифікатора.

Всі алгоритми кластеризації спираються на так звану гіпотезу компактності, згідно з якою в просторі ознак все близькі об'єкти повинні належати до одного кластеру, а все різні об'єкти - відповідно до різних кластерів (рис. 6.1).

Приклад двох очевидних кластерів

Мал. 6.1. Приклад двох очевидних кластерів

Основним параметром алгоритму кластеризації даних є метрика. Метрика - це функція, яка визначає відстань між об'єктами в просторі ознак. Саме метрика дозволяє визначити поняття близькості в гіпотезі компактності. Метрика - дуже важливий параметр алгоритму кластеризації, який сильно може вплинути на результати роботи алгоритму. Найпростіша метрика - евклідова відстань:

яке буде працювати для речових ознак (або для порядкових).

В ідеалі метрика повинна відповідати таким вимогам [2] :

  • • якщо d (x, у) = 0, то х = у, де d (x, у) - метрика;
  • d (x, у) = d (y, х);
  • d (x, z) <= d (x, у) + d (y, z ) - правило трикутника.

Однак найчастіше на практиці правилом трикутника нехтують, причому алгоритм все одно успішно справляється із завданням кластеризації.

Дамо формальну постановку задачі кластеризації. Дано безліч об'єктів X = {x iy х 2 , х 3 , x L ) f бажане кількість кластерів К, а також цільова функція, мета якої - оцінити якість кластеризації. Необхідно навчити алгоритм а (х) : X -> -> {1,2, ..., / З}, тобто знайти таку модель, яка б для вхідного об'єкта привласнювала йому мітку кластера. Цільова функція визначена в термінах метрики, міри схожості між об'єктами, тобто необхідно мінімізувати відстань між об'єктами одного кластера.

Також можна говорити про повну і неповну кластеризації. При повній кластеризації весь набір вхідних об'єктів повинен бути розбитий на кластери, при неповній - частина об'єктів може не отримати мітки кластера (наприклад, такі об'єкти можуть бути викидами). У даній книзі ми будемо говорити тільки про повну кластеризації.

Число До називається потужністю кластеризації і позначає загальне число можливих або бажаних кластерів. Це число, так само як і метрика, є параметром алгоритму кластеризації і впливає на його якість. Часто при виборі значення цього параметра спираються на зовнішнє подання даних (як на рис. 6.1), яке може допомогти визначити кількість кластерів. У тих же випадках, коли неможливо на око визначити кількість кластерів, можна вдатися до побудови кривої навчання, в якій буде відображена залежність між параметром До і якістю кластеризації.

  • [1] Маннинг К. Д., Рагхаван П. Введення в інформаційний пошук. М .: Вільямс, 2014.
  • [2] Скворцов В. А. Приклади метричних просторів. М .: Изд-во МЦНМО, 2002.
 
<<   ЗМІСТ   >>