鄰近分割演算法

❶ 圖像分割演算法總結

       圖像處理的很多任務都離不開圖像分割。因為圖像分割在cv中實在太重要(有用)了，就先把圖像分割的常用演算法做個總結。

        接觸機器學習和深度學習時間已經不短了。期間看過各種相關知識但從未總結過。本文過後我會盡可能詳細的從工程角度來總結，從傳統機器學習演算法，傳統計算機視覺庫演算法到深度學習目前常用演算法和論文，以及模型在各平台的轉化，量化，服務化部署等相關知識總結。

        圖像分割常用演算法大致分為下面幾類。由於圖像的能量范函，邊緣追蹤等方法的效果往往只能解決特定問題，效果並不理想，這里不再闡述。當然二值化本身也可以分割一些簡單圖像的。但是二值化演算法較多，我會專門做一個文章來總結。這里不再贅述。

        1.基於邊緣的圖像分割演算法：

            有利用圖像梯度的傳統演算法運算元的sobel，roberts，prewitt,拉普拉斯以及canny等。

            這些演算法的基本思想都是採用合適的卷積運算元，對圖像做卷積。從而求出圖像對應的梯度圖像。(至於為什麼通過如圖1這樣的運算元卷積，即可得到圖像的梯度圖像，請讀者復習下卷積和倒數的概念自行推導)由於圖像的邊緣處往往是圖像像素差異較大，梯度較大地方。因此我們通過合適的卷積核得到圖像的梯度圖像，即得到了圖像的邊緣圖像。至於二階運算元的推導，與一階類似。優點：傳統運算元梯度檢測，只需要用合適的卷積核做卷積，即可快速得出對應的邊緣圖像。缺點：圖像邊緣不一定準確，復雜圖像的梯度不僅僅出現在圖像邊緣，可以能出現在圖像內部的色彩和紋理上。

             也有基於深度學習方法hed，rcf等。由於這類網路都有同一個比較嚴重的缺陷，這里只舉例hed網路。hed是基於FCN和VGG改進，同時引出6個loss進行優化訓練，通過多個層輸出不同scale的粒度的邊緣，然後通過一個訓練權重融合各個層的邊緣結果。hed網路結構如下：

可以得到一個比較完整的梯度圖像，可參考github的hed實現。優點：圖像的梯度細節和邊緣完整性，相比傳統的邊緣運算元要好很多。但是hed對於邊緣的圖像內部的邊緣並不能很好的區分。當然我們可以自行更改loss來嘗試只擬合外部的圖像邊緣。但最致命的問題在於，基於vgg的hed的網路表達能力有限，對於圖像和背景接近，或者圖像和背景部分相融的圖片，hed似乎就有點無能為力了。

        2.基於區域分割的演算法：

            區域分割比較常用的如傳統的演算法結合遺傳演算法，區域生長演算法，區域分裂合並，分水嶺演算法等。這里傳統演算法的思路是比較簡單易懂的，如果有無法理解的地方，歡迎大家一起討論學習。這里不再做過多的分析。

            基於區域和語意的深度學習分割演算法，是目前圖像分割成果較多和研究的主要方向。例如FCN系列的全卷積網路，以及經典的醫學圖像分割常用的unet系列，以及rcnn系列發展下的maskrcnn，以及18年底的PAnet。基於語意的圖像分割技術，無疑會成為圖像分割技術的主流。

            其中，基於深度學習語意的其他相關演算法也可以間接或直接的應用到圖像分割。如經典的圖像matting問題。18年又出現了許多非常優秀的演算法和論文。如Deep-Image-Matting，以及效果非常優秀的MIT的 semantic soft segmentation(sss).

            基於語意的圖像分割效果明顯要好於其他的傳統演算法。我在解決圖像分割的問題時，首先嘗試用了hed網路。最後的效果並不理想。雖然也參考github，做了hed的一些fine-tune,但是還是上面提到的原因，在我多次嘗試後，最終放棄。轉而適用FCN系列的網路。但是fcn也無法解決圖像和背景相融的問題。圖片相融的分割，感覺即需要大的感受野，又需要未相融部分原圖像細節，所以單原FCN的網路，很難做出准確的分割。中間還測試過很多其他相關的網路，但都效果不佳。考慮到感受野和原圖像細節，嘗試了resnet和densenet作為圖像特徵提取的底層。最終我測試了unet系列的網路：

                unet的原始模型如圖所示。在自己拍照爬蟲等手段採集了將近1000張圖片。去掉了圖片質量太差的，圖片內容太過類似的。爬蟲最終收集160多張，自己拍照收集200張圖片後，又用ps手動p了邊緣圖像，採用圖像增強變換，大約有300*24張圖片。原生unet網路的表現比較一般。在將unet普通的卷積層改為resnet後，網路的表達能力明顯提升。在將resnet改為resnet101，此時，即使對於部分相融的圖像，也能較好的分割了。但是unet的模型體積已經不能接受。

                在最後階段，看到maskrcnn的實例分割。maskrcnn一路由rcnn,fasterrcnn發展過來。於是用maskrcnn來加入自己的訓練數據和label圖像進行訓練。maskrcnn的結果表現並不令人滿意，對於邊緣的定位，相比於其他演算法，略顯粗糙。在產品應用中，明顯還不合適。                

        3.基於圖的分割演算法

            基於深度學習的deepgrab,效果表現並不是十分理想。deepgrab的git作者backbone採用了deeplabv2的網路結構。並沒有完全安裝原論文來做。

論文原地址參考： https://arxiv.org/pdf/1707.00243.pdf

整體結構類似於encode和decoder。並沒有太仔細的研究，因為基於resent101的結構，在模型體積，速度以及deeplab的分割精度上，都不能滿足當前的需求。之前大致總結過計算機視覺的相關知識點，既然目前在討論移動端模型，那後面就分模塊總結下移動端模型的應用落地吧。

由於時間實在有限。這里並沒有針對每個演算法進行詳細的講解。後續我會從基礎的機器學習演算法開始總結。

❷ 最鄰近規則分類（K-Nearest Neighbor）KNN演算法（七）

1.1 Cover和Hart在1968年提出了最初的鄰近演算法。
1.2 分類(classification)演算法。
1.3 輸入基於實例的學習(instance-based learning),或則是懶惰學習(lazy learning)。-----（為什麼叫懶惰學習了？因為在處理大量的訓練集的時候並沒有建立大量的模型，而是剛開始的時候對於一個未知的實例進行歸類的時候我們會根據已知類型實例的比較來進行歸類）

目的：求未知的電影屬於什麼類型？ ----可以根據實例的特徵值來進行歸類（分類）。

3.1 步驟：

3.3 舉例:

4.1 演算法優點

4.2 演算法缺點

注意：在選擇k的時候，一般k為奇數，因為保證了結果相等的出現情況被排除了，如果選擇偶數，可能會出現結果相等

考慮距離，根據距離加上權重（ 比如: 1/d (d: 距離）---表示加權重來計算大小）

❸ 鄰近演算法

k-Nearest Neighbor algorithm K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，採用這種方法可以較好地避免樣本的不平衡問題。另外，由於 KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

❹ 鄰近演算法的缺點

該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。
可理解性差，無法給出像決策樹那樣的規則。

❺ 圖像分割

圖像閾值化分割是一種傳統的最常用的圖像分割方法，因其實現簡單、計算量小、性能較穩定而成為圖像分割中最基本和應用最廣泛的分割技術。它特別適用於目標和背景占據不同灰度級范圍的圖像。它不僅可以極大的壓縮數據量，而且也大大簡化了分析和處理步驟，因此在很多情況下，是進行圖像分析、特徵提取與模式識別之前的必要的圖像預處理過程。

圖像閾值化的目的是要按照灰度級，對像素集合進行一個劃分，得到的每個子集形成一個與現實景物相對應的區域，各個區域內部具有一致的屬性，而相鄰區域不具有這種一致屬性。這樣的劃分可以通過從灰度級出發選取一個或多個閾值來實現。

基本原理是：通過設定不同的特徵閾值，把圖像象素點分為若干類。
常用的特徵包括：直接來自原始圖像的灰度或彩色特徵；由原始灰度或彩色值變換得到的特徵。
設原始圖像為f(x，y)，按照一定的准則f(x，y)中找到特徵值T，將圖像分割為兩個部分，分割後的圖像為：
若取：b0=0(黑)，b1=1(白)，即為我們通常所說的圖像二值化。

閾值分割方法實際上是輸入圖像f到輸出圖像g的如下變換：

其中，T為閾值，對於物體的圖像元素g(i,j)=1，對於背景的圖像元素g(i,j)=0。

由此可見，閾值分割演算法的關鍵是確定閾值，如果能確定一個合適的閾值就可准確地將圖像分割開來。閾值確定後，將閾值與像素點的灰度值逐個進行比較，而且像素分割可對各像素並行地進行，分割的結果直接給出圖像區域。
閾值分割的優點是計算簡單、運算效率較高、速度快。有著各種各樣的閾值處理技術，包括全局閾值、自適應閾值、最佳閾值等等。

閾值處理技術參看：

區域分割是講圖像按照相似性准則分成不同的區域，主要包括區域增長，區域分裂合並和分水嶺等幾種類型。

區域生長是一種串列區域分割的圖像分割方法。區域生長是指從某個像素出發，按照一定的准則，逐步加入鄰近像素，當滿足一定的條件時，區域生長終止。區域生長的好壞決定於1. 初始點（種子點）的選取。 2. 生長准則。 3. 終止條件 。區域生長是從某個或者某些像素點出發，最後得到整個區域，進而實現目標的提取。

區域生長的基本思想是將具有相似性質的像素集合起來構成區域。具體先對每個需要分割的區域找一個種子像素作為生長的起點，然後將種子像素周圍鄰域中與種子像素有相同或相似性質的像素(根據某種事先確定的生長或相似准則來判定)合並到種子像素所在的區域中。將這些新像素當作新的種子像素繼續進行上面的過程，直到再沒有滿足條件的像素可被包括進來。這樣一個區域就長成了。

區域生長需要選擇一組能正確代表所需區域的種子像素，確定在生長過程中的相似性准則，制定讓生長停止的條件或准則。相似性准則可以是灰度級、彩色、紋理、梯度等特性。選取的種子像素可以是單個像素，也可以是包含若干個像素的小區域。大部分區域生長准則使用圖像的局部性質。生長准則可根據不同原則制定，而使用不同的生長准則會影響區域生長的過程。

圖1是區域增長的示例。

區域生長是一種古老的圖像分割方法，最早的區域生長圖像分割方法是由Levine等人提出的。該方法一般有兩種方式，一種是先給定圖像中要分割的目標物體內的一個小塊或者說種子區域(seed point)，再在種子區域基礎上不斷將其周圍的像素點以一定的規則加入其中，達到最終將代表該物體的所有像素點結合成一個區域的目的；另一種是先將圖像分割成很多的一致性較強，如區域內像素灰度值相同的小區域，再按一定的規則將小區域融合成大區域，達到分割圖像的目的，典型的區域生長法如T. C. Pong等人提出的基於小面（facet）模型的區域生長法，區域生長法固有的缺點是往往會造成過度分割，即將圖像分割成過多的區域

區域生長實現的步驟如下:

區域分裂合並演算法的基本思想是先確定一個分裂合並的准則，即區域特徵一致性的測度，當圖像中某個區域的特徵不一致時就將該區域分裂成4個相等的子區域，當相鄰的子區域滿足一致性特徵時則將它們合成一個大區域，直至所有區域不再滿足分裂合並的條件為止。當分裂到不能再分的情況時，分裂結束，然後它將查找相鄰區域有沒有相似的特徵，如果有就將相似區域進行合並，最後達到分割的作用。在一定程度上區域生長和區域分裂合並演算法有異曲同工之妙，互相促進相輔相成的，區域分裂到極致就是分割成單一像素點，然後按照一定的測量准則進行合並，在一定程度上可以認為是單一像素點的區域生長方法。區域生長比區域分裂合並的方法節省了分裂的過程，而區域分裂合並的方法可以在較大的一個相似區域基礎上再進行相似合並，而區域生長只能從單一像素點出發進行生長（合並）。

反復進行拆分和聚合以滿足限制條件的演算法。

令R表示整幅圖像區域並選擇一個謂詞P。對R進行分割的一種方法是反復將分割得到的結果圖像再次分為四個區域，直到對任何區域Ri，有P(Ri)=TRUE。這里是從整幅圖像開始。如果P(R)=FALSE，就將圖像分割為4個區域。對任何區域如果P的值是FALSE．就將這4個區域的每個區域再次分別分為4個區域，如此不斷繼續下去。這種特殊的分割技術用所謂的四叉樹形式表示最為方便(就是說，每個非葉子節點正好有4個子樹)，這正如圖10.42中說明的樹那樣。注意，樹的根對應於整幅圖像，每個節點對應於劃分的子部分。此時，只有R4進行了進一步的再細分。

如果只使用拆分，最後的分區可能會包含具有相同性質的相鄰區域。這種缺陷可以通過進行拆分的同時也允許進行區域聚合來得到矯正。就是說，只有在P(Rj∪Rk)=TRUE時，兩個相鄰的區域Rj和Rk才能聚合。
前面的討論可以總結為如下過程。在反復操作的每一步，我們需要做：

可以對前面講述的基本思想進行幾種變化。例如，一種可能的變化是開始時將圖像拆分為一組圖象塊。然後對每個塊進一步進行上述拆分，但聚合操作開始時受只能將4個塊並為一組的限制。這4個塊是四叉樹表示法中節點的後代且都滿足謂詞P。當不能再進行此類聚合時，這個過程終止於滿足步驟2的最後的區域聚合。在這種情況下，聚合的區域可能會大小不同。這種方法的主要優點是對於拆分和聚合都使用同樣的四叉樹，直到聚合的最後一步。

分水嶺分割方法，是一種基於拓撲理論的數學形態學的分割方法，其基本思想是把圖像看作是測地學上的拓撲地貌，圖像中每一點像素的灰度值表示該點的海拔高度，每一個局部極小值及其影響區域稱為集水盆，而集水盆的邊界則形成分水嶺。分水嶺的概念和形成可以通過模擬浸入過程來說明。在每一個局部極小值表面，刺穿一個小孔，然後把整個模型慢慢浸入水中，隨著浸入的加深，每一個局部極小值的影響域慢慢向外擴展，在兩個集水盆匯合處構築大壩，即形成分水嶺。

分水嶺的計算過程是一個迭代標注過程。分水嶺比較經典的計算方法是L. Vincent提出的。在該演算法中，分水嶺計算分兩個步驟，一個是排序過程，一個是淹沒過程。首先對每個像素的灰度級進行從低到高排序，然後在從低到高實現淹沒過程中，對每一個局部極小值在h階高度的影響域採用先進先出(FIFO)結構進行判斷及標注。

分水嶺變換得到的是輸入圖像的集水盆圖像，集水盆之間的邊界點，即為分水嶺。顯然，分水嶺表示的是輸入圖像極大值點。因此，為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即

分水嶺演算法對微弱邊緣具有良好的響應，圖像中的雜訊、物體表面細微的灰度變化，都會產生過度分割的現象。但同時應當看出，分水嶺演算法對微弱邊緣具有良好的響應，是得到封閉連續邊緣的保證的。另外，分水嶺演算法所得到的封閉的集水盆，為分析圖像的區域特徵提供了可能。
為消除分水嶺演算法產生的過度分割，通常可以採用兩種處理方法，一是利用先驗知識去除無關邊緣信息。二是修改梯度函數使得集水盆只響應想要探測的目標。

為降低分水嶺演算法產生的過度分割，通常要對梯度函數進行修改，一個簡單的方法是對梯度圖像進行閾值處理，以消除灰度的微小變化產生的過度分割。即

程序可採用方法：用閾值限制梯度圖像以達到消除灰度值的微小變化產生的過度分割，獲得適量的區域，再對這些區域的邊緣點的灰度級進行從低到高排序，然後在從低到高實現淹沒的過程，梯度圖像用Sobel運算元計算獲得。對梯度圖像進行閾值處理時，選取合適的閾值對最終分割的圖像有很大影響，因此閾值的選取是圖像分割效果好壞的一個關鍵。缺點：實際圖像中可能含有微弱的邊緣，灰度變化的數值差別不是特別明顯，選取閾值過大可能會消去這些微弱邊緣。

參考文章：

圖像分割的一種重要途徑是通過邊緣檢測，即檢測灰度級或者結構具有突變的地方，表明一個區域的終結，也是另一個區域開始的地方。這種不連續性稱為邊緣。不同的圖像灰度不同，邊界處一般有明顯的邊緣，利用此特徵可以分割圖像。

圖像中邊緣處像素的灰度值不連續，這種不連續性可通過求導數來檢測到。對於階躍狀邊緣，其位置對應一階導數的極值點，對應二階導數的過零點(零交叉點)。因此常用微分運算元進行邊緣檢測。常用的一階微分運算元有Roberts運算元、Prewitt運算元和Sobel運算元，二階微分運算元有Laplace運算元和Kirsh運算元等。在實際中各種微分運算元常用小區域模板來表示，微分運算是利用模板和圖像卷積來實現。這些運算元對雜訊敏感，只適合於雜訊較小不太復雜的圖像。

由於邊緣和雜訊都是灰度不連續點，在頻域均為高頻分量，直接採用微分運算難以克服雜訊的影響。因此用微分運算元檢測邊緣前要對圖像進行平滑濾波。LoG運算元和Canny運算元是具有平滑功能的二階和一階微分運算元，邊緣檢測效果較好，

在邊緣檢測演算法中，前三個步驟用得十分普遍。這是因為大多數場合下，僅僅需要邊緣檢測器指出邊緣出現在圖像某一像素點的附近，而沒有必要指出邊緣的精確位置或方向．邊緣檢測誤差通常是指邊緣誤分類誤差，即把假邊緣判別成邊緣而保留，而把真邊緣判別成假邊緣而去掉．邊緣估計誤差是用概率統計模型來描述邊緣的位置和方向誤差的．我們將邊緣檢測誤差和邊緣估計誤差區分開，是因為它們的計算方法完全不同，其誤差模型也完全不同．

Roberts運算元 ：邊緣定位準，但是對雜訊敏感。適用於邊緣明顯且雜訊較少的圖像分割。Roberts邊緣檢測運算元是一種利用局部差分運算元尋找邊緣的運算元,Robert運算元圖像處理後結果邊緣不是很平滑。經分析，由於Robert運算元通常會在圖像邊緣附近的區域內產生較寬的響應，故採用上述運算元檢測的邊緣圖像常需做細化處理，邊緣定位的精度不是很高。

Prewitt運算元 ：對雜訊有抑製作用，抑制雜訊的原理是通過像素平均，但是像素平均相當於對圖像的低通濾波，所以Prewitt運算元對邊緣的定位不如Roberts運算元。

Sobel運算元 ：Sobel運算元和Prewitt運算元都是加權平均，但是Sobel運算元認為，鄰域的像素對當前像素產生的影響不是等價的，所以距離不同的像素具有不同的權值，對運算元結果產生的影響也不同。一般來說，距離越遠，產生的影響越小。

Isotropic Sobel運算元 ：加權平均運算元，權值反比於鄰點與中心點的距離，當沿不同方向檢測邊緣時梯度幅度一致，就是通常所說的各向同性。
在邊沿檢測中，常用的一種模板是Sobel 運算元。Sobel 運算元有兩個，一個是檢測水平邊沿的；另一個是檢測垂直平邊沿的 。Sobel運算元另一種形式是各向同性Sobel(Isotropic Sobel)運算元，也有兩個，一個是檢測水平邊沿的，另一個是檢測垂直平邊沿的 。各向同性Sobel運算元和普通Sobel運算元相比，它的位置加權系數更為准確，在檢測不同方向的邊沿時梯度的幅度一致。由於建築物圖像的特殊性，我們可以發現，處理該類型圖像輪廓時，並不需要對梯度方向進行運算，所以程序並沒有給出各向同性Sobel運算元的處理方法。

1971年，R.Kirsch[34]提出了一種能檢測邊緣方向的Kirsch運算元新方法：它使用了8個模板來確定梯度幅度值和梯度的方向。

圖像中的每個點都用8個掩模進行卷積，每個掩模對某個特定邊緣方向作出最大響應。所有8個方向中的最大值作為邊緣幅度圖像的輸出。最大響應掩模的序號構成了對邊緣方向的編碼。
Kirsch運算元的梯度幅度值用如下公式：

不同檢測運算元的對比：

參考文章：

文章引用於 木夜溯
編輯 Lornatang
校準 Lornatang

❻ 鄰近演算法的演算法流程

1. 准備數據，對數據進行預處理
2. 選用合適的數據結構存儲訓練數據和測試元組
3. 設定參數，如k
4.維護一個大小為k的的按距離由大到小的優先順序隊列，用於存儲最近鄰訓練元組。隨機從訓練元組中選取k個元組作為初始的最近鄰元組，分別計算測試元組到這k個元組的距離，將訓練元組標號和距離存入優先順序隊列
5. 遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L 與優先順序隊列中的最大距離Lmax
6. 進行比較。若L>=Lmax，則舍棄該元組，遍歷下一個元組。若L < Lmax，刪除優先順序隊列中最大距離的元組，將當前訓練元組存入優先順序隊列。
7. 遍歷完畢，計算優先順序隊列中k 個元組的多數類，並將其作為測試元組的類別。
8. 測試元組集測試完畢後計算誤差率，繼續設定不同的k值重新進行訓練，最後取誤差率最小的k 值。

❼ 鄰近演算法的優點

1.簡單，易於理解，易於實現，無需估計參數，無需訓練；
2. 適合對稀有事件進行分類；
3.特別適合於多分類問題(multi-modal,對象具有多個類別標簽)， kNN比SVM的表現要好。

❽ 鄰近圖演算法基本思想是什麼為何說該演算法能夠節省能量

鄰近圖的功率控制演算法的基本思想。如果一個樣本在特徵空間中的K個最相似（即特徵空間中最鄰近）的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。它的整體思想簡單，效果強大。

❾ knn演算法是什麼

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

介紹

KNN演算法本身簡單有效，它是一種lazy-learning演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為n，那麼KNN的分類時間復雜度為O(n)。

KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

❿ 使用Node.js如何實現K最近鄰分類演算法

源於數據挖掘的一個作業， 這里用Node.js技術來實現一下這個機器學習中最簡單的演算法之一k-nearest-neighbor演算法(k最近鄰分類法)。
k-nearest-neighbor-classifier
還是先嚴謹的介紹下。急切學習法（eager learner）是在接受待分類的新元組之前就構造了分類模型，學習後的模型已經就緒，急著對未知的元組進行分類，所以稱為急切學習法，諸如決策樹歸納，貝葉斯分類等都是急切學習法的例子。惰性學習法（lazy learner）正好與其相反，直到給定一個待接受分類的新元組之後，才開始根據訓練元組構建分類模型，在此之前只是存儲著訓練元組，所以稱為惰性學習法，惰性學習法在分類進行時做更多的工作。
本文的knn演算法就是一種惰性學習法，它被廣泛應用於模式識別。knn基於類比學習，將未知的新元組與訓練元組進行對比，搜索模式空間，找出最接近未知元組的k個訓練元組，這里的k即是knn中的k。這k個訓練元祖就是待預測元組的k個最近鄰。
balabala了這么多，是不是某些同學想大喊一聲..speak Chinese! 還是來通俗的解釋下，然後再來看上面的理論應該會明白很多。小時候媽媽會指著各種各樣的東西教我們，這是小鴨子，這個紅的是蘋果等等，那我們哼哧哼哧的看著應答著，多次被教後再看到的時候我們自己就能認出來這些事物了。主要是因為我們在腦海像給這個蘋果貼了很多標簽一樣，不只是顏色這一個標簽，可能還有蘋果的形狀大小等等。這些標簽讓我們看到蘋果的時候不會誤認為是橘子。其實這些標簽就對應於機器學習中的特徵這一重要概念，而訓練我們識別的過程就對應於泛化這一概念。一台iphone戴了一個殼或者屏幕上有一道劃痕，我們還是能認得出來它，這對於我們人來說非常簡單，但蠢計算機就不知道怎麼做了，需要我們好好調教它，當然也不能過度調教2333，過度調教它要把其他手機也認成iphone那就不好了，其實這就叫過度泛化。
所以特徵就是提取對象的信息，泛化就是學習到隱含在這些特徵背後的規律，並對新的輸入給出合理的判斷。
我們可以看上圖，綠色的圓代表未知樣本，我們選取距離其最近的k個幾何圖形，這k個幾何圖形就是未知類型樣本的鄰居，如果k=3，我們可以看到有兩個紅色的三角形，有一個藍色的三正方形，由於紅色三角形所佔比例高，所以我們可以判斷未知樣本類型為紅色三角形。擴展到一般情況時，這里的距離就是我們根據樣本的特徵所計算出來的數值，再找出距離未知類型樣本最近的K個樣本，即可預測樣本類型。那麼求距離其實不同情況適合不同的方法，我們這里採用歐式距離。
綜上所述knn分類的關鍵點就是k的選取和距離的計算。
2. 實現
我的數據是一個xls文件，那麼我去npm搜了一下選了一個叫node-xlrd的包直接拿來用。
// node.js用來讀取xls文件的包
var xls = require('node-xlrd');
然後直接看文檔實例即可，把數據解析後插入到自己的數據結構里。
var data = [];// 將文件中的數據映射到樣本的屬性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 讀取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件讀取完畢後 執行測試
run();
});
然後定義一個構造函數Sample表示一個樣本，這里是把剛生成的數據結構里的對象傳入，生成一個新的樣本。
// Sample表示一個樣本
var Sample = function (object) {
// 把傳過來的對象上的屬性克隆到新創建的樣本上
for (var key in object)
{
// 檢驗屬性是否屬於對象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定義一個樣本集的構造函數
// SampleSet管理所有樣本 參數k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 將樣本加入樣本數組
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然後我們會在樣本的原型上定義很多方法，這樣每個樣本都可以用這些方法。
// 計算樣本間距離 採用歐式距離
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 計算歐式距離
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 將鄰居樣本根據與預測樣本間距離排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判斷被預測樣本類別
Sample.prototype.guessType = function(k) {
// 有兩種類別 1和-1
var types = { '1': 0, '-1': 0 };
// 根據k值截取鄰居裡面前k個
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判斷鄰居里哪個樣本類型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我這里的數據有a-k共11個屬性，樣本有1和-1兩種類型，使用truetype和type來預測樣本類型和對比判斷是否分類成功。
最後是樣本集的原型上定義一個方法，該方法可以在整個樣本集里尋找未知類型的樣本，並生成他們的鄰居集，調用未知樣本原型上的方法來計算鄰居到它的距離，把所有鄰居按距離排序，最後猜測類型。
// 構建總樣本數組，包含未知類型樣本
SampleSet.prototype.determineUnknown = function() {

for (var i in this.samples)
{
// 如果發現沒有類型的樣本
if ( ! this.samples[i].type)
{
// 初始化未知樣本的鄰居
this.samples[i].neighbors = [];
// 生成鄰居集
for (var j in this.samples)
{
// 如果碰到未知樣本 跳過
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 計算所有鄰居與預測樣本的距離
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有鄰居按距離排序
this.samples[i].sortByDistance();
// 猜測預測樣本類型
this.samples[i].guessType(this.k);
}
}
};
最後分別計算10倍交叉驗證和留一法交叉驗證的精度。
留一法就是每次只留下一個樣本做測試集，其它樣本做訓練集。
K倍交叉驗證將所有樣本分成K份，一般均分。取一份作為測試樣本，剩餘K-1份作為訓練樣本。這個過程重復K次，最後的平均測試結果可以衡量模型的性能。
k倍驗證時定義了個方法先把數組打亂隨機擺放。
// helper函數 將數組里的元素隨機擺放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩餘測試代碼好寫，這里就不貼了。
測試結果為
用餘弦距離等計算方式可能精度會更高。
3. 總結
knn演算法非常簡單，但卻能在很多關鍵的地方發揮作用並且效果非常好。缺點就是進行分類時要掃描所有訓練樣本得到距離，訓練集大的話會很慢。
可以用這個最簡單的分類演算法來入高大上的ML的門，會有點小小的成就感。