论文部分内容阅读
摘 要：经典的基于辨识矩阵的属性约简快速算法在非协调决策系统上不能有效地得到约简，针对该问题，提出一种新的辨识矩阵快速约简方法，有效地解决了该问题。利用标准UCI数据集模拟实验，与经典方法相比，进一步减少了属性的个数，凸显其有效性和可靠性。
关键词：辨识矩阵；属性约简；决策系统；特征选择
中图分类号：TP301.6
属性约简是机器学习和人工智能最重要的研究方向之一[1，2]，其作用在于消除冗余的列，从而获得更精简的数据。目前，这方面出现了许多优秀的结果，譬如基于属性依赖度的选择方法[3，4]，利用互信息进行属性约简的方法[5]，采用模糊粗糙集进行约简[6]等。随着辨识矩阵和辨识函数概念的提出，利用辨识矩阵和辨识函数实现了属性约简，并得到了广泛的研究[7-9]。然而，非协调决策系统的经典的辨识矩阵贪心算法会陷入局部最优解，因此，需要做进一步的研究。
1 非协调决策系统的经典辨识矩阵贪心算法及其缺点
给定非协调决策系统IDS=（U，C∩D，V，f），其辨识矩阵定义为：
M=（M（x，y）），
其中M（x，y）定义为
显然，矩阵中元素是由处于不同决策类中的对象和属性值不同的属性组成。
基于辨识矩阵属性频率的属性约简贪心算法，根据属性在辨识矩阵里出现的频率作为衡量属性重要程度的依据。这意味着，属性出现的次数越高，我们认识其越重要。基于辨别矩阵属性频率属性约简的贪心算法如下：
算法1：基于辨识矩阵属性频率的非协调决策系统属性约简的贪心算法
输入： IDS=（U，C∩D，V，f）
输出： red
（1）计算M；
（2）若M=0，返回red；
（3）对所有a∈C- red，计算a的频率；
（4）选择最大频率的属性，red = red ∩{ax}，令M中包含ax的元素为0；
（5）如果M为0矩阵，返回red；否则转第3步。
该算法属性选择有两个循环，时间复杂度为O（丨C丨2），另外计算单个属性的频率的时间复杂度为O（丨U丨），因此该算法总的时间复杂度为：O（丨U丨丨C丨2）。
例1：给定非协调决策系统IIS=（U.C∪D，V，f）如表1，其中C={a，b，c，d，e}是条件属性，D是决策属性。
表1 非协调决策系统
很容易验证该系统是非协调决策系统。而利用快速算法1，求得的结果是{e，a，b，d}，然而{e，a，b，d}不是约简，这是一个局部最优解，因此经典算法不能有效地计算出约简，导致结果仍然有一定的冗余性。本文提出一种新的属性约简方法来解决此问题。
2 适用非协调决策系统的改进的辨识矩阵属性约简算法
因为贪心算法容易陷入局部最优解，因此基于辨识矩阵的属性约简贪心算法也会陷入局部最优解。另一方面，因为在算法中，一旦选择了一个属性，则将它及已选好的子集中能够区分对象的辨识矩阵元素都删除，而不能用这些属性区分该对象的元素并不删除，所以并不会带来数据分类精度的损失。那么只会导致结果中存在冗余。因此，针对该情况，我们提出一种可以有效避免冗余的辨识矩阵属性约简快速算法。
算法2：改进的基于辨识矩阵的非协调决策系统的属性约简快速算法
输入： IDS=（U，C∩D，V，f）
输出： red
（1）根据red，计算辨识矩阵M；
（2）如果M=0，转第6步；
（3）对所有a∈C-red，计算a的频率；
（4）选择最大频率的属性ax，red=red∪{ax}，令M中包含ax的元素为0；
（5）如果M不为0矩阵，转第3步；
（6）对a∈red，如果νred（D）=νred-a（D），那么red=red-{ax}；
（7）返回red；
显然，算法2与算法1具有相同的时间复杂度。
例2：继续例1，利用算法2，可以得到约简red={e，a，d}。因此，相对于经典算法，算法2有效地获得了约简。该算法能够避免陷入局部最优解。
3 结论
本文提出了一种适用于非协调决策系统的辨识矩阵属性约简快速算法，该算法能够解决经典贪心算法陷入局部最优问题，也能消除所带来的冗余，有效的得到了约简。实例分析显示了其有效性和实用性。
參考文献：
[1]张文修，吴伟志，梁吉业.粗糙集理论与方法[M].北京：科学出版社，2001：5-7.
[2]PawlakZ.Roughsets[J].InternationalJournalofComputerandInformationSciences，1982，11：341-356.
[3]李克文，吴孟达，张雄明.约简的一种启发式算法[J].计算机工程与科学，2004，26（1）：92-94.
[4]王天江，晏伟峰，漆志旺.一种基于RoughSet的启发式属性约简算法[J].计算机工程与科学，2007，29（2）：86-88.
[5]R.Bhatt，M.Gopal.Onfuzzy-roughsetsapproachtofeatureselection[J].PatternRecognitionLetters，2004，26（7）：965-975.
[6]朱江华，李海波，潘丰.基于遗传算法和模糊粗糙集的知识约简[J].计算机仿真，2007，24（1）：86-89.
[7]王柯，朱启兵.一种基于差别矩阵的启发式属性约简算法[J].计算机工程与科学，2008，30（6）：73-75.
[8]任小康，吴尚智，马如云.基于可辨识矩阵的属性频率约简算法[J].兰州大学学报，2007，43（1）：138-140.
[9]龙鹏飞，蔡翱鹏，陈曦.基于遗传算法和区分矩阵的属性约简[J].计算机工程与科学，2010，32（11）：104-106.
作者单位：临沂大学信息学院，山东临沂 276005
关键词：辨识矩阵；属性约简；决策系统；特征选择
中图分类号：TP301.6
属性约简是机器学习和人工智能最重要的研究方向之一[1，2]，其作用在于消除冗余的列，从而获得更精简的数据。目前，这方面出现了许多优秀的结果，譬如基于属性依赖度的选择方法[3，4]，利用互信息进行属性约简的方法[5]，采用模糊粗糙集进行约简[6]等。随着辨识矩阵和辨识函数概念的提出，利用辨识矩阵和辨识函数实现了属性约简，并得到了广泛的研究[7-9]。然而，非协调决策系统的经典的辨识矩阵贪心算法会陷入局部最优解，因此，需要做进一步的研究。
1 非协调决策系统的经典辨识矩阵贪心算法及其缺点
给定非协调决策系统IDS=（U，C∩D，V，f），其辨识矩阵定义为：
M=（M（x，y）），
其中M（x，y）定义为
显然，矩阵中元素是由处于不同决策类中的对象和属性值不同的属性组成。
基于辨识矩阵属性频率的属性约简贪心算法，根据属性在辨识矩阵里出现的频率作为衡量属性重要程度的依据。这意味着，属性出现的次数越高，我们认识其越重要。基于辨别矩阵属性频率属性约简的贪心算法如下：
算法1：基于辨识矩阵属性频率的非协调决策系统属性约简的贪心算法
输入： IDS=（U，C∩D，V，f）
输出： red
（1）计算M；
（2）若M=0，返回red；
（3）对所有a∈C- red，计算a的频率；
（4）选择最大频率的属性，red = red ∩{ax}，令M中包含ax的元素为0；
（5）如果M为0矩阵，返回red；否则转第3步。
该算法属性选择有两个循环，时间复杂度为O（丨C丨2），另外计算单个属性的频率的时间复杂度为O（丨U丨），因此该算法总的时间复杂度为：O（丨U丨丨C丨2）。
例1：给定非协调决策系统IIS=（U.C∪D，V，f）如表1，其中C={a，b，c，d，e}是条件属性，D是决策属性。
表1 非协调决策系统
很容易验证该系统是非协调决策系统。而利用快速算法1，求得的结果是{e，a，b，d}，然而{e，a，b，d}不是约简，这是一个局部最优解，因此经典算法不能有效地计算出约简，导致结果仍然有一定的冗余性。本文提出一种新的属性约简方法来解决此问题。
2 适用非协调决策系统的改进的辨识矩阵属性约简算法
因为贪心算法容易陷入局部最优解，因此基于辨识矩阵的属性约简贪心算法也会陷入局部最优解。另一方面，因为在算法中，一旦选择了一个属性，则将它及已选好的子集中能够区分对象的辨识矩阵元素都删除，而不能用这些属性区分该对象的元素并不删除，所以并不会带来数据分类精度的损失。那么只会导致结果中存在冗余。因此，针对该情况，我们提出一种可以有效避免冗余的辨识矩阵属性约简快速算法。
算法2：改进的基于辨识矩阵的非协调决策系统的属性约简快速算法
输入： IDS=（U，C∩D，V，f）
输出： red
（1）根据red，计算辨识矩阵M；
（2）如果M=0，转第6步；
（3）对所有a∈C-red，计算a的频率；
（4）选择最大频率的属性ax，red=red∪{ax}，令M中包含ax的元素为0；
（5）如果M不为0矩阵，转第3步；
（6）对a∈red，如果νred（D）=νred-a（D），那么red=red-{ax}；
（7）返回red；
显然，算法2与算法1具有相同的时间复杂度。
例2：继续例1，利用算法2，可以得到约简red={e，a，d}。因此，相对于经典算法，算法2有效地获得了约简。该算法能够避免陷入局部最优解。
3 结论
本文提出了一种适用于非协调决策系统的辨识矩阵属性约简快速算法，该算法能够解决经典贪心算法陷入局部最优问题，也能消除所带来的冗余，有效的得到了约简。实例分析显示了其有效性和实用性。
參考文献：
[1]张文修，吴伟志，梁吉业.粗糙集理论与方法[M].北京：科学出版社，2001：5-7.
[2]PawlakZ.Roughsets[J].InternationalJournalofComputerandInformationSciences，1982，11：341-356.
[3]李克文，吴孟达，张雄明.约简的一种启发式算法[J].计算机工程与科学，2004，26（1）：92-94.
[4]王天江，晏伟峰，漆志旺.一种基于RoughSet的启发式属性约简算法[J].计算机工程与科学，2007，29（2）：86-88.
[5]R.Bhatt，M.Gopal.Onfuzzy-roughsetsapproachtofeatureselection[J].PatternRecognitionLetters，2004，26（7）：965-975.
[6]朱江华，李海波，潘丰.基于遗传算法和模糊粗糙集的知识约简[J].计算机仿真，2007，24（1）：86-89.
[7]王柯，朱启兵.一种基于差别矩阵的启发式属性约简算法[J].计算机工程与科学，2008，30（6）：73-75.
[8]任小康，吴尚智，马如云.基于可辨识矩阵的属性频率约简算法[J].兰州大学学报，2007，43（1）：138-140.
[9]龙鹏飞，蔡翱鹏，陈曦.基于遗传算法和区分矩阵的属性约简[J].计算机工程与科学，2010，32（11）：104-106.
作者单位：临沂大学信息学院，山东临沂 276005