Кластерний аналіз з прикладами на R, Про програмування, алгоритми і не тільки
Дружина посилає чоловіка-програміста до магазину та каже, купи батон ковбаси, а якщо будуть яйця – візьми десяток. Він у магазині: У Вас є яйця? -Є -Тоді дайте десять батонів ковбаси.
Tuesday, May 3, 2011
Кластерний аналіз із прикладами на R
Доброго дня, шановний читачу! Перед вами черговий опус із серії про data mining. Минулого разу я розповів про метод найближчих сусідів. Сьогодні, як логічне продовження, поговоримо про кластерний аналіз чи кластеризацію. З термінологією тут проблеми, т.к. більшість публікацій англійською та доводиться вигадувати український еквівалент англійським термінам. Тому і я іноді теж скочуватимуся на англіцизми.
Чому це логічне продовження? Тому що ідеї, що лежать в основі цих підходів, дуже схожі. Нагадаю, що суть методу найближчих сусідів полягає в тому, що для кожного об'єкта ми шукаємо найближчих до нього сусідів і на підставі наявних даних про сусідів робимо висновок про вихідний об'єкт, мовою data mining, це називається навчанням з учителем. Для того щоб цей підхід працював, потрібно мати набір тренувальних даних.
А якщо у нас є просто дані і ми нічого не знаємо про їх структуру? Зате у кожного елемента даних є набір характеристик (наприклад, якщо йдеться про людей: вік, стать, освіту тощо). Так ось, завдання кластерного аналізу полягає в тому, щоб розбити об'єкти на групи (кластери) так, щоб об'єкти в кожній групі були схожі. Тим самим розкривається внутрішня структура даних. При цьому нам не потрібні тренувальні дані. Такий підхід називається навчання без вчителя.
Попередня робота
Розглянемо, наприклад, набір даних:
| Ім'я | Вік | Місто | Дохід |
| Петро | 25 | Москва | 120000 |
| Вася | 34 | Кіров | 45000 |
| Марійка | 27 | Самара | 15000 |
| Світлана | 36 | Нью Йорк | 150000 |
| Катя | 24 | Москва | 30000 |
Існують різні заходи відстаней, але для нас інтуїтивно зрозумілою є класична Евклідова відстань і, заради справедливості, зауважу, що її в більшості завдань більш ніж достатньо. Важливо лише правильно нормалізувати дані. Як у нашому прикладі: зарплати вимірюються у тисячах, а вік у роках. Безпосередньо порівнювати ці дві величини не можна. А ось якщо попередньо привести їх до діапазону від 0 до 1, то вони стануть цілком порівнянними.
Таким чином, кластерний аналіз насамперед складається з роботи над даними. Потрібно вибрати характеристики, що нас цікавлять, нормалізувати їх і вибрати відповідну міру відстаней. І лише після цьогоможна переходити до алгоритмів кластерного аналізу.
Алгоритми кластерного аналізу
Отже, перш за все, всі алгоритми кластерного аналізу діляться на дві групи: ієрархічні та неієрархічні. Перші будують не просто розбиття на класи, а ієрархію розбиття. Результатом їх роботи, як правило, є дендрограма, на основі якої користувач може сам вибрати бажане розбиття. Неієрархічні алгоритми, навпаки, внаслідок роботи видають деяке конкретне розбиття і мають низку параметрів, що дозволяють налаштовувати алгоритм наявних даних. Природно, другі працюють швидше, ніж перші.
Усі методи кластеризації працюють із даними у вигляді векторів у багатовимірному просторі. Кожен вектор визначається значеннями кількох напрямів, а напрями є відомі нам характеристики (стаття, вік, освіта). Характеристики можуть бути як кількісні, так і якісні та мистецтво фахівця з data mining полягає в тому, щоб правильно відібрати та нормалізувати ці характеристики, а потім вибрати відповідний захід. І лише після цього в гру вступають алгоритми кластеризації.
До найбільш популярних, неієрархічних алгоритмів належить алгоритм k-середніх. Він особливо популярний через простоту реалізації та швидкість роботи. Головним його недоліком є збіжність до локального мінімуму та залежність результату від початкового розподілу. Крім того, потрібно заздалегідь знати передбачувану кількість кластерів k.
Отже, сам алгоритм: 1) Вибрати k випадкових центрів у просторі, що містить вихідні дані 2) Приписати кожен об'єкт із безлічі вихідних даних кластеру виходячи з того, який центр до нього ближче 3) Перерахувати центри кластерів використовуючи отримане4. Якщо алгоритм не зійшовся, то перейти до п. 2. Типові критерії сходження алгоритму це або середньоквадратична помилка, або відсутність переміщень об'єктів із кластера в кластер.
Існує безліч варіацій цього алгоритму, деякі з них намагаються вибирати найкращий початковий розподіл, інші дозволяють кластерам розбиватися на частини та об'єднуватися. Прикладом такої модифікації є алгоритм ISODATA, реалізований у маткаді та багатьох інших математичних бібліотеках.
Ієрархічна кластеризація
За своїм підходом, всі алгоритми ієрархічної кластеризації поділяються на два типи: зверху-вниз та знизу-вгору. Перші починають з одного великого кластера що складається з усіх елементів, а за тим крок за кроком розбивають його на все більш і більш дрібні кластери. Другі, навпаки, починають з окремих елементів поступово поєднуючи їх у більші і більші кластери. Для користувача принципової різниці між цими двома підходами немає, куди більш значуще те, яким способом алгоритм користується для обчислення відстаней між кластерами. За цією ознакою ієрархічні алгоритми діляться на алгоритми з одиночним і повним зв'язком (існують інші підходи, але менш популярні). В алгоритмах з одиночним зв'язком відстанню між двома кластерами вважається мінімальна відстань між усіма парами елементів цих двох кластерів. У алгоритмах з повним зв'язком відстанню вважається максимальна відстань між усіма парами елементів двох кластерів.
Таким чином, алгоритми з повним зв'язком схильні знаходити компактніші кластери. Алгоритми з одиночним зв'язком, навпаки, схильні виявляти сильно витягнуті та складні форми. Але часто страждають через шуми. На малюнку нижче наведено класичний прикладроботи алгоритму одиночного та повного зв'язку. Нам дано два кластери, з'єднані "доріжкою шумів". Зліва результат роботи алгоритму з одиночним зв'язком, а праворуч алгоритму з повним зв'язком:
Видно, що алгоритм з одиночним зв'язком дав не самий адекватний результат. З іншого боку, алгоритми з повним зв'язком не здатні виявити концентричні кластери, такі як на малюнку:
Отже, вибір алгоритму визначається конкретним завданням. Але на практиці кластери складної форми зустрічаються рідко, а шуми часто і тому частіше застосовуються алгоритми з повним зв'язком.
Алгоритми засновані на теорії графів
Насправді, у чистому вигляді, застосовуються рідко, т.к. їхня обчислювальна складність не дозволяє обробляти великі графи. Найчастіше використовуються у поєднанні з іншими алгоритмами, такими як k-середніх. Класичний приклад, це алгоритм мінімального дерева, що покриває. Ідея полягає в тому, щоб представити весь набір даних у вигляді графа, вершини якого це наші елементи даних, а вага кожного ребра дорівнює відстані між відповідними елементами (пам'ятайте, тут теж немає жодних чудес, спочатку доведеться визначити поняття відстані). Тоді ми можемо побудувати мінімальне покриваюче дерево на даному графі, а потім послідовно видаляти ребра з найбільшою вагою. Кластером вважається безліч елементів, з'єднаних "залишком" дерева. З кожним прибраним рубом кількість кластерів збільшується.
Статистичні алгоритми
Цей підхід дуже популярний у сфері розпізнавання зображень. Ідея така: припустимо, що кожен кластер у наших даних, підпорядковується деякому розподілу, зазвичай передбачається Гаусівський розподіл. Далі, методами статистики, ми визначаємо параметри допустимих розподілів таїхні центри. На цьому ґрунтується, наприклад, алгоритм EM-кластеризації.
Для прикладу буде використовуватися програмне середовище R. Що це таке, де взяти і як налаштувати можна почитати тут.Як завжди, приклад у мене з галузі фінансових ринків. Допустимо, у нас є акції великої кількості різних компаній. Одні з них ростуть, інші падають і ми нагромадили велику історію зміни їхніх цін. Чи можемо ми на основі цих даних об'єднати акції у групи? Логічно було б припустити, що акції з одного сектора ринку зростають чи падають разом. І було б логічно, якщо отримані групи це якось відобразили.
Для початку я викачав котирування приблизно 20 українських компаній з різних областей, за два роки з періодом 1 день. Для зручності всі вони зібрані в одному файлі і доступні тут. Спробуймо проаналізувати їх засобами кластерного аналізу. Т.к. ціни різних акцій відрізняються дуже сильно, і абсолютна величина ціни нам зовсім не цікава, а цікава відносна зміна, наведемо всі ціни до спільного знаменника: а саме, замість самої ціни вважатимемо логарифмічну зміну ціни: Xi = log(Ci) - log(Ci-1) ,де Ci - ціна закриття в i-ий день
Отримуємо результат:
| 1 | 2 | 3 | 4 | 5 | RASP | AFLT, PMTL, PLZL, MMBM, MTSI, VZRZ | GAZP, LKOH, VTBR, URKA, TRNFP, SIBN, SBER, ROSN, GMKN, SNGS | OGK1, OGK2, OGK5 | KMAZ, AVAZ |
На цій картинці вже набагато краще видно традиційні сектори нашої економіки. Видно і виколоті точки. Виколоті точки часто можуть стати предметом особливого дослідження, адже якщо компанія веде себе не як усі в її галузі, значить вона щось робить по-іншому. Знання такої інформації може дати додаткову перевагу у торгівлі.