我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：
- 不喜欢的人
- 魅力一般的人
- 极其魅力的人
尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会那些魅力一般的人，而周末更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。
实验具体步骤如下：
- 收集数据：提供文本文件。
- 准备数据：使用Python解析文本文件。
- 分析数据：使用Matplotlib画二维扩散图。
- 训练算法：此步驟不适用于k近邻算法。
- 测试算法：使用海伦提供的部分数据作为测试样本。测试样本和非测试样本的区别：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
- 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。
准备数据：从文本文件中解析数据
海伦收集约会数据并存放在datingTestSet2.txt文本文件中，每个样本数据占据一行，总共有1000行。收集的样本主要包含以下3中特征：
- 每年获得的飞行常客里程数
- 玩视频游戏所耗时间百分比
- 每周消费的冰淇淋公斤数
在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在main.py中创建名为file2Matrix的函数，以此来处理输入格式问题。该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。
代码实现：
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines()) # get the number of lines in the file
returnMat = zeros((numberOfLines, 3)) # prepare matrix to return
classLabelVector = [] # prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('t')
returnMat[index, :] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
然后利用numpy函数库来处理，在Python命令提示符下输入下列命令：
import importlib importlib.reload(main)
datingDataMat,datingLabels = main.file2matrix('datingTestSet2.txt')
使用函数file2matrix读取文件数据，必须确保文件datingTestSet2.txt存储在我们的工作目录中。此外在执行这个函数之前，我们重新加载了main.py模块，以确保已更新的内容可以生效，否则Python将继续使用上次加载的main模块。
成功导入datingTestSet.txt文件数据后，可以通过命令：datingDataMat和datingLabels[0:20]来检查数据内容，输出结果大致如下：
分析数据：用Matplotlib创建散点图
在Python命令行环境中输入下列命令通过使用Matplotlib制作原始数据的散点图
>>>import matplotlib >>>import matplotlib.pyplot as plt >>>fig = plt.figure() >>>ax = fig.add_subplot(111) >>>ax.scatter(datingDataMat[:,1], datingDataMat[:,2]) >>>plt.show()
输出如下结果：
该结果表示散点图使用datingDataMat矩阵的第二、第三列数据，分别表示特征值”玩视频游戏所耗时间百分比“和”每周所消耗的冰淇淋公升数“。
由于没有使用样本分类的特征值，很难从上图看到任何有用的数据模式信息。我们一般会采用色彩或其他的记号来标记不同样本分类，以便更好地理解数据信息。Matplotlib库提供的scatter函数支持个性化标记散点图上的点。重新输入上面的代码，调用scatter函数时使用下列参数：
>>>ax.scatter(datingDataMat[:,1], datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
此代码利用变量datingLabels存储的类标签属性，在散点图上绘制了色彩不等、尺寸不同的点。下图利用颜色及尺寸标识了数据点的属性类别，因而我们可以从图上数据点所属三个样本分类的区域轮廓。
此处遇到一个问题，直接导入scatter函数时会出现name ‘array’ is not defined 的错误，需在调用scatter函数前重新导入一次numpy库。
准备数据：归一化数值
下面的表中提取了四组数据，如果想要计算样本3和样本4之间的距离，可以使用下面的方法：
我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于其他的两个特征-玩视频游戏后每周消费的冰淇淋公升数-的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。
约会网站原始数据改进之后的样本数据表：
在处理这种不同取值范围的特征值时，我们通常采用的方法时将数值归一化，如将取值范围处理为0-1或者-1到1之间。下面的公式可以将任意取值范围的特征值转换到0到1区间内的取值，newValue=(oldValue-min)/(max-min)。其中，max和min分别代表数据集中的最大特征值和最小特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。我们需要在文件kNN.py中增加了一个新函数autopNorm(),该函数可以将数字特征值转换为0-1区间。
代码实现如下：
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m, 1))
normDataSet = normDataSet / tile(ranges, (m, 1)) # element wise divide
return normDataSet, ranges, minVals
在函数autonorm()中，我们将每列的最小值放在变量minVals中，将最大值放在变量maxVals中，其中dataSet.min(0)中的参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值。然后，函数计算可能的取值范围，并创建新的返回矩阵。正如前面给出的公式，为了归一化特征值，我们必须使用当前值减去最小值，然后除以取值范围。需要注意的是，特征矩阵有10003个值*，而minVals和range的值都为1*3.为了解决这个问题，我们使用numpy库中的tile()函数将变量内容复制成输入矩阵同样大小的矩阵，注意这是具体特征值相除，而对于某些数值处理软件包，/可能意味着矩阵除法，矩阵除法需要使用函数linalg.slove(matA,matB).
在Python命令提示符下输入下列命令，重新加载main.py，执行autoNorm函数
import importlib importlib.reload(main) normMat, ranges, minVals = main.autoNorm(datingDataMat) normMat
检测函数的执行结果为：
测试算法：作为完整程序验证分类器
上面我们已经按照需求做了处理，下面我们将测试分类器的结果，如果分类器正确率满足要求，海伦就可以使用这个软件来处理约会网站提供的约会名单了。机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。后面我们会使用更高级的方法，当前我们还是采用最原始的方法。但是要注意的是，10%的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定的数据排序，所以我们可以随意选择10%数据而不影响随机性。
前面我们已经提到可以使用错误率来检测分类器的性能。对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为0，而错误率为1.0的分类器不会给出任何正确的分类结果。代码里我们定义一个计数器变量，每次分类器错误地分类数据，计数器就加1，程序执行完成之后计数器的结果除以数据点总数即是错误率。
为了测试分类器效果，在main.py文件中创建函数datingClassTest，该函数是自包含的，你可以在任何时候在Python运行环境中使用该函数测试分类器效果，在main.py中输入下面的代码：
def datingClassTest():
hoRatio = 0.10 # 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)
在Python中重新加载main模块，输入main.datingClassTest(),执行分类器测试程序，我们将得到下面的输出结果：
>>>main.datingClassTest()
可以看到分类器的错误率为0.05，这是一个不错的结果。我们可以改变函数datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量的变化而增加。
使用算法：构建完整可用系统
上面我们对分类器进行了测试，现在终于可以使用这个分类器为海伦来对人们进行分类。我们增加一小段程序，通过该程序海伦在约会网站上找到某个人并输入他的信息。程序会给出他对对方喜欢程度的预测值。
将下面的代码加入到main.py并重新载入main,执行过程和结果如下图：
#输入某人的信息，便得出对对方喜欢程度的预测值
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(”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]
按照课本上的代码会出现如下错误
将代码中的raw_input改为input即可正确，结果如下：
实例分析
使用K-近邻分类器的手写识别系统。简单起见，这里构造的系统只能识别数字0到9。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素*32像素的黑白图像。当前使用文本格式存储图像，即使不能有效的利用空间，但是为了方便理解，还是将图像转换成文本格式。
流程步骤
- 收集数据：提供文本文件。
- 处理数据：编写imgVector()函数，将图像格式转换成分类器使用的向量格式。
- 分析数据：在Python命令提示符中检查数据，确保它符合要求。
- 训练算法：此步骤不适用于k-近邻算法。
- 测试算法：编写函数使用提供的部分数据集作为测试样本，对学习算法进行测试。
- 使用算法：本例没有完成此步骤。
准备数据：将图像转换为测试向量
目录trainingDigits中包含了大约2000个例子，每个数字大约有200个样本；测试文件testDigits中包含了大约900个测试数据。两组数据没有重叠。使用trainingDigits中的数据训练分类器，使用testDigits的数据测试分类器效果。为了使用kNN算法分类器必须将一个3232的二进制矩阵转换为11024的向量，以便我们使用分类器处理数字图像信息。
将下列代码输入到main.py中：
def img2vector(filename):
returnVect = zeros((1, 1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0, 32 * i + j] = int(lineStr[j])
return returnVect
测试代码及测试结果：
测试算法：使用K-近邻算法识别手写数字
构造handwritingClassTest( )函数对分类器进行测试，并将其写入main.py文件中。但在写代码之前需先确保将from os import listdir写入文件的起始部分，其功能是从os模块中导入函数listdir，它可以列出给定目录的文件名。
输入代码：
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = listdir('testDigits') # iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
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)))
在命令行中输入main.handwritingClassTest()来测试函数结果，其结果如下：
K-近邻算法识别手写数字数据集错误率为1.06%。
在导入部分和路径出现了许多问题，还有一些因python版本不兼容的问题导致一些错误，例如：上面提到的input、items等的修改。通过本次实验加深了我对KNN算法的理解，同时也增强了我的动手能力，后续将多测试几遍，将内容继续完善。
以下为在实验中遇到并已解决的问题：
Array()接受1到2个位置参数，但给出了4个
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort()
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines()) #get the number of lines in the file
returnMat = zeros((numberOfLines,3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('t')
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
