机器学习基础教程课件：分类与聚类学习算法

分类与聚类学习算法绪论5.1分类学习算法5.1.1线性分类算法5.1.2非线性分类算法5.1.3核方法与支持向量机5.2聚类学习方法5.2.1K均值聚类算法

5.2.2其他聚类算法

分类（classification）和聚类（clustering）是机器学习的基本问题。

分类是一种监督学习方法，必须事先明确地知道各类别的信息，且所有待分类样本都有一个类别与之对应。很多时候无法满足上述条件，如处理海量数据时候，这时候可以考虑聚类分析。

聚类是将数据集划分为多个簇的过程，每个簇由若干样本构成，并满足某种度量为标准的相似性。这种相似性在同一聚类之间最小，而在不同聚类之间最大。5.1分类学习算法

分类学习算法在实际中有大量的应用，也是众多复杂算法的基础。分类学习算法有线性与非线性之分。线性分类就是用一个“超平面”将正、负样本隔离开，如用一条直线对二维平面上的正、负样本进行分类，用一个平面对三维空间内的正、负样本进行分类，用一个超平面对N维空间内的正、负样本进行分类。相反，非线性分类则是用一个“超曲面”或多个超平（曲）面的组合将正、负样本隔离开，如用一条曲线或折线对二维平面上的正、负样本进行分类，用一个曲面或者折面对三维空间内的正、负样本进行分类，用一个超曲面对N维空间内的正、负样本进行分类。5.1.1线性分类算法

一个分类问题是否属于线性可分，取决于是否有可能找到一个点、直线、平面或超平面来分离开两个相邻的类别。如果每个类别的分布范围本身是全连通的单一凸集，且互不重叠，则这两个类别一定是线性可分的，如图5.1所示。线性分类算法主要有线性回归、逻辑回归分类、单层感知器等。图5.1线性可分情况1.线性拟合（回归）分类方法线性拟合分类方法是求解直线（或超平面）问题求解的常见算法。这种方法可以用来进行数据分类：如图5.1所示，可以拟合一条直线（或超平面）作为两种类别的“分界线（面）”，通过对数据与分类面之间的关系可以对两类数据进行分类和区别。线性拟合的目标是找到一个函数，能将输入属性x映射到输出（目标）属性y，在机器学习领域可将该映射模型记为上述模型还需要一个参数集合（常以符号θ表示），机器学习的任务就是从给定的数据集（训练集）中“学习”到拟合参数集θ。因此，式（5.1）常写作如下形式

假设二元分类问题的正、负样本分别用1和0表示。这样，用线性拟合方法求解分类问题时，可设定一个阈值t（如t=0.5），使时预测，使时预测0。假设，产品的重量决定产品是否合格，将该方法用于某产品质量检测时方案如图5.2所示，其中“○”表示合格、“◊”表示不合格。用线性拟合得到的正好是一条直线，正好能够将产品质量合格和不合格分开。图5.2线性回归算法求解分类问题

线性拟合算法试图用一条直线去拟合只有两种取值的离散样本，通常并不适合分类问题：①线性回归算法用于分类问题的预测值是连续的数值型，可能会超出[0,1]范围，不利于类别解释；②当类别不平衡（正、负样本数量上差别非常大）或者少数样本点较为远离时，常造成模型偏向某个类别以至形成错误分类。如图5.3所示，有的样本远离，造成错误分类现象。图5.3线性回归算法错误分类例子

假设由两个类别：和，它们属于同一个样本空间Ω，在类别中的数据概率密度函数为，在类别中的数据概率密度函数为。如果将中的数据错分到中，则其条件概率为：而将中的数据错分到中，则其条件概率为：

其中，。若令为类别的先验概率，为类别的先验概率，则有。则分类情况应为先验概率与条件概率的乘积，可以用表5.1表示。关于错误分类的情况可以形象地用图5.4来说明。

数据实际属于类别π1数据实际属于类别π2分类操作结果属于类别π1分类操作结果属于类别π2表5.1分类情况表图5.4错误分类概率情况图

分类情况的好坏可以使用错误分类代价（简称错分代价）来进行衡量。由于正确分类没有出现错误，因此正确分类的错分代价为0。而将本来属于类别的数据错分为类别的错分代价为；同样的，将本来属于类别的数据错分为类别的错分代价为。在两分类的情况下，综合所有的因素，可以使用期望错分代价（ECM）来进行评价：优良的分类结果应该式（5.5）的错分代价最小。对于图5.4所示的两个分类区域，应该有：对于R2有：对于有：对于有：

对于两个同属于正态分布的数据集，其联合概率密度函数为：

（5.8）

其中，为两个正态总体的期望，

为其方差，而且这两个方差预设为相等，则分类后的最小ECM为：

（5.9）

（5.10）上两式中，指数函数的自变量有：

（5.11）

于是式（5.9）和式（5.10）取对数，变成：

（5.12）

（5.13）

在实际处理过程中，可以将均值代替期望

，样本协方差阵代阵代替

。分类函数的形式由式（5.2）给出，对于两重分类的分类函数应该有：

（5.14）

式中，为两类数据的均值（期望），S为两类数据相同的协方差阵。对式（5.14）有：

(5.15)

可得线性分类函数为：

(5.16)

对于两类方差不同的总体，其分类域变为：(5.17)

(5.18)

式中，(5.19)

可见，当两个总体的方差相同时,将其代入式（5.19）。式（5.17）、（5.18）就退化为式（5.12）、（5.13）。

对于多个正态总体的数据集进行分类，可以将两类数据的分类方法进行推广。对于期望错分代价函数来讲，如果有n类数据，且将第一类数据错分为各个n-1类的数据，则借鉴两个总体期望错分代价函数的情况，有：

以此类推，可得到总的期望错分代价函数为：式中，为各类数据的先验概率。

对于多重分类的线性分类函数，有：

（5.21）式中，为组间交叉乘积和，为组内样本矩阵。线性组合

为样本数据第一判别量，依次可以得到第k判别量。2.逻辑斯蒂（Logistic）回归分类（1）决策边界与决策区域

逻辑斯蒂（Logistic）回归分类是应用最为广泛的分类学习算法。其“回归”并不是真正意义上的回归或拟合，其目标属性不是连续的数值型，而是离散的标称型。逻辑斯蒂（Logistic）回归算法使用Sigmoid函数（简称S函数）作为分类问题的假设函数，满足分类问题预测值在[0,1]区间这一性质。Sigmoid函数表达式如下

（5.22）Sigmoid函数很好地近似了阶跃函数，且连续光滑，严格单调递增，并以（0,0.5）中心点对称，即当输入大于0时输出趋于1，当输入小于0时输出趋于0，当输入等于0时输出正好为0.5，如图5.4所示。此外，Sigmoid函数容易求导，其导数为

（5.23）图5.5Sigmoid函数曲线

这样，可通过Sigmoid函数对进行变换，使其取值压缩在“[0,1]”范围，即显然，当时，预测样本x为正例；当，预测样本x为负例；当时，，称为样本分类的决策边界。如图5.6展示了二维数据的决策边界图5.6决策边界为直线

这样，特征空间被决策边界划分成不同的区域，每个区域对应一个类别，称为决策区域。当我们判定待识别的样本位于某个决策区域时，就判决它可以划归到对应的类别中。需要注意的是，决策区域包含类别中样本的分布区域，但不等于类别的真实分布范围。

这样，准则函数可以表达成N个样本的负对数似然代价均值式中，和分别表示第k个样本的输入和输出；N为样本总个数。使用梯度下降法可以求解出使取极值最小的最优参数。梯度下降基本思想是，随机选取一组参数初值，计算代价，然后寻找能让代价在数值上下降最多的另一组参数，反复迭代直到达到一个局部最优。梯度下降参数更新公式如下求导得

代入得，上式就是逻辑斯蒂回归算法的核心递推公式。通过不断更新参数集，直到达到收敛，此时得到的参数即为。图5.6所得决策边界即采用逻辑回归算法所得，其准则函数随迭代次数变化如图5.7所示，可见最终准则函数趋于0。3.单层感知器

感知器模型如第四章图4.2所示，是一种神经元模型，没有反馈和内部状态，是对多个输入量加权求和后确定输出的值。显然，感知器是一个多输入单输出的非线性系统。

显然，感知器没有反馈和内部状态，是多输入单输出的非线性系统。其输入与输出满足如下关系：(5.30)

感知器算法的具体步骤可表达如下：1）设定初始参数集，s=0;2)对训练样本集的所有规范化增广特征向量进行分类，将分类错误的样本（即不满足的样本）放入集合中；3）利用公式（5.35）更新参数集；4）返回步骤2），直至所有的样本都被正确分类为止。此时参数集即为求得的最优值。显然，感知器算法中递推步长决定了每次对参数集修正的幅度，其大小直接影响迭代速度和精度。一般，递推步长选择有如下方式：1）固定值。即选择固定的非负数；

2）绝对修正。在单样本修正算法中，为保证分类错误的样本在对参数集合进行一次修正后能正确分类，需要满足，代入递推修正公式（5.35）得解得，3）部分修正。若满足式（5.38）则称部分修正。4）变步长法。可以取按照某种规律逐步减小的，使得算法开始时收敛较快，接近最优解时收敛速度变慢，以提高求解的精度。比较常用的变步长法是取5）最优步长法。在每一次迭代时，通过求准则函数对于不同的的最小值，来确定最优的。该方法会带来更大的计算量。5.1.2非线性分类算法

线性分类器可以实现线性可分的类别之间的分类决策，其形式简单，分类决策快速。但在许多实际分类问题中，两个类别的样本之间并没有明确的分类决策边界，线性分类器无法完成分类任务。线性不可分情况典型如下：①分布范围是凹的类别的凸包与另一类别分布范围重叠（如图5.8a所示）；②类别的分布范围由两个以上不连通区域构成，如异或（XOR）问题（如图5.8b所示）。（a）凹集凸包与凸集重叠（b）异或问题图5.8线性不可分情况1.多项式逻辑回归算法

大多数情况，无法用一条直线将不同的类别分开（如图5.9所示）。图5.9决策边界复杂情况图5.10多项式逻辑回归的决策边界2.贝叶斯分类器

贝叶斯分类器是一种基于统计的分类器，原理如下：确定某样本的先验概率，利用贝叶斯公式计算出其后验概率（该样本属于某一类的概率），选择具有最大后验概率的类别作为样本的所属类别。（1）贝叶斯理论改写成（2）朴素贝叶斯分类算法例5.1人的心情受活动、天气、地点、是否独处等环境条件影响。近段时间来，小明情绪波动较大，其中心情愉悦情况10次，心情欠佳情况5次。为此，他将当时的活动、天气、地点、是否独处等情况做了详细的记录，并统计如下表

请预测某天天气晴、小明一个人在校外看电影时他的心情。环境心情环境心情愉悦欠佳愉悦欠佳活动看电影31天气晴天52逛街42雨天20考试32阴天33地点学校53是否独处独处32校外52有伴73解：将“天气晴、小明一个人在校外看电影”记为事件X。首先，分别计算心情愉悦和心情欠佳的先验概率：，然后，分别计算心情愉悦和心情欠佳的类条件概率：

第三，分别计算心情愉悦和心情欠佳的后验概率最后，事件X导致小明心情愉悦和心情欠佳概率分别为，（3）特殊问题

下面，我们讨论朴素贝叶斯分类算法遇到的两类特殊问题。

①如果训练样本集中有的属性值一次都没有出现（如表5.2中，在心情欠佳时，天气为雨天的样本一次也没有出现），即其条件属性概率为0。这时，计算该属性的类条件概率时，各项属性都需乘以该0值，导致不管其他数值的概率有多大，最终乘积都为0。显然这是不合理的，不能因为没有观察到某事件，就认为该事件发生的概率为0。当这种属性值一次都没有出现的情况出现较多时，在归一化后求取最终的条件概率时，甚至会发生0除以0的现象。

对于这种情况，通常采用拉普拉斯平滑进行处理。以例5.1中心情欠佳时的天气情况概率为例。根据表5.2，当心情欠佳时天气晴天、雨天和阴天的概率分别为2/5、0/5、3/5。

此时，选择一个很小的常数，按如下形式进行平滑理：、、。其中，、、需满足。②有的训练样本集不仅有离散的标称属性，还有连续的数值属性，如例5.1，若小明在记录的时候将当时的温度、湿度用数值记录下来，这就变成了混合问题。对混合问题，朴素贝叶斯分类算法有两种处理方法：一种方法是将数值属性离散化，转换为常规的离散标称属性；另一种方法是假设数值属性符号正态分布，根据训练样本计算出正太分布的参数，然后再计算测试样本某个数值属性出现的概率，并以该概率作为条件概率代入式（5.31）和（5.32）中求解。下面通过例5.2演示如何解决上述两类特殊问题。例5.2

小明喜欢户外“驴行”，表5.3是近来小明“驴行”的情况统计。其中，“天气”和“空气质量”等离散型属性为统计次数；“温度”、“湿度”等连续数值型属性为数值，单位分别为“℃”和“%”。

请预测某天下雨、气温20℃、湿度90%、空气重度污染时小明是否外出“驴行”。天气“驴行”温度“驴行”湿度“驴行”空气质量“驴行”是否是否是否是否晴天83

2535

8590良好92雨天01

1822

7560轻度污染12阴天21

2319

6065重度污染01

1930

7095

3110

5585

22

90

16

80

30

75

26

80

17

90

表5.3小明“驴行”与否与条件情况统计解：将“天气晴、小明一个人在校外看电影”记为事件X。首先，分别计算“驴行”=“是”和“驴行”=“否”的先验概率。根据上表统计，“驴行”=“是”的次数为10次，“驴行”=“否”的次数为5次，故，然后，分别计算“驴行”=“是”和“驴行”=“否”条件下各项属性的类条件概率。①在计算和时，会遇到第1类问题，即为该属性值的样本一次也没出现。此时，进行拉普拉斯平滑处理，则：

这样，对于“驴行”=“是”和“驴行”=“否”条件下的“天气”和“空气质量”各属性的类条件概率汇总如下表：②对于含数值属性的“温度”和“湿度”，假设均符合正态分布。这样，对于“温度”和“湿度”属性，为“是”类别的样本均为10个，为“否”类别的样本均为5个。按下式分别计算各组数据的均值和标准差。汇总如下表：这样，对于属性值为“x”的样本，均值和标准差均已知，其正态分布的概率密度函数可按下式计算：对于“气温20℃”、“湿度90%”按上式计算得：

第三，以概率密度代替概率值，分别计算在事件X条件下“驴行”=“是”和“驴行”=“否”的后验概率：

最后，事件X导致小明外出“驴行”和不外出“驴行”概率分别为贝叶斯分类器给出的下雨、气温20℃、湿度90%、空气重度污染时，小明不外出“驴行”概率达99.9936%。故，小明不会外出“驴行”。5.1.3核方法与支持向量机

核方法的基本思想是，将原始数据通过某种非线性映射到高维空间，再利用线性方法分析和处理数据。支持向量机（SupportVectorMachine，SVM）是一种由监督学习，其基本思想是将样本向量映射到高维空间中，寻求一个最优区分两类数据的超平面，使各分类到超平面的距离最大，亦称大间距分隔机。显然，SVM使用了核方法，使用不同的核函数形成了不同的SVM算法。1.核方法核方法认为，将低维空间中不可线性分割的数据集，映射到高维空间中时，很可能变成线性可分的。例如，对于一维特征空间中线性不可分问题（如图5.11a），可设定判别函数J(x)=(x-a)(x-b)(5.52)（a）一维线性不可分问题（b）二维线性可分问题图5.11将一维线性不可分问题转化为二维线性可分问题

则可通过的正负来判别x的类别：当时，x属于类别1，当，x属于类别2。

进一步，令，，则原始一维特征空间就映射到二维特征空间即，上述一维线性问题涉及的数据在二维特征空间映射为一条抛物线。其判别函数（式（5.52））转换为其决策边界在二维特征空间为一条直线。这样，决策边界将抛物线分割为两部分，实现了线性分割。其中，在决策边界下部（）为类别1，在决策边界上部（）为类别2。

设原始数据集（输入变量x）在低维空间X中，通过变换将映射到目标高维空间H中。若存在，使得则称为核函数。对于目标高维空间H，一般维数比较高，难以求其内积。通过核技巧可巧妙地解决该问题，即不显式定义和计算映射函数，而是通过低维空间点的核函数计算高维空间向量的内积。这样，就只涉及映射后特征向量的内积计算，而不直接计算的值，可以有效避免维度祸根（curseofdimension）问题，也减少了计算量。下面，以二阶多项式变换进一步说明核方法。设对n维数据的二阶多项式映射函数为

则，高维特征向量的内积（核函数）可表示为

即，将映射函数和内积运算巧妙地转换成原始特征的内积运算，可有效地加快运算速度。

一般，核函数K(x,y)都是由经验选定，然后通过实验验证该选择的有效性。常用的核函数有如下几类：（1）线性核函数，式中，c为可选常数。（2）多项式核函数，式中，c为可选常数；d为最高次项次数。（3）高斯核函数，式中，为高斯核带宽。越大，高斯核函数越平滑，泛化能力越差；越小，高斯核函数变化越剧烈，泛化能力越强。（4）拉普拉斯核函数，式中，为参数。（5）Sigmoid核函数，式中，，tanh为双曲正切函数；c为可选常数，一般为数据维数的倒数。此外，核函数的组合亦是核函数。设和是核函数，则（1）其线性组合是核函数，式中，、为任意正数。（2）其直积是核函数（3）组合亦是核函数式中，为任意函数。2.SVM问题数学描述对线性可分的二元分类问题，其分类决策边界是高维特征空间中的超平面，其解有无穷多个（如图5.12所示）。显然，可以在一定范围内平移分类决策边界（超平面），只要该决策边界不达到或跨过各类别中距其最近的样本，均可正确地实现线性分类。通常，将上述平移裕量d称为分类间隔。图5.12超平面、分类间隔与支持向量

设最优决策边界方程为注意式（5.64）与式（5.2）以及逻辑回归中的的表达是一致的，区别在于将原来的改写为c，并不再使用恒为1的。因此，采用SVM进行二元分类时，可以通过符号函数将映射到不同的类别（设类别标签y分别为“-1”和“1”）上，则这样，如果能确定和c，对于任意样本，可以根据的正负号很快地确定其类别即。

由于只有1和-1两种取值，上式实质为因此，要使分类间隔最大，即要使样本尽量远离决策边界，使足够大。而对于样本数为N的整个训练集来说，其离决策边界的最大距离由离该边界最近的样本决定。因此，要使训练集的分类间隔最大，应使最近样本的分类间隔尽可能的大，即应尽可能的大。由几何知识可知，样本距决策边界的距离为式中，表示参数向量的2-范式，即。

设训练集的分类间隔为d。由于训练集分类间隔由最近样本决定，且决策边界居中平分分类间隔。因此，有SVM的目标是，寻找一个离决策边界（超平面）最近的数据点的最大间隔，即要求d尽可能的大。因此，SVM分类问题的数学描述为将上两式转化为

为使式（5.71）的解有唯一确定值，常令。这样，训练集的分类间隔为d重新定义为SVM分类问题的数学描述变为上式就是SVM的基本形式。3.线性支持向量机SVM的基本形式是一个标准的二次规划问题，可直接利用现成的优化计算包求解，但求解效率慢。一般，通过对每条约束引入拉格朗日乘子，将SVM问题转换为更易求解的“对偶问题”进行求解。在拉格朗日乘子法转换过程中还可引入核函数，便于将SVM算法推广到非线性分类问题。这样，式（5.73）的拉格朗日函数表达如下其对偶形式为求的极小值。对求偏导，有

联立，得其对偶问题为上式是一个二次规划问题，总能为二次规划问题找到全局极大值点（即支持向量）及对应的，并由计算得到。然后，将代入任意支持向量，得

这样，当使用已经训练好的模型进行测试时时，只需要支持向量而不需要显示地计算参数集。设测试样本为，则式中，为支持向量。4.非线性支持向量机将SVM算法应用于非线性分类问题，需引入核方法将原特征向量映射到高维空间中，使非线性问题转化为线性问题，再使用求解线性问题的方法，寻找变换后特征向量与目标之间的模型。设原特征向量为x，特征映射函数为，则映射到高维空间形成新的特征向量。则用支持向量机方法在高维特征空间划分超平面所对应的模型可表达为则有其对偶问题为

改写为求解后即可得超平面为截距项通过核函数求解得。设任一支持向量，则

这样，对任意未知的测试样本为，则式中，为支持量。5.2聚类学习算法聚类是一种无监督的学习算法，追求的是簇内个体间距小，而簇间间距大。其数学定义如下：对特征空间H中的n个样本，按照样本间的相似程度，将H划分为K个特征区域

，且使得各样本均能归入其中一个特征区域，且不会同时归入两个或多个特征区域，即则称该过程为聚类。聚类具有如下特点：1、聚类是对整个样本集的划分，而不是对单个样本的识别。因此，K等于1或者样本数目是毫无意义的。2、聚类的依据是“样本间的相似程度”，即满足“紧致性”要求：簇内样本间的相似程度要远大于簇间的相似程度。一般用各种距离函数表征这种相似程度，常见的有曼哈顿距离、欧式距离、名考夫斯基距离、切比雪夫距离等。样本间相似程度的度量标准不同，可能造成不同的聚类结果。3、每个样本均确定性地属于某一簇，不会同时属于两个或多个簇。由于聚类是数据驱动的无监督学习算法，常有多种聚类结果出现。一个良好的聚类算法应该具有如下特征：1、良好的可伸缩性。既对数据量小、维度少的数据集有良好的聚类结果，又对数据量大、维度多的数据集有良好性能。2、具有处理不同类型数据的能力。包括数值、图像、文本、序列等各种数据类型以及它们的混合形式。3、处理噪声数据能力。能有效降低噪声对聚类结果的影响，在低质量的数据集中也能获得不错的聚类结果。4、对样本顺序不敏感。不受输入样本顺序影响，任意顺序的相同数据集能得到相同的聚类结果。5、在约束条件下，能够得到更高质量的聚类结果。6、易解释性和易使用性。即聚类的结果易于解释并为大家所接受，且方便使用。5.2.1K均值聚类算法K均值是一种基于划分的聚类算法，其优点是计算速度快、易于理解，是最常用的一种聚类算法。

在K均值聚类中，若样本的距离越近，则说明其相似度越高。通常以距离的倒数表征相似程度，常见的距离计算方法有欧式距离（如式（5.90）所示）和曼哈顿距离（如式（5.91）所示）。式中，x,y均为n维样本。

为保证算法的收敛性，K均值聚类算法常用平方误差函数度量：式中，表示第i个样本；表示第2个样本所属簇的聚类中心（Ce