????????? 機(jī)器學(xué)習(xí)方法有一個(gè)進(jìn)階的過程，不同的方法族，都有其基礎(chǔ)和逐漸進(jìn)化的模型。每一個(gè)更新的模型一般是對(duì)上一個(gè)簡單模型的改進(jìn)，比如SVM就直接改進(jìn)了近鄰方法，降低了保留的實(shí)例個(gè)數(shù)。

????????? 本文有大量修改，如有閱讀不適，請移步原文。

???????? 原文鏈接：www.cnblogs.com/tornadomeet/p/3395593.html

前言：

　　找工作時(shí)（IT行業(yè)），除了常見的軟件開發(fā)以外，機(jī)器學(xué)習(xí)崗位也可以當(dāng)作是一個(gè)選擇，不少計(jì)算機(jī)方向的研究生都會(huì)接觸這個(gè)，如果你的研究方向是機(jī)器學(xué)習(xí)/數(shù)據(jù)挖掘之類，且又對(duì)其非常感興趣的話，可以考慮考慮該崗位，畢竟在機(jī)器智能沒達(dá)到人類水平之前，機(jī)器學(xué)習(xí)可以作為一種重要手段，而隨著科技的不斷發(fā)展，相信這方面的人才需求也會(huì)越來越大。

　　縱觀IT行業(yè)的招聘崗位，機(jī)器學(xué)習(xí)之類的崗位還是挺少的，國內(nèi)大點(diǎn)的公司里百度，阿里，騰訊，網(wǎng)易，搜狐，華為（華為的崗位基本都是隨機(jī)分配，機(jī)器學(xué)習(xí)等崗位基本面向的是博士）等會(huì)有相關(guān)職位，另外一些國內(nèi)的中小型企業(yè)和外企也會(huì)招一小部分。當(dāng)然了，其中大部分還是百度北京要人最多，上百人。阿里的算法崗位很大一部分也是搞機(jī)器學(xué)習(xí)相關(guān)的。另外本人有幸簽約了網(wǎng)易杭州研究院的深度學(xué)習(xí)算法崗位，打算從事機(jī)器學(xué)習(xí)領(lǐng)域至少5年。非常感謝小易收留了我！

　　下面是本人在找機(jī)器學(xué)習(xí)崗位工作時(shí)，總結(jié)的常見機(jī)器學(xué)習(xí)算法（主要是一些常規(guī)分類器）大概流程和主要思想，希望對(duì)大家找機(jī)器學(xué)習(xí)崗位時(shí)有點(diǎn)幫助。實(shí)際上在面試過程中，懂這些算法的基本思想和大概流程是遠(yuǎn)遠(yuǎn)不夠的，那些面試官往往問的都是一些公司內(nèi)部業(yè)務(wù)中的課題，往往要求你不僅要懂得這些算法的理論過程，而且要非常熟悉怎樣使用它，什么場合用它，算法的優(yōu)缺點(diǎn)，以及調(diào)參經(jīng)驗(yàn)等等。說白了，就是既要會(huì)點(diǎn)理論，也要會(huì)點(diǎn)應(yīng)用，既要有點(diǎn)深度，也要有點(diǎn)廣度，否則運(yùn)氣不好的話很容易就被刷掉，因?yàn)槊總€(gè)面試官愛好不同。

??? 決策是智能化的一個(gè)重要表現(xiàn)，類似于數(shù)據(jù)庫“觸發(fā)器”的概念，其意義可以表示為：我們在什么情況下該做什么？ML領(lǐng)域“分類”概念與其類似，智能決策也是從決策條件到?jīng)Q策結(jié)果的出發(fā)，與分類類似。分類可以表示為 if() then () 語句，形象表示為BOOL邏輯的組合，if (Feature >X) Then (ClassLabel =1)，決策和觸發(fā)器也可以這樣表示。使用數(shù)據(jù)的模式識(shí)別方法，為機(jī)器學(xué)習(xí)，機(jī)器直接從數(shù)據(jù)中獲取分類函數(shù)跳過規(guī)則獲取這一步，隱式地把規(guī)則用模型的方式表現(xiàn)出來。

???????? 規(guī)律是科學(xué)的追逐目標(biāo)，發(fā)現(xiàn)規(guī)則是簡化復(fù)雜表象的方法，就像復(fù)雜的語義是由相對(duì)較少的語法規(guī)則約束，掌握了語義的形式化規(guī)則——語法，則可以利用少量的存儲(chǔ)應(yīng)對(duì)復(fù)雜的場景，機(jī)器學(xué)習(xí)是顯式或者隱式尋找復(fù)雜場景隱藏規(guī)則的過程，通過模型的方式表現(xiàn)出來。

???????? 專家系統(tǒng)第一目標(biāo)是完備性，即系統(tǒng)規(guī)則是無矛盾的。機(jī)器學(xué)習(xí)模型的第一目標(biāo)是泛化性能，模型能完成更多空間樣本的決策分類。

??????? 基于規(guī)則的專家系統(tǒng)為硬規(guī)則系統(tǒng)，規(guī)則在系統(tǒng)內(nèi)表現(xiàn)為知識(shí)，專家系統(tǒng)可以表示為機(jī)器學(xué)習(xí)模型的最終表現(xiàn)形式。盡管規(guī)則的推廣性不可能無限制增加，總有處理不了的新目標(biāo)，這也是知識(shí)獲取的來源——數(shù)據(jù)受限制決定的，并不能說明規(guī)則是錯(cuò)誤的，可以通過規(guī)則細(xì)分化——決策樹分裂來完成。

????? ? 專家系統(tǒng)的規(guī)則面對(duì)新目標(biāo)失效時(shí)，可以通過反饋重構(gòu)規(guī)則，完成規(guī)則系統(tǒng)的完備性，對(duì)應(yīng)在機(jī)器學(xué)習(xí)領(lǐng)域表現(xiàn)為“在線機(jī)器學(xué)習(xí)”，其同態(tài)映射為“在線決策樹”算法。

??????? 算法的擴(kuò)展性是機(jī)器學(xué)習(xí)算法性能衡量標(biāo)準(zhǔn)之一，機(jī)器學(xué)習(xí)算法遵循? 樣本->新場景中實(shí)例確定 因果關(guān)聯(lián)。 根據(jù)已知中間模型的類型和步驟不同，劃分為多種。“可擴(kuò)展性”、“泛化性能” 在數(shù)學(xué)系統(tǒng)的 同態(tài)映射為函數(shù) 的值域可拓延性 范圍，

????? ? ANN方法族：若 樣本-> 模型?->新場景中實(shí)例確定 模型為黑箱，則其代表為可能為神經(jīng)網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)是使用參數(shù)描述模型的代表，甚至不用知道參數(shù)的意義也可以得到好的結(jié)果，這種使用結(jié)構(gòu)來替代“決策”這種智能的描述 值得追求嗎？

??????? 概率描述方法族：若 樣本-> 模型?->新場景中實(shí)例確定 模型為先驗(yàn)概率和后驗(yàn)概率的關(guān)系，此種方法為 樸素貝葉斯，樸素貝葉斯使用 結(jié)果和規(guī)則來推測原因，利用數(shù)字化“可能性”來描述規(guī)則，必然有一定的錯(cuò)誤率，這也是其他一切模型所能達(dá)到正確率的極限了。 ??

??????? 決策樹方法族：若 樣本-> 模型?->新場景中實(shí)例確定 模型為bool邏輯規(guī)則的附加，此種方法為 決策樹方法。決策樹運(yùn)用 “And”運(yùn)算，對(duì)特征進(jìn)行優(yōu)先級(jí)分層建立樹狀結(jié)構(gòu)，利用“And”運(yùn)算完成從根部開始到葉子的遞推，完成決策過程。決策樹方法必然會(huì)出現(xiàn)過擬合現(xiàn)象，其泛化性能受樣本拓?fù)浞植继卣骷s束明顯，由于其分裂特性，決策空間劃分為塊狀，其不同父類葉子間的分類面不相關(guān)。

　　一般映射方法族：若 樣本-> 模型?->新場景中實(shí)例確定 模型表現(xiàn)為連續(xù)函數(shù)，則需要擬合，方法有線性回歸等。

??????? 近鄰查詢方法族：直接從分類的相似性要求開始，在整個(gè)模型的構(gòu)建過程中，近鄰性要求貫穿始終。

??????? 組合模型方法族：強(qiáng)化思想和泛化思想引發(fā)了兩類不同的組合分了器，Boosting和Bag方法，一個(gè)主要使用增強(qiáng)用于提高模型的精度，一個(gè)主要用于保證模型的泛化性能。

?????? 下面的分類不是很規(guī)則，如有疑問，請自行排疑.

概率描述方法族?

一. NaiveBayes樸素貝葉斯：

　　有以下幾個(gè)地方需要注意：

　　1. 如果給出的特征向量長度可能不同，這是需要?dú)w一化為通長度的向量（這里以文本分類為例），比如說是句子單詞的話，則長度為整個(gè)詞匯量的長度，對(duì)應(yīng)位置是該單詞出現(xiàn)的次數(shù)。

　　2. 計(jì)算公式如下：

?　　

　　其中一項(xiàng)條件概率可以通過樸素貝葉斯條件獨(dú)立展開。要注意一點(diǎn)就是的計(jì)算方法，而由樸素貝葉斯的前提假設(shè)可知，

= ，

因此一般有兩種，一種是在類別為ci的那些樣本集中，找到wj出現(xiàn)次數(shù)的總和，然后除以該樣本的總和；第二種方法是類別為ci的那些樣本集中，找到wj出現(xiàn)次數(shù)的總和，然后除以該樣本中所有特征出現(xiàn)次數(shù)的總和。

　　3. 如果 中的某一項(xiàng)為0，則其聯(lián)合概率的乘積也可能為0，即2中公式的分子為0，為了避免這種現(xiàn)象出現(xiàn)，一般情況下會(huì)將這一項(xiàng)初始化為1，當(dāng)然為了保證概率相等，分母應(yīng)對(duì)應(yīng)初始化為2（這里因?yàn)槭?類，所以加2，如果是k類就需要加k，術(shù)語上叫做laplace光滑, 分母加k的原因是使之滿足全概率公式）。

　　樸素貝葉斯的優(yōu)點(diǎn)：

　　對(duì)小規(guī)模的數(shù)據(jù)表現(xiàn)很好，適合多分類任務(wù)，適合增量式訓(xùn)練。

　　缺點(diǎn)：

　　對(duì)輸入數(shù)據(jù)的表達(dá)形式很敏感。

? 后記：

　　? 貝葉斯方法是已知后驗(yàn)概率，收集條件概率，求取模型的先驗(yàn)分布的方法。

?

?決策樹方法族

二.決策樹：

　　決策樹中很重要的一點(diǎn)就是選擇一個(gè)屬性進(jìn)行分枝，因此要注意一下信息增益的計(jì)算公式，并深入理解它。

　　信息熵的計(jì)算公式如下:

?　　

　　其中的n代表有n個(gè)分類類別（比如假設(shè)是2類問題，那么n=2）。分別計(jì)算這2類樣本在總樣本中出現(xiàn)的概率p1和p2，這樣就可以計(jì)算出未選中屬性分枝前的信息熵。

　　現(xiàn)在選中一個(gè)屬性xi用來進(jìn)行分枝，此時(shí)分枝規(guī)則是：如果xi=vx的話，將樣本分到樹的一個(gè)分支；如果不相等則進(jìn)入另一個(gè)分支。很顯然，分支中的樣本很有可能包括2個(gè)類別，分別計(jì)算這2個(gè)分支的熵H1和H2,計(jì)算出分枝后的總信息熵H’=p1*H1+p2*H2.，則此時(shí)的信息增益ΔH=H-H’。以信息增益為原則，把所有的屬性都測試一邊，選擇一個(gè)使增益最大的屬性作為本次分枝屬性。

　　決策樹的優(yōu)點(diǎn)：

　　計(jì)算量簡單，可解釋性強(qiáng)，比較適合處理有缺失屬性值的樣本，能夠處理不相關(guān)的特征；

　　缺點(diǎn)：

　　決策樹具有強(qiáng)表達(dá)性，因此容易過擬合，一般降低過擬合的方法為剪枝，類似于正則化，又分為后剪枝和預(yù)剪枝兩種方法（后續(xù)出現(xiàn)了隨機(jī)森林，使用隨機(jī)性來保證繁華性能，減小了過擬合現(xiàn)象）；

?

?一般函數(shù)映射方法族

三.Logistic回歸：

　　Logistic是用來分類的，是一種線性分類器，需要注意的地方有：

　　1. logistic函數(shù)表達(dá)式為：

?　　

　　其導(dǎo)數(shù)形式為：

?　　

　　2. logsitc回歸方法主要是用最大似然估計(jì)來學(xué)習(xí)的，所以單個(gè)樣本的后驗(yàn)概率為：

?　　

　　到整個(gè)樣本的后驗(yàn)概率：

?　　

　　其中：

?　　

　　通過對(duì)數(shù)進(jìn)一步化簡為：

?　　

　　3. 其實(shí)它的loss function為-l(θ)，因此我們需使loss function最小，可采用梯度下降法得到。梯度下降法公式為:

?　　

　　

　　Logistic回歸優(yōu)點(diǎn)：

　　1、實(shí)現(xiàn)簡單；

　　2、分類時(shí)計(jì)算量非常小，速度很快，存儲(chǔ)資源低；

　　缺點(diǎn)：

　　1、參數(shù)過少，容易欠擬合，一般準(zhǔn)確度不太高。

　　2、只能處理兩分類問題（在此基礎(chǔ)上衍生出來的softmax可以用于多分類），且必須線性可分；

?

?一般函數(shù)映射方法族

四.線性回歸：

　　線性回歸才是真正用于回歸的，而不像logistic回歸是用于分類，其基本思想是用梯度下降法對(duì)最小二乘法形式的誤差函數(shù)進(jìn)行優(yōu)化，當(dāng)然也可以用normal equation直接求得參數(shù)的解。

??????? 結(jié)果為：

?　　

　　而在LWLR（局部加權(quán)線性回歸）中，參數(shù)的計(jì)算表達(dá)式為:

?　　

　　因?yàn)榇藭r(shí)優(yōu)化的是：

?　　

　　由此可見LWLR與LR不同，LWLR是一個(gè)非參數(shù)模型，因?yàn)槊看芜M(jìn)行回歸計(jì)算都要遍歷訓(xùn)練樣本至少一次。

　　線性回歸優(yōu)點(diǎn)：

　　實(shí)現(xiàn)簡單，計(jì)算簡單；

　　缺點(diǎn)：

　　不能擬合非線性數(shù)據(jù)；

?

?近鄰方法族

五.KNN算法：

　　KNN即最近鄰算法，其主要過程為：

　　1. 計(jì)算訓(xùn)練樣本和測試樣本中每個(gè)樣本點(diǎn)的距離（常見的距離度量有歐式距離，馬氏距離等）；

　　2. 對(duì)上面所有的距離值進(jìn)行排序；

　　3. 選前k個(gè)最小距離的樣本；

　　4. 根據(jù)這k個(gè)樣本的標(biāo)簽進(jìn)行投票，得到最后的分類類別；

　　如何選擇一個(gè)最佳的K值，這取決于數(shù)據(jù)。一般情況下，在分類時(shí)較大的K值能夠減小噪聲的影響。但會(huì)使類別之間的界限變得模糊。一個(gè)較好的K值可通過各種啟發(fā)式技術(shù)來獲取，比如，交叉驗(yàn)證。另外噪聲和非相關(guān)性特征向量的存在會(huì)使K近鄰算法的準(zhǔn)確性減小。

　　近鄰算法具有較強(qiáng)的一致性結(jié)果。隨著數(shù)據(jù)趨于無限，算法保證錯(cuò)誤率不會(huì)超過貝葉斯算法錯(cuò)誤率的兩倍。對(duì)于一些好的K值，K近鄰保證錯(cuò)誤率不會(huì)超過貝葉斯理論誤差率。

　　注：馬氏距離一定要先給出樣本集的統(tǒng)計(jì)性質(zhì)，比如均值向量，協(xié)方差矩陣等。關(guān)于馬氏距離的介紹如下：

?　　

　　KNN算法的優(yōu)點(diǎn)：

　　1. 思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；

　　2. 可用于非線性分類；

　　3. 訓(xùn)練時(shí)間復(fù)雜度為O(n)；

　　4. 準(zhǔn)確度高，對(duì)數(shù)據(jù)沒有假設(shè)，對(duì)outlier不敏感；

　　缺點(diǎn)：

　　1. 計(jì)算量大；

　　2. 樣本不平衡問題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）；

　　3. 需要大量的內(nèi)存；

?

?近鄰搜索方法族

六.SVM：

　　要學(xué)會(huì)如何使用libsvm以及一些參數(shù)的調(diào)節(jié)經(jīng)驗(yàn)，另外需要理清楚svm算法的一些思路：

　　1. svm中的最優(yōu)分類面是對(duì)所有樣本的幾何裕量最大（為什么要選擇最大間隔分類器，請從數(shù)學(xué)角度上說明？網(wǎng)易深度學(xué)習(xí)崗位面試過程中有被問到。答案就是幾何間隔與樣本的誤分次數(shù)間存在關(guān)系： ，其中的分母就是樣本到分類間隔距離，分子中的R是所有樣本中的最長向量值），即：

?　　

　　經(jīng)過一系列推導(dǎo)可得為優(yōu)化下面原始目標(biāo)：

　　

　　2. 下面來看看拉格朗日理論：

　　

　　可以將1中的優(yōu)化目標(biāo)轉(zhuǎn)換為拉格朗日的形式（通過各種對(duì)偶優(yōu)化，KKD條件），最后目標(biāo)函數(shù)為：

?　　

　　我們只需要最小化上述目標(biāo)函數(shù)，其中的α為原始優(yōu)化問題中的不等式約束拉格朗日系數(shù)。

　　3. 對(duì)2中最后的式子分別w和b求導(dǎo)可得：

　　

　　?

　　由上面第1式子可以知道，如果我們優(yōu)化出了α，則直接可以求出w了，即模型的參數(shù)搞定。而上面第2個(gè)式子可以作為后續(xù)優(yōu)化的一個(gè)約束條件。

　　4. 對(duì)2中最后一個(gè)目標(biāo)函數(shù)用對(duì)偶優(yōu)化理論可以轉(zhuǎn)換為優(yōu)化下面的目標(biāo)函數(shù)：

　　

　　而這個(gè)函數(shù)可以用常用的優(yōu)化方法求得α，進(jìn)而求得w和b。

　　5. 按照道理，svm簡單理論應(yīng)該到此結(jié)束。不過還是要補(bǔ)充一點(diǎn)，即在預(yù)測時(shí)有：

?　　

　　那個(gè)尖括號(hào)我們可以用核函數(shù)代替，這也是svm經(jīng)常和核函數(shù)扯在一起的原因。

　　6. 最后是關(guān)于松弛變量的引入，因此原始的目標(biāo)優(yōu)化公式為：

?　　

　　此時(shí)對(duì)應(yīng)的對(duì)偶優(yōu)化公式為：

?　　

　　與前面的相比只是α多了個(gè)上界。

　　SVM算法優(yōu)點(diǎn)：

　　#相對(duì)于KNN，SVM只保存少數(shù)支持向量，且是保存的高維空間的支持向量。

?????? 可用于線性/非線性分類，也可以用于回歸；

　　相當(dāng)于剪枝，低泛化誤差；

　　支持向量的近鄰特性，容易解釋；

　　只保留少量的支持向量，計(jì)算復(fù)雜度較低；

　　缺點(diǎn)：

　　對(duì)參數(shù)和核函數(shù)的選擇比較敏感；

　　優(yōu)化方法決定SVM本質(zhì)上是一個(gè)二分類器，原始的SVM只比較擅長處理二分類問題；

?

組合模型方法族

七.Boosting：

　　主要以Adaboost為例，首先來看看Adaboost的流程圖，如下：

?　　

　　從圖中可以看到，在訓(xùn)練過程中我們需要訓(xùn)練出多個(gè)弱分類器（圖中為3個(gè)），每個(gè)弱分類器是由不同權(quán)重的樣本（圖中為5個(gè)訓(xùn)練樣本）訓(xùn)練得到（其中第一個(gè)弱分類器對(duì)應(yīng)輸入樣本的權(quán)值是一樣的），而每個(gè)弱分類器對(duì)最終分類結(jié)果的作用也不同，是通過加權(quán)平均輸出的，權(quán)值見上圖中三角形里面的數(shù)值。那么這些弱分類器和其對(duì)應(yīng)的權(quán)值是怎樣訓(xùn)練出來的呢？

　　下面通過一個(gè)例子來簡單說明。

　　書中（machinelearning in action）假設(shè)的是5個(gè)訓(xùn)練樣本，每個(gè)訓(xùn)練樣本的維度為2，在訓(xùn)練第一個(gè)分類器時(shí)5個(gè)樣本的權(quán)重各為0.2.注意這里樣本的權(quán)值和最終訓(xùn)練的弱分類器組對(duì)應(yīng)的權(quán)值α是不同的，樣本的權(quán)重只在訓(xùn)練過程中用到，而α在訓(xùn)練過程和測試過程都有用到。

　　現(xiàn)在假設(shè)弱分類器是帶一個(gè)節(jié)點(diǎn)的簡單決策樹，該決策樹會(huì)選擇2個(gè)屬性（假設(shè)只有2個(gè)屬性）的一個(gè)，然后計(jì)算出這個(gè)屬性中的最佳值用來分類。

　　Adaboost的簡單版本訓(xùn)練過程如下：

　　1. 訓(xùn)練第一個(gè)分類器，樣本的權(quán)值D為相同的均值。通過一個(gè)弱分類器，得到這5個(gè)樣本（請對(duì)應(yīng)書中的例子來看，依舊是machine learning in action）的分類預(yù)測標(biāo)簽。與給出的樣本真實(shí)標(biāo)簽對(duì)比，就可能出現(xiàn)誤差(即錯(cuò)誤)。如果某個(gè)樣本預(yù)測錯(cuò)誤，則它對(duì)應(yīng)的錯(cuò)誤值為該樣本的權(quán)重，如果分類正確，則錯(cuò)誤值為0. 最后累加5個(gè)樣本的錯(cuò)誤率之和，記為ε。

　　2. 通過ε來計(jì)算該弱分類器的權(quán)重α，公式如下：

?　　

　　3. 通過α來計(jì)算訓(xùn)練下一個(gè)弱分類器樣本的權(quán)重D，如果對(duì)應(yīng)樣本分類正確，則減小該樣本的權(quán)重，公式為：

?　　

　　如果樣本分類錯(cuò)誤，則增加該樣本的權(quán)重，公式為：

?　　

　　4. 循環(huán)步驟1,2,3來繼續(xù)訓(xùn)練多個(gè)分類器，只是其D值不同而已。

　　測試過程如下：

　　輸入一個(gè)樣本到訓(xùn)練好的每個(gè)弱分類中，則每個(gè)弱分類都對(duì)應(yīng)一個(gè)輸出標(biāo)簽，然后該標(biāo)簽乘以對(duì)應(yīng)的α，最后求和得到值的符號(hào)即為預(yù)測標(biāo)簽值。

　　Boosting算法的優(yōu)點(diǎn)：

　　低泛化誤差；

　　容易實(shí)現(xiàn)，分類準(zhǔn)確率較高，沒有太多參數(shù)可以調(diào)；

　　缺點(diǎn)：

　　Boosting方法的進(jìn)階訓(xùn)練過程中，著重強(qiáng)調(diào)了負(fù)樣本的效用。對(duì)外表現(xiàn)為，模型對(duì)outlier比較敏感；

?

?

八.聚類：

　　根據(jù)聚類思想劃分：

　　1. 基于劃分的聚類:

　　K-means, k-medoids(每一個(gè)類別中找一個(gè)樣本點(diǎn)來代表),CLARANS.

　　k-means是使下面的表達(dá)式值最小：

?　　

　　 k-means算法的優(yōu)點(diǎn)：

　　（1）k-means算法是解決聚類問題的一種經(jīng)典算法，算法簡單、快速。

　　（2）對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮的和高效率的，因?yàn)樗膹?fù)雜度大約是O(nkt)，其中n是所有對(duì)象的數(shù)目，k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n。這個(gè)算法通常局部收斂。

　　（3）算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)簇是密集的、球狀或團(tuán)狀的，且簇與簇之間區(qū)別明顯時(shí)，聚類效果較好。

　　?缺點(diǎn)：

　　（1）k-平均方法只有在簇的平均值被定義的情況下才能使用，且對(duì)有些分類屬性的數(shù)據(jù)不適合。

　　（2）要求用戶必須事先給出要生成的簇的數(shù)目k。

　　（3）對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同的聚類結(jié)果。

　　（4）不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。

　　（5）對(duì)于"噪聲"和孤立點(diǎn)數(shù)據(jù)敏感，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大影響。

　　2. 基于層次的聚類：

　　自底向上的凝聚方法，比如AGNES。

　　自上向下的分裂方法，比如DIANA。

　　3. 基于密度的聚類：

　　DBSACN,OPTICS,BIRCH(CF-Tree),CURE.

　　4. 基于網(wǎng)格的方法：

　　STING, WaveCluster.

　　5. 基于模型的聚類：

　　EM,SOM,COBWEB.

　　以上這些算法的簡介可參考聚類（百度百科）。

?

?九.推薦系統(tǒng)：

　　推薦系統(tǒng)的實(shí)現(xiàn)主要分為兩個(gè)方面：基于內(nèi)容的實(shí)現(xiàn)和協(xié)同濾波的實(shí)現(xiàn)。

　　基于內(nèi)容的實(shí)現(xiàn)：

　　不同人對(duì)不同電影的評(píng)分這個(gè)例子，可以看做是一個(gè)普通的回歸問題，因此每部電影都需要提前提取出一個(gè)特征向量(即x值)，然后針對(duì)每個(gè)用戶建模，即每個(gè)用戶打的分值作為y值，利用這些已有的分值y和電影特征值x就可以訓(xùn)練回歸模型了(最常見的就是線性回歸)。這樣就可以預(yù)測那些用戶沒有評(píng)分的電影的分?jǐn)?shù)。（值得注意的是需對(duì)每個(gè)用戶都建立他自己的回歸模型）

　　從另一個(gè)角度來看，也可以是先給定每個(gè)用戶對(duì)某種電影的喜好程度（即權(quán)值），然后學(xué)出每部電影的特征，最后采用回歸來預(yù)測那些沒有被評(píng)分的電影。

　　當(dāng)然還可以是同時(shí)優(yōu)化得到每個(gè)用戶對(duì)不同類型電影的熱愛程度以及每部電影的特征。具體可以參考Ng在coursera上的ml教程：https://www.coursera.org/course/ml

　　基于協(xié)同濾波的實(shí)現(xiàn)：

　　協(xié)同濾波（CF）可以看做是一個(gè)分類問題，也可以看做是矩陣分解問題。協(xié)同濾波主要是基于每個(gè)人自己的喜好都類似這一特征，它不依賴于個(gè)人的基本信息。比如剛剛那個(gè)電影評(píng)分的例子中，預(yù)測那些沒有被評(píng)分的電影的分?jǐn)?shù)只依賴于已經(jīng)打分的那些分?jǐn)?shù)，并不需要去學(xué)習(xí)那些電影的特征。

　　SVD將矩陣分解為三個(gè)矩陣的乘積，公式如下所示：

?　　

　　中間的矩陣sigma為對(duì)角矩陣，對(duì)角元素的值為Data矩陣的奇異值(注意奇異值和特征值是不同的)，且已經(jīng)從大到小排列好了。即使去掉特征值小的那些特征，依然可以很好的重構(gòu)出原始矩陣。如下圖所示：

　　

　　其中更深的顏色代表去掉小特征值重構(gòu)時(shí)的三個(gè)矩陣。

　　果m代表商品的個(gè)數(shù)，n代表用戶的個(gè)數(shù)，則U矩陣的每一行代表商品的屬性，現(xiàn)在通過降維U矩陣（取深色部分）后，每一個(gè)商品的屬性可以用更低的維度表示（假設(shè)為k維）。這樣當(dāng)新來一個(gè)用戶的商品推薦向量X，則可以根據(jù)公式X'*U1*inv(S1)得到一個(gè)k維的向量，然后在V’中尋找最相似的那一個(gè)用戶（相似度測量可用余弦公式等），根據(jù)這個(gè)用戶的評(píng)分來推薦（主要是推薦新用戶未打分的那些商品）。具體例子可以參考網(wǎng)頁：SVD在推薦系統(tǒng)中的應(yīng)用。

　　另外關(guān)于SVD分解后每個(gè)矩陣的實(shí)際含義可以參考google吳軍的《數(shù)學(xué)之美》一書（不過個(gè)人感覺吳軍解釋UV兩個(gè)矩陣時(shí)好像弄反了，不知道大家怎樣認(rèn)為）。或者參考machinelearning in action其中的svd章節(jié)。

?

?

十.pLSA:

　　pLSA由LSA發(fā)展過來，而早期LSA的實(shí)現(xiàn)主要是通過SVD分解。pLSA的模型圖如下：

?　　

　　公式中的意義如下：

?　　

　　具體可以參考2010龍星計(jì)劃：機(jī)器學(xué)習(xí)中對(duì)應(yīng)的主題模型那一講

?

?

十一、LDA：

　　主題模型，概率圖如下：

?　　

　　和pLSA不同的是LDA中假設(shè)了很多先驗(yàn)分布，且一般參數(shù)的先驗(yàn)分布都假設(shè)為Dirichlet分布，其原因是共軛分布時(shí)先驗(yàn)概率和后驗(yàn)概率的形式相同。

?

?

組合模型方法

　　GDBT：

　　GBDT(Gradient?Boosting?Decision?Tree)?又叫?MART（Multiple?Additive?Regression?Tree)，好像在阿里內(nèi)部用得比較多（所以阿里算法崗位面試時(shí)可能會(huì)問到），它是一種迭代的決策樹算法，該算法由多棵決策樹組成，所有樹的輸出結(jié)果累加起來就是最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強(qiáng)的算法。近些年更因?yàn)楸挥糜谒阉髋判虻臋C(jī)器學(xué)習(xí)模型而引起大家關(guān)注。

　　GBDT是回歸樹，不是分類樹。其核心就在于，每一棵樹是從之前所有樹的殘差中來學(xué)習(xí)的。為了防止過擬合，和Adaboosting一樣，也加入了boosting這一項(xiàng)。這種學(xué)習(xí)方法即包含了Boosting的基本思想。

　　關(guān)于GDBT的介紹可以可以參考：GBDT（MART） 迭代決策樹入門教程 | 簡介。

?

?正則化，用于剪枝降低過擬合

　　Regularization:

　　作用是（網(wǎng)易電話面試時(shí)有問到）：

　　1. 數(shù)值上更容易求解；

　　2. 特征數(shù)目太大時(shí)更穩(wěn)定；

　　3. 控制模型的復(fù)雜度，光滑性。復(fù)雜性越小且越光滑的目標(biāo)函數(shù)泛化能力越強(qiáng)。而加入規(guī)則項(xiàng)能使目標(biāo)函數(shù)復(fù)雜度減小，且更光滑。

　　4. 減小參數(shù)空間；參數(shù)空間越小，復(fù)雜度越低。

　　5. 系數(shù)越小，模型越簡單，而模型越簡單則泛化能力越強(qiáng)（Ng宏觀上給出的解釋）。

　　6. 可以看出是權(quán)值的高斯先驗(yàn)。

?

?

　　異常檢測：

　　可以估計(jì)樣本的密度函數(shù)，對(duì)于新樣本直接計(jì)算其密度，如果密度值小于某一閾值，則表示該樣本異常。而密度函數(shù)一般采用多維的高斯分布。如果樣本有n維，則每一維的特征都可以看作是符合高斯分布的，即使這些特征可視化出來不太符合高斯分布，也可以對(duì)該特征進(jìn)行數(shù)學(xué)轉(zhuǎn)換讓其看起來像高斯分布，比如說x=log(x+c),x=x^(1/c)等。異常檢測的算法流程如下：

?　　

?　　其中的ε也是通過交叉驗(yàn)證得到的，也就是說在進(jìn)行異常檢測時(shí)，前面的p(x)的學(xué)習(xí)是用的無監(jiān)督，后面的參數(shù)ε學(xué)習(xí)是用的有監(jiān)督。那么為什么不全部使用普通有監(jiān)督的方法來學(xué)習(xí)呢（即把它看做是一個(gè)普通的二分類問題）？主要是因?yàn)樵诋惓z測中，異常的樣本數(shù)量非常少而正常樣本數(shù)量非常多，因此不足以學(xué)習(xí)到好的異常行為模型的參數(shù)，因?yàn)楹竺嫘聛淼漠惓颖究赡芡耆桥c訓(xùn)練樣本中的模式不同。

　　另外，上面是將特征的每一維看成是相互獨(dú)立的高斯分布，其實(shí)這樣的近似并不是最好的，但是它的計(jì)算量較小，因此也常被使用。更好的方法應(yīng)該是將特征擬合成多維高斯分布，這時(shí)有特征之間的相關(guān)性，但隨之計(jì)算量會(huì)變復(fù)雜，且樣本的協(xié)方差矩陣還可能出現(xiàn)不可逆的情況（主要在樣本數(shù)比特征數(shù)小，或者樣本特征維數(shù)之間有線性關(guān)系時(shí)）。

　　上面的內(nèi)容可以參考Ng的https://www.coursera.org/course/ml

?

?

　　EM算法：

　　有時(shí)候因?yàn)闃颖镜漠a(chǎn)生和隱含變量有關(guān)（隱含變量是不能觀察的），而求模型的參數(shù)時(shí)一般采用最大似然估計(jì)，由于含有了隱含變量，所以對(duì)似然函數(shù)參數(shù)求導(dǎo)是求不出來的，這時(shí)可以采用EM算法來求模型的參數(shù)的（對(duì)應(yīng)模型參數(shù)個(gè)數(shù)可能有多個(gè)），EM算法一般分為2步：

　　E步：選取一組參數(shù)，求出在該參數(shù)下隱含變量的條件概率值；

　　M步：結(jié)合E步求出的隱含變量條件概率，求出似然函數(shù)下界函數(shù)（本質(zhì)上是某個(gè)期望函數(shù)）的最大值。

　　重復(fù)上面2步直至收斂。

　　公式如下所示：

?　　

　　M步公式中下界函數(shù)的推導(dǎo)過程：

?　　

　　EM算法一個(gè)常見的例子就是GMM模型，每個(gè)樣本都有可能由k個(gè)高斯產(chǎn)生，只不過由每個(gè)高斯產(chǎn)生的概率不同而已，因此每個(gè)樣本都有對(duì)應(yīng)的高斯分布（k個(gè)中的某一個(gè)），此時(shí)的隱含變量就是每個(gè)樣本對(duì)應(yīng)的某個(gè)高斯分布。

　　GMM的E步公式如下（計(jì)算每個(gè)樣本對(duì)應(yīng)每個(gè)高斯的概率）：

?　　

　　更具體的計(jì)算公式為：

　　

　　M步公式如下（計(jì)算每個(gè)高斯的比重，均值，方差這3個(gè)參數(shù)）：

?　　

　　關(guān)于EM算法可以參考Ng的cs229課程資料 或者網(wǎng)易公開課：斯坦福大學(xué)公開課 ：機(jī)器學(xué)習(xí)課程。

?

關(guān)聯(lián)模式分析

　　Apriori:

　　Apriori是關(guān)聯(lián)分析中比較早的一種方法，主要用來挖掘那些頻繁項(xiàng)集合。其思想是：

　　1. 如果一個(gè)項(xiàng)目集合不是頻繁集合，那么任何包含它的項(xiàng)目集合也一定不是頻繁集合；

　　2. 如果一個(gè)項(xiàng)目集合是頻繁集合，那么它的任何非空子集也是頻繁集合；

　　Aprioir需要掃描項(xiàng)目表多遍，從一個(gè)項(xiàng)目開始掃描，舍去掉那些不是頻繁的項(xiàng)目，得到的集合稱為L，然后對(duì)L中的每個(gè)元素進(jìn)行自組合，生成比上次掃描多一個(gè)項(xiàng)目的集合，該集合稱為C，接著又掃描去掉那些非頻繁的項(xiàng)目，重復(fù)…

　　看下面這個(gè)例子：

　　元素項(xiàng)目表格：

?　　

　　如果每個(gè)步驟不去掉非頻繁項(xiàng)目集，則其掃描過程的樹形結(jié)構(gòu)如下：

?　　

　　在其中某個(gè)過程中，可能出現(xiàn)非頻繁的項(xiàng)目集，將其去掉（用陰影表示）為：

?　　

　　上面的內(nèi)容主要參考的是machinelearning in action這本書。

?

?關(guān)聯(lián)模式分析方法

　　FP Growth:

　　FPGrowth是一種比Apriori更高效的頻繁項(xiàng)挖掘方法，它只需要掃描項(xiàng)目表2次。其中第1次掃描獲得當(dāng)個(gè)項(xiàng)目的頻率，去掉不符合支持度要求的項(xiàng)，并對(duì)剩下的項(xiàng)排序。第2遍掃描是建立一顆FP-Tree(frequent-pattentree)。

　　接下來的工作就是在FP-Tree上進(jìn)行挖掘。

　　比如說有下表：

?　　

　　它所對(duì)應(yīng)的FP_Tree如下：

?　　

　　然后從頻率最小的單項(xiàng)P開始，找出P的條件模式基，用構(gòu)造FP_Tree同樣的方法來構(gòu)造P的條件模式基的FP_Tree，在這棵樹上找出包含P的頻繁項(xiàng)集。

　　依次從m,b,a,c,f的條件模式基上挖掘頻繁項(xiàng)集，有些項(xiàng)需要遞歸的去挖掘，比較麻煩，比如m節(jié)點(diǎn)，具體的過程可以參考博客：Frequent?Pattern?挖掘之二(FP?Growth算法)，里面講得很詳細(xì)。

??????? 此種樹的詳細(xì)編寫過程可以參考書籍《機(jī)器學(xué)習(xí)實(shí)踐指南》，給出了完整的Python版本。

?

?

　　參考資料：

　 Harrington, P. (2012). Machine Learningin Action, Manning Publications Co.

? ? ??最近鄰算法（維基百科）

? ? ??馬氏距離（維基百科）

　 聚類（百度百科）

? ? ??https://www.coursera.org/course/ml

? ? ??SVD在推薦系統(tǒng)中的應(yīng)用

? ? ? 吳軍 and 谷歌 (2012).數(shù)學(xué)之美, 人民郵電出版社.

? ? ??2010龍星計(jì)劃：機(jī)器學(xué)習(xí)對(duì)應(yīng)的視頻教程：2010龍星計(jì)劃機(jī)器學(xué)習(xí)視頻教程

? ? ??GBDT（MART） 迭代決策樹入門教程 | 簡介

? ? ??Ng的cs229課程資料

? ? ??斯坦福大學(xué)公開課 ：機(jī)器學(xué)習(xí)課程

? ? ??Frequent?Pattern?挖掘之二(FP?Growth算法)

總結(jié)

以上是生活随笔為你收集整理的ML大杂烩:**常见机器学习算法公式梳理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。