06 - Unbalanced Datasets

by Alejandro Correa Bahnsen & Iván Torroledo

version 1.3, June 2018

Part of the class Applied Deep Learning

This notebook is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Special thanks goes to Kevin Markham

Background

Unbalanced classification problems cause problems to many learning algorithms. These problems are characterized by the uneven proportion of cases that are available for each class of the problem.

Most classification algorithms will only perform optimally when the number of samples of each class is roughly the same. Highly skewed datasets, where the minority heavily outnumbered by one or more classes, haven proven to be a challenge while at the same time becoming more and more common.

One way of addresing this issue is by resampling the dataset as to offset this imbalance with the hope of arriving and a more robust and fair decision boundary than you would otherwise.

Resampling techniques are divided in two categories:

  • Under-sampling the majority class(es)
  • Over-sampling the minority class
In [1]:
%matplotlib inline

import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_classification
from sklearn.decomposition import PCA
plt.style.use('ggplot')
In [2]:
# Generate some data
X, y = make_classification(n_classes=2, class_sep=2, weights=[0.9, 0.1],
                           n_informative=3, n_redundant=1, flip_y=0,
                           n_features=20, n_clusters_per_class=1,
                           n_samples=1000, random_state=10)

# Instanciate a PCA object for the sake of easy visualisation
pca = PCA(n_components = 2)

# Fit and transform x to visualise inside a 2D feature space
x_vis = pca.fit_transform(X)

# Plot the original data

def plot_two_classes(X, y, subplot=False, size=(10, 10)):
    # Plot the two classes
    if subplot == False:
        fig, subplot = plt.subplots(nrows=1, ncols=1, figsize=size)
        
    subplot.scatter(X[y==0, 0], X[y==0, 1], label="Class #0", 
                    alpha=0.5, s=70)
    subplot.scatter(X[y==1, 0], X[y==1, 1], label="Class #1", 
                    alpha=0.5, s=70)
    subplot.legend()
    return subplot

plot_two_classes(x_vis, y)
Out[2]:
<matplotlib.axes._subplots.AxesSubplot at 0x7f5443d54da0>
In [3]:
y.mean()
Out[3]:
0.1

Part 1: Under-sampling

Random - Under-sampling

Randomly select a percentage of the negative class such that the resulting dataset is balanced

In [4]:
n_samples = y.shape[0]
print(n_samples)
1000
In [5]:
n_samples_0 = (y == 0).sum()
n_samples_0
Out[5]:
900
In [6]:
n_samples_1 = (y == 1).sum()
n_samples_1
Out[6]:
100
In [7]:
n_samples_1 / n_samples
Out[7]:
0.1

How many negatives cases should I select if I want a new dataset with 50% of positives?

0.5 = n_samples_1 / (n_samples_1 + n_samples_0_new)

(n_samples_1 + n_samples_0_new) = n_samples_1 / 0.5

In [8]:
n_samples_0_new =  n_samples_1 / 0.5 - n_samples_1
n_samples_0_new
Out[8]:
100.0
In [9]:
n_samples_0_new_per = n_samples_0_new / n_samples_0
n_samples_0_new_per
Out[9]:
0.1111111111111111

Create a filter to select n_samples_0_new_per from the negative class

In [10]:
# Select all negatives
filter_ = y == 0

# Random sample
np.random.seed(42)
rand_1 = np.random.binomial(n=1, p=n_samples_0_new_per, size=n_samples)

# Combine
filter_ = filter_ & rand_1
In [11]:
filter_.sum()
Out[11]:
108

Also select all the positives

In [12]:
filter_ = filter_ | (y == 1)
In [13]:
filter_ = filter_.astype(bool)

plot

In [14]:
plot_two_classes(x_vis[filter_], y[filter_])
Out[14]:
<matplotlib.axes._subplots.AxesSubplot at 0x15efa139048>

Convert into a function

In [15]:
def UnderSampling(X, y, target_percentage=0.5, seed=None):
    # Assuming minority class is the positive
    n_samples = y.shape[0]
    n_samples_0 = (y == 0).sum()
    n_samples_1 = (y == 1).sum()

    n_samples_0_new =  n_samples_1 / target_percentage - n_samples_1
    n_samples_0_new_per = n_samples_0_new / n_samples_0

    filter_ = y == 0

    np.random.seed(seed)
    rand_1 = np.random.binomial(n=1, p=n_samples_0_new_per, size=n_samples)
    
    filter_ = filter_ & rand_1
    filter_ = filter_ | (y == 1)
    filter_ = filter_.astype(bool)
    
    return X[filter_], y[filter_]
In [16]:
for target_percentage in [0.1, 0.2, 0.3, 0.4, 0.5]:
    X_u, y_u = UnderSampling(x_vis, y, target_percentage, 1)
    print('Target percentage', target_percentage)
    print('y.shape = ',y_u.shape[0], 'y.mean() = ', y_u.mean())
    plot_two_classes(X_u, y_u, size=(5, 5))
    plt.show()    
Target percentage 0.1
y.shape =  1000 y.mean() =  0.1
Target percentage 0.2
y.shape =  510 y.mean() =  0.196078431373
Target percentage 0.3
y.shape =  343 y.mean() =  0.291545189504
Target percentage 0.4
y.shape =  249 y.mean() =  0.401606425703
Target percentage 0.5
y.shape =  199 y.mean() =  0.502512562814

Comparing Under-Sampling with other models

Advantages of Under-Sampling:

  • Fast to estimate
  • Easy to understand

Disadvantages of Under-Sampling:

  • Information of the negative class is lost
  • Variance due to randomnes
  • Need to define the target percentage

Identify and remove majority samples that form a Tomek link with minority samples.

Find the nearest neighbour of every point

In [17]:
from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(n_neighbors=2)
nn.fit(x_vis)
nns = nn.kneighbors(x_vis, return_distance=False)[:, 1]
In [18]:
nns[0:10]
Out[18]:
array([209, 633, 161, 610, 800, 268, 827, 606, 211, 940], dtype=int64)

Find if tomek. Use the target vector and the first neighbour of every sample point and looks for Tomek pairs. Returning a boolean vector with True for majority Tomek links.

In [19]:
# Initialize the boolean result as false, and also a counter
links = np.zeros(len(y), dtype=bool)

# Loop through each sample of the majority class then we
# look at its first neighbour. If its closest neighbour also has the
# current sample as its closest neighbour, the two form a Tomek link.
for ind, ele in enumerate(y):

    if ele == 1 | links[ind] == True:  # Keep all from the minority class
        continue

    if y[nns[ind]] == 1:

        # If they form a tomek link, put a True marker on this
        # sample, and increase counter by one.
        if nns[nns[ind]] == ind:
            links[ind] = True
In [20]:
links.sum()
Out[20]:
3
In [21]:
filter_ = np.logical_not(links)
In [22]:
print('y.shape = ',y[filter_].shape[0], 'y.mean() = ', y[filter_].mean())
plot_two_classes(x_vis[filter_], y[filter_])
y.shape =  997 y.mean() =  0.100300902708
Out[22]:
<matplotlib.axes._subplots.AxesSubplot at 0x15efd2fc2b0>

Advantages of TomekLinks:

  • Creates a linearly-separable space

Disadvantages of TomekLinks:

  • Still a highly imbalance dataset

Condensed Nearest Neighbour

The goal is to eliminate examples from the majority class that are much further away from the border

In [23]:
# Import the K-NN classifier
from sklearn.neighbors import KNeighborsClassifier
In [24]:
# Number of samples to extract in order to build the set S.
n_seeds_S = 51

# Size of the neighbourhood to consider to compute the
# average distance to the minority point samples.
size_ngh = 100

# Randomly get one sample from the majority class
np.random.seed(42)
maj_sample = np.random.choice(x_vis[y == 0].shape[0], n_seeds_S)
maj_sample = x_vis[y == 0][maj_sample]
In [25]:
# Create the set C
# Select all positive and the randomly selected negatives
C_x = np.append(x_vis[y == 1], maj_sample, axis=0)
C_y = np.append(y[y == 1], [0] * n_seeds_S)
In [26]:
# Create the set S
S_x = x_vis[y == 0]
S_y = y[y == 0]
In [27]:
knn = KNeighborsClassifier(n_neighbors=size_ngh)

# Fit C into the knn
knn.fit(C_x, C_y)

# Classify on S
pred_S_y = knn.predict(S_x)
In [28]:
# Find the misclassified S_y
idx_tmp = np.nonzero(y == 0)[0][np.nonzero(pred_S_y != S_y)]
In [29]:
filter_ = np.nonzero(y == 1)[0]
filter_ = np.concatenate((filter_, idx_tmp), axis=0)
In [30]:
print('y.shape = ',y[filter_].shape[0], 'y.mean() = ', y[filter_].mean())
plot_two_classes(x_vis[filter_], y[filter_])
y.shape =  175 y.mean() =  0.571428571429
Out[30]:
<matplotlib.axes._subplots.AxesSubplot at 0x15efd32b358>
In [31]:
# Import the K-NN classifier
from sklearn.neighbors import KNeighborsClassifier
def CondensedNearestNeighbor(X, y, n_seeds_S=1, size_ngh=1, seed=None):
    # Randomly get one sample from the majority class
    np.random.seed(seed)
    maj_sample = np.random.choice(X[y == 0].shape[0], n_seeds_S)
    maj_sample = X[y == 0][maj_sample]
    # Create the set C
    # Select all positive and the randomly selected negatives
    C_x = np.append(X[y == 1], maj_sample, axis=0)
    C_y = np.append(y[y == 1], [0] * n_seeds_S)
    # Create the set S
    S_x = X[y == 0]
    S_y = y[y == 0]
    knn = KNeighborsClassifier(n_neighbors=size_ngh)

    # Fit C into the knn
    knn.fit(C_x, C_y)

    # Classify on S
    pred_S_y = knn.predict(S_x)
    # Find the misclassified S_y
    idx_tmp = np.nonzero(y == 0)[0][np.nonzero(pred_S_y != S_y)]

    filter_ = np.nonzero(y == 1)[0]
    filter_ = np.concatenate((filter_, idx_tmp), axis=0)

    return X[filter_], y[filter_]
In [32]:
for n_seeds_S, size_ngh in [(1, 1), (100, 100), (50, 50), (100, 50), (50, 100)]:
    X_u, y_u = CondensedNearestNeighbor(x_vis, y, n_seeds_S, size_ngh, 1)
    print('n_seeds_S ', n_seeds_S, 'size_ngh ', size_ngh)
    print('y.shape = ',y_u.shape[0], 'y.mean() = ', y_u.mean())
    plot_two_classes(X_u, y_u, size=(5, 5))
    plt.show()    
n_seeds_S  1 size_ngh  1
y.shape =  386 y.mean() =  0.25906735751295334
n_seeds_S  100 size_ngh  100
y.shape =  100 y.mean() =  1.0
n_seeds_S  50 size_ngh  50
y.shape =  112 y.mean() =  0.8928571428571429
n_seeds_S  100 size_ngh  50
y.shape =  102 y.mean() =  0.9803921568627451
n_seeds_S  50 size_ngh  100
y.shape =  246 y.mean() =  0.4065040650406504

Comparing CondensedNearestNeighbor with other models

Advantages of CondensedNearestNeighbor:

  • Create Condensed space

Disadvantages of CondensedNearestNeighbor:

  • Variance due to randomnes
  • Need to define the two parameters

Other Under-sampling methods

  • Under-sampling with Cluster Centroids
  • NearMiss-(1 & 2 & 3)
  • One-Sided Selection
  • Neighboorhood Cleaning Rule

Part 2: Over-Sampling

Random over-sampling

Replicate the minority class examples to increase their relevance

In [31]:
import random
def OverSampling(X, y, target_percentage=0.5, seed=None):
    # Assuming minority class is the positive
    n_samples = y.shape[0]
    n_samples_0 = (y == 0).sum()
    n_samples_1 = (y == 1).sum()

    n_samples_1_new =  -target_percentage * n_samples_0 / (target_percentage- 1)

    np.random.seed(seed)
    filter_ = np.random.choice(X[y == 1].shape[0], int(n_samples_1_new))
    # filter_ is within the positives, change to be of all
    filter_ = np.nonzero(y == 1)[0][filter_]
    
    filter_ = np.concatenate((filter_, np.nonzero(y == 0)[0]), axis=0)
    
    return X[filter_], y[filter_]
In [32]:
for target_percentage in [0.1, 0.2, 0.3, 0.4, 0.5]:
    X_u, y_u = OverSampling(x_vis, y, target_percentage, 1)
    print('Target percentage', target_percentage)
    print('y.shape = ',y_u.shape[0], 'y.mean() = ', y_u.mean())
    plot_two_classes(X_u, y_u, size=(5, 5))
    plt.show()    
Target percentage 0.1
y.shape =  1000 y.mean() =  0.1
Target percentage 0.2
y.shape =  1125 y.mean() =  0.2
Target percentage 0.3
y.shape =  1285 y.mean() =  0.299610894942
Target percentage 0.4
y.shape =  1500 y.mean() =  0.4
Target percentage 0.5
y.shape =  1800 y.mean() =  0.5

Comparing Over-Sampling with other models

Advantages of Over-Sampling :

  • Fast to estimate
  • Easy to understant
  • No information of the majority class is lost

Disadvantages of Over-Sampling :

  • No new information is added
  • Hurts the generalization capacity
  • Variance due to randomnes
  • Need to define the target percentage

SMOTE

SMOTE (Chawla et. al. 2002) is a well-known algorithm to fight this problem. The general idea of this method is to artificially generate new examples of the minority class using the nearest neighbors of these cases. Furthermore, the majority class examples are also under-sampled, leading to a more balanced dataset.

In [33]:
# Number of nearest neighbours to used to construct synthetic samples.
k = 5

from sklearn.neighbors import NearestNeighbors
nearest_neighbour_ = NearestNeighbors(n_neighbors=k + 1)
In [34]:
# Look for k-th nearest neighbours, excluding, of course, the
# point itself.#
nearest_neighbour_.fit(x_vis[y==1])
Out[34]:
NearestNeighbors(algorithm='auto', leaf_size=30, metric='minkowski',
         metric_params=None, n_jobs=1, n_neighbors=6, p=2, radius=1.0)
In [35]:
# Matrix with k-th nearest neighbours indexes for each minority
# element.#
nns = nearest_neighbour_.kneighbors(x_vis[y==1], 
                                    return_distance=False)[:, 1:]

Example of the nns of two cases

In [36]:
def base_smote_plot(sel, nns):
    fig, subplot = plt.subplots(nrows=1, ncols=1, figsize=(10, 10))
    
    for i in range(len(sel)):
        # plot the select sample
        subplot.scatter(x_vis[y==1, 0][sel[i]], x_vis[y==1, 1][sel[i]],
                alpha=1., s=70)
        # plot the neighbors
        subplot.scatter(x_vis[y==1, 0][nns[sel[i]]], 
                        x_vis[y==1, 1][nns[sel[i]]],
                        alpha=0.5, s=70) 
        
        # plot the lines
        for nn in nns[sel[i]]:
            plt.plot([x_vis[y==1, 0][sel[i]], x_vis[y==1, 0][nn]],  
                     [x_vis[y==1, 1][sel[i]], x_vis[y==1, 1][nn]],
                     'r--') 
    
    xlim = subplot.get_xlim()
    ylim = subplot.get_ylim()
    subplot.scatter(x_vis[y==1, 0], x_vis[y==1, 1], alpha=0.1, s=70)
    subplot.set_xlim(xlim)
    subplot.set_ylim(ylim)
    return subplot
base_smote_plot([12],nns)
Out[36]:
<matplotlib.axes._subplots.AxesSubplot at 0x15efd4092b0>
In [37]:
# Create syntetic sample for 12

# Select one random neighbor
np.random.seed(3)
nn_ = np.random.choice(nns[12])

x_vis[y==1][nn_]
Out[37]:
array([ 4.06447682,  0.27624239])
In [38]:
# Take a step of random size (0,1) in the direction of the
# n nearest neighbours
np.random.seed(5)
step = np.random.uniform()

# Construct synthetic sample
new = x_vis[y==1][12] - step * (x_vis[y==1][12] - x_vis[y==1][nn_])
new
Out[38]:
array([ 3.99919087,  0.14561291])
In [39]:
plot_ = base_smote_plot([12],nns)
plot_.scatter(new[0], new[1], alpha=1., s=400, marker="*")
Out[39]:
<matplotlib.collections.PathCollection at 0x15efd7cfa58>
In [42]:
# Select one random neighbor
np.random.seed(5)
nn_2 = np.random.choice(nns[12])
np.random.seed(1)
step = np.random.uniform()
# Construct synthetic sample
new2 = x_vis[y==1][12] - step * (x_vis[y==1][12] - x_vis[y==1][nn_2])

plot_ = base_smote_plot([12],nns)
plot_.scatter(new[0], new[1], alpha=1., s=400, marker="*")
plot_.scatter(new2[0], new2[1], alpha=1., s=400, marker="*")
Out[42]:
<matplotlib.collections.PathCollection at 0x7fd7eed5d908>

Apply to all cases

Estimate number of synthetic cases to create

In [40]:
target_percentage = 0.5
n_samples_1_new =  -target_percentage * n_samples_0 / (target_percentage- 1) - n_samples_1
n_samples_1_new = int(n_samples_1_new)
n_samples_1_new
Out[40]:
800
In [41]:
# A matrix to store the synthetic samples
new = np.zeros((n_samples_1_new, x_vis.shape[1]))
In [42]:
# Select examples to use as base
np.random.seed(34)
sel_ = np.random.choice(y[y==1].shape[0], n_samples_1_new)
In [43]:
# Define random seeds (2 per example)
np.random.seed(64)
nn__ = np.random.choice(k, n_samples_1_new)
np.random.seed(65)
steps = np.random.uniform(size=n_samples_1_new)
In [44]:
# For each selected examples create one synthetic case
for i, sel in enumerate(sel_):
    # Select neighbor
    nn_ = nn__[i]
    step = steps[i]
    new[i, :] = x_vis[y==1][sel] - step * (x_vis[y==1][sel] - x_vis[y==1][nn_])
In [48]:
new
Out[48]:
array([[4.99956657, 0.45629856],
       [4.9262738 , 0.41983964],
       [4.64508466, 0.25702488],
       ...,
       [5.58945487, 0.51102965],
       [5.47529954, 0.39266754],
       [5.09802765, 0.36978454]])
In [49]:
plot_ = plot_two_classes(x_vis, y, size=(10, 10))
plot_.scatter(new[:, 0], new[:, 1], alpha=0.5, s=150, marker='*')
Out[49]:
<matplotlib.collections.PathCollection at 0x7fd7ece825c0>