Групиране на данни в групи, част 3

СТАТИЯ

Групиране на данни в групи, част 3

От Data Science Bookcamp от Леонард Апелцин

Тази поредица от статии от 3 части обхваща:

Клъстериране на данни по централно място
Клъстериране на данни по плътност
Компромиси между алгоритми за клъстериране
Извършване на групиране с помощта на библиотеката scikit-learn
Итериране на клъстери с помощта на Pandas

Вземете 35% отстъпка Data Science Bookcamp, като въведете fccapeltsin в полето за код за отстъпка при плащане на manning.com.

В случай, че сте ги пропуснали, вижте част 1 и част 2.

DBSCAN: Алгоритъм за клъстериране за групиране на данни въз основа на пространствена плътност

DBSCAN е акроним, който означава базирано на плътност пространствено групиране на приложения с шум. Това е абсурдно дълго име за това, което по същество е много проста техника:

Изберете произволна point координата от data списък.
Вземете всички съседи в рамките на epsilon разстояние от това point.
Ако бъдат открити по-малко от min_points съседи, повторете стъпка 1, като използвате различна произволна точка. В противен случай групирайте point и неговите съседи в един клъстер.
Итеративно повторете стъпки 2 и 3 за всички новооткрити съседи. Всички съседни плътни точки се сливат в клъстера. Итерациите приключват, след като клъстерът спре да се разширява.
След като извлечете целия клъстер, повторете стъпки 1–4 за всички точки от данни, чиято плътност все още не е анализирана.

Процедурата DBSCAN може да бъде програмирана в по-малко от 20 реда код. Въпреки това, всяка основна реализация ще работи много бавно в нашия rocks списък. Програмирането на бърза реализация изисква някои много нюансирани оптимизации, които подобряват скоростта на преминаване на съседите и са извън обхвата на тази книга. За щастие, няма нужда да възстановяваме алгоритъма от нулата: scikit-learn предоставя бърз DBSCAN клас, който можем да импортираме от sklearn.cluster. Нека импортираме и инициализираме класа, като присвоим epsilon и min_points с помощта на параметрите eps и min_samples. След това използваме DBSCAN, за да групираме нашите три пръстена (фигура 13).

Списък 21. Използване на DBSCAN за групиране на пръстениs

from sklearn.cluster import DBSCAN
 cluster_model = DBSCAN(eps=epsilon, min_samples=min_points) (1)
 rock_clusters = cluster_model.fit_predict(rocks) (2)
 colors = [['g', 'y', 'k'][cluster] for cluster in rock_clusters]
 plt.scatter(x_coordinates, y_coordinates, color=colors)
 plt.show()

❶ Създава обект cluster_model за извършване на групиране по плътност. Стойност на епсилон от 0,1 се предава с помощта на параметъра eps. Стойност min_points от 10 се предава с помощта на параметъра min_samples.

❷ Групира скалните пръстени въз основа на плътността и връща присвоения клъстер за всяка скала

DBSCAN успешно идентифицира трите скални пръстена. Алгоритъмът успя там, където K-средните се провалиха.

Сравнение на DBSCAN и K-средни

DBSCAN е изгоден алгоритъм за групиране на данни, съставени от извити и плътни форми. Освен това, за разлика от K-средните, алгоритъмът не изисква приближение на броя на клъстерите преди изпълнение. Освен това DBSCAN може да филтрира произволни извънредни стойности, разположени в оскъдни региони на пространството. Например, ако добавим отклонение, разположено отвъд границата на пръстените, DBSCAN ще му присвои идентификатор на клъстер от -1. Отрицателната стойност показва, че отклонението не може да бъде групирано с останалата част от набора от данни.

За разлика от K-средствата, монтираният DBSCAN модел не може да бъде приложен отново към чисто нови данни. Вместо това трябва да комбинираме нови и стари данни и да изпълним клъстерирането от нулата. Това е така, защото изчислените K-средни центрове могат лесно да бъдат сравнени с допълнителни точки от данни. Въпреки това, допълнителните точки от данни могат да повлияят на разпределението на плътността на предишни данни, което принуждава DBSCAN да преизчисли всички клъстери.

Списък 22. Намиране на отклонения чрез DBSCAN

noisy_data = rocks + [[1000, -1000]]
 clusters = DBSCAN(eps=epsilon,
                   min_samples=min_points).fit_predict(noisy_data)
 assert clusters[-1] == -1

Друго предимство на техниката DBSCAN е, че тя не зависи от средната стойност. Междувременно алгоритъмът за K-средни изисква от нас да изчислим средните координати на групирани точки. Както обсъдихме в раздел 5, тези средни координати минимизират сумата от квадратите на разстоянията до центъра. Свойството за минимизиране е валидно само ако разстоянията на квадрат са евклидови. По този начин, ако нашите координати не са евклидови, средната стойност не е много полезна и алгоритъмът на K-средните не трябва да се прилага. Евклидовото разстояние обаче не е единствената метрика за измерване на разделянето между точките — съществуват безкрайни метрики за определяне на разстоянието. Разглеждаме някои от тях в следващия подраздел. В процеса научаваме как да интегрираме тези показатели в нашия DBSCAN клъстерен изход.

Групиране въз основа на неевклидово разстояние

Да предположим, че посещаваме Манхатън и искаме да знаем разстоянието пеша от Емпайър Стейт Билдинг до Кълъмбъс Съркъл. Емпайър Стейт Билдинг се намира на кръстовището на 34-та улица и Пето авеню. Междувременно Columbus Circle се намира на кръстовището на 57-ма улица и Осмо авеню. Улиците и булевардите в Манхатън винаги са перпендикулярни една на друга. Това ни позволява да представим Манхатън като 2D координатна система, където улиците са разположени по оста x, а булевардите са разположени по оста y. Под това представяне Емпайър Стейт Билдинг е разположен на координата (34, 5), а Кълъмбъс Съркъл е разположен на координата (57, 8). Можем лесно да изчислим евклидово разстояние по права линия между двете координатни точки. Тази крайна дължина обаче би била непроходима, тъй като извисяващи се стоманени сгради заемат района, очертан от всеки градски блок. По-правилното решение е ограничено до път през перпендикулярните тротоари, които образуват решетката на града. Такъв маршрут изисква да изминем три пресечки между Пето авеню и Трето авеню и след това 23 пресечки между 34-та улица и 57-ма улица, за общо разстояние от 26 пресечки. Средната дължина на блока в Манхатън е 0,17 мили, така че можем да оценим разстоянието пеша като 4,42 мили. Нека изчислим това пешеходно разстояние директно с помощта на обобщена функция manhattan_distance.

Списък 23. Изчисляване на разстоянието Манхатън

def manhattan_distance(point_a, point_b):
     num_blocks = np.sum(np.absolute(point_a - point_b))
     return 0.17 * num_blocks
  
 x = np.array([34, 5])
 y = np.array([57, 8])
 distance = manhattan_distance(x, y) (1)
  
 print(f"Manhattan distance is {distance} miles")

❶ Можем също да генерираме този изход, като импортираме cityblock от scipy.spatial.distance и след това изпълним .17 * cityblock(x, y).

Manhattan distance is 4.42 miles

Сега да предположим, че искаме да групираме повече от две местоположения в Манхатън. Ще приемем, че всеки клъстер притежава точка, която е в рамките на една миля пеша от три други групирани точки. Това предположение ни позволява да приложим DBSCAN клъстериране, като използваме класа DBSCAN на scikit-learn. Зададохме eps на 1 и min_samples на 3 по време на инициализацията на DBSCAN. Освен това предаваме metric= manhattan_distance в метода за инициализация. Параметърът metric разменя евклидовото разстояние с нашия персонализиран показател за разстояние, така че разстоянието за групиране правилно отразява ограниченията, базирани на мрежата в рамките на града. Следните кодови клъстери Manhattan координират и ги изобразяват върху мрежа заедно с техните клъстерни обозначения (фигура 14).

Списък 24. Групиране с помощта на разстояние Манхатън

points = [[35, 5], [33, 6], [37, 4], [40, 7], [45, 5]]
 clusters = DBSCAN(eps=1, min_samples=3,
                   metric=manhattan_distance).fit_predict(points) ❶
  
 for i, cluster in enumerate(clusters):
     point = points[i]
     if cluster == -1:
         print(f"Point at index {i} is an outlier")
         plt.scatter(point[0], point[1], marker='x', color='k') ❷
     else:
         print(f"Point at index {i} is in cluster {cluster}")
         plt.scatter(point[0], point[1], color='g')
  
 plt.grid(True, which='both', alpha=0.5) ❸
 plt.minorticks_on()
  
  
 plt.show()

❶ Функцията manhattan_distance се предава на DBSCAN чрез метричния параметър.

❷ Отклоненията се изчертават с помощта на маркери с форма на x.

❸ Методът на мрежата показва правоъгълната мрежа, в която изчисляваме разстоянието до Манхатън.

Point at index 0 is in cluster 0
 Point at index 1 is in cluster 0
 Point at index 2 is in cluster 0
 Point at index 3 is an outlier
 Point at index 4 is an outlier

Първите три местоположения попадат в рамките на един клъстер, а останалите точки са извънредни. Можехме ли да открием този клъстер с помощта на алгоритъма на K-средните? Може би. В края на краищата нашите координати на блока в Манхатън могат да бъдат усреднени, което ги прави съвместими с внедряване на K-средства. Какво ще стане, ако разменим разстоянието Манхатън с различен показател, където средните координати не се получават толкова лесно? Нека дефинираме нелинейна метрика на разстоянието със следните свойства: две точки са на 0 единици една от друга, ако всичките им елементи са отрицателни, на 2 единици една от друга, ако всичките им елементи са неотрицателни, и на 10 единици в противен случай. Като имаме предвид тази нелепа мярка за разстояние, можем ли да изчислим средната стойност на произволни две точки? Не можем и K-средствата не могат да бъдат приложени. Слабост на алгоритъма е, че зависи от наличието на средно разстояние. За разлика от K-средните, алгоритъмът DBSCAN не изисква нашата функция за разстояние да бъде линейно делима. По този начин можем лесно да стартираме DBSCAN клъстериране, използвайки нашия нелеп показател за разстояние.

Списък 25. Групиране с помощта на абсурдна мярка за разстояние

def ridiculous_measure(point_a, point_b):
     is_negative_a = np.array(point_a) < 0 ❶
     is_negative_b = np.array(point_b) < 0
     if is_negative_a.all() and is_negative_b.all(): ❷
         return 0
     elif is_negative_a.any() or is_negative_b.any(): ❸
         return 10
     else: ❹
         return 2
  
 points = [[-1, -1], [-10, -10], [-1000, -13435], [3,5], [5,-7]]
  
 clusters = DBSCAN(eps=.1, min_samples=2,
                   metric=ridiculous_measure).fit_predict(points)
  
 for i, cluster in enumerate(clusters):
     point = points[i]
     if cluster == -1:
         print(f"{point} is an outlier")
     else:
         print(f"{point} falls in cluster {cluster}")

❶ Връща булев масив, където is_negative_a[i] е True, ако point_a[i] ‹ 0

❷ Всички елементи на point_a и point_b са отрицателни.

❸ Съществува отрицателен елемент, но не всички елементи са отрицателни.

❹ Всички елементи са неотрицателни.

[-1, -1] falls in cluster 0
 [-10, -10] falls in cluster 0
 [-1000, -13435] falls in cluster 0
 [3, 5] is an outlier
 [5, -7] is an outlier

Изпълнението на DBSCAN с нашата метрика ridiculous_measure води до групиране на отрицателни координати в една група. Всички други координати се третират като извънредни стойности. Тези резултати не са концептуално практични, но гъвкавостта по отношение на избора на показатели се оценява високо. Ние не сме ограничени в избора си на метрика! Можем, например, да зададем показателя за изчисляване на разстоянието на преминаване въз основа на кривината на Земята. Такъв показател би бил особено полезен за групиране на географски местоположения.

DBSCAN методи за групиране

dbscan_model = DBSCAN(eps=epsilon, min_samples=min_points) — Създава DBSCAN модел за групиране по плътност. Плътна точка се дефинира като имаща поне min_points съседи на разстояние от epsilon. Съседите се считат за част от същия клъстер като точката.
clusters = dbscan_model.fit_predict(data) — Изпълнява DBSCAN върху въведени данни с помощта на инициализиран DBSCAN обект. Масивът clusters съдържа идентификатори на клъстери. ИД на клъстера data[i] е равен на clusters[i]. Неклъстерираните външни точки се присвояват с идентификатор -1.
clusters = DBSCAN(eps=epsilon, min_samples=min_points).fit_predict(data) — Изпълнява DBSCAN в един ред код и връща получените клъстери.
dbscan_model = DBSCAN(eps=epsilon, min_samples=min_points, metric=metric_function) — Създава DBSCAN модел, където показателят за разстояние се определя от персонализирана метрична функция. Не е необходимо показателят за разстояние metric_function да е Евклидов.

DBSCAN има определени недостатъци. Алгоритъмът е предназначен да открива клъстери с подобни разпределения на плътност на точките. Данните от реалния свят обаче варират по плътност. Например магазините за пицария в Манхатън са разпределени по-гъсто от магазините за пицария в Ориндж Каунти, Калифорния. По този начин може да имаме проблеми с избора на параметри за плътност, които ще ни позволят да групираме магазини и на двете места. Това подчертава друго ограничение на алгоритъма: DBSCAN изисква значими стойности за параметрите eps и min_samples. По-специално, вариращите eps входове ще повлияят значително на качеството на клъстерирането. За съжаление, няма една надеждна процедура за оценка на подходящия eps. Въпреки че някои евристики се споменават понякога в литературата, ползата от тях е минимална. През повечето време трябва да разчитаме на нашето интуитивно разбиране на проблема, за да присвоим практически входни данни на двата DBSCAN параметъра. Например, ако трябва да групираме набор от географски местоположения, нашите eps и min_samples стойности ще зависят от това дали местоположенията са разпръснати по цялото земно кълбо или дали са ограничени до един географски регион. Във всеки случай нашето разбиране за плътност и разстояние ще варира. Най-общо казано, ако групираме произволни градове, разпръснати по цялата Земя, можем да настроим параметрите min_samples и eps да се равняват съответно на три града и 250 мили. Това предполага, че всеки клъстер притежава град в рамките на 250 мили от поне три други клъстерирани града. За по-регионално разпределение на местоположението е необходима по-ниска стойност eps.

Анализиране на клъстери с помощта на Pandas

Досега отделяхме нашите входни данни и клъстерни изходи. Например, в нашия анализ на скалния пръстен, входните данни са в списъка rocks, а изходът за клъстериране е в масив rock_clusters. Проследяването както на координатите, така и на клъстерите изисква да картографираме индекси между входния списък и изходния масив. По този начин, ако искаме да извлечем всички скали в клъстер 0, трябва да получим всички случаи на rocks[i], където rock_clusters[i] == 0. Този анализ на индекса е сложен. Можем по-интуитивно да анализираме клъстерирани скали, като комбинираме координатите и клъстерите заедно в една таблица Pandas.

Следният код създава таблица Pandas с три колони: X, Y и Cluster. Всеки iти ред в таблицата съдържа x-координатата, y-координатата и групата на скалата, намираща се на rocks[i].

Списък 26. Съхраняване на групирани координати в таблица

import pandas as pd
 x_coordinates, y_coordinates = np.array(rocks).T
 df = pd.DataFrame({'X': x_coordinates, 'Y': y_coordinates,
                    'Cluster': rock_clusters})

Нашата маса Pandas ни позволява лесен достъп до скалите във всеки клъстер. Нека начертаем скалите, които попадат в клъстер 0, като използваме техниките, описани в раздел 8 (фигура 15).

Списък 27. Изчертаване на единичен клъстер с помощта на Pandas

df_cluster = df[df.Cluster == 0] ❶
 plt.scatter(df_cluster.X, df_cluster.Y) ❷
 plt.show()

❶ Изберете само онези редове, където колоната Клъстер е равна на 0

❷ Изчертава колоните X и Y на избраните редове. Обърнете внимание, че изпълняваме и точковата диаграма, като изпълняваме df_cluster.plot.scatter(x=’X’, y=’Y’).

Pandas ни позволява да получим таблица, съдържаща елементи от всеки отделен клъстер. Като алтернатива може да искаме да получим множество таблици, където всяка таблица се съпоставя с ИД на клъстер. В Pandas това става чрез извикване на df.groupby('Cluster'). Методът groupby ще създаде три таблици: по една за всеки клъстер. Той ще върне итерируем над съпоставянията между идентификатори на клъстери и таблици. Нека използваме метода groupby, за да повторим нашите три клъстера. Впоследствие ще начертаем скалите в клъстер 1 и клъстер 2, но не и скалите в клъстер 0 (фигура 16).

Извикването на df.groupby('Cluster') връща повече от просто итерируем: той връща DataFrameGroupBy обект, който предоставя допълнителни методи за филтриране и анализ на клъстери.

Списък 28. Итериране на клъстери с помощта на Pandas

for cluster_id, df_cluster in df.groupby('Cluster'): ❶
     if cluster_id == 0:
         print(f"Skipping over cluster {cluster_id}")
         continue
  
     print(f"Plotting cluster {cluster_id}")
     plt.scatter(df_cluster.X, df_cluster.Y)
  
  
 plt.show()
 Skipping over cluster 0
 Plotting cluster 1
 Plotting cluster 2

❶ Всеки елемент от итерируемия, върнат от df.groupby(‘Cluster’) е кортеж. Първият елемент на кортежа е идентификаторът на клъстера, получен от df.Cluster. Вторият елемент е таблица, съставена от всички редове, където df.Cluster е равен на ID на клъстера.

Методът Pandas groupby ни позволява да изследваме итеративно различни клъстери. Това може да се окаже полезно в нашия анализ на казус 3.

Резюме

Алгоритъмът K-средства клъстери въведе данни чрез търсене на K центроиди. Тези центроиди представляват средните координати на откритите групи данни. K-средните се инициализират чрез избиране на K произволни центроиди. След това всяка точка от данни се групира въз основа на най-близкия си център и центроидите се преизчисляват итеративно, докато се сближат на стабилни места.
K-средствата гарантирано се сближават с решение. Това решение обаче може да не е оптимално.
K-средните изискват евклидови разстояния за разграничаване между точките. Алгоритъмът не е предназначен за групиране на неевклидови координати.
След като изпълним клъстерирането на K-означава, можем да изчислим инерцията на резултата. Инерцията е равна на сумата от квадратите на разстоянията между всяка точка от данни и нейния най-близък център.
Начертаването на инерцията в диапазон от стойности на K генерира коленна графика. Компонентът на коляното в диаграмата с форма на коляно трябва да сочи надолу към разумна стойност на K. Използвайки диаграмата на лакътя, можем евристично да изберем значим K вход за K-средни стойности.
Алгоритъмът DBSCAN групира данни въз основа на плътност. Плътността се определя с помощта на параметрите epsilon и min_points. Ако дадена точка се намира на epsilon разстояние от min_point съседи, тогава тази точка е в плътен регион на пространството. Всеки съсед на точка в плътна област от пространството също се групира в това пространство. DBSCAN итеративно разширява границите на плътна област от пространството, докато бъде открит пълен клъстер.
Точките в неплътни региони не се групират от алгоритъма DBSCAN. Те се третират като извънредни стойности.
DBSCAN е изгоден алгоритъм за групиране на данни, съставени от извити и плътни форми.
DBSCAN може да групира, използвайки произволни, неевклидови разстояния.
Няма надеждна евристика за избор на подходящи параметри epsilon и min_points. Въпреки това, ако искаме да групираме глобални градове, можем да зададем двата параметъра съответно на 250 мили и три града.
Съхраняването на клъстерирани данни в таблица на Pandas ни позволява интуитивно да обикаляме клъстери с метода groupby.

Това е всичко за тази серия. Ако искате да научите повече за книгата, вижте я в платформата LiveBook на Manning тук.

Групиране на данни в групи, част 3

СТАТИЯ