沈荣 张保文

摘要： 首先针对数据分析中数据库处理方式的不同，对数据仓库的各种应用场景，数据挖掘技术的处理过程和数据挖掘面临的主要问题进行了阐述；随后对大数据处理技术的九种典型方法进行了简要综述， 包括布隆过滤器、散列法、倒排序、数据库索引与分布式处理等，对各种技术在大数据分析理解过程中的关键作用进行了总结；并对大数据处理和分析面临的计算复杂性、数据复杂性、以及系统复杂性进行分析，对各种典型的业务应用场景，提出了较为理想的应对方案。

关键词：数据库；到排序；分布式处理； 数据挖掘； 大数据；推荐系统

中图分类号：TP393 文献标识码：A

文章编号：1009-3044（2019）11-0013-04

“人类自有史以来的数据总量，每过18个月就会翻番”——“新摩尔定律”。谷歌是大数据处理的鼻祖，早在2007年，谷歌每天就要处理近20PB的数据量。2011年，全球数据总量就已达到了2.1ZB。IDC预计到2020年，全球数据总量将会超过40ZB。我国也在各个领域出现了海量数据。2013年百度的数据总量接近1000PB，阿里巴巴公司保存的数据超过了百PB级别，腾讯公司总存储数据量经压缩处理后仍超过了百PB级别，并且数据月增量达到10%，包括大量社交、游戏等领域积累的文本、音频、视频和关系类数据，大数据应用系统覆盖数据的获取、清洗、集成、分析与可视化等大数据全生命周期的多个处理环节[1]。伴随信息技术的发展，人们逐步迈入了大数据时代[2-6]的人-机-物融合的三元世界。近年来，大数据引起了学术界和产业界谷歌[7]等的重视，政府部门如美国[8]和其他组织如麦肯锡公司[9]、高德纳公司[10]的高度关注。

1 大数据分析

大数据技术是随着数据量急剧膨胀而产生的对海量数据使用和提取有效信息的一种方法，数据仓库是大数据分析的基础，数据挖掘是建立数据仓库的方法，也是使用和分析数据的方法。

1.1数据仓库

Oracle、Mysql、SQL server等关系数据库管理系统是随着关系数据库理论的提出现的，随着数据库使用范围的不断扩大，逐步被分为操作型数据库和分析型数据库。

1.1.1操作型数据库与分析型数据库的区别

（1）数据组成差别

操作型数据一般只会存放90天以内的数据，主要存放细节数据，一般反映的是现实世界的当前状态。分析型数据库存放的则是数年内的数据，既有细节数据，又有汇总数据，一般用户关注的是汇总数据部分，它可以综合所有快照对各个历史阶段进行统计分析。

（2）技术差别

操作型数据库查询的数据量少但频率高，并且允许用户进行增加、删除、修改、查询的操作，可以减少数据冗余，避免更新异常；而分析型数据库查询的量大但频率少，并且只能允许进行查询，它并不重视减少数据冗余。

1.1.2 数据仓库的组成

数据仓库的核心组件主要由四部分组成：各个源数据库、数据仓库技术（ETL）、数据仓库和前端应用，如图1所示：

（1）业务系统

业务系统包括各种源数据库，这些源数据库主要为业务系统提供数据支撑，同时也可以作为数据仓库的数据源，当然，除了业务系统，数据仓库也可以从其他外部数据源获取数据。

（2）ETL

ETL过程是构建数据仓库的重要的一个环节，包括数据提取（Extract）、转换（tranform）、清洗（cleansing）、加载（load）。

（3）数据仓库

数据仓库的突出的特点是对海量数据的支持和快速的检索技术。

1.2数据挖掘

数据挖掘既是建立数据仓库的方法，也是使用和分析数据的方法，数据挖掘在大型数据存储库中，可以自动发现有用的信息。数据挖掘用来探查大型数据库，发现先前未知的有用的模式。

数据挖掘是数据库中知识发现（Knowledge Discovery in database，Kdd）不可缺少的一部分，而KDD是将未加工的数据转换为有用信息的整个过程，该过程包括一系列转换步骤，从数据的预处理到数据挖掘结果的后处理。

数据挖掘主要任务包括预测建模（Predictive Modeling）、关联分析、聚类分析、异常检测等。

2 大数据处理方法

对于海量数据的处理，手工方式早已不能满足需求，必须通过工具进行处理。当数据量达到TB级别时，用计算机处理时也会对软、硬件的要求加倍提升。当遇到的海量数据无法全部存入内存时，那么如何处理这些重复、格式不正确的数据也是数据处理人员需要去解决的问题。

2.1 布隆过滤器及散列法

布隆过滤器（Bloom Filter）是1970年由Bloom提出，最初广泛用于拼写检查和数据库系统中。

布隆过滤器的基本原理：当一个元素被加入集合时，通过k个散列函数将这个元素映射为一个元素中的k个点，把它们置为1。检索时，我们只要看这些点是否是1就知道集合中是否有它了。如果这些点有任何一个0，则被检元素一定不在；如果都是1，被检元素很可能在，查找结果并不能保证100%正确。所以简单的改进就是Counting Bloom Filter，用counter数组代替位数组，就可以支持删除了插入的关键字了。

原始的Bloom Filter不支持删除已经插入的关键字，因为该关键字对应的位会牵动到其他关键字。所以简单的改进就是Counting Bloom Filter，用counter数组代替位数组，就可以支持删除了插入的关键字了。布隆过滤器可以用来实现数据字典，进行数据的判重（重复数据判断），或者集合求交集。

散列法（Hashing）是計算机科学中一种对数据的处理方法，通过某种特定的函数/算法，将要检索的项与用来检索的索引关联起来，生成一种便于搜索的数据结构。它常用作一种信息安全的方法，如果一串数据中经过散列算法计算出来的数据指纹，经常用来识别档案与数据是否被篡改过，以保证档案与数据确实是由原创者所提供的。

Hash函数选择在针对字符串、整数、排列时具有相应的Hash方法。 一种是Open Hashing，也称为拉链法；另一种就是Closed Hashing，也称开放地址法，即Opened Addressing。目前主要有除法散列法，平方散列法，斐波那契（Fibonacci）散列法。

2.2 堆排序及双层桶划分

堆排序（Heapsort）是利用一种叫堆积树的数据结构所设计出来的一种排序算法，它是选择排序的一种，可以利用数组的特点快速定位指定索引的元素。堆分为大顶堆和小顶堆，是完全二叉树.大顶堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大顶堆，因为根据大顶堆的要求可知，最大值一定在堆顶。

利用大顶堆（小顶堆）项记录的是最大关键字（最小关键字）这一特性，使得每次从无序数组中选择最大记录（最小记录）变得简单了。对于堆排序，最重要的两个操作就是构造初始堆和调整堆，事实上构造初始堆就是调整堆的过程，但构造初始堆是对所有非叶节点都进行调整。

堆排序适合处理海量数据，并且是可以放入内存的数据。

双层桶划分是一种数据结构，也可以看作一种算法设计思想.面对一堆大量的数据无法处理的时候，可以将其分为一个个小的单元，然后根据一定的策略来处理这些小单元。从而达到目的。

因为元素范围很大，不能利用直接寻址表，所以可通过多次划分，逐步确定范围，然后可以在一个可以接受的范围内进行。可以通过多次划分来缩小范围，双层只是一个例子，分治才是其根本。

双层桶划分适用于数据库范围查询，用来寻找第k大、中位数、不重复（或重复）的数字。

2.3索引

根据数据库的功能，可在数据库中创建3种索引：

（1）唯一索引

唯一索引是不允许其中任何兩行具有相同索引值的索引。当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复值得新数据。

（2）主键索引

主键索引是唯一索引的特殊类型，主键索引要求主键中的每个值都唯一，当在查询中使用主键索引时，还允许对数据的快速访问。

（3）聚集索引

聚集索引中表中的物理顺序与键值的逻辑索引顺序是一样的，一张表只能包含一个聚集索引，如果某索引不是聚集索引，那么表中行的物理顺序与键值的逻辑顺序是不匹配的，聚集索引比非聚集索引将提供更快的数据访问速度。

数据库索引是数据库管理系统中一个排序的数据结构，可以提高数据库表的数据访问速度，能实现大数据量的增加、删除、修改、查询等操作，还可以实现快速查询、更新数据库表中的数据。

倒排序索引在实际应用中主要是根据属性的值来查找数据，是根据属性来确定记录的位置，而不是由记录来确定属性值。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址，带有倒排序索引的文件称为倒排索引文件，也称倒排文件。

倒排序索引是文档检索系统中最常用的数据结构，主要用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。倒排序索引可以根据单词快速获取包含这个单词的文档列表，是实现单词到文档映射关系的最佳实现方式和最有效地索引结构，主要适用于搜索引擎、关键字查询等。

2.4 外排序及TRIE树

外排序指的是对大文件的排序，当文件太大而无法将整个文件所有记录调入内存中进行排序时，只能将文件放在外存储器中，通过数据的内、外存交换和”内部归并”两者结合起来实现。外排序在排序期间由于文件太大对象个数太多，不能同时全部存入内存，因此必须根据排序过程的要求，在内、外存之间不断地进行移动排序，适用于大部分大数据的排序、去重。

单词查找树Trie是一种哈希树的变种，也是一种树形结构。

TRIE树在信息检索、字符串匹配等领域有广泛的应用，是一种非常重要的数据结构，它也是后缀树、 AC自动机等复杂算法和数据结构的基础。

本节将分析对比典型的大数据处理平台，如 Hadoop[11]， Disco[12]，Twister[13]，Haloop[14]，iMapReduce[15]，iHadoop[16]以及类似MapReduce的Dryad[17]，Spark[18]。

3 大数据分析业务场景

3.1 信用风险建模

在信用风险建模中，可以根据实际需求采用多种不同的分析建模技术。在信用风险建模中，需要计算的其他指标还有违约损失率（LGD）、违约风险暴露（Exposure at Default，EAD）。违约损失率（LGD）是以未偿贷款总金额占比的形式来衡量经济损失，通常以线性回归方法或回归树方法进行估算。EAD是指债务人违约时预期的表外项目和表内项目的风险暴露总额，如抵押贷款、分期偿还的借款等，表外项目指信用卡的信用额度、赊销最高限额等。

3.2 产品知识中心

产品提供商创建的知识中心，可以直接在网站中使用，通过将信息放在WEB上，通信服务提供商网站作为知识中心，可以增加网站流量并减少投诉人数，知识中心网站提供自助服务，用户需要的产品支持技术通过知识中心自助解决，所以客户需要产品服务时，联系呼叫中心，寻求产品技术帮助的来源减少了。

一旦创建了一个知识的来源，这个来源可用于销售其他产品，并且把产品的特点和用户的诉求连接起来。许多关于该产品的零散的知识可能会迅速组织起来，并找到各种其他用途。

3.3 基于位置的服务

使用大数据技术的交易数据分析是革命性的，基于位置的服务，实现了个性化服务，完成了低延时导购服务。Shopkick是一个零售活动的工具，可以下载到任意一部智能手机上。SHopkick需要使用位置数据以提供服务。一旦该应用程序被下载到智能手机中，SHOPkick 将会寻找可使用的用户，通过智能手机记录他们的当前位置。此外，Shopkick还有零售商及其地理位置数据库。当用户家附近的百货商场想让用户去购物并激发购物欲望，Shopkick会给用户奖励这家商场的购物优惠券。当用户走进商场时，Shopkick可以使用智能手机确认当前的位置在该商场，然后增加用户的积分奖励，从而为用户换取更大的优惠。

设备制造商、通信服务提供商都已经开始提供大量的基于位置的服务，以吸引用户。例如智能手机在提供”找到我的电话”服务，可以找到电话。如果手机丢失，可以通过网站确定最后的已知的位置。这些基于位置的服务也可以产生收入。通信服务提供商可以决定为每次将智能手机切换到静音模式的配置服务收费。用户进入电影院后切换到静音模式，一旦用户离开电影院，就自动恢复正常响铃。使用这些数据的时候，一定要考虑如何保护用户隐私。

3.4 推荐系统

推荐系统作为一种有效的信息过滤手段，是当前解决信息过载问题及实现个性化信息服务的有效方法之一。目前，主流推荐系统可以分为 4 类[19]：协同过滤推荐、基于内容的推荐、基于知识的推荐和组合推荐。

3.5 市场细分

自动化技术让我們有机会在面向客户流程的每一步中收集数据在网页上的行为，例如，单击网站中的点击流。传感器的数据给了我们一个建立行为学模式应用分析的机会。早期的技术化是使用分析法来进行市场细分，原始的细分方式使用了人口统计学技术，并使用消费者的硬数据，如地理位置、年龄、性别和名族特点，建立市场细分。但营销人员很快意识到，行为特征也是细分客户的重要参数。

随着市场的发展，可以看到更多、更细致的细分方式，基于分析参数，驱动特定市场。例如，对于小型电子产品，市场营销人员开始尝试区分以下两类人群：一类是由于愿意尝试新鲜事物而购买的创新者，一类是跟随其他人购买的适应者。通过数据分析表可知，创新者群体乐于早期分享使用产品经验，而且对产品的缺陷表现得更宽容。

3.6 在线广告

随着在线内容的发布，线上广告在市场上的影响越来越大，同时，在线广告变得越来越复杂，为细分市场广告和基于上下文的广告提供了巨大的机会。发布客户广告的主要目标是在适当的网页上下文环境下，打动线上的用户，从而使用户产生行动，实现对商品的购买。大数据为营销人员提供了一个机会：收集无数用户的行为信息。通过整理和分析这些信息，可以建立两套关于客户的见解，这两项都与在线广告相关。首先，通过细分大量用户的购物历史来建立用户细分段，以及每个段的习惯购买模式。其次，可以使用上下文的驱动，特定于上下文的广告。

4 小结

本文主要介绍了大数据发展中出现的各种发展技术，介绍了布隆过滤器、散列法、堆排序、双层桶划分、数据库索引、倒排索引、外排序、trie树、分布式处理九种不同形式数据，并对信用分险建模、基于位置的服务、推荐系统、市场细分、在线广告五类大数据分析应用场景进行了介绍。

参考文献：

[1] Jagadish HV， Gehrke J， Labrinidis A， Papakonstantinou Y， Patel JM， Ramakrishnan R， Sha-habi C. Big data and its technical. Communications of the Acm， 2014.

[2] Big data. Nature， 2008，455（7209）：1-136.

[3] Dealing with data. Science， 2011，331（6018）：639-806.

[4] Big data. ERCIM News， 2012（89）：10-39.

[5] Vivien Marx. The big challenges of big data. Nature， 2013， 498（7453）：255-260.

[6] Xindong Wu， Xingquan Zhu， Gong-Qing Wu， and Wei Ding. Data mining with big data. IEEE Transactions on Knowledge and Data Engineering， 2014，26（1）：97-107.

[7] Divyakant Agrawal， Philip Bernstein， Elisa Bertino， Susan Davidson， Umeshwar Dayal， Mi-chael Franklin， Johannes Gehrke， Laura Haas， Alon Halevy， Jiawei Han， H.V. Jagadish， Alexandros Labrinidis， Sam Madden， Yannis Papakonstantinou， Jignesh Patel， Raghu Ramakrish-nan， Kenneth Ross， Cyrus Shahabi， Dan Suciu， Shiv Vaithyanathan， and Jennifer Widom. Chal-lenges and opportunities with big data： A community white paper developed by leading research-ers across the united states. White Paper， 2012.

[8] Rick Weiss and Lisa-Joy Zgorski. Obama administration unveils “Big Data” initiative： An-nounces $200 million in new R&D investments. Office of Science and Technology Policy， Executive Office of the President， 2012.

[9] James Manyika， Michael Chui， Brad Brown， Jacques Bughin， Richard Dobbs， Charles Roxburgh， and Angela Hung Byers. Big data： The next frontier for innovation， competition， and productivity. McKinley Global Institute， White Paper， 2011.

[10] Yvonne Genovese and Stephen Prentice. Pattern-based strategy： Getting value from big data. Gartner Secial Report， G00214032， 2011.

[11] Liu Y， Li M， Alham NK， Hammoud S. HSim： A MapReduce simulator in enabling cloud computing. Future Generation Computer Systems， 2013，29（1）：300 308. [doi： 10.1016/j.future.2011.05.007].

[12] GridGain in-memory data fabric. http：//go.gridgain.com/rs/491-TWR-806/images/GridGain_Product_Datasheet_070416.pdf.

[13] Mundkur P， Tuulos V， Flatow J. Disco： A computing platform for large-scale data analytics. In： Proc. of the 10th ACM SIGPLAN Workshop on Erlang. 2011. 84 89. [doi： 10.1145/2034654.2034670]540 Journal of Software Vol.28， No.3， March 2017.

[14] Ekanayake J， Li H， Zhang B， Gunarathne T， Bae S， Qiu J， Fox G. Twister： A runtime for iterative MapReduce. In： Proc. of the 19th ACM Intl Symp. on High Performance Distributed Com-puting. ACM Press， 2010. 810 818. [doi： 10.1145/1851476.1851593].

[15] Bu Y， Howe B， Balazinska M， Ernst MD. HaLoop： Efficient iterative data processing on large clusters. Proc. of the VLDB Endowment， 2010，3（1-2）：285 296. [doi： 10.14778/1920841.1920881].

[16] Zhang Y， Gao Q， Gao L， Wang C. Imapreduce： A distributed computing framework for iterative computation. Journal of Grid Computing， 2012，10（1）：47 68. [doi： 10.1007/s10723-012-9204-9].

[17] Elnikety E， Elsayed T， Ramadan HE. iHadoop： Asynchronous iterations for MapReduce. In： Proc. of the 3rd IEEE Intl Conf. on Cloud Computing Technology and Science （CloudCom）. IEEE， 2011. 81 90. [doi： 10.1109/CloudCom.2011.21].

[18] Isard M， Budiu M， Yu Y， Birrell A， Fetterly D. Dryad： Distributed data-parallel programs from sequential building blocks. Proc. Of the ACM SIGOPS Operating Systems Review， 2007，41（3）：59 72. [doi： 10.1145/1272998.1273005].

[19] Zaharia M， Chowdhury M， Franklin MJ， Shenker S， Stoica I. Spark： Cluster computing with working sets. HotCloud， 2010.

【通聯编辑：唐一东】