整数計画法で不均衡データを均衡サンプリング(PuLP併用)
Posted On 2025-03-15
整数計画法(PuLP)を使えば小規模データでTrue/Falseの偏りをほぼ1:1にでき、最適解が得られます。一方、大規模データでは厳密解よりスピードを重視するグリーディ法が有効です。
目次
はじめに
- True/Falseの列がいくつかあるテーブルデータがあったとして、各列のTrue/Falseの分布がなるべく等しくなるようにサンプリングするにはどうすればいいのか?という問題
- 最適化手法を使うとうまくいって、2通りやり方があるそうだ(ChatGPTに聞いた)
- 整数計画法を使う:厳密だが中小規模のデータで有効。大規模データになったときは遅い
- ヒューリスティックなグリーディ法:精度は下がるが、大規模データになったときも速い
- 以下はGPTより。今回は上の整数計画法を使う
手法 | 精度 | 計算速度 | 大規模データ向け |
---|---|---|---|
整数計画(PuLP) | ◎(最適解) | ×(遅い) | ×(大規模データには不向き) |
グリーディ法 | ○(準最適) | ○(高速) | ◎(大規模データ向け) |
- 小規模データ(数千行以下) → 整数計画
- 大規模データ(数万行以上) → グリーディ法
PuLPによる整数計画法
以下の記事が参考になる
以下のコマンドでインストール
どのように整数計画法の問題に落とすか
Claude 3.7 Sonnetによる解説
このコードでは整数計画法を使って、不均衡なデータセットから各特徴(カラム)のTrue/Falseの値がバランスした行のサブセットを選択しています。
目的関数と決定変数
- 決定変数: 各行を選択するかどうかを表す二値変数(
row_vars[i]
) - 目的関数: 実は明示的な目的関数は設定されていません。このコードでは「制約を満たす実行可能解を1つ見つける」というアプローチになっています。
制約条件
- 選択される行数が正確に
num_select
(20行)になるよう制約
- 各カラムについて、選択された行のTrue値とFalse値の数の差が最大1になるよう制約
- これにより、選択された行のサブセットでは各カラムがほぼ均等(差が最大1)になる
不均衡の解消方法
元のデータセットでは各カラムのTrue確率が異なる(0.2 + 0.1 * i
)ため不均衡ですが、この整数計画法によって:
- 各カラムのTrue/False比率がほぼ1:1(差が最大1)となる行の組み合わせを探索
- その制約を満たしながら、指定された行数(20行)を選択
- 結果として、選択されたサブセットでは元データの不均衡が解消される
結果
最初に作ったデータフレーム。不均衡が見られる
整数計画法により選択されたデータ。不均衡が解消されている
最適化の結果。100行ぐらいのデータならめっちゃ速い
全体コード
Shikoan's ML Blogの中の人が運営しているサークル「じゅ~しぃ~すくりぷと」の本のご案内
技術書コーナー