Εργαλείο ανάλυσης περιγράμματος δεδομένων

• Φεβρουάριος 24, 2014
• Βασίλης Βρυνιώτης
• . 3 Σχόλια

Η Ανάλυση Επεξεργασίας Δεδομένων, γνωστή και ως DEA, είναι μια μη παραμετρική μέθοδος για την εκτέλεση ανάλυσης στα σύνορα. Χρησιμοποιεί γραμμικό προγραμματισμό για να εκτιμήσει την αποτελεσματικότητα πολλαπλών μονάδων λήψης αποφάσεων και χρησιμοποιείται συνήθως στην παραγωγή, τη διαχείριση και τα οικονομικά. Η τεχνική προτάθηκε για πρώτη φορά από Charnes, Cooper και Ρόδος το 1978 και από τότε έγινε ένα πολύτιμο εργαλείο για την εκτίμηση των συνόρων παραγωγής.

Ενημέρωση: Το Datumbox Machine Learning Framework είναι τώρα ανοιχτού κώδικα και δωρεάν κατεβάσετε. Ρίξτε μια ματιά στο πακέτο com.datumbox.framework.algorithms.dea για να δείτε την εφαρμογή του Data Envelopment Analysis στην Java.

Όταν αντιμετώπισα για πρώτη φορά τη μέθοδο πριν από 5-6 χρόνια, με εντυπωσίασε η πρωτοτυπία του αλγορίθμου, η απλότητά του και η ευφυΐα των ιδεών που χρησιμοποίησε. Ήμουν ακόμη πιο έκπληκτος που βλέπω ότι η τεχνική λειτούργησε πολύ έξω από τις συνηθισμένες εφαρμογές της (οικονομική, έρευνα λειτουργίας κ.λπ.), καθώς θα μπορούσε να εφαρμοστεί με επιτυχία στο Διαδικτυακό Μάρκετινγκ, την Κατάταξη Μηχανών Αναζήτησης και τη δημιουργία σύνθετων μετρήσεων. Παρ 'όλα αυτά, σήμερα η DEA συζητείται σχεδόν αποκλειστικά στο πλαίσιο της επιχείρησης. Γι 'αυτό, σε αυτό το άρθρο, θα καλύψω τις βασικές ιδέες και το μαθηματικό πλαίσιο πίσω από το DEA και στην επόμενη δημοσίευση θα σας δείξω μερικές νέες εφαρμογές του αλγορίθμου σε διαδικτυακές εφαρμογές.

Γιατί είναι ενδιαφέρουσα η ανάλυση φακέλων δεδομένων;

Η Ανάλυση Ανάπτυξης Δεδομένων είναι μια μέθοδος που μας επιτρέπει να συγκρίνουμε και να βαθμολογούμε αρχεία (καταστήματα, εργαζόμενοι, εργοστάσια, ιστοσελίδες, καμπάνιες μάρκετινγκ κ.λπ.) με βάση τα χαρακτηριστικά τους (βάρος, μέγεθος, κόστος, έσοδα και άλλες μετρήσεις ή KPI) χωρίς να κάνουμε προηγούμενες παραδοχές σχετικά με τη σημασία ή το βάρος των χαρακτηριστικών. Το πιο ενδιαφέρον μέρος αυτής της τεχνικής είναι ότι μας επιτρέπει να συγκρίνουμε εγγραφές που αποτελούνται από πολλά χαρακτηριστικά που έχουν εντελώς διαφορετικές μονάδες μέτρησης. Αυτό σημαίνει ότι μπορούμε να έχουμε δίσκους με χαρακτηριστικά που μετράται σε χιλιόμετρα, κιλά ή νομισματικές μονάδες και εξακολουθούμε να είμαστε σε θέση να τα συγκρίνουμε, να τα ταξινομήσουμε και να βρούμε τα αρχεία με τις καλύτερες / χειρότερες και μέσες επιδόσεις. Ακούγεται ενδιαφέρον? Συνέχισε να διαβάζεις.

Η περιγραφή και οι παραδοχές της Ανάλυσης Δεικτών

Όπως συζητήσαμε νωρίτερα, το DEA είναι μια μέθοδος που εφευρέθηκε για τη μέτρηση της παραγωγικότητας στις επιχειρήσεις. Έτσι, πολλές από τις ιδέες της προέρχονται από τον τρόπο με τον οποίο μετράται η παραγωγικότητα σε αυτό το πλαίσιο. Ένα από τα βασικά χαρακτηριστικά της μεθόδου είναι ο διαχωρισμός των χαρακτηριστικών εγγραφής σε δύο κατηγορίες: είσοδος και έξοδος. Για παράδειγμα, αν μετρήσουμε την απόδοση ενός αυτοκινήτου, θα μπορούσαμε να πούμε ότι η είσοδος είναι τα λίτρα βενζίνης και η έξοδος είναι ο αριθμός χιλιομέτρων που ταξιδεύει.

Στο DEA, όλα τα χαρακτηριστικά πρέπει να είναι θετικά και θεωρείται ότι όσο υψηλότερη είναι η αξία τους, τόσο μεγαλύτερη είναι η είσοδος / έξοδος τους. Επιπλέον, η Ανάλυση Ανάπτυξης Δεδομένων προϋποθέτει ότι τα χαρακτηριστικά μπορούν να συνδυαστούν γραμμικά ως σταθμισμένο άθροισμα μη αρνητικών βαρών και να σχηματίσουν μια αναλογία μεταξύ εισόδου και εξόδου που θα μετρήσει την απόδοση κάθε εγγραφής. Για να είναι αποτελεσματική μια εγγραφή, πρέπει να μας δίνει μια «καλή» έξοδο σε σχέση με την παρεχόμενη είσοδο. Η αποδοτικότητα μετράται από την αναλογία μεταξύ εξόδου και εισόδου και στη συνέχεια συγκρίνεται με την αναλογία των άλλων εγγραφών.

Η έξυπνη ιδέα πίσω από το DEA

Αυτό που καλύψαμε μέχρι τώρα είναι μια κοινή λογική / πρακτική. Χρησιμοποιούμε τις εισόδους και τις εξόδους, σταθμισμένα ποσά και αναλογίες για να ταξινομήσουμε τα αρχεία μας. Η έξυπνη ιδέα του DEA είναι ο τρόπος υπολογισμού των βαρών των χαρακτηριστικών. Αντί να χρειαστεί να ορίσετε τα βάρη των χαρακτηριστικών και να αποφασίσετε για τη σημασία τους πριν από την εκτέλεση της ανάλυσης, η Ανάλυση φακέλων δεδομένων τα υπολογίζει από τα δεδομένα. Επιπλέον, τα βάρη ΔΕΝ είναι τα ίδια για κάθε δίσκο!

Εδώ είναι πώς η DEA επιλέγει τα βάρη: Προσπαθούμε να μεγιστοποιήσουμε την αναλογία κάθε εγγραφής επιλέγοντας τα κατάλληλα βάρη χαρακτηριστικών. ταυτόχρονα αν και πρέπει να διασφαλίσουμε ότι εάν χρησιμοποιήσουμε τα ίδια βάρη για να υπολογίσουμε τους λόγους όλων των άλλων εγγραφών, καμία από αυτές δεν θα γίνει μεγαλύτερη από 1.

Η ιδέα ακούγεται λίγο περίεργη στην αρχή. Δεν θα οδηγήσει σε υπολογισμό διαφορετικών σταθμισμένων αναλογιών; Η απάντηση είναι ναι. Αυτό δεν σημαίνει ότι πραγματικά υπολογίζουμε διαφορετικά τις αναλογίες για κάθε δίσκο; Η απάντηση είναι και πάλι ναι. Πώς λειτουργεί λοιπόν; Η απάντηση είναι απλή: Για κάθε δίσκο, δεδομένων των χαρακτηριστικών του, προσπαθούμε να βρούμε την «ιδανική κατάσταση» (βάρη) στην οποία η αναλογία της θα ήταν όσο το δυνατόν υψηλότερη και κάνοντάς την έτσι όσο το δυνατόν πιο αποτελεσματική. ΑΛΛΑ ταυτόχρονα, δεδομένης αυτής της «ιδανικής κατάστασης», καμία από τις αναλογίες εξόδου / εισόδου των άλλων εγγραφών δεν πρέπει να είναι μεγαλύτερη από 1, που σημαίνει ότι δεν μπορούν να είναι πιο αποτελεσματικές από το 100%! Μόλις υπολογίσουμε τους λόγους όλων των εγγραφών κάτω από κάθε «ιδανική κατάσταση», χρησιμοποιούμε τους λόγους τους για να τους ταξινομήσουμε.

Έτσι, η κύρια ιδέα του DEA μπορεί να συνοψιστεί στα ακόλουθα: «Βρείτε την ιδανική κατάσταση στην οποία μπορούμε να επιτύχουμε την καλύτερη βαθμολογία με βάση τα χαρακτηριστικά κάθε δίσκου. Στη συνέχεια, υπολογίστε αυτήν την ιδανική αναλογία κάθε δίσκου και χρησιμοποιήστε τη για να συγκρίνετε την αποτελεσματικότητά τους ».

Ας δούμε ένα παράδειγμα

Ας δούμε ένα παράδειγμα όπου θα μπορούσαμε να χρησιμοποιήσουμε το DEA.

Ας υποθέσουμε ότι μας ενδιαφέρει να αξιολογήσουμε την αποτελεσματικότητα των καταστημάτων σούπερ μάρκετ μιας συγκεκριμένης αλυσίδας με βάση ορισμένα χαρακτηριστικά: τον συνολικό αριθμό των εργαζομένων, το μέγεθος του καταστήματος σε τετραγωνικά μέτρα, το ποσό των πωλήσεων που δημιουργούν και τον αριθμό των πελατών που εξυπηρετούν κάθε μήνα κατά μέσο όρο. Γίνεται προφανές ότι η εύρεση των πιο αποτελεσματικών καταστημάτων απαιτεί από εμάς να συγκρίνουμε αρχεία με πολλές δυνατότητες.

Για να εφαρμόσουμε το DEA πρέπει να ορίσουμε ποια είναι η είσοδος και η παραγωγή μας. Σε αυτήν την περίπτωση, η παραγωγή είναι προφανώς το ποσό των πωλήσεων και ο αριθμός των πελατών που εξυπηρετούν. Η είσοδος είναι ο αριθμός των υπαλλήλων και το μέγεθος του καταστήματος. Εάν εκτελέσουμε DEA, θα εκτιμήσουμε την αναλογία εξόδου προς είσοδο για κάθε κατάστημα κάτω από τα ιδανικά βάρη (όπως συζητήθηκε παραπάνω). Μόλις έχουμε τους λόγους τους, θα τους κατατάξουμε ανάλογα με την αποτελεσματικότητά τους.

Είναι ώρα μαθηματικών!

Τώρα που έχουμε μια διαίσθηση για το πώς λειτουργεί το DEA, ήρθε η ώρα να ανακαλύψουμε τα μαθηματικά.

Ο λόγος απόδοσης μιας συγκεκριμένης εγγραφής i με είσοδο x και έξοδο y (και οι δύο διανύσματα χαρακτηριστικών με θετικές τιμές) εκτιμάται χρησιμοποιώντας τον ακόλουθο τύπο:

Όπου u και v είναι τα βάρη κάθε εξόδου και εισόδου της εγγραφής, το s είναι ο αριθμός των χαρακτηριστικών εξόδου και το m είναι ο αριθμός των χαρακτηριστικών εισόδου.

Το πρόβλημα της εύρεσης των καλύτερων / ιδανικών βαρών για μια συγκεκριμένη εγγραφή μπορώ να διατυπωθεί ως εξής:

Και πάλι τα παραπάνω είναι απλώς ο μαθηματικός τρόπος εύρεσης των βαρών u και v που μεγιστοποιούν την αποδοτικότητα της εγγραφής i, υπό την προϋπόθεση ότι αυτά τα βάρη δεν θα κάνουν καμία από τις άλλες εγγραφές πιο αποτελεσματική από το 100%.

Για να λύσουμε αυτό το πρόβλημα πρέπει να χρησιμοποιήσουμε γραμμικό προγραμματισμό. Δυστυχώς, ο γραμμικός προγραμματισμός δεν μας επιτρέπει να χρησιμοποιούμε κλάσματα και ως εκ τούτου πρέπει να μετατρέψουμε τη διατύπωση του προβλήματος ως εξής:

Πρέπει να τονίσουμε ότι το παραπάνω πρόβλημα γραμμικού προγραμματισμού θα μας δώσει τα καλύτερα βάρη για την εγγραφή i και θα υπολογίσουμε την αποδοτικότητά του κάτω από αυτά τα βέλτιστα βάρη. Το ίδιο πρέπει να επαναλαμβάνεται για κάθε εγγραφή στο σύνολο δεδομένων μας. Επομένως, εάν έχουμε n εγγραφές, πρέπει να λύσουμε και ξεχωριστά γραμμικά προβλήματα. Εδώ είναι ο ψευδοκώδικας για το πώς λειτουργεί το DEA:

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

Περιορισμοί της ανάλυσης φακέλων δεδομένων

Το DEA είναι μια εξαιρετική τεχνική αλλά έχει τους περιορισμούς του. Πρέπει να καταλάβετε ότι το DEA είναι σαν ένα μαύρο κουτί. Δεδομένου ότι τα βάρη που χρησιμοποιούνται στην αναλογία αποτελεσματικότητας κάθε δίσκου είναι διαφορετικά, προσπαθώντας να εξηγήσουμε πώς και γιατί υπολογίστηκε κάθε βαθμολογία είναι άσκοπο. Συνήθως εστιάζουμε στην κατάταξη των εγγραφών και όχι στις πραγματικές τιμές των αποτελεσμάτων αποτελεσματικότητας. Σημειώστε επίσης ότι η ύπαρξη ακραίων μπορεί να προκαλέσει τις βαθμολογίες να έχουν πολύ χαμηλές τιμές.

Έχετε υπόψη ότι το DEA χρησιμοποιεί γραμμικούς συνδυασμούς των χαρακτηριστικών για να εκτιμήσει τους λόγους. Επομένως, εάν ο συνδυασμός τους γραμμικά δεν είναι κατάλληλος στην εφαρμογή μας, πρέπει να εφαρμόσουμε μετασχηματισμούς στα χαρακτηριστικά και να τους επιτρέψουμε να συνδυάζονται γραμμικά. Ένα άλλο μειονέκτημα αυτής της τεχνικής είναι ότι πρέπει να λύσουμε τόσα προβλήματα γραμμικού προγραμματισμού όσο και τον αριθμό των εγγραφών, κάτι που απαιτεί πολλούς υπολογιστικούς πόρους.

Ένα άλλο πρόβλημα που αντιμετωπίζει η DEA είναι ότι δεν λειτουργεί καλά με δεδομένα υψηλής διαστάσεων. Για να χρησιμοποιήσετε το DEA, ο αριθμός των διαστάσεων d = m + s πρέπει να είναι σημαντικά χαμηλότερος από τον αριθμό των παρατηρήσεων. Η εκτέλεση του DEA όταν το d είναι πολύ κοντά ή μεγαλύτερο από το n δεν παρέχει χρήσιμα αποτελέσματα, καθώς πιθανότατα όλες οι εγγραφές θα είναι βέλτιστες. Σημειώστε ότι καθώς προσθέτετε μια νέα μεταβλητή εξόδου (διάσταση), όλες οι εγγραφές με μέγιστη τιμή σε αυτήν την ιδιότητα θα βρεθούν βέλτιστες.

Τέλος, πρέπει να σημειώσουμε ότι στη γενική μορφή του αλγορίθμου, τα βάρη των δυνατοτήτων στο DEA υπολογίζονται από τα δεδομένα και επομένως δεν χρησιμοποιούν προηγούμενες πληροφορίες σχετικά με τη σημασία των δυνατοτήτων που ενδέχεται να έχουμε στο πρόβλημά μας (φυσικά είναι δυνατόν να ενσωματώσουμε αυτές τις πληροφορίες ως περιορισμούς στο γραμμικό μας πρόβλημα). Επιπλέον, οι βαθμολογίες απόδοσης που υπολογίζονται είναι στην πραγματικότητα οι ανώτεροι λόγοι απόδοσης κάθε εγγραφής, δεδομένου ότι υπολογίζονται υπό «ιδανικές καταστάσεις». Αυτό σημαίνει ότι το DEA μπορεί να είναι μια καλή λύση όταν δεν είναι δυνατόν να κάνουμε υποθέσεις σχετικά με τη σημασία των χαρακτηριστικών, αλλά εάν έχουμε προηγούμενες πληροφορίες ή μπορούμε να ποσοτικοποιήσουμε τη σημασία τους, τότε συνιστάται η χρήση εναλλακτικών τεχνικών.

Στο επόμενο άρθρο, θα σας δείξω πώς να αναπτύξετε μια εφαρμογή του Ανάλυση φακέλου δεδομένων στην JAVA και θα χρησιμοποιήσουμε τη μέθοδο για την εκτίμηση της δημοτικότητας των ιστοσελίδων και των άρθρων στα δίκτυα κοινωνικών μέσων.

Αν σας αρέσει το άρθρο, αφιερώστε λίγο χρόνο για να το μοιραστείτε στο Twitter ή στο Facebook. 🙂