机器学习:使用k近邻分类(knn)

2021年8月4日16:27:05 发表评论
摘要

本文介绍了机器学习中KNN的原理,然后通过一个例子来说明KNN是如何做到分类的。

在机器学习中,存在一种很简单的分类方法,那就是knn(k-nearest neighbors)。

预备知识

首先我们把数据集划分为两部分,一部分为训练集,另一部分为测试集。他们的比值可能是2:8,也可能是1:9,总之是训练集样本数量是远多于测试集的。

我们的目的是对那些测试样本进行分类,我们先假设不知道它们的标签是什么(但我们实际上是知道的)

原理

knn的原理是,从测试样本中取一个数据M,然后计算它和所有训练样本的距离,再对这些距离进行排序(从小到大),然后取前k个距离。其中这k个距离对应样本的标签中,占比最大的标签,就是M的标签。

评估

我们可以根据上面那个原理,对每个测试样本用knn来预测它们的标签,再对比它们真实的标签,就能得到一个正确率。正确率越高,knn的效果越好。

改进

knn的大体思路是这样的,你可以根据实际情况来选择k的数目,以及距离度量函数来适应这个数据集。

例子

我的一个朋友老喜欢用在线约会网站找对象,虽然网站给她推荐很多人,但不是每个人她都喜欢。经过一番总结,她发现曾经交往过三类人:

  • 不喜欢的人
  • 魅力一般的人
  • 很有魅力的人

尽管有这个规律,但她做不到将推荐的人进行分类。但我们的分类软件可以试图给她分类,于是我们的海王朋友收集了一些网站没有记录的数据,她认为有助于给匹配的对象归类。

海王收集的样本主要包含3种特征

  • 每年飞行里程数
  • 看视频玩游戏时间占比
  • 每周冰激凌消费公升数

样本如下:

注:本例的数据集可在这里找到

里程       占比       公升        喜爱程度(这一行文件是没有的)
40920   8.326976   0.953952   largeDoses
14488  7.153469   1.673904   smallDoses
26052  1.441871   0.805124   didntLike
75136  13.147394  0.428964   didntLike

步骤

  1. 读取文件
  2. 归一化
  3. k近邻算法
  4. 评估

1.读取文件

这个应该挺容易理解的,不解释了,实在不理解可以在下面留言。

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

2.归一化

因为每个特征,它们的数值范围是不一样的,而我们在求距离的时候,数值大的数据对距离的影响更大。而我们认为这三个特征应该是一样重要,所以我们把每个特征都缩放到[0,1]这个区间,这个步骤也叫归一化。

这个也是 不解释,一看就懂了。关于tile这个函数,解释起来比较复杂,网上自己查查。

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))
    return normDataSet, ranges, minVals

3.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)
    # 求根号
    distance = sqDistance ** 0.5
    # 下标排序,下标就是训练样本的标号
    sortedDistIndicies = distance.argsort()
    classCount = {}
    for i in range(k):
        # 获取下标的标签,就是训练样本的标签
        voteIlabel = labels[sortedDistIndicies[i]]
        # 统计标签
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 标签排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 占比最多的标签
    return sortedClassCount[0][0]

4.评估

def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    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)))

最后,有什么不懂的就在评论区留言吧,博客我一般几天都会看一次的。码字不易,懂了点赞!

flyingsheep

发表评论