CondensedNearestNeighbour()处理百万级数据无结果的原因及非随机欠采样替代方案咨询

Let me break down your problem and give you practical, actionable solutions here.

First: Why CondensedNearestNeighbour (CNN) is Crawling on Your Dataset #

CNN works by iteratively building a "condensed" dataset: it starts with one sample, then checks every other sample to see if it’s misclassified by the current condensed set. If yes, it adds that sample to the set. This process has O(n²) time complexity in the worst case—for 1 million samples, that’s 1e12 operations. Even with single-variable distance calculations (which are fast), this is computationally prohibitive for large datasets.

CNN’s Actual Use Case #

CNN shines on small to medium-sized datasets (think tens of thousands of samples, not millions). It’s designed when you need to retain as much critical decision boundary information as possible, and you’re willing to trade computation time for a precise, boundary-focused condensed dataset. For large-scale data, it’s just not feasible.

Recommended Non-Random Undersampling Methods for Large Datasets #

Here are faster, scalable alternatives that avoid random sampling:

1. Tomek Links #

Tomek Links are pairs of samples from different classes where each is the nearest neighbor of the other. Removing these pairs eliminates overlapping, ambiguous samples—great for cleaning up class boundaries without excessive computation. For single-variable data, this is extremely fast:

• Sort your data by the single variable
• Linear scan to find adjacent samples of different classes that are each other’s nearest neighbors (trivial in 1D)

Code Example:

from imblearn.under_sampling import TomekLinks
from collections import Counter

X = df1[['var1']].to_numpy()
y = df1['target'].to_numpy()

print(f"Original class distribution: {Counter(y)}")

undersample = TomekLinks()
X_resampled, y_resampled = undersample.fit_resample(X, y)

print(f"Resampled class distribution: {Counter(y_resampled)}")

2. Edited Nearest Neighbours (ENN) with Efficient Neighbor Search #

ENN removes samples that are misclassified by their k nearest neighbors. By default, it uses brute-force search, but you can switch to a KD-Tree (optimized for low-dimensional data like your single variable) to drastically speed things up.

Code Example:

from imblearn.under_sampling import EditedNearestNeighbours
from sklearn.neighbors import NearestNeighbors

X = df1[['var1']].to_numpy()
y = df1['target'].to_numpy()

# Use KD-Tree for fast nearest neighbor search in 1D
nn = NearestNeighbors(algorithm='kd_tree', n_neighbors=3)
undersample = EditedNearestNeighbours(neighbors=nn)

X_resampled, y_resampled = undersample.fit_resample(X, y)
print(f"Resampled class distribution: {Counter(y_resampled)}")

3. Clustering-Based Undersampling (MiniBatchKMeans) #

For large majority classes, cluster the samples first, then select representative samples from each cluster (e.g., cluster centers). This retains the overall distribution of the majority class while reducing sample size, and uses MiniBatchKMeans which is optimized for large datasets.

Code Example:

from sklearn.cluster import MiniBatchKMeans
import numpy as np
from collections import Counter

X = df1[['var1']].to_numpy()
y = df1['target'].to_numpy()

# Split majority and minority classes
majority_class = max(Counter(y), key=Counter(y).get)
minority_class = min(Counter(y), key=Counter(y).get)

X_majority = X[y == majority_class]
X_minority = X[y == minority_class]
y_minority = y[y == minority_class]

# Cluster majority class (adjust n_clusters to target sample size)
target_size = len(X_minority)  # Match minority size, or set your own
kmeans = MiniBatchKMeans(n_clusters=target_size, random_state=44, batch_size=1000)
kmeans.fit(X_majority)

# Get cluster centers as resampled majority samples
X_majority_resampled = kmeans.cluster_centers_
y_majority_resampled = np.array([majority_class] * target_size)

# Combine minority and resampled majority
X_resampled = np.vstack([X_majority_resampled, X_minority])
y_resampled = np.hstack([y_majority_resampled, y_minority])

print(f"Resampled class distribution: {Counter(y_resampled)}")

4. NearMiss #

NearMiss selects samples from the majority class that are closest to the minority class (three variants exist). It’s more efficient than CNN because it doesn’t use iterative building—instead, it selects based on distance thresholds, and can use fast nearest neighbor searches like KD-Tree.

Code Example:

from imblearn.under_sampling import NearMiss
from sklearn.neighbors import NearestNeighbors

X = df1[['var1']].to_numpy()
y = df1['target'].to_numpy()

# Use KD-Tree for speed
nn = NearestNeighbors(algorithm='kd_tree', n_neighbors=3)
undersample = NearMiss(version=1, neighbors=nn)

X_resampled, y_resampled = undersample.fit_resample(X, y)
print(f"Resampled class distribution: {Counter(y_resampled)}")

Final Notes #

For your single-variable case, Tomek Links or the clustering approach will be the fastest options—they leverage the 1D structure of your data to avoid unnecessary computations. All these methods avoid random sampling while retaining meaningful class distribution information.

内容的提问来源于stack exchange，提问作者Neverse