Standardowa miara zlepienia?

Mam dużo danych i chcę zrobić coś, co wydaje się bardzo proste. W tym dużym zestawie danych interesuje mnie, jak bardzo konkretny element zlepia się ze sobą. Powiedzmy, że moje dane są uporządkowanym zestawem w następujący sposób: {A, C, B, D, A, Z, T, C ...}. Powiedzmy, że chcę wiedzieć, czy litery A znajdują się tuż obok siebie, a nie losowo (lub bardziej równomiernie) w całym zestawie. Jest to właściwość, którą nazywam „grudką”.

Czy jest jakiś prosty pomiar „zlepienia” danych? To znaczy, jakieś statystyki, które pokażą mi, jak daleko od losowej dystrybucji As są? A jeśli nie ma prostego sposobu na zrobienie tego, z grubsza byłoby to trudne? Wszelkie wskazówki bardzo mile widziane!

Załóżmy na przykład, że masz uporządkowany zestaw, w którym każda pozycja ma jednakowe prawdopodobieństwo, że będzie jedną z małych liter alfabetu. W tym przypadku sprawię, że zamówiony zestaw będzie zawierał elementów.$1000$

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

Okazuje się, że jeśli każda z pozycji uporządkowanego zbioru ma równomierny rozkład na małe litery alfabetu, to odległość między dwoma wystąpieniami tej samej litery ma rozkład geometryczny z parametrem . W świetle tych informacji obliczmy odległość między kolejnymi wystąpieniami tej samej litery.$p=1/26$

# 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)

Spójrzmy na histogram odległości między wystąpieniami tej samej litery i porównajmy go z funkcją masy prawdopodobieństwa związaną z wyżej wspomnianym rozkładem geometrycznym.

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)

Czerwone kropki reprezentują rzeczywistą funkcję masy prawdopodobieństwa odległości, której moglibyśmy oczekiwać, gdyby każda z pozycji uporządkowanego zbioru miała równomierny rozkład na litery, a słupki histogramu reprezentują empiryczną funkcję masy prawdopodobieństwa odległości związanej z uporządkowanym zestaw.

Mam nadzieję, że powyższy obraz przekonuje, że rozkład geometryczny jest odpowiedni.

Ponownie, jeśli każda pozycja uporządkowanego zestawu ma jednolity rozkład na litery, spodziewalibyśmy się, że odległość między wystąpieniami tej samej litery będzie podążać za rozkładem geometrycznym z parametrem . Jak więc podobny jest oczekiwany rozkład odległości i empiryczny rozkład różnic? Odległość bhattacharyya dwóch odrębnych rozkładów jest gdy dystrybucje są dokładnie takie same, a raczej jako dystrybucje stają się coraz bardziej różne.0 $p=1/26$$0$$\infty$

Jak d.flatz góry porównuje się z oczekiwanym rozkładem geometrycznym pod względem odległości Bhattacharyya?

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)

Odległość bhattacharyya między oczekiwaną rozkładu geometrycznego i emprirical dystrybucji odległości wynosi około , który jest dość blisko do .$0.026$$0$

EDYTOWAĆ:

Zamiast po prostu stwierdzić, że obserwowana powyżej odległość Bhattacharyya ( ) jest dość bliska , myślę, że jest to dobry przykład, kiedy przydaje się symulacja. Pytanie brzmi teraz: W jaki sposób zaobserwowana powyżej odległość Bhattacharyya porównuje się do typowych odległości Bhattacharyya zaobserwowanych, jeśli każda pozycja uporządkowanego zestawu jest jednolita na literach? Wygenerujmy takich uporządkowanych zestawów i obliczmy ich odległości Bhattacharyya na podstawie oczekiwanego rozkładu geometrycznego.0 10 , $0.026$$0$$10,000$

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))

Teraz możemy obliczyć prawdopodobieństwo zaobserwowania obserwowanej powyżej odległości Bhattacharyya, lub jeszcze jednej skrajności, jeśli uporządkowany zbiór został wygenerowany w taki sposób, że każda jego pozycja ma jednolity rozkład na litery.

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

W tym przypadku prawdopodobieństwo wynosi około .$0.38$

Dla kompletności poniższy obraz jest histogramem symulowanych Odległości Bhattacharyya. Myślę, że ważne jest, aby zdać sobie sprawę, że nigdy nie zaobserwujesz odległości Bhattacharyya równej ponieważ zamówiony zestaw ma skończoną długość. Powyżej maksymalna odległość między dowolnymi dwoma wystąpieniami litery wynosi maksymalnie .$0$$999$

Dokładnie to, co opisujesz, zostało skodyfikowane w procedurze o nazwie Test Runs. Nie jest skomplikowane opanowanie. Można go znaleźć w wielu źródłach na temat testów statystycznych, np. Wikipedia lub Nat'l Institut. standardów i technologii lub YouTube .

Jeśli interesuje Cię nieco inna perspektywa, możesz spojrzeć na elementarną teorię informacji - dziedzinę matematyki interesującą w obliczeniach, przetwarzaniu obrazu / wideo / audio, teorii komunikacji oraz (być może bardziej zaskakującej) fizyki i kosmologia (kluczowa dla zrozumienia czarnych dziur, a także klasyczna termodynamika), a nawet biologia.

Nieoficjalnie możemy powiedzieć, że sekwencja „zbijaków” (jak w twoim przykładzie) będzie bardziej gęsto skompresowana, gdy zostanie poddana algorytmowi kompresji ogólnego przeznaczenia - tzn. Plik zip zawierający surowy tekst będzie mniejszy. Podobnie „zbrylony” obraz (powiedzmy kilku kul bilardowych na zwykłym zielonym baize) skompresuje się o wiele bardziej wydajnie - np. Utworzy mniejszy plik jpeg - niż bardziej zróżnicowany obraz (na przykład obraz grupy ludzi ). Oczywiście zawartość informacyjna (inaczej negatywna entropia lub „negentropy”) takich danych ma różne formalne definicje niezależne od poszczególnych algorytmów kompresji.

Jednym z przykładów przypadku, w którym miara teoretyczno-informacyjna może być bardziej odkrywcza niż bardziej klasyczne analizy statystyczne powyżej, jest zainteresowana identyfikacją „skupisk” na wielu (lub wszystkich) poziomach rozdzielczości. W przykładzie ciągu tekstowego, jeśli na początku sekwencji było dużo wiązek „A”, wówczas nie było zbyt dużo wiązek „A”, a następnie okresowo więcej wiązek i mniej wiązek w miarę kontynuowania sekwencji, to można powiedzieć, że zlepek istnieje w wielu rozdzielczościach - coś, co można bardzo naturalnie uchwycić za pomocą teoretycznych miar informacji.

(Edytuj) Przyszło mi do głowy, że obawiasz się, że może to być śmieszne pytanie, podczas gdy w rzeczywistości badanie „grudek” - pod postacią informacji i (negatywnej) entropii - doskonale informuje nas o codziennym funkcjonowaniu współczesnego życia (internet, komunikacja mobilna, sam język) i natura wszechświata (czarne dziury, powstawanie galaktyk, interpretacja promieniowania tła kosmicznego, określanie, co jest „żywe”) należy odpowiedzieć z przysłowiem, że „nie ma głupich pytań , tylko głupie odpowiedzi „[nieprzypisany cytat].