王 慧，冀曉亮

（對外經濟貿易大學統(tǒng)計學院，北京100029）

人工智能涉及到的算法很多，普通的學習者在入門階段，很容易被各種名稱復雜、變化多樣的算法嚇退。為此，本文整理了幾類常見的計算機統(tǒng)計學習方法（機器學習算法），并闡述了原理。為了方便讀者查找和學習源代碼，所有的數(shù)據(jù)均使用UCI的鳶尾花數(shù)據(jù)集進行實現(xiàn)。機器學習算法分類如圖1所示。

1 監(jiān)督學習

在人工智能中，占比較大的問題就是監(jiān)督學習。在給定作為訓練的樣本中，每個樣本輸入的x都對應著確定的結果y，所以需要訓練一個映射模型（即x→y的映射關系f），并在給定未知樣本x′后，對結果y′進行預測。

如果預測的結果是離散值（較多情況下為類別類型，比如衣服是否滿足用戶品味、零件是否合格等），則稱其為分類問題；如果預測結果是連續(xù)值（比如股票價格、環(huán)境溫度和濕度變化、人的體重變化等），則叫作回歸問題。

用于解決分類問題的最經典算法包括樸素貝葉斯、支持向量機、邏輯回歸等算法，還有用于解決回歸問題的邏輯回歸、線性回歸等算法。

2 非監(jiān)督學習

對于某些問題，樣本中并沒有給出標準/非標準答案，只是給出了一些樣本或數(shù)據(jù)，需要自己從樣本中提取某些通用的規(guī)則，這種問題稱為非監(jiān)督學習。聚類算法、關聯(lián)規(guī)則等諸多的機器學習算法均歸于非監(jiān)督學習。按照以上介紹的順序，使用經典的鳶尾花數(shù)據(jù)集，將這些算法的應用和原理作詳細介紹。以下按照監(jiān)督學習中的分類和回歸、非監(jiān)督學習中的聚類降維和關聯(lián)分析的順序進行闡述。

3 幾種用于人工智能的核心算法

首先探討描述幾種經典的機器學習種算法：KNN、決策樹、邏輯回歸（線性回歸）、樸素貝葉斯、SVM、隨機森林、PCA、Kmeans、Boosting。

另外，提及人工智能，筆者們也對神經網(wǎng)絡的深度學習算法——BP算法，作了一些探索。

3.1 KNN算法（K近鄰算法）

KNN算法中的距離常通過歐氏距離或者夾角余弦來計算。但在大數(shù)據(jù)的工程應用中，因為歐氏距離的運算量較大，可以采用曼哈頓距離等來代替（事實上，工程中為了減少運算量級經常這么做）。KNN主要分為以下幾個步驟：①距離測量。計算給定對象與訓練集中其他對象之間的距離。②找鄰居。找到最近距離的K個訓練對象。③作出分類。根據(jù)K個近鄰歸屬的主要類別，來對測試對象分類。

用人工智能領域常用的Python語言對UCI數(shù)據(jù)集中的鳶尾花數(shù)據(jù)進行分析和計算。因為這套數(shù)據(jù)最容易獲取，且最具有代表性。

按照統(tǒng)計可看到，鳶尾花的數(shù)據(jù)有4個維度（花瓣和花萼的長和寬），這4個維度都可以用來進行

KNN分類。鳶尾花數(shù)據(jù)4個維度的KNN分類如圖2所示。

KNN算法運行結果如圖3所示。

3.2 回歸算法

回歸算法常見的有線性回歸和邏輯回歸算法。線性回歸根據(jù)歷史數(shù)據(jù)擬合一條模擬線段，從而預測未知數(shù)據(jù)的分類或近似數(shù)值。邏輯回歸算法思想類似，是一種廣義的線性回歸模型。但其使用S型曲線來擬合數(shù)據(jù)，將線性函數(shù)的結果映射到了Sigmoid函數(shù)中。Sigmoid函數(shù)常被用作神經網(wǎng)絡的激活函數(shù)，變量映射的值域是（0，1）之間，如圖4所示。

圖4 Sigmoid函數(shù)圖

事實上鳶尾花種類有3種，如圖5所示。

從圖5中可以看到，圓點種類的setosa鳶尾花較為顯著地區(qū)別于X形種類和十字形種類的versicolor和virginica鳶尾花。

圖5 鳶尾花種類圖

而選擇使用Logistic Regression分類器，由于Iris數(shù)據(jù)集涉及到3個目標分類問題，邏輯回歸模型是二分類模型，用于二分類問題。所以，它也可以被用于多分類，被推廣為多項邏輯回歸模型（multi-nominal logistic regression model），公式如下：

式（1）（2）中：k=1，2，…，K－1；K為分類的種類集合。

使用邏輯回歸對鳶尾花進行分類后，其結果如圖6所示。

如圖6所示，選取花萼的長和寬作為特征值，經過邏輯回歸后劃分為3個區(qū)域，左上角部分為圓點種類，對應setosa鳶尾花；右上角部分為十字形種類，對應virginica鳶尾花；中間下部分為X形種類，對應versicolor鳶尾花。散點圖為各數(shù)據(jù)點真實的花類型，3個區(qū)域的數(shù)據(jù)點所預測出的花的類型與訓練數(shù)據(jù)的真實結果是基本相符的，部分鳶尾花出現(xiàn)了交叉。這個分類結果顯然達不到所想要的效果。為此，筆者們選取花萼和花瓣的長度為特征再次運行程序，得到的結果如圖7所示。

圖6 選取花萼的長和寬作為特征分類圖

圖7 選取花萼和花瓣的長度為特征分類圖

從圖7中可以看到，選取不同的特征對分類器的影響顯著。

3.3 決策樹

決策樹同時可以用來解決分類或回歸問題，分別稱之為分類樹或回歸樹。其中，分類樹的輸出是一個標量，而回歸樹的一般輸出為一個實數(shù)。

通常情況下，決策樹利用損失函數(shù)最小的原則建立模型，然后再利用該模型進行預測。決策樹學習通常包含3個階段：特征選擇、樹的生成、樹的修剪。

3.3.1 特征選擇

建立決策樹之前最重要的一步就是特征選擇。如果特征是隨機選擇的，那么決策樹的學習效率會大大降低。舉例說明，銀行采用決策樹來解決信用卡審批問題，判斷是否向某人發(fā)放信用卡可以根據(jù)其年齡、工作單位、是否有不動產、歷史信貸情況等特征決定。而選擇不同的特征，后續(xù)生成的決策樹就會不一致，這種不一致最終會影響到決策樹的分類效率。

通常在選擇特征時，會考慮到兩種不同的指標，分別為信息增益和信息增益比。為此需要提到信息論中的另一個十分常見的名詞——熵。

熵（Entropy）是表示隨機變量不確定性的度量。簡單來講，熵越大，隨機變量的不確定性就越大。而特征A對于某一訓練集D的信息增益g（D，A）定義為集合D的熵H（D）與特征A在給定條件下D的熵H（D/A）之差。

簡單來講，每一個特征針對訓練數(shù)據(jù)集的前后信息變化的影響是不一樣的，信息增益越大，即代表這種影響越大，而影響越大，就表明該特征更加重要。

3.3.2 生成算法

當了解信息增益的概念之后，就可以學習決策樹的生成算法了。其中，最經典的就數(shù)QUINLAN提出的ID3算法，這個算法的核心理論即源于上面提到的信息增益。

ID3算法建立決策樹是通過遞歸的方法。首先從根節(jié)點開始，為節(jié)點計算每個個體特征的信息增益，選擇信息增益最大的特征作為節(jié)點特征。接下來，對特征施加判斷條件以建立子節(jié)點。然后用信息增益來判斷子節(jié)點，直到所有特征的信息增益很小或沒有特征為止。就這樣，一顆完整的決策樹被一步步建立起來。

每個對象首先被視為一個簇，隨后這些原子簇被合并成越來越大的簇，直到滿足某個終端條件為止。

決策樹算法在實際的使用過程中有兩個技巧，一個是要盡量減少樹的高度，這樣可以減少運算的數(shù)量級。為此要把強過濾條件盡量放在頂層。另一個技巧在于減枝，減枝在同等數(shù)據(jù)規(guī)模的情況下可以大幅減少運算次數(shù)。為了達到這個目的，在通常情況下，可以把復雜邏輯的判斷盡量放在第一步去運算。

除了從信息增益演化而來的ID3算法，還有一種常見的算法叫C4.5。C4.5算法同樣由QUINLAN發(fā)明，但它使用了信息增益比來選擇特征，這被看成是ID3算法的一種改進。

D3和C4.5算法簡單高效，但是他們均存在一個缺點，那就是用“完美去造就了另一個不完美”。這兩個算法從信息增益和信息增益比開始，對整個訓練集進行的分類，擬合出來的模型針對該訓練集是非常完美的。但是，這種完美就使得整體模型的復雜度較高，而對其他數(shù)據(jù)集的預測能力就降低了。

1984年，BREIMAN提出了CART算法，使這個過程變得可以一步到位。CART算法本身就包含了決策樹的生成和修剪，并且可以同時被運用到分類樹和回歸樹。這是CART算法和ID3及C4.5算法的最大區(qū)別。

使用決策樹預測鳶尾花數(shù)據(jù)集的代碼較為簡單，不做贅述。代碼運行結果如表1所示。決策樹如圖8所示。

圖8 決策樹

表1 決策樹運行結果

3.4 SVM

支持向量機（support vector machines）是一種二分類模型，定義為特征空間中間隔最大的線性分類器。SVM還包括核技巧，這使得它本質上是一個非線性分類器。

SVM的學習策略是間隔最大化，可以形式化為求解凸二次規(guī)劃問題，也可等價于正則化的合頁損失函數(shù)的最小化問題。SVM的學習算法是求解凸二次規(guī)劃的最優(yōu)化算法。

基于這個原則，SVM算法認為分類器A在性能上優(yōu)于分類器B，其依據(jù)是A的分類間隔要大于B，如圖9所示。

圖9 分類器A、B結果圖

這里涉及到一個“分類間隔”的問題，它是SVM獨有的概念。如果決策面的方向保持不變，并且在移動決策面時不會發(fā)生樣本錯分，則在決策面的兩側會發(fā)現(xiàn)兩個極限位置（如果超過該位置，就會發(fā)生錯分），如圖9中虛線所示。

決策面的方向和離原決策面最近的幾個樣本的位置決定了虛線的位置，而位于兩條平行虛線正中間的分界線，是在當前決策面方向不變的前提下的最優(yōu)決策面。兩條虛線之間的垂直距離就是當前最優(yōu)決策面的分類間隔。顯然每個方向都有一個最優(yōu)決策平面可以正確地分離數(shù)據(jù)集（有些方向無論如何移動決策面的位置也不可能將兩類樣本完全分開），不同方向的最優(yōu)決策面的分類間隔是不同的，具有“最大間隔”的決策面才是SVM正在找尋的最優(yōu)解。最優(yōu)解對應的兩側虛線所穿過的樣本點，就是SVM中的支持樣本點，稱為“支持向量”。

SVM算法的步驟如下。

3.4.1 決策面方程

為了便于理解，以二維平面方程為例進行闡述。

給定線性方程：y=ax＋b。

將原來的x軸變成x1軸，y軸變成x2軸，于是公式中的直線方程會變成：x2=ax1＋b，即：ax1＋（-1）x2＋b。

在更高維的向量中，其決策面方程也如上式，只是參數(shù)更多。

3.4.2 分類間隔的計算

將分類間隔方程中的xi給定分類yi，如果分類正確，則滿足：

假設決策面正好處于間隔區(qū)域的中軸線上，并且相應的支持向量對應的樣本點到決策面的距離為d，則式（4）變換為：

3.4.3 約束條件

引入分類間隔后，將約束條件描述為：

把類別標簽yi和兩個不等式左邊相乘，形成SVM統(tǒng)一的表述：

限于篇幅，SVM最優(yōu)化問題的求解我們不過多深入研究，在實際的應用中，不同的分類器和最優(yōu)化方法對結果會有較大的影響。利用SVM對鳶尾花數(shù)據(jù)進行分類后，其展示結果如圖10所示。

圖10 SVM對鳶尾花數(shù)據(jù)分類結果圖

3.5 隨機森林、Boosting和PCA

3.5.1 隨機森林

嚴格來講，隨機森林不是一種算法，而是一種方法。隨機森林通過以下算法來構建每棵樹：①訓練樣本的個數(shù)用N來表示，特征數(shù)目用M來表示；②輸入特征數(shù)m，用于確定決策樹中某個節(jié)點的決策結果，其中m應該遠小于M；③從N個訓練樣本中，使用有放回的方式抽樣N次，組成一個訓練集（也就是bootstrap取樣），然后使用未抽到的樣本進行預測，評估其誤差；④對于每個節(jié)點，隨機選取m個特征，基于這些特征確定決策樹中每個節(jié)點的決策，根據(jù)這m個特征，計算出最佳分裂方式；⑤每棵樹最后都將完全長成而無需剪枝，在構建成一棵正常的樹狀分類器后，被采用的概率非常大。采用隨機森林對鳶尾花數(shù)據(jù)進行分類后，其展示結果如圖11所示。

圖11 隨機森林分類結果圖

3.5.2 Boosting

Boosting與隨機森林的思想類似，其思想是由迭代使用弱學習分類器組成，并將其結果加入一個最終的成強學習分類器。加入的過程中，通常根據(jù)它們的分類準確率給予不同的權重。加和弱學習者之后，數(shù)據(jù)通常會被重新加權，來強化對之前分類錯誤數(shù)據(jù)點的分類。

Boosting主要是通過對樣本集的操作獲得樣本子集，然后用弱分類算法在樣本子集上訓練生成一系列的基分類器。其實際使用效果和隨機森林類似但略好。

3.5.3 PCA

PCA是一種數(shù)據(jù)降維的算法。降維是一種對高維度特征數(shù)據(jù)預處理的方法。降維是將高維度的數(shù)據(jù)保留下最重要的一些特征，去除噪聲和不重要的特征，從而實現(xiàn)提升數(shù)據(jù)處理速度的目的。

降維的算法非常多，比如主成分分析（PCA）、奇異值分解（SVD）、獨立成分分析（ICA）和因子分析（FA）。其中最常用的降維算法就是PCA。

PCA最重要的思想是把n維特征映射到k維，這是一個全新的正交特征，即主成分，是在原有n維特征的基礎上重新構造出來的。

PCA的步驟：①定義輸入向量Xn，假如要降到k維，先要將每一位特征減去各自的平均值，這一步稱為去平均值（也叫去中心化）；②計算協(xié)方差矩陣，即（這里除或不除樣本數(shù)量n或n－1都不會影響求出的特征向量）；③通過分解特征值的方法得到協(xié)方差矩陣的特征值和特征向量；④從大到小排序特征值，從中選出最大的k個，分別取對應的k個特征向量作為行向量，形成特征向量矩陣P；⑤將數(shù)據(jù)轉換為由k個特征向量構成的新空間，即Y=PY。

將鳶尾花的特征數(shù)據(jù)降到二維，并分類，可以得到如圖12所示的結果。

圖12 鳶尾花特征數(shù)據(jù)降維分類結果圖

3.6聚類算法和Kmeans、DBSCAN和AGNES

數(shù)據(jù)聚類算法可以分為結構性聚類和分散性聚類。結構性聚類用以前使用過的聚類器分類，分散型聚類則一次確定所有分類。結構性聚類算法可以從上至下或者從下至上地進行計算。從下至上算法從每個對象作為單獨分類開始聚類，不斷融合相近對象。而從上至下算法則把所有對象作為一個整體分類，而后逐漸拆分。另外還有分布式聚類算法，這種算法是一次確定要產生的類別。分布式聚類算法也試用于從下至上的算法?；诿芏鹊木垲愃惴ㄗ钤鐬榱送诰蛴腥我庑螤钐匦缘念悇e。該算法把類別視為數(shù)據(jù)集中大于某閾值的一個區(qū)域，DBSCAN和OPTICS是兩個典型的密度聚類算法。

3.6.1 分散性聚類（Kmeans）

Kmeans是迭代求解的聚類算法，其步驟是隨機選取K個聚類中心，然后計算出每個對象與每個聚類中心的距離，把每個對象分配到離它距離最短的聚類中心。該中心和分配的對象代表一個聚類。每分配一個樣本，聚類中心會根據(jù)現(xiàn)有的對象被重新計算。迭代這個過程直到滿足某個終止條件。終止條件可以是沒有對象被重新分配給不同的聚類，沒有聚類中心再變化，誤差平方和局部最小等。

算法流程：①選擇聚類的個數(shù)k；②任意產生k個聚類，然后確定聚類中心，或者直接生成k個中心；③對每個點確定其聚類中心點；④再計算其聚類新中心；⑤重復上述幾個步驟，直到能滿足收斂要求（通常確定的中心點不再改變）。Kmeans聚類前后效果如圖13、14所示。

圖13 原始圖

圖14 Kmeans聚類結果圖

3.6.2 結構性聚類（層次聚類）

3.6.2.1 凝聚層次聚類：AGNES算法（自下而上）

先將每個樣本對象作為一個簇，合并這些對象為越來越大的簇，直到滿足某個終止條件。

3.6.2.2 分裂層次聚類：DIANA算法（自上而下）

首先把所有的樣本對象放到一個簇中，逐步細分成更小的簇，直至滿足某個終止條件。

演示代碼采用AGNES算法聚類鳶尾花數(shù)據(jù)。運行結果如下。

各個簇的樣本數(shù)目：

聚類結果：

AGNES算法聚類結果如圖15所示。

圖15 AGNES算法聚類結果圖

3.6.3 密度聚類與DBSCAN算法

需要兩個參數(shù)：ε（eps）和形成高密度區(qū)域所需要的最少點數(shù)（minPts）。

它由任意一個未被訪問的點開始，探索該點的ε-鄰域，如果ε-鄰域內有足夠的點，則建立新的聚類，否則該點被標簽為雜音。注意之后該點可能被發(fā)現(xiàn)在其他點的ε-鄰域，如果該ε-鄰域有足夠的點，屆時這個點會被加入到該聚類中。DBScan算法的程序運行結果如圖16所示。

圖16 DBScan算法結果圖

3.7 神經網(wǎng)絡、深度學習及其他

談到人工智能，不得不談到人工神經網(wǎng)絡（artificial neural networks，ANN）。它出現(xiàn)于1940年之后，是由許多可調的神經元連接權重組成，具有大規(guī)模并行處理、分布式信息存儲以及良好的自組織自學習能力，廣泛應用于信息處理、模式識別、智能控制和系統(tǒng)建模等領域。

BP（Back Propagation）神經網(wǎng)絡是一種按誤差逆?zhèn)鞑ニ惴ㄓ柧毜亩鄬忧梆伨W(wǎng)絡。BP的基本思想是：信號正向傳播，誤差反向傳播。它適合用在小型分層的神經網(wǎng)絡中。鳶尾花用三層BP神經網(wǎng)絡的運行結果顯示，對鳶尾花種類的識別正確率達到了100%。

本文使用鳶尾花的數(shù)據(jù)集對幾類人工智能算法做了概要的介紹。介于篇幅，對更深層次的計算技巧和算法發(fā)展沒有深入探索。這些算法當然不僅僅用于分析數(shù)據(jù)，而是可以更深層次地用在包含人工智能在內的各類計算機領域或數(shù)據(jù)領域。謹以本文供讀者參考。