面向故障短文本的改进图节点嵌入与聚类方法
2024-01-13邱竞雄孙林夫
邱竞雄,孙林夫+,韩 敏
(1.西南交通大学 计算机与人工智能学院,四川 成都 610031;2.四川省制造业产业链协同与信息化支撑技术重点实验室,四川 成都 610031)
0 引言
随着信息技术的普及和发展,大数据分析技术在汽车行业等传统制造业中正发挥越来越重要的作用。汽车产业中,车辆及其零部件的供销存过程中会产生数量庞大的业务数据,对其进行有效的价值挖掘有助于推动汽车服务行业数据化、智能化[1]。针对汽车维修服务过程中产生的大量记录汽车零部件故障现象、故障原因等的中文短文本数据进行分类,是实现故障诊断、案例推荐等服务应用的必要工作之一[2-5]。
文本数据分类方法通常可分为有监督分类及无监督聚类,有监督分类一般具有固定的分类体系,无法挖掘文本数据中的潜在信息。聚类方法可通过数据特征划分数据形成不同的簇类,获取数据潜在信息。现有文本聚类方法多是针对独立的句子级短文本本身[6-9],忽略了不同文本句子间的词汇关联,缺少对各条文本中不同特征实体的聚类,无法获取各类实体的潜在聚类标签。针对该问题,部分学者将独立的短文本转化为文档级的整合数据,再进行文档级的聚类研究[10-11],但如此又会失去各个实体的句子级关系特征。本文通过将句子级文本数据转换为图结构,并在图结构基础上进行实体特征表示及聚类,以此同时保留实体的句子、文档级特征。
另一方面,在真实的汽车故障数据中,有的故障件实体对应的解决方案实体有数十种,有的只有数种甚至一种。在数据对应的图结构中,该现象表现为图节点度值(与该节点直接相连的节点数量)大小不一,度值大的节点会产生较为强烈的噪音,干扰度值小的节点与其它节点建立关联,进而影响节点全局结构特征的建立。
针对上述问题,本文提出一种面向故障短文本的改进图节点嵌入与聚类方法(improved Graph Node Embedding and Clustering method for Fault Short Text, GNEC_FST),改进了已有的图节点随机游走方法,用以体现度值差异对节点结构特征的影响,通过将节点的结构特征与邻域关系特征融合形成新的节点表示向量,并基于该节点表示向量进行聚类。本文主要贡献包括4个方面:
(1)提出面向故障短文本的图节点嵌入与聚类方法,在图结构度值差异较大的数据集中,该方法可获取更加有效的实体节点聚类标签。
(2)创新区分同一窗口下不同距离的词汇间关联的权重计算方法;针对所构建的图结构具有度值分布较分散、度值大节点噪音大的问题,设计了度值差异影响参数用于改进节点转移概率计算方法,从而有效获取度值差异较大节点间的关联特征;同时,本文将所获取的节点结构嵌入向量与关系特征向量进行融合,从而在嵌入向量中表达具有相似邻居节点的同类节点之间的相似性。
(3)加入备选节点数改进局部密度计算方法,针对不同的数据集特点及规模,可按需求选取邻域节点更加紧密或稀疏的节点作为初始聚类中心,缓解了截断距离的敏感性,提高了方法的适应性。
(4)利用公开数据集及真实数据集对所提方法进行参数分析和性能评估,结果表明该方法可获取更加精准有效的节点聚类结果。
1 相关工作
将短文本集转化为图结构,通过图表示方法获取词汇及关系的嵌入表示向量,再对嵌入表示向量进行聚类,这个过程中本文主要研究图嵌入方法、局部密度计算方法两个方面的相关工作内容。
(1)基于随机游走的图嵌入方法
图嵌入(Graph Embedding, GE)方法的目标是将图的组成单元映射到低维特征向量,并尝试保留节点之间的连接强度,用向量的方式表示图结构及其特征,为聚类等下游问题提供特征数据。现有的图嵌入方法可分为基于随机游走[12]、矩阵分解[13-14]、深度学习[15-16]等方面的方法。其中,基于随机游走的方法优化节点嵌入向量的方式是使随机游走中共现的节点具有更相似的表示,其方法简单有效,是获取关系型数据图结构嵌入向量的可靠选择。现有的随机游走方法大多数是基于Deepwalk[12]进行改进的,主要可以按照改进随机游走采样方法、改变所保留的邻近度进行区分。
改进随机游走采样方法的现有研究中,Constrained DeepWalk[17]采用了边权重采样的方法,通过非概率的方式将节点间边权重的特征直接融入到嵌入向量中,其方法在应对边权重差异大的图结构中有较好效果。Node2vec[18]方法中设计了搜索偏差参数,通过调节该参数,可以使嵌入向量倾向于表达不同的特性,在广度优先和深度优先图搜索之间进行权衡,但是其方法难以体现不同度值分布的图结构中的节点差异。Planetoid方法[19]则按标签和结构对节点对进行采样,且保留了标签的邻近度值,是一种半监督方法,用于应对带标签的图节点,不适用于无监督图节点。NBNE方法[20]中对目标节点的直接邻居节点进行采样,该文献是针对超大型图结构进行的改进,其方法在图中节点数大于1 000时表现好于Deepwalk和Node2vec。WANG等[21]提出的方法使用了元路径指导的随机游走进行采样,且首次利用了节点在双曲空间中的距离作为相似度度量,该方法是当前研究中基于随机游走的图嵌入方法中表现最好的之一。
改变所保留的邻近度的方法中,ZHANG等的[22]方法通过保留节点的文本、图像描述性标签的邻近度来获取更加精确的节点特征嵌入向量,其方法也是半监督方法,适用于有充足数据基础的图嵌入场景。GenVector方法[23]通过保留同一类别实体两两之间的邻近度来强化同类实体之间的关联,在一定程度上缓解游走对同类型实体间相似度的削弱,其方法在多模态数据场景中适用性更高。ProxEmbed方法[24]中则先将各节点按照相似度评分进行排名,然后基于此构建邻近度特征融入到节点的邻近度矩阵中。DeepCas[25]中基于信息流预测方面的技术构建了基于马尔可夫链的随机游走策略,并将由此策略获取的信息级联序列也加入到邻近度的计算中,其获得的嵌入向量中包含了时效性特征,可用于涉及时效性的图结构数据嵌入场景中。
随机游走直接获取的表示向量需要进行降维处理,该过程一般采用深度学习方法。当前研究中,多数方法采用的是SkipGram加分层softmax的方式[12,22-23],也有部分研究采用SkipGram加负采样[18-19]、LSTM[24]或GRU[25]等方法,其区别在于,基于SkipGram的方法只能进行嵌入单个节点,而基于LSTM或GRU的方法可以嵌入句子级的节点集或信息级的路径节点集。
(2)局部密度计算方法
局部密度是基于密度的聚类方法中的概念[26],局部密度计算是基于密度的聚类算法中一个关键步骤[27],为有效提高处理交叉数据集和密度不均数据集的聚类精度,很多方法都考虑了数据集分布的局部信息以消除对截断距离的依赖。现有研究可按照针对参数敏感性、不同模态数据、数据密度特性等方面进行分类。
在针对参数敏感性方面,ADPC_KNN算法[28]能更大地扩展核心对象与边界对象的密度差异,其算法只需一个参数,且相较一般DPC算法更加健壮(Robustness)。STClu算法[29]中,用基于密度指标的外部统计测试来识别簇中心,降低了参数的敏感性。在针对不同模态数据上,SEYEDI等[30]提出一种DPC-DLP算法,利用K邻近重新定义局部密度的计算方法,该方法在处理图像、基因方面的较高维数据时具有更好的效果。在针对数据密度特性方面,DPC-KNN算法[31]倾向于处理密度不均匀数据集,FKNN-DPC算法[32]倾向于处理任意形状或规模的数据集,SNN-DPC算法[33]则倾向于处理多尺度、交叉缠绕和变化密度的数据集。
2 面向故障短文本的改进图节点嵌入与聚类方法
面向故障短文本的图节点嵌入与聚类方法基本流程主要包括4个步骤,如图1所示。
①基于权重计算方法构建图结构,用以表示短文本中的实体、行为及实体行为间的关系;②通过改进的随机游走方法获取图中节点表示序列,训练该表示序列获取节点结构特征;③将所得的节点结构特征与节点关系特征融合;④对融合所得的节点表示向量集计算局部密度并选取初始聚类中心进行聚类。
2.1 区分同一窗口下不同距离的词汇间关联的权重计算
基于短文本集D,采用滑动窗口方法构建可拓展的带权无向图,窗口宽度width的取值取决于短文本的平均长度,图结构G=(V,E,W),其中V={vi|i=1,2,…,n}表示节点集;E={eij|vi∈V,vj∈V,i≠j}表示边集;W={wij|eij∈E}表示每条边上对应的权重值集合。
传统的方法[34]中,权重的取值一般是文本词汇的“同窗”次数,如某文档中,一定width下,“发动机”与“冒烟”两个词汇在同一窗口内出现的次数为5,则这两个节点间的边上的权重为5。但在这种方法下,一定窗口范围内所有词与当前窗口中心词的关联度都一样,没有合理体现词汇之间的距离。为了区分同一窗口下的词汇关联度,同时保证上下文相关性,本文中设计的权重计算方法为:
(1)
式中:x为当前窗口下目标词与中心词的距离;u为设定的滑动窗口宽度;t为文档中短文本句子条数;woij为传统方法计算的权重值,
(2)
各条文本中,两个相同词汇间的距离可能不同,式(1)可以表达出这种不同,然后累加各条文本中相同词汇间的权重,最终形成文档级的词汇间(边)权重。
2.2 面向度值差异的节点结构特征获取
2.2.1 随机游走
随机游走是一种通过定义在节点之间移动的方法,从而形成游走路线,再通过路线确定嵌入向量的图嵌入方法。随机游走的概率定义如式(3)所示,使用ci表示游走过程中第i个节点,初始节点co=u,则由节点ci-1转移到节点ci的概率计算方式如下:
(3)
式中:πv,x表示节点v和x之间的非规范转移概率;z表示归一化常数。
通过改变非规范转移概率πv,x的定义,可以构建出不同的游走方法,从而展现不同的图结构特性。Node2vec[17]中提出了搜索偏差α这一参数用于确定非规范转移概率πv,x,
πv,x=αpq(t,x)·wvx。
(4)
式中:wvx表示边evx上的权重,由式(1)确定;搜索偏差αpq(t,x)由式(5)确定:
(5)
式中:dtx表示节点t到节点x的最短距离,此处的节点t表示游走路线上当前所在节点v的前一个节点,而节点x表示与当前节点v直接相连的节点,其数量为节点v的度数。因此,dtx取值范围为{0,1,2}。
参数p控制游走过程中回到上一节点的可能性,值越小,游走回上一节点的可能性越高。参数q控制游走趋向于“远离”当前节点的可能性,当q<1时,表示趋向于“远离”;当q>1时,表示游走趋向于当前节点附近。参数p、q的作用,本质上是根据当前节点与周围节点之间的距离调整这些节点之间边上的权重。
2.2.2 面向度值差异的搜索偏差改进
故障数据图结构中节点度值差异较大,度值大的节点会产生严重的噪音干扰度值小的节点与其它节点建立关联。为了改进非规范转移概率对边权重的依赖性,进而改善图中度值大的节点噪音大的问题,本文改进了搜索偏差的计算方法,如式(6)所示。
(6)
利用式(6),从当前节点v转移到目标节点x的概率可基于当前节点及目标节点的度值、度值差异影响参数τ进行调整。其中dgv和dgx分别表示当前节点和目标节点的度值,当dgv>dgx时,该式可提高转移到目标节点的概率,反之则会降低该概率。而参数τ用于调整度值差异对转移概率的影响程度,τ的取值根据整个图结构的度值分布情况确定。当τ取值较小时,所构建的游走路线倾向于在度值较高的节点周围;当τ取值较大时,所构建的游走路线倾向于前往度值较低的节点附近。基于图中所有n个节点的度值(dg1,dg2,…,dgn),当前图的度值分布情况表达式如式(7)所示。
(7)
基于上述方法对每个节点形成游走路线,可以得到图结构下各节点的表示序列,但当前节点表示向量为独热向量的形式,其维度n为全图节点个数,维度太高且训练速度极慢。考虑到进行的是节点的嵌入,本文采用SkipGram方法对所有节点表示向量进行训练降维,训练过程中采用负采样方法进行样本的权重更新,负采样方法因只更新部分边权重,可大幅提高训练速度。
2.3 节点结构特征与关系特征的融合
在2.2节获取各个节点的结构特征的过程中,将节点之间的关系以权重的方式融入到了图的边中,但是这种方式会在强化直接相连节点之间关联的同时削弱同类型的实体节点之间的相似性表示,如4个实体节点“发动机”、“喷油器”、“冒烟”、“噪音”中,前两者分别与后两者直接相连,他们的关联会被强化,但实际上前两个实体都是一类故障件实体,他们之间的相似性不应被削弱。本文通过节点关系特征的相似性来表示具有相似邻居节点的同类节点之间的相似性,因此将结构特征与关系特征进行融合。
本文采用邻接矩阵作为关系特征矩阵,但邻接矩阵是n×n的矩阵,而节点结构特征矩阵是n×d,因此将节点特征与关系特征的融合过程分为映射与融合两个步骤。
(1)映射 第一步是将关系特征向量空间映射到结构特征向量空间,这样可以避免不同空间融合带来的误差,这一步中,对以下3种方法进行了比较:
1)比例函数:直接采用简单的比例函数进行映射,fmap=A·x。
2)线性函数:映射函数是线性函数fmap=A·x+b。
3)多层感知器MLP:映射函数定义为一个多层感知器,其激活函数是ReLU。
用于训练映射函数的损失函数为:
(8)
采用梯度下降法进行求解,其中:n表示节点个数;θ表示映射函数的参数:ai表示节点vi的关系特征向量;xi表示节点vi的结构特征向量。
处理阶段主要是对以上3个阶段进行总结和分析,同时也贯彻于前3个阶段。通过科室带教组长对带教老师和实习同学的定期检查和考核,对检查的结果进行处理,对带教过程中做的好的方面进行肯定并标注化,以指导日后的带教工作;对带教过程中遇到的问题及时进行分析,组织带教老师、实习同学共同进行讨论,寻找解决方案,并在下一个PDCA循环中进行改进。
基于上述方法,获得了新的节点表示向量yi作为聚类算法的输入。
2.4 加入备选节点个数的局部密度计算方法
获取各节点的嵌入向量之后,将进行初始聚类中心的选取。考虑到故障短文本数据中的关键词特性,由该类短文本构建的嵌入向量节点的可能性分布情况如图2所示,两种分布情况中,截距范围内节点个数相同,但节点主要分布情况不同,可能导致零部件关键词与故障现象关键词等各自形成不同簇,难以达到全局聚类目标,因此其指标结果应有所区分。针对该问题,采用下述方法改进局部密度的计算。
计算获取当前图中各节点距离矩阵H后,为各个节点计算其局部密度指标ρi和相对最小距离指标γi,其中
(9)
式中:dij表示节点i,j之间的欧式距离;dc表示截断距离,考虑到本文所构建的图中节点个数,dc取值为所有dij由小到大排列时占4%位置的值;mi表示节点i截断距离内的邻居节点个数。
对所有mi值由大到小排序,取前σ个对应的节点作为备选节点,根据式(9)求各备选节点的ρi值。此处我们设备选节点个数为σ,σ值可根据数据规模确定,且K≤σ≤n-1,其中n为图中节点总数。通过设置备选节点个数,可以缓解截断距离参数的敏感性。
最小距离指标γi计算方法采用原方法:
(10)
基于上述两指标计算θi=ρi×γi,选择θi最大的K个节点作为初始中心。
2.5 整体方法伪代码
本文提出面向故障短文本的改进图节点嵌入与聚类方法流程如算法1和算法2所示。
算法1改进随机游走方法获取图节点嵌入向量。
输入:图结构G=(V,E,W),全节点采样次数r,节点表示序列长度l,词向量上下文最大距离b,嵌入向量维度d,Return参数p,In_out参数q,度差异影响参数τ;
输出:节点嵌入表示向量集合:y_embs。
1.利用公式(3)、(4)、(6)基于图结构参数G=(V,E,W)中的权重W获取转移概率P;
2.初始化节点表示序列集合walks为空;
3.对采样次数iter=1 tor:
对每个节点v∈V:
初始化当前节点表示序列walk为空;
设置初始节点v,并将节点v加入walk,使walk=[v];
当walk长度低于所设节点表示序列长度l时:
依据当前节点的前一节点与附近节点的最近距离情况及涉及节点的度值情况确定从当前节点转移到各个邻居节点的概率;
依据概率将某个邻居节点添加到walk;
将当前节点的walk加入walks;
4.对walks采用SkipGram+负采样方法进行降维,获得维度为d的结构嵌入向量集合St_embs.
5.采用公式(8)训练映射函数,获取融合后的嵌入表示向量集y_embs。
算法2改进局部密度计算方法。
输入:每个节点的嵌入表示向量集合y_embs,备选节点个数σ,预设聚类簇数目K,聚类迭代次数tmp;
输出:聚类结果C。
1.根据y_embs构建距离矩阵H,并基于此确定截断距离dc;
2.对每个节点vi∈V,分别求截断距离内邻居节点个数mi;
3.对所有m值由大到小进行排序,选取前σ个对应的节点,对每个节点vi利用公式(9)、(10)求局部密度ρi及最小距离指标γi,然后分别求θi=ρi×γi;
4.对所有节点的θi值排序,选取最大的前K个θi对应的节点作为初始聚类中心;
5.初始化K个簇,分别包含一个初始中心节点;
6.当迭代次数clu_iter小于tmp时:
计算其余所有节点到K个中心节点的距离,并将其分配到距离最近的中心所在的簇内,形成新的K个簇,记录当前簇中心节点为vi1至vik;
重新计算每个簇的中心位置,并分别与前一次的中心位置对比,若距离不等于0,则clu_iter+1;若距离等于0,则结束循环;
7.验证算法收敛性并返回K个簇。
3 实验及结果
3.1 实验数据
为验证本文中所提GNEC_FST方法中图嵌入与聚类的效果,所采用的公开数据集是github上中文文本数据项目中一个短文本数据集toutiao_cat_data(ttc_data)。该数据集共包含约38万条短文本,共15类,本文中随机选取约1 900条进行所提方法的有效性验证。
真实文本数据来源是汽车产业云服务平台[33]中的业务系统上提取的汽车故障文本数据,选取其中涉及发动机部件的数据,共选取5 903条短文本用于实验分析,数据中各不同机构/系统下的文本条数、预设主题数、平均长度等相关信息如表1所示,故障体系如图3所示。
表1 真实业务数据信息统计表
3.2 参数分析
本文对度值差异影响参数τ和备选节点参数σ进行了选取分析。评价指标为轮廓系数及CH分数,轮廓系数取值范围为(-1,1),轮廓系数越接近1,表示聚类结果越好;反之,应极力避免轮廓系数为负值。CH分数方法评价目标是用尽量少的类别数聚类尽量多的样本数,其取值越大,表示聚类结果越好。
3.2.1 度值差异影响参数τ选取分析
度值差异影响参数τ的取值可以影响游走路线的趋势,从而影响最终形成的嵌入向量。根据前文中式(7)求取ξ,获得整个图的节点度值分布情况,0≤ξ 故障短文本构建的图结构中,关于某个故障部件的全部故障信息节点通常分布较分散,为了充分避免大度值节点的噪音,体现小度值节点的关联关系,本文中τ取值为[1,8]范围内取16个点,分别对发动机部件的4组数据集1、2、4、5获取嵌入向量并聚类,根据结果对比轮廓系数及CH分数。 如图4所示,数据集1中,随着τ值提高,结果表现逐步变好,超过3.5时逐步降低,而后在取值超过5.5后又会有提升,而后再次降低;同样其他数据集中,τ的取值对结果的影响亦存在起伏。整体而言,度值差异影响参数在不同取值下,所得到的轮廓系数及CH分数的值曲线形似“M”型。同时,在不同数据集下,其形态变化呈现不同的平滑程度,这是由于各个数据集规模不同导致其对应的所有节点的度值分布连续性不同,如数据集4规模较小,这种变化起伏则更大;反之,数据集5中数据规模较大,所有节点的度值分布更加具有连续性,ξ值因此变小,即每种度值的节点数差异相对较小,则其相应的变化起伏则较平滑。通过上述分析可知,τ的取值会对聚类结果的影响有明显的起伏,但可以明确地找出有较好表现的取值。因此,通过加入度值差异影响参数来改进搜索偏差的计算方法,可以有效提高节点的聚类表现。 3.2.2 备选节点个数σ选取分析 备选节点个数σ用于确定聚类初始中心,备选节点个数越大,越有可能选到附近节点更紧密的节点作为初识中心。考虑对各数据集需设置不同的K值,此处我们选择了K值相同的数据集2和数据集5进行分析,基于各个数据集所构建的图中总的节点数量,选取备选节点个数σ值取值范围为K≤σ≤2K,即5≤σ≤10,分析结果如表2所示。 表2 不同σ取值对初始中心选取的结果对比 由表3的结果对比可以看出,在备选节点个数σ的影响下,所选取的聚类中心能明显提高聚类的结果表现,并且,随着σ值的增大,其轮廓系数更高。但是另一方面,随着σ值的提高,所消耗的运行时间会明显增多,因此,可以基于数据规模针对性地选择σ的取值以平衡时间消耗及结果表现。 表3 方法参数设置 另外,时间复杂度方面,由2.4节第4段中陈述以及2.5节中算法2步骤3可知,备选节点数量的选择直接影响的参数为局部密度指标ρ,该参数的计算时间复杂度主要包括两部分:①备选节点数量σ取值范围:K≤σ≤n-1;②单个节点ρ值的计算时间复杂度为O(1)。因此,对σ个节点计算ρ的时间复杂度为O(n)。 对方法性能的评价指标为聚类准确率ACC和标准化互信息值NMI,结果取值范围均为[0,1],其值越接近1,则表示聚类结果越好;反之,越接近0则表示聚类结果越差。 3.3.1 对比方法 本文中进行对比方法包括:①Node2vec[14]+LD[28];②HHINE[34]+LD;③改进图嵌入方法+LD;④Node2vec+ILD;⑤HHINE +ILD;⑥本文所提方法:GNEC_FST。选用上述方法,主要考虑到:Node2vec方法是最经典的基于游走的图嵌入方法之一,且本文面向度值差异的搜索偏差计算方法是基于其方法改进的;HHINE是当前基于随机游走的图节点嵌入方法中表现最好的方法之一;本文的另一个改进点是局部密度计算方法,选择与经典的局部密度计算方法对比,所有方法的最终获取聚类结果的方法都是K-Means,因其是图节点聚类研究中最常用的获取聚类结果的方法。 本文所提方法中部分关键参数的取值情况如表3所示,其中后3种参数的取值分别依次对应6个数据集。 3.3.2 方法性能评估 基于1个公开数据集ttc_data和5个汽车产业真实业务数据,结合图3中的发动机部件故障分类体系,本文方法的性能评估基于聚类准确率ACC、和标准化互信息值NMI两个评价指标进行。性能评估结果如表4中所示。 表4 在6个数据集上的方法性能评估结果 对表4中的性能评估结果进行分析可知:①图节点嵌入方法的改进对图节点聚类结果精度的提升较大,而局部密度方面的改进对聚类结果的影响较小;②在故障领域这类数据节点度值差异较大的领域中,GNEC_FST方法表现明显好于其他方法。 图5展示了各方法不同视角下ACC值的对比结果。图5a显示了各个方法针对不同数据集的结果,灰色表示ttc_data数据集的结果,黑色表示故障数据下的结果平均值,各个方法在tcc_data这种常识性数据集中表现区别不大,在汽车故障业务数据集中则明显是GNEC_FST方法表现最好;图5b中3组并列的柱形分别显示了在3种嵌入方法下,两种不同密度计算方法的结果区分;图5c中两组并列的柱形则显示了不同局部密度方法下,3种不同嵌入方法的结果对比。可以看出,面向故障数据集时,嵌入方法的不同对结果的改进更明显。 为有效挖掘故障短文本中跨文本的词汇间关联,构建故障实体节点的全局特征表示,从而获取故障实体节点聚类标签,本文提出了一种面向故障短文本的图节点嵌入与聚类方法,该方法在面向故障短文本的图节点嵌入与聚类上有更优的性能,但是本文构建的图结构是无向图,而故障实体间的关系还有许多是有向的,本文在这方面还需进一步研究。本文通过构建图结构表达故障短文本中的词汇间关联性,未来,随着数据规模的增加,大型图结构可以拓展形成汽车维修知识库等,有利于进行长期动态的知识发掘工作。另一方面,可以继续研究节点-边的特征表示问题,将其拓展到故障预测、知识库补全等方面的研究应用中。3.3 方法性能评估
4 结束语