機器學(xué)習算法之K近鄰算法

本文和大家分享的主要是機器學(xué)習算法中的K近鄰算法相關(guān)內(nèi)容，一起來看看吧，希望對大家學(xué)習和掌握這門算法有所幫助。

　　K近鄰算法(K-Near-Neighbor)起的名字還是很容易讓人知道它的算法原理的. 在對于分類問題上, 我們可以通過一個距離比較算法, 算出待預(yù)測的數(shù)據(jù)與已知數(shù)據(jù)之間的距離, 然后選擇距離最近的k個數(shù)據(jù), 最后再比較這K個數(shù)據(jù)里面哪個分類最多, 預(yù)測結(jié)果就是算出來的分類. 這個真的是最基本的機器學(xué)習算法了, 我們完全不需要公式就可以理解意思, 并且還能夠編寫源碼出來完成這項工作, 并不需要一些成熟的機器學(xué)習框架. 我們是自己開發(fā)的噢, 這樣才能更加深刻的理解算法。

　　當然上面提到的距離公式也有很多, 在本篇中, 我們使用歐式距離公式:

　　例如: 當我們的訓(xùn)練數(shù)據(jù)集中的特征只有兩個的時候比如下面提到的坐標點(1, 1), (2, 4) 之間的歐式距離就可以這么算:

　　如果表示三維坐標體系或者訓(xùn)練樣本中有3個特征的時候計算方式如下:

　　K近鄰算法一般的流程如下:

　　1、收集數(shù)據(jù): 可以使用任意方法2、準備數(shù)據(jù): 距離計算所需要的數(shù)值, 最好是結(jié)構(gòu)化的數(shù)據(jù)格式3、分析數(shù)據(jù): 可以使用任意方法4、訓(xùn)練數(shù)據(jù): 在KNN算法上不適用5、測試宣發(fā): 計算錯誤率6、使用算法: 使用該算法對未知數(shù)據(jù)進行預(yù)測。

　　下面我們假設(shè)一個場景, 并且在該場景下使用KNN算法來預(yù)測未知數(shù)據(jù).

　　場景一、預(yù)測某一個二維坐標位于哪個象限

　　哈哈, 可能有些人看到這個標題會忍不住大笑, 這TM還用機器學(xué)習方法? 我看(x, y)的符號就知道在哪個象限了啊. 同志, 你要知道要學(xué)習最高深的武功必須忘記前面學(xué)過的任何知識才能很快的接收新的知識噢, 想想張無忌吧~

　　當然在開始搭建模型之前, 我們還是要構(gòu)造一些數(shù)據(jù)的, 構(gòu)造的這些數(shù)據(jù)還是需要我們以前學(xué)過的知識的. 這個數(shù)據(jù)怎么生成呢? 我大概的思路是這樣的

　　1、隨機生成一堆有符號整數(shù)2、將該整數(shù)兩兩結(jié)合, 生成一個[N, 2] N行兩列的數(shù)組3、同時利用我們已知的知識,生成一個[N, 1]的分類(1象限, 2象限等等)4、編寫KNN算法, 通過傳入預(yù)測參數(shù), 來預(yù)測坐標應(yīng)該屬于哪個象限.

　　首先聲明, 我并不怎么會用Python的API, 所以要查一下Python 隨機生成數(shù)字怎么使用

　　import random

　　random.randint(-100, 100)

　　我們利用上面的代碼在區(qū)間[-100, 100]生成一個整數(shù)

　　如果想生成500個數(shù)字, 那么就需要調(diào)用該方法500次, 同時我們還不想要 x 或者 y 是 0 的數(shù)據(jù). 那么我們要怎么生成呢?

　　# _*_ coding:utf-8 _*_

　　import random

　　def generate_knn_data():

　　count = 0

　　points = []

　　while True:

　　x = random.randint(-100, 100)

　　y = random.randint(-100, 100)

　　if x != 0 and y != 0:

　　count = count + 1

　　points.append(x)

　　points.append(y)

　　if count >= 500:

　　break

　　return points

　　print(generate_knn_data())

　　現(xiàn)在我們生成了一個具有1000個非0數(shù)字的列表, 那么如何將數(shù)據(jù)整合成一個[N, 2]的數(shù)組呢? 我聽說過一個Numpy的框架能夠幫我們完成這個事情, 但是之前必須使用 pip install numpy -U來安裝該python包.

　　安裝好了之后, 我們隨便找個搜索引擎, 搜索 python list 轉(zhuǎn) numpy 數(shù)組

　　import numpy as np

　　num_list = [0, 1, 2, 3, 5]

　　num_array = np.array(num_list)

　　print(num_array)

　　我們使用上面代碼, 先將python里的List轉(zhuǎn)化為Numpy的數(shù)組, 有的人可能會說, 轉(zhuǎn)這個干嗎, 因為Numpy對于數(shù)組的操作函數(shù)比較多, 不用我們敲很多的代碼. 我們用搜索到的知識來完成我們的任務(wù).

　　# _*_ coding:utf-8 _*_

　　import random

　　import numpy as np

　　def generate_knn_data():

　　count = 0

　　points = []

　　while True:

　　x = random.randint(-100, 100)

　　y = random.randint(-100, 100)

　　if x != 0 and y != 0:

　　count = count + 1

　　points.append(x)

　　points.append(y)

　　if count >= 500:

　　break

　　return points

　　num_array = np.array(generate_knn_data())

　　print(num_array)

　　通過上面的代碼, 我們可以得到一個numpy的數(shù)組了, 后面就更加方便我們操作了, 首先 我們需要將numpy一維數(shù)組轉(zhuǎn)變?yōu)槎S數(shù)組

　　同時對各個訓(xùn)練數(shù)據(jù)進行標簽

　　//將數(shù)據(jù)轉(zhuǎn)為二維數(shù)組

　　train_data = np.array(generate_knn_data()).reshape((-1, 2))

　　print(train_data)

　　def label(item):

　　if item[0] > 0 and item[1] > 0:

　　return 1

　　elif item[0] > 0 and item[1] < 0:

　　return 4

　　elif item[0] < 0 and item[1] > 0:

　　return 2

　　else:

　　return 3

　　labels = np.array(list(map(label, train_data)))

　　//對各個數(shù)據(jù)分別打標簽

　　print(labels)

　　后面我們需要封裝一下我們的函數(shù), 最終得到的結(jié)果如下:

　　# _*_ coding:utf-8 _*_

　　import randomimport numpy as npimport operator

　　def generate_points_data():

　　count = 0

　　points = []

　　while True:

　　x = random.randint(-100, 100)

　　y = random.randint(-100, 100)

　　if x != 0 and y != 0:

　　count = count + 1

　　points.append(x)

　　points.append(y)

　　if count >= 500:

　　break

　　return np.array(points).reshape((-1, 2))

　　def generate_labels_data(points):

　　def label_lambda(item):

　　if item[0] > 0 and item[1] > 0:

　　return 1

　　elif item[0] > 0 and item[1] < 0:

　　return 4

　　elif item[0] < 0 and item[1] > 0:

　　return 2

　　else:

　　return 3

　　return np.array(list(map(label_lambda, points)))

　　points = generate_points_data()

　　labels = generate_labels_data(points)

　　在開始開發(fā)KNN之前, 我們學(xué)習一個numpy的高級函數(shù)用法(對于我來說),快速生成多行相同的元素

　　//該numpy的tile函數(shù)可以生成一個2行2列的元素都是[10, 30]的數(shù)據(jù)

　　extend = np.tile([10, 30], (2, 1))

　　這樣我們就可以根據(jù)tile函數(shù)來快速完成歐式距離的計算

　　def predict(input_data):

　　train_data_size = points.shape[0]

　　extend_input_data = np.tile(input_data, (train_data_size, 1))

　　minus_result = extend_input_data - points

　　square_result = np.power(minus_result, 2)

　　add_result = np.sum(square_result, axis=1)

　　distances = np.sqrt(add_result)

　　sorted_distance = distances.argsort()

　　counter = {}

　　for index in range(10):

　　label_index = sorted_distance[index]

　　label = labels[label_index]

　　if label in counter:

　　counter[label] += 1

　　else:

　　counter[label] = 1

　　sorted_classes = sorted(counter.items(), key=operator.itemgetter(1), reverse=True)

　　return sorted_classes[0][0]

　　print(predict([-11, 30]))

　　通過上面的代碼, 我們就完成了歐式距離的5-NN算法以及最后的統(tǒng)計結(jié)果匯總, 得到最終的預(yù)測分類, 完整的代碼如下:

　　# _*_ coding:utf-8 _*_

　　import randomimport numpy as npimport operator

　　def generate_points_data():

　　count = 0

　　points = []

　　while True:

　　x = random.randint(-100, 100)

　　y = random.randint(-100, 100)

　　if x != 0 and y != 0:

　　count = count + 1

　　points.append(x)

　　points.append(y)

　　if count >= 500:

　　break

　　return np.array(points).reshape((-1, 2))

　　def generate_labels_data(points):

　　def label_lambda(item):

　　if item[0] > 0 and item[1] > 0:

　　return 1

　　elif item[0] > 0 and item[1] < 0:

　　return 4

　　elif item[0] < 0 and item[1] > 0:

　　return 2

　　else:

　　return 3

　　return np.array(list(map(label_lambda, points)))

　　points = generate_points_data()

　　labels = generate_labels_data(points)

　　def predict(input_data):

　　train_data_size = points.shape[0]

　　extend_input_data = np.tile(input_data, (train_data_size, 1))

　　minus_result = extend_input_data - points

　　square_result = np.power(minus_result, 2)

　　add_result = np.sum(square_result, axis=1)

　　distances = np.sqrt(add_result)

　　sorted_distance = distances.argsort()

　　counter = {}

　　for index in range(10):

　　label_index = sorted_distance[index]

　　label = labels[label_index]

　　if label in counter:

　　counter[label] += 1

　　else:

　　counter[label] = 1

　　sorted_classes = sorted(counter.items(), key=operator.itemgetter(1), reverse=True)

　　return sorted_classes[0][0]

　　print(predict([-11, 30]))

 

 

來源：Terry