k近鄰模型(KNN)及python實現(xiàn)

1. k近鄰模型

k 近鄰法呆贿,k-nearest neighbor, k-NN,是一種基本的分類與回歸的算法唱蒸。其三大要素:k的選取臼隔、距離判別公式祈噪、分類決策.
k 近鄰法模型:
N_k(x)代表與 x 最近鄰的 k 個點的鄰域锄弱。
y = \arg \max _{c_{j}} \sum\limits_{x_j \in N_k(x)} I(y_i = c_j)

1眷射、k取值
取值小焚廊,結(jié)構(gòu)復(fù)雜知允,相似誤差小闯捎,但容易過擬合椰弊;
取值大,結(jié)構(gòu)簡單瓤鼻,相似誤差大秉版。
在應(yīng)用中,k 一般選擇較小的值茬祷,可通過交叉驗證來確定最佳的 k 值清焕。此外,k 一般取奇數(shù)祭犯,防止出現(xiàn)類別數(shù)相等的情況秸妥。

2、距離度量
一般使用歐氏距離沃粗,或者更一般的L_p距離粥惧。
L_p(x_1, x_2) = (\sum\limits_l |x_i^l - x_j^l|^p)^{1/p}

這里,l 代表特征維度.

3最盅、分類決策
多數(shù)表決突雪,即k個最近點類別多數(shù)的那個類別。

2. kd樹

kd 樹涡贱,k-dimensional tree,一種分割 k 維度數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)咏删。

創(chuàng)建kd樹
1、選擇當(dāng)前維度下數(shù)據(jù)的中位數(shù)對應(yīng)的樣本當(dāng)作父節(jié)點问词,從而饵婆,劃分剩余數(shù)據(jù)劃分到左、右子樹戏售;
2、選取當(dāng)前維度的下一個維度草穆,對左灌灾、右子樹重復(fù)操作 1。

最近鄰搜索
1悲柱、搜索目標(biāo)節(jié)點在kd 樹對應(yīng)的“最佳葉節(jié)點”锋喜。
具體是從根節(jié)點出發(fā),根據(jù)目標(biāo)節(jié)點在相應(yīng)維度下的值進(jìn)行劃分,直到劃分到葉子結(jié)點嘿般。
2段标、向上遍歷。
具體是從“最佳葉節(jié)點”出發(fā)炉奴,如果當(dāng)前點比“最佳葉節(jié)點”更靠近目標(biāo)節(jié)點逼庞,則該節(jié)點為當(dāng)前最佳點,并且檢查該節(jié)點的兄弟節(jié)點瞻赶;
直到根節(jié)點赛糟,搜索結(jié)束。

3. 實踐

3.1暴力法

使用暴力法進(jìn)行實現(xiàn)砸逊, N 個樣本璧南,D維數(shù)據(jù)建模的算法復(fù)雜度O(DN^2),因為計算距離時復(fù)雜度O(DN), 找出k個最領(lǐng)域時復(fù)雜度O(N)

from sklearn import datasets
import numpy as np
from sklearn.model_selection import train_test_split
## Example 1: iris for classification( 3 classes)
# X, y = datasets.load_iris(return_X_y=True)
# Example 2
X, y = datasets.load_breast_cancer(return_X_y=True)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# my k-NN
class KNN():
    def __init__(self,data,K=3):
        self.X = data[0]
        self.y = data[1]
        self.K = K
    def fit(self, X_test):
        diffX = np.repeat(X_test, len(self.X), axis=0) - np.tile(self.X,(len(X_test),1))
        square_diffX = (diffX**2).sum(axis=1).reshape(len(X_test),len(self.X))
        sorted_index = square_diffX.argsort()
        predict = [0 for _ in range(len(X_test))]
        for i in range(len(X_test)):
            class_count={}
            for j in range(self.K):
                vote_label = self.y[sorted_index[i][j]]
                class_count[vote_label] = class_count.get(vote_label,0) + 1
            sorted_count = sorted(class_count.items(), key=lambda x: x[1],reverse=True)
            predict[i] = sorted_count[0][0]
        return predict
    def predict(self, X_test):
        return self.fit(X_test)
    def score(self,X,y):
        y_pred = self.predict(X)
        return 1 - np.count_nonzero(y-y_pred)/len(y)

knn = KNN((X_train,y_train), K=3)
print(knn.score(X_test,y_test))

運(yùn)行結(jié)果:0.9415204678362573.
使用sklearn的API:

# sklearn API
from sklearn.neighbors import KNeighborsClassifier
neigh = KNeighborsClassifier(n_neighbors=3)
neigh.fit(X_train, y_train)
print(neigh.score(X_test,y_test))

運(yùn)行結(jié)果:0.9415204678362573
只要kNN法在實現(xiàn)上 k 的選擇师逸,以及距離的定義一致司倚,結(jié)果是完全相同的。

3.2 kd樹

定義kd 樹篓像。時間復(fù)雜度:O[D N \log (N)]动知。

# kd-tree
class KDNode:
    '''
    vaule: [X,y]
    '''
    def __init__(self, value=None, parent=None, left=None, right=None, index=None):
        self.value = value
        self.parent = parent
        self.left = left
        self.right = right 
    @property
    def brother(self):
        if not self.parent:
            bro = None
        else:
            if self.parent.left is self:
                bro = self.parent.right
            else:
                bro = self.parent.left
        return bro

class KDTree():
    def __init__(self,K=3):
        self.root = KDNode()
        self.K = K
        
    def _build(self, data, axis=0,parent=None):
        '''
        data:[X,y]
        '''
        # choose median point 
        if len(data) == 0:
            root = KDNode()
            return root
        data = np.array(sorted(data, key=lambda x:x[axis]))
        median = int(len(data)/2)
        loc = data[median]
        root = KDNode(loc,parent=parent)
        new_axis = (axis+1)%(len(data[0])-1)
        if len(data[:median,:]) == 0:
            root.left = None
        else:
            root.left = self._build(data[:median,:],axis=new_axis,parent=root)
        if len(data[median+1:,:]) == 0:
            root.right = None
        else:
            root.right = self._build(data[median+1:,:],axis=new_axis,parent=root)
        self.root = root
        return root
    
    def fit(self, X, y):
        # concat X,y
        data = np.concatenate([X, y.reshape(-1,1)],axis=1)
        root = self._build(data)
        
    def _get_eu_distance(self,arr1:np.ndarray, arr2:np.ndarray) -> float:
        return ((arr1 - arr2) ** 2).sum() ** 0.5
        
    def _search_node(self,current,point,result={},class_count={}):
        # Get max_node, max_distance.
        if not result:
            max_node = None
            max_distance = float('inf')
        else:
            # find the nearest (node, distance) tuple
            max_node, max_distance = sorted(result.items(), key=lambda n:n[1],reverse=True)[0]
        node_dist = self._get_eu_distance(current.value[:-1],point)
        if len(result) == self.K:
            if node_dist < max_distance:
                result.pop(max_node)
                result[current] = node_dist
                class_count[current.value[-1]] = class_count.get(current.value[-1],0) + 1
                class_count[max_node.value[-1]] = class_count.get(max_node.value[-1],1) - 1
        elif len(result) < self.K:
            result[current] = node_dist
            class_count[current.value[-1]] = class_count.get(current.value[-1],0) + 1
        return result,class_count
        
    def search(self,point):
        # find the point belongs to which leaf node(current).
        current = self.root
        axis = 0
        while current:
            if point[axis] < current.value[axis]:
                prev = current
                current = current.left
            else:
                prev = current
                current = current.right
            axis = (axis+1)%len(point)
        current = prev
        # search k nearest points
        result = {}
        class_count={}
        while current:
            result,class_count = self._search_node(current,point,result,class_count)
            if current.brother:
                result,class_count = self._search_node(current.brother,point,result,class_count)
            current = current.parent
        return result,class_count
        
    def predict(self,X_test):
        predict = [0 for _ in range(len(X_test))]
        for i in range(len(X_test)):
            _,class_count = self.search(X_test[i])
            sorted_count = sorted(class_count.items(), key=lambda x: x[1],reverse=True)
            predict[i] = sorted_count[0][0]
        return predict
        
    def score(self,X,y):
        y_pred = self.predict(X)
        return 1 - np.count_nonzero(y-y_pred)/len(y)
        
    def print_tree(self,X_train,y_train):  
        height = int(math.log(len(X_train))/math.log(2))
        max_width = pow(2, height)
        node_width = 2
        in_level = 1
        root = self.fit(X_train,y_train)
        from collections import deque
        q = deque()
        q.append(root)
        while q:
            count = len(q)
            width = int(max_width * node_width / in_level)
            in_level += 1
            while count>0:
                node = q.popleft()
                if node.left:
                    q.append(node.left )
                if node.right:
                    q.append(node.right)
                node_str = (str(node.value) if node else '').center(width)
                print(node_str, end=' ')
                count -= 1 
            print("\n")
kd = KDTree()
kd.fit( X_train, y_train)
print(kd.score(X_test,y_test))

運(yùn)行結(jié)果:0.9590643274853801

Q1: 為什么結(jié)果和上述暴力法的不一樣?

A1: 應(yīng)該是在向上回溯的過程遗淳,這里對每個節(jié)點的兄弟節(jié)點進(jìn)行計算距離拍柒,并且如果兄弟節(jié)點是當(dāng)前最佳節(jié)點,并沒有繼續(xù)向下搜索了屈暗。正確做法應(yīng)該是拆讯,如果當(dāng)前節(jié)點是當(dāng)前最佳點,并對兄弟節(jié)點搜索养叛,如果兄弟節(jié)點成為最佳點种呐,還得對該兄弟節(jié)點進(jìn)行向下搜索(我猜的)。

比較kd 樹和蠻力法的運(yùn)行效率
自定義樣本集

# Example 3
X, y = datasets.make_blobs(n_samples=10000, centers=3, 
n_features=3, random_state=0)

import time
# 暴力法
st = time.time()
knn = KNN((X_train,y_train), K=3)
print(knn.score(X_test,y_test))
et = time.time()
print("use", et-st)

# kd tree
st = time.time()
kd = KDTree()
kd.fit( X_train, y_train)
print(kd.score(X_test,y_test))
et = time.time()
print("use", et-st)

運(yùn)行結(jié)果:

# 暴力法
0.9993333333333333
use 2.8174679279327393
# kd tree
0.9973333333333333
use 0.7757344245910645

在精度相近下弃甥, kd-tree的運(yùn)行時間是更短的爽室。


參考:

  1. zhihu knn;
  2. 機(jī)器學(xué)習(xí)實戰(zhàn) k-近鄰算法;
  3. sklearn.neighbors.KNeighborsClassifier;
  4. sklearn Nearest Neighbor Algorithms;
  5. 百科 kd-tree;
  6. github imylu kd-tree;
  7. github python-kNN;
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市淆攻,隨后出現(xiàn)的幾起案子阔墩,更是在濱河造成了極大的恐慌,老刑警劉巖瓶珊,帶你破解...
    沈念sama閱讀 211,743評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件啸箫,死亡現(xiàn)場離奇詭異,居然都是意外死亡伞芹,警方通過查閱死者的電腦和手機(jī)忘苛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評論 3 385
  • 文/潘曉璐 我一進(jìn)店門蝉娜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人扎唾,你說我怎么就攤上這事召川。” “怎么了胸遇?”我有些...
    開封第一講書人閱讀 157,285評論 0 348
  • 文/不壞的土叔 我叫張陵荧呐,是天一觀的道長。 經(jīng)常有香客問我狐榔,道長坛增,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,485評論 1 283
  • 正文 為了忘掉前任薄腻,我火速辦了婚禮收捣,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘庵楷。我一直安慰自己罢艾,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 65,581評論 6 386
  • 文/花漫 我一把揭開白布尽纽。 她就那樣靜靜地躺著咐蚯,像睡著了一般。 火紅的嫁衣襯著肌膚如雪弄贿。 梳的紋絲不亂的頭發(fā)上春锋,一...
    開封第一講書人閱讀 49,821評論 1 290
  • 那天,我揣著相機(jī)與錄音差凹,去河邊找鬼期奔。 笑死,一個胖子當(dāng)著我的面吹牛危尿,可吹牛的內(nèi)容都是我干的呐萌。 我是一名探鬼主播,決...
    沈念sama閱讀 38,960評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼谊娇,長吁一口氣:“原來是場噩夢啊……” “哼肺孤!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起济欢,我...
    開封第一講書人閱讀 37,719評論 0 266
  • 序言:老撾萬榮一對情侶失蹤赠堵,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后法褥,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體顾腊,經(jīng)...
    沈念sama閱讀 44,186評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,516評論 2 327
  • 正文 我和宋清朗相戀三年挖胃,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,650評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡酱鸭,死狀恐怖吗垮,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情凹髓,我是刑警寧澤烁登,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布,位于F島的核電站蔚舀,受9級特大地震影響饵沧,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜赌躺,卻給世界環(huán)境...
    茶點故事閱讀 39,936評論 3 313
  • 文/蒙蒙 一狼牺、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧礼患,春花似錦是钥、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至肤粱,卻和暖如春弹囚,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背领曼。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評論 1 266
  • 我被黑心中介騙來泰國打工鸥鹉, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人悯森。 一個月前我還...
    沈念sama閱讀 46,370評論 2 360
  • 正文 我出身青樓宋舷,卻偏偏與公主長得像,于是被迫代替她去往敵國和親瓢姻。 傳聞我的和親對象是個殘疾皇子祝蝠,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,527評論 2 349