- 2014 年 2 月 24 日
- ヴァシリス・ヴリニオティス
- 。 3コメント
DEAとしても知られるデータ包絡分析は、フロンティア分析を実行するためのノンパラメトリック手法です。 線形計画法を使用して複数の意思決定単位の効率を推定し、生産、管理、および経済学で一般的に使用されます。 この手法は最初に 1978年のチャーンズ、クーパー、ロードス それ以来、生産フロンティアを推定するための貴重なツールになりました。
更新：Datumbox Machine Learning Frameworkがオープンソースになり、無料で ダウンロード。 パッケージcom.datumbox.framework.algorithms.deaをチェックして、Javaでのデータ包絡分析の実装を確認してください。
5-6年前にこの方法に初めて出会ったとき、アルゴリズムの独創性、その単純さ、使用したアイデアの巧妙さに驚かされました。 オンラインマーケティング、検索エンジンのランキング、および複合指標の作成にうまく適用できるため、この手法が通常のアプリケーション（財務、運用調査など）以外でもうまく機能することを知って、さらに驚きました。 それにもかかわらず、今日のDEAはビジネスのコンテキスト内でほとんど独占的に議論されています。 そのため、この記事では、DEAの背後にある基本的なアイデアと数学的フレームワークについて説明し、次の投稿では、Webアプリケーションでのアルゴリズムの新しいアプリケーションをいくつか紹介します。
データ包絡分析が興味深いのはなぜですか？
データ包絡分析は、レコード（店舗、従業員、工場、ウェブページ、マーケティングキャンペーンなど）を、機能（重量、サイズ、コスト、収益、その他のメトリックまたはKPI）に基づいて比較およびランク付けすることを可能にする方法です。機能の重要性または重み。 この手法の最も興味深い部分は、まったく異なる測定単位を持つ複数の機能で構成されるレコードを比較できることです。 これは、キロメートル、キログラム、または通貨単位で測定された特徴を持つレコードがあり、それらを比較、ランク付けして、最高/最低および平均のパフォーマンスレコードを見つけることができることを意味します。 興味深いですね？ 読み続けます。
データ包絡分析の説明と仮定
前述のとおり、DEAはビジネスの生産性を測定するために発明された方法です。 したがって、そのアイデアのいくつかは、生産性がこのコンテキストで測定される方法から来ています。 この方法の中心的な特徴のXNUMXつは、レコード機能をXNUMXつのカテゴリ（入力と出力）に分離することです。 たとえば、自動車の効率を測定する場合、入力はガソリンのリットルであり、出力は走行距離です。
DEAでは、すべての機能が正である必要があり、それらの値が高いほど、それらの入出力が多いと想定されます。 さらに、データ包絡分析は、特徴が非負の重みの重み付き合計として線形に結合され、各レコードの効率を測定する入力と出力の比率を形成できると想定しています。 レコードが効率的であるためには、提供された入力に対して「良い」出力を提供する必要があります。 効率は、出力と入力の比率で測定され、他のレコードの比率と比較されます。
DEAの背後にある独創的なアイデア
これまでカバーしてきたのは常識/実践です。 レコードのランク付けには、入力と出力、加重和、比率を使用します。 DEAの賢いアイデアは、フィーチャの重みが計算される方法にあります。 分析を実行する前に、特徴の重みを設定し、重要度を決定する代わりに、データ包絡分析はデータから重みを計算します。 さらに、重みはすべてのレコードで同じではありません。
DEAが重みを選択する方法は次のとおりです。適切なフィーチャの重みを選択することにより、すべてのレコードの比率を最大化しようとします。 同時に、他のすべてのレコードの比率を計算するために同じ重みを使用した場合、それらのレコードが1より大きくならないようにする必要があります。
アイデアは最初は少し奇妙に聞こえます。 これは、異なる重み付けの比率の計算につながりませんか？ 答えはイエスです。 これは、実際にすべてのレコードの比率を異なる方法で計算することを意味しませんか？ 答えは再びイエスです。 これはどのように機能するのでしょうか？ 答えは簡単です。すべてのレコードについて、その特性を考慮して、比率が可能な限り高くなるように「理想的な状況」（重み）を見つけようとし、それによって可能な限り効果的にします。 しかし、同時に、この「理想的な状況」を考えると、他のレコードの出力/入力比率は1より大きくなることはありません。つまり、それらは100％より効果的ではありません。 各「理想的な状況」でのすべてのレコードの比率を計算したら、それらの比率を使用してランク付けします。
したがって、DEAの主なアイデアは次のように要約できます。「各レコードの特性に基づいて最高の比率スコアを達成できる理想的な状況を見つけます。 次に、各レコードのこの理想的な比率を計算し、それを使用してそれらの有効性を比較します。
例を見てみましょう
DEAを使用できる例を見てみましょう。
特定のチェーンのスーパーマーケットストアの効率を、従業員の総数、平方メートルでの店舗のサイズ、店舗での売り上げ、顧客数に基づいて評価するとします。彼らは平均して毎月役立つこと。 最も効率的な店舗を見つけるには、レコードを複数の機能と比較する必要があることが明らかになります。
DEAを適用するには、入力と出力のどちらを定義する必要があります。 この場合、出力は明らかに売上高とそれらがサービスを提供する顧客の数になります。 入力は、従業員の数と店舗のサイズです。 DEAを実行する場合は、理想的な重み（上記で説明）の下で、各ストアの出力と入力の比率を推定します。 それらの比率がわかったら、効率に従ってランク付けします。
数学の時間です！
DEAがどのように機能するかを直感的に理解できたので、次は数学について詳しく説明します。
入力xと出力yを持つ特定のレコードi（両方とも正の値を持つ特徴ベクトル）の効率比は、次の式を使用して推定されます。
ここで、uとvはレコードの各出力と入力の重み、sは出力特徴の数、mは入力特徴の数です。
特定のレコードiの最良/理想的な重みを見つける問題は、次のように定式化できます。
繰り返しますが、これらの重みが他のレコードを100％よりも効率的にしない場合、上記は、レコードiの効率を最大化する重みuおよびvを見つける数学的な方法にすぎません。
この問題を解決するには、線形計画法を使用する必要があります。 残念ながら、線形計画法では分数を使用できないため、問題の定式化を次のように変換する必要があります。
上記の線形計画問題はレコードiに最適な重みを与え、それらの最適な重みの下での効率を計算することを強調する必要があります。 データセットのすべてのレコードについて同じことを繰り返す必要があります。 したがって、n個のレコードがある場合、n個の別個の線形問題を解く必要があります。 DEAの動作方法の疑似コードは次のとおりです。
ratio_scores = [];
for every record i {
i_ratio = get_maximum_effectiveness();
ratio_scores[i] = i_ratio;
}
データ包絡分析の制限
DEAは優れた手法ですが、制限があります。 DEAはブラックボックスのようなものであることを理解する必要があります。 各レコードの有効率で使用される重みは異なるため、各スコアがどのように、なぜ計算されたかを説明しようとしても意味がありません。 通常は、有効性スコアの実際の値ではなく、レコードのランキングに焦点を当てます。 また、極値が存在すると、スコアの値が非常に低くなる可能性があります。
DEAは機能の線形結合を使用して比率を推定することを覚えておいてください。 したがって、それらを線形結合することがアプリケーションで適切でない場合は、フィーチャに変換を適用し、線形結合できるようにする必要があります。 この手法のもうXNUMXつの欠点は、レコード数と同じ数の線形計画問題を解決しなければならないことです。これは、多くの計算リソースを必要とするものです。
DEAが直面するもうXNUMXつの問題は、高次元データではうまく機能しないことです。 DEAを使用するには、次元の数d = m + sが観測の数よりも大幅に少ない必要があります。 dがnに非常に近いか、nより大きい場合にDEAを実行しても、すべてのレコードが最適であることが判明する可能性が高いため、有用な結果は得られません。 新しい出力変数（ディメンション）を追加すると、このディメンションで最大値を持つすべてのレコードが最適であることがわかります。
最後に、アルゴリズムの一般的な形式では、DEAの特徴の重みはデータから推定されるため、問題に含まれる可能性のある特徴の重要性に関する以前の情報を使用しないことに注意してください（もちろんこの情報を制約として線形問題に組み込むことが可能です）。 さらに、計算される効率スコアは「理想的な状況」で計算されるため、実際には各レコードの上限効率比です。 これは、機能の重要性について何も想定できない場合にDEAが優れたソリューションになる可能性があることを意味しますが、事前の情報がある場合、または機能の重要性を定量化できる場合は、代替手法を使用することをお勧めします。
次の記事では、実装の開発方法を紹介します JAVAでのデータ包絡分析 また、このメソッドを使用して、ソーシャルメディアネットワークでのWebページと記事の人気を推定します。
記事が気に入ったら、TwitterまたはFacebookで共有してください。 🙂
