第1章 绪论
分类问题是机器学习和模式识别的核心研究内容， 分类算法利用有监督学习方法学习一个映射函数， 并利用该映射函数将待分类样本的特征映射到有限类别集合中. 通常分类算法使用的训练样本至少包含两个不同的类别， 通过求解分类算法对应的优化问题得到用于决策的函数或模型.
当类别集合中仅有两个类别时， 所对应的分类任务被称为两类分类， 如垃圾邮件分类， 需要将一个文本邮件归为两类: 垃圾邮件和非垃圾邮件. 多类分类则是指类别集合中具有两个以上的类别， 如人脸识别， 需要判断一张图片中的人脸是谁的脸.
然而在某些情况下， 由于样本获取的难度太大或者代价较高， 只能获得一类样本或获得的样本类别极端不平衡. 例如在网络入侵检测模型的构建过程中， 绝大多数能够收集到的数据是非入侵情况下的网络通信数据. 因为只能利用一类样本训练分类器， 故称该分类问题为单类分类， 如网络入侵检测， 能够根据用户的行为或资源使用状况的正常程度来判断是否入侵， 它以系统、网络、用户或进程的正常行为建立轮廓模型， 即正常行为模式. 将与之偏离较大的行为解释为入侵.
1.1 两类分类
在机器学习和模式识别研究领域中， 许多方法在模型构造过程中都假设训练样本仅有两个类别， 如对数几率回归[1.3]、支持向量机 [4]、AdaBoost [5] 等.
1.1.1 例子 (蠓虫分类)
Af 是宝贵的传粉益虫， 而 Apf 则是某种疾病的载体毒蠓， 生物学家 Grogan和 Wirth [6] 曾根据两种蠓虫 Af 和 Apf 的触角长度和翼长对它们的鉴别问题进行过研究. 现测得 9 只 Af 和 6 只 Apf 的触角长度和翼长， 如表 1.1 所示.
表 1.1 蠓虫 Af 和 Apf 数据集
这些数据可以综合为
(1.1)
其中 xi = (xi1， xi2)T 表示第 i 只蠓虫且 xi1 和 xi2 分别表示该蠓虫的触角长度和翼长， yi 2 f1，-1g 表示该蠓虫的类别， 当 yi = 1 时， 蠓虫 xi 属于正类， 即为 Af;当 yi = -1 时， 蠓虫 xi 属于负类， 即为 Apf. 现在问题是， 对新来的一只蠓虫， 已知它的触角长度 x1 和翼长 x2， 试推断它是 Af 还是 Apf， 即求对应的类别标号 y是 1 还是 -1.
这个问题是一个二维空间上的两类分类问题， 可以在平面直角坐标系中描述如下: 根据蠓虫的两个特征和类别标号， 把每个蠓虫用一个样本点来表示， 参看图 1.1. 样本点的两个坐标分别由两个特征确定， 点的形状由类别标号确定: Af用“+”形点，Apf 用“0” 形点.
图 1.1 蠓虫 Af 和 Apf 数据集
新来一只蠓虫， 相当于给了平面上的一个点 x， 现在的问题是要推断它属于正类 (y = 1) 还是负类 (y = -1). 换言之， 需要把平面划分成两个部分， 使得当该点落入其中一部分时， 推断该蠓虫属于正类; 而落入另一部分时， 推断它属于负类，关键是如何划分平面.
观察图 1.1 中标出的两类点， 可以考虑选择一条合适的直线 wTx + b = 0 把平面划分为两部分， 其中 wTx 是 w = (w1，w2)T 和 x = (x1， x2)T 的内积. 把直线的两侧分别归为正类和负类. 或者说可以按下式推断点 x 所对应的 y:
(1.2)
其中 sign( ) 为符号函数， 即
(1.3)
1.1.2 两类分类问题
前面讲的例子是一个具体的二维空间上的两类分类问题， 它包含两个特征 (即x∈R2) 和 15 个样本点. 一般地， 考虑 d 维空间上的两类分类问题， 它包含 d 个特征 (即 x∈R d) 和 N 个样本点. 记这 N 个样本点的集合为
(1.4)
其中是输入向量， 或称示例， 其分量称为特征， 或属性; yi ∈ Y ={1，-1g} 是输出， i = 1， ，N. 这 N 个样本点构成的集合称为训练集. 这时的问题是， 对任意给定的一个新的示例 x， 根据训练集， 推断它所对应的输出 y 是 1 还是 -1.
因此， 两类分类问题可以描述为:
根据给定的训练集， 其中， 寻找上的一个实值函数 g(x)， 以便用决策函数
(1.5)
推断任一示例 x 相对应的 y 值.
据此， 求解两类分类问题， 实质上是寻找一个把 <d 上的样本点分为两部分的规则. 解决该分类问题的方法可称为分类器. 当 g(x) 为线性函数 g(x) = wTx + b，由决策函数 (1.5) 确定分类准则时， 称为线性分类器; 当 g(x) 为非线性函数， 由决策函数 (1.5) 确定分类准则时， 称为非线性分类器. 不难想象， 对于图 1.1 所示的问题， 很容易用一条直线把训练集正确地分开 (即两类样本点分别在直线的两侧，没有错分点)， 其分类效果如图 1.2 所示.
图 1.2 蠓虫 Af 和 Apf 数据集的分类效果
1.2 多类分类
多类分类问题在现实生活中常常存在， 与两类分类相比， 多类分类的分类模型更为复杂， 而且获得的分类效果更差. 在处理多类分类问题时， 往往采用两种方式: 一种是直接使用多类分类算法， 如决策树[7，8]、神经网络[9]、K 近邻分类器[10，11] 等; 另一种则是将多类分类问题分解为多个两类分类问题， 并分别使用两类分类算法， 如支持向量机.
1.2.1 例子 (鸢尾属植物分类)
鸢尾属 (Iris) 植物数据集 [12] 是用于测试机器学习算法的常用数据集. 该数据集包括四个特征: 萼片长度、萼片宽度、花瓣长度和花瓣宽度， 用于描述鸢尾属植物的三个不同物种: Setosa， Versicolor 和 Virginica. 该数据集中每个物种有 50个样本. 表 1.2 展示了该数据集中的部分样本.
表 1.2 Iris 数据集中的部分样本
该数据集可以综合为
(1.6)
其中 xi = (xi1， xi2， xi3， xi4)T 表示第 i 个样本且 xi1~ xi4 分别表示该样本的萼片长度、萼片宽度、花瓣长度和花瓣宽度， yi ∈ {1， 2， 3} 表示该样本的类别， 当 yi = 1时， xi 属于物种 Setosa; 当 yi = 2 时， xi 属于物种 Versicolor; 当 yi = 3 时， xi 属于物种 Virginica. 现在的问题是， 对新来的一个样本， 已知它的萼片长度 x1、萼片宽度 x2、花瓣长度 x3 和花瓣宽度 x4， 试推断它属于 Setosa， Versicolor 还是Virginica， 即求对应的类别标号 y 是 1， 2 还是 3.
这个问题是一个四维空间上的三类分类问题， 为了便于可视化， 仅考虑使用花瓣长度和花瓣宽度两个特征， 根据样本的特征和类别标号， 把每个样本用一个样本点来表示， 参看图 1.3. 样本点的两个坐标分别由两个特征确定， 点的形状由类别标号确定: Setosa 用 “+” 形点， Versicolor 用“*”形点， Virginica 用 “0”形点.
图 1.3 Iris 数据集
新来一个样本， 相当于给了平面上的一个点 x， 现在的问题是要推断它属于Setosa(y = 1)， Versicolor(y = 2) 还是 Virginica (y = 3). 可以通过两种途径确定 x 的类别标号. 一种是直接使用多类分类算法; 另一种是将此三类分类问题分解为三个两类分类问题， 然后对三个两类分类问题分别使用两类分类算法进行处理. 此处使用第一种途径中的多层感知器神经网络方法， 需将训练样本的类别标号由标量变为三维向量， 如 y = 1 可以转化为 (1，-1，-1)T， y = 2 可以转化为( - 1， 1，-1)T， 而 y = 3 可以转化为 ( - 1，-1， 1)T. 训练过程完成之后， 将 x 代入，假设该多层感知器第 l 个输出节点上的输出表示为 f(βl -θl)， 其中 f( ) 为输出节点上的激活函数， βl 表示第 l 个输出节点的输入， θl 表示该输出节点上的偏差项.最终， x 的类别标号可以由下式求取:
(1.7)
1.2.2 多类分类问题
考虑 d 维空间上的多类分类问题， 它包含 d 个特征 (即 x∈Rd) 和 N 个样本点. 记这 N 个样本点的集合为
(1.8)
其中 xi ∈ X Rd 是输入向量， yi 2 Y = f1， 2， ，Kg 是输出， i = 1， ，N. 该N 个样本点构成训练集. 此时的问题为， 对任意给定的一个新的示例 x， 根据训练集， 推断出它所对应的输出 y 是 1， 2， ， K 中哪一个.
因此， 多类分类问题可以描述为:
根据给定的训练集， 其中， 寻求决策函数 f(x) : X→Y. 实质上， 求解多类分类问题， 就是寻找一个把 <d 上的点分成 K 个互不相交子集的规则.
1.2.2.1 直接法
对于多类分类任务， 有些两类分类方法可直接推广到多类分类， 如朴素贝叶斯分类器 [13，14]、对数几率回归、神经网络、K 近邻分类器等.
下面以神经网络中的多层感知器为例. 如 1.2.1 节所述， 训练集中的类别标号需要转化为向量形式， 如 yi = k 向量化为 (-1， ，-1， 1，-1， ，-1)T， 其中 1为向量的第 k 个元素， 而其余的元素均为 -1.
训练样本的输入向量为 d 维， 则多层感知器的输入层含有 d 个输入节点. 假设多层感知器只含有一个隐含层， 且该隐含层由 NH 个隐含节点组成. 训练样本的类别标记已向量化为 K 维列向量， 则输出层含有 K 个输出节点. 若隐含层的激活函数为 sigmoid 函数， 则第 j 个隐含节点在第 i 个训练样本的输入向量上的输出为
(1.9)
其中 wji 是连接第 j 个隐含节点和第 i 个输入节点的连接权重， wj0 是第 j 个隐含节点上的偏差项. 若输出节点上的激活函数采用线性函数， 则第 l 个输出节点上的网络输出为
(1.10)
其中 vlj 是连接第 l 个输出节点和第 j 个隐含节点的连接权重， vl0 是第 l 个输出节点上的偏差项， 与公式 (1.7) 中的 θl 含义相同.
多层感知器的网络连接权重和偏差项学习完成之后， 对于待测示例 x， 将其输入多层感知器， 由式 (1.10) 计算出 K 个输出值 .最终， 待测示例 x的类别标号由下式给出
(1.11)
对于图 1.3 所示的问题， 可利用多层感知器作为多类分类器， 其分类效果如图1.4 所示.
展开
