（一）算法思想：
? ? ?自然語言描述：給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實例，在訓(xùn)練數(shù)據(jù)集上找到與該實例最鄰近的k個實例，這k個實例的多數(shù)屬于哪個類，就將輸入劃分為該類。
? ? ?形式化描述：對于給定的輸入x，根據(jù)給定的距離度量，算出包含k個訓(xùn)練樣本的鄰域Nk，然后在Nk內(nèi)進行決策，即y=argmax Σi（i為指示函數(shù)，eg（0,0,1））
（二）k鄰近模型
? ? ?1.模型：
? ? ? ? ? cell：特征空間中，每一個訓(xùn)練樣本看做xi，距離該點比其他點更近的所有點組成的區(qū)域，叫做單元cell
? ? ? ? ? 類標記：yi則是xi的cell中的類標記class label
? ? ?2.距離度量：
? ? ? ? ? 距離度量反映了兩個點的相似程度，一般采用歐式距離或者曼哈頓距離。
? ? ? ? ? p=1：曼哈頓距離
? ? ? ? ? p=2：歐式距離
? ? ?3.k值的選擇：
? ? ? ? ? k值選的大：減少學(xué)習(xí)的估計誤差，但是近似誤差會增大（與樣本距離較遠，不相似的樣本會對估計產(chǎn)生影響），即模型過于簡單--欠擬合
? ? ? ? ? k值選的?。航普`差會減小，但是估計誤差會增大（如果與樣本最近的點是噪聲，則會影響預(yù)測結(jié)果），即模型過于復(fù)雜敏感--過擬合
? ? ? ? ? 現(xiàn)實應(yīng)用中一般使用較小的k值，然后使用交叉驗證的方式選取最優(yōu)k
? ? ?4.分類決策的規(guī)則：
? ? ? ? ? 多數(shù)表決規(guī)則（majority voting rule）：k個鄰近實例中類別最多的類最為輸出。
? ? ? ? ? 損失函數(shù)：0-1損失函數(shù)，使損失函數(shù)最小，則應(yīng)選擇所屬類別最多的類
（三）k鄰近算法的實現(xiàn)---kd樹
?????1.為什么構(gòu)造kd樹：若樣本龐大，線性的計算所有的訓(xùn)練樣本與輸入的距離非常耗時，不可取。于是選擇特殊的數(shù)據(jù)結(jié)構(gòu)對訓(xùn)練樣本進行存儲，方便計算距離。
? ? ?2.構(gòu)造kd樹：
? ? ? ? ? （1）構(gòu)造根節(jié)點，選擇x1特征為坐標軸，選擇x1特征的中位數(shù)，將該樣本作為切分點，構(gòu)造垂直于坐標軸的超平面將特征空間分為2份
? ? ? ? ? （2）對深度為j的節(jié)點，選擇j%k+1（k為特征數(shù)量）作為坐標軸，使用同樣的辦法進行劃分
? ? ? ? ? （3）重復(fù)步驟2直至劃分出的區(qū)域中沒有實例。
? ? ?3.搜索kd樹--最鄰近搜索
? ? ?1.從根節(jié)點出發(fā)，遞歸的向下訪問kd樹。若目標節(jié)點的當前維坐標小于切分點，則走左子樹，否則走右子樹。走到葉節(jié)點為當前最近節(jié)點。
? ? ?2.遞歸的向上回退，每個節(jié)點進行以下操作：
? ? （a）如果該節(jié)點距離目標節(jié)點更近，則該節(jié)點為當前最近節(jié)點。
（b）以當前的最近節(jié)點為圓心，以最近距離為圓心，判斷該圓形（實際上超過二維成為超球體）是否與分割的超平面相交。若相交，遞歸的進行最鄰近搜索；若相離，則向上回退。
? ? ?3.當退回根節(jié)點時，當前節(jié)點為最鄰近節(jié)點。
時間復(fù)雜度：如果實例點是隨機分布的，則時間復(fù)雜度是O(logN).kd樹更適用于訓(xùn)練示例遠大于空間維數(shù)的k鄰近掃描，否則幾乎接近線性時間。
