Tag: 相似矩阵

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十五）：降维和PCA

 降维

降维完全属于unsupervised learning了，即给定数据集，我们希望降到q维的。从这个角度来讲，降维和聚类还是有相通之处的，都是对于特征的提取。只是一个从行的角度出发，一个对列操作的感觉。

PCA（主成分分析，Principle Component Analysis）

个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||

1. 求,使得，且最大。

PCA

直觉上来讲，就是想寻找一个主方向。

这样，求解问题为：

。所以我们只需要求一阶导数即可。

设A为对称矩阵，则存在正交阵使得，其中为A的特征值矩阵，故(列向量为特征向量）。不失一般性，我们可以排序使得（从大到小排序）。

最大特征值:

同时为x的相关矩阵，，从而

2. 找到(q维的子空间）

将投影到该q维空间，这样，且最小。

A矩阵的范数：
tr表示矩阵的迹（对角线元素和）。

则上述问题等价于，求使得最小。

最小。

即使得最大（注意没有负号）。

称为数据的相似矩阵。

和均为对称阵，且两个阵有相同的特征值。记为A的秩，AA'的特征向量，A'A的特征向量，则，。做奇异值分解，则.

由此，求得的和前述结果等价。

回到PCA。如果降维后需要重构，则，解即可。

3. 对偶PCA。如果即数据非常高的时候，可以转置后再做。

4. KPCA （kernel）PCA也可以先用核函数，即实现非线性的降维。需要注意，降维的过程需要保持可逆。

---------------

PS. PCA不适合解决overfitting的问题。如果需要解决，加regularization项。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十四）：聚类

聚类讲的比较简单...怎么感觉老师不怎么待见unsupervised learning捏？...

---------------笔记开始---------------------

1. 一般概念

1)分类与聚类（分类标识）

评测纯度。我们有测试集，这样定义纯度为.

2) 输入

  • 特征向量的表示：。
  • 相似矩阵的表示：，其中相似度的计算可以是的内积。显然，向量表示很容易可以计算相似度表示。
  • 距离矩阵的表示（不相似度）：，其中距离可以用二阶范数定义，比如。

3) 输出： ，对应K个聚类。这里还分为：

  • 非层次的
  • 层次的（类似于树结构）

2. K-means方法（非层次聚类）

（注意不要和KNN搞混了，都是K开头的...）

1) K-means方法（特征表示）

输入：，K——聚类的个数。

算法：

初始化，随机选定类中心.

  • (i)根据分配到距离最近的类。
  • (ii)修改，使得。重复上面两步。

2) K-medoids方法（相似度表示）

输入：s,k

初始化。然后根据分配，再按照确定新的中心。

3) 模糊的K-means方法

输入：，K

初始化。

  • (i) ,计算，然后根据这个距离的比重来“软”分配(需要归一化分配权重）。
  • (ii) ，利用中的进行加权平均。

重复上述两步。

4) 谱聚类（向量表示）

输入：，K

然后对原始数据做转换，形成新的数据集，然后再做K-means聚类。

其中转换的步骤如下：

  • (i) 计算相似矩阵S
  • (ii) 计算L=D-S，其中，。
  • (iii)计算L最小的K个特征值对应的特征向量
  • (iv)让U=，则是U的第i行，这样就从p维降到了K维。
  • (v)对Z进行K-means聚类。

3. 层次聚类

1) 自底向上的方法（聚合）

初始：每个都为一类

而后对于最相似的两类，合并到一类。对于类的最相似，可以定义为距离最近的类。而对于距离，则可以定义为三者之一：

  • (i) ，称之为单连。
  • (ii) ，称之为全连。
  • (iii) .

2) 自顶向下的方法（分裂）

初始：所有的x作为一类。选用一种非层次的方法进行聚类，递归使用。

例子：二分法。

初始：，。而后选择离G最远的一个点g。

修改，。重复步骤，选择离H近的离G远的逐渐加入H。

直到分不动了，彻底分为两类。

---------------------

下节课讲的是降维方法。