决策树
纯度和信息熵：
决策树构造的过程就是为寻找纯净划分的过程，数学上的解释，就是让目标变量分歧最小。比如有3个集合：集合1有6次去打球；集合2有5次去打球，1次不去；集合3有3次去打球，3次不去。按纯度划分就是集合1>集合2>集合3。集合1的分歧最小，集合3分歧最大。
熵（entropy）：表示了信息的不确定性。
image.png
t是节点，i是分类。log2取以2为底的对数，加上负号是因为Log 1/P = logP ^ -1=-logP,概率导数变成了负号然后拿到前面去了。继续3上面3个集合的例子，集合2信息熵可以写成
image.png
集合3信息熵可以写成
image.png
可以看出信息熵越大，纯度越低。
ID3(信息增益）
信息增益 = 信息熵（整体的不确定性）- 条件熵（某一条件下/分支，随机变量的不确定性）
所以信息增益代表了在某一条件下，信息不确定性减少的程度。减少的越多，我们越选这个特征。公式就不贴了，但是信息增益有个问题，比方说特征“ID”可以获得很大的信息增益，纯度也很大，但是这样的决策树没有意义。 ID3比较偏向取值较多的属性进行分割，存在一定的偏好。为了减少这一影响，提出了C4.5。
C4.5(信息增益率)
相比ID3，C4.5有哪些改进和优势？
1.信息增益率
信息增益率 = 信息增益 / 属性熵，当属性有很多值时，如“ID” 相当于被分成了许多份，但是对于C4.5来说，属性熵也会变大，所以整体的信息增益率并不大。
2.悲观剪枝
悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。ID3在构造剪枝时，容易产生过拟合的情况。在C4.5采用悲观剪枝后，可以提升决策树的泛化能力。
3.离散化处理连续属性，比如湿度属性，按湿度值来进行计算，然后选择阈值。
4.处理缺失值，C4.5可以在数值缺失的情况下，依然可以计算信息增益，并对属性进行选择。
总结一下，ID3优点是方法简单，但是对噪声敏感。训练数据如果有少莲数据，会产生决策树分类错误。C4.5用信息增益率替代了信息增益解决了噪声敏感的问题，可以对树进行剪枝，处理连续值及数值缺失等情况。但由于C4.5需要对数据集进行多次扫描，算法效率较低
CART
CART与C4.5算法类似，只是属性选择的指标采用的是基尼系数。基尼系数本身反映了样本的不确定性。基尼系数越小，说明样本间的差异性越小，不确定程度越低。分类的过程本身就是一个不确定度降低的过程，即纯度提升的过程。所以CART算法在构造分类树时，会选择基尼系数最小的属性作为属性的划分。
image.png
针对集合1，所有人都去打篮球，所以p(Ck|t)=1，因此 GINI(t)=1-1=0。而集合3，一半人去，一半人不去，所以p(C1|t)=0.5，p(C2|t)=0.5，GINI(t)=1-（0.5 * 0.5+0.5*0.5）=0.5。
通过集合1和集合3两个样本，集合1的基尼系数最小，说明样本最稳定，而集合2的样本不稳定性更大。无论ID3,C4.5,CART 都是决策树的方法，一棵树一个特征，多棵树就是多个特征并形成森林。
随机森林RandomForest：
随机+森林：
· 随机：训练集随机，bootstrap 随机有放回抽样
特征随机, 从M个特征中随机抽取m个特征（M>m),降维
· 森林：多个决策树,解决了决策树泛化能力弱
sklearn中的应用
sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion='gini', max_depth=None, bootstrap=True, random_state=None, min_samples_split=2)
n_estimators: optional(default-10)森林里的树木数量
criteria: string,可选（default='gini'）分割特征的测量方法
max_depth: 默认为无，树的最大深度5，8，15，25，30
max_features='auto' 每个决策树的最大特征
boostrap:default = True，是否在构建数时使用放回抽样
min_samples_split: 节点划分最少样本数
min_samples_leaf: 叶子节点的最小样本数
超参数：n_estimator, max_depth, min_samples_split, min_samples_leaf
随机森林是集成思想的一种，什么是集成思想了？
集成思想：
Boosting通过将弱学习器提升为强学习器的集成方法（AdaBoost,GBDT）
Bagging通过自助采样的方法生成众多并行式分类器，通过“少数服从多数”的原则来确定最终的结果（RandomForest）
集成学习在各个规模的数据集上都有很好的策略。
数据集大：划分成多个小数据集，学习多个模型进行组合。
数据集小：利用Bootstrap方法进行抽样，得到多个数据集，分别训练多个模型再进行组合。
Adaboost:adaptive Boosting自适应算法
在算法开始的时候，为每一个样本赋一个权重，这时大家都是一样重要的。在每一步训练中，会使得数据点的估计有对有错，故在每一步结束后，增加分错点的权重，减少分对点的权重，这样如果某些点老是被分错，就会被“重点关注”，也就被赋予一个很高的权重。
这样N次迭代后，会得到N个简单的分类器，然后我们把它们组合起来（加权或者投票），得到一个最终模型。
GBDT
Gradient Boosting Decision Tree 梯度上升树，GBDT虽然以CART作为基分类器，但是GBDT是回归树不是分类树。GBDT的核心在于每一棵树学的是之前所有树结论和的残差(负梯度)，Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。
比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。
Adaboost和GBDT的区别：
Adaboost重点在对调整错分类样本的权重。对样本分类后，根据对错来调整权重weight，错分的样本权重越来越大，使它们更被重视。
GBDT重点在消除残差residual。在残差减少的梯度方向建立一个新的树，建完后还有残差再继续建立树，这样一步步逼近最终结果。这种串行的过程很有效，但是无法并行化，使得计算复杂度搞，同时不太适合高维稀疏特征。
XGBoost
相对于传统GBDT，XGBoost对其进行了优化。
-
基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性回归，此时XGBoost相当于带L1和L2正则化项的Logisitc（分类问题）或者线性回归（回归问题）
-
导数信息：XGBoost对损失函数做了二阶泰勒展开，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导。
什么是泰勒展开式？泰勒展开式就是把一个三角函数或者指数函数或者其他比较难缠的函数用多项式替换掉。也就是说，有一个原函数 f(x) ，我再造一个图像与原函数图像相似的多项式函数 g(x),为了保证相似，我只需要保证这俩函数在某一点的初始值相等，1阶导数相等，2阶导数相等，……n阶导数相等。
也就是说，有一个原函数** ，我再造一个图像与原函数图像相似的多项式函数 ,为了保证相似，我只需要保证这俩函数在某一点的初始值相等，1阶导数相等，2阶导数相等，……n阶导数相等。相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。 -
正则项：XGBoost的目标函数加了正则项， 相当于预剪枝，使得学习出来的模型更加不容易过拟合。
-
列抽样：XGBoost支持列采样，与随机森林类似，用于防止过拟合。
-
缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支
-
并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。支持GPU加速，支持分布式，如果你是CPU，则支持CPU多核并行计算。
在xgboost中：
import xgboost as xgb
from sklearn.metrics import accuracy score
#load data,训练集和测试集
my_workpath = './data'
#xgb加载数据到对象DMatrix中，做了存储效率和运行速度的优化
dtrain = xgb.DMatrix(my_workpath + 'agaricus.txt.train')
dtest = xgb.DMatrix(my_workpath + 'agaricus.txt.test')
#specify parameters via map 设置训练参数
#max_depth:树的最大深度，默认值为6，取值范围为[1,无穷大]
#eta:为防止过拟合，更新过程中用到的收缩步长。默认值为0.3，取值范围为[0,1]
#objective:定义学习任务对应的target，"binary:logistic"表示二分类逻辑回归问题， 输出为概率
param = {'max_depth':2, 'eta':1, 'silent':0, 'objective':'binaray:logistic'}
#模型训练
num_round = 2
bst = xgb.train(param,dtrain,num_round)
#预测prediction
train_preds = bst.predict(dtrain)
train_predictions = [round(value) for value in train_preds]
y_train = dtrain.get_label()
train_accuracy = accuracy_score(y_train,train_predictions)
print("Train Accuracy: %.2f%%" % (train_accuracy * 100.0))
调用xgb中plot_tree模型可视化,三个参数：1.模型；2.树的索引(从0开始)；3.显示方向，默认为数值，‘LR’是水平方向
from matplotlib import pylot
import graphviz
xgb.plot_tree(bst, num_trees = 0, rankdir='LR')
pyplot.show()
通过学习曲线查看调参后性能变化,在sklearn中
#设置boosting迭代计算次数
num_round = 100
bst = XGBClassifier(max_depth=2,leraning_rate=0.1, n_estimators=num_round, silent=True，objective=logistic)
#设置评估集
eval_set = [(x_train_part,y_train_part),(x_validation,y_validation)]
bst.fit(x_train_part, y_train_part,eval_metric = ["error","logloss"],eval_set=eval_set,verbose=False)
#显示学习曲线
results = bst.evals_result()
epochs = len(result['validation_0']['error'])
x_axis = range(0,epochs)
fig,ax = pyplot.subplots()
ax.plot(x_axis, results['validation_0']['logloss'], label='Train')
ax.plot(x_axis, results['validation_1']['logloss'], label='Test')
ax.legend()
pyplolt.ylabel('Log Loss')
pyplot.title('XGBoost Log Loss')
pyplot.show()
image.png
Early stop:一种防止过拟合的方法（模型被训练的太复杂）
#设置boosting迭代计算次数
num_round = 100
eval_set = [(x_validation,y_validation)]
#early_stopping_rounds=10,在接下来的10轮中性能还没有提升就停止。
bst.fit(x_train_part, y_train_part,early_stopping_rounds=10,eval_metrics="error",eval_set=eval_set,verbose=False)
image.png
最佳迭代是10
验证方法：
train_test_split是比较常用的，速度快，而且适合大规模数据。但是分割太粗暴，随机性太强，比如恰好分到test集的和train集的差异大了？所以提出了交叉验证（cross-validation）但是训练时间太长。这里提出k-fold cross validation,把训练集等分成K分（K通常取3，5，10），每次留一份做validation，其余k-1做训练。这样得到的估计比train_test_split得到的估计方差更小。
在sklearn中
from sklearn.model_selection import KFold
from sklearn.model_slection import cross_val_score
kfold = KFold(n_split=10, random_state=7)
results = cross_val_score(model, X, Y ,cv=kfold)
print("Accuracy:%.ef%%(%.2f%%)"%*(results.men()*100,results.std()*100))
可以根据上面交叉验证评估后的结果来选择最佳参数调优，这里提一下网格搜索（GridSearchCV）
from sklearn.grid_search import GridSearchCV
param_test = {'n_estimators': range(1,51,1)}
clf = GridSearchCV(estimator = bst, param_grid=param_test, scoring = 'accuracy', cv=5)
clf.fit(x_train, y_train)
clf.grid_scors,_, clf.best_params_, clf.best_score_
GridSearchCV(estimator, param_grid, scoring=None, fit_params=None, n_jobs=1, iid=True, refit=True, cv=None, verbose=0, pre_dispatch='2*n_jobs',error_score='raise', return_train_score=True)
LightGBM
LightGBM高效，并行计算速度快，占用内存小。
在实际应用中，面对的数据集维度可能非常高（特征多），同时数据样本也很大（训练实例多），这样一来许多算法在训练速度和可扩展性方面就显得力不从心了。最主要的原因是，对于每一个特征这些算法需要扫描每一个数据实例来计算最佳的信息增益从而确定最佳的分裂节点，这是非常耗时间的。xgboost面临的问题：
1.每次迭代都要读取整个数据集，耗时耗内存
- 贪心计算分裂节点时，预先将特征值进行排序，排序后保存排序结果，耗时耗内存
3.计算分裂节点时，要遍历每个一个候选节点，然后计算分裂后的信息增益，耗时
4.生成决策树是level-wise也就是预先设置好树的深度之后，每一颗树都需要生长到设置的那个深度，这样有些树在某一次分裂之后效果甚至没有提升但仍然会继续划分树枝，然后再次划分....之后就是无用功了，耗时。
为避免xgboost的缺陷，lightGBM在传统GBDT算法上加了两个技术：
1.单边梯度采样GOSS
2.互斥稀疏特征绑定EFB
使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGB遍历所有特征值节省了不少开销；使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
另外，histogram-based algorithm不是ligthGBM特有的，GBDT也采用这样的算法，将连续的特征映射到离散的buckets中，组成一个个的bins，然后使用这些bins建立直方图。简而言之就是将连续变量离散化。
import lightgbm as lgb
# 创建模型，训练模型
gbm = lgb.LGBMRegressor(objective='regression',num_leaves=31,learning_rate=0.05,n_estimators=20)
gbm.fit(X_train, y_train,eval_set=[(X_test, y_test)],eval_metric='l1',early_stopping_rounds=5)
# 测试机预测
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_)
# 模型评估
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)
# feature importances
print('Feature importances:', list(gbm.feature_importances_))
# 网格搜索，参数优化
estimator = lgb.LGBMRegressor(num_leaves=31)
param_grid = {
'learning_rate': [0.01, 0.1, 1],
'n_estimators': [20, 40]
}
gbm = GridSearchCV(estimator, param_grid)
gbm.fit(X_train, y_train)
print('Best parameters found by grid search are:', gbm.best_params_)
网友评论