使用K-近邻算法构建鸢尾属分类器
4952字,阅读需时17分钟

鸢尾属是一种草本植物,约有300多种分类。现在需要建立一个分类器,对鸢尾属进行自动分类。

有两种自动分类方式:一种方式是提供一些已经分类完成的样本,样本包括鸢尾属的一组特征和类别标识,将待分类的鸢尾属特征与所有样本的特征进行比较,与待分类鸢尾属特征最接近的样本所属的类别,就是待分类鸢尾属的类别;另外一种方式是没有分类完成的样本,程序需要自动对待分类的鸢尾属进行归类,即该分类方法没有正确的答案供分类算法参考,算法需要按照开发者设定的参数对鸢尾属进行分类。

第一种分类算法称为监督学习,有样本数据可供参考;第二种分类方法为无监督学习,没有样本数据参考,完全需要算法自己完成分类。在这个案例中,主要设计监督学习的分类算法。

监督学习算法需要有样本数据为算法提供参考,建立样本数据是鸢尾属分类器的第一步工作。建立样本数据前,需要找出鸢尾属的特征进行归类,鸢尾属不同种类的花瓣及花萼的宽度和长度是有一定区别的,并且这些特征通过测量就可以获取,可以考虑采用花萼长度、花萼宽度、花瓣长度、花瓣宽度作为样本的特征数据。

样本数据样例(单位为厘米):

01.PNG

表格列出了样本数据构成,表格的列是样本的特征数据,表格的行是1个样本。

鸢尾属数据集由埃德加·安德森建立,数据集包含了setosa 、versicolor 、virginica种类各 50个样本。

鸢尾属分类器以鸢尾属数据集为样本数据,将数据集分为两部分:一部分用于归类训练,一部分用于归类测试。

训练数据集为:train_Iris.csv

测试数据集为:test_ Iris.csv

如何设计一个自动分类算法呢?设想一下,若待分类的数据特征与样本数据之间的距离很小,说明两者的特征值相似,可以考虑将待分类的数据归类为样本数据所属类别。在后面的内容中,也将待分类数据称为目标数据。

例如:

02.PNG

在表格样例数据中,序号1、2、3为已分类样本数据,序号4为目标数据,分别计算待分类数据与样本1、样本2、样本3的距离,取距离样本数据最近的类别。

表格样例数据每行为一个向量,向量的分量分别为花萼长度、花萼宽度、花瓣长度、花瓣宽度,只要计算两个向量间的距离就可以了,计算两个向量间的距离可以采用欧几里得距离计算方法。

欧几里得距离也称欧氏距离,是指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。例如:在二维空间中,两点间的欧氏距离为:

03.PNG

欧氏距离为向量的自然长度,也称为向量的模。在同维度空间中,两个向量差的模即为两个向量间的欧氏距离。例如:目标数据与样本1的欧氏距离为:

04.PNG

例1 计算目标数据与样本数据的欧几里得距离

案例代码见课程资源(unit2/case01.py)

import numpy as np
 
# 样本数据
sample_data = np.array([
    [5.1,3.5,1.4,0.2],
    [6.7,3.1,4.7,1.5],
    [5.8,2.7,5.1,1.9]
    ])
 
# 目标数据
dest_data = np.array([4.5,2.3,1.3,0.3])
 
# 计算目标数据与样本数据的距离
dist_list = []
for v in sample_data:
    dist = np.linalg.norm(v - dest_data)
    dist_list.append(dist)
print(dist_list)

输出结果如下:

样本序号(1)与目标数据的距离:1.349

样本序号(2)与目标数据的距离:4.299

样本序号(3)与目标数据的距离:4.342

从输出结果可以看出,目标数据与序号为1的样本数据距离最近,目标数据可以归类为Iris-setosa。

通过距离来预测目标数据的归类算法,很容易受到一些数据噪声或离群数据的影响。例如下图:

05.png

图中蓝色数据点和橙色数据点是两个分类的数据,黑色数据点是待分类的目标数据,从图中可以直观看出,黑色数据点和近邻橙色数据点的距离最近,若采用距离最近的分类算法,黑色数据点会归类为橙色圆点分类,这显然是有错误的,它应该归类于蓝色数据类别。这是因为分类算法受到了离群数据的影响,与黑色数据点近邻的橙色数据点就是离群数据。

可以考虑取黑色数据点近邻(距离黑色数据点最近)的K(1≤K≤N,N为训练数据集的长度)个数据点,确定K个数据点中同一类别出现的频率,把频率最高的类别作为黑色数据点的类别。

例如:取K=3,黑色数据点近邻的两个蓝色数据点和一个橙色数据点会被选取,按照出现频率最高类别作为目标数据类别的原则,黑色数据点归类为蓝色数据类。

K值的选取对归类算法影响较大。如果选择较小的k值,只有离目标数据较近的K个数据点对分类预测有影响,忽略了数据的真实分布,也容易放大数据噪声或离群数据对分类的影响。如果选择较大的k值,与目标数据较远的K个数据点也会对分类预测有影响,虽然减小了数据噪声或离群数据的影响,但也增大了预测分类发生错误的概率。

K值一般选取较小的数值,再通过交叉验证来调整K值。交叉验证即把训练数据集分为两组,一组用于训练,一组用于验证,可以多次选取不同的训练集和验证集,将K值调整到最优。

上述分类算法也称为K-近邻算法。

例2 使用K-近邻算法构建鸢尾属分类器

案例代码见课程资源(unit2/case02.py)

import numpy as np
from collections import Counter
 
# 定义K值
K = 5
 
# 定义存储项集的类
class Term:
    # 数据集样本的索引
    index = 0
    # 数据集样本所属类别
    category = ""
    # 数据集样本与目标数据的距离
    distance = 0
 
# 取与目标数据距离最近的K个样本数据
# data:样本数据  v:目标数据
def k_distance(data,v,category):
    dist_list = []
    for i,item in enumerate(data):
        dist = np.linalg.norm(v-item)
        trem = Term()
        trem.index = i
        trem.category = category[i]
        trem.distance = dist
        dist_list.append(trem)
    # 排序
    dist_list = sorted(dist_list,key = lambda x:x.distance)
    # 取K项
    if len(dist_list) > K:
        k_list = dist_list[0:K]
    else:
        k_list = dist_list
    return k_list
 
# 在K项集中,返回项最多的类别
def find_category(kdata):
    category = [kitem.category for kitem in kdata]
    most_category =  Counter(category).most_common(1)
    return most_category[0]
 
 
 
# 程序入口
if __name__ == '__main__':
 
   # 读取训练集特征数据
   feature_data = np.genfromtxt('train_Iris.csv',delimiter=',',dtype='float',usecols=[0,1,2,3])
   # 读取训练集类别名称
   category_data = np.genfromtxt('train_Iris.csv',delimiter=',',dtype='str',usecols=[4])
   # 读取目标数据集
   dest_data = np.genfromtxt('test_Iris.csv',delimiter=',',dtype='float',usecols=[0,1,2,3])
   # 计算目标数据集项与训练集特征数据的距离
   for dest_v in dest_data:
       kdata = k_distance(feature_data,dest_v,category_data)
       category,count = find_category(kdata)
       print(dest_v,end=":")
       print(category,count)
       print("\n")

执行构建的鸢尾属分类器,对test_ Iris.csv测试集的33项目标数据进行了自动归类测试,正确归类32项,错误归类一项,归类正确率为96.97%。

鸢尾属分类器采用的是K-近邻算法,从分类器代码可以看出,K-近邻算法并不是通过训练输出函数模型。而是从训练数据集中找到与目标数据最邻近的K个样本数据,再从这K个样本数据中选择所属类别最多的类,目标数据就归为该类。

在K-近邻算法中,选取的特征值差别不能太大,若差别太大需要对特征值做标准化处理。因为若样本数据的某列特征值较大,而其它列的特征值较小时,分类结果会被较大的特征值所主导,而弱化了其他特征值的影响。

特征值的标准化是将所有特征值全部映射到一个特定区间,一般将全部特征值映射到区间[0,1]。常用的标准化方法是离差标准化(min-max标准化),转换函数如下:

07.PNG

其中,max为样本数据的最大值,min为样本数据的最小值。标准化代码如下:

# 数据标准化
def normalizing(data):
   max, min = data.max(), data.min()
   # max - min作为基数对数据归一化处理
   result = (data - min)/(max - min)
   return result

K-近邻算法每预测一个目标数据的分类,都需要计算目标数据与全部训练数据样本的距离,对于大容量样本数据计算量非常大,特别是特征数据较多时,计算向量的距离会非常耗时,当样本特征值不平衡时,会降低预测的准确率。

读者留言
最新
推荐
郎宏林
授课老师
授课老师简介
项目经理,系统分析和架构师,从事多年中文信息处理技术。熟悉项目管理、擅长项目需求分析和设计、精通Java、C#、Python等编程语言。