DBSCAN із Scikit-Learn у Python

Вступ

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

Перевіряючи дані різних груп студентів, ви натрапили на три розташування точок, як у пунктах 1, 2 і 3 нижче:

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

На малюнку 2 є кругла маса фіолетових точок, ще одна помаранчевих точок, а також чотири сірі точки, які далекі від усіх інших.

А на графіку 3 ми можемо побачити чотири концентрації точок, фіолетову, синю, помаранчеву, рожеву, і ще три віддалені сірі точки.

Тепер, якби ви вибрали модель, яка могла б зрозуміти нові дані студентів і визначити подібні групи, чи існує алгоритм кластеризації, який міг би дати цікаві результати для таких даних?

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

Алгоритм на основі щільності, який може фільтрувати шум, наприклад DBSCAN (Dсутність-Based Sпатіальний Cлюстрування Aдодатки с Noise), є сильним вибором для ситуацій із більш щільними областями, округлими формами та шумом.

Про DBSCAN

DBSCAN є одним із найбільш цитованих алгоритмів у дослідженнях, його перша публікація з’явилася в 1996 році, це оригінальний папір DBSCAN. У статті дослідники демонструють, як алгоритм може ідентифікувати нелінійні просторові кластери та ефективно обробляти дані з більшою розмірністю.

Основна ідея DBSCAN полягає в тому, що існує мінімальна кількість точок, які будуть на певній відстані або радіус від самої «центральної» точки кластера, наз основний пункт. Точки в межах цього радіуса є околицями, а точки на краю цього околиці є прикордонні пункти or граничні точки. Радіус або відстань околиці називається околиці епсилон, ε-околиці або просто ε (символ грецької літери епсилон).

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

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

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

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

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

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

Подивимося, як це працює на практиці!

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

Щоб побачити, як DBSCAN працює на практиці, ми дещо змінимо проекти та використаємо невеликий набір даних про клієнтів із жанром, віком, річним доходом і оцінкою витрат 200 клієнтів.

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

Після завантаження набору даних ви побачите, що це файл CSV (значення, розділені комами). shopping-data.csv, ми завантажимо його в DataFrame за допомогою Pandas і збережемо в customer_data змінна:

import pandas as pd path_to_file = '../../datasets/dbscan/dbscan-with-python-and-scikit-learn-shopping-data.csv'
customer_data = pd.read_csv(path_to_file)

Щоб переглянути перші п’ять рядків наших даних, ви можете виконати customer_data.head():

Це призводить до:

 CustomerID Genre Age Annual Income (k$) Spending Score (1-100)
0 1 Male 19 15 39
1 2 Male 21 15 81
2 3 Female 20 16 6
3 4 Female 23 16 77
4 5 Female 31 17 40

Вивчаючи дані, ми можемо побачити ідентифікаційні номери клієнтів, жанр, вік, доходи в тисячах доларів і оцінки витрат. Майте на увазі, що деякі або всі ці змінні будуть використані в моделі. Наприклад, якби ми мали використовувати Age та Spending Score (1-100) як змінні для DBSCAN, який використовує метрику відстані, важливо привести їх до спільного масштабу, щоб уникнути внесення спотворень, оскільки Age вимірюється в роках і Spending Score (1-100) має обмежений діапазон від 0 до 100. Це означає, що ми будемо виконувати певне масштабування даних.

Ми також можемо перевірити, чи потребують дані додаткової попередньої обробки, окрім масштабування, перевіривши, чи є тип даних послідовним, і перевіривши, чи є якісь відсутні значення, які потрібно обробити, виконавши Panda info() метод:

customer_data.info()

Тут відображається:

<class 'pandas.core.frame.DataFrame'>
RangeIndex: 200 entries, 0 to 199
Data columns (total 5 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 CustomerID 200 non-null int64 1 Genre 200 non-null object 2 Age 200 non-null int64 3 Annual Income (k$) 200 non-null int64 4 Spending Score (1-100) 200 non-null int64 dtypes: int64(4), object(1)
memory usage: 7.9+ KB

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

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

Цей набір даних клієнта такий самий, як той, що використовується в нашому повному посібнику з ієрархічної кластеризації. Щоб дізнатися більше про ці дані, як їх досліджувати та про показники відстані, ви можете переглянути Повний посібник з ієрархічної кластеризації за допомогою Python і Scikit-Learn!

Візуалізація даних

За допомогою Seaborn's pairplot(), ми можемо побудувати графік розсіювання для кожної комбінації ознак. Оскільки CustomerID це лише ідентифікація, а не функція, ми видалимо його за допомогою drop() до побудови:

import seaborn as sns customer_data = customer_data.drop('CustomerID', axis=1) sns.pairplot(customer_data);

Це виводить:

Дивлячись на комбінацію функцій, створених pairplot, графік Annual Income (k$) з Spending Score (1-100) здається, відображає близько 5 груп точок. Це здається найбільш перспективним поєднанням функцій. Ми можемо створити список із їхніми іменами, вибрати їх із customer_data DataFrame і збережіть виділення в customer_data знову змінна для використання в нашій майбутній моделі.

selected_cols = ['Annual Income (k$)', 'Spending Score (1-100)']
customer_data = customer_data[selected_cols]

Після вибору стовпців ми можемо виконати масштабування, описане в попередньому розділі. Щоб привести функції до однакового масштабу або стандартизувати їх, ми можемо імпортувати Scikit-Learn StandardScaler, створіть його, підберіть наші дані, щоб обчислити його середнє значення та стандартне відхилення, і перетворите дані, віднімаючи його середнє значення та ділячи його на стандартне відхилення. Це можна зробити в один крок за допомогою fit_transform() метод:

from sklearn.preprocessing import StandardScaler ss = StandardScaler() scaled_data = ss.fit_transform(customer_data)

Тепер змінні масштабовані, і ми можемо перевірити їх, просто надрукувавши вміст scaled_data змінна. Крім того, ми також можемо додати їх до нового scaled_customer_data DataFrame разом із назвами стовпців і використовуйте head() знову метод:

scaled_customer_data = pd.DataFrame(columns=selected_cols, data=scaled_data)
scaled_customer_data.head()

Це виводить:

 Annual Income (k$) Spending Score (1-100)
0 -1.738999 -0.434801
1 -1.738999 1.195704
2 -1.700830 -1.715913
3 -1.700830 1.040418
4 -1.662660 -0.395980 

Ці дані готові для кластеризації! Представляючи DBSCAN, ми згадували мінімальну кількість точок і епсилон. Ці два значення потрібно вибрати перед створенням моделі. Давайте подивимося, як це робиться.

Вибір мін. Зразки та Епсилон

Щоб вибрати мінімальну кількість точок для кластеризації DBSCAN, існує емпіричне правило, яке стверджує, що вона має дорівнювати або перевищувати кількість вимірів у даних плюс один, як у:

$$
текст{мін. пункти} >= текст{розміри даних} + 1
$$

Розміри – це кількість стовпців у кадрі даних, ми використовуємо 2 стовпці, тому мін. балів має бути або 2+1, тобто 3, або вище. Для цього прикладу скористаємося 5 хв. балів.

$$
текст{5 (мін. бали)} >= текст{2 (розміри даних)} + 1
$$

Тепер, щоб вибрати значення для ε, існує метод, у якому a Найближчі сусіди алгоритм використовується, щоб знайти відстань до попередньо визначеної кількості найближчих точок для кожної точки. Ця заздалегідь визначена кількість сусідів є мін. точки, які ми щойно вибрали мінус 1. Отже, у нашому випадку алгоритм знайде 5-1 або 4 найближчі точки для кожної точки наших даних. це те k-сусідів і наші k дорівнює 4.

$$
текст{k-сусідів} = текст{мін. бали} – 1
$$

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

Щоб виконати ці кроки, ми можемо імпортувати алгоритм, підібрати його до даних, а потім витягти відстані та індекси кожної точки за допомогою kneighbors() метод:

from sklearn.neighbors import NearestNeighbors
import numpy as np nn = NearestNeighbors(n_neighbors=4) nbrs = nn.fit(scaled_customer_data)
distances, indices = nbrs.kneighbors(scaled_customer_data)

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

distances = np.sort(distances, axis=0)
distances = distances[:,1] 

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

import matplotlib.pyplot as plt plt.figure(figsize=(6,3))
plt.plot(distances)
plt.axhline(y=0.24, color='r', linestyle='--', alpha=0.4) plt.title('Kneighbors distance graph')
plt.xlabel('Data points')
plt.ylabel('Epsilon value')
plt.show();

Ось результат:

Зауважте, що під час малювання лінії ми дізнаємося значення ε, у даному випадку воно є 0.24.

Нарешті ми маємо точки мінімуму та ε. З обома змінними ми можемо створити та запустити модель DBSCAN.

Створення моделі DBSCAN

Щоб створити модель, ми можемо імпортувати її з Scikit-Learn, створити її за допомогою ε, яке є таким самим, як і eps аргумент і мінімальні точки, до яких відноситься mean_samples аргумент. Потім ми можемо зберегти це в змінній, назвемо її dbs і підігнати його до масштабованих даних:

from sklearn.cluster import DBSCAN dbs = DBSCAN(eps=0.24, min_samples=5)
dbs.fit(scaled_customer_data)

Ось так наша модель DBSCAN була створена та навчена на даних! Щоб отримати результати, ми отримуємо доступ до labels_ власність. Ми також можемо створити новий labels у стовпці scaled_customer_data кадр даних і заповнити його передбаченими мітками:

labels = dbs.labels_ scaled_customer_data['labels'] = labels
scaled_customer_data.head()

Ось кінцевий результат:

 Annual Income (k$) Spending Score (1-100) labels
0 -1.738999 -0.434801 -1
1 -1.738999 1.195704 0
2 -1.700830 -1.715913 -1
3 -1.700830 1.040418 0
4 -1.662660 -0.395980 -1

Зверніть увагу, що ми маємо мітки з -1 цінності; це точки шуму, ті, що не належать до жодного кластера. Щоб дізнатися, скільки точок шуму знайдено алгоритмом, ми можемо порахувати, скільки разів значення -1 з’являється в нашому списку міток:

labels_list = list(scaled_customer_data['labels'])
n_noise = labels_list.count(-1)
print("Number of noise points:", n_noise)

Це виводить:

Number of noise points: 62

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

Спочатку, коли ми спостерігали за даними, здавалося, що вони містять 5 кластерів точок. Щоб дізнатися, скільки кластерів сформував DBSCAN, ми можемо підрахувати кількість міток, які не є -1. Є багато способів написати цей код; тут ми написали цикл for, який також працюватиме для даних, у яких DBSCAN знайшов багато кластерів:

total_labels = np.unique(labels) n_labels = 0
for n in total_labels: if n != -1: n_labels += 1
print("Number of clusters:", n_labels)

Це виводить:

Number of clusters: 6

Ми бачимо, що алгоритм передбачив, що дані мають 6 кластерів із багатьма шумовими точками. Давайте візуалізуємо це, поклавши це на графік із Сіборном scatterplot:

sns.scatterplot(data=scaled_customer_data, x='Annual Income (k$)', y='Spending Score (1-100)', hue='labels', palette='muted').set_title('DBSCAN found clusters');

Це призводить до:

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

Якщо ми виділимо кластери, зверніть увагу, як DBSCAN повністю отримує кластер 1, який є кластером з меншим простором між точками. Потім він отримує частини кластерів 0 і 3, де точки розташовані близько одна до одної, розглядаючи більш віддалені точки як шум. Він також розглядає точки в нижній лівій половині як шум і розділяє точки в нижній правій частині на 3 кластери, знову захоплюючи кластери 4, 2 і 5, де точки розташовані ближче одна до одної.

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

Оцінка алгоритму

Щоб оцінити DBSCAN, ми будемо використовувати партитура силуету який буде враховувати відстань між точками одного кластера та відстані між кластерами.

По-перше, ми можемо імпортувати silhouette_score від Scikit-Learn, потім передайте йому наші стовпці та мітки:

from sklearn.metrics import silhouette_score s_score = silhouette_score(scaled_customer_data, labels)
print(f"Silhouette coefficient: {s_score:.3f}")

Це виводить:

Silhouette coefficient: 0.506

Відповідно до цієї оцінки, здається, що DBSCAN міг би охопити приблизно 50% даних.

Висновок

Переваги та недоліки DBSCAN

DBSCAN — це дуже унікальний алгоритм або модель кластеризації.

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

Це вимагає від нас вказати мінімальні точки та ε, але немає необхідності вказувати кількість кластерів заздалегідь, як, наприклад, у K-Means. Його також можна використовувати з дуже великими базами даних, оскільки він розроблений для даних великого розміру.

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

Розширення DBSCAN

Є й інші алгоритми, наприклад Ієрархічний DBSCAN (HDBSCAN) та Впорядкування точок для визначення структури кластеризації (OPTICS), які вважаються розширеннями DBSCAN.

І HDBSCAN, і OPTICS зазвичай можуть працювати краще, коли в даних є кластери різної щільності, а також менш чутливі до вибору або початкової мін. точок і параметрів ε.

• Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
• Платоблокчейн. Web3 Metaverse Intelligence. Розширені знання. Доступ тут.
• джерело: https://stackabuse.com/dbscan-with-scikit-learn-in-python/