统计量

统计量：统计理论中对数据进行分析、检验的变量

• 传统的统计量具有显式解析表达式

  • 均值：数据之和除数量
  • 中位数：数据中间者

• 统计量同样可以理解为和数据相关优化问题的解

  • 均值：离差平方和最小
  • 中位数：划分均匀

  • 优化问题目标本身也是统计量

Odds/Odds Ratio

• Odds：几率/优势，事件发生与不发生的概率比值

  $$odds = \frac p {1-p}$$

  • $p$：事件发生概率

• Odds Ratio：优势比，两组事件 odds 的比值

  $$OR = \frac {odds_1} {odds_0}$$

WOE 值

WOE 值：将预测变量（二分类场景中）集中度作为分类变量编码的数值

$$\begin{align*} WOE_i & = log(\frac {\%B_i} {\%G_i}) \\ & = log(\frac {\#B_i / \#B_T} {\#G_i / \#G_T}) \\ & = log(\frac {\#B_i / \#G_i} {\#B_T / \#G_T}) \\ & = log(\frac {\#B_i} {\#G_i}) - log(\frac {\#B_T} {\#G_T}) \\ & = log(\frac {\#B_i / ({\#B_i + \#G_i})} {\#G_i / (\#B_i + \#G_i)}) - log(\frac {\#B_T} {\#G_T}) \\ & = log(odds_i) - log(odds_T) \end{align*}$$

• $\%B_i, \%G_i$：分类变量取第 $i$ 值时，预测变量为 B 类、G 类占所有 B 类、G 类比例
• $#B_i, #B_T$：分类变量取第 $i$ 值时预测变量为 B 类数量，所有 B 类总数量
• $#G_i, #G_T$：分类变量取第 $i$ 值时预测变量为 G 类数量，所有 G 类样本总数量
• $odds_i$：分类变量取第 $i$ 值时，预测变量取 B 类优势
• $odds_T$：所有样本中，预测变量取 B 类优势
• 其中 $log$ 一般取自然对数

• WOE 编码是有监督的编码方式，可以衡量分类变量各取值中

  • B 类占所有 B 类样本比例、G 类占所有 G 类样本比例的差异
  • B 类、G 类比例，与所有样本中 B 类、G 类比例的差异

• WOE 编码值能体现分类变量取值的预测能力，变量各取值 WOE 值方差越大，变量预测能力越强

  • WOE 越大，表明该取值对应的取 B 类可能性越大
  • WOE 越小，表明该取值对应的取 G 类可能性越大
  • WOE 接近 0，表明该取值预测能力弱，对应取 B 类、G 类可能性相近

OR与WOE线性性

$$\begin{align*} log(OR_{j,i}) &= log(odds_i) - log(odds_j) \\ &= WOE_i - WOE_j \end{align*}$$

• 即：预测变量对数优势值与 WOE 值呈线性函数关系

  • 预测变量在取 $i,j$ 值情况下，预测变量优势之差为取 $i,j$ 值的 WOE 值之差
  • WOE 值编码时，分类变量在不同取值间跳转时类似于线性回归中数值型变量

  

• 考虑到对数优势的数学形式，单变量 LR 模型中分类型变量 WOE 值可以类似数值型变量直接入模

  • 当然，WOE 值编码在多元 LR 中无法保证单变量分类情况下的线性
  • 或者说多变量 LR 中个变量系数值不一定为 1
  • 在基于单变量预测能力优秀在多变量场合也优秀的假设下，WOE 值编码（IV 值）等单变量分析依然有价值

Bayes Factor、WOE 编码、多元 LR

$$\begin{align*} ln(\frac {P(Y=1|x_1,x_2,\cdots,x_D)} {P(Y=0|x_1,x_2,\cdots,x_D)}) &= ln(\frac {P(Y=1)} {P(Y=0)}) \\ & \overset {conditionally independent} {=} ln (\frac {P(Y=1)} {P(Y=0)}) + \sum_{i=1}^D ln(\frac {P(x_i|Y=1)} {P(x_i|Y=0)}) \\ ln(\frac {P(Y=1|x_1,x_2,\cdots,x_D)} {P(Y=0|x_1,x_2,\cdots,x_D)}) & \overset {semi} {=} ln (\frac {P(Y=1)} {P(Y=0)}) + \sum_{i=1}^D \beta_i ln(\frac {P(x_i|Y=1)} {P(x_i|Y=0)}) \end{align*}$$

• $\frac {P(x_i|Y=1)} {P(x_i|Y=0)}$：贝叶斯因子，常用于贝叶斯假设检验

• Naive Bayes 中满足各特征 $X$ 关于 $Y$ 条件独立的强假设下，第二个等式成立

• Semi-Naive Bayes 中放宽各特征关于 $Y$ 条件独立假设，使用权重体现变量相关性，此时则可以得到多元 LR 的预测变量取值对数 OR 形式

  • 则多元 LR 场景中，WOE 值可以从非完全条件独立的贝叶斯因子角度理解

IV 值

$$\begin{align*} IV_i &= (\frac {\#B_i} {\#B_T} - \frac {\#G_i} {\#G_T}) * WOE_i \\ &= (\frac {\#B_i} {\#B_T} - \frac {\#G_i} {\#G_T}) * log(\frac {\#B_i / \#B_T} {\#G_i / \#G_T}) \\ IV &= \sum IV_i \end{align*}$$

• $IV_i$：特征 $i$ 取值 IV 值
• $IV$：特征总体 IV 值

• 特征总体的 IV 值实际上是其各个取值 IV 值的加权和
  • 类似交叉熵为各取值概率的加权和

Entropy

• （信息）熵：在概率分布上对复杂程度/多样性/不确定性/混乱程度的度量

$$\begin{align*} HOD(X) & = -E_P log P(x) \\ & = \sum_d^D P(x_d) log \frac 1 {P(x_d)} \\ & = - \sum_d^D p_d log p_d \\ \end{align*}$$

• $p_d$：随机变量各取值对应概率
• 事件 $i$ 发生概率 $p_d=0$：约定 $p_d log(p_d)$ 为 0
• 其中 $log$ 以 2 为底，单位为 bit，以 $e$ 为底，单位为 nat

• 信息论中，熵越高能传输越多信息

  • 可携带的信息量 = 单位消息熵 * 消息长度
  • 熵衡量系统复杂程度，提高系统确定性即削弱系统多样性，降低熵

• 概率分布包含的信息即其复杂程度（可能取值数量）

  • 考虑按照 $(p_1,\cdots,p_D)$ 分布、长度为 $N$ 的随机变量序列，其可能排列数为 $\frac {N!} {\prod_d^D (p_d N)!}$

  • 则根据 Stirling 公式有

    $$\begin{align*} log (\frac {N!} {\prod_d^D (p_d N)!}) & = log(N!) - \sum_d^D log((p_d N)!) \\ & \overset {\lim_{N \rightarrow \infty}} = log(\sqrt {2\pi N} ({\frac N e})^N) + \sum_d^D log(\sqrt {2\pi p_dN} ({\frac {p_dN} e})^{p_dN}) \\ & = log(\sqrt {2\pi N}) + N(logN-1) - \sum_d^D log(\sqrt {2\pi p_dN}) - \sum_d^D p_dN (log(p_dN) - 1) \\ & = log(\sqrt {2\pi N} + \sum_d^D log(\sqrt {2\pi p_dN})) + N \sum_d^D p_d log p_d \\ & \approx N \sum_d^D p_d log p_d \end{align*}$$

  • 则长度为 $N$ 的随机变量串的多样性、信息量为 $H * N$，其中 $H=\sum_d^D p_d log p_d$ 概率分布的信息熵

• 某个事件包含的信息可以用编码长度理解

  • 对概率 $p$ 事件，编码 $1/p$ 个需编码（2进制编码）长度 $log_2 \frac 1 p$
  • 则概率 $p$ 事件包含信息量可以定义为 $log \frac 1 p$，即事件包含的信息量可用表示事件需要编码的长度表示 （底数则取决于编码元，只影响系数）
  • 则整个随机变量的信息为各事件信息量加权和

• 熵可以视为变量取值概率的加权和

  • 只依赖随机变量 $X$ 的分布，与其取值无关，可将其记为 $H(P)$
  • 由定义 $0 \leq H(P) \leq log_2 k$
    • $H(p) = 0$：$\exists j, p_j=1$，随机变量只能取一个值，无不确定性
    • $H(p) = log k$：$\forall j, p_j=1/k$，随机变量在任意取值概率相等，不确定性最大

• empirical entropy：经验熵，熵中的概率由数据估计时（尤极大似然估计）
• 参考链接

  • https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
  • https://zhuanlan.zhihu.com/p/27876027
  • https://zhuanlan.zhihu.com/p/73710585

• Stirling 公式即用积分近似计算 $\sum logn$：https://zhuanlan.zhihu.com/p/143992660

熵的性质

• 对称性：事件取值不影响熵

• 极值性

  • 所有符号有同等机会出现的情况下，熵达到极大（琴生不等式）

    $$\begin{align*} H(X) & = E[log(\frac 1 {P(X)})] \leq log(E[\frac 1 {P(x)}]) & = log(n) \end{align*}$$

  • 仅有一个符号确定出现的情况下，熵达到极小 0

• Continuity连续性：度量连续，概率微小变化只能引起熵微小变化

• Normalization规范化：$H_2(\frac 1 2, \frac 1 2) = 1$

• Grouping组合法则/可加和性：熵与过程如何划分无关 （此即要求熵形式为对数）

  • 若子系统间相互作用已知，则可以通过子系统熵值计算系统整体熵

    $$H(X) = H(X_1,\cdots,X_K) + \sum_{k=1}^K \frac {|X_k|} {|X|} H(X_k)$$

    • $X_1,\cdots,X_K$：$K$ 个子系统，可以理解为将随机变量 $X$ 划分为 $K$ 种情况
    • $H(X_1,\cdots,X_K)$：子系统相互作用熵

    • 子系统相互作用熵可以认为是，通过已知信息消除的多样性（即信息增益）
    • 子系统熵之和则是利用已知信息消除多样性之后，系统剩余混乱程度

  • 一般的，两个事件 $X,Y$ 熵满足以下计算关系

    $$\begin{align*} H(X, Y) & = H(X) + H(Y|X) \\ & = H(Y) + H(X|Y) \\ & \leqslant H(X) + H(Y) \\ H(X|Y) & \leqslant H(X) \\ \end{align*}$$

  • 特别的，若事件 $X, Y$ 相互独立

    $$\begin{align*} H(X|Y) &= H(X) \\ H(X, Y) &= H(X) + H(Y) \end{align*}$$

• 满足以上特性的熵定义必然为如下形式

$$
-K \sum P(x)log(P(x))
$$

• 在热力学、信息论等领域，熵有多种不同定义，满足熵性质的测度泛函，只能具有（Shannon 熵和 Hartley 熵）或（von Neumann 熵和 Shannon 熵）线性组合的函数形式，若不要求满足组合法则，还有 Tsallis 熵等

Conditinal Entropy

条件熵：随机变量 $X$ 给定条件下，随机变量 $Y$ 的条件概率分布的熵对 $X$ 的数学期望

$$\begin{align*} H(Y|X) & = \sum_{i=1}^N p_i H(Y|X=x_i) \\ H(Y|x=x_i) & = - \sum_j P(y_j|x_i) log P(y_j|x_i) \end{align*}$$

• $P(X=xi, Y=y_j)=p{i,j}$：随机变量 $(X,Y)$ 联合概率分布
• $p_i=P(X=x_i)$
• $H(Y|X=x_i)$：后验熵

• 特别的，考虑数据集 $D$ 被分为 $D_1,\cdots,D_m$，条件经验熵可计算如下

  $$\begin{align*} H(D|A) & = \sum_{m=1}^M \frac {|D_m|} {|D|} H(D_m) \\ & = -\sum_{m=1}^M \frac {|D_m|} {|D|} \sum_{k=1}^K \frac {|D_{m,k}|} {|D_m|} log_2 \frac {|D_{m,k}|} {|D_m|} \end{align*}$$

• postorior entropy：后验熵，随机变量 $X$ 给定条件下，随机变量 $Y$ 的条件概率分布的熵
• empirical conditional entropy：经验条件熵，概率由数据估计

Infomation Gain/Mutual Infomation

互信息/信息增益：（经验）熵与（经验）条件熵之差

$$\begin{align*} g(Y|X) & = H(Y) - H(Y|X) \\ & = \sum_{x \in X} \sum_{y \in Y} P(x,y) log \frac {P(x,y)} {P(x)P(y)} \end{align*}$$

• 与数据集具体分布有关、与具体取值无关

  • 绝对大小同易受熵影响，（经验）熵较大时，互信息也相对较大
  • 由于误差存在，分类取值数目较多者信息增益较大

• 可衡量变量 $X$ 对 $Y$ 预测能力、减少不确定性的能力

  • 信息增益越大，变量之间相关性越强，自变量预测因变量能力越强
  • 只能考察特征对整个系统的贡献，无法具体到特征某个取值
  • 只适合作全局特征选择，即所有类使用相同的特征集合

Infomation Gain Ratio

信息增益比：信息增益对原始信息熵的比值

$$\begin{align*} g_R(Y|X) & = \frac {g(Y|X)} {H(X)} \end{align*}$$

• 考虑熵大小，减弱熵绝对大小的影响

Cross Entropy

• 信息论：基于相同事件测度的两个概率分布 $P, Q$，基于非自然（相较于真实分布 $P$）概率分布 $Q$ 进行编码，在事件集合中唯一标识事件所需 bit
• 概率论：概率分布 $P, Q$ 之间差异

$$\begin{align*} H(P, Q) & = E_P[-log Q] = \left \{ \begin{array}{l} -\sum_{X} P(x) logQ(x), & 离散分布 \\ -\int_X P(x) log(Q(x)) d(r(x)), & 连续分布 \end{array} \right. \\ & = H(P) + D_{KL}(P||Q) \end{align*}$$

• $P(x), Q(x)$：概率分布（密度）函数
• $r(x)$：测度，通常是 $Borel \sigma$ 代数上的勒贝格测度
• $D_{KL}(P||Q)$：$P$ 到 $Q$ 的 KL 散度（$P$ 相对于 $Q$ 的相对熵）

• 信息论中，交叉熵可以看作是信息片段在错误分布 $Q$ 分布下的期望编码长度
  • 信息实际分布实际为 $P$，所以期望基于 $P$

• 交叉熵是常用的损失函数：效果等价于 KL 散度，但计算方便
• sigmoid 激活函数时：相较于二次损失，收敛速度更快

Entropy 衍生指标

Kullback-Leibler Divergence

KL 散度/相对熵：衡量概率分布 $P, Q$ 之间差异的量化指标

$$\begin{align*} D_{KL}(P||Q) & = E_P[(-log Q(x)) - (-log P(x))] \\ & = E_P[log P(x) - log Q(x)] \\ & = \sum_{d=1}^D P(x_d) (log P(x_d) - log Q(x_d)) \\ & = \sum_{d=1} P(x_d) log \frac {P(x_d)} {Q(x_d)} \end{align*}$$

• KL 散度含义

  • 原始分布 $P$、近似分布 $Q$ 之间对数差值期望
  • 若使用观察分布 $Q$ 描述真实分布 $P$，还需的额外信息量

• KL 散度不对称，分布 $P$ 度量 $Q$、$Q$ 度量 $P$ 损失信息不同

  • 从计算公式也可以看出
  • KL散度不能作为不同分布之间距离的度量

Population Stability Index

PSI：衡量分布 $P, Q$ 之间的差异程度

$$\begin{align*} PSI &= \sum_d^D (P_d - Q_d) * log \frac {P_d} {Q_d} \\ &= \sum_d^D P_d log \frac {P_d} {Q_d} + \sum_d^D Q_d log \frac {Q_d} {P_d} \\ &= D_{KL}(P||Q) + D_{KL}(Q||P) \end{align*}$$

• 是 KL 散度的对称操作
  • 更全面的描述两个分布的差异

Gini 指数

基尼指数：可视为信息熵的近似替代

$$\begin{align*} Gini(p) & = \sum_{k=1}^K p_k(1-p_k) \\ & = 1 - \sum_{k=1}^K p_k^2 \end{align*}$$

• $p$：概率分布
• 异质性最小：Gini 系数为 0
• 异质性最大：Gini 系数为 $1 - \frac 1 k$

• Gini 指数度量分布的不纯度
  • 包含类别越多，Gini 指数越大
  • 分布越均匀，Gini 指数越大

• 熵较 Gini 指数对不纯度判罚更重

• 经济学领域的 Gini 系数更类似 AUC 值

与 Entropy 关系

$$\begin{align*} H(X) & = -E_P log P(x) \\ & = - \sum_i^N p_i log p_i \\ & = - \sum_i^N p_i (log (1 + (p_i-1))) \\ & = - \sum_i^N p_i (p_i - 1 + \xi(p_i^{'}-1)) \\ & \approx 1 - \sum_i^N p_i^2 \end{align*}$$

• Gini 指数可以视为是熵在 1 附近的一阶泰勒展开近似

条件 Gini 指数

$$Gini(Y|X) = \sum_{k=1}^K P(X=x_k)Gini(Y|X=x_k)$$

• 性质类似信息增益

Pearson 积矩相关系数

$$\rho_{X,Y} = \frac {cov(X, Y)} {\sigma_X \sigma_Y}$$

• $cov(X, Y)$：变量 $X, Y$ 协方差
• $\sigma_X, \sigma_Y$：变量 $X, Y$ 方差

• Pearson 积矩相关系数取值范围为 $[-1, 1]$
  • $1, -1$ 分别表示变量成正线性、负线性函数关系

显著性检验

Fisher 变换

$$z = \frac 1 2 ln(\frac {1+r} {1-r}) = arctanh(r)$$

• $z$：Pearson 积矩相关系数的 Fisher 变换
• $r$：样本的 Pearson 积矩相关系数值

• 当 $(X, Y)$ 为二元正态分布时，$z$ 近似正态分布
  • 均值：$\frac 1 2 ln(\frac {1+\rho} {1-\rho})$
  • 标准差：$\frac 1 {\sqrt {N - 3}}$

基于数学的近似方法

$$t = r \sqrt{\frac {N - 2} {1 - r^2}}$$

• 当 $(X, Y)$ 为二元正态分布且不相关时，$t$ 服从自由度为 $n-2$的 t-分布

Spearman 秩相关系数

$$\begin{align*} \rho_{X, Y} & = \frac {cov(Rank(X) - Rank(Y))} {\sigma_{Rank(X)} \sigma_{Rank(Y)}} \\ & = 1 - \frac {6 \sum_i^N d_i^2} {N(N^2-1)} \\ \end{align*}$$

• $Rank(X), Rank(Y)$：变量 $X, Y$ 的秩（应同序）（相同值秩取均值）
• $d_i$：变量对 $X, Y$ 中，二者秩差值

• Spearman 秩相关系数被定义为变量秩的 Pearson 相关系数

• Spearman 秩相关系数也可以使用 Fisher 变换检验显著性

Kendell 秩相关系数

$$\begin{align*} \tau_a &= \frac {N_c - N_d} {N_0} \\ \tau_b &= \frac {N_c - N_d} {\sqrt{(N_0 - N_X)(N_0 - N_Y)}} \\ \tau_c &= \frac {2(N_c - N_d)} {N^2 \frac {M-1} M} \end{align*}$$

• $N_0 = \frac {N(N-1)} 2$：变量对数量
• $N_c, N_d$：变量对 $X, Y$ 中有序对数量、无序对数量
• $N_X, N_Y$：变量对 $X, Y$ 中 $X$ 取值、$Y$ 取值相同对数量
• $M$：变量 $X, Y$ 中较小取值数量者取值数量

• Kendell 秩相关系数取值范围同样为 $[-1, 1]$

  • -1 仅在变量 $X, Y$ 取值完全反向取到

• $\tau_a$ 是 $\tau_b$ 在变量不存在取值相同时的特例

• $\tau_c$ 适合“层级”数据，即两个变量取值类似划分、内部细分

  ||A|B|C| |——-|——-|——-|——-| |I-1|30|0|0| |I-2|30|0|0| |II-1|0|30|0| |II-1|0|30|0| |III-2|0|0|30| |III-2|0|0|30|

  • 对以上数据，$\tau_b$ 取值在 0.9 附近，而 $\tau_c$ 取 1

• 有序对：对 $(X_i, Y_i), (X_j, Y_j)$，满足 $X_i < X_j, Y_i < Y_j$ 或 $X_i > X_j,Y_i > Y_j$ 则为有序对
• 无序对：对$(X_i, Y_i), (X_j, Y_j)$，满足 $X_i < X_j, Y_i > Y_j$ 或 $X_i > X_j, Y_i < Y_j$ 则为无序对

卡方统计量

卡方统计量：通过观察实际与理论值的偏差确定理论正确与否

$$\chi^2 = \sum \frac {(A - E)^2} E$$

• $A$：自变量、因变量组合对应频数观察值
• $E$：自变量、因变量组合对应频数期望值

• 将模型预测结果视为实际分布、先验分布（均匀分布）视为理论分布

• 卡方检验：检验定性变量之间相关性，假设两个变量确实独立，观察实际值、理论值偏差程度判断变量之间相关性

  • 若偏差足够小，认为误差是自然的样本误差，两者确实独立
  • 若偏差大到一定程度，误差不可能由偶然、测量精度导致， 认为两者相关

• 若模型预测结果同先验分布差别很大，说明模型有效，且卡方统计量值越大表示预测把握越大

特点

• 由于随机误差存在，卡方统计量容易
  • 夸大频数较小的特征影响
  • 相应的，取值数较少（各取值频数相对而言可能较大）特征影响容易被低估

分布证明

• 考虑随机变量 $X=(x_1,\cdots,x_D)$ 服从 Multinomial 分布，分布参数为 $n, p=(p_1,\cdots,p_D)$

• 考虑服从理论分布的随机变量 $X$ 协方差矩阵

  $$\begin{align*} \Sigma = Cov(X) &= \begin{bmatrix} np_1(1-p_1) & -np_1p_2 & \cdots & -np_1p_D \\ np_2p_1 & -np_2(1-p_2) & \cdots & -np_2p_D \\ \vdots & \vdots & \ddots & \vdots \\ -np_Dp_1 & -np_Dp_2 & \cdots & np_D(1-p_D) \end{bmatrix} \\ &= n\begin{bmatrix} p_1 & 0 & \cdots & 0 \\ 0 & p_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & p_D \end{bmatrix} - npp^T \\ \end{align*}$$

• 则由中心极限定理有，如下依分布收敛的结论

  $$\begin{align*} \frac {(X - np)} {\sqrt n} & \overset {D} {\rightarrow} N(0,\Sigma) \\ \end{align*}$$

• 考虑服从理论分布的随机变量 $X$ 的 $\chi^2$ 参数

  $$\begin{align*} \chi^2 &= \frac 1 n (X-np)^T D^2 (X-np) \\ D &= \begin{bmatrix} \frac 1 {\sqrt {p_1}} & 0 & \cdots & 0 \\ 0 & \frac 1 {\sqrt {p_2}} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac 1 {\sqrt {p_D}} \end{bmatrix} \end{align*}$$

• 并由连续映射定理可以得到 $D\frac {x-np} {\sqrt n}$ 分布，且其协方差矩阵 $\Sigma_0$ 满足

  $$\begin{align*} D\frac {x-np} {\sqrt n} & \overset {D} {\rightarrow} N(0, D \Sigma D^T) \\ \Sigma_0 &= D \Sigma D^T \\ \Sigma_0^2 &= (E - \sqrt p {\sqrt p}^T)(E - \sqrt p {\sqrt p}^T) = \Sigma_0 \\ \end{align*}$$

• 由以上，$\Sigma_0$ 仅有特征值 0，1

  • 特征值 0 对应特征向量有且仅有 $\sqrt p$
  • 特征值 1 对应特征向量有 $D-1$ 个
  $$\begin{align*} \Sigma_0 \sqrt p - 0 \sqrt p &= \sqrt p - \sqrt p = 0 \\ \Sigma_0 \lambda - 1 \lambda &= \lambda - \sqrt p {\sqrt p}^T \lambda = \sqrt p {\sqrt p}^T \lambda = 0 \end{align*}$$

• 则 $\chi^2$ 统计量依分布收敛于自由度为 $D-1$ 的卡方分布

  $$\begin{align*} \chi^2 &= \sum_{d=1}^D \frac {(x_d - np_d)^2} {np_d} \overset {D} {\rightarrow} \chi_{D-1} \end{align*}$$

• 可据此构造统计量进行卡方检验，检验实际值实际分布频率 $(a_1,\cdots,a_D)$ 是否符合该分布

  • 构造卡方统计量 $\chi^2 = \sum_{d=1}^D \frac {(x_d - na_d)^2} {na_d}$
  • 则卡方统计量在随机变量满足多项分布情况下依分布收敛于自由度为 $D-1$ 的卡方分布

• https://www.zhihu.com/question/309694332/answer/952401910
• https://zhuanlan.zhihu.com/p/198864907

Cauthy-Schwarz 不等式

• https://zhuanlan.zhihu.com/p/22004031
• https://zhuanlan.zhihu.com/p/129033407
• https://zhuanlan.zhihu.com/p/70315155
• https://zhuanlan.zhihu.com/p/85283405

常用定理

Lucas 定理

$$C(n, m) \% p = (C(n//p, m//p) * C(n\%p, m\%p)) \% p$$

• $p < 10^5$：必须为素数

Holder 定理

$|x|^{*}_p = |x|_q$

• $\frac 1 p + \frac 1 q = 1$

Radial Basis Function

• RBF 径向基函数：取值仅依赖到原点距离的实值函数，即 $\phi(x) = \phi(|x|)$

  • 也可以按照距离某中心点 $c$ 的距离定义，即 $\phi(x) = \phi(|x-c|)$
  • 其中距离一般为使用 $L_2$ 范数，即欧式距离
  • 函数 $\phi$ 一般与 $|x|$ 负相关

• 径向基函数最初用于解决多变量插值问题

  • 即以各样本为中心创建多个径向基函数
  • 多个径向基函数加权加和即得到拟合的函数曲线，可用于函数插值

  

常见径向基函数

• 定义 $r=|x-x_i|$

• 高斯函数

  $$\phi(r) = e^{-(\epsilon r)^2}$$

• Multiquadric 多二次函数：

  $$\phi(r) = \sqrt {1 + (\epsilon r)^2}$$

• Inverse Quadric 逆二次函数：

  $$\phi(r) = \frac 1 {1 + (\epsilon r)^2}$$

• Polyharmonic Spline 多重调和样条：

  $$\begin{align*} \phi(r) &= r^k, & k=1,3,5,\cdots \\ \phi(r) &= r^k (ln(r))^{}, & k=2,4,6,\cdots \\ \end{align*}$$

• Thin Plate Spline 薄板样条（多重调和样条特例）：

  $$\phi(r) = r^2 ln(r)$$

距离

• 距离可认为是两个对象 $x,y$ 之间的 相似程度
  • 距离和相似度是互补的
  • 可以根据处理问题的情况，自定义距离

Bregman Divergence

$$D(x, y) = \Phi(x) - \Phi(y) - <\nabla \Phi(y), (x - y)>$$

• $Phi(x)$：凸函数

• 布雷格曼散度：穷尽所有关于“正常距离”的定义

  • 给定 $R^n * R^n \rightarrow R$ 上的正常距离 $D(x,y)$，一定可以表示成布雷格曼散度形式
  • 直观上：$x$处函数、函数过$y$点切线（线性近似）之差
    • 可以视为是损失、失真函数：$x$由$y$失真、近似、添加噪声得到

• 特点

  • 非对称：$D(x, y) = D(y, x)$
  • 不满足三角不等式：$D(x, z) \leq D(x, y) + D(y, z)$
  • 对凸集作 Bregman Projection 唯一
    • 即寻找凸集中与给定点Bregman散度最小点
    • 一般的投影指欧式距离最小

• 正常距离：对满足任意概率分布的点，点平均值点（期望点）应该是空间中距离所有点平均距离最小的点
• 布雷格曼散度对一般概率分布均成立，而其本身限定由凸函数生成

  • 和 Jensen 不等式有关？凸函数隐含部分对期望的度量

• http://www.jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf

单点距离

Minkowski Distance

闵科夫斯基距离：向量空间 $\mathcal{L_p}$ 范数

$$d_{12} = \sqrt [1/p] {\sum_{k=1}^n |x_{1,k} - x_{2,k}|^p}$$

• 表示一组距离族

  • $p=1$：Manhattan Distance，曼哈顿距离
  • $p=2$：Euclidean Distance，欧式距离
  • $p \rightarrow \infty$：Chebychev Distance，切比雪夫距离

• 闵氏距离缺陷

  • 将各个分量量纲视作相同
  • 未考虑各个分量的分布

Mahalanobis Distance

马氏距离：表示数据的协方差距离

$$d_{12} = \sqrt {({x_1-\mu}^T) \Sigma^{-1} (x_2-\mu)}$$

• $\Sigma$：总体协方差矩阵

• 优点
  • 马氏距离和原始数据量纲无关
  • 考虑变量相关性
• 缺点
  • 需要知道总体协方差矩阵，使用样本估计效果不好

LW Distance

兰氏距离：Lance and Williams Distance，堪培拉距离

$$d_{12} = \sum^{n}_{k=1} \frac {|x_{1,k} - x_{2,k}|} {|x_{1,k} + x_{2,k}|}$$

• 特点
  • 对接近0的值非常敏感
  • 对量纲不敏感
  • 未考虑变量直接相关性，认为变量之间相互独立

Hamming Distance

汉明距离：差别

$$diff = \frac 1 p \sum_{i=1}^p (v^{(1)}_i - v^{(2)}_i)^k$$

• $v_i \in {0, 1}$：虚拟变量
• $p$：虚拟变量数量

• 可以衡量定性变量之间的距离

Embedding

• 找到所有点、所有维度坐标值中最大值 $C$
• 对每个点 $P=(x_1, x_2, \cdots, x_d)$
  • 将每维 $x_i$ 转换为长度为 $C$ 的 0、1 序列
  • 其中前 $x_i$ 个值为 1，之后为 0
• 将 $d$ 个长度为 $C$ 的序列连接，形成长度为 $d * C$ 的序列

• 以上汉明距离空间嵌入对曼哈顿距离是保距的

Jaccard 系数

Jaccard 系数：度量两个集合的相似度，值越大相似度越高

$$sim = \frac {\|S_1 \hat S_2\|} {\|S_1 \cup S_2\|}$$

• $S_1, S_2$：待度量相似度的两个集合

Consine Similarity

余弦相似度

$$similarity = cos(\theta) = \frac {x_1 x_2} {\|x_1\|\|x_2\|}$$

• $x_1, x_2$：向量

欧式距离

点到平面

• $T={(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)}$：样本点集
• $wx + b = 0$：超平面

Functional Margin 函数间隔

$$\hat{\gamma_i} = y_i(wx_i + b)$$

• 函数间隔可以表示分类的正确性、确信度

  • 正值表示正确
  • 间隔越大确信度越高

• 点集与超平面的函数间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

• 超平面参数 $w, b$ 成比例改变时，平面未变化，但是函数间隔成比例变化

Geometric Margin 几何间隔

$$\begin{align*} \gamma_i & = \frac {y_i} {\|w\|} (wx_i + b) \\ & = \frac {\hat \gamma_i} {\|w\|} \end{align*}$$

• 几何间隔一般是样本点到超平面的 signed distance

  • 点正确分类时，几何间隔就是点到直线的距离

• 几何间隔相当于使用 $|w|$ 对函数间隔作规范化

  • $|w|=1$ 时，两者相等
  • 几何间隔对确定超平面、样本点是确定的，不会因为超平面表示形式改变而改变

• 点集与超平面的几何间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

Levenshtein/Edit Distance

（字符串）编辑距离：两个字符串转换需要进行插入、删除、替换操作的次数

$$lev_{A,B}(i, j) = \left \{ \begin{array}{l} i, & j = 0 \\ j, & i = 0 \\ min \left \{ \begin{array}{l} lev_{A,B}(i,j-1) + 1 \\ lev_{A,B}(i-1,j) + 1 \\ lev_{A,B}(i-1, j-1) + 1 \end{array} \right. & A[i] != B[j] \\ min \left \{ \begin{array}{l} lev_{A,B}(i,j-1) + 1 \\ lev_{A,B}(i-1,j) + 1 \\ lev_{A,B}(i-1, j-1) \end{array} \right. & A[i] = B[j] \\ \end{array} \right.$$

组间距离

Single Linkage

Average Linkage

Complete Linkage

Hash Function

• hash：散列/哈希，将任意类型值转换为关键码值
• hash function：哈希/散列函数，从任何数据中创建小的数字“指纹”的方法
• hash value：哈希值，哈希函数产生关键码值
• collision：冲突，不同两个数据得到相同哈希值

• 哈希函数应该尽可能使得哈希值均匀分布在目标空间中
  • 降维：将高维数据映射到低维空间
  • 数据应该低维空间中尽量均匀分布

数据相关性

• Data Independent Hashing：数据无关哈希，无监督，哈希函数基于某种概率理论

  • 对原始的特征空间作均匀划分
  • 对分布不均、有趋向性的数据集时，可能会导致高密度区域哈希桶臃肿，降低索引效率

• Data Dependent Hashing：数据依赖哈希，有监督，通过学习数据集的分布从而给出较好划分的哈希函数

  • 得到针对数据密度动态划分的哈希索引
  • 破坏了传统哈希函数的数据无关性，索引不具备普适性

应用

• 查找数据结构：cs_algorithm/data_structure/hash_table
  • 哈希表
• 信息安全方向：cs_algorithm/specification/info_security
  • 文件检验
  • 数字签名
  • 鉴权协议

哈希函数

• 简单哈希函数主要用于提升查找效率（构建哈希表）

  • 要求哈希函数的降维、缩小查找空间性质
  • 计算简单、效率高

• 复杂哈希函数主要用于信息提取

  • 要求哈希函数的信息提取不可逆、非单调映射
  • 查表哈希
    • CRC 系列算法：本身不是查表，但查表是其最快实现
    • Zobrist Hashing
  • 混合哈希：利用以上各种方式
    • MD5
    • Tiger

单值输入

• 直接寻址法：取关键字、或其某个线性函数值 $hash(key) = (a * key + b) \% prime$

  • $prime$：一般为质数，以使哈希值尽量均匀分布，常用的如：$2^{32}-5$

• 数字分析法：寻找、利用数据规律构造冲突几率较小者

  • 如：生日信息前 2、3 位大体相同，冲突概率较大，优先舍去

• 平方取中法：取关键字平方后中间几位

• 折叠法：将关键字分割为位数相同部分，取其叠加和

• 随机数法：以关键字作为随机数种子生成随机值

  • 适合关键字长度不同场合

• 常用于之前哈希结果再次映射为更小范围的最终哈希值

序列输入

加法哈希

加法哈希：将输入元素相加得到哈希值

• 标准加法哈希

  1 2 3 4 5 6

  AddingHash(input): hash = 0 for ele in input: hash += ele # prime 为任意质数，常用 2^32 - 5 hash = hash % prime

  • 最终哈希结果 $\in [0, prime-1]$

位运算哈希

位运算哈希：利用位运算（移位、异或等）充分混合输入元素

• 标准旋转哈希

  1 2 3 4 5

  RotationHash(input): hash = 0 for ele in input: hash = (hash << 4) ^ (hash >> 28) ^ ele return hash % prime

• 变形 1

  1	hash = (hash<< 5) ^ (hash >> 27) ^ ele

• 变形2

  1 2 3

  hash += ele hash ^= (hash << 10) hash ^= (hash >> 6)

• 变形3

  1 2 3 4

  if (ele & 1) == 0: hash ^= (hash << 7) ^ ele ^ (hash >> 3) else: hash ^= ~((hash << 11) ^ ele ^ (hash >> 5))

• 变形4

  1	hash += (hash << 5) + ele

• 变形5

  1	hash = ele + (hash << 6) + (hash >> 16) - hash

• 变形6

  1	hash ^= (hash << 5) + ele + (hash >> 2)

乘法哈希

乘法哈希：利用乘法的不相关性

• 平方取头尾随机数生成法：效果不好

• Bernstein 算法

  1 2 3 4 5

  Bernstein(input): hash = 0 for ele in input: hash = 33 * hash + ele return hash

  • 其他常用乘数：31、131、1313、13131、131313

• 32位 FNV 算法

  1 2 3 4 5 6 7

  M_SHIFT = M_MASK = FNVHash(input): hash = 2166136261; for ele in input: hash = (hash * 16777619) ^ ele return (hash ^ (hash >> M_SHIFT)) & M_MASK

• 改进的 FNV 算法

  1 2 3 4 5 6 7 8 9 10

  FNVHash_2(input): hash = 2166136261; for ele in input: hash = (hash ^ ele) * 16777619 hash += hash << 13 hash ^= hash >> 7 hash += hash << 3 hash ^= hash >> 17 hash += hash << 5 return hash

• 乘数不固定

  1 2 3 4 5 6 7

  RSHash(input): hash = 0 a, b = 378551, 63689 for ele in input: hash = hash * a + ele a *= b return hash & 0x7FFFFFFF

• 除法也类似乘法具有不相关性，但太慢

定长序列

• 两步随机数

  1 2 3 4 5 6

  main_rand_seq = randint(k) TwoHashing(input[0,...,k]): hash = 0 from i=0 to k: hash += input[i] * main_rand_seq[i] hash = hash mod prime

Universal Hashing

• 全域哈希：键集合 $U$ 包含 $n$ 个键、哈希函数族 $H$ 中哈希函数 $h_i: U \rightarrow 0..m$，若 $H$ 满足以下则为全域哈希 $$

    \forall x \neq y \in U, | \{h|h \in H, h(x) = h(y) \} | = \frac {|H|} m
  

  $$

  • $|H|$：哈希函数集合 $H$ 中函数数量

• 独立与键值随机从中选择哈希函数，避免发生最差情况
• 可利用全域哈希构建完美哈希

性质

• 全域哈希 $H$ 中任选哈希函数 $h_i$，对任意键 $x \neq y \in U$ 冲突概率小于 $\frac 1 m$

  • 由全域哈希函数定义，显然

• 全域哈希 $H$ 中任选哈希函数 $hi$，对任意键 $x \in U$，与其冲突键数目期望为 $\frac n m$，即 $E{[collision_x]}=\frac n m$

  $$\begin{align*} E(C_x) &= E[\sum_{y \in U - \{x\}} C_{xy}] \\ &= \sum_{y \in U - \{x\}} E[C_{xy}] \\ &= \sum_{y \in U - \{x\}} \frac 1 m \\ &= \frac {n-1} m \end{align*}$$

  • $C_x$：任选哈希函数，与 $x$ 冲突的键数量
  • $C_{xy} = \left { \begin{matrix} 1, & h_i(x) = h_i(y) \ 0, & otherwise \end{matrix} \right.$：指示 $x,y$ 是否冲突的指示变量

  • $m = n^2$ 时，冲突期望小于 0.5
    • $n$ 个键两两组合数目为 $C_n^2$
    • 则 $E_{total} < C_n^2 \frac 1 n < 0.5$

例

• 以下构造 $[0,p-1] \rightarrow [0,m-1]$ 全域哈希

• $p$ 为足够大素数使得所有键值 $\in [0,p-1]$

  • 记 $Z_p = { 0,1,\cdots,p-1 }$
  • 记 $Z_p^{*}={ 1,2,\cdots,p-1 }$
  • 且哈希函数映射上限（哈希表长度） $m < max(U) < p$

• 记哈希函数

  $$\forall a \in Z_p^{*}, b \in Z_p, h_{a, b}(k) = ((a k + b) \% p) \% m$$

• 则以下哈希函数族即为全域哈希

  $$H_{p,m} = {h_{a,b}|a \in Z_p^{*}, b \in Z_p}$$

Locality Sensitive Hashing

LSH：局部敏感哈希

• $(r_1,r_2,P_1,P_2)-sensitive$ 哈希函数族 $H$ 需满足如下条件 $$ \begin{align*}

    Pr_{H}[h(v) = h(q)] \geq P_1, & \forall q \in B(v, r_1) \\
    Pr_{H}[h(v) = h(q)] \geq P_2, & \forall q \notin B(v, r_2) \\
  

  \end{align*}$$

  • $h \in H$
  • $r_1 < r_2, P_1 > P_2$：函数族有效的条件
  • $B(v, r)$：点 $v$ 的 $r$ 邻域
  • $r_1, r_2$：距离，强调比例时会表示为 $r_1 = R, r_2 = cR$

• 此时 相似目标（距离小）有更大概率发生冲突

LSH查找

思想

• 相似目标更有可能映射到相同哈希桶中

  • 则只需要在目标所属的哈希桶中进行比较、查找即可
  • 无需和全集数据比较，大大缩小查找空间

• 可视为降维查找方法

  • 将高维空间数据映射到 1 维空间，寻找可能近邻的数据点
  • 缩小范围后再进行精确比较

概率放大

• 期望放大局部敏感哈希函数族 $Pr_1, Pr_2$ 之间差距

• 增加哈希值长度（级联哈希函数中基本哈希函数数量） $k$

  • 每个哈希函数独立选择，则对每个级联哈希函数 $g_i$ 有 $Pr[g_i(v) = g_i(q)] \geq P_1^k$
  • 虽然增加哈希键位长会减小目标和近邻碰撞的概率，但同时也更大程度上减少了和非近邻碰撞的概率、减少搜索空间

  • 级联哈希函数返回向量，需要对其再做哈希映射为标量，方便查找

• 增加级联哈希函数数量（哈希表数量） $L$

  • $L$个哈希表中候选项包含真实近邻概率 至少 为 $1 - (1 - P_1^k)^L$
  • 增加哈希表数量能有效增加候选集包含近邻可能性
  • 但同时也会增大搜索空间

搜索近似最近邻

• 使用 $L$ 个级联哈希函数分别处理待搜索目标
• 在 $L$ 个哈希表分别寻找落入相同哈希桶个体作为候选项
• 在所有候选项中线性搜索近邻

基于汉明距离的 LSH

• 在汉明距离空间中搜索近邻
  • 要求数据为二进制表示
  • 其他距离需要嵌入汉明距离空间才能使用
    • 欧几里得距离没有直接嵌入汉明空间的方法
      • 一般假设欧几里得距离和曼哈顿距离差别不大
      • 直接使用对曼哈顿距离保距嵌入方式

设计哈希函数族

• 考虑哈希函数族 $H = { h_1, h_2, \cdots, h_m }$

  • 其中函数 $h_i$ 为 ${0, 1}^d$ 到 ${0, 1}$ 的映射：随机返回特定比特位上的值

• 从 $H$ 中随机的选择哈希函数 $h_i$

  • 则 $Pr[h_i(v) = h_i(q)]$ 等于 $v, q$ 相同比特数比例，则
    • $Pr_1 = 1 - \frac R d$
    • $Pr_2 = 1 - \frac {cR} d$
  • 考虑到 $Pr_1 > Pr_2$，即此哈希函数族是局部敏感的

基于 Jaccard 系数的 LSH

• 考虑 $M * N$ 矩阵 $A$，元素为 0、1

  • 其中
    • $M$：集合元素数量
    • $N$：需要比较的集合数量
  • 目标：寻找相似集合，即矩阵中相似列

• 用 Jaccard 系数代表集合间相似距离，用于搜索近邻

  • 要求各数据向量元素仅包含 0、1：表示集合是否包含该元素

定义 Min-hashing 函数族

• 对矩阵 $A$ 进行 行随机重排 $\pi$，定义 Min-hashing 如下

  $$h_{\pi}(C) = \min \pi(C)$$

  • $C$：列，表示带比较集合
  • $\min \pi(C)$：$\pi$ 重排矩阵中 $C$ 列中首个 1 所在行数

• 则不同列（集合） Min-hashing 相等概率等于二者 Jaccard 系数

  $$\begin{align*} Pr(h_{\pi}(C_1) = h_{\pi}(C_2)) & = \frac a {a + b} \\ & = Jaccard_d(C_1, C_2) \end{align*}$$

  • $a$：列 $C_1, C_2$ 取值均为 1 的行数
  • $b$：列 $C_1, C_2$ 中仅有一者取值为 1 的行数
  • 根据 Min-hashing 定义，不同列均取 0 行被忽略

Min-hashing 实现

• 数据量过大时，对行随机重排仍然非常耗时，考虑使用哈希函数模拟行随机重排

  • 每个哈希函数对应一次随机重排
    • 哈希函数视为线性变换
    • 然后用哈希函数结果对总行数取模
  • 原行号经过哈希函数映射即为新行号

• 为减少遍历数据次数，考虑使用迭代方法求解

  1 2 3 4 5 6

  for i from 0 to N-1: for j from 0 to M-1: if D[i][j] == 1: for k from 1 to K: # 更新随机重拍后，第 `j` 列首个 1 位置 DD[k][j] = min(h_k(i), DD[k][j])

  • $D$：原始数据特征矩阵
  • $DD$：$Min-hashing* 签名矩阵
  • $N$：特征数量，原始特征矩阵行数
  • $M$：集合数量，原始特征矩阵列数
  • $K$：模拟的随机重排次数，Min-hashing 签名矩阵行数
  • $h_k,k=1,…,K$：$K$ 个模拟随机重排的哈希函数，如 $h(x) = (2x + 7) mod N$

  • 初始化 Min-hashing 签名矩阵所有值为 $\infty$
  • 遍历 $N$ 个特征、$M$ 个集合
    • 查看每个对应元素是否为 1
    • 若元素为 1，则分别使用 $K$ 个哈希函数计算模拟重排后对应的行数
    • 若计算出行数小于当前 *Min-hash$ 签名矩阵相应哈希函数、集合对应行数，更新
  • 遍历一遍原始数据之后即得到所有模拟重排的签名矩阵

Exact Euclidean LSH

• $E^2LSH$：欧式局部LSH，LSH Based-on P-stable Distribution

  • 使用内积将向量随机映射到哈希值
  • p-stable 分布性质将欧式距离同哈希值相联系，实现局部敏感

• $E^2LSH$ 特点

  • 基于概率模型生成索引编码结果不稳定
  • 随编码位数 $k$ 增加的，准确率提升缓慢
  • 级联哈希函数数量 $L$ 较多时，需要大量存储空间，不适合大规模数据索引

p-stable 哈希函数族

$$h_{a, b}(v) = \lfloor \frac {av + b} r \rfloor$$

• $v$：$n$ 维特征向量
• $a = (X_1,X_2,\cdots,X_n)$：其中分量为独立同 p-stable 分布的随机变量
• $b \in [0, r]$：均匀分布随机变量

p-stable 哈希函数碰撞概率

• 考虑$|v_1 - v_2|_p = c$的两个样本碰撞概率

• 显然，仅在 $|av1 - av_2| \leq r$ 时，才存在合适的 $b$ 使得 $h{a,b}(v1) = h{a,b}(v_2)$

  • 即两个样本碰撞，不失一般性可设 $av_1 \leq av_2$
  • 此 $r$ 即代表局部敏感的 局部范围

• 若 $(k-1)r \leq av_1 \leq av_2 < kr$，即两个样本与 $a$ 内积在同一分段内

  • 易得满足条件的 $b \in [0,kr-av_2) \cup [kr-av_1, r]$
  • 即随机变量 $b$ 取值合适的概率为 $1 - \frac {av_2 - av_1} r$

• 若 $(k-1)r \leq av_1 \leq kr \leq av_2$，即两个样本 $a$ 在相邻分段内

  • 易得满足条件的 $b \in [kr-av_1, (k+1)r-av_2)$
  • 即随机变量 $b$ 取值合适的概率同样为 $1 - \frac {av_2 - av_1} r$

• 考虑 $av_2 - av_1$ 分布为 $cX$，则两样本碰撞概率为

  $$\begin{align*} p(c) & = Pr_{a,b}(h_{a,b}(v_1) = h_{a,b}(v_2)) \\ & = \int_0^r \frac 1 c f_p(\frac t c)(1 - \frac t r)dt \end{align*}$$

  • $c = |v_1 - v_2|_p$：特征向量之间$L_p$范数距离
  • $t = a(v_1 - v_2)$
  • $f$：p稳定分布的概率密度函数

  • $p=1$ 柯西分布

    $$p(c) = 2 \frac {tan^{-1}(r/c)} \pi - \frac 1 {\pi(r/c)} ln(1 + (r/c)^2)$$

  • $p=2$ 正态分布

    $$p(c) = 1 - 2norm(-r/c) - \frac 2 {\sqrt{2\pi} r/c} (1 - e^{-(r^2/2c^2)})$$

性质、实现

限制近邻碰撞概率

• $r$ 最优值取决于数据集、查询点

  • 根据文献，建议$r = 4$

• 若要求近邻 $v \in B(q,R)$以不小于$1-\sigma$ 概率碰撞，则有

  $$\begin{align*} 1 - (1 - p(R)^k)^L & \geq 1 - \sigma \\ \Rightarrow L & \geq \frac {log \sigma} {log(1 - p(R)^k)} \end{align*}$$

  则可取

  $$L = \lceil \frac {log \sigma} {log(1-p(R)^k)} \rceil$$

• $k$ 最优值是使得 $T_g + T_c$ 最小者

  • $T_g = O(dkL)$：建表时间复杂度
  • $T_c = O(d |collisions|)$：精确搜索时间复杂度
  • $T_g$、$T_c$ 随着 $k$ 增大而增大、减小

• 具体实现参考https://www.mit.edu/~andoni/LSH/manual.pdf

限制搜索空间

• 哈希表数量 $L$ 较多时，所有碰撞样本数量可能非常大，考虑只选择 $3L$ 个样本点

• 此时每个哈希键位长 $k$、哈希表数量 $L$ 保证以下条件，则算法正确

  • 若存在 $v^{ }$ 距离待检索点 $q$ 距离小于 $r_1$，则存在 $g_j(v^{ }) = g_j(q)$

  • 与 $q$ 距离大于 $r_2$、可能和 $q$ 碰撞的点的数量小于 $3L$

    $$\sum_{j=1}^L |(P-B(q,r_2)) \cap g_j^{-1}(g_j(q))| < 3L$$

• 可以证明，$k, L$ 取以下值时，以上两个条件以常数概率成立 （此性质是局部敏感函数性质，不要求是 $E^2LSH$）

  $$\begin{align*} k & = log_{1/p_2} n\\ L & = n^{\rho} \\ \rho & = \frac {ln 1/p_1} {ln 1/p_2} \end{align*}$$

• $\rho$ 对算法效率起决定性作用，且有以下定理

  • 距离尺度 $D$ 下，若 $H$ 为 $(R,cR,p1,p_2)$-敏感哈希函数族，则存在适合 (R,c)-NN 的算法，其空间复杂度为 $O(dn + n^{1+\rho})$、查询时间为 $O(n^{\rho})$ 倍距离计算、哈希函数计算为 $O(n^{\rho} log{1/p_2}n)$， 其中 $\rho = \frac {ln 1/p_1} {ln 1/p_2}$

  • $r$ 足够大、充分远离 0 时，$\rho$ 对其不是很敏感
  • $p1, p_2$ 随 $r$ 增大而增大，而 $k = log{1/p_2} n$ 也随之增大，所以 $r$ 不能取过大值

Scalable LSH

Scalable LSH：可扩展的 LSH

• 对动态变化的数据集，固定哈希编码的局部敏感哈希方法对数据 动态支持性有限，无法很好的适应数据集动态变化

  • 受限于初始数据集分布特性，无法持续保证有效性
  • 虽然在原理上支持数据集动态变化，但若数据集大小发生较大变化，则其相应哈希参数（如哈希编码长度）等需要随之调整，需要从新索引整个数据库

• 在 $E^2LSH$ 基础上通过 动态增强哈希键长，增强哈希函数区分能力，实现可扩展 LSH

混淆矩阵

• 对比实际类别值、预测类别值，编制混淆矩阵
• 基于混淆矩阵，计算各类错判率、总错判率（总错判率会受到数据不平衡性的影响）

F-Measure

F-测度：准率率和召回率综合值，越大越好

$$F-measure = \frac {(\beta^2 + 1) * P * R} {\beta^2 * P + R}$$

• $P = \frac {TP} {TP+FP}$：查准率、精确率
• $R = \frac {TP} {TP+FN}$：查全率、召回率、覆盖率

F1 值

F1值：$\beta=1$ 时的 F测度

$$\begin{align*} \frac {1} {F_{1}} &= \frac {1} {2} \left( \frac {1} {P} + \frac {1} {R} \right) \\ \Rightarrow F_{1} &= \frac {2 * P * R} {P + R} = \frac {2 * TP} {样例总数 + TP - TN} \end{align*}$$

TPR、FPR

• TPR、FPR 可视为对 TP、FP 用样本数量归一化的结果

  • 样本全体中正、负样本数量往往差距很大，直接比较 TP、FP 不合理
  • 考虑使用样本正、负数量归一化，即计算正比例 TPR、负比例 FPR

• TPR 越高越好，FPR 越低越好，但是这两个指标相互制约，两者同时增加、减小

  • 模型倾向于将样本 判定为 为正例，则 TP、FP 同时增加，TPR、FPR 同时变大
  • 即模型取不同阈值，会产生正相关的 TPR、FPR 的点列

Recevier Operating Characteristic Curve

ROC 曲线：不同 正样本概率 划分阈值下 TPR、FPR 绘制的折线/曲线

$$TPR = \frac {TP} {TP+FN} \\ FPR = \frac {FP} {FP+TN}$$

• ROC 曲线即以 FPR 为横坐标、TPR 为正坐标绘制曲线

  • FPR 接近 1 时，TPR 也接近 1，这是不可避免的
  • 而 FPR 接近 0 时，TPR 越大越好
  • 所以模型 ROC 曲线下方面积越大，模型判断正确效果越好

• 理解

  • 将正负样本的正样本概率值分别绘制在 x=1、x=-1 两条直线上
  • 阈值即为 y=threshold 直线
  • TPR、FPR 则为 x=1、x=-1 两条直线在阈值直线上方点数量，与各直线上所有点数量比值

Accuracy

准确率、误分率：评价分类器性能一般指标

$$\begin{align*} acc & = \frac 1 N sign(y_i = \hat y_i) \\ & = \frac {TP+TN} N \\ mis & = 1 - acc \end{align*}$$

• $y_i$：第 $i$ 样本实际类别
• $\hat y_i$：第 $i$ 样本预测类别
• $N$：样本数量

• 对给定测试集，分类器正确分类样本数与总样本数比值
• 即 0-1 损失函数时经验风险

Top PR

头部准召：评估模型头部性能

$$pr_{top} = \frac {TP_{top}} {TOP}$$

• $TOP$：指定的头部数量
• $TP_{top}$：头部中正例数量（正例指已知原 $TOP$ 样本）

Area Under Curve

AUC 值：ROC 曲线下方面积，越大越好

• AUC 值实际含义：随机抽取一对正、负样本，对其中正样本的正样本预测概率值、大于负样本的正样本预测概率值的概率

  • $=1$：完美预测，存在一个阈值可以让模型 TPR 为 1，FPR 为 0
  • $(0.5, 1)$ ：优于随机预测，至少存在某个阈值，模型 $TPR > FPR$
  • $=0.5$：同随机预测，无价值
  • $[0, 0.5)$：差于随机预测，但是可以反向取预测值

AUC 计算

• 绘制 ROC 曲线，计算曲线下面积

  • 给定一系列阈值（最精确时为样本数量），分别计算 TPR、FPR
  • 根据 TPR、FPR 计算 AUC

• 正负样本分别配对，计算正样本预测概率大于负样本比例

  $$\begin{align*} auc & = \frac {\sum I(P_P > P_N)} {M * N} \\ I(P_P, P_N) & = \left \{ \begin{array}{l} 1, & P_P > P_N, \\ 0.5, & P_P = P_N, \\ 0, & P_P < P_N \end{array} \right. \end{align*}$$

  • $M, N$：正、负样本数量

• Mann-Witney U 检验：即正、负样本分别配对的简化公式

  $$auc = \frac {\sum_{i \in Pos} rank(i) - \frac {M * (M+1)} 2} {M * N}$$

  • $Pos$：正样本集合
  • $rank(i)$：样本 $i$ 的按正样本概率排序的秩（对正样本概率值相同样本，应将秩加和求平均保证其秩相等）

Weighted-AUC

WAUC：给 每个样本 赋权，计算统计量时考虑样本权重

• FPR、TPR 绘图

  $$\begin{align*} WTPR & = \frac {\sum_{i \in Pos} w_i I(\hat y_i=1)} {\sum_{i \in Pos} w_i} \\ WFPR & = \frac {\sum_{j \in Neg} w_j I(\hat y_j=1)} {\sum_{j \in Neg} w_j} \end{align*}$$

  • $WTPR, WFPR$：加权 TPR、加权 FPR
  • $\hat y_i$：样本预测类别
  • $w_i$：样本权重

• Mann-Witney U 检验：考虑其意义，带入权重即可得

  $$\begin{align*} auc = \frac {\sum_{i \in Pos} w_i * rank(i) - \sum_{i \in Pos} w_i * rank_{pos}(i)} {\sum_{i \in Pos} w_i * \sum_{j \in Neg} w_j} \end{align*}$$

  • $rank_{pos}(i)$：正样本内部排序，样本$i$秩
  • $Neg$：负样本集合

多分类 AUC

• Micro-AUC：将每个类别视为样本标签，计算全体样本的正标签、负标签的 AUC

  • $n$ 个样本的 $m$ 维标签展平， 则其中有 $n$ 个正样本、$n * (m-1)$ 个负样本
  • $n$ 个样本的 $m$ 个分类器共 $n * m$ 个得分展平
  • 使用以上预测得分、标签计算 AUC

  1 2 3 4 5 6 7 8 9 10

  # one-vs-rest分类器得分 y_score = classifer.transform(X_test) # 展平后计算fpr、tpr fpr_micro, tpr_micro, threshhold_micro = \ skilearn.metrics.roc_curve(y_test.ravel(), y_score.ravel()) # 利用fpr、tpr计算auc auc_micro = skilearn.metrics.auc(fpr_micro, tpr_micro) # 等价于直接调用 auc_micro = skilearn.metrics.roc_auc_score(y_test, y_score, average="micro")

• Macro-AUC：对各类别，分别以计算 ROC 曲线（即 TPR、FPR），计算平均 ROC 曲线得到 AUC

  • 对各类别分别计算 TPR、FPR，共 $m$ 组 TPR、FPR

  • 平均合并 TPR、FPR，计算 AUC

    • 方法1：合并 FPR、去除重复值，使用 $m$ 组 TPR、FPR 分别求合并后 FPR 插值

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

      # 分别计算各类别fpr、tpr fprs, tprs = [0] * n_classes, [0] * n_classes for idx in range(n_classes): fprs[idx], tprs[idx], _ = sklearn.metrics.ruc_curve( y_test[:, i], y_score[:, i]) # 合并fpr all_fpr = np.unique(np.concatenate(fprs)) mean_tpr = np.zeros_like(all_fpr) # 计算合并后fpr插值 for idx in range(n_classes): mean_tpr += scipy.interp(all_fpr, fpr[idx], tpr[idx]) mean_tpr /= n_classes auc_macro = sklearn.metrics.auc(all_fpr, mean_tpr) # 但是和以下结果不同 auc_macro = sklearn.metrics.roc_auc_score(fprs)

• 以上分类器均为 one-vs-rest 分类器，$m$ 个类别则 $m$ 个分类器、每个样本 $m$ 个得分

Kolmogorov-Smirnov 统计量

KS 值：刻画区分正负样本能力

$$KS = max \{|TPR - FPR|\}$$

• KS 值体现 最理想情况 下，对正负样本区分能力
  • 即 ROC 曲线与 $TPR = FPR$ 直线的最远距离

Squared Error

Mean Squared Error

MSE：均方误差（偏差）

$$MSE = \frac 1 n \sum_{i=1}^{n} (y_{i} - \hat{y_{i}})^{2}$$

Mean Absolute Error

MAE：平均绝对误差

$$MAE = \frac 1 n \sum_{i=1}^n |y_i - \hat {y_i}|$$

Mean Absolute Percentage Error

MAPE：平均绝对百分比误差

$$MAPE = \frac 1 n \sum_{i=1}^n |\frac {y_i - \hat {y_i}} {y_i}|$$

Symmetric Mean Absolute Percentage Error

SMAPE：对称平均绝对百分比误差

$$MAPE = \frac 1 n \sum_{i=1}^n |\frac {y_i - \hat {y_i}} {(|y_i| + |\hat {y_i}|) / 2}|$$

$R^2$

$$\begin{align*} R^2 & = 1 - \frac {SSE} {SST} = \frac {SSR} {SST} \\ R^2_{adj} & = 1 - \frac {1 - R^2} {n - p - 1} \end{align*}$$

• $n, p$：样本量、特征数量
• $SSE$：残差平方和
• $SSR$：回归平方和、组内平方和
• $SST$：离差平方和
• $R^2_{adj}$：调整的$R^2$

Akaike Information Criterion

AIC ：赤池信息准则

$$\begin{align*} AIC & = -2log(L(\hat \theta, x)) + 2p \\ & = nln(SSE/n) + 2p \end{align*}$$

• $n, p$：样本量、特征数量
• $\theta$：带估参数
• $L(\theta, x)$：似然函数
• $SSE$：残差平方和

Bayesian Information Criterion

BIC：贝叶斯信息准则

$$\begin{align*} BIC & = -2log(L(\hat \theta, x)) + ln(n)p \\ & = nln(SSE/n) + ln(n)p \end{align*}$$

$C_p$

$$\begin{align*} C_p & = \frac {SSE} {\hat {\sigma^2}} - n + 2p \\ & = (n - m - 1) \frac {SSE_p} {SSE_m} - n + 2p \end{align*}$$

• $p$：选模型特征子集中特征数量
• $m$：所有特征数量
• $SSE_p$：选模型中残差平方和
• $SSE_m$：全模型中残差平方和