Tutorial sull'analisi dell'inviluppo dei dati

• 24 Febbraio 2014
• Vasilis Vryniotis
• . 3 commenti

L'analisi dell'inviluppo dei dati, nota anche come DEA, è un metodo non parametrico per eseguire l'analisi delle frontiere. Utilizza la programmazione lineare per stimare l'efficienza di più unità decisionali ed è comunemente usato in produzione, gestione ed economia. La tecnica è stata proposta per la prima volta da Charnes, Cooper e Rodi nel 1978 e da allora è diventato uno strumento prezioso per la stima delle frontiere produttive.

Aggiornamento: Datumbox Machine Learning Framework è ora open-source e gratuito scaricare. Dai un'occhiata al pacchetto com.datumbox.framework.algorithms.dea per vedere l'implementazione di Data Envelopment Analysis in Java.

Quando ho incontrato per la prima volta il metodo 5-6 anni fa, sono rimasto sorpreso dall'originalità dell'algoritmo, dalla sua semplicità e dalla genialità delle idee che ha usato. Sono stato ancora più sorpreso di vedere che la tecnica ha funzionato bene al di fuori delle sue solite applicazioni (finanziarie, ricerche operative, ecc.) Dal momento che poteva essere applicata con successo nel marketing online, nella classifica dei motori di ricerca e nella creazione di metriche composite. Nonostante ciò, oggi la DEA è discussa quasi esclusivamente nell'ambito del business. Ecco perché, in questo articolo, tratterò le idee di base e il quadro matematico dietro DEA e nel prossimo post ti mostrerò alcune nuove applicazioni dell'algoritmo sulle applicazioni web.

Perché l'analisi dell'inviluppo dei dati è interessante?

L'analisi dell'inviluppo dei dati è un metodo che ci consente di confrontare e classificare i record (negozi, dipendenti, fabbriche, pagine Web, campagne di marketing ecc.) In base alle loro caratteristiche (peso, dimensioni, costi, ricavi e altre metriche o KPI) senza fare ipotesi preliminari su l'importanza o il peso delle funzionalità. La parte più interessante di questa tecnica è che ci consente di confrontare i record composti da più funzioni che hanno unità di misura totalmente diverse. Ciò significa che possiamo avere record con caratteristiche misurate in chilometri, chilogrammi o unità monetarie ed essere ancora in grado di confrontare, classificarli e trovare i record migliori / peggiori e con prestazioni medie. Sembra interessante? Continua a leggere.

La descrizione e i presupposti dell'analisi dell'inviluppo dei dati

Come discusso in precedenza, DEA è un metodo inventato per misurare la produttività negli affari. Pertanto, molte delle sue idee derivano dal modo in cui la produttività viene misurata in questo contesto. Una delle caratteristiche principali del metodo è la separazione delle caratteristiche del record in due categorie: input e output. Ad esempio, se misuriamo l'efficienza di un'auto, potremmo dire che l'ingresso è i litri di benzina e l'uscita è il numero di chilometri che percorre.

In DEA, tutte le funzionalità devono essere positive e si presume che più alto è il loro valore, maggiore è il loro input / output. Inoltre, l'analisi dell'inviluppo dei dati presuppone che le funzioni possano essere combinate in modo lineare come somma ponderata di pesi non negativi e formare un rapporto tra input e output che misurerà l'efficienza di ciascun record. Perché un record sia efficiente, deve darci un output "buono" rispetto all'input fornito. L'efficienza viene misurata dal rapporto tra output e input e quindi confrontata con il rapporto degli altri record.

L'idea geniale dietro DEA

Ciò che abbiamo trattato finora è un buon senso / pratica. Usiamo input e output, somme ponderate e rapporti per classificare i nostri record. L'idea intelligente di DEA è nel modo in cui vengono calcolati i pesi delle funzionalità. Invece di dover impostare i pesi delle funzionalità e decidere la loro importanza prima di eseguire l'analisi, l'analisi dell'inviluppo dei dati li calcola dai dati. Inoltre i pesi NON sono gli stessi per ogni disco!

Ecco come DEA seleziona i pesi: proviamo a massimizzare il rapporto di ogni record selezionando i pesi delle caratteristiche appropriate; allo stesso tempo, tuttavia, dobbiamo assicurarci che se usiamo gli stessi pesi per calcolare i rapporti di tutti gli altri record, nessuno di essi diventerà maggiore di 1.

L'idea suona un po 'strana all'inizio. Questo non porterà al calcolo di rapporti ponderati in modo diverso? La risposta è si. Questo non significa che in realtà calcoliamo in modo diverso i rapporti per ogni record? La risposta è di nuovo sì. Quindi come funziona? La risposta è semplice: per ogni disco, date le sue caratteristiche, proviamo a trovare la "situazione ideale" (pesi) in cui il suo rapporto sarebbe il più alto possibile e quindi rendendolo il più efficace possibile. MA allo stesso tempo, data questa "situazione ideale", nessuno dei rapporti di output / input degli altri record dovrebbe essere maggiore di 1, il che significa che non possono essere più efficaci del 100%! Una volta calcolati i rapporti di tutti i record in ciascuna "situazione ideale", utilizziamo i loro rapporti per classificarli.

Quindi l'idea principale di DEA può essere riassunta nel modo seguente: “Trova la situazione ideale in cui possiamo ottenere il miglior punteggio in base alle caratteristiche di ciascun record. Quindi calcola questo rapporto ideale di ogni record e usalo per confrontare la loro efficacia ”.

Vediamo un esempio

Vediamo un esempio in cui potremmo usare DEA.

Supponiamo che siamo interessati a valutare l'efficienza dei negozi di supermercati di una determinata catena in base a una serie di caratteristiche: il numero totale di dipendenti, la dimensione del negozio in metri quadrati, la quantità di vendite che generano e il numero di clienti che servono ogni mese in media. Diventa ovvio che trovare i negozi più efficienti richiede di confrontare i record con più funzionalità.

Per applicare DEA dobbiamo definire qual è il nostro input e output. In questo caso l'output è ovviamente la quantità di vendite e il numero di clienti che servono. L'input è il numero di dipendenti e le dimensioni del negozio. Se eseguiamo DEA, stimeremo il rapporto output / input per ogni negozio con i pesi ideali (come discusso sopra). Quando avremo i loro rapporti, li classificheremo in base alla loro efficienza.

È tempo di matematica!

Ora che abbiamo avuto un'intuizione di come funziona la DEA, è tempo di scavare in matematica.

Il rapporto di efficienza di un particolare record i con input x e output y (entrambi i vettori con valori positivi) è stimato usando la seguente formula:

Dove u e v sono i pesi di ogni output e input del record, s è il numero di funzionalità di output e m è il numero di funzionalità di input.

Il problema di trovare i pesi migliori / ideali per un particolare record può essere formulato come segue:

Di nuovo quanto sopra è solo il modo matematico di trovare i pesi u e v che massimizzano l'efficienza del record i, a condizione che quei pesi non rendano nessuno degli altri record più efficiente del 100%.

Per risolvere questo problema dobbiamo usare la programmazione lineare. Purtroppo la programmazione lineare non ci consente di usare le frazioni e quindi abbiamo bisogno di trasformare la formulazione del problema come segue:

Dobbiamo sottolineare che il problema di programmazione lineare di cui sopra ci fornirà i pesi migliori per il record i e calcolerà la sua efficienza con quei pesi ottimali. Lo stesso deve essere ripetuto per ogni record nel nostro set di dati. Quindi se abbiamo n record, dobbiamo risolvere n problemi lineari separati. Ecco lo pseudocodice di come funziona la DEA:

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

Limitazioni dell'analisi dell'inviluppo dei dati

DEA è un'ottima tecnica ma ha i suoi limiti. Devi capire che DEA è come una scatola nera. Poiché i pesi utilizzati nel rapporto di efficacia di ciascun record sono diversi, cercare di spiegare come e perché ogni punteggio è stato calcolato non ha senso. Di solito ci concentriamo sulla classifica dei record piuttosto che sui valori effettivi dei punteggi di efficacia. Si noti inoltre che l'esistenza di estremi può causare valori molto bassi nei punteggi.

Tenere presente che DEA utilizza combinazioni lineari delle funzionalità per stimare i rapporti. Pertanto, se la loro combinazione lineare non è appropriata nella nostra applicazione, dobbiamo applicare trasformazioni sulle caratteristiche e renderle possibili una combinazione lineare. Un altro svantaggio di questa tecnica è che dobbiamo risolvere tanti problemi di programmazione lineare quanti sono i record, cosa che richiede molte risorse computazionali.

Un altro problema che DEA deve affrontare è che non funziona bene con dati ad alta dimensione. Per utilizzare DEA il numero di dimensioni d = m + s deve essere significativamente inferiore al numero di osservazioni. L'esecuzione di DEA quando d è molto vicino o maggiore di n non fornisce risultati utili poiché molto probabilmente tutti i record saranno ottimali. Tieni presente che quando aggiungi una nuova variabile di output (dimensione), tutti i record con il valore massimo in questa dimensione verranno trovati ottimali.

Infine, dovremmo notare che nella forma generale dell'algoritmo, i pesi delle funzionalità in DEA sono stimati dai dati e quindi non usano alcuna informazione precedente sull'importanza delle funzionalità che potremmo avere nel nostro problema (ovviamente è possibile incorporare queste informazioni come vincoli nel nostro problema lineare). Inoltre, i punteggi di efficienza calcolati sono in realtà i rapporti di efficienza limite superiore di ciascun record poiché sono calcolati in "situazioni ideali". Ciò significa che la DEA può essere una buona soluzione quando non è possibile fare ipotesi sull'importanza delle funzionalità, ma se disponiamo di informazioni preliminari o possiamo quantificare la loro importanza, si consiglia di utilizzare tecniche alternative.

Nel prossimo articolo, ti mostrerò come sviluppare un'implementazione di Analisi dell'inviluppo dei dati in JAVA e useremo il metodo per stimare la popolarità di pagine Web e articoli nei social network.

Se ti piace l'articolo, prenditi un momento per condividerlo su Twitter o Facebook. 🙂