【正文】 由 Jensen 不等式的性質(zhì)，為了讓等式成立，需要滿足：利用貝葉斯公式，可得：M 步驟，即最大化其最緊下界，由于該最緊下界中的隱變量已在 E 步驟中求得，可以直接利用極大似然估計求解：求解過程中，對每個參數(shù)逐個求偏導(dǎo)，然后令偏導(dǎo)等于0求得該參數(shù)。最大化其最緊下界，就是 M 步驟。由此，可以通過求似然函數(shù)的最緊下界，然后最大化其最緊下界這兩個步驟迭代求得 log 似然函數(shù)的最大值。這里不展開介紹，有興趣的讀者可以參考維基百科對 Jensen 不等式的介紹（）。因此，這里就需要對上式做一些變換，如下：這里引入 Q 函數(shù)，而且利用了 Jensen 不等式。我們還知道，在這個問題中，有一個隱變量，即每個樣本屬于不同類別的概率，將該隱變量的各個取值求和，可得：可以通過求解上式的最大值得到各個參數(shù)的解。假設(shè)觀察到的樣本數(shù)據(jù)都是獨立的，則它們出現(xiàn)的概率為每個樣本的概率乘積。同時，也會有疑惑，究竟期望最大化兩步中，求解四個參數(shù)的公式從何而來呢？這就要提到最大似然估計，以及 EM（期望最大化）算法。下一節(jié)介紹利用 EM 算法如何估計高斯混合模型的參數(shù)。不斷迭代這兩步，直到收斂或者達到最大迭代次數(shù)為止?？梢钥闯觯@一步利用期望步驟中求得的 w，來更新三個模型參數(shù)。其中，m 為樣本的個數(shù)。只不過，在混合高斯模型中，需要計算高斯分布的參數(shù)：均值 mu,方差 sigma 和男女生類別概率 phi。. Maximization (最大化)最大化用來求解各個聚類結(jié)果對應(yīng)的高斯分布的參數(shù)，即期望步驟中提到的 mu ,sigma 和 phi 三個參數(shù)。在這一步中，假設(shè)三個參數(shù)都是已知的，只有每個樣本點屬于男女生兩類的概率是未知的，這個概率可以通過已知的這三個參數(shù)計算得出。Phi 服從多項式分布，指男生類別和女生類別出現(xiàn)的概率。注意這里是概率，而不是像 Kmeans 中確定每個樣本點屬于男女生哪個類，取值是0或1，而非概率。對應(yīng)到高斯混合模型中，就是 Expectation（期望）這一步。參考 Kmeans，首先會隨機初始化聚類中心，Kmeans 中的這個聚類中心對應(yīng)到高斯混合模型中就是男女生兩個簇的高斯分布參數(shù)。這就需要先估計每個樣本所屬的類別，然后根據(jù)每個樣本估計的類別，計算男女生兩個類別的高斯分布的參數(shù)，然后不斷迭代。如上一節(jié)中所介紹，如果我們知道每條樣本所屬的類別后，可以很容易得計算出男女生兩個類所對應(yīng)的高斯分布的參數(shù)。在這種情況下，求如何將這 20 個身高數(shù)據(jù)聚成男女生兩大類。在本節(jié)中主要介紹高斯混合模型這兩步的原理，至于這兩步的計算公式是如何得到的，會在下一節(jié)介紹。這時，需要利用EM算法，即期望最大化算法求解參數(shù)。高斯混合分布首先將該問題轉(zhuǎn)換為包含隱變量（即每條樣本屬于不同類別的概率）和模型參數(shù)（即男女生兩個高斯分布的參數(shù)）的極大似然估計問題。從下圖可以看出，身高在 150cm 到 180cm 之間分布。假設(shè)我們已知班上所有同學(xué)的性別，如下圖所示，那么可以很容易根據(jù)樣本身高和樣本類別求得男生身高和女生身高這兩個高斯分布的參數(shù)。對比 Kmeans，高斯混合的不同之處在于，樣本點屬于某簇的概率不是非零即 1 的，而是屬于不同簇有不同的概率值。不斷迭代這兩個步驟，當(dāng)聚類中心不再發(fā)生變化或者達到最大迭代次數(shù)時結(jié)束。然后對形成的每個簇，重新計算聚類中心，計算方式為簇內(nèi)所有樣本點的均值。這兩個模型的思想有相似之處。聚類和分類的區(qū)別在于，待聚類的樣本標簽是未知的，需要根據(jù)樣本分布情況，將樣本聚成不同的簇，每一簇代表相似的群體。分類模型根據(jù)樣本標簽和樣本數(shù)據(jù)訓(xùn)練分類模型，如 SVM，決策樹等模型；關(guān)聯(lián)規(guī)則挖掘頻繁項集之間的共現(xiàn)規(guī)則。則停止迭代，最終強分類器為G(x) = * G1(x) + * G2(x) + * G3(x)。 x , 則 y = 1。 x , 則 y = 1。 x , 則 y = 1。此時強分類器為G(x) = * G1(x) + * G2(x) + * G3(x)。 x , 則 y = 1。此時錯誤率為2 * = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。 * 2 + + = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。 + = 。. 第三輪迭代 選擇最優(yōu)弱分類器，得弱分類器x ,則 y = 1。 x , 則 y = 1。 x , 則 y = 1。此時強分類器為G(x) = * G1(x) + * G2(x)。 計算最優(yōu)弱分類器的權(quán)重alpha = * ln((1 –) / ) = 。，則最優(yōu)弱分類器為x ,則 y = 1。 x , 則 y = 1。 * 3 = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。此時錯誤率為1 * = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。則強分類器的錯誤率為1 / 6 = 。G1(x)為x ,則 y = 1。 計算最優(yōu)弱分類器的權(quán)重alpha = * ln((1 – ) / ) = 更新樣本權(quán)重x = 0, 1, 2, 3, 5時，y分類正確，則樣本權(quán)重為： * exp() = x = 4時，y分類錯誤，則樣本權(quán)重為： * exp() = * 5 + = 規(guī)范化后，x = 0, 1, 2, 3, 5時，樣本權(quán)重更新為： / = x = 4時, 樣本權(quán)重更新為： / = 綜上，新的樣本權(quán)重為(, , , , , )。，則最優(yōu)弱分類器為x ,則 y = 1。 x , 則 y = 1。此時錯誤率為3 * = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。此時錯誤率為1 * = 。，得弱分類器x ,則 y = 1。 x , 則 y = 1。表格 , , , , 。如使用本系列上篇文章介紹的 CART 樹中的分類樹作為弱分類器，可訓(xùn)練出提升分類樹模型。為方便說明，本文所用弱分類器為形如x,則y=1，否則y=1的簡單分類算法。. 用例子解釋 AdaBoost 原理本節(jié)主要用示例數(shù)據(jù)詳細說明用上節(jié)介紹的 AdaBoost 原理進行分類的過程。. 迭代終止條件不斷重復(fù)1,2,3步驟，直到達到終止條件為止。當(dāng)樣本被正確分類時，y 和 Gm 取值一致，則新樣本權(quán)重變小；當(dāng)樣本被錯誤分類時，y 和 Gm 取值不一致，則新樣本權(quán)重變大。w 是樣本權(quán)重。樣本權(quán)重更新公式如下：其中m = 1,2,..,M，代表第 m 輪迭代。這樣可以使分類精度高的弱分類器起到更大的作用，并削弱精度低的弱分類器的作用。. 計算最優(yōu)弱分類器的權(quán)重最優(yōu)弱分類器的權(quán)重只與該弱分類器的錯誤率有關(guān)。取錯誤率最低的弱分類器為當(dāng)前迭代的最優(yōu)弱分類器。w 是樣本權(quán)重。錯誤率的計算公式是：其中m = 1,2,..,M，代表第m輪迭代。每一輪迭代的樣本權(quán)重都不相同，依賴于弱分類器的權(quán)重值和上一輪迭代的樣本權(quán)重。G(x) = sign( * f(x) + * g(x) + * z(x) ). AdaBoost原理AdaBoost 的核心就是不斷迭代訓(xùn)練弱分類器，并計算弱分類器的權(quán)重。關(guān)于 oneverusrest 的細節(jié)可以參考本系列第一篇文章 SVM。當(dāng)然，就如每一個算法都有自己的優(yōu)缺點一樣，AdaBoost 也有自身的缺點。這就可以充分利用不同分類算法的優(yōu)勢進行建模。本文將重點介紹用 AdaBoost 進行分類的算法原理。值得注意的是，AdaBoost 不止適用于分類模型，也可以用來訓(xùn)練回歸模型。這類 boosting 算法的特點是各個弱分類器之間是串行訓(xùn)練的，當(dāng)前弱分類器的訓(xùn)練依賴于上一輪弱分類器的訓(xùn)練結(jié)果。為什么要這樣做呢？因為弱分類器訓(xùn)練起來很容易，將弱分類器集成起來，往往可以得到很好的效果。本文將要介紹的是分類模型中的另一種模型，AdaBoost（adaptive boosting），即自適應(yīng)提升算法。8. Adaboost基本原理前面內(nèi)容涵蓋了分類、回歸、關(guān)聯(lián)分析等諸多模型，其中分類模型被介紹得最多。 面積 = 21, 價格 = }的目標變量非常接近，故不繼續(xù)劃分，得葉節(jié)點值( + ) / 2 = ； 同理得子集{面積 = 35,價格 = 。 面積 = 36, 價格 = }兩個子集。按最優(yōu)特征劃分數(shù)據(jù)集以特征面積 = 21 為切分點，將數(shù)據(jù)切分為{面積 = 20,價格 = 。類別 139。類別 039。圓的39。類別 039。紅的39。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。 圓的:0, 分類:0}繼續(xù)劃分。 第二種為如果是紅的:1, 則有如下數(shù)據(jù)子集 {圓的:1,分類：1。. 分類樹表格 9 示例數(shù)據(jù)集圓的紅的分類111100010000100選擇最優(yōu)特征按特征圓的 = 1 劃分數(shù)據(jù)集，則Gini為：3/5 * Gini(D1) + 2/5 * Gini(D0)= 3/5 * [1/3 * 2/3 + 2/3 * 1/3] + 2/5 * [0]= 按特征紅的 = 1 劃分數(shù)據(jù)集，則Gini為：2/5 * Gini(D1) + 3/5 * Gini(D0)= 2/5 * [1/2 * 1/2 + 1/2 * 1/2] + 3/5 * [0]= 綜上所述，由于按特征紅的比特征圓的劃分的基尼指數(shù)小，所以特征紅的 = 1 為切分點。平方誤差不同于分類樹，回歸樹用平方誤差選擇切分點?；嶂笖?shù)：同信息增益、信息增益比作用類似，不過基尼指數(shù)相對更快假設(shè)有 N 個類，樣本屬于第 n 類的概率為Pn，則基尼指數(shù)為：若數(shù)據(jù)集按特征A取值是否等于切分點值劃分為D1和D2兩部分，則在特征A下，集合D的基尼指數(shù)為：. 回歸樹二分回歸樹也利用二分劃分數(shù)據(jù)。圖 14 回歸樹示例. CART 樹原理. 分類樹二分分類樹利用二分劃分數(shù)據(jù)?？梢钥闯鰣D 14利用切分點s將特征空間進行劃分，y是在劃分單元上的輸出值。回歸將已知數(shù)據(jù)進行擬合，對于目標變量未知的數(shù)據(jù)可以預(yù)測目標變量的值。如圖 13所示就是一個分類樹。不同之處是劃分方法。分類問題輸出特征向量對應(yīng)的分類結(jié)果，回歸問題輸出特征向量對應(yīng)的預(yù)測值。顧名思義，分類樹用于處理分類問題；回歸樹用來處理回歸問題。而且二分策略可以直接處理連續(xù)型屬性值。這就導(dǎo)致了劃分過于迅速，從而影響分類結(jié)果。它們利用信息增益和信息增益比劃分數(shù)據(jù)集。. 按最優(yōu)特征劃分數(shù)據(jù)集 決策樹按最優(yōu)特征劃分數(shù)據(jù)集方法與上節(jié) ID3 決策樹方法相同。為了便于理解，仍然使用表格 8所示數(shù)據(jù)集進行說明。類別139。類別039。圓的39。類別039。紅的39。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。 圓的:0, 分類:0}繼續(xù)劃分。 第二種為如果是紅的:1, 則得到如下數(shù)據(jù)子集 {圓的:1,分類：1。表格 8 示例數(shù)據(jù)集圓的紅的分類111100010000100. ID3決策樹選擇最優(yōu)特征表格 8數(shù)據(jù)集的信息熵為:1/5 * log(1/5) 4/5 * log(4/5) = 1. 按特征圓的劃分數(shù)據(jù)集，則信息熵為