粗糙集理论由Pawlak于1982年首次提出[1],它基于一个不可区分二元关系建立信息粒化机制,然后以信息粒为基本单位,通过上下近似算子对概念的不确定性进行表征和度量,以此对数据进行分析,从而发掘数据间的关系及规律。近年来,粗糙集理论在数据挖掘[2]、特征选择[3]和决策分析[4]等方面都具有广泛的应用。
随着传感器技术、互联网和物联网的普及,以及社交媒体等平台的发展,使得数据来源变得更加多样化,数据类型更加复杂,经典粗糙集模型已逐渐无法处理日常生活中的复杂数据。有学者将直觉模糊集与粗糙集相结合,通过正隶属度和负隶属度更准确地描述数据对象之间的模糊性和不确定性。直觉模糊粗糙集相比经典粗糙集具有更强的模糊性处理能力、更丰富的相似性描述、更强的数据处理能力、更全面的特征提取和更强的决策支持能力等优势。为实现直觉模糊信息系统(intuitionistic fuzzy information system,IFIS,记作SIFI)的对象分类,学者基于经典粗糙集的等价关系,通过模糊粗糙集将其推广为模糊等价关系[5]。同时,针对不完备信息系统,一般的等价关系已然不适用,故广义二元关系如相似关系被引入以适应扩展的粗糙集模型[6]。
直觉模糊信息系统由于其出色的复杂数据表征和处理能力而被广泛使用,但由于数据广泛性和模糊性,使得其存在大量的属性冗余,因此属性约简成为直觉模糊信息系统一大关键问题。对于直觉模糊信息系统中的属性约简,近年来众多学者对其进行了系统性的研究,如Tiwari等[7]通过定义一对下近似和上近似,建立了一种新的直觉模糊粗糙集模型以提出基于直觉模糊粗糙集的属性约简方法;李瑞等[8]通过构造直觉模糊决策系统的辨识矩阵,得到基于辨识矩阵的属性约简算法;Anh等[9]基于两个直觉模糊划分之间的距离测度提出了一个属性约简方法。然而,现有的直觉模糊信息系统属性约简方法大多是基于辨识矩阵或代数来定义属性重要度,导致计算复杂度高、时间效率低,而基于信息熵或粗糙熵等不确定性度量对属性重要度进行刻画的研究较少。熵作为一种度量属性重要度的重要方法,由苗夺谦等[10-11]引入经典信息系统并进行了系统研究。对于直觉模糊信息系统,陈曦[12]根据正隶属度和负隶属度定义了信息熵度量,并基于该度量构造了相应的属性约简算法。然而,当前的研究未对直觉模糊信息系统中的相似性度量进行详细讨论,现在针对直觉模糊信息系统的大部分相似性度量方法并不具有单调性,故无法直接使用信息熵对直觉模糊信息系统进行度量。为此,如何针对直觉模糊信息系统建立一种有效的粒化机制,进而构建信息熵、粗糙熵等进行不确定性度量,对实现直觉模糊信息系统的启发式属性约简具有重要意义。
本文基于直觉模糊信息系统中的优势关系建立一种有效的粒化机制,使得在此关系下的信息粒符合粒度单调性,随后利用粗糙熵对直觉模糊信息系统进行不确定性度量,进而刻画属性重要度。在此基础上,设计了直觉模糊信息系统的启发式属性约简方法,并基于UCI数据集从约简长度、分类精度、计算效率等方面进行了算法有效性验证。
1 预备知识
本节回顾直觉模糊信息系统、相似性度量和不确定性度量(信息熵)等相关概念。
1.1 直觉模糊信息系统
定义1[13] 设U={x1,x2,…,xn}为非空有限论域,A*={< (x), (x)>:x∈U}为U上的直觉模糊集,其中 (x), (x)∈[0,1]分别为元素x关于A*的正隶属度与负隶属度,且∀x∈U,0≤ (x)+ (x)≤1,称 (x)=1- (x)- (x)为元素x关于A*的犹豫度。记U上的所有直觉模糊集为SIF(U)。
定义2[14] 记直觉模糊信息系统为SIFI=(U,AT,Va,fa),其中U和AT分别为非空对象集和属性集,Va为属性a∈AT的值域,fa(x)=<μa(x),va(x)>为信息函数,且∀x∈U,a∈AT,0≤μa(x)+va(x)≤1。
1.2 相似性度量
相似性度量可以作为直觉模糊集理论中一种重要的粒化方法,Liang等[14]将犹豫度所携带的信息以及正隶属度和负隶属度的端点距离相结合,提出了一种相似性度量方法。
定义3[14] 令SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,则∀x,y∈U,A⊆AT,x与y关于A的相似度SA(x,y)被定义为
SA(x,y)=1- (|μa(x)-μa(y)|+|va(x)-va(y)|+|μa(x)-va(x)-μa(y)+va(y)|+|πa(x)-πa(y)|+ )。
令0≤λ≤1,A∈AT,则论域U上关于A的相似关系被定义为
={(x,y)∈U×U:SA(x,y)≥λ}。
显然, 具有自反性和对称性,将[x ={y∈U:(x,y)∈ }称为对象x在直觉模糊信息系统中关于A的相似类。
然而,上述相似性度量方法无法保证信息粒度的单调性,即∀A,B⊆AT,若B⊆A,则[x ⊆[x 不一定成立,故不宜使用信息熵对其进行不确定性度量。
1.3 不确定性度量
2 直觉模糊信息系统不确定性度量
本节介绍直觉模糊信息系统下的优势关系和基于信息熵的不确定性度量方法。针对目前相似性度量方法无法实现信息粒度单调性的问题,本文选择利用优势关系对直觉模糊信息系统进行粒化。
定义5 令SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,∀A⊆AT,则关于A的优势关系被定义为
={(x,y)∈U×U:μa(x)≤μa(y), va(x)≥va(y),∀a∈A}。
由此可以定义任意的x∈U关于A的优势类为
[x ={y∈U:(x,y)∈ }。
显然,其具有单调性,即∀A,B⊆AT,若B⊆A,则[x ⊆[x ,因此,可以基于优势关系建立直觉模糊信息系统的不确定性度量。
在直觉模糊信息系统中,由于粒度机制的变化,数据空间的粒不再构成论域的划分,而是转变为一种覆盖,这使得经典信息系统中的熵理论无法直接适用于直觉模糊信息系统。接下来,将定义直觉模糊信息系统中的信息熵和粗糙熵以度量不确定性。
定义6 设SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,∀A⊆AT,其关于A的信息熵和粗糙熵分别被定义为
H(A)=- log2 ,
Er(A)=- log2 。
信息熵与粗糙熵可以对直觉模糊信息系统中关于不同属性集的不确定性进行度量,且二者存在互补关系,具体如下述定理所示。
定理2 设SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,其关于A⊆AT信息熵和粗糙熵分别为H(A)和Er(A),则它们具有如下关系:
H(A)+Er(A)=log2|U|。
证明:由定义6可知
H(A)+Er(A)= + =- log2 =-|U|· log2 =log2|U|。
则定理得证。
定理3 设SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,∀A,B⊆AT,若B⊆A,则有
H(B)≤H(A),Er(A)≤Er(B)。
证明 因为B⊆A,由优势关系的单调性可得[x ⊆[x ,则
- log2 ≥- log2 ,
即可以得到H(B)≥H(A)。
同理,Er(A)≥Er(B)可证。
定理表明,基于更多的属性会得到信息系统更细致的粒化结果,粗糙熵也会随粒度的精细而减小,即直觉模糊信息系统的粗糙熵随属性增加会减小。
例1 表1是根据某公司对5个不同销售区域客户满意度调查整理的一个直觉模糊信息系统SIFI,其中U={x1,x2,x3,x4,x5}表示5 个不同受调区域,AT={a1,a2,a3,a4,a5,a6} 为评价指标。a1为服务质量,a2为价格,a3为送货速度,a4为性价比,a5为售后,a6为产品质量。
表1 客户满意度调查直觉模糊信息系统Tab.1 Intuitionistic fuzzy information system for customer satisfaction survey |
| SIFI | a1 | a2 | a3 | a4 | a5 | a6 |
|---|---|---|---|---|---|---|
| x1 | (0.7, 0.2) | (0.5, 0.3) | (0.5, 0.5) | (0.8, 0.0) | (0.3, 0.3) | (0.9, 0.0) |
| x2 | (0.5, 0.4) | (0.5, 0.4) | (0.1, 0.6) | (0.6, 0.4) | (0.1, 0.6) | (0.3, 0.5) |
| x3 | (0.5, 0.4) | (0.5, 0.5) | (0.7, 0.1) | (0.5, 0.3) | (0.9, 0.0) | (0.1, 0.6) |
| x4 | (0.2, 0.6) | (0.5, 0.3) | (0.3, 0.5) | (0.4, 0.4) | (0.1, 0.8) | (0.2, 0.6) |
| x5 | (0.8, 0.1) | (0.4, 0.5) | (0.6, 0.3) | (0.9, 0.0) | (0.6, 0.3) | (0.5, 0.4) |
对于表1的直觉模糊信息系统,求其关于属性集AT的优势类:
[x1 ={x1},[x2 ={x1,x2},[x3 ={x3},[x4 ={x1,x4},[x5 ={x5}。
基于式(5)可求得关于AT的信息熵
H(AT)= (2.322+1.321+2.322+1.321+2.322)=1.922,
利用式(6)可得关于AT的粗糙熵
Er(AT)= =0.4,
进一步可以验证满足定理2中式(7),即
H(AT)+Er(AT)=log2|U|=2.322。
3 直觉模糊信息系统属性约简
基于优势关系所建立的的粗糙熵,可以对直觉模糊信息系统的不确定性进行度量。通过比较在不同粒度下粗糙熵、判断属性对于整个直觉模糊信息系统的重要性,再基于重要度进行属性约简。本节介绍基于粗糙熵的属性重要度与属性约简与方法。
定义7 设SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,∀A⊆AT,若A满足:
1)Er(AT)=Er(A);
2)∀a∈A,Er(AT)≠Er(A-{a})。
则称A是SIFI的一个约简。
定义8 SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,∀A⊆AT,则关于任意属性a∈A定义相对重要度和b∈(AT-A)定义绝对重要度分别为
sin(a,A)=Er(A-{a})-Er(A),
sout(b,A)=Er(A)-Er(A∪{b})。
相对属性重要度说明了属性的必要性,若sin(a,A)>0,则a是必要的,绝对属性重要度用于选择必要属性之外重要度最大的属性。
定理4 设SIFI=(U,AT,Va,fa)为一个直觉模糊信息系统,若A⊆AT为SIFI的一个约简,当且仅当满足以下条件:
1)Er(AT)=Er(A);
2)∀a∈A,sin(a,A)>0。
证明 若A⊆AT为SIFI的一个约简,则有Er(AT)=Er(A),并且∀a∈A,Er(AT)≠Er(A-{a}),根据定理3,可知∀a∈A,Er(A)≤Er(A-{a}),故∀a∈A,Er(A)<Er(A-{a}),则∀a∈A,sin(a,A)>0,则必要性得证。
若有Er(AT)=Er(A),并且∀a∈A,sin(a,A)>0,则有∀a∈A,Er(AT)≠Er(A-{a}),根据定义7,显然A⊆AT为SIFI的一个约简,则充分性得证。
由于基于辨识矩阵的约简算法复杂度过高,不适用于大规模数据,故本文根据直觉模糊信息系统的属性重要度定义,给出一种基于粗糙熵的直觉模糊信息系统的启发式属性约简算法。其核心思想为首先根据相对属性重要度在直觉模糊信息系统SIFI中选取必要属性,通过对比得到的属性集与AT的粗糙熵判断其是否为一个约简,若不是,则利用绝对属性重要度选取必要属性外重要度最大的属性,直到得到一个约简。算法具体描述如下。
| 算法1 直觉模糊信息系统的启发式属性约简算法 输入:直觉模糊信息系统SIFI=(U,AT,Va,fa) 输出:属性约简R(AT) R(AT)←∅ for i=1,i≤|AT|,i←i+1 do if sin(ai,AT)>0 then R(AT)←R(AT)∪{ai} end if end for while Er(AT)≠Er(R(AT)) do a0← sout(aj,R(AT)) R(AT)←R(AT)∪{a0} end while return R(AT) |
例2 根据算法1计算表1直觉模糊信息系统的属性约简的步骤如下:
1)由优势关系计算优势类,结果如例式1所示。
2)根据式(8)计算属性相对重要度:
sin(a1,AT)=0,sin(a2,AT)=0.234 0,sin(a3,AT)=0,sin(a4,AT)=0,sin(a5,AT)=0,sin(a6,AT)=0。
故R(AT)={a2}。
3)基于粗糙熵进行验证,由于Er(AT)≠Er(R(AT)),故还需继续进行绝对重要度计算。
4)利用式(9) 计算a ∈(AT-a2) 中属性可得
sout(a1,R(AT))=0.864 3,sout(a3,R(AT))=0.864 3,sout(a4,R(AT))=0.981 3,sout(a5,R(AT))=0.981 3,sout(a6,R(AT))=0.581 4。
故R(AT)={a2}∪{a4},继续验证依然有Er(AT)≠Er(R(AT)),所以进行下一步循环,继续基于式(9)进行计算。
sout(a1,R(AT))=0,sout(a3,R(AT))=0.200,sout(a5,R(AT))=0.200,sout(a6,R(AT))=0。
验证可得Er(AT)=Er(R(AT)),故循环终止,输出约简结果R(AT)={a2,a3,a4}。
4 实验分析
为了验证本文提出的直觉模糊信息系统启发式属性约简方法的有效性,选用UCI数据集并通过提出算法对其进行约简,同时与辨识矩阵约简算法对比其分类精度与时间效率。数据集详细信息如表2所示。
表2 UCI数据集Tab.2 UCI datasets |
| 数据集 | 对象数 | 属性数 |
|---|---|---|
| Ionosphere | 351 | 34 |
| HESPE | 145 | 31 |
| Parkinsons | 195 | 22 |
| Glass | 214 | 9 |
| Rice | 3 810 | 7 |
| Page Blocks | 5 473 | 10 |
关于本文算法验证所需的直觉模糊信息系统,采用文献[17]中给出的方法得到正负隶属度
(x)= ,
(x)=1- (x)。
式中:f(x,a)为数据集中对象x关于属性a的值;max(a)和min(a)分别为所有对象关于a的最大值与最小值。随后,将正负隶属度相乘构造犹豫度
εa(x)= (x) (x)。
最后,基于犹豫度对正负隶属度进行调整:
μa(x)= (x)- ,
va(x)=1-μa(x)-εa(x)。
以此方法处理所有数据以得到实验所需的直觉模糊信息系统。针对6 个数据集,利用算法1对其进行属性约简, 并比较其与利用辨识矩阵方法获取的约简长度、分类精度以及计算的时间效率等,其中两种方法获取的约简长度实验结果如表3所示。
表3 启发式算法约简长度Tab.3 Reduce length of heuristic algorithm |
| 数据集 | 对象数 | 属性数 | 约简长度 |
|---|---|---|---|
| Ionosphere | 351 | 34 | 31 |
| HESPE | 145 | 31 | 21 |
| Parkinsons | 195 | 22 | 9 |
| Glass | 214 | 9 | 7 |
| Rice | 3 810 | 7 | 6 |
| Page Blocks | 5 473 | 10 | 6 |
表4 SVM分类精度比较Tab.4 SVM classification accuracy comparison 单位:% |
| 数据集 | 启发式算法 | 辨识矩阵算法 |
|---|---|---|
| Ionosphere | 81.00 | 81.50±1.00 |
| HESPE | 21.00 | 20.65±4.37 |
| Parkinsons | 92.00 | 90.46±0.88 |
| Glass | 65.00 | 64.71±1.38 |
| Rice | 92.00 | 92.00±0.00 |
| Page Blocks | 96.00 | 96.00±0.00 |
表5 时间效率比较Tab.5 Time efficiency comparison |
| 数据集 | 对象数 | 启发式算 法用时/s | 辨识矩阵算 法用时/s |
|---|---|---|---|
| Ionosphere | 351 | 10.07 | 16.53 |
| HESPE | 145 | 8.32 | 343.40 |
| Parkinsons | 195 | 5.06 | 119.39 |
| Glass | 214 | 1.13 | 1.77 |
| Rice | 3 810 | 261.24 | 360.42 |
| Page Blocks | 5 473 | 594.65 | 1 111.97 |
由表5可知,启发式算法在所有数据集上的时间效率都要高于辨识矩阵算法,在对象集较大的数据集上尤为明显,辨识矩阵算法由于其高复杂度,以及其对数据本身的高依赖性,导致了其耗时的不稳定性,启发式算法有效地避免了这种不稳定性并能够在短时间内求得长度最小的约简,弥补了辨识矩阵算法的不足。综合实验结果,本文提出的直觉模糊信息系统的启发式属性约简方法在约简结果、提高分类精度以及优化时间效率方面均展现出很好的有效性。
5 结语
本文基于优势关系在直觉模糊信息系统中建立了粒化机制,解决了普通的相似关系对直觉模糊数据粒化时存在的粒度单调性不成立问题,并通过引入粗糙熵对属性重要度进行度量,用以描述属性对信息粒的影响。为了去除冗余的属性,基于属性重要度设计了一种直觉模糊信息系统启发式属性约简算法,并进行了有效性验证。此算法可获得信息系统中的一个约简,有效地避免了辨识矩阵造成的算法时间消耗过大问题。接下来,将进一步对直觉模糊信息系统的不同粒化机制进行研究,并开展针对多源数据获取、动态知识发现等方面的研究。