吴金波 唐前进 杨 明

(公安部第三研究所 上海 201204)

0 引 言

随着信息技术的飞速发展，人类进入了大数据时代，来自商业、社会、科学、工程、医疗以及日常生活的大量数据在飞速产生并实现存储。如何从如此巨量的、无序的、离散的数据中提取有效信息成为当前计算机领域的研究热点，促进了大数据及数据挖掘技术的快速发展。

近年来，人工智能蓬勃发展，引起了数据挖掘技术的又一次革命，研究人员提出了一系列优秀的数据挖掘算法，并证明了这些算法的最优性能。然而，理论上的证明并不能保证算法实现(即数据挖掘应用程序)的正确性，因此针对数据挖掘应用程序进行正确性测评是必要的。

由于数据挖掘本身具有一定的“主观色彩”，所以，数据挖掘应用程序在进行测评时很难找到预知的分析结果与程序输出进行精确的对比，即存在所谓的“Oracle”问题[1]。它指的是，在对某些应用程序进行正确性测评过程中，由于很难构造预期输出等原因而造成的无法确定程序输出是否正确的问题。这是数据挖掘应用程序与普通应用程序在正确性测评方面存在的最重要区别，分类算法作为数据挖掘领域的常用算法，其应用程序测试同样存在着“Oracle”问题。

为了解决该问题，香港中文大学的Chen等提出了蜕变测试[2-3]方法。该方法的核心思想是：对于为数较少的通过测试的正确用例，虽然没有发现应用程序的错误[4]，但能够以该用例为基础，采用一定的蜕变策略构造新的测试用例(称为蜕变用例)及预期输出(称为蜕变输出)。通过检查蜕变用例的程序输出与蜕变输出是否契合来更全面地检测应用程序的正确性[5]。

本文以数据挖掘算法中经典的分类算法为例，对蜕变测试技术在分类算法中的应用进行深入研究。针对分类算法的特点，参考了文献[3]和文献[18]中描述的蜕变关系构造的基本准则，构造了一系列蜕变关系(Metamorphic Relation,MR)，并在KNN算法应用程序的正确性测评上进行了实践，对测评结果进行了分析。

1 问题描述

1.1 蜕变测试综述

蜕变测试以通过测试的正确用例为基础，利用一定的变换规则来生成蜕变测试用例[2]，蜕变测试用例与原测试用例间的逻辑关系(称为蜕变关系)可以确定蜕变测试用例的输入在经过被测程序处理后得到的理论输出(称为蜕变输出)，通过检验实际输出与理论输出是否一致来判断程序的正确性[7-8]，从而实现更全面的应用程序正确性测试[6]。蜕变测试技术是缓解“Oracle”问题的有效途径之一，其普适性较好[6]。蜕变测试的形式化描述如下。

定义1蜕变关系[2,5]。设算法f的实现程序为p，算法f有n个输入i1，i2，…，in(n≥1)，函数输出为o1，o2，…，om(m≥1)。若i1，i2，…，in之间满足关系r，则o1，o2，…，om满足关系rf，即：

r(i1,i2，…，in)⟹rf(o1,o2，…，om)

(1)

则称(r,rf)是算法f的蜕变关系[3,6,8]。

由于程序p是实现算法f的应用程序，若程序p是正确的，必然满足：

r(I1,I2，…，In)⟹rf(O1,O2，…，Om)

(2)

式中：I1，I2，…，In是程序p中对应于i1，i2，…，in的输入，O1，O2，…，Om是程序输出。显然，在进行蜕变测试时，只需要检测式(2)是否成立即可判断被测程序的正确性。

定义2蜕变测试。利用蜕变关系进行的程序正确性测试称为蜕变测试。蜕变测试是一种有效的软件测试方法，在拓展程序正确性测试覆盖面上能够发挥重要作用[9-10]。

定义3原始用例和蜕变用例。利用其他测试方法生成，且用例中的输入经过程序p的处理后得到的实际输出与预期输出一致的测试用例称为原始用例。原始用例经过蜕变关系(r,rf)转换得到的区别于原始用例的测试用例称为原始用例基于(r,rf)的蜕变用例，简称为蜕变用例。

1.2 分类算法

在当今大数据时代，如何在海量、无序、离散的数据中获取有用的信息成为了目前的研究热点，而分类作为有效组织和管理数据的方法受到了广泛关注。目前，较为流行的分类算法包括KNN[11]、决策树[12]、SVM[13]、Native Bayes[14]以及基于深度学习的分类算法等，其中KNN算法以其实现简单、鲁棒性好等优点成为了数据挖掘领域的经典分类算法之一。本文将以KNN算法为具体实例开展针对分类算法的蜕变测试研究。

KNN算法又称K最近邻分类(K-Nearest Neighbor Classification)，是一种经典的模式识别算法，广泛应用于机器学习领域[16]。其核心思想是在训练样本中找到与待分类样本距离最近的K个样本(称为K近邻)，根据K近邻中最占优势的类别来确定待分类样本的类别。即：K个最近邻样本中哪个类别的样本数量最多，则待分类样本就属于该类别[17]。

KNN算法步骤的描述如下：

第一步计算距离。分别计算待分类样本与训练样本集中每一个样本的距离(欧氏距离、马氏距离以及余弦相似度等)。

第二步寻找最近邻。将训练样本集按照第一步计算所得的距离进行排序，找到与待分类样本距离最近的K个训练样本。

第三步确定分类。将待分类样本确定为K近邻中最占优势的类别。

KNN算法的关键问题是K值的选择、距离的计算以及样本的排序。

2 分类程序的蜕变测试方法

2.1 蜕变测试流程

蜕变测试的一般流程如下：

(1) 利用其他方法获得被测程序的原始用例，且原始用例的程序输出与预期输出完全一致。

(2) 研究被测程序的特点，构造一组蜕变关系。

(3) 利用蜕变关系，基于原始用例生成蜕变用例。

(4) 通过检验蜕变用例的输入在经过被测程序的处理后得到的输出是否满足蜕变关系来确定被测程序是否存在错误。

在蜕变测试自动化方面，Gotlieb等[15]提出了自动蜕变测试的框架。蜕变测试的一般流程如图1所示。

图1 蜕变测试流程

2.2 蜕变关系构造

为了便于蜕变关系的描述，针对KNN算法的特点，给出如下定义：

本文模型的主要目的是实现多节点间组成区域内链路状态的预测,但节点数的增加会导致局部区域链路状态的复杂度呈指数倍上升,使得预测难度大大增加.为了探寻节点数和预测效果之间的关系,本次实验切片时长为320s,预测区域的节点数分别为:2、3、4,共进行了30次预测,实验结果如图12所示.

定义5相似类。若待分类样本相对于类型C的类型相似度大于0，则类型C称为待分类样本的相似类。

定义6最大相似类。待分类样本的所有相似类中，若类型C的类型相似度最大，则类型C称为待分类样本的最大相似类。显然，最大相似类就是利用KNN算法得到的分类结果。

定义7最小相似类。待分类样本的所有相似类中，若类型C的类型相似度最小，则类型C称为待分类样本的最小相似类。

定义8完全隶属类。若待分类样本相对于类型C的类型相似度为1，则类型C称为待分类样本的完全隶属类。

定义9不相关类。若待分类样本相对于类型C的类型相似度为0，则类型C称为待分类样本的不相关类。

关于蜕变关系的构造，文献[3]表述了有效蜕变关系构造的基本要求，即有效的蜕变关系应能够对被测程序的核心功能进行有效测试，并对程序错误具有较高的敏感性。基于以上的基本要求，文献[18]对蜕变关系的构造提出了更为明确的5个基本准则。

基于以上参考文献中描述的蜕变关系构造的基本准则，考虑到基于KNN算法的分类程序自身特点，构造以下蜕变关系(设训练样本集容量为n)。

MR1线性平移。若对训练样本集中每一个样本的每一个属性值xi均做线性平移f(xi)=xi+bi,bi≠0，并且对待分类样本的每一个属性值做完全一致的线性平移，则分类结果不变。

MR2等比例缩放。若对训练样本集中每一个样本的每一个属性值xi均做等比例缩放f(xi)=axi,a>0，并且对待分类样本的每一个属性值做完全一致的等比例缩放，则分类结果不变。

MR4属性列置换。若对训练样本集中每一个样本及待分类样本的任意两个属性列ci、cj做置换操作，则分类结果不变。

MR5样本乱序。若对训练样本集中样本的排列顺序进行随机重排，则分类结果不变。

MR6无效属性列增加。若对训练样本集中的每一个样本和待分类样本增加属性值相同的无效属性列，则分类结果不变。

MR7-1全样本复制。若对训练样本集中的所有样本都复制一次，使得训练样本集容量由n变为2n，则分类结果不变。

MR7-2部分样本复制。若在训练样本集中将待分类样本的最大相似类(样本数为m)内所有样本均复制一次，使得训练样本集容量由n变为n+m，则分类结果不变。

MR8不相关类复制。若在训练样本集中选择待分类样本的不相关类(样本数为m)进行一次复制，并按随机顺序插入到训练样本集中，使得训练样本容量由n变为n+m，则分类结果不变。

MR9最小相似类去除。若在训练样本集中选择待分类样本的最小相似类(样本数为m)，将该类的样本从训练样本集中去除，使得训练样本容量由n变为n-m，则分类结果不变。

3 实 验

3.1 实验程序

为了对以上的蜕变关系的有效性进行验证，本文选择了最有具代表性的欧氏距离作为距离度量方法，基于C++语言编写了基于KNN算法的分类程序。

设n维向量空间中存在数据集D，样本点X(x1,x2,…,xn)和Y(y1,y2,…,yn)的欧氏距离do定义为：

(3)

欧氏距离能够表征两个样本点的整体距离(不相似性)，是分类算法中最常用的距离度量方法。其缺点是将不同向量元素同等对待，在各向量元素的量纲不相同的情况下可能导致距离度量偏离实际情况，因此在本文的分类程序中首先对训练样本和待分类样本进行了归一化处理。

3.2 实验数据

本文选取文献[19]中的约会网站数据集作为实验数据集。该数据集内有1 000个样本，每一个样本包含3个元素:每年的飞行里程数,玩视频游戏所占时间比,每周消费的冰淇淋(L)。通过3个元素将约会对象分为不喜欢的人、魅力一般的人和极具魅力的人。

3.3 实验过程

本文采用如下的流程来对蜕变关系的有效性进行评估。

(1) 数据准备。待分类样本集：从实验数据中随机抽取10%的样本，以及在每个属性的取值范围内取随机数生成待分类样本。训练样本集：实验数据中除待分类样本以外的样本组成训练数据集。

(2) 运行分类程序得出分类结果，并统计“最大相似类平均相似度”和“相似类总数指标”。

(3) 按照2.2节中所述的蜕变关系对训练数据集进行处理，构造蜕变用例。

(4) 以蜕变用例的输入作为程序输入，重新运行分类程序，验证蜕变用例输出是否与预期结果一致，并检查各项分类指标是否发生变化。

(5) 对分类结果和分类指标的变化进行分析，确认每一条蜕变关系是否有效。

3.4 实验结果

首先给出本文用于评估蜕变测试效果的指标定义：分类结果、最大相似类平均相似度以及相似类总数。分类结果定义见定义6。

定义10最大相似类平均相似度。若待分类样本集的样本容量为n，设该样本集中第i个样本的最大相似类相似度为si，则当前待分类样本集的最大相似类平均相似度定义为：

(4)

定义11相似类总数。若待分类样本集的样本容量为n，设该样本集中第i个样本的相似类数量为ai，则当前待分类样本集的相似类总数定义为：

(5)

表1汇总了实验结果，显示了原始用例与蜕变用例基于“分类结果”、“最大相似类平均相似度”以及“相似类总数”三个指标的对比结论。当原始用例和蜕变用例输出的指标一致时，则表中填入“不变”；当原始用例和蜕变用例输出的指标不一致，且指标值无法确定增大或减小，则表中填入“变化”；当原始用例和蜕变用例输出的指标不一致，且指标值确定增大，则表中填入“提高”；当原始用例和蜕变用例输出的指标不一致，且指标值确定减小，则表中填入“降低”。

3.5 结果分析

由表1可以看出，原始用例经过以上10种蜕变关系变换后的蜕变用例在“分类结果”这一指标上都未发生变化，与预期的结果一致，说明分类程序在分类正确性上利用以上的蜕变关系未能发现错误。在“最大相似类平均相似度”和“相似类总数”这两个更为精细的指标上，某些蜕变用例发生了变化。这些变化可能是程序隐含错误导致的，也可能是另有原因，需要对程序实现细节及蜕变关系本身进行深入细致的分析。

MR1、MR2、MR3、MR4的所有指标均未发生变化，与预期一致，不做讨论。

MR5对训练样本集进行随机乱序，形成蜕变用例，与原始用例相比，“最大相似类平均相似度”和“相似类总数”两个指标均发生变化。通过对KNN分类程序源代码分析可知，为提高程序运行效率，距离差小于一定阈值，KNN分类程序不对训练样本做基于距离的排序调整。因此，在极少数情况下，原始用例中K近邻内个别距离较远的样本在蜕变用例中可能因为排序问题未入选K近邻(称为淘汰样本)，而入选了其他样本(称为新入选样本)。若新入选样本为最大相似类中的样本，则“最大相似类平均相似度”指标提高；若新入选样本不是最大相似类中的样本且被淘汰样本是最大相似类中的样本，则“最大相似类平均相似度”指标降低。MR5的“最大相似类平均相似度”指标提高或降低不明确，因此该指标表现为“变化”。进而，在某些最大相似类不占绝对优势的情况下，可能引起分类结果发生变化。若新入选样本入选K近邻后，其所属类由不相关类变为相似类，则“相似类总数”指标提高；若淘汰样本被淘汰出K近邻后，其所属类由相似类变为不相关类，则“相似类总数”指标降低。MR5的“相似类总数”指标提高或降低不明确，因此该指标表现为“变化”。

MR6增加值相同的无效属性列，所有指标均未发生变化，与预期一致。若增加的无效属性采用不同的赋值(随机值)，则可能对分类结果带来不可预知的变化。由此可以得出结论，在进行分类计算时，非关键属性的引入可能对分类结果的正确性带来严重的负面影响。

MR7-1对训练样本集进行全样本复制，形成蜕变用例，与原始用例相比，“最大相似类平均相似度”指标提高，“相似类总数”指标降低。通过对KNN分类程序源代码分析可知，若原始用例中入选K近邻的最大相似类样本数量为n，则对训练样本集进行复制以后，蜕变用例中入选K近邻的最大相似类样本数量将接近2n，显然“最大相似类平均相似度”指标在蜕变用例中会提高。由于最大相似类复制样本对K近邻的“填充”，导致入选K近邻的非最大相似类样本减少，使得某些类由相似类变为不相关类，因此“相似类总数”指标降低。

MR7-2对最大相似类内的样本进行复制，形成蜕变用例，与原始用例相比，“最大相似类平均相似度”指标提高、“相似类总数”指标降低。引起指标变化的原因与MR7-1基本一致。

MR8对不相关类内的样本进行复制，并随机插入到训练样本集中，形成蜕变用例，与原始用例相比，“相似类总数”指标发生了变化。引起指标变化的原因与MR5相同，在极少数情况下，由于程序性能优化和样本排序问题在蜕变用例中引起不相关类和相似类变化，从而导致“相似类总数”指标提高或降低。

MR9从训练样本中去除最小相似类，形成蜕变用例，与原始用例相比，“最大相似类平均相似度”指标提高，“相似类总数”指标变化。通过对KNN分类程序源代码分析可知，最小相似类的样本去除后，必然会有新的样本入选待分类样本的K近邻，用以填补去除最小相似类样本后的“空白”，新入选K近邻的样本若属于最大相似类，则“最大相似类平均相似度”指标提高。若新入选K近邻的样本全部属于最大相似类，则“相似类总数”指标可能降低；若新入选K近邻的样本属于2个以上不相关类，则“相似类总数”指标可能提高。因此，“相似类总数”指标表现为“变化”。

3.6 实验结论

本文构建的KNN分类程序经过以上10种蜕变测试，有效的测试用例明显增加，虽然未能发现程序错误，但在程序的实现方式及分类规则的构建上发现了可改进空间。

(1) 参与分类的样本属性需要经过慎重的筛选，非关键属性的引入可能影响分类结果的正确性。

(2) 对分类程序的性能优化可能影响分类结果，因此在进行程序性能优化时在优化方法及优化阈值的合理性上需要进行详细的测试论证。

4 结 语

本文提出的基于蜕变关系的KNN分类程序测试方法，不仅能够有效拓展测试用例集，达到核查程序正确性的目的，还能够对程序的优化起到一定的指导作用。以上基于蜕变关系的测试思路可以推广到其他具备蜕变特性的数据挖掘程序测试上，在进行具体的蜕变关系构造时由测试专家和算法专家一起配合，分析数据挖掘算法的特点，识别蜕变关系，更全面地构造有效的蜕变用例，缓解数据挖掘算法程序测试上的“Oracle”问题。