k-近鄰算法（kNN）：采用測量不同特征值之間的距離方法進(jìn)行分類
-
優(yōu)點(diǎn)：
- 簡單好用诺核，容易理解抄肖，精度高，理論成熟窖杀，既可以用來做分類也可以用來做回歸漓摩；
- 可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)；
- 訓(xùn)練時間復(fù)雜度為O(n)入客；無數(shù)據(jù)輸入假定管毙；
- 對異常值不敏感。
-
缺點(diǎn)：
- 計算復(fù)雜性高桌硫；空間復(fù)雜性高夭咬；
- 樣本不平衡問題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）铆隘；
- 一般數(shù)值很大的時候不用這個卓舵，計算量太大。但是單個樣本又不能太少膀钠，否則容易發(fā)生誤分边器。
- 最大的缺點(diǎn)是無法給出數(shù)據(jù)的內(nèi)在含義。
使用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
-
工作原理
- 使用無標(biāo)簽數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征比較托修，
- 算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽，
- 只選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù)恒界，
- 選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類睦刃，作為新數(shù)據(jù)的分類。
-
算法詳解：
- k近鄰法
輸入：訓(xùn)練數(shù)據(jù)集
其中十酣，
為實(shí)例的特征向量涩拙，
為實(shí)例的類別，
耸采；實(shí)例特征向量
輸出：實(shí)例
所屬的類
兴泥。
（1）根據(jù)給定的距離度量，在訓(xùn)練集
中找出與
個點(diǎn)虾宇，涵蓋這
搓彻；
（2）在
式中，
為指示函數(shù)，即當(dāng)
時
- 線性掃描：最簡單的實(shí)現(xiàn)方法式
- kd樹：一種對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。二叉樹
相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分稀轨，構(gòu)成一系列的k維超矩形區(qū)域扼脐。kd樹的每個結(jié)點(diǎn)對應(yīng)于一個k維超矩形區(qū)域。通常選定坐標(biāo)軸上的中位數(shù)奋刽，得到的kd樹是平衡的輸入：
其中
,
瓦侮；
輸出
樹的算法。
（1）開始：構(gòu)造根結(jié)點(diǎn)佣谐，根結(jié)點(diǎn)對應(yīng)于包含
選擇為坐標(biāo)軸，以
由根結(jié)點(diǎn)生成深度為1的左趁蕊、右子結(jié)點(diǎn)：左子結(jié)點(diǎn)對應(yīng)坐標(biāo)
將落在切分超平面上的實(shí)例點(diǎn)保存在根結(jié)點(diǎn)掷伙。（2）重復(fù)：對深度為
的結(jié)點(diǎn)是己，選擇
為切分的坐標(biāo)軸，
任柜，以該結(jié)點(diǎn)的區(qū)域中所有實(shí)例的
由該結(jié)點(diǎn)生成深度為的左摔认、右子結(jié)點(diǎn)：左子結(jié)點(diǎn)對應(yīng)坐標(biāo)
將落在切分超平面上的實(shí)例點(diǎn)保存在該結(jié)點(diǎn)参袱。（3）直到兩個子區(qū)域沒有實(shí)例存在時停止。從而形成
- 用kd樹的最近鄰搜索：平均計算復(fù)雜度是
輸入：已構(gòu)造的
輸出：
（1）在
（2）以此葉結(jié)點(diǎn)為“當(dāng)前最近點(diǎn)”懂酱。
-
（3）遞歸地向上回退竹习，在每個結(jié)點(diǎn)進(jìn)行以下操作：
（a）如果該結(jié)點(diǎn)保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)距離目標(biāo)點(diǎn)更近，則以該實(shí)例點(diǎn)為“當(dāng)前最近點(diǎn)”列牺。
（b）當(dāng)前最近點(diǎn)一定存在于該結(jié)點(diǎn)一個子結(jié)點(diǎn)對應(yīng)的區(qū)域整陌。檢查該子結(jié)點(diǎn)的父結(jié)點(diǎn)的另一子結(jié)點(diǎn)對應(yīng)的區(qū)域是否有更近的點(diǎn)。具體地瞎领，檢查另一子結(jié)點(diǎn)對應(yīng)的區(qū)域是否與以目標(biāo)點(diǎn)為球心泌辫、以目標(biāo)點(diǎn)與“當(dāng)前最近點(diǎn)”間的距離為半徑的超球體相交。
如果相交九默，可能在另一個子結(jié)點(diǎn)對應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點(diǎn)更近的點(diǎn)震放，移動到另一個子結(jié)點(diǎn)。接著驼修，遞歸地進(jìn)行最近鄰搜索殿遂；
如果不相交，向上回退乙各。
（4）當(dāng)回退到根結(jié)點(diǎn)時墨礁，搜索結(jié)束。最后的“當(dāng)前最近點(diǎn)”即為
- k近鄰法
-
參數(shù)選擇
- k值
- 較卸骶病：近似誤差（對現(xiàn)有訓(xùn)練集的訓(xùn)練誤差）會減小，只有與輸入實(shí)例較近的（相似的）訓(xùn)練實(shí)例才會對預(yù)測結(jié)果起作用蹲坷。估計誤差（對測試集的測試誤差）會增大
- 較大：估計誤差減少驶乾，近似誤差會增大，模型趨于簡單
- k=N：完全卻決于訓(xùn)練集中類的多少循签，
- 一般取一個比較小的數(shù)值级乐。通常采用交叉驗(yàn)證法來選取最優(yōu)的k值。
- k值
-
一般流程
- 收集數(shù)據(jù)：可以使用任何方法县匠。
- 準(zhǔn)備數(shù)據(jù)：距離計算所需要的數(shù)值唇牧，最好是結(jié)構(gòu)化的數(shù)據(jù)格式。
- 分析數(shù)據(jù)：可以使用任何方法聚唐。
- 訓(xùn)練算法：此步驟不適用于k-近鄰算法。
- 測試算法：計算錯誤率腔召。
- 使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果杆查，然后運(yùn)行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理臀蛛。
手寫重要代碼
#導(dǎo)入庫
import numpy as np
import operator
#創(chuàng)建數(shù)據(jù)集合
def createDataSet():
group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
#歐式距離的k-近鄰算法
def classify0(inX, dataSet, labels, k):
"""
歐式距離的k-近鄰算法
params inX：單一輸入值亲桦，list or np.array
params dataSet：樣本集崖蜜，np.array
params labels：樣本集標(biāo)簽，list or np.array
params k：int
returns sortedClassCount[0][0]：分類的類別
"""
# 計算輸入值與樣本集的距離——基于歐式距離
#numpy函數(shù)shape[0]返回dataSet的行數(shù)
dataSetSize = dataSet.shape[0]
#在列向量方向上重復(fù)inX共1次(橫向)客峭，行向量方向上重復(fù)inX共dataSetSize次(縱向)
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
#二維特征相減后平方
sqDiffMat = diffMat**2
#sum()所有元素相加豫领，sum(0)列相加，sum(1)行相加
sqDistances = sqDiffMat.sum(axis=1)
#開方舔琅，計算出距離
distances = sqDistances**0.5
#返回distances中元素從小到大排序后的索引值
sortedDistIndicies = distances.argsort()
#定一個記錄類別次數(shù)的字典
classCount = {}
for i in range(k):
#取出前k個元素的類別
voteIlabel = labels[sortedDistIndicies[i]]
#dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認(rèn)值等恐。
#計算類別次數(shù)
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
#key=operator.itemgetter(1)根據(jù)字典的值進(jìn)行排序
#key=operator.itemgetter(0)根據(jù)字典的鍵進(jìn)行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
#返回次數(shù)最多的類別,即所要分類的類別
return sortedClassCount[0][0]
#輸入歸一化
def autoNorm(dataSet):
"""
newValue=(oldValue-min)/(max-min) 將認(rèn)一取值范圍的特征值轉(zhuǎn)化為[0,1]
params dataSet：歸一化數(shù)集
returns normDataSet：歸一化后的特征矩陣
returns ranges：數(shù)據(jù)范圍
returns minVals：數(shù)據(jù)最小值
"""
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m, 1))
normDataSet = normDataSet/np.tile(ranges, (m, 1)) #element wise divide
return normDataSet, ranges, minVals
#算法測試
def handwritingclasstest(data_test,data_test_label,data_train,data_train_label,k):
"""
算法測試函數(shù)
params data_test：測試數(shù)集
params data_test_label：測試集的標(biāo)簽
params data_train：訓(xùn)練數(shù)集
params data_train_label：訓(xùn)練集的標(biāo)簽
params k：k近鄰算法的k
"""
errorCount = 0.0
for i in range(data_test.shape[0]):
classifierResult = classify0(data_test[i, :], data_train, data_train_label, k)
print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, data_test_label[i]))
if (classifierResult != data_test_label[i]): errorCount += 1.0
print("錯誤率:%f%%" %(errorCount/float(numTestVecs)*100))
print(errorCount)
- sklearn實(shí)現(xiàn)算法
- sklearn.neighbors模塊實(shí)現(xiàn)kNN
- sklearn.neighbors.KNeighborsClassifier
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)- 參數(shù)
- params n_neighbors - 默認(rèn)為5，就是k-NN的k的值备蚓，選取最近的k個點(diǎn)课蔬。
- params weights - 默認(rèn)是uniform，參數(shù)可以是uniform郊尝、distance二跋，也可以是用戶自己定義的函數(shù)。uniform是均等的權(quán)重流昏，就說所有的鄰近點(diǎn)的權(quán)重都是相等的扎即。distance是不均等的權(quán)重，距離近的點(diǎn)比距離遠(yuǎn)的點(diǎn)的影響大况凉。用戶自定義的函數(shù)谚鄙，接收距離的數(shù)組，返回一組維數(shù)相同的權(quán)重茎刚。
-
params algorithm - 快速k近鄰搜索算法襟锐，默認(rèn)參數(shù)為auto，可以理解為算法自己決定合適的搜索算法膛锭。
- ball_tree將使用
sklearn.neighbors.BallTree是為了克服kd樹高緯失效而發(fā)明的粮坞，其構(gòu)造過程是以質(zhì)心C和半徑r分割樣本空間，每個節(jié)點(diǎn)是一個超球體; - kd_tree將使用
sklearn.neighbors.KDTree構(gòu)造kd樹存儲數(shù)據(jù)以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)初狰，kd樹也就是數(shù)據(jù)結(jié)構(gòu)中的二叉樹莫杈。以中值切分構(gòu)造的樹，每個結(jié)點(diǎn)是一個超矩形奢入，在維數(shù)小于20時效率高; - brute將使用蠻力搜索筝闹，也就是線性掃描，當(dāng)訓(xùn)練集很大時腥光，計算非常耗時
- ball_tree將使用
- params leaf_size - 默認(rèn)是30关顷，這個是構(gòu)造的kd樹和ball樹的大小。這個值的設(shè)置會影響樹構(gòu)建的速度和搜索速度武福，同樣也影響著存儲樹所需的內(nèi)存大小议双。需要根據(jù)問題的性質(zhì)選擇最優(yōu)的大小。
- params metric - 用于距離度量捉片，默認(rèn)度量是minkowski平痰，也就是p=2的歐氏距離(歐幾里德度量)汞舱。
- params p - p=1曼哈頓距離；p=2歐式距離
- params metric_params - 距離公式的其他關(guān)鍵參數(shù)宗雇，這個可以不管昂芜，使用默認(rèn)的None即可
- params n_jobs - 并行處理設(shè)置。默認(rèn)為1赔蒲，臨近點(diǎn)搜索并行工作數(shù)泌神。如果為-1，那么CPU的所有cores都用于并行工作嘹履。
- 方法
-
methods fit(X, y) - 使用X作為訓(xùn)練數(shù)據(jù)并將y作為目標(biāo)值來擬合模型 參數(shù)
- params X- {陣列式腻扇，稀疏矩陣，BallTree砾嫉，KDTree} - 訓(xùn)練數(shù)據(jù)幼苛。 如果數(shù)組或矩陣，如果metric ='precomputed'焕刮，則形成[n_samples舶沿，n_features]或[n_samples，n_samples]配并。
- params y - {數(shù)組式括荡，稀疏矩陣} - shape的目標(biāo)值= [n_samples]或[n_samples，n_outputs]
-
methods predict(X) - 預(yù)測提供的數(shù)據(jù)的類別標(biāo)簽
- params X - 測試樣本溉旋；類似數(shù)組畸冲，形狀（n_query，n_features）或（n_query观腊，n_indexed）如果metric =='precomputed'
- ruturns y - 每個數(shù)據(jù)樣本的類標(biāo)簽邑闲；形狀數(shù)組[n_samples]或[n_samples，n_outputs]
-
methods get_params(deep=True) - 獲取此估算工具的參數(shù)
- params deep - 如果為True梧油，將返回此估計器的參數(shù)并包含作為估算器的子對象苫耸；布爾值，可選
- returns params - 映射到其值的參數(shù)名稱儡陨。將字符串映射到任何字符串
-
methods kneighbors(X=None, n_neighbors=None, return_distance=True) - 找到一個點(diǎn)的K鄰居褪子。返回每個點(diǎn)的鄰居的索引和距離。
- params X:類似數(shù)組骗村，形狀（n_query嫌褪，n_features）或（n_query，n_indexed）如果metric ='''precomputed' - 查詢點(diǎn)或點(diǎn)胚股。如果未提供渔扎，則返回每個索引點(diǎn)的鄰居。在這種情況下信轿，查詢點(diǎn)不被視為自己的鄰居晃痴。
- params n_neighbors ： int - 要獲取的鄰居數(shù)（默認(rèn)值是傳遞給構(gòu)造函數(shù)的值）。
- params return_distance - 布爾值财忽，可選倘核。默認(rèn)為True。 如果為False即彪，則不會返回距離
- returns dist：數(shù)組 - 表示點(diǎn)數(shù)長度的數(shù)組紧唱，僅在return_distance = True時出現(xiàn)
- returns ind：數(shù)組 - 矩陣中最近點(diǎn)的指數(shù)。
- methods kneighbors_graph(X=None, n_neighbors=None, mode=’connectivity’) - 計算X中點(diǎn)的k-鄰居的（加權(quán)）圖
- methods predict_proba(X) - 測試數(shù)據(jù)X的返回概率估計隶校。
- methods score(X, y, sample_weight=None) - 返回給定測試數(shù)據(jù)和標(biāo)簽的平均精度漏益。
- methods set_params(**params) - 設(shè)置此估算器的參數(shù)。
-
methods fit(X, y) - 使用X作為訓(xùn)練數(shù)據(jù)并將y作為目標(biāo)值來擬合模型 參數(shù)
- 參數(shù)
- sklearn.neighbors.KNeighborsClassifier
- sklearn.neighbors模塊實(shí)現(xiàn)kNN
from sklearn.neighbors import KNeighborsClassifier as kNN
def kNNClassTest(data_test,data_test_label,data_train,data_train_label,k):
"""
params data_test：測試數(shù)集
params data_test_label：測試集的標(biāo)簽
params data_train：訓(xùn)練數(shù)集
params data_train_label：訓(xùn)練集的標(biāo)簽
params k：k近鄰算法的k
"""
#構(gòu)建kNN分類器
neigh = kNN(n_neighbors = k, algorithm = 'auto')
#擬合模型, data_train為訓(xùn)練數(shù)集,data_train_label為訓(xùn)練集的標(biāo)簽
neigh.fit(data_train, data_train_label)
#錯誤檢測計數(shù)
errorCount = 0.0
#測試數(shù)據(jù)的數(shù)量
mTest = data_test.shape[0]
#從文件中解析出測試集的類別并進(jìn)行分類測試
#獲得預(yù)測結(jié)果
classifierResult = neigh.predict(data_test)
for i in range(mTest):
print("分類返回結(jié)果為%d\t真實(shí)結(jié)果為%d" % (classifierResult[i], data_test_label[i]))
if(classifierResult[i] != data_test_label[i]):
errorCount += 1.0
print("總共錯了%d個數(shù)據(jù)\n錯誤率為%f%%" % (errorCount, errorCount/mTest * 100))
- 案例實(shí)現(xiàn)
- 案例1：約會網(wǎng)站配對
# 導(dǎo)入數(shù)據(jù)
def file2matrix(filename):
love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1}
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines) #get the number of lines in the file
returnMat = np.zeros((numberOfLines, 3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
index = 0
for line in arrayOLines:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
if(listFromLine[-1].isdigit()):
classLabelVector.append(int(listFromLine[-1]))
else:
classLabelVector.append(love_dictionary.get(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
#測試函數(shù)
def datingClassTest():
path = r'E:\C_all\Desktop\ML倉庫\機(jī)器學(xué)習(xí)實(shí)戰(zhàn)\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
hoRatio = 0.50 #hold out 10%
datingDataMat, datingLabels = file2matrix(path) #load data setfrom file
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
if (classifierResult != datingLabels[i]): errorCount += 1.0
print("the total error rate is: %f" % (errorCount / float(numTestVecs)))
print(errorCount)
datingClassTest()
the total error rate is: 0.068000
34.0
#應(yīng)用
def classifyPerson():
path = r'E:\C_all\Desktop\ML倉庫\機(jī)器學(xué)習(xí)實(shí)戰(zhàn)\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(input(\
"percentage of time spent playing video games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix(path)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([
ffMiles,
percentTats,
iceCream,
])
classifierResult = classify0((inArr - minVals) / ranges, normMat,
datingLabels, 3)
print("You will probably like this person: %s" %
resultList[classifierResult - 1])
classifyPerson()
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: in small doses
- 案例2：手寫數(shù)字分類
#數(shù)據(jù)導(dǎo)入
from tensorflow.examples.tutorials.mnist import input_data
# 利用tensorflow代碼下載MNIST
mnist = input_data.read_data_sets("/MNIST_data/", one_hot=False)
# 代碼中的one_hot=True深胳，表示將樣本標(biāo)簽轉(zhuǎn)化為one_hot編碼
#測試函數(shù)
def handwritingclasstest():
errorCount = 0.0
for i in range(mnist.test.images.shape[0]):
classifierResult = classify0(mnist.test.images[i, :], mnist.train.images, mnist.train.labels, 10)
print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, mnist.test.labels[i]))
if (classifierResult != mnist.test.labels[i]): errorCount += 1.0
print("the total error rate is: %f" % (errorCount / float(mnist.test.images.shape[0])))
print(errorCount)
handwritingclasstest()
the total error rate is: 0.033200
332.0
