作為一個合格的生物信息工程師茬贵，生物學的算法是必備的技能。本人從業(yè)不到一年移袍，深感統(tǒng)計學知識匱乏解藻，希望以簡書作為自己的學習平臺，和大家分享一些常用的算法葡盗，本人能力有限螟左，只能介紹一些常用的，還有很多不斷在更新的算法觅够，希望各位道友多多發(fā)表胶背，多多溝通。
決策樹算法
算法思想
決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）蔚约。
其每個非葉節(jié)點表示一個特征屬性上的測試奄妨，每個分支代表這個特征屬性在某個值域上的輸出涂籽，而每個葉節(jié)點存放一個類別苹祟。
使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應的特征屬性评雌，并按照其值選擇輸出分支树枫，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結果景东。
簡單的說就是根據(jù)一些feature進行數(shù)據(jù)分類砂轻，從根上開始，每個分支節(jié)點提一個問題斤吐，然后依據(jù)是否滿足條件分為兩類搔涝，然后再進行提問，循環(huán)往復和措，直到達到數(shù)據(jù)每個分支的末端
總結來說：
決策樹模型核心是下面幾部分：
一庄呈、結點和有向邊組成
二、結點有內部結點和葉結點倆種類型
三派阱、內部結點表示一個特征诬留，葉節(jié)點表示一個類
算法
ID3算法
“信息熵”是度量樣本集合不確定度的最常用的指標。
在ID3算法中，我們采取信息增益這個量來作為不確定度的度量文兑。我們選取使得信息增益最大的特征進行分裂盒刚！
信息熵是代表隨機變量的復雜度（不確定度），條件熵代表在某一個條件下绿贞，隨機變量的復雜度（不確定度）因块。而我們的信息增益恰好是：信息熵-條件熵。
當前樣本集合 D 中第 k 類樣本所占的比例為 pk 籍铁，則 D 的信息熵定義為：
離散屬性 a 有 V 個可能的取值 {a1,a2,…,aV}贮聂；樣本集合中，屬性 a 上取值為 av 的樣本集合寨辩，記為 Dv吓懈。
用屬性 a 對樣本集 D 進行劃分所獲得的“信息增益”
信息增益表示得知屬性 a 的信息而使得樣本集合不確定度減少的程度
在決策樹算法中，我們的關鍵就是每次選擇一個特征靡狞，特征有多個耻警，那么到底按照什么標準來選擇哪一個特征。
這個問題就可以用信息增益來度量甸怕。如果選擇一個特征后甘穿，信息增益最大（信息不確定性減少的程度最大），那么我們就選取這個特征梢杭。
C4.5算法
首先我們來看信息增益率的公式：
由上圖我們可以看出牵咙，信息增益率=信息增益/IV(a),說明信息增益率是信息增益除了一個屬性a的固有值得來的嵌洼。
我們來看IV(a)的公式：
屬性a的固有值：
CART算法
這里我們重點看一下CART算法
當CART是分類樹時，采用GINI值作為節(jié)點分裂的依據(jù)；當CART是回歸樹時土童，采用樣本的最小方差作為節(jié)點分裂的依據(jù);
分類樹的作用是通過一個對象的特征來預測該對象所屬的類別了罪，而回歸樹的目的是根據(jù)一個對象的信息預測該對象的屬性硼补，并以數(shù)值表示茶鹃。
CART既能是分類樹，又能是決策樹全释。
CART如何選擇分裂的屬性装处？
如果是分類樹，CART采用GINI值衡量節(jié)點純度浸船；如果是回歸樹妄迁，采用樣本方差衡量節(jié)點純度。節(jié)點越不純李命，節(jié)點分類或者預測的效果就越差登淘。
GINI值的計算公式：
節(jié)點越不純，GINI值越大项戴。以二分類為例形帮，如果節(jié)點的所有數(shù)據(jù)只有一個類別槽惫，則
如果兩類數(shù)量相同辩撑，則
回歸方差計算公式：
方差越大，表示該節(jié)點的數(shù)據(jù)越分散合冀，預測的效果就越差各薇。如果一個節(jié)點的所有數(shù)據(jù)都相同，那么方差就為0君躺，此時可以很肯定得認為該節(jié)點的輸出值峭判；如果節(jié)點的數(shù)據(jù)相差很大，那么輸出的值有很大的可能與實際值相差較大棕叫。
因此林螃，無論是分類樹還是回歸樹，CART都要選擇使子節(jié)點的GINI值或者
回歸方差最小的屬性作為分裂的方案俺泣。即最小化（分裂樹）
或者（回歸樹）：
CART如何分裂成一棵二叉樹疗认？
節(jié)點的分裂分為兩種情況，連續(xù)型的數(shù)據(jù)和離散型的數(shù)據(jù)伏钠。
CART對連續(xù)型屬性的處理與C4.5差不多横漏，通過最小化分裂后的GINI值或者樣本方差尋找最優(yōu)分割點，將節(jié)點一分為二熟掂，在這里不再敘述缎浇，詳細請看C4.5。
對于離散型屬性赴肚，理論上有多少個離散值就應該分裂成多少個節(jié)點素跺。但CART是一棵二叉樹，每一次分裂只會產(chǎn)生兩個節(jié)點尊蚁，怎么辦呢亡笑？很簡單，只要將其中一個離散值獨立作為一個節(jié)點横朋，其他的離散值生成另外一個節(jié)點即可。這種分裂方案有多少個離散值就有多少種劃分的方法百拓，舉一個簡單的例子：如果某離散屬性一個有三個離散值X琴锭，Y，Z衙传，則該屬性的分裂方法有{X}决帖、{Y，Z}蓖捶，{Y}地回、{X，Z}，{Z}刻像、{X畅买，Y}，分別計算每種劃分方法的基尼值或者樣本方差確定最優(yōu)的方法细睡。
詳細的例子決策樹算法
隨機森林算法
1 什么是隨機森林谷羞？
作為新興起的、高度靈活的一種機器學習算法溜徙，隨機森林（Random Forest湃缎，簡稱RF）擁有廣泛的應用前景，從市場營銷到醫(yī)療保健保險蠢壹，既可以用來做市場營銷模擬的建模嗓违，統(tǒng)計客戶來源，保留和流失图贸，也可用來預測疾病的風險和病患者的易感性靠瞎。最初，我是在參加校外競賽時接觸到隨機森林算法的求妹。最近幾年的國內外大賽乏盐，包括2013年百度校園電影推薦系統(tǒng)大賽、2014年阿里巴巴天池大數(shù)據(jù)競賽以及Kaggle數(shù)據(jù)科學競賽制恍，參賽者對隨機森林的使用占有相當高的比例父能。此外，據(jù)我的個人了解來看净神，一大部分成功進入答辯的隊伍也都選擇了Random Forest 或者 GBDT 算法何吝。所以可以看出，Random Forest在準確率方面還是相當有優(yōu)勢的鹃唯。
那說了這么多爱榕，那隨機森林到底是怎樣的一種算法呢？
如果讀者接觸過決策樹（Decision Tree）的話坡慌，那么會很容易理解什么是隨機森林黔酥。隨機森林就是通過集成學習的思想將多棵樹集成的一種算法，它的基本單元是決策樹洪橘，而它的本質屬于機器學習的一大分支——集成學習（Ensemble Learning）方法跪者。隨機森林的名稱中有兩個關鍵詞，一個是“隨機”熄求，一個就是“森林”渣玲。“森林”我們很好理解弟晚，一棵叫做樹忘衍，那么成百上千棵就可以叫做森林了逾苫，這樣的比喻還是很貼切的，其實這也是隨機森林的主要思想--集成思想的體現(xiàn)枚钓∏Υ辏“隨機”的含義我們會在下邊部分講到。
其實從直觀角度來解釋秘噪，每棵決策樹都是一個分類器（假設現(xiàn)在針對的是分類問題）狸吞，那么對于一個輸入樣本，N棵樹會有N個分類結果指煎。而隨機森林集成了所有的分類投票結果蹋偏，將投票次數(shù)最多的類別指定為最終的輸出，這就是一種最簡單的 Bagging 思想至壤。
簡單地說威始，就是在源數(shù)據(jù)中隨機選取幾個子集，產(chǎn)生隨機subsets進行分類
2 隨機森林的特點
我們前邊提到像街，隨機森林是一種很靈活實用的方法黎棠，它有如下幾個特點：
- 在當前所有算法中，具有極好的準確率/It is unexcelled in accuracy among current algorithms镰绎；
- 能夠有效地運行在大數(shù)據(jù)集上/It runs efficiently on large data bases脓斩；
- 能夠處理具有高維特征的輸入樣本，而且不需要降維/It can handle thousands of input variables without variable deletion畴栖；
- 能夠評估各個特征在分類問題上的重要性/It gives estimates of what variables are important in the classification随静；
- 在生成過程中，能夠獲取到內部生成誤差的一種無偏估計/It generates an internal unbiased estimate of the generalization error as the forest building progresses吗讶；
- 對于缺省值問題也能夠獲得很好得結果/It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing
- ... ...
實際上燎猛，隨機森林的特點不只有這六點，它就相當于機器學習領域的Leatherman（多面手）照皆，你幾乎可以把任何東西扔進去重绷，它基本上都是可供使用的。在估計推斷映射方面特別好用膜毁，以致都不需要像SVM那樣做很多參數(shù)的調試昭卓。具體的隨機森林介紹可以參見隨機森林主頁：Random Forest。
3 隨機森林的相關基礎知識
隨機森林看起來是很好理解爽茴，但是要完全搞明白它的工作原理葬凳，需要很多機器學習方面相關的基礎知識。在本文中室奏，我們簡單談一下，而不逐一進行贅述劲装，如果有道友不太了解相關的知識胧沫，可以參閱其他博友的一些相關博文或者文獻昌简。
1）信息、熵以及信息增益的概念
這三個基本概念是決策樹的根本绒怨，是決策樹利用特征來分類時纯赎，確定特征選取順序的依據(jù)。理解了它們南蹂，決策樹你也就了解了大概犬金。
引用香農(nóng)的話來說，信息是用來消除隨機不確定性的東西六剥。當然這句話雖然經(jīng)典晚顷，但是還是很難去搞明白這種東西到底是個什么樣，可能在不同的地方來說疗疟，指的東西又不一樣该默。對于機器學習中的決策樹而言，如果帶分類的事物集合可以劃分為多個類別當中策彤，則某個類（xi）的信息可以定義如下:
I(x)用來表示隨機變量的信息栓袖，p(xi)指是當xi發(fā)生時的概率。
熵是用來度量不確定性的店诗，當熵越大裹刮，X=xi的不確定性越大，反之越小庞瘸。對于機器學習中的分類問題而言捧弃，熵越大即這個類別的不確定性更大，反之越小恕洲。
信息增益在決策樹算法中是用來選擇特征的指標塔橡，信息增益越大，則這個特征的選擇性越好霜第。
這方面的內容不再細述葛家，感興趣的同學可以看 信息&熵&信息增益 這篇博文。
2）決策樹
決策樹是一種樹形結構泌类，其中每個內部節(jié)點表示一個屬性上的測試癞谒，每個分支代表一個測試輸出，每個葉節(jié)點代表一種類別刃榨。常見的決策樹算法有C4.5弹砚、ID3和CART。
3）集成學習
集成學習通過建立幾個模型組合的來解決單一預測問題枢希。它的工作原理是生成多個分類器/模型桌吃，各自獨立地學習和作出預測。這些預測最后結合成單預測苞轿，因此優(yōu)于任何一個單分類的做出預測茅诱。
隨機森林是集成學習的一個子類逗物，它依靠于決策樹的投票選擇來決定最后的分類結果。你可以在這找到用python實現(xiàn)集成學習的文檔：Scikit 學習文檔瑟俭。
4 隨機森林的生成
前面提到翎卓，隨機森林中有許多的分類樹。我們要將一個輸入樣本進行分類摆寄，我們需要將輸入樣本輸入到每棵樹中進行分類失暴。打個形象的比喻：森林中召開會議，討論某個動物到底是老鼠還是松鼠微饥，每棵樹都要獨立地發(fā)表自己對這個問題的看法逗扒，也就是每棵樹都要投票。該動物到底是老鼠還是松鼠畜号，要依據(jù)投票情況來確定缴阎，獲得票數(shù)最多的類別就是森林的分類結果。森林中的每棵樹都是獨立的简软，99.9%不相關的樹做出的預測結果涵蓋所有的情況蛮拔，這些預測結果將會彼此抵消。少數(shù)優(yōu)秀的樹的預測結果將會超脫于蕓蕓“噪音”痹升，做出一個好的預測建炫。將若干個弱分類器的分類結果進行投票選擇，從而組成一個強分類器疼蛾，這就是隨機森林bagging的思想（關于bagging的一個有必要提及的問題：bagging的代價是不用單棵決策樹來做預測肛跌，具體哪個變量起到重要作用變得未知，所以bagging改進了預測準確率但損失了解釋性察郁。）衍慎。下圖可以形象地描述這個情況：
有了樹我們就可以分類了，但是森林中的每棵樹是怎么生成的呢皮钠？
每棵樹的按照如下規(guī)則生成：
1）如果訓練集大小為N稳捆，對于每棵樹而言，隨機且有放回地從訓練集中的抽取N個訓練樣本（這種采樣方式稱為bootstrap sample方法）麦轰，作為該樹的訓練集乔夯；
從這里我們可以知道：每棵樹的訓練集都是不同的，而且里面包含重復的訓練樣本（理解這點很重要）款侵。
為什么要隨機抽樣訓練集末荐？
如果不進行隨機抽樣，每棵樹的訓練集都一樣新锈，那么最終訓練出的樹分類結果也是完全一樣的甲脏，這樣的話完全沒有bagging的必要；
為什么要有放回地抽樣？
我理解的是這樣的：如果不是有放回的抽樣剃幌，那么每棵樹的訓練樣本都是不同的聋涨，都是沒有交集的晾浴，這樣每棵樹都是"有偏的"负乡，都是絕對"片面的"（當然這樣說可能不對），也就是說每棵樹訓練出來都是有很大的差異的脊凰；而隨機森林最后分類取決于多棵樹（弱分類器）的投票表決抖棘，這種表決應該是"求同"，因此使用完全不同的訓練集來訓練每棵樹這樣對最終分類結果是沒有幫助的狸涌，這樣無異于是"盲人摸象"切省。
2）如果每個樣本的特征維度為M，指定一個常數(shù)m<<M帕胆，隨機地從M個特征中選取m個特征子集朝捆，每次樹進行分裂時，從這m個特征中選擇最優(yōu)的懒豹；
3）每棵樹都盡最大程度的生長芙盘，并且沒有剪枝過程。
一開始我們提到的隨機森林中的“隨機”就是指的這里的兩個隨機性脸秽。兩個隨機性的引入對隨機森林的分類性能至關重要儒老。由于它們的引入，使得隨機森林不容易陷入過擬合记餐，并且具有很好得抗噪能力（比如：對缺省值不敏感）驮樊。
隨機森林分類效果（錯誤率）與兩個因素有關：
- 森林中任意兩棵樹的相關性：相關性越大，錯誤率越大片酝；
- 森林中每棵樹的分類能力：每棵樹的分類能力越強囚衔，整個森林的錯誤率越低。
減小特征選擇個數(shù)m雕沿，樹的相關性和分類能力也會相應的降低练湿；增大m，兩者也會隨之增大晦炊。所以關鍵問題是如何選擇最優(yōu)的m（或者是范圍）鞠鲜，這也是隨機森林唯一的一個參數(shù)。
5 袋外錯誤率（oob error）
上面我們提到断国，構建隨機森林的關鍵問題就是如何選擇最優(yōu)的m贤姆，要解決這個問題主要依據(jù)計算袋外錯誤率oob error（out-of-bag error）。
隨機森林有一個重要的優(yōu)點就是稳衬，沒有必要對它進行交叉驗證或者用一個獨立的測試集來獲得誤差的一個無偏估計霞捡。它可以在內部進行評估，也就是說在生成的過程中就可以對誤差建立一個無偏估計薄疚。
我們知道碧信，在構建每棵樹時赊琳，我們對訓練集使用了不同的bootstrap sample（隨機且有放回地抽取）砰碴。所以對于每棵樹而言（假設對于第k棵樹）躏筏，大約有1/3的訓練實例沒有參與第k棵樹的生成，它們稱為第k棵樹的oob樣本呈枉。
而這樣的采樣特點就允許我們進行oob估計趁尼，它的計算方式如下：
（note：以樣本為單位）
1）對每個樣本，計算它作為oob樣本的樹對它的分類情況（約1/3的樹）猖辫；
2）然后以簡單多數(shù)投票作為該樣本的分類結果酥泞；
3）最后用誤分個數(shù)占樣本總數(shù)的比率作為隨機森林的oob誤分率。
（文獻原文：Put each case left out in the construction of the kth tree down the kth tree to get a classification. In this way, a test set classification is obtained for each case in about one-third of the trees. At the end of the run, take j to be the class that got most of the votes every time case n was oob. The proportion of times that j is not equal to the true class of n averaged over all cases is the oob error estimate. This has proven to be unbiased in many tests.）
oob誤分率是隨機森林泛化誤差的一個無偏估計啃憎，它的結果近似于需要大量計算的k折交叉驗證芝囤。
詳細例子[隨即森林例子]（https://blog.csdn.net/yangyin007/article/details/82385967）
SVM算法
support vector machine
這個想法對于生物信息來說應該是最為熟悉，無論是Seurat包還是Cellranger都采用這個算法
算法很復雜辛萍，這里我們簡單來學一下其中的基礎算法
1.1支持向量機(SVM)的由來
首先我們先來看一個3維的平面方程：Ax+By+Cz+D=0
這就是我們中學所學的悯姊，從這個方程我們可以推導出二維空間的一條直線：Ax+By+D=0
那么，依次類推叹阔，更高維的空間叫做一個超平面：
x代表的是一個向量挠轴，接下來我們看下二維空間的幾何表示：
SVM的目標是找到一個超平面，這個超平面能夠很好的解決二分類問題耳幢，所以先找到各個分類的樣本點離這個超平面最近的點岸晦，使得這個點到超平面的距離最大化，最近的點就是虛線所畫的睛藻。由以上超平面公式計算得出大于1的就屬于打叉分類启上，如果小于0的屬于圓圈分類。
這些點能夠很好地確定一個超平面店印，而且在幾何空間中表示的也是一個向量冈在，那么就把這些能夠用來確定超平面的向量稱為支持向量（直接支持超平面的生成），于是該算法就叫做支持向量機(SVM)了按摘。
1.2如何找到超平面
函數(shù)間隔
在超平面wx+b=0確定的情況下包券，|wx+b|能夠表示點x到距離超平面的遠近，而通過觀察wx+b的符號與類標記y的符號是否一致可判斷分類是否正確炫贤，所以溅固，可以用(y(w*x+b))的正負性來判定或表示分類的正確性。于此兰珍，我們便引出了函數(shù)間隔（functional margin）的概念侍郭。定義函數(shù)間隔（用
表示)為：
但是這個函數(shù)間隔有個問題，就是我成倍的增加w和b的值，則函數(shù)值也會跟著成倍增加亮元，但這個超平面沒有改變猛计。所以有函數(shù)間隔還不夠，需要一個幾何間隔爆捞。
幾何間隔
我們把w做一個約束條件奉瘤，假定對于一個點 x ，令其垂直投影到超平面上的對應點為 x0 嵌削，w 是垂直于超平面的一個向量毛好，為樣本x到超平面的距離，如下圖所示：
根據(jù)平面幾何知識苛秕，有
1.3最大間隔分類器
對一個數(shù)據(jù)點進行分類，當超平面離數(shù)據(jù)點的“間隔”越大找默，分類的確信度（confidence）也越大艇劫。所以，為了使得分類的確信度盡量高惩激，需要讓所選擇的超平面能夠最大化這個“間隔”值店煞。這個間隔就是下圖中的Gap的一半。
1.4后續(xù)問題
至此风钻，SVM的第一層已經(jīng)了解了顷蟀，就是求最大的幾何間隔，對于那些只關心怎么用SVM的朋友便已足夠骡技，不必再更進一層深究其更深的原理鸣个。
SVM要深入的話有很多內容需要講到，比如：線性不可分問題布朦、核函數(shù)囤萤、SMO算法等。
在此推薦一篇博文是趴，這篇博文把深入的SVM內容也講了涛舍，包括推導過程等。如果想進一步了解SVM唆途，推薦看一下：
支持向量機通俗導論：https://blog.csdn.net/v_JULY_v/article/details/7624837#commentBox
KNN算法
一富雅、KNN算法概述
鄰近算法，或者說K最近鄰(kNN肛搬，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術中最簡單的方法之一没佑。所謂K最近鄰，就是k個最近的鄰居的意思滚婉，說的是每個樣本都可以用它最接近的k個鄰居來代表图筹。Cover和Hart在1968年提出了最初的鄰近算法。KNN是一種分類(classification)算法，它輸入基于實例的學習（instance-based learning）远剩，屬于懶惰學習（lazy learning）即KNN沒有顯式的學習過程扣溺，也就是說沒有訓練階段，數(shù)據(jù)集事先已有了分類和特征值瓜晤，待收到新樣本后直接進行處理锥余。與急切學習（eager learning）相對應。
KNN是通過測量不同特征值之間的距離進行分類痢掠。
思路是：如果一個樣本在特征空間中的k個最鄰近的樣本中的大多數(shù)屬于某一個類別驱犹，則該樣本也劃分為這個類別。KNN算法中足画，所選擇的鄰居都是已經(jīng)正確分類的對象雄驹。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
提到KNN淹辞，網(wǎng)上最常見的就是下面這個圖医舆，可以幫助大家理解。
我們要確定綠點屬于哪個顏色（紅色或者藍色）象缀，要做的就是選出距離目標點距離最近的k個點蔬将，看這k個點的大多數(shù)顏色是什么顏色。當k取3的時候央星，我們可以看出距離最近的三個霞怀，分別是紅色、紅色莉给、藍色毙石，因此得到目標點為紅色。
算法的描述：
1）計算測試數(shù)據(jù)與各個訓練數(shù)據(jù)之間的距離禁谦；
2）按照距離的遞增關系進行排序胁黑；
3）選取距離最小的K個點；
4）確定前K個點所在類別的出現(xiàn)頻率州泊；
5）返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預測分類
二丧蘸、關于K的取值
K：臨近數(shù)，即在預測目標點時取幾個臨近的點來預測遥皂。
K值得選取非常重要端蛆，因為：
如果當K的取值過小時黑竞，一旦有噪聲得成分存在們將會對預測產(chǎn)生比較大影響芹枷，例如取K值為1時汁咏，一旦最近的一個點是噪聲，那么就會出現(xiàn)偏差样悟，K值的減小就意味著整體模型變得復雜拂募，容易發(fā)生過擬合庭猩；
如果K的值取的過大時，就相當于用較大鄰域中的訓練實例進行預測陈症，學習的近似誤差會增大蔼水。這時與輸入目標點較遠實例也會對預測起作用，使預測發(fā)生錯誤录肯。K值的增大就意味著整體的模型變得簡單趴腋；
如果K==N的時候，那么就是取全部的實例论咏，即為取實例中某分類下最多的點优炬，就對預測沒有什么實際的意義了；
K的取值盡量要取奇數(shù)厅贪，以保證在計算結果最后會產(chǎn)生一個較多的類別蠢护，如果取偶數(shù)可能會產(chǎn)生相等的情況，不利于預測卦溢。
K的取法：
常用的方法是從k=1開始糊余，使用檢驗集估計分類器的誤差率。重復該過程单寂，每次K增值1，允許增加一個近鄰吐辙。選取產(chǎn)生最小誤差率的K宣决。
一般k的取值不超過20，上限是n的開方昏苏，隨著數(shù)據(jù)集的增大尊沸，K的值也要增大。
三贤惯、關于距離的選取
距離就是平面上兩個點的直線距離
關于距離的度量方法洼专，常用的有：歐幾里得距離、余弦值（cos）, 相關度 （correlation）, 曼哈頓距離 （Manhattan distance）或其他孵构。
Euclidean Distance 定義：
兩個點或元組P1=（x1屁商，y1）和P2=（x2，y2）的歐幾里得距離是
距離公式為：（多個維度的時候是多個維度各自求差）
四颈墅、總結
KNN算法是最簡單有效的分類算法蜡镶，簡單且容易實現(xiàn)。當訓練數(shù)據(jù)集很大時恤筛，需要大量的存儲空間官还，而且需要計算待測樣本和訓練數(shù)據(jù)集中所有樣本的距離，所以非常耗時
KNN對于隨機分布的數(shù)據(jù)集分類效果較差毒坛，對于類內間距小望伦，類間間距大的數(shù)據(jù)集分類效果好林说，而且對于邊界不規(guī)則的數(shù)據(jù)效果好于線性分類器。
KNN對于樣本不均衡的數(shù)據(jù)效果不好屯伞，需要進行改進腿箩。改進的方法時對k個近鄰數(shù)據(jù)賦予權重，比如距離測試樣本越近愕掏，權重越大度秘。
KNN很耗時，時間復雜度為O(n)饵撑，一般適用于樣本數(shù)較少的數(shù)據(jù)集剑梳，當數(shù)據(jù)量大時，可以將數(shù)據(jù)以樹的形式呈現(xiàn)滑潘，能提高速度垢乙，常用的有kd-tree和ball-tree。
（弱小無助语卤。追逮。。根據(jù)許多大佬的總結整理的）
神經(jīng)網(wǎng)絡算法
神經(jīng)網(wǎng)絡是所謂深度學習的一個基礎粹舵，也是必備的知識點钮孵，他是以人腦中的神經(jīng)網(wǎng)絡作為啟發(fā)，最著名的算法就是backpropagation算法眼滤，這里就簡單的整理一下神經(jīng)網(wǎng)絡相關參數(shù)巴席，和計算方法。
一诅需、多層向前神經(jīng)網(wǎng)絡（Multilayer Feed-Forward Neural Network）
多層向前神經(jīng)網(wǎng)絡由一下幾個部分組成：
輸入層（input layer）漾唉，隱藏層（Hidden layer），輸出層（output layer）
特點如下：
1堰塌、每層由單元（units）組成
2赵刑、輸入層是有訓練集的實例特征向量傳入
3、經(jīng)過連接接點的權重（weight）傳入下一層场刑，一層的輸出是下一層的輸入
4般此、隱藏層的個數(shù)可以是任意的，輸入層有一層摇邦，輸出層有一層
5恤煞、每個單元也可以稱之為神經(jīng)結點，根據(jù)生物學來源定義
6施籍、以上成為兩層的神經(jīng)網(wǎng)絡居扒，輸入層是不算在里面的
7、一層中加權求和丑慎，然后根據(jù)非線性方程轉化輸出
8喜喂、作為多層向前神經(jīng)網(wǎng)絡瓤摧，理論上，如果有足夠的隱藏層玉吁，和足夠的訓練集照弥，可以模擬出任何方程
二、設計神經(jīng)網(wǎng)絡結構
1进副、使用神經(jīng)網(wǎng)絡訓練數(shù)據(jù)之前这揣，必須確定神經(jīng)網(wǎng)絡的層數(shù)，以及每層單元的個數(shù)
2影斑、特征向量在被傳入輸入層時通常要先標準化到0-1之間（為了加速學習過程）
3给赞、離散型變量可以被編碼成每一個輸入單元對應一個特征值可能賦的值
比如：特征值A可能取三個值（a0, a1, a2), 可以使用3個輸入單元來代表A。
如果A=a0, 那么代表a0的單元值就取1, 其他取0矫户；
如果A=a1, 那么代表a1de單元值就取1片迅，其他取0，以此類推
4皆辽、神經(jīng)網(wǎng)絡即可以用來做分類（classification）問題柑蛇，也可以解決回歸（regression）問題
（1）對于分類問題，如果是2類驱闷，可以用一個輸出單元表示（0和1分別代表2類）耻台，如果多余2類，則每一個類別用一個輸出單元表示
（2）沒有明確的規(guī)則來設計最好有多少個隱藏層空另，可以根據(jù)實驗測試和誤差以及精準度來實驗并改進
三粘我、交叉驗證方法（cross-Validation）
這里有一堆數(shù)據(jù)，我們把他切成3個部分（當然還可以分的更多）
第一部分做測試集痹换，二三部分做訓練集，算出準確度都弹；
第二部分做測試集娇豫，一三部分做訓練集，算出準確度畅厢；
第三部分做測試集冯痢，一二部分做訓練集，算出準確度框杜；
之后算出三個準確度的平局值浦楣，作為最后的準確度，如下圖：
這里寫圖片描述
四咪辱、backpropagation算法
他是通過迭代性來處理訓練集中的實例振劳，對比經(jīng)過神經(jīng)網(wǎng)絡后，輸人層預測值與真實值之間的誤差油狂，再通過反向法（從輸出層=>隱藏層=>輸入層）以最小化誤差來更新每個連接的權重历恐。
- 算法的詳細介紹
輸入：D（數(shù)據(jù)集）寸癌，學習率（learning rate），一個多層向前神經(jīng)網(wǎng)絡
輸出：一個訓練好的神經(jīng)網(wǎng)絡（a trained neural network）
1.初始化權重和偏向：隨機初始化在-1到1之間弱贼，或者-0.5到0.5之間蒸苇，每個單元有一個偏向
2.開始對數(shù)據(jù)進行訓練，步驟如下：
由輸入層向前傳送
Ij：要對其進行非線性轉化吮旅，為下一單元的值
Oi：是輸入的值
wij：為每個單元到下一個單元連線之間的權重
θj:偏向
對Ij進行非線性轉化溪烤，得到下一個單元的值
根據(jù)誤差(error)反向傳送
對于隱藏層：這里寫圖片描述
Errj：用于更新偏向
Oj：為輸出的值
Tj：為標簽的值
權重更新：
括號里為小l ，是學習率（learning rate）
終止條件
方法一：權重的更新低于某個閾值
方法二：預測的錯誤率低于某個閾值
方法三：達到預設一定的循環(huán)次數(shù)
這個算法看起來很復雜庇勃，不容易理解檬嘀，需要認真揣摩，一步一步認真推導結果匪凉。
