武靖娜, 杨 姝, 王剑辉

(沈阳师范大学 教育技术学院, 沈阳 110034)



一种分布式大数据挖掘的快速在线学习算法

武靖娜, 杨 姝, 王剑辉

(沈阳师范大学 教育技术学院, 沈阳 110034)

在大数据分析处理中,存在诸多问题,如数据类型多,处理效率低,从中获得有用的信息和知识以便指导后续的决策,这是机器学习的最终目标。有效学习样本逐渐增加,据此如何高效渐进地学习分类器是一个非常有价值的问题。大数据分析要求大量数据流的分布式挖掘要实时执行,设计这样独特的分布式挖掘系统:在线适应传入数据的特征;在线处理大量的异构数据;在分布式学习者之间的有限数据访问和通信能力。提出了一个基本的数据挖掘框架,并基于此研究了一种高效的在线学习算法。框架包括一个整体学习者和只能访问不同输入数据部分的多个局部学习者。通过利用在局部学习者学习的相关性模型,提出的学习算法可以优化预测精度而比现有最先进的学习解决方案需要更少的信息交换和计算复杂度。

大数据分析; 分布式挖掘; 实时; 在线学习算法

0 引 言

大数据分析包括处理在不同分布式数据源中的异构数据生成互补的数据集[1-2]。因此,数据集不仅表现为他们极大的体积而且还表现为异构和数据的分布式采集。分布式数据挖掘技术[3]已经被提出来处理分布式数据在遗传算法方面也有所应用[4]。不同于传统的集中式数据挖掘系统,分布式数据挖掘系统通常使用集成学习技术包括在层次结构的最低层次上操作的全球数据集的子集的多个局部学习者[5-7]的层次结构,并且一个或多个集合的学习者组合所有局部学习者的输出。通过允许更大和更多样化的数据集进行分析来扩大知识获取的前沿,这样的分布式数据挖掘系统伴随着重要的设计挑战是这项工作的重点。

大数据分析包括5个基本方面:

1) 可视化分析:不管是对数据分析专家还是普通用户,数据可视化是数据分析工具最基本的要求。可视化可以直观的展示数据,让数据自己说话,让观众听到结果。

2) 数据挖掘算法:可视化是给人看的,数据挖掘就是给机器看的。集群、分割、孤立点分析还有其他的算法让我们深入数据内部,挖掘价值。这些算法不仅要处理大数据的量,也要处理大数据的速度。

3) 预测性分析能力:数据挖掘可以让分析员更好的理解数据,而预测性分析可以让分析员根据可视化分析和数据挖掘的结果做出一些预测性的判断。

4) 语义引擎:我们知道由于非结构化数据的多样性带来了数据分析的新的挑战,我们需要一系列的工具去解析,提取,分析数据。语义引擎需要被设计成能够从"文档"中智能提取信息。

5) 数据质量和数据管理:数据质量和数据管理是一些管理方面的最佳实践。通过标准化的流程和工具对数据进行处理可以保证一个预先定义好的高质量的分析结果。

在分布式系统中,每个局部学生只有有限的访问整个数据集的权限。有2种类型的数据分区:在基于分布式数据挖掘的实例中,每个局部学习者有访问整个实例的一个子集的权限,而在基于特征的分布式数据挖掘,每个局部学习者有访问所有实例的特征空间的一个子集权限。在本文研究中,特别注重情景与功能分布式数据。由于大的数据量和个体学习者的有限通信能力,在此系统中是非常昂贵的,如果可行,将是在集中挖掘中花费十分昂贵。适合局部学习者的数据增长的非常快,数据的统计特性也可能随时间动态改变。

为了处理这些挑战,提出了分布式网络学习机的总体框架:1)在线学习。不同于多数的分布式数据挖掘学习算法,这个新的学习机是可以处于脱机状态。学习算法训练模型在不同的学习者上以在线的方式,只需要一个经过训练的数据。2)学习者之间的相互协作。此设计的主要目的在于处理这几个问题:如何搭配学习者最优选择局部学习者的学习模型,局部学习者如何优化更新他们的合作学习模式。3)交叉学习者相关开发。通过评估他们学习模型之间的交叉把局部学习者分到有相关的组中。在同一组中的学习者有着很高的关联性能够相互协调的训练;不同组中的学习者将会单独分开训练。因此,可以控制计算复杂性和信息交换通过调整交叉相关性阈值在局部学习者中。

1 系统框架

目标是在学习者的权向量的正则化约束[10]之下,设计算法能够确定学习模型且预测误差在给定的情况下均方最小化。在每个周期n相应的优化问题表示如下:

(1)

算法1 整体权重更新:

(2)

(3)

为了解决这个问题,提出了在线算法[11]来更新整体学习者的权重向量w和每个局部学习者的学习模型bk。接下来将要讨论详细的改进算法。

(4)

(5)

最小的整体训练剩余为

(6)

(7)

每一个局部学习者在每一个周期中基本的学习过程可以简要的总结为如下。 整体学习者更新完w之后, 发送训练消息到局部学习者。 每个局部学习者使用这个消息来更新它自己的权重向量bk。 直观来说以合作方式这是一个比较好的训练所有局部学习者。 当每一个局部学习者更新它的学习模型时候, 需要把所有其他局部学习者的训练误差考虑在内, 为了在最后预测输出时最小化误差。 然而, 这种方法可能引起不必要的信息交换和可能的过度学习问题, 尤其当一些局部的学习者是关联松散, 需要训练有素的相互独立性格。对于分布式数据挖掘这些属性是理想的, 从学习者不仅具有好的预测精度还要能够很快适应时变数据动态与稳定的信息交换的能力中获得。 这促使下一步的训练算法的生成。

通过检查方差矩阵CTC,提出了如下的算法2和在局部学习者之间以更少的信息交换和更快的收敛速度相关更新预测精度。

算法2 相关权重更新

(8)

确定相关局部学习者和局部学习者的集合Covk。

(9)

(10)

(11)

2 实验分析

在这一部分,提供了初步实验结果来表明分布式算法的效率关于KDD数据集。这个数据集包含了7周的网络流量4g的压缩二进制TCP转储数据,这是被加工成大约500万连接记录,其中随机选择5万条记录作为训练数据集。每个连接记录标记作为一个“正常”的连接或攻击。

通过分布式算法分类每个连接标签y∈{1,0}来建造预测模型,0表明正常连接,1代表攻击。在这50 000条记录中,35.3%受到攻击。每个记录包含40个属性。每一个局部学习者包含所有或者部分基分类器如表1所示。

表1 基分类器

使用2个指标----精度和召回来衡量分布式学习系统的性能。在第一个实验中,利用10个局部学习者检测该算法的性能。选择10 000个训练数据样本和10 000个测试数据样本。为了做比较,引入三元学习算法基准,所有的都使用一种离线的方式训练数据样本:Ada-boost算法[13-14],L-2Boosting算法[15],Meta-L[16]算法。L-2Boosting算法以各自的局部学习者的输出作为它的输入,使用一个L2线性回归来改正模型。然而,从整体学习者到局部学习者没有反馈。因此,在训练过程中每个局部学习者的模型是固定的。在Meta-L算法中,整体学习者简单结合了局部学习者的输出以一种附加的形式,不能自适应地调整权重分配到不同局部学习者中。

结果如表2所示。很明显算法2和Ada-boost算法有同样高的精确度。因此,它是非常重要的更新模型对于整体学习者和局部学习者朝着一个方向合作,能增加总体预测精度。在第一个实验中,收敛速度是无法评估的。第2个实验中,检查算法2的运行时间行为,设置采用同第一个实验中局部学习者一样的数据。图1展示出了结果,可以看出,使用正确的局部学习者之间的关联性,算法收敛速度是加快的。

图1 预测精度的进化 表2 不同算法的效率

算法精确度/%撤销率/%算法285.382.1Ada-boost算法88.184.3L-2Boosting算法72.269.5Meta-L算法73.171.8

3 结 论

提出了一个对于在线学习算法大规模分布式数据挖掘应用程序的通用框架设计,专注于分布式功能分布式数据线性回归问题通过不同局部的学习者。对于整体学习者和局部学习者的最佳回归量是经过严格推断得出来的,然后设计了2种在线算法能收敛到最优回归量:合作更新算法和相关的更新算法。实验表明,相关更新算法明显优于合作方面的更新算法在所需的计算复杂性和通信成本方面,预测精度有轻微的差别。结果表明,巧妙利用局部学习者之间的关联信息, 基于应用程序的需求和最终用户提出了在线学习算法可以灵活地平衡计算复杂度,沟通成本和预测准确性。

[1]程学旗,靳小龙,王元卓,等. 大数据系统和分析技术综述[J]. 软件学报, 2014,25(9):1889-1908.

[2]申彦. 大规模数据集高效数据挖掘算法研究[D]. 扬州:江苏大学, 2013.

[3]胡文瑜,孙志挥,张柏礼. 分布式数据挖掘中的最优K相异性取样技术[J]. 东南大学学报(自然科学版), 2008,38(3):385-389.

[4]刘天华,殷守林. 一种改进的遗传卡尔曼算法在室内定位中的研究[J]. 沈阳师范大学学报(自然科学版), 2015,33(2):265-269.

[5]张凌志,薛晶心,张媛. 微信模式下个体知识学习的特征和交流模式研究[J]. 情报理论与实践, 2015,38(7):67-71.

[6]ANHAI D, PEDRO D, ALON H. Learning to match the schemas of data sources:a multistrategy approach[J]. Machine Learning, 2003,50(3):279-301.

[7]覃琼霞,江涛,陆文聪. 计量模型中的加总偏误与内生性:一种数值模拟方法[J]. 数量经济技术经济研究, 2013,30(12):140-157.

[8]石斌,刘思峰,党耀国,等. 无偏灰色预测模型递推解法及其优化[J]. 系统工程理论与实践, 2011,31(8):1532-1538.

[9]唐述,龚卫国,仲建华. 稀疏平滑特性的多正则化约束图像盲复原方法[J]. 软件学报, 2013,24(5):1143-1154.

[10]于彦伟,王沁,邝俊,等. 一种基于密度的空间数据流在线聚类算法[J]. 自动化学报, 2012,38(6):1051-1059.

[11]陈晓曦,王延杰,刘恋. 小波阈值去噪法的深入研究[J]. 激光与红外, 2012,42(1):105-110.

[12]龙建武,申铉京,陈海鹏. 自适应最小误差阈值分割算法[J]. 自动化学报, 2012,38(7):1134-1144.

[13]曹莹,苗启广,刘家辰,等. AdaBoost算法研究进展与展望[J]. 自动化学报, 2013,39(6):745-758.

[14]李闯,丁晓青,吴佑寿. 一种改进的AdaBoost算法----AD AdaBoost[J]. 计算机学报, 2007,30(1):103-109.

[15]宋捷,吴喜之. 一种新的Boosting回归树方法[J]. 统计与信息论坛, 2010,25(5):9-13.

[16]王凌,郑大钟. Meta-heuristic算法研究进展[J]. 控制与决策, 2000,15(3):257-262.

A new fast online learning algorithm based on distributed mining of big data

WUJingna,YANGShu,WANGJianhui

(College of Education Technology, Shenyang Normal University, Shenyang 110034, China)

In big data analysis and processing, there are many problems, such as data types, low processing efficiency. Getting useful information and knowledge to guide the subsequent decisions is the ultimate goal of machine learning. Effective learning samples increase gradually, so how effectively to learn classifier is a very valuable problem. Big data analysis requires a large amount of data flow to perform real-time distributed mining. It designs unique distributed mining system: online adapting to the characteristics of the incoming data; online processing a large amount of heterogeneous data; the limited data ability to access between distributed learners and communication. It proposes a basic framework of data mining, and based on this it researches a kind of efficient online learning algorithm. Framework contains the whole different learners and local learners which can only have access to the input data. By using the local correlation model, the learning algorithm can optimize the prediction precision than the existing advanced learning solutions, which requires less exchange of information and computational complexity.

big data analysis; distributed mininrg; real-time; online learning algorithm

2015-08-26。

国家自然科学基金资助项目(60970112)。

武靖娜(1986-),女,辽宁朝阳人,沈阳师范大学硕士研究生; 通信作者:杨 姝(1963-),女,辽宁沈阳人,沈阳师范大学教授,博士。

1673-5862(2016)01-0100-05

TP393.08

A

10.3969/ j.issn.1673-5862.2016.01.023