算法理解：
K-近鄰算法測(cè)量待分類樣本的特征值與已經(jīng)分好類的樣本對(duì)應(yīng)的特征值之間的距離，最鄰近的一個(gè)或者幾個(gè)訓(xùn)練樣本的類別決定了待分類樣本所屬的類別。
工作原理：
存在一個(gè)樣本數(shù)據(jù)集合(訓(xùn)練樣本集)，并且每個(gè)訓(xùn)練樣本都有已知對(duì)應(yīng)的所屬分類(標(biāo)簽)。輸入待分類的新樣本后，將新樣本的每個(gè)特征與訓(xùn)練樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較。然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽。一般選前k個(gè)最相似的數(shù)據(jù)(一般k不大于20)。最后，選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新樣本的分類。
距離計(jì)算：
在KNN中，通過計(jì)算待測(cè)樣本和訓(xùn)練樣本的特征值之間的差異(距離)作為對(duì)象之間的相似性指標(biāo)，一般使用歐氏距離或曼哈頓距離：
2.jpg
k-近鄰算法優(yōu)點(diǎn)是精度高、對(duì)異常值不敏感、無數(shù)據(jù)輸入假定。缺點(diǎn)是計(jì)算復(fù)雜度高、空間復(fù)雜度高。適用數(shù)據(jù)范圍為數(shù)值型和標(biāo)稱型。
算法的描述：
1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。
# -*- 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ù)組的一個(gè)屬性，表示數(shù)組的維度
# 比如一個(gè) 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、先將一維矩陣擴(kuò)展和測(cè)試矩陣的維度一樣
# 2、將新生成的待測(cè)矩陣同測(cè)試矩陣進(jìn)行矩陣減法，再將矩陣的差的平方和開根得到距離
# 3、將距離排序并返回
#==============================================================================
# 1、 tile(A, reps):reps的數(shù)字從后往前分別對(duì)應(yīng)A的第N個(gè)維度的重復(fù)次數(shù)。
# 如（A,2）表示A的列變量重復(fù)2遍，
# tile（A,(2,3)）表示A的行變量重復(fù)2遍，列變量重復(fù)3遍
# tile（A,(2,2,3)）表示A的第一個(gè)維度重復(fù)2遍，第二個(gè)維度重復(fù)2遍，
# 第三個(gè)維度重復(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
# 其中矩陣的每一個(gè)元素都做平方操作
# [[ 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]，即將矩陣的行向量想加后得到一個(gè)新的一維向量
# c.sum(axis=1) =[3,14,2], 即每個(gè)向量將自己內(nèi)部元素加和作新一維向量里的一個(gè)元素
# 此處已經(jīng)將每一個(gè)行向量中的每一個(gè)元素都做了平方操作，并求和得到每一個(gè)向量之和
# 得到一個(gè)一維數(shù)組，其中有四個(gè)元素分別對(duì)應(yīng)了輸入元素與 4個(gè)測(cè)試樣本的平方距離
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對(duì)應(yīng)下表1，數(shù)值2對(duì)應(yīng)下表2，數(shù)值3，對(duì)應(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]
# 建造一個(gè)名為classCount的字典，Key是label，value是這個(gè)label出現(xiàn)的次數(shù)
classCount={}
for i in range(k):
# 這里很巧妙的地方在于，一開始測(cè)試數(shù)組和Label的位置是一一對(duì)應(yīng)的
# 所以這里可以通過上面獲得的測(cè)試數(shù)組的下標(biāo)index獲得對(duì)應(yīng)的分類labels[index]
voteLabel = labels[sortedDistIndex[i]]
# 這里將每一個(gè)[label : Value]賦值，Value為計(jì)算VoteLabel出現(xiàn)的次數(shù)
# 如果Label不在字典classCount中時(shí)，get()返回 0，存在則value加 1
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
# 根據(jù)字典classCount中的Value值對(duì)字典進(jìn)行排序，選出出現(xiàn)次數(shù)最多的Label
# sorted(iterable, cmp=None, key=None, reverse=False)
# return new sorted list
# 1、iterable：是可迭代類型的對(duì)象（這里的字典通過iteritems()進(jìn)行迭代）
# 2、cmp：用于比較的函數(shù)，比較什么由key決定，一般用Lamda函數(shù)
# 3、key：用列表元素的某個(gè)屬性或函數(shù)進(jìn)行作為關(guān)鍵字，迭代集合中的一項(xiàng);
# operator.itemgetter(1)表示獲得對(duì)象的第一個(gè)域的值(這里指value)
# 4、reverse：排序規(guī)則。reverse = True 降序 或者 reverse = False 升序。
#
# return： 一個(gè)經(jīng)過排序的可迭代類型對(duì)象，與iterable一樣。
# 這里返回排好序的[Label:value], 即 [('B', 2), ('A', 1)]
sortedClassCount = sorted(classCount.iteritems(),
key=operator.itemgetter(1), reverse=True)
# 返回可迭代對(duì)象的第一個(gè)域的第一值，也就是出現(xiàn)次數(shù)最多的Label
# sortedClassCount[0][1] 表示第一個(gè)域的第二個(gè)值，就是出現(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)換為矩陣方便我們后面做運(yù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) 僅有一個(gè)參數(shù)時(shí)，創(chuàng)建一個(gè)一維矩陣，一行 a 列
# zeros(a, b) 創(chuàng)建一個(gè) a X b 矩陣， a 行 b 列
# 這里取了數(shù)據(jù)的行數(shù)和前三個(gè)特征值(前三個(gè)是特征，第四個(gè)個(gè)是類別)創(chuàng)建一個(gè)矩陣
returnMat = zeros((numberOfLines,3))
# 建造一個(gè)名為 classLabelVector 的 List 用來存放最后列的Label
classLabelVector = []
# 這里的 index 指的是矩陣的第幾行，從 0 開始
index = 0
#（ 以下三行） 解析文件數(shù)據(jù)到列表
for line in arrayOlines:
# 去掉文本中句子中的換行符"/n",但依然保持一行四個(gè)元素
line = line.strip()
# 以 ‘\t’(tab符號(hào))分個(gè)字符串，文本中的數(shù)據(jù)是以tab分開的
# 另外需要注意 split() 函數(shù)返回一個(gè) List對(duì)象
# 如：['30254', '11.592723', '0.286188', '3']
listFromLine = line.split('\t')
# 選取前l(fā)istFromLine的三個(gè)元素，存儲(chǔ)在特征矩陣中
# returnMat[index,:]這里需要注意，因?yàn)閞eturnMat是一個(gè)矩陣
# 其中的 index指的是矩陣中的第幾個(gè)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兩個(gè)元素
#
# listFromLine[0:3]切片開始于0、停止于3，也就是取了下標(biāo)為0,1,2的元素
# 將listFromLine[0:3]的第0號(hào)到2號(hào)元素賦值給特征矩陣returnMat對(duì)應(yīng)特征中
returnMat[index,:] = listFromLine[0:3]
# listFromLine[-1] 取listFromLine的最后一列標(biāo)簽類(將其強(qiáng)行轉(zhuǎn)換為int類型)
# 同時(shí)將該類別標(biāo)簽按順序加入到標(biāo)簽向量classLabelVector中
classLabelVector.append(int(listFromLine[-1]))
# index加 1，矩陣存取下一個(gè)list
index += 1
return returnMat,classLabelVector
在這先根據(jù)特征值，利用Matplotlib繪制類別的散點(diǎn)圖。
import matplotlib
# matplotlib的pyplot子庫(kù)提供了和matlab類似的繪圖API，方便用戶快速繪制2D圖表。
import matplotlib.pyplot as plt
# 我們先利用寫好的KNN.py文件中的file2matrix()函數(shù)將數(shù)據(jù)轉(zhuǎn)為矩陣
datingDataMat, datingLabels = KNN.file2matrix(filename)
# 這里創(chuàng)建了一個(gè)新的 figure，我們要在上面作圖
fig = plt.figure()
# add_subplot(111)相當(dāng)于在figure上添加子圖
# 其中 111 的意思是，將子圖切割成 1行 1列的圖，并在第 1 塊上作畫
# 所以這里只有一副畫
# 再舉個(gè)例子 add_subplot(22x)，將子圖切割成 2行 2列的圖，并在第 X 塊上作畫
ax = fig.add_subplot(111)
# 利用scatter()函數(shù)分別取已經(jīng)處理好的矩陣datingDataMat的第一列和第二列數(shù)據(jù)
# 并用不同顏色將類別標(biāo)識(shí)出來
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ū)分的散點(diǎn)圖：
3.png
（紅色的點(diǎn)表示非常喜歡，綠色的點(diǎn)表示一般喜歡，藍(lán)色的點(diǎn)表示并不喜歡）
觀察上圖我們不難發(fā)現(xiàn)一個(gè)問題，如果當(dāng)某一個(gè)特征值與其他的特征值的差異過大的話，如果不加權(quán)重或各特征權(quán)重均衡的話，很可能會(huì)影響到最后的分類，比如例子中的飛行距離，遠(yuǎn)遠(yuǎn)大于其他兩個(gè)特征值，在這種情況下，特征的距離就會(huì)受飛行距離特征值得影響。所以我們需要將數(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)
# 返回的是一個(gè)一維矩陣
minVals = dataSet.min(0)
# max(0)取矩陣每一列的最大值
# max(1)取矩陣每一列的最大值
# 返回的是一個(gè)一維矩陣
maxVals = dataSet.max(0)
# ranges也是一個(gè)一維矩陣
ranges = maxVals - minVals
# shape(dataSet) 返回一個(gè)記錄有矩陣維度的tuple
# 例如：np.shape([[1, 2]]) = (1, 2)
# zeros(shape)返回一個(gè)具有 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!
