词-文档矩阵谱共聚类的随机化SVD近似方法
摘要
本文提出了两种用于词-文档矩阵谱共聚类的随机化SVD近似方法,表明在多种设置下随机投影方法更为可靠,而基于采样的方法在更密集的矩阵上表现更佳。
arXiv:2609.19243v1 公告类型:新
摘要:谱共聚类是发现词-文档矩阵中潜在结构的有用工具,但其对奇异值分解(SVD)的依赖可能使标准方法在高维数据上变得昂贵。本文提出了两种用于二分文本数据归一化谱共聚类的随机近似方法,当文档和词聚类数量可能不同时。第一种方法通过随机投影使用随机化SVD,而第二种方法结合了部分SVD和逐元素随机采样。在真实世界和合成数据集上,两种方法相对于完整SVD基线都减少了运行时间,但它们的行为取决于矩阵稀疏性。在测试的设置中,随机投影方法是更可靠的近似,而基于采样的方法在更密集的矩阵上最有用,并且对已经稀疏的文本数据提供的益处有限。这些结果表明,用于谱共聚类的随机近似方法应根据数据的底层结构进行选择。
查看缓存全文
缓存时间: 2026/09/18 08:49
# 面向词项-文档矩阵谱协同聚类的随机化奇异值分解近似方法 来源:https://arxiv.org/html/2609.19243 Fateme Mazdarani、Carlos Toxtli 所属机构:克莱姆森大学计算学院,美国南卡罗来纳州克莱姆森市 [email protected] ###### 摘要 谱协同聚类是揭示词项-文档矩阵潜在结构的有效工具,但其对奇异值分解(SVD)的依赖使得标准方法在高维数据上计算代价高昂。本文针对文档聚类数与词项聚类数可能不同的二部文本数据归一化谱协同聚类问题,提出两种随机化近似方法:第一种方法通过随机投影实现随机化SVD,第二种方法结合部分SVD与逐元素随机采样。在真实和合成数据集上的实验表明,与完整SVD基线相比,两种方法均能降低运行时间,但其表现取决于矩阵稀疏性。随机投影方法在所有测试设置中表现出更可靠的近似效果,而基于采样的方法在较密集矩阵上效果最佳,在已经稀疏的文本数据上收益有限。结果表明,谱协同聚类的随机化近似方法选择应依据数据的内在结构决定。 ###### 索引词 谱协同聚类、文档聚类、随机化奇异值分解、可扩展聚类、文本挖掘 ## I 引言 现代数据挖掘与自然语言处理应用涉及日益庞大的高维文本集合。聚类通过将相似数据点分组来揭示潜在结构,广泛应用于文档的组织、检索与探索性分析[1]。然而,k-均值、模糊c-均值与期望最大化等标准单视图聚类方法独立于词汇结构对文档进行聚类。谱聚类[2]通过图拉普拉斯矩阵的特征向量对数据进行嵌入,克服了基于质心方法的某些局限性。由于其能捕获相似性图中的非凸结构,谱聚类在文档聚类中得到广泛应用。但特征分解在时间和内存消耗上可能代价高昂[3],这推动了面向文本数据的可扩展谱近似方法的发展。 术语-文档矩阵天然表示两类耦合实体:文档与词汇。仅对矩阵一侧聚类会忽略其相互依赖关系。因此,当目标是同时识别文档组及其特征词汇模式时,行-列联合聚类十分有用。谱协同聚类将术语-文档矩阵建模为二部图,并同时对文档和词项进行聚类[4]。该方法计算归一化矩阵的奇异向量,并对所得文档与词项嵌入应用k-均值算法,从而捕获文档组与词项组之间的关系,而非将它们视为独立的聚类问题。 原始二部谱公式采用共享分区结构,但许多实际术语-文档矩阵可能需要不同的文档聚类数与词项聚类数。相关谱双聚类方法(尤其在生物信息学领域)同样寻求行与列的同时分区,并能建模具有不同行/列聚类数的棋盘模式[5,6]。这些方法对结构化矩阵很有用,但其对奇异向量计算的依赖限制了其在高维文本矩阵上的直接应用。 主要计算瓶颈在于SVD步骤。对于n×m矩阵,当两个维度都很大时,精确SVD计算代价高昂。随机化SVD通过随机投影近似主导奇异子空间来降低此成本[7]。部分SVD方法仅计算主导奇异分量,尤其适用于稀疏术语-文档矩阵[8]。 受这些观察启发,我们研究归一化谱协同聚类流程中面向词项-文档矩阵的随机化与稀疏感知近似方法。目标并非引入新的协同聚类目标,而是探究当行与列聚类数不同时,不同SVD近似对运行时间与聚类质量的影响。主要贡献包括: (i) 针对具有不同文档/词项聚类数的非方阵词项-文档矩阵的归一化二部谱协同聚类流程; (ii) 在真实与合成矩阵上,对随机投影SVD与部分SVD采样变体与完整SVD基线进行的实证比较。 ## II 相关工作 协同聚类同时对数据矩阵的行和列进行划分,经典方法包括直接矩阵协同聚类、谱双聚类、二部谱图划分、信息论协同聚类、Bregman协同聚类与矩阵分解方法[9,5,6,4,10,11,12,13]。可扩展性仍是主要挑战[14]。我们的工作保持归一化谱公式,并研究SVD近似如何影响运行时间与聚类质量。 基于图的协同聚类将两类实体建模为二部图或异构图。相关方法包括文档-词项谱图模型[15]、半监督谱协同聚类[16]、结构化最优二部图学习[17]以及支持不同行/列聚类数的快速灵活二部图划分[18]。近期可扩展方法使用锚点图或归一化二部割来降低图构建或特征求解器成本[19,20]。这些工作通常修改图模型、目标或优化流程,而我们保留标准归一化谱协同聚类流程,并在其框架内评估近似选择。 随机化与稀疏谱近似与我们的方法密切相关。随机化SVD使用随机投影、过采样和幂迭代近似主导奇异子空间[7],随机化谱方法已在大型无向网络与有向网络协同聚类中得到研究[21,22]。稀疏SVD方法对文本数据很重要,因为术语-文档矩阵具有高维稀疏性;截断SVD长期用于潜在语义分析[8],而Lanczos类算法与IRLBA等迭代方法的计算成本与非零元素数量相关[23]。矩阵采样与稀疏化也已用于随机低秩近似研究[24,25]。我们将这些近似工具与归一化谱协同聚类结合,应用于非方阵词项-文档矩阵,并探究采样在何种情况下有益或会消除稀疏文本数据中的有效信号。 ## III 问题陈述 ### III-A 词项-文档图建模 沿用先前工作[4,15],我们将语料库建模为无向二部图G=(D∪W,E),其中D={d₁,...,dₙ}为文档集,W={w₁,...,wₘ}为词汇表。边(dᵢ,wⱼ)∈E表示词项wⱼ出现在文档dᵢ中;文档间或词项间无连边。边权重编码词项-文档相关性。我们采用TF-IDF[26],其中词频衡量局部词频,逆文档频率降低全局常见词的权重: TF-IDF(wⱼ,dᵢ)=TF(wⱼ,dᵢ)×IDF(wⱼ) (1) 其中TF(wⱼ,dᵢ)为wⱼ在dᵢ中的频率,IDF(wⱼ)=log(n/(1+nⱼ)) (2) n为文档总数,nⱼ为包含wⱼ的文档数。加权邻接矩阵A∈ℝⁿˣᵐ定义为: Aᵢⱼ = { Eᵢⱼ 若词项wⱼ出现在文档dᵢ中 { 0 其他情况 (3) 其中Eᵢⱼ为对应TF-IDF权重。 ### III-B 图划分问题 协同聚类可视为对二部顶点集V=D∪W的划分。对于两个子集,图割定义为: min_{V₁,V₂} cut(V₁,V₂) = min_{V₁,V₂} Σ_{vᵢ∈V₁,vⱼ∈V₂} wᵢⱼ (4) 对于k-way划分,变为: cut(V₁,...,Vₖ) = Σ_{i<j} Σ_{v∈Vᵢ,w∈Vⱼ} w_{vw} (5) 归一化割定义为: Ncut(V₁,...,Vₖ) = Σ_{i<j} cut(Vᵢ,Vⱼ)/(vol(Vᵢ)+vol(Vⱼ)) (6) 其中vol(V)=Σ_{v∈V} d(v),d(v)为顶点度。最小化归一化割等价于对归一化拉普拉斯矩阵Lₙ=D⁻¹/²AD⁻¹/²进行特征分解,其中D为度矩阵[2]。 ## IV 方法 ### IV-A 归一化二部谱协同聚类(SCC) 给定词项-文档矩阵A∈ℝⁿˣᵐ,我们首先构建归一化矩阵: Aₙ = Dᵣ⁻¹/² A Dc⁻¹/² (7) 其中Dᵣ=diag(A1ₘ),Dc=diag(1ₙᵀA)。计算Aₙ的SVD:Aₙ=UΣVᵀ,取前k个奇异向量构造嵌入矩阵Uₖ∈ℝⁿˣᵏ和Vₖ∈ℝᵐˣᵏ,然后分别对Uₖ和Vₖ的行进行k-均值聚类得到文档与词项标签。标准SCC使用k=⌈log₂(max(kᵣ,kc))⌉+1,其中kᵣ和kc为预期聚类数。该方法需完整SVD,计算成本随矩阵规模增长而显著上升。 ### IV-B 基于随机投影的谱协同聚类(SCCRP) 为降低SVD成本,我们采用随机投影SVD[7]。该方法首先生成随机高斯矩阵Ω∈ℝᵐˣᵏ,计算Y=(AₙAₙᵀ)ᵍAₙΩ,再通过QR分解得到正交基Q,形成更小的矩阵B=QᵀAₙ,计算B的SVD后映射回原始空间。其关键优势在于避免显式计算大型矩阵乘积。 Wedin扰动界表明:若Aₙ的奇异值间隙γ>0,近似误差ε产生的子空间误差量级为O(ε/γ)。因此,当近似误差相对于奇异值间隙较小且嵌入簇充分分离时,k-均值分配结果应保持稳定。 **算法2 随机投影SVD** 输入:A∈ℝⁿˣᵐ,目标奇异向量数k,幂迭代次数q 输出:U,Σ,V(其中UΣVᵀ为A的秩k近似) 1. 生成高斯测试矩阵Ω₁∼𝒩(0,1)ᵐˣ²ᵏ和Ω₂∼𝒩(0,1)ⁿˣ²ᵏ 2. 交替与A及Aᵀ相乘构造Y₁=(AAᵀ)ᵍAΩ₁和Y₂=(AᵀA)ᵍAᵀΩ₂ 3. 构造矩阵Q₁和Q₂,其列分别为Y₁和Y₂值域的正交基 4. 构建较小矩阵B=Q₁ᵀAQ₂ 5. 计算SVD B=ŨΣ̃Ṽᵀ 6. 保留Ũₖ=Ũ(:,1:k), Ṽₖ=Ṽ(:,1:k), Σ=Σ̃(1:k,1:k) 7. 令U=Q₁Ũₖ, V=Q₂Ṽₖ **算法3 基于随机投影SVD的谱协同聚类** 输入:A∈ℝⁿˣᵐ,文档聚类数kᵣ,词项聚类数kc 输出:预测的行列标签:row_labels, col_labels 1. 计算对角矩阵Dᵣ和Dc,其中Dᵣ(i,i)=ΣⱼA(i,j),Dc(i,i)=ΣⱼA(j,i) 2. 计算归一化矩阵Aₙ=Dᵣ⁻¹/²ADc⁻¹/² 3. 设置lr=⌈log₂kᵣ⌉, lc=⌈log₂kc⌉, k=max(lr,lc)+1 4. 使用算法2的随机投影SVD方法近似计算Aₙ=UΣVᵀ 5. 令Uₖ=Dᵣ⁻¹/²U(:,2:lr+1), Vₖ=Dc⁻¹/²V(:,2:lc+1) 6. 分别对Uₖ和Vₖ的行执行k-均值得到row_labels和col_labels 谱协同聚类的主要成本来自SVD计算,SCCRP将其替换为基于随机投影的近似。其主要成本是幂迭代中的矩阵乘积序列(AAᵀ)ᵍAΩ₁和(AᵀA)ᵍAᵀΩ₂。对于稀疏矩阵A,这些乘积的计算时间为O((2q+1)‖A‖₀(k+max(m,n)))。剩余SVD步骤成本低廉,因其作用于较小的投影矩阵。随机化SVD也适用于并行化[7],使该方法适用于大规模数据。 ### IV-C 基于部分SVD的谱协同聚类(SCCP) #### IV-C1 部分SVD 对于稀疏数据,谱协同聚类可通过仅提取前k≪min(m,n)个奇异值与向量来避免完整SVD:A≈UₖΣₖVₖᵀ。其中Uₖ和Vₖ包含主导左右奇异向量,Σₖ包含对应奇异值。该近似捕获数据主要结构同时降低噪声与冗余。 部分SVD可使用Lanczos双对角化及隐式重启Lanczos双对角化算法(IRLBA)[23]等迭代方法高效计算。这些方法构建低维Krylov子空间,通过迭代近似主导奇异分量并控制内存使用。其计算成本约为O(k·nnz(A)·t),其中nnz(A)为非零元数量,t为收敛所需迭代次数。由于k和t通常较小,运行时间近似与非零元数量呈线性关系。 #### IV-C2 随机采样 由于部分SVD成本依赖于nnz(A),我们通过逐元素随机采样降低其成本。与行/列采样方法[24,25]不同,该策略以概率p独立保留每个非零元,生成均匀稀疏矩阵Ars: Arsᵢⱼ = { Aᵢⱼ 以概率p { 0 以概率1-p (8) **算法4 基于部分SVD与随机采样的谱协同聚类** 输入:A∈ℝⁿˣᵐ,文档聚类数kᵣ,词项聚类数kc,采样概率p 输出:预测的行列标签:row_labels, col_labels 1. 使用公式(8)构建稀疏化矩阵Ars 2. 根据行和计算对角矩阵Dr和Dc 3. 构建归一化矩阵Arsn=Dr⁻¹/²ArsDc⁻¹/² 4. 计算Arsn的部分SVD:Arsn≈UₖΣₖVₖᵀ 5. 对Uₖ和Vₖ的行执行k-均值得到row_labels和col_labels SCCP通过采样降低非零元数量以加速部分SVD。但采样会以概率1-p移除有效非零元,可能破坏文本数据中的重要共现信息。因此,该方法在密集矩阵上更有效,而在稀疏文本数据上可能降低聚类质量。 ## V 实验设置 ### V-A 数据集 我们使用20-Newsgroups(20NG)、Reuters-21578和TREC AP三个真实数据集,以及生成的合成数据集。合成数据基于文档-词项共现的块结构生成,文档与词项分别划分为kᵢ和kj个聚类。 ### V-B 评估指标 使用归一化互信息(NMI)和调整互信息(AMI)评估聚类质量,使用墙钟时间评估计算效率。 ### V-C 基线方法 比较以下方法: 1. 完整SVD谱协同聚类(SCC) 2. 随机投影SVD谱协同聚类(SCCRP) 3. 部分SVD谱协同聚类(SCCP) 4. 随机投影SVD部分SVD组合(SCCRP-SCCP) ## VI 结果与分析 ### VI-A 运行时间比较 在所有数据集上,随机化方法均显著快于完整SVD。SCCRP的加速比随矩阵规模增大而提高,在20NG数据集上达到3.2倍加速。SCCP在密集合成数据上表现最佳,但在稀疏文本数据上优势有限。 ### VI-B 聚类质量比较 SCCRP在所有真实数据集上与SCC质量相当(NMI差异<0.02),而SCCP在稀疏数据上质量略有下降(NMI下降0.05-0.1)。这验证了Wedin扰动界的预测:当近似误差受控时,聚类分配保持稳定。 ### VI-C 参数敏感性分析 - **幂迭代次数q**:SCCRP对q不敏感,q=1即可获得稳定结果 - **采样概率p**:SCCP需p≥0.5以保持聚类质量,而SCCRP无需采样参数 - **稀疏性影响**:在稀疏数据(密度<0.01)上,SCCRP始终优于SCCP ## VII 结论 本文提出两种用于谱协同聚类的随机化SVD近似方法。随机投影方法(SCCRP)在各类数据上表现稳健,尤其适合稀疏文本数据。部分SVD采样方法(SCCP)在密集矩阵上高效,但在稀疏文本数据上收益有限。实验表明,随机化近似方法的选择应依据数据结构和稀疏性决定。未来工作将探索自适应近似策略与在线流处理场景。 ## 致谢 感谢克莱姆森大学计算学院提供的计算资源。本研究部分受美国国家科学基金会资助(批准号:XXXXXXX)。
相似文章
基于半张量积的多项目随机化T-SVD及其视觉应用
本文提出了一种新的张量半张量积,并开发了一种多项目随机化张量奇异值分解(MSTP-SVD),以提高视觉数据处理任务中的低秩近似精度和计算效率。
截断SVD
本文解释了截断SVD及其与主成分分析的关系,展示了如何通过使用更少的奇异值重建图像来近似原图。它以月球图像为例说明重建过程。
基于有界秩一投影的Grassmannian核近似随机特征
本文介绍了用于格拉斯曼流形上可扩展核机器的随机特征映射,利用有界秩一投影来近似旋转不变的Grassmannian核,并降低计算和内存成本。
具有聚类结构的向量的随机复杂性
本文提出一种递归公式,用于使用 Normalized Maximum Likelihood 模型高效计算具有聚类结构的向量的随机复杂性,将时间复杂度从多项式降低到线性。
双值对称循环矩阵:在深度学习中的应用
本文提出双值对称循环矩阵(TVSCM),一种极度稀疏的架构,每层仅使用两个权重,即可在MNIST和MIT-BIH心律失常数据集上实现超过80倍的参数压缩,同时保持可比的精度,使其成为边缘和微型机器学习平台的理想选择。