====== Variacije na Jaccarda ======
4-5. februar 2022\\

[[vlado:work:2m:salton|Salton]]

===== Jaccard 1 =====

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

J<sub>1</sub>(x,y) =  ∑<sub>i</sub> min(x<sub>i</sub>,y<sub>i</sub>) / ∑<sub>i</sub> max(x<sub>i</sub>,y<sub>i</sub>)\\

Hitro lahko preverimo, da za dvojiška vektorja x in y velja ∑<sub>i</sub> min(x<sub>i</sub>,y<sub>i</sub>) = | X ∩ Y | in  ∑<sub>i</sub> max(x<sub>i</sub>,y<sub>i</sub>) = | X ∪ Y |. Torej je res J<sub>1</sub>(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<sub>2</sub>(x,y) = x∙y / ( (x-y)<sup>2</sup>  + x∙y ) za x ≠ 0 in y ≠ 0; in J<sub>2</sub>(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)<sup>2</sup>  + x∙y = | X ∪ Y |.

Za splošne realne vektorje veljajo lastnosti:

  * J<sub>2</sub>(x,y) = J<sub>2</sub>(y,x)
  * J<sub>2</sub>(x,y) ≤ 1
  * J<sub>2</sub>(x,y) = 1 ⇔ x = y
  * J<sub>2</sub>(a.x,a.y) = J<sub>2</sub>(x,y)  za a ∈ ℝ. 

Za nenegativna vektorja x in y je  J<sub>2</sub>(x,y) ≥ 0.
Toda v primeru y = -x dobimo

  * J<sub>2</sub>(x,-x) = -1/3

Če pogledamo nekoliko splošneje, dobimo J<sub>2</sub>(x,a.x) = a / ( (1-a)<sup>2</sup> + a )


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

{{vlado:work:pics:j2a.png?350}}\\

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

  * J<sub>2</sub>(x,y) ≥ -1/3 ; enačaj velja ntk. x = -y .

Mero J<sub>2</sub> spravimo na interval [1,0] s pretvorbo\\

J<sub>3</sub>(x,y) = (3.J<sub>2</sub>(x,y) + 1)/4\\

Preizkusimo jo!
<code>
> 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")
</code>

Za februarske podatke dobimo drevo združevanja {{vlado:work:pics:vjaccardcom.pdf}}, ki določa isto razvrstitev kot drevo dobljeno za Saltonovo kosinusno podobnost {{vlado:work:pics:saltonwcom.pdf}}.\\

Zakaj je temu tako mi še ni jasno. Monotona povezanost? Če izraz za J<sub>3</sub> (poenostavimo) izrazimo s skalarnimi produkti, dobimo\\

J<sub>3</sub>(x,y) = ( (x+y)/2 )<sup>2</sup>/( (x-y)<sup>2</sup>  + x∙y )  

===== Manhattan-Jaccard =====

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

MJ(x,y) = ∑<sub>i</sub> w<sub>i</sub> . |x<sub>i</sub> - y<sub>i</sub>| / | X ∪ Y |

<code>
> 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")
</code>

Dobimo razvrstitev {{vlado:work:pics:manjaccwcom.pdf}}, ki je precej podobna Saltonovi in posplošeni Jaccardovi J<sub>3</sub>. Tu je še ustrezno omrežje po dveh najbližjih sosedov {{vlado:work:pics:manjac.pdf}}.

===== Povezave =====

  * [[https://stats.stackexchange.com/questions/483903/is-jaccard-similarity-distance-suitable-for-non-binary-quantitative-data|Is Jaccard similarity distance suitable for non binary quantitative data]]
  * [[https://apps.dtic.mil/sti/pdfs/AD1026967.pdf]]
  * [[https://en.wikipedia.org/wiki/Jaccard_index|Jaccard index]]
  * [[https://hal.archives-ouvertes.fr/hal-03410273/document|On similarity]]
  * [[https://www.leydesdorff.net/cosinevspearson/cosinevspearson.pdf]]