第2期 储德润，等：加权PageRank改进地标表示的自编码谱聚类算法 ·305· 嵌入表示是不可靠的，对聚类有负面影响。为了 2.3所提算法流程 将聚类和学习表示联合更新，并且能够获得更强 加权PageRank改进地标表示的自编码谱聚 大的表示和更精确的聚类结果，将这两个过程集 类算法步骤： 成到一个具有基于KL散度的聚类损失函数的单 输入数据集X,目标聚类数k,地标数目p 一框架中，并迭代地优化了自动编码器和聚类中 最近邻地标数目r,停止阈值B,迭代数目t,停止 心的参数。聚类损失被定义为分布在P和Q之 阈值h。 间的KL散度，其中Q是由-SNE测量的软标签 输出实际聚类数目y,聚类损失L,重构损 的分布，P是由Q导出的目标分布。聚类损失可 失Lo 以用来同时更新堆叠式自动编码器和聚类中心的 1)根据式(2)(4)计算wpr(b)的值，迭代计算 参数，如式(15)所示： wpr直到满足式(S),根据最高的wpr值选择p个 L=KL(PIO)=∑∑P,log (15) 地标点。 9 2)通过式(7)计算稀疏表示矩阵Z,所选地标 其中，9附是由t-SNE测量的嵌入表示y和聚类中 点p和具有r个最近邻地标点的矩阵U。 心c,的相似性。 （+b-c) 3)通过式(12)计算新的拉普拉斯矩阵Lw。 (16) 4)使用D22r作为自动编码器的输人。接 ∑1+-c) 着对叠加式自动编码器进行训练，得到嵌入表 P是由q确定的目标分布： 示h。 呢∑9 5)在最后一个隐藏层的嵌入表示：上进行k means聚类，以初始化聚类中心cj。根据式(22)、 p时= (17) ∑∑w (23)更新自动编码器的参数和聚类中心c0 2.4算法复杂度分析 因为，P是由9确定的目标分布，所以L的 假设从n个数据点中选择p个地标，则所提 最小化可以看作是自我训练的一种形式。重构损 算法采用加权PageRank选择地标点，该步骤的时 失保证了嵌入空间能够保持数据的局部结构，因 间复杂度为O(pm),其中t为迭代次数。为了构 此将重构损失和聚类损失作为优化参数的目标 造新的相似矩阵，只需根据方程计算稀疏表示矩 函数。 阵Z,这一步的时间复杂度为O(pm)。堆叠式自动 L=L+AL (18) 其中，1(（≥0）是一个控制嵌入空间失真程度的因子。 编码器和优化算法的时间复杂度为O(nD2+ndk), 利用最小批量随机梯度下降可以得到自动编 k是簇数，D是隐藏层的最大单元数，d是嵌入层 码器的聚类中心和参数的优化，计算出L关于嵌 的维数。通常k≤d≤D,所以时间复杂度可写为 入表示和聚类中心c的梯度。 O(tpn+pm+nD)。基于地标点的谱聚类算法阿的时 张-221+b-c'p-46-6 间复杂度为O(tpm+pm+p2n+p),又p≤n,则p3≤ (19) dy p2n,故p2n+p3≈p2n,所以基于地标点谱聚类算法 1 a业-221+-c0'(a-p6-c） 的时间复杂度可写为O(tpn+pm+p2n),其中p与 (20) oc: 1 D的取值相近且远小于n,因此，可推断本文方法 L/y:可以传递到叠加的自动编码器，并用 与基于地标点谱聚类算法时间复杂度相当，但由 于反向传播以计算参数aLe/aM1、Le/aM2的梯 于算法改进中通过采样少数几个数据，点来推断数 度。编码器权重的更新公式如下： 据集的全局特征，空间复杂度有所降低。 M=M-2(0+%) (21) 3实验与结果分析 译码器的权重公式更新如下： M=M-2胎） 3.1实验环境及性能指标 (22) 在本文算法实验中，选取了几个数据量较大 聚类中心c的更新公式如下： 的数据集进行实验，它们分别为手写数字数据集 99”此 (23) USPS、Pendigits、MNIST、英文字母表数据集Let- m台ac terRec和UCI数据库中的数据集CoverType,表I 式中：m是小批量的样本数；刀是学习速率。 给出了数据集的详细特征。本文算法实验是在PytP Q Q P Q 嵌入表示是不可靠的，对聚类有负面影响。为了 将聚类和学习表示联合更新，并且能够获得更强 大的表示和更精确的聚类结果，将这两个过程集 成到一个具有基于 KL 散度的聚类损失函数的单 一框架中，并迭代地优化了自动编码器和聚类中 心的参数。聚类损失被定义为分布在 和 之 间的 KL 散度，其中 是由 t-SNE 测量的软标签 的分布， 是由 导出的目标分布。聚类损失可 以用来同时更新堆叠式自动编码器和聚类中心的 参数，如式（15）所示： Lc = KL(P∥Q) = ∑ i ∑ j pi j log pi j qi j (15) qi j yi cj 其中， 是由 t-SNE 测量的嵌入表示 和聚类中 心 的相似性。 qi j = ( 1+ yi −cj 2 )−1 ∑ j ( 1+ yi −cj 2 )−1 (16) pi j 是由 qi j 确定的目标分布： pi j = q 2 i j/ ∑ i qi j ∑ j   q 2 i j/ ∑ i qi j   (17) 因为， pi j 是由 qi j 确定的目标分布，所以 Lc 的 最小化可以看作是自我训练的一种形式。重构损 失保证了嵌入空间能够保持数据的局部结构，因 此将重构损失和聚类损失作为优化参数的目标 函数。 L = Lc +λLr (18) 其中， λ (λ ⩾ 0) 是一个控制嵌入空间失真程度的因子。 Lc yi cj 利用最小批量随机梯度下降可以得到自动编 码器的聚类中心和参数的优化，计算出 关于嵌 入表示 和聚类中心 的梯度。 ∂Lc ∂yi = 2 ∑k j=1 ( 1+ yi −cj 2 )−1 ( pi j −qi j) (yi −cj ) (19) ∂Lc ∂cj = 2 ∑k i=1 ( 1+ yi −cj 2 )−1 ( qi j − pi j) (yi −cj ) (20) ∂Lc/∂yi ∂Lc/∂M1 ∂Lc/∂M2 可以传递到叠加的自动编码器，并用 于反向传播以计算参数 、 的梯 度。编码器权重的更新公式如下： M1 = M1 − η m ∑m i=1 ( ∂Lc ∂M1 +λ ∂Lr ∂M1 ) (21) 译码器的权重公式更新如下： M2 = M2 − η m ∑m i=1 ( ∂Lr ∂M2 ) (22) 聚类中心 cj 的更新公式如下： cj = cj − η m ∑m i=1 ∂Lc ∂cj (23) 式中：m 是小批量的样本数； η 是学习速率。 2.3 所提算法流程 加权 PageRank 改进地标表示的自编码谱聚 类算法步骤： X k p r β t h 输入 数据集 ，目标聚类数 ，地标数目 ， 最近邻地标数目 ，停止阈值 ，迭代数目 ，停止 阈值 。 y Lc Lr 输出 实际聚类数目 ，聚类损失 ，重构损 失 。 wpr(b) wpr wpr p 1) 根据式 (2)~(4) 计算 的值，迭代计算 直到满足式 (5)，根据最高的 值选择 个 地标点。 Z p r U 2) 通过式 (7) 计算稀疏表示矩阵 ，所选地标 点 和具有 个最近邻地标点的矩阵 。 3) 通过式 (12) 计算新的拉普拉斯矩阵 Lnew。 D −1/2 2 Zˆ T hi 4) 使用 作为自动编码器的输入。接 着对叠加式自动编码器进行训练，得到嵌入表 示 。 hi cj cj 5) 在最后一个隐藏层的嵌入表示 上进行 k￾means 聚类，以初始化聚类中心 。根据式 (22)、 (23) 更新自动编码器的参数和聚类中心 。 2.4 算法复杂度分析 n p O(tpn) t Z O(pn) O ( nD2 +ndk) k D d k ⩽ d ⩽ D O ( tpn+ pn+nD2 ) O ( tpn+ pn+ p 2n+ p 3 ) p ≪ n p 3 ≪ p 2n p 2n+ p 3 ≈ p 2n O ( tpn+ pn+ p 2n ) p D n 假设从 个数据点中选择 个地标，则所提 算法采用加权 PageRank 选择地标点，该步骤的时 间复杂度为 ，其中 为迭代次数。为了构 造新的相似矩阵，只需根据方程计算稀疏表示矩 阵 ,这一步的时间复杂度为 。堆叠式自动 编码器和优化算法的时间复杂度为 ， 是簇数， 是隐藏层的最大单元数， 是嵌入层 的维数。通常 ，所以时间复杂度可写为 。基于地标点的谱聚类算法[15] 的时 间复杂度为 ，又 ，则 ，故 ，所以基于地标点谱聚类算法 的时间复杂度可写为 ，其中 与 的取值相近且远小于 ，因此，可推断本文方法 与基于地标点谱聚类算法时间复杂度相当，但由 于算法改进中通过采样少数几个数据点来推断数 据集的全局特征，空间复杂度有所降低。 3 实验与结果分析 3.1 实验环境及性能指标 在本文算法实验中，选取了几个数据量较大 的数据集进行实验，它们分别为手写数字数据集 USPS、Pendigits、MNIST、英文字母表数据集 Let￾terRec 和 UCI 数据库中的数据集 CoverType，表 1 给出了数据集的详细特征。本文算法实验是在 Pyt- 第 2 期 储德润，等：加权 PageRank 改进地标表示的自编码谱聚类算法 ·305·