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)课堂笔记（二十二）：核函数和核方法

补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...

核函数（正定）

定义 , 满足：

1) 对称：

2) 正定： n个观测， 正定（或者非负定）。

举例：

  • 常数——
  • 内积—— ，或广义下，其中，从。

性质：

1. 封闭性

1) 正定，，则正定。

2) 正定，正定，则正定，正定。

3) 正定，，则正定。

4) 正定

5) 正定。

2. 归一性

正定，。

再生核Hilbert空间（RKHS)

（走神一下：关于这个命名的吐槽猛击 -> 翻译版、 英文原版Normal Deviate）

1. Hilbert空间：完备内积空间，可以视作欧氏空间的推广。。

在这个空间中，我们定义：

  • 加法：x+y
  • 数乘：, 。
  • 内积：对称性;线性 ，.
  • 零元素：若，则定义为零元素。
  • 完备性：如果且，则。（收敛到该空间内）。

2. 再生核Hilbert空间

给定正定，可以构造Hilbert空间H使得，；且构造一个，使得，即核函数可以写成内积形式。

这样对于，。

核方法

1. 基本思想

将线性模型推广到非线性模型的方法（其中较为简单的一种）

，从到的一个映射。举例：，这样就可以拓展为广义线性模型。

2. SVM

可以转化为：

令，，则

非线性变换之后，

注意此时的维数有变化（）。

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

如果各位更关心SVM后面的直觉，还是去看看Andrew Ng的相关课程吧...这里推导太多，直觉反而丢了一些。

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。

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

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

下节课讲的是降维方法。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十三）：原型方法和最近邻KNN

笔记（二十二）需要等我找到上一本笔记本再说，暂时不知道扔到哪里去了...汗。届时补上。

这一章主要是讲的原型方法（prototype）和最近邻（KNN）。相对而言直觉更强，公式没那么复杂。

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

1. 原型方法

1) 1-NN 最近邻居方法

最极端的情况：只找到最近的一位邻居。

数据集，输入，在中找到与最近的邻居，输出对应的类标记。

2) 类中心的方法

类中心： ，相当于对于一群有着同样类标记的点，对x取平均。

输入：，而后在所有类中心中与其最近的类中心。

输出：对应的类标记。

3) 对每个类可计算若干个“中心”（称之为原型或者样板，比如在每类中做聚类）。

输入：，而后在所有类中心中与其最近的类中心。

输出：对应的类标记。

4) K-NN方法

输入：，在中找到与最近的K个邻居。

输出：(最多的那一类，从众原则的感觉）。

由于这一类方法都比较懒，所以称之为lazy learning methods.

2. K-NN方法的错误率（渐近性质）

1) 结果

设为Bayes分类器的错误概率（最优分类器）；为1-NN分类器的错误概率。

则有：当样本数时，。接下来会证明这个优良的性质。

2) 分类问题

给定，则。

这里我们称 为先验分布，为类分布。从而

，称之为后验概率。

3) Bayes分类器

x对应的，即使得后验概率最大的k。

所以，，从。

4) 1-NN分类器

1-NN输出的是离x最近的对应的，则

。

由于只限训练集，而那部分只跟测试集有关，所以由独立性我们可以拆分为：

，则当时，,，上面一项可以收敛为，为后验概率（条件误差）。

5)由于，设为所有中最大的，则

6)。得证。

下一章会讲到聚类，然后就是降维了。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十一）：SMO算法

1. SVM优化问题

1) 原问题

2) 拉格朗日形式的表述

其中，。

3) 对偶问题

4) SVM分类器

(i)

(ii) 选，，然后。

(iii)SVM分类器

2. SMO算法

1) 基本思想：迭代下降、坐标下降

一次要选择两个变量（否则会破坏的约束），之后就可以解这个双变量优化问题。

2) 两个变量的优化

任取,作为变量，其他作为常量。

展开的矩阵大致如下：

目标函数=

这样,,,。

约束(对应对偶问题)

，这里d代表其余不改变的那些。

化到单变量的话，

所以，

  • 目标函数= ，最优条件
  • 约束 ，其中和分别为lower/upper bound。故必有最优点在L、H之间或者L、H之一。
  • ，，可以解得

这里虽然需要迭代很多次，但是迭代的每一步都比较快。

至于如何选择，第一个变量可以选择，同时最大。第二个变量选择最大的。