首页 > 代码库 > K-邻近(KNN)算法

K-邻近(KNN)算法

K近邻分类算法概述

K-近邻算法是机器学习之中最简单的分类算法之一,它采用测量不同特征值之间的距离方法进行分类。它的工作原理是:存在一个样本数量集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似或最近邻的分类标签。一般类说,我们只选择样本数据集中前K个最相似的数据,这就是K-近邻算法中K的出处,通常K是不大于20的整数,最后,选择前K个最相似数据中出现次数最多的分类,作为新数据的分类。

 

K近邻算法步骤

  1. 计算已知类别数据集中的电与当前点之间的距离
  2. 按照距离递增次数排列
  3. 选取与当前点距离最小的K个点
  4. 确定前K个点所在类别的出现频率
  5. 返回前K个点出现频率最高的类别作为当前点的预测分类

在计算点和点之间的距离时,我们使用欧几里得距离:

技术分享

 

代码1-1实现K-近邻算法

# coding:utf-8

from numpy import *
import operator


# 生成数据集
def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    lables = [‘A‘, ‘A‘, ‘B‘, ‘B‘]
    return group, lables


def classify0(inX, dataSet, lables, 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 = {}
    # 选取前K个距离最小的点
    for i in range(k):
        voteIlable = lables[sortedDistIndicies[i]]
        classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

  

使用K-近邻算法改进社交网站的推荐效果

艾米在社交网站一直和来自天南地北的的人聊天,但并不是所有人她都喜欢与之交往,经过一番总结,她发现曾交往过三类人:

  1. 不善言谈的人
  2. 幽默感一般的人
  3. 极具幽默的人

艾米将他交往过的人形成数据并存储在datingTestSet2.txt文件中,每个样本数据占据一行,总共有1000行,每一行包含以下3种特征:

  1. 每年飞行程数
  2. 玩游戏时间所耗百分比
  3. 每周消费冰淇淋公升数 
表1-2社交网站样本数据
 

玩游戏时间所耗百分比

每年飞行程数

每周消费冰淇淋公升数 

样本分类
1 8.326976 40920 0.953952 3
2 7.153469 14488 1.673904 2
3 1.441871 26052 0.805124 1

 

数据集地址:http://pan.baidu.com/s/1hsvbxXE

 

归一化数值

表1-2给出了三组数据,如果想计算样本1和样本2之间的距离,用欧几里得公式[(8.326976-7.153469)2+(40920-14488)2+(0.953952-1.673904)2]1/2  ,可以很容易发现,方程中数字差值最大的属性对计算结果的影响最大,也就是说每年飞行程数对结果的影响远大于其他两个特征——玩游戏时间所耗百分比和每周消费冰淇淋公升数,然而,如果三个特征同等重要,每年飞行程数不应该严重影响到计算结果,在处理这种不同取值范围的特征值时,我们通常采用的方法是将数值归一化,如将取值范围处理为0到1或-1到1之间,下面的公式可以将任意取值范围的特征值转化为0到1区间内的值:

newVaule = (oldValue-min)/(max-min)

其中min和max分别是数据集中最小特征值和最大特征值。

 

代码1-3

# 读取文件
def fileMatrix(fileName):
    fr = open(fileName)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    mat = zeros((numberOfLines, 3))
    classLableVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split("\t")
        mat[index, :] = listFromLine[0:3]
        classLableVector.append(int(listFromLine[-1]))
        index += 1
    return mat, classLableVector


# 归一化特征值
def autoNorm(dataSet):
    # 从每一列选取最小值
    minVals = dataSet.min(0)
    # 从每一列选取最大值
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(dataSet.shape)
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minVals


# 分类器测试数据集
def datingClassTest(fileName):
    hoRatio = 0.10
    datingDataMat, datingLabels = fileMatrix(fileName)
    mat, ranges, minVals = autoNorm(datingDataMat)
    m = mat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(mat[i, :], mat[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))

  

 代码1-3中,函数datingClassTest首先使用了fileMatrix和autoNorm函数从文件中读取数据,并将其转化为归一化特征值,接着划分mat数据中,哪些数据用于测试,哪些数据用于分类器的训练样本,然后将这两部分数据沮洳到分类器classify0中。最后函数计算错误率并输出结果,用上面的数据集测试,可以得到错误率是5%,这是一个还不错的结果,这个例子可以表明,我们可以正确的预测分类,而错误率仅5%,通过输入未知对象的属性信息,由分类算法可以帮助我们预测输入的对象是不善言谈的人、还是幽默感一般或极具幽默感的人

 

代码1-4为本章代码整合

# coding:utf-8

from numpy import *
import operator


# 生成数据集
def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    lables = [‘A‘, ‘A‘, ‘B‘, ‘B‘]
    return group, lables


def classify0(inX, dataSet, lables, 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 = {}
    # 选取前K个距离最小的点
    for i in range(k):
        voteIlable = lables[sortedDistIndicies[i]]
        classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


# 读取文件
def fileMatrix(fileName):
    fr = open(fileName)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    mat = zeros((numberOfLines, 3))
    classLableVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split("\t")
        mat[index, :] = listFromLine[0:3]
        classLableVector.append(int(listFromLine[-1]))
        index += 1
    return mat, classLableVector


# 归一化特征值
def autoNorm(dataSet):
    # 从每一列选取最小值
    minVals = dataSet.min(0)
    # 从每一列选取最大值
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(dataSet.shape)
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minVals


# 分类器测试数据集
def datingClassTest(fileName):
    hoRatio = 0.10
    datingDataMat, datingLabels = fileMatrix(fileName)
    mat, ranges, minVals = autoNorm(datingDataMat)
    m = mat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(mat[i, :], mat[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))

  

K-邻近(KNN)算法