Category: 经济、IT观察与思考

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

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

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

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

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

Categories
读书有感

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

这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍，现在又来了-_-||

附赠个老的掉牙的段子...

有人问经济学家一个数学问题，经济学家表示不会解...

然后那个人把这个数学问题转成了一个等价的最优化问题，经济学家立马就解出来了...

好吧，我还是乖乖的赘述一遍对偶问题吧，表示被各种经济学最优化问题折磨过的孩子这点儿真是不在话下。

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

1. 对偶问题的一般情况

1) 优化问题

一个典型的最优化问题形如：

(不等式约束)

（等式约束）

2) 优化问题的Lagrange （拉格朗日）函数

3) 对偶函数

称为该优化问题的对偶函数。此时，

，显然这个时候一阶偏导数为0。

4) 对偶问题

我们称为原优化问题的对偶问题，可化为最优化问题的标准形式。

如果原优化问题为凸优化，则必为凹函数，从而最终的标准形式依旧是一个凸优化问题。

5) 弱对偶性

令为原问题的解，则，且，.

令为对偶问题的解，则; .

定理（弱对偶性）：，即对偶问题的优化值必然小于等于原问题优化值。

6) 强对偶性

当时，两者具有强对偶性；满足该条件的称之为constraint qualifications，如Sliter定理。

强对偶性满足的时候，原优化问题就可以化为一个二步优化问题了。

7) KTT条件（库恩-塔克条件）

局部最优化成立的必要条件：

（一阶条件）

注：SVM满足强对偶性，所以可以直接解对偶问题。

2. 对偶问题应用于SVM

1) SVM的最优化问题

上节课可知，SVM的最优化问题为：

写成标准形式就是

这样这里总计有2N个约束条件。

对应的Lagrange函数为：

这样一阶条件就是


这样最后我们有.

3) 对偶函数

这里的对偶函数就是

4) 对偶问题

5) KKT条件

6) SVM分类器

  • 解对偶问题，得到,
  • 计算
  • 计算：找到一个（非边界上），从而满足。由，我们可得
  • 平面分类器: , ，故只与内积有关。

这样下节课就会讲到解对偶问题的方法，以及SVM和kernel methods的联系。