作為想在AI領(lǐng)域長(zhǎng)期發(fā)展的PM同學(xué)來(lái)說(shuō)，對(duì)算法有一個(gè)初步、通識(shí)的了解是非常有必要的。今天我們就從一個(gè)最為簡(jiǎn)單、易懂的“k-近鄰（KNN）算法”聊起，KNN屬于監(jiān)督學(xué)習(xí)算法，即可以用于分類，也可以用于回歸，后續(xù)還會(huì)逐步為大家介紹一些常用的其他算法。

作為想在AI領(lǐng)域長(zhǎng)期發(fā)展的PM同學(xué)來(lái)說(shuō)，對(duì)算法有一個(gè)初步、通識(shí)的了解是非常有必要的。

我們之所以要了解算法，不僅僅有利于和算法同學(xué)的溝通，更能深入的理解人工智能為產(chǎn)品賦能的過(guò)程，只有將這個(gè)過(guò)程了解透徹，才能清晰明確的把握產(chǎn)品的方向，挖掘產(chǎn)品的亮點(diǎn)。

那么，今天我們就從一個(gè)最為簡(jiǎn)單、易懂的“k-近鄰（KNN）算法”聊起，KNN屬于監(jiān)督學(xué)習(xí)算法，即可以用于分類，也可以用于回歸，后續(xù)還會(huì)逐步為大家介紹一些常用的其他算法。

KNN的核心思想可以用一句俗語(yǔ)表達(dá)：“物以類聚、人以群分”，想了解一個(gè)人，可以看他交什么樣的朋友。即它的核心思想是：如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本（距離最近的樣本）中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。

這里面提及的距離，一般可以選用歐氏距離、曼哈頓距離、閔式距離等等公式進(jìn)行計(jì)算，對(duì)于我們初步了解的產(chǎn)品經(jīng)理來(lái)講，就不上各種公式了。

我們用這個(gè)圖做一個(gè)簡(jiǎn)單的介紹，藍(lán)色方形（用B標(biāo)識(shí)）和紅色三角（R）代表兩個(gè)不同的分類，綠色圓形（C）是待分類樣本，根據(jù)KNN的思想，如果K=3，則C的最近鄰有1B、2R，根據(jù)少數(shù)服從多數(shù)原則，C應(yīng)該屬于“R”的類型。如果k=5呢?C的最近鄰有3B、2R，C是不是應(yīng)該屬于“B”類型了呢？

其中判定類別也有兩種方法：

1. 投票決定：少數(shù)服從多數(shù)，近鄰中哪個(gè)類別的點(diǎn)最多就分為哪類。
2. 加權(quán)投票法：根據(jù)距離的遠(yuǎn)近、對(duì)鄰近的投票進(jìn)行加權(quán)，距離越近咋權(quán)重越大（權(quán)重為距離平方的倒數(shù)。）

看到這兒，是不是有不少小伙伴產(chǎn)生了疑問(wèn)，那該如何選擇K值呢？K值的大小又將如何影響模型的效果呢？

關(guān)于K值的選擇，需要注意：

• k值過(guò)大，非相似數(shù)據(jù)被包含較多，造成噪聲增加而導(dǎo)致分類結(jié)果的降低；
• k值過(guò)小，得到的鄰近數(shù)過(guò)少，會(huì)降低分類精度，同時(shí)也會(huì)放大噪聲數(shù)據(jù)的干擾；

經(jīng)驗(yàn)規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根，通常采用交叉檢驗(yàn)來(lái)確定。

接下來(lái)我們簡(jiǎn)單介紹一下訓(xùn)練過(guò)程，有如下幾步：

1. 準(zhǔn)備數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理；
2. 選用合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)和測(cè)試元組；
3. 設(shè)定參數(shù)，如k；
4. 維護(hù)一個(gè)大小為k的的按距離由大到小的優(yōu)先級(jí)隊(duì)列，用于存儲(chǔ)最近鄰訓(xùn)練元組。隨機(jī)從訓(xùn)練元組中選取k個(gè)元組作為初始的最近鄰元組，分別計(jì)算測(cè)試元組到這k個(gè)元組的距離，將訓(xùn)練元組標(biāo)號(hào)和距離存入優(yōu)先級(jí)隊(duì)列；
5. 遍歷訓(xùn)練元組集，計(jì)算當(dāng)前訓(xùn)練元組與測(cè)試元組的距離，將所得距離L 與優(yōu)先級(jí)隊(duì)列中的最大距離Lmax
6. 進(jìn)行比較。若L>=Lmax，則舍棄該元組，遍歷下一個(gè)元組。若L < Lmax，刪除優(yōu)先級(jí)隊(duì)列中最大距離的元組，將當(dāng)前訓(xùn)練元組存入優(yōu)先級(jí)隊(duì)列。
7. ?遍歷完畢，計(jì)算優(yōu)先級(jí)隊(duì)列中k 個(gè)元組的多數(shù)類，并將其作為測(cè)試元組的類別。
8. 測(cè)試元組集測(cè)試完畢后計(jì)算誤差率，繼續(xù)設(shè)定不同的k值重新進(jìn)行訓(xùn)練，最后取誤差率最小的k 值。

基本概念和訓(xùn)練過(guò)程我們都簡(jiǎn)單的介紹清楚了，下面來(lái)講講K近鄰的優(yōu)勢(shì)及缺陷。

優(yōu)勢(shì)：

1. 簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練；
2. 特別適合于多分類問(wèn)題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好。

缺點(diǎn)：

1. 計(jì)算復(fù)雜度高、空間復(fù)雜度高；
2. 樣本嚴(yán)重不平衡時(shí)，如果一個(gè)類的樣本容量很大，而其他類很小，有可能導(dǎo)致輸入一個(gè)新樣本時(shí)，被誤判為該分類的概率會(huì)很大。

了解了算法的優(yōu)勢(shì)和局限性，下面就要了解一下它的適用領(lǐng)域了：

• 模式識(shí)別，特別是光學(xué)字符識(shí)別；
• 統(tǒng)計(jì)分類；
• 計(jì)算機(jī)視覺(jué)；
• 數(shù)據(jù)庫(kù)，如基于內(nèi)容的圖像檢索；
• 編碼理論（最大似然編碼）；
• 數(shù)據(jù)壓縮（mpeg-2標(biāo)準(zhǔn)）；
• 向?qū)到y(tǒng)；
• 網(wǎng)絡(luò)營(yíng)銷；
• DNA測(cè)序
• 拼寫(xiě)檢查，建議正確拼寫(xiě)；
• 剽竊偵查；
• 相似比分算法，用來(lái)推動(dòng)運(yùn)動(dòng)員的職業(yè)表現(xiàn)。

本文由 @燕然未勒 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載。

題圖來(lái)自 Unsplash ，基于 CC0 協(xié)議。