一种改进的ROUSTIDA数据填补方法

关莹苏贵斌康熠华

摘 要：针对数据稀疏度大的信息系统提出了一种基于序数属性相似度的不完备数据分析方法。通过采用差值替代等值的方式改进可辨识矩阵，从而实现填补稀疏度较大的信息系统的目的。弥补了原算法对于某些缺失值不能填充的情况，改善了其它改进方法对于序数属性处理不准确的缺点，并通过实验证明了改进后的方法可以更精确更有效地填充缺失值。

关键词关键词：不完备数据分析方法；可辨识矩阵；序数属性；粗糙集

DOIDOI：10.11907/rjdk.162011

中图分类号：TP301

文献标识码：A 文章编号文章编号：16727800（2016）011001203

基金项目基金项目：

作者简介作者简介：关莹（1993-），女，辽宁丹东人，内蒙古师范大学计算机与信息工程学院硕士研究生，研究方向为软件工程、数据挖掘；苏贵斌（1968-），男，黑龙江望奎人，内蒙古师范大学网络技术学院副教授、硕士生导师，研究方向为软件工程、数据挖掘；康熠华（1992-），女，内蒙古呼和浩特人，内蒙古师范大学计算机与信息工程学院硕士研究生，研究方向为软件工程、数据挖掘。

0 引言

计算机与网络信息技术的飞速发展，使得各领域的数据和信息急剧增加。在数据与信息系统不确定性日益显著，且采集到的数据往往包含着噪声甚至不完整的情况下，粗糙集理论应运而生。粗糙集理论是波兰数学家Z.Pawlak[1]于1982年提出的一种数据分析理论，作为一种研究不精确、不确定性知识的数学工具，粗糙集理论越来越受到重视。经过30多年的发展，该理论已经得到广泛应用，成为人工智能领域的研究热点。它的优点是无需提供除问题所需处理的数据集合之外的任何先验信息。

基于粗糙集理论的ROUSTIDA算法是一种处理不完备信息系统缺失值的常用算法，它利用可辨识矩阵找到与有缺失值的对象相似度最高的对象的属性值进行填充[2]。该算法的基本思想是：遗失数据值的填充应该使完备化后的信息系统产生的分类规则具有尽可能高的支持度，产生的规则尽可能集中[3]。由于算法本身具有一些缺陷，因此本文对该算法进行了改进，提出了一种面向序数属性信息系统的不完备数据方法，使得填充结果更准确、更有效。

1 ROUSTIDA算法

1.1 理论基础

定义1：令信息系统为S=，A={ai|i=1，…，m}是属性集，U={x1，x2，…，xn}是论域，ai（xj）是样本xj在属性ai上的取值。M （i， j）表示经过扩充的可辨识矩阵中第i行j列的元素，则经过扩充的可辨识矩阵M定义为[45]

1.2 ROUSTIDA算法描述

ROUSTIDA算法步骤如下：

当计算到S1后，算法满足结束条件，不再往下计算。因此S1为使用ROUSTIDA算法填充后的最终结果。此时信息系统中仍有部分缺失值没有被填充，且按照原算法采用平均值或最高频率值来进行填充会产生很大的误差，因此本文提出了改进方案。

2 改进的ROUSTIDA算法

2.1 算法描述

ROUSTIDA算法本身具有一些局限性。在算法的步骤2中，当有缺失属性的对象与任何对象都不相似，或与多个对象都相似且与之相似对象的相应属性值互不相等时，ROUSTIDA算法无法进行填充。并且，其对产生的噪声数据没有分辨能力，易受到噪声数据的干扰从而影响填充效果。在算法填充完成之前要对可扩充辨识矩阵、遗失对象集和遗失属性集进行多次更新，因此产生了大量的过渡数据，增加了算法的时间复杂度。本文提出的改进方法主要集中在以下两个方面：（1）根据序数属性之间的相似度进行改进。传统的ROUSTIDA算法忽略了序数属性之间的相似度，只有两个对象的各个属性完全相同才能进行填充。那么当对象的属性为序数属性时，属性级别越多，满足原算法条件的对象越少，也就越难以填充。实际上，在评分系统中，大部分属性级别数目为5，有的甚至为10，此时原算法的填充效率将大大降低。可以考虑，在寻找无差别对象时，适当放宽标准，使各属性级别的差值保持小于等于1（此差值根据信息系统实际情况进行改变），最后用总差值最小，也即最相似的对象的相应属性值进行填充。并且原始的ROUSTIDA算法以及现有改进方法都没有考虑到序数属性各级别之间的关系，序数属性的属性值之间也有一定的相似性，属性值越相近，两个对象就越相似。为了使用改进算法，重新定义可辨识矩阵M。定义3：令信息系统为S=，A={ai|i=1，…，m}是属性集，U={x1，x2，…，xn}是论域，ai（xj）是样本xj在属性ai上的取值。M （i， j）表示经过扩充的可辨识矩阵中第i行j列的元素，则经过扩充的可辨识矩阵M定义为：M（i，j）={ak|ak∈A∧|ak（xi）-ak（xj）|>1∧ak（xi）≠*∧ak（xj）≠*}其中，i，j=1，…，n；“*”表示缺失值。（2）针对原算法步骤2不能处理的情况进行改进。改进后的算法考虑找出与目标对象属性最相似的对象属性值进行填充。分别计算NS中的各个对象与目标对象属性值的总差值，总差值越小，对象之间的相似度越高。为了使用改进算法，作以下补充定义：定义4：令信息系统为S=，A={ai|i=1，…，m}是属性集，对任意xi，定义Ni={p|ap（xi）≠*，i=1...n}为对象xi属性不为空的集合。Nij={p|ap（xi）≠*∧ap（xj）≠*，i，j=1...n}为对象xi和xj属性都不为空的集合。定义5：令信息系统为S=，A={ai|i=1，…，m}是属性集，定义dj=∑p∈Ni|ap（xj）-ap（xi）|为用户xj与xi属性值的总差值。改进的ROUSTIDA算法如下：改进后的可辨识矩阵M：

2.2 实验分析

对表1实施改进后的ROUSITIDA算法结果如表3所示。

改进后的算法针对原算法不能处理的几种情况，分别提出了相应的解决策略，使得最终得到的信息系统更加完备化，填补的属性值更加准确。该算法主要针对具有序数属性的信息系统，考虑到了各属性值之间的相似性，扩充了原算法的适用范围，弥补了采用最多出现值或平均值填补缺失值带来的误差。

3 结语

本文对基于粗糙集的不完备数据分析方法（ROUSTIDA）进行了改进，在计算可辨识矩阵M时采用差值代替等值的方式，拓宽了对无差别对象的选择，大大提高了算法的填充效率，同时也具备一定的噪声数据分辨能力。实验证明，改进后的算法对于具有序数属性的信息系统有很好的填充能力。

参考文献：

[1] PAWLAK Z.Rough sets[J].International Journal of Computer Information Science，1982（11）：341356.

[2] 王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2001：4697.

[3] 田树新，吴晓平，王红霞.一种基于改进的ROUSTIDA算法的数据补齐方法[J].海军工程大学学报，2011，23（5）：1115.

[4] 丁春荣，李龙澍.基于相似关系向量的改进ROUSTIDA算法[J].计算机工程与应用，2014，50（13）：133136.

[5] 段鹏，庄红林，何磊，等.不完备数据分析方法（ROUSTIDA）的改进算法[J].计算机工程与设计，2009，30（7）：16811684.

（责任编辑：孙 娟）