基于形式概念分析的依赖簇检测方法研究  

Research on FCA Based Dependence Cluster Detection

作　　者：尚颖[1] 程克[1] 李征[1] 

机构地区：[1]北京化工大学信息科学与技术学院,北京100029

出　　处：《计算机科学》2017年第4期144-147,176,共5页Computer Science

基　　金：国家自然科学基金(61170082;61472025;61672085);教育部新世纪优秀人才计划(NCET-12-0757)资助

摘　　要：依赖簇是相互依赖的程序组件的最大集合,大尺寸依赖簇已被证实在程序中普遍存在。依赖簇中任意一点产生变动都会引起其他组件的连锁反应,进而对整个系统造成潜在的影响,这将会阻碍软件理解、测试、维护等方面的工作。检测出依赖簇是消除不良影响的前提,目前通过单调切片尺寸图近似检测依赖簇的方法的准确度较低,会出现漏报和误报。提出了一种基于形式概念分析的依赖簇检测方法,通过概念包含度选取的大型概念来检测大尺寸依赖簇,并进一步提出轻量化策略以有针对性地选取大型概念,降低计算开销。在12个不同规模和领域的开源程序上,将所提方法与单调切片尺寸图法进行对比实验,结果表明所提方法及其轻量化策略能够有效地检测大尺寸依赖簇,可以提高依赖簇检测的准确度和效率。Dependence cluster is a maximal set of program components that all depend upon each other.The current view is that large dependence cluster is extremely universal,which widely exists in all kinds of program source code.The existence of large dependence cluster may lead to the significant ripple effect,i.e.,a change to a certain point of the cluster will cause potential adverse effects on the rest of the cluster,which might affect the whole system.It has a negative impact on many different software engineering activities,including comprehension,testing and maintenance.Dependence cluster detection is a prerequisite for solving adverse effects caused by large dependence cluster.Previous researchers have proposed monotonic slice-size graph（MSG）based method to detect the same slice size of dependence cluster.However,the proposed method is of conservative approximation,which will cause false positives and false negatives.This paper proposed a technique to detect dependence clusters using formal concept analysis（FCA）,in which concept inclusiveness is defined to select large concepts.Furthermore,a light-weight computing strategy for FCA was proposed to compute large concept to decrease the computation cost significantly.Based on 12 open source subjects,the empirical comparison showes that the proposed technique can increase the detection accuracy of large dependence clusters with higher efficiency.

关 键 词：形式概念分析 概念格 依赖簇 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]