精读西瓜书(第九章-聚类)-原型聚类

写在前面

  • 昨天, 我们学习了聚类中的距离计算; 今天, 我们将继续学习聚类中的原型聚类.

原型聚类

  • 原型聚类亦称'基于原型的聚类'(prototype-based clustering), 此类算法假设聚类结构能通过一组原型刻画, 在显示聚类任务中极为常用. 通常情形下, 算法先对原型进行初始化, 然后对原型进行迭代更新求解. 采用不同的原型表示, 不同的求解方式, 将产生不同的算法.

k均值算法

  • 给定样本集 , 'k均值'(k-means)算法针对聚类所得簇划分 最小化平方误差
  • 其中 , 是簇 的均值向量. 直观来看, E值越小则簇内样本相似度越高.

学习向量量化

  • 与k均值算法相似, '学习向量量化'(Learning Vector Quantization, 简称LVQ)也是视图找到一组原型向量来刻画聚类结构, 但与一般聚类算法不同的是, LVQ假设数据样本带有类别标记, 学习过程利用样本的这些监督信息来辅助聚类.
  • 给定样本集 , 每个样本 是由n个属性描述的特征向量 , 是样本 的类别标记, LVQ的目标是学得一组n维原型向量 , 每个原型向量代表一个聚类簇, 簇标记 .

高斯混合聚类

  • 与k均值, LVQ用原型向量来刻画聚类结构不同, 高斯混合(Mixture-of-Gaussian)聚类采用概率模型来表达聚类原型.

写在后面

  • 今天, 我们学习了聚类中的原型聚类; 明天, 我们将继续学习聚类中的密度聚类.

精读西瓜书(第九章-聚类)-性能度量

写在前面

  • 昨天, 我们学习了聚类中的聚类任务; 今天, 我们将继续学习聚类中的性能度量.

性能度量

  • 聚类性能度量亦称聚类'有效性指标'(Validity Index). 与监督学习中的性能度量作用相似, 对类似结果, 我们需通过某种性能度量来评估其好坏; 另一方面, 若明确了最终将要使用的性能度量, 则可直接将其作为聚类过程的优化目标, 从而更好地得到符号要求的聚类结果.
  • 聚类是将样本集 划分为若干互不相交的子集, 即样本簇. 那么, 什么样的聚类结果比较好呢? 直观上看, 我们希望'物以类聚', 即同一簇的样本尽可能彼此相似, 不同簇的样本尽可能不同. 换言之, 聚类结果的'簇内相似度'(Intra-Cluster Similarity)高且'簇间相似度'(Inter-Cluster Similarity)低.
  • 聚类性能度量大致有两类. 一类是将聚类结果与某个'参考模型'(Reference Model)进行比较, 称为'外部指标'(External Index); 另一类是直接考察聚类结果而不利用任何参考模型, 称为'内部指标'(Internal Index).
  • 对数据集 , 假定通过聚类给出的簇划分为 . 相应地, 令 分别表示与 对应的簇标记向量. 我们将样本两两配对考虑, 定义:
  • 其中集合 包含了在 中隶属于相同簇且在 中也隶属于相同簇的样本对, 集合 包含了在 中隶属于相同簇但在 中隶属于不同簇的样本对, 由于每个样本对 仅能出现在一个集合中, 因此有 成立. 则有:
  • 显然, 上述性能度量的结果值均在 区间, 值越大越好. 考虑聚类结果的簇划分 , 定义:
  • 其中, 用于计算两个样本之间的距离; 代表簇 的中心点 . 显然, 对应于簇 内样本间的平均距离, 对应于簇 内样本间的最远距离, 对应于簇 与簇 最近样本间的距离, 对应于簇 与簇 中心点检的距离, 则有:

写在后面

  • 今天, 我们学习了聚类中的性能度量; 明天, 我们将继续学习聚类中的距离计算.

精读西瓜书(第九章-聚类)-聚类任务

写在前面

  • 昨天, 我们学习了集成学习中的多样性; 今天, 我们将继续学习聚类中的聚类任务.

聚类任务

  • 在'无监督学习'(unsupervised learning)中, 训练样本的标记信息是未知的, 目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律, 为进一步的数据分析提供基础. 此类学习任务中研究最多, 应用最广的是'聚类'(Clustering).
  • 聚类试图将数据集中的样本划分为若干个通常是不相交的子集, 每个子集称为一个'簇'(Cluster). 通过这样的划分, 每个簇有可能对应于一些潜在的概念(类别). 需要说明的是, 这些概念对聚类算法而言事先是未知的, 聚类过程仅能自动形成簇结构, 簇所对应的概念语义需由使用者来把握和命名.
  • 形式化地说, 假定样本集 包含 个无标记样本, 每个样本 是一个 维特征向量, 则聚类算法将样本集 划分为 个不相交的簇 , 其中 . 相应地, 我们用 表示样本 的'簇标记'(Cluster Label), 即 . 于是, 聚类的结果可用包含 个元素的簇标记向量 表示.
  • 聚类既能作为一个单独过程, 用于找寻数据内在的分布结构, 也可作为分类等其他学习任务的前驱过程. 例如, 在一些商业应用中需对新用户的类型进行判别, 但定义'用户类型'对商家来说却可能不太容易, 此时往往可先对用户数据进行聚类, 根据聚类结果将每个簇定义为一个类, 然后再基于这些类训练分类模型, 用于判别新用户的类型.
  • 基于不同的学习策略, 人们设计出多种类型的聚类算法.

写在后面

  • 今天, 我们学习了聚类中的聚类任务; 明天, 我们将继续学习聚类中的性能度量.

精读西瓜书(第八章-集成学习)-多样性

写在前面

  • 昨天, 我们学习了集成学习中的结合策略; 今天, 我们将继续学习集成学习中的多样性.

误差-分歧分解

  • 欲构建泛化能力强的集成, 个体学习器应'好而不同'. 现在我们来做一个简单的理论分析. 假定我们用个体学习器 通过加权平均法结合产生的集成来完成回归学习任务 . 对示例 , 定义学习器 的'分歧'(Ambiguity)为:
  • 则集成的'分歧'是:
  • 显然, 这里的'分歧'项表征了个体学习器在样本 上的不一致性, 即在一定程度上反映了个体学习器的多样性. 个体学习器 和集成 的平方误差分别为:
  • 表示个体学习器误差的加权均值, 有:
  • 表示样本的概率密度, 则在全样本上有:
  • 类似的, 个体学习器 在全样本上的泛化误差和分歧项分别为:
  • 集成的泛化误差为:
  • 最后有:

写在后面

  • 今天, 我们将继续学习了集成学习中的多样性; 明天, 我们将学习下一个章节, 聚类中的聚类任务.

精读西瓜书(第八章-集成学习)-结合策略

写在前面

  • 昨天, 我们学习了集成学习中的Bagging与随机森林; 今天, 我们将继续学习集成学习中的结合策略.

结合策略

  • 学习器结合可能会从三个方面带来好处: 首先, 从统计的方面来看, 由于学习任务的假设空间往往很大, 可能有多个假设在训练集上达到同等性能, 此时若使用单学习器可能因误选而导致泛化性能不佳, 结合多个学习器则会减小这一风险; 第二, 从计算的方面来看, 学习算法往往会陷入局部极小点所对应的泛化性能可能很糟糕, 而通过多次运行之后进行结合, 可降低陷入糟糕局部绩效点的风险; 第三, 从表示的方面来看, 某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中, 此时若使用单学习期则肯定无效, 而通过结合多个学习器, 由于相应的假设空间有所扩大, 有可能学得更好的近似, 如下图:
  • 假定集成包含 个基学习器 , 其中 在示例 上的输出为 . 本节介绍几种对 进行结合的常见策略.

    平均法

  • 对数值型输出 , 最常见的结合策略是使用平均法(Averaging).
  • 简单平均法(Simple Averaging):
  • 加权平均法(Weighted Averaging):
  • 其中, 是个体学习器 的权重, 通常要求 , .

    投票法

  • 对分类任务来说, 学习器 将从类别标记集合 中预测出一个标记, 最常见的结合策略是使用投票法(Voting). 为便于讨论, 我们将 在样本 上的预测输出表示为一个 维向量 , 其中 在类别标记 上的输出.
  • 绝对多数投票法(Majority Voting):
  • 即若某标记得票过半数, 则预测为该标记; 否则拒绝预测.

  • 相对多数投票法(Plurality Voting):
  • 即预测为得票最多的标记, 若同时有多个标记获得最高票, 则从中随机选取一个.

  • 加权投票法(Weighted Voting):
  • 与甲醛平均法类似, 的权重, 通常 ,

    学习法

  • 当训练数据很多时, 一种更为强大的结合策略是使用'学习法', 即通过另一个学习器来进行结合. Stacking是学习法的典型代表. 这里我们把个体学习器称为初级学习器, 用于结合的学习器称为次级学习器或原学习器(Meta-Learner). Stacking先从初始数据训练集训练处初级学习器, 然后'生成'一个新数据集用于训练次级学习器. 在这个新数据集中, 初级学习器的输出被当做样例输入特征, 而初始样本的标记被当做样例标记. Stacking的算法描述如下图, 这里我们假定初级学习器使用不同学习算法产生, 即初级集成是异质的:
  • 写在后面

  • 今天, 我们学习集成学习中的结合策略; 明天, 我们将继续学习集成学习中的多样性.

精读西瓜书(第八章-集成学习)-Bagging与随机森林

写在前面

  • 昨天, 我们学习了集成学习中的Boosting; 今天, 我们继续学习集成学习中的Bagging与随机森林.

Bagging

  • Bagging是并行式集成学习方法最著名的代表, 从名字即可看出, 它直接基于我们上节介绍过的自助采样法(Boostrap Sampling). 给定包含 个样本的数据集, 我们先随机取出一个样本放入采样集中, 再把改样本放回初始数据集, 使得下次采样时该样本仍有可能被选中, 这样, 经过 次随机采样操作, 我们得到含 个样本的采样集, 初始训练集只能怪有的样本在采样集里多次出现, 有的则从未出现. 照这样, 我们可采样出 个含 个训练样本的采样集, 然后基于每个采样集训练处一个基学习器,再讲这些基学习器进行结合. 这就是Bagging的基本流程. 在对预测输出进行结合时, Bagging通常对分类任务使用简单投票法, 对回归任务使用简单平均法. 若分类预测时出现两个类收到同样票数的情形, 则最简单的做法是随机选择一个, 也可进一步考虑学习器投票的置信度来确定最终胜者. 如下图:
  • 随机森林(Random Forest, 简称RF)是Bagging的一个扩展变体. RF在以决策树为基学习器构建Bagging集成的基础上, 进一步在决策树的训练过程中引入了随机属性选择. 具体来说, 传统决策树在选择划分属性时是在当前节点的属性集合(假定有 个属性)中选择一个最优属性; 而在RF中, 对基决策树的每个节点, 先从该节点的属性集合中随机选择一个包含 个属性的子集, 然后再从这个子集中选择一个最优属性用于划分. 这里的参数 控制了随机性的引入程度: 若令 , 则基决策树的构建与传统决策树相同; 若令 , 则是随机选择一个属性用于划分; 一般情况下, 推荐值 . 如下图:

写在后面

  • 今天, 我们学习了集成学习中的Bagging与随机森林; 明天, 我们将继续学习集成学习中的结合策略.

精读西瓜书(第八章-集成学习)-Boosting

写在前面

  • 昨天, 我们学习了集成学习中的个体与集成; 今天, 我们将继续学习集成学习中的Boosting.

Boosting

  • Boosting是一族可将弱学习器提升为强学习器的算法. 这族算法的工作机制类似: 先从初始训练集训练出一个基学习器, 再根据基学习器的表现对训练样本分布进行调整, 使得闲钱基学习器做错的训练样本在后续受到更多关注, 然后基于调整后的样本分布来训练下一个基学习器; 如此重复进行, 直至基学习器数目达到实现指定的值 , 最终将这 个基学习器进行加权结合.
  • Boosting族算法最著名的代表是AdaBoost, 其描述如下图, 其中 , 是真实函数:
  • AdaBoost算法有多种推导方式, 比较容易理解的是基于'加性模型'(Additive Model), 即机器学习器的线性组合:
  • 来最小化指数损失函数(Exponential Loss Function):
  • 能令指数损失函数最小化, 则考虑对 的偏导:
  • 令上式为零可解得:
  • 因此, 有:
  • 这意味着 达到了贝叶斯最优错误率. 换言之, 若指数损失函数最小化, 则分类错误率也将最小化; 这说明指数损失函数是分类任务原本 损失函数的一直的(Consistent)替代函数. 由于这个替代函数有更好的数学性质, 例如它是连续可微函数, 因此我们用它代替 损失函数作为优化目标. 在AdaBoost算法中, 第一个基分类器 是通过直接将基学习算法用于初始数据分布而得; 此后迭代地生成 当基分类器 基于分布 产生后, 改基分类器的权重 应使得 最小化指数损失函数:
  • 其中 . 考虑指数损失函数的导数:
  • 令其为零可解得:
  • 这恰恰是分类器权重更新公式. AdaBoost算法在获得 之后样本分布将进行调整, 使下一轮的及学习器 能纠正 的一些错误. 理想的 能纠正 的全部错误, 即最小化:
  • 注意到 , 则上式可使用 的泰勒展开式近似为:
  • 于是, 理想的基学习器:
  • 注意到 是一个常数. 令 表示一个分布:
  • 则根据数学期望的定义, 这等价于令:
  • , , 有:
  • 则理想的基学习器:
  • 由此可见, 理想的 将在分布 下最小化分类误差. 因此弱分类器将基于分布 来训练, 且针对 的分类误差应小于 0.5. 在一定程度上类似'残差逼近'的思想. 考虑到 的关系, 有:
  • 这恰是样本分布更新公式, 于是, 我们从基于加性模型迭代式优化指数损失函数的角度推导出了AdaBoost算法. Boosting算法要求基学习器能对特定的数据分布进行学习, 这可通过'重赋权法'(re-weighting)实施, 即在训练过程的每一轮中, 根据样本分布为每个训练样本重新赋予一个权重. 对无法接受带权重样本的基学习算法, 即可通过'重采样法'(re-sampling)来处理, 即在每一轮学习中, 根据样本分布对训练集重新进行采样, 在用重采样而得到的样本集对基学习器进行训练.

写在后面

  • 今天, 我们学习了集成学习中的Boosting; 明天, 我们将继续学习集成学习中的Bagging与随机森林.

精读西瓜书(第八章-集成学习)-个体与集成

写在前面

  • 昨天, 我们结束了对贝叶斯分类器章节的学习; 今天, 我们将继续学习集成学习中的个体与集成.

个体与集成

  • 集成学习(Ensemble Learning)通过构建并结合多个学习器来完成学习任务, 有时也会被称为多分类器系统(Multi-Classifier System), 基于委员会的学习(Committee-Based Learning)等.
  • 如下图, 显示出集成学习的一般结构: 先产生一组'个体学习器'(Individual Learner), 再用策略将它们结合起来. 个体学习器通常由一个现有的学习算法从训练数据产生, 例如C4.5决策树算法, BP神经网络算法等, 此时集成中值包含同种类型的个体学习器, 例如'决策树集成'中全是决策树, '神经网络集成'中全是神经网络, 这样的集成是'同质'的(Homogeneous). 同质集成中的个体学习器亦称'基学习器'(Base Learner), 相应的学习算法称为'基学习算法'(Base Learning Algorithm). 集成也可包含不同类型的个体学习器, 例如同事包含决策树和神经网络, 这样的集成是'异质'的(Heterogenous). 异质集成中的个体学习器由不同的学习算法生成, 这是就不在有基学习算法; 相应地, 个体学习器一般不称为基学习器, 常称为'组件学习器'(Component Learner)或直接称为个体学习器.
  • 集成学习通过将多个学习器进行结合, 长可获得比单一学习器显著优越的泛化性能. 这对'弱学习器'(Weak Learner)尤为明显, 因此集成学习的很多理论研究都是针对若学习器进行的, 而基学习器有时也被直接成为弱学习器. 但需注意的是, 虽然从理论上来说使用弱学习器集成足以获得好的性能, 但在实践中出于种种考虑, 例如希望使用较少的个体学习器, 或是重用关于常见学习器的一些经验等, 人们往往会使用比较强的学习器. 在一般经验中, 如果把好坏不等的东西掺到一起, 那么通常结果会是比最坏的要好一些, 比最好的要坏一些. 集成学习把多个学习器结合起来, 如何能获得比最好的单一学习器更好的性能呢?
  • 考虑一个简单的例子: 在二分类任务中, 假定三个分类器在三个测试样本上的表现如下图, 其中 表示分类正确, 表示分类错误, 集成学习的结果通过投票法(Voting)产生, 即'少数服从多数'. a图中每个分类器都只有 的精度, 但集成学习却高达了 ; 在b图中, 三个分类器没有差别, 集成之后性能没有提高; 在c图中, 每个分类器的精度都只有 , 集成学习的结果变得更糟. 这个简单的例子显示出: 要获得好的集成, 个体学习器应'好而不同', 即个体学习器要有一定的'准确性', 即学习器不能太坏, 并且要有'多样性'(Diversity), 即学习器间具有差异.
  • 我们来做个简单的分析. 考虑二分类问题 和真实函数 , 假定基分类器的错误率为 , 即对每个基分类器 有:
  • 假设集成通过简单投票法结合 个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确:
  • 假设基分类器的错误率相互独立, 则由Hoeffding不等式可知, 集成的错误率为:
  • 上式显示出, 随着集成中个体分类器数目 的增大, 集成的错误率将指数级下降, 最终趋向于零. 然而我们必须注意到, 上面的分析有一个关键假设: 及学习期的误差相互独立. 在现实任务中, 个体学习器是为解决同一个问题训练出来的, 他们显然不可能互相独立! 事实上, 个体学习器的'准确性'和'多样性'本身就存在冲突. 一般的, 准确性很高之后, 要增加多样性就需要牺牲准确性. 事实上, 如何产生并结合'好而不同'的个体学习器, 恰是集成学习研究的核心. 更具个体学习器的生成方式, 目前的集成学习方法大致可分为两大类, 即个体学习器间存在强依赖关系, 必须串行生成的序列化方法, 以及个体学习器间不存在强依赖关系, 可同时生成的并行化方法; 前者代表是Boosting, 后者的代表是Bagging和'随机森林'(Random Forest).

写在后面

  • 今天, 我们学习了集成学习中的个体与集成; 明天, 我们将继续学习集成学习中的Boosting.

精读西瓜书(第七章-贝叶斯分类器)-EM算法

写在前面

  • 昨天, 我们学习了贝叶斯分类器中的贝叶斯网; 今天, 我们将继续学习贝叶斯分类器中的EM算法.

EM算法

  • 在前面的讨论中, 我们一直假设训练样本所有属性变量的值都已被观测到, 即训练样本是'完整'的. 但在现实应用中往往会遇到'不完整'的训练样本. 未观测变量的学名是'隐变量'(Latent Variable). 令 表示已观测变量集, 表示隐变量集, 表示模型参数. 若欲对 做极大似然估计, 则应最大化对数似然:
  • 然而由于 是隐变量, 上式无法直接求解. 此时我们可以通过对 计算期望, 来最大化已观测数据的对数'边际似然'(Marginal Likelihood):
  • EM(Expectation-Maximization)算法是常用的估计参数隐变量的利器, 他是一种迭代式的方法, 其基本想法是: 若参数 已知, 则可更具训练数据推断出最优隐变量 的值(E步); 反之, 若 的值已知, 则可方便地对参数 做极大似然估计(M步). 于是, 以 为起点, 可迭代执行以下步骤直至收敛
  • 这就是EM算法的原型.
    - 进一步, 若我们不是取 的期望, 而是基于 计算隐变量 (Z) 的概率分布 , 则EM算法的两个步骤是:

  • 简单来说, EM算法使用两个步骤交替计算: 第一步是期望(E)步, 利用当前估计的参数值来计算对数似然的期望值; 第二部是最大化(M)步, 寻找能使E步产生的似然期望最大化的参数值. 然后得到的参数值重新被用于E步, ......直至收敛到局部最优解.
  • 事实上, 隐变量估计问题也可以通过梯度下降等优化算法求解, 但由于求和的项数将随着隐变量的数目以指数级上升, 会给梯度计算带来麻烦; 而EM算法则可看做一种非梯度优化方法.

写在后面

  • 今天, 我们学习了贝叶斯分类器中的EM算法; 明天, 我们将学习下一个章节, 集成学习中的个体与集成.

精读西瓜书(第七章-贝叶斯分类器)-贝叶斯网

写在前面

  • 昨天, 我们系统的学习了贝叶斯分类器中的半朴素贝叶斯分类器; 今天, 我们继续学习贝叶斯分类器中的贝叶斯网.

贝叶斯网

  • 贝叶斯网(Bayesian Network)亦称'信念网'(Belief Network), 它借助有向无环图(Directed Acyclic Graph, 简称DAG)来刻画属性之间的依赖关系, 并使用条件概率表(Conditional Probability Table, 简称CPT)来描述属性的联合概率分布.
  • 具体来说, 一个贝叶斯网 由结构 和参数 两部分构成, 即 . 网络结构 是一个有向无环图, 其每个节点对应一个属性, 若两个属性有直接依赖关系, 则他们由一条边连接起来; 参数 定量描述这种依赖关系, 假设属性 中的父结点集为 , 则 包含了每个属性的条件概率表 .

结构

  • 贝叶斯网结构有效地表达了属性建的条件独立性. 给定父节点集, 贝叶斯网假设每个属性与它的非后裔属性独立, 于是 将属性 的联合概率分布定义为:
  • 联合概率分布定义为:
  • 显然, 在给定 的取值时独立, 在给定的 取值时独立, 分别简记为 . 下图显示出贝叶斯网中三个变量之间的典型依赖关系:
  • 在'同父'(Common Parent)结构中, 给定父节点 的取值, 则 条件独立. 在'顺序'结构中, 给定 的值, 则 条件独立. V型结构(V-Structure)亦称'冲撞'结构, 给定子结点 的取值, 必不独立; 奇妙的是, 若 的取值完全未知, 则V型结构下 却是相互独立的.
  • 事实上, 一个变量取值的确定与否, 能对另两个变量间的独立性发生影响, 这个现象并非V型结构所特有.

学习

  • 若网络结构已知, 即属性间的依赖关系已知, 则贝叶斯网的学习过程相对简单, 只需通过对训练样本'计数', 估计出每个节点的条件概率表即可. 但在现实应用中我们往往并不知晓网络结构, 于是, 贝叶斯网学习的首要任务就是根据训练数据集来找出结构最'恰当'的贝叶斯网. '评分搜索'是求解这一问题的常用办法. 具体来说, 我们先定义一个评分函数(Score Function), 以此来评估贝叶斯网与训练数据的契合程度, 然后基于这个评分函数来寻找结构最优的贝叶斯网. 显然, 评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好.
  • 常用评分函数通常基于信息论准则, 此类准则将学习问题看做一个数据压缩任务, 学习的目标是找到一个能以最短编码长度和使用该模型描述数据所需的字节长度. 对贝叶斯网学习而言, 模型就是一个贝叶斯网, 同事, 每个贝叶斯网描述了一个在训练数据上的概率分布, 自由一套编码机制能使那些经常出现的样本有更短的编码. 于是, 我们应选择那个综合编码长度(包括描述网络和编码数据)最短的贝叶斯网, 这就是'最小描述长度'(Minimal Description Length, 简称MDL)准则.

推断

  • 贝叶斯网训练好之后就能用来回答'查询'(Query), 即通过一些属性变量的观测值来推测其他属性变量的取值. 通过已知变量观测值来推测待查询变量的过程称为'推断'(Inference), 已知变量观测值为'证据'(Evidence).
  • 最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率, 不幸的是, 这样的'精确推断'已被证明是NP难的; 换言之, 当网络结点较多, 链接稠密时, 难以进行精确推断, 此时需借助'近似推断', 通过降低精度要求, 在有限时间内求得近似解. 在现实应用中, 贝叶斯网的近似推断常使用吉布斯采样(Gibbs Sampling)来完成, 这事一种随机采样方法

写在后面

  • 今天, 我们学习了贝叶斯分类器中的贝叶斯网; 明天, 我们将继续学习贝叶斯分类器中的EM算法.