機器學習學習方式及其算法探討

沈榮　張保文

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

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

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

1機器學習

對于機器學習，有以下基本的4種學習方式：

1）監(jiān)督式學習

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

2）非監(jiān)督式學習

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

3）半監(jiān)督式學習

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

4）強化學習

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

2機器學習常用算法歸類

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

2.1回歸算法

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

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

2.2Apriori算法

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

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

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

2.3FPGrowth算法

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

2.4決策樹算法

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

決策樹分類算法通常分為兩個步驟：構造決策樹和修剪決策樹。

構造決策樹算法采用自上而下的遞歸構造，輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹，其內部結點是屬性，邊是該屬性的所有取值，樹的葉子結點都是類別標記。

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

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

3小結

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