发表于

红黑树

什么是红黑树

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。

黑色高度
从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。

红黑树的 5 个特性

我的头像

红黑树在原有的二叉查找树基础上增加了如下几个要求：

  1. 每个节点要么是红色，要么是黑色；
  2. 根节点永远是黑色的；
  3. 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
  4. 每个红色节点的两个子节点一定都是黑色；
    从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

  • 注意：
    性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。

    性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。
    因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。

    性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。

    红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。

红黑树的左旋右旋

我的头像

红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。

比如 X 左旋(右图转成左图)的结果，是让在 Y 左子树的黑色节点跑到 X 右子树去。

#红黑树的平衡插入
红黑树的插入主要分两步：

  1. 首先和二叉查找树的插入一样，查找、插入
  2. 然后调整结构，保证满足红黑树状态
  3. 对结点进行重新着色
  4. 以及对树进行相关的旋转操作
  5. 红黑树的插入在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作

插入后调整红黑树结构
红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。

同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。

因此我们需要在插入黑色节点后进行结构调整，保证红黑树始终满足这 5 条特征。

调整思想

前面说了，插入一个节点后要担心违反特征 4 和 5，数学里最常用的一个解题技巧就是把多个未知数化解成一个未知数。我们这里采用同样的技巧，把插入的节点直接染成红色，这样就不会影响特征 5，只要专心调整满足特征 4 就好了。这样比同时满足 4、5 要简单一些。

染成红色后，我们只要关心父节点是否为红，如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。

  • 注：插入后我们主要关注插入节点的父亲节点的位置，而父亲节点位于左子树或者右子树的操作是相对称的，这里我们只介绍一种，即插入位置的父亲节点为左子树。

红黑树的平衡删除

红黑树的插入平衡需要好好理解下，如果前面没有理解，删除后的调整平衡更加难懂，前方高能，请注意！

  • 红黑树的删除也是分两步：

    二叉查找树的删除
    结构调整
    二叉查找树的删除

发表于

矩阵传达了两种信息：

（1）静态信息
一个矩阵其实同时包含两个信息 :

  • 在哪个向量空间下描述事物，即坐标系信息，以及坐标值信息。

（2）动态信息
一个矩阵表示一种线性变换；

  • 矩阵的静态信息可以看作动态信息的矩阵经过变换后得来的。所以，一个矩阵可以拆分称几个矩阵相乘的形式。
  • 一个 $m*n$ 的矩阵，即可看作一个线性映射：将所给矩阵从 $m$ 维空间映射到 $n$ 维空间。

1.线性变换

【从动态信息角度理解】

【1】线性变换几何直观理解

例如 ：旋转、推移，伸缩：

  • 直线变换后仍是直线
  • 直线比例保持不变
  • 原点变换后仍是原点

【2】矩阵变换

注意相乘的顺序：

$$A_{线性变换后}=W \bullet A=线性变换\bullet原矩阵\tag{1}$$

矩阵变换实际上是“基的变换”，见式（3）（4）。

举例子，一个以原点为中心的正方形，基向量为 $i,j$ :
$$
\begin{bmatrix}
1 \\
0
\end{bmatrix} \
$$
\begin{bmatrix}
1 \\
0
\end{bmatrix}

然后逆时针旋转 $\theta$ ，即，旋转矩阵 $T_{rotate}=$
$$
\begin{bmatrix}
cos(\theta) & -sin(\theta) \\
sin(\theta) & cos(\theta)
\end{bmatrix} \tag{2}
$$
则基向量变为 $i’,j‘$ ：
$$
\begin{bmatrix}
cos(\theta) \\
sin(\theta)
\end{bmatrix} $$
$$
\begin{bmatrix}
-sin(\theta) \\
cos(\theta)
\end{bmatrix}
$$
也就是，旋转变换后的基向量就是旋转矩阵的列。————》列空间

用公式表述上述变化：
$$ A=a \bullet i+b \bullet j=[i,j] \bullet [a;b]=基\bullet坐标 \tag{3}$$

$$T_{rotate} \bullet A=T_{rotate} \bullet [i,j] \bullet [a;b]=[i’,j’] \bullet [a;b]=]A’ \tag{4}$$

$$A’=a \bullet i’+b \bullet j’\tag{5}$$

2.行列式

[1] 【从动态信息角度理解】

行列式的本质：行列式是线性变换的伸缩因子

看上述的旋转，旋转矩阵 $T_{rotate}$的行列式的值为：
$$
\begin{matrix}
cos(\theta) \bullet cos(\theta)-(sin(\theta) \bullet (-sin(\theta)))=1\
\end{matrix} \tag{5}
$$

即旋转变换后正方形的面积不变。

$$| 行列式 | > 1 , 对于图形有放大作用$$
$$| 行列式 |= 1 , 图形大小不变$$
$$0 < | 行列式 | < 1 , 对于图形有缩小作用 $$

[2] 【从静态信息角度理解/看成一个单纯的矩阵】

行列式值物理意义:

$$ 二阶矩阵A的行列式值 = 矩阵A的列组成的平行四边形的面积$$
$$三阶矩阵A的行列式值 = 矩阵A的列组成的平行六面体的体积$$

3.秩:

（将一个矩阵看作线性变换来思考）

秩 ：列空间的维度

数学家们定义，矩阵中的最大的不相关的向量的个数，就叫秩，即 列空间的维度。

  • 不在一条直线上的向量，即为不相关的向量。

  • 【秩 = 列秩 = 行秩】 是恒成立的。所以直接把「列秩」称为「秩」也不算错误

$$ 图像A——>秩为0的线性变换——>一个零维的点$$
$$图像A——>秩为1的线性变换——>一维直线$$
$$图像A——>秩为2的线性变换——>二维图像$$

所以,可以理解：

$没有线性变换矩阵可以将一个点还原为原来的图像，所以秩为0的矩阵没有逆矩阵，即 不可逆 。$

也就是：

$如果B经过线性变换P之后，得到结果M;但 M 无法经过线性变换还原为B,则称矩阵P不可逆$。

4.低秩的意义

形象地理解：

低秩表征一种冗余程度，秩越低表示数据冗余性越大，因为用很少几个基就可以表达所有数据了，也就是说，可以用 $rank(A)$ 个线性无关的特征向量通过线性组合，基本地还原图片$A$ 的信息。

一个矩阵是 low rank,说明它比它看起来更简单，矩阵信息量较低，实际坐标空间的维度就低，矩阵中大量内容线性相关，信息相关性高，则有规律，表示 $”可大幅压缩”$ ；

如果矩阵内容大量线性相关，则该矩阵可以等价位少数几个向量多次组合而来，对于机器学习而言，这种信息 $“易建模（我的通俗理解，容易学习出函数f）”$。

5.矩阵的特征值理解

此 视频 非常形象，这个系列的都很好。看完就懂啦！

矩阵乘法对应了一个变换，是把任意一个向量变成另一个方向或长度都大多不同的新向量。

在这个变换的过程中，原向量主要发生旋转、伸缩的变化。

如果矩阵对某一个向量或某些向量只发生伸缩变换，不对这些向量产生旋转的效果，那么这些向量就

称为这个矩阵的特征向量，伸缩的比例就是特征值。

6.奇异值的理解

【1】奇异值的物理意义

矩阵的奇异值是一个数学意义上的概念，一般由奇异值分解（即SVD分解，矩阵分解的一种）得到。

下面考虑二维矩阵 $A$（一张人脸图像，像素为 $450 \bullet 333$）。

将$A$进行奇异值分解，即分解为若干个秩一矩阵（秩为1的矩阵）之和：
$$
\begin{matrix}
A=\sigma_1u_1v_1^T+ \sigma_2u_2v_2^T+…+\sigma_ru_rv_r^T \
\end{matrix} \tag{6}
$$
其中等式右边每一项的系数 $\sigma$ 就是 奇异值 , $u$、$v$ 分别表示列向量，大小分别为 $4501$ 和 $3331$。注意，每一项 $uv^T$ 都是秩一矩阵。将奇异值大小顺序排列，假定式（6）是按奇异值大小顺序排列的。

  • 保留奇异值较大的几项（前几项），舍去奇异值较小的项（后几项），会得到和原图差别不大的图像。保留的项越多，结果和原图差距越小。对于含噪的，奇异值较小的项在很大概率上是噪点(在图像处理领域，应用于数据压缩和图像去噪)。

  • 一般情况下，存储一张图片，并不需要存储所有的项，所以可以达到节省存储空间的目的。

  • 假设保留前50项，结果已经很接近 $A$:$A$,$450 \bullet 333=149850$ ;
    前50项,$(450+333+1) \bullet 50 = 39200$，存储量仅为前者的 20% 。

  • 奇异值往往对应着矩阵中隐含的重要信息，且重要性和奇异值大小正相关。每个矩阵$A$都可以表示为一系列秩为 1 的“小矩阵”之和，而奇异值则衡量了这些“小矩阵”对于 $A$ 的权重。
    知乎郑宁的回答特别好。

【2】奇异值的几何意义

博客 讲得特别好。
未完待续

发表于

逆波兰表达式

  • [x] 表达式一般由操作数、运算符组成，例如算术表达式中，通常把运算符放在两个操作数的中间，这称为中缀表达式，如A+B。
    波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：

    • (1). 把运算符写在操作数之前，称为波兰表达式或前缀表达式，如+AB；
      • (2). 把运算符写在操作数之后，称为逆波兰表达式或后缀表达式，如AB+

  • [x] 将中缀表达式 转换成 后缀表达式算法/逆波兰表达式：
    1、从左至右扫描中缀表达式。
    2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
    3、若读取的是运算符
    (1) 该运算符为左括号”(“，则直接存入运算符堆栈。
    (2) 该运算符为右括号”)”，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
    (3) 该运算符为非括号运算符：

    (a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。

    4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

  • 逆波兰表达式求值算法：
    1
    逆波兰式中不存在括号

1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。

  • 例如 $$ a(b-cd)+e-f/g(h+ij-k)$$ 的逆波兰表达式为：
    $$ abcd-e+fg/hij+k-- $$

发表于

L0/L1/L2范数

DeepLearning

包含三部分：

  • 范数的应用
  • 范数的概念

  • [ ] 详解L1/L2范数的作用及原因

    范数的应用

    [1] 作为正则化中的惩罚项
    在机器学习中正则化是指在损失函数中通过引入一些额外的信息，来防止ill-posed问题或过拟合问题。一般这些额外的信息是用来对模型复杂度进行惩罚（Occam’s razor）。其一般形式如下：

便可以选取L1或是L2范数来作为惩罚项，不同的模型，其损失函数也不同，对于线性回归而言，如果惩罚项选择L1，则是我们所说的Lasso回归，而L2则是Ridge回归。

[2] 贝叶斯先验
正则化项从贝叶斯学习理论的角度来看，其相当于一种先验函数。即当你训练一个模型时，仅仅依靠当前的训练集数据是不够的，为了实现更好的预测（泛化）效果，我们还应该加上先验项。而L1则相当于设置一个Laplacean先验，去选择MAP（maximum a posteriori）假设。而L2则类似于 Gaussian先验。从图可以看出，L1先验对大值和小值的tolerate都很好，而L2先验则倾向于均匀化大值和小值。

如下图所示：

[3] 特征选择与稀疏编码
机器学习社区里通常把特征选择的方法分为三种。一种是基于统计学的一些方法，对特征进行预筛选，选出子集作为模型输入。如统计推理使用的假设检验，P值。另一种是采用某种成熟的学习算法进行特征选择，如决策树中采用信息增益来选择特征。还有一种便是在模型算法中进行自动特征选择。而L1范数作为正则化项，其特征选择的图谱倾向于spiky，实现了有效的特征选择。
稀疏编码也是想通过寻找尽可能少的特征表达某个输入的向量X。

其中 $ϕ^i$ 是所要寻找的基向量，$a_i^j$ 是我们要优化的各个基向量的权重。最右边的表达式便是其正则化惩罚项，在这里也称Sparse Cost。实际中我们通常便用L1范数。

范数的概念：

向量的范数可以简单形象的理解为向量的长度，或者向量到零点的距离，或者相应的两个点之间的距离。

向量的范数定义：向量的范数是一个函数||x||,满足非负性||x|| >= 0，齐次性||cx|| = |c| ||x|| ，三角不等式||x+y|| <= ||x|| + ||y||。

常用的向量的范数：

  • L1范数: ||x|| 为x向量各个元素绝对值之和;L0范数是指向量中非0的元素的个数。
    如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0。

  • L2范数: ||x||为x向量各个元素平方和的1/2次方，L2范数又称Euclidean范数或者Frobenius范数。
    改善机器学习里面一个非常重要的问题：过拟合,通过L2范数，我们可以实现了对模型空间的限制，从而在一定程度上避免了过拟合。

  • Lp范数: ||x||为x向量各个元素绝对值p次方和的1/p次方。

  • L∞范数: ||x||为x向量各个元素绝对值最大那个元素的绝对值，如下：

椭球向量范数: ||x||A = sqrt[T(x)Ax]， T(x)代表x的转置。定义矩阵C 为M个模式向量的协方差矩阵， 设C’是其逆矩阵，则Mahalanobis距离定义为||x||C’ = sqrt[T(x)C’x], 这是一个关于C’的椭球向量范数.下图给出了一个Lp球的形状随着P的减少的可视化图。

![](http://t.hengwei.me/assets/img/post/lp_ball.png)

详细解释L1/L2范数的作用及原因

参考 http://www.cnblogs.com/zf-blog/p/6522502.html

发表于

attention

深度学习算法

参考文章 FEED-FORWARD NETWORKS WITH ATTENTION CAN SOLVE SOME LONG-TERM MEMORY PROBLEMS中的注意力机制

我的头像

我的头像
注意力模型，以n个参数 $ y_1,…,y_n$作为输入，以及上下文向量$ c $，返回一个向量$ z$，这个向量是聚焦于上下文信息的情况下对于$yi$的概要表示。更正式的，它返回的是$yi$的加权算术平均，权重是基于每个$yi$跟上下文向量$ c $的相关程度来确定的。
注意力模型的一个有趣特性是，算术平均的权重是可以获取得到并且绘制出来的，前面例子的图就是这么处理得到的，如果图像某一部分对应的权重越大，那这部分图像中的像素点会越白。

注意力模型这个黑箱子里的细节如下图所示。

这个网络看起来有些复杂，我们将会一步一步地解释。
模型的输入是下图中没有被模糊遮盖的部分，包括上下文向量$ c $和一系列的个$yi$。
我的头像
接下来，模型使用一个tanh层计算得到$ m_1,…,m_n$。计算$ m_i$的输入包括上下文向量$ c $和对应的$yi$，也就是说每个$ m_i$的计算是相互独立的。

这里$ m_i$是向量。
接着，通过softmax计算得到每个权重。

$s_1$+…+$s_i$=1
这里，$ s_i$是$ m_i$的softmax结果在学习到的方向上的投影，是一个标量。
$ w_m$是所谓的学习到的方向，用以做内积
输出$ z$是所有$y_i$的算数加权平均，权重表示每个向量跟上下文向量的相关性。

发表于

Anaconda/pycharm 中python/Anaconda2.3共存安装

环境配置

我是先装的Anaconda3（也可以先安装Anaconda2哒）
俺是基于windowsX64
对于配环境的菜鸟，网上教程太凌乱，有的还有错，我摸爬滚打后总结如下：

  • [x] 在Anaconda3的基础上，安装Anaconda2.
    正常看心情决定Anaconda2的路径；
    如果失败，尝试Anaconda2的安装路径为：安装时浏览到Anaconda3/envs，然后在后边填写py2,就会将其安装到文件夹py2中。不用提前自己专门新建文件夹，否则会报错：路径存在。
    安装中去掉第二个选择界面。即 Advanced installtion option 界面中两个选项的 勾选 即可。一路安装。直接在开始菜单就可以打开使用。
    这样，你想用python3编写代码时，就打开python3的spyder；你想用python2编写代码时，就打开python2的spyder。两种环境的切换非常方便。

  • [x] 在Anaconda3的基础上，仅仅安装纯净的python2，也就是说没有其他包，需要的话还得重新下包。

  • 全程在cmd中操作
    在开始菜单栏中搜索cmd,并打开
    1）先在conda中创建一个名为python2的环境，并下载对应版本python2.7
    conda create –name python27 python=2.7
    2）激活python2环境
    activate python27
    3)在python2的环境下下载spyder和Jupter notebook
    conda install spyder
    因为我这里已经装过spyter了，如果第一次安装，系统会让你确定是否下载，输入 y 即可。
    4) 下面我们可以看到菜单栏已经有了python2的spyter了。
    5）下载Jupyter notebook，一样的方法。
    conda install jupyter

  • spyder(python27)使用方法

  • 打开cmd

输入 activate python27
输入 spyder
成功打开后就是spyder(python27)

  • spyder(python3.6)使用方法
    依旧可以从菜单中打开

接下来

接下来，我们看如何在pycharm当中添加python2和python3，以便于pycharm 当中，我们可以随意切换python3，python2 环境：
pycharm–file–setting–搜索Project Interpreter–设置按钮–add local–寻找Anaconda3\envs\py2\python.exe
添加 - OK- Apply- OK
到此结束,叽里呱啦弄完后，回头看觉得很简单~严肃欢快的学习吧~~~

发表于

关于版本控制-起步

其他折腾

【1】 关于版本控制
什么是版本控制？我为什么要关心它呢？版本控制是一种记录一个或若干文件内容变化，以便将来查阅特定版本 修订情况的系统。在本书所展示的例子中，我们仅对保存着软件源代码的文本文件作版本控制管理，但实际上， 你可以对任何类型的文件进行版本控制。
采用版本控制系统（VCS）是个明智的选择。有了它你就可以将某个文件回溯到之前的状态，甚至将整个项目都回退到过去某个时间点的状态。你可以比较文件的变化细节，查出最后是谁修改了哪个地方，从而找出导致怪异问题出现的原因，又是谁在何时报告了某个功能缺陷等等。使用版本控制系统通常还意味着，就算你乱来一气把整个项目中的文件改的改删的删，你也照样可以轻松恢复到原先的样子。但额外增加的工作量却微乎其微。

【2】 代码版本管理系统的历史
代码版本管理系统大致可以分为三个时代：
第一代：本地式 –> 第二代：客户端-服务器式 –> 第三代：分布式

  • 本地式:许多人习惯用复制整个项目目录的方式来保存不同的版本，或许还会改名加上备份时间以示区别。这么做唯一的好处就是简单。不过坏处也不少：有时候会混淆所在的工作目录，一旦弄错文件丢了数据就没法撤销恢复。为了解决这个问题，人们很久以前就开发了许多种本地版本控制系统，大多都是采用某种简单的数据库来记录文件的历次更新差异. [简单粗暴地说 就是自己在自己的电脑上管自己的东西]
  • 集中化的版本控制系统 (Centralized Version Control Systems，简称CVCS) 有一个单一的集中管理的服务器，保存所有文件的修订版本，而协同工作的人们都通过客户端连到这台服务器，取出最新的文件或者提交更新。显而易见的缺点是中央服务器的单点故障。如果宕机一小时，那么在这一小时内，谁都无法提交更新，也就无法协同工作。要是中央服务器的磁盘发生故障，碰巧没做备份，或者备份不够及时，就会有丢失数据的风险。 [只有中央服务器管理，一旦崩溃，完蛋。]

  • 分布式版本控制系统（ Distributed Version Control System，简称 DVCS ）
    在这类系统中，像 Git，Mercurial，Bazaar 以及 Darcs 等，客户端并不只提取最新版本的文件快照，而是把代码仓库完整地镜像下来。这么一来，任何一处协同工作用的服务器发生故障，事后都可以用任何一个镜像出来的本地仓库恢复。因为每一次的提取操作，实际上都是一次对代码仓库的完整备份。见下图：

    我的头像

发表于

#哈夫曼编码、前缀码

哈夫曼树

【每次合并两个最小的】

  • 以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，求其带权路径长度：
    构造方法是每次取最小的两个数， 合并成一个数， 然后循环这种做法， 直到只剩一个点为止。构造的树是
    我的头像

    所以带权路径长度是 （4+5）3+（6+7+8）2=69

    • 若为对句子中的字符编码，频率大的赋予大权重，左孩子可以编为0，右孩子为1
    • 例如:字符串”alibaba”的二进制哈夫曼编码有（13）位。
      根据字符出现频率构建的带权重二叉树确定每个字符编码的。首先我们统计“alibaba”各个字符出现频率：a-3，b-2，l-1，i-1。将a看为数字3，b=2,l=1,i=1,对四个数字{3，2，1，1}构建哈夫曼树，由出现的频率我们有以下哈夫曼二叉树：

    我的头像

对应每个字符编码为：

我的头像

最终“alibaba”整个字符串的编码为0 100 101 11 0 11 0。
所以字符串”alibaba”的二进制哈夫曼编码有：31+22+31+31=13位

前缀码

  • 前缀
    设a=b1b2…bn，bi∈{0,1}是一个0-1序列(符号串)。序列b= b1b2…bi (1 i n)称为a的前缀。
    例如,设a=010, 则, 0, 01 ,010都是a的前缀.
  • 前缀码
    • 设Q ={a1, a2, …, am}是一个0~1序列集合 .
    • 如果Q中没有一个序列是另一个序列的前缀 , 则称Q为前缀码.
    • 例如，{0,10,110}就是一个前缀码，而{0,10,101}就不是前缀码。

发表于

之前看到过这篇文章，介绍DMLC给keras增加了MXNet支持，但是当时的版本是keras1.2.2，现在最新的已经到了kera2，现在想使用最新的Keras和MXnet咋办，试了以下方法，亲测可行

测试环境
win10,Cuda9.0,cuDNNv7

步骤
首先删除本机现有的keras,一般默认在c://user/xxx文件下面
按照这个教程

mkdir keras
git clone https://github.com/deep-learning-tools/keras ./keras/
cd keras/

检查是否为keras2_mxnet_backend

git fetch
git checkout keras2_mxnet_backend
git pull

然后执行setup.py 安装keras

python setup.py install

接下来安装最新的MXNet

pip install mxnet-cu90

然后import一下 ，很奇怪我的还是tf的后端，进入.keras文件夹，把原来这样的json文件

{
"floatx": "float32",
"backend": "tensorflow",
"image_data_format": "channels_last",
"epsilon": 1e-07
}

改成

{
"floatx": "float32",
"backend": "mxnet",
"image_data_format": "channels_first",
"epsilon": 1e-07
}

就可以了

发表于

线索二叉树、二叉排序树

1，什么是线索二叉树？

2，为什么要建立线索二叉树？

3，如何将二叉树线索化？

4，线索二叉树的常见操作及实现思路？

一 、什么是线索二叉树

在有n个结点的二叉链表中必定存在n+1个空指针域，因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树被称为线索二叉树。

二、为什么要建立线索二叉树

有了二叉树不就足够了吗？那为什么还要弄个线索二叉树出来呢？

在原来的二叉链表中，查找结点的左，右孩子可以直接实现，可是如果要找该结点的前趋和后继结点呢？这就变得非常困难，所以为了实现这个常见的需求，我们要在每个结点中增加两个指针域来存放遍历时得到的前趋和后继结点，这样就可以通过该指针直接或间接访问其前趋和后继结点。

三，如何将二叉树线索化

按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。

下面是线索二叉树和线索二叉链表示意图，它可以帮助我们更好地理解线索二叉树。

我的头像

四，线索二叉树的常见操作及实现思路

1，二叉树线索化

实现思路：按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。
a). 若上次访问到的结点的右指针为空，则将当前访问到的结点地址填入，并置右标志域为 1
b). 若当前访问到的结点的左指针为空，则将上次访问到的结点地址填入，并置左标志域为 1

2，查找后继节点

实现思路：分两种情况，一，没有右孩子，直接获取。二，有右孩子，中序遍历查找右子树中序遍历的第一个节点即为当前节点的后继节点。

3，查找前驱节点

实现思路：同样也分两种情况，一，没有左孩子，依据线索直接获取。二，有左孩子，中序遍历左子树中往右链中第一个没有右孩子的节点即为前驱节点(左子树中序遍历的最后一个节点)

4，遍历

实现思路：以中序遍历为例，首先找到中序遍历的开始节点，然后利用线索依次查找后继节点即可。

1. 二叉排序树定义

二叉排序树(Binary Search Tree)是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：
⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

2. 二叉排序树的插入

  • 在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

  • 插入过程：

    • 若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；
    • 当非空时，将待插结点关键字S->key和树根关键字t->key进行比较：
      若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，
      若s->key> t->key,则插入到根的右子树中。
      而子树中的插入过程和在树中的插入过程相同，
      如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。(待插入的节点，从根节点开始，依次与现有节点比较)。