·304· 智能系统学报 第15卷 其中，o%是节点b的传出链路数；o是节点c的传 其中，()是一个具有尺度参数σ的高斯核函 出链路数。 数，(x,4)=exp(-x-4l/2o2)是最常用的高斯 wpr(b)的计算需要迭代过程来调整近似到理 核函数之一，其中，σ控制着每个数据点的局部 论真值，wpr表示节点的加权PageRank权重，所 邻域。根据核尺度参数σ的自调整策略，在本文 有节点的wpr初始值初始化为l/n,n为节点数。 所提算法中，设置σ2=0，YΦ(x,u),其中σ：是 在每个迭代中，每个节点b的wpr(b)计算如下： i的邻居点的平均距离，也是Z ERPXn的稀疏表 wpr(b)=I-d④wpr(a)+d∑wpr(awaw(④) 示中的非零元素。对于W亲和矩阵，认为W= 在每次迭代中，所有节点的wpr值都是基于式 2T2,其中2=DrZ是D=∑，乙：度矩阵的归一 (4)减小的。对于所有节点当满足以下的停止 化Z。 准则时，迭代过程停止： 如果计算所有数据点的相似性矩阵并将其作 Nprb)a-1-wpr(b)延≤B 为堆叠式自动编码器的输入，对于大型数据集来 (5) wpr(b)er 说空间消耗非常高。代替计算给定数据与所有其 其中，分数是前一次迭代与当前迭代之间的归一 他数据点的相似性，本文算法只考虑选择的地标 化差值，B是一个预定义的停止阈值，这里设置 点与其他数据点之间的相似性。在这里重写了如 B=10-3。最后当式(5)成立时，选择wpr最高的p 下拉普拉斯矩阵的形式： 节点作为地标点。 Lnew =SST (8) 2改进地标表示的自编码谱聚类算法 在这里使用S作为叠加自编码器的输人，从 前文可以知道归一化相似矩阵可以用稀疏表示矩 2.1构造新的拉普拉斯矩阵 阵Z,为了进一步降低计算复杂度，在这里使用一 在文献[14-15]中，提出了基于地标点的谱聚 种简单的方法计算度矩阵D2,矩阵的主要对角线 类算法来加速谱聚类，在给定n个数据点的数据 元素一般计算如下： 集的情况下，选择p<n个具有代表性的数据点 d=∑w=∑22 (9) 作为地标的特征点，将原始数据点表示为这些地 对式(11)进行运算演化可以得到： 标的线性稀疏组合，然后利用基于地标的表示来 高效地计算数据的谱嵌入，并通过理论分析证明 d山--=g28=2 (10) 1 其性能优于Nystruom和快速谱聚类方法，有效地 = 利用稀疏表示矩阵逼近了整个图的相似度矩阵。 其中，2是一个p×1的向量，第k个元素是2中 它表示选定的p个地标点与n个数据点之间的成 第k行元素的和。 对相似性。 D2=diag() (11) 给定数据矩阵X={x1,2…xn}∈R4,它可以 在这里新的拉普拉斯矩阵的构造如下： 近似为X≈UZ。U每一列都可以看作捕捉数据 Le=DPWDR=D:E2TZDR (12) 中较高层次特征的基向量。选定的地标点可以看 S=D-IPaT (13) 作是基向量。假设对于任何数据，已经有了地标 最后，将相似度矩阵S输入到自动编码器中，最 矩阵U。对于任意点x,它的近似￡：计算为 后运行k-means聚类，从而得到聚类结果。 (6) 2.2自编码器与聚类优化 自动编码器是一种用于有效编码和降维的无 根据稀疏编码策略，假设当x,更接近4时， 监督学习的人工神经网络。自动编码器的目的是 矩阵Z的第j个元素应该更大。为了强调这一假 使原始输人：和新的嵌入表示y的重构输出m 设，创建Z亲和稀疏矩阵的稀疏表示，通过选择 之间的重构损失最小化69。重构损失定义如下 r<p个最近的地标点，代替p个地标点(U∈R), N 例如，如果不是r的最近的地标之一，则z的 L=∑1,8f;0):》 (14) 值为0，生成稀疏表示矩阵Z。设Uo∈R表示 U的子矩阵，由x:最近的r个地标点组成，然后 其中，{0,2}=h1,b,2,b2}是自动编码器的参数。 计算出每个z#元素如下： 虽然用自编码器配合得到聚类结果，有效地 Φ(x,u) 降低了计算复杂度，减小了空间复杂度。但是， Zi= Φ(x,u） iE1,2,....n,and,jeU (7) 由于需要计算和保存所有数据点的相似关系，因 fEUu 此内存消耗进一步增加。学习表示与聚类分离，其中，ob 是节点 b 的传出链路数；oc 是节点 c 的传 出链路数。 wpr(b) wprwpr 1/n n b wpr(b) 的计算需要迭代过程来调整近似到理 论真值， 表示节点的加权 PageRank 权重，所 有节点的 初始值初始化为 ， 为节点数。 在每个迭代中，每个节点 的 计算如下： wpr(b) = (1−d)wpr(a)+d ∑ a∈R(b) wpr(a)w in (a,b)w out (a,b) (4) 在每次迭代中，所有节点的 wpr 值都是基于式 (4) 减小的[13]。对于所有节点当满足以下的停止 准则时，迭代过程停止： wpr(b)iter−1 −wpr(b)iter wpr(b)iter ⩽ β (5) β β = 10−3 wpr p 其中，分数是前一次迭代与当前迭代之间的归一 化差值， 是一个预定义的停止阈值，这里设置 。最后当式 (5) 成立时，选择 最高的 节点作为地标点。 2 改进地标表示的自编码谱聚类算法 2.1 构造新的拉普拉斯矩阵 n p ≪ n p n 在文献 [14-15] 中，提出了基于地标点的谱聚 类算法来加速谱聚类，在给定 个数据点的数据 集的情况下，选择 个具有代表性的数据点 作为地标的特征点，将原始数据点表示为这些地 标的线性稀疏组合，然后利用基于地标的表示来 高效地计算数据的谱嵌入，并通过理论分析证明 其性能优于 Nystrüom 和快速谱聚类方法，有效地 利用稀疏表示矩阵逼近了整个图的相似度矩阵。 它表示选定的 个地标点与 个数据点之间的成 对相似性。 X = {x1, x2 · · · xn} ∈ R n×d X ≈ UZ U U xi xˆi 给定数据矩阵 ，它可以 近似为 。 每一列都可以看作捕捉数据 中较高层次特征的基向量。选定的地标点可以看 作是基向量。假设对于任何数据，已经有了地标 矩阵 。对于任意点 ，它的近似 计算为 xˆi = ∑p j=1 zjiuj (6) xi uj Z j Z r < p p U ∈ R d×p uj r zji Z U⟨i⟩ ∈ R d×r U xi r zji 根据稀疏编码策略，假设当 更接近 时， 矩阵 的第 个元素应该更大。为了强调这一假 设,创建 亲和稀疏矩阵的稀疏表示,通过选择 个最近的地标点,代替 个地标点 ( )， 例如，如果 不是 的最近的地标之一，则 的 值为 0，生成稀疏表示矩阵 。设 表示 的子矩阵，由 最近的 个地标点组成，然后 计算出每个 元素如下： zji = Φ ( xi ,uj ) ∑ j ′∈U⟨i⟩ Φ ( xi ,uj ) , i ∈ 1,2,· · · ,n, and, j ∈ U⟨i⟩ (7) Φ(·) σ Φ ( xi ,uj ) = exp( − xi−uj /2σ 2 ) σ σ σ 2 = σiσj ,∀Φ ( xi ,uj ) σi i Z ∈ R p×n W W = Zˆ T Zˆ Zˆ = D −1/2Z D = ∑ j Zji Z 其中， 是一个具有尺度参数 的高斯核函 数 ， 是最常用的高斯 核函数之一，其中， 控制着每个数据点的局部 邻域。根据核尺度参数 的自调整策略，在本文 所提算法中，设置 ，其中 是 的邻居点的平均距离，也是 的稀疏表 示中的非零元素。对于 亲和矩阵，认为 ，其中 是 度矩阵的归一 化 。 如果计算所有数据点的相似性矩阵并将其作 为堆叠式自动编码器的输入，对于大型数据集来 说空间消耗非常高。代替计算给定数据与所有其 他数据点的相似性，本文算法只考虑选择的地标 点与其他数据点之间的相似性。在这里重写了如 下拉普拉斯矩阵的形式： Lnew = SST (8) S Z D2 在这里使用 作为叠加自编码器的输入，从 前文可以知道归一化相似矩阵可以用稀疏表示矩 阵 ，为了进一步降低计算复杂度，在这里使用一 种简单的方法计算度矩阵 ，矩阵的主要对角线 元素一般计算如下: d2ii = ∑ i wi j = ∑ i zˆ T i zˆj (9) 对式 (11) 进行运算演化可以得到： d2ii = ∑n j=1 wi j = ∑n j=1 zˆ T i zˆj = zˆ T i ∑n j=1 zˆj= zˆ T i Zˆ s (10) Zˆ s p×1 k Zˆ k 其中， 是一个 的向量，第 个元素是 中 第 行元素的和。 D2= diag( Zˆ T Zˆ s ) (11) 在这里新的拉普拉斯矩阵的构造如下: Lnew = D −1/2 2 W D−1/2 2 = D −1/2 2 Zˆ T ZˆD −1/2 2 (12) S = D −1/2 2 Zˆ T (13) 最后，将相似度矩阵 S 输入到自动编码器中，最 后运行 k-means 聚类，从而得到聚类结果。 2.2 自编码器与聚类优化 xi yi mi 自动编码器是一种用于有效编码和降维的无 监督学习的人工神经网络。自动编码器的目的是 使原始输入 和新的嵌入表示 的重构输出 之间的重构损失最小化[16-19]。重构损失定义如下: Lr = ∑N i=1 l(xi ,g(f (xi ; θ1); θ2)) (14) 其中， {θ1, θ2} = {h1,b1,h2,b2} 是自动编码器的参数。 虽然用自编码器配合得到聚类结果，有效地 降低了计算复杂度，减小了空间复杂度。但是， 由于需要计算和保存所有数据点的相似关系，因 此内存消耗进一步增加。学习表示与聚类分离， ·304· 智 能 系 统 学 报 第 15 卷