Variance of a distribution of multi-level categorical data

Question

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.

Answer 1

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:

Answer 2

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.

Answer 3

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!