《机器学习实战》笔记（1） 第二章

k-近邻算法

2.1

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

2. 特点：

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

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

4. k-近邻算法的一般流程：

   • 收集数据：可以使用任何方法
   • 准备数据：距离计算所需要的数值，最好是结构化的数据格式
   • 分析数据：可以使用任何方法
   • 训练算法：此步骤不适用 k- 近邻算法
   • 测试算法：计算错误率
   • 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行 k-近邻算法判定输入数据分别输入哪个分类，最后应用对计算出的分类执行后续的处理。

5. 代码部分：

   • 准备：使用 python 导入数据

     def createDataSet():
         group1 = [[1, 1.1], [1, 1], [0, 0], [0, 0.1]]
         group = array(group1)
         label = ['A', 'A', 'B', 'B']
         return group, label
     

   • 实施 kNN 分类算法

     伪代码如下：

     ​ 对位置类属性的数据集中的每个点依次执行以下操作：

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

     def classfy(inX, dataSet, labels, k):
        # 行数
         dataSize = dataSet.shape[0]
         # tile(inX,(a,b)): 将矩阵 inX 重复a行b列
         # diffMat 表示 inX 在各个维度上与样本数据集中每个数据的距离
         diffMat = tile(inX, (dataSize, 1)) - dataSet
         sqDiffMat = diffMat ** 2
         # 矩阵行相加，得到一个 dataSize 行的矩阵
         sqDistance = sqDiffMat.sum(axis=1)
         # 距离
         distance = sqDistance ** 0.5
         #　index 排序
         sortedDistance = distance.argsort()
         
         # 类型 dict， key 为 标签值， value 为该值出现的次数
         classType = {}
         for index in range(k):
             item_label = label[sortedDistance[index]]
             classType[item_label] = classType.get(item_label, 0) + 1
         sortClassType = sorted(classType.items(), key=operator.itemgetter(1), reverse=True)
         return sortClassType[0][0]
     

     KNN.classify([0,0],group,labels,3)
     

6. 注意点：

   • 归一化数据：数字差值最大的属性对计算结果的影响最大，如果特征等权重，该特征不应该严重影响计算结果。要处理这种不同取值范围的特征值，我们通常采用的方法是将数值归一化。如将取值范围处理为0到1或者-1到1之间。

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