
class Chapter3:
    """
    第3章 k近邻法
    """
    def __init__(self):
        """
        第3章 k近邻法
        """
        pass

    def note(self):
        """
        chapter3 note
        """
        print('第3章 k近邻法')
        print('k近邻法(k-nearset neighbor, k-NN)是一种基本分类方法与回归方法.本章只讨论分类问题中的k近邻法.',
            'k近邻法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类.')
        print('k近邻法假定给定一个训练数据集,其中的实例类别已定.分类时,对新的实例,根据其k个最邻近的训练实例的类别,',
            '通过多数表决等方式进行预测.')
        print('因此,k近邻法不具有显式的学习过程.k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”.',
            'k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素.k近邻法1968年由Cover和Hart提出')
        print('k近邻法模型、三个基本要素、k近邻法的一个实现方法----kd树,构造kd树和搜索kd树的算法')
        print('3.1 k近邻算法')
        print('k近邻算法简单、直观：给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,',
            '这k个实例的多数属于某个类,就把该输入实例分为这个类.')
        print('算法3.1 (k近邻算法)')
        print('  输入:训练数据集T={(x1,y1),(x2,y2),...,(xn,yn)}')
        print('  其中,xi∈X∈R^n为实例的特征向量,yi∈Y={c1,c2,...,cK}为实例的类别,i=1,2,...,N;实例特征向量x')
        print('  输出:实例x所属的类y.')
        print('  (1) 在Nk(x)中根据分类决策规则(如多数表决)决定x的类别y:')
        print('  y=argmax∑I(yi=cj),i=1,2,...,N; j=1,2,...,K')
        print('  I为指示函数,即当yi=cj时I为1,否则I为0.')
        print('k近邻法的特殊情况是k=1的情形,称为最近邻算法.对于输入的实例点(特征向量)x,最近邻法将训练数据集中与x最邻近点的类作为x的类.')
        print('3.2 k近邻模型')
        print('k近邻法使用的模型实际上对应于特征空间的划分.模型由三个基本要素----距离度量、k值的选择和分类决策规则决定.')
        print('3.2.1 模型')
        print('k近邻法中,当训练集、距离度量(如欧式距离)、k值及分类决策规则(如多数表决)确定后,对于任何一个新的输入实例,',
            '它所属的类唯一地确定.这相当于根据上述要素将特征空间划分为一些子空间,确定子空间里的每个点所属的类')
        print('3.2.2 距离度量')
        print('特征空间中两个实例点的距离是两个实例点相似程度的反映.k近邻模型的特征空间一般是n维实数向量空间R^n.',
            '使用的距离是欧式距离,但也可以是其他距离,如更一般的Lp距离或Minkowski距离.(类似于向量的L范数)')
        print('设特征空间X是n维实数向量空间R^n,点xi和点xj的Lp距离为：')
        print('Lp(xi,xj)=(∑|xi-xj|^p)^(1/p); p>=1')
        print('当p=2时,称为欧式距离,当p=1时,称为欧式距离.')
        print('当p=∞时,它是各个坐标距离的最大值,即L∞(xi,xj)=max|xi(l)-xj(l)|')
        print('p=1时在平面上表示一个正菱形,p=2在平面上表示一个圆,p=∞在平面上表示一个正方形')
        print('例3.1 已知二维空间的3个点x1=(1,1)^T, x2=(5,1)^T, x3=(4,4)^T, 试求在p取不同值时,Lp距离下x1的最近邻点')
        print('解: 因为x1和x2只有第二维上值不同,所以p为任何值时,Lp(x1,x2)=4.而:')
        print('  L1(x1,x3)=6, L2(x1,x3)=4.24, L3(x1,x3)=3.78, L4(x1,x3)=3.57')
        print('于是得到:p等于1或2时,x2是x1的最近邻点;p大于等于3时,x3是x1的最近邻点.')
        print('3.2.3 k值的选择')
        print('k值的选择会对k近邻法的结果产生重大影响.')
        print('如果选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差会减小,只有与输入实例较近的(相似的)',
            '训练实例才会对预测结果起作用.','但缺点是“学习”的估计误差会增大,预测结果会对近邻的实例点非常敏感.')
        print('如果邻近的实例点恰好是噪声,预测就会出错.换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合')
        print('如果选择较大的k值,就相当于用较大邻域中的训练实例进行预测.其优点是可以减少学习的估计误差.',
            '但缺点是学习的近似误差会增大.这时与输入实例较远的(不相似的)训练实例也会起预测作用,使预测发生错误.',
            'k值的增大就意味着整体的模型变得简单')
        print('如果k=N,那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类.',
            '这时,模型过于简单,完全忽略训练实例中的大量有用信息,是不可取的')
        print('在应用中,k值一般取一个比较小的数值.通常采用交叉验证法来选取最优的k值')
        print('3.2.4 分类决策规则')
        print('k近邻法中的分类决策规则往往是多数表决的,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类')
        print('多数表决规则有如下解释:如果分类的损失函数为0-1损失函数,分类函数为f:R^n->{c1,c2,...,cK}')
        print('那么误分类的概率是:P(Y!=f(X))=1-P(Y=f(X))')
        print('对给定的实例x∈X,其最近邻的k个训练实例点构成集合Nk(x).如果涵盖Nk(x)的区域的类别是cj,',
            '那么误分类率是1/k∑I(yi!=cj)=1-1/k∑I(yi=cj)')
        print('要使误分类率最小即经验风险最小,就要使∑I(yi=cj)最大.所以多数表决规则等价于经验风险最小化.')
        print('3.3 k近邻法的实现：kd树')
        print('实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索.这点在特征空间的维数大及训练数据容量大时尤其必要.')
        print('k近邻法最简单的实现方法是线性扫描.这时要计算输入实例与每一个训练实例的距离.当训练集很大时,计算非常耗时')
        print('3.3.1 构造kd树')
        #! kd树的构造过程类似于并归递归排序,并生成一个二叉树
        print('kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构.kd树是二叉树,表示对k维空间的一个划分(partition)',
            '构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间划分,构成一系列的k维超矩形区域.kd树的每个节点对应于一个k维超矩形区域')
        print('构造kd树的方法如下:构造根结点,使根结点对应于k维空间中包含所有实例点的超矩形区域,通过递归方法,',
            '不断地对k维空间进行划分,生成子结点.在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点,',
            '确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域(子结点);',
            '这时,实例被分到两个子区域.这个过程直到子区域内没有实例时终止(终止时的结点为叶结点).在此过程中,将实例保存在相应的结点上')
        print('注意：平衡的kd树搜索时的效率未必是最优的')
        print('算法3.2 (构造平衡kd树)')
        print('输入:k维空间数据集T={x1,x2,...,xN}')
        print('其中,xi=(xi(1),xi(2),...,xi(k)),i=1,2,...,N')
        print('输出:kd树')
        print('  (1) 开始:构造根结点,跟结点对应于包含T的k维空间的超矩形区域')
        print('  选择x(1)为坐标轴,以T中所有的实例的x(1)坐标的中位数为切分点,将根结点对应的超矩形区域切分为两个子区域.',
            '切分由通过切分点并与坐标轴x(1)垂直的超平面实现.')
        print('  由根结点生成深度为1的左、右子结点对应坐标x(1)小于切分点的子区域,右子结点对应于坐标x(1)大于切分点的子区域')
        print('  (2) 重复:对深度为j的结点,选择x(l)为切分的坐标轴,l=j(mod k) + 1,',
            '以该结点的区域中所有实例的x(l)坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域.',
            '切分由通过切分点并与坐标轴x(l)垂直的超平面实现')
        print('  由该结点生成深度为j+1的左、右子结点：左子结点对应坐标x(l)小于切分点的子区域，右子结点对应坐标x(l)大于切分点的子区域')
        print('  将落在切分超平面上的实例点保存在该结点')
        print('  (3) 直到两个子区域没有实例存在时停止.从而形成kd树的区域划分')
        print('例3.2 给定一个二维空间的数据集:T={(2,3)^T, (5,4)^T, (9,6)^T, (4,7)^T, (8,1)^T, (7,2)^T},构造一个平衡kd树')
        print('解:根结点对应包含数据集T的矩形,选择x(1)轴,6个数据点的x(1)坐标的中位数是7.以平面x(1)=7将空间分为左、右两个子矩形(子结点)',
            '接着:左矩形以x(2)=4分为两个子矩形,右矩形以x(2)=6分为两个子矩形,如此递归,最后得到最终的kd树')
        print('3.3.2 搜索kd树')
        # !先将所有的数据点存入一个二叉搜索树结构中,利用二叉树的结构只搜索目标结点的父结点即可
        print('  下面介绍如何利用kd树进行k近邻搜索.可以看出,利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量.',
            '这里以最近邻为例加以叙述,同样的方法可以应用到k近邻.')
        print('  给定一个目标点,搜索其最近邻.首先找到包含目标点的叶结点;然后从叶结点出发,依次退回到父结点;',
            '不断查找与目标点最邻近的结点,当确定不可能存在更近的结点时终止.',
            '这样搜索就被限制在空间的局部区域上,效率大为提高.')
        print('算法3.3 (用kd树的最近邻搜索)')
        print('输入:已构造的kd树;目标点x;')
        print('输出:x的最近邻')
        print('  (1) 在kd树中找出包含目标点x的叶结点:从根结点出发,递归地向下访问kd树.若目标点x当前维度的坐标小于切分点的坐标,',
            '则移动到左子结点,否则移动到右子结点.直到子结点为叶结点为止')
        print('  (2) 以此叶结点为“当前最近点”')
        print('  (3) 递归地向上回退,在每个结点进行一下操作')
        print('  (a) 如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”')
        print('  (b) 当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一子结点对应的区域是否有更近的点',
            '具体地,检查另一子结点对应的区域是否以目标点为球心,以目标点与“当前最近点”间的距离为半径的超球体相交')
        print('  如果相交,可能在另一子结点对应的区域内存在距目标点更近的点,移动到另一个子结点.接着,递归地进行最近邻搜索.')
        print('  如果不相交,向上回退')
        print('  (4) 当回退到根结点时,搜索结束.最后的“当前最近点”即为x的最邻点')
        print('  如果实例点是随机分布的,kd树搜索的平均计算复杂度是O(logN),这里N是训练实例数.',
            'kd树更适用于训练实例树远大于空间维数时的k近邻搜索.当空间维数接近训练实例数时,效率会迅速下降,几乎接近线性扫描.')
        print('本章概要')
        print('1.k近邻法是基本且简单的分类与回归方法.k近邻法的基本做法是：',
            '对给定的训练实例点和输入实例点,首先确定输入实例点的k个最近邻训练实例点',
            '然后利用这k个训练实例点的类的多数来预测输入实例点的类')
        print('2.k近邻模型对应于基于训练数据集对特征空间的一个划分.k近邻法中,当训练集,距离度量,',
            'k值及分类决策规则确定后,其结果唯一确定.')
        #! k近邻法三要素:距离度量,k值的选择,分类决策规则
        print('3.k近邻法三要素:距离度量,k值的选择,分类决策规则.常用的距离度量是欧式距离及更一般的Lp距离.',
            'k值小时,k近邻模型更复杂;k值大时,k近邻模型更简单.k值的选择反应了对近似误差与估计误差之间的权衡',
            '通常由交叉验证选择最优的k.常用的分类决策规则是多数表决.对应于经验风险最小化')
        print('4.k近邻法的实现需要考虑如何快速搜索k个最近邻点.kd树是一种便于对k维空间中的数据进行快速检索的数据结构',
            'kd树是二叉树,表示对k维空间的数据进行快速检索的数据结构.kd树是二叉树,表示对k维空间的一个划分,',
            '其每个结点对应于k维空间划分中的一个超矩阵区域.利用kd树可以省去对大部分数据点的搜索,',
            '从而减少搜索的计算量')
        print('习题3.1 在二维空间中给出实例点,画出k=1和2时的k近邻法构成的空间划分,并对其进行比较',
            '并对其进行比较,体会k值选择与模型复杂度及预测准确率的关系')
        print('习题3.2 构造kd树求点x=(3,4.5)^T的最近邻点')
        print('习题3.3 写出输出为x的k近邻的算法')
        
chapter3 = Chapter3()

def main():
    chapter3.note()

if __name__ == '__main__':
    main()