Apakah jarak harus menjadi "metrik" agar pengelompokan hierarkis valid?

9

Mari kita katakan bahwa kita mendefinisikan jarak, yang bukan metrik , antara N item.

Berdasarkan jarak ini kami kemudian menggunakan pengelompokan hierarki Agglomerative .

Bisakah kita menggunakan masing-masing algoritma yang dikenal (tautan tunggal / maksimum / rata-rata dll), untuk mendapatkan hasil yang bermakna? Atau dengan kata lain, apa masalah dengan menggunakannya jika jaraknya bukan metrik?

clustering multilevel-analysis metric hierarchical-clustering Tal Galili
sumber
Apa "item" dalam kasus Anda? (Saya bertanya apakah ini ada hubungannya dengan psikometrik karena jika ini masalahnya, saya akan merekomendasikan untuk melihat item clustering , atau Revelle, W. Hierarchical cluster analysis dan dengan struktur internal tes , MBR (1979) 14 : 57.)
chl

Jawaban:

7

Persyaratan untuk jarak tergantung pada metode pengelompokan hierarkis. Metode tunggal, lengkap, rata-rata membutuhkan jarak menjadi no-negatif dan simetris. Metode ward, centroid, median membutuhkan jarak (euclidean) (yang bahkan lebih sempit daripada metrik) jarak untuk menghasilkan hasil yang bermakna secara geometris.

(Seseorang dapat memeriksa apakah matriks jaraknya adalah euclidean dengan memusatkannya dua kali lipat [lihat jawaban saya di sini ] dan melihat nilai eigen; jika tidak ada nilai eigen negatif yang ditemukan maka jarak melakukan konvergensi dalam ruang euclidean.)

ttnphns
sumber
Terima kasih. Pertanyaan selanjutnya: apakah ketimpangan segitiga harus dimiliki untuk metode tunggal, lengkap, rata-rata? dan jika jarak tertentu (misalnya) tidak simetris, masalah apa yang ditimbulkannya pada metode ini? (Terima kasih!)
Tal Galili
1
Metode pengelompokan hierarkis klasik dapat mengambil apa pun selain matriks simetris: jarak dari A ke B = dari B ke A. Metode khusus lain ada untuk menangani asimetris (Anda dapat google). Adapun ketidaksetaraan segitiga - tidak perlu kondisi untuk metode yang Anda sebutkan. (Namun, kebijaksanaan umum menganggap "jarak" sebagai pertanda ketidaksetaraan, jadi sebaiknya pertimbangkan untuk memaksakannya jika hilang. Untuk melakukannya, tambahkan sedikit konstanta kecil pada jarak dan periksa. Dan jika Anda terus menambahkan saat mencapai maka Anda akan segera tiba pada jarak euclidean)
ttnphns
5

Tidak, jaraknya tidak harus berupa metrik. Ia dapat, misalnya, menjadi ultrametrik:

d(A,B)≤max(d(A,C),d(B,C))

Jarak ultrametrik yang diperoleh dari langkah-langkah berurutan dalam algoritma pengelompokan dapat direpresentasikan menggunakan dendrogram, yang mungkin Anda lihat dalam konteks ini.

Hong Ooi
sumber
Hong terima kasih Saya ingat bahwa metode untuk mengubah beberapa objek ke hclust menuntut bahwa dendrogram bersifat ultrametrik - saya lebih terluka jika ini ada hubungannya dengan apa yang Anda tulis. Dalam hal apa pun, terima kasih atas jawabannya.
Tal Galili