Tutorial de analiză a dezvoltării datelor

• 24 Februarie 2014
• Vasilis Vryniotis
• . 3 comentarii

Data Envelopment Analysis, cunoscută și sub numele de DEA, este o metodă neparametrică pentru efectuarea analizei de frontieră. Utilizează programarea liniară pentru a estima eficiența mai multor unități de luare a deciziilor și este utilizat în mod obișnuit în producție, management și economie. Tehnica a fost propusă pentru prima dată de Charnes, Cooper și Rhodes în 1978 iar de atunci a devenit un instrument valoros pentru estimarea frontierelor de producţie.

Actualizare: Datumbox Machine Learning Framework este acum open-source și gratuit Descarca. Consultați pachetul com.datumbox.framework.algorithms.dea pentru a vedea implementarea analizei învelișului de date în Java.

Când am întâlnit metoda pentru prima dată în urmă cu 5-6 ani, am fost uimit de originalitatea algoritmului, de simplitatea lui și de inteligența ideilor pe care le folosea. Am fost și mai uimit să văd că tehnica a funcționat bine în afara aplicațiilor sale obișnuite (financiare, cercetare operațională etc.), deoarece a putut fi aplicată cu succes în Marketing Online, Ranking Motoare de Căutare și pentru crearea de metrici compozite. În ciuda acestui fapt, astăzi DEA este discutată aproape exclusiv în contextul afacerilor. De aceea, în acest articol, voi acoperi ideile de bază și cadrul matematic din spatele DEA și în postarea următoare vă voi arăta câteva aplicații inedite ale algoritmului pe aplicații web.

De ce este interesantă analiza învelișului de date?

Data Envelopment Analysis este o metodă care ne permite să comparăm și să clasificăm înregistrările (magazine, angajați, fabrici, pagini web, campanii de marketing etc.) pe baza caracteristicilor acestora (greutate, dimensiune, cost, venituri și alte valori sau KPI) fără a face ipoteze anterioare despre importanța sau ponderile caracteristicilor. Cea mai interesantă parte a acestei tehnici este că ne permite să comparăm înregistrări compuse din mai multe caracteristici care au unități de măsură total diferite. Aceasta înseamnă că putem avea înregistrări cu caracteristici măsurate în kilometri, kilograme sau unități monetare și totuși putem să le comparăm, să le ierarhăm și să găsim cele mai bune/proaste înregistrări și cu performanțe medii. Sună interesant? Continua să citești.

Descrierea și ipotezele analizei învelișului datelor

După cum am discutat mai devreme, DEA este o metodă care a fost inventată pentru a măsura productivitatea în afaceri. Astfel, mai multe dintre ideile sale provin din modul în care productivitatea este măsurată în acest context. Una dintre caracteristicile de bază ale metodei este separarea caracteristicilor de înregistrare în două categorii: intrare și ieșire. De exemplu, dacă măsurăm eficiența unei mașini, am putea spune că intrarea este litrii de benzină și ieșirea este numărul de kilometri parcurși.

În DEA, toate caracteristicile trebuie să fie pozitive și se presupune că cu cât valoarea lor este mai mare, cu atât intrarea/ieșirea lor este mai mare. În plus, Data Envelopment Analysis presupune că caracteristicile pot fi combinate liniar ca o sumă ponderată de ponderi nenegative și formează un raport între intrare și ieșire care va măsura eficiența fiecărei înregistrări. Pentru ca o înregistrare să fie eficientă, trebuie să ne ofere o ieșire „bună” în raport cu intrarea furnizată. Eficiența este măsurată prin raportul dintre ieșire și intrare și apoi comparată cu raportul celorlalte înregistrări.

Ideea ingenioasă din spatele DEA

Ceea ce am acoperit până acum este un bun simț/o practică. Folosim intrări și ieșiri, sume ponderate și rapoarte pentru a ne clasifica înregistrările. Ideea inteligentă a DEA este modul în care sunt calculate ponderile caracteristicilor. În loc să fie nevoie să setăm ponderile caracteristicilor și să decidem cu privire la importanța lor înainte de a efectua analiza, Data Envelopment Analysis le calculează din date. Mai mult, greutățile NU sunt aceleași pentru fiecare record!

Iată cum DEA selectează ponderile: Încercăm să maximizăm raportul fiecărei înregistrări selectând ponderile caracteristice adecvate; în același timp, trebuie să ne asigurăm că, dacă folosim aceleași ponderi pentru a calcula rapoartele tuturor celorlalte înregistrări, niciuna dintre ele nu va deveni mai mare de 1.

Ideea sună cam ciudat la început. Acest lucru nu va duce la calcularea unor rapoarte ponderate diferit? Raspunsul este da. Nu înseamnă asta că de fapt calculăm diferit rapoartele pentru fiecare înregistrare? Răspunsul este din nou da. Deci cum funcționează asta? Răspunsul este simplu: pentru fiecare înregistrare, având în vedere caracteristicile ei, încercăm să găsim „situația ideală” (greutăți) în care raportul său ar fi cât mai mare și astfel să o facem cât mai eficientă. DAR în același timp, având în vedere această „situație ideală”, niciunul dintre rapoartele de ieșire/intrare ale celorlalte înregistrări nu ar trebui să fie mai mare de 1, ceea ce înseamnă că nu pot fi mai eficiente de 100%! Odată ce calculăm rapoartele tuturor înregistrărilor pentru fiecare „situație ideală”, le folosim pentru a le clasifica.

Deci ideea principală a DEA poate fi rezumată în următoarele: „Găsiți situația ideală în care putem obține cel mai bun punctaj raport pe baza caracteristicilor fiecărei înregistrări. Apoi calculați acest raport ideal al fiecărei înregistrări și utilizați-l pentru a le compara eficacitatea”.

Să vedem un exemplu

Să vedem un exemplu în care am putea folosi DEA.

Să presupunem că suntem interesați să evaluăm eficiența magazinelor de supermarketuri ale unui anumit lanț pe baza unui număr de caracteristici: numărul total de angajați, dimensiunea magazinului în metri pătrați, volumul vânzărilor pe care le generează și numărul de clienți. pe care le servesc în medie în fiecare lună. Devine evident că găsirea celor mai eficiente magazine ne impune să comparăm înregistrările cu funcții multiple.

Pentru a aplica DEA trebuie să definim care este intrarea și ieșirea noastră. În acest caz, rezultatul este în mod evident valoarea vânzărilor și numărul de clienți pe care îi deservesc. Intrarea este numărul de angajați și dimensiunea magazinului. Dacă rulăm DEA, vom estima raportul ieșire la intrare pentru fiecare magazin sub ponderile ideale (după cum s-a discutat mai sus). Odată ce avem rapoartele lor, le vom clasifica în funcție de eficiența lor.

E vremea matematicii!

Acum că ne-am intuit cum funcționează DEA, este timpul să pătrundem în matematică.

Raportul de eficiență al unei anumite înregistrări i cu intrare x și ieșire y (ambele vectori caracteristici cu valori pozitive) este estimată folosind următoarea formulă:

Unde u și v sunt ponderile fiecărei ieșiri și intrări a înregistrării, s este numărul de caracteristici de ieșire și m este numărul de caracteristici de intrare.

Problema găsirii celor mai bune/ideale ponderi pentru o anumită înregistrare i poate fi formulată după cum urmează:

Din nou, cele de mai sus sunt doar modalitatea matematică de a găsi ponderile u și v care maximizează eficiența înregistrării i, cu condiția ca acele ponderi să nu facă nici una dintre celelalte înregistrări mai eficientă decât 100%.

Pentru a rezolva această problemă trebuie să folosim programarea liniară. Din păcate, programarea liniară nu ne permite să folosim fracții și, prin urmare, trebuie să transformăm formularea problemei după cum urmează:

Ar trebui să subliniem că problema de programare liniară de mai sus ne va oferi cele mai bune ponderi pentru înregistrarea i și va calcula eficiența acesteia sub acele ponderi optime. Același lucru trebuie repetat pentru fiecare înregistrare din setul nostru de date. Deci, dacă avem n înregistrări, trebuie să rezolvăm n probleme liniare separate. Iată pseudocodul cum funcționează DEA:

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

Limitări ale analizei anvelopei datelor

DEA este o tehnică grozavă, dar are limitele ei. Trebuie să înțelegi că DEA este ca o cutie neagră. Deoarece ponderile care sunt utilizate în raportul de eficiență al fiecărei înregistrări sunt diferite, încercarea de a explica cum și de ce a fost calculat fiecare scor este inutilă. De obicei, ne concentrăm mai degrabă pe clasarea înregistrărilor decât pe valorile reale ale scorurilor de eficiență. De asemenea, rețineți că existența extremumurilor poate determina ca scorurile să aibă valori foarte scăzute.

Rețineți că DEA utilizează combinații liniare ale caracteristicilor pentru a estima rapoartele. Astfel, dacă combinarea lor liniară nu este adecvată în aplicația noastră, trebuie să aplicăm transformări asupra caracteristicilor și să le facem posibil să fie combinate liniar. Un alt dezavantaj al acestei tehnici este că trebuie să rezolvăm atâtea probleme de programare liniară câte sunt numărul de înregistrări, lucru care necesită multe resurse de calcul.

O altă problemă cu care se confruntă DEA este că nu funcționează bine cu date de dimensiuni mari. Pentru a utiliza DEA numărul de dimensiuni d = m + s trebuie să fie semnificativ mai mic decât numărul de observații. Rularea DEA când d este foarte aproape sau mai mare decât n nu oferă rezultate utile, deoarece cel mai probabil toate înregistrările vor fi găsite a fi optime. Rețineți că, pe măsură ce adăugați o nouă variabilă de ieșire (dimensiune), toate înregistrările cu valoarea maximă în această dimensiune vor fi găsite optime.

În cele din urmă, ar trebui să remarcăm că, în forma generală a algoritmului, ponderile caracteristicilor în DEA sunt estimate din date și astfel nu folosesc nicio informație prealabilă despre importanța caracteristicilor pe care le-am putea avea în problema noastră (desigur este posibil să încorporăm aceste informații ca constrângeri în problema noastră liniară). În plus, scorurile de eficiență care sunt calculate sunt de fapt ratele de eficiență limită superioară ale fiecărei înregistrări, deoarece sunt calculate în „situații ideale”. Aceasta înseamnă că DEA poate fi o soluție bună atunci când nu este posibil să facem nicio presupunere cu privire la importanța caracteristicilor, dar dacă avem informații prealabile sau putem cuantifica importanța lor, atunci se recomandă utilizarea unor tehnici alternative.

În articolul următor, vă voi arăta cum să dezvoltați o implementare a Analiza învăluirii datelor în JAVA și vom folosi metoda pentru a estima popularitatea paginilor web și a articolelor din rețelele de socializare.

Dacă vă place articolul, acordați-vă un moment pentru a-l distribui pe Twitter sau Facebook. 🙂