?
/*先把標題給寫了、這樣就能經常提醒自己*/
1. k近鄰算法
k臨近算法的過程，即對一個新的樣本，找到特征空間中與其最近的k個樣本，這k個樣本多數屬于某個類，就把這個新的樣本也歸為這個類。
算法?
輸入：訓練數據集
其中為樣本的特征向量，為實例的類別，i=1,2,…,N；樣本特征向量x（新樣本）；
輸出：樣本x所屬的類y。
（1）根據給定的距離度量，在訓練集T中找出與x最相鄰的k個點，涵蓋這k個點的鄰域記作；
（2）在中根據分類決策規則（如多數表決）決定x的類別y：
??????????????????????????????????????????????????????????????????? （1）
式中I為指示函數，即當時I為1，否則為0。
由這個簡單的算法過程可以看出來，距離的選擇、以及k的選擇都是很重要的，這恰好對應的三個要素中的兩個，另一個為分類決策規則，一般來說是多數表決法。
?
2. k近鄰模型
k近鄰算法使用的模型實際上對應于特征空間的劃分，模型由三個基本要素——距離度量、k值的選擇和分類決策規則決定。
距離度量
? ? ? 特征空間中倆個實例的距離是倆個實例點相似程度的反映，k近鄰中一般使用歐氏距離，本文中主要只介紹這一種。
設特征空間
是
維實數向量空間
，
，
,
,
的
距離定義為
?
當p=2時，稱為歐氏距離(Euclidean distance).
==================在此吐槽一下，博客園的圖片插入好折騰人啊，已經搞出肩周炎了,明天再繼續碼第二要素了 2014-6-30========================
舉個粟子，已知
,
，則
?的歐氏距離為
，挺容易理解的吧!
K 值的選擇
首先說明一下K值的選擇對最終的結果有很大的影響！??！
? ? ? 如果選擇的k過小，則預測的結果對近鄰的實例點非常敏感，如果近鄰剛好是噪聲，則預測就會出錯，例如k=1，很難保證最近的一個點就是正確的預測，亦即容易發生過擬合！如果選擇的k過大，則會忽略掉訓練實例中的大量有用信息，例如k=N，那么無論輸入實例是什么最終的結果都將是訓練實例中最多的類。
? ? ? 關于分類決策規則這里就不再贅述，正常情況下直接采用多數表決即可，如果覺得結果不滿意的話，可以加入各個類的先驗概率進去融合！
?
3. K近鄰的實現
該小節書本中用到了KD樹，通過構造平衡KD樹來方便快速查找訓練數據中離測試實例最近的點，不過構造這顆樹本身是一個比較繁瑣的過程（其實是本人代碼能力實在太菜了，真的覺得把KD樹寫下來需要花太多時間了，而且KD樹中每增加一個新數據又要進行節點插入操作，實在不方便，直接放棄），所以直接用最土豪的方法，時間復雜度差就差了，咱有的是CPU?。。?
在這里直接套用書中例子，不過實現上就用其它算法了。稍等，我勒個去！書中的例子只是用于構造KD樹的，李航兄你不厚道啊，說好的K近鄰怎么變成這樣了，不能直接引用書中例子了，自己再編一個得了。
例子：
訓練數據集中，正樣本點有
，負樣本點有
，現要求判斷實例
屬于哪個類別,如下圖所示：
??????
假設取K=3，則距離
最近的3個點為
,按照多數表決規則可得出
應該屬于正類。
為了表示咱們不是拍腦袋給出的結果，下面給出具體的代碼實現
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;
//
距離函數的選擇，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的新特性，返回值必須是一對正負數
}
}
/**
* 倆個實例間的距離函數
*
@param
a
*
@param
b
*
@return
返回距離值，如果倆個實例的維度不一致則返回一個極大值
*/
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);
}
/**
* 計算實例與訓練集的距離并返回最終判斷結果
*
@param
d 待判斷實例
*
@param
tran 訓練集
*
@return
實例的判斷結果
*/
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/
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
