knn演算法c
1. K-means 與KNN 聚類演算法
K-means 演算法屬於聚類演算法的一種。聚類演算法就是把相似的對象通過靜態分類方法分成不同的組別或者更多的子集(subset),這樣讓在同一個子集中的成員對象都有相似的一些屬性。聚類演算法的任務是將數據集劃分為多個集群。在相同集群中的數據彼此會比不同集群的數據相似。通常來說,聚類演算法的目標就是通過相似特徵將數據分組並分配進不同的集群中。
K-means 聚類演算法是一種非監督學習演算法,被用於非標簽數據(data without defined categories or groups)。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。 演算法從 Κ 質心的初始估計開始,其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代:
每個質心定義一個集群。在此步驟中,基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點, ci 屬於質心集合 C ,然後每個數據點 x 基於下面的公式被分配到一個集群中。
在此步驟中,重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下:
K-means 演算法在步驟 1 和步驟 2 之間迭代,直到滿足停止條件(即,沒有數據點改變集群,距離的總和最小化,或者達到一些最大迭代次數)。
上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數,用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常,沒有用於確定 K 的精確值的方法,但是可以使用以下技術獲得准確的估計。
Elbow point 拐點方法
通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離,因此當 K 與數據點的數量相同時,增加 K 將總是減小該度量,達到零的極值。因此,該指標不能用作唯一目標。相反,繪制了作為 K 到質心的平均距離的函數,並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。
DBI(Davies-Bouldin Index)
DBI 是一種評估度量的聚類演算法的指標,通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是:DBI 是聚類內的距離與聚類外的距離的比值。所以,DBI 的數值越小,表示分散程度越低,聚類效果越好。
還存在許多用於驗證 K 的其他技術,包括交叉驗證,信息標准,信息理論跳躍方法,輪廓方法和 G 均值演算法等等。
需要提前確定 K 的選值或者需嘗試很多 K 的取值
數據必須是數字的,可以通過歐氏距離比較
對特殊數據敏感,很容易受特殊數據影響
對初始選擇的質心/中心(centers)敏感
之前介紹了 KNN (K 鄰近)演算法 ,感覺這兩個演算法的名字很接近,下面做一個簡略對比。
K-means :
聚類演算法
用於非監督學習
使用無標簽數據
需要訓練過程
K-NN :
分類演算法
用於監督學習
使用標簽數據
沒有明顯的訓練過程
鄰近演算法,或者說K最近鄰(kNN,k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰,就是k個最近的鄰居的意思,說的是每個樣本都可以用它最接近的k個鄰居來代表。Cover和Hart在1968年提出了最初的鄰近演算法。KNN是一種分類(classification)演算法,它輸入基於實例的學習(instance-based learning),屬於懶惰學習(lazy learning)即KNN沒有顯式的學習過程,也就是說沒有訓練階段,數據集事先已有了分類和特徵值,待收到新樣本後直接進行處理。與急切學習(eager learning)相對應。
KNN是通過測量不同特徵值之間的距離進行分類。
思路是:如果一個樣本在特徵空間中的k個最鄰近的樣本中的大多數屬於某一個類別,則該樣本也劃分為這個類別。KNN演算法中,所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
提到KNN,網上最常見的就是下面這個圖,可以幫助大家理解。
我們要確定綠點屬於哪個顏色(紅色或者藍色),要做的就是選出距離目標點距離最近的k個點,看這k個點的大多數顏色是什麼顏色。當k取3的時候,我們可以看出距離最近的三個,分別是紅色、紅色、藍色,因此得到目標點為紅色。
演算法的描述:
1)計算測試數據與各個訓練數據之間的距離;
2)按照距離的遞增關系進行排序;
3)選取距離最小的K個點;
4)確定前K個點所在類別的出現頻率;
5)返回前K個點中出現頻率最高的類別作為測試數據的預測分類
二、關於 K 的取值
K:臨近數,即在預測目標點時取幾個臨近的點來預測。
K值得選取非常重要,因為:
如果當K的取值過小時,一旦有雜訊得成分存在們將會對預測產生比較大影響,例如取K值為1時,一旦最近的一個點是雜訊,那麼就會出現偏差,K值的減小就意味著整體模型變得復雜,容易發生過擬合;
如果K的值取的過大時,就相當於用較大鄰域中的訓練實例進行預測,學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用,使預測發生錯誤。K值的增大就意味著整體的模型變得簡單;
如果K==N的時候,那麼就是取全部的實例,即為取實例中某分類下最多的點,就對預測沒有什麼實際的意義了;
K的取值盡量要取奇數,以保證在計算結果最後會產生一個較多的類別,如果取偶數可能會產生相等的情況,不利於預測。
K的取法:
常用的方法是從k=1開始,使用檢驗集估計分類器的誤差率。重復該過程,每次K增值1,允許增加一個近鄰。選取產生最小誤差率的K。
一般k的取值不超過20,上限是n的開方,隨著數據集的增大,K的值也要增大。
三、關於距離的選取
距離就是平面上兩個點的直線距離
關於距離的度量方法,常用的有:歐幾里得距離、餘弦值(cos), 相關度 (correlation), 曼哈頓距離 (Manhattan distance)或其他。
Euclidean Distance 定義:
兩個點或元組P1=(x1,y1)和P2=(x2,y2)的歐幾里得距離是
距離公式為:(多個維度的時候是多個維度各自求差)
四、總結
KNN演算法是最簡單有效的分類演算法,簡單且容易實現。當訓練數據集很大時,需要大量的存儲空間,而且需要計算待測樣本和訓練數據集中所有樣本的距離,所以非常耗時
KNN對於隨機分布的數據集分類效果較差,對於類內間距小,類間間距大的數據集分類效果好,而且對於邊界不規則的數據效果好於線性分類器。
KNN對於樣本不均衡的數據效果不好,需要進行改進。改進的方法時對k個近鄰數據賦予權重,比如距離測試樣本越近,權重越大。
KNN很耗時,時間復雜度為O(n),一般適用於樣本數較少的數據集,當數據量大時,可以將數據以樹的形式呈現,能提高速度,常用的有kd-tree和ball-tree。
2. 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一樣,如果結點包含的觀測點到達了預先設定的最小值,這個頂點就可以不再分割了。
3. 簡單數字識別(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)
4. 大數據經典演算法解析(8)一KNN演算法
姓名:崔升 學號:14020120005
【嵌牛導讀】:
本文討論的kNN演算法是監督學習中分類方法的一種。所謂監督學習與非監督學習,是指訓練數據是 否有標注類別,若有則為監督學習,若否則為非監督學習。監督學習是根據輸入數據(訓練數據) 學習一個模型,能對後來的輸入做預測。在監督學習中,輸入變數與輸出變數可以是連續的,也可 以是離散的。若輸入變數與輸出變數均為連續變數,則稱為 回歸 ;輸出變數為有限個離散變數,則 稱為 分類 ;輸入變數與輸出變數均為變數序列,則稱為 標注 [2]。
【嵌牛鼻子】:經典大數據演算法之kNN演算法的簡單介紹
【嵌牛提問】:kNN是一種怎麼的演算法,其數學原理又是如何?
【嵌牛正文】:
1. 引言
頂級數據挖掘會議ICDM於2006年12月評選出了數據挖掘領域的 十大經典演算法 :C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naïve Bayes與 CART。 以前看過關於這些數據挖掘演算法,但對背後數學原理未做過多探究,因而藉此整理以更深入地理解這些演算法。
2. kNN演算法
kNN演算法的核心思想非常簡單:在訓練集中選取離輸入的數據點最近的k個鄰居,根據這個k個鄰居中出現次數最多的類別(最大表決規則),作為該數據點的類別。
演算法描述
訓練集T={(x1,y1),(x2,y2),⋯,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)},其類別yi∈{c1,c2,⋯,cK}yi∈{c1,c2,⋯,cK},訓練集中樣本點數為NN,類別數為KK。輸入待預測數據xx,則預測類別
y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K(1)(1)y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K
其中,涵蓋xx的k鄰域記作Nk(x)Nk(x),當yi=cjyi=cj時指示函數I=1I=1,否則I=0I=0。
分類決策規則
kNN學習模型:輸入XX,通過學習得到決策函數:輸出類別Y=f(X)Y=f(X)。假設分類損失函數為0-1損失函數,即分類正確時損失函數值為0,分類錯誤時則為1。假如給xx預測類別為cjcj,即f(X)=cjf(X)=cj;同時由式子 (1) (1)可知k鄰域的樣本點對學習模型的貢獻度是均等的,則kNN學習模型誤分類率為
1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)
若要最小化誤分類率,則應
maxcj∑xi∈Nk(x)I(yi=cj)maxcj∑xi∈Nk(x)I(yi=cj)
所以,最大表決規則等價於經驗風險最小化。
存在問題
k值得選取對kNN學習模型有著很大的影響。若k值過小,預測結果會對噪音樣本點顯得異常敏感。特別地,當k等於1時,kNN退化成最近鄰演算法,沒有了顯式的學習過程。若k值過大,會有較大的鄰域訓練樣本進行預測,可以減小噪音樣本點的減少;但是距離較遠的訓練樣本點對預測結果會有貢獻,以至於造成預測結果錯誤。下圖給出k值的選取對於預測結果的影響:
前面提到過,k鄰域的樣本點對預測結果的貢獻度是相等的;但距離更近的樣本點應有更大的相似度,其貢獻度應比距離更遠的樣本點大。可以加上權值wi=1/∥xi−x∥wi=1/‖xi−x‖進行修正,則最大表決原則變成:
maxcj∑xi∈Nk(x)wi∗I(yi=cj)maxcj∑xi∈Nk(x)wi∗I(yi=cj)
3. 參考資料
[1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.
[2] 李航,《統計學習方法》.
5. R語言-KNN演算法
1、K最近鄰(k-NearestNeighbor,KNN)分類演算法,是一個理論上比較成熟的方法,也是最簡單的機器學習演算法之一。該方法的思路是:如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別。
2、KNN演算法中,所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理,但在類別決策時,只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本,而不是靠判別類域的方法來確定所屬類別的,因此對於類域的交叉或重疊較多的待分樣本集來說,KNN方法較其他方法更為適合。
3、KNN演算法不僅可以用於分類,還可以用於回歸。通過找出一個樣本的k個最近鄰居,將這些鄰居的屬性的平均值賦給該樣本,就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight),如權值與距離成正比。
簡言之,就是將未標記的案例歸類為與它們最近相似的、帶有標記的案例所在的類 。
原理及舉例
工作原理:我們知道樣本集中每一個數據與所屬分類的對應關系,輸入沒有標簽的新數據後,將新數據與訓練集的數據對應特徵進行比較,找出「距離」最近的k(通常k<20)數據,選擇這k個數據中出現最多的分類作為新數據的分類。
演算法描述
1、計算已知數據集中的點與當前點的距離
2、按距離遞增次序排序
3、選取與當前數據點距離最近的K個點
4、確定前K個點所在類別出現的頻率
5、返回頻率最高的類別作為當前類別的預測
距離計算方法有"euclidean"(歐氏距離),」minkowski」(明科夫斯基距離), "maximum"(切比雪夫距離), "manhattan"(絕對值距離),"canberra"(蘭式距離), 或 "minkowski"(馬氏距離)等
Usage
knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)
Arguments
train
matrix or data frame of training set cases.
test
matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.
cl
factor of true classifications of training set
k
number of neighbours considered.
l
minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even
ifkis increased by ties.)
prob
If this is true, the proportion of the votes for the
winning class are returned as attributeprob.
use.all
controls handling of ties. If true, all distances equal
to thekth largest are
included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.
kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))
參數:
formula A formula object.
train Matrix or data frame of training set cases.
test Matrix or data frame of test set cases.
na.action A function which indicates what should happen when the data contain 』NA』s.
k Number of neighbors considered.
distance Parameter of Minkowski distance.
kernel Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".
ykernel Window width of an y-kernel, especially for prediction of ordinal classes.
scale Logical, scale variable to have equal sd.
contrasts A vector containing the 』unordered』 and 』ordered』 contrasts to use
kknn的返回值如下:
fitted.values Vector of predictions.
CL Matrix of classes of the k nearest neighbors.
W Matrix of weights of the k nearest neighbors.
D Matrix of distances of the k nearest neighbors.
C Matrix of indices of the k nearest neighbors.
prob Matrix of predicted class probabilities.
response Type of response variable, one of continuous, nominal or ordinal.
distance Parameter of Minkowski distance.
call The matched call.
terms The 』terms』 object used.
iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)
library(kknn)
data(iris)
dim(iris)
m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3),replace=FALSE,prob=rep(1/m,m))
建立訓練數據集
data.train<-iris[-val,]
建立測試數據集
data.test<-iris[val,]
調用kknn 之前首先定義公式
formula : Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width
iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")
summary(iris.kknn)
# 獲取fitted.values
fit <- fitted(iris.kknn)
# 建立表格檢驗判類准確性
table(iris.valid$Species, fit)
# 繪畫散點圖,k-nearest neighbor用紅色高亮顯示
pcol <- as.character(as.numeric(iris.valid$Species))
pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]
二、R語言knn演算法
install.packages("class")
library(class)
對於新的測試樣例基於距離相似度的法則,確定其K個最近的鄰居,在K個鄰居中少數服從多數
確定新測試樣例的類別
1、獲得數據
2、理解數據
對數據進行探索性分析,散點圖
如上例
3、確定問題類型,分類數據分析
4、機器學習演算法knn
5、數據處理,歸一化數據處理
normalize <- function(x){
num <- x - min(x)
denom <- max(x) - min(x)
return(num/denom)
}
iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))
summary(iris_norm)
6、訓練集與測試集選取
一般按照3:1的比例選取
方法一、set.seed(1234)
ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))
iris_train <-iris[ind==1, 1:4]
iris_test <-iris[ind==2, 1:4]
train_label <-iris[ind==1, 5]
test_label <-iris[ind==2, 5]
方法二、
ind<-sample(1:150,50)
iris_train<-iris[-ind,]
iris_test<-iris[ind,1:4]
iris_train<-iris[-ind,1:4]
train_label<-iris[-ind,5]
test_label<-iris[ind,5]
7、構建KNN模型
iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)
8、模型評價
交叉列聯表法
table(test_label,iris_pred)
實例二
數據集
http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data
導入數據
dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)
names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')
table(wdbc.data$Diagnosis)## M = malignant, B = benign
wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))
6. KNN計算復雜度是多少,有好的說明資料或者參考文獻嗎
解決方案1:M,且與類域邊界的沿垂直於該超平面方向的距離最大,其歸於cj類的類條件概率是P(X/;T2,具有相對優良的性能指標(1)決策樹
決
策樹歸納是經典的分類演算法,…。另外,M,類別總體的概率分布和各類樣本的概率分布函數(或密度函數)常常是不知道的,由此構造出的分類器可以最大化類與
類的間隔,Bayes分類方法在理論上論證得比較充分,因此該方法往往在效果上難以達到理論上的最大值,記為C={c1;
ci)P(ci)=Maxj[P(x/,這樣的條件在實際文本中一般很難滿足,而那些樣本容量較小的類域採用這種演算法比較容易產生誤分:
若
P(x/,因為對每一個待分類的文本都要計算它到全體已知樣本的距離。因此:D=D(T1,因此對於類域的交叉或重疊較多的待分樣本集來說,由
Salton等人於60年代末提出,待分樣本的分類結果取決於各類域中樣本的全體;…,VSM法相對其他分類方法而言;P(x)(1)
若
P(ci/,…,其包含的每個特徵項對於類別的表達能力越弱,Bayes法要求表達文本的主題詞相互獨立,採用這種方法可以較好地避免樣本的不平衡問題:
如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別。為了獲得它們,只與極少量的相鄰樣本有關,則有
x∈ci(2)
式(2)是最大後驗概率判決准則,ci,…,只需要計算待分樣本和每一個類別向量的相似度即內積。該方法的思路非常簡單直觀。當需要對一篇待分樣本進行分類的時候,2,是一個理論上比較成熟的方法。
設訓練樣本集分為M類;x)=P(x/。
KNN方法雖然從原理上也依賴於極限定理,故SVM法亦被稱為最大邊緣(maximum margin)演算法,移去或者減少這些樣本對分類結果沒有影響,事先去除對分類作用不大的樣本,則該樣本也屬於這個類別。當文本被表示為空間向量模型的時候,則x∈ci
這就是常用到的Bayes分類判決准則,Wn)。另外,就要求樣本足夠大。可以從生成的決策樹中提取規則。
Bayes
方法的薄弱環節在於實際情況下,但在類別決策時;X)=MaxjP(cj/,2,可得到cj類的後驗概率P(ci/,i=1,而不是靠判別類域的方法來確
定所屬類別的,由於KNN方法主要靠周圍有限的鄰近的樣本。當樣本集非常大時,由Vapnik等人於1995年提出;ci),i=1,能降低KNN演算法的
計算復雜度。因此,i=1,…,SVM可以自動尋找出那些對分類有較好區分能力的支持向量,則有,…,提高分類的效率,在應用上也是非常廣泛的;總樣本
數,KNN方法較其他方法更為適合。待分樣本集中的大部分樣本不是支持向量。目前常用的解決方法是事先對已知樣本點進行剪輯。該方法在定類決策上只依據最
鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。根據研究發現。經過長期的研究。
該演算法比較適用於樣本容量比較大的類域的自動分類。該方
法只需要由各類域的邊界樣本的類別來決定最後的分類結果。通過學習演算法。它採用自頂向下遞歸的各個擊破方式構造決策樹,而該空間向量的建立又很大程度的依
賴於該類別向量中所包含的特徵項,文本的相似度就可以藉助特徵向量之間的內積來表示。
(4) VSM法
VSM法即向量空間模型(Vector Space Model)法。這是最早也是最出名的信息檢索方面的數學模型。
由於VSM法中需要事先計算類別的空間向量,SVM法對小樣本情況下的自動分類有著較好的分類結果。
(3) SVM法
SVM法即支持向量機(Support Vector Machine)法。
在實際應用中,j=1,M,j=1。另外還有一種Reverse KNN法;Tn;ci)·P(ci)/,因而有較好的適應能力和較高的分准率,W1:
P(ci/,M,然後選取相似度最大的類別作為該待分樣本所對應的類別,VSM法一般事先依據語料庫中的訓練樣本和分類體系建立類別向量空間,則根據Bayes定理。
該方法的不足之處是計算量較大,類別中所包含的非零特徵項越多,最初由Cover和Hart於1968年提出的。樹的每一個結點上使用信息增益度量選擇測試屬性;X)。
支
持向量機演算法的目的在於尋找一個超平面H(d),…cM},2,將式(1)代入式(2)。對於一個待分樣本X,然後通過計算文本相似度的方法來確定待分樣
本的類別,2,2,該超平面可以將訓練集中的數據分開。該方法是建立在統計學習理論基礎上的機器學習方法,每類的先驗概率為P(ci),W2,…。
(5) Bayes法
Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法;cj)P(cj)],更適合於專業文獻的分類,才能求得它的K個最近鄰點。
(2) KNN法(K-Nearest Neighbor)
KNN法即K最近鄰法,M;X),可以認為P(ci)=ci類樣本數/。其基本思想是將文檔表示為加權的特徵向量
7. KNN演算法,k近鄰
K最近鄰(k-Nearest Neighbour,KNN)分類演算法,是一個理論上比較成熟的方法,也是最簡單的機器學習演算法之一。該方法的思路是:如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別。