二、傳統大數據算法

算法設計與分析是計算科學的重要主題，進行大數據計算，算法設計與分析是必不可少的步驟，可以說算法設計是大數據項目落地的關鍵之一。大數據算法按挖掘任務細分，主要有分類分析、聚類分析、關聯分析等算法。其中分類就是按照一定的標準把數據對象劃歸成不同類別；聚類是在沒有給定劃分類的情況下根據數據信息的相似度進行數據聚集的一種方法；關聯分析就是對大量的數據進行分析，從中發現滿足一定支持度和可信度的數據項之間的聯系規則。

（一）分類算法

1．分類算法綜述

分類是大數據分析中的一個重要課題。分類的目的是學會一個分類模型（也常常稱作分類器），該模型能把數據庫中的數據項映射到給定類別中的某一個。分類可用于提取描述重要數據類的模型或預測未來的數據趨勢。

2．主要分類算法介紹

主要使用的分類算法有決策樹、邏輯回歸、神經網絡、支持向量機、樸素貝葉斯分類、判別分析、K近鄰算法，等等，下面將逐一介紹。

（1）決策樹

決策樹方法是利用信息論中的信息增益尋找數據庫中具有最大信息量的屬性字段，建立決策樹的一個結點，再根據該屬性字段的不同取值建立樹的分支，在每個分支子集中重復建立樹的下層結點和分支的一個過程。

構造決策樹的具體過程為：首先尋找初始分裂，以決定哪個屬性域作為目前最好的分類指標。一般的做法是窮盡所有的屬性域，對每個屬性域分裂的好壞做出量化，計算出最好的一個分裂。量化的標準是計算每個分裂的多樣性指標。其次，重復第一步，直至每個葉節點內的記錄都屬于同一類且增長到一棵完整的樹。

常用的決策樹算法有ID3、C4.5、CART算法等。這些算法主要以信息論為基礎，以信息熵、信息增益率或基尼系統為衡量標準，從而實現對數據的歸納分類。

（2）邏輯回歸

邏輯回歸就是這樣的一個過程：面對一個回歸或者分類問題，建立代價函數，然后通過優化方法迭代求解出最優的模型參數，然后測試驗證我們這個求解的模型的好壞。Logistic回歸雖然名字里帶“回歸”，但是它實際上是一種分類方法，主要用于二分類問題，是一種強分類器。

Logistic回歸算法基于Sigmoid函數，Sigmoid函數定義如下：1/（1+exp（-z）），其函數值域范圍為（0，1），可以用來做分類器。

邏輯回歸的一般步驟是：尋找h函數（即預測函數）、構造J函數（損失函數）、想辦法使得J函數最小并求得回歸參數（θ），參數的求解過程可以由最優化算法來完成。在最優化算法中，最常用的就是梯度上升算法，而梯度上升算法可以簡化為隨機梯度上升算法。

（3）神經網絡

神經網絡是分類技術中重要方法之一。人工神經網絡是一種應用類似于大腦神經突觸聯接的結構進行信息處理的數學模型，在這種模型中，大量的節點（或稱“神經元”）之間相互聯接構成網絡，即“神經網絡”，以達到處理信息的目的。神經網絡通常需要進行訓練，訓練的過程就是網絡進行學習的過程。訓練改變了網絡節點的連接權值使其具有分類的功能，經過訓練的網絡就可用于對象的識別。

神經網絡的優勢在于：可以任意精度逼近任意函數；神經網絡方法本身屬于非線性模型，能夠適應各種復雜的數據關系；神經網絡具備很強的學習能力，使它能比很多分類算法更好地適應數據空間的變化；神經網絡借鑒人腦的物理結構和機理，能夠模擬人腦的某些功能，具備“智能”的特點。用于分類常見的神經網絡模型包括：BP（Back Propagation）神經網絡、RBF（Radical Basis Function）神經網絡等。

人工神經網絡作為另一種處理非線性、不確定性的有力工具，目前還存在許多局限性：首先，網絡本身的黑箱式內部知識表達，使其不能利用初始經驗進行學習，易于陷入局部極小值。其次，就本質而言，人工神經網絡就是用靜態網絡處理連續時間動態系統的控制問題。這就不可避免地帶來了差分模型定階及網絡規模隨階次迅速增加的復雜性問題。再次，人工神經網絡的泛化能力在相當程度上決定了控制系統的魯棒性。全局逼近的泛化能力受大量局部極值與緩慢學習速度制約，局部逼近則受存儲容量與實時性的而嚴重限制。

（4）支持向量機

支持向量機（Support Vector Machine）是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中有許多特有的優勢，并能推廣應用到函數擬合等其他機器學習問題中。

支持向量機是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。

支持向量機將向量映射到一個更高維的空間里，在這個空間里建有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。因此最大化幾何間隔成了我們訓練階段的目標。實際中，我們會經常遇到線性不可分的樣例，此時，我們的常用做法是把樣例特征映射到高維空間中去。線性不可分映射到高維空間，可能會導致維度大小高到可怕的程度，導致計算復雜。核函數的價值在于它雖然也是講特征進行從低維到高維的轉換，但核函數絕就絕在它事先在低維上進行計算，而將實質上的分類效果表現在了高維上，避免了直接在高維空間中的復雜計算。

（5）樸素貝葉斯分類

樸素貝葉斯分類基于貝葉斯定理，假設一個屬性值對給定類的影響獨立于其他屬性的值。設X是類標號未知的數據樣本。設H為某種假定，如，數據樣本X屬于某特定的類C。因此我們希望確定P（H ｜X），即給定觀測數據樣本X，假定H成立的概率（后驗概率）。

貝葉斯定理（公式）：

樸素貝葉斯分類是一種十分簡單的分類算法，叫它樸素貝葉斯分類是因為這種方法的思想真的很樸素，樸素貝葉斯的思想基礎是這樣的：對于給出的待分類項，求解在此項出現的條件下各個類別出現的概率，哪個最大，就認為此待分類項屬于哪個類別。

（6）判別分析

判別分析是一種在已知研究對象用某種方法已經分成若干類的情況下，確定新的樣品屬于哪一類的多元統計分析方法，其原理是利用已知對象的某些觀測指標和所屬類別，根據判別準則建立一個或多個判別函數，用研究對象的大量資料確定判別函數中特定系數，并計算判別指標，然后用總結出判別規則確定未知對象屬于哪一類。當描述研究對象的性質特征不全或不能直接測量數據確定研究對象所屬類別時，可以通過判別分析進行歸類。判別分析，根據采用的判別準則的不同主要有以下幾種：

①最大似然法：用于自變量均為分類變量，該方法建立在獨立事件概率乘法定理的基礎上，根據訓練樣本信息求得自變量各種組合情況下樣品被封為任何一類的概率。當新樣本進入時，計算它被分到每一類中去的條件概率（似然值），概率最大的那一類就是最終評定的歸類。

②距離判別：其基本思想是由訓練樣本得出每個分類的重心坐標，然后對新樣本求出它們離各個類別重心的距離遠近，從而歸入離得最近的類。最常用的距離是馬氏距離。距離判別的特點是直觀、簡單，適合于對自變量均為連續變量的情況下進行分類，且它對變量的分布類型無嚴格要求，特別是并不嚴格要求總體協方差陣相等。

③Fisher判別：也稱典則判別，是根據線性Fisher函數值進行判別，通常用于兩種判別問題，使用此準則要求各組變量的均值有顯著性差異。該方法的基本思想是投影，即將原來在R維空間的自變量組合投影到維度較低的D維空間去，然后在D維空間中再進行分類。投影的原則是使得每一類的差異盡可能小，而不同類間投影的離差盡可能大。

④Bayes判別：許多時候用戶對各類別的比例分布情況有一定的先驗信息，比如客戶對投遞廣告的反應絕大多數都是無回音，如果進行判別，自然也應當是無回音的居多。此時，Bayes判別恰好適用。Bayes判別就是根據總體的先驗概率，使誤判的平均損失達到最小。其最大優勢是可以用于多組判別問題。但是適用此方法必須滿足三個假設條件，即各種變量必須服從多元正態分布、各組協方差矩陣必須相等、各組變量均值均有顯著性差異。

（7）K近鄰算法

K近鄰法是有監督學習方法，原理很簡單，假設我們有一堆分好類的樣本數據，分好類表示每個樣本都一個對應的已知類標簽，當來一個測試樣本要我們判斷它的類別時，就分別計算到每個樣本的距離，然后選取離測試樣本最近的前K個樣本的標簽累計投票，得票數最多的那個標簽就為測試樣本的標簽。

K近鄰算法是最近鄰算法的一個推廣。該規則將是一個測試數據點x分類為與它最接近的K個近鄰中出現最多的那個類別。K近鄰算法從測試樣本點x開始生長，不斷的擴大區域，直到包含進K個訓練樣本點為止，并且把測試樣本點x歸為這最近的K個訓練樣本點中出現頻率最大的類別。其中測試樣本與訓練樣本的相似度一般使用歐式距離測量。

在大樣本集和高維樣本分類中（如文本分類），KNN方法的缺陷凸顯。表現在以下幾個方面：KNN分類算法是懶散的分類算法，對于分類所需的計算均推遲至分類進行，故在其分類器中存儲有大量的樣本向量。在未知類別樣本需要分類時，在計算所存儲樣本和未知類別樣本的距離時，高維樣本或大樣本集所需要的時間和空間的復雜度均較高。

（二）聚類算法

1．聚類算法綜述

聚類算法是多元統計分析中研究“物以類聚”的一種方法，用于對事物的類別面貌尚不清楚，甚至在事前連總共有幾類都不能確定的情況下進行分類的場合。

聚類算法把分類對象按一定規則分成組或類，這些組或類不是事先給定的而是根據數據特征而定的，它同分類的根本區別在于：分類是開始知道所根據的特征，而聚類是要準確地找到數據特征，進行聚類前并不知道將要劃分成幾個組和什么樣的組，也不知道根據哪些空間區分規則來定義組。聚類也可作為特征和分類算法的預處理步驟，其應用范圍涉及商務、生物、地理、WEB文檔分類、仿真等諸多領域。

2．數據的相似性度量

聚類算法按照樣本點之間的親疏遠近程度進行分類。刻畫聚類樣本點之間的親疏遠近程度主要的方法是利用距離度量的方法，常用的距離度量方法有歐幾里德距離、余弦距離和馬氏距離等。

3．主要聚類方法

目前聚類算法主要分為基于層次的聚類方法和基于劃分的聚類方法。

（1）基于層次的聚類方法

層次聚類算法，它是通過將數據組織為若干組并形成一個相應的樹來進行聚類的。根據層次是自底向上還是自頂而下形成，層次聚類算法可以進一步分為凝聚型的聚類算法和分裂型的聚類算法。兩種基本的層次聚類方法。

凝聚的層次聚類（AGNES算法）是一種自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者達到某個終結條件。大部分的層次聚類方法都屬于這一類，它們在簇間的相似度的定義有點不一樣。

分裂的層次聚類（DIANA算法）是一種自頂向下的策略，它首先將所有對象放在一個簇中，然后慢慢地細分為越來越小的簇，直到每個對象自行形成一簇，或者直到滿足其他的一個終結條件，例如滿足了某個期望的簇數目，又或者兩個最近的簇之間的距離達到了閾值。

（2）基于劃分的聚類方法

給定一個數據庫包含N_p 個數據對象以及數目K的即將生成的簇，一個劃分類的算法將對象分為K個劃分，其中，這里的每個劃分分別代表一個簇，并且K < = N_p。其中的K需要人為指定。它一般從一個初始劃分開始，然后通過重復的控制策略，使某個準則函數最優化。因此，它可以被看作一個優化問題，而優化問題往往是NP難問題。基于劃分的聚類方法的優缺點跟層次的聚類方法的優缺點剛剛相反，層次聚類算法的優點恰恰是劃分聚類方法的缺點，反之亦然。根據它們之間的優缺點，實踐中往往會更趨向于使用劃分的聚類方法。

基于劃分的聚類算法有許多，下面介紹幾種常見的基于劃分的聚類算法。

①K - means

k - means算法是最為經典的基于劃分的聚類方法，是十大經典大數據分析算法之一。k - means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近它們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

該算法的最大優勢在于簡潔和快速，對于處理大數據集，該算法是相對可伸縮和高效率的。算法的缺點是簇的數目必須人為的指定，并且對初值敏感，對于不同的初值，可能會導致不同結果，而且不適合于發現非凸面形狀的簇或者大小差別很大的簇，它對于“噪聲”和孤立點數據是敏感的。該算法的關鍵在于初始中心的選擇和距離公式。

②模糊C均值算法

模糊聚類算法作為無監督機器學習的主要技術之一，是用模糊理論對重要數據分析和建模的方法，建立了樣本類屬的不確定性描述，能比較客觀地反映現實世界，它已經有效地應用在大規模數據分析、大數據分析、矢量量化、圖像分割、模式識別等領域，具有重要的理論與實際應用價值，隨著應用的深入發展，模糊聚類算法的研究不斷豐富。在眾多模糊聚類算法中，模糊C -均值（FCM）算法應用最廣泛且較成功，它通過優化目標函數得到每個樣本點對所有類中心的隸屬度，從而決定樣本點的類屬以達到自動對樣本數據進行分類的目的。它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。模糊C均值算法是普通C均值算法的改進，普通C均值算法對于數據的劃分是硬性的，而FCM則是一種柔性的模糊劃分。

所以，該算法的隸屬函數是一個軟隸屬函數，即一個數據點可能屬于多個簇，而它的權重是一個恒定的常數。模糊C均值算法可以很好地處理臨界數據點，它和K - means算法一樣，需要人為的指定簇的數目。該算法的缺點是可能會產生重合聚類，需要人為指定簇的個數，收斂于局部最優以及初始條件對聚類結果影響很大。

③EM算法

EM（Expectation - Maximization Algorithm）最大期望算法是在概率模型中尋找參數最大似然估計或者最大后驗估計算法，其中概率模型依賴于無法觀測的隱藏變量。最大期望算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變量的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在E步上求得的最大似然值來計算參數的值。M步上找到的參數估計值被用于下一個E步計算中，這個過程不斷交替進行。

EM是一個軟隸屬函數而且權重是一個常數。EM算法的特點有它會收斂到局部極值，但不保證收斂到全局最優。而且對初值很敏感，通常需要一個好的、快速的初始化過程。EM算法適應于缺失數據不太多以及數據維數低時，因為如果數據集的維數太高的話，E步的計算很費時。最大期望經常用在機器學習和計算機視覺的數據聚類領域。

④KHM算法

KHM（The K-Harmonic Means Algorithm）算法是基于中心的迭代過程，它采用所有數據點到每個聚類中心的和平均值的和作為目標函數。KHM算法的權重是個變量，它把距離中心點遠的數據點賦以高的權重，這樣可以讓質心能夠很好的覆蓋整個數據集。KHM算法對初始值不敏感，適合處理大數據集，然而KHM算法容易陷入局部最優及簇個數需要預先指定的問題。綜合上來說它勝過K-means、FCM和EM算法。

（3）非迭代的劃分的聚類方法

另外的一種聚類算法就是非迭代的劃分的聚類方法，最常用的非迭代的算法是MacQueen的K - means算法。該算法的思想是，給定一個數據集，找到指定數量的聚類中心，然后把數據集聚類到相應的簇。該算法對初始值敏感，為了解決這個問題，可以打亂數據集中數據點的順序。一般情況下來說，迭代的算法要比非迭代的算法要高效的多。

4．其他的聚類方法

（1）最近鄰聚類算法

最近鄰聚類算法（Nearest Neighbor Clustering Algorithm）是一個用于處理多密度數據集的聚類算法，其主要思想可概括為：對于數據集中每個點，找出距離其最近的K個鄰近點，形成一個集合。然后考慮數據集中的任意兩個點，若對應于這兩個對的K個鄰近點集合交集部分的點數超過一個閾值，則將這兩個點歸于一類。SNN算法的優點是可以對不同密度和形狀的數據集進行聚類，能處理高維數據集和自動識別簇的數目。缺點是在多密度聚類和處理孤立點或噪聲方面SNN算法精度都不高，并且該算法對參數是敏感的。

（2）譜聚類

譜聚類算法首先根據給定的樣本數據集定義一個描述成對數據點相似度的親合矩陣，并且計算矩陣的特征值和特征向量，然后選擇合適的特征向量聚類不同的數據點。譜聚類算法最初用于計算機視覺、VLSI設計等領域，最近才開始用于機器學習中，并迅速成為國際上機器學習領域的研究熱點。譜聚類算法建立在譜圖理論基礎上，其本質是將聚類問題轉化為圖的最優劃分問題，是一種點對聚類算法，與傳統的聚類算法相比，它具有能在任意形狀的樣本空間上聚類且收斂于全局最優解的優點。

（3）MeanShift算法

MeanShift（均值漂移）是一種非參數概率密度估計的方法，一種最優的尋找概率密度極大值的梯度上升法，在解決計算機視覺底層過程中表現出了良好的魯棒性和較高的處理速度。MeanShift算法一般指的是一個迭代的步驟，即先算出當前點的漂移均值，移動該點到其漂移均值，然后以此為新的起始點，繼續移動，直到滿足一定的條件結束。

5．各類聚類算法比較

基于上述的分析，下面對常用聚類算法的性能從可伸縮性、發現聚類的形狀、對“噪聲”的敏感性、對數據輸入順序的敏感性、高維性和是否是硬聚類六個方面進行比較，如表2所示。

（三）關聯分析

1．關聯分析綜述

所謂關聯，反映的是一個事件和其他事件之間依賴或關聯的知識。關聯規則挖掘是大數據分析中最活躍的研究方法之一。最早是由Agrawal等人提出的稱為Apriori的關聯規則挖掘算法。最初提出的動機是針對購物籃分析問題提出的，其目的是為了發現交易數據庫中不同商品之間的聯系規則。Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。其核心是基于兩階段頻繁項集思想的遞推算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。

關聯分析幾個基本概念：

（1）關聯規則A - > B的支持度support = P（AB），指事件A與事件B同時發生的概率。

（2）關聯規則A - > B的置信度confidence = P（B ｜ A）= P（AB）/ P（A），指發生事件A的基礎上發生事件B的概率。

（3）如果事件A中包含k個元素，那么稱這個事件A為k項集，并且把滿足最小支持度閾值的事件稱為頻繁k項集。

2．Apriori關聯規則算法介紹

Apriori算法過程分為兩個步驟：第一步通過迭代，找出事務數據庫所有的頻繁項集，即支持度不低于用戶設定的閾值的項集；第二步利用頻繁項集構造出滿足用戶最小置信度的規則。具體做法是：首先，找出頻繁“1項集”的集合，該集合記作L1；然后利用L1來產生候選項集C2，再對C2中的項進行判定挖掘出L2，即頻繁“2項集”；不斷如此循環下去，直到不能找到頻繁“k項集”為止。其中每找出一層Lk都需要進行一次數據庫掃描。

經典的關聯規則數據挖掘算法Apriori算法廣泛應用于各種領域，通過對數據的關聯性進行了分析和挖掘，挖掘出的這些信息在決策制定過程中具有重要的參考價值。

（四）總結

上述的數據分析算法屬于傳統的數據挖掘方法，在實際應用中都取得了非常好的效果，例如邏輯回歸在消費者信用評分中的應用是金融領域數據分析最成功的應用案例之一。在當今大數據時代，這些傳統的數據挖掘算法也面臨數據量和運算效率的挑戰，因為傳統的數據挖掘都是假設數據在內存中存儲，在面對大數據時，這些算法存在著單位時間內處理量小、面對大量的數據時處理時間較長、難以達到預期性能等缺陷。目前這些算法也在更新換代，逐步完善來適應大數據時代的要求，例如開發K - means聚類算法的并行策略等。