K-近邻算法

1.概述

简单来书，K-近邻算法就是采用测量不同特征值之间距离的方法来分类的。

此笔记是根据《机器学习》书中介绍的KNN。
在包含特征值的训练样本集中，输入没有特征的新数据后，将新数据每个特征与训练集对应特征进行比较，然后提取最相似数据的分类标签，一般来说只选择训练集中前k个最相似的数据，通常k不大于20的整数，最后统计次数最多的分类标签即为新数据的标签。

《机器学习》数据源

---

2.介绍

优点：精度高，对异常值不敏感，无数据输入假定
缺点：计算复杂度高，控件复杂度高
适用数据范围：数值型和标称型

from numpy import * #引用所有numpy
#1.导入数据源，解析文本记录
def  file2matrix(filename):
  fr = open(filename)
  arrayLines = fr.readlines()
  numberOfLines = len(arrayLines)
  returnMat = zeros((numberOfLines,3))  #返回由0填充的数组
  labelVec =[]                                            #数据类别
  index = 0
  for line in arrayLines:
    line = line.strip() #删除字符串头尾的指定字符（默认空格或换行符）
    listFromLine = line.split('\t')
    returnMat[index,;] = listFromLine[0:3]
    labelVex.append(int(listFromLine[-1]))
    index +=1
  return returnMat,labelVec
#2.归一化特征值 newVals = (oldVals - minVals)/(maxVals - minVals)
def  autoNorm(dataSet):
  minVals = dataSet.min(0)                  #0:列 1:行  min(0):每一列的最小值
  maxVals= dataSet.max(0)                  #返回的是行数据
  ranges = maxVals - minVals
  m= dataSet.shape[0]
  normDataSet = zeros((shape(dataSet)))  # shape(dataSet) 得到(行，列)，即复制数组结构
  normDataSet = dataSet - tile(minVals,(m,1)) #tile(data,(行，1)) 复制数据，m行
  normDataSet = normDataSet/tile(ranges,(m,1))
  return normDataSet,ranges,minVals

#3.k-近邻算法 平方差公式
def  classify(inx,dataSet,Labels,k):
  m = dataSet.shape[0] #获取dataSet的行
  copyInxArray= tile(inx,(m,1))
  diffMat = pow(dataSet - copyInxArray,2)  #差的平方
  #sum 与axis 连用时，axis=0 每一列数据相加；axis=1 每一行数据相加， 结果都是一个一维数组；
  #当max/min与axis 连用时，axis=0  取出每一行的最大值，保持列数；axis=1时，取出每一列的最大值，保持行数
  sumDiffMat = diffMat.sum(axis=1)   
  Distance = sumDiffMat ** 0.5
  sortedDistance = distance.argsort()  #1.标注对应索引。2.对数据升序排序。3.返回升序结果后对应的索引
  classCount ={}
  for i in range(k):
    votes = Labels[sortedDistance[k]] 
    classCount[vote] = classCount.get(vote,0)+1 #计算label出现的次数
  #按照value(次数)排序，需要引用 import operator，返回由tuple组成的List
  sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True) 
  return sortedClassCount[0][0]

#4.data test
def  datingClassTest():
  ratio = 0.10  #测试数据比例
  dataMat,labels = file2matrix('test.txtx')
  normdataMat,ranges,minVals= autoNorm(dataMat)
  m = normdataMat.shape[0]
  numTestData = int(m*ratio)
  errorCount = 0.0
  for i in range(numTestData):
    TestClassify =classify(dataMat[i],dataMat[numTestData:m:],labels[numTestData:m:],3)
    print("classify type:%s,the real answer is %s" % (TestClassify,labels[i]))
    if(TestClassify!=labels[i]):
      errorCount +=1.0
  pring("the error rate %f"%(errorCount/float(numTestData)))

Done.