App下載

Python機(jī)器學(xué)習(xí)之KNN近鄰算法

請把小喵還給我 2021-08-13 14:39:55 瀏覽數(shù) (1790)
反饋

在python機(jī)器學(xué)習(xí)中,KNN近鄰算法是相當(dāng)出名的存在。通過測量不同特征值之間的距離方法來進(jìn)行分類,使它擁有了精度高,對異常值不敏感的優(yōu)秀特點。那么這么出名的算法究竟是如何實現(xiàn)的呢?今天我們就從源代碼來分析一下KNN近鄰算法的實現(xiàn)。

一、KNN概述

簡單來說,K-近鄰算法采用測量不同特征值之間的距離方法進(jìn)行分類

優(yōu)點:精度高、對異常值不敏感、無數(shù)據(jù)輸入假定
缺點:計算復(fù)雜度高、空間復(fù)雜度高
適用數(shù)據(jù)范圍:數(shù)值型和標(biāo)稱2型

工作原理:存在一個樣本數(shù)據(jù)集合,也稱為訓(xùn)練樣本集,并且樣本集中每個數(shù)據(jù)都存在標(biāo)簽,即我們知道樣本集中每一個數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系(訓(xùn)練集)。輸入沒有標(biāo)簽的新數(shù)據(jù)之后,將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較,然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽(測試集)。一般來說,我們只選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù),這就是k-近鄰算法中k的出處。(通常k不大于20)

二、使用Python導(dǎo)入數(shù)據(jù)

我們先寫入一段代碼

from numpy import *		# 導(dǎo)入numpy模塊
import operator		# 導(dǎo)入operator模塊
def createDataSet():		# 創(chuàng)建數(shù)據(jù)集函數(shù)
	# 構(gòu)建一個數(shù)組存放特征值
    group = array(
        [[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]
    )
    # 構(gòu)建一個數(shù)組存放目標(biāo)值
    labels = ['A', 'A', 'B', 'B']
    return group, labels

此處稍微介紹一下numpy這個包吧

三、numpy.array()

NumPy的主要對象是同種元素的多維數(shù)組。這是一個所有的元素都是一種類型、通過一個正整數(shù)元組索引的元素表格(通常是元素是數(shù)字)。
在NumPy中維度(dimensions)叫做軸(axes),軸的個數(shù)叫做秩(rank,但是和線性代數(shù)中的秩不是一樣的,在用python求線代中的秩中,我們用numpy包中的linalg.matrix_rank方法計算矩陣的秩
線性代數(shù)中秩的定義:設(shè)在矩陣A中有一個不等于0的r階子式D,且所有r+1階子式(如果存在的話)全等于0,那末D稱為矩陣A的最高階非零子式,數(shù)r稱為矩陣A的秩,記作R(A)。

四、實施KNN分類算法

依照KNN算法,我們依次來

先準(zhǔn)備好四個需要的數(shù)據(jù)

  • inX:用于分類的輸入向量inX
  • dataSet:輸入的訓(xùn)練樣本集dataSet
  • labels:標(biāo)簽向量labels(元素數(shù)目和矩陣dataSet的行數(shù)相同)
  • k:選擇最近鄰居的數(shù)目

五、計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離

使用歐式距離:

歐式距離公式

六、完整代碼

# 返回矩陣的行數(shù)
dataSetSize = dataSet.shape[0]	
# 列數(shù)不變,行數(shù)變成dataSetSize列
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5

第一行

# 返回矩陣的行數(shù)
dataSetSize = dataSet.shape[0]	
# 以第一步的數(shù)據(jù)為例
answer:4		# 4行

第二行

inX = [1. , 0.]
# 列數(shù)不變,行數(shù)變成dataSetSize列
diffMat = tile(inX, (dataSetSize, 1)) - dataSet

# tile(inX, (dataSetSize, 1))
inX = [
	[1. , 0.],
	[1. , 0.],
	[1. , 0.],
	[1. , 0.]
]
# inX - dataSet兩個矩陣相減(行列相等相加相減才有意義)
dataSet = [
		[1. , 1.1],
        [1. , 1. ],
        [0. , 0. ],
        [0. , 0.1]
]
diffMat = [
	[0. , -1.1],
	[0. , -1.],
	[1. , 0.],
	[1. , -0.1]
]

第三行

# 求平方差
sqDiffMat = diffMat * 2

第四行

# 計算矩陣中每一行元素之和
# 此時會形成一個多行1列的矩陣
sqDistances = sqDiffMat.sum(axis=1)

第五行

# 開根號
distances = sqDistances**0.5

按照距離遞增次序排序

# 對數(shù)組進(jìn)行排序
sortedDistIndicies = distances.argsort()

選擇與當(dāng)前點距離最小的k個點

classCount = {}		# 新建一個字典
# 確定前k個距離最小元素所在的主要分類
for i in range(k):
	# voteIlabel的取值是labels中sortedDistIndicies[i]的位置
	voteIlabel = labels[sortedDistIndicies[i]]
	classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

確定前k個點所在類別的出現(xiàn)概率

# 排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

###11# 返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類

return sortedClassCount[0][0]

剛剛試一試C++的版本…小心,救命

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
int sum_vector(std::vector<int>& v) {
	int sum = 0;
	for (int i = 0; i < v.size(); ++i) {
		sum = v[i] + sum;
	}
	return sum;
}
int knn(int k) {
	using std::cout;
	using std::endl;
	using std::vector;
	vector<vector<int>> x;	
	vector<int> x_sample = {2, 3, 4};	
	for (int i = 0; i < 4; ++i) {
		x.push_back(x_sample);
	}
	vector<int> y = {1, 1, 1, 1};
	int dataSetSize = x.size();		

	vector<int> x_test = {4, 3, 4};
	vector<vector<int>> x_test_matrix;
	for (int i = 0; i < dataSetSize; ++i) {
		x_test_matrix.push_back(x_test);
	}
	vector<int> v_total;
	for (int i = 0; i < dataSetSize; ++i) {
		for (int j = 0; j < x_test_matrix[i].size(); ++j) {
			x_test_matrix[i][j] = x_test_matrix[i][j] - x[i][j];
			x_test_matrix[i][j] = x_test_matrix[i][j] * 2;
		}
		int sum_vec = sum_vector(x_test_matrix[i]);
		v_total.push_back(sqrt(sum_vec));
	}
	sort(v_total.begin(), v_total.end());
	std::map<int, int> mp;
	for (int i = 0; i < k; ++i) {
		int label = y[v_total[i]];
		mp[label] += 1;
	}
	int max_end_result = 0;
	for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) {
		if (it->first > max_end_result) {
			max_end_result = it->first;
		}
	}
	return max_end_result;
}
int main() {
	int k = 12;
	int value = knn(k);
	std::cout << "result:
" << std::endl;
	return 0;
}

七、數(shù)據(jù)處理、分析、測試

處理excel和txt數(shù)據(jù)

excel數(shù)據(jù)是矩陣數(shù)據(jù),可直接使用,在此不做處理。

文本txt數(shù)據(jù)需要一些數(shù)據(jù)處理

def file2matrix(filename):
	fr = open(filename)
	# 讀取行數(shù)據(jù)直到尾部
	arrayOLines = fr.readlines()
	# 獲取行數(shù)
	numberOfLines = len(arrayOLines)
	# 創(chuàng)建返回shape為(numberOfLines, 3)numpy矩陣
	returnMat = zeros((numberOfLines, 3))
	classLabelVector = []
	index = 0
	for line in arrayOLines:
		# 去除首尾的回車符
		line = line.strip()
		# 以tab字符'	'為符號進(jìn)行分割字符串
		listFromLine = line.split('	')
		# 選取前3個元素,把他們存儲到特征矩陣中
		returnMat[index, :] = listFromLine[0: 3]
		# 把目標(biāo)變量放到目標(biāo)數(shù)組中
		classLabelVector.append(int(listFromLine[-1]))
		index += 1
	return returnMat, classLabelVector

數(shù)據(jù)歸一化和標(biāo)準(zhǔn)化

在數(shù)值當(dāng)中,會有一些數(shù)據(jù)大小參差不齊,嚴(yán)重影響數(shù)據(jù)的真實性,因此,對數(shù)據(jù)進(jìn)行歸一化和標(biāo)準(zhǔn)化是使得數(shù)據(jù)取值在一定的區(qū)間,具有更好的擬合度。

例如歸一化就是將數(shù)據(jù)取值范圍處理為0到1或者-1到1之間

# max:最大特征值
# min:最小特征值
newValue = (oldValue - min)/(max-min)

寫個函數(shù)

def autoNorm(dataSet):
	# min(0)返回該矩陣中每一列的最小值
	minVals = dataSet.min(0)
	# max(0)返回該矩陣中每一列的最大值
	maxVals = dataSet.max(0)
	# 求出極值
	ranges = maxVals - minVals
	# 創(chuàng)建一個相同行列的0矩陣
	normDataSet = zeros(shape(dataSet))
	# 得到行數(shù)
	m = dataSet.shape[0]
	# 得到一個原矩陣減去m倍行1倍列的minVals
	normDataSet = dataSet - tile(minVlas, (m,1))
	# 特征值相除
	normDataSet = normDataSet/tile(ranges, (m, 1))
	return normDataSet, ranges, minVals

歸一化的缺點:如果異常值就是最大值或者最小值,那么歸一化也就沒有了保證(穩(wěn)定性較差,只適合傳統(tǒng)精確小數(shù)據(jù)場景)

標(biāo)準(zhǔn)化可查

八、鳶尾花數(shù)據(jù)測試

既然已經(jīng)了解其內(nèi)置的算法了,那么便調(diào)庫來寫一個吧

from sklearn.datasets import load_iris      # 導(dǎo)入內(nèi)置數(shù)據(jù)集
from sklearn.model_selection import train_test_split        # 提供數(shù)據(jù)集分類方法
from sklearn.preprocessing import StandardScaler        # 標(biāo)準(zhǔn)化
from sklearn.neighbors import KNeighborsClassifier      # KNN


def knn_iris():
    # 獲得鳶尾花數(shù)據(jù)集
    iris = load_iris()
    # 獲取數(shù)據(jù)集
    # random_state為隨機(jī)數(shù)種子,一個數(shù)據(jù)集中相等的行不能大于6
    x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=6)
    # 特征工程:標(biāo)準(zhǔn)化
    transfer = StandardScaler()
    # 訓(xùn)練集標(biāo)準(zhǔn)化
    x_train = transfer.fit_transform(x_train)
    # 測試集標(biāo)準(zhǔn)化
    x_test = transfer.transform(x_test)
    # 設(shè)置近鄰個數(shù)
    estimator = KNeighborsClassifier(n_neighbors=3)
    # 訓(xùn)練集測試形成模型
    estimator.fit(x_train, y_train)

    # 模型預(yù)估
    # 根據(jù)預(yù)測特征值得出預(yù)測目標(biāo)值
    y_predict = estimator.predict(x_test)
    print("y_predict: 
", y_predict)
    # 得出預(yù)測目標(biāo)值和真實目標(biāo)值之間是否相等
    print("直接比對真實值和預(yù)測值:
", y_test == y_predict)
    # 計算準(zhǔn)確率
    score = estimator.score(x_test, y_test)
    print("準(zhǔn)確率為:
", score)


def main():
    knn_iris()


if __name__ == '__main__':
    main()

九、RESULT

運算結(jié)果

到此這篇Python機(jī)器學(xué)習(xí)之KNN近鄰算法的文章就介紹到這了,更多機(jī)器學(xué)習(xí)的內(nèi)容請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章。

0 人點贊