K-NN算法两种近似实现结果不一致问题排查求助

问题概述 #

我在Python中基于Online News Popularity数据集从零实现K近邻（K-NN）分类算法，常规单K值验证的准确率和sklearn的KNeighborsClassifier结果完全一致，但为提升验证效率设计的批量多K值验证版本，在k=169时的准确率和常规实现出现偏差，无法定位问题所在。

常规正确实现 #

核心预测函数 #

def KNNClassificationPredictOnValidation(row, norm_type, k):
    distances = np.linalg.norm(x_validation_train_np-row, ord=norm_type, axis=1)
    indexes = np.argpartition(distances, k)[:k]
    values = [y_th_validation_train_np[indexes[i]] for i in range(k)]
    return np.argmax(np.bincount(values))

运行代码及结果 #

y_pred = []
for row in x_validation_np:
  y_pred.append(KNNClassificationPredictOnValidation(row, 2, 169))

print(f"{metrics.accuracy_score(y_th_validation_np, y_pred)*100}%")

输出准确率：58.600031530821376%

sklearn对比实现及结果 #

neigh = KNeighborsClassifier(n_neighbors=169)
neigh.fit(x_validation_train_np, y_th_validation_train_np)
y_pred = neigh.predict(x_validation_np)
print(f"{metrics.accuracy_score(y_th_validation_np, y_pred)*100}%")

结果与常规实现完全一致。

批量验证优化版本（存在问题） #

批量预测函数 #

# Version tweaked for fast validation
def KNNClassificationValidationPredict(row, norm_type, start, end, step):
    distances = np.linalg.norm(x_validation_train_np-row, ord=norm_type, axis=1)
    indexes = np.argpartition(distances, end)[:end+1]
    return [np.argmax(np.bincount([y_th_validation_train_np[indexes[i]] for i in range(k)])) for k in range(start, end, step)]

测试代码及结果 #

# My tweaked version for validation
left_end = 167
right_end = 171
y_pred = []
for row in x_validation_np:
  y_pred.append(KNNClassificationValidationPredict(row, 2, left_end, right_end+1, 2))

results = []
y_pred = np.array([np.array(y) for y in y_pred])
for i in range(len(y_pred[0])):
  y = y_pred[:, i]
  accuracy = metrics.accuracy_score(y_th_validation_np, y)
  results.append((left_end+i*2, accuracy*100))
print(results)

输出中k=169对应的准确率为58.473908245309794%，与常规实现结果不一致。

最小可复现代码 #

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn import metrics
import numpy as np
from sklearn.neighbors import KNeighborsClassifier


df = pd.read_csv('OnlineNewsPopularity/OnlineNewsPopularity.csv')
df = df.rename(columns=lambda x: x.strip())
df = df.iloc[: , 2:]

# non-thresholded shares
y = df.pop('shares')

# thresholded shares
y_th = y.copy(deep=True)
y_th = y_th.apply(lambda x: 1 if x >= 1400 else 0)

# renaming the variable
x = df

# tresholded version
x_train, x_test, y_th_train, y_th_test = train_test_split(
    x, y_th,
    test_size=0.20,
    random_state=1
)

x_train_np = x_train.to_numpy()
x_test_np = x_test.to_numpy()

y_th_train_np = y_th_train.to_numpy()
y_th_test_np = y_th_test.to_numpy()

# Creating validation set
x_validation_train, x_validation, y_th_validation_train, y_th_validation = train_test_split(
    x_train, y_th_train,
    test_size=0.20,
    random_state=1
)


x_validation_train_np = x_validation_train.to_numpy()
x_validation_np = x_validation.to_numpy()

y_th_validation_train_np = y_th_validation_train.to_numpy()
y_th_validation_np = y_th_validation.to_numpy()


def KNNClassificationPredict(row, norm_type, k):
    distances = np.linalg.norm(x_train_np-row, ord=norm_type, axis=1)
    indexes = np.argpartition(distances, k)[:k]
    values = [y_th_train_np[indexes[i]] for i in range(k)]
    return np.argmax(np.bincount(values))

# Version tweaked for fast validation
def KNNClassificationValidationPredict(row, norm_type, start, end, step):
    distances = np.linalg.norm(x_validation_train_np-row, ord=norm_type, axis=1)
    indexes = np.argpartition(distances, end)[:end+1]
    return [np.argmax(np.bincount([y_th_validation_train_np[indexes[i]] for i in range(k)])) for k in range(start, end, step)]

def KNNClassificationPredictOnValidation(row, norm_type, k):
    distances = np.linalg.norm(x_validation_train_np-row, ord=norm_type, axis=1)
    indexes = np.argpartition(distances, k)[:k]
    values = [y_th_validation_train_np[indexes[i]] for i in range(k)]
    return np.argmax(np.bincount(values))

# Sklearn implementation against validation set
neigh = KNeighborsClassifier(n_neighbors=169)
neigh.fit(x_validation_train_np, y_th_validation_train_np)
y_pred = neigh.predict(x_validation_np)
print(f"{metrics.accuracy_score(y_th_validation_np, y_pred)*100}%")

# My normal knn against validation set
y_pred = []
for row in x_validation_np:
  y_pred.append(KNNClassificationPredictOnValidation(row, 2, 169))

print(f"{metrics.accuracy_score(y_th_validation_np, y_pred)*100}%")

# My tweaked version for validation
left_end = 167
right_end = 171
y_pred = []
for row in x_validation_np:
  y_pred.append(KNNClassificationValidationPredict(row, 2, left_end, right_end+1, 2))

results = []
y_pred = np.array([np.array(y) for y in y_pred])
for i in range(len(y_pred[0])):
  y = y_pred[:, i]
  accuracy = metrics.accuracy_score(y_th_validation_np, y)
  results.append((left_end+i*2, accuracy*100))
print(results)

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