- 2014 年 2 月 24 日
- 瓦西利斯·弗里尼奥提斯（Vasilis Vryniotis）
- 。 3条留言
数据包络分析，也称为DEA，是一种用于执行边界分析的非参数方法。 它使用线性规划来估计多个决策单元的效率，并且通常用于生产，管理和经济学中。 该技术最初是由 1978年的Charnes，Cooper和Rhodes 从那时起，它就成为估算生产前沿的宝贵工具。
更新：Datumbox机器学习框架现在是开源的，免费提供给 下载。 签出com.datumbox.framework.algorithms.dea软件包，以查看Java中数据包络分析的实现。
当我在5到6年前第一次遇到该方法时，我对算法的独创性，它的简单性以及所用思想的巧妙之处感到惊讶。 令我惊讶的是，该技术在常规应用程序（财务，运营研究等）之外运行良好，因为它可以成功地应用于在线营销，搜索引擎排名和创建综合指标。 尽管如此，今天DEA几乎是在业务范围内讨论的。 这就是为什么在本文中，我将介绍DEA背后的基本思想和数学框架，而在下一篇文章中，我将向您展示该算法在Web应用程序上的一些新颖应用程序。
为什么数据包络分析很有趣？
数据包络分析是一种使我们能够根据记录的特征（权重，大小，成本，收入和其他指标或KPI）对记录（商店，员工，工厂，网页，营销活动等）进行比较和排名的方法，而无需事先对功能的重要性或权重。 该技术最有趣的部分是，它使我们能够比较由具有完全不同的度量单位的多个要素组成的记录。 这意味着我们可以拥有具有以公里，千克或货币单位度量的特征的记录，并且仍然能够对它们进行比较，排序并找到最佳/最差和平均表现的记录。 听起来不错？ 继续阅读。
数据包络分析的描述和假设
正如我们前面所讨论的，DEA是一种用来度量业务生产率的方法。 因此，它的一些想法来自在这种情况下衡量生产率的方式。 该方法的核心特征之一是将记录特征分为两类：输入和输出。 例如，如果我们测量汽车的效率，则可以说输入的是汽油升，输出的是行驶的公里数。
在DEA中，所有特征都必须为正，并且假定其值越高，其输入/输出就越大。 此外，数据包络分析假设可以将要素线性组合为非负权重的加权总和，并在输入和输出之间形成比率，以衡量每个记录的效率。 为了使记录高效，相对于所提供的输入，它必须给我们提供“良好”的输出。 效率通过输出与输入之比来衡量，然后与其他记录的比率进行比较。
DEA背后的创意
到目前为止，我们所涵盖的是常识/惯例。 我们使用输入和输出，加权总和和比率对记录进行排名。 DEA的巧妙思想在于计算特征的权重。 数据包络分析无需在运行分析之前设置功能的权重并确定其重要性，而是从数据中计算出它们。 此外，每条记录的权重都不相同！
这是DEA选择权重的方法：我们尝试通过选择适当的特征权重来最大化每个记录的比率； 同时，尽管我们必须确保，如果我们使用相同的权重来计算所有其他记录的比率，它们中的任何一个都不会大于1。
一开始这个想法听起来有点奇怪。 这不会导致计算不同的加权比率吗？ 答案是肯定的。 这是否意味着我们实际上对每条记录的比率进行不同的计算？ 答案再次是。 那么这是如何工作的呢？ 答案很简单：对于每条记录，鉴于其记录的特征，我们试图找到“理想情况”（权重），在这种情况下，其比率应尽可能高，从而使其尽可能有效。 但同时，鉴于这种“理想情况”，其他记录的输出/输入比率均不应大于1，这意味着它们的效率不能超过100％！ 一旦我们计算了每种“理想情况”下所有记录的比率，就可以使用它们的比率对它们进行排名。
因此，DEA的主要思想可以归纳为以下几点：“找到理想的情况，在这种情况下我们可以根据每个记录的特征获得最佳比率得分。 然后计算每个记录的理想比率，并用其比较其有效性”。
让我们看一个例子
让我们看一个可以使用DEA的示例。
假设我们有兴趣基于以下几个特征来评估特定连锁超市商店的效率：员工总数，以平方米为单位的商店大小，他们产生的销售量以及客户数量他们平均每个月服务一次。 显而易见，要找到最高效的商店，就需要我们比较具有多个功能的记录。
要应用DEA，我们必须定义输入和输出。 在这种情况下，输出显然是销售额和所服务的客户数量。 输入的是员工人数和商店规模。 如果我们运行DEA，我们将以理想的权重（如上所述）估算每个商店的产出与投入之比。 一旦有了它们的比率，我们就会根据它们的效率对其进行排名。
现在是数学时间！
现在我们对DEA的工作原理有了一个直观的认识，现在该深入研究数学了。
使用以下公式估算具有x输入和y输出（均为正值的特征向量）的特定记录i的效率比：
其中u和v是记录的每个输出和输入的权重，s是输出要素的数量，m是输入要素的数量。
为特定记录i找到最佳/理想权重的问题可以表述为：
同样，以上只是寻找使记录i的效率最大化的权重u和v的数学方法，只要这些权重不会使任何其他记录的效率超过100％。
为了解决这个问题，我们必须使用线性编程。 不幸的是，线性编程不允许我们使用分数，因此我们需要按如下方式变换问题的表述：
我们应该强调，上述线性规划问题将为记录i提供最佳权重，并在这些最佳权重下计算其效率。 必须对数据集中的每个记录重复相同的操作。 因此，如果我们有n条记录，则必须解决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必须大大低于观测数。 当d非常接近或大于n时运行DEA不会提供有用的结果，因为很可能会发现所有记录都是最优的。 请注意，当您添加新的输出变量（维度）时，在该维中具有最大值的所有记录都将被发现是最佳的。
最后，我们应该注意，在算法的一般形式中，DEA中特征的权重是根据数据估算的，因此，它们没有使用任何有关我们可能在问题中具有特征重要性的先验信息（当然可以将这些信息作为约束纳入我们的线性问题中）。 另外，计算出的效率得分实际上是每条记录的上限效率比，因为它们是在“理想情况”下计算得出的。 这意味着当无法对功能的重要性进行任何假设但如果我们确实有任何先验信息或者我们可以量化其重要性时，DEA可能是一个很好的解决方案，建议使用替代技术。
在下一篇文章中，我将向您展示如何开发实现 JAVA中的数据包络分析 我们将使用该方法估算社交媒体网络中网页和文章的受欢迎程度。
如果您喜欢这篇文章，请花一点时间在Twitter或Facebook上分享。 🙂
