Table of Contents

Variacije na Jaccarda

4-5. februar 2022

Salton

Jaccard 1

Obstaja nekaj posplošitev Jaccardove podobnosti J(x,y) na (nenegativne) realne vektorje. Morda najbolj znana je (Ružička)

J1(x,y) = ∑i min(xi,yi) / ∑i max(xi,yi)

Hitro lahko preverimo, da za dvojiška vektorja x in y velja ∑i min(xi,yi) = | X ∩ Y | in ∑i max(xi,yi) = | X ∪ Y |. Torej je res J1(x,y) = J(x,y).

Žal se ta mera ne obnese dobro za vektorje, ki vsebujejo negativne člene.

Jaccard 2

Druga posplošitev Jaccardove podobnosti je

J2(x,y) = x∙y / ( (x-y)2 + x∙y ) za x ≠ 0 in y ≠ 0; in J2(0,0) = 1.

kjer je x∙y skalarni produkt. Zopet za dvojiška vektorja x in y velja x∙y = | X ∩ Y | ter (x-y)2 + x∙y = | X ∪ Y |.

Za splošne realne vektorje veljajo lastnosti:

Za nenegativna vektorja x in y je J2(x,y) ≥ 0. Toda v primeru y = -x dobimo

Če pogledamo nekoliko splošneje, dobimo J2(x,a.x) = a / ( (1-a)2 + a )

> f <- function(x) x/((1-x)**2+x)
> curve(f(x), from=-3, to=3, xlab="x", ylab="y")


Zgleda, da je -1/3 najmanjša možna vrednost mere J2. Izkaže se, da to drži. Dokaz je kratek: veljavno neenakost 0 ≤ (x+y)2 preoblikujemo v -3 x∙y ≤ (x-y)2 + x∙y kar pomeni

Mero J2 spravimo na interval [1,0] s pretvorbo

J3(x,y) = (3.J2(x,y) + 1)/4

Preizkusimo jo!

> D <- matrix(1,nrow=44,ncol=44)
> colnames(D) <- rownames(D) <- nam
> Jv <- function(x,y) x %*% y / ((x-y) %*% (x-y) + x %*% y)
> for(i in 1:43) for(j in (i+1):44) D[i,j] <- D[j,i] <- (3*Jv(W[,i],W[,j])+1)/4
> disD <- as.dist(1-D,diag=FALSE,upper=FALSE)
> t <-hclust(disD,method="complete")
> plot(t,hang=-1,cex=1,main="vector Jaccard / Complete")

Za februarske podatke dobimo drevo združevanja vjaccardcom.pdf, ki določa isto razvrstitev kot drevo dobljeno za Saltonovo kosinusno podobnost saltonwcom.pdf.

Zakaj je temu tako mi še ni jasno. Monotona povezanost? Če izraz za J3 (poenostavimo) izrazimo s skalarnimi produkti, dobimo

J3(x,y) = ( (x+y)/2 )2/( (x-y)2 + x∙y )

Manhattan-Jaccard

Poskusil sem še različnost, ki na Manhattanski razdalji uporabi Jaccardovo normalizacijo

MJ(x,y) = ∑i wi . |xi - yi| / | X ∪ Y |

> MJ <- function(x,y) sum(w*abs(x-y))/sum(abs(x)+abs(y)>0)
> for(i in 1:43) for(j in (i+1):44) D[i,j] <- D[j,i] <- MJ(P[,i],P[,j])
> diag(D) <- 0
> disD <- as.dist(D,diag=FALSE,upper=FALSE)
> tm <-hclust(disD,method="complete")
> plot(tm,hang=-1,cex=1,main="Manhattan-Jaccard / weighted / Complete")
> S <- 1/(1 + D)
> matrix2net(S,Net="MatJac.net")

Dobimo razvrstitev manjaccwcom.pdf, ki je precej podobna Saltonovi in posplošeni Jaccardovi J3. Tu je še ustrezno omrežje po dveh najbližjih sosedov manjac.pdf.

Povezave