Wie kann man zwei Algorithmen in drei Datensätzen bei der Auswahl und Klassifizierung von Features statistisch vergleichen?

8

Problemhintergrund: Im Rahmen meiner Forschung habe ich zwei Algorithmen geschrieben, mit denen eine Reihe von Merkmalen aus einem Datensatz ausgewählt werden können (Genexpressionsdaten von Krebspatienten). Diese Merkmale werden dann getestet, um festzustellen, wie gut sie eine unsichtbare Probe entweder als Krebs oder als Nichtkrebs klassifizieren können. Für jeden Lauf des Algorithmus wird eine Lösung (eine Reihe von Merkmalen) generiert und an Z unsichtbaren Proben getestet. Die prozentuale Genauigkeit der Lösung wird wie folgt berechnet : (correct classifications / Z) * 100.

Ich habe zwei Algorithmen: Algorithmus X & Algorithmus Y.

Ich habe drei separate (verschiedene Krebs-) Datensätze: Datensatz A, Datensatz B und Datensatz C. Diese Datensätze unterscheiden sich stark voneinander. Sie haben nicht die gleiche Anzahl von Proben oder die gleiche Anzahl von Messungen (Merkmalen) pro Probe.

Ich habe jeden Algorithmus 10 Mal für jeden Datensatz ausgeführt. Algorithmus X hat also 10 Ergebnisse aus Datensatz A, 10 aus Datensatz B und 10 aus Datensatz C. Insgesamt hat Algorithmus X 30 Ergebnisse.

Mein Problem: Ich würde gerne sehen, ob sich die kombinierte Leistung von Algorithmus X über alle drei Datensätze statistisch signifikant von der kombinierten Leistung von Algorithmus Y unterscheidet.

Kann ich die Ergebnisse für Algorithmus X aus jedem Datensatz zu einem einzigen Ergebnissatz kombinieren? Auf diese Weise hätte ich 30 standardisierte Ergebnisse für Algorithmus X und 30 standardisierte Ergebnisse für Algorithmus Y. Ich kann dann den t-Test verwenden, um festzustellen, ob es einen signifikanten Unterschied zwischen den beiden Methoden gibt.

Bearbeiten - Dies sind evolutionäre Algorithmen, sodass sie bei jeder Ausführung eine etwas andere Lösung zurückgeben. Wenn eine Stichprobe jedoch ein Merkmal enthält, das, wenn vorhanden, die Stichprobe stark als Krebs oder Nichtkrebs klassifizieren kann, wird dieses Merkmal fast jedes Mal ausgewählt, wenn der Algorithmus ausgeführt wird.

Ich erhalte aus folgenden Gründen für jeden der 10 Läufe leicht unterschiedliche Ergebnisse:

  • Diese Algorithmen werden zufällig ausgesät.
  • Ich verwende die wiederholte zufällige Validierung von Teilstichproben (10 Wiederholungen).
  • Die von mir verwendeten Datensätze (DNA-Microarray und Proteomics) sind sehr schwierig zu bearbeiten, da es viele lokale Optima gibt, in denen der Algorithmus stecken bleiben kann.
  • Es gibt viele Interaktionen zwischen Funktionen und Teilmengen, die ich erkennen möchte.
  • Ich trainiere 50 Chromosomen und sie sind nicht auf eine bestimmte Länge beschränkt. Sie können frei wachsen und schrumpfen (obwohl der Selektionsdruck sie zu kürzeren Längen führt). Dies führt auch zu Abweichungen vom Endergebnis.

Allerdings wählt der Algorithmus fast immer eine bestimmte Teilmenge von Merkmalen aus!

Hier ist ein Beispiel meiner Ergebnisse (hier werden nur 4 von 10 Läufen für jeden Algorithmus angezeigt):

Datensatz / Lauf-Algorithmus X Algorithmus Y.
A 1 90,91 90,91
A 2 90,91 95,45
A 3 90,91 90,91
A 4 90,91 90,91

B 1 100 100
B 2 100 100
B 3 95,65 100
B 4 95,65 86,96

C 1 90,32 87,10
C 2 70,97 80,65
C 3 96,77 83,87
C 4 80,65 83,87

Wie Sie sehen können, habe ich Ergebnisse für zwei Algorithmen aus drei Datensätzen zusammengestellt. Ich kann Kruskal-Wallis-Tests mit diesen Daten durchführen, aber sind sie gültig? Ich frage dies, weil:

  • Ich bin mir nicht sicher, ob die Genauigkeit in verschiedenen Datensätzen angemessen ist. Wenn dies nicht der Fall ist, wäre es bedeutungslos, sie wie ich zusammenzusetzen, und jeder statistische Test, der an ihnen durchgeführt wird, wäre ebenfalls bedeutungslos.
  • Wenn Sie die Genauigkeiten so zusammenstellen, ist das Gesamtergebnis anfällig für Ausreißer. Die hervorragende Leistung eines Algorithmus für einen Datensatz kann die durchschnittliche Leistung für einen anderen Datensatz maskieren.

Ich kann t-test auch in diesem Fall nicht verwenden, weil:

  • Commensurability - Der T-Test ist nur dann sinnvoll, wenn die Unterschiede zwischen den Datensätzen angemessen sind.
  • t-test erfordert, dass die Unterschiede zwischen den beiden verglichenen Algorithmen normal verteilt sind. In meinem Fall gibt es keine Möglichkeit (zumindest ist mir dies bekannt), diesen Zustand zu garantieren.
  • t-test wird von Ausreißern beeinflusst, die die Teststatistik verzerren und die Leistung des Tests verringern, indem sie den geschätzten Standardfehler erhöhen.

Was denken Sie? Wie kann ich in diesem Fall einen Vergleich zwischen Algorithmus X & Y durchführen?

Revolusionen
quelle
Enthalten Ihre Algorithmen eine Art Zufälligkeit, oder warum führen Sie sie sonst jeweils zehnmal für jeden Datensatz aus?
Stephan Kolassa
Ja! Sie sind evolutionäre Algorithmen (stochastische Algorithmen). Jedes Mal produzieren sie ein anderes Ergebnis. Wenn es jedoch starke Merkmale gibt (Gene / ein einzelner Wert aus einer Probe), werden diese häufig ausgewählt. Ziel des Algorithmus ist es, diejenigen Gene auszuwählen, die stark mit einer bestimmten Klasse korrelieren (z. B. Eierstockkrebs), damit sie in Zukunft für die Früherkennung / Vorhersage von Krebs verwendet werden können.
Revolusionen

Antworten:

8

Solange Ihre Algorithmen keine großen Leistungsunterschiede aufweisen und Sie eine große Anzahl von Testfällen aufweisen, können Sie Unterschiede nur anhand der Leistung erkennen.

Sie können jedoch ein gepaartes Design verwenden:

  • Führen Sie alle drei Algorithmen auf genau demselben Zug- / Test-Split eines Datensatzes aus
  • Aggregieren Sie die Testergebnisse nicht in% korrekt, sondern halten Sie sie auf der Ebene der einzelnen Testfälle als richtig oder falsch.

Schauen Sie sich zum Vergleich McNemars Test an . Die Idee hinter der Nutzung eines gepaarten Designs ist, dass alle Fälle, in denen beide Algorithmen richtig und beide falsch waren, Ihnen nicht dabei helfen, die Algorithmen zu unterscheiden. Aber wenn ein Algorithmus besser ist als der andere, sollte es viele Fälle geben, in denen der bessere Algorithmus richtig, aber nicht schlechter wurde, und nur wenige, die durch die schlechtere Methode richtig vorhergesagt wurden, durch die bessere jedoch falsch.

Auch Cawley und Talbot: Über Überanpassung bei der Modellauswahl und nachfolgende Auswahlverzerrung bei der Leistungsbewertung, JMLR, 2010, 1, 2079-2107. ist sehr relevant.

Aufgrund der zufälligen Aspekte Ihrer Algorithmen möchten Sie auch die gleiche Aufteilung desselben Datensatzes mehrmals überprüfen. Daraus können Sie die Abweichung zwischen verschiedenen Läufen abschätzen, die ansonsten gleich sind. Es kann schwierig sein zu beurteilen, wie unterschiedlich die ausgewählten Variablensätze sind. Wenn Ihr Endziel jedoch die Vorhersageleistung ist, können Sie auch die Variation zwischen Vorhersagen desselben Testfalls während verschiedener Läufe verwenden, um die Stabilität der resultierenden Modelle zu messen.

Sie möchten dann auch die Abweichung (wie oben angegeben) aufgrund unterschiedlicher Aufteilungen des Datensatzes überprüfen und diese mit der ersten Abweichung in Beziehung setzen.

Brüche (wie% korrekt erkannte Stichproben) werden normalerweise als binomial verteilt angenommen , in bestimmten Fällen ist eine normale Annäherung möglich, aber das Kleingedruckte hierfür wird in Feldern mit breiten Datenmatrizen kaum jemals erreicht. Dies hat zur Folge, dass die Konfidenzintervalle für eine kleine Anzahl von Testfällen sehr groß sind. binom::binom.confintBerechnet in R Konfidenzintervalle für den wahren Anteil bei Nr. von Tests und Nr. von Erfolgen.

Schließlich legen meine Erfahrungen mit der genetischen Optimierung für spektroskopische Daten (meine Diplomarbeit in deutscher Sprache) nahe, dass Sie auch die Trainingsfehler überprüfen sollten. GAs neigen dazu, sehr schnell zu überanpassen und zu sehr geringen Trainingsfehlern zu gelangen. Geringe Trainingsfehler sind nicht nur zu optimistisch, sondern haben auch zur Folge, dass die GA nicht zwischen vielen Modellen unterscheiden kann, die gleichermaßen perfekt zu sein scheinen. (Sie haben möglicherweise weniger Probleme damit, wenn die GA intern auch zufällig Stichproben und interne Testsätze unterabtastet.)

Beiträge in englischer Sprache:

cbeleites unzufrieden mit SX
quelle
Vielen Dank für eine hervorragende Analyse! Ich werde ein gepaartes Design ausprobieren. Sie sind genau richtig in Bezug auf Überanpassung. Die nächste Phase meiner Forschung wird sich darauf konzentrieren, eine Überanpassung während des Trainings zu vermeiden. Dies ist wirklich wichtig, da mein Endziel darin besteht, einen Algorithmus zu entwickeln, der vollständig automatisiert ist, damit Onkologen Krebs frühzeitig diagnostizieren können. Ich bin wirklich daran interessiert, Ihre Zeitung zu lesen, aber ich fürchte, ich kann kein Deutsch lesen. Bitte lassen Sie mich wissen, ob es eine englische Version gibt. Nochmals vielen Dank für Ihre ausführliche Eingabe.
Revolusionen
@revolusions: Die Informationen sind etwas über einige Papiere verteilt. Ich habe jedoch eine Liste mit 2 Informationen zur Auswahl der GA-Variablen und eine Liste zur Unsicherheit bei der Messung der Klassifizierungsfehlerraten hinzugefügt. Wenn Sie Fragen haben (oder keinen Zugang zu den Papieren haben), senden Sie mir eine E-Mail.
cbeleites unglücklich mit SX
Vielen Dank! Ich habe es geschafft, das letzte Papier herunterzuladen, kann aber die ersten beiden nicht bekommen. Ich werde es morgen von meinem Universitätscomputer aus versuchen und Sie wissen lassen, ob ich es schaffe, sie herunterzuladen.
Revolusionen
1

Sie führen 10 Mal eine Auswahl mit GA durch und jedes Mal, wenn Sie eine andere Ausgabe erhalten !!

Erstens, wenn Sie mit demselben Startwert beginnen, sollten Sie immer dieselbe ausgewählte featuer-Teilmenge erhalten. Wenn Sie jedoch einen zufälligen Startwert verwenden, sollten Sie höchstwahrscheinlich auch fast dieselben ausgewählten Funktionen erhalten. Ein Grund, warum Sie dieselbe ausgewählte Funktion erhalten, ist in Ihrem Beitrag angegeben. Für einen fairen Vergleich können Sie auch die gleichen Samen in den Läufen von A für die B-Experimente verwenden.

Zweitens können Sie zum Vergleich Kreuzvalidierung oder Bootstraping verwenden. Auf diese Weise erhalten Sie einen repräsentativeren Vergleich. In diesem Fall gibt es eine Variationsquelle, dh zufällige Trainingsmuster, die stärker zu sein scheinen als zufällige Samen. Der Vergleich kann also zeigen, welcher Algorthim wirklich besser ist.

Schließlich können Sie den von Ihnen vorgeschlagenen t-Test verwenden oder einige nicht parametrische Tests wie den Kruskal-Wallis-Test direkt verwenden.

Soufanom
quelle
Vielen Dank für Ihre Antwort! Ich möchte ein paar Dinge klären und vielleicht später noch einmal Ihre Meinung einholen, da ich immer noch verwirrt über den Vergleich bin. Ich hoffe, Sie können helfen! Sie sagten: <blockquote> Für einen fairen Vergleich können Sie auch dieselben Samen in den Läufen von A für die B-Experimente verwenden. </ Blockquote> Dies ist ein sehr guter Punkt, danke. Ich habe meine Frage bearbeitet, um die von Ihnen angesprochenen Punkte anzusprechen. Es wäre großartig, wenn Sie einen Blick darauf werfen und mich wissen lassen könnten, was Sie denken.
Revolusionen
Sie können für jeden Datensatz einen separaten Vergleich zwischen Klassifizierern durchführen. Überprüfen Sie zunächst den Mittelwert und die Standardabweichung. Wenn für alle Datensätze ein Klassifikator den anderen schlägt. Dann sind wir fertig. Andernfalls können Sie eine "Ensemble" -Idee verwenden. Überprüfen Sie das neue Beispiel, wenn es zu Datensatz A gehört. Verwenden Sie den besseren Klassifikator und so weiter. Es kann jedoch einen statistischen Test geben, der auf einer gepaarten Ansicht basiert und den ich für diesen Fall nicht kenne.
Soufanom
Nochmals vielen Dank für Ihre Eingabe. Ich habe getan, was Sie vorgeschlagen haben, und es gibt keinen klaren Gewinner. Deshalb habe ich beschlossen, alles zusammenzustellen und zu sehen, ob es einen Gewinner geben würde. Diese "Ensemble" -Idee klingt interessant. Gibt es einen Ort, an dem ich mehr darüber lesen kann? Danke für Ihre Hilfe.
Revolusionen
Eine weitere Sache, erwägen Sie den Vergleich von Sensitivität und Spezifität. Die Quelle des Ensembles finden Sie in dem Buch unter meinem Beitrag stats.stackexchange.com/questions/47075/…
soufanom