Міністерство освіти і науки України
Львівський національний університет імені Івана Франка
Економічний факультет
Кафедра економічна кібернетика
Доповідь
на тему:
«Неієрархічний кластерний аналіз»
Студента групи: ЕКК-41з
Бурбели І.М.
Викладач:
Зомчак Л.М.
Вступ
Кластерний аналіз - це сімейство алгоритмів, розроблених для формування груп таким чином, щоб члени групи були найбільш схожими один на одного і не схожими на елементи, що не виходять в групу. Кластер і група - це синоніми в світі кластерного аналізу. Задачу кластеризації можна сформулювати так: заданий набір з n векторів, кожен з яких має розмірність d, необхідно розбити на підмножини відповідно до заданого критерію оптимізації.
Основними завданнями кластерного аналізу є:
– розробка типології або класифікації досліджуваних об'єктів;
– дослідження та визначення прийнятних концептуальних схем групування об'єктів;
– висунення гіпотез на підставі результатів дослідження даних;
– перевірка гіпотез чи справді типи (групи), які були виділені певним чином, мають місце в наявних даних.
Кластерний аналіз потребує здійснення таких послідовних кроків:
1) проведення вибірки об'єктів для кластеризації;
2) визначення множини ознак, за якими будуть оцінюватися відібрані об'єкти;
3) оцінка міри подібності об'єктів;
4) застосування кластерного аналізу для створення груп подібних об'єктів;
5) перевірка достовірності результатів кластерного рішення.
Мета та сфери застосування
Кластерний аналіз застосовується в різних сферах і галузях. Він працює навіть тоді, коли даних мало і не виконуються вимоги нормальності розподілу випадкових величин й інші вимоги класичних методів статистичного аналізу. Він корисний, коли потрібно класифікувати велику кількість інформації. Наприклад, у медицині кластеризація використовується для класифікації захворювань або їх симптомів, таксономії6 пацієнтів, препаратів тощо. В психіатрії – для правильної діагностики симптомів, таких як параноя, шизофренія тощо, що є вирішальним чинником для успішної терапії. В археології встановлюються таксономії кам’яних споруд, похованих об’єктів.
У маркетингу це можуть бути завдання сегментації конкурентів і споживачів.
У менеджменті прикладами задач кластеризації слугують розбивка персоналу на різні групи, кластеризація споживачів і постачальників, виявлення схожих виробничих ситуацій, за яких виникає брак. У соціології – розбивка респондентів на однорідні групи. У маркетингових дослідженнях кластерний аналіз застосовується як у теоретичних дослідженнях, так і маркетологами, що практикують і вирішують проблеми угруповання різних об’єктів (аналіз поведінки споживача, групування споживачів в однорідні класи для одержання максимально повної картини про поведінку клієнта з кожної групи й про фактори, що впливають на його поведінку). При цьому розв’язуються питання про групи клієнтів, продуктів тощо. В геоінформатиці кластерний аналіз застосовується для спрощення роботи з геоінформацією, візуалізації даних, сегментації зображень, інтелектуального пошуку; в економіці – для аналізу ринків і фінансових потоків, виведення закономірностей на фондових біржах; в астрономії – виділення груп зірок і галактик, в ДЗЗ – автоматичної обробки космічних знімків. Можна стверджувати, що кластерний аналіз добре зарекомендував себе у всіх сферах життєдіяльності людини.
Кластеризація – це розбиття множини даних на кластери.
Кластери – підмножини однорідних одиниць сукупності, параметри яких заздалегідь невідомі.
Кластерний аналіз має низку переваг перед іншими методами класифікації даних.
По-перше, він дозволяє виконувати розбивку об’єктів як за однією ознакою, так і за цілим набором ознак. Причому вплив кожного з параметрів може бути доволі просто підсилений або послаблений шляхом внесення в математичні формули відповідних коефіцієнтів.
По-друге, кластерний аналіз не накладає обмежень на вид об’єктів групування і дозволяє розглядати безліч вихідних даних практично довільної природи.
По-третє, особливістю кластеризації є те, що більшість алгоритмів здатні самостійно визначити кількість кластерів, на які потрібно розбити дані, а також виділити характеристики цих кластерів без участі людини, тільки за допомогою використовуваного алгоритму.
Кластеризація методом k-середніх — популярний метод кластеризації, — впорядкування множини об'єктів в порівняно однорідні групи. Винайдений в 1950-х роках математиком Гуґо Штайнгаузом і майже одночасно Стюартом Ллойдом. Особливу популярність отримав після виходу роботи МакКвіна.
Мета методу — розділити n спостережень на k кластерів, так щоб кожне спостереження належало до кластера з найближчим до нього середнім значенням. Метод базується на мінімізації суми квадратів відстаней між кожним спостереженням та центром його кластера, тобто функції:
де d — метрика ( Евклідова відстань), xi— і-ий об'єкт даних, а mj— центр кластера, якому на j-ій ітерації приписаний елемент xi.
Алгоритм реалізації
Маємо масив спостережень (об'єктів), кожен з яких має певні значення по ряду ознак. Відповідно до цих значень об'єкт розташовується у багатовимірному просторі.
1. Дослідник визначає кількість кластерів, що необхідно утворити.
2. Випадковим чином обирається k спостережень, які на цьому кроці вважаються центрами кластерів. Візуально можна переглянути на рисунку 1, де k початкових «середніх» (тут k=3) випадково згенеровані у межах домена даних (кружечки).
Рисунок 1. Другий крок алгоритму
3. Кожне спостереження «приписується» до одного з n кластерів — того, відстань до якого найкоротша. Візуально можна переглянути на рисунку 2 (створено k кластерів, асоціюючи кожне спостереження з найближчим середнім. Розбиття відбувається згідно з діаграмою Вороного утвореною середніми).
Рисунок 2. Третій крок алгоритму
4. Розраховується новий центр кожного кластера як елемент, ознаки якого розраховуються як середнє арифметичне ознак об'єктів, що входять у цей кластер. Візуально можна переглянути на рисунку 3 (Центроїд кожного з k кластерів стає новим середнім).
Рисунок 3. Четвертий крок алгоритму
5. Відбувається така кількість ітерацій (повторюються кроки 3-4), поки кластерні центри стануть стійкими (тобто при кожній ітерації в кожному кластері опинятимуться одні й ті самі об'єкти), дисперсія всередині кластера буде мінімізована, а між кластерами — максимізована. Візуально можна переглянути на рисунку 4 (Кроки 3 і 4 повторюються до досягнення збіжності).
Рисунок 4. П'ятий крок алгоритму
Вибір кількості кластерів відбувається на основі дослідницької гіпотези. Якщо її немає, то рекомендують створити 2 кластери, далі 3,4,5, порівнюючи отримані результати.
Переваги та недоліки методу
Поширеність методу k-середніх зумовлено його головними перевагами: простотою, гнучкістю, швидкою збіжністю. Крім того, метод к-середніх може використовуватися для попереднього розбиття на групи великого набору даних, після якого проводиться більш потужний кластерний аналіз підкластера. Також метод може використовуватися, щоб «прикинути» кількість кластерів і перевірити наявність неврахованих даних і зв'язків в наборах. Варто відмітити, що метод k-середніх більш зручний для кластеризації великої кількості спостережень, ніж метод ієрархічного кластерного аналізу (у якому дендограми стають перевантаженими і втрачають наочність).
Незважаючи на очевидні переваги методу, він має суттєві недоліки:
1. Результат класифікації сильно залежить від випадкових початкових позицій кластерних центрів;
2. Алгоритм чутливий до викидів, які можуть викривлювати середнє;
3. Кількість кластерів повинна бути заздалегідь визначена дослідником;
4. Алгоритм може сходитися до локального мінімуму цільової функції.
Одним із недоліків простого методу є порушення умови зв'язності елементів одного кластера, тому розвиваються різні модифікації методу, а також його нечіткі аналоги (англ. fuzzy k-means methods), у яких на першій стадії алгоритму допускається приналежність одного елемента множини до декількох кластерів (із різним ступенем приналежності).
У методі k-середніх++ (k-means++) введено вдосконалену процедуру ініціалізації, що дозволяє покращити результати кластеризації за рахунок спеціального вибору початкової конфігурації центроїдів. Для прискорення процесу обчислення відстаней від точок до центроїдів було запропоновано відкидати з розгляду статичні центроїди, тобто такі, що залишилися на своїх позиціях на поточній ітерації. З метою запобігання локальній збіжності в запропоновано ітеративний алгоритм, що дозволяє наблизитися до глобального оптимуму шляхом покрокового послідовного запуску k-середніх. Даний метод було розвинуто шляхом застосування особливої структури даних — kd-дерев, що дозволило суттєво зменшити обчислювальну складність методу.
Порівняльний аналіз ієрархічних і неієрархічних методів кластеризації
Перед проведенням кластеризації в аналітика може виникнути питання: якій групі методів кластерного аналізу надати перевагу?
Вибираючи між ієрархічними й неієрархічними методами, потрібно враховувати їхні особливості.
Неієрархічні методи виявляють вищу стійкість щодо шумів і викидів, некоректного вибору метрики, введення незначущих змінних у набір, що бере участь у кластеризації. Ціною, що доводиться платити за ці переваги методу, є слово "апріорі". Аналітик повинен заздалегідь визначити кількість кластерів, кількість ітерацій або правило зупинки, а також деякі інші параметри кластеризації. Це особливо складно фахівцям-початківцям.
Якщо немає припущень щодо кількості кластерів, рекомендують використати ієрархічні алгоритми. Однак якщо обсяг вибірки не дозволяє це зробити, можливий шлях – провести низку експериментів з різною кількістю кластерів, наприклад, почати розбивку сукупності даних з двох груп і, поступово збільшуючи їх кількість, порівнювати результати. За рахунок такого "варіювання" результатів досягається доволі велика гнучкість кластеризації.
Ієрархічні методи, на відміну від неієрархічних, відмовляються від визначення кількості кластерів, а будують повне дерево вкладених кластерів.
Складності ієрархічних методів кластеризації: обмеження обсягу набору даних, вибір міри близькості, негнучкість отриманих класифікацій.
Перевага цієї групи методів порівняно з неієрархічними методами – їх наочність і можливість одержати детальне подання структури даних.
Використовуючи ієрархічні методи, можливо доволі легко ідентифікувати викиди в наборі даних й, у результаті, підвищити якість даних. Ця процедура є основою двокрокового алгоритму кластеризації. Такий набір даних надалі можна використати для проведення неієрархічної кластеризації.
Існує ще один аспект, про який слід згадати. Це питання кластеризації всієї сукупності даних або ж її вибірки. Названий аспект важливий для обох розглянутих груп методів, однак він критичніший для ієрархічних методів. Ієрархічні методи не можуть працювати з великими наборами даних, а використання деякої вибірки, тобто частини даних, могло б дозволити застосовувати ці методи.
Результати кластеризації можуть не мати достатнього статистичного обґрунтування. З іншого боку, під час розв’язання задач кластеризації допустима нестатистична інтерпретація отриманих результатів, а також доволі велика розмаїтість варіантів поняття кластера. Така нестатистична інтерпретація дає можливість аналітикові одержати результати кластеризації, які задовольняють його, що у разі використання інших методів часто доволі складно.
Ієрархічні алгоритми забезпечують порівняно високу якість кластеризації при високій наочності. Більшість з них мають складність O(f(n2)). Тому ієрархічні методи кластерного аналізу зазвичай використовуються при невеликих об’ємах наборів даних.
Приклад реалізації
Проведемо сегментування колишніх клієнтів фітнес-центру з відповідей респондентів на питання про те, якими наданих центром послуг вони користувалися. Попередньо для визначення оптимального числа кластерів та знаходження їх центрів була виконана ієрархічна кластеризація. Виявилося, що раціональним числом кластерів є чотири. За результатами попереднього розбиття на чотири кластери були розраховані центри цих кластерів, координати цих центрів були збережені у файлі.
Потім розділити клієнтів на чотири кластери було уточнено методом К-середніх, в якості початкових умов були взяті центри кластерів, збережені у файл. На рисунку 5 показано, яким чином в 14-й англомовної та 17-й російськомовної версії SPSS були обрані необхідні для кластеризації змінні і зроблені зазначені вище призначення.
На рисуноку 6 показано умови, при досягненні яких ітерації повинні бути припинені. Такими умовами можуть служити або досягнення максимально допустимого числа ітерацій (у даному разі 100), або той факт, що між черговими ітераціями критерій змінився менше, ніж на задане порогове значення. Одиницями вимірювання, при цьому служать відсотки від мінімальної відстані між початковими центрами кластерів. Якщо значення критерію дорівнює, наприклад, 0,02 ітерації припиняються, коли ні один з центрів кластерів не зрушується в результаті ітерації на відстань, що перевищує 2% від найменшої відстані між центрами будь-яких початкових кластерів. Якщо, як пропонується за умовчанням, задати порогове значення рівним нулю, ітерації будуть продовжуватися до тих пір, поки не виявиться, що чергова ітерація не перемістила з кластера в кластер жодного об'єкта.
Рисунок 5. Призначення змінних, числа кластерів і початкових центрів розбиття на кластери
Рисунок 6. Умови припинення ітерацій
Наведене діалогове вікно дозволяє також замовити режим використання ковзних середніх (Use running means). У цьому режимі центри кластерів перераховуються не як зазвичай, тобто після того як всі об'єкти в черговий раз розподілені між кластерами, виходячи з близькості до їх центрам, а після кожного "зарахування" об'єкта в той або інший кластер.
На рисуноку 7 показано, як замовляється збереження у файлі даних про номери кластерів і про відстанях від кожного об'єкта до "свого" центру. Якщо зробити такі призначення, у файлі з'являться два стовпця з відповідною інформацією. Зокрема, за значеннями у другому з цих стовпців можна сказати, наскільки кожен респондент схожий на основну масу представників кластера.
Нарешті, на рисунку 8 показано, як замовити видачу у файл звіту даних про те, які первинні центри були нами поставлені для кластеризації, а також як вивести у файл звіту довідкову таблицю, аналогічну таблиці дисперсійного аналізу. Ця таблиця допомагає простежити, по яким перемінним побудовані нами кластери істотно відрізняються один від одного, а за якими - незначно.
Перейдемо до розгляду результатів кластеризації методом К-середніх. Насамперед у файл звіту виводиться таблиця з координатами центрів одержані в результаті кластерів (таблиця 1).
Рисунок 7. Замовлення запису результатів кластеризації в файл з вихідними даними
Рисунок 8. Замовлення видачі в файл даних звіту про початкових умовах для кластеризації і таблиці, аналогічної таблиці дисперсійного аналізу
Таблиця 1. Координати центрів кластерів у просторі вихідних змінних
| Відвідували | Номери кластерів | |||
| 1 | 2 | 3 | 4 | |
| Тренажерний зал | 1,00 | 0,86 | 0,00 | 1,00 |
| Сауна | 0,00 | 0,95 | 0,28 | 1,00 |
| Солярій | 0,13 | 0,44 | 0,02 | 0,24 |
| Інфрачервоні кабіни | 0,04 | 0,82 | 0,02 | 0,00 |
| Зал аеробіки | 0,19 | 0,66 | 0,14 | 0,00 |
| Масажний кабінет | 0,06 | 0,19 | 0,02 | 0,16 |
Оскільки кластерний аналіз в даному випадку виконувався на бінарних (тобто містять лише нулі та одиниці) змінних, у клітинках таблиці наведено частки представників кластера, які користувалися цією послугою. Ми бачимо, наприклад, що всі без винятку представники першого кластера відвідували тренажерний зал, 19% від їх числа відвідували зал аеробіки, 13% - солярій. Іншими послугами мало хто з них користувався, причому сауну не відвідував ніхто з представників першого кластера. Таким чином, даним стилем користування послугами клубу природно дати умовну назву: "Тренажерний зал".
Зовсім інший стиль користування у представників четвертого кластера: всі вони відвідували тренажерний зал і сауну, а деякі - солярій і масажний кабінет (24 і 16% відповідно). Цей стиль ми назвали "Тренажерний зал і сауна".
Представники другого кластера користуються багатьма різними послугами фітнес-центру. Навіть такими рідко використовуються, як послуги масажиста, користується майже кожен п'ятий з них (19%). А 15% користуються послугами салону краси, якими в цілому за опитуванням користуються лише 8%, внаслідок чого ця змінна не враховувалася при побудові кластерів. Умовна назва цього стилю - "Різноманітні послуги".
Третій кластер - повна протилежність другого: його представники жодного разу не відвідували тренажерний зал, лише 2% від їх числа відвідували солярій, інфрачервоні кабіни і масажний кабінет. 14% з них ходили на аеробіку, 28% - в сауну, і це все, що вони робили в клубі, крім відвідування басейну. Оскільки басейн відвідують майже всі відвідувачі клубу (93%), відповідна змінна у кластеризації не брала участь. Проте виявилося, що басейн відвідували 100% представників третього кластера.
Таким чином, за допомогою кластерного аналізу вдалося виявити чотири абсолютно різних стилю користування послугами фітнес-клубу. Умовна назва цього стилю - "Басейн"
Наступна таблиця демонструє наповненість кластерів (таблиця 2).
Таблиця 2. Кількість респондентів у кожному кластері
| Кластер 1 | 48,000 |
| Кластер 2 | 73,000 |
| Кластер 3 | 43,000 |
| Кластер 4 | 50,000 |
| Дійсні | 214,000 |
| Пропущені | 0,000 |
Ми бачимо, що найбільш численним (73 людини, або 34% від числа усіх опитаних) є другий кластер, програма перебування представників якого в клубі найбільш різноманітна. Найменше клієнтів (43 людини, або 20%) у складі другого кластера, де мало користуються послугами клубу. Стилі ж "Тільки тренажери" і "Тренажери і сауна" майже однаково поширені: 48 і 50 чоловік, 22 і 23% відповідно. Як вже зазначалося, при використанні методу К-середніх можна вивести в файл звіту таблицю, аналогічну результатами дисперсійного аналізу (таблиця 3).
Таблиця 3. Таблиця результатів дисперсійного аналізу (ANOVA)
| Відвідували | Cluster | Error | F | Sig. | |||||
| Mean Square | df | Mean Square | df | ||||||
| Тренажерний зал | 10,415 | 3 | 0,041 | 210 | 253,421 | 0,000 | |||
| Сауна | 12,792 | 3 | 0,059 | 210 | 216,084 | 0,000 | |||
| Солярій | 1,842 | 3 | 0,159 | 210 | 11,610 | 0,000 | |||
| Інфрачервоні кабінети | 10,292 | 3 | 0,065 | 210 | 159,169 | 0,000 | |||
| Зал аеробіки | 5,180 | 3 | 0,138 | 210 | 37,621 | 0,000 | |||
| Масажний кабінет | 0,339 | 3 | 0,104 | 210 | 3,261 | 0,022 | |||
Дисперсійний аналіз (ANOVA) використовується у випадках, коли вибірка розділена з якого-небудь ознакою і потрібно перевірити, чи відрізняються середні значення вихідних змінних при різних значеннях цієї ознаки. Для кожної ознаки за F-критерієм Фішера перевіряється нульова гіпотеза про те, що спостережувані відмінності середніх значень випадкові, а насправді (у всій досліджуваній сукупності, а не вибірці) вони збігаються, тобто що міжкластерна дисперсія незначно відрізняється від внутрікластерной. Відзначимо, однак, що у випадку кластерного аналізу така сувора статистична інтерпретація даних таблиці дисперсійного аналізу неможлива, оскільки об'єкти спеціально розкладалися по кластерам так, щоб відмінності стали значущими. Використовувати таблицю можна лише у суто інформаційних цілях: з неї видно, з яким вихідним змінним середні значення відрізняються суттєво, а за яких - ні. Так, ми бачимо, що слабше всього розрізняється між кластерами частка респондентів, які користуються послугами масажного кабінету.
Львів - 2020