我一想到明天要面试，我就贼紧张。赶紧好好复习一下吧。
主成分分析PCA 线性判别分析LDA 矩阵奇异值分解SVD 深度学习SparseAutoEncoder LASSO 小波分析法 拉普拉斯特征映射
最小误判概率准则 最小损失准则
| 决策树 | ID3/C4.5 | CART |
|---|---|---|
| 相同 | 都是基于信息论的决策树算法 | |
| 不同1 | ID3是信息增益，C4.5是信息增益比 | CART中用于选择变量的不纯性度量是Gini指数 |
| 不同2 | C4.5/ID3不一定是二叉树 | CART一定是二叉树 |
简介
设一个\(m\times n\)的矩阵\(M\),它的SVD分解是： \[M=UΣV^*\] 其中： - \(U\)是一个\(m\times m\)的酉矩阵。(我的理解：酉矩阵是在复数空间上，类似正交矩阵的矩阵。它有很多不错的性质。可以在我上一篇博客里看到) - \(Σ\)是\(m\times n\)的矩形对角矩阵，并且在对角线上的元素都是非负实数\(σ_i\)，称为\(M\)的奇异值 - \(V^*\)是一个\(n\times n\)的酉矩阵，也是\(V\)的共轭转置矩阵。
首先，我们对正交矩阵进行一些回顾。
正交矩阵回顾
从上一节我们知道，正交矩阵对应的变换是不会改变向量长度的。即，对于向量\((a,b)\)，正交矩阵\(U\)，变换后的向量\(U(a,b)\)的长度与\((a,b)\)是相等的。这个正交变换只是对\((a,b)\)做了旋转或者镜射等操作。
在讨论SVD之前，我们先讨论矩阵的特征值分解（EVD）。
回顾特征值分解，特征值分解是把一个n阶实对称矩阵分解为下面的形式： \[A=QΣQ^{-1}\] 其中： - \(Q\)是这个矩阵\(A\)的特征向量组成的矩阵，是一个正交矩阵 - \(Σ\)是一个对角阵，每个对角线上的元素就是一个特征值
此时假设有一个\(x\)向量，用\(A\)将这个向量\(x\)变换到\(A\)的列空间中，即： \[Ax=QΣQ^{-1}x=QΣQ^Tx=QΣ(Q^Tx)\] 1. 首先进行\(Q^Tx\)操作。\(Q\)和\(T^T\)都是正交阵，那么\(Q^T\)对\(x\)的变换是正交变换，它将\(x\)用新的坐标系，这个坐标系就是\(A\)的所有正交的特征向量构成的坐标系。 我们如果将\(x\)用\(A\)的所有特征向量来表示的话，即表示为\(x=a_1x_1+a_2x_2+...+a_mx_m\)，则通过第一个变换，\((Q^Tx)=[a_1,a_2,...,a_m]'\),即
2. 紧接着，在新的坐标系表示下，由中间那个对角矩阵对新的向量坐标换，其结果就是将向量往各个轴方向拉伸或压缩：
从上图可以看到，如果A不是满秩的话，那么就是说对角阵的对角线上元素存在0，这时候就会导致维度退化，这样就会使映射后的向量落入m维空间的子空间中。 3. 最后一个变换就是U对拉伸或压缩后的向量做变换，由于U和U'是互为逆矩阵，所以U变换是U'变换的逆变换。
因此，从对称阵的分解对应的映射分解来分析一个矩阵的变换特点是非常直观的。假设对称阵特征值全为1那么显然它就是单位阵，如果对称阵的特征值有个别是0其他全是1，那么它就是一个正交投影矩阵，它将m维向量投影到它的列空间中。
上面的矩阵\(A\)要求必须是n阶实对称的。那么对于任意的\(M\times N\)矩阵，能否找到一个相似的变换呢？这就是SVD分解的精髓所在。
在上面的特征值分解中，我们能找到一个变换\(A\)，将一组正交基映射到另一组正交基。
这样我们就证明了，这个变换是存在的。
接下来，我们将向量组\({u_1,u_2,...,u_k}\)扩充为\(R^m\)中的标准正交基\(u_1,u_2,...,u_r,...,u_m\)，则： \[AV=A(v_1,v_2,...,v_n)=(Av_1,Av_2,...,Av_k,0,0,...,0)\] 而由之前的推导我们知道，\(Av_i=u_i\alpha_i(奇异值)\)，因此上式变为 \[AV=(u_1\alpha_1,u_2\alpha_2,...,u_k\alpha_k,0,0,...,0)=UΣ\]
即： \[A=UΣV^T\]
这就表明任意的矩阵\(A\)是可以分解成三个矩阵。\(V\)表示了原始域的标准正交基，\(U\)表示经过\(A\)变换后的co-domain的标准正交基，\(Σ\)表示了\(V\)中的向量与\(U\)中相对应向量之间的关系。
其中： - \(A是m\times n维度\) - \(U叫左奇异向量，是m\times m维的正交矩阵\) - \(Σ叫右奇异向量，是n\times n维的对角矩阵，但实际上只有左上角的k阶非零\),即:
从大小上来看：
即：
参考文献机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用提到，奇异值和特征值可以对应起来。
在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解： \[A_{m\times n}\approx U_{m\times r}Σ_{r_\times r}V^T_{r\times n}\] r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子： 
右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。
小例子
接下来我们给出一个用python的SVD分解小例子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#coding=utf-8
# 首先做一些数据声明
from sklearn.decomposition import TruncatedSVD
from matplotlib import pyplot as plt
from numpy import random
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
import pandas as pd
fig = plt.figure()
ax = Axes3D(fig)
ax=plt.subplot(111,projection='3d')
ax.set_zlabel('Z') #坐标轴
ax.set_ylabel('Y')
ax.set_xlabel('X')
X = np.arange(0, 4, 0.125) + 0.2 * random.randn(32)
Y = np.arange(0, 4, 0.125) + 0.2 * random.randn(32)
Z = np.arange(0, 4, 0.125) + 0.2 * random.randn(32)
# 数据是3维×32维
data = [[x, y, z] for x, y, z in zip(X, Y, Z)]
1 | # 分解，n_components是主元素个数，也就是维度 |
当降到二维，再还原时，我们看到： 
降到一维，再还原，我们看到： 
\[A=UΣV^T\]
吴军老师在矩阵计算与文本处理中的分类问题中谈到：三个矩阵有非常清楚的物理含义。 - \(U\)中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。 - \(V^T\)中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。 - 因此，我们只要对关联矩阵\(A\)进行一次奇异值分解，我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。
参考文献机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用给出了一个理解这句话的例子，此处不再阐述。
我在做比赛的过程中，曾尝试过用SVD分解做APP特征，来描述APP之间的相似性特征。但效果不佳。推测原因是维度过低（几百万维压到了20维）。项目在这里
但这里我还是打算好好看看。万一以后用到呢？
参考文献SVD在推荐系统中的应用以经典的电影评分问题为例，讲述了整个过程。参考文献SVD在推荐系统中的应用用matlab进行了详细的过程复现。
我的理解： SVD分解 SVD分解是：\[A_{m\times n}=U_{m\times m}Σ_{m\times n}V^T_{n\times n}\] 其中： - \(Σ_{m\times n}\)是一个对角阵。 - \(U_{m\times m}\)表示行间元素（一般是用户）的相似度 - \(V^T_{n\times n}\)表示列间元素（一般是商品）的相似度 根据好友张思遥的理解，是通过数学的方法，来将行和列的拆开，放在两个矩阵里。 降维 根据PCA理论（强烈建议看斯坦福大学安德鲁老师的机器学习课程，这里有前辈的笔记斯坦福ML公开课笔记14——主成分分析，我们可以取前\(r\)维来对矩阵进行近似表示： \[A_{m\times n}\approx U_{m\times r}Σ_{m\times n}V^T_{r\times n}\]
1 | # 基本的SVD，但这个很难得到U |
特征值与特征向量
如果一个向量\(v\)是方阵\(A\)的特征向量，那么： \[Av=\lambda v\] - \(\lambda\):特征值 - \(v\):特征向量 把\(A\)乘到\(v\)上，得到一个\(\lambda v\)，也就是意味着我们得到了一个方向未变但在长度上有伸缩改变的向量（方向未变不准确，有可能变反向）。这是让\(A\)乘以他的特征向量表现出来的性质。 也就是说，\(v\) 在 \(A\) 的作用下，保持方向不变，进行比例为\(\lambda\) 的伸缩
因此： - 特征向量所在直线上的向量都是特征向量； - 特征向量所在的直线（包含了所有特征向量），叫特征空间；
特征值分解
假设矩阵\(A\) 有n个线性无关的特征向量\([v^{1}, v^{2}, ..., v^{n}]\) ，对应着特征值\([\lambda_1, \lambda_2,...,\lambda_n]\) 。我们将特征向量连成一个矩阵，使得每一列是一个特征向量：\(V = [v^{1}, v^{2}, ..., v^{n}]\) ，类似地将特征值连成一个向量\(\lambda = [[\lambda_1, \lambda_2,...,\lambda_n]]^T\)
特征值分解是把一个n阶实对称矩阵分解为下面的形式： \[A=Vdiag(\lambda)V^{-1}\]
其中：
特征值分解有利于我们分析矩阵的性质，就像质因数分解一样有助于我们理解整数。
特征向量可能不唯一，而特征值一定唯一。
什么是正交变换？ 正交变换：在线性空间中，保持向量长度不变的线性变换。 正交变换的定义是什么？ 设\(V\)为欧式空间，\(T\)是\(V\)的一个线性变换。如果\(T\)保持\(V\)中任一向量\(x\)的长度不变，即有： \[(x,x)=(Tx,Tx)\] 那么称\(T\)是\(V\)的一个正交变换。（即内积不变）
注： \((x,x)\)是向量内积 怎样的变换算是正交变换？ 线性变换\(T\)为正交变换的充要条件是，对于欧式空间\(V\)中任二向量\(x,y\)都有： \[(x,y)=(Tx,Ty)\]
正交矩阵的定义是什么？ 如果实方阵\(Q\)满足： \[T^TQ=I,或 Q^{-1}=Q^T\] 则称\(Q\)为正交矩阵
其中，\(I\)是单位矩阵。 正交矩阵有哪些特点？ - 正交矩阵的行列式必定为\(+-1\) - 行列式值为+1的正交矩阵，称为特殊正交矩阵，它是一个旋转矩阵。 - 行列式值为-1的正交矩阵，称为瑕旋转矩阵。瑕旋转是旋转加上镜射。镜射也是一种瑕旋转。 - 正交矩阵的逆矩阵依然是正交矩阵 - 两个正交矩阵的乘积依然是正交矩阵 - 下面是一些小的正交矩阵和可能的解释： 
怎样的矩阵能够成为正交矩阵？ \(Q\)是正交矩阵的充要条件是，它的列向量是两两正交的单位向量。
欧式空间的线性变换是正交变换的充要条件是，它对于标准正交基的矩阵是正交矩阵。
欧式空间是针对实数域\(R\)上的线性空间； 酉空间是特殊的复线性空间。
酉变换 酉空间\(V\)中的线性变换\(T\)，如果满足 \[(x,x)=(Tx,Tx),x\in V\] 则称\(T\)为\(V\)的酉变换。 酉矩阵 酉变换在酉空间的标准正交基下的矩阵\(A\)是酉矩阵，即\(A\)满足下式： \[A^HA=AA^H=I\] - 酉矩阵的逆矩阵也是酉矩阵 - 两个酉矩阵的乘积还是酉矩阵
酉空间上的Schur定理（定理1.41） 设\(A\in C^{n\times n}\)的特征值为\(\lambda _1,\lambda _2,...,\lambda _n\)，则存在酉矩阵\(P\),使得： \[P^{-1}AP=P^HAP=\left[ \begin{matrix} \lambda _1 & . & ...& . \\ & \lambda _2 & ...& . \\ & & ...& . \\ & & &\lambda _n \end{matrix} \right]\]
实数空间上的Schur定理 设\(A\in R^{n\times n}\)的特征值为\(\lambda _1,\lambda _2,...,\lambda _n\)，且\(\lambda _n \in R(i=1,2,...,n)\),则存在正交矩阵\(Q\),使得： \[Q^{-1}AQ=Q^HAQ=\left[ \begin{matrix} \lambda _1 & . & ...& . \\ & \lambda _2 & ...& . \\ & & ...& . \\ & & &\lambda _n \end{matrix} \right]\]
正规矩阵
设\(A \in C^{n \times n}\)，且等式 \[A^HA=AA^H\] 成立，则称\(A\)为正规矩阵。
正规矩阵与对角矩阵的定理（定理1.42）
这是很久以前的IRIE的期末大作业。现在贴在自己的博客上。
实验要求： 1. 用爬虫采集特定网站的信息； 2. 设计实现信息检索与提取系统，对采集的信息进行检索提取； 3. 结合webpy与html实现界面展示。
网络爬虫是捜索引擎抓取系统中重要的组成部分，其主要目的是将互联网上的网页下载到本地形成一个文件或互联网内容的镜像备份。流程如下： a. 从给定的入口网址把第一个网页下载下来 b. 从第一个网页中提取出所有新的网页地址，放入下载列表中 c. 按下载列表中的地址，下载所有新的网页 d. 从所有新的网页中找出没有下载过的网页地址，更新下载列表 e. 重复3、4两步，直到更新后的下载列表为空表时停止 其实就是简化成下面的步骤： a. 按下载列表进行下载 b. 更新下载列表 c. 循环操作a，b，直到列表为空结束 在本次作业中我们使用python编码实现爬虫的功能，其中用到的python组件有： urllib2：用于获取URLs（Uniform Resource Locators）的组件，以urlopen函数的形式提供一个非常简单的接口，具有利用不同协议获取URLs的能力，同时提供了一个比较复杂的接口来处理一般情况，如：基础验证，cookies代理和其他。通过handlers和openers的对象提供。urllib2支持获取不同格式的URLs并利用它们相关网络协议（例如FTP，HTTP）进行获取。 BeautifulSoup：是python的一个库，最主要的功能是从网页抓取数据。它提供简单的、python式的函数用来处理导航、搜索、修改分析树等功能。可以通过解析文档为用户提供需要抓取的数据。在bs4库中导入。 Htmlparser：是一个开源项目，提供了线性和嵌套两种方式来解析网页，主要用于 html 网页的转换（Transformation）以及网页内容的抽取（Extraction）。HtmlParser 有如下一些易于使用的特性：过滤器（Filters），访问者模式（Visitors），处理自定义标签以及易于使用的 JavaBeans。 selenium ：是一个模拟浏览器，进行web的自动化测试的工具，它提供一组API可以与真实的浏览器内核交互。用于抓取js动态生成的页面。
信息检索系统的模型主要有布尔模型、向量模型和概率模型。其中布尔模型 是最早的IR模型，也是应用最广泛的模型，目前仍然应用于商业系统中，布尔模型查询简单但不支持部分匹配，很难控制被检索的文档数量；向量模型（VSM：Vector Space Model）是Salton在上世纪60年代提出的，成功应用于SMART（System for the Manipulation and Retrieval of Text）文本检索系统，其基于关键词，并根据关键词的出现频率计算相似度，向量模型中术语权重的算法提高了检索的性能，部分匹配的策略使得检索的结果文档集更接近用户的检索需求，同时可以根据结果文档对于查询串的相关度使用Cosine Ranking等公式对结果文档进行排序。 在本次作业中信息检索系统采用向量模型，根据相似度返回结果。 ## 结巴（Jieba）分词 结巴（jieba）是一个可以对一段中文进行分词的插件，支持精确模式、全模式及搜索引擎模式三种分词模式，可以适应不同需求。其基本实现原理有：（1）基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG）；（2）采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合；（3）对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法。 ## 基于webpy界面设计网页 webpy 是一个轻量级Python web框架，可以快速的完成简单的web页面。在本次实验中使用webpy建立搜索网页，web.py 的模板语言叫做 Templetor，它能负责将 python 的强大功能传递给模板系统。本实验中使用template与html编写网页。
本次实验中信息检索与提取系统的整体设计流程如下图所示。主要包括抓取信息、分词、建立索引、建立向量模型、计算比较相似度、返回结果这六个过程，此外，我们基于webpy建立了搜索的网页界面，使查询过程更加简洁明了。下面具体介绍相应的模块。 
抓取信息
使用python编写爬虫程序抓取新浪网（http://news.sina.com.cn/） 上的新闻，使用urllib2获取网页源代码，使用beautifulsoup和htmlparser解析网页获取网页中的新闻（标题、关键字、内容、日期），用selenium获取js动态生成的数据(评论数)。解析过的与未解析的链接分开标记。经过一段时间的抓取，共获得3000多条新闻信息，保存为txt文件，具体格式如下： 
每条新闻包括标题、关键字、时间、网址、评论数（热度）等信息。
分词 导入jieba分词模块，首先按是否为汉字、数字、英文字符及标点 符号对新闻内容进行梳理，去除掉信息缺失的数据，然后用jieba分词对title及description内容进行分词，得到如下txt文件； 
建立索引 对于所有的词，按照其在全部新闻中出现的情况建立倒排索引，将每个词与相应的新闻序号建立联系。 建立向量模型 结合建立的倒排索引表，计算每个新闻条目的向量，其中权重采用tf-idf算法生成，构建向量模型。 
查询返回结果 根据在query中输入的关键词与向量模型进行数量积计算相似度，根据相似度的大小将检索到的新闻按序列出。如：query中输入“南海，菲律宾”，得到的检索结果如下： 
前后端实现 基于webpy界面设计搜索网页，建立交互的界面。在之前系统设计的基 础上，在webpy框架下，利用templates模板语言将后台结果与前端界面进行交互，并在服务器端使用GET和POST函数与客户端web交互并传递参数传递参数，将搜索新闻在网页上呈现出来。其主要步骤为：（1）客户端发送get请求，触发服务端get()函数，调用index.html网页，返回给客户端。（2）客户端发送搜索关键字并通过post方式给服务端，触发服务端post()函数，post()函数将收到的关键字传入之前设计的搜索系统中，得到返回值新闻条目。（3）通过webpy传递给result.html，得到html网页后发给客户端。 
例如想要查询与“习近平”“南海”相关的新闻，按下图输入，关键词之间要有空格。 
点击search之后的网页界面如下，将我们之前抓取的与“习近平”及“南海”有关的新闻链接按照相似度大小排列，同时列出相应的时间、内容及热度。 
如果输入的关键词并不在之前建立的索引中，则会出现如下界面： 
• 对Python语言不熟悉、甚至0基础： 阅读相关书籍，掌握for循环，try，list dict 等基本数据结构的操作及语法，文件读写操作，数学运算等，快速上手。 • Python程序运行打印之后不输出： import sys reload(sys) sys.setdefaultencoding('utf-8') • 获取网页速度慢： if response.info().get('Content-Encoding') == 'gzip': buf = StringIO(response.read()) f = gzip.GzipFile(fileobj=buf) 下载压缩的网页，速度更快 • 获取网页异常时，程序中断，导致不能源源不断地爬取到需要的网页： 利用try/except处理异常。
1 | try: |
• beautifulsoup解析网页内容不全，无法获取新闻网页中关于评论数目的信息： 查看网页源代码发现评论数是js动态生成的，beautifulsoup不能用于获取动态生成的数据，经查阅网上资料，返现selenium包可以用于解析网页中js动态生成的数据，我们首先获取新闻id，访问新浪新闻评论链接，找到其中评论数据。 commenturl = 'http://comment5.news.sina.com.cn/comment/skin/default.html?channel=gn&newsid=comos-' + newsid driver = webdriver.PhantomJS() driver.set_page_load_timeout(30)#设置延时 driver.get(commenturl)#获取网页 comment = driver.find_element_by_class_name('f_red').text#获取元素 • selenium运行报错： 需要添加环境变量，将PhantomJS文件所在文件夹添加到\(PATH文件下：sudo vi /etc/paths • 搜索时建立索引过程耗费时间 预先建立好索引，存储在内存中，搜索时直接利用已经建立好的索引进行搜索。 • 为每条新闻数据、query建立向量并存储速度慢、由于字典集合很大，导致向量稀疏、耗费资源，另外进行向量乘法运算计算相似度时产生不必要的浪费： 仅为每条新闻数据建立字典，存储包含的词和tf-idf权重值，计算query和每一个新闻条目的相似度时，只需要对query中包含的关键词在新闻条目中的权值进行运算即可（因为其它位都是0），简化运算。 • 新闻条目数量庞大，query与新闻的匹配计算量大、效率低： 给定query时，我们先访问query中关键词在索引中的倒排列表，只对其中的新闻与query进行相似度计算、排序、返回最终结果，极大程度上过滤掉与query不相关的新闻条目。 • 字典创建无序，不能按创建顺序输出结果： 利用OrderedDict有序字典，能够记录下字典的创建顺序，有序输出结果dict= collections.OrderedDict() • 搜索结果优化：搜索返回的结果题目中不包含关键词： 对在新闻题目中出现的关键词增加权重，使得题目与关键词匹配度越高的新闻排名越靠前，符合真实需求。 • webpy不能直接调用Python中的函数： 在webpy模板首行定义一个变量\)def with (posts) 在Python中计算后利用将参数传入，可以是任意类型。 • webpy使用template时，路径设置： render = web.template.render('templates/') 打开render下的index.html： render.index()
在做比赛的过程中，我们发现了有转化率这个指标在大量数据下是有效的。理想情况下，例如某个广告点击量是10000次，转化量是100次，那转化率就是1%。但有时，例如某个广告点击量是2次，转化量是1次，这样算来转化率为50%。但此时这个指标在数学上是无效的。因为大数定律告诉我们，在试验不变的条件下，重复试验多次，随机事件的频率近似于它的概率。后者点击量只有2次，不满足“重复试验多次”的条件。
那么如何解决这个问题呢？
整体思路：用估计值来模拟实际CVR。
实际上，广告妆化率是随着时间迁移和用户喜好变化而变化的。因此我们可以利用先验知识来持续性地调整CVR。计算广告训练与平滑思想给出了一个很好的解决方案：贝叶斯平滑。
考虑到时序序列模型，我们把从第一天到第n天的所有先验知识汇总到第n天的结果，并以此来对第n+1天的CTR进行平滑。在广告平滑上，没有什么方法比贝叶斯平滑能够更好的利用先验知识了，而帮助贝叶斯平滑方法实现目标的就是Beta分布。Beta分布的强大之处在于，通过改变其中的两个参数α和β，你可以让Beta分布的图形变成任意形状，而且在加入先验知识前后，通过贝叶斯变换，对CTR的预估都可以表示为Beta分布。
Beta分布中参数α和β的本质含义，即：α表示点击数，β表示曝光数。因为贝叶斯平滑的具体公式（后面再讲这个公式的原理）就是：
\[SmoothCTR = \frac{(α + CurrentC - 1)}{( α + β + CurrentI -2)}\]
公式由来：
能不能直接把历史点击和历史曝光分别赋值给α和β来进行计算呢？显然不行，因为这么做就会犯之前我们提到的那些问题，比如不同日期的曝光、点击权重应该不一样。所以基础的贝叶斯平滑是不能解决我们刚才提到的问题的，我们需要深入研究Beta分布的特性，用一种新的方法通过先验知识求解α和β，从而计算SmoothCTR。
参考文献CTR预估中的贝叶斯平滑方法（二）参数估计和代码实现
矩估计的方法要追溯到19世纪的Karl Pearson，是基于一种简单的 “替换” 思想建立起来的一种估计方法。 其基本思想是用样本矩估计总体矩. 由大数定理，如果未知参数和总体的某个(些)矩有关系，我们可以很自然地来构造未知参数的估计。具体计算步骤如下：
Beta分布除了两个显性的重要参数α和β外，还有两个相对隐形但同样重要的参数，均值和方差，通过均值和方差可以唯一确定α和β的值，它们的数学关系如下：(见参考链接beta（贝塔）分布的数学期望和方差)
\[均值 mean =\frac{\alpha}{\alpha+\beta}\] \[方差 var =\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta + 1)}\]
因此，如果我们根据数据集统计了平均值和方差，那么α和β的值也就确定了：
\[\alpha = mean \frac{mean(1-mean)}{var - 1}\]
\[\beta = (1-mean)\frac{mean(1-mean)}{var-1}\]
这种估计方法其实叫Fixed-point iteration。只是有点类似EM的思想。
首先构造出似然函数，然后利用Fixed-point iteration来求得似然函数的最大值。
1）首先给出参数的一个初始值（通常可以使用矩估计得到的结果作为初始值）。
2）在初始值处，构造似然函数的一个紧的下界函数。这个下界函数可以求得其最大值处的闭式解，将此解作为新的估计用于下一次迭代中。
3）不断重复上述（2）的步骤，直至收敛。此时便可到达似然函数的stationary point。如果似然函数是convex的，那么此时就是唯一的最优解。
其实Fixed-point iteration的思想与EM类似。
1 |
|
参考文献转化率（CTR）预测的贝叶斯平滑
对于一件商品或一条广告，对于某次曝光，用户要么点击，要么没点击，这符合二项分布。因此下文中对于点击率类的贝叶斯平滑，都是基于以下假设：对于某件商品或广告XX，其是否被点击是一个伯努利分布（Bernoulli）。
\[X \sim Ber( r) \tag{3}\]
其中X表示某个广告是否被点击，点击取1，未被点击取0，r是某件商品被点击的概率，即点击率。
在(3)式的假设下，可以使用极大似然法计算出点击率的估计值\(\hat{r}\) 。具体做法为：
从用户日志中随机抽取n条记录，对任一条记录i都有
\[X_i \sim Ber( r) \tag{4}\]
那么所有记录的点击数的联合概率密度就是上式的连乘，也就是构造了极大似然函数。将极大似然函数对r求导并令导数等于0，就可以解出\(r\) 的估计值\(\hat{r}\) 。\(\hat{r}\) 就是点击率的极大似然估计。当某个商品的点击次数或者曝光次数为0时，可以用\(\hat{r}\) 当成它的初始值。
然而这样并没有解决新上线广告问题。例如有两件商品A和B，其点击率分别为\(r_A=\frac{5}{10}\)和\(r_B=\frac{50}{100}\)，\(r_A=r_B\)，但商品A的曝光只有10次，商品B的曝光有100次，这样比较是否合理？那么我们就要用到贝叶斯估计来解决这个问题了！
在贝叶斯框架下，我们假设点击率r服从某个分布：
\[r \sim \pi(r) \tag{5}\]
因为这是基于经验的，这个分布称为先验分布。贝叶斯参数估计可以同时解决最开始提出的两个问题。其过程是基于经验或历史数据先给出一个r的估计值，然后基于现有的数据在这个估计值上修正，得到最终的点击率估计，此时的估计值已经是修正过的。更美好的是我们可以分离出修正参数，来进行更好的估计（即(2)式中的a和b）。
\[r = \frac{C+a}{I+b} \tag{2}\]
既然有先验分布，就有后验分布。r的后验分布记作\(\pi(r|x)\) 。 其中x表示输入数据或特征，对于点击率预测，x就是点击次数和曝光量。因为已经看到了数据，才确定r的分布，因此叫做『后验』分布。贝叶斯估计的实质就是求后验分布。即基于当前的点击次数和曝光量，求点击率的分布；而未看到数据之前点击率的分布是\(\pi(r)\)。下面会讲解如何计算后验分布\(\pi(r|x)\).
贝叶斯估计的过程可以简单认为：
用历史数据根据\(\pi(r)\)估计r，记作\(\hat{r}_{history}\)；用当前数据根据\(\pi(r|x)\)估计r，记作\(\hat{r}_{current}\)，然后用\(\hat{r}_{history}\)修正\(\hat{r}_{current}\)。
r 的后验分布\(\pi(r|x)\)是个概率密度函数，无法知道r确切的值。需要求出最接近真实情况的r需要损失函数来约束。
适用于点击率的损失函数有：
\[L(\hat{r}, r) = (\hat{r} - r)^2\]
\[L(\hat{r}, r) = |\hat{r} - r|\]
贝叶斯参数估计的过程可以简单描述为：求\(\hat{r}\)，使得损失函数在r的后验分布上的期望最小。这句话的数学定义为：
\[\arg \min \int L(r, \hat{r}) \pi(r|\boldsymbol{x})\ dr = E_{\pi} L(r, \hat{r}) \tag{6}\]
因此需要知道\(\pi(r|x)\)的形式，然而\(\pi(r|x)\)的形式一般不知道的，但是可以知道\(\pi(r)\)的形式（经验值嘛，我们指定的）。此外，数据的分布我们也是知道的，其概率密度函数（pdf）记为\(f(x|r)\)，表示数据的分布跟参数r有关，r是要求解的参数，在这里就是点击率。
这时可以根据贝叶斯公式计算出\(\pi(r|x)\)：
\[\pi(r|\boldsymbol{x}) = \frac{f(\boldsymbol{x}|r)\pi(r)}{f(\boldsymbol{x})} \tag{7}\]
其中，
\[f(\boldsymbol{x}) = \int_0^\infty f(\boldsymbol{x}|r) \pi(r) dr\ \mbox{ (边缘概率密度定义)}\]
上式好复杂，但其实一些常见的分布都可以求出上式积分的具体形式。但通常不用实际去积分，因为满足一定条件，\(\pi(r)\)跟\(\pi(r|x)\)有一样的形式。\(\pi(r)\)是已知的，如果形式一样，\(\pi(r|x)\)也就容易求得了。下面介绍共轭先验的概念。
共轭先验： 如果找到一个\(\pi(r)\)，它是\(f(x|r)\)的共轭先验，那么r的后验分布\(\pi(r|x)\)和先验分布\(\pi(r)\)会有一样的形式。
『轭』是指驾车时套在牲口脖子上的曲木。古代拉扯的牲口通常有两只，因此轭是连接两只牲口的工具。在这里共轭是指\(\pi(r)\)和\(\pi(r|x)\)通过\(f(x|r)\)联系起来了。
之前假设广告是否点击服从伯努利分布，参数为r；对于点击次数，服从的是二项分布，即\(f(C, I|r) \sim Bin(r)\) ，二项分布的共轭先验是Beta分布。Beta分布的参数是α和β，即\(\pi(r) =Beta(\alpha, \beta)\) ,根据共轭先验的定义，r的后验分布\(\pi(r|x)\)的形式跟其先验分布\(\pi(r)\)一样，即\(\pi(r|x) = Beta(\alpha', \beta')\)。
对于点击率预测，求出\(\pi(r|x)\)，带入公式(6)，当\(L(\hat{r}, r) = (\hat{r} - r)^2\)时，
\[\hat{r} = \frac{C + \alpha}{I + \alpha + \beta} \tag{8}\]
上式的求解过程可以参考贝叶斯参数估计最后的例子。(8)式就是点击率估计（平滑）的最终形式。其中C和I就是点击次数和曝光量，α即为公式(2)中的a，α+β是公式(2)中的b。α和β是从历史数据中得到的。
上面的内容给出了为什么很多文章会假设点击率服从Beta分布的理由，因为最终的平滑的因子是Beta分布（先验分布）中的两个参数。
在做比赛的过程中，我曾用过word embedding生成app特征，对结果提升了有几个万分点。
论文：tem2vec: Neural Item Embedding for Collaborative Filtering # 思想 这篇文章比较朴素，创新性不高，基本是参照了google的word2vec方法，应用到推荐场景的i2i相似度计算中，但实际效果看还有有提升的。主要做法是把item视为word，用户的行为序列视为一个集合，item间的共现为正样本，并按照item的频率分布进行负样本采样，缺点是相似度的计算还只是利用到了item共现信息，1).忽略了user行为序列信息; 2).没有建模用户对不同item的喜欢程度高低。
主要代码来自于写论文的作者分享的代码
最近在做比赛，发现在工业上，很多分类问题的标签分布都是不平衡的。如参考文献标签倾斜修正方法记要所属，比如用分类器去判断x光片中的癌症，这是一个二元分类问题，由于癌症的比例是非常小的，比如0.001。那么，将这些样本放到大多数分类模型中训练，模型的表现会非常相似，将所有数据都预测为没有癌症，因为这样也可以得到99.999%的准确率。
参考文献解决真实世界问题：如何在不平衡类上使用机器学习？说，从不平衡数据中学习，是一项已被研究了 20 年之久的问题。它曾是许多论文、研讨会、特别议程的主题（一项最近的调查就有大约 220 个引用）。人们尝试了许多方法，但结果各不相同，所以至今没有得到明晰的答案。当数据科学家们第一次遇到这个问题，他们往往会问：「如果我的数据是不平衡的，我该怎么做？」而这一问题是没有固定答案的，就像你问「哪个学习算法是最好的」一样：答案取决于数据。
一般来说，有下面几种方法：
什么也不做
通过某些方法使得数据更加平衡：
在算法层面之上（或之后）：
参考文献Practical Lessons from Predicting Clicks on Ads at Facebook6.3指出，欠采样可以加快训练速度，提升模型表现。需要注意的是，就算数据被欠采样，其实也可以通过在欠采样空间中对预测结果进行修正。例如，在采样之前CTR只有0.1%，那么我们对负样本欠采样0.01，那么CTR就会变为10%。为了修正结果，使得CTR恢复到0.1%,我们可以通过公式： \[q=\frac{p}{p+(1-p)/w}\] 其中，\(p\)是欠采样空间下预测的概率， \(w\)是对负样本的采样率。
在这里我决定先复习一下先验概率、后验概率
先验概率是指事件尚未发生，对该事件发生的概率的估计，是在缺乏某个事情的情况下描述一个变量。 先验概率可以通过已知的关于事件本身的先验知识得到，蒙特卡洛方法也可以用于计算先验概率。 后验概率是指在事件已经发生的条件下，求该事件发生原因是由某个因素引起的可能性的大小，是考虑一个事件之后的条件概率。 后验概率可以基于 贝叶斯定理，通过先验概率乘以似然度，再归一化得到。具体来说，贝叶斯公式： \[P(h|D)=\frac{P(D|h)P(h)}{p(D)}\] 其中，\(P(h)\)为\(h\)的先验概率，\(P(h|D)\)为\(h\)的后验概率。 通常，事件A在事件B（发生）的条件下的概率，与事件B在事件A（发生）的条件下的概率是不一样的；然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。贝叶斯公式的一个用途在于通过已知的三个概率函数推出第四个。
参考文献标签倾斜修正方法记要通过理论推导来验证这个结论。 上参考文献作者提到，PRML的1.5.4节中介绍了一种标签倾斜修正的方法。
首先，你的模型必须是一个软分类器，即预测值为0到1之间的概率。假设输入向量x，预测标签\(C_k\)，那么可以用条件概率表示，即计算\(p(C_k|x)\)的概率。根据贝叶斯公式，条件概率可以如下变化： \[p(C_k|x)=\frac{p(x|C_k)p(C_k)}{p(x)}\]
上面是没有做重采样时，得到概率。当做重采样时，只是改变了标签\(C_k\)的先验概率\(p(C_k)\)，即将\(p(C_k)\)变为\(p'(C_k)\)（其实就是标签\(C_k\)的先验分布而已）。而\(p(x)\)是条件\(x\)发生的概率，不会变化。\(p(x|C_k)\)是后验概率，也不会变化。【问题，为什么不变？我感觉是因为特征是采样前的特征，因此这个没变】
因为是对负样本进行了抽样，假设对负样本抽样比例为\(w\)，抽样后：
\[n'(0)=n(0)\times w,n'(1)=n(1)\]
易知： \[p(1)=\frac{n(1)}{n(1)+n(0)}=\frac{n'(1)}{n'(1)+n'(0)/ w}\] \[=\frac{p'}{p'+(1-p')/w}\] 其中，\(n(C_k)\)表示\(C_k\)的个数
我们推导出了先验概率\(p'(C_k)\)与\(p(C_k)\)的关系。那么，如果我们想修正\(p(C_k|x)\)，则：
\[p(1|x) = \frac{p(x|1)p(1)}{p(x)} = \frac{p(x|1)p'(1)p(1)}{p(x)p'(1)}\] \[=p'(1|x)\frac{p(1)}{p'(1)}=p'(1|x)\frac{p}{p'}\]
而由之前的推导我们可知\(p=\frac{p'}{p'+(1-p')/w}\)，代入得： \[p(1|x)=p'(1|x)\frac{p}{p'}=p'(1|x)\frac{\frac{p'}{p'+(1-p')/w}}{p'}\] \[=p'(1|x)\frac{1}{p'+(1-p')/w}\]
需要注意的是，\(p'(1|x)\)是预测出来的概率，\(p'\)是抽样之后正样本的比例，而在facebook的论文中，假设\(p'\approx p'(1|x)\)（也就是说，我们假设了预测集中，1出现的概率=预测出来的为1的概率。我的理解就是，我们完全信任了预测的结果），并记\(q=p'(1|x)\)则以上公式变为：
\[p(1|x)=\frac{q}{q+(1-q)/w}\]
【问题：在预测时，\(p'\)可不可以变为预测集的正样本比例\(p'\)】
在欠采样中，假设对负样本采样率为\(w\)，则直接将结果按照如下公式修正即可：
\[p=\frac{q}{q+(1-q)/w}\]
其中： - \(q\)是在欠采样之后，模型预测出来的概率。 - \(p\)是修正后的概率。
当w=0.1时，变换其实为：
上面是y1=q(不做变换)，下面是本变换y2。
而如果我们将y3=y1-y2绘出： 
我们发现，概率大的压缩的小。 因为你负样本采样了之后，就是会预测的比实际的高一点，所以要给它压下去。
附上matlab代码： q=0.001:0.01:1; y1=1./(1+(1./q-1)./0.1); y2 = q; plot(q,y1); hold on; plot(q,y2); hold on; y3 = y2-y1; plot(q,y3)
如果在已知样本中，正样本的概率\(p\),那么：
\[p'(1)=\frac{n'(1)}{n'(1)+n'(0)}=\frac{n(1)}{n(1)+n(0)\times w}\] \[=\frac{1}{1+\frac{n(0)\times w}{n(1)}}=\frac{1}{1+\frac{p(0)\times w}{p(1)}}\] \[=\frac{p(1)}{p(1)+p(0)\times w}=\frac{p}{p+(1-p)\times w}\]
而因为： \[p(1|x)=p'(1|x)\frac{p}{p'}\]
代入得：
\[p(1|x)=p'(1|x)\frac{p}{\frac{p}{p+(1-p)\times w}}\] \[=p'(1|x)(p+(1-p)\times w)\]
这里的p是样本中，正样本的概率。 # 参考文献
“这一段奔波太过匆忙，有时来不及回头张望。”
腾讯“人工寻找trick”大赛初赛今天结束了。最终初赛线上logloss为0.099104，排名为64名：
复赛成绩0.101941，排名26名：
虽然与前排大神的分相差甚远，虽结果不那么如人意，也是对这个领域入了个门。
详细赛题见官方网站
已知：17-30天移动APP的广告、用户的转化情况，及相关上下文。 预测：第31天指定用户和对应广告的转化率。
评估方式： \[logloss=-\frac{1}{N}\sum_{i=1}^N(y_ilog(p_i)+(1-y_i)log(1-p_i))\]
其中， - N是测试样本总数 - \(y_i\)是二值变量，取值为0或1，表示第i个样本的label - \(p_i\)是模型预测第i个样本label为1的概率
总之，就是预测的越准越好（这不废话么2333）
这是Kaggle上数据挖掘比赛的黄金流程图： 
其实对于这个比赛的初赛而言，线上是容易过拟合的。因为线上只有一个集，可反复提交多次来使得线上得分很高，但实际上模型是有些过拟合的。不过这不是重点。
接下来一步步做说明
训练集train.csv没有大问题，我注意的只是后几天的一些数据没有回流的问题。
值得注意的是，本次竞赛的训练数据提供的截止第31天0点的广告日志，因此，对于最后几天的训练数据，也就是说后五天部分用户实际上是转化了，但广告主还没有来得及将这条转化汇报给广告系统，导致数据集中的label被误标记为了0（实际上是1）。（如果我还没有描述清楚，这里具体可以看官网赛题FAQ.1）
这里我采取了一种很暴力的方法，即去掉每个广告主最后一次回流之后的数据。
通过分析我们发现，其实有近一半的广告主还是尽职尽责的，直到30号23点还在反馈回流。只有有一部分广告主在30号下班后，或29号下班后就不回流了。所以我们将这些广告主最后一次回流之后的数据都删除（其实这些都是负样本），这样就在一定程度上减少了不准的负样本。
这样筛去了大概有3万条，也不算多。
一开始的时候我们采用了很多基本特征，即各种ID（AppID,UserID,creativeID,pisitionID等）的onehot编码，又对单特征进行了一定的统计。后来看了大神“为情所困的少年”的分享，才反应过来其实无论是onehot还是对ID单维度的统计特征，其实都是对于一个特征的一种表达，从一定意义上是重复的。我个人感觉onehot之后的稀疏特征更适合于线性模型，如LR；而统计量的连续特征更适合于树模型，如GBDT。
回头来看，其实特征工程需要根据模型预先选择方向。李沐说过，模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。
就此题来说，有两个方向：
如果我们懒得分析数据（初期我们就是这样），并且有还不错的设备（自以为64G内存很有优势），我们可以直接选择这个方向。
初期的时候，我们是选择的这条路。 当时只有简单的ID类特征，以及ID类特征的交叉组合，将这些特征onehot之后输入了LR模型。
关于特征组合，我在后面会介绍到。
做完特征和特征组合，将它onehot之后输入模型就可以了。
对于LR这种线性模型来说，它更适合于onehot类型的特征，首先它对于稀疏高维特征处理是无压力的，其次离散化后的特征对异常数据有很强的鲁棒性，这些在参考文献2逻辑回归LR的特征为什么要先离散化中可以看到。
但由于ID类特征非常多，例如本题的UserID有好几百万个。这时就会带来维度灾难问题，见参考文献4机器学习中的维度灾难。不仅如此，这时基本上也就被设备问题限制死了。这很烦。于是我们就换模型了。
这是我们暂定的一个方案，就是采用少量、但表现很不错的组合特征统计量，以及一些手工提取的特征（如用户历史安装次数、APP历史被安装次数），这些特征主要来源于群内“为情所困”大神分享的一张表。
模型我们采用的是GBDT，直接使用了陈天奇大牛的xgboost框架。模型我暂时还没有很认真地研究，只是熟悉了一些参数，为决赛做了一些准备。
特征组合真是我遇到的一个大难题。
说到特征组合，从统计的角度解释，基本特征仅仅是真实特征分布在低维空间的映射，不足以描述真实分布，加入组合特征是为了在更高维空间拟合真实分布，使得预测更准确。 组合特征我现在用过的有以下两种方式：
对离散ID进行hash生成新特征
在初期用LR的时候，我们采用的方式是hash。即对两个ID做hash运算，得到一个新特征。这是一个很巧妙的方法。例如下面这个表，我们做哈希：
\[age\times 10 + gendar\]
得到第三列：
| age | gendar | hash |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 21 |
| 3 | 2 | 32 |
第三列的的特征的取值有两位，十位是age,个位是gendar。新特征是一种新的交叉特征的体现。
对组合进行统计生成新特征
像之前“为情所困”大神说过的那样，其实无论onehot还是统计特征，其实都是对于一个特征的一种表达。因为后期我们采用了GBDT，因此我们弃用了之前的hash组合方式，而选用统计量（即点击量、转化量和转化率）。这样就在一个维度上表达了这两个特征的组合，而且非常便于计算。
需要注意的是，特征组合也不是随便从原来的特征里摘出来两列就做组合。这种随意地对特征堆叠其实会增加模型的负担，而且这些其实就像是“随机数一般的，毫无作用的特征”，可能会使得效果变差。
究竟对谁做组合，这也是一直困扰我们的问题。以下是我搜集到的几种方案：
迭代选取方式
Jerrylin大神曾经说过，可以先对一个组合做groupby分析，看看转化率的分布。可是我遇到了一个瓶颈——大多数特征的转化率分布都是不均匀的，组合起来就更不均匀了。不知道大神是怎么解决的，也许是计算这个分布的方差？【这是个问题，等来日解决，我再回来填坑】 大神刚才回我了，他说他是按照gbdt给的一个评分，选取评分较高的几个进行组合，然后再次输入模型进行迭代筛选。 在此我要再次偷偷感谢一下这位大神。要是没有他，我可能还会在二百名外挣扎。
刚才风，飞扬。。大神告诉我，其实xgb给的评分也是只能作为一个参考，因为不一定组合之后给会更高。
忆『凌』殇大神说，构造的特征很可能相关性很高，然后这两个特征的重要性肯定都不低。但是因为相关性高反而会影响性能。这个相关性可以计算这两个特征的相关系数corrcoef来得到。
穷举后用卡方检验筛特征
参考文献描述量选择及特征的组合优化提到，由于任何非穷举的算法都不能确保所得结果是最优的，因此要得最优解，就必需采用穷举法，只是在搜索技术上采用一些技巧，使计算量有可能降低。
我的学长“酱紫”对此有一种建议就是直接对所有基本特征进行遍历两两组合，然后用卡方检验筛出来一些比较好的特征。这种方式很简单，大多数工作只需要交给模型来完成。
循环特征消减和特征重要性评级
参考文献scikit-learn系列之特征选择中提到，在scikit-learn中有两种特征选择的方法，一种叫做循环特征消减(Recursive Feature Elimination)和特征重要性评级 (feature importance ranking)。
用GBDT筛特征
主要思想： GBDT每棵树的路径直接作为LR输入特征使用。
原理： 用已有特征训练GBDT模型，然后利用GBDT模型学习到的树来构造新特征，最后把这些新特征加入原有特征一起训练模型。构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。
【这里其实不太懂，一会问问张思遥】
步骤： 1. 首先要切分数据集，一部分用于训练GBDT，另一部分使用训练好的GBDT模型 2. GBDT模型的apply方法生成x在GBDT每个树中的index，然后通过onehot编码做成特征。 3. 新的特征输入到分类（如LR）模型中训练分类器。
实现： 参考文献GBDT原理及利用GBDT构造新的特征-Python实现的末尾有一个调用GBDT训练模型构建树，调用apply()方法得到特征，然后将特征通过one-hot编码后作为新的模型输入LR进行训练。feature trainsformation with ensembles of tree官方文档
竟然有这种操作队分享总结得非常好，主要特征是分为以下几类：
Trick特征： 通过观察原始数据是不难发现的,有很多只有clickTime和label不一样的重复数据，按时间排序发现重复数据如果转化，label一般标在头或尾，少部分在中间，在训练集上出现的情况在测试集上也会出现，所以标记这些位置后onehot，让模型去学习，再就是时间差特征，关于trick我比赛分享的这篇文章有较详细的说明。比赛后期发现了几个和这个trick相类似的文章1和文章2，可以参考。
统计特征： 原始特征主要三大类：广告特征、用户特征、位置特征，通过交叉组合算统计构造特征，由于机器限制，统计特征主要使用了转化率，丢掉了点击次数和转化次数。初赛利用了7天滑窗构造，决赛采用了周冠军分享的clickTime之前所有天算统计。三组合特征也来自周冠军分享的下载行为和网络条件限制，以及用户属性对app需求挖掘出。贝叶斯平滑user相关的特征特别废时间，初赛做过根据点击次数阈值来操作转化率，效果和平滑差不多但是阈值选择不太准。
活跃数特征：
特征构造灵感来自这里,比如某个广告位的app种数。
均值特征：
比如点击某广告的用户平均年龄
平均回流时间特征： 利用回流时间方式不对的话很容易造成leackage，这里参考了官方群里的分享，计算了每个appID的平均回流时间，没有回流的app用其所在类的平均回流时间代替
用户流水和历史特征： 利用installed文件关联user和app获得历史统计特征，利用actions进行7天滑动窗口获得用户和app流水特征。
多线程抽特征
决赛数据集太大，而我们组合特征非常多。因此我们采用了多线程抽特征的方式。 代码见TencentAD_contest，extra_rate_thread_0623.py 贝叶斯平滑 在决赛时，我们还使用了贝叶斯平滑。针对Pandas，我们对网上已有的代码进行了改进。 贝叶斯平滑笔记 word embedding 这个我没有做过多研究，这里是word embedding笔记 SVD分解 思路和代码主要看我这篇博客SVD分解 # 训练集构造
训练集特征做不好，就很容易造成泄露。这是我试过的两种方式：
经测试我们发现，即使我们去掉了30号的部分负样本，还是有一些问题的。因此我们将时间区间改了一下： 
这样做出于两种目的：一是尽量做到了线上线下统一，二是不让模型学习30号的样本数据，防止一些错误样本被模型学到。
相信很多人都用的是这两种其中的一种。我是一个对自己极度不自信的人，来来回回换了好几次。最终觉得第2种方式很稳定，线上线下较统一。第1种方式特征更新较快，模型更准确，但带来的问题就是线上线下不太统一。
至此特征工程已经完毕，开始训练。
训练其实没什么好说的，只要注意一下别过拟合就可以。
初赛我们采用的xgboost，决赛用的lightgbm。其实都是对GBDT的实现，两者都很好，但lightGBM更快一些，因为它只对部分节点进行生长。
在初赛的时候听到最多的就是stacking魔法了。文章【SPA大赛】腾讯广告点击大赛：对stacking的一些基本介绍非常详细地介绍了stacking大法。我觉得这句话很好：“在我看来stacking严格来说不能称为一种算法，我理解的是一种非常精美而复杂的对模型的集成策略。”
平时在学习的过程中，过于注重理论的推导，只是在一遍遍地看那些公式。但没有切身实践过，感受不到模型真正的威力和缺憾。通过这次比赛，还是收获比较多的。注意到了平时学习过程中自以为不重要的、很容易被忽略的细节。
在初赛中，我们其实并没有注重模型的调参等，而是一直在做特征工程。其实我初期也不知道究竟该怎么办。但JerryLin大神用他的言行教会我，特征决定了结果的上限，而模型只是在不断地逼近这个上限而已。只有得到了好的特征，才会拿到好的模型。
做了这么久的特征工程，最大的感想就是，只有认认真真、踏踏实实分析数据，才能得到好的特征。过度依赖算法在工业上是不可靠的。
越来越发现务实基础的必要性。比如LR中为什么要采用正则化项，为什么GBDT能有筛特征的功效，为什么树模型容易过拟合，为什么为什么......这些为什么直接决定了在遇到问题的时候能不能独立解决。而不能像我现在一样，分分钟心态爆炸，宛如一只无头的苍蝇。
还有就是，写代码一定要认认真真地写。不能直接把别人的直接粘过来用，这样是极其不负责的，也非常容易出错。在比赛的过程中，我的xgboost预测的代码是直接粘贴的O2O优惠券使用预测的冠军的代码，但他那个的目标是auc，因此他将结果映射到了（0,1）区间上。这句话让我白白浪费了很久很久的时间去试特征，结果发现线上线下不统一，整个人直接崩溃。
希望自己在未来的日子里，能将周志华老师的《机器学习》和李航老师的《统计学习方法》这两本书吃透，而不是像现在这样，狗熊掰棒子。
失败乃成功之母。
天行健，君子以自强不息。
特征选择：很重要
tip:冗余特征(redundant feature)： - 本特征能被其它特征中推演出来。它不一定有坏处，但也不一定有好处。例如：考虑立方体对象，若已有特征“长”、“宽”，则“底面积”是冗余特征。 - 冗余特征在很多时候不起作用，会增加学习过程的负担。 - 但如果学习目标是估算立方体体积，则“底面积”特征会对学习更好。
结论：如果某冗余特征恰好对应完成学习任务所需的“中间概念”，则该冗余特征是有益的。
特征选取时，若没有任何领域知识进行先验假设，只能遍历所有可能子集。-->不可取！
可行做法: 产生个“候选子集”，评价它的好坏，基于评价结果产生下一个候选子集。
子集搜索
信息增益
\[Gain(A)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\]
其中信息熵定义为：
\[Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k\]
信息增益\(Gain(A)\)越大，特征子集A包含的有助于分类的信息越多。
特征选择方法=子集搜索+子集评价
常见特征选择方法： - 过滤式(filter) - 包裹式(wrapper) - 嵌入式(embedding)
概念：先特征选择，再训练模型
特点：特征选择与模型学习无关
===来日填坑===
概念：把最终将要使用的学习器的性能作为特征子集的评价准则
特点：需要多次训练学习器
===来日填坑===
概念：将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成
给定数据集\(D={(x_1,y_1),(x_2,y_2),...(x_m,y_m)}\),其中\(x\in R^d,y\in R\).
考虑最简单的线性回归，以平方误差为损失函数，则优化目标为：
\[min_w\sum_{i=1}^m(y_i-w^Tx_i)^2\]
当样本特征很多，而样本数较少时，上式很容易陷入过拟合。解决方案，正则化项。
\(L_2\)范数正则化（“岭回归”(redge regression)）：
\[min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda ||w||_2^2\]
\(L_1\)范数正则化：
\[min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda ||w||_1\]
区别：\(L_2\)比\(L_1\)更容易获得“稀疏”(sparse)解，即它求得的\(w\)会有更少的非零分量。 （这里一定要看一下西瓜书-253页的解释）
以以下的拟合为例： 
在图二中，明显是因为高次项的系数\(\theta_3,\theta_4\)过大造成的。
因此我们加入正则化项： 
即给目标函数加一点东西。
现在，如果我们要最小化这个函数，那么为了最小化这个新的代价函数，我们要让\(θ3\)和\(θ4\)尽可能小。因为，如果你在原有代价函数的基础上加上1000乘以\(θ3\)这一项，那么这个新的代价函数将变得很大，所以，当我们最小化这个新的代价函数时，我们将使\(θ3\)的值接近于0，同样\(θ4\)的值也接近于0，就像我们忽略了这两个值一样。如果我们做到这一点（\(θ3\)和\(θ4\)接近0），那么我们将得到一个近似的二次函数。
更一般地：
\(L_2\)范数正则化：
\[min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda ||w||_2^2 \] \[= min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda\sqrt{\sum_{n=1}^nw_i^2}\]
(其中,m是数据个数，n是特征维度) 因此在正则化里，我们要做的事情，就是把减小我们的代价函数（例子中是线性回归的代价函数）所有的参数值，因为我们并不知道是哪一个或哪几个要去缩小。
因此，我们需要修改代价函数，在这后面添加一项，就像我们在方括号里的这项。当我们添加一个额外的正则化项的时候，我们收缩了每个参数。
\[ min_w\frac{1}{2m}[\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda\sqrt{\sum_{n=1}^nw_i^2}]\]
引言
说到缓冲区，不得不提Java NIO。
Java NIO(New IO)是一个可以替代标准Java IO API的IO API（从Java 1.4开始)，Java NIO提供了与标准IO不同的IO工作方式。
Java NIO: Channels and Buffers（通道和缓冲区）
Buffer定义
代码的角度来讲（可以查看JDK中Buffer、ByteBuffer、DoubleBuffer等的源码），Buffer类内部其实就是一个基本数据类型的数组，以及对这个缓冲数组的各种操作；
常见的缓冲区如ByteBuffer、IntBuffer、DoubleBuffer...内部对应的数组依次是byte、int、double...
Buffer与通道的关系
标准的IO基于字节流和字符流进行操作的，而NIO是基于通道（Channel）和缓冲区（Buffer）进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。
继承结构
以ByteBuffer为例：
Buffer是顶层抽象类，ByteBuffer继承Buffer，也是抽象类，ByteBuffer最常见的两个具体实现类如下：
DirectByteBuffer（JVM堆外部、通过unsafe.allocateMemory实现）、HeapByteBuffer（JVM堆）
缓冲区用途
写，然后读出
容量(capacity) capacity指的是缓冲区能够容纳元素的最大数量，这个值在缓冲区创建时被设定，而且不能够改变，如下，我们创建了一个最大容量为10的字节缓冲区；
ByteBuffer bf = ByteBuffer.allocate(10);上界（limit） limit指的是缓冲区中第一个不能读写的元素的数组下标索引，也可以认为是缓冲区中实际元素的数量；
位置（position） position指的是下一个要被读写的元素的数组下标索引，该值会随get()和put()的调用自动更新；
标记（mark） 一个备忘位置，调用mark()方法的话，mark值将存储当前position的值，等下次调用reset()方法时，会设定position的值为之前的标记值；
四个属性值之间的关系 根据以上四个属性的定义，我们可以总结出它们之间的关系如下： 0 <= mark <= position <= limit <= capacity