控制与决策  2020, Vol. 35 Issue (9): 2070-2080  
0

引用本文 [复制中英文]

张清华, 刘凯旋, 高满. 基于代价敏感的粗糙集近似集与粒度寻优算法[J]. 控制与决策, 2020, 35(9): 2070-2080.
[复制中文]
ZHANG Qing-hua, LIU Kai-xuan, GAO Man. Approximation sets of rough sets and granularity optimization algorithm based on cost-sensitive[J]. Control and Decision, 2020, 35(9): 2070-2080. DOI: 10.13195/j.kzyjc.2019.0149.
[复制英文]

基金项目

国家自然科学基金项目(61876201);重庆市研究生科研创新项目(CYS18244)

作者简介

张清华(1974-), 男, 教授, 博士生导师, 从事不确定信息处理、粗糙集与粒计算等研究, E-mail: zhangqh@cqupt.edu.cn;
刘凯旋(1992-), 男, 硕士生, 从事不确定信息处理、粗糙集与粒计算的研究, E-mail: 1025160455@qq.com;
高满(1994-), 男, 硕士生, 从事不确定信息处理、粗糙集与三支决策的研究, E-mail: gaomandaner@qq.com

通讯作者

张清华, E-mail: zhangqh@cqupt.edu.cn

文章历史

收稿日期:2019-02-01
修回日期:2019-04-23
基于代价敏感的粗糙集近似集与粒度寻优算法
张清华 , 刘凯旋 , 高满     
1. 重庆邮电大学计算机科学与技术学院,重庆 400065;
2. 重庆邮电大学计算智能重庆市重点实验室,重庆 400065
摘要:粗糙集的近似集用已有知识粒对不确定性目标概念进行近似描述, 但在构建近似集时并没有考虑数据的代价信息这一实际因素.对此, 首先分析在构建粗糙集的近似集时考虑代价信息的必要性; 然后, 从代价敏感角度构建误分类代价的粗糙集近似集模型, 并分析该模型下求得的近似集的相关性质.为了在多粒度空间中寻找一个合适的粒度空间来对不确定性目标概念进行近似描述, 使误分类代价与测试代价之和尽可能小, 给出属性代价贡献率的定义, 并提出一种代价敏感的粒度寻优算法.实验结果表明, 所提出算法能适用于现有代价认知场景, 并在给定代价场景下求出合理的层次粒度空间结构以及不确定性目标概念的近似集.
关键词粗糙集    近似集    代价敏感    多粒度    粒度寻优    
Approximation sets of rough sets and granularity optimization algorithm based on cost-sensitive
ZHANG Qing-hua , LIU Kai-xuan , GAO Man     
1. School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;
2. Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Abstract: Approximation sets of rough sets use existing knowledge granules to describe the uncertain concept approximately. However, the cost information contained in data have not been considered when constructing the approximation set of the uncertain concept. Therefore, the necessity of considering cost information is analyzed when constructing the approximation sets of rough sets firstly. Then an approximation set model of rough sets of misclassification cost is constructed from the perspective of cost-sensitive, and some properties of this model are discussed in detail. In order to find a suitable granularity space to describe the uncertain concept approximately that can minimize the sum of misclassification cost and test cost as far as possible in multi-granulation spaces, the contribute rate of attribute cost is defined, and the cost-sensitive granularity optimization algorithm is proposed. The experimental results show that the proposed algorithm can be used in existing cost cognition scene. And a reasonable hierarchy granulation space and the approximation set of the uncertain concept can be obtained under the given cost scene.
Keywords: rough sets    approximation sets    cost-sensitive    multi-granularity    granularity optimization    
0 引言

目前, 随着计算机技术以及认知科学的发展, 越来越多的专家学者开始聚焦于不确定性问题的研究.自Zadeh[1]提出模糊集理论以来, 不确定性问题的研究取得了重大突破, 各种处理不确定性问题的理论也随之产生, 例如, Pawlak[2-3]提出的粗糙集理论, 张钹等[4-5]提出的商空间理论, 李德毅等[6-7]提出的云模型理论等.作为处理不确定性问题的重要方法, 这些理论已被广泛地用于人工智能领域.粗糙集理论在处理不确定性问题时, 无需提供所需处理数据集合之外的任何先验知识, 它与模糊集、概率论、证据理论等其他理论有着很强的互补性.因此, 粗糙集已成为一种重要的智能信息处理技术[8-12], 越来越受到广大专家学者的青睐.

为了使粗糙集理论能更好地应用于问题求解中, 许多专家学者从不同角度构建了粗糙集的扩展模型, 如概率粗糙集[13]、模糊粗糙集[14]、决策粗糙集[15-16]、变精度粗糙集[17]、邻域粗糙集[18-19]等.这些模型构建了扩展的Pawlak近似算子, 丰富了粗糙集理论, 但是没有考虑用现有知识粒构建目标概念的近似集[20].为了能用现有知识粒构建一个精确集对不精确集进行近似刻画, 在前期的研究中, 笔者从集合相似度出发, 利用模糊截集提出了粗糙集的近似集模型[20-21], 并且基于该模型在属性约简、图像分割、文本分类等领域取得了一系列成果[22-24], 这些研究扩展了粗糙集理论模型及应用.

现实中, 许多数据都含有代价信息, 将代价信息引入到数据挖掘及机器学习领域中便产生了代价敏感学习方法[25-27].许多专家学者将代价敏感学习运用于粗糙集理论中, 并取得了重要的研究成果[28-33].在代价敏感学习中考虑最多的两种代价为测试代价和误分类代价[34].在前期的粗糙集近似集模型研究中, 实现了利用现有知识粒来构建目标概念的近似集, 但是, 此时构成的近似集必然会存在对象错误划分的情况.由于人类在对现实问题决策时, 往往希望得到的划分结果的误分类代价尽可能小, 考虑到代价这一实际因素, 从集合相似度出发构建的近似集很有可能不适应现实应用的需求.因此, 为使所构建的近似集符合人类实际决策, 基于代价敏感角度, 本文构建一种误分类代价的粗糙集近似集模型, 以保证得到的近似集的误分类代价总和在当前知识空间下最小, 该模型也更加符合人类认知, 在现实场景中具有更好的应用价值.

现实中, 人们往往希望问题求解的精度尽可能高, 并且所产生的误分类代价尽可能低.为了有效降低构建近似集所产生的误分类代价, 人们会考虑引入新的属性来细化当前粒度空间.然而, 现实中属性值的获取需要付出一定的测试代价.尽管随着粒度空间的细化, 所求得的近似集的误分类代价会逐渐降低, 但也会造成测试代价的上升, 而且在不同粒度空间下, 人们的决策结果往往是不同的.为了使在多粒度空间中求得的近似集更加符合人类认知, 出于代价优化的考虑, 应将误分类代价与测试代价综合考虑.测试代价的产生主要是由于边界域对象的不确定性, 通常, 人们为了更精确地对边界域中的对象进行决策划分, 会进一步获取边界域对象的新的属性值, 而引入不同的属性所带来的测试代价是不一样的.为了选取合理的属性细化已知粒度空间, 本文给出属性代价贡献率的定义, 并根据该定义提出代价敏感的粒度寻优算法.该算法可以在不同粒度空间下有效选取合适的属性来细化当前粒度空间, 进而在一个合理的粒度空间下构建目标概念的近似集, 帮助人们从数据中挖掘出具有代价敏感的决策知识.最后, 通过实验表明, 对于同一数据集以及同一目标概念, 在不同的代价场景下将产生不同的层次空间结构, 所得到的近似集也更加符合实际应用场景, 这也是代价敏感的充分体现.

1 相关基本概念

为了能更清楚地对本文进行阐述, 这里首先给出相关的基本概念.

定义1 (决策信息系统)[2]  一个决策信息系统S可以表示为

其中: U是对象全集, 也称为论域; A = CD是属性全集, CD分别为条件属性集和决策属性集; V = 是属性值的集合, Vr表示属性rA的属性值范围, 即属性r的值域; f:U × AV是一个信息函数, 它指定U中每一个对象x的属性值.

定义2 (粗糙集)[2]   给定决策信息系统S=(U,A, V, f), 对于任一对象集合XU和属性集合RC, 当X能用属性子集R确切地描述时, 称XR可定义的. R可定义集称为R精确集, R不可定义集称为R不精确集或R粗糙集.当XR粗糙集时, XR上近似集和R下近似集分别为

(1)
(2)

集合BNDR(X) = R (X) - R (X)称为XR边界域, POSR(X) = R (X)称为XR正域, NEGR(X) = U - R (X)称为XR负域.其中: IND(R)为一个不分明关系(等价关系), IND(R)={ (x, y)|(x, y) ∈ U2, . 是不分明关系IND(R)在U上的划分.

定义3 (粗糙集的近似集)[20]  给定决策信息系统S = (U, A, V, f), 对于任意不确定性目标概念X(XU)和属性子集R(RA), 令

(3)

Rα (X)为Xα近似集.其中:在IND(R)的划分下, μXR(x)表示对于任意的x(xU), x属于集合X的隶属程度, .这里: [x]RU/IND(R), [x]R表示对象x在不分明关系IND(R)上形成的等价类(划分块).

2 基于误分类代价的粗糙集近似集

粗糙集给出了不确定性目标概念的两个边界线, 但它无法给出一个不确定性概念外延的近似描述.粗糙集的α近似集模型实现了用已有知识粒构建目标概念的近似集, 通过对比α与对象x隶属于目标概念X的隶属程度来判定该对象是否可用于对X作近似描述.如图 1所示, 位于边界域中的等价类E1中有6个对象, 其中4个圆形对象属于目标概念X, 2个三角形对象不属于X.假设要求构建X的近似集R0.5(X), 根据E1隶属于X的隶属度, 可知E1R0.5(X), 即E1将被用于对X进行近似描述.

图 1 目标概念的R0.5(X)近似集

现实中, 如果事物出现错误划分, 则必然会因错误划分而付出一定的误分类代价.在前期研究中, 构造目标概念的近似集时并没有考虑误分类代价这一现实因素.考虑这一因素, 本文给出如下误分类代价的决策信息系统.

定义4 (误分类代价的决策信息系统)   一个误分类代价的决策信息系统S可以表示为S=(U, A, V, f, λe).其中: UAVf的定义与定义1中的一致, λe={λx1, λx2, …, λx|U|}, λxi(1≤ i≤ |U|)表示U中对象xi的误分类代价取值.

虽然在给定粒度空间下, 同一等价类中各个对象的属性值一样, 但随着粒度空间的不断细化, 每一个对象都会被区分开来, 因此, 对于论域中的每一个对象, 它们的误分类代价不一定相同.对于对象xiU, 将其误分类代价记为λxi, 如果xiX, 则当它被用来描述X时, λxi = 0;如果xiX, 则当它不被用来描述X时, λxi = 0.等价类Ej的误分类代价记为λEj.

在粗糙集中, 可以清晰地判断正域和负域中的等价类是否属于目标概念, 因此, 在构建R0.5(X)时, 正域和负域中的等价类不产生误分类代价.而对于某一等价块Ej ⊂ BNDR(X), Ej无论是否被用来描述目标概念, 总会产生误分类代价.假设在图 1中, 2个三角形对象的误分类代价之和为λ1, 4个圆形对象的误分类代价之和为λ2, 当λ1 > λ2时, 如果继续将E1用于对X进行近似描述, 则显然是不合理的.因此, 结合实际生产需求, 构建误分类代价的粗糙集近似集模型是非常必要的.对于等价类Ej, 当Ej被用于描述X时, Ej的误分类代价为

(4)

Ej不被用于描述X时, Ej的误分类代价为

(5)

从代价最小化角度出发, 如果λEjY≤λEjN, 则Ej将被用于对X进行近似描述; 否则, Ej将不被用于对X进行近似描述.基于误分类代价的决策信息系统, 本文给出误分类代价的粗糙集近似集的定义.

定义5 (误分类代价的粗糙集近似集)   给定误分类代价的决策信息系统S=(U, A, V, f, λe), 设X是论域上的一个集合(目标概念), RC, 令

其中EiU/IND(R).称R(X)为误分类代价敏感下X的近似集.用λR(X)表示R(X)作为X的近似集而产生的误分类代价, 即, 显然R(X)⊂ R(X) ⊂ R (X).

为了更清晰地阐述误分类代价的粗糙集近似集模型, 下面给出一个例子.

例1  给定如表 1所示的误分类代价的决策信息系统S = (U, A, V, f, λe).其中: U = { x1, x2, …, x10}, X = {x1, x3, x4, x7, x8, x10}, R = { a1, a2, a3}.可知U/IND(R) = { E1, E2, E3, E4}.其中: E1 = { x1}, E2 = { x2, x3, x4}, E3={ x5, x6, x7, x8}, E4={x9, x10}.根据对象中的误分类代价计算得λE1Y < λE1N, λE2Y > λE2N, λE3Y < λE3N, λE4YE4N, 根据定义5可得R(X) = E1E3, 即R(X)={x1, x5, x6, x7, x8}.

表 1 误分类代价的决策信息系统

下面详细讨论R(X)的一些相关运算性质.

性质1  给定误分类代价的决策信息系统S = (U, A, V, f, λe), 设XY是论域上的两个集合, X表示X的补集, RC, 则:

1) R(X) = ~R(~X);

2) 若XY, 则R(X) ⊆ R(Y);

3) R(XY) ⊇ R(X) ∪ R(Y);

4) R(XY) ⊇ R(X) ∩R(Y);

5)~(R(X) ∪ R(Y)) = R(~X) ∩R(~Y);

6)~(R(X) ∩R(Y)) = R(~X) ∪ R(~Y).

证明   1)对于∀ EiU/IND(R), 如果EiR(X), 则Ei notR(X), 可知R(X) ∪ R(X) = U, 即R(X) = R(X), 得证.

2) 对于∀ EiU/IND(R), 因为XY, 所以R (X) ⊆ R (Y).当R (X) = R (Y)时, 如果EiR(X) (Ei notR(X)), 则对于目标概念X而言, λEiY≤λEiNEiY > λEiN); 同样, 对于目标概念Y而言, 显然λEiY≤λEiNEiYEiN)成立, 此时R(X)=R(Y).当R (X) ⊂ R (Y)时, 必然有, 此时, 若∀ Ej不用于对Y进行近似描述, 则R(X) = R(Y)成立; 若∃Ej用于对Y进行近似描述, 则R(X) ⊂ R(Y).因此R(X) ⊆ R(Y), 得证.

3) 因为XXY, 由2)可知R(X) ⊆ R(XY); 同样有R(Y)⊆ R(XY), 因此R(XY)⊇ R(X) ∪ R(Y)显然成立.

4) 同3)可得, 该性质显然成立.

5) 由德·摩根定律可知~(R(X) ∪ R(Y))= ~R(X) ∩ ~R(Y), 由1)可知R(X) ∩ R(Y) = R(~ X) ∩R(~Y), 故~(R(X) ∪ R(Y)) = R(~X) ∩R(~Y), 得证.

6) 同5)可得, 该性质显然成立.

在不同粒度空间下求得的目标概念的误分类代价的近似集不一定相同,下面通过定理1来讨论不同粒度空间下误分类代价的近似集的误分类代价的变化规律.

定理1  给定误分类代价的决策信息系统S=(U, A, V, f, λ e), 令XU, RPC, λR(X)、λP(X)分别表示R(X)与P(X)下产生的误分类代价, 则λ R(X)≥λ P(X).

证明  假设U/IND(R)={E1, E2, …, Ey}, U/IND(P)={F1, F2, ..., Fz}, 由于RPC, 可知U/IND(R)中的任意一个等价类可由U/IND(P)中的一个或多个等价类合并而成.

任取EiU(1 < i < y), 当Ei⊆ POSR(X)或Ei⊆ NEGR(X)时, 不产生误分类代价; 当Ei ⊆ BNDR(X)时, 无论是否将Ei用于对X的近似描述, 都将产生误分类代价.假设Ei={Fj, Fj+1, …, Fj+k}(1≤ j+kz), 如果存在Fj+m⊆ POSP(X)(0≤ mk)或Fj+m⊆ NEGP(X)(0≤ mk), Fj+m不用于对目标概念进行近似描述, 此时Fj+m的误分类代价为0, 则min (λFjY, λFjN)+min (λFj+1Y, λFj+1N)+ …+min(λFj+kY, λFj+kN)≤min (λEiY, λEiN), 此时λ R(X)≥λ P(X)显然成立.当 (Fj+m⊆ BNDP(X))(0≤ mk)时, 可知, 显然, 故, 此时λ R(X)≥λ P(X).综上所述, 当RPC时, λ R(X)≥λ P(X).

定理1表明, 在较细粒度空间下求得X的误分类代价的近似集的误分类代价不大于较粗粒度空间下X的误分类代价的近似集的误分类代价, 这也符合人类认知.

在问题求解中, 可以用R(X)、R(X)和R(X)分别作为X的近似集, 那么采用哪一个集合作为X的近似集将会产生最少的误分类代价?下面将通过定理2说明R(X)作为X的近似集在误分类代价方面的优势.

定理2  给定误分类代价的决策信息系统S = (U, A, V, f, λe), 令XU, RC, λR(X)、λR(X)和λR (X)分别表示R(X)、R (X)和R (X)作为X的近似集时产生的误分类代价, 则λR(X)≤ λR (X), λR(X)≤λR (X).

证明  当用R (X)作为X的近似集时, 误分类代价为当用R (X)作为X的近似集时, 误分类代价为; 当用R(X)作为X的近似集时, 误分类代价为λR(X) = , 显然

即λR(X)≤λR (X), λR(X)≤λR (X).

定理3  给定误分类代价的决策信息系统S=(U, A, V, f, λ e), 令XU, RC, 如果, 则R(X)={R0.5}(X).

证明  当时, λEiY≤λEiN表明|Ei-X|≤|XEi|, 由此可知|XEi|≥|Ei|/2, 即, 所以.又因为R0.5(X)={xXR(x)≥0.5}, 所以R(X)={R0.5(X).

定理3表明, 当论域中所有对象的误分类代价都相等时, X的误分类代价的近似集R(X)将退化为R0.5(X).

本节提出的误分类代价的粗糙集近似集模型中, 可以在给定粒度空间中, 求出误分类代价最小的近似集用于对目标概念进行近似描述, 并且通过对该近似集的分析, 表明了所求得的近似集在代价敏感环境下更符合当前粒度空间下的认知环境.

3 代价敏感的粒度寻优策略

在上节中本文利用现有知识粒构建了目标概念误分类代价的近似集模型.为了进一步减小构建近似集的误分类代价, 只有引入新的属性来细化原有知识空间, 但这也必然会造成测试代价的增加.现实问题求解中, 存在以付出较少测试代价换取降低较大误分类代价的情况, 从而达到降低总代价的目的.但是, 当粒度空间细化到一定程度时, 只能以较大的测试代价的付出换取较小的误分类代价的降低, 此时出于对总代价优化的考虑, 再对粒度空间细化已经没有意义了.因此, 在构建多粒度空间下代价敏感的粗糙集近似集时, 从代价优化的角度出发, 在选取粒度空间时, 需要在误分类代价与测试代价之间寻找一个平衡点, 进而得到一个合适的粒度空间来对目标概念进行近似描述.考虑到测试代价和误分类代价这两种代价信息, 本文将引入Min等[35]提出的测试代价和误分类代价的决策信息系统, 如定义6所示.

定义6 (测试代价和误分类代价的决策信息系统)[35]一个测试代价和误分类代价的决策信息系统S可以表示为S=(U, A, V, f, λ e, λ t).其中: UAVf、{λe}的定义与定义4中的一致, λ t={λa1t, λa2t, …, λa|A|t}, λajt(0≤ j ≤ |A|)表示任意对象获取属性{aj}属性值所需的测试代价.

在给定粒度空间下, 只有边界域对象具有不确定性, 因此, 在对当前粒度空间细化时, 只需要获取边界域对象的属性值, 因而测试代价主要是由边界域元素引起的.在给定粒度空间下, 选取不同的属性, 所花费的测试代价是不同的.那么在当前粒度空间下, 如何选取新的属性从而构建新的粒度空间是一个研究要点.由于人类认知有限, 往往不能精确地给出所需要的属性集以达到代价最优化的目的, 人类只能依赖当前认知体系来细化已有的粒度空间.在对问题进一步细化时, 可以从多角度出发, 即引入不同的属性或属性集.假设当前的粒度空间由属性集R诱导得出, 并且通过新增属性a1a2可以达到问题求解的目的.如果一次性加入属性集{a1, a2}, 则产生的测试代价为(λa1ta2t)BNDR(X); 如果逐步增加属性, 即先增加属性a1, 再增加属性a2, 则产生的测试代价为λa1tBNDR(X)+λa2tBNDRa1(X), 显然(λa1ta2t)BNDR(X)≥λa1tBNDR(X)+λa2tBNDRa1(X).虽然新的粒度空间都是由属性集R∪ {a1, a2}诱导得出的, 但是, 所带来的测试代价却是不一样的.通过逐步增加属性可以使测试代价渐近式增长, 因此在引入新的属性时, 应考虑每次只引入一个属性, 逐步缩减边界域.

由于属性选取引起的边界域动态变化, 不同的属性集下产生的近似集是不同的.属性选取的先后顺序对所求得的粒度空间构建近似集的总代价起关键作用, 因此, 构建合理的属性选取顺序也是非常必要的.现实生活中, 人类在当前认知环境下处理问题时, 总想以最小的付出赢取最大的利益, 即以最小的测试代价尽可能最大地降低误分类代价.基于这一思想, 本文给出属性代价贡献率的定义来对不同粒度空间下的属性进行选取, 以达到属性的合理选取的目的.

定义7 (属性代价贡献率)给定测试代价和误分类代价的决策信息系统S=(U, A, V, f, λ e, λ t), 令XU, RC, aiC-R, R'=R∪{ai}, 则属性ai在属性子集R所构成的粒度空间中的属性代价贡献率为

(6)

ω(R, ai)的物理意义表示在属性集R对应的粒度空间下, 引入属性ai后, ai引起的单位测试代价值的增长所降低的X的近似集的误分类代价值.根据属性代价贡献率这一定义, 在对问题求解时, 可以根据当前粒度空间选取ω (R, ai)值最大的属性来构建更细的粒度空间.基于这一思想, 本文给出一种代价敏感的粒度寻优算法.算法的主要思想是:首先需要初始化一个属性集P = {}.然后, 在条件属性集C中选取属性代价贡献率最大的属性细化当前粒度空间, 标记被选取的属性为pi, 令P = P ∪ { pi}, C = C - { pi}, 判断C是否为空集, 如果不为空集, 则继续在C中选取属性代价贡献率最大的属性细化粒度空间, 直至C为空集.将第1次选取的属性标记为p1, 第2次选取的属性标记为p2, 依次类推, 此时可以根据属性集P中选取属性的先后顺序构建一个层次空间结构, 即P0P1→…→Pn, 其中P0 = { }, P1 = { p1}, Pn = { p1, p2, ..., pn}.用CostPi(X)表示在第i层空间中选取属性所付出的测试代价和构建X的近似集的误分类代价之和.最后, 寻找CostPi(X)值最小所对应的粒度空间作为最优粒度空间, 并在该空间下构建目标概念的误分类代价的近似集.该算法的具体步骤如算法1所示, 算法流程如图 2所示.

图 2 代价敏感的粒度寻优算法流程

算法1  代价敏感的粒度寻优算法.

输入:S=(U, A, V, f, λ e, λ t)及目标概念X;

输出:层次粒度空间结构以及粗糙集X的近似集R(X).

step 1:初始化P = { }, j=1.

step 2:判断C是否为空, 如果为空, 则执行step 6;否则执行step 3.

step 3: for i=1:|C|

计算ω (P, ai);

end for

step4:pj={ai|max(ω(P, ai))}, P=Ppj, C=C-pj, j++.

step 5:判断C是否为空, 如果不为空, 则执行step 3;如果为空, 则执行step 6.

step 6:得到属性序列P0={}, P1={p1},P2={p1, p2}, …, Pn={p1, p2, …, pn}.

step 7:R = { Pi|CostPi(X) = min (CostP0(X), CostP1(X), …, CostPn(X))}, 0≤ in.

step 8:得到层次粒度空间{P1}→ {P2}→...→Pi, 从而得到R(X).

在计算算法的时间复杂度时, 往往以最坏情况计算, 即论域中的每个对象在条件属性和决策属性下得以区分.通过对代价敏感的粒度寻优算法分析可知, 算法的时间复杂度主要是由step 3、step 4以及step 7引起的.在step 3中计算aiω(R, ai)值需要求得λR(X)、λR'(X)以及|BNDR(X)|, 需要分别求属性集R以及R'下的等价划分. step 3需要循环|C|次, 因此, step 3的时间复杂度为O(|C|(|C|-|R|)((|R|+|R'|)|U|2+2|U|+|BNDR(X)||U|)).在step 4中需要找出C-Rω(R, ai)值最大所对应的ai, 每次找最大值的时间复杂度为O(|C-R|), 需要循环|C|次, 因此, step 4的时间复杂度为O(|C||C - R|).在step 7中, 求得的层次粒度空间共有|C|+1层, 需要找出总代价最小的粒度空间, 此时的时间复杂度为O(|C|+1).一般情况下, 对象总数|U|远大于属性个数|C|.综上所述, 代价敏感的粒度寻优算法的时间复杂度为O(|U|2|C|3).

下面通过一个实例来说明本文算法的计算过程.

例2给定如表 2所示的测试代价和误分类代价的决策信息系统S = (U, A, V, f, λt, λe).其中: U = { x1, x2, …, x15}, C = { a1, a2, …, a6}, D={d}.可知U/IND(D)={{x1, x2, x5, x7, x9, x10, x14, x15}, {x3, x4, x6, x8, x11, x12, x13}, 假设X={x3, x4, x6}, x8, x11, x12, x13, 初始化P={}, 此时U/IND(P)={U}, 求得P(X)=∅, CostP(X)=269.

表 2 误分类代价的决策信息系统

为了减小总代价, 需要增加属性以细化当前粒度空间.这时要选取第1个属性, 通过计算可得ω (P, a1)=0, ω (P, a2)=0, ω (P, a3)=3.67, ω (P, a4)= 3.26, ω (P, a5)=2.57, ω (P, a6)=0.09.根据算法1, 第1次选取的属性为a3, 此时P=P∪{a3}={a3}, U/IND(P)={{x1, x2, x3, x4, x13, x14, x15}, {x5, x6, x9, x10, x11, x12}, {x7}, {x8}, 求得P(X)={x8}, CostP(X)=189.接下来选取第2个属性, 通过计算可得ω (P, a1)=0, ω (P, a2)=4.5, ω (P, a4)=2.51, ω (P, a5)=0.84, ω (P, a6)=0.13.根据算法1, 第2次选取的属性为a2, 此时P=P∪{a2}={a3, a2}, U/IND(P)={{x1, x2, x3, x4}, {x5, x6}, {x7}, {x8}, {x9, x10, x11, x12}, {x13, x14, x15}}, 求得P(X)={x1, x2, x3, x4, x5, x6, x8}, CostP(X)=143.5.

依此进行计算, 中间的计算过程不再赘述, 可得后面依次选取的属性为a4a5a1a6.记得到的层次粒度空间结构为P0→ {P1}→ {P2}→ {P3}→ {P4}→ {P5}→ {P6}.其中: P0=∅, {P1}={a3, P2}={a2, a3}, P3={a2, a3, a4}, P4={a2, a3, a4, a5}, P5={a1, a2, a3, a4, a5}, P6={a1, a2, a3, a4, a5, a6}.通过计算可得CostP0(X)=269, CostP1(X)=189, CostP2(X)=143.5, CostP3(X)=103.5, CostP4(X)=114, CostP5(X)=114.2, CostP6(X)=134.2.由于min (CostP0(X), CostP1(X), …, CostP6(X))=CostP3(X), 即当粒度空间细化到由{P3}诱导出的粒度空间时, 总的代价最小.所以{P3}即为要寻找的最优粒度空间, 且所构建出来的层次粒度空间的属性引入序列为{a3}→ {a3, a2}→ {a3, a2, a4}, 在P3下求得的误分类代价的近似集为P3(X)={x3, x4, x5, x6, x8, x11, x12, x13, x14}.

通过例2可以看出, 从代价敏感的角度出发, 可以根据现有信息构建出一个层次粒度空间结构, 并且在这个层次粒度空间结构中可以寻找出测试代价与误分类代价之和最小的粒度空间, 并求出误分类代价的粗糙集近似集.

4 实验及分析

为了验证代价敏感的粒度寻优算法的有效性, 本文从UCI数据集中随机选取3个数据集进行实验, 并且每个数据集在两种不同的代价环境下进行实验.数据集的具体信息如表 3所示.实验所用计算机硬件环境为:内存为8 G, CPU为Intel(R) Core(TM)i5-4590 3.30 GHz.软件环境为Windows10, 64位操作系统, 算法实现的过程使用Matlab2014平台.其中Post-Operative Patient数据集中有3个对象个别属性值缺失, 因此在实验时删除了这3个对象, 并且这3个对象的删除不影响实验的进行.

表 3 数据集信息表

在粒度寻优过程中, 不同的代价参数将诱导出不同的层次粒度空间.因此, 在对以上3个数据集进行实验时, 本文将从不同的代价参数出发, 寻找适应给定代价场景下的合适的粒度空间, 并在该粒度空间下求出目标概念的误分类代价的近似集.

测试代价是由所获取的对象属性值而产生的, 误分类代价是由原本属于某一类的对象因错误划分到另一类而产生的.现实中, 测试代价可以是金钱、时间等多种形式, 例如当人们去医院就诊时, 进行验血、做核磁共振都是获取属性值的过程, 是需要花费一定费用的, 这些费用即为测试代价; 而医生在诊断过程中, 会根据化验结果对病人是否患病进行判断, 如果将原本没有患病的健康人误诊为患病, 则原本健康的人就需要接受治疗, 治疗过程所花费的费用即为误分类代价的一种体现.现实中, 可以用金钱或其他形式来衡量这两种代价参数.由于数据集中没有给定对象的误分类代价以及属性的测试代价, 在进行实验时, 对于对象误分类代价参数的选取, 本文采用随机生成方式, 并且每个数据集将采用两组不同的代价参数进行实验.数据集中的数据根据决策属性可以划分为不同的类别, 在实验过程中, 将选取数据集中的某一类数据作为目标概念.

下面将给出不同数据集进行实验时的代价参数信息. Post-Operative Patient数据集、Liver Disorders数据集、Nursery数据集的两次实验的代价参数分别如表 4表 5表 6所示.其中, 每个数据集的第1组实验每个对象的误分类代价参数均取0 50之间的随机整数值, 第2组实验每个对象的误分类代价参数均取0 200之间的随机整数值.实验的目的是寻求一个合适的粒度空间以求得给定目标概念的近似集, 而整个算法是以代价敏感为出发点, 因此, 在实验结果中将展示各个粒度空间下求得目标概念的误分类代价的近似集的误分类代价, 得到该粒度空间的测试代价以及测试代价与误分类代价之和.由于在实验中, 目标概念中对象数量较大, 在这里就不一一列举目标概念的对象以及求得的目标概念的代价敏感的近似集中的对象, 实验部分将着重展示得到的层次粒度空间结构以及在各个粒度空间下, 求得目标概念代价敏感的近似集的总代价、测试代价和误分类代价.

表 4 Post-Operative Patient数据集代价参数
表 5 Liver Disorders数据集代价参数
表 6 Nursery数据集代价参数

通过使用代价敏感的粒度寻优算法, 将在不同代价参数环境下寻找一个合适的粒度空间, 以达到测试代价与误分类代价之和最大化降低的目的.针对Post-Operative Patient数据集, 实验结果如表 7图 3所示.从实验结果可以看出, 在第1组代价参数下, 粒度空间由属性集{a1, a2, a3, a6, a8}诱导得到且选取属性的顺序为a6a8a2a1a3时, 构建目标概念的代价敏感的近似集时总代价最小, 为623.1;在第2组代数参数下, 选取属性顺序为a8a1a4a2a3a7时, 构建目标概念的代价敏感的近似集时总代价最小, 为1 435.

表 7 Post-Operative Patient数据集下的实验结果
图 3 Post-Operative Patient数据集下两种代价参数的粒度寻优结果

针对Liver Disorders数据集, 实验结果如表 8图 4所示.可以看出, 在第1组代价参数下, 选取属性的顺序为a3a6a1时, 构建目标概念的代价敏感的近似集时总代价最小为2 188;在第2组代数参数下, 选取属性顺序为a2a4a6a3时, 构建目标概念的代价敏感的近似集时总代价最小, 为5 088.

表 8 Liver Disorders数据集下的实验结果
图 4 Liver Disorders数据集下两种代价参数的粒度寻优结果

针对Nursery数据集, 实验结果如图 5表 9所示.可以看出, 在第1组代价参数下, 选取属性的顺序为a8a2a1时, 构建目标概念的代价敏感的近似集时总代价最小, 为74 774;在第2组代数参数下, 选取属性顺序为a8a1a2a5a7a4a3a6时, 构建目标概念的代价敏感的近似集时总代价最小, 为188 128.

图 5 Nursery数据集下两种代价参数的粒度寻优结果
表 9 Nursery数据集下的实验结果

从以上3个数据集的实验结果可以看出, 随着粒度空间的细化, 测试代价逐步增大, 而误分类代价逐步降低, 并且在构建误分类代价的近似集时, 划分正确率呈单调递增, 这与现实生产中的情况相吻合.而针对同一数据集和同一目标概念, 当选取不同的代价参数时, 所得到的层次空间不一定相同, 即便是改变一个代价参数也可能引起整个层次粒度空间结构的改变, 进而得到的目标概念的误分类代价的近似集可能也是不一样的.这种以代价为诱导因子来构建合适的粒度空间也是本文算法代价敏感的体现, 更加符合人类认知.

本文提出的代价敏感的粒度寻优算法是一种启发式寻优算法, 根据该算法可以在给定代价场景下求得当前启发式函数上总代价最小的粒度空间, 并将该粒度空间用于构建给定目标概念的误分类代价的近似集, 但并不能保证所求得的粒度空间下构建目标概念的近似集所产生的测试代价与误分类代价之和是全局最优的.

5 结论

粗糙集理论经过多年的发展, 无论是在理论研究还是实际应用上都取得了许多的成果, 为数据挖掘、机器学习、模式识别等领域提供了重要的理论基础.在前期的研究工作中, 笔者提出了利用当前知识空间中的知识粒构建目标概念的近似集的方法.但是在现实生产中, 代价信息是客观存在的, 在问题求解中决策者需要充分考虑代价这一因素.因此, 本文从误分类代价最小化角度出发, 给出了误分类代价的粗糙集近似集模型, 并讨论了该模型的相关性质.进一步地, 为了能在多粒度空间中寻找一个合适的粒度空间对目标概念进行近似描述, 从而达到减小测试代价与误分类代价之和的目的, 本文给出了属性代价贡献率的定义, 并基于该定义, 给出了一种代价敏感的粒度寻优算法.通过该算法可以求得现有代价环境下的一个合适层次粒度空间结构, 并且能在当前认知环境下选取合理的粒度空间对目标概念进行近似描述, 这种渐近式求解过程符合人们的问题求解策略.最后, 利用UCI数据集对该算法进行了验证, 实验结果表明了该算法的有效性和实用性.这些研究工作进一步完善了粗糙集近似集理论, 丰富了粗糙集理论, 希望该研究工作能够推动不确定性人工智能的发展, 扩展粗糙集理论模型及其应用.

参考文献
[1]
Zadeh L A. Fuzzy sets[J]. Information and Control, 1965, 8(3): 338-353. DOI:10.1016/S0019-9958(65)90241-X
[2]
Pawlak Z. Rough sets[J]. International Journal of Computer Information Sciences, 1982, 11(5): 341-356. DOI:10.1007/BF01001956
[3]
Pawlak Z, Skowron A. Rudiments of rough sets[J]. Information Sciences, 2007, 177(1): 3-27.
[4]
张钹, 张铃. 问题求解的理论及应用[M]. 北京: 清华大学出版社, 2007: 1-399.
(Zhang B, Zhang L. Theory and applications of problem solving[M]. Beijing: Tsinghua University Press, 2007: 1-399.)
[5]
Zhang L, Zhang B. The quotient space theory of problem solving[C]. The 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing. Berlin: Springer, 2003, 2639: 11-15.
[6]
李德毅, 刘常昱, 杜鹢, 等. 不确定性人工智能[J]. 软件学报, 2004, 15(11): 1583-1594.
(Li D Y, Liu C Y, Du Y, et al. Artificial intelligence with uncertainty[J]. Journal of Software, 2004, 15(11): 1583-1594.)
[7]
李德毅, 孟海军, 史雪梅. 隶属云和隶属云发生器[J]. 计算机研究与发展, 1995, 32(6): 15-20.
(Li D Y, Meng H J, Shi X M. Membership cloud and membership cloud generators[J]. Journal of Computer Research and Development, 1995, 32(6): 15-20.)
[8]
王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[J]. 计算机学报, 2009, 32(7): 1229-1246.
(Wang G Y, Yao Y Y, Yu H. A survey on rough set theory and applications[J]. Chinese Journal of Computers, 2009, 32(7): 1229-1246.)
[9]
张文修, 吴伟志. 粗糙集理论介绍和研究综述[J]. 模糊系统与数学, 2000, 14(4): 1-12.
(Zhang W X, Wu W Z. An introduction and a survey for the studies of rough set theory[J]. Fuzzy Systems and Mathematics, 2000, 14(4): 1-12. DOI:10.3969/j.issn.1001-7402.2000.04.001)
[10]
张清华, 胡荣德, 姚龙洋, 等. 基于属性重要度的风险决策粗糙集属性约简[J]. 控制与决策, 2016, 31(7): 1199-1205.
(Zhang Q H, Hu R D, Yao L Y, et al. Risk DTRS attribute reduction based on attribute importance[J]. Control and Decision, 2016, 31(7): 1199-1205.)
[11]
官礼和, 王国胤, 胡峰. 一种基于属性序的决策规则挖掘算法[J]. 控制与决策, 2012, 27(2): 313-316.
(Guan L H, Wang G Y, Hu F. A decision rules mining algorithm based on attribute order[J]. Control and Decision, 2012, 27(2): 313-316.)
[12]
黄恒秋, 曾玲, 黎利辉. 混合值不完备系统的双邻域粗糙集分类方法[J]. 控制与决策, 2018, 33(7): 1207-1214.
(Huang H Q, Zeng L, Li L H. Double-neighborhood rough set classification method in incomplete decision system with hybrid value[J]. Control and Decision, 2018, 33(7): 1207-1214.)
[13]
Ziarko W. Probabilistic rough sets[C]. International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing. Berlin: Springer, 2005: 283-293.
[14]
Didier D, Henri P. Rough fuzzy sets and fuzzy rough sets[J]. International Journal of General Systems, 1990, 17(2/3): 191-209.
[15]
于洪, 王国胤, 姚一豫. 决策粗糙集理论研究现状与展望[J]. 计算机学报, 2015, 38(8): 1628-1639.
(Yu H, Wang G Y, Yao Y Y. Current research and future perspectives on decision-theoretic rough sets[J]. Chinese Journal of Computers, 2015, 38(8): 1628-1639.)
[16]
Yao Y Y. Decision-theoretic rough set models[C]. International Conference on Rough Sets and Knowledge Technology. Berlin: Springer, 2007: 1-12.
[17]
Ziarko W. Variable precision rough set model[J]. Journal of Computer and System Sciences, 1993, 46(1): 39-59. DOI:10.1016/0022-0000(93)90048-2
[18]
Hu Q H, Yu D R, Liu J F, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information Sciences, 2008, 178(18): 3577-3594. DOI:10.1016/j.ins.2008.05.024
[19]
Yang X B, Zhang M, Dou H L, et al. Neighborhood systems-based rough sets in incomplete information system[J]. Knowledge-Based Systems, 2011, 24(6): 858-867. DOI:10.1016/j.knosys.2011.03.007
[20]
张清华, 王国胤, 肖雨. 粗糙集的近似集[J]. 软件学报, 2012, 23(7): 1745-1759.
(Zhang Q H, Wang G Y, Xiao Y. Approximation sets of rough sets[J]. Journal of Software, 2012, 23(7): 1745-1759.)
[21]
张清华, 薛玉斌, 王国胤. 粗糙集的最优近似集[J]. 软件学报, 2016, 27(2): 295-308.
(Zhang Q H, Xue Y B, Wang G Y. Optimal approximation sets of rough sets[J]. Journal of Software, 2016, 27(2): 295-308.)
[22]
姚龙洋, 张清华, 胡帅鹏, 等. 基于近似集与粒子群的粗糙熵图像分割方法[J]. 计算机科学与探索, 2016, 10(5): 699-708.
(Yao L Y, Zhang Q H, Hu S P, et al. Rough entropy for image segmentation based on approximation sets and particle swarm optimization[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 699-708.)
[23]
Zhang Q H, Guo Y L, Xiao Y. Attribute reduction based on approximation set of rough set[J]. Journal of Computational Information Systems, 2014, 10(16): 6859-6866.
[24]
Zhang Q H, Yang J J, Yao L Y. Attribute reduction based on rough approximation set in algebra and information views[J]. IEEE Access, 2016, 4: 5399-5407. DOI:10.1109/ACCESS.2016.2600252
[25]
Yang Q, Wu X D. The 10 challenging problems in data mining research[J]. International Journal of Information Technology and Decision Making, 2006, 5(4): 597-604. DOI:10.1142/S0219622006002258
[26]
Domingos P. MetaCost: A general method for making classifiers cost-sensitive[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle: ACM Press, 1999, 99: 155-164.
[27]
廖淑娇.代价敏感粒计算若干方法的研究[D].成都: 电子科技大学信息与软件工程学院, 2018.
(Liao S J. Research on cost-sensitive granular computing approaches[D]. Chengdu: School of Information and Software Engineering, University of Electronic Science and Technology of China, 2018.) http://cdmd.cnki.com.cn/Article/CDMD-10614-1018974933.htm
[28]
Min F, Hu Q H, Zhu W. Feature selection with test cost constraint[J]. International Journal of Approximate Reasoning, 2014, 55(1): 167-179. DOI:10.1016/j.ijar.2013.04.003
[29]
Min F, He H P, Qian Y H, et al. Test-cost-sensitive attribute reduction[J]. Information Sciences, 2011, 181(22): 4928-4942. DOI:10.1016/j.ins.2011.07.010
[30]
Liao S J, Zhu Q X, Qian Y H, et al. Multi-granularity feature selection on cost-sensitive data with measurement errors and variable costs[J]. Knowledge-Based Systems, 2018, 158: 25-42. DOI:10.1016/j.knosys.2018.05.020
[31]
Yang J, Wang G Y, Zhang Q H, et al. Optimal granularity selection based on cost-sensitive sequential three-way decisions with rough fuzzy sets[J]. Knowledge-Based Systems, 2019, 163: 131-144. DOI:10.1016/j.knosys.2018.08.019
[32]
Yao Y Y, Wong S K M, Lingras P. A decision-theoretic rough set model[J]. Methodologies for Intelligent Systems, 1990, 5: 17-24.
[33]
Yang X B, Qi Y S, Song X N, et al. Test cost sensitive multigranulation rough set: Model and minimal cost selection[J]. Information Sciences, 2013, 250: 184-199. DOI:10.1016/j.ins.2013.06.057
[34]
Hunt E B, Marin J, Stone P J. Experiments in Induction[M]. New York: Academic Press, 1966: 651-653.
[35]
Min F, Zhu W. Minimal cost attribute reduction through backtracking[J]. Communications in Computer and Information Sciences, 2011, 258: 100-107.