整数計画法で不均衡データを均衡サンプリング（PuLP併用）

Posted On 2025-03-15

2{icon} {views}

整数計画法（PuLP）を使えば小規模データでTrue/Falseの偏りをほぼ1:1にでき、最適解が得られます。一方、大規模データでは厳密解よりスピードを重視するグリーディ法が有効です。

はじめに

True/Falseの列がいくつかあるテーブルデータがあったとして、各列のTrue/Falseの分布がなるべく等しくなるようにサンプリングするにはどうすればいいのか？という問題
最適化手法を使うとうまくいって、2通りやり方があるそうだ（ChatGPTに聞いた）
- 整数計画法を使う：厳密だが中小規模のデータで有効。大規模データになったときは遅い
- ヒューリスティックなグリーディ法：精度は下がるが、大規模データになったときも速い
以下はGPTより。今回は上の整数計画法を使う

手法	精度	計算速度	大規模データ向け
整数計画（PuLP）	◎（最適解）	×（遅い）	×（大規模データには不向き）
グリーディ法	○（準最適）	○（高速）	◎（大規模データ向け）

小規模データ（数千行以下） → 整数計画
大規模データ（数万行以上） → グリーディ法

PuLPによる整数計画法

以下の記事が参考になる

最適化におけるPython（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の中の人が運営しているサークル「じゅ～しぃ～すくりぷと」の本のご案内

技術書コーナー

Tags:PuLP, 整数計画法, 最適化