大數(shù)據(jù)分析和大數(shù)據(jù)處理技術研究綜述

沈榮 張保文

摘要： 首先針對數(shù)據(jù)分析中數(shù)據(jù)庫處理方式的不同，對數(shù)據(jù)倉庫的各種應用場景，數(shù)據(jù)挖掘技術的處理過程和數(shù)據(jù)挖掘面臨的主要問題進行了闡述；隨后對大數(shù)據(jù)處理技術的九種典型方法進行了簡要綜述， 包括布隆過濾器、散列法、倒排序、數(shù)據(jù)庫索引與分布式處理等，對各種技術在大數(shù)據(jù)分析理解過程中的關鍵作用進行了總結；并對大數(shù)據(jù)處理和分析面臨的計算復雜性、數(shù)據(jù)復雜性、以及系統(tǒng)復雜性進行分析，對各種典型的業(yè)務應用場景，提出了較為理想的應對方案。

關鍵詞：數(shù)據(jù)庫；到排序；分布式處理； 數(shù)據(jù)挖掘； 大數(shù)據(jù)；推薦系統(tǒng)

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）11-0013-04

“人類自有史以來的數(shù)據(jù)總量，每過18個月就會翻番”——“新摩爾定律”。谷歌是大數(shù)據(jù)處理的鼻祖，早在2007年，谷歌每天就要處理近20PB的數(shù)據(jù)量。2011年，全球數(shù)據(jù)總量就已達到了2.1ZB。IDC預計到2020年，全球數(shù)據(jù)總量將會超過40ZB。我國也在各個領域出現(xiàn)了海量數(shù)據(jù)。2013年百度的數(shù)據(jù)總量接近1000PB，阿里巴巴公司保存的數(shù)據(jù)超過了百PB級別，騰訊公司總存儲數(shù)據(jù)量經(jīng)壓縮處理后仍超過了百PB級別，并且數(shù)據(jù)月增量達到10%，包括大量社交、游戲等領域積累的文本、音頻、視頻和關系類數(shù)據(jù)，大數(shù)據(jù)應用系統(tǒng)覆蓋數(shù)據(jù)的獲取、清洗、集成、分析與可視化等大數(shù)據(jù)全生命周期的多個處理環(huán)節(jié)[1]。伴隨信息技術的發(fā)展，人們逐步邁入了大數(shù)據(jù)時代[2-6]的人-機-物融合的三元世界。近年來，大數(shù)據(jù)引起了學術界和產(chǎn)業(yè)界谷歌[7]等的重視，政府部門如美國[8]和其他組織如麥肯錫公司[9]、高德納公司[10]的高度關注。

1 大數(shù)據(jù)分析

大數(shù)據(jù)技術是隨著數(shù)據(jù)量急劇膨脹而產(chǎn)生的對海量數(shù)據(jù)使用和提取有效信息的一種方法，數(shù)據(jù)倉庫是大數(shù)據(jù)分析的基礎，數(shù)據(jù)挖掘是建立數(shù)據(jù)倉庫的方法，也是使用和分析數(shù)據(jù)的方法。

1.1數(shù)據(jù)倉庫

Oracle、Mysql、SQL server等關系數(shù)據(jù)庫管理系統(tǒng)是隨著關系數(shù)據(jù)庫理論的提出現(xiàn)的，隨著數(shù)據(jù)庫使用范圍的不斷擴大，逐步被分為操作型數(shù)據(jù)庫和分析型數(shù)據(jù)庫。

1.1.1操作型數(shù)據(jù)庫與分析型數(shù)據(jù)庫的區(qū)別

（1）數(shù)據(jù)組成差別

操作型數(shù)據(jù)一般只會存放90天以內(nèi)的數(shù)據(jù)，主要存放細節(jié)數(shù)據(jù)，一般反映的是現(xiàn)實世界的當前狀態(tài)。分析型數(shù)據(jù)庫存放的則是數(shù)年內(nèi)的數(shù)據(jù)，既有細節(jié)數(shù)據(jù)，又有匯總數(shù)據(jù)，一般用戶關注的是匯總數(shù)據(jù)部分，它可以綜合所有快照對各個歷史階段進行統(tǒng)計分析。

（2）技術差別

操作型數(shù)據(jù)庫查詢的數(shù)據(jù)量少但頻率高，并且允許用戶進行增加、刪除、修改、查詢的操作，可以減少數(shù)據(jù)冗余，避免更新異常；而分析型數(shù)據(jù)庫查詢的量大但頻率少，并且只能允許進行查詢，它并不重視減少數(shù)據(jù)冗余。

1.1.2 數(shù)據(jù)倉庫的組成

數(shù)據(jù)倉庫的核心組件主要由四部分組成：各個源數(shù)據(jù)庫、數(shù)據(jù)倉庫技術（ETL）、數(shù)據(jù)倉庫和前端應用，如圖1所示：

（1）業(yè)務系統(tǒng)

業(yè)務系統(tǒng)包括各種源數(shù)據(jù)庫，這些源數(shù)據(jù)庫主要為業(yè)務系統(tǒng)提供數(shù)據(jù)支撐，同時也可以作為數(shù)據(jù)倉庫的數(shù)據(jù)源，當然，除了業(yè)務系統(tǒng)，數(shù)據(jù)倉庫也可以從其他外部數(shù)據(jù)源獲取數(shù)據(jù)。

（2）ETL

ETL過程是構建數(shù)據(jù)倉庫的重要的一個環(huán)節(jié)，包括數(shù)據(jù)提?。‥xtract）、轉(zhuǎn)換（tranform）、清洗（cleansing）、加載（load）。

（3）數(shù)據(jù)倉庫

數(shù)據(jù)倉庫的突出的特點是對海量數(shù)據(jù)的支持和快速的檢索技術。

1.2數(shù)據(jù)挖掘

數(shù)據(jù)挖掘既是建立數(shù)據(jù)倉庫的方法，也是使用和分析數(shù)據(jù)的方法，數(shù)據(jù)挖掘在大型數(shù)據(jù)存儲庫中，可以自動發(fā)現(xiàn)有用的信息。數(shù)據(jù)挖掘用來探查大型數(shù)據(jù)庫，發(fā)現(xiàn)先前未知的有用的模式。

數(shù)據(jù)挖掘是數(shù)據(jù)庫中知識發(fā)現(xiàn)（Knowledge Discovery in database，Kdd）不可缺少的一部分，而KDD是將未加工的數(shù)據(jù)轉(zhuǎn)換為有用信息的整個過程，該過程包括一系列轉(zhuǎn)換步驟，從數(shù)據(jù)的預處理到數(shù)據(jù)挖掘結果的后處理。

數(shù)據(jù)挖掘主要任務包括預測建模（Predictive Modeling）、關聯(lián)分析、聚類分析、異常檢測等。

2 大數(shù)據(jù)處理方法

對于海量數(shù)據(jù)的處理，手工方式早已不能滿足需求，必須通過工具進行處理。當數(shù)據(jù)量達到TB級別時，用計算機處理時也會對軟、硬件的要求加倍提升。當遇到的海量數(shù)據(jù)無法全部存入內(nèi)存時，那么如何處理這些重復、格式不正確的數(shù)據(jù)也是數(shù)據(jù)處理人員需要去解決的問題。

2.1 布隆過濾器及散列法

布隆過濾器（Bloom Filter）是1970年由Bloom提出，最初廣泛用于拼寫檢查和數(shù)據(jù)庫系統(tǒng)中。

布隆過濾器的基本原理：當一個元素被加入集合時，通過k個散列函數(shù)將這個元素映射為一個元素中的k個點，把它們置為1。檢索時，我們只要看這些點是否是1就知道集合中是否有它了。如果這些點有任何一個0，則被檢元素一定不在；如果都是1，被檢元素很可能在，查找結果并不能保證100%正確。所以簡單的改進就是Counting Bloom Filter，用counter數(shù)組代替位數(shù)組，就可以支持刪除了插入的關鍵字了。

原始的Bloom Filter不支持刪除已經(jīng)插入的關鍵字，因為該關鍵字對應的位會牽動到其他關鍵字。所以簡單的改進就是Counting Bloom Filter，用counter數(shù)組代替位數(shù)組，就可以支持刪除了插入的關鍵字了。布隆過濾器可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重（重復數(shù)據(jù)判斷），或者集合求交集。

散列法（Hashing）是計算機科學中一種對數(shù)據(jù)的處理方法，通過某種特定的函數(shù)/算法，將要檢索的項與用來檢索的索引關聯(lián)起來，生成一種便于搜索的數(shù)據(jù)結構。它常用作一種信息安全的方法，如果一串數(shù)據(jù)中經(jīng)過散列算法計算出來的數(shù)據(jù)指紋，經(jīng)常用來識別檔案與數(shù)據(jù)是否被篡改過，以保證檔案與數(shù)據(jù)確實是由原創(chuàng)者所提供的。

Hash函數(shù)選擇在針對字符串、整數(shù)、排列時具有相應的Hash方法。 一種是Open Hashing，也稱為拉鏈法；另一種就是Closed Hashing，也稱開放地址法，即Opened Addressing。目前主要有除法散列法，平方散列法，斐波那契（Fibonacci）散列法。

2.2 堆排序及雙層桶劃分

堆排序（Heapsort）是利用一種叫堆積樹的數(shù)據(jù)結構所設計出來的一種排序算法，它是選擇排序的一種，可以利用數(shù)組的特點快速定位指定索引的元素。堆分為大頂堆和小頂堆，是完全二叉樹.大頂堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值。在數(shù)組的非降序排序中，需要使用的就是大頂堆，因為根據(jù)大頂堆的要求可知，最大值一定在堆頂。

利用大頂堆（小頂堆）項記錄的是最大關鍵字（最小關鍵字）這一特性，使得每次從無序數(shù)組中選擇最大記錄（最小記錄）變得簡單了。對于堆排序，最重要的兩個操作就是構造初始堆和調(diào)整堆，事實上構造初始堆就是調(diào)整堆的過程，但構造初始堆是對所有非葉節(jié)點都進行調(diào)整。

堆排序適合處理海量數(shù)據(jù)，并且是可以放入內(nèi)存的數(shù)據(jù)。

雙層桶劃分是一種數(shù)據(jù)結構，也可以看作一種算法設計思想.面對一堆大量的數(shù)據(jù)無法處理的時候，可以將其分為一個個小的單元，然后根據(jù)一定的策略來處理這些小單元。從而達到目的。

因為元素范圍很大，不能利用直接尋址表，所以可通過多次劃分，逐步確定范圍，然后可以在一個可以接受的范圍內(nèi)進行?？梢酝ㄟ^多次劃分來縮小范圍，雙層只是一個例子，分治才是其根本。

雙層桶劃分適用于數(shù)據(jù)庫范圍查詢，用來尋找第k大、中位數(shù)、不重復（或重復）的數(shù)字。

2.3索引

根據(jù)數(shù)據(jù)庫的功能，可在數(shù)據(jù)庫中創(chuàng)建3種索引：

（1）唯一索引

唯一索引是不允許其中任何兩行具有相同索引值的索引。當現(xiàn)有數(shù)據(jù)中存在重復的鍵值時，大多數(shù)數(shù)據(jù)庫不允許將新創(chuàng)建的唯一索引與表一起保存。數(shù)據(jù)庫還可能防止添加將在表中創(chuàng)建重復值得新數(shù)據(jù)。

（2）主鍵索引

主鍵索引是唯一索引的特殊類型，主鍵索引要求主鍵中的每個值都唯一，當在查詢中使用主鍵索引時，還允許對數(shù)據(jù)的快速訪問。

（3）聚集索引

聚集索引中表中的物理順序與鍵值的邏輯索引順序是一樣的，一張表只能包含一個聚集索引，如果某索引不是聚集索引，那么表中行的物理順序與鍵值的邏輯順序是不匹配的，聚集索引比非聚集索引將提供更快的數(shù)據(jù)訪問速度。

數(shù)據(jù)庫索引是數(shù)據(jù)庫管理系統(tǒng)中一個排序的數(shù)據(jù)結構，可以提高數(shù)據(jù)庫表的數(shù)據(jù)訪問速度，能實現(xiàn)大數(shù)據(jù)量的增加、刪除、修改、查詢等操作，還可以實現(xiàn)快速查詢、更新數(shù)據(jù)庫表中的數(shù)據(jù)。

倒排序索引在實際應用中主要是根據(jù)屬性的值來查找數(shù)據(jù)，是根據(jù)屬性來確定記錄的位置，而不是由記錄來確定屬性值。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址，帶有倒排序索引的文件稱為倒排索引文件，也稱倒排文件。

倒排序索引是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結構，主要用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。倒排序索引可以根據(jù)單詞快速獲取包含這個單詞的文檔列表，是實現(xiàn)單詞到文檔映射關系的最佳實現(xiàn)方式和最有效地索引結構，主要適用于搜索引擎、關鍵字查詢等。

2.4 外排序及TRIE樹

外排序指的是對大文件的排序，當文件太大而無法將整個文件所有記錄調(diào)入內(nèi)存中進行排序時，只能將文件放在外存儲器中，通過數(shù)據(jù)的內(nèi)、外存交換和”內(nèi)部歸并”兩者結合起來實現(xiàn)。外排序在排序期間由于文件太大對象個數(shù)太多，不能同時全部存入內(nèi)存，因此必須根據(jù)排序過程的要求，在內(nèi)、外存之間不斷地進行移動排序，適用于大部分大數(shù)據(jù)的排序、去重。

單詞查找樹Trie是一種哈希樹的變種，也是一種樹形結構。

TRIE樹在信息檢索、字符串匹配等領域有廣泛的應用，是一種非常重要的數(shù)據(jù)結構，它也是后綴樹、 AC自動機等復雜算法和數(shù)據(jù)結構的基礎。

本節(jié)將分析對比典型的大數(shù)據(jù)處理平臺，如 Hadoop[11]， Disco[12]，Twister[13]，Haloop[14]，iMapReduce[15]，iHadoop[16]以及類似MapReduce的Dryad[17]，Spark[18]。

3 大數(shù)據(jù)分析業(yè)務場景

3.1 信用風險建模

在信用風險建模中，可以根據(jù)實際需求采用多種不同的分析建模技術。在信用風險建模中，需要計算的其他指標還有違約損失率（LGD）、違約風險暴露（Exposure at Default，EAD）。違約損失率（LGD）是以未償貸款總金額占比的形式來衡量經(jīng)濟損失，通常以線性回歸方法或回歸樹方法進行估算。EAD是指債務人違約時預期的表外項目和表內(nèi)項目的風險暴露總額，如抵押貸款、分期償還的借款等，表外項目指信用卡的信用額度、賒銷最高限額等。

3.2 產(chǎn)品知識中心

產(chǎn)品提供商創(chuàng)建的知識中心，可以直接在網(wǎng)站中使用，通過將信息放在WEB上，通信服務提供商網(wǎng)站作為知識中心，可以增加網(wǎng)站流量并減少投訴人數(shù)，知識中心網(wǎng)站提供自助服務，用戶需要的產(chǎn)品支持技術通過知識中心自助解決，所以客戶需要產(chǎn)品服務時，聯(lián)系呼叫中心，尋求產(chǎn)品技術幫助的來源減少了。

一旦創(chuàng)建了一個知識的來源，這個來源可用于銷售其他產(chǎn)品，并且把產(chǎn)品的特點和用戶的訴求連接起來。許多關于該產(chǎn)品的零散的知識可能會迅速組織起來，并找到各種其他用途。

3.3 基于位置的服務

使用大數(shù)據(jù)技術的交易數(shù)據(jù)分析是革命性的，基于位置的服務，實現(xiàn)了個性化服務，完成了低延時導購服務。Shopkick是一個零售活動的工具，可以下載到任意一部智能手機上。SHopkick需要使用位置數(shù)據(jù)以提供服務。一旦該應用程序被下載到智能手機中，SHOPkick 將會尋找可使用的用戶，通過智能手機記錄他們的當前位置。此外，Shopkick還有零售商及其地理位置數(shù)據(jù)庫。當用戶家附近的百貨商場想讓用戶去購物并激發(fā)購物欲望，Shopkick會給用戶獎勵這家商場的購物優(yōu)惠券。當用戶走進商場時，Shopkick可以使用智能手機確認當前的位置在該商場，然后增加用戶的積分獎勵，從而為用戶換取更大的優(yōu)惠。

設備制造商、通信服務提供商都已經(jīng)開始提供大量的基于位置的服務，以吸引用戶。例如智能手機在提供”找到我的電話”服務，可以找到電話。如果手機丟失，可以通過網(wǎng)站確定最后的已知的位置。這些基于位置的服務也可以產(chǎn)生收入。通信服務提供商可以決定為每次將智能手機切換到靜音模式的配置服務收費。用戶進入電影院后切換到靜音模式，一旦用戶離開電影院，就自動恢復正常響鈴。使用這些數(shù)據(jù)的時候，一定要考慮如何保護用戶隱私。

3.4 推薦系統(tǒng)

推薦系統(tǒng)作為一種有效的信息過濾手段，是當前解決信息過載問題及實現(xiàn)個性化信息服務的有效方法之一。目前，主流推薦系統(tǒng)可以分為 4 類[19]：協(xié)同過濾推薦、基于內(nèi)容的推薦、基于知識的推薦和組合推薦。

3.5 市場細分

自動化技術讓我們有機會在面向客戶流程的每一步中收集數(shù)據(jù)在網(wǎng)頁上的行為，例如，單擊網(wǎng)站中的點擊流。傳感器的數(shù)據(jù)給了我們一個建立行為學模式應用分析的機會。早期的技術化是使用分析法來進行市場細分，原始的細分方式使用了人口統(tǒng)計學技術，并使用消費者的硬數(shù)據(jù)，如地理位置、年齡、性別和名族特點，建立市場細分。但營銷人員很快意識到，行為特征也是細分客戶的重要參數(shù)。

隨著市場的發(fā)展，可以看到更多、更細致的細分方式，基于分析參數(shù)，驅(qū)動特定市場。例如，對于小型電子產(chǎn)品，市場營銷人員開始嘗試區(qū)分以下兩類人群：一類是由于愿意嘗試新鮮事物而購買的創(chuàng)新者，一類是跟隨其他人購買的適應者。通過數(shù)據(jù)分析表可知，創(chuàng)新者群體樂于早期分享使用產(chǎn)品經(jīng)驗，而且對產(chǎn)品的缺陷表現(xiàn)得更寬容。

3.6 在線廣告

隨著在線內(nèi)容的發(fā)布，線上廣告在市場上的影響越來越大，同時，在線廣告變得越來越復雜，為細分市場廣告和基于上下文的廣告提供了巨大的機會。發(fā)布客戶廣告的主要目標是在適當?shù)木W(wǎng)頁上下文環(huán)境下，打動線上的用戶，從而使用戶產(chǎn)生行動，實現(xiàn)對商品的購買。大數(shù)據(jù)為營銷人員提供了一個機會：收集無數(shù)用戶的行為信息。通過整理和分析這些信息，可以建立兩套關于客戶的見解，這兩項都與在線廣告相關。首先，通過細分大量用戶的購物歷史來建立用戶細分段，以及每個段的習慣購買模式。其次，可以使用上下文的驅(qū)動，特定于上下文的廣告。

4 小結

本文主要介紹了大數(shù)據(jù)發(fā)展中出現(xiàn)的各種發(fā)展技術，介紹了布隆過濾器、散列法、堆排序、雙層桶劃分、數(shù)據(jù)庫索引、倒排索引、外排序、trie樹、分布式處理九種不同形式數(shù)據(jù)，并對信用分險建模、基于位置的服務、推薦系統(tǒng)、市場細分、在線廣告五類大數(shù)據(jù)分析應用場景進行了介紹。

參考文獻：

[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.

【通聯(lián)編輯：唐一東】