第二天knn近鄰分類算法

1、KNN算法算法概述kNN算法又稱為k近鄰分類(k-nearest neighbor classification)算法。 最簡(jiǎn)單平凡的分類器就是死記硬背式的分類器，記住所有的訓(xùn)練數(shù)據(jù)，對(duì)于新的數(shù)據(jù)則直接和訓(xùn)練數(shù)據(jù)匹配，如果存在相近屬性的訓(xùn)練數(shù)據(jù)，則直接用它的分類來(lái)作為新數(shù)據(jù)的分類。這種方式有一個(gè)明顯的缺點(diǎn)，那就是很可能一個(gè)新數(shù)據(jù)與訓(xùn)練數(shù)據(jù)屬性值差異很大時(shí)，無(wú)法找到完全匹配的訓(xùn)練記錄。kNN算法則是從訓(xùn)練集中找到和新數(shù)據(jù)最接近的k條記錄，然后根據(jù)他們的主要分類來(lái)決定新數(shù)據(jù)的類別。該算法涉及3個(gè)主要因素：訓(xùn)練集、距離或相似的衡量、k的大小。近鄰分類思想行業(yè)應(yīng)用比如文字識(shí)別，面部識(shí)別預(yù)測(cè)某人是否喜歡

2、推薦的電影（Netflix）基因模式識(shí)別，比如用于檢測(cè)某種疾病客戶流失預(yù)測(cè)、欺詐偵測(cè)等（更適合于稀有事件的分類問(wèn)題）KNN應(yīng)用場(chǎng)景通常最近鄰居分類器適用于特征與目標(biāo)類之間的關(guān)系為比較復(fù)雜的數(shù)字類型，或者說(shuō)二者關(guān)系難以理解，但是相似類間特征總是相似。kNN算法：簡(jiǎn)單有效，對(duì)數(shù)據(jù)分布沒(méi)有假設(shè)，數(shù)據(jù)訓(xùn)練也很快但是它沒(méi)有模型輸出，因此限制了對(duì)特征間關(guān)系的理解分類階段也比較慢，耗費(fèi)內(nèi)存對(duì)nominal特征以及缺少數(shù)據(jù)需要預(yù)先處理算法要點(diǎn)指導(dǎo)思想kNN算法的指導(dǎo)思想是“近朱者赤，近墨者黑”，根據(jù)與待分類數(shù)據(jù)集中的最近的k個(gè)訓(xùn)練集中的分類標(biāo)簽來(lái)對(duì)決定其類別。算距離：給定測(cè)試對(duì)象，計(jì)算它與訓(xùn)練集中的每個(gè)對(duì)象的

3、距離找鄰居：圈定距離最近的k個(gè)訓(xùn)練對(duì)象，作為測(cè)試對(duì)象的近鄰做分類：根據(jù)這k個(gè)近鄰歸屬的主要類別，來(lái)對(duì)測(cè)試對(duì)象分類）距離或相似度的衡量什么是合適的距離衡量？距離越近應(yīng)該意味著這兩個(gè)點(diǎn)屬于一個(gè)分類的可能性越大。距離衡量包括歐式距離、夾角余弦,曼哈頓距離等。對(duì)于文本分類來(lái)說(shuō)，使用余弦(cosine)來(lái)計(jì)算相似度就比歐式(Euclidean)距離更合適。距離或相似度的衡量歐幾里德距離余弦距離為何使用余弦距離以判斷用戶的喜歡為例，基于余弦相似度的計(jì)算方法就是把用戶的喜好作為n-維坐標(biāo)系中的一個(gè)點(diǎn)，通過(guò)連接這個(gè)點(diǎn)與坐標(biāo)系的原點(diǎn)構(gòu)成一條直線（向量），兩個(gè)用戶之間的相似度值就是兩條直線（向量）間夾角的余弦值。

4、因?yàn)檫B接代表用戶評(píng)分的點(diǎn)與原點(diǎn)的直線都會(huì)相交于原點(diǎn)，夾角越小代表兩個(gè)用戶越相似，夾角越大代表兩個(gè)用戶的相似度越小。調(diào)和余弦距離余弦相似度更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感。因此沒(méi)法衡量每個(gè)維數(shù)值的差異，會(huì)導(dǎo)致這樣一個(gè)情況：比如用戶對(duì)內(nèi)容評(píng)分，5分制，X和Y兩個(gè)用戶對(duì)兩個(gè)內(nèi)容的評(píng)分分別為(1,2)和(4,5)，使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評(píng)分上看X似乎不喜歡這2個(gè)內(nèi)容，而Y比較喜歡，余弦相似度對(duì)數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差，需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個(gè)均值，比如X和Y的評(píng)分均值都是3，那么調(diào)整后為(-2,-1)和

5、(1,2)，再用余弦相似度計(jì)算，得到-0.8, 相似度為負(fù)值并且差異不小，但顯然更加符合現(xiàn)實(shí)。為何使用余弦距離以判斷用戶的喜歡為例，基于余弦相似度的計(jì)算方法就是把用戶的喜好作為n-維坐標(biāo)系中的一個(gè)點(diǎn)，通過(guò)連接這個(gè)點(diǎn)與坐標(biāo)系的原點(diǎn)構(gòu)成一條直線（向量），兩個(gè)用戶之間的相似度值就是兩條直線（向量）間夾角的余弦值。因?yàn)檫B接代表用戶評(píng)分的點(diǎn)與原點(diǎn)的直線都會(huì)相交于原點(diǎn)，夾角越小代表兩個(gè)用戶越相似，夾角越大代表兩個(gè)用戶的相似度越小。歐幾里德還是余弦距離？根據(jù)歐氏距離和余弦相似度各自的計(jì)算方式和衡量特征，分別適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個(gè)體數(shù)值特征的絕對(duì)差異，所以更多的用于需要從維度的數(shù)值大小中

6、體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異余弦相似度更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感，更多的用于使用用戶對(duì)內(nèi)容評(píng)分來(lái)區(qū)分用戶興趣的相似度和差異，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問(wèn)題（因?yàn)橛嘞蚁嗨贫葘?duì)絕對(duì)數(shù)值不敏感）類別的判定投票決定：少數(shù)服從多數(shù)，近鄰中哪個(gè)類別的點(diǎn)最多就分為該類。加權(quán)投票法：根據(jù)距離的遠(yuǎn)近，對(duì)近鄰的投票進(jìn)行加權(quán)，距離越近則權(quán)重越大（權(quán)重為距離平方的倒數(shù)）KNN算法流程番茄屬于什么類別？已知：番茄是什么類別？番茄是水果如果k=1，那么西紅柿與orange最近，就應(yīng)該是水果，如果k=3，就是投票，橘子和葡萄都說(shuō)它是水果，那它就是水果了。優(yōu)

7、點(diǎn)簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練適合對(duì)稀有事件進(jìn)行分類（例如當(dāng)流失率很低時(shí)，比如低于0.5%，構(gòu)造流失預(yù)測(cè)模型）特別適合于多分類問(wèn)題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)，例如根據(jù)基因特征來(lái)判斷其功能分類，kNN比SVM的表現(xiàn)要好缺點(diǎn)懶惰算法，對(duì)測(cè)試樣本分類時(shí)的計(jì)算量大，內(nèi)存開(kāi)銷大，評(píng)分慢可解釋性較差，無(wú)法給出決策樹(shù)那樣的規(guī)則。計(jì)算距離常見(jiàn)問(wèn)題k值設(shè)定為多大？很明顯k的選擇對(duì)最終結(jié)果大有影響，這就是機(jī)器學(xué)習(xí)中幾點(diǎn)的bias與variance取舍問(wèn)題，魚(yú)和熊掌不可兼得。如果k很大，那么可以減少干擾數(shù)據(jù)的影響，但是此時(shí)就導(dǎo)致了系統(tǒng)性偏差，比如如果取k為總的訓(xùn)練數(shù)據(jù)數(shù)，那

8、么每次投票肯定都是訓(xùn)練數(shù)據(jù)中多的類別勝利。顯然訓(xùn)練數(shù)據(jù)的系統(tǒng)性偏差會(huì)影響結(jié)果。而如果k=1，那么某個(gè)干擾數(shù)據(jù)或者異常數(shù)據(jù)會(huì)影響最終結(jié)果的準(zhǔn)確性，所以我們始終是在bias與variance直接取舍。K取值k通常會(huì)在310直接取值或者是k等于訓(xùn)練數(shù)據(jù)的平方根。比如15個(gè)數(shù)據(jù)，可能會(huì)取k=4k取較大值，但是我們?cè)谕镀睍r(shí)權(quán)重不同類別如何判定最合適？投票法沒(méi)有考慮近鄰的距離的遠(yuǎn)近，距離更近的近鄰也許更應(yīng)該決定最終的分類，所以加權(quán)投票法更恰當(dāng)一些。數(shù)據(jù)的預(yù)處理有了計(jì)算距離的方法，也有了k的取值，是否我們就可以開(kāi)始分類了？簡(jiǎn)單考慮一下，比如我們度量各個(gè)特征的時(shí)候刻度單位不同，那么會(huì)帶來(lái)什么問(wèn)題。特征A取值是從01，另一個(gè)特征B則是010000，這里特征B的1000，不代表是特征A 的1的1000倍，因此我們要對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化。傳統(tǒng)的是采用最小最大值標(biāo)準(zhǔn)化方法：這樣X(jué)new的取值就在01之間了。另一種方法則是z-score:數(shù)據(jù)預(yù)處理數(shù)據(jù)已經(jīng)標(biāo)準(zhǔn)化了是否就ok了？不是的，歐幾里德距離只能用于數(shù)字，對(duì)于nominal變量（分類變量），無(wú)法處理。這個(gè)時(shí)候我們可以通過(guò)dummy（啞元）來(lái)處理。比如：性別為male就取1其它取0那如果不止2類，是多個(gè)呢？一種方法就是我創(chuàng)建（n-1)個(gè)啞元變量，還有一種就是如果你的分類變量是有順序的，而且每一級(jí)間的間隔是固定的那你