快速近似最近鄰演算法介紹

⑴ 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。

⑵ 大數據挖掘的演算法有哪些

大數據挖掘的演算法：
1.樸素貝葉斯，超級簡單，就像做一些數數的工作。如果條件獨立假設成立的話，NB將比鑒別模型收斂的更快，所以你只需要少量的訓練數據。即使條件獨立假設不成立，NB在實際中仍然表現出驚人的好。
2. Logistic回歸，LR有很多方法來對模型正則化。比起NB的條件獨立性假設，LR不需要考慮樣本是否是相關的。與決策樹與支持向量機不同，NB有很好的概率解釋，且很容易利用新的訓練數據來更新模型。如果你想要一些概率信息或者希望將來有更多數據時能方便的更新改進模型，LR是值得使用的。
3.決策樹，DT容易理解與解釋。DT是非參數的，所以你不需要擔心野點（或離群點）和數據是否線性可分的問題，DT的主要缺點是容易過擬合，這也正是隨機森林等集成學習演算法被提出來的原因。
4.支持向量機，很高的分類正確率，對過擬合有很好的理論保證，選取合適的核函數，面對特徵線性不可分的問題也可以表現得很好。SVM在維數通常很高的文本分類中非常的流行。

如果想要或許更多更詳細的訊息，建議您去參加CDA數據分析課程。大數據分析師現在有專業的國際認證證書了，CDA，即「CDA 數據分析師」，是在數字經濟大背景和人工智慧時代趨勢下，面向全行業的專業權威國際資格認證， 旨在提升全民數字技能，助力企業數字化轉型，推動行業數字化發展。 「CDA 數據分析師」具體指在互聯網、金融、零售、咨詢、電信、醫療、旅遊等行業專門從事數據的採集、清洗、處理、分析並能製作業務報告、 提供決策的新型數據分析人才。點擊預約免費試聽課。

⑶ k近鄰演算法的案例介紹

如 上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。 於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN 演算法本身簡單有效，它是一種 lazy-learning 演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間復雜度為O(n)。
KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
K 近鄰演算法使用的模型實際上對應於對特徵空間的劃分。K 值的選擇，距離度量和分類決策規則是該演算法的三個基本要素： K 值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。 該演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。 KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
實現 K 近鄰演算法時，主要考慮的問題是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

⑷ K-近鄰演算法 KNN

K值選擇問題 ，李航博士的一書「統計學習方法」上所說：

近似誤差（train loss）：

估計誤差（test loss）：

 在實際應用中，K值一般取一個比較小的數值，例如採用交叉驗證法（簡單來說，就是把訓練數據在分成兩組:訓練集和驗證集）來選擇最優的K值。

 例如：將數據分成4份，其中一份作為驗證集。然後經過4次(組)的測試，每次都更換不同的驗證集。即得到4組模型的結果，取平均值作為最終結果。又稱4折交叉驗證。

 據KNN每次需要預測一個點時，我們都需要計算訓練數據集里每個點到這個點的距離，然後選出距離最近的k個點進行投票。當數據集很大時，這個計算成本非常高，針對N個樣本，D個特徵的數據集，其演算法復雜度為O(DN ² )。

在構建kd樹時，有2個關鍵問題：
（1）選擇向量的哪一維進行劃分? 隨機選擇某一維或按順序選擇，但是更好的方法應該是在數據比較分散的那一維進行劃分（分散的程度可以根據方差來衡量）。
（2）如何劃分數據? 好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數來進行劃分。
構造方法

  給定一個二維空間數據集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，構造一個平衡kd樹。

 優點：

 缺點：

⑸ 什麼叫做knn演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的非參數統計方法。

在這兩種情況下，輸入包含特徵空間（Feature Space）中的k個最接近的訓練樣本。

1、在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k=1，則該對象的類別直接由最近的一個節點賦予。

2、在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-均值演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關系。數據標准化可以大大提高該演算法的准確性。

參數選擇

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一個較好的K值能通過各種啟發式技術（見超參數優化）來獲取。

雜訊和非相關性特徵的存在，或特徵尺度與它們的重要性不一致會使K近鄰演算法的准確性嚴重降低。對於選取和縮放特徵來改善分類已經作了很多研究。一個普遍的做法是利用進化演算法優化功能擴展，還有一種較普遍的方法是利用訓練樣本的互信息進行選擇特徵。

在二元（兩類）分類問題中，選取k為奇數有助於避免兩個分類平票的情形。在此問題下，選取最佳經驗k值的方法是自助法。

⑹ KNN演算法-4-演算法優化-KD樹

KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。

Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。

必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：

首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。

常規的k-d tree的構建過程為：

對於構建過程，有兩個優化點：

例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：

如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。

如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。

如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。

首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。

接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。

遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。

舉例：查詢點（2，4.5）

一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。

一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：

但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：

研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。

同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。

Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。

⑺ 2021-01-21

摘要

人臉聚類最近吸引了越來越多的研究興趣，以利用網路上的大量人臉圖像。圖卷積網路（GCN）由於其強大的表示能力而實現了最先進的性能。然而，現有的基於 GCN 的方法主要根據特徵空間中的 kNN 關系構建人臉圖，這可能導致連接不同類別的兩個人臉的大量雜訊邊緣。當消息通過這些雜訊邊緣時，面部特徵將被污染，從而降低 GCN 的性能。在本文中，提出了一種名為 Ada-NETS 的新演算法，通過為 GCN 構建干凈的圖來聚類人臉。在 Ada-NETS 中，每個人臉都被轉換到一個新的結構空間，通過考慮相手租鄰圖像的人臉特徵來獲得魯棒的特徵。然後，提出了一種自適應鄰居發現策略來確定連接到每個人臉圖像的適當數量的邊。它顯著減少了雜訊邊緣，同時保持了良好的邊緣，從而為 GCN 構建具有干凈而豐富邊緣的圖形來聚類人臉。在多個公共聚類數據集上的實驗表明，Ada-NETS 顯著優於當前最先進的方法，證明了其優越性和泛化性。

1.引言

近年來，網路上的圖像數量迅速增加，其中很大一部分是以人為中心的照片。在幾乎沒有人為參與的情況下理解和管理這些照片是一項艱巨的任務，例如將來自某個人的照片關聯在一起。面對這些需求的一個基本問題是人臉聚類（Manning et al., 2008）。

近年來，人臉聚類得到了徹底的研究。使用圖卷積網路獲得了顯著的性能改進（Wang 等人，2019b；Yang 等人，2019；2020；Guo 等人，2020；Shen 等人，2021）由於其強大的特徵傳播能力.代表性的 DA-Net (Guo et al., 2020) 和 STAR-FC (Shen et al., 2021) 使用 GCN 通過頂點或邊分類任務來學習增強的特徵嵌入，以輔助聚類。

然而，限制現有基於 GCN 的人臉聚類演算法能力的主要問題是人臉圖中存在雜訊邊緣。如圖1（b）所示，雜訊邊緣是指不同類別的兩個面之間的連接。與 Citeseer、Cora 和 Pubmed 等以顯式鏈接關系作為邊的常見圖形數據集不同（Kipf & Welling, 2017），人臉圖像不包含明確的結構信息，而僅包含從經過訓練的 CNN 模型中提取的深層特徵。因此，人臉圖像被視為頂點，人臉圖像之間的邊緣通常在構建圖時基於 kNN (Cover & Hart, 1967) 關系構建：每個人臉作為一個探針，通過以下方式檢索其 k 個最近鄰居深度特徵（Wang 等人，2019b；Yang 等人，2019；2020；Guo 等人，2020；Shen 等人，2021）。 kNN 關系並不總是可靠的，因為深度特徵不夠准確。因此，雜訊邊緣與 kNN 一起被引入到圖中。雜訊邊緣問題在人臉聚類中很常見，但很少受到研究關注。例如，(Yang et al., 2020; Shen et al., 2021) 中使用的圖在測試中包含約 38.23% 的雜訊邊緣。雜訊邊緣會在頂點之間傳播雜訊信息，在聚合時會損害它們的特徵，從而導致性能下降。在圖 1 (b) 中，三角形頂點 v1 與三個不同類別的頂點相連，它會被圖中傳遞的消息污染。因此，基於 GCN 的鏈接預測無法有效解決相關工作中的雜訊邊緣問題（Wang 等人，2019b；Yang 等人，2020；Shen 等人，2021）。

圖 1：基於 GCN 的人臉聚類中的雜訊邊緣問題。圖中不同的形狀代表不同的類別。 (a) 要聚類的人臉圖像。 (b) 在基於 na ̈ıve kNN 構建圖時引入了雜訊邊緣。 (c) 通過特徵距離連接邊緣可能會導致雜訊邊緣。 (d) 現有的「一刀切」的解決方案對每個頂點使用固定數量的鄰居會引入許多雜訊邊緣。

如圖 1 (c) (d) 所示，去除人臉圖中的雜訊邊緣的挑戰是雙重的。首先，深度特徵的表示能力在現實世界的數據中是有限的。僅根據深度特徵很難判斷兩個頂點是否屬於同一類，因此連接不同類的兩個頂點不可避免地會帶來雜訊邊緣。其次侍薯消，在構建圖時很難確定每個頂點連接多少條邊：連接的邊太少會導致圖中的信息聚合不足。連接的邊太多會增加雜訊邊的數量，並且頂點特徵會被錯誤連接的頂點老知污染。雖然 Clusformer (Nguyen et al., 2021) 和 GAT (Velickovic et al., 2018) 試圖通過注意力機制減少雜訊邊緣的影響，但各個頂點之間的連接非常復雜，因此很難找到注意力權重學習的常見模式（Yang et al., 2020）。

為了克服這些嚴峻的挑戰，每個頂點周圍的特徵都被考慮在內，因為它們可以提供更多信息。具體來說，當考慮附近的其他頂點時，可以改進每個頂點特徵表示。這有利於解決圖 1 (c) 中的表示挑戰。然後，一個頂點與其他頂點之間的邊數可以從它周圍的特徵模式中學習，而不是為所有頂點手動設計參數。這種學習方法可以有效地減少雜訊邊緣的連接，這對於解決圖 1 (d) 中的第二個挑戰至關重要。基於上述思想，提出了一種新的聚類演算法，稱為結構空間中的自適應鄰居發現（Ada-NETS），用於處理聚類中的雜訊邊緣問題。在 Ada-NETS 中，首先提出了一個結構空間，其中頂點在感知數據分布後，可以通過編碼更多的紋理信息來獲得魯棒的特徵。然後，仔細設計候選鄰居質量標准以指導構建雜訊較小但豐富的邊緣，以及可學習的自適應濾波器來學習該標准。通過這種方式，自適應地發現每個頂點的鄰居，以構建具有干凈和豐富邊緣的圖。最後，GCN 將此圖作為輸入來聚類人臉。

本文的主要貢獻總結如下：

• 據我們所知，這是第一篇在人臉圖像上為 GCN 構建圖時解決雜訊邊緣問題的論文。同時，本文闡述了其成因、重大影響、現有解決方案的弱點以及解決該問題的挑戰。

• 所提出的 Ada-NETS 可以緩解在人臉圖像上構建圖形時的雜訊邊緣問題，從而極大地改進 GCN 以提高聚類性能。

• Ada-NETS 在聚類任務上取得了最先進的性能，在人臉、人物和衣服數據集上大大超過了之前的表現。

2 相關工作

FaceClustering 人臉聚類任務軟化人臉大規模樣本和復雜數據分布，因此引起了特別的研究關注。經典的無監督方法速度很慢，並且由於其簡單的分布假設無法實現良好的性能，例如 K-Means 中的凸形數據（Lloyd，1982）和 DBSCAN 中相似的數據密度（Ester et al.，1996））。近年來，基於 GCN 的監督方法被證明對人臉聚類有效且高效。 L-GCN (Wang et al., 2019b) 部署了一個 GCN 用於子圖的鏈接預測。 DS-GCN (Yang et al., 2019) 和 VE-GCN (Yang et al., 2020) 都提出了基於大 kNN 圖的兩階段 GCN 聚類。 DA-Net (Guo et al., 2020) 通過基於密度的圖利用非本地上下文信息進行聚類。 Clusformer (Nguyen et al., 2021) 將人臉與變壓器進行聚類。 STAR-FC (Shen et al., 2021) 開發了一種結構保留的采樣策略來訓練邊緣分類 GCN。這些成就展示了 GCN 在表示和聚類方面的強大功能。然而，現有方法大多基於kNN構建人臉圖，其中包含大量雜訊邊緣。在構建這些圖時，僅根據並不總是准確的深度特徵來獲得頂點之間的相似度，並且每個頂點的邊數是固定的或由相似度閾值確定。

Graph Convolutional Networks GCN 被提出來處理非歐幾里得數據，並在學習圖模式方面展示了它們的能力。它最初用於轉導式半監督學習 (Kipf & Welling, 2017)，並由學習特徵聚合原理的 GraphSAGE (Hamilton et al., 2017) 擴展到歸納任務。為了進一步擴展 GCN 的表示能力，可學習的邊權重被引入到圖注意網路 (GAT) 中的圖聚合中 (Velickovic et al., 2018)。除了人臉聚類，GCN 還用於許多任務，例如基於骨架的動作識別 (Yan et al., 2018)、知識圖譜 (Schlichtkrull et al., 2018) 和推薦系統 (Ying et al., 2018) .然而，這些方法是在結構數據上提出的，其中明確給出了邊緣。如果圖形是由大量雜訊邊緣構成的，則 GCN 在人臉圖像數據集上可能表現不佳。

圖 2：Ada-NETS 的框架。 （一世）。將特徵轉換到結構空間以獲得更好的相似度度量。 (二)。每個頂點的鄰居由自適應濾波器發現。 （三）。使用 (II) 發現的鄰居關系構建圖，GCN 模型使用該圖對頂點對進行分類。最終的聚類結果是使用來自 GCN 的嵌入來鏈接具有高相似性的頂點對獲得的。

3 方法論

人臉聚類旨在將一組人臉樣本進行分組，使一個組中的樣本屬於一個身份，不同組中的任意兩個樣本屬於不同的身份。給定一組特徵向量 V = {v1,v2,...,vi,...,vN | vi ∈ RD} 由經過訓練的 CNN 模型從人臉圖像中提取，聚類任務為每個向量 vi 分配一個組標簽。 N是樣本總數，D是每個特徵的維度。提出了如圖 2 所示的 Ada-NETS 演算法，通過處理人臉圖中的雜訊邊緣來對人臉進行聚類。首先，將特徵轉換為提出的結構空間以獲得准確的相似度度量。然後使用自適應鄰居發現策略為每個頂點查找鄰居。根據發現結果，構建一個具有干凈和豐富邊緣的圖作為 GCN 的輸入圖，用於最終聚類。

3.1 結構空間

雜訊邊緣問題會導致頂點特徵的污染，降低基於 GCN 的聚類的性能。僅僅根據它們的深度特徵很難確定兩個頂點是否屬於同一類，因為不同類的兩個頂點也可以具有很高的相似性，從而引入雜訊邊緣。不幸的是，據我們所知，幾乎所有現有方法（Wang 等人，2019b；Yang 等人，2020；Guo 等人，2020；Shen 等人，2021）僅基於成對餘弦構建圖使用深度特徵的頂點之間的相似性。實際上，可以通過考慮結構信息來改進相似度度量，即數據集圖像之間的鄰域關系。基於這一思想，提出了結構空間的概念來應對這一挑戰。在結構空間中，特徵可以通過感知數據分布來編碼更多的紋理信息，從而更加穩健（Zhang et al., 2020）。一個轉換函數 φ 被部署來將一個特徵 vi 轉換為結構空間，記為 vis：

vis = φ(vi|V),∀i ∈ {1,2,··· ,N}。 (1)

如圖2（I）所示，在結構空間的幫助下，對於一個頂點vi，它與其他頂點的相似度通過以下步驟計算：首先，通過近似最近鄰（Approximate Nearest-neighbour）獲得vi的kNN（ ANN) 演算法基於 vi 與其他頂點之間的餘弦相似度，記為 N (vi, k) = {vi1 , vi2 , ···, vik }。其次，通過核方法 (Shawe-Taylor & Cristianini, 2004) 進行激勵，我們不是直接求解 φ 的形式，而是通過以下方式定義 vi 與其在結構空間中的每個候選者的相似性

κ􏰅v,v =􏰈vs,vs􏰉 iij iij

(2) 其中 η 加權餘弦相似度 scos 􏰅v ,v 􏰆 = vi·vij 和 Jaccard 相似度

􏰎(1−η)sJac􏰅v,v 􏰆+ηscosv,v , ∀j∈{1,2,···,k}, i ij i ij

i ij ∥vi∥∥vij ∥

sJac 􏰅v , v 􏰆 受到基於公共鄰居的度量的啟發（Zhong et al., 2017）。和

我

上面的定義， κ 􏰅v , v 測量 v 和 v 在結構空間中的相似性。

iij i ij 3.2 自適應鄰居發現

現有方法通過深度特徵（Wang 等人，2019b；Yang 等人，2020；Shen 等人，2021）或使用固定的相似度閾值（Guo 等人，2020）從樸素的 kNN 關系中連接邊緣。這些方法都是一刀切的解決方案，超參數對性能有很大影響。為了解決這個問題，提出了自適應鄰居發現模塊來學習每個頂點周圍的特徵模式，如圖2（II）所示。

對於頂點vi，其大小為j的候選鄰居是基於深度特徵相似度的j個最近鄰居頂點，其中j = 1, 2,····,k。它的鄰居是指一個特定大小的候選鄰居，滿足如下所述的某些特定標准。 vi 與其所有鄰居之間的邊被構造。

3.2.1 候選鄰居質量標准

受頂點置信度估計方法 (Yang et al., 2020) 的啟發，設計了一種啟發式標准來評估每個探測頂點的候選鄰居的質量。好鄰居應該是干凈的，即大多數鄰居應該與探測頂點具有相同的類標簽，這樣在構建圖時就不會大量包含雜訊邊緣。鄰居也應該是豐富的，這樣消息才能在圖中完全傳遞。為了滿足這兩個原則，在信息檢索中根據Fβ-score（Rijsbergen，1979）提出了標准。與視覺語法類似（Nguyen et al., 2021），所有候選鄰居都按照與序列中探測頂點的相似度排序。給定由頂點 vi 探測到的大小為 j 的候選鄰居，其質量標准 Q (j) 定義為：

其中 P rj 和 Rcj 是前 j 個候選鄰居相對於 vi 的標簽的精度和召回率。 β 是權重平衡精度和召回率。較高的 Q 值表示更好的候選鄰居質量。

3.2.2 自適應濾波器

使用上述標准，koff 被定義為要選擇的鄰居數量的啟發式真實值：

3.3 用於人臉聚類的 ADA-NETS

為了有效解決人臉聚類中的雜訊邊緣問題，Ada-NETS 首先利用所提出的結構空間和自適應鄰居發現來構建具有干凈和豐富邊緣的圖。然後使用 GCN 模型完成該圖中的聚類，如圖 2（III）所示。使用上述結構空間中的相似度度量和自適應鄰居發現方法，頂點vi的發現鄰居表示為N s(vi, k)：

其中 Ind 表示按 κ 􏰅v , v 􏰆 降序排列的 v 的索引。基於這些鄰居關系，如果其中任何一個是另一個已發現的鄰居，則通過鏈接兩個頂點之間的邊來生成無向圖 G (F, A)。 F = [v1 , v2 , ··· , vN ]T 為頂點特徵矩陣，A 為鄰接矩陣：

通過構建的圖 G(F,A)，使用 GCN 模型來學習兩個頂點是否屬於同一類。一個 GCN 層定義為：

其中 A ̃ = A + I, I ∈ RN ×N 是單位矩陣，D ̃ 是對角度矩陣 D ̃ ii = 􏰊Nj=1 A ̃ i,j , Fl 和 Wl 分別是輸入特徵矩陣和第 l 層的權重矩陣，和

σ(·) 是一個激活函數。本文使用了兩個 GCN 層，然後是一個具有 PReLU (He et al., 2015) 激活和一個歸一化的 FC 層。對於一批隨機采樣的頂點 Bv，訓練損失定義為鉸鏈損失的變體版本（Rosasco et al., 2004）：

其中 yvi,vj 是批次 Bv 中兩個頂點 vi 和 vj 的 GCN 輸出特徵 v′i 和 v′j 的餘弦相似度，[·]+ = max(0,·)，∥li = lj∥ 是正對的數量，即vi的ground-truth標簽li和vj的ground-truth標簽lj相同； β1 和 β2 是正負損失的邊際，λ 是平衡這兩個損失的權重。

在推理過程中，將測試數據的整個圖輸入到 GCN 中，得到所有頂點的增強特徵 F′ = [v′1, v′2, ···, v′N ]T ∈ RN×D′，其中 D′是每個新特徵的維度。

當頂點對的相似度分數大於預定義的閾值 θ 時，它們將被鏈接。最後，聚類是通過使用聯合查找演算法傳遞合並所有鏈接來完成的，即無等待並行演算法（Anderson & Woll，1991）。

4 項實驗

4.1 評估指標、數據集和實驗設置

Signal-Noise Rate (SNR) 和 Q-value 用於直接評估圖構建的質量，其中 SNR 是圖中正確邊數與雜訊邊數之比。 BCubed F-score FB (Bagga & Baldwin, 1998; Amigo ́ et al., 2009) 和 Pairwise F-score FP (Shi et al., 2018) 用於評估最終的聚類性能。

實驗中使用了三個數據集：MS-Celeb-1M (Guo et al., 2016; Deng et al., 2019) 是一個大規模的人臉數據集，經過數據清洗後包含 86K 身份的約 580 萬張人臉圖像。為了公平比較，我們遵循與 VE-GCN (Yang et al., 2019) 相同的協議和特徵，將數據集按身份平均分為十部分，並將第 0 部分作為訓練集，將第 1 部分到第 9 部分作為訓練集測試集。除了人臉數據，Ada-NETS 還被評估為在聚類其他對象方面的潛力。服裝數據集 DeepFashion (Liu et al., 2016) 使用與 VE-GCN (Yang et al., 2020) 相同的子集、分割設置和特徵，其中有 3,997 個類別的 25,752 張圖像用於訓練，26,960 張圖像用於測試的 3,984 個類別。 MSMT17 (Wei et al., 2018) 是目前最大的 ReID 數據集。它的圖像是在不同的天氣、光照條件和時間段下從 15 個攝像機捕獲的，這對聚類具有挑戰性。有 1,041 個人的 32,621 張圖像用於訓練，3,060 個人的 93,820 張圖像用於測試。特徵是從在訓練集上訓練的模型中獲得的（He et al., 2020）。

學習率最初是 0.01 用於訓練自適應濾波器，0.1 用於訓練具有餘弦退火的 GCN。對於 Huberloss，δ=1，β1 =0.9，β2 =1.0，對於 Hingleloss，λ=1，對於 Q 值，β=0.5。使用動量為 0.9 且權重衰減為 1e-5 的 SGD 優化器。 k 在 MS-Celeb-1M、DeepFashion 和 MSMT17 上設置為 80、5、40。實驗是使用 PyTorch (Paszke et al., 2019) 和 DGL (Wang et al., 2019a) 進行的。

4.2 方法比較

在具有不同數量未標記圖像的 MS-Celeb-1M 數據集上評估人臉聚類性能。比較方法包括經典的聚類方法 K-Means (Lloyd, 1982)、HAC (Sibson, 1973)、DBSCAN (Ester et al., 1996) 和基於圖的方法 L-GCN (Wang et al., 2019b)、DS -GCN (Yang et al., 2019)、VE-GCN (Yang et al., 2020)、DA-Net (Guo et al., 2020)、Clusformer (Nguyen et al., 2021) 和 STAR-FC (Shen等人，2021）。在本節中，為了進一步增強 GCN 的聚類性能，在訓練圖中添加了一些雜訊。表 1 中的結果表明，所提出的 Ada-NETS 在所有測試中都達到了最佳性能（θ = 0.96），在 584K 未標記數據上的 BCubed F-score 比 STAR-FC 高 1.19%，達到 91.40%。隨著未標記圖像數量的增加，所提出的 Ada-NETS 保持了優越的性能，揭示了圖構建在大規模聚類中的重要性。

為了進一步評估我們的方法在非人臉聚類任務中的泛化能力，還對 DeepFashion 和 MSMT17 進行了比較。如表 2 所示，Ada-NETS 在衣服和人物聚類任務中取得了最佳性能。與 STAR-FC 相比，衣服聚類的 Pairwise F-score 為 37.07%，達到了驚人的 39.30%，人物聚類的 Pairwise F-score 為 58.80%，達到了 64.05%。

4.3 消融研究

結構空間和自適應鄰居發現的研究 表 3 評估了結構空間和自適應鄰居發現的貢獻。將構建圖的 SNR 與 BCubed 和 Pairwise F 分數進行比較。可以觀察到，結構空間和自適應鄰居發現都有助於性能提升，其中自適應鄰居發現貢獻更大。使用這兩個組件，圖的 SNR 大大提高了 13.38 倍，聚類性能也大大提高。圖 4 中的每一行顯示了以第一張圖像作為探針的發現結果，按結構空間中的相似性排序。帶有藍色圓圈的圖像與探針具有相同的身份。它們都成功地在結構空間中獲得了比代表不同身份的紅色三角形更大的相似性。在自適應濾波器的幫助下，黃色垂直線之後的圖像被過濾掉，保持干凈和豐富的鄰居。如果沒有自適應濾波器，帶有紅色三角形的圖像將與其探頭連接，導致探頭污染。

質量標准研究 根據等式3，該標准包含一個超參數β。較小的 β 更強調精確度，更大的 β 更強調召回。我們選擇三個最常用的值 β ∈ {0.5, 1.0, 2.0} 來研究它如何影響鄰居發現和聚類。表 4 顯示了 Ada-NETS 在原始（表示為 Ori.）和結構空間（表示為 Str.）中不同 β 下的性能。 Qbefore 和 Qafter 是大小為 k 和 koff 的候選鄰居的 Q 值。 FP和FB是koff下對應的聚類性能。可以觀察到，在所有情況下，Qafter 與 Qbefore 相比都有明顯的提高。對於相同的β，結構空間比原始空間的改進更明顯。如上所述，較高的 Q 值表示更好的候選鄰居質量，例如，更多的雜訊邊緣將被消除（干凈）或更多正確的邊緣將在圖中保留（豐富）。因此，結構空間中的聚類性能也如預期的那樣高於原始空間。此外，β = 0.5 在兩個空間中均實現了最佳聚類性能，而在結構空間中的敏感度要低得多，達到 95.51% Pairwise F-score 和 94.93% BCubed F-score。這表明了特徵表示在結構空間中的魯棒性。

學習頭自適應過濾器

建議使用自適應過濾器從候選鄰居中選擇鄰居。與直接在自適應濾波器中回歸 koff 的估計方法（稱為 Ekreg）相比，還研究了其他一些估計方法： Ekcls 將 koff 估計表示為 k-

分類任務； EQseq 直接回歸所有 j 的 Q 值； EQparam 用二次曲線擬合關於 j 的 Q 值，並估計該曲線的參數。表 5 中的結果表明，估計 koff 的 Ekreg 和 Ekcls 獲得的性能明顯高於估計 koff 的 EQseq 和 EQparam

估計 Q 值。與 Ekcls 相比，Ekreg 取得了接近的結果，但需要學習的參數更少。 GAT 也通過注意力機制進行了比較以消除雜訊邊緣，但由於復雜的特徵模式而沒有獲得有競爭力的結果（Yang et al., 2020）。

對 k 的敏感性研究 圖 5 (a) 顯示了具有 k 方差的聚類性能。 「kNN」表示直接選擇最近的k個鄰居來構建圖，就像現有方法（Yang et al., 2020; Shen et al., 2021）一樣，「Structure kNN」表示在N（v）的結構空間中選擇kNN , 256)。盡管在結構空間中有所幫助，但兩種 kNN 方法都對 k 敏感，因為當 k 增加時會包含更多的雜訊邊緣。然而，所提出的 Ada-NETS 可以相對穩定地獲得良好的性能，表明我們的方法可以有效地提供干凈和豐富的鄰居來為 GCNs 構建圖。

圖嵌入的研究 在 Ada-NETS 中，GCN 模塊用於生成分布更緊湊的特徵，因此更適合聚類。十億個隨機選擇的對的 ROC 曲線如圖 5 (b) 所示。觀察到原始特徵嵌入 (OFE) 獲得了最差的 ROC 性能，而所提出的 GCN 輸出的圖嵌入 (GE) 得到了大幅增強。在自適應鄰居發現（GE + AND）的幫助下，輸出特徵更具辨別力。當發現應用在結構空間（GE + AND + SS）時，GCN 可以輸出最具區分性的特徵。通過 PCA (Pearson, 1901) 對 10 個隨機選擇的身份進行降維後嵌入的分布如圖 5 (c) 所示。可以觀察到，在圖 5（b）中，一種特徵嵌入的 ROC 性能越好，它的嵌入對於某個身份就越緊湊。有了更好的特徵嵌入，聚類可以重新開始。這些「GE + AND + SS」的判別圖嵌入被用作Ada-NETS的輸入，以獲得最終的聚類結果進行增強（θ = 0.99）。在表 6 中，將 MS-Celeb-1M 上的聚類結果與使用原始特徵嵌入的聚類結果進行了比較。據觀察，圖嵌入進一步將 Ada-NETS 從最先進的水平提高到了顯著的 93.74% 的 Pairwise F-score，在 584K 未標記數據上再次實現了近 1% 的改進。

5 結論

本文提出了一種新的 Ada-NETS 演算法來處理在基於 GCN 的人臉聚類中構建圖時的雜訊邊緣問題。在 Ada-NETS 中，首先將特徵轉換為結構空間以提高相似度度量的准確性。然後使用自適應鄰居發現方法在啟發式質量標準的指導下自適應地為所有樣本尋找鄰居。基於發現的鄰居關系，構建具有干凈和豐富邊緣的圖作為 GCN 的輸入，以獲得人臉、衣服和人物聚類任務的最新技術。

⑻ kNN（k-NearestNeighbor）演算法

參考《數據挖掘10大演算法》對kNN演算法進行基本總結，附有一個Python3的簡例。

基本思想
從訓練集中找出 k 個最接近測試對象的訓練對象，再從這 k 個對象中找出居於主導的類別，將其賦給測試對象。

定位
由於這種總體占優的決策模式，對於類域的交叉、重疊較多的或者多模型、多標簽的待分樣本集來說，kNN方法較其他方法更為適合。kNN演算法屬於有監督學習的分類演算法。

避開了兩個問題
（1）分類時對象之間不可能完全匹配（kNN方法計算的是對象之間的距離）；
（2）具有相同屬性的對象有不同的類別（kNN方法依據總體占優的類別進行決策，而不是單一對象的類別進行決策）。

需要考慮幾個關鍵要素
（1）訓練集；
（2）用於計算對象之間臨近的程度或者其他相似的指標；
（3）最近鄰的個數 k；
（4）基於 k 個最近鄰及其類別對目標對象類別進行判定的方法。

kNN方法很容易理解和實現，在一定條件下，其分類錯誤率不會超過最優貝葉斯錯誤率的兩倍。一般情況下，kNN方法的錯誤率會逐漸收斂到最優貝葉斯錯誤率，可以用作後者的近似。

基本演算法

演算法的存儲復雜度為O(n)，時間復雜度為O(n)，其中 n 為訓練對象的數量。

影響kNN演算法性能的幾個關鍵因素
（1）k 值的選擇；
如果 k 值選得過小，結果就會對雜訊點特別敏感；k 值選得過大就會使得近鄰中包含太多別的類的點。最佳 k 值的估計可以使用交叉驗證的方法。通常，使用 k=1會有一個比較好的結果（特別是對於小數據集的情況）。但是，在樣本很充足的情況下，選擇較大的 k 值可以提高抗噪能力。

（2）類別決策時的綜合方法；
對目標對象的類別進行決策，最簡單的就是使用總體占優方法（簡單投票，票數最多的一類勝出）。稍微復雜一點，考慮近鄰中每個點與目標對象的距離不同，對決策的份量進行加權考慮。

（3）距離測量標準的選擇。
距離測量的標准一般選擇 歐幾里得距離 或者 曼哈頓距離 。

簡單例子

⑼ 12 - SVM, KNN，LR, RF簡要介紹

這里接 第11篇 的介紹。

支持向量機是可對類別進行分類的有監督的學習演算法。其在樣本的特徵空間中找出間隔最大的超平面對樣本進行分類。SVM根據其學習演算法不同可劃分為線性可分SVM、線性近似可分SVM與非線性SVM。實現上述三種SVM主要依靠核函數—線性核函數、高斯核函數、多項式核函數與Sigmoid核函數，後三種核函數為非線性，一般建議使用高斯核函數。

如上圖，對於二分類，SVM需要確定一條最優直線使兩類樣本分開，在圖1-4中A可以看到有多條直線可將兩組分開，但最優的是圖1-4中B的w*x+b=0直線。對於最優直線的確定，需要使最優直線到最近點的距離最大，最近點被稱為支持向量（如圖1-4中B的紅點/圈），這里的距離是求出點到直線的距離最大，這是在二維空間，當在三維及其以上的空間時，直線變為超平面，距離則需要求點到超平面的幾何距離（Westreich et al 2010）。

SVM的優點：（1）適用各種形式的數據，如文本、圖像等；（2）泛化能力較好，即其過擬合的風險小；（3）相對較好地處理高維度數據；（4）核函數的應用使其能很好的適應各種情況。其缺點：（1）對大規模數據難以處理；（2）只依靠少數支持向量決定最終結果，如有異常值，則結果容易出現較大偏差；（3）對缺失值敏感（Westreich et al 2010）。

K最近鄰演算法是通過計算樣本特徵之間的距離，根據距離k進行分類，屬於無參數分類和回歸方法（Altman 1992）。距離k的度量可以使用閔可夫斯基距離、歐氏距離與曼哈頓距離等距離公式進行計算，一般其取20以內的正整數，較大的k取值會降低噪音對分析的影響，且一般對於二分類問題，取k為奇數將有利於判別。

閔可夫斯基距離公式為：

上述公式中，當p=2時，變為歐氏距離，當p=1時，變為曼哈頓距離（Hechenbichler and Schliep 2004）。
KNN屬於「懶惰學習」，即只是將訓練集數據儲存起來，再來新樣本時進行距離計算，根據投票結果判別新樣本屬於哪一類。例如圖1-6，藍色方框與紅色三角為已知的訓練集，當有綠色圓圈新樣本進行判別時，假設k為1，則有兩個紅色三角與一個為藍色方框參與判別，這樣投票結果為2:1，故綠色圓圈屬於紅色三角形一類；假如k為2，則有兩個紅色三角與三個為藍色方框參與判別，這樣投票結果為2:3，故綠色圓圈屬於藍色方框。所以k值需要選擇，一般是根據經驗進行設置，並且每個樣本（如紅三角）對判別決策所佔的比重也可以進行設定即為權重KNN（Hechenbichler and Schliep 2004）。

邏輯回歸是一種有監督的學習方法，其函數基本的公式：

上述公式為Sigmoid函數，圖為1-7，其輸出值在[0, 1]之間，需要選擇一個閾值，通常是0.5，當p(x) > 0.5時，x為A類，如果p(x) < 0.5時，x為B類。閾值可以調整，其代表對於這個事情的把握度，如上述的閾值為0.5，如計算的p(x1)=0.3，則有50%的把握認為x1屬於B類（Press 2013）。
LR的運算基本過程：（1）假設p(x)=1，構造sigmoid函數，即利用最大似然取對數作為誤差函數，用梯度下降求最小的誤差函數值，求出a與b；（2）根據訓練數據集多組數據，重復循環（1）n次，計算數據集梯度，更新sigmoid參數，確定最終的sigmoid函數；（3）輸入預測集數據；（4）運用最終sigmoid函數求解分類（Dreiseitl and Ohno-Machado 2002）。
LR的優點：（1）容易接收新數據，對模型更新；（2）能夠容易解決變數間的共線性問題；（3）運算速度快，適合二分類問題。其缺點：（1）適用的數據和具體場景較少；（2）不適用於樣本具有很大的特徵值（即變數過多）；（3）容易欠擬合，分類准確性較低；（4）使用前提是應變數和自變數有線性關系，只是廣義線性模型，不能處理非線性問題。

隨機森林是將多個決策樹集合在一起的一種演算法，基本單元為決策樹，並且可以用於回歸和分類（Breiman 2001, Liaw and Wiener 2002）。其名字由「隨機」與「森林」組成，「隨機」有兩個含義，一指在訓練集中隨機且有放回的抽取n個樣本進行建模，二指每個節點在特徵值M中隨機抽取k（k<M）個進行建模，且每個節點處的k應相同，這兩個隨機使該演算法不容易過擬合（Ho 1998）。「森林」即為多個決策樹組成，其要求基本同上述的決策樹，但這里的決策樹沒有剪枝的過程，讓其盡量生長（Cutler et al 2012）。其將多個決策樹組合在一起是採用集成學習方法，該演算法的中心思想是讓每個決策樹產生一個結果，再對這些結果進行統計，哪種結果數量最多，即為最終結果。

RF實現的過程（1）隨機有放回的從樣本N中選出n個子樣本；（2）每個節點在特徵值M中隨機選出k個特徵值；（3）重復第一與第二步s次，創建s個決策樹；（4）對s個決策樹結果分析，哪一類決策樹最多，則最終判別為哪一類。

RF演算法主要有兩個參數，第一個為抽取每個樣本的特徵值k，第二個為決策樹的數量。特徵值k一般建議為全部特徵值的開方（Geurts et al 2006）。在確定較優的k後，一般取決策樹數為500進行嘗試，查看隨著決策樹的數量增多，袋外錯誤率是否會穩定在一個定值，取能達到這個定值的最小決策樹數的數量。

隨機森林演算法優點：（1）能夠有效處理大數據；（2）能處理高維度變數的樣本，不需要降維；（3）能較好處理缺失值問題。其缺點：（1）不能直觀進行解釋（2）過度擬合某些具有雜訊分類。
上述的八種演算法，一般多用於二分類問題，如「有或無」與「好或壞」等，但在實際應用中也有較多的多分類問題，如彩虹可以劃分7種顏色，當判別一個新的顏色屬於這7種顏色的哪一種時，這就需要解決一個七分類問題。多分類是二分類的一個拓展，解決辦法有兩種，第一種是一對多，即先從K類中選出一種，剩餘K-1類歸為一種，這樣需要建立K個判別模型，當有新數據進行判別時，新樣本需在K個判別模型中，同時進行判別，看被判別為哪一類的可能性最大，就判別為哪類；

⑽ 機器學習中演算法的優缺點之最近鄰演算法

機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為KNN。我們在學習機器學習知識的時候一定要學習這種演算法，其實不管是什麼演算法都是有自己的優缺點的，KNN演算法也不例外，在這篇文章中我們就詳細的給大家介紹一下KNN演算法的優缺點，大家一定要好好學起來喲。
說到KNN演算法我們有必要說一下KNN演算法的主要過程，KNN演算法的主要過程有四種，第一就是計算訓練樣本和測試樣本中每個樣本點的距離，第二個步驟就是對上面所有的距離值進行排序(升序)。第三個步驟就是選前k個最小距離的樣本。第四個步驟就是根據這k個樣本的標簽進行投票，得到最後的分類類別。
那麼大家是否知道如何選擇一個最佳的K值，這取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一般來說，一個較好的K值可通過各種啟發式技術來獲取，比如說交叉驗證。另外雜訊和非相關性特徵向量的存在會使K近鄰演算法的准確性減小。近鄰演算法具有較強的一致性結果，隨著數據趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。
那麼KNN演算法的優點是什麼呢？KNN演算法的優點具體體現在六點，第一就是對數據沒有假設，准確度高，對outlier不敏感。第二就是KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練。第三就是KNN理論簡單，容易實現。第四就是理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。第五就是可用於非線性分類。第六就是訓練時間復雜度為O(n)。由此可見，KNN演算法的優點是有很多的。
那麼KNN演算法的缺點是什麼呢？這種演算法的缺點具體體現在六點，第一就是樣本不平衡時，預測偏差比較大。第二就是KNN每一次分類都會重新進行一次全局運算。第三就是k值大小的選擇沒有理論選擇最優，往往是結合K-折交叉驗證得到最優k值選擇。第四就是樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）效果差。第五就是需要大量內存。第六就是對於樣本容量大的數據集計算量比較大。
正是由於這些優點和缺點，KNN演算法應用領域比較廣泛，在文本分類、模式識別、聚類分析，多分類領域中處處有KNN演算法的身影。
在這篇文章中我們給大家介紹了很多關於KNN演算法的相關知識，通過對這些知識的理解相信大家已經知道該演算法的特點了吧，希望這篇文章能夠幫助大家更好的理解KNN演算法。