分类规则挖掘（一）

一、分类问题概述

动物分类：设有动物学家陪小朋友林中散步，若有动物突然从小朋友身边跑过就会问“ 这是什么动物？”，动物学家说是“松鼠”呀！这就是所谓动物的分类问题。

数据分类 (Data Classification) ：对于一个未知类别标号的数据对象 $Z_u$ ，给出它的类别名称或标号。相当于动物学家看到一个动物会说出动物的名称，是因为他经历了长时间的学习，并记住了各种类动物的特性或分类规则。数据分类器是指若干分类规则的集合 (图9-1)。

在这里插入图片描述
分类分析 (Classification Analysis) 的三个步骤：挖掘分类规则 (建立分类器或分类模型)，分类规则评估和分类规则应用。

（一）分类规则挖掘

先将一个已知类别标号的数据样本集 (也称为示例数据库) 随机地划分为训练集 $S$ (通常占2/3) 和测试集 $T$ 两个部。通过分析 $S$ 中的所有样本点 (数据对象)，为每个类别做出准确的特征描述，或建立分类模型，或挖掘出分类规则。这一步也称为有监督的 (supervised) 学习，即在模型建立之前就被告知每个训练样本。

训练集 $S=\{X_1,X_2, \cdots, X_n\}$ 且每个样本点 $X_i$ 都对应一个已知的类别标号 $C_j$ （表9-1）。其中 $A_1,A_2,\cdots,A_d$ 称为样本集 $S$ 的 $d$ 个条件属性 (简称属性) ， $C$ 称为类别属性或决策属性， $C_j(i=1,2,\cdots,k)$ 又称为类别属性值或决策属性值或类别标识，并将 $C=\{C_1,C_2,\cdots,C_k\}\tag{9-1}$ 称为 $S$ 的类别属性集，也称为 $S$ 的分类集。

在这里插入图片描述

定义9-1 对于给定的训练样本集 $S$ 和分类属性 $C=\{C_1,C_2,\cdots,C_k\}$ ，如果能找到一个函数 $f$ 满足：
① $f : S \to C$ ，即 $f$ 是 $S$ 到 $C$ 的一个映射；
② 对于每个 $X_i\in S$ 存在唯一 $C_k$ 使 $f(X_i)=C_j$ ，并记 $C_j=\{X_i | f(X_i)=C_j, 1≤j≤k, X_i\in S\}$ 。
则称函数 $f$ 为分类器，或分类规则，或分类方法，其寻找过程称为分类规则挖掘等。

类别标号 $C_j$ 其实也代表属于该类的样本点集合，比如，我们说样本点 $X_1 , X_2, X_3$ 是 $C_1$ 类的，表示样本点 $X_1, X_2, X_3$ 属于 $C_1$ ，即 $C_1=\{X_1, X_2, X_3\}$ 。因此， $C_1$ 既是一个类别标号 (分类属性的取值)，又表示属于该类所有样本点的集合。

（二）分类规则评估

对测试集 $T$ 中的样本点，若有 $N$ 个样本点被分类模型正确地分类，则分类模型在测试集 $T$ 上的准确率定义为 “正确预测数/预测总数”，即 $准确率 = N /∣ T ∣$ 。

由于 $T$ 中的样本点已有分类标识，很容易统计分类器对 $T$ 中样本进行正确分类的准确率，加之 $T$ 中样本是随机选取的，且完全独立于训练集 $S$ ，其测试准确率高就说明分类模型是可用的。

如果直接使用训练集 $S$ 进行评估，则其评估结果完全可能是乐观的，即准确率很高，但因为分类模型是由 $S$ 学习而得到的，它会倾向于过分拟合训练集 $S$ ，而对 $S$ 以外的其它数据对象进行分类却可能很不准确。因此，交叉验证法来对模型进行评估是更合理的方法。

（三）分类规则应用

如果评估分类模型的准确率可以接受，接下来就是利用这个分类器对没有类别标号的数据集 $Z$ （表9-2）进行分类。

在这里插入图片描述
即从 $Z$ 中任意取出一个样本点 $Z_u$ ，将其输入分类器，所得的类别标号就是 $Z_u$ 所属的类别集合。

二、k-最近邻分类法

$k$ -最近邻 ( $k$ -Nearest Neighbour, $k$ NN) 分类法是一种基于距离的分类算法，它既不需要事先建立分类模型，也无需对分类模型进行评估，而仅利用有类别标号的样本集，直接对没有类别标号的数据对象 $Z_u$ 进行分类，即确定其类别标号。

假定样本集 $S$ 中每个数据点都有一个唯一的类别标号，每个类别标识 $C_j$ 中都有多个数据对象。对于一个没有标识的数据点 $Z_u$ ， $k$ -最近邻分类法遍历搜索样本集 $S$ ，找出距离 $Z_u$ 最近的 $k$ 个样本点，即 $k$ -最近邻集 $N$ ，并将其中多数样本的类别标号分配给 $Z_u$ 。

算法9-1 $k$ -最近邻分类算法
输入：已有类别标号的样本数据集 $S$ ，最近邻数目 $k$ ，一个待分类的数据点 $Z_u$
输出：输出类别标号 $C_u$
（1）初始化 $k$ -最近邻集： $N=\phi$ ；
（2）对每一个 $X_i\in S$ ，分两种情况判断是否将其并入 $N$
① 如果 $∣ N ∣ \leq k$ ，则 $N=N\cup\{X\}$
② 如果 $∣ N ∣ > k$ ，存在 $d(Z_u,X_j)=max\{d(Z_u,X_r)|X_r\in N\}$ 且 $d(Z_u,X_j)>d(Z_u,X_i)$
则 $N=N-\{X_j\}；N=N\cup\{X_i\}$ ;
（3）若 $X_u$ 是 $N$ 中数量最多的数据对象，则输出 $X_u$ 的类别标号 $C_u$ ，即 $Z_u$ 的类别标号为 $C_u$

例9-1 设某公司现有15名员工的基本信息，包括其个子为高个、中等、矮个的分类标识。

在这里插入图片描述
公司现刚招进一位名叫刘平的新员工 $Z_1$ ，令 $k = 5$ ，试采用 $k$ -最近邻分类算法判断员工刘萍的个子属于哪一类？

在这里插入图片描述
解：只有身高才是与个子高矮相关的属性，因此用 $X_i$ 表示第 $i$ 个员工的身高。

首先从 $X$ 中选择5个员工作为初始 $k$ -最近邻集 $N$ 。不失一般性，取 $N=\{X_1=1.60, X_2=2.00, X_3=1.90,X_4=1.88,X_5=1.70\}$ （1）对 $S$ 的 $X_6=1.85$ ，身高 $X_2=2.00$ 是 $N$ 中与身高 $Z_1=1.62$ 差距最大的员工，且有 $d(Z_1,X_2)>d(Z_1,X_6)$ ，因此，在 $N$ 中用 $X_6$ 替换 $X_2$ 得到 $N=\{X_1=1.60, X_6=1.85, X_3=1.90, X_4=1.88, X_5=1.70\}$ （2）同理，用 $S$ 中 $X_7=1.59$ 替换 $N$ 中身高距离 $Z_1=1.65$ 最大的员工 $X_3=1.90$ ，得到 $N=\{X_1=1.60, X_6=1.85, X_7=1.59, X_4=1.88, X_5=1.70\}$ （3）用 $X_8=1.70>$ 替换 $N$ 中距离 $Z_1$ 最大的员工 $X_6=1.85$ ，得到 $N=\{X_1=1.60, X_8=1.70, X_7=1.59, X_4=1.88, X_5=1.70\}$ ；

（4）因为 $S$ 中的 $X_9=2.20$ 和 $X_{10}=2.10$ ，故根据算法， $N$ 不需要改变。

（5）用 $X_{11}=1.8$ 替换 $N$ 中 $X_{11}=1.88$ 得 $N=\{X_1=1.60, X_8=1.70, X_7=1.59, X_{11}=1.80, X_5=1.70\}$ （6）因为 $S$ 中的 $X_{12}=1.95, X_{13}=1.90, X_{14}=1.80$ ，故 $N$ 不需要改变。

（7）用 $X_{15}=1.75$ 替换 $N$ 中 $X_{11}=1.8$ 得 $N=\{X_1=1.60, X_8=1.70, X_7=1.59, X_{15}=1.75, X_5=1.70\}$ （8）在第（7）步所得 $N$ 中，有5个身高最接近 $Z_1=1.62$ 的员工，且其 $X_1=1.60，X_8=1.70，X_7=1.59，X_5=1.70$ 这4个员工的类别都是 “矮个”，仅有 $X_{15}=1.75$ 的类别是 “中等”；因此，新员工 $Z_1=刘平$ 的个子为矮个。