Machine Learning (4) - Unsupervised Learning
Clustering - K-means Algorithm
 - Unsupervised Learning/1495320402756.png)
 - Unsupervised Learning/1495320502218.png)
步骤
- Randomly initialize K cluster centroids .
1) Should have
2) Randomly pick K training examples
3) Seteuqal to these K examples.
- Repeat
for i=1 to m:= index (from 1 to K) of cluster centroid closest to x^{(i)}
将归到离其最近的centroid
for k = 1 to K:= average (mean) of points assigned to cluster k.
按照归到该centroid的所有sample来相应地移动该centroid
 - Unsupervised Learning/SVGcaa49b5ed0437e76689324768d138893)
调优
目的
为了避免因为初始化不当，而产生local optima
Cost Function
 - Unsupervised Learning/SVG04c8c98dae72dc923b894d03fb65031a)
调优就是使Cost Function最小化。具体的做法就是多做几次K-means (Andrew推荐100次)，选取Cost Function最小的一组。
选择cluster number
Elvow method (肘关节法)
 - Unsupervised Learning/1496198213650.png)
 - Unsupervised Learning/1496198240034.png)
Dimensionality Reduction - Principal Component Analysis (PCA)
Dimensionality Reduction = 降维, 3D->2D
步骤
- Feature scaling/mean normalization.
1)
2)
3) (optional)，
是标准差
- Compute “covariance matrix”
- 调用系统库，Compute “eigenvectors” of matrix
:
[U,S,V] = svd(Sigma); Ureduce = U(:,1:k); z = Ureduce'*x;
 - Unsupervised Learning/SVG29d009b437dd9b26b6e8985fa671b39a)
 - Unsupervised Learning/SVGa209c958af5d3317adb0077bd995e64d)
 - Unsupervised Learning/SVGc7eb48feca7891ec3968e1826a2e630d)
Reconstruct
x = Ureduce * z
 - Unsupervised Learning/1496209550430.png)
Choose k
Typically, choose k to be smallest value so that,
 - Unsupervised Learning/SVGcd56e05d3418bc206818f09072bd9e32)
另外一种通过svd函数计算variance的方法
- Start from k=1
[U,S,V] = svd(Sigma)- Pick the smallest k.
 - Unsupervised Learning/SVG0aba91df8094a8c9263f3240b6b11801)
Application of PCA
- Compression: 节省数据空间，提升计算速度
- Visualization: k=2 or k = 3
不要滥用PCA。例如，用PCA减少feature set来消除Overfitting
Before implementing PCA, first try running whatever you want to do with the original/raw data
 - Unsupervised Learning/SVG4998374b22101c20dc233b891c38c800)
Anomaly detection algorithm
我将之翻译为异常检测。实际就是对属于正态（或高斯）分布的特征量的非正常检测。
- Choose features
that you think might be indicative of anomalous examples.
- Fit parameters
- Given new example
, compute
- 概率
- Anomaly if
 - Unsupervised Learning/SVGe1b9cb48606138bd958660ce3e24168e)
 - Unsupervised Learning/SVG75cc786f63053982833ee7989a021761)
 - Unsupervised Learning/SVG34cf43bcc554e2db196e00450a1d6ac5)
 - Unsupervised Learning/SVGf1b949461f892e9189b45c2b7156ec3e)
 - Unsupervised Learning/SVGdbcdfbb0502caf852af21ad81e64e206)
高斯分布概率密度公式：
 - Unsupervised Learning/SVG1a7177056fcb3d346d8cce697bf5417b)
结果评估
如何对数据分类进行training和validate
Aircraft engines motivating example
10000 good(normal) engines
20 flawed engines (anomalous)Training set: 6000 good engines
CV: 2000 good engines(y=0), 10 anomalous(y=1)
Test: 2000 good engines(y=0), 10 anomalous(y=1)
也就是把anomalous的sample省下来做validate和test用
特征量的选取
如果特征量不符合正态分布怎么办？按Andrew的建议是进行变换，则能得到近似正态的分布，如下：
 - Unsupervised Learning/1496744051794.png)
Andrew在视频中用Octave命令行做了live demo：
 - Unsupervised Learning/1496744359543.png)
讲义中提到的Error Analysis指的是：
有一些异常情况是，特征向量的各分量都在大概率的点，但是当某些分量组合时，会是小概率事件，则此时需要产生新的特征向量。例如：Andrew的例子，当CPU load相对较大，但仍在正常范围，但是network traffic却很小，但仍然在正常范围。这时你就需要一个变量，比如 - Unsupervised Learning/SVGe790c9e07d042ec591211ba1862b5df3)
 - Unsupervised Learning/SVGe4c7400fd5f5688c80b5d4073895402b){kind=small}
Multivariate Gaussian distribution
前面的Anomaly Detection基于各特征分量是独立分布的情况，如果是非独立分布就采用上面提到的Error Analysis的方法。而Multivariate Gaussian则是对非独立分布的补充，也就是说上面的Anomaly Detection其实是Multivariate Gaussian的一种特殊情况。
Andrew给出了矢量化的Multivariate Gaussian的概率密度公式：
 - Unsupervised Learning/SVG97c2efbf405de50647e276864ed7ae38)
 - Unsupervised Learning/SVG3e6b22d60daffa2daa82a596ca77736f){kind=small}
 - Unsupervised Learning/SVG55093ecf700acd98f8e23971b128f2fb){kind=small}
其中
为
- wiki - 行列式
简单摘取两张计算矩阵行列式的插图：在上面给出的公式里，Covariance Matrix即
 - Unsupervised Learning/1496745897356.png)
Original model和multivariate model都可以检测到上面举的CPU load和network traffic的例子中的情况。那要如何选择呢？Andrew给出了对比：
 - Unsupervised Learning/1496746985199.png)
Anomaly detection vs. supervised learning
 - Unsupervised Learning/1496580685327.png)
 - Unsupervised Learning/1496580714267.png)
Recommender Systems
Content-based recommender systems
这个问题，其实就是已知每部电影的特征(特征向量)，以及用户对电影的评分，来推测用户对没看过的电影的评分。看下面的表格：
 - Unsupervised Learning/1497231459572.png)
 - Unsupervised Learning/SVGf2aed53219fc8843b375e3c222e3538e){kind=small}
: 用户数
: 电影数
: 用户j给电影i评分了
: 用户的真实评分
: hypothesis，推测评分
Gradient Descent:
for k = 0:  - Unsupervised Learning/SVGb9fc9d2c7020559486a69ca0cc966589)
for k - Unsupervised Learning/SVG04de81d576ce79f945575d59b5754b6f){kind=small}
 - Unsupervised Learning/SVG84cdaecb7f2fa1c2838171840d086e7f)
Collaborative filtering
假设在前面一节的training中， - Unsupervised Learning/SVG88502c86edcc6c6fe8ee0dbd8a1a00f5)
 - Unsupervised Learning/SVG27e556cf3caa0673ac49a8f0de3c73ca)
- Initialize
to small random values.
- Minimize
using gradient descent (or an advanced optimization algorithm).
 - Unsupervised Learning/SVG7e8d704796c1d03480ee649a193e1128)
 - Unsupervised Learning/1497233522468.png)
- For a user with parameters
 - Unsupervised Learning/SVG45e726186266b4456810a6a4829609f8)
因为存在未给任何电影评分的用户，如果不做特殊处理，则这些用户对所有电影的预测评价都会是0分，具体Andrew在视频中给出论证。所以需要mean normalization，具体做法是：
 - Unsupervised Learning/SVGc799a7ea9c6e76572d9c3d5c8529443f)
 - Unsupervised Learning/SVGb5937bb6db10bc61cd036e6a59fe4722)
- 不用标准差除，因为评分本来就在近似的range
1
Collaborative filtering矢量写法是：
 - Unsupervised Learning/SVG78fc46c06fb75ec479d40577b745fcbb)
 - Unsupervised Learning/SVGb83395c8c2a8336574abfaf1ab3f78d4)
就是Low rank matrix。当要给用户推荐的时候，
足够小的时候，就可以认为i和j足够相似。