机器学习实战Ch02_k近邻算法的运行

简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

#第一个kNN分类器  inX-测试数据的输入向量 dataSet-训练样本数据集  labels-标签向量 k-邻近的k个样本
def classify0(inX, dataSet, labels, k):
    # 使用欧氏距离来计算距离
    dataSetSize = dataSet.shape[0]#训练集大小即数组大小
    diffMat = tile(inX, (dataSetSize, 1))-dataSet#把待分类数据向量复制成与训练集等阶，对应项求差
    sqDiffMat = diffMat ** 2#各项平方，上一项是为了这一步，因为欧氏距离就是对应项间的操作
    sqDistance = sqDiffMat.sum(axis=1)#axis=1，将一个矩阵的每一行向量相加（平方和想加） 
    # print(sqdistance)
    distances = sqDistance ** 0.5#开方，求出距离 

#按照距离递增次序排列  计算完所有点之间的距离后，可以对数据按照从小到大的次序进行排序，然后确定前k个距

#离最小元素所在的主要分类，输入k总是正整数；最后，将classCount字典分解为元祖列表，然后使用程序第二行导

#入运算符模块的itemgetter方法，按照第二个元素的次序对元祖进行排序  

    sortedDistIndex = distances.argsort()#距离从小到大排序，返回数组的索引，因为索引对应标签 
    classCount = {}#字典分解为元祖列表
    # 选择距离最小的k个点 
    for i in range(k):#在字典里每次都是遍历前K个样本训练集,确定前k个距离最小的元素所对应的分类
        voteIlabel = labels[sortedDistIndex[i]]#对应分类
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#出现过的计数，没出现的找分类
    # 排序 
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    # 此处排序为逆序，按照从大到小
    #输出在前k个里面出现频率最高的元素标签
    return sortedClassCount[0][0]#返回统计最多的分类

#输入为文件名字符串输出为训练样本矩阵和类标签向量
def file2matrix(filename):
    fr = open(filename)
    arrayOnLines = fr.readlines()#获取所有数据，以行为单位切割
    numberOfLines = len(arrayOnLines)#得到文件行数1000
    returnMat = zeros((numberOfLines, 3))#构建矩阵NumPy（默认二维），以0填充，我们将矩阵另一维设置成固定值3
    classLabelVector = []
    index=0
    for line in arrayOnLines:#循环处理文件每行数据
        line = line.strip()#截取掉所有的回车字符
        listFromLine = line.split('\t')#以tab分割为数组（将上一步得到的整行数据分割成一个元素列表）
        returnMat[index, :] = listFromLine[0:3]#copy数据，选取前3个元素存储到矩阵
        classLabelVector.append(int(listFromLine[-1]))#保存对应的分类（-1表示列表最后一列元素）
    return returnMat, classLabelVector

重新输入上面所有的代码（从头再来），因为由于没有使用样本分类特征值，为了在图中用不用颜色标记不同样本分类，来更好理解数据信息。scatter函数支持个性化标记散点图的点： from numpy import array注意不加这个会报错，因为python的array和numpy的array有差别 ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) plt.show()

def autoNorm(dataSet):
    minVals = dataSet.min(0)#一维数组，值为各项特征（列）中的最小值，1*3。每列的最小值  参数0可以从列中选取最小值而不是选取当前行的最小值
    maxVals = dataSet.max(0)#每列最大值
    ranges = maxVals - minVals#1*3。函数计算可能的取值范围，并创建新的返回矩阵，为了归一化特征值，必须使用当前值减去最小值，然后除以取值范围  
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]#特征值大小为1000*3。注意事项：特征值矩阵有1000*3个值。而minVals和range的值都为1*3.为了解决这个问题使用numpy中tile函数将变量内容复制成输入矩阵同样大小的矩阵
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges, (m,1))#特征值相除，使用tile函数使得矩阵大小一致
    return normDataSet, ranges, minVals注意事项：特征值矩阵有1000*3个值。而minVals和range的值都为1*3.为了解决这个问题使用numpy中tile函数将变量内容复制成输入矩阵同样大小的矩阵
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges, (m,1))#特征值相除，使用tile函数使得矩阵大小一致
    return normDataSet, ranges, minVals

def datingClassTest():
    hoRatio = 0.50  # hold out 10%
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')  # load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.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]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print ("the total error rate is: %f" % (errorCount / float(numTestVecs)))
    print (errorCount)

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(raw_input(\
        "percentage of time spent playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))#raw_input允许用户输入文本行命令并返回用户输入的命令
    iceCream = float(raw_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]

def img2vector(filename):
    returnVect = zeros((1, 1024))#创建1*1024的numpy数组
    fr = open(filename)
    for i in range(32):#循环读出文件的前32行
        lineStr = fr.readline()
        for j in range(32):#将每行的头32个字符值存储在numpy数组中，最后返还给数组
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect

reload(kNN)

testVector=kNN.img2vector('testDigits/0_13.txt')

testVector[0,0:31]

testVector[0,32:63]

# 手写识别系统测试代码
def handwritingClassTest():
    hwLabels = []
    trainingFileList = dir('trainingDigits')#获取testDigits目录中的文件内容存储在列表中
    m = len(trainingFileList)#得到目录中有多少文件，便将其存储到变量m中
    trainingMat = zeros((m, 1024))#创建一个m*1024的训练矩阵，该矩阵的每行数据存储一个图像，可以从文件名中解析出分类数字
    for i in range(m):
        fileNameStr = trainingFileList[i] #分割得到标签  从文件名解析得到分类数据
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr) #测试样例标签，该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例
#将类代码存储在hwLabels向量中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr )#使用img2vector载入图像 
    #对testDigits目录中的文件执行相似的操作，不同之处在于我们并不将这个目录下的文件载入矩阵中  
    #而是利用classify0()函数测试该目录下每个文件，由于文件中的值已在0~1之间，所以不需要autoNorm()函数 
    testFileList = dir('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)))

reload(kNN)

kNN.handwritingClassTest()