Algorithm

Principle of token bucket 随着互联网的发展，在处理流量的方法也不仅仅为 first-come，first-served，而在共享网络中实现流量管理的基本机制就是排队。而公平算法则是实现在优先级队列中基于哪些策略来排队的 “公平队列” 。Token Bucket 则是为公平排队提供了替代方案。Fair Queue 与 Token Bucket的区别主要在，对于Fair Queue来讲，如果请求者目前空闲，Queue会将该请求者的带宽分配给其他请求者；而 Token Bucket 则是分配给请求者的带宽是带宽的上限。 通过例子了解算法原理 假设出站带宽是 4个数据包/ms，此时有一个需求为，为一个特定的发送端 A 来分配 1个数据包/ms的带宽。此时可以使用公平排队的方法分给发送 A 25%的带宽。 此时存在的问题是我们希望可以灵活地允许 A 的数据包以无规则的时间间隔发送。例如假设 A 在每个数据包发送后等待1毫秒后再开始下一个数据包的发送。 sence1：此时假设 A 以 1ms 的间隔去发送数据包，而由于某种原因导致应该在 t=6 到达的数据包却在 t=6.5 到达。随后的数据包在 t=7 准时到达，在这种情况下是否应该保留到t=7.5？ sence2：或者是否允许在 t=6.5 发送一个迟到的数据包，在 t=7 发送下一个数据包，此时理论上平均速率仍然还是 1 个数据包/ms？ 显然sence2是合理的，这个场景的解决方法就是令牌桶算法，规定 A 的配额，允许指定平均速率和突发容量。当数据包不符合令牌桶规范，那么就认为其不合理，此时会做出一下相应： delay，直到桶准备好 drop mark，标记为不合规的数据包 delay 被称为 整形 shaping , shaping 是指在某个时间间隔内发送超过 Bc（Committed Burst）的大小，Bc 在这里指桶的尺寸。由于数据流量是突发性的，当在一段时间内不活动后，再次激活后的在一个间隔内发送的数量大于 Bc ，那么额外的流量被称为Be （burst excess）。 将流量丢弃或标记超额流量，保持在一个流量速率限制称为 “管制” policing。...

Overview K近邻值算法 KNN (K — Nearest Neighbors) 是一种机器学习中的分类算法；K-NN是一种非参数的惰性学习算法。非参数意味着没有对基础数据分布的假设，即模型结构是从数据集确定的。 它被称为惰性算法的原因是，因为它**不需要任何训练数据点来生成模型。**所有训练数据都用于测试阶段，这使得训练更快，测试阶段更慢且成本更高。 如何工作 KNN 算法是通过计算新对象与训练数据集中所有对象之间的距离，对新实例进行分类或回归预测。然后选择训练数据集中距离最小的 K 个示例，并通过平均结果进行预测。 如图所示：一个未分类的数据（红色）和所有其他已分类的数据（黄色和紫色），每个数据都属于一个类别。因此，计算未分类数据与所有其他数据的距离，以了解哪些距离最小，因此当K= 3 （或K= 6 ）最接近的数据并检查出现最多的类，如下图所示，与新数据最接近的数据是在第一个圆圈内（圆圈内）的数据，在这个圆圈内还有 3 个其他数据（已经用黄色分类），我们将检查其中的主要类别，会被归类为紫色，因为有2个紫色球，1个黄色球。 KNN算法要执行的步骤 将数据分为训练数据和测试数据 选择一个值 K 确定要使用的距离算法 从需要分类的测试数据中选择一个样本，计算到它的 n 个训练样本的距离。 对获得的距离进行排序并取 k最近的数据样本。 根据 k 个邻居的多数票将测试类分配给该类。 影响KNN算法性能的因素 用于确定最近邻居的距离的算法 用于从 K 近邻派生分类的决策规则 用于对新示例进行分类的邻居数 如何计算距离 测量距离是KNN算法的核心，总结了问题域中两个对象之间的相对差异。比较常见的是，这两个对象是描述主题（例如人、汽车或房屋）或事件（例如购买、索赔或诊断）的数据行。 汉明距离 汉明距离（Hamming Distance）计算两个二进制向量之间的距离，也简称为二进制串 binary strings 或位串 bitstrings ；换句话说，汉明距离是将一个字符串更改为另一个字符串所需的最小替换次数，或将一个字符串转换为另一个字符串的最小错误数。 示例：如一列具有类别 “红色”、“绿色” 和 “蓝色”，您可以将每个示例独热编码为一个位串，每列一个位。 注：独热编码 one-hot encoding：将分类数据，转换成二进制向量表示，这个二进制向量用来表示一种特殊的bit（二进制位）组合，该字节里，仅容许单一bit为1，其他bit都必须为0 如： apple banana pineapple 1 0 0 0 1 0 0 0 1 100 表示苹果，100就是苹果的二进制向量 010 表示香蕉，010就是香蕉的二进制向量...

决策边界 (decision boundary) 支持向量机获取这些数据点并输出最能分离标签的超平面。这条线是决策边界 决策平面 （ decision surface ），是将空间划分为不同的区域。位于决策平面一侧的数据被定义为与位于另一侧的数据属于不同的类别。决策面可以作为学习过程的结果创建或修改，它们经常用于机器学习、模式识别和分类系统。 环境空间 ( Ambient Space)，围绕数学对象即对象本身的空间，如一维 Line ，可以独立研究，这种情况下L则是L；再例如将L作为二维空间 $R^2$ 的对象进行研究，这种情况下 L 的环境空间是 $R^2$。 超平面（Hyperplane）是一个子空间， N维空间的超平面是其具有维数的平面的子集。就其性质而言，它将空间分成两个半空间，其维度比其环境空间的维度小 1。如果空间是三维的，那么它的超平面就是二维维平面，而如果空间是 2 维的，那么它的超平面就是一维线。支持向量机 (SVM) 通过找到使两个类之间的边距最大化的超平面来执行分类。 法向量 （Normal） 是垂直于该平面、另一个向量的 90° 角倾斜 什么是支持向量 支持向量 （Support vectors），靠近决策平面（超平面）的数据点。 如图所示，从一维平面来看，哪个是分离的超平面？ 一般而言，会有很多种解决方法（超平面），支持向量机就是如何找到最佳方法的解决方案。 转置运算 矩阵的转置是原始矩阵的翻转版本，可以通过转换矩阵的行和列来转置矩阵。我们用 $A^T$ 表示矩阵 A 的转置。例如， $$A=\left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{matrix} \right]$$ ；那么 A 的转置就为 $$A=\left[ \begin{matrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \end{matrix} \right]$$ ；...

熵和基尼指数 信息增益 信息增益 information gain 是用于训练决策树的指标。具体来说，是指这些指标衡量拆分的质量。通俗来说是通过根据随机变量的给定值拆分数据集来衡量熵。 通过描述一个事件是否"惊讶"，通常低概率事件更令人惊讶，因此具有更大的信息量。而具有相同可能性的事件的概率分布更"惊讶"并且具有更大的熵。 定义：熵 entropy是一组例子中杂质、无序或不确定性的度量。熵控制决策树如何决定拆分数据。它实际上影响了决策树如何绘制边界。 熵 熵的计算公式为：$E=-\sum^i_{i=1}(p_i\times\log_2(p_i))$ ；$P_i$ 是类别 $i$ 的概率。我们来举一个例子来更好地理解熵及其计算。假设有一个由三种颜色组成的数据集，红色、紫色和黄色。如果我们的集合中有一个红色、三个紫色和四个黄色的观测值，我们的方程变为：$E=-(p_r \times \log_2(p_r) + p_p \times \log_2(p_p) + p_y \times \log_2(p_y)$ 其中 $p_r$ 、$p_p$ 和 $p_y$ 分别是选择红色、紫色和黄色的概率。假设 $p_r=\frac{1}{8}$，$p_p=\frac{3}{8}$ ，$p_y=\frac{4}{8}$ 现在等式变为变为： $E=-(\frac{1}{8} \times \log_2(\frac{1}{8}) + \frac{3}{8} \times \log_2(\frac{3}{8}) + \frac{4}{8} \times \log_2(\frac{4}{8}))$ $0.125 \times log_2(0.125) + 0.375 \times log_2(0.375) + 0.5 \times log_2(0.375)$ $0.125 \times -3 + 0.375 \times -1.415 + 0.5 \times -1 = -0.375+-0.425 +-0.5 = 1....

Overview 逻辑回归通常用于分类算法，例如预测某事是 true 还是 false（二元分类）。例如，对电子邮件进行分类，该算法将使用电子邮件中的单词作为特征，并据此预测电子邮件是否为垃圾邮件。用数学来讲就是指，假设因变量是 Y，而自变量集是 X，那么逻辑回归将预测因变量 $P(Y=1)$ 作为自变量集 X 的函数。 逻辑回归性能在线性分类中是最好的，其核心为基于样本属于某个类别的概率。这里的概率必须是连续的并且在 (0, 1) 之间（有界）。它依赖于阈值函数来做出称为 Sigmoid 或 Logistic 函数决定的。 学好逻辑回归，需要了解逻辑回归的概念、优势比 (OR) 、Logit 函数、Sigmoid 函数、 Logistic 函数及交叉熵或Log Loss Prerequisite odds ratio explain odds ratio是预测变量的影响。优势比取决于预测变量是分类变量还是连续变量。 连续预测变量：$OR > 1$ 表示，随着预测变量的增加，事件发生的可能性增加。$OR < 1$ 表示随着预测变量的增加，事件发生的可能性较小。 分类预测变量：事件发生在预测变量的 2 个不同级别的几率；如 A,B，$OR > 1$ 表示事件在 A 级别的可能性更大。$OR<1$ 表示事件更低的可能是在A。 例如，假设 X 是受影响的概率，Y 是不受影响的概率，则 $OR= \frac{X}{Y}$ ，那么 $OR = \frac{P}{(1-P)}$ ，P是事件的概率。 让概率的范围为 [0,1] ，假设 $P(success)=0.8$ ，$Q(failure) = 0.2$ ；$OR$ 则是 成功概率和失败概率的比值，如：$O(success)=\frac{P}{Q} = \frac{0....