聚类
之前的课程中我们学习的都是监督学习相关的算法,现在来开始看非监督学习。非监督学习相对于监督非学习来看,其使用的是未标记的训练集而监督学习的是标记的训练集。换句话说,我们不知道向量y的预期结果,仅仅只是拥有一个可以找到结构的特征的集合。
其中一种可能的结构是,所有的数据可以大致地划分成两组,这种划分的算法称为聚类算法。 这是我们第一种 无监督学习算法。在很多场景下我们会使用聚类的方式来解决非监督学习问题,比如市场分割,社会网络分析等等。
K-means
K-Means算法是最流行和广泛使用的自动将数据分组到相干子集的算法,其算法的步骤主要是:
首先选择 K 个随机的点,称为聚类中心(cluster centroids);对于数据集中的每一个数据,按照距离K个中心点的距离,将其与距离最近的中心点关联起来,与同一个中心点关联的所有点聚成一类。计算每一个组的平均值,将该组所关联的中心点移动到平均值的位置。重复步骤2-4直至中心点不再变化。
下图展示了对n个样本点进行K-means聚类的效果,这里k取2。
用 $μ^1,μ^2,...,μ^k$ , 来表示聚类中心,用 $c^{(1)},c^{(2)},...,c^{(m)}$ ,来存储与第 i 个实例数据最近的聚类中心的索引,K-均值算法的伪代码如下:
Randomly initialize K cluster centroids mu(1), mu(2), ..., mu(K)Repeat:for i = 1 to m:c(i):= index (from 1 to K) of cluster centroid closest to x(i)for k = 1 to K:mu(k):= average (mean) of points assigned to cluster k
算法分为两个步骤,第一个for循环是赋值步骤,即:对于每一个样例i,计算其应该属于的类。第二个for循环是聚类中心的移动,即:对于每一个类 K重新计算该类的质心。
在K-means算法中的变量有下面几个:
用这些变量我们可以定义代价函数为:
$$ J(c^{(1)},...,c^{(m)},μ_1,...,μ_K)=\dfrac {1}{m}\sum^{m}_{i=1}\left\| X^{\left( i\right) }-\mu_{c^{(i)}}\right\| ^{2} $$
我们的的优化目标便是找出使得代价函数最小的$c^{(1)},c^{(2)},...,c^{(m)} ,和 μ^1,μ^2,...,μ^k $。回顾刚才给出的: K-均值迭代算法,我们知道,第一个循环是用于减小$c^{(i)}$引起的代价,而第二个循环则是用于减小${{\mu }_{i}}$引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数,不然便是出现了错误。
随机初始化
在运行K-均值算法的之前,我们首先要随机初始化所有的聚类中心点,下面介绍怎样做:
我们应该选择 K<m,即聚类中心点的个数要小于所有训练集实例的数量随机选择 K 个训练实例。令 K 个聚类中心分别与这 K个训练实例相等
K-均值的一个问题在于它有可能会停留在一个局部最小值处,而这取决于初始化的情况。为了解决这个问题,我们通常需要多次运行K-均值算法,每一次都重新进行随机初始化,最后再比较多次运行K-均值的结果,选择代价函数最小的结果。这种方法在K较小的时候(2--10)还是可行的,但是K如果较大,这么做也可能不会有明显地改善。
for i = 1 to 100:randomly initialize k-meansrun k-means to get 'c' and 'm'compute the cost function (distortion) J(c,m)pick the clustering that gave us the lowest cost
选择聚类数
K的选择往往是任意的或者说是模糊不清的,通常是需要根据不同的问题人工进行选择的。选择的时候我们需要思考运用K-均值算法聚类的动机是什么,然后选择能最好服务于该目的标聚类数。
当人们在讨论,选择聚类数目的方法时,有一个可能会谈及的方法叫作“肘部法则”。将代价J和聚类K画在图中。代价函数会随着K的增加而降低然后趋于平缓,我们要做的就是找到J开始趋于平缓时的K。然而很多时候,曲线经常是很平缓的,这时的肘部就很不明显。(note:J一般都是随着K的增加而降低,但如果K出现了错误的局部最优则会导致不一样的结果)。
降维
使用降维的动机
有几个不同的的原因使你可能想要做降维。一是数据压缩,如果我们有大量多余的数据时,我们可能想降低特征的维度,为此可以找到两个高度相关的特征,将其画出图像然后做一条直线来同时描述这两个特征。二是数据可视化,因为数据超过三维就很难可视化了,因此有时候需要将维度下降到3或者以下来达到可视化的目的。
主成分分析问题
主成分分析(PCA)是最常见的降维算法。其定义是想把数据从n维降到k维(k小于n),就在这个空间里面找k个单位向量来表示数据,使得数据点投影到这个面上的误差最小。如下例子:2到1和3到2:
虽然同是一条直线拟合,但PCA和线性回归是不同的:
计算loss的方式不同(垂直)。PCA没有标签Y(非监督)。
PCA算法
PCA 减少 n 维到 k 维:
第一步是均值归一化。我们需要计算出所有特征的均值,然后令$x_j=x_j-μ_j$。如果特征是在不同的数量级上,我们还需要将其除以标准差$σ^2$。
第二步是计算协方差矩阵(covariance matrix) Σ :$\sum=\frac {1}{m}\sum^{n}_{i=1}\left( x^{(i)}\right) \left( x^{(i)}\right) ^{T}$
第三步是计算协方差矩阵Σ的特征向量(eigenvectors):
在 Octave 里我们可以利用奇异值分解(singular value decomposition)来求解,[U, S, V]= svd(sigma)。
$\Sigma=\frac {1}{m}\sum^{n}_{i=1}\left( x^{(i)}\right) \left( x^{(i)}\right) ^{T}$
对于一个 n×n 维度的矩阵,上式中的 U 是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从 n 维降至 k 维,我们只需要从U中选取前k个向量,获得一个n×k维度的矩阵,我们用$U_{reduce}$表示,然后通过如下计算获得要求的新特征向量 $z^{(i)}=U^{T}_{reduce}*x^{(i)}$。
其中x是n×1维的,因此结果为 k×1 维度。我们不对方差特征进行处理。
选择主成分的数量
在PCA算法中我们把n维特征变量降维到k维特征变量。这个数字k也被称作主成分的数量或者说是我们保留的主成分的数量。我们先来思考两个值:
第一个是:PCA所做的是尽量最小化平均平方映射误差(Average Squared Projection Error)。第二个是:我还要定义一下数据的总变差(Total Variation)。它的意思是 “平均来看我的训练样本距离零向量多远?
我们把两个数的比值作为衡量PCA算法的有效性
定义一个阈值然后实验k,看看那个最小的k合适。计算步骤如下:
这里有个技巧:svd函数会返回一个对角矩阵S,他的元素可以很快的计算这个阈值。
主成分分析法的应用建议
PCA算法主要有以下用途:
压缩:
减少内存和磁盘的占用提升算法的速度
可视化:
降维到二维或者三维
有些人觉的PCA也可以用来防止过拟合,但是这是不对的。应该用正则化。正则化使用y标签最小化损失函数,使用了y标签信息。而PCA只单纯的看x的分部就删除了一些特征,损失率很多信息。另一个常见的错误是,默认地将主要成分分析作为学习过程中的一部分,这虽然很多时候有效果,最好还是从所有原始特征开始,只在有必要的时候(算法运行太慢或者占用太多内存)才考虑采用主要成分分析。
以上为吴恩达机器学习非监督学习这一章节的内容。
参考链接
/p/43488853
/u012052268/article/details/78847915#3维度约简-主成分分析法pca