面向缺失数据的动态特征选择

王 锋，宋 鹏

1(山西大学 计算机与信息技术学院，太原030006)2(山西大学 经济与管理学院，太原 030006)

1 引 言

随着各种数据观测和数据获取工具的更新和迅速发展，使得数据库中数据更新的速度越来越快，同一时刻有大量数据发生变化.尤其目前在大数据背景下，数据更新的速度和规模都在发生着巨大的变化，这对如何高效地从更新后的数据中获取知识带来了全新而巨大的挑战.数据挖掘技术旨在研究如何从数据中挖掘潜在的信息，即发现知识.面对快速更新的动态数据集，探索和发展高效的可有效处理动态数据集的数据挖掘技术也已迅速成为目前数据挖掘研究中的一个热点问题[1,2].

数据挖掘技术的探索中表明，对数据进行有效的预处理可进一步方便或加快数据中知识的获取.特征选择作为一种常用的数据预处理技巧已经被广泛用于许多实际应用领域中，如：图像检索，入侵检测以及文本分类等[3-8].随着对动态数据挖掘技术的分析和探索，面向动态数据集的有效特征子集的选取也引起研究者的关注，且随着研究的逐步深入，目前已经取得了一系列的研究成果.针对数据集规模的不断增大，Liu基于引入布尔矢量到特征表示中，提出了一种针对无类信息数据的增量式特征选择更新算法，是一类无监督的特征选择算法[9].Orlowska和Yang等基于粗糙集理论，分别设计了面向有类信息数据集的一种增量式特征选择算法[10,11].Liang等通过分析三种常见信息熵的增量式更新机制，一种基于信息熵的特征选择的组增量更新算法，即该算法可一次处理一组新增的数据集[12].针对数据集维数的动态更新，Wang等设计了一种维数增量式特征选择处理机制，当给定数据集增加一个特征集后，该算法可高效地求解到维数增加后的有效特征子集[13].针对数据表中数据取值的动态更新，Wang等基于粗糙集理论和信息熵的概念，提出了一种可有效处理数据取值动态变化的特征子集更新算法[14].在该算法的基础上，Zhang等发展了一种可有效处理一批数据取值发生变化特征选择更新机制[15].

实际应用中数据取值缺失的现象是广泛存在的，为此众多研究者已经提出了一系列面向含有缺失数据的数据挖掘算法和技术[16,17].其中针对面向含有缺失数据的特征选择的研究也取得了可观的成果.随着面向动态数据集特征选择技术的深入探索，如何高效地求解含有缺失数据的动态数据集的有效特征子集也成为了特征选择研究中的一个重点研究问题.Wang等通过分析含有缺失数据的数据集中新增数据后，信息熵的单增量和组增量更新机制，通过重新定义特征重要度，提出了一种面向含有缺失数据数据集的组增量特征选择更新算法[18].本文针对数据取值动态更新的含有缺失数据的数据集，基于粗糙集理论和信息熵的概念[19-21]，设计了一种面向缺失数据的动态特征选择算法.为有效求解数据集更新后的特征子集，本文中首先讨论并分析了当数据取值变化后，数据集上互补信息熵的更新机制，并重新定义了特征重要度.在此基础上，设计了基于信息熵的动态特征选择算法.为进一步验证本文提出特征选择算法求解过程中的高效性以及其选择结果的有效性，实验分析中选取了4组UCI中含有缺失数据的数据集进行仿真实验，并分别与基于信息熵的经典算法进行了比较，实验结果进一步验证了新算法的高效性和可行性.

2 基本概念

本节中以粗糙集理论为背景介绍含有缺失数据的数据集的相关符号表示.

对给定的数据表，粗糙集理论中令S=(U，C∪D)表示一个数据表，其中C表示数据表的特征集，D表示数据表的类信息，U是数据表的论域.对任意的a∈C，有a:U→Va，其中Va是特征a的值域，即对任意的a∈C，x∈U有f(x，a)∈Va，其中f(x，a)是一个信息函数，它对数据表中每个对象的每个特征赋予一个具体的值.如果至少有一个特征a∈C使得Va中含有空值，即表示数据表S中含有缺失的数据取值，粗糙集中称该类数据表为非完备数据表，并使用*表示数据表中的空值，即缺失掉的数据取值.

粗糙集理论中，设P⊆C，由P诱导的相容关系定义为：

SIM(P)={(x，y)∈U×U|∀a∈P，f(x，a)=f(y，a)或f(x，a)=*或f(y，a)=*}.

在此基础上，令SP(x)={y∈U|(x，y)∈SIM(P)}表示与数据对象x可能不可区分的数据的最大集合.U/SIM(P)是数据表上的一个分类，其中的每个元素称为相容类.

定义1.令S=(U，C∪D)是一个含有缺失数据的数据表，P⊆C，则互补信息熵的条件熵定义为

上述信息熵的定义见文献[17].

3 信息熵更新机制

对于含有缺失数据的数据集，本节主要介绍上述信息熵随数据取值动态变化的更新机制.通过分析给定数据集中数据取值发生变化的数据对象所在的相容类的变化，在本节中分析并证明互补信息熵随数据对象取值变化的更新机制，具体介绍如下.

定理1.令S=(U，C∪D)是一个含有缺失数据的数据集，P⊆C，且有U/SIM(P)={SP(x1)，SP(x2)，…，SP(x|U|)}和U/SIM(D)={SD(x1)，SD(x2)，…，SD(x|U|)}.论域U上D关于P的互补信息熵记为EU(D|P).当数据对象x∈U的取值发生变化，变化为x′.设与原数据x在特征集P上满足相容关系的数据集为X，在D上与x满足相容关系的数据集为Y，与变化后的数据x′在P和D上满足相容关系的数据集分别为X′和Y′.则论域U上新的互补信息熵为

E′(D|P)=EU(D|P)+Δ，

证明：当数据对象x的变化为x′后，论域中与x和x′满足相容关系的数据主要由分以下几种情况讨论：

1) 对∀y∈U-X∪Y(或∀y′∈U-X′∪Y′)，x和y(或x′和y′)在P和D上均不满足相容关系；

2)对∀y∈Y-X(或∀y′∈Y′-X′)，x和y(或x′和y′)在D上满足相容关系，而在P上不满足相容关系；

3) 对∀y∈X-Y(或∀y′∈X′-Y′)，x和y(或x′和y′)在P上满足相容关系，而在D上不满足相容关系；

4) 对∀y∈X∩Y(或∀y′∈X′∩Y′)，x和y(或x′和y′)在P和D上都满足相容关系.

由于x的取值变化为x′可理解为先从给定数据集中去掉数据x再添加新数据x′.因此，证明过程中先证明从数据集中删除一个数据的信息熵更新机制，再分析向数据集中添加一个新数据的更新机制.当将数据x从数据集中删除后，假设l=|U-X∪Y|，U-{x}/SIM(P) ={SP′(x1)，SP′(x2)，…，SP′(x|U|)}，且U-{x}/SIM(D) ={SD′(x1)，SD′(x2)，…，SD′(x|U|)}，则数据集U-{x}上的互补信息熵为：

EU-{x}(D|P)

∩(SD(xi)-{x})|)-|X-Y|

-|X-Y|+

-2|X-Y|)

当数据集U-{x}中添加新对象x′后，令U′表示新数据集U-{x}∪{x′}，则根据文献[18]中定理1可得U′上的互补信息熵为：

因为|U|的值和|U′|的值是相等的，所以上述计算公式可进一步表示为：

由定理1可得，当给定数据集中有数据的取值发生变化后，通过分析与该数据变化前后满足相容关系的数据子集，即可通过上述定理中的计算公式求解到数据集上新的熵值，降低了计算代价，提高了计算效率.

4 动态特征选择算法

基于定理1中对信息熵随数据取值更新的分析和证明，本节中基于信息熵的概念重新定义了特征重要度，并在此基础上设计了一种面向数据取值动态更新的特征选择算法.

4.1 特征重要度的度量

定义2.令S=(U，C∪D)是一个含有缺失数据的数据集，P⊆C，对任意特征a∈P的特征重要度定义为

Sigin(a，P，D)=E(D|P-{a})-E(D|P)，

而任意特征a∈C-P的特征重要度定义为

Sigout(a，P，D)=E(D|P)-E(D|P∪{a}).

上述定义中的Sigin(a，P，D)和Sigout(a，P，D)在粗糙集理论中分别称为内部重要度和外部重要度.其中内部重要度主要用于检测特征子集中的冗余特征，即相对于当前特征子集不重要的特征，如果内部重要度为0(或小于给定阈值)，则被认为是冗余特征；外部重要度主要用于当前特征子集不满足结束规则时，向当前特征子集中添加新的重要特征，在搜索过程中通常选择外部重要度最大的特征添加到当前特征子集中.

4.2 面向含有缺失数据的动态特征选择算法

基于第3节中信息熵的更新机制和4.1节特征重要度的度量，本节中介绍一种可有效处理含有缺失数据的数据集中数据取值动态更新的动态特征选择算法，算法步骤介绍如下.

算法1.一种面向含有缺失数据的动态特征选择算法(DFSM)

输入：含有缺失数据的数据集S=(U，C∪D)，U上的特征选择结果R，数据对象x取值更新为x′；

步骤1.B←R，计算X和Y：∀y∈U，如果x与y在B上满足相容关系，则X=X∪{y}，如果x与y在D上满足相容关系，则Y=Y∪{y}；

步骤2.计算X′和Y′：∀y∈U′，如果x′与y在B上满足相容关系，则有X′=X′∪{y}，如果x′与y在D上满足相容关系，则Y′=Y′∪{y}；

步骤3.whileEU′(D|B)≠EU′(D|C)do

{∀a∈C-B，计算其外部重要度Sigout(a，B，D)；

选择外部重要度最大的特征a0=max{Sigout(a，B，D)}，a∈C-B；

B←B∪{a0}；

}

步骤4.∀a∈B执行

{计算其内部重要度Sigin(a，B，D)；

如果Sigin(a，B，D)=0，则B←B-{a}；

}

当给定含有缺失数据的数据集中有数据的取值被更新后，使用上述算法可快速求解到新的特征选择结果，有效节省了重新计算的计算代价和耗时.算法1中的步骤3的操作是向当前特征子集中添加新的特征，步骤4的操作是检测特征选择结果中的冗余特征.

算法DFSM的计算时间复杂度分析：根据定理1，当有一个数据对象的取值被更新后，计算新的信息熵的时间复杂度是O(|U||C|+|X||Y||C|).则有算法步骤1-3的时间复杂度是O(|U||C|2+|X||Y||C|2)；步骤4的时间复杂度是O(|U||C||B|+|X||Y||C||B|)；所以算法总的时间复杂度是O(|U||C|2+|X||Y||C|2).

5 实验分析

为验证动态特征选择算法DFSM的有效性，本节中选取了4组UCI数据集(见表1)进行测试.程序运行的个人计算机配置为CPU Inter(R) Core(TM) i7-6700，3.40GHz，内存为8.00GB，操作系统是Windows 7.程序开发平台是 Microsoft Visual Studio 2005，编程语言为C#.

表1 实验数据集Table 1 Data sets for experiments

为有效验证算法DFSM的有效性，对表1中的每组数据集，实验中选取40%数据作为取值发生变化的数据子集.当每组数据集中部分数据取值被更新后，本节实验中分别使用算法DFSM和基于信息熵的经典特征选择算法[17]求解数据集上的特征选择结果.为进一步验证本文中新算法的性能，本节中引入了两个常见分类器(朴素贝叶斯和决策树)来测试上述两个算法特征选择结果的分类精度.特征选择结果的分类精度和计算时间见表2，其中NBC表示朴素贝叶斯分类器，C4.5表示决策树，N为选择到的有效特征个数，IFS表示面向含有缺失数据的基于信息熵的粗糙特征选择算法[17].

表2 特征选择结果比较Table 2 Comparison of feature subsets

为进一步验证算法DFSM的高效性，对表1中的每组数据集，依次选取其中的10%，20%，30%，40%，50%规模的数据并更新其数据取值.然后分别使用算法DFSM和IFS来计算数据取值发生变化后的新数据集上的特征选择结果，上述两个算法的计算时间见图1-图4，其中x轴表示10%-50%数据取值被更新的不同规模，y轴表示计算时间.

图1 Backup-large的计算时间Fig.1 Computational timeof Backup-large图2 Cancer的计算时间Fig.2 Computational timeof Cancer

图3 Mushroom的计算时间Fig.3 Computational timeof Mushroom图4 Shuttle的计算时间Fig.4 Computational timeof Shuttle

由表2和图1-图4的实验比较结果可得，与经典的基于信息熵的粗糙特征选择方法相比较，本文中的新算法在求解特征选择过程中明显降低了计算耗时，提高了计算效率.而且，求解到的特征子集的分类性能并未降低.由图1-图4中计算时间的比较可进一步得到，随着取值被更新的数据子集规模的不断增大，本文新算法都能节省大量的计算时间，高效性非常明显.因此，本节中实验结果表明，算法DFSM可在更短的时间内求解到一个有效的特征子集.

6 结 论

数据观测和数据获取工具的更新和迅速发展，使得可有效处理动态数据集的数据挖掘技术引起众多研究者的广泛关注.本文以含有缺失数据的数据集为背景，通过分析并证明信息熵的更新机制，发展了一种基于信息熵的动态特征选择算法.实验分析进一步验证了当给定数据集中的部分数据取值被更新后，新算法在节省大量计算耗时的同时，可求解到一个有效的特征子集.海量高维的数据集中经常存在着大量的过时而冗余的数据，为进一步提高信息获取的时效性，可考虑直接将这类无效的数据更新为最新的取值，再进行知识获取.这样既可节省大量存储空间，也可基于原有的信息获取结果发现新的知识.本文的算法为探索数据取值动态更新的数据挖掘技术提供了新的思路和可以借鉴的研究途径.