?
/*先把標(biāo)題給寫了、這樣就能經(jīng)常提醒自己*/
1. k近鄰算法
k臨近算法的過程，即對一個(gè)新的樣本，找到特征空間中與其最近的k個(gè)樣本，這k個(gè)樣本多數(shù)屬于某個(gè)類，就把這個(gè)新的樣本也歸為這個(gè)類。
算法?
輸入：訓(xùn)練數(shù)據(jù)集
其中為樣本的特征向量，為實(shí)例的類別，i=1,2,…,N；樣本特征向量x（新樣本）；
輸出：樣本x所屬的類y。
（1）根據(jù)給定的距離度量，在訓(xùn)練集T中找出與x最相鄰的k個(gè)點(diǎn)，涵蓋這k個(gè)點(diǎn)的鄰域記作；
（2）在中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定x的類別y：
??????????????????????????????????????????????????????????????????? （1）
式中I為指示函數(shù)，即當(dāng)時(shí)I為1，否則為0。
由這個(gè)簡單的算法過程可以看出來，距離的選擇、以及k的選擇都是很重要的，這恰好對應(yīng)的三個(gè)要素中的兩個(gè)，另一個(gè)為分類決策規(guī)則，一般來說是多數(shù)表決法。
?
2. k近鄰模型
k近鄰算法使用的模型實(shí)際上對應(yīng)于特征空間的劃分，模型由三個(gè)基本要素——距離度量、k值的選擇和分類決策規(guī)則決定。
距離度量
? ? ? 特征空間中倆個(gè)實(shí)例的距離是倆個(gè)實(shí)例點(diǎn)相似程度的反映，k近鄰中一般使用歐氏距離，本文中主要只介紹這一種。
設(shè)特征空間
是
維實(shí)數(shù)向量空間
，
，
,
,
的
距離定義為
?
當(dāng)p=2時(shí)，稱為歐氏距離(Euclidean distance).
==================在此吐槽一下，博客園的圖片插入好折騰人啊，已經(jīng)搞出肩周炎了,明天再繼續(xù)碼第二要素了 2014-6-30========================
舉個(gè)粟子，已知
,
，則
?的歐氏距離為
，挺容易理解的吧!
K 值的選擇
首先說明一下K值的選擇對最終的結(jié)果有很大的影響?。?！
? ? ? 如果選擇的k過小，則預(yù)測的結(jié)果對近鄰的實(shí)例點(diǎn)非常敏感，如果近鄰剛好是噪聲，則預(yù)測就會(huì)出錯(cuò)，例如k=1，很難保證最近的一個(gè)點(diǎn)就是正確的預(yù)測，亦即容易發(fā)生過擬合！如果選擇的k過大，則會(huì)忽略掉訓(xùn)練實(shí)例中的大量有用信息，例如k=N，那么無論輸入實(shí)例是什么最終的結(jié)果都將是訓(xùn)練實(shí)例中最多的類。
? ? ? 關(guān)于分類決策規(guī)則這里就不再贅述，正常情況下直接采用多數(shù)表決即可，如果覺得結(jié)果不滿意的話，可以加入各個(gè)類的先驗(yàn)概率進(jìn)去融合！
?
3. K近鄰的實(shí)現(xiàn)
該小節(jié)書本中用到了KD樹，通過構(gòu)造平衡KD樹來方便快速查找訓(xùn)練數(shù)據(jù)中離測試實(shí)例最近的點(diǎn)，不過構(gòu)造這顆樹本身是一個(gè)比較繁瑣的過程（其實(shí)是本人代碼能力實(shí)在太菜了，真的覺得把KD樹寫下來需要花太多時(shí)間了，而且KD樹中每增加一個(gè)新數(shù)據(jù)又要進(jìn)行節(jié)點(diǎn)插入操作，實(shí)在不方便，直接放棄），所以直接用最土豪的方法，時(shí)間復(fù)雜度差就差了，咱有的是CPU！??！
在這里直接套用書中例子，不過實(shí)現(xiàn)上就用其它算法了。稍等，我勒個(gè)去！書中的例子只是用于構(gòu)造KD樹的，李航兄你不厚道啊，說好的K近鄰怎么變成這樣了，不能直接引用書中例子了，自己再編一個(gè)得了。
例子：
訓(xùn)練數(shù)據(jù)集中，正樣本點(diǎn)有
，負(fù)樣本點(diǎn)有
，現(xiàn)要求判斷實(shí)例
屬于哪個(gè)類別,如下圖所示：
??????
假設(shè)取K=3，則距離
最近的3個(gè)點(diǎn)為
,按照多數(shù)表決規(guī)則可得出
應(yīng)該屬于正類。
為了表示咱們不是拍腦袋給出的結(jié)果，下面給出具體的代碼實(shí)現(xiàn)
package
org.juefan.knn;
import
java.util.ArrayList;
import
java.util.Collections;
import
java.util.Comparator;
import
java.util.HashMap;
import
java.util.Map;
import
org.juefan.basic.FileIO;
import
org.juefan.data.Data;
public
class
SimpleKnn {
public
static
final
int
K = 3
;
public
static
int
P = 2;
//
距離函數(shù)的選擇，P=2即歐氏距離
public
class
LabelDistance{
public
double
distance = 0
;
public
int
label;
public
LabelDistance(
double
d,
int
l){
distance
=
d;
label
=
l;
}
}
public
sort compare =
new
sort();
public
class
sort
implements
Comparator<LabelDistance>
{
public
int
compare(LabelDistance arg0, LabelDistance arg1) {
return
arg0.distance < arg1.distance ? -1 : 1;
//
JDK1.7的新特性，返回值必須是一對正負(fù)數(shù)
}
}
/**
* 倆個(gè)實(shí)例間的距離函數(shù)
*
@param
a
*
@param
b
*
@return
返回距離值，如果倆個(gè)實(shí)例的維度不一致則返回一個(gè)極大值
*/
public
double
getLdistance(Data a, Data b){
if
(a.x.size() !=
b.x.size())
return
Double.MAX_VALUE;
double
inner = 0
;
for
(
int
i = 0; i < P; i++
){
inner
+= Math.pow((a.x.get(i) -
b.x.get(i)) , P);
}
return
Math.pow(inner, (
double
)1/
P);
}
/**
* 計(jì)算實(shí)例與訓(xùn)練集的距離并返回最終判斷結(jié)果
*
@param
d 待判斷實(shí)例
*
@param
tran 訓(xùn)練集
*
@return
實(shí)例的判斷結(jié)果
*/
public
int
getLabelvalue(Data d, ArrayList<Data>
tran){
ArrayList
<LabelDistance> labelDistances=
new
ArrayList<>
();
Map
<Integer, Integer> map =
new
HashMap<>
();
int
label = 0
;
int
count = 0
;
for
(Data data: tran){
labelDistances.add(
new
LabelDistance(getLdistance(d, data), data.y));
}
Collections.sort(labelDistances, compare);
for
(
int
i = 0; i < K & i < labelDistances.size(); i++
){
//System.out.println(labelDistances.get(i).distance
+ "\t" +
labelDistances.get(i).label);
int
tmplabel =
labelDistances.get(i).label;
if
(map.containsKey(tmplabel)){
map.put(tmplabel, map.get(tmplabel)
+ 1
);
}
else
{
map.put(tmplabel,
1
);
}
}
for
(
int
key: map.keySet()){
if
(map.get(key) >
count){
count
=
map.get(key);
label
=
key;
}
}
return
label;
}
public
static
void
main(String[] args) {
SimpleKnn knn
=
new
SimpleKnn();
ArrayList
<Data> datas =
new
ArrayList<>
();
FileIO fileIO
=
new
FileIO();
fileIO.setFileName(
".//file//knn.txt"
);
fileIO.FileRead();
for
(String data: fileIO.fileList){
datas.add(
new
Data(data));
}
Data data
=
new
Data();
data.x.add(
2); data.x.add(1
);
System.out.println(knn.getLabelvalue(data, datas));
}
}
?
?
對代碼有興趣的可以上本人的GitHub查看： https://github.com/JueFan/StatisticsLearningMethod/
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
