LearningunderConceptDrift：AReview概念漂移综述论⽂阅读⾸先这是2018年⼀篇关于概念漂移综述的论⽂[1]。
最新的研究内容包括
（1）在⾮结构化和噪声数据集中怎么准确的检测概念漂移。how to accurately detect concept drift in unstructured and noisy datats
（2）怎么⽤⼀种可解释的⽅法来定量理解概念漂移。how to quantitatively understand concept drift in a explainable way
（3）如何有效的结合相关知识和概念漂移。how to effectively react to drift by adapting related knowledge
该论⽂做了：
（1）总结了概念漂移的研究成果，将概念漂移研究分为三类：概念漂移检测、概念漂移理解和概念漂移适应，为概念漂移研究的发展提供了清晰的框架。
（2）提出了⼀种新的概念漂移理解⽅法，⽤于从时间、⽅式和地点三个⽅⾯检索概念漂移的状态信息。
（3）揭⽰了概念漂移下的主动学习技术和基于模糊能⼒模型的漂移检测技术，并对涉及到概念漂移的相关研究进⾏了综述。
（4）系统地检查两套概念漂移数据集，合成数据集和真实数据集，通过多个维度：数据集描述，可⽤性，漂移类型的适⽤性，和现有的应⽤程序。
（5）提出了该领域的⼏个新的研究课题和潜在的研究⽅向。
论⽂中图
概念漂移的定义：
给定⼀个时间范围[0, t]，样本表⽰为S0,t ={d0, . . . , d t}，其中d i = (X i , y i)是对于概念的⼀次观察，Xi是特征向量，y是标签，S0,t服从⼀个确定分布F0,t(X, y).
如果F0,t(X, y) ≠ F t+1,∞(X, y)，则称概念漂移发⽣在t+1时刻，记为∃t: P t(X, y) 6 ≠ P t+1(X, y)
Concept drift 也有⼀些⼈称之为 datat shift [2] or concept shift [3].[4]认为Concept drift or shift 只是 datat shift 的⼦类，它认为datat shift 包括 covariance shift，prior probablity shift and concept shift.
联合概率函数 P t(X, y) 可以解构为 P t(X, y) = P t(X) × P t(y|X)，因此概念漂移可以由三个源引起
1）P t(X) ≠ P t+1(X) while P t(y|X) = P t+1(y|X), that is, 关注 P t(X)上的漂移⽽ P t(y|X) 保持不变. P t(X) 的漂移不影响决策边界, 因此也被认为是⼀种虚漂移 virtual drift[5], Fig. 3(a).
2）P t(y|X) ≠ P t+1(y|X) while P t(X) = P t+1(X) while P t(X) remains unchanged. 这种漂移会使决策边界变化，从⽽导致预测精度下降, 也被称为实漂移 actual drift, Fig. 3(b).
3）结合了上⾯两者, Pt(X) ≠ Pt+1(X) and Pt(y|X) ≠ Pt+1(y|X).两者都发⽣了漂移, 因为这两种变化都传达了关于学习环境的重要信息 Fig. 3(c).
通常，概念漂移⽅式分为四类：突发式漂移，渐进式漂移，增量式漂移，复发式漂移
漂移检测
dogfart 漂移检测的⼀般框架
Stage 1：数据获取。由于单个数据实例不能携带⾜够的信息来推断整个分布，所以知道如何组织数据块形成有意义的模式或知识在数据流分析任务中是很重要的。
Stage 2：数据建模。抽象出数据的特征，漂移的特征对系统的影响最⼤。这个阶段是可选的，因为它主要关注维数减少，或样本⼤⼩减少，以满⾜存储和速度的要求。
Stage 3：统计值计算。是衡量不⼀致性，或者漂移量。通过统计测试和假设检验来定量研究漂移的严重性。. 不相似度度量还可以⽤于聚类评价，并确定样本集之间的不相似度。
Stage 4：使⽤特定的假设检验来评估阶段3中观察到的变化的统计显著性，或p值。即这种变化由概念漂移⽽⾮噪声或随机样本选择偏差[3]引起的可能性有多⼤。最常⽤的假设检验有：最常⽤的假设检验有：估计检验统计量的分布[5]，[6]， bootstrapping[7]，[8]，排列检验[9]。
概念漂移检测算法
总账
Error rate-bad drift detection
基于错误率来检测，具体来说对于在线检测，就是分类错误显著升⾼，或者显著降低，这时将触发漂移检测。
Drift Detection Method (DDM) [20] 是被引最多的⼀种漂移探测⽅法之⼀，这是第⼀个定义预警级别和漂移级别的概念漂移检测算法。
Stage 1 通过时间窗实现，如图6所⽰。当⼀个新的数据实例可以⽤于评估时，DDM会检测时间窗⼝内的总体在线错误率是否显著增加。当错误率变化的置信度达到预警级别时，DDM开始构建⼀个新的学习器，同时使⽤旧的学习者进⾏预测。如果变化达到漂移级别，旧的学习者将被新的学习者代替，进⾏进⼀步的预测任务。为了获得在线错误率，DDM需要⼀个分类器来进⾏预测。这个过程将训练数据转换为学习模型，这是第⼆阶段(数据建模)。阶段3的测试统计数据构成在线错误率。假设检验阶段(第四阶段)通过估计在线错误率的分布，计算预警级别和漂移阈值进⾏假设检验。
类似的还有LLDD [10], EDDM [11], HDDM [12], FW-DDM [13], DELM[14]。
LLDD修改了3,4阶段，将整个漂移检测问题分解为⼀组基于决策树节点的漂移检测问题。
EDDM利⽤两个正确分类间的距离改进了DDM的第3阶段，提⾼了漂移检测的灵敏度。
HDDM 修改阶段4，使⽤了Hoeffding不等式识别漂移临界区域的⽅法。
FW-DDM改进了DDM的第⼀阶段，使⽤模糊时间窗代替传统的时间窗来解决逐步漂移问题。
DEML没有改变DDM检测算法，⽽是采⽤了⼀种新的基学习器，它是⼀种单隐层反馈神经⽹络，称为 ELM [15]，以改进漂移确定后的⾃适应过程。
ECDD[16] 使⽤EWMA图表来跟踪错误率的变化。⽤动态均值替代静态均值，动态⽅差为
，其中λ是新数据对⽐旧数据的权重，作者建议取0.2.
当时,ECDD将会发出预警，当，这时就认为发了概念漂移。
与DDM等类似算法相⽐，STEPD[17]，⽐较最近的时间窗⼝和整个时间窗⼝来检测错误率的变化
ADWIN不需要指定时间窗⼝⼤⼩，需要指定⼀个⾜够⼤的窗⼝总⼤⼩。对所有⼦窗⼝计算漂移量。
Data Distribution-bad Drift Detection
基于数据分布差异的漂移检测，通过计算数据分布的差异度，来进⾏检测，不仅可以检查时间维度上的漂移，也可以检测数据集内部的概念差异。然⽽这些算法的资源消耗通常⽐上者要⾼。通常的做法是利⽤两个滑动窗⼝来选取数据。
最初使⽤这种想法的是[18]，如果分布有它⾃⼰的概率密度函数，则距离可以计算为。
类似的还有ITA[8]，它使⽤kdqTree来划分历史数据和新数据，然后⽤KL散度来计算差异性。ITA采⽤的假设检验⽅法是将W hist、W new合并为W all，重采样为W hist、W new进⾏bootstrapping，则确定概念漂移，其中α是控制漂移检测灵敏度的显著⽔平。
类似的算法还有SCD[19]，n CM[20]，PCA-CD [21]，EDE[22]，LSDD-CDT[21]，LSDD-INC[23]，LDD-DSDA[24]。
Multiple Hypothesis Test Drift Detection
智力小游戏 并⾏假设检验佛语祝福
最早的算法是JIT[5]，核⼼思想是拓展CUSUM test，作者给出了给出了漂移检测⽬标的4种配置⽅案，1）PCA提取后的特征，移除和⼩于某⼀阈值的情况。 2）PCA提取的特征，加上⼀些原始特征中的通⽤特征。 3）对每⼀个特征独⽴检测。4）检测所有可能组合的特征空间。
相似的LFR[25]，考察TP, TN, FP, FN的变化，⽽不是准确率的变化。
IV-Jac[26]是⼀种三层检测算法，第⼀层检测标签层⾯，第⼆层是特征层⾯，第三层决策边界层⾯。它通过提取证据权重 WoE，和信息价值 IV，来观察其变化。
串⾏假设检验
HCDTs[27]最先设计了检测层和验证层，验证层根据检测层的返回结果决定激活或者休眠，给了两个设计验证层的策略，1）通过最⼤相似度来计算测试层数据的分布， 2）调整⼀种已有的假设检验⽅案。
HLFR[28]类似的，使⽤LFR作为检测层，把验证层简单的使⽤ 0-1损失函数进⾏评估，超过阈值则为发⽣概念漂移。
漂移理解
属于作者⾃⼰的新增部分，要解决概念漂移，要从时间上何时发⽣，地点上哪些特征or标签，程度上的严重性来考量。内容⽐较冗余。
漂移调整
发⽣概念漂移后，如何调整我们的算法才是最重要的。有三种主要的调整⽅案，应对不同的形式的概念漂移。
Training new models for global drift
最简单有效的⽅法就是训练⼀个新的学习器。窗⼝策略通常会被使⽤。Paired Learners[fdfd]就是这种。
百得利集团 关于窗⼝策略，对于窗⼝的⼤⼩，⼩窗⼝可以反映最新的数据，⼤窗⼝可以为模型提供更多训练数据。ADWIN不需要固定窗⼝尺⼨，根据两个⼦窗⼝之间的变化率计算最佳⼦窗⼝⼤⼩。找到最优窗⼝割后，删除包含旧数据的窗⼝，⽤最新的窗⼝数据训练新模型。
DELM没有使⽤全部重新训练的策略，⽽是当错误率上升时，为提⾼其逼近能⼒加⼊更多节点，继续训练。
什么电视剧最好看 FP-ELM[29]是⼀种elm扩展⽅法，它通过引⼊遗忘参数来适应漂移树模型。
OS-ELM[30]是另⼀种抑制因⼦模型的在线集成，它使⽤有序聚合(OA)技术集成ELM，克服了确定最优集成⼤⼩的问题。
采⽤基于能⼒模型的漂移检测算法[9]定位案例库中的漂移实例，并将其与噪声实例区分开，采⽤冗余去除算法，逐步冗余消除(Stepwi Redundancy Removal, SRR)，以统⼀的⽅式去除冗余实例，保证减少的案例库仍能保留⾜够的信息⽤于未来的漂移检测。
Model enmble for recurring drift
对于recurring drift 复发式漂移，保留和重⽤旧的模型可以节省很⼤时间。这是使⽤集成学习解决问题的核⼼思路。
ARF[31]算法，它在随机森林树算法的基础上引⼊了概念漂移检测⽅法，如ADWIN，以决定何时⽤新树替换旧树。
DWM[32]就是这样⼀种集成⽅法，它可以通过⼀组简单的加权投票规则来适应漂移。它根据单个分类器和全局集成器的性能来管理基分类器。如果集成误分类了⼀个实例，DWM将训练⼀个新的基分类器并将其添加到集成中。如果基本分类器错误地分类了实例，DWM会减少它的权重⼀个因⼦。当基分类器的权重低于⽤户定义的阈值时，DWM将其从集合中移除。这种⽅法的缺点是，添加分类器过程可能被触发得太频繁。
日本武士刀短刀
⼀个著名的集合法，Learn++NSE[33]，通过根据基分类器对最新⼀批数据的预测错误率加权来缓解这个问题。如果最⼩分类器的错误率超过50%，将根据最新的数据训练⼀个新的分类器。
AUE2[34]的提出重点在于同时处理突发式漂移和渐变式漂移。它是⼀种基于增量基分类器的批处理加权投票集成⽅法。通过重新加权，整个系统能够对突然漂移做出快速反应。所有的分类器也⽤最新的数据增量地训练，这确保了总体的演进与渐进的漂移。
OWA[35]通过为不同的概念漂移类型使⽤加权实例和加权分类器来构建集合，实现了相同的⽬标。
Adjusting existing models for regional drift
当漂移只发⽣在局部地区时，这类⽅法中的许多⽅法是基于决策树算法的，因为树有能⼒分别检查和适应每个⼦区域。
VFDF[36] 针对⾼速数据流的在线决策树算法。它使⽤Hoeffding边界来限制节点分割所需的实例数量。它有许多优点 1）只需处理数据⼀次，不需要存储。2）树本⾝只占很⼩的空间。3）维护树的成本很低。
CVFDT[37]，保持⼀个滑动窗⼝来保存最新的数据。在窗⼝的基础上训练备选⼦树，并对其性能进⾏监控。如果备选⼦树的表现优于原来的对应⼦树，它将被⽤于未来的预测，⽽原来废弃的⼦树将被修剪。
VFDTc[38]是对VFDT进⾏改进的另⼀个尝试，它增强了⼀些功能：处理数字属性的能⼒；朴素贝叶斯分类器在树叶分类中的应⽤以及对概念漂移的检测和适应能⼒。提出了两种节点级漂移检测⽅法。第⼀种⽅法使⽤分类错误率，第⼆种⽅法直接检查分布差异。
[39], [40]进⼀步扩展了VFDTc，使⽤⾃适应叶策略，从多数投票、朴素贝叶斯和加权朴素贝叶斯这三个选项中选择最佳分类器
尽管VFDT取得了成功，但最近的研究[41]、[42]表明，它的基础Hoeffding界可能不适⽤于节点分裂计算，因为它计算的变量，即信息增益，不是独⽴的。
多少天过年评估与数据集
对于能够处理概念漂移的学习算法的评估，有三个独特的流程
1) holdout, 2) prequential, and 3) controlled permutation
2）Prequential是流数据中常⽤的⼀种评估⽅案。每个数据实例⾸先⽤来测试学习算法，然后训练学习算法。该⽅案的优点是不需要知道概念的漂移时间，最⼤限度地利⽤了现有数据。误差是根据预测和观测标签之间的损失函数的累加和计算的。错误率估计有三种:⾥程碑窗⼝、滑动窗⼝和遗忘机制。
3）Controlled permutation运⾏多个测试数据集，其中数据顺序以⼀种可控的⽅式进⾏了排列，以保持局部分布，这意味着最初在时间上彼此接近的数据实例在⼀次排列之后需要保持接近。受控制的排列减少了其先⾏评估对序列中固定顺序的数据产⽣偏差结果的风险。
对涉及概念漂移的数据集的评价指标可以从传统的精度度量中选择，如检索任务中的精度/召回率、回归中的平均绝对缩放误差、推荐系统中的均⽅根误差等。
除此以外，作者还推荐可以使⽤以下⼏点度量：
1）RAM-hours [43] ⽤于计算数据挖掘的成本。
2）Kappa statistic [44]，考虑不平衡分类时使⽤，p是分类器的准确率，P ran是随机分类器的准确率
3）Kappa-Temporal statistic[45] 考虑时序的分类使⽤，
4) Combined Kappa statistic [45] 综合上⾯两者的使⽤。
5) Prequential AUC [46]
6) 平均归⼀化⾯积(NAUC)值[47]，⽤于概念漂移的流数据分类。
对于显著性的度量，有以下三种流⾏⽅案：
1）McNemar test
2）Sign test
3）Wilcoxon’s signrank tes
合成数据集
