Machine Learning In Action 学习笔记之 KNN算法

kNN算法应该是整个机器学习算法里最最容易理解的算法。

k-近邻算法

它采用测量不同特征值之间的距离来进行分类，求距离是整个算法中最核心的部分。

K-近邻，顾名思义，取离测试样例最近的k个已知类型样例，其中这个测试样例的类别即为这k个样例中占最多类别的样例类别。

下图为KNN的原理：

图中，如果K=3，由于红色三角形所占比例为2/3最高，绿色圆将被赋予红色三角形那个类别，如果K=5，由于蓝色正方形比例为3/5最高，因此绿色圆被赋予蓝色正方形类别。

所以算法真的很容易很容易理解。

kNN算法的一般流程

• 收集数据：可使用任何方法。
• 准备数据：距离计算所需要的数值，这里最好为结构化数据。
• 分析数据：可使用任何方法
• 训练算法：kNN不需要训练。
• 测试算法：计算错误率。
• 使用算法：对输入样本数据采用kNN进行判断类别，然后进行后续操作。

---

简单例子

1. 导入数据

创建一个数据集，带有坐标点和其类别。

def createDataSet():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

2. kNN算法

欧氏距离公式为：
$d = \sqrt{(xA_0-xB_0)^2 + (xA_1 - xB_1)^2}$d=(xA0​−xB0​)2+(xA1​−xB1​)2​

#inx:用于分类的输入向量
#dataSet:输入样本集
#labels:标签向量
#k表示用于选择最近邻居的数目
def classify0(inX, dataSet, labels, k):
    # numpy函数shape[0]返回dataSet的行数
    dataSetSize = dataSet.shape[0]
    #距离计算
    #将inX重复dataSetSize次并排成一列
    diffMat = np.tile(inX, (dataSetSize,1))-dataSet
    # 二维特征相减后平方（用diffMat的转置乘diffMat）
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    #开方得到距离
    distances = sqDistances ** 0.5
    #print('排序之前的距离向量为')
    #print(distances)
    sortedDistIndicies = distances.argsort()#argsort返回的distances值从小到大的索引值
    #print('排序之后的距离向量为')
    #print(sortedDistIndicies)
    classCount = {}
    #选择距离最小的k个点
    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)
    #print(sortedClassCount)
    #返回次数最多的类别
    return sortedClassCount[0][0]

所以当执行完

kNN.classify0([0,0], group, labels, 3)

输出类别 B

---

使用kNN算法改进约会网站的配对效果

1. 准备数据：从文本文件中解析数据

首先给的文件文本datingTestSet.txt中的数据为：

40920 8.326976 0.953952 largeDoses
14488 7.153469 1.673904 smallDoses
26052 1.441871 0.805124 didntLike
75136 13.147394 0.428964 didntLike
38344 1.669788 0.134296 didntLike
72993 10.141740 1.032955 didntLike
35948 6.830792 1.213192 largeDoses
42666 13.276369 0.543880 largeDoses
67497 8.631577 0.749278 didntLike
35483 12.273169 1.508053 largeDoses
50242 3.723498 0.831917 didntLike
63275 8.385879 1.669485 didntLike
5569 4.875435 0.728658 smallDoses
51052 4.680098 0.625224 didntLike
77372 15.299570 0.331351 didntLike
43673 1.889461 0.191283 didntLike
61364 7.516754 1.269164 didntLike
69673 14.239195 0.261333 didntLike
15669 0.000000 1.250185 smallDoses
28488 10.528555 1.304844 largeDoses
6487 3.540265 0.822483 smallDoses
37708 2.991551 0.833920 didntLike
22620 5.297865 0.638306 smallDoses
…

前三列表示的表示特征：

• 每年获得的飞行常客里程数
• 玩游戏所耗时间百分比
• 每周消费的冰淇淋公斤数

第四列表示的是类别（有三种类别）：

• didntLike: 不喜欢的人
• smallDoses: 魅力一般的人
• largeDoses: 极具魅力的人

先将文本转换到Numpy：

def loadData(filename):
    fr = open(filename)
    features = []
    labels = []
    for line in fr.readlines():
        list = line.strip().split()
        arr = []
        for i in range(3):
            arr.append(float(list[i]))
        features.append(arr)
        if (list[-1] == 'didntLike'):
            labels.append(1)
        elif(list[-1] == 'smallDoses'):
            labels.append(2)
        else:
            labels.append(3)
    # list转化为numpy类型
    features = np.array(features)
    labels = np.array(labels)
    #print(features, labels)
    return features, labels

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

因为有三个特征，所以直接画出三维散点图即可

def showdatas(datingDataMat, datingLabels):
    ax = plt.figure().add_subplot(111, projection='3d')
    # 基于ax变量绘制三维图
    # xs表示x方向的变量
    # ys表示y方向的变量
    # zs表示z方向的变量，这三个方向上的变量都可以用list的形式表示
    # m表示点的形式，o是圆形的点，^是三角形（marker)
    # c表示颜色（color for short）
    data1 = []
    data2 = []
    data3 = []
    for i in range(datingDataMat.shape[0]):
    	# 取出类别为1的数据
        if(datingLabels[i] == 1):
            list = []
            list.append(datingDataMat[i, 0])
            list.append(datingDataMat[i, 1])
            list.append(datingDataMat[i, 2])
            data1.append(list)
        # 取出类别为2的数据
        elif(datingLabels[i] == 2):
            list = []
            list.append(datingDataMat[i, 0])
            list.append(datingDataMat[i, 1])
            list.append(datingDataMat[i, 2])
            data2.append(list)
        # 取出类别为3的数据
        else:
            list = []
            list.append(datingDataMat[i, 0])
            list.append(datingDataMat[i, 1])
            list.append(datingDataMat[i, 2])
            data3.append(list)
    # 转化为numpy类型
    data1 = np.array(data1)
    data2 = np.array(data2)
    data3 = np.array(data3)
    # 按照类别画出图像
    ax.scatter(data1[:, 0], data1[:, 1], data1[:, 2], c='r', marker='.')  # 点为红色
    ax.scatter(data2[:, 0], data2[:, 1], data2[:, 2], c='b', marker='.')  # 点为红色
    ax.scatter(data3[:, 0], data3[:, 1], data3[:, 2], c='g', marker='.')  # 点为红色
    # 设置坐标轴
    ax.set_xlabel('X Label:Number of frequent flyer miles earned per year')
    ax.set_ylabel('Y Label:Percentage of time spent playing video games')
    ax.set_zlabel('Z Label:Liters of ice cream consumed per week')
    # 显示图像
    plt.show()

结果为:

3. 准备数据：归一化数值

如果我们计算这样的距离
$\sqrt{(0 - 67)^2 + (20000-32000)^2 + (1.1 - 0.1)^2}$(0−67)2+(20000−32000)2+(1.1−0.1)2​
可以发现第二个特征数值很大，这样对计算结果影响就非常大，但如果这三种特征是同等重要的，那么就需要将数值进行归一化。如将取值范围处理到0到1或者-1到1之间。
使用公式：
$newValue = (oldValue - min) / (max - min)$newValue=(oldValue−min)/(max−min)
其中 $min$min 和 $max$max 分别是数据集中的最小特征值和最大特征值。

具体代码如下：

#归一化特征值
def autoNorm(dataSet):
    #获取数据的最小值
    minVals = dataSet.min(0)
    #获取数据的最大值
    maxVals = dataSet.max(0)
    #最小值与最大值的范围
    ranges = maxVals - minVals
    # shape(dataSet)返回dataSet的矩阵行列数
    normDataSet = np.zeros(np.shape(dataSet))
    # numpy函数shape[0]返回dataSet的行数
    m = dataSet.shape[0]
    # 原始值减去最小值（x-xmin）
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    # 差值处以最大值和最小值的差值（x-xmin）/（xmax-xmin）
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    # 归一化数据结果，数据范围，最小值
    return normDataSet, ranges, minVals

4. 测试数据

def datingClassTest():
    # 打开文件名
    filename = "datingTestSet.txt"
    # 将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
    datingDataMat, datingLabels = file2matrix(filename)
    # 取所有数据的10% hoRatio越小，错误率越低
    hoRatio = 0.10
    # 数据归一化，返回归一化数据结果，数据范围，最小值
    normMat, ranges, minVals = autoNorm(datingDataMat)
    # 获取normMat的行数
    m = normMat.shape[0]
    # 10%的测试数据的个数
    numTestVecs = int(m * hoRatio)
    # 分类错误计数
    errorCount = 0.0
    for i in range(numTestVecs):
        # 前numTestVecs个数据作为测试集，后m-numTestVecs个数据作为训练集
        # k选择label数+1（结果比较好）
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], \
                                     datingLabels[numTestVecs:m], 4)
        print("分类结果:%d\t真实类别:%d" % (classifierResult, datingLabels[i]))
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("错误率:%.2f%%" % (errorCount / float(numTestVecs) * 100))

5. 使用算法

自己输入三个特征的数，然后通过这个算法预测结果。

def classifyPerson():
    resultList = ['讨厌','有些喜欢','非常喜欢']
    # 三维特征用户输入
    percentTats = float(input("玩视频游戏所消耗时间百分比："))
    ffMiles = float(input("每年获得的飞行常客里程数："))
    iceCream = float(input("每周消费的冰淇淋公升数："))
    filename = "datingTestSet.txt"
    datingDataMat, datingLabels = file2matrix(filename)
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([percentTats, ffMiles, iceCream])
    # 测试集归一化
    norminArr = (inArr - minVals) / ranges
    # 返回分类结果
    #print(datingLabels)
    classifierResult = classify0(norminArr, normMat, datingLabels, 4)
    # 打印结果
    print("你可能%s这个人" % (resultList[classifierResult - 1]))