Кластеризація з пакетом ClusterR, частина 2

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

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

Найбільш відомі приклади алгоритмів кластеризації кластеризація на основі зв'язності (ієрархічна кластеризація), кластеризація на основі центрів (метод k-середніх, метод k-медоидов), кластеризація на основі розподілів (GMM — Gaussian mixture models — Гаусова суміш розподілів) і кластеризація на основі щільності (DBSCAN — Density-based spatial clustering of applications with noise — просторова кластеризація додатків з шумом на основі щільності, OPTICS — Ordering points to identify the clustering structure — впорядкування точок для визначення структури кластеризації, і ін).

першої частини: гаусового суміш розподілів (GMM), метод k-середніх, метод k-середніх у міні-групах.

Метод k-медоидов

Алгоритм k-медоидов (Л. Кауфман, П. Руссо, 1987) — алгоритм кластеризації, що має спільне з алгоритмом k-середніх і алгоритмом зміщення медоидов. Алогритмы k-середніх і k-медоидов — розділяють, і обидва намагаються мінімізувати відстань між точками імовірно з одного кластера і точкою, призначеної центром кластера. На відміну від алгоритму k-середніх, метод k-медоидов вибирає точки з набору даних в якості центрів (медоиды або еталони) і працює з довільній метрикою відстаней між точками. Корисний інструмент для визначення k — ширина контуру. Метод k-медоидов більш стійкий до шуму і аномальних значень, ніж k-середніх, оскільки він мінімізує суму попарних відхилень, а не суму квадратів эвклидовых відстаней. Медоид можна визначити як об'єкт кластера, чиє середнє відхилення від всіх інших об'єктів у кластері мінімально, тобто це найбільш близька до центру кластера точка.

Найбільш поширена реалізація кластеризації k-медоидов — алгоритм поділу навколо медоидов (РАМ — Partitioning Around Medoids). РАМ має дві фази: «побудувати» (BUILD) і «переставити» (SWAP). На фазі BUILD алгоритм шукає хороший набір вихідних медоидов, а на фазі SWAP здійснюються всі можливі переміщення між BUILD-медоидами і значеннями, до тих пір, поки цільова функція не перестане убувати (Кластеризація в об'єктно-орієнтованому середовищі, А. Штруйф, М. Хуберт, П. Руссо, 1997).

У пакеті ClusterR функції Cluster_Medoids та Clara_Medoids відповідають алгоритмам PAM (partitioning around medoids) і CLARA (clustering large applications — кластеризація великих додатків).

У наступному прикладі коду використовую дані mushroom для ілюстрації, як працює метод k-медоидов з метрикою відстані, відмінною від эвклидовой. Дані mushroom складаються з 23 категорійних атрибутів (включаючи клас) і 8124 значень. У документації до пакету більше інформації про цих даних.

Cluster_Medoids
В якості вхідних даних функція Cluster_Medoids може також приймати матрицю відхилень (в доповнення до матриці з даними). У випадку даних mushroom, де всі змінні категоріальні (з двома або більше унікальними значеннями), має сенс використовувати відстань gower. Відстань gower застосовує різні функції для різних показників в залежності від типу (числовий, упорядкований і невпорядкований список). Ця метрика відхилення реалізована в ряді пакетів R, серед інших в пакеті cluster (функція daisy), і пакет FD (функція gowdis). Я скористаюся функцією gowdis з пакету FD, оскільки вона також дозволяє задати певні користувачем ваги в якості окремого чинника.

data(гриб)
X = mushroom[, -1]
y = as.numeric(mushroom[, 1]) # конвертувати мітки числа
gwd = FD::gowdis(X) # порахувати відстань 'gower' для факторних змінних
gwd_mat = as.matrix(gwd) # конвертувати відстані в матрицю
cm = Cluster_Medoids(gwd_mat, clusters = 2, swap_phase = TRUE, verbose = F)

adjusted_rand_index avg_silhouette_width
0.5733587 0.2545221
Як раніше згадувалося, функція gowdis пакету FD дозволяє користувачеві задавати різні ваги для кожної окремої змінної. Параметр weights можна налаштовувати, наприклад, за допомогою випадкового пошуку, для досягнення кращих результатів кластеризації. Наприклад, з допомогою таких ваг кожної окремої змінної можна поліпшити і adjusted-rand-index (зовнішня валідація), і average silhouette width (середня ширина контуру, внутрішня валідація).
predictors weights
cap_shape 4.626
cap_surface 38.323
cap_color 55.899
bruises 34.028
odor 169.608
gill_attachment 6.643
gill_spacing 42.08
gill_size 57.366
gill_color 37.938
stalk_shape 33.081
stalk_root 65.105
stalk_surface_above_ring 18.718
stalk_surface_below_ring 76.165
stalk_color_above_ring 27.596
stalk_color_below_ring 26.238
veil_type 0.0
veil_color 1.507
ring_number 37.314
ring_type 32.685
spore_print_color 127.87
population 64.019
habitat 44.519
weights = c(4.626, 38.323, 55.899, 34.028, 169.608, 6.643, 42.08, 57.366, 37.938, 
33.081, 65.105, 18.718, 76.165, 27.596, 26.238, 0.0, 1.507, 37.314, 
32.685, 127.87, 64.019, 44.519)
gwd_w = FD::gowdis(X, w = weights) # відстань 'gower' з застосуванням ваг
d_mat_w = as.matrix(gwd_w) # перетворення в матрицю відстаней
cm_w = Cluster_Medoids(gwd_mat_w, clusters = 2, swap_phase = TRUE, verbose = F)

adjusted_rand_index avg_silhouette_width
0.6197672 0.3000048
Clara_Medoids
CLARA (CLustering LARge Applications — кластеризація великих додатків) — очевидний вибір для кластеризації великих наборів даних. Замість пошуку медоидов для всього набору даних — розрахунок матриці неподобия — також нездійсненне завдання — CLARA бере невелику вибірку і застосовує до неї алгоритм РАМ (Partitioning Around Medoids — поділ навколо медоидов), щоб створити оптимальний набір медоидов для цієї вибірки. Якість отриманих медоидов визначається середнім неподобием між кожним об'єктом у наборі даних і медоидом його кластера.

Функція Clara_Medoids в пакеті ClusterR використовує аналогічну логіку, застосовуючи функцію Cluster_Medoids до кожній вибірці. Clara_Medoids приймає ще два параметри: samples sample_size. Перший визначає кількість вибірок, які потрібно сформувати з вихідного набору даних, другий — частку даних в кожній ітерації формування вибірок (дробове число між 0.0 та 1.0). Варто згадати, що функція Clara_Medoids не приймає на вхід матрицю неподобия, на відміну від функції Cluster_Medoids.

Я застосую функцію Clara_Medoids до раніше використаного набору даних mushroom, взявши відстань Хеммінга як метрику неподобия, і порівняю час обчислення і результат з результатом функції Cluster_Medoids. Відстань Хеммінга підходить для даних mushroom, оскільки воно застосовне до дискретним змінним і визначається, як кількість атрибутів, які приймають різні значення для двох порівнюваних примірників («Алгоритми інтелектуального аналізу даних: пояснення з R», Пауел Чікош, 2015, стор 318).

cl_X = X # скопіювати вихідні дані 

# функція Clara_Medoids приймає тільки числові атрибути
# тому спочатку привести до числовим

for (i in 1:ncol(cl_X)) { cl_X [i] = as.numeric(cl_X [i]) }
start = Sys.time()
cl_f = Clara_Medoids(cl_X, clusters = 2, distance_metric = 'hamming', samples = 5, 
sample_size = 0.2, swap_phase = TRUE, verbose = F, threads = 1)
end = Sys.time()
t = end - start
cat('time to complete :', t, attributes(t)$units, '\n')

# час обчислення : 3.104652 сек

adjusted_rand_index avg_silhouette_width
0.5944456 0.2678507
start = Sys.time()
cl_e = Cluster_Medoids(cl_X, clusters = 2, distance_metric = 'hamming', swap_phase = TRUE, 
verbose = F, threads = 1)
end = Sys.time()
t = end - start
cat('time to complete :', t, attributes(t)$units, '\n')

# час обчислення : 14.93423 сек

adjusted_rand_index avg_silhouette_width
0.5733587 0.2545221
З використанням відстані Хеммінга Clara_Medoids, Cluster_Medoids повертають приблизно однаковий результат (порівняно з результатами для відстані gower), але при цьому функція Clara_Medoids працює більш ніж в чотири рази швидше, ніж Cluster_Medoids, для цього набору даних.

З результатами останніх двох фрагментів коду можна побудувати на графіку ширину контуру за допомогою функції Silhouette_Dissimilarity_Plot. Тут варто згадати, що неподобие і ширина контуру функції Clara_Medoids — на найкращій вибірці, а не на всьому наборі даних, як для функції Cluster_Medoids.

# Контурний графік для об'єкта "Clara_Medoids"

Silhouette_Dissimilarity_Plot(cl_f, silhouette = TRUE)


# Контурний графік для об'єкта "Cluster_Medoids"

Silhouette_Dissimilarity_Plot(cl_e, silhouette = TRUE)


Посилання для функцій k-медоидов

Реалізація функцій k-медоидов (Cluster_Medoids Clara_Medoids) зайняла у мене досить багато часу, оскільки спочатку я думав, що початкові медоиды ініціалізуються так само, як і центри в алгоритм k-середніх. Оскільки у мене не було доступу до книги Кауфмана і Руссо, дуже допоміг пакет cluster з докладною документацією. Він включає обидва алгоритму РАМ (Partitioning Around Medoids — поділ навколо медоидов), і CLARA (CLustering LARge Applications — кластеризація великих додатків), при бажанні можна порівняти результати.

У наступному фрагменті коду порівняю функцію pam пакету cluster Cluster_Medoids пакету ClusterR і отримані медоиды, ґрунтуючись на попередньому прикладі квантування.

#====================================
# функція pam пакету cluster
#====================================

start_pm = Sys.time()
set.seed(1)
pm_vq = cluster::pam(im2, k = 5, metric = 'неевклідової', do.swap = TRUE)
end_pm = Sys.time()

t_pm = end_pm - start_pm
cat('time to complete :', t_pm, attributes(t_pm)$units, '\n')

# час обчислення : 12.05006 сек

pm_vq$medoids

# [,1] [,2] [,3]
# [1,] 1.0000000 1.0000000 1.0000000
# [2,] 0.6325856 0.6210824 0.5758536
# [3,] 0.4480000 0.4467451 0.4191373
# [4,] 0.2884769 0.2884769 0.2806337
# [5,] 0.1058824 0.1058824 0.1058824

#====================================
# функція Cluster_Medoids пакету ClusterR з використанням 6 потоків (паралелізація доступна з OpenMP)
#====================================

start_vq = Sys.time()
set.seed(1)
cl_vq = Cluster_Medoids(im2, clusters = 5, distance_metric = 'неевклідової', 
swap_phase = TRUE, verbose = F, threads = 6)
end_vq = Sys.time()

t_vq = end_vq - start_vq
cat('time to complete :', t_vq, attributes(t_vq)$units, '\n')

# час обчислення : 3.333658 сек

cl_vq$medoids

# [,1] [,2] [,3]
# [1,] 0.2884769 0.2884769 0.2806337
# [2,] 0.6325856 0.6210824 0.5758536
# [3,] 0.4480000 0.4467451 0.4191373
# [4,] 0.1058824 0.1058824 0.1058824
# [5,] 1.0000000 1.0000000 1.0000000

#====================================
# функція Cluster_Medoids пакету ClusterR в один потік
#====================================

start_vq_single = Sys.time()
set.seed(1)
cl_vq_single = Cluster_Medoids(im2, clusters = 5, distance_metric = 'неевклідової', 
swap_phase = TRUE, verbose = F, threads = 1)
end_vq_single = Sys.time()

t_vq_single = end_vq_single - start_vq_single
cat('time to complete :', t_vq_single, attributes(t_vq_single)$units, '\n')

# час обчислення : 8.693385 сек

cl_vq_single$medoids

# [,1] [,2] [,3]
# [1,] 0.2863456 0.2854044 0.2775613
# [2,] 1.0000000 1.0000000 1.0000000
# [3,] 0.6325856 0.6210824 0.5758536
# [4,] 0.4480000 0.4467451 0.4191373
# [5,] 0.1057339 0.1057339 0.1057339

Для цього набору даних (5625 рядків колонки 3) функція Cluster_Medoids повертає ті ж медоиды майже в чотири рази швидше, ніж функція pam, якщо доступний OpenMP (6 потоків).

Актуальна версія пакету ClusterR доступна в моєму Github репозиторії, а для баг-репортов, будь ласка, використовуйте посилання.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.