一种基于形式概念分析的软件质量评价方法

【关键词】形式概念分析 概念格 二值背景

软件质量

概念格理论，也称形式概念分析(Formal

Concept Analysis)，由Wille R 于1982 年提出，

是一种有效的知识表示与知识发现的工具，已

被成功用于决策分析、数据挖掘等领域，概念

格结构模型是该理论的核心数据结构。它是根

据形式背景（称为形式背景）中属性与对象之

间的二元关系建立的一种概念层次结构，生动

而又简洁的体现出了概念之间的特化和泛化的

关系，概念格中的每一个节点表示的是一个形

式概念。概念是由两部分组成的：内涵表示的

是概念的属性，也就是这个概念所有的对象共

同具有的属性；外延则表示的是概念所覆盖的

对象。哈斯图则非常形式化的体现了这些概念

之间的关系。

概念格理论在各种形式背景的知识表示

和知识发现中发挥着独特优势，基于概念格理

论所创造的系统具有和其他数据挖掘系统无法

比拟的性能。概念格已经被广泛应用于机器学

习、信息检索、知识工程、软件工程、语义

Web、数据挖掘等领域。本文描述形式概念分

析在软件质量评价领域的应用。

1 背景知识

形式概念分析是基于数学的序理论的，特

别是基于关于完全格的理论。概念格的理论是

建立在格论以及图论等相关理论的基础上的，

本节介绍概念格的基本理论。首先给出形式背

景的定义。

定义1 称（U，A，I）表示一个形式背景，

其中U=（x1,...,xn）为对象集，每个称

之为一个对象；为属性集，每个

称一个属性；I 为A 和U 之间二元关

系， 。

对于形式背景（U，A，I），若，

则说x 具有属性，记为. 本文中，用1 表

示， 用 0 表示这样就可以用只

有0 和1 的表格来表示形式背景。

文/金腾辉 孙龙

形式概念分析是一种有效的

知识表示与知识发现工具，在数

据挖掘、知识发现、信息检索、

软件工程等领域得到了广泛的应

用。本文描述了形式概念分析在

软件测试领域对软件质量评价的

一种方法，利用概念格表示分析

和统计软件测试结果，根据软件

测试结果建立形式背景，从而建

立概念格，用于对软件测试结果

进行分析，为软件质量评价提供

了一种新的方法。文中主要描述

了形式概念分析在软件测试阶段

的应用。

摘 要

对于形式背景（U，A，I），在对象的子

集和属性的子集上首先可以定义

这样一对对偶算子：

式（1）

式（2）

X* 表示X 中全部的对象都共同所具有的

属性的集合，B* 表示共同的包含B 所有属性

的对象集合。记为x*； 记

为. 若Ø， ，且

Ø， Ø 则表示形式背景

为正则的。在本文中若没有明确的指出，所用

的形式背景都是正则的。

定义2 设为形式背景。如果一个

二元组（X，B）满足X*=B，且X=B*，则称（X，

B）为一个形式概念，简称为概念。其中B 称

之为概念的内涵，X 称之为概念的外延。

对于一个形式背景

，可以得到

以下的一些基本性质：

（1）

式（3）

（2） 式（4）

（3） 式（5）

（4） 式（6）

（5）

式（7）

（6）

式（8）

（7）（X**，X*）和（B*，B**）都是概念。

用来表示形式背景的全部

概念，记

式（9）

则“≤”是上面的偏序关系。

其中叫做的亚概念，叫做

的超概念。

若和是概念，则：

式（10）

式（11）

也是概念，从而是格，并且是

一个完备格。

定义3 设， 且不存

， 使得

则称是的

父概念，是的子概念。

2 形式概念分析的应用

本节叙述形式概念分析在软件测试领域

的应用。

概念格的建立是概念格应用的基础，而

形式背景的构造是概念格建立的基础，下面结

合软件测试的应用构建形式背景。

软件分为文档和代码，软件测试是对软

件的文档和代码正确性进行考核，按照测试流

程分为文档审查、静态分析、代码审查、单元

测试、部件测试、配置项测试和系统测试。软

件质量评价的一项指标是千行缺陷率，选择一

个基准的缺陷率（如取2.39，根据软件重要度

级别可以自行调整该值）。选择对象集为所有

待评价的软件，属性为各个测试阶段的千行代

码缺陷率，缺陷率大于基准缺陷率则表示该对

象具备该属性，按照此规则建立形式背景。

根据生成的形式背景，按照形式概念分

析规则生成对应的哈斯图，再提取出概念，根

据生成的概念格可以对软件质量进行评价。

对应的哈斯图中越往底层表明在软件测

试各个不同的阶段发现的问题越多，越往上层

表明软件的质量越高，同一个概念中的对象的

软件的缺陷率是接近的。当对软件测试的某一

个阶段的缺陷比较关注时，可以根据概念格中

的关系获取对应的某一个概念。此方法对于海

量的软件质量对比评价中具备很大的优势。

3 举例

建立形式背景如表1。

表1：对象- 属性集

a b c d e

1 1 1 0 1 1

2 1 1 1 0 0

3 0 0 0 1 0

4 1 1 1 0 0

表1 中：对象集为{1,2,3,4} 分别表示4

个不同的软件，属性集为{a,b,c,d,e} 分别表示

软件测试流程中不同的阶段，对于每一个软件

当在不同的阶段发现的问题缺陷率大于等于基

准缺陷率时则表示该对象具备该属性，如：软

件1 在a 阶段千行代码缺陷率大于等于2.39（可

根据需要调整缺陷率）则对象1 具备属性a，

对应的形式背景中值取1，否则取0。

根据表