常見機(jī)器學(xué)習(xí)算法優(yōu)缺點(diǎn):
樸素貝葉斯:
1. 如果給出的特征向量長度可能不同,這是需要?dú)w一化為通長度的向量(這里以文本分類為例),比如說是句子單詞的話,則長度為整個(gè)詞匯量的長度,對應(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),一般情況下會將這一項(xiàng)初始化為1,當(dāng)然為了保證概率相等,分母應(yīng)對應(yīng)初始化為2(這里因?yàn)槭?類,所以加2,如果是k類就需要加k,術(shù)語上叫做laplace光滑, 分母加k的原因是使之滿足全概率公式)。
樸素貝葉斯的優(yōu)點(diǎn):對小規(guī)模的數(shù)據(jù)表現(xiàn)很好,適合多分類任務(wù),適合增量式訓(xùn)練。
缺點(diǎn):對輸入數(shù)據(jù)的表達(dá)形式很敏感。
決策樹:決策樹中很重要的一點(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):容易過擬合(后續(xù)出現(xiàn)了隨機(jī)森林,減小了過擬合現(xiàn)象)。
Logistic回歸:Logistic是用來分類的,是一種線性分類器,需要注意的地方有:
1. logistic函數(shù)表達(dá)式為:
其導(dǎo)數(shù)形式為:
2. logsitc回歸方法主要是用最大似然估計(jì)來學(xué)習(xí)的,所以單個(gè)樣本的后驗(yàn)概率為:
到整個(gè)樣本的后驗(yàn)概率:
其中:
通過對數(shù)進(jìn)一步化簡為:
3. 其實(shí)它的loss function為-l(θ),因此我們需使loss function最小,可采用梯度下降法得到。梯度下降法公式為:
Logistic回歸優(yōu)點(diǎn):
1. 實(shí)現(xiàn)簡單
2. 分類時(shí)計(jì)算量非常小,速度很快,存儲資源低;
缺點(diǎn):
1. 容易欠擬合,一般準(zhǔn)確度不太高
2. 只能處理兩分類問題(在此基礎(chǔ)上衍生出來的softmax可以用于多分類),且必須線性可分;
線性回歸:
線性回歸才是真正用于回歸的,而不像logistic回歸是用于分類,其基本思想是用梯度下降法對最小二乘法形式的誤差函數(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. 對上面所有的距離值進(jìn)行排序;
3. 選前k個(gè)最小距離的樣本;
4. 根據(jù)這k個(gè)樣本的標(biāo)簽進(jìn)行投票,得到最后的分類類別;
如何選擇一個(gè)最佳的K值,這取決于數(shù)據(jù)。一般情況下,在分類時(shí)較大的K值能夠減小噪聲的影響。但會使類別之間的界限變得模糊。一個(gè)較好的K值可通過各種啟發(fā)式技術(shù)來獲取,比如,交叉驗(yàn)證。另外噪聲和非相關(guān)性特征向量的存在會使K近鄰算法的準(zhǔn)確性減小。
近鄰算法具有較強(qiáng)的一致性結(jié)果。隨著數(shù)據(jù)趨于無限,算法保證錯(cuò)誤率不會超過貝葉斯算法錯(cuò)誤率的兩倍。對于一些好的K值,K近鄰保證錯(cuò)誤率不會超過貝葉斯理論誤差率。
注:馬氏距離一定要先給出樣本集的統(tǒng)計(jì)性質(zhì),比如均值向量,協(xié)方差矩陣等。關(guān)于馬氏距離的介紹如下:
KNN算法的優(yōu)點(diǎn):
1. 思想簡單,理論成熟,既可以用來做分類也可以用來做回歸;
2. 可用于非線性分類;
3. 訓(xùn)練時(shí)間復(fù)雜度為O(n);
4. 準(zhǔn)確度高,對數(shù)據(jù)沒有假設(shè),對outlier不敏感;
缺點(diǎn):
1. 計(jì)算量大;
2. 樣本不平衡問題(即有些類別的樣本數(shù)量很多,而其它樣本的數(shù)量很少);
3. 需要大量的內(nèi)存;
SVM:
要學(xué)會如何使用libsvm以及一些參數(shù)的調(diào)節(jié)經(jīng)驗(yàn),另外需要理清楚svm算法的一些思路:
1. svm中的最優(yōu)分類面是對所有樣本的幾何裕量最大(為什么要選擇最大間隔分類器,請從數(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)換為拉格朗日的形式(通過各種對偶優(yōu)化,KKD條件),最后目標(biāo)函數(shù)為:
我們只需要最小化上述目標(biāo)函數(shù),其中的α為原始優(yōu)化問題中的不等式約束拉格朗日系數(shù)。
3. 對2中最后的式子分別w和b求導(dǎo)可得:
由上面第1式子可以知道,如果我們優(yōu)化出了α,則直接可以求出w了,即模型的參數(shù)搞定。而上面第2個(gè)式子可以作為后續(xù)優(yōu)化的一個(gè)約束條件。
4. 對2中最后一個(gè)目標(biāo)函數(shù)用對偶優(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è)尖括號我們可以用核函數(shù)代替,這也是svm經(jīng)常和核函數(shù)扯在一起的原因。
6. 最后是關(guān)于松弛變量的引入,因此原始的目標(biāo)優(yōu)化公式為:
此時(shí)對應(yīng)的對偶優(yōu)化公式為:
與前面的相比只是α多了個(gè)上界。
SVM算法優(yōu)點(diǎn):
1. 可用于線性/非線性分類,也可以用于回歸;
2. 低泛化誤差;
3. 容易解釋;
4. 計(jì)算復(fù)雜度較低;
缺點(diǎn):
1. 對參數(shù)和核函數(shù)的選擇比較敏感;
2. 原始的SVM只比較擅長處理二分類問題;
Boosting:
主要以Adaboost為例,首先來看看Adaboost的流程圖,如下:
從圖中可以看到,在訓(xùn)練過程中我們需要訓(xùn)練出多個(gè)弱分類器(圖中為3個(gè)),每個(gè)弱分類器是由不同權(quán)重的樣本(圖中為5個(gè)訓(xùn)練樣本)訓(xùn)練得到(其中第一個(gè)弱分類器對應(yīng)輸入樣本的權(quán)值是一樣的),而每個(gè)弱分類器對最終分類結(jié)果的作用也不同,是通過加權(quán)平均輸出的,權(quán)值見上圖中三角形里面的數(shù)值。那么這些弱分類器和其對應(yīng)的權(quán)值是怎樣訓(xùn)練出來的呢?
下面通過一個(gè)例子來簡單說明,假設(shè)的是5個(gè)訓(xùn)練樣本,每個(gè)訓(xùn)練樣本的維度為2,在訓(xùn)練第一個(gè)分類器時(shí)5個(gè)樣本的權(quán)重各為0.2. 注意這里樣本的權(quán)值和最終訓(xùn)練的弱分類器組對應(yīng)的權(quán)值α是不同的,樣本的權(quán)重只在訓(xùn)練過程中用到,而α在訓(xùn)練過程和測試過程都有用到。
現(xiàn)在假設(shè)弱分類器是帶一個(gè)節(jié)點(diǎn)的簡單決策樹,該決策樹會選擇2個(gè)屬性(假設(shè)只有2個(gè)屬性)的一個(gè),然后計(jì)算出這個(gè)屬性中的最佳值用來分類。
Adaboost的簡單版本訓(xùn)練過程如下:
1. 訓(xùn)練第一個(gè)分類器,樣本的權(quán)值D為相同的均值。通過一個(gè)弱分類器,得到這5個(gè)樣本(請對應(yīng)書中的例子來看,依舊是machine learning in action)的分類預(yù)測標(biāo)簽。與給出的樣本真實(shí)標(biāo)簽對比,就可能出現(xiàn)誤差(即錯(cuò)誤)。如果某個(gè)樣本預(yù)測錯(cuò)誤,則它對應(yīng)的錯(cuò)誤值為該樣本的權(quán)重,如果分類正確,則錯(cuò)誤值為0. 最后累加5個(gè)樣本的錯(cuò)誤率之和,記為ε。
2. 通過ε來計(jì)算該弱分類器的權(quán)重α,公式如下:
3. 通過α來計(jì)算訓(xùn)練下一個(gè)弱分類器樣本的權(quán)重D,如果對應(yīng)樣本分類正確,則減小該樣本的權(quán)重,公式為:
如果樣本分類錯(cuò)誤,則增加該樣本的權(quán)重,公式為:
4. 循環(huán)步驟1,2,3來繼續(xù)訓(xùn)練多個(gè)分類器,只是其D值不同而已。
測試過程如下:
輸入一個(gè)樣本到訓(xùn)練好的每個(gè)弱分類中,則每個(gè)弱分類都對應(yīng)一個(gè)輸出標(biāo)簽,然后該標(biāo)簽乘以對應(yīng)的α,最后求和得到值的符號即為預(yù)測標(biāo)簽值。
Boosting算法的優(yōu)點(diǎn):
1. 低泛化誤差;
2. 容易實(shí)現(xiàn),分類準(zhǔn)確率較高,沒有太多參數(shù)可以調(diào);
3. 缺點(diǎn):
4. 對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)對處理大數(shù)據(jù)集,該算法是相對可伸縮的和高效率的,因?yàn)樗膹?fù)雜度大約是O(nkt),其中n是所有對象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n。這個(gè)算法通常局部收斂。
(3)算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)簇是密集的、球狀或團(tuán)狀的,且簇與簇之間區(qū)別明顯時(shí),聚類效果較好。
缺點(diǎn):
(1)k-平均方法只有在簇的平均值被定義的情況下才能使用,且對有些分類屬性的數(shù)據(jù)不適合。
(2)要求用戶必須事先給出要生成的簇的數(shù)目k。
(3)對初值敏感,對于不同的初始值,可能會導(dǎo)致不同的聚類結(jié)果。
(4)不適合于發(fā)現(xiàn)非凸面形狀的簇,或者大小差別很大的簇。
(5)對于"噪聲"和孤立點(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):不同人對不同電影的評分這個(gè)例子,可以看做是一個(gè)普通的回歸問題,因此每部電影都需要提前提取出一個(gè)特征向量(即x值),然后針對每個(gè)用戶建模,即每個(gè)用戶打的分值作為y值,利用這些已有的分值y和電影特征值x就可以訓(xùn)練回歸模型了(最常見的就是線性回歸)。
這樣就可以預(yù)測那些用戶沒有評分的電影的分?jǐn)?shù)。(值得注意的是需對每個(gè)用戶都建立他自己的回歸模型)
從另一個(gè)角度來看,也可以是先給定每個(gè)用戶對某種電影的喜好程度(即權(quán)值),然后學(xué)出每部電影的特征,最后采用回歸來預(yù)測那些沒有被評分的電影。
當(dāng)然還可以是同時(shí)優(yōu)化得到每個(gè)用戶對不同類型電影的熱愛程度以及每部電影的特征。
基于協(xié)同濾波的實(shí)現(xiàn):協(xié)同濾波(CF)可以看做是一個(gè)分類問題,也可以看做是矩陣分解問題。協(xié)同濾波主要是基于每個(gè)人自己的喜好都類似這一特征,它不依賴于個(gè)人的基本信息。
比如剛剛那個(gè)電影評分的例子中,預(yù)測那些沒有被評分的電影的分?jǐn)?shù)只依賴于已經(jīng)打分的那些分?jǐn)?shù),并不需要去學(xué)習(xí)那些電影的特征。
SVD將矩陣分解為三個(gè)矩陣的乘積,公式如下所示:
中間的矩陣sigma為對角矩陣,對角元素的值為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è)用戶的評分來推薦(主要是推薦新用戶未打分的那些商品)。
pLSA:由LSA發(fā)展過來,而早期LSA的實(shí)現(xiàn)主要是通過SVD分解。pLSA的模型圖如下
公式中的意義如下:
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í)可能會問到),它是一種迭代的決策樹算法,該算法由多棵決策樹組成,所有樹的輸出結(jié)果累加起來就是最終答案。
它在被提出之初就和SVM一起被認(rèn)為是泛化能力(generalization)較強(qiáng)的算法。近些年更因?yàn)楸挥糜谒阉髋判虻臋C(jī)器學(xué)習(xí)模型而引起大家關(guān)注。
GBDT是回歸樹,不是分類樹。其核心就在于,每一棵樹是從之前所有樹的殘差中來學(xué)習(xí)的。為了防止過擬合,和Adaboosting一樣,也加入了boosting這一項(xiàng)。
Regularization作用是
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ù),對于新樣本直接計(jì)算其密度,如果密度值小于某一閾值,則表示該樣本異常。而密度函數(shù)一般采用多維的高斯分布。
如果樣本有n維,則每一維的特征都可以看作是符合高斯分布的,即使這些特征可視化出來不太符合高斯分布,也可以對該特征進(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)練樣本中的模式不同。
EM算法:有時(shí)候因?yàn)闃颖镜漠a(chǎn)生和隱含變量有關(guān)(隱含變量是不能觀察的),而求模型的參數(shù)時(shí)一般采用最大似然估計(jì),由于含有了隱含變量,所以對似然函數(shù)參數(shù)求導(dǎo)是求不出來的,這時(shí)可以采用EM算法來求模型的參數(shù)的(對應(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è)樣本都有對應(yīng)的高斯分布(k個(gè)中的某一個(gè)),此時(shí)的隱含變量就是每個(gè)樣本對應(yīng)的某個(gè)高斯分布。
GMM的E步公式如下(計(jì)算每個(gè)樣本對應(yīng)每個(gè)高斯的概率):
更具體的計(jì)算公式為:
M步公式如下(計(jì)算每個(gè)高斯的比重,均值,方差這3個(gè)參數(shù)):
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,然后對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)目集,將其去掉(用陰影表示)為:
FP Growth是一種比Apriori更高效的頻繁項(xiàng)挖掘方法,它只需要掃描項(xiàng)目表2次。其中第1次掃描獲得當(dāng)個(gè)項(xiàng)目的頻率,去掉不符合支持度要求的項(xiàng),并對剩下的項(xiàng)排序。第2遍掃描是建立一顆FP-Tree(frequent-patten tree)。
接下來的工作就是在FP-Tree上進(jìn)行挖掘,比如說有下表:
它所對應(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)。