CTR相关算法总结

Algorithm

1、Logistic Regression

1.0 关于 LR 的理论，需要注意的点：

本质理解：LR的loss function选择的是对数损失（对数似然损失），所以其cost function的形式和MLE的形式如此神似。
loss function 和 cost function的区别：

1.1 网上总结的很好，这里自己偷个懒，就不做搬运工了~

• Github总结
• CSDN总结，附python底层实现代码

1.2 贴个基本原理

1.3 一些需要注意到点

• Cost函数（损失函数），表示预测的输出（h(x)）与训练数据类别（y）之间的偏差，可以是二者之间的差（h(x)-y）或者是其他的形式。综合考虑所有训练数据的“损失”，将Cost求和或者求平均，表示所有训练数据预测值与实际类别的偏差。
• 个人对 LR 的 cost func 的理解：
  
  1. LR 是基于 MLE 求解各个 feature 的权重；
  2. 等价于会有个似然函数，优化的方向是最大化；
  3. 对极大似然函数取对数，再乘以 1/(-m) 后，便将 cost func 的优化方向变为 min；（这样做的目的是符合人的思考习惯，想一想 SVM 的原问题也是做了类似的转化）；
  4. So 最小化 cost func <=> MLE
• h(x)函数的值，表示结果取1的概率。
• 自己没事了，可以推导一遍 损失函数的偏导为什么是下面这个样子？
  （1）
  （2）推导的时候注意一个点：f(x)对θ求导，等于x的累加。
• 计算机比较笨，无法一步找到全局最优解或者局部最优解。So，只能用梯度的方法（梯度下降or梯度上升）或者其它的方法来找到或近似找到最优解。比如使用梯度上升的方法，就会是：
  
  α是学习率，目的是为了让学习的步伐较慢。如果学习率太快，会导致求解过程不稳定。学习率的倒数决定了function达到当前局部最优最小值的迭代次数。
• 关于梯度下降的优化方法
  
  • 机器学习的三大元素：一个model，一个loss fuction，一个优化算法
  • 
  • 
  • 由上图可知，学习步长控制着每次迭代时朝着负梯度方向前进的长度，不同的学习步长会呈现如下情况：
    

1.4 基于python，从底层用梯度上升的方法求出LR的最优解

#!/usr/bin/env python
#coding:utf8
import random
import pandas as pd
import scipy.stats as stats
from sklearn import preprocessing
from sklearn import datasets
import numpy
from sklearn.linear_model import LogisticRegression
def sigmodFunc(inx):
    return 1.0/(1+numpy.exp(-inx))
def graAscent(dataMatIn, classLabels):
    dataMatrix = numpy.mat(dataMatIn)               # 转为矩阵
    labelMat = numpy.mat(classLabels).transpose()   # 转置
    m,n = numpy.shape(dataMatrix)                   # 获取结构
    alpha = 0.001                                   # 设置学习率
    maxCycles = 500                                 # 设置最大迭代次数
    weights = numpy.ones((n,1))                     # 初始化weights向量
    # 迭代的目标的是更新weights向量，即更新特征对于label的权重。
    # 这也就回归到了LR的本质：估计特征对label的重要程度。
    for k in range(maxCycles):
        h = sigmodFunc(dataMatrix*weights)
        error = (labelMat-h)
        weights = weights+alpha*dataMatrix.transpose()*error
    return weights
# 构建数据集
X, y = datasets.make_classification(n_samples=100000, n_features=20, n_informative=2, n_redundant=2)
train_samples = 100
X_train = X[:train_samples]
X_test  = X[train_samples:]
y_train = y[:train_samples]
y_test  = y[train_samples:]
"""
使用自定义的func训练LR
"""
weights_self = graAscent(X_train, y_train)
# print weights_self
"""
使用大牛的轮子训练LR
"""
clf = LogisticRegression()
skModel = clf.fit(X_train, y_train)
# print skModel.coef_
selfList = str(numpy.matrix.tolist(weights_self))
selfList = selfList.replace('[','')
selfList = selfList.replace(']','')
selfList = list(eval(selfList))
confList = skModel.coef_
confList = confList.tolist()[0]
"""
计算自己实现的LR和大牛造LR，训练结果的差异：
用weights的分布来判断差异的大小。
"""
statList = []
for index in xrange(len(weights_self)):
    statList.append(selfList[index] - confList[index])
calList = statList
"""
计算自己造的轮子和别人造的轮子之间差异
"""
maxValue = max(abs(max(calList)), abs(min(calList)))
# 均值
meanValue = sum(map(abs,calList)) / float(len(calList))
# 计算分位数时，需要先排序
calList.sort()
# 计算分位数
value_Q05 = calList[int(round(0.05 * len(calList) + 0.5))-1]
value_Q25 = calList[int(round(0.25 * len(calList) + 0.5))-1]
value_Q50 = calList[int(round(0.5  * len(calList) + 0.5))-1]
value_Q75 = calList[int(round(0.75 * len(calList) + 0.5))-1]
value_Q95 = calList[int(round(0.95 * len(calList) + 0.5))-1]
# 统计两个描述分布倾斜程度的变量：meanValue与各分位数之间的差值
"""
1、meanValue - value_Q05 < 0：95%的记录 大于 均值
2、meanValue - value_Q95 > 0：95%的记录 小于 均值
"""
deviation_1 = meanValue-value_Q05
deviation_2 = meanValue-value_Q25
deviation_3 = meanValue-value_Q50
deviation_4 = meanValue-value_Q75
deviation_5 = meanValue-value_Q95
# 标准差
if len(calList) > 1:
    sdsq = sum([(i - meanValue) ** 2 for i in calList])
    stdValue = (sdsq / (len(calList) - 1)) ** .5
else:
    stdValue = 0
print 'maxValue:' , maxValue
print 'meanValue:', meanValue
print 'stdValue:' , stdValue
print 'value_Q05:', value_Q05
print 'value_Q25:', value_Q25
print 'value_Q50:', value_Q50
print 'value_Q75:', value_Q75
print 'value_Q95:', value_Q95
print 'deviation_1:', deviation_1
print 'deviation_2:', deviation_2
print 'deviation_3:', deviation_3
print 'deviation_4:', deviation_4
print 'deviation_5:', deviation_5

1.5 优缺点

• 优点：由于 LR 模型简单，训练时便于并行化，在预测时只需要对特征进行线性加权，所以性能比较好，往往适合处理海量 id 类特征，用 id 类特征有一个很重要的好处，就是防止信息损失（相对于范化的 CTR 特征），对于头部资源会有更细致的描述。
• 缺点：LR 的缺点也很明显，首先对连续特征的处理需要先进行离散化，如上文所说，人工分桶的方式会引入多种问题。另外 LR 需要进行人工特征组合，这就需要开发者有非常丰富的领域经验，才能不走弯路。这样的模型迁移起来比较困难，换一个领域又需要重新进行大量的特征工程。