沈榮　張保文

摘要：文章主要對機(jī)器學(xué)習(xí)中經(jīng)典的四種學(xué)習(xí)方式即監(jiān)督式學(xué)習(xí)、非監(jiān)督式學(xué)習(xí)、半監(jiān)督式學(xué)習(xí)、強(qiáng)化學(xué)習(xí)進(jìn)行簡單介紹，并重點(diǎn)提出了涉及機(jī)器學(xué)習(xí)方式下常用的一些算法，主要對機(jī)器學(xué)習(xí)目前最常用的回歸算法、Apriori算法、FP Growth算法、決策樹算法的基本理論進(jìn)行闡述，并對決策樹算法的基本構(gòu)造方法進(jìn)行詳細(xì)說明。

關(guān)鍵詞：監(jiān)督式學(xué)習(xí)；回歸算法；決策樹算法；聚類算法

機(jī)器學(xué)習(xí)涉及神經(jīng)網(wǎng)絡(luò)、圖建模、人工智能、最優(yōu)化理論、模式識別、信號處理、深度學(xué)習(xí)等方面。目前機(jī)器學(xué)習(xí)較為新興領(lǐng)域就是深度學(xué)習(xí)，深度學(xué)習(xí)主要是構(gòu)建和模擬人腦進(jìn)行分析學(xué)習(xí)，使計(jì)算機(jī)能夠模擬人腦對數(shù)據(jù)進(jìn)行解釋，如圖像、聲音、和文本。由于機(jī)器學(xué)習(xí)領(lǐng)域深度學(xué)習(xí)的廣泛應(yīng)用，越來越多的學(xué)術(shù)機(jī)構(gòu)和企業(yè)已經(jīng)把目光轉(zhuǎn)向了深度學(xué)習(xí)領(lǐng)域。近年來，機(jī)器學(xué)習(xí)領(lǐng)域深度學(xué)習(xí)目前在語音識別、計(jì)算機(jī)視覺、圖像分類和自然語言方面取得了一定的成功。

1機(jī)器學(xué)習(xí)

對于機(jī)器學(xué)習(xí)，有以下基本的4種學(xué)習(xí)方式：

1）監(jiān)督式學(xué)習(xí)

監(jiān)督式學(xué)習(xí)方式是先輸入“訓(xùn)練數(shù)據(jù)”，建立預(yù)測模型，在將預(yù)測結(jié)果與實(shí)際結(jié)果比較，直到一個(gè)預(yù)期的準(zhǔn)確率。督式學(xué)習(xí)常見算法有回歸算法和反向傳遞神經(jīng)網(wǎng)絡(luò)。

2）非監(jiān)督式學(xué)習(xí)

在非監(jiān)督式學(xué)習(xí)中，聚類分析的使用最為廣泛，聚類的主要思想是將具體或抽象的對象的集合分組成多各類或簇的過程。聚類分析主要用數(shù)學(xué)的方法來研究與處理給定對象的分類，找出數(shù)據(jù)集中的相似性，從而找出有用信息。常見的聚類算法主要有基于劃分的方法、基于密度方法、基于層次方法、基于網(wǎng)格方法。

3）半監(jiān)督式學(xué)習(xí)

半監(jiān)督式學(xué)習(xí)模型主要用來預(yù)測，最常用的是支持向量機(jī)算法，該方法建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)之上，支持向量機(jī)在解決小樣本，非線性及高維模式識別中表現(xiàn)出色，目前該算法可以推廣并應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中，目前該成為了模式識別中常用的方法之一。使用SVM還可以在高維空間構(gòu)造良好的預(yù)測模型。

4）強(qiáng)化學(xué)習(xí)

在這種學(xué)習(xí)模式下，輸入數(shù)據(jù)作為對模型的反饋，常見算法包括Q-Learning以及時(shí)間差學(xué)習(xí)（Temporal difference learning）。

2機(jī)器學(xué)習(xí)常用算法歸類

我們可以根據(jù)算法的功能和形式的類似性進(jìn)行分類，常用的分類有基于樹的算法，基于神經(jīng)網(wǎng)絡(luò)的算法等等，下面介紹一些常用的算法。

2.1回歸算法

回歸算法預(yù)測的結(jié)果是連續(xù)的數(shù)值，線性回歸算法是最常用的算法之一，其使用輸入值的線性組合來預(yù)測輸出值。

常見的回歸算法還包括：最小二乘法（Ordinary Least Square），邏輯回歸（Logistic Regression），逐步式回歸（Stepwise Regression），多元自適應(yīng)回歸樣條（Multivariate Adaptive Regression Splines）以及本地散點(diǎn)平滑估計(jì)（Locally Estimated Scatterplot Smoothing）。

2.2Apriori算法

1994年，R.Afrawal和R.Srikant提出了著名的Apriori算法。Apriori算法基于頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識，使用由上至下逐層搜索的迭代方法，即從頻繁1項(xiàng)集開始，采用頻繁k項(xiàng)集搜索頻繁k+1項(xiàng)集，直到不能找到更多的頻繁項(xiàng)集為止。

Aporiori的核心步驟是連接步和剪枝步，它是一種基于水平數(shù)據(jù)分布的、寬度優(yōu)先的算法，由于使用了層次搜索的剪枝技術(shù)，使得Apfiofi算法在挖掘頻繁模式時(shí)具有較高的效率。

同時(shí)Apriori算法有兩個(gè)很大的缺點(diǎn)：一是Apriori算法是一個(gè)多趟搜索算法，每次搜索都要掃描事物數(shù)據(jù)庫，I/O開銷巨大，對于候選k項(xiàng)集ck來說，必須掃描其中的每個(gè)元素以確認(rèn)是否加入頻繁k項(xiàng)集Lk，若候選k項(xiàng)集Ck中包含n項(xiàng)，則至少需要掃描事物數(shù)據(jù)庫n次。另外Apriori算法可能產(chǎn)生龐大的候選項(xiàng)集。由于針對頻繁項(xiàng)集Lk-1的k-2連接運(yùn)算，由Lk-1產(chǎn)生的候選k項(xiàng)集Ck是呈指數(shù)增長的，如此海量的候選集對于計(jì)算機(jī)的運(yùn)算時(shí)間和存儲空間都是巨大的挑戰(zhàn)。

2.3FPGrowth算法

韓家煒等提出了一種不產(chǎn)生數(shù)據(jù)項(xiàng)集的算法——頻繁模式樹增長算法（Frequent Patter Tree Growth，F(xiàn)P增長）。FP增長是一種自底向上的探索樹，由FP樹（FP-tree）產(chǎn)生頻繁項(xiàng)集的算法。它采用分而治之的算法，將數(shù)據(jù)庫中的頻繁項(xiàng)集壓縮到一棵頻繁模式樹中，同時(shí)保持項(xiàng)集之間的關(guān)聯(lián)關(guān)系。然后將這顆壓縮后的頻繁模式樹分成一些條件子樹，每個(gè)條件子樹對應(yīng)一個(gè)頻繁項(xiàng)，從而獲得頻繁項(xiàng)集，最后進(jìn)行關(guān)聯(lián)規(guī)則挖掘。該算法高度濃縮了數(shù)據(jù)庫，同時(shí)也能保證對頻繁項(xiàng)集的挖掘是完備的。

2.4決策樹算法

決策樹（Decision Tree）最早產(chǎn)生于20世紀(jì)60年代，是一種生成分類器的有效方法，它從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。在數(shù)據(jù)處理過程中，將數(shù)據(jù)按樹狀結(jié)構(gòu)分成若干分支形成決策樹，每個(gè)分支包含數(shù)據(jù)元祖的類別歸屬共性，從決策樹的根到葉結(jié)點(diǎn)的每一條路徑都對應(yīng)著一條合取規(guī)則，整顆決策樹就對應(yīng)著一組析取表達(dá)式規(guī)則。因此，本質(zhì)上來說，決策樹就是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程。

決策樹分類算法通常分為兩個(gè)步驟：構(gòu)造決策樹和修剪決策樹。

構(gòu)造決策樹算法采用自上而下的遞歸構(gòu)造，輸入是一組帶有類別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉樹或多叉樹，其內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，樹的葉子結(jié)點(diǎn)都是類別標(biāo)記。

構(gòu)造決策樹的方法主要是根據(jù)實(shí)際需求及所處理的數(shù)據(jù)的特性，選擇類別標(biāo)識屬性和決策樹的決策屬性集，在決策屬性集中選擇最有分類標(biāo)識能力的屬性作為決策樹的當(dāng)前決策結(jié)點(diǎn)，根據(jù)當(dāng)前決策結(jié)點(diǎn)屬性取值的不同，將訓(xùn)練樣本數(shù)據(jù)集劃分為若干子集，針對上一步中得到的每一個(gè)子集，重復(fù)進(jìn)行上兩個(gè)步驟，直到最后的子集符合約束的3個(gè)條件之一，根據(jù)符合條件不同生成葉子節(jié)點(diǎn)。

由于訓(xùn)練樣本中的噪聲數(shù)據(jù)和孤立點(diǎn)，構(gòu)建決策樹可能存在對訓(xùn)練樣本過度適應(yīng)問題，從而導(dǎo)致在使用決策樹模型進(jìn)行分類時(shí)出錯(cuò)。因此，需要對決策樹進(jìn)行修剪，除去不必要的分支，也能使決策樹得到簡化。常用的決策樹修剪策略可以分為3種，基于代價(jià)復(fù)雜度的修剪（cost-complexity Pruning）、悲觀修剪（Pessimistic Pruning）、最小描述長度修剪（Minimum Descripyion Length，MDL）修剪。

3小結(jié)

本文對機(jī)器學(xué)習(xí)的四種方式進(jìn)行了介紹，對機(jī)器學(xué)習(xí)的幾種經(jīng)典算法進(jìn)行了描述，然而，機(jī)器學(xué)習(xí)的路還很漫長，在大數(shù)據(jù)云計(jì)算發(fā)展的今天，機(jī)器學(xué)習(xí)的應(yīng)用也越來越廣泛，由于機(jī)器學(xué)習(xí)領(lǐng)域中的深度學(xué)習(xí)能夠深刻刻畫海量數(shù)據(jù)中的內(nèi)在信息，未來幾年，機(jī)器學(xué)習(xí)將會被廣泛應(yīng)用于大數(shù)據(jù)的預(yù)測，而不是停留在淺層模型上，即使是通過人工神經(jīng)網(wǎng)絡(luò)建立的精度越來越高的模型，這都將促進(jìn)科技的發(fā)展，推動人工智能和人機(jī)交互的步伐。