不完备信息系统（通用7篇）
不完备信息系统 篇1
1引言
粗糙集理论[1]是波兰数学家Z.Pawlak教授提出来的一种新型的处理模糊和不确定性知识的数学工具, 并在决策分析, 模式识别及数据挖掘等领域取得了很大的成功[1,2,3,4]。经典粗糙集模型的局限性是它所处理的分类必须是完全正确的或肯定的, 即严格按照等价类来分类的, 而在现实中, 由于数据采集能力有限、测量误差等原因, 往往得到的系统是不完备的, 即存在对象属性值是未知的。所以Ziarko提出可变精度粗糙集模型 (VPRSM) [5], 允许上近似和下近似存在一定的分类误差, 它的多数包含关系的引入, 增强了模型的容噪能力。 文献[6]利用集对分析方法, 提出了不完备信息系统中基于集对分析的变精度粗糙集模型。本文的属性约简算法是在该模型的基础上进行分析和研究的。
属性约简是Rough集理论的核心内容之一, 其目的是导出相关决策表的决策规则, 而约简后的属性能否表达与原属性集完全一致的信息直接影响着决策规则的性能和效率。针对完备信息系统及不完备信息系统文献[7]和文献[6]提出的属性重要性算子都是面向对象集U进行计算, 而未考虑正域变化对决策属性各个等价类的影响, 因此本文定义了一个新的属性重要性的算子, 并由此给出了基于不完备信息系统的一种属性约简的启发式算法。算法可从相似度α、包含度β和约简终止精度δ三个方面进行调节, 因此它在提高属性约简的准确性的基础上, 增加了灵活性。并且它将文献[8]的直接求核的方法扩展到不完备信息系统中, 以核属性为起点, 从条件属性中逐个加入属性重要性算子大的属性, 从而得到一个满足要求的近似约简。同时, 它也是完备信息系统的属性约简算法的推广。当α=1, β=0, δ=1时, 本算法可以得到完备信息系统的一个属性约简。
2在不完备信息系统里基于集对分析的变精度粗糙集模型
集对分析方法的核心思想是把被研究的客观事物的确定性联系和不确定性联系作为一个系统来处理。
定义1[6] :设 (U, A∪{d}) 是不完备信息系统, U是对象的非空有限集, A= {a1, a2, ……, ak}是条件属性集, ak是某一条件属性, d是决策属性, D⊆A∪{d}, 阀值α的取值范围是0≤α≤1, 定义x关于D的α领域为:
Sundefined (x) ={y∈U|UD (x, y) =a+bi+cj, 且a+b≥α }
这里undefined, undefined, undefined
(1) s={a∈D|a (x) =a (y) ∧a (x) ≠*∧a (y) ≠*} (x和y是在D下取值都明确且相等的属性集)
(2) f={a∈D|a (x) =*∨a (y) =*} (x和y是在D下取值都不明确的属性集)
(3) p={a∈D|a (x) ≠a (y) ∧a (x) ≠*∧a (y) ≠*}
(x和y是在D下取值都明确但不等的属性集)
定义2[9]:设 (U, A∪{d}) 是一个不完备信息系统, 对于X⊆U, D⊆{d}, α>0, 包含度β∈ (0.5, 1], 则任一决策等价类Dj∈U/D (j=1, 2, …, |U/D|) 关于A的β包含度α领域的集对型下近似、上近似分别定义为:
undefined
undefined
定义3: 设 (U, A∪{d}) 是一个不完备信息系统, 对于X⊆U, C⊆A, D⊆{d}, α>0, 包含度β∈ (0.5, 1], 则Dj∈U/D (j=1, 2, …, |U/D|) 关于A的β包含度α领域的集对型正域定义为:undefined。
3在不完备信息系统里基于集对变精度粗糙集模型的属性约简算法
3.1决策表属性重要度的定义
例1:设 (U, A∪{d}) 是一个不完备信息系统, 其中U是对象集, C是条件属性集, D⊆{d}是决策属性。Dj∈U/D (j=1, 2, …, |U/D|) 是对象集U相对于决策属性D形成的决策等价类。|Dj|表示Dj等价类的元素个数。设决策类一共分为D1和D2两类, 其中|D1|=1000, |D2|=50。POSC (D) 表示决策属性D相对条件属性集C下的正域。
(1) 当|POSC (D1) -POSC-{a} (D1) |=19, |POSC (D2) -POSC-{a} (D2) |=1时, |POSC (D) -POSC-{a} (D) |=20, 根据文献[7]中属性重要性的定义得属性a的重要性为 (19+1) /1050=0.019。
(2) 当|POSC (D1) -POSC-{b} (D1) |=1, |POSC (D2) -POSC-{a} (D2) |=18时, |POSC (D) -POSC-{b} (D) |=19, 同样根据文献[7]中属性重要性的定义得属性b的重要性为 (1+18) /1050=0.018。
从 (1) 计算中得到当去掉属性a时, 对于决策类D1其正域有19个元素发生了变化, 19/|D1|=19/1000=0.019, 约简前后正域中有1.9%的元素发生了变化, 即对于决策类D1仅有1.9%的对象不能正确地体现原信息系统的基本特征。从 (2) 计算中得到当去掉属性b时, 对于决策类D2其正域有18个元素发生了变化, 18/|D2|=18/50=0.36, 但是约简前后正域中有36%的元素发生了变化, 即对于决策类D2有36%的对象不能正确地体现原信息系统的基本特征。通过上面的分析可以知道去掉属性b后比去掉属性a后对正域的影响要大, 所以属性b比属性a重要。但是根据文献[7]中提到的属性重要性算子进行计算, 属性a比属性b重要, 这与上面分析结果属性b比属性a重要不符。造成这种结果的原因是由于文献中[6]的属性重要性算子是面向对象集U而不是面向决策属性的各个等价类进行计算。依据上面的分析, 所以本文提出了一个新的属性重要性的定义。
定义4:设 (U, A∪{d}) 是一个不完备信息系统, 对于X⊆U, B⊆C⊆A, D⊆{d}, Dj∈U/D (j=1, 2, …, |U/D|) , α>0, 包含度β∈ (0.5, 1], 条件属性子集B相对于决策属性集D的β包含度α领域的重要性定义为:
undefined
当B={a}时, 条件属性a∈A关于{d}的β包含度α领域的重要性为
undefined
注: (1) 属性重要性算子θ (C, B, D) undefined是用来描述条件属性集C中属性集B相对于决策属性D的重要性。
(2) 设A、B为任意两个集合, A和B的对称差为集合S, 其元素或属于A, 或属于B, 但不能既属于A又属于B, 记做A⊕B。undefined。定义4中的⊕是用来求不属于约简前正域和约简后正域交集的元素。由于本文所进行的属性约简是基于集对变精度粗糙集模型的, 所以随着属性的减少, 约简后正域与原正域之间没有包含关系, 所以定义4采用了对称差。
(3) 当分母相应决策类个数|Dj|越小, 分子正域变化元素个数|POSundefined (C, D, β) ⊕POSundefined (C-B, D, β) |越大的时候, 它们的比就越大, 其对相应决策类正域的影响越大, 反之亦然。算子θ (C, B, D) undefined是各个决策类所求比值的和, 所以该算子可以作为衡量属性重要性的标准。
(4) 若去掉条件属性子集B所引起的分类变化越大, 则属性重要性算子θ的值越大, 说明B对决策越重要。
将定义4应用到例1中得:θ (C, a, d) undefined=19/1000+1/50=0.039;θ (C, b, d) undefined=1/1000+18/50=0.361。因为0.361>0.039, 所以属性b比属性a重要。
3.2属性约简的启发式算法
定义5:[9]给定决策信息系统S= (U, C∪D, β) , C是条件属性集, D是决策属性集, U关于C的分类为U/C={C1, C2, …, C|U/C|}, U关于D的分类为U/D={D1, D2, …, D|U/D|}。条件属性集C关于决策属性集D的βundefined约简定义为C的最小属性子集RED (C, D, βundefined) , 且满足:
(1) POS (C, D, βundefined) =POS (RED (C, D, βundefined) , D, βundefined) ) 且对∀Dj∈U/D均有
(0≤δ≤1) ;
(2) 从Red中去掉任何一个属性, (1) 不成立。
其中:δ为约简终止精度。
定义5:是属性约简定义, 主要是用来定义属性的约简结束条件的。本文将定义5应用到了属性约简算法中去。
现在给出基于集对变精度粗糙集模型的属性约简的启发式算法, 设S= (U, C∪D, β) 是一个不完备信息系统, 算法是以相对核为起点, 从条件属性中逐个加入属性重要性算子大的属性, 如此反复, 直到求出一个C关于D的β包含度α领域近似约简Red为止。
算法:求条件属性C关于D的β包含度α领域近似约简Red
输入:一个不完备决策信息系统S= (U, C∪D, β) ;相似度α;包含度β;约简终止精度δ。
输出:C关于D的β包含度α相似度δ约简终止精度的一个近似约减。
步骤1 令核属性集coreD (C) =Φ, 属性重要性集合E=Φ, 计算U在不可分辨关系ind (D) 下的划分undefined。
步骤2对每个x∈U, 计算x关于C的α领域Sundefined (x) , 再计算C关于D的β包含度α领域的集对型下近似undefined及正域POSundefined (C, D, β) 。
步骤3对每个a∈C, 计算每个x∈U关于C-{a}的α领域Sundefined (x) {d}, 再计算C-{a}关于{d}的β包含度α领域的集对型下近undefined。如果对undefined均有 (0≤δ≤1) , 则转3.1, 否则转3.2。
步骤3.1 令E = E∪{a}, 利用属性重要性定义θ (C, a, D) undefined计算属性a的重要性, 并依据计算出的属性重要性对集合E中元素进行排序。转3.3。
步骤3.2 令coreD (C) =coreD (C) ∪{a}, 最后得到的coreD (C) 为C相对于D的相对核。
步骤3.3 如果每个a∈C的属性都计算过, 则转4, 否则转3。
步骤4 令Red=coreD (C) , 在E中选择属性重要性最大的属性b加如到Red中, 即Red=Red∪b, 如果对undefined均有 (0≤δ≤1) , 则输出约简Red, 否则重复执行步骤4, 直到得到满足条件的约简。
注:在步骤3中当不满足定义5的约简定义时则转步骤3.2, 进行属性核的计算, 即对文献[8]的信息系统决策表相对核计算方法的推广。本文将文献的约简终止条件应用到了属性核的计算中, 并且由于约简终止条件中变量的引入使本文属性核的计算在保证准确性的同时, 更加具有灵活性。该求属性核的计算不仅适用于完备信息系统, 同时也适用于不完备信息系统。
3.3算法分析
算法性能分析:设有n个对象, 算法第一步的时间耗费是O (n) , 算法第二步和第四步的最坏时间复杂度为O (n2) , 算法第三步的最坏时间复杂度为O (|C|n2) 。
属性约简算法常常涉及的数据量非常大, 因此算法的时间开销和空间开销也非常大。所以算法的时间复杂度应尽量控制在多项式范围内, 而且次数越低越好。本论文提出的算法时间复杂度大约是O (n+|C|n2) , 依然在多项式范围内, 是可以接受的。
该算法可以通过对相似度α、包含度β和约简终止精度δ三个变量的调节, 得到具有不同侧重度的约简, 因此该算法增强了约简的灵活性。同时新的属性重要性定义的引入使该算法具有更高的准确度。.
4实例分析
为考察本算法的有效性, 下面用一个不完备信息系统来分析。
设 (U, C∪{d}) 是一个不完备信息系统, 其中对象集U={x1, x2, ..., x12}, 条件属性集C={a1, a2, a3, a4}, d是决策属性, 决策表如表1。
利用本文提出的属性约简算法进行约简。当相似度 α=0.8, 精度 β=0.65 , 约简终止精度δ=0.9时, 相对核属性为{a2, a4}, 得到一个近似属性约简结果为{a2, a3, a4}。由于本算法的终止条件采用的是文献[9]的定义, 且该定义是相对于各个决策类的正域进行定义, 所以该定义比文献[6]中的约简定义更加地苛刻。所以本约简后的属性个数比文献[6]得到的约简个数多, 因此得到的约简的也越能体现原决策信息系统的特征。
5结束语
本文在集对变精度粗糙集模型的基础上, 提出了基于β包含度α领域的属性重要性算子, 以及将直接求核算法与约简定义相结合的属性核的计算, 并由此给出了基于不完备信息系统的一种属性约简的启发式算法。该算法以核属性为起点, 从条件属性中逐个加入属性重要性算子大的属性, 从而得到一个满足要求的近似约简。算法在保证属性约简的准确性的基础上, 增加了灵活性。本文的属性重要性算子虽然是在集对分析的变精度粗糙集模型基础上提出的, 但是它也同样适用于许多别的粗糙集及粗糙集扩展模型。
参考文献
[1] Pawlak Z.Rough sets.International Journal of Computerand Information Science, 1982, 11 (5) :341~356
[2]苗夺谦, 胡贵荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36 (6) :681~684
[3]张文修, 吴伟志, 梁吉业等.粗糙集理论与方法.北京:科学出版社, 2001.
[4]王国胤.Rough集理论在不完备信息系统中的扩充.计算机研究与发展, 2002, 39 (10) :1238~1248
[5] Ziarko W.Variable precision rough set model.Journal of Computer and System Sciences, 1993, 46 (1) :39~59
[6]刘富春.变精度集对粗糙集模型中的属性约简.计算机工程与应用, 2006, (05) :8~18
[7]何明, 冯博琴等.一种基于Rough集理论的属性约简启发式算法.小型微型计算机系统, 2005, (26) :356~359
[8]张腾飞, 肖健梅, 王锡淮.粗糙集理论中属性相对约简算法.电子学报, 2005, 33 (11) :2080~2084
[9]龚安, 王琳, 牛秋丽.在不完备信息系统中基于VPRSM的约简异常分析.计算机工程与应用, 2008, 44 (24) :165~167
不完备信息系统 篇2
波兰数学家Pawlak提出的粗糙集理论 (RSA) [1,2]是一种处理不确定、不精确、不完备问题和模糊信息的数学工具。经过近三十几年的飞速发展, 粗糙集理论已成功应用到图像识别、数据处理、智能模拟、数据的决策与分析等众多领域。
经典粗糙集理论是基于不可区分关系对属性进行分类, 但是在实际背景下, 属性值大小体现对象关于属性之间的优劣关系, 这是经典粗糙集模型中等价关系所不能体现的, 为处理序信息系统中的知识发现问题, Greco等将经典粗糙集理论加以推广, 提出了基于优势关系的粗糙集方法 (DRSA) [3,4]。为解决从大量杂乱无章的、强干扰的数据中发现潜在的、有价值的、简洁的信息, 优化决策规则获取这一研究方向吸引了不少学者的关注。谢军等在文献[5]中提出了二种描述子的概念, 基于描述子讨论了优化决策规则的获取问题;邵明文和张文修在文献[6]中提出了一种扩展优势关系粗糙集模型, 进而利用该模型讨论了不完备协调序信息系统的决策规则获取问题;杨习贝等在不完备序信息系统中提出了相似优势关系, 而后利用相似优势关系定义了相应的知识约简以获取优化决策规则;并给出了最优可信决策规则的获取方法;杨习贝等在文献[8]给出了不完备区间值序决策信息系统获取优化规则的一种方法, 他们利用完备序信息系统的结论, 将不完备问题完备化, 进而给出了六种不同形式的约简, 讨论了这几种约简之间的关系, 并构造六种区分函数来计算相应的约简, 以获取优化的决策规则;姜洪冰等在文献[9]中利用正则元构造了相容支配集, 并基于此给出了不完备序决策信息系统的可信决策规则获取的方法;
目前对于优势关系粗糙集的研究, 都是以支配集或者被支配集作为基本知识颗粒, 来定义关系决策类的上并 (下并) 的下、上近似, 进而导出“at most”决策规则或者“at most”决策规则。然而, 在实际问题当中, 往往需要导出类似“at most and at most”的区间决策规则, 为解决此类问题, 管延勇, 王洪凯等利用支配集和被支配集的交来作为基本知识颗粒, 提出了区间知识颗粒的概念, 研究了序信息系统的极小决策规则获取问题。本文针对不完备序信息系统, 结合区间知识颗粒, 提出了I-区间约简的概念, 利用布尔推理理论, 给出了计算I-区间约简的区分函数, 提供了获取不完备序信息系统的区间决策规则的方法。
2 基本概念
定义2.4[3,4]在序决策信息系统S中, 由B哿C所确定的优势关系记为
定义2.6[10]在序决策信息系统S中, 由B哿C确定的区间知识颗粒记为
3 优化决策规则获取及其区分函数求法
所谓决策规则约简, 就是在保证得到相同的决策结论的前提下, 亦即在保证决策规则的确定性程度不变的前提下, 使其条件属性描述更加简洁, 找出对决策结论是必要的条件属性.为此, 下面我们给出决策规则的简化以及最优决策规则的概念。
基于定义3.2和定理3.1, 结合布尔推理技术, 可以得到下面的命题3.1。
例3.1.求表1所示不完备序决策信息系统的优化的区间决策规则
类似上面的计算方法, 可以由相应的区间颗粒得到所有优化的区间决策规则。
4 结论
利用管延勇等提出的区间知识颗粒的概念, 研究了在不完备序信息系统的优化决策规则获取问题。通过区间知识颗粒的引入, 导出了区间决策规则。然后给出定义相应的判定定理及区分函数, 来获取优化的决策规则, 使我们能从数学理论方面, 从决策规则简化的直观角度, 对不完备序决策信息系统的知识有了一个清楚的认识。
参考文献
[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science.1982, 11:341-356.
[2]Pawlak Z.Rough sets:Theoretical aspects of reasoning about data[M].London:K.A.P, 1991.
[3]S.Greco, B.Matarazzo, R.Slowinski.Rough sets theory for multicriteria decision analysis[J].European Journal of Operational Research, 2001, 129:1-47.
[4]S.Greco, B.Matarazzo, R.Slowinski.Rough approximation by dominance relation[J].International Journal of Intelligent Systems, 2002, 17:153-171.
[5]谢军, 杨习贝, 孙怀江等.序值决策系统中基于描述子的可信规则获取[J].系统工程理论与实践, 2009, 29 (7) :105-112.
不完备信息系统 篇3
属性约简是知识发现的基础, 也是Rough集理论的核心内容之一。众所周知, 知识库中描述知识的属性并不是同等重要的, 甚至其中某些属性是冗余的。属性约简是在保证信息系统分类或决策能力不变的条件下, 删除条件属性中的冗余属性。粗糙集中的知识约简研究大部分集中在完备信息系统上, 对于不完备信息系统, 一般需要对经典粗糙集理论进行必要的扩展[3]。目前, 许多学者对于不完备信息系统的知识约简作了深入的研究, 并取得了很多成果[3,4,5]。但是这些研究都是考虑属性值为单个值的情况, 而没有考虑取多个值的情况。
主要考虑对于对象在每个属性下具有一个或多个属性值, 即在属性取值为集合的情况下的集值不完备信息系统, 将不完备信息系统作了相应的拓展, 分析了集值不完备信息系统上的半半序这种二元关系, 定义了基于这种二元关系的Rough近似集合;同时也定义了基于这种二元关系的可辨识属性矩阵, 讨论了系统的属性约简问题, 给出属性约简判定定理。最后给出具体的实例, 以解释和说明文章的主要结论。
1 不完备信息系统与集值信息系统
1.1 不完备信息系统
定义1[6] 设S= (U, A, V, F) 为一信息系统, 其中U是对象的非空集合;A=C∪D, C∩D=∅, C是条件属性, D是决策属性集;undefined表示属性a的值域;F={fa|a∈A}它为每个对象在属性a上指定一个属性值, 即对∀x∈U, fa (x) ∈Va。若存在一个对象x∈U, a∈A, 有fa (x) 的值未知 (记作fa (x) =*) , 则称信息系统是不完备的;否则称信息系统是完备的。
1.2 集值信息系统
定义2[7] 称S= (U, A, V, F) 为集值信息系统, 其中U为对象集;A为属性集;undefined表示属性a的值域;F={fa|a∈A}为对象属性值映射, 其中集值映射fa:U→P (Va) (a∈A) , P (Va) 表示Va的非空子集的全体, 即∀x∈U, fa (x) ⊆Va。
1.3 集值不完备信息系统
对于不完备信息系统, 其中某些对象的属性值是未知的 (不知道取何值) 或部分已知的 (如肯定不取某值) 。对于完全不知道的情形, 称这种属性值为空值。空值一般有三种情形[8]: (1) 不存在型空值。即无法填入的值, 或称对象在该属性上无法取值。 (2) 存在型空值。即对象在该属性上的取值是存在的, 但是暂时无法知道。 (3) 占位型空值。即无法确定是不存在型空值还是存在型空值。
对于存在型空值, 为讨论问题的方便, 同时也不失一般性, 我们往往将其可能取值的全体 (即该属性的值域) 作为该对象的属性取值, 即本质上将* 看作一个全集合值。对于属性取值部分知道的情况, 即肯定不取某值, 则它有可能取该属性值域中的其他值中任何一个, 因此我们可以用这些值关于该属性值域的补集作为该对象的属性取值。在此基础
上, 如果我们将属性的单个取值统一看作单元素集合的取值, 我们可以将不完备信息系统作为一类特殊的集值信息系统来看待。
下面我们基于属性集值, 给出集值不完备信息系统的定义。
定义3 设S= (U, A, V, F) 为一信息系统, 其中U={x1, x2, …, xn}是对象的非空集合;A=C∪D, C∩D=∅, C={a1, a2, …, an}是条件属性, D={d}是决策属性集;Va表示属性a的值域;F={fa|a∈A}为对象属性值映射, 其中fa:U→P (Va ) (a∈A) , P (Va) 表示Va的非空子集的全体。如果至少有一个属性a∈C, 使得fa (x) =Va或fa (x) =V′ (V′⊂Va) , 则称信息系统是集值不完备信息系统。若fa (x) =Va, 则表示对象x关于属性a的值是缺省的或遗漏的;若fa (x) =V′ (V′⊂Va) , 则表示对象x关于属性a的值可能是V′中的任何一个值。对于决策属性 d, 对∀x∈U, fd (x) ∈Vd, 即Vd中不存在集合值。由于专家在信息不完备的情况下也能给出决策, 故假设在决策属性上取值没有遗漏或缺失。
以下的讨论都是基于此集值不完备信息系统的。
1.4 半半序关系
在集值不完备信息系统中, 属性值可以看作集合即集值, 如果考虑属性值集合间的包含关系, 我们可定义论域U上的如下二元关系:
定义4 对于B⊆C, 定义二元关系: RB={ (x, y) ∈U×U|fa (x) ⊆fa (y) , a∈B}
显然RB满足自反性和传递性, 但未必满足对称性和非对称性, 故称RB是由B确定的一个半半序关系[8]。
定义5 对象x在半半序关系RB下的后续关系类[x]B和前继关系类[x]undefined分别定义为:
[x]B={ y∈U| (x, y) ∈RB}
[x]undefined={ y∈U| (y, x) ∈RB}
定义6 对于∀X⊆U, X在关系RB下关于属性集B的下、上近似分别定义为:
undefined
对于半半序关系, 容易证明以下性质:
1) 当B1⊆B2⊆A时, 有RB1⊇RB2⊇RA。
2) 当B1⊆B2⊆A时, [x]B1⊇[x]B2⊇[x]A。
3) {[x]B |x∈U}是U的一个覆盖。
4) 当y∈[x]B时, [y]B⊆[x]B。
2 不完备信息系统的属性约简
定义7[7] 设S= (U, A=C∪D, V, F) 为一信息系统, 若RC⊆RD, 则称信息系统是相容的, 否则是不相容的。对于相容的信息系统, 若存在B⊆C使得RB⊆RD, 且对于任意b∈B, RB-{b}⊈RD, 则称B是不完备信息系统S的一个约简。
为方便问题讨论, 以下我们所讨论的信息系统均是相容的。
定义8 设 (U, A=C∪D, V, F) 为一相容信息系统, B⊆C, 若RB-{a}⊆RD, a∈B, 则称属性a是B中不必要的;否则称a是B中必要的。如果每一个a∈B都是B中必要的, 则称B为独立的;否则B为依赖的。
定义9 设S= (U, A=C∪D, V, F) 为一信息系统, 在半半序关系下, 我们定义系统的可辨识属性矩阵M (S) 为:M (S) ={M (xi, xj) }。
undefined
在上述定义中, 由于决策属性D的取值没有遗漏或缺失, 故由决策属性D确定的关系为等价关系, 在定义中我们用[xi]D、[xj]D分别表对象xi、xj在的等价类, 同时我们记M0={M (xi, xj) |M (xi, xj) ≠∅}。
定理1 设不完备信息系统 (U, A=C∪D, V, F) 是相容的, 可辨识属性矩M, 则有:
(1) B⊆C, 使B∩M (xi, xj) ≠∅ (∀i≠j) 当且仅当RB⊆RD。
(2) RB⊆RD当且仅当对于任意B⊆C, B∩M (xi, xj) =∅, 必有M (xi, xj) ∉M0。
证明: (1) 必要性 对于∀xi∈U, 如果xj∉[xi]D, 则[xi]D≠[xj]D, 从而由B∩M (xi, xj) ≠∅可知, 存在a∈B, 使得a∈M (xi, xj) , 这等价于fa (xi) ∩fa (xj) =∅ (在相容关系下) 或者fa (xi) ⊈fa (xj) 且fa (xj) ⊈fa (xi) (在半半序关系下) , 这说明xj∉[xi]B, 于是[xi]B⊆[xj]D, 即RB⊆RD。
充分性 反之, 若RB⊆RD, 则对于任意的xi∈U, 有[xi]B⊆[xi]D。当xj∉[xi]D时, 由[xi]B⊆[xi]D可得xj∉[xi]B, 从而必存在a∈B使得[xi]a∩[xj]a=∅, 这样就有a∈M (xi, xj) , 即B∩M (xi, xj) ≠∅。
(2) 由 (1) 知RB⊆RD当且仅当对于M (xi, xj) ∈M0, B∩M (xi, xj) ≠∅。则得证。
由上述定理易知, 如果B⊆C是满足B∩M (xi, xj) ≠∅, ∀M (xi, xj) ≠∅的极小子集, 则B是C的相对约简。据此, 我们可得出如下结论:
定理2 (属性约简判定定理) 对于不完备信息系统 (U, A=C∪D, V, F) , B是C的约简, 当且仅当:
(1) ∀M (xi, xj) ∈M0, 有B∩M (xi, xj) ≠∅。
(2) ∀b∈B, 存在M (xi, xj) ∈M0, 使得 (B-{b}) ∩M (xi, xj) =∅。
定义10 设S= (U, A=C∪D, V, F) 为集值不完备信息系统, 对于每个M (xi, xj) ∈M0, 我们用∑M (xi, xj) 表示M (xi, xj) 中属性所对应的变量的析取, 则信息系统S的辨识函数可定义为[9]:
undefined
利用幂等律、吸收律以及分配律和结合律等布尔运算定律, 将Δ化为极小析取范式, 在其极小析取范式中, 每个合取子项就对应属性集合的一个极小约简, 所有合取子项就是全部约简。
3 实例
我们引用文献[9]如表1所列的不完备决策表, 条件属性C={Price, Mileage, Size, Max-peed}, 决策属性为D。为方便起见, 我们用P, M, S, X分别表示属性Price, Mileage, Size, Max-peed。属性P、M、X的值域为{H, L}, 属性S的值域为{F, C}, D的值域为{G, E, P}。
如果将表1 中* 看作一个全集合值, 将属性的单个取值统一看作单元素集合的取值, 我们可把表1所列的不完备信息系统转化为表2 所示的集值信息系统。
对于此集值不完备信息系统, 下面我们半半序关系来处理。
RC={ (1, 1) , (2, 2) , (3, 3) , (4, 4) , (4, 5) , (5, 5) , (6, 6) }
[1]C={1}, [2]C={2}, [3]C={3}, [4]C={4, 5}, [5]C={5}, [6]C={6}
[1]undefined={1}, [2]={2}, [3]={3}, [4]={4}, [5]={4, 5}, [6]-1C={6}
如取X={1, 2, 5, 6}, 则X在相容关系RB下的下近似、上近似为:
undefined
我们运用定义9经计算求得系统的可辨识属性矩阵见表3。
由表3 可知M0={{S, X}, {S}, {X}}
根据属性约简判定定理2, 对于B={S, X}, 显然满足B∩M (xi, xj) ≠∅ (∀ M (xi, xj) ∈M0) ;另外, 对于B中去掉任意一个属性的子集, 都存在相交为空的M (xi, xj) , 故{S, X}为属性集C的一个约简。
利用系统S的可辨识属性函数, 我们可求得系统的所有约简:
Δ= (S∨X) ∧S∧X=S∧X
结果表明, 系统S只有一个约简{S, X}, 这与我们利用属性约简判定定理得出的结果是一致的。
4 总结
知识约简是粗糙理论的重要研究内容, 为适应粗糙集理论在现实中的应用, 人们将经典的等价关系推广到相容关系、相似关系, 甚至一般的二元关系。本文我们首先在不完备信息系统下考虑了属性值存在集值的情况, 将传统的不完备信息系统与集值粗糙集模型相结合, 对不完备信息系统进行了推广。根据属性值集合间的基本关系定义了集值不完备信息系统下的半半序关系, 讨论了系统的属性约简问题。
为建立不同意义下的知识获取系统提供了一定的基础, 同时为不完备信息系统的处理提供了一个新的思路, 使不完备信息系统的应用范围得到了一定的推广, 对不完备系统的知识约简和决策规则提取具有一定的意义。
参考文献
[1]Pawlak Z.Rough sets[J].Internation Journal of Informa-tion and Computer Science, 1982, 11 (5) 341-356.
[2]Pawlak Z.Rough set theory and its applications to data a-nalysis[J].Cybernetics and Systems, 1998, 29 (5) :661-688.
[3]王国胤.Rough集理论与知识发现[M].西安:西安交通大学出版社, 2001.
[4]张宏宇, 梁吉业.不完备信息系统下的变精度粗糙集模型及其知识约简算法[J].计算机科学, 2003, 30 (4) :153-155.
[5]李华雄, 刘盾, 周献中.决策粗糙集模型研究综述[J].重庆邮电大学学报, 2010, 22 (5) :624-630.
[6]Kryszkiewicz M.Rough set approach to incomplete infor-mation systems[J].Information Science, 1998, 11 (2) :39-49.
[7]张文修, 梁怡, 吴伟志.信息系统与知识发现[M].北京:科学出版社, 2003.
[8]吴学谋.从泛系观看世界[M].北京:中国人民大学出版社, 1990.
不完备信息系统 篇4
为了更准确地辨识中医证候, 需要尽可能多地收集患者症状。但由于患者症状描述不清楚、检查仪器精度等原因, 往往会导致患者数据不完备。不完备数据将使辨证规则提取困难、推理产生差异、导致预测准确率降低等问题[1,2]。近年来, 针对临床数据表现出的不完备特性, 国内外学者进行了一些探索性研究, 取得了一定的成果[3,4,5,6,7,8]。
删除法是最简单的数据不完备处理方法[9,10,11,12]。文献[12]通过删除包含不完备症状的样本, 将不完备样本集变换成完整样本集, 进而构造决策树模型;文献[11]利用中西医双视图集成学习, 分别在两个视图通过删除方法处理不完备数据, 再进行诊疗模型的构造。然而, 对于中医证候辨识问题, 删除法将改变系统中数据的分布结构, 造成信息遗漏和数据的浪费, 导致在预测中无法充分利用不完备样本中蕴涵的信息, 特别是在肝硬化中医样本收集难度大的情况下, 直接删除不完备数据难以满足中医辨证的临床应用。
填补法是用一个预估值代替不完备数据, 在一定程度上弥补删除法的不足。文献[13,14,15,16,17]分别利用样本的先验概率密度分布、证据积累、统计分析结果, 以及特征间的互信息预估不完备数据。文献[18,19,20]基于机器学习相关算法填补不完备数据。虽然上述方法可以解决数据不完备的问题, 然而, 从中医患者的症状信息中, 很难获得概率密度和证据函数等先验知识, 使得这些方法在中医证候知识辨识领域无法广泛应用。删除法和填补法在处理不完备数据时, 或多或少会改变原始数据集。针对这些问题, 文献[21,22,23,24]提出一种直接在不完备样本集构造分类模型的方法。但中医样本很难保证各条件属性间的独立性, 文献[25]为降低条件属性和决策属性间相关性的计算复杂度, 提出了选择性集成方法, 从样本集中挖掘可信完备子集, 在每个可信完备子集上构建诊疗模型, 通过选择性集成方法获取知识, 但文献[25]没有考虑不完备数据稀疏以及测试样本包含不完备数据的情况。
因此, 现有不完备数据处理方法, 当被应用于肝硬化证候辨识模型构建时都存在以下不足: (1) 数据损失; (2) 引入不恰当的假设; (3) 没有充分利用有限的临床样本和不完备样本中包含的信息。本文将不完备样本集中对象间的关系扩展为一种相似关系, 进而构建肝硬化证候辨识模型, 以提升所构建模型的鲁棒性[26]。
2 材料与方法
给定不完备证候辨识系统, 其中是非空有限样本集合;为样本的属性非空有限集;表示决策集。临床收集样本的过程中, 样本属性集不可避免的包含缺失数据, 即和, 满足, 其中表示样本在属性的取值, *表示空值。
中医证候智能辨识过程可抽象为构造从样本集到证候集的一个模型, 基于已有样本集学习训练, 使得对于一个给定的新样本, 能够正确辨识患者肝硬化程度。图1给出了相似性框架下肝硬化证候辨识知识获取方法的技术路线。
包含不完备数据的证候辨识系统, 样本间的关系为相似关系, 样本域上只能产生覆盖, 在相似性框架下, 条件属性对于属性集的依赖度和重要度分别为[27]:
其中表示集合中成员的个数。
基于和确定条件属性的可信度, 按可信度大小降序排列条件属性。可信度最大的条件属性为种子, 在样本集中枚举覆盖最多完备数据的极大子集, 每个极大子集确定一种可信完备模式p, p公式化的形式如下:
进而基于覆盖最大原则, 每个模式p唯一映射一个可信子集S:
互信息与子集的可聚性具有内在一致性, 基于子集间条件属性的互信息、子集的熵衡量子集间的相关性μ, 以及子集的样本规模, 度量子集间的互信息, 将互信息值大的子集聚类为可信子集。
3 应用实例和结果
将文中方法应用于临床收集的肝硬化样本, 每个样本包含67个条件属性、1个Child-Pugh分级属性和1个证候分类属性。表1列出了含有缺失值的条件属性, 以及其缺失程度。本文用不完备率来描述临床样本第个条件属性的缺失程度。定义为:
其中表示样本的个数。
对于上述包含缺失值的样本集, 基于贝叶斯网络模型, 以证候辨识精度为评价标准, 我们分别采用三种不同方法处理缺失值。第一种方法是删除法, 删除条件属性不完备的样本, 将剩下的样本应用于贝叶斯网络模型, 获取辨识精度;计算每个条件属性的均值, 用均值填补缺失数据, 新获取的完备样本集应用于贝叶斯网络模型, 以证候辨识精度作为标准评估对比删除法、均值填补法和本论文所提出方法。表2列出了三种方法的辨识精度。实验结果显示删除法减少了样本数量, 均值填补法不可避免的引入噪声, 这两种方法都没有获得较好的辨识精度。本文所提方法直接应用于原数据集, 充分利用完备或不完备的数据, 保证了一定的辨识精度。
但文中所提方法当不完备数据稀疏程度增加时, 算法的时间复杂度也会增加, 如何提升数据稀疏时的算法效率是后续将研究的工作。
4 结语
本文在相似性框架下, 将不完备样本集中对象间的关系扩展为一种相似关系。该方法直接面向包含不完备信息的样本集, 构建可信完备模式的挖掘方法, 进而通过可信完备模式获取映射可信完备子集的方法。该方法应用于临床中医肝硬化的证候辨识, 通过和临床医生的辨识结果比照, 具有较好的一致性。
摘要：数据质量在很大程度上决定了中医证侯辨识模型的精度。临床实践中, 数据缺失的现象非常普遍。现有的中医证侯辨识知识发现方法在数据不完备时, 都存在一定的局限性。笔者研究一种面向不完备数据的肝硬化证侯辨识知识发现方法。基于对象间的相似关系, 建立相似性框架下可信完备模式挖掘方法, 进而构建可以应用于肝硬化证候辨识的知识获取方法。该方法获取了肝硬化中医诊疗规则, 对于新收集肝硬化病例数据, 自动辨识其证侯。通过实例验证, 表明通过文中所提方法辨识所得证侯与临床医生辩证结果具有较好的一致性。
缺失或不完备数据的填补方法分析 篇5
不完备数据又称缺失数据, 在各种科学研究中, 数据的缺失现象很普遍, 不完备数据给数据的使用和分析带来了很大的困难, 也是造成信息系统不确定的主要原因之一。我们经过整理相关文献, 总结了一些不完备数据的定义:数据传输或采集中的错误、空值、超出范围或者不符合要求的值。造成数据缺失的原因是多方面的, 主要可能有以下几种:
1.1 有些信息暂时无法获取。
例如在医疗数据库中, 并非所有病人的所有临床检验结果都能在给定的时间内得到, 就致使一部分属性值空缺出来。又如在申请表数据中, 对某些问题的反映依赖于对其他问题的回答。
1.2 有些信息是被遗漏的。
可能是因为输入时认为不重要、忘记填写了或对数据理解错误而遗漏, 也可能是由于数据采集设备的故障、存储介质的故障、传输媒体的故障、一些人为因素等原因而丢失了。
1.3 有些对象的某个或某些属性是不可用的。
也就是说, 对于这个对象来说, 该属性值是不存在的, 如一个未婚者的配偶姓名、一个儿童的固定收入状况等。
1.4 有些信息 (被认为) 是不重要的。
如一个属性的取值与给定语境是无关的, 或训练数据库的设计者并不在乎某个属性的取值 (称为dont-care value) 。
1.5 获取这些信息的代价太大。
1.6 系统实时性能要求较高。即要求得到这些信息前迅速做出判断或决策。
2001年荷兰统计与运筹协会下属的统计软件分会组织了一个关于缺失数据的讨论会, 讨论会提醒人们, 即使表面上看缺失数据对研究结果不可能构成威胁时, 也不要简单地将其删除, 因为虽然缺失数据可能只占到4%-5%的比例, 但那些重要信息中往往有30%-95%的数据来自这些数据, 如果恰好重要信息完全不在这些“盲区” (缺失数据) 中, 那么也就没有什么问题, 但很显然这样的风险太大了, 所以绝对不能存在侥幸心理.而要妥善处理好不完备数据。下文如无特别说明, “缺失”、“不完备”、“不完全”不再区分, 都是同一说法。
2 数据预处理中填补不完备数据的方法
填补空缺值的方法技术很多, 下面我们描述了在实际中采用的几种方法, 对于不同类型的空缺值, 其填补方式是不一样的, 应根据实际情况选取适当的技术。
2.1 从相关信息中提取填补空缺值所需数据:
某些数据中的空缺值, 其内容在其他有些相关信息中存在, 关键是利用这些相关信息, 在其中查找, 用查找到的内容来填补空缺值, 这种方法的关键是在相关信息中的查询、搜索技术。
为了很好的应用这些相关信息, 必须对其进行规范、整理, 要进行的工作有: (1) 统一数据格式; (2) 数据的一致性处理; (3) 制定查询、搜索策略; (4) 分析空缺项填补值的正确性; (5) 改进查询、搜索策略。
2.2 利用同类别均值填补空缺值。对于某些空缺数据项, 以其同类别的所有非空缺值的平均值来填补该空缺数据项。
2.3 利用决策树技术填补空缺值。
该方法是将数据巾其他不存在空缺项的数据生成一个决策树, 然后应用此决策树填补空缺的数据项。
生成决策树的算法很多, 有著名的ID3、C4.5算法, 还有其他及改进的算法等, 对于诸多的、生成决策树的算法, 将其应用于同一问题, 取得的效果各不一样, 为取得最佳的效果, 需要试验。
在填补空缺值时, 可以应用ID3算法生成决策树。ID3算法的一般过程在各类数据挖掘资料中都有阐述, 在此, 仅介绍算法在填补空缺数据项时的过程。
算法如下:
(1) 根据空缺数据项选定分类属性, 根据分类属性生成测试属性集合; (2) 根据选定的测试属性集合, 生成当前数据库表 (根据此表中的数据生成决策树) , 将其置为当前决策树节点; (3) 计算当前节点各测试属性的信息增益; (4) 选定当前节点信息增益值最大的测试属性; (5) 如果当前节点满足条件a之一, 则将堆栈中的节点弹出一个, 并将弹出节点置为当前节点, 转第3步。不满足条件, 转下一步。如果堆栈空, 转第7步;条件a:分类属性值单一;选定的测试属性值单一;选定的测试属性最大信息增益是0。 (6) 生成当前节点的子决策树, 将子决策树中除最右边节点外的其他节点压入堆栈, 将子决策树最右边节点置为当前节点, 转第3步: (7) 结束。结束后, 则得到一棵以测试属性为节点的决策树, 树的分支为相应节点测试属性的各种取值。算法分析:该算法是树的遍历算法, 属先根遍历, 其时间复杂度为O (n) 。
2.4 手工填补。
当上述几种方法都无法使用时, 需要应用有关领域的专业知识, 根据数据的实际情况人工填补。人工填补的效率非常低, 这种方法只对个别空缺值使用。
3 从相关信息中提取填补空缺值所需数据的实例分析
某公司在全国某些地区有其子公司, 每年底, 各子公司要向总公司上报库存产品的情况, 而总公司为检查储存产品的情况, 每年都要在全国有关子公司内抽取若干库存产品来检测其质量。做检测时, 由于当时的历史条件所限, 很多产品的元件信息没有填写.公司为了分析产品的质量状况, 将历年检测情况综合起来进行分析, 由于检测产品的很多元件信息都是空缺值, 为了填补这些空缺数据项, 需要从公司历年产品的库存信息内查询搜索有关产品的信息。为此, 对历年库存产品信息进行了统一数据格式、数据一致性处理等工作, 为了进行有效的查询搜索, 制定了如下的查询搜索策略:
(1) 元件三的有关信息, 由于当时认为其没有必要, 因此, 在历年的检测中没有记录其信息。
(2) 对所有空缺项的记录依次填补, 首先填补元件一的有关信息, 其次填补元件二的信息, 最后填补元件三的信息。
(3) 以产品名称、序、生产年、生产厂为主线索进行查找搜索, 同时, 为各查询搜索条件赋予了查询级别。
a.以查询级别为01、02的产品名称、序、生产年、生产厂搜索;b.以查询级别为01的产品名称、生产年、生产厂搜索;C.以查询级别为02的产品名称、生产年、生产厂搜索;d.以查询级别为小于03的产品名称、序、生产年、生产厂搜索;e.以查询级别为小于03的产品名称、生产年、生产厂搜索。
(4) 同一年的库存产品信息内如果包含多个空缺数据项的记录, 则依次搜索。
(5) 查找检测年份 (含) 前所有年份的库存产品信息。
(6) 查找检测年份后的所有年份的库存产品信息。
经过填补, 在对填补数据项正确性进行分析后, 认为第4步可以改进, 在多个记录内可以采用最有可能的记录进行填补, 而不是依次搜索, 最后得出的结果, 令人比较满意。
4 结束语
通过本文的阐述, 我们可以看出, 对数据填补应慎重对待, 一味增加填补次数以求较好的填补效果是不合理的, 需要结合资料本身的信息选择恰当的填补次数, 才能得到最大的收益。正如最早系统地提出填补方法的Rubin所说:“填补, 这个概念是十分诱人的也是非常危险的。之所以诱人, 是它会使人们进入一种高兴的状态, 以至于最后完全迷信填补后的数据集而容易忽略偏差的存在, 这即是其危险所在。”所以针对各种实际问题, 要注意分清问题的实质, 合理并且适当地运用处理方法才是解决好实际问题的关键所在。
参考文献
[1]曹阳, 张罗漫.运用SAS时不完整数据集进行多重填补一SAS 9中的多重填补及其统计分析过程 (一) .中国卫生统计, 2004, 21 (1) :56-63.[1]曹阳, 张罗漫.运用SAS时不完整数据集进行多重填补一SAS 9中的多重填补及其统计分析过程 (一) .中国卫生统计, 2004, 21 (1) :56-63.
不完备信息系统 篇6
退市制度对于资本市场的健康、有序发展起着不可或缺的作用。合理、完善、有效的退市制度可以对证券市场进行规范, 通过将触及退市标准的上市公司淘汰出局, 激励上市公司完善其公司治理结构, 注重其经营业绩提升。从而达到净化资本市场、促进资金合理流动、优化资源配置、降低投资者风险的目的。
但是, 制度的有效性才是保证上市公司合理有序退市, 保持证券市场活力的根本。从1993年证券交易所成立初期《股票交易与管理暂行条例》的施行至今, 我国上市公司退市制度建设已迎来了第20个年头。在这过程中, 我国退市制度在不断地进行改革, 但是各项标准仍不够完善, 且制度的有效性并未很好地显现。因此, 到目前为止, 我国退市制度的不完备性仍然比较严重, 这主要体现在我国退市制度的不完善性以及退市制度的低效性。
二、我国退市制度不完善性
对比国际成熟市场, 目前, 我国退市制度仍然存在诸多不完善的地方。
首先, 从退市标准来看, 我国的退市标准过于单一, 形同虚设, 同时也缺乏严密性。旧版的退市制度中主要就是“最近三年连续亏损”这一“实质大于内容”的硬性指标。长期以来, 多只ST股的上市公司可通过资产处置、债务重组和政府补贴多种手段轻松规避退市。
其次, 在退市程序方面, 我国的退市程序行政干预过多, 具有浓重的行政色彩, 且属于公司的权力无法体现, 这不仅不利于纠正上市公司的行为偏差, 提高其整体素质, 而且会为幕后操作提供滋生腐败的沃土。
第三, 退市法律规定不够健全。特别是缺乏对投资者利益保护的相关法律法规。由于在我国, 中小股东处于相对弱势地位, 上市公司退市后, 持股的中小股东将面临损失, 其利益得不到保障, 合法权益无法得到伸张。
三、我国退市制度改革
针对上市公司退市制度各方面的不完善性, 本次的退市制度修改与完善较以往有很大突破。继深交所将创业板退市制度公诸于世后, 沪深交易所于2012年6月28日正式发布了完善主板和中小板市场退市制度的方案。方案主要在借鉴国外成熟资本市场退市制度经验的基础上进行相关完善。
首先, 新政中有关退市标准的规定更加多元化, 不仅增加了“净资产”“营业收入”“市场指标”等数量型指标, 还更加关注对上市公司的持续经营能力与获利能力的考察, 体现了市场化退市的理念和运行机制;而且在非数量标准方面, 也纳入了审计意见类型指标, 扩大适用未在法定期限内如期披露年报的指标, 纳入了扣除非经常性损益后的净利润指标, 并对相关暂停上市、终止上市的指标进行细化。这使得退市标准更加合理, 退市程序更加完善, 弥补了旧版退市制度“形式大于内容”的不足。
其次, 新政在保护投资者权益方面, 也借鉴国际成熟市场的经验, 做了相关改进。增设“风险警示板”和“退市整理板”。由于存在退市风险的相关传闻, 上市公司退市前后股价常会有异常波动, 因此, “风险警示板”的建立有助于提醒投资者对风险及时防范风险, 做出合理投资选择。而当上市公司股票被交易所作出终止上市的决定后, 将被转入“退市整理板”进行另板交易。届时, 上市公司将得到30天的“退市整理期”, 整理期满, 上市公司的股票将终止上市。这样, 能够保证投资者在上市公司退市前有一定的缓冲期可以将持有的股票进行处理。因此, 总的来说, “风险警示板”和“退市整理板”的设立在一定程度上可以起到缓冲退市风险, 保护中小投资者的作用。
四、我国退市制度的低效性分析
虽然在2012年6月28日发布的退市制度新规则中, 我国两市退市制度在借鉴国外成熟证券市场退市制度经验的基础上, 进行了相关条例的修改, 使其与国外主要证券市场退市制度具有较高的相似度, 但是我国上市公司退市现状与国外相比存在很大的差距:我国新上市公司数量较多而退市公司寥寥无几。究其根源, 在于我国退市制度的低效性。这主要体现为大量触及退市标准的公司“停而不退”, “退而不出”现象严重。据统计, 在过去三年间, 美国纳斯达克退市公司的数量占上市公司总数的13.8%;而我国股市成立至今的22年间, 退市公司数量仅占上市公司总数的1.82%。造成我国退市制度的有效性低的原因主要有以下几方面:
(一) 证券市场的低成熟性
退市制度能够较严格执行的重要原因之一在于证券市场体系发展程度高, 多元化结构丰富。在海外发达证券市场上, 均存在多层次的证券市场体系。如美国上市公司从主板市场退出后, 可退到二板市场。如果上市公司在宽限期内仍不能达到上市要求, 监管机构将责令其退到场外市场进行交易, 从而实现逐级退市。若在宽限期内整改后又符合上市条件的, 则可恢复上市。可见, 完善多层次的证券市场体系为退市制度的有效执行提供良好的市场环境。此外, 海外成熟的证券市场拥有发达便捷的公司收购、兼并和破产机制。因此, 绩差公司很容易成为被廉价收购的目标, 而无需管理部门勒令其强制退市, 就因破产或者被收购而自动退市。从而市场上不会充斥大量的劣质股。这正式成熟资本市场对资源配置起作用的结果。
相比较国外成熟资本市场几百年的历史, 我国资本市场起步较晚, 发展速度也较为缓慢慢, 市场结构仍处在从单一化到多元化的过渡阶段, 不能够像成熟资本市场那样, 为退市制度的顺利施行提供良好的环境。使得目前我国退出程序与制度安排上仍然存在一定的施行困难, 绩差股仍然充斥着市场, 从而导致我国上市公司退市制度有效性降低。
(二) “壳资源”的稀缺性
对于发达国家和地区的成熟资本市场来说, “借壳上市”行为常常受到较为严格的管制。在韩国KOSDAQ市场, 日本JAS-DAQ市场以及英国AIM市场等国际主要证券市场上, 拟通过“借壳上市”的完成并购重组的公司, 一般都需要满足IPO的条件, 通过IPO标准的审核, 完成IPO的上市程序, 上市发行人被看成是新的上市申请人。因此, 在成熟资本市场上, “壳资源”并没有过高的吸引力。
对于我国而言, 由于新股发行实行“核准制”, 拟上市公司的IPO难度较大, 而通过“借壳上市”的方式来进入证券市场要比企业申请上市难度小, 成本低。而且在公司退市过程中, 由于“借壳上市”预期的存在, “壳公司”成为争相炒作的稀缺资源。创业板的设立虽然在一定程度上降低了上市难度, 增加了公司的上市机会, 使得“壳资源”的稀缺性得到一定缓解, 但是《关于完善创业板退市制度的方案》的推出, 并未彻底堵住“借壳上市”的后门。一些触及退市标准的绩差公司为避免其退市命运, 常常试图利用“壳资源”进行并购重组的方式, 完成华丽转身, 来维持其上市地位。因此, “壳资源”的稀缺性是使得我国证券市场退市制度有效性降低以及我国上市公司“退而不出”的局面难以缓解的最重要的原因。
(三) 法律制度的低效性以及
一个完整的证券市场必须重视退市法律制度的完善与有效执行。完善的上市公司退市法律制度对于一个正处在发展中的证券市场尤为必要。在海外成熟的证券市场上, 上市公司退市法律制度设计充分遵循了证券市场的自身规律, 体现了市场化的规则;并且注重操作程序, 能够充分保护中小投资者的利益。
与成熟证券市场相比, 我国证券市场现行的退市法律制度还存在着很大的差距。这也是我国退市制度运行效率低下的原因。我国《公司法》中有关上市公司退市的规定仅是一种字面上的法律, 对于上市公司退市之后的相关问题, 未能得到很好解决。而且, 我国的退市决定权存在于证券管理部门, 因此, 法律规定缺乏足够的操作空间, 不能有效实施。1999年施行的《证券法》, 其在上市公司退市问题上仅对《公司法》中的相关规定进行简单的重复。其唯一突破在于开始关注交易所在退市问题上应发挥的具体作用。可以说, 这部《证券法》对健全与完善我国上市公司退市法律制度并没有起到实质的促进作用。2006年新《公司法》和《证券法》虽然对退市的相关条例作了修改, 但是由于其原则性较强, 因此其可操作性仍然不高。
(四) 各方利益的博弈性
对于上市公司来说, 由于上市的成本太大, 而在证券市场上的融资成本低。所以公司一旦上市, 就想永续保持其上市地位, 实现“圈钱”的目的。在公司出现问题时, 则会利用各种手段维持其上市地位, 而死活不愿意退市。
对于各地政府来说, 上市公司数量成为考核官员政绩的重要指标之一。因此, 各地政府从自身利益考虑, 采取各种措施避免上市公司退市。从而我国证券市场上市公司的退市行为呈现出较严重的行政干预性。大批绩效差的上市公司通过政府补贴, 破产重整, 债务重组等方式得以“退而不出”。这样, 退市过程中过重的行政色彩, 使得我国退市制度的有效性难以实现。
对于中小投资者来说, 上市公司一旦退市, 其投资者持有股票的流动性降低, 基本上失去股票的意义。而且, 我国民事赔偿制度的不健全, 退市后由于操纵市场、虚假信息披露等违法违规行为给投资者造成的损失不能得到有效赔偿。因此, 在目前我国证券市场体制下, 从投资者的利益角度讲, 他们是最不希望所持有股票的上市公司从证券市场退出的。
因此, 无论从哪一方的利益考虑, 上市公司退市都不是各方利益均衡的最优选择。从而, 完善的退市制度在利益各方面前的有效性只成为一种摆设。
(五) 退市新规的缺陷性
虽然退市新规提高了我国退市制度的完善性和可操作性, 也为新旧规则的过渡期的衔接做了妥善安排。但是, 此次退市制度的修改也存在一定的缺陷性。这使得新规尚未开始正常运行, 其有效性就大打折扣。其一是“连续三年净资产为负”才可能退市的标准, 使得退市过程变得愈发漫长与艰难。我国IPO超募使每股净资产高企局面难以缓解, 若想让公司每股净资产“亏空”实属不易。如果再有“连续三年净资产为负”才能退市的规定, 那么我国上市公司退市则成为遥遥无期的谎言。其二是退市新规规定从2012年会计报表算起, 对于过去“连续三年净资产为负”的公司, 则对其历史问题既往不咎。而目前, 我国A股市场“连续三年净资产为负数”的上市公司已达30多家。退市制度的改革, 使得这些濒临退市的上市公司在“净资产”这个指标上仍有三年的宽限期, 因此给了它们足够的时间来规避退市, 从而拉长了退市过程。这是对垃圾股历史遗留问题的妥协与让步, 对其余上市企业来说, 也无法体现制度的公平性。
五、提高退市制度有效性的几点建议
退市制度的完备性不仅需要根据证券市场的需要不断调整和完善退市的标准和规则, 而且应当采取适当措施提高退市制度的有效性, 从而缓解我国上市公司历来“停而不退”, “退而不出”的弊病。针对以上分析, 本文提出以下几点建议:
(一) 大力发展与完善我国资本市场。建立包含一级市场、二
级市场、三级市场以及场外市场的多层次证券市场。这不仅可以给予退市公司继续进行交易的机会, 使其更加顺利、有序地逐步从证券市场退出, 而且可以较大程度上减少投资者的损失。
(二) 针对我国“借壳上市”现象严重, 并且屡禁不止的情形,
一定程度上可以借鉴境外成熟市场的做法, 如严厉退市法规, 适当提高“借壳上市”门槛, 使“借壳上市”的标准与公司IPO难度相当, 甚至杜绝“借壳上市”。这样, “壳资源”的稀缺性就得到一定程度的缓解。
(三) 针对我国地方保护主义盛行, 各方利益博弈所导致的
证券市场退市制度执行不力情形, 管理层应当提高执行力, 加强监管力度, 从而提高退市制度的效力, 使地方保护主义等行政干扰因素远离退市机制。其次, 通过量化退市考核机制来减少管理层随意性, 通过实施以市场调控为主, 行政调控为辅的退市机制, 达到由市场决定去留的目的。尽量减少长时间的退市缓冲机制, 防止暂停上市的绩差公司寻找重组的机会来规避退市。对于投资者方面, 应该建立投资者保护的司法保障体系, 细化投资者通过法律程序追究责任的条款。
(四) 提高退市制度的执行效率, 还需要进一步对退市法律
法规进行完善。比如在对《公司法》《证券法》两部法律修改的基础上, 设计更加符合市场规则的退市标准, 完善退市程序, 注重提高法律条款的可操作性;完善退市的配套制度;相关制度的执行部门要强化执法力度与成效。
(五) 虽然退市新政使我国的退市制度有了跨越性的进步,
但对于退市新规中有关条例的改革有待完善, 并要注重其合理性。比如对具有历史遗留问题的上市公司, 应当设置特殊的处理方法, 从而体现制度的公正性。而不是既往不咎, 与其他企业一视同仁;对于暂停上市、终止上市的退市标准的改革应该考虑其可行性, 而不是形同虚设。
参考文献
[1]上市公司退市制度研究[J].河北法学, 2004, (03) .
[2]李自然, 成思危.完善我国上市公司的退市制度[J].金融研究, 2006, (11) .
[3]王震强, 李央.境外资本市场退市制度与运行经验分析[J].投资研究, 2011, (03) .
[6]陈杰.海外创业板退市制度分析及对我国的借鉴启示[J].武汉金融, 2009, (10) .
[4]宋常, 陈晶.中国资本市场退市制度改革与探索[J].潍坊学院学报, 2012, (05) .
不完备信息系统 篇7
算法使用链表的一元存储方式替代矩阵的二元存储方式,在约简过程中不断剔除大量的无效数据并摒弃复杂的计算,使得算法复杂度大大降低,利用启发式方法设计了基于限制性容差关系的改进算法,并通过实例证明算法在计算效率和存储空间等方面都有一定的优势。
1 基本概念
定义1决策表是一个有序的四元组S = 〈U,A,V,f〉,其中U是对象的集合,A = C∪D是属性集合,C和D分别称为条件属性集和决策属性集,D≠Ø ,V是属性集A的值域,f: U×A→V是属性到值域的映射。如果对于至少存在一个属性a∈C ,Va包含空值,即f( x,a) = * ,则称此决策表是不完备的。具有遗漏属性值的属性子集BA ,记遗漏值为* 。
定义2设S = < U,A,V,f > 是一个完备信息系统,
定义3设S = < U,A,V,f > 是一个完备信息系统,定义U上的二元关系L ( 限制容差关系) ,,令
2 限制容差关系下的差别矩阵
定义4[8]设不完备决策表S = < U,C,D,V,f > ,其中C = { c1,c2,. . .,ck,. . .,cn} ,D = { d} ,改进的差别矩阵: M = {m ij }n* n,1≤i,j≤n = U;式中:
式中:
差别矩阵是对称矩阵,式中1≤k≤C ,其中k代表条件属性的位置。
定理1在基于限制容差条件下的差别关系中,mij,如果有且只有一个条件属性性ck,使得f( ck) = 1,并且xi和xj在其他属性值上存在属性ct,使得f( ct) = 0,则属性ck属于核属性。
证明: 对象xi与xj只在一个条件属性ck上取不同的非空值,则f( ck) = 1,对象xi与xj在其他属性下不可分辨,且满足限制容差关系,所以属性ck是唯一能够区分对象xi与xj的属性,去掉该属性后xi与xj就不可分辨了,所以属性ck是核属性。
3 链表
3. 1 链表的基本运算
链表是通过一组任意的存储单元来存储数据元素,其中数据结构图如图1所示,链表中的每个节点在数据结构都包含数据域和指针域,数据域存放数据元素,指针域存放后继节点的地址。若删除单链表的节点时,其功能说明如图2所示。
3. 2 基于链表的改进算法
差别矩阵的空间复杂度为O( | U |2) ,保存着论域中两两对象的可区分属性,在论域关于属性集划分中,相同决策值的对象在差别矩阵中矩阵元素为空,由此可知差别矩阵的空间利用率不高,因此选择链表作为非空矩阵元素的存储结构是非常有效,其约简与原来相同,但空间复杂度最多为O( | U/R |* ( | U / R | - 1) ) ,非空的矩阵元素值mij作为链表节点中的数据域。具体算法如下。
输入: 一个不完备的决策表
输出: S在限制容差关系下的约简结果RED ;
Step1初始化链表List,RED = Ø,Core =Ø;
Step2构建链表,若数据域中有且只有一个1[只有1个属性满足f( ck) = 1) ]且存在0( 即有属性ct使得f( ct) = 0) 则位置k处的属性ck即为核属性,Core = Core∪ { ck} ,不插入到链表List中; 否则插入链表List的表尾。
Step3 RED = Core,为减少计算量,删除List数据域中所有核属性位置为1的节点。
Step 4得到简化的List后,统计List中个属性出现的次数,然后将出现次数最多的属性ci加入到约简结果中,RED = RED∪ { ci} ,并删除链表中位置i为1的所有节点,依次循环,直到链表为空。
Step5输出约简结果RED。
4 算法实例分析
Step1给定不完备信息系统S = < U,C∪D,V,f > ,其中论域U = { a1,a2,. . . . ,a12} ,条件属性C = { c1,c2,c3,c4} ,决策属性D = { d} ,引用文献[8]和表1。
Step2计算得矩阵元素m19= 0001 ,m26=0001,m49= * 0* 1中f( c4) = 1并且f( c2) = 0 ,所以条件属性c4为表1的核属性,同时m46= * 1* 0中f( c2) = 1且f( c4) = 0 ,所以属性c2为表1的核属性,RED = Core = { c2,c4} ;
Step3删除链表元素中f( c2) = 1或者f( c4) =1的链表元素,链表如图3所示剩余5个节点;
Step4统计数据域中位置为1的值为5,位置为4的值为2,则RED = RED∪ { c1} ,删除链表节点中数据域位置1为1的节点,得到空链表;
相对文献[8]算法复杂度较高的缺点,改进后的算法计算过程简单,且不涉及复杂的计算Step2的时间复杂度为O( | U |2| C | ) ,Step 3的复杂度小于为O( | U |2) ,Step 4的时间复 杂度计算 为O( | C - Core | | K | ) + … + O( | C - RED | | K | ) ,其中| K |为链表的长度且长度一直在大大减小,所以Step4的时间复杂度小于O( | U |2| C | ) ,算法的时间复杂度为O( | U |2| C | ) ,空间复杂度为比文献[6]算法的时间复杂度O( | U |2| C - Core |2) 和空间消耗都要低。
5 结束语
限制容差关系相对相容关系更适合作为不完备决策表中扩充Rough集模型的不分明二元关系,因此本文选择限制容差关系作为选取不分明二元关系的关系模型,算法将基于限制容差关系下差别矩阵中的有效元素使用链表节点的方式存储于链表中,其过程对核属性的求取非常简单,链表的存储方式可以大大节省空间,空间利用率高,且不会浪费。
摘要：差别矩阵作为决策信息系统属性约简的方法是有效的;但空间利用率不高。通过对算法空间利用率及时间效率进行研究,提出基于链表的改进算法;并引入链表的基本运算。该算法通过使用链表的节点存储基于限制容差关系下有效的差别矩阵元素,并在约简过程中通过不断删除不必要的节点以节省时间。通过理论与实例证明其有效性和正确性。