基于Markov性半监督流行学习算法研究.pdfVIP

沈亮等：基于Markov性的半监督流行学习算法研究 在实际分类问题中，由于对样本进行标签通常需要大量的人力、物力和财力，所 以用于分类的标 签点通常是有限的，这样对于大多数分类算法而言就可能导致预测效果较差．因此，分类学习算法 (特 别是有监督的1都面临着如何从大量的无标签训练集 中来挖掘数据的信息这个难题．所 以，如何进行 有效的模式识别并改善分类器的预测能力仍然是当今应用概率统计所面临的问题．在模式识别中核函 数的框架下，本文结合具有 Markov性的流行学习来构造一类半监督的统计算法，并对模拟数据和三 个真实的药物动力学数据进行分类．实验结果表明，一类基于Markov性的半监督流行分类算法 【，】 fmanifoldsemi—supervisedclassification，MSSC)可以挖掘样本中内在的流行结构并且可以有效地处理 非线性分类问题． 2 理论及方法 2．1 流行学习的算法原理 作为一种半监督学习算法，流行学习算法 (MSSC)是由文献 [4，21】针对模式识别问题提出的，已 经被广泛的应用于图像处理、文本分类和信号识别等领域 (参见文献 [211)．根据有标签的数据集和无 标签的数据集所反映出来的内在结构，流行学习可以更好地进行分类，特别是对 病“态”的分类 问题 (标签样本少、维数高)也能得到有效的、稳定的预测效果． 给定一个数据集 = xl，… ，Xl，Xl+l，… ，zn)C ， 标签类别集合为 L一{1…．，c)，前2个样本zi(i2)是所对应的标签Yi∈L，其余的点 (2+1U n)是无标签的样本．令 表示元素非负的nxc的矩阵所组成的集合．矩阵F=[砰 …．，碍 】T∈ 可 以理解成一个向量函数 F：)(_÷ 。，每一个 向量 与 Xt相对应，每个 的标签为 定义 礼×C的矩阵Y ∈厂，如果 Xi是标签样本点且对应的标签 Yi=J，则令 J=1；否则为 0．很明 显，矩阵y与初始标签点相一致．具体算法如下： 第 1步 首先构建邻接矩阵 ， W ={叫 Ii，J=1… ．，n) 其中叫 表示 Xi与 间的相似性测度．设 G=(E)表示一个图，其中V代表所有节点 (样本点) 组成的集合，E表示边．边的权重用邻接矩阵中的相似性测度 枷 来表示，若 叫 0，表示节点 Xi 与 相连且权重为 wij；若 =0，则称 Xi与 是不相连的．同时，为了消除节点的自增强性，令 Wii= 0． 第 2步 对矩阵 标准化从而生成转移概率矩阵S， S ：D一1／2W D一1／2 其中J[)为对角矩阵并且 D为 中第 i行元素之和 第 3步 基于转移概率矩阵 S，利用公式 F(t+1)=~sF(t)+(1一 )y (2．1) 704 中国科学：数学 第 45卷 第 5期 进行迭代，其中 ∈(0，1)．从而，y 中标签点的初始得分值 l就可 以通过迭代被不断地传递． 第 4步 令 表示序列 {F())的收敛值，则每个数据Xt的标签为 Yi=argmax≤F5．收敛性 的证明请参见文献 f211． 直观上来说，如果把算法中的图G表示成一个复杂网络的话，则 Wj表示从一个节点转移到另一 个节点的概率．此：过程相当于一个 Markov链，具有 Markov性．如果X 没有向外的连接，则 中的 第 i行为 0．通过第 2步标准化之后，S中则不会有行和为 0的行，S则为一个随机矩阵．通过不断地 迭代，最终网络达到一个平稳分布．平稳分布中各节点的概率值即为节点属于不同类别的得分值． 2．2 一类流行学习算法的构造 由于大量实际问题是具有多类别的高维复杂模式的识别，因此研究复杂模式的分析和分类方法是 必要而且有意义的．基于核函数的学习方法 (简称核方法)本质上是非线性的信息处理工具，它在处理 具有非线性关系的高维复杂模式识别问题时，有着其他方法无法 比拟的优越性．核方法是解决非线性 模式分析问题的一种有效途径，其核心思想是，首先，通过某种非线性映射将原始数据嵌入到合适的 高维特征空间：然后