http://www.searchtb.com/2010/12/an-introduction-to-treelink.html
“機(jī)器學(xué)習(xí)”這個(gè)名詞對(duì)大家來(lái)說(shuō)想必不是一個(gè)陌生的詞匯，特別對(duì)算法組的同學(xué)來(lái)說(shuō)，工作中或多或少接觸使用過(guò)這種“高科技“。對(duì)于我來(lái)說(shuō)，剛來(lái)淘寶工作一個(gè)月就開(kāi)始接觸了機(jī)器學(xué)習(xí)，當(dāng)時(shí)做主搜索功夫熊貓項(xiàng)目，和小致飄雪一起做交易模型，正是使用了機(jī)器學(xué)習(xí)的方法，也首次接觸了treelink模型。做完那個(gè)項(xiàng)目后對(duì)機(jī)器學(xué)習(xí)解決問(wèn)題的流程有了一定的了解，但對(duì)其內(nèi)部的工作原理和實(shí)現(xiàn)機(jī)制還是完全不知道，基本也就是在黑盒使用機(jī)器學(xué)習(xí)工具。后面也多多少少聽(tīng)了一些機(jī)器學(xué)習(xí)的講座，但都是一些比較寬泛的基本概念，沒(méi)有深入的原理性的介紹。也自己嘗試過(guò)專(zhuān)研一下，但生硬晦澀的E文讓人望而生畏。一直到今年做導(dǎo)購(gòu)搜索的項(xiàng)目，又再次需要使用機(jī)器學(xué)習(xí)，“懷揣著對(duì)科學(xué)真理的向往”，主動(dòng)請(qǐng)纓做模型方面的工作。經(jīng)過(guò)一個(gè)多月的學(xué)習(xí)實(shí)踐，算是對(duì)treelink模型有了一定的了解。下面做一些對(duì)treelink模型通俗版的介紹。都是自己的一些理解，如果有誤，多指教。
在介紹treelink之前首先不得不簡(jiǎn)單介紹一下決策樹(shù)算法，決策樹(shù)相信大家都有所了解，任何一本機(jī)器學(xué)習(xí)書(shū)籍都會(huì)介紹這種算法，也是應(yīng)用最廣的歸納推理算法之一。該模型學(xué)習(xí)的結(jié)果是一棵決策樹(shù)，這棵決策樹(shù)可以被表示成多個(gè)if-else的規(guī)則。下圖是一個(gè)典型的學(xué)習(xí)得到?jīng)Q策樹(shù)。這棵決策樹(shù)根據(jù)兩個(gè)特征因素來(lái)分類(lèi)“元涵今天的心情好壞”。長(zhǎng)方形的表示特征，橢圓型的表示特征的取值，最下面的葉子節(jié)點(diǎn)就是最后的分類(lèi)結(jié)果了。
學(xué)習(xí)得到如上這棵決策樹(shù)之后，當(dāng)輸入一個(gè)待預(yù)測(cè)的樣本實(shí)例的時(shí)候，我們就可以根據(jù)這個(gè)樣本的兩個(gè)特征的取值來(lái)把這個(gè)樣本劃分到某一個(gè)葉子節(jié)點(diǎn)，得到分類(lèi)結(jié)果了，這就是決策樹(shù)模型的預(yù)測(cè)過(guò)程，決策樹(shù)的學(xué)習(xí)構(gòu)建過(guò)程這里就不介紹了，大家看書(shū)吧，比較經(jīng)典的有ID3算法和C4.5算法。
切入正題下面開(kāi)始說(shuō)treelink算法，treelink這個(gè)名字其實(shí)只是我們阿里集團(tuán)內(nèi)部的叫法，學(xué)術(shù)上的名稱(chēng)叫GBDT（Gradientboost decisiontree）。treelink模型不像決策樹(shù)模型那樣僅由一棵決策樹(shù)構(gòu)成，而是由多棵決策樹(shù)構(gòu)成，通常都是上百棵樹(shù)，而且每棵樹(shù)規(guī)模都較?。礃?shù)的深度會(huì)比較淺）。模型預(yù)測(cè)的時(shí)候，對(duì)于輸入的一個(gè)樣本實(shí)例，首先會(huì)賦予一個(gè)初值，然后會(huì)遍歷每一棵決策樹(shù)，每棵樹(shù)都會(huì)對(duì)預(yù)測(cè)值進(jìn)行調(diào)整修正，最后得到預(yù)測(cè)的結(jié)果。
F0是設(shè)置的初值，Ti是一棵一棵的決策樹(shù)。對(duì)于不同的問(wèn)題（回歸問(wèn)題或者分類(lèi)問(wèn)題）和選擇不同的損失函數(shù)，初值的設(shè)定是不同的。比如回歸問(wèn)題并且選擇高斯損失函數(shù)，那么這個(gè)初值就是訓(xùn)練樣本的目標(biāo)的均值。
下面是一個(gè)簡(jiǎn)單的treelink模型示意圖。模型的目標(biāo)是上海一套普通商品房的價(jià)格，特征有三個(gè)：房子的面積（連續(xù)特征），是否在內(nèi)環(huán)（分類(lèi)特征），是否學(xué)區(qū)房（分類(lèi)特征）。模型由四棵決策樹(shù)構(gòu)成，每棵決策樹(shù)只進(jìn)行了一次分裂，即樹(shù)的深度為一（這種樹(shù)被稱(chēng)為DecisionStump）。實(shí)際應(yīng)用中通常較復(fù)雜，深度不會(huì)為一。
初值設(shè)定為上海普通商品房?jī)r(jià)格的均值150萬(wàn)，每經(jīng)過(guò)一棵決策樹(shù)，都會(huì)對(duì)根據(jù)相應(yīng)特征的取值對(duì)預(yù)測(cè)價(jià)格進(jìn)行調(diào)整。比如一個(gè)面積為120平的內(nèi)環(huán)非學(xué)區(qū)房的價(jià)格預(yù)測(cè)值為：150+20-10+30-10=180萬(wàn)。
那為什么要用多棵決策樹(shù)，一棵決策樹(shù)為什么不好呢？使用單棵決策樹(shù)，最大的問(wèn)題就是會(huì)因?yàn)檫^(guò)度分裂，而造成過(guò)擬合，失去泛化能力。試想一下，對(duì)于給定的一批訓(xùn)練數(shù)據(jù)，完全可以只構(gòu)造一棵樹(shù)，不斷分裂下去，直到每個(gè)葉子節(jié)點(diǎn)包含的樣本的目標(biāo)值都一樣，然后把這節(jié)點(diǎn)的預(yù)測(cè)值設(shè)定成這個(gè)目標(biāo)值，這樣構(gòu)造出來(lái)的這棵樹(shù)就可以在這批訓(xùn)練數(shù)據(jù)上達(dá)到100%的準(zhǔn)確性。但這樣一棵過(guò)度分裂的決策樹(shù)，對(duì)于新的樣本基本沒(méi)有什么預(yù)測(cè)能力。而如果分裂太少，又會(huì)造成學(xué)習(xí)不夠充分。Treelink使用多棵決策樹(shù)正是希望能夠在訓(xùn)練精度和泛化能力兩個(gè)方面都能達(dá)到較好的效果。作為一種boosting算法，Treelink自然包含了boosting的思想：將一系列弱分類(lèi)器組合起來(lái)，構(gòu)成一個(gè)強(qiáng)分類(lèi)器。它不要求每棵樹(shù)學(xué)到太多的東西，每顆樹(shù)都學(xué)一點(diǎn)點(diǎn)知識(shí)，然后將這些學(xué)到的知識(shí)累加起來(lái)構(gòu)成一個(gè)強(qiáng)大的模型。舉個(gè)現(xiàn)實(shí)生活中的例子，電視里的那種益智類(lèi)節(jié)目，如開(kāi)心詞典，答題者有三次請(qǐng)求幫組的機(jī)會(huì)，其中一個(gè)就是請(qǐng)求現(xiàn)場(chǎng)所有觀(guān)眾，通過(guò)他們的選擇來(lái)給出答案。我們可以把每個(gè)觀(guān)眾當(dāng)做一個(gè)弱的分類(lèi)器，他們各個(gè)單獨(dú)的準(zhǔn)確率都不高，但把他們的知識(shí)綜合起來(lái)這個(gè)準(zhǔn)確率會(huì)大大提升。也許上面這個(gè)例子不太能說(shuō)服你，我們來(lái)把這個(gè)例子量化。假如我們有三個(gè)觀(guān)眾，他們各自的準(zhǔn)確率為60%（非常弱的分類(lèi)器，只比隨機(jī)分類(lèi)器好一點(diǎn)點(diǎn)），如果這三位觀(guān)眾中有大于等于兩位的答案是正確的，那么則認(rèn)為我們正確了，反之則錯(cuò)誤。那么我們正確的概率是多少呢？preciseness= p(三個(gè)人都正確) + p(三個(gè)人中有兩個(gè)人正確) = 0.6*0.6*0.6 + 3*0.6*0.6*0.4 =0.648，比單個(gè)人0.6的正確率有所提升，驗(yàn)了中國(guó)那句老話(huà)“三個(gè)臭皮匠頂個(gè)諸葛亮”。隨著人數(shù)的增加，這個(gè)正確率還會(huì)提升。
Treelink模型的學(xué)習(xí)過(guò)程，就是多顆樹(shù)的構(gòu)建過(guò)程。和決策樹(shù)模型一樣，在樹(shù)的構(gòu)建過(guò)程中，最重要的就是尋找分裂點(diǎn)（某個(gè)特征的某個(gè)取值）。我們希望選擇的這個(gè)分裂點(diǎn)是最能區(qū)分樣本的。那么如何衡量一個(gè)分裂點(diǎn)對(duì)樣本的區(qū)分能力？在treelink算法我們通過(guò)Loss（衡量樣本預(yù)測(cè)值與目標(biāo)值的差異）的減小程度用來(lái)衡量這個(gè)區(qū)分能力，Loss減小得越多，這個(gè)分裂點(diǎn)就越好。即以某個(gè)分裂點(diǎn)劃分，把樣本分成兩部分，使得分裂后樣本的損失函數(shù)（LossFunction）值減小的最多。好像有點(diǎn)不太通俗了，沒(méi)辦法。
訓(xùn)練流程：
1 估計(jì)初值
2 按如下方式構(gòu)造M顆樹(shù)
2.1 隨機(jī)選取部分樣本作為本顆樹(shù)的訓(xùn)練數(shù)據(jù)
2.2 按如下方式尋找最優(yōu)分裂點(diǎn)，進(jìn)行N次葉子節(jié)點(diǎn)的分裂
2.2.1 對(duì)當(dāng)前所有葉子節(jié)點(diǎn)
2.2.1.1 計(jì)算該葉子節(jié)點(diǎn)的最優(yōu)劃分以及其增益（損失函數(shù)減少量）
2.2.1.2 選擇增益最大的葉子節(jié)點(diǎn)及其劃分點(diǎn)，進(jìn)行分裂，將樣本劃分到子節(jié)點(diǎn)中
2.2.1.3 更新樣本估計(jì)值
集團(tuán)開(kāi)發(fā)的mllib機(jī)器學(xué)習(xí)工具包中treelink是最重要的一個(gè)模型。對(duì)于如何使用這個(gè)工具包， mlllib usermanual里面已經(jīng)寫(xiě)的非常詳細(xì)了。下面說(shuō)一下其中一些重要參數(shù)的意義及如何設(shè)置。
tree_count：前面提到的決策樹(shù)的個(gè)數(shù)，這個(gè)數(shù)設(shè)的越大學(xué)習(xí)就越充分，但太大也會(huì)造成過(guò)度擬合，而且也消耗訓(xùn)練和預(yù)測(cè)的時(shí)間。可以先選擇比較大的樹(shù)個(gè)數(shù)，然后觀(guān)察訓(xùn)練過(guò)程中的損失減少趨勢(shì)，損失減少比較平緩時(shí)，樹(shù)個(gè)數(shù)就比較合適了。tree_count和shrinkage也有關(guān)系，shrinkage越大，學(xué)習(xí)越快，需要的樹(shù)越少。
shrinkage：步長(zhǎng)，它代表的是學(xué)習(xí)的速度，越小表示學(xué)習(xí)越保守（慢），而越大則表示學(xué)習(xí)越冒進(jìn)（快）。通常我們可以把Shrinkage設(shè)小一點(diǎn)，把樹(shù)的個(gè)數(shù)設(shè)大一點(diǎn)。
sample_rate：樣本采樣率，一次學(xué)習(xí)使用全部的樣本是浪費(fèi)，為了構(gòu)造出具有不同傾向性的模型，需要使用樣本的子集來(lái)進(jìn)行訓(xùn)練，而過(guò)多的樣本對(duì)簡(jiǎn)單的模型無(wú)益，只會(huì)造成更多的過(guò)擬合和局部極小問(wèn)題。這個(gè)采樣的比例一般選擇50%-70%比較合適。
variable_sample_rate：特征采樣率，和上面的樣本采樣率不同，這個(gè)采樣率是指從樣本的所有特征中選取部分的特征來(lái)學(xué)習(xí)，而不使用全部特征。當(dāng)你發(fā)現(xiàn)訓(xùn)練出來(lái)的模型，某一兩個(gè)特征非常強(qiáng)勢(shì)，重要性很大，而造成其他特征基本學(xué)不到的時(shí)候，可以考慮設(shè)置一下把這個(gè)參數(shù)設(shè)置成<1的數(shù)。
最后是對(duì)于使用機(jī)器學(xué)習(xí)的一些常見(jiàn)問(wèn)題的一些理解。
1 機(jī)器學(xué)習(xí)是萬(wàn)能的？
當(dāng)然不是，如果你認(rèn)為可以簡(jiǎn)單地把一堆特征樣本扔給機(jī)器學(xué)習(xí)，就期望它給一個(gè)好的模型，那是不可能。在使用機(jī)器學(xué)習(xí)之前，一定要對(duì)所使用的模型有個(gè)基本的了解，最好能夠知道它的計(jì)算原理。如果你都不知道treelink為何物，那些參數(shù)大概是個(gè)什么意思，你最好就不要用了，用也是在拼人品。
2 使用機(jī)器學(xué)習(xí)的同時(shí)做好數(shù)據(jù)分析工作
就算使用機(jī)器學(xué)習(xí)，數(shù)據(jù)的分析工作也是省不了的，做好了分析工作，你會(huì)發(fā)現(xiàn)自己都可以像機(jī)器一樣找到那些規(guī)律。其實(shí)機(jī)器學(xué)習(xí)本身也就是統(tǒng)計(jì)，幫你找數(shù)據(jù)之間的規(guī)律，并把這些規(guī)律做成規(guī)則。好萊塢奧斯卡金像獎(jiǎng)電影《美麗心靈》中的男主人翁，諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主數(shù)學(xué)家約翰納什在電影中被稱(chēng)為最厲害的人肉密碼破譯者，充分向我們展現(xiàn)了howpeople learning beats machinelearning，當(dāng)然是有些夸張的成份。下面是一些可以做的最基本的數(shù)據(jù)分析工作：
1） 特征的分布：按特征的取值分段，每一段包含的樣本數(shù)量，特征均值，方差。
2） 目標(biāo)分布同上
3） 特征目標(biāo)關(guān)系：特征分段，每段中包含的樣本的目標(biāo)取值。
4） 目標(biāo)特征關(guān)系：目標(biāo)分段，每段中包含的樣本的特征取值
3 模型在訓(xùn)練數(shù)據(jù)上效果不錯(cuò)，但做Cross-validation效果不佳
主要原因有兩個(gè)：
1） 選取的樣本數(shù)據(jù)太少，覆蓋度不夠，考慮增加訓(xùn)練樣本
2） 樣本特征過(guò)多，可以考慮減少一些特征，只留下重要的特征
4
