簡(jiǎn)介

又叫K-鄰近算法，是監(jiān)督學(xué)習(xí)中的一種分類算法。目的是根據(jù)已知類別的樣本點(diǎn)集求出待分類的數(shù)據(jù)點(diǎn)類別。

基本思想

kNN的思想很簡(jiǎn)單：在訓(xùn)練集中選取離輸入的數(shù)據(jù)點(diǎn)最近的k個(gè)鄰居，根據(jù)這個(gè)k個(gè)鄰居中出現(xiàn)次數(shù)最多的類別（最大表決規(guī)則），作為該數(shù)據(jù)點(diǎn)的類別。kNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。

算法復(fù)雜度

kNN是一種lazy-learning算法，分類器不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，因此訓(xùn)練時(shí)間復(fù)雜度為0；kNN分類的計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，也就是說(shuō)，如果訓(xùn)練集中文檔總數(shù)為n，那么kNN的分類時(shí)間復(fù)雜度為O(n)；因此，最終的時(shí)間復(fù)雜度是O(n)。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

1. 理論成熟，思想簡(jiǎn)單，既可以用來(lái)做分類也可以用來(lái)做回歸 ；
2. 適合對(duì)稀有事件進(jìn)行分類（例如：客戶流失預(yù)測(cè)）；
3. 特別適合于多分類問(wèn)題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽，例如：根據(jù)基因特征來(lái)判斷其功能分類)， kNN比SVM的表現(xiàn)要好。

缺點(diǎn)

1. 當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)；
2. 計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)；
3. 可理解性差，無(wú)法給出像決策樹(shù)那樣的規(guī)則。

代碼

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 20:53:14 2020

@author: Administrator
"""

# coding:utf-8

import numpy as np

def createDataset():
    '''
    創(chuàng)建訓(xùn)練集,特征值分別為搞笑鏡頭、擁抱鏡頭、打斗鏡頭的數(shù)量
    '''
    learning_dataset = {"寶貝當(dāng)家": [45, 2, 9, "喜劇片"],
              "美人魚(yú)": [21, 17, 5, "喜劇片"],
              "澳門風(fēng)云3": [54, 9, 11, "喜劇片"],
              "功夫熊貓3": [39, 0, 31, "喜劇片"],
              "諜影重重": [5, 2, 57, "動(dòng)作片"],
              "葉問(wèn)3": [3, 2, 65, "動(dòng)作片"],
              "倫敦陷落": [2, 3, 55, "動(dòng)作片"],
              "我的特工爺爺": [6, 4, 21, "動(dòng)作片"],
              "奔愛(ài)": [7, 46, 4, "愛(ài)情片"],
              "夜孔雀": [9, 39, 8, "愛(ài)情片"],
              "代理情人": [9, 38, 2, "愛(ài)情片"],
              "新步步驚心": [8, 34, 17, "愛(ài)情片"]}
    return learning_dataset

def kNN(learning_dataset,dataPoint,k):
    '''
    kNN算法,返回k個(gè)鄰居的類別和得到的測(cè)試數(shù)據(jù)的類別
    '''
    # s1:計(jì)算一個(gè)新樣本與數(shù)據(jù)集中所有數(shù)據(jù)的距離
    disList=[]
    for key,v in learning_dataset.items():
       #對(duì)距離進(jìn)行平方和開(kāi)根號(hào)
       d=np.linalg.norm(np.array(v[:3])-np.array(dataPoint))
       #round四舍五入保留兩位小數(shù)，并添加到集合中
       disList.append([key,round(d,2)])

    # s2:按照距離大小進(jìn)行遞增排序
    disList.sort(key=lambda dis: dis[1]) 
    # s3:選取距離最小的k個(gè)樣本
    disList=disList[:k]
    # s4:確定前k個(gè)樣本所在類別出現(xiàn)的頻率，并輸出出現(xiàn)頻率最高的類別
    labels = {"喜劇片":0,"動(dòng)作片":0,"愛(ài)情片":0}
    #從k個(gè)中進(jìn)行統(tǒng)計(jì)哪個(gè)類別標(biāo)簽最多
    for s in disList:  
        #取出對(duì)應(yīng)標(biāo)簽
        label = learning_dataset[s[0]] 
        labels[label[len(label)-1]] += 1
    labels =sorted(labels.items(),key=lambda asd: asd[1],reverse=True)

    return labels,labels[0][0]


if __name__ == '__main__':

    learning_dataset=createDataset()
    testData={"唐人街探案": [23, 3, 17, "？片"]}
    dataPoint=list(testData.values())[0][:3]
    
    k=6

    labels,result=kNN(learning_dataset,dataPoint,k)
    print(labels,result,sep='\n')