Clustering

聚类(Clustering)

无监督学习(Unsupervised Learning)

数据没有任何标签信息

聚类算法

将一系列无标签的训练数据，输入到一个算法中，得到给定数据的内在结构。我们可能需要某种算法帮助我们寻找一种结构。

应用：

• 市场分割
• 社交网络分析
• 组织计算机集群
• 研究星系形成

K-均值算法(K-Means Algorithm)

K-均值算法是普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的簇。

算法步骤:

• 选择k个随机的点作为聚类中心(cluster centroids)
• 将每个数据与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类
• 计算每一个组的平均值，将该组的中心点移动到平均值的位置
• 重复2-3步直至中心点不再变化

伪代码

Repeat {
    for i = 1 to m
       c(i) := index (form 1 to K) of cluster centroid closest to x(i)
    for k = 1 to K
       μk := average (mean) of points assigned to cluster k
}

优化目标(Optimization Objective)

K-均值最小化问题，是要最小化所有数据与所关联的聚类中心点之间的距离之和，因此其代价函数(畸变函数)为:

$$J(c^{(1)},...,c^{(m)},\mu^1,...,\mu^k)=\frac{1}{m}\sum_{i=1}^{m}||X^{(i)}-\mu_{c^{(i)}}||^2$$

我们知道，第一个循环是用于减小 引起的代价，而第二个循环则是用于减小 引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数，不然便是出现了错误。

随机初始化(Random Initialzation)

步骤

• 选择$K\leq m$
• 随机选择$K$个训练实例，然后令$K$个聚类中心分别与这$K$个训练实例相等

可能会停留在一个局部最小值，这取决于初始化的情况
为了解决这个问题，我们通常需要多次运行K-均值算法，每一次都重新进行随机初始化，最后再比较多次运行K-均值的结果，选择代价函数最小的结果。这种方法在k较小的时候还是可行的，但是如果k较大，这么做也可能不会有明显地改善。

选择K

没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选择的时候思考我们运用K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。

肘部法则

当畸变值下降得慢的时候，说明此时的聚类个数较为合理

降维(Dimensionality Reduction)

数据压缩(Motivation I_Data Compression)

例如两种仪器对同一个东西测量的结果不完全相等，但是都特征却有些重复，这时候需要进行降维。

将数据从三维降至二维:
将三维向量投射到一个二维平面上，强迫所有数据在同一平面上，降至二维的特征向量。

可视化(Motivation II_Visualization)

只有三维以内的数据才方便可视化

问题

降维算法只负责减少维数，新产生特征的意义需要自己发现

主成分分析(Principal Component Analysis)

主成分分析是常见的降维算法，要做的是找到一个方向向量，把所有数据投射到该向量上时，我们希望投射平均均方误差尽可能地小。

主成分分析与线性回归的比较：
主成分分析最小化的是投射误差，而线性回归尝试最小化预测误差。线性回归的目的是预测结果，而主成分分析不作任何预测。

PCA技术的好处：对数据进行降维处理，对新求出的“主元”向量的重要性进行排序，根据需要选取最重要的部分。将后面的维数省去，可以达到降维从而简化模型或者对数据进行压缩。PCA无参数限制，不需要人为干预，但是如果对数据有先验知识，这却是一个缺点，因为无法通过参数化对处理过程进行干预。

主成分分析算法

1. 均值归一化，计算出所有特征的均值，令$x_j=x_j-\mu_j$,如果特征在不同数量级上，还需要进行特征缩放，将其除以标准差$\sigma$
2. 计算协方差矩阵(covariance matrix)
   $\sum=\frac{1}{m}(x^{(i)})(x^{(i)})^T$,
   这是一个n*n的矩阵。

3. 计算协方差矩阵$\sum$的特征向量(eigenvectors)
   奇异值分解:

   [U,S,V] = svd(sigma)
   对于一个 n×n维度的矩阵，上式中的U是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从n维降至k维，我们只需要从U中选取前k个向量，获得一个n×k维度的矩阵，我们用$U_{reduce}$表示，然后通过如下计算获得要求的新特征向量：

   $$z^{(i)} = U^T_{reduce} * x^{(i)}$$

选择主成分分析的数量

主成分分析是减少投射的平均均方误差:

$$\frac{1}{m}\sum_{i=1}^m||x^{(i)-x_{approx}^{(i)}}||^2$$

训练集的方差为$\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2$
如果我们希望平均均方误差与训练集方差比例小于1%,这意味着原本数据偏差的99%都保留下来了。
我们可以先令k=1，然后进行主要成分分析，获得 和z，然后计算比例是否小于 1%。如果不是再令k=2，如此类推，直到找到可以使得比例小于1%的最小k值（原因是各个特征之间通常情况存在某种相关性）

在svd函数中，S是一个n*n矩阵，只有对角线上有值，其他单元都是0，我们使用这个矩阵来计算平均均方误差与训练集方差的比例:

$$1-\frac{\sum_{i=1}^mS_{ii}}{\sum_{i=1}^{k}S_{ii}}\leq 1\%$$

重建的压缩表示

$$X_{approx} = U_{reduce}Z$$

主成分分析法应用建议

• 如果我们有交叉验证集合测试集，也采用对训练集学习而来的$U_{reduce}$
• 一个常见错误使用主要成分分析的情况是，将其用于减少过拟合（减少了特征的数量）。这样做非常不好，不如尝试正则化处理
• 另一个常见的错误是，默认地将主要成分分析作为学习过程中的一部分。这虽然很多时候有效果，最好还是从所有原始特征开始，只在有必要的时候（算法运行太慢或者占用太多内存）才考虑采用主要成分分析。