粒子群优化算法(PSO)之基于离散化的特征选择(FS)(二)

前面我们介绍了特征选择(Feature Selection,FS)与离散化数据的重要性,总览的介绍了PSO在FS中的重要性和一些常用的方法。今天讲一讲FS与离散化的背景,介绍本文所采用的基于熵的切割点和最小描述长度原则(MDLP)。

A. 特征选择

特征选择是一个组合优化问题,因为在具有N个特征的数据集上有2N个可能的不同特征子集。FS方法通常有两个重要的部分组成,即搜索技术和特征评估方法。

在特征评估方面,FS方法通常可以分为过滤(filter)和包装(wrapper)方法。过滤法基于它们的内在特性来评估特性。过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN)、决策树和支持向量机。一般来说,过滤器方法比包装器方法更快,然而,它们通常比包装器获得更低的分类精度。

在FS方法中搜索技术可以分为穷举搜索、启发式搜索、随机搜索和随机搜索。虽然穷举搜索保证找到最好的解决方案,但是由于它的计算时间太高,对大多数实际应用程序来说是不可行的。序列搜索如线性正向选择(LFS)和贪婪逐步逆向选择(GSBS)是启发式搜索的典型方法。这两种方法分别是序列正向选择(SFS)和序列逆向选择的派生版本。LFS通过限制每个步骤中考虑的特性的数量来提高SFS的有效性和效率。虽然向后选择可以考虑特性交互,而不是向前选择,但是对具有大量特性的数据集应用是不切实际的。GSBS不能在一个星期内完成,它运行在具有数百个特征的数据集上。另外,前后策略通常都要面对局部最优的问题。

随机搜索可能会以一种完全随机的方式生成子集,使用Las Vegas算法,比如LVW,在一个大的搜索空间中,它的收敛速度太慢。与随机生成不同,EC是一种随机的方法,它应用进化原理或群智能来从当前的子集生成更好的子集。PSO是一种应用于FS的群体智能技术,并显示了其有效性。大家可以通过使用EC技术对FS的不同策略进行更全面的调查。虽然PSO已经成功地应用于不同的优化问题,包括FS,但它还没有应用于离散化。

B. 特征离散化

特征离散化是一个研究历史悠久的话题。在此领域提出了许多不同策略的离散化方法。但是,它们都具有相同的目的,即确定将特征值分割为离散值的分割点。在特征值的范围内,分割点或分点是真正的值,这些值被用来分割这个范围到若干个间隔。现有的离散化方法可以使用不同的标准进行分类。在直接方法中,间隔是基于预定义的参数生成的。另一方面,增量方法递归地分离(或合并)间隔,直到满足一些标准,从而产生分裂(或合并)方法。它们也被称为自顶向下或自底向上的方法。根据是否在离散化过程中使用类标签,对离散化方法进行监督或无监督。如果在每个离散化步骤中使用整个实例空间,或者如果每个离散步骤只使用一个实例子集,那么它将是全局的。一种方法也属于单变量或多变量,这取决于特征是离散的还是多个特性的离散化,同时考虑特征之间的交互。

等宽和等频是两种简单的无监督方法。它们将特性离散为一个预定义的m间隔,具有相同的宽度或相同数量的值。这些简单的方法易于实现,但对m的值敏感,通常很难确定,尤其是当特性不是均匀分布或包含异常值时。

使用类标签作为搜索切割点的引导,监督离散化通常比无监督的匹配要好。在不同的类的边界上定义了切点的特征值。除了不同的搜索技术,还有分类错误率、信息增益和统计度量等不同的评价方法。

在受监督的方法中,Fayyad和Irani提出的最小描述长度(MDL)是最常用的方法之一。它是一种基于熵的增量分割离散化方法。利用信息增益来评价候选点。MDL递归地选择最佳的切点,将一个间隔分割为两个,直到实现MDLP。受此策略启发,我们建议使用由MDLP所接受的基于熵的切点作为BBPSO的初始或候选切入点。

C. 基于熵的切割点

基于熵的离散化的目的是找到最佳的分割,以便离散化的特性在类标签上尽可能的纯粹。这意味着在一个区间内的大多数值都更倾向于具有相同的类标签。如果用熵E(S)来衡量集合S的纯度,那么根据这一标准,获得最高信息增益的切点是最好的。以下公式用于计算特征A的切点T的信息增益,作为特征值的集合。S1和S2是S分区的子集。

D. 通过离散化来进行特征选择

虽然FS和离散化是近几十年来新兴的领域,但是结合这些任务的方法并没有引起足够的重视。Chi2是通过离散化提出FS的第一个方法。它是一种自下而上的方法,从只有一个特征值的间隔开始。然后相邻间隔χ2最低的测试结果将合并后的递归,直到χ2值对超过一个阈值。此阈值是通过试图维护数据的预定义一致性级别来确定的。通过释放这个一致性级别,Chi2可以提出只有一个间隔的特征,可以为FS移除。结果表明,在两个合成数据集上,Chi2有效地消除了相关特征,消除了所有的噪声特征。然而,用户定义的不一致率很难预先定义,也可能导致离散化过程的不准确。改进的Chi2 (MChi2)是一种完全自动的离散化方法,解决了Chi2的缺点。

另一种通过离散化的方法是基于离散化过程中计算出的一些度量方法进行排序。然后,将选择一些级别最高的特征。这个方法的一个例子是PEAR,其中的特性是从最小的切点数量到最大的。顶级的特征被认为是相关的,并被选择形成最终的子集。结果表明,该算法具有与原特性集相似的性能,且效果较好。但是,很难为PEAR选择合适的参数,以及应该选择哪些特性来形成最终子集。同样,特征根据原始连续值的方差和用于编码离散特征的比特数的比值进行排序。

综上所述,通过离散化的特征选择在两个不同的阶段。但是,将他们整合到同一个阶段的研究目前还没有。

E. 粒子群优化算法

具体可参考之前的文章“计算智能(CI)之粒子群优化算法(PSO)”。本篇文章将不再赘述。

参考文献: 文章:“A New Representation in PSO for Discretization-Based Feature Selection” 作者:Binh Tran, Student Member, IEEE, Bing Xue, Member, IEEE, and Mengjie Zhang, Senior Member, IEEE

原文发布于微信公众号 - 磐创AI(xunixs)

原文发表时间:2018-04-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

微软资深研究员详解基于交错组卷积的高效DNN | 公开课笔记

1451
来自专栏新智元

谷歌大脑:使用强化学习,从头生成神经网络架构(论文)

【新智元导读】深度学习的成功,使业内范式开始从特征设计转向架构设计。Google Brain 研究人员使用强化学习,从头开始生成神经网络架构。【论文地址:htt...

4226
来自专栏机器之心

业界 | 如何达到Kaggle竞赛top 2%?这里有一篇特征探索经验帖

在数值数据上构建任意监督学习模型的一个重要方面是理解特征。查看模型的部分依赖图可帮助理解任意特征对模型输出的影响。

1033
来自专栏机器学习算法与Python学习

Kaggle如何取得top 2%,这篇文章告诉你!

本文作者 Abhay Pawar 多次参加 Kaggle 竞赛,并在 Instacart Market Basket Analysis 竞赛中拿到 top 2%...

1194
来自专栏AI科技大本营的专栏

撕起来了!谁说数据少就不能用深度学习?这锅俺不背!

作者 | Andrew L. Beam 编译 | AI100 撕逼大战,从某种角度,标志着一个产业的火热。 最近,大火的深度学习,也开始撕起来了。 前几日,有一...

4617
来自专栏AI派

业界 | 如何达到Kaggle竞赛top 2%?这里有一篇特征探索经验帖

在数值数据上构建任意监督学习模型的一个重要方面是理解特征。查看模型的部分依赖图可帮助理解任意特征对模型输出的影响。

983
来自专栏新智元

【重磅】谷歌开源 TensorFlow 图说生成模型,可真正理解图像

【新智元导读】谷歌今天宣布开源图说生成系统 Show and Tell 最新版在 TensorFlow 上的模型。该系统采用编码器-解码器神经网络架构,分类准确...

5155
来自专栏量子位

称霸Kaggle的十大深度学习技巧

在各种Kaggle竞赛的排行榜上,都有不少刚刚进入深度学习领域的程序员,其中大部分有一个共同点:

1581
来自专栏人工智能

机器学习教程:朴素贝叶斯文本分类器

在本教程中,我们将讨论朴素贝叶斯文本分类器。朴素贝叶斯是最简单的分类器之一,只涉及简单的数学表达,并且可以使用PHP,C#,JAVA等语言进行编程。

2759
来自专栏新智元

南开大学提出新物体分割评价指标,相比经典指标错误率降低 69.23%

---- 新智元专栏 作者:范登平(南开大学) 【新智元导读】南开大学媒体计算实验室等研究团队从人类视觉系统对场景结构非常敏感的角度出发,提出一种新颖、...

3288

扫码关注云+社区

领取腾讯云代金券