第 ２５ 卷第 １ 期 ２００８ 年 １ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ．２５ Ｎｏ．１ Ｊａｎ．２００８ 倡 不 完 备 信 息 系 统 的 数 据 挖 掘 方 法 研 究 １， 刘思伟 邢化玲 ２， 高社生 １， 唐士杰 １ （１．西北工业大学 自动化学院， 西安 ７１００７２； ２．西安测绘研究所， 西安 ７１００５４） 摘　要： 根据分层递阶约简算法，提出了一种直接在不完备信息系统上进行数据挖掘的方法。 该方法首先将信 息系统中由所有属性构成的单层知识表示转变成由部分属性所构成的多层知识表示，即由完备属性和不完备属 性表示；然后建立了两个不同层次的子系统，并推导出各个子系统的规则集；最后，将该方法应用于心脏病诊断 系统的研究。 仿真结果证明，该方法具有较强的实用性和有效性，并能提高知识约简的速度。 关键词： 不完备信息系统； 粗糙集； 数据挖掘； 分层递阶约简 中图分类号： ＴＰ２７４　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２００８）０１唱００９０唱０３ Ｒｅｓｅａｒｃｈ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ＸＩＮＧ Ｈｕａ唱ｌｉｎｇ１， ＬＩＵ Ｓｉ唱ｗｅｉ２， ＧＡＯ Ｓｈｅ唱ｓｈｅｎｇ１， ＴＡＮＧ Ｓｈｉ唱ｊｉｅ１ （１．College of Automation， Northwestern Polytechnichal University， Xi’ an ７１００７２， China； ２．Xi’ an Mapping Institute， Xi’ an ７１００５４， China） Abstract： Ｂａｓｅｄ ｏｎ ｔｈｅ ｈｉｅｒａｒｃｈｉｃａｌ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｄａｔａ ｍｉｎｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｒｏｕｇｈ ｓｅｔｓ ｔｈｅｏｒｙ ｆｏｒ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ．Ｋｎｏｗｌｅｄｇｅ ｗａｓ ｐｒｅｓｅｎｔｅｄ ｈｉｅｒａｒｃｈｉｃａｌｌｙ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｌａｙｅｒｓ．Ｔｈｅ ａｔｔｒｉｂｕｔｅｓ ｗｅｒｅ ｆｉｒｓｔｌｙ ｐａｒ唱 ｔｉｔｉｏｎｅｄ ｉｎｔｏ ｃｏｍｐｌｅｔｅ ｐａｒｔｓ ， ｉｎｃｏｍｐｌｅｔｅ ｐａｒｔｓ ａｎｄ ｔｗｏ ｓｕｂ唱ｓｙｓｔｅｍｓ ｗｉｔｈ ｖａｒｉｏｕｓ ｌｅｖｅｌｓ ｗｅｒｅ ｃｒｅａｔｅｄ ａｃｃｏｒｄｉｎｇｌｙ．Ｔｈｅｎ ｔｈｅ ｒｅ唱 ｄｕｃｔｉｏｎ ｗａｓ ｈｉｅｒａｒｃｈｉｃａｌｌｙ ａｐｐｌｉｅｄ ｔｏ ｅａｃｈ ｓｕｂ唱ｓｙｓｔｅｍ．Ｆｉｎａｌｌｙ， ｔｈｅ ｍｅｔｈｏｄ ｗａｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｄｉａｇｎｏｓｉｓ ｓｙｓｔｅｍ ｏｆ ｈｅａｒｔ ｄｉｓ唱 ｅａｓｅ．Ｓｉｍｕｌａｔｉｏｎｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｅｔｈｏｄ ｈａｓ ａ ｓｔｒｏｎｇ ａｐｐｌｉｃａｂｉｌｉｔｙ ａｎｄ ａ ｍｏｒｅ ｒａｐｉｄ ｒｅｄｕｃｔｉｏｎ ｓｐｅｅｄ．Ｔｈｅｒｅｆｏｒｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｍｅｔｈｏｄ ｉｓ ｖｅｒｉｆｉｅｄ． Key words： ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ； ｒｏｕｇｈ ｓｅｔｓ； ｄａｔａ ｍｉｎｉｎｇ； ｈｉｅｒａｒｃｈｉｃａｌ ｒｅｄｕｃｔｉｏｎ 问题的决策或分类规则 0　引言 粗糙集理论作为一种新的处理不确定性知识的数学工具， 越来越受到众多学者的广泛关注。 粗糙集理论的主要思想是 在保持分类能力不变的前提下，通过知识约简，导出所要研究 ［１］。 将粗糙集理论与神经网络、模糊 理论、专家系统、遗传算法和证据理论结合，可广泛应用于模式 识别、机器学习、知识获取、数据挖掘、决策分析和决策支持等 领域。 数据挖掘是知识发现的一个环节。 它是在某种约束条 件下，应用数据分析和数据发现算法，从数据中获取某些特定 模式，目的在于从大量数据中发现那些令人感兴趣的规则。 在 实际问题中不完备信息广泛存在。 经典的粗糙集理论只能处 理完备的信息系统，而对不完备信息系统进行知识约简时，要 先经过预处理使其完备化，然后再进行约简。 这样，可能会使 原始数据和经过数据挖掘而获得的知识存在不同程度的失真， ［２］。 文献［３］ 中提出了一 种分层递阶约简算法，并证明了在信息系统的信息熵、平均知 识粒度和平均知识层次保持不变的情况下，由该算法所得到的 层次和多种粒度上问题的求解。 本文提出一种基于粗糙集理 分层递阶约简可使单层次和单粒度上问题的求解转变为多种 甚至可能使原有数据系统不可挖掘 论的不完备信息系统的数据挖掘方法。 1　不完备信息系统 1畅1　不完备信息系统 定义１　称四元组 S ＝（U，A，V， f） 为信息系统。 其中：U 是对象的非空有限集，称为论域；A 为属性的非空有限集合，Va 为属性 a∈A 值域；V ＝∪ a∈AVa，而 Va 为属性 a 的值域； f：U ×A→ V 是一信息函数，对于给定对象 x， f（x，a）赋予对象 x 在属性 a 下的取值。 如果 A 由属性集合 C 和结论属性 D 组成，C 和 D 满足 C∪D ＝A，C∩D ＝碬，则称 S 为决策系统。 若在 S 中， 愁x∈U，a∈C，a（x） ＝倡，即 a（x） 未赋值时，称该决策系统是 不完备的，a 为不完备属性；否则，称该决策系统是完备的 ［４］。 1畅2　不完备信息系统的常见处理方法 有：删除法；使用全 局常量填充空缺值；使用属性的平均值或常见值填充空缺值； 使用回归法、贝叶斯方法或判定树等方法确定最可能的值，用 来填充空缺值；扩展法，将一个不完备元素扩展成由其不完备 属性上的所有可能取值组合而成的若干元素。 常见的处理不完备信息系统的方法 ［２］ 以上这些方法都不同程度地使原始数据和所获得的知识 收稿日期： ２００６唱１０唱２３； 修回日期： ２００７唱０１唱２３　　基金项目： 国家自然科学基金资助项目（６０５７４０３４） 作者简介：邢化玲（１９８０唱），女，吉林通化人，硕士研究生，主要研究方向为信息融合与控制（ａｌｉｎｇ６５４＠１６３．ｃｏｍ）；刘思伟（１９６２唱），男，山东诸城 人，高级工程师，博士，主要研究方向为惯性大地测量与装备技术；高社生（１９５６唱），男，陕西西安人，中国惯导技术学会会员，美国数学评论（Ａｍｅｒｉ唱 ｃａｎ Ｒｅｖｉｅｗ） 特邀评委，教授，主要研究方向为导航、制导与控制、信息融合与控制；唐士杰（１９８０唱），女，广西桂林人，硕士研究生，主要研究方向为信 息融合与控制． 

邢化玲，等：不完备信息系统的数据挖掘方法研究 第 １ 期 失真，并且未考虑实际问题中属性获取的实时性、难易程度和 成本代价等，从而影响最终决策的实用性。 针对这些不完备处 理方法的不足，本文从原始数据出发，直接在不完备信息系统 上进行数据挖掘，以求得最接近原始数据的规则。 2　粗糙集及其扩展 2畅1　粗糙集题 定义 ２　对于信息系统 S ＝（U，A，V， f），设 P彻A，称二元 等价关系 ＩＮＤ（P） ＝｛（x，y）｜（x，y）∈U ×U 且橙a∈P 有 f（x， a） ＝f（y，a）｝为由属性集 P 导出的不可分辨关系。 定义３　对于信息系统 S，设 B彻A，X彻U，称 BX ＝｛x∈U｜ ［x］ＩＮＤ（B）彻X｝，BX ＝｛x彻U｜［x］ＩＮＤ（B）∩X≠碬｝ 分别为 X 的 B 下近似集和 B 上近似集。 ＰＯＳB（X） ＝BX，ＮＥＧB（X） ＝U －BX， ＢＮB（X） ＝BX －BX 分别为 X 在 B 下的正域、负域和边界。 2畅2　扩展的粗糙集 通常，以不可分辨关系为基础的经典粗糙集理论无法直接 处理不完备信息系统的信息。 相似模型是经典粗糙集模型的 扩展，用相似关系代替了不可分辨关系，可以处理不完备信息 系统。 定义 ４　对于不完备信息系统，设 B彻A，称 ＳＩＭ（B） ＝ ｛（x，y）∈U ×U｜橙a∈B，a（x） ＝a（y） ｏｒ a（x） ＝倡 ｏｒ a（y） ＝ 倡｝为由属性集 B 导出的相似关系。 令 SB（x）表示对象集｛y∈ U｜（x，y）∈ＳＩＭ（B）｝，对 B 而言，SB（x）是与 x 可能不可区分的 对象的最大集合。 定义５　设 B彻A，X彻U，称 BX ＝｛x∈U｜SB（x）彻X｝ 和 BX ＝｛x∈U｜SB（x）∩X≠碬｝分别为 X 在 B 下的正域、负域 ［４］。 3　不完备信息系统的数据挖掘方法 通常对于不完备的信息系统，在数据挖掘前首先按照某种 方法将不完备的数据完备化；然后对完备化后的信息系统进行 数据挖掘。 但是，相对于原始数据来讲，这种做法将会使完备 化后的数据失真，引进噪声，从而使获取的知识或规则不可用。 考虑到实际问题中获取属性的难易程度、实时性和成本等要 求，遵循分层递阶的原则，利用那些容易采集的数据在本层次 上进行数据挖掘获取所需的知识。 如果得不到所需知识，就进 一步深入观察，在下一个层次上获取知识。 这样就可以在不同 的层次上观察和分析同一问题，利用已有的知识逐步缩小问题 求解的范围，直到得到最终结果。 3畅1　数据挖掘过程 数据挖掘方法的思路是：首先，从原始数据出发将属性分 为完备层和不完备层，让不完备属性出现在较深层次上；然后， 利用完备层属性建立首层决策子系统，给定目标规则的置信 度，应用经典的粗糙集理论对其进行知识约简得到满足置信度 要求的规则；最后，根据首层的约简情况，利用不完备层属性建 立次层决策子系统，应用扩展的粗糙集理论对其进行规则推 导。 同时，在每个子系统中，利用粗糙集得到的规则构建模糊 神经网络，以增强系统的决策能力和推广能力。 数据挖掘的步骤如下： ［５］ 方法 ·１９· 　　　 ａ）数据准备。 从原始数据出发，确定条件属性和结论属 性集合，选择各属性的值域。 将原始数据表示成适合粗糙集处 理的二维决策表形式，并将连续条件属性按属性重要性离散化 进行离散化，得到决策系统，记做（U，C∪｛d｝）。 ｂ）属性分层。 将属性分为完备属性层 C１ 和不完备属性 层 C２，并且 C１∪C２ ＝C，C１∩C２ ＝碬。 ｃ）首层决策系统。 以条件属性 C１ 和决策属性 d 构成首层 决策系统，并对其进行知识约简，得到 n 组规则。 计算各条规 则的置信度，确定置信度阈值 r 和规则支持数阈值 m。 放弃置 信度小于 r 且支持数小于 m 的规则，得到置信度等于１ 的确定 性规则和置信度大于等于 r 且小于１ 的不确定性规则，记为 n１ 组规则。 利用这 n１ 组规则构建模糊神经网络，对首层决策系 统（U１，C１∪｛d｝）进行决策分析。 ｄ）次层决策系统。 以条件属性 C２ 和决策属性构 d 成层次 决策系统（U２，C２∪｛d｝）。 其中：U１∪U２ ＝U；U１∩U２ ＝碬。 利 约简，得到带有置信度的规则，并构建模糊神经网络，对其进行 决策分析。 3畅2　首层决策系统的约简算法 的分辨矩阵。 其元素定义为 定义６　对于决策系统 S ＝（U，C∪｛d｝），称（m倡 ij ＝ ｛a｜a∈C 且 f（xi，a）≠f（xj，a）｝　（xi，xj）臭ＩＮＤ（d） m倡 （xi，xj）∈ＩＮＤ（d） ij ｝为决策系统的分辨函数。 其中：∨m倡 用扩展的粗糙集理论中的相似模型对次层决策系统进行知识 ij ） n ×n 为 S ij 表示 碬 ij 表示合取运算 化为析取范式，则每个子式所包含的条件 称 ρ倡 ＝∧｛∨m倡 ij 所有属性的析取运算；∧m倡 m倡 将分辨函数 ρ倡 属性构成一个约简。 3畅3　次层决策系统约简的计算 定义７　对于不完备决策系统 S ＝（U，C∪｛d｝），B彻C，称 矪B（x） ＝｛i｜i ＝d（y），y∈SB（x）｝ 为决策系统的广义决策函数。 设 αB（x，y） 是满足（x，y）臭ＳＩＭ（｛a｝） 的 a∈B 的集合，则称 （x，y）∈U ×｛z∈U｜d（z）臭矪C（x）｝αC（x，y）为 S 的区分函数。 Δ倡 ＝ 将区分函数转换为析取范式，则每个子式所包含的条件属 性构成一个约简。 3畅4　模糊神经网络的构造 粗糙集作为一种数据挖掘方法，在特征提取和消除冗余数 据方面具有显著功效。 但是由于粗糙集方法不具备推广性，将 其与模糊神经网络相结合来增强系统的泛化能力和决策精度。 ａ）对原始数据进行离散化得到初始的决策表，并求出各离散 值对应的隶属函数；ｂ）对离散化的决策表进行属性约简，获取 最简决策规则；ｃ） 以所得的决策规则为模糊推理系统的模糊 规则，构建模糊神经网络。 根据以上思路，模糊神经网络共由 以下五层组成。 网络结构如图１ 所示。 ａ）输入层。 节点数与条件属性数目同为 m；输入变量是精 确的条件属性值。 I１ ｂ）模糊化层。 对每个输入变量 xi 离散化为 ri 个不同的离 散值。 该层的神经元作用函数为各离散值对应的模糊隶属函 数： I２ kik ＝O１ kik］（k ＝１，２，…， k，O２ kik ＝uikk ＝ｅｘｐ［ －（I２ k（k ＝１，２，…，m）。 kik －akik）２ ／σ２ k ＝xk，O１ ［６］。 朝钞 k ＝I１ 

计 算 机 应 用 研 究 第 ２５ 卷 数据挖掘方法，其误差曲线如图 ４ 所示。 误差只能收敛到 ０畅０１。 0.9 0.7 0.5 0.3 0.1 0.09 0.07 0.05 0.03 0.01 j ＝I３ mim，O３ １i１ ×O２ j ＝αj ＝O２ ２i２ ×… ×O２ ·２９· m；ik ＝（１，２，…，rk）。 ｃ）规则层。 每一个节点代表一条规则。 若 ｂ） 神经元对应 的离散值是某条规则的规则前件，则该神经元与相应规则层神 经元的连接权值为１；否则为０。 该层的作用函数为该条规则 j （j ＝１，２，…， 的适用度：I３ p）。 ｄ）结论层。 节点数与决策属性的类型数 n 相同。 ｃ）神经 元与该层中代表相应结论的神经元相连，表示该规则推出某条 结论。 I４ l ＝钞 l （l ＝１，２，…，n）。 其中：wjl 表示规 j O３ 则的置信度，初值选为相应规则的置信度。 ｛ ｜［xk］ Ri∩Dk ｜／ 决策规则的置信度公式为 μ（xk） ＝ｍｉｎi ｜［xk］Ri｜｝。其中：xk 代表第 k 条规则；Dk 代表第 k 条规则的决 策属性类；Ri 代表针对该规则的第 i 个条件属性所作的分类。 ｅ）输出层。 节点数与决策属性个数相同。 该层表示去模 糊化。 I５ ＝钞 l O４ ，wjl。 误 采用梯度最速下降法来修正网络的参数 akik 差函数为 E ＝钞 l ×bl／（钞 l O４ （ti －yi）２ ／２。 l），O５ ＝I５。 j ×wjl，O４ ，σkik l ＝I４ i x1 x2 xm ur1 1 ur1 1 ur1 m m 琢1 琢2 琢p w11w21 win wpn b1 bn O5 输入层 模糊化层 规则层 结论层 输出层 图 1 网络的拓扑结构 从 ＵＣＩ 机器学习数据库 4　仿真实验 ［７］ ｈｅａｒｔ唱ｄｉｓｅａｓｅ 中选择不完备的 Ｓｗｉｔｚｅｒｌａｎｄ 数据库，验证本文所提出的数据挖掘方法的有效 性。 其中：条件属性１３ 个，结论属性１ 个，取值为１ 和２，代表 是否患有心脏病。 由于属性５ 的取值只有 ０，将属性 ５ 去掉。 软件将原始数据库按 ８０％和 ２０％的比例分 利用 ＲＯＳＥＴＴＡ［８］ 成两个：一个作为训练集；另一个作为测试集。 对于训练集，用 属性重要性离散化方法将连续条件属性１、４、７ 和９ 进行离散 化。 结果属性１ 和７ 被约掉，属性 ４ 有（１０７．５，１２７．５，１５２．５） 三个断点；属性９ 有（１．３５）一个断点。 根据本文提出的方法，首先将条件属性分为两层。 首层包 括完备属性２、３、６ 和８；次层包括不完备属性４、５、９、１０、１１ 和 １２。 对于首层决策子系统，取置信度阈值为０．７５，支持度阈值 为２，通过约简，得到九条规则。 对应的模糊神经网络输入为 条件属性２、３、６ 和 ８，规则层节点数目为九个，三层和四层之 间连接权值的初始值为规则的置信度，即［１，１，１，１，１，１，１， ０畅８，０畅７５］。 对于次层决策子系统，取置信度阈值为 ０．６，经过 约简，属性５、１０ 和１２ 被约掉，得到七条规则，则网络的输入为 条件属性４、９ 和１０，第三层节点数目为七个，三层和四层之间 连接权值的初始值为［１，１，１，１，１，０．７５，０．６５］。 两个子网络的 学习速率都取０．００５，α＝０畅１。 首层决策子系统的学习误差曲 线如图２ 所示；次层决策子系统的学习误差曲线如图３ 所示。 误差都收敛到０．００５。 先将不完整数据进行完备化后再进行 0.16 0.12 0.08 0.04 0 50 200 100 250 100 150 训练次数/步 300 训练次数/步 200 0 图 2 网络 1 的误差曲线 400 图 3 网络 2 的误差曲线 下面对网络进行测试，测试样本为 ２５ 组。 首层网络识别 出２０ 组样本，将剩下的５ 组样本输入次层网络，有２ 组样本得 到识别，所以整个系统的误判率为１２％。 从表１ 可以看出，本 方法比将不完整的数据完备化处理后再进行数据挖掘的方法， 在决策精度上得到了提高。 本方法不但提高了系统的决策精 度，而且减小了网络规模加快了网络的收敛速度。 表 1 比较结果 设计方法 网络规模 训练 误差 训练 次数 本文方法 4 11 9 2 10.005 3 9 7 2 1 0.005 完备化方法7 24 34 2 10.01 240 400 700 误判 率/% 12 16 0 400 200 800 图4 完备化方法的误差曲线 训练次数/步 600 5　结束语 由于数据采集过程受实时性、难易程度及成本等因素的限 制，在现实生活中，不完备信息系统广泛存在。 传统的处理不 完备信息系统的方法，不同程度地使挖掘到的知识失真于原始 数据。 为此，本文提出了直接在不完备信息系统上进行数据挖 掘的方法。 该方法从实际应用出发，遵循分层递阶的原则，先 在完备属性层上进行数据挖掘。 如果得到的结论不满意， 就 进一步在不完备属性层上进行挖掘；这样可用较小的代价在较 浅层次上得到问题的求解。 在知识推理过程中，将粗糙集和模 糊神经网络相结合，增强了系统的泛化和容错能力，从而提高 了决策精度。 参考文献： ［１］ ＰＡＷＬＡＫ Ｚ．Ｒｏｕｇｈ ｓｅｔｓ［Ｊ］．Communications of ACM，１９９５，38 ［２］ 胡旺，冯伟森，李志蜀，等．基于粗糙集理论不完备信息系统的数 （１１）： ８９唱９５． 据挖掘［Ｊ］．四川大学学报，２００４，41（４）：７４４唱７４８． 理论基础［Ｊ］．控制理论与应用，２００４，21（２）：１９５唱１９９． 出版社，２００１． ［３］ 乔斌，李玉榕，蒋静坪．粗糙集理论的分层递阶约简算法及其信息 ［４］ 张文修，吴伟业，梁吉业，等．粗糙集理论与方法［Ｍ］．北京：科学 ［５］ 侯利娟，王国胤，聂能，等．粗糙集理论中的离散化问题［Ｊ］．计算 ［６］ 李雄飞，李军．数据挖掘与知识发现［Ｍ］．北京：高等教育出版社． ［７］ ＤＵＮＴＳＣＨ Ｉ，ＧＥＤＩＧＡ Ｇ．Ｕｎｃｅｒｔａｉｎｔｙ ｍｅａｓｕｒｅｓ ｏｆ ｒｏｕｇｈ ｓｅｔ ｐｒｅｄｉｃ唱 ［８］ ＯＨＭ Ａ．ＲＯＳＥＴＴＡ ｔｅｃｈｎｉｃａｌ ｒｅｆｅｒｅｎｃｅ ｍａｎｕａｌ［Ｄ］．［Ｓ．ｌ．］：Ｎｏｒｗｅ唱 机科学，２０００，27（１２）：８９唱９４． ２００３． ｔｉｏｎ［Ｊ］．Artificial Intelligence，１９９８，106（１）： １０９唱１３７． ｇｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，１９９９．