数据科学与工程算法基础1-7章
1 绪论
混淆矩阵
| 预测\真实 | 正例 | 负例 |
|---|---|---|
| 正例 | TP | FP |
| 负例 | FN | TN |
召回率$R=\frac{TP}{TP+FN}$
准确率$P=\frac{TP}{TP+FP}$
$F_\beta=\frac{(\beta^2+1)PR}{\beta^2P+R}$
回归问题
平均绝对误差$MAE$
均方误差$MSE$
均方根误差$RMSE$
2 抽样算法
系统抽样
- 直线等距抽样
- 圆形等距抽样
特点：简便、均匀、 潜在分层，但会有偏差，误差计算复杂
分层抽样
样本量分配方法：
- 等额样本法
- 按比例分配法
水库抽样
- 分布是水库抽样算法
3 尾概率不等式
Markov
$P(X\geqslant a)\leqslant\frac{E(X)}{a}$
Chebyshev
$P(|X-E(X)|\geqslant \epsilon)\leqslant \frac{Var(X)}{\epsilon^2}$
Chernoff
$P(X<(1-\delta)\mu)<(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}})^\mu$
$P(X>(1+\delta)\mu)<(\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu$
推论
$P(X<(1-\delta)\mu)<e^{-\frac{\mu\delta^2}{2}}$
$P(X>(1+\delta)\mu)<e^{-\frac{\mu\delta^2}{3}}$
Moris
以$1/2^X$的概率更新X的值为X+1，返回近似估计值$2^X-1$
是无偏估计（归纳法证明）
方差$Var(2^{X_N}-1)\simeq \frac{1}{2}N^2$
Moris+
对多次Moris算法取平均值
对n个数取均值，方差被减小到$O(N^2/n)$
当$n\geqslant O(1/(\delta\epsilon^2))$，$P(|\hat N-N|>\epsilon N)<\delta$（由Chebyshev不等式证）
Moris++
运行$t=ln(1/\delta)$次Moris+算法，每个Moris+算法由$n=1/\epsilon^2$构成，取n次Moris+算法结果的中位数
当$n=O(1/\epsilon^2)$，$P(|\hat{N_i}-N|>\epsilon N)<\frac{1}{2n\epsilon^2}<\frac{1}{3}$（Chebyshev）
指示变量$Y_i=1$表示Moris+算法失败，则$E(Y_i)=P(Y_i=1)<\frac{1}{3}$
算法至少失败t/2次时Moris++算法失败，$P(\sum Y_i>\frac{t}{2})= P(\sum Y_i>(1+\frac{1}{2})\frac{t}{3})\leqslant P(\sum Y_i>(1+\frac{1}{2})\mu)\leqslant exp(-\mu(\frac{1}{2})^2/4)<\delta$（Chernoff）
即$\mu\geqslant 16\ln\frac{1}{\delta}$，$\frac{t}{3}\geqslant \mu\geqslant 16\ln\frac{1}{\delta}$
有$t=O(\ln(1/\delta))$
4 哈希算法
布隆过滤器
参数m（数组位数），k（哈希函数个数）
误判率分析：
- 任意一次哈希没有选中某位的概率$1-\frac{1}{m}$
- 插入一个元素需要被哈希k次，k次哈希后某位置没有被置为1的概率$(1-\frac{1}{m})^k$
- 插入n个元素后，某位仍然为0的概率$(1-\frac{1}{m})^{kn}\simeq e^{-\frac{kn}{m}}$
- 某个元素经过k个哈希函数哈希后，对应的k个位置恰好都被置为1才会发生误判，则误判率为$(1-e^{-\frac{kn}{m}})^k$
- 令$\rho=e^{-\frac{kn}{m}}=\frac{1}{2}$时误判率最小，此时$k=\ln2\cdot \frac{m}{n}$
局部敏感哈希
Jaccard相似度
最小哈希
基于最小哈希签名矩阵的相似度（最小哈希值相同的比例即为相似度）
局部敏感哈希
两个元素被映射到同一个桶的概率是$(1-s^r)^b$，s：Jaccard相似度，r：行数，b：组数
5 Sketch算法
Misra Gries
可能会出现误报，但不会漏报，且无法知晓每个元素的频数
Count Sketch
简单抽样算法
数据流大小m，抽样后的数据流大小为M，$p=M/m$，元素到达时以p概率更新$c_i$，估计频数为$c_i/p$
Basic Count Sketch
哈希函数$h(\cdot)$将元素均匀映射到k个位置，哈希函数$g(\cdot)$将n个元素映射为-1或+1，对于信道大的元素，将其位置上计数+1或-1，元素a的估计频数为$g(a)C[h(a)]$
$E(\hat{f_a})=0,Var(\hat{f_a})=\frac{1}{k}(\sum_if_i^2-f_a^2)=\frac{||f_{-a}||_2^2}{k}$（用$Var(X)=E(X^2)-E(X)^2$算，最后用了个很奇怪的符号）
$P(|\hat{f_a}-f_a|\geqslant \epsilon||f||_2)\leqslant P(|\hat{f_a}-f_a|\geqslant\epsilon||f_{-a}||_2)\leqslant \frac{Var(\hat{f_a})}{\epsilon^2||f_{-a}||_2^2}=\frac{1}{k\epsilon^2}<\delta$
因此，需要$k=O(1/\epsilon^2\delta)$，使得偏离值超过$\epsilon||f||_2$的概率小于$\delta$
Count Sketch
t次Basic Count Sketch算法取中位数，运用Tug of War
$k=O(\ln(1/\delta)/\epsilon^2)$，证明类似Moris++
Count-Min Sketch
CM Sketch算法中$c_i$严格为正，估计频率返回d个哈希表中的最小值
分析得计数器个数$M=O(\frac{\ln(1/\delta)}{\epsilon})$
6 EM算法
最大似然估计
概统学过了不看了
EM算法
不考 不看了
7 随机游走
随机过程
与时间t有关的一个随机变量序列
马尔可夫过程
已知时刻t=n所处状态得条件下，过程在t=n+1时刻得状态与t<n之前的状态无关
若时间集合和状态空间离散，则称为马尔科夫链
转移概率矩阵
矩阵行和为1，列和不一定为1，每个位置上的值[0,1]
平稳分布
存在条件：满足不可约和反周期性质
不可约
若马氏链中任意两个状态都是连通的，则称该马氏链不可约
反周期
若所有状态的周期均为1，则称该马氏链是反周期的
状态x的周期是经过该状态所有环的长度的最大公约数