Approximation Reduction in Intuitionistic Fuzzy Ordered Decision Information System with Preference Measure

决策表作为一种特殊的信息系统，同时具有条件属性和决策属性，下面给出决策表的相关概念.

令DT=(U，C∪D，F，G)为一个五元组，称I为决策表. 其中U为非空有限对象集，U={x₁，x₂，…，x_n}；C为有限条件属性集；D为有限决策属性集，D={d₁，d₂，…，d_q}；F是U与C的关系集，F={f_i：U→V_i，i≤n}，V_i为a_i的有限值域；G是U与D的关系集，G={g_i：U→V′_j，j≤q}，V′_j为d_j的有限值域.

在决策表的基础上，进一步有直觉模糊决策表.

给定I=(U，C∪{d}，F，G)为决策表，对任意f∈F，g∈G，a∈C和x∈U有：f(x，a)=(μ_a(x)，ν_a(x))，g(x，d)∈R(R为实数集)，其中μ_a(x)和ν_a(x)分别为x(x∈U)在条件属性a下的隶属度和非隶属度，μ_a：U→[0, 1]，ν_a：U→[0, 1]且满足0≤μ_a(x)+ν_a(x)≤1. 若记f(a)={f(x，a)|a∈AT}，称f(a)为U上的直觉模糊集，并称(U，C∪{d}，F，G)为直觉模糊决策表，记作DT_*.

下面给出“偏好度量”的概念，由此便可扩充为直觉模糊偏好度量序决策表.

若DT_*=(U，C∪{d}，F，G)为直觉模糊决策表，x∈U，a∈C，定义对象x对属性a的得分函数为S_a(x)=αμ_a(x)-βν_a(x)-γπ_a(x)，其中μ_a(x)、和ν_a(x)分别为对象x在条件属性a下的隶属度和非隶属度，而π_a(x)表示对象x在条件属性a下的犹豫度，且π_a(x)=1-μ_a(x)-ν_a(x)，权重α，β，γ的值域为[0, 1]，且满足α+β+γ=1. 这里α，β，γ取值都是根据具体的任务需求给定，α为隶属度的权重，越看重隶属度，则α的值越大；β为隶属度的权重，越看重非隶属度，则β的值越大；γ为隶属度的权重，γ的值则可根据α，β的值来确定.

设DT_*=(U，C∪{d}，F，G)为直觉模糊决策表，对任意的a∈C，f∈F，g∈G，x_i，x_j∈U有：

则根据得分函数的大小确立了条件属性上的偏序关系，根据决策属性值的大小确立了决策属性上的偏序关系.

设DT_*=(U，C∪{d}，F，G)为直觉模糊决策表，若存在属性a的值域具有偏序关系，则称该属性a为此系统中的一个准则，由若干个准则组成的集合称为准则集.

定义1   对于直觉模糊决策表DT_*=(U，C∪{d}，F，G)，若C为准则集，则称DT_*为直觉模糊序决策表，记为DT_*^≥(本文只讨论递增偏序关系的情况，递减类似，不再赘述).

定义2   令DT_*^≥=(U，C∪{d}，F，G)为直觉模糊序决策表，记W=(α，β，γ)为偏好向量，则称DT_ω^≥*=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表.

定义3   若DT_ω^≥*=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，对于A⊆C，A≠Ø，属性A的优势关系与决策属性d的优势关系如下：

则称R_A^≥，R_d^≥为直觉模糊偏好度量优势关系. 基于以上优势关系得出优势类的定义为

于是，优势关系的上、下近似定义为

至此，给出了直觉模糊偏好度量序决策表的相关定义，得到了该决策表基于得分函数优势关系的上、下近似.

不同于经典的Pawlak粗糙集理论，本文讨论的直觉模糊偏好度量序决策表所研究的背景关系为偏序关系，而基于偏序关系的优势类构成了论域的覆盖而非划分，因此基于带偏好度量的直觉模糊序决策信息系统的近似约简与经典信息系统下的近似约简也有所不同.

下面给出直觉模糊偏好度量序决策表的上、下近似约简函数及约简.

定义4   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，R_A^≥ω和R_d^≥ω分别是条件属性集A和决策属性集{d}关于偏序关系的偏序类，对A⊆C，x_i∈U，记：

分别称σ_A^≥ω与ρ_A^≥ω为论域U上关于属性集A的上近似函数与下近似函数.

定义5   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，对A⊆C，有：若σ_A^≥ω=σ_C^≥ω，则称A为上近似协调集；若ρ_A^≥ω=ρ_C^≥ω，则称A为下近似协调集. 若A为上近似协调集，且A的任意真子集都不是上近似协调集，则称A为上近似约简；若A为下近似协调集，且A的任意真子集都不是下近似协调集，则称A为下近似约简.

显然，由上面定义可知下述性质成立.

性质1   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，有：

1) 属性子集A是上近似协调集，当且仅当对∀D_n∈U/R_d^≥ω，有$\overline{R_A^{\geqslant \omega}}\left(D_n\right)=\overline{R_C^{\geqslant \omega}}\left(D_n\right)$.

2) 属性子集A是下近似协调集，当且仅当对∀D_n∈U/R_d^≥ω，有$\underline{R_A^{\geqslant \omega}}\left(D_n\right)=\underline{R_C^{\geqslant {\mathit{ω}}}}\left(D_n\right)$.

定理1   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，对A⊆C，有：

1) 当且仅当对∀D_n∈U/R_d^≥ω，x_i∈ $\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)且x_j∉$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)时，∃a_k∈A，使得S_ak(x_i)＜S_ak(x_j)，则A是上近似协调集.

2) 当且仅当对∀D_n∈U/R_d^≥ω，x_i∈$\underline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)且x_j∉$\underline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)时，∃a_k∈A，使得S_ak(x_i)＞S_ak(x_j)，则A是下近似协调集.

该定理说明在协调集中不仅仅只保留了各个决策类中对象的信息，而且还保留了包含不同决策类的对象之间的交互信息，以此来保证约简之后与原决策表信息相对完整.

证   1) 必要性：使用反证法.

假设 ∃D_n∈U/R_d^≥ω，当x_i∈$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)且x_j∉$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)时，对∀a_k∈A，有S_ak(x_i)≥S_ak(x_j)，即x_i∈[x_j]_A^≥ω，故[x_i]_A^≥ω⊆[x_j]_A^≥ω.

由于A为上近似协调集，对∀D_n∈U/R_d^≥ω有$\overline{R_A^{\geqslant \omega}}$(D_n)=$\overline{R_C^{\geqslant }}$(D_n)，所以x_i∈$\overline{R_A^{\geqslant \omega}}$(D_n)，故[x_i]_A^≥ω∩D_n≠Ø. 又因[x_i]_A^≥ω⊆[x_j]_A^≥ω，所以[x_j]_A^≥ω∩D_n≠Ø，得x_j∈$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)，矛盾，得证.

充分性：使用反证法.

假设A不是上近似协调集，则∃D_n∈U/R_d^≥ω，使$\overline{R_A^{\geqslant \omega}}$(D_n)≠$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)，即∃x∈$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)，但x∉$\overline{R_A^{\geqslant \omega}}$(D_n)，故有[x]_C^≥ω∩D_n≠Ø，[x]_A^≥ω∩D_n=Ø.

又因[x]_C^≥ω⊆[x]_A^≥ω，所以[x]_A^≥ω∩D_n≠Ø，矛盾，得证.

2) 与1)同理可证.

由于直接利用定义5求解上、下近似的过程比较复杂，效率低下，所以本节给出求上、下近似约简的具体判别方法，即利用辨识矩阵求上、下近似约简.

定义6   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，记：

定义：

分别称D_σ^≥ω(x_i，x_j)和D_ρ^≥ω(x_i，x_j)为上近似辨识属性集和下近似辨识属性集. 另记：

分别称M_σ^≥ω和M_ρ^≥ω为上近似辨识矩阵和下近似辨识矩阵.

定理2   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，且A⊆C，则有：

1) A是上近似协调集，当且仅当对∀(x_i，x_j)∈ $\overline{D^{\geqslant \omega}}$，有A∩D_σ^≥ω(x_i，x_j)≠Ø.

2) A是下近似协调集，当且仅当对∀(x_i，x_j)∈$\underline{D^{\geqslant \omega}}$，有A∩D_ρ^≥ω(x_i，x_j)≠Ø.

证   1) 必要性：由于A是上近似协调集，则由定理1可得对∀D_n∈U/R_d^≥ω，x_i∈$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)且x_j∉$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)时，∃a_k∈A，使得S_ak(x_i)＜S_ak(x_j)，即对∀(x_i，x_j)∈$\overline{D^{\geqslant \omega}}$时，∃a_k∈A，使得S_ak(x_i)＜S_ak(x_j)，又因A⊆C，故对∀(x_i，x_j)∈$\overline{D^{\geqslant \omega}}$时，有A∩D_σ^≥ω(x_i，x_j)≠Ø，得证.

充分性：因A⊆C，所以对∀(x_i，x_j)∈$\overline{D^{\geqslant \omega}}$，有A∩D_σ^≥ω(x_i，x_j)≠Ø，对∀(x_i，x_j)∈$\overline{D^{\geqslant \omega}}$时，∃a_k∈A，有S_ak(x_i)＜S_ak(x_j)，即对∀D_n∈U/R_d^≥ω，x_i∈$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)且x_j∉$\overline{R_C^{\geqslant {\mathit{ω}}}}$(D_n)时，∃a_k∈A，使得S_ak(x_i)＜S_ak(x_j)，由定理1得A是上近似协调集，得证.

2) 与1)同理可证.

定义7   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，记：

分别称F_σ^≥ω和F_ρ^≥ω为该直觉模糊偏好度量序决策表的上近似辨识函数和下近似辨识函数.

定理3   若DT_*^≥ω=(U，C∪{d}，F，G，W)为直觉模糊偏好度量序决策表，有：

1) 上近似辨识函数F_σ^≥ω的极小析取范式为

记C_σⁿ={a_k|k=1，2，…，q_n}，则所有上近似约简的集合为：{C_σⁿ|n=1，2，…，m}.

2) 下近似辨识函数F_ρ^≥ω的极小析取范式为

记C_ρⁿ={a_k|k=1，2，…，q_n}，则所有下近似约简的集合为：{C_ρⁿ|n=1，2，…，m}.

证   1)对∀(x_i，x_j)∈D^≥，由极小析取范式的定义可得C_σⁿ∩D_σ(x_i，x_j)≠Ø，由定理2得C_σⁿ为上近似协调集. 若由C_σⁿ去掉一个元素得C_σ^n*，则一定存在(x_i，x_j)∈D^≥，使得C_σ^n*∩D_σ(x_i，x_j)≠Ø，因而C_σ^n*不是上近似协调集，故C_σⁿ为上近似约简，而{C_σⁿ|n=1，2，…，m}为所有上近似约简的集合.

2) 与1)同理可证.

通过上文得到了求解直觉模糊偏好度量序决策表近似约简的具体方法，下面通过一个实例来说明具体近似约简的求解过程.

设某艺术公司收到了员工交纳的一批画作，为了考察其价值将作品分成上、中、下3个等级，公司委派10位专家从4个方面(色调、意蕴、画功、风格)对这批画作进行评判，评判结果如表 1所示.

表 1列出的直觉模糊偏好度量序决策表中的直觉模糊数是通过专家的判断确定的. 例如对于画作x₃，要确定其画工a₃的隶属度和非隶属度，让10位专家对其投票，有2位专家觉得画作x₃的画功好，而有7位专家觉得x₃的画工不好，还有1位专家持保留意见，不做评价，这时就可以取画作x₃对画功a₃的隶属度为0.2，非隶属度为0.7，犹豫度为0.1. 而隶属度权重α和非隶属度权重β则是根据不同的问题，不同的需求来设定，这里设定隶属度权重α=0.5，非隶属度权重β=0.3，犹豫度权重γ=1-α-β=0.2.

于是，该公司可建立直觉模糊偏好度量决策表DT_*^≥ω=(U，C∪{d}，F，G，W)，如表 1所示，其中论域U={x₁，x₂，x₃，x₄，x₅，x₆，x₇，x₈}，x_i表示第i幅画作，条件属性集C={a₁，a₂，a₃，a₄}，a₁，a₂，a₃，a₄分别表示属性色调、意蕴、画功、风格，g(x_i，d)∈{1，2，3}，1，2，3表示下、中、上3个等级，W=(0.5，0.3，0.2).

下面分别用定义和辨识矩阵两种不同方法来求解该系统的近似约简.

方法1

计算属性AT下的各优势类：

计算：U/R_d^≥ω={[x_i]_d^≥ω|x_i∈U}={D₁，D₂，D₃}

再求出上、下近似：

如果取A={a₁}，则：

此时

且

所以{a₁}既不是上近似协调集也不是下近似协调集.

如果取A={a₃}，则：

此时

且

所以{a₃}既是上近似协调集，也是下近似协调集.

同理可以验证{a₁，a₂，a₃}，{a₂，a₃，a₄}，{a₁，a₃，a₄}，{a₁，a₃}，{a₂，a₃}，{a₃，a₄}，{a₃}都是上、下近似协调集，而{a₁，a₂，a₄}，{a₁，a₂}，{a₁，a₄}，{a₂，a₄}，{a₁}，{a₂}，{a₄}都不是上、下近似协调集. 由此，根据定义5可以求得该直觉模糊偏好度量序决策表的上近似约简和下近似约简都为{a₃}.

方法2

首先，计算该信息系统的上、下近似辨识矩阵如表 2、表 3所示.

于是，由辨识矩阵可得：

故得出该直觉模糊偏好度量序决策表的上、下近似约简为{a₃}. 与方法1求得的结果一致，这说明了10位专家判断画作好坏的最主要的标准是画功，这也完全符合人们的认知.

通过以上求解过程可以看出，方法2的复杂度明显要小于方法1，方法1相对来看非常繁杂，方法2比较简洁，容易理解.

利用上节给出的直觉模糊偏好度量序决策表近似约简的辨识矩阵方法，进行算法设计(以下近似的约简为例，上近似类似，本文不再赘述)并给出详细数值实验.

算法1   直觉模糊偏好度量序决策表的下近似约简算法

输入：DT_*^≥ω=(U，C∪{d}，F，G，W)

输出：下近似约简Red

1. 选择属性子集Red←Ø，red←Ø；

2. 计算得分函数S_a(x)=αμ_a(x)-βν_a(x)-γπ_a(x)；

3. for i=1 to |U| do

4.     dec←Ø

5.     for j=1 to |U| do

6.       if g(x_i，d)≥g(x_j，d) then

7.         dec←x_j

8.         end if

9.       end for

10.     Dec←Dec∪dec

11.     end for

12. end for //3至12步为求解决策类的过程//

13. for i=1 to |U| do

14.     for j=1 to |U| do

15.       M_ij←Ø

16.       for k in $\underline{R_{A T}^{\geqslant \omega}}$(D) do

17.         if [x_i]_AT^≥ω in k and [x_j]_AT^≥ω not in k then

18.            M_ij←A //(A={a_k∈C|S_ak(x_i)＞S_ak(x_j)})//

19.            break

20.         end if

21.       end for

22.     end for

23. end for //13至23步为求辨识矩阵的过程//

24. for i=1 to |U| do

25.     for j=1 to |U| do

26.       if M_ij≠Ø then

27.         red←red∪M_ij

28.       end if

29.     if i=1 then

30.       Red←red

31.     end if

32.     Red←Red∩red

33.     end for

34. end for //24至34步为根据辨识矩阵求约简的过程//

35. end

下面对算法1的时间复杂度进行分析. 第2步中，要求出每个对象对应属性下的得分函数，故其时间复杂度为O(|U||C|). 第3~12步需要求决策类，时间复杂度为O(|U|²)，第13~23步为求解辨识矩阵的过程，需要遍历辨识矩阵并求解对应位置的元素，所以其时间复杂度为O(|U|²| $\underline{R_{A T}^{\geqslant \omega}}$(D)|). 最后24~34步根据辨识矩阵求约简的过程中遍历搜索辨识矩阵，时间复杂度为O(|U|²). 因此，算法的时间复杂度为O(|U||C|+|U|²+|U|²|$\underline{R_{A T}^{\geqslant \omega}}$(D)|+|U|²).

接下来，我们通过系列实验来验证算法的有效性. 实验使用的计算机的配置如下：CPU为Intel(R) Cor e(TM) i5-6200U @ 2.30GHz，内存为4GB，操作系统为64位Windows 10. 环境采用Python平台. 数据集为UCI machine learning repository的8个数据集，如表 4所示.

根据算法1，求出以上数据集的约简，并使用该约简分别通过KNN和SVM两个分类器进行分类，求出其分类的精度，得到的精度如表 5所示.

通过表 5中的实验结果可以看到，对算法1得到的约简进行分类，不论采用是KNN算法分类还是采用SVM算法分类，分类精度都保持在一个较高的水平，其平均精度分别为78.24和86.61，结果较可观.

本文在序决策表的基础上引入了直觉模糊集以及偏好度量，从而序决策表拓展为直觉模糊偏好度量序决策表. 本文进一步研究了基于直觉模糊偏好度量序决策表的近似约简，并得出了近似约简的判定定理、性质及其辨识矩阵，给出了求解直觉模糊偏好度量序决策表的近似约简的具体方法步骤，最后通过案例对比分析了两种求近似约简的方法，并且通过实际数值实验验证了其有效性，为对这类复杂的决策表进行数据分析提供了新的理论基础.