怎樣理解和實現(xiàn)KNN算法

今天就跟大家聊聊有關(guān)怎樣理解和實現(xiàn)KNN算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

knn介紹

鄰近算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。平常生活中我們都會下意識的運用到我們的判斷中，比如富人區(qū)和窮人區(qū)，判斷一個人是富人還是窮人根據(jù)他的朋友的判斷，就是運用了kNN的思想。

KNN是通過測量不同特征值之間的距離進行分類。它的的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。K通常是不大于20的整數(shù)。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
在KNN中，通過計算對象間距離來作為各個對象之間的非相似性指標(biāo)，避免了對象之間的匹配問題，在這里距離一般使用歐氏距離

KNN算法實現(xiàn)

主要參考劉建平Pinard的博文K近鄰法(KNN)原理小結(jié)，劉建平Pinard的博文對每個算法有很深刻的見解，一般在看不懂李航的《統(tǒng)計學(xué)習(xí)方法》的時候，去看劉大大的博客會有豁然開朗的感覺。他博文中提到scikit-learn里只使用了蠻力實現(xiàn)(brute-force)，KD樹實現(xiàn)(KDTree)和球樹(BallTree)實現(xiàn)，所以他的這篇文章中只討論這幾種算法的實現(xiàn)原理。其余的實現(xiàn)方法比如BBF樹，MVP樹等沒有做討論，需要對算法有更深一步了解的童鞋，移步劉建平Pinard的文章~

實戰(zhàn)代碼

這一部分主要是參考實戰(zhàn)，然后主要講解一些具體的實現(xiàn)~
下面的代碼為運行程序?qū)胨枰膸?/p>

from numpy import *
import operator

下面的程序主要實現(xiàn)了生成測試數(shù)據(jù)的功能

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels
group,labels = createDataSet()

輸出：

In [2]:group
Out[2]: array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])

In [3]: labels
Out[3]: ['A', 'A', 'B', 'B']

下面的代碼主要實現(xiàn)了利用knn分類的功能

def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    #tile 擴展矩陣的函數(shù)
    diffMat = tile(inX,(dataSetSize,1))-dataSet
    sqdiffMat = diffMat**2
    sqDistances = sqdiffMat.sum(axis = 1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()
    print(sortedDistIndicies)
    classCount={}
    for i in range(k):
        voteLabels = labels[sortedDistIndicies[i]]
        #dict.get  獲取指定鍵的值，默認(rèn)返回none，鍵值不存在時，不同于dict['key']直接返回error，也可以指定，下面指定為0
        classCount[voteLabels] = classCount.get(voteLabels,0)+1
    print(classCount)
    #Python3.5中：iteritems變?yōu)?span lang="EN-US">items(python2   classCount.iteritems())
    #items可以輸出dict中的（key，value）
    #sorted中的key參數(shù)傳入函數(shù)，operator.itemgetterr函數(shù)獲取的不是值，而是定義了一個函數(shù)，通過該函數(shù)作用到對象上才能獲取值。
    #operator.itemgetter(1) 為獲取classCount.items()中的第二個參數(shù)
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
    print(sortedClassCount)
    return sortedClassCount[0][0]

• 給定輸出，給出分類值

In [7]: classify0([0,0.2],group,labels,2)
[3 2 1 0]
{'B': 2}
[('B', 2)]
Out[6]: 'B'

深度解讀實戰(zhàn)代碼

argsort函數(shù)

argsort()函數(shù)是將x中的元素從小到大排列，提取其對應(yīng)的index(索引)，然后輸出到y。
輸出是按照從小到大的順序輸出的
例子：

import numpy as np
a = np.array([2,0,4,1,2,4,5])
a.argsort()

輸出為a從小到大排序后的index：

Out[12]: array([1, 3, 0, 4, 2, 5, 6], dtype=int64)

輸出為list的index，提取出來就是list從小到大的排序

排序解釋

dict.get vs dict[‘key’]

a = {'name': 'wang'}

dict[‘key’]輸出

a['age']
Out[16]: KeyError: 'age'

dict.get輸出：

a.get('age')
a.get('age', 10)
Out[17]: 10

dict[‘key’]只能獲取存在的值，如果不存在則觸發(fā)KeyError
而dict.get(key, default=None)則如果不存在則返回一個默認(rèn)值，如果設(shè)置了則是設(shè)置的，否則就是None

Python中sort 和 sorted函數(shù)

• 用sort函數(shù)對列表排序時會影響列表本身，而sorted不會

a = [1,2,1,4,3,5]
a.sort()
aOut[18]: [1, 1, 2, 3, 4, 5]

sort函數(shù)改變了a的順序

a = [1,2,1,4,3,5]
sorted(a)
aOut[19]: [1, 2, 1, 4, 3, 5]

sorted未改變a的順序

sorted函數(shù)

• sorted(iterable，cmp，key，reverse）（pyhton2的用法）

• python3 sorted取消了對cmp的支持。

list1 = [('david', 90), ('mary',90), ('sara',80),('lily',95)]
sorted(list1,cmp = lambda x,y: cmp(x[0],y[0]))
TypeError: 'cmp' is an invalid keyword argument for this function

• 用key函數(shù)排序

sorted(list1,key = lambda list1: list1[0])
Out[23]: [('david', 90), ('lily', 95), ('mary', 90), ('sara', 80)]

list1[0]表示用list中的第一個元素排序

sorted(list1,key = lambda list1: list1[1])
Out[24]: [('sara', 80), ('david', 90), ('mary', 90), ('lily', 95)]

list1[1]表示用list中的第二個元素排序

三道sorted面試題

1）key函數(shù)的運用

students = [('john', 'A', 15), ('jane', 'B', 12), ('dave','B', 10)]
sorted(students,key=lambda s: s[2]) #按照年齡來排序

2）多個字符的排序

‘asdf234GDSdsf23’這是一個字符串排序，排序規(guī)則：小寫<大寫<奇數(shù)<偶數(shù)

s = 'asdf234GDSdsf23'  #排序:小寫-大寫-奇數(shù)-偶數(shù)
#解法1：
print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isdigit() and int(x) % 2 == 0,x.isupper(),x))))
Out[25]: addffssDGS33224
#解法2：
print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isupper(),x.isdigit() and int(x) % 2 == 0,x))))
Out[26]: addffssDGS33224

解釋:

• Boolean 的排序會將 False 排在前，True排在后 . 

• 1.x.isdigit()的作用是把數(shù)字放在后邊,字母放在前邊.

• 2.x.isdigit() and int(x) % 2 == 0的作用是保證奇數(shù)在前，偶數(shù)在后。

• 3.x.isupper()的作用是在前面基礎(chǔ)上,保證字母小寫在前大寫在后.

• 4.最后的x表示在前面基礎(chǔ)上,對所有類別數(shù)字或字母排序。

• 若不進行第四步，每個內(nèi)部是未排序的，但是整體順序是按照要求排序的

print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isupper(),x.isdigit() and int(x) % 2 == 0))))
Out[27]: asdfdsfGDS33242

3） 特殊需求的排序

list1=[7, -8, 5, 4, 0, -2, -5]

要求1.正數(shù)在前負(fù)數(shù)在后 2.整數(shù)從小到大 3.負(fù)數(shù)從大到小

#解法1：
sorted(list1,key = lambda x:(x<0,x<0 and -x,x))
Out[28]:  [0, 4, 5, 7, -2, -5, -8]
解法2：
sorted(list1,key=lambda x:(x<0,abs(x)))
Out[29]: [0, 4, 5, 7, -2, -5, -8]

看完上述內(nèi)容，你們對怎樣理解和實現(xiàn)KNN算法有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。