第二章 k-近邻算法

一时失言乱红尘 2022-05-08 14:06 182阅读 0赞

# 第二章 k-近邻算法 #

## 2.1 k-近邻算法概述（KNN） ##

k-近邻算法采用测量不同特征值之间的距离方法进行分类。

*  **优点**：精度高、对异常值不敏感、无数据输入假定。
 *  **缺点**：计算复杂度高、空间复杂度高。
 *  **适用数据范围**：数值型和标称型。

**工作原理：**

存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

### 2.1.1 准备：使用 Python 导入数据 ###

from numpy import *
    import operator
    
    
    # 创建数据集和标签
    def createDataSet():
        group = array([
            [1.0, 1.1],
            [1.0, 1.0],
            [0.0, 0.0],
            [0.0, 0.1]
        ])
        labels = ['A', 'A', 'B', 'B']
        return group, labels
    
    
    if __name__ == '__main__':
        group, labels = createDataSet()
        print(group)
        print(labels)

[[1.  1.1]
     [1.  1. ]
     [0.  0. ]
     [0.  0.1]]
    ['A', 'A', 'B', 'B']

### 2.1.2 从文本文件中解析数据 ###

使用k-近邻算法将每组数据划分到某个类中，其伪代码如下：

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

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

def classify0(inx, dataSet, labels, k):
        """
        分类器
        :param inx: 用于分类的输入向量
        :param dataSet: 输入的训练样本集
        :param labels: 标签向量
        :param k: 用于选择最近邻居的数目
        :return:  返回前k个点出现频率最高的类别作为当前点的预测分类
        """
        dataSetSize = dataSet.shape[0]      # shape[0] 计算矩阵的行数，shape[1]计算矩阵的列数
        # 计算距离
        diffMat = tile(inx, (dataSetSize, 1)) - dataSet     # 数组inX以dataSetSize行1列重复
        sqDiffMat = diffMat**2
        sqDistances = sqDiffMat.sum(axis=1)     # array中每行元素的和，这些和再组成一个array
        distances = sqDistances**0.5
    
        # 选择距离最小的k个点
        sortedDistIndicies = distances.argsort()
        classCount = {
        }
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            # dict提供的get方法，如果key不存在，可以返回None，或者自己指定的value，这里classCount.get(voteIlabel, 0)是指不存在相对应key值的value则返回0
            classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    
        # 排序
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]

## 2.2 示例：使用 k-近邻算法改进约会网站的配对效果 ##

我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：

*  不喜欢的人
 *  魅力一版的人
 *  极具魅力的人

尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会那些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。

### 2.2.1 准备数据：从文本文件中解析数据 ###

海伦的样本主要包含以下3种特征

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

def file2matrix(file_name):
        """
            将待处理数据的格式改变为分类器可以接受的格式
            :param file_name: 文件名
            :return:
                returnMat: 为训练样本矩阵
                classLabelVector: 类标签向量
            """
        love_dictionary = {
        'largeDoses': 3, 'smallDoses': 2, 'didntLike': 1}
        fr = open(file_name)
        arrayOLines = fr.readlines()
        numberOfLines = len(arrayOLines)  # get the number of lines in the file
        returnMat = np.zeros((numberOfLines, 3))  # prepare matrix to return
        classLabelVector = []  # prepare labels return
        index = 0
        for line in arrayOLines:
            line = line.strip()
            listFromLine = line.split('\t')
            returnMat[index, :] = listFromLine[0:3]
            if (listFromLine[-1].isdigit()):
                classLabelVector.append(int(listFromLine[-1]))
            else:
                classLabelVector.append(love_dictionary.get(listFromLine[-1]))
            index += 1
        return returnMat, classLabelVector

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

def show(data, labels):
        fig = plt.figure()
        font = FontProperties(fname=r'C:\Windows\Fonts\simhei.ttf')
        ax = fig.add_subplot(111)
        plt.xlabel('玩视频游戏所耗时间百分比', fontproperties=font)
        plt.ylabel('每年获取的飞行常客里程数', fontproperties=font)
        # ax.scatter(data[:, 0], data[:, 1], 15.0 * np.array(labels), 15.0 * np.array(labels))
        label = np.array(labels)
        idx_1 = np.where(label == 1)
        p1 = ax.scatter(data[idx_1, 0], data[idx_1, 1], color='r', label='不喜欢', s=20)
        idx_2 = np.where(label == 2)
        p2 = ax.scatter(data[idx_2, 0], data[idx_2, 1], color='b', label='魅力一般', s=10)
        idx_3 = np.where(label == 3)
        p3 = ax.scatter(data[idx_3, 0], data[idx_3, 1], color='g', label='极具魅力', s=30)
        plt.legend(loc='upper left')
        plt.show()

![在这里插入图片描述][70]

### 2.2.3 准备数据：归一化数值 ###

表2-3给出了提取的四组数据，如果想要计算样本3和样本4之间的距离，可以使用下面的方法：  
 d = ( 0 − 67 ) 2 + ( 20000 − 32000 ) 2 + ( 1.1 − 0.1 ) 2 d=\\sqrt\{\\left(0-67\\right)^2+\\left(20000-32000\\right)^2+\\left(1.1-0.1\\right)^2\} d=(0−67)2\+(20000−32000)2\+(1.1−0.1)2  
表2-3 约会网站原始数据改进之后的样本数据

<table> 
 <thead> 
  <tr> 
   <th align="center">样本</th> 
   <th align="center">玩视频游戏所耗时间百分比</th> 
   <th align="center">每年获得的飞行常客里程数</th> 
   <th align="center">每周消费的冰淇淋公升数</th> 
   <th align="center">样本分类</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">1</td> 
   <td align="center">0.8</td> 
   <td align="center">400</td> 
   <td align="center">0.5</td> 
   <td align="center">1</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="center">12</td> 
   <td align="center">134000</td> 
   <td align="center">0.9</td> 
   <td align="center">3</td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="center">0</td> 
   <td align="center">20 000</td> 
   <td align="center">1.1</td> 
   <td align="center">2</td> 
  </tr> 
  <tr> 
   <td align="center">4</td> 
   <td align="center">67</td> 
   <td align="center">32 000</td> 
   <td align="center">0.1</td> 
   <td align="center">2</td> 
  </tr> 
 </tbody> 
</table>

我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于表中其他两个特征——玩视频游戏的和每周消费冰淇淋公升数——的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0到1或者-1到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  
其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。

def autoNorm(data):
        minVals = data.min(0)   # 参数0使得函数可以从列中选取最小值
        maxVals = data.max(0)
        ranges = maxVals - minVals
        normDataSet = np.zeros(np.shape(data))
        m = data.shape[0]
        normDataSet = data - np.tile(minVals, (m, 1))
        normDataSet = normDataSet / np.tile(ranges, (m, 1))  # element wise divide
        print(normDataSet)
        return normDataSet, ranges, minVals

### 2.2.4 测试算法：作为完整程序验证分类器 ###

机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为0，而错误率为1.0的分类器不会给出任何正确的分类结果。

# 测试分类器
    def datingClassTest(dataMat, dataLabel):
        hoRatio = 0.10
        normData, ranges, minValues = autoNorm(dataMat)
        m = normData.shape[0]
        numTestVecs = int(hoRatio * m)  # 测试数据占比0.1
        errorCount = 0.0
        for i in range(numTestVecs):
            classifierResult = classify0(normData[i, :],
                                         normData[numTestVecs:m, :],
                                         dataLabel[numTestVecs:m], 3)
            print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, dataLabel[i]))
            if classifierResult != dataLabel[i]:
                errorCount += 1.0
        print("the total error count is: ", errorCount)
        print("the total error rate is: %f" % (errorCount / float(numTestVecs)))

### 2.2.5 使用算法：构建完整可用系统 ###

上面我们已经在数据上对分类器进行了测试，现在终于可以使用这个分类器为海伦来对人们分类。我们会给海伦一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息。程序会给出她对对方喜欢程度的预测值。

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('./data/datingTestSet.txt')
        normDataSet, ranges, minVals = autoNorm(datingDataMat)
        inArr = np.array([percentTats, ffMiles, iceCream])
        classifierResult = classify0((inArr - minVals) / ranges, datingDataMat, datingLabels, 3)
        print("you will probably like this person:", resultList[classifierResult - 1])

## 2.3 示例：手写识别系统 ##

本节我们一步步地构造使用k-近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字0到9。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素×32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

![在这里插入图片描述][70 1]

![在这里插入图片描述][70 2]

### 2.3.1 准备数据：将图像转换为测试向量 ###

# 将图像转换为向量
    def img2vector(file_name):
        returnVect = np.zeros((1, 1024))
        fr = open(file_name)
        arrayOLines = fr.readlines()
        numberOfLines = len(arrayOLines)
        for i in range(numberOfLines):
            lineStr = arrayOLines[i]  # fr.readline()
            for j in range(32):     # 并将每行的头32个字符值存储在NumPy数组中
                returnVect[0, 32 * i + j] = int(lineStr[j])
        return returnVect

### 2.3.2 测试算法：使用 k-近邻算法识别手写数字 ###

# 测试分类器
    def handwritingClassTest():
        hwLabels = []
        trainingFileList = listdir('./data/trainingDigits')
        m = len(trainingFileList)
        trainingMat = np.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('./data/trainingDigits/%s' % fileNameStr)
        testFileList = listdir('./data/testDigits')
        errorCount = 0.0
        mTest = len(testFileList)
        for j in range(mTest):
            fileNameStr = testFileList[j]
            fileStr = fileNameStr.split('.')[0]
            classNumStr = int(fileStr.split('_')[0])
            vectorUnderTest = img2vector('./data/testDigits/%s' % fileNameStr)
            classifiedResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
            print('the classifier came back with: %d, the real answer is : %d' % (classifiedResult, classNumStr))
            if classifiedResult != classifiedResult:
                errorCount += 1.0
        print('\n the total number of errors is: %d' % errorCount)
        print('\n the total error rate is: %f' % (errorCount / float(mTest)))

## 2.4 小结 ##

k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据集的很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。

k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。

[70]: /images/20220508/18c5f8a286d24c10a449f33c74447605.png
[70 1]: /images/20220508/79c36c56bb43439e8d77b8bbdd15ee4f.png
[70 2]: /images/20220508/b32b922ff6ac4b7d951e2d9a905122a6.png