专门做spa的网站,网站 租用服务器,网站运营策划提案,现在做一个网站多少钱前言
这个周基本在琢磨这个算法以及自己利用Python3 实现自主编程实现该算法。持续时间比较长#xff0c;主要是Pyhton可能还不是很熟练#xff0c;走了很多路#xff0c;基本是一边写一边学。不过#xff0c;总算是基本搞出来了。不多说#xff0c;进入正题。
1. K-邻近…前言
这个周基本在琢磨这个算法以及自己利用Python3 实现自主编程实现该算法。持续时间比较长主要是Pyhton可能还不是很熟练走了很多路基本是一边写一边学。不过总算是基本搞出来了。不多说进入正题。
1. K-邻近算法
1.1 基本原理
k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是存
在一个样本数据集合也称作为训练样本集并且样本集中每个数据都存在标签即我们知道样本集中每一个数据与所属分
类的对应关系。输入没有标签的新数据后将新的数据的每个特征与样本集中数据对应的特征进行比较然后算法提取样本
最相似数据(最近邻)的分类标签。一般来说我们只选择样本数据集中前k个最相似的数据这就是k-近邻算法中k的出处
通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类作为新数据的分类。
1.2 一个例子
先来看一个图
在这个图里面我们可以看到有第三种颜色标记的标签蓝色正方形红色三角形以及一个未知类型的绿色原点。那么如何判断这
个绿色点是属于蓝色家族的还是红色家族的呢
邻近的思想就是计算这个绿色的点分别到它附近的点的距离距离近就判定属于这个类型那么K-邻近就是让待分类的这个点与所
有的已经分类点的距离然后选取K个点统计待分类的这个绿色点属于哪个类别的数量比较多就最终判定这个点属于哪一个。
再回到图首先是K3可以看到实线里面有两个红点一个蓝点那么判定这个绿家伙属于红色的三角形类型。接着选取了近
距离绿色点最近的5个点这时会发现蓝色系占得更多所以判定这个绿家伙是属于蓝色正方形的类型。
从这个例子可以看出来K-邻近的几个基本关键点有
点之间的距离计算 欧式距离 d12∑i1n(x1i−x2i)−−−−−−−−−−−√d_{12}=\sqrt{ \sum_{i=1}^n(x_{1i}-x_{2i})}曼哈顿距离 两个向量a(x11,xx12,⋯,x1n)a(x_{11},xx_{12},\cdots,x_{1n})与b(x21,xx22,⋯,x2n)b(x_{21},xx_{22},\cdots,x_{2n})的曼哈顿距离为 d12∑k1n|x1k−x2k|d_{12}=\sum_{k=1}^n|x_{1k}-x_{2k}|其他 参考http://www.cnblogs.com/xbinworld/archive/2012/09/24/2700572.html 里面有着更加详细的关于距离的介绍。距离排序 在这个计算的过程中需要将最终的计算进行一个排序的。为下一步操作做好准备。K的选择 很明显对于这算法K的选取决定了整个算法分类预测的准确性可以说是其核心参数。从上面的例子也可以看出来K3和K5得到的决然不同的结果的。
1.3 算法步骤
1初始化距离 2计算待分类样本和每个训练集的距离 3排序 4选取K个最邻近的数据 5计算K个训练样本的每类标签出现的概率 6将待分类样本归为出现概率最大的标签分类结束。
2. Python实现K-邻近算法
2.1 K-邻近函数
def mykNN(testData, trainData, label, K):# testData 待分类的数据集# trainData 已经分类好的数据集# label trainData数据集里面的分类标签# K是knn算法中的K# testData[101,20]# testDatanp.array(testData)import numpy as nparraySize trainData.shapetrainingSampleNumber arraySize[0] # 样本大小trainFeatureNumber arraySize[1] # 样本特征个数# 将待测试样本拓展为和训练集一样大小矩阵testDataTemp np.tile(testData, (trainingSampleNumber, 1))distanceMatrixTemp (testDataTemp - trainData)**2distanceMatrix np.sum(distanceMatrixTemp, axis1)distanceMatrix np.sqrt(distanceMatrix)# print(测试集与训练集之间的欧式距离值为\n)# print(distanceMatrix)# print()# np.argsort()得到矩阵排序后的对应的索引值sortedDistanceIndex np.argsort(distanceMatrix)# print(sortedDistanceIndex)# 定义一个统计类别的字典labelClassCount {}for i in range(K):labelTemp label[sortedDistanceIndex[i]] # 获取排名前K的距离对应的类别值# print(labelTemp)labelClassCount[labelTemp] labelClassCount.get(labelTemp, 0) 1 # 统计前K中每个类别出现的次数# print(labelClassCount)sortedLabelClassCount sorted(labelClassCount.items(), keylambda item: item[1], reverseTrue) # 对字典进行降序排序# lambda item:item[1] 匿名函数将利用dict.items()获取的字典的key-value作为该匿名函数的变量输入。# reverseTrue 降序排列# print(sortedLabelClassCount)return sortedLabelClassCount[0][0] # 返回最终的分类标签值
2.2 牛刀小试-电影分类
举个简单的例子我们可以使用k-近邻算法分类一个电影是爱情片还是动作片。
电影名称打斗镜头接吻镜头电影类型电影11101Romance电影2589Romance电影31085action电影41158action
以上是已知的训练样本我们需预测的是101, 20这个样本我们大致可以知道打斗镜头多则应该是动作片
数据集函数
def creatDataSet():
#定义数据集函数group np.array([[1, 101, 5], [5, 89, 6], [108, 5, 100], [115, 8, 120]])label [romance Movie, romance Movie, action Movie, action Movie]# label[r,r,a,a]return group, label# print(group)# print(label)主函数
if __name____main__:
#主函数finalIdentifyingResult[]group,labelcreatDataSet()print()print(Identifying ......)print()print(The identified result is :\n)testData[101,20]testDatanp.array(testData)finalIdentifyingLabelmykNN(testData,group,label,3)print(the test data is identified as: ,finalIdentifyingLabel,\n) 可以看出来分类结果和我们预测的是一致的动作电影。
完整代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Date : 2017-08-28 16:04:25
# Author : AiYong (aiyong_stu163.com)
# Link : http://blog.csdn.net/sjtuai
# Version : $Id$import numpy as npdef creatDataSet():group np.array([[1, 101], [5, 89], [108, 5], [115, 8]])label [romance Movie, romance Movie, action Movie, action Movie]return group, labelprint(group)print(label)def mykNN(testData, trainData, label, K):arraySize trainData.shapetrainingSampleNumber arraySize[0]testDataTemp np.tile(testData, (trainingSampleNumber, 1))distanceMatrixTemp (testDataTemp - trainData)**2distanceMatrix np.sum(distanceMatrixTemp, axis1)distanceMatrix np.sqrt(distanceMatrix)sortedDistanceIndex np.argsort(distanceMatrix)labelClassCount {}for i in range(K):labelTemp label[sortedDistanceIndex[i]] labelClassCount[labelTemp] labelClassCount.get(labelTemp, 0) 1 sortedLabelClassCount sorted(labelClassCount.items(), keylambda item: item[1], reverseTrue) return sortedLabelClassCount[0][0] if __name____main__:finalIdentifyingResult[]group,labelcreatDataSet()print()print(Identifying ......)print()print(The identified result is :\n)testData[101,20]testDatanp.array(testData)finalIdentifyingLabelmykNN(testData,group,label,3)print(the test data is identified as: ,finalIdentifyingLabel,\n)2.3 考验阶段-鸢尾花数据集应用-分类预测
鸢尾花数据集
U can get description of ‘iris.csv’ at ‘http://aima.cs.berkeley.edu/data/iris.txt‘#### Definiation of COLs: #1. sepal length in cm (花萼长) # #2. sepal width in cm花萼宽# #3. petal length in cm (花瓣长) #4. petal width in cm花瓣宽 # #5. class: # #– Iris Setosa # #– Iris Versicolour # #– Iris Virginica # #Missing Attribute Values: None
数据集整理函数
def creatDataSet(fileName, test_size_ratio):# fileName is the data file whose type is string# test_size whose type is float is the ratio of test data in the whole# data setirisData np.loadtxt(fileName, dtypefloat,delimiter,, usecols(0, 1, 2, 3))dataSize irisData.shapeirisLabel np.loadtxt(fileName, dtypestr, delimiter,, usecols4)irisLabel irisLabel.reshape(dataSize[0], 1)#这里使用的一个函数是机器学习库中的一个可以用来随机选取训练集和测试集的一个函数iristrainData, iristestData, iristrainDataLabel, iristestDataLabel cross_validation.train_test_split(irisData, irisLabel, test_sizetest_size_ratio, random_state0)return iristrainData, iristestData, iristrainDataLabel, iristestDataLabel
矩阵转化为列表函数
def ndarray2List(label):#这个函数的目的是为了后的数据服务的。label label.tolist()finalLabel []for i in range(label.__len__()):finalLabel.append(\n.join(list(label[i])))return finalLabel
自定义混淆矩阵计算函数
def computingConfusionMatrix(trueResultA, modelPredictResultB):# trueResultA 正确的分类结果numpy矩阵类型# modelPredictResultB 模型预测结果numpy矩阵类型# labelType 分类标签值list列表类型#返回confusionMatrix混淆矩阵numpy矩阵类型#返回labelType分类标签list列表类型#返回Accuracy分类争取率float浮点数据import numpy as nplabelType []for i in trueResultA:if i not in labelType:labelType.append(i)print(labelType)labelTypeNumber labelType.__len__()confusionMatrix np.zeros([labelTypeNumber, labelTypeNumber], dtypeint64)finalCount 0for i in range(labelTypeNumber):for j in range(trueResultA.__len__()):if modelPredictResultB[j] labelType[i] and trueResultA[j] labelType[i]:confusionMatrix[i][i] 1else:for k in range(labelTypeNumber):if k i:breakif modelPredictResultB[j] labelType[k]:confusionMatrix[i][k] 1breakcount 0for i in range(labelTypeNumber - 1, -1, -1):if i 0:breakfor j in range(labelTypeNumber - 1 - count):confusionMatrix[i][j] confusionMatrix[i][j] - confusionMatrix[i - 1][j]count 1totalTrueResult 0for k in range(labelTypeNumber):totalTrueResult confusionMatrix[k][k]Accuracy float(totalTrueResult / modelPredictResultB.__len__()) * 100return confusionMatrix, labelType, Accuracy
定义图里面的横纵坐标轴标签值的旋转
def labelsRotation(labels, rotatingAngle):#labels 获取的xy轴的标签值#rotatingAngle 想要旋转的角度# 定义xy轴标签旋转函数for t in labels:t.set_rotation(rotatingAngle)定义混淆矩阵可视化函数
def plotConfusionMatrix(confusionMatrix,labelType):import matplotlib.pyplot as plt
# 设置图片的大小以及图片分辨率fig plt.figure(figsize(10, 8), dpi120)plt.clf()
# 绘制图colormap是coolwarmplt.imshow(confusionMatrix, cmapplt.cm.coolwarm, interpolationnearest)plt.colorbar()
# 设置xy的横纵轴的标签plt.xlabel(Predicted Result, fontsize11)plt.ylabel(True Result, fontsize11)cmSize confusionMatrix.shapewidth cmSize[0]height cmSize[1]plt.xticks(fontsize11)plt.yticks(fontsize11)
# 设置横纵坐标的刻度标签显示为分类标签值x_locs, x_labels plt.xticks(range(width), labelType[:width])y_locs, y_labels plt.yticks(range(height), labelType[:height])
# 设置xy轴的标签是否旋转labelsRotation(x_labels, 0)labelsRotation(y_labels, 0)# 在图里面添加数据标签confusionMatrix confusionMatrix.Tfor x in range(width): # 数据标签for y in range(height):plt.annotate(confusionMatrix[x][y], xy(x, y), horizontalalignmentcenter, verticalalignmentcenter)plt.grid(True, whichminor, linestyle-)
# plt.rc(font,familyTimes New Roman,size15)font {family: monospace, weight: bold, size: 15}plt.rc(font, **font)plt.show()
主函数
if __name__ __main__:finalIdentifyingResult []iriskNNResult []iristrainData, iristestData, iristrainDataLabel, iristestDataLabel creatDataSet(iris.txt, 0.8)testGroup iristestDatatrainGroup iristrainDatatrainLabel iristrainDataLabeltestSize testGroup.shapetestSampleNumber testSize[0]print()print(Identifying ......)print()print(The identified result is :\n)for i in range(testSampleNumber):testData testGroup[i]finalIdentifyingLabel mykNN(testData, trainGroup, trainLabel, 10)finalIdentifyingResult.append(finalIdentifyingLabel)iriskNNResult np.array(finalIdentifyingResult).reshape(testSampleNumber, 1)print(finalIdentifyingResult)trueResultA ndarray2List(iristestDataLabel)modelPredictResultB finalIdentifyingResultconfusionMatrix, labelType, Accuracy computingConfusionMatrix(trueResultA, modelPredictResultB)print(The accuracy is :{a:5.3f}%.format(aAccuracy))plotConfusionMatrix(confusionMatrix, labelType)结果 混淆矩阵
从上面的结果可以看到这个准确率在90%以上说明还是不错的
完整的程序结构
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Date : 2017-08-08 16:04:25
# Author : AiYong (aiyong_stu163.com)
# Link : http://blog.csdn.net/sjtuai
# Version : $Id$import numpy as np
from sklearn import cross_validation
import matplotlib.pyplot as pltdef mykNN(testData, trainData, label, K):# testData 待分类的数据集# trainData 已经分类好的数据集# label trainData数据集里面的分类标签# K是knn算法中的K# testData[101,20]# testDatanp.array(testData)import numpy as nparraySize trainData.shapetrainingSampleNumber arraySize[0] # 样本大小trainFeatureNumber arraySize[1] # 样本特征个数# 将待测试样本拓展为和训练集一样大小矩阵testDataTemp np.tile(testData, (trainingSampleNumber, 1))distanceMatrixTemp (testDataTemp - trainData)**2distanceMatrix np.sum(distanceMatrixTemp, axis1)distanceMatrix np.sqrt(distanceMatrix)# print(测试集与训练集之间的欧式距离值为\n)# print(distanceMatrix)# print()# np.argsort()得到矩阵排序后的对应的索引值sortedDistanceIndex np.argsort(distanceMatrix)# print(sortedDistanceIndex)# 定义一个统计类别的字典labelClassCount {}for i in range(K):labelTemp label[sortedDistanceIndex[i]] # 获取排名前K的距离对应的类别值# print(labelTemp)labelClassCount[labelTemp] labelClassCount.get(labelTemp, 0) 1 # 统计前K中每个类别出现的次数# print(labelClassCount)sortedLabelClassCount sorted(labelClassCount.items(), keylambda item: item[1], reverseTrue) # 对字典进行降序排序# lambda item:item[1] 匿名函数将利用dict.items()获取的字典的key-value作为该匿名函数的变量输入。# reverseTrue 降序排列# print(sortedLabelClassCount)return sortedLabelClassCount[0][0] # 返回最终的分类标签值def creatDataSet(fileName, test_size_ratio):# fileName is the data file whose type is string# test_size whose type is float is the ratio of test data in the whole# data setirisData np.loadtxt(fileName, dtypefloat,delimiter,, usecols(0, 1, 2, 3))dataSize irisData.shapeirisLabel np.loadtxt(fileName, dtypestr, delimiter,, usecols4)irisLabel irisLabel.reshape(dataSize[0], 1)#这里使用的一个函数是机器学习库中的一个可以用来随机选取训练集和测试集的一个函数iristrainData, iristestData, iristrainDataLabel, iristestDataLabel cross_validation.train_test_split(irisData, irisLabel, test_sizetest_size_ratio, random_state0)return iristrainData, iristestData, iristrainDataLabel, iristestDataLabeldef ndarray2List(label):#这个函数的目的是为了后的数据服务的。label label.tolist()finalLabel []for i in range(label.__len__()):finalLabel.append(\n.join(list(label[i])))return finalLabeldef computingConfusionMatrix(trueResultA, modelPredictResultB):# trueResultA 正确的分类结果numpy矩阵类型# modelPredictResultB 模型预测结果numpy矩阵类型# labelType 分类标签值list列表类型#返回confusionMatrix混淆矩阵numpy矩阵类型#返回labelType分类标签list列表类型#返回Accuracy分类争取率float浮点数据import numpy as nplabelType []for i in trueResultA:if i not in labelType:labelType.append(i)print(labelType)labelTypeNumber labelType.__len__()confusionMatrix np.zeros([labelTypeNumber, labelTypeNumber], dtypeint64)finalCount 0for i in range(labelTypeNumber):for j in range(trueResultA.__len__()):if modelPredictResultB[j] labelType[i] and trueResultA[j] labelType[i]:confusionMatrix[i][i] 1else:for k in range(labelTypeNumber):if k i:breakif modelPredictResultB[j] labelType[k]:confusionMatrix[i][k] 1breakcount 0for i in range(labelTypeNumber - 1, -1, -1):if i 0:breakfor j in range(labelTypeNumber - 1 - count):confusionMatrix[i][j] confusionMatrix[i][j] - confusionMatrix[i - 1][j]count 1totalTrueResult 0for k in range(labelTypeNumber):totalTrueResult confusionMatrix[k][k]Accuracy float(totalTrueResult / modelPredictResultB.__len__()) * 100return confusionMatrix, labelType, Accuracydef labelsRotation(labels, rotatingAngle):#labels 获取的xy轴的标签值#rotatingAngle 想要旋转的角度# 定义xy轴标签旋转函数for t in labels:t.set_rotation(rotatingAngle)def plotConfusionMatrix(confusionMatrix,labelType):import matplotlib.pyplot as pltfig plt.figure(figsize(10, 8), dpi120)plt.clf()plt.imshow(confusionMatrix, cmapplt.cm.coolwarm, interpolationnearest)plt.colorbar()plt.xlabel(Predicted Result, fontsize11)plt.ylabel(True Result, fontsize11)cmSize confusionMatrix.shapewidth cmSize[0]height cmSize[1]plt.xticks(fontsize11)plt.yticks(fontsize11)x_locs, x_labels plt.xticks(range(width), labelType[:width])y_locs, y_labels plt.yticks(range(height), labelType[:height])labelsRotation(x_labels, 0)labelsRotation(y_labels, 0)confusionMatrix confusionMatrix.Tfor x in range(width): # 数据标签for y in range(height):plt.annotate(confusionMatrix[x][y], xy(x, y), horizontalalignmentcenter, verticalalignmentcenter)plt.grid(True, whichminor, linestyle-)font {family: monospace, weight: bold, size: 15}plt.rc(font, **font)plt.show()if __name__ __main__:finalIdentifyingResult []iriskNNResult []iristrainData, iristestData, iristrainDataLabel, iristestDataLabel creatDataSet(iris.txt, 0.8)testGroup iristestDatatrainGroup iristrainDatatrainLabel iristrainDataLabeltestSize testGroup.shapetestSampleNumber testSize[0]print()print(Identifying ......)print()print(The identified result is :\n)for i in range(testSampleNumber):testData testGroup[i]finalIdentifyingLabel mykNN(testData, trainGroup, trainLabel, 10)finalIdentifyingResult.append(finalIdentifyingLabel)iriskNNResult np.array(finalIdentifyingResult).reshape(testSampleNumber, 1)print(finalIdentifyingResult)trueResultA ndarray2List(iristestDataLabel)modelPredictResultB finalIdentifyingResultconfusionMatrix, labelType, Accuracy computingConfusionMatrix(trueResultA, modelPredictResultB)print(The accuracy is :{a:5.3f}%.format(aAccuracy))plotConfusionMatrix(confusionMatrix, labelType)3. 总结
这里有非常好的关于K-邻近分类的理论以及一些比较好的图理
https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
3.1 优缺点
优点
简单易于理解易于实现无需估计参数无需训练 适合对稀有事件进行分类例如当流失率很低时比如低于0.5%构造流失预测模型 特别适合于多分类问题(multi-modal,对象具有多个类别标签)例如根据基因特征来判断其功能分类kNN比SVM的表现要好
缺点
懒惰算法对测试样本分类时的计算量大内存开销大评分慢 可解释性较差无法给出决策树那样的规则。
3.2 一些问题集锦
1、k值设定为多大 k太小分类结果易受噪声点影响k太大近邻中又可能包含太多的其它类别的点。对距离加权可以降低k值设定的影响 k值通常是采用交叉检验来确定以k1为基准 经验规则k一般低于训练样本数的平方根
2、类别如何判定最合适 投票法没有考虑近邻的距离的远近距离更近的近邻也许更应该决定最终的分类所以加权投票法更恰当一些。
3、如何选择合适的距离衡量
高维度对距离衡量的影响众所周知当变量数越多欧式距离的区分能力就越差。 变量值域对距离的影响值域越大的变量常常会在距离计算中占据主导作用因此应先对变量进行标准化。
4、训练样本是否要一视同仁
在训练集中有些样本可能是更值得依赖的。 可以给不同的样本施加不同的权重加强依赖样本的权重降低不可信赖样本的影响。
5、性能问题
kNN是一种懒惰算法平时不好好学习考试对测试样本分类时才临阵磨枪临时去找k个近邻。 懒惰的后果构造模型很简单但在对测试样本分类地的系统开销大因为要扫描全部训练样本并计算距离。
参考链接
https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
http://blog.csdn.net/jmydream/article/details/8644004
http://wuguangbin1230.blog.163.com/blog/static/61529835201522905624494/
https://docs.scipy.org/doc/numpy-dev/user/quickstart.html
http://matplotlib.org/api/pyplot_summary.html
