這篇文章主要介紹了機器學習之KNN算法原理及Python實作方法,結合執行個體形式詳細分析了機器學習KNN算法原理以及Python相關實作步驟、操作技巧與注意事項,需要的朋友可以參考下
本文執行個體講述了機器學習之KNN算法原理及Python實作方法。分享給大家供大家參考,具體如下:
文中代碼出自《機器學習實戰》CH02,可參考本站:
機器學習實戰 (Peter Harrington著) 中文版
機器學習實戰 (Peter Harrington著) 英文原版 [附源代碼]
KNN算法介紹
KNN是一種監督學習算法,通過計算新資料與訓練資料特征值之間的距離,然後選取K(K>=1)個距離最近的鄰居進行分類判(投票法)或者回歸。若K=1,新資料被簡單配置設定給其近鄰的類。
KNN算法實作過程
(1)選擇一種距離計算方式, 通過資料所有的特征計算新資料與已知類别資料集中的資料點的距離;
(2)按照距離遞增次序進行排序,選取與目前距離最小的k個點;
(3)對于離散分類,傳回k個點出現頻率最多的類别作預測分類;對于回歸則傳回k個點的權重值作為預測值;
算法關鍵
(1)資料的所有特征都要做可比較的量化
若是資料特征中存在非數值的類型,必須采取手段将其量化為數值。例如樣本特征中包含顔色,可通過将顔色轉換為灰階值來實作距離計算。
(2)樣本特征要做歸一化處理
樣本有多個參數,每一個參數都有自己的定義域和取值範圍,他們對距離計算的影響不一樣,如取值較大的影響力會蓋過取值較小的參數。是以樣本參數必須做一些scale處理,最簡單的方式就是所有特征的數值都采取歸一化處置。
(3)需要一個距離函數以計算兩個樣本之間的距離
距離的定義:歐氏距離、餘弦距離、漢明距離、曼哈頓距離等,一般選歐氏距離作為距離度量,但是這是隻适用于連續變量。在文本分類這種非連續變量情況下,漢明距離可以用來作為度量。通常情況下,如果運用一些特殊的算法來計算度量的話,K近鄰分類精度可顯著提高,如運用大邊緣最近鄰法或者近鄰成分分析法。
(4)确定K的值
K值選的太大易引起欠拟合,太小容易過拟合。交叉驗證确定K值。
KNN分類
分類算法常采用多數表決決定。一個缺點是出現頻率較多的樣本将會主導測試點的預測結果。解決這個缺點的方法之一是在進行分類時将K個鄰居到測試點的距離考慮進去。若樣本到測試點距離d,則選1/d為該鄰居的權重,統計k個鄰居所有類标簽的權重和,值最大的就是新資料點的預測類标簽。
KNN回歸
KNN回歸是取K個鄰居類标簽值得權重作為新資料點的預測值。
優缺點
(1)KNN算法的優點
- 1.簡單、有效。
- 2.重新訓練的代價較低(類别體系的變化和訓練集的變化,在Web環境和電子商務應用中是很常見的)。
- 3.計算時間和空間線性于訓練集的規模(在一些場合不算太大)。
- 4.由于KNN方法主要靠周圍有限的鄰近的樣本,而不是靠判别類域的方法來确定所屬類别的,是以對于類域的交叉或重疊較多的待分樣本集來說,KNN方法較其他方法更為适合。
- 5.該算法比較适用于樣本容量比較大的類域的自動分類,而那些樣本容量較小的類域采用這種算法比較容易産生誤分。
(2)KNN算法缺點
- 1.KNN算法是懶散學習方法(lazy learning,基本上不學習),一些積極學習的算法要快很多。
- 2.類别評分不是規格化的(不像機率評分)(???)。
- 3.輸出的可解釋性不強,例如決策樹的可解釋性較強。
- 4.該算法在分類時有個主要的不足是,當樣本不平衡時,如一個類的樣本容量很大,而其他類樣本容量很小時,有可能導緻當輸入一個新樣本時,該樣本的K個鄰居中大容量類的樣本占多數。該算法隻計算最近的鄰居樣本,某一類的樣本數量很大,那麼或者這類樣本并不接近目标樣本,或者這類樣本很靠近目标樣本。無論怎樣,數量并不能影響運作結果。可以采用權值的方法(和該樣本距離小的鄰居權值大)來改進。
- 5.計算量較大。目前常用的解決方法是事先對已知樣本點進行剪輯,事先去除對分類作用不大的樣本。
KNN實作
- | import numpy as np
- | import operator
- | import matplotlib
- | import matplotlib.pyplot as plt
- | from os import listdir
- | def Create_DataSet():
- | group = np.array([[1.0, 1.1],[1.0,1.0],[0,0],[0,0.1]])
- | labels = ['A','A','B','B']
- | return group,labels
函數Create_DataSet建立一個資料集,坐标軸左下角分類為B,右上角分類為A。
下面函數classify0,計算向量inX與資料集中各點的距離,計算n_estimators個近鄰中label頻率最高的分類号并傳回作為向量inX的分類号。
- | def classify0(inX, dataSet, labels, n_estimators=3):
- | dataSetSize = dataSet.shape[0]
- | #print 'in classify0,dataSetSize = \n',dataSetSize
- | #轉變向量inx格式為datasize行,1列;并計算與dataset元素距離
- | diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
- | #計算歐氏距離((x0-x1)^2 + (y0-y1)^2 )^(1/2)
- | sqDiffMat = diffMat**2 #diffMat每個元素取平方
- | sqDistances = sqDiffMat.sum(axis=1)
- | distances = sqDistances**0.5
- | #排序,将值從小到大排列,傳回索引
- | sortedDistIndicies = distances.argsort()
- | #print 'in classify0,sortedDistIndicies:\n',sortedDistIndicies
- | #求與距離最近的k個點的label統計
- | classCount={}
- | for i in range(n_estimators):
- | voteIlabel = labels[sortedDistIndicies[i]] #擷取對應label号
- | classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
- | #對字典排序,按value值降序排列
- | sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), revers| e=True)
- | #print 'sortedClassCount[0][0]:\n',sortedClassCount[0][0]
- | return sortedClassCount[0][0]
dataSet.shape()函數用于擷取矩陣dataSet的大小,shape[0]傳回對應行數,shape[1]傳回對應列數。
因為需要對每列屬性做距離運算,是以需要将輸入inX轉換為和dataSet相同行數和列數的矩陣,因為inX列數與dataSet中每個元素列數相同,是以需要将其行數進行擴充,np.tile(inX, (dataSetSize,1))将inX行數拓展為dataSetSize行,1表示縱向複制1次,即列不變。
距離公式采用歐式距離計算,得到的距離值為一維清單,分别對應dataSet中每個元素和inX的距離。distances.argsort() 将距離按從小到大排列,并傳回索引。例如distance = [0.1,0.5,0.3],distance.argsort()傳回[1,3,2] 。傳回索引是為了找到對應的label值,并進行統計。
下面for循環用于建立字典并統計前n_estimators個label的個數。key對應label,key_value對應個數。
operator.itemgetter函數,operator子產品提供的itemgetter函數用于擷取對象的哪些維的資料,參數為一些序号,即需要擷取的資料在對象中的序号;例如a = [1,2,3] ,定義函數b=operator.itemgetter(1),擷取對象的第1個域的值,則 b(a)=2;若定義函數b,擷取對象的第1個域和第0個的值b=operator.itemgetter(1,0),則b(a)=(2, 1) 。注意operator.itemgetter函數擷取的不是值,而是定義了一個函數,通過該函數作用到對象上才能擷取值;
sorted函數:Python内置的排序函數sorted可以對list或者iterator進行排序;
第一個參數iterable指定要排序的list或者iterable,第二個參數指定排序時進行比較的函數,可以指定一個函數或者lambda函數。例如students為類對象的list,每個成員有三個域,用sorted進行比較時可以自己定cmp函數,例如這裡要通過比較第三個資料成員來排序,students = [(‘john', ‘A', 15), (‘jane', ‘B', 12), (‘dave', ‘B', 10)],sorted(students, key=lambda student : student[2]),key為函數,指定取待排序元素的哪一項進行排序,key指定的lambda函數功能是去元素student的第三個域(student[2]),
是以sorted排序時會以students所有元素的第三個域來進行排序;也可以這麼寫sorted(students, key=operator.itemgetter(2)) ,sorted函數也可以進行多級排序,例如要根據第二個域和第三個域進行排序;sorted(students, key=operator.itemgetter(1,2))即先根據第二個域排序,再根據第三個域排序;第三個參數reverse是一個bool變量,表示升序還是降序排列,預設為false升序排列,定義為True時将按降序排列。
此處sort函數用于對字典進行排序。按key_value降序排列,即對應label個數從大到小排列。傳回值為清單,清單元素為元組,元組第一個元素對應label,第二個元素對應label個數。sortedClassCount[0][0]即傳回label次數最多的類标号,為inX的label。
下面測試一個簡單的向量:
group,labels = Create_DataSet()
sortedClassCount = classify0([0,0.5],group,labels,3)
輸出為
sortedClassCount:[(‘B', 2), (‘A', 1)]
sortedClassCount[0][0]:
B
下面函數file2matrix用于從txt中讀取原始資料并轉化為矩陣。
test.txt格式為
40920 8.326976 0.953952 largeDoses
14488 7.153469 1.673904 smallDoses
26052 1.441871 0.805124 didntLike
75136 13.147394 0.428964 didntLike
……
最後一列為label,值為largeDoses、smallDoses或didntLike。每行元素用\t隔開。轉換後label分别對應3、2、1。
轉換函數如下:
- | def file2matrix(filename):
- | fr = open(filename)
- | numberOfLines = len(fr.readlines())
- | print 'in file2matrix,numberOfLines:\n',numberOfLines
- | returnMat = np.zeros((numberOfLines,3))
- | classLabelVector = []
- | fr = open(filename)
- | index = 0
- | for line in fr.readlines(): #周遊每一行
- | line = line.strip() #strip用于删除字元,此處删除空白字元,回車
- | listFromLine = line.split('\t') #擷取每行的元素清單,元素用\t分開
- | returnMat[index,:] = listFromLine[0:3]#取前3個元素,對應屬性集
- | if(listFromLine[-1] == 'largeDoses'):#有什麼有效的方法 将屬性值和類标号分開,互相對| 應
- | classLabelVector.append(3)
- | elif(listFromLine[-1] == 'smallDoses'):
- | classLabelVector.append(2)
- | elif(listFromLine[-1] == 'didntLike'):
- | classLabelVector.append(1)
- | elif(listFromLine[-1] == 3):
- | classLabelVector.append(3)
- | elif(listFromLine[-1] == 2):
- | classLabelVector.append(2)
- | elif(listFromLine[-1] == 1):
- | classLabelVector.append(1)
- | index += 1
- | #print 'returnMat = ',returnMat
- | #print 'classLabelVector = ',classLabelVector
- | return returnMat,classLabelVector #得到屬性集和類标号
首先打開檔案并擷取行數,建立一個相同大小的空矩陣,用于存儲轉換後的屬性集,并建立一個一維清單,用于存放類标号。fr.readlines()讀取所有行,得到一個行清單,清單元素為每行内容;readline隻讀取1行,擷取該行元素的清單。
上述函數即傳回屬性集矩陣和類标号清單。
因為屬性值差距較大,為了減少值太大的屬性對值小的屬性的影響,分類之前還需要進行歸一化。歸一化方程為(datain-min_val) / (max_val - min_val),輸出值都介于0-1。
- | def autoNorm(dataSet):
- | minVals = dataSet.min(0) #擷取每列最大值與最小值,(0)指定列,而不是行
- | print 'in autoNorm,minVals:',minVals
- | maxVals = dataSet.max(0)
- | print 'in autoNorm,maxVals:',maxVals
- | ranges = maxVals - minVals
- | print 'in autoNorm,ranges:',ranges
- | normDataSet = np.zeros(np.shape(dataSet))
- | m = dataSet.shape[0] #擷取行數
- | #特征值矩陣為1000x3,minVals值為1x3,使用tile函數擴充為相同大小的矩陣
- | #np.tile(minVals, (m,1))矩陣minval,橫向複制m次,縱向複制1次
- | normDataSet = dataSet - np.tile(minVals, (m,1)) # (data - minval)/(maxval - minval)
- | normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise divide
- | print 'in autoNorm,normDataSet = ',normDataSet
- | return normDataSet, ranges, minVals
傳回歸一化以後的屬性集。即可進行距離運算并分類。
下面函數即對檔案中所有輸入的行向量屬性進行分類
- | def datingClassTest(n_estimators=3):
- | hoRatio = 0.50
- | #(1)讀取檔案
- | datingDataMat,datingLabels = file2matrix('datingTestSet.txt')
- | #(2)歸一化
- | 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[num| TestVecs:m],n_estimators=n_estimators)
- | if (classifierResult != datingLabels[i]): errorCount += 1.0
- | print "in datingClassTest,the total error rate is: %f" % (errorCount/float(numTestVecs))
- | print 'in datingClassTest,errorCount:',errorCount
将測試檔案分為資料集和用于測試的向量2部分。前一半用于測試,後一半作為資料集,并定義errorCount用于統計出錯個數。經過歸一化以後的資料集和驗證通過for循環計算分類結果,并與實際結果進行對比,得到總出錯數和出錯率。
執行該函數,結果顯示:
in datingClassTest,the total error rate is: 0.064000
in datingClassTest,errorCount: 32.0
由于學習内容實在是太多了,小編就一時間也分享不完,這個是小編整理的人工智能項目視訊和pdf文檔,大家需要的話就可以轉發關注小編,私信小編“學習”來擷取了。