Andrew Ng机器学习课程笔记（第八周至第十一周）
本笔记基于Coursera上吴恩达（Andrew Ng）的机器学习课程内容集结而成。（课程链接）
全课程分为十一周，每周都有1-3个测验。第二周至第九周附有编程作业，一共8份。
更新：
3/1/2018： 更正kNN为k-平均算法
第八周
非监督学习(Unsupervised Learning)
非监督学习是使用非标签的数据来建立模型。非监督学习可用于建立数据集群，为数据分类。
k-平均演算法 （K-Means Algoithm)
- 随机在数据集中选择两点为集群中心（cluster centroids）。
- 为所有数据选择最近的集群中心。
- 移动集群中心到下属数据的中心点。
- 重新运行2-3直至建立集群。
K代表的是集群的数量。\({x^{(1)}, x^{(2)}, \dots,x^{(m)}}\)代表训练组。
在为数据选择最近的集群中心的步骤中，公式为：
\[c^{(i)} = argmin_k\ ||x^{(i)} - \mu_k||^2\]
其中\(c^{(i)}\)代表的是离数据\(x^{(i)}\)最近的集群中心的编号。
移动集群中心到下属数据的中心点，公式为:
\[\mu_k = \dfrac{1}{n}[x^{(k_1)} + x^{(k_2)} + \dots + x^{(k_n)}] \in \mathbb{R}^n\]
如果一个集群中心并没有任何下属的数据，可以为该中心重新随机设计一点，也可以直接消除该数据集。在一定数量的循环过后，模型会收敛，集群并不会有所变化。
优化目标
代价函数：
\[J(c^{(i)},\dots,c^{(m)},\mu_1,\dots,\mu_K) = \dfrac{1}{m}\sum_{i=1}^m ||x^{(i)} - \mu_{c^{(i)}}||^2\]
其中，\(c^{(i)}\)代表的是数据\(x^{(i)}\)所属的集群中心编号；\(\mu_{(k)}\)是集群中心；\(\mu_{c^(i)}\)代表的是\(x^{(i)}\)所属的集群中心。
优化目标是要\(min_{c,\mu}\ J(c,\mu)\)。代价函数的数值只会下降，不会上升。
随机初始
- 保证集群的数量少于训练样本数量。(K < m)
- 随机选择K个不重复的训练样本。
- 设置\(\mu_1,\dots,\mu_K\)在训练样本上。
k-平均演算法可能会困在局部最优解。为了减少发生的几率，算法模型需要至少跑几次以上。
集群的数量
肘部法则：为Cost J和K画图显示两者关系。Cost J在K到一定数量后，下降的幅度减少，趋于平缓。找出那一点的K值。（通常是Cost J的曲线是逐步下降的，那一转折点并不明显。）
下游目的(downstream purpose)：选择一个最能达到想要目地的K值。也就是说，在选择K个集群，出来的结果最为有用，能达到想要的目的。
数据降维
降到数据的维度，以达到减少臃肿数据的目的。同时，透过该方法也能做到数据可视化的目的。
主成份分析（Principal Component Analysis (PCA))
PCA的目的是要减少每一个特征到投影线的平均距离，也就是减少投影误差。
PCA并不是线性回归，线性回归是减少平方误差，PCA是减少垂直距离。
预先处理：
- 给予一个训练集\(x^{(1)}，x^{(2)}，x^{(3)}...x(m)\)
- 特征缩放\(\mu_j = \dfrac{1}{m}\sum^m_{i=1}x_j^{(i)}\)
- 用\(x_j^{(i)} - \mu_j\)取代\(x_j^{(i)}\)
- 缩放所有特征\(x_j^{(i)} = \dfrac{x_j^{(i)} - \mu_j}{s_j}\)
2D数据缩放到1D数据，可以用公式来表示：
\[\Sigma = \dfrac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T\]
PCA过程：
- 计算出协方差矩阵(covariance matrix)\(\Sigma = \dfrac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T\)
- 找出协方差矩阵的特征向量（eigenvector）
- 取出头K个栏位的矩阵计算出z \(z^{(i)} = Ureduce^T \cdot x^{(i)}\)
总结所有步骤：
Sigma = (1/m) * X' * X; % compute the covariance matrix
[U,S,V] = svd(Sigma); % compute our projected directions
Ureduce = U(:,1:k); % take the first k directions
Z = X * Ureduce; % compute the projected data points
由压缩数据重建，由1D变2D的话(\(z \in \mathbb{R} \rightarrow x \in \mathbb{R}^2\))：\(x_{approx}^{(1)} = U_{reduce} \cdot z^{(1)}\)
K的数值可以参考这方法：
- 计算出平均平方投影错误。\(\dfrac{1}{m}\sum^m_{i=1}||x^{(i)} - x_{approx}^{(i)}||^2\)
- 计算出\(\dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2\)
- 选一个最小的k值
\[\dfrac{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)} - x_{approx}^{(i)}||^2}{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2} \leq 0.01\]
可以这样表示：
\[\dfrac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \geq 0.99\]
使用PCA来减少过拟合问题是一个坏的用法。不要假设每个模型都需要PCA，先正常运行一次，再考虑是否需要PCA。
第九周
异常检测
设置\(x^{(i)}\)为i的特征。用数据设置模型p(x)。根据\(p(x) < ϵ\)识别一些不正常的活动。如果检测出过多/太多的异常，可以减少阀值\(ϵ\)。
高斯分布（正态分布）
x的高斯机会分布可以这样表示：\(x \sim \mathcal{N}(\mu, \sigma^2)\)。
完整的公式表示是：
\[\large p(x;\mu,\sigma^2) = \dfrac{1}{\sigma\sqrt{(2\pi)}}e^{-\dfrac{1}{2}(\dfrac{x - \mu}{\sigma})^2}\]
估算参数\(\mu\)为数据集的平均值：
\[\mu = \dfrac{1}{m}\displaystyle \sum_{i=1}^m x^{(i)}\]
然后估算参数\(\sigma^2\)，用平均误差公式：
\[\sigma^2 = \dfrac{1}{m}\displaystyle \sum_{i=1}^m(x^{(i)} - \mu)^2\]
假设数据集的每个数据都是独立的，我们可以得出公式：
\[p(x) = \displaystyle \prod^n_{j=1} p(x_j;\mu_j,\sigma_j^2) \]
评估检测系统
用训练集\(\lbrace x^{(1)},\dots,x^{(m)} \rbrace\)算出模型系统的\(p(x)\)值。
在验证集上，预测一下结果:
如果 \(p(x) < ϵ\)，y = 1
如果 \(p(x) \ge ϵ\)，y = 0
然后使用F1数值等方法评估模型。
使用异常检测的情况：
- 有一个很小数目的正样本和很多数目的负样本
- 有很多种不同的异常，难于从正样本中找出，未来异常可能跟以往的异常情况不一样。
使用监督学习的情况：
- 大数目的政府样本
- 有足够多的正样本，可以推测出新的正样本的样子。
可以为数据进行变形（transforms）以便适合高斯分布。（例如：\(\log(x)，\log(x+1)，\sqrt(x)，x^{1/3}\))
多元高斯分布
\[p(x;\mu,\Sigma) = \dfrac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-1/2(x-\mu)^T\Sigma^{-1}(x-\mu))\]
推荐系统
\(n_u \)为用户的数量，\(n_m \)为电影的数量，\(r(i,j) = 1\)为用户j评价了电影i，\(y(i,j) = 1\)为用户j给电影i的评分。
\(\theta^{(j)} \)为用户j的参数向量，\(x^{(i)} \)为电影i的参数向量。预测用户j在电影i的评分会是：\((\theta^{(j)})^Tx^{(i)}\)。
设置\(m^{(j)}\)为用户j评分过的电影数量。
\(\theta^{(j)}\)的数值可以透过这方法得出：
\[min_{\theta^{(1)},\dots,\theta^{(n_u)}} = \dfrac{1}{2}\displaystyle \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} ((\theta^{(j)})^T(x^{(i)}) - y^{(i,j)})^2 + \dfrac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^n(\theta_k^{(j)})^2\]
协同过滤（collaborative filtering）
代价函数可以更改为：
\[J(x,\theta) = \dfrac{1}{2} \displaystyle \sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \dfrac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2 + \dfrac{\lambda}{2}\sum_{j=1}^{n_u} \sum_{k=1}^{n} (\theta_k^{(j)})^2\]
算法分为几个步骤：
- 初始设置\(x^{(i)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)}\)为一些较小的随机数值。
- 用梯度下降的方法最小化\(J(x^{(i)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})\)数值。公式为：
\[\begin{gather}
x_k^{(i)} := x_k^{(i)} - \alpha\left (\displaystyle \sum_{j:r(i,j)=1}{((\theta^{(j)})^T x^{(i)} - y^{(i,j)}) \theta_k^{(j)}} + \lambda x_k^{(i)} \right) \cr
\theta_k^{(j)} := \theta_k^{(j)} - \alpha\left (\displaystyle \sum_{i:r(i,j)=1}{((\theta^{(j)})^T x^{(i)} - y^{(i,j)}) x_k^{(i)}} + \lambda \theta_k^{(j)} \right)
\end{gather}\] - 用\(\theta\)和特征\(x\)，预测出评分\(\theta^Tx\)。
第十周
随机梯度下降法
这方法不用一次性计算出所有数据的梯度，而是运用各个数据来缓慢寻找准确的梯度。
\[cost(\theta,(x^{(i)}, y^{(i)})) = \dfrac{1}{2}(h_{\theta}(x^{(i)}) - y^{(i)})^2\]
训练组的代价函数为：
\[J_{train}(\theta) = \dfrac{1}{m} \displaystyle \sum_{i=1}^m cost(\theta, (x^{(i)}, y^{(i)}))\]
该算法的步骤为：
- 随机打乱数据组的排序。
- 从第一个数据到最后一个数据，计算\(\Theta_j := \Theta_j - \alpha (h_{\Theta}(x^{(i)}) - y^{(i)}) \cdot x^{(i)}_j\)
小型批量梯度下降
假设每次批量处理10个数据：
\[\theta_j := \theta_j - \alpha \dfrac{1}{10} \displaystyle \sum_{k=i}^{i+9} (h_\theta(x^{(k)}) - y^{(k)})x_j^{(k)}\]
随机梯度下降收敛
较小的学习效率很有可能找到一个更好的结果。所以学习效率代数应该要缓慢下降。公式为：
\[\alpha = \dfrac{const1}{iterationNumber + const2}\]
MapReduce和平行数据处理
MapReduce会讲计算工作拆分，最后合并起来计算。
\[\Theta_j := \Theta_j - \alpha \dfrac{1}{z}(temp_j^{(1)} + temp_j^{(2)} + \cdots + temp_j^{(z)})\]
第十一周
机器学习系统流程：图片识别（Photo OCR）
图片识别流水线：图像->文字检测->文字拆分->文字识别
取得更多数据的方法
- 换背景
- 扭曲/反转
- 添加白噪/噪点
上线分析
分析出改进哪一个部分最具性价比。
假设该部分能100%准确做到想要的效果，最终结果能提升多少。