生信算法专题

隐马尔可夫模型

什么是马尔科夫性 指一个过程的”将来“指依赖于”现在“，而不依赖于”过去“，符合这个条件的的过程具有马尔可夫性，也称为马尔科夫模型

用统计学术语解释： 某一随机变量\(X_{t}\)，在某一时间\(t, (t=1,2,3, ...)\) 与前一个时刻的随机变量\(X_{t-1}\)之间存在条件概率\(P(X_{t}|X_{t-1})\)，若满足\(P(X_{t}|X_{t-1}, X_{t-2}, ..., X_{1})=P(X_{t}|X_{t-1})\)，则该随机变量具有一阶马尔科夫性

以上只是一阶马尔科夫模型，且这两种说法也只适用于一阶马尔科夫模型 n阶马尔科夫模型中，过去的状态依赖于前n个状态。

隐马尔可夫模型 指在马尔科夫模型的基础上，增加了一个不可观测的参数。即对于一个随机事件，既有观察值序列，又有一个隐藏的状态序列，可将观察序列与状态序列之间建立联系，可估计隐藏状态到可观测状态的输出概率，以及隐藏状态之间的转移概率。

HMM满足三个假设： - 齐次马尔科夫假设：任意时刻的状态至于前一时刻有关，而与其他时刻及观测无关\(P(X_{t}|X_{t-1}, X_{t-2}, ..., X_{1})=P(X_{t}|X_{t-1})\) - 参数不变性假设：状态转移概率不随时间变化而变化\(P(X_{m}|X_{m-1})=P(X_{n}|X_{n-1})\) - 观测独立性假设：任意时刻的观察值只与当前时刻的状态和输出概率有关，而与其他时刻及观察值无关\(P(O_{1},...,O_{t}|X_{1},...,X_{t})=P(O_{t}|X_{t})\)

HMM是一个五元组 观测集(符号\(\Omega_{O}\))，状态集(\(\Omega_{X}\))，转移概率矩阵(A)，输出概率矩阵(B)，初始状态分布(\(\pi\))

HMM解决三个问题 - 评估问题，给定模型λ，求某一观察值序列的概率\(P(\sigma|\lambda)\) - 解码问题，对于给定模型和观察值序列，求可能性最大的状态序列 - 学习问题，对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率\(p(σ|λ)\)最大

评估问题使用的是前向算法 前向算法是指，在给定参数模型λ的基础上，前t时刻的观察序列为\(o_{1},o_{2},...,o_{t}\)，且在t时刻状态为\(S_{i}\)的概率。 采用递推的思想，减少重复性计算，将每一步的计算结果存储起来，用于下一步的计算。 公式： \[ \begin{array}{l} \alpha_{1}(i)=\pi_{i}\cdot b_{i}(o_{1}),t=1\\ \alpha_{t+1}(j)=[\sum\limits_{i=1}^{N}\alpha_{t}(i)\cdot a_{ij}]\cdot b_{j}(o_{t+1})\\ P(O|\lambda)=\sum\limits_{i=1}^{N}\alpha_{T}(i) \end{array} \]

后向算法是指，在给定参数模型λ的基础上，从t+1时刻开始到终止时刻T，保证后T-t个观察序列为\(o_{t+1},o_{t+2},...,o_{T}\)的概率 公式： \[ \begin{array}{l} \beta_{T}(i)=1,1\le t \le T\\ \beta_t(i)=\sum\limits_{j=1}^{N}a_{ij}b_{j}(o_{t+1})\beta_{t+1}(j)\\ F(O|\lambda)=\sum\limits_{i=1}^{N}\pi_{i}b_{i}(o_{1})\beta_{1}(i) \end{array} \] 前向算法与后向算法的联系与区别 前向算法和后向算法都是采用递推的思想，只不过一个是从头推到尾，另一个是从尾推到头 区别在于，终止求和的时候，前向算法是直接将T时刻的各个\(\alpha\)相加，而后向算法不是将t=1时刻的\(\beta\)直接相加，而是还要利用初始的\(\pi\)再算一次并求和。前向算法主要用于计算观测序列概率，解决评估问题；后向算法常与前向算法组合进行概率计算和参数估计，解决监督式的学习问题

解码问题使用Viterbi算法 是一个动态规划的问题，将一个大问题分成一个个小问题，找到每一个小问题的最优解，联合起来就是整个问题的最优解

Viterbi算法是指，在给定参数模型λ和一个观测序列O，但观测序列隐藏的状态序列未知，于是使用动态规划的思想求最佳路径问题。涉及到递推和路径回溯，类似于双序列比对算法 公式： 其中\(\sigma\)表示从t时刻所有状态i，向t+1时刻某一状态j转移时，转移概率与输出概率乘积的最大值 \(\phi\)表示取最大值的\(\sigma\)所经过的两端点之间的连线路径，用于回溯的指针

学习问题使用前向后向算法 - 监督学习方法： - 假设训练数据是包括观测序列O和对应的状态序列I - 可以利用极大似然估计法来估计隐马尔可夫模型参数。 - 非监督学习方法： - 假设训练数据只有S个长度为T的观测序{O1,O2,…Os}, - 可以采用Baum-Welch算法

Baum-Welch算法 是一种用于HMM中参数评估的算法，是EM在HMM学习问题中的应用。在只给定一条观测集序列，但没有确定状态集和参数λ的情况下，通过初始化一组参数λ，使用EM算法进行迭代计算，直至模型参数收敛或小于预设的阈值。 Baum-Welch算法中Expectation，是计算隐变量的概率分布，并得到可观察变量与隐变量联合概率的log-likelihood在前面求得的隐变量概率分布下的期望，在这一步，使用前向后向算法来得到隐变量中各种可能性的概率；Maximization是求得上述期望最大的新的模型参数，若达到收敛条件则退出，未达到则继续迭代。

---

聚类算法

1. 层次聚类

层次聚类hierarchical clustering：通过 计算不同类别数据点间的相似度 来创建一棵有层次的嵌套聚类树。 分为两类：自下而上的聚集性层次聚类；自下而上的分裂型层次聚类

步骤： - 合并距离最近的两个结点 - 重新计算新结点与其他结点之间的距离 - 分支长度代表距离

两点之间距离的选取 ^215e31 - 欧氏距离 \(d(u,v)=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}\) - 曼哈顿距离 \(d(u,v)=|x_{1}-x_{2}|+|y_{1}-y_{2}|\) - 协方差/马氏距离 \(d(u,v)=\frac{\sum\limits_{k=1}^{K}(x_1-u)(x_2-v)}{\sqrt{\sum\limits_{k=1}^ {K}(x_{1}-u)^2\sum\limits_{k=1}^{K}(x_{2}-v)^{2}}}\) - 1-相关系数（皮尔森相关系数） \(1-\frac{1}{n}\sum\limits_{i=1}^{n}(\frac{x_{i}-\overline{x}}{\sigma_{x}})(\frac{y_{i}-\overline{y}}{\sigma_{y}})\)

不同簇之间距离的选取 Single Linkage最小距离 取两个类中距离最近的两个样本的距离作为这两个集合的距离。这种计算方式容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。

Complete Linkage最大距离 Single Linkage 的反面，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。

Average Linkage平均距离 这种方法就是把两个集合中的点两两的距离全部放在一起求均值，相对也能得到合适一点的结果。有时异常点的存在会影响均值，平常人和富豪平均一下收入会被拉高是吧，因此这种计算方法的一个变种就是取两两距离的中位数。

Centroid Linkage质心距离 分别计算两类的质心，然后以质心作为两类的距离

2. K-均值聚类

将给定的数据集划分成K个簇，并给出每个样本数据对应的中心点。 需要确定初始需要划分为几个类，将数据分配到距离最近的类中心点，然后重新计算各个类的中心点，不断重复直到类的中心点不再变化，趋于收敛。

缺点： - 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。 - 若簇中含有异常点，将导致均值偏离严重（即:对噪声和孤立点数据敏感）。 - 为解决K-means中离群值干扰的影响，可用K-中心点聚类

提问 如何选择 k-means 中的 K 值？ 一般先将 K 定为 2，然后逐渐增加；在增加 K 的过程中，最好能使 cluster 内的距离减小，而 cluster 间的距离增加，即获得最大的（组内距离/组间距离）；评估每次增加 K 值的成本，如果不值得再继续增加就停止。

k-medoids聚类算法有许多不同类型的算法可以执行k-medoids聚类，其中最简单，最有效的算法是PAM。 在PAM中，我们执行以下步骤来查找集群中心： - 从散点图中选择k个数据点作为聚类中心的起点。 - 计算它们与散点图中所有点的距离。 - 将每个点分类到最接近中心的聚类中。 - 在每个群集中选择一个新点，以使该群集中所有点与自身的距离之和最小。 - 重复步骤2，直到中心停止变化。

支持向量机 SVM

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。 SVM算法原理 SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示，即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

随机森林 random forest

算法性能评估

算法性能评估一般看这几个指标：准确率Accuracy、精确率Precision、召回率Recall、F1-Score、ROC曲线、AUC。 算法性能评估指标需要借助混淆矩阵Confusion Matrix中的参数：

准确率Accuracy的计算公式为：\(\frac{TP+TN}{TP+TN+FP+FN}\) 准确率预测的是正确的结果占总样本的百分比。虽然准确率可以判断总的正确率，但是在样本不平衡的情况下，准确率并不是一个很好的指标。例如在正样本为90%而负样本为10%时，模型将样本全部预测为正样本也会有90%的准确率，因此准确率会存在很大的水分。

精确率Precision的计算公式为：\(\frac{TP}{TP+FP}\) 准确率表示被预测为“正”的样本中真正为阳性的样本所占的百分比。精确度反映了正样本结果中预测的准确度，与准确度不同的是，精确度不考虑负样本，不受样本不平衡的影响。

召回率Recall的计算公式为：\(\frac{TP}{TP+FN}\) 召回率表示的实际为“正”的样本中被预测为真阳性的样本所占的百分比。召回率越高，实际正样本被预测出来的概率越大。

F1-Score的计算公式为：\(2\cdot \frac{Precision \cdot Recall}{Precision+Recall}\) Precision和Recall是一对矛盾的度量，一般Precision越高，Recall就会越低，Precision越低，Recall就会越高。同时分类置信度高时，Precision越高，反之Recall越高。为了能够综合考虑着两者指标，F1-Score定义为二者的调和平均数，旨在尽可能提高Precision和Recall的同时，使两者的差距尽可能减小。

ROC曲线 ROC（Receiver Operating Characteristic受试者操作曲线）曲线选用两种指标，分别为灵敏度Sensitivity和（1-特异度Specificity）。灵敏度的计算公式与召回率相同，特异度的计算公式为 \(\frac{TN}{FP+TN}\)。之所以选择1-特异度是因为要获取实际“负”样本中被错误预测为阳性的百分比。灵敏度也被称为真阳性率TPR，1-特异度也被称为假阳性率FPR。 TPR和FPR都是分别在实际为正样本和负样本中观察相关概率，因此不会受到样本是否平衡的影响。ROC是以FPR为横坐标，TPR为纵坐标，并通过遍历所有阈值来绘制的曲线。FPR能够反映模型虚报的响应程度，TPR可以反映模型预测响应的覆盖程度。当FPR越小，虚报的越少，TPR越大，覆盖的越多，即FPR越小，TPR越大，ROC曲线越陡峭，表示模型的性能越好。

AUC(Area Under Curve) ：ROC曲线下的面积，因为ROC“随机猜测”模型通常对应于其对角线，因而通常AUC的值范围为0.5~1，其值越大说明模型算法的性能越好，AUC为0.5时模型算法为“随机猜测”，其值为1时说明模型算法达到理想状态。

马修相关系数（Mathew correlation coefficient, MCC）：计算公式为\(\frac{(TP\times TN)-(FN\times FP)}{\sqrt{(TP+FN)\times (TN+FP) \times (TP+TN)\times (FP+FN)}}\) 特别适用于处理不平衡数据集。它考虑了真正例（TP）、真反例（TN）、假正例（FP）和假反例（FN），提供一个能够总结分类质量的单一数值。马修相关系数的取值为[-1,1]，-1表示预测与实际完全不符，1表示完美预测，0表示随机预测，一般0.5以上就表示预测效果良好。

1. Sensitivity, Recall, TPR：\(\frac{TP}{TP+FN}\) 代表真阳性，对于实际为“正”样本中被预测为“阳性”的比例是多少 2. Specificity, TNR：\(\frac{TN}{FP+TN}\) 代表真阴性，对于实际为“负”样本，被预测成“阴性”的比例是多少 3. False positive rate, FPR：\(\frac{FP}{FP+TN}\) 代表假阳性，对于实际为“负”样本中，被预测为“阳性”的比例是多少 4. False discovery rate, FDR：\(\frac{FP}{TP+FP}\) 代表假发生率，对于被预测为“阳性”的样本中，负样本的比例是多少