Tutoriel d'analyse d'enveloppement de données

• 24 février 2014
• Vassilis Vryniotis
• . 3 Commentaires

L'analyse d'enveloppement des données, également appelée DEA, est une méthode non paramétrique pour effectuer une analyse de frontière. Il utilise la programmation linéaire pour estimer l'efficacité de plusieurs unités de prise de décision et il est couramment utilisé dans la production, la gestion et l'économie. La technique a d'abord été proposée par Charnes, Cooper et Rhodes en 1978 et depuis lors, il est devenu un outil précieux pour estimer les frontières de production.

Mise à jour: le Datumbox Machine Learning Framework est désormais open-source et gratuit pour download. Consultez le package com.datumbox.framework.algorithms.dea pour voir l'implémentation de Data Envelopment Analysis en Java.

Quand j'ai rencontré la méthode pour la première fois il y a 5-6 ans, j'ai été étonné par l'originalité de l'algorithme, sa simplicité et l'intelligence des idées qu'il utilisait. J'ai été encore plus étonné de voir que la technique fonctionnait bien en dehors de ses applications habituelles (finance, recherche opérationnelle, etc.) puisqu'elle pouvait être appliquée avec succès dans le marketing en ligne, le classement des moteurs de recherche et pour la création de métriques composites. Malgré cela, le DEA est aujourd'hui presque exclusivement abordé dans le cadre des affaires. C'est pourquoi, dans cet article, je couvrirai les idées de base et le cadre mathématique derrière DEA et dans le prochain post, je vous montrerai quelques nouvelles applications de l'algorithme sur les applications Web.

Pourquoi l'analyse d'enveloppement des données est-elle intéressante?

L'analyse d'enveloppement des données est une méthode qui nous permet de comparer et de classer les enregistrements (magasins, employés, usines, pages Web, campagnes marketing, etc.) en fonction de leurs caractéristiques (poids, taille, coût, revenus et autres mesures ou KPI) sans faire d'hypothèses préalables sur l'importance ou le poids des caractéristiques. La partie la plus intéressante de cette technique est qu'elle nous permet de comparer des enregistrements composés de plusieurs entités ayant des unités de mesure totalement différentes. Cela signifie que nous pouvons avoir des enregistrements avec des caractéristiques mesurées en kilomètres, en kilogrammes ou en unités monétaires et être toujours en mesure de les comparer, de les classer et de trouver les enregistrements les plus performants / les moins performants et moyens. Ça a l'air intéressant? Continue de lire.

La description et les hypothèses de l'analyse d'enveloppement des données

Comme nous l'avons vu précédemment, la DEA est une méthode qui a été inventée pour mesurer la productivité en entreprise. Ainsi, plusieurs de ses idées proviennent de la manière dont la productivité est mesurée dans ce contexte. L'une des principales caractéristiques de la méthode est la séparation des caractéristiques d'enregistrement en deux catégories: entrée et sortie. Par exemple, si nous mesurons l'efficacité d'une voiture, nous pourrions dire que l'entrée correspond aux litres d'essence et la sortie correspond au nombre de kilomètres qu'elle parcourt.

Dans DEA, toutes les caractéristiques doivent être positives et on suppose que plus leur valeur est élevée, plus leur entrée / sortie est élevée. En outre, l'analyse d'enveloppement des données suppose que les caractéristiques peuvent être combinées linéairement sous forme de somme pondérée de poids non négatifs et forment un rapport entre l'entrée et la sortie qui mesurera l'efficacité de chaque enregistrement. Pour qu'un enregistrement soit efficace, il doit nous donner une «bonne» sortie par rapport à l'entrée fournie. L'efficacité est mesurée par le rapport entre la sortie et l'entrée, puis comparée au rapport des autres enregistrements.

L'idée ingénieuse derrière DEA

Ce que nous avons couvert jusqu'à présent est un bon sens / pratique. Nous utilisons des entrées et des sorties, des sommes pondérées et des ratios pour classer nos enregistrements. L'idée intelligente de DEA réside dans la manière dont les poids des caractéristiques sont calculés. Au lieu d'avoir à définir les pondérations des entités et à décider de leur importance avant d'exécuter l'analyse, l'analyse d'enveloppement des données les calcule à partir des données. De plus, les poids ne sont PAS les mêmes pour chaque disque!

Voici comment DEA sélectionne les pondérations: Nous essayons de maximiser le rapport de chaque enregistrement en sélectionnant les pondérations de caractéristiques appropriées; en même temps, nous devons cependant nous assurer que si nous utilisons les mêmes poids pour calculer les ratios de tous les autres enregistrements, aucun d'entre eux ne deviendra supérieur à 1.

L'idée semble un peu étrange au début. Cela ne conduira-t-il pas au calcul de ratios différemment pondérés? La réponse est oui. Cela ne signifie-t-il pas que nous calculons en fait différemment les ratios pour chaque enregistrement? La réponse est à nouveau oui. Donc comment ça fonctionne? La réponse est simple: pour chaque enregistrement, compte tenu de ses caractéristiques, nous essayons de trouver la «situation idéale» (poids) dans laquelle son ratio serait le plus élevé possible et le rendrait ainsi aussi efficace que possible. MAIS en même temps, étant donné cette «situation idéale», aucun des rapports sortie / entrée des autres enregistrements ne doit être supérieur à 1, ce qui signifie qu'ils ne peuvent pas être plus efficaces que 100%! Une fois que nous calculons les ratios de tous les enregistrements sous chaque «situation idéale», nous utilisons leurs ratios pour les classer.

L'idée principale du DEA peut donc se résumer comme suit: «Trouvez la situation idéale dans laquelle nous pouvons obtenir le meilleur ratio score en fonction des caractéristiques de chaque enregistrement. Calculez ensuite ce ratio idéal de chaque enregistrement et utilisez-le pour comparer leur efficacité ».

Voyons voir un exemple

Voyons un exemple où nous pourrions utiliser DEA.

Supposons que nous nous intéressions à évaluer l'efficacité des supermarchés d'une chaîne particulière en fonction d'un certain nombre de caractéristiques: le nombre total d'employés, la taille du magasin en mètres carrés, le montant des ventes qu'ils génèrent et le nombre de clients qu'ils servent tous les mois en moyenne. Il devient évident que trouver les magasins les plus efficaces nous oblige à comparer des enregistrements avec de multiples fonctionnalités.

Pour appliquer DEA, nous devons définir quelle est notre entrée et notre sortie. Dans ce cas, le résultat est évidemment le montant des ventes et le nombre de clients qu'ils servent. L'entrée est le nombre d'employés et la taille du magasin. Si nous exécutons DEA, nous estimerons le rapport sortie / entrée pour chaque magasin sous les poids idéaux (comme indiqué ci-dessus). Une fois que nous aurons leurs ratios, nous les classerons en fonction de leur efficacité.

C'est l'heure des maths!

Maintenant que nous avons une intuition sur le fonctionnement de la DEA, il est temps de se plonger dans les mathématiques.

Le rapport d'efficacité d'un enregistrement i particulier avec entrée x et sortie y (les deux vecteurs de caractéristiques avec des valeurs positives) est estimé à l'aide de la formule suivante:

Où u et v sont les poids de chaque sortie et entrée de l'enregistrement, s est le nombre d'entités de sortie et m est le nombre d'entités d'entrée.

Le problème de trouver les poids meilleurs / idéaux pour un enregistrement particulier i peut être formulé comme suit:

Encore une fois, ce qui précède n'est que la manière mathématique de trouver les poids u et v qui maximisent l'efficacité de l'enregistrement i, à condition que ces poids ne rendent aucun des autres enregistrements plus efficace que 100%.

Pour résoudre ce problème, nous devons utiliser la programmation linéaire. Malheureusement, la programmation linéaire ne nous permet pas d'utiliser des fractions et nous devons donc transformer la formulation du problème comme suit:

Nous devons souligner que le problème de programmation linéaire ci-dessus nous donnera les meilleurs poids pour l'enregistrement i et calculera son efficacité sous ces poids optimaux. La même chose doit être répétée pour chaque enregistrement de notre ensemble de données. Donc, si nous avons n enregistrements, nous devons résoudre n problèmes linéaires séparés. Voici le pseudocode du fonctionnement de DEA:

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

Limitations de l'analyse d'enveloppement des données

La DEA est une excellente technique mais elle a ses limites. Vous devez comprendre que la DEA est comme une boîte noire. Étant donné que les poids utilisés dans le rapport d'efficacité de chaque enregistrement sont différents, il est inutile d'essayer d'expliquer comment et pourquoi chaque score a été calculé. Habituellement, nous nous concentrons sur le classement des enregistrements plutôt que sur les valeurs réelles des scores d'efficacité. Notez également que l'existence d'extrémums peut amener les scores à avoir des valeurs très faibles.

Gardez à l'esprit que DEA utilise des combinaisons linéaires des caractéristiques pour estimer les ratios. Ainsi, si les combiner linéairement n'est pas approprié dans notre application, il faut appliquer des transformations sur les entités et permettre leur combinaison linéaire. Un autre inconvénient de cette technique est que nous devons résoudre autant de problèmes de programmation linéaire que le nombre d'enregistrements, ce qui nécessite beaucoup de ressources de calcul.

Un autre problème auquel la DEA est confrontée est qu'elle ne fonctionne pas bien avec des données de grande dimension. Pour utiliser DEA, le nombre de dimensions d = m + s doit être significativement inférieur au nombre d'observations. L'exécution de DEA lorsque d est très proche ou supérieur à n ne fournit pas de résultats utiles car tous les enregistrements seront probablement jugés optimaux. Notez que lorsque vous ajoutez une nouvelle variable de sortie (dimension), tous les enregistrements avec une valeur maximale dans cette dimension seront jugés optimaux.

Enfin, nous devons noter que dans la forme générale de l'algorithme, les poids des fonctionnalités dans DEA sont estimés à partir des données et n'utilisent donc aucune information préalable sur l'importance des fonctionnalités que nous pourrions avoir dans notre problème (bien sûr il est possible d'incorporer ces informations comme contraintes dans notre problème linéaire). De plus, les scores d'efficacité calculés sont en fait les ratios d'efficacité limites supérieurs de chaque enregistrement puisqu'ils sont calculés dans des «situations idéales». Cela signifie que DEA peut être une bonne solution lorsqu'il n'est pas possible de faire des hypothèses sur l'importance des fonctionnalités, mais si nous avons des informations préalables ou que nous pouvons quantifier leur importance, il est conseillé d'utiliser des techniques alternatives.

Dans le prochain article, je vais vous montrer comment développer une implémentation de Analyse de l'enveloppe des données dans JAVA et nous utiliserons cette méthode pour estimer la popularité des pages Web et des articles sur les réseaux sociaux.

Si vous aimez l'article, prenez un moment pour le partager sur Twitter ou Facebook. 🙂