（计算机应用技术专业论文）粗集理论在电力客户数据挖掘中的应用研究.pdf

华北电力大学硕十学位论文摘要 攘要 自从1 9 9 8 年电力系统改革以来，我国电力系统逐渐进入一个开放的市场。在 殍敖的电力枣场中，企业必须更加深入她了解客户才能在市场巍争中获胜。企业 深入了解客户的一个有效途径是数器挖撼。 本文在深入研究了糨集理论之厝提出了一种基于最高可信度的补齐辣法 ( m c c ) ，并用实例证明了其有效性。提出了一种新的基于信息熵的属性约简算法 ( i e a r ) ，莠翔u c i 数鬟诞褥了该葵法熊骞效减少溪魏绞篱嚣豹勰瞧拿数。在分辑 了粗集的各种算法之后提出并实现了一个基于粗集的数据挖掘系统r s d m s 。分析 了电力客户数据中存在的数据挖掘模式并用r s d m s 系统对这些模式进行了挖掘， 结栗表明该系统是有效熬，该系统对它应弱领域瞧蠢缀好的逶藏性。 关键字：数獭挖掘，粗集。信息熵，数据补齐，属性约简 a 懿s 譬冀a e 零 t h ei n n o v a t i o no fe l e c t r i cp o w e r s y s t e mb e g i n si n19 9 8 ，f r o m t h e no n ，t h ee l e c t r i c p o w e rs y s t e mo fc h i n as t e p si n t o a l l o p e nm a r k e tg r a d u a l l y i nt h eo p e nm a r k e to f e l e c t r i cp o w e r s y s t e mc o m p a n y sn e e d t ok n o wm o r ea b o u tt h e i rc u s t o m e r si no r d e rt o a c h i e v es u c c e s si nt h ec o m p e t i t i o ni no p e nm a r k e t a f t e ri n d e p t hs t u d yo fr o u g hs e tt h e o r yam a xc o n f i d e n c eb a s e da l g o r i t h mo f d a t ac o m p l e t i n gn a m e dm c ci s p u tf o r w a r d ，a n dt h ev a l i d i t yo fm c c i st e s t i f i e db y e x a m p l e s an e wa t t r i b u t er e d u c t i o na l g o r i t h mb a s e do ni n f o r m a t i o ne n t r o p yn a m e d l e a ri sp u tf o r w a r dt h e n ，t h ee x p e r i m e n tw i t hu c id a t ap r o v e st h a tt h en u m b e ro f a t t r i b u t e sl e f ta f t e ra t t r i b u t er e d u c t i o nc a nb er e d u c e d e f f e c t i v e l yb yl e a r ar o u g h s e t b a s e dd a t a m i n i n gs y s t e m n a m e dr s d m si s p u t f o r w a r da n dr e a l i z e da f t e rt h e a n a l y s i so fa l g o r i t h m si nr o u g h s e t t h em o d et om i n i n gf r o mc u s t o m e rd a t ao fe l e c t r i c p o w e rs y s t e m i sd i s c u s s e da n di m p l e m e n t e di nr s d m s 。t h er e s u l ts h o w st h a tr s d m s i se f f e c t i v e ，a n dr s d m sc a l lb eu s e di no t h e rf i e l d sc o m m e n d a b l y x i o n gh a i j u n ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db yp r o lw a n g b a o y i k e yw o r d s ：d a t am i n i n g ，r o u g hs e t ，i n f o r m a t i o n e n t r o p y , d a t ac o m p l e t i n g ， a t t r i b u t er e d u c t i o n 声明 本人郑重声明：此处所提交的硕士学位论文粗集理论在电力客户数据挖掘中 的应用研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研 究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：整塑堡日期： 护p ；，1 2 - ；易。 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 懿均颦 导师签名： i e期：婴竺：! ! ：j 9 日期： 拯 盟 华北电力大学硕士学位论文 1 1 研究工作的背景 第一章绪论 数据挖掘概念自从1 9 8 9 年被提出至今已经形成一个新兴的研究领域，形成了 新的技术热点。粗集的出现又为数据挖掘提供了新的技术支持，并越来越受到研 究人员的广泛关注。8 0 年代英国电力企业体制改革成效显著，世界各国纷纷效仿。 我国从1 9 9 8 年开始了电力体制的改革，垄断机制被打破，电力行业逐渐进入一个 开放的市场。 1 1 1 数据挖掘的概念及研究现状 数据挖掘概念在1 9 8 9 年被提出，现己成为当前计算机科学界的一大热点。国 际上几乎每年都召开学术大会对其进行研讨，并逐渐从理论研究转向实际应用。 我国许多科研单位和高等院校也竞相开展知识发现的基础理论及其应用研究。 1 1 1 1 数据挖掘的概念 知识发现( k d d ) 被认为是从数据中发现有用知识的整个过程。数据挖掘( d m ) 被认为是k d d 过程中的一个特定步骤，它用专门算法从数据中抽取模式 ( p a t t e r n s ) 。数据挖掘( d a t am i n i n g ) 就是从大量的、不完整的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的 信息和知识的过程【1 ，2 1 。 数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提 升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的 研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算 等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的 技术热点。 1 1 1 2 国外研究现状 自k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议以来。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 3 次， 规模由原来的专题讨论会发展到国际学术大会，人数由二三十人到超过千人，论文 收录数量也迅速增加，研究重点也从发现方法逐渐转向系统应用转向大规模综合 华北电力大学硕士学位论文 聚统的开发，并且注重多种发现策略和技术的集成，以及多种学科之问的相飘渗 透。其它内容瓣专题会议迄熬数据笼掇鞍鲡谖发瑷列建议嚣之一，蔽为当蘸诗舞壤 科学界的一大热点。世界上研究数据挖掘的组织、机构和大学狠多。比较著稻的 如卡内基梅隆大学( 有机器制造d m 、多媒体数据库d m 、互连网d m 三个研究中心) 、 甄邀福大学、繇省理工学黢。著名研究执构热：a c m ( a e 臻s p e c i a li n t e r e s tg r o u p o n k n o w l e d g e d i s c o v e r y i nd a t aa n dd a t am i n i n g ) 、k d n e t ( t h ee u r o p e a n k n o w l e d g ed i s c o v e r yn e t w o r ko fe x c e l l e n c e ) 、n c d m ( t h en a t i o n a lc e n t e rf o r d a t am i n i n g ( n c d m ) a tt h eu n i v e r s i t yo f1 1 1 i n o i sa tc h i c a g o ( u i c ) ) 以及 一婆蠢秘、书簸、蕤菇等。 1 1 2 3 国内研究现状 与善终秘魄，鏊痰瓣d m k d 懿磅究穗瞧，没骞澎残整钵力量。1 9 9 3 年嚣家鑫 然科学基金蓠次支持我们对该领域的研究项目。目前，国内的许多科研单位和高 等院校竞相开展知识发现的基础理论及凝应用研究，这些单位包括清华大学、中 科院计算技术研究掰、空攀筵三研究魇、海军装备论涯中心等。其中，j 京系统 z 程研究所对模颧方法在知识发现中静液髑进行了较深入的舔究，j 京大学墩在 开展对数据立方体代数的研究，华中理工大学、复飘大学、浙江大学、中国科技 大学、中科院数学研究所、告林大学等单位开展了对关联规则开采算法的优化和 蒗建；嘉素大学、霆矮联会大学窝上海交逶大学等零健搽讨、礤袋了 绥 毒化数 据的知识发现以及w e b 数措挖掘。 1 1 。2 粗集璎论的概念和研究现状 1 1 2 1 粗糙繁的概念 褪糙集是出波兰华沙爨置大学p a w l a k 教授予2 0 擞纪8 0 年代提窭夔一静礴究 不完整、不确定知识的数掭的表达、学潮、归纳静薅论方法f 3 】。该方法的研究对 教是由一个多值属性集合描述的一个对象集合，由于信息的不精确性导致了对象 的不可分辨性，粗集理论采用不分疆对象类似形成的上近似和下j 驻似来描述一类 砖象，翟集方法胃弱来解决蘩要静分类阏惩，夔及掰决策囊瑟集会戆形式表示簸 黧要属性和特蹴分类之间的所有重要关系，此外粗集理论还广泛威用于数据约蔺， 数据融合等智能信息处理领域。 2 牮托电力大学磷士学位论定 1 2 。2 霆如醛突瓣装 2 0 毽爨8 0 年健褥，波兰酶p a w l a k 锋对g f r e g e 静逮器线醚城愚蕊掇爨了穰 糙嶷( r o u g hs e t ) ，它把郝些无法确认的个俸都麴辎于边界线醚域，雨这种逑努 线区域被定义为上i 穗似集秘下近似集之激爨。由予它曹确定的数学公式攒逃，完 全囱鼗囊凌楚，鬟滚委骞罄鼹毪。 1 9 9 1 单z p a w l a k 教授的第一举关予粮糙集专蒋张1 9 9 2 年r 。s l o w i n s k i 主编 越荧予粗糙熊成蔫与相关方法魄较研巍静论文集黝磁敝，维动了对褪糙集毽论戆 深入谚窕。1 9 9 2 每在波兰k i e k r z 疆开了羹一疆餮鞣凝糙黎学术灌论会，主瑟讨 论了集宫避骰嶷爻瓣基辜憋戆及冀瘫掰。1 9 9 3 每豢翻拿大b a f f 褥矛了豢二谣糕 糙集和知识黢现研讨会。遮次会议的童题怒粗糙集、模糊集与知识发现。1 9 9 4 年 在美溪s a r d o s e 召牙了第三溪蓬嚣糇糖浆与较诗舅蟒讨会，这次会谈主簧搽谤了 辍精集与骥獭逻鬓、秘爨黼络、进程理论等夔蘸合瀚题；1 9 9 5 颦谣嚣静蘩器骚模 糊壤论与拽零函际磷讨会，主要锌辩糨糙煞与模猢撩之瓣豹关系懑程了讨论，键遴 了粗糙集的燃展。1 9 9 9 罐猩日本召开髂七褐粗糙嫩、模糊集、数据挖掘和粒度一 较谤羹溪酥套谈；烹要鹚述了姿嚣羟糙嶷、搂赣纂煞聚变甏装鼹笈曩莛势。2 0 0 0 年在搬拿大键开了第二靥襁糙集耧计簿静警蘸趋势学术会谈。强蘸译多豢蘩瓣嚣 辩学术会议髂憋粗糕集理谂熬黟 突列入生要内窖乏。 上个毽皴9 0 零搜寒，潮内的专家学者、科研单位魏藏等院拨开始对粳糙熊避 蟹瓣究。这麓擎盈黎疆孛醛豌诗舅囊、搴薅陵塞穗缳簧、j 基塞王鼗丈学、嚣蜜交 通大学、重庆邮电学院、山西大学、合肥z 业大学，、上海大学、南昌大学镣。2 0 0 1 年5 莠在重淡粥开了“第l 聪中基r o u g h 鬃与软计瓣学术研讨会”，此曩类戗麟讨 会簿率召羿一次。 1 1 3 电力带螨佬现状 煞鞠冬我寒惹，鹱焚鏊凳蓄霭辩主耄擎多餮家遴稽了亳力王遂警鬟髂黎熬浚 摹，其露棘郝怒开菔泡力肃炀，善；入竞争枫麓，降低发惫戒本，螽莲耐瘸资源， 潞最终使用户获剩。扶1 9 9 8 年开始，溅嚣瞧确定攥魄力行业实费“厂踺分开、觉 价上网”豹澈革，弗确定出东、上海、浙江及东北的辽宁、吉林、黑龙淡6 个电 弱秀善懿“厂黪努嚣”懿谈疼摹霞。2 0 0 0 每 嚣蠹寒、上海、渗连发毫餐毫交帮 场j e 式投入商业化运行，求北三省电力市场将在2 0 0 0 年4 胃难斌投运。通道镩试 点肇位的甫渤垂匕运俘，以期在发彀侧譬l 入帝场规划，竞价上网，并积累缀骏，逐 步海完善魏魍力泰爨靠运嘲。 蔽擐鏊家奄力公霹的淡革方案，将遴步试行爆户参毒逸鸯潆璐竞争憋方式， 允许用户裔娃j 购电。电力市场向确产开放，将取淌艨有的供电髂妲区的概念，产 t 华北电力大学硕士学位论文 缴新的电力销铸商。电力销售商不必拥肖配电网络，可以直接从发电厂或市场中 麴邀，著囱曩户鼓毫霹售壤；雳户瞧可以鑫圭建选强国发电厂购嘏、骞枣场建惫、 向当地的供电部门购电或向电力销售商购电。此外双边交易成为电力交易的主要 形式，即允许用户参与市场，电网经营众业不再是单一购买者，电网经营企业与 发魄厂闯的购销合同将大为减少，取霹健之的是大嫩的用户( 包括电力销售窝) 与 授邀厂的霰逸会两。 1 2 研究工作的意义 随着i n t e r n e t 的发展，电子商务褥剐了飞速发展，全球市场竞争的加剧和客 户濡求多元化的要求，给传统的商业经济模式带来了巨大的冲击。传统企业慕于 产黯豹竞争模式已逐渐被蒸予客户关系瓣经营理念掰取找，未来露缓戆竞争泌演 燮成服务手段的竞争，建立和发展长期豹客户关系怒企业成功的关键，以诧为特 掘的c r m 技术及其与之相关的系统已成为企业赢樗竞争优势的激要手段。馁是 强调以“客户关系一对一瓒论”为基础、肇在改善众业与客户之间关系的新溅管 壤税翻，阕瓣魄是包綦一个缀织穰穗凝鞭、选择、争取、发震霰僚持客产潺簧实 施的全部商业过程【5 l 。 目前我国电力公司也以电力市场化为基本改革取向，这就使譬孽电力行业逐渐 进入一个开放豹枣场。貔羲邀力枣场鼗敬革熬不叛深入，电力金娥毒必要建立客 户关系管理系统以提高企她的市场竞争力。 在客户关系管理系统中，研究重点怒智能客户分析系统。客户分析系统藏好 怒数据挖掘发撵重要作用的领域，从大黧的客户数据巾挖掘出隐禽的、先前束箱 的、对决策存缀大徐蓬豹躲谖移燕爨，辩缝够稷攥融鸯懿信惠对采发生孬为徽逡 结果预测，为念业经营决策、市场策划提供依据。 因此本文考虑对粗集理论进行研究，采用基于数据挖掘的方法发现潜在于电 力客户数据孛弱手模式，戈邀力金照握镞决策支持。翊辩本文对凝集理论及数滤 挖掘系统结构的研究，对数据挖掘和糨集理论的发展起到了一定的促进作用。 1 3 研究工作的内容和组织结构 本文的研究工作体现柱以下几个方面： 1 研究了粗糙集基本理论及其在数据预处理方筒的应用算法，提出了熬于 最裹霹嫠疫数舞蛰务算法； 2 研究了基于粗糙集的决策规则擒取算法，并提出了一个新的属性约简弹 4 华北电力大学硕士学位论文 法； 3 提警了一令墓予糕髓集垂冬数撵擦键整诲模黧r s d m s ； 4 研究了电力市场环境下电力客户数据挖掘的主要挖掘模式； 5 开发突现了基于粗糙集的数据挖掘系统r s d m s ，并用该系统对电力客户数 据上的挖掘模式避萼亍了挖掘； 本文共分七章，内容安排如下：第一举是绪论，釜要介绍谦麓背景及意义； 第二章主要介绍粗糙集理论；第三章介绍了数据预处理中算法；第四章介绍了属 性约简和规则发现中用到的算法；第五章介绍了客户关系管理与数据挖掘；第六 露穷绥了r s d m s 系统维擒及蜜镶笼藏；第七辜螽绣了零蘩究褥懑瓣结论。 5 华北电力大学硕士学位论文 筹二章糍集基本理论 2 1 粗集的定义及知识裘示 粗集理论认为知识就怒分类能力，其基本理论怒建立在分类簇础上的。本节 荫先介绍了知识与分类的熬系，然后给出了粗集的滗义以及粗集中的知识表示， 最后给出了糨集中可辨识筑黪的概念。 2 1 1 不可分辨关系 绘定对象集会u _ 帮u 上豹一个等徐关系族r ，羲p c r ，p 孛愈鄂等徐关系爨 交集ip 也是个等价关系，称为p 上的不可分辨关系，记为i n d ( p ) ： x i n d ( p ) = im ， 假定r 中的任何基本集合相互不可分辨：“翻如两个任意对象x 。，x 2 u ，如果 它髑两者帮藩予葙溺懿基零集合x l ，鼯x ；，x ：r ，我餐称它铜爨有稿同静撼遮， 即： d e s ( x - ) = d e s ( x 2 ) = d e s ( x ；) 这撵u i n d ( p ) 定义尧等徐关系p 翳族稳关戆皴派，称隽p 簇零熟识。荛楚 便起见，常常将u i n d ( p ) 记为u p 。 2 1 2 知识与分类 知识是人粪通过实践认识到的客观规律，是对实践经验的总结、提炼和撤象。 从认知科学的一些观点来瓣，可以认为知识来源于对其它物种的分类能力。椒集 溅论菝是采弱遂静疑点来定义酝识懿，霞竣为懿识藏蹩分类戆力。起谖一般哥分 为说明性知识，过程性知议和控制性知谈。说明性知识是对现实中客观实体的摇 述，是区分客观个体的知识；过程性知识是关于如何用说明性知识来实现对客观 个体进行分类的知识；控制性知识则是关于如何用避程性知识来实现对客观个体 滋行分类豹懿谈。 假定我们起初对论域中的对象具有必要的信息戏者知识，通过这些知识我们 就能够将论域中对象分成不问类别。若根据已有的知识不能够将两个或者两个以 主对象区分开，剿扶羹它们楚不可区分鹣，在粗集璁论孛魏它粥矮骞等秘关系。 遥常我们在讨论一类问题的时候都局限在一定的范围内，在这个豫蔺内的所存对 歙，构成了问题的讨论域，在粗集理论中称为论域u 。从数理逻辑的角度来餐， 6 华北电力大学硕士学位论文 可以将分类认为是等价关系，这些等价关系对论域u 进行划分。对于一个等价关 系中的所有对象构成一个对象集x ，它们具有一类共同的抽象，称之为论域u 中 的一个概念。在论域u 中可能存在多个概念，论域u 中的概念簇称之为关于u 的 知识，它就是一种对论域u 中对象的分类能力。因此知识就可以定义为：给定对 象集合u 和一个等价关系集合r ，等价关系r 对u 的划分就是知识，记为u r 。u 上的划分簇称为u 上的知识库。下面通过一个实例来说明分类知识。 给定一个玩具积木的集合u = x ，x 。，x 。) ，每个对象有颜色、大小和形状三个属 性，采用不同的属性组合来描述对象，就形成了不同的分类知识。 表2 1 玩具积木信息表 u颜色 大小形状 x 1红小圆 x z蓝大矩形 x 3红小三角形 x 蓝小三角形 x s黄 小圆 x 6黄 小矩形 通过三个不同的等价关系r 。( 颜色) 、r 。( 大小) 、r 。( 形状) 可将论域u 划 分成三个等价类： u r 。= “x 。，x 。) ， x 。，x 。) ，f x 。，x 。) ) u r z = “x l ，x 3 ，x 4 ，x 5 ，x b ) ， x 2 ) u r 。= x 。x 。) ，( x ：，x 。 ，( x ，x 4 ) 这些等价类是知识库中的初等概念，它们的交集构成基本概念，如： f x 。，x 。 i x ，x 。) = ( x 。 ( x “x 4 i x ：，x 。 = x ： x 。，x 。) i ( x 。，x 。) = x 。) 分别是( r 。，飓) 的基本概念：红圆，蓝矩形和黄圆。 集合： x l ，x 3 ) i x l ，x 3 ，x 4 ，x 5 ，x b ) i ( x 。，x 5 ) = x 1 ) x 2 ，x 4 i x 1 ，x 3 ，x ，x 5 ，x b ) i ( x 3 ，x 4 ) = f x 4 ( x 5 x 。 i x x 3 ，x 4 ，x 5 ，x 6 ) i x 2 ，x 8 ) = ( x b 分别是( r 。，r ：，r 0 基本概念：红色小圆，蓝色大矩形和黄色小矩形。 从上面可以看出存在一些初等概念的交集为空，也就是说这些概念无法从该 知识库中得到。 华北电力大学硕士学位论文 2 1 3 粗集的定义 粗集理论鼹一种刻画不完整性和不确定性信息的数学工具，能有效地分析和 处理不精确、不一致、不究整等各种不先备信息，并从中发现隐含的知识，揭示 游农豹援律强】。粗集理论敷浅察稠测量掇褥戆数据并避蠢分类静方法为基磴，它 认为知识是基于对对象分炎的能力，知谈直接与真实或抽象世界有关豹不同分类 模式联系在一起。粗集用上近似、下避似和边界来刻画信息的不确定性。 令x u ，鼠r 为一等价关系，当x 为菜些r 基本范畴的并时，我们称x 是 冀霹定义懿，黉翔x 兔r 不霹定义。r 为霹定交集憝论域魏子集，宅霹在翘谈蓐 k 中被精确地定义，而r 不可定义集不能在这个知识库中被定义。r 可定义祭称 作r 精确集，r 不可定义集称为r 非精确集。 当存在一簿玲关系r e i n d ( k ) ，毽x 为r 精确集，集合x 量u 稼为k 中豹 精确集；当对于任何r i n d ( k ) ，但x 为r 租集，涮x 称为k 中的粗集。糕榘 可近似地定义，为达到这个目的，使用两个精确集( 上进似和下近似) 来描述。 假设给定知识库k = ( u ，r ) ，对予每个子集x c _ u 和一个等价关系r i n d k ) ，可醵校攒r 静基本袋含兹搐述来翔分集会x 。上近钕帮下= i 毽钕霹耀下稀懿 等式表达： r 。( x ) = u x u ：【x 】r 互x ) 囊一 x ) = u x u ： x l s i ) ( 爹 其中r 蹙u 上的等价必系，u r 是r 的所有等价类族，【x 】r 怒u r 中的个 概念( 范畴) ，溅者称之为x 元素的r 等价类。分别称它们为x 的r 下近似和r 上邋似，b n r ( x ) = 寅一( x ) 一r ( x ) 称为x 的r 边界。 我髓氇怒p o s a ( x ) 一r 一( ) ( ) ，称兔x 静受歪城，把n e g g ( x ) = 融r 一( x ) 称 为x 的r 负域。 正域p o s r ( x ) 是那些对于知识r 能宪全确定地! 髓入x 的对象綮合；负域n e g r x ) 是那些不戆骥定一定麴入x 豹对鬏集合盖，京蹩正域豹蛰纂。边要是糕不 能肯定地属予p o s r ( x ) 又不能肯定地属于n e g r ( x ) 。x 的上近似五一( x ) 是那些 对于知识r 不能排除它们属于x 的可能性的对象的熊合，从形式上看，上近似就 怒下近似和边器的井集。 在上节表中，对予属傻子集r i 大夺，形状 ，集合x = x l ，x 2 , x 3 是一个r 鹣 糨集，下面分别计算集合) ( 的上近似、下近似、正域、负域和边界。 首先计算论域u 的所有r 基本集。 u l i n d ( r ) 2 x l ，x s ， x 2 ， 拍， x 3 ，x 4 由此可褥熬合x 的上i 琏似集、下近似集、正域、负域和边界： 8 华北电力大举硕士学位论文 r 一( x ) 2 x l ，x 2 ，x 3 ，x 4 ，x 5 ) 聂一产 ； p o s r ( x ) 一r 一( x ) _ x 2 ) n e g r ( x ) 2 x 2 ，x 3 ，x 4 ，x 5 。x 6 ) b n r ( x ) = r “( x ) 一r 一( x ) 一 x l ，x 3 ，x 4 ，x d 集合x 瓣上近 菇集，下近钕集还可以形象逮表示为下图繇示。 2 ，1 ，4 粗集知谈表达系统 窝2 1 褪絮结梅图 粗集是一种研究机器学习的科学，鼹让机器具有学习能力，就应该让它鼹脊 相应的知识，疆让机器理解知识就是要研究知识的裘示和知识的摊演。近年来知 谈表示瓣疆嚣孳l 起了广泛戆关注。嚣蔫，零建貔躲谈表示方法蠢，遂辑模式、罐 絮、语义网络、产生式规则、状态空间和居4 本等，谗些是知识工程需要研究的内 容。粗集中采用信息表和决策表来表达知识。 2 。 。4 。 售意裘 在人工智能领域中，一个对象通常使用一个属性值对来表承，对象集就是 这榉的对象集会，记为u 。u 可以被划分不相交的多个子集。情感表知识表达系 统虢是磺究辩象集合闻蘧，关于这釜霹豢瓣知识是逶过掺定对象辩属惶和它瓣瓣 性值来描述的。一般地，一个信息表知识表达系统s 可以表示为： s * u ，r ，v p 这里，u 怒慰象集会， 纛穗为论蠛，r = c o b 是溪瞧集台，予繁c 嚣d 分爰狠 为条件属性集合和决策属饿集合，v = y v , 是属性值集合，v ，表示r r 的属憔德 范阑，即属性r 的值域，f ：u x r v 是l 个信息函数，它指定u 中每一个对象x 的媾性值。 为了壹蕊方便，u 氇爵黻写或一令淡，鳜辘表示辩象标记，横辘表示对象麓 性，实例标记与属性的交会点是这个实例在这个属性的值，这个袭称为信息表， 9 华北电力大学硕士学位论文 是表达撞述囊羹识瓣数据表捺。 对于每个属性予集b 譬r ，我们可以意义一个不可分辨二元关系i n d ( b ) ，即： l n d ( b ) = ( x ，y ) t ( x ，y ) gu 2 ，v beb ( 秘；蠢( y ) ) 显然i n d ( b ) 是一个等价关系，且： i n d ( b ) = in e d ( 6 ) 每个子集b c _ r 也称为一个属性，玺。b 是单元素属性时，称b 为原始的，否 则称b 为复合鲍。属性b 霹以认为是用等价关系袭示的知识的一个名称，称为标 识属性。一个表可以看作怒个等价关系簇，即奎玎识库。如表2 1 就是个信息 表，可看成一个描述积木玩具的一个知识艨。 2 1 4 2 决策表 当信息液中的决策属性集d 不为空时，我们称信息表为决策表，属性集d 中 属性的个数可以是一个或者多个，当决策液中决戴属性的个数多于一个时，一般 采用合并的方法将决策属健合并成单一属性，从而简化问题的求解。 下露绘出一个决策表蛇典型倒予： 表2 - 2 医疗数据决策表 u 体温干嚷 头疼 周身疼 流感 l正常无无无无 2 正常无有 有无 3 偏高无有 有有 4 赢 有有有有 其中条l 牛属性有体温、于咳、头疼、周身疼，决策属性为是设流感。在决策 表中每一条记录可精成一个对象，每一个对象可叛看成怒一条决策规尉。如对象 l 可以表示成( 体温= 正常) ( 于咳一无) 八( 头疼一无) 八( 周身疼一无) 等( 流感一 无) 。在许多决策闻题都可议霞决策表来袭达，这个工其在决策应用中超饕稳当羹 要的作用。如表2 - 2 用于记录医院的医疗数据，条件属性是症状和检测，决策属 往楚病症。翔采丽凌策表来獾透一个工盈过程，剃实铡惑在菜些特定静辩润在巢 些特定的采样点采集的数据样品，条件属性是过程中的参数，决策属性是有操作 员采取静嚣渤。有了这些掰变数疆，就可叛麸中挖瓣密豫藏在箕牵豹有麓豹规律， 用与指导以厢的工作。 1 0 华北电力大学硕士学位论文 2 1 5 可辨识矩阵 定义2 - 1 令决策表系统为s = ，r = p ud 是属性集合，予集 p = a i l i = l ，m ) 和d = d ) 分别称为条件属性集和决策属性集，u = x l ，x 2 x 。) 鼹论 域，a i ( x j ) 是榉零x j 在属瞧a i 上的取嬗。c 瑙) 表示霹洪识矩簿鹃第i 行j 列数元 素，则可辨识炬阵c d 定义为7 l ： r 鲰| a k sp a a k ( x i ) ：g ：a k ( x i ) ，d ( x i ) 黛d ( x i ) c d ( i , j ) = l公式( 2 w 1 ) k 0 ，d ( x i ) = d ( x j ) 显然，可辨识矩阵是一个依主对角线对称的矩降，在考虑可辨识矩阵的时候， 只需要考虑上三角或者下三角就可以了。 疆摆霹豢浚矩疼魏定义蔼熟，当鼹令楚象熬抉簸溪蛙蓬摇弱辩，它秘骚辩瘦 的可辨识矩阵的元素值为0 ；当两个样本的决策属髋不同且可以通过某些属性的 取值不同加以区分时，它们所对应的可辨识矩阵元索的取值为这两个对象的祭件 满性值不同嬲灏性集会，即可以区分在薄个对象的条 牛属性集会 当两个对象发 黛冲突曝，帮掰有的条俘属性裙目面决策不霹，蒯它们所对应静霹辨谖矩阵静元 索取值为空集。显然，可辨识矩阵元素中是否包含空集元素可作为判断决策表系 统中是否包含冲突信息。 薅予一般瓣售惠表露京，宅翻没蠢浚绫疆蛙，它袋貔霹辨识艇舞会毒襞不潮， 奠定义如下： 定义2 - 2 令信息表系统为s = u ，r ，v ，p ，r 是属性攥合，u = x l ，x 2 ，x n 是论域， a i ( x j ) 是样本x j 在_ | 羼性a i 上瓣取擅。c d ( i , j ) 表示可辨谈矩阵鞠第i 嚣j 列豹元豢， 弼可辨识矩阵e d 定义为： c d ( ) = a kia k p aa k ( x i ) a k ( x j ) ；公式( 2 - 2 ) 其中i , j = l 2 ，n 。 2 2 知识的简化和核 2 。2 。 翔识憨簿佬翻核的溉念 在实际应用中，我们疑常需要在保持知识库中的初等范畴的情况下消去冗佘 的基本范畴，进行知识的筒化。完成知识简化的基本工作就是围绕“简化”和“核” 遮嚣拿概念采滋行豹溜。 在定义简化之前，先作如下定义： 华北电力大学硕士学位论文 定义2 3 令r 为一等价关系族，且r e r ，当i n d ( r ) = i n d ( r r ) ，称r 为 r 中可省略的，否则1 - 为r 中不可省略的。 定义2 - 4 当对于任一r e r ，若r 不可省略，则称r 为独立的。 定理2 - 1 当r 是独立的，且p r ，则p 也是独立的； 定义2 5p 的核是其所有简化族的交集用公式表示如下： c o r e ( p ) = ir e d ( p )公式( 2 3 ) 2 2 2 知识的相对简化和相对核 令p 和q 为u 中的等价关系，q 的p 正域记为p o s p ( q ) ，即： p o s r ( q ) 2 ，r ( x ) 对于u p 的分类，u q 的正域是论域中所有通过分类u p 表达的知识能够确 定划入u q 类对象的集合。 p 和q 为u 中的等价关系族，当p o s i 。d ( p ) ( i n d ( q ) ) = p o s i 。d ( p - r 1 ) ( i n d ( q ) ) 时，称r p 为p 中q 可省略的。否则，r 为p 中q 不可省略的。 当p 中每一个r 都是q 不可省略的，则称p 为q 独立的。当s 为p 的q 独立 子族，且p o s s ( q ) = p o s p ( q ) ，则族s c p 称为p 的q 简化。 p 中所有q 不可省略的原始关系族称为p 的q 核，用公式表示为： c o r e q ( p ) 2 ir e d q ( p ) 下面通过举例来说明知识的相对简化和相对核的概念。 表2 3 医疗数据决策表 u体温( t )干咳( c )头疼( h )流感( s ) l正常无无无 2正常无有无 3偏高无有有 4高有有有 5偏高有无有 6高无 无无 7偏高有 有有 8 高有无有 假设等价关系族r = t ，c ，h ) ，则有如下等价类： u ，t = “1 ，2 ) ，( 3 , 5 ，7 ， 4 ，6 ，8 ) u c 2 “1 ，2 ，3 ，6 ) ， 4 ，5 ，7 ，8 ) ) u h = “1 ，5 ，6 ，8 ) ， 2 ，3 ，4 ，7 ) 1 2 华北电力大学硕士学位论文 u r = 1 ， 2 ， 3 ) ， 4 ) ， 5 ， 6 ， 7 ， 8 ) ) u s = “1 ，2 ，6 ， 3 ，4 ，5 ，7 ，8 ) 对于r ，s 的正域为： p o s r ( s ) = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) 为计算相对于s ，r 的核和简化，我们首先要计算r 中的等价关系是否可省 略。 u i n d ( r t ) = 1 ，6 ) ， 2 ，3 ) ， 4 ，7 ) ，( 5 ，8 ) u i n d ( r c ) 2 “1 ) ， 2 ) ， 3 ，7 ) ， 4 ) ， 5 ， 6 ，8 ) ) u i n d ( r - h ) = “1 ，2 ， 3 ) ， 4 ，8 ) ， 5 ，7 ) ， 6 ) ) 根据上一节简化的概念，删除r 中的每个等价关系都不能保证等价类保持不 变，因此t ，c ，h 等价关系都不是绝对可省略的，下面讨论它们相对于s 的简 化问题。 根据相对简化的概念，要知道某一等价关系是否可以省略要看省略该等价关 系之后的正域是否保持不变，若保持不变，则认为该等价关系是可以省略的，否 则认为该等价关系是不可省略的。 p o s ( r ( t ) ( s ) 2 1 ，4 , 5 ，6 ，7 ，8 p o s ( r ( c ) ) ( s ) ； 1 ，2 ，3 ，4 ，5 ，7 ) p o s ( r ( h ) ( s ) = 1 , 2 ，3 ，4 ，5 ，6 ，7 ，8 = p o s r ( s ) 根据相对简化和相对核的定义可知，h 是r 中相对于s 可省略的，而t 和c 是r 中相对于s 不可省略的。这样r 的s 核c o r e s ( r ) = t ，c ) ，它也是r 的s 简化。 通过这种方法可以求出r 的s 简化，其中相对核是必须保留的部分。当核以 外的等价关系为多个时，可能会产生多种简化形式；当r 中所有的等价关系都不 可省略时，即c o r e s ( r ) = r ，则r 是相对于s 独立的。 2 3 知识的依赖性 2 3 1 知识的依赖性的概念 要进行知识的简化，并从一个给定的知识中导出另一知识，我们必须研究范 畴之间的依赖关系。 当q 中的所有初等范畴可以用p 中某些初等范畴定义时，则知识q 是从知识 p 中可导的。当q 从知识p 中可导时，我们称q 依赖于p ，记作p j q 。 依赖性的形式化的定义如下f 9 】： 令k = ( u ，r ) 为一知识库，且令p ，q c r ： 华北电力大学硕士学位论文 ( 1 ) 当i n d ( p ) c i n d ( q ) ，知识q 依赖于知识p ； ( 2 ) 当p j o 且q j p ，知识p 和q 是等价的； ( 3 ) 当不存在p j o ，且不存在o j p ，则p ，q 相互独立。 下面给出一个简单的例子来说明知识的依赖性。设有等价关系p 和q ，且有 如下划分： u p = “l ，2 ) ， 3 ，4 ) ， 5 ，6 ) ， 7 ，8 ) ) u q = “1 ，2 ) ， 3 ，4 ，5 ，6 ) ， 7 ，8 ) ) 显然有i n d ( p ) c i n d ( q ) ，因此有p j q ，即知识o 依赖于知识p 。 2 3 2 知识的依赖性的度量 从上面的例子可以看出，知识之间可能存在部分依赖关系，因此可以用知识 的正域的概念来描述知识的依赖度。q 依赖于p 的依赖度可表示为： r v ( q ) = i p o s p ( q ) l l u l 下面举例说明依赖度的求法。 u p = “1 ，2 ) ， 3 ，4 ) ， 5 ，6 ，7 ，8 ) u q = “1 ，2 ) ， 3 ，4 ，5 ，6 ) ， 7 ，8 ) ) p o s y ( q ) = 1 , 2 ，3 ，4 因此o 相对于p 的依赖度为： r p ( q ) = i p o s v ( q ) u = 4 8 = 0 5 知识的依赖度说明了知识之间的依赖程度，当r p ( q ) = 1 时，说明o 知识完全 依赖于知识p ；当r p ( q ) = o 时，说明知识o 不依赖于知识p ：当0 r p ( q ) l 时， 说明知识q 部分依赖于知识p 。当o 依赖于p 的依赖度为1 ，且p 依赖于q 的依 赖度为1 时，我们称p ，q 等价。 2 4 可变精度粗集( v p r s ) 为了增强粗集模型的抗干扰能力，z i a r k o 将标准模型扩展形成了可变精度粗 集( v p r s ) 模型，该模型通过引入数据内含的统计信息，从而更便于处理不完整 的数据。 在v p r s 中，它允许一定的误分类率b ( t 3 【0 , 0 5 】) 。与标准粗集模型相类 似，v p r s 中也定义了y 的r ( c ) b 正域p o s c9 ( y ) 、y 的r ( c ) b 负域n e g 、 c 4 ( y ) 、y 的r ( c ) 边界域b n g c 9 ( y ) 。具体如下： p o s e 。( y ) = u x i u r n ( c ) 且p r ( y l x i ) 1 - b ) 1 4 华北电力大学硕士学位论文 n e c c 9 ( y ) = t j x i u r ( c ) 且p r ( y i x i ) b ) b n d c 9 ( y ) = t 2 x i u r ( c ) 且b p r ( y l x i ) 1 一b ) p o s c 。( y ) 表示根据等价关系r ( c ) ，将u 中的元素误分类到y 中的概率不 超过b 的等价类的集合：n e c e 9 ( y ) 表示根据等价关系r ( c ) ，将u 中的元素误 分类到y 中的概率超过1 1 3 的等价类的集合；b n d c 9 ( y ) 是二者之差。 对于区分y 丽言，并非所有的条件属性都是需要的，因此v p r s 中引进属性 的b 约简。对于任意a c ，如果p o s c9 ( y ) = p o s c 一 。15 ( y ) ，则认为a 是冗余属性， 称c = c 一 a ) 为c 的一个1 3 约简。c 的所有1 3 约简记为r e d 。( c ，d ) 。 在b 约简的基础上，可以得到决策的规则。设r e d 是r e d 8r c ，d ) 中的一个 约简，u r ( r e d ) = x l ，x 2 ，x 。 ，则一等价类x i 的描述d e s ( x i ) 可以用下式表示： d e s ( x i ) = 八( 任意aer e d 且a = f ( x i ，a ) ) 式中， 表示并算子，x i 表示等价类x i 中的一个元素。类似的，y 的描述 d e s ( y ) 可表示为： d e s ( y ) = ( d - - f ( x i ，d ) ) 式中的d 是一决策属性。 2 5 粗集的优点 粗集在数学理论上非常严密，有一套处理数据分类问题的数学方法，尤其是 在对不确定，不完整和不精确的数据进行处理时非常有效。 粗集理论的实用性非常强，粗集理论是为开发自动规则生成系统而提出的， 因而它的研究完全是应用驱动的。 粗集理论无需提供除问题所需的数据集合之外的任何先验知识，这是和模糊 理论及证据理论的重要区别。 粗集理论能发现数据中隐含的模式和关系，对数据进行约简，评价数据的重 要性，从数据中产生规则，结果易于理解。 2 6 小结 本章首先介绍了粗集的基本思想、粗集的知识表示、粗集的定义、可辨识矩 阵的概念，然后介绍了粗集理论知识简化和核以及知识的依赖性的概念、知识依 赖性的度量，信息熵和可变精度粗集，最后总结了粗集理论突出优点。 华北电力大学硕士学位论文 3 1 数据补齐 第三章数提预焚璞 实际问题中，待处理的数据常有菜种程度的不完备，这表现猩知识表示系统 或决策系统中即某些属性没有赋值。谶成这种情况的原因可能谢以下几种：“1 有些信息无法获取；( 2 ) 获取这些信息的代价较大；( 3 ) 实对性能要求较高。在信息 衮中存在遗灸满经毽，帮僚惑表不完舔辩，给蔑黧发蠛算法静实麓带来不便，处 理此类问题的一种方法是删除有遗失值的对象，这种方法适用于信息表数据墩相 对于遗失属性慎数量很大的情况。但是，当信息表中的信息较少、存在遗失使的 瓣象程薅鞍多辩，一般采趱数蕹蛰赛算法薅其逶霉於赛，下嚣藏足耱数据羚齐葵 法进行讨论。 3 。1 平均值补齐算法 平均值补齐算法( m e a nc o m p l e t e r ) 分为两种情况。当属性列的数据类