一种无监督的软件复杂度度量与评估模型①

柯文俊 王泊涵* 杜泽峰** 姜 利*** 缪沛恩****

(*中国科学院计算技术研究所 北京 100190) (**中国科学院大学 北京 100049) (***北京计算机技术及应用研究所 北京 100089) (****国防科技大学信息工程学院 长沙 410073) (*****中国地质大学信息工程学院 北京 100190) (******中国科学技术大学软件工程学院 合肥 230051) (*******南昌大学信息工程学院 南昌 330000)

0 引 言

随着计算机控制系统智能化、信息化的深入，计算机控制系统越来越成为一种软件密集型装备，软件作为“计算机控制系统”的核心被广泛使用，计算机控制系统软件的规模呈超几何级数增长。随着软件规模的增长，软件从各方面都会变得越来越复杂，这给软件项目开发、测试、维护带来了重重困难。

针对高复杂度软件，要求设计时就找到合适的设计模式和开发方法，控制软件复杂度与性能，解决软件维护保障困难，保证其可信属性，保证软件质量，提高开发效率。通过度量和评估，掌握软件开发过程的复杂度数据，并加以分析、利用，可将软件过程管理发挥作用，使得软件开发工作持续改进、发展。

软件度量作为软件工程的重要组成部分，在软件工程及软件过程中的作用不言而喻。软件复杂性度量作为软件度量的重要分支，可以有效评估软件产品的复杂性。通过复杂性度量对软件复杂性进行预警，可以帮助人们客观地分析和评估软件生命周期不同阶段的复杂度情况，并采取一定的复杂度控制和降解措施，来降低软件缺陷率，提高软件质量。本文旨在通过软件复杂性的度量与综合评估，改进软件开发过程、降低软件缺陷率、改进软件评估体系，从而完善计算机控制系统软件过程管理、提升软件质量、优化软件测试的资源分配，为高质量软件研制提供支撑。

软件复杂度度量元数据是一种客观存在的集合，如何针对客观数据，制定无监督的综合评估模型，成为现阶段软件工程领域的难题，本文通过研究软件复杂度度量元的概率分布，利用高斯混合模型(Gaussian mixture model，GMM)进行度量元概率归一化；进而，通过皮尔逊相关系数分析度量元间的涌现特征，建立最大权值的顶点表示活动(activity on vertex，AOV)网络，计算各领域软件度量元的融合概率，形成一种面向计算机控制系统领域的无监督软件复杂度评估模型。

1 相关工作

1.1 软件复杂度度量元及度量方法

软件的复杂度度量方法有代码行度量法[1](line of code，LOC)、Halstead软件科学度量法[2](Halstead software science，HSS)、McCabe圈复杂度度量法[3](McCabe cyclomatic complexity，MCC)，它们依次测量软件的长度、体积和结构复杂度，是经典的测量方法。其中，MCC方法以图论为基础，通过分析程序的控制流图来获得模块的复杂度，HSS是在程序中操作符和操作数做统计的基础上,建立起程序的总词汇表,对程序长度、算法的潜在最小容量、实际容量、程序级别、程序难度进行度量。还有Oviedo的数据流度量[4](Oviedo data flow，ODF)、Henry的信息流度量[5]( Henry information flow，HIF)、Emerson的聚合度量[6]、Yau和Collofello的稳定性度量[7](Yau and Collofello’s stability，YCS)等度量法，它们从测量代码模块内部或外部的逻辑关系或依赖关系的层次进行软件复杂度的度量；此外，在面向对象的软件度量方面先后出现了一批有效的度量元来度量面向对象开发软件的复杂度，包括C&K度量集[8]、MOOD度量集(metrics for object oriented desiGn)[9]、改进C&K度量集的Li度量集[10]以及Chen&Liu[11]度量集，它们对类、类之间的关联、方法以及面向对象的各种特征进行度量；在面向对象软件的复杂度评估方面，Chidamber和Kemerer[8]提出的基于面向对象的度量指标(Chidamber Kemerer six，CK6)，使用C++代码的6个度量指标来评估复杂度的方法被广泛使用，这6个度量指标分别度量每一个类中所有方法的复杂度度量，继承的深度，孩子个数，一个类的响应数，对象间的耦合程度以及方法内部的聚合的缺乏度。黄光燕和李晓维[12]提出软件复杂度的变量度量方法(variable metrics method，VMM)，分别度量软件的变量个数、变量距离及变量聚合缺乏度来估计软件的复杂度。它通过度量构成软件的基本元素变量来度量，更能从底层抓住软件的本质，而且该方法在实际的软件复杂度估计中十分准确有效。文献[12]提出对软件系统模型的时间/堆栈分析的软件复杂度度量方法，可减少后期系统发生错误的概率。文献[13]提出了一种通过研究软件复杂度与统一建模语言(unified modelinG lanGuaGe，UML)模型的关联关系进而基于UML模型来评估软件复杂度的方法，可在软件开发的早期评估软件的复杂度。文献[14]通过代表对软件复杂性理解和直觉感受的多个概念和公式，来评估软件的复杂度，这种基于概念、公式等信息的评估方法对此前造成评估不准确的因素是弹性可恢复的。

软件的度量方法虽多，正如文献[15]指出，或许单独的一种度量方法是有效的，把它们综合起来或许就没用了。在比较软件复杂度度量的有效性的文献中，文献[16]用确凿的大型软件实例证明最简单的LOC度量打败了精细化度量的CK6(CK6度量博采众家之长，综合了许多度量方法)方法。以上的这些度量方法(从LOC到CK6)度量的抽象层次太高而且抽象层次也各不相同，都没有从根本上去度量软件的最原始核心。W9和P3抓住了一些软件的本质属性，但是不能解释为什么有这样的属性。而软件的变量度量方法(VMM)分别度量软件的变量个数、变量聚合度以及变量距离来估计软件的复杂度。该方法通过度量构成软件的基本元素变量，更能从底层抓住软件的本质。

1.2 数据归一化

数据的归一化能够提高求解速度和计算精度，归一化常用方法包括线性归一化(linear scalinG)、0均值标准化(z-score standardization)、非线性归一化(nonlinear scalinG)、局部响应归一化(local response normalization，LRN)、批归一化(batch normalization)、局部对比归一化(local contrast normalization)等。

线性归一化把原始数据取值转换到[0,1]之间，实际使用时，不同样本集得到的max/min可能不同，造成归一化结果不稳定，从而使模型也不稳定。0均值标准化转换后的数值服从均值为0、方差为1的高斯正态分布，适合原始数据近似高斯分布的情况，否则归一化后的效果会很差。非线性归一化使用对数函数、指数函数、正切函数等对数据归一化，当数据分化比较大，有些很大，有些很小时，此方法可将数值映射到一个比较小的范围进行处理。局部响应归一化多用于神经网络中，对局部神经元的活动创建竞争机制，使得其中响应比较大的值变得相对更大，并抑制其他反馈较小的神经元，增强了模型的泛化能力。批归一化由GooGle于2015年提出，是一个深度神经网络训练的技巧，它不仅可以加快模型的收敛速度，而且在一定程度上缓解了深层网络中“梯度弥散”的问题，从而使得训练深层网络模型更加容易和稳定。局部对比归一化主要进行的是局部做减和做除归一化，它会迫使在特征矩阵中的相邻特征进行局部竞争，还会迫使在不同特征矩阵的同一空间位置的特征进行竞争，多用于神经网络中。

1.3 复杂度综合评估方法

多种软件复杂度采用多种度量元的综合评估方法(综合评判函数)被相继提出。文献[17]使用加权平均型综合评价函数来计算并比较学生所写的2个不同代码的复杂度。文献[18]提出Telenor方法从广泛的角度对IT复杂性进行综合评估。文献[19]提出满足9个Weyuker属性的软件复杂性综合评估方法，相比McCabe、Halstead和Oviedo等复杂性度量方法更具有鲁棒性。文献[14]为软件系统中的信息容量复杂度(information volumetric complexity，IVC)提供了一种计算方法，它捕获了软件模块中设计信息的数量，取得了良好的复杂度计算效果。

此外，还有多种度量元按权重计算的方法，软件复杂度各个度量元的重要性是不同的。文献[20]在软件可靠性评估领域，使用模糊层次分析法对评估进行管理。文献[21]在iso/iec 25010软件质量模型的基础上，采用模糊综合评价法和三角形模糊数层次分析法建立了软件质量的综合评价模型。

2 软件复杂度的无监督评估模型

文本首先提出了一个基于高斯混合模型的度量元概率归一化方法，旨在将不同量级的软件度量元都无监督地归一化到[0,1]之间；然后针对不同领域的软件对各类度量元敏感程度不同的特点，将软件复杂度评估定义为一个基于度量元归一化结果的线性加权模型。本文提出基于影响域AOV网络的特征融合算法，借助皮尔逊相关系数，分析度量元间的涌现特征，进而得到各度量元的最大影响域，并借助拓扑排序算法思想，计算得到度量元的特征权重，最终确定软件的综合复杂度。

首先用高斯混合模型分别对每个度量元数据建模，将各个度量元的高斯混合模型的分布概率作为归一化值；然后基于皮尔逊相关系数获得这些度量元间的相关关系，同时用现行回归模型拟合每2个度量元归一化后的软件度量元数据，获得每对度量元的斜率，作为权值；接下来用每组度量元间的皮尔逊系数，对斜率权值数据进行过滤、筛选，获得度量元间的相关性大小；最后，根据度量元间相关性大小构建AOV网络，获得各度量元的影响域，进而得到各度量元的重要度权值，从而可以根据这些权值对新的软件度量元数据计算软件的复杂度。其中，本文使用的度量元是由领域专家针对不同软件类分析大量软件数据、同时考虑各度量元的不足而筛选得到的。

2.1 软件程序度量元设计与选择

针对软件程序复杂度的度量，本文总结提炼常用的程序复杂度度量元，有圈复杂度(圈复杂度度量一个模块逻辑复杂度的值)、代码行等。本文选择的度量元见表1。

表1 软件度量元设计及选择

2.2 基于高斯混合模型的度量元概率归一化算法

由于样本数据中各个特征的数量级存在较大的差异，数量级大的特征容易掩盖数量级小的特征的变化，获得较大的影响力，从而影响算法的精度、有效性和收敛速度。此外，在多类计算机控制系统中，某度量元值出现频率越高，该度量元的影响力越大。针对系统中存在的以上特点，本文使用一种新的基于高斯混合模型的度量元概率归一化算法，从概率的角度分别对数据中的各个度量元进行概率归一化处理。首先，针对数据中的各个度量元的频率分布，使用无监督的最大期望算法(expectation maximization alGorithm，EM)对其进行高斯混合建模，拟合该度量元的概率密度函数；然后，基于该度量元的概率密度函数计算其累积分布函数，使用累积分布函数的值作为该度量元的归一化处理后的数值，分布函数的非降性、有界性和右连续性，保证了本概率归一化算法的有效性和准确性。

2.2.1 度量元频率分布高斯混合建模

高斯混合模型(GMM)是多个高斯分布函数进行线性组合后得到的概率分布模型，理论上可以拟合任意类型的分布。GMM的概率分布如式(1)所示，任一分模型的高斯分布密度函数如式(2)所示。

(1)

(2)

其中，πk是系数，πk≥0。

在大量控制类软件的样本数据度量中，与高斯混合模型相比，使用高斯混合模型能够更好地拟合各度量元M的分布。在对度量元的频率分布进行高斯混合建模时，本文选择样本数据似然最大的超参数K值作为最终高斯混合模型的K值。选择算法如下：针对各个K值，首先使用无监督的EM算法进行度量元频率分布的高斯混合建模；然后计算所有样本数据的似然概率，选择似然概率最大的K值作为高斯混合模型的K值。

2.2.2 度量元的概率归一化计算

分布函数定义为随机变量X取值小于x的累积概率函数，用于描述随机变量落在任一区间上的概率，也称为概率累积函数。使用高斯混合分布拟合特征X的概率密度函数p(x)时，X的分布函数如式(3)所示。

(3)

分布函数是随机变量最重要的概率特征之一，可以完整地反映随机变量的统计规律，并且决定随机变量的其他概率特征。此外，分布函数具有非降性、有界性和右连续性，其取值范围是[0, 1]，具有良好的统计特性。故使用特征x的分布函数值F(x)作为特征X的归一化处理后的值，实现特征X的概率归一化计算，X取x值的概率越大时，可以认为x值越重要。

在软件复杂度评估中，本文首先使用GMM拟合任一软件度量元的数据，然后计算得到该GMM模型的分布函数，则度量元数值对应的分布函数值即作为该度量元的概率归一化值，实现度量元数据的归一化。针对任一软件度量样本X={x1,x2, …,xj, …,xm}，基于高斯混合模型的度量元概率归一化结果为R={R1,R2, …,Rj, …,Rm}，其中第j个度量值xj的归一化值Rj的计算方式如式(4)所示。

(4)

2.3 基于AOV网络的软件复杂度评估算法

本文在基于高斯混合模型对度量元数据进行概率归一化的基础上，借助AOV网络，基于度量元在软件复杂度评估中的重要程度来赋予不同的权重，通过线性组合来计算软件的整体复杂度，对软件复杂度进行综合评估。本文的无监督复杂度度量方法采用了多种度量元，不同度量元之间相关影响，一个度量元的变化可能与其他度量元相关，本文将度量元之间的相关关系引入到度量元的权值计算中，从而获取更优度量元融合策略。

皮尔逊相关系数用来度量2个变量间的线性相关性，其值在-1与1之间。本文中，首先计算不同度量元间的皮尔逊相关系数，评估其相关关系的大小，得到度量元的皮尔逊相关系数矩阵P；然后，基于线性拟合方法得到不同度量元间线性相关关系的斜率大小，得到度量元的斜率矩阵K；继而，基于皮尔逊相关系数的大小与斜率的大小对斜率进行过滤处理，剔除不相关或者斜率值小于阈值的斜率，得到斜率矩阵T；进而，将斜率矩阵转化为一个有向有环图，度量元作为图中的节点，斜率矩阵中度量元间的斜率作为图中对应边的权重；接下来，通过最大生成树算法将有向有环图转换为AOV网；最后，基于AOV的权重计算每个度量元的影响域，根据度量元影响域的大小分配每个度量元的权重。基于AOV网络的软件复杂度评估算法，见算法1。

算法1基于AOV网络的软件复杂度评估算法

输出：样本各度量元权重集合W={W1,W2, …,Wp}。

(1) 计算不同度量元间的皮尔逊相关系数矩阵P=Pm×m， pab为样本集R中第a个和第b个度量元的数据集Sa、Sb间的皮尔逊相关系数，计算方式如公式(5)所示。

(5)

(2) 计算不同度量元间的斜率矩阵K=Km×m， kab为样本集R中第a个和第b个度量元的数据集Sa、Sb间使用线性拟合方法计算的斜率。

(3) 斜率矩阵K的过滤处理。当2个度量元间的相关系数pab小于阈值β，或者斜率kab小于γ时，认为第a个和第b个度量元间不具备线性相关关系，置wab=0，本文β1取0.8，从而得到权重矩阵T=Tm×m，计算方式如式(6)所示。

(6)

(4) 基于邻接矩阵T构造有向有环图G(N,E)；其中N={n1,n2,n3, …,nm}，节点ni表示第i个度量元构成的节点；E={…,eab, …}为有向有环图中所有边的集合，其中eab表示度量元a指向度量元b的边且eab的权重等于tab。

(6)计算AOV网G′(N,E′)中的节点ni(代表第i个度量元)的影响域Ii，得到各节点影响域集合I={I1,I2, …,Im}，计算见式(7)。

(7)

(7)计算各节点(度量元)的权重W={W1,W2, …,Wm}，其中节点ni对应的权重是Wi，计算方式如式(8)所示。

(8)

3 实验结果

本节首先介绍了本文使用的数据集，然后阐述了对比算法和评价指标等实验设计，最后分别从定性和定量2个方面分析本文算法在软件复杂度评估上的结果及其原因。

3.1 实验数据集

在3种数据集上验证本文所提出的模型，分别是信号处理类软件(siGnal processinG software，SPS)、显示控制类软件(display control software,DCS)和算法控制类软件(alGorithmic control software，ACS)3类软件的度量原始数据，数量分别是980、870、950个。尽管不同种类控制软件的度量元存在一定的差异，本文的软件复杂度度量算法可以针对不同的软件类型，无监督地、自适应地学习各度量元的权重，赋予不同度量元以不同的重要性，在选择度量元时应该尽可能多地选择度量元。本文中，在度量3类软件的复杂度时，均选择了相同的度量元来分别度量软件复杂度，表1列出了本文3类软件选择的度量元。

实验时，本文将任一数据集切分为70%的训练数据、20%的验证数据和10%的测试数据，训练数据用于构建模型，验证数据用于确定GMM模型的子模型数量、阈值β和 γ等系数，测试数据用于输出预测效果。

为了方便分析阐述本文复杂度度量算法的有效性，表2罗列了部分软件的原始度量数据。

3.2 实验设计

本文采用LOC、VMM、CK6、人工专家评估(记为HEE)作为对比算法，与本文模型进行比较，为了方便评估，将各种方法度量的复杂度通过均值方差标准化到0～1之间比较。采用根均方差(root mean square error，RMSE)和均值平均精度(mean averaGe precision，MAP)作为本文实验的评价指标，其定义如下。

根均方差是估计值与真实值之差平方的期望值的开方，是衡量平均误差的一种较方便的方法。计算公式如式(9)所示。

(9)

单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。 MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就可能越高。如果系统没有返回相关文档，则准确率默认为0。

3.3 实验结果及分析

分析本文所提算法与对比算法在整体性能上的结果，首先分别在3个数据集上构建所提出的复杂度度量模型以及对比算法模型，然后以专家度量评估结果为基准，分别计算本文模型和对比模型的复杂度度量结果与人工专家度量结果的RMSE和MAP，表3和表4分别给出了3次实验结果计算的平均值。

表2 软件度量的部分原始数据

表3 软件度量的RMSE实验结果

表4 软件度量的MAP实验结果

根据表3可知，在3种类型的软件数据集上，本文算法相对其他3种对比算法取得了更好的效果，进一步说明了本文算法的有效性。在RMSE的评估结果上，对于LOC算法，在DCS类软件上取得了相对更好的度量效果，误差最低；对于CK6算法，则在SPS类软件上取得了更好的度量效果；对于VMM算法，则在DCS类软件上取得了更好的度量效果；而本文提出的度量模型，则在3类软件上的度量效果相差不多，由此可见，LOC算法、CK6算法或者VMM算法，在软件复杂度度量上与软件类别较为相关，可能在一类软件上能够取得较好的结果，但在其他类软件上度量效果极有可能不理想，而本文提出的度量模型对不同类软件的度量结果，误差较低，且不依赖于软件类别，是一种更优越的度量算法。此外，分析SPS、DCS、ACS这3类控制类软件，本文模型的度量效果均比对比模型取得了更好的效果。由此可见，而本文模型的无监督、自适应的权重确定方式能够根据不同的软件类别，自适应地调整不同度量元的权重，从而更好地对不同类别的软件进行复杂度的度量，适用范围更广，这充分说明了本文模型的概率归一化和AOV网络权重自适应算法的有效性。

表4中MAP评估指标的计算是2种度量算法根据软件测试数据集中复杂度度量的相对顺序来计算的，同样以人工专家的度量相对顺序为基准顺序，分别计算文本模型和对比模型的软件复杂度度量顺序与基准顺序得到，这种软件度量的相对顺序具有更具说服力的效果。由表4可知，根据MAP实验结果，各度量模型在不同类型的软件数据上的评价精准度差异相对更小，但可以看到，文本的模型仍然在SPS、DCS、ACS类软件上取得了最好的结果，且在不同类软件上的度量平均精准度仍然相差最小，结果说明了本文所提出模型的优越性，优于LOC、VMM和CK6算法。

本文通过MAP定性的评估指标以及RMSE定量的评估指标的实验结果，可以看出本文算法的高斯混合模型的数据概率归一化方式和基于AOV网络进行度量元权重的自适应确定方式的有效性和合理性，本文所提出的算法在软件复杂度度量上，对软件类型的适用范围更广，且效果更好。

4 结 论

本文提出了一个融合高斯混合模型(GMM)概率归一化和AOV网络自适应权值的无监督的软件复杂度度量算法，软件度量元数据的概率归一化，表征了度量元数据在同类型数据中所处的概率位置，避免了度量元间数量级不同对算法精度、有效性等的影响。此外，度量元间的关系通过皮尔逊相关系数和线性回归相关系数来计算，并通过AOV网络自适应地确定各度量元的影响域和权值，从而摆脱了人工专家的干预。通过在不同类型的软件度量元数据集上的实验发现，本文所提出的算法在软件复杂度度量评估上要优于作为对比的传统方法，尤其是优于基于多度量元的传统方法。但本文的工作还存在一些可改进之处，如，对度量元进行高斯混合建模时通过人工观察该度量元数据分布来选择其子模型个数的方式较为费时，可以通过参数搜索的方式自适应地找到最适合的参数。另外，根据AOV网络及其权值确定各度量元的权重时，是对各度量元的出度节点进行归一化加权计算方式来确定，其存在拥有不同层数出度节点的度量元的权重差异过大的问题，在未来的工作中，会更为合理地根据AOV网络进行权重自适应的方式来更好地解决这些问题。