分类目录归档：学习
期望最大化（Expectation-Maximum，简称EM）算法是一种机器学习常见基础算法
EM算法常用于处理存在隐变量的最大似然估计模型，训练过程简单描述如下：
以K-means聚类为例进行直观理解：
EM算法作为一种基础算法，广泛应用于多种算法模型的学习过程，比如：隐马尔可夫模型 HMM
这类算法思想在其他模型中也经常遇见，比
输入重定向：
<：将指定文件的内容作为前面命令的参数
输出重定向：
>：直接把输出覆盖保存到指定文件
>>：把输出尾部追加保存到指定文件
/dev/null
- 类Unix系统中的一个特殊的设备文件
- 作用是像垃圾桶一样接收一切写入其中的数据并丢弃
- 写入操作会提示成功，读取操作会返回一个EOF报错
用于不挂断地运行命令（关闭当前session不会中断程序，只能通过kill等命令删除） 默认情况下该程序的输出都会被重定向到nohup.out文件中，也可以通
本文内容主要摘自：
《Is something better than pandas when the dataset fits the memory?》
代码地址
性能对比主要围绕5个操作展开：
Chinese Whispers（简称CW）算法，是一种无监督的图聚类算法
CW算法运行效率高，但结果存在不确定性，常用于人脸聚类或文本聚类
以人脸聚类为例，先进行图的初始化（构建无向加权图）：每个人脸图片为一个节点，不同节点通过计算相似度，然后连接相似度超出指定阈值的节点，并以相似度作为边的权重
算法步骤
- 对于N个人脸样本，每个样本节点先单独成簇（自成一类）
- 遍历所有节点，根据每个节点的邻节点所属类别，计算权重累加
- 修正节点类别，选择最终累加权重最高的类别
- 如果有多个权重最高的类别，
欧氏距离：对应元素求差后计算平方和（要求两个时序长度一致） $$ D(x,y) = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + ... + (x_n-y_n)^2} = \sqrt{\sum\limits_{i=1}^{n}(x_i-y_i)^2} $$ 曼哈顿距离：基于网格地图的路程（比如出租车的行驶路线长度） $$ D(x,y) =|x_1-y_1| + |x_2-y_2| + ... + |x_n-y_n| =\sum\limits_{i=1}^{n}|x_i-y_i| $$ 闵可夫斯基距离
K均值算法（即，k-means clustering），是一种无监督聚类算法
K-means算法属于NP-hard问题，不过存在高效的启发式算法，能快速收敛到一个局部最优解
算法步骤
- 对于N个样本，随机选择其中K个，作为最初的质心
- 遍历所有样本，选择最新的质心进行归类，形成K个簇
- 根据每个簇的样本重新计算质心（比如求均值）
- 重复步骤2-3，直到每个簇质心基本不再变化或达到最大迭代次数
算法的收敛过程如下所示：
（图源来自https
有偏样本方差：$Var=\frac{1}{n}\Sigma_{i=1}^n(X_i-X_{mean})^2$
无偏样本方差：$Var=\frac{1}{n-1}\Sigma_{i=1}^n(X_i-X_{mean})^2$
当数据量较少时，无偏样本方差更合理；当数据量较大时，二者不存在明显差异
Python相关方差计算
- numpy包中默认计算方差是有偏的，无偏计算需要设定参数
ddof=1- pandas包中默认计算方差是无偏的，有偏计算需要设定参数
ddof=0
定义随机变量$X$的概率
一个无向图，结点表示随机变量，边表示两个随机变量之间的概率依赖关系，每个随机变量都可以指定一种可能取值，当变量满足马尔可夫性（即变量的可能取值只与它的临近变量有关）时，这时的图就叫马尔可夫网络，也就是马尔可夫随机场。（非严谨定义）
以构建以词性标注为例，假设一个句子由10个单词组成的句子，每个单词的词性选择有10种，则马尔可夫随机场就限制了所有单词的词性只和它前后的单词有关系。
条件随机场
前置知识：1_study/math/马尔可夫模型
可视马尔可夫模型的状态是可知的，而隐马尔可夫模型（The Hidden Markov Model，简称 HMM）的状态是不可知，但存在可知的序列观察值
以典型的看病模型为例，设病人的状态有两种：{健康（Healthy），发烧（Fever）}
医生不能直接知道病人的状态，但能够得知病人的健康状况：{正常（Normal），发寒（Cold）， 头晕（Dizzy）}，作为一个行医多年的鬼才医生，他可以构建出看病用的隐马尔可夫模型：
注