Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.37 No.4 pp.239-244
DOI : https://doi.org/10.11627/jkise.2014.37.4.239

Clustering of Decision Making Units using DEA

Kyeongtaek Kim†
Department of Industrial and Management Engineering, Hannam University
Corresponding Author : kkim610@gmail.com
November 13, 2014 December 10, 2014 December 10, 2014

Abstract

The conventional clustering approaches are mostly based on minimizing total dissimilarity of input and output. However, the clustering approach may not be helpful in some cases of clustering decision making units (DMUs) with production feature converting multiple inputs into multiple outputs because it does not care converting functions. Data envelopment analysis (DEA) has been widely applied for efficiency estimation of such DMUs since it has non-parametric characteristics. We propose a new clustering method to identify groups of DMUs that are similar in terms of their input-output profiles. A real world example is given to explain the use and effectiveness of the proposed method. And we calculate similarity value between its result and the result of a conventional clustering method applied to the example. After the efficiency value was added to input of K-means algorithm, we calculate new similarity value and compare it with the previous one.


DEA를 이용한 의사결정단위의 클러스터링

김 경택†
한남대학교 산업경영공학과

초록


    1.서 론

    Data Envelopment Analysis(DEA)는 유사한 목적을 가 지고 운영되는 동일한 다수산출요소/다수투입요소 자료 구조를 갖는 의사결정단위(DMU)들의 상대적 효율성을 평가하는 방법이다. 모든 투입요소를 비례적으로 증가시 킬 때 산출도 일정한 비율에 따라 증가하는, 규모에 대한 수익불변(Constant Returns to Scale)을 가정하여, Charnes et al.[6]이 DEA 모델을 제시함으로써 널리 알려지게 되 었다.

    클러스터링은 동일한 군집(cluster) 내에 있는 객체들의 유사성은 극대화하면서, 서로 다른 군집에 속한 객체들과의 유사성(similarity)은 최소화되도록, 객체들의 군집을 결정 하는 절차이다[12]. 일반적으로, 클러스터링 방법으로는 계층적(hierarchical) 클러스터링, 센트로이드 기반(centroidbased) 클러스터링, 밀집도 기반(density-based) 클러스터링, 모델기반(model-based) 클러스터링 등이 있다. 계층적 클러 스터링은 덴드로그램(dendrogram)이라 불리우는 군집트리 (cluster tree)를 생성함으로써 객체들을 군집화한다. 트리 를 구성하는 방법에 따라 병합식(agglomerative)과 분할식 (divisive)으로 나뉜다. 센트로이드 기반 클러스터링은 Kmeans 알고리듬이 가장 널리 알려진 예이며, 어떤 알고리 듬을 사용하던지 거리(distance)를 정의하는 함수에 따라 클러스터링의 결과가 크게 변한다. 밀집도기반 클러스터 링에서, 군집은 밀집도가 나머지 지역보다 높은 지역으로 정의된다. 모델기반 클러스터링은 데이터가 만들어졌을 것으로 추정되는 모델과, 데이터 사이의 적합성(fitness)이 최적화되도록 군집을 구성한다.

    DEA와 클러스터링을 결합한 여러 연구들이 있다. Shin and Shon[19]은 모든 고객들을 DMU로 정의하기에는 너 무 많아서, 고객들을 클러스터링 한 후, 각 군집을 하나 의 DMU로 정의하여 분석하였다. Sharma and Yu[18]는 DMU를 입력요소에 따라 클러스터링하여 추후 벤치마킹 과정에 도움이 되도록 하였다. Schreyogg and Reitzenstein [20]은 DEA를 적용한 후, 각각의 클러스터링 목적에 맞게 일부 요소만으로 클러스터링을 수행하여, 각 목적별로 2개 의 전략그룹(strategic group)를 선별하여, 그들의 특징을 비 교하였다. Saati et al.[17]은 퍼지 환경하에서 DMU를 클러 스터링 하는 Fuzzy DEA 방법을 제안하였다. Marroquin et al.[14]은 DMU의 수가 너무 많아서 가장 널리 사용되 는 Excel Solver 같은 소프트웨어로 DEA 최적해를 구하 는데 많은 시간이 소요될 때, DMU를 먼저 클러스터링 한 다음, 각 군집에서 효율성이 1인 DMU들을 구하고, 이들 DMU들만 모은 다음, 처음부터 다시 절차를 반복 하여 시간을 단축하는 방법을 제안하였다.

    다수의 투입요소를 사용하며 또한 다수의 산출물을 생 산하는 DMU의 생산특성을 비교하기 위해서, K-means 알고리듬 같은 전통적인 클러스터링 방법 대신에, Po et al.[16]은 DEA 모델을 이용한 클러스터링 알고리듬을 제 시하였다. 이 알고리듬은 다음과 같은 장점을 갖는다 : (1) 투입요소와 산출요소 사이의 함수적 관계의 가정이 필요하지 않다. (2) 군집의 개수가 DEA 적용 결과에 의해 객관적으로 정해진다. Bi et al.[4]은 Po et al.[16]의 DEA 기반 클러스터링 알고리듬을 이용하여, 중국 각 지역을 DMU로 하여 환경에 대한 효율성을 측정하고, 클러스터 링을 하였다. 한편, Amin et al.[1]는 최적해가 다수 있을 때 DEA 기반 클러스터링 알고리즘이 어떻게 서로 다른 군집들을 생성하는지를 보여주었다.

    그러나, Po의 DEA 기반 클러스터링 알고리즘은 계산 이 복잡한 단점이 있다. 본 연구에서는 이러한 단점을 수 정하여, 새로운 DEA 기반 클러스터링 알고리즘을 제시 하고, 실제 데이터에 적용하였다. 미국 플로리다주에 있 는 각 병원을 DMU로 설정하여, 2012년 통계자료에서 투 입변수와 산출변수를 결정한 다음 DEA 모형을 이용하여 효율성을 측정하고, 본 연구에서 제안한 알고리즘을 적 용하여 클러스터링 한다. 아울러, K-means 클러스터링 방법을 통한 결과와 비교한다.

    2.DEA를 이용한 클러스터링

    2.1.DEA

    효율성(efficiency)은 투입요소의 사용량에 대한 산출물 생산량의 비율을 의미한다. 효율성은 생산조직이 단일 투 입요소를 사용하여 단일 산출물을 생산할 경우에는 계산 이 매우 간단하다. 그러나 대부분의 생산조직은 다수의 투입요소를 사용하며 또한 다수의 산출물을 생산한다. 이 러한 다수투입 다수산출의 경우 효율성을 계산하려면 다 수의 투입요소에 가중치를 적용하여 총괄한 총괄투입과 다수의 산출물에 가중치를 적용하여 총괄한 총괄산출을 계산하는 과정이 필요하다. DEA는 다수산출/다수투입을 하는 DMU에 대하여, DMU가 속한 그룹 내에 있는 베스 트 프랙티스(best practice)와 비교한 상대적 효율성을 계 산한다.

    Charnes et al.[6]은, 모든 투입요소를 비례적으로 증가 시킬 때 산출도 일정한 비율에 따라 증가한다고 가정하여, DMU의 효율성은, 나머지 DMU의 총괄산출/총괄투입 비 율이 1보다 작거나 같아야 한다는 조건하에서, 가중된 투 입에 대한 가중된 산출의 비율의 최대치로 정의하였다. 이 모형은 식 (1)과 같다.

    각 DMU k에 대하여,

    Max r = 1 s u rk y rk i = 1 m v ik x ik

    Subject to r = 1 s u rk y rj i = 1 m v ik x ij 1 , j = 1 , ..., n u rk 0 , r = 1 , ..., s v ik 0 , i = 1 , ..., m
    (1)

    여기에서 yrj,xij(모두 양수)는 j번째 DMU의 이미 알고 있는 산출변수 및 투입변수이며, urk,vik는 DMU k의 가 변의 가중치이다.

    이 모형은 비선형문제인데, Charnes et al.[8]은 이 모형 을 아래 식 (2)와 같은 선형계획법(Linear Programming) 문제로 변환하였다.

    각 DMU k에 대하여,

    Max Eff k = r = 1 s u rk y rk

    Subject to r = 1 s u rk y rj i = 1 m v ik x ij 0 , j i = 1 m v ik x ik = 1 u rk 0 , r v ik 0 , i
    (2)

    위 모형은 CCR 모형이라 부른다. 한편, Banker et al.[2] 은 규모수익불변(CRS) 가정 대신에 규모수익가변(Variable Returns to Scale)을 가정하여 아래와 같이 효율성을 측정 하는 식 (3)을 제안하였다.

    각 DMU k에 대하여,

    Max r = 1 s u rk y rk u 0 k i = 1 m v ik x ik

    Subject to r = 1 s u rk y rj i = 1 m v ik x ij u ok 1 , j = 1 , ..., n u rk 0 , r = 1 , ..., s v ik 0 , i = 1 ..., m u 0 k unrestricted sign
    (3)

    위 식에서 u0k는 효율적 DMU의 규모수익(Returns to Scale)효과를 평가하는 척도로 해석된다. u0k > 0은 규모수 익체증을 나타내고, u0k < 0은 규모수익체감을 나타낸다.

    그 외에 Additive 모형[7], Slack-based measure 모형 [21], Russell measure 모형[9] 등이 있다. 본 연구에서는 CCR 모형을 사용하기로 한다.

    2.2.DEA 기반 클러스터링 알고리듬

    DMU가 투입요소 및 산출요소로 구분되는 특징을 가 지고 있다면, DMU를 클러스터링 할 때 이 특성을 반영 하여야 한다. 그러나 일반적인 클러스터링 알고리듬은 투입변수와 산출변수 사이의 관계를 전혀 고려하지 않 고, 모든 변수들을 동일한 변수로 취급하여 클러스터링 을 한다. 이러한 단점을 극복하고자, PO et al.[16]은 생 산함수(production function)를 기반으로 클러스터링을 하 는 것이 더 타당하다고 주장하고, 이러한 클러스터링을 가능하게 하는 알고리듬을 제시하였다.

    Po의 DEA 기반 클러스터링 알고리즘[16]은 3단계로 되어있다. 첫 번째 단계에서 urk*vik*가 모두 nonzero 인 DMU k에 대하여 r = 1 S u rk y rj i = 1 m v ik x ij = 0 이면, 새로운 군집 PF(h)로 분류한다. 두 번째 단계에서 urk*vik*가 모두 nonzero이지는 않은 DMU k는 기존의 군집 C 에 배정한다. 두 번째 단계를 수행하기 위해서 각 DMU 당 p번만큼 계산하여 t(1), … , t(p)를 구한다음 그 중 최 대치를 구하여 클러스터를 결정한다.

    본 연구에서는 Po의 DEA 기반 클러스터링 알고리즘 과 동일한 클러스터링 결과를 가져오면서 보다 간편히 계산 할 수 있는 알고리즘을 제시한다.

    1. FR={}; BFR={}

    각 DMU k에 대하여

    • 1-1. DEA CCR 모델 식 (2)를 실행하여 효율성(EffK) 을 계산한다.

    • 1-2. r = 1 S u kr y rj i = 1 m v ik x ij = 0 이 되는 모든 j의 집합 을 Fk라 한다.

    • 1-3. 만일 FkFR 이 아니면, FR= FR∪{Fk}

    2. FR = {fr1, fr2, ⋯, frp+q}이라 하자. 각 원소 frt 에 대하여

    |frt | < m이면, FR = FR - {frt }, BFR = BFR∪ {frt }

    3. 각 원소 frt 에 대하여 C(frt) = t로 놓는다.

    BFR = {bfr1, bfr2, ⋯, bfrq이라 하자. 각 원소 bfrh에 대하여

    bfrhfrt 이면, C (bfrh) = t 로 놓는다

    5. 각 DMU k에 대하여 클러스터 C (Fk) 를 배정한다.

    Po 알고리듬의 1단계는 선형계획 문제를 풀어서 효율 성을 계산하고 클러스터를 결정하는 단계로 계산횟수는 제시된 알고리듬의 1단계보다 계산 횟수가 많다. 제시된 알고리듬의 2단계는 p+3q, 3단계는 p, 4단계는 최대 pq 이다. 4단계에서 각 DMU k에 대하여 C(Fk) 를 계산하여 야 하므로, 최대 p만큼의 계산(비교)이 필요하며 따라서 4단계에서 최대 pm만큼의 계산을 하게 된다. 제시된 알 고리듬의 2~5단계의 계산 횟수를 합하면, 2p + 3q + pq + pm 이고, 일반적으로 n ≫ p이고, n ≫ q이므로, 2p + 3q + pq + pn < 2pn이다. Po 알고리듬의 2단계에서는, 먼저 각 DMU 당 t(1), … , t(p)를 구해야 하는데, t(h)마다 2(s + m)만큼 의 계산이 필요하므로, 각 DMU마다 2(s + m)p만큼의 계 산이 필요하다. 따라서 전체적으로, 2(s + m)p (n - p)만큼 의 계산이 필요하다. s + m ≥ 2이고 일반적으로 n ≫ p이므 로, Po의 알고리듬 2단계는 2(s + m)p (n - p) ≥ 4p(n - p) ≅ 4pn의 계산이 필요하게 되어, 본 논문에서 제시한 알고 리듬이 더 효율적이라 할 수 있다.

    3.적용 사례

    3.1.데이터

    병원은 DEA의 관점에서 쉽게 DMU로 정의될 수 있기 때문에, 보건 의료 분야는 DEA 분석에 아주 적합한 분 야로 여겨져 왔다[3]. 따라서, 보건 의료 분야에서 DEA 를 이용한 많은 연구들이 수행되었다[13].

    본 연구에서는, Florida Agency for Health Care Administration에서 공개한 2012 Florida Hospital Financial Data [11] 및 AHCA Inpatient Data[10]에 있는 데이터에 대하 여, 제시된 알고리듬을 적용하여 미국 플로리다주에 있 는 각 병원을 DMU로 하여 효율성을 측정하고, 클러스 터링을 한다. 2012 Florida Hospital Financial Data[11]에 서는 병원을 16개 그룹으로 나누었는데, 본 연구에서는 Group 5(Medium Urban Hospital Group)로 분류 된 33개 병원 전체를 적용 대상으로 하였다. 본 사례는 제시된 알고리듬을 쉽게 설명하고, 결과를 이차원 좌표에 표시 하기 위하여, 투입변수를 1개, 산출변수를 2개로 제한 한다.

    침상수 및 종업원 FTE(Full Time Equivalent)를 투입변 수로 사용하고, CMI 보정 퇴원환자수(CMI Adjusted Discharge) 를 산출변수로 사용하였다. CMI(Case Mix Index, 환자구성지표)는 병원의 환자중증도를 보정하기 위한 지 표로, 일반적으로 환자중증도가 높을수록 더 많은 의료서 비스를 제공받게 된다. 따라서, 병원의 효율을 측정 할 때, CMI로 보정을 해 주는 것이 보다 정확한 측정의 전제조 건이다[5, 15]. 본 사례에서는 퇴원 환자수에 CMI를 곱하 여 CMI 보정 퇴원환자수를 구하였다. 종업원 FTE는 파 트타임 종업원을 포함하여 임금을 받는 종업원들의 연간 총 근무시간을 2080으로 나눈 값으로, 정규직종업원 몇 명에 해당하는 지를 나타내는 값이다. <Table 1>은 본 연 구에서 사용 된 데이터를 보여주며, <Table 2>는 이들의 통계치를 보여준다.

    3.2.결과

    <Table 3>은 제시된 알고리듬의 1단계를 실행한 결과 이다. 2단계에서, FR = {{7},{3,7},{3,39},{29}}임을 알 수 있다. 그러면, 4단계에서, C({7}) = 1, C({3, 7}) = 1, C({3, 29}) = 2, C({29}) = 2가 된다. 알고리듬을 모두 수 행하면 <Figure 1>과 같은 군집을 얻는다. 이는 Po의 알 고리듬을 적용한 결과와 일치한다. <Figure 2>는 제시된 알고리듬을 적용한 결과를 이차원 좌표에 나타내었다 (단, DMU4, DMU11, DMU17, DMU27은 나타내는 점들 의 해상도를 위하여 <Figure 2>에 나타내지 않았다). 여 기에서 x1, x2는 산출요소 1단위를 산출하기 위하여 투 입된 입력요소의 크기를 나타낸다.

    동일한 투입변수 및 산출 변수에 k-means 알고리듬을 적용하여 DMU를 클러스터링하여, 제시된 알고리듬의 클 러스터링 결과가 유사한지 살펴보자. 이를 위하여 군집 수를, 제시된 알고리듬의 클러스터링 결과와 동일하게 2 로 정하고, 각 변수를 정규화한 후, k-means 알고리듬을 적용하여, 클러스터링을 한 결과, <Figure 3>과 같은 결과 를 얻었다.

    두 클러스터링의 결과가 얼마나 유사한지를 나타내는 척도중의 하나로 유사도(similarity measure)가 있다. Torres et al.[22]은 두 클러스터링 결과, C = {C1, C2, ⋯,Cm}, D = {D1, D2, ⋯, Dn }에 대하여, 유사도 Sim(C,D)를 다 음과 같이 정의하였다.

    Sim C , D = i = 1 m = 1 n S ij / max m , n

    여기에서 SijCiDj 에 대한 자카드 유사도 계수(Jaccard’s Similarity Coefficient)이다. 이 정의를 이용하여 본 예제에 대한 DEA 기반 클러스터링의 결과와 k-means 클러스터링 의 결과와의 유사도를 측정하면 0.5597이다. 이 값으로부 터 두 클러스터링의 결과가 유사하지 않음을 알 수 있다.

    k-means 클러스터링 알고리듬은 투입변수와 산출변수 사이의 관계를 전혀 고려하지 않고, 모든 변수들을 동일 한 요소로 한다. 따라서, 거리가 가까운 DMU들은 동일한 군집으로 분류된다. 이 결과는 동일한 군집에 속한 DMU 들이 비슷한 생산특성도 가지고 있다라는 잘못된 메시지 를 전달할 수 있다.

    4.결 론

    본 연구에서는 DEA 모델을 이용한 새로운 클러스터링 알고리듬을 제시하였다. 제시된 모델은 Po의 알고리듬과 동일한 결과를 가져오나, 계산이 더 간편함을 보였다. 아 울러, 플로리다 병원데이터에 적용한 DEA 기반 클러스터 링의 결과와 k-means 알고리듬을 적용한 결과는 유사도 가 작아, DEA 기반 클러스터링과 k-means 클러스터링은 전혀 다른 결과를 가져옴을 보였다.

    본 논문의 한계로는 최근에는 computing power가 높아 짐에 따라 대용량의 자료가 아닌 한 알고리즘의 효율성 의 의미가 점차 중요하지 않게 되어가고 있다는 점이다. 아울러, 사례연구에서 사용된 33개 DMU의 클러스터링은 제시된 알고리즘의 간편성을 설명하기에는 부족한 수준 이며, 보다 대용량의 데이터에 대한 연구가 필요하다.

    본 논문은 동일한 투입변수, 산출변수들을 사용하고도 K-means 알고리듬의 결과와 완전히 다른 클러스터링 결 과를 산출함을 보여주고 있다. 이에 따라, 추후 연구 과제 로 DMU의 효율을 비교할 때, 전체를 하나의 클러스터로 보고 비교하는 것이 타당한지, 클러스터링을 한 후 클러 스터 내에서 각 DMU의 효율성을 비교 하는 것이 나은지 에 관한 연구가 있을 수 있다. 또한 각 클러스터내에서 각 DMU의 효율성을 비교할 때, 어떤 클러스터링 결과가 더 타당한지에 관한 연구 등으로 확장 될 수 있다. 이러한 추 후연구의 결과는 학계 및 산업계에서 DMU의 효율성 비 교에 큰 영향을 끼칠 수 있다.

    Figure

    JKISE-37-239_F1.gif

    Clustering Results of Suggested Algorithm

    JKISE-37-239_F2.gif

    An Illustration of Suggested DEA-based Clustering Algorithm

    JKISE-37-239_F3.gif

    Clustering Results of K-means Algorithm

    Table

    Data from 33 Florida Hospitals

    Summary Statistics of Inputs and Outputs

    DEA Optimal Solution

    Reference

    1. Amin G , Emrouznejad A , Razaei S (2011) Some Clarifications on the DEA Clustering , European Journal of Operations Research, Vol.215; pp.498-501
    2. Banker RD , Charnes A , Cooper WW (1984) Some Models for Estimating Technical and Scale Inefficiencies in Data Envelopment Analysis , Management Science, Vol.40; pp.1078-1092
    3. Ben-Arieh D , Gullipalli D (2012) “Data Envelopment Analysis of Clinics with Sparse Data : Fuzzy Clustering Approach , Computers and Industrial Engineering, Vol.63; pp.13-21
    4. Bi G-B , Song W , Wu J (2014) A Clustering Method for Evaluating the Environmental Performance based on slack-based Measure , Computers and Industrial Engineering, Vol.72; pp.169-177
    5. Bjorkgren MA , Fries BE , Hakkinen U , Brommels M (2004) Case-Mix Adjustment and Efficiency Measurement , Scandinavian Journal of Public Health, Vol.32; pp.464-471
    6. Charnes A , Cooper WW , Rhodes EL (1978) Measuring the Efficiency of Decision Making Units , European Journal of Operations Research, Vol.2; pp.429-444
    7. Charnes A , Cooper WW , Golany B , Seiford LM , Stutz J (1985) Foundation of Decision Envelopment Analysis and Pareto-Koopmans Empirical Production Functions , Journal of Econometrics, Vol.30; pp.91-107
    8. Charnes A , Cooper WW , Rhodes EL (1981) Evaluating Program and Managerial Efficiency : An Application of Decision Envelopment Analysis to Program Follow Through , Management Science, Vol.27; pp.668-697
    9. Fare RS , Lovell CAK (1978) Measuring the Technical Efficiency of Production , Journal of Economic Theory, Vol.19; pp.150-162
    10. (2012) Florida Agency for Health Care Administration , AHCA Inpatient Data,
    11. (2012) Florida Agency for Health Care Administration, FloridaHospital Financial Data,
    12. Jain AK , Murty MN , Flynn PJ (1999) Data Clustering : A Review , ACM Computing Surveys, Vol.31 (3 ) ; pp.264-323
    13. Liu JS , Lu LYY , Lu W-M , Lin BJY (2013) A Survey of DEA Applications , Omega, Vol.41; pp.893-902
    14. Marroquin MGV , Pena ML , Castro CE , Castro JM , Cabrera-Rios M (2008) Use of Data Envelopment Analysis and Clustering in Multiple Criteria Optimization , Intelligent Data Analysis, Vol.12; pp.89-101
    15. O’Neill L , Rauner M , Heidenberger K , Kraus M (2008) A Cross-National Comparison and Taxanomy of DEA-based Hospital Efficiency Studies , Scio-Economic Planning Sciences, Vol.42; pp.158-189
    16. Po R , Guh Y , Yang M (2009) A new Clustering Approach using Data Envelopment , European Journal of Operations Research, Vol.199; pp.276-284
    17. Saati S , Hatami-Marbini A , Tavana M , Agrell PJ (2013) A Fuzzy Data Envelopment Analysis for Clustering Operating Units with Imprecise Data , International Journal of Uncertainty Fuzziness and Knowledge-Based System, Vol.21 (1 ) ; pp.29-54
    18. Sharma MJ , Yu SJ (2009) Performance based Stratification and Clustering for Benchmarking of Container Terminals , Expert Systems with Applications, Vol.36; pp.5016-5022
    19. Shin HW , Sohn SY (2004) Multi-attribute scoring method for Mobile Telecommunication Subscribers , Expert Systems with Applications, Vol.26; pp.363-368
    20. Schreyogg J , Reitzenstein C (2008) Strategic Group and Performance Differences among Academic and Medical Centers , Health Care Management Review, Vol.33 (3 ) ; pp.225-233
    21. Tone K (2001) A Slack-based Measure of Efficiency in Data Envelopment Analysis , European Journal of Operations Research, Vol.130; pp.498-509
    22. Torres GJ , Basnet RB , Sung AH , Mukkamala S , Ribeiro BM (2009) A Similarity Measure for Clustering and Its Applications , International Journal of Electrical Computer and System Engineer, Vol.3 (3 ) ; pp.164-170