（计算机科学与技术专业论文）基于知识约简的施工安全决策研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：盎氖彰导师( 签名) 弓淳哆如期纱f f 加 摘要 地下空间建造在地质复杂、道路狭窄、地下管线密集、交通繁忙的闹市中心， 其安全问题是绝对不容忽视的。地下空间工程不管在施工期还是在运营期都要对 其结构进行严格的数据监测，以确保地下空间的主体结构稳定和周边环境安全。 该工程它是一项长期性的工作，其特点是监测项目多、线路长、测点多、测期频 和数据量大。面对海量的数据，这些数据可能是不完备、不精确和不确定，需要 建立相关必要的数学模型，进行高效率的综合应用，充分发挥地下空间施工安全 监控系统的辅助决策作用。 z p a wl a k 提出了粗糙集理论，它是一种刻画不完整性和不确定性的数学工 具，能够对不精确，不确定，不完整等各种不完备的信息进行有效地分析。因此， 本文对地下空间工程的相关信息，利用相关的仪器设备进行数据监测采集，将所 采集到的数据利用粗糙集理论中的方法来进行分析研究。论文针对施工安全决策 中的问题，提出基于知识约简的施工安全决策方法。在分析经典知识约简算法的 基础上，提出了基于完备和不完备的知识约简算法。本文的主要工作如下： 1 对于完备的知识系统而言，一方面针对复杂知识的约简展开研究，通过构 造新的知识划分粒度和新的相对条件划分粒度，提出了对一致和不一致决策表都 适用且完备的知识约简算法。另一方面，以海量动态知识为研究对象，针对动态 建立知识库的需要，利用数据压缩性的思路，提出了基于h a s h 表对一致和不一 致决策表都适用及完备的快速动态知识约简算法。 2 对于不完备的知识系统而言，主要针对非对称关系中明显相似的对象分类 不合理的问题，定义了动态量化非对称相似关系，提出带有自动阈值调节的动态 量化非对称相似关系模型，根据实际数据自动确定其阈值，使之更加灵活和合理。 3 研究了不完备知识系统中的相容类和极大相容块，设计了相应的基于相 容类的快速约简算法。 4 论文研究的算法已应用到施工工程数据的约简和安全决策中，效果良好。 关键字：粗糙集，知识粒，知识约简，完备信息系统，不完备信息系统 a b s t r a c t u n d e r g r o u n ds p a c eb u i l d i n g ss e c u r i t yi si m p o r t a n t s i n c ei to f t e nb u i l to n g e o l o g i c a lc o m p l e x ，r o a dn a r r o w ，u n d e r g r o u n dp i p e l i n ed e n s e ，b u s yt r a f f i cc e n t e r d o w n t o w n w h e n e v e rt h eu n d e r g r o u n ds p a c ep r o j e e t sc o n s t r u c t i o no rt h eo p e r a t i o n p e r i o d ，i ts h o u l db et a k e nas t r i c tm o n i t o r i n gt ot h ed a t af o rt h es t a b i l i t yo ft h em a i n s t r u c t u r ea n dt h es a f e t yo fe n v i r o n m e n t n ep r o j e c ti sal o n g t e r mw o r k ；i t s c h a r a c t e r i s t i c si n c l u d et h ev a r i o u si t e m s ，t h el o n gd i s t a n c e ，t o om a n yp o i n t st o m o n i t o r , t h ep e r i o df r e q u e n c ya n dl a r g ea m o u n to fd a t ai nt h em o n i t o r i n gp e r i o d f a c i n gl o t so f d a t aw h i c hm a y b e i n c o m p l e t e 、i n a c c u r a t ea n du n c e r t a i n , i sn e c e s s a r y t o e s t a b l i s ht h em a t h e m a t i c a lm o d e lf o re f f i c i e n ts y n t h e s i su t i l i z a t i o n ，t oe x e r tf u l l yt h e a i d e dd e c i s i o n - m a k i n gr o l eo ft h eu n d e r g r o u n ds p a c ec o n s t r u c t i o ns a f e t ym o n i t o r i n g s y s t e m z p a wl a kp r o p o s e sr o u g hs e t st h e o r yw h i c hi sak i n do fd e p i c t i n gi n c o m p l e t e a n du n c e r t a i nm a t h e m a t i c a lt 0 0 1 i tc a na n a l y z et h ei n a c c u r a t e ，u n c e r t a i n , i n c o m p l e t e i n f o r m a t i o ne f f e c t i v e l y t h e r e f o r e , f o rr e l e v a n ti n f o r m a t i o na b o u tu n d e r g r o u n ds p a c e p r o j e c t ，t h i sp a p e ru t i l i z e sr e l a t e de q u i p m e n tf o rd a t am o n i t o r i n gc o l l e c t i o na n dl i s a t h er o u g hs e t st h e o r yt oa n a l y z et h ec o l l e c t e dd a t a t os o l v et h ep r o b l e m so f c o n s t r u c t i o ns a f e t yd e c i s i o n , t h i sp a p e ri n t r o d u c e sac o n s t r u c t i o ns a f e t yd e c i s i o n m e t h o db a s e do nk n o w l e d g er e d u c t i o n b ya n a l y z i n gt h ec l a s s i ck n o w l e d g er e d u c t i o n a l g o r i t h m , i tp r o p o s e dan e wm e t h o df o rc o m p l e t ea n di n c o m p l e t ek n o w l e d g e r e d u c t i o n n 圮m a i nj o b si nt h ep a p e ra r ea sf o l l o w s ： 1 f o rt h ec o m p l e t ek n o w l e d g es y s t e m ，t h ec o m p l e xr e d u c t i o nb yc o n s t r u c t i n g n e wk n o w l e d g ep a r t i t i o na n dr e l a t i v ec o n d i t i o n sp a r t i t i o na l ep r o p o s e d a n da n a p p l i c a b l e a n dc o m p l e t ek n o w l e d g er e d u c t i o na l g o r i t h mf o rt h ec o n s i s t e n ta n d i n c o n s i s t e n td e c i s i o nt a b l ei sp r o p o s e d o nt h eo t h e rh a n d ，i no r d e rt or e d u c eh u g e d y n a m i ck n o w l e d g ea n ds a t i s f yt h en e e dt ob u i l dk n o w l e d g eb a s e ，aq u i c ka n d d y n a m i ck n o w l e d g er e d u c t i o na l g o r i t h mf o rt h ec o n s i s t e n ta n di n c o n s i s t e n td e c i s i o n t a b l eb a s e do nh a s ht a b l ei ss t u d i e d 2 f o rt h ei n c o m p l e t ek n o w l e d g es y s t e m ，s i n c ei ti su n r e a s o n a b l ef o ra s y m m e t r i c s i m i l a r i t yr e l a t i o nt oc l a s s i f yo b v i o u s l ys i m i l a rr e l a t i o n , d y n a m i cv a l u e da s y m m e t r i c s i m i l a r i t yr e l a t i o n i sd e f i n e da n dal 【i n do fv a l u e da s y m m e t r i cs i m i l a r i t yr e l a t i o n m o d e l 、历ma u t o s e l e c t i n gt h r e s h o l di sb u i l t t i l i sm o d e lm a k e sd a t as e l e c t i o nm o r e f l e x i b l ea n dr e a s o n a b l e 摘要。 a b s t r a c t 。 第1 章绪论 目录 1 1 1 选题背景和意义1 1 2 国内外研究现状2 1 3 粗糙集应用现状：7 1 4 本文的主要研究内容8 第2 章粗糙集理论及其知识约简 2 1 粗糙集的基本概念1 0 2 1 1 粗糙集的定义1 0 2 1 2 知识和知识库l l 2 2 知识约简1 3 2 2 1 知识的约简与核1 3 2 2 2 知识的相对约简与相对核1 4 2 2 3 知识的表达系统与决策表1 5 2 3 本章小节1 6 第3 章完备信息系统的知识约简算法 1 7 3 1 相对条件划分粒度1 7 3 2 一致或不一致决策表的知识约简1 9 3 2 1 一致决策表19 3 2 2 不一致决策表2 0 3 3 基于相对条件划分粒度的知识约简算法2 l 3 4 分析相关文章的局限性。2 2 3 5 一种具有数据压缩性的动态知识约简算法2 3 3 5 1 预定义2 4 3 5 2 动态知识约简算法的总体思想2 5 3 5 3 动态知识约简算法。2 6 3 6 本章小节2 7 第4 章不完备信息系统的知识约简算法 2 8 4 1 不完备信息系统的基本概念2 9 4 2 量化非对称相似关系2 9 4 3 基于动态量化非对称相似关系的扩充粗集模型3 0 4 4 动态调节的知识重要性的约简算法3 3 4 4 1 参数口，的动态确定3 3 4 4 2 基于知识重要性的约简算法3 4 4 4 3 算法时间复杂度分析3 7 4 5 本章小结3 7 第5 章知识约简应用于地下施工安全的研究。3 8 5 1 实例分析与比较3 8 5 2 完备信息系统的知识约简算法应用于地下空间决策3 9 5 3 算法比较及实验分析4 3 5 4 不完备信息系统的知识约简算法应用于地下空间决策4 3 5 5 本章小结”4 5 第6 章总结和展望4 6 6 1 全文总结4 6 6 2 工作展望4 7 致谢。 参考文献 附录 4 8 4 9 5 7 武汉理工大学硕士学位论文 1 1 选题背景和意义 第1 章绪论 随着我国经济的不断高速发展，全国许多的城市地下交通建设中的大型地下 空间项目非常之多，而且工程项目的扩展规模越来越大。监测工程项目需要不断 地进行安全监测，监测到的数据进行综合分析，为进一步的施工安全提供相应的 决策。在监控项目的监控过程中，尽管有的监控项目是做了监控测量工作，但是 在现实中还是存在不够合理或是存在有漏洞地方；偶尔还出现工程监测人员的专 业技术不合格，或者完全没有达到专业水平，结果观测来一大堆的无效测量数据， 再者也没有对它用最新的科学进行及时数据分析与反馈，所以也就根本没有对监 控指导工作起到什么良好的作用；再者有的监控工程项目没有考虑地质问题，为 了节省时间或者其他因素，基本没有开展监测量测工作就开始动工，这样的工程 安全风险很大，所以也就常有安全事故发生，以上提到的工程安全现象都是与我 国的经济建设的发展相悖而行。 、 因此，对监测到的项目数据进行现场核查并把监测项目数据进行综合的粒度 分析，为进一步解决地下空间工程施工安全问题提供相应的预测预报和相应的施 工措施和方案，故不管是作为地下空间施工安全主体的施工单位、监理、设计、 安全监测等多个部门带来指导性的事故安全建议，还是给监控项目带来更多的利 益。通过对监测数据进行及时科学分析且尽快优化施工安全措施和解决方案，加 快施工进度又保证了安全，又可节约施过程中成本，还可根据相关的数据为工程 设计提出相应的修改建议，为下一步的地下施工安全提供相应的安全决策是非常 有必要的。 地下空间建造在地质复杂、道路狭窄、地下管线密集、交通繁忙的闹市中心， 其安全问题不容忽视。地下空间不管在施工期还是在运营期都要对其结构进行严 格的数据监测，以确保主体结构稳定和周边环境安全。该工程它是一项长期性的 工作，其特点是监测项目多、线路长、测点多、测期频和数据量大，其中包括以 下数据：侧斜测值数据、收敛测值数据、沉降测值数据、水位测值数据、测点限 值数据、测点信息数据等。面对这海量数据，这些数据可能是不完备、不精确和 不确定，为此当务之急就是对其粒度分析，建立必要模型，进行高效率的综合运用， 充分发挥地下空间施工安全监控系统的辅助决策作用。 然而粗糙集理论n 1 正是可以用来解决这一问题的有效手段，是由波兰华沙理 工大学p 口毗放教授于1 9 8 2 年提出的，它是一种处理不完备、不精确和不确定知 武汉理工大学硕士学位论文 识的新型数学工具，尤其在数据挖掘、模式识别、决策分析、图像处理、医疗诊 断和人工智能乜一一5 6 7 一一1 等领域发挥了重要的作用。知识在经典的粗糙集理论 中是有粒度的，但是它没有对知识的分类能力给予量化，苗夺谦教授等n 1 0 印从 知识划分粒度的角度来定量表示知识的分类能力。知识n 删可以定义为：给定一组 数据【，与不分辨关系集合r ，在不可分辨关系集合r 下对数据集合【厂的划分，称 为知识，记为u r 。 r o u g hs e t 的核心研究内容之一就是知识约简n 州m 1 捌，找出所用的知识d 一 约简或最优d 一约简( 即属性个数最少) 是一个p 难问题，因此一般采用知识的 启发式信息作为启发式条件找出其最优d 一或是次优d 一约简。以信息系统数据 的分类能力不改变作为前提条件，删除其中的冗余知识，这就是知识约简( 属性约 简) 。然后通过高效完备的知识约简算法对各种复杂或冗余的数据进行分析、判 断与比较，并进行评价、优选，使数据标准化、条理化，加速信息传递，缩短处理 时间，为其工程安全及高层决策者提供预警信息。对于( 不) 完备信息系统而言， 学者及研究者们总是特别期望能求解出所有d 一约简或找出最优d 一约简( 即知 识的个数最少) 。然而，目前大多数的知识约简算法都是在研究完备信息系统上的 绝对约简以及其的知识相对约简的问题上：然而，对于不完备信息系统，不完备决 策表的知识约简算法学者们也进行了相应的研究，但是在这方面的研究的深入远 远还不够。由于在现实工程应用中，绝大多数信息系统都是不完备的，缺少的信息 仍然蕴含一些有用的知识，这些知识对于不完备信息下的决策，是特别有意义的。 因此，对地下空间工程的相关信息，利用相关的仪器设备进行数据监测采集， 将所采集到的数据利用粗糙集的方法来分析研究，将研究得到的知识约简算法应 用到实际的施工安全决策中，为地下空间施工安全的决策提提供一种方法与思路， 是一件很有意义的工作。 1 2 国内外研究现状 众所周知，施工期安全问题是控制地下空间工程施工工期的一个关键性技 术问题。为此国内外均投入大量人力物力进行地下工程施工安全技术的研究探 索。2 0 世纪7 0 年代开始以安全监测为标志性技术的新奥法应用研究大大地推动 了地下空间施工期安全管理和决策的规范化、科学化，促进了安全管理和决策水 平的提高。2 0 世纪9 0 年代初，日本开始了地下工程的信息化施工设计管理的应 用研究，国内在十三陵、小浪底等地下工程中，系统地进行了地下空间工程的安全 监测和反馈研究工作n 州唧。在现实监测项目的实施过程中，偶尔还出现工程监 测人员的专业技术不合格，或者对地质条件完全没有一点认识，结果观测来一大 堆的无效测量数据，再加上也没有对它用最新的科学进行及时数据分析与反馈， 2 武汉理工大学硕士学位论文 所以也就根本没有对监控指导工作起到什么良好的作用；再者也有的监控工程项 目没有考虑地质问题，为了节省时间或者其他因素，基本没有开展监测量测工作 就开始动工。目前，在施工安全的决策方面，还没有把施工安全数据的粒度化应用 到施工决策中。面对施工安全的海量数据，这些数据可能是不完备、不精确和不 确定，为此当务之急就是对其粒度化分析，建立必要模型进行高效率的综合分析， 为下一步的地下施工安全提供相应的安全决策是非常有必要的。 粗糙集理论( r o u g hs e tt h e o r y ，r s t ) 由波兰数学家z p a w l a k 在1 9 8 2 年 提出，该理论能有效地分析和处理不精确、不一致、不完整等各种不完备信息， 并从中发现隐含的知识，提示潜在的规律。知识约简( k n o w l e d g er e d u c t i o n ，k s ) 是让高维数据在一定程度在降低维度的手段，常常作为数据挖掘( d a t am i n i n g ， d m ) 的一个预处理工具，其工作内容就是让整体原有数据的分类能力在原有的基 础上不改变，删除其中一些不必要或者不相关的知识，从而减少相关算法的搜索 时间，为后续的研究工作提高了效率。k s 是r s t 主要研究的核心问题之一，一般 将该研究方向大致可分为三个研究方面：求取某个的知识约简、求取全部的知识 约简和求取最小的知识约简。与其它数据降维的方法n 玑1 相比，使用粗糙集方法 进行知识约简的优势在于能够保持其数据本身的语义特征( s e r n a n t i cf e a t u r e s ， s f ) 1 2 o 与此同时还有主成分分析( p c a ) 、线性鉴别分析( l d a ) m 一钔等降维方法， 然而它们只对正态分布样本是最优的，而且l d a 不支持高维小样本问题，不能完 全区分线性可分样本m 巾3 等。许多学者都对知识约简算法问题进行过研究n 明， 其中已经公认的结论是求解信息系统最小约简是一个p 难题n 射。 在研究知识约简算法的过程中，对于决策表也可以采用盲目删除知识的办法 来求取最优d 一的知识约简或是次优d 一的知识约简，由于是盲目来删除知识， 所以就造成这是一个组全性的爆炸问题。因此，学者们在研究知识约简算法的过 程中，一般都沿用知识的重要度作为启发式信息来减少知识约简算法的搜索空间， 从而得到最优d 一知识约简或是d 一次优的知识约简。 由于知识约简的方法多样性，从而导致知识约简算法的类型也因实际项目目 的与学问研究出发点的而各有不同，其中知识约简算法采用差别矩阵 ( d i a m m i b i f i 够m a t r i c e s ，d m ) 计算方法有n 蝴1 ，采用分辨矩阵计算方法的知识约简 算法的时间复杂度通常都为q l c f l v l 2 ) ，其中i c i 为知识库中的知识个数，为知 识库中的对象数。这种知识约简算法的方法从理解性的角度来说，相对较直观、 易于人们在计算中的理解，但是在计算中会有生成一个分辨矩阵的中间过程以及 计算差别函数所对应的简化最小析取范式都会直接给整个算法提高了空间上的 较大开销。还有就是在计算知识约简的过程中，其中分辨矩阵中会产生大量的重 复元素，从而让这些重复的元素占用了大量的内存空间。故此类算法的复杂度相 3 武汉理工大学硕士学位论文 对较高，在计算的效率上也相对低下，一般并不适合处理海量的数据集。 目前，从计算p o s f ( d ) 的知识约简算法在时间上分析，由分析可以发现其中 以提高计算决定表正区域p o s c ( d ) 的算法效率归为一类，因为p o s r ( d ) 的计算 效率将直接影响到整个知识约简算法的时间复杂度。为此，在降低求解正区域 p o s r ( d ) 时间复杂度在研究上，我国许多学者为此做了大量的研究州妇等，其 中以刘少辉等啪1 提出利用快排法( 跏i c k s o r t ) 对知识集先进行排序，然后才对等 价类的进行划分，该算法已将计算正区域p o s r ( d ) 的时间复杂度降为 o ( i c l l u i i o g l u l ) 。在此研究的前提下徐章艳等例提出了采用基数排序( r 口d i x s o r t ) 来计算正区域p o s r ( d ) 方法，该计算正区域的方法将时间复杂度下降至 o ( i c i i u i ) 。葛浩等啪1 在其文章中详细地分析了徐章艳一求正区域p o s ，( d ) 算法中 所存在的局限性，且通过分析刘少辉一求正区域p o s r ( d ) 算法，在其算法研究的 前提下加以改进并提出了分布计数的r a d i x s o r t 算法，该求正区域p o s ，( d ) 算法 的时间复杂度也降至为o ( i c l l u l ) ，但该算法在效率上要优于文献哺3 的算法，并解 决了文献嘲1 中算法所存在的问题。然而文献啪1 通过动态生成s q l 语句也将计算正 区域的时间复杂度也降到o l c l l u1 ) ，文献n n 从完备信息系统的不一致记录来考虑， 文中给出了不一致记录的定义及其相关的性质，并对不一致记录与正区域 p o s r ( d ) 的等价关系给予了相关的证明。在此研究的前提下，该文给出了基于 h a s h 求解正区域p o s r ( d ) 的方法，该算法的时间复杂度下降为o ( 1 ui ) ，也是目前 相对来说最高效的求解算法。 从出发点为信息论的角度来看，采用信息论的知识约简算法有蕊弘眠眈1 等， 如果依据知识的重要度来进行选择下一个所要添加或删除的知识，称之为启发式 的知识约简算法，苗夺谦等1 对完备信息系统中决策表的知识重要度进行了相应 的重新定义，从信息论的方面来讲，知识重要性通过定义在决策表中给予度量， 然后利用此作为启发式信息，为此以决策知识和条件知识之间的互信息量作为启 发式信息的知识约简算法被提出了。通过对该算法加以分析，计算约简的搜索空 间在知识约简算法中被缩小了，通过大多数的数据集加以测试，其可以得到决策 表的d 一最优或d 一次优约简。对于较为突出的研究内容有，王国胤教授等删从 信息表示的角度出发研究，得出的结论有“约简的代数观点属于信息论观点一， 但是对一致决策表而言并基于此给出了基于条件信息熵( i n f o r m a t i o ne n t r o p y , l e ) 对完备信息系统决策表进行知识约简的两套知识约简算法一c e b a r k n c 和 c e b a r k c c 。c e b a r k n c 约简算法是基于所有条件知识集为起点，采用自顶向下 的方式删除其中不必要的知识：c e b a r k c c 约简算法则是基于完备信息系统决 策表的核知识集为起点，采用自底向上的方式依次增加知识。李小勇等啪1 等在文 献口2 1 的基础上直接从分析传感器监测到的动态数据入手，针对影响信任的多个度 武汉理工大学硕士学位论文 测指标进行自适应的数据挖掘与知识发现。 基于大数据集的知识约简算法3 l 矧等，随着时间的不断地推移，监控项目的 数据量也会不断地扩大，由此数据库容量也被要求不断扩大。由此，目前的多 数知识约简算法考虑空间复杂度远不够，对于海量数据的来说内存空间的要求由 此加大了，但是内存的容量毕竟有限，因而这些约简算法并不适用来处理海量的 数据集。为此，许多的学者都在努力研究适合海量数据集的知识约简算法：王国 胤教授等人嘲朋利用分治的算法思想提出了一种并行把知识约简的计算任务分 到多个c p u 同时运算的快速知识约简算法，知识约简算法的运算效率从而大大 的被提高了。吴子特嘲等人提出了一种借助s l i q 思想将完备信息系统决策表纵 向分割成不同的知识划分列表存储在硬盘上且仅在需要时调入内存的快速可伸 缩知识约简算法，此算法在内存空间上得到了很好地节省，算法的效率从也得到 了很大的提高。 基于连续值知识的约简算法溉柏鹳艏眠6 7 删等，文献汹1 提出了一种从连续值 知识决策表中获取知识的方法k a c g a 。该方法将经典r s t 对数据空间的等价划 分思路转换为相似划分的方法，把传统r s t 中正区域p o s r ( d ) 的表示方法扩充到 连续值一知识的决策表中：通过计算连续值一知识决策表中各条件聚类对决策类的 分类能力，从而生成相应的决策规则。文献h 伽提出了连续值一知识决策表中的可变 精度r s 模型以及基于此模型的连续值一知识约简算法，其知识约简算法可以对连 续值一知识进行约简，而且比经典r s 的相关方法在处理连续值一知识约简算法方 面更加有效。文献呻1 通过定义新的对象一致性，由此提出一种新的基于一致性准 则的知识约简模型，该模型可针对离散或连续值一知识进行有效的知识约简。其 它的一些知识约简算法，其中包括基于云模型决策表规则的知识约简算法h “删， 基于幂图的知识约简搜索式算法陬“蜘等，还有其它一些模型的算法呻7 0 j 1 7 2 3 等。 文献h 妇通过对完备信息系统决策表的转换，采用将规则映射成为云向量的方法， 利用云向量数学特征间的相似度来度量决策表规则间的不可分辨关系。苗夺谦等 人h 3 1 采用幂图对知识进行相应的表示，并给出了基于幂图的知识约简搜索式算 法，把知识约简计算问题转化为在幂图中的搜索问题。 以上分析的知识约简算法都是在知识完备的情况下，然而基于不完备信息系 统的r s 方法，近些年也取得了一些重要的进展h l 船饵娜1 矾巩眠引l 铷。从不同的 角度出发，文献璐卜船1 通过运用由数据导出的相容关系、量化容差关系、限制容差 关系、基于集对相似度、基于联系度分别提出了不同的针对不完备信息系统的 r s 扩展模型。其中文献m 1 提出的r s t 模型对相容关系的结构进行深入剖析，所 提的方法均是以获得知识集所决定的极大相容块( m a x i r m lc o n s i s t e n tb l o c k ， m c b ) 为基础，证明了i l c b 是不完备信息系统中的最小知识颗粒( 这就意味着， 5 武汉理工大学硕士学位论文 它可以为知识获取提供更有效的计算，特别是对于大规模不完备信息系统而言) ， 以m c b 为基本知识颗粒定义的近似算子比以对象的相容类为基本知识颗粒所定 义的更具有近似精度高的性质。以m c b 为最小知识颗粒的不完备信息决策系统， 其中所构造区分矩阵简化了区分矩阵的计算量，提高了用区分矩阵求知识约简的 效率。由此研究m c b 的快速求取算法显得非常重要，一方面，求出知识集决定的 相容关系再求m c b 的问题是n p h a r d 问题，另一方面先求出各个对象所在的相 容块，然后检验u 的任意子集是否满足文献m 3 中性质1 的条件，所设计的算法也 特别复杂。文献嘲3 提出了在不完备信息系统中以分层递阶的方式求取m c b 的构造 算法，从而简化了m c b 的求取过程。然而，该算法也有一定不足之处，在求取 m c b 的中间过程中没有进行非m c b 的却除，从而增加了算法的空间复杂度，因此 该算法仅适用于小规模不完备信息系统。 s t e f a b o w s k i 等人提出了基于非对称相似关系和基于量化容差关系的r s 扩充 模型，认为遗失值当前不存在的，不认为它是不确定的，因此一些看上去明显很 相同的对象被分到不同的相似类中。王国胤教授口7 1 提出了基于限制容差关系的扩 充模型，文献口羽在量化容差关系的基础上，提出了量化非对称相似关系的扩充模 型并在近似能力方面与量化容差关系作了相应的比较研究，而文献3 提出了限制 量化相容关系，是限制容差关系的改进。 容差关系和非对称相似关系是对不可分辨关系扩充的两个极端。容差关系的 条件太宽松，容易将根本没有相同已知知识信息的对象或只有极少相同的已经知 识信息的对象分到同个容差类。非对称相似关系的条件太严格，可能将具有很多 相同已知知识信息的对象分到不同的相似类，例如对象 1 , 0 ，1 ，i ，0 ，0 ，2 l 和 l ，0 ，i ，l , o ，0 ，2 被分到不同的类，而事实上二都相等的概率很大。因此，上述模 型在对知识分类时会出现知识粒度较大，分类精度较低等缺陷。然而限制容差关 系 3 刚好介于容差关系与非对称相似关系这两个极端情况之间，该模型有更多 的优点，但是它也存在局限性，即对于一个属性值都不确定的个体对象，必须单 独处理，这给不完备信息系统的处理带来不必要的麻烦。 在现实中，绝大多数信息系统是不完备的，关于不完备信息系统的知识约简 的研究还不够成熟，文献嘞8 1 8 乙8 3 朋8 5 眠8 7 黯瑚鲫1 等所给出的知识约简算法的时间复 杂度均为o ( 1 c 1 3 i u f ) 。大部分的算法实现中都要频繁地求解非完备信息系统或决策 表的相容类，但现有的方法计算耗时过大的缺陷直接影响其相关算法的性能。因 此，如何有效地计算非完备信息系统中的相容类是提高相关算法性能的一个关键 环节。文献嘲计算相容类的时间复杂度为d 科阱) ，本文中采用快速排序的方法降 低计算相容类时间复杂度，该计算相容类的方法时间复杂度为0 1 1 u i i c i a ) ，其中 o 。 按照累计沉降分类： 正常2 而，恐，而，x 4 ，而，而 ，偏高= 黾) ，偏小= 黾，五。 。 按照沉降速率分类： 正常2 “，而，x 6 ，x 7 ，黾，焉) ，偏大； x 4 ，毛 ，偏小= 怯，五。 。 三个属性定义了三个等价关系：r 1 ( 相对变形) ，r 2 ( 累计沉降量) ，r 3 ( 沉 降速率) ，由此可以利用集合表示的论域的不同划分： v & = 五，屯，而，x 6 ，而，而) ， 屯，毛，玉。) ) ， u 恐= 玉，屯，毛，x 6 ，j c 7 ，x o ， 屯) ， 毛，五。) ， u 马= ，屯，毛，而，黾，而) ， ，毛) ， 毛，五。) ) 。 由u & ，u r , 及u r , 构成的知识库足= 姒 焉，是，焉 ) 中的初等概念，基本概念 是由初等概念的交集构成的，例如由他，是 所表示的基本概念： 如，毛，五。n 纯) = 地) ，变形且累计沉降量偏大。 k ，毛，五。) n 玩，五。) = “，五。，变形且累计沉降量偏小。 1 2 武汉理工大学硕士学位论文 同理，也可以得到知识讽，恐) 、 r ，忍) 或佩，足，弓) 的基本概念。 两个知识库的关系：设置= ( u ，尸) 和局= ( 【，q ) 为两个知识库，( 1 ) 当 1 n d ( p ) = n v d ( q ) ，即u 1 n d ( p ) = u i n d ( q ) ，则称知识库墨与五：是等价的。( 2 ) 当 u i n d ( p ) c u i n d ( q ) 时，称知识库k 比知识库k ：更精细，或者说q 比p 更粗糙。 例如表2 中的两个知识库墨= ( ( ， 墨，马，墨) ) 和局= ( 【，馄，心) ) ，其中论域为 u = ，屯，毛，讫，而，黾，焉，x l o ) 。显然， 33 u i n d ( nr f ) = n 【x 】鼻= x i ，工2 ，x 6 ，工7 ，x 9 ， 工3 ， x ) ， 工5 ， x s ， 工i o 1 0 1 1 5 i 22 u i n d ( nr f ) = n 【x 】露= x l ，x 2 ，x 3 ，x ，x ，x 7 ，x 9 ， x 5 ， x l ，x i o 1 2 i 1 2 i 很明显，对于u 7 肋( 9 墨中任意一个元素，都能在u7 肋( ! = ! 墨中找到一个元素， 使得前者包含后者，换言之，u7 肋( 9 墨的商集中的每一个元：素都是v7 肋( ! = l 墨) 商集中某一个元素的子集或真子集，因此可以偈到此关系： 洲n d ( 侧n r ，) c 【，7 肋【q r 且u 肋【! = ! r f ) w n d ( 渊n a z ) 。即知识库k 比知识库k z 更 精细，且知识库墨与知识库墨不等价。 2 2 知识约简 知识约简是数据归约的一种表现形式，约简通常作为k d d 的一个预处理数 据的先行步骤，以完备、不完备信息系统的分类能力不改变作为前提条件是其基 本思想，删除其中不必要或不相关的知识，从而减少搜索空间，提高后续工作的效 率。其中有两具最基本的概念：约简与核。 2 2 1 知识的约简与核 定义2 1 给定一个知识库k = ( u ，r ) 和知识库中的一个等价关系蔟p e r ， v q ep ，若i n d ( p ) = i n d ( p 一 q ) 成立，则称知识q 为p 中不必要的，反之则称q 为 p 中必要的。 定义2 2 给定一个知识库k = ( c ，尺) 和知识库中的一个等价关系蔟p c r ， 对v g p ，若g 满足以下两个条件： ( 1 ) g 是独立的； ( 2 ) n v d ( g ) = 肋( 竹。 则称g 是p 的一个约简，记为g e a e d ( p ) ，其中脚( p ) 表示p 的全体约简组 成的集合。一般而言，知识约简不是唯一，可以有多种约简。 定义2 3 给定一个知识库x = ( c ，尺) 和知识库中的一个等价关系蔟p r ， 1 3 武汉理工大学硕士学位论文 对v g 户，若g 满足i n d ( p 一 g ) ) i n d ( p ) ，则称g 为尸中必要的，p 中所有必要 的知识组成的集合称为p 的核，记为c d 舾( p ) 。 定理2 1c o r e ( p ) = n 肛d ( p ) 。 下面举例说明上述概念，由表2 可以得到等价关系羁，足，墨及z n d ( r ) 所对应的 等价类，其中r = 池，恐，b 。 u 焉= “而，而，毛，毛，而，而 ， 黾，黾，而o ) ， u 如= 而，而，而，x 6 ，而，而 ， 黾) ， 黾，五o ) ， 【厂玛= 五，而，而，黾，而 ， ，墨) ， 玛，五o ) ， u i n d ( r ) = “，而，毛，而，而 ， ， ， 墨 ， 黾 ， 五o ，。 因为u i n d ( r 一 墨) ) = “，而，民，而，而 ，协 ，“ ，魄 ， ，如。 ) = u i n d ( r ) ，所以墨 为r 中不必要的。 因为u i n d ( r - r 2 ) = “，屯，而，而 ，他 ，“ ，玩 ，瓴 ，瓴o = u i n d ( r ) ，所以足 为r 中不必要的。 因为u i n d ( r 一池 ) = “，毛，而，气，而，而) ，玩 ，纯，五。 c ，肋( 尺) ，所以焉为r 中必要的。 由此，就得到的知识的核c o r e ( r ) = 假 。 2 2 2 知识的相对约简与相对核 定义2 4 知识q 相对于知识p 的正域定义为：p d 品( q ) 2 影，口p 一( x ) ，它 是论域u 中所有根据分类u p 的信息可以准确地划分关系q 的等价类中去的对 象的集合。 定义2 5 给定一个知识库k = ( c ，r ) 和知识库中的两个等价关系蔟p , qc _ r ， v gep ，若p o s ，d i ，) ( i n d ( q ) ) = p o s ，口，一l g ( i n d ( q ) ) 成立，则称知识g 为尸中 q 不必要的，反之则称知识g 为尸中q 必要的。为了方便起见，用p o s e ( q ) 替代 p d s 肿i ，) ( 肿( q ) ) 。 定义2 6 给定一个知识库k = ( 【，月) 和知识库中的两个等价关系蔟p , q c _ r ， v g p ，若g 满足以下两个条件： ( 1 ) g 是q 独立的； ( 2 ) p o s e ( q ) = p o s g ( q ) 。 则称g 是p 的一个约简，也称为g 是尸相对于q 的一个约简。 定义2 7 给定一个知识库k = ( 仉r ) 和知识库中的两个等价关系蔟p , q r ， v ge p ，若g 满p d s 肿i ，) ( 肋( q ) ) 乒p d s 肋( ， g l ( 肋( q ) ) ，则称g 为p 中q 必要的， p 中所有q 必要的知识组成的集合称为p 的q 核，也称为p 的相对于q 的核，记 为c o , 刚e e ( p ) 。 1 4 武汉理工大学硕士学位论文 举例说明上述概念，由表2 可以得到等价关系置，是，墨r = 倔，恐，焉) 及肋( r )