简单解释:采用测量不同特征值之间距离的方法进行分类的算法。
主要优点是精度高,缺点是计算和空间负责度高,适用于数值型和标称型。
已下是通过Python实现的k-近邻算法,大致思路是计算样本数据data_set
中的点与待分类点的距离,按距离递增排序,然后取出前K个点,计算这些点所属标签的数量,计数最高的标签为分类结果。
1 | #! /data/server/python/bin/python |
k-d tree算法
k近邻法 给定一个训练数据集,对新输入的实例,在训练的数据集中找到与该实例最近邻的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。
kd树 是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
算法:(构造平衡kd树)
输入:k维空间数据集
输出:kd树。
生成:
从深度为0的结点开始。重复对深度为j的结点,选择x(l)
为切分的坐标轴,l=j(mode k) + 1
,以该结点的区域中所有实例的x(l)
坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x(l)
垂直的超平面实现。由该结点生成深度为j+1的左、右子结点:左子节点对应坐标x(l)
小于切分点的子区域,右子节点对应坐标x(l)
大于切分点的子区域。
实例:
对以下给定二维数据集构造一个平衡kd树