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

Завдання кластеризації (clustering) відрізняються від класифікації (classiﬁcation) тим, що не задаються відповіді y i = y (x i ) . Відомі лише самі об'єкти x i ,

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

приклад 1.13. Основним інструментом соціологічних і маркетингових досліджень.

дування є проведення опитувань. Щоб результати опитування були об'єктивними, необхідно забезпечити представництво вибірки респондентів. З іншого боку потрібно мінімізувати вартість проведення опитування. Тому при плануванні опитувань виникає допоміжне завдання: відібрати якнайменше респондентів, щоб вони утворювали репрезентативну вибірку, тобто представляли весь спектр громадської думки. Один із способів це зробити полягає в наступному. Спочатку складаються ознакові описи досить великої кількості точок опитування (це може бути міста, райони, магазини, тощо. буд.). І тому використовуються недорогі способи збирання інформації пробні опитування чи фіксація деяких характеристик самих точок. Потім вирішується завдання кластеризації, і з кожного кластера відбирається по одній представницькій точці. Тільки у відібраному безлічі точок проводиться основне, найбільш ресурсомістке, опитування.

Завдання кластеризації, у яких частина об'єктів (зазвичай, незначна) розмічена за класами, називаються завданнями з частковим навчанням (semisupervised learning). Вважається, що вони не зводяться безпосередньо до класифікації чи кластеризації, і для нихрішення потрібні спеціальні способи.

приклад 1.14. Завдання рубрикації текстів виникає при роботі з великими кіл-

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

К. В. Воронцов. Обчислювальні методи навчання за прецедентами

1.2.5 Завдання пошуку асоціацій

Завдання пошуку асоціативних правил (association rule induction) винесено в окремий клас і відноситься до завдань навчання без вчителя, хоча має багато спільного із завданням класифікації.

приклад 1.15. Завдання аналізу ринкових кошиків (market basket analysis) складається

куплено та молоко¿. У багато підручників з бізнес-аналітики увійшов приклад, коли система пошуку асоціативних правил виявила неочевидну закономірність: увечері перед вихідними днями зростає спільний продаж памперсів та пива. Розмістивши дорогі сорти пива поряд із памперсами, менеджери змогли збільшити продаж у масштабах усієї роздрібної мережі, що окупило впровадження системи аналізу даних. Пізніше маркетологи та соціологи запропонували розумне пояснення даному явищу, проте виявлено воно було саме шляхом аналізу даних.

приклад 1.16. Завдання виділення термінів (term extraction) з текстів, яке вирішується

перед завданням рубрикації (див. приклад 1.14), може бути зведена до пошуку асоціацій. Термінами вважаються окремі слова або стійкі словосполучення, які часто зустрічаються в невеликому підмножині документів, і рідко у всіх інших. Безліч часто спільно зустрічаються термінів утворює тему, швидше за все, що відповідає певній рубриці.

1.2.6 Методологія тестування алгоритмів, що навчаються

Поки що ще не створено універсальний метод навчання з прецедентів, здатний вирішувати будь-які практичні завдання однаково добре. Кожен метод має свої переваги, недоліки та межі застосування. Насправді доводиться проводити чисельні експерименти, аби зрозуміти, який метод з арсеналу краще підходить для конкретного завдання. Зазвичай при цьому методи порівнюються по ковзному контролю ( 1.6 ).

Існує два типи експериментальних досліджень, що відрізняються цілями та методикою проведення.

Експерименти на модельних даних. Їхня мета виявлення меж застосування методу навчання; побудова прикладів вдалої та невдалої його роботи; розуміння, потім впливають параметри методу навчання. Модельні експерименти часто використовуються на стадії налагодження методу. Модельні вибірки спочатку генеруються у двовимірному просторі, щоб роботу методу можна було наочно уявити на плоских графіках. Потім досліджується робота методу на багатовимірних даних, при різному числі ознак. Генерація даних виконується або за допомогою

датчика випадкових чисел за заданими ймовірнісними розподілами, або детермінованим чином. Часто генерується не одне модельне завдання, а ціла серія, яка параметризована таким чином, щоб серед завдань виявилися яксвідомо «легкі», так і свідомо «важкі»; за такої організації експерименту точніше виявляються межі застосування методу.

класифікації, з різних предметних областей [ 30 ].

ванна розширена методика тестування та централізоване сховище завдань. Реалізація алгоритмів класифікації, навпаки, децентралізована. Будь-який користувач Інтернету може оголосити свій комп'ютер обчислювальним сервером Полігона, що реалізує один або кілька методів класифікації. Всі результати тестування зберігаються як готові звіти в базі даних системи і можуть бути в будь-який момент видані на запит без проведення трудомістких обчислень заново.