経営課題にAIを!ビジネスインフォマティクス研究会 (第16回)
JSAI Special Interest Group on Business Informatics (SIG-BI #16)

DEA によるシミュレーション・ログ集合の分類
A Classification of the Simulation Log Set by DEA
國上真章 1 菊地剛正 2

寺野隆雄 3Masaaki Kunigami 1, Takamasa Kikuchi 2, and Takao Terano 3
東京工業大学Tokyo Institute of Technology2
慶應義塾大学2
Keio University
3
千葉商科大学3
Chiba University of Commerce
1

1

Abstract: This study proposes a method of using Data Envelopment Analysis (DEA) to classify a set of
input/output logs in a social or organizational simulation and compares it with previous methods based oncluster analysis using examples. DEA is used mainly in policy analysis as a method to compare theefficiency based on multiple input and multiple output data. In DEA, the entire data is partitioned by thedata that define efficiency corner points, called reference sets. In this study, we propose to use DEA as aclassifier of simulation logs due to this property of reference sets. In this paper, we illustrate how DEA
allows us to classify a set of simulation logs by their characteristics, using the SIR model of infectious
disease spreading with additional variables multiple indicating measures. In addition, the results werecompared with the results of the previous log classification using cluster analysis.

1 はじめに

2 包絡分析法（DEA）

本稿は，社会や組織のシミュレーションの入出力
ロ グ 集 合 の 分 類 に 包 絡 分 析 法 (Data EnvelopmentAnalysis: DEA)の活用を提案するものである．DEA
は多入力・多出力の経営データ間の効率性を相互に比較する手法として，政策分析等で利用されている[1]．DEA による分類では参照集合と呼ばれる効率性の端点を定める経営データによってデータ全体が分割される．本稿では，この参照集合の性質によりDEA をシミュレーション・ログの分類器として用いる．
これまでに田中[2]は，組織シミュレーションのログをクラスター分析により分類するとともに，各クラスター毎にその性質を特徴づける意志決定を決定木により抽出する方法を提案している．また菊池[3]は，クラスター分析によりログを類型化し，形式化された仮想ケースとして記述している．
本稿ではシミュレーションの入出力ログをその振舞いに応じて分類するために DEA による方法を提案し，その特徴についてクラスター分析と比較しつつ考察する．

Charnes，Cooper，Rhodes が 1978 年に提案した包絡分析法 (Data Envelopment Analysis: DEA)[4]は，複数の入力と複数の出力をもつ意思決定主体（DecisionMaking Unit: DMU）の効率性を比較する手法である．
DEA では各 DMU について，より最適化された効率性を持つ DMU からなる参照集合（Reference Set）による特徴づけを行うとともに，参照集合をつないで生成される包絡線（Envelopment）により，DMU の相対的な位置づけの比較を可能にする．

2.1 DEA の考え方
DEA の最も基本的な方法である CCR 法[4]の考え方は，次のとおりである．a) 複数の入出力をもつ意
志決定主体（DMU）の重み付き効率性，b) 各 DMUの効率の重みの最適化を通した DMU 間の効率性の比較，c) 劣効率的な DMU に対しての最適な効率性を持つ DMU の集まりである参照集合（ReferenceSet）による特徴づけである．
まず，複数（K 個）の意志決定主体のそれぞれDMUk (k = 1~K) が，M 成分の入力 xk ={xkm >0 | m =経営課題にAIを!ビジネスインフォマティクス研究会 (第16回)
JSAI Special Interest Group on Business Informatics (SIG-BI #16)

1~M} から N 成分の出力 yk {ykn >0 | n = 1~N} を生成するとする．この時，各 DMUk の効率性Θk は，入力xk と出力 yk に重み ξk ={ξkm >0 (m = 1~M)}, ηk (ηkn>0 (n = 1~N))をつけて，Θk ≡ (ηk·yk) /(ξk ·xk) =∑n,m{(ηknykn) / (ξkm xkm)}と定義できる．（図１）
xk1
xk2
:xkM

Θk ≡N
η⋅y=  η kn y kn
ξ ⋅ x n =1km

M
 N

E k = k ′  η n y k ′n =  ξ m xk ′m (k ′ = 1 ~ K )m =1
 n =1
kmm =1

図１：意志決定主体 DMU と効率性Θ．

図４：分数計画問題（図 2）は等価な線形計画問題によって解くことができる．

このとき，重み ξk , ηk はいくらでも動かせるので，効率性 Θk は変わってしまう．そこで相互に比較するので効率性の上限は１（Θk ≤ 1）で共通化した上で，それぞれの DMUk の効率性 Θk を最も有利になるように重み ξk , ηk を最適化する．ただしこの最適化の際，その重み ξk , ηk で他の全ての DMUh 効率性
も 1 を超えない（Θh ≤ 1）ように最適化するのがポイントである．（図２）Nη ,ξn =1Mξ xmm =1km

DMUkの効率性ΘkM N  η n y hn  ξ m xhm ≤ 1 (h = 1 ~ K )m =1
 n =1
そのη, ξ で他のDMU
s.t. 
η n ≥ 0 (n = 1 ~ N ) の効率性Θhが１を超えないよう制限 ξ m ≥ 0 (m = 1 ~ M )重み 全て非負 ξ kn = ξ n∗ , η kn = η n∗

図２：DMU の効率性Θを求める最適化問題．
もし最適化した重みでもでも効率性 Θk =1 にできず他の DMUk’ の Θk’ に劣れば，DMUk は効率的でないといえる．このとき，DMUk を最適化した重みにおいてもその効率性 Θk を上回り最適な効率性が1 と な る DMUk’ を DMUk の 参照 集 合 Ek と い い ，DMUk にとっての効率性改善の参考となる．（図３）

E k = k '  η kn y k 'n
 n =1N

効率性の分母を１に固定する  ξ m xkm = 1
制約式を等価な m =1不等式に変更
 NMs.t.   η n y k ′n ≤  ξ m xk ′m (k ′ = 1 ~ K ) n =1m =1 η ≥ 0 (n = 1 ~ M ) n ξ ≥ 0 (m = 1 ~ M ) mM

ξ xn =1Mn = 1~N,ykn > 0 (∀k, ∀n)k = 1~Kmax Θ k =  η n y kn

η ,ξyk1yk2:yNkDMUkm = 1~M,xkm > 0 (∀k, ∀m)

Nmax Θ k =  η n y kn

M



m =1

 ξ km xk 'm = 1 (1 ≤ k ' ≤ K )DMUkを最適化してもΘk<1のとき ，Θk=1を妨げている
他のDMUk′ （kのための最適化の重みでも効率1となる）が存在する

DEA を用いることの利点の一つが，このように多入力多出力系の効率性を比較する際の重みをどう決めるかという問題が，上記の最適化のプロセスで自動的に解決されることにある．

2.2 DEA による分類
DEA においては，ある DMUk にとってその参照
集合 Ek は，DMUk にとって改善の参考となる対象であり，効率的な DMU の参照集合は自分自身である．
また，入出力変数で張られる空間において DMU の散布図を描くと，効率的な DMU は全 DMU の包絡線となる．また効率的な DMU と原点で分割される領域には，その効率的な DMU を参照集合とする効率的でない DMU が含まれる．よってこれらの DMU達は同じ参照集合を共有するという性質で分類されていることになる．（図 5）（M=1, N=2 のとき）

y1/x

k :DMUk

152

3476

効率的DMU:{1, 5, 6}
E1 ={1}, E5 ={5}, E6 ={6}
非効率的DMU: {2, 3, 4, 7, 8}
E2 = E3 = {1, 5}
E4 = E7 = {5, 6}
E6 = {6}
参照集合を共有するという性質によって分類できる

8y2/x
図５：効率的な DMU（参照集合）により包絡線を分割すると非効率な DMU を分類できる．

図３：DMUk の参照集合 Ek．
ここまでに見た DEA の最適化（図２）は，分数計画問題として定式化されているが，実用上は次の等価な線形計画問題に変換して解かれる．（図４）

同じ参照集合を共有する DMU は，効率性の改善について同じ方向（参照集合の元）を共有している．
このように，分類群の中において分類群を特徴付ける元（効率的な DMU～参照集合の元）と，その他の

経営課題にAIを!ビジネスインフォマティクス研究会 (第16回)
JSAI Special Interest Group on Business Informatics (SIG-BI #16)

元（非効率的な DMU）の関係が，自動的に与えられることが DEA を用いることの今一つの利点である．
また部分的にしか一致しない参照集合をとるグループ間においては，共通する部分とその多少によってグループ間の類似性を考察することができる．これも分類器としての DEA を見たときの利点である．

3 シミュレーションへの適用
簡単なシミュレーションを用いて，その入出力データを DEA により分類してみる．シミュレーションモデルとしては，感染症伝播に関する SIR モデル[5]を用いる．ただし SIR モデルは，独立な自由度が２しかないため，出力の自由度とともに政策的な入力変数を追加して DEA を適用する．

3.1

SIR モデルの拡張

本稿で例題として用いる拡張した SIR モデルは以下の状態遷移（図６）を持つ差分方程式系（式(1)～(3)）である．
Ｓ：未感染・感受性
susceptibles

Ｉ：感染・伝染性
infectives

Ｒ：回復・抵抗性
recovered/resistant

口を I(t)，回復した非感受性人口を R(t) とし，さらに死亡人口を D(t)として追加した，従属変数 P(t)は生存者人口である．また感染率 c, 治癒率 h, 死亡率m を，制御変数 u(t), v(t), w(t) によって変化させられる変数とした．ここで正定数 c0, h0, m0 は制御入力がない時の c(t), h(t), m(t) の値を示し，正定数 αu , αv ,αw はそれぞれ u(t), v(t), w(t)の感度である．
制御入力 u(t), v(t), w(t)について，u(t)は感染率 c(t)を抑制する施策を，v(t)は治癒率 h(t)を向上させる施策を，w(t)は死亡率 m(t)を抑制する施策をそれぞれ表す．これらの費用と効果はそれぞれ異なるが費用で規格化することで一般性を失わずにその違いを感度
αu , αv , αw のみで表し，費用制約は u(t) + v(t) + w(t) ≤ 1としている．

DEA による結果の分類

3.2

前節で導入した拡張された SIR モデルを例として用いて，シミュレーションの入出力データの集合をDEA によって分類する．共通する初期値，係数等は表１のとおりである．
InitialConditions

S(0):

I(0) = ε :

R(0):

D(0):

Susceptibles

Infectives

Recovered

Dead

9990

1000

P(0): Population Alive =10000

S(t)c I(t)S(t)c: congestion

I(t)h I(t)

R(t)Coefficientsh: healingm I(t)

m: mortality

D ：死亡
dead

D(t)

ControlSensitivities

c0h0m0

Contagion

Healing

Mortality

0.00002

0.01

0.01

αuαv

αw

101520

表１：シミュレーションの初期値および係数
図６：拡張された SIR モデルの状態遷移と差分方程式系および制御入力
 S (t + 1) = S (t ) − c(t ) S (t ) I (t ), I (t + 1) = I (t ) + c(t ) S (t ) I (t ) − h(t ) I (t ) − m(t ) I (t ),⋯⋯ (1)
 R(t + 1) = R(t ) + h(t ) I (t ), D(t + 1) = D(t ) + m(t ) I (t ).
 P(t ) = S (t ) + I (t ) + R(t ), population alive,⋯⋯ ( 2)
 P(0) = P0 , initial population,
 S (0) = P − ε , I (0) = ε , , R (0) = 0, D (0) = 0.
0c0
, : contagion, c(t ) =α
1+u ⋅ u (t ) h(t ) = h (1 + α ⋅ v(t )), : heeling,  u (t ), v(t ), w(t ) ≥ 0 ⋯ (3)0v
 u (t ) + v(t ) + w(t ) ≤ 1
m0
 m(t ) = 1 + α ⋅ w(t ) , : mortality.
w

式(1)は状態変数の時間変化を，式(2)は従属変数と状態変数の初期値を，式(3)は制御変数による係数の時間変化を表す．
状態変数は，未感染の感受性人口を S(t), 感染者人

次に，シミュレーション実行(RUN)設定は，表２に示す 10 通りの制御入力の割付に従った．
Stage-0
Stage-1
Stage-2
Stage-3
t = 0 ~ 29
t = 30 ~ 89
t = 90 ~ 179
t = 180 ~ 500
u (t ) v (t ) w (t ) u (t ) v (t ) w (t ) u (t ) v (t ) w (t ) u (t ) v (t ) w (t )RUN #(DMU #)

00.0 0.0 0.0 0.0 0.0
11.0 0.0 0.0 1.0 0.0
2
1.0 0.0 0.0 0.0 1.0
3
1.0 0.0 0.0 0.0 0.0
4
0.0 1.0 0.0 1.0 0.0
0.0 0.0 0.0
5
0.0 1.0 0.0 0.0 1.0
60.0 1.0 0.0 0.0 0.0
7
0.0 0.0 1.0 1.0 0.0
8
0.0 0.0 1.0 0.0 1.0
90.0 0.0 1.0 0.0 0.00.0
0.00.01.00.00.4 0.3 0.30.0
1.0
0.0
0.0
1.0

表２：シミュレーションの実行設定．
上記の設定から得られた実行結果の要約値は表３のとおりである．要約値を用いたのは，本例では実行数が少ないためと，DEA の性質から出力変数は正の望大特性であることが必要なためである．

経営課題にAIを!ビジネスインフォマティクス研究会 (第16回)
JSAI Special Interest Group on Business Informatics (SIG-BI #16)

Cs

Input:Cm

BtmActP

OutPut:AvgActP

AlvPE

Social Cost:

Medical Cost:

Bottom Active
Population:

Average Active
Population:

Alive Poplation at
the end:

接触・感染防止 感染者の回復と 活動可能な人数
活動可能な人数 最終的に生き残の社会的コスト: 救命コスト:が最も落ち込んの平均値:った人の数:
Avg[ P (t )· α u
Avg[I (t ){α v · v (t ) だ時の値:
Avg[P (t )-I (t )]Min[P (t )]Min[ P (t )-I (t )]· u (t )]+ α w · w (t )}]012
3
Run # 4(DMU #) 5
6
7
8
9

13,574
49,69334,73734,481
41,87924,652
24,32833,20324,08824,418231340
617
19,220
912
919
6,776
15,244
15,932
29,615

1,915
8,176
8,371
2,514
8,650
8,650
6,505
1,906
1,906
1,906

5,112
8,590
9,011
7,974
9,560
9,575
9,147
6,589
8,663
8,082

ついて，グループの特徴づけがされている．さらに，参照集合の共有の有無によってグループ間の近さも読み取ることができる．
参照集合
(Θ=1)

5,296
8,638
9,072
8,967
9,603
9,619
9,488
7,235
9,399
9,524

120586943

劣効率的なデータ(Θ<1)
InputWeight

表３：シミュレーションの実行結果（入出力要約値）

Output Weight

7Cm > 5.0

Cm = 0

BtmActP > 0.5

BtmActP = 0

図７：DEA による入出力要約値のグループ化
表４は，シミュレーションの入出力要約値のデータ（表３）から DEA（CCR 法）によって求めた，最適な効率性Θ（DEA Score），参照集合（Reference Set），入出力の要約値への最適化された重み（Input Weight,Output Weight）である．なお CCR 法の計算について
は，並木[6]による Python コードを用いた．
DEA_CCRDEA Reference
Score ΘSet01234Run #(DMU #) 5
6789

1.0 {0, 1, 2}
1.0{1}
1.0 {1, 2}
0.6665 {8, 5}
0.7903 {0, 2, 5}
1.0{5}
0.9995 {8, 5}
0.5584 {8, 5}
1.0{8}
0.9997{8}

3.3

クラスター分析による分類

次に，同じ入出力要約値（2 入力 3 出力）について，クラスター分析による分類を行う．分類は階層的クラスタリングの Ward 法により，データ間の距離は Euclid 距離を用いた．

Input Weights
Output Weights
Cs
Cm BtmActP AvgActP AlvPE

0.4
0
0.1
0.3
0.1
0.4
0.4
0.3
0.4
0.4

22.4
29.48.405.3000001.8
1.2
1.200.5
1.2000000000.4000001.2000.700
1.10.81.11.0

表４：DEA による表３の入出力要約値の分析結果
DEA の結果（表４）によると，効率的な実行結果として，{Run 0, 1, 2, 5, 8}が得られた．一方，非効率な実行結果としては，{Run 3, 6, 7}が{Run 5, 8}を参照集合として共有する分類群となっており，入出力要約値の重みづけも互いに近い傾向を示している．
また効率的な実行結果である，{Run 0, 1, 2, 5, 8}については，Run 8 と 5 にはこれらを参照集合として共有するグループがあり，Run 0, 1, 2 は互いを参照集合としているなどそれぞれの間で違いが少ないことを示している．反面，Run 8 と Run 0, 1 の間にはこれらを共有する非効率集合が無いなど，これらの間で違いが大きいことを示している．
これらの結果を模式的にまとめたのが図 7 である．効率的な実行結果（参照集合）の共有によって，実行結果がグループ化されている，これによりグループ内での効率性の改善の参考となるデータが明らかになっている．また最適な入出力要約値の重みに

図８：入出力要約値のクラスタリング
クラスタリングによる，入出力要約値の類似性（ベクトルとしての距離の近さ）による樹形図は図８のとおりである．

4 考察
これまでに見たように DEA による分類とクラスター分析では，同じデータに対しても異なった分類を示す．ここでは DEA とクラスター分析のアプロー
チについて分類器としての特徴という視点でから追加的に考察する．
まず基本的なアプローチについて，DEA ではグループの分類と特徴づけは，参照集合によって行われる．参照集合はグループの端点であり，グループ内でも特異な元である．このためクラスター分析のようななグループ内の平均あるいは重心付近の元という意味は持たないが，グループ内の元の効率性の方向性でのトップという意味は明確である．

経営課題にAIを!ビジネスインフォマティクス研究会 (第16回)
JSAI Special Interest Group on Business Informatics (SIG-BI #16)

ＤＥＡ

クラスタリング

対して相反する性質を有する．このことから DEA による分類は，クラスター分析を超えるものというよりは，互いに補う様に使うことでより分析の幅を広げられる可能性を持つと考えられる．

5 まとめ
図８：クラスタリングが互いに近いものをまとめるのに対し DEA は端点でグループ化する．
DEA による分類においては，入出力の重みは自動的に最適化される．このためクラスター分析でのデータの重みをどう決めるかという問題は，DEA 任せにできる．一方 DEA には，分類に特化した方法ではないための使い勝手の悪さも存在する．例えば，クラスター分析では，生成するクラスターの階層数を選ぶことができる．これ対し DEA では，グループの数は DEA 任せであり，一つのグループしか生成されないことや，すべてのグループがひとつの参照集合しか含まないということもあり得る．また DEA では，入力は正の望小特性，出力は正の望大特性である必要があり，負の値や望大特性と望小特性が入り交ざっていると事前にデータの変換処理が必要になる．
次に，データの追加に対する安定性について比較してみる．まず，グループの内側に非効率なデータが追加される場合，DEA によるグループ分けは影響を受けない．一方クラスター分析ではクラスター間に中間的なデータが追加されるとクラスタリングが大きく影響される可能性がある．（図９上）
他方，新たな包絡線の外側に位置するようなデータが追加された場合，DEA によるグループ分けは大きな影響を受ける．一方，クラスター分析では大きな外れ値は独立したクラスターとなり，その他のクラスタリングには影響しない．（図９下）

本稿は，シミュレーション入出力ログ集合の分類法としての DEA の活用を提案し，シミュレーションによる例題と，クラスター分析との比較を考察した．
DEA による分類は，クラスタリングと相互補完的な分類器となると考えられる．ログの本格的な分類器として活用するためには，Window 分析等の時系列の DEA も必要であり，今後検討を深めていきたい．

謝辞
本稿の着想の多くは，竹内俊彦先生の解説[7]に拠っている，この場で深く感謝を表したい．また，本研究の一部について，公益財団法人科学技術融合振興財団の調査研究助成を受けている．

参考文献：[１] Cooper, WW., Seiford, LM., Tone, K.: Data Envelopment
Analysis, A Comprehensive Text A Comprehensive Text
with Models, Applications, References and DEA-Solver
Software (Second Edition), Springer, (2007).
[２] 田中祐史, 國上真章, 寺野隆雄: エージェントシミュ
レーションにおけるログクラスターの系統的分析からわかること, シミュレーション＆ゲーミング,
Vol.27, No.1, pp. 31-41, (2017)
DOI https://doi.org/10.32165/jasag.27.1_31[３] 菊地剛正, 國上真章, 高橋大志, 鳥山正博, 寺野隆雄
ビジネスケースの形式的記述のためのシミュレーシ
ョン結果の類型化手法, 経営情報学会論文誌 研究ノート Vol.29,

ＤＥＡ

クラスタリング

No.3, (to be published 2020)[４] Charnes, A., Cooper, WW., Rhodes, E.: Measuring
Efficiency of Decision Making Units, European Journalof Operational Research, Vol.2 , pp.429-444, (1978).
[５] Kermack, WO., McKendrick, AG.: A Contribution to the
Mathematical Theory of Epidemics, Proceedings of theＤＥＡ

クラスタリング

Royal Society, vol.115A, pp.700–721 (1927),
DOI https://doi.org/10.1098/rspa.1927.0118,(reprinted Bulletin of Mathematical Biology vol.53,pp.33-55 (1991))[６] 並木誠: Python による数理最適化入門, 朝倉書店,
pp.70-71, (2018)

図９：新しいデータの追加に対する安定性：図８のグループの内部に追加（★）された場合（上）とグループの外側に追加（★）された場合（下）このように DEA による分類は，クラスター分析に[７] 竹 内 俊 彦 : DEA 入 門 ・ 泉 恵 女 学 園 物 語 ,http://blog.livedoor.jp/lionfan/archives/52682140.html,(2020.8 閲覧)