Bagaimana cara menggunakan variabel biner dan kontinu bersama dalam clustering?

27

Saya perlu menggunakan variabel biner (nilai 0 & 1) dalam k-means. Tetapi k-means hanya bekerja dengan variabel kontinu. Saya tahu beberapa orang masih menggunakan variabel-variabel biner ini dalam k-means mengabaikan fakta bahwa k-means hanya dirancang untuk variabel kontinu. Bagi saya ini tidak bisa diterima.

Pertanyaan:

  1. Jadi apa cara yang benar secara statistik / matematis untuk menggunakan variabel biner dalam k-means / hierarchical clustering?
  2. Bagaimana cara mengimplementasikan solusi di SAS / R?
GeorgeOfTheRF
sumber
1
Saya ingin tahu tentang sumber informasi Anda bahwa "K means hanya dirancang untuk variabel kontinu." Apakah Anda dapat mengutip referensi?
whuber
2
jmp.com/support/help/K-Means_Clustering.shtml "K-Means clustering hanya mendukung kolom numerik. K-Means clustering mengabaikan tipe model (nominal dan ordinal), dan memperlakukan semua kolom numerik sebagai kolom kontinu." Saya baru saja googled dan mendapatkan ini. Intinya adalah mean didefinisikan untuk variabel kontinu bukan untuk biner, jadi k berarti tidak dapat menggunakan variabel biner.
GeorgeOfTheRF
1
Itu dapat menggunakannya, dengan memperlakukannya sebagai berkelanjutan; tetapi menafsirkan hasilnya akan sulit, karena pusat-pusat cluster tidak akan memiliki nilai biner lagi; dan IMHO semuanya jelas jika hasilnya terlalu berarti - mengapa meminimalkan varians dari variabel biner masuk akal? Sebagai gantinya, pertimbangkan misal penambangan item freuqent pada variabel biner jika mereka sesuai dengan ada / tidaknya pola di data Anda.
Anony-Mousse
Apakah ada hal lain yang Anda butuhkan, di luar jawaban di bawah ini? Ini sudah ada sejak lama, & sangat dilihat & dipilih, tetapi tidak jelas bahwa pertanyaan Anda telah diselesaikan untuk kepuasan Anda, & juga tidak ada indikasi apa yang Anda mungkin masih hilang.
gung - Reinstate Monica

Jawaban:

31

Anda benar bahwa k-means clustering tidak boleh dilakukan dengan data tipe campuran. Karena k-means pada dasarnya adalah algoritma pencarian sederhana untuk menemukan partisi yang meminimalkan jarak Euclidean kuadrat-dalam-kluster antara observasi berkerumun dan cluster centroid, itu hanya boleh digunakan dengan data di mana jarak Euclidean kuadrat akan bermakna.

sayasaya

Pada titik ini, Anda dapat menggunakan metode pengelompokan apa pun yang dapat beroperasi melalui matriks jarak alih-alih membutuhkan matriks data asli. (Perhatikan bahwa k-means membutuhkan yang terakhir.) Pilihan yang paling populer adalah mempartisi sekitar medoids (PAM, yang pada dasarnya sama dengan k-means, tetapi menggunakan observasi paling sentral daripada centroid), berbagai pendekatan pengelompokan hierarkis (mis. , median, hubungan tunggal, dan hubungan lengkap; dengan pengelompokan hierarkis Anda akan perlu memutuskan di mana ' memotong pohon ' untuk mendapatkan penugasan kluster akhir), dan DBSCAN yang memungkinkan bentuk klaster yang jauh lebih fleksibel.

Berikut ini adalah Rdemo sederhana (nb, sebenarnya ada 3 cluster, tetapi sebagian besar data tampak seperti 2 cluster sesuai):

library(cluster)  # we'll use these packages
library(fpc)

  # here we're generating 45 data in 3 clusters:
set.seed(3296)    # this makes the example exactly reproducible
n      = 15
cont   = c(rnorm(n, mean=0, sd=1),
           rnorm(n, mean=1, sd=1),
           rnorm(n, mean=2, sd=1) )
bin    = c(rbinom(n, size=1, prob=.2),
           rbinom(n, size=1, prob=.5),
           rbinom(n, size=1, prob=.8) )
ord    = c(rbinom(n, size=5, prob=.2),
           rbinom(n, size=5, prob=.5),
           rbinom(n, size=5, prob=.8) )
data   = data.frame(cont=cont, bin=bin, ord=factor(ord, ordered=TRUE))
  # this returns the distance matrix with Gower's distance:  
g.dist = daisy(data, metric="gower", type=list(symm=2))

Kita dapat mulai dengan mencari berbagai kluster dengan PAM:

  # we can start by searching over different numbers of clusters with PAM:
pc = pamk(g.dist, krange=1:5, criterion="asw")
pc[2:3]
# $nc
# [1] 2                 # 2 clusters maximize the average silhouette width
# 
# $crit
# [1] 0.0000000 0.6227580 0.5593053 0.5011497 0.4294626
pc = pc$pamobject;  pc  # this is the optimal PAM clustering
# Medoids:
#      ID       
# [1,] "29" "29"
# [2,] "33" "33"
# Clustering vector:
#  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
#  1  1  1  1  1  2  1  1  1  1  1  2  1  2  1  2  2  1  1  1  2  1  2  1  2  2 
# 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 
#  1  2  1  2  2  1  2  2  2  2  1  2  1  2  2  2  2  2  2 
# Objective function:
#     build      swap 
# 0.1500934 0.1461762 
# 
# Available components:
# [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 
# [6] "clusinfo"   "silinfo"    "diss"       "call" 

Hasil-hasil tersebut dapat dibandingkan dengan hasil pengelompokan hierarkis:

hc.m = hclust(g.dist, method="median")
hc.s = hclust(g.dist, method="single")
hc.c = hclust(g.dist, method="complete")
windows(height=3.5, width=9)
  layout(matrix(1:3, nrow=1))
  plot(hc.m)
  plot(hc.s)
  plot(hc.c)

masukkan deskripsi gambar di sini

Metode median menyarankan 2 (mungkin 3) cluster, yang hanya mendukung 2, tetapi metode lengkap bisa menyarankan 2, 3 atau 4 ke mata saya.

Akhirnya, kita bisa mencoba DBSCAN. Ini membutuhkan menentukan dua parameter: eps, 'jarak jangkauan' (seberapa dekat dua pengamatan harus dihubungkan bersama-sama) dan minPts (jumlah minimum poin yang perlu dihubungkan satu sama lain sebelum Anda bersedia menyebutnya sebagai 'gugus'). Aturan praktis untuk minPts adalah menggunakan satu lebih dari jumlah dimensi (dalam kasus kami 3 + 1 = 4), tetapi memiliki angka yang terlalu kecil tidak disarankan. Nilai default untuk dbscanadalah 5; kami akan tetap dengan itu. Salah satu cara untuk memikirkan jarak jangkauan adalah dengan melihat berapa persen jarak yang kurang dari nilai yang diberikan. Kita dapat melakukannya dengan memeriksa distribusi jarak:

windows()
  layout(matrix(1:2, nrow=1))
  plot(density(na.omit(g.dist[upper.tri(g.dist)])), main="kernel density")
  plot(ecdf(g.dist[upper.tri(g.dist)]), main="ECDF")

masukkan deskripsi gambar di sini

Jarak itu sendiri tampaknya mengelompok ke dalam kelompok 'dekat' dan 'lebih jauh' yang terlihat secara visual. Nilai 0,3 tampaknya paling bersih membedakan antara dua kelompok jarak. Untuk mengeksplorasi sensitivitas output terhadap berbagai pilihan eps, kita dapat mencoba .2 dan .4 juga:

dbc3 = dbscan(g.dist, eps=.3, MinPts=5, method="dist");  dbc3
# dbscan Pts=45 MinPts=5 eps=0.3
#        1  2
# seed  22 23
# total 22 23
dbc2 = dbscan(g.dist, eps=.2, MinPts=5, method="dist");  dbc2
# dbscan Pts=45 MinPts=5 eps=0.2
#         1  2
# border  2  1
# seed   20 22
# total  22 23
dbc4 = dbscan(g.dist, eps=.4, MinPts=5, method="dist");  dbc4
# dbscan Pts=45 MinPts=5 eps=0.4
#        1
# seed  45
# total 45

Menggunakan eps=.3memang memberikan solusi yang sangat bersih, yang (setidaknya secara kualitatif) setuju dengan apa yang kami lihat dari metode lain di atas.

Karena tidak ada cluster 1-ness yang bermakna , kita harus berhati-hati mencoba mencocokkan pengamatan mana yang disebut 'cluster 1' dari cluster yang berbeda. Sebaliknya, kita dapat membentuk tabel dan jika sebagian besar pengamatan yang disebut 'cluster 1' dalam satu fit disebut 'cluster 2' di yang lain, kita akan melihat bahwa hasilnya masih serupa secara substantif. Dalam kasus kami, pengelompokan yang berbeda sebagian besar sangat stabil dan menempatkan pengamatan yang sama di kelompok yang sama setiap kali; hanya pengelompokan hierarki hierarki lengkap yang berbeda:

  # comparing the clusterings
table(cutree(hc.m, k=2), cutree(hc.s, k=2))
#    1  2
# 1 22  0
# 2  0 23
table(cutree(hc.m, k=2), pc$clustering)
#    1  2
# 1 22  0
# 2  0 23
table(pc$clustering, dbc3$cluster)
#    1  2
# 1 22  0
# 2  0 23
table(cutree(hc.m, k=2), cutree(hc.c, k=2))
#    1  2
# 1 14  8
# 2  7 16

Tentu saja, tidak ada jaminan bahwa analisis cluster apa pun akan memulihkan cluster laten yang sebenarnya dalam data Anda. Tidak adanya label kluster yang sebenarnya (yang akan tersedia dalam, katakanlah, situasi regresi logistik) berarti bahwa sejumlah besar informasi tidak tersedia. Bahkan dengan dataset yang sangat besar, cluster mungkin tidak cukup terpisah untuk dapat dipulihkan dengan sempurna. Dalam kasus kami, karena kami tahu keanggotaan cluster yang sebenarnya, kami dapat membandingkannya dengan output untuk melihat seberapa baik itu. Seperti yang saya sebutkan di atas, sebenarnya ada 3 cluster laten, tetapi data memberikan tampilan 2 cluster sebagai gantinya:

pc$clustering[1:15]    # these were actually cluster 1 in the data generating process
# 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 
# 1  1  1  1  1  2  1  1  1  1  1  2  1  2  1 
pc$clustering[16:30]   # these were actually cluster 2 in the data generating process
# 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
#  2  2  1  1  1  2  1  2  1  2  2  1  2  1  2 
pc$clustering[31:45]   # these were actually cluster 3 in the data generating process
# 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 
#  2  1  2  2  2  2  1  2  1  2  2  2  2  2  2 
gung - Reinstate Monica
sumber
di hierarchical clustering merencanakan Anda sebutkan median method suggests 2 (possibly 3) clusters, the single only supports 2, but the complete method could suggest 2, 3 or 4.. bagaimana Anda sampai pada ini? menggunakan ketinggian 0,3?
lukeg
1
@ Lukuk, ketinggian gabungan pada dendrogram mewakili seberapa jauh Anda harus pergi untuk menggabungkan 2 cluster. Anda mencari di mana jarak menjadi lebih jauh untuk melanjutkan aglomerasi. Mungkin membantu untuk membaca utas yang membahas ini di sini & / atau di sini .
gung - Reinstate Monica
2

Lihatlah makalah ini oleh Finch, http://www.jds-online.com/files/JDS-192.pdf . Ini menjelaskan mengapa menerapkan metode kontinu untuk data biner dapat mengelompokkan data secara tidak akurat, dan yang lebih penting apa saja pilihan dalam fungsi jarak yang sesuai. Itu tidak menjawab bagaimana mengelompokkan dengan k-means, melainkan bagaimana mengelompokkan data biner dengan benar menggunakan metrik non-Euclidean dan metode hierarkis seperti Ward.

Chris
sumber