『壹』 簡單數字識別(knn演算法)
knn演算法,即k-NearestNeighbor,後面的nn意思是最近鄰的意思,前面的k是前k個的意思,就是找到前k個離得最近的元素
離得最近這個詞具體實現有很多種,我使用的是歐式幾何中的距離公式
二維中兩點x(x1,y1),y(x2,y2)間距離公式為sqrt( (x1-x2)^2+(y1-y2)^2 )
推廣到n維就是
x(x1,x2, … ,xn),y(y1,y2, … ,yn)
sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)
knn演算法是要計算距離的,也就是數字之間的運算,而圖像是png,jpg這種格式,並不是數字也不能直接參與運算,所以我們需要進行一下轉換
如圖所示一個數字8,首先要確定的是這一步我做的是一個最簡單的轉換,因為我假定背景和圖之間是沒有雜物的,而且整個圖只有一個數字(0-9)如果遇到其他情況,比如背景色不純或者有其他干擾圖像需要重新設計轉換函數
接下來就是最簡單的轉換,將圖片白色部分(背景)變0,有圖像的部分變1。轉換後的大小要合適,太小會影響識別准確度,太大會增加計算量。所以我用的是書上的32*32,轉換後結果如圖所示
這樣一來,圖片就變成了能進行計算的數字了。
接下來我們需要創建一個庫,這個庫裡面存著0-9這些數字的各種類似上圖的實例。因為我們待識別的圖像要進行對比,選出前k個最近的,比較的對象就是我們的庫。假定庫中有0-9十個數字,每個數字各有100個這種由0和1表示的實例,那麼我們就有了一共1000個實例。
最後一步就是進行對比,利用開頭說的歐式幾何距離計算公式,首先這個32*32的方陣要轉換成一個1*1024的1024維坐標表示,然後拿這個待識別的圖像和庫中的1000個實例進行距離計算,選出前k個距離最近的。比如50個,這50個裡面出現次數最多的數字除以50就是結果數字的概率。比如50個裡面數字8出現40次,那麼待識別數字是8的可能性就是40/50 = 80%
個人理解:
只能識別單個數字,背景不能有干擾。如果想多數字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉01的方法。
數字識別非常依賴庫中的圖像,庫中的圖像的樣子嚴重影響圖像的識別(因為我們是和庫中的一一對比找出距離最近的前k個),所以數字的粗細,高低,胖瘦等待都是決定性因素,建庫時一定全面考慮數字的可能樣子
計算量比較大,待識別圖像要和庫中所有實例一一計算,如果使用32*32,就已經是1024維了。如果庫中有1000個,那就是1024維向量之間的1000次計算,圖像更清晰,庫更豐富只會使計算量更大
對於其他可以直接計算距離的數值型問題,可以用歐式距離,也可以用其他能代表距離的計算公式,對於非數值型的問題需要進行合適的轉換,轉換方式很重要,我覺得首先信息不能丟失,其次要精確不能模糊,要實現圖片轉換前後是一對一的關系
參考資料:機器學習實戰 [美] Peter Harrington 人民郵電出版社
python源碼
import numpy
import os
from PIL import Image
import heapq
from collections import Counter
def pictureconvert(filename1,filename2,size=(32,32)):
#filename1待識別圖像,filename2 待識別圖像轉換為01txt文件輸出,size圖像大小,默認32*32
image_file = Image.open(filename1)
image_file = image_file.resize(size)
width,height = image_file.size
f1 = open(filename1,'r')
f2 = open(filename2,'w')
for i in range(height):
for j in range(width):
pixel = image_file.getpixel((j,i))
pixel = pixel[0] + pixel[1] + pixel[2]
if(pixel == 0):
pixel = 0
elif(pixel != 765 and pixel != 0):
pixel = 1
# 0代表黑色(無圖像),255代表白色(有圖像)
# 0/255 = 0,255/255 = 1
f2.write(str(pixel))
if(j == width-1):
f2.write('\n')
f1.close()
f2.close()
def imgvector(filename):
#filename將待識別圖像的01txt文件轉換為向量
vector = numpy.zeros((1,1024),numpy.int)
with open(filename) as f:
for i in range(0,32):
linestr = f.readline()
for j in range(0,32):
vector[0,32*i+j] = int(linestr[j])
return vector
def compare(filename1,filename2):
#compare直接讀取資源庫識別
#filename1資源庫目錄,filename2 待識別圖像01txt文檔路徑
trainingfilelist = os.listdir(filename1)
m = len(trainingfilelist)
labelvector = []
trainingmatrix = numpy.zeros((m, 1024), numpy.int8)
for i in range(0,m):
filenamestr = trainingfilelist[i]
filestr = filenamestr.split('.')[0]
classnumber = int(filestr.split('_')[0])
labelvector.append(classnumber)
trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)
textvector = imgvector(filename2)
resultdistance = numpy.zeros((1,m))
result = []
for i in range(0,m):
resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])
resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)
for i in resultindices:
result.append(labelvector[i])
number = Counter(result).most_common(1)
print('此數字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))
def distinguish(filename1,filename2,filename3,size=(32,32)):
# filename1 png,jpg等格式原始圖像路徑,filename2 原始圖像轉換成01txt文件路徑,filename3 資源庫路徑
pictureconvert(filename1,filename2,size)
compare(filename3,filename2)
url1 = "/Users/wang/Desktop/number.png"
url2 = "/Users/wang/Desktop/number.txt"
traininglibrary = "/Users/wang/Documents/trainingDigits"
distinguish(url1,url2,traininglibrary)
『貳』 K-近鄰演算法(K-NN)
給定一個訓練數據集,對於新的輸入實例, 根據這個實例最近的 k 個實例所屬的類別來決定其屬於哪一類 。所以相對於其它機器學習模型和演算法,k 近鄰總體上而言是一種非常簡單的方法。
找到與該實例最近鄰的實例,這里就涉及到如何找到,即在特徵向量空間中,我們要採取 何種方式來對距離進行度量 。
距離的度量用在 k 近鄰中我們也可以稱之為 相似性度量 ,即特徵空間中兩個實例點相似程度的反映。在機器學習中,常用的距離度量方式包括歐式距離、曼哈頓距離、餘弦距離以及切比雪夫距離等。 在 k 近鄰演算法中常用的距離度量方式是歐式距離,也即 L2 距離, L2 距離計算公式如下:
一般而言,k 值的大小對分類結果有著重大的影響。 當選擇的 k 值較小的情況下,就相當於用較小的鄰域中的訓練實例進行預測,只有當與輸入實例較近的訓練實例才會對預測結果起作用。但與此同時預測結果會對實例點非常敏感,分類器抗噪能力較差,因而容易產生過擬合 ,所以一般而言,k 值的選擇不宜過小。但如果選擇較大的 k 值,就相當於在用較大鄰域中的悶鄭握訓練實例進行預測,但相應的分類誤差也會增大,模型整體變得簡單,會產生一定程度的欠擬合。所以一般而言,我們需要 採用交叉驗證的方式來選擇合適的 k 值 。
k 個實例的多數屬於哪叢褲個類,明顯是多數表決的歸類規則。當然還可能使用其他規則,所以第三個關鍵就是 分類決策規則。
回歸:k個實例該屬性值的平均值
它是一個二叉樹的數據結構,方便存儲 K 維空間的數據
KNN 的計算過程是大量計算樣本點之間的距離。為了減少計算距離次數,提升 KNN 的搜索效率,人們提出了 KD 樹(K-Dimensional 的縮寫)。KD 樹是對數據點在 K 維空間中劃分的一種數據結構。在 KD 樹的構造中,每個節點都是 k 維數值點的二叉樹。螞慶既然是二叉樹,就可以採用二叉樹的增刪改查操作,這樣就大大提升了搜索效率。
如果是做分類,你需要引用:from sklearn.neihbors import KNeighborsClassifier
如果是回歸, 需要引用:from sklearn.neighbors import KNeighborsRegressor
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)
『叄』 KNN演算法常見問題總結
給定測試實例,基於某種距離度量找出訓練集中與其最靠近的k個實例點,然後基於這k個最近鄰的信息來進行預測。
通常,在分類任務中可使用「投票法」,即選擇這k個實例中出現最多的標記類別作為預測結果;在回歸任務中可使用「平均法」,即將這k個實例的實值輸出標記的平均值作為預測結果;還可基於距離遠近進行加權平均或加權投票,距離越近的實例權重越大。
k近鄰法不具有顯式的學習過程,事實上,它是懶惰學習(lazy learning)的著名代表,此類學習技術在訓練階段僅僅是把樣本保存起來,訓練時間開銷為零,待收到測試樣本後再進行處理。
KNN一般採用歐氏距離,也可採用其他距離度量,一般的Lp距離:
KNN中的K值選取對K近鄰演算法的結果會產生重大影響。如果選擇較小的K值,就相當於用較小的領域中的訓練實例進行預測,「學習」近似誤差(近似誤差:可以理解為對現有訓練集的訓練誤差)會減小,只有與輸入實例較近或相似的訓練實例才會對預測結果起作用,與此同時帶來的問題是「學習」的估計誤差會增大,換句話說,K值的減小就意味著整體模型變得復雜,容易發生過擬合;
如果選擇較大的K值,就相當於用較大領域中的訓練實例進行預測,其優點是可以減少學習的估計誤差,但缺點是學習的近似誤差會增大。這時候,與輸入實例較遠(不相似的)訓練實例也會對預測器作用,使預測發生錯誤,且K值的增大就意味著整體的模型變得簡單。
在實際應用中,K值一般取一個比較小的數值,例如採用交叉驗證法來選擇最優的K值。經驗規則:k一般低於訓練樣本數的平方根
1、計算測試對象到訓練集中每個對象的距離
2、按照距離的遠近排序
3、選取與當前測試對象最近的k的訓練對象,作為該測試對象的鄰居
4、統計這k個鄰居的類別頻率
5、k個鄰居里頻率最高的類別,即為測試對象的類別
輸入X可以採用BallTree或KDTree兩種數據結構,優化計算效率,可以在實例化KNeighborsClassifier的時候指定。
KDTree
基本思想是,若A點距離B點非常遠,B點距離C點非常近, 可知A點與C點很遙遠,不需要明確計算它們的距離。 通過這樣的方式,近鄰搜索的計算成本可以降低為O[DNlog(N)]或更低。 這是對於暴力搜索在大樣本數N中表現的顯著改善。KD 樹的構造非常快,對於低維度 (D<20) 近鄰搜索也非常快, 當D增長到很大時,效率變低: 這就是所謂的 「維度災難」 的一種體現。
KD 樹是一個二叉樹結構,它沿著數據軸遞歸地劃分參數空間,將其劃分為嵌入數據點的嵌套的各向異性區域。 KD 樹的構造非常快:因為只需沿數據軸執行分區, 無需計算D-dimensional 距離。 一旦構建完成, 查詢點的最近鄰距離計算復雜度僅為O[log(N)]。 雖然 KD 樹的方法對於低維度 (D<20) 近鄰搜索非常快, 當D增長到很大時, 效率變低。
KD樹的特性適合使用歐氏距離。
BallTree
BallTree解決了KDTree在高維上效率低下的問題,這種方法構建的樹要比 KD 樹消耗更多的時間,但是這種數據結構對於高結構化的數據是非常有效的, 即使在高維度上也是一樣。
KD樹是依次對K維坐標軸,以中值切分構造的樹;ball tree 是以質心C和半徑r分割樣本空間,每一個節點是一個超球體。換句簡單的話來說,對於目標空間(q, r),所有被該超球體截斷的子超球體內的所有子空間都將被遍歷搜索。
BallTree通過使用三角不等式減少近鄰搜索的候選點數:|x+y|<=|x|+|y|通過這種設置, 測試點和質心之間的單一距離計算足以確定距節點內所有點的距離的下限和上限. 由於 ball 樹節點的球形幾何, 它在高維度上的性能超出 KD-tree, 盡管實際的性能高度依賴於訓練數據的結構。
BallTree適用於更一般的距離。
1、優點
非常簡單的分類演算法沒有之一,人性化,易於理解,易於實現
適合處理多分類問題,比如推薦用戶
可用於數值型數據和離散型數據,既可以用來做分類也可以用來做回歸
對異常值不敏感
2、缺點
屬於懶惰演算法,時間復雜度較高,因為需要計算未知樣本到所有已知樣本的距離
樣本平衡度依賴高,當出現極端情況樣本不平衡時,分類絕對會出現偏差,可以調整樣本權值改善
可解釋性差,無法給出類似決策樹那樣的規則
向量的維度越高,歐式距離的區分能力就越弱
樣本空間太大不適合,因為計算量太大,預測緩慢
文本分類
用戶推薦
回歸問題
1)所有的觀測實例中隨機抽取出k個觀測點,作為聚類中心點,然後遍歷其餘的觀測點找到距離各自最近的聚類中心點,將其加入到該聚類中。這樣,我們就有了一個初始的聚類結果,這是一次迭代的過程。
2)我們每個聚類中心都至少有一個觀測實例,這樣,我們可以求出每個聚類的中心點(means),作為新的聚類中心,然後再遍歷所有的觀測點,找到距離其最近的中心點,加入到該聚類中。然後繼續運行2)。
3)如此往復2),直到前後兩次迭代得到的聚類中心點一模一樣。
本演算法的時間復雜度:O(tkmn),其中,t為迭代次數,k為簇的數目,m為記錄數,n為維數;
空間復雜度:O((m+k)n),其中,k為簇的數目,m為記錄數,n為維數。
適用范圍:
K-menas演算法試圖找到使平凡誤差准則函數最小的簇。當潛在的簇形狀是凸面的,簇與簇之間區別較明顯,且簇大小相近時,其聚類結果較理想。前面提到,該演算法時間復雜度為O(tkmn),與樣本數量線性相關,所以,對於處理大數據集合,該演算法非常高效,且伸縮性較好。但該演算法除了要事先確定簇數K和對初始聚類中心敏感外,經常以局部最優結束,同時對「雜訊」和孤立點敏感,並且該方法不適於發現非凸面形狀的簇或大小差別很大的簇。
1)首先,演算法只能找到局部最優的聚類,而不是全局最優的聚類。而且演算法的結果非常依賴於初始隨機選擇的聚類中心的位置。我們通過多次運行演算法,使用不同的隨機生成的聚類中心點運行演算法,然後對各自結果C通過evaluate(C)函數進行評估,選擇多次結果中evaluate(C)值最小的那一個。k-means++演算法選擇初始seeds的基本思想就是:初始的聚類中心之間的相互距離要盡可能的遠
2)關於初始k值選擇的問題。首先的想法是,從一個起始值開始,到一個最大值,每一個值運行k-means演算法聚類,通過一個評價函數計算出最好的一次聚類結果,這個k就是最優的k。我們首先想到了上面用到的evaluate(C)。然而,k越大,聚類中心越多,顯然每個觀測點距離其中心的距離的平方和會越小,這在實踐中也得到了驗證。第四節中的實驗結果分析中將詳細討論這個問題。
3)關於性能問題。原始的演算法,每一次迭代都要計算每一個觀測點與所有聚類中心的距離。有沒有方法能夠提高效率呢?是有的,可以使用k-d tree或者ball tree這種數據結構來提高演算法的效率。特定條件下,對於一定區域內的觀測點,無需遍歷每一個觀測點,就可以把這個區域內所有的點放到距離最近的一個聚類中去。這將在第三節中詳細地介紹。
相似點:都包含這樣的過程,給定一個點,在數據集中找離它最近的點。即二者都用到了NN(Nears Neighbor)演算法,一般用KD樹來實現NN。
k-d tree 與 ball tree
1)k-d tree[5]
把n維特徵的觀測實例放到n維空間中,k-d tree每次通過某種演算法選擇一個特徵(坐標軸),以它的某一個值作為分界做超平面,把當前所有觀測點分為兩部分,然後對每一個部分使用同樣的方法,直到達到某個條件為止。
上面的表述中,有幾個地方下面將會詳細說明:(1)選擇特徵(坐標軸)的方法 (2)以該特徵的哪一個為界 (3)達到什麼條件演算法結束。
(1)選擇特徵的方法
計算當前觀測點集合中每個特徵的方差,選擇方差最大的一個特徵,然後畫一個垂直於這個特徵的超平面將所有觀測點分為兩個集合。
(2)以該特徵的哪一個值為界 即垂直選擇坐標軸的超平面的具體位置。
第一種是以各個點的方差的中值(median)為界。這樣會使建好的樹非常地平衡,會均勻地分開一個集合。這樣做的問題是,如果點的分布非常不好地偏斜的,選擇中值會造成連續相同方向的分割,形成細長的超矩形(hyperrectangles)。
替代的方法是計算這些點該坐標軸的平均值,選擇距離這個平均值最近的點作為超平面與這個坐標軸的交點。這樣這個樹不會完美地平衡,但區域會傾向於正方地被劃分,連續的分割更有可能在不同方向上發生。
(3)達到什麼條件演算法結束
實際中,不用指導葉子結點只包含兩個點時才結束演算法。你可以設定一個預先設定的最小值,當這個最小值達到時結束演算法。
圖6中,星號標注的是目標點,我們在k-d tree中找到這個點所處的區域後,依次計算此區域包含的點的距離,找出最近的一個點(黑色點),如果在其他region中還包含更近的點則一定在以這兩個點為半徑的圓中。假設這個圓如圖中所示包含其他區域。先看這個區域兄弟結點對應區域,與圓不重疊;再看其雙親結點的兄弟結點對應區域。從它的子結點對應區域中尋找(圖中確實與這個雙親結點的兄弟結點的子結點對應區域重疊了)。在其中找是否有更近的結點。
k-d tree的優勢是可以遞增更新。新的觀測點可以不斷地加入進來。找到新觀測點應該在的區域,如果它是空的,就把它添加進去,否則,沿著最長的邊分割這個區域來保持接近正方形的性質。這樣會破壞樹的平衡性,同時讓區域不利於找最近鄰。我們可以當樹的深度到達一定值時重建這棵樹。
然而,k-d tree也有問題。矩形並不是用到這里最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外,矩形甚至是正方形並不是用在這里最完美的形狀,由於它的角。如果圖6中的圓再大一些,即黑點距離目標點點再遠一些,圓就會與左上角的矩形相交,需要多檢查一個區域的點,而且那個區域是當前區域雙親結點的兄弟結點的子結點。
為了解決上面的問題,我們引入了ball tree。
2)ball tree[4]
解決上面問題的方案就是使用超球面而不是超矩形劃分區域。使用球面可能會造成球面間的重疊,但卻沒有關系。ball tree就是一個k維超球面來覆蓋這些觀測點,把它們放到樹裡面。圖7(a)顯示了一個2維平麵包含16個觀測實例的圖,圖7(b)是其對應的ball tree,其中結點中的數字表示包含的觀測點數。
不同層次的圓被用不同的風格畫出。樹中的每個結點對應一個圓,結點的數字表示該區域保含的觀測點數,但不一定就是圖中該區域囊括的點數,因為有重疊的情況,並且一個觀測點只能屬於一個區域。實際的ball tree的結點保存圓心和半徑。葉子結點保存它包含的觀測點。
使用ball tree時,先自上而下找到包含target的葉子結點,從此結點中找到離它最近的觀測點。這個距離就是最近鄰的距離的上界。檢查它的兄弟結點中是否包含比這個上界更小的觀測點。方法是:如果目標點距離兄弟結點的圓心的距離大於這個圓的圓心加上前面的上界的值,則這個兄弟結點不可能包含所要的觀測點。(如圖8)否則,檢查這個兄弟結點是否包含符合條件的觀測點。
那麼,ball tree的分割演算法是什麼呢?
選擇一個距離當前圓心最遠的觀測點i1,和距離i1最遠的觀測點 i2,將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心,然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑。對包含n個觀測點的超圓進行分割,只需要線性的時間。
與k-d tree一樣,如果結點包含的觀測點到達了預先設定的最小值,這個頂點就可以不再分割了。
『肆』 knn演算法優缺點
KNN演算法的優缺點如下:
優點:
1. 簡單直觀:KNN演算法是一種基於實例的學習演算法,它不需要建立復雜的數學模型,而是直接利用訓練數據集進行預測。這種方法的邏輯非常直觀,易於理解和實現。
2. 無需參數估計:KNN演算法在訓練階段基本上不需要進行參數估計和模型訓練,這避免了因參數設置不當而導致的模型性能下降。它主要依賴於數據集本身,使得演算法更加靈活。
3. 適用於多分類問題:KNN演算法可以很方便地擴展到多分類問題中,只需在預測時考慮K個最近鄰的類別即可。
4. 對異常值不敏感:由於KNN演算法是基於局部信息進行預測的,因此它對數據集中的異常值相對不敏感。這意味著即使數據集中存在少量雜訊或異常點,演算法的性能也不會受到太大影響。
缺點:
1. 計算量大:KNN演算法在預測階段需要計算待預測樣本與所有訓練樣本之間的距離,這導致在大數據集上運行時計算成本非常高。隨著數據量的增加,演算法的效率會顯著下降。
2. K值選擇困難:KNN演算法中的K值是一個關鍵參數,它直接影響到演算法的預測性能。然而,選擇合適的K值並不容易,通常需要通過交叉驗證等方法來確定。此外,不同的K值可能導致完全不同的預測結果,使得演算法的穩定性受到質疑。
3. 樣本不平衡問題:當訓練數據集中各類別的樣本數量不平衡時,KNN演算法的預測性能可能會受到影響。因為演算法是基於最近鄰的類別進行預測的,如果某一類別的樣本數量過多,那麼待預測樣本的最近鄰很可能都屬於這個類別,從而導致預測偏差。
4. 維度災難:在高維空間中,距離的計算可能變得不再有意義,因為隨著維度的增加,數據點之間的距離差異可能會變得越來越大。這會導致KNN演算法在高維數據上的性能下降,即所謂的“維度災難”。
綜上所述,KNN演算法具有簡單直觀、無需參數估計等優點,但同時也面臨著計算量大、K值選擇困難等挑戰。在實際應用中,我們需要根據具體的數據集和問題特點來選擇是否使用KNN演算法,並針對性地調整其參數以優化性能。