Category: 经济、IT观察与思考

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
游来游去 经济、IT观察与思考

数据分析职业病

分析是种职业病，融贯在每一分血液里，每一分骨髓里...去参加个Qcon看看人家的创意网站，然后心里各种痒痒，拉着思喆哥、堰平兄饭局讨论实现的原理也就罢了，最近只要一出门就习惯性的开始思考某些稍微“违背常理”或者“略显聪明”的现象...

比如这次去西安，在去的航班上，就开始思考起来了“航空公司的数据挖掘”....
-------------------回忆的分割线-------------
有些事情纯属职业病。这次上海飞西安坐的是南航的航班，一路折腾到飞机上就已经疲惫不已了，直接睡过去。

后面的一切毫无波折，如果不是临下飞机十几分钟的一段对话，我估计会对这段航行毫无记忆。只是突然间空姐的一句问候，"您是***女士么（我的本名）"，让我第一反应是我不是你们的金银卡啊，这也开始问候了？...然后笑意盈盈的递给我一张会员申请表。"您虽然还不是我们的会员，但是您是我们的潜在会员。所以请您加入我们南航明珠俱乐部"...

我第一反应是，"潜在会员"这个是怎么分析出来的？目测我大概有一年的时间没有飞过南航（在过去的半年时间我似乎都完全没有飞过），难道他们有个"沉睡用户苏醒监测"？要不就是，正巧这次我累计乘坐南航的次数达到了他们分析的阈值（比如10次）？要不就是，每次坐南航我都累积东航，让他们终于忍无可忍了...还是说，他们真有一个customer life value model，算出来我对他们的潜在价值了？

蛮有意思的是，我曾经有段时间周周飞南航，他们却从来对我爱理不理，所以我猜测他们的模型里面对于"reactivated"的顾客有个很高的权重。

到最后，南航猜的准吗？准，有可能是我确实在东航还有一些里程可以挥霍。不准，则是我现在飞行大都是私人旅行了，基本不可能象以前做咨询时候出差那般频率了，所以我的潜在价值肯定没有模型上估计出来的高。如果这个模型进一步分析"公务旅行"还是"私人旅行"，怕是效果会更好吧。不知道能不能通过机票代理来区分这两类客源...所以，准，却有点晚了。

当然对于垄断国企来说，这个CRM并不是那么重要，反正利润会一直在那里，国内的常客计划也发展不起来。只是感慨一下，这样的分析要是想做好，绝对离不开自己对于这项服务的亲身体验。只有飞的多了，才知道常客计划的最大引力和最关键时点。而后的分析，才会水到渠成吧？

职业病发作完毕...

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)。得证。

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