机器学习：k-近邻分类

from numpy import *
import operator

def kNN_classification(inX, dataSet, labels, k):
    '''
    inX: 待分类的样本（以一个一维矩阵的形式表示）
    dataSet: 训练样本集（以一个二维矩阵的形式表示，其中行数为样本个数，每一行代表一个样本）
    labels: 训练样本集中样本所对应的分类
    k: K-近邻分类中的K，要事先给定
    '''
    m = dataSet.shape[0] # 计算dataSet的行数
    diffMat = tile(inX, (m, 1)) - dataSet      # numpy中的tile函数
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    
    sortedDistances = distances.argsort() 
    # argsort函数返回一个与distances同样大小的一维数组，其中每个索引上的值为distances在该索引的值从小到大排序的“序号-1“

    classCount = {} # 用来存储距离最近的K个样本的类别计数
    for i in range(len(sortedDistances)):
        if sortedDistances[i] < k:
            label = labels[i]
            classCount[label] = classCount.get(labe, 0) + 1

    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    '''
    python字典中还存在items()方法。两者有些许区别。
    items方法是可以将字典中的所有项，以列表方式返回。
    iteritems方法与items方法相比作用大致相同，只是它的返回值不是列表，而是一个迭代器。
    例如要通过student的第三个域排序，可以这么写：
        sorted(students, key=operator.itemgetter(2)) 
    reverse=True表示从大到排序
    '''
    return sortedClassCount[0][0]
    
     

'''
在约会网站上使用K-近邻算法：
    1、首先要获取数据，将数据处理为算法要求的格式，这里创建一个从文件中解析数据的函数file2matrix，
    将数据解析为算法所要求的格式（一个样本数据集——矩阵形式；一个样本数据所对应的分类——列表形式）。
    2、数据解析出来之后，需要对数据进行一些处理，要使得每一个属性的值对相似度计算的影响是一样，则要
    进行数据归一化处理。
    所谓的“使每一个属性值对相似度计算的影响是一样的”，意思是：举个例子，使用欧氏
    距离计算相似度时，如果某个属性值非常大，大到使得其他属性值的计算可以忽略，但是这三个属性对于分类
    来说是同等重要的。因此要进行数据归一化处理。创建一个autoNorm函数进行归一化
    3、开始测试分类器的错误率。随机挑选样本中10%的数据作为测试集来测试分类器的错误率，使用一个函数
    datingClassTest来完成。
    4、测试成功之后，则可以使用该分类器为某人确定某一对象的可交往程序：通过输入那三个特征的数值来判断。
    这里使用classifyPerson函数来完成。
'''
def file2matrix(filepath):
    '''
    :param filepath: 数据保存在文本文件里，filepath为该文件的路径
    :return: 一个矩阵形式的样本数据集，一个样本数据所对应的分类标签列表。
    '''
    fr = open(filepath)
    lines = fr.readlines()
    numberOfLines = len(lines)
    # 首先构建第一个样本数据集（矩阵形式）
    returnMat = zeros((numberOfLines, 3))
    # laberVector用来存放数据样本所对应的分类
    labelVector = []
    # index用来控制returnMat的行数，returnMat共有numberOfLines行，也就是共有numberOfLines个样本数据
    index = 0
    for line in lines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0: 3]
        # 下面这个判断语句将三种分类类型”极大魅力largeDoses“、”较小魅力smallDoses“、”不喜欢didntLike“用数字来表示
        if listFromLine[-1] == 'largeDoses':
            labelVector.append(3)
        elif listFromLine[-1] == 'smallDoses':
            labelVector.append(2)
        else:
            labelVector.append(1)
        # labelVector.append(listFromLine[-1])
        index += 1

    return returnMat, labelVector

def autoNorm(datas):

    # 使用numpy中的min和max
    # min或max中无参，返回的是数组中所有数字的最小值或最大值（一个值）；
    # min或max中参数为0，返回的是数组中每列的最小值或最大值（为一个一维数组）；
    # min或max中参数为1，返回的是数组中每行的最小值或最大值（为一个一维数组）。
    minVals = datas.min(0)
    maxVals = datas.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(datas))
    m = datas.shape[0]
    # numpy中两个数组进行运算时，是数组中对应的数值进行相应运算。
    # 这里运用了tile函数，tile（minVals, (m, 1)）表示的是每一行都是minVals，共m行
    normDataSet = datas - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))

    return normDataSet, ranges, minVals

def datingClassTest():
    hoRatio = 0.10 # 要取样本中10%作为测试集
    datingDataMat, datingLabels = file2matrix('D:/machinelearninginaction/Ch02/datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]   # 样本数据总量
    numTestVecs = int(m * hoRatio)  # 求出10%样本数据的数量
    # print(normMat[1])   # 这两行结果一样
    # print(normMat[1,:])

    errorCount = 0.0
    for i in range(numTestVecs):
        classifyResult = classify0(normMat[i, :], normMat[numTestVecs: m, :], datingLabels[numTestVecs: m], 5)
        print('the classifier came back with: %d, the real answer is: %d' % (classifyResult, datingLabels[i]))
        if classifyResult != datingLabels[i]:
            errorCount += 1
    print('the total error rate is: %f' % (errorCount / float(numTestVecs)))


# datingClassTest() 结果为0.04，错误率很低，因此可以使用

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?'))
    iceCream = float(raw_input('ilters of ice cream consumed per year?'))
    datingDataMat, datingLabels = file2matrix('D:/machinelearninginaction/Ch02/datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 5)
    print('You will probably like this person: ', resultList[classifierResult - 1])


# classifyPerson()


# 使用一个界面来可视化这个过程
window = Tk()


def classify():
    resultList = ['不喜欢', '较小魅力', '极具魅力']
    percentTats = entry1.get()
    ffMiles = entry2.get()
    iceCream = entry3.get()
    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([float(ffMiles), float(percentTats), float(iceCream)])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 5)
    theStringResult = '通过你所输入的某个人的特征得出，该人应该属于：' + resultList[ classifierResult - 1]
    text.insert(0.0, theStringResult)

var1 = StringVar()
var2 = StringVar()
var3 = StringVar()
window.geometry('400x320') # 其中的乘号是x不是*
window.title('约会网站人员分类')
label = Label(window, text='请输入某人的以下三个特征值：', font='Helvetica -16 bold')
label1 = Label(window, text='玩视频游戏所耗时间百分比：')
label2 = Label(window, text='每年获得的飞行常客里程数：')
label3 = Label(window, text='每周消费的冰淇淋公升数：')
entry1 = Entry(window, textvariable=var1)
entry2 = Entry(window, textvariable=var2)
entry3 = Entry(window, textvariable=var3)
label.pack()
label1.place(x=20, y=50)
label2.place(x=20, y=100)
label3.place(x=20, y=150)
entry1.place(x=180, y=50)
entry2.place(x=180, y=100)
entry3.place(x=180, y=150)

button = Button(window, text='查看该人类别', width=15, command=classify)
button.place(x=150, y=200)

text = Text(window, height=3)
text.place(x=0, y=250)


window.mainloop()

# -*- coding: utf-8 -*-
'''
利用kNN（K-近邻分类器）的手写识别系统，这里构造的系统只识别0-9的数字。
在使用kNN分类器之前，
    首先收集到数据（这里主要是两个文件夹，一个训练集数据，一个测试集数据）。
    然后要处理数据（准备数据），将图像格式转换为分类器使用的list格式。
    最后是分析数据，在Python中检查数据，确保它符合要求。
处理好数据格式之后，就可以开始测试kNN分类算法了，
    使用kNN分类器是识别手写数字，这里构建一个函数handwritingClssTest
'''

from numpy import *
from os import listdir # 从os模块导入listdir函数，该函数可以列出给定目录的文件名


'''
图像格式为一个32x32的矩阵，由于在kNN分类器中，每个样本在样本矩阵中都是以一行的形式存在，
因此要将它转换为1x1024的矩阵形式。
'''
def img2vector(filepath):
    '''
    :param filepath: 一个图像32x32矩阵所保存的文本文件路径
    :return: 将该图像32x32矩阵转换为1x1024矩阵形式。
    '''
    returnVec = zeros((1, 1024))
    file = open(filepath)
    for i in range(32):
        lineStr = file.readline()
        for j in range(32):
            returnVec[0, i * 32 + j] = int(lineStr[j])
    return returnVec

# 测试数据是否符合要求
# testdata = img2vector('testDigits/0_13.txt')
# print(testdata[0, 0: 31])
# print(testdata[0, 32: 63])

def handwritingClassTest():
    # 首先提取训练集数据，得到一个样本矩阵trainingMat以及样本对应类别标签列表hwLabel
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        # 首先获取该文件的所表示的数字是哪个（即所属类别），由文件名称的第一个字符可知。文件名通常为：数字_第几个.txt
        digitStr = fileNameStr.split('.')[0]
        firstDigitStr = digitStr.split('_')[0]

        hwLabels.append(firstDigitStr)
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)

    # 然后从文本文件中提取每个测试集数据进行测试，计算错误率
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        testFileNameStr = testFileList[i]
        # 获取该文件类别标签
        testDigitStr = testFileNameStr.split('.')[0]
        classNumStr = testDigitStr.split('_')[0]

        fileVec = img2vector('testDigits/%s' % testFileNameStr)
        classifierResult = classify0(fileVec, trainingMat, hwLabels, 3)
        print('the classifier came back with: %d, the real answer is: %d' %(int(classifierResult), int(classNumStr)))
        if classifierResult != classNumStr:
            errorCount += 1
    print('the total number of errors is: %d' % errorCount)
    print('the total error rate is: %f' % (errorCount / mTest))


handwritingClassTest()