论文总字数：19266字

目 录

1.绪论 1

1.1研究背景和意义 1

1.2国内外相关研究现状 1

1.3本文的主要研究内容 2

1.4论文组织结构 2

2.基于距离度量的特征选择算法概述 3

2.1距离度量概述 3

2.1.1距离度量的定义 3

2.1.2距离度量的应用 4

2.2特征选择概述 5

2.2.1特征选择的定义 5

2.2.2特征选择的框架 5

2.2.3特征选择的分类 7

3.relief算法及其相关算法实现 8

3.1relief算法 8

3.1.1relief算法概述 8

3.1.2relief算法原理 8

3.1.3matlab实现 9

3.2relieff算法 9

3.2.1relieff算法概述 9

3.2.2relieff算法原理 10

3.2.3matlab实现 11

4.基于互信息的relief算法改进 11

4.1mRMR最大相关最小冗余算法 11

4.2互信息概述 11

4.3relief算法改进 12

5.实验与分析 13

5.1KNN分类器 13

5.2数据集的获取 14

5.3实验结果 14

5.3.1relief和基于互信息relief算法实验 14

5.3.2relieff和基于互信息relieff算法实验 16

5.3实验结果分析 17

6.总结与讨论 17

6.1研究工作总结 17

6.2讨论与展望 18

参考文献 19

致谢 21

基于距离度量的特征分析方法

杨明明

，China

Abstract：Feature selection is an important part of machine learning. It can be said that data and features determine the upper limit of machine learning. Distance measurement is also the key to distance-based machine learning algorithms. The Relief algorithm is considered to be one of the most successful algorithms for evaluating quality based on distance metrics. This paper mainly studies the relief algorithm and relieff algorithm, and removes the high redundancy feature by calculating the mutual information between features, and improves the relief algorithm, which is called mrelief algorithm. Experiments were performed on different data sets. The experimental results show that the mrrelief algorithm has fewer features and high classification accuracy.

Key words：Feature selection, distance metrics, relief, relieff, mrrelief

1.绪论

1.1研究背景和意义

随着互联网的高速发展，我们已经进入数据爆炸时代。每天我们都要通过不同的社交媒体和软件接受大量信息，直到数据挖掘出现后，人们才真正了解到这些数据和信息的价值。数据挖掘指的是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的，是拥有潜在价值的。在数据挖掘的过程中，为了应对和解决一些高维问题，在有限的训练样本中，为这些问题选择有用的特征，很多专家对此进行了广泛研究。

对高维数据集的处理，主要有2种方式进行数据降维：特征提取和特征选择。特征提取指的是对数据集采用线性或者非线性的变换方式，对数据集进行降维；特征选择指的是按照一定的评价标准从原始数据集中选取符合条件的特征，最后得到的是原始数据集的特征子集。假设现在有原始数据集S={，如果经过特征提取之后，即线性变换后，得到的数据集为P={。如果经过特征选择的话，得到的数据集就为Q={。

机器学习，需要使用大量的数据进行建模，因此数据集的处理变得必不可少。一方面随着特征维数的增加，算法的分类性能会不断增加，但是当特征维数达到到一定数目后，特征维数的增加，反而会导致算法精准度和分类性能的下降，这是目前所有的算法的通病，因此原始数据集的处理，作为机器学习的开始步骤，同时也是机器学习最关键的一个步骤，关系到之后的一系列的处理，所以特征选择是一个具有重大意义的研究领域，值得我们投入大量的时间和精力去探索！

1.2国内外相关研究现状

特征选择同样在数据挖掘和机器学习中扮演着举足轻重的角色，它不仅可以降低系统复杂性和处理时间，还可以提高系统性能。特征选择研究在过去的十年间非常活跃，出现了很多特征选择方法，但是由于特征选择方法的多样性和所处理问题的复杂性，至今没有一个固定的选择模式，一个有效的方法以及完美的定义；因此特征选择仍然处于一个不断发展和完善的过程中，需要更多的人去研究去探索。

根据与学习算法的关系，特征选择方法主要分为Filter模型和Wrapper模型两大类，Filter模型主要通过度量对特征进行排序，典型的是类间距离或信息熵，来选择合适的特征；Wrapper模型最早是由john提出，通过分类器对所选择的特征集合进行评价，从而选择合适的特征。Filter模型不是直接优化任何指定学习算法的性能，而是通过特定的度量来评价特征的相关性和重要性，所以基于不同的度量会产生不同的特征选择算法，如基于信息熵的特征选择算法、基于各种距离度量的特征选择算法。在大多数情况下，Filter模型在计算上效率要高很多，但性能比Wrapper模型差。

特征空间中的距离度量也是模式识别领域的核心问题^[29]。R.A.Fisher.在1936年尝试使用不同的度量方式来解决分类问题^[20]。同时期的W.L.G.Koontz和K.Fukunaga提出了一种非线性特征提取方法，这种方法基于距离度量信息^[21]。T.Hastie和R.Tibshirani提出了自适应判别的最近邻分类算法^[22]。20世纪之后，距离度量学习的概念才被正式提出来。

基于距离度量的特征选择算法是一类典型的特征选择算法，通过各种距离来度量特征之间的相关性和重要性，如基于Hellinger距离，欧式距离，曼哈顿距离，切尔雪夫距离，汉明距离等，本文研究的relief系列算法就是基于欧式距离的特征选择算法。

1.3本文的主要研究内容

特征选择算法可以分为单特征搜索和特征子集搜索两大类。单特征算法中最具有代表性的是Relief系列算法，也就是本文的主要研究对象，针对relief系列算法，无法去除高冗余特征的特点，本文提出了改进算法，并针对relief系列算法和改进算法进行了对照实验。

本文的主要研究内容包含以下2个方面：

1. 总结和研究了2种relief算法：relief和relieff算法。分析了它们之间的区别和各自适用的范围和类型。
2. 在relief算法基础上，将得到的高权重特征子集，根据互信息度量计算特征之间的相关度，去除高冗余的特征，从而得到更高质量的特征子集。

1.4论文组织结构

本文一个六章，分为三个部分，第一部分，介绍特征选择和距离度量的相关概念，以及研究现状（包括第1,2章）；第二部分深入介绍了relief和relieff算法，包括它们的概念、原理，以及结合互信息改进了relief算法，并结合实验实现，验证改进算法的优越性。（第3,4,5章）。第三部分总结分析了这次的研究工作，总结了工作中存在的问题，并为以后的工作明确了方向。（第6章）

各章具体安排如下：

第一章，绪论

主要介绍了特征选择和距离度量的背景、意义，以及国内外研究现状。

第二章，基于距离度量的特征选择算法概述

具体介绍了特征选择的定义、框架和分类，以及距离度量的概念和意义。

第三章，relief算法及其相关算法实现

完整的叙述了relief系列算法的发展进程，relief系列算法的原理，对应的公式，伪代码。

第四章基于互信息的relief算法改进

论述了互信息的概念和相关知识，结合互信息对relief系列算法提出了改进。

第五章，实验与分析

挑选了数据集，对传统的relief算法和改进后的relief算法进行对比实验，并对结果进行对照分析。

第六章，总结与讨论

总结了本文的研究内容，分析了存在的问题和不足，明确了未来的研究方向和目标。

2.基于距离度量的特征选择算法概述

2.1距离度量概述

距离度量通常是利用特征对类别的可判别分离性、差异性或者辨别性作为评价标准，因此它也称作类可分准则等^[28]。距离度量又可以划分为几何距离度量和概率距离度量。欧式距离，曼哈顿距离，切尔雪夫距离，汉明距离等都是几何距离度量，而概率距离采用概率形式计算类内和类间的距离。

2.1.1距离度量的定义

距离度量学习的本质是寻找一个度量函数D_M( a, b)使得任意的三个向量 ，， 满足：

1. 非负性D_M (,)0；
2. 自反性D_M (,)=0，当且仅当=；
3. 对称性D_M (,)=D_M (,)；
4. 三角不等式D_M (,) D_M (,)D_M (,)。^[18]

距离度量学习的目的是通过寻找一个合适的距离度量矩阵M，计算d_i，d_j 之间的马氏距离度量：

D_M(d_i，d_j)² =（d_i，d_j）^T M（d_i - d_j） （1）

2.1.2距离度量的应用

如何度量两个实例之间的距离，即距离度量问题，是基于实例的学习方法的核心问题之一。基于实例的学习，包括最近邻学习^[14]、局部加权学习^[15]、基于记忆的推理^[16]，都需要依靠距离度量。距离度量学习同样被广泛应用于模式识别、神经网络、统计学、以及认知心理学等领域^[17]。基于距离度量的特征选择算法是一类典型的特征选择算法，通过各种距离来度量特征之间的相关性和重要性，如基于Hellinger距离，欧式距离，曼哈顿距离，切尔雪夫距离，汉明距离等，本文研究的relief系列算法就是基于欧式距离的特征选择算法。

剩余内容已隐藏，请支付后下载全文，论文总字数：19266字