基于可分辨重要度的属性约简算法

一种基于属性重要度的值约简算法
曹坤;柳炳祥;张仁宏
【期刊名称】《信息技术》
【年(卷),期】2005(29)8
【摘要】值约简是粗糙集理论的一个重要研究课题,很多学者对它进行了研究并提出了不同的值约简算法,但由于值约简算法是NP-hard问题,目前还没有高效的值约简算法.文中利用信息熵来计算属性重要度,在此基础上对值约简算法进行改进,提出了一种基于属性重要度的值约简算法,并将此算法运用到变压器故障诊断中.实验结果验证了此算法的可行性和有效性,能节省循环比较时间,提高计算速度.
【总页数】3页(P110-112)
【作者】曹坤;柳炳祥;张仁宏
【作者单位】景德镇陶瓷学院信息工程学院,景德镇,333000;景德镇陶瓷学院信息工程学院,景德镇,333000;景德镇陶瓷学院信息工程学院,景德镇,333000
【正文语种】中文
【中图分类】TP301.5
【相关文献】
1.一种新的基于区分矩阵的值约简算法 [J], 兰聪花;王逢娟
2.一种基于聚类划分的并行粗糙集属性值约简算法 [J], 陈燕云;肖坤楠;邱建林
3.一种基于属性重要度的约简算法 [J], 杨冠军;谢永芳;桂卫华
4.一种基于粗糙微聚集算法及属性重要度的匿名模型的数据质量评估 [J], 段文影;
段隆振;邱桃荣
5.一种基于粗糙集理论的值约简算法 [J], 樊艳英;徐章艳;张伟;张自敏;陈冠萍因版权原因，仅展示原文概要，查看原文内容请购买。

基于粗集可辨识矩阵的属性频率约简算法1 粗集可辨识矩阵粗集可辨识矩阵作为一种不精确、但可以提取较好特征的聚类方法，在数据挖掘任务中得到了广泛的应用。

它的核心是分布式的，也就是说，可以利用大量的类内数据来构建实例和属性之间的关系。

它的主要操作是将内部元素的属性频率应用于矩阵，然后利用频率约简算法把矩阵约简成一个稀疏的矩阵表示。

2 属性频率约简算法属性频率约简算法是一种使用统计学的技术，通过收集类内的特征频率，来构建属性间的关联，有效地对属性进行频率约简，从而获得较精确的特征聚类。

它的基本原理是，根据给定的特征计算来计算每个特征的频率，然后使用一种统计学技术来将它们抽象成一个稀疏的矩阵。

它的主要步骤如下：首先通过计算每个特征出现的频率来填充矩阵，然后使用最大熵原则对矩阵进行约简，最后利用聚类算法将不同的特征聚类，从而获得一种更有效的特征形式。

综上，属性频率约简算法可以使特征简化，矩阵简化，并且可以提取出一种有效的特征。

3 属性频率约简的优势属性频率约简算法的优势有：首先，它可以构建出有效的聚类，从而使分析任务更加容易；其次，它还可以用于建立稀疏的特征，这样可以更好地减少冗余的特征和噪声；最后，它可以有效地处理高维数据中的大量元素，并使其聚类更有效。

4 属性频率约简的应用属性频率约简算法在很多领域都有广泛的应用，如文本分类、图像分类、软件推荐等。

比如，在自然语言处理中，可以使用属性频率约简来提取文本的关键词，从而帮助文本分类。

另外，它还可以用来提取图像中的特征，从而方便图像分类。

此外，它还可以用于大规模数据访问和软件推荐，从而更加有效地实现软件任务。

5 结论从上文可以看出，基于粗集可辨识矩阵的属性频率约简算法可以有效提取出有效特征，并有很多应用。

它可以简化特征，减少运算量，有效地提取特征，从而实现数据挖掘的目的。

另外，属性频率约简的优势可以极大提升数据挖掘的性能，使算法更加有效。

基于云计算的属性重要度约简算法研究王志丹【摘要】Oriented to information system that processes large-scale data , this paper proposes a cloud-based attribute importance reduction algorithm , which applies MapReduce model , where Map and Reduce functions are reconstructed .This algorithm is a better solution and a new approach of attribute reduction in large-scale data pro-cessing.At last, case study indicates that this attribute reduction algorithm is efficient and feasible .%面对海量数据的信息系统，通过引入MapReduce模型，重构Map和Reduce函数，本文提出了基于云计算的属性重要度约简算法，较好地实现了海量数据集中的属性约简，为属性约简研究提供了新思路。

最后，实例分析表明，该约简算法是有效可行的。

【期刊名称】《洛阳师范学院学报》【年(卷),期】2014(000)008【总页数】3页(P64-66)【关键词】云计算;信息系统;属性重要度;属性约简【作者】王志丹【作者单位】郑州华信学院信息工程系，河南新郑451100【正文语种】中文【中图分类】TP3120 引言在粗糙集理论中，属性约简是其重要研究方向，通过属性约简可以删除不必要的属性，从而简化信息系统.近年来，许多学者从多角度提出相关的属性约简算法，如基于知识粒度［2］、属性相关性［3］、粒计算［4］等.这些方法虽然能在一定程度上寻找到最小约简，但面对海量数据时，却无法高效地删除冗余属性.基于此，本文将在云计算环境中，通过基于属性重要度的属性约简算法与MapReduce等云技术相结合，实现分布式并行处理海量数据的信息系统，最终寻找到符合要求的最小约简.通过实例分析表明，该算法不仅具有较好的执行效率，而且能够有效地进行海量数据处理.1 相关理论1.1 粗糙集理论下面，本文将引入Rough集的相关定义，详细内容请参考文献［7］.定义1［7］四元组 S=(U，A，V，f）称为一个信息系统，其中U表示对象的非空有限集合，称为论域;A表示属性的非空有限集合，V=∪a∈AVa，Va表示属性a的值域;f表示U×A→V的一个信息函数，它为每个对象在每个属性上赋予一个信息值，即对于任意的a∈A，x∈U，有f(x，a）∈Va，通常S=(U，A，V，f）也简记为 S=(U，A）.定义2［7］设S=(U，A）为一个信息系统，若XU，RA，给出下近似定义为:定义3［7］设S=(U，A）为一个信息系统，若XU，P、QA，则Q的P正域定义为:1.2 MapReduce模型为了更好地处理海量数据，本文采用Google公司提出的云计算技术——MapReduce模型.MapReduce是一种并行处理海量数据的编程模型，该模式主要包含Map和Reduce函数.面对海量数据，该模型的处理过程如下:首先，将待处理的海量数据集分割成若干可并行处理的子数据集;其次，对于每个子数据集，使用Map函数对子数据集进行数据解析，并产生中间结果，通常以＜key，value ＞形式表示;最后，对于所有中间结果＜key，value＞，使用Reduce函数合并具有相同key 的一组value值，减少中间结果个数.由于MapReduce模型简单，易于实现并行处理海量数据，因此，本文将提出基于MapReduce模型的属性重要度约简算法.2 基于云计算的属性重要度约简算法2.1 属性重要度定义4 设S=(U，A）为一个信息系统，属性a∈A，POSA(a）为P对A的正域，|POSA(a）|、|U|分别表示集合POSA(a）、U中元素个数，若令则称SigA(a）为属性a在属性集A中的属性重要度.SigA(a）表示属性集A中属性a分类的对象与A分类的对象的相似度，SigA(a）值越大，说明属性a的分类越接近A的分类，则属性a对于A就越重要.定义5 设S=(U，A）为一个信息系统，P⊆A，若对于任意的a∈P，都有SigP-{a}(a）＞0，说明每一个a∈P在P中都是必要的，则称P为独立的;否则称P为依赖的.由定义4和定义5可得如下定义:定义6 设S=(U，A）为信息系统，PA，若SigA(P）=1且P是独立的，则P为A 的一个约简.显然，一个信息系统可以有多个约简.2.2 基于云计算的属性重要度约简算法下面，给出基于云计算的属性重要度约简算法，本文分别设计了Map(算法1用于计算属性子集的中间结果）、Reduce(用于合并中间结果中具有相同key的value 值）和主算法(算法3用于选择最优候选属性，逐步添加到Red(A）中，寻找最小约简）.算法1Map(P，Vi）输入:属性子集PA，Vi为P的不同属性取值之一.输出:＜＜P，Vi＞，1＞.＜＜P，Vi＞，1＞是指P取Vi时出现的次数为1.对于PA，假设其共有n种不同的属性取值，则执行以下操作:for i=1 to n {扫描所有子信息系统，输出各个子信息系统的＜＜P，Vi＞，1＞}.算法2 Reduce(＜＜P，Vi＞，1＞）输入:＜＜P，Vi＞，1＞.输出:简化后的＜＜P，Vi＞，di＞.逐个扫描各子信息系统的中间结果，统计所有属性取值为Vi的中间结果个数，并记为di，输出简化后的＜＜P，Vi＞，di＞算法3 主算法输入:一个信息系统S=(U，A），其中U为论域，A为属性集.输出:该信息系统的一个最小约简.步骤1:将信息系统划分成若干子信息系统，令Red(A）=Φ，计算U/A.步骤2:在各子信息系统中，对于每个属性a∈A，执行Map函数和Reduce函数，生成所有的＜＜a，Vi＞，di＞，据此计算 a在 A中的重要度 SigA(a），选择SigA(a）值最大的属性a(若不唯一，任选其一）构成Red(A），即Red(A）={a}. 步骤3:判断SigA(Red(A））=1是否成立，若成立则此时的Red(A）为该信息系统一个约简，转Step5，否则执行Step4.步骤4:对于所有属性b∈A-Red(A），选择SigA(Red(A）∪{b}）值最大的属性b(若不唯一，任选其一），并将其添加至Red(A）中，即Red(A）=Red(A）∪{b}，转Step3.步骤5:若Red(A）⊆A且 SigA(Red(A））=1，则输出该信息系统的约简为Red(A），算法终止;若Red(A）=A且SigA(Red(A））＜1，则无法找到约简，算法也终止.3 实例分析下面，采用文献［8］中的信息系统(表1），本文将通过下述步骤来验证上述算法的有效性.其中，文献［8］得到的最小约简是{a3，a4}.表1 文献［8］中信息系统U a1 a2 a3 a4 x10000 x2 0 1 0 2 x3 1 1 0 1 x4 1 1 0 1 x50112图1 本文约简算法执行过程步骤1:数据分割阶段:将表1中信息系统进行数据分割，形成图1中两个子信息系统.步骤2:Map阶段.对于第1个子信息系统第1个对象x1，执行Map函数后，生成关于属性a1的中间结果＜＜a1，0＞，1＞，其余对象x2～x5生成过程类似.步骤3:Reduce阶段.将Map阶段输出的各中间结果进行归类合并，最终输出＜＜a1，0＞，3＞和＜＜a1，1＞，2＞.步骤4:主算法阶段.利用定义4，结合Reduce阶段输出的结果，计算a1在A中的重要度SigA(a1）=3/5，类似可求得其余属性的重要度，如图1所示;选择重要度最大者，由于SigA(a1）=SigA(a4），先令Red(A）={a1}.将其余属性与Red(A）分别组合，重新执行Map、Reduce和主算法等阶段，最终无法得到关于a1的约简.此时，重新令Red(A）={a4}，重复上述过程，最终形成约简{a3，a4}，与文献［8］的约简一致.4 结语传统的属性约简算法采用不同的方法以提高寻找最小约简的效率，但只适合处理小数据集.为了实现海量数据集的属性约简，本文深入分析各属性约简算法，通过融合MapReduce技术，提出了基于云计算的属性重要度约简算法.实例分析表明，该算法是可行的，并能有效地处理海量数据集.参考文献［1］Yao Y Y.Granular Computing basic issue and possible solutions ［C］.Proceedings of the 5th Joint Conference on In-formation Sciences，2000:186-189.［2］李秀红，史开泉.一种基于知识粒度的属性约简算法［J］.计算机应用，2006，26(6）:76-77.［3］张静，王建民，何华灿.基于属性相关性的属性约简新方法［J］.计算机工程与应用，2005，28:55-57.［4］陈玉明，苗夺谦，焦娜.基于二进制与粒计算的属性约简［J］.广西师范大学学报:自然科学版，2008，26(2）:81-84.［5］钱进，苗夺谦，张泽华.云计算环境下差别矩阵知识约简算法研究［J］.计算机科学，2011，38(8）:193-196.［6］钱进，苗夺谦，张泽华.云计算环境下知识约简算法［J］.计算机科学，2011，34(12）:2332-2342.［7］张文修，吴伟志，梁吉业，等.粗糙集理论与方法［M］.北京:科学出版社，2001:11-33.［8］梁吉业，曲开社，徐宗本.信息系统的属性约简［J］.系统工程理论与实践，2001，21(12）:76-80.［9］Liu Q.Research of resowing-problem in AI based on granular computing［J］.Computer Science，2003，30(5A）:11-12.［10］刘清，刘少辉，郑非.Rough逻辑及其在数据约简中的应用［J］.软件学报，2001，12(3）:415-418.。

一种基于属性度量的快速属性约简算法属性约简是数据挖掘中非常重要的一项任务，是数据预处理的关键步骤之一。

属性约简的目的是去除冗余的属性，提高数据集的可处理性和可解释性。

在现实数据集中，经常存在大量的属性，且这些属性有一定的相关性，因此必须找到一个方法来减少属性数量和保留最重要的属性。

目前，基于属性度量的快速属性约简算法是一种被广泛研究和应用的方法。

本篇文章将讨论一种基于属性度量的快速属性约简算法。

1. 引言：对于实际问题，往往会涉及大量的属性，但这些属性可能会影响到我们最终得到的结论。

因此，属性约简就成为了一种非常重要的技术。

在属性约简的过程中，一个重要的概念是属性依赖。

属性依赖是指某个属性能否通过其他属性推出，而不需要利用所有的属性。

2. 基于属性度量的快速属性约简算法：基于属性度量的快速属性约简算法通过计算属性的不确定性和相关度来实现属性的筛选。

该算法主要有以下几个步骤：（1）初始化：将每个属性放入一个C和D中，其中C是原始属性集合，D是属性依赖集合。

（2）消除无用属性：对于一个属性a，如果其对于D中所有属性都是无用的，即对于任意X ⊂ C，a ⊈ (X)，则a是一个无用属性。

（3）计算属性相关度：对于一个属性a，其相关度的计算公式如下：相关度(A,B) = | supp(A,B) - supp(~A,B) - supp(A,~B) +supp(~A,~B) |其中supp(A,B)表示数据集中同时包含属性A和B的记录的个数，~A表示某个属性A的补集，即不包含A的集合。

（4）选择最优属性：在C中选择相关度最高的属性a，并将其添加到S中，S表示最终被选择的属性。

然后从D中删除与a相关的属性依赖，即将D中所有形如a -> y的依赖项删除。

（5）重复步骤（2）至（4）直到所有的属性都被计算完。

3. 算法优点：（1）时间复杂度低：该算法采用了计算属性相关度的方法，避免了对于所有子集的枚举，因此算法的时间复杂度较低。