定义1^[1] 称K=(U, A, I)为一个形式背景, 其中, U为对象集, A为属性集, I为U和A之间的二元关系, I⊆U× A.若x∈ U, a∈ A, (x, a)∈ I, 说明对象x具有属性a, 记为xIa.

定义2^[1] 在形式背景K=(U, A, I)中, 对∀ X⊆U, B⊆A, 定义

f(X)={a∈ A | ∀ x∈ X, (x, a)∈ I}, g(B)={x∈ U | ∀ a∈ B, (x, a)∈ I},

其中, f(X)表示X中所有对象共同拥有的属性组成的集合, g(B)表示B中所有属性的对象组成的集合.

对于形式背景(U, A, I), 对于∀ X⊆U, B⊆A, 若满足f(X)=B且g(B)=X, 称(X, B)为一个概念, 其中, X称为概念的外延, B称为概念的内涵.

所有概念的集合形成一个完备格, 称为(U, A, I)的概念格, 表示为L(U, A, I).

在各种下游任务中, 概念往往不能满足严格意义上的内涵与外延的协调统一.因此, 在弱化概念的前提下, Hong等^[16]提出近似概念的定义.

定义3^[16] 设K=(U, A, I)为一个形式背景, (X, B)为K上的一个概念.假设存在(X₁, B₁), 满足X₁⊆X或B₁⊆B, 称(X₁, B₁)为(X, B)的一个近似概念, 其中, X₁为近似概念的外延, B₁为近似概念的内涵.

定义4^[16] 假设(X₁, B₁)、(X₂, B₂)为形式背景(U, A, I)上2个近似概念, 满足X₁⊆X₂, 称(X₁, B₁)为(X₂, B₂)的子概念, (X₂, B₂)为(X₁, B₁)的超概念, 记作(X₁, B₁)≤ (X₂, B₂).关系≤ 表示概念间基于属性的序.形式背景(U, A, I)所有近似概念用这种序组成的集合表示为R(U, A, I), 称为形式背景(U, A, I)上的属性偏序结构图.

定义5^[16] 在形式背景K=(U, A, I)中, 若属性a∈ A满足g(a)=U, 则称属性a为形式背景K的最大共有属性.

定义6^[16] 在形式背景K=(U, A, I)中, 若属性a₀∈ A, a₁∈ A, …, a_k∈ A满足

g(a_t)⊆g(a₀), t=1, 2, …, k, k≥ 2,

则称在形式背景K中, 属性a₀为属性集合{a₁, a₂, …, a_k}的共有属性.

定义7^[16] 在形式背景K=(U, A, I)中, 若属性a∈ A满足|g(a)|=1, 则称属性a为形式背景K的独有属性, 其中|g(a)|表示具有集合g(a)的基数.

最大共有属性、共有属性和独有属性及其关系是构造属性偏序结构图的关键, 基于这3种基本属性特征和基本关系类型的属性偏序结构图构建方法在文献[16]中有详细介绍.下面通过例1直观说明属性偏序结构图.

例1 表1为一个形式背景(U, A, I), 其中, 对象集U={1, 2, …, 6}, 属性集

A={a, b, c, d, e, f, g},

表中× 表示对象具有某属性.根据表1, 构建属性偏序结构图R(U, A, I), 如图1所示, 生成的概念格L(U, A, I)如图2所示.

表1

Table 1

表1(Table 1)

表1 形式背景(U, A, I) Table 1 formal context(U, A, I) U a b c d e f g 1 × × 2 × × 3 × × 4 × × × 5 × × × 6 × ×

表1 形式背景(U, A, I) Table 1 formal context(U, A, I)

对比图1与图2可知, 概念格与APOSD都属于偏序结构, 都是从FCA发展而来.不同之处在于概念格是以概念的外延偏序由大到小建立的偏序结构, 而APOSD是以属性覆盖概念的程度为偏序.在同一形式背景中, 概念格一般会有边的交叉, 而APOSD中边与边之间不交叉.由于两种图形依据的原理和节点定义不同, 在不同的应用问题上具有各自的优势.相比在概念格下进行属性约简任务, 在APOSD下进行属性约简任务不仅可提高构建效率, 而且可在每个属性约简步骤中提供约简图, 从而提高属性约简方法的可解释性.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 属性偏序结构图R(U, A, I)Fig.1 Attribute partial order structure diagram R(U, A, I)

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 概念格L(U, A, I)Fig.2 Concept lattice L(U, A, I)

定义8^[30] 设一个带有逆序对和运算“ '” 的有界格(L, ∨ , ∧ , O, I), L的最大元为I, 最小元为O, 若存在

1)x→ (y→ z)=y→ (x→ z);

2)x→ x=I;

3)x→ y=y'→ x';

4)如果x→ y=y→ x=I, 那么x=y;

5)(x→ y)→ y=(y→ x)→ x;

6)(x∨ y)→ z=(x→ z)∨ (y→ z);

7)(x∧ y)→ z=(x→ z)∧ (y→ z);

那么有界格(L, ∨ , ∧ , ', → , O, I)称为一个格蕴涵代数.

定义9^[30] 设AD_n={h₁, h₂, …, h_n}为含有n个语气算子的集合, h₁< h₂< …< h_n, M_T={c₁, c₂}为具有一对相反意义的语言真值的集合, c₁< c₂, 令

L_{V(n× 2)}=AD_n× M_T,

则称

L_{V(n× 2)}=(L_{V(n× 2)}, ∧ , ∨ , ', → , (h_n, c₁), (h_n, c₂))

为由AD_n和M_T生成的语言真值格蕴涵代数.L_{V(n× 2)}哈斯图如图3所示.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 哈斯图LV(n× 2)Fig.3 Hasse diagram of LV(n× 2)

定义10^[11] 称(U, A, ILV(n×2))为一个模糊语言值形式背景, 其中, U为对象集, A为属性集, ILV(n×2)为U和A之间的模糊语言值关系, 即 ILV(n×2)⊆U× A.对于∀ x_i∈ U, a_i∈ A, 存在

ILV(n×2)(xi, ai)=(hi, cj),

其中(h_i, c_j)∈ LV(n× 2).

定义11^[11] 设(U, A, ILV(n×2))为一个模糊语言值形式背景, λ ∈ ILV(n×2)为模糊语言值信任度, 对于∀ Y⊆U, C⊆A, 定义

Yλ≥={a∈ A|∀ x∈ U, ILV(n×2)(x, a)≥ λ or ILV(n×2)(x, a)‖ λ },

Cλ≥={x∈ U|∀ a∈ A, ILV(n×2)(x, a)≥ λ or ILV(n×2)(x, a)‖ λ },

其中 ILV(n×2)(x, a)‖ λ 表示 ILV(n×2)(x, a)与λ 在LV(n× 2)中不可比.

注 λ 所取的模糊语言值(h_i, c_j)与决策者的风险偏好有关.

对于模糊语言值形式背景(U, A, ILV(n×2)), 若满足 Yλ≥=C且 Cλ≥=Y, 则称(Y, C)为一个模糊语言值分层概念, 其中, Y称为模糊语言值分层概念的外延, C称为模糊语言值分层概念的内涵.

所有模糊语言值分层概念的集合形成一个完备格, 称为(U, A, ILV(n×2))的概念格, 表示为LVLL_λ (U, A, ILV(n×2)).

定义13 设(U, A, ILV(n×2))为模糊语言值形式背景, λ 为模糊语言值信任度, R(U, A, ILV(n×2))_λ 为(U, A, ILV(n×2))在λ 下对应的模糊语言属性偏序结构图.R(U, A, ILV(n×2))_λ 中与最底层节点(A, Ø )连接的节点的集合记为P, 定义映射:

h∶ P→ 2^U,

h((Bm, n, Xm, n))=Xm, n- ∪im+1, i,

其中, (B_{m, n}, X_{m, n})∈ P表示第m层第n个节点, X_{m+1, n}表示(B_{m, n}, X_{m, n})第n个下层节点对应的对象集合, 称映射h为R (U, A, ILV(n×2))_λ 的对象划分映射.集合

U/h={ ∪(Bm, n, Xm, n)∈P(Xm, n- ∪iXm+1, i)P⊆R(U, A, ILV(n×2))λ }

称为R(U, A, ILV(n×2))λ 的对象划分集合, 集合中每个元素表示一类对象划分.

例3 以图5(e)中λ =(h₂, c₂)的属性偏序结构图R(U, A, ILV(n×2))(h2, c2)为例, 与最底层节点(A, Ø )连接的节点的集合P可表示为

P={(abce, 2), (bc, 12), (cd, 45), (acd, 4), (ae, 3)}.

(bc, 12)节点拥有2个下层节点:(abc, 2)和(A, Ø ).(cd, 45)节点拥有2个下层节点:(acd, 4)和(A, Ø ).其余3个节点的下层节点都为(A, Ø ).容易得到R(U, A, ILV(n×2))(h2, c2)的对象划分集合:

U/h={{1}, {2}, {3}, {4}, {5}}.

定义14 设

(U, A1, ( ILV(n×2))1), (U, A2, (ILV(n×2))2)

为2个模糊语言值形式背景, λ ₁、λ ₂为模糊语言值信任度,

R(U, A1, (ILV(n×2))1)λ1, R(U, A2, (ILV(n×2))2)λ2

为2个模糊语言属性偏序结构图, U/h1、U/h2为其对应的对象划分集合.对于∀ X∈ U/h1, 总存在X∈ U/h2, 则称R (U, A1, (ILV(n×2))1)λ1与R(U, A2, (ILV(n×2))2)λ2

类等价, 记作

R (U, A1, (ILV(n×2))1)λ1≃H/h R(U, A2, (ILV(n×2))2)λ2.

定义15 设(U, A, ILV(n×2))为模糊语言值形式背景, λ 为模糊语言值信任度, 如果存在属性子集D⊆A, 使得R(U, D, (ILV(n×2))D)λ ≃H/h R(U, A, ILV(n×2))λ , 则称D为(U, A, ILV(n×2))中λ 下的简化集.若∀ d∈ D, R(U, D-{d}, (ILV(n×2))D-{d})λ ≃H/hR(U, A, ILV(n×2))λ 不成立, 则称D为(U, A, ILV(n×2))中λ 下的约简集, R(U, D, (ILV(n×2))D)λ 为R(U, A, ILV(n×2))λ 的约简图, 其中

(ILV(n×2))D= ILV(n×2)∩ (U× D).

定理1 在模糊语言值形式背景(U, A, ILV(n×2))中, λ 为模糊语言值信任度, 如果存在属性e∈ A, 使得R (U, A-{e}, (ILV(n×2))A-{e})λ ≃H/h R (U, A, ILV(n×2))λ 成立, 当且仅当属性e为(U, A, ILV(n×2))中λ 下的非核心属性.

证明 充分性.设R(U, A, ILV(n×2))λ 对应的对象划分集合为U/h, R (U, A-{e}, (ILV(n×2))A-{e})λ 对应的对象划分集合为U/hA-{e}.若在模糊语言值形式背景(U, A, ILV(n×2))中, 存在属性e∈ A, 使得R(U, A-{e}, (ILV(n×2))A-{e})λ ≃H/h R(U, A, ILV(n×2))λ 成立, 则对于∀ X∈ U/h, 总存在X∈ U/hA-{e}, 即对象分类不变, 属性e可约, 所以e∈ A-∩ Di为(U, A, ILV(n×2))中λ 下的非核心属性.

必要性.若在模糊语言值形式背景(U, A, ILV(n×2))中, 属性e为(U, A, ILV(n×2))中λ 下的非核心属性, 则e∈ A-∩ Di, 其中τ 为一个指标集.由e∈ A-∩ Di可知, 存在约简Di, 使得e∉Di, 即Di⊆A-{e}.由于

R (U, Di, (ILV(n×2))Di)λ ≃H/h R(U, A, ILV(n×2))λ ,

且Di⊆A-{e}, 所以存在

R (U, A-{e}, (ILV(n×2))A-{e})λ ≃H/h R(U, A, ILV(n×2))λ .

得证.

定理2 在模糊语言值形式背景(U, A, ILV(n×2))中, λ 为模糊语言值信任度, R(U, A, ILV(n×2))λ 为(U, A, ILV(n×2))在λ 下对应的模糊语言属性偏序结构图, 其对应的对象划分集合为U/h.若存在属性e∈ A, 使

R (U, A-{e}, (ILV(n×2))A-{e})λ ≃H/h R (U, A, ILV(n×2))λ ,

则一定存在属性集B⊂A, 使得 eλ≥⊆POS(B), e∉B.这里 POS(B)为B的正域, 表示根据属性集B能被准确分入U/h的对象集合.

证明 假设对于∀ B⊂A, 存在e∈ A-B, 使得 eλ≥⊆POS(B)不成立.

因为对于∀ B⊂A, 存在e∈ A-B, 使得 eλ≥⊆POS(B)不成立, 则一定存在U_e⊆ eλ≥未被正确划分入U/h, 即存在Xe∈ U/hA-{e}对∀ X∈ U/h, Xe≠ X.所以R (U, A1, (ILV(n×2))1)λ 与R (U, A2, (ILV(n×2))2)λ 非类等价.这与R(U, A-{e}, (ILV(n×2))A-{e})λ ≃H/h R(U, A, ILV(n×2))λ 矛盾, 假设不成立. 得证.

当模糊语言值形式背景(U, A, ILV(n×2))有n个属性时, 最多能区分2ⁿ个属性, 即约简集中的每个属性及不同的属性组合都能起到区分对象的作用.根据模糊语言属性偏序结构图的构图特点, 该情况在模糊语言属性偏序图中体现为每个节点都向底层节点建立边.由此分析未与底层节点建立边的节点并加以处理, 将属性约简问题转化为在模糊语言属性偏序结构图中使尽可能多的节点向底层节点建立边的问题.

由模糊语言属性偏序结构图的构图步骤可知, 在模糊语言值形式背景(U, A, ILV(n×2))中, 给定模糊语言值信任度λ , 若节点

C_{m, n}=(A_{m, n}, U_{m, n})

与其子节点集合

Φ ={Φ (j)=C_{m+1, j}|j=1, 2, …, M}

满足关系

∪j=1MU_{m+1, j}≠ U_m,

节点C_{m, n}与最底层节点建立边, C_{m, n}表示R(U, A, I)中第m层第n个节点.若节点

C_{m, n}=(A_{m, n}, U_{m, n})

未向底层节点建立边, 为建边需得到

∪j=1MU_{m+1, j}≠ U_m,

可删除C_{m, n}=(A_{m, n}, U_{m, n})及其子节点集合

Φ ={Φ (j)=C_{m+1, j}|j=1, 2, …, M}

中对应属性的差别属性A_{m+1, j}-A_{m, n}.

因此本文的模糊语言属性偏序结构图的逐层属性约简算法(LLAR)的思想是:在保持与FL-APOSD类等价的情况下, 分析删减FL-APOSD中未向底层节点建立边的节点

C_{m, n}=(A_{m, n}, U_{m, n})

及其子节点集合

Φ ={Φ (j)=C_{m+1, j}|j=1, 2, …, M}

中对应属性的差别属性A_{m+1, j}-A_{m, n}.简化FL-APOSD, 直至删除任意属性后的更新图都不与原FL-APOSD类等价, 这样保留的属性组成的集合即为属性约简集.

根据上述分析, LLAR步骤如算法1所示.

算法1 LLAR

输入 模糊语言值形式背景(U, A, ILV(n×2)),

模糊语言值信任度λ

输出 约简图R(U, D, (ILV(n×2))D)λ ,

属性约简集D

构造模糊语言属性偏序结构图R(U, A, ILV(n×2))λ ; 按照从上到下、从左到右的顺序扫描R(U, A, ILV(n×2))λ , 寻找未与底层节点建立边的节点集合

Γ ={Γ (s)=C_{m, n}|s=1, 2, …, N};

令s = 1;

while Γ ≠ Ø

Γ (s)=C_{m, n};

A'← A-(A_{m+1, j}-A_{m, n});

R(U, A', (ILV(n×2))A')λ ← R(U, A, ILV(n×2))λ ;

if R(U, A', (ILV(n×2))A')λ ≃U/h R(U, A, ILV(n×2))λ

根据R (U, A', (ILV(n×2))A')λ 更新Γ 和Φ ;

else

if j≤ M

j++;

else

Γ (s)=Ø ;

end if

end if

end while

return R (U, D, (ILV(n×2))D)λ , D.

算法1的运行时间主要包括如下2部分.

1)R(U, D, (ILV(n×2))D)_λ 的构造.假设模糊语言值形式背景(U, A, ILV(n×2))含有m个对象和n个属性.当计算最大共有属性、共有属性和独有属性, 需要遍历所有属性.因此, 求解R(U, D, (ILV(n×2))D)_λ 需要的时间复杂度为O(n²).

2)约简图与R(U, D, (ILV(n×2))D)_λ 类等价的计算.假定R(U, D, (ILV(n×2))D)_λ 中没有向底层节点建立边的节点个数为o个, 子节点个数为p个.对于未向底层节点建立边的每个节点, 在计算差别属性时, 需要遍历所有的子节点, 需要的时间复杂度为O(o²p).

LLAR的输出结果为约简图

R (U, D, (ILV(n×2))D)λ

与属性约简集D, 根据定理1, 当删除核心属性时, 会造成R(U, D, (ILV(n×2))D)λ 与原始数据产生的模糊语言属性偏序结构图R(U, A, ILV(n×2))λ 非类等价, 即核心属性可起到区分不同对象的作用, 反映到R(U, A, ILV(n×2))λ 中, 删除节点中包含的核心属性信息会使某些节点不会与底层节点建立边.反之, 当删除非核心属性时, R(U, D, (ILV(n×2))D)λ 与R(U, A, ILV(n×2))λ 类等价, 即非核心属性不会起到区分不同对象的作用, 反映到R(U, A, ILV(n×2))λ 中, 删除节点中包含的非核心属性信息不会影响节点与底层节点的连边关系.

通过上述分析可知, 通过遍历所有节点的属性信息以删除节点中的非核心属性信息得到的属性约简集是保持模糊语言属性偏序结构图区分能力不变的最小属性子集.

例4(续例2) 以表2作为LLAR的输入, 并设置模糊语言值信任度λ =(h₂, c₂), 构造模糊语言属性偏序结构图R (U, A, ILV(n×2))(h2, c2), 如图5(e)所示.

1)按照由上到下、由左到右的顺序扫描

R(U, A, ILV(n×2))(h2, c2),

发现首个未向底层节点建立边的节点为(Ø , U), 子节点为(c, 1245)、(a, 3), 由于构图时属性a、c左右位置可能不同, 所以属性集A中可删除属性a或c.

当属性集A删除属性a时, 更新

R(U, A, ILV(n×2))(h2, c2)

为

R(U, A-{a}, (ILV(n×2))A-{a})(h2, c2),

模糊语言属性偏序结构图如图6所示.在图中

R (U, A-{a}, (ILV(n×2))A-{a})(h2, c2)

的对象划分集合为

U/h₁={{1}, {2}, {3}, {4, 5}}.

由定义14可知

R (U, A-{a}, (ILV(n×2))A-{a})(h2, c2)

与R (U, A, ILV(n×2))(h2, c2)非类等价.因此, 属性a不可删除, 转为删除属性c.

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 模糊语言属性偏序结构图R (U, A-{a}, (ILV(n×2))A-{a})(h2, c2)Fig.6 FL-APOSD R (U, A-{a}, (ILV(n×2))A-{a})(h2, c2)

当删除属性c时, 更新R(U, A, ILV(n×2))(h2, c2)为

R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2),

如图7所示.在图中, R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2)的对象划分集合为U/h₂={{1}, {2}, {3}, {4}, {5}}, 因此, R (U, A, ILV(n×2))(h2, c2)与R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2)类等价, 确认删除属性c.

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 模糊语言属性偏序结构图R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2)Fig.7 FL-APOSD R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2)

2)扫描R(U, A-{c}, (ILV(n×2))A-{c})(h2, c2), 发现首个未向底层节点建立边的节点为(a, 234), 删除a, 更新

R(U, A-{c}, (ILV(n×2))A-{c})(h2, c2)

为

R(U, A-{a, c}, (ILV(n×2))A-{a, c})(h2, c2),

模糊语言属性偏序结构图如图8所示.

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 模糊语言属性偏序结构图R (U, A-{a, c}, (ILV(n×2))A-{a, c})(h2, c2)Fig.8 FL-APOSD R (U, A-{a, c}, (ILV(n×2))A-{a, c})(h2, c2)

在图8中R (U, A-{a, c}, (ILV(n×2))A-{a, c})(h2, c2)的对象划分集合为U/h₃={{1}, {2}, {3}, {4, 5}},

可得

R (U, A-{a, c}, (ILV(n×2))A-{a, c})(h2, c2)

与R (U, A, ILV(n×2))(h2, c2)非类等价, 属性a不可删除.继续扫描

R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2),

发现节点(a, 234)的子节点为(ae, 23)、(ad, 4), 可删除属性为e或d.

3)当删除属性e时, 更新

R(U, A-{c}, (ILV(n×2))A-{c})(h2, c2)

为

R(U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2),

模糊语言属性偏序结构图如图9所示.在图中

R(U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2)

的对象划分集合为

U/h₄={{1}, {2}, {3}, {4}, {5}},

因此, R (U, A, ILV(n×2))(h2, c2)与

R (U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2)

类等价, 确认删除属性e.

扫描

R (U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2),

除顶层节点以外, 未发现未向底层节点建立边的节点, 算法结束.输出属性约简集D₁={a, b, d}, 模糊语言属性偏序结构图如图9所示.

图9

Fig.9

	Figure Option ViewDownloadNew Window
	图9 模糊语言属性偏序结构图R (U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2)Fig.9 FL-APOSD R (U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2)

当删除属性d时, 更新

R (U, A-{c}, (ILV(n×2))A-{c})(h2, c2)

为

R (U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2),

模糊语言属性偏序结构图如图10所示.在图中

R (U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2)

的对象划分集合为

U/h₅={{1}, {2}, {3}, {4}, {5}},

因此, 与R(U, A, ILV(n×2))(h2, c2)类等价, 属性d可删除.扫描

R (U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2),

未发现未向底层节点建立边的节点, 算法结束.输出属性约简集D₂={a, b, e}.

图10

Fig.10

	Figure Option ViewDownloadNew Window
	图10 模糊语言属性偏序结构图R (U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2)Fig.10 FL-APOSD R (U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2)

由上述步骤可知, 属性约简集为{a, b, d}和{a, b, e}, 对比R(U, A-{c, d}, (ILV(n×2))A-{c, d})(h2, c2)和R(U, A-{c, e}, (ILV(n×2))A-{c, e})(h2, c2)可知, 属性约简结果不同, 对象的区分方式也有差异.实际上, 多数情况下顶层节点(Ø , U)∈ Γ , 依据本文算法进行属性约简时会首先删减位于第一层节点中的属性.属性所处的节点层越高, 说明包含此属性的对象越多, 在该节点的基础上可区分的对象类别越多.所以通常设置顶层节点(Ø , U)∉Γ , 以保留位于第一层节点中属性, 达到使用较少属性区分较多对象类别的目的.

当在算法中设置(Ø , U)∉Γ 时, 属性约简步骤如下.

1)按照由上到下、由左到右的顺序扫描

R(U, A, ILV(n×2))(h2, c2),

首个发现未向底层节点建立边的节点为(c, 1245), 其子节点有(bc, 12), (cd, 45), 可选择删除属性b或d.

2)当删除属性b时, 更新

R(U, A, ILV(n×2))(h2, c2)

为

R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2),

模糊语言属性偏序结构图如图11所示.在图中,

R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2)

的对象划分集合为

U/h₁={{1}, {2}, {3}, {4}, {5}},

因此

R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2)

与R(U, A, ILV(n×2))(h2, c2)类同构, 确定删除属性b.

图11

Fig.11

	Figure Option ViewDownloadNew Window
	图11 模糊语言属性偏序结构图R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2)Fig.11 FL-APOSD R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2)

3)扫描

R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2), 首个发现未向底层节点建立边的节点为(a, 3), 其子节点为(ae, 3), 可删除属性e, 更新

R(U, A-{b}, (ILV(n×2))A-{b})(h2, c2)

为

R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2),

模糊语言属性偏序结构图如图12所示.在图中

R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2)

的对象划分集合为

U/h₂={{1}, {2}, {3}, {4}, {5}},

R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2)

与R(U, A, ILV(n×2))(h2, c2)类等价, 确定删除属性e.

图12

Fig.12

	Figure Option ViewDownloadNew Window
	图12 模糊语言属性偏序结构图R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2)Fig.12 FL-APOSD R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2)

4)扫描

R(U, A-{b, e}, (ILV(n×2))A-{b, e})(h2, c2),

除顶层节点外, 未发现未向底层节点建立边的节点, 算法结束.输出属性约简集D₃={a, c, d}及其约简图R(U, D₃, (ILV(n×2))D3)(h2, c2).

同理, 当删除属性d时, 最终得到的属性约简结果为D₄={a, b, c}, 模糊语言属性偏序结构图如图13所示.

图13

Fig.13

	Figure Option ViewDownloadNew Window
	图13 模糊语言属性偏序结构图R(U, A-{d, e}, (ILV(n×2))A-{d, e})(h2, c2)Fig.13 FL-APOSD R(U, A-{d, e}, (ILV(n×2))A-{d, e})(h2, c2)

本节通过在真实数据集上实现模糊语言属性偏序结构图在不同模糊语言值信任度λ 上的构建及属性约简, 进而验证LLAR的有效性.

实验环境如下:CPU为Intel(R)Core(TM) i5-10400FCPU@2.90 GHz, 16 GB内存, 软件环境为Windows10下的python 3.9.

使用UCI数据集上的Iris、Glass Identification、Ionosphere、Winequality-Red这4个真实数据集评估LLAR.为了说明LLAR的有效性, 将这4个数据集进行转置, 使其属性数量增多, 更明显表现LLAR的效果.具体数据集信息如表3所示.

表3

Table 3

表3(Table 3)

表3 实验数据集 Table 3 Experimental datasets 名称 样本 特征 连续性 Iris 4 150 是 Glass Identification 9 214 是 Ionosphere 33 351 是 Winequality-Red 11 1599 否

表3 实验数据集 Table 3 Experimental datasets

LLAR可以处理不确定性环境中的多个模糊语言值.将表3中的原始数据集通过模糊语言值信任度λ 转化为模糊语言值形式背景(U, A, ILV(3×2)), 具体如表4所示, 应用六元语言真值格蕴涵代数, 即L_{V(3× 2)}=(L_{V(3× 2)}, ∨ , ∧ , ', → , (h₃, c₁), (h₃, c₂)).

表4

Table 4

表4(Table 4)

表4 模糊语言值形式背景(U, A, ILV(3×2)) Table 4 Fuzzy linguistic-valued formal context (U, A, ILV(3×2)) 形式背景 对象 属性 关系类型 Iris 4 150 模糊语言值(6) Glass Identification 9 214 模糊语言值(6) Ionosphere 33 351 模糊语言值(6) Winequality-Red 11 1599 模糊语言值(6)

表4 模糊语言值形式背景(U, A, ILV(3×2)) Table 4 Fuzzy linguistic-valued formal context (U, A, ILV(3×2))

在4个不同的模糊语言值形式背景(U, A, ILV(3×2))上进行实验, 选取六元语言真值格蕴涵代数中3个不同的模糊语言值作为模糊语言值信任度λ , 并观察λ 的不同取值对模糊语言属性偏序结构图构造的影响.这里选取节点数量与运行时间作为指标观察模糊语言属性偏序结构图构造的情况.

不同模糊语言值信任度λ 下模糊语言属性偏序结构图的指标值变化情况如表5所示.由表可看出, 在模糊语言值形式背景(U, A, ILV(3×2))中, 对于语言真值格蕴涵代数中的不同模糊语言值, 模糊语言值信任度λ 越大, 对象与属性之间的模糊语言值关系越粗, 构造的模糊语言属性偏序结构图规模越小, 即节点数量越少, 算法运行时间越短.反之, 模糊语言值信任度λ 越小, 对象与属性之间的模糊语言值关系越细, 构造的模糊语言属性偏序结构图规模越大, 即节点数量越多, 算法运行时间越长.

表5

Table 5

表5(Table 5)

表5 不同λ 对模糊语言属性偏序结构图的影响 Table 5 Influence of different λ on FL-APOSD 数据集 λ 节点数量 运行时间/s Iris (h3, c2) 90 0.0144 (h1, c1) 153 0.0640 (h1, c2) 197 0.0792 Glass Identification (h3, c2) 236 0.0429 (h1, c1) 677 0.4472 (h1, c2) 452 0.3583 Ionosphere (h3, c2) 1324 1.1174 (h1, c1) 3437 5.6007 (h1, c2) 4533 9.8700 Winequality-Red (h3, c2) 606 0.6512 (h1, c1) 3288 50.5852 (h1, c2) 6165 245.3209

表5 不同λ 对模糊语言属性偏序结构图的影响 Table 5 Influence of different λ on FL-APOSD

为了验证LLAR在属性约简方面的有效性与实用性, 在4个数据集上进行实验, 并记录不同模糊语言值信任度λ 下LLAR的属性约简数量、约简率及运行时间, 具体如表6所示.由表可看出, 在不同模糊语言值形式背景(U, A, ILV(3×2))中, 随着模糊语言值信任度λ 的增大, 对象与属性之间的模糊语言值关系越粗, 属性约简数量越少, 运行时间越短.

表6

Table 6

表6(Table 6)

表6 不同λ 对LLAR属性约简结果的影响 Table 6 Influence of different λ on LLAR attribute reduction results 数据集 λ 属性 数量 约简 数量 约简率 /% 运行 时间/s Iris (h3, c2) 150 77 51.33 0.0182 (h1, c1) 150 105 70.00 0.0703 (h1, c2) 150 99 66.00 0.1079 Glass Identification (h3, c2) 214 106 49.53 0.0609 (h1, c1) 214 165 77.10 0.4771 (h1, c2) 214 194 90.65 0.4613 Ionosphere (h3, c2) 351 92 26.21 1.4021 (h1, c1) 351 297 84.62 6.4741 (h1, c2) 351 286 81.48 11.9974 Winequality-Red (h3, c2) 1599 146 9.13 1.9522 (h1, c1) 1599 1368 85.55 55.6815 (h1, c2) 1599 1420 88.80 272.3314

表6 不同λ 对LLAR属性约简结果的影响 Table 6 Influence of different λ on LLAR attribute reduction results

本文提出LLAR, 删除冗余属性的同时保证R(U, D, (ILV(3×2))D)_λ ≃_H/h R(U, A, ILV(3×2))_λ , 因此依据LLAR输出的集合D即为属性约简集.

本文选择如下属性约简算法进行实验对比:概念格约简方法(Concept Lattice Reduction Approach, CLR)^[33]、SE-ISIAR(Attribute Reduction of SE-ISI Concept Lattices)^[40] 、DM-methods^[39]、DMSRC(Reduct Construction Method Based on Discernibility Matrix Simplification)^[42]、MGLCR(Multi-granularity Linguistic Concept Reduction)^[13] .各算法对比结果如表7所示.

本文在如下4方面上进行对比分析.

1)出发点.相比其它属性约简方法, 只有LLAR是以模糊语言属性偏序结构图为基础进行的属性约简.存在3个模型是以概念格为基础进行的属性约简.在形式背景(U, A, I)中, 构造属性偏序结构图的时间复杂度为O(|A|²), 构造概念格的时间复杂度为O(|U||A|²), 属性偏序结构图的生成效率高于概念格, 更适合应用于属性约简.

SE-ISIAR在三支概念格下进行属性约简, 可同时考虑正面信息与负面信息, 但是构建效率低于概念格.

CLR、SE-ISIAR、DM-methods、DMSRC都无法表达模糊语言值数据, MGLCR与LLAR可表达模糊语言值信息, 但MGLCR使用的模糊语言值会随着属性数量的增多而产生维度爆炸的问题, 并且MGLCR嵌入的模糊语言值数据是语义序关系, 无法表达模糊语言值的不可比性.

LLAR使用的FL-APOSD是由模糊语言值形式背景构建的, 模糊语言值数据通过语言真值格蕴涵代数表示, 可同时处理模糊语言值的可比信息与不可比信息.此外, FL-APOSD的构建效率与可解释性都优于语言概念格.

2)约简原理.由于LLAR是在FL-APOSD下进行的属性约简, 因此, 得到的属性约简结果是保持对象的区别能力不变的最小属性子集.而其它方法是在不同种类的概念格下进行属性约简, 得到的是保持其概念结构不变的最小属性子集.

3)约简图.仅有LLAR可产生约简图, 从而可直接观察对象之间的区分方式, 明确属性约简结果中每个属性的作用. 每个约简过程产生的约简图方便人工纠正约简信息, 提高LLAR的鲁棒性.相比其它基于辨识矩阵的方法, 属性偏序结构图能更完整地表达信息, 有利于部分对象的识别.

4)背景知识.CLR、SE-ISIAR、DM-methods、DM-SRC未使用背景知识.MGLCR将模糊语言值的语义序作为背景知识, 指导语言概念格下的属性约简工作.LLAR在约简每个属性时都充分利用FL-APOSD的节点, 保持与FL-APOSD类等价.在模糊语言值形式背景中, 使用语言真值格蕴涵代数作为模糊语言值的表示模型, 引入模糊语言值的序关系与不可比关系作为背景知识.

此外, 在同个模糊语言值形式背景中, 选取的模糊语言值信任度λ 不同, 产生的FL-APOSD不同.因此, LLAR得到的属性约简结果也不同.可通过选择模糊语言值信任度满足不同风险偏好的决策者对于同一模糊语言值形式背景属性约简结果的不同需要.