随着大数据时代的来临, 数据挖掘技术蓬勃发展.近年来, 由于不确定性数据比重的不断增大, 不确定性数据挖掘越来越受到人们的重视.在不确定数据上进行降维, 如基于模糊粗糙集的属性约简, 近几年得到广泛关注.但是, 现有的模糊粗糙集约简方法由于其基础理论复杂度的桎梏, 无法直接应用到大规模数据集上.

模糊粗糙集是粗糙集在模糊集框架下的一种概述^[1-4].属性约简作为模糊粗糙集的一种重要应用, 已经得到了广泛和深入的研究^[5-12].一般来说, 有两种属性约简的方法:一种是基于依赖度函数的方法, 另一种是基于辨识矩阵的方法.基于依赖度函数的属性约简方法, 其核心思想是在保持依赖度不变的条件下去掉冗余属性.文献[7]首次提出模糊粗糙集上基于依赖度的约简算法, 该方法在一些实际应用上表现相当不错, 但是在实际应用中还存在着一些明显的不足.一个明显的不足就是算法时间复杂度极高.文献[9]中指出:文献[7]中的算法, 由于其终止条件的设计不佳, 在很多真实数据集上根本无法收敛.与文献[7]不同, 文献[8]提出了一种属性约简方法, 他们通过信息熵来衡量属性的重要性.但无论是依赖度函数, 还是属性重要性, 在大型数据集上都有着过高的时间消耗.另一个常用的属性约简方法是基于辨识矩阵^{[11, 12]}, 文献[11]提出了一种关于属性约简的统一框架:文中提出了基于模糊近似算子属性约简的正式的概念; 同时, 利用严格的数学证明, 分析了属性约简的数学构造.通过这个框架, 基于辨识矩阵的模糊属性约简方法得以提出.考虑到模糊粗糙集的灵敏度, 文献[12]提出了近似算子的一个阈值.然而, 文献[11, 12]都面临着一个相同的问题, 那就是基于辨识矩阵的方法空间消耗过大.

从上述情况可以看出:在模糊粗糙集中, 基于依赖度或者辨识矩阵的算法通常有着高时间或者高空间复杂度.这是由于作为其理论支撑的基本概念复杂度过高, 比如说, 在模糊粗糙集中十分重要的下近似算子与辨识信息的度量, 其复杂度是全集数量的平方量级.因此, 基于下近似算子与辨识信息度量的约简和分类器在大规模数据集上无法得到有效的应用.随机抽样是一种可以极大地减小运算量的统计学方法, 且随机抽样已被引入模糊粗糙集理论, 提出了一种统计近似的知识表示方法^[13].然而基于随机抽样的属性约简方法并未进一步讨论.因此, 本文将随机抽样引入到经典的模糊粗糙约简理论中, 建立一种新的统计粗糙辨识度量方法, 并设计出基于随机抽样的统计约简的算法.

本文的主要贡献在于:将随机抽样和传统的属性约简方法结合, 借助于统计下近似算子, 提出了统计辨识度和统计属性约简的概念; 然后, 利用随机抽样快速计算出统计辨识度的估计值, 从而设计用以计算统计属性约简的算法, 该算法极大地降低了属性约简的复杂度和计算量.

本文第1节回顾模糊粗糙约简.第2节提出统计不可辨识的几个基本概念, 如统计不可辨识度与统计粗糙约简等; 并给出一个定理, 该定理指出, 随机抽样的方法可用于发现属性不可辨识度的无偏估计值.第3节设计基于随机抽样的序约简算法.通过第4节的数值实验发现, 基于随机抽样的序约简算法相对于经典的属性约简算法所需的时间、空间较小, 该约简算法更适用于大规模数据集.第5节总结全文的工作.

1 相关工作 1.1 模糊粗糙集模型

首先, 我们回顾一下模糊粗糙集的基本概念^[14].

全集U是一个有限个数示例的非空集合, 记作U={x₁, x₂, …, x_n}; 每一个示例都有一系列条件属性, 记作R={r₁, r₂, …, r_p}; 决策属性D.于是, (U, R∪D)被称为一个决策表DS.

对于每一个P⊆R, 我们将二维关系P(x, y)表示成为P的模糊相似关系, 对于任意x, y, z∈U, 一个模糊相似关系满足自反性:P(x, x)=1;对称性:P(x, y)=P(y, x); T-传递性:P(x, y)≥T(P(x, z), P(z, y)).简单来说, P是用来代表其相似关系的.

模糊粗糙集是用于将模糊集和粗糙合起来的工具, 它在文献[2]中被Dubois等人提出来.然后, 其细节在文献[15, 16]中被深入地研究.总体上来说, 如今的模糊粗糙集可以被下列4个近似算子概括.

$ \begin{array}{c} \overline {{R_T}} A(x) = {\sup _{u \in U}}T(R(x, u), A(u));{\rm{ }}\underline {{R_\vartheta }} A(x) = {\inf _{u \in U}}\vartheta (R(x, u), A(u));\\ \overline {{R_\sigma }} A(x) = {\sup _{u \in U}}\sigma (N(R(x, u)), A(u));{\rm{ }}\underline {{R_S}} A(x) = {\inf _{u \in U}}S(N(R(x, u)), A(u)), \end{array} $

其中, T, ϑ, σ, S和N均为模糊逻辑算子, 详见文献[11, 12].依据对偶性, ($\overline {{R_T}} A, \underline {{R_\vartheta }} A$)是一对近似算子, ($\overline {{R_\sigma }} A, \underline {{R_S}} A$)是另一对近似算子.为简便起见, 本文接下来只讨论($\overline {{R_T}} A, \underline {{R_\vartheta }} A$)的性质与应用.($\overline {{R_\sigma }} A, \underline {{R_S}} A$)采用类似的方法, 也可以得

到类似的结果.

1.2 常见约简算法研究

常见的属性约简方法主要有两种:一种是基于依赖度函数的方法, 另一种是基于辨识矩阵的方法.下面我们简单地回顾上述两种方法.

1.2.1 基于依赖度的约简

本节我们给出一些属性约简的相关定义, 比如正域、依赖度和约简.

在决策表DS=(U, R∪D)中, 对于所有的x∈U, $PO{S_R}(D)(x) = \bigcup\limits_{z \in U} {\underline {{R_\vartheta }} ({{[z]}_D})(x)} $被称为D关于R的正域.这里,

$ {{\left[\mathit{z} \right]}_{\mathit{D}}}=\{\mathit{x}\in \mathit{U}\ \rm{s}.\rm{t}.\ \mathit{D}\left( \mathit{z}, \mathit{x} \right)=1\}. $

$Dep(PO{{S}_{R}}(D))=\sum\limits_{x\in u}{PO{{S}_{R}}(D)(x)}~$被称为决策属性集D在R上的依赖度.

属性约简的核心思想就是:在保持正域不变的条件下, 最大程度地减少冗余的属性.

在一个决策表DS=(U, R∪D), P⊆R, P被称为R对于D的一个约简, 如果P满足下列式子:

(1) Dep(POS_P(D))=Dep(POS_R(D));

(2) 对于任何b∈P, Dep(POS_P-{b}(D))≠Dep(POS_R(D)).

保持依赖度不变, 就等价于正域不变.因此, 也可以用下面的方式描述约简.

在决策表DS=(U, R∪D)中, P⊆R称为R对于D的一个约简, 如果P满足下列式子:

(1) POS_P(D)=POS_R(D);

(2) 对于任何b∈P, POS_P-{b}(D)≠POS_R(D).

基于依赖度设计的约简方法被称为依赖度算法.依赖度算法通过一个值来度量数据集的辨识信息含量, 在计算依赖度的过程中, 需要计算每一个示例的下近似.计算所有示例的下近似所需要的时间是数据规模的平方级, 因而该算法所需的时间代价较大.

1.2.2 基于辨识矩阵的约简

在模糊粗糙集中, 辨识矩阵是一个nxn的矩阵c_ij, 用M(U, R, D)来表示.

(M1):${{c}_{ij}}=\{a:T(a({{x}_{i}}, {{x}_{j}}), \lambda )=0\}, \lambda =\underline{{{R}_{\vartheta }}}{{[{{x}_{i}}]}_{D}}(x)$, 对于$D({{x}_{i}}, {{x}_{j}})=0$;

(M2):c_ij=ø, 对于D(x_i, x_j)=1.

在基于辨识矩阵的属性约简中, 其核心思想是保持辨识矩阵中的辨识能力不变.基于辨识矩阵, 可以这样定义约简:在决策表DS=(U, R∪D)中, P⊆R, P被称为R对于D的一个约简, 如果P满足下列条件:

$ \mathit{P}\cap {{\mathit{c}}_{\mathit{ij}}}=\varnothing, 对于所有{{\mathit{c}}_{\mathit{ij}}}\ne \varnothing . $

基于辨识矩阵设计的约简方法被称为辨识矩阵算法.该算法计算了每一对示例的辨识信息, 并将它们存为矩阵形式, 这是辨识矩阵算法的特点.然而, 矩阵的形式的信息度量方法也成为辨识矩阵方法在大规模数据上应用的瓶颈.这是由于辨识矩阵算法需要数据规模平方级大小的空间来存储矩阵.

1.3 统计粗糙集模型

对于∀x∈U, 下近似值就是到不同类别点的最小距离^{[17, 18]}.假设y恰好就是x取到异类点最小值的示例, 那么很明显地, x和y必然在某些维度上非常接近.因为如果x和y在所有维度上都距离很远, 那么x就不会在y上取到异类点的最小距离.基于这个逻辑, 如果我们将整个数据库在该维度, 即属性)上排序, 那么x和y会离得比较接近.下面我们会提出两个概念k-neighbor和k-limit, 用来定义某示例的邻居.

定义1. 给出一个随机变量X和它的n个样本升序排列{x₁, x₂, …, x_n}, 那么x_i的k-neighbor可以表达成

$ \left\{ \begin{array}{*{35}{l}} {{x}_{1}}, ..., {{x}_{i}}, ..., {{x}_{i+k}},&{\rm{if }}\ i-k<1 \\ {{x}_{i-k}}, ..., {{x}_{i}}, ..., {{x}_{n}},&{\rm{if }}\ i+k>n \\ {{x}_{i-k}}, ..., {{x}_{i}}, ..., {{x}_{i+k}},&{\rm{others}} \\ \end{array} \right., 1\le k\le {\rm{arg}}\left( n/2 \right). $

定义2. 给定决策表DT=(U, R, D), 其中, U={x₁, x₂, …, x_n}, R={r₁, r₂, …, r_m}.对于所有属性1≤k≤arg(n/2), 将x_i的k-neighbor集中到一个集合中, 这个集合就称为x_i的k-limit(限定区域).这里, k就是限定长度.

定义3. 给定决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}, R={r₁, r₂, …, r_m}, F(U)是U的模糊幂函数集合.对于∀x∈U, A∈F(U), x的k-统计下近似算子和k-统计上近似算子可以如下表示:

$ \begin{align} & A(x)={{\inf }_{u\in k-limit(x)}}\vartheta (R(u,x),A(u)),\overline{R_{T}^{k}}A(x)={{\sup }_{u\in k-limit(x)}}T(R(u,x),A(u)), \\ & \underline{R_{S}^{k}}A(x)={{\inf }_{u\in k-limit(x)}}S(N(R(u,x)),A(u)),\overline{R_{\sigma }^{k}}A(x)={{\sup }_{u\in k-limit(x)}}\sigma (N(R(u,x)), \\ & A(u)). \\ \end{align} $

定义3提供了一种新的方法, 用更少的计算量来拟合经典的近似算子.性质1和性质2说明:在k足够大时, k-统计近似算子可以逼近经典的近似算子.文献[13]还详细地给出了基于随机抽样的统计下近似计算的方法以及理论支持.然而, 如何基于统计近似算子, 借助随机抽样的手段构建快速的统计粗糙约简算法, 文献[13]并未提及.因此, 本文接下来的工作将围绕如何基于统计粗糙集与随机抽样的方法构建基于随机抽样的粗糙约简算法.

2 基于随机抽样的属性约简

为了提高属性约简算法的效率, 我们首先定义一些新信息度量的概念, 用以定义统计不可辨识性和基于随机抽样的统计约简.

定义4. 对于决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}.对于(x_i, x_j)∈U并且x_j是x_i的k-neighbor, 如果D_r(x_i, x_j) < λ_i, 那么我们说x_i对于x_j在r上是k-统计不可辨识, 或者说(x_i, x_j)称为r上的k-统计不可辨识对.如果D_r(x_i, x_j)≥λ_i, 那么我们说x_i对于x_j在r上是k-统计可分辨, 或者说(x_i, x_j)称为r上的k-统计可分辨对.其中, D_r(x_i, x_j)是x_i和x_j在属性r上的距离, 可以是欧氏距离; λ_i是x_i的k-统计下近似.

定义5. 对于决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}, ∀x_i∈U.

(1) ∀r∈R, $IND_{r}^{k}({{x}_{i}})=\{({{x}_{i}}, {{x}_{j}})|{{D}_{r}}({{x}_{i}}, {{x}_{j}})<{{\lambda }_{i}}, 1\le j\le n\}, IND_{r}^{k}({{x}_{i}})$称为|INP_r(x_i)|上的不可辨识集合, $IND_{r}^{k}({{x}_{i}})$包含所有x_i在|INP_r(x_i)|上的k-统计不可辨识对.

(2) ∀r∈R, |IND_r^k(x_i)|代表着$IND_{r}^{k}({{x}_{i}})$中元素的个数, 我们称其为x_i在|INP_r(x_i)|上的k-统计不可辨识度.

(3) ∀Q⊆R, $IND_{Q}^{k}({{x}_{i}})=\bigcap\limits_{r\in Q}{IND_{r}^{k}({{x}_{i}})}, IND_{Q}^{k}({{x}_{i}})$包含所有x_i在Q上的k-统计不可辨识对, 称为x_i在Q上的不可辨识集.

(4) ∀Q⊆R, |IND_r^k(x_i)|称为x_i在Q上的k-统计不可辨识度.

由定义4可得:某属性的不可辨识度越大, 该属性可以分辨的示例就越多.

性质1.

(1) 当P⊆Q⊆R, $IND_{P}^{k}({{x}_{i}})\supseteq IND_{Q}^{k}({{x}_{i}})\supseteq IND_{R}^{k}({{x}_{i}})$;

(2) 当P⊆Q⊆R, $|IND_{P}^{k}({{x}_{i}})|\ge |IND_{Q}^{k}({{x}_{i}})|\ge |IND_{R}^{k}({{x}_{i}})|$.

定义6. 对于决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}.

(1) ∀r_j∈R, $IND_{r}^{k}=\bigcup\limits_{i=1}^{n}{IND_{r}^{k}({{x}_{i}})}, IND_{r}^{k}$包含着所有x_i在|INP_r(x_i)|上的k-统计不可辨识对, 我们称IND_r^k为属性r的不可辨识集.

(2) ∀r_j∈R, $|IND_{r}^{k}|$是$IND_{r}^{k}$中元素的个数, 称为属性r的k-统计不可辨识.

(3) ∀Q⊆R, $IND_{Q}^{k}=\bigcap\limits_{r\in Q}{IND_{r}^{k}}, IND_{Q}^{k}$包含着属性集Q中每一个属性的k-统计不可辨识对, 称为属性集Q上不可辨识集.

(4) ∀Q⊆R, |$IND_{Q}^{k}$|是$IND_{Q}^{k}$中元素的个数, 称为属性集Q的k-统计不可辨识度.

由定义6可以看出, 不可辨识度越大, 该属性集就有越多无法分辨的示例对.

性质2.

(1) 如果P⊆Q⊆R, 那么$IND_{P}^{k}\supseteq IND_{Q}^{k}\supseteq IND_{R}^{k}$;

(2) 如果P⊆Q⊆R, 那么$|IND_{P}^{k}|\ge |IND_{Q}^{k}|\ge |IND_{R}^{k}|$.

定义7(统计属性约简). 对于决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}, R={r₁, r₂, …, r_m}.如果子集Q⊆R满足下列条件, 那么我们就说子集Q是R的一个统计属性约简.

(1) $IND_{Q}^{k}=IND_{R}^{k}$或者$|IND_{Q}^{k}|=|IND_{R}^{k}|$;

(2) ∀r∈R, $|IND_{Q-\{r\}}^{k}|>|IND_{Q}^{k}|$.

定义7说明了本文中统计属性约简是保持统计不可辨识的信息含量不变的最小属性子集.

定理1. 给定决策表, 其中, U={x₁, x₂, …, x_n}, S={s₁, s₂, …, s_a}表示随机从全集U中抽样得到的一个示例集合.当$ a>\frac{{{t}^{2}}{{\sigma }^{2}}}{{{d}^{2}}{{{\bar{Y}}}^{2}}}$时, 满足以下条件, 则至少以e的置信度, 使得:

$ \left| \frac{\frac{ind({{r}_{i}})}{a}-\frac{IND({{r}_{i}})}{n}}{\frac{IND({{r}_{i}})}{n}} \right|<d. $

(1) IND(r_i)是r_i在U上的不可辨识度;

(2) ind(r_i)是r_i在S上的不可辨识度;

(3) σ², Y分别是r_i在U上的不可辨识度的方差与均值, 由预调研得到;

(4) t是标准正态分布的1-e双侧分位数;

(5) d是绝对误差.

证明:对于简单随机抽样, y的方差为$V(\bar{y})=\frac{N-n}{Nn}{{\sigma }^{2}}$, 其中, ${{\sigma }^{2}}=~\frac{1}{N-1}\sum\limits_{i=1}^{N}{{{({{Y}_{i}}-\bar{Y})}^{2}}}$, N为总体个数, n为样本个数; y的相对误差记为$d=\frac{\sqrt{V(\bar{y})}}{{\bar{Y}}}$.将V(y)代入相对误差, 可得$d=\frac{t}{{\bar{Y}}}\sqrt{\frac{N-n}{Nn}{{\sigma }^{2}}}$, 从而有$n=\frac{N{{t}^{2}}{{\sigma }^{2}}}{N{{d}^{2}}{{{\bar{Y}}}^{2}}+{{t}^{2}}{{\sigma }^{2}}}$^[19].当N足够大时, $n=\frac{{{t}^{2}}{{\sigma }^{2}}}{{{d}^{2}}{{{\bar{Y}}}^{2}}}$.

定理1保证了在样本集S中计算的k-统计不可辨识度可以有很高的置信度, 以很小的误差拟合全集U中的k-统计不可辨识度.

前面我们回顾了经典的下近似、属性约简算法的不足——无法应用到大规模数据集中.因此, 为了满足现实应用中的大规模数据约简的需要, 我们需要基于统计粗糙集模型, 对经典的属性约简方法进行改进.而缩小属性约简的计算范围, 可以提升运算的效率——在海量数据下, 任何计算, 其范围是全集的时候, 必然会导致运算量过大.

为了进一步对约简的效率进行提升, 在约简时用抽样集代替全集, 计算每个属性的重要性排序.并且, 应用定理1保证在样本集中计算出的重要性排序, 有很高的置信度, 以很小的误差拟合全集中的重要性排序.从而以很小的代价计算出统计属性约简.

本节中提出的统计辨识信息相对于经典模糊粗糙信息度量的优势在于:原本涉及到大规模计算(全集范围)的部分, 都巧妙地以随机抽样得到的小容量样本代替.由于随机抽样得到的样本数量和全集相比数量极小, 更值得一提的是, 随着全集数量的增大, 样本数量并不会显著增大, 因此, 全集数量越大, 统计粗糙约简的优势就越大.

3 基于随机抽样的约简算法

本节针对统计属性约简设计了基于随机抽样的约简算法.我们将计算统计属性约简分成两步:第1步是根据依赖度函数对属性重要性进行排序, 第2步是根据所得到的顺序进行约简.

3.1 对属性进行排序

对于决策表DS=(U, R∪D), 其中, U={x₁, x₂, …, x_n}. $|IND_{r}^{k}|$是r上的k-统计不可辨识度.从第2节对k-统计不可辨识度的描述中可知:$|IND_{r}^{k}|$越小, 属性r可以辨识的元素越多, 它的重要性可能就越高.

算法1. 对属性排序.

输入:DS=(U, R∪D), U={x₁, x₂, …, x_n}, R={r₁, r₂, …, r_m}, 排序属性队列SR $\leftarrow $ø, η, e.

输出:SR.

第1步:计算出样本数量$a={{\max }_{P}}\left( \frac{{{t}^{2}}{{\sigma }^{2}}}{{{\eta }^{2}}{{{\bar{Y}}}^{2}}} \right)$, 随机的从全集U中抽取a个样本, 得到S={s₁, s₂, …, s_a}.

第2步:计算$IN{{D}_{~}}_{{{r}_{j}}}^{k}=\bigcup\limits_{i=1}^{n}{IN{{D}_{~}}_{{{r}_{j}}}^{k}({{s}_{i}})}$, ∀j∈[1, 2, …, m]:

    (2.1)计算x_i的限定区域k-limit;

    (2.2)计算${{{\lambda }'}_{i}}=\underline{R_{\vartheta }^{k}}{{[{{x}_{i}}]}_{D}}({{x}_{i}});$

    (2.3) i$\leftarrow $i+1.

第3步:q$\leftarrow $0.

第4步:当q < m, 执行:

    (4.1) q$\leftarrow $q+1;

    (4.2) R' =R-SR;

    (4.3) ∀r_j∈R' ,计算$IN{{D}_{~}}_{SR\cup {{r}_{j}}}^{k};$

    (4.4) SR$\leftarrow $SR∪sr_q, 其中, $|IN{{D}_{~}}_{SR\cup s{{r}_{q}}_{~}}^{k}|={{\min }_{{{r}_{j\in {R}'}}}}(|IN{{D}_{~}}_{SR\cup {{r}_{j}}}^{k}|). $

第5步:输出SR={sr₁, sr₂, …, sr_m}.

在本节算法中, 我们使用随机抽样所得到的样本, 而非全集来决定属性约简的顺序.同时, 我们使用统计不可分辨来衡量属性的重要性.定理1保证在很高的置信度下, 以很小且可控的误差用样本集中的数据来拟合全集中的数据.

3.2 计算属性约简

算法2. 得到k-统计属性约简.

输入:DS=(U, R∪D), U={x₁, x₂, …, x_n}, R={r₁, r₂, …, r_m}, SR={sr₁, sr₂, …, sr_m}, k.

输出:RED.

第1步:Red$\leftarrow $sr₁; q$\leftarrow $1.

第2步:对于∀x_i∈U, 计算$IN{{D}_{~}}_{Red}^{k}({{x}_{i}}):$

    (2.1)计算x_i的限定区域k-limit;

    (2.2)计算${{{\lambda }'}_{i}}=\underline{R_{\vartheta }^{k}}{{[{{x}_{i}}]}_{D}}({{x}_{i}});$

    (2.3) i$\leftarrow $i+1.

第3步:当 |IND_Red∪srq+1^k|-|IND_Red^k| > 0和q < m时, 执行:

$ \mathit{q}\leftarrow \mathit{q}+1, \mathit{Red}\leftarrow \mathit{Red}\cup \mathit{s}{{\mathit{r}}_{\mathit{q}}}. $

第4步:输出RED.

这里, 我们需要强调以下两点.

第一, 我们使用不可辨识对来存储不可辨识关系.

与传统的辨识矩阵关系不同的是, 我们只存储第1个属性, 也就是最重要的属性的不可辨识对.在不断约简这些不可辨识对的时, 只有尚存的不可辨识对, 用新的属性去测试是否可以被辨识.这种做法有两个好处:其一是只需要存储一个属性下的不可辨识对, 减少了空间消耗; 其二是没有无用的操作, 所有的比较操作都是有效的.

第二, 我们使用位图来存储这些不可辨识对.

位图可以用1bit存储一个不可辨识对, 这样可以节省32倍的空间.在比较时, 我们也是用位操作来进行操作, 由于位操作比正常的运算快很多, 因此这样也可以有更好的时间空间性能.

需要指出的是, 本文提出的算法的计算复杂度为O(max(2k|R|²|U|, |R|²|S|²)), 而经典算法的计算复杂度为O(|R|²|U|²).因此当2k远小于|U|时, 我们提出的基于随机抽样的算法比经典算法节约了大量的时间和空间.

4 数值实验

在本节中, 随机抽样算法(简记为Sampling)与两种经典启发式属性约简算法, 即依赖度函数算法(简记为Dependency)和辨识矩阵算法(简记为Matrix)进行对比.我们从3个方面来评估3种算法的性能:算法的时间效率、空间效率和算法得到约简的性能.

4.1 实验环境及数据集

所有的实验均是在Linux下, 由C++编码完成.实验所使用的硬件参数是, CPU为Intel® Xeon® CPU ES-2670 2.6GHz.

在本实验中, 几个UCI数据集用来验证每一个算法的效率^[20], 具体数据集参数见表 1.

为了更好地展示计算的时间和空间, 在数据集的示例数逐渐增加的情况下, 观察3种算法的运算时间与所占用的空间变化趋势.

4.2 实验结果与分析 4.2.1 属性约简时间消耗对比

在本节中, 约简时间消耗随着数据集大小的变化趋势绘制在图 1中.

在图 1中, 基于依赖度函数的部分时间消耗值由于过于庞大, 以至于超过图表的顶部.这是因为基于依赖度函数的时间复杂度较高, 在大规模数据集上其时间消耗过于庞大, 甚至达到了某限定时间内无法收敛的地步.

在图 1中, 随着数据集的增大, 基于依赖度的算法时间消耗急剧上升, 辨识矩阵算法时间消耗上升较快, 随机抽样算法则上升速度十分平缓, 而且随机抽样算法的时间消耗总是远小于另外两种算法的时间消耗.这体现了随机抽样算法在进行属性约简时的时间优越性, 特别是在大规模数据集下的计算时间可控.

4.2.2 空间消耗对比

为什么传统的辨识矩阵约简算法无法应用到大规模数据集呢?一个主要的因素就是太多的空间消耗.因此, 本节对比了随机抽样算法和基于辨识矩阵算法的空间消耗势.

表 2给出两种算法在8个数据集上进行约简的空间消耗对比.

从表 2中我们可以清晰地看到:随机抽样算法的空间消耗非常小, 所降低的空间消耗量级约在2个数量级到3个数量级之间; 并且, 可以隐约看出, 数据量越大, 随机抽样算法所降低的量级也越多.图 2给出了随机抽样算法和辨识矩阵算法的空间消耗随着数据集大小变化的趋势.

从图 2中可以看出, 基于辨识矩阵的算法与随机抽样相比, 有着很高的空间消耗.事实上, 很多时候, 当数据集的大小不断增长时, 辨识矩阵算法的空间消耗急剧增加, 而随机抽样算法的消耗较为平稳.这是因为随机抽样的样本集大小并不会随着全集的增加急剧增大, 而是基本保持稳定, 所以使得整体空间消耗较为稳定.

4.2.3 约简效果对比

我们将用KNN算法作为分类器, 对原始数据集、依赖度算法约简后数据集、辨识矩阵算法约简后数据集、随机抽样算法约简后数据集进行分类, 观察分类精度的变化.所有数据集在进行分类时, 都是用了10-交叉验证.

从表 3中可以看出, 3种算法在约简后剩下的属性数量上大致相同; 而在精度上, 基于随机抽样的算法与其他两者相比, 分类精度略有下降, 但是下降不多.这是由于在随机抽样过程中, 不可避免地有一些信息量的损失, 但是定理1保证了其损失的精度在可控范围.

综上可得, 随机抽样算法虽然在某些时候对于约简精度会有小幅度但可控的下降, 但其在属性约简时间效率、属性约简空间效率方面, 相对于传统的属性约简算法都有着大幅度的提升.

4.2.4 抽样下近似的稳定性分析

基于抽样的约简的稳定性取决于基于抽样的不可辨识度的稳定性, 本节我们实验验证抽样下近似的稳定性.我们实验比较了真实下近似与抽样下近似之间的差异性.实验结果汇总至表 4.

基于定理1, 给定绝对误差d与置信度e的双侧分位数t, 即可得到样本容量的下界.基于此下界抽样获得样本上的不可辨识度在样本上与总体上的真实不可辨识度的差值, 即|P-p|, 统计上应小于d.表 4给出了在给定对误差d与置信度e的双侧分位数t后, 样本上的不可辨识度在样本上与总体上的真实不可辨识度的差值, 即|P-p|.表 4的最后一列显示确实如此.这说明, 不可辨识度在样本上与总体上是统计稳定的.因而, 基于样本不可辨识度所获得的约简也是具有统计稳定性的.

5 总结

现有的模糊粗糙集约简方法由于其基础理论复杂度的桎梏, 不可避免地使得约简效率极低, 无法应用到大规模数据集上.随机抽样则是一种可以极大地减少运算量的统计学方法, 因此, 本文将随机抽样引入到经典的模糊粗糙约简理论中, 设计了一种基于随机抽样的粗糙约简算法.通过数值实验发现:随机抽样算法虽然在某些时候对于约简精度会有小幅度但可控的下降, 但其在属性约简时间效率、属性约简空间效率方面, 相对于传统的属性约简算法都有着大幅度提升, 并且这种提升随着数据集的增大更加显著.因此, 随机抽样算法弥补了传统属性约简方法无法应用到大规模数据集上的缺陷, 适合应用于大规模数据集.