e-works数字化企业网  »  文章频道  »  基础信息化  »  大数据

大数据关键技术及应用分析(三)

2017/1/13    来源:e-works    作者:于艳华  宋美娜      
关键字:大数据技术  大数据分析  
数据是与自然资源一样重要的战略资源,大数据技术就是从数量巨大、结构复杂、类型众多的数据中,快速获得有价值信息的能力,它已成为学术界、企业界甚至各国政府关注的热点。
    数据是与自然资源一样重要的战略资源,大数据技术就是从数量巨大、结构复杂、类型众多的数据中,快速获得有价值信息的能力,它已成为学术界、企业界甚至各国政府关注的热点。本讲座将分3期对大数据进行讨论:第1期介绍了大数据的提出、含义、特点,大数据和云计算的关系以及大数据典型应用;第2期介绍大数据获取、存贮、搜索、分享、分析、可视化等方面的关键技术,并对当前热点技术一可视化进行重点分析;第3期探讨数据流挖掘等实时数据分析技术,介绍大数据中非结构化数据处理和挖掘技术,并给出大数据发展面临的挑战与应用前景。
 
    7、数据挖掘和数据流挖掘
 
    7.1大数据挖掘技术的简介和分类
 
    大数据技术广义上包括大数据相关的获取、存储、处理、挖掘等技术,但就美国政府2012年提出的“大数据研究与发展计划”而言,它主要指的是面向大数据的数据挖掘、机器学习技术。此期重点介绍大数据中的数据挖掘技术,重点是数据流挖掘技术。
 
    数据挖掘技术是一个涉及数据库、机器学习、统计学、神经网络、高J胜能计算和数据可视化的多学科领域,是计算机模仿人类学习机理和方法,利用数据自动获取知识的一种技术。数据挖掘出现于20世纪80年代末,在过去的20年中得到了广泛的研究和快速的发展,表现在出现了大量的算法,并可以处理各种类型数据。然而随着大数据时代的来临,数据挖掘技术迎来了空前广泛的应用机会,也面临新的挑战。大数据是伴随智能终端的普及和互联网上微博、社交网络等业务的广泛应用而出现的,因此面向大数据的数据挖掘的应用首推Google、Amazon、Yahoo、阿里巴巴等互联网公司,比如2009年甲型H1N1流感爆发时,Google利用海量的用户搜索词及其组合,比美国国家疾控中心更及时更准确地报告了疫情;Amazon公司首先提出井应用协同过滤技术进行书籍推荐,其应用效果超过了之前被誉为“公司皇冠之上宝石“的书评团队,开启了电子商务应用中商品推荐的先河。基于互联网上海量语言材料应用机器学习技术的Google语言翻译系统,则是目前为止最为成功的计算机自动翻译系统。面向大数据的数据挖掘技术的一个挑战是:大数据时代我们能得到现象相关的所有数据,即统计学上所说的总体,而不再是传统的统计学和数据挖掘中一个容量有限的样本或容量有限的训练集。另外一个挑战是所得到的数据不是绝对精确的,只要在保证速度的前提下近似地反映宏观和整体情况,这一挑战要求数据挖掘要能处理非结构化数据和含噪音的数据,而挖掘结果的正确性则只要保证在期望的区间内。目前来看,应对这两个挑战的主要技术之一就是数据流的挖掘。
 
    数据挖掘技术主要分为如下几个分支:分类、聚类、关联规则挖掘、序列模式挖掘、异常点挖掘、时间序列分析预测等。在大数据的相关挖掘应用中,虽然处理的数据形式更丰富,但就学习方法来看井没有根本差别,因为全部是基于数字化后信息的学习。
 
    7.2概念漂移
 
    “概念漂移”是Schlimme:等人于1986年首次提出的。大部分的数据挖掘技术都有一个假设前提:样本是随机获取的,并且服从同一稳定的分布。然而在大数据场景下,数据源源不断地到来,样本具有不稳定和不确定性。例如,顾客的购买兴趣随着时间很有可能发生变化;用户上网的浏览习J惯也会随着时间的推移而发生明显地改变。因此大数据场景中不可避免的,一定要考虑概念漂移间题。如图8,样本的统计特性在某一时刻开始发生变化,我们认为此时发生了“概念漂移”。
 
    从样本是否服从相同分布的维度,可以将数据流划分为2类:稳定数据流,样本服从同一分布;动态数据流,随着时间推移,样本服从不同分布,只有动态数据流中才存在“概念漂移”现象。概念漂移又可以分为:突变式和渐变式,对这两种漂移的处理方式和难度通常井不相同,在设计漂移算法时,应该分别进行考虑。如图9所示,在tn,时刻之前,数据样本服从同一分布A,而在tnt1之间,数据流发生概念漂移,在t1,时刻之后,数据重新趋于稳定,少十服从同一分布B。
 
    当概念漂移发生之后,最直接的结果就是从之前样本中学习获得的概念模型,已经不再适用,必须尽快更新。现有概念漂移检测的方法,可以分为3类:模型性能监测法、概念聚类法、样本分布监测法。
 
    (1)模型性能监测法。以分类挖掘为例,首先需要对分类器的性能进行跟踪监测,当使用新采集的训练集,对现有分类器进行更新之后,如果分类器在测试集上表现出的性能明显下降,我们则认为发生了概念漂移。Windme:和Kubat提出的FLORA系列算法、Last提出的OLIN算法等都是属于这一类。模型性能监测是十分常用的方法,但当数据流中存在类别不平衡或者进行半监督学习时,此方法将不再适用。
 
    (2)概念聚类法。Kataki、在2010年首次提出这一方法,基本思路是将数据流划分为数据块,少十且再将其映射为“概念向量”,对多个概念向量进行聚类,每一个聚类代表一个概念。当一个新的数据块到来时,计算其对应的概念向量与各个聚类中心之间的距离,少十以此判断是否发生了漂移。这一方法可以解决概念漂移领域的一个重要间题:重复概念的检测。概念聚类法局限的地方在于:假设每次划分的数据块内所有数据都属于同一概念。
 
    (3)样本分布监测法。针对样本集,提取其中的统计特性:特征值分布等,以这些参数的变化来判断是否发生概念漂移。2006-2011年间,Alippi, Peter, Kuncheva等人都是基于此原理提出了检测概念漂移的具体策略。
 
概念漂移
 
图8 概念漂移

 概念漂移:渐变式和突变式

图9 概念漂移:渐变式和突变式
 
    7.3聚类
 
    Han Jiawei教授在《Data Mining:Concept and Techniques》中,对聚类有一个简短的定义:将物理或抽象对象的集合分成相似的对象类的过程称为聚类。更形式化的一个描述方法是:聚类分析就是按照某种相似性度量方法对对象进行分组,使得各组内的相似度高,而组间的相似度低。俗语“物以类聚,人以群分”可以说是聚类作用的一个生动说明。
 
    聚类挖掘已广泛用于各种应用领域的模式识别以及离群点检测中。市场分析人员可以在没有任何先验知识的情况下,应用聚类方法基于购买模式数据库发现不同的顾客群;网络数据分析人员针对web文档数据或网络访间日志数据对访间的网页进行聚类,以发现对不同网页信息急感兴趣的人群,来支持精准营销或分析社会学上原因。应用聚类还可以发现异常点,即那些无法归入任何簇的点,离群点检测广泛应用于信用卡欺诈检测和监控电子商务中的犯罪活动。聚类分析还可以作为研究数据分布的功能以及作为其他算法的预处理步骤。
 
    从1967年研究人员提出第一种聚类算法开始,目前为止已经有多种可用的聚类算法。但是没有任何一种是普遍适用的,因为不同间题中数据的维度高低不同、各维数据特性不同、数据分布情况不同、数据规模不同,而随着大数据时代数据流的出现,对聚类算法更提出了内存限制、处理时间限制等挑战。但这些算法可以按照聚类依据不同进行分类,首先总体分为2大类:基于样本的聚类、基于变量的聚类。其中,基于样本的聚类人们研究的比较多,前面的聚类举例也全部是针对基于样本的;基于变量的聚类顾名思义就是对变量(即维度或属性)进行分组,它和数据分析中的因子分析及主成分分析(PCA)比较像;但聚类分析井不会对变量进行合井,只是用层次式等方法对变量的远近亲疏程度进行判别。在某些领域,基于变量聚类非常有用,比如传感器网络、社会网络、电力供应、股票市场上,比如通过聚类分析我们可以发现各支股票之间的关系,而通过流数据聚类则可以发现这种关系的变化的情况。
 
    基于样本的聚类是目前为止研究的最多,这些算法又可以分为:基于划分的聚类、基于层次的聚类、基于网格的聚类、基于密度的聚类、基于模型的聚类。对流数据的聚类也是在这些聚类算法的基础上发展而来的,因此,接下来简要介绍下这几种聚类算法及其特点。
 
    7.3.1基于划分的聚类
 
    经典的聚类算法k-mean、就是基于划分的,这种算法之所以应用广泛是因为其简单快速。但该算法需要人为设定一个代表聚类个数的参变量关,如何正确设置这个值是个难题。另外,k-mean、算法的理论基础是找到k个点(所谓中心点。entroid )使得相应簇中的点到这关个点的距离平方和最小。由此可见,采用这种理论所找到的簇是球形的,而且这种方法对噪声和孤立点敏感。而k-中心点法则是克服了这个间题的另一种基于划分的聚类算法。为了处理大规模数据集,人们在这些算法基础上进行了改进,提出一些新的算法如最大期望算法(EM)、基于随机选择的聚类算法(CLARANS)等。
 
    对数据流聚类时,因为流数据不断到达,所以无法在数据完全到达后进行聚类,部分数据上的聚类结果也很可能不再适用后面到达的数据,因此必须进行增量式聚类。而且,为了及时对后面很快到达的数据进行处理,每次的聚类操作必须在指定时间内完成,同时内存也要不断腾出来配合下一次聚类操作。当然,聚类结果可能达不到理论上的完美效果,但是要有尽可能好的效果,最好这个结果和理想结果差多少有一个理论上的范围。这些间题其实是所有流数据挖掘和静态数据的区别所在:要在有限内存有限时间内给出一个准确性有一定保证的挖掘结果,
 
    Farnstrom等人提出的一趟k-mean算法是适应流数据挖掘的k-mea,算法,它只对数据进行一趟扫描,当然历史结果的保存需要采用一种叫做聚类特征的概要数据。Domingo、和Hulten在此基础上提出的快速K均值算法(VFKM)则对每次增量聚类时需要的样本个数给出了理论上计算方法,其采用的理论基础是Hoeffding不等式,这个不等式和契比雪夫不等式性质类似,都是对于一个分布特性未知的随机变量,已知很少量的统计参数,可以在任意置信度之下计算出相应的置信区间。而Guha等人则提出了数据流聚类的k-中心点算法,并给出所需的样本个数及所需时间和空间的理论计算结果。
 
    7.3.2基于层次的聚类
 
    层次聚类也是一种常用聚类方法。它不再是只给出关个聚类而成的簇,而是给出多层的树状聚类结果。层次聚类又可分为凝聚和分裂两类,分别采用自底向上和自顶向下两种方法。BIRCH算法则综合了这两种方法。
 
    Aggarwal,J.Han等人提出的CIuStream算法则是BIRCH算法在数据流挖掘上的扩展。该算法的特征之一是:提出了倾斜时间窗口的概念,依据较近的数据比历史数据更重要的理念,最近的时间变化以较细的时间粒度刻画,而离现在较远的数据则采用较粗的时间粒度。该算法的另一个重要特点是,整个流聚类分为在线和离线两部分。在线部分增量式进行数据处理,获得摘要信息微簇( micro-cluster ),离线部分宏簇( macro-cluster)通过对在线部分的结果进行再处理获得层次的聚类结果。
 
    7.3.3基于网格和密度的聚类
 
    基于密度的聚类不再按之前两种聚类采用的距离的远近作为分划的依据,而是按照单位空间范围内点的个数即密度来划分空间,只要某一范围内密度大于某一指定参变量,则认为是同一簇。基于密度的聚类算法(DBSCAN)、通过对象排序识别聚类结构算法(OPTICS)等是经典基于密度聚类算法。
 
    基于网格的聚类是面向时空相关间题。它采用一个多分辨率的网格数据结构,这些网格把空间量化为有限数目的单元,所有聚类操作都在这些网格上进行。这些方法的主要优点是处理速度快,挚独立于数据对象数目,只与每一维上的单元数目相关。经典算法是信息网格算法(STING)、WaveCluster,而Quest上聚类(CLIQUE)则综合了密度和网格两种方法。
 
    在流数据聚类中,分形聚类则是一种基于网格的聚类,它将具有相同分形维的具有高自相似性的点分为一类。
 
    7.3.4基于模型的聚类
    
    基于模型的聚类其实是把回归拟合应用在聚类中,它为每一簇拟合一个模型,根据拟合模型的方法不同又分为统计学方法和神经网络方法,属于前者的有简单增量概念聚类算法(COBWEB)方法,属于后者的有学习矢量量化网络( LVQM )、自组织映射(SOM)等方法。

责任编辑:李欢
本文为e-works原创投稿文章,未经e-works书面许可,任何人不得复制、转载、摘编等任何方式进行使用。如已是e-works授权合作伙伴,应在授权范围内使用。e-works内容合作伙伴申请热线:editor@e-works.net.cn tel:027-87592219/20/21。
e-works
官方微信
掌上
信息化
编辑推荐
新闻推荐
博客推荐
视频推荐