“當前，信息化建設的第三波浪潮正撲面而來，信息化正在開啟以數 據的深度挖掘和融合應用為主要特征的智能化階段(信息化 3.0)。隨著互 聯網向物聯網(含工業互聯網)延伸而覆蓋物理世界，“人機物”三元融 合的發展態勢已然成型，除了人類在使用信息系統的過程中產生數據以 外，各種傳感器、智能設備也在源源不斷地產生數據，并逐漸成為數據 最重要的來源。近年來，數據資源的不斷豐富、計算能力的快速提升， 推動數據驅動的智能快速興起。大量智能應用通過對數據的深度融合與 挖掘，幫助人們采用新的視角和新的手段，全方位、全視角展現事物的 演化歷史和當前狀態，掌握事物的全局態勢和細微差別;歸納事物發展 的內在規律，預測預判事物的未來狀態;分析各種備選方案可能產生的 結果，從而為決策提供最佳選項。當然，第三次浪潮還剛剛開啟、方興 未艾，大數據理論和技術還遠未成熟，智能化應用發展還處于初級階段。 然而，聚集和挖掘數據資源，開發和釋放數據蘊含的巨大價值，已經成 為信息化新階段的共識。——梅宏

（1）按搜索策略劃分特征選擇算法

根據算法進行特征選擇所用的搜索策略，可以把特征選擇算法分為采用全局最優搜索策略、隨機搜索策略和啟發式搜索策略3類。

（2）評價函數

評價函數的作用是評價產生過程所提供的特征子集的好壞。根據其工作原理，評價函數主要分為篩選器（filter）和封裝器（wrapper）兩大類。

篩選器通過分析特征子集內部的特點來衡量其好壞。篩選器一般用作預處理，與分類器的選擇無關，常用的度量方法有相關性、距離、信息增益、一致性等。

運用相關性來度量特征子集的好壞是基于這樣假設：好的特征子集所包含的特征應該是與分類的相關度較高，而特征之間相關度較低的；運用距離度量進行特征選擇是基于這樣的假設：好的特征子集應該使得屬于同一類的樣本距離盡可能小，屬于不同類的樣本之間的距離盡可能大；使用信息增益作為度量函數的動機在于：假設存在特征子集A和特征子集B，分類變量為C，若A的信息增益比B大，則認為選用特征子集A的分類結果比B好，因此傾向于選用特征子集A。一致性指的是：若樣本1與樣本2屬于不同的分類，但在特征A和B上的取值完全一樣，那么特征子集{A, B}不應該選作最終的特征集。

篩選器由于與具體的分類算法無關，因此其在不同的分類算法之間的推廣能力較強，而且計算量也較小。

封裝器實質上是一個分類器，封裝器用選取的特征子集對樣本集進行分類，分類的精度作為衡量特征子集好壞的標準。封裝器由于在評價的過程中應用了具體的分類算法進行分類，因此其推廣到其他分類算法的效果可能較差，而且計算量也較大。使用特定的分類器，用給定的特征子集對樣本集進行分類，用分類的精度來衡量特征子集的好壞。

數據建模

數據建模是從大數據中找出知識的過程，常用的手段是機器學習和數據挖掘。所謂數據挖掘可以簡單地理解為“數據挖掘 = 機器學習+數據庫”。從商業層次來說，數據挖掘是企業按既定業務目標，對大量企業數據進行探索和分析，揭示隱藏的、未知的或驗證已知的規律性，并進一步將其模型化。從技術層次來說，數據挖掘是通過分析，從大量數據中尋找其規律的技術。

機器學習

在心理學理論中，學習是指（人或動物）依靠經驗的獲得而使行為持久變化的過程。在機器學習場景下，不同的學者有不同的理解和定義。比如西蒙（Simon）認為：如果一個系統能夠通過執行某種過程而改進它的性能，這就是學習；明斯基（M. Minsky）認為：學習是在人們頭腦中（心理內部）進行有用的變化；湯姆·米切爾（Tom M. Mitchell）認為：對于某類任務T和性能度P，如果一個計算機程序在T上以P衡量的性能隨著經驗E而自我完善，那么，我們稱這個計算機程序從經驗E中學習。根據不同的分類準則，機器學習又可以分為不同的類別，具體參見表4-2。

表4-2 不同分類準則意義下的機器學習

事實上，具體到每一個機器學習方法，根據上述不同的分類準則，可能會歸屬到一個或多個類別中。

非監督學習

在非監督學習（unsupervised learning）中，數據并不會被特別標識，學習模型是為了推斷出數據的一些內在結構。非監督學習一般有兩種思路：

（1）第一種思路是在指導Agent時不為其指定明確的分類，而是在成功時采用某種形式的激勵制度。需要注意的是，這類訓練通常會被置于決策問題的框架里，因為它的目標不是產生一個分類系統，而是做出最大回報的決定，這類學習往往被稱為強化學習。

（2）第二種思路稱之為聚合（clustering），這類學習類型的目標不是讓效用函數最大化，而是找到訓練數據中的近似點。常見的應用場景包括關聯規則的學習以及聚類等。常見算法包括關聯規則挖掘、K-Means、EM等。

關聯規則挖掘

顧名思義，關聯規則挖掘就是從數據背后發現事物（務）之間可能存在的關聯或者聯系。比如數據挖掘領域著名的“啤酒-尿不濕”的故事（這個故事的真假不論）就是典型的關聯規則挖掘發現的有趣現象。在關聯規則挖掘場景下，一般用支持度和置信度兩個閥值來度量關聯規則的相關性（關聯規則就是支持度和信任度分別滿足用戶給定閾值的規則）。所 謂 支 持 度（support）， 指 的 是 同 時 包 含X、Y的 百 分 比， 即P（X, Y）；所謂置信度（confidence）指的是包含X（條件）的事務中同時又包含Y（結果）的百分比，即條件概率P（Y|X），置信度表示了這條規則有多大程度上可信。

關聯規則挖掘的一般步驟是：首先進行頻繁項集挖掘，即從數據中找出所有的高頻項目組（frequent itemsets，滿足最小支持度或置信度的集合，一般找滿足最小支持度的集合）；然后進行關聯規則挖掘，即從這些高頻項目組中產生關聯規則（association rules，既滿足最小支持度又滿足最小置信度的規則）。

引用一個經典用例解釋上述的若干概念，使用的數據集如表4-3所示，該數據集可以認為是超市的購物小票，第一列表示購物流水ID，第二列表示每個流水同時購買的物品。

表4-3 超市購物流水

計算示例1：計算“如果orange則coke的置信度”，即P（coke|orange），從上述的購物流水數據中可以發現，含有orange的交易有4個（分別是T1、T2、T3、T4），在這4個項目中僅有兩條交易含有coke（T1、T4），因此

計算示例2：計算在所有的流水交易中“既有orange又有coke的支持度”，即P（orange, coke），從上述的購物流水數據中可以發現，總計有5條交易記錄（T1、T2、T3、T4、T5），既有orange又有coke的記錄有兩條（T1、T4），因此

上述兩個計算示例總結出的關聯規則是：如果一個顧客購買了orange,則有50%的可能購買coke。而這樣的情況（即買了orange會再買coke）會有40%的可能發生。

K-Means算法

K-Means算法是典型的基于距離的聚類算法，K-Means認為：

（1）兩個對象的距離越近，其相似度就越大。

（2）相似度接近的若干對象組成一個聚集（也可稱為“簇”）。

（3）K-Means的目標是從給定數據集中找到緊湊且獨立的簇。

K-Means中的“K”指的就是在數據集中找出的聚集（“簇”）的個數，在K-Means算法中，此“K”的大小需要事先設定，K-Means的算法流程如下：

輸入：數據集，K

輸出：K個聚集

Step-1：從N個數據對象中任意選擇K個對象作為初始聚類中心，記為

Step-2：根據每個聚類對象的均值（中心對象），計算每個對象與

這些中心對象的距離，并根據最小距離重新對相應對象進行劃分，即

Step-3：重新計算每個（有變化）聚類的均值（中心對象），即

Step-4：循環Step-2到Step-3直到每個聚類不再發生變化（收斂）為止。

K-Means聚類算法的優點集中體現在（不限于）：

（1）算法快速、簡單。

（2）對大數據集有較高的計算效率并且可伸縮。

（3）時間復雜度近于線性，適合挖掘大規模數據集。K-Means聚類算法的時間復雜度是Q (N·K·T )，其中N代表數據集中對象的數量；T代表著算法迭代的次數；K代表著簇的數目；一般而言：K<

K-Means的缺陷集中體現在（不限于）：

（1）在K-Means算法中，K是事先設定的，而K值的選定是非常難以估計的。很多時候，事先并不知道給定的數據集應該被分成多少個類別才最合適。

（2）在K-Means算法中，初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇得不好，可能無法得到有效的聚類結果。

（3）K-Means算法需要不斷地進行樣本分類調整，不斷地計算調整后的新的聚類中心，因此當數據量非常大時，算法的時間開銷是非常大的。

監督學習

監督學習（supervised learning）是指：利用一組已知明確標識或結果的樣本調整分類器的參數，使其達到所要求性能的過程，也稱為有教（導）師學習。所謂“監督”或者“有教（導）師”指的是監督學習必須依賴一個已經標記的訓練數據（訓練集）作為監督學習的輸入（學習素材）。訓練集是由若干個訓練實例組成，每個實例都是一個屬性集合（通常為向量，代表對象的特征）和一個明確的標識（可以是離散的，也可以是連續的）組成。監督學習的過程就是建立預測模型的學習過程，將預測結果與訓練集的實際結果進行比較，不斷地調整預測模型，直到模型的預測結果達到一個預期的準確率。

根據訓練集中的標識是連續的還是離散的，可以將監督學習分為兩類：回歸和分類。前者對應于訓練集的標識是連續的情況，而后者適用于訓練集的標識是離散的場景，離散的標識往往稱為類標（label）。

回歸

回歸是研究一個隨機變量Y或者一組隨機變量Y ( y1, y2, …, yn )對一個屬性變量X或者一組屬性變量X (x1, x2, …, xn )的相依關系的統計分析方法，通常稱X或者X (x1, x2, …, xn )為自變量，稱Y或者Y ( y1, y2, …, yn )為因變量。當因變量和自變量的關系是線性時，則稱為線性模型（這是最簡單的一類數學模型）。當數學模型的函數形式是未知參數的線性函數時，稱為線性回歸模型；當函數形式是未知參數的非線性函數時，稱為非線性回歸模型。

回歸分析的一般過程是通過因變量和自變量建立回歸模型，并根據訓練集求解模型的各個參數，然后評價回歸模型是否能很好地擬合測試集實例，如果能夠很好地擬合，則可以根據自變量進行因變量的預測，回歸分析的主要步驟是：

（1）尋找h函數（即hypothesis）。

（2）構造J (W )函數（又稱損失函數）。

（3）調整參數W使得J (W )函數最小。

1.? 線性回歸

線性回歸模型假設自變量（也稱輸入特征）和因變量（也稱目標值）滿足線性關系。為了便于敘述，取自變量為X (x1, x2, …, xn )，因變量為Y，訓練參數為W (w1, w2, …, wn )。

（1）目標數學模型函數定義為

（2）基于最小二乘定義損失函數為

其中Xi和Yi分別表示訓練集中第i個樣本的自變量和因變量，m表示訓練集的個數，前面乘上系數（1/2）是為了求導的時候，使常數系數消失。

（3）調整參數W使得J (W )最小，即

具體的方法有梯度下降法、最小二乘法等，下面先以梯度下降法介紹求解思路：對W取一個隨機初始值，然后不斷地迭代改變W的值使J減小，直到最終收斂（取得一個W值使得J (W )最小）。W的迭代更新規則如下

其中，ε稱為學習率（Learning Rate），j表示W的迭代次數，將J (W )代入上式得到：

此更新規則稱為最小均方LMS（least mean squares，LMS）更新策略，也稱為Widrow-Hoff learning rule，從此更新公式可以看到，W的每一次迭代都考察訓練集的所有樣本，這種更新策略稱為批量梯度下降（batch gradient descent）。還有一種更新策略是隨機梯度下降（stochastic gradient descent），其基本思路是：每處理一個訓練樣本就更新一次W。相比較而言，由于batch gradient descent在每一步都考慮全部數據集，因而復雜度比較高；隨機梯度下降會比較快地收斂。在實際情況中兩種梯度下降得到的最優解J (W )一般都會接近真實的最小值，所以對于較大的數據集，一般采用效率較高的隨機梯度下降法。

為了便于理解上述的計算流程，以一個具體的示例加以說明，示例設置如下。

整個訓練過程中各個參數變化如表4-4，為了便于閱讀，將每次迭代W的變化羅列在表中，即表中的?w1、?w2、?w3。

為了表示方便，表4-4中的數值均保留兩位小數，并且僅顯示了5步迭代的計算過程（假定0.02是可以接受的誤差），從表4-4可見，經過5步迭代后可得到回歸模型函數是

表4-4 簡單迭代過程示意

事實上，對于形如的樣本，其模型或許是，這意味著兩點：

（1）從回歸的角度而言，結果可能并不唯一。

（2）回歸結果未必是數據樣本本來的模型。

對于后者，如果有更多的學習樣本，或許會有利于結果更加逼近訓練集背后的模型，這或許也是大數據時代，為什么要更熱衷于“大”的數據，因為，唯有以更“大”的數據作為支撐，才有可能發掘數據背后的那個知識或模型。

剛才提及的更新策略是梯度下降法，需要多次迭代，相對比較費時而且不太直觀。除了梯度下降法以外，還有最小二乘法更新策略。最小二乘法的計算思路是基于矩陣論，將權值的計算從梯度下降法的迭代改為矩陣計算，經過推導可以知道

限于篇幅原因，此處不做具體的推導。無論是梯度下降法還是最小二乘法，其在擬合的過程中都是基于X (x1, x2, …, xn )中“每一個屬性的重要性（權重）是一樣”的這樣假設，而這在實際場景中未必適用（往往會產生過擬合或者欠擬合的現象），針對這種情況就產生了加權的線性回歸的思路，其本質是對各個元素進行規范化處理，對不同的輸入特征賦予了不同的非負值權重，權重越大，對于代價函數的影響越大。

特 別 值 得 一 提 的 是： 上 述 提 到 的 線 性 回 歸 模 型Y (W, X ) =

w1x1 + w2x2 + … + wn xn，所謂的線性是對參數W而言的，并非一定是輸入X (x1, x2, …, xn )的線性函數，比如可以通過一系列的基函數?i (.)對輸入

進行非線性變換，即

其中，?i (.)是基函數，可選擇的基函數有多項式、高斯函數、Sigmoid函數等，簡單介紹如下。

（1）多項式

多項式函數是由常數與自變量經過有限次乘法與加法運算得到的，定義如下

其中，ai (i = 0, 1, …, n)是常數，當n = 1時，多項式函數為一次函數。

（2）高斯函數

高斯函數的形式如下

其中，a、b及c均是實常數，且a > 0。

（3）Sigmoid函數

Sigmoid函數是一個在生物學中常見的S函數，定義如下

2.? Logistic回歸

Logistic回歸一般用于分類問題，而其本質是線性回歸模型，只是在回歸的連續值結果上加了一層函數映射，將特征線性求和，然后使用g (z)作映射，將連續值映射到一個區間內，然后在該區間內取定一個閾值作為分類邊界。根據映射函數g (z)的不同選擇，其分類性能也不同，比如如果映射函數是Sigmoid函數時，其分類結果為0和1兩類，而如果映射函數是雙曲正弦sinh函數時，其分類結果則為1和-1兩類。

以Sigmoid二值化（Sigmoid函數的特征是：當自變量趨于-∞，因變量趨近于0，而當自變量趨近于∞，因變量趨近于1）為例，為了便于后文的敘述，將Y (W, X )寫作hW (X )，Logistic回歸模型如下Logistic回歸與多重線性回歸實際上有很多相同之處，最大的區別就是他們的因變量不同，其他的基本都差不多。正是因為如此，這兩種回歸可以歸于同一個家族，即廣義線性模型（generalized linearmodel）。Logistic回歸的因變量可以是二分類的，也可以是多分類的，但是二分類的更為常用，也更加容易解釋。所以實際中最為常用的就是二分類的Logistic回歸。如果因變量是多分類的，則擴展為Softmax回歸。Softmax回歸模型是logistic模型在多分類問題上的推廣，在Softmax回歸中，類標簽Y 可以取k (k > 2)個不同的值，其推導思路與Logistic回歸相同，本文不再贅述。

分類

分類問題是機器學習研究中的一個重要問題，與回歸問題類似，分類過程也是從訓練集中建立因變量和自變量的映射過程。與回歸問題不同的是，在分類問題中，因變量的取值是離散的，根據因變量的取值范圍（個數）可將分類問題分為二分類問題（比如“好人”或者“壞人”）、三分類問題（比如“支持”、“中立”或者“反對”）及多分類問題。在分類問題中，因變量稱為類標（label），而自變量稱為屬性（或者特征）。

根據分類采用的策略和思路的不同，分類算法包括（不限于）：基于示例的分類方法（代表算法是KNN）、基于概率模型的分類方法（代表算法是樸素貝葉斯、最大期望算法EM）、基于線性模型的分類方法（代表算法是SVM）、基于決策模型的分類方法（代表算法包括：C4.5、AdaBoost、隨機森林）等，下面簡單介紹上述各種典型的分類算法的問題背景和算法思路。

1. KNN

K最近鄰（k-nearest neighbor，KNN）分類算法是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的出發點是：如果一個樣本在特征空間中的k個最相似（即特征空間中最鄰近）的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。KNN算法則是從訓練集中找到和新數據最接近的k條記錄，然后根據他們的主要類別來決定新數據的類別。該算法涉及3個主要因素：訓練集、距離或相似的度量、k的大小，算法的執行步驟如下：

輸入：訓練集（包括n個已經標注的記錄(X, X )）、k、測試用例X (x1, x2, …, xn )

輸出：測試用例的類標

Step-1：遍歷訓練集中的每個記錄，計算每個記錄屬性特征Xi(i = 1, 2, …n)與測試用例X (x1, x2, …, xn )的距離，記為Di(i = 1, 2, …n)；

Step-2：從Di (i = 1, 2, …n)中選擇最小的k個記錄（樣本）；

Step-3：統計這k個記錄（樣本）對應的類別出現的頻率；

Step-4：返回出現頻率最高的類別作為測試用例的預測類標。

KNN的思想很好理解，也容易實現。更重要的是：KNN算法不僅可以用于分類，還可以用于回歸，具體思路是：通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值（如權值與距離成反比），使得回歸更加普適。但KNN算法的不足之處在于：

（1）每次分類都需要和訓練集中所有的記錄進行一次距離或相似度的計算，如果訓練集很大，則計算負擔很重。

（2）從上述記錄流程中可以看出，如果k個近鄰的類別屬性各異，則就給分類帶來了麻煩（需要其他策略支持）。

2.樸素貝葉斯

樸素貝葉斯分類是利用統計學中的貝葉斯定理來預測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率，樸素貝葉斯分類基于的一個假設是：每個屬性之間都是相互獨立的，并且每個屬性對分類問題產生的影響都是一樣的。

貝葉斯定理由英國數學家貝葉斯（Thomas Bayes）發現，用來描述兩個條件概率之間的關系，比如P (A|B)和P (B|A)，其中P (A|B)表示事件B已經發生的前提下，事件A發生的概率，稱為事件B發生下事件A的條件概率，其基本公式是

按照乘法法則

P (A∩B) = P (A) * P (B | A) = P (B) * P (A | B)

由上式可以推導得到

例，一座別墅在過去的20年里一共發生過2次被盜，別墅的主人有一條狗，狗平均每周晚上叫3次，在盜賊入侵時狗叫的概率被估計為0.9，問題是：在狗叫的時候發生入侵的概率是多少？

用貝葉斯的理論求解此問題，假設A事件為“狗在晚上叫”，B為“盜賊入侵”，則：

（1）（計算根據：狗平均每周晚上叫3次）

（2）（計算根據：過去20年發生過2次被盜）

（3） P (A|B)=0.9。（計算根據：B 事件發生時 A 事件發生的概率是 0.9）

基于上述數據，可以很容易地計算出A事件發生時B事件發生的概率P (B | A)是

樸素貝葉斯分類的出發點是：對于給出的待分類項，求解在此項出現的條件下各個類別出現的概率，哪個最大，就認為此待分類項屬于哪個類別。為了便于描述，將事件A表示為特征屬性X (x1, x2, …, xn )，將事件B表示類標屬性Y (y1, y2, …, ym )，則樸素貝葉斯分類問題可以描述為：

對于一個給定的測試樣本的特征屬性X (x1, x2, …, xn )，求其屬于各個類標

yi(i = 1, 2, …, m)的概率P (yi | X )中的最大值，基于前面的定義可以知道

其中X表示特征屬性(x1, x2, …, xn )，由于樸素貝葉斯是基于屬性獨立性的假設（前文已提及），故

又由于P (X )是一個常數，因此只要比較分子的大小即可。樸素貝葉斯分類器的算法流程如下。

輸入：訓練集，測試用例X (x1, x2, …, xn)

輸出：測試用例X (x1, x2, …, xn)的類標

Step-1：遍歷訓練集，統計各個類別下各個特征屬性的條件概率估計，即P (xi | yi)(i = 1, 2, …, n; j = 1, 2, …, m)

Step-2：遍歷訓練集，根據上述公式，計算P (y1 | X ), P (y2 | X ), …,P (ym | X )

Step-3：如果P (yk | X ) = max{P (y1 | X ), P (y2| X), …, P (ym | X )}，則測試用例的類標是yk。

為了更好地理解上述計算流程，以一個具體的實例說明。已知一個訓練集如表4-5所示，特征屬性有兩個，分別是color和weight，其中，color的取值范圍是{0, 1, 2, 3}；weight的取值范圍是{0, 1, 2, 3, 4}。類標屬性有1個（sweet），取值范圍是{yes, no}。

表4-5 訓練集示意

測試用例是（color = 3; weight = 4），求其類標。

遍歷訓練集，可以得到：

遍歷訓練集，可以得到：

因為測試用例是（color = 3; weight = 4），所以

由于P (y1 | (x1 = 3；x2 = 4)) > P (y2 | (x1 = 3; x2 = 4))，故測試用例的類標是y1，即yes。

通過上述的計算實例可以發現，事實上，是沒有必要把P (xi | yi）的所有可能均事先計算出來，而是根據測試用例的具體樣本進行選擇性的計算即可。理論上，樸素貝葉斯分類模型與其他分類方法相比具有最小的誤差率，但其獨立性假設在實際應用中往往是不成立的，這給樸素貝葉斯分類模型的正確分類帶來了一定影響。針對這個缺點，也有一些改進的算法，此處不作羅列。