1 前言

這一章我們將會開始討論將視覺轉(zhuǎn)化為感知的機(jī)器，換句說該機(jī)器將視覺輸入轉(zhuǎn)化為有意義的視覺語義。

前幾章中我們已經(jīng)討論了如何將2維，或者3維傳感器收集到的信息轉(zhuǎn)化為特征、類簇、或者幾何信息。在接下來的幾章中，我們會將這些信息轉(zhuǎn)化為對場景或者目標(biāo)模型的感知，即判斷機(jī)器看到的是什么，它相對于相機(jī)的位置。

在本章中我們將會討論機(jī)器學(xué)習(xí)的基礎(chǔ)，焦點主要在于機(jī)器學(xué)習(xí)是什么。我們也將看到OpenCV提供的一些簡單機(jī)器學(xué)習(xí)能力，這是我們?nèi)胬斫鈾C(jī)器學(xué)習(xí)基本理論的一個很好切入點。在下一章中我們會看到更多現(xiàn)代機(jī)器學(xué)習(xí)方法在OpenCV中的實現(xiàn)細(xì)節(jié)。機(jī)器學(xué)習(xí)和很多其他模塊一樣，通過opencv_contrib提供擴(kuò)展能力，這在本系列后續(xù)文章后記B中有更詳細(xì)的介紹。如需了解更多細(xì)節(jié)，請參考源代碼倉庫內(nèi)的深度神經(jīng)網(wǎng)絡(luò)模塊cnn_3dobj和dnn。

2 什么是機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)(Machine Learning, ML)的目標(biāo)是將數(shù)據(jù)轉(zhuǎn)化為信息。通過一定數(shù)據(jù)集的學(xué)習(xí)后，我們想讓機(jī)器具備回答和數(shù)據(jù)相關(guān)的問題，例如其余那部分?jǐn)?shù)據(jù)和該數(shù)據(jù)最相似，圖像中是否存在汽車，什么廣告能夠得到用戶回應(yīng)?？紤]到成本因素，這個問題可以是，在我們利潤最高的一系列產(chǎn)品中，如果我們通過廣告推銷，用戶最可能購買的是哪一個。機(jī)器學(xué)習(xí)從該數(shù)據(jù)中提取規(guī)則或者模式將數(shù)據(jù)轉(zhuǎn)化為信息。

機(jī)器學(xué)習(xí)是一個很寬的話題，OpenCV主要處理統(tǒng)計機(jī)器學(xué)習(xí)而不是如貝葉斯網(wǎng)絡(luò)，馬爾可夫隨機(jī)場，和圖形模型這樣的主題。這里推薦一些比較好的機(jī)器學(xué)習(xí)相關(guān)文獻(xiàn)?！禩he Elements of Statistical Learning: Data Mining, Inference and Prediction》、《Pattern Recognition and Scene Analysis》、《Pattern Classification》、《Pattern Recognition and Machine Learning》、《Evaluating mapreduce for multi-core and multiprocessor systems》、《Map-reduce for machine learning on multicore》

2.1 訓(xùn)練集和測試集

我們感興趣的機(jī)器學(xué)習(xí)處理的是原始的數(shù)值數(shù)據(jù)，例如溫度值，股票價格，和顏色強(qiáng)度。這些數(shù)據(jù)通常被預(yù)處理成特征，例如我們可能有一個包含1萬張人臉圖像的數(shù)據(jù)庫，對人臉應(yīng)用邊緣檢測，然后手機(jī)入邊緣方向，邊緣強(qiáng)度，以及邊緣和中心的距離等特征。對于每張臉，我們我們可能能得到500個這樣的特征值，或者說是一個包含500個元素的特征向量（Feature Vector）。接下來我們可以使用機(jī)器學(xué)習(xí)技術(shù)根據(jù)這些采集到的數(shù)據(jù)重建某種類型的模型。如果我們想要知道這些人臉能夠被分成幾組(寬的、窄的等)，聚類算法（Clustering Algorithm）就是最好的選擇。如果我們想要根據(jù)例如在人臉圖像上檢測到的邊緣模式預(yù)測對應(yīng)人的年齡，則分類器算法（Classifier Algorithm）將會是合適的選擇。為了實現(xiàn)我們的目標(biāo)，機(jī)器學(xué)習(xí)算法根據(jù)該目標(biāo)不斷的分析收集到的特征，然后調(diào)整權(quán)重、閾值和其他模型參數(shù)從而得到最佳性能。這個為了滿足某個目標(biāo)的調(diào)參過程就稱為機(jī)器學(xué)習(xí)。

在本文撰寫的時候OpenCV還沒有包含深度學(xué)習(xí)，因為盡管它們的發(fā)展前景比較好，但是這些技術(shù)仍然太新，還不能確定到底應(yīng)該包含哪些內(nèi)容。然而卷積神經(jīng)網(wǎng)絡(luò)《Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position》、《Neural Networks: Tricks of the Trade》、《Convolutional neural network committees for handwritten character classification》絕對是深度學(xué)習(xí)未來的重要內(nèi)容之一。

了解機(jī)器學(xué)習(xí)的性能總是非常重要的，這也是一個非常精細(xì)的任務(wù)。傳統(tǒng)上將可用數(shù)據(jù)集分為一個較大的訓(xùn)練集和一個較小的測試集，在我們的例子中將1萬個人臉數(shù)據(jù)分為9千個樣本的訓(xùn)練集和1千個樣本的測試集。接下來在訓(xùn)練集上運行分類器，使用數(shù)據(jù)特征向量學(xué)習(xí)年齡預(yù)測模型。當(dāng)學(xué)習(xí)完成后就可以在測試集的圖像上廁所年齡預(yù)測分類器。

測試集不會用于訓(xùn)練，并且我們不會講測試集的標(biāo)簽暴露給分類器。只有在訓(xùn)練完成后，才會對1000個樣本的測試集中的每一張人臉圖片運行分類器，并記錄基于特征向量預(yù)測到的年齡和實際年齡之間匹配度。如果分類器的預(yù)測結(jié)果很糟糕，我們可能需要在數(shù)據(jù)中添加一些新的特征或者考慮使用不同類型的分類器。這一章中我們將會看到很多類型的分類器，以及訓(xùn)練它們的多種算法。

如果分類器的預(yù)測質(zhì)量不錯，我們現(xiàn)在就有了一個具有潛在價值的模型，我們可以將它部署在真實世界的數(shù)據(jù)上。可能這個系統(tǒng)將會被用在基于年齡設(shè)置視頻游戲的行為這種場景中。當(dāng)玩家準(zhǔn)備游玩時，他的臉部圖像將會被提取出500個特征，如邊緣方向，邊緣強(qiáng)度，距離中心的距離等。分類器就會處理這些數(shù)據(jù)，并預(yù)測用戶的年齡并根據(jù)該值設(shè)置游戲的游玩行為。當(dāng)分類器被部署后，它處理的人臉圖像是之前并未見過的，并根據(jù)在訓(xùn)練集中學(xué)習(xí)到的信息作出決策。

最后，當(dāng)部署一個分類系統(tǒng)時，我們通常還會使用一個驗證數(shù)據(jù)集。有些時候在最后測試整個系統(tǒng)是一項艱巨的任務(wù)，在講分類器提交到最終測試之前我們經(jīng)常想要對一些參數(shù)進(jìn)行調(diào)整。為了處理這個問題，我們可以將1萬個臉部圖像數(shù)據(jù)集分為3部分，分別是包含8000個樣本的訓(xùn)練集，1000個樣本的驗證集，1000個樣本的測試集。通過訓(xùn)練集完成學(xué)習(xí)后，可以在驗證集上預(yù)測試分類器的效果。當(dāng)對驗證集上的性能感到滿意時，我們再到測試集合上運行分類器做最終校驗。

你可能想到一種相較于直接從9000個樣本的訓(xùn)練集中分離出8000個樣本的訓(xùn)練集和1000個樣本的測試集更好的策略。的確，這種場景下的標(biāo)準(zhǔn)實踐其實是多次重復(fù)這種分組策略。在本例中重復(fù)9次，每一次都抽取其中1000個樣本作為驗證集，另外8000個樣本訓(xùn)練集。這個過程稱為k次折疊交叉驗證(k-fold cross-validation)。這里的k次折疊意味著k次分組，這里k的值為9。

2.2 有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)

數(shù)據(jù)有時時候是沒有標(biāo)簽的，例如我們可能只是想基于邊緣檢測的信息觀察人臉圖像自然的被標(biāo)記為某一類。有時候數(shù)據(jù)是有標(biāo)簽的，例如每張圖片中人物特征的年齡。這意味著機(jī)器學(xué)習(xí)數(shù)據(jù)的時候可能是需要受到監(jiān)督(Supervised)的，例如需要利用教學(xué)信號或者標(biāo)簽，和數(shù)據(jù)特征向量協(xié)同工作。當(dāng)然也有可能是不需要監(jiān)督的(Unsupervised)，即機(jī)器學(xué)習(xí)算法無法獲取這樣的標(biāo)簽，并且我們期待算法自己能夠弄清數(shù)據(jù)的結(jié)構(gòu)。下圖演示了這個過程。

有監(jiān)督學(xué)習(xí)可以用于分類(Categorical)，例如將名字和臉關(guān)聯(lián)起來，或者為數(shù)字加上一個有序的或者是數(shù)值化(Numeric or Ordered)的標(biāo)簽，例如年齡。當(dāng)數(shù)據(jù)的標(biāo)簽是名字的時候，這種類型被稱為分類(Classification)，當(dāng)數(shù)據(jù)是數(shù)值時，這種類型被稱為回歸(Regression)，回國通過一些類別活著數(shù)值輸入你和一個數(shù)值輸出。

監(jiān)督學(xué)習(xí)也有一些灰色地帶，包括標(biāo)簽和數(shù)據(jù)向量的一一匹配，另外它也可能由加強(qiáng)學(xué)習(xí)(Reinforcement Learning)組成，有些時候也稱為延遲學(xué)習(xí)(Deferred Learning)。在加強(qiáng)學(xué)習(xí)中，數(shù)據(jù)標(biāo)簽(也被稱為獎勵(Reward)與懲罰(Punishment))在單個數(shù)據(jù)向量被觀察到后較長時間才會生效。當(dāng)一個老鼠在迷宮中尋找食物的時候，它可能需要經(jīng)歷一系列的轉(zhuǎn)彎才能最終找到食物，然后獲得獎勵。這個獎勵一定會以某種方式反向影響以后它在尋找食物之前的行為與見解。加強(qiáng)學(xué)習(xí)以相同的方式工作，系統(tǒng)接收到一個延時信號，可能是一個獎勵活著是一個懲罰，嘗試推導(dǎo)出一個在未來運行時應(yīng)當(dāng)采取的行為，更正式的被稱為策略。在這個場景下，學(xué)習(xí)到的策略實際上是做決策的方式，例如在穿越迷宮時在每一步應(yīng)該選擇哪條路。有監(jiān)督學(xué)習(xí)同樣可能只有部分標(biāo)簽，其中的一些標(biāo)簽可能缺失，這也被稱為半監(jiān)督學(xué)習(xí)(Semisupervised Learning)。也可能存在一些噪聲，提供的某些標(biāo)簽可能是錯誤的。大多數(shù)機(jī)器學(xué)習(xí)算法只能狗處理一種或者兩種上述場景，例如某個算法可能能夠處理分類，但是不能給處理回歸，某個算法可能能夠處理半監(jiān)督學(xué)習(xí)，但是不能處理加強(qiáng)學(xué)習(xí)，某個算法可能能夠處理數(shù)值數(shù)據(jù)，但是不能處理分類數(shù)據(jù)等。

與之相比，通常我們沒有數(shù)據(jù)的標(biāo)簽，并且更想觀察是否數(shù)據(jù)會被自然分為多個組。這種無監(jiān)督學(xué)習(xí)的算法通常被稱為聚類算法(Clustering Algorithms)。在這種情況下，算法的目標(biāo)時將未標(biāo)記的相”近”(預(yù)先定義的度量標(biāo)準(zhǔn)或者可能是通過學(xué)習(xí)得到的概念)的數(shù)據(jù)向量分為一組。我們可能只是想看這些人臉是如何分布的，它們是否構(gòu)成了瘦、寬、長或者短的臉這樣幾組。如果我們正在研究癌癥數(shù)據(jù)，是否可以根據(jù)不同的化學(xué)信號將它們分入到不同的組內(nèi)。無監(jiān)督學(xué)習(xí)的聚類數(shù)據(jù)通常也被用于構(gòu)造特征向量供高層有監(jiān)督分類器使用。我們可能首先將臉部圖像聚合成幾類(寬的、窄的、長的和短的)，然后將它們作為輸入，再結(jié)合一些其他數(shù)據(jù)，入平均聲音頻率，從而預(yù)測當(dāng)事人的性別。

常見的兩個機(jī)器學(xué)習(xí)任務(wù)，分類和聚類，和計算機(jī)視覺中最常見的兩個任務(wù)，識別和分割，有著一些共通之處。有時我們將其稱之為“什么”(what)和“哪里”(where)。也就是說我們通常想要計算機(jī)對圖像中的某個目標(biāo)模型命名(識別、或者是確定這是什么)，也想知道該模型出現(xiàn)的位置(分割、或者是確定它在哪里)。因為計算機(jī)視覺如此頻繁的利用到機(jī)器學(xué)習(xí)的知識，OpenCV在ML庫中包含了很多強(qiáng)大的機(jī)器學(xué)習(xí)算法，可以在目錄…/opencv/modules/ml和…/opencv/modules/flann中找到。

OpenCV中的機(jī)器學(xué)習(xí)代碼是通用的，也就是說盡管這些代碼在處理視覺任務(wù)是非常有用，但是它們的使用并不限于視覺。使用合適的函數(shù)甚至可以研究基因組序列。當(dāng)然我們這里主要關(guān)注的還是使用圖像中提取到的特征向量進(jìn)行目標(biāo)識別。

2.3 生成式和判定式模型

現(xiàn)在已經(jīng)有很多算法用于分類和聚類，OpenCV提供了一些最有用的當(dāng)下可用的統(tǒng)計機(jī)器學(xué)習(xí)方法?；诟怕实臋C(jī)器學(xué)習(xí)方法，如貝葉斯網(wǎng)絡(luò)（Bayesian Networks）或者圖形模型（Graphical Models）在OpenCV中支持得沒有那么好，部分原因是這些方法都很新，并且正處于活躍的發(fā)展階段。OpenCV傾向于支持判定式算法（Discriminative Algorithms），該算法計算的是給定數(shù)據(jù)標(biāo)簽的概率P(L｜D)，而不是傾向于支持生成式算法（Generative Algorithms），該算法計算的是給定標(biāo)簽的數(shù)據(jù)的分布P(D｜L)。盡管這兩者之間的區(qū)別并不總是很清晰，但是判定式模型對于給定做出預(yù)測的場景工作很好，而生成式模型善于給出關(guān)于數(shù)據(jù)的更強(qiáng)大的表現(xiàn)，或者有條件的合成新的數(shù)據(jù)。在腦海想象一下大象的畫面，你將會根據(jù)條件“大象”想像出很多數(shù)據(jù)。

因為生成式模型是對數(shù)據(jù)的形成過程建模，盡管有時得到的模型并不一定準(zhǔn)確，因此通常它更容易被解釋。判定式機(jī)器學(xué)習(xí)通常會基于一些可能看上去是隨意選取的閾值做出決策。例如，假定在場景中路上的一小塊區(qū)域由于其顏色中的紅色分量低于125被識別出來，但是這意味著紅色分量等于126的地方一定不是路嗎？這個問題很難被解釋。而生成式的模型通常處理的是給定類別情況下的數(shù)據(jù)條件分布，因此能夠很容易感覺出它與實際的分布是否相似。

2.4 OpenCV中的機(jī)器學(xué)習(xí)算法

大多數(shù)OpenCV中的機(jī)器學(xué)習(xí)算法都被劃分在ML模塊中，但是Mahalanobis算法和K均值算法在Core模塊中，人臉檢測和目標(biāo)識別算法在objdetect模塊中，F(xiàn)LANN算法在flann模塊中，其他算法在opencv_contrib擴(kuò)展庫內(nèi)。

2.4.1 Mahalanobis

Mahalanobis算法定義了一種距離的度量方式，也被稱為馬氏距離，它通過將距離除以協(xié)方差從而得到一個具有空間拉伸的距離。如果協(xié)方差矩陣是單位矩陣，那么這個距離就等于歐式距離。詳細(xì)的算法介紹可以參考論文《On the generalized distance in statistics》。

2.4.2 K-均值(K-means)

K-均值算法是一個無監(jiān)督的聚類算法，它使用用戶定義的K個中心表示數(shù)據(jù)的分布。該算法和期望最大算法的區(qū)別是其使用的中心不是高斯分布的，因此聚類的結(jié)果看上去更像是肥皂泡，因為每個中心都“競爭”著去“捕獲”最近的數(shù)據(jù)樣本。這些聚類區(qū)域通常被用作稀疏直方圖的條從而表示數(shù)據(jù)。該算法由Steinhaus發(fā)明，相關(guān)論文為《Sur la division des corp materiels en parties》。由Lloyd使用，相關(guān)論文為《Least square quantization in PCM’s》。

2.4.3 正態(tài)/樸素貝葉斯分類器(Normal/Naive Bayes Classifier)

一種生成式分類器，它假定特征是高斯分布的，并在統(tǒng)計學(xué)上服從獨立分布，相互之間不影響，但是這種假設(shè)太嚴(yán)苛通常情況下都無法成立。也是因為這個原因它經(jīng)常被稱為樸素貝葉斯分類器（Naive Bayes Classifier）。然而這個方法經(jīng)常卻工作得出奇的好，最早提及該方法的論文是《Automatic indexing: An experimental inquiry》和《Steps toward artificial intelligence》。

2.4.4 決策樹(Decision Trees)

決策樹是一個判定式分類器，它通過在當(dāng)前節(jié)點尋找一個數(shù)據(jù)特征和一個閾值從而將數(shù)據(jù)最優(yōu)劃分到不同的類別中。每次處理完數(shù)據(jù)后都會跳轉(zhuǎn)到左子樹或者右子樹，并沿著樹向下重復(fù)這個流程。雖然該算法的表現(xiàn)并不是最好，但是通常你應(yīng)該首先嘗試這個算法，因為它的運行速度非?？?，并且具有功能很強(qiáng)大。更多算法細(xì)節(jié)可以參考論文《Classification and Regression Trees》。

2.4.5 期望最大算法(Expectation Maximization, EM)

一個用于聚類的生成式無監(jiān)督學(xué)習(xí)算法，它使用N維高斯分布擬合數(shù)據(jù)，這里的N由用戶選擇。在只有少量參數(shù)，如均值和方差時，它是一個表示更復(fù)雜數(shù)據(jù)分布的有效方式。該方法通常用于分割。更詳細(xì)的算法細(xì)節(jié)請參考論文《Maximum likelihood from incomplete data via the EM algorithm》。

2.4.6 Boosting算法

它由一組判定式分類器組成，最終的分類結(jié)果是組內(nèi)各個分類器結(jié)果的加權(quán)結(jié)果。在訓(xùn)練時會逐個訓(xùn)練組內(nèi)的分類器，這些分類器都是“弱”分類器，其性能僅僅略高于隨機(jī)選擇一個分類。它們由簡單稱為“樁”（Stumps）的單變量決策樹組成。在訓(xùn)練的時候決策樁不僅需要從數(shù)據(jù)中學(xué)習(xí)分類決策，還需要根據(jù)它處理數(shù)據(jù)的精度學(xué)習(xí)到自己“投票的權(quán)重。在處理每個分類器的間隙，數(shù)據(jù)樣本的權(quán)重會重新分配，從而使得錯分的數(shù)據(jù)能夠得到更多的關(guān)注。這個過程一直重復(fù)直到由不同決策樹的投票加權(quán)結(jié)果產(chǎn)生的整體誤差低于預(yù)設(shè)的某個閾值。這個方法需要在訓(xùn)練集較大時才會取得較好的結(jié)果。更多的細(xì)節(jié)可以參考論文《A decision-theoretic generalization of on-line learning and an application to boosting》。

2.4.7 隨機(jī)森林(Random Trees)

由很多決策樹組成的判定式森林，每個決策樹都向下重逢以獲取最大深度。在學(xué)習(xí)過程中，每棵樹的每個節(jié)點都允許從數(shù)據(jù)特征的隨機(jī)子集中選擇類別劃分變量。這有助于每棵樹成為一個統(tǒng)計學(xué)上相互獨立的決策者。在運行模式下，每棵樹進(jìn)行不加權(quán)的投票。這個方法通常很有效，并且對每棵樹的輸出平均后還可以用于處理回歸問題。更多的算法細(xì)節(jié)請參考論文《Random decision forest》、《Decision forests for computer vision and medical image analysis》和《Fast approximate energy minimization via graph cuts》。

2.4.8 K臨近算法(K-nearest neighbors)

這可能是最簡單的分類器。訓(xùn)練數(shù)據(jù)和對應(yīng)的標(biāo)簽被同時保持，處理測試數(shù)據(jù)時，根據(jù)離它最近(歐式距離)的K個樣本的投票對被測樣本進(jìn)行分類。該算法通常很有效但是運行速度比較慢，并且需要大量的類次。更多算法細(xì)節(jié)可以參考論文《Discriminatory analysis, nonparametric discrimination: Consistency properties》和FLANN的相關(guān)介紹。

2.4.9 快速近似最近鄰法(FLANN)

OpenCV包含一個快速近似最近鄰庫，由Marius Muja開發(fā)，支持最近鄰的近似和K個最近鄰的匹配。更多的細(xì)節(jié)可以參考論文《Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration.》。這里的FLANN的全稱是Fast Library for Approximate Nearest Neighbors。

2.4.10 支持向量機(jī)(SVM)

一個判定式的分類器，它也可用于回歸。算法定義了任意兩個樣本在一個更高維度空間內(nèi)的距離函數(shù)。將數(shù)據(jù)投影到更高維度的空間會使得數(shù)據(jù)更可能是線性可分的。算法學(xué)習(xí)一個分類超平面，它能最大程度的在更高維度內(nèi)對數(shù)據(jù)分類。當(dāng)數(shù)據(jù)樣本有限時該算法趨于獲得近似最佳的效果，而當(dāng)數(shù)據(jù)量非常大時，bossting或者隨機(jī)森林算法能夠獲得更高的效果。更多的算法細(xì)節(jié)可以參考論文《An introduction to the Kalman filter》。

什么是大的數(shù)據(jù)，這里沒有明確的答案，因為它取決于底層生成過程的變化有多快。但是這里有一個非常粗暴的經(jīng)驗法則，每個分類/目標(biāo)在每個有意義的維度/特征上包含10個數(shù)據(jù)樣本。因此對于兩個分類，三個維度的場景需要的數(shù)據(jù)至少大于2??10??10??10=2000個數(shù)據(jù)樣本才能稱為大的數(shù)據(jù)。

2.4.11 人臉識別/級聯(lián)分類器

一個巧妙使用boosting分類器的目標(biāo)檢測應(yīng)用。OpenCV提供了訓(xùn)練過的正面人臉檢測器，它的檢測效果非常好。你可以用這個算法來訓(xùn)練軟件提供的其他目標(biāo)。當(dāng)然你也可以使用其他特征或者未這個分類器創(chuàng)建你自己的特征。這個算法非常善于處理剛性物體和特征視圖。該算法也被稱為Viola Jones分類器，這個根據(jù)作者的名字命名的。更多的算法細(xì)節(jié)可以參考論文《Robust real-time face detection》。

2.4.12 Waldboost

該算法事Viola級聯(lián)算法的一種衍生版本。它是一個運算非?？斓哪繕?biāo)檢測器，在處理一系列任務(wù)的時候也要優(yōu)于傳統(tǒng)的級聯(lián)分類器?？梢栽谀K…/opencv_contrib/modules中找到，更多的算法細(xì)節(jié)可以參考論文《WaldBoost - learning for time constrained sequential detection》。

2.4.13 隱變量支持向量機(jī)(Latent SYM)

隱變量支持向量機(jī)使用一個局部模型，基于識別目標(biāo)單個部分，并通過學(xué)習(xí)一個模型關(guān)聯(lián)不同的部分來識別復(fù)合目標(biāo)。更多的算法細(xì)節(jié)可以參考論文《Object detection with discriminatively trained part-based models》。

2.4.14 詞袋模型

詞袋方法將文檔分類中使用非常頻繁的技術(shù)推廣到了圖像分類。該方法非常強(qiáng)大，因為它不僅可以標(biāo)識單個物體，還可以用于標(biāo)識場景和環(huán)境。

2.5 使用機(jī)器學(xué)習(xí)處理視覺任務(wù)

通常情況下前文提到的那些算法的輸入是由很多特征構(gòu)成的數(shù)據(jù)向量，這些特征的數(shù)量可能高達(dá)幾千個。假定你的任務(wù)是識別一個特定類型的對象，例如一個人。你遭遇的第一個問題就是如何收集數(shù)據(jù)，并將其標(biāo)記為有人和沒有人的兩類。你很快會意識到人像在圖像上呈現(xiàn)不同的比例，你可能發(fā)現(xiàn)有的人像僅僅覆蓋很少的像素，而有的圖片上一只耳朵就能占據(jù)整個圖像。甚至更糟糕的情況是人們經(jīng)常被遮擋，如在車?yán)锏娜耍粡埮说哪槪瑥臉浜笊斐龅囊粭l腿。你需要定義哪種情況下可以判定場景內(nèi)出現(xiàn)了人。

接下來的問題是如何收集數(shù)據(jù)，是使用相機(jī)采集，還是去照片分享網(wǎng)站上嘗試找到“人物”的分類標(biāo)簽，或者兩種方式都使用以及更多的方式。是否采集移動信息，以及一起其他的信息，如場景中的門是否開啟，時間、季節(jié)和溫度信息。一個能夠在沙灘上搜索人物的算法在處理滑雪斜坡時可能無法正常工作。你需要捕獲數(shù)據(jù)中的這些變化信息，如不同的視角、光照、天氣條件、陰影等。

收集完數(shù)據(jù)之后，首先你需要確定想要通過標(biāo)簽表述什么信息，你是想確定場景中是否存在人物？他們的動作是否重要？是在跑步，走路，爬行還是追蹤。你可能收集到超過百萬張圖片，甚至更多。標(biāo)記這些信息有很多技巧，例如在受控的設(shè)置下應(yīng)用背景提取并收集被分割出來的走入場景的前景人物。你也可以使用一些數(shù)據(jù)服務(wù)來幫你完成分類工作，例如可以通過亞馬遜的Mechanical Turk服務(wù)雇人來處理你的數(shù)據(jù)。如果你將工作排列得比較簡單，就能將成本控制在約每個標(biāo)簽1便士以下。最后你再使用圖像硬件如GPU或者其他計算族群完成目標(biāo)、人物、人臉、手臂的渲染。使用相機(jī)模型參數(shù)，你通常可以得到背景已知的非常逼真圖像，因為數(shù)據(jù)是你自己生產(chǎn)的。

標(biāo)記完數(shù)據(jù)之后，你必須決定從目標(biāo)中提取哪些特征。如果人物總是正面站立的，就沒有必要使用旋轉(zhuǎn)不變性的特征，也沒有必要在處理圖像之前旋轉(zhuǎn)它們。總的來說，你需要找到能夠表述目標(biāo)固有屬性的特征，例如對縮放不敏感的梯度或者顏色直方圖，或者是流行的SIFT特征。關(guān)于SIFT特征更多細(xì)節(jié)可以參考Lowe的Keypoint demo。如果有背景信息，你可能想首先移除這些信息。接下來需要對圖像進(jìn)行處理，其中包括對圖像的標(biāo)準(zhǔn)化處理，和計算不同類型的特征。其中標(biāo)準(zhǔn)化處理包括縮放、旋轉(zhuǎn)、直方圖均衡等。得到的每個數(shù)據(jù)向量都會分配一個標(biāo)簽，它們和目標(biāo)、運動或者場景相關(guān)聯(lián)。

當(dāng)數(shù)據(jù)收集完成后需要將它轉(zhuǎn)換為特征向量，通常需要將它們分為訓(xùn)練、驗證(可選)和測試集。正如我們前面提到過，訓(xùn)練策略的一個最佳實踐就是使用交叉驗證的方式進(jìn)行訓(xùn)練、驗證和測試?；仡櫱拔奶岬降木唧w做法，將數(shù)據(jù)氛圍K個子集并執(zhí)行多個訓(xùn)練、驗證(可選)和測試會話，每次會話包含不同的數(shù)據(jù)集用于訓(xùn)練、驗證(可選)和測試。通常可以包含5到10次訓(xùn)練會話。不同會話的測試結(jié)果經(jīng)過平均得到最終的性能結(jié)果。交叉驗證能夠更準(zhǔn)確的表述分類器部署到新的數(shù)據(jù)時的效果。

數(shù)據(jù)準(zhǔn)備好后就需要選擇分類器，通常分類器的選擇和計算效率，數(shù)據(jù)條件，和內(nèi)存條件相關(guān)。對于某些應(yīng)用程序，例如在線用戶偏好偏好建模，你必須快速的訓(xùn)練分類器。在這種情況下最近鄰、貝葉斯或者決策樹都是不錯的選擇。如果對內(nèi)存要求苛刻，決策樹或者神經(jīng)網(wǎng)絡(luò)能夠高效的利用內(nèi)存空間。如果分類器的訓(xùn)練時間充分，但是要求判斷迅速，神經(jīng)網(wǎng)絡(luò)是很好的選擇，當(dāng)然樸素貝葉斯和支持向量機(jī)也是不錯的選擇。如果訓(xùn)練的時間充分，并且也支持一定的時間做出判斷，但是要求較高的精度，則bossting和隨機(jī)森林可以滿足你的需求。如果只是想要一個簡單的，易懂的便于檢查特征選擇的是否好的分類器，則決策樹或者最近鄰是很好的選擇。當(dāng)然要獲得最好性能，最好首先嘗試boosting或者隨機(jī)森林。

需要注意沒有最好的分類器，更多細(xì)節(jié)可以參考文章No Free Launch Theorem(http://en.wikipedia.org/wiki/No_free_lunch_theorem)。對所有可能存在的數(shù)據(jù)分布類型平均后，所有的分類器表現(xiàn)都差不多。因此我們不能夠說某個算法就是最好的。但是對于特定的數(shù)據(jù)分布或者數(shù)據(jù)集分布而言，確實有最好的分類器。因此當(dāng)處理真實數(shù)據(jù)時多嘗試不同的分類器是一個不錯的主意。首先確定你的目的，是要得到正確的分?jǐn)?shù)，或者是想要解釋數(shù)據(jù)。你是否追求更快的計算效率、更小的內(nèi)存消耗或者對決策的置信度有要求？不同的分類器在這些維度上有不同的表現(xiàn)。

2.6 變量的重要性

前文列舉的機(jī)器學(xué)習(xí)算法中有兩個可以判斷變量的重要性(Variable Importance)。已知特征向量，判定這些特征對分類準(zhǔn)確性的重要性是一個常見的問題。二叉決策樹可以直接表示這個信息，通過在每個節(jié)點選擇最能將數(shù)據(jù)分成不同部分的特征來訓(xùn)練模型。頂層的節(jié)點表示的變量則是最重要的變量，第二層的節(jié)點對應(yīng)的變量則是次重要的變量，并以此類推。該算法對噪聲非常敏感，二叉樹真正做的是為每個節(jié)點構(gòu)建代理分支，并計算該節(jié)點上所有分割方案的重要性。隨機(jī)森林算法使用了Leo Breiman開發(fā)的技術(shù)，也能夠計算變量的重要性。該技術(shù)能過被用在任意分類器中，但是到目前為止OpenCV中只有決策樹和隨機(jī)森林算法實現(xiàn)了這個技術(shù)。

變量重要性的一個使用場景就是減少分類器需要考慮的特征數(shù)量。對于特征數(shù)量很多的數(shù)據(jù)，訓(xùn)練分類器并找到每個特征相較于其他特征的重要程度。然后丟棄不重要的特征。因為算法不再需要技算這些特征數(shù)據(jù)，消除不重要的特征能提升算法效率，讓訓(xùn)練和測試過程變得更快。同樣的，如果已有的數(shù)據(jù)并不充分，通常我們會面臨這種情況，則消除不重要的變量能夠提升分類器的準(zhǔn)確性，這樣能夠提升算法的效率并得到更好的結(jié)果。

Breiman的重要性算法主要步驟如下：

1. 在訓(xùn)練集上訓(xùn)練分類器。
2. 使用驗證或者測試集判斷分類器的準(zhǔn)確性。
3. 對于選定的一個特征，將每個樣本該特征的值都隨機(jī)的使用集合中其他樣本的值替換，這種技術(shù)也被稱為替補(bǔ)抽樣(Sampling with Replacement)。這樣就抱著了特征的分布并不會改變，但是實際的結(jié)構(gòu)或者說含義被消除了。隨機(jī)森林算法的實際實現(xiàn)并不會生成新的值，實際上只是在樣本中交換了它們。
4. 在改變后的訓(xùn)練集上訓(xùn)練分類器，然后在改變后的驗證和測試集上計算分類器的準(zhǔn)確性。如果準(zhǔn)確性降低很多，則該特征就是非常重要的，如果對準(zhǔn)確性影響不大，則該特征就是一個可以被移除的特征候選項。
5. 恢復(fù)數(shù)據(jù)集，并重復(fù)3-4的步驟處理其他特征。再將所有特征根據(jù)重要程度排序得到最后的結(jié)果。

這個過程被內(nèi)置再隨機(jī)森林和決策樹算法中，因此可以直接使用這兩個算法決定我們實際需要的是哪些特征，然后使用瘦身后的特征向量來訓(xùn)練同一個或者其他類型的分類器。

2.7 常見的機(jī)器學(xué)習(xí)問題

讓機(jī)器學(xué)習(xí)算法工作理想不僅是個科學(xué)問題，更是一門藝術(shù)。算法通常能夠解決大多數(shù)問題，但其結(jié)果又不完全和你預(yù)期的一致。這就是藝術(shù)所在，為了讓它工作更好，你需要找出是哪個地方存在問題。盡管這里我們不會講解所有的細(xì)節(jié)，但是會大致介紹一些你可能遭遇到的常見問題。斯坦福大學(xué)的Andrew Ng教授開授了名為Advice for Applying Machine Learning(http://www.stanford.edu/class/cs229/materials/ML-advice.pdf)的網(wǎng)絡(luò)課程，你可以從這里找到更多的細(xì)節(jié)。

首先介紹重要的經(jīng)驗法則，更多的數(shù)據(jù)比更小的數(shù)據(jù)更重要，更好的特征比更好的算法重要。如果你的特征設(shè)計得非常好，即使它們之間的相互獨立性更強(qiáng)，并使它們受不同環(huán)境的影響更小，則幾乎任意的算法都會工作得非常好。除了這兩點之外，還有三個常見的問題。

• 欠擬合：模型的假設(shè)太嚴(yán)格，因此不能很好的匹配數(shù)據(jù)。
• 過擬合：算法將沒有排除噪聲，因此不具很好的通用性。
• 錯誤：機(jī)器學(xué)習(xí)代碼通常會包含一些表面上看上去非常嚴(yán)重的Bug，它們在預(yù)期完全錯誤的時候通常會降低算法性能。

下圖介紹了統(tǒng)計機(jī)器學(xué)習(xí)的基本結(jié)構(gòu)，它的工作方式是對函數(shù)f進(jìn)行數(shù)學(xué)建模，該函數(shù)將給定的輸入數(shù)據(jù)轉(zhuǎn)換成一個確定的輸出。這個函數(shù)可能是一個回歸問題，例如根據(jù)人臉預(yù)測某個人的年齡?？赡苡行┚鞯淖x者會認(rèn)為因為該場景中計算得到的年齡都是整數(shù)，因此它更像一個分類問題。但是回歸問題和分類問題的定義是輸出結(jié)果的連續(xù)性，因此這實際上是一個回歸問題。另外這個函數(shù)也可能是一個分類預(yù)測問題，例如根據(jù)臉部特征識別莫個人。在真實世界中，噪聲和一些未考慮到的影響將會導(dǎo)致觀察到的輸出數(shù)據(jù)和理論輸出值不同。例如在人臉識別應(yīng)用程序中，我們可能需要學(xué)習(xí)一個模型通過測量眼睛、嘴巴和鼻子之間的距離來識別特定的臉。但是由于附近閃爍的燈光導(dǎo)致光照條件的改變可能產(chǎn)生測量誤差，或者一些質(zhì)量較低的相機(jī)透鏡可能在測量時產(chǎn)生系統(tǒng)扭曲，這些因素我們都沒有考慮到模型中，它們會影響模型的精度。

下圖演示了欠擬合和過擬合對測試集和訓(xùn)練集的誤差影響，其中上方的兩幅圖分別表示的是欠擬合和過擬合的場景中模型的匹配情況，下方的兩幅圖則是對應(yīng)的訓(xùn)練以及測試過程中誤差和對應(yīng)集合樣本數(shù)量大小點關(guān)系。在欠擬合場景中，通過左上角的圖可以看到模型設(shè)置非常嚴(yán)格，它和真實的函數(shù)f并不匹配，在下方對應(yīng)的誤差分析圖也可以看到這種情況下無論是訓(xùn)練和測試誤差都很大，即使有著大量數(shù)據(jù)也并不能很好的處理誤差，只是讓測試和訓(xùn)練誤差更接近而已。對于右側(cè)兩幅圖中過擬合的場景，模型和實際的樣本嚴(yán)格匹配，但是這樣卻考慮了所有的噪聲，從下方的誤差分析圖中可以看到這樣也會導(dǎo)致很大的誤差?？偨Y(jié)一下就是相對低的訓(xùn)練誤差和高測試誤差表示模型欠擬合，而訓(xùn)練誤差較低，測測誤差很高則表明模型過擬合。

有時需要仔細(xì)思考正在處理的問題是否是你想要解決的那個問題，如果你得到了較低的測試和訓(xùn)練誤差，但是算法在實踐中工作得并不理想，那么可能是因為數(shù)據(jù)集采集時處于非真實的條件或者環(huán)境，可能這些不真實的條件或者環(huán)境使得數(shù)據(jù)更容易采集和模擬。如果這個算法不能夠重現(xiàn)測試集和數(shù)據(jù)集的表現(xiàn)，可能是因為使用了錯誤的算法，從數(shù)據(jù)中提取的特征是無效的，或者說真正的信號并不在收集的數(shù)據(jù)中。

下表列出了我們之前討論的問題的一些可能解法，當(dāng)然這里并未列出全部的問題，也并未列出所有的解法。為了機(jī)器學(xué)習(xí)模型能過工作得更好，需要收集哪些數(shù)據(jù)，以及從中提取哪些特征是需要仔細(xì)思考和設(shè)計的。同樣診斷機(jī)器學(xué)習(xí)問題也需要系統(tǒng)的思考。

交叉驗證、booststrapping、ROC曲線和混淆矩陣

最后介紹一些度量機(jī)器學(xué)習(xí)結(jié)果優(yōu)劣的基本工具，在有監(jiān)督學(xué)習(xí)中，一個最基本的問題就是確定算法的性能，算法分類或者擬合數(shù)據(jù)的精確度。可能我們會認(rèn)為這很簡單，只需要在測試和驗證集上運行算法并獲取結(jié)果就可以了。但是在處理真實問題的時候，我們必須考慮噪聲、采樣誤差和采樣錯誤。簡單的說，測試和驗證集可能并不能準(zhǔn)確的反映真實數(shù)據(jù)的分布。為了更準(zhǔn)確的評估分類器的性能，我們采用交叉驗證(Cross-Validation)或者類似的bootstrapping技術(shù)。

在最基本的形式下，交叉驗證將數(shù)據(jù)分為K個不同的子集。使用K-1個子集訓(xùn)練模型，并使用剩下的那個子集作為測試集。這樣操作K次，每個子集都會作為一次測試集，然后將結(jié)果平均。

Boostrapping和交叉驗證類似，但是驗證集是從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇的。每次從全部數(shù)據(jù)中隨機(jī)選出一部分樣本作為子集作為驗證集，并使用剩下的數(shù)據(jù)訓(xùn)練模型，這樣執(zhí)行N次并將所得的結(jié)果進(jìn)行平均。因為每次驗證集都是隨機(jī)選擇的，因此某些樣本可能在不同迭代輪次的驗證集中重復(fù)出現(xiàn)。通常情況下使用Boostrapping算法得到的結(jié)果會優(yōu)于使用交叉驗證得到的結(jié)果。Boostrapping的主要目標(biāo)是找到最優(yōu)的訓(xùn)練參數(shù)，因為平均訓(xùn)練誤差是容易的，但是將多個模型平均成一個模型可能是不常見或者低效的。

使用這些技術(shù)的任意一種都能夠得到更準(zhǔn)確更優(yōu)秀的評估結(jié)果。在你重復(fù)的改變參數(shù)、訓(xùn)練模型得到結(jié)果的過程中，增加的準(zhǔn)確性又能反過來用于參數(shù)的調(diào)優(yōu)。

另外兩個非常有用的評估和調(diào)整分類器的方法是繪制ROC(Receiver Operating Characteristic)曲線，和填充混淆矩陣(Confusion Matrix)。如下圖，ROC曲線描述了分類器的正確識別率(識別為真的結(jié)果中實際為真的結(jié)果占全部實際為真結(jié)果的比例)和錯誤識別率(識別為真的結(jié)果中實際為假的結(jié)果占全部實際為假結(jié)果的比例)的關(guān)系，它們是衡量分類器性能的重要指標(biāo)。曲線上的每個點都可能是使用交叉驗證法計算得到的結(jié)果。我們假定分類器的參數(shù)是一個閾值，更具體點我們假定需要在圖像中識別出黃色的花，并且我們定義了一個顏色閾值作為我們的檢測器。如果我們將閾值設(shè)置得非常高，則檢測器識別的結(jié)果為假，也就是說分類器的錯誤識別率和正確識別率都為0。也就是下圖曲線的左下角點。另一方面，如果黃色的閾值被設(shè)置為0，則所有的結(jié)果都被識別為真，也就是說錯誤識別率和正確識別率都是100%，即下圖曲線的右上角點。最好的ROC曲線是幾乎沿著Y軸上升到正確識別率100%后再沿著X軸到達(dá)右上角的折線。當(dāng)然實際上這很難做到，但是曲線越靠近左上角，分類器性能越好。實際應(yīng)用中，通常計算曲線下方面積占整個畫面的比例，結(jié)果越接近1表明分類器的性能越好。

盡管在其他文獻(xiàn)中有數(shù)不清的關(guān)于分類器品質(zhì)的定義，并且它們都有同樣多的理由認(rèn)為自己更優(yōu)秀，但是這并沒有太大意義。文中使用到的定義是其中很常見的一種，可能該定義并不一定是關(guān)于某個分類器質(zhì)量最好的表述，但是這種定義更容易理解，并且它對于幾乎任意分類問題都有足夠好的定義。

上圖中的混淆矩陣行分別表示實際的真值和加值，列分別表示預(yù)測的真值和價值，理想情況下評估一個分類器性能時，我們希望右對角線上的值都是100%，而其他地方的值為0%。如果分類器能夠?qū)W習(xí)到兩個以上的類別，如多層感知神經(jīng)網(wǎng)絡(luò)的隨機(jī)森林分類器一次能夠?qū)W習(xí)到很多不同的類別標(biāo)簽，則混淆矩陣可以推廣到覆蓋所有標(biāo)簽的形式，矩陣中的每個實體都表示該情景的樣本數(shù)量占整行樣本的比例。但是ROC曲線在處理多個分類標(biāo)簽時只能記錄在測試集上做出的正確和錯誤抉擇。

分錯類的成本

錯誤分類的成本我們還沒有詳細(xì)討論，假定我們的分類器用于識別食用蘑菇，在下一章會有具體的實例。顯然我們可以接受模型具有較大的錯誤拒絕率（即將可食用的蘑菇標(biāo)記為不可食用的），同時我們想盡量減小模型的錯誤識別率（將有毒的蘑菇標(biāo)記為可以食用的）。ROC曲線可以幫助我們實現(xiàn)這樣的目標(biāo)，可以調(diào)整ROC參數(shù)從而在曲線的左下段選擇一個操作點。另外一種方式是在生成ROC曲線時，給錯誤識別率相較于錯誤拒絕率更大的權(quán)重。例如你可以將每個錯誤識別的成本設(shè)置為10倍錯誤拒絕的成本。另外如果你有一些兩個錯誤類型的相對成本的具體先驗概念，這種方式非常有用。例如在超市結(jié)賬時一個商品被錯誤分類成另外一個商品的成本很容易預(yù)先準(zhǔn)確量化。

在一些OpenCV的機(jī)器學(xué)習(xí)算法種，如決策樹和SVM，你可以通過指定不同類型自己的先驗概率（即哪些類更容易被標(biāo)記，哪些類更不容易被標(biāo)記），活著指定單個訓(xùn)練樣本的權(quán)重來平衡命中率和虛警率，即正確識別率和錯誤識別率。

特征方差不一致

在訓(xùn)練分類器時另外一個常見的問題時特征向量種的特征方差不一致。例如假如某個特征使用小寫的英文字符的ASCII表示，則該特征的只有26個不同的取值，而假如有另外一個特征描述的是顯微鏡下玻片上的細(xì)胞數(shù)量，該特征的的取值可以在幾百萬個值中變化。類似于K最鄰近算法這樣的機(jī)器學(xué)習(xí)算法可能會將第一個特征視為常量，也就是從該特征種無法學(xué)到東西。處理這個問題的方式是先使用特征各自的方差對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。當(dāng)特征之間沒有關(guān)聯(lián)時這種做法時可以接受的，當(dāng)它們之間存在關(guān)聯(lián)時，你可以食用它們的平均方差活著協(xié)方差來標(biāo)準(zhǔn)化數(shù)據(jù)。特征方差不一致對一些算法沒有影響，如決策樹，此時這種預(yù)處理操作不需要執(zhí)行。決策樹算法不受方差不一致因素影響是因為對于每個特征僅搜索有效分離閾值，換句話說，只有能夠找到明確的分離值，變量的數(shù)值范圍有多大并不重要。

一個經(jīng)驗法則是如果算法依賴于某種距離度量的方式，如加權(quán)值，則你應(yīng)該對各個特征的方差進(jìn)行歸一化處理。一個可以一次標(biāo)準(zhǔn)化處理所有特征值并解釋它們的協(xié)方差的手段是馬氏距離（Mahalanobis Distance），在本章的后半部分我們將深入介紹該技術(shù)。熟悉機(jī)器學(xué)習(xí)或者信號處理的讀者可能已經(jīng)意識到這實際上就是數(shù)據(jù)”美白”技術(shù)。

接下來將會討論一些在OpenCV中支持的機(jī)器學(xué)習(xí)技術(shù)。

3 ML庫中遺留的算法

大多數(shù)ML庫都是用了基于對象的公共C++接口，并在繼承于該基類的對象中實現(xiàn)了這些算法。通過這種方式可以通過標(biāo)準(zhǔn)方式在這些庫中訪問和使用這些算法。然而一些最基本的算法由于它們在引入這種規(guī)范之前就被設(shè)計，因此并不遵守這些標(biāo)準(zhǔn)。接下來在本節(jié)中我們將介紹K均值聚類算法，馬氏距離及其在K均值聚類算法中的使用，然后再介紹一種分割技術(shù)，它常用于提高K均值聚類算法的速度和準(zhǔn)確度。

3.1 k-均值算法

K-均值算法嘗試找到使用向量表示的數(shù)據(jù)集的自然分簇。用戶設(shè)置需要的分簇數(shù)量，K-均值算法會快速的找到它們的數(shù)據(jù)中心的一個較好解決方案，當(dāng)然這里的較好值的是數(shù)據(jù)簇中心趨于整個數(shù)據(jù)集自然分類的中。該算法是最常用的一種分簇技術(shù)，并和期望最大算法(Expectation Maximization)，以及前面章節(jié)提到的均值漂移算法(即函數(shù)cv::meanShift()內(nèi)部的算法)類似。更準(zhǔn)確的說，K-均值算法是和使用高斯混合模型的期望最大算法相似。在OpenCV中的實現(xiàn)接口是cv::EM()，在本章的后續(xù)部分還會詳細(xì)介紹。正如在OpenCV中的實現(xiàn)一樣，K-均值算法是一個迭代算法，它也被稱為Lloyd算法，具體參考論文《Least squares quantization in PCM》，同時它還被稱為Voronoi迭代。該算法的主要步驟如下。

• 接收用戶的輸入，包含數(shù)據(jù)集D以及期望分簇的數(shù)量K。
• 隨機(jī)但足夠分散的分配數(shù)據(jù)簇中心。
• 將每個數(shù)據(jù)點關(guān)聯(lián)到最近的數(shù)據(jù)簇中心。
• 將數(shù)據(jù)簇中心移動到各自數(shù)據(jù)子集的質(zhì)心。
• 回到第三步直至算法收斂，也就是說質(zhì)心不再移動。

下圖演示了一個K-均值算法應(yīng)用的實例，在這個例子中算法迭代三次就收斂。在實際的應(yīng)用中通常算法收斂速度非常快，但是也有需要大量迭代才能收斂的情況。在下圖中，圖a隨機(jī)分配了三個數(shù)據(jù)簇中心，并將所有樣本點關(guān)聯(lián)到最近的數(shù)據(jù)中心，圖b將這些數(shù)據(jù)中心移動到各自子集的質(zhì)心，并將所有樣本點重新關(guān)聯(lián)到最近的集合中心，圖c和圖d實際上是重復(fù)了圖b的操作得到新一輪迭代的結(jié)果。

3.1.1 相關(guān)問題以及解決方案

K-均值算法是一個非常有效的聚類算法，但是它有三個重要的缺陷。

• 它不能保證找到分類中心的最佳解決方案。它只保證收斂到某一個解決方案，即迭代不會無限的進(jìn)行下去。
• 算法不能告訴調(diào)用方應(yīng)該選擇的分類數(shù)量。如果對于上圖的場景我們確定分簇數(shù)量為2或者4將會得到不同甚至不合理的結(jié)果。
• 它并不關(guān)心數(shù)據(jù)在空間中的協(xié)方差是否匹配，或者說數(shù)據(jù)已經(jīng)歸一化處理。后面還會對該點詳細(xì)解釋，并引入馬氏距離(Mahalanobis Distance)。

這三個問題都有一個解決方案，或者說至少有一個可以提供幫助的方法。前兩種結(jié)局方案都依賴于解釋數(shù)據(jù)的方差。在K-均值算法中，每個聚類中心都管理著自己的樣本子集，我們會計算這些樣本的方差。在這里方差值的是點到聚類中心到距離。點的方差通常是這些點的正交積(Quadrature Sum)，這個積也被稱為緊湊度(Compactness)。

最好的聚類方案在不造成太大的復(fù)雜度即數(shù)據(jù)簇的數(shù)量不太大的情況下，使分簇結(jié)果整體方差最小?；诖耍覀兛梢酝ㄟ^如下方式改善上述列出的問題。

1. 多次執(zhí)行K-均值算法，這樣每次隨機(jī)選擇的初始聚類中心幾乎不會相同，并選擇整體方差最小的結(jié)果。
2. 將聚類的數(shù)量設(shè)置為1，然后再依次遞增迭代執(zhí)行K-均值算法，每次迭代都是用方案1的策略得到當(dāng)前聚類數(shù)量下最好的結(jié)果。通常情況下整體方差變化會快速趨于平坦，接著在方差曲線上將會出現(xiàn)一個拐點。這意味著新增一個聚類中心不會明顯的減少方差，此時可以停止迭代并使用當(dāng)前的聚類中心數(shù)量。
3. 將數(shù)據(jù)集乘以方差矩陣的逆矩陣，在本章后續(xù)部分介紹馬氏距離的時候還會解釋。例如，如果輸入的數(shù)據(jù)D中每個樣本都是使用一行來描述的，通過計算局長D??來標(biāo)準(zhǔn)化數(shù)據(jù)，此處D?? = DΣ^-1/2。

3.2.2 相關(guān)接口

OpenCV中提供的K-均值算法接口如下。

// 返回值：緊湊度
// data：待處理的數(shù)據(jù)樣本，元素為float類型
// K：聚類中心的數(shù)量
// bestLabels：數(shù)據(jù)樣本被分到的聚類中心索引，元素為int類型
// criteria：算法終止迭代的條件，可以指定迭代數(shù)或者指定最小聚類中心偏移距離
// attempts：設(shè)定算法總體迭代次數(shù)，即前文的解決方案1，選擇不同的初始聚類中心
// flags：初始化選項
// centers：找到的聚類中心，如果不需要該結(jié)果直接傳入cv::noArray()
double cv::kmeans(cv::InputArray data,
int K,
cv::InputOutputArray bestLabels,
cv::TermCriteria criteria,
int attempts,
int flags,
cv::OutputArray centers = cv::noArray());

該接口中參數(shù)data是一組多維樣本點的矩陣，其中每一行都表示了一個樣本，矩陣中的每個元素都是浮點類型的，如CV_32FC1。當(dāng)然矩陣也可以只有一列，但此時元素類型需要是多通道的，如CV_32FC2、CV_32FC3甚至CV_32FCM等。參數(shù)criteria可以指定算法迭代結(jié)束的條件，可以從迭代執(zhí)行次數(shù)和最小距離兩個角度，這里的最小距離指的是算法兩次計算出的聚類中心之間的距離低于設(shè)定閾值時算法結(jié)束迭代。參數(shù)attempts指定了算法的總體迭代次數(shù)，一次總體迭代表示算法尋找新的聚類中心初始位置，也就是前文解決方案1描述的策略，算法會保存最好的結(jié)果。這里結(jié)果的質(zhì)量通過緊湊度衡量，也就是說所有樣本點到各自關(guān)聯(lián)的聚類中心的距離平方和。

參數(shù)flags的取值包含cv::KMEANS_RANDOM_CENTERS、cv::KMEANS_USE_INITIAL_LABELS、cv::KMEANS_PP_CENTERS，其中第一個是默認(rèn)值。cv::KMEANS_RANDOM_CENTERS表示的是前文提到的隨機(jī)選擇初始的聚類中心。cv::KMEANS_USE_INITIAL_LABELS表示使用參數(shù)bestLabels的信息來計算初始的聚類中心。而cv::KMEANS_PP_CENTERS表示使用Sergei Vassilvitskii和David Arthur提出的K-均值++的方式去計算初始的聚類中心，具體可以參考論文《k-means++: the advantages of careful seeding》。K-均值++內(nèi)部的原理這里不用關(guān)心，我們暫時只需要知道該算法會更謹(jǐn)慎的選擇初始的聚類中心，通常比使用默認(rèn)選項算法執(zhí)行更少的迭代次數(shù)，并且現(xiàn)代引用中，K-均值++也逐漸成為標(biāo)準(zhǔn)策略。

需要注意的是理論上K-均值算法可能得到非常糟糕的結(jié)果，但是它在實踐中卻仍被大量使用是因為大多數(shù)時間它都能得到很好的結(jié)果。在最壞的情況下分簇問題是一個NP問題，意味著不太可能得到一個真正的優(yōu)解，但是對于大多數(shù)應(yīng)用而言一個較好的解已經(jīng)足夠。 除此之外該算法還有一些其他問題。其中一個就是在特定的場景下，該算法可能得到一個數(shù)學(xué)家稱為”Arbitrarily Bad”的結(jié)果。也就是無論你認(rèn)為得到的結(jié)果有多糟糕，總有人會面臨同樣或者更糟的結(jié)果。在過去幾年中也出現(xiàn)了一些應(yīng)對這個問題的新技術(shù)，它們旨在提供一些通用的性能改進(jìn)，或者在最好當(dāng)前情況下一些技術(shù)還能提供一些可以證明的邊界，這些邊界能在算法結(jié)果上給用戶多一點信心。這些改進(jìn)技術(shù)中的一個就是前文提到的K-均值++算法。

使用K-均值算法的示例程序核心如下，閱讀該部分源碼對理解算法是有幫助的，并且數(shù)據(jù)生成部分的代碼也可以用于測試其他機(jī)器學(xué)習(xí)程序。完整的源碼請前往程序KMeans，更多關(guān)于算法的細(xì)節(jié)請參考前文列出的論文。

3.2 馬氏距離(Mahalanobis Distance)

前文的章節(jié)中已經(jīng)介紹過馬氏距離可以計算點到分布中心的距離，并且它的計算結(jié)果與分布形狀密切相關(guān)。在K均值算法的背景下，馬氏距離的概念有兩種用途。第一個應(yīng)用來源于將其視為在變形空間上測量歐式距離(Euclidean Distance)的觀點，這使得我們可以使用馬氏距離對數(shù)據(jù)進(jìn)行處理從而明顯提升K均值算法的性能。第二個應(yīng)用是將其作為為K均值算法定義的類簇分配新數(shù)據(jù)點的方法。

3.2.1 使用馬氏距離約束輸入數(shù)據(jù)

在示例程序KMeans中，我們簡要提到了數(shù)據(jù)在空間上的分布可能極其不對稱。當(dāng)然使用K-均值算法的核心是保證數(shù)據(jù)在空間上是不均勻分布的，然后嘗試找到類簇。然而不均勻(Nonuniform)和不對稱(Asymmetrical)之間有非常重要的差異。例如假如數(shù)據(jù)在某個維度上的分布較松散，而在另外一個維度上分布較為緊湊，則K均值算法的計算結(jié)果會較差。馬氏距離使我們可以將數(shù)據(jù)的協(xié)方差看作是空間上的拉伸，如下圖中，左圖中的原始數(shù)據(jù)在垂直方向上的距離要小于水平軸上的距離。右圖中，空間使用方差歸一化后數(shù)據(jù)之間的水平距離小于對應(yīng)的垂直距離。

這種情況經(jīng)常出現(xiàn)，因為數(shù)據(jù)向量的不同維度通常具有不同的度量單位。例如如果使用身高、體重和受教育的年限來表示社區(qū)內(nèi)的某個人，最明顯的就是身高和年的度量單位并不相同，這使得它們各自維度上的數(shù)據(jù)分布并不相同。類似的，盡管年齡和受教育的時間度量單位都是年，但是他們在自然人口中的數(shù)據(jù)分布差異也非常大。這個例子引出了一個簡單有用的技術(shù)，可以將數(shù)據(jù)集合看作是一個整體，并計算整個數(shù)據(jù)集協(xié)方差矩陣，然后使用協(xié)方差對原始數(shù)據(jù)進(jìn)行縮放。

在前文章節(jié)介紹函數(shù)cv::Mahalonobis()時曾介紹過馬氏距離。傳統(tǒng)的馬氏距離沿著某個點的特定方向，使用分布的方差作為度量單位測量了任意點到數(shù)據(jù)分布中心的距離。對于這些和統(tǒng)計學(xué)上的Z-score概念相似的算法而言，馬氏距離是Z-score在多維空間上的推廣。我們使用分布的協(xié)方差逆矩陣來計算馬氏距離，協(xié)方差矩陣的計算公式如下。

其中E[.]表示期望，則兩個點之間的馬氏距離計算公式如下。

此時，我們有兩種選擇繼續(xù)使用馬氏距離。首先我們可以在K均值算法中使用馬氏距離替換歐式距離，其次我們也可以首選對數(shù)據(jù)進(jìn)行縮放，然后在變形空間上使用歐式距離。第一個方案可能更直觀，但是假如我們不想破壞已有還不錯的K-均值算法實現(xiàn)的話，第二個方案在計算上會容易很多。最后，因為馬氏距離對數(shù)據(jù)的縮放是線性的，因此可以直接對縮放后的結(jié)果進(jìn)行插值。

顯然采用第一種方案，我們可以通過如下公式對原始進(jìn)行處理。其中D??是處理后的數(shù)據(jù)，D是原始數(shù)據(jù)，【∑-1/2】是逆協(xié)方差的平方根的倒數(shù)。這里協(xié)方差相關(guān)項放在等式的末尾是因為在機(jī)器學(xué)習(xí)庫ML的慣例中，矩陣中每行表示一個樣本，其中的每列表示不同的維度。也就是說數(shù)據(jù)是按行排列的，而不是按列排列。

這里我們不直接使用函數(shù)cv::Mahalanobis()計算馬氏距離，相反我們使用函數(shù)cv::calcCovarMatrix()計算協(xié)方差矩陣，再使用函數(shù)cv::invert()和參數(shù)cv::DECOM_EIG計算其逆矩陣，最后再計算其平方根。

在計算逆矩陣時，分解方式也可以選擇cv::DECOMP_SVD，但是這種方式的計算速度更慢，并且精度更低。另外即使DECOM_EIG所耗費的時間比DECOM_LU更長，但是當(dāng)數(shù)據(jù)的維度明顯低于數(shù)據(jù)集的樣本數(shù)量時仍然應(yīng)該選擇這種方式。這種情況下整個算法的總體時間由函數(shù)cv::calcCovarMatrix()控制。因此更明智的方式是多花一點點時間用于計算逆協(xié)方差矩陣從而獲得更高的精度。另外這里并沒有一個通用的計算平方根函數(shù)，但是由于協(xié)方差矩陣自身的特性?？梢韵葘ζ鋵腔幚恚缓笤俜謩e計算特征值的平方根，然后再使用對角化處理時的特征向量將其旋轉(zhuǎn)回原始的坐標(biāo)系。

3.2.2 使用馬氏距離分類

給定一個使用K均值或者其他算法分類的標(biāo)簽，我們可以嘗試預(yù)測新的樣本點最有可能屬于哪一個分類標(biāo)簽。當(dāng)這些分類本身是，或者認(rèn)為它們是高斯分布時，在處理數(shù)據(jù)的不同維度之間可能存在相關(guān)性時，應(yīng)用馬氏距離對于分類預(yù)測也是有意義的。
首先我們需要描述每個類簇的平均值和協(xié)方差，然后就可以計算新樣本點到每個類簇中心的馬氏距離。到這里你可能會猜測新樣本點屬于具有最小馬氏距離的類簇，然而事情并沒有如此簡單。準(zhǔn)確的說只有當(dāng)所有的類簇包含相同數(shù)量的元素時這個猜測才是正確的，或者從統(tǒng)計學(xué)的角度說，如果屬于每個類簇的先驗概率是相同的情況下，這個猜測才成立。

這個差異可以簡潔的使用貝葉斯規(guī)則描述，即對于事件A和B，事件B成立前提下A成立的概率，和事件A成立前提下B成立的概率并不相同。用公式概括如下：

貝葉斯規(guī)則也提到事件B成立概率與事件B成立前提條件下事件A成立概率的乘積，和事件A成立概率與事件A成立前提條件下事件B成立概率的乘積相等，用公式概括如下：

為了將這些概率理論和馬氏距離分類問題聯(lián)系在一起，回想一下馬氏距離告訴我們的是特定樣本X位于分類C前提條件下P(C)，出現(xiàn)對應(yīng)觀測值的概率P(X | C)，馬氏距離越，概率越低。其中關(guān)鍵的是它前提已經(jīng)假定了樣本X屬于分類C。但是我們想要知道的是出現(xiàn)樣本X的觀測值P(X)前提條件下，樣本屬于類簇C的概率P(C | X)?；谪惾~斯規(guī)則的計算公式如下：

隨機(jī)從集合中抽取到一個樣本，其位于分類C的概率P(C)近似等于類簇C的樣本數(shù)量NC和ND的比值。這意味著為了比較兩個不同類簇的馬氏距離，我們需要考慮類簇的樣本數(shù)量。假定每個類簇的概率分布都是高斯分布，我們應(yīng)該比較的的指標(biāo)被稱為似然性，其計算公式如下：

你可能注意到在這個公式中沒有P(X)的計算，這是因為樣本在沒有確切分配到每個類別中時，我們沒有任何預(yù)先理由相信任意的特定樣本取值會比其他取值出現(xiàn)的概率更高，即使特定的取值確實有著更高的概率也不重要，因為這個概率對于我們比較的所有組別都是相同的。等式的后半部份首先對類簇C的協(xié)方差矩陣計算其行列式結(jié)果后區(qū)平方跟的倒數(shù)，然后將馬氏距離的平方作為自然數(shù)e的指數(shù)。

小結(jié)

在這一章我們首先討論了什么是機(jī)器學(xué)習(xí)，以及這個龐大的問題集合中哪些部分可以使用OpenCV庫解決，以及哪些不能。我們討論了測試數(shù)據(jù)和訓(xùn)練數(shù)據(jù)之間的區(qū)別。我們了解到生成式模型在無監(jiān)督或者沒有帶標(biāo)簽的訓(xùn)練數(shù)據(jù)前提下嘗試找到數(shù)據(jù)中的結(jié)構(gòu)，而判別式模型從示例中學(xué)習(xí)并嘗試從已知的信息中推廣數(shù)據(jù)結(jié)構(gòu)。然后我們開始研究OpenCV庫中的兩個基本工具，K均值聚類算法和馬氏距離。我們看到如何使用這些工具構(gòu)建簡單的模型從而解決有趣的問題。我們順便提到OpenCV目前也支持深度神經(jīng)網(wǎng)絡(luò)，但是它們當(dāng)前還位于實驗性質(zhì)的庫OpenCV_Contrib中。在最后的附錄B種的示例cnn_3dobj和dnn中將會有更詳細(xì)的描述。