Hughui's Blog
0%

Posted on Edited on In

K近邻算法 简介

这一部分就不赘述了，挺基本的。

为啥需要KD-Tree

KD-Tree是存储训练数据的一种结构，因为K近邻算法没有显示的学习过程，所以每次对目标点进行分类的时候，都需要借助已知的训练数据。而类似感知机这种具有显示的学习过程的算法，会根据训练数据，得出一个模型sign(<w,x>+B)，后续预测直接用训练好的模型进行预测就行了。
因为这个特性，所以如果不采取特殊的数据结构对数据进行存储，那么每一次分类目标点的时候，都要遍历所有的训练数据，时间不可控。对此，KD-Tree就出来了，其实KD-Tree听名字就是一棵树，可以参考二分查找的过程。

什么是KD-Tree

这里先给出一颗KD-Tree的例子，后续再对KD-tree的Construction与Searching进行论述。
每一个节点对应着一个划分(就是一个大饼被刀切了)，如图所示，根节点(30,40)对应了整个输入空间（整个饼），根节点将整个输入控件分为了两类，分别是x<30, x>30，由其两个分支表示。（解释为啥是x，这与选择的特征有关，看图根节点左边是选的x，所以对比x）。这样不断往下划分，最终得到了整个输入空间的划分（左边），对应的数据结构如右边所示。
闲话：其实通过上面描述应该就知道KD-Tree存储的什么东西了，它将数据的信息（具体特征的数值大小）表示在了结构上。其与排序二叉树十分类似嘛。

KD-Tree’s Construction

  • 数据描述：(5,25) (10, 12) (30, 40) (35, 45) (50, 30) (70, 70)，输入空间为整个二维平面。即每个样本点，有两个特征，我们假定为(x, y)。我们先展示整个构造过程，再解释构造细节。
  1. 随机选择一点(30, 40)，作为`根节点`，x<30的(5,25) (10, 12)位于根节点左子树上。大于的就位于右子树。
  2. 在左子树中，随机选择一点作为`左子树的根节点`，这里选择了(5, 25)。然后y<25的位于其左子树，y>25的位于右子树
  3. 这样不断迭代，最终形成了树的模样。
  4. 根据构造出来的树画图：根据`判别条件`画垂直的线。如根节点，根据x来判别的，那么就在这一点上，垂直与x轴，将其代表的`划分`(根节点是整个输入空间嘛)，一分为二。

** 由上可知，整个过程中存在着3个问题尚未解决：我们在划分时应该选取哪个维度？划分时我们应该选择哪一个值来划分？什么时候停止划分？ **

  • 应该选择哪一个维度？
    一般是交叉维度来进行选择，如有n个维度，那么依次选择(1, 2, 3…n, 1, 2…n…)这样子。上述例子中就是交叉选择(x,y,x,y…)来进行的
  • 维度确定了我们应该选择哪一个点当作划分点？
    这个其实理论上来说当然是选择搜索路径最短的那个点，但是这好像不是很容易达到。《统计学习方法》中采用的方法是`采用中位数当作划分点`，这样可以保证整个树是平衡的。如上述第一步骤中，x的中位数是(30, 40) **(以左边为基准的话)**。那么根节点就是(30, 40)。
  • 我们什么时候停止划分?
    这是我们自己设定阈值，我们知道，每一个点对应一个划分区域，那么我们可设定 `threshold = 10`，表示如果这个划分区域中， 
    1
    2
    if num(point_In_Split) < threshold
    	End Spliting.

    • 这个其实理论上来说当然是选择搜索路径最短的那个点，但是这好像不是很容易达到。《统计学习方法》中采用的方法是采用中位数当作划分点，这样可以保证整个树是平衡的。如上述第一步骤中，x的中位数是(30, 40) (以左边为基准的话)。那么根节点就是(30, 40)。

    KD-Tree’s Searching

    这个我懒得描述了，看李航老师《统计学习方法》上就有。需要更正的一点是**（我觉得其算法3.3漏了一个判别步骤）**，算法3.3的(1)中，强调的是“直到子节点为叶节点为止”，但是有可能搜索结束后发现结束的那个节点并不是叶节点，如(50,30)，那么就要在(50, 30)下添加一个空节点，然后以该空节点作为"包含目标点x的叶节点"。

    Posted on Edited on In

    1. 奇异值分解：A=UΣV^T, 其中，U是AA^T的特征向量，Σ^2是AA^T的特征值，V是A^TA的特征向量，目的即将图片weights x heights分解为矩阵表达，这样存储时仅仅存储矩阵表达即可，从而达到压缩的效果。代码如下所示。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    import numpy as np
    from PIL import Image


    if __name__ == "__main__":
        # psuedo Code
        # 1. 加载图片成width x height的数组A
        # 2. 计算A^TA，算出其lambda^2, lambda是SIGMA, 对应特征向量是V1，V2；再根据(1):解AA^T的eigen vector作为U；（2）或者解AV/SIGMA得出U。
        # 3. 从大到小排列SIGMA以及对应U，V得出分解内容。
        # 4. 分析结论

        # 1. 得出矩阵A_TA
        Img = Image.open('./test.jpg')
        Img_array = np.array(Img)
        A = Img_array[:,:,0]
        A_T = A.transpose()
        A_TA = np.dot(A_T, A)

        # 2. 计算出对应特征值及对应特征向量，并排好序（in order of importance）
        eigenvalues,eigenVectors = np.linalg.eig(A_TA)
        tmp = np.column_stack((eigenvalues, eigenVectors))
        tmp = tmp[np.argsort(-(tmp[:,0]))]
        singularValues, singularVectorsV = np.nan_to_num(np.power(tmp[:, 0], 0.5)), tmp[:, 1:]

        # 用AV/SIGMA = U 计算U
        singularVectorsU = np.dot(A, singularVectorsV)/singularValues

        # 设置阈值为99%
        threshold = 0.99
        SigmaSum = np.sum(singularValues)
        tmp = singularValues[0]
        i = 1
        while(tmp/SigmaSum &lt;= threshold):
            tmp += singularValues[i]
            i += 1

        reConstructImgArray = np.dot(
            np.dot(singularVectorsU[:, 0:i+1], np.diag(singularValues[0:i+1])), 
            np.transpose(singularVectorsV[:, 0:i+1]))

        reConstructImg = Image.fromarray(reConstructImgArray)
        reConstructImg.show()
        # 结果为i=1257, 即压缩为了1257*(1980+2640), 原图是1980*2640, 这样压缩保留了99%的信息
        print("good luck")

    2. 左为重构，右为原图

    3. 结果说明

    > 原图大小是 198026403(带color channel)，现经过SVD压缩为了(1257(1980+2640)3)(代码中为了简单表明过程，只计算了一个color channel上的)。上述例子表明，在保存图片信息99%的情况下，压缩率为90%。

    Posted on Edited on In

    参考书目章节

    1. Introduction to linear algebra: P239, The Factorization A = QR
  • Iterative Methods for Sparse Linear systems: **P11**, Gram-schmidt

    [](#一：Gram-Schmidt)一：Gram-Schmidt

    Interesting: gilbert strang said:”i don’t know what schmidt did in this greatful process”
    在很多工作中，我们需要用到一组向量空间的正交基来简化计算（如简化求解Ax=b的最小二乘解的过程）。Gram-Schmidt就是**正交化**一种经典方法，掌握了**投影**后，gram-schmidt就很好理解了。

    • Interesting: gilbert strang said:”i don’t know what schmidt did in this greatful process”
    在很多工作中，我们需要用到一组向量空间的正交基来简化计算（如简化求解Ax=b的最小二乘解的过程）。Gram-Schmidt就是正交化一种经典方法，掌握了投影后，gram-schmidt就很好理解了。

    prerequisite: A的column space’s projection matrix is

    [](#1-首先以二维为例)1. 首先以二维为例

    `(x1, x2)`是线性无关的列向量，现需找出`orthonormal的(q1, q2)`来表示(x1,x2)的`列空间`。第一步:`q1=x1/norm2(x1)`。问题是如何依据x2找到q2使`<q1, q2> = 0`。 如图所示，`x2`在`q1`上的投影`p=<q1, x2>q1`，而我们需要的部分是`e(error) = x2-p`(# 注为啥叫error在投影那一章节有记录)。从而令`q2 = e/norm2(e)`。**用人话**来说就是，第n维的目标向量`(qn)`是第n维的已知向量`(xn)`依次减去其在`q1 -> qn-1`上的投影，最后单位化。

    [](#2-三维图示)2. 三维图示

    由此可推到出Gram_Schmidt的公式：

    [](#3-Pseudo-Code-of-Gram-Schmidt)3. Pseudo Code of Gram-Schmidt

    2. 三维图示

    二：A=QR与Gram-Schmidt的关系

    实际上这也是A=QR的第一种推理方式，即从Gram-Schmidt的推理过程得出A=QR。现假设我们已经通过Gram-Schmidt得到了前j个q(q1,q2...qj)，这样我们就可以得到,即将xj分解至每一个正交基上。用矩阵的语言进行表达，即X=QR,X=[x1, x2...,xr],Q=[q1,q2,...,qr]。如下图所示

    三：从行列空间规律得出A=QR

    这是A=QR的第二种推理方式，C(A)是independent的，在Gram-Schmidt中，我们的目的是找出orthonormal的Q，从目的而言，Q与A的列向量代表的向量空间肯定是一样的，即C(A) = C(Q)，根据线代的基础知识我们知道，肯定存在一个矩阵R，使得A=QR(A与Q的列向量空间相同)。若A is Square，那么A and Q both are invertiable。从而R=Q^(-1)A，又Q is orthonormal，so Q^(-1) = Q^T，so R = Q^TA，这样就求出了R，如下图所示。

    四：A=QR的应用

    gilbert Strang教授在书上说过："the matrix factorization is of most importance in linear algebra",A=QR作为一种矩阵分解，可以把线性独立的矩阵，分解成QR，Q是orthonormal,R又是upper triangle，特别是orthonormal给计算提供了很好的性质，目前接触到的就是在least square solution中的投影矩阵部分，逆的那一块直接为单位矩阵了，大大节约了计算时间成本。