决策树分类思想：
用树的节点代表样本集合，通过某些判定条件来对节点内的样本进行分配，将它们划分到当前节点下的子节点，这样决策树希望各个子节点中类别的纯度之和应高于该节点中的类别纯度，达到分类效果。
节点类别纯度：
节点纯度反映的是节点样本标签的不确定性。当一个节点的纯度较低时，说明每种类别都倾向于以比较均匀的频率出现，从而我们较难在这个节点上得到关于样本标签的具体信息，其不确定性较高。当一个节点的纯度很高时，说明有些类别倾向于以比较高的频率出现，从而我们能够更有信心地把握这个节点样本标签的具体信息，即确定性较高。
不确定性的函数H§：
满足三个信息熵条件
若度量不确定性的函数H满足三个信息熵条件，
其中，信息熵条件如下：
HH关于pipi是连续函数。
若p1=…=pnp1=…=pn，则HH关于nn单调递增。
若将某一个pipi拆分为pi1pi1和pi2pi2，即pi1+pi2=pipi1+pi2=pi，则
解释：从构造和计算的角度而言，条件一是容易满足的。对于条件二而言，假设原来箱子里分别有10个球和100个球，加入每次摸到的球都是等概率抽出的，那么100个球的箱子产生的不确定性必然是要大于10个球的箱子产生的不确定性，即HH在等概率条件下关于nn递增。
条件三看上去比较复杂，但其意义是容易理解的，即nn个事件拆分为n+1个事件时的不确定性增加了，并且增加的不确定性与拆分时的比例和拆分事件的概率有关。举例来说：将p=[0.9,0.1]分别拆分为p1=[0.45,0.45,0.1]和p2=[0.9,0.05,0.05]，那么显然p1p1增加的不确定性远超过p2p2；同时，将p=[0.9,0.1]分别拆分为p3=[0.8,0.1,0.1]，那么显然p1p1增加的不确定性也远超过p3。
由于指标H§H§中的自变量pp是对于某个随机变量YY分布的描述，因此不妨将其记为信息熵H(Y)H(Y)来反应YY的不确定性。对于定义在有限状态集合*{y1,…,yK}*上的离散变量而言，对应信息熵的最大值在离散均匀分布时取到，最小值在单点分布时取到。
信息熵：
条件熵：
信息增益（Information Gain）:
有了信息熵和条件熵的基础，我们就能很自然地定义信息增益（Information Gain），即节点分裂之后带来了多少不确定性的降低或纯度的提高。在得到了随机变量XX的取值信息时，随机变量YY不确定性的平均减少量为:
G
(
Y
,
X
)
=
H
(
Y
)
−
H
(
Y
∣
X
)
G(Y,X)=H(Y)−H(Y|X)
G(Y,X)=H(Y)−H(Y∣X)
从直觉上说，随机变量Y关于X的信息增益一定是非负的，因为我们额外地知道了随机变量X的取值，这个条件降低了Y的不确定性。
对于每个节点进行分裂决策时，我们会抽出max_features个特征进行遍历以比较信息增益的大小。特征的类别可以分为三种情况讨论：类别特征、数值特征和含缺失值的特征，它们各自的处理方法略有不同。
类别：
数值：
含缺失值：
在前面的部分中，我们讨论了单个节点如何选取特征进行分裂，但没有涉及到树节点的分裂顺序。例如下图所示，假设当前已经处理完了节点2的分裂，所有黄色节点（包括2号节点）都是当前已经存在的树节点，那么我们接下来究竟应该选取叶节点3号、4号和5号中的哪一个节点来继续进行决策以生成新的叶节点6号和7号？
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XbuxjTFR-1636391550999)(E:\新建文件夹\datawhale\集成学习上\CSDN\tree_pic1.png)]
对于回归树而言，每个叶节点输出的不再是类别而是数值，其输出值为该叶节点所有样本标签值的均值。在每次分裂时，我们希望不同的子节点之间的差异较大，但每个子节点内部的差异较小。此时，分割策略仍然可以采用随机分割法或最佳分割法，只是现在不再以熵（条件熵）来评价节点（子节点）的纯度。
决策树具有很强的拟合能力，对于任何一个没有特征重复值的数据集，决策树一定能够在训练集上做到分类错误率或均方回归损失为0，因此我们应当通过一些手段来限制树的生长，这些方法被称为决策树树的剪枝方法。其中，预剪枝是指树在判断节点是否分裂的时候就预先通过一些规则来阻止其分裂，后剪枝是指在树的节点已经全部生长完成后，通过一些规则来摘除一些子树。
预剪枝：
后剪枝：
CART中用于选择变量的不纯性度量是Gini指数,最好的划分就是使得GINI_Gain最小的划分。
参考：https://blog.csdn.net/u011067360/article/details/24871801
class Node:
j=None
theta=None
p=None
left=None
right=None
class DecistonTreeBasel:
def__init__(self，max_depth,get_score, feature_sample_rate=1.0):
self.max_depth=max depth
self.get_score=get_score
self.feature_sample_raterfeature_sample_rate
def split_data(self,j,theta,X,idx):
idx1,idx2=list()，list()
for i in idx:
if x[i][j]<=theta:
idx1.append(i)
else:
idx2.append(i)
return idx1,idx2
def get_random_features(self，n):
shuffled=np.random.permutation(n)
size=int(self.feature sample rate*n)
return shuffledL:size]
def find_best_split(self,x,y,idx):
m，n=X.shape
best_score,best_j,best theta=float("inf")，-1，float("inf")
best idx1,best_idx2=list()，list()
selected_j=self.get_random_features (n)
for j in selected_j:
thetas=set([x[j] for x in x])
for theta in thetas:
idx1，idx2=self.split_data(j，theta，X，idx)
if min(len(idx1)，len(idx2))==0:
continue
scorel，score2=self.get_score(y，idx1)，self.get_score(y，idx2)
w=1.0*len(idx1)/len(idx)
score=w*score1+(1-w)* score2
if score<best_score:
best score,best_j,best_theta=score,j,theta
best idx1,best_idx2=idx1,idx2
return best_j,best_theta,best_idx1,best_idx2，best_score
def generate_tree(self，X，Y，idx，d):
r=Node ()
if d==0 or len(idx)==1:
r.p=np.average(y[idx]，axis=0)
return r
j，theta,idx1，idx2，score=self.find_best_split(x,y,idx)
current_score=self.get score(y,idx)
if score>=current score:
return r
r.j，r.theta=j,theta
r.left,r.right=self.generate_tree(x，y，idx1，d-1)，self.generate_t(X，Y，idx2，d-1)
return r
def fit(self,X，y):
self.root=self.generate_tree(X，y，range(len(X))，self.max_depth)
def get_prediction(self，r，x):
if r.left==None and r.right ==None:
return r.p
if x[r.j]<=r.theta:
return self.get_prediction(r.left，x)
else:
return.self.get_prediction(r.right，x)
def predict(self,X):
y=list()
for i in range(len(X)):
y.append(self.get_prediction(self.root,x[i]))
return np.array(y)
# 基于CART算法基类的决策树分类算法
def get_entropy(y，idx):
_，k=y.shape
p=np.average(y[idx]，axis=0)
return -np.1og(p+0.001*np.random.rand(k)).dot(p.T)
class DecisionTreeClassifier(DecisionTreeBase):
def__init__(self,max depth=0，feature_sample_rate=1.0):
super()._init__(max_depth=max_depth,
feature_sample_rate=feature_sample_rate,get_score=get_entropy)
def predict_proba(self,X):
return super().predict(X)
def predict(self，X):
proba=self.predict_proba(X)
return np.argmax(proba,axis=1)
# 基于CART算法基类的决策树回归算法
def get_var(y,idx):
y_avg=np.average(y[idx])*np.ones(len(idx))
return np.linalg.norm(y_avg -y[idx]，2)** 2/len(idx)
class DecisionTreeRegressor(DecisionTreeBase):
def_init__(self，max_depth=0，feature_sample_rate=1.0):
super().__init__(
max_depth = max_depth
feature_sample_rate = feature_sample_rate
get_score = get_var)
训练均方误差：训练集上的数据，那么这个误差为训练均方误差
测试均方误差：测试集的数据计算的均方误差，我们称为测试均方误差
目标：我们并不关心模型在训练集上的训练均方误差，我们关心的是模型面对未知的样本集，即测试集上的测试误差，我们的目标是使得我们建立的模型在测试集上的测试误差最小。
训练误差达到最小时，测试均方误差一般很大
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kV898DNg-1636391551002)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210320101534404.png)]
模型的方差：用不同的数据集去估计ff时，估计函数的改变量，例如：100个1000人的样本集。我们使用线性回归模型估计参数就能得到100个线性回归模型。由于样本抽取具有随机性，我们得到的100个模型不可能参数完全一样，那么这100个模型之间的差异就叫做方差。一个稳定的模型，也就是在不同的样本集估计的模型都不会相差太大，即要求f的方差越小越好。一般来说，模型的复杂度越高，f的方差就会越大。方差度量的是同一个模型在不同数据集上的稳定性
模型的偏差：以一个的模型去估计真实函数时存在的误差，偏差度量了某个学习算法的期望预测与真实结果的偏离程度，即刻画了某个学习算法本身的拟合能力1。偏差度量的是某个模型的学习能力。
一般而言，增加模型的复杂度，会增加模型的方差，但是会减少模型的偏差，我们要找到一个方差–偏差的权衡，使得测试均方误差最。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aU6Y7lQL-1636391551004)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210320104005434.png)]
数据本身决定模型得分上限，对数据的处理、加工非常重要，特别是结构化数据，模型的选择与调参反而是其次。
000000
将训练集数据划分为K部分，利用其中的K-1份做为训练，剩余的一份作为测试，估计由K-1个样本集得到的模型的精度，过程重复K次取平均值得到测试误差的一个估计，最后取平均测试误差做为泛化误差。这样做的好处是，训练集的所有样本都必然会成为训练数据同时页必然有机会成为一次测试集。可以更好的利用训练集数据。
K越大，平均误差被视为泛化误差这个结果就越可靠，但相应的所花费的时间也是线性增长的。
交叉验证则是对测试误差的直接估计
查看链接：
https://zhuanlan.zhihu.com/p/83841282、
在机器学习中，我们通常用参数向量w的范数来量化模型的复杂度。而L1范数、L2范数是两个最常用的范数定义。
向量w的L1范数：|w| = |w1| + |w2| + |w3|、、、、
L2：||w|| = { (w1)^2 + (w2)^2 + (w3)2、、、}0.5
在机器学习中我们普遍认为，参数w的范数越小，模型就越简单。由奥卡姆剃刀法则可知，如果两个模型在训练数据上的经验损失接近，则应该选取参数的范数较小那个。L1正则化方法的目标函数就是在经验损失基础上加入一个惩罚项入|w|。
L1正则化方法的效果：引导算法在Ls的取值接近的情况下选出L1范数较小的那个模型。
在正则化过程中：入是正则化系数，它控制正则化强度。取0的时候就不做任何正则化。而随着它增大，模型会变得越来越简单，若继续增大就会变得过简单，从而导致拟合不足，就是说会让经验损失过大。
降维算法有主成分分析方法，主成分分析的核方法(主成分分析方法的一个加强，用于某些非线性的数据分布上)，线性判别分析法(监督式学习算法)，流形降维算法，自动编码器(深度学习的降维算法)。
降维算法的主要任务是对高维特征组做低维近似。设计算法主要考量如何尽量保留原特征组所携带的重要信息。
又称PCA算法。它可以将数据投影至低维空间并使其投影方差尽可能大，所以降维后数据的方差即为降维模型的度量。由于方差能表示
一组数据的信息量，所以pca方法能够最大程度保留原始数据的信息量。
过程：
效果评估：为了评价主成分分析方法的降维效果，可以将降维后的数据再投影回原来的高维空间，这个做法称为数据重构。重构的数据越接近原始数据，降维效果越好。
主成分分析法是用线性投影的方式实现数据降维，适用于高维空间中的数据近似地分布于某个低维线性子空间的情形。因此对于n个特征之间存在线性相关关系，适用主成分分析法。但对于非线性时，适用主成分分析的核方法。
又看到了协方差矩阵这个东西，作图像基本就绕不过它，虽然公式网上都有，但是不太明白它的物理意义，通俗的说，它到底是干嘛的，为啥总露脸，哪里都看得到~~单以前看PCA的时候就特困扰，没想到现在还是搞不清楚，索性开始查协方差矩阵的资料，恶补之后决定马上记录下来。
在讲协方差之前，先谈谈均值、标准差、方差。
均值描述的是样本集合的中间点，它告诉我们的信息是很有限的，而标准差给我们描述的则是样本集合的各个样本点到均值的距离之平均。以这两个集合为例，[0，8，12，20]和[8，9，11，12]，两个集合的均值都是10，但显然两个集合差别是很大的，计算两者的标准差，前者是8.3，后者是1.8，显然后者较为集中，故其标准差小一些，标准差描述的就是这种“散布度”。之所以除以n-1而不是除以n，是因为这样能使我们以较小的样本集更好的逼近总体的标准差，即统计上所谓的“无偏估计”。而方差则仅仅是标准差的平方。
我们应该注意到，标准差和方差一般是用来描述一维数据的，但现实生活我们常常遇到含有多维数据的数据集，最简单的大家上学时免不了要统计多个学科的考试成绩。面对这样的数据集，我们当然可以按照每一维独立的计算其方差，但是通常我们还想了解更多，比如，一个男孩子的猥琐程度跟他受女孩子欢迎程度是否存在一些联系啊，嘿嘿~协方差就是这样一种用来度量两个随机变量关系的统计量。
协方差多了就是协方差矩阵
上一节提到的猥琐和受欢迎的问题是典型二维问题，而协方差也只能处理二维问题，那维数多了自然就需要计算多个协方差，比如n维的数据集就需要计算n*(n-1)/2 ( 1+2+3+…+n-1+n-n）个协方差，那自然而然的我们会想到使用矩阵来组织这些数据。于是就有了协方差矩。协方差矩阵是一个对称的矩阵，而且对角线是各个维度上的方差。
根据公式，计算协方差需要计算均值，那是按行计算均值还是按列呢，我一开始就老是困扰这个问题。前面我们也特别强调了，协方差矩阵是计算不同维度间的协方差，要时刻牢记这一点。样本矩阵的每行是一个样本，每列为一个维度，所以我们要按列计算均值。
原来协方差矩阵还可以这样计算，先让样本矩阵中心化，即每一维度减去该维度的均值，使每一维度上的均值为0，然后直接用新的到的样本矩阵乘上它的转置，然后除以(N-1)即可。
总结：理解协方差矩阵的关键就在于牢记它计算的是不同维度之间的协方差，而不是不同样本之间，拿到一个样本矩阵，我们最先要明确的就是一行是一个样本还是一个维度。
机器学习的理论，同时也在天池，datawhale，这些平台参加组队学习，巩固机器学习的基础，
泰迪杯B，进一步自学有关，图像处理方面
准备四级
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VuYGnrH9-1636391551006)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210328203928881.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mB4R9KyP-1636391551007)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210328204428617.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ydOrlhO1-1636391551009)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210328204721476.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-65sxaRHD-1636391551010)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210328210026602.png)]
LEETCODE
必须了解用了什么算法，什么模型，做这个比赛的流程，
预处理、提取、选择：结构化数据、图像数据、非结构化数据
决定系数：R2（R-Square）：R2方法是将预测值跟只使用均值的情况下相比，看能好多少。其区间通常在（0,1）之间。0表示还不如什么都不预测，直接取均值的情况，而1表示所有预测跟真实结果完美匹配的情况。
R方一个综合评估的指标，可以理解为因变量y中的变异性能能够被估计的多元回归方程解释的比例，它衡量各个自变量对因变量变动的解释程度，分母理解为原始数据的离散程度，分子为预测数据和原始数据的误差，二者相除可以消除原始数据离散程度的影响.其取值在0与1之间，其值越接近1，则变量的解释程度就越高，其值越接近0，其解释程度就越弱。
理论上取值范围（-∞，1], 正常取值范围为[0 1] ------实际操作中通常会选择拟合较好的曲线计算R²，因此很少出现-∞
越接近1，表明方程的变量对y的解释能力越强，这个模型对数据拟合的也较好
越接近0，表明模型拟合的越差
经验值：>0.4， 拟合效果好
优点：既考虑了预测值与真值之间的差异，也考虑了问题本身真值之间的差异，是一个归一化的度量标准。
缺点： 数据集的样本越大，R²越大，因此，不同数据集的模型结果比较会有一定的误差
参考：https://blog.csdn.net/AIYA_aya/article/details/95905319
#r2_score
from sklearn.metrics import r2_score
y_true=[3,-0.5,2,7]
y_pred=[2.5,0.0,2,8]
print(r2_score(y_true,y_pred))
y_true=[[0.5,1],[-1,1],[7,-6]]
y_pred=[[0,2],[-1,2],[8,-5]]
print(r2_score(y_true,y_pred,multioutput="variance_weighted"))
y_true=[[0.5,1],[-1,1],[7,-6]]
y_pred=[[0,2],[-1,2],[8,-5]]
print(r2_score(y_true,y_pred,multioutput="uniform_average"))
print(r2_score(y_true,y_pred,multioutput="raw_values"))
print(r2_score(y_true,y_pred,multioutput=[0.3,0.7]))
#结果
#0.948608137045
#0.938256658596
#0.936800526662
#[ 0.96543779 0.90816327]
#0.92534562212
均方误差：MSE（Mean Squared Error）：L2范数损失，该指标计算的是拟合数据和原始数据对应样本点的误差的平方和的均值，其值越小说明拟合效果越好。常被用作线性回归的损失函数。
优点：解决了不光滑的问题（即不可导问题）。
缺点：MSE与我们的目标变量的量纲不一致，为了保证量纲一致性，我们需要对MSE进行开方，得到RMSE。
#mean_squared_error
from sklearn.metrics import mean_squared_error
y_true=[3,-0.5,2,7]
y_pred=[2.5,0.0,2,8]
print(mean_squared_error(y_true,y_pred))
y_true=[[0.5,1],[-1,1],[7,-6]]
y_pred=[[0,2],[-1,2],[8,-5]]
print(mean_squared_error(y_true,y_pred))
#结果
#0.375
#0.708333333333
【练习】假设使用闵氏距离来度量两个嵌入向量之间的距离，此时对叶子节点的编号顺序会对距离的度量结果有影响吗？
Answer:应该不会。
只要了解决策树的算法，那么随机森林是相当容易理解的。随机森林的算法可以用如下几个步骤概括：
用有抽样放回的方法（bootstrap）从样本集中选取n个样本作为一个训练集
用抽样得到的样本集生成一棵决策树。在生成的每一个结点：
随机不重复地选择d个特征
利用这d个特征分别对样本集进行划分，找到最佳的划分特征（可用基尼系数、增益率或者信息增益判别）
重复步骤1到步骤2共k次，k即为随机森林中决策树的个数。
用训练得到的随机森林对测试样本进行预测，并用票选法决定预测的结果。
原文链接：https://blog.csdn.net/zjuPeco/article/details/77371645
没错，就是这个到处都是随机取值的算法，在分类和回归上有着极佳的效果，是不是觉得强的没法解释~
然而本文的重点不是这个，而是接下来的特征重要性评估。
现实情况下，一个数据集中往往有成百上前个特征，如何在其中选择比结果影响最大的那几个特征，以此来缩减建立模型时的特征数是我们比较关心的问题。这样的方法其实很多，比如主成分分析，lasso等等。不过，这里我们要介绍的是用随机森林来对进行特征筛选。
用随机森林进行特征重要性评估的思想其实很简单，说白了就是看看每个特征在随机森林中的每颗树上做了多大的贡献，然后取个平均值，最后比一比特征之间的贡献大小。
好了，那么这个贡献是怎么一个说法呢？通常可以用基尼指数（Gini index）或者袋外数据（OOB）错误率作为评价指标来衡量。
原文链接：https://blog.csdn.net/zjuPeco/article/details/77371645
值得庆幸的是，s k l e a r n sklearnsklearn已经帮我们封装好了一切，我们只需要调用其中的函数即可。
我们以UCI上葡萄酒的例子为例，首先导入数据集。
import pandas as pd
url = 'http://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data'
df = pd.read_csv(url, header = None)
df.columns = ['Class label', 'Alcohol', 'Malic acid', 'Ash',
'Alcalinity of ash', 'Magnesium', 'Total phenols',
'Flavanoids', 'Nonflavanoid phenols', 'Proanthocyanins',
'Color intensity', 'Hue', 'OD280/OD315 of diluted wines', 'Proline']
# 然后，我们来大致看下这时一个怎么样的数据集
import numpy as np
np.unique(df['Class label'])
#输出：array([1, 2, 3], dtype=int64)
# 然后再来看下数据的信息：
df.info()
'''
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 178 entries, 0 to 177
Data columns (total 14 columns):
Class label 178 non-null int64
Alcohol 178 non-null float64
Malic acid 178 non-null float64
Ash 178 non-null float64
Alcalinity of ash 178 non-null float64
Magnesium 178 non-null int64
Total phenols 178 non-null float64
Flavanoids 178 non-null float64
Nonflavanoid phenols 178 non-null float64
Proanthocyanins 178 non-null float64
Color intensity 178 non-null float64
Hue 178 non-null float64
OD280/OD315 of diluted wines 178 non-null float64
Proline 178 non-null int64
dtypes: float64(11), int64(3)
memory usage: 19.5 KB
'''
# 可见除去class label之外共有13个特征，数据集的大小为178。
# 按照常规做法，将数据集分为训练集和测试集。
from sklearn.cross_validation import train_test_split
from sklearn.ensemble import RandomForestClassifier
x, y = df.iloc[:, 1:].values, df.iloc[:, 0].values
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.3, random_state = 0)
feat_labels = df.columns[1:]
forest = RandomForestClassifier(n_estimators=10000, random_state=0, n_jobs=-1)
forest.fit(x_train, y_train)
# 好了，这样一来随机森林就训练好了，其中已经把特征的重要性评估也做好了，我们拿出来看下。
importances = forest.feature_importances_
indices = np.argsort(importances)[::-1]
for f in range(x_train.shape[1]):
print("%2d) %-*s %f" % (f + 1, 30, feat_labels[indices[f]], importances[indices[f]]))
# 输出的结果为
'''
1) Color intensity 0.182483
2) Proline 0.158610
3) Flavanoids 0.150948
4) OD280/OD315 of diluted wines 0.131987
5) Alcohol 0.106589
6) Hue 0.078243
7) Total phenols 0.060718
8) Alcalinity of ash 0.032033
9) Malic acid 0.025400
10) Proanthocyanins 0.022351
11) Magnesium 0.022078
12) Nonflavanoid phenols 0.014645
13) Ash 0.013916
'''
# 如果要筛选出重要性比较高的变量的话，这么做就可以
threshold = 0.15
x_selected = x_train[:, importances > threshold]
x_selected.shape
'''
(124, 3)
'''
# 瞧，这不，帮我们选好了3个重要性大于0.15的特征了吗~
孤立森林也是一种使用树来进行集成的算法，其功能是用于连续特征数据的异常检测。孤立森林的基本思想是：多次随机选取特征和对应的分割点以分开空间中样本点，那么异常点很容易在较早的几次分割中就已经与其他样本隔开，正常点由于较为紧密故需要更多的分割次数才能将其分开。下图中体现了两个特征下的4次分割过程，可见右上角的异常点已经被单独隔离开。
理解：孤立森林 （Isolation Forest, iForest）是一个基于Ensemble的快速离群点检测方法，具有线性时间复杂度和高精准度，是符合大数据处理要求的State-of-the-art算法。由南京大学周志华教授等人于2008年首次提出，之后又于2012年提出了改进版本。适用于连续数据（Continuous numerical data）的异常检测，与其他异常检测算法通过距离、密度等量化指标来刻画样本间的疏离程度不同，孤立森林算法通过对样本点的孤立来检测异常值。具体来说，该算法利用一种名为孤立树（iTree）的二叉搜索树结构来孤立样本。由于异常值的数量较少且与大部分样本的疏离性，因此，异常值会被更早的孤立出来，也即异常值会距离iTree的根节点更近，而正常值则会距离根节点有更远的距离。此外，相较于LOF，K-means等传统算法，孤立森林算法对高纬数据有较好的鲁棒性。其可以用于网络安全中的攻击检测，金融交易欺诈检测，疾病侦测，和噪声数据过滤等。
原理：对于如何查找哪些点是否容易被孤立，iForest使用了一套非常高效的策略。假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间（想象拿刀切蛋糕一分为二）。之后我们再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。直观上来讲，我们可以发现那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点很容易很早的就停到一个子空间了。上图里面黑色的点就很容易被切几次就停到一个子空间，而白色点聚集的地方可以切很多次才停止。
算法：怎么来切这个数据空间是iForest的设计核心思想，本文仅介绍最基本的方法。由于切割是随机的，所以需要用Ensemble的方法来得到一个收敛值（蒙特卡洛方法），即反复从头开始切，然后平均每次切的结果。iForest 由 t 个 iTree 组成，每个 iTree 是一个二叉树结构。该算法大致可以分为两个阶段，第一个阶段我们需要训练出 t 颗孤立树，组成孤立森林。随后我们将每个样本点带入森林中的每棵孤立树，计算平均高度，之后再计算每个样本点的异常值分数。
第一阶段，步骤如下：
（1）从训练数据中随机选择Ψ个点样本点作为样本子集，放入树的根节点。
（2）随机指定一个维度（特征），在当前节点数据中随机产生一个切割点 p（切割点产生于当前节点数据中指定维度的最大值和最小值之间）。
（3）以此切割点生成了一个超平面，然后将当前节点数据空间划分为2个子空间：把指定维度里小于 p 的数据放在当前节点的左子节点，把大于等于 p 的数据放在当前节点的右子节点。
（4）在子节点中递归步骤（2）和（3），不断构造新的孩子节点，直到子节点中只有一个数据（无法再继续切割）或子节点已到达限定高度。
（5）循环（1）至（4），直至生成 t 个孤立树iTree。
第二阶段：
获得t个iTree之后，iForest 训练就结束，然后我们可以用生成的iForest来评估测试数据了。对于每一个数据点 xi，令其遍历每一颗孤立树（iTree），计算点 xi 在森林中的平均高度好h(xi)，对所有点的平均高度做归一化处理。
from sklearn.ensemble import IsolationForest
X = [[-1.1], [0.3], [0.5], [100]]
clf = IsolationForest(random_state=0).fit(X)
clf.predict([[0.1], [0], [90]])
array([ 1, 1, -1])
补充：
1. iForest具有线性时间复杂度。因为是ensemble的方法，所以可以用在含有海量数据的数据集上面。通常树的数量越多，算法越稳定。由于每棵树都是互相独立生成的，因此可以部署在大规模分布式系统上来加速运算。
2. iForest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。对这类数据，建议使用子空间异常检测（Subspace Anomaly Detection）技术。此外，切割平面默认是axis-parallel的，也可以随机生成各种角度的切割平面，详见“On Detecting Clustered Anomalies Using SCiForest”。
3. iForest仅对Global Anomaly敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （Local Anomaly）。目前已有改进方法发表于PAKDD，详见“Improving iForest with Relative Mass”。
4. iForest推动了重心估计（Mass Estimation）理论发展，目前在分类聚类和异常检测中都取得显著效果，发表于各大顶级数据挖掘会议和期刊（如SIGKDD，ICDM，ECML）。
#############################################
首先这三种算法都属于Boosting方法，且GBDT是机器学习算法，XGBoost和LightGBM是GBDT的算法实现。
Boosting方法训练基分类器时采用串行的方式，各个基分类器之间
有依赖。其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。这个过程是在不断地减小损失函数，使得模型偏差不断降低。但Boosting的过程并不会显著降低方差。这是因为Boosting的训练过程使得各弱分类器之间是强相关的，缺乏独立性，所以并不会对降低方差有作用。
Gradient Boosting是Boosting中的一大类算法，算法1描述了Gradient
Boosting算法的基本流程，在每一轮迭代中，首先计算出当前模型在所
有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合
并计算出该弱分类器的权重，最终实现对模型的更新。
enter description here
1)预测阶段的计算速度快，树与树之间可并行化计算。
2)在分布稠密的数据集上，泛化能力和表达能力都很好。
3)采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。
1)GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。
2)GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理 数值特征时明显。
3)训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。
链接：https://www.jianshu.com/p/765efe2b951a
https://zhuanlan.zhihu.com/p/99069186
来源：简书、知乎。
import pandas as pd
import numpy as np
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.metrics import roc_curve,auc
from sklearn import metrics
from sklearn.model_selection import GridSearchCV
from sklearn.preprocessing import LabelEncoder
#读取数据
data = pd.read_excel(r'E:/wyz/Desktop/data/data.xlsx')
#将数据集中的字符串转化为代表类别的数字。因为sklearn的决策树只识别数字
le = LabelEncoder()
for col in data_model.columns:
data_model[col] = le.fit_transform(data_model[col].astype(str))
#划分数据集（3、7划分）
y = data_model['target']
x = data_model.drop('target', axis=1)
x_train, x_test, y_train, y_test = train_test_split(x, y,random_state=0,train_size=0.7)
#标准化数据
ss_x = StandardScaler()
ss_y = StandardScaler()
x_train = ss_x.fit_transform(x_train)
x_test = ss_x.transform(x_test)
model_GBDT = GradientBoostingClassifier(random_state=10)
model_GBDT.fit(x_train,y_train)
y_pred = gbm0.predict(x_train)
y_predprob = model_GBDT.predict_proba(x_train)[:,1]
print ("Accuracy : %.4g" % metrics.accuracy_score(y.values, y_pred))
print ("AUC Score (Train): %f" % metrics.roc_auc_score(y, y_predprob))
# https://blog.csdn.net/weixin_41851055/article/details/106260066
import numpy as np
import math
'''
Input: x,y,splint_point_array(该特征的所有切分点)
Output:minloss(所有切分点中最小损失)，最优切分点，残值数组（下一次在此基础进行拟合）
'''
def findBestSplitPoint(x_array,y_array,split_point_array):
minloss = np.inf
best_split_point = 0
best_c1 = 0
best_c2 = 0
best_R1 = 0
best_R2 = 0
#遍历切分点
for c in split_point_array:
loss = 0
# math.floor() 向下取整，划分R1/R2区域
R1 = y_array[:x_array.index(math.floor(c))+1]
R2 = y_array[x_array.index(math.floor(c))+1:]
c1 = np.mean(R1)
c2 = np.mean(R2)
for y in y_array:
if y in R1:
loss+=(y - c1)**2
else:
loss+=(y - c2)**2
if loss < minloss:
minloss = loss
best_split_point = c
best_c1 = c1
best_c2 = c2
best_R1 = R1
best_R2 = R2
#残值结果，用于下一次拟合
residual_array = np.hstack((best_R1-best_c1, best_R2-best_c2))
return minloss,best_split_point,list(residual_array)
x = [1,2,3,4,5,6,7,8,9,10]
y = [5.56,5.70,5.91,6.40,6.80,7.05,8.9,8.70,9.00,9.05]
#切分点
split_point_array = [1.5,2.5,3.5,4.5,6.5,7.5,8.5,9.5]
print(findBestSplitPoint(x,y,split_point_array))
#https://blog.csdn.net/forestForQuietLive/article/details/89335508
优点：泛化错误率低， 码，可以应用在大部分分类器上，无参数调 。
缺点：对离 点敏 。
适用数据类型：数值型和标 型数据。
能否使用弱分类器和多个实例来构建一个强分类器？这是一个非常有趣的理论问题。这里的“弱”意味着分类器的性能比随机猜测要略好，但是也不会好太多。这就是说，在二分类情况下弱分类器的错误率会高于5 0 %，而 “强”分类器的错误率将会低很多。AdaBoost运行过程如下：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量乃。一开始，这些权重都初始化成相等值。首 先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果 ，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v4XgJvpV-1636391551012)(E:\新建文件夹\datawhale\集成学习上\CSDN\屏幕截图 2021-10-30 220836.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WKYnMLe5-1636391551013)(E:\新建文件夹\datawhale\集成学习上\CSDN\屏幕截图 2021-10-30 222524.png)]
class AdaBoost:
def __init__(self, n_estimators=100):
self.clf_num = n_estimators
def init_args(self, X, y):
self.X = X
self.y = y
M, _ = X.shape
self.models = []
self.alphas = []
self.weights = np.ones(M) / M # 1
def fit(self, X, y):
self.init_args(X, y)
for n in range(self.clf_num):
cla = DecisionTreeClassifier(max_depth=1) # weak cla
cla.fit(X, y, sample_weight=self.weights) # 2(a)
P = cla.predict(X)
err = self.weights.dot(P != y) # 2(b) 8.1
alpha = 0.5*(np.log(1 - err) - np.log(err)) # 2(c) 8.2
self.weights = self.weights * np.exp(-alpha * y * P)
self.weights = self.weights / self.weights.sum() # 2(d) 8.3, 8.4, 8.5
self.models.append(cla)
self.alphas.append(alpha)
return 'Done!'
def predict(self, x):
N, _ = x.shape
FX = np.zeros(N)
for alpha, cla in zip(self.alphas, self.models):
FX += alpha * cla.predict(x)
return np.sign(FX)
def score(self, X_test, y_test):
p = self.predict(X_test)
r = np.sum(p == y_test)
return r/len(X_test)
def _weights(self):
return self.alphas, self.weights, self.models
adaboost = AdaBoost()
adab
oost.fit(X_train, y_train)
#输出 'Done!'
adaboost.score(X_test, y_test)
#输出 1.0
【练习】左侧公式的第二个等号是由于当样本分类正确时，…，当样本分类错误时， …请说明原因。
【练习】对公式进行化简，写出K=2K=2时的SAMME算法流程，并与李航《统计学习方法》一书中所述的Adaboost二分类算法对比是否一致。
【练习】在sklearn源码中找出算法流程中每一行对应的处理代码。
【练习】算法2第12行中给出了ff输出的迭代方案，但在sklearn包的实现中使用了I{G∗(x)=S(y)}I{G∗(x)=S(y)}来代替b∗(m)(x)b∗(m)(x)。请根据本文的实现，对sklearn包的源码进行修改并构造一个例子来比较它们的输出是否会不同。（提示：修改AdaboostClassifier类中的decision_function函数和staged_decision_function函数）
待补
or必须限制使用支持概率预测的分类器。SAMME算法则没有这个限制。
【练习】左侧公式的第二个等号是由于当样本分类正确时，…，当样本分类错误时， …请说明原因。
【练习】对公式进行化简，写出K=2K=2时的SAMME算法流程，并与李航《统计学习方法》一书中所述的Adaboost二分类算法对比是否一致。
【练习】在sklearn源码中找出算法流程中每一行对应的处理代码。
【练习】算法2第12行中给出了ff输出的迭代方案，但在sklearn包的实现中使用了I{G∗(x)=S(y)}I{G∗(x)=S(y)}来代替b∗(m)(x)b∗(m)(x)。请根据本文的实现，对sklearn包的源码进行修改并构造一个例子来比较它们的输出是否会不同。（提示：修改AdaboostClassifier类中的decision_function函数和staged_decision_function函数）
待补