英语原文共 27 页，剩余内容已隐藏，支付完成后下载完整资料
用于特征加权的迭代RELIEF：
算法，理论和应用
Yijun Sun
生物技术研究跨学科中心
电气和计算机工程系
佛罗里达大学
Gainesville, FL 32610-3622
摘要：RELIEF被认为是评估质量最成功的算法之一特征。在本文中，我们提出了一组新的特征加权算法，其性能显着比RELIEF更好，而不会引起计算复杂度的大幅增加。我们的工作从对看似启发式RELIEF算法作为在线方法求解的数学解释具有基于边际的目标函数的凸优化问题。这个解释解释了RELIEF在实际应用中的成功，并使我们能够确定并解决其以下的弱点。RELIEF隐含地假设在原始特征空间中找到的最近邻居是加权空间中的那些，并且RELIEF没有处理异常值数据的机制。 我们建议一个迭代的RELIEF（I-RELIEF）算法，通过探索，减轻RELIEF的不足期望最大化算法框架。 我们将I-RELIEF扩展为多类设置使用新的多类保证金定义。 为了降低计算成本，一个在线学习算法是也开发了。 给出了算法的收敛性分析。 大规模的结果报道了UCI和微阵列数据集上的实验，证明了该方法的有效性提出了算法，并验证了所提出的理论结果。
关键词：特征加权，特征选择，RELIEF，迭代算法，DNA微阵列，分类。
IEEE模式分析与机器智能汇刊
2006年9月提交，2006年11月通过小幅修订
这项工作的初步结果出现在[1]。
请将所有信函寄至：佛罗里达大学生物技术研究所跨学科中心孙义军博士。 框
103622，Gainesville，FL 32610-3622，USA。 电子邮件：sun@dsp.ufl.edu。
一．导言
特征选择是机器学习的基本问题之一。 它不仅适当设计降低系统复杂性和处理时间，但它也可以提高系统性能很多情况下。 对于问题中机器学习算法的成功，它变得更加关键涉及大量不相关的功能。 一个例子是DNA微阵列数据[2]，[3]，其中的特征（基因）的数量通常在数千乃至数万的数量级上，而相信有用基因的数目在数十和数百的范围内。 由于成本高收集大量患者数据，通常只有数十或最多数百个样本为了训练。 在有限的训练样本中，为这些问题选择有用的特征构成了一个问题严重挑战现有的特征选择算法。
特征选择研究在过去的十年中非常活跃[4]，[5]，[6]，[7]，[8]。现有的特征选择算法通常可以基于标准被分类为包装或过滤方法函数用于搜索信息特征[9]。在包装方法中，学习的表现算法用于评估所选特征子集的好处，而在滤波器方法标准中函数通过信息内容来评估特征子集，典型地是类间距离或信息理论措施，而不是直接优化任何指定学习算法的性能。在大多数情况下，过滤器方法在计算上效率要高得多，但性能比封装器差方法。给定一个准则函数，特征选择就减少为搜索问题。一个详尽的搜索是最佳的，但只有当功能数量不是很大时才会有效，因为它很快就会变成随着问题规模的增加，计算不可行。一些启发式组合搜索，例如作为前向和/或后向选择[5]，通常被采用。这些算法显示了一些在实际应用中取得成功。但是，它们都不能提供最佳性的保证。对于更详细的讨论，感兴趣的读者可以参考[7]和其中的参考文献。
组合搜索的计算问题在某种程度上可以通过使用一个特征来缓解加权策略。允许特征权重采用实数值而不是二进制值使用一些完善的优化技术，从而实现高效的算法实现。在现有的特征加权算法中，RELIEF算法[10]是由于其简单性和有效性而被认为是最成功的一个[11]。伪代码的算法如图1所示。RELIEF的主要思想是迭代估计特征权重根据他们区分相邻模式的能力。在每次迭代中，模式x是随机选择，然后找到两个最近的邻居x，一个来自同一个类（称为最近的命中或NH），另一个来自不同的类别（称为最近的命中或NM）。的重量然后更新第i个特征：wi = wi | x（i） - NM（i）（X）| - | x（i）-NH（i）（x）|的。 RELIEF延长了以处理[12]中的嘈杂和缺失的数据，其中对RELIEF的概率解释也是如此提供，说明学习权重接近下列概率：
wi = P（第i个特征| NM的不同值） - P（第i个特征| NH的不同值）。（1）
然而，理解这种解释并不容易，因为方程 （1）不好定义。 为了进一步研究这个问题，在第二部分中，我们提出了一个新的RELIEF解释从优化的角度来看。 我们证明RELIEF是一个在线算法，可以解决一个凸基于边际的目标函数的优化问题。 余量是基于1-NN定义的
RELIEF Algorithm
(1) 初始化: 给定D = {(xn, yn)}
N
n=1, 设 wi = 0, 1 le; i le; I, 迭代次数 T;
(2) for t = 1 : T
(3) 从D中随机选择一个模式x;
(4) 找到x的最近邻居 hit NH(x) and miss NM(x);
(5) for i = 1 : I
(6)计算: wi = wi |x(i) minus; NM(i)(x)| minus; |x(i) minus; NH(i)(x)|;
(7) end
(8) end
（一个最近邻居）分类器[13]。 因此，与过滤方法相比，RELIEF通常执行由于非线性分类器在搜索信息特征时的性能反馈更好;与传统包装方法相比，通过优化凸问题，RELIEF避免了任何问题穷尽的或启发式的组合搜索，因此可以非常有效地实现。 这两个优点使RELIEF特别适用于微阵列数据分析等大规模问题。
RELIEF的新解释使我们能够识别和解决算法的一些弱点。RELIEF的一个主要缺点是最近的邻居是在原始特征空间中定义的，这很可能不是加权空间中的那些。而且，RELIEF没有机制处理异常数据。在存在大量不相关的特征和错误标签的情况下，RELIEF的解决方案质量可能会严重降低。为了缓解这些问题，我们在第三部分提出了一种新的特征加权算法，称为I-RELIEF，遵循的原则是期望最大化（EM）算法[14]。 I-RELIEF对待最近的邻居和身份模式作为隐藏的随机变量，迭代地估计特征权重直到收敛。我们提供I-RELIEF的收敛定理，它表明在一定条件下I-RELIEF收敛于alpha;无论初始起点如何，都是独特的解决方案。我们还将I-RELIEF扩展到多类问题。在第四节，通过使用RELIEF优化基于边际的目标函数的事实，我们提出了一个新的使用新的多类边界定义的多类RELIEF算法。我们也考虑在线学习
为我 - 救济。新提出的I-RELIEF算法基于批量学习。在这种情况下存在大量的训练样本，在线学习在计算上更具吸引力。我们在第五节开发了一个在线I-RELIEF算法，其中还提供了一个收敛定理。验证新提出的算法的有效性并确认已建立的理论结果在本文中，我们在第七节中对9个UCI数据集和6个微阵列进行了大规模实验数据集。我们最后在第八节结束这篇论文。
主要贡献
该论文的主要贡献是双重的：
bull;首先，在算法方面，从对RELIEF的新解释开始，我们提出了一套特征加权算法。 这些算法的有效性，就解决方案的质量而言计算效率，在各种数据集上进行实验演示。考虑到在一些新兴领域对具有大特征维度的数据进行分析的需求增加如生物信息学，我们期望在这些应用中广泛使用这些算法。
bull;第二，在理论方面，本文可能为特征选择研究提供新的方向除了提供一些新的算法。特征选择在机器中起着关键作用学习。然而，与分类器设计相反，它仍然缺乏严格的理论处理。
这很大程度上是由于难以定义可以轻松优化的目标函数通过一些成熟的优化技术。包装方法尤其如此使用非线性分类器来评估所选特征子集的优劣。清晰的分区一个特征集合和一个分类函数的非线性作出了最终的目标函数非凸，甚至不可微分。出于这个原因，大多数特征选择算法依赖于启发式搜索。 I-RELIEF算法具有明确的目标函数，可以解决通过数值分析而不是组合搜索，从而提出了一个有前途的方向对特征选择问题进行更严格的处理。
在转到论文的主体部分之前，我们简要讨论特征冗余。据报道，冗余特征会降低分类性能[9]。因此，进行分类目的，删除多余的功能是必要的。但是，在一些应用程序中，例如DNA微阵列，一些研究人员指出，鉴定一个小的基因子集良好的预测能力可能不足以提供对理解和理解的重要见解建模基因与某些疾病之间的关系[15]。冗余（或共同调节）的基因可以为生物学家提供一些有用的附带信息。而且，在数量庞大的情况下不相关的特征，同时删除不相关的和冗余的特征可能会导致导致算法复杂。因此，我们建议分两个阶段执行任务：第一阶段试图恢复所有相关功能，第二阶段检查更小的功能子集，执行一些计算上更昂贵的算法，例如包装方法以去除冗余如果最终目标是用于分类的话。设计一个精确的特征加权算法可以用在第一阶段是本文的重点。
二．felief算法的优化方法
A.算法
RELIEF作为凸优化问题的在线实现的新解释对其在实际应用中的成功提供了一些见解。 更重要的是，它使我们能够识别算法的一些弱点，并提出一些解决方案来解决它们。 两个主要的缺点RELIEF从方程（1）中定义的目标函数变得清晰。（3）。 首先，最近的邻居是在原始特征空间中定义，这在加权特征空间中可能不是真实的。 其次，由RELIEF优化的目标函数实际上是平均边际。 在异常值的情况下，一些利润率可能会带来很大的负面价值。 在高度嘈杂的数据情况下，有大量不相关的数据特征和/或贴错标签，上述两个问题可能变得如此严重以至于性能的RELIEF可能会大大恶化。
启发式算法，称为RELIEF-F [12]，已被提出来解决第一个问题。 RELIEF-F在计算样本边际时平均K，而不是仅仅一个最近的邻居。实证研究表明RELIEF-F可以比原始的RELIEF有显着的性能提升。至于第二个问题，据我们所知，没有这样的算法存在。一个可能的解决方案是采用SVM [18]和AdaBoost [19]中使用的大幅度概念，其中松弛变量被定义为占非常负的利润率，并且软边际被最大化[20]。为了解决诱导有效的优化问题，需要一个好的线性或二次规划求解器。移动，一个引入了一个非常关键的参数来控制培训绩效和惩罚之间的权衡术语。使用大容量概念进行特征选择似乎是一个有趣的方向，我们将在我们未来的工作中追求。然而，在本文中，我们将仅限于RELIEF框架。下面，我们提出一个分析解决方案来同时解决上述两个问题
我们首先定义两个集合Mn = {i：1le;ile;N，yi6 = yn}和Hn = {i：1le;ile;N，yi = yn，i6 = n}，与每个模式xn相关联。 现在假设对于每个模式xn，其最近的命中和未命中是已知的，其索引保存在集Sn = {（sn1，sn2）}中，其中sn1isin;Mn且sn2isin;Hn。 例如，sn1 = 1，sn2=2意味着xn的最近的miss和hit分别是x1和x2。 我们也表示o = [o1，...，oN]Ť作为一组二进制参数，如果xn是异常值则on = 0，否则为on = 1。在这里，我们使用术语“异常值”来表示错误标记的样本或高度被噪声破坏的样本。我们想要优化的目标函数可以表示为：
，通过使用所得出的结论可以轻松优化此目标函数在第二部分。 当然，，我们不知道集和矢量o。但是，如果我们假设和o的要点是随机变量，我们可以继续推导概率分布的未观测数据。我们首先猜测重量w。 通过使用具有的成对距离在搜索最接近的命中和未命中时计算，即第i个数据点的概率xn的最近错过可以定义为：
类似地，第i个数据点是xn的最接近命中的概率是：
xn为异常值的概率可以定义为：
其中f（·）是一个核函数。一个常用的例子是f(d) = exp(minus;d/sigma;)，核宽度sigma;是用户定义的参数。在整篇论文中，使用指数内核其他内核函数也可以使用，和他们的属性的描述可以在[21]中找到。
现在我们准备推导下面的迭代算法。尽管我们采用EMalgorithm [14]的思想，将未观测的数据视为随机变量，但应该注意的是，下面的方法不是EM算法，因为方程中的目标函数。（7）不是可能性。为了简化说明，我们定义alpha;i,n = Pm(i|xn, w(t) ), beta;i,n = Ph(i|xn, w(t) ), gamma;n = 1 minus; Po(on = 0|D, w(t) ), W = {w : kwk 2 2 = 1, w ge; 0}, mi,n = |xn minus; xi | if i isin; Mn, and hi,n = |xn minus; xi | if i isin; Hn.
Step 1: 在第t次迭代之后，Q函数计算为（1）：
（1）更严格地说，尽管xn可能不是离群值，但Mn和Hn中可能存在离群值，这应该被视为与Q函数不相称。 然而，o中的错误标记对计算裕度的影响要大于Mn和Hn中的标记，其解释如下：考虑公式 （11）：
假设xn是一个例外。 那么边际的价值是完全错误的; 现在假设xn不是异常值，而是Mn中的一个元素。 由于第一个终点rho;〜n是通过对整个Mn集进行平均计算的，因此对边际值的影响不大。 由于I-RELIEF是一个数据预处理算法，并且在各种各样的数据集（c.f. Sec。VII）上表现很好，考虑到Mn和Hn中的错误标记可能不会显着提高性能，但会使算法实施和随后的分析变得复杂化。
I-RELIEF 算法
- 初始化：给定设w（0）= 1 / I，迭代次数T，核宽度sigma;，停止准则theta;;
- for t = 1 : T
- 计算相对于w（t-1）的成对距离;
- 按方程式计算Pm，Ph和Po。 （8），（9）和（10）;
-
根据等式更新权重。（12
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[22627]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
