1、第 59 卷 第 1 期2023 年 1 月南京大学学报（自然科学）（NATURAL SCIENCE）Vol.59,No.1Jan.,2023JOURNAL OF NANJING UNIVERSITY具有多尺度决策的信息系统的最优全局剪枝选择于子淳1,吴伟志1,2*（1.浙江海洋大学信息工程学院,舟山,316022；2.浙江省海洋大数据挖掘与应用重点实验室，浙江海洋大学,舟山,316022）摘要：作为人工智能领域的一个重要方向，粒计算在数据挖掘和知识发现方面的研究呈现较大的优势.针对具有多尺度决策的信息系统的知识获取问题，利用粒度树与剪枝来研究具有多尺度决策的信息系统的最优尺度选择问题.首先介
2、绍了粒度树与剪枝的概念，每个属性和决策都有一个粒度树，每个粒度树都有许多不同的局部剪枝，代表特定属性下的尺度选择.不同属性和决策的一个局部剪枝组合形成全局剪枝，从而产生一个混合尺度决策表.其次，给出具有多尺度决策的信息系统基于粒度树与剪枝的最优全局剪枝选择的概念.最后将全局剪枝选择与最优尺度选择进行比较研究，还设计了一个算法来验证该方法的有效性.关键词：粒度树，剪枝，具有多尺度决策的信息系统，粗糙集中图分类号：TP18 文献标志码：AOn selection of optimal cuts in information systems with multiscale decisionsYu Z
3、ichun1,Wu Weizhi1,2*(1.School of Information Engineering，Zhejiang Ocean University，Zhoushan，316022，China；2.Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province，Zhejiang Ocean University，Zhoushan，316022，China)Abstract:As an important direction in research fields of art
4、ificial intelligence，granular computing has great advantages in data mining and knowledge discovery.To solve the problem of knowledge acquisition in information system with multiscale decisions，the optimal scale selection problem of information systems with multiscale decisions is studied by using g
5、ranularity trees and cuts.The concepts of granularity trees and cuts are firstly introduced.Each attribute and decision has a granularity tree，and each granularity tree has many different local cuts，which represent the scale selection methods under a specific attribute.A local cut combination of dif
6、ferent attributes and decision forms a global cut，resulting in a mixed scale decision table.Then，the concept of optimal cuts based on granularity trees and cuts in information systems with multiscale decisions is presented.Finally，a comparative study between optimal cuts and optimal scale selections
7、 is performed and an algorithm is designed to verify the effectiveness of the method.Key words:granularity tree,cut,information systems with multiscale decisions,rough sets粒计算是数据挖掘和知识表示的重要研究领域之一，它模拟人的思维，在不同的粒度层次上观察、分析和解决同一个问题.1979 年 Zadeh1首次提出信息粒化（Information Granulation）的概念，认为人类认知能力可以概括为粒化、组织和因果三个主
8、要特征.1990年 Hobbs2提出粒度（Granularity）DOI：10.13232/ki.jnju.2023.01.002基金项目：国家自然科学基金（61976194，62076221）收稿日期：2022-09-28*通讯联系人，Email：第 1期于子淳，吴伟志：具有多尺度决策的信息系统的最优全局剪枝选择的概念，描述粒计算原型的一些基本特征.粒计算这个概念最早于 1997年由 Lin3提出，之后 Lin4和Yao5阐述了粒计算研究的一些基本问题.迄今为止，已经提出了许多涉及具体应用背景的粒计算模型和方法，而在众多粒计算模型中，粗糙集对粒计算研究的推动和发展起到了重要的作用6-17.粗
9、糙集数据分析中的数据描述结构称为信息系统（Information System）18，又称信息表或对象属性值表.原始的 Pawlak 粗糙集理论利用样本集上的等价类来描述“粒”，用等价关系诱导的划分来粒化数据的样本空间.在传统粗糙集数据分析中，信息系统或决策表中的每一个对象只能取唯一的属性值，这样的信息系统描述的是固定尺度下的对象信息，称为单尺度信息系统.事实上，单一尺度框架下的知识表示以及数据处理方法已远远不能满足实际应用的需求，因而“多粒度”已经成为粒计算研究的重要方向.在粗糙集数据分析方面，多粒度粗糙集模型由 Qian et al19首次提出，其主要思想是通过属性的选择进行交运算或并运算
10、来对数据进行处理，以此为基础，许多针对不同数据背景的多粒度粗糙集模型相继被提出20-21.2011 年，Wu and Leung22首次提出基于多粒度划分的粗糙集数据分析模型，在这种多粒度数据模型下，同一批数据可以被标记为不同的粒度层次，对应的数据描述结构称为多尺度信息系统或多粒度标记信息系统，人们可以根据需求在不同的粒度标记上处理和分析数据.吴伟志等23-27还进一步研究了多尺度框架下其他数据类型的信息粒表示和最优粒度的选择问题.She et al28提出了多粒度决策系统的局部最优粒度选择和规则提取方法.Gu and Wu29-30给出了协调的和不协调的多粒度决策系统中知识获取的算法.Wu
11、et al31又进一步提出不完备多粒度标记粗糙集数据分析模型.Li and Hu32提出一种推广的多尺度数据分析模型，研究了不同属性具有不同粒度标记的多尺度决策系统的最优尺度选择问题，给出两种最优尺度选择方法.最近，Wu and Leung33对广义多尺度决策系统中各种最优尺度组合选择进行比较研究.郑嘉文等34还用熵刻画了多尺度决策系统的最优尺度选择.Li et al35提出用矩阵来表示广义多尺度决策表的最优尺度.然而，以上多尺度信息系统都有一个共同的假设，即系统中的决策属性只有一个尺度，而现实生活中人们可能会遇到决策属性具有多个尺度的数据处理问题，针对这种情况，Huang et al36首次
12、研究协调的具有多尺度决策的信息系统的最优尺度选择问题，并给出两种最优尺度选择算法.值得注意的是，以上关于最优尺度选择方法的研究均有一定局限性：对于多尺度决策表中的每个对象，它在不同属性下具有相同水平的最优尺度22，或对于多尺度决策表中的每个属性，所有对象都具有相同水平的最优尺度32.对此，She et al37从上述两个方面对现有的最优尺度选择方法进行归纳总结，并在每个条件属性构建的粒度树38-39中使用剪枝的概念，由此获得一种混合尺度信息表，其中每个属性的属性值可能在不同的尺度下获得，并引出了一种新的尺度选择方法，称为最优全局剪枝选择.但目前关于最优全局剪枝选择的研究仍有一定局限性：系统中的
13、决策属性只有一个尺度.本文结合文献 31-39 的思路，介绍粒度树与剪枝和具有多尺度决策的信息系统的最优尺度选择的概念，利用粒度树与剪枝来研究具有多尺度决策的信息系统的最优尺度选择问题，并提出具有多尺度决策的信息系统的最优全局剪枝选择概念.1 基础知识 设U是非空论域，U的子集全体记为P()U.对 于A P(U)，A在U中 的 补 集 记 为A，即A=|x U x A.本节简单介绍后面用到的一些基本概念与知识.1.1信息系统一个信息系统为一个二元组(U，A)，其中U=x1，x2，xn为一个非空有限对象集，称为论域；A=a1，a2，am为一个非空有限属性集，使得a A，满足a：U Va，即a(x
14、)Va，x U，其中Va=|a(x)x U称为a的值域.对任意非空子集B A，记：RB=|(x，y)U U a(x)=a(y)，a BRB称为由属性集B导出的不可分辨关系，它将U 13南京大学学报（自然科学）第 59 卷粒化为不可区分集合U/RB=|xBx U，其中，xB是对象x关于属性集B的等价类，即：xB=y U|(x，y)RB从粒计算的角度来看，等价类xB是由属性集B确定的不可分辨元素组成的粒，属性集B将U粒化为不相交的粒族U/RB，它们是近似U的任意子集的基本元素.集合X U关于属性集B A的上近似与下近似分别定义如下：-RB(X)=x U|xB X =|xBxB X （1）-RB(X
15、)=x U|xB X=|xBxB X（2）决策系统，也称为决策信息系统，是一个二元组S=(U，A d)，其中(U，A)是一个信息系统，A称为条件属性集，d A是一个特殊的属性，称为决策属性，它可以看作映射d：U Vd.不失一般性，假设Vd=1，2，r.由决策属性d确定U上的等价关系：Rd=|(x,y)U U d(x)=d(y)（3）它将U划分成不相交的决策类：U/Rd=D1,D2,Dr（4）其中，Dj=x U|d(x)=j，j Vd=1，2，r如 果RA Rd，那 么 称 决 策 系 统S=(U，A d)是协调的，否则称S是不协调的.1.2多尺度决策系统定义 132 一个多尺度决策系统是一个二
16、元组S=(U，A d)，其中，(U，A)=(U，|akjk=1，2，Ij；j=1，2，m)是一个多尺度信息系统，d（d A）是决策属性.这样一个多尺度决策系统可以表示成一个表：S=(U,A d)=(U,|akjk=1,2,Ij;j=1,2,m d)(5)其中，akj：U Vkj是一个满射，Vkj是属性aj在第k个 尺 度 下 的 值 域，对 于j=1，2，m，1 k Ij-1，存 在 一 个 满 射gk，k+1j：Vkj Vk+1j使 得ak+1j=gk，k+1jakj，即：ak+1j(x)=gk,k+1j(akj(x),x U(6)称gk，k+1j是条件属性的信息尺度变换.1.3剪枝定义 237 设：S=(U，A)=(U，|akjk=1，2，Ij；j=1，2，m)是一个多尺度信息系统，则对于属性aj，j1，2，m，可以按照以下方式来构建粒度树Tj：（1）Tj有一个根节点，用aj来标记.除根节点外，树的每个节点都用一个属性属性值对来进行标记，其形式为()akj，vkj()k=1，2，Ij，其中vkj是第k级尺度上akj的属性取值.（2）对于节点的每个标签()akj，vkj，关联一个集合
