Ejercicio 3.1.3: Supongamos que tenemos un conjunto universal U de n elementos, y elegimos dos subconjuntos S y T al azar, cada una con m de n elementos.
¿Cuál es el valor esperado de la similitud de Jaccard de S y T?
Estoy leyendo el libro http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
Respuestas
¿Demasiados anuncios?
Nathaniel Reinhart
Puntos
658
A la respuesta anterior, se supone que un elemento en $T$ puede ser repetido varias veces en $S$ ($S$$T$ no son conjuntos, pero multisets); de otra manera, la probabilidad de no ser $m/n$ uniformemente.
Espero que la respuesta debe ser más a lo largo de las líneas siguientes:-
Deje que el número de elementos comunes entre los $S$$T$$k$. Entonces, como se ha mencionado por ack_inc en el comentario a su respuesta, la similitud de Jaccard $Sim(S,T)=k/(2m-k)$.
Ahora, $Pr(Sim(S,T)=k/(2m-k))$ $\dfrac{{m\choose {k}} {n-m\choose m-k}}{n\choose m}$ ya que hay $n$ total de elementos, de los cuales, $m$ $S$ $k$ son comunes. Por lo que el número de maneras en que podemos elegir $m$ elementos para $T$ está dado por ${m \choose k}$ (la elección de la $k$ elementos comunes de $S$) veces ${n-m\choose m-k}$ (elegir restante $m-k$ elementos).
Por lo tanto, $E(Sim(S,T))=\sum_{k=0}^{m} \dfrac{k}{2m-k} \dfrac{{m\choose {k}} {n-m\choose m-k}}{n\choose m}$.
Sin embargo, la simplificación de la expresión anterior está más allá de mis limitados conocimientos de combinatoria de las identidades. Si alguien puede hacerlo, la amabilidad de la actualización de la respuesta.
SofaKng
Puntos
194
Voy a postear una solución alternativa.
La similitud de Jaccard de dos conjuntos de $S$ $T$ se define como la fracción de los elementos de estos dos conjuntos tienen en común, es decir,$\text{sim}(S,T)=|S\cap T|/|S\cup T|$. Supongamos que elegimos $m$-elemento subconjuntos $S$ $T$ uniformemente al azar de una $n$-elemento del conjunto. Lo que se espera de similitud de Jaccard de estos dos juegos? Supongamos que el $|S\cap T|=k$ algunos $0\le k\le m$. Observe que en el primer set, $S$, $\binom{n}{m}$ opciones, mientras que para $T$ tenemos $\binom{m}{k}\binom{n-m}{m-k}$ elecciones, porque $k$ elementos deben ser de $S$ $m-k$ elementos no deben ser de $S$. Esto nos da $$\Pr[|S\cap T|=k]=\frac{\binom{m}{k}\binom{n-m}{m-k}}{\binom{n}{m}},$$ meaning that $$\text{E}[\text{sim}(S,T)]=\sum_{k=0}^m\frac{\binom{m}{k}\binom{n-m}{m-k}}{\binom{n}{m}}\frac{k}{2m-k}.$$ Even though $\texto{E}[|S\cap T|/|S\taza de T|]\neq\text{E}[|S\cap T|]/\text{E}[|S\taza de T|a]=m/(2n-m)$, esta expresión parece dar una buena aproximación.
Gracias a Mitja Trampus por señalar una solución alternativa, con $$\Pr[|S\cap T|=k]=\binom{m}{k}\frac{\binom{m}{k}}{\binom{n}{k}}\frac{\binom{n-m}{m-k}}{\binom{n}{m}},$$ dando la siguiente expresión: $$\text{E}[\text{sim}(S,T)]=\sum_{k=0}^m\binom{m}{k}\frac{\binom{m}{k}}{\binom{n}{k}}\frac{\binom{n-m}{m-k}}{\binom{n}{m}}\frac{k}{2m-k}.$$
(Las expresiones anteriores son, por supuesto, equivalentes).
EDIT: en Cuanto a la simplificación, tal vez la aplicación de la siguiente identidad (de Aigner del libro, página 13) podría funcionar: $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}.$$
Cada elemento de T tiene una probabilidad de $\frac{m}{n}$ de ser también en S. Es el número esperado de artículos comunes a S & T $\frac{m^2}{n}$.
Exp. $\text{Jaccard Similarity} = \dfrac{\text{No. of common items}}{\text{Size of T} + \text{Size of S} - \text{Number of common items}} = \dfrac{m}{2n - m}$ (después de simplificación).
