Hintergrund
Nehmen wir an, wir haben ein Alphabet von A,B, C, D
, dann schauen wir uns einige Daten an und finden ein "Wort", bei dem DDDDDDDDCDDDDDD
die Wahrscheinlichkeit, diesen Zufall zu finden, für mich gering erscheint, während das Finden BABDCABCDACDBACD
weniger zufällig erscheint.
Frage
Wie soll ich überprüfen, ob die Zeichenfolgen, auf die ich stoße, nicht zufällig sind?
Ich habe einige Dinge in R ausprobiert, z. B. die Buchstaben numerisch codiert und diese dann mit Permutationen verglichen. Die vorherige Codierung ist jedoch ziemlich umständlich, wahrscheinlich gibt es dafür einen direkteren Ansatz.
text-mining
randomness
CodeNoob
quelle
quelle
Antworten:
Warum sollte das so sein? Wenn der Gesamtanteil der Buchstaben A ... D für jeden Buchstaben gleich 0,25 ist und jeder Buchstabe unabhängig vom anderen ist, sind beide Wörter genau gleich wahrscheinlich. Wenn sich die Verteilung der Buchstaben unterscheidet, können die Wahrscheinlichkeiten für die Erzeugung beider Wörter natürlich unterschiedlich sein.
Sie können versuchen, Wörter mit "geringer Komplexität" zu finden, beispielsweise Wörter mit einem besonders hohen Anteil eines Buchstabens (Sie könnten die Shannon-Informationen verwenden, wie in der anderen Antwort vorgeschlagen, und bei der Analyse biologischer Sequenzen gibt es viele andere Ansätze), aber es gibt sie ist kein Test für "Zufälligkeit", da der Begriff "Zufälligkeit" ohne weitere Annahmen oder Kenntnisse darüber, was Sie tatsächlich analysieren, keinen Sinn ergibt.
quelle
Sie können Shannon-Informationen ausprobieren: wobei , ist die Anzahl der Buchstaben im Wort und.H=−∑i=0nPilog2(Pi) Pi=cin ci c n=|word|
Für das erste Wort hast du . Im zweiten Wort hast du .H=0.35 H=2
Wenn die Entropie hoch ist, können Sie sie sich als zufälliger gegenüber einem anderen Wort mit niedrigerer Entropie vorstellen.
quelle
bababbaabb
undaaaabbbbbb
. Der zugegebenermaßen sehr lockere Begriff der "Zufälligkeit", der von OP verwendet wird, würde den ersteren wahrscheinlich als "zufälliger" als den letzteren betrachten.Andere Antworten hier haben sich auf das allgemeine Auftreten verschiedener Buchstaben in der Sequenz konzentriert, was ein Aspekt der erwarteten "Zufälligkeit" sein kann. Ein weiterer interessanter Aspekt ist jedoch die offensichtliche Zufälligkeit in der Reihenfolge der Buchstaben in der Sequenz. Zumindest würde ich denken, dass "Zufälligkeit" die Austauschbarkeit des Buchstabenvektors beinhaltet, die mit einem "Lauftest" getestet werden kann. Der Lauftest zählt die Anzahl der "Läufe" in der Sequenz und vergleicht die Gesamtzahl der Läufe mit ihrer Nullverteilung unter der Nullhypothese der Austauschbarkeit für einen Vektor mit denselben Buchstaben. Die genaue Definition eines "Laufs" hängt vom jeweiligen Test ab (siehe z. B. eine ähnliche Antwort hier)), aber in diesem Fall besteht die natürliche Definition bei nominalen Kategorien darin, jede aufeinanderfolgende Sequenz, die nur aus einem Buchstaben besteht, als einen einzigen "Lauf" zu zählen.
Zum Beispiel Ihre Sequenz† n=16 r=16
BABD-CABC-DACD-BACD
sieht prima facie nicht zufällig zu mir (kein Brief erscheint mit sich, die für eine Folge dieses lange wahrscheinlich ungewöhnlich ist). Um dies formal zu testen, können wir einen Lauftest auf Austauschbarkeit durchführen. In dieser Sequenz haben wir Buchstaben (vier von jedem Buchstaben) und es gibt Läufe, die jeweils aus einer einzelnen Instanz eines Buchstabens bestehen. Die beobachtete Anzahl von Läufen kann unter der Hypothese der Austauschbarkeit mit ihrer Nullverteilung verglichen werden. Wir können dies über eine Simulation tun, die eine simulierte Nullverteilung und einen p-Wert für den Test ergibt. Das Ergebnis für diese Zeichenfolge ist in der folgenden Grafik dargestellt.Für diese Sequenz beträgt der p-Wert für den (unter der Nullhypothese der Austauschbarkeit) . Dies ist bei einem Signifikanzniveau von 10% signifikant, jedoch nicht bei einem Signifikanzniveau von 5%. Es gibt einige Hinweise auf eine nicht austauschbare Reihe (dh nicht zufällige Reihenfolge), aber die Hinweise sind nicht besonders stark. Bei einer länger beobachteten Zeichenfolge hätte der Lauftest eine größere Leistung, um eine austauschbare Zeichenfolge von einer nicht austauschbaren Zeichenfolge zu unterscheiden. (Wie Sie sehen können, kann mein anfängliches Anscheinsurteil, dass diese Zeichenfolge nicht zufällig ist, falsch sein - der p-Wert ist tatsächlich nicht so niedrig, wie ich es erwartet hatte.)p=0.0537
Schließlich ist zu beachten, dass bei diesem Test nur die Zufälligkeit der Reihenfolge der Buchstaben in der Zeichenfolge berücksichtigt wird. Dabei wird die Anzahl der Buchstaben jedes Typs als feste Eingabe verwendet. Dieser Test wird nicht Zufälligkeit im Sinne von nicht erkennen Austauschbarkeit der Buchstaben in der Zeichenkette, aber es wird nicht testen „Zufälligkeit“ im Sinne der Gesamtwahrscheinlichkeiten der verschiedenen Buchstaben. Wenn letzteres auch Teil der angegebenen Bedeutung von "Zufälligkeit" ist, könnte dieser Lauftest durch einen anderen Test ergänzt werden, der die Gesamtzahl der Buchstaben betrachtet und diese mit einer hypothetischen Nullverteilung vergleicht.
R-Code: Das obige Diagramm und der p-Wert wurden unter Verwendung des folgenden
R
Codes erzeugt:quelle
Angenommen, die Buchstabenfolge ist lang genug, können Sie Zufälligkeitstests auf die Daten anwenden .
Ein Satz solcher Tests wird als eingefleischte Tests bezeichnet :
Sie beinhalten eine möglicherweise willkürliche Reihe von Tests wie:
Eine gute Folge von Zufallsdaten sollte diese Tests bestehen.
Das Bestehen dieser Tests reicht jedoch nicht aus, um zu beweisen, dass die Zahlen kein echtes Signal codieren. Sie könnten die Ausgabe einer hochwertigen Verschlüsselungsroutine sein.
quelle