表形式データ拡張手法 part12：MWMOTE

TL; DR

• MWMOTEはSMOTEで発生する多数クラスデータ領域の侵害を防ぐためのクラスターベースの手法である
• $k$-nnを3回実行することによって決定境界に近いデータを特定し，それを基にデータの拡張を行う
• 多数クラスデータにどれだけ近いかなどを考慮に入れて，各少数クラスサンプルの選択確率を重み付けし，更にクラスタリングも組み合わせることで境界付近でありながら安全なデータ生成を実現する

基本情報

SMOTEの記事で説明した通り，幅広い分野で使われる表形式データにはクラス不均衡という大きな課題があります．それを解決するために使用されるのが表形式データ拡張であり，その代表格がSMOTEです．

そのシンプルさと強力さから，SMOTEには多くの変種があります．実際，自分がこれまで説明してきた12手法のうち，ROSEを除いた11手法がSMOTEをベースにしたものです(何故かROSEがSMOTEベースの手法と紹介している論文がありますが，これは明らかに間違いです)．それらは主にSMOTEの欠点を解消することを目的として設計されています．

各手法の工夫点は各手法ごとの記事を読んでいただくとして，それらの手法の改善の方向性としてよく挙げられるものとして多数クラス領域の侵害を回避し，分類器への悪影響を軽減すること があります．これはSMOTEが多数クラス分布を考慮に入れないために，多数クラス領域にデータを生成してしまう可能性があることに対する改善です．例えばSafe-Level-SMOTEでは周辺の多数クラスデータの個数に応じて，安全な領域にデータを生成するというアプローチをとっています．

本記事で紹介するMajority Weighted Minority Oversampling TEchnique (MWMOTE) もそのような目的で設計されている手法です．著者らはBorderline-SMOTEやSafe-Level-SMOTEのような$k$-nnを単純に適用するような手法では，領域の侵害を完全には回避できないという理由でより複雑なアプローチを採用しています．

これからMWMOTEの説明を始めるわけですが，事前に注意喚起しておきます．それは本手法はかなり複雑なので，初めて表形式データ拡張を行うような人に対してはいきなりこの手法を理解しようとすることはおすすめしないということです．なるべくわかりやすく説明するように心がけますが，著作権の問題で論文の図を引用していいのかいまいちわからない以上，文章ベースの説明になってしまいます．もし原論文を読める環境であればそちらの図を見ながらこちらを読むことをおすすめします．

なお，書いていて流石に長過ぎるなと思ったのでTL; DRの章を入れておきます．全部読むのが面倒な人はそちらを見て下さい．

MWMOTEのアルゴリズムの紹介

アルゴリズムを紹介するわけですが，非常に長いため，一旦全体像をお見せしてから各ステップの内容について詳しく説明するような形にしたいと思います．その際，意識しておいてもらいたいことは，MWMOTEはBorderline-SMOTEと同様に決定境界に近い点ほど分類に重要であるため，そこを重点的にオーバーサンプリングする という考えのもとで設計されているという点です．この分野のみならず，手法の理解をするときには作成者がどのような思想のもと設計したのかを考慮したほうがわかりやすくなると思います．それでは始めます．

全体の流れ

初めに使用する用語について説明しておきます．$S_{maj}$はデータセットのうち多数クラスデータの集合，$S_{min}$は少数クラスデータの集合，そして$N$を最終的に必要とする拡張データの個数であるとします．また，本手法では$k$-nnを3回別々に実施するため，$k_1, k_2, k_3$の3つのパラメータが設定されています．流れとしては以下のとおりです．

1. 少数クラスデータに対する$k$-nn
   各少数クラスデータに対して，ユークリッド距離を用いてすべてのデータの中で$k_1$個の近傍点を探索する．この時，中心となる少数クラスデータを$x_i$として，その近傍点を$NN(x_i)$とする．この時，$NN(x_i)$には少数クラスデータと多数クラスデータが含まれる．
2. 少数クラスデータのフィルタリング
   少数クラスデータ$x_i$のうち，近傍点$NN(x_i)$に少数クラスデータが含まれないものをノイズデータとして削除した，フィルタリング後少数クラスデータ集合$S_{minf}$を構築する．
3. 多数クラスデータ近傍点の探索
   $S_{minf}$に属する各少数クラスデータ$x_i$に対して，多数クラスデータの中で$k_2$個の近傍点を探索する．これを$N_{maj}(x_i)$とする．この集合には多数クラスデータのみが含まれる．
4. ボーダーライン多数クラスデータ集合の構築
   $N_{maj}(x_i)$に含まれる多数クラスデータを結合し，ボーダーライン多数クラスデータ集合$S_{bmaj}$を構築する．
5. ボーダーライン少数クラスデータの探索
   $S_{bmaj}$に含まれる多数クラスデータ$y_i$に対して，少数クラスデータの中で$k_3$個の近傍点を探索する．これを$N_{min}(y_i)$とする．この集合には少数クラスデータのみが含まれる．
6. ボーダーライン少数クラスデータ集合の構築
   $N_{min}(y_i)$に含まれる少数クラスデータを結合し，ボーダーライン少数クラスデータ集合$S_{imin}$を構築する．
7. 少数クラスデータに対する情報重みの計算
   $S_{bmaj}$に含まれる各多数クラスデータ$y_i$および，$S_{imin}$に含まれる各少数クラスデータ$x_i$に対し，情報重み$I_w(y_i, x_i)$を計算する．なお，この重みの定義は後ほど説明する．
8. 少数クラスデータに対する選択重みの計算
   7で計算した情報重み$I_w(y_i, x_i)$を用いて，各少数クラスデータに対する選択重み$S_w (x_i)$を
   $S_w(x_i) = \sum_{y_i \in S_{bmaj}} I_w(y_i, x_i)$
   のように計算する．
9. 少数クラスデータに対する選択確率の計算
   先ほど計算した選択重み$S_w (x_i)$を用いて選択確率$S_p(x_i)$を
   $S_p(x_i) = S_w(x_i) / \sum_{z_i \in S_{imin}} S_w(z_i)$
   のように計算する．
10. 少数クラスデータのクラスタリング
    少数クラスデータ集合$S_{min}$(少数クラスデータ全てであって，フィルタリング後の集合$S_{minf}$ではないことに注意)をクラスタリングする．
11. 拡張データの合成
    少数クラスデータ選択確率$S_p(x_i)$に基づいて少数クラスサンプル$x$を$S_{imin}$から選択する．その少数クラスサンプルが属するクラスターから自分以外のサンプルを選択し，SMOTEのように2点間でデータを生成する．なお，クラスターにデータが1つのみしかない場合は自分自身を複製する(ランダムオーバーサンプリング)．

どうでしょうか．原論文に合わせてステップをかなり細切れにして説明しているため，若干わかりにくいかも知れません．また，これまでに説明してきた手法と比べるとそもそも操作がかなり多いのも特徴です．ここからは動作を大まかに3段階に分割し，各段階での意図を含めて詳しく説明していきます．

ステップ1~6：$S_{imin}$の構築

MWMOTEの前半部分では$k$-nnを3回実施することで，最終的に少数クラスデータのうちより重要と考えられるサンプルによる集合$S_{imin}$を構築しています．この部分を理解するのに重要なのは著者らは少数クラスデータのうち，決定境界に近いサンプルが分類に重要である と考えている点です．すなわち，$S_{imin}$とは少数クラスデータのうち，決定境界に近いサンプルの集合であるということです．

さて，決定境界に近いサンプルというのはどの様に特定すればよいでしょうか．2次元ならばプロットして目視で特定できますが，高次元になると不可能です．決定境界に近いサンプルを用いた拡張データを生成するというMWMOTEと似たようなアプローチを取るBorderline-SMOTEでは，少数クラスデータの近傍点を探索し，そのうち多数クラスデータがいくつあるかということを基に特定します．このアプローチは妥当性があるように思います．周辺に多数クラスデータがある程度あるというのは，複数のクラスのデータが混在している状態であると考えられます．ではMWMOTEは何故このアプローチを採用しなかったのでしょうか．

答えはシンプルで，著者らは$k$-nnを1回実行するのみでは決定境界に近いサンプルを正しく特定できないと考えたためです．少数クラスデータを中心とした$k$-nnでは決定境界に近いサンプルでも近傍点が全て少数クラスデータになりえますし，$k$を大きくするとノイズデータの除去に悪影響を及ぼします．そこで，著者らは多数クラスデータから見た少数クラス近傍点こそが決定境界近くのサンプルであると考えたわけです．

ただし，どのようなデータでもいいわけではありません．例えば完全に多数クラスデータに囲まれている少数クラスデータは多数クラスデータから見た近傍点に選ばれる可能性が高いですが，実際にはこれはノイズデータである可能性があります．また，少数クラスデータから非常に離れた多数クラスデータから少数クラスデータ近傍点を探索したとしても，その多数クラスデータが分類に影響を及ぼす可能性は低いです．つまり，決定境界に近い多数クラスデータから見た，ノイズデータを除いた少数クラスデータ近傍点こそが決定境界に近い少数クラスデータである と著者らは主張しているわけです．

つまり，流れとしてはノイズデータの削除→決定境界に近い多数クラスデータの決定→決定境界に近い少数クラスデータの特定，と進みます．アルゴリズムのステップ1~6を眺めてもらえば確かにそのような流れになっています．まず多数クラスデータに囲まれている少数クラスデータをノイズデータとして削除し，残った少数クラスデータに近い多数クラスデータを決定境界に近い多数クラスデータとし，最後にそれらから近い少数クラスデータを決定境界に近い少数クラスデータであるとしています．

ステップ7~9：選択確率$S_p(x_i)$の計算

さて，前半部分で分類に重要であると考えられる決定境界に近い少数クラスデータを特定しました．しかし，筆者らはこれを用いて単純にオーバーサンプリングするのではなく，これらのデータの中でも重要度は異なるよね，と主張しています．その重要度は以下の3つの要素によって定められます．

1. 決定境界からの近さ(近いほうが重要で，遠いほうが重要ではない)
2. 少数クラスサンプルの属するクラスターの密度(疎のほうが重要で，密のほうが重要ではない)
3. 少数クラスサンプルに近い多数クラスデータ周辺の密度(密のほうが重要で，疎のほうが重要ではない)

1はこの手法の根幹を担う決定境界に近い少数クラスデータこそが重要であるという思想に沿っています．2に関しては，元々密なクラスターでは十分な情報量があると判断し，疎なクラスターに多くサンプルを生成することで情報量を補填しようという考えです．3に関しては，近くの多数クラスの密度が高いと決定境界が押されてしまう可能性があるため，それを防ごうという考えです．これらの考えに基づいて各少数クラスサンプルに重みを付けていきます．

さて，具体的な式の説明に移るわけですが，正直この部分は理解しなくても良いと思います．あくまで上の3つの要素に基づいて少数クラスサンプルに重みが割り当てられるということさえ理解していれば何の問題もありません．本記事の目的は手法解説なので，式自体は説明しますが，あくまで思想の実現手段として設定されていると思えば十分です．

この重みに関してですが，まず初めに決定境界に近い多数クラスデータ集合$S_{bmaj}$と決定境界に近い少数クラスデータ集合$S_{imin}$の各サンプルごとに計算されます．それぞれ$y_i, x_i$とすると，この2点を用いて重み$I_w (y_i, x_i)$を計算し，それを全ての$y_i$に対して足し合わせることで，少数クラスサンプル$x_i$に対する選択重み$S_w (x_i)$が計算されます．そのため，まず$I_w (y_i, x_i)$の計算方法について説明します．

$I_w (y_i, x_i)$は近接係数$C_f (y_i, x_i)$と密度係数$D_f (y_i, x_i)$を掛けることによって得られます．すなわち

$$I_w (y_i, x_i) = C_f (y_i, x_i) \times D_f (y_i, x_i)$$

です．近接係数は上記の要素の内1の決定境界からの近さを反映し，密度係数は2の少数クラスサンプルクラスターの密度を反映します．まず，近接係数$C_f (y_i, x_i)$は$y_i$と$x_i$の距離$dist(y_i, x_i)$と特徴量数$l$，ユーザーによって定義されるパラメータである$C_f(th)$と$CMAX$，カットオフ関数$f$を用いて以下のように表されます．

$$C_f (y_i, x_i) = \dfrac{f \left( \dfrac{l}{dist(y_i, x_i)} \right) }{C_f (th)} \times CMAX$$

ここでカットオフ関数$f(x)$は$x$が$C_f (th)$以下ならば$x$，それより大きい場合は$C_f(th)$を返します．つまり最大値を$C_f (th)$に制限しています．すなわち最終的に得られる近接係数$C_f (y_i, x_i)$は$[0, CMAX]$の範囲にあります．ただし注意があり，この値はもし$x_i$が$y_i$の$k_3$個の近傍点に含まれない場合，すなわち$x_i \notin N_{min} (y_i)$の場合は0に固定されます(これはステップ5で特定したものです)．全体としては$y_i$と$x_i$が近ければ近いほどこの値は大きくなります．

次に密度係数$D_f (y_i, x_i)$に関しては以下のように表されます．

$$D_f (y_i, x_i) = \dfrac{C_f (y_i, x_i)}{\sum_{q \in S_{imin}} C_f(y_i, q)}$$

これはどういうことかということを説明します．まず注意すべきことは，$y_i$と$x_i$が近傍点でない場合，この値は0になるということです．つまりこの2つの点が近い場合のみを考えればよいです．
分母の部分は多数クラスサンプルを$y_i$に固定したうえで各少数クラスサンプル$q$に対する近接係数$C_f (y_i, q)$を足し合わせています．もし$y_i$と$x_i$が近傍点で，さらに$x_i$が高密度のクラスターに属している場合，必然的に$x_i$周辺の少数クラスデータと$y_i$との近接係数の値は$x_i$による近接係数の値と近くなります．つまり密度係数の値は小さくなります．

それに対し，$x_i$が疎なクラスターに属している場合，$x_i$周辺の少数クラスデータと$y_i$との近接係数の値はばらつきます．つまり，$x_i$と$y_i$がより近い位置にある場合は密度係数の値は大きくなります．ただし，もし$x_i$が近傍点の中でも遠い場所に位置している場合は密度係数の値は(密なクラスターの場合と比べても)小さくなると考えられるので，この係数は純粋な密度を測っているというよりも，どれだけ近いかという要素がかなり作用している点には注意する必要があります．

こうして計算された$y_i$と$x_i$の間の重み$I_w (y_i, x_i)$に関して，これを決定境界に近い多数クラスデータ集合$S_{bmaj}$に属する全てのサンプル$y_i$に対して足し合わせ，最終的に$x_i$の選択重み$S_w (x_i)$を得ます．この足し合わせる動作に関して，近くの多数クラスデータが密であればあるほど各情報重みは大きくなります(というより0である確率が下がります)．すなわち単純な足し合わせによって，上記の要素3の近くの多数クラスデータの密度の要素が考慮されているわけです．

この様に各サンプルに対する選択重み$S_w (x_i)$を計算した後，その値を正規化することによって選択確率$S_p (x_i)$にします．この名前のとおり，これは拡張データの生成時に$x_i$が選ばれる確率を表しており，高ければ高いほど周辺にデータが生成されやすくなるということになります．これまで説明したように多数クラス近傍点に近ければ近いほど近接係数も密度係数も大きくなり，結果として情報重みも大きくなることから，より多数クラスデータに近い少数クラスサンプルはより選択されやすくなるということになります．

ステップ11~12：拡張データの生成

選択確率をもとめたのでいよいよ拡張データを生成するわけですが，単純に選択して近くのサンプルとの間に生成するわけではありません．一番初めに少数クラスデータ全体(フィルタリング前)をクラスタリングします．ここでのクラスタリングにはaverage-linkage agglomerative clusteringというクラスタリング手法を使うようです．このクラスタリング手法はMWMOTEの本質とは関係がないため詳しい説明は省きますが，近くの距離にあるサンプルをどんどん結合していくようなクラスタリングだそうです．

クラスタリングが終わった後，先程計算した選択確率に基づいて$S_{imin}$の中から少数クラスサンプルを1つ選びます．これを$x$とし，$x$と同じクラスターに属する少数クラスデータから1つをランダムに選びます．いつものSMOTEだとここで$k$-nnを使いますが，本手法ではクラスター内であればどれでも良いです．そして2点間の内分点を拡張データとして生成します．

もしクラスターに属しているデータが1つのみの場合はそのデータの複製が行われます．この事によって多数クラスデータ領域への侵害を防いでいます．

Pythonによる使用例

以下にDBSMOTEを用いたPythonコードを示します．なお，このコードはGeminiを用いて生成したものです．同じクラスターベースの手法であるK-means SMOTEと並列に並べています．

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import f1_score
from imblearn.over_sampling import SMOTE, KMeansSMOTE
import smote_variants

# 合計3つのクラスタを生成
centers = [[0, 0], [3, 3], [-3, 3]]
n_samples = [2970, 15, 15]
cluster_std = [1.2, 0.4, 0.4]

X, y_temp = make_blobs(n_samples=n_samples, centers=centers, cluster_std=cluster_std, random_state=42)

# ラベルの再割り当て
y = np.where(y_temp == 0, 0, 1)

# 訓練データとテストデータに分割
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
print(len(X_train), len(X_test))

# SMOTEの適用
smote = SMOTE(random_state=42, k_neighbors=20)
X_train_smote, y_train_smote = smote.fit_resample(X_train, y_train)
print(len(X_train_smote))

# KMeans SMOTEの適用
kmeans_smote = KMeansSMOTE(random_state=42, k_neighbors=2, cluster_balance_threshold=0.01)
X_train_kmeans, y_train_kmeans = kmeans_smote.fit_resample(X_train, y_train)
print(len(X_train_kmeans))

# MWMOTEの適用
mwmote = smote_variants.MWMOTE(random_state=42)
X_train_mwmote, y_train_mwmote = mwmote.sample(X_train, y_train)
print(len(X_train_mwmote))

# プロット領域の作成
# グラフを4つ並べるため幅を変更
plt.figure(figsize=(24, 6))
FONT_SIZE = 25

# オーバーサンプリング前のプロット
plt.subplot(1, 4, 1)
plt.scatter(X_train[y_train == 0][:, 0], X_train[y_train == 0][:, 1], label='Majority', alpha=0.5)
plt.scatter(X_train[y_train == 1][:, 0], X_train[y_train == 1][:, 1], label='Minority', alpha=0.7)
plt.title('Before Oversampling', fontsize=FONT_SIZE)
plt.legend()

# SMOTE適用後のプロット
plt.subplot(1, 4, 2)
plt.scatter(X_train_smote[y_train_smote == 0][:, 0], X_train_smote[y_train_smote == 0][:, 1], label='Majority', alpha=0.5)
plt.scatter(X_train_smote[y_train_smote == 1][:, 0], X_train_smote[y_train_smote == 1][:, 1], label='Minority', alpha=0.7)
plt.title('After SMOTE', fontsize=FONT_SIZE)
plt.legend()

# KMeans SMOTE適用後のプロット
plt.subplot(1, 4, 3)
plt.scatter(X_train_kmeans[y_train_kmeans == 0][:, 0], X_train_kmeans[y_train_kmeans == 0][:, 1], label='Majority', alpha=0.5)
plt.scatter(X_train_kmeans[y_train_kmeans == 1][:, 0], X_train_kmeans[y_train_kmeans == 1][:, 1], label='Minority', alpha=0.7)
plt.title('After KMeans-SMOTE', fontsize=FONT_SIZE)
plt.legend()

# MWMOTE適用後のプロット
plt.subplot(1, 4, 4)
plt.scatter(X_train_mwmote[y_train_mwmote == 0][:, 0], X_train_mwmote[y_train_mwmote == 0][:, 1], label='Majority', alpha=0.5)
plt.scatter(X_train_mwmote[y_train_mwmote == 1][:, 0], X_train_mwmote[y_train_mwmote == 1][:, 1], label='Minority', alpha=0.7)
plt.title('After MWMOTE', fontsize=FONT_SIZE)
plt.legend()
plt.tight_layout()

# 画像の保存
plt.savefig('oversampling_comparison.png')

# 適用前の決定木モデルの学習と評価
clf_original = DecisionTreeClassifier(random_state=42)
clf_original.fit(X_train, y_train)
y_pred_original = clf_original.predict(X_test)
f1_original = f1_score(y_test, y_pred_original)

# SMOTE適用後の決定木モデルの学習と評価
clf_smote = DecisionTreeClassifier(random_state=42)
clf_smote.fit(X_train_smote, y_train_smote)
y_pred_smote = clf_smote.predict(X_test)
f1_smote = f1_score(y_test, y_pred_smote)

# KMeans SMOTE適用後の決定木モデルの学習と評価
clf_kmeans = DecisionTreeClassifier(random_state=42)
clf_kmeans.fit(X_train_kmeans, y_train_kmeans)
y_pred_kmeans = clf_kmeans.predict(X_test)
f1_kmeans = f1_score(y_test, y_pred_kmeans)

# MWMOTE適用後の決定木モデルの学習と評価
clf_mwmote = DecisionTreeClassifier(random_state=42)
clf_mwmote.fit(X_train_mwmote, y_train_mwmote)
y_pred_mwmote = clf_mwmote.predict(X_test)
f1_mwmote = f1_score(y_test, y_pred_mwmote)

# 結果の出力
print(f"Original F1: {f1_original:.4f}")
print(f"SMOTE F1:    {f1_smote:.4f}")
print(f"KMeans-SMOTE F1: {f1_kmeans:.4f}")
print(f"MWMOTE F1:   {f1_mwmote:.4f}")

以下が実行結果の図になります．

各手法によるデータ分布の比較．左から元データ，SMOTE拡張後データ，K-means SMOTE後データ，MWMOTE後データ
図を見ると同じクラスターベースでもだいぶ違う位置にデータが生成されています．これはおそらくMWMOTEでのクラスタリングがK-means SMOTEによるクラスタリングと比べて非常に細かくなっていることが理由であると考えられます．なお，F1-Scoreの比較は

Original F1: 0.5455
SMOTE F1:    0.3200
KMeans-SMOTE F1: 0.6667
MWMOTE F1:   0.6667

となっています．

引用

Barua, Sukarna, et al. "MWMOTE--majority weighted minority oversampling technique for imbalanced data set learning." IEEE Transactions on knowledge and data engineering 26.2 (2012): 405-425.