K-近鄰算法目錄1概述2K-近鄰算法的Python實(shí)現(xiàn)3Kd樹(shù)4樣本實(shí)驗(yàn)PARTONE01概述概述k-近鄰算法(k-NearestNeighbouralgorithm)，又稱為KNN算法，是數(shù)據(jù)挖掘技術(shù)中原理最簡(jiǎn)單的算法。KNN的工作原理:給定一個(gè)已知標(biāo)簽類別的訓(xùn)練數(shù)據(jù)集，輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后，在訓(xùn)練數(shù)據(jù)集中找到與新數(shù)據(jù)最鄰近的k個(gè)實(shí)例，如果這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類別，那么新數(shù)據(jù)就屬于這個(gè)類別?？梢院?jiǎn)單理解為:由那些離X最近的k個(gè)點(diǎn)來(lái)投票決定X歸為哪一類。概述圖中有紅色三角和藍(lán)色方塊兩種類別，我們現(xiàn)在需要判斷綠色圓點(diǎn)屬于哪種類別當(dāng)k=3時(shí)，綠色圓點(diǎn)屬于紅色三角這種類別;當(dāng)k=5時(shí)，綠色圓點(diǎn)屬于藍(lán)色方塊這種類別。PARTONE02K-近鄰算法的Python實(shí)現(xiàn)K-近鄰算法的Python實(shí)現(xiàn)1構(gòu)建已經(jīng)分類好的原始數(shù)據(jù)集為了方便驗(yàn)證，這里使用python的字典dict構(gòu)建數(shù)據(jù)集，然后再將其轉(zhuǎn)化成DataFrame格式。importpandasaspdrowdata={'電影名稱':['無(wú)問(wèn)西東','后來(lái)的我們','前任3','紅海行動(dòng)','唐人街探案'，'戰(zhàn)狼2']，'打斗鏡頭':[1,5,12,108,112,115]，'接吻鏡頭':[101,89,97,5,9,8]，'電影類型':['愛(ài)情片','愛(ài)情片'，'愛(ài)情片','動(dòng)作片'，'動(dòng)作片'，'動(dòng)作片']}movie_data=pd.DataFrame(rowdata)movie_dataK-近鄰算法的Python實(shí)現(xiàn)⒉計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離new_data=[24,67]dist=list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)dist3.將距離升序排列，然后選取距離最小的k個(gè)點(diǎn)dist_1=pd.DataFrame({'dist':dist，'labels':(movie_data.iloc[:6，3])3)dr=dist_1.sort_values(by='dist')[:4]drK-近鄰算法的Python實(shí)現(xiàn)4.確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率re=dr.1oc[:,'1abels'].value_counts(）re5.選擇頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)類別result=[]result.append(re.index[0])resultK-近鄰算法的Python實(shí)現(xiàn)封裝函數(shù)importpandasaspd"""函數(shù)功能:KNN分類器參數(shù)說(shuō)明:new_data:需要預(yù)測(cè)分類的數(shù)據(jù)集dataset:已知分類標(biāo)簽的數(shù)據(jù)集（訓(xùn)練集)k:k-近鄰算法參數(shù)，選擇距離最小的k個(gè)點(diǎn)返回:result:分類結(jié)果....defc1assifyo(inx,dataset,k):result=[]dist=list((((dataset.iloc[:,1:3]-inX)**2).sum(1))**0.5)dist_l=pd.DataFrame({'dist':dist,'1abe1s':(dataset.iloc[:，3])3)dr=dist_1.sort_values(by='dist')[:k]re=dr.loc[:，'7abels'].value_counts(resu1t.append(re.index[0])returnresultK-近鄰算法的Python實(shí)現(xiàn)測(cè)試函數(shù)運(yùn)行結(jié)果這就是我們使用k-近鄰算法構(gòu)建的一個(gè)分類器，根據(jù)我們的"經(jīng)驗(yàn)′可以看出，分類器給的答案還是比較符合我們的預(yù)期的。學(xué)習(xí)到這里，有人可能會(huì)問(wèn):"分類器何種情況下會(huì)出錯(cuò)?“或者"分類器給出的答案是否永遠(yuǎn)都正確?“答案一定是否定的，分類器并不會(huì)得到百分百正確的結(jié)果，我們可以使用很多種方法來(lái)驗(yàn)證分類器的準(zhǔn)確率。此外，分類器的性能也會(huì)受到很多因素的影響，比如k的取值就在很大程度上影響了分類器的預(yù)測(cè)結(jié)果，還有分類器的設(shè)置、原始數(shù)據(jù)集等等。為了測(cè)試分類器的效果，我們可以把原始數(shù)據(jù)集分為兩部分，一部分用來(lái)訓(xùn)練算法（稱為訓(xùn)練集一部分用來(lái)測(cè)試算法的準(zhǔn)確率（稱為測(cè)試集)。同時(shí)，我們不難發(fā)現(xiàn)，k-近鄰算法沒(méi)有進(jìn)行數(shù)據(jù)的訓(xùn)練，直接使用未知的數(shù)據(jù)與已知的數(shù)據(jù)進(jìn)行比較，得到結(jié)果。因此，可以說(shuō)，k-近鄰算法不具有顯式的學(xué)習(xí)過(guò)程。PARTONE03Kd樹(shù)Kd樹(shù)1.實(shí)現(xiàn)k近鄰法時(shí)，主要考慮的問(wèn)題是:如何對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行快速k近鄰搜索。⒉.最簡(jiǎn)單的實(shí)現(xiàn)方法:線性掃描。此時(shí)要計(jì)算輸入樣本與每個(gè)訓(xùn)練樣本的距離。當(dāng)訓(xùn)練集很大時(shí)，計(jì)算非常耗時(shí)。解決辦法是:使用kd樹(shù)來(lái)提高k近鄰搜索的效率。3.kd樹(shù)是一種對(duì)k維空間中的樣本點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)型數(shù)據(jù)結(jié)構(gòu)。它是二叉樹(shù)，表示對(duì)k維空間的一個(gè)劃分。4.構(gòu)造kd樹(shù)的過(guò)程相當(dāng)于不斷的用垂直于坐標(biāo)軸的超平面將k維空間切分的過(guò)程。kd樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域。簡(jiǎn)述Kd樹(shù)Kd樹(shù)算法構(gòu)建Kd樹(shù)Kd樹(shù)搜索算法Kd樹(shù)通常最近鄰搜索只需要