机器学习个人笔记——（一）k近邻算法

机器学习个人笔记——（一）k近邻算法

1. 监督学习和无监督学学习

机器学习：用一些训练数据，使机器能够利用它们分析和预测未知数据，机器学习中分有监督学习和无监督学习。

监督学习：根据已有的数据集，知道输入和输出结果之间的关系，从已有的训练数据集中学习出一个函数（模型参数），当新数据到来时，可以根据这个函数去预测结果。
监督学习最常见的就是：回归和分类。

回归：

想要预测房屋卖出的价格，给出一定数量的房屋数据集，包括房屋的面积等参数，且已知这些房屋的价格，通过训练数据集，得到面积等因素和价格之间的函数关系，当输入一个新的房屋面积等参数时，可输出价格预测值。

分类：

要预测一批零件是否损坏，给出一定数量的数据集，包括零件重量等参数，且已知是否损坏，通过分类器训练数据，得到各个之间的关系，输入一个新的零件的重量等参数，预测该零件是否损坏。

无监督学习：输入数据没有被标记，也没有确定的结果，不知道数据集中数据、特征之间的关系，而是要根据聚类或一定的模型得到数据之间的关系。

k均值算法
有一数据点集在二维坐标轴如图所示，他们是没有标签的

通过k均值算法（无监督学习），可得到如下分类点集，将点集分成了3个簇，即3个类别

2. k近邻算法概述

k-近邻算法属于有监督学习的一种分类算法，采用测量不同特征值之间的距离方法进行分类

工作原理：

1、存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。
2、输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后提取样本集中特征最相似数据（最近邻）的分类标签。
3、一般来说,只选择样本数据集中前k个最相似的数据，通常k是不大于20 的整数。
4、最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类

例如：

在上图中有3个已知类别（1，2，3）的数据点，黑色三角形是新的数据（即要预测的数据），取平面上离它最近的k=3个点（假设三个点如图），所取的3个点中，有2个是属于3类别，1个属于2类别，3类别数量最多，则预测的数据类别为3

1. 求距离
对训练集A中每个数据集于B点求距离，A与B的距离公式如下所示

…

其中，m为训练集个数，n为特征的个数

例如点(0,0)和点(1,2)的距离为

若数据集存在4个特征，则点(3,1,0,1)和点(1,2,1,1)的距离计算为

2. 取距离最近的k个点
对d1,d2,…dm进行从小到大排序
取距离最近的前k个点，k<=m

3.获取出现频率最高的类别
对所取得的K个点进行类别计数，
对类别进行排序，得到频率最高的类别L
B预测的类别为L

3. k近邻算法实现
k近邻算法运作流程举例：

若训练集有10个数据，每个数据有3个特征值，和一个类别标签（有2种类别1和2）

数据集：

标签向量:

测试向量为

对以上实例使用k近邻算法如下：
1. 求距离

**...**

A中的每个向量都与B向量求一次距离，得到d1~d10

2. 取距离最近的3个点
对d1,d2,…d10进行从小到大排序
得到距离最近的前3个点的下标，
假如得到了indexList=[2,0,8]，即下标为2,0,8三个点

3.获取出现频率最高的类别
对所取得的3个点进行类别计数，

因为下标 indexList=[2,0,8]
分别取标签向量中的，L[2],L[0],L[8],假设取到的类别为1,2,2
则预测结果为2

4. k近邻算法优化问题

1.数据集划分
已知包含n个数据的集合，对其使用k近邻算法，评估该算法是否有效，可将n个数据分为两个部分，训练集和测试集，一般比例为7:3。

注：
在机器学习，当涉及多个模型进行选择时，通常会将数据集划分为：训练集、交叉验证集合测试集，其中，交叉验证集的作用是对不同的模型进行性能评估，即用于筛选模型，最后再使用测试集进行测试。通常，训练集：交叉验证集：测试集=6：2：2

2. 数据归一化

假设某个数据中所包含的特征如下图

计算样本1 和样本4 之间的距离，使用距离公式

上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年
获取的飞行常客里程数对于计算结果的影响将远远大于表中其他两个特征

该样本数据，若不做特殊说明，则其三个特征的影响程度应该相等，此时，应该对样本数据进行归一化处理，将3个特征的值，统一转换为[0,1]的数。

针对上图的样本，分别对三个特征值进行归一化

1. 上图共有4个数据，每个数据3个特征，在4x3的矩阵中，求每一列的最大值maxValue，最小值minValue，
求得maxValue=[67,134000,1.1],minValue=[0,400,0.1]

2.求每一列最大值与最小值的差值ranges=maxvalue-minvalue
求得ranges=[67,133600,1]

3.对每一个数进行归一化：
data[i][j]=(data[i][j]-minValue[j])/ranges[i]
例如：
data[0][0]=0.8归一化后的数据=(0.8-0)/67=
data[0][1]=400归一化后的数据=(400-400)/133600=0
...
等等

5. 使用k - 近邻算法预测约会网站的配对类型&手写字体识别程序

import numpy as np
import operator
import random
# import matplotlib.pyplot as plt
# from os import listdirdef computDist(dataMat, inX):"""计算点向量之间距离的平方:param dataMat:大小为m*n的矩阵:param inX: 大小为1*n的行向量:return:距离平方，大小为m*1的列向量:type  dataMat: np.mat:type  inX: np.mat:rtype :np.mat样例输入:dataMat=[0,1,2],[1,1,1],[0,0,0],[0,1,0]]inX=[1,1,1]]样例输出:[[2],[0],[3],[2]]"""return np.sum(np.power((dataMat-inX), 2), axis=1)def autoNorm(dataMat):"""数据归一化,转换为[0,1]的数:param dataMat: 大小为m*n的数据矩阵，:return:大小为m*n，归一化后的矩阵，:type  dataMat:np.mat:rtype :np.mat样例输入:dataMat=[[a00,a01,...,a0n],[a10,a11,...,a1n],...,[am0,am1,...,amn,]]样例输出:[[b00,b01,...,b0n],[b10,b11,...,b1n],...,[bm0,bm1,...,bmn,]]其中:0<=b[i][j]<=1"""minVals=np.min(dataMat, axis=0)maxVals=np.max(dataMat, axis=0)ranges=maxVals-minValsnormDataSet=dataMat-minValsnormDataSet=normDataSet/rangesreturn normDataSetdef loadDataMat(filename):"""读取文件中的数据:param filename: 文件路径:return:归一化后的数据矩阵m*n, 类别标签向量1*n:type  filename:   str:rtype:np.mat,np.mat"""with open(filename, 'r') as fr:dataSet=[]labelSet=[]for line in fr:currLine=line.strip().split('t')dataSet.append(list(map(float, currLine[:-1])))labelSet.append([float(currLine[-1])])return autoNorm(np.mat(dataSet)), np.mat(labelSet)def divTrainSet_TestSet(dataMat, dataSetLabels, testRate=0.30):"""从原始数据集中划分出 训练集和测试集:param dataMat: 数据集:param dataSetLabels: 数据类别标签:param testRate: 测试集比例:return:testDataSet测试数据集 ,trainDataSet训练数据集 ,testDataSetLabels测试数据集实际类别标签 ,trainDataSetLabels训练数据类别标签 ,:type dataMat: np.mat:type dataSetLabels: np.mat:type testRate: float:rtype: np.mat, np.mat, np.mat, np.mat"""n, k = dataMat.shapetestSetCnts = int(n*testRate)testDataSet = np.zeros((testSetCnts, k))testDataSetLabels = np.zeros((1, testSetCnts))indexList = list(range(n))testIndex = random.sample(indexList, testSetCnts)# testIndex=indexList[:testSetCnts]tDataSet&#py()for i in range(testSetCnts):index=testIndex[i]testDataSet[i, :]=tDataSet[index]testDataSetLabels[:, i]=dataSetLabels[index]trainDataSet=np.delete(dataMat, testIndex, axis=0)trainDataSetLabels=np.delete(dataSetLabels, testIndex, axis=0)return testDataSet, trainDataSet, testDataSetLabels, anspose()def classify0(testDatMat, trainDataMat, trainLabels, k=3):"""分类器，对数据进行预测分类，核心函数:param testDatMat: 测试集数据,大小为m1*n:param trainDataMat: 训练集数据,大小为m2*n:param trainLabels: 训练集类别标签行向量,大小为1*m2:param k: 距离最近的前k个点，控制选取数量:return: 预测的标签值行向量,大小为1*m1,m1为测试集数目:type testDatMat: np.mat:type testDatMat: np.mat:type trainDataMat: np.mat:type k: int:rtype:np.mat"""shape=np.shape(testDatMat)dataShape=np.shape(trainDataMat)distSet=np.s((dataShape[0], shape[0])))n=shape[0]for i in range(n):distSet[:, i] = computDist(trainDataMat, testDatMat[i])copyDistSet = py()sorIndex=np.argsort(copyDistSet, axis=0)resultLabels = np.zeros((1, n))for i in range(shape[0]):classCnt={}for j in range(k):index = int(sorIndex[j, i])nowLabel=int(trainLabels[0, index])classCnt[nowLabel]&#(nowLabel, 0)+1resultLabels[:, i]=sorted(classCnt.items(), key=operator.itemgetter(1), reverse=True)[0][0]return resultLabelsdef getErrRate(resultLabels,realLabels):"""计算预测值与真实值的错误率:param resultLabels: 分类器所预测的类别结果，大小为1*m1的行向量:param realLabels:  真实的类别，大小为1*m1的行向量:return: '错误率为 %lf'%(errorRate):type resultLabels: np.mat:type realLabels: np.mat:rtype: str"""resultLabels=list(map(int, list()[0]))realLabels=list(map(int, list()[0]))resLen=len(resultLabels)reaLen=len(realLabels)# import os# fileList = os.listdir('Files/digits/testDigits')if(resLen!=reaLen):return NoneerrCnts=0.0for i in range(reaLen):if(resultLabels[i]!=realLabels[i]):errCnts+=1.0print('错误的是%d,识别为%d,实际为%d'%(i,resultLabels[i], realLabels[i]))return '错误率为 %lf'%(errCnts/float(resLen))def sample_test():"""实例测试函数:return:None"""normdataSet, labelSet = loadDataMat('')testDataSet, trainDataSet, testDataSetLabels, trainDataSetLabels= divTrainSet_TestSet(normdataSet, labelSet, testRate=0.3)# print('测试集大小为 %d' % testDataSetLabels.shape[1])print('测试标签：',testDataSetLabels.shape, ' 训练标签：',trainDataSetLabels.shape)resultLabels = classify0(testDataSet, trainDataSet, trainDataSetLabels, k=3)print(' 结果标签：',resultLabels.shape)print(getErrRate(resultLabels, testDataSetLabels))def file_to_vector(file):dataVector=[]with open(file) as fr:for line in fr:currline=line.strip()d(list(map(int, currline)))return dataVectordef get_data_labels(file_father_path):import osdataMat = []labelMat = []fileList = os.listdir(file_father_path)for filename in fileList:number = int(filename.strip().split('.')[0].split('_')[0])dataMat.append(file_to_vector(file_father_path+filename))labelMat.append(number)return np.mat(dataMat), np.mat(labelMat)def hand_writing():"""手写字体识别:return: None"""train_dataMat,train_labels=get_data_labels('Files/digits/trainingDigits/')print(train_dataMat.shape, train_labels.shape)test_dataMat, test_labels = get_data_labels('Files/digits/testDigits/')print(test_dataMat.shape, test_labels.shape)resultLabels=classify0(test_dataMat, train_dataMat, train_labels, k=3)print(getErrRate(resultLabels,test_labels))# sample_test()
hand_writing()