k-近邻算法（kNN）---它的工作原理是：存在一个样本数据集合，也称做训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据得到分类。

1. 说明一下，文本数据格式：文本名字为：datingTestSet2.txt，该文件我放在项目里面的python文件同级

2. 使用python转化文件

 def file2matrix(filename):

     """

     Cynthia:解析文本数据，将属性数据放在returnMat,将标签放在classLabelVector

     导入训练数据

     :param filename: 数据文件路径

     :return: 数据矩阵returnMat和对应的类别classLabelVector

     """

     # 打开文件

     fr = open(filename, 'r')

     # 获得文件中的数据行的行数

     numberOfLines = len(fr.readlines())

     # 生成对应的空矩阵

     # 例如：zeros(2，3)就是生成一个 2*3 的矩阵，各个位置上全是 0

     returnMat = zeros((numberOfLines, 3))  # prepare matrix to return

     classLabelVector = []  # prepare labels return

     fr = open(filename, 'r')

     index = 0

     for line in fr.readlines():

         # str.strip([chars]) --返回移除字符串头尾指定的字符生成的新字符串

         line = line.strip()

         # 以 '\t' 切割字符串

         listFromLine = line.split('\t')

         # 每列的属性数据，即 features

         returnMat[index] = listFromLine[0: 3]

         # 每列的类别数据，就是 label 标签数据

         classLabelVector.append(int(listFromLine[-1]))

         index += 1

     # 返回数据矩阵returnMat和对应的类别classLabelVector

     return returnMat, classLabelVector

3. 数据归一化：

 def autoNorm(dataSet):

     """

     Desc：

         归一化特征值，消除属性之间量级不同导致的影响

     Args：

         dataSet -- 需要进行归一化处理的数据集

     Returns：

         normDataSet -- 归一化处理后得到的数据集

         ranges -- 归一化处理的范围

         minVals -- 最小值

     归一化公式：

         Y = (X-Xmin)/(Xmax-Xmin)

         其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。

     """

     # 计算每种属性的最大值、最小值、范围

     minVals = dataSet.min(0)

     maxVals = dataSet.max(0)

     # 极差

     ranges = maxVals - minVals

     normDataSet = (dataSet - minVals) / ranges

     return normDataSet, ranges, minVals

4. KNN分类的算法核心：

 1 def classify0(inX, dataSet, labels, k):
 2     """

     Desc:

         kNN 的分类函数

     Args:

         inX -- 用于分类的输入向量/测试数据

         dataSet -- 训练数据集的 features

         labels -- 训练数据集的 labels

         k -- 选择最近邻的数目

     Returns:

         sortedClassCount[0][0] -- 输入向量的预测分类 labels

     注意：labels元素数目和dataSet行数相同；程序使用欧式距离公式.

     预测数据所在分类可在输入下列命令

     kNN.classify0([0,0], group, labels, 3)

     """

     # -----------实现 classify0() 方法的第一种方式----------------------------------------------------------------------------------------------------------------------------

     # 1. 距离计算

     #shape函数是查看矩阵或者数组的维数

     dataSetSize = dataSet.shape[0]

     # tile生成和训练样本对应的矩阵，并与训练样本求差

     #tile是用于对某个序列进行重复。

     #示例：tile([1,2],(2,2,3))，输出为array([[[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]  ,  [[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]    ])

     #（1）可以看到是先将[1,2]重复3次得到[1, 2, 1, 2, 1, 2]，

     #（2）再将[1, 2, 1, 2, 1, 2]重复2次得到[[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]，

     #（3）最后再将[[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]重复两次[[[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]  ,  [[1, 2, 1, 2, 1, 2],[1, 2, 1, 2, 1, 2]]]。

     #总结：从上面的例子可以看出，tile(A,rep)按照rep里面从右到左的序列顺序对A进行重复，每对重复完一次，A就增加一个维度。

     diffMat = tile(inX, (dataSetSize, 1)) - dataSet

     #目的是计算出该测试点对训练集中的每个点的距离。

     """

     欧氏距离： 点到点之间的距离

     """

     # 取平方

     sqDiffMat = diffMat ** 2

     # 将矩阵的每一行相加

     sqDistances = sqDiffMat.sum(axis=1)

     # 开方

     distances = sqDistances ** 0.5

     # 根据距离排序从小到大的排序，返回对应的索引位置

     # argsort() 是将x中的元素从小到大排列，提取其对应的index（索引），然后输出到y。

     # print 'distances=', distances

     sortedDistIndicies = distances.argsort()

     # print 'distances.argsort()=', sortedDistIndicies

     # 2. 选择距离最小的k个点

     classCount = {}

     for i in range(k):

         # 找到该样本的类型

         voteIlabel = labels[sortedDistIndicies[i]]

         # 在字典中将该类型加一

         # 字典的get方法

         # 如：list.get(k,d) 其中 get相当于一条if...else...语句,参数k在字典中，字典将返回list[k];如果参数k不在字典中则返回参数d,如果K在字典中则返回k对应的value值

         # l = {5:2,3:4}

         # print l.get(3,0)返回的值是4；

         # Print l.get（1,0）返回值是0；

         # 感觉像Java中的键值对原理，键是这里的标签类型，值是标签出现的次数

         classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

     # 3. 排序并返回出现最多的那个类型
     # 字典的 items() 方法，以列表返回可遍历的(键，值)元组数组。

     # 例如：dict = {'Name': 'Zara', 'Age': 7}   print "Value : %s" %  dict.items()   Value : [('Age', 7), ('Name', 'Zara')]

     # sorted 中的第2个参数 key=operator.itemgetter(1) 这个参数的意思是先比较第几个元素

     # 例如：a=[('b',2),('a',1),('c',0)]  b=sorted(a,key=operator.itemgetter(1)) >>>b=[('c',0),('a',1),('b',2)] 可以看到排序是按照后边的0,1,2进行排序的，而不是a,b,c

     # b=sorted(a,key=operator.itemgetter(0)) >>>b=[('a',1),('b',2),('c',0)] 这次比较的是前边的a,b,c而不是0,1,2

     # b=sorted(a,key=opertator.itemgetter(1,0)) >>>b=[('c',0),('a',1),('b',2)] 这个是先比较第2个元素，然后对第一个元素进行排序，形成多级排序。

     sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)

     return sortedClassCount[0][0]

5. 用约会网站的数据进行训练中的数据标签测试

 #分类器针对约会网站的进行测试代码

 def datingClassTest():

     """

     Desc：

         对约会网站的测试方法，并将分类错误的数量和分类错误率打印出来

     Args：

         None

     Returns：

         None

     """

     # 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）

     hoRatio = 0.1  # 测试范围,一部分测试一部分作为样本

     # 从文件中加载数据

     datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")  # load data setfrom file

     # 归一化数据

     normMat, ranges, minVals = autoNorm(datingDataMat)

     # m 表示数据的行数，即矩阵的第一维

     m = normMat.shape[0]

     # 设置测试的样本数量， numTestVecs:m表示训练样本的数量

     numTestVecs = int(m * hoRatio)

     print('numTestVecs=', numTestVecs)

     errorCount = 0

     for i in range(numTestVecs):

         # 对数据测试

         classifierResult = classify0(normMat[i], normMat[numTestVecs : m], datingLabels[numTestVecs : m], 3)

         print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))

         errorCount += classifierResult != datingLabels[i]

     print("the total error rate is: %f" % (errorCount / numTestVecs))

     print(errorCount)

6. 做预测

 def classifyPerson():

     resultList = ['not at all','in small doses', 'in large doses']

     percentTats = float(input("percentage of time spent playing video games?"))

     ffMiles = float(input("frequent flier miles earned per years?"))

     iceCream = float(input("liters of ice cream consumed per year?"))

     datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")

     normMat, ranges, minVals = autoNorm(datingDataMat)

     inArr = array([ffMiles, percentTats, iceCream])

     classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)

     print("you will probably like this person:",resultList[classifierResult-1])

注：python3中的控制台交互是input

python2的是raw_input

控制台测试结果：

kNN代码测试已完毕。

本人github代码链接：https://github.com/CynthiaWendy/Machine-Learning-in-Action-KNN

项目案例2：构造k-近邻分类器的手写识别系统

　　说明：这里构造的系统只能识别数字0到9.如下图所示：

　　需要识别的数据已经使用图像处理软件，处理成具有相同的色彩和大小：宽高是32像素*32像素的黑白图像。尽管采用的文本格式存储图像不饿呢过有效地利用内存空间，但是为了方便理解，还是将图像转化为文本格式。

1. 数据准备：我们有两个数据集文件，一个是训练数据trainingDigits(大约2000个例子，每个数字大约有200个样本)，一个是测试数据（大约有900个测试数据）。这两组数据没有覆盖。

　　我们将把一个32*32的二进制图像矩阵转化为1*1024的向量，这样我们上面项目1的knn的分类器就可以处理数字图像信息。

 def img2vector(filename):

     '''

     该函数创建1*1024的Numpy数组，然后打开给定的文件，循环读出文件的前32行，

     并将每行的头32个字符值存储在Numpy数组中，最后返回数据。

     :param filename:

     :return:

     '''

     returnVect = zeros((1,1024))

     fr = open(filename)

     for i in range(32):

         lineStr=fr.readline()

         for j in range(32):

             #将信息取出，放在1*1024向量相应的位置上

             returnVect[0,32*i+j]=int(lineStr[j])

     return returnVect

2. 项目1中的knn核心函数被使用在测试中。

3. 测试代码

 def handwritingClassTest():

     """

         Desc:

             手写数字识别分类器，并将分类错误数和分类错误率打印出来

         Args:

             None

         Returns:

             None

         """

     hwLabels=[]

     #装入训练数据

     trainingFileList=os.listdir('trainingDigits')

     #得到该文件夹的文件个数

     m=len(trainingFileList)

     trainingMat=zeros((m,1024))

     for i in range(m):

         fileNameStr=trainingFileList[i]

         #得到文件的名字

         fileStr=fileNameStr.split('.')[0]

         #得到文件名字的分隔

         classNumStr=int(fileStr.split('_')[0])

         #将类别存在数组中

         hwLabels.append(classNumStr)

         #将每个文件的数据以1*1024的形式保存

         trainingMat[i]=img2vector("trainingDigits/%s" % fileNameStr)

     #导入测试数据

     testFileList=os.listdir('testDigits')

     errorCount=0.0

     mTest=len(testFileList)

     for i in range(mTest):

         fileNameStr=testFileList[i]

         fileStr=fileNameStr.split('.')[0]

         classNumStr=int(fileStr.split('_')[0])

         vectorUnderTest=img2vector("testDigits/%s" % fileNameStr)

         classifierResult=classify0(vectorUnderTest, trainingMat, hwLabels,3)

         print("the classifier came back with: %d, the real answer is: %d" % (classifierResult,classNumStr))

         if (classifierResult!=classNumStr): errorCount+=1.0

     print("\nthe total number of errors is: %d" % errorCount)

     print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

运行结果：

该项目的代码及数据放在本人的github上：欢迎指导。

https://github.com/CynthiaWendy/Machine-Learning-in-Action-KNN1

最新文章

  1. [转]ExtJs基础--Html DOM、Ext Element及Component三者之间的区别
  2. float导致父级元素塌陷的问题
  3. 《Linux内核分析》第六周 读书笔记
  4. bzoj2251
  5. Codeforces Round #Pi (Div. 2) B. Berland National Library 模拟
  6. Django学习笔记（五）—— 表单
  7. db2 备份还原
  8. mvn 手动安装jar 到本地库
  9. 电脑中安装多个jdk，eclipse的选择！
  10. spring boot+mybatis+quartz项目的搭建完整版
  11. 使用Python的库qrcode生成二维码
  12. 如何定义一个有效的OWIN Startup Class
  13. BZOJ 1055: [HAOI2008]玩具取名（记忆化搜索）
  14. [javamail]AUTH LOGIN failed;Invalid username or password报错
  15. Python Web框架 tornado 异步原理
  16. P2014 选课
  17. windows下python2.7.14版本的安装
  18. [JS] selector 背景选择器
  19. Uboot流程分析
  20. Python cx_oracle自动化操作oracle数据库增删改查封装，优化返回查询数据

热门文章

  1. php判断变量是否为数字is_numeric()
  2. DedeCms织梦发布文章时输入Tag标签逗号自动变成英文标点的方法
  3. 关于 html button 点击刷新页面的问题
  4. thinkphp读取器和修改器
  5. MYSQL<五>
  6. CodeForces-585B(BFS)
  7. C++ 遍历循环表达示 auto, auto&, auto&&
  8. Winserver-禁止程序启动
  9. 导出csv文件(使用a标签)
  10. BZOJ 3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛 水题~