Samouczek dotyczący analizy obwiedni danych

• 24 lutego 2014 r.
• Wasilis Wryniotis
• . 3 komentarzy

Analiza zakresu danych, znana również jako DEA, jest nieparametryczną metodą przeprowadzania analizy granic. Wykorzystuje programowanie liniowe do szacowania wydajności wielu jednostek decyzyjnych i jest powszechnie stosowany w produkcji, zarządzaniu i ekonomii. Technikę po raz pierwszy zaproponował Charnes, Cooper i Rhodes w 1978 roku i od tego czasu stał się cennym narzędziem do szacowania granic produkcji.

Aktualizacja: Platforma uczenia maszynowego Datumbox jest teraz open-source i bezpłatna pobieranie. Sprawdź pakiet com.datumbox.framework.algorithms.dea, aby zobaczyć implementację analizy otoczenia danych w Javie.

Kiedy po raz pierwszy zetknąłem się z metodą 5-6 lat temu, byłem zdumiony oryginalnością algorytmu, jego prostotą i sprytem zastosowanych pomysłów. Byłem jeszcze bardziej zdumiony, gdy zauważyłem, że technika działa dobrze poza jej zwykłymi zastosowaniami (finansami, badaniami operacyjnymi itp.), Ponieważ można ją z powodzeniem stosować w marketingu online, rankingu w wyszukiwarkach i do tworzenia wskaźników złożonych. Mimo to dziś DEA jest omawiana prawie wyłącznie w kontekście biznesowym. Dlatego w tym artykule omówię podstawowe idee i ramy matematyczne stojące za DEA, aw następnym poście pokażę kilka nowatorskich zastosowań algorytmu w aplikacjach internetowych.

Dlaczego analiza zakresu danych jest interesująca?

Analiza otoczenia danych to metoda, która umożliwia nam porównywanie i uszeregowanie rekordów (sklepów, pracowników, fabryk, stron internetowych, kampanii marketingowych itp.) Na podstawie ich funkcji (waga, rozmiar, koszt, przychody i inne wskaźniki lub wskaźniki KPI) bez wcześniejszego zakładania znaczenie lub wagę funkcji. Najbardziej interesującą częścią tej techniki jest to, że pozwala nam porównywać rekordy składające się z wielu cech, które mają zupełnie różne jednostki miary. Oznacza to, że możemy mieć rekordy z cechami mierzonymi w kilometrach, kilogramach lub jednostkach pieniężnych i nadal być w stanie je porównać, uszeregować i znaleźć najlepsze / najgorsze i średnie wyniki. Brzmi interesująco? Czytaj dalej.

Opis i założenia analizy zakresu danych

Jak omówiliśmy wcześniej, DEA to metoda, która została wymyślona do pomiaru produktywności w biznesie. W związku z tym kilka z jego pomysłów wynika ze sposobu mierzenia wydajności w tym kontekście. Jedną z głównych cech metody jest rozdzielenie cech rekordu na dwie kategorie: wejście i wyjście. Na przykład, jeśli mierzymy sprawność samochodu, możemy powiedzieć, że wkład to litry benzyny, a wyjście to liczba kilometrów, które przejeżdża.

W DEA wszystkie cechy muszą być dodatnie i zakłada się, że im wyższa ich wartość, tym większy jest ich wkład / wyjście. Dodatkowo Analiza obwiedni danych zakłada, że ​​cechy mogą być łączone liniowo jako suma ważona nieujemnych wag i tworzyć stosunek między wejściem a wyjściem, który będzie mierzył efektywność każdego rekordu. Aby rekord był skuteczny, musi dawać „dobry” wynik w stosunku do dostarczonego wkładu. Efektywność mierzy się stosunkiem produkcji do nakładów, a następnie porównuje się ją ze stosunkiem innych rekordów.

Genialny pomysł stojący za DEA

To, co do tej pory omówiliśmy, to zdrowy rozsądek / praktyka. Do uszeregowania naszych rekordów używamy danych wejściowych i wyjściowych, sum ważonych i współczynników. Sprytny pomysł DEA polega na sposobie obliczania wagi cech. Zamiast ustawiać wagi cech i decydować o ich znaczeniu przed przeprowadzeniem analizy, Analiza otoczenia danych oblicza je na podstawie danych. Ponadto wagi NIE są takie same dla każdego rekordu!

Oto jak DEA wybiera wagi: Staramy się zmaksymalizować stosunek każdego rekordu, wybierając odpowiednie wagi cech; jednocześnie jednak musimy zapewnić, że jeśli użyjemy tych samych wag do obliczenia stosunków wszystkich innych rekordów, żaden z nich nie będzie większy niż 1.

Pomysł na początku brzmi trochę dziwnie. Czy nie doprowadzi to do obliczenia współczynników ważonych o różnym znaczeniu? Odpowiedź brzmi tak. Czy nie oznacza to, że faktycznie obliczamy współczynniki dla każdego rekordu inaczej? Odpowiedź znowu brzmi: tak. Jak to działa? Odpowiedź jest prosta: dla każdego rekordu, biorąc pod uwagę jego charakterystykę, staramy się znaleźć „sytuację idealną” (wagi), w której jego stosunek byłby jak najwyższy, a przez to jak najbardziej efektywny. ALE w tym samym czasie, biorąc pod uwagę tę „idealną sytuację”, żaden ze współczynników wyjścia / wejścia innych rekordów nie powinien być większy niż 1, co oznacza, że ​​nie mogą być bardziej efektywne niż 100%! Po obliczeniu stosunków wszystkich rekordów w każdej „idealnej sytuacji” używamy ich do uszeregowania ich.

Tak więc główną ideę DEA można podsumować w następujący sposób: „Znajdź idealną sytuację, w której możemy osiągnąć najlepszy wynik w oparciu o cechy każdego rekordu. Następnie oblicz ten idealny stosunek każdego rekordu i użyj go do porównania ich skuteczności ”.

Zobaczmy przykład

Zobaczmy przykład, w którym moglibyśmy użyć DEA.

Załóżmy, że interesuje nas ocena efektywności sklepów supermarketów danej sieci na podstawie szeregu cech: całkowitej liczby pracowników, wielkości sklepu w metrach kwadratowych, wielkości sprzedaży, jaką generują i liczby klientów że służą średnio co miesiąc. Staje się oczywiste, że znalezienie najbardziej wydajnych sklepów wymaga od nas porównania rekordów z wieloma funkcjami.

Aby zastosować DEA, musimy zdefiniować, co jest naszym wejściem i wyjściem. W tym przypadku wynikiem jest oczywiście wielkość sprzedaży i liczba klientów, których obsługują. Dane wejściowe to liczba pracowników i wielkość sklepu. Jeśli uruchomimy DEA, oszacujemy stosunek produkcji do wkładu dla każdego sklepu przy idealnych wagach (jak omówiono powyżej). Kiedy już mamy ich współczynniki, uszeregujemy je według ich efektywności.

Czas na matematykę!

Teraz, gdy mamy intuicję, jak działa DEA, czas zagłębić się w matematykę.

Współczynnik sprawności danego rekordu i z wejściem x i wyjściem y (oba wektory cech o wartościach dodatnich) szacuje się za pomocą następującego wzoru:

Gdzie uiv to wagi każdego wyjścia i wejścia rekordu, s to liczba cech wyjściowych, am to liczba cech wejściowych.

Problem znalezienia najlepszych / idealnych wag dla konkretnego rekordu i można sformułować następująco:

Ponownie, powyższe jest tylko matematycznym sposobem znalezienia wag uiv, które maksymalizują wydajność rekordu i, pod warunkiem, że te wagi nie spowodują, że żaden z pozostałych rekordów nie będzie bardziej wydajny niż 100%.

Aby rozwiązać ten problem, musimy użyć programowania liniowego. Niestety programowanie liniowe nie pozwala nam na użycie ułamków i dlatego musimy przekształcić sformułowanie problemu w następujący sposób:

Powinniśmy podkreślić, że powyższy problem programowania liniowego da nam najlepsze wagi dla rekordu i i obliczy jego wydajność pod tymi optymalnymi wagami. To samo należy powtórzyć dla każdego rekordu w naszym zbiorze danych. Więc jeśli mamy n rekordów, musimy rozwiązać n oddzielnych zadań liniowych. Oto pseudokod opisujący, jak działa DEA:

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

Ograniczenia analizy zakresu danych

DEA to świetna technika, ale ma swoje ograniczenia. Musisz zrozumieć, że DEA jest jak czarna skrzynka. Ponieważ wagi używane we współczynniku efektywności każdego rekordu są różne, próba wyjaśnienia, w jaki sposób i dlaczego obliczono każdy wynik, jest bezcelowa. Zwykle koncentrujemy się na rankingu rekordów, a nie na rzeczywistych wartościach wyników skuteczności. Należy również zauważyć, że istnienie ekstremów może spowodować, że wyniki będą miały bardzo niskie wartości.

Należy pamiętać, że DEA wykorzystuje liniowe kombinacje cech do oszacowania współczynników. Jeśli więc łączenie ich liniowo nie jest właściwe w naszej aplikacji, musimy zastosować transformacje na cechach i umożliwić ich liniowe łączenie. Inną wadą tej techniki jest to, że musimy rozwiązać tyle problemów programowania liniowego, ile jest rekordów, co wymaga dużej ilości zasobów obliczeniowych.

Innym problemem, z którym boryka się DEA, jest to, że nie działa dobrze z wysokowymiarowymi danymi. Aby użyć DEA, liczba wymiarów d = m + s musi być znacznie mniejsza niż liczba obserwacji. Uruchamianie DEA, gdy d jest bardzo blisko lub większe niż n, nie daje użytecznych wyników, ponieważ najprawdopodobniej wszystkie rekordy zostaną uznane za optymalne. Zwróć uwagę, że po dodaniu nowej zmiennej wyjściowej (wymiaru) wszystkie rekordy z maksymalną wartością w tym wymiarze zostaną uznane za optymalne.

Na koniec należy zauważyć, że w ogólnej postaci algorytmu wagi funkcji w DEA są szacowane na podstawie danych, a zatem nie wykorzystują żadnych wcześniejszych informacji o znaczeniu cech, które możemy mieć w naszym problemie (oczywiście możliwe jest włączenie tych informacji jako ograniczeń do naszego problemu liniowego). Ponadto obliczane wyniki wydajności są w rzeczywistości górnymi granicznymi współczynnikami wydajności każdego rekordu, ponieważ są one obliczane w „sytuacjach idealnych”. Oznacza to, że DEA może być dobrym rozwiązaniem, gdy nie można poczynić żadnych założeń co do ważności cech, ale jeśli mamy jakieś wcześniejsze informacje lub możemy oszacować ich znaczenie, wówczas zaleca się użycie technik alternatywnych.

W następnym artykule pokażę, jak opracować implementację Analiza otoczenia danych w JAVA i wykorzystamy tę metodę do oszacowania popularności stron internetowych i artykułów w sieciach społecznościowych.

Jeśli podoba Ci się artykuł, poświęć chwilę, aby udostępnić go na Twitterze lub Facebooku. 🙂