·99· 邓廷权，等：半监督类保持局部线性嵌入方法 第1期 据效果较好，成为当前数据挖掘的热门方向之 低维特征矩阵，Y=yy…yT,y:∈R,dm。 一。流形学习6作为一种非线性特征提取方法， 对于每个数据点，计算每一个数据点x到其 应用了流形在局部结构上与欧氏空间同胚的性 它点的欧氏距离，找到最近的k个点作为该数据 质。通过对高维数据样本的分析来挖掘隐藏的本 样本的近邻，确定数据的k近邻域。也可采用ε 质结构，从而提取有效的低维特征。然而，流形 邻域方法确定数据的近邻点。 学习方法仍然存在一些不足，例如：流形学习方 假设任一点x都可用它的k近邻通过线性权值 法忽略了数据的类别标记信息，提取的特征并不 wj=1,2,…,k加权来得到，由以下优化问题求解 是分类上的最优特征。因此，忽略标记信息而提取 线性重构的权矩阵w=wTw…w]下=(wm,为 到的特征在进行数据聚类或分类时，结果往往与 实际存在较大差异。所以希望可以使用半监督 mins(w 的方法进行学习，即少量标记信息来指导特征提 (1) 取，同时又使用大量无标记信息的数据点来刻画 S.t. =1 =1 并保持样本的局部或全局几何、线性等结构。 容易获得优化问题式(1)的最优解： 局部线性嵌入(LLE)是一种无监督的流 rG 形学习方法，直接用它提取的特征进行数据挖掘 w:-MTG.T (2) 如聚类或分类得到的结果并不是很理想。因此我 式中：G:=(gy)是一个k×k的Gram矩阵（距离矩 们希望将数据集的标记信息引入到LLE方法中 阵)；g=(G-xax-);T=(1,1,…,1)F是一个 用以提高特征提取效果。而已有的一些半监督方 k×1的全1矩阵；x表示样本x的第I个近邻点。 法，例如半监督局部线性嵌人方法(semi-super- 记g1=x-x,则g5=gag。 vised locally linear embedding,SSLLE)虽然利用了 基于局部线性重构矩阵式(2)，构造优化问题： 标记信息对特征提取进行一定的改进，但它只考 虑了近邻点的标记信息做局部调整，因此当整体 mino(Y 标记信息较低时每个近邻中将有可能出现没有标 (3) 记点的情况。这时SSLLE将失去作用并且由于 st.∑yy=∑y=0 它只考虑近邻的这种调整，当标记信息很多时它 获得高维数据X的低维嵌入Y。 们整体的区分度也不大。本文在LLE的基础上 根据样本的邻域点分布将k维行向量w:扩 利用近邻伪标签赋予得到的标记信息作局部调 充成n维行向量W,记W=[WW灯…W]P,M= 整，同时从全局角度对同类数据点和异类数据 (I-W'(I-W,则优化问题式(3)的目标函数可化 点进行全局调整，使得重构数据低维特征空间 简为r(YTMY) 时，既保持局部线性结构，又能使提取后的数据 采用拉格朗日乘子法求解优化问题式(3)，可 在低维特征空间中可以实现具有相同标记信息的 得MY=AY。即式(3)可转化为求特征值问题。 数据点互相靠近，而标记不同的数据点彼此分 实对称半正定矩阵M的最小d个非0特征值对 离，从而达到更好的特征提取结果。最后通过聚 应的特征向量按列排列时，每行做成的向量的就 类分析及可视化证明本文方法的有效性。 是对应数据的低维特征：。 1局部线性嵌入 2半监督类保持局部线性嵌入方法 由Roweis等提出的LLE是一个经典的保持 在数据挖掘任务中，监督信息为用户提供强 局部线性特性的流形学习方法，可以有效提取高 有力的数据分析基础。然而，众多实际问题只能 维数据的低维特征。其基本原理为：假设数据是 获得少量样本的监督标记。半监督机器学习方法 分布在一个流形上的，任一点均可用它的近邻点 应运而生。 经由线性重构而得到。基于局部线性表示系数， LLE是一种经典的无监督高维数据特征提取 构造优化问题使得数据在高维原始空间到低维特 方法。本文在LLE基础上提出一种半监督类保 征空间的过程中局部线性重构权值不发生变化， 持局部线性嵌入方法(SSCLLE)。该方法不仅利 获得高维数据的低维特征。 用近邻伪标签赋予得到的标记信息调整近邻数据 假设数据集X={x,2,…,x}中有n个样本点 间的距离，而且从全局角度加入了同类数据点和 x,x:∈Rm,ie[l,川，YeRd为特征提取后获得的n个 异类数据点的全局约束，使提取后的数据在低维据效果较好，成为当前数据挖掘的热门方向之 一。流形学习[1-6] 作为一种非线性特征提取方法， 应用了流形在局部结构上与欧氏空间同胚的性 质。通过对高维数据样本的分析来挖掘隐藏的本 质结构，从而提取有效的低维特征。然而，流形 学习方法仍然存在一些不足，例如：流形学习方 法忽略了数据的类别标记信息，提取的特征并不 是分类上的最优特征。因此，忽略标记信息而提取 到的特征在进行数据聚类或分类时，结果往往与 实际存在较大差异。所以希望可以使用半监督[7-14] 的方法进行学习，即少量标记信息来指导特征提 取，同时又使用大量无标记信息的数据点来刻画 并保持样本的局部或全局几何、线性等结构。 局部线性嵌入 (LLE)[15] 是一种无监督[16] 的流 形学习方法，直接用它提取的特征进行数据挖掘 如聚类或分类得到的结果并不是很理想。因此我 们希望将数据集的标记信息引入到 LLE 方法中 用以提高特征提取效果。而已有的一些半监督方 法，例如半监督局部线性嵌入方法 (semi-super￾vised locally linear embedding, SSLLE) 虽然利用了 标记信息对特征提取进行一定的改进，但它只考 虑了近邻点的标记信息做局部调整，因此当整体 标记信息较低时每个近邻中将有可能出现没有标 记点的情况。这时 SSLLE 将失去作用并且由于 它只考虑近邻的这种调整，当标记信息很多时它 们整体的区分度也不大。本文在 LLE 的基础上 利用近邻伪标签赋予得到的标记信息作局部调 整，同时从全局[17] 角度对同类数据点和异类数据 点进行全局调整，使得重构数据低维特征空间 时，既保持局部线性结构，又能使提取后的数据 在低维特征空间中可以实现具有相同标记信息的 数据点互相靠近，而标记不同的数据点彼此分 离，从而达到更好的特征提取结果。最后通过聚 类分析及可视化证明本文方法的有效性。 1 局部线性嵌入 由 Roweis 等提出的 LLE 是一个经典的保持 局部线性特性的流形学习方法，可以有效提取高 维数据的低维特征。其基本原理为：假设数据是 分布在一个流形上的，任一点均可用它的近邻点 经由线性重构而得到。基于局部线性表示系数， 构造优化问题使得数据在高维原始空间到低维特 征空间的过程中局部线性重构权值不发生变化， 获得高维数据的低维特征。 X = {x1, x2,··· , xn} xi xi ∈ R m i ∈ [1,n] Y ∈ R n×d n 假设数据集 中有 n 个样本点 , , , 为特征提取后获得的 个 Y = [y T 1 y T 2 ··· y T n ] T yi ∈ R d 低维特征矩阵， ， ,d ≪ m 。 xi ε 对于每个数据点，计算每一个数据点 到其 它点的欧氏距离，找到最近的 k 个点作为该数据 样本的近邻，确定数据的 k 近邻域。也可采用 邻域方法确定数据的近邻点。 xi wi j, j = 1,2,··· , k w = [w T 1 w T 2 ··· w T n ] T = (wi j)k×n 假设任一点 都可用它的 k 近邻通过线性权值 加权来得到，由以下优化问题求解 线性重构的权矩阵 ，为 minε(w) = ∑n i=1 xi − ∑k j=1 wi jxj 2 s.t. ∑k j=1 wi j = 1 (1) 容易获得优化问题式 (1) 的最优解： wi = Γ TG −1 i ΓTG−1 i Γ (2) Gi = (g i l j) k×k Gram g i l j = (xi − xil)(xi − xi j) T Γ = (1,1,··· ,1)T k×1 xil xi gil = xi − xil g i l j = gil g T i j 式中： 是一个 的 矩阵 (距离矩 阵 )； ； 是一个 的全 1 矩阵； 表示样本 的第 l 个近邻点。 记 ，则 。 基于局部线性重构矩阵式 (2)，构造优化问题： minσ(Y) = ∑n i=1 yi − ∑k j=1 wi jyj 2 s.t. ∑n i=1 y T i yi = I, ∑n i=1 yi = 0 (3) 获得高维数据 X 的低维嵌入 Y。 wi Wi W = [WT 1 WT 2 ··· WT n ] T M = (I−W) T (I−W) tr( Y TMY) 根据样本的邻域点分布将 k 维行向量 扩 充成 n 维行向量 ，记 ， ，则优化问题式 (3) 的目标函数可化 简为 。 MY = λY yi 采用拉格朗日乘子法求解优化问题式 (3)，可 得 。即式 (3) 可转化为求特征值问题。 实对称半正定矩阵 M 的最小 d 个非 0 特征值对 应的特征向量按列排列时，每行做成的向量的就 是对应数据的低维特征 。 2 半监督类保持局部线性嵌入方法 在数据挖掘任务中，监督信息为用户提供强 有力的数据分析基础。然而，众多实际问题只能 获得少量样本的监督标记。半监督机器学习方法 应运而生。 LLE 是一种经典的无监督高维数据特征提取 方法。本文在 LLE 基础上提出一种半监督类保 持局部线性嵌入方法 (SSCLLE)。该方法不仅利 用近邻伪标签赋予得到的标记信息调整近邻数据 间的距离，而且从全局角度加入了同类数据点和 异类数据点的全局约束，使提取后的数据在低维 ·99· 邓廷权，等：半监督类保持局部线性嵌入方法 第 1 期