K-近鄰算法概述
簡(jiǎn)單地說(shuō)垂谢，k-近鄰算法采用測(cè)量不同特征值之間的距離的方法進(jìn)行分類疮茄。他的優(yōu)點(diǎn)是精度高、對(duì)異常值不敏感徙邻、無(wú)數(shù)據(jù)輸入設(shè)定畸裳。缺點(diǎn)是計(jì)算復(fù)雜度高、空間復(fù)雜度高怖糊。使用數(shù)據(jù)范圍為：數(shù)值型和標(biāo)稱型伍伤。
k-近鄰算法（kNN）的工作原理是：存在一個(gè)樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集扰魂，并且樣本集合中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系姐直。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后蒋畜，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中特征最相似（最近鄰）的分類標(biāo)簽插龄。一般來(lái)說(shuō)佣渴，我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似數(shù)據(jù)的數(shù)據(jù)，這就是k-近鄰算法中k的出處膨处，通常，k是不大于20的整數(shù)真椿。最后突硝，選擇k個(gè)最相似的數(shù)據(jù)中出現(xiàn)的次數(shù)最多的分類，作為新數(shù)據(jù)的分類解恰。
k-近鄰算法的一般流程
收集數(shù)據(jù)： 可以使用任何方法
準(zhǔn)備數(shù)據(jù)：距離計(jì)算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式
分析數(shù)據(jù)：可以使用任何方法
訓(xùn)練算法：此步驟不適合k-近鄰算法
測(cè)試算法：計(jì)算錯(cuò)誤率
使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果挟纱。然后運(yùn)行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類腐宋，最后應(yīng)用對(duì)計(jì)算出的分類執(zhí)行后續(xù)的處理。
k-近鄰算法的實(shí)施
對(duì)未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作：
計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)中的每個(gè)點(diǎn)與當(dāng)前點(diǎn)之間的距離
按照距離遞增次序排序
選取與當(dāng)前距離最小的k個(gè)點(diǎn)
確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率
返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類
點(diǎn)與點(diǎn)之間的距離的算法有很多欺嗤，這里使用了歐氏距離公式：
?
例如煎饼，點(diǎn)（0,0）與（1,2）之間的距離計(jì)算為：?
數(shù)據(jù)的歸一化
對(duì)于某些數(shù)據(jù)剃盾，其特征值之間的數(shù)值差異比較大淤袜，而差值最大的屬性對(duì)結(jié)果影響也很大。這會(huì)大大提高分類模型的錯(cuò)誤率积蔚。因此將該類數(shù)據(jù)歸一化是一個(gè)重要的操作烦周。下面的公式可以將任取值范圍的特征值轉(zhuǎn)換為0到1之間的值：?。其中漱贱，min和max分別是數(shù)據(jù)集中的最小特征值和最大特征值夭委。
如何測(cè)試分類器
分類器并不會(huì)得到百分百正確的結(jié)果，我們可以使用多種方法檢測(cè)分類器的正確率。此外分類器的性能也會(huì)受到多種因素的影響擎值，如分類器設(shè)置和數(shù)據(jù)集等逐抑。不同的算法在不同數(shù)據(jù)集上的表現(xiàn)可能完全不同。
為了測(cè)試分類器的效果进每，我們可以使用已知答案的數(shù)據(jù)命斧，檢驗(yàn)分類器給出的結(jié)果是否符合預(yù)期結(jié)果。通過(guò)大量的測(cè)試數(shù)據(jù)肉瓦，我們可以得到分類器的錯(cuò)誤率----分類器給出錯(cuò)誤結(jié)果的次數(shù)除以測(cè)試執(zhí)行的總數(shù)胃惜。錯(cuò)誤率是常用的評(píng)估方法，主要用于評(píng)估分類器在某個(gè)數(shù)據(jù)集上的執(zhí)行效果鲫趁。完美分類器的錯(cuò)誤率為0利虫，最差分類器的錯(cuò)誤率是1.0。
示例： 使用k-近鄰算法改進(jìn)約會(huì)網(wǎng)站的配對(duì)效果
數(shù)據(jù)集見(jiàn)：datingTestSet.txt(提取碼：80ms)疫剃。數(shù)據(jù)一共分四列硼讽，前三列為三種特征，第四列為三種人物類型固阁。我們將通過(guò)前三種特征值备燃，生成一個(gè)kNN分類器，來(lái)預(yù)測(cè)不同人對(duì)于你的吸引力并齐。
| 飛行里程數(shù)/年 | 視頻游戲時(shí)間百分比 | 每周消費(fèi)冰激凌公升數(shù) | 吸引力 |
|---|---|---|---|
| 40920 | 8.326976 | 0.953952 | largeDoses |
| 14488 | 7.153469 | 1.673904 | smallDoses |
| 26052 | 1.441871 | 0.805124 | didntLike |
約會(huì)網(wǎng)站K-近鄰分類器生成步驟：
收集數(shù)據(jù)：提供文本文件
準(zhǔn)備數(shù)據(jù)：使用python解析文本文件
測(cè)試算法：使用部分?jǐn)?shù)據(jù)作為測(cè)試樣本。計(jì)算分類器的錯(cuò)誤率
使用算法：產(chǎn)生簡(jiǎn)單的命令行程序唁奢，然后可以輸入一些特征數(shù)據(jù)以判斷對(duì)方是否為自己喜歡的類型麻掸。
python3代碼實(shí)現(xiàn)
#!/usr/bin/env python3
# coding: utf-8
# Author：Shen Yi
# Date ：2020/2/13 21:19
?
"""機(jī)器學(xué)習(xí)實(shí)戰(zhàn) 第二章 k-近鄰算法
?
k-近鄰算法的完整實(shí)現(xiàn)，包含了k-近鄰算法的距離計(jì)算脊奋，錯(cuò)誤率統(tǒng)計(jì)诚隙，數(shù)據(jù)集矩陣標(biāo)準(zhǔn)化以及一個(gè)戀愛(ài)網(wǎng)站的demo.
?
"""
?
from collections import Counter
from numpy import *
?
?
def knn_classify(in_x, data_set, labels, k_num):
""" implementation of algorithm of knn
?
calculation of distance between prediction and training, then sorted and extract the most common labels in top k_num closer data
?
:param in_x: the vector to predict
:param data_set: training data
:param labels: label of training data
:param k_num: number of k
:return: label of predict
"""
?
# calculation of distance
data_set_size = data_set.shape[0]
diff_mat = tile(in_x, (data_set_size, 1)) - data_set
distances = ((diff_mat ** 2).sum(axis=1)) ** 0.5
sort_distances_index = distances.argsort()
?
# extract the most common label
vote_labels = [labels[index] for index in sort_distances_index[0: k_num]]
most_label = Counter(vote_labels).most_common(1)[0][0]
return most_label
?
?
def auto_norm(data_set):
"""data normalization"""
?
min_vals = data_set.min(0)
max_vals = data_set.max(0)
ranges = max_vals - min_vals
m = data_set.shape[0]
norm_data_set = data_set - tile(min_vals, (m, 1))
norm_data_set = norm_data_set / tile(ranges, (m, 1))
return norm_data_set, ranges, min_vals
?
?
def dating_class_test(data_mat, labels, ho_ratio, k_num):
"""calculate the accuracy of the model"""
?
m = data_mat.shape[0]
error_count = 0
number_test_vecs = int(m * ho_ratio)
for i in range(number_test_vecs):
classifier_rslt = knn_classify(data_mat[i, :], data_mat[number_test_vecs: m, :], labels[number_test_vecs: m], k_num)
if classifier_rslt != labels[i]:
error_count += 1
print(f"the total error rate is: {error_count / number_test_vecs}")
return error_count / number_test_vecs
?
?
def demo_date():
"""demo： used knn algorithm model to predict the matching effect of dating websites"""
?
file_name = "data\\Ch02\\datingTestSet.txt"
lines = open(file_name).readlines()
lines_number = len(lines)
data_mat = zeros((lines_number, 3))
labels = []
index = 0
for line in lines:
line = line.strip().split('\t')
data_mat[index, :] = line[0: 3]
labels.append(line[-1])
index += 1
?
norm_data_set, ranges, min_vals = auto_norm(data_mat)
dating_class_test(norm_data_set, labels, 0.1, 3)
?
percent_tas = float(input("percentage of time spent playing video games: "))
ffmiles = float(input("frequent flier miles earned per year: "))
ice_cream = float(input("liters of ice cream consumed per year:"))
in_array = (array([ffmiles, percent_tas, ice_cream]) - min_vals) / ranges
classifier_result = knn_classify(in_array, norm_data_set, labels, 3)
print(f"you will probably like this person: {classifier_result}")
?
?
if __name__ == '__main__':
demo_date()
運(yùn)行結(jié)果：
the total error rate is: 0.05
percentage of time spent playing video games: 10
frequent flier miles earned per year: 10000
liters of ice cream consumed per year:0.5
you will probably like this person: smallDoses</pre>
從結(jié)果可以看出巫延，該分類器的錯(cuò)誤率為5%地消，在輸出一組特征值后，得到了預(yù)期的分類標(biāo)簽脉执。
