KNN

前言：之所以會有這個文集是因為快要秋招了，想要準備一下，所有的內(nèi)容都以面試問答的形式體現(xiàn)，以前有人做過類似的內(nèi)容：深度學習500問，但是里面的內(nèi)容感覺更適合作為平時學習的參考。

本文集所有的文章與前人工作最大的區(qū)別是：有的回答會顯得有些口語化，因為是我自己一邊嘴里念念有詞，一邊記下來的（想象你腦海里有兩個小人），實際面試的時候，不可能機械的去背誦，那樣會感覺怪怪的，但是所有的回答又有一定的內(nèi)在邏輯。

我在自己有限的幾次面試中，發(fā)現(xiàn)，對于面試官的很多問題，我知道答案，但是不知道該怎么回答，該從何講起，沒有條例，邏輯不清晰，原因一方面是自己基礎(chǔ)不扎實，一方面是沒有針對性的準備，所以我想通過這個文集，解決這個問題，換句話說，這個文集里的文章可能只適合我自己，各位看官請仔細甄別。

1. 請詳述/介紹/說一下KNN算法？

介紹KNN時至少要答出以下四點：

1. knn的原理，2.k值的選擇，3.距離度量，4. 決策規(guī)則。
   后三者又稱為KNN的三要素

答：KNN是一種基本的分類與回歸方法

1. 處理分類問題時，給定一個訓練數(shù)據(jù)集，對新輸入的實例，在訓練數(shù)據(jù)集中找到和它最鄰近的K個實例，這K個實例的多數(shù)屬于某個類，就把這個新的實例分為這個類，也就是多數(shù)表決投票；如果把最鄰近的K個實例的標簽均值作為預(yù)測值，就可以處理回歸問題了。（原理解釋完了）

2. 這里面K值的選擇會對KNN算法的訓練結(jié)果產(chǎn)生重要影響，

   • 如果K值比較小，那就相當于用比較小的鄰域中的訓練樣本進行預(yù)測，"學習"的偏差減小（優(yōu)點），只有和輸入樣本比較近的訓練樣本才會對預(yù)測起作用。缺點是會增大"學習"的方差（波動），預(yù)測結(jié)果會對近鄰的樣本點非常敏感。如果這時候近鄰的訓練樣本點剛好是噪聲，那預(yù)測就會出錯。也就是說K 值的減小意味著模型整體變復雜，容易發(fā)生過擬合。
   • 反過來如果K值比較大，模型變簡單，方差減小，偏差增大，和新樣本較遠的訓練樣本也會對預(yù)測起作用，會使預(yù)測結(jié)果偏離預(yù)期的結(jié)果。
     實際中通常采用交叉驗證法來選取最優(yōu)K值

3. 評判兩個樣本遠近的方法是距離度量，這是特征空間中兩個樣本點相似程度的反映。K近鄰模型（的特征空間一般是N 維實數(shù)向量空間）一般使用歐式距離(也就是中學學的空間兩個點之間的距離)，（另外還有曼哈頓距離，不用平方，不用開方，直接對應(yīng)坐標做差，然后取絕對值，再累加做和）。距離度量不同，所確定的最近鄰點不同。

4. 決策規(guī)則有分類決策規(guī)則和回歸決策規(guī)則兩種，

   • 分類決策通常采用多數(shù)表決， 回歸決策通常采用均值回歸，兩個都可以基于距離的遠近進行加權(quán)投票：距離越近的樣本權(quán)重越大。

注意：如果這是面試官問你的第一個問題，那他下面一定會基于你上面的回答繼續(xù)提問，所以接下來可能會問到：

1.1 什么是過擬合，什么是欠擬合，該怎么解決呢

這個問題要拆成四個問題去回答：解釋過擬合，解釋怎么解決過擬合；解釋欠擬合，解釋怎么解決欠擬合

1. 選擇的模型包含的參數(shù)過多，模型在訓練數(shù)據(jù)上表現(xiàn)很好，但是在測試數(shù)據(jù)上表現(xiàn)很差，這種情況叫過擬合（過擬合高 方差）；

2. 過擬合無法避免，只能緩解，可以通過

   • 正則化
   • 數(shù)據(jù)集增強：通過人工規(guī)則產(chǎn)生虛假數(shù)據(jù)來創(chuàng)造更多的訓練數(shù)據(jù)。
   • 噪聲注入：包括輸入噪聲注入、輸出噪聲注入、權(quán)重噪聲注入。將噪聲分別注入到輸入/輸出/權(quán)重參數(shù)中。
   • 早停（early stop）：當驗證集上的誤差沒有進一步改善時，算法提前終止。
     最好的解決方案是使用更多訓練數(shù)據(jù)。這樣得到的模型自然能夠更好地泛化。如無法采用這種解決方案，則次優(yōu)解決方案是使用正則化等技術(shù)

3. 與過擬合相對的是欠擬合，模型在訓練數(shù)據(jù)上表現(xiàn)就很差（欠擬合高偏差）。出現(xiàn)這種情況的原因有很多：模型不夠強大、過于正則化，或者根本沒有訓練足夠長的時間。

4. 解決欠擬合的方法有：
   - 增加新特征，可以考慮加入進特征組合、高次特征;
   - 更換模型;
   - 選擇較小的正則項參數(shù)
   - 增加訓練時間

1.2 交叉驗證是怎么回事兒？/通過交叉驗證怎么選擇K值

這個問題感覺圖文并茂的方式更能講清楚；選擇K值其實就是選擇不同的模型，所以交叉驗證是常用的模型選擇方法之一，另一種是正則化，后面再補充

交叉驗證

1.3 什么是多數(shù)表決規(guī)則

這個問題我不太確定是不是一定要寫出公式來，但是就是字面意思：在投票的時候，少數(shù)服從多數(shù)。

參考：

1. 統(tǒng)計學習方法-李航（第二版)
2. 探索過擬合和欠擬合
3. 機器學習防止欠擬合、過擬合方法
4. KNN