k近鄰（k-nearest neighbor，k-nn）是一種基本的、有監督學習的分類方法，於2023年由cover和hart提出，其用於判斷某個物件的類別。k近鄰的輸入為物件特徵向量，對應於特徵空間上的點；輸出為物件的類別。
k近鄰演算法例項引入：
圖1.1 k近鄰例項
如上圖所示，有兩類不同的樣本資料，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所示的資料則是待分類的資料。也就是說，現在，我們不知道中間那個綠色的資料是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。
所謂物以類聚，人以群分，判別乙個人是乙個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手。要判別上圖中那個綠色的圓是屬於哪一類資料，只需根據它周圍的鄰居即可。但一次性看多少個鄰居呢？
從上圖中，你還能看到：
如果k=3，綠色圓點的最近的3個鄰居（歐式距離）是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。
如果k=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。
上面這個小例子基本上體現了k近鄰演算法的三個基本要素：確定度量方式（歐式距離）、選著k值（2 or 3）、分類決策規則（少數服從多數）。
下面，給出k近鄰演算法的數學表述：
輸入：訓練資料集
其中，為例項的特徵向量，為例項的類別，;例項特徵向量;
輸出：例項所屬的類。
（1）根據給定的距離度量，在訓練集t中找出與x最鄰近的k個點，涵蓋這k個點的x的鄰域記作；
（2）在中根據分類決策規則（如多數表決）決定x的類別y：
1-1）
其中，為指示函式，即當時為1,否則為0。
k近鄰的特殊情況是k=1的情形，稱為最近鄰演算法，對於輸入的物件（特徵向量）x，最近鄰法將訓練資料集中於x最近鄰點所屬的類作為x的類。
建立數學模型的過程實質就是確定三個基本要素的過程。
樣本空間（特徵空間）中兩個物件的距離是它們相似程度的量化反映。k近鄰模型的特徵空間可被抽象為n維的向量空間r，現在兩個物件之間的距離就可轉化為兩個向量之間的距離，這樣研究起來就方便多了。在k近鄰模型中，計算向量之間距離的公式列舉如下：
（1） 歐式距離1-2）
（2）曼哈頓距離1-3）
（3）切比雪夫距離1-4）
（4）閔可夫斯基距離1-5）
特點：為綜合性的公式 。
（5）馬氏距離1-6）
特點：可排除物件間的相關性。
（6）相關距離1-7）
（7）夾角余弦距離和tonimoto係數：
（i）夾角余弦距離1-8）
（ii）tonimoto係數（夾角余弦的改進1-9）
下面給出計算歐式距離的c/c++ **：
//計算歐氏距離
double euclideandistance(const vector& v1, const vector& v2)
選擇較小的k值，近似誤差會減小，估計誤差會增大，意味著整體模型變得複雜，容易發生過擬合；
選擇較大的k值，減少估計誤差，近似誤差會增大，k值的增大就意味著整體的模型變得簡單。
在實際應用中，k值一般取乙個比較小的數值，例如採用交叉驗證法（一部分樣本做訓練集，一部分做測試集）來選擇最優的k值。
（1）多數表決
k近鄰法中的分類決策規則往往是多數表決，即由輸入物件的k個鄰近中的多數類決定輸入物件的類，通俗點就是「少數服從多數」。
（2）誤分類率
誤分類率即對輸入物件出現錯誤分類的概率。其數學表示如下：
對給定的例項， 其最近鄰的k個訓練例項點構成集合.如果涵蓋的區域的類別是，那麼誤分類率是
1-10）
要使誤分類率最小即經驗風險最小，就要使最大，所以多數表決規則等價於經驗風險最小化.
在實現k近鄰法時，主要考慮的問題是如何對訓練資料進行快速k近鄰捜索。
k近鄰法最簡單的實現方法是線性掃瞄法（linear scan)。即計算輸入物件與每乙個訓練物件之間的距離，然而當訓練集很大時，計算非常耗時，這種方法是不可行的.
為了提高k近鄰搜尋的效率，我們可以構建資料的索引（因為實際資料一般都會呈現簇狀的聚類形態，因此我們想到建立資料索引，然後再進行快速匹配）。索引樹是一種樹結構索引方法，其基本思想是對搜尋空間進行層次劃分。根據劃分的空間是否有混疊可以分為clipping和overlapping兩種。
前者劃分空間沒有重疊，其代表就是kd樹；後者劃分空間相互有交疊，其代表為r樹。下面主要介紹其中的kd樹（kd tree)方法。
該方法來自史丹福大學的jon louis bentley在acm雜誌上發表的一篇**：multidi-mensional binary search trees used for associative searching ，這篇**中正式提出kd樹，並闡述的了kd樹的構建等（此時的k與knn中的k含義是不同的）。
kd樹是一種對k維空間中的例項點進行儲存以便對其進行快速檢索的樹形資料結構。kd樹是二叉樹，表示對k維空間的乙個劃分（partition)。構造k樹相當於不斷地用垂直於座標軸的超平面將k維空間切分，構成一系列的k維超矩形區域。
kd樹的每個結點對應於乙個k維超矩形區域。
構造kd樹的方法如下：構造根結點，使根結點對應於k維空間中包含所有物件點的超矩形區域；通過下面的遞迴方法，不斷地對k維空間進行切分，生成子結點。在超矩形區域（結點）上選擇乙個座標軸和在此座標軸上的乙個切分點，確定乙個超平面，這個超平面經過選定的切分點並垂直於選定的座標軸，將當前超矩形區域切分為左右兩個子區域（子結點）：
這時，物件被分到兩個子區域。重複這個過程直到子區域內沒有物件時終止（終止時的結點為葉結點)。在此過程中，將所有物件儲存在相應的結點上。
對於三維的情形，kd樹對空間的劃分，如下圖所示：
圖1.2 三維kd樹
通常，依次選擇座標軸對空間切分，選擇訓練物件點在選定座標軸上的中位數為切分點，這樣得到的kd樹是平衡的。在確定座標軸時，選著當前方差最大的效果較好，因為此時區分度最大。注意，平衡的樹搜尋時的效率未必是最優的。
下面給出構造以樹的演算法（見圖1.3）：
演算法1.1 (構造平衡kd樹）
輸入：k維空間資料集，
其中輸出：kd樹。
（1）開始：構造根結點，根結點對應於包含t的k維空間的超矩形區域.
選擇為座標軸，以t中所有例項的座標的中位數為切分點，將根結點對應的超矩形區域切分為兩個子區域.切分由通過切分點並與座標軸垂直的超平面實現.
由根結點生成深度為1的左、右子結點：左子結點對應座標小於切分點的子區域，右子結點對應於座標大於切分點的子區域.
將落在切分超平面上的物件點儲存在根結點.
（2）重複：對深度為j的結點，選擇為切分的座標軸，， 以該結點的區域中所有例項的座標的中位數為切分點，將該結點對應的超矩形區域切分為兩個子區域.切分由通過切分點井與座標軸垂直的超平面實現.
機器學習演算法總結SVM
第5章支援向量機 支援向量機 support vector machine，簡稱svm 是於1995年由cortes和vapnik首先提出的，它在解決小樣本 非線性及高維模式識別中表現出許多特有的優勢，並能夠推廣應用到函式擬合等其他機器學習問題中。它通過尋求結構化風險最小來提高學習機泛化能力，實現經...
機器學習十大經典演算法簡介
不僅僅是選中的十大演算法，其實參加評選的18種演算法，實際上隨便拿出一種來都可以稱得上是經典演算法，它們在資料探勘領域都產生了極為深遠的影響。c4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是id3演算法.c4.5演算法繼承了id3演算法的優點，並在以下幾方面對id3演算法進行了...
kuka機械人培訓學習總結劉季
kuka機械人培訓學習心得體會 鄒城高階職業技術學校機械組劉季 2015年4月13日至4月23日，學校派我去山東諾博泰 參加機械人培訓活動，我們學習的內容如下 第一天，學習了機械人系統的結構和功能介紹 機械人系統資訊與應用領域山東若博泰公司的介紹，如何設計更好的機械人等。主要是認識機械人的組成部分，...