MyException - 我的异常网
当前位置:我的异常网» 数据仓库 » 数据挖掘稿件翻译-Mining Emerging Patterns by Str

数据挖掘稿件翻译-Mining Emerging Patterns by Streaming Feature Selection

www.MyException.Cn  网友分享于:2013-06-21  浏览:0次
数据挖掘文章翻译--Mining Emerging Patterns by Streaming Feature Selection

学习数据挖掘,可以用到的工具-机器学习,SPSS(IBM),MATLAB,HADOOP,建议业余时间都看文章,扩充视野,下面是本人翻译的一篇文章,供大家学习。另外,本人感兴趣的领域是机器学习,大数据,目标跟踪方面,有兴趣的可以互相学习一下,本人Q Q邮箱 657831414.,word格式翻译和理解可以发邮件
“ 原文题目是Mining Emerging Patterns by Streaming Feature Selection

通过流特征的选择挖掘显露模式
俞奎,丁薇,Dan A. Simovici,吴信东
俞奎,吴信东,合肥工业大学计算机系
丁薇,美国麻省大学波士顿校区计算机系
Dan A. Simovici,美国佛蒙特大学(伯灵顿)

摘要
以高维数据集建立一个准确的显露模式的分类是一个具有挑战性的问题。假如整个特征空间在机器学习开始之前是不可用的,那么问题将变得更加困难。本文提出了一种新的技术,是关于用流特征选择来挖掘显露模型。我们用流特征将高维空间模型化,也就是说,特征到达就被处理一次。当特征流一个接一个来到时,我们就在线估计每一个讲将到达的特征流通过利用特征相关性和EP分辨力(EP的预测力)之间的关系是否对挖掘预测显露的模式(EP)有用。我们采用这种关系来引导在线EP挖掘过程。这种新方法可以可以从高维数据集中挖掘EP,即使当其整个特征集在学习之前不可用。这个实验在广泛的数据集上验证了我们所建议的方法相比其他已确立的方法在预测准确性、模式数和运行时间上的有效性。
分类和主题描述
1.5.2 【计算方法】:设计方法分类器的设计和评估、特征评估和选择。
概述:算法,实验。
关键字:显露模型,特征相关性,流特征。
1.介绍
一个显露模式(简称EP)[7,10]就是一个支持度数值显著地一类接着一类变化的模型。通过聚集区分EPs力来建立高度准确的分类器。
当特征维数达到上千,挖掘EP仍然是一个艰巨的问题,因为有大量的候选EPs所以很难存储,检索和排序,修剪,有效的分类。因为显露的大量的数据集的出现,包括成百上千的特征流,比如图像处理,基因表达数据,文本数据等等。这类模型搜索空间相当巨大,即使对这些特征空间进行平滑处理都不太可能。因此,从这样的一个空间挖掘EPs必须面对两个具有挑战性的研究问题:
(1)怎样从一个高维数据集高效地挖掘一小部分可预测的EPs.
(2)当在一个大的特征空间上进行穷举搜索既耗时或不可行时,怎样在这个特征空间预测EPs.
在本文中,我们提出了一种新的方法来讨论这两个挑战性的问题。我们的方法一个新的贡献就是用流特征来将高维空间模型化,然后将流特征选择融入到EP挖掘过程来帮助在一个大的特征空间进行有效和高效地发现可预测的EPs小集合并且取得很好的性能。
提出流特征的概念是为了随着时间在变化的特征空间里处理特征选择。不像数据流那样,带有流特征的特征维度要被模拟成特征流,那些特征流一个接一个地出现,在处理特征流时取决于它的到达。最近的研究表示特征流的选择不仅在一个大的特征空间而且在一个未知的满特征空间也是有效和高效的[19]。然而,如果我们把流特征选择和EP挖掘看成一个整体,那集合所有的特征和样本来挖掘EP就是一个复杂的研究性问题。
(1)在线数据处理.因为特征维度一个接一个地流入,这就要求在线转换、映射和分派到达的特征流。第一,将一个真实数据集转换成一个所需的编码数据集,而在挖掘开始之前所有工作项目都是不可行的。第二,项目数量和真实的特征流之间的映射在特征流随着是按一个接一个流入时需要被构建和更新。第三,当一个特征有效时,我们应该把每一类数据划分而不是提前以特征流把所有数据划分。
(2)动态EP挖掘。根据流特征,一个挖掘EPs的解决办法是采用流特征选择来动态控制EP挖掘过程。这个问题是怎样把流特征融入到EP挖掘过程来获取准确的EP分类器。
本文中,我们提出了EPSF(通过流特征选择来挖掘显露模式)。更具体来说,EPSF假定特征逐个流入并被立刻在线处理。在动态EP模式挖掘阶段,EPSF提出了两阶段的框架来动态处理EP模式挖掘。随着特征逐个流入,EPSF交替执行下面两个过程,从而EPSF提供了一种自然的方式把流特征选择嵌入到EP模式挖掘过程来解决动态高维特征空间中的模式挖掘问题。
本文的其余部分组织结构如下:第2部分回顾相关工作。第3部分给出相关基础知识,第4部分展现我们的方法。第5部分报道我们的结果,第6部分提供我们的结论和未来的工作。
2.相关工作
Dong和Li[9]介绍了EPs来展现在不同类数据间的显著对比。另外,一个跳跃性的显露模型(简称JEP)是一种特殊的EPs,它支持将一类数据中的零增加到另一类的非零.像其他模式一样由相关连接的元素的组合组成,EPs很容易被理解和直接用于广泛的应用中,比如说错误检测和在基因表达数据中发现信息[8,18]。
挖掘EPs的最大的一个挑战就是高计算成本,因为候选模型呈指数型。一个有意思的措施可以在不牺牲分辨力的情况下减少所发现的EP数。Dong 和 Li受Max-Miner算法启发第一次提出了基于边界的方法。在他们的方法中,边界值是用来代表EPs的候选和子集,边界差异化操作是用来发现EPs。ConsEPMiner 算法遵循了一个逐层、候选集生成测试方法来挖掘EPs[23]。Bailey et al. [3]推荐了挖掘JEPs的快速算法,它比基于边界的算法速度更快。后来Bailey et al. [4]根据计算最小超图传送展现了一种新的算法来高效挖掘EPs。。受FP树启发,一个基于CP树数据结构的CP树挖掘器显示可以提高EP挖掘性能[6]。尽管EP挖掘性能提高了,[17]证明了之前的那些技术都不能处理维度超过60的。他们提出了一个ZBDD EP-MINOR的方法:用零压缩二叉决策图在高维度数据下挖掘EPs.
很多关于EPs的研究都集中在分类方面。Dong et al.[10]提出第一个EP分类器,把它称作CAEP(通过聚集显露模式分类).基于CAEP,Li et al.提出了JEP分类器,它明显区别于CAEP分类器。由于JEPs在不同的类之间比其他类型EPs更加不同,因而JEP分类器独特的采用了JEPs.所有这些分类器挖掘EPs时都是基于边界值的方法。同时,Li et al.[13]也基于距离的EP发现展现了一个惰性EP分类器,即DeEPs, 用来证明CAEP和JEP分类器的准确性和高效性。另外,Fan 和 Ramamohanarao[7]提出了一个强健的EP分类器,即SJEP分类器,使用了一个有力的跳跃显露模式,该模式是一个特殊的JEP,它支持一个类中的零但是另一个类中取得非零但得满足最小阀值。SJEP分类器将CP树嵌入到EP分类器中,并且使用更少的JEPs而不是JEP分类器。
受EP挖掘技术限制,现有的EP分类器仍然不能处理超过六十维以上的数据集。尽管ZBDD EP挖掘器能够处理一个高维度的数据集,但是和以前方法一样,它仍然受制于EP数量的突发性增加,即使有相当高的支持度阀值。但是要从大量的候选EPs中挖掘出少量的可预测的EPs仍然是一个极具挑战性的研究问题。在最近的一个研究中,Yu et al.用贝叶斯网络来帮助构建EP分类器,从而解决了一个随意关联分类的概念。这个研究显示将任意结构嵌入到EP挖掘中能搞高效地在高维数据中提取少量预测性高的EP模型,并且取得高准确度的EP分类器。与[21]比较,我们提出了一个有流特征选择控制的挖掘EP模型的方法。这个方法能处理未知的或大量的完全特征空间,然而穷举查找既耗时又不一定可行。
3.预备知识
假设我们有一个数据集D定义为N个特征 和类别属性C的集合。对每一个特征Fi,i=1,…N,我们假设它在一个离散领域中,其离散取值的范围表示为dom(Fi).令 表示所有项集的集合, 。假设项集X是 的一个子集且它在D中的支持度表示为 , 是D中包含X的实例的数目,|D|是D中实例的数目。令 BI表示K个不同类标签的有限集,那么数据集可悲划分成D1,D2,…,DK,Dj由类标签为Cj的实例组成,j=1,2,…,K.从Ds到Dm(s,m=1,…,k,s m)X的增长率定义如下。
定义1:(GR:增长率)[9] ,如果 那么 ;如果 那么 。
定义2:(EP :显露模型)给定一个阀值 ,一个从DS到Dm的EP定义为一个项集X,且
一个从Ds到Dm的EP成为Dm的EP模式。如果 ,那么项集X被称作是一个从Ds到Dm的JEP.EP挖掘的目标是给定一个预定的增长率阀值 和一个最小支持度阀值,从每个类别CI中挖掘从D-Dci到Dci的EP集合Ei。
定义3:(Growth Rate Improvement)[23]给定一个EP e,e的Growth Rate Improvement Tateimp(e)定义为它的增长率和它的所有子集增长率的最小差值。

Rateimp(e)为正的阀值则保证了EPs集合的简明和代表性,而且EPs不被另一类所包含,有助于提高该模型的预测力。因此,Growth Rate Improvement 可以去除无用或冗余的EP模式。
在表1和2中给出了一个很明了的例子,表一和表二的Ballon数据集来自于UCI machine learning repository[5],假设最小支持度阀值是0.2,增长率阀值 >1,候选EPs是T(膨胀类)和F(非膨胀类)两类,一共20个例子,4个特征:color,size,act和age.

由定义2,在表二中,{act=stretch}和{age=adult}都是T类中的EPs.在表一中,由定义3看出,{act=dip,age=child}是F类的EP,由于{act=dip}和{age=child}都包含在其中。当把EPs应用到分类中,每一个Ci类的EP集合被用于决定一个测试实例t属于哪个类。具体的说,根据每个类别的EPs和评分函数 ,我们为t计算k个分数。下面的定义给出了评分函数的计算公式[10].
定义4:(Aggregate Score).给出一个实例t和一个类别 的EPs集合Ei,t在Ci类的评分定义如下:

在定义4中的评分存在的问题是不同类的EP模式的数量可能是不平衡的。如果雷Ci比类Cj包含更多的EPs,那么一个测试实例在例Ci获得的评分要比其在Cj获得的要高,即使测试实例实际属于Cj类。因此定义4计算的评分不能被直接用于分类一个测试实例。为此,Dong等人提出了一个类CI的评分被重新定义为normScore(t,Ci),是score(t,Ci)和baseScore(Ci)的壁纸,normScore(t,CI)定义如下:

测试实例t被赋予具有最高normScore的那个类别。如果normScore相等,则测试实例t赋予具有最大训练样本数据的那个类别。
4.特征流下的显露模式挖掘
4.1特征相关性和EP鉴别力
在一个大型高维数据集中检测一个搜索空间所包含的可能性的数据是行不通的。问题是在挖掘EP前是否所有·特征值可以被修剪。从表一和表2中,我们可以看到最终EP模式集合并不包含特征size和color,因为他们所对应的EP模式对构造精确的分类器没有影响。我们提出嵌入特征流使得在高维下的EP挖掘从而产生高准确度的EP分类器,否则在高维空间下搜索可能性空间就不可能。在本节我们从理论上分析特征相关性和EP鉴别力的关系,然后以EP鉴别力和特征流随时间变化估计出特征相关度。
一个输入特征可能存在于三个不同类中的一个,这三类是就相关性和它的类分配而言,即强相关性,弱相关性和不相关。弱相关性特征可以进一步被分成冗余特征、最佳特征子集和非冗余特征,但是非冗余特征具有强相关特征[22].在下面的定义中,令F是满特征集合,Fi是第I个输入特征,C是类分布,P(C|S)是不同类的概率分布,其中特征子集
定义5(强相关性)一个特征Fi对C具有强相关则有
定义6(弱相关性),Fi对C具有弱相关则

定义7(不相关),FI对C不相关则有

命题1:对 , ,则Fi对C不相关。
证明:假定数据集D中有两类个类别C={CP,Cn},Dp表示类别Cp的训练数据,Dn表示类别Cn的训练数据,•—supDp(Fi=f)表示项集{FI=f}在类别Dn中的支持度,则从类别Dn到DP的增长率GR(Fi=f)计算过程如下:

另一方面,若有 ,则有

根据定义7,对于任意 和 的F和C,有 ,因而Fi对C不相关。说得清楚点就是,如果GR(Fi=f)=1,就表示F与C不相关,另外一方面,Fi对C不相关,则

命题1得证。
定义8:(马尔可夫毯)[11]令 是特征一个子集,如果Fi条件独立于F-MI-{Fi},则Mi对F而言是一个马尔可夫毯。
定义9(冗余特征)[22]一个特征多余时,需要从F中被移出,有且仅有若相关且有一个马尔可夫毯存在于F中。
从定义3来看,对于一个EP e,如果我盟可以找到 ,使得 ,那么给定子集e’,e可能是冗余的EP,因为e可以被它的子集e’取代。因此,事先避免产生这些冗余的EP将会提高搜索效率。下面给出明体2来解释冗余结点和EP挖掘中的冗余EP中的关系。

命题2 :

若Fi对C而言是多余的,C的条件是在子集S上。
GR增长率从类别Dn到Dp的增长率计算如下:

因此我们证明了命题2.
命题2表明如果FI是C的冗余,给出一个子空间S,若 且对
包含相同的可预测的信息作为子集 。
根据命题1和2,我们能够在不考虑不相关和冗余特征时提取EPs.因此我们将流特征选择嵌入到EP挖掘过程中避免产生非EPs和冗余EP.
因为不相干特征可以很容易地发现,我们面临的两个挑战性问题是:(1)如何识别冗余特征流的特性;(2)如何从当前特征池中在线提取EPs. 我们给下面的两个命题处理冗余特征。从定义8看,因为马尔可夫毯的C贯穿了所有其他的信息特性,对C我们设置一个马尔科夫毯的C(MB(C)短)是一个空集一开始,逐步构建CMB(C)随着时间的推移特性流在一个接一个。显然,根据定义,我们可以得到命题3确定是否一个新的到达特性是冗余的。
当特征一个接一个流入,一个当前的马尔可夫毯在时间T被定义成 ,假设新到达的马尔可夫毯Fi在t+1时刻对C弱相关。若 ,那么,Fi可以移除。
有了命题3,我们得到命题4来决定在 中哪种特征是冗余的当Fi加入时。
命题4:在时间t时的 ,我们假设在 下不存在任何 如果
,那么Y就可以在 下移除。
4.2特征流选择下的显露模式挖掘
有了4.1中的理论分析,我们在图1中提出了一个EPSF算法:

EPSF 在线建立了两个池:一个特征池和一个EP池。特征池是用来存储对挖掘具有预测能力的EP模式的特征且随着特征逐个流入而动态变化;EP池是用来保存从当前特征池中挖掘出来的候选EP模型,且随着特征池动态变化而实时在线更新。当一个新特征流入时,如果它是一个强相关或者非冗余特征,EPSF就把它加入到当前特征池中,在线把它转换成一个项集,同时在这组项集中在线挖掘EP模式,并把这些EP模式加入到EP池。随着特征的流入,当前的EP池随着特征池的变化而在线更新。为了快速响应这种变化,当特征逐个流入时,我们只在线挖掘单项集(1-itemset)EP模式,然后当所有特征到达时再从当前EP池中挖掘所有的EP模式。
具体地说,EPSF包含以下几个主要阶段:
在线挖掘单项集(1-itemset)EP模式(steps 2到18)。当一个新特征到达时,EPSF首先鉴别它是否是不相关的特征;如果是,则丢弃。否则,我们通过命题2评估它是冗余的;如果是,则丢弃。如果不是,把它加入到当前特征池CMB(C)中。然后,EPSF把特征X转换成一组项集 ,保存 和X之间的映射关系map_form.这个映射关系可以保证从同一个特征转换出来的项集,或其超集不会出现在一个EP模式中。根据项集 合映射关系,EPSF根据类别个数划分特征X,为每个类别挖掘EP模式,并且把挖掘EP模式存储在称谓CEP的候选EP池中。
在线更新CEP和map_form.由于新特征X的加入当前特征池CMC(B)中,EPSF通过移除CMB(C)中的冗余特征来在线更新特征池CMB(C).如果有特征从CMB(C)中被移出,CEP和map_form将被在线更新。
EPSF算法与高维度下的数据集是相关的。,它不需要存储所有数据,仅在内存中检测:当一个新特征加入时,是否新特征是冗余的,然后更新CMB(C)。作为一个新分布,EPSF可以在不知道完整特征集之前在高维数据下挖掘数据集。当特征一个个流入时,每一个特征的处理取决于它的到达。特征冗余检验(Step 6)和CMB(C)更新(Steps 20-22)都是在当前CMB©下进行,而无需在整个特征空间。
5.实验结果
5.1实验设置
未来全面评估EPSF算法,表3的36个数据集分别来自UCI机器学习数据库(前24个),高维的生物医学数据集(hiva,ovarian-cancer,lymphoma breast-cancer),NIPS2003特征选择挑战数据集(madelon,arcene, dorothea, 和dexter)和4个常用的基因调控数据集(最后四个数据集)。
我们的对比研究包括三种类型的比较,在所有数据集上都用十折交叉验证。
EP分类器的状态比较:CAEP[10]和CE-EP[21]:
三个知名的有关联的分类器:CBA[15],CMAR[14]和CRPR[20]与EPSF做比较。
比较EPSF和不相干的分类器的预测准确性,包括决策树J48,SVM,ADABoost以默认参数实施Weka.
我们用Aliferis等人提出的方法来离散连续的特征集。在实验中,我们设置最小阀值为:CBA和CMAR0.8,EPSF、CAPE、ce-ep增长率20。为了测试最小支持度阀值的影响,我们分别为EPSF、CE-EP、CAEP、CBA、CMAR设定7个最小支持度:0.005、0.01、0.05、0.1、0.2、0.3、0.4。CPAR的参数和[20]中报告的相同。CBA 、CMAR和CPAR在LUCS KDD软件上实施。而EPSF 、CAEP和CE-EP在C++上实施。这些实验均在Windows7DELL工作空间,配置为Intel Xeon 2.93GHZ的处理器和12GRAM.

5.2预测准确度的比较
表4 - 6报告详细的EPSF分类器和其他八个分类器预测结果的准确性,包括两个EP,三个关联和三个不相关在三十六基准数据集的分类器。我们在7个最低支持度下比较研究的结果选择最佳的预测精度。在表6中,CBA,随着和CPAR只有结果24低维数据集,因为他们无法处理高特征空间。最好的结果是对每个数据集加强以及用符号“/”代表一个分类器用掉的内存在大量候选模型下。
进一步研究分类的结果,我们在95%的显著性水平下做实验,在表7中总结出EPSF算法和其他算法的胜/平/负表。(注意:如果一个分类器不能在数据集上运行而能在EPSF上工作,则EPSF获胜)。
在表7中,制定EPSF通常优于CAEP在所有三十六个数据集上及CBA,CMAR,CPAR在24个低维数据集下。EPSF也优于CE-EP,CE-EP是最先进的EP分类器在处理高特征维度数据上。与此同时,与著名的non-associative分类器相比,EPSF明显优于J48和Adaboost与SVM也很有竞争力,如表7所示。我们在实验中证明了将流特征选择嵌入EP挖掘可以避免生成non-EPs和冗余的EP。这不仅能使EPSF处理高维数据集比如处理最后12个数据集等,而且在表3中,也产生非常有前途的预测精度。

5.3模型数量的比较
图2到4比较了EPSF与CBA CMAR CAEP CE-EP下挖掘的模型数量,由于
这五个分类器都集中于在支持度框架下产生模型。我们通过7个不同的最小阀值报告平均挖掘的模型数量。由于在wdbc, kr-vs-kp, ionosphere, horse-colic 和german上CAEP不能用所有的支持度阀值来运行,在可用的支持度阀值上做出的数据集的模型数量取的是平均值。
图2只画了21个低维数据集,因为CAEP不能在infant,promoters和spectf的数据集上运行.在图3中,x轴表示表三中头24个数据集对应的二十四个数据集。在图4中 X轴表示表三中对应的所有三十六个数据集。很清楚,EPSF在低维数据集下选择模式比CBA,CMAR少很多。
在图4中,EPSF在十六个数据集上也比CE-EP选择的模式更少。这些结果说明EPSF和CE-EP都可以在高维数据集下选择少量的强预测EPs。在图4中,25到36对应表三的最后十二个高维数据集。我们可以看到,即使在非常高的特性维度下,CE-EP和EPSF选择的模式数量相比在24维低维数据集下也没有太大的改变的。
5.4运行时间的比较
EPSF,CAEP和CE-EP的运行时间包括所有的获取时间,包括导入数据集、十折交叉验证测试。在表8中显示了EPSF与CAEP,CE-EP各自的运行时间。在表8中可以看到,在所有数据集上,EPSF比CAEP快。在头二十4个低维
数据集下,EPSF比CE-EP快。但最后十二个高维度空间数据集下,EPSF并不比CE-EP更快一些。这是因为在每个折交叉验证下,EPSF考虑所有特征挖掘EP,而CE-EP在EP挖掘前能发现类的直接原因和类分布直接的影响,然后在减少的特征空间下直接进行折交叉验证而不是针对所有特征。因此,在图5 - 6,我们只画了EP挖掘的运行时间(不包括培训和测试分类器的时间)在每一折上以支持度阈值的上限为0.2。
在图5中,和图二一样X轴表示同样的二十一个数据集。在图六中,X轴上,1到3分别代表infant,promoters,specff的数据集,4到15代表表三中的最后十二个高维数据集。在图五中,我们可以看到EPSF在21个低维数据集下仍然比CAEP和CE-EP快。

图2,挖掘EP的数量:EPSF vs CAEP.X轴上的21个数据集分别是:1.australian, 2. breast-w, 3.crx, 4.cleve, 5.diabetes,6.german,7. house-votes, 8.hepatitis, 9.horse-colic,10. hypothyroid,11.heart, 12.ionosphere, 13.kr-vs-kp, 14.labor, 15. liver, 16.mushroom,17. pima, 18.spect, 19.tictactoe, 20. vote, 21. wdbc).

在图6中,EPSF仅在3个数据集下比CE-EP慢:hiva,dexter and breast-cancer. 总而言之,EPSF在三十六个数据集中有三十三个比CE-EP快。

5.5在不同增长率阀值下的预测准确性分析
为了进一步探索EPSF,CAEP,CE-EP的性能,我们在7个不同的增长率阀值下对EPSF,CAEP,CE-EP的预测精确度做了分析,如图7到9所示,GR代表增长率阀值,最小支持度阀值稳定在0.1.由于在infant, ionosphere, promoters and spectf上,CAEP在7类增长率阀值下不能运行,图7画出了在7种增长率阀值下的剩余的20个低维数据集的预测精确性。在图8和9中,X轴表示表三中对应的三十六个数据集。在图7到9中,我们看到CAEP,CE-EP和EPSF对低增长率阀值并不敏感,特别是CE-EP和EPSF.
5.6在整个特征空间下不平滑地挖掘EPs
与CE-EP相比,EPSF不仅能处理大规模特征空间,而且在不知道完整特征空间前提下也能处理高维数据集。有时,假如一个特征空间过大,而穷举查找即耗时又不可行。EPSF提供了一个解决此问题的方法,根据特征的到来通过依次处理特征,并且以用户分类的标准处理。CE-EP就不能解决这种状况因为它需要根据类的分布鉴别原因和影响。由于页面限制我们仅仅在图10的四类基因数据下估计了EPSF的性能对于每一个数据集合,我们随机挑选出10个样本作为测试实例(5正5负),其余的用于训练。SVM和AdaBoost用于测试和训练所有特征集的基线。在不清楚所有特征空间前提下,EPSF和EPs在训练样本上当特征依次流入时在测试样本上估计当前EPs.

Fig.7.CAEP下不同增长率阀值的影响:X轴上的20个数据集分别表示wth rate thresholds on CAEP (the 20
datasets on the X-axis are: 1.australian, 2. breast-w, 3.crx, 4.cleve,5.diabetes, 6.german, 7. house-votes, 8.hepatitis, 9.horse-colic, 10.hypothyroid, 11.heart, 12.kr-vs-kp, 13.labor, 14. liver, 15.mushroom, 16.pima, 17.spect, 18.tictactoe, 19. vote, 20. wdbc).

在克隆的数据集上,当到达的特征的百分比有20%到50%,那EPSF的预测精确性就和SVM相同。当所有特征到达时,EPSF的预测精确性达到100%,比SVM更好。至于剩下的数据集,EPSF不会比Adaboost糟糕,在不对整个特征空间做穷举查找下能达到SVM的预测准确性。这证明了在整个特征空间做平滑处理又昂贵又不可能时EPSF提供了一个有效和高效的解决EP挖掘问题的方法。

5.7实验结果总结
基于5.2到5.6的对比研究,我们有以下发现:
在所有数据集合上,EPSF产生的模型数量比较小。EPSF相比其他四类分类器(CAEP,CBA,CMAR,和CPAR)和两个最先进的分类器(J48和AdaBoost)更精确,可以与SVM竞争。甚至,作为联合分类器,CAEP,CBA,CMAR,和CPAR不能处理高维数据集。而对于运行时间,EPSF在所有数据集中比CAEP快。
EPSF vs. CE-EP.EPSF和CE-EP能处理高维数据集且有很高的预测精确性。当所有特征集已经知道了,在三个评价指标上:准确性、模式数量和运行时间,EPSF都优于CE-EP,尽管他们很接近。这一实证验证了特征相关性和EP辨别力之间的关系。另外,流特征选择,相比CE-EP,EPSF不仅能处理更高的特征维度,而且在获取整个空间前处理未知的满特征空间也有优势。而且EPSF可能可以避免在整个特征空间进行穷举查找。
结论和未来工作
在本文中,我们探讨了特征相关性和EP辨别力之间的关系。通过使用这种关系,我们将流特征选择嵌入到指导一个动态的EP挖掘的过程。这种新方法不仅能处理更高的特征维度,而且在获取整个空间前处理未知的满特征空间也有优势。实验结果验证了我们方法的效率性和高效性。我们计划将我们的新方法应用于真实的卫星图像中来生成无限基于质地(纹理)的特征。
致谢
这个工作有中国国家863项目(2012AA011005)、中国国家自然科学基金(61070131、61175051和61005007)、美国国家科学基金(CCF-0905337),以及美国航天局研究奖(NNX09AK86G)提供支持.
参考文献
[1] C. F. Aliferis, I. Tsamardinos, A. Statnikov & L.E. Brown. (2003)Causal Explorer: a causal probabilistic network learning toolkit for biomedical discovery. METMBS’03.
[2] Roberto J. Bayardo. (1998) Efficiently mining long patterns fromdatabases. SIGMOD’98, 85-93.
[3] J. Bailey, T. Manoukian & K. Ramamohanarao. (2002) Fast algorithms for mining emerging patterns. PKDD’02, 39-50.
[4] J. Bailey, T. Manoukian & K. Ramamohanarao. (2003) A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. ICDM’03, 485-488.
[5] C.L. Blake & C.J. Merz. (1998) UCI Repository of Machine Learning Databases.
[6] H. Fan & K. Ramamohanarao. (2002) An efficient single-scan algorithm for mining essential jumping emerging patterns for classification. PAKDD’02, 456-462.
[7] H. Fan & K. Ramamohanarao. (2006) Fast discovery and the generalization of strong jumping emerging patterns for building compact and accurate classifiers. IEEE Transactions on Knowledge and Data Engineering, 18(6), 721-737.
[8] G. Fang, G. Pandey, W. Wang, M. Gupta, M. Steinbach, & V. Kumar. (2012) Mining low-support discriminative patterns from dense and high-dimensional data. IEEE Transactions on Knowledge and Data Engineering, 24(2), 279 - 294.
[9] G. Dong & J. Li. (1999) Efficient mining of emerging patterns: discovering trends and differences. KDD’99, 43-52.
[10] G. Dong, X. Zhang, L. Wong, & J. Li. (1999) CAEP: Classification by Aggregating Emerging Patterns. DS’99, 30-42.
[11] R. Kohavi & G. H. John. (1997) Wrappers for feature subset selection. Artificial Intelligence, 97, 273-324.
[12] J. Li, G. Dong, & K. Ramamohanarao. (2000) Making use of the most expressive jumping emerging patterns for classification.PAKDD’00, 220-232.
[13] J. Li, G. Dong & K. Ramamohanarao (2000). Instance-based classification by emerging patterns. PKDD’00, 191-200.
[14] W. Li, J. Han, & J. Pei. (2001) CMAR: accurate and efficient classification based on multiple-class association rule. ICDM’01,369–376.
[15] B. Liu, W. Hsu, & Y. Ma. (1998) Integrating classification and association rule mining. KDD’98, 80-86.
[16] D. Lo, H. Cheng, J. Han, S. Khoo, & C. Sun. (2009) Classification of software behaviors for failure detection: a discriminative pattern mining approach. KDD’09, 557-566.
[17] E. Loekito & J. Bailey. (2006) Fast mining of high dimensional expressive contrast patterns using zero suppressed binary decision diagrams. KDD’06, 307–316.
[18] S.Mao & G.Dong. (2005) Discovery of highly differentiative gene groups from microarray gene expression data using the gene club approach. J. Bioinformatics and Computational Biology,3(6):1263-1280.
[19] X. Wu, K.Yu, H. Wang & W. Ding. (2010) Online streaming
feature selection. ICML’10, 1159-1166.
[20] X. Yin & J. Han. (2003) CPAR: classification based on predictive association rule. SDM’03, 369-376.
[21] K. Yu, X. Wu, W. Ding, H. Wang & H. Yao. (2011) Causal associative classification. ICDM’11 , 914-923.
[22] L.Yu & H. Liu. (2004) Efficient feature selection via analysis of relevance and redundancy. J. of Machine Learning Research, 5, 1205-1224.
[23] X. Zhang, G. Dong & K. Ramamohanarao. (2000) Exploring onstraints to efficiently mine emerging patterns from large highdimensional datasets. KDD’00, 310-314.
[24] J. Zhou, D. Foster, R.A. Stine & L.H. Ungar. (2006) Streamwise feature selection. J. of Machine Learning Research, 7, 1861-1885.“

文章评论

程序员的鄙视链
程序员的鄙视链
Java程序员必看电影
Java程序员必看电影
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
如何成为一名黑客
如何成为一名黑客
那些争议最大的编程观点
那些争议最大的编程观点
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员必看的十大电影
程序员必看的十大电影
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员和编码员之间的区别
程序员和编码员之间的区别
我的丈夫是个程序员
我的丈夫是个程序员
旅行,写作,编程
旅行,写作,编程
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
 程序员的样子
程序员的样子
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
总结2014中国互联网十大段子
总结2014中国互联网十大段子
代码女神横空出世
代码女神横空出世
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为什么程序员都是夜猫子
为什么程序员都是夜猫子
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
10个调试和排错的小建议
10个调试和排错的小建议
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
老程序员的下场
老程序员的下场
每天工作4小时的程序员
每天工作4小时的程序员
一个程序员的时间管理
一个程序员的时间管理
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员都该阅读的书
程序员都该阅读的书
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
中美印日四国程序员比较
中美印日四国程序员比较
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
鲜为人知的编程真相
鲜为人知的编程真相
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有