一种概念漂移问题的解决算法
今天研究了一下概念漂移问题并了解了一种解决算法，记录如下。
内容来自论文《 Learning with Drift Detection 》。
该论文展示了一种检测样本概率分布变化的方法。其背后的思想是控制在线学习模型的错误率。
当数据到达的时候，对数据进行学习。根据统计理论，当被分类数据的概率分布是确定的时候，学习错误率将逐渐减小；当概率分布是变化的时候，学习错误率将上升。该算法根据在线学习的错误率，定义了预警值和漂移值两个概念。如果在一个数据流环境中，学习的错误率上升到预警值Kw和漂移值Kd，那么一个新的上下文context便生成了。这是样本概率变化的一个信号。该算法仅从预警值开始学习一个新的模型。算法验证采用八个人工数据集和一个真实数据集；使用感知机，神经网络，决策树三种学习算法进行学习。实验表明，该算法拥有良好的性能，且性能独立于分类算法。
context： 通过确定概率分布生成的一个数据集合。
数据流可以看做是一个个context组成的。在context之间的概念变化可能是平缓的，也可能是急剧的。该算法通过监测这种变化，进而确定信息是否过时（无关信息），并重新学习当前context的相关信息。
在机器学习领域中，概念漂移问题一般通过时间窗口和加权样本（根据样本的年龄和实用价值进行赋权）来处理。应对概念漂移的方法可以分为两类：
- 定期调整学习者的方法，而不考虑变化是否真的发生;
- 首先检测概念变化的变化，接下来，学习器适应这些变化。
加权样本基于一种简单的观点，即样本的重要性随时间而逐渐降低。
对于一个当前正在被使用的时间窗口，学习器只能根据窗口内的数据进行学习。如何确定时间窗口的大小是一个关键问题。小的窗口可以很快地适应样本的概念变化，但是在更多概率分布稳定的情况下会影响学习器的性能。大的窗口可以在概率分布稳定的情况下获得良好的学习性能，但是无法及时地反应概念变化。
所以通常地，一般通过监测样本的某些数据指标来确定是否发生了概念漂移，通过概念漂移的程度确定时间窗口的大小。按照惯例，如果概念漂移发生了则时间窗口减小，反之增大。一个相关的例子就是FLORA算法。FLORA2包含了一个基于规则的分类器的窗口调整的启发式思想。为了监测概念漂移，当前学习器的准确度和覆盖度被实时监测，并且窗口大小进行相应地调整。此外，还有通过准确率，召回率，时间精度等指标进行监测。启发式思想有一定的局限性：1. 反馈信息少；2. 相当多的参数需要被调整。另有人使用支持向量机进行窗口大小的研究。
漂移算法思想
对于 错误 是一个服从伯努利实验的随机变量的样本。二项分布给出了随机变量的概率的一般形式，随机变量表示含有n个样例的样本中的错误数量。
1 | 定义pi为观测到的错误率； |
对于足够多的样本，二项分布近似于具有相同均值和方差的正态分布。我们可以通过评估假设中的方法估计一个样本集合的真实错误率（基于某离散值假设h在样本S上观察到的样本错误率，估计它的真实错误率，内容较多此处不进行详述）。
