一种决策表数据约简方法

摘要

本发明提供一种决策表数据约简方法，所述方法包括：步骤1，判断决策表数据集中最后一个条件属性是否为决策表核属性,如果是则将该属性的数据加入约简集R，执行步骤2；否则删除最后一列条件属性数据，重新执行步骤1；步骤2，将所述决策表核属性对应的列数据放到第一列，确定满足结束条件后，输出约简集R，否则返回步骤1。本发明具有简单高效地对决策表数据进行约简的有益效果。

权利要求

1.一种决策表数据约简方法，其特征在于，包括：

步骤1，判断决策表数据集中最后一个条件属性是否为决策表核属性,如果是则将该条件属性的数据加入约简集R，执行步骤2；否则删除最后一列条件属性数据，重新执行步骤1；

步骤2，将所述决策表核属性对应的列数据放到第一列，确定满足结束条件后，输出约简集R，否则返回步骤1；

其中，所述步骤1中判断决策表数据集中最后一个条件属性是否为决策表核属性，包括：对决策表数据集按照升序进行排序，如两个相邻样本xi,xi+1满足条件：cn(xi)＜cn(xi+1),d(xi)≠d(xi+1)且其他属性值全部相等，则最后一个条件属性为决策表核属性，其中C＝{c1,c2,…,cn}称为条件属性集，cn为条件属性集中元素，D＝{d}称为决策属性集,d为决策属性。

2.如权利要求1所述的方法，其特征在于，所述步骤1前还包括：删除决策表数据集中重复样本；如决策表数据集不一致，则将决策表数据集中所有样本的决策值变为d0,所述d0比已有的最大决策值大1；

其中,所述决策表数据集不一致是指所述决策表数据集中的条件属性的值都相同,而决策属性的值不同。

3.如权利要求1所述的方法，其特征在于，所述步骤1前还包括：设置约简集

4.如权利要求1所述的方法，其特征在于，所述步骤2中将所述决策表核属性对应的列数据放到第一列，之后还包括：删除约简集R 的正域。

5.如权利要求1或2所述的方法，其特征在于，所述步骤2中结束条件为：决策表数据集为空或剩下数据的决策值全部为d0。

6.如权利要求4所述的方法，其特征在于，所述删除约简集R的正域包括：对约简集R按升序排序，对任意两个相邻样本xi,xi+1进行如下检测，若R(xi)≠R(xi+1)，则判断xi所在粒子的决策值个数是否为1，若是则删除该粒子。

说明书

一种决策表数据约简方法

技术领域

[0001] 本发明涉及数据处理技术领域，更具体地，涉及一种决策表数据约简方法。

背景技术

[0002] 目前，随着数据采集、存储技术的快速发展，数据冗余的问题越来越严重，它不仅极大地浪费存储空间，也会显著降低基于数据的建模、决策等算法的性能。粗糙集理论是一种专门约简数据、从数据中提取有效信息的理论。该理论的核心在于数据约简，通过将不重要的、冗余的数据以及属性删除，从而获得一个包含完整信息的精简的新数据集，为基于数据的分析、建模、决策等提供优质的源数据。

[0003] 传统的数据约简方法常采用基于属性重要度的启发式约简结构。其方案表述如下：步骤1，数据集预处理，并计算决策表核属性集；步骤2，计算每个属性的重要度；步骤3，挑选具有最大重要度的属性；步骤4，基于所有已挑选的属性修改数据集；步骤5，判断是否满足算法结束条件，如果满足则输出已挑选的属性集，否则跳到步骤2。传统启发式约简方法的特点在于需要计算属性重要度以及整个决策表核属性集。尤其是属性重要度的定义与计算吸引了很多研究者的注意，并取得了大量的成果。

[0004] 然而，这种传统的启发式约简结构存在一些不足，主要表现在：第一，重要度计算次数太多，步骤2会被执行多次，大部分属性的都会被多次计算重要度，如果步骤4采用加法模式，则重要度需要计算(2|C|-|R|+1)*|R|/2次，如果步骤4采取减法模式，则重要度需要计算(|C|+|R|+1|)*(|C|-|R|)/2次，因此，不管属性重要度的计算公式是否简单，都需要浪费大量的时间；第二，基于属性重要度的随机性启发问题，现有的属性重要度计算方法都有可能产生多个具有最大重要度的属性，已有的解决办法常常在步骤3中进行随机选择，这将对属性约简的结果以及分类精度产生一个难以预知的影响。

发明内容

[0005] 本发明为克服上述问题或者至少部分地解决上述问题，提供一种更简单的启发式约简结构，为高速约简算法设计提供结构层面的理论支持与实现方法。

[0006] 根据本发明的一个方面，提供一种决策表数据约简方法，包括：步骤1，判断决策表数据集中最后一个条件属性是否为决策表核属性,如果是则将该属性的数据加入约简集R，执行步骤2；否则删除最后一列条件属性数据，重新执行步骤1；步骤2，将所述决策表核属性对应的列数据放到第一列，确定满足结束条件后，输出约简集R，否则返回步骤1。

[0007] 本申请提出一种决策表数据约简方法，利用决策表核属性判断来代替传统的属性重要度计算；利用排序技术构建高效的决策表核属性判断算法以及正域计算算法；每个属性最多计算一次，要么保留，要么丢弃；在启发过程中会不断删除冗余的列数据，以减少后续启发过程的时间以及空间复杂度。具有如下有益效果：1、本发明克服了传统的基于属性重要度约简结构的缺陷。表现在：抛弃了传统的属性重要度概念，不需要设计重要度计算公式，也不存在属性启发的随机性问题，计算结果客观，可重复性好；2、本发明的方法结构简单。表现在：每个属性最多计算一次，而传统方法的属性需要多次计算；其次，本发明不需要在启发之前计算整个决策表核属性集；3、本发明的方法只涉及到排序与比较操作，计算简单，不仅在单机上易于实现，也适合在大数据平台上运行；4、本发明的方法计算速度快。通过采用本发明推荐的快速算法，可以快速计算一个完备的约简。

附图说明

[0008] 图1为根据本发明实施例一种决策表数据约简方法的流程示意图。

具体实施方式

[0009] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0010] 本发明主要针对决策表数据进行处理，表示为S＝＜U,At,{Va|a∈At},{Ia|a∈At}＞，其中，U是所有样本的集合，At＝C∪D,C＝{c1,c2,…,cn}称为条件属性集，D＝{d}称为决策属性集。

[0011] 图1，在本发明的一个具体实施例中，示出一种决策表数据约简方法的整体流程。总体来说，包括：步骤1，判断决策表数据集中最后一个条件属性是否为决策表核属性,如果是则将该属性的数据加入约简集R，执行步骤2；否则删除最后一列条件属性数据，重新执行步骤1；步骤2，将所述决策表核属性对应的列数据放到第一列，确定满足结束条件后，输出约简集R。

[0012] 在本发明的一个具体实施例中，一种决策表数据约简方法，步骤1前还包括：删除决策表数据集中重复样本；如决策表数据集不一致，则将决策表数据集中所有样本的决策值变为d0,所述d0比已有的最大决策值大1：d0＝max(d(x))+1。

[0013] 在本发明的一个具体实施例中，一种决策表数据约简方法，步骤1前还包括：对数据集进行升序排序；然后对任意两个相邻样本xi,xi+1

[0014] 在本发明的一个具体实施例中，一种决策表数据约简方法，步骤1前还包括：设置约简集

[0015] 在本发明的一个具体实施例中，一种决策表数据约简方法，步骤1中判断决策表数据集中最后一个条件属性是否为决策表核属性，包括：对决策表数据集按照升序进行排序，如两个相邻样本xi,xi+1满足条件：cn(xi)＜cn(xi+1),d(xi)≠d(xi+1)且其他属性值全部相等，则最后一个条件属性为决策表核属性，其中c为条件属性集，d为决策属性集。

[0016] 在本发明的一个具体实施例中，一种决策表数据约简方法，所述步骤2中将所述决策表核属性对应的列数据放到第一列，之后还包括：删除约简集R的正域。

[0017] 在本发明的一个具体实施例中，一种决策表数据约简方法，所述步骤2中结束条件为：决策表数据集为空或剩下数据的决策值全部为d0。

[0018] 在本发明的一个具体实施例中，一种决策表数据约简方法，所述删除约简集R的正域包括：对简集R按升序排序，对任意两个相邻样本xi,xi+1进行如下检测，若R(xi)≠R(xi+1)，则判断xi所在粒子的决策值个数是否为1，若是则删除该粒子[xi]R。

[0019] 在本发明的一个具体实施例中，一种决策表数据约简方法，原始决策表数据集如表1所示。

[0020] 表1 一个原始决策表数据集

[0021]

[0022]

[0023] S1，设置 将数据集按照升序排序，如果是matlab环境，则使用sortrows函数进行排序，然后按照推荐的算法检查相邻样本，获得新的决策表数据集如表2所示。

[0024] 表2 预处理之后的数据集

[0025]

[0026] 其中，所有的不一致样本的决策值(也就是最后一列的值)全部改为“4”。

[0027] S2，判断条件属性c4是否为决策表核属性。具体方法如下：先比较第一个和第二个样本，它们c2,c3的值不同；然后比较第二个和第三个样本，它们c1,c3的值不同；然后比较第三个和第四个样本，它们c2,c3的值不同；以此类推，最后发现，没有两个相邻样本满足方案中的条件，因此，属性c4不是决策表核属性。

[0028] S3，删除最后一列数据，转上step2.对属性c3进行检测。可以发现：在比较第四个样本与第五个样本时，发现它们的c1,c2属性值相同(均为2和3)，c3属性值不同(分别为1和2)，对应的决策值也不同(分别为3和0)，因此属性c3是决策表核属性。R＝{c3}，转如下步骤。

[0029] S4，首先将属性c3对应的列放到第一列，然后按照升序排序，获得数据集如表3所示。

[0030] 表3 排序之后的数据集

[0031]

[0032] 按照本发明的算法，对相邻样本进行检测，由于R＝{c3}，因此，具体过程如下：令gr＝{x1}，第一个和第二个样本比较，可知它们的c3值相同，因此属于同一个粒子，gr＝{x1,x2}；接下来对第二个样本和第三个样本比较，它们的c3值不相同，因此，对gr进行判断，发现有两个决策值(0和3)，所以{x1,x2}为粗糙粒子，令gr＝{x3}；接下来，比较第三个与第四个样本，它们的c3值相同，gr＝{x3,x4}，接下来，比较第四个与第五个样本，它们的c3值也相同，gr＝{x3,x4,x5}，接下来，比较第五个与第六个样本，c3值不相同，因此，对gr进行判断，发现有多个决策值，所以{x3,x4,x5}为粗糙粒子，令gr＝{x6}；接下来，比较第六个与第七个样本，c3值不相同，因此，对gr进行判断，发现只有一个决策值，样本x6属于正域，令gr＝{x7}；接下来，由于没有相邻样本，因此直接判断gr的决策值，发现只有一个决策值，x7属于正域；即正域为{x6，x7}.删除正域之后获得的数据集如表4所示。

[0033] 表4 删除R正域之后

[0034]

[0035] S5，不满足结束条件，跳转S2。

[0036] 执行S2，判断c2，通过比较相邻样本可以发现，第三个和第四个样本的c3,c1值相同，c2值不同，决策值也不同，因此，属性c2为决策表核属性，R＝{c3，c2}.转step4.[0037] 执行S4，将c2所在列数据移动到第一列，按照升序排序，如表5所示。

[0038] 表5

[0039]

[0040] 接下来计算关于{c3，c2}的正域，得到正域为{x1,x2,x3,x4,x5}，删除正域之后，数据集为空；

[0041] 执行S5，由于数据集为空，算法结束，输出最终结果R＝{c3，c2}。

[0042] 在本发明的一个具体实施例中，一种决策表数据约简方法，相关的实验表明，本发明的计算复杂度近似为O(|U||C||R|).基于九个标准UCI数据集(Dermatology，Backup_large.test，Breast-cancer-wisconsin，Tic-tac-toe，Kr_vs_kp，Mushroom，Ticdata2000，Letter-recognition，Shuttle_all)的测试表明，本方法的计算时间为传统方法的0.09％到12.8％之间。与部分其他约简算法的计算时间比较如下各表所示。

[0043] 表6 与算法FSPA-PR的计算速度对比

[0044]

[0045]

[0046] 表1表明，本发明方法的计算时间为FSPA-PR的0.12％to 17.6％之间。对比算法FSPA-PR来自于：Y.H.Qian,J.Y.Liang,W.Pedrycz,C.Y.Dang,Positive approximation:An accelerator for attribute reduction in rough set theory,Artificial Intelligence 174(2010)597–618.

[0047] 表7 与ADM以及OADM的计算速度对比

[0048]

[0049]

[0050] 表2表明，本发明方法的计算时间为ADM的0.03％to 1.09％之间，为OADM的3.18％to 27.79％之间。表2的对比算法ADM以及OADM来源于：Z.Meng,Z.Shi,A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets,Information Sciences 179(16)(2009)2774-2793.

[0051] 表8 与Q-ARA的计算速度对比

[0052]

[0053] 表3表明，本发明方法的计算时间不超过Q-ARA的14.56％。对比算法Q-ARA来源于：M.Li,C.X.Shang,S.Z.Feng,et al.Quick attribute reduction in inconsistent decision tables,Information Sciences 254(2014)155-180.

[0054] 上述实验结果中对比算法所需要的运行时间均来自于参考文献本身，本算法的运行时间则采用与对比算法相似性能的计算机(Inter(R)CPU G645,2.9GHz and 1.81GB memory)进行计算获得。软件平台为matlab。对比结果表明，本发明方法计算速度非常快。

[0055] 最后，本申请的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。