时间：2022-07-21 09:54:57
摘要:为了得到用户满意的文本特征约简,在粗集理论属性约简技术的基础上,提出文本特征选择的新方法RSUA。RSUA方法采用用于关联规则挖掘的Apriori算法的思想进行决策表的约简。实验验证了RSUA方法的有效性。
关键词:RSUA;粗糙集;Web
中图分类号:TP301文献标识码:A文章编号:1009-3044(2009)32-9052-02
Selece Eigenvectors Form Documents Based on Rough Set Reduction Algorithm
LI Hong-xia, YI Li-ping
(School of Computer, Jiangxi Aviation Vocational & Technical College, Nanchang 330024, China)
Abstract: The paper discuss a new method(RSUA) for selece eigenvectors form documents based on rough Set Reduction. It put forward a mining model of association rules with decision attributes based on Apriori.
Key words: RSUA; Rough Set; Web
网络的快速发展给人们带来大量信息,网页中最主要的信息资源是文本,WEB挖掘就是针对网上大量文本信息进行知识发现、知识表示的研究领域。由于构成文本的原始词汇量往往非常巨大,一般为几万甚至几十万,所以文本的原始特征项空间也非常巨大,这样大的特征空间对许多分类算法来说是很难处理的,在实际应用中系统运行速度也对特征空间的压缩提出了要求。对文本原始特征空间的压缩一般使用特征选择或特征提取方法。
文本挖掘的一个重要问题就是高维的特征空间,这些特征空间是由文本中的词或词组构成的,许多传统算法难处理。
1 算法的设计思想
关联规则是关联分析中的一种常见的技术,是寻找在同一个事件中出现的不同项的相关性。挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则。在利用粗糙集的决策表进行数据分析,决策属性的选取很重要,对一个问题当有多个影响因素时,通过关联规则得到一些符合最小支持度和最小可信度的一些规则,从中可以发现一些规则,这样可以根据决策规则的条件,作为粗糙集决策表的决策属性,利用粗糙集进行运算,得到这一决策属性的相关因素。
而利用粗糙集进行分析时,可以约简冗余属性,缩小考虑范围,同时验证或从另一角度对同一问题进行分析。另外,粗糙集可以处理含有不一致、噪声、不完备的数据,比关联规则具有更广的使用范围。粗糙集的约简中,将关联规则挖掘和粗糙集理论结合起来,引入关联规则中的支持度概念,并重新定义了这个概念。
在决策表DT中,t为条件属性,s为决策属性,规则t=>s的基数card(t=>s)称作规则t=>s的支持度,记为sup(t=>s);属性t的基数card(t)称作属性t的支持度,记为sup(t)。
假如一条规则t=>s的sup(t=>s)=sup(t),则称该规则是确定性规则;假如一条确定规则的支持度大于用户指定的最小支持度,称这条规则为强确定性规则。
这里主要讨论决策表中的强确定性规则,提出算法RSUR,该算法采用用于关联规则挖掘的Apriori算法的思想进行决策表的约简,即“频繁项集的所有非空子集都必须也是频繁的”,也就是:假如规则t=>s不是强的,则它的扩展tΛp=>s也不是强的。算法根据用户指定的最小支持度,利用Apriori性质删除低于最小支持度的规则,得到强确定的规则表。
2 算法的描述
算法RSUA的算法描述如下:
输入:决策表DT,最小支持度minup;
输出:所产生的规则集。
步骤一:对决策表进行属性约简;
步骤二:K赋值为1;
步骤三:计算候选集CK中每个属性的属性支持度和规则支持度;
步骤四:若规则支持度小于最小支持度,则将其从CK中删除;若该规则的属性支持度等于规则支持度,则将该规则移入规则集Pk;
步骤五:将CK扩展为CK+1,首先扫描CK,将CK中的每两项合成具有K+1个属性的候选项,插入CK+1中。接着检查CK+1中的每一项C,若C的K子集中有不在CK中的项,则将C删除;若C是不相容的,将C删除。最后得到CK+1,将K赋值为K+1;
步骤六:循环调用三至五步,直到CK为空;
步骤七:结束。
3 实验结果
为了验证RSUA算法的有效性,使用实验数据集测试RSUA算法。首先与传统决策表算法-最小值约简算法进行实验对比。表1的最左列是数据集的名称,第2,3栏分别是该数据集的实例个数和属性个数。
为进一步验证RSUA算法的有效性,与传统的基于区分距阵的约简算法进行实验对比。采用UCI机器学习数据库中的数据集举行测试。对该数据集中的11个决策表举行属性约简,结果如表2所示。
4 结束语
从表1和表2的约简结果中可以看出:
1) 算法RSUA数据集的规则约简率和数据约简率大于传统算法的学习结果。
2) 算法RSUA的运行时间一般大于传统算法的学习结果,在实例数据和属性较多的情况下,要花费更多的时间。这是由于算法RSUA采用了多次迭代的方法,并且所设计的数据结构较为复杂的缘故。
3) 采用不同的数据集进行同样的算法对比实验是,结果相差较大。说明文档的规范程度、文本分词算法的选择、文本结构化描述都会影响算法的执行结果。
4) 本算法在约简过程中保留了所有对用户有用的规则,它并不特别注重约简率的大小,而主要是面向实用系统的,因此约简率并非是最好的衡量算法的标准。
参考文献:
[1] 常犁云.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报,1999,10(11):1206-1211.
[2] Agrawal R,Imielinski T,Swami A.Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIGMOD Conference on Management of data,1993:207-216.
[3] Kryszkiewice M.Strong rules in large database[Z].
[4] Lin T Y. Rough set theory in very large database[C].In Procedding os CESA'96,Lille,1996,2,936-941.
[5] 朱雪龙.应用信息论基础[M].北京:清华大学出版社,2001.
[6] 史忠植.知识发现[M].清华大学出版,2002.
[7] 郭萌,王钰.数据挖掘与数据库知识发现:综述[J].模式识别与人工智能,1998,11(3).
[8] 陈栋.KDD研究现状及发展[J].计算机科学,1996,23(6).
[9] 张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].北京:科技出版社,2001.
[10] Pawlak Z.Rough sets:Theoretical aspects of Reasoning about Data[M].Dordrecht:Kluwer Acasemic Publishers,1991.
[11] Pawlak Z.Vagueness and uncertainty-Rough Set Prospective[J],Computational Intelligence,1995,11(2):227-232.
[12] 曾黄麟.粗糙集理论及应用_关于数据推理的新方法[M].重庆:重庆大学出版社,1996:61-82.
[13] 李水平.数据采掘技术回顾[J].小型微型计算机系统,1998,19(4).
[14] 铁治欣,陈奇,俞瑞钊.关联规则采掘综述[J].计算机应用研究,2000(1):1-5.