论文研究-一种基于决策信息系统的知识约简算法.pdf

所需积分/C币:9 2019-09-07 14:28:42 507KB .PDF

差别矩阵方法作为求解粗糙集知识约简的关键技术之一,而差别矩阵中的元素个数将直接影响知识约简算法的计算效率,针对现有基于差别矩阵方法的知识约简算法的不足,并且当决策信息系统中样本量较大、决策类别数较少时,算法构造的差别矩阵中将存在大量空值元素。提出了一种新的差别矩阵构造方法,有效地剔除了差别矩阵中的空值元素,在此基础上,设计了一种决策信息系统的知识约简算法,由于算法能有效地利用核属性,进一步缩小了知识约简算法的效率,并通过算例分析说明了算法的可行性。
胡秦斌:一种基于决策信息系统的知识约简算法 2013,49(16)135 步骤2假定求得决策类为UD={D,D2…,D}识约简算法能够得到与同类算法的相同约简集,由丁本文 for(i=l; i<UID; i++) 算法省略了许多不必要的计算过程,从而具有更高的计算 for(j=i;}≤| 效率 根据决策属性值构造差别矩阵 if(x∈D,Ay∈D) 4算例分析 for(k=1;k≤C;k++) 为了进一步更好地说明本文所提出算法的可行性和 if((x,e)≠f(,C) 有效性,下面以文献[5]中实倒为例进行了详细分析,其中 m(x,y)=m(x,y)UCk; U={x1,x2…,xs}为非室对象集,C={Size,Hair,Eyes,Com plexion}为条件属性集,并分别用{c,c2,c3c4}裘示,决策 步骤3if(m(x,y)∈M==1Ac1∈m(x,y) 属性集为{}。 {Red=RedU{cr};∥c;为核属性 表1决策信息系统 并将差别矩阵M中内含属性c1的矩阵元素 剔除 0 lall 步骤4 while(m(x,y)∈M≠) Tall {对于vc∈C-Red,计算差别矩阵M屮各属 Natt Tall d 性的频度f(ck Tall pale 选择满足属性c=max{f(c)} matt 若存在多个这样的属性,则仟选取一个; dark brown Red-RedUc; 若根据文献[12-14中算法对差别矩阵的构造,将得到 将差別矩阵M中内含属性c的矩阵元素剔除;如表2所示的差距矩阵。从表2中的差别矩阵元素可以看 出,差别矩阵中产生了大量的空值元素,浪费了大量的存 步骤5输出决策信息系统的知识约简Red; 储空问。而造成空值元素存在的原因是由于只有相同决 算法步骤1的最坏时间复杂度为O(U,步骒2的最策属性值的对象两两比较的结果,这些元素是尤需存储 D-1|D 坏时间复杂度为O(C∑∑DD;步骤3的最坏时的。为此,首先根据本文算法的步骤1,先根据决策属性值 =1f=1+1 对决策信息系统中的对象进行划分,从而求解出决策类 UID CiD-I U:DI 间复杂度为0∑∑|D1D+OC∑∑DDD;步D={xx,xx2xx,x,x,然后根据算法的步骤 2,可求解出压缩后的差别矩阵,见表3所示。 骤4的最坏时问复杂度为Oc∑∑DDD;步骤5 由表3中的差别知阵及定义7可知,此时{c2}为单个元 素,即为核属性,根掂算法的步骤3,可知属性c,是知识约 的最坏时间复杂度为O();所以新算法的时间复杂度为简的候选属性Red={e2},同时删除差别矩阵中包含属性c OCDD)。可知算法的空间复杂度为的矩阵元素,见表4所示;再根据算法的步骤,可计算出其 他属性出现的频度为∫(c1)=2,f(-)=4,f(cn)=4;选择 O( ID- 5 IDIJID,D。对于一致的决策信息系统面言,文满足c=。m(),由于存在多个属性同时满足条 献[12-14]中知识约简算法的时间复杂度和空间复杂度分件,则选取属性c23,则删除差别矩阵中包含属性c3的矩阵 别为OCU)和O(CU)。综上分析,本文所提出的知元素,此时差别矩阼为空,算法结束,知识约简Red={c2,c2}。 表2原差别矩阵 {e2,c;}{c,e2} (c,,ct, Ca cI, C,,C, Cal 136 013,49(16) Computer Engineering and Applications计算机工程与应用 表3压缩后的差别知阵 Science,2007,117(1):3-37. 3」常犁公,王国胤,吴渝一种基于 Rough set理论的属性约简及 {,c}{r,c}{c,2,(3,ca}{c3,ca} 规则提取方法.软件学报,1999,10(11):1206-1211. 1C:, x12,c,.}te,e,c}te}te.,ch}e,e,ce,c}H4张绍兵,季厌浮基于粗糙集和神经网络里论的规则提取算法[ {c3,C4}{c1,C2,ta}{ce2} 计算机工程与应用,2008,44(24):145-147 15」鄂旭、邵良杉,张毅智,等一种基于粗糙集理论的规则提取方 表4删除含核属性后的差别矩阵 法小计算机科学,201,38(1):232-235. 16」徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max{OC|U} {C1,C3,c4 C O(CHU!C)的快速属性约简算法[J计算机学报,2006,29 x C.c (3):391-399 [7]蒋瑜,刘胤田,李超基于 Bucket sort的快速属性约简算法[J 5结束语 控制与决策,2011,26(2):207-212. 差别矩阵方法作为知识约简的经典方法之一,目前利8]F国胤,于洪杨大春基于条作信息熵的决策表约简门计算 用差别矩阵方法求解知识约简算法具有较高的时间和空 机学报,2002,25(7):759-76 间复杂度,当决策信息系统的样本量较大决策类别较少]亩夺兼,陈玉明,王睿智,等图表示下的知识约简门电子学 时,差别矩阵所需的存储空间和计算量都会显著增加,导 报,2010,38(8):1952-1957 致算法计算效率较低,从而限制了差别矩阵方法的工程应10 omron, auster. c dIscernibilIty matrices and Tunc 用,所以如何压缩差别矩阼的元素对方法的实际应用非常 tion in Information systems[C]Slowinski R Intelligent De 重要,为此,本文提出了一种针对决策信息系统的差别知 cision Support Handbook of Applications and Advances 阵的压缩构造方法,利用汏策属性值的划分对差別矩阵的 of the rough Scts Thcory, 1992: 331-362 构造过程进行了改进,并利用属性的频度作为启发信息, [11] Hu X H, Ccrconc N L canning in relational databases: a roug sct approach[]. Computational Intclligencc, 1995, 11(2) 提出一种有效的知识约简算法。通过算法的实例分析来 323-337 看,消除了构造差别矩阵过程中的大量空值元素,使得压 [12] Wang J, Wang I Rcduction algorithms bascd on discernibility 缩后的差別矩阵的规模显著小于原差别矩阵的规模,有效 matrix: Thc ordered attributes mcthod J]Journal of Computcr 省略了求解空值元素所需的计算时问和存储消耗,同时, Scicncc Tcchnology, 2001,16(6): 489-504 世为知识约简过程节省了大量的计算时间,并从理论上详13]高学东,丁军基于简化差别矩阵的属性约简算法[系统工 细分析算法的时间复杂度和空间复杂度。 程理论与实践,2006,25(6):101-107 [14] Yao YY, Zhao YDiscernibility matrix simplification for 参考文献 constructing attribute reducts[J]. Information Scicnccs, 2009. [1 Pawlak Z Rough sets[J]. International Journal of Computer and 179:867-882 Information Science, 1982, 11(5): 341-356 5]程玉胜,张佑生,胡学钢两类决策系统中规则获取的联合决 [2 Pawlak Z, Skowron A Rudiments of rough sets[J]. Information 策矩阵算法叮系统工程理论与实践,2008,28(6):137-142. (上接120页) 社,2007:5-6. 2」刘靖明,韩丽川,侯立文基于粒了群的K均值聚类算法J.系 6结束语 统工程理论与实践,2005(6):54-58. 本文针对ACO-K- Imeans的随着数据容量的增加聚类所31刘星,毕奇龙郑付刚基于蚁群k均值聚类算法的边坡稳定性 消菥的时间也同时会成倍增长的缺陷,提出了利用 Mapreduce 分析[小水电能源科学,2010,28(8):108-109 将ACOK- neans并行化的方法,以提高ACO-k- Ineans处 [4 Ngazimbi M. Data clustering using mapreduce[D]. Idaho: Bosie 理大容量数据的计算效率,实验结果表明,基于 Mapreduce State University, 2009 的并行 ACO-K-means具有良好的加速比和扩展性。随着s]段海滨蚁群算法原理及其应用M]北京:科学出版社,2005 当今数据爆炸性的增长,在云计算平台上利用 Mapreduce 50-52 并行模型实现数据挖掘算法是县有现实意义的。在以后[6春花,特日格勒,任哲明基于蚁样算法的参数设置研究内蒙 的研究中,将对 DBSCAN等聚类算法的并行化进行研究。 古民族大学学报:自然科学版,2011(7):402-404 [7 Dean J, Ghemawat SMapReduce: simplified data 参考文献: Largeclusters[j].communicatIonsoftheAcm.2005,51(1): [1韩家炜,堪博数据挖掘概念与技术M].北京:机械工业出版 107-113

...展开详情
试读 4P 论文研究-一种基于决策信息系统的知识约简算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-一种基于决策信息系统的知识约简算法.pdf 9积分/C币 立即下载
    1/4
    论文研究-一种基于决策信息系统的知识约简算法.pdf第1页
    论文研究-一种基于决策信息系统的知识约简算法.pdf第2页

    试读已结束,剩余2页未读...

    9积分/C币 立即下载 >