第
45
卷
第
10
期
2018
年
10
月
计 算 机 科 学
COMPUTER SCIENCE
Vol.45No.10
Oct.2018
到稿日期
:
2017G08G16
返 修 日 期
:
2017G12G03
本 文 受 国 家 自 然 科 学 基 金
(
61170040
,
61473111
),
河 北 大 学 自 然 科 学 研 究 计 划 项 目
(
799207217069
)
资助
.
李
艳
(
1976-
),
女
,
博士
,
教授
,
CCF
会员
,
主要研究方向为机器学习
、
Rou
g
h
集理论
、
计算智 能
,
EGmail
:
l
y
@hbu.cn
(
通信作 者
);
郭娜娜
(
1992-
),
女
,
硕士生
,
主要研究方向为粒计算 与 知 识 发 现
,
EGmail
:
1498976702@
qq
.com
;
吴 婷 婷
(
1989-
),
女
,
硕 士 生
,
主 要 研 究 方 向 为 粒 计 算 与 知 识
发现
;
湛
燕
(
1978-
),
女
,
副教授
,
主要研究方向为机器学习
.
优势关系下基于浓缩布尔矩阵的属性约简方法
李
艳
郭娜娜
吴婷婷
湛
燕
(
河北大学数学与信息科学学院河北省机器学习与计算智能重点实验室
河北 保定
071002
)
摘
要
在优势关系粗糙集方法
(
DRSA
)
的框 架 下
,
针 对 不 协 调 的 目 标 信 息 系 统 求 属 性 约 简
.
基 于 优 势 矩 阵 的 方 法
是最常用的一类约简方法
,
但矩阵中不是所有的元素都有效
.
浓缩优势矩阵只保留对求约简有用的最小属性集
,
因而
可以明显降低约简过程中的计算量
.
进一步地
,
浓缩布尔矩阵通过布尔代数的形式有效地弥补了优势矩阵生 成 效 率
低的缺点
.
文中将等价关系上的浓缩布尔矩阵属性约简方法扩展到优势关系上
,
针对优势矩阵提出了浓缩布 尔 矩 阵
的概念
,
建立了相应的高效约简方法
,
使效率得到明显提高
.
最后采用
9
组
UCI
数据进行实验
,
结果验证了所提方法
的有效性
.
关键词
粗糙集
,
属性约简
,
优势关系
,
浓缩优势矩阵
,
浓缩布尔矩阵
中图法分类号
TP181
文献标识码
A DOI 10.11896
/
j
.issn.1002G137X.2018.10.042
AttributeReductionBasedonConcentrationBoolean MatrixunderDominanceRelations
LIYan GUO NaGna WUTin
g
Gtin
g
ZHAN Yan
(
Ke
y
LabofMachineLearnin
g
andCom
p
utationalIntelli
g
ence
,
Colle
g
eofMathematicsandInformationScience
,
HebeiUniversit
y
,
Baodin
g
,
Hebei071002
,
China
)
Abstract UndertheframeworkofdominancerelationGbasedrou
g
hseta
pp
roach
(
DRSA
),
attributereductionwasstuG
diedforinconsistenttar
g
etinformations
y
stems.Themethodsbasedondominancematrixarethemostcommonl
y
used
ones
,
butnotallelementsinthematrixarevalid.Theconcentrationdominancematrixonl
yp
reservesthesmallestsetof
attributeswhichareusefulforattributereduction
,
andthusthecom
p
utationalcom
p
lexit
y
canbesi
g
nificantl
y
reduced.
Ontheotherside
,
theconcentrationBooleanmatrixfurtherim
p
rovesthe
g
enerationefficienc
y
ofthedominancematrix
b
y
Booleanal
g
ebra.This
p
a
p
erextendedtheconcentrationBooleanmatrixmethodundere
q
uivalencerelationstothat
underdominancerelations.Theconce
p
tofconcentrationBooleanmatrixwas
p
ro
p
osedforthedominancematrix
,
andthe
corres
p
ondin
g
efficientreductionmethodwasestablishedtoim
p
rovetheefficienc
y
ofthereductional
g
orithm.Finall
y
,
nineUCIdatasetswereusedintheex
p
eriments
,
andtheresultsshowthefeasibilit
y
andeffectivenessofthe
p
ro
p
osed
method.
Ke
y
words Rou
g
hset
,
Attributereduction
,
Dominancerelation
,
Concentrationdominancematrix
,
Concentrationboolean
matrix
1
引言
Rou
g
h
理论
[
1
]
是由
Pawlak
教授于
1982
年提出的一种用
于处理不精确
、
不完全与不相容知识的数学理论
,
近年来被广
泛应用于机器学习
、
数 据 挖 掘 及 模 式 识 别 等 多 个 领 域
.
属 性
约简
[
2G8
]
是粗糙集理论的核心问题之一
,
其中最常用且高效的
方法是基于辨 识 矩 阵 的 方 法
[
9G12
]
.
所 谓 属 性 约 简
,
就 是 在 保
持知 识 库 分 类 能 力 不 变 的 条 件 下
,
发现并去除其中不相关或
不重要的属性
,
从而使知识表示简化
,
又不丢失基本信息
.
目
前为 止
,
许多学者通过不同的方法从不同的角度对知识约简
进行了深入的研究
,
并 取 得 了 很 多 成 果
.
但 这 些 研 究 主 要 是
在等 价 关 系 下 的 信 息 系 统 中 进 行 的
,
而在实际问题中有一些
属性值是有序的
,
比如综合评判问题中的
“
得分
”
属性
,
它的属
性值分为
“
高
、
中
、
低
”,
这 时 往 往 不 能 忽 视 属 性 值 的 偏 好 性 信
息
.
为了解决这 个 问 题
,
Greco
等
[
13G15
]
提 出 了 基 于 优 势 关 系
的粗糙集方法
(
DRSA
),
用 优 势 关 系 代 替 等 价 关 系 来 描 述 属
性值 的 偏 好 顺 序
,
之后在这个框架下取得了一系列的研究成
果
.
文献
[
16G18
]
定义了优势 关 系 下 协 调 目 标 信 息 系 统 的 约
简
,
并给出了相应的优 势 矩 阵 方 法
.
徐 伟 华 等 对 优 势 关 系 下
的不 协 调 目 标 信 息 系 统 做 了 深 入 研 究
,
引入了协调近似空间