機器學習實戰（k-近鄰算法-入門篇）

k-近鄰算法概述

k-近鄰算法就是采用測量不同的特征值之間的距離進行分類

它的工作原理是：存在一個樣本資料集合，也稱作訓練樣本集，并且樣本集中每個資料都存在标簽，即我們知道樣本集中每一資料與所分類類别的對應關系。輸入沒有标簽的新資料後，将新資料的每個特征最相似資料（最鄰近）的分類标簽。一般來說，我們隻選擇樣本資料集中的前k個最相似的資料，這就是k-近鄰算法中的k的出處，通常k<=20(整數)。最後我們選擇k個最相似資料中出現次數最多的分類，最為新資料的分類。

優缺點

優點：精度高、對異常不敏感、無資料就輸入假定

缺點：計算複雜度高、空間複雜度高

适用資料範圍：數值型和标稱型

k-近鄰算法的一般流程

（1）、收集資料：可以使用任何方法

（2）、準備資料：距離計算所需要的資料，最好是結構化的資料格式

（3）、分析資料：可以使用任何方法

（4）、測試算法：計算錯誤率

（5）、使用算法：首先輸入樣本資料和結構化的輸出結果，然後運作k-近鄰算法判定輸入資料分别屬于哪個類，最後應用對計算 出的分類執行後續的處理

電影分類的例子

使用k-近鄰算法分類愛情片和動作片。有人曾經統計過很多電影的打鬥鏡頭和接吻鏡頭。假如有一部看過的電影，如何确定它是愛情片還是動作片？我們可以使用KNN來 解決這個問題。

每部電影的打鬥鏡頭、接吻鏡頭以及電影評估類型

電影名稱	打鬥鏡頭	接吻鏡頭	電影類型
Colifornia Man	3	104	愛情片
He’s Not Really into Dudes	2	100	愛情片
Beautiful Woman	1	81	愛情片
Kevin Longblade	101	10	動作片
Robo Slayer 3000	99	5	動作片
Amped II	98	2	動作片
？	18	90	未知

即使不知道未知電影的類型，我們也可以通過某種方法計算出來。首先計算出未知電影與樣本集中其他電影的距離。

現在我們得到了樣本中所有與未知電影的距離，按照遞增排序，可以找到k個距離最近的電影。假定k=3，則三個最靠近的電影依次是 He’s Not Really into Dudes 、Beautiful Woman 、 Colifornia Man。k-近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型。而這三部電影全是愛情片，是以我們判定未知電影屬于愛情片。

假設這裡有五組資料，五個對應的标簽以及一組未知标簽的資料如下，我們要來預測未知标簽的資料屬于哪一類

已知資料：

    A   1.0,1.1

    A   1.0,1.0

    B   0.0,0.0

    B   0.0,0.1

    B   0.0,0.1

未知資料

    1.0,1.0

代碼實作

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
'''
@Time    : 2018/8/13 16:15
@Author  :
@Site    : 
@File    : KNN.py
@Software: PyCharm
'''
from numpy import *
import operator

def createDataSet():
    """
    準備資料集
    A   1.0,1.1
    A   1.0,1.0
    B   0.0,0.0
    B   0.0,0.1
    B   0.0,0.1
    :return: group,labels
    """
    group = array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1], [0.0, 0.1]])
    labels = ['A', 'A', 'B', 'B', 'B']
    return group, labels


def classify(inX, dataSet, labels, k):
    """
     K-近鄰算法
    :param inX:用于分類的輸入向量
    :param dataSet: 輸入的訓練樣本
    :param labels: 向量的标簽
    :param k:用于選擇最近鄰居的數目
    :return:
    """
    dataSetSize = dataSet.shape[0]                  #擷取訓練樣本的個數
    diffMat = tile(inX,(dataSetSize, 1)) - dataSet  #tile(A,n) 将A重複n次構成一個新的數組
    sqDiffMat = diffMat**2                          #将兩向量之間的內插補點分别平方
    sqDistance = sqDiffMat.sum(axis=1)              #axis=1表述行，axis=0表述列
    distances = sqDistance**0.5                     #開方算出歐氏距離
    sortedDistancesIndex = distances.argsort()      #将距離從小到大排序并将其下表存入sortedDistanceIndex
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistancesIndex[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1   #統計各個标簽出現的次數
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

#----------------測試------------------
group, labels = createDataSet()
print(classify([1,1], group, labels, 3))
"""
結果輸出:A
"""