K-means聚类算法在回归测试用例选择中的应用

《K-means聚类算法在回归测试用例选择中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于判别型半监督K-means聚类方法的回归测试用例选择技术程雪梅【摘要】回归测试的目的是保证修改过后的软件没有引入新的错误。但是随着软件的演化，回归测试用例集不断增大，为了控制成本，回归测试用例选择技术应运而生。近年来，聚类分析技术被运用到回归测试用例选择问题中。其基本思想为：根据测试用例的历史执行剖面进行聚类，将具有相似的函数覆盖、能够发现相同故障后面聚类时，将能够覆盖相同函数的测试用例聚类到一起，与这里不一致。当然也可以理解为覆盖了相同函数的测试用例，也能够发现相同的错误，但这两种描述方式的侧重点不一样。好的，就这样改吗？改成具有相似的函数覆盖、能

2、够发现相同错误的测试用例。的测试用例具有相似的函数覆盖、能够发现相同错误的测试用例？改为发现相同错误。聚为一个簇。然后通过取样策略从每一簇中选出一定比例的测试用例组成新的测试用例集。将半监督学习引入到聚类技术中，提出了判别型半监督K-means聚类方法（DiscriminativeSemi-supervisedK-means，简称DSKM），该方法通过从回归测试的历史执行记录中挖掘出隐藏的成对约束信息，同时利用大量的无标签样本和少量的有标签样本进行学习，从而优化聚类的结果，近进一步优化测试用例选择的结果。通过实验，发现相对于普通的K-means算法，DS

3、KM方法在保持较高的召回率和代码覆盖率的前提下，准确率和约简率都有明显的提高。【关键词】回归测试测试用例选择K-means算法成对约束线性判别分析1引言在软件开发的过程中，软件系统及其环境在不断地进行变化。增强功能、纠正错误、新增或者删除功能，都需要修改代码并触发软件的演化。为了确保演化后的软件能够正确运行并且新的改变没有引入新的错误，必须对软件进行回归测试[1]。统计数据表明，回归测试开销一般占整个软件测试预算的80%以上，占整个软件维护预算的50%以上，因此有效的回归测试是非常重要的[2]。然而，随着软件的不断演化，测试用例集不断增大，由于资源有限，

4、几乎不可能运行所有的测试用例。为了提高回归测试的运行效率，许多策略被提出，其中最主要的一种技术是回归测试用例选择技术[3]（RegressionTtestCcaseSselection，（简称RTS）。回归测试用例选择定义为：设程序P，以及P对应的测试用例集T，设改变过后的程序为P’，寻找T的子集T’对P’进行测试，并且保证T’具有与T近似相等或者足够的测试覆盖率。近年来，数据挖掘中的聚类技术被用于解决回归测试用例选择问题技术引入数据挖掘的方法。聚类测试选择的其基本思想是：根据测试用例的历史执行剖面进行聚类，将具有相似的函数覆盖、能够发现相同故障的测试用

5、例聚为一个簇。同一簇中的测试用例具有相似的行为，而不同簇中的测试用例的行为差异较大引用的其他论文中对聚类测试的基本思想的解释。因此，若一个测试用例能检测某一故障，则属于同一簇的其他测试用例通常也能检测到这一故障[1]。在回归测试时中，只需从每一簇中选取一定比例的测试用例组成新的测试用例集T’，新测试用例集T’的精度和覆盖率在很大程度上依赖于聚类结果，而聚类结果很大程度依赖于聚类算法的选取。传统的K-means聚类算法是无监督的，而且算法对选取的K值和初始的簇中心都非常敏感，可能会产生局部最优的聚类结果，从而导致选择出的测试用例无法满足较高的准确率和覆盖率

6、。为了优化聚类的结果，论文提出一种判别型半监督K-means聚类方法（DiscriminativeSemi-supervisedK-means，简称DSKM），将半监督聚类运用到回归测试用例选择中。在保证测试用例覆盖率的同时，减少测试用例，从而缩减回归测试的成本，提高回归测试的效率。论文第1一部分介绍了研究背景，提出研究的问题。第2二部分对目前该领域的相关研究做出了进行总结。第3三部分对论文提出的方法进行了介绍。第4四部分通过设计和执行实验，验证提出的方法对实验结果做出了定量的分析。第5五部分对论文进行总结，提出未来工作。1相关工作还需简化针对在回归测试

7、用例选择技术Regressiontestcaseselection（简称RTS）问题的研究这一段举了几个一般测试用例选择技术的相关研究，中，对RTS问题的研究最早可以追溯到Fischer在1977年发表的研究论文[4]。随后，众多研究人员提出了很多的解决方案[4]。大致可以总结为以下几类[4]：1)线性规划法：Fischer等人针对Fortran编程语言首次对RTS问题展开研究。他们基于基本语句块构造出两个矩阵：可达矩阵和测试用例依赖矩阵。通过可达矩阵，可以计算获得存在可达关系的其他基本语句块并将其取值设置为1。2)数据流分析法：这类方法对代码修改进行数

8、据流分析，通过识别出新添、修改或删除的定义使用对（Definition-useP