0 概述

知识发现将知识提取后表示为概念、规则、规律和模式等形式。分类是知识发现研究的重要分支之一, 它通常有基于符号和基于连接的2种方法^[1]。基于连接的方法以神经网络为代表, 其分类模型蕴含在本体结构中, 不易理解。虽然神经网络具有分类精度高和鲁棒性强的优点, 但是存在训练时间长、网络结构复杂等问题, 特别是其知识解释性能差^[2]。基于符号的方法得到的分类知识以分类规则的形式出现, 此类方法包括决策树、粗糙集理论等技术^[3]。决策树分类算法通过对训练集的学习, 获取一个树模型, 最终可以通过从树模型的根节点出发到所有叶子结点的路径生成表示规则集(IF-THEN结构)的结果, 每条规则的前件(IF部分)按照所在遍历路径中的属性值对的逻辑合取形成, 而规则后件(THEN部分)就是叶子节点的类标记^[4-5]。基于粗糙集的规则挖掘方法利用知识的不确定性度量各属性值对的重要程度, 每次选择相对决策属性最重要的属性值对到候选规则, 通过迭代过程形成一个分类规则集作为不确定性决策的挖掘结果^[6-7]。粗糙集规则提取方法与决策树模型相比, 不需要训练数据提供先验知识, 也省去了构建树模型这一中间步骤, 为提高规则挖掘效率提供了新思路^[8]。

规则挖掘系统以特定的学习方法不断提取规则, 并依据这些知识进行推理和判断, 以演绎或归纳的结果形成决策^[9]。这种规则提取、再生、组织和决策的过程同人类的思维过程极为类似。该过程分为信息输入、信息处理和信息输出3个环节, 从人的思维过程能够得到如下启发:规则蕴含在多源信息之中, 但蕴含的形式多样, 蕴含的复杂度不同, 对于隐含的规则, 要通过抽象概括、关联以及发现等技术进行提取。规则挖掘系统的简化原则是指从用例空间提取的属性维数空间、判决空间以及用于决策的知识数量最小, 以便形成精炼简化的知识, 避免获取的知识过拟合训练数据, 从而保证得到可信的判决结果^[10]。简化原则的目标有2个:一个是减少要处理的信息; 另一个是减少误判率, 提高结果的准确性和可信度。该准则多用于知识的产生处理和状态估计过程中, 因为生成的知识数量小, 推理引擎的检索速度、匹配效率和计算性能可以得到相应的提高。

在属性约简和规则挖掘过程中, 要保证规则的有效性^[4], 就应使组成规则的属性集中在约简属性集合上, 且规则的前件由少数几个属性组成。这样生成的规则最少或最简^[11-13], 便于推理引擎快速及时的查询、匹配并作出判断^[14]。此外, 由于决策过程中每个决策都存在一定的误差, 若用于决策的状态少, 则累计误差小, 从而能够降低误判率, 使造成的损失减小^[15]。因此, 规则挖掘系统遵循简化准则可以保证知识获取的有效性^[16-18]。由于复杂形式的规则不易被领域专家理解, 且可能导致过拟合训练数据集的问题, 规则挖掘算法为提高效率, 提取的规则集合在保持较高分类精度的同时, 其集合大小和表达形式应尽可能简洁^[19-20]。本文借助权重模糊粗糙集模型, 设计一种混合数据上用例带权重的粗糙集分类规则提取算法。

1 基于粗糙集的LEM2算法

文献[14]以LEM2算法为核心, 开发了经典粗糙集规则挖掘系统LERS。以Pawlak粗糙集模型的上、下近似集作为算法LEM2的输入, 该系统可以处理不带先验知识的训练数据, 同时生成确定规则和可能规则, 具有较好的分类效果。

粗糙集理论给出了通过下近似和上近似计算分类正域、负域和边界域的框架。LEM2算法假定没有任何有关数据集的先验知识, 基于粗糙集分类知识和约简结果, 可以从正域和负域提取确定性规则, 还可以从边界域提取可能性规则。

算法LEM2用到的基本概念有属性值对t=(c_j, v), c_j∈C, v∈V, t是规则前件的组成部分, 满足属性c_j取值为v的所有用例集可记为[t], 也称t的块, 块可以表示属性值对的一个知识粒度, 满足{x|x_j=v, x∈U}。设B是论域空间上的正域、负域或边界域集合, T是属性值对t=(c_j, v)的集合, 算法LEM2利用[t]的频繁度评估函数构造一个T的集合$\mathbb{C}$, 即近似最优覆盖, 使它满足以下性质:

1)∪_{T∈$\mathbb{C}$}[T]=B。

2) ∀$\mathbb{C}$⊂$\mathbb{C}$不满足条件1。

算法LEM2利用启发式信息策略, 迭代选择具有高评分值的属性值对, 将选择的值对逐步加入粗糙集最小覆盖。一旦找到一个完整的粗糙集局部覆盖后, LEM2算法就可以将局部覆盖解释为一组规则集。算法不断从训练数据提取规则集, 获取的分类规则结果可用于决策新的数据集。该方法的改进版本MLEM2为解决含有数值型属性数据集的问题, 与离散化方法、属性约简方法进行了结合, 但实验发现离散化方法对分类性能的影响很大。

2 模糊粗糙集理论和规则提取方法

经典Pawlak粗糙集模型在不需要任何先验知识的前提下, 可以处理含有不确定分类特征的离散值数据。然而, 在实际应用中, 多模态数据挖掘任务需要同时处理离散值和连续值并存的混合数据。模糊粗糙集模型作为对经典粗糙集模型的扩充, 拓展了含有异质属性论域的数据挖掘思想, 并提出了有效的属性约简方法。这种思想也为分类规则提取方法提供了理论依据。本文假设处理的论域中用例带有权重信息, 属性集同时具有离散型和连续型特点, 基于模糊粗糙集模型的带权用例论域上的模糊等价关系, 研究从带权模糊近似空间的上、下近似中提取规则的步骤和方法。

定义1  设五元组WIS=〈U, A, V, f, w〉表示一个用例带权的信息系统, 其中, U为论域, A={a₁, a₂, …, a_n}为属性集合, V为属性值域的集合, f:U×A→V是映射函数, 各用例权重分配由函数w:U→R描述。如果将属性集合划分为2个子集, 即A=C∪D, 其中C、D分别为条件和决策属性集合, 则WIS也可被称为用例带权的决策信息系统。

定义2  设给定一个带权论域〈U, w〉上的一个模糊集合$\widetilde X$, 则$\widetilde X$相对于用例带权论域〈U, w〉的模糊集合加权度数定义为:

$ |\tilde X{|^w} = \sum\limits_i {\frac{{{w_i}}}{{\sum\limits_j {{w_j}} }}} \tilde X(i) $

根据模糊集理论和经典集合论的关系, 经典等价关系可以生成论域上的清晰划分, 而模糊划分则定义为论域上的一个模糊等价关系。因此, 传统属性值对的块定义需要推广到数值型属性的论域上。下文将粗糙集规则挖掘算法LEM2中核心块概念进行扩展, 推广到用例带权重的信息系统的模糊等价空间中。

定义3  设t=(c_j, F_j^p_j)是用例带权的决策信息系统上的模糊属性值对, 则t的模糊块定义为:

$ [t] = \int_{x \in U} {{\mu _{F_j^{pj}}}} \left( {{x_j}} \right) $

(1)

由模糊块定义可知, [t]是一个论域上满足属性取值(c_j, F_j^p_j)条件的模糊等价关系。因此, 也可以将模糊块[t]看作属性值对(c_j, F_j^p_j)形成的一个模糊知识信息粒度, 这是权重模糊块和算法LEM2中清晰块的主要区别。

在模糊近似空间中, 模糊粗糙集模型给出了利用模糊等价关系计算下、上近似集的框架, 假设X为一个包含用例的概念集, R是X上的模糊等价关系, 模糊粗糙集关于X的下、上近似集分别定义为:

$ (X) = \left\{ {x|{{[x]}_R} \subseteq X,x \in U} \right\} $

(2)

$ \bar R(X) = \left\{ {x|{{[x]}_R} \cap X \ne \emptyset ,x \in U} \right\} $

(3)

其中, 模糊集合操作⊆和∩是Zadeh包含和Zadeh交。

定义4  若t=(c_j, F_j^p_j)是用例带权信息系统中的一个模糊属性值对, X是一个含有论域用例的经典集合, T是所有模糊属性值对t的集合的一个子集。若满足以下条件:

$ \emptyset \ne [T] = { \cap _{t\varepsilon }}\tau [t]{ \subseteq _\alpha }X $

定义集合X以近似局部依赖于集合T。其中, 交运算的定义是:

$ A \cap B = \int_{x \in U} {\min } \left( {{\mu _A}(x),{\mu _B}(x)} \right)/x $

由粗糙集理论可知, 概念集的上近似和下近似集合可以形成分类正域、负域和边界域。规则提取算法以这些集合为起点获取确定性规则和可能性规则。设B是一个类别的正域、负域或边界域的经典集合, T是模糊属性值对的集合。当且仅当B为α近似局部依赖于T, 并且不存在T的子集T′使得B满足近似依赖于T′, 集合T是B的一个最小近似局部覆盖。

定义5  若t=(c_j, F_j^p_j)是一个模糊属性值对, $\mathbb{C}$是t的最小近似局部覆盖, POS⁺是权重论域上的一个类别的正域集合, 则$\mathbb{C}$是POS⁺正域的一个(α, k)权重局部覆盖定义为:

1) H^w(∪_{T∈$\mathbb{C}$}[T], POS⁺)≤k。

2) ∀t∈$\mathbb{C}$, t是正域集POS⁺的一个α最小近似局部覆盖。

权重论域的模糊集合相异度采用经典度量标准:

$ \begin{array}{*{20}{l}} {{H^w}(A,B) = \frac{{|\bar A \cap B{|^w} + |A \cap \bar B{|^w}}}{{|A \cup B{|^w}}}| \cdot {|^w} = }\\ {\bar A = \int_{x \in U} {\left( {1 - {\mu _A}(x)} \right)} /x}\\ {{H^w}(A,B) \in [0,1]}。\end{array} $

α和k为规则挖掘算法提供了新的停止准则, 是简化规则集的剪枝条件。算法LEM2无法提取简洁规则的一个原因是:遍历结束条件导致挖掘的规则集数目和规则集长度均变大, 即使提高了训练数据的分类性能, 也无法满足测试数据的分类精度要求。这就是知识获取中的过拟合问题。为克服过拟合给粗糙集规则挖掘方法带来的影响, 借助于定义的局部依赖和近似局部覆盖, 本文引入局部依赖度和近似局部覆盖度2个重要参数, 规则提取算法利用这2个泛化性能参数进行调节。局部依赖度是对经典依赖的扩展, 控制生产的规则前件过于冗长, 而近似局部覆盖度容许算法提取的规则子集覆盖部分正域数据, 使规则集数目更小。当训练数据存在部分不一致分类对象时, 泛化剪枝机制非常有效。

经典LERS系统中的算法LEM2对正域类集合的属性值对空间进行启发式的遍历和搜索, 以属性值对最小覆盖度作为优先级, 逐步提取最优规则的前件信息。而算法HLEM2利用的启发式信息包含局部覆盖度和局部近似覆盖度, 为提高学习的泛化能力, 需要重新设计启发式评估函数, 通过新的评估方法控制生成规则集的复杂程度。因为模糊块是经典块定义在模糊集理论上的扩展, 需要重新定义模糊粗糙集规则提取算法的权重评估函数。

定义6  设G是一个模糊集合, t=(c_j, F_j^p_j)是用例带权信息系统中的一个模糊属性值对, 规则提取算法的权重评估函数定义为:

$ Scor{e^w}(t,G) = |[t] \cap G{|^w} $

(4)

设HDIS={U, C^s∪Cⁿ∪C^f∪{d}, V, f}为用例带权重的决策信息系统, 它含有离散型属性集合C^s、连续型属性集合Cⁿ、模糊型属性集合C^f和决策属性d。规则提取算法的泛化参数α和k通常设置在0附近, 本文实验将它们都设置为0.05。模糊集合的操作利用Zadeh定义。算法HLEM2给出了分类规则挖掘算法的伪代码。

算法   HLEM2

输入  混合权重信息系统WIS

输出   IF-THEN规则集

1.G ⇐ POS⁺

2.$\mathbb{C}$⇐∅

3.while I(∪_{T∈$\mathbb{C}$}[T], B) > k do

4.T ⇐∅

5.while (T = ∅) or (not ([T]⊆_αB)) do

6.t ⇐ arg max_t∈TScore^w(t, G)

7.T ⇐ T ∪{t}

8.G ⇐[t]∩ G

9.end while

10.$\mathbb{C}$ ⇐$\mathbb{C}$ ∪{T}

11.G ⇐ B \∪_{T∈$\mathbb{C}$}[T]

12.end while

13.for ∀T ∈ $\mathbb{C}$ do

14.if H^w(∪_{S∈$\mathbb{C}$ {T}}[S], B) ≤ k then

15. $\mathbb{C}$⇐ $\mathbb{C}${T}

16.end if

17.end for

18.return $\mathbb{C}$

由算法HLEM2流程可知, 算法的空间复杂度和传统的LEM2相同, 均为O(n²)。下文对算法HLEM2的时间复杂度进行理论分析。设n为用例总数, r为生成的规则数量。第1行~第2行的时间复杂度为O(1);第3行~第12行循环流程迭代O(r)次, 每次迭代的计算复杂度为O(n); 第13行~第17行最多迭代O(r)次。因此, 算法的总体时间复杂度为O(rn)。

定理  当各用例权重相等时, 若k=α=0, 且属性全为离散型属性, 算法HLEM2等价于算法LEM2。

证明  各用例权重相等, ∀x, y, w(x)=w(y), 对于离散型属性, 算法HLEM2中的(α, k)权重近似覆盖定义和LEM2算法的经典覆盖定义完全一致, 且针对离散型属性的模糊集合操作和经典集合操作完全等价。由此可知, 算法HLEM2和LEM2的规则提取步骤、剪枝条件相同, 所以规则提取结果相同, 定理成立。

定理表明了本文算法HLEM2在各用例权重相等时, 信息系统仅含有离散型属性时的性质。在设计规则提取算法HLEM2时, 剪枝条件由最小覆盖属性集合的区分能力和原有属性集一致时结束, 改为属性子集的近似最小局部覆盖的区分能力大于给定阈值时停止。改变的原因是, 当近似局部覆盖的分类能力达到一定区分度时, 算法的泛化性能可能更好, 使得改变后的规则提取剪枝条件更符合实际需要。

事实上, 算法HLEM2避免了过于严格的终止准则以及LERS系统中对属性类型的限制。与算法MLEM2不同, 即使决策表中的属性全是离散型的, 算法HLEM2的性能也可以由参数α和k进行调节。规则挖掘算法HLEM2生成的规则形式如“IF $\widetilde \phi $ THEN D=d”, 其中$\widetilde \phi $={t_i|t_i=(c_i, F_i^p_i), i=1, 2, …, t}是规则的前件, 为t个基本条件的合取式。规则的支持度、覆盖度和可信度因子可以通过模糊隶属度确定。

3 实验与结果分析

本文选择LEM2算法和DataSqueezer(DS)算法作为对比算法, 重点关注3种算法在数据集上的分类精度、规则集的复杂程度。首先对数据进行预处理, 利用平均值填充连续型属性和出现频率最大值填充离散型属性, 解决缺失数据问题。表 1列出了实验选取的6个基准数据集的配置, 数据集来源于UCI-ML数据库。前5个数据集采用10次交叉验证实验, 最后一个数据集有单独测试集, 并且每个数据集均包含了离散型和数值型的属性。其中, 训练用例的范围为151~48 842, 条件属性的数量为5~36。算法HLEM2对连续属性进行模糊化, 即通过模糊C-means算法对连续属性的取值划分3个区间, 用三角分布的隶属函数表示每个区间。通过与基准算法的对比, 可以较为客观地反映本文算法HLEM2的分类性能。

表 2给出了HLEM2、DS和LEM2算法在数据集上的准确率。前5个数据集的实验采用了10次交叉验证, 表 2记录的是10次实验的平均准确率和标准方差。

由表 2可以得出以下结论:

1) 算法HLEM2在所有数据集上取得的平均准确率最高, 算法DS其次, 算法LEM2最低。

2) 在分类准确率指标上, 3种算法中任何一个算法都不是最优的。

3) HLEM2仅选取了形式最简单的三角隶属函数, 在整体上就可以获得较好分类准确率。

表 3给出了3种算法的精度P和召回率R比较。HLEM2在大部分数据集上的精度和召回率取得了较好结果。图 1给出各算法在6个数据集上的F1值。从图 1可以看出, 算法HLEM2在6个数据集均取得最高的F1值, 表明本文算法具有较好的分类性能。事实上, 由于DS算法和LEM2算法需要对数据进行离散化的预处理, 针对不同分布的数据集会导致分类性能有所下降。

表 4给出了3种算法提取的规则集的质量比较。其中, N表示提取规则的数目, l/r表示平均规则长度。由于规则集的复杂度可以由规则数目和规则长度2个指标来衡量, 通过对比3种算法提取规则的复杂度, 可以评估算法的泛化性能。由表 4中的平均数据可以看出, 算法HLEM2生成的规则集最简洁、规则长度最小, LEM2提取的规则复杂度最大。

综上, 可以得到以下结论:算法HLEM2通过泛化性能参数可以有效简化经典算法LEM2的规则集, 而且在多个数据集上的分类性能F1值指标也超过了算法DS, 且生成规则的平均长度最短。

4 结束语

本文设计一种混合数据上用例带权重的粗糙集分类规则提取算法。在规则提取过程中, 通过对泛化参数的调节, 提高规则挖掘结果的分类精度。实验结果表明, 本文算法通过参数α和k寻找近似局部覆盖, 可以提高粗糙集规则挖掘方法的泛化能力, 解决经典粗糙集算法严格的停止准则和对属性类型的局限性问题, 扩展粗糙集在混合数据和带权论域上的应用范围。下一步将研究加权粗糙集规则提取算法, 减小生成规则集的误分代价损失以及数据集倾斜对算法的影响。