⑴ KNN算法-4-算法优化-KD树
KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作时，可以使用kd树对查询操作进行优化。
Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想象一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：
首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。
常规的k-d tree的构建过程为：
对于构建过程，有两个优化点：
例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：
如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。
如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：
kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。
如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。
首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。
以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。
接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。
以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。
遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。
举例：查询点（2.1,3.1）
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。
举例：查询点（2，4.5）
一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：
上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。
一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：
但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：
研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。
同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。
Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。
⑵ 如何用pso算法优化离散数据
聚类可以理解为根据你划定的半径取圈样本，圈出几类就是几类，半径大类就少，半径小类就多。中心选择可以随机选取，那就是无监督算法，现在有一种半监督算法，先用少量标记好的样本产生一些类别作为聚类中心，指导聚类的过程。可以使用kmeans和SVM结合
⑶ Hive 的Map-Rece Job执行太慢，有什么办法可以优化吗
1.jpg 优化可以从几个方面着手：1. 好的模型设计事半功倍。2. 解决数据倾斜问题。3. 减少job数。4. 设置旅态茄合理的map rece的task数，能有效提升性能。(比如，10w+级别的计算，用160个rece，那是相当的浪费，1个足够)。5. 自己动手写sql解决数据倾斜问题是个不错的选择。set hive.groupby.skewindata=true;这是通用的算法优化，但算法优化总是漠视业务，习惯性提供通用的解决方法。 Etl开发人员更了解业务，更了解数据，所以通过业务逻辑解决倾斜的方法往往更精确，更有效。6. 对count(distinct)采取漠视的方法，尤其数据大的时候很容易产生倾斜问题，不抱侥幸心理。自己动手，丰衣足食。7. 对小文件进行合并，是行至有效的提高调度效率的方拆察法，假如我们的作业设置合理的文件数，对云梯的整体调度效率也会产生积极的影响。8. 优化时把握整闭凯体，单个作业最优不如整体最优。
⑷ 数据归一化会降低数据集大小吗
数据归一化方法的本质是一种对数据进行线性转换的方法，通过构建一种样本空间之间的线性映射关系来进行数据数值的转化，这种转化并不会影响数据分布，即不会影响数据的内在规律，只是对数据的数值进行调整。数据归一化有很多方法，并且在机器学习领域有诸多用途，不仅是能够作为梯度下降的优化算法，同时还能帮助一些数据集避免量纲不一致等问题。
经典机器学习领域的数据归一化算法主要有两种，分别是0-1标准化（Max-Min Normalization）和Z-Score标准化。我们先讨论归一化基本流程，再探讨归一化对机器学习算法在各方面的影响。
关于归一化和标准化的概念辨析
一般来说，归一化和标准化都是指对数据进行数值转化，根据维基网络的解释，都是Feature scaling(特征缩放)的方法，并且都可以称为normalization。但某些场景下也会有不同的称呼，例如将0-1标准化称为normalization，也就是归一化散冲，而把Z-Score标准化称为Standardization，即标准化。课上对二者概念不做具体区分。
1.数据归一化计算公式
1.1 0-1标准化
0-1标准化是最简单同时也是最常用的标准化方法。该方法通过在输入特征中逐列遍历其中里的每一个数据，将Max和Min的记录下来，并通过Max-Min作为基数（即Min=0，Max=1）进行数据的归一化处理，基本公式为：
𝑥𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛=𝑥−𝑀𝑖𝑛𝑀𝑎𝑥−𝑀𝑖𝑛
x
n
o
r
m
a
l
i
z
a
t
i
o
n
=
x
−
M
i
n
M
a
x
−
M
i
n
实际计算过程中需要逐列进行处理，即用每一列中的元素减去当前列的最小值，再除以该列的极差。
1.2 Z-Score标准化
和0-1标准化不同，Z-score标准化利用原始数据的均值（mean）和标准差（standard deviation）进行数据的标准化。同样是逐列进行操作，每一条数据都减去当前列的均值再除以当前列的标准差，在这种标准化操作下，如果原数据服从正态分布，处理之后的数据服从标准正态分布。Z-Score标准化计算公式如下：
𝑥𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛=𝑥−𝜇𝜎
x
n
o
r
m
a
l
i
z
a
t
i
o
n
=
x
−
μ
σ
其中𝜇
μ
代表均值，𝜎
σ
代表标准差。
和0-1标准化不同，Z-Score标准化并不会将数据放缩在0-1之间，而是均匀地分布在0的两侧。类似这种数据也被称为Zero-Centered Data，在深度学习领域有重要应用。
一种更加严谨的做法，是在分母项、也就是标准差上加上一个非常小的常数𝜇
μ
，从而使得分母恒大于0。
1.3 非线性标准化
除了0-1标准化和Z-Score标准化外，还有一类使用非线性函数进行归一化操作的方法。其中最具代表性的是Sigmoid标准化。
Sigmoid标准化其实非常好理解，就是利用Sigmoid函数对数据集的每一列进行处理，由于Sigmoid函数特性，处理之后的数据也将被压缩到0-1之间。
当然，相比Sigmoid标准化，Z-Score标准化实际用途更广。
2.数据归一化算法执行过程
我们以0-1标准化为例，来探讨数据归一化处理对量纲的影响以及在实际建模过程冲伏歼中的计算流程。当然其他标准化也类似。
对于0-1标准化来说，表面上看起来只是将每一列数据都放缩至0-1区间内，但实际上却有着非常多的用途。一个最简单的使用场景是，当数据集中不同列的量纲不一致时，通过对每一列的0-1标准化处理，能够消除因为这种不一致而引发的算法学习偏差。例如，在鸢尾花数据中，每一列都是以厘米作为单位，整体数据分布相对统一，但如果把其中某一列改为毫米、而其他几列改为米作为单位，则以毫米为单位的列数值将特别大，而其他几列数值将特别小，如此一来就会对包括线性方程在内的一系列模型建模造成重大影响，模型将无法“均匀的”从各列中提取信息。
数据的真实规律是第一个特征其实对标签的取值起到非常重大的作用，厅中但在实际数据获取记录过程中，如果量纲错配，即给了第一个特征一个非常大的量纲、第二个特征一个非常小的量纲，那么数据情况和实际建模情况就将产生较大误差。
此时模型为了捕捉第一列相对更加重要的特性，计算所得的第一列特征取值非常大，甚至是第二列特征系数的10的5次方倍左右。尽管上述模型结果仍然是可以使用的结果，但特征系数差异性的增加（由200倍变成20000倍差异）会导致两个问题，其一是部分系数太小而导致计算精度问题，其二则是在特征重要性判别上会忽视系数较小的特征。而为了能够消除这种量纲差异所带来的规律挖掘方面的影响，我们就需要采用归一化方法。
注意，关于标签是否需要归一化的问题，一般来说这并不是一个典型的操作，在绝大多数情况下我们也并不会对标签进行归一化操作。但此处，由于需要在归一化后全都为正数的特征上进行回归类问题预测，且标签取值有正有负，因此可以考虑对标签进行归一化处理，以方便观测后续模型参数。不过尽管如此，此处的标签归一化也并不是必须的。
当然，如果是划分训练集和测试集进行建模并且进行归一化操作，那么在遵循“在训练集上训练，在测试集上进行测试”的基本原则下，我们首先在训练集上进行数据归一化处理并记录各列的极值，然后当模型训练完成之后，再借助训练集各列的极值来对测试机数据进行归一化，再带入模型进行测试。当然，如果这个过程对标签也进行了归一化处理，则标签的归一化过程和特征归一化过程无异，唯一需要注意的是如果是对未知数据进行预测，即需要模型输出和真实采集到数据类似的结果，则需要在模型输出的归一化的标签基础上进行逆向归一化处理。
此外，一般来说如果是Z-Score标准化，则无需对标签进行标准化处理。
3.数据归一化算法评价
此处我们通过量纲不一致问题引出归一化方法，但归一化方法却并不一定、且不仅仅应用于处理量纲不一致问题中。
首先，并非所有模型都受到数据各列的绝对数值大小影响，在通用的模型中，线性模型和距离类模型是两类典型的会受到各列绝对数值大小影响的模型，例如线性回归、KNN、K-Means（一种无监督的聚类模型）等，并且逻辑回归在使用ECOC编码进行类别判别时也是利用距离来判别样本最终归属，此时，由于各列的绝对数值会影响模型学习的偏重，模型会更加侧重于学习那些数值比较大的列，而无法“均匀”的从各列中提取有效信息，因此有时会出现较差的模型结果。但有些模型却不受此影响，典型的如树模型。
辩证的看，“均匀”的从各列提取有效信息其实也并不一定是最好的做法，本身对于有监督学习算法来说，大多数数据集各列的重要性就不是等价的。但是，比起无法“均匀”的从各列提取有效信息，更可怕的是我们会不受控制的“不均匀”的去提取有效信息，这也是归一化要解决的核心问题。
其次，我们需要知道，一旦对数据进行归一化处理，数据就将失去可解释性，也就是失去了量纲。例如对于鸢尾花数据来说，原始数据代表花瓣花萼的长宽测量结果，而如果我们对其进行归一化处理，则每条数据就无法再给予明确的现实意义，这也是在很多要求可解释性的情况下我们应该避免使用归一化方法的原因。
不仅是归一化方法，其实所有的样本空间的映射都会改变数据集的可解释性。
其三，归一化方法属于仿射变换的一种特殊形式，而所有的仿射变换其实都不会影响数据集原始分布，也就是并不影响数据集真实规律，只会影响某些算法挖掘规律的难度（也就是受到特征绝对数值影响的算法）。例如对如下数据，我们可以观察其归一化前后的数据分布变化情况：
仿射变换指的是样本空间平移（加减某个数）和放缩（乘除某个数）的变换。0-1标准化过程中，平移就是减去每一列最小值，放缩就是除以某一列的极差。
最后，也是最重要的一点，那就是对于梯度下降算法来说，归一化能够提高收敛速度，例如下图所示，经过归一化处理之后的数据，在进行损失函数构造时损失函数的等高线图将更加均匀，此时梯度下降的收敛速度也将更快，具体理论理解详见下文论述，而在实际使用过程中，经过归一化的数据在梯度下降过程中往往收敛更快，这其实是相比消除量纲影响，归一化方法更加重要应用场景。
在提高收敛速度方面，Z-Score效果要好于0-1标准化。
关于归一化能够让等高线更加均匀从而加快迭代收敛过程的理解：
从理论角度出发，其实梯度下降过程每一步参数点移动的方向是能够让梯度最快速下降的方向，也就是图片上垂直于等高线的方向。但这种所谓的最快速的方向只在开始移动的一瞬间满足，由于梯度是连续变化的函数，因此当移动了一小步之后“最优方向”其实就可能发生了变化，但参数只能在下次移动时再改变方向，因此中间其实很长一段距离参数并不不一定是沿着最优方向在进行移动。这里需要注意，如果下一次移动的方向和上一次移动方向一致或者类似，那就说明这次移动过程中参数并没有偏离方向太多，反之则这次移动走了很多弯路。而当损失函数的等高线是均匀分布时，外圈的垂直线也就是内圈的垂直线，此时参数两次移动过程大概率最优方向一致，也就是说相同的移动能够更大程度降低损失函数值，而如果类似图1中的情况，内外圈分布不均匀，则参数两次迭代过程最优方向将发生偏移，也就是说明上一次迭代过程有很长一段距离没有沿着最优方向迭代，该次迭代只降低了有限的损失函数计算值。经次过程不断迭代，由于经过归一化的损失函数每次迭代效率都更高，因此相比其他损失函数，经过归一化的数据只需要更少次的迭代就能抵达最小值点，这也就是加快收敛速度的根本原因。
另外需要注意的是，收敛更快往往也意味着能够收敛至更靠近全局最小值的点。
4.Z-Score标准化算法评价及横向对比
从大类上来分，Z-Score的使用场景要远高于0-1标准化使用场景。当然这也并不是绝对的，要区分二者使用情景，我们首先需要进一步了解二者算法性能。
生成Zero-Centered Data
一般来说，由于Z-Score标准化生成数据的Zero-Centered特性，使得其在深度学习领域倍受欢迎（是Batch Normalization的一种特殊情况）。而在机器学习领域对于标签同时存在正负值的回归类问题，使用Z-Score能够避免对标签进行归一化。
标准正态分布
由于该方法同时也是正态分布转换为标准正态分布的计算公式，因此如果原始数据满足正态分布，则经过Z-Score转化之后就能转化为标准正态分布，进而可以利用标准正态分布诸多统计性质。
保留极端值分布
还有一点非常实用的功能，就是相比0-1标准化，Z-Score标准化能够保留极端值的分布。
由于极端值的存在，会将其他数值压缩在一个非常小的范围内。而如果此时我们采用Z-Score进行标准化，极端值仍然还是极端值（相对该列其他数值而言），此时我们即可采用极端值处理方法对其进行处理（删除或者盖帽（默认凡小于百分之1分位数和大于百分之99分位数的值将会被百分之1分位数和百分之99分位数替代））。
二、梯度下降算法优化初阶
归一化和学习率调度，是梯度下降算法优化的基本方法。
1.数据归一化与梯度下降算法优化
接下来，我们讨论归一化与梯度下降之间的关系。此前我们通过简单例子观察了数据归一化对梯度下降的影响——即归一化能够改变损失函数形态，而这种改变将显着加快梯度下降的迭代收敛过程，直观判断是归一化之后的损失函数等高线图更加均匀。本小节我们将从梯度下降算法优化角度出发，讨论数据归一化和梯度下降之间的关系。
在机器学习模型优化体系中，构建损失函数和损失函数求解是模型优化的两大核心命题，通过损失函数的构建和求解，就能够找到模型最优参数。但对于很多复杂模型来说，损失函数构建和求解并非易事，而梯度下降作为损失函数求解的重要方法，如何优化梯度下降求解过程，使其能够“又快又好”的找到最小值点，就成了决定建模成败的核心因素。当然，从梯度下降到随机梯度下降再到小批量梯度下降，我们可以理解其为算法层面上的优化，但除此以外还有许多围绕优化梯度下降求解过程的算法和方法，例如本节介绍的归一化和学习率调度方法。
当然，优化方法的学习也需要遵循循序渐进的过程，本节我们仍然还是在线性回归损失函数、也就是凸函数上进行基本优化思路的介绍和基本优化方法的学习，围绕现线性回归的凸函数损失函数求解，其实是可以使用最小二乘法一步到位求出数值解的，但也正是因为其最优解明确存在，也就给了我们进行对照实验的基础。我们将利用梯度下降算法，在更加复杂的数据集上，探索如何使用优化方法，来逼近明确存在的全域最小值点，并在这个过程中深化对优化方法的理解，进而能够在后续更加复杂的损失函数上、甚至是非凸的损失函数上，凭借我们的理解和所掌握的工具，用好最小二乘法这把利器进行更快更好的最优参数的求解。
为何在相同学习率下，在归一化之后的数据集上进行梯度下降，却更加接近全域最小值点，这又是什么原因呢？回顾此前我们所讨论的归一化对损失函数的影响，从等高线图上来看是等高线变得更加均匀，但实际上是整个损失函数在不同区域对应梯度都更加均匀，从而在靠近最小值点附近的梯度也比归一化之前的损失函数梯度要大，也就是说，虽然学习率相同，但由于归一化之后最小值点附近梯度要更大，因此同样的迭代次，在归一化之后的损失函数上参数点将移动至更加靠近最小值地附近的点。
我们可以通过不断尝试，直到“测出”最佳学习率为止。当然，在Scikit-Learn中其实也提供了这种类似枚举去找出最佳超参数取值的方法，但如果是面对超大规模数据集的建模，受到计算资源的限制，我们其实是无法反复建模来找到最优学习率的，此时就需要采用一种更加先进的计算流程来解决这个问题。
2.学习率调度
基本概念
其实梯度下降优化的核心目标就是希望“更快更好”的找到最小值点，归一化是通过修改损失函数来达成这个目标，而所谓学习率调度，则是通过调整学习率来达到这个目标。值得注意的是，此时找到一个确定的最优学习率并不是目标，“更快更好”找到最小值点才是目标，因此我们完全可以考虑在迭代过程动态调整学习率。而所谓学习率调度，也并不是一个寻找最佳学习率的方法，而是一种伴随迭代进行、不断调整学习率的策略。
学习率调度方法有很多种，目前流行的也达数十种之多，而其中一种最为通用的学习率调度方法是学习率衰减法，指的是在迭代开始时设置较大学习率，而伴随着迭代进行不断减小学习率。通过这样的学习率设置，能够让梯度下降收敛速度更快、效果更好。
实践过程
例如在上述例子中，我们不妨设置这样的减速衰减的一个学习调度策略，衰减过程比例由如下函数计算得出：
lr_lambda = lambda epoch: 0.95 ** epoch
即假设初始学习率为0.5，则第一次迭代时实际学习率为0.5*1，第二轮迭代时学习率为0.5*0.95，以此类推。据此，我们可以优化梯度下降迭代过程。
算法评价
接下来，简单总结学习率调度的使用场景和注意事项。
首先，在很多海量数据处理场景下，学习率调度的重大价值在于能够提供对学习率超参数设置更大的容错空间。在很多情况下，搜索出一个最佳学习率取值进而设置恒定学习率进行梯度下降，难度会远高于设置一组学习率衰减的参数。并且有的时候，刚开始学习率设置过大其实也可以通过多轮迭代进行调整，其所消耗的算力也远低于反复训练模型寻找最佳恒定学习率。
其次，尽管上述例子我们是在梯度下降中使用学习率衰减这一调度策略，但实际上更为一般的情况是学习率调度和小批量梯度下降或者随机梯度下降来配合使用。一般来说梯度下降的使用场景在于小规模数据集且损失函数较为简单的情况，此时可利用梯度下降+枚举找到最佳学习率的策略进行模型训练，其相关操作的技术门槛相对较低（枚举法可借助Scikit-Learn的网格搜索）；而对于更大规模的数据集且损失函数情况更加复杂时，则需要考虑小批量梯度下降+学习率调度方法来进行梯度下降求解损失函数。
当然，除了学习率衰减外还有很多学习率调度策略，甚至有些学习率调度策略会间接性提高和降低学习率，来帮助梯度下降找到最小值点。
3.梯度下降组合优化策略
无论是数据归一化、学习率调度还是采用小批量梯度下降，这些方法并不互斥，我们完全可以组合进行使用，达到组合优化的目的。
⑸ 梯度下降算法中的优化途径
特征缩放还可以使机器学习算法工作的更好。
比如在K近邻算法中，分类器主要是计算两点之间的欧几里得距离，如果一个特征比其它的特征有更大的范围值，那么距离将会被这个特征值所主导。
在梯度下降法中，当某个特征值较颤圆大的时候会出现类似于 图一 的代价函数轮廓图：
这样的情况下，梯度下降的过程中会来回震荡，使得需要更多次的迭代才能到达局部最优点。
而如果对特征进行缩放（Feature Scaling）那么，迭代过程就可以像 图二 一样，更为快速的收敛。
因此每个特征应该被归一化，比如将取值范围处理为0到1之间。
这种方法是将数据的特征缩放到[0,1]或[-1,1]之间。缩放到游岩什么范围取决于数据的性质。对于这种方法的公式如下：
0均值归一化方法将原始数据集归一化为均茄磨塌值为0、方差1的数据集
公式如下：
其中max为样本数据的最大值，min为样本数据的最小值。这种方法有个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义。
S = Xmax - Xmin
⑹ 总数一定优化分配用什么算法
梯度下降法。
梯度下降法就是实现该“学习”过程的一种最常见的方式，尤其是在深度学习 (神经网络)模型中，BP反向传播方法的核心就是对每层的权重参数不断使用梯度下降来进行优化。. 梯度下降法 (gradient descent)是一种常用的一阶 (first-order)优化方法，是求解无约束优化问题最简单、最亏戚经典的方法之一。我们来考虑一个无约束优化问题 , 其中 为连续可微函数，如果我们能够构造一个序列 ，并能够满足。
梯度下降法销帆陵（英语：Gradient descent）是一个一阶最优化算法。 要使用梯轿滚度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点；这个过程则被称为梯度上升法。
⑺ 求能够优化此类计算速度的算法
左边数据放在这誉则里：
ListLeft.add(String[A][100],String[B][200]，...)
右边数据放在这里：
HashMap.put("A","100")
HashMap.put("B","800")
然后遍历ListLeft,if(HashMap.cantain(String[A]){相加并放入第液斗三个List;HashMap.remove(String[A]);}else{直接放入第三个List},遍历完后HashMap中剩庆埋棚下的都是ListLeft没有的，全放入第三个List
只是初步设想，不知道会不会快
⑻ 数据结构和算法优化
APP的优化是任重而道远的过程，必须在意每一个环节，否者当你想要优化的时候，发现到处都是坑，已经不知道填补哪里了，所以我们必须一点一滴的做起。
数据结构和算法优化
能带来什么好处呢？他能使得你程序获得数据更快，内存占用更合理。最终体现为响应快内存占用小。
我们先看常见的数据结构类型特点
数组 ： 一片物理上连续的大小确定的储存空间 。int[num]
顺序表 ：物理上连续、逻辑上连续、大小可以动态增加。ArrayList （查找快，添加删除慢）
链表 ：物理上不连续、逻辑上连续、可以动态增加和删除节点。LinkedList （查找慢只能轮寻，增加删除快）
物理上连续：数组或者链表在初始化的时候，会申请分配内存空间：只要存储空间足够你申请的大小就分配给你初始化（物理不连续）；必须要连续的存储空间，我才给你分配，否则失败（物理上连续）
那么有没有继承纯虚标和链表的2个有点的数据结构呢？HashMap！
HashMap
它是由数组和链表结合组成。（HashMap：JDK1.7之前 24 之前： 数组+ 链表； HashMap：JDK1.8 之后： 数组+ 链表 + 红黑树）
下面是HashMap结构图
它是怎么操作的呢？为什么他能同时拥有顺序表和链表的优点呢？ 搞清它的实现方式，我们就可以知道了， 大致可以分为以下的步骤。
①put方法，传入object和value，通过hash运算得到一个int类型的hashcode，这里假设为X（后续X为这个hashcode）。
②hashmap内部是有一个table数组+链表形成的。我们拿到这个X后，使用X/table.length(hashcode值/table[].length),得到一个小于table.length的值M，该值就是这个value应该放置的数组位置。我们准备把value放入table[M]中。
③我们把hashcode和value打包为一个node节点(为什么需要这么打包后续会提到),准备存入table[M]中。
④出入table数组的链表中有2种方式：
前插方式：不管数组table[M]节点有值与否，都把这个准备插入的node节点作为数组的根节点。可能出现2种情况：
（1）如果table[M]节点没有值，则node节点作为数组的根节点。
（2）如果table[M]节点已存在数据链表，就把这些数据灶含链表，链到这个准备插入的node节点上，以弄得节点为根节点放入table[M中]。
后插方式：可能会出现的2种情况
码清 (1) 如果table[M]节点没有值，则node节点作为数组的根节点。
（2）如果table[M]节点已存在数据链表，则把node节点链到该数据链表的最后一个节点上。
经历以上4个步骤就完成了hashmap的插入操作，现在解释一下为什么要打包为node节点。
举个栗子，假如hashmap.length=16,我们准备存入ObjectA(OA)和ObjectB(OB),假设OA经过hash运算得到的hashcode是1，OB经过hash运算得到hashcode是17，OA和OB进行求模运算结果都为1，链到链表上时，我们get方法的时候怎么取到正确的值呢，因为链表上的模运算都是1.这个时候我们就需要通过hashcode来识别这个链表上隐模笑的哪个值是OA的value哪个是OB的value，因为我们已经把hashcode和value打包起来了。
补充
hashmap的table数组的大小事是2的次幂（不要问为什么，源码定的，他们肯定经过大量的统计或者运算，这是科学）。table数组默认的长度是16，也就是说你new一个空的hashmap长度为16，当然也提供了一个给你设置长度的方法，但是假如你设置17，则长度会为32，这不难理解。
hash碰撞
hash碰撞就是，假如OA、OB...ON经过模运算得到的数组位置相同，那么他们都会挂在这个数组节点的链表上，极端情况想整个hashmap看起来像单链表。但这种情况这并不是我们想要的结果。我们可以通过扩容来尽可能的避免hash碰撞。
扩容 ：（意义，在于避免大量的hash碰撞，因为在某些极端情况下，有点像单链表）
阈值 ：阈值=table.length* DEFAULT_LOAD_FACTOR （扩容系数，默认为0.75，也可以自己设定，一般不做修改）
hashmap定义：当hashmap中的元素个数超过阈值大小时，我们就需要对table数组进行2倍扩容，如从16→32。
注意：扩容后hashmap会调用resize()，对hashmap内的数据重新计算所有元素的位置 。 。因为假如你之前17/16=1，现在17/32=17，你的位置发生变化了。
缺点 ：
hashMap因为有阈值的扩容机制，所以一定会有空间浪费，比如0.75的时候，一定有25%空间被浪费掉了。空间换时间。
hashmap是线程不安全的。因为可能在一个线程扩容（resize（）方法执行）的情况下,另外一个线程在get，但是拿不到之前的数据了，因为扩容。所以是线程不安全的。或者线程扩容（resize（）方法执行时，多线程进行put的时候导致的多线程数据不一致。
如何线程安全的使用HashMap?使用使用锁分段技术或者使用HashTable(Hashtable的方法是Synchronize的，而HashMap不是,其实也就是锁机制起作用)。
SparseArray（Android为了优化内存所提供的api）
特性：key为int,value为object，二分查找的思想，双数组，删除的时候节点不删除，而是把value删除，避免删除的时候数组还要移动。
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示。
为什么是能够进行二分查找呢？从源码上看key和value分别是用int类型数组和object数组表示，所以这也是SparseArray的局限性。
private int[] mKeys;
private Object[] mValues;
为什么说SparseArray比HashMap更省内存，在某些条件下性能更好？
因为SparseArray有以下一个特性，首先它是2个数组，在数据查找的时候无疑会比hashmap快很多，其次在删除的时候，SparseArray并不会把数组key位置进行删除，而是把key的索引value置位DELETE标志（这样就避免了数组delete操作后的array的操作）。当我们下次进行插入的时候，若要插入的位置key的索引value为DELETE标志，则把数据覆盖给value（只是经历了set操作，并无其他操作）。否则进行add操作（包含array）。
所以经过以上的情况，我们可以看出，SparseArray相对于HashMap,会越用越快。
缺点
（1）SparseArray仅仅能存储key为int类型的数据。
（2）插入操作需要复制数组，增删效率降低 数据量巨大时，复制数组成本巨大，gc()成本也巨大。
（3）数据量巨大时，查询效率也会明显下降。
（4）线程不安全问题，类似hashmap
一般我们在满足下面两个条件我们可以使用SparseArray代替HashMap：
（1）数据量不大，最好在千级以内
（2）key必须为int类型，这中情况下的HashMap可以用SparseArray代替：
ArrayMap（Android为了优化内存所提供的api）
ArrayMap和SparseArray差不多，不同的是key类型可以是object类型。
ArrayMap的2个数组，一个数组记录key的hash值，另外一个数组记录Value值。其他存储方式和运行思想和SparseArray一致。
线程不安全:hashmap、ArrayMap、SparseArray
⑼ 基于标记数据学习降低误报率的算法优化
基于标记数据学习降低误报率的算法优化
无论是基于规则匹配的策略，还是基于复杂的安全分析模型，安全设备产生的告警都存在大量误报，这是一个相当普遍的问题。其中一个码银重要的原因是每个客户的应用场景和数据都多多少少有不同的差异，基于固定判断规则对有统计涨落的数据进行僵化的判断，很容易出现误判。
在没有持续人工干预和手动优化的情况下，策略和模型的误报率不会随着数据的积累而有所改进。也就是说安全分析人员通过对告警打标签的方式，可以将专业经验传授给智能算法，自动得反馈到策略和模型当中，使之对安全事件做出更精准的判断。本文介绍利用专家经验持续优化机器学习的方法，对告警数据进行二次分析和学习，从而显着地降低安全威胁告警的误报率。
为了降低误报率，当前大体上有两种技术途径：
根据不同客户的各种特定情况修正策略和模型，提高策略或者模型的适应能力;
定期(如每月一次)对告警进入二次人工分析，根据分析结果来调整策略和模型的参数配置。
这两种方法对降低误报率都有一定的作用。但是第一种没有自适应能力，是否有效果要看实际情况。第二种效果会好一些，但是非常耗时耗力，而且由于是人工现场干预和调整策略和模型，出错的概率也非常高。
MIT的研究人员[1] 介绍了一种将安全分析人员标记后的告警日志作为训练数据集，令机器学习算法学习专家经验，使分析算法持续得到优化，实现自动识别误报告警睁模厅，降低误报率的方法(以下简称“标签传递经验方法”)。这种把安全分析人员的专业悉隐智能转化成算法分析能力的过程，会让分析算法随着数据的积累而更加精确。继而逐渐摆脱人工干预，提高运维效率。如下图所示：
下面我们通过基于“频繁访问安全威胁告警”模拟的场景数据来介绍一下实现机制。
什么是频繁访问模型?逻辑比较简单：一段时间内(比如1分钟)，一个攻击者对系统的访问次数显着高于普通访问者的次数。此告警规则可以用简单的基于阈值，或者是利用统计分布的离异概率。基于此，我们先模拟一些已经被安全分析人员打过标签的告警数据。根据实际应用经验，我们尽量模拟非常接近实际场景的数据。如下图：
关于模拟数据的介绍：
总共模拟了20天的告警数据，从2017-01-01到2017-01-20。前10天的数据用来训练模型，后10天的数据用来衡量模型的表现;
每个告警带有是否误报的标签。红色代表误报，蓝色代表准确告警。
关于模拟数据的假设：
误报聚集在某个时间段，模拟数据假设的范围是18:00-19:00。在安全运维实践中，的确存在某个特定的时间段，由于业务逻辑或者系统原因导致误报增多的现象。所以上述假设是合理的，告警时间可以作为有效的特征值。但并不是所有的误报都聚集在这个时间段，同时并不是这个时间段的所有告警都是误报;
误报大多来自于一批不同的IP。所以访问来源IP也是有用的特征值;
任何数据都不是完美的，所以在模拟数据中加入了~9%的噪音。也就是说再完美的智能模型，误报率也不会低于9%。
这些假设在实际的应用场景中也是相对合理的。如果误报是完全随机产生的，那么再智能的模型也不能够捕捉到误报的提出信号。所以这些合理的假设帮助我们模拟真实的数据，并且验证我们的机器学习模型。
简要模拟数据的代码实现：
下图显示利用PCA降维分析的可视化结果，可以看到明显的分类情况：
红色代表误报，蓝色代表正确告警。基于设定特征值的降维分析可以得到两个聚集，即误报和非误报有明显的区分的，也就是说误报的是有一定规律，不是完全随机的，因此是可以被机器学习捕捉到的。
简要代码实现：
基于模拟数据，我们想要达到的目的是通过持续的强化机器学习能够降低误报率。所以我们采取的策略是：
训练一天的数据2017-01-01，测试10天的数据2017-01-11到2017-01-20;
训练两天的数据2017-01-01到2017-01-02，测试10天的数据2017-01-11到2017-01-20;
以此类推，来看通过学习越来越多的数据，在测试数据中的误报率是否能够得到不断的改进。
简要代码如下：
此安全威胁场景相对简单，我们不需要太多的特征值和海量的数据，所以机器学习模型选择了随机森林(RandomForest)，我们也尝试了其他复杂模型，得出的效果区别不大。测试结果如下：
达到我们所预期的效果，当训练数据越来越多的时候，测试数据当中的误报率从20%多降低到了10%。通过对告警数据和标签的不断自学习，可以剔除很多告警误报。前面提到，数据当中引入了9%的噪音，所以误报率不会再持续的降低。
在我们的机器学习模型当中，我们利用了4个主要的特征值：
srcIP，访问源IP
timeofday，告警产生的时间
visits，访问次数
destIP，被访问IP
下图显示了特征值在模型中的重要性：
和我们的预期也是一致的，访问源IP(srcIP)和告警发生的时间(timeofday)是区分出误报告警效果最好的特征值。
另外，由于随机森林模型以及大部分机器学习模型都不支持分类变量(categoricalvariable)的学习，所以我们把srcIP和destIP这两个特征值做了二值化处理。简要代码如下：
总结
本文通过一组模拟实验数据和随机森林算法，从理论上验证了“标签传递经验方法”的有效性。即通过安全分析专家对告警日志进行有效或误报的标记，把专家的知识技能转化成机器学习模型的分析能力。和其他方法相比，此方法在完成自动化学习之后就不再需要人工干预，而且会随着数据的积累对误报的剔除会更加精确。
⑽ 几种常用最优化方法
学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解，比如我们现在学习的机器学习算法，大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的优化方法(optimization)有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。
1. 梯度下降法（Gradient Descent）
梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。
梯度下降 法的缺点：
（1）靠近极小值时收敛速度减慢;
（2）直线搜索时可能会产生一些问题；
（3）可能会“之字形”地下降。
在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。
比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J( )为损失函数， 是参数，要迭代求解的值，求解出来了那最终要拟合的函数h( )就出来了。其中m是训练集的样本个数，n是特征的个数。
1）批量梯度下降法（Batch Gradient Descent，BGD）
（1）将J( )对 求偏导，得到每个theta对应的的梯度：
(2）由于是要最小化风险函数，所以按每个参数 的梯度负方向，来更新每个 ：
（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。
对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。
2）随机梯度下降（Stochastic Gradient Descent，SGD）
（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
（2）每个样本的损失函数，对 求偏导得到对应梯度，来更新 ：
（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将
迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。 两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
对批量梯度下降法和随机梯度下降法的总结：
批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）
1）牛顿法（Newton's method）
牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 f ( x )的泰勒级数的前面几项来寻找方程 f ( x ) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
具体步骤：
首先，选择一个接近函数 f ( x )零点的x0，计算相应的 f ( x 0)和切线斜率 f ' ( x 0)（这里 f ' 表示函数 f 的导数）。然后我们计算穿过点( x 0, f ( x 0))并且斜率为 f '( x 0)的直线和 x 轴的交点的 x 坐标，也就是求如下方程的解：
我们将新求得的点的 x 坐标命名为 x 1，通常 x 1会比 x 0更接近方程 f ( x ) = 0的解。因此我们现在可以利用 x 1开始下一轮迭代。迭代公式可化简为如下所示：
已经证明，如果 f '是连续的，并且待求的零点 x 是孤立的，那么在零点 x 周围存在一个区域，只要初始值 x 0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果 f ' ( x )不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。
关于牛顿法和梯度下降法的效率对比：
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
牛顿法的优缺点总结：
优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
2）拟牛顿法（Quasi-Newton Methods）
拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。
拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。 拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
具体步骤：
拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：
这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：
其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：
我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求
从而得到
这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。
原文链接： [Math] 常见的几种最优化方法 - Poll的笔记 - 博客园