Copenhagen Business School
17. maj 2021
Prædiktere Frafaldssandsynlighed for gymnasiale studerende ved brug af
Supervised Machine Learning
Skrevet af:
Saifullah Babrak — 112186 Andreas Schade — 110806
Vejleder:
Anders Rønn-Nielsen
Speciale, Cand.merc.(mat.)
MSc in Business Administration and Mathematical Business Economics
Sider: 91 Anslag: 222232
Abstract
In this master thesis we investigate how machine learning algorithms can be used in the industry of education. More specific we will investigate if machine learning algorithm can be used to predict the dropout probabilities for high school students.
By using Edaptios anonymized data on the students, we will try different algorithms as Logistic Regression, Random Forest, XGboost and Neural Networks to see if it is possible to predict a useful dropout probability. Lastly we will contruct a Stacking model by combining all the previous mentioned models except Neural Network. For every model we will fit a balanced and unbalanced model. Furthermore, we will test different thresholds and find the best performing model.
After testing the models we conclude that the logistic regresssion models does not obtain any useful results. Random Forest and XGboost on the other hand result in high performing models which can be used for predicting dropout probabilities with a low misclassicationrate. We can also conclude that Neural Network achive the same performs level as the logistic regression models. Lastly we can conclude that Stacking obtaing similar results to Random Forest and XGboost.
Indhold
1 Introduktion 1
1.1 Problemformulering . . . 2
1.1.1 Problemstilling . . . 2
1.2 Afgrænsning . . . 2
1.3 Struktur . . . 3
2 Datahåndtering 3 2.1 Edaptio . . . 3
2.2 Tabel beskrivelse . . . 4
2.3 Variabel beskrivelse . . . 7
2.4 Samling af datasæt fra database . . . 8
2.5 Data transformering og aggregering . . . 9
2.6 Dataudforskning . . . 11
2.7 Håndtering af uafhængighed . . . 13
3 Teori 14 3.1 Sentiment analyse . . . 14
3.1.1 Bag-Of-Words . . . 14
3.1.3 Term Frequency - Inverse Document Frequency (TF-IDF) . . 15
3.1.4 Afinn pakken . . . 16
3.2 Optimal model performance . . . 16
3.2.1 Trænings- og testdatasæt . . . 16
3.2.2 Overfitting . . . 17
3.2.3 Regularisering . . . 17
3.2.4 Hyperparametre . . . 17
3.2.5 Cross-validation . . . 17
3.2.6 Gridsearch . . . 18
3.3 Logistisk Regression . . . 18
3.3.1 Regulariseret Logistisk Regression . . . 19
3.3.1.1 Lasso Regularisering (L1) . . . 20
3.3.1.2 Ridge Regularisering (L2) . . . 20
3.3.2 Hyperparametre beskrivelse . . . 20
3.4 Random Forest . . . 21
3.4.1 Klassifikationstræ . . . 21
3.4.1.1 Renhed i Noder . . . 22
3.4.1.2 Pruning . . . 23
3.4.2 Bootstrapping . . . 23
3.4.2.1 Out-Of-Bag (OOB) . . . 24
3.4.3 Bagging . . . 24
3.4.4 Random Forest algoritme . . . 25
3.4.5 Hyperparametre beskrivelse . . . 26
3.5 XGboost . . . 27
3.5.1 Boosting . . . 28
3.5.2 Gradient Boosting . . . 29
3.5.2.1 Loss funktion . . . 30
3.5.3 XGboost algoritme . . . 31
3.5.3.1 Shrinkage og kolonne subsampling . . . 33
3.5.3.2 Approksimativ algoritme og sparse matricer . . . 33
3.5.4 Hyperparametre beskrivelse . . . 34
3.6 Neuralt Netværk . . . 35
3.6.1 Feed forward . . . 36
3.6.2 Perceptron . . . 36
3.6.3 Valg af activation funktion . . . 37
3.6.4 Multilags Neuralt Netværk . . . 38
3.6.5 Backpropagation . . . 39
3.6.5.1 Gradient Descent . . . 40
3.6.5.2 Stochastic gradient descent . . . 40
3.6.5.3 Backpropagation algoritme . . . 40
3.6.6 Overfitting . . . 42
3.6.7 Regularisering . . . 42
3.6.7.1 Early stopping . . . 43
3.6.7.2 Dybde af Neuralt Netværk . . . 43
3.6.7.3 Dropout regularisering . . . 44
3.7 Stacked Machine Learning Model . . . 44
3.7.1 Stacking algoritme . . . 44
3.8 AUC/ROC . . . 46
3.8.1 Threshold . . . 46
3.8.2 Confusion matrix, sensitivitet og specificitet . . . 46
3.8.3 Performancemål . . . 47
3.8.3.1 Precision . . . 47
3.8.3.2 Recall . . . 48
3.8.3.3 Accuracy . . . 48
3.8.3.4 F1-score . . . 48
3.8.3.5 Samlet . . . 48
3.8.4 Receiver Operating Characteristic (ROC) . . . 48
3.8.4.1 Area Under Curve (AUC) . . . 49
4 Analyse 49 4.1 Datagrundlag . . . 50
4.1.1 Valg af datasæt . . . 50
4.1.2 Ubalance i datasæt . . . 51
4.1.3 Håndtering af klasse ubalance . . . 52
4.1.4 Endeligt datasæt . . . 54
4.1.5 Threshold . . . 54
4.2 Logisktisk Regression . . . 55
4.2.1 Plain Logistisk Regression . . . 55
4.2.1.1 Hyperparametre . . . 55
4.2.1.2 Ubalanceret klassifikationsresultater . . . 56
4.2.1.3 Balanceret klassifikationsresultater . . . 57
4.2.2 Ridge Logistisk Regression . . . 58
4.2.2.1 Hyperparametre . . . 58
4.2.2.2 Ubalanceret klassifikationsresultater . . . 59
4.2.2.3 Balanceret klassifikationsresultater . . . 60
4.2.3 Lasso Logistisk Regression . . . 61
4.2.3.1 Hyperparametre . . . 61
4.2.3.2 Ubalanceret klassifikationsresultater . . . 61
4.2.3.3 Balanceret klassifikationsresultater . . . 62
4.2.4 Receiver Operating Characteristic (ROC) . . . 64
4.2.5 Sammenfatning . . . 65
4.3 Random Forest . . . 66
4.3.1 Ubalanceret Random Forest . . . 66
4.3.1.1 Hyperparametre . . . 66
4.3.1.2 Klassifikationsresultater . . . 67
4.3.2 Balanceret Random Forest . . . 68
4.3.2.1 Hyperparmatre . . . 68
4.3.2.2 Klassifikationsresultater . . . 69
4.3.3 Receiver Operating Characteristic (ROC) . . . 70
4.3.4 Sammenfatning . . . 70
4.4 XGboost . . . 71
4.4.1 Hyperparametre ubalanceret og balanceret . . . 71
4.4.2 Ubalanceret klassifikationsresultater . . . 72
4.4.3 Balanceret klassifikationsresultater . . . 74
4.4.4 Receiver Operating Characteristic (ROC) . . . 75
4.4.5 Sammenfatning . . . 76
4.5 Neuralt Netværk . . . 76
4.5.1 Valg af Neuralt Netværk arkitektur . . . 77
4.5.2 Neuralt Netværk uden regularisering . . . 77
4.5.2.1 Klassifikationsresultater . . . 78
4.5.3 Neuralt Netværk med regularisering . . . 79
4.5.3.1 Klassifikationsresultater . . . 80
4.5.4 Receiver Operating Characteristic (ROC) . . . 81
4.5.5 Balanceret Neuralt Netværk . . . 81
4.5.6 Sammenfatning . . . 82
4.6 Stacked Machine Model . . . 82
4.6.1 Klassifikationsresultater . . . 83
4.6.2 Receiver Operating Characteristic (ROC) . . . 84
4.6.3 Sammenfatning . . . 84
4.7 Modelsammenfatning . . . 84
5 Konklusion 85 6 Diskussion 88 6.1 Data . . . 88
6.1.1 Data transformeringsvalg . . . 88
6.1.2 Ubalance i datasæt . . . 88
6.1.3 Tilføjelse af nye variable til datasættet . . . 89
6.1.4 Begrænsninger . . . 89
6.2 Modeller . . . 90
6.3 Det økonomiske aspekt . . . 90
Litteratur 92
Appendiks 94
A Maks / Min af renhed mål 94
B Balancerede klassifikationsresultater Neuralt Netværk 94
C MySQL query 95
D MySQL query 103
1 Introduktion
Uddannelse er fundamentet for fremtiden af samfundet. Som Malcolm X siger:
"Education is the passport to the future, for tomorrow belongs to those who prepare for it today- Malcolm X
Danmark forbereder sin befolkning på fremtiden ved at gøre folkeskolen obligatorisk.
Desuden har vi i Danmark har fokus på at få folk uddannet, hvorfor uddannelser er gratis. Man bliver tilmed betalt for at tage en uddannelse. Efter folkeskolen tager man sit første selvstændige valg om at starte på en gymnasial uddannelse. Idet at gymnasiet ikke er obligatorisk, vil der være en risiko for, at en studerende ikke gen- nemfører uddannelsen. Gymnasiet skaber et fundament for de studerendes efterføl- gende uddannelsesforløb. Derfor er det vigtigt at få flest mulige igennem gymnasiet.
Staten bidrager til at få flest mulige studerende igennem uddannelsessystemet ved at betale institutionerne et honorar for hver studerende, som gennemfører et forløb [1]. Det vil sige, at institutionerne har et økonomisk incitament for at hjælpe de studerende igennem flest mulige kurser. Derfor ansættes personale med kompeten- cer i at fastholde og hjælpe studerende, som har det svært. Desuden vil der være en personlig gevinst for den studerende ved at gennemføre uddannelsen. Dette kan give den studerende mod på at læse en lang videregående uddannelse, som på sigt kan gavne samfundet.
Ved indsamling af data på de studerende, kan man bygge modeller, der kan bruges som værktøjer til at hjælpe institutionen med at detektere frafaldstruede studeren- de. Den nye GDPR-lovgivning gør det dog vanskeligt at opbevare personfølsomme data. Derfor har Edaptio udviklet en platform, som håndterer personfølsomme data korrekt. Edaptio er en læringsplatform, som de gymnasielle institutioner kan bruge til at tilrettelægge undervisningen og som de studerende kan tilgå. De studerendes interaktion med platformen bliver logget og gemt i en database. Edaptio ønsker at levere et værktøj, som kan hjælpe gymnasierne med at finde de studerende, som har behov for ekstra hjælp. Værktøjet skal prædiktere sandsynligheden for frafald for hver studerende. Desuden vil Edaptio tilbyde sine kunder to typer af model- ler. Den første model skal fokusere på at klassificiere så mange frafald som muligt, selvom det betyder, at flere ikke-frafald bliver klassificeret som frafald. Den anden model skal være sikker i prædiktionen af frafald. Det vil sige, at modellen hellere skal fejlprædiktere frafald som ikke-frafald end omvendt. For at løse dette problem kan adskillige Machine Learning modeller anvendes.
Dette leder os til følgende problemformulering.
1.1 Problemformulering
Hvordan kan supervised Machine Learning algoritme, bruges på de studerendes ak- tivitetsdata til at prædiktere en frafaldssandsynlighed?
1.1.1 Problemstilling
• Hvordan en kan ikke-personfølsomme aktivitetsdata fra Edaptios platform bru- ges til at prædiktere om en studerende frafalder et kursus?
• Hvilke prædiktionsmodeller passer til de to typer af modeller, som Edaptio vil levere til sine kunder?
• Er det muligt at lave en sandsynlighedsprædiktion for frafald, som faktisk hjælper skolerne?
1.2 Afgrænsning
I denne opgave fokuserer vi på at håndtere Edaptios problemstilling specificeret i afsnit 1.1. Derfor fokuserer vi udelukkende på at prædiktere studerendes frafalds- sandsynligheder fra kurser. Vi har afgrænset os til Edaptios kunder fra gymnasielle institutioner som STX, HHX, HTX, HF´ere og VUC´er. Grunden til denne afgræns- ning er, at vi laver et meget specifikt værktøj til Edaptio. Vi har valgt at afgrænse os til at opstille data, så vi har et supervised Machine Learning problem. På den måde kan vi imødekomme Edaptios forespørgsel i forhold til prædiktion af frafald.
Løsningen i denne rapport opstilles, så Edaptio selv kan vælge, hvilken prædiktion de ønsker. Det vil sige, hvis Edaptio for eksempel ønsker at se på studerende 12 uger inde i kurset og ønsker at lave en prædiktion 8 uger i fremtiden, så skal dette være muligt.
Vi har valgt at afgrænse os til fire typer af modeller. Den første model, som vi vil bruge til Edaptios data, er logistisk regression, der fungerer som vores baseline model. Her vil vi både bruge de uregulariserede og regulariserede versioner. Dernæst vil vi undersøge, hvordan træmodeller, som Random Forest og XGboost, performer.
Den tredje type model, som vi laver, er et Neuralt Netværk, hvor vi tester, hvordan denne model performer. Til slut vil vi lave en ensemble model kaldet stacking, hvor vi samler Lasso Regression, Random Forest og XGboost. Derudover har vi valgt at fokusere på den statistiske performance og undlader derfor at fokusere på, hvordan algoritmerne kan optimeres.
Vi vælger ikke at finde de absolut optimale hyperparametre, da vores fokus er på modellernes generelle performance.
I det kommende afsnit vil vi kortlægge strukturen for rapporten.
1.3 Struktur
Rapporten vil besvare spørgmålene fra afsnit 1.1 med følgende struktur.
I kapitel 2 giver vi en overordnet beskrivelse af hvordan Edaptios data håndteres.
Her vil vi beskrive Edaptios original data fra databasen. Kapitlet vil også indholde en beskrivelse af de variable, som vi laver på baggrund af Edaptios data og hvordan vi samler data til det endelige datasæt. Vi vil yderligere undersøge, hvordan aktivi- teten fordeler sig for de studerende i datasættet. Til slut vil vi undersøge for mulig afhængighed i datasættet.
I kapitel 3 vil vi gennemgå den generelle teori for modellerne, som vi benytter i rapporten. Derudover vil der være en teoretisk gennemgang af de metoder, som vi bruger til at måle model performance.
I kapitel 4 vil vi bruge teorien beskrevet i kapitel 3 til at opstille vores modeller.
Vi vil yderligere lave en analyse af, hvordan de forskellige modeller performer på Edaptios data.
Vi vil i kapitel 5 lave en konklusion, hvor vi opsummerer de væsentlige resultater fra analysen og konkluderer, hvilke anbefalinger vi har til Edaptio.
Til slut i kapitel 6 vil vi diskutere, hvilke alternativer der er til håndtering af pro- blemet beskrevet i afsnit 1.1. Yderligere vil vi diskutere, hvilke begrænsningerne vi møder ved brug af Edaptios data og hvordan man kan håndtere disse.
Python koden for alle modellerne i denne rapport er vedhæftet som en zip-fil.
2 Datahåndtering
Dette kapitel vil give et overblik over, hvordan vi transformerer Edaptios data fra deres database til ét samlet datasæt. I første afsnit 2.1 bliver Edaptio beskrevet, for at give en forståelse af hvor data stammer fra. Derefter vil afsnit 2.2 give et overblik over de tabeller fra Edaptios database, som bruges til at samle det endelige datasæt. Afsnit 2.3 giver en beskrivelse af de variable, som er indhentet og benyttet til at danne variablene i det endelige datasæt. Afsnit 2.4 beskriver, hvordan tabeller fra Edaptios database kædes sammen. Afsnit 2.5 vil beskrive hvordan de indhentede variable i 2.3 omdannes til variable, som kan bruges til klassificering. Det endelige datasæt er samlet og afsnit 2.6 fokuserer på at udforske dette. Afslutningsvist vil afsnit 2.7 beskrive håndtering af uafhængighedsantagelsen.
2.1 Edaptio
Data anvendt i denne rapport kommer fra et samarbejde med virksomheden Edap- tio. Edaptios vision er at give flest mulige adgang til bedre læring og give undervisere den bedste læringsoplevelse. Desuden har Edaptio tre produkter, Bookzy, Matema-
tiktutor og Learnu. Bookzy er en platform, hvor studerende kan samarbejde. Mate- matiktutor er et værktøj til at forbedre de studerendes matematikkundskaber ved at løse opgaver. Learnu er en platform, hvor underviseren tilrettelægger undervis- ning til de studerende. Her kan underviseren oprette materiale til undervisningen og eleverne kan gennemgå materialet enten i fællesskab med læreren eller hver for sig.
Materialet kan eksempelvis bestå af Youtube videoer og quizzer. Når underviseren tilrettelægger sin undervisning på Edaptios platform, bliver samtlige interaktioner mellem de studerende og platformen logget. Platformen er etableret til HF og andre gymnasiale institutioner, hvor størstedelen af Edaptios kunder er HF uddannelses- institutioner. De har også andre virksomheder, enkeltpersoner og andre kunder, som ikke er tilknyttet en gymnasiel institution.
Edaptio har en ambition om at anvende Machine Learning algoritmer på den sto- re mængde af logget data. Som tidligere nævnt bliver de studerendes aktiviteter på platformen logget kontinuerligt i Edaptios egen database. Personfølsomme op- lysninger på de studerende bliver anonymiseret i databasen grundet GDPR loven.
Af samme årsag bliver 5 år gammel data slettet. Edaptios data består af 98 for- skellige tabeller, hvor hver af tabellerne følger specifikke interaktioner mellem den studerende og platformen.
Det følgende afsnit vil indeholde en beskrivelse af tabellerne fra databasen, som vi bruger i vores datasæt.
2.2 Tabel beskrivelse
activity_log:
Hele vores datasæt er bygget op omkring tabellen, activity_log, som indeholder de studerendes interaktion med Learnu platformen. Det kan for eksempel være, at den studerende har besvaret en quiz eller set en Youtube video, som er inkluderet i un- dervisningsmaterialet.
youtube_video_statistics:
Denne tabel indeholder information om de forskellige Youtube videoer, som læreren har inkluderet i undervisningen. Yderligere finder vi her, hvor meget af videoen en studerende har set.
vimeo_video_statistics:
Denne tabel indeholder samme information som for youtube_video_statistics, men Youtube erstattes her med Vimeo. Vimeo er en videotjeneste som Youtube.
media_view_statistics:
Denne tabel indeholder samme information somyoutube_video_statistics og vimeo_video_statistics, men hvor videoer er uploadet fra lærerens egen computer.
quiz_question_responses:
Denne tabel indeholder information om quizzerne, der er inkluderet som læringsele- ment i undervisningen. Yderligere findes der information om, hvor mange spørgsmål den studerende har besvaret og hvorvidt en studerende har svaret rigtigt eller forkert på et spørgsmål.
quiz_question_relations:
Denne tabel bruges til at beregne antallet af spørgsmål i hver quiz.
questionnaire_question_responses:
Denne tabel indeholder information om de studerendes svar på evalueringer. Det kan for eksempel være evaluering af platformen Learnu. Derfor findes der ikke et rigtigt eller forkert svar, men er blot en interaktion mellem den studerende og platformen, Learnu.
questionnaire_question_relations:
Ligesomquiz_question_relationsbruges denne tabel også til at beregne, hvor mange spørgsmål der indgår i hver evaluering. Dette bruges til at se, hvor mange spørgsmål den studerende har besvaret af evalueringen.
raw_text:
Denne tabel indeholder tekst, som skrives ud til de studerende. Det kan for eksempel være en informerende tekst, som beskriver, at den studerende har fuldført et emne i matematik.
raw_text_statistics:
I denne tabel findes data på, hvor meget tid de studerende bruger på at læse teksten, som skrives til dem.
user_dropouts:
Denne tabel er vigtig, da den indeholder information om, hvornår studerende udgår fra et kursus. Informationen rapporteres af de forskellige institutioner. Hvis den stu- derende udgår fra et kursus før kursets officielle afslutningstidspunkt, så vil denne studerende blive kategoriseret som et frafald.
assignment:
Denne tabel indeholder information om opgaverne, som de studerende skal lave og om de har afleveret opgaverne. Yderligere findes information om afleveringsfristen, om mulighed for grupper eller genaflevering.
assignment_plans:
Denne tabel indeholder information om afleveringstidspunktet for de studerendes afleveringer.
external_links:
Underviseren kan inkludere et link til eksempelvis khanacademy. Denne tabel ind- holder linket, titel, beskrivelse og kurset linket er lagt op i.
flashcard_collection_statistics:
En flashcard kollektion er en samling af flashcards, som den studerende kan svare på.
Flashcardet kan derefter vendes for at se, om man har svaret rigtigt på spørgsmålet.
Denne tabel indeholder flashcard kollektionerne, som er inkluderet i undervisningen.
flashcard_statistics:
Denne tabel indeholder information om, hvilke flashcards den studerende har besva- ret.
users:
Denne tabel indeholder information om, en studerende har et profilbillede inde på Learnu platformen og hvilken institution den studerende tilhører.
interactives:
Denne tabel indeholder information om interaktionen mellem den studerende og matematikprogrammet Geogebra.
posts:
Denne tabel indholder information på for eksempel feedback på en aflevering. Yder- ligere findes der kommentarer til afleveringerne fra underviseren til de studerende.
group_material_elements:
Denne tabel bruges til at koble kurser tilactivity_log. group_materials:
Denne tabel indeholder kursus id.
uni_groups:
Denne tabel bruges til at finde start- og sluttidspunt for kurserne.
uni_admin_user_ids:
Denne tabel bruges til at fjerne undervisere fra activity_log.
I dette afsnit har der været en gennemgang af tabellerne brugt til at danne det endelige datasæt. I det efterfølgende afsnit vil de mest relevante variable i datasættet blive beskrevet.
2.3 Variabel beskrivelse
Dette afsnit beskriver alle variable, som bruges til at opstille det endelige datasæt.
En oversigt over beskrivelserne vil fremgå i tabel 1. Variable, hvor der er behov for uddybende forklaring, beskrives efterfølgende.
Variabel Beskrivelse
activity_id Unikt id for hver aktivitet
user_id Unikt bruger-id. Dette nummer er ens for samme bruger på tværs af kurser
adaptive_object_id Et unikt interaktions-id for hver type af aktivitet
adaptive_object_type_id Aktivitetstype
read_date Starttidspunkt for en given aktivitet
group_id Unikt id for hvert kursus
understood_date Tidspunktet for når en aktivitet er gennemført
group_material_id Et unikt id for hver aktivitet i et kursus
video_id Unikt id for en bestemt video
video_type Videotype
max_watch_time Hvor langt en studerende er nået i en video
duration Længden af en video
latest_watch_time Tidspunktet for sidste gang videoen er blevet set
total_watch_time Den totale mængde af tid en studernede har brugt på en video
dropout_time Tidspunktet hvor den studerende frafalder
quiz_id Unikt id for hver quiz
user_answered_correct En binær variabel, som viser, om den studerende har svaret korrekt på et spørgsmål i en quiz
text Teksten for raw_text elementet
total_time_spent Det totale antal sekunder en studerende bruger på et raw_text element
assignment_time Afleveringstidspunkt
allow_late En binær variabel som beskriver, om det er tilladt at aflevere senere end afleveringsfristen
allow_groups En binær variabel som beskriver, om underviseren tillader, at man afleverer som gruppe
profile_picture Et id på et billede den studerende har indsat som profilbillede
institution_id Et id som beskriver, hvilken institution den studerende tilhører
uni_start_date Kursus startdato
uni_end_date Kursus slutdato
Tabel 1: Beskrivelse af originale variabler fra Edaptios database
Variablenunderstood_datekan have flere betydninger afhængigt af hvilken inter- aktion, som den studerende har med platformen. For et flashcard vil den studerendes understood_date være tidspunktet for, hvornår det vendes. For en video vil den studerendesunderstood_date være, hvornår videoen er set færdig.
Variablentotal_watch_timeangiver den totale tid, der er brugt på at se en video.
I kombination med duration kan antallet af gange en video cirka er set beregnes.
Bemærk, attotal_watch_timeer summen af alt tid, der er brugt på at se videoen.
Det vil sige, at videoen ikke nødvendigvis er set til ende. For eksempel hvis en stu- derende har set den samme del af en video flere gange, så kantotal_watch_time være højere end længden på videoen.
max_watch_time angiver det seneste tidspunkt, som den studerende er nået til i videoen. Dette kan være misvisende, hvis den studerende springer frem i videoen.
I så fald vilmax_watch_time være det tidpunkt, den studerende spoler frem til.
2.4 Samling af datasæt fra database
Alle tabellerne beskrevet i afsnittet 2.2 sammensættes ved brug af MySQL1. Koden er at finde i appendix D. Tabellen activity_log har 3.348.506 rækker og indehol- der de studerendes interaktion med Learnu platformen. Vi tager udgangspunkt i activity_log og bruger denne til at samle alle tabellerne. Hver type aktivitet en stu- derende laver, findes iactivity_log. Yderligere information om aktiviteten findes i en eller flere af de tidligere beskrevet tabeller. Derfor sættes disse tabeller sammen med activity_log tabellen for at se hvilken specifik type af aktivitet, der har været. På den måde tilføjer vi mere information tilactivity_log tabellen. For eksempel hvis én
1Koden kan findes i Appendiks D
aktivitet har været, at en aflevering er afleveret, vilactivity_log udvides med denne information fraassigntments tabellen. Med andre ord sættes disse tabeller sammen.
Det samme gør sig gældende for samtlige variable beskrevet i tabel 2. Aktiviteter er derfor ikke én samlet tabel fra start, hvorfor det kræver, at der bliver fundet de rig- tige forbindelser mellem tabellerne i databasen. Dette er nødvendigt, da tabellerne hver især ikke har nogen relevant information.
For at samle tabellerne krævede det en forståelse af relationen mellem de forskellige tabeller i databasen. Dette har været en omfattende proces, da flere mindre tabeller skulle sammensættes for at beskrive hver aktivitetstype. Det ønskede mål er at samle et stort datasæt, som indeholder alt relevant information.
Efter sammensætningen af tabellerne skal data renses. Derfor vil der i næste afsnit være en gennemgang af, hvordan transformering og aggregering af data håndteres.
2.5 Data transformering og aggregering
Ved brug af variable, som findes i tabellen dannet i afsnit 2.4, laves nye variable som input til modellen. Det kan eksempelvis være antallet af spørgsmål i en quiz den studerende har besvaret korrekt. Disse variable vil blive beskrevet nærmere i tabel 2.
Variabel Beskrivelse
quiz_question_frac_answeared Denne variabel beskriver hvor stor en andel af spørgsmålene i en quiz, som den studerende har besvaret. Det skal
bemærkes, at den studerende har muligheden for at svare flere gange på samme spørgsmål. Derfor kan ratioen overstige 1
quiz_questions_frac_answeared_correct Denne variabel beskriver, hvor stor en andel af spørgsmålene i en quiz den studerende har besvaret korrekt
questionaire_quetions_frac_answeared Denne variable beskriver hvor mange spørgsmål den studerende har besvare i et spørgeskema.
video_frac_seen Denne variable beskriver, hvor meget af videoen den studerende har set. Videoen kan også ses mere end én gang
flash_cards_frac_viewed Denne variable beskriver, hvor stor en andel af flashcardsene den studerende har vendt ud af det samlede antal flashcards i en kollektion
raw_text_sec_pr_charector Denne variable indikerer, hvor lang tid den studerende bruger på raw_text
video_flag Denne variable er en binær variabel og indikerer, om den studerende har set en video, som er lagt op af underviseren
assignment_flag Denne variable er en binær variabel og indikerer, om den studerende har afleveret en aflevering
flashcard_flag Denne variable er en binær variabel og indikerer, om den studerende har vendt et flashcard
questionaire_flag Denne variable er en binær variabel og indikerer, om den studerende har svaret på et evalueringsspørgsmål
quiz_flag Denne variable er en binær variabel og
indikerer, om den studerende har svaret på et quiz spørgsmål
raw_text_info_flag Denne variable er en binær variabel og indikerer, om den studerende har læst raw_text
external_link_flag Denne variable er en binær variabel og indikerer, om den studerende har været inde på linket, som underviseren har inkluderet i sin undervisningen
interactive_link_flag Denne variable er en binær variabel og indikerer, om den studerende har brugt et geogebra link
profile_pic_flag Denne variable er en binær variabel og indikerer, om den studerende har et billede på sin bruger inde på Learnu platformen
questionaire_sentiment Denne variable indikerer, om den studerendes evaluering er positiv eller negativ
dropout_before_cutoff_date_ratio Denne variable beskriver andelen af fag, som den studerende er frafaldet inden skæringsdatoen2
dropouts Dette er en binær variable, som
indikerer, om eleven er frafaldet et kursus indenfor forecastintervallet3, men efter skæringsdatoen
Tabel 2: Beskrivelse af definerede variable
Sentiment analysen af questionaire/evalueringer er taget med som variabel,questio- naire_sentiment. Denne kan fungere som trivselsindikator. Et negativt sentiment kan indikere, at den studerende ikke trives, hvilket kan resultere i, at frafaldssandsyn- ligheden stiger. Omvendt kan et positivt sentiment indikere det modsatte. Sentiment analyse er en under disciplin af Natural Language Processing også kaldet NLP [2].
En overordnet teoretisk gennemgang af sentiment analyse vil blive udledt i afsnit 3.1.
Data aggregeres på uge niveau, da man må forvente, at der er aktivitet på ugebasis.
I gymnasiet bliver undervisningen tilrettelagt på ugeniveau, hvilket er baggrunden for denne beslutning.
Inden aggregering vælges et antalaktivitetsuger, der benyttes som skæringsdato. Det er den dato, hvortil man gerne vil se aktiviteten for den studerende. Dertil vælges et antalforecastuger.forecastuger sættes til, hvor lang tid ude i fremtiden man vil præ- diktere et frafald. Afsnit 4.1.1 vil indeholde en detaljeret forklaring afaktivitetsuger ogforecastuger.
2.6 Dataudforskning
I dette afsnit vil data blive visualiseret. Der vil være et overblik over hvilke typer af aktiviteter, som udgør størstedelen af datasættet. Derudover vil der være et overblik over hvor stor en andel af de studerende, som ender med et frafald.
Kvaliteten af en model afhænger direkte af datasættet, som modellen trænes på. Det er derfor et krav, at der kun bruges repræsentativt data. I samarbejde med Edaptio fravælges dele af datasættet, som ikke er repræsentativt for de studerendes adfærd.
2Skæringsdato bliver beskrevet under tabellen
3Forecastuger bliver beskrevet under tabellen
Eksempler på databeskæring er:
• Data før juni 2018 er skåret fra, da der er en masse mangler i data før juni 2018, som ville påvirke prædiktionen i en misvisende retning.
• Derudover vælges alle følgende institution_id,
{314297,111647,838375,114873,87090,817744}, da alle disse er gymnasielle uddannesler.
• Ud af alle de ovenstående institutioner fravælges {87090,817744}, da de ikke rapporterer frafald på deres studerende.
• Desuden indeholder datasættet aktiviteter på undervisere og administrations- medarbejdere. Disse fjernes, da hverken undervisere eller administrationsme- darbejdere kan frafalde et kursus.
Figur 1 giver et overblik over aktivitetsfordelingen i datasættet. Det ses af figur 1, at
Figur 1: Aktivitesfordeling
aktivitetstyperne media, raw_text, quiz,assignment og external_link udgør størstedelen af aktiviterne. Desuden ses det, at media, altså videoer, er den mest forekommende aktivitet i datasættet.
Det ses af figur 2, at størstedelen af de studerende ikke frafalder deres kurser. Sam- let set frafalder 8817 studerende fra et kurses, hvor 26460 elever gennemfører. Det svarer til, at omkring 25% af alle studerende frafalder deres kurser. Det er vigtigt at bemærke, at det ikke er uddannelsen, den studerende frafalder, men derimod et enkelt kursus. Med andre ord kan en studerende godt frafalde et kursus, men stadig
Figur 2: Fordeling af frafald og ikke-frafald i Edaptios data
2.7 Håndtering af uafhængighed
Det kan potentielt være bekymrende, at de samme studerende kan indgå i datasættet med forskellige kurser, som uafhængige observationer. Dette er bekymrende, da et frafald fra et kursus kan påvirke sandsynligheden for frafald i et andet kursus. Hvis dette er tilfældet, vil der være afhængighed mellem rækkerne i datasættet.
Figur 3: Fordelingen af studerende på antal kurser
Figur 3 viser fordelingen af, hvor mange kurser de studerende tager. Figuren inklu- derer kun studerende, der tager færre eller præcist 5 kurser. Det svarer til 89.57%
af alle studerende i datasættet.
Det ses af figur 3, at 6329 studerende kun har ét kursus, hvilket er 51.92% af de studerende. Dermed vil 48.08% af de studerende tage flere end to kurser, hvorfor
der vil være mulighed for afhængighed.
Variablen dropout_before_cutoff_date_ratio, som beskrevet i afsnit 2, an- giver andelen af fag, som den studerende er frafaldet inden skæringsdatoen. Ved inddragelse af denne variabel tages der højde for afhængigheden mellem kurser, en studerende tager. Dette vil i nogen grad håndtere afhængigheden mellem rækkerne i datasættet.
I dette afsnit var der en gennemgang af, hvordan data blev håndteret. I kapitel vil der være en gennemgang af teorien, som bruges i denne rapport.
3 Teori
I dette kapitel vil der være en gennemgang af den teoretiske baggrund for rapporten.
I afsnit 3.1 vil der være en overordnet gennemgang af sentiment analyse teorien. I Afsnit 3.2 gennemgås teorien for, hvordan performance for Machine Learning mo- dellen måles. Yderligere bliver det beskrevet, hvordan datasættet skal splittes op i trænings- og testdatasæt. Afsnit 3.3 gennemgår teorien for logistisk regression. Her- efter gennemgås teorien for Random Forest i afsnit 3.4. XGboost teorien vil blive beskrevet i afsnit 3.5, hvor teorien for Neuralt Netværk vil blive gennemgået i af- snit 3.6. Afslutningsvis vil der være en gennemgang af stacked Machine Learning i afsnit 3.7.
3.1 Sentiment analyse
Sentiment analyse er et underemne til Natural Language Processing (NLP), hvor en algoritme trænes på en række teksteksempler til at kunne klassificere, om en given tekst er positivt eller negativt ladet. Det kan eksempelvis være en filmanmeldelse eller en evaluering af undervisningen i et kursus.
Den primære kilde i dette afsnit er [2].
3.1.1 Bag-Of-Words
For at en computer kan læse en tekst, skal teksten laves om til numeriske værdier.
Dette kaldes også for "feature extraction"eller "text embedding". Det kaldes for
"feature extraction", da hvert unikke ord i teksten bruges som en variabel.
En standard metode til "feature extraction"er "Bag-Of-Words"(BoW) modellen.
Ideen bag BoW er:
1. Lav en liste over alle unikke ord/tokens som indgår i teksterne/dokumenterne.
Dette kaldes også for "tokenize".
2. Der konstrueres en vektor, som indeholder frekvensen af ordene i teksten for hver tekst/dokument, altså hvor ofte hvert ord forekommer i teksten/doku- mentet.
Ved tilføjelse af flere tekster vil antallet af unikke ord stige. Dette medfører, at antallet af variable stiger. For at undgå en alt for stor stigning i antallet af variable, kan man gøre følgende:
• Fjerne stopord. Stopord er ord, som ikke kan bruges til at skelne mellem unikke tekster, men bruges, så sætningen hænger sammen. Det kan eksempelvis være
"er", "den", "de", "et", "med".
• Fjerne tegnsætning som punktum og komma.
• Ændre alle ord med stort bogstav til udelukkende at indeholde små bogstaver.
• Omskrive alle ord til sin grundform. Dette kaldes også "lemmatization".
• Fjerne slutbøjningen af ordet. Dette kaldes at "stemme"ordene. Eksempelvis bør man ændre "lege"til "leg".
De ovenstående punkter kaldes for "preprocessing", altså man transformerer data så de nemmere kan benyttes ved feature extraction.
3.1.2 N-grams
BoW kaldes for "1-gram/"unigram", altså man deler teksten i enkelte ord. En anden tilgang er at sammensætte flere ord, hvilket danner flere variable, som kan øge forståelsen af dokumentets kontekst. Med udgangspunkt i følgende sætning, "Det er en dejlig dag", kan følgende eksempler for en unigram og bigram/2-gram op stilles:
• Unigram:
("det", "er", "en", "dejlig", "dag")
• Bigram:
("det er", "er en", "en dejlig", "dejlig dag")
Det er værd at bemærke, at mellemrum bliver i teksten. Dette bruges til at kunne adskille ord/features i unigram ligeså vel som andre N-gram.
3.1.3 Term Frequency - Inverse Document Frequency (TF-IDF)
Ord som forekommer oftest i en tekst, vil have en højere frekvens uden nødvendigvis at bidrage med information til teksten. For at undgå at disse ord dominerer for meget, kan man bruge "Term Frequency- "Inverse Document Frequency"(TF-IDF).
Denne tilgang kan opstilles i to steps, i TF og IDF:
1. TF bruges til at finde frekvensen af ord i et dokument.
2. IDF bruges til at finde unikke ord, som karakteriserer hvert dokument. De unikke ord bruges til at adskille dokumenterne.
Generelt set handler det om, at hvis en variabel optræder hyppigere i et dokument, så er denne variabel god til at klassificere dette dokument.
3.1.4 Afinn pakken
I denne opgave er Pythons "Afinn"pakke brugt til at lave en sentiment analyse. Det er en prætrænet model, som giver noget tekst en positiv eller negativ score. Pakken er lavet af Finn Årup Nielsen, som selv har lavet en liste af ord og vurderet dem til at være enten positivt eller negativt ladet. Han har givet dem scoren mellem -5 og 5 [3]. En score mellem [-5, 0[ betyder, at ordet er negativt. Scoren af de forskellige ord i en sætning bliver summeret. Hvis et ord får scoren5og et andet ord får scoren−2, så vil den samlede score være 3, som betyder, at sætningen har et positivt sentiment.
Finn lavede pakken i 2009, som skulle bruges til at vurdere virksomheders omdømme ved brug af tweets fra Twitter4. Mere om Afinn pakken kan findes på følgende link https://pypi.org/project/afinn/.
3.2 Optimal model performance
I dette afsnit vil der gives en beskrivelse af, hvordan datasættet klargøres til mo- dellerne i rapporten. Afsnittet vil derudover give en forklaring af, hvorfor denne datahåndtering er nødvendig. Afsnittet vil omtale grundlæggende problematikker ved måling af performance for modeller. Håndtering af disse problematikker vil ef- terfølgende forklares. Desuden vil [4] i dette afsnit, benyttes som den primære kilde.
3.2.1 Trænings- og testdatasæt
I denne rapport vil hver model trænes på et træningsdatasæt, som består af 80% af det samlede datasæt. De 80% er tilfældigt udtrukkede observationer fra det samlede datasæt. De resterende 20% af datasættet anvendes som testdatasæt. Alle resultater fra modellerne er beregnet på testdatasættet. Denne opdeling af datasættet er vigtig, da modellens performance skal vurderes på et datasæt, som den ikke har set før.
Edaptio vil gerne prædiktere, om en studerende står til at være et frafald baseret på ny observeret data. Det er derfor vigtigt for Edaptio at vide, at modellen er generaliserbar og derfor kan bruges på ny data.
For at teste modellens performance i løbet af træningsfasen, kan træningsdatasættet yderligere splittes op. 80% af træningsdatasættet bruges til at træne modellen og
4Link: http://www2.imm.dtu.dk/pubdb/edoc/imm6975.pdf
de sidste 20% af træningsdatasættet benyttes til at validere modellens performance.
Derfor hedder den sidste del af datasættet valideringsdatasæt.
3.2.2 Overfitting
En model er overfittet, hvis dens loss på træningsdatasættet falder, uden at loss falder på valideringsdatasættet/testdatasættet. Loss-funktionen kan eksempelvis lig- ning () i afsnit . Det ønskede mål er at have en model, som er generaliserbar. Generelt forekommer overfitting, fordi modellen fitter koefficienter, der er datasæt specifikke, som man gerne vil undgå. Der er flere måder at undgå overfitting på, én løsning er regularisering af modellen.
3.2.3 Regularisering
For mange variable i en model kan lede til overfitting, da det øger modellens kom- pleksitet. Det ønskes derfor at kontrollere variable, som ikke har indflydelse på per- formance. Der er flere måder at regularisere på. Et eksempel på regularisering er at tilføje et L1 strafled til en objektfunktion, som forklares nærmere i afsnit 3.3.1.1.
Den optimale regulariseringsmetode afhænger af datastrukturen samt formålet for modellen. Regularisering er ofte specifikt til den enkelte model. De relevante regu- lariseringsmetoder for hver model, som benyttes i denne rapport, beskrives i deres respektive teori afsnit.
3.2.4 Hyperparametre
For hver model bruges flere forskellige hyperparametre, som beskriver hvilken proces modellen trænes efter. Et eksempel på en hyperparameter er valget af, hvor dybe klassifikationstrærne i Random Forest må være. Disse er ikke parametre, som mo- dellen selv er i stand at optimere. Som det nævnes i afsnit 3.2.6, findes de optimale parametre i denne rapport ved brug af gridsearch.
3.2.5 Cross-validation
Cross-validation er en metode, som sikrer, at modellen bliver genaraliserbar. Tanken bag cross-validation er, at opdele træningsdatasættet i mindre dele. Modellen trænes på en del af træningsdatasættet og valideres på resten af træningsdatasættet. Meto- denK-fold giver et godt indblik i princippet bag cross-validation. K-fold går ud på, at man splitter sit datasæt op i K lige store dele. Man vil fitte sin model5 på K-1 dele af datasættet. Dette anses som træningsdatasættet. Den sidste del vil bruges som valideringsdatasæt til at beregne performance. Pointen er, at hele datasættet skal bruges som både trænings- og valideringsdatasæt for at finde en generaliserbar
5Her har man bestemt hyperparameterne og model typen på forhånd.
model. K-fold resulterer i en performance, som er beregnet ved at tage et gennem- snit af de K modellers performance. Et større K vil lede til mindre usikkerhed i modellens performance på ny data. Det ekstreme eksempel er at have K = n, her vil hver del, som man deler datasættet op i, indeholde en enkelt observation. Dette vil give en meget præcis performance for modellen på ny data, men det vil være beregningstungt. Cross-validation bruges i gridsearch, som bliver beskrevet i næste afsnit.
3.2.6 Gridsearch
I gridsearch vælges en række værdier for hver hyperparameter, som man gerne vil teste for i en given model. Dette kan eksempelvis være hyperparametre tilhørende en Random Forest model. Alle kombinationer af hyperparametre bliver gennemgået, hvorefter dén kombination, som optimerer en score, for eksempel AUC, vælges. For hver hyperparameter kombination bruges cross-validtion til at beregne scoren.
3.3 Logistisk Regression
De primære kilder i det følgende afsnit er [5] og [6].
Logistisk regression er en del af model-klassen af generaliserede lineære modeller.
I Logistisk regression vil den enkelte observations responsvariabel være binomial- fordelt. Den mest anvendte link funktion er logit funktionen. Logit funktionen er bygget på odds, som kan tage værdierne [0,∞], hvor log(odds(y)) = logit(y), som kan tage værdierne [0,1].
Det antages, at Y’erne er uafhængige og kun kan tage værdier 0 eller 1. I den- ne rapport har vi 2 udfald, den studerende kan enten frafalde eller ikke-frafalde et kursus.
X er en input design matrice, som består af aktivitetsdataen. Datasættet består af p beskrivende variable, hvorfor X vil have dimensionerne n×p. Den logistisk regressions model kan dermed opstilles.
log(odds(Y = 1|X =x))
= log
P(Y = 1|X =x) P(Y = 0|X =x)
= log
P(Y = 1|X =x) 1−P(Y = 1|X =x)
=logit(Y)
=β0+β>x
(1)
Hvorβ>= (β1, β2, . . . , βp)> for p forskellige variable.
Sandsynligheden for hvert udfald kan isoleres i ligning (1) til P(Y = 1|X =x) = exp (β0+β>x)
1 + exp (β0 +β>x) P(Y = 0|X =x) = 1
1 + exp (β0 +β>x)
I logistisk regression er variablernes koefficienter estimeret ved Maximum Likelihood Estimation (MLE). Konceptet i MLE er at tilpasse hver koefficient, så det obser- verede datasæt har den højest mulige likelihood for at forekomme. Det vil sige, at MLE finder de koefficienter, som producerer estimater, der er tættest på de faktiske observationer.
Likelihood funktionen for observationer, hver med en binomialfordeling, kan opstilles for observationer(xi, yi), i= 1, . . . , n
L(x;β)
=
n
Y
i=1
P(Y =yi|X =xi)
=
n
Y
i=1
exp (β0+β>xi)yi 1 + exp (β0+β>xi) Den tilhørende Log-likelihoodfunktion bliver
ll(x;β) =
n
X
i=1
yi(β0+β>xi)−log(1 + exp (β0+β>xi))
(2) Ofte anvendes Log-likelihooden, ligning (2), da den er nemmere at optimere. Opti- meringsproblemet er, at man skal maksimere likelihood funktionen med hensyn til alleβi, hvor i= 0, . . .p. Denne optimering findes numerisk, hvor forskellige optime- ringsalgoritmer kan bruges. Optimeringsalgoritmerne er ikke fokus for denne rapport og bliver dermed ikke forklaret nærmere.
For mange variable kan medføre at den logistiske regression overfittes. For at und- gå dette problem kan de regulariserede versioner benyttes. Dette leder os til næste afsnit.
3.3.1 Regulariseret Logistisk Regression
Regulariseret logistisk regression ændrer optimeringsproblemet, set i ligning (2), ved at tilføje et strafled til objektfunktionen. Den ene del i objektfunktionen kontrollerer fit af data, hvor strafleddet kontrollerer antallet af variable. De to mest anvendte regulariserede modeller er Lasso og Ridge regression.
3.3.1.1 Lasso Regularisering (L1)
Lasso regression vil medføre, at koefficienterne tilhørende de mindst væsenlige vari- able sættes til 0. Det sker ved at indføre et strafled, −λ∗Pp
j=1|βj|, i ligning (2).
Maksimeringsproblemet kommer til at se ud som følgende:
( ˆβ0,β) =ˆ argmax
β0,β
n
X
i=1
(yi(β0+β>xi)−log(1 + exp (β0+β>xi))−λ∗
p
X
i=j
|βj|)
!
(3) λ er en vægtningsparameter for Lasso regulariseringens strafled, som bruges til at styre hvor kraftig regulariseringen skal være. Større værdier afλmedfører, at straffen bliver større. Numerisk store værdier af β’erne straffes, for at de samlet set holder sig i ro. Dette resulterer i, at de mindst betydningsfulde β’er forsvinder.
Generelt har Lasso regression tendens til at give de bedste resultater ved data, hvor kun få variable beskriver responsvariablen.
3.3.1.2 Ridge Regularisering (L2)
Den eneste forskel på Ridge og Lasso regression er strafleddet. Maksimeringsproble- met for Ridge regression kommer til at se ud på følgende måde:
( ˆβ0,β) =ˆ argmax
β0,β n
X
i=1
(yi(β0+β>xi)−log(1 + exp (β0+β>xi))−λ∗
p
X
i=j
βj2)
!
(4) Den største forskel mellem de to regulariseringsmetoder er, at for ikke væsentlige variable vil Ridge regression resultere i numerisk små koefficienter.
Ridge vil modsat Lasso regression have tendens til at give et bedre resultat, hvis flere variable er nødvendige for at beskrive responsvariablen.
3.3.2 Hyperparametre beskrivelse
Hyperparameter Beskrivelse
penalty Type af regularisering tilføjet til maksimum likeli- hood funktionen
C = λ, vægten for strafledet tilføjet til objektfunk- tionen
class_weight Vægtning af klassifikations typerne for trænings- data
random_state Fastlåser tilfældighedsalgoritmen
Tabel 3: Beskrivelse af Hyperparametre for Logistisk Regression
Udvælgelsen af hyperparametre samt implementation af funktionen beskrives nær- mere i afsnit 4.2.
Mere information kan findes på følgende link om Logistisk regressions hyperpara- metre
I dette afsnit blev teorien bag logistiske regressionsmodeller gennemgået. I næste afsnit vil der være en gennemgang af Random Forest algoritmen.
3.4 Random Forest
Den primære kilde til dette afsnit er [5]. Random Forest modellen er en supervised klassifikationsmetode, der er baseret på klassifikationstræer. Hvert klassifikationstræ dannes ved bootstrapping og aggregeres til én samlet model. Vi vil i dette afsnit først gennemgå alle delkomponenter anvendt i Random Forest efterfulgt af Random Forest algoritmen.
I næste afsnit vil teorien for klassifikationstræer blive gennemgået.
3.4.1 Klassifikationstræ
Den generelle struktur for et klassifikationstræ bliver vist i figur 4. Alle observatio- ner vil gå igennem et antaldecision nodes. Hverdecision node vil opdele datasættet baseret på et threshold for en bestemt variabel. Alle observationer vil starte med at gå igennem den første decision node, kaldet root node. Observationerne vil opdeles efter deres værdi i forhold til thresholdet. Desuden vil bbservationerne gå igennem hverdecision node sekventielt i træet, indtil den ønskede renhed er opnået. Der vil være en detaljeret forklaring af noderenhed i afsnit 3.4.1.1. Når en node har opnået den ønskede renhed, vil den blive til enleaf node.
For hver decicion node, der er i træet, tildeles hver observation en region givet et threshold.
R1(j, s) ={X|Xj < s}
R2(j, s) ={X|Xj ≥s}
Her erXdatasættet med observationer, Xj er en vektor med observationernes vær- dier for den j’te variabel ogs er et threshold for den j’te variabel.
Man vil for allep variable, X1, . . . , Xp, finde det threshold, s, for den j’te variabel, som giver den laveste RSS (Residual Sum of Squares). Denne splitting metode genta- ges for klassifikationstræet med éndecision node ad gangen, indtil et stop kriterium er nået.
Figur 4: Strukturen for et klassifikationsstræ
RSS = X
i:xi∈R1(j,s)
(yi−yˆR1)2+ X
i:xi∈R2(j,s)
(yi −yˆR2)2
Hver observation i vil enten tildeles R1 eller R2. Observationer i R1 vil have én klassifikationsværdi og observationer iR2 vil have en anden klassifikationsværdi.
3.4.1.1 Renhed i Noder
Der findes flere målenheder for renhed i klasifikationstræets noder, hvor Gini og Cross-Entropy er de mest anvendte. Gini indexet måler urenhed som følgende:
G=
c=2
X
i=1
ˆ
pi(1−pˆi) (5)
Hvorpˆi er andelen af observationer, som er tildelt deni’te klasse i den givne node og c er antallet af unikke klasser. I denne rapport har vi at gøre med 2 klasser, hvorfor c = 2. Et Gini indeks regner urenheden for noden og et Gini indeks på 0 svarer til at noden er ren. Entropy regner urenhed ved brug af følgende formel:
Entropy=−
c=2
X
i=1
ˆ
pi∗log(ˆpi) (6)
Ligesom ved Gini indeks’et er pˆi andelen af observationer, som er tildelt den i’te klasse i den givne node og c er igen antal af unikke klasser. Her vil −pˆi ∗log(ˆpi) altid være større end nul. Da0≤pˆi ≤1vil log(ˆpi)<0. Hvis pˆi er tæt på 0 eller 1, vil både Gini og Entropy være tæt på 0, hvorfor Gini og Entropy stortset identiske.
Gini indexet og Entropy vil være størst, når hver af de 2 klasser udgør 50% af ob- servationerne i noden [7]6.
Et klassifikationstræ udvides med decicion nodes indtil et defineret stopkriterium er nået. Her kan flere forskellige stopkriterier vælges baseret på valget af hyperpa- rametre. Eksempler på hyperparametre, som vil stoppe klassifikationstræet i at lave flere decision nodes, er:
• Mængden af observationer i endecision node. Hvis endecision nodeindeholder færre eller er lig et antal af observationer, vil dennedecision node ikke splittes yderligere.
• Et loft på antallet af leaf nodes.
• Stigningen i renheden, som den næstedecision nodetilføjer, er under en fastsat værdi.
Når klassifikationstræet har nået sit stopkriterium, vil decision noden blive til en leaf node. For hver leaf node vil man finde klassen, som flest observationer tilhører.
Alle fremtidige observationer, der ender i denneleaf node, tildeles denne klasse.
3.4.1.2 Pruning
Dybe klassifikationstræer kan give meget præcise prædiktioner, men har en tendens til at overfitte.
Pruning kan bruges til at håndtere risikoen for overfitting ved dybe klassifikations- træer. Her vil pruning tilskære klassifikationstræet, så træet kun indholder de mest nødvendige noder. En populær metode til Pruning er "weakest link pruning". We- akest link pruning lægger sig tæt op ad Lasso regularisering, som er beskrevet i afsnit 3.3.1.1. Her vil strafleddet α∗ |T| lægges til loss funktionen, som skal mini- meres
|T|
X
j=1
X
i: xi∈Rj
(yi−yˆRj)2+λ∗ |T| (7)
j indikerer det j’teleaf node, hvor |T| er det totale antal leaf node i klassifikations- træet.Rj er en mængde af observationer, som er i den j’te leaf node.
λ parameteren gør det dyrere at have mange leaf nodes og størrelsen på λ vælges ved parameter tuning.
3.4.2 Bootstrapping
Bootstrapping vil lave m (m ≥ 1) datasæt, hver med n tilfældige udtrukket ob- servationer med tilbagelægning fra det oprindelige datasæt med n observationer.
6Eksempler på max og min af Gini indeks og Cross-Entropy findes i Appendix A
Figur 5 viser Bootstrapping udtrækning. Disse udtræk vil være en delmængde af det originale datasæt med samme fordeling og dermed samme varians [8].
Figur 5: Simpelt eksempel af Bootstrapping udtrækningsmetode
3.4.2.1 Out-Of-Bag (OOB)
Når bootstrapping genererer datasæt, vil der være nogle observationer fra det ori- ginale datasæt, som ikke kommer med i udtrækket med tilbagelægning. Observa- tionerne fra det originale datasæt, som ikke tages med i bootstrapping datasættet, kaldes Out-Of-Bag (OOB) observationer. Figur 5 illustrerer, hvordan nogle observa- tioner er i "Bootstrap Sample"og nogle observationer er "Out-Of-Bag Set".
Det er vist empirisk, at med stortn vil hvert Bootstrapping datasæt cirka indholde 2/3 af alle unikke observationer. Det vil sige, at i gennemsnit vil cirka 1/3 af alle unikke observationer være OOB i hver af dem Bootstrap datasæt.
3.4.3 Bagging
Bootstrap aggregering, også kaldet Bagging, vil danne et klassifikationstræ for hver af demdatasæt dannet ved brug af Bootstrapping. Bagging danner træer med højest mulig performance. Aggregering af de m klassifikationstræer, også kaldet "Bagging estimation", sker ved, at man for hver observation finder klassen, som flertallet af dem klassifikationstræer tillægger observationen.
Dybe træer vil have en høj præcision, som Bagging drager fordel af. Den høje præ- cision medfører høj varians og dermed risiko for overfitting. Siden træerne er dannet ud fra samme datasæt, vil de tilnærmelsesvis have samme varians.
For uafhængige og identiske fordelte stokastiske variable,Z1, . . . , Zm, gælder følgende
udtryk
V ar(Zj) = σ2j >
Pm
i=1V ar(Zi)
m =
Pm i σi2
m (8)
Her er venstresiden variansen for en enkelt stokastisk variabel, Zj, hvor højresiden er gennemsnittet for de m uafhængige identiske fordelte stokastiske variable. Al- le Zi, . . . Zm på højresiden har samme varians, som er det samme som variansen for Zj på venstresiden. Derfor er variansen for den enkelte stokastiske variabel, Zj, højere end gennemsnittet af varianserne for de m uafhængige stokastiske variable, Z1, . . . , Zm.
De dybe klassifikationstræer er ikke direkte uafhængige, hvorfor ligning (8) ikke hol- der direkte for klassifikationstræer. Det vil dog stadig gælde, at et gennemsnit af varianserne for de forskellige modeller vil være lavere end variansen for de enkelte modeller.
Der er indtil nu gennegået teorien, som skal bruges i Random Forest algoritmen. I næste afsnit vil Random Forest algoritmen blive gennemgået.
3.4.4 Random Forest algoritme
Random Forest metoden lægger sig tæt op ad Bagging. Random Forest genererer mange klassifikationstræer med Bootstrapping metoden og finder ved brug af disse træer en OOB error af observationerne.
OOB error for Random Forest kan ses som en form for cross-validation og kan for eksempel bruges til at finde ud af, hvornår træning af Random Forest kan stoppe.
Man kan eksemplevis benytte OOB error til at vurdere, hvornår ekstra træer ik- ke mindsker modellens OOB error, hvorfor træningen bør stoppes. Random Forest reducerer variansen for klassifikationen yderligere, sammenlinget med Bagging, ved at begrænse brugen af variable. For hver decision node i klassifikationstræet vil p0 ud af allep mulige variable blive udvalgt. Størrelsen på p0 skal optimeres, hvor den generelle regel siger p0 =√
p. Desuden vælges p0 ofte på baggrund af gridsearch.
Hvis p0 = p vil Random Forest tilsvare Bagging. Fordelen ved at have p0 < p er, at enkelte variable ikke har mulighed for at dominere alle klassifikationstræerne.
Empirisk vil de mest betydningsfulde variable bruges som split i root noden. Root noden er den mest betydningsfulde node, da den kan påvirke flest observationer.
I Random Forest kan den samme variabel ikke splitte alle root nodes, fordi hver variabel i alleroot nodes udtrækkes tilfældigt. Denne variation i variable forhindrer, at klassifikationstræerne bliver ens. Man vil ved højt korrellerede variable sætte p0 til at være lille og dermed sikre lav korrelation mellem klassifikationstræerne.
Prædiktionen dannet af Random Forest tilsvare Bagging estimation. De mange klas- sifikationstræer, som dannes i Random Forest, vil gøre det svært at forstå variable-
nes påvirkning på klassifikationsmodellen. Dog kan variance importance bruges til at analysere variablenes vigtighed i modellens prædiktion. Her vil man sammenligne faldet i klassifikationsfejl for modellen skabt af grene med en bestemt variabel. Den- ne klassifikationsfejl sammenlignes med klassifikationsfejlen for modeller, som ikke indholder grenen med den bestemte variabel. Hver variables påvirkning af klassifika- tionen kan estimeres ved, at undersøge hvordan variablen påvirker klassifikationen.
Random Forest metoden opnår høj præcision samtidig med gode generaliserende egenskaber, da den høje varians er blevet mindsket.
Algoritme 1 Random Forest klassifikation 1. For i = 1 to m
(a) Udtræk et bootstrap datasæt
(b) Dan et "grådigt" klassifikationstræ ved
i. Vælg p0 variable tilfældigt fra datasættes p variable ii. Vælg den af dem variable med det bedste split iii. Opdeldecision node til to noder
(c) Gem det opstillede klassifikationstræ
2. Lav en prædiktion for en ny observation ved at finde den klasse, som flest af de m gemte klassifikationstræer prædiktere den nye observation til
Algoritme 1 gennemgår, hvordan en Random Forest model dannes i praksis. I trin 1 starter man i (a) med at lave en bootstrap sample. Derefter vil man i (b) konstru- ere et klassifikationstræ. I (c) gemmes det konstruerede klassifikationstræ. Denne process gentages m gange, hvor m er antallet klassifikationstræer fittet i Random Forest algoritmen. Aggregering af de m træer sker i trin 2.
I næste afsnit vil der være en gennemgang af hyperparametrene, som bruges i Ran- dom Forest.
3.4.5 Hyperparametre beskrivelse
Hyperarameter Beskrivelse
max_depth Maksimalt antal niveauer i klassifikationstæet random_state Fastlåser tilfældighedsalgoritmen
bootstrap Indikator variabel for om bootstrapping skal bru- ges til at genere datasæt for alle klassifikationstræ- er
criterion Renhedsmål for modellen
max_features Antal variable som trækkes tilfældigt ud fra allep variable fra modellen
n_estimators Antal datasæt der dannes ud fra bootstrapping og dermed antal klassifikationstræer der fittes
class_weight Vægtning af klasifikationstyperne for træningsdata min_samples_split Minimum antal observationer, som skal være i en node, før den tages i betragtning til at blive til en decicion node
min_samples_leaf Minimum observationer, som skal være til stede i en node, før den kan omdannes til en leaf node max_leaf_nodes Maksimalt antal leaf nodes
min_impurity_decrease En node vil laves til endecicion node, hvis og kun hvis det vil mindske urenheden af klassifikations- træet mere eller lig denne parameterværdi
max_samples Hvis bootstrap er i brug vil denne variable beskrive antallet af observationer som trækkes med tilbage- lægning i bootstrap til at træne hvert klassifika- tionstræ
Tabel 4: Beskrivelse af Hyperparametre for Random Forest
Udvælgelsen af hyperparametre samt implementering af modellen beskrives nærmere i afsnit 4.3.
Mere information kan findes på følgende link om Random Forest hyperparametre I dette afsnit har der været en gennemgang af Random Forest teorien. I næste afsnit vil teorien for en anden træbaseret algoritme, XGboost, blive gennemgået.
3.5 XGboost
I dette afsnit vil der være en gennemgang af XGboost algoritmen. Bøgerne [6], [5]
og artiklen [9] er brugt til hele dette afsnit.
XGboost er en træbaseret supervised klassifikationsalgoritme, som også kan bruges til regression. "Extreme Gradient boosting" er udviklet af Tianqi Chen[9]. Som det også indgår i navnet, bruges boosting i XGboost algoritmen, som vil blive nærmere beskrevet i næste afsnit.
3.5.1 Boosting
Ligesom Bagging er Boosting en effektiv tilgang til at forbedre prædiktionen ved brug af flere klassifikationstræer. Desuden kan Boosting anvendes til forskellige sta- tistiske metoder indenfor regression eller klassifikation. Ideen med Boosting er at kombinere mange klassifikationstræer til én model, som har en bedre klassifikations- evne. Dét kaldes også for en ensemble model. En svag klassifikationsmodel er en model, som kun er marginalt bedre til at prædiktere end et tilfældigt gæt. Dette kaldes en weak learner. I Boosting algoritmer samles mange weak learners til én super learner. Denne super learner opnår bedre prædiktionsevne sammenlignet med de enkelte weak learners.
En af de mest populære Boosting algoritmer er Adaptive Boost (AdaBoost). Boosting forklares med AdaBoost som eksempel, da denne er den oprindlige Boosting algo- ritme. Med udgangspunkt i et binært klassifikationsproblem, som kan tage værdier Y ∈ {0,1}, kan en AdaBoost klassifikationsmodel opstilles. Givet et datasæt, X, vil klassifikationsmodellen,G(X), lave en prædiktion, Yˆ ∈ {0,1}. Fejlraten for træ- ningsdatasættet kan findes ved følgende formel
l = 1 n
n
X
i=1
I(yi 6=G(xi)) (9)
Hvor I er en indikator funktion, som er lig 1, når den prædikterede observation er forskellig fra den faktiske observation.
Modsat Bagging fittes klassifikationstræer sekventielt ved Boosting. Med andre ord fittes der ét træ ad gangen, hvorefter hvert træ bruger informationen fra det tidli- gere fittede træ til at lave en ny prædiktion. Boosting opnås ud fra M sekventielle definerede træerG1, . . . , GM på følgende måde
G(x) =
M
X
i=1
αiGi(x) (10)
Hvorα1, α2, . . . , αM er beregnet i AdaBoost algoritmen og er vægtningen for de en- kelte klassifikationstræer. Vægten skal være højest for de træer, som har den bedste prædiktionsevne. Med andre ord får bedre træer størst indflydelse på den samle- de model. Yderligere modificeres træningsdatasættet ved, at der tillægges en vægt w1, w2, . . . wn til hver observation (xi, yi), i = 1,2, . . . n. Hver observation får en initial vægt på 1n. For hver iteration vil vægten på de misklassificerede observationer stige. Sagt med andre ord vil observationer, som er sværere at klassificere rigtigt, få større betydning. Dette medfører, at de efterfølgende klassifikationstræer tvinges til at fokusere på de observationer, som blev misklassificeret af tidligere klassifikations- træer.
Den sekventielle fremgangsmåde til at danne klassifikationstræer i AdaBoost er gen- nemgående for Boosting algoritmer.
I det efterfølgende afsnit vil der være en beskrivelse af Gradient Boosting, som bruges til XGboost.
3.5.2 Gradient Boosting
Gradient Boosting er, som AdaBoost, en model, hvor mange weak learners lægges sammen til én model. Det er dermed også en additiv model.
Ved brug af gradient boosting til klassifikation skabes træer, hvor alleleaf nodes er log(odds) for "succes" og hvor log er den naturlige logaritme. Træet skal bruges til at klassificere en observation, hvorfor de enkelte leaf nodes tilbageregnes til sand- synligheder. Dette gøres ved brug af logistisk funktion. Sluttræet bliver summen af alle de iterativt konstruerede træer.
ˆ
yi =φ(xi) =
M
X
j=1
fj(xi), fj ∈ F (11)
Lt =
n
X
i=1
l
yi,yˆ(t−1)i +ft(xi)
(12) HvorF er rummet, som indeholder alle træerne og ft er modellen i den t´te itera- tion. xi er den i´te inputvektor til modellen fj og yi er den i´te response variabel.
Ligning (11) er modellen, hvor alleiiterativt konstruerede træer summeres og laver en prædiktion. Ligning (12) er objektfunktionen, som skal minimeres ved tilføjelse af et nyt træ. Nye træer vil blive konstrueret indtil (12) er minimeret.
En gradient boosting klassifikationsmodel dannes i praksis ved brug af følgende algoritme, fra side 387 i [6]. Bemærk, at der kun bruges K = 2 klasser i denne sammenhæng, da der i denne rapport er at gøre med en binær klassifikation:
