7
$\begingroup$

I am currently analyzing large data sets with various characteristics (such as city). I wanted to find a measure which would essentially say how much or how little of a variance there was across the data. This would be much more useful than simply getting a count of the number of distinct elements.

For example, consider the following data:

City
----
Moscow
Moscow
Paris
London
London
London
NYC
NYC
NYC
NYC

I can see that there are 4 distinct cities, but that doesn't tell me how much a distribution there is. One 'formula' I came up with was taking the sum of the fractions of the total dataset for each element. In this case, it would be (2/10)^2 + (1/10)^2 + (3/10)^2 + (4/10)^2. I have no real mathematical proof for this, but just thought about it.

In this case, for example, in a set with 10 elements, if 9 were the same, and 1 was different, the number would be (9/10)^2 + (1/10)^2. However, if it were half and half, it would be (5/10)^2 + (5/10)^2.

I wanted to get an opinion on what similar formulas and areas of study there are. I really could not find anything with a few quick Google searches.

$\endgroup$
8
$\begingroup$

I think what you probably want is (Shannon's) entropy. It is calculated like this:
$$ H(x) = -\sum_{x_i} p(x_i)\log_2 p(x_i) $$ This represents a way of thinking about the amount of information in a categorical variable.

In R, we can calculate this as follows:

City = c("Moscow", "Moscow", "Paris", "London", "London", 
         "London", "NYC", "NYC", "NYC", "NYC")
table(City)
# City
# London Moscow    NYC  Paris 
#      3      2      4      1 
entropy = function(cat.vect){
  px  = table(cat.vect)/length(cat.vect)
  lpx = log(px, base=2)
  ent = -sum(px*lpx)
  return(ent)
}
entropy(City)                                             # [1] 1.846439
entropy(rep(City, 10))                                    # [1] 1.846439
entropy(c(    "Moscow",       "NYC"))                     # [1] 1
entropy(c(    "Moscow",       "NYC", "Paris", "London"))  # [1] 2
entropy(rep(  "Moscow", 100))                             # [1] 0
entropy(c(rep("Moscow",   9), "NYC"))                     # [1] 0.4689956
entropy(c(rep("Moscow",  99), "NYC"))                     # [1] 0.08079314
entropy(c(rep("Moscow",  97), "NYC", "Paris", "London"))  # [1] 0.2419407

From this, we can see that the length of the vector doesn't matter. The number of possible options ('levels' of a categorical variable) makes it increase. If there were only one possibility, the value is $0$ (as low as you can get). The value is largest, for any given number of possibilities when the probabilities are equal.

Somewhat more technically, with more possible options, it takes more information to represent the variable while minimizing error. With only one option, there is no information in your variable. Even with more options, but where almost all actual instances are a particular level, there is very little information; after all, you can just guess "Moscow" and nearly always be right.

your.metric = function(cat.vect){
  px   = table(cat.vect)/length(cat.vect)
  spx2 = sum(px^2)
  return(spx2)
}
your.metric(City)                                             # [1] 0.3
your.metric(rep(City, 10))                                    # [1] 0.3
your.metric(c(    "Moscow",       "NYC"))                     # [1] 0.5
your.metric(c(    "Moscow",       "NYC", "Paris", "London"))  # [1] 0.25
your.metric(rep(  "Moscow", 100))                             # [1] 1
your.metric(c(rep("Moscow",   9), "NYC"))                     # [1] 0.82
your.metric(c(rep("Moscow",  99), "NYC"))                     # [1] 0.9802
your.metric(c(rep("Moscow",  97), "NYC", "Paris", "London"))  # [1] 0.9412

Your suggested metric is the sum of squared probabilities. In some ways it behaves similarly (e.g., notice that it is invariant to the length of the variable), but note that it decreases as the number of levels increases or as the variable becomes more imbalanced. It moves inversely to entropy, but the units—size of the increments—differ. Your metric will be bound by $0$ and $1$, whereas entropy ranges from $0$ to infinity. Here is a plot of their relationship:

enter image description here

$\endgroup$
  • 3
    $\begingroup$ Entropy as you define it is bounded for $S$ categories by $\log_2 S$. Clearly $S$ can grow as large as one likes but in most problems of this kind it's small or moderate and entropy is thus finite. $\endgroup$ – Nick Cox Jun 30 '16 at 7:21
8
$\begingroup$

The sum of the squares of the fractions (to let your text align with your arithmetic) is indeed a much re-discovered or re-invented measure of the concentration of distributions divided into distinct categories. It is now in its second century at least, allowing a little latitude to include under the same umbrella its complement and its reciprocal: all three versions have easy interpretations and uses. There are (wild guess) perhaps twenty different names for it in common use. Let's write generically $p$ for proportion or probability, where necessarily $1 \ge p_s \ge 0$ and $\sum_{s=1}^S p_s \equiv 1$.

Your measure is $\sum_{s=1}^S p_s^2 =: R$. At least for biologists the index $s=1, \dots, S$ is mnemonic for species. Then that sum is for ecologists the Simpson index (after E.H. Simpson, 1922-2019, the person for whom Simpson's paradox is named); for economists it's the Herfindahl-Hirschman index; and so on. It has a long history in cryptography, often clouded in secrecy for decades by its use in classified problems, but most famously featuring A.M. Turing. I.J. Good (who like Simpson worked with Turing in World War II) called it the repeat rate, which motivates the symbol $R$ above; for D.J.C. MacKay it is the match probability.

Suppose we rank the proportions $p_1 \ge \dots \ge p_S$. Then at one extreme $p_1$ grows to $1$ and the other $p_s$ shrink to $0$ and then $R = 1$. Another extreme is equal probabilities $1/S$ so that $R = S (1/S^2) = 1/S$. The two limits naturally coincide for $S = 1$. Thus for $2, 10, 100$ species $R \ge 0.5, 0.1, 0.01$ respectively.

The complement $1 - R$ was one of various measures of heterogeneity used by Corrado Gini, but beware serious overloading of terms in various literatures: the terms Gini index or coefficient have been applied to several distinct measures. It features in machine learning as a measure of impurity of classifications; conversely $R$ measures purity. Ecologists usually talk of diversity: $R$ measures diversity inversely and $1 - R$ measures it directly. For geneticists $1 - R$ is the heterozygosity.

The reciprocal $1/R$ has a 'numbers equivalent' interpretation. Imagine as above any case in which $S$ species are equally common with each $p_s = 1/S$. Then $1/R = 1/\sum_{s=1}^S (1/S)^2 = S$. By extension $1/R$ measures an equivalent number of equally common categories, so that for example the squares of $1/6, 2/6, 3/6$ give $1/R \approx 2.57$ which matches an intuition that the distribution is between $2/6, 2/6, 2/6$ and $3/6,3/6, 0$ in concentration or diversity.

(The numbers equivalent for Shannon entropy $H$ is just its antilogarithm, say $2^H, \exp(H)$ or $10^H$ for bases $2, e = \exp(1)$ and $10$ respectively.)

There are various generalisations of entropy which make this measure one of a wider family; a simple one given by I.J. Good defines the menagerie $\sum_{s} p_s^a\ [\ln (1/p_s)]^b$ from which $a =2, b=0$ gives our measure; $a = 1, b=1$ is Shannon entropy; $a =0; b=0$ returns $S$, the number of species present, which is the simplest measurement of diversity possible and one with several merits.

$\endgroup$
  • $\begingroup$ Wow, there seems to be a lot of this. It isn't my field, so I'm only peripherally familiar with it, although I do recall having heard of some of these names. How is $S$ calculated? Is it always $1/R$, or only when the species are equiprobable? $\endgroup$ – gung Jun 29 '16 at 23:57
  • $\begingroup$ $S$ is just how many species are present. Sometimes you adopt a classification (e.g. males and females, so $S = 2$) so that is pre-defined for data collection, except that in this example too other schemes are possible. Sometimes it's how many species present themselves; imagine you are a botanist or ornithologist looking for tree or bird species. Naturally the term species is generic (weak biological pun); in economics that could be sectors of the economy, kinds of traded products or services, etc. In demography it could be ethnic categories, etc. $\endgroup$ – Nick Cox Jun 30 '16 at 0:03
  • $\begingroup$ So for the cities example data, $S = 4$? That doesn't seem like as good of a metric as the others. $\endgroup$ – gung Jun 30 '16 at 0:43
  • $\begingroup$ That's right in the simple example. But suppose you and I compare how many countries we've visited ever. You say 78, I say 23. That's informative. And in that example, I really can't dig up precise information on how many days I've spent in each. The ecologist who tells another ecologist that 78 and 23 bird species have been found on two islands is trading useful data. $\endgroup$ – Nick Cox Jun 30 '16 at 6:10
1
$\begingroup$

Interesting question... It really depends what you want to do with this metric - if you just want to rank a list by "most variable" a lot of things might work. The metric you made up seems reasonable. I wouldn't say you need mathematical "proof": proof of what? You could ask a question like "is this dataset likely to come from a uniform distribution?". I find some intuitive appeal in "what is the probability that two random draws from this list are equal?". You could do that in R like so:

set.seed(1)
cities <- c("Moscow", "Moscow", "NYC", "London")
# Gives .3525
prob_equal = mean(sample(rep(cities, 100)) == sample(rep(cities, 100)))
citiesTwo <- c(rep("Moscow", 100), rep("NYC", 100)) # Gave .497
citiesTwo <- c(rep("Moscow", 100), rep("NYC", 10)) # Gave .833

Where the 'mean' part gives the mean of a vector few hundred random entries like TRUE, TRUE, FALSE, TRUE, FALSE ..., which becomes the mean of 1, 1, 0, 1, 0, etc

1 minus that probability might give a better notion of "variance" though (i.e. prob two random are different, thus higher number means more diverse). Some such quantity could probably be calculated without too much effort. It's probably something like P(a random selection is moscow) * P(a second is moscow) + P(a random selection is NYC) * P(a second is NYC) + ..., so I think it's just proportion_moscow ^ 2 + proportion_nyc ^ 2, which in fact would be what you came up with!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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