[algoritme/kans] Vinden uit data-set

[Douweegbertje]

Beste tweakers.

Ik zou graag een data-set willen 'ontleden'.
Nu heb ik naast mijn wiskunde geen ervaringen in het gebruik van algoritmes in programmeren. Althans niet verder dan de standaard hasing / encrypties methodes.

In feite heb ik 4 verschillende waardes, namelijk: 1 - 2 - 3 en 4
Deze komen in een bepaalde volgorde terug.

Voor het blote oog zit hier eigenlijk geen algoritme in, en ziet het er echt uit als random.
Echter kun je toch zien dat het op een bepaalde manier gegenereerd is.

In feite hoef ik niet een 100% zekerheid te hebben, maar zal er ook een deel kansberekening in komen.

Een voorbeeld:

Stel dat de huidige iteratie de volgende waardes geeft: 1-2-4-4-1-4-3-1
Dan zou ik graag de kansen willen weten voor de volgende waarde. Bijvoorbeeld 1: 10%, 2: 10% 3: 10% 4: 70% (overigens al een realistisch voorbeeld, gezien mijn dataset)

Nu wil ik niet opnieuw het wiel uitvinden, dus ik vraag mij het volgende af;
- zijn er al 'tools' die zoiets al kunnen doen (in feite lijkt het verdomd veel op kansberekening voor bijv. roulette)
- zijn er misschien bepaalde library's of weet ik veel wat die hier mee om kunnen gaan?

Ik heb ruime ervaring in PHP, maar python of iets van .net moet ook geen probleem voor me zijn om zo iets simpels te schrijven.

Alvast bedankt

[Soultaker]

Wat de beste aanpak is hangt er vanaf wat voor soort redundantie er precies in je uitvoer zit; op basis van zo'n kort voorbeeld kun je daar nauwelijks uitspraken over doen.

Technieken die voor soortgelijke problemen gebruikt worden zijn prediction by partial matching en (hidden) Markov modelling. Een simpele variant van PPM is N-gram modeling, waarbij je onthoudt hoe vaak elke serie van N letters in de uitvoer voorkomt, en op basis daarvan een voorspelling doet.

Als je voor je voorbeeld bijvoorbeeld een bigram model maakt, dan zie je dat de paren die voorkomen zijn: 12, 24, 44, 41, 14, 43, 31. Het laatste getal is een 1, dus dan kun je zeggen dat de kansen op 1,2,3 en 4 proportioneel zijn aan ε, 1, ε, 1 (omdat alleen 12 en 14 eerder voorkwamen) waarbij ε een klein getal is dat op de een of andere manier gekozen wordt om de kans op een situatie die nog niet eerder is voorgekomen in te schatten. Bij langere reeksen kan dit redelijk goed werken.

De vraag is dan weer welke waarde van N de beste voorspellingen levert. Je kunt verschillende modellen gaan mixen en dan kom je al snel op een soort PPM of dynamisch Markovmodel uit. Of die extra complexiteit de moeite waard is hang sterk af van waar je 't voor wil gebruiken.

Voor inspiratie kun je ook kijken naar compressie-algoritmen die gebaseerd zijn op het principe van statistisch modelleren van de invoer gevolgd door entropie-codering — wat jij wil is eigenlijk de eerste stap daarvan. Bekende voorbeelden zijn PPMd en PAQ.

[Douweegbertje]

code:

1 1 4 4 1 1 4 3 4 4 1 4 4 4 4 1 1 1 1 4 1 4 3 4 3 2 1 4 1 4 1 4 1 4 1 4 1 1 3 4 1 3 2 2 1 4 4 1 3 4 1 1 4 2 4 1 1 4 4 4 4 2 4 1 2 3 3 3 1 1 4 1 3 1 3 4 1 4 1 1 1 1 4 4 4 4 1 4 4 2 1 4 4 1 4 4 3 4 3 1 1 4 1 1 4 1 4 1 1 1 4 1 2 4 1 4 4 4 4 2 3 1 4 4 1 1 4 2 2 1 2 2 4 4 1 1 1 1 2 4 1 2 1 1 1 1 4 4 4 1 3 1 1 1 1 1 1 1 1 4 1 2 3 4 4 4 1 2 4 1 4 4 1 4 1 4 4 1 1 2 1 3 4 4 4 1 1 1 4 4 3 3 4 1 1 1 1 4

Hierbij dan even een gedeelte van de data.

In feite zit er geen redundantie, of misschien ook wel maar heb je daar super veel data voor nodig om het één en ander terug te gaan zien.
Daarom zoek ik ook deels een kansberekening ipv een pure wiskundige formule die exact gaat vertellen wat het volgende nummer is, aangezien dat naar mijn mening niet mogelijk is.

Het verschil zit hem ook in, dat ik graag 'ergens' en dan maak het niet uit wanneer, een hoge kans op nummer 4 wil krijgen. Het enige wat ik nu een beetje kan zien is dat bijvoorbeeld 4, meestal na een 1 komt. Echter komt dit ook omdat 2 - 3 weinig voor komen.

Hopelijk ben ik nu ook iets duidelijker
Ik ga even naar je voorbeelden kijken, bedankt

[pedorus]

Als ik er een Wikipedia: Pearson's chi-squared test op los laat, dan lijkt die data niet af te wijken van data met 1 t/m 4 willekeurig getrokken met kansen (0.4, 0.1, 0.1, 0.4). Dezelfde test ziet ook geen onderscheid tussen groepen als je de aantallen indeelt op basis van het voorgaande getal. In R:

> chisq.test(c(84,18,19,76),p=c(0.4,0.1,0.1,0.4))

        Chi-squared test for given probabilities

data:  c(84, 18, 19, 76) 
X-squared = 0.6142, df = 3, p-value = 0.8932

> chisq.test(rbind(c(36,8,7,33),c(6,3,3,6),c(5,2,3,9),c(36,5,6,29)),
simulate.p.value=TRUE)

        Pearson's Chi-squared test with simulated p-value (based on 2000
        replicates)

data:  rbind(c(36, 8, 7, 33), c(6, 3, 3, 6), c(5, 2, 3, 9), c(36, 5,
      6, 29)) 
X-squared = 6.2377, df = NA, p-value = 0.7271

Dergelijke hoge p-waardes (groter dan 0.1) geven geen aanwijzing dat de boel afwijkt van de hypothese. Je hebt dus waarschijnlijk meer test data dan hierboven staat nodig voor analyse, of wellicht is er simpelweg getrokken zoals hierboven staat.