Standardowa miara zlepienia?

13

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!

Alan H.
źródło

Odpowiedzi:

14

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.

wprowadź opis zdjęcia tutaj

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/260

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 .00.0260

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 , 0000.026010,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 .9990999

wprowadź opis zdjęcia tutaj

przyjęty jako normalny
źródło
Wygląda na to, że zakładasz na samym początku, że rozkład liter jest wielomianowy z jednakowym prawdopodobieństwem dla każdej litery. Co się stanie, jeśli rozkład jest nierówny dla liter? - Czy oczekiwany rozkład odległości między wystąpieniami dla każdej litery będzie nadal geometryczny? I jakim parametrem?
ttnphns
Przy nierównych prawdopodobieństwach dla każdej litery odległość między wystąpieniami każdej litery jest nadal geometryczna. Jednak parametr różni się w zależności od litery i dla każdej litery jest równy prawdopodobieństwu pozycji w uporządkowanym zestawie zawierającym tę literę.
zakładano, że jest nietypowy
1
Lubię twoje podejście. Czy nie byłoby bardziej realistyczne założyć, że liczba każdej litery jest stała i że kolejność jest rysowana jednolicie wśród wszystkich możliwych kolejności? Niestety nie wiem, co to za dystrybucja. Dowolny pomysł?
gui11aume
@ gui11aume To ciekawa myśl. Czy masz na myśli rodzaj testowania permutacji, w którym wielokrotnie permutujemy obserwowany uporządkowany zestaw i widzimy, jak podobny jest oryginalny zestaw uporządkowany do permutacji za pomocą statystyk?
zakładano, że jest nietypowy
Tak, właśnie to mam na myśli. Następnie można użyć odległości Bhattacharyya lub dywergencji Kullbacka-Leiblera, aby zmierzyć odstępstwo od pełnego wymieszania.
gui11aume
7

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 .

rolando2
źródło
+1. @Alan, test Runs nazywa się również testem Wald – Wolfowitz - dla twojej wiedzy.
ttnphns
Problem z testami uruchomieniowymi polega jednak na tym, że dotyczy to tylko danych dychotomicznych lub dychotomicznych.
ttnphns
0

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].

Barney Pitt
źródło