Unsupervised Learning 本周我们讲学习非监督学习算法,会学习到如下概念
首先需要知道的是无监督学习下,数据是没有标签的,所以可视化数据后是下面这样的效果(只有一种颜色)
K-Means算法步骤如下: 1.随机分配聚类中心(cluster centroid) 假设我们知道数据可以分为两类(这样做为了方便讨论),所以我们随机分配两个聚类中心(如下图一个红色,一个蓝色)。 2.聚类分配 遍历每一个数据x计算出其离哪个中心点更近,更近的标上和那个中心点相同的颜色。
3.移动聚类中心 完成步骤2后,计算每个聚类所有数据点的中心,该点即为新的聚类中心。
一般来说,求聚类中心点的算法你可以很简的使用各个点的(X,Y)坐标的平均值。
不过,另有三个求中心点的的公式:
1)Minkowski Distance公式——λ可以随意取值,可以是负数,也可以是正数,或是无穷大。
\[d_{ij}=\sqrt{ \sum_{k=1}^{n}|x_{ik} - y_{jk}|^λ }\]
2)Euclidean Distance公式——也就是第一个公式λ=2的情况
\[d_{ij}=\sqrt{ \sum_{k=1}^{n}|x_{ik} - y_{jk}|^2 }\]
3)CityBlock Distance公式——也就是第一个公式λ=1的情况
\[d_{ij}=\sum_{k=1}^{n}|x_{ik} - y_{jk}| \]
这三个公式的求中心点有一些不一样的地方,我们看下图(对于第一个λ在0-1之间)。
(1)Minkowski Distance (2)Euclidean Distance (3) CityBlock Distance
上面这几个图的大意是他们是怎么个逼近中心的,第一个图以星形的方式,第二个图以同心圆的方式,第三个图以菱形的方式。
4.重复2,3步骤,直到收敛,即中心不再变化或变化范围达到设定阈值
总结起来就是:
m:样本数据集的大小 d\(c^{(i)}\):第i个数据d\(x^{(i)}\)所属聚类的下标 d\(μ_k\):第k个聚类中心点
是的,k-means也有优化目标函数,如下:
\[minJ_(c^{(1)},……c^{(m)},μ_1,……μ_k)=\frac{1}{m}\sum_{i=1}^{m}{||x^{(i)}-μ_{c^{(i)}}||^2}\]
前面的步骤中都提到了随机初始化聚类中心,但是这样可能会得到局部最优点而不是全局最优,如下图所示:
所以为了解决这个问题,我们先需要重复多次的随机初始化,然后看最后得到的结果中是否有很多结果是相同的,如果有那么很可能就是全局最优解。 算法如下
本小节将讨论聚类个数K的如何选取。
如上图所示,我们可以通过计算不同k值所对应的损失函数的值,然后绘制成曲线,上面的曲线看上去就像是人的手臂,拐点(k=3)就是肘部,所以选择k=3是比较好的选择。
但是并不是所有时候都能得到上面那种比较理想的曲线,例如下面的曲线就不太好选择k值了。
上图左边按照 ‘S,M,L’ 划分,右边按照 'XS,S,M,L,XL' 划分,这也不是为办法中的办法2333.
在面对数据冗余的时候或者数据维度过大的时候可以通过降维来实现对数据的压缩从而提高计算效率。 例如 2D→1D
3D→2D
例如我们描述一个国家可以有50多种特征,但是想要可视化是不可能的,所以通过数据压缩后可以实现50D→2D,这样就能很好的看出各个国家之间的差距关系。
如下图是一些二维的点,现在需要将这些数据转化为一维数据点
PCA的方法是
乍一看感觉这个线性回归很像啊?但是还是有很大的区别的,见下图
左边是线性回归,右边是PCA。
区别如下:
1. 数据预处理 在使用PCA算法之前需要对数据机型预处理,方法有两种:
2. PCA算法描述
\[Σ=\frac{1}{m}\sum_{i=1}^{m}(x^{(i)})(x^{(i)})^T\]
左边的Σ是希腊大写的σ,右边的∑是求和符号
注意d\(x^{(i)}\)是(n,1)的向量,所以Σ是(n,n)的矩阵。
假设原始特征向量是n维的,我们想转化成k维,只需要取U矩阵的前k列即可,我们记这前k列向量为d\(U_{reduce}^{n×k}∈R^{n×n}\)。
\[z = (U_{reduce})^T*x\] \[ 维度表示: (R^{k×n}*R^{n×1}) = R^{k×1}\]
所以z是(k,1)向量。
上一步骤得到的d\(U\)可以理解成一个映射面,这里的z就是各个原始数据点x对应映射面的映射点z。
总结 1.数据预处理 2.计算协方差Σ: d\(Σ=\frac{1}{m}\sum_{i=1}^{m}(x^{(i)})(x^{(i)})^T\) 3.计算特征向量U: d\([U,S,V] = svd(sigma)\) 4.获取k维的d\(U_{reduce}^{n×k}\) 5.计算z: d\(z= (U_{reduce})^T*x\)
即已知降维后的向量z,如何还原成x?方法如下:
\[x = U_{reduce} * z\]
注意这里的还原并不是真正的还原成原始数据,因为这个公式得到的x是映射面U上的点,记为d\(x_{approx}\),虽然有些误差,但是误差一般很小。
\[minE_p = min\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-x_{approx}^{(i)}||^2\]
我们记原始数据离原点距离的平方的均值为
\[E_{total}=\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2\]
选择k值的标准就是满足下面的条件
\[\frac{E_p }{E_{total}}=\frac{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2}≤0.01\]
所以算法描述如下:
即k从1开始不断计算,知道满足小于等于0.01为止(也不一定非得是0.01,具体情况具体分析)。
之所以说这个方法比上一个简单,是因为下面两个式子可以等价计算。
即
\[\frac{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2}=1-\frac{\sum_{i=1}^{k}s_{ii}}{\sum_{i=1}^{n}s_{ii}}≤0.01\]
S矩阵只需要计算一次即可,所以只需要将k从1递增,知道满足小于等于0.01即可求出k值。
下面是使用PCA的一些误区