算法理解：
K-近鄰算法測量待分類樣本的特征值與已經(jīng)分好類的樣本對應(yīng)的特征值之間的距離，最鄰近的一個或者幾個訓(xùn)練樣本的類別決定了待分類樣本所屬的類別戴而。
工作原理：
存在一個樣本數(shù)據(jù)集合(訓(xùn)練樣本集)，并且每個訓(xùn)練樣本都有已知對應(yīng)的所屬分類(標(biāo)簽)捐康。輸入待分類的新樣本后掠剑，將新樣本的每個特征與訓(xùn)練樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較。然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽签钩。一般選前k個最相似的數(shù)據(jù)(一般k不大于20)。最后坏快，選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類铅檩，作為新樣本的分類。
距離計算：
在KNN中莽鸿，通過計算待測樣本和訓(xùn)練樣本的特征值之間的差異(距離)作為對象之間的相似性指標(biāo)昧旨，一般使用歐氏距離或曼哈頓距離：
2.jpg
k-近鄰算法優(yōu)點是精度高拾给、對異常值不敏感、無數(shù)據(jù)輸入假定兔沃。缺點是計算復(fù)雜度高蒋得、空間復(fù)雜度高。適用數(shù)據(jù)范圍為數(shù)值型和標(biāo)稱型粘拾。
算法的描述：
1）計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離窄锅；
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個點缰雇；
4）確定前K個點所在類別的出現(xiàn)頻率入偷；
5）返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。
# -*- coding: utf-8 -*-
""" k-Nearest Neighbors
Created on Mon Jan 23 12:56:00 2017
@author: xieyuxi
"""
from numpy import *
import operator
import numpy as np
def createDataSet():
group = array([[1.0, 1.1],[1.0,1.0],[0,0],[0,0.1]])
lables = ['A','A','B','B']
return group, lables
print group, lables
createDataSet()
""" Classify the unknown vector input into defined classes
1械哟、calculate the distance between inX and the current point
2疏之、sort the distances in increasing order
3、take k items with lowest distances to inX
4暇咆、find the majority class among these items
5锋爪、return the majority class as our prediction for the class of inX
Args:
inX : the input vector to classify
dataSet : the full matrix of training examples
labels : a vector of labels from the training examples
k : the number of nearest neighbors to use in the voting
Attention：
The labels vector should have as many elements in it
as there are rows in the dataSet matrix.
Returns:
the majority class as our prediction for the class of inX
Raises:
None
"""
def classify0(inX, dataSet, labels, k):
# shape是numpy的數(shù)組的一個屬性，表示數(shù)組的維度
# 比如一個 n x m的數(shù)組 Y(n 行 m列)爸业，Y.shape表示(n,m)
# 所以 Y.shape[0]等于 n, Y.shape[1]等于 m
# dataSet是4X2的數(shù)組其骄，所以此處dataSetSize等于4
dataSetSize = dataSet.shape[0] # 4
# 1、先將一維矩陣擴展和測試矩陣的維度一樣
# 2扯旷、將新生成的待測矩陣同測試矩陣進(jìn)行矩陣減法拯爽，再將矩陣的差的平方和開根得到距離
# 3、將距離排序并返回
#==============================================================================
# 1钧忽、 tile(A, reps):reps的數(shù)字從后往前分別對應(yīng)A的第N個維度的重復(fù)次數(shù)毯炮。
# 如（A,2）表示A的列變量重復(fù)2遍，
# tile（A,(2,3)）表示A的行變量重復(fù)2遍耸黑，列變量重復(fù)3遍
# tile（A,(2,2,3)）表示A的第一個維度重復(fù)2遍桃煎，第二個維度重復(fù)2遍，
# 第三個維度重復(fù)3遍大刊。
# Examples：
# ----------------------------------------
# # a = np.array([0, 1, 2])
# # np.tile(a, 2)
# array([0, 1, 2, 0, 1, 2])
# # np.tile(a, (2, 3))
# array([[0, 1, 2, 0, 1, 2, 0, 1, 2],
# [0, 1, 2, 0, 1, 2, 0, 1, 2]])
# ----------------------------------------
# # b = np.array([[1, 2], [3, 4]])
# # np.tile(b, 2)
# array([[1, 2, 1, 2],
# [3, 4, 3, 4]])
# # np.tile(b, (2, 1))
# array([[1, 2],
# [3, 4],
# [1, 2],
# [3, 4]])
#
# 2为迈、diffMat矩陣：先將輸入的值復(fù)制到和訓(xùn)練樣本同行，再做減法
# 以[0,0]為例：
# [0,0] to array([[0, 0] [[0, 0] [[1.0,1.1] [[-1. -1.1]
# [0, 0] to [0, 0] - [1.0,1.0] to [-1. -1. ]
# [0, 0] [0, 0] [0,0] [ 0. 0. ]
# [0, 0]]) [0, 0]] [0,0.1]] [ 0. -0.1]]
#==============================================================================
diffMat = tile(inX, (dataSetSize,1)) - dataSet
# 其中矩陣的每一個元素都做平方操作
# [[ 1. 1.21]
# [ 1. 1. ]
# [ 0. 0. ]
# [ 0. 0.01]]
sqDiffMat = diffMat**2
# axis=0, 表示列缺菌。 axis=1, 表示行曲尸。
# example：
# c = np.array([[0, 2, 1], [3, 5, 6], [0, 1, 1]])
# c.sum() = 19
# c.sum(axis=0) =[3 8 8]，即將矩陣的行向量想加后得到一個新的一維向量
# c.sum(axis=1) =[3,14,2], 即每個向量將自己內(nèi)部元素加和作新一維向量里的一個元素
# 此處已經(jīng)將每一個行向量中的每一個元素都做了平方操作男翰，并求和得到每一個向量之和
# 得到一個一維數(shù)組，其中有四個元素分別對應(yīng)了輸入元素與 4個測試樣本的平方距離
sqDistances = sqDiffMat.sum(axis=1) # [ 2.21 2. 0. 0.01]
# 將平方距離開方
distances = sqDistances**0.5 # [ 1.48660687 1.41421356 0. 0.1 ]
# argsort函數(shù)返回的是數(shù)組值從小到大的索引值
# examples:
# # x = np.array([3, 1, 2])
# # np.argsort(x)
# array([1, 2, 0]) 數(shù)值1對應(yīng)下表1纽乱，數(shù)值2對應(yīng)下表2蛾绎，數(shù)值3，對應(yīng)下標(biāo)0
# [1.48660687 1.41421356 0.0 0.1 ] to [2 3 1 0]
sortedDistIndex = distances.argsort() # [2 3 1 0]
# 建造一個名為classCount的字典，Key是label租冠，value是這個label出現(xiàn)的次數(shù)
classCount={}
for i in range(k):
# 這里很巧妙的地方在于鹏倘，一開始測試數(shù)組和Label的位置是一一對應(yīng)的
# 所以這里可以通過上面獲得的測試數(shù)組的下標(biāo)index獲得對應(yīng)的分類labels[index]
voteLabel = labels[sortedDistIndex[i]]
# 這里將每一個[label : Value]賦值，Value為計算VoteLabel出現(xiàn)的次數(shù)
# 如果Label不在字典classCount中時顽爹，get()返回 0纤泵，存在則value加 1
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
# 根據(jù)字典classCount中的Value值對字典進(jìn)行排序，選出出現(xiàn)次數(shù)最多的Label
# sorted(iterable, cmp=None, key=None, reverse=False)
# return new sorted list
# 1镜粤、iterable：是可迭代類型的對象（這里的字典通過iteritems()進(jìn)行迭代）
# 2捏题、cmp：用于比較的函數(shù)，比較什么由key決定肉渴，一般用Lamda函數(shù)
# 3公荧、key：用列表元素的某個屬性或函數(shù)進(jìn)行作為關(guān)鍵字，迭代集合中的一項;
# operator.itemgetter(1)表示獲得對象的第一個域的值(這里指value)
# 4同规、reverse：排序規(guī)則循狰。reverse = True 降序 或者 reverse = False 升序。
#
# return： 一個經(jīng)過排序的可迭代類型對象券勺，與iterable一樣绪钥。
# 這里返回排好序的[Label:value], 即 [('B', 2), ('A', 1)]
sortedClassCount = sorted(classCount.iteritems(),
key=operator.itemgetter(1), reverse=True)
# 返回可迭代對象的第一個域的第一值，也就是出現(xiàn)次數(shù)最多的Label
# sortedClassCount[0][1] 表示第一個域的第二個值关炼，就是出現(xiàn)最多次數(shù)Label出現(xiàn)次數(shù)
return sortedClassCount[0][0]
本案例的數(shù)據(jù)被置于txt文件中程腹，所以需要我們將數(shù)據(jù)從txt文件中抽出并做處理。所以我們準(zhǔn)備函數(shù)file2matrix()將txt的數(shù)據(jù)轉(zhuǎn)換為矩陣方便我們后面做運算盗扒。
""" Parsing data from a text file
Change the text file data to the format so that the classifier can accept and use it
Args:
filename string
Returns:
A matrix of training examples,
A vector of class labels
Raises:
None
"""
def file2matrix(filename):
# 根據(jù)文件名打開文件
fr = open(filename)
# 讀取每一行的數(shù)據(jù)
# txt文件中的數(shù)據(jù)類似："40920 8.326976 0.953952 largeDoses"W
arrayOlines = fr.readlines()
# 得到文件行數(shù)
numberOfLines = len(arrayOlines)
# 創(chuàng)建返回的Numpy矩陣
# zeros(a) 僅有一個參數(shù)時跪楞，創(chuàng)建一個一維矩陣，一行 a 列
# zeros(a, b) 創(chuàng)建一個 a X b 矩陣侣灶， a 行 b 列
# 這里取了數(shù)據(jù)的行數(shù)和前三個特征值(前三個是特征甸祭，第四個個是類別)創(chuàng)建一個矩陣
returnMat = zeros((numberOfLines,3))
# 建造一個名為 classLabelVector 的 List 用來存放最后列的Label
classLabelVector = []
# 這里的 index 指的是矩陣的第幾行，從 0 開始
index = 0
#（ 以下三行） 解析文件數(shù)據(jù)到列表
for line in arrayOlines:
# 去掉文本中句子中的換行符"/n",但依然保持一行四個元素
line = line.strip()
# 以 ‘\t’(tab符號)分個字符串褥影，文本中的數(shù)據(jù)是以tab分開的
# 另外需要注意 split() 函數(shù)返回一個 List對象
# 如：['30254', '11.592723', '0.286188', '3']
listFromLine = line.split('\t')
# 選取前l(fā)istFromLine的三個元素池户，存儲在特征矩陣中
# returnMat[index,:]這里需要注意，因為returnMat是一個矩陣
# 其中的 index指的是矩陣中的第幾個list
# 例如 listMat = [[list1]
# [list2]
# [list3]
# ......
# [listn]]
# listMat[0]表示的是矩陣listMat中的第1行凡怎，即 [list1]
# listMat[2,:] 表示的是矩陣listMat中的第3行的所有元素
# listMat[2,0:2] 表示矩陣listMat中的第3行下標(biāo)為 0和1兩個元素
#
# listFromLine[0:3]切片開始于0校焦、停止于3，也就是取了下標(biāo)為0,1,2的元素
# 將listFromLine[0:3]的第0號到2號元素賦值給特征矩陣returnMat對應(yīng)特征中
returnMat[index,:] = listFromLine[0:3]
# listFromLine[-1] 取listFromLine的最后一列標(biāo)簽類(將其強行轉(zhuǎn)換為int類型)
# 同時將該類別標(biāo)簽按順序加入到標(biāo)簽向量classLabelVector中
classLabelVector.append(int(listFromLine[-1]))
# index加 1统倒，矩陣存取下一個list
index += 1
return returnMat,classLabelVector
在這先根據(jù)特征值寨典，利用Matplotlib繪制類別的散點圖。
import matplotlib
# matplotlib的pyplot子庫提供了和matlab類似的繪圖API房匆，方便用戶快速繪制2D圖表耸成。
import matplotlib.pyplot as plt
# 我們先利用寫好的KNN.py文件中的file2matrix()函數(shù)將數(shù)據(jù)轉(zhuǎn)為矩陣
datingDataMat, datingLabels = KNN.file2matrix(filename)
# 這里創(chuàng)建了一個新的 figure报亩，我們要在上面作圖
fig = plt.figure()
# add_subplot(111)相當(dāng)于在figure上添加子圖
# 其中 111 的意思是，將子圖切割成 1行 1列的圖井氢，并在第 1 塊上作畫
# 所以這里只有一副畫
# 再舉個例子 add_subplot(22x)弦追，將子圖切割成 2行 2列的圖，并在第 X 塊上作畫
ax = fig.add_subplot(111)
# 利用scatter()函數(shù)分別取已經(jīng)處理好的矩陣datingDataMat的第一列和第二列數(shù)據(jù)
# 并用不同顏色將類別標(biāo)識出來
ax.scatter(datingDataMat[:,0], datingDataMat[:,1],
15.0*array(datingLabels), 15.0*array(datingLabels))
# 展示我們做好的 figure
plt.show()
下圖是很好地解釋add_subplot(22x)：
5 (1).png
根據(jù)矩陣第一列和第二列數(shù)據(jù)可以獲得以下帶有顏色類別區(qū)分的散點圖：
3.png
（紅色的點表示非常喜歡花竞，綠色的點表示一般喜歡劲件，藍(lán)色的點表示并不喜歡）
觀察上圖我們不難發(fā)現(xiàn)一個問題，如果當(dāng)某一個特征值與其他的特征值的差異過大的話约急，如果不加權(quán)重或各特征權(quán)重均衡的話零远，很可能會影響到最后的分類，比如例子中的飛行距離烤宙，遠(yuǎn)遠(yuǎn)大于其他兩個特征值遍烦，在這種情況下，特征的距離就會受飛行距離特征值得影響躺枕。所以我們需要將數(shù)據(jù)進(jìn)行歸一化服猪，即將所有數(shù)據(jù)都變?yōu)?0~1 之間的數(shù)，目的是讓數(shù)據(jù)的影響都能比較均衡拐云。
""" Normalizing numeric values
Normalize the data to values between 0 and 1.
Formula:
newValue = (oldValue-min)/(max-min)
In the normalization procedure, the variables min and max are the
smallest and largest values in the dataset.
Args:
dataSet: the data set to be normalized
Returns:
A normalized data set
Raises:
None
"""
def autoNorm(dataSet):
# min(0)取矩陣每一列的最小值
# min(1)取矩陣每一行的最小值
# Examples:
# array([[1,2]
# [3,4]
# [5,6]])
# min(array,0) = [1,2]
# min(array,1) = [1,3,5]
# 這里同： minVals = np.min(dataSet,0)
# 返回的是一個一維矩陣
minVals = dataSet.min(0)
# max(0)取矩陣每一列的最大值
# max(1)取矩陣每一列的最大值
# 返回的是一個一維矩陣
maxVals = dataSet.max(0)
# ranges也是一個一維矩陣
ranges = maxVals - minVals
# shape(dataSet) 返回一個記錄有矩陣維度的tuple
# 例如：np.shape([[1, 2]]) = (1, 2)
# zeros(shape)返回一個具有 shape 維度的矩陣罢猪，并且所有元素用 0 填充
normDataSet = zeros(shape(dataSet))
# m 表示 dataSet 矩陣的行數(shù)
# dataSet.shape[1] 表示矩陣的列數(shù)
m = dataSet.shape[0]
# tile(minVals, (m,1)) 首先將 minVals 復(fù)制為 m 行的矩陣
# examples：
# if minVals = [[1,2,3]]
# tile(minVals, (3,1))(行數(shù)復(fù)制 3 遍，列保持不變)
# return [[1,2,3]
# [1,2,3]
# [1,2,3]]
normDataSet = dataSet - tile(minVals, (m,1))
# 同上叉瘩，將 一維矩陣 ranges 復(fù)制 m行膳帕，再讓矩陣中的元素做商
normDataSet = normDataSet/tile(ranges, (m,1))
# 返回歸一化的矩陣，最大與最小值的差值矩陣薇缅，和最小值矩陣
return normDataSet, ranges, minVals
4.png
（上圖為歸一化后的特征值）
我自己的博客地址為：謝雨熹的學(xué)習(xí)博客
歡迎大家來交流危彩！
Talk is cheap, show me your code!
