ML算法——KNN随笔【全国科技工作者日创作】【机器学习】

来杯Sherry

发布于 2023-05-31 10:57:33

3910

发布于 2023-05-31 10:57:33

文章被收录于专栏：第一专栏第一专栏

9、K-Nearest Neighbors (KNN)

9.1、理论部分

K最邻近算法

把一个物体表示成向量【特征工程】,且 KNN 需要考虑【特征缩放】。
标记每个物体的标签
计算两个物体之间的距离/相似度
选择合适的 K

未知点的判断基于已知点的距离，选出最近的K个点，投票选出未知点的最大可能。

计算两个物体之间的距离/相似度？

欧氏距离

\sqrt{\sum_{i=1}^{n}(x_i^{} - x_i^{})^2}

其中，xi和xj是空间中的两个点，i和j表示维度。

点数K选取奇数的目的？

偶数更容易出现“平票”，奇数也不可避免地会出现平票（1：1：1）

使用 sklearn 实现，详见9.3。

选择合适的 k 对决策边界的影响？

决策边界：决定线性分类器、非线性分类器。

图中：

线性
非线性
非线性【最陡峭】，过拟合。

KNN的决策边界举例：

边界越陡峭，越不稳定，希望得到平滑的边界，理论上，K↑，边界越平滑。

如何选择 K 值？

交叉验证：训练集进一步划分为训练集【train】+验证集【validation】

以常用的五折交叉验证为例，

对 K= 1执行五次循环，取平均，作为 k= 1的成绩。
换 K ，重复。
千万不能用测试数据【X_test、y_test】来调参

在数据少时，可适当增加折数的合理性？

交叉验证可以通过增加折数来减少主观因素的影响，使得结果更加准确。

主观因素：主要指在进行数据分割的时候，因为某些人为因素导致分割不准确，进而对结果产生影响。比如，如果使用随机拆分数据的方式进行验证，因为随机拆分数据的时候存在不随机的情况，所以就会对验证效果产生影响。

KNN的优化方向

时间复杂度 O（N），适合低维空间内使用，优化方向：KD-tree 在二维空间的优化、LSH（Locality Sensitivity Hashing）不再寻求完全准确的解，加快搜索。
特征间的相关性处理，Mahalanobis Distance

9.2、实现

9.2.1、KNN 手写实现

from sklearn import datasets
from collections import Counter # 投票
from sklearn.model_selection import train_test_split
import numpy as np

def euc_dis(instance1, instance2):
    """
    计算欧氏距离
    :param instance1:样本1，array数组
    :param instance2: 样本2，array数组
    :return: 欧氏距离
    """
    d = np.sqrt(sum(instance1-instance2)**2)
    return d

def knn_classify(X , y, testInstance, k):
    """
    给未知点归类
    :param X: train——feature
    :param y: train——label
    :param testInstance:测试数据，array数组
    :param k:选择多少个 neighbors
    :return:最多元素
    """
    distances = [euc_dis(x, testInstance)for x in X]
    kneighbors = np.argsort(distances)[:k] #快排后，取前 k 个  || 优化？改用优先队列，维护前 k 个， O（NlogN）
    count = Counter(y[kneighbors]) # Counter([0,0,0,1,1,1,1,1,1])  -》 Counter({1: 6, 0: 3})
    return count.most_common()[0][0]   # [(1, 6), (0, 3)]  -》 1

#导入 iris 数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=50)

#预测结果
predictions = [knn_classify(X_train, y_train, data, 3) for data in X_test]
correct = np.count_nonzero((predictions == y_test) == True)
# acc
print("Accuaracy is :%.3f" %(correct/len(X_test)))

9.2.2、KNN sklearn 实现

鸢尾花【三分类问题】

库

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

读取数据 X,y

data = datasets.load_iris()
X = data.data   #N*D:sample * Dimension
y = data.target #label:(0,1,2)

分为训练数据 & 测试数据 (默认比例: 3/4 : 1/4)

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=500)

构建KNN模型，K=3 & 训练

clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(X_train, y_train)

计算准确率（二选一）

方法一

from sklearn.metrics import accuracy_score

acc  = accuracy_score(y_test,clf.predict(X_test))
print(acc)

方法二

import  numpy as np

correct = np.count_nonzero((clf.predict(X_test) == y_test) == True)
print(f'acc is {correct/len(X_test)}')

完整代码

#
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
#
data = datasets.load_iris()
X = data.data   #N*D:sample * Dimension
y = data.target #label:(0,1,2)
#
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=500)
#
clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(X_train, y_train)
#
from sklearn.metrics import accuracy_score

acc  = accuracy_score(y_test,clf.predict(X_test))
print(acc)

KNN没有训练痕迹，那么 clf.fit() 在做什么？

它是机器学习中唯一一个不需要训练过程的算法，它在训练阶段只是把数据保存下来，训练时间开销为 0，等收到测试样本后进行处理。

knn 算法手写实现的意义？较 sklearn 实现的 knn 优势在哪里?

简单易理解：KNN算法非常简单，易于理解。通过自己实现该算法，可以更深入地了解KNN算法的工作原理。
可扩展性：自己实现KNN算法可以让你更好地了解如何扩展算法以适应不同的数据集和场景。例如，你可以尝试使用不同的距离度量（如曼哈顿距离或切比雪夫距离），或者调整K值以获得更好的性能。
性能优化：在大数据集上，KNN算法的计算复杂度较高。通过自己实现该算法，你可以对算法进行优化，例如使用KD树来加速搜索邻居。
无依赖：自己实现KNN算法可以让你更好地了解算法的内部工作原理，无需依赖外部库。

想更深入地了解KNN算法的工作原理，或者需要对算法进行定制和优化，自己实现KNN算法是有意义的。只是想快速应用到项目上，那么使用sklearn是更好的选择。

9.3、案例

二手车预测案例【回归问题】

import pandas as pd
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns
#读取数据
df = pd.read_csv('data.csv')

#清洗数据
# 把颜色独热编码
df_colors = df['Color'].str.get_dummies().add_prefix('Color: ')
# 把类型独热编码
df_type = df['Type'].apply(str).str.get_dummies().add_prefix('Type: ')
# 添加独热编码数据列
df = pd.concat([df, df_colors, df_type], axis=1)
# 去除独热编码对应的原始列
df = df.drop(['Brand', 'Type', 'Color'], axis=1)
# 数据转换
matrix = df.corr()
f, ax = plt.subplots(figsize=(8, 6))
sns.heatmap(matrix, square=True)
plt.title('Car Price Variables')

from sklearn.neighbors import KNeighborsRegressor
from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.preprocessing import StandardScaler
import numpy as np

X = df[['Construction Year', 'Days Until MOT', 'Odometer']]
y = df['Ask Price'].values.reshape(-1, 1)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=41)

X_normalizer = StandardScaler() # N(0,1) 
X_train = X_normalizer.fit_transform(X_train)
X_test = X_normalizer.transform(X_test)

y_normalizer = StandardScaler()
y_train = y_normalizer.fit_transform(y_train)
y_test = y_normalizer.transform(y_test)

knn = KNeighborsRegressor(n_neighbors=2)
knn.fit(X_train, y_train.ravel())

#Now we can predict prices:
y_pred = knn.predict(X_test)
y_pred_inv = y_normalizer.inverse_transform(y_pred)
y_test_inv = y_normalizer.inverse_transform(y_test)

# Build a plot
plt.scatter(y_pred_inv, y_test_inv)
plt.xlabel('Prediction')
plt.ylabel('Real value')

# Now add the perfect prediction line
diagonal = np.linspace(500, 1500, 100)
plt.plot(diagonal, diagonal, '-r')
plt.xlabel('Predicted ask price')
plt.ylabel('Ask price')
plt.show()

print(y_pred_inv)