英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
数据包络分析和大数据
Dariush Khezrimotlagh a, Joe Zhu b,c,lowast;, Wade D. Cook d, Mehdi Toloo e
摘要：在用于一组n个决策单元（DMU）的传统数据包络分析（DEA）方法中，标准DEA模型被解决n次，每个DMU一个。随着DMU数量的增加，解决标准模型的时间急剧增加。在该研究中，当存在大量DMU（例如，20,000DMU或更多）时，与现有方法相比，提出了一种新的框架，显着地减少了所需的DEA计算时间。该框架包括五个步骤：（i）使用所提出的算法选择DMU的子样本，（ii）在所选择的子样本中找到最佳实践DMU，（iii）在所选子样本的船体中找到外部DMU，（iv）识别所有有效DMU的集合，以及（v）测量DMU的性能分数，作为传统DEA方法产生的分数。假设变量返回规模技术，并设计了几个模拟实验来估计应用所提出的大数据方法的运行时间。本研究得到的结果表明，与现有技术相比，运行时间降低了99.9％。此外，我们说明了将所提出的方法应用为DMU数量（基数），输入和输出数量（维度）以及有效DMU（密度）比例的函数的基本计算时间。从1996年到2016年，这些方法还在美国30,099个电厂组成的真实数据集上进行了比较。
1.介绍：
数据包络分析（DEA）由Charnes，Cooper和Rhodes（1978）开发，用于评估一组具有多个输入和多个输出的同质决策单元（DMU）的性能。使用线性规划（LP），DEA将DMU分为两个互斥和集体详尽的组（有效的DMU和低效的DMU），并测量每个DMU的性能分数。随着DMU数量的增加（例如，退伍军人事务部对超过20,000家医院的研究），应该解决大量的LPs。在DEA文献中有几项研究，从Ali（1990,1993）的研究开始，提供理论框架，以减少应用DEA模型的计算时间。例如，Dulaacute;和Helgason（1996）开发了一种程序，将有限DMU的LPs数量减少到不超过凸壳中极端DMU的数量（参见Dulaacute;，Helgason，＆Venugopal，1998）。 Barr和Durchholz（1997）提出了一种分层分解（HD）程序，以减少解决大规模DEA问题的运行时间。他们在软件实现中的建议是将DMU分成更小的组，并逐渐从随后的问题中删除已知的低效DMU的相应决策变量。 Dulaacute;（2008）讨论了三个参数对应用DEA模型的计算时间的影响，即所涉及的DMU数量（基数），输入和输出数量（维度）以及有效DMU（密度）的比例。不久之后，Dulaacute;（2011）提出了一种名为build-hull（BH）的情感程序，以大大减少寻找所有高效DMU的运行时间。关于大规模DEA的一些相关研究也可以在Chen和Lai（2017），Dulaacute;和Loacute;pez（2013），Dulaacute;和Thrall（2001），Chen和Cho（2009），Sueyoshi和Chang（1989）等中找到。大多数提议的将DMU划分为较小组的框架背后的主要思想是首先找到一组有效的DMU，然后计算低效DMU的性能得分（例如参见Barr＆Durchholz，1997，Korhonen＆Siitari，2009）。虽然减少大数据集存在时的计算时间的关键是识别所有有效的DMU，但随着维数的增加，样本的密度增加，找到有效DMU集的运行时间也会增加（例如，见Chen＆Cho，2009，Dulaacute;，2008）。因此，计算所有DMU的DEA分数的运行时间可能很长。
本研究的目标是开发一个框架，与现有方法相比，大大减少了查找所有高效DMU集的计算时间，从而减少了测量所有DMU性能分数的运行时间。换句话说，我们开发了一种新方法来显着减少解决大规模DEA问题所需的计算时间。我们的贡献是选择DMU的子样本，然后找到所选子样本的外壳的外部DMU。接下来我们将找到所有有效DMU的集合，并测量所有低效DMU的性能分数。为了证明我们提出的方法的有效性，我们使用变量规模收益（VRS）技术（有关选择VRS的更多细节，请参见第2节）。我们使用Matlab2017a（学生版）和一台笔记本电脑配备Intelreg;CoreTMi7-7820HK CPU @ 2.90千兆赫，16千兆字节内存和64位Windows 10操作系统。由于不同的编程方式，使用的不同软件，不同的设备，不同的设置，安装的应用程序以及所使用系统中的首选项会影响测量DMU样本性能的运行时间，因此我们显示了减少运行时间的速度。我们的方法相对于传统的DEA方法，HD（层次分解）和BH（build-hull）。根据我们的知识，HD和BH是DEA文献中最强大和最有效的技术。由于Dulaacute;（2011）显示了BH与HD的相比，在本研究中，我们只展示了方法与BH的比较，使用一台具有少量8个处理器的计算机。该研究分为八个部分。第2节介绍了该研究的背景。有关DEA的基本定义，以及大规模DEA中三种最有效的方法，在第3节中介绍。第4节介绍了使用的短语。该方法在第5节中开发。第6节描述了应用我们的框架与BH的准备。第7节介绍了所提方法与现有方法的测量时间。最后一节给出了结论。
2.背景：
标准DEA模型由Charnes等人发起。 （1978），是径向恒定的规模收益率（CRS）模型。 在这项研究中，我们专注于径向输出导向的变量返回比例（VRS）模型。 VRS高效DMU的数量通常大于CRS高效DMU的数量，并且VRS模型的大小也大于CRS模型的大小。 VRS模型（见模型1）有两种形式，即包络和乘法形式。 包络形式包含n 1个决策变量，m s 1个约束和n个非负性限制;同时，乘数形式包括m s 1个决策变量，n个约束和m s个非负性限制，其中 是DMU的数量，m和s分别是输入和输出的数量。本研究涉及所提方法第一阶段的包络形式，因为Cooper，Seiford和Tone（2007）p。52：
（i）LP的计算工作量趋于与约束数量的权力成比例增长。 通常，在DEA中，n比m s（经验法则）大得多，因此解决乘数形式需要花费更多时间。
包络形式。
（ii）由于保持基础（或其反向）所需的存储器大小是约束数量的平方，因此包络形式更适合于节省存储器的目的。
（iii）乘数形式未能提供最大松弛的解决方案。
（iv）对包络形式的解释更为直接。
很明显，在HD，BH和我们的方法的第一阶段之后，任何DEA模型（包络形式或乘数形式）都可以用来评估DMU的性能。此外，VRS模型应该被解决n次（一次是DMU）因此，随着基数的增加，决策变量的数量增加，这导致所需计算数量的显着增加。因此，在存储容量，CPU时间和高级软件方面需要强大的计算机系统来运行简单的传统DEA模型，例如VRS模型（参见Dulaacute;，2008）。自Ali（1993）的工作以来，有几种方法已经开发出最初找到一组有效的DMU（称为阶段1） - 为了通过删除与低效DMU相关的决策变量来减少决策变量的数量 - 然后，应用所需的DEA模型来衡量性能其余低效的DMU。 Ali（1993）建议首先找到非支配的DMU，然后通过逐渐将相关的决策变量丢弃到已知的低效DMU来更新DEA模型的决策变量的数量。 Barr和Durchholz（1997）遵循Ali（1993）的建议，并使用HD程序将DMU分成较小的组，大小大致相同。他们还并行使用多个处理器，以减少用于测量所有DMU的性能分数的计算时间。杜拉等人。 （1998）提出了一种方法来识别最小的DMU集合，从中提取生产可能性集合，以便获得DEA结果。 Dulaacute;和Thrall（2001）开发了一种处理四种技术回报的方法。根据他们的方法，可以从VRS高效DMU中提取减少/不增加返回到规模有效DMU，并且从这三组有效DMU中可以获得CRS高效DMU集合。 Dulaacute;（2008）表明，应用传统DEA模型的计算时间相对于DMU的数量几乎是二次方的，并且相对于输入和输出的数量是线性的（参见Dulaacute;和Loacute;pez，2009）。 Korhonen和Siitari（2009）提出了一种带有复杂参数编程的层次分解程序，以减小尺寸较小时的DEA计算负担。 Chen和Cho（2009）也提出了一个加速程序来处理尺寸较小的大规模VRS问题。 Dulaacute;（2011）建立了一种BB算法，该算法可用于所有四种技术回报，以及时获得DMU的DEA分数。 Dulaacute;和Loacute;pez（2013）在存在大量数据时探索了理论和计算方面的挑战。当数据不断变化时，它们提供了理论框架和专用工具来处理动态情况下的大规模数据.Chen和Lai（2017）也提出了一种算法来解决LP大小限制的问题，以便在存在大规模数据时计算径向效率。根据他们的算法，LP可以在合理的迭代次数内得到解决，而不会产生运行时间。作者还强调，他们的算法并不是为了与其他算法竞争而设计的。在这项研究中，我们提出了一个强大的框架，包括五个简单的步骤，与现有技术相比，大大减少了大规模DEA的计算时间。
3.名词定义
我们首先提供一些基本定义来阐明本研究中使用的术语的概念和含义。假设集合D包括n个观测值DMU j，（j = 1，...，n），其中每个DMUj具有m个非负输入xj =（x1j，...，xmj）和s个非负输出yj =（y1j，...，ysj）。我们有以下定义（Cooper等，2007）：
定义1.当且仅当（i）xAle;xB且（ii）yAge;yB时，DMUA支配DMUB。
定义2.令NA为支配DMUA的所有DMU的集合。如果NA = {DMUA}，则DMUA是非支配的DMU，并且整组这样的DMU称为非支配DMU的集合，由N表示。
定义3.当且仅当DMUA既不由任何其他DMU也不由任何虚拟DMU（由其他DMU的线性组合生成）主导时，DMUA被称为有效DMU。这组有效的DMU用F表示。
显然，非支配DMU的集合是所有观测集合的子集，即Nsube;D。有效DMU集合也是非支配DMU集合的子集，即Fsube;N。另外，非支配DMU不一定是有效的DMU，即N F.
包络形式的标准VRS模型（面向输出）（Banker，Charnes，＆Cooper，1984）如下，其中DMU1（l = 1，...，n）正在评估中。
假设由DS表示的大小为p的子样本是从观察集合中给出的，即DSsube;D。通常，p可以是小于或等于n的自然数，即| DS |。 =ple;n。我们注意到，DScap;F可以是空集。 对于k = 1，我们让DMUS k =（xSk，ykS）。。。 ，p表示子样本DS中的所选DMU。 基于子样本DS的径向VRS模型，其中DMU1（l = 1，...，n）正在评估中，如下公式化：
定义3：当且仅当phi;lS* = 1时，DMU1被称为最佳实践。最佳实践DMU不一定有效。 DS中的最佳实践集合由BS表示。我们也称phi;lS*，即DMUS l的子效率得分。与具有n 1个变量的模型相比，模型中决策变量的数量为p 1。因此，使用模型，其中p n，我们处理具有少得多的决策变量的LP问题，因此解决VRS模型的运行时间大大减少。通常，增加LP中的决策变量的数量会导致增加解决该LP的运行时间。例如，求解大小为20,000和2 2输入输出的模型的运行时间平均为0.5062秒，而求解大小为2000和2 2维度的模型的运行时间平均为0.0085秒。理论上，模型中决策变量的数量越少，估算所有DMU性能所需的运行时间就越短（例如，见Barr＆Durchholz，1997）。当子样本包括所有有效的DMU时，模型等同于标准VRS模型（1）（参见Ali，1993）。
Ali（1993）建议从模型（1）和（2）中消除主导DMU的相应lambda。他提到样本中可能存在少量完全占主导地位的DMU，但是，这种对大规模数据的预处理是值得的。例如，对于具有10 10维度的20,000个DMU，其中每个输入（输出）均匀地分布在区间[10,20]上，样本中平均有超过98.8％的非支配DMU。我们不会将这些使用过的框架（包括我们的框架）的增强功能考虑在现有框架之间进行透明比较，以便更好地了解它们的性能。我们现在介绍最知名的方法来减少大规模数据的运行时间。
3.1 RBE（受限制的基础条目）
Ali（1993）提出了一种RBE程序，以逐渐减小VRS LP的大小。该过程从使用具有n 1个决策变量（n个非负变量lambda;和自由变量phi;）的模型评估DMU开始。如果评估的DMU效率低，则从模型（1）中移除其对应的变量lambda;因此，该模型在下一次迭代中具有n个决策变量。 LP的尺寸逐渐减小，并且当去除样品中的所有低效DMU时它是恒定的。有关RBE及相关增强功能的详细讨论，请参见Dulaacute;（2008）。
与传统方法不同，RBE的主要弱点是LP不是彼此独立的。换句话说，当少数资源可用时，RBE很有用，因为在评估一组100 K DMU时，并行使用100 K计算机，传统方法不需要任何改进。然而，RBE与BH不具有可比性，因此，我们不在本研究中将我们的方法与此程序进行比较。这里应该注意，并行处理的目的是驱动连接到同一计算机的不同处理器之间的所有计算。换句话说，在该方法中，运行时间减少而计算的数量是固定的。与此方法相反，我们建议的方法的目的是减少计算的数量，从而改善所需的运行时间。很明显，验证在我们的方法中应用并行方法来解决减少的计算也将减少运行时间。
全文共15884字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2117]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
