第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 所示.
展开