大数据复习
分类
朴素贝叶斯 Naive Bayes
假设每一个样本都由$x_{1},x_{2}…x_{n}$个独立事件组合起来，样本的标签有$C_{1},C_{2}…C_{m}$种，有一堆训练集的数据，然后给你一个新的样本X，问它该打哪个标签
这个问题转化一下，就是求$P(C_{i} |X)$，看一下哪个标签的概率最大，即求$argmax_{C_{i}} P(C_{i} |X)$ 。
但是X在竖线右边，用不了独立事件概率相乘的公式，只会求
$$P(X|C_{i})=P(x_{1}|C_{i})P(x_{2}|C_{i})P(x_{3}|C_{i})$$
那么就要用到贝叶斯公式了
$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$
即
$$argmax_{C_{i}} P(C_{i}|X) = argmax_{C_{i}}\frac{P(X|C_{i})P(C_{i})}{P(X)}$$
$$=argmax_{C_{i}}\frac{P(x_{1}|C_{i})P(x_{2}|C_{i})P(x_{3}|C_{i})P(C_{i})}{P(X)}$$
然后又用到MAP (maximum a posteriori，极大后验) 假设，其实就是X是给定的样本，是已知的，P(X)=1。
分别求分子哪几项乘一起就得到结果了，看哪个概率最大，就把X分为哪一类。
KNN k-nearest-neighbors
有一堆点，每个点都有个标签，然后又给了一个点，问这个点属于哪个标签？
求这个点和已知的所有点的距离，取最近的k个点，这k个点里哪个标签的最多，就归为哪一类
附上不同距离定义的公式 （假设x和y都是长度为n的向量）
欧氏距离 $L_{2}(X,Y) = (\sum_{i=1}^{n} |x_{i}-y_{i}|^{2} )^{\frac{1}{2}} $
曼哈顿距离$L_{1}(X,Y)=\sum_{i=1}^{n} |x_{i}-y_{i}| $
$L_{p}$距离 $L_{p}(X,Y) = (\sum_{i=1}^{n} |x_{i}-y_{i}|^{p} )^{\frac{1}{p}} $
$L\infty$距离 $L_{\infty }(X,Y)=\max|x_{i}-y_{i}|$
Logistic Regression
本身是从线性回归中引申出来的，logistic regression用的sigmoid函数$$\sigma(z)=\frac{1}{1+e^{-z}}$$，就是一个光滑化之后的阶跃函数（x小于某个值时，y是一个值，x大于某个值时，y是另一个值）,把线性回归的wx+b添加了非线性因素进去
前向传播就是$\sigma(wX)=\frac{1}{1+e^{-wx}}$，（这里先不加偏置）关键是损失函数
最大似然估计
什么是似然Likelihood
和概率Probobality是相对的，在参数$ \beta$的前提下，x发生的概率是$P(x|\beta)$
似然就是在x发生了的前提下，什么样的参数 $\beta$，是使这件事发生概率最大的参数，似然函数记为$L(\beta|x)$，和前面那个P是相等的
也就是说，每一个参数都对应一个似然函数的值，当参数变化，似然函数值而在变化，最大似然估计就是说，**找到一个使似然函数最大的参数$\beta$**，在这个参数下，最有可能发生x事件
在二分类中（y只有0和1两个值），概率函数是这样表示的
$$P(y|x,\beta)=P(y=1|x)^{y}[1-P(y=1|x,\beta)]^{1-y}$$
然后训练集的样本有n个，那么概率就是上面这个式子乘n次，带入前向传播的公式，根据最大似然的概念，要做的就是最大化这个概率函数
$$L(\beta)=\prod_{i=1}^{n}P(y|x,\beta)=\prod_{i=1}^{n}(\frac{1}{1+e^{-x_{i}\beta}})^{y_{i}}(1-\frac{1}{1+e^{-x_{i}\beta}})^{1-y_{i}}$$
因为直接对这个东西取最大值很难，所以取个对数,连乘就会变成连加
然后又给他取个相反数，从取最大值就变成了取最小值，然后就可以当作损失函数了 logistic regression的损失函数就是这么个东西
$$J(\beta) = -\log{L(\beta)}= - \sum_{i=1}^{n}[y_{i}(\beta{x_{i}})-\log{(1+e^{\beta x_{i}})}]$$
最小化这个损失函数，得到$\hat{\beta}$，带入就得到了预测值
$P(y=1|x)=\frac{e^{\hat{\beta}x}}{1+e^{\hat{\beta}x}}$ ， $P(y=0|x)=\frac{1}{1+e^{\hat{\beta}x}}$
上述就是二项logistic回归的全过程
AdaBoost
假设T个弱分类器$h_{t}(x)$，每个弱分类器的权重都是$\alpha$，目的就是通过这个式子获取强分类器的预测结果
$$H(x)=sign(\sum_{t=1}^{T}\alpha_{t}h_{t}(x))$$
训练过程
每个样本都有个权重$w_{i}$，初始都是$\frac{1}{N}$，那么初始样本的权重分布就是$D_{1}=(\frac{1}{N},…,\frac{1}{N})$
重复以下过程T次
- 每个弱分类器的误差的计算
$$e_{t}=\sum_{i=1}^{n}w_{ti}(H_{t}(x_{i})\ne y_{i})$$
- 计算弱分类器在最终分类其中所占的权重
$$\alpha_{t}=\frac{1}{2}\ln (\frac{1-e_{t}}{e_{t}})$$
- 更新样本权值分布
$$D_{t+1}[i]=\frac{D_{t}[i]}{Z_{t{}}}e^{-\alpha_{t}y_{i}H_{t}(x_{i})}$$
Z是归一化常数，好像可以是不同的？
算完每个$\alpha$，就得到了开头的那个公式
SVM
画一条线（或者一个超平面）把不同类别的点分开，但是点都是离散的，能画出来无数条线把它们分开
硬间隔SVM
这个最佳超平面离最近的正类别和负类别的样本点的距离最远，这些最近的样本点被称为支持向量。
假设一个超平面$w^{T}x+b=0$，某个样本到这个超平面的距离是$\frac{|w^{T}x+b|}{||w||}$
再假设这个二分类的标签是+1和-1，那两类样本点分别要满足$w^{T}x+b\ge1,w^{T}x+b\le-1$，那这个边界平面的距离就是$\frac{2}{||w||}$，目的就是最大化这个距离
（其实标签不是+1和-1也没关系，最终距离只会改变分子，不影响取最值的条件）
由于$||w||$求的时候要开根号，所以把这个问题改为求他的平方，最小化$\frac{||w||^{2}}{2}$
但是很难直接求解，因为有个约束条件$y_{i}(wx_{i}+b)\ge1$，乘y是为了把$\le-1$那部分合并到一个式子里
然后为了求解这种条件约束，引入拉格朗日算子（原因这里先不管了，引入之后就不需要考虑约束条件了）
$$L=\frac{1}{2}||w||^{2}+\sum_{i=1}^{l}\alpha_{i}(1-y_{i}(wx_{i}+b))$$
软间隔SVM
找不到一条线，让两类点都分布在两侧，那么就允许有部分点在线的另一边，但是不能太远，这个远近是由一个叫松弛变量$\xi$控制的
和硬间隔类似，只不过把优化问题转变成
$$y_{i}(wx_{i}+b)\ge1-\xi$$
优化
$\frac{1}{2}||w||^{2}+C(\sum\xi)$
升维
软间隔也找不到，就把样本转化到更高维度的空间中，再找超平面
聚类
顺序聚类
第一个样本归为第一类，后面每个样本都和已有类计算一下最短距离，小于给定的阈值，就归进去，否则归为新的类
划分聚类K-means
- 随机选k个元素，作为k个簇的中心
- 剩下元素到k个簇中心的距离，将他们划分到距离最近的簇
- 重新计算k个簇的中心（所有点各个元素的均值）
- 全部样本重复2和3再次划分，直到不变
马氏距离
$$D_{M}(x,y) = \sqrt{(x-y)^{T}\sum^{-1}(x-y)}$$
其中$\sum^{-1}$是协方差矩阵的逆矩阵，修正了欧式距离中各个维度尺度不一致且相关的问题
层次聚类AGNES、DIANA
AGNES是自下而上的凝聚，开始每个点都是一个簇
根据两个簇中最近的数据点找到最近的两个簇，合并，直到到达指定的簇的个数
这个寻找最近的两个簇的方法还可以换成最大距离，平均距离，重心法……
DIANA是自上而下的分裂
密度聚类DBSCAN
DBSCAN，OPTICS，DENCLUE
DBSCAN:不再需要指定簇的个数，前面的k-means和agnes都需要指定
对于数据集中的每个点，计算其邻域（距离小于$\epsilon$）内的点的个数，如果个数超过阈值（MinPts），认为这个点是核心点
对于每个核心点，将在邻域内的点归为同一簇（这些点被称为密度可达的），不属于任何簇的点标记为噪声点
谱聚类（Spectral clustering）
回归
一元线性模型
$Y_{i}=\mu(x_{i})=a+bX_{i}+\epsilon_{i}$，$\epsilon$相互独立，服从$N(0,\sigma^{2})$
最小二乘法估计
$$\min\sum_{i=1}^{n}(y_{i}-\hat{y_{i}})^{2}=min\sum_{i=1}^{n}[y_{i}-\hat{\mu}(x_{i})]^{2}$$
如果目标函数是一元线性模型，把$\mu(x)$带入，分别对a和b求偏导，令偏导得0，会解出
$$\hat{b}=\frac{\sum(x_{i}-\overline{x})y_{i}}{\sum(x_{i}-\overline{x})^{2}}$$
$$\hat{a}=\overline{y}-\hat{b}\overline{x}$$
多元线性回归
非线性回归
关联规则
如何描述关联规则
集合$I={i_{1},i_{2},i_{3}…i_{m}}$中每一项（叫做项目）代表一个商品，集合$D={t_{1},t_{2}…t_{n}}$中每一项代表一个交易，且是I中元素的组合（t为一个项集，一个事务）
项集X在D中出现的次数占总事物的百分比叫做项集的支持度，给定一个阈值，支持度超过这个阈值就叫做频繁项集
关联规则是形如$X=>Y$的蕴含式，其中$X\subseteq I$，$Y\subseteq I$且 $X\cap Y=\oslash $，则X称为规则的条件，Y称为规则的结果。
支持度和置信度
$$support(X=>Y)=(包含X和Y的事物数/事物总数)*100%$$
$$confidence(X=>Y)=(包含X和Y的事务数/包含X的事物数)*100%$$
例如5次交易分别为（ABC）(ACD)（BCD）（ADE）（BCE）$ABCDE\in I$
支持度 置信度 A=>D 2/5 2/3 C=>A 2/5 2/4 A=>C 2/5 2/3 B&C=>D 1/5 1/3
由于分母相同，有时只用分子表示支持度，叫做频度
Apriori算法
关联规则的挖掘过程：
寻找频繁项集，然后产生关联规则（满足最小支持度和置信度）
难点在于寻找频繁项集，因为子集的数量太多了（$2^{项目个数}-1$）
如果某个项集是频繁项集，他的子集也一定是（逆否：有子集不是频繁的他也一定不是）
从上面一条可以推断出，如果一个项集是小的，就不用再考虑包含他（超集）的了
因此，Apriori算法是，先找频繁1-项集（也就是只有一个元素的项集），由选出来的1-项集，去组合2-项集，验证组合出来的，3-项集……
所以Aprioiri算法是一个逐层搜索的迭代算法
改进
Apriori算法每处理一层就要读一次数据库
PCY算法，FP-Tree
兴趣度，AprioriAll
时间序列分析
离群点outlier（奇异值anomaly），远离序列一般水平的极端大和极端小值
加性离群点：之干扰发生的那一时刻T上的序列值$X_{T}$，不影响$X_{T+…}$
新生离群点：干扰后面的序列
水平迁移离群点：在这个时刻发生了结构性变化，在T时刻前后发生水平迁移
暂时变更离群点：对后面有影响，但是影响很快变小
自回归模型 AR
$X_{t}$为平稳且零均值的时间序列，$X_{t}$与其滞后一期$X_{t-1}$高度线性相关，但滞后二期、三期…相关较弱，用$X_{t}=\phi X_{t-1}+a_{t}$ 表示一阶自回归模型
n阶自回归就是直到$X_{t-n}$都相关，是前面n项的线性组合
理论上要求$a_{t}$是正态白噪声序列（平稳时间序列的协方差为0）
移动平均模型 MA
$X_{t}$为平稳且均值为零的时间序列，$X_{t}$与滞后期之间的相关性较弱，但与干扰项的滞后一期$a_{t-1}$相关较强。$X_{t}=a_{t}-\theta {1}a{t-1}$表示一阶移动平均模型
m阶就是$X_{t}=a_{t}-\sum_{k=1}^{m}\theta {k}a{t-k}$
自回归移动平均模型 ARMA
$X_{t}=\phi {1}X{t-1} + \phi {2}X{t-2} + a_{t} - \theta {1}a{t-1}$叫做2阶自回归、1阶移动平均模型
降维
主成分分析PCA
把原来的p个具有一定相关性的指标，变为m个互不相关的指标
每一个主成分都是原始变量的先行组合，$Y=\mu{X}$
约束条件：
系数的平方和为1，即$\mu_{i} ‘ \mu_{i}=1$，$\sum_{j=1}^{p}\mu_{ij}^{2}=1$
Y1是满足线性组合中的方差最大者，Y2是与Y1不相关的方差最大者，Y3……
从几何意义上看，是把Xi构成的坐标系旋转产生新的坐标系，形成了最大的样本方差
线性判别式分析 LDA / Fisher
PCA是无监督的，LDA是有监督的，需要考虑标签
LDA：投影后类内方差最小，类间方差最大
因子分析
SVD 奇异值分解
特征值分解是针对方针的，奇异值分解可以不是
文本数据处理
TF-IDF
分析每个词对于文档的重要程度
建立一个DxV的词频矩阵TF，D为语料库文档个数，V为词典中词的个数，矩阵每个元素表示词典中这个词在这篇文档中出现的频率
建立一个大小为V的逆文本频率对角方阵IDF，词典中w个词，在df(w)篇文档中都有出现，那么w个词的逆文本频率定义为
$$IDF(w)=log\frac{|D|}{df(w)}$$
如果两个文本的TFxIDF结果余弦相似度越大，说明越相似
概率图
用图的形式表示随机变量之间条件依赖关系的概率模型，概率论和图论的结合
预处理
自我选择偏差
在不考虑做出选择的原因的时候，就进行选择差异对 比
在禁酒的学校， 学生嗜酒的概率低30%，完全戒酒的概率更高
大样本 随机 对照 双盲
双盲：为了客观公正，实验双方互不知道对方信息
缺失数据处理
热卡填充：找到最相似的赝本来填充
knn：k近邻的加权平均
回归：建立回归模型
不平衡数据处理
过采样：根据不平衡比例设置一个采样比例，对于每一少数类样本x，从knn中选择若干样本
线代
矩阵满足结合律和分配律(AB)C=A(BC)，(A+B)C=AC+BC
(AB)’=B’A’，(A+B)’=A’+B’
奇异矩阵：方阵、行列式是0，不是0就是非奇异
$A^{-1}=A^{}/|A|$，$A^{}$是伴随矩阵，元素是$a_{ij}$代数余子式
（去掉所在的行和列，带符号计算剩下的部分行列式的值）
k阶子式（矩阵中任取k行k列组成的方阵）的非零最高阶数k称为矩阵的秩 r(A)
满秩矩阵：方阵，k=边长，否则是降秩矩阵
秩就是行阶梯矩阵的阶梯数（非零行的数目）
增广矩阵：线性方程组Ax=B，A是稀疏矩阵，拼接上B就是增广矩阵
r(A)<r(A,b)无解，r(A)=r(A,b)=n(未知数个数)，有唯一解，小于n的时候有无数个解
特征值：A是n阶方阵，存在一个向量$\xi$，使得$A\xi=\lambda\xi$，$\lambda$就是特征值，$\xi$就是属于$\lambda$的一个特征向量
特征多项式：$|\lambda E-A|$。方程$|\lambda E -A|=0$称为特征方程
一个特征向量只能有一个特征值，但一个特征值可以有无数个特征向量($k\xi$)
$A^{m}$的特征值是$\lambda^{m}$，逆矩阵的特征值是$\lambda^{-1}$
相似矩阵：$B=P^{-1}AP$，A和B是相似的，P叫相似变换矩阵
概率统计
事件运算性质
交换、结合、分配律，对偶律（$\overline{A\cap B}=\overline{A}\cup \overline{B}$，$\overline{A\cup B}=\overline{A}\cap \overline{B}$）
条件概率
$P(A|B)=\frac{P(AB)}{P(B)}$，不要求AB独立，$P(B)>0$
互不相容
$P(A\cup B)=P(A)+P(B)-P(AB)$
如果A和B互不相容$P(A\cup B)=P(A)+P(B)$
方差
$Var(X_{1}+/-X_{2})=Var(X_{1})+Var(X_{2})$，当$X_{1}X_{2}$相互独立
标准差
$\sigma(X_{1}+X_{2})=\sqrt{Var(X_{1})+Var(X_{2})}$，当其相互独立
假设检验
$H_{0}$为原假设，$H_{1}$为备择假设
（1）$H_{0}:\mu\le\mu_{0},H_{1}:\mu>\mu_{0}$
（2）$H_{0}:\mu\ge\mu_{0},H_{1}:\mu<\mu_{0}$
（3）$H_{0}:\mu=\mu_{0},H_{1}:\mu\ne\mu_{0}$
(1)(2)称为单边假设检验，(3)称为双边假设检验
得分排名
Elo
每一场比赛之后调整得分$r’(A)=r(A)+k(S_{A}-\mu_{A})$
k是固定参数，比赛获胜$S_{A}=1$，反之-1，$\mu_{A}$是预期结果，如果A和B水平相同则为0，但如果几乎认定A会赢，就接近1，如果几乎必输，接近-1
基于有向图的排名
A胜B，画一条从A到B的箭头，最优排名的规则是画一个有向图（DAG，没有圈的图）使得违反有向边的顶点数至少
np完全
PageRank
所有网页为顶点，网页之间的超链接为边集的有向图
被越多网页超链接指向的网页越重要，被越重要的网页超链接指向的网页越重要