一天一元网站建设,安徽建站系统,视频制作网站素材,借20万资金办厂文章目录k近邻 / KNN主要思想模型要素距离度量分类决策规则kd树主要思想kd树的构建kd树的搜索总结归纳k近邻 / KNN
主要思想
假定给定一个训练数据集#xff0c;其中实例标签已定#xff0c;当输入新的实例时#xff0c;可以根据其最近的 kkk 个训练实例的标签#xff0c…
文章目录k近邻 / KNN主要思想模型要素距离度量分类决策规则kd树主要思想kd树的构建kd树的搜索总结归纳k近邻 / KNN
主要思想
假定给定一个训练数据集其中实例标签已定当输入新的实例时可以根据其最近的 kkk 个训练实例的标签预测新实例对应的标注信息。
具体划分kkk 近邻又可细分为分类问题和回归问题。
分类问题对新的实例根据与之相邻的 kkk 个训练实例的类别通过多数表决等方式进行预测。 回归问题对新的实例根据与之相邻的 kkk 个训练实例的标签通过均值计算进行预测。
输入训练集 T{(x1,y1),(x2,y2)⋯,(xN,yN)}T\left\{\left(x_1, y_1\right),\left(x_2, y_2\right) \cdots,\left(x_N, y_N\right)\right\} T{(x1,y1),(x2,y2)⋯,(xN,yN)} 其中xi∈X⊆Rn,y∈Y{c1,c2,⋯,cK}x_i \in \mathcal{X} \subseteq \mathbf{R}^n, y \in \mathcal{Y}\left\{c_1, c_2, \cdots, c_K\right\}xi∈X⊆Rn,y∈Y{c1,c2,⋯,cK}实例 xxx
输出实例 xxx 的所属的类 yyy 。
根据给定的距离度量计算 xxx 与 TTT 中点的距离在 TTT 中找到与 xxx 最邻近的 kkk 个点涵盖这 kkk 个点的 xxx 的邻域记作 Nk(x)N_k(x)Nk(x) 在 Nk(x)N_k(x)Nk(x) 中根据分类决策规则如多数表决决定 xxx 的类别 yyy
yargmaxcj∑xi∈Nk(x)I(yicj),i1,2,⋯,N;j1,2,⋯,Ky\underset{c_j}{\arg \max } \sum_{x_i \in N_k(x)} I\left(y_ic_j\right), \quad i1,2, \cdots, N ; j1,2, \cdots, K ycjargmaxxi∈Nk(x)∑I(yicj),i1,2,⋯,N;j1,2,⋯,K
kkk 近邻法k-nearest neighbork-NN不具有显性的学习过程无优化算法无训练过程实际上利用训练数据集对特征向量空间进行划分以其作为分类的“模型”。
模型要素
距离度量
LPL_PLP 距离特征空间 X\mathcal{X}X 假设为 Rn,∀xi,xj∈X,xi(xi(1),xi(2),⋯,xi(n))T,xj(xj(1),xj(2),⋯,xj(n))T\mathbf{R}^n, \forall x_i, x_j \in \mathcal{X}, x_i\left(x_i^{(1)}, x_i^{(2)}, \cdots, x_i^{(n)}\right)^T, x_j\left(x_j^{(1)}, x_j^{(2)}, \cdots, x_j^{(n)}\right)^TRn,∀xi,xj∈X,xi(xi(1),xi(2),⋯,xi(n))T,xj(xj(1),xj(2),⋯,xj(n))T则有
Lp(xi,xj)(∑l1n∣xi(l)−xj(l)∣p)1p,p≥1L_p\left(x_i, x_j\right)\left(\sum_{l1}^n\left|x_i^{(l)}-x_j^{(l)}\right|^p\right)^{\frac{1}{p}}, \quad p \geq 1 Lp(xi,xj)(l1∑nxi(l)−xj(l)p)p1,p≥1
欧氏距离Euclidean distance ppp 2 L2(xi,xj)(∑I1n∣xi(l)−xj(l)∣2)12L_2\left(x_i, x_j\right)\left(\sum_{I1}^n\left|x_i^{(l)}-x_j^{(l)}\right|^2\right)^{\frac{1}{2}} L2(xi,xj)(I1∑nxi(l)−xj(l)2)21 曼哈顿距离Manhattan distance ppp 1 L1(xi,xj)∑l1n∣xi(l)−xj(l)∣L_1\left(x_i, x_j\right)\sum_{l1}^n\left|x_i^{(l)}-x_j^{(l)}\right| L1(xi,xj)l1∑nxi(l)−xj(l) 切比雪夫距离Chebyshev distanceppp ∞{\infty}∞ L∞(xi,xj)maxl∣xi(l)−xj(l)∣L_{\infty}\left(x_i, x_j\right)\max _l\left|x_i^{(l)}-x_j^{(l)}\right| L∞(xi,xj)lmaxxi(l)−xj(l) 分类决策规则
分类函数 f:Rn→{c1,c2,⋯,cK}f: \mathbf{R}^n \rightarrow\left\{c_1, c_2, \cdots, c_K\right\} f:Rn→{c1,c2,⋯,cK} 0-1 损失函数 L(Y,f(X)){1,Y≠f(X)0,Yf(X)L(Y, f(X)) \begin{cases}1, Y \neq f(X) \\ 0, Yf(X)\end{cases} L(Y,f(X)){1,0,Yf(X)Yf(X) 误分类概率 P(Y≠f(X))1−P(Yf(X))P(Y \neq f(X))1-P(Yf(X)) P(Yf(X))1−P(Yf(X)) 给定实例 x∈Xx \in \mathcal{X}x∈X 相应的 kkk 邻域 Nk(x)N_k(x)Nk(x) 类别为 cjc_jcj 误分类率 1k∑xi∈Nk(x)I(yi≠cj)1−1k∑xi∈Nk(x)I(yicj)\frac{1}{k} \sum_{x_i \in N_k(x)} I\left(y_i \neq c_j\right)1-\frac{1}{k} \sum_{x_i \in N_k(x)} I\left(y_ic_j\right) k1xi∈Nk(x)∑I(yicj)1−k1xi∈Nk(x)∑I(yicj) 最小化误分析率等价于 argmax∑xi∈Nk(x)I(yicj)\underset{}{\arg \max } \sum_{x_i \in N_k(x)} I\left(y_ic_j\right) argmaxxi∈Nk(x)∑I(yicj)
kd树
主要思想
kd 树是一种对 kkk 维空间中的实例点进行储存以便对其进行快速检索的树形数据结构。
本质二叉树表示对 kkk 维空间的一个划分。 构造过程不断地用垂直于坐标轴的超平面将 kkk 维空间切分形成 kkk 维超矩形区域。 kd 树的每一个结点对应于一个 kkk 维超矩形区域。
kd树的构建
输入 kkk 维空间数据集 T{x1,x2,⋯,xN}T\left\{x_1, x_2, \cdots, x_N\right\} T{x1,x2,⋯,xN} 其中xi(xi(1),xi(2),⋯,xi(k))Tx_i\left(x_i^{(1)}, x_i^{(2)}, \cdots, x_i^{(k)}\right)^Txi(xi(1),xi(2),⋯,xi(k))T
输出kd 树
开始构造根结点。 选取 x(1)x^{(1)}x(1) 为坐标轴以训练集中的所有数据 x(1)x^{(1)}x(1) 坐标中的中位数数据集为偶数时中位数1作为切分点将超矩形区域切割成两个子区域将该切分点作为根结点。 由根结点生出深度为 1 的左右子结点左结点对应坐标小于切分点右结点对应坐标大于切分点。 重复 对深度为 jjj 的结点选择 x(l)x^{(l)}x(l) 为切分坐标轴切分应垂直于坐标轴lj(modk)1l j(\ mod \ k) 1lj( mod k)1 以该结点区域中所有实例 x(1)x^{(1)}x(1) 坐标的中位数作为切分点将区域分为两个子区域。 生成深度为 j1j1j1 的左、右子结点。左结点对应坐标小于切分点右结点对应坐标大于切分点。 直到两个子区域没有实例时停止。
kd树的搜索
输入已构造的 kd 树目标点 xxx
输出xxx 的最近邻
寻找“当前最近点“ 从根结点出发递归访问 kd 树找出包含 xxx 的叶结点kd 树的每一个结点对应一个超矩形区域以此叶结点为当前最近点 回溯 若该结点比“当前最近点”的距离目标更近更新“当前最近点”当前最近点一定存在于该结点一个子结点对应的区域检查子结点的父结点的另一子结点子结点的兄弟结点对应的区域是否有更近的点。 当回退到根结点时搜索结束最后的“当前最近点”即为 xxx 的最近邻点。
目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。
如果父结点的另一个子结点的超矩形区域与超球体相交那么在相交的区域内寻找与目标点更近的实例点。
总结归纳
较小的 kkk 值学习的近似误差减小但估计误差增大敏感性增强而且模型复杂容易过拟合。 较大的 kkk 值减少学习的估计误差但近似误差增大而且模型简单。kkk 的取值可通过交叉验证来选择一般低于训练集样本量的平方根。分类决策规则使用 0-1 损失函数因为分类问题只有分类正确和分类错误两种可能。kd 树构建时对于超平面的划分二位空间划分为矩形三维空间划分为长方体。构建完成的 kd 树类似于二叉排序树每一层代表着一个维度。kd 树的搜索类似于二叉排序树的搜索过程。kkk 近邻算法对于高维数据的处理略显缓慢此时可以考虑数据降维以及 kd 树。kd 树更适用于训练实例数远大于空间维数时的 kkk 近邻搜索。
