7.4 惰性学习法在线视频

前面介绍的决策树归纳

朴素贝叶斯分类都属于急切学习法

即当给定训练元组集时

急切学习法在接收待分类的新元组之前

就构造泛化模型（即分类模型）

可以认为学习后的模型已经可以使用

对未知类别元组进行分类

惰性学习法并不急于

在收到测试对象之前构造分类模型

当接收一个训练集时

惰性学习法只是简单地存储

或稍加处理每个训练对象

直到测试对象出现

才构造分类模型

这种延迟的学习方法有一个关键的优点

即它们不在整个对象空间上

一次性地估计目标函数

而是针对每个待分类对象作出不同的估计

显然

惰性学习法的大部分工作存在于

分类阶段而非接收训练集的阶段

因此分类时其计算开销比较大

惰性学习方法主要包括

k近邻分类法

局部加权回归法和基于案例的推理

其中

前两者均假定对象可以被表示为

欧式空间中的点

后者则采用更复杂的符号表示对象

本节主要介绍k近邻分类法

K近邻算法的思想是

从训练集中找出

k个最接近测试对象的训练对象

再从这k个对象中确定主导类别

将此类别值赋给测试对象

假设训练对象有n个属性

每个对象由n维空间的一个点表示

则整个训练集处于n维模式空间中

每当给定一个测试对象c

K近邻算法计算c到每个训练对象的距离

并找到最接近c的k个训练对象

这k个训练对象就是c的k个“最近邻”

然后

将测试对象c指派到

“最近邻”中对象数量最多的类

当然不限于这一种策略

比如可以从“最近邻”中

随机选择一个类或选择最大类

当k=1时

测试对象被指派到与它

最近的训练对象所属的类

值得注意的是

该算法不需要花费任何时间做模型构造

因此与决策树等分类法相比

后期分类时消耗时间会稍长

K近邻算法进行分类时

需要考虑以下4个关键要素

①被标记的训练对象的集合

即训练集

用来决定一个测试对象的类别

②距离（或相似度）指标

用来计算对象间的邻近程度

一般情况下

采用欧几里得距离或曼哈顿距离

对于给定的具有n个属性的对象x和y

欧几里得距离与曼哈顿距离

分别由以下公式计算

其中xˇk-yˇk

是两个对象属性k对应值的差

③最近邻的个数k

k的值可以通过实验来确定

对于小数据集

取k=1常常会得到比其他值更好的效果

而在样本充足的情况下

往往选择较大的k值

④从k个“最近邻”中

选择目标类别的方法

例 K近邻算法实例

iris.arff数据集

包含了150条关于花的数据

这些数据被等分为三类Iris物种

Setosa

Versicolor

Virginica

每朵花的数据描述四项特征

花萼长度 花萼宽度

花瓣长度和花瓣宽度

以下两表分别是

iris.arff训练数据

与测试数据的示例

解

目标是确定表中测试数据的物种

选取欧几里得距离来计算

该测试对象与每个训练对象

之间的距离（保留两位小数）

计算如下

由于数据量很小

可以取k=1

可以看到该测试对象

与第7或第8个已标记对象最接近

因此属于Virginica物种

事实上

即便把k取值扩大到5

根据选择对象占多数的类别

分类结果依然正确

而k=6时

“最近邻”中

Versicolor

和Virginica的个数相等

现有的目标类判定方法失效

所以k值的选取非常重要

K近邻分类算法

输入

数据集D是具有n个训练元组

和对应类标号的集合

近邻数目k

待分类数据X

输出

数据X所属的类别

方法

从数据集D中

取A[1]～A[k]作为X的初始近邻

计算与待分类数据X间的欧式距离

d(X, A[i])

其中 i=1,2,…,k

按d(X,A[i])升序排序

得到最远样本与X间的距离

Distmax{d(X, A[j])的最大值

其中j =1,2,…,k}

for (i=k+1：i<=n; i++)

计算a[i]与X间距离

d(X,A[i])

如果if(d(X,A[i])

则用A[i]代替最远样本

按照d(X, A[i])

升序排序

得到最远样本与X间的距离

Distmax{d(X, A[j])

j =1,2,…,k}

循环结束

计算前k个样本

A[i]

其中(i=1,2,……,k)

所属类别的概率

具有最大概率的类别即为数据X的类

K近邻算法的性能

会受到一些关键因素的影响

首先是k值的选择

如果k值选择过小

结果会对噪声点的影响特别敏感

反之

k值选择过大

那么近邻中就可能包含太多种类别的点

可以通过实验确定最佳k值

从k=1开始

利用测试集估计分类器的错误率

k值每增加1

允许增加一个近邻并重复估计错误率

由此可以选取产生最小错误率的k值

一般情况下

样本数越充足

即训练对象越多

k值越大

随着训练对象数量趋向无穷并且k=1

K近邻分类器的错误率

最多不会超过贝叶斯错误率的2倍

（后者是理论最小错误率）

如果k同时也趋向无穷

K近邻分类器的错误率

会渐进收敛到贝叶斯错误率

因此

在样本非常充足的情况下

选择较大的k值

能提高K近邻分类器的抗噪能力

其次

目标类别的选择也非常重要

最简单的做法是如之前所述的投票方式

但是

如果不同的近邻对象

与测试对象之间距离差异很大

那么实际上距离更近的对象的类别

在目标类别选择上的作用更大

所以

一个稍复杂的方法是

对每个投票依据距离进行加权

加权的方法种类很多

比如

经常用距离的平方的倒数作为权重因子

实际上

投票加权法使得k值的选择敏感度

相对下降

最后

距离指标的选择也是影响

K近邻算法性能的一个重要因素

原则上

各种测量方法都可以计算两点之间的距离

但从最近邻算法的目的出发

最佳测距方法应该满足这种性质

对象之间距离越小

它们同属于一个类别的可能性越大

比如在文本分类的应用环境下

余弦距离就比欧几里德距离

更适合作为K近邻算法的测距方法

另外

一些距离测量方法会受到数据维数的影响

比如

欧几里得距离在属性数量增加时

判别能力会减弱

因此在测距之前

有时需要对属性的值做规范化处理

以防止距离测量结果

被单个有较大初始值域的属性所主导

例如

在一个数据集中

人的身高数据区间是1.5~1.8米

体重区间是45~90公斤

收入区间1~100万元

如果没有规范属性值

那么收入会主导距离计算

并影响最终的分类结果

可以使用前面讲过的规范化方法

进行规范化