数据挖掘在软件工程中的应用

心郁郁 贡献于2013-11-05

作者 yongbao  创建于2013-10-19 06:59:54   修改者  修改于2013-10-31 04:20:00字数9619

文档摘要:数据挖掘在软件工程中的应用摘要随着软件系统的规模和复杂性日益增长,软件开发已经演变成一项复杂的系统工程。软件工程中的对象、活动和过程更加难以控制和管理,因此该领域原有的经验直觉型的处理模式已经不能适应新的需求,而数据挖掘技术的引入为实现知识智能型软件工程提供了重要契机。以软件工程领域中的数据对象为主线,对在程序代码分析、故障检测、软件项目管理、开源软件开发等软件活动中所运用到的数据挖掘技术进行了系统的介绍和归纳,并在每一环节作了方法间的优劣性对比分析。
关键词:

 数据挖掘在软件工程中的应用 摘 要 随着软件系统的规模和复杂性日益增长,软件开发已经演变成一项复杂的系统工程。软件工程中的对象、活动和过程更加难以控制和管理,因此该领域原有的经验直觉型的处理模式已经不能适应新的需求,而数据挖掘技术的引入为实现知识智能型软件工程提供了重要契机。以软件工程领域中的数据对象为主线,对在程序代码分析、故障检测、软件项目管理、开源软件开发等软件活动中所运用到的数据挖掘技术进行了系统的介绍和归纳,并在每一环节作了方法间的优劣性对比分析。 关键词 数据挖掘、软件工程、软件项目管理 Abstract With rapid increase of the size and complexity of software system, software development has evolved into a complex and systematic engineering. The objects,activities and processes in software engineering will to be controlled even more with difficulty , so the traditional modes, such as treatment wit h experience and intuition, a re unable to adapt properly to the new requirements. However, the introduction of data mining techniques can promote the development of knowledgeable and intelligent software engineering. In the perspective of the data to be mined in software engineering field,the paper systematically described and summarized the data mining techniques adopted in the activities such as program code analysis, fault detection, software project management, and open source software(OSS) development. The comparison analysis about these techniques is also addressed in each section. Key words Data mining, Software engineering, Software project management 1 历史和发展现状 数据挖掘(DM)就是从大量的、不完全的、有噪声的、模糊的实际应用数据中,提取隐含在其中的、人们事先不知道的,但又是潜在有用的信息和知识的过程。软件工程(Software Engineering,简称为SE)这个概念,在1968年NATO(北约)的科技委员会召集的讨论和制定关于摆脱“软件危机”的会议上第一次被提出。软件工程是一门研究用工程化方法构建和维护有效的、实用的和高质量的软件的学科,其目标是在给定成本、进度的前提下,开发出满足用户需求的软件产品。 在软件工程领域,通过数据挖掘可以从软件工程数据库(例如源代码库,程序执行记录,版本信息记录,漏洞数据库等)中挖掘出有价值的信息,这些信息可以帮助我们预测系统漏洞,定位系统故障,寻找代码间的依赖关系,了解项目状况,项目进度,进行成本评估等等。 数据挖掘技术在软件工程领域的应用可追溯到上世纪90年代初,当时主要是用以发现一些可复用的代码。但随着软件系统复杂性的快速增长和数据挖掘技术的日益更新,极大地促进了该项技术在软件工程领域的广泛应用。从上世纪 90 年代末起 ,逐渐有软件工程或数据挖掘领域的学者从事这方面的研究,并通过实例证实数据挖掘技术是实现低成本、高效率完成软件工程任务的有效解决方案。 直至目前,诸如ICSE, ISSTA, ASE, FSE, KDD 等顶级国际会议专门开设了相关议题;从2004年起挖掘软件资源库( mining software repositories, MSR) 研讨会的成功召开标志着该方向已成为软件工程的一个重要研究分支。 数据挖掘技术在软件工程中的应用主要是采用有效的分类、聚类、预测和统计分析技术从各种软件资源库中发现潜在的知识、规则等用以反馈指导软件工程活动,以达到改进软件产品质量、提高开发效率的目的。以软件工程领域中的数据对象为主线,系统地介绍和对比了在程序代码分析、故障检测、开源软件开发等软件活动中所运用到的数据挖掘技术。 为了提高软件的生产效率和质量,软件工程师越来越多的数据挖掘算法应用到软件工程领域中。然而,挖掘软件工程中的数据面对一些挑战。软件在商业、政府和社会中占据着一个重要的角色,提高软件生产效率和质量就成为软件工程中的一个重要目标。挖掘软件工程中的数据最近成为一个有前途的手段实现这一目标,有两个主要趋势:数据的大量增加和它的有助于帮助解决真实的世界。 一般的软件版本控制系统如:分布式版本控制系统和集中式版本控制系统使软件工程不仅获得了当前项目代码的快照同时也维持了所有的版本历史信息。完成生命周期的故障管理也可能通过使用故障跟踪系统,如:Bugzilla。此外,丰富的执行数据是可用的强大的仪器仪表工具,如微软的沃森博士技术,所使用的软件开发商和轻量级监控工具,为最终用户进行了优化。版本控制系统 (如CVS, SVN, Visual SourceSafe等)有利于程序修改的有序性 、可回溯性以及全局统一性等,目前软件开发企业或开源组织基本上均会采用它来组织多参与者或分布式的软件开发活动。当前在版本控制信息上挖掘应用大多是挖掘软件变更历史的,并用以发现不同程序模块(子系统)间的逻辑依赖,预测程序故障的引入方式,或是预测今后的变更可能。通过上述挖掘活动,将有利于降低系统后期维护代价,便于系统逆向分析和前瞻性地预防一些因变更而引入的故障。 软件工程数据涉及到3P:人员,过程和产品。人员包括软件开发人员,测试人员,项目经理,以及用户。过程包括不同的开发阶段和活动,如需求,设计,实现,测试,调试,维护和部署。产品可以是结构化的,如源代码(包括生产和测试代码),或非结构化的,如文件和错误报告。 如表1的第一列显示软件工程的数据可以大致分为: l 序列:如执行追踪在运行时收集来自源代码的静态追踪和共同改变的代码位置; l 图:如图在运行时动态调用和图从源代码中提取静态调用; l 文本:如错误报告,电子邮件,代码注释和文档。 表1 软件工程数据、挖掘算法、软件工程任务的例子 软件工程数据例子 挖掘算法 软件工程任务 序列: 执行/静态追踪,共同的变化 频繁项集/序列/部分阶挖掘, 序列匹配/聚类/分类 编程,维护,错误检测,调试 图:动态/静态调用图, 程序依赖图 频繁子图挖掘,图形匹配/聚类/分类 错误检测,调试 文本:错误报告,电子邮件,代码注释,文档 文本匹配/聚类/分类 维护,错误检测,调试 为了提高软件生产率和质量,软件工程师正越来越多地应用数据挖掘算法各种软件工程任务。例如,利用这种算法可以帮助工程师弄清楚如何调用由一个复杂的不足文档库或框架提供的API方法。在维护方面,这种算法可以协助确定代码位置时,必须改变另一个代码的位置改变。软件工程师还可以使用数据挖掘算法,寻找潜在可能会导致未来的现场故障的缺陷,以及确定已经知道的故障运行的代码行(LOC)。在表1中的第二列和第三列的几个例子数据挖掘算法和软件工程师适用他们的任务。 2 挖掘过程及挖掘技术 2.1 挖掘过程 一个典型的数据挖掘过程有四个步骤:选择,预处理,挖掘和吸收。在软件工程中,由这四个步骤组成的数据挖掘过程由图1所示。数据挖掘的过程通常是具有高度交互性。挖掘过程中有时需要重新考虑数据的选择,有时需要对改进数据的预处理,有时算法需要被频繁地调整。由于这一特性,数据挖掘过程中有反馈环(feedback loops)。 挖掘到的信息 被选择的过程和产品数据 格式化的数据 软件工程数据 知识 吸收 挖掘 预处理 选择 图1 软件工程中的数据挖掘流程 在软件工程中进行数据挖掘的第一步工作是将软件管理和工程的目标映射到一个或多个数据挖掘任务上。数据挖掘的工作可以被大致划分为以下六类: 1)评估和预测:评估包括对软件实体集(包括产品、过程和资源)中属性的检查,以及基于这些属性值对需要量化的未知属性进行赋值。预测经常是在评估完成后被用来预测属性值的未来结果。 2)分类:分类包括检查一个给定实体的属性,以及根据这些属性值将其指派入某一预先定义的范畴或类别。 3)关联发现:关联发现是识别一个给定环境中相互关联的属性。例如找出在软件开发团队中哪些属性和最终的软件产品属性相关联。 4)聚类:聚类就是将一个异构群体划分到一个较为同构的子群的集合的工作。它划分各个类的依据是类成员之间的相似性。 5)数据可视化:数据可视化就是通过可视化的表示方式来描述复杂信息的工作。 6)可视数据探察:作为对可视化数据描述工作的扩展,可视数据探察是通过对可视化表示的交互控制来检视大量数据。它使用了具有高级用户界面和交互数据查询资源的可视化数据挖掘工具来处理被考察的数据。 以上六类数据挖掘任务是处于知识发现工作的不同层次上的。分类和预测任务的目的是建立可以为软件组织所用的明确的模型:关联发现和聚类任务的目的是自动识别数据中有用的模式:可视化和可视数据探察的目的是帮助专家们方便地寻找数据中的有用模式。这些任务定义了数据探究和知识发现的三个层次(如图2所示)。 模型构建 自动模式提取 交互式可视数据探查 图2 软件工程中的图形挖掘层次 由图2可以看到,这三个层次是密切相关的。它们可以被看作一个金字塔,可视的数据探察为模式提取和模型构建提供了基础。数据探察和模式提取是帮助领域专家及时了解由软件组织监控的数据的改变的工具。这三个层次对于一个软件组织来说都是非常重要的。 2.2 挖掘技术 常用的数据挖掘技术包括:分类树、关联发现、聚类、人工神经网络、最优集合规约、贝叶斯信念网络和可视数据挖掘等。我们已经清楚地认识到软件度量数据常常是具有多维度的,并且有着的高度耦合和冗余。软件工程数据挖掘中用到的特殊技术包括统计分析、回归建模、分类树和神经网络等。在具体的软件工程实践中,选用哪种数据挖掘技术取决于软件工程专家的目标和为达成这些目标而想完成的任务。 3 挖掘方法 软件工程数据 4 3 1 采用/调整/开发挖掘算法 处理数据 收集/调查 软件工程数据 2 2 5 判定软件工程任务 后处理/应用挖掘结果 软件工程任务 图3 挖掘软件工程中的数据方法涉及到五个基本步骤。在实践中,软件工程师同时采用的前两个步骤。 图3显示出五种挖掘软件工程数据的主要步骤。软件工程师一开始可以采用问题驱动方法(知道什么是协助软件工程任务)或者采用数据驱动方法(知道什么是挖掘软件工程数据),但在实践中,他们普遍采用两个步骤:收集/调查数据挖掘及协助确定软件工程任务。其余三个步骤,顺序,预处理数据,采集、调整、开发一个挖掘算法和后处理、应用挖掘的结果。 预处理数据的涉及第一个从相关原始的软件工程数据提取相关的数据。例如:静态方法调用序列或调用图的源代码,动态方法调用序列或调用图执行的痕迹,或字序列的错误报告摘要。该数据进一步预处理清洁和正确格式化的挖掘算法。例如:输入格式的序列数据可以是每个序列是一系列事件的数据库。 根据来自前两个步骤中的挖掘要求,下一个步骤是生成一个挖掘算法及其配套工具。在一般情况下,挖掘算法主要分为四类: l 频繁模式挖掘:发现通常出现的模式; l 模式匹配:调查给定模式的数据实例; l 聚类:分组数据到集群; l 分类:预测标签数据基础上的已标记的数据。 最后一步是转换挖掘算法的结果到适当格式需求协助的软件工程任务。例如:在预处理阶段,软件工程师取代每一个不同的方法调用一个唯一的序列数据库符号进入数据挖掘算法。然后挖掘算法表征这些符号频繁模式。在后处理中,工程师改变每个符号对应的方法调用。当应用频繁模式挖掘,这一步也包括寻找相匹配的挖掘模式的地点。例如,在编程或维护中的协助,并寻找违反了挖掘的模式的地点,例如,在错误检测中的协助。 4 数据挖掘的挑战 挖掘软件工程数据提出来一些挑战。 4.1 软件工程的独特需求 众所周知,大多数软件工程数据挖掘的研究依赖于公开可用的工具,如关联规则挖掘和聚类。黑盒复用的挖掘工具可能危及软件工程拟合工具的不良功能独特的要求。此外,许多这样的工具都是通用的,应适应协助手边特定的任务。然而,软件工程研究员可能缺乏适应或开发挖掘算法或工具的专业知识,而数据挖掘的研究人员可能会在软件工程领域缺乏了解挖掘的要求。一个有希望的方式来缩小这种差距是软件工程社区(要求供应商)和数据挖掘社区(解决方案提供商)之间建立紧密的合作。 4.2 复杂的数据和模式 软件工程研究者通常挖掘个人的数据类型,独自完成一定软件工程的任务。然而,软件工程的任务要求越来越采矿多个相关的数据类型,包括序列和文本数据,以及以得到最有效的结果。即使对于一个单一的数据类型,丰富的信息通常不仅与一个单独的数据项相关,而且还与多个数据项之间有联系。此外,在软件工程领域的模式表示可能很复杂。有可能是生产所需的图案表示没有现有的挖掘算法,对这样的表示开发新的算法可能会很困难。总体而言,确保可扩展性尚未表现挖掘解决方案是困难的。 4.3 大规模数据 软件工程研究者往往只挖掘少数本地资源库。然而,在这些资料库中有可能是太少的相关数据点,以支持挖掘的理想模式,如API方法之间的调用。解决这个问题的方法之一是挖掘大规模互联网的软件库,例如,通过代码搜索引擎。数据挖掘可以被应用到整个开源世界或一个组织内或跨组织的许多软件库。此外,执行甚至从一个平均大小的程序收集的痕迹可以很长,动态或静态提取的调用图可能是巨大的。如此大规模的数据分析对现有的挖掘算法提出了挑战。 4.4 及时挖掘 软件工程研究者通常进行离线挖掘已经收集和储存的数据。然而,在现代综合软件工程环境中,特别是协作环境中,软件工程师必须能够收集和挖掘软件工程数据提供快速的时间反馈。可以适应或开发流数据挖掘算法和工具,以满足这些具有挑战性的挖掘要求。 5 挖掘软件工程数据 5.1序列挖掘 例如软件工程序列数据包括方法调用序列,无论是从程序源代码中动态的收集还是在程序执行过程中静态的提取。动态收集方法调用序列的形式执行的痕迹。动态收集方法在调用序列的形式是执行跟踪。 常见类型的挖掘算法包括频繁模式挖掘,例如,频繁项集,序列,或部分阶挖掘,以及序列匹配,聚类,分类。频繁模式挖掘可用于挖掘API调用使用模式以帮助编程或以帮助在错误检测中的规格。不同的算法生成的模式反映不同层次的信息,算法的选择取决于特定软件工程任务的挖掘要求。例如,关联规则频繁项集不反映开采模式中的元素之间的顺序信息,而频繁序列或部分顺序则反映。序匹配通过寻找合适的位置用来检测潜在的错误,但不完全匹配挖掘的序列模式。已经开发了新的解决的独有特性SE数据挖掘算法。这些算法包括挖掘迭代模式,时间规则,序列图,有限状态机(FSM),和序列的关联规则。 5.1.1 迭代模式挖掘 现有顺序模式挖掘算法在跟踪(序列)忽略重复项(方法调用)和在软件工程中丰富的属性规范语言语义是不可知的。为了解决这个问题,我们已经开发了一种算法,捕获重复出现在每次跟踪和跨越的多个痕迹的图案。 请考虑以下的序列数据库: 1 A B C D E F A X B C 2 A G X B C 3 A X B C 我们的算法挖掘一套频繁封闭的迭代序列模式,在最小支持度阈值4,{}.当前频繁序列挖掘算法会忽略第二次出现或重复序列1中的这种模式,因此不能挖掘这种模式。 我们已经应用迭代模式挖掘收集来自JBoss应用服务器的事务组件收集的痕迹。挖掘必须遵循的模式范围小、经常出现的模式,如“锁开锁”更长的模式,超过30个方法调用模式。我们还表明,挖掘的迭代模式可以作为高层次的功能进行程序行为分类。 5.1.2 序列图和有限状态机挖掘 我们已经开发出算法来挖掘其他形式的API规范,包括顺序图和序列的有限状态机。这些规范捕捉了难以表达的使用模式和规则的约束。例如,一个UML序列图中不仅包含方法调用,但也显示为生命周期的主叫方和被叫方信息。此外,规则和模式不是表达背离,从而无法捕捉到分支和循环行为与有限状态机的表达。规则和策略经常被用来表达强烈的观察属性。 5.2 图挖掘 例如:软件工程图形数据包括静态或动态调用图以及边表示数据或控制的依赖和节点代表语句程序依赖图。针对各种表述的评价程序执行整个程序(例如,在if和while语句),所以执行可以被建模为静态调用图的遍历,导致动态调用图。图挖掘算法的常见类型包括频繁子图挖掘、图形匹配、图形分类、图聚类。频繁子图挖掘可用于发现程序规则,表现为频繁子从代码库中提取的程序依赖图,而图匹配几乎可以用来找到位置,但不完全匹配开采子图对应潜在的错误。 已经开发出了新的图挖掘算法,包括歧视性的图挖掘和图形分类,以帮助程序调试。 5.2.1 判别图挖掘 检测的程序运行一组测试案例会产生两种结果:一个相应的纠正执行通过的测试用例和其他错误执行失败的测试用例。踪迹中的每一个都可以是“卷曲”,形成动态调用图。调用图中的一个节点对应的方法调用,图中的一个过渡对应的方法调用之间的各种关系。例如,一个方法返回后立即调用另一个方法,一个方法调用了另一个。这种卷取会产生两种动态调用图。我们也可以建立一个类似的没有任何跳跃在程序执行基本块的语句序列的图形。 为了提取功能,在子图的形式中,即区分的两种动态调用图,我们已经开发了一种算法挖掘前k个最有特征的图形。这些图表作为签名和错误发生的背景下,有可能帮助软件工程师的定位和固定错误。我们的基准数据集上的实证结果显示,平均74%的精确度和91%的召回在方法层面,平均59%的精确度,在基本块级和73%的召回。 5.2.2 图形分类 执行一个错误的动态调用图有时会偏离正确执行。了解在什么时候出现的分歧将揭示潜在错误的位置。考虑到调用图看起来正确和错误之间的执行大致相同直到走过的地方是相同的,我们利用增量的分类去检测被触发的位置。具体来说,我们在不同的执行点建立一个支持向量机分类的基础桑动态地调用图表,直到程序被执行,分类的准确度将直观地保持在低水平。因此,通过提升检测的准确性,我们可以判断错误的位置。为了去分类动态调用图,我们已经开发了一个封闭的表示由一系列基本子图表的图形挖掘算法。 5.3 文本挖掘 例如软件工程文本数据包括错误报告,电子邮件,代码注释,API方法的文档。共同关注的一个单元是一个在序列数据库中相似的序列的序列数据的文本文件。 文本挖掘算法的常见类型包括文本聚类,分类和匹配。文本聚类应用示例包括集群错误报告检测重复的错误报告和从而减少检查力度,并指派特定的开发商,修正错误的报告。文本分类中的应用示例包括根据旧的错误报告对过去分配到一个特定的开发商的建议分配一个新的错误报告。例如文本匹配应用,包括搜索关键字的代码注释,API文档,或错误报告,检测重复旧报告中一个给定的错误报告。 我们已经开发出一种方法,有助于避免重复的错误报告分配到不同的开发商的重复错误报告检测。我们举例说明的办法有两个例子,使用Firefox的错误库的报告。 例子: 考虑下面总结性文件的错误: 219232错误:随机“不包含任何数据的文件。”警报 244372错误:“不包含任何数据的文件”纽约时报的文章后续页面的消息。 为了检测244372错误是在所有现存的报告重复的219232错误,我们把每个概要文件作为一个n维向量,其中,n是在所有的文件和每个索引词(字)的数量唯一索引条款的一个权重。该指数的矢量值,计算基于以下的条件:如果索引项出现更多的文档,它比那些出现更少的文档获得更少的权重,因为t是不是一个很好的鉴别在跨文档。向量转换文档之前,我们使用普通的自然语言处理(NLP)技术,例如去除携带有点意思的停止词话,如“开”或“关”的244372错误摘要。以改造后的文件为载体,我们在现有错误的汇总文件中计算每个错误报告的摘要文件,通过一个公式来定义两个向量的相似性244372错误的相似性。我们的结论确定错误219232和 错误244372具有最高相似性。因此,这将标志着错误244372作为一个潜在的重复219232错误。 软件工程数据量巨大,增长为今后的研究提供了很多机会。集成附加的比较有效的数据挖掘工具,解决实际的软件工程问题进入流行的软件工程环境,例如:Eclipse和Microsoft Visual Studio将有利于在软件工程广泛采用的数据挖掘解决方案。 然而,这个长远目标并不是没有障碍。目前,大量的工作需要做进一步适应通用的挖掘算法或制定具体的算法,以满足独特的软件工程的数据和任务的要求。另外,可以受益于数据挖掘的软件工程任务范围必须扩大以及可以被挖掘的软件工程的数据。 在模式挖掘领域中,增加了可扩展性的挖掘算法和挖掘结果的表达性需要获得重要的掘金以后,可以被输送到下游软件工程工具来执行各种软件工程任务的知识。在分类领域,更准确的分类软件工程任务是可取的。在模式匹配领域,更高效的近似匹配算法可以帮助软件工程数据分析规模巨大的延伸到十亿LOC,随着时间的推移积累错误报告,并通过互联网或内联网共享的。 结束语 随着软件系统日趋复杂、涉众(stakeholders) 增多以及技术不断更新 ,软件开发已经演变成一项复杂的系统工程。相应地,软件工程也变成一个“计算型”的工程学科。在该项活动中原有的靠单个人员的决策行为已经不复存在,更多的则是对软件项目数据进行挖掘、分析和智能处理的基础上进行“ 量化”管理。本文以软件开发活动中形成的数据集为对象,对其上实施的挖掘技术及其主要用途进行了系统的归纳与总结,旨在给国内的同行以适当的借鉴。不难看出,数据挖掘领域的主要技术均能在软件工程实践活动中找到应用之处,并产生了一定的获益。但由于软件工程中数据形式、管理方式和多重影响因素等原因,数据挖掘技术在该领域的应用研究尚处于初步发展期,还有很多工作值得进一步深入探究。例如,(1)结合自然语言处理及语义分析的软件项目文档挖掘;(2)软件特征准确定位;(3)软件安全脆弱点的挖掘等。 参考文献: [1] Xie Tao, Thummalapenta S, Lo D, et al. Data mining for software engineering[J]. IEEE ,2009, 42: 55−62. [2] Quinn Taylor, Christophe Giraud-Carrier. Applications of data mining in software engineering.[J]. Data Analysis Techniques and Strategies, 2010 [3] J.L.Alvarez, J.Mata, J.C. Riquelme. Data mining for the management of software development process[J]. International Journal of Software Engineering and Knowledge Engineering, 1994 [4] 张帆,沈孙园. 浅谈数据挖掘技术在软件工程中的应用, 电脑知识与技术,2009 [5] 郁抒思,周水庚,关佶红. 软件工程数据挖掘研究进展, Journal of Frontiers of Computer Science and Technology, 2012 [6] 毛澄映,卢炎生,胡小华. 数据挖掘技术在软件工程中的应用综述,计算机科学, 2009.5 [7] 张志荣,黄 杰,孙伟宏,韩晓东,苏先名. 数据挖掘在软件工程领域中的应用浅析, 电子测试, 2013.5 [8] 数据挖掘/朱明编著.第二版 -合肥:中国科学技术大学出版社,2008.11 [9] 数据挖掘算法与应用/梁循编著. -北京:北京大学出版社,2006.4

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档