机器学习算法与实践 课件 第11章 半监督学习

第十一章半监督学习半监督学习（Semi-SupervisedLearning，SSL）是模式识别和机器学习领域研究的重点问题，是监督学习与无监督学习相结合的一种学习方法。许多实例采用无监督标记来提高预测精度和学习算法的速度；通过引入加权系数动态调整无类标签样例的影响，提高了分类准确度；建立每类中具有多个混合部分的模型，使贝叶斯偏差减小。半监督学习使用大量的未标记数据，同时使用标记数据来进行模式识别工作。111.1未标记样本

如果图中有一个样本恰好位于正负实例中间，可以在图中看到大体上类似于随机猜测。如果观察到图中的未标记样本，则可以基于聚类假设来利用未标记样本，由于待预测样本与正例样本通过未标记样本的“撮合”聚集在一起，与相对分离的反例样本相比，可以将该样本判定为正例。211.1未标记样本

311.2半监督学习方法半监督学习可进一步划分为纯半监督学习和直推学习，前者假设训练数据中的样本不显著，而后者则假定学习过程中所考虑的未标记样本恰好是待预测数据，学习目的就是在这些未标记样本中获得最优泛化性能。4

11.2.1生成式方法

5

11.2.1生成式方法6

（11-2）

11.2.1生成式方法7

11.2.1生成式方法8

生成式方法简单，易于实现，在有标记数据极少的情形下往往比其他方法性能更好。

然而，此类方法中模型假设必须准确，即假设的生成式模型必须与真是数据分布吻合，否则未用未标记数据反倒会降低泛化性能。现实任务中，除非拥有充分可靠的领域知识，否则往往很难事先做出准确的模型假设。

11.2.2半监督SVM半监督支持向量机（Semi-SupervisedSupportVectorMachine，简称S3VM），S3VM是一种在半监督学习上推广的广义支持向量机。在不考虑未标记样本的情况下，支持向量机尝试寻找最大间隔划分超平面。在考虑未标记样本后，S3VM尝试寻找能够划分开两类有标记样本，且可以通过低密度区域分割将它们分开的超平面，如图所示，其中“+”和“-”分别表示有标记的正例和反例，蓝色点表示未标记样本。9

11.2.2半监督SVM10

在传统的支持向量机有监督学习中，我们试图找到超平面的分割点，使得两个半监督学习点之间的距离很小。S3VM考虑了超平面通过区域的情况，S3VM的主要思想是将每个标记样本分为阳性样本和阴性样本。首先利用标记样本集和初始支持向量机进行训练，然后利用机器对未标记样本进行标记，使所有样本稳定然后采用局部迭代搜索最优策略。

11.2.3图半监督学习基于图的半监督学习方法是一种利用数据集的图结构进行学习的技术。其主要思想是通过构建一个图来表示数据集，其中节点代表标记和未标记的数据点，边表示数据点之间的相似性或关联关系。通过赋予边权重来度量数据点的相似性，权重越大表示相似性越高。在该方法中，如果两个样本之间的相似度较高，就可以将它们映射到相应的节点上。通过给已标记的样本节点着色，未标记的样本节点不着色，可以观察到节点的颜色分布情况，从而进行半监督学习。11

11.2.3图半监督学习基于图的半监督学习方法通常包括以下步骤：1）构建图：根据数据集的相似性，构建一个图结构，其中节点表示数据点，边表示相似性关系。2）赋权重：为图中的边赋予权重，以度量数据点之间的相似性，常用的距离度量有欧几里德距离、马氏距离、切比雪夫距离等。3）标记节点：将已标记的样本节点着色，表示其已知类别信息。4）扩散过程：通过图的结构和节点的颜色信息，将标记信息扩散到未标记的节点上，以获得它们的预测标签。5）分类或回归：使用已标记和预测标记的节点进行分类或回归任务。12

11.2.4基于分歧的方法基于分歧的方法使用多学习器，而学习器之间的“分歧”的决策，就需要用到未标记数据。在某些应用任务中，一个数据集可能包含多个属性集，此时每个数据样本同时拥有多个特征向量描述；这里的每个属性集即被称为数据的一个“视图（View）”。基于分歧的半监督学习的起源、也是最著名的代表性方法是“协同训练法”，由于最初的设计是针对多视图数据的，所以也被看作是多视图学习的代表。协同训练法要求数据具有两个充分冗余且满足条件独立性的视图，“充分”是指每个视图都包含足够产生最优学习器的信息，此时对其中任一视图来说，另一个视图则是“冗余”的；同时，对类别标记来说这两个视图条件独立。13

11.2.4基于分歧的方法协同训练法的学习过程：首先分别在每个视图上利用有标记样本训练一个分类器，然后，每个分类器从未标记样本中挑选若干标记置信度（即对样本赋予正确标记的置信度）高的样本进行标记，并把这些“伪标记”样本（即其标记是由学习器给出的）加入另一个分类器的训练集中，以便对方利用这些新增的有标记样本进行更新。这个“互相学习、共同进步”的过程不断迭代进行下去，直到两个分类器都不再发生变化，或达到预先设定的学习轮数为止。1411.3半监督聚类半监督聚类是一种结合了无监督学习和半监督学习思想的聚类方法。它利用有限的标记数据和大量的未标记数据，通过将样本分组成不同的簇来发现隐藏在数据中的结构和模式。传统的聚类算法通常只利用未标记数据进行无监督学习，而半监督聚类则通过引入标记数据的先验知识或约束条件来指导聚类过程，从而提高聚类的准确性和鲁棒性。15这类方法使用用户提供的标签或先验知识作为约束条件来指导聚类过程。常见的约束条件包括“必连”和“勿连”关系，即将两个样本标记为必须属于同一簇或不能属于同一簇。基于约束的方法通常通过优化目标函数来确保尽量满足约束条件。具体可以分为如下几种：

11.3.1基于约束的方法让样本无条件满足给定的约束条件引入惩罚因子（或罚参数）施加独立的类标签（或种子集）作为约束16约束K均值聚类算法的基本过程：1）初始化：选择初始的K个聚类中心。2）聚类分配：根据当前的聚类中心，将每个样本分配到最近的聚类中心所代表的簇。3）约束调整：根据给定的约束信息，对聚类结果进行调整。可以根据约束条件来判断当前的聚类结果是否满足要求，并对不符合约束的样本进行调整。调整的具体方式可以根据具体约束的特点而定，例如将不满足约束的样本重新分配到合适的簇中。4）更新聚类中心：根据调整后的聚类结果，更新每个簇的聚类中心。5）重复步骤2至步骤4，直到满足停止条件（例如达到最大迭代次数或聚类结果不再变化）。

11.3.1基于约束的方法17基于距离的半监督聚类方法是一种常见的半监督聚类算法，它结合了无标签数据和有标签数据中的距离信息，来指导聚类过程。通常情况下，已知标签数据会提供一些关于簇之间相对位置或距离的先验知识，从而有助于更准确地分配无标签数据到相应的簇中。

11.3.2基于距离的方法18基于距离的半监督聚类方法的一般步骤：1）初始化：选择初始的聚类中心。2）聚类分配：根据当前的聚类中心，将每个无标签样本分配到最近的聚类中心所代表的簇。3）标签约束：使用已知标签数据来调整聚类结果。可以通过计算带标签数据和无标签数据之间的距离，然后将这些距离作为约束引入聚类过程。可以根据已知标签数据的信息，对聚类中心进行调整，或者调整样本之间的距离度量方式，以更好地满足先验的标签约束。4）更新聚类中心：根据调整后的聚类结果，更新每个簇的聚类中心。5）重复步骤2至步骤4，直到满足停止条件（例如达到最大迭代次数或聚类结果不再变化）。

11.3.2基于距离的方法19常见的基于距离的半监督聚类方法可以分为以下三种：基于凸优化问题调整样本间的距离基于最短路径算法调节样本之间的距离基于谱聚类方法，通过约束信息来控制样本之间的距离

11.3.2基于距离的方法20

11.3.2基于约束和距离的方法快速K均值算法（FastK-means）该方法使用已知标签数据的信息来调整样本之间的距离，从而改善聚类结果。具体而言，该方法通过引入距离约束，将已知标签数据限制在其对应的簇附近，并根据这些约束来更新聚类中心。这样可以更好地利用已知标签的信息，提高聚类的准确性。21

11.3.2基于约束和距离的方法快速K均值算法的基本过程：

1）随机选择k个样本作为初始聚类中心；2）根据当前的聚类中心，计算每个样本与聚类中心的距离，并将样本分配给距离最近的聚类中心所对应的簇；3）对每个簇，计算簇内所有样本的均值，并将该均值作为新的聚类中心；4）重复执行步骤2，步骤3直到收敛，即簇的分配不再改变或达到最大迭代次数5）在步骤4中将每个样本的簇分配结果进行记录。22

11.3.2基于约束和距离的方法度量学习半监督聚类（MetricLearningforSemi-SupervisedClustering）

该方法旨在通过学习一个合适的距离度量来改善聚类质量。该方法使用已知标签数据的信息来训练一个度量函数，使得同一类别样本之间的距离较小，不同类别样本之间的距离较大。通过优化度量函数，可以调整样本之间的距离，从而更好地聚类数据。23

11.3.2基于约束和距离的方法度量学习半监督聚类算法的基本过程：

1）根据样本距离矩阵D构建簇关联矩阵A；2）将簇关联矩阵A规范化得到拉普拉斯矩阵L；3）对拉普拉斯矩阵L进行特征分解，得到特征值和特征向量；4）根据前k个最小的特征值对应的特征向量构建新的数据表示Z；5）使用K-means聚类算法对新的数据表示Z进行聚类，得到聚类结果C。24

11.4