Variacije na Jaccarda

Variacije na Jaccarda

4-5. februar 2022

Jaccard 1

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

J₁(x,y) = ∑_i min(x_i,y_i) / ∑_i max(x_i,y_i)

Hitro lahko preverimo, da za dvojiška vektorja x in y velja ∑_i min(x_i,y_i) = | X ∩ Y | in ∑_i max(x_i,y_i) = | X ∪ Y |. Torej je res J₁(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

J₂(x,y) = x∙y / ( (x-y)² + x∙y ) za x ≠ 0 in y ≠ 0; in J₂(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)² + x∙y = | X ∪ Y |.

Za splošne realne vektorje veljajo lastnosti:

J₂(x,y) = J₂(y,x)
J₂(x,y) ≤ 1
J₂(x,y) = 1 ⇔ x = y
J₂(a.x,a.y) = J₂(x,y) za a ∈ ℝ.

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

J₂(x,-x) = -1/3

Če pogledamo nekoliko splošneje, dobimo J₂(x,a.x) = a / ( (1-a)² + 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 J₂. Izkaže se, da to drži. Dokaz je kratek: veljavno neenakost 0 ≤ (x+y)² preoblikujemo v -3 x∙y ≤ (x-y)² + x∙y kar pomeni

J₂(x,y) ≥ -1/3 ; enačaj velja ntk. x = -y .

Mero J₂ spravimo na interval [1,0] s pretvorbo

J₃(x,y) = (3.J₂(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 J₃ (poenostavimo) izrazimo s skalarnimi produkti, dobimo

J₃(x,y) = ( (x+y)/2 )²/( (x-y)² + x∙y )

Manhattan-Jaccard

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

MJ(x,y) = ∑_i w_i . |x_i - y_i| / | 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 J₃. Tu je še ustrezno omrežje po dveh najbližjih sosedov manjac.pdf.

Variacije na Jaccarda

Jaccard 1

Jaccard 2

Manhattan-Jaccard

Povezave