🐙

表形式データ拡張手法 part13：AHC

に公開
機械学習
表形式データ拡張
データ不均衡
tech

基本情報

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

SMOTEは強力ではあるものの，様々な欠点があり，それを解決するために設計された様々な変種が存在します．その中でも一大勢力がクラスターベースの手法で，これまでに説明してきた手法でもK-means SMOTEやDBSMOTE, MWMOTEがクラスターベースに当たります．クラスターベースの手法の良い点はクラスター内でデータを生成することで，多数クラスデータ領域への侵害を防げる点です．

ただし，SMOTE系以外にもクラスターベースの拡張手法は存在します．本記事で紹介するAgglomerative Hierarchical Clustering (AHC) はクラスターベースの拡張手法として初めて登場した手法であり，SMOTE系ではない拡張手法です．名前のとおり，Agglomerative Hierarchical Clusteringというクラスタリング手法を用いた拡張手法です．なお，両者を区別するため，以降はAHC拡張手法およびAHCクラスタリングと呼称します．まずAHCクラスタリングについて説明した後にAHC拡張手法を説明します．

予備知識

AHC拡張手法自体は非常に単純な手法です．ただ，完全に理解するためにはAHCクラスタリングについて知っておく必要があるため，本章ではAHCクラスタリングについて説明します．なお，筆者もAHCクラスタリングについてほとんど知らなかったため，こちらのサイトを基に説明を行います．

AHCクラスタリングは各データがバラバラのクラスターとして独立している状態から，距離が近いクラスター同士を結合していくクラスタリング手法です．この「距離の近さ」をどの様に計算するかによってAHCはいくつかの種類に分離されます．数式を示すにあたって，u, vをそれぞれ別のクラスター，u[i]をクラスターuに属するi番目のデータ(i = 0, 1, \dots n-1)とします．ここでクラスター間の距離をd(u, v)，それぞれのクラスター内のデータ間の距離をdist(u[i], v[j])のように表記します．距離の計算法の1つであるsingle-link methodではクラスター間の距離d(u, v)は

d(u, v) = min(dist(u[i], v[j]))

のように表されます．すなわち2つのクラスターに属するデータ間の距離の最小値をクラスター間の距離とします．気持ちとしてはどれかのデータ同士が近ければクラスターも近いよね，という感じです．これに対し，別の計算法であるcomplete-link methodでは

d(u, v) = max(dist(u[i], v[j]))

のように計算されます．これはsingle-link methodの逆で，各クラスター間に属するデータ間の距離の最大値をクラスター間の距離としています．気持ちとしては最も遠いデータ間が遠すぎたら同じクラスターとみなさないほうが良いよね，という感じです．他にも各クラスターの重心間距離を使うcentroidなどがあります．

このような計算法のうち1つを選択し，距離が最も近いクラスター同士をどんどん結合していきます．なお，特に距離に対しての基準や，最小クラスター数を設定しない限りは必ず最終的にすべてのデータが同一のクラスターに割り当てられます．ただし，どの様にクラスターが形成されていったかの記録(樹形図)を保存しておけば，事後的に基準を設定すること(すなわちどこでクラスタリングを打ち切るか)でそれぞれの基準ごとに別のクラスターが得られます．すなわち，1度のクラスタリングで複数の結果を得ることが可能です．

AHC拡張手法のアルゴリズム紹介

AHC拡張手法のアルゴリズムは比較的単純です．以下にアルゴリズムの流れを示します．

  1. AHCクラスタリングの実行
    少数クラスデータに対してsingle-linkとcomplete-linkの2つの方法を用いてAHCクラスタリングを実行します．すなわち，最終的に得られるクラスタリングの記録(樹形図)は2種類になり，更に計算基準が異なるため，全く別の結果が得られると考えられます．

  2. 合成データの生成
    クラスタリング後，得られた記録(樹形図)の全てのレベル，すなわち実行途中で生成された全てのクラスター組み合わせに対し，クラスターの重心を計算し，それを拡張データとします．

Pythonによる使用例

以下にAHCを実装した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))

# AHCの適用
ahc = smote_variants.AHC(random_state=42)
X_train_ahc, y_train_ahc = ahc.sample(X_train, y_train)
print(len(X_train_ahc))

# プロット領域の作成
# グラフを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()

# AHC適用後のプロット
plt.subplot(1, 4, 4)
plt.scatter(X_train_ahc[y_train_ahc == 0][:, 0], X_train_ahc[y_train_ahc == 0][:, 1], label='Majority', alpha=0.5)
plt.scatter(X_train_ahc[y_train_ahc == 1][:, 0], X_train_ahc[y_train_ahc == 1][:, 1], label='Minority', alpha=0.7)
plt.title('After AHC', 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)

# AHC適用後の決定木モデルの学習と評価
clf_ahc = DecisionTreeClassifier(random_state=42)
clf_ahc.fit(X_train_ahc, y_train_ahc)
y_pred_ahc = clf_ahc.predict(X_test)
f1_ahc = f1_score(y_test, y_pred_ahc)

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

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

各手法によるデータ分布の比較．左から元データ，SMOTE拡張後データ，K-means SMOTE後データ，AHC後データ

図を見るとAHCは他に比べて生成データの多様性が薄いように見えます．実際に生成データも少ないです(重なっていて少なく見えるわけではなく)．訓練データに含まれる少数クラスデータの数が26個に対し，生成数が25個しかありません．勘のいい人はこの時点でsmote-variantsの実装が誤っていることに気づくと思います．何故なら原論文でのAHCではsingle-linkとcomplete-linkの2種類のクラスタリングを行ってデータを生成しているので，必ず生成数は2の倍数になるはずです．しかし，smote-variantsでは1種類しかクラスタリングを行っておらず，さらにその計算方法はward-linkという別の方法です．

なお，AHCクラスタリングにおいてクラスター同士が結合する動作を行うたびに全体のクラスター数は1つ減ります．最初のクラスター数(すなわちデータ数)をNとした時，クラスター同士の結合はN-1回行われるため，生成データはN-1個になります(1種類のみの場合)．実際，上の例では訓練データ26個に対し，生成数は25個になっています．

他にAHCの性質として，最後には必ず全てのデータが属する単一のクラスターができるというものがあります．実際に，生成結果の図を見ると2つのクラスター間のちょうど真ん中当たりに1つだけデータが生成されているのが見て取れます．これは多数クラスデータ領域への侵害を引き起こすので，その点には注意する必要があります．

なお，F1-Scoreの比較は以下のようになっています．

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

データの生成数が少なかったAHCですが，性能自体は向上させています．実際，データ拡張においてもどの程度のデータ数を生成すべきかは完全にはわかっておらず，基本的に多数クラスと少数クラスが均衡状態になったときが良くなることが多い(悪くなりにくい)とされているので，その様に生成する場合が多いです．最適性を求めるのであれば実際には生成数はその都度調整してもよいのかもしれません．

引用

Cohen, Gilles, et al. "Learning from imbalanced data in surveillance of nosocomial infection." Artificial intelligence in medicine 37.1 (2006): 7-18.

Discussion