2
$\begingroup$

I have a set of sets and I want to assign a measure of variability to it. If all member sets are the same (e.g., S0={{a,b},{a,b},{a,b}}), the measure shall be 0. If some members are different (e.g., S1={{a,b},{a,b},{a,b,c}} and S2={{a,b},{a,b,c,d,e},{a,b,f,g,h}}), it shall be strictly greater than 0, and the magnitude shall be bigger for the sets which are intuitively more diverse (S1 is less diverse than S2).

The measure does not have to be normalized, so I am thinking of some sort of entropy, but cannot figure out how to calculate it.

$\endgroup$
9
  • 1
    $\begingroup$ Variability of what quantity? $\endgroup$
    – whuber
    Aug 19, 2016 at 18:58
  • $\begingroup$ Variability of set composition. I want to know to what extent the set is homogeneous. $\endgroup$
    – DYZ
    Aug 19, 2016 at 19:01
  • $\begingroup$ Before you can assess the variability of something, you have to be able to measure it. How are you measuring "composition"? $\endgroup$
    – whuber
    Aug 19, 2016 at 19:51
  • $\begingroup$ But that's exactly my question: How to measure the variability of a set of sets? $\endgroup$
    – DYZ
    Aug 19, 2016 at 19:52
  • $\begingroup$ There is a preceding question that must be answered first: there is no "variability" in your data until you have a number. Exactly what number are you attaching to each member set? $\endgroup$
    – whuber
    Aug 19, 2016 at 19:53

1 Answer 1

1
$\begingroup$

In this answer I assume you really mean "set" rather than "multiset" (as we might see more typically in statistics).

One measure of set-similarity is Jaccard similarity $J(A,B) = {{|A \cap B|}\over{|A \cup B|}}$ (also called the Jaccard index). That is, the number in both sets divided by the number in either set.

Correspondingly, the Jaccard dissimilarity between two sets is $1-J(A,B)$.

We could generalize the Jaccard similarity to more than two sets readily enough.

If $A$ is a collection of sets $A_1, A_2,...,A_n$, then $J(A) = {{|\bigcap_i A_i|}\over{|\bigcup_i A_i|}}$ and then perhaps define a measure of dissimilarity (taking on some sense of "variability") as its complement, $1-J(A)$.

(However numerous other similarity measures exist, as whuber points out; it depends what you want to measure)


You mention using entropy (by which I assume you mean something like cross-entropy).

To work with cross entropy you'd need to assign some sort of probabilities to the elements.

If the sets were finite, and one were to define the probabilities uniformly that might work, but

  • cross entropy is also not symmetric; you'd presumably want a symmetric measure (you could perhaps add the two cross entropies $d(p,q)=H(p,q)+H(q,p)$).

  • then you'd need to generalize to more than two sets, possibly by summing all the pairwise $d$s. However

  • I don't think this would be especially satisfactory as it stands since it's not 0 when the sets are the same.


Related to it but better still might be the symmetrized Kullback-Liebler divergence. Again you would need to generalize to multiple sets.

Hopefully these give you some ideas. You should probably look around some of the other similarity and dissimilarity indices that already exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.