Огляд алгоритмів кластеризації даних

У своїй дипломній роботі я проводив огляд та порівняльний аналіз алгоритмів кластеризації даних. Подумав, що вже зібраний та опрацьований матеріал може виявитися комусь цікавим та корисним.
Про те, що таке кластеризація, розповів sashaeve у статті «Кластеризація: алгоритми k-means та c-means». Я частково повторю слова Олександра, частково доповню. Також наприкінці цієї статті можуть почитати матеріали за посиланнями у списку літератури.

Також я постарався привести сухий «дипломний» стиль викладу до публіцистичнішого.

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

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

1. Вибір вибірки об'єктів для кластеризації.
2. Визначення безлічі змінних, якими оцінюватимуться об'єкти у вибірці. За потреби – нормалізація значень змінних.
3. Обчислення значень міри схожості між об'єктами.
4. Застосування методу кластерного аналізу до створення груп подібних об'єктів (кластерів).
5. Подання результатів аналізу.

міри відстаней

Отже, як визначати «схожість» об'єктів? Для початку потрібно скласти вектор характеристик для кожного об'єкта - як правило, це набір числових значень, наприклад, зростання ваги людини. Проте існують також алгоритми, які працюють із якісними (т.зв. категорійними) характеристиками.

Після того, як ми визначили вектор характеристик, можна провести нормалізацію, щоб усі компоненти давали однаковий вклад при розрахунку відстані. У процесі нормалізації всі значення призводять до деякого діапазону, наприклад [-1, -1] або [0, 1].

Євклідова відстань
Найбільш поширена функція відстані. Являє собою геометричну відстань у багатовимірному просторі:

Класифікація алгоритмів

1. Ієрархічні та плоскі.
   Ієрархічні алгоритми (також звані алгоритмами таксономії) будують не одне розбиття вибірки на кластери, що не перетинаються, а систему вкладених розбиття. Т.о. на виході ми отримуємо дерево кластерів, корінням якого є вся вибірка, а листям — найдрібніші кластери.
   Плоскі алгоритми будують одне розбиття об'єктів на кластери.
2. Чіткі та нечіткі.
   Чіткі (чи непересічні) алгоритми кожному об'єкту вибірки ставлять у відповідність номер кластера, тобто. кожен об'єкт належить лише одному кластеру. Нечіткі (або пересічні) алгоритми кожному об'єкту ставлять у відповідність набір речових значень, що показують ступінь ставлення об'єкта до кластерів. Тобто. кожен об'єкт відноситься до кожного кластера з деякою ймовірністю.

Об'єднання кластерів

1. Одиночний зв'язок (відстань найближчого сусіда)
   У цьому методі відстань між двома кластерами визначається відстанню між двома найближчими об'єктами (найближчими сусідами) у різних кластерах. Результуючі кластери мають тенденцію поєднуватися в ланцюжки.
   
2. Повний зв'язок (відстань найбільш віддалених сусідів)
   У цьому методі відстані між кластерами визначаються найбільшою відстанню між будь-якими двома об'єктами в різних кластерах (тобто найбільш віддаленими сусідами).Цей метод зазвичай працює дуже добре, коли об'єкти походять з окремих груп. Якщо ж кластери мають подовжену форму або їх природний тип є «ланцюжковим», цей метод непридатний.
   
3. Незважена попарна середня
   У цьому методі відстань між двома різними кластерами обчислюється як середня відстань між усіма парами об'єктів у них. Метод ефективний, коли об'єкти формують різні групи, проте він працює однаково добре і у випадках протяжних («ланцюжкового» типу) кластерів.
   
4. Зважена попарна середня
   Метод ідентичний методу невваженого попарного середнього, за винятком того, що при обчисленнях розмір відповідних кластерів (тобто кількість об'єктів, що містяться в них) використовується як ваговий коефіцієнт. Тому цей метод має бути використаний, коли передбачаються нерівні розміри кластерів.
   
5. Незважений центроїдний метод
   У цьому методі відстань між двома кластерами визначається як відстань між їхніми центрами тяжіння.
   
6. Зважений центроїдний метод (медіана)
   Цей метод ідентичний попередньому, крім того, що з обчислення використовуються ваги для обліку різниці між розмірами кластерів. Тому, якщо є або підозрюються значні відмінності у розмірах кластерів, цей метод виявляється кращим за попередній.
   

Огляд алгоритмів

Алгоритми ієрархічної кластеризації

Серед алгоритмів ієрархічної кластеризації виділяються два основні типи: висхідні та низхідні алгоритми. Низхідні алгоритми працюють за принципом «зверху-вниз»: на початку всі об'єкти поміщаються в один кластер, який потім розбивається на дрібніші кластери.Найбільш поширені висхідні алгоритми, які на початку роботи поміщають кожен об'єкт в окремий кластер, а потім об'єднують кластери в дедалі більші, поки всі об'єкти вибірки не будуть утримуватися в одному кластері. У такий спосіб будується система вкладених розбиття. Результати таких алгоритмів зазвичай у вигляді дерева – дендрограми. Класичний приклад такого дерева – класифікація тварин та рослин.

Для обчислення відстаней між кластерами найчастіше користуються двома відстанями: одиночним або повним зв'язком (див. огляд мір відстаней між кластерами).

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

Алгоритми квадратичної помилки

Завдання кластеризації можна як побудова оптимального розбиття об'єктів на групи. При цьому оптимальність може бути визначена як вимога мінімізації середньоквадратичної помилки розбиття:

де c_j - «Центр мас» кластера j (Точка із середніми значеннями характеристик для даного кластера).

1. Випадково вибрати k точок, які є початковими центрами мас кластерів.
2. Віднести кожен об'єкт до кластера з найближчим центром мас.
3. Перерахувати «центри мас» кластерів відповідно до їхнього поточного складу.
4. Якщо критерій зупинення алгоритму незадоволений, повернутися до п. 2.

До недоліків даного алгоритму можна віднести необхідність задавати кількість кластерів для розбиття.

Нечіткі алгоритми

1. Вибрати початкове нечітке розбиття n об'єктів на k кластерів шляхом вибору матриці приладдя U розміру n x k.
2. Використовуючи матрицю U, знайти значення критерію нечіткої помилки:
   ,
   де c_k - «Центр мас» нечіткого кластера k:
   .
3. Перегрупувати об'єкти для зменшення цього значення критерію нечіткої помилки.
4. Повертатися до п. 2 доти, доки зміни матриці U не стануть незначними.

Алгоритми, засновані на теорії графів

Суть таких алгоритмів у тому, що вибірка об'єктів представляється як графа G = (V, E), вершинам якого відповідають об'єкти, а ребра мають вагу, що дорівнює «відстанню» між об'єктами. Перевагою графових алгоритмів кластеризації є наочність, відносна простота реалізації та можливість внесення різних удосконалень, що ґрунтуються на геометричних міркуваннях. Основними алгоритмами є алгоритм виділення зв'язкових компонентів, алгоритм побудови мінімального покриваючого (остовного) дерева та алгоритм пошарової кластеризації.

Алгоритм виділення зв'язкових компонентів

В алгоритмі виділення зв'язкових компонентів задається вхідний параметр R і у графі видаляються всі ребра, для яких «відстань» більше R. Сполученими залишаються лише найближчі пари об'єктів. Сенс алгоритму полягає в тому, щоб підібрати таке значення R, що лежить в діапазоні всіх «відстаней», при якому граф «розвалиться» на кілька зв'язкових компонентів. Отримані компоненти є кластери.

Для вибору параметра R зазвичай будується гістограма розподілів попарних відстаней. У завданнях із добре вираженою кластерною структурою даних на гістограмі буде два піки – один відповідає внутрішньокластерним відстаням, другий – міжкластерним відстані. Параметр R підбирається із зони мінімуму між цими піками. У цьому керувати кількістю кластерів з допомогою порога відстані досить складно.

Алгоритм мінімального дерева, що покриває.

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

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

Пошарова кластеризація

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

Алгоритм пошарової кластеризації формує послідовність підграфів графа G, що відображають ієрархічні зв'язки між кластерами:

де G t = (V, E t ) - граф на рівні з t ,
,
з t - t-ий поріг відстані,
m – кількість рівнів ієрархії,
G 0 = (V, o), o – порожня безліч ребер графа, одержуване при t 0 = 1,
G m = G, тобто граф об'єктів без обмежень на відстань (довжину ребер графа), оскільки t m = 1.

Порівняння алгоритмів

Трохи про застосування

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

На відміну від повнозв'язкового графа, в орієнтованому дереві в повному обсязі вершини з'єднані ребрами, у своїй загальна кількість ребер дорівнює n–1, де n – число вершин. Тобто. Стосовно вузлів дерева робота алгоритму виділення зв'язкових компонент спроститься, оскільки видалення будь-якої кількості ребер «розвалить» дерево на зв'язкові компоненти (окремі дерева). Алгоритм мінімального покриваючого дерева в даному випадку збігатиметься з алгоритмом виділення зв'язкових компонентів - шляхом видалення найдовших ребер вихідне дерево розбивається на кілька дерев. При цьому очевидно, що фаза побудови найменшого дерева, що покриває, пропускається.

У разі використання інших алгоритмів у них довелося окремо враховувати наявність зв'язків між об'єктами, що ускладнює алгоритм.

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

Список литературы

1. Воронцов К.В. Алгоритми кластеризації та багатовимірного шкалювання. Курс лекцій. МДУ, 2007.
2. Jain A., Murty M., Flynn P. Data Clustering: A Review. // ACM Computing Surveys. 1999. Vol. 31, no. 3.
3. Котов А., Красильников Н. Кластеризація даних. 2006.
3. Мандель І. Д. Кластерний аналіз - М.: Фінанси та Статистика, 1988.
4. Прикладна статистика: класифікація та зниження розмірності. / С.А. Айвазян, В.М. Бухштабер, І.С. Єнюков, Л.Д. Мешалкін - М.: Фінанси та статистика, 1989.
5. Інформаційно-аналітичний ресурс, присвячений машинному навчанню, розпізнаванню образів та інтелектуальному аналізу даних - www.machinelearning.ru
6. Чубукова І.А. Курс лекцій "Data Mining", Інтернет-університет інформаційних технологій - www.intuit.ru/department/database/datamining

Кластеризація даних: методи та приклади

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

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

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

Основні алгоритми кластеризації

K-середніх (K-means)

Алгоритм K-середніх є одним із найпопулярніших і найпростіших методів кластеризації. Він працює наступним чином:

1. Вибирається кількість кластерів K.
2. Ініціалізуються K центроїдів випадковим чином.
3. Кожен об'єкт даних надається найближчому центроїду.
4. Центроїди перераховуються як середнє значення об'єктів у кожному кластері.
5. Кроки 3 і 4 повторюються доти, доки центроїди не перестануть змінюватися.

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

Ієрархічна кластеризація

Ієрархічна кластеризація поділяється на два типи: агломеративна та дивізіонна.Агломеративна кластеризація починається з кожного об'єкта як окремого кластера і поступово об'єднує їх, доки залишиться один кластер. Дивізіонна кластеризація, навпаки, починає з одного великого кластера і поступово поділяє його на менші кластери.

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

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN — це метод кластеризації, що ґрунтується на щільності даних. Він визначає кластери як області з високою густиною об'єктів, розділені областями з низькою густиною. Основні параметри DBSCAN:

• Eps: радіус околиці для пошуку сусідніх точок.
• MinPts: мінімальна кількість точок для формування щільного регіону.

DBSCAN добре справляється з кластерами довільної форми та стійкий до шуму, але потребує ретельного налаштування параметрів. Цей метод особливо корисний для даних з нерівномірною густиною, де традиційні методи, такі як K-середніх, можуть не впоратися. Однак, вибір параметрів Eps та MinPts може бути складним завданням і потребує експериментів та аналізу даних.

Алгоритм середніх зрушень (Mean Shift)

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

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

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

Маркетинг та сегментація клієнтів

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

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

Обробка зображень

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

Кластеризація також може бути використана для аналізу медичних зображень, таких як МРТ та КТ, для виявлення аномалій та діагностики захворювань. Це може допомогти лікарям приймати більш обґрунтовані рішення та покращувати якість медичної допомоги.

Біоінформатика

У біоінформатиці кластеризація використовується для аналізу геномних даних та виявлення груп генів зі схожими виразами. Наприклад, ієрархічна кластеризація може допомогти виявити групи генів, які активуються у відповідь на певні умови, що є корисним для розуміння біологічних процесів. Це може включати аналіз даних про генну експресію, виявлення біомаркерів та розробку нових ліків.

Кластеризація також може бути використана для аналізу даних про білки та виявлення груп білків зі схожими функціями та структурами. Це може допомогти вченим краще розуміти біологічні процеси та розробляти нові методи лікування захворювань.

Аналіз соціальних мереж

Кластеризація може використовуватися для аналізу соціальних мереж та виявлення груп користувачів зі схожими інтересами та поведінкою. Наприклад, DBSCAN може допомогти виявити спільноти користувачів, які активно взаємодіють один з одним, що є корисним для аналізу структури соціальних мереж. Це може включати аналіз даних про взаємодії користувачів, виявлення ключових впливових осіб та розробку стратегій взаємодії з користувачами.

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

Переваги та недоліки різних методів

K-середніх

Переваги:

• Простота та швидкість реалізації.
• Добре працює з великими наборами даних.
• Ефективний для даних із сферичною формою кластерів та однаковим розміром.

Недоліки:

• Потребує заздалегідь заданої кількості кластерів.
• Чутливий до вибору початкових центроїдів.
• Погано справляється з кластерами довільної форми та різної щільності.

Ієрархічна кластеризація

Переваги:

• Не вимагає попередньо заданої кількості кластерів.
• Надає зручну візуалізацію у вигляді дендрограми.
• Дозволяє досліджувати дані на різних рівнях деталізації.

Недоліки:

• Обчислювально витратний великих наборів даних.
• Може бути чутливим до шуму та викидів.
• Може вимагати значних обчислювальних ресурсів обробки великих даних.

DBSCAN

Переваги:

• Добре справляється із кластерами довільної форми.
• Стійкий до шуму.
• Ефективний для даних із нерівномірною щільністю.

Недоліки:

• Вимагає ретельного налаштування параметрів.
• Може бути складним для інтерпретації результатів.
• Не завжди підходить для даних із рівномірною щільністю кластерів.

Алгоритм середніх зрушень

Переваги:

• Не потребує заздалегідь заданої кількості кластерів.
• Добре працює із кластерами довільної форми.
• Автоматично визначає кількість кластерів.

Недоліки:

• Обчислювально витратний для великих наборів даних.
• Може бути чутливим до вибору початкових параметрів.
• Вимагає значних обчислювальних ресурсів обробки великих даних.

Висновок та рекомендації для новачків

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

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

Спробуйте застосувати описані алгоритми на своїх даних та оцініть їх ефективність. Це може включати використання різних інструментів та бібліотек, таких як Scikit-learn, для реалізації та тестування алгоритмів кластеризації. Успіхів у вивченні та застосуванні кластеризації даних! 😉

Читайте також

• Регресія у Data Science: що це і як працює
• Ключові концепції Data Science
• Професії та ролі в Data Science
• Аналіз даних: методи та підходи
• Статистичні методи у Data Science
• Збір даних: перший крок у Data Science
• Обробка природної мови (NLP) у Data Science
• Навички та компетенції для кар'єри в Data Science
• Правові норми та регуляції в Data Science
• Бібліотеки та фреймворки для Data Science: TensorFlow та PyTorch