Apakah ketimpangan segitiga terpenuhi untuk jarak berbasis korelasi ini?

13

Untuk pengelompokan hierarkis saya sering melihat dua "metrik" berikut (mereka tidak berbicara) untuk mengukur jarak antara dua variabel acak $X$ dan $Y$ : $\newcommand{\Cor}{\mathrm{Cor}}$

\begin{aligned} d_{1} (X, Y) & = 1 - | C o r (X, Y) |, \\ d_{2} (X, Y) & = 1 - (C o r (X, Y))^{2} \end{aligned}

$\begin{align} d_1(X,Y) &= 1-|\Cor(X,Y)|, \\ d_2(X,Y) &= 1-(\Cor(X,Y))^2 \end{align}$ Apakah juga satu memenuhi ketidaksetaraan segitiga? Jika demikian, bagaimana saya harus membuktikannya selain hanya melakukan perhitungan bruteforce? Jika itu bukan metrik, apa contoh penghitung sederhana?

correlation clustering distance metric Linda
sumber

Anda mungkin tertarik untuk meninjau makalah ini: arxiv.org/pdf/1208.3145.pdf .

Chris

5

The ketidaksamaan segitiga pada Anda akan menghasilkan: $d_1$ $\newcommand{\Cov}{\mathrm{Cov}}$ $\newcommand{\Cor}{\mathrm{Cor}}$ $\newcommand{\Var}{\mathrm{Var}}$

\begin{aligned} d_{1} (X, Z) & \leq d_{1} (X, Y) + d_{1} (Y, Z) \\ 1 - | C o r (X, Z) | & \leq 1 - | C o r (X, Y) | + 1 - | C o r (Y, Z) | \\ ⟹ | C o r (X, Y) | + | C o r (Y, Z) | & \leq 1 + | C o r (X, Z) | \end{aligned}

$\begin{align*} d_1(X,Z) &\leq d_1(X,Y) + d_1(Y,Z) \\ 1 - |\Cor(X,Z)| &\leq 1 - |\Cor(X,Y)| + 1 - |\Cor(Y,Z)| \\ \implies |\Cor(X,Y)| + |\Cor(Y,Z)| &\leq 1 + |\Cor(X,Z)| \end{align*}$

Tampaknya ini merupakan ketidaksetaraan yang mudah untuk dikalahkan. Kita dapat membuat sisi kanan sekecil mungkin (tepatnya satu) dengan membuat dan independen. Lalu bisakah kita menemukan yang melebihi sisi kiri? $X$ $Z$ $Y$

Jika dan dan memiliki varian yang identik, maka dan demikian pula dengan , jadi sisi kiri jauh di atas satu dan ketidaksetaraan dilanggar. Contoh pelanggaran ini di R, di mana dan adalah komponen normal multivarian: $Y=X+Z$ $X$ $Z$ $\Cor(X,Y) = \frac{\sqrt{2}}{2} \approx 0.707$ $\Cor(Y,Z)$ $X$ $Z$

library(MASS)
set.seed(123)
d1 <- function(a,b) {1 - abs(cor(a,b))}

Sigma    <- matrix(c(1,0,0,1), nrow=2) # covariance matrix of X and Z
matrixXZ <- mvrnorm(n=1e3, mu=c(0,0), Sigma=Sigma, empirical=TRUE)
X <- matrixXZ[,1] # mean 0, variance 1
Z <- matrixXZ[,2] # mean 0, variance 1
cor(X,Z) # nearly zero
Y <- X + Z

d1(X,Y) 
# 0.2928932
d1(Y,Z)
# 0.2928932
d1(X,Z)
# 1
d1(X,Z) <= d1(X,Y) + d1(Y,Z)
# FALSE

Meskipun perhatikan konstruksi ini tidak berfungsi dengan Anda : $d_2$

d2 <- function(a,b) {1 - cor(a,b)^2}
d2(X,Y) 
# 0.5
d2(Y,Z)
# 0.5
d2(X,Z)
# 1
d2(X,Z) <= d2(X,Y) + d2(Y,Z)
# TRUE

Daripada meluncurkan serangan teoretis pada , pada tahap ini saya hanya merasa lebih mudah untuk bermain-main dengan matriks kovarians dalam R sampai sebuah contoh bagus muncul. Mengizinkan , dan memberi: $d_2$ Sigma $\Var(X)=2$ $\Var(Z)=1$ $\Cov(X,Z)=1$

V a r (Y) = V a r (X + Y) = V a r (X) + V a r (Z) + 2 C o v (X, Z) = 2 + 1 + 2 = 5

$\Var(Y)=\Var(X+Y)=\Var(X)+\Var(Z)+2\Cov(X,Z)=2+1+2=5$

Kami juga dapat menyelidiki kovarian:

C o v (X, Y) = C o v (X, X + Z) = C o v (X, X) + C o v (X, Z) = 2 + 1 = 3

$\Cov(X,Y)=\Cov(X,X+Z)=\Cov(X,X)+\Cov(X,Z)=2+1=3$

C o v (Y, Z) = C o v (X + Z, Z) = C o v (X, Z) + C o v (Z, Z) = 1 + 1 = 2

$\Cov(Y,Z)=\Cov(X+Z,Z)=\Cov(X,Z)+\Cov(Z,Z)=1+1=2$

Korelasi kuadrat adalah:

C o r (X, Z)^{2} = \frac{C o v (X, Z)^{2}}{V a r (X) V a r (Z)} = \frac{1^{2}}{2 \times 1} = 0.5

$\Cor(X,Z)^2 = \frac{\Cov(X,Z)^2}{\Var(X)\Var(Z)}=\frac{1^2}{2\times1}=0.5$

C o r (X, Y)^{2} = \frac{C o v (X, Y)^{2}}{V a r (X) V a r (Y)} = \frac{3^{2}}{2 \times 5} = 0.9

$\Cor(X,Y)^2 = \frac{\Cov(X,Y)^2}{\Var(X)\Var(Y)}=\frac{3^2}{2\times5}=0.9$

C o r (Y, Z)^{2} = \frac{C o v (Y, Z)^{2}}{V a r (Y) V a r (Z)} = \frac{2^{2}}{5 \times 1} = 0.8

$\Cor(Y,Z)^2 = \frac{\Cov(Y,Z)^2}{\Var(Y)\Var(Z)}=\frac{2^2}{5\times1}=0.8$

Kemudian sedangkan dan sehingga ketimpangan segitiga dilanggar oleh margin yang substansial. $d_2(X,Z)=0.5$ $d_2(X,Y)=0.1$ $d_2(Y,Z)=0.2$

Sigma    <- matrix(c(2,1,1,1), nrow=2) # covariance matrix of X and Z
matrixXZ <- mvrnorm(n=1e3, mu=c(0,0), Sigma=Sigma, empirical=TRUE)
X <- matrixXZ[,1] # mean 0, variance 2
Z <- matrixXZ[,2] # mean 0, variance 1
cor(X,Z) # 0.707
Y  <- X + Z
d2 <- function(a,b) {1 - cor(a,b)^2}
d2(X,Y) 
# 0.1
d2(Y,Z)
# 0.2
d2(X,Z)
# 0.5
d2(X,Z) <= d2(X,Y) + d2(Y,Z)
# FALSE

Gegat
sumber

5

Mari kita memiliki tiga vektor (bisa variabel atau individu) , , dan . Dan kami distandarisasi masing-masing untuk z-skor (rata-rata = 0, varians = 1). $X$ $Y$ $Z$

$\newcommand{\Cor}{\mathrm{Cor}}$

Kemudian menurut teorema cosinus ("hukum cosinus") kuadrat jarak euclidean antara dua vektor standar (katakanlah, X dan Y) adalah , di mana , persamaan cosinus, adalah Pearson karena z-standardisasi vektor. Kami dapat dengan aman menghilangkan pengganda konstan dari pertimbangan kami. $d_{XY}^2 = 2(n-1)(1-\cos_{XY})$ $\cos_{XY}$ $r_{XY}$ $2(n-1)$

Jadi, muncul bahwa jarak yang dinyatakan dalam pertanyaan sebagaiakan menjadi jarak euclide kuadrat jika rumusnya tidak mengabaikan tanda koefisien korelasi. $d_1(X,Y)=1-|\Cor(X,Y)|$

Jika matriksS terjadi gramian (semidefinit positif) kemudian akar kuadrat dari jarak "d1" adalah jarak euclidean, yang tentu saja adalah metrik. Dengan matriks tidak besaritu sering merupakan kasus atau dekat kasus ketika jarak tidak jauh dari konvergen yang baik di ruang euclidean. Karena metrik adalah kelas yang lebih luas daripada euclidean, matriks jarak "sqrt (d1)" yang diberikan mungkin berharap akan sering muncul metrik. $|r|$ $|r|$

Adapun "d1" per se, yang "seperti" jarak euclide kuadrat , sudah pasti non-metrik. Bahkan jarak euclidean kuadrat sejati bukanlah metrik: kadang-kadang melanggar prinsip segitiga ketimpangan. [Dalam analisis kluster, jarak euclidean kuadrat cukup sering digunakan; Namun, sebagian besar kasus tersebut menyiratkan sebenarnya membangun analisis pada jarak nonsquared, yang kuadrat menjadi input yang mudah untuk perhitungan.] Untuk melihatnya (tentang kuadrat euclidean ), mari kita gambar tiga vektor kita. $d$

masukkan deskripsi gambar di sini

Vektor adalah satuan panjang (karena terstandarisasi). Cosinus dari sudut ( , , ) masing- adalah , , . Sudut-sudut ini menyebarkan jarak euclidean yang sesuai antara vektor: , , . Untuk kesederhanaan, ketiga vektor semuanya berada pada bidang yang sama (dan sudut antara dan adalah jumlah dari dua vektor lainnya, ). Ini adalah posisi di mana pelanggaran ketimpangan segitiga oleh jarak kuadrat paling menonjol. $\alpha$ $\beta$ $\alpha+\beta$ $r_{XY}$ $r_{XZ}$ $r_{YZ}$ $d_{XY}$ $d_{XZ}$ $d_{YZ}$ $X$ $Z$ $\alpha+\beta$

Karena, seperti yang dapat Anda lihat dengan mata, area kotak hijau unggul jumlah dari dua kotak merah: . $d_{YZ}^2 > d_{XY}^2 + d_{XZ}^2$

Karena itu mengenai

$d_1(X,Y)=1-|\Cor(X,Y)|$

jarak kita bisa mengatakan itu bukan metrik. Karena bahkan ketika semua s awalnya positif jaraknya adalah euclidean yang itu sendiri bukan metrik. $r$ $d^2$

Bagaimana dengan jarak kedua?

$d_2(X,Y)=1-(\Cor(X,Y))^2$

Karena korelasi dalam kasus vektor standar adalah , adalah . (Memang, adalah regresi linier, kuantitas yang merupakan kuadrat korelasi variabel dependen dengan sesuatu yang ortogonal dengan prediktornya.) Dalam hal ini gambar sinus vektor, dan buatlah kuadratnya (karena kita berbicara tentang jarak yang ): $r$ $\cos$ $1-r^2$ $\sin^2$ $1-r^2$ SSerror/SStotal $\sin^2$

masukkan deskripsi gambar di sini

Meskipun secara visual tidak terlalu jelas, kotak hijau lagi lebih besar dari jumlah area merah . $\sin_{YZ}^2$ $\sin_{XY}^2 + \sin_{XZ}^2$

Itu bisa dibuktikan. Di pesawat, . Segi kedua sisi karena kami tertarik pada . $\sin(\alpha+\beta) = \sin\alpha \cos\beta + \cos\alpha \sin\beta$ $\sin^2$

\begin{aligned} \sin^{2} (α + β) & = \sin^{2} α (1 - \sin^{2} β) + (1 - \sin^{2} α) \sin^{2} β + 2 \sin α \cos β \cos α \sin β \\ = \sin^{2} α + \sin^{2} β - 2 [\sin^{2} α \sin^{2} β] + 2 [\sin α \cos α \sin β \cos β] \end{aligned}

$\begin{align} \sin^2(\alpha+\beta) &= \sin^2\alpha (1-\sin^2\beta) + (1-\sin^2\alpha) \sin^2\beta + 2 \sin\alpha \cos\beta \cos\alpha \sin\beta \\ &= \sin^2\alpha + \sin^2\beta -2 [\sin^2\alpha \sin^2\beta] +2 [\sin\alpha \cos\alpha \sin\beta \cos\beta] \end{align}$

Dalam ungkapan terakhir, dua istilah penting ditampilkan dalam tanda kurung. Jika yang kedua dari keduanya (atau bisa) lebih besar dari yang pertama maka , dan jarak "d2" melanggar ketimpangan segitiga. Dan demikian pada gambar kami di mana sekitar 40 derajat dan sekitar 30 derajat (istilah 1 adalah dan istilah 2 adalah ). "D2" bukan metrik. $\sin^2(\alpha+\beta) > \sin^2\alpha + \sin^2\beta$ $\alpha$ $\beta$ .1033.2132

Akar kuadrat dari jarak "d2" - ukuran ketidaksamaan sinus - adalah metrik (saya percaya). Anda dapat bermain dengan berbagai sudut dan di lingkaran saya untuk memastikan. Apakah "d2" akan menunjukkan metrik dalam pengaturan non-collinear (yaitu tiga vektor tidak pada pesawat) juga - Saya tidak bisa mengatakan pada saat ini, meskipun saya ragu-ragu mengira itu akan terjadi. $\alpha$ $\beta$

ttnphns
sumber

3

Lihat juga pracetak ini yang saya tulis: http://arxiv.org/abs/1208.3145 . Saya masih perlu waktu dan mengirimkannya dengan benar. Abstrak:

Kami menyelidiki dua kelas transformasi kesamaan cosinus dan korelasi Pearson dan Spearman menjadi jarak metrik, memanfaatkan alat sederhana fungsi pelestarian metrik. Kelas pertama menempatkan objek anti-berkorelasi secara jauh terpisah. Transformasi yang sebelumnya diketahui termasuk dalam kelas ini. Kelas kedua menyusun objek yang berkorelasi dan anti-berkorelasi. Contoh dari transformasi yang menghasilkan jarak metrik adalah fungsi sinus ketika diterapkan pada data terpusat.

Hasilnya untuk pertanyaan Anda adalah bahwa d1 , d2 memang bukan metrik dan bahwa akar kuadrat dari d2 sebenarnya adalah metrik yang tepat.

micans
sumber

2

Tidak.

Contoh kontra paling sederhana:

untuk jaraknya tidak ditentukan sama sekali, apa pun Anda . $X=(0,0)$ $Y$

Setiap seri konstan memiliki standar deviasi , dan dengan demikian menyebabkan pembagian dengan nol dalam definisi ... $\sigma=0$ $Cor$

Paling-paling itu adalah metrik pada subset ruang data, tidak termasuk seri konstan.

Memiliki QUIT - Anony-Mousse
sumber

Poin bagus! Saya harus menyebutkan ini di pra-cetak yang disebutkan di tempat lain.

micans

Apakah ketimpangan segitiga terpenuhi untuk jarak berbasis korelasi ini?

Jawaban: