机器学习实战 -- K-Nearest Neighbor Algorithm

实战 -- K-Nearest Neighbor Algorithm"/>

机器学习实战 -- K-Nearest Neighbor Algorithm

机器学习实战 – K-Nearest Neighbor Algorithm

KNN算法概述

KNN算法是一种分类算法，属于监督学习算法，它采用测量不同特征值之间的距离方法对实例进行分类。

基本原理

有一个样本数据集，称为训练集，其中的每一个数据都有标签，即它们的类别已知。输入没有标签的新数据，我们将新数据的每个特征和训练集中数据对应的特征进行比较，找出训练集中前K个与输入数据最相似的数据（通常以距离为依据）。

最后，选择这K个数据中出现次数最多的类别，作为新数据的类别，完成分类。

优缺点：

• 优点： 精度高、对异常值不敏感、无数据输入假定
• 缺点：计算复杂度高、空间复杂度高
• 使用数据范围：数值型、标称型（标称型的目标变量只在有限集合中取值，如真或假）

KNN算法的一般流程

1. 收集数据：any way
2. 准备数据：将数据转换为距离计算所需的数值，最好是结构化的数据格式
3. 分析数据：any way
4. 训练算法：KNN算法不需要训练（CNN之类的算法则需要训练）
5. 测试算法：计算算法对于测试集的正确率
6. 使用算法：首先输入样本数据，并将其结构化转换为算法能够识别的数据类型，然后运行KNN算法进行分类，最后应用计算出的分类做后续的处理。

KNN算法的伪代码

对未知类别属性的数据集中的每个点（当前点）依次执行以下操作：

1. 计算该点与已知类别数据集中的点的举了
2. 按照距离递增次序排序
3. 选取与当前点距离最小的K个点（通常使用欧氏距离）
4. 确定K个点所在类别出现的频率
5. 返回这K个点中出现频率最高的类别作为当前点的预测分类结果

代码

# KNN算法
def classify0(inX, dataSet, labels, k):# inX 为输入向量，函数将该向量分类dataSetSize = dataSet.shape[0]  # 数据集行数diffMat = tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat ** 2sqDistances = sqDiffMat.sum(axis=1)distances = sqDistances ** 0.5 # 距离sortedDisIndicies = distances.argsort() # 返回数组从小到大的索引值classCount = {}for i in range(k):voteIlabel = labels[sortedDisIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1# 计算k个实例中每一类出现的次数sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 以出现次数为依据进行排序# iteritems（） 将字典组合为元组列表m = sortedClassCount[0][0] # 距离最近的k个实例中，类别出现最多的类别return m

示例：使用KNN算法改进约会网站的配对效果

算法流程：

约会对象类型：

• 不喜欢的人 didntlike
• 魅力一般的人
• 极具魅力的人

对象的特征：

• 每年获得飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰激凌公升数

准备数据

将数据存储到numpy数组中

def file2matrix(filename):fr = open(filename)arrayOLines = fr.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines, 3))classLabelVector = []index = 0for line in arrayOLines:line = line.strip()listFromLine = line.split('\t')returnMat[index, :] = listFromLine[0:3]classLabelVector.append(listFromLine[-1])index += 1return returnMat, classLabelVector

分析数据：使用Matplotlib创建散点图

plt.rcParams['font.sans-serif']=['Simhei']
plt.scatter(datingDataMat[:, 1], datingDataMat[:, 2], s= 15 * array(datingLabels), c=15 * array(datingLabels))
plt.xlabel('玩游戏所占时间比')
plt.ylabel('周消耗冰激凌公升数')

准备数据：归一化数据

数据的不同特征值单位往往不同，造成不同特征数值差异很大，影响算法的正确性，所以对数据进行归一化，映射到 ( 0 , 1 ) (0,1) (0,1)区间。公式如下：
n e w V a l u e = o l d V a l u e − m i n m a x − m i n newValue = \frac{oldValue - min}{max -min} newValue=max−minoldValue−min​

# 归一化数据
def autoNorm(dataSet):minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = zeros(shape(dataSet))m = dataSet.shape[0]normDataSet = dataSet - tile(minVals, (m, 1))normDataSet = normDataSet / tile(ranges, (m, 1))return normDataSet, ranges, minVals

测试算法：在测试集上使用算法

我们使用算法在测试集上运行，利用测试集样本标签已知，得到算法在测试集上的错误率，来评价我们的算法好坏。

# 测试算法
def datingClassTest():hoRatio = 0.1 # 测试集的比例为0.1,训练集比列为0.9datingDataMat, datingLabels = file2matrix('datingTestSet.txt')        normMat, ranges, minVals = autoNorm(datingDataMat) # 数据归一化m = normMat.shape[0] # 数据个数numTestVecs = int(m * hoRatio)errorCount = 0 # 算法分类结果错误个数for i in range(numTestVecs):classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3) # 分类temp = label2int(datingLabels[i])print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, temp))if classifierResult != temp:errorCount += 1print("the total error rate is: %f" % (errorCount / numTestVecs))def label2int(datingLabel):# 将字符串标签转化为离散数字，便于处理m = datingLabelif m == 'didntLike':datingLabel = 1
#         colors.append('black')elif m == 'smallDoses':datingLabel = 2
#         colors.append('orange')elif m == 'largeDoses':datingLabel = 3
#         colors.append('green')return datingLabel

得到：

使用算法

利用算法，对未知的样本进行分类

# 使用算法，对未知数据进行分类
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 year?"))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])clasifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3) # 进行分类    print("You will probably like this person: ", resultList[int(clasifierResult) - 1])

示例：手写识别系统

识别0-9之内的手写数字

获取数据

分析数据

准备数据

我们知道，计算机中图片是一个矩阵。我们需要将图片的32×32矩阵转化为一个1024维向量，以便计算距离。

def img2vector(filename):# 将表示图片的(32,32)矩阵转换为(1, 1024)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

训练算法

测试算法

在测试集上运行算法，以验证算法的错误率。

# 在测试集上测试算法
def handwritingClassTest():from os import listdirhwLabels = [] # 标签列表trainingFileList = 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)trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)testFileList = listdir('testDigits')errorCount = 0.0 # 分类错误个数mTest = len(testFileList)for i in range(mTest):fileNameStr = testFileList[i]fileStr = fileNameStr.split('.')[0]classNameStr = int(fileStr.split('_')[0])vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) # (32,32)->(1, 1024)classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) # 对测试集数据进行分类print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNameStr))if classifierResult != classNameStr:errorCount += 1024print("\n the total number of errors is: %d" % errorCount)print("\nthe total error rate isL %f" % (errorCount / float(mTest)))

使用算法

略

使用算法

略