Tutorial zur Datenumhüllungsanalyse

• 24. Februar 2014
• Vasilis Vryniotis
• . 3 Kommentare

Die Datenumhüllungsanalyse, auch als DEA bekannt, ist eine nicht parametrische Methode zur Durchführung von Grenzanalysen. Es verwendet lineare Programmierung, um die Effizienz mehrerer Entscheidungseinheiten abzuschätzen, und wird häufig in Produktion, Management und Wirtschaftlichkeit verwendet. Die Technik wurde zuerst von vorgeschlagen Charnes, Cooper und Rhodos 1978 und seitdem wurde es ein wertvolles Instrument zur Schätzung der Produktionsgrenzen.

Update: Das Datumbox Machine Learning Framework ist jetzt Open Source und kostenlos für herunterladen. Schauen Sie sich das Paket com.datumbox.framework.algorithms.dea an, um die Implementierung der Datenumhüllungsanalyse in Java zu sehen.

Als ich vor 5-6 Jahren zum ersten Mal auf die Methode stieß, war ich erstaunt über die Originalität des Algorithmus, seine Einfachheit und die Klugheit der verwendeten Ideen. Umso mehr war ich erstaunt zu sehen, dass die Technik außerhalb ihrer üblichen Anwendungen (Finanzen, Betriebsforschung usw.) gut funktionierte, da sie erfolgreich im Online-Marketing, im Suchmaschinen-Ranking und zur Erstellung zusammengesetzter Metriken angewendet werden konnte. Trotzdem wird DEA heute fast ausschließlich im geschäftlichen Kontext diskutiert. Aus diesem Grund werde ich in diesem Artikel die grundlegenden Ideen und mathematischen Rahmenbedingungen hinter DEA behandeln und Ihnen im nächsten Beitrag einige neuartige Anwendungen des Algorithmus für Webanwendungen zeigen.

Warum ist die Datenumhüllungsanalyse interessant?

Die Datenumhüllungsanalyse ist eine Methode, mit der wir Datensätze (Geschäfte, Mitarbeiter, Fabriken, Webseiten, Marketingkampagnen usw.) anhand ihrer Funktionen (Gewicht, Größe, Kosten, Umsatz und andere Kennzahlen oder KPIs) vergleichen und bewerten können, ohne vorher Annahmen treffen zu müssen die Wichtigkeit oder das Gewicht der Merkmale. Der interessanteste Teil dieser Technik besteht darin, dass wir Datensätze vergleichen können, die aus mehreren Merkmalen mit völlig unterschiedlichen Maßeinheiten bestehen. Dies bedeutet, dass wir Aufzeichnungen mit Merkmalen haben können, die in Kilometern, Kilogramm oder Währungseinheiten gemessen werden, und dennoch in der Lage sind, diese zu vergleichen, zu bewerten und die Aufzeichnungen mit der besten / schlechtesten und durchschnittlichsten Leistung zu finden. Klingt interessant? Weiter lesen.

Die Beschreibung und Annahmen der Datenumhüllungsanalyse

Wie bereits erwähnt, ist DEA eine Methode, die erfunden wurde, um die Produktivität in Unternehmen zu messen. Einige seiner Ideen stammen daher aus der Art und Weise, wie die Produktivität in diesem Zusammenhang gemessen wird. Eines der Hauptmerkmale der Methode ist die Aufteilung der Datensatzmerkmale in zwei Kategorien: Eingabe und Ausgabe. Wenn wir zum Beispiel den Wirkungsgrad eines Autos messen, können wir sagen, dass der Input die Liter Benzin und der Output die Anzahl der Kilometer ist, die es fährt.

In DEA müssen alle Merkmale positiv sein, und es wird angenommen, dass je höher ihr Wert, desto höher ihre Eingabe / Ausgabe ist. Zusätzlich wird bei der Datenumhüllungsanalyse davon ausgegangen, dass die Features linear als gewichtete Summe nicht negativer Gewichte kombiniert werden können und ein Verhältnis zwischen Eingabe und Ausgabe bilden, das die Effizienz jedes Datensatzes misst. Damit ein Datensatz effizient ist, muss er eine „gute“ Ausgabe im Verhältnis zur bereitgestellten Eingabe liefern. Die Effizienz wird anhand des Verhältnisses zwischen Ausgabe und Eingabe gemessen und dann mit dem Verhältnis der anderen Datensätze verglichen.

Die geniale Idee hinter DEA

Was wir bisher behandelt haben, ist ein gesunder Menschenverstand / eine gesunde Praxis. Wir verwenden Inputs und Outputs, gewichtete Summen und Verhältnisse, um unsere Datensätze zu ordnen. Die clevere Idee von DEA besteht darin, dass die Gewichte der Merkmale berechnet werden. Anstatt die Gewichte der Features festlegen und ihre Wichtigkeit festlegen zu müssen, bevor wir die Analyse ausführen, berechnet die Datenumhüllungsanalyse sie aus den Daten. Außerdem sind die Gewichte NICHT für jeden Datensatz gleich!

So wählt DEA die Gewichte aus: Wir versuchen, das Verhältnis jedes Datensatzes zu maximieren, indem wir die entsprechenden Merkmalsgewichte auswählen. Gleichzeitig müssen wir jedoch sicherstellen, dass, wenn wir zur Berechnung der Verhältnisse aller anderen Datensätze dieselben Gewichte verwenden, keiner von ihnen größer als 1 wird.

Die Idee klingt am Anfang etwas seltsam. Wird dies nicht zur Berechnung unterschiedlich gewichteter Verhältnisse führen? Die Antwort ist ja. Bedeutet dies nicht, dass wir die Verhältnisse für jeden Datensatz tatsächlich unterschiedlich berechnen? Die Antwort lautet wieder ja. Wie funktioniert das? Die Antwort ist einfach: Für jeden Datensatz versuchen wir aufgrund seiner Eigenschaften, die „ideale Situation“ (Gewichte) zu finden, in der sein Verhältnis so hoch wie möglich wäre, und machen ihn so effektiv wie möglich. ABER gleichzeitig sollte angesichts dieser „idealen Situation“ keines der Ausgabe- / Eingabeverhältnisse der anderen Datensätze größer als 1 sein, was bedeutet, dass sie nicht effektiver als 100% sein können! Sobald wir die Verhältnisse aller Datensätze unter jeder „idealen Situation“ berechnet haben, verwenden wir ihre Verhältnisse, um sie zu ordnen.

Die Hauptidee von DEA lässt sich also wie folgt zusammenfassen: „Finden Sie die ideale Situation, in der wir basierend auf den Merkmalen jedes Datensatzes die beste Verhältnisbewertung erzielen können. Berechnen Sie dann dieses ideale Verhältnis für jeden Datensatz und vergleichen Sie damit seine Wirksamkeit. “

Lass uns ein Beispiel sehen

Sehen wir uns ein Beispiel an, in dem wir DEA verwenden könnten.

Nehmen wir an, wir möchten die Effizienz der Supermarktgeschäfte einer bestimmten Kette anhand einer Reihe von Merkmalen bewerten: der Gesamtzahl der Mitarbeiter, der Größe des Geschäfts in Quadratmetern, der Umsatzmenge und der Anzahl der Kunden dass sie durchschnittlich jeden Monat dienen. Es wird deutlich, dass wir zum Finden der effizientesten Geschäfte Datensätze mit mehreren Funktionen vergleichen müssen.

Um DEA anzuwenden, müssen wir definieren, welche unsere Eingabe und Ausgabe ist. In diesem Fall ist die Ausgabe offensichtlich die Menge des Umsatzes und die Anzahl der Kunden, die sie bedienen. Die Eingabe ist die Anzahl der Mitarbeiter und die Größe des Geschäfts. Wenn wir DEA ausführen, schätzen wir das Verhältnis von Ausgabe zu Eingabe für jedes Geschäft unter den idealen Gewichten (wie oben erläutert). Sobald wir ihre Verhältnisse haben, werden wir sie nach ihrer Effizienz ordnen.

Es ist Mathezeit!

Jetzt, da wir eine Vorstellung davon haben, wie DEA funktioniert, ist es Zeit, sich mit Mathematik zu beschäftigen.

Das Effizienzverhältnis eines bestimmten Datensatzes i mit x-Eingabe und y-Ausgabe (beide Merkmalsvektoren mit positiven Werten) wird unter Verwendung der folgenden Formel geschätzt:

Dabei sind u und v die Gewichte jeder Ausgabe und Eingabe des Datensatzes, s die Anzahl der Ausgabemerkmale und m die Anzahl der Eingabemerkmale.

Das Problem, die besten / idealen Gewichte für einen bestimmten Datensatz zu finden, kann wie folgt formuliert werden:

Wiederum ist das Obige nur der mathematische Weg, um die Gewichte u und v zu finden, die die Effizienz von Datensatz i maximieren, vorausgesetzt, dass diese Gewichte keinen der anderen Datensätze effizienter als 100% machen.

Um dieses Problem zu lösen, müssen wir lineare Programmierung verwenden. Leider erlaubt uns die lineare Programmierung nicht, Brüche zu verwenden, und daher müssen wir die Formulierung des Problems wie folgt transformieren:

Wir sollten betonen, dass das obige lineare Programmierproblem uns die besten Gewichte für Datensatz i liefert und seine Effizienz unter diesen optimalen Gewichten berechnet. Dasselbe muss für jeden Datensatz in unserem Datensatz wiederholt werden. Wenn wir also n Datensätze haben, müssen wir n separate lineare Probleme lösen. Hier ist der Pseudocode, wie DEA funktioniert:

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

Einschränkungen der Datenumhüllungsanalyse

DEA ist eine großartige Technik, hat aber ihre Grenzen. Sie müssen verstehen, dass DEA wie eine Black Box ist. Da die Gewichte, die im Effektivitätsverhältnis jedes Datensatzes verwendet werden, unterschiedlich sind, ist es sinnlos zu erklären, wie und warum jede Punktzahl berechnet wurde. Normalerweise konzentrieren wir uns eher auf die Rangfolge der Datensätze als auf die tatsächlichen Werte der Effektivitätswerte. Beachten Sie auch, dass das Vorhandensein von Extremen dazu führen kann, dass die Werte sehr niedrige Werte haben.

Beachten Sie, dass DEA lineare Kombinationen der Merkmale verwendet, um die Verhältnisse zu schätzen. Wenn eine lineare Kombination in unserer Anwendung nicht angemessen ist, müssen wir Transformationen auf die Features anwenden und sie linear kombinieren lassen. Ein weiterer Nachteil dieser Technik besteht darin, dass wir so viele lineare Programmierprobleme wie die Anzahl der Datensätze lösen müssen, was viele Rechenressourcen erfordert.

Ein weiteres Problem, mit dem DEA konfrontiert ist, besteht darin, dass es mit hochdimensionalen Daten nicht gut funktioniert. Um DEA verwenden zu können, muss die Anzahl der Dimensionen d = m + s signifikant niedriger sein als die Anzahl der Beobachtungen. Das Ausführen von DEA, wenn d sehr nahe oder größer als n ist, liefert keine nützlichen Ergebnisse, da höchstwahrscheinlich alle Datensätze als optimal befunden werden. Beachten Sie, dass beim Hinzufügen einer neuen Ausgabevariablen (Dimension) alle Datensätze mit dem Maximalwert in dieser Dimension als optimal befunden werden.

Schließlich sollten wir beachten, dass in der allgemeinen Form des Algorithmus die Gewichte der Merkmale in DEA aus den Daten geschätzt werden und daher keine vorherigen Informationen über die Bedeutung von Merkmalen verwendet werden, die wir (natürlich) in unserem Problem haben könnten Es ist möglich, diese Informationen als Einschränkungen in unser lineares Problem aufzunehmen. Zusätzlich sind die berechneten Effizienzwerte tatsächlich die Obergrenzen-Effizienzverhältnisse jedes Datensatzes, da sie unter „idealen Situationen“ berechnet werden. Dies bedeutet, dass DEA eine gute Lösung sein kann, wenn keine Annahmen über die Wichtigkeit der Merkmale getroffen werden können. Wenn wir jedoch über vorherige Informationen verfügen oder deren Wichtigkeit quantifizieren können, wird die Verwendung alternativer Techniken empfohlen.

Im nächsten Artikel werde ich Ihnen zeigen, wie Sie eine Implementierung von entwickeln Datenumhüllungsanalyse in JAVA und wir werden die Methode verwenden, um die Popularität von Webseiten und Artikeln in sozialen Netzwerken abzuschätzen.

Wenn Ihnen der Artikel gefällt, nehmen Sie sich einen Moment Zeit, um ihn auf Twitter oder Facebook zu teilen. 🙂