文摘

最小属性约简的目的是找到的最小子集的条件属性集这样分类质量一样吗。这个问题是众所周知的赋权。当只有一个最小属性约简是必需的,它变成了一个非线性约束组合优化问题在逻辑空间和一些启发式搜索方法。在这种情况下,适应度函数是这个问题的关键之一。它要求适应度函数必须满足最优解之间的等价性和最小属性约简。不幸的是,现有的健身功能不符合等价,或过于复杂。在本文中,一个简单的基于正域和更好的适应度函数。理论证明表明,最优解等于最小属性约简。实验结果表明,提出的适应度函数比现有的适应度函数为每个算法在测试。

1。介绍

对于一个给定的数据集,属性约简是粗糙集理论的一个基本问题,提出pswlak和Sowinski1]。形式上,它是一个非线性约束的组合优化问题,其目标函数是一个候选子集的大小的属性和约束,代表的分类质量的属性子集,由一个属性约简条件得到满足。如图所示,2),这个问题已经被证明是np难。

为了克服这个问题,许多策略必须考虑文献在过去的二十年。一般来说,有两种类型的最小属性约简的类别:贪婪的(或爬山)类别和随机类别。贪婪的类别通常采用粗糙集属性作为启发式知识意义。它开始与空集或属性核心,然后采用选择向前或向后消除。胡锦涛和Cercone给减少算法使用积极的提出属性重要性作为引导启发式(3]。王等人开发一个条件信息entropy-based还原算法,使用条件entropy-based属性意义(4]。胡等人计算的意义属性利用差别矩阵的启发式思想和提出一个启发式约简算法5]。Susmaga认为不可辨认性和分辨率的关系在属性约简6]。这些类别是快但不能保证找到最优或最小的减少。

一些研究人员使用随机粗糙集属性约简的方法。这些类别是优化方法。它有一个更高的概率比第一类找到最小约简。Wroblewski结合了遗传算法和贪婪算法来生成短的权值。然而,它使用高耗时的操作,不能保证结果真的是一个约简子集(7]。以Wroblewski的工作为基础,Bjorvand和科莫罗夫斯基应用遗传算法计算近似权值(8]。算法使一些变化和实际改进速度和质量的近似。原因生成算法基于遗传算法的粗糙集属性约简非常有效(9]。

但粗糙集只能处理离散属性。一种离散化的方法提出了基于粒子群优化(PSO) (10]。把这项工作作为基础,粗糙集的知识约简算法,提出了基于粒子群优化(11]。该算法可以解决现有启发式算法不能解决的一些问题。为了提高算法的效率,许多学者不断提高和更新这些算法。Santana-Quintero路易斯等人提出一个多目标进化算法的混合粒子群优化方法和粗糙集理论中的一些概念(12]。的方法的主要思想是将粒子群优化算法的收敛率高的基于粗糙集的局部搜索方法就是能传播nondominated找到解决方案。在那之后,两步粒子群优化解决特征选择问题是由贝罗等人在13]。改进的算法是一个方法,可以提高搜索效率。气等人提出了一个基于量子PSO算法连续属性离散化方法(14]。谢长廷和Horng提出了基于异步离散算法的特征选择方法搜索算法(15]。此外,其他随机算法被用来属性约简,例如,蚁群算法(ACO) [16)和支持向量机(SVR) [17]。

系统最优或最小子集是必需的,可以使用随机类别。在这种情况下,这个问题转化为一个问题找到一个最大(或最小)值的适应度函数,然后一些随机优化方法应用于解决健康最大化或最小化的问题。一种常见方法将约束优化问题转化为一个无约束健身优化问题是使用惩罚的方法(18]。这样的方法,设计一个更好的适应度函数是最重要的工作。获得良好的性能,健身的健身功能应符合要求的评估候选人的适当解决方案和最优等效得到保证。在这里,最优等效意味着健康最大化问题的最优解对应于最小属性约简。不幸的是,现有的健身功能不满足上述要求,因此影响相关算法的性能(19]。

本文提出了一个适用的适应度函数。与现有的健身功能如前所述,它不仅考虑较少的因素,也克服了缺点。实验结果表明,对于每一个测试的两个算法,使用提出的适应度函数的概率找到最低减少高于函数的使用提出了(19]。

剩下的纸是组织如下。部分2提出了一些关于最小属性约简的概念,回顾和分析了适应度函数提出了(19]。节3,一个新的适应度函数和属性。节4,实验的结果和比较分析。最后,部分5总结了纸。

2。基本概念和相关的工作

在本节中,我们将回顾一些粗糙集理论的基本概念,必要的最小属性约简问题的描述。

可以表示为一个决策表,在那里是一个非空的有限集合的对象,,在那里是一组属性和条件是一个决策属性集,域的属性属于吗,分配对象的属性值是一个函数。

与任何,有一个不可辨认性相关关系:

让;的-减少近似的被定义为,在那里表示的等价类由对象。的符号指的是阳性区域由。的光纤质量相对于决策属性集被定义为。

对决策表,它可能有很多属性减少;减少被定义为的集合

属性约简的最小属性约简以最小基数将搜索。最小属性约简问题可以制定如下非线性组合优化问题:

让是一组被定义如下:

的定义,下面的命题是明显的。

命题1。让;然后优化问题的最优解(3)当且仅当。

根据命题1每个元素的对应于一个最小的减少。为了解决问题(3),最常用的方法是将其转换为无约束最大化问题,通过启发式算法来解决: 在哪里适应度函数是关于属性子集。

对于这个优化问题,等价之间的最优最小属性约简问题(3)和健身功能的最大化必须保证。不幸的是,大多数功能不满足要求的文献[19]。

例如,你们等人定义适应度函数(19]。让 等价类的基数在哪里满足,在那里表示基数函数被定义为一组 在哪里。

让,,;然后和,因此。如果,然后。它表明,适应度函数不能区分这两个概念。也就是说,这两个算法运行时是等价的。这个缺点将减少算法的性能。此外,在实际应用中,因为包含分类质量的值函数不是一个整数。在搜索过程中,计算误差减少将降低搜索的概率最低。最后,决策表的一致性计算之前必须确定健身价值,这就增加了计算复杂度。

3所示。一个新的函数及其属性

在本节中,我们提出一个新的适应度函数。首先,介绍了相关定义如下。

定义2。让。如果成立,那么据说是一致的吗。让是一组包括的所有组一致(19]:

通过减少的定义,任何组一致,本身是一种减少或包含减少。如果是最小的,那么是一个减少。这是非常明显的。与一个非线性约束的组合优化问题被定义为

让是一组定义如下:

的定义,我们知道是的一个子集和下面的命题明显。

命题3。 ,然后是减少的。

命题4。让;然后当且仅当优化问题的最优解(9)。

由命题4,优化问题的解集(9)。根据前面的定义,提出了一种新的适应度函数如下:, 在哪里。

命题5。让。
如果,然后。
如果,然后。
特别是,。

证明。如果,,然后和。这是根据适应度函数的定义。的是举行。如果,然后,从而。

根据命题5域的功能可以分成两个不相交的集和,在那里和的最小和最大价值,分别。通过函数的缺陷,提出了(19)是可以避免的。最小优化问题定义如下的定义:

定理6。让;然后当且仅当是一个最小属性约简;也就是说,。

证明。 ;然后减少由命题吗3。如果不是一个最小属性约简,然后有一个最小属性约简这样。
另一方面,是一个属性约简,然后呢。的定义和,,一个矛盾,反之亦然。

由定理6的所有元素最小属性约简;然后根据命题4,我们可以得到所有优化问题的解决方案(9减少)的最小属性。

定理7。 ,然后是一个优化问题的最优解(12)。它相当于情况的所有元素优化问题的最优解(12)。

证明。我们用反证法。假设有一个这样不是一个优化问题的最优解(12)。然后这样。所以 然后,有两种情况这将在下面讨论。
如果,然后,所以和。自,从而。因此 一个矛盾。
如果,然后;也就是说,,然后 一个矛盾。

从上面我们知道的所有元素的证据优化问题的最优解(12);也就是说,最小属性约简是优化问题的最优解(12)。

定理8。让;如果是一个优化问题的最优解(12),然后。

证明。 。
如果,然后。对所有,。自是一个优化问题的最优解(12),然后,所以 一个矛盾,所以。
。
如果,让。根据我们知道,所以,然后 一个矛盾,所以。

根据定理8优化问题的最优解(12)是一个最小属性约简。然后,通过定理7和8显然,我们可以获得以下定理。

定理9。让;然后是一个优化问题的最优解(12)当且仅当。

由定理9,我们可以得到优化问题的最优解(12)相当于最小属性约简。然后,根据定理6,我们可以获得以下定理。

定理10。让;然后是一个最小属性约简当且仅当吗是一个优化问题的最优解(12)。

由定理10函数的最小值,提出了相当于最小属性约简。我们可能得到的最小属性约简通过搜索函数的最小值,然后可以使用随机类别。

4所示。性能比较

为了分析和评估了适应度函数的有效性提出本文在文献[19),一个实验以以下方式设计。现有的两个最小属性约简算法基于不同类型的随机优化技术被用于比较。第一个是粒子群文中针对属性约简算法在20.),用算法,另一种是基于遗传算法的属性约简算法提出了(7,8,16),用GA简而言之。在实验中,两种算法实现和测试的数据集使用两种不同的健身功能:一是提出了(19)(简而言之),本文提出了新的适应度函数(简而言之)。七个UCI机器学习的数据集选择存储库。这些数据集通常用于评估属性约简算法在文献[7,8,11,14,16,17,19]。

每个两个健身的功能,两种算法运行50倍的数据集具有相同参数的设置。对于每个运行,需要记录三个值:第一个是输出的长度,第二个是输出对应于一个减少,最后运行时间。如果输出减少,输出是一个正常的输出;否则,它是一个不成功的输出。如果正常输出最小的长度,那么输出是一个成功的输出。让STL表示成功输出的长度,AVL表示平均长度,AVT表示平均运行时间在50分。成功的比率和正常输出表示,分别和。

电脑运行Windows 7(32位)和2.1×2 GHz CPU和2 GB的内存用于运行两种算法。两种算法的MATLAB程序。两种算法的参数设置见表1。在表1,造是指人口的规模(GA)或粒子群(PSO),最大允许的迭代次数(或代),所需的速度上限在PSO算法,和在GA变异概率和交叉,然后呢和学习系数算法。表2和3GA算法的主要性能和使用的每个两个健身功能。

从表2PSO算法,对STL的指数,健身功能都有相同的值。这意味着两个健身功能可以减少产量最低。AVL的指数的值不超过除了最后的日期。它反映的输出更专注于STL。相同的结论可以到达从索引中。这意味着它有一个更高的概率找到最低减少通过使用提出的适应度函数。AVT的所有值不到的值吗。因此,实验数据表明,该适应度函数的效率比通过使用PSO算法。可以从表中获得相同的结论3通过使用算法GA。

上述两个实验表明,该适应度函数比其他健身功能更充分的数据集。

5。结论

在本文中,为了克服缺点现有健身功能的最小属性约简问题,我们讨论了适应度函数,提出了一种简单的适应度函数。理论分析和实验结果表明,它可以保证最优等效和足够的比现有的适应度函数。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是支持的科技发展规划中国铁道部(2012 x003-a),四川省教育科学研究基金部门(14 za0245 14 zb0208),和四川大学重点实验室开放项目的桥梁Non-Destruction检测和工程计算(2014 qyj02)。作者感谢匿名审稿人的宝贵意见和建议。