BestMasters Mit „BestMasters“ zeichnet Springer die besten Masterarbeiten aus, die an renom- mierten Hochschulen in Deutschland, Österreich und der Schweiz entstanden sind. Die mit Höchstnote ausgezeichneten Arbeiten wurden durch Gutachter zur Ver- öff entlichung empfohlen und behandeln aktuelle Th emen aus unterschiedlichen Fachgebieten der Naturwissenschaft en, Psychologie, Technik und Wirtschaft swis- senschaft en. Die Reihe wendet sich an Praktiker und Wissenschaft ler gleichermaßen und soll insbesondere auch Nachwuchswissenschaft lern Orientierung geben. Dominik Koch Verbesserung von Klassifi kationsverfahren Informationsgehalt der k-Nächsten-Nachbarn nutzen Dominik Koch München, Deutschland BestMasters ISBN 978-3-658-11475-6 ISBN 978-3-658-11476-3 (eBook) DOI 10.1007/978-3-658-11476-3 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbi- bliogra(cid:191) e; detaillierte bibliogra(cid:191) sche Daten sind im Internet über http://dnb.d-nb.de abrufbar. Springer Spektrum © Springer Fachmedien Wiesbaden 2016 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikrover(cid:191) lmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informa- tionen in diesem Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag noch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oder Äußerungen. Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Springer Fachmedien Wiesbaden ist Teil der Fachverlagsgruppe Springer Science+Business Media (www.springer.com) Vorwort DasvonFixundHodgesentwickeltek-Na¨chsteNachbarnVerfahrenisteinesder simpelstenundzugleichintuitivstenKlassifikationsverfahren.Nichtsdestotrotzist es in den meisten Fa¨llen in der Lage, ziemlich gute Klassifikationsergebnisse zu liefern. Diesen Informationsgehalt der Na¨chsten Nachbarn kann man sich zu Nutze machen, um bereits etablierte Verfahren zu verbessern. In diesem Buch werden die Auswirkungen der Na¨chsten Nachbarn auf den Boosting-Ansatz, Lasso und Random Forest in Bezug auf bina¨re Klassifikationsprobleme behan- delt. Die Informationen, die in den Na¨chsten Nachbarn enthalten sind, werden den Klassifikationsverfahren zusa¨tzlich zu den noch vorhandenen Kovariablen, in Form von Summen, zur Verfu¨gung gestellt. Durch diese Modifikation ist es mo¨glich,eineVerbesserungderKlassifikationsgu¨tezuerzielen. Mu¨nchen,imDezember2014 DominikKoch Inhaltsverzeichnis 1 Einleitung................................................... 1 2 DatenstrukturundNotation................................... 3 2.1 Datenstruktur............................................ 3 2.1.1 GenerelleNa¨chsteNachbarn......................... 3 2.1.2 RichtungsbezogeneNa¨chsteNachbarn ................ 5 2.1.3 SummenalsPra¨diktor .............................. 7 2.2 ModifikationderNa¨chsteNachbarnErmittlung ............... 12 2.2.1 Distanzmaße ...................................... 12 2.2.2 Standardisierung................................... 13 2.2.3 Bindungsbrechung ................................. 14 2.3 Gu¨temaße............................................... 15 2.4 Notation ................................................ 17 3 Klassifikationsverfahren ...................................... 19 3.1 Na¨chsteNachbarn ........................................ 20 3.1.1 k-Na¨chsteNachbarn................................ 20 3.1.2 Gewichteterk-Na¨chsteNachbarnAlgorithmus.......... 25 3.2 LineareDiskriminanzanalyse............................... 29 3.3 QuadratischeDiskriminanzanalyse .......................... 33 3.4 LogistischeRegression.................................... 35 3.5 Lasso................................................... 39 3.6 RandomForests.......................................... 45 3.7 Boosting................................................ 50 3.7.1 AdaBoost......................................... 50 3.7.2 GradientBoosting ................................. 52 3.8 Ensemble-Lasso.......................................... 56 viii Inhaltsverzeichnis 4 SimulierteDatensa¨tze ........................................ 61 4.1 mlbench ................................................ 62 4.2 2dimensionaleGaußverteilung ............................. 66 4.3 2dimensionaleGaußverteilungmitSto¨rvariablen.............. 69 4.4 EinfachesKlassifikationsproblem ........................... 72 4.5 SchwierigesKlassifikationsproblem ......................... 76 4.6 Ergebnisu¨bersicht ........................................ 78 5 RealeDatensa¨tze............................................. 83 5.1 GlasIdentifikation........................................ 84 5.2 Brustkrebs .............................................. 86 5.3 Ionospha¨re .............................................. 89 5.4 AustralischeKreditkartenantra¨ge ........................... 92 5.5 Glaukom................................................ 94 5.6 Ergebnisu¨bersicht ........................................ 97 6 Fazit........................................................ 101 AnhangA FluchderDimensionen ............................... 105 AnhangB ZusatzgrafikendersimuliertenDatensa¨tze .............. 107 B.1 (mlbench)-Gu¨temaße .................................... 107 B.2 (mlbench)-Variablenwichtigkeit ........................... 109 B.3 (mlbench)-WilcoxonVorzeichenRangTests................. 112 B.4 (HT1)-Gu¨temaße........................................ 115 B.5 (HT1)-Variablenwichtigkeit............................... 117 B.6 (HT1)-WilcoxonVorzeichenRangTests .................... 120 B.7 (HT2)-Gu¨temaße........................................ 123 B.8 (HT2)-Variablenwichtigkeit............................... 125 B.9 (HT2)-WilcoxonVorzeichenRangTests .................... 132 B.10 (easy)-Gu¨temaße........................................ 135 B.11 (easy)-Variablenwichtigkeit ............................... 137 B.12 (easy)-WilcoxonVorzeichenRangTests .................... 144 B.13 (difficult)-Gu¨temaße ..................................... 147 B.14 (difficult)-Variablenwichtigkeit ............................ 149 B.15 (difficult)-WilcoxonVorzeichenRangTests.................. 156 AnhangC ZusatzgrafikenderrealenDatensa¨tze................... 159 C.1 (GlasIdentifikation)-Gu¨temaße............................ 159 C.2 (GlasIdentifikation)-Variablenwichtigkeit................... 161 C.3 (GlasIdentifikation)-WilcoxonVorzeichenRangTests ........ 168 Inhaltsverzeichnis ix C.4 (Brustkrebs)-Gu¨temaße .................................. 171 C.5 (Brustkrebs)-Variablenwichtigkeit.......................... 173 C.6 (Brustkrebs)-WilcoxonVorzeichenRangTests ............... 180 C.7 (Ionospha¨re)-Gu¨temaße .................................. 183 C.8 (Ionospha¨re)-Variablenwichtigkeit ......................... 185 C.9 (Ionospha¨re)-WilcoxonVorzeichenRangTests............... 191 C.10 (Kreditkartenantra¨ge)-Gu¨temaße........................... 194 C.11 (Kreditkartenantra¨ge)-Variablenwichtigkeit.................. 196 C.12 (Kreditkartenantra¨ge)-WilcoxonVorzeichenRangTests ....... 205 C.13 (Glaukom)-Gu¨temaße.................................... 208 C.14 (Glaukom)-Variablenwichtigkeit........................... 210 C.15 (Glaukom)-WilcoxonVorzeichenRangTests ................ 217 Literaturverzeichnis .............................................. 221 Abbildungsverzeichnis 2.1 BestimmungderNa¨chstenNachbarn(euklidischeDistanzmetrik). 5 2.2 Verfa¨lschungdurchnicht-informativeKovariablen............. 6 2.3 VergleichderMissklassifikationsratenvonlasso.nn10und lasso.sg................................................. 10 3.1 Voronoi-DiagrammzurVeranschaulichungderMetriken........ 22 3.2 WahldesParameterskbeimk-Na¨chsteNachbarnVerfahren..... 23 3.3 Missklassifikationsratenvonnn1undknn. ................... 24 3.4 Missklassifikationsratendergewichtetenk-Na¨chsteNachbarn Verfahren. .............................................. 29 3.5 VisualisierungvonLDAundQDA.......................... 33 3.6 MissklassifikationsratenvonLDA,QDAsowielogit.cov........ 35 3.7 Missklassifikationsraten diverser Verfahren, welche ausschließlichaufdenNa¨chstenNachbarnoderderenSummen basieren. ............................................... 39 3.8 MissklassifikationsratenderLasso-Verfahren. ................ 45 3.9 MissklassifikationsratederklassischenRandomForestAnsa¨tze.. 50 3.10 MissklassifikationsratederBoostingAnsa¨tze................. 55 3.11 MissklassifikationsratederEnsemble-LassoAnsa¨tze .......... 60 4.1 VisualisierungderSimulationsdaten ........................ 62 4.2 (mlbench)Missklassifikationsraten.......................... 64 4.3 200SimulationsdatengeneriertnachVorschlagvonHastieund Tibshirani(1996)......................................... 66 4.4 (HT1)Missklassifikationsraten. ............................ 67 4.5 (HT2)Missklassifikationsraten. ............................ 70 4.6 (easy)Missklassifikationsraten. ............................ 73