（模式识别与智能系统专业论文）次属性原理.pdf

次属性原理：摘要 次属性原理 摘要 目前，一个数据集合常常由许多用户共享。但不同的用户希望从这个数据 库中获得的知识却可能不同。这意昧着我们需要能够根据用户需求从数据库中 挖掘满足用户需求解的有效算法。如果把用户的需求看作是一种语义，那么， 建立在信息系统条件属性集合上的属性序可以理解为描述用户对需求的一种原 语。这样，寻找满足用户需求解的问题可以转变为根据属性序计算w 砌c r 的问 题。属性序作为一种描述用户需求的原语，对从信息系统中寻找用户需要的规 则与例外有着重要的意义。因此，仔细研究属性序与信息系统您如甜之间的关 系，对信息系统解的计算和应用都是必要的。 基于属性序的旭幽“算法已经在文 w w 0 1 仲提出。由于该算法对旭出c f 完备且其输出对给定的属性序唯一，因此可以看作是由属性序集合到陀如甜集 合的一个映射。因为不同的属性序可以对应相同的旭幽c r ，因此这个影射不是一 一的映射。这就产生了一些问题：给定一个坤如甜，哪些属性序与其对应? 对于 两个不同的属性序，是否存在直接判定其旭出“相同的准则? 在一定条件下，是 否可以根据用户的特定需求从已知的解推断其它的解? 本文基于这些问题展开 讨论。主要工作包括以下几个方面： 一、通过形式化属性序旭咖c r 算法，分析了属性序集合和憎幽“集合之间 的关系，证明了邻近属性序偶基本判定定理，给出了一系列直接判定邻近属性 序偶旭出c f 相等的判定规则。 二、提出了次属性原理，并由此构造性地证明了次属性定理。次属性定理 是全文的核心，一方面，它可以作为直接判定由阳幽甜属性向右移动获得的邻 近属性序偶增幽c f 是否相同的判定准则；另一方面，它又可以作为设计任意属 性序偶理幽c f 是否相同判定准则的基础。 三、基于次属性定理和属性范序，设计了直接判定任意属性序偶胛咖甜是 否相同的判定准则，并证明了利用次属性定理可以在属性序集合中确定具有相 同肥幽“的属性序的范围。 四、次属性定理的证明依赖差别矩阵，它暗示的次属性算法的复杂性为 0 ( n 2 m ) 。由于大多数信息系统的对象的个数n 远大于属性的个数m ，即，n m ， 因此，基于属性值树表示，设计了计算复杂度为d 0 m 2 ) 的属性一值树次属性 算法，并证明了它与次属性定理暗示的次属性算法等价。 关键字：属性序，属性一值树表示，陀幽甜，次属性，差别矩阵 垄曼壁璺翌! 些! 堕 t h ep r i n c i p i eo fs e c o n da t t r _ b u t e a b s t r a c t i np r a c t i c e ，m a l l yd a t a s e t sa r es h a r e d 锄o n gm u n i p l eu s e r s h o w c v e r d i 恐r e m u s e r sm a yd e s i r ed i 丘b r e ml m o w l e d g e 行o mt l l ed a t a s e t s t h i sm e a l l st h a tw en e e dt o d e v e l o pe f f i c i e ma l g o r i 也m st a i l o r c dt o d i 丘b r e mu s e rn e e d s i fw ev i e wt h eu s e r s r e q u i r e m e m sa ss o m ef o n no fs e m a n t i cs t m c t i l r e ，a na t 廿i b u t eo r d e r ，b u i l to nt l e c o n d i t i o n 釉m u t e so fn l ei o r n l a t i o ns y s t e m ，c 锄b er e c o g i l l z e da sap r i m i d v e d e s c r i b i n gt 1 1 eu s e r s r c q u i r e m e m s t h u st h ep r o b l e m o ff l n d 访gp e r s o n a l i z e d s o l u t i o n sc a nb et r a n s f b n n e di n t oc o m p u t i l l gt l l e ，曾幽“o na n 时嘶b u t eo r d e lt h e a t m b u t eo r d e r ，a st 1 1 ep r h m v cd e s c r i b i n gt 1 1 eu s e r s r e q u i r e m e n t s ，h a si m p o r t a l l t i m p l i c a t i o n sw i t l l 山eq u e s t f o rr u l e sa n de x c e p t i o n si na 1 1i n f o r r n a t i o ns y s t e m t h e r c f o r e ，“i sc m c i a lt os t u d yt 1 1 er c l a 廿o n s l l i pb e t 、e e nt h ea t 仃i b u t eo r d e ra n d 龇 旭d h “0 fa nm f o h n a t i o ns y s t e m 1 1 圮r 8 幽c fa l g 喊也mb a s e do n 眦i h l t eo r d c rw a sp r o p o s e di n 【w w o l 】t 1 1 i s a l g o r i m mi sc o m p l c t ef o r 肥d “c fa 1 1 du n i q u ef o ra 西v e na t t r i b u t eo r d e r ，t | l u si tc a nb e c o n s i d e r e da sam a p p i n g 舶mt 1 1 es e to f 撕i b u t eo r d e r st ot l l es e to f 阳d “矾t h j s m 印p i n gi sn o to n e t o o n e ，s i n c ed i f l e r e n ta t 仃i b u t eo r d e r sc a l ly i e l dt l l es a 芏n er e d u c t r 1 1 1 i sr c i n a r kg i v e sr i s et os e v e r a lq u e s t i o n s g i v e na 阳幽c f ，w h i c h 抛i b u t eo r d e r sc a l l y i e l di t ? g i v e nt w od i 任b r e n ta t 埘b u t eo r d e r s ，i st h e r cac r i t e r i o nt od e t e m _ l i n e 、v h e t h e r t h e i r 阳d h c 捃盯et 1 1 es 锄e ? c 趾w ei n f e rn e w p c r s 伽融i z e ds 0 1 u t i o n s 丘o m 锄e x i s t i l l g s 0 1 u t i o n ，u n d e rs o m er e g u l a r i t yc o n d m o n s ? t h i sa r t i c l ei sm o t i v a t e do nt 1 1 e s e p m b l e m s t h em a i nc o m r i b u t i o n so f 也i sa r t i c l ea r e ： 1 b yf o m a l i z i n g 吐1 e 肥如c fa l g o i i 也mo na t 晡b u t eo r d e r ，t 1 1 er e l a t i o nb e t w e e n 也es e to fa 七t r i b u t eo r d e r sa n dt l l es c to f 旭西z c 括w 弱a n a l y z e da n das e r i e so f c r i t e r i at o d e t c n n i n ew h e t l l e rn e i g h b o r i n g 砌b u t eo r d e r sy i e l d 血es 锄e 旭出dw e r eg i v e n 2 1 1 1 ep r i n c i p l eo fs e c o n da 拊i b u t e 、v a sp r o p o s e da n dt h cs e c o n da 蜘b u t e t 1 1 e o r e mw a sp r 0 v e nc o n s 仇l c t i v e l y t h es e c o r da t t r i b u t et 坨o r e mi s 也ec o r eo ft h i s a r t i c l e ，i tc a nb ee x p l o i t e di 1 1t 、v ow a y s ：a sad i r e c tc r i t e r i o nt oj u d g i n gw h e t h e r 也e i 次属性原理 s 锄e 旭如甜、a sy i e l d e dw h e nn e i 曲b o r i n ga _ 七t 啪u t eo r d e r sh a db c e nc o n s t n l c t e db y m o v i n g 比如甜砌b u t e st ot 1 1 er i g h t ，a i l da sab a s i sf o rd e s i g l l i n gc r i t e r i af o rj u d 百n g w h e t h e rt 、oa r b i t r a r ya _ 心i b u t eo r d e r sy i e l dt l l es 锄e 圮击f c f 3 t h cc r i t e r i ad i r e c n yj u d g i l l gw b e t l l e rt 、v oa r b i 呻抛i b u t eo r d e r sy i e l dt h e s a i n er e d u c t 、盯ed e s i g n e do nm es e c o n do r d e rm e o r 锄a 1 1 dn o 珊a l 删b u t e0 r d e r a n di tw a sp m v e nt l l a tt 1 1 es e c o n d 砌b u t et 1 1 e o r e mc a l lb eu s e dt od e t e m l i n et 1 1 e m n g eo f 删b u t eo r d e r s 、：i l i c hy i e l dm es a m em 击l c r 4 t h ep r o o fo ft 1 1 es e c o n d 啪i b u t et h e o r e mw a sb a s e do nd i s c e m i b i l i t ym a 蝻x ， t 1 1 u s 血ea l g o m h mi t i m p l i e d h a sat i m e c o m p l e x i t yo f0 ( 胆2 m ) s i n c em o s t i n f o n n a t i o ns y s 胁sh a v em o r eo b j e c t st l l a na t 啊b u t e s ( n m ) ，a na l g o r i m mo f c o n l p l e x i 哆。( h 卅2 ) w a sd e s i g n e d 趾dp r o v e ne q u i v a l e n tw i t l l l cs e c o n d 砌b u t e a l g o r i t l l mi m p l i e db ym es e c o n d 砌b u t et h e o r e m k e y w o r d s ：a t t m u t eo r d e r ，a 蜘b u t e - v a l u et r e er e p r e s e n 诅t i o n ，旭如c f ，s e c o n d a t 心i b m e ，d i s c e m i b i l i 田m 州x 主要符号袁 主要符号表 ( u c u d ) 信息系统，其中u 是一个有限非空对象集，称为论域：c 和d 也 是两个有限非空集，分别表示信息系统的条件属性集和决策属性集。 m 信息系统 uo j d ) 的差别矩阵。 s ：日】 d 2 - 诉4 _ 口。定义在条件属性集c 上的属性序。 “属性序上位于第z 位的属性。其中z 为整数。 【巩k 差别矩阵中以属性以为标记属性的差别元素的集合，称为等价类。 0 z ( 1 s ) = ( 【。1 k 啦k “j 嘲s ) 差别矩阵m 关于属性序s 的划分。 田属性序s 上属性啦的函数表示。 嘶0 属性序s 上位于第x 位的标记属性的函数表示。 z j k 卅属性序s 上位于区间b ，纠中的标记属性的函数表示，称为区间标记 属性函数。 r 积) 属性序s 上位于第z 位的 加r 属性的函数表示。 r s k 胡属性序s 上位于区间肛，卅中的，e 幽c ，属性的函数表示，称为区间 m 龇f 属性函数。 【划s + 等价类【n x 】5 关于凡陋 l ，n 】的相对等价类，即， 硝，= qlq 【嘲s 且 值n r s d + 1 ，珊 = g ) 。 e 删等价类 础的函数表示。 嘶) 相对等价类嘲，的函数表示。 g ：舡b 等价类嘛b 关于r 由斗1 ，m 的相对等价类函数，即，赔0 b = 刮口 口m 且c r 1 月s d 件1 ，m 】= o 。 西h ，纠属性序s 上区间陆，纠中的等价类的集合。 鸯砷，玷属性序s 上，区间肛，川中关于妙l ，棚 的相对等价类的函数表示， i x 敬属性原理 称为区问相对等价类函数。 n 舡) 脚) = “1 p u 酬，是属性序s 上区间【1 ，x 】中的差别元素的集合。 风k 纠协陆，卅- 蹦x 1 ) ，是属性序s 上区间i z ，卅中差别元素的集合。 味0 ) 属性序s 上，区间ky 】中关于胄击h 1 ，叫的差别元素的函数表示，称 为区间相对差别元素函数。黯旺，y 】属性序s 上，区问旺，纠中关于r s 一l ，州 的差别元素的函数表示，称为区间相对差别元素函数。 z 廿在给定属性序上，属性如从位置z 向右移动到位置y 。 + 叫在给定属性序上，属性以从位置z 向左移动到位置y 。 s j 甘由属性序s 变换为属性序且获得的邻近属性序偶序列呈“， ，d “”，加的过程。 硝以n 为根节点的的属性一值树表示。 ( 以a 为根节点的封闭属性一值树表示。 q ，户由属性一值树覆盖的对象构成的分支对。 瑚，由属性一值活子树巧曲上分支对产生的以巩为标记属性的差别元素 的集合。 x 独创性声明 本人卢明所成交的论文是我个人在导师指导下进行的研究上作及取得的研究成果。尽我所知 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与 我一l 司工作的同志对本研究所做的任何贡献均己在论文中作了明确地说明并表示了谢意。 签名： 鲣垒鱼日期 关于论文使用授权的说明 ，工1 口 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即：中国科学院自 动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅；可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：鲢耋盔导师签名日期 如i ! 、 o 第一章引言 1 1 研究背景 第一章引言 传统的数据分析方法通常基于以坚实的数学理论为基础的统计，统计数据 分析方法已经获得了广泛的应用。但是，随着信息产业的迅猛发展，可共享的 资源变得越来越多，获取信息的方式也变得越来越简单，这导致人们不得不常 常面对远远超过人当前处理能力的庞大数据。在许多实际应用中，如自然语言 数据分析、d n a 数据分析、网络与电信数据分析、图像数据分析、金融与经济 数据分析等方面，传统的小规模数据分析方法己不再适用，迫切需要能够将海 量信息转化为知识的有效计算方法。 近年来以计算机技术为动力的机器学习为数据分析增添了新的方法和思 路。机器学习已成为处理海量数据，探索数据内在规律，提取数据中未知知识 的重要手段之一。但机器学习的方法和技术不是为了替代传统的统计分析技术， 相反，它是统计分析方法的延伸和扩展。大多数的统计分析技术都基于完善的 数学理论和高超的技巧，对于某些闯题，预测的准确度在一定程度上令人满意。 但是，统计分析方法存在两个局限：一是对使用者的要求很高，二是能够处理 的数据的规模有限。而随着计算机计算能力的不断增强，我们有可能翻用计算 机强大的计算能力，只通过相对简单和固定的方法来完成同样的功能。这是符 号数据分析产生的背景。 1 2 符号机器学习与符号数据分析 符号数据分析与符号机器学习密切相关，但又不同于符号机器学习e 符号 机器学习假设所有用户的需求相同，以泛化能力为评测标准寻找“最小”解。由于 寻找c 最小”解是n p h a r d 问题，因此，算法设计以求近似“最小”为目的。 符号数据分析是指对于定义在符号域上的数据的分析。它假定不同的用户 需求不同，以约简能力为评测标准寻找在需求意义下的相对最小解，因此，算 法设计以求满足用户需求的相对较小的精确解为目的。 次属性原理 1 3 用户需求描述 在数据挖掘中，一个信息系统对于不同的用户来说，其意义不同。不同的 用户希望从这个信息系统中获得的知识也不同。因此，来自用户对需求的描述 就显得非常重要。 在机器学习中，用户的需求往往通过基于某种策略的属性序来体现( 比如， 基于信息熵的属性序) 。但无论使用什么样的手段对属性的重要性进行测量，其 数值本身对问题的解答并不重要，重要的是它给属性排了序。因此，我们认为 建立在信息系统条件属性集合上的属性序，可以理解为描述用户需求的一种计 算语义。 在r o u g ls e t 理论中，增幽“是一个特殊的概念，与一般意义下的约简概念 不同，它需要满足属性的独立性条件，即，对于v ，月，旭出d 满足 p 嘶( d ) 妒o 师f ， p ) ，其中月是信息系统 掰 因此，基于属性- 值树表示，第六章设计了计算复杂度为d ( n x 朋2 ) 的属性值树表 示次属性算法，并证明了它与次属性定理暗示的次属性算法等价。 第七章总结全文。 第二章符号数据分析 第二章符号数据分析 目前，面对数据量和数据关系复杂性的快速膨胀，数据分析方法日益丰富。 近年来，以计算机技术为动力的机器学习也为数据分析增添了新的思路和方法。 机器学习已成为处理海量数据，探索数据内在规律，提取数据中未知知识的重 要手段之一。 数据分析方法的个显著特点是它关注数据。正如佛罗里达中心大学统计 与精算系教授m o r g a nc w 抽g 所说，要仔细倾听数据说话，潜藏在数据中的各 种信息可能会给用户带来意想不到的收益。 m o r 鹭a nc w 撕g 曾经举出一个典型的商业数据分析案例。家美国企业， 它的服务对象是学校和医院，每隔五年都需要重新签订合约。因此第四年就极 为关键。该企业要达到续签合约的目的，必须对不同的客户采取不同的公关措 施，例如捐赠款项、制定投标金额等。但是不同客户的具体情况不同，因此该 企业需要通过对包含客户信息的数据进行分析以了解每个客户的特点，从而针 对客户自身的特点制定不同的策略。企业对这些客户进行数据分析的数据源是 已有的、成熟的来自美国教育部对学校的统计资料以及荚国调查公司对地区生 活指标的调查等。换句话说，这家企业的所有客户共同享有一个数据集。这个 例子显示，一个信息系统对于不同的用户来说，其意义不同。因此，来自对用 户需求的描述就显得非常重要。 传统的数据分析方法通常倾向于使用统计数据分析方法，即根据特定的需 求过滤“噪音”展现数据内涵，因而统计显著是其核心。统计数据分析方法的任务 主要包括相关分析，多元素分析，时序分析，o u t l i e r 检测等。那么基于统计的 数据分析的各类任务能否平行地在符号域上找到呢? 这是值得尝试的一个课 题，也是本文关注的问题。 本文的研究建立在符号数据集上，因此，本章后面的所有内容也将只涉及 与符号机器学习有关的内容。 2 1 数据表示 无论使用计算机解决什么样的问题，第一个需要解决的问题是如何把要解 次属性原理 决的问题转换成为计算机语言。因此，表示语言是描述样本、概念和背景知识 不可或缺的要件。 在大多数传统的机器学习中，数据集的样本通过一组条件属性和一组决策 属性以属性一值的方式来描述。学习到的规则以析取或合取的方式表示为 i f t h e n 句型。因此，这是一类基于命题逻辑的表示语言。 在命题逻辑推理体系中，原子命题被看作是基本单位，是不可再分的整体， 复合命题由原子命题通过逻辑连接词来表达。命题逻辑的推理就建立在这个层 次上。这种体系带来的一个不足是，命题逻辑推理体系对命题的内部结构不加 分析。这意味着许多实际问题中的样本将无法使用属性值表示方法表示。比 如递归关系问题中的样本以及某些依赖背景知识的特定领域的问题等。因此， 为了提高推理能力，需要考虑表达能力更强的表示语言一阶逻辑。 i l p 是基于一阶逻辑的规则归纳学习方法。它采用了一种被称作逻辑程序 ( l o g i cp r o g r a m ) 的表述语言，这种语言不仅比传统的属性值表示方式具有更 强的表达能力，而且可以很好地把背景知识融入到学习过程中。由于引入了一 阶逻辑作为表述语言，因此，i l p 有能力克服传统机器学习中的两个主要限制， 即知识表示机制的限制和在学习中有效利用背景知识的限制。 符号数据分析的有效性在很大程度上取决于数据的形式、数量和质量。如 果能够确保以符号形式表示的“纯净数据( c l e a l ld a t a ) ”的实现，那么。数据分 析方法的优势和作用无疑是显著的。因此，为了确保数据符号化和数据纯净， 在进行数据分析之前，有必要先对原始样本数据进行处理。 常见的数据处理方法包括：特征抽取、特征重建和特征选择。特征抽取 ( f e a t u r ec x 扛私t i o n ) 是指在保持原特征空间内在结构不变的条件下，通过对原空间 进行某种形式的变换，寻找新空间的过程。特征重建( f e a t u r ec o n s m l c d o n ) 是指通 过在原有特征空间中应用结构算子，产生另外一些用于描述目标概念新特征的 过程；与特征抽取过程不同，特征重建扩张了特征空间。特征选择( f e a t u r es e l e c t i o n ) 则是在原有特征空间中，基于某种优化准则。选择特征子集的过程：这个过程 在不产生任何新的特征的情况下能够降低特征空间的维数。 目前，大规模数据的特征抽取、特征重建和特征选择成为对已有经典方法 的挑战，特征抽取、特征藿建和特征选择的研究开始逐渐呈现出多样性和综合 第二章符号数据分析 性，这或许是今后的一个研究方向，但我们对这部分内容不做讨论。 2 2 符号机器学习 符号机器学习中最为核心、也最为成熟的部分是规则归纳学习方法，这类 方法被广泛地应用到机器学习的各个领域，特别是符号机器学习领域。 符号机器学习中的规则归纳学习方法主要包括：m i t c h e l l 关于v e r s i o n 空间 的候选消除算法 m i t 7 7 、m i c h a l 如和c h i l a u s b 的a q l l 【m c 8 0 】、m i c h a l s k i 和 洪家荣等关于a q l l 的扩充算法a q l 5 【h m m 8 6 】、洪家荣的a e i h u 8 7 、c l a r k 的c n 2 c n 8 9 】、h u n t 等人的决策归纳程序c l s h m s 6 6 】、q u i i l l a f l 的i d 3 q u i 8 6 】、 i d 3 的改进c 4 5 【q u i 9 3 】以及a s s i s 弘n t k b r 8 4 ，c k b 8 7 】等。 规则归纳也称为概念学习：给定某类别的若干正样本和负样本，或某几 类样本，从中归纳出该类别或几个类别的一般定义。概念学习可以看作是对于 目标概念的搜索过程，它在预先定义好的假设空间中搜索与训练样例有最佳拟 合度的目标假设。 根据规则归纳所使用的搜索策略，规则归纳算法可以分为覆盖算法与分治 ( d i v i d ea 1 1 dc o n q u e r ) 算法两类。在覆盖算法中，大多数算法使用序列覆盖 ( s e q u e 椭a 1c o v e r i n 曲，也有一些使用并行覆盖。 序列覆盖算法每次学习规则集合中的一条规则，而分治学习算法同时学到 所有的规则( 规则集合) 。虽然学习的结果都是样本空间的超矩形，但策略的不 问却可能会导致对同一样本集合产生不同的规则集合：序列覆盖产生的规则关 于数据集合不是严格的划分，各规则之间可以相交。而分治算法产生的规则关 于数据集合则是完整的划分，各规则之间不能相交。 序列覆盖算法的学习过程是每次学习一条规则，然后从数据集合中移去被该 规则覆盖的样本，再学习下一条规则，直至覆盖所有样本。已经证明，求一个 最小集覆盖是n p h a r d 问题，因此通常采用各种形式的贪心算法求取近似最小规 则集合。具体地说，每条规则的生成方式又可分为自上而下( 般到特殊) 与 自下而上( 特殊到一般) 两种。自上而下的方法由最一般的规则( 通常是空规 则) 开始，逐步加入能保留正样本、去掉负样本的特征；自下而上的方法由最 特殊的规则( 通常是某样本) 开始，逐步去掉特征使得规则覆盖的正样本增 次属性原理 多。 分治学习算法的一个典型是决策树算法。决策树算法首先构造出一棵决策 树，然后将此树转换为一个等价的规则集合。由于求最小决策树是一个n p - h a r d 问题，因此通常采用贪心算法构造决策树。决策树的生成一般是白上而下的。 开始时，所有的样本都在根节点，然后将样本用选定的属性递归地进行分割， 属性的选择可以基于启发式规则，也可以基于统计度量。递归停止的条件是：( 1 ) 节点上的样本都属于同一个类别；( 2 ) 没有属性可以再用于对数据进行分割。 规则归纳的本质是将给定的数据集合所隐含的概念用简洁的规则表示出来， 因此需要首先假定一个概念空间( 或称假设空间) 。概念空间中的概念一般表示 为属性的析取范式，这是一个偏好很大的假定，因此，常常会导致假设空间中 不存在正确概念。 假设空间确定后，规则归纳的任务就成为怎样依据给定的目标从假设空间 中找到最优假设。由于规则归纳学习假设所有用户需求相同，因此以泛化能力 为评测标准寻找“最小”解。由于寻找“最小”解是n p h a r d 问题，因此，算法设 计以求近似“最小”为目标。由于关注规则在未知样本上的分类能力，因此不要求 归纳结果关于给定数据集合完全正确。换句话说，在利用归纳结果对给定数据 集进行分类时允许存在一定的分类误差。 2 3 符号数据分析 符号数据分析是定义在符号域上的数据的分析。符号数据分析有别于符号 机器学习，它假定不同的用户需求不同，并以约简能力为评测标准寻找在需求 意义下的相对最小解，因此，它对算法的设计要求是输出精确的解。 2 3 1 熘如以理论 阳也c f 是一个特殊的约简概念，与一般意义下的约简概念不同，它需要满足 属性的独立性条件，即，对于协尺，愆幽“满足户。珐( d ) 舻o 啜“| d ) ，其中异 是信息系统 的一个彤妣f ，p o s 是 的正区域 pa w 8 2 】。独立 性条件说明，删除r 中的任何一个属性，都会使正区域改变，或者说，样本中 矛盾对象的数量都会增加。这意味着旭幽c r 是使矛盾对象个数不改变的相对最 小的属性集合。因此，旭妣f 可以作为构成规则集合的基本元素。 第二章符号数据分析 由于信息系统的旭幽甜并不唯一，并且任何一个m 幽甜都可以取代信息系 统的条件属性集而保持信息系统分类能力不变，因此，信息系统旭出d 不唯一 这一现象。实际上反映了以信息系统不同旭出甜作为基本要素构成的规则集合， 是对信息系统不同侧面的描述。这意味着不同的用户对于这个信息系统可能会 关注某个侧面或是某几个不同的侧面。因此，我们认为旭幽c f 理论可以作为面 向用户需求的符号数据分析的理论基础。 不同于”幽甜，m 不仅在信息系统中唯一，而且它包含在信息系统的所有 陀幽c f 中 p a w 8 2 】。对于彤中的任何一个属性，在对象集合中，至少存在一对 对象，使得它们之间的差别只有这个属性的值。由于c o 糟反映了信息系统的本 质，因而c d 旭在旭幽甜理论中非常重要。 地砌c f 与c o 心之间的另外一层关系是，假如r 是给定信息系统的一个陀出c f ， 则r 的每一个属性都是由r 构成的新信息系统 的旭属性。此时，去 掉r 中的任何一个属性都会导致例外的出现，因此，这个性质对于在数据中发 现例外具有及其重要的意义【赵岷0 4 。 阳出c r 理论的一个基本问题是如何求出给定信息系统的肥幽“。研究证明： 求出信息系统的所有旭出c f 和求信息系统的最小旭幽c f 都是n p - h a r d 问题。因此， 一般的算法都采用启发式策略寻找比如甜。从降低计算代价和提高预测能力的角 度出发，有些算法不是直接计算理如c f ，丽是计算动态的陀幽“ b s s 9 4 ，近似 的理巍耐f s l e 9 6 1 ，或是局部的地幽df w r 6 9 8 】。 常见的旭妣f 算法包括基于属性独立性的形出甜算法【p a w 9 1 ，s h c 9 5 ：基于 正区域的您幽甜算法 瑚9 5 ，j e l 9 5 】，基于互信息的心咖c f 算法( m i b a r k 算 法) m w 9 8 ，基于遗传算法的措如甜的算法【w r 6 9 5 ，9 6 】以及基于差别矩阵的 旭如c f 算法s r 9 1 ，w m 9 8 】等。 基于属性独立性的m d k f 算法是根据旭幽c ，的原始定义求解。对于一个给 定的信息系统 职c u j d ，算法从条件属性集合c 出发，对所有r c ，通过计算 尸。耻c d ) ，依次检查属性的独立性。当发现非独立的属性时，从属性集c 中 移除该属性，然后对剩余的属性继续检查，直至所有属性都满足独立性条件。 由于算法的输出一定是这个信息系统的旭如“。因此，基于独立性条件的旭幽“ 算法对陀咖甜完备，但局限是该算法的计算代价很大。在最糟的情况下，计算 9 次属性原理 代价为0 ( n 2 加2 ) ，其中m 表示属性的个数， 表示论域中对象的个数。因此， 并不适用于大规模数据集合。 基于正区域的陀d 沈f 算法和基于互信息的陀出c f 算法从本质上讲是一回事。 它们都是根据预先定义的属性重要性度量，依次从条件属性集中选择最重要的 属性添加到c d 陀中，直到终止条件满足。算法的复杂性，如果忽略对象数对计 算时间的影响，在最坏情况下为d ( m 2 ) ，其中，m 为决策表中条件属性的个数。 由于这些算法强调寻找最小近似腭幽c f ，因此，对陀也“不完备。 基于遗传算法的理d 沈f 算法的主体思想是：首先对信息系统中的所有样本 两两构造样本对，然后用字符串编码表示，最后用基于遗传算法的贪心策略求 解。 基于遗传算法，w r 6 b l e w s h 一共给出三种旭幽c f 计算方法。其中有两种算 法关于旭咖“不完备但计算复杂度较低( o 沏榭2 ) ) ：另一种算法关于旭幽c f 完备 但计算复杂度高( d ( 舻- 矛) ) 。因此，如果同时考虑算法的完备性和计算复杂度， 这三种算法都不算成功。 在关于地幽甜理论的研究中，最具影响的工作应该是s k o 、r o n 的差剐矩阵 原理 s r 9 1 】。基于差别矩阵原理，旭妣，、聊曾与边缘区域等概念可以看作是一 类特殊的距离。尽管s k o w r o n 没有进一步研究差别矩阵原理的几何性质，但是， 正是由于其所具有的几何特性，使得坨幽c r 的计算变得简单。 设船 是一个信息系统，差别矩阵m 定义为忙口胡。， = 1 ，2 ，胁 其中差别元素萨句满足： c 扩= ? 1 口工，盘x ，v 口c ，x p x ，u 耋舅凄：；：舅：；嚣 c ， pj 三j 上j 【工，j = 上j l 工fjh 0 可以看出，白是可以区别对象鞠与畸的所有属性的集合。当。口= 口) 时，意 味着d 是区分对象而与却的唯属性，因而是，e 属性。据此，核属性的判别 规则可以设计为：日是 的一个核属性，当且仅当，j 口m ，使萨 口) 。 注解：由于差别矩阵肘中的元素与排列方式无关，为描述方便起见，我们 通常把差别矩阵写成集合的形式，并依然用字母m 表示，即 仁 白1 泸1 ，2 ，” 。 差别元素娓可以区别信息系统某两个对象的所有属性的集合，用逻辑的方 第二章符号数据分析 式可以表示为萨c v c ，v v “。肘中所有差别元素硝q 合取：苁c l ，c 2 ，c m ) = 口 f a 幻，是可以区别信息系统所有对象的逻辑表达式，称为差别矩阵m 的差别 函数。差别函数，具有这样的性质：，的极小析取范式中的每一个合取范式都是 属性集4 ( 彳= c 或彳= c u d ) 的憎幽甜。 这样，差别矩阵原理把求信息系统陀幽甜的问题转化成了求， 极小范式的问 题。为了简化，的计算，在求取差别函数之前，可以通过对差别矩阵m 使用吸 收律卧( a ，g ) = f 1 v ( ，= f ( f 与g 是两个逻辑公式) 来简化差别矩阵。 根据差别函数与朋幽c ，之间的关系，s k o 、v r o n 给出了计算信息系统r 8 幽甜 的方法：1 ) 计算信息系统的差别矩阵m ，并用吸收律简化m ：2 ) 计算差别函数 厂的极小析取范式：3 ) 令其中的每一个析取分量对应一个旭幽“。 由于算法在计算差别函数的析取范式时使用了吸收律，因此，算法对把如c 完备。 尽管基于差别矩阵的旭幽甜算法与基于属性独立性的方法旭出c r 算法相比 较具有直观明了的优势，但由于基于差别矩阵原理求信息系统旭出口的算法是 n p 完全问题【s r 9 1 】，并且当讨论的对象与属性的规模较大时，差别矩阵m 的存 储需要占据大最的存储空间。因此，基于差别矩阵的阳幽甜算法在实际应用中 受到了限制。 根据撑幽“的定义，用任何一个瑁舭f 都可以替代原系统中的全部属性， 而不会影响系统的分类( 决策) 能力。因此，基于差别矩阵如何求解比如c ，空间中 的一个腭砒甜成为新的研究目标。 如果不考虑约简的独立性条件，仅从糟幽c f 空间中直接求解一个旭幽d ，那 么，问题已经被s k o o n 解决。他的方法基于这样一种思想：假设m 是信息系 统 的差别矩阵，那么，r 僻c c ) 是 的一个愆如c f ，当且仅当 v 口m 且群，酬2 o ；c c 是 的一个核属性，当且仅当j a m 俨 c ) 。 s k o w m n 给出的算法在一开始对旭幽吖属性的选择上采用了任意选择的策 略。这种策略一方面导致算法对旭幽d 不完备，另一方面使得基于差别矩阵原 理的启发式搜索增如“算法有了很大的改进空间。 次属性原理 从上面介绍的几种算法可以看到，基于属性独立性的m 如c f 算法与s k o w r o n 基于差别矩阵的地咖c f 算法，对阳如d 完备但计算复杂度高；基于正区域、基 于信息熵和互信息、以及基于差别矩阵原理的算法，虽然计算复杂度较低但对 憎出c r 不完备。 2 3 2 属性序陀幽c f 算法 尽管用任何一个旭如c f 取代原系统中的条件属性集后，不会影响到系统的 分类( 决策) 能力。但是，在所有得m 砌d 中，到底哪一个解更为重要一些呢? 因 为以信息系统不同比咖甜作为基本要素构成的规则可以理解为是关于信息系统 不同侧面的描述，那么，对于共同享有一个信息系统的不同用户来说，他们对 于信息系统关注的侧面可能不同。因此，当数据分析针对某一个特定用户进行 时，单纯追求计算出一个旭妇“，或是计算出一个“最小阳出c r ”是不合理的。 在数据分析中，用户的需求往往通过基于某种策略的属性序来体现( 比如， 基于信息熵的属性序) 。但无论使用什么样的手段对属性的重要性进行测量，其 数值本身对问题的解答并不重要，重要的是它给属性排了序。因此，建立在信 息系统条件属性集合上的属性序，可以理解为对用户需求进行描述的一种原语。 它可以当用户不能够精确表述自己的需求，或者当用户对于需求的描述过于笼 统，以至于无法满足计算条件时，作为对于用户需求