Practical Feature Reduction Using SVD in R

I’m refreshing my data mining skills and thought it could be fun to do the Digit Recognizer competition over at Kaggle. Each datapoint in that dataset is an image of a hand drawn digit from zero to nine. Our task is to determine which digit each of them represent. The problem is that each pixel represents a feature making it a huge number of them. Machine learning algorithms really don’t like large feature spaces due to the risk of overfitting. I was going to apply some sort of feature reduction technique, and I remembered SVD being awesome for this type of jobs.

To my surprise the resources I found online didn’t really bring the task down to earth. I spent some time to “get it” again and thought it could be a worthy blog post. Remember, this isn’t meant to be rigorous in any way. It’s just an attempt at making a practical example. If you’re interested in understanding how SVD works I’d suggest any of the other brilliant resources out there.

I’ll be assuming some familiarity with matrix notation and R code. If you need a brush up on matrix notation I’ve written a post about it before.

Alright, lets get started. We’ve got a dataset \(X \in \mathbb{R}^{m\times n}\) and labels \(\vec{y} \in \{0,1,…,9\}^{m}\) where \(m\) is the number of datapoints and \(n\) is the number of features. The datapoints are typically denoted as lower case \(\vec{x} \in \mathbb{R}^{n}\). For the database nuts, you can think of \(X\) as a table of \(m\) rows and \(n\) features where \(\vec{x}\) is a row. Each datapoint \(\vec{x}\) has a corresponding label \(y\) taking a value 0 to 9. These values can be found in \(\vec{y}\). What we want to do is to make a good classifier \(f\) which learns the patterns of \(X\) such that when we give it a new datapoint \(\vec{z} \in \mathbb{R}^{n}\) with unknown label we can estimated (i.e., guess) the value \(\hat{y} \in \{0,1,…,9\}\).

What we’ve got then is a classifier which does the following:

\(f(\vec{z}; X) = \hat{y}\)

Problem: There are too many features. We need to reduce \(n\) somehow. Singular value decomposition (SVD) can help us out. You can think of what it does as transforming the features of our datapoints into a new feature set with increasing importance. This last point is important because it means we can truncate the less important features. Actually this is how many lossy image compression algorithms work since you are removing data, while retaining as much of the information as possible. What you get from performing SVD on your dataset is two matrices \(U \in \mathbb{R}^{m\times n}\) and \(V \in \mathbb{R}^{n\times n}\) in addition to a vector \(\vec{d} \in \mathbb{R}^{n}\). Typically this last vector gets represented as a diagonal matrix \(D = \mathrm{diag}(\vec{d}) \in \mathbb{R}^{n\times n}\), meaning each element of \(\vec{d}\) is in the top-left to bottom-right diagonal of \(D\) and the rest of the entries are zero. These three matrices can losslessly be reverted to your initial dataset \(X\) using the following relationship:

\(X = UDV^\mathrm{T}\).

What is cool about this is that we can remove columns from the right of \(U\) and \(V\), as well as the bottom-right column-row pairs of \(D\), and still maintain a good approximation of \(X\). One important caveat: \(X\) must be centered. The average of each feature must be zero. You do this by subtracting the average feature value from each respective element of each datapoint. I’m not going to represent this in matrix notation, but you can see how to go about doing this in the R code further below.

X = UDV'

Image is a modified version of one found at semanticquery.com

In the above image, the gray part is what we retain. Also, don’t get confused, the \(V\) is transposed thus the part which is retained looks like a rows in the image.

Alright, let’s give these smaller matrices names:

\(\hat{X} = U_rD_rV_r^\mathrm{T}\)

Here \(\hat{X} \in \mathbb{R}^{m\times n}\) is an approximate version of our original dataset \(X\), while the subscript \(r\) indicates that the matrix has “reduced” size as described above. What we got now is \(U_r \in \mathbb{R}^{m\times k}\), \(D_r = \mathrm{diag}(d) \in \mathbb{R}^{k\times k}\) and \(V_r \in \mathbb{R}^{k\times n}\) where \(k \in \{1,\dots,n\}\), i.e., we are planning to retaining \(k\) features from the original \(n\) features.

Alright, all of this seem fine and dandy, but where is the new dataset we are going plug into our classifier. I asked myself the same question. Without fail, every post I found skipped this part, until I found this answer at stats.stackexchange.com. The answer is to use the \(U_rD_r\), called the principle components or “score”. What we end up with is

\(X_r = U_rD_r\)

Again, I use the subscript \(r\) to indicate a “reduced” matrix, in this case we now have \(X_r \in \mathbb{R}^{m\times k}\). That’s it! Case closed? No, not entirely. The following won’t work:

\(f(\vec{z}; X_r) = \hat{y}\)

This is because your unlabeled \(\vec{z} \in \mathbb{R}^{n}\) must have the same number of features as \(X_r\). It very much doesn’t. \(X_r\) has \(k\) features, while our unlabeled datapoint \(\vec{z}\) still has \(n\) features. We need to transform the unlabeled datapoints we want to classify. Let’s say we have a a bunch (\(l\)) of unlabeled datapoints in a dataset \(Z \in \mathbb{R}^{l\times n}\) then we can transform it using the \(V_r\) matrix as follows:

\(Z_r = ZV_r\)

If you’r streaming datapoints and need to do predictions one-by-one you can do the same as follows

\(z_r^\mathrm{T} = z^\mathrm{T}V_r\)

or the equivalent

\(z_r = V_r^\mathrm{T}z\)

Thus, we have what we need to do predictions with the feature reduced dataset:

\(f(\vec{z}_r; X_r) = \hat{y}\)

I did say we were doing this in R, and I’ll stick to this promise. The following outlines how to do it on dummy data.

Later I will follow up with a post on how to do it using the Digit Recognizer dataset from Kaggle.

Hvorfor jobbe i Affecto?


Ble intervjuet om hvordan det er å jobbe hos Affecto.
Her følger svarene mine.


André Andersen – BI-konsulent og tidligere TRP-er

André Andersen bor i Oslo, er 29 år og jobber som Business Intelligence Konsulent i Affecto. Han er èn av mange nyansatte som har deltatt i Talent Recruitment Program .

Navn: André Andersen
Alder: 29
Jobber som: Business Intelligence konsulent

Det beste med jobben: – Å kombinere “tech” og “business”. Det passer veldig bra med min utdanning og mine interesser.

Andre har en solid utdannelse og har etter at han begynte i Affecto deltatt i talentutviklingsprogrammet (TRP) vårt for nyutdannede ansatte.

Hva slags utdannelse har du?

Jeg tok en femårig siv.ing. i industriell økonomi og teknologiledelse på NTNU. Hovedprofilen min var anvendt økonomi og optimering, og teknologifordypningen min var datateknikk og intelligente systemer. I fjerde klasse på Indøk studerte jeg ved UCSD i USA, og før NTNU studerte jeg en treårig bachelor i matematikk, informatikk og teknologi på UiO.

Hovedoppgaven min på Indøk handlet om automatisert aksjehandel ved hjelp av porteføljeoptimering, maskinlæring og evolusjonære algoritmer.

Hva gjorde at du valgte Affectos TRP program og hvordan opplevde du programmet?

Fra studietiden har jeg bygget en sterk interesse for intelligente systemer. I forretningsverdenen betyr det i praksis dataanalyse og data mining. Jeg så på det å jobbe hos Affecto som en gylden anledning til å komme nærmere på mye interessante data og kunne arbeide med praktiske utfordringer rundt datadrevet beslutningsstøtte. Affecto hadde også profilen jeg så etter i en arbeidsplass: Flat struktur, kunnskapsrikt og hyggelig miljø, villig til å prøve nye ting, fostring av engasjement, mange forskjellige kunder, relevant kursing, verdifull oppfølging, og mye mer.

TRP-programmet var et spesielt bra initiativ da det baserer seg på en fin miks mellom å lære kunsten å være en god konsulent, og passe på at man har grunnlaget man trenger både fagmessig og teknologisk. Man blir på ingen måte kastet ut på dypenden. Gjennom TRP og mentorordningen blir man gradvis forberedt og hjulpet på vei til å bli del av forretningsverden. Man blir utrustet med en verktøykasse og et nettverk som gjør én forberedt til å møte sin første kunde med riktig tyngde og støtte.

Hva innebærer det du jobber med og kan du gi noen eksempler??

Fagfeltet til Affecto som helhet heter Business Intelligence (BI). Her er målet å forvandle bedrifters rådata til nyttig informasjon og forretningsinnsikt. Bedrifter produserer fantastisk store mengder data, men uten riktig behandling skaper disse liten verdi, og kan faktisk koste mer enn nytten.

Jeg jobber i Insight & Integration-avdeling til Affecto. Her jobber vi i kjernen av problemdomenet til BI. Siden jeg startet i Affecto for litt over et år siden har jeg fått deltatt på utrolig mye givende arbeid. Jeg har arbeidet med prosjektplanlegging og -estimering, anbuds- og innsalgsarbeid, produkt- og løsningspresentasjoner, utvikling av løsninger i ett flust av verktøy – dette gjelder både “proof of concepts” og faktisk produksjonssystemer.
Videre har jeg stått for dokumentering av egne løsninger og eksterne løsninger, deltatt på kurs, holdt kurs, og holdt webinar. Jeg har også fått reist en del; spesielt til våre naboland gjennom TRP-ordningen, sørover til varmere strøk for kick-off, og nordover til en av våre kunder der.

Hvordan så forrige arbeidsuke ut for deg?

Mandag til onsdag jobbet jeg sammen med datavarehusavdelingen til hovedkunden min, en forretningsbank. Her jobbet jeg med en teknisk oppgave hvor jeg laget dataflyter for å sammenstille endringer på lånekontrakter fra flere kildesystem. Dette er hva man kaller dataintegrering, og handler om å gjøre data tilgjengelig for videre analyse.

Etter lunch på onsdag, dro jeg til min tidligere hovedkunde, en offentlig institusjon, her hadde vi akseptansemøte hvor vi gikk gjennom løsningen jeg produksjonssatte uken før – et system for prognoseføring og rapportering av interne og eksterne kostnader. Løsningen ble akseptert med kun ønske om kosmetiske forbedringer.

På torsdagen til fredag var jeg hos “forretning” hos min nåværende hovedkunden. Her gjorde vi analyse av forretningskrav, og jeg startet med å sette meg inn i logikken i eksisterende løsning som var implementert i et for meg nytt analyseverktøy. Målet er å konkretisere en midlertidige løsning for risikovurdering av lånekunder og gjøre den klar for generell bruk. Ellers, på fredag brukte jeg litt tid til å hjelpe HR med å forberede bedriftspresentasjon på NTNU.

Hva synes du er spennende og utfordrende med din jobb?

I alle oppdragene jeg har deltatt i har jeg arbeidet tett med forretning. Å avdekke behov, artikulere dem, estimere arbeidsmengde, og bygge forventninger står veldig sentralt. Dette er en givende prosess da man deltar både i defineringen av hva som skal lages og så få se disse tankene konkretisert og brukt i praksis.

Man skal kunne både beherske “tech” og “business” noe som passer veldig bra med min utdanning og mine interesser. Som konsulent i Affecto er det forventet at man skal ha et bredt forhold til teknologi. Det er fint om man er gode på spesifikke verktøy, og etterhvert vil man selvsagt tendere mot noen verktøy mer enn andre, men det er et mål i seg selv å ha en holdning om å være verktøy-agnostisk.

Man er først og fremst førsteklasses konsulenter med medmenneskelige og analytiske evner, dernest fagfolk med konkrete verktøyerfaring. Dette gjør at man skal stadig være forberedt på å ta på seg nye utfordringer og være åpen for å raskt kunne sette seg inn i nye problemstillinger og teknologier. For meg ligger de mest spennende utfordringene i grensesnittet mellom forretning og teknologi; et område hvor Affecto har sin hovedgeskjeft.

Ser du noen trender innen ditt område?

Innen mitt område er den største trenden jeg ser at bedrifter stadig går fra å se på IT-investeringer som en ren kostnad til å se på det som en mulig inntektskilde. Det å kunne love bort bedre bunnlinje gjennom f.eks. økt omsetning, fremfor lavere IT-kostnader, gjør at forretning blir drivkraften til ønske om IT-investeringer fremfor IT-avdelingen selv. Og er det en ting som er fellesnevneren for vellykkede løsninger så er det støtte fra forretning.

Det som driver dette skiftet er tilgjengeligheten av moderne analyseverktøy og økt kunnskap innen dataanalyse. Gjennom data mining-metoder, som prediktiv analyse på kundedata, starter bedrifter nå å ta i bruk tilpassede system for semi- og helautomatisert beslutningsstøtte. Eksempel på dette er system som automatisk godkjenner lån, eller system som automatisk anbefaler kunden produkt basert på deres egne og andres preferanser, eller system som automatisk varsler en kundebehandler om misfornøyde kunder gjennom tekstlig sentimentanalyse.

Verktøy som Tableau har gjort utforsking og visualisering av data nærmest til en lek, gøy som en lek i alle fall. Man kan nå sitte sammen med forretning og se på dataene, og gjøre oppdateringer like fort som man kommer på muligheten: “Analytics at the speed of thought.”

Juleøltesten 2014

Resultatene – kort og godt

Tradisjonen tro er årets juleøltest gjennomført, og analyseresultatene er kommet inn. For de utålmodige kan vi annonsere med en gang at Nøgene Ø kom på topp i år også. Nøgene Øs God Jul og Underlig Jul troner på henholdsvis første og andre plass, med Kinn Julefred på en hårfin tredjeplass. Verst ut kom Tuborg Julebrygg, som med et “uhell” kom med i rangeringen. Den har visstnok fått “brygge” nederst i kjøleskapet siden juleøltesten 2012.

Resultatoversikt for juleøltesten 2014.

Resultatoversikt for juleøltesten 2014. Justerte poengsummer gjør at total kan avvike.

Vinnernes bryggerier skal selv få beskrive ølen sin:

Førsteplass: Nøgene Ø God Jul. A dark ale brewed specially for the Christmas season, with a rich, complex taste of caramel. This is a strong, dark and rather sweet Christmas Beer – just the way we think a Christmas beer should be.

Andreplass: Nøgene Ø Underlig Jul. The name of this beer is “Peculiar Christmas” in english. This spiced Christmas ale is strange – and indeed a fusion beer. We have gathered inspiration from the Norwegian drink “gløgg”, and as such this is quite an uncompromising brew.

Tredjeplass: Kinn Julefred. I meir enn 1000 år har nordmenn bryggja øl til jul. Juleølet var festdrikk og sterkare enn ølet ein drakk ellers i året. Vårt juleøl er bryggja i denne tradisjonen og er eit fyldig og kraftig øl med god maltsmak. Julefred er bryggja spesielt med tanke på den tradisjonelle salta og tørka julematen, men høver og godt som sjelevarmar for ein frosen skrott.

Ønsker å takke verten og vertinnen, Helge og Marit, for deres innsats i å arrangere juleølsmaking atter et år. Det er ikke julestemning før smaksløkene bikker over, og skriker etter andre sanseinntrykk enn bekmørkt og overkrydret juleøl. Spesielt ønsker vi i juryen å takke vertinnen for hennes gjestmildhet og innsats som bartender, eller kanskje forskerspire(?), da juryens forhold til henne er nærmere den mellom forsøkskaniner og mad scientist.

Dem som ønsker et nærmere innblikk i hvordan vi kom fram til resultatene og er nysgjerrige på hva annet dataen kan fortelle om juleøla, og kanskje litt om jurymedlemmene selv, inviteres til å fortsette å lese.

Analysen – et dypdykk i ølla

Sist år ble analysen gjort i Excel, og resultatet finner du her. I år går vi grundigere og mer systematisk til verks. Vi har fått tak i en lisens til analyseverktøyet Tableau, noe som gjør dataanalyse til en lek.

Årets jury består av Helge Svendsen, Stian Skår (Krystad), Nikolai Skogstad, og André Andersen. Helge fronter instagramkontoen 365wines om vinkunsten, noe som muligens har farget vår tilnærming til juleøltestingen. Spesielt gjelder det poengsystemet vi har brukt som er basert på Robert Parkers poengsystem for vin. Poengsystemet har følgende delresultat:

  • Farge (med skum/head) gir opp til 5 poeng
  • Lukt gir opp til 15 poeng
  • Smak gir opp til 20 poeng
  • Helhet gir opp til 10 poeng

Poengene fra delresultatene pluss 50 grunnpoeng legges sammen og gir en skala fra 50 til 100 poeng. Dette følger det underliggende karaktersystemet i Amerikanske akademia.

Standardisering av poengene

Vi har digitalisert poengene og kan derfor gjøre en god del artig analyse. Først anerkjenner vi at minst to av oss ikke vet hva vi driver på med når det gjelder øltesting, og at poenggivingen spriker en god del. Dette har vi tatt hånd om ved å standardisere resultatene slik at jurymedlemmene har samme snitt og standardavvik. Dette er en fancy måte å si at vi får poengene til å kunne bedre sammenliknes. Hvis noen (*host* Nikolai) gir veldig sprikende og lave resultater blir de automatisk gjort mer konsentrert og hevet litt for å likne mer fellesresultatet. Både rådataen og de standardiserte resultatene finner du her. Delpoengene og endelig poengsum har blitt standardisert hver for seg, noe som gjør at endelig totalsum ikke nødvendigvis går opp.

Deskriptiv statistikk over jurymedlemmenes poenggivning.

Deskriptiv statistikk over jurymedlemmenes poenggivning.

Fra første tabellen over ser vi at rådataen til Helge og Stian begge har rimelig like standardavvik og gjennomsnitt, i motsetning til Nikolai og mine egen standardavvik som er ganske brede. Vi to har også henholdsvis ganske lav og høy gjennomsnitt. Det er kanskje ikke så rart at vi to virker mer urutinert i stemmegivningen i forhold til Helge som har erfaring innen vinkunsten og Stian som brygger eget øl. Pytt, pytt, vi gyver løs på oppgaven med hodet hevet likevel, og kompenserer våre mangler med å tvinge stemmene våre til å ha samme standardavvik og gjennomsnitt som de med peiling. Dette påvirker ikke Helge og Stians resultater så mye, men Nikolais og mine egne resultat blir normalisert.

Etter standardiseringen har vi følgende poengfordeling på sluttresultatene:

Fordeling av endelige poeng.

Fordeling av endelige poeng.

I all hovedsak gis det ikke mange poeng mellom 95 og 100, og vi virker svært så glad i å gi rundt 85 poeng. Fordelingen ser ikke akkurat ut som antatt normalfordeling, men det får være grenser på hvor statistisk korrekt vi skal være i en uformell juleøltest.

Poengfordelingen på hver av deltestene oppfører seg litt mer som forventet:

Fordeling av delpoeng.

Fordeling av delpoeng.

Her ser vi kanskje en tendens til normalfordeling. Siden vi summerer normalfordelinger er det å forvente at endelig poengsum bør være normalfordelt også, men akk nei; dette gjelder kun uavhengige normalfordelte variable, og senere vil vi se at dette på ingen måte er tilfellet. Lukter en øl godt er det stor sannsynlighet for at den også smaker godt. Mer om det senere.

Kanskje mest for jurymedlemmenes del så er de standardiserte poengsummene vi ga som følger:

Jurymedlemmenes poenggivning.

Jurymedlemmenes poenggivning.

Beste fem øl innen farge, duft, smak og helhet.

Så hvem er vinnerene av deltestene? Her følger topp fem for hver deltest:

Beste fem øl innen farge, duft, smak og helhet.

Beste fem øl innen farge, duft, smak og helhet.

Har du tenkt å drikke øl med kun ganen så ser det ut til at Kinn Julefred går av som vinner, ellers troner Nøgene Øs øl på topp også på deltestene.

Korrelasjonene – fra farge og duft til smak

Oppdelingen i flere deltester gjør at vi kan se nærmere på hva som muligens påvirker smaken og helhetsinntrykket. Følgende viser korrelasjoner; farge og duft versus duft, smak og helhet.

Scatter-plot mellom delpoengene.

Scatter-plot mellom delpoengene.

Det ser ut til å være en positiv korrelasjon mellom delpoengsummene. Tableau rapporterer at samtlige trendlinjer har p-verdi på lavere enn 0.0001, men følgende R-squared.

X-aksen Y-aksen R-squared p-verdi
Farge Helhet 0,216341 < 0.0001
Farge Smak 0,220991 < 0.0001
Farge Duft 0,236277 < 0.0001
Duft Helhet 0,615605 < 0.0001
Duft Smak 0,580103 < 0.0001
Duft Duft 1 < 0.0001

Poenggivningen ble gjort på en slik måte at vi ga delpoeng før vi gikk videre til neste deltest. Altså, fikk farge poeng før duft, og duft før smak og helhet. Dette kan gi støtte til at det er snakk om kausalitet og ikke bare korrelasjon i tallene. Det virker som at vi faktisk synes at øl som ser bra ut også lukter bra, og øl som lukter bra også smaker bra. Akkurat hvorfor skal jeg ikke begi meg innpå, annet enn at det kan være en slags anchoring effekt og/eller ønske om å være konsistent med tidligere poenggivning. Selvsagt, det kan jo også være at vi er superflinke til å tyde ølens kvaliteter fra utseende, men jeg tviler.

Svik og lureri

Hva skjer når eksperimentøren finner ut av å servere samme øl flere ganger? Og ikke minst samme øl rett etter hverandre? Tredjeplassen, Kinn Julefred, ble servert som nummer 4 og 10, samt Delirium Christmas som nummer 14 og 15, altså rett etter hverandre.

Servering av samme øl flere ganger.

Servering av samme øl flere ganger.

For Kinn Julefred var dens andre mottakelse svært så mørk; den gikk tilbake 10 poeng. Kun undertegnede valgte å ikke gi nevneverdig mindre poeng, mens største tilbakefallet fra et jurymedlem var på hele 20 poeng, eller 2.5 standardavvik lavere. Dette tilsvarer å gå fra å ha ei topp 1% øl til å ei som er nøyaktig midt på treet. For Delirium Christmas var tilbakefallet ikke så ille. De fleste jurymedlemmene sto på stedet hvil; tilbakefallet var på kun 3 poeng.

Betydningen av land og gjæringsprosess

I utgangspunktet forventet vi ikke mye forskjell mellom landene. Men la følgende illustrasjon synke inn.

Box-and-whiskers-plot av endelig poengsum mot varegruppe og land.

Box-and-whiskers-plot av endelig poengsum mot varegruppe og land.

Av en eller annen grunn kom dansk øl veldig dårlig ut. Mulig det er tilgjengelighet og seleksjonsbias. Sveriges resultat bør vi også ta med en klype salt, da de ikke har mange datapunkt. Muligens bare ei øl.

Når det kommer til gjæringsprosessen så er resultatet ca. det samme i snitt, men undergjæret ser ut til å gi mer konsistente resultat.

Kanskje bør man velge belgisk undergjæret øl for å være sikker på at juleølla er rimelig god? Vet ikke helt om vi har grunnlag for å si det, men artige resultat er det likevel.

Alkoholprosenten kan ha mye å si

En ting som undertegnede ikke hadde forventet var at alkoholprosenten kan ha en god del å si. Følgende viser samme poengfordeling som før, men denne gangen farger vi intervallene med alkoholprosenten. Tallet i søylene forteller snitt prosenten.

Poengfordeling med alkoholprosenten farget.

Poengfordeling med alkoholprosenten farget.

Det ser ut til at øl med for høy eller lav alkoholprosent ikke blir tatt i mot like godt som dem med mer normale alkoholnivåer. For å sjekke dette nærmere gjorde vi en scatter-plot mellom poeng og alkoholprosent.

Scatter-plot av alkoholprosent mot poeng.

Scatter-plot av alkoholprosent mot poeng.

Visuelt ser vi også her en tendens til at for høy eller lav alkoholprosent er negativt. Litt over 8% er perfekt – kanskje. Trendlinjene er polynomisk (andre grad) med følgende egenskaper:

X-aksen Y-aksen R-squared p-verdi
Alkoholprosent Smak 0,353001 < 0.0001
Alkoholprosent Duft 0,26575 < 0.0001
Alkoholprosent Total 0,373889 < 0.0001
Alkoholprosent Helhet 0,366977 < 0.0001

Hva har vi lært?

Helt klart: Den beste juleølla er ikke dansk, har rundt 8% alkoholvolum, og er overgjæret. Allerede av fargen vil du kunne ha en anelse om du vil like den, og når duften er sjekket så er dommen så og si allerede gitt. Helge og Stian vet hva de holder på med, mens vi to andre bør studere videre. Tja, vell, kanskje så bombastisk bør vi ikke være på alle punkter, men analysen har vært artig å utføre og kan kanskje være verdt en ettertanke. Er det en ting som er sikkert så går du ikke feil med Nøgene Øs juleøl.

Igjen takk til vertene, og øvrige jurymedlemmer. Det var utrolig gøy! Håper vi alle har blitt klokere på julebrygget. Ser frem til juleøltesten 2015.

Hiding Your Bits in the Bytes: A basic example of modern steganography using C#

I recently found a video on youtube where some CSI personnel zoomed into an innocuous image to discover that there were embedded several hidden contraband images in the larger image. The actual link to the video escapes my googling abilities at the moment of writing. The first thing I thought when seeing the video was that “this is definitely not how I would have embedded data into an image.” I hypothesized that it in essence could be done by wiggling the less significant bits of information in the image. A tiny difference in hues for each pixel in the image would probably not be perceptible by humans. I set out to confirm my hypothesis as a small personal project for the evening, knowing full well that this was nothing new and naturally done before.

I have later learned the name of the practice of hiding information in larger works: Steganography. Wikipedia defines Steganography as “the art or practice of concealing a message, image, or file within another message, image, or file.” It’s quite an intriguing concept.

Concept and theory

A computer image, such as PNG-files, when uncompressed is simply an m-by-n matrix, i.e., table, of pixels each of a specific color (and transparency). The pixels can be further decomposed into three primary component colors, Red, Green, and Blue, and the transparency, Alpha. In C# these can be extracted as an integer value per component per pixels. I focused on only the color components, and ignored the Alpha value even though it could have been used too. Besides, it would be quite suspicious having loads subtle transparencies in an image.

The following code reads the image file “image.png” as a Bitmap object, extracts the Color object of the pixel at the arbitrary column 7 and row 11, and writes the RGB values to the console window.

Bitmap bmp = new Bitmap("image.png");
int x = 7; int y = 11;
Color px = bmp.GetPixel(x, y);
Console.Write("Red={0}, Green={1}, Blue={2}",
px.R, px.G, px.B);

The code requires a reference to the System.Drawing assembly and namespace, and will output something like

Red=124, Green=156, Blue=43

Notice how the pixel color components px.R, px.G, px.B are simply small integer values, in fact they are simple byte structs, with a minimum value of 0 and a maximum value of 255. Changing the value of these by one bit changes the color, however, only imperceptibly.

The first of the two following images is named light turquoise by MS Paint, and has the RGB values 153, 217, and 234 respectively. The second of the two images I have perturbed by one bit such that the RGB values are now 152, 218, and 233.
light_turquoise_pert

These are for all esthetical purposes identical, and we can utilize this to encode our bits. First though, we need to be able to make out if a color component has been perturbed or not. A simple way would be to make all of the components even (or odd) and encode the one-bits as odd values and the zero-bits as even values.

The following table illustrates how the ascii string “Hi!” (or “100100011010010100001” in binary) can be encoded in the first six pixels of an image:

Char Row Col. Comp. Original Flat Encoded Parity Bit
‘H’ 0 0 Red 41 40 41 Odd 1
0 0 Green 42 42 42 Even 0
0 0 Blue 56 56 56 Even 0
0 1 Red 133 132 133 Odd 1
0 1 Green 104 104 104 Even 0
0 1 Blue 127 126 126 Even 0
0 2 Red 64 64 64 Even 0
‘i’ 0 2 Green 80 80 81 Odd 1
0 2 Blue 138 138 139 Odd 1
0 3 Red 242 242 242 Even 0
0 3 Green 178 178 179 Odd 1
0 3 Blue 182 182 182 Even 0
0 4 Red 190 190 190 Even 0
0 4 Green 169 168 169 Odd 1
‘!’ 0 4 Blue 192 192 192 Even 0
0 5 Red 250 250 251 Odd 1
0 5 Green 213 212 212 Even 0
0 5 Blue 143 142 142 Even 0
0 6 Red 185 184 184 Even 0
0 6 Green 193 192 192 Even 0
0 6 Blue 7 6 7 Odd 1

In this table we can see that each pixel can store three hidden bits of information. Thus an 800 by 600 pixel image could store 1.44 Mb (megabits) or 180 kB (kilobytes) of hidden data.

Code and application

Lets now turn the concepts we have been talking about into code.

Disclaimer: The following code is by no means production ready, or safe to use for real applications. Its simply a proof of concept. There probably exists plenty of methods which could easily detect the data we are hiding.

There are two main steps to be concerned about. The encoding of data we want to hide into some innocuous image file, and the recovery of this data through decoding. This outline is encapsulated in the main method:

static void Main()
{
    byte[] hiddenBytes = Util.BitmapToByteArray(Image.FromFile("hidden.png"));
    Encode(hiddenBytes, "innocuous.png", "encoded.png");
    byte[] loadedHiddenBytes = Decode("encoded.png");
    Util.ByteArrayToBitmap(loadedHiddenBytes).Save("decoded.png", ImageFormat.Png);
}

The first line loads the image “hidden.png” into memory as a simple byte array.

hidden.png - An image of Charles Darwin we would like hide.

hidden.png – An image of Charles Darwin we would like hide.

The “hidden.png” image is the data we would like to encode into the data of some other innocuous file. The second line does this by loading the image “innocuous.png” to memory, encodes and hides the data of “hidden.png” into the “innocuous.png” data and stores it as “encoded.png”. Thus “innocuous.png” and “encoded.png” should look identical, just that the latter has the “hidden.png” data embedded into it.

innocuous.png - An innocuous image of a forest. There is no embedded data in this image.

innocuous.png – An innocuous image of a forest. There is no embedded data in this image.

encoded.png – An innocuous-looking image of a forest. The hidden.png data is embedded in this image.

encoded.png – An innocuous-looking image of a forest. The hidden.png data is embedded in this image.

Now we want to extract the hidden “hidden.php” data from the “encoded.png” image. The third line loads and decodes the hidden bytes into memory, and in the fourth line we write this data back to file as “decoded.png”. Thus “hidden.png” and “decoded.png” will be identical.

decoded.png - An image of Charles Darwin we just extracted from the encoded.php image file.

decoded.png – An image of Charles Darwin we just extracted from the encoded.php image file.

To recap, the first and second line is what one would use to hide your data, while lines three and four is what you would use to get it back.

High level data flow of the encoding and decoding process.

High level data flow of the encoding and decoding process.

Lets go into more detail.

Encoding

Too keep things somewhat organized helper methods have been encapsulated into a custom Util class, for lack of a better name. In the main method the Util.BitmapToByteArray is used to convert our contraband Darwin image into bytes. Specifically it takes the image object generated when we loaded the “hidden.png” file and converts it into a byte array using a new MemoryStream object.

class Util
{
    public static byte[] BitmapToByteArray(Image img)
    {
        using (MemoryStream ms = new MemoryStream())
        {
            img.Save(ms, ImageFormat.Png);
            return ms.ToArray();
        }
    }
...
}

When this is done the byte array is passed to the Encode method with the file name of the innocuous image, and the desired output file name.

public static void Encode(byte[] hiddenBytes, string inputImageFileName, string outputImageFileName)
{
    // Loading the data we want to hide to a byte array
    byte[] hiddenLengthBytes = BitConverter.GetBytes(hiddenBytes.Length);
    byte[] hiddenCombinedBytes = Util.Combine(hiddenLengthBytes, hiddenBytes);
	
     // Loading an innocuous image we want to store the hidden data in to a byte array
    Image innocuousBmp = Image.FromFile(inputImageFileName);
    byte[] rgbComponents = Util.RgbComponentsToBytes(innocuousBmp);
	
     // Encoding the hidden data into the innocuous image, and storing it to file.
    byte[] encodedRgbComponents = EncodeBytes(hiddenCombinedBytes, rgbComponents);
    Bitmap encodedBmp = Util.ByteArrayToBitmap(encodedRgbComponents, innocuousBmp.Width, innocuousBmp.Height);
    encodedBmp.Save(outputImageFileName, ImageFormat.Png);
}

First thing we need is a strategy to know how much data is encoded. There are multiple ways of doing this. I have chosen to simply encode it as a fixed length header. This can be done simply by encoding the length of the hidden data using a BitConverter, then append these bytes to the front of the data we want to hide. This is done in the Util.Combine method.

class Util
{
...
    public static byte[] Combine(byte[] left, byte[] right)
    {
        byte[] combined = new byte[left.Length + right.Length];
        Buffer.BlockCopy(left, 0, combined, 0, left.Length);
        Buffer.BlockCopy(right, 0, combined, left.Length, right.Length);
        return combined;
    }
...
}

Next we load the innocuous image file and converts the color components into an array of consecutive bytes stored as an array. This is done in the Util.RgbComponentsToBytes method.

class Util
{
...
    public static byte[] RgbComponentsToBytes(Image innocuousImg)
    {
        Bitmap innocuousBmp = new Bitmap(innocuousImg);
        int counter = 0;
        byte[] components = new byte[3 * innocuousBmp.Width * innocuousBmp.Height];
        for (int y = 0; y < innocuousBmp.Height; y++)
        {
            for (int x = 0; x < innocuousBmp.Width; x++)
            {
                Color c = innocuousBmp.GetPixel(x, y);
                components[counter++] = c.R;
                components[counter++] = c.G;
                components[counter++] = c.B;
            }
        }
        return components;
    }
...
}

This creates a medium for hiding our bits as the less significant bits of the color component bytes. Now that we have data we want to hide and the medium we want to hide the data in as suitable data types we can do the actual encoding.

private static byte[] EncodeBytes(byte[] hiddenBytes, byte[] innocuousBytes)
{
    BitArray hiddenBits = new BitArray(hiddenBytes);
    byte[] encodedBitmapRgbComponents = new byte[innocuousBytes.Length];
    for (int i = 0; i < innocuousBytes.Length; i++)
    {
        if (i < hiddenBits.Length)
        {
            byte evenByte = (byte)(innocuousBytes[i] - innocuousBytes[i] % 2);
            encodedBitmapRgbComponents[i] = (byte)(evenByte + (hiddenBits[i] ? 1 : 0));
        }
        else
        {
            encodedBitmapRgbComponents[i] = innocuousBytes[i];
        }
    }
    return encodedBitmapRgbComponents;
}

First thing is to convert the data we want to hide, and it’s size header into a BitArray. Then we loop through all the component color bytes of the innocuous data. If we are looping through parts of the component colors we want to encoding data we truncate the least significant bit. If it is zero then we keep it zero, if it is one we make it zero, in effect this makes all the color components an even number. To encode our hidden bits we literally add them to the even color component bytes. This makes hidden one bits odd color component numbers, and zeroe bits even color component numbers. A slight perturbation which isn’t recognizable to the naked eye. When we have encoded all the hidden bits, we simply keep the original color component bytes as they are. I’ve intentionally made this part of the code as simple as possible so that it is easier to explain. However, there are innumerous ways of doing this in more complex ways to avoid detection. This is outside the scope of this simple tutorial, although I’ll do a simple analysis at the end to show how things look when encoded.

When the actual encoding is done we must convert the color components byte array back to an image.

class Util
{
...
    public static Bitmap ByteArrayToBitmap(byte[] rgbComponents, int width, int hight)
    {
        Queue<byte> rgbComponentQueue = new Queue<byte>(rgbComponents);
        Bitmap bitmap = new Bitmap(width, hight);
        for (int y = 0; y < hight; y++)
        {
            for (int x = 0; x < width; x++)
            {
                bitmap.SetPixel(x, y, Color.FromArgb(rgbComponentQueue.Dequeue(), rgbComponentQueue.Dequeue(), rgbComponentQueue.Dequeue()));
            }
        }
        return bitmap;
    }
}

When we again have an image object (Bitmap extends the Image class) we can save it using it’s save method. This outputs the “encoded.png” image file, which looks identical to the “innocuous.png” image file.

Decoding

The next part is about restoring the hidden image from the encoded innocuous file. This is done in the Decode method.

public static byte[] Decode(string imageFileName)
{
    // Loading the seemingly innocuous image with hidden data into a byte array
    Bitmap loadedEncodedBmp = new Bitmap(imageFileName);
    byte[] loadedEncodedRgbComponents = Util.RgbComponentsToBytes(loadedEncodedBmp);
    const int bytesInInt = 4;
    byte[] loadedHiddenLengthBytes = DecodeBytes(loadedEncodedRgbComponents, 0, bytesInInt);
    int loadedHiddenLength = BitConverter.ToInt32(loadedHiddenLengthBytes, 0);
    byte[] loadedHiddenBytes = DecodeBytes(loadedEncodedRgbComponents, bytesInInt, loadedHiddenLength);
    return loadedHiddenBytes;
}

Here we again use Util.RgbComponentsToBytes to extract the color component bytes. We know there is a header which says how much data there is. This is an Int32 converted which is stored as four bytes stored in the first 32 color component bytes. To extract the length data, we use the DecodeBytes method. It takes the color color component bytes, the first byte index and length of data. This means we can read any part of the hidden data, doesn’t have to be the start. In this case it is the first byte index and four bytes down.

private static byte[] DecodeBytes(byte[] innocuousLookingData, int byteIndex, int byteCount)
{
    const int bitsInBytes = 8;
    int bitCount = byteCount * bitsInBytes;
    int bitIndex = byteIndex * bitsInBytes;
    bool[] loadedHiddenBools = new bool[bitCount];
    for (int i = 0; i < bitCount; i++)
    {
        loadedHiddenBools[i] = innocuousLookingData[i + bitIndex] % 2 == 1;
    }
    BitArray loadedHiddenBits = new BitArray(loadedHiddenBools);
    byte[] loadedHiddenBytes = new byte[loadedHiddenBits.Length / bitsInBytes];
    loadedHiddenBits.CopyTo(loadedHiddenBytes, 0);
    return loadedHiddenBytes;
}

When we have extracted the length of the hidden data to follow we use the DecodeBytes method again, this time from byte index four to the end of the hidden data. The way we extract the hidden data is by checking if a color component is even or odd using the modulus operation. We put all the detected bits into a bool array and convert it to a BitArray which is converted into a Byte array and returned.

Back in the main method we convert the hidden bytes into an image object and store it to file as “decoded.png”.

Simple Analysis

Again, I’d like to stress that this isn’t the best way to do this in practice. This is simply a hobby project where I did next to zero research. When that is said, lets look at what the encoded data looks like.

First, lets look at the difference between the “innocuous.png” image and the “encoded.png” image.

The visual difference between innocuous.png and encoded.png.

The visual difference between innocuous.png and encoded.png.

I added the black border manually to emphasis that the bottom part is actually blank. If a pixel is white it means that there is no difference between the images at all, while if it is black then all three color components of the pixels are perturbed by one. Gray scales between mean that only one or two of the three color components of the pixels are identical. As we can see the first one third of the image have perturbed pixels. The rest are identical. This means that the hidden Darwin image and its length header are stored in this top part of the image. It kind of looks like noise.

This is apposed to what the parity of the color components look like:

Looking at the parity of the color components of the innocuous.png  image.

Looking at the parity of the color components of the innocuous.png image.

What we see here is that the compression algorithm of the “innocuous.png” image lumps some of the pixels together. Especially where there are really dark or light colors. Notice at the top where there is a white spot where there is some sky in the original image. If we overlay the “innocuous.png” image, its parity image, and the parity image of the “ecoded.png” image we see that a lot of the compression data is lost and that there are quite noticeable perturbations:

Looking at the parity of the color components of the innocuous.png  image versus the ecoded.png image.

Looking at the parity of the color components of the innocuous.png image versus the ecoded.png image.

This could probably be detected automatically thus notifying an adversary of the existence of hidden data in the image.

Source code

For completeness the full source code is included below. I have also added the mask creation method which I used to analyse the image at the end.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Text;

namespace SteganographyTest
{
    class Program
    {
        static void Main()
        {
            byte[] hiddenBytes = Util.BitmapToByteArray(Image.FromFile("hidden.png"));
            Encode(hiddenBytes, "innocuous.png", "encoded.png");
            byte[] loadedHiddenBytes = Decode("encoded.png");
            Util.ByteArrayToBitmap(loadedHiddenBytes).Save("decoded.png", ImageFormat.Png);
            CreateMask("innocuous.png", "encoded.png");
        }

        public static void Encode(byte[] hiddenBytes, string inputImageFileName, string outputImageFileName)
        {
            // Loading the data we want to hide to a byte array
            byte[] hiddenLengthBytes = BitConverter.GetBytes(hiddenBytes.Length);
            byte[] hiddenCombinedBytes = Util.Combine(hiddenLengthBytes, hiddenBytes);

            // Loading an innocuous image we want to store the hidden data in to a byte array
            Image innocuousBmp = Image.FromFile(inputImageFileName);
            byte[] rgbComponents = Util.RgbComponentsToBytes(innocuousBmp);

            // Encoding the hidden data into the innocuous image, and storing it to file.
            byte[] encodedRgbComponents = EncodeBytes(hiddenCombinedBytes, rgbComponents);
            Bitmap encodedBmp = Util.ByteArrayToBitmap(encodedRgbComponents, innocuousBmp.Width, innocuousBmp.Height);
            encodedBmp.Save(outputImageFileName, ImageFormat.Png);
        }

        private static byte[] EncodeBytes(byte[] hiddenBytes, byte[] innocuousBytes)
        {
            BitArray hiddenBits = new BitArray(hiddenBytes);
            byte[] encodedBitmapRgbComponents = new byte[innocuousBytes.Length];
            for (int i = 0; i < innocuousBytes.Length; i++)
            {
                if (i < hiddenBits.Length)
                {
                    byte evenByte = (byte)(innocuousBytes[i] - innocuousBytes[i] % 2);
                    encodedBitmapRgbComponents[i] = (byte)(evenByte + (hiddenBits[i] ? 1 : 0));
                }
                else
                {
                    encodedBitmapRgbComponents[i] = innocuousBytes[i];
                }
            }
            return encodedBitmapRgbComponents;
        }

        public static byte[] Decode(string imageFileName)
        {
            // Loading the seemingly innocuous image with hidden data into a byte array
            Bitmap loadedEncodedBmp = new Bitmap(imageFileName);
            byte[] loadedEncodedRgbComponents = Util.RgbComponentsToBytes(loadedEncodedBmp);

            const int bytesInInt = 4;
            byte[] loadedHiddenLengthBytes = DecodeBytes(loadedEncodedRgbComponents, 0, bytesInInt);
            int loadedHiddenLength = BitConverter.ToInt32(loadedHiddenLengthBytes, 0);
            byte[] loadedHiddenBytes = DecodeBytes(loadedEncodedRgbComponents, bytesInInt, loadedHiddenLength);
            return loadedHiddenBytes;
        }

        private static byte[] DecodeBytes(byte[] innocuousLookingData, int byteIndex, int byteCount)
        {
            const int bitsInBytes = 8;
            int bitCount = byteCount * bitsInBytes;
            int bitIndex = byteIndex * bitsInBytes;
            bool[] loadedHiddenBools = new bool[bitCount];
            for (int i = 0; i < bitCount; i++)
            {
                loadedHiddenBools[i] = innocuousLookingData[i + bitIndex] % 2 == 1;
            }
            BitArray loadedHiddenBits = new BitArray(loadedHiddenBools);
            byte[] loadedHiddenBytes = new byte[loadedHiddenBits.Length / bitsInBytes];
            loadedHiddenBits.CopyTo(loadedHiddenBytes, 0);
            return loadedHiddenBytes;
        }

        public static void CreateMask(string inputImageFileName1, string inputImageFileName2)
        {
            Image image1 = Image.FromFile(inputImageFileName1);
            Image image2 = Image.FromFile(inputImageFileName2);
            Bitmap bmp1 = new Bitmap(image1);
            Bitmap bmp2 = new Bitmap(image2);
            Bitmap maskDiff = new Bitmap(bmp1);
            Bitmap maskParity1 = new Bitmap(bmp1);
            Bitmap maskParity2 = new Bitmap(bmp2);

            for (int i = 0; i < maskDiff.Height; i++)
            {
                for (int j = 0; j < maskDiff.Width; j++)
                {
                    Color px1 = bmp1.GetPixel(j, i);
                    Color px2 = bmp2.GetPixel(j, i);

                    int maskDiffIntensity = 255 - Math.Abs(px2.R - px1.R) * 85 - Math.Abs(px2.G - px1.G) * 85 - Math.Abs(px2.B - px1.B) * 85;
                    maskDiff.SetPixel(j, i, Color.FromArgb(maskDiffIntensity, maskDiffIntensity, maskDiffIntensity));

                    int maskParityIntensity1 = (px1.R % 2) * 85 + (px1.G % 2) * 85 + (px1.B % 2) * 85;
                    maskParity1.SetPixel(j, i, Color.FromArgb(maskParityIntensity1, maskParityIntensity1, maskParityIntensity1));

                    int maskParityIntensity2 = (px2.R % 2) * 85 + (px2.G % 2) * 85 + (px2.B % 2) * 85;
                    maskParity2.SetPixel(j, i, Color.FromArgb(maskParityIntensity2, maskParityIntensity2, maskParityIntensity2));
                }
            }

            maskDiff.Save("maskDiff.png");
            maskParity1.Save("maskParity_" + inputImageFileName1);
            maskParity2.Save("maskParity_" + inputImageFileName2);

        }
    }

    class Util
    {
        public static byte[] BitmapToByteArray(Image img)
        {
            using (MemoryStream ms = new MemoryStream())
            {
                img.Save(ms, ImageFormat.Png);
                return ms.ToArray();
            }
        }

        public static Image ByteArrayToBitmap(byte[] bytes)
        {
            using (MemoryStream ms = new MemoryStream(bytes))
            {
                return Image.FromStream(ms);
            }
        }

        public static byte[] Combine(byte[] left, byte[] right)
        {
            byte[] combined = new byte[left.Length + right.Length];
            Buffer.BlockCopy(left, 0, combined, 0, left.Length);
            Buffer.BlockCopy(right, 0, combined, left.Length, right.Length);
            return combined;
        }

        public static byte[] RgbComponentsToBytes(Image innocuousImg)
        {
            Bitmap innocuousBmp = new Bitmap(innocuousImg);
            int counter = 0;
            byte[] components = new byte[3 * innocuousBmp.Width * innocuousBmp.Height];
            for (int y = 0; y < innocuousBmp.Height; y++)
            {
                for (int x = 0; x < innocuousBmp.Width; x++)
                {
                    Color c = innocuousBmp.GetPixel(x, y);
                    components[counter++] = c.R;
                    components[counter++] = c.G;
                    components[counter++] = c.B;
                }
            }
            return components;
        }

        public static Bitmap ByteArrayToBitmap(byte[] rgbComponents, int width, int hight)
        {
            Queue<byte> rgbComponentQueue = new Queue<byte>(rgbComponents);
            Bitmap bitmap = new Bitmap(width, hight);
            for (int y = 0; y < hight; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    bitmap.SetPixel(x, y, Color.FromArgb(rgbComponentQueue.Dequeue(), rgbComponentQueue.Dequeue(), rgbComponentQueue.Dequeue()));
                }
            }
            return bitmap;
        }
    }
}