Tutorial voor analyse van gegevensomhulling

• 24 februari 2014
• Vasilis Vryniotis
• . 3 opmerkingen

Data Envelopment Analysis, ook bekend als DEA, is een niet-parametrische methode voor het uitvoeren van grensanalyse. Het maakt gebruik van lineaire programmering om de efficiëntie van meerdere besluitvormingseenheden te schatten en wordt vaak gebruikt in productie, beheer en economie. De techniek is voor het eerst voorgesteld door Charnes, Cooper en Rhodes in 1978 en sindsdien is het een waardevol instrument geworden voor het schatten van productiegrenzen.

Update: het Datumbox Machine Learning Framework is nu open-source en gratis voor Download. Bekijk het pakket com.datumbox.framework.algorithms.dea om de implementatie van Data Envelopment Analysis in Java te zien.

Toen ik de methode 5-6 jaar geleden voor het eerst tegenkwam, was ik verbaasd over de originaliteit van het algoritme, de eenvoud en de slimheid van de ideeën die het gebruikte. Ik was zelfs nog meer verbaasd om te zien dat de techniek goed werkte buiten de gebruikelijke toepassingen (financieel, operationeel onderzoek enz.), Omdat deze met succes kon worden toegepast in online marketing, zoekmachine-ranking en voor het maken van samengestelde statistieken. Desondanks wordt DEA tegenwoordig bijna uitsluitend besproken in de context van het bedrijfsleven. Daarom zal ik in dit artikel de basisideeën en het wiskundige kader achter DEA behandelen en in de volgende post zal ik u enkele nieuwe toepassingen van het algoritme op webapplicaties laten zien.

Waarom Data Envelopment Analysis interessant is?

Data Envelopment Analysis is een methode waarmee we records (winkels, werknemers, fabrieken, webpagina's, marketingcampagnes enz.) Kunnen vergelijken en rangschikken op basis van hun kenmerken (gewicht, omvang, kosten, inkomsten en andere statistieken of KPI's) zonder vooraf aannames te doen over het belang of de gewichten van de functies. Het meest interessante deel van deze techniek is dat we hiermee records kunnen vergelijken die uit meerdere kenmerken bestaan ​​met totaal verschillende meeteenheden. Dit betekent dat we records kunnen hebben met kenmerken gemeten in kilometers, kilogrammen of geldeenheden en toch in staat zijn om ze te vergelijken, ze te rangschikken en de beste / slechtste en gemiddeld presterende records te vinden. Klinkt interessant? Blijf lezen.

De beschrijving en aannames van Data Envelopment Analysis

Zoals we eerder hebben besproken, is DEA een methode die is uitgevonden om de productiviteit in het bedrijfsleven te meten. Verschillende van zijn ideeën komen dus voort uit de manier waarop productiviteit in deze context wordt gemeten. Een van de belangrijkste kenmerken van de methode is de scheiding van de recordkenmerken in twee categorieën: invoer en uitvoer. Als we bijvoorbeeld de efficiëntie van een auto meten, kunnen we zeggen dat de input de liters benzine is en de output het aantal kilometers dat hij aflegt.

In DEA moeten alle functies positief zijn en er wordt aangenomen dat hoe hoger hun waarde, hoe meer hun invoer / uitvoer is. Bovendien gaat Data Envelopment Analysis ervan uit dat de kenmerken lineair kunnen worden gecombineerd als een gewogen som van niet-negatieve gewichten en een verhouding vormen tussen invoer en uitvoer die de efficiëntie van elk record zal meten. Om een ​​record efficiënt te laten zijn, moet het ons een "goede" output geven ten opzichte van de geleverde input. De efficiëntie wordt gemeten door de verhouding tussen output en input en vervolgens vergeleken met de ratio van de andere records.

Het ingenieuze idee achter DEA

Wat we tot nu toe hebben besproken, is een gezond verstand / praktijk. We gebruiken input en output, gewogen sommen en ratio's om onze records te rangschikken. Het slimme idee van DEA zit in de manier waarop de gewichten van de functies worden berekend. In plaats van de gewichten van de functies in te stellen en te beslissen over hun belang voordat we de analyse uitvoeren, berekent de Data Envelopment Analysis ze uit de gegevens. Bovendien zijn de gewichten NIET voor elk record hetzelfde!

Hier is hoe DEA de gewichten selecteert: we proberen de verhouding van elk record te maximaliseren door de juiste kenmerkgewichten te selecteren; Tegelijkertijd moeten we er echter voor zorgen dat als we dezelfde gewichten gebruiken om de verhoudingen van alle andere records te berekenen, geen van hen groter zal worden dan 1.

Het idee klinkt in het begin een beetje vreemd. Leidt dit niet tot de berekening van verschillend gewogen ratio's? Het antwoord is ja. Betekent dit niet dat we de verhoudingen voor elk record eigenlijk anders berekenen? Het antwoord is opnieuw ja. Dus hoe werkt dit? Het antwoord is simpel: voor elk record proberen we, gezien de kenmerken ervan, de 'ideale situatie' (gewichten) te vinden waarin de verhouding zo hoog mogelijk zou zijn en deze zo effectief mogelijk zou maken. MAAR tegelijkertijd mag, gezien deze "ideale situatie", geen van de output / input-verhoudingen van de andere records groter zijn dan 1, wat betekent dat ze niet effectiever kunnen zijn dan 100%! Zodra we de verhoudingen van alle records onder elke "ideale situatie" hebben berekend, gebruiken we hun verhoudingen om ze te rangschikken.

Het belangrijkste idee van DEA kan dus als volgt worden samengevat: “Vind de ideale situatie waarin we de beste ratio-score kunnen behalen op basis van de kenmerken van elk record. Bereken vervolgens deze ideale verhouding van elk record en gebruik het om hun effectiviteit te vergelijken ”.

Laten we een voorbeeld bekijken

Laten we een voorbeeld bekijken waar we DEA zouden kunnen gebruiken.

Stel dat we geïnteresseerd zijn in het evalueren van de efficiëntie van de supermarkten van een bepaalde keten op basis van een aantal kenmerken: het totale aantal werknemers, de grootte van de winkel in vierkante meters, het aantal verkopen dat ze genereren en het aantal klanten die ze gemiddeld elke maand serveren. Het wordt duidelijk dat het voor het vinden van de meest efficiënte winkels vereist dat we records vergelijken met meerdere functies.

Om DEA toe te passen, moeten we definiëren wat onze input en output is. In dit geval is de output natuurlijk het aantal verkopen en het aantal klanten dat ze bedienen. De input is het aantal medewerkers en de grootte van de winkel. Als we DEA uitvoeren, zullen we de output / input-verhouding voor elke winkel schatten onder de ideale gewichten (zoals hierboven besproken). Zodra we hun ratio's hebben, zullen we ze rangschikken op basis van hun efficiëntie.

Het is wiskundetijd!

Nu we een idee hebben van hoe DEA werkt, is het tijd om in de wiskunde te duiken.

De efficiëntieverhouding van een bepaald record i met x-invoer en y-uitvoer (beide kenmerkvectoren met positieve waarden) wordt geschat met behulp van de volgende formule:

Waar u en v de gewichten zijn van elke uitvoer en invoer van het record, is s het aantal uitvoerfuncties en is m het aantal invoerfuncties.

Het probleem van het vinden van de beste / ideale gewichten voor een bepaald record kan als volgt worden geformuleerd:

Nogmaals, het bovenstaande is slechts de wiskundige manier om de gewichten u en v te vinden die de efficiëntie van record i maximaliseren, op voorwaarde dat die gewichten geen van de andere records efficiënter maken dan 100%.

Om dit probleem op te lossen, moeten we lineaire programmering gebruiken. Helaas laten lineaire programmering ons niet toe om breuken te gebruiken en daarom moeten we de formulering van het probleem als volgt transformeren:

We moeten benadrukken dat het bovenstaande lineaire programmeerprobleem ons de beste gewichten geeft voor record i en de efficiëntie ervan berekent onder die optimale gewichten. Hetzelfde moet worden herhaald voor elk record in onze dataset. Dus als we n records hebben, moeten we n afzonderlijke lineaire problemen oplossen. Hier is de pseudocode van hoe DEA werkt:

ratio_scores = [];
for every record i {
    i_ratio = get_maximum_effectiveness();
    ratio_scores[i] = i_ratio;
}

Beperkingen van analyse van gegevensomhulling

DEA is een geweldige techniek, maar heeft zijn beperkingen. Je moet begrijpen dat DEA als een zwarte doos is. Aangezien de gewichten die worden gebruikt in de effectiviteitsratio van elk record verschillend zijn, is het zinloos om uit te leggen hoe en waarom elke score is berekend. Meestal richten we ons op de rangschikking van de records in plaats van op de werkelijke waarden van de effectiviteitsscores. Merk ook op dat het bestaan ​​van extremums ertoe kan leiden dat de scores zeer lage waarden hebben.

Houd er rekening mee dat DEA lineaire combinaties van de kenmerken gebruikt om de verhoudingen te schatten. Dus als ze lineair combineren niet geschikt is in onze toepassing, moeten we transformaties toepassen op de kenmerken en ze mogelijk maken om lineair te combineren. Een ander nadeel van deze techniek is dat we evenveel lineaire programmeerproblemen moeten oplossen als het aantal records, iets waarvoor veel rekenkracht nodig is.

Een ander probleem waarmee DEA wordt geconfronteerd, is dat het niet goed werkt met gegevens met hoge afmetingen. Om DEA te gebruiken moet het aantal dimensies d = m + s significant lager zijn dan het aantal waarnemingen. Het uitvoeren van DEA wanneer d erg dichtbij of groter is dan n levert geen bruikbare resultaten op, aangezien hoogstwaarschijnlijk alle records optimaal zullen blijken te zijn. Merk op dat als u een nieuwe uitvoervariabele (dimensie) toevoegt, alle records met de maximale waarde in deze dimensie optimaal worden gevonden.

Ten slotte moeten we opmerken dat in de algemene vorm van het algoritme de gewichten van de functies in DEA worden geschat op basis van de gegevens en daarom gebruiken ze geen eerdere informatie over het belang van functies die we in ons probleem zouden kunnen hebben (natuurlijk het is mogelijk om deze informatie op te nemen als beperkingen in ons lineaire probleem). Bovendien zijn de berekende efficiëntiescores in feite de bovengrens-efficiëntieverhoudingen van elk record, aangezien ze worden berekend onder "ideale situaties". Dit betekent dat DEA een goede oplossing kan zijn als het niet mogelijk is om aannames te doen over het belang van de functies, maar als we vooraf informatie hebben of het belang ervan kunnen kwantificeren, wordt geadviseerd om alternatieve technieken te gebruiken.

In het volgende artikel zal ik je laten zien hoe je een implementatie van kunt ontwikkelen Analyse van gegevensomhulling in JAVA en we zullen de methode gebruiken om de populariteit van webpagina's en artikelen in sociale medianetwerken in te schatten.

Als je het artikel leuk vindt, neem dan even de tijd om het op Twitter of Facebook te delen. 🙂