程一艦

數(shù)據(jù)技術(shù)處

? ? ? K最近鄰(kNN，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。KNN是通過測量不同特征值之間的距離進行分類。其基本思想可以用這樣一句俗語來解釋——“近朱者赤,近墨者黑”。

一、原理介紹K近鄰的思路是如果一個樣本在特征空間中的k個最鄰近的樣本中的大多數(shù)屬于某一個類別，則該樣本也劃分為這個類別。通過下面的這張圖就好理解了：如果要確定綠點屬于哪個顏色(紅色或者藍色)，要做的就是選出距離目標(biāo)點距離最近的k個點，看這k個點的大多數(shù)顏色是什么顏色。當(dāng)k取3的時候，我們可以看出距離最近的三個，分別是紅色、紅色、藍色，因此得到目標(biāo)點為紅色。

二、算法步驟

K緊鄰分類主要分為以下幾個步驟：

1)計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離；2)按照距離的遞增關(guān)系進行排序；3)選取距離最小的K個點；4)確定前K個點所在類別的出現(xiàn)頻率；5)返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類三、實例說明下面用一個經(jīng)過改造了的Peter Harrington的《機器學(xué)習(xí)實戰(zhàn)》中電影分類的例子(當(dāng)然實際情況不可能這么簡單)來說明該算法的用法。第一步：準(zhǔn)備下電影分類數(shù)據(jù)集(電影名稱與分類來自于優(yōu)酷網(wǎng)；鏡頭數(shù)量則純屬虛構(gòu))：上面數(shù)據(jù)集中序號1-12為已知的電影分類，分為喜劇片、動作片、愛情片三個種類，使用的特征值分別為搞笑鏡頭、打斗鏡頭、擁抱鏡頭的數(shù)量。那么來了一部新電影《唐人街探案》，它屬于上述3個電影分類中的哪個類型？用KNN是怎么做的呢？首先，我們構(gòu)建一個已分好類的數(shù)據(jù)集。對于一個規(guī)模巨大的數(shù)據(jù)集，顯然數(shù)據(jù)庫是更好的選擇。這里為了方便驗證，使用Python的字典dict構(gòu)造數(shù)據(jù)集。第二步：計算一個新樣本與數(shù)據(jù)集中所有數(shù)據(jù)的距離。這里的新樣本就是："唐人街探案": [23, 3, 17, "？片"]。歐式距離是一個非常簡單又最常用的距離計算方法。其中x,y為2個樣本，n為維度，xi，yi為x，y第i個維度上的特征值。如x為："唐人街探案": [23, 3, 17, "？片"]，y為："倫敦陷落": [2, 3, 55, "動作片"]，則兩者之間的距離為：下面為求與數(shù)據(jù)集中所有數(shù)據(jù)的距離代碼：第三步：按照距離大小進行遞增排序。KNN.sort(key=lambda dis: dis[1])輸出結(jié)果：第四步：選取距離最小的*k**個樣本。*這里取k=5；KNN=KNN[:5]輸出：[['我的特工爺爺', 17.49], ['美人魚', 18.55], ['功夫熊貓3', 21.47], ['寶貝當(dāng)家', 23.43], ['澳門風(fēng)云3', 32.14]]第五步：確定前*k**個樣本所在類別出現(xiàn)的頻率，并輸出出現(xiàn)頻率最高的類別。*輸出結(jié)果：[('喜劇片', 4), ('動作片', 1), ('愛情片', 0)]喜劇片四、總結(jié)

KNN算法是最簡單有效的分類算法，簡單且容易實現(xiàn)。當(dāng)訓(xùn)練數(shù)據(jù)集很大時，需要大量的存儲空間，而且需要計算待測樣本和訓(xùn)練數(shù)據(jù)集中所有樣本的距離，所以非常耗時。KNN對于隨機分布的數(shù)據(jù)集分類效果較差，對于類內(nèi)間距小，類間間距大的數(shù)據(jù)集分類效果好，而且對于邊界不規(guī)則的數(shù)據(jù)效果好于線性分類器。KNN對于樣本不均衡的數(shù)據(jù)效果不好，需要進行改進。改進的方法時對k個近鄰數(shù)據(jù)賦予權(quán)重，比如距離測試樣本越近，權(quán)重越大。KNN很耗時，時間復(fù)雜度為O(n)，一般適用于樣本數(shù)較少的數(shù)據(jù)集，當(dāng)數(shù)據(jù)量大時，可以將數(shù)據(jù)以樹的形式呈現(xiàn)，能提高速度，常用的有kd-tree和ball-tree。大數(shù)據(jù)平臺將一如既往的為各種數(shù)據(jù)挖掘類應(yīng)用提供算力支持，為我行金融科技發(fā)展打造堅持的大數(shù)據(jù)平臺支撐。

總結(jié)

以上是生活随笔為你收集整理的数据挖掘算法_技术分享|大数据挖掘算法之KNNk近邻算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。