机器学习-KNN
KNN大致流程
1)计算已知类别数据集中的点与当前点之间的距离
2)按距离递增次序排序
3)选取与当前点距离最⼩的k个点
4)统计前k个点所在的类别出现的频率
5)返回前k个点出现频率最⾼的类别作为当前点的预测分类
1.距离度量
范数(norm):给单个向量定义“长度”或“大小”
1.1 欧氏距离(Euclidean distance)
最经典的距离,表示所有维度上的差异平方后相加的值再开根,i表示维度
距离公式:
d(x,y)=∑i(xi−yi)2
d\left( x,y \right) = \sqrt{\sum_{i}^{}(x_{i} - y_{i})^{2}}
d(x,y)=i∑(xi−yi)2
def euclidean(x, y):
return np.sqrt(np.sum((x - y)**2))
曼哈顿距离(Manhattan distance)
也称为城市街区距离,表示在所有维度上的差异值直接相加,i表示维度
距离公式:
d(x,y)=∑i∣xi−yi∣
d(x,y) = \sum_{i}^{}|x_{i} - y_{i}|
d(x,y)=i∑∣xi−yi∣
def manhattan(x, y):
return np.sum(np.abs(x - y))
切比雪夫距离(Chebyshev distance)
表示在所有维度(坐标轴)上寻找最大的单一维度差异。即当闵可夫斯基距离的p趋于∞时除最大维度差异外其余维度的差异可忽略,i表示维度
距离公式:
d(x,y)=maxi∣xi−yi∣
d\left( x,y \right) = \max_{i}\left| x_{i} - y_{i} \right|
d(x,y)=imax∣xi−yi∣
def chebyshev(x, y):
return np.max(np.abs(x - y))
闵可夫斯基距离(Minkowski distance)
闵可夫斯基距离是欧几里得距离的推广,通过一个参数 p 控制对维度间差异的敏感度,当p无穷大时除最大维度距离外其余可被忽略,i表示维度
范数Lp的p实际上就是Minkowskidistance的参数p
范数 L_p 的p实际上就是Minkowski distance的参数p
范数Lp的p实际上就是Minkowskidistance的参数p
当p=1时,为曼哈顿距离
当p=2时,为欧氏距离
当p->∞时,为切比雪夫距离
d(x,y)=(∑i∣xi−yi∣p)1p
d\left( x,y \right) = \left( \sum_{i}^{}|x_{i} - y_{i}|^{p} \right)^{\frac{1}{p}}
d(x,y)=(i∑∣xi−yi∣p)p1
def minkowski(x, y, p):
return np.sum(np.abs(x - y)p)(1 / p)
*汉明距离(Hamming distance)
汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以表示两个字,之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。
距离公式:
d(x,y)=1N∑i1xi≠yi
d\left( x,y \right) = \frac{1}{N}\sum_{i}^{}1_{x_{i} \neq y_{i}}
d(x,y)=N1i∑1xi=yi
def hamming(x, y):
return np.sum(x != y) / len(x)
*余弦相似度(Cosine Similarity)
余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时,余弦相似度的值为1;两个向量夹角为90°时,余弦相似度的值为0;两个向量指向完全相反的方向时,余弦相似度的值为-1。这结果是与向量的长度无关的,仅仅与向量的指向方向相关。余弦相似度通常用于正空间,因此给出的值为0到1之间。
二维空间为例,上图的aaa和bbb是两个向量,我们要计算它们的夹角θ。余弦定理告诉我们,可以用下面的公式求得:
cosθ=a2+b2−c22ab
\cos\theta = \frac{a^{2} + b^{2} - c^{2}}{2ab}
cosθ=2aba2+b2−c2
假定aaa向量是[x1,y1]\left\lbrack x_{1},y_{1} \right\rbrack[x1,y1],bbb向量是[x2,y2]\left\lbrack x_{2},y_{2} \right\rbrack[x2,y2],两个向量间的余弦值可以通过使用点积公式求出:
cos(θ)=A⋅B∥A∥∥B∥=(x1,y1)⋅(x2,y2)x12+y12×x22+y22=x1x2+y1y2x12+y12×x22+y22 \cos\left( \theta \right) = \frac{A \cdot B}{\parallel A \parallel \parallel B \parallel} = \frac{\left( x_{1},y_{1} \right) \cdot \left( x_{2},y_{2} \right)}{\sqrt{x_{1}^{2} + y_{1}^{2}} \times \sqrt{x_{2}^{2} + y_{2}^{2}}} = \frac{x_{1}x_{2} + y_{1}y_{2}}{\sqrt{x_{1}^{2} + y_{1}^{2}} \times \sqrt{x_{2}^{2} + y_{2}^{2}}} cos(θ)=∥A∥∥B∥A⋅B=x12+y12×x22+y22(x1,y1)⋅(x2,y2)=x12+y12×x22+y22x1x2+y1y2
如果向量aaa和bbb不是二维而是nnn维,上述余弦的计算法仍然正确。假定AAA和BBB是两个nnn维向量,AAA是[A1,A2,…,An]\left\lbrack A_{1},A_{2},\ldots,A_{n} \right\rbrack[A1,A2,…,An],BBB是[B1,B2,…,Bn]\left\lbrack B_{1},B_{2},\ldots,B_{n} \right\rbrack[B1,B2,…,Bn],则AAA与BBB的夹角余弦等于:
cos(θ)=A⋅B∥A∥∥B∥=∑i=1nAi×Bi∑i=1n(Ai)2×∑i=1n(Bi)2 \cos\left( \theta \right) = \frac{A \cdot B}{\parallel A \parallel \parallel B \parallel} = \frac{\sum_{i = 1}^{n}A_{i} \times B_{i}}{\sqrt{\sum_{i = 1}^{n}(A_{i})^{2}} \times \sqrt{\sum_{i = 1}^{n}(B_{i})^{2}}} cos(θ)=∥A∥∥B∥A⋅B=∑i=1n(Ai)2×∑i=1n(Bi)2∑i=1nAi×Bi
2 KD树的划分和搜索
1 KD树
KD树(K-Dimension Tree),一种二叉树,也可称之为kkk维树,构造KD树相当于不断地用垂直于坐标轴的超平面将kkk维空间切分,构成一系列的维超矩形区域。KD树的每个结点对应于一个kkk维超矩形区域。。利用KD树可以省去对大部分数据点的搜索,从而减少搜索的计算量。
2 构造KD树的方法
(1)分割维度
KD树在每一层选择一个维度(比如x轴、y轴.),按该维度的 中位数 把数据分成两半。
例子(2维数据)
第1层按 x轴 分割
第2层按 y轴 分割
第3层又回到 x轴…(交替进行)
(2)分割点
选当前维度下所有数据的 中位数 作为分割点,比它小的去左子树,大的去右子树。【左小右大】
目的: 让树尽量平衡,提高搜索效率。
(3)终止条件
当剩余数据点少于某个阈值(比如S5个),就不再分割,直接作为叶子节点。
类⽐“⼆分查找”:给出⼀组数据:[9 1 4 7 2 5 0 3 8],要查找8。如果挨个查找(线性扫描),那么将会把数据集都遍历⼀遍。⽽如果排⼀下序那数据集就变成了:[0 1 2 3 4 5 6 7 8 9],按前⼀种⽅式我们进⾏了很多没有必要的查找,现在如果我们以5为分界点,那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。
因此,根本就没有必要进⼊第⼀个簇,可以直接进⼊第⼆个簇进⾏查找。把⼆分查找中的数据点换成k维数据点,这样的划分就变成了⽤超平⾯对k维空间的划分。空间划分就是对数据点进⾏分类,“挨得近”的数据点就在⼀个空间⾥⾯。
3 k值选择:
通常是 k = 开根n
最好通过网格搜索寻找最优参数
不同k值的区别
k值过小:易过拟合,近似误差小而估计误差大
k值过大:易欠拟合,近似误差过大而估计误差小(但有限)
from sklearn.datasets import load_iris
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as snsiris = load_iris() # 导入数据集
iris_data = pd.DataFrame(iris.data,columns=iris.feature_names)
iris_data["target"] = iris.target
# iris_data["target_names"]=iris.target
# for i in range(len(iris.target_names)):
# mask =iris_data["target"]==i
# iris_data.loc[mask,"target_names"]=iris.target_names[i]
def plot_iris(data,col1,col2):sns.scatterplot(data=data,x=col1,y=col2,hue="target",)plt.title(f"{col1} vs {col2}")plt.show()
plot_iris(iris_data,"sepal length (cm)","sepal width (cm)")
#%%
# 分出特征和目标
X=iris_data.drop(columns="target")
y=iris_data["target"]
# 分出训练集和测试集
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size= 0.2,random_state=42
)# 标准化
transfer = StandardScaler()
X_train=transfer.fit_transform(X_train)
X_test = transfer.transform(X_test)
# 训练
estimator = KNeighborsClassifier(n_neighbors=5)
estimator.fit(X_train, y_train) # fit的X参数必须输入二维的
#评估
ret = estimator.predict(X_test)# 准确率
accuracy = estimator.score(X_test, y_test)
accuracy
# f1_score = estimator.f1_score(X_test, y_test)