Melakukan PCA dengan hanya matriks jarak

12

Saya ingin mengelompokkan dataset besar yang saya hanya memiliki jarak berpasangan. Saya menerapkan algoritma k-medoid, tetapi butuh waktu terlalu lama untuk dijalankan sehingga saya ingin memulai dengan mengurangi dimensi masalah saya dengan menerapkan PCA. Namun, satu-satunya cara saya tahu untuk melakukan metode ini adalah dengan menggunakan matriks kovarians yang tidak saya miliki dalam situasi saya.

Apakah ada cara untuk menerapkan PCA dengan mengetahui jarak berpasangan saja?

pca dimensionality-reduction multidimensional-scaling pohon besar
sumber
1
Jadi, Anda memiliki matriks persegi besar jarak antara titik-titik yang ingin Anda klaster. (BTW, berapa jarak? Euclidean?) Apa yang membuat Anda berpikir bahwa jumlah dimensi yang direntang titik-titik ini, dan bukan jumlah titik itu sendiri (kardinalitas), yang menghambat pengelompokan?
ttnphns
1
Jumlah poin tidak "sangat besar" (beberapa ribu). Jarak yang saya gunakan adalah korelasi pearson antara titik-titik ini
bigTree
2
Tetapi pertanyaan saya adalah: apakah Anda benar-benar ingin mengurangi dimensionalitas (dan jika ya, mengapa?) Atau kardinalitas (jumlah poin)? Karena pertanyaan Anda tidak jelas .
ttnphns
1
@ttnphns: Ya ampun, tentu saja saya salah mengetik komentar saya sebelumnya. Untuk menghapus kebingungan mungkin, sekarang saya akan menghapus komentar itu dan mengulangi apa yang saya katakan di sini dengan kata-kata yang benar: "Mengurangi kardinalitas dalam hal ini berarti membuat Anda matriks jarak yang lebih kecil (penurunan N ) Mengurangi berarti dimensi sehingga menurunkan. rank, tanpa mengubah N . PCA sebesar yang terakhir dan tidak benar-benar membantu dengan mantan tujuan". N×NNN
Amuba mengatakan Reinstate Monica
1
Saya pikir cara termudah bagi Anda adalah menggunakan (a) metode pengelompokan atau (b) penerapannya atau (c) komputer yang kuat (cukup RAM) yang akan mengambil dan mengklasifikasikan 6000 objek (saya tidak tahu mengapa Anda program medoid menemukan kesulitan. 6000 besar, tetapi tidak terlalu besar.). Beberapa metode (seperti K-means) memerlukan objek X fitur data. Anda bisa membuat data seperti itu dari matriks jarak objek melalui metrik MDS (jika, sekali lagi, program komputer / MDS Anda akan mengizinkan 6000 objek).
ttnphns

Jawaban:

8

Pembaruan: Saya sepenuhnya menghapus jawaban asli saya, karena didasarkan pada kebingungan antara jarak Euclidean dan produk skalar. Ini adalah versi baru dari jawaban saya. Permintaan maaf.

Jika dengan jarak berpasangan yang Anda maksud jarak Euclidean, maka ya, ada cara untuk melakukan PCA dan untuk menemukan komponen utama. Saya menjelaskan algoritma dalam jawaban saya untuk pertanyaan berikut: Apa perbedaan antara analisis komponen utama dan penskalaan multidimensi?

Secara singkat, matriks jarak Euclidean dapat dikonversi menjadi matriks Gram terpusat, yang dapat langsung digunakan untuk melakukan PCA melalui eigendekomposisi. Prosedur ini dikenal sebagai penskalaan multidimensi [klasik] (klasik) .

Jika jarak berpasangan Anda bukan Euclidean, maka Anda tidak dapat melakukan PCA, tetapi masih dapat melakukan MDS, yang tidak akan setara dengan PCA lagi. Namun, dalam situasi ini MDS cenderung lebih baik untuk tujuan Anda.

amuba kata Reinstate Monica
sumber
Jarak yang saya gunakan adalah korelasi (korelasi Pearson) dan karenanya bukan jarak Euclidian. Apakah itu akan bekerja dengan cara yang sama?
bigTree
1
@ BigTree: Jika ini bukan jarak Euclidean, tidak ada cara Anda bisa menjalankan PCA. Namun, Anda dapat menggunakan penskalaan multi-dimensi yang merupakan teknik reduksi dimensionalitas yang menggunakan matriks jarak berpasangan secara tepat (bisa berupa jarak berapapun). Catatan lain: dengan asumsi tertentu tentang korelasi data-poin asli (yang tidak Anda miliki) dapat diubah menjadi jarak Euclidean. Asumsinya adalah: (1) memiliki rata-rata nol, (2) memiliki tetap, misalnya satuan, panjang. Apakah ini benar untuk data Anda?
Amuba mengatakan Reinstate Monica
Tidak ada yang benar atau data saya, tetapi saya akan mencoba MDS terima kasih
bigTree
1
tidak bisakah kamu menggunakan kernel PCA? Saya membayangkan bahwa hanya perlu produk dot berpasangan, tapi saya tidak tahu banyak tentang masalah ini, jadi saya tidak tahu apakah itu masuk akal
rep_ho
4

PCA dengan matriks jarak ada, dan itu disebut penskalaan multi-dimensi (MDS). Anda dapat mempelajari lebih lanjut di wikipedia atau di buku ini .

Anda dapat melakukannya Rdengan fungsi mds cmdscale. Untuk sampel x, Anda dapat memeriksanya prcomp(x)dan cmdscale(dist(x))memberikan hasil yang sama (di mana prcompPCA dan disthanya menghitung jarak euclidian antara elemen x)

Pop
sumber
3

Ini terlihat seperti masalah yang bisa diterapkan pada pengelompokan spektral. Karena Anda memiliki matriks jarak berpasangan, Anda dapat menentukan grafik yang sepenuhnya terhubung di mana setiap node memiliki koneksi N, sesuai dengan jaraknya dari setiap node lain dalam grafik. Dari ini, Anda dapat menghitung grafik Laplacian (jika ini terdengar menakutkan, jangan khawatir - ini adalah perhitungan yang mudah) dan kemudian ambil vektor eigen dari yang terkecilnilai eigen (di sinilah berbeda dari PCA). Jika Anda mengambil 3 vektor eigen, misalnya, Anda akan memiliki matriks Nx3. Dalam ruang ini, titik-titik harus (mudah-mudahan) dipisahkan dengan baik karena beberapa teori grafik rapi yang menunjukkan bahwa ini adalah potongan optimal untuk memaksimalkan aliran (atau jarak, dalam hal ini) antara cluster. Dari sana, Anda bisa menggunakan k-means atau algoritma serupa untuk mengelompokkan dalam 3-ruang. Saya sarankan memeriksa langkah-langkah luar biasa ini untuk wawasan lebih lanjut:

http://arxiv.org/abs/0711.0189

Christopher Krapu
sumber
0

Jarak berpasangan juga membentuk matriks persegi seperti matriks co-variance. PCA hanya SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) yang diterapkan pada matriks co-variance. Anda harus tetap dapat melakukan pengurangan dimensi menggunakan SVD pada data Anda. Saya tidak begitu yakin bagaimana menafsirkan output Anda, tetapi itu pasti sesuatu untuk dicoba. Anda bisa menggunakan metode pengelompokan seperti k-means atau pengelompokan hierarkis. Lihat juga teknik reduksi dimensi lain seperti penskalaan multidimensi. Apa yang Anda coba untuk keluar dari kelompok Anda?

Andrew Cassidy
sumber
Jawaban Andrew Cassidy sebenarnya valid. Jika ukuran jarak Anda adalah korelasi pearson, Anda hanyalah faktor standardisasi "terlalu jauh" dari benar-benar memiliki matriks kovarians. Jadi, menerapkan SVD pada dasarnya sama dengan melakukan PCA.
Matthew Anthony