[科普中国]-决策规则

决策规则的获取概述

Pawlak 粗糙集理论及其扩展模型, 是处理不同类型的决策信息系统的不协调性与不完备性, 并由此揭示其数据规律的有力工具. 信息系统知识发现的重要任务是, 揭示条件属性与决策属性之间的依赖关系. 对两者之间的依赖关系的研究主要体现在两个方面, 一是通过属性约简评估条件属性相对于决策属性的重要性, 二是计算“if-then”决策规则.在信息系统中, 如果一个对象关于某属性的属性值仅表示该对象关于属性所在的类, 则属性值确定对象间的不可分辨关系, 从而可建立以等价类为基本知识颗粒的Pawlak 粗糙集模型; 如果属性值表达对象之间的相似程度(接近程度), 则可以通过定义相容关系, 以相容类或最大相容类为基本知识颗粒, 建立相容关系粗糙集模型[4-9];如果对象的属性值表达对象之间的优势关系(偏序关系), 则该系统被称为序信息系统. 在序决策信息系统中, 对象的条件属性值确定对象之间的优势关系(支配关系), 而决策属性所确定的决策类之间也被赋予优劣关系. 以支配集和被支配集为基本知识颗粒, 提出了基于优势关系的粗糙集方法(DRSA).

DRSA 以对象的支配集和被支配集为基本知识颗粒, 定义决策类的并的上、下近似, 并由此获取优势决策规则(“at least”决策规则和“at most”决策规则).针对各类序决策信息系统, 如不完备序决策信息系统[14-16]、集值序决策信息系统[17]、区间值序决策信息系统以及模糊序决策信息系统等, 提出DRSA 的多种扩展模型, 并在属性约简与决策规则获取方面取得丰硕成果. 这些扩展模型也是以对象的支配集和被支配集为基本知识颗粒, 然而, DRSA 存在以下3 个方面的问题.

1)某些情况下, 支配集和被支配集作为基本知识颗粒显得太粗. 举一个特殊的例子: 当信息系统中的对象集关于条件属性集存在最大(小) 元而该最大(小) 元被指派至最劣(优) 的决策类时, 利用DRSA 得不到任何“at least”(“at most”) 决策规则, 即DRSA 无法处理这类不协调性.

2)DRSA 所得到的“at least”(“at most”) 决策规则,其决策值大(小) 于某特定值, 而不是落于一个有限区间. 它们能将满足条件的对象指派到不劣(优) 于某个特定决策类的那些决策类中, 但不能指派对象到优于一个特定决策类同时又劣于另外一个特定决策类的那些决策类中; 特别地, 不能把对象指派于一个指定的决策类; 因此, “at least”(“at most”) 决策规则不能直接应用于序信息系统中对象的分类.

3)DRSA 基于这样一种假设: 序决策信息系统本应满足优势关系原理(亦称系统是协调的), 即条件属性和决策属性之间满足单调性, 亦即, 依条件属性值为优的对象其决策值亦为优, 只不过由于数据获取手段的局限性或专家在赋予对象决策值时的踌躇, 导致数据出现不协调性, 使某些条件属性值为优的对象其决策值反而为劣. 然而, 可以想象, 在很多实际问题中, 条件属性和决策属性之间不一定满足单调性, 而往往满足分区域的单调性. 例如, 在评估国民经济运行状态时, 作为指标之一, 经济增长率并不是越高越好, 而是要控制其在一个合理的范围之内; 在评估身体健康状态时, 血压并不是越高越好或越低越好, 而是处于一个恰当的范围为好. DRSA 不能处理这种条件属性和决策属性之间满足分区域单调性的序决策信息系统.为了解决上述问题, 本文以“区间”为基本知识颗粒, 建立一种新的基于优势关系的粗糙集模型. 这里, “区间”是一个对象的支配集和另外一个对象的被支配集的交集.1

决策规则挖掘算法概述规则挖掘是数据挖掘的一项重要内容, 传统的基于粗糙集理论的规则挖掘方法是先求决策信息系粒计算的核心思想是对待求解的问题进行粒化, 在多个粒度空间对问题进行分析和求解, 进而合成原始问题的解, 符合人类从多角度分析问题、求解问题的认知规律, 并受到了研究者的关注.

本文将属性约简和属性值约简过程合二为一, 以知识粒为单位挖掘规则. 先对决策信息系统分层粒化, 在不同粒度的知识空间下计算粒关系矩阵, 并从中获取启发式信息根据启发式信息确定信息粒的属性值约简顺序, 在此基础上去除冗余属性,并设定终止条件, 实现决策规则的快速挖掘. 理论分析和UCI 数据集的测试结果表明, 该算法能获得所有最简规则.

基于粒计算的最简决策规则挖掘算法对决策信息系统挖掘规则的传统方法是先求属性约简, 再逐行提取规则, 中间包含了很多冗余计算,最后的结果也取决于属性约简结果的好坏, 并且随着样本集的增大, 算法复杂性将大大增加. 对属性约简进行了粒度原理分析并指出, 对决策信息系统进行属性约简得到的知识划分空间是极大近似划分空间, 但该知识空间的知识粒并不一定是整个知识空间中最 “粗” 的粒. 本文考虑在不同粒度层次的知识空间中挖掘规则. 为便于算法说明, 先给出符号定义.

3.1 符号定义

为了不失一般性, 假设决策信息系统有 个条件属性, 1 个决策属性. 为条件属性 ′ 所含条件属性的个数, 表征系统的粒度, 1;为粒度下的所有条件属性 ′, 这样的条件属性有 个;为 中某一条件属性对应的条件粒矩阵; 为决策属性对应的决策粒矩阵; × 为粒关系矩阵.

3.2 算法描述

基于粒计算的最简决策规则挖掘算法.输入: 决策信息系统;输出: 所有最简决策规则.

1) 生成决策粒矩阵 并取粒度 = 1.

2) 对 中每一个条件属性求条件粒矩阵和粒关系矩阵 , 计算 1、 2, 保存相应数据并做以下处理:

① 寻找是否存在 2 = 1. 若存在, 则由性质 3 可知, 对应信息粒可以完全区分某一决策类, 约简过程中优先考虑, 这样可以保证在区分能力不变的情况下得到的规则最少, 约简相应的信息粒得到决策规则,否则转 ②;

② 若不存在 2 = 1, 则对 1 值的大小进行比较, 1 值越大, 对应信息粒的区分能力越大, 同样可以保证在区分能力不变的情况下得到的规则最少. 根据 1 值的大小确定信息粒的约简顺序, 通过约简信息粒得到决策规则, 转 ③;

算法复杂性分析算法主要考虑如何提高现有算法的计算效率, 包括如何减少冗余计算, 如何提高搜索效率, 如何减少存储空间.按照启发式信息 1、 2对信息粒进行约简, 同时去掉冗余属性, 减少了传统先约简属性再约简属性值时的冗余计算. 在同一粒度空间下进行搜索时使用启发式算子对不同知识空间进行选择和排序, 提高了搜索效率. 在最坏的情况下需要搜索2次, 而在实际情况中, 当数据本身的冗余性很大时, 搜索空间要远远小于2 ,因为在该算法中加入启发式信息, 同时设置终止条件, 算法收敛更快. 本文使用的矩阵是布尔稀疏矩阵。2

决策规则约简概述基于数据挖掘的KDD技术近来得到人工智能领域的广泛关注。粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。粗糙集合理论提供了一整套方法，从数学上严格地处理数据分类问题。它是处理具有信息不确定、不精确、不完善系统的数学工具，是一种比较适用的归纳、分类方法。粗糙集合仅仅分析隐藏在数据中事实，并没有带入人为的模糊性。是采用精确的数学方法分析不精确系统的一种理想方法。目前已经在知识与数据发现、模式识别与分类、 故障检测等方面得到了较为成功的应用。在机器学中，基于Rough Set的推理技术也逐渐得到应用。

粗糙集理论虽然是针对不确定性问题提出的，但与模糊集处理问题的方法不同。它不像模糊集那样需要依赖先验知识对不确定性的定量描述，而只依赖数据内部的知识，用数据之间的近似来表示知识的不确定性。所以粗糙集理论本身是具有严密逻辑基础的，是精确的。利用粗糙集理论进行数据挖掘，抽取知识规则，最重要的一点就是基于粗糙集的属性约简和规则冗余值约简。 通过约简操作，降低属性的维数，总结出适用于决策支持的知识规则，是粗糙集理论的最重要应用之一。

粗糙集的基本概念粗糙理论的基本思想是，将数据库中的属性分为条件属性和结论属性，对数据库中的实例根据各个属性不同的属性值分成相应的子集，然后对条件属性划分的子集与结论属性划分的子集之间的上下近似关系生成判定规则。知识表达系统是有序对S=，其中U 非空有限集合, 称为全域，C 条件属性集合，D 是一个决策属性，A=C ÈD，称为属性集合。V是属性值的集合，f指定U中没一个对象的属性值，全域U的元素被称为对象或者实例。粗糙集之所以描述知识的不确定关系，是基于知识表达中的不可分辨关系的。在知识表达系统中，对于属性集A 中的任意一个属性a，如果实例i和记录xj对于属性a的取值相同，我们称xi和j基于属性集相等，是不可分辨的。

基于某个属性集A的所有等价记录的集合，被定义为等价类。属于同一等价类的记录归为一类，此分类称为R基于属性集A的划分，表示为U/ind(R)={R1,R2,..., R n}，[x]R表示中包含的等价类。当X ÍU ，且X为U/ind(R)={R1,R2,...,Rn}的并时，称X是R可定义的，称为R的精确集，否则X为R不可定义的，也称为R的粗糙集。粗糙集可以近似地用上近似和下近似来刻画。

属性约简为了说明约简，定义决策属性对条件属性的依赖性和属性的重要性。约简是原始属性集的一个最小子集, 并且这个子集具有和整个属性集同样的分类能力。对原始的数据表表示的知识系统，可以采用属性的重要性来进行约简。当 IMF a ( D ) = 0 时，该属性对决策属性分类没有贡献，可以省略的。 IMF a ( D ) ¹ 0 ，该属性就是核中的元素。根据属性重要性来进行约简，我们很轻松地得到该知识表中的核的构成，但核不是该原始知识表的约简。如果可省略的属性不唯一时，通常存在多种约简形式，这给决策规则提取带来障碍。并且被证明，最简单约简的求解是一个NP问题 。对约简的简化获得，只能采用启发式规则。利用属性重要性作为启发求最小约简 ，基本算法是，首先得到核作为属性约简集的基础，然后按照属性的重要程度从大到小逐个加入属性，直到依赖程度已经与原始属性集的依赖程度相等为止。最后对新加入的每个属性, 计算去掉后是否影响依赖系数。如果不影响,则将其删除。在属性重要性启发规则中，每次加入一个一个新属性要大量计算依赖度，而且最后还要对非核属性计算依赖度，是很烦琐的过程。下面讨论一种基于分辨矩阵的启发式规则。

根据分辨矩阵的原理知道， C i, j 在某种程度上代表了约简。如果约简与分辨矩阵交集为空，说明对象不能靠约简将它们区分开来，那么约简就不是区分所有对象的最小属性集合。利用约简与分辨矩阵的交集不为空的原理出发，我们设计了一个启发规则。如果 Ci, j 只有一个属性元素，该属性肯定是约简中的元素，否则 i , j 不可区分。因此可以类推, 分辨矩阵某项的所含属性越少, 该项就对分类所起的作用就越大。 而且该项出现得越频繁, 该项就越重要，该项中的元素更可能是约简中的元素。采用一个函数来标记属性的频度：f ( a ) = f ( a ) + card ( C ) / card ( C i , j ) ， 表示条件属性数目， card (C i , j ) 表示该分辨矩阵项中属性个数，f(a ) 为该项某个属性元素的频率。该公式考虑了项所含元素的多少的影响，同一元素在不同项中的频度增加 card (C) / card (Ci, j ) 是不同的。3

囚徒困境下的决策规则概述美国决策研究专家黑斯蒂(Hastie，R)认为判断与决策是人类根据自己的愿望和信念选择行动的过程。决策(decision making)从狭义上说是一个动态过程，是个体运用感知觉、记忆、思维等认知能力，对情境做出选择，确定策略的过程。广义的决策则包含判断与决策两个部分。博弈论中“囚徒困境”下的决策就是一个很有代表性的例子.

囚徒困境简介及其传统策略囚徒困境也称社会两难情境，是博弈论中的经典案例，指两个嫌疑犯被警察抓到，但警方没有掌握确切的证据，警察就分别找他们谈话：“如果你们都不认罪的话，我们将让你们都入狱一年；如果一个认罪，另一个不认罪的话，那么我们将判不认罪的那个十年的徒刑，认罪的将无罪释放；如果两人都认罪的话，我们将基于你们的诚实把每个人的徒刑降为五年，请你们各自权衡。”在这种情形下，两个疑犯都将面临着一个具有决定意义的两难选择。

亚当·斯密(Adam Smith)曾提出了理性经济人的假设，一是经济人是自私自利的；二是经济人的行为是理性的，即他们根据处境来判断自身的利益，追求个人利益尽可能最大化。在一个标准的囚徒困境中，可以用下面这个矩阵来表示：

|| ||

两个囚犯面临同样的选择——无论同伙选择什么，他们最好都选择认罪。因为，如果同伙不认罪，那么他们就无罪释放，否则，他们起码会被判十年徒刑。在一般情况下，假定每个囚徒都是理性的，他们的选择通常会出现以下两种可能情形：以A 为例，第一种可能是：B 认罪，这时如果A 也认罪，那么他们都要入狱5 年；如果A 不认罪，则A 将被判十年，B 无罪释放，两相比较下，对于A 来说，认罪显然是最优策略。第二种是：B 不认罪，这时如果A 认罪，那么B 将被判十年，A 将无罪释放，如果A 也不认罪，那么他们都将被判一年，这种情形下，A 的最优策略也是认罪。由此可见，对双方而言，每一个囚犯从个人利益出发，不考虑他人，他们都将选择认罪。但如果双方都不认罪，那么等待他们的将是一年的牢狱之苦。也就是说，对个人最有利的认罪策略，却不是集体(A 和B)的最佳策略。

囚徒困境中彰显的人性特点和理性信任观囚徒困境中个人的理性选择却是集体的非理性选择，从人性的角度来看，就会发现其中包含着人性恶的倾向。如果A 是善的，那么会出现两种情况，第一种情况是A 坚持不认罪也不供出B，B 同样也是坚持不认罪也不供出A；第二种情况是，A 坚持不认罪，B 认罪。

如果A 是恶的，那么也会出现两种情况，第一种情况是A 认罪也供出B，而B 不认罪.第二种情况是A 认罪也供出B，B 也认罪且也供出A 。

从善的角度考虑问题，可能得到最好的(1 年)和最糟的(10 年)的处罚结果；从恶的角度考虑，可能得到最好的(0 年)和最糟的(5年)的处罚结果。A、B 双方都从自己的利益考虑，选择恶的可能性会更大些。由此从囚徒困境中看到了人性恶的倾向。

在很多情况下，人面对的是一种集体条件下的困境，即博弈的双方可能是两大集团或更多的人，相同的博弈者可能会不断地重复面对相似的困境，“有条件的合作策略”将可能是理性经济人的最优策略。

重复为博弈产生了新的动力结构。通过重复，博弈者就可能按对手以往的选择而决定当前的选择。例如，存在一种所谓的“一触即发”策略，即“只要你背叛，我随后将永远背叛”，当双方保持背叛的状态时，就失去了双方获益的机会。而如果双方合作，其前提是双方的相互信任，就可能争取到双方获益的机会。还存在另一种所谓的“一报还一报”的策略，以合作开始，然后模仿对方上一步选择的策略。该策略以信任开始，决不首先背叛。时间嵌入性理论表明，今天的行为(合作或背叛)，将影响再次相遇时所做的选择。信任是使关系更持久、更稳固的最优选择。

现实生活中的“囚徒困境”及其应对策略囚徒困境在现实社会中广泛存在，而且情形要复杂的多。如汽车尾气与空气质量的问题。要保持空气清洁，汽车主人就要对车安装防污染的过滤装置，需要自己负担费用。而理性个体既想享受清洁的空气，又不愿为此付出代价。还有民众生育观的多子多福与人口膨胀的问题，上车不排队拥挤的问题等等。

要想克服重复条件下的囚徒困境，就要从集体成员的主观条件入手，使成员在新的基础上做出最优决策，打破原有的纳什均衡，建立新的有价值的纳什均衡(纳什均衡是经济学家Nash 提出的，若有N 个人参加博弈，那么在给定他人战略的情况下，在每一个参与人选择的最优战略所形成的战略组合中，没有任何一个参与人有积极性选择其他战略，也没有任何人有积极性打破这种均衡)。为此可以采取以下措施：

1、利用强化的作用.制定规则或提供奖惩措施，通过正强化的作用，引导决策者改变自己原有的决策偏好，向着有利于集体利益的方向发展，做出对集体而言的最优策略。

2、创造良好的文化氛围.囚徒困境说到底其实也是一种道德困境，要解决这种道德困境，就要从根本入手，创造良好的文化氛围，逐步改变全体的道德观、价值观、主观偏好。深刻认识囚徒困境的弊端，充分利用强化手段，在良好的社会文化氛围中创造人人都能从全局的利益出发，团结合作，使全社会建立起一种新的有利于全体成员的有价值的纳什均衡。4