差别矩阵约简表示及其快速算法实现_差别矩阵求约简集matlab资源-CSDN文库

175 浏览量 2021-01-13 03:40:05 上传评论收藏 210KB PDF 举报

资源推荐

资源详情

资源评论

第 31 卷第 1 期

Vol. 31 No. 1

控制与决策

Control and Decision

2016 年 1 月

Jan. 2016

差别矩阵约简表示及其快速算法实现

文章编号: 1001-0920 (2016) 01-0012-09 DOI: 10.13195/j.kzyjc.2014.1809

葛浩

1a,2

, 李龙澍

, 杨传健

(1. 滁州学院 a. 电子与电气工程学院， b. 计算机与信息工程学院，安徽滁州 239000;

2. 安徽大学计算智能与信号处理教育部重点实验室，合肥 230601)

摘要: 差别矩阵可以拥有不同的信息, 根据差别矩阵描述的区分信息量不同, 给出 4 种差别矩阵定义, 并提出相

应 H-约简、S-约简、B-约简和 P-约简的概念; 研究 4 种约简之间的关系, 构建通用约简算法模型. 为了提高约简算法

的效率, 给出相对分辨能力约简定义 (RD-约简), 揭示相对分辨能力约简与 4 种差别矩阵约简之间的等价性, 进而设

计相对分辨能力快速约简算法. 最后, 通过实例和 UCI 数据集验证了所提出约简算法的有效性和时空性能.

关键词: 粗糙集；差别矩阵；分辨能力；核属性；约简

中图分类号: TP181 文献标志码: A

Discernibility matrix-based reduct representation and quick algorithms

GE Hao

1a,2

, LI Long-shu

, YANG Chuan-jian

(1a. School of Electronic and Electrical Engineering，1b. School of Computer and Information Engineering，Chuzhou

University，Chuzhou 239000，China；2. Key Laboratory of Computation Intelligence and Signal Processing of Ministry

of Education，Anhui University，Hefei 230601，China. Correspondent：GE Hao，E-mail：togehao@126.com)

Abstract: The discernibility matrix can possess different information. In this paper, according to different discernible

information quantity, four descriptions of the discernibility matrix are proposed, and the four reduct deﬁnitions, i.e., H-

reduct, S-reduct, B-reduct and P-reduct are presented. The relationship and equivalence for four reducts are researched,

and two general reduction algorithms are designed. In order to improve the efﬁciency of the reduction algorithm, the related

concepts of the relative discernibility-based reduct(denoted as RD-reduct) are proposed. The equivalence between the relative

discernibility-based reduct and four discernibility matrix-based reducts are revealed. Two effective reduction algorithms

based on the relative discernibility are designed. Finally, the example and experiments are used to explain the feasibility and

effectiveness of the proposed algorithms.

Keywords: rough set；discernibility matrix；discernibility；core attributes；attribute reduct

0 引引引言言言

粗糙集理论

[1]

作为一种强有力的软计算工具, 被

广泛应用于决策分析、数据挖掘、机器学习和故障诊

断等方面. 属性约简是粗糙集理论的核心内容之一,

是在保持知识库中某种性质不变的情况下, 删除不相

关和冗余属性, 只保留能够保持该特性的最小属性集.

许多学者对粗糙集约简方法进行研究, 并取得了较好

的结果

[2-4]

约简定义与维持目标特性息息相关, 对于不同的

目的, 约简的概念和性质则不同, 获得的约简结果未

必一样. 因此, Miao 等

[5]

指出约简无所谓对错, 约简的

标准不同, 约简结果不一定相同. Pawlak

[1]

给出的是

正域约简概念, 它保持了知识库正区域的不变性. 杨

明

[6]

提出了正域差别矩阵构建方法, 并设计了正域约

简求解算法. 根据 Skowron 差别矩阵

[7]

, Hu 等

[8]

设计

了差别矩阵约简方法, 它保持了知识库分辨能力的不

变性. Kryzkiewicz

[9]

提出了分布约简和分配约简的概

念, 前者保持了每个对象在决策类的隶属度不变, 后

者保持了每个对象可能的决策类不变. 张文修等

[10]

在

Kryzkiewicz 研究的基础上提出了最大分布约简的概

念, 该约简保持了对象最大决策类的不变性. Miao

等

[5]

针对不协调决策表提出了正域约简、决策约简和

收稿日期: 2014-11-29；修回日期: 2015-02-07.

基金项目: 国家自然科学基金项目(51307011, 61402005)；安徽省自然科学基金项目(1308085QF114, 1508085MF126,

1508085MF127)；安徽省高等学校省级自然科学研究项目(KJ2013A015, KJ2012A212)；滁州学院科技优秀

人才基金重点项目(2013RC003)；计算智能与信号处理教育部重点实验室开放课题基金项目.

作者简介: 葛浩(1976−), 男, 副教授, 博士生, 从事数据挖掘、粒计算和粗糙集的研究；李龙澍(1956−), 男, 教授, 博士

生导师, 从事不精确信息处理、智能软件等研究.

第 1 期

葛浩等: 差别矩阵约简表示及其快速算法实现

关系约简, 并针对这些约简给出一个统一的约简框

架. Zhou 等

[11]

研究了 13 种约简以及它们之间的关系,

指出 13 种约简中对不协调决策表存在 6 种约简, 协调

决策表上仅存在 2 种约简. 针对不完备决策表, Meng

等

[12]

研究了 8 种约简及其之间的关系, 指出本质上只

有 5 种约简, 并构建分辨函数, 设计了约简求解算法.

为了提高不同约简算法的效率, 蒋云良等

[13]

从条件信

息熵着手, 通过哈希分类实现高效的分布约简算法.

针对分布约简、分配约简和最大分布约简, 为了避免

直接采用定义求解约简的不便, Li 等

[14]

分别针对分

布约简、最大分布约简和分配约简给出新的属性重要

性度量标准, 并设计了 3 种快速约简算法.

上述方法从不同侧面研究在保持决策表某种特

性不变的情况下, 不同约简概念、性质、之间关系, 以

及基于差别矩阵或差别函数的约简实现. 然而, 对于

差别矩阵中可以拥有怎样信息、信息多少与约简表示

形式之间的关系, 并没有给予深入讨论. 本文则从差

别矩阵可含有描述信息不同着手, 定义 4 种差别矩阵,

研究它们之间的关系, 并给出相应约简定义; 同时提

出添加和删除两种策略的通用差别矩阵约简模型. 为

了解决差别矩阵约简算法效率低下的不足, 提出相对

分辨能力约简概念, 研究差别矩阵约简和相对分辨能

力约简之间的关系, 设计快速启发式属性约简算法.

最后通过实例表明了本文方法的有效性, 并利用 UCI

中的数据集对比分析了差别矩阵约简与相对分辨能

力约简的时空性能.

1 差差差别别别矩矩矩阵阵阵及及及其其其属属属性性性约约约简简简

决策表可以表示为 DT = (𝑈, 𝐴 = 𝐶



𝐷, 𝑉, 𝑓).

其中: 𝐴 为属性集, 由条件属性集 𝐶 和决策属性集 𝐷

构成, 且 𝐶



𝐷 = ∅; 𝑉 =



𝑎∈𝐴

𝑉

𝑎

, 𝑉

𝑎

是属性 𝑎 的值域;

𝑓 : 𝑈 × 𝐴 → 𝑉 为信息函数, ∀𝑎 ∈ 𝐴, 𝑥 ∈ 𝑈, 有 𝑓(𝑥, 𝑎)

∈ 𝑉

𝑎

. 设 𝑃 ⊆ 𝐶, IND(𝑃 ) = {(𝑥, 𝑦) ∈ 𝑈 ×𝑈 ∣ 𝑓(𝑥, 𝑎) =

𝑓(𝑦, 𝑎), ∀𝑎 ∈ 𝑃 } 称为 𝑈 的不可区分关系. 不可区分关

系实为等价关系, 含 𝑥 的等价类记为 [𝑥]

𝑃

= {𝑦∣𝑦 ∈ 𝑈,

(𝑥, 𝑦) ∈ IND(𝑃 )}.

1.1 4 种种种差差差别别别矩矩矩阵阵阵

定定定义义义 1 决策表为 DT, 设 𝑅⊆𝐶, 称 𝑀

𝑅

𝐻

={𝑚

𝑅

𝑖𝑗

∣

1 ⩽ 𝑖, 𝑗 ⩽ ∣𝑈∣} 为属性集 𝑅 的 Hu 差别矩阵, 𝑚

𝑅

𝑖𝑗

表示

矩阵中 𝑖 行 𝑗 列的元素, 其满足

𝑚

𝑅

𝑖𝑗











{𝑎∣𝑎 ∈ 𝑅},

𝑓(𝑥

𝑖

, 𝑎) ∕= 𝑓(𝑥

𝑗

, 𝑎)



𝑓(𝑥

𝑖

, 𝐷) ∕= 𝑓(𝑥

𝑗

, 𝐷);

∅, otherwise.

(1)

定定定义义义 2 决策表为 DT, 设 𝑎 ∈ 𝐶, 称 𝑀

{𝑎}

𝐵

={𝜆

𝑎

𝑖𝑗

∣

1 ⩽ 𝑖, 𝑗 ⩽ ∣𝑈∣} 为属性集 𝑎 的布尔差别矩阵, 𝜆

𝑎

𝑖𝑗

表示

矩阵 𝑖 行 𝑗 列的元素, 其满足

𝜆

𝑎

𝑖𝑗







1, 𝑓(𝑥

𝑖

, 𝑎) ∕= 𝑓(𝑥

𝑗

, 𝑎)



𝑓(𝑥

𝑖

, 𝐷) ∕= 𝑓 (𝑥

𝑗

, 𝐷);

0, otherwise.

(2)

定定定义义义 3 决策表为 DT, 设 𝑎 ∈ 𝐶, 属性 𝑎 的布尔

差别矩阵为 𝑀

{𝑎}

𝐵

, 则 𝑀

{𝑎}

𝐵

的势记为 𝑝(𝑎), 其满足

𝑝(𝑎) =

∣𝑈∣



𝑖=1

∣𝑈∣



𝑗=1

𝜆

𝑎

𝑖𝑗

. (3)

𝑝(𝑎) 实际为 𝑀

{𝑎}

𝐵

中 1 的个数, 也称为属性 𝑎 的

频率.

定定定义义义 4 决策表为 DT, 设 𝑅 ⊆ 𝐶, 称 𝑀

𝑅

𝑆

= {𝛿

𝑅

𝑖𝑗

∣

1 ⩽ 𝑖, 𝑗 ⩽ ∣𝑈∣} 为属性集 𝑅 的结构差别矩阵, 𝛿

𝑅

𝑖𝑗

表示

矩阵 𝑖 行 𝑗 列的元素, 其满足

𝛿

𝑅

𝑖𝑗

∣𝑅∣



𝑘=1

𝜆

𝑎

𝑘

𝑖𝑗

, 𝑎

𝑘

∈ 𝑅. (4)

定定定义义义 5 决策表为 DT, 设 𝑅 ⊆ 𝐶, 称 𝑀

𝑅

𝐵

= {𝜆

𝑅

𝑖𝑗

∣

1 ⩽ 𝑖, 𝑗 ⩽ ∣𝑈∣} 为属性集 𝑅 的布尔差别矩阵, 𝜆

𝑅

𝑖𝑗

表示

矩阵 𝑖 行 𝑗 列的元素, 其满足

𝜆

𝑅

𝑖𝑗











1, ∃𝑎 ∈ 𝑅, 𝑓(𝑥

𝑖

, 𝑎) ∕= 𝑓(𝑥

𝑗

, 𝑎)



𝑓(𝑥

𝑖

, 𝐷) ∕= 𝑓 (𝑥

𝑗

, 𝐷);

0, otherwise.

(5)

定定定义义义 6 决策表为 DT, 设 𝑅 ⊆ 𝐶, 属性 𝑅 的布

尔差别矩阵为 𝑀

𝑅

𝐵

, 用 ∣𝑀

𝑅

𝐵

∣ 表示矩阵的势, 其满足

∣𝑀

𝑅

𝐵

∣ =

∣𝑈∣



𝑖=1

∣𝑈∣



𝑗=1

𝜆

𝑅

𝑖𝑗

. (6)

∣𝑀

𝑅

𝐵

∣ 实际为 𝑀

𝑅

𝐵

中非 0 元素的个数 (即 𝑀

𝑅

𝐵

中

元素的累加和).

差别矩阵直观地反映了对象之间的区分关系. 在

上面的描述形式中, 𝑀

𝑅

𝐻

不仅描述了矩阵中某行某列

是否含有元素, 而且还反映了该元素是由哪些属性组

成; 𝑀

𝑅

𝑆

不仅描述了某行某列是否非空, 而且还能描

述该元素由几个属性构成, 但具体由哪些属性组成,

则不明确; 𝑀

𝑅

𝐵

仅能描述某行某列是否非空, 具体由

几个属性构成, 则不明确; ∣𝑀

𝑅

𝐵

∣ 能描述矩阵中非空元

素的数量.

例 1 表 1 为一个决策表, 其中 {𝑎, 𝑏, 𝑐} 为条件属

性 𝐶, 𝐷 为决策属性, 有 4 个样本对象 𝑈 = {𝑥

, 𝑥

𝑥

, 𝑥

设 𝑅 = {𝑎𝑐}, 则有

剩余8页未读，继续阅读

评论收藏

内容反馈

weixin_38631389

粉丝: 6
资源: 891

差别矩阵约简表示及其快速算法实现

一种Hu差别矩阵属性约简的高效算法 (2012年)

基于差别矩阵属性约简算法的改进

基于差别矩阵和属性选择的属性约简算法

基于差别矩阵的属性约减算法

python差别矩阵求约简

J基于C++矩阵类

论文研究-基于改进的差别矩阵的快速属性约简算法.pdf

论文研究-一种快速差别矩阵属性约简算法.pdf

论文研究-基于差别矩阵的属性约简算法及其应用.pdf

基于差别矩阵的属性约简算法 (2006年)

快速傅里叶变换的分析方法

计算方法及MATLAB实现习题集.pdf

算法导论 第三版

计算机数据结构与算法常用英语词汇

算法导论3rd

一个基于差别矩阵的属性约简改进算法* (2009年)

概念格属性约简的准则及其快速约简算法

基于改进差别矩阵的增量式属性约简算法 (2012年)

论文研究-基于信息熵的二进制差别矩阵属性约简算法.pdf

算法概论[Algorithms].pdf

divideandconquer

一种快速的动态属性约简矩阵算法

论文研究-不完备决策表的差别矩阵属性约简算法.pdf

最新资源

算法导论第三版