一种新的信息熵属性约简算法
- 格式：pdf
- 大小：294.99 KB
- 文档页数：4
万方数据
万方数据
１１０２００９．４５（３２）ＣｏｍｐｕｔｅｒＥ，ｔｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃｍｉｏｎｓ计算机工程与应用
ｔ＝ｌ；且＝协’Ｊｏ
ｆｏｒ（ｊ＝２，ｊ＜ｎ＋１Ｊ＋＋）
若任一ｃＩ∈Ｃ（ｉ＝Ｉ，２，…，ｓ）均有“∥，ｃ．）承而ｍｔＣｉ），则毋＝Ｂ，Ｕｋ’｝；
否ＩＡｔ］｛ｔ＝ｔ＋ｌ；Ｂｍ｛ｘｊ’ＩＩ；
Ｓｔｅｐ５：Ｕ’＝Ｄ；
ｆｏｒ（ｉ＝ｌ，ｉ＝ｔ＋ｌ，“十）
取出Ｂ．中的第—个对象并入Ｕ’并计算出ｒｅ（ｙ）；
４．２基ｆ信息熵的怏速属性约简算法
算法２基于信息熵的快速属性约简算法
输入：简化的决策表ｓ＝（Ｕ’，Ｃ，Ｄ，Ｖ，，），ｃ＝ｆｃ。
，ｃ２＇…，ｃｌｌ；
输出：属性约简Ｒ；
Ｓｔｅｐｌ：由算法１，求出：∥＝Ｑｌｒ，Ｘ２’，…，ｚ。
’）和Ｖｚ∈∥租ｃ（ｚ）；
Ｓｔｅｐ２：将Ｍ（１≤ｉ≤ｓ）从大到小进行快速排序得到：
Ｍ。
≥帆≥…≥帆，它们对应的属性为ＣｔｌｙＣ。
，……Ｃ令尺＝ｆｃ。
１】；ＲＦＤ；
Ｓｔｅｐ３：用基数排序的思想求出Ｕ７／Ｒ＝｛Ａ一．Ａｚ，…，＾ｃ｝；
ｓｔｅｐ４：对每一Ａ产‰，ｘｊ２，…，纠ＥＵ’／Ｒ，（１句≤￡）
ｆｏｒ（ｈ＝ｌ；＾＜ｒ；＾＋＋）
ｇｒ（ｇ＝ｈ＋ｌ；ｇ＜ｒ＋ｌ；ｇ＋＋）
ｊｆ（脚（和）≠脚（‰））
则将（研，靠，并入Ｒｃ中；
Ｓｔｅｐ５：ｆｏｒ（ｋ＝２；ｋ＜ｓ＋ｌ：☆＋＋）
｛
ｉ“尺ｃ：Ｄ）算法终止；
ｅｌｓｅＲ＝Ｒｕ｛ｃｔｌ；
对Ｒ。
中任一区分对象对☆．，ｊ．＞
ｉｆ抓‰Ｃｔ），钒毛，Ｃｍ））
Ｒｃ＝Ｒｃ－｛＜ｘｈ，舻ｌ；
ｌ
算法２的复杂度分析：第１步的时间复杂度由算法１知为０（ＩＣＩＩＵＩ）；第２步的时间复杂度为０（ＩＣＩｌｏｇｌＣＩ）；第３步的时间复杂度是０（ＩｃＩＩＵ’／ＣＩ）；第４步的时间复杂度是０（ＩＡｌｌ２＋ＩＡ２１２＋…＋ｌＡＬ１２）≤０（（ＩＡｌＩ＋ＩＡ２Ｉ＋…＋Ｍ￡Ｉ）２）＝０（ＩＵ’／ＣＩ）２；第５步的每一次循环最坏的时间复杂度为Ｏ（Ｉ尺ｃ－ｆ。
ｌＩ），最多循环ＩｃＩ—１次，故第５步最坏的时间复杂度为０（ＩＣＩＩＲｃ．１。
ｌＩ），由第４步知Ｏ（ＩＲｃ－ｈ｝Ｉ）≤０（ＩＡｌｌ２＋ＩＡ２１２＋－．・＋Ｌ４￡１２），从而第５步最坏的时｜．日Ｊ复杂度为Ｏ（ＩＯ（ｂ４。
阿Ｌ４：１２＋…＋ＭＬ１２））；由于ＩｃＩ远远小于Ｉ明，故算法２的时｜’日Ｊ复杂度为Ｏ（ＩＣｌｌＵｌ）＋ｏ（ｉｃｌ（Ｌ４．Ｆ＋ＩＡ：１２＋…＋ＩＡＬＰ））≤０（ＩＣＩＩＵＩ）＋Ｏ（ＩＣＩＩＵ／ＣＩ）：。
算法２第１步的空间复杂度为０（１Ｍ）；第２步的空Ｉ’日Ｊ复杂度为Ｏ（ｉｏｇｌＣＩ）；第３步最坏的空Ｉ’日Ｊ复杂度为ｏ（Ｉｕ’Ｉ）；第４步最坏的空Ｉ＇日Ｊ复杂度为Ｏ（ＩＵ／ＣＩ）２；第５步最坏的空间复杂度为０（Ⅱｈ．Ｊ），故算法２的空间复杂度为０（Ｍ）＋ｏ（ｕｂ．Ｊ）≤Ｏ（１Ｍ）＋Ｏ（Ｉ叫Ｃ１）２。
５实例分析
为了更好地说明新算法的高效性，以文献［１０１中的决策表１为例来说明新算法。
对决策表ｌ的１５个对象ｕ，利用算法１得到：
Ｕ’＝Ⅸｌ。
Ｘ２，Ｘ８，Ｘ４，Ｘ６，Ｘ７，Ｘ１３ｌ
“，Ｄ＝“Ｘｌ，Ｘ３，Ｘ４ｌ，｛Ｘ２，Ｘ５，Ｘ８，Ｘ１２，Ｘ１３ｌ，
｛Ｘ６，Ｘ７，Ｘｌｏ，Ｘ１１’Ｘ１５），ｌＸ９，Ｘ１４ＩＩ＝
｛Ｄｒ，Ｄ２，Ｄ３，Ｏ，Ｉ
由概率分配函数可得№（ｔ）：
脚（Ｘ１）＝（１，０，０，０）；№（爿２）＝（０，１，０，０）；
№（Ｘ４）＝（１，０，０，０）；触（Ｘ６）＝（０，０，２１３，１１３）；
№（Ｘ７）＝（０，０，２／３，１／３）；№（Ｘ８）＝（０，１，Ｏ，０）；
舭（Ｘ１３）＝（０，１／２，１／２，０）
得到简化的决策表如表２所示。
表２表１的简化决策表
由算法２的第２步，得到肘。
－－４，Ｍｚ＝３，尬－－４，眠＝２，从而尬≥肌≥Ｍ２≥眠，对应的属性序为ｎ，ｃ，ｂ，口！；选出属性８作为属性约简的第—个属性，则有Ｒ＝ｆｏｌ；尺ｃ＝０；由算法２的第３步得到：Ｕ’／｛ａｌ＝｛ｌＸ。
，Ｘ，｝，ｆＸ：，Ｘ４，Ｘ。
），｛Ｘ。
｝，Ⅸ。
，｝ｌ；由算法２的第４步得到Ｒ产｛＜ｘｌ，Ｘ７＞，＜ｘ２，Ｘ４＞，ｄＢ，ｘ４＞｝；由算法２的第５步得到：由于Ｒｃ≠０，选出ｃ，得到尺＝恤，Ｃ｝，从而尺ｃ＝｛“２，ｘ。
＞｝；由于Ｒ。
≠Ｄ，故选出ｂ，得到｜Ｒ＝Ｉｏ，Ｃ，ｂｌ，从而有尺ｃ＝Ｄ，算法终止，从而属性约简为：Ｒ＝（口，ｂ，ｃｌ。
若用文献『８】中的算法所求得的二进制差别矩阵是１０５个记录，再用其算法中的变换，使计算量大大增加。
而该新算法只需计算４个即口丁，从而能节省大量的计算时间和存储空间。
因此该新算法是一个高效的属性约简算法。
６结束语
为有效地降低基于信息熵的属性约简算法的复杂度，在简化决策表的基础上，给出了区分对象对集和基于区分对象对集的属性约简的定义，并证明了该定义与基于信息熵的属性约简的定义是等价的。
在此基础上，利用区分对象对和属性约简的关系，并结合差别矩阵的思想．设计了一个高效的信息熵属性约简算法，并分析了该算法的时间复杂度和空间复杂度，它们分别为Ｏ（ＩＣＩＩＵｌ）＋０（ＩＣＩＩＵＩＣｌ２）和０（ＩＵ／Ｃ１２）＋０（（，），与文献『４—５１的算法相比，该算法的时Ｉ’日Ｊ复杂度和空｜’日Ｊ复杂度都较低，故该文给出的算法是—个较好的信息熵属性约简算法。
这一算法的设计思想也为求其他不『司的属性约简算法提供了一种新的思路，这也是下一步的研究工作。
参考文献：
【１】ＰａｗｌａｋＺ，ＳｋｏｗｒｏｎＡ．Ｒｕｄｉｍｅｎｔｓｏｆｍｕｇｌｌ∞埘Ｊ１．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，２００７．１１７（Ｉ）：３－３７．
（下转１１３页）一～一～～一～一～
万方数据
万方数据。
