整数計画法で不均衡データを均衡サンプリング(PuLP併用)
Posted On 2025-03-15
整数計画法(PuLP)を使えば小規模データでTrue/Falseの偏りをほぼ1:1にでき、最適解が得られます。一方、大規模データでは厳密解よりスピードを重視するグリーディ法が有効です。
目次
はじめに
- True/Falseの列がいくつかあるテーブルデータがあったとして、各列のTrue/Falseの分布がなるべく等しくなるようにサンプリングするにはどうすればいいのか?という問題
- 最適化手法を使うとうまくいって、2通りやり方があるそうだ(ChatGPTに聞いた)
- 整数計画法を使う:厳密だが中小規模のデータで有効。大規模データになったときは遅い
- ヒューリスティックなグリーディ法:精度は下がるが、大規模データになったときも速い
- 以下はGPTより。今回は上の整数計画法を使う
手法 | 精度 | 計算速度 | 大規模データ向け |
---|---|---|---|
整数計画(PuLP) | ◎(最適解) | ×(遅い) | ×(大規模データには不向き) |
グリーディ法 | ○(準最適) | ○(高速) | ◎(大規模データ向け) |
- 小規模データ(数千行以下) → 整数計画
- 大規模データ(数万行以上) → グリーディ法
PuLPによる整数計画法
以下の記事が参考になる
以下のコマンドでインストール
pip install PuLP
どのように整数計画法の問題に落とすか
Claude 3.7 Sonnetによる解説
このコードでは整数計画法を使って、不均衡なデータセットから各特徴(カラム)のTrue/Falseの値がバランスした行のサブセットを選択しています。
目的関数と決定変数
prob = LpProblem("BalanceSelection", LpMinimize)
row_vars = {i: LpVariable(f"row_{i}", cat=LpBinary) for i in range(len(df))}
- 決定変数: 各行を選択するかどうかを表す二値変数(
row_vars[i]
) - 目的関数: 実は明示的な目的関数は設定されていません。このコードでは「制約を満たす実行可能解を1つ見つける」というアプローチになっています。
制約条件
# 選択行数の制約
prob += lpSum(row_vars.values()) == num_select
- 選択される行数が正確に
num_select
(20行)になるよう制約
# 各カラムのTrueとFalseのバランスを最小化する制約
for col in df.columns:
true_count = lpSum(row_vars[i] for i in df[df[col] == True].index)
false_count = lpSum(row_vars[i] for i in df[df[col] == False].index)
prob += true_count - false_count <= 1 # TrueとFalseの差が1以下
prob += false_count - true_count <= 1 # TrueとFalseの差が1以下
- 各カラムについて、選択された行のTrue値とFalse値の数の差が最大1になるよう制約
- これにより、選択された行のサブセットでは各カラムがほぼ均等(差が最大1)になる
不均衡の解消方法
元のデータセットでは各カラムのTrue確率が異なる(0.2 + 0.1 * i
)ため不均衡ですが、この整数計画法によって:
- 各カラムのTrue/False比率がほぼ1:1(差が最大1)となる行の組み合わせを探索
- その制約を満たしながら、指定された行数(20行)を選択
- 結果として、選択されたサブセットでは元データの不均衡が解消される
結果
最初に作ったデータフレーム。不均衡が見られる
col_0 col_1 col_2 col_3 col_4
0 False True False True True
1 False False True False False
2 False False True False True
3 False False False False False
4 True False False False True
5 True True True False False
6 True False True False True
7 False False False True True
8 False True True False False
9 False True True True True
10 True True False True True
11 False True False True False
12 False False False True False
13 False False True False True
14 True False False False False
15 True False True False True
16 False False True True True
17 False True False True True
18 False False False True False
19 False False False True False
整数計画法により選択されたデータ。不均衡が解消されている
col_0 col_1 col_2 col_3 col_4
1 False False True False False
5 True True True False False
9 False True True True True
10 True True False True True
12 False False False True False
23 False True True True True
32 True True False True False
35 False False False True False
37 True False True False False
40 True False False True True
50 False False True False False
52 False True False False True
55 False True False False True
56 True False False True True
68 True True True True True
79 True True False True True
83 True False True False False
84 False True False False True
85 False False True False False
最適化の結果。100行ぐらいのデータならめっちゃ速い
Result - Optimal solution found
Objective value: 0.00000000
Enumerated nodes: 3
Total iterations: 222
Time (CPU seconds): 0.07
Time (Wallclock seconds): 0.07
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.07 (Wallclock seconds): 0.08
col_0 0.5
col_1 0.5
col_2 0.5
col_3 0.5
col_4 0.5
全体コード
import pandas as pd
import numpy as np
from pulp import LpProblem, LpVariable, lpSum, LpMinimize, LpBinary
# ダミーデータ作成:各カラムで True の確率を 0.2 + 0.1 * i に設定
np.random.seed(42)
data = {}
num_rows = 100
num_cols = 5
for i in range(num_cols):
true_prob = 0.2 + 0.1 * i
data[f'col_{i}'] = np.random.choice([True, False], size=num_rows, p=[true_prob, 1-true_prob])
df = pd.DataFrame(data)
print(df.head(n=20))
# 固定の選択行数
num_select = 20
# 最適化問題の定義
prob = LpProblem("BalanceSelection", LpMinimize)
# 各行が選択されるかどうかを表す二値変数
row_vars = {i: LpVariable(f"row_{i}", cat=LpBinary) for i in range(len(df))}
# 選択行数の制約
prob += lpSum(row_vars.values()) == num_select
# 各カラムのTrueとFalseのバランスを最小化する制約
for col in df.columns:
true_count = lpSum(row_vars[i] for i in df[df[col] == True].index)
false_count = lpSum(row_vars[i] for i in df[df[col] == False].index)
prob += true_count - false_count <= 1 # TrueとFalseの差が1以下
prob += false_count - true_count <= 1 # TrueとFalseの差が1以下
# 解く
prob.solve()
# 選択された行を取得
selected_indices = [i for i in row_vars if row_vars[i].varValue == 1]
selected_df = df.iloc[selected_indices]
# 確認:各カラムのTrue比率を表示
print(selected_df.mean())
print(selected_df)
Shikoan's ML Blogの中の人が運営しているサークル「じゅ~しぃ~すくりぷと」の本のご案内
技術書コーナー
北海道の駅巡りコーナー