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之一。
  • ,可以解得

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

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