推荐星级：

基于互信息下粒子群优化的属性约简算法

更新时间：2019-12-24 20:41:01 大小：2M 上传用户：zhiyao6 查看TA发布的资源 标签：粒子群优化 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

最小属性约简是粗糙集理论中属性约简的优化问题.在寻找最小属性约简的问题上,基于粒子群优化的属性约简算法(ARPSO算法)优于传统的属性约简算法.在现有的ARPSO算法中,正域部分通常被作为启发式信息,但是它并不能够很好地衡量不确定性,而互信息是粗糙集理论中一种更有效的度量不确定信息的重要工具.为此,提出基于互信息下的粒子群优化的属性约简算法(MIPSO算法),该算法把互信息作为适应度函数,通过增强粒子能迅速靠近吸引子的这一特性,改进了内嵌区域震荡搜索的粒子群优化算法(简记为RSPSO算法),防止算法较早的陷入局部最优,使得粒子群中的粒子更快的找到最优值,因此使得算法尽可能实现全局收敛.实验结果表明,该算法不仅提高了寻优的能力,加快了算法的速度,提升了算法的精度,而且也能够使得约简后剩余属性的互信息值与约简前所有属性的互信息值近似相等.

部分文件列表

文件名	大小
基于互信息下粒子群优化的属性约简算法.pdf	2M

立即下载

部分页面预览

（完整内容请下载后查看）

第１１期

电ꢀ

ꢀ

子ꢀ

ꢀ

学ꢀ

ꢀ

报

Ｖｏｌ．４５ꢀ Ｎｏ．１１

Ｎｏｖ．ꢀ ２０１７

２０１７年１１月

ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡ

基于互信息下粒子群优化的

属性约简算法

续欣莹^１，张ꢀ 扩^１，谢ꢀ 珺^１，谢ꢀ 刚^２

（１．太原理工大学，山西晋中０３００６０；２．太原理工大学国际教育交流学院，山西太原０３００２４）

ꢀ ꢀ 摘ꢀ 要：ꢀ 最小属性约简是粗糙集理论中属性约简的优化问题．在寻找最小属性约简的问题上，基于粒子群优化

的属性约简算法（ＡＲＰＳＯ算法）优于传统的属性约简算法．在现有的ＡＲＰＳＯ算法中，正域部分通常被作为启发式信

息，但是它并不能够很好地衡量不确定性，而互信息是粗糙集理论中一种更有效的度量不确定信息的重要工具．为此，

提出基于互信息下的粒子群优化的属性约简算法（ＭＩＰＳＯ算法），该算法把互信息作为适应度函数，通过增强粒子能

迅速靠近吸引子的这一特性，改进了内嵌区域震荡搜索的粒子群优化算法（简记为ＲＳＰＳＯ算法），防止算法较早的陷

入局部最优，使得粒子群中的粒子更快的找到最优值，因此使得算法尽可能实现全局收敛．实验结果表明，该算法不仅

提高了寻优的能力，加快了算法的速度，提升了算法的精度，而且也能够使得约简后剩余属性的互信息值与约简前所

有属性的互信息值近似相等．

关键词： ꢀ 互信息；粒子群优化；最小属性约简；粗糙集；局部搜索模式

中图分类号： ꢀ ＴＰ１８１ꢀ ꢀ ꢀ 文献标识码： ꢀ Ａꢀ ꢀ ꢀ 文章编号： ꢀ ０３７２⁃２１１２（２０１７）１１⁃２６９５⁃１０

电子学报ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎꢀ

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０３７２⁃２１１２．２０１７．１１．０１７

ＡｎＡｔｔｒｉｂｕｔｅＲｅｄｕｃｔｉｏｎＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎ

ＭｕｔｕａｌＩｎｆｏｒｍａｔｉｏｎｏｆＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ

ＸＵＸｉｎ⁃ｙｉｎｇ^１，ＺＨＡＮＧＫｕｏ^１，ＸＩＥＪｕｎ^１，ＸＩＥＧａｎｇ^２

（１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＴａｉｙｕａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｊｉｎｚｈｏｎｇ，Ｓｈａｎｘｉ０３００６０，Ｃｈｉｎａ；

２．ＣｏｌｌｅｇｅｏｆＩｎｔｅｒｎａｔｉｏｎａｌＥｄｕｃａｔｉｏｎａｎｄＥｘｃｈａｎｇｅ，ＴａｉｙｕａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｔａｉｙｕａｎ，Ｓｈａｎｘｉ０３００２４，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ꢀ Ｍｉｎｉｍｕｍａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎｉｓｔｈｅｏｐｔｉｍｕｍｐｒｏｂｌｅｍｉｎｔｈｅａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎｏｆｔｈｅｒｏｕｇｈｓｅｔｓｔｈｅｏｒｙ．Ｔｏ

ｓｅｅｋｔｈｅｍｉｎｉｍｕｍａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎ，ｔｈｅａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ（ＡＲＰＳＯａｌ⁃

ｇｏｒｉｔｈｍ）ｂｅａｔｓｔｈｅｔｒａｄｉｔｉｏｎａｌａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍ．ＩｎｅｘｉｓｔｅｄＡＲＰＳＯａｌｇｏｒｉｔｈｍｓ，ｔｈｅｐｏｓｉｔｉｖｅｒｅｇｉｏｎｉｓｕｓｕａｌｌｙｔａｋｅｎ

ａｓｔｈｅｈｅｕｒｉｓｔｉｃｉｎｆｏｒｍａｔｉｏｎ，ｈｏｗｅｖｅｒ，ｉｔｉｓｎｏｔｐｒｅｃｉｓｉｏｎｅｎｏｕｇｈｔｏｍｅａｓｕｒｅｔｈｅｕｎｃｅｒｔａｉｎｔｙ．Ｔｈｅｍｕｔｕａｌｉｎｆｏｒｍａｔｉｏｎｉｓａｍｏｒｅ

ｅｆｆｉｃｉｅｎｔｔｏｏｌｔｏｍｅａｓｕｒｅｔｈｅｕｎｃｅｒｔａｉｎｔｙｉｎｔｈｅｒｏｕｇｈｓｅｔｓｔｈｅｏｒｙ．Ｔｏｈａｎｄｌｅｔｈｉｓｐｒｏｂｌｅｍ，ａｎａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍ

ｂａｓｅｄｏｎｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎｔａｋｅｓｔｈｅｍｕｔｕａｌｉｎｆｏｒｍａｔｉｏｎ（ＭＩＰＳＯａｌｇｏｒｉｔｈｍ）ａｓａｔｅｒｍｉｎｔｈｅｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎ，

ＴｈｅｐｒｏｐｏｓｅｄＭＩＰＳＯａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｓｔｈｅｒｅｇｉｏｎａｌｓｈｏｃｋｓｅａｒｃｈｅｍｂｅｄｄｅｄｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＲＳＰ⁃

ＳＯ）ｂｙｅｎｈａｎｃｉｎｇｔｈｅｓｐｅｅｄｗｈｉｃｈｔｈｅｐａｒｔｉｃｌｅｉｓｃｌｏｓｅｔｏｔｈｅａｔｔｒａｃｔｏｒ，ｐｒｅｖｅｎｔｉｎｇｆｒｏｍｂｅｉｎｇｌｏｃａｌｏｐｔｉｍｕｍｅａｒｌｙａｎｄｆｉｎｄ⁃

ｉｎｇｔｈｅｏｐｔｉｍｕｍａｓｓｏｏｎａｓｐｏｓｓｉｂｌｅ．Ｃｏｎｓｅｑｕｅｎｔｌｙ，ｔｈｅｇｌｏｂａｌｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅＭＩＰＳＯａｌｇｏｒｉｔｈｍｉｓｇｕａｒａｎｔｅｅｄａｓｓｏｏｎａｓ

ｐｏｓｓｉｂｌｅ．ＴｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄＭＩＰＳＯａｌｇｏｒｉｔｈｍｎｏｔｏｎｌｙｉｍｐｒｏｖｅｓｔｈｅｏｐｔｉｍｉｚａｔｉｏｎａｂｉｌｉｔｙ，ａｃｃｅｌ⁃

ｅｒａｔｅｓｔｈｅｓｐｅｅｄａｎｄｉｍｐｒｏｖｅｓｔｈｅａｃｃｕｒａｃｙ，ｂｕｔａｌｓｏｃａｎｋｅｅｐｔｈｅｍｕｔｕａｌｉｎｆｏｒｍａｔｉｏｎｖａｌｕｅｏｆａｌｌａｔｔｒｉｂｕｔｅｓｂｅｆｏｒｅｒｅｄｕｃｉｎｇ

ａｐｐｒｏｘｉｍａｔｅｌｙｅｑｕａｌｔｏｔｈｅｖａｌｕｅｏｆｒｅｍａｉｎｉｎｇａｔｔｒｉｂｕｔｅｓａｆｔｅｒｒｅｄｕｃｉｎｇ．

Ｋｅｙｗｏｒｄｓ： ꢀ ｍｕｔｕａｌｉｎｆｏｒｍａｔｉｏｎ；ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ；ｍｉｎｉｍｕｍａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎ；ｒｏｕｇｈｓｅｔ；ｌｏｃａｌ

ｓｅａｒｃｈｓｃｈｅｍｅｓ

收稿日期：２０１６⁃０１⁃２９修回日期：２０１６⁃０６⁃０７；责任编辑：蓝红杰

基金项目：人社部留学回国人员科技活动择优资助项目（Ｎｏ．２０１３⁃６８）；山西省自然科学基金（Ｎｏ．２０１４０１１０１８⁃２）；山西省回国留学人员科研资助

项目Ｎｏ．２０１３⁃０３３，Ｎｏ．２０１５⁃０４５）

电ꢀ ꢀ 子ꢀ ꢀ 学ꢀ ꢀ 报

２０１７年

２６９６

能够找到数据属性的最小属性约简，同时也为了能够

保证属性约简后的准确度，本文基于互信息度量，在标

准粒子群算法的理论基础上深入的研究了内嵌区域震

荡搜索的粒子群优化算法，并对算法中吸引子的求解

过程做了进一步的改进，利用互信息度量属性重要度，

提出了ＭＩＰＳＯ算法，并采用ＵＣＩ数据集进行实验，实验

结果表明该算法是有效的．

１ꢀ 引言

ꢀ ꢀ 波兰数学家Ｐａｗｌａｋ在２０世纪８０年代初提出了粗

糙集（ＲｏｕｇｈＳｅｔ，ＲＳ），它是一种处理不完备信息的数学

理论^［１］．当前全世界的数据迅速地增长，且数据处于动

态更新的状态，数据处理技术成为了数据挖掘领域中

重要的一部分^［２］．在粗糙集理论中，属性约简是粗糙集

应用不可或缺的分支，也是挖掘和简化数据的重要步

２ꢀ 互信息与粗糙集属性约简

骤

^{［３，４］}．为了获得最精简的特征集，需要对决策表进行最

＝

ꢀ ꢀ 定义１ꢀ 定义ＩＳ（Ｕ，Ｅ，Ｖ，ｆ）为一个数据信息系

小属性约简．利用粗糙集理论进行属性约简与特征选择

已经在许多领域得到广泛应用，例如海量数据分析、聚

类分析、神经网络、模式识别、过程控制、天气情况、诊断

统，其中Ｕ为非空数据样本集，称为论域空间，Ｅ是有限

＝

→

属性集，Ｖ

∪

Ｖ，Ｖ表示属性ａ的值域，ｆ：ＵＥ

Ｖ

ａ∈Ｅ

ａ

疾病、机器学习、大数据处理等^{［５～９］}

．

是一个信息度量函数，即对ｘ∈Ｕ，ａ∈Ｅ有ｆ（ｘ，ａ）∈Ｖ_ａ．

任一属性子集ＢＥ决定了一个二元等价关系ＩＮＤ（Ｂ）：

粒子群优化算法（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）

是由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ于１９９５年提出的一种寻优算

＝

ＩＮＤ（Ｂ）｛（ｘ，ｙ） ∈ＵＵ｜ａ∈Ｂ，ｆ（ｘ，ａ）ｆ（ｙ，ａ）｝．Ｕ／

ＩＮＤ（Ｂ）或者Ｕ／Ｂ称为Ｕ的一个等价划分，是论域Ｕ上

的一个知识．该等价划分包括多个等价类，每个等价类

称为一个知识粒．

法

^［１０］．它可以解决大量非线性、不可微和多峰值的复杂

问题，并能应用于函数优化、神经网络训练、属性约简等

多个领域^［１１］．但是该算法容易陷入局部最优．为了提升

算法的寻优能力，使得算法能够全局收敛，相关学者做

了大量的研究，对算法进行了改进^［１２］．大多数改进的粒

子群算法都是将变异操作引入，当粒子趋于局部收敛

时或算法后期使粒子产生变异，使得粒子能够跳出局

部收敛位置，从而实现全局收敛．

定义２^［１９］ꢀ （互信息）设Ｕ是论域，Ｋ_１（Ｕ，Ｐ）和

＝

Ｋ_２（Ｕ，Ｑ）是关于Ｕ的两个知识库，其中Ｐ｛Ｐ_１，Ｐ_２，

＝

…，Ｐ_ｍ｝，Ｑ｛Ｑ_１，Ｑ_２，…，Ｑ_ｎ｝，Ｐ与Ｑ的互信息定义为

Ｑ_ｉ∩Ｐ_ｊＱ^ｃ_ｉ∩Ｐ_ｊ^ｃ

ｎ

ｍ

＝

Ｅ（Ｑ：Ｐ）

．其中Ｑ^ｃ_ｉ为Ｑ_ｉ在

∑∑

Ｕ

＝

１

ｉ

１

ｊ

目前，采用粗糙集理论进行属性约简的方法有许

多种，这些属性约简方法基本上采用的是启发式算法，

能够得到一个约简．文献［１３］提出了基于可行域的遗传

约简算法（简记为ＧＡ算法），文献［１４］提出了经典的

启发式最小属性约简算法（简记为Ｈｕ算法），文献［１５］

提出了基于二进制的粒子群优化的属性约简算法（简

记为ＰＳＯ算法），文献［１６］提出了基于免疫粒子群优化

的最小属性约简算法（简记为ＩＰＳＯ算法），文献［１７］提

出了基于二进制粒子群优化的一个最小属性约简算法

（简记为ＢＰＳＯ算法），文献［１８］提出了最小属性约简

问题的一个有效的组合人工蜂群算法（简记为ＣＡＢＣ算

法）．前两种算法都能够对数据进行属性约简，但不一定

能够得到最小的属性约简；后四种算法都是基于代数

观下的正域为属性重要度，但是利用正域来衡量数据

的不确定性是不够准确的，因为基于正域的属性重要

度具有较弱的启发信息，对不确定性度量能力较差．

互信息是粗糙集属性约简中基于信息观下的一种

度量工具，能够度量数据信息系统的不确定性，也能够

用来去除冗余属性，样本中属性的增减直接影响互信

息大小的变化．文献［１９］已经证明在一致决策表中，代

数观和信息观是等价的，而在不一致决策表中，信息观

的约简包含代数观，所以运用互信息来进行属性约简

要比使用正域来进行约简的效果要好一些．因此，为了

Ｕ上的补集，Ｐ^ｃ_ｊ为Ｐ_ｊ在Ｕ上的补集．

定理１^［１９］ꢀ 设Ｕ是论域，Ｋ_１（Ｕ，Ｐ）和Ｋ_２（Ｕ，Ｑ）

＝

是关于Ｕ的两个知识库，则有：

＝

－

Ｅ（Ｑ：Ｐ）Ｅ（Ｑ）Ｅ（Ｑ｜Ｐ）．

＝

定义３ꢀ 定义ＤＳ（Ｕ，Ｃ∪Ｄ，Ｖ，ｆ）为一个数据决策

＝

系统，其中Ｃ为条件属性，其等价划分为Ｕ／Ｃ｛Ｃ_１，Ｃ_２，

＝

…，Ｃ_ｍ｝，Ｄ为决策属性，其等价划分为Ｕ／Ｄ｛Ｄ_１，Ｄ_２，

…，Ｄ_ｎ｝．

＝

定义４ꢀ （决策表的互信息）设数据决策系统ＤＳ

（Ｕ，Ｃ∪Ｄ，Ｖ，ｆ），其中Ｃ为条件属性，Ｄ为决策属性，

ｎ

ｍ

＝

ＢＣ，则定义Ｂ对Ｄ的互信息为Ｅ（Ｄ：Ｂ）

Ｄ_ｉ∩Ｂ_ｊＤ^ｃ_ｉ∩Ｂ_ｊ^ｃ

∑∑

＝

１

ｉ

１

ｊ

，其中Ｂ表示的是条件属性下关于Ｕ

Ｕ

＝

的类元素，即Ｂ｛Ｂ_１，Ｂ_２，…，Ｂ_ｍ｝，Ｄ表示的是决策属

ｃ

＝

性下关于Ｕ的类元素，即Ｄ｛Ｄ_１，Ｄ_２，…，Ｄ_ｎ｝．其中Ｄ_ｉ

为Ｄ_ｉ在Ｕ上的补集，Ｂ^ｃ_ｊ为Ｂ_ｊ在Ｕ上的补集．

定理２^［１９］ꢀ 设数据决策系统ＤＳ（Ｕ，Ｃ∪Ｄ，Ｖ，ｆ），

＝

Ｂ和Ｐ分别为Ｕ上的两个属性集合．若ＩＮＤ（Ｂ）ＩＮＤ

＝

（Ｐ），则有Ｅ（Ｄ：Ｂ）Ｅ（Ｄ：Ｐ）．

＝

证明ꢀ 因为ＩＮＤ（Ｂ）ＩＮＤ（Ｐ），所以Ｂ和Ｃ在Ｕ

＝

上得到的划分是相同的，故有Ｅ（Ｄ：Ｂ）Ｅ（Ｄ：Ｐ）．

＝

定义５ꢀ 设数据决策系统ＤＳ（Ｕ，Ｃ∪Ｄ，Ｖ，ｆ），Ｂ，

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

基于互信息下粒子群优化的属性约简算法

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

资料专题

推荐下载

专栏首页