13
$\begingroup$

I have a lot of data and I want to do something which seems very simple. In this large set of data, I am interested in how much a specific element clumps together. Let's say my data is an ordered set like this: {A,C,B,D,A,Z,T,C...}. Let's say I want to know whether the A's tend to be found right next to each other, as opposed to being randomly (or more evenly) distributed throughout the set. This is the property I am calling "clumpiness".

Now, is there some simple measurement of data "clumpiness"? That is, some statistic that will tell me how far from randomly distributed the As are? And if there isn't a simple way to do this, what would the hard way be, roughly? Any pointers greatly appreciated!

$\endgroup$

3 Answers 3

15
$\begingroup$

As an example, suppose you have an ordered set in which each position has an equal probability of being any of the lowercase letters in the alphabet. In this case I will make the ordered set contain $1000$ elements.

# generate a possible sequence of letters
s <- sample(x = letters, size = 1000, replace = TRUE)

It turns out that if each of the positions of the ordered set follows a uniform distribution over the lowercase letters of the alphabet, then the distance between two occurrences of the same letter follows a geometric distribution with parameter $p=1/26$. In light of this information, let's compute the distance between consecutive occurrences of the same letter.

# find the distance between occurences of the same letters
d <- vector(mode = 'list', length = length(unique(letters)))
for(i in 1:length(unique(letters))) {
    d[[i]] <- diff(which(s == letters[i]))
}
d.flat <- unlist(x = d)

Let's look at a histogram of the distances between occurrences of the same letter and compare it to the probability mass function associated with the geometric distribution mentioned above.

hist(x = d.flat, prob = TRUE, main = 'Histogram of Distances', xlab = 'Distance',
     ylab = 'Probability')
x <- range(d.flat)
x <- x[1]:x[2]
y <- dgeom(x = x - 1, prob = 1/26)
points(x = x, y = y, pch = '.', col = 'red', cex = 2)

The red dots represent the actual probability mass function of the distance we would expect if each of the positions of the ordered set followed a uniform distribution over the letters and the bars of the histogram represent the empirical probability mass function of the distance associated with the ordered set.

enter image description here

Hopefully the image above is convincing that the geometric distribution is appropriate.

Again, if each position of the ordered set follows a uniform distribution over the letters, we would expect the distance between occurrences of the same letter to follow a geometric distribution with parameter $p=1/26$. So how similar are the expected distribution of the distances and the empirical distribution of the differences? The Bhattacharyya Distance between two discrete distributions is $0$ when the distributions are exactly the same and tends to $\infty$ as the distributions become increasingly different.

How does d.flat from above compare to the expected geometric distribution in terms of Bhattacharyya Distance?

b.dist <- 0
for(i in x) {
    b.dist <- b.dist + sqrt((sum(d.flat == i) / length(d.flat)) * dgeom(x = i - 1,
              prob = 1/26))
}
b.dist <- -1 * log(x = b.dist)

The Bhattacharyya Distance between the expected geometric distribution and the emprirical distribution of the distances is about $0.026$, which is fairly close to $0$.

EDIT:

Rather than simply stating that the Bhattacharyya Distance observed above ($0.026$) is fairly close to $0$, I think this is a good example of when simulation comes in handy. The question now is the following: How does the Bhattacharyya Distance observed above compare to typical Bhattacharyya Distances observed if each position of the ordered set is uniform over the letters? Let's generate $10,000$ such ordered sets and compute each of their Bhattacharyya Distances from the expected geometric distribution.

gen.bhat <- function(set, size) {
    new.seq <- sample(x = set, size = size, replace = TRUE)
    d <- vector(mode = 'list', length = length(unique(set)))
    for(i in 1:length(unique(set))) {
        d[[i]] <- diff(which(new.seq == set[i]))
    }
    d.flat <- unlist(x = d)
    x <- range(d.flat)
    x <- x[1]:x[2]
    b.dist <- 0
    for(i in x) {
        b.dist <- b.dist + sqrt((sum(d.flat == i) / length(d.flat)) * dgeom(x = i -1,
                  prob = 1/length(unique(set))))
    }
    b.dist <- -1 * log(x = b.dist)
    return(b.dist)
}
dist.bhat <- replicate(n = 10000, expr = gen.bhat(set = letters, size = 1000))

Now we may compute the probability of observing the Bhattacharyya Distance observed above, or one more extreme, if the ordered set was generated in such a way that each of its positions follows a uniform distribution over the letters.

p <- ifelse(b.dist <= mean(dist.bhat), sum(dist.bhat <= b.dist) / length(dist.bhat),
            sum(dist.bhat > b.dist) / length(dist.bhat))

In this case, the probability turns out to be about $0.38$.

For completeness, the following image is a histogram of the simulated Bhattacharyya Distances. I think it's important to realize that you will never observe a Bhattacharyya Distance of $0$ because the ordered set has finite length. Above, the maximum distance between any two occurrences of a letter is at most $999$.

enter image description here

$\endgroup$
7
  • $\begingroup$ It looks like you assume in the very beginning that the distribution of letters is multinomial with equal probability for each letter. What if the distribution is of unequal probabilities for letters? - Will the expected distribution of distances between occurences for each letter be still geometric? And with what parameter? $\endgroup$
    – ttnphns
    Jul 29, 2012 at 6:46
  • $\begingroup$ With unequal probabilities for each letter, the distance between occurrences of each letter is still geometric. However, the parameter varies by letter, and for each letter it is equal to the probability of a position in the ordered set containing that letter. $\endgroup$ Jul 29, 2012 at 9:49
  • 2
    $\begingroup$ I like your approach. Wouldn't it be more realistic to assume that the number of each letter is fixed and that an ordering is drawn uniformly among all possible orderings? Unfortuately I don't know what the distribution is in that case. Any idea? $\endgroup$
    – gui11aume
    Jul 29, 2012 at 13:40
  • $\begingroup$ @gui11aume That's an interesting thought. Are you referring to a kind of permutation testing approach where we permute the observed ordered set many times and see how similar the original ordered set is to the permutations using some statistic? $\endgroup$ Jul 29, 2012 at 13:47
  • $\begingroup$ Yes, that's what I have in mind. You can then use Bhattacharyya distance or Kullback-Leibler divergence to measure the departure from full mixing. $\endgroup$
    – gui11aume
    Jul 29, 2012 at 13:49
7
$\begingroup$

Exactly what you're describing has been codified into a procedure called the Runs Test. It's not complicated to master. You can find it in many sources on statistical tests, e.g., wikipedia or the Nat'l Instit. of Standards and Technology or YouTube.

$\endgroup$
2
  • $\begingroup$ +1. @Alan, Runs test is also called Wald–Wolfowitz test - for you to know. $\endgroup$
    – ttnphns
    Jul 29, 2012 at 5:47
  • 1
    $\begingroup$ The problem with runs test though is that it is only for dichotomous or dichotomized data. $\endgroup$
    – ttnphns
    Jul 29, 2012 at 6:27
0
$\begingroup$

If you are interested in a slightly different perspective on this, you might like to look at a primer on information theory - an area of mathematics of interest in computing, image/video/audio processing, communication theory and (perhaps more surprisingly) physics and cosmology (crucial to the understanding of black holes, as well as classical thermodynamics) and even biology.

Informally, we can say that a "clumpier" sequence of letters (as per your example) will be more densely compressed when subjected to a general purpose compression algorithm - i.e. a zip file containing the raw text will be smaller. Similarly, a "clumpy" image (say, of a few billiard balls on a plain green baize) will compress a lot more efficiently - e.g. create a smaller jpeg file - than a more varied image (such as an image of a group of people). Of course the information content (a.k.a. negative entropy or "negentropy") of such data has various formal definitions independent of particular compression algorithms.

One example of a case in which an information-theoretical measure might be more revealing than the more classical statistical analyses above is if you are interested in identifying "clumpiness" at multiple (or all) levels of resolution. In the example of your text string, if there were plenty of "A"s bunched together at the beginning of the sequence, then not much bunching of "A"s, and then periodically more bunching and less bunching as the sequence continues, then the clumpiness could be said to exist at multiple resolutions - something which can be very naturally captured by information theoretical measures.

(Edit) It occurs to me that your concern that this might be a ridiculous question, when in fact the study of "clumpiness" - in the guise of information and (neg)entropy - vitally informs us about both the everyday operation of modern life (the internet, mobile communications, language itself) and the nature of the universe (black holes, galaxy formation, interpretation of the Cosmic Background Radiation, determining what is "alive") should be answered with the adage that "there are no stupid questions, only stupid answers" [unattributed quotation].

$\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.