數(shù)據(jù)挖掘中的KNN

  K最近鄰算法是分類問題中經(jīng)常使用的一種非參數(shù)方法。算法的思路清晰簡潔：對于待分類的樣本，找出與其最近的K個(gè)樣本（即訓(xùn)練樣本中的K個(gè)）。然后對這K個(gè)樣本進(jìn)行投票，待分樣本與多數(shù)樣本的類別一致。

 在該算法中有兩個(gè)最主要的問題：1、最近怎么評價(jià)？2、到底K等于多少？

 對于第一個(gè)問題，我們分三種情況討論：

 A.標(biāo)稱屬性：如果樣本的屬性值相同，則兩個(gè)樣本的距離為0，否則為1。舉例:有兩個(gè)樣本，其中有個(gè)屬性是性別，如果兩個(gè)樣本的性別都是男，則距離為0，若一個(gè)為男一個(gè)為女，則距離為1。

 B.序數(shù)屬性：如考慮學(xué)生的成績評定有如下的等級{poor,fair,ok,good,perfect}。我們可以這樣處理，將每個(gè)等級映射到從0開始的相繼整數(shù){poor=0,fair=1,ok=2,good=3,perfect=4}。如何兩個(gè)學(xué)生的成績分別是good和fair,我們可以定義距離distance=3-1=2。

 C.連續(xù)屬性：可以用歐氏距離來衡量√∑(〔x-y〕(x-y))。如兩個(gè)點(diǎn)（1,2）和（3,4）之間的距離distance = √((1-3)*(1-3) + (2-4)*(2-4)) = √8 = 2√2 .

 假如一個(gè)樣本中包含以上三種屬性，我們需要對各屬性做歸一化之后再求距離?；蛘呤沁x擇其他算法如決策樹、樸素貝葉斯等。

 對于第二個(gè)問題，我覺得比較好的辦法就是試探。設(shè)立一個(gè)確認(rèn)樣本集，然后試探看看選定哪個(gè)K值的效果比較好。當(dāng)然對于大規(guī)模數(shù)據(jù)這種方法可能不太行，這時(shí)工程師的經(jīng)驗(yàn)和判斷就顯得尤為重要了。很多資料建議K值在3-10之間，經(jīng)驗(yàn)顯示這樣的K值能較好的控制噪聲的干擾。

 K最近鄰算法的特點(diǎn)：a.不需要建立模型（也稱消極學(xué)習(xí)方法），但是計(jì)算開銷很大，每次判斷一個(gè)樣本都要計(jì)算該樣本到所有訓(xùn)練樣本的距離。

 b.可以生成任意形狀的邊界，而像決策樹算法只能生成線性的邊界。

 c.適當(dāng)?shù)木嚯x度量準(zhǔn)則非常重要。