大數據分析和大數據處理技術研究綜述

沈榮 張保文

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

關鍵詞：數據庫；到排序；分布式處理； 數據挖掘； 大數據；推薦系統

中圖分類號：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.

【通聯編輯：唐一東】