文摘
由于许多领域如电子商务平台的兴起,出现了大量的流数据。不完整的标签问题和概念漂移问题,这些数据构成一个巨大的挑战,现有的流数据分类方法。在这方面,一个动态流数据流数据的分类算法。不完整的标签问题,该方法引入了随机化和快速迭代策略基于决策树VFDT算法设计迭代集成算法,算法使用前面的模型分类结果作为下一个模型输入和实现新的数据分类的投票机制。同时,窗口机制用于存储数据和计算数据分布特征的窗口,然后,结合计算结果和预测的数据量来调整滑动窗口的大小。实验证明算法的优越性在分类精度。这项研究的目的是比较不同算法来评估分类模型是否适应当前的数据环境。
1。介绍
随着互联网的发展,传感器和互联网的事情,出现了大规模的流数据。流数据是不断生成的不同来源的数据。这些数据应该逐步处理使用流处理技术而无需访问所有的数据。它包括各种数据格式,如日志文件生成的web应用程序中,网上购物数据、交通监控、社交网站信息,地理和气象卫星数据。这些流数据意味着大量的信息是真实的决策指导。因此,许多学者分析数据来获取有用的信息,指导人们进行科学决策,如电子商务平台实时个性化推荐,股票市场监控、网络入侵,欺诈监测异常,大多数智能手机应用程序中,交通监控、实时运动分析等。流数据处理是有利的对于大多数场景动态数据不断生成。作为数据挖掘的一个重要分支,分类问题具有重要的现实意义在金融领域信用评级,预防电信欺诈和网络入侵检测(1]。据流数据的特点,分类技术的分析具有较高的商业价值和研究意义。
流数据实时生成的特点,快速到来,大量、重复采集困难(2]。如果传统的分类挖掘的模型和算法仍用于处理,大量的有用的信息将丢失。一些现有的数据挖掘方案和算法未能充分考虑流数据和实际应用场景的特点,如概念漂移,不完整的标签和数据流量不均匀。一些研究假设所有流动数据到达完全标记,可以直接使用这些标签1]。这个假设很难建立在许多实际应用,尤其是在电信欺诈和入侵检测领域。此外,随着时间的变化,底层数据流的概念将会改变。许多检测算法是复杂的,消耗了大量的空间和资源。在流基于滑动窗口的数据处理算法,滑动窗口的大小是固定的或只改变概念漂移。然而,不考虑流特性,所以当数据流量非常快或非常缓慢,没有获得即时处理,从而影响流数据处理的效率。因此,它具有重要的研究价值和现实意义来设计分类模型和方法,可以更有效地应用于实际的场景。
针对上述问题,本文提出了一种实时流数据动态分类算法,采用决策树为基础的分类模型,结合一个集成分类算法的想法改变单一的模式分类模型并定期更新分类模型;在概念漂移的检测,检测到概念漂移的程度通过计算前和结束部分的数据之间的差别在滑动窗口。当发生概念漂移时,滑动窗口的大小调整根据概念漂移的程度,同时,结合实时数据流量情况再调整滑动窗口,使数据处理更及时、有效。
部分2介绍了分类算法和概念漂移的相关研究和相关定义。部分3介绍了详细的算法和框架内部算法的具体实现过程。部分4分析了相关部分的实验部分。部分5总结全文和算法的缺陷和未来相关工作的前景。
2。相关工作和理论基础
2.1。相关研究
目前,流数据环境的分类算法主要是研究和设计一些基本的机器学习算法,包括支持向量模型、贝叶斯模型(一个贝叶斯模型是一种统计模型,你使用概率表示模型中的不确定性,不确定性关于输出不确定性也输入),神经网络模型(这是一个简化模型生活人类大脑有输入层、隐藏层和输出层),和决策树模型(决策树是一种决策支持工具,使用树状模型的决策及其可能的后果,包括随机事件的结果,资源成本和效用)。决策树模型是更快和更有效的比其他的批处理算法在处理流数据。
一个最具影响力的算法是决策树快速数据流分类算法VFDT [3),介绍了霍夫丁绑定(4)选择最佳分割财产。每个实例在常数时间处理。在分类过程中,数据只需要扫描一次。该算法具有更高的处理速度。然而,VFDT不执行在处理连续属性。VFDTc [5基于VFDT算法进行了优化。通过引入离散化算法,VFDT被扩展的能力来处理连续属性和提高了分类精度。组合后的决策树和其他算法的分类性能进一步提高。例如,决策树和频繁模式挖掘的结合提出了一个处理流数据频繁模式决策树算法和基于闭合频繁模式(6]。然后,建立了决策树分类。根据观察到的域和时间域的顺序数据集,基于C4.5,归纳提出了学习时间数据分类(7]。
随着机器学习得到太多的关注,一直欢迎作为集成学习算法从机器学习技术来提高分类精度。集成分类集成多个弱分类器或多个分类算法产生一个有效的组合分类器大大改善了分类精度的经典算法在静态数据。我们是一个集成的分类框架8]。当数据块到达一个特定的时间t,选择一个分类学习算法学习独立数据块。N分类模型。每个分类模型给出的重量根据不同方法和获得集成分类模型。大海算法(Schoof-Elkies-Atkin算法)使用集成的概念分类(8]。它将训练数据划分为有序数据块的大小根据数据到达时间和构造一个基分类器每一块数据。分类器达到最大容量时,更新的基本分类器和启发式的替代机制。王等人设计了一个通用框架,数据流分类命名加权装袋(9]。它构建一个基本分类器基于C4.5算法,用于数据挖掘决策树分类器,可以用来生成一个决定,基于一定的样本数据,K-based分类器建立一个集成分类器的加权投票。在实施过程中,这些方法的内存消耗太大,这减少了处理速度。
概念漂移问题使得流数据分类面临很多挑战。因此,许多研究人员研究了概念漂移问题,创造了许多解决方案。
算法(10,11)检测计算信息熵概念漂移的新老数据块。观察熵值之间的差异,12,13]法官概念漂移通过构建集群。例如,集群k - means算法获得的数据块。计算聚类中心之间的距离,确定是否发生概念漂移,类的标签传播方法充分利用标签信息,从集群内部结构信息来推断每个集群的类标签。
除了上述算法,滑动窗口的一个重要处理概念漂移问题的机制。基于VFDT CVFDT [14]算法增加了滑动窗口更新生成的决策树根据样本数据流入窗口。随着越来越多的算法的发展,研究人员使用双窗口和多窗口机制。(自适应窗口)ADWIN方法任意窗口W分为两个好子窗口(15]。当两个好子窗口之间的平均差超过一定的限制,认为windows的期望值不一致。减少发生概念漂移和窗口。基于ADWIN算法,帽子16)学习的模型变化的数据流,避免滑动窗口大小选择的问题。(Double-Window-Based分类)DWCDS [17)算法采用一个两层的窗口机制。双层窗口是一个滑动窗口由多个基本窗口。概念漂移是判断通过定期检测的变化分布的流数据窗口。但是周期检测算法的消耗大量的时间。Yim et al。18提出了一种可变滑动窗口。由风暴并行窗口算法初始化窗口方案。根据泊松分布和不平等,分配的信息隐含在检测到的窗口。如果期望值小于阈值,这意味着可能存在概念漂移。窗口是适当降低。否则,窗口适当放大。该算法提高了吞吐量和处理速度,指的并行处理机制。然而,该算法没有考虑不同类型的概念漂移。同时,当窗口太小,减少可能导致数据样本不足,更大的噪声影响,和更多的错误。
针对上述概念漂移检测算法的缺点,提出了一种基于数据属性的决策树分类算法的特性。根据数据的属性特征,它所观察到的特性区别前和结束检测概念漂移的数据。它使用窗口机制,扩大或缩小窗口大小根据概念漂移的程度。窗口大小调整两次根据数据量的增加和减少,这可以有效地处理数据在不同的流速和及时。分类器是定期更新,以满足变化的数据的概念。根据不同类型的概念漂移,采取相应措施来有效地处理概念漂移。
2.2。相关的概念
数据流 是一个序列的数据生成。每一块数据 ,有一个相应的属性设置和相应的潜在的类标签。通过培训和学习数据已知的类标签,创建一个有效的分类模型,和真正的类标签。
2.2.1。它
如果样品r有一个值的范围R后,获得n样品,样本的平均值 ;然后真正的平均值r至少是1−的概率δ,在那里
的最小值n的公式是当前节点所需的最低实数。
2.2.2。程度的差异
假设一个矩阵米的 维度;在这里 。两个子矩阵 显示为 在哪里 是统计向量的和 是统计向量的 。然后定义的程度不同δ的矩阵作为
不同的程度δ是用来衡量是否数据分布变化。如果δ大于预定阈值,可以认为矩阵的元素米经历了数据分布的变化。
3所示。基于决策树的分类算法的流数据
流数据分类问题的难度在于如何解决概念漂移的问题和不完整的标签。如果没有这些问题,传统的分类算法可以有效流数据分类。在某种程度上,造成的困难不完整的标签问题也由概念漂移引起的。概念漂移不发生时,数据分布是非常稳定的,在这种情况下,即使训练数据量的比值测试数据量很低,传统的分类算法可以表现良好。
决策树是一个基本的分类方法。因为决策树有一个相对少量的计算,很容易被转化为分类规则与精度高、容易理解,适合高维数据。因此,决策树通常被用来做流媒体数据和分类模型。
本文算法使用决策树分类模型对滑动窗口中的数据进行分类。通过概念漂移的程度和数据量的预测,动态滑动窗口大小调整。分类精度降低时,会更新分类模型。该算法框架如图1。主要包括三个模块,分类器的构建模块,滑动窗口调整模块,和分类器定期检测模块。整个过程描述如下:(1)分类器的构建模块,集成分类器由多个决策树建立了通过培训数据和类标签。(2)使用当前分类器分类传入的流数据,数据分类是形成一个初始窗口根据滑动窗口的大小。当前分类模型用于分类窗口中的数据获取分类结果集,更新和旧的分类模型用分类结果集。定期使用数据的类标签监视器的分类性能,并观察是否准确率高于预设阈值。如果分类错误的比例太大,当前分类器需要更新。(3)在窗口调整模块,利用历史数据来预测流数据的数据量。然后执行分类结果集的概念漂移检测获得的第二步,调整窗口的大小根据预测的结果和检测。最后,更新当前窗口大小。
3.1。动态数据流分类算法基于VFDT模型
摘要DVFDTc集成分类算法,基于决策树,设计。该算法主要是完成建设的分类器。对测试数据进行分类的过程中,随机化,投票,并采用其他机制来避免错误引起的应变,然后流数据的准确分类是实现。当机密数据足够的滑动窗口大小,构造一个新的分类器。然后,基本更新分类模型。
该算法保持两个数据窗口赢得1和赢得c。一开始,赢得1商店原来的训练数据赢得c将数据分类存储在最近时期。在随后的运行过程中,他们分别存储最近的相邻期间的机密数据。后把训练数据赢得1列车数据,集成分类算法赢得1获得初始的分类模型米1。然后,重新分类的数据赢得1通过米1并将the结果集进赢得c。当前分类模型重建米c与赢得c。所以米1和米c形成了最初的集成分类模型。
新传入的数据d我、数据d我分类是米1和米c,分别。如果这两个分类结果一致,标签d我结果临时数据容器赢得amp。如果他们不一致,数据的赢得1和赢得c根据一定的比例混合,取样。K混合数据集 是用于构造K新的分类模型 。最后,K分类模型是用于分类数据d我。最终结果由投票产生,而最支持类标签是最终结果。标记的数据添加到临时数据的容器赢得amp。当数据容器的大小赢得tmp到达滑动窗口大小、更新赢得1通过赢得c和更新赢得c通过赢得amp。同时,更新相应的分类模型。
算法的核心思想1如下:
|
概念漂移对分类性能有很大的影响。本文还设计了评价当前分类模型的操作。它使用分类准确率作为评价指标来确定分类模型适应当前数据环境。摘要三次迭代过程是用作循环,和标记数据作为验证集。通过分类验证组评估的准确性,如果精度小于预设值,当前分类模型将被删除和正确分类数据重建根据初始基分类器施工过程,以便分类模型可以适应不断变化的数据环境。
4所示。概念漂移检测算法
由于数据分布的变化,当前分类器不能适应的变化数据的概念。这将导致不准确的下降。本文提出一个概念漂移检测算法基于数据属性特征。每个属性的特征数据,并观察数据分布的差异之前和之后,然后决定是否发生概念漂移。
4.1。基于属性的概念漂移特性
本文的属性特征数据作为研究对象,和当前数据的分布状态是由属性判断的特征。在第一个 在开始和最后一次 最后两个subdatasets滑动窗口。假设他们是赢得0和赢得1。每个数据集都看为一组高维向量。所示(5)和(6),计算属性的不同值的平方意味着在每个数据集的分布状态数据。
对于一个 维矩阵米,元素 ,和特征值统计的矩阵米被定义为
然后的区别赢得0和赢得1根据确定
如果他们的差异大于预设阈值 ,然后数据的分布状态是变化。当发生概念漂移。
4.2。阈值的选择
阈值的大小起着关键作用的判断概念漂移。如果阈值太小,经常可能发生概念漂移,而分类模型和滑动窗口更新频繁。这将导致减少分类的效率和准确性。如果该值太大,那么可能会有很少或根本没有概念漂移。它还降低了分类的准确性。因此阈值大小的选择是非常重要的。
为了避免上面的情况,以确保出现的次数的概念漂移是一个合理的范围内,提出了一种动态调整阈值的方法。确定是否调整阈值的大小根据概念漂移的频率。
阈值设置为不同的脑袋和尾巴初始滑动窗口的数据。在分类过程中,观察发生概念漂移的速度。如果速度超过 ,概念漂移是过于频繁,然后阈值将增加 。如果发生概念漂移小于 或者几乎没有发生时,阈值将会减少 。重复以上过程,直到这个概念漂移比率是一个合理的范围内。
4.3。理性的分析概念漂移检测方法
概念漂移的检测过程主要是根据数据分布特征的变化判断。数据分布特征的变化通常有两种类型的兴衰的特征值的变化趋势;但从的角度的大小变化,突变和渐变。
数据分布的突然变化的情况,分析了头和尾巴好子窗口赢得0和赢得1当前的滑动窗口。如图所示的结果2。
从图可以看出2的突变数据分布可以有效地检测到计算特征值和的两个窗口。
数据分布的情况下逐渐改变,如果等级趋势是单调的,它可以根据捕获(6)。相反,如果不是单调的,不稳定的趋势,那么造成的错误数据的梯度分布样本的随机性可以纠正的集成分类算法。假设数据分布不规则变化如图3。
如果数据分布差异,脑袋和尾巴没有达到阈值,当前窗口的数据分布变化可以忽略。观察是否测试数据的类标签d两种分类模型是相同的吗米0和米c。如果他们是相同的,数据特征变化可以忽略。否则,这两个好子窗口的数据证明有很大的特性变化。然后,随机抽样比例两个数据窗口中执行。通过使用水库采样方法,数据提取滑动窗口的概率是相等的。从两个数据窗口中提取的数据组合成一个新的数据窗口。新数据窗口的数据训练来获得k分类模型 。投票机制是用来确定的类标签测试数据d。通过合理设置的抽样比率两个数据窗口,混合类型的分类精度可以有效地改善。
通过上述分析,提出概念漂移检测算法能有效处理的概念漂移突变和渐变。
5。滑动窗口动态调整算法
滑动窗口的分类算法,滑动窗口的大小有很大的影响数据处理的速度和准确性。因此,滑动窗口的大小应该是不断变化的数据变化,因此,当前的数据可以实时准确地处理。两个主要因素是影响滑动窗口的大小。首先,数据流的流动速度。滑动窗口的大小应根据变化调整流速度;其次,概念漂移。当发生概念漂移时,窗口应该适当的减少,和窗口中的数据分布应保证尽可能保持一致。
因此,本文检测了概念漂移和预测数据和扩展或收缩的速度数据窗口的大小根据检测的结果和预测。
5.1。数据流量预测
根据数据流的流动特性,数据更改的数量可能是普通的一天。例如,一个web页面可能会在某一段时间内大量访问时可能很少访问另一个时期。当大量数据聚集在某一时刻,这可能导致数据丢失没有处理如果滑动窗口仍然保持原来的大小。相反,如果流动速度慢,窗口将花很多时间等待数据的聚合。它可能会造成资源和时间的浪费。本文预测可能的数据流速度下一个窗口到来之前调整滑动窗口大小。
本文实现了序列化和研究法律一段时间的增加和减少数据量每天从历史数据。挖掘的数据量的预设时间内。如果大于平均的数据量的数据量在预定时期,那么当前数据量被认为是在一个上升或高潮阶段,此时和滑动窗口将会扩大;否则,数据被认为是在下跌或低潮阶段,和窗口大小会减少。
5.2。滑动窗口大小调整
在窗口调整算法2根据概念漂移的数据量,处理下一个滑动窗口大小如下:
|
当前窗口的概念漂移检测数据和确定数据的窗口有一个概念漂移。如果发生概念漂移情况,获得一个窗口还原度值l根据当前窗口,减少其大小的窗口大小宽度。
根据数据量的增加或减少的预设期间,宽度调整再次获得下一个滑动窗口的大小。细节如下:(1)如果预测数据的数量大于阈值,将增加预测数据窗口大小 基于概念漂移减少窗口不改变数据窗口的趋势变得更小。(2)如果小于预设的数据量,窗外是根据预测数据的数量减少了 基于概念漂移减少窗口(不少于800)的最小窗口长度。
如果没有发生概念漂移,窗外是线性扩展:(1)如果预测数据的数量大于预设的数据量,窗外是根据预测数据的数量增加了 基于窗口的概念漂移的扩张。(2)如果它是小于预设的数据量, 预测的数据量减少基于概念漂移减少窗口不改变数据窗口成为大的趋势。
根据上述情况在分类过程中,执行相应的处理。这个过程重复一遍又一遍地在分类器迭代和更新。
6。实验和分析
实验是基于Windows 10操作系统,实现Eclipse, Weka开发环境。在实验中使用的数据是合成数据上形成Weka开发工具。合成数据集有50000块的数据,每个有20属性维度和2类标签。实验分析,介绍了算法的精度和效率。
6.1。DVFDTC算法分类精度分析
流数据分类算法的验证方法与传统的静态的验证方法不同分类算法。在这个实验中,十倍交叉验证算法更有效地改进验证流数据分类算法。
首先,数据集是解密,只有类标签的第一个数据集是用于培训的1/10。窗口的实例在每次迭代过程中被认为是数据块 。在这个实验中,VFDT算法和DVFDTc算法分类精度比较算法,两种算法的分类精度表所示1。
从表可以看出1DVFDTc的分类精度高于VFDT算法。然而,DVFDTc的准确性低于VFDT起初,因为初始的数据量不足;在这个概念漂移检测过程中,阈值的选择是没有经验的,精度低。然而,随着分类器继续迭代更新,准确率一般保持上升。
DVFDTc获得实验结果的过程中遍历10个数据块,平均精度提高了2.95%,准确率是最多增长了7.83%。
6.2。DVFDTC算法执行效率分析
DVFDTc算法的性能主要从的角度分析了该算法的执行时间。实验比较了DVFDTc VFDT。结果如图所示4。
从上面的图中,DVFDTc算法的执行时间和VFDT算法都比VFDT算法的执行时间长,最长和DVFDTc算法执行时间。这一现象的原因是DVFDTc算法和VFDT算法迭代和更新分类器在分类的过程中。本地大量的中间结果写在程序的执行期间,大大增加了磁盘IO的读和写。如果算法的中间结果存储在内存中,算法的运行时间可以大大减少。执行时间的另一个原因DVFDTc算法,该算法构造多个分类器的分类器和也有定时检测。事实上,在情况下,分类精度要求不是很高,投票分类器的数量可以减少有效降低算法的运行时间。
6.3。SWDA性能分析
SWDA算法的性能从两个角度进行了分析。一个是分析算法是否有助于提高DVFDTc算法的准确性;另一种是分析的影响SWDA算法DVFDTc算法的执行时间。实验进行比较与SWDA DVFDT算法算法和DVFDT算法没有SWDA算法。计算他们的分类精度和执行时间。
与SWDA DVFDTc算法的精度统计如表所示2。
它可以看到从表取消学位2SWDA DVFDTc算法的算法有一定的改进错误,证明了概念漂移检测的结果和数据量的预测是合理的滑动窗口大小调整策略。然而,DVFDTc算法的效率提高的原因是小SWDA算法和DVFDTc算法重叠影响流数据分类的准确性。
执行时间统计DVFDTc与集成的滑动窗口动态调整算法如表所示3。
在表格的最后一列3DVFDTc算法的执行时间和DVFDTc SWDA算法类似于SWDA算法的执行时间。算法的执行时间SWDA远低于DVFDTc算法的执行时间。
6.4。实验总结
通过上述实验的验证,可以看出,基于决策树的分类算法的流数据具有良好的性能。的平均精度是3.66%高于VFDT算法。然而,由于分类器迭代,定时检测,和概念漂移检测过程中,执行时间比VFDT低。
数据流分类算法的精度比基于决策树和VFDT算法如图5。
DVFDTc和VFDT算法的执行时间比较图所示6。
7所示。结论
针对不完全标记流数据分类的问题,本文设计并优化了流数据基于决策树的分类算法。该算法在一定程度上解决了概念漂移的问题和精度有很大的提高。
的迭代更新分类器增加IO的读和写,该算法仍然是缺乏执行效率。在下一阶段,我们将研究如何实现决策树流数据分类算法在分布式平台上以提高算法的执行效率。
数据可用性
使用的数据来支持本研究的结果包括在本文中。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是支持部分由中国国家自然科学基金批准号。61402090和61402090下。