精华内容
下载资源
问答
  • ​ 从图中提取特征与从正常数据中提取特征完全不同。...​ 从图中获取信息的最简单方法之一是为每个节点创建单独的特性。这些特征可以利用迭代方法从一个较近的邻域和一个较远的K-hop邻域捕获信息。让我们.

    在这里插入图片描述

    ​ 从图中提取特征与从正常数据中提取特征完全不同。图中的每个节点都是相互连接的,这是我们不能忽视的重要信息。幸运的是,许多适合于图的特征提取方法已经创建,这些技术可以分为节点级、图级和邻域重叠级。在本文中,我们将研究最常见的图特征提取方法及其属性。

    ​ 注意:我的文章结构类似于William L. Hamilton[1]所写的图形学习书籍。

    节点级别的特征

    ​ 从图中获取信息的最简单方法之一是为每个节点创建单独的特性。这些特征可以利用迭代方法从一个较近的邻域和一个较远的K-hop邻域捕获信息。让我们开始吧!

    节点的度

    为了计算节点度,将关联边的数量计算到Vr中。

    ​ 节点度是一个简单的度量指标,可以定义为关联到节点的边数。数学上可以定义为:

    节点度方程[1]

    ​ 其中A是邻接矩阵,du是节点u的一个度。这个度量常被用作算法的初始化,用于生成更复杂的图级特征,如weisfeler - lehman核。

    特征向量中心

    不同的中心。左图说明了特征向量的中心。右图显示了度的中心。

    ​ 特征向量中心性度量考虑了2个方面:

    • 节点u的重要性
    • 节点u的相邻节点的重要性

    ​ 换句话说,具有高特征向量中心性的节点应该有许多与其他节点高度连接的邻居。

    ​ 这个度量背后的数学是基于使用矩阵方程的递推算法,相当复杂。我没有告诉你这个数学方程的细节,但如果你对此感兴趣,[1]对这个话题有一个很好的解释(第19页)。

    集聚系数

    计算每个红节点的聚类系数

    ​ 直观地说,我们可以把这个度量看作是节点组之间连接的紧密程度。它测量节点[1]邻域内闭合三角形的比例。节点u的聚类系数可定义为:

    聚类系数方程,摘自[1]

    其中(v1、v2)∈Ɛ意味着节点v1、v2之间的联系。v1和v2被定义为与节点u相邻的任意节点对。

    ​ 我们可以说它是相邻节点之间的边数与节点的相邻节点数(节点度)[1]的比值。当值接近1时,表示节点u的所有邻居都是相连的(图中左侧的黄圈),当值接近0时,表示节点的邻居之间几乎没有任何联系(图中右侧的黄圈)。

    DeepWalk

    DeepWalk以一个图形作为输入,并在R维度中创建节点的输出表示。看看R中的“映射”是如何将不同的簇分开的。

    ​ 它是一种基于学习的方法,将一个图作为输入,并学习节点[4]的表示和输出。它将语言建模中使用的技术重新应用到图形领域。该算法主要包括两个部分:

    • DeepWalk
    • SkipGram

    ​ 在DeepWalk中,我们使用一个随机生成器来生成节点的短序列。然后,SkipGram使用生成的节点序列将节点编码到低维空间中。

    ​ DeepWalk算法有点难以理解,所以我建议看看他们的原始论文(http://www.perozzi.net/publications/14_kdd_deepwalk.pdf)

    图的层次特性

    ​ 如果我们想要获取整个图的信息,而不是查看单个节点,该怎么办呢?幸运的是,有许多可用的方法可以聚合关于整个图的信息。从简单的方法,如邻接矩阵,到更复杂的内核,如weisfeler - lehman内核,或基于路径的内核。从图中提取全局信息的方法有很多种;在本节中,我们将探讨最常见的一些。

    邻接矩阵

    邻接矩阵是一个稀疏矩阵,其中“1”表示两个节点之间存在连接。

    ​ 这是一个常见的特征。是一个稀疏矩阵,它包含关于两个节点之间连接的信息。如果有“1”,则表示两个特定节点之间存在连接。矩阵中的a_ij元素中i是行,j是列,表示节点Vi和Vj之间是否有连接。

    拉普拉斯矩阵

    ​ 拉普拉斯矩阵包含与邻接矩阵相同的关于连通性的信息,但方式略有不同。简单定义为:

    拉普拉斯算子的矩阵方程。L -拉普拉斯矩阵,D度矩阵,A -邻接矩阵

    ​ 式中,L为拉普拉斯矩阵,D为度矩阵,A为邻接矩阵。度矩阵是一个简单的对角矩阵,对角线上的每个元素表示每个节点有多少个邻居。

    节点的度量

    ​ 它不是一个单一的度量,而是一种类型。它背后的算法非常简单——我们只是以[1]的某种方式聚合节点级别的特性。例如,我们可以取节点度数的平均值,或者取边缘连接的直方图。

    Weisfeiler-Lehman内核

    ​ WL内核是对节点度量方法的改进,在这种方法中,我们从节点的邻近点迭代地聚合信息[1]。

    ​ 该算法可归纳为以下几个步骤[1]:

    • 为图中的每个节点设置一个初始标签,例如节点的度数
    • 使用邻域的散列标签,通过迭代为每个节点分配新标签
    • 经过K次迭代,我们现在已经收集了K-hop邻域的信息。然后我们可以使用任何类型的节点度量来总结这些新标签

    ​ 这个内核在化学信息学中应用非常广泛,它经常应用于分子数据。例如,循环指纹算法就是基于WL核的。

    Graphlet内核

    从图中计算所有可能的核大小为3的图。

    ​ Graphlet构造大小k∈{3,4,5}的小子图。graphlet内核背后的思想很简单:遍历所有图可能是一个NP难问题,因此通过其他的技术,比如对固定数量的图形进行采样,以降低计算复杂度[5]。在数学上,graphlet kernel定义如下:

    graphlet内核的定义。G - 图, G ' - 另一张图, f_G -向量,其中第i个分量对应于graphlet_i的出现。

    ​ G和G '是我们可以比较的不同的图。f_G和f_G '是向量,其中第i个元素对应于某个graphlet_i[5]的出现频率。我们可以将这些向量归一化,以考虑较小尺寸的图形[5]的较高频率计数:

    ​ Graphlet核在生物信息学和化学信息学中被广泛使用,在这些领域中,了解用图表示的分子中某些子结构出现的频率特别有用。

    基于路径的内核

    ​ 基于路径的核通过在图的标记节点和边缘上应用随机漫步或最短路径来创建特征向量[7,8]。这个内核的算法与graphlet内核类似,但是我们研究的不是graphlet,而是图中的不同路径[1]。使用随机漫步的基于路径的内核将检查随机生成的路径。那些基于最短路径的,只研究连接两个节点的最短路径。

    优秀算法

    ​ 还有更多的算法/模型可以创建图形级别的特性。其他包括GraphHopper内核、神经消息传递或图卷积网络。

    社区重叠特征

    ​ 节点级和图级特性无法收集邻近节点之间的相关信息[1]。邻域重叠特征帮助我们预测两个节点之间是否有连接及其类型,并测量了图中局部和全局的重叠。

    区域重叠

    ​ 局部重叠度量是量化两个节点之间邻域的相似性的度量。这些度量标准中的大多数都非常相似,只是在标准化常数方面略有不同[1]。

    ​ 例如,节点u与v之间的Sorenson索引计算公式如下:

    节点u和v之间的索伦森指数方程中的分子计算这些节点之间的共同邻居。分母是一个标准化常数,是节点度数的总和。

    ​ 分子项计算这些节点之间的共同邻居。分母项(d_u + d_v)/2是节点度数的平均值。

    ​ 另一个度量标准,如Salton索引、Hub提升索引或Jaccard索引与Sorensen索引的不同之处在于标准化常数。

    ​ 一个稍微不同的度量是资源分配(RA)索引。它度量了节点u和v之间共同邻居的重要性[1]。它是通过对所有共同邻居的节点度的倒数求和来实现的。

    资源分配索引。

    全局重叠

    全局重叠度量检查节点是否属于图中的同一个社区。

    ​ 如果某些节点属于图中的同一社区,则全局重叠度量将获取该信息。我们不再只关注两个相邻的节点,而是查看来自更遥远的邻域的节点,并检查它们是否属于图中相同的社区。

    ​ 常用的方法之一是Katz索引,它计算两个特定节点之间所有可能的路径:

    Katz索引。

    ​ 邻接矩阵A有一个有趣的性质。它的i次幂表示在两个节点uv之间是否有一条长度为i的路径[10]。β一种标准化常数,在这里我们可以选择路径长度(即短或长)。

    ​ 节点的度越高[1],Katz指数就会产生越高的相似度得分。为了克服这一问题,提出了考虑这种偏差的LHN相似度度量:

    LHN相似性度量。

    ​ 该度量通过邻接矩阵的期望值进行标准化。

    总结

    ​ 我们已经看到了可以从图中提取的三种主要类型的特征:节点级、层次级和邻域重叠特征。节点级特征(如节点度)或特征向量中心性为每个单独的节点生成特征,而图级特征(如WL或Graphlet内核)从整个图中捕获信息。邻域重叠特征,例如,Sorensen索引或LHN相似性,创建了度量两个节点之间共同邻域的特征。

    ​ 在本文中,我总结了最流行的图形特征提取方法。当然,还有很多,我没有在这里说。如果你想深入了解这个话题,你可以在参考资料部分找到非常有用的文献:)

    ​ 感谢您阅读本文。我希望这对你有用!

    引用

    [1] Graph Representation Learning Book by William L. Hamilton

    [2] On Node Features for Graph Neural Networks

    [3] Survey on Graph Kernels

    [4] DeepWalk: Online Learning for Social Representations

    [5] Efficient graphlet kernels for large graph comparison

    [6] Graphlet Kernels (ETH Lecture Notes)

    [7] Marginalized Kernels Between Labelled Graphs

    [8] Shortest-path kernels on graphs

    [9] Community structure in social and biological networks

    [10] Katz Centrality within a social network.)

    翻译:孟翔杰

    原文链接:https://towardsdatascience.com/feature-extraction-for-graphs-625f4c5fb8cd

    展开全文
  • 数据特征的选取

    万次阅读 2017-09-14 14:50:36
    对后续图像分类有着重要的影响,并且对于图像数据具有样本少,维数高特点,要从图像中提取有用的信息,必须对图像特征进行降维处理,特征提取与特征选择就是有效降维方法,其目的是得到一个反映数据本质结构、...
    图像特征的提取和选择是图像处理过程中很重要的环节,对后续图像分类有着重要的影响,并且对于图像数据具有样本少,维数高的特点,要从图像中提取有用的信息,必须对图像特征进行降维处理,特征提取与特征选择就是最有效的降维方法,其目的是得到一个反映数据本质结构、识别率更高的特征子空间 。

    一.原始特征提取

    1.图像的基本特征

    • 颜色特征
    • 形状特征
    • 纹理特征
    • 空间关系特征

    2.基于颜色特征的提取方法 

    • 颜色直方图
    • 颜色集,是对颜色直方图的一种近似,其将图像表达为一个二进制的颜色索引集
    • 颜色矩,其将图像中任何的颜色分布用它的矩来表示
    • 颜色聚合向量
    • 颜色相关图
    颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。由于颜色对图像或图像区域的方向、大小等变化不敏感,所以颜色特征不能很好的捕捉图像中对象的局部特征。另外,仅使用颜色特征查询时,如果数据库很大,常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法,其优点是不受图像旋转和平移变化的影响,进一步借助归一化还可不受图像尺度变化的影响,基缺点是没有表达出颜色空间分布的信息。

    3.基于纹理特征的提取方法

    • 基于统计的灰度共生矩阵和能量谱函数法
    • 几何法,例如基于图像基元的结构化方法
    • 模型法,以图像的构造模型为基础,采用模型参数作为纹理特征,典型的方法有随机场模型法
    • 信号处理法,例如,小波变换
    纹理特征也是一种全局特征,它也描述了图像或图像区域所对应景物的表面性质。作为一种统计特征,纹理特征常具有旋转不变性,并且对于噪声有较强的抵抗能力。但纹理只是一种物体表面的特性,无法完全反映出物体的本质属性,所以仅利用纹理特征无法获得高层次图像内容,且纹理特征还有一个很明显的缺点是当图像的分辨率变化的时候,所计算出来的纹理可能会有较大偏差。

    4.基于形状特征的提取方法

    • 基于边界的,例如Hough变换,傅里叶变换等
    • 基于区域的,例如矩不变量,几何矩特征,转动惯量等
    • 其他方法,例如有限元法,旋转函数和小波描述符等
    基于形状特征的检索方法都可以比较有效地利用图像中感兴趣的目标来进行检索 ,但也存在一些问题,例如当目标有变形时检索结果就不太可靠,且许多形状特征仅描述了目标的局部特征,对全面描述目标有较高的时间和空间要求等。

    5.基于空间关系的特征提取方法

    空间关系,是指图像中分割出来的多个目标之间的相互的空间位置或相对方向关系,这些关系可分为连接/邻接关系、交叠/重叠关系和包含/包容关系等。提取图像空间关系特征可以有两种方法:一种方法是首先对图像进行自动分割,划分出图像中所包含的对象或颜色区域,然后根据这些区域提取图像特征,并建立索引;另一种方法则简单地将图像均匀地划分为若干规则子块,然后对每个图像子块提取特征,并建立索引。
    空间关系特征的使用可加强对图像内容的描述区分能力,但空间关系特征常对图像或目标的旋转、反转、尺度变化等比较敏感。另外,实际应用中,仅仅利用空间信息往往是不够的,不能有效准确地表达场景信息。

    6.小结

    上述特征提取方法是图像特征的初步获取,其各有利弊。针对不同的实际问题,可选择适当的图像特征提取方法。但有时仅用单一的特征来进行图像检索或匹配,其结果准确度不高,为了提高准确度,有人提出了多特征融合的图像检索或匹配技术。

    二.特征提取

    对于初步获取的图像特征,可能维数依然很大,且可能包含一定的无关或冗余特征。这里的特征提取是指从初步获取的原始特征中通过一定的数学运算得到一组新的特征也称作特征变换,其可以有效的降低特征空间维数和消除特征之间可能存在的相关性,减少特征中的无用信息。

    1.特征提取的基本方法

    • 线性方法,如主成分分析法(PCA),线性判别分析法(LDA),多维尺度法(MDS)
    • 非线性方法,如核方法(KPCA,KDA),流型学习
    2.主成分分析法
    PCA方法是从一组特征中通过求解最优的正交变换,得到一组相互间方差最大的新特征,它们是原始特征的线性组合,且相互之间是不相关的,再对新特征进行重要性排序,选取前几个主成分。用较少的主成分来表示数据,可以实现特征的降维,还可以消除数据中的噪声。该算法不考虑样本的类别信息,是一种无监督的方法。
    3.线性判别方法
    该方法基本思想是将高维的数据样本投影到最佳判别的矢量空间,以达到提取分类信息和压缩特征空间维数的效果,投影后保证数据样本在新的子空间类间距离最大和类内距离最小,即样本数据在该空间中有最佳的可分离性。Fisher线性判别分析是最具有代表性的LDA 法。
    4.多维尺度法
    MDS是一种很经典的数据映射方法,其根据样本之间的距离关系或不相似度关系在低维空间里生成对样本的一种表示。MDS分为度量型和非度量型两种,度量型MDS把样本间的距离关系或不相似度关系看作一种定量的度量,尽可能的在低维空间里保持这种度量关系;非度量型MDS把样本间的距离关系或不相似度关系看作一种定性的关系,在低维空间里只需保持这种关系的顺序。
    5.核主成分分析法
    该方法对样本进行非线性变换,通过在变换空间进行主成分分析来实现在原空间的非线性主成分分析。根据可再生希尔伯特空间的性质,在变换空间中的协方差矩阵可以通过原空间中的核函数进行运算,从而绕过复杂的非线性变换。核方法对于不同的问题选择合适的核函数类型,不同的核函数类型反映了对数据分布的不同假设,也可以看作是对数据引入了一种非线性距离度量。
    6.基于流型学习的方法
    其基本思想是通过局部距离来定义非线性距离度量,在样本分布较密集的情况下可以实现各种复杂的非线性距离度量。具体方法有:
    • 等容特征映射(IsoMap)--欧氏距离累加
    • 局部线性嵌入(LLE)--近邻样本线性重构
    • 拉普拉斯特征映射(LE)--邻域选取和样本间相似度表达
    • 其他改进算法

    三.特征选择

    特征选择也是降低特征空间维数的一种基本方法,它是用计算的方法从一组给定的特征中选出能够有效识别目标的最小特征子集。与特征提取最本质的区别就是特征提取主要是从原特征空间到新特征空间的一种变换,特征提取到的子特征会失去对类别原有主观意义的具体解释,而特征选择可以保持对这中具体意义的解释。

    1.特征选择的基本步骤

    • 候选特征子集的生成(搜索策略)
    • 子集评价(评价准则)
    • 停止准则
    • 结果验证
    2.特征选择方法分类
    根据搜索策略和评价准则的不同,可对特征选择方法进行如下分类:

    按搜索策略分:

    • 基于全局寻优的分支定界法
    该方法是一种从包含所有候选特征开始,逐步去掉不被选中的特征的自顶向下的方法,具有回溯的过程,能够考虑到所有可能的组合。
    其基本思想是:设法将所有可能的特征组合构建成一个树状结构,按照特定的规律对树进行搜索,使得搜索过程尽可能早的达到最优解而不必遍历整棵树。
    要做到这一点必须要求准则判据对特征具有单调性,且当处理高维数据时,算法复杂度较高,所以很难广泛使用。
    • 基于启发式搜索的方法
    很多情况下,即使采取分支定界法,全局寻优的方法计算量可能仍然很大,因此提出了一些基于启发式搜索的次优选择算法:单独最优特征组合,序列前向选择(SFS)及广义的SFS(GSFS),序列后向选择(SBS)及广义的SBS(GSFS),增l去r选择及广义的增l去r选择方法,浮动搜索方法及浮动的广义后向选择方法(FGSBS)等。
    • 随机搜索方法
    该类方法在计算中将特征选择问题与遗传算法、模拟退火算法、粒子群优化算法,随机森林或一个随机重采样过程结合起来,以概率推理和采样过程作为算法基础,基于分类估计的有效性,在算法运行过程中对每个特征赋予一定的权重,再根据给定的或自适应的阈值对特征的重要性进行评价。例如,Relief及其扩展算法就是一种典型的根据权重选择特征的随机搜索方法,它能有效的去掉无关特征,但不能去除冗余特征,且只能用于两类分类问题。

    按评价准则分:

    特征选择方法依据是否独立于后续的学习算法可分为过滤式(Filter)和封装式(Wrapper)和嵌入式(Embedded)三种。Filter方式独立于学习算法,直接利用训练数据的统计特性来评估特征。Wrapper方式利用学习算法的训练准确率来评价特征子集。Embedded方式结合了Filter和Wrapper方式。
    • Filter方式
    Filter式的特征选择方法一般使用评价准则来使特征与类别间的相关性最大,特征间的相关性最小。该方式可以很快的排除掉很多不相关的噪声特征,缩小优化特征子集搜索的规模,计算效率高,通用性好,可用作特征的预筛选器。但当特征和分类器息息相关时,该方法不能保证选择出一个优化特征子集,即使能找到一个满足条件的优化子集,其计算规模也比较大。根据评价函数可分为四类:
    a.基于距离度量的
    常用的距离度量有:欧氏距离,Minkowski距离,Chebychev距离和平方距离等。
    Relief及其扩展算法ReliefF和RRelidfF,分支定界法和BFF算法都是基于距离度量的特征选择算法。
    b.基于信息度量的
    常用信息度量:信息增益与互信息信息增益:可以有效的选出关键特征,剔除无关特征;互信息:描述两个随机变量之间相互依存关系的强弱,常见算法如下:
    • 基于互信息的MIFS算法
    • 基于最小冗余最大相关(mRMR)的方法
    • 基于互信息的快速滤波算法FCBF
    • 基于条件互信息的CMIM算法
    • 基于动态互信息的特征选择算法
    由于信息熵理论不要求假定数据分布是已知的能够以量化的形式度量特征间的不确定程度,且能有效地度量特征间的非线性关系,基于信息度量的特征选择算法成为近年来研究的热点,提出了许多基于信息理论的改进算法。
    c.基于依赖性度量的
    该方法利用一些统计相关系数,如Pearson相关系数,Fisher得分,方差得分,t检验,秩和检验或Hilbert-Schmidt依赖性准则等来度量特征相对于类别可分离性间的重要性程度。有人提出了一种基于稀疏表示的特征选择方法,且在人脸图像聚类实验中取得了较好的结果。
    d.基于一致性度量的
    该方法其思想是寻找全集有相同区分能力的最小子集,尽可能保留原始特征的辨识能力。它具有单调、快速、去除冗余和不相关特征、处理噪声等优点,但其对噪声数据敏感,且只适合处理离散特征。
    典型的算法有Focus,LVF等。
    • Wrapper方式
    Wrapper方式依据选择子集最终被用于构造分类模型,把特征选择算法作为学习算法的一个组成部分,直接使用训练结果的准确率作为特征重要性程度的评价标准。该方法在速度上要比Filter方式慢,但它所选的优化特征子集规模相对要小的多,非常有利于关键特征的辨识;同时其准确率比较高,但泛化能力较差,时间复杂度较高。
    目前,关于Wrapper方式的研究也比较多,例如:
    Hsu等人用决策树来进行特征选择,采用遗传算法来寻找使得决策树分类错误率最小的一组特征子集
    Chiang等人将Fisher判别分析与遗传算法结合,用于化工故障过程中辨识关键变量,其效果也不错。
    Guyon等人利用支持向量机的分类性能衡量特征的重要性,最终构造了一个分类性能较高的分类器。
    Krzysztof提出了一种基于相互关系的双重策略的Wrapper特征选择方法FFSR(fast feature subset ranking),以特征子集作为评价单位,以子集收敛能力作为评价标准
    戴平等人提出了一种基于SVM的快速特征选择方法
    • Embedded方式
    针对Filter和Wrapper方式的利弊,提出了Embedded方式的特征选择方法,该方式先用filter方法初步去掉无关或噪声特征,只保留少量特征,减少后续搜索规模,然后再用Wrapper方法进一步优化,选择分类准确率最高的特征子集。例如,Li G-Z等人先使用互信息度量标准和随机重采样技术获取前k个重要特征,再使用SVM构造分类器。

    四.总结

    从图像中提取特征,首先根据具体的问题,判断选取的图像特征,如颜色或纹理。针对不同的特征选择具体的提取方法,如常用的基于颜色特征的颜色直方图或基于纹理的灰度共生矩阵和小波变换等。这是第一步对图像原始特征的提取。由于原始特征可能维数很高,或包含大量的冗余特征和无关特征,会使后续算法的计算复杂度变得很高,所以进一步进行特征提取和特征选择,抽取样本最相关特征,降低数据维数和消除不相关特征和冗余特征。
    统计意义上的特征提取是由获取到的原始特征经过线性或非线性变换得到较少数量且更具有的表达能力的新特征。常用的线性变换有PCA、LDA、MDS,非线性变换有KPCA、流型学习等。有时基本的特征提取方法由于自身的局限性或不能满足在某些具体问题中的要求,就需要对这些方法进行改进。例如,PCA不考虑样本类别,因此得到的低维空间相对判别分类而言不是最优的;在样本类内分布为高斯分布且协方差相同时,LDA可以得到最优线性判别分析转换矩阵,但现实世界中类内分布的复杂度远远超出了高斯分布;MDS方法中目标函数的定义及对该目标函数最小化选择适合的优化方法;KPCA方法中核函数的选择与核函数的参数设定等,都需要根据具体的情况选择与设定;关于流型学习中的各种方法,在样本分布较稀疏时,对近邻样本间距离的度量可能会有较大的偏差。
    特征提取技术很难解释新特征与样本类别之间的相互关系,但在某些领域内对这种相互关系的理解却很重要,所以,在这种情况下,特征选择就更加有效。特征选择是指从原始特征中选择最少的特征,使所选特征与类别之间具有最大相关度,特征与特征之间具有最小相关度。根据评价标准是否依赖于具体的学习算法,特征选择算法分为Filter,Wrapper,Embedded三种方式。Filter方式依据数据内在的结构特征选择最相关的特征,该方式主要是选取对样本距离及相关性的度量准则。直接依赖学习算法准确率的Wrapper方式,主要是对学习算法的选择,通常选择SVM作为评估标准。Embeded方式将特征选择视为学习算法的子系统,该算法计算复杂度介于Wrapper和Filter方式之间,选择的特征比Filter方式更准确,但需要与新设计的算法相结合。
    最后,获取特征子集的选择策略,在高维样本空间对所有候选子集进行评估测试是不实际的。最优特征选择算法-分支界定法不仅对准则判据有要求,且计算量还是很大,所以又提出了基于启发式的次优选择算法,还可以利用一些群智能的随机搜索算法,例如GA、PSO、SAA,可以更好的提高搜索效率。

    展开全文
  • 机器学习的特征工程

    2019-08-13 16:20:12
    1,特征工程的重要性。 好数据 >...模型更精准:好的特征是数据中抽取出来对预测结果最有用的信息 3,特征提取总结: 特征设计时需要与目标高度相关,应考虑以下三个问题: 这个特征对于目标是否有...

    1,特征工程的重要性。
    好数据 > 多数据 > 好算法。
    数据和特征决定了模型预测的上限,而算法只是逼近这个算法而已。
    应用机器学习基本上就是特征工程。

    2,什么是好的特征?–少而精!
    模型更简单:同样的模型精度选择更简单的模型
    模型更精准:好的特征是数据中抽取出来的对预测结果最有用的信息

    3,特征提取的总结:
    特征设计时需要与目标高度相关,应考虑以下三个问题:
    这个特征对于目标是否有用?
    如果有用,这个特征重要程度如何?
    这个特征的信息是否在其他的特征上体现过?
    特征设计需要一定的领域知识、直觉和数学知识
    初始提取特征后还需要进行特征转换处理后,再进入算法模型
    特征设计和提取需要不断进行反复的迭代验证,需要大量时间

    4,特征提取。
    1,文本特征提取。
    词袋模型
    TFIDF
    2,图像特征提取。

    参考链接:https://www.zybuluo.com/rianusr/note/1156011

    展开全文
  • 特征选择是挖掘高维数据的重要预处理步骤。 它旨在确定最有用的功能,以实现紧凑,准确数据表示。 由于典型受监督特征选择方法比无监督方法具有更好性能,在无监督方法中,使用类标签作为受监督信息。 除类...
  • 图像特征提取与特征选择基本方法总结

    万次阅读 多人点赞 2014-09-18 11:19:05
    对后续图像分类有着重要的影响,并且对于图像数据具有样本少,维数高特点,要从图像中提取有用的信息,必须对图像特征进行降维处理,特征提取与特征选择就是有效降维方法,其目的是得到一个反映数据本质结构、...
    图像特征的提取和选择是图像处理过程中很重要的环节,对后续图像分类有着重要的影响,并且对于图像数据具有样本少,维数高的特点,要从图像中提取有用的信息,必须对图像特征进行降维处理,特征提取与特征选择就是最有效的降维方法,其目的是得到一个反映数据本质结构、识别率更高的特征子空间 。

    一.原始特征提取

    1.图像的基本特征

    • 颜色特征
    • 形状特征
    • 纹理特征
    • 空间关系特征

    2.基于颜色特征的提取方法 

    • 颜色直方图
    • 颜色集,是对颜色直方图的一种近似,其将图像表达为一个二进制的颜色索引集
    • 颜色矩,其将图像中任何的颜色分布用它的矩来表示
    • 颜色聚合向量
    • 颜色相关图
    颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。由于颜色对图像或图像区域的方向、大小等变化不敏感,所以颜色特征不能很好的捕捉图像中对象的局部特征。另外,仅使用颜色特征查询时,如果数据库很大,常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法,其优点是不受图像旋转和平移变化的影响,进一步借助归一化还可不受图像尺度变化的影响,基缺点是没有表达出颜色空间分布的信息。

    3.基于纹理特征的提取方法

    • 基于统计的灰度共生矩阵和能量谱函数法
    • 几何法,例如基于图像基元的结构化方法
    • 模型法,以图像的构造模型为基础,采用模型参数作为纹理特征,典型的方法有随机场模型法
    • 信号处理法,例如,小波变换
    纹理特征也是一种全局特征,它也描述了图像或图像区域所对应景物的表面性质。作为一种统计特征,纹理特征常具有旋转不变性,并且对于噪声有较强的抵抗能力。但纹理只是一种物体表面的特性,无法完全反映出物体的本质属性,所以仅利用纹理特征无法获得高层次图像内容,且纹理特征还有一个很明显的缺点是当图像的分辨率变化的时候,所计算出来的纹理可能会有较大偏差。

    4.基于形状特征的提取方法

    • 基于边界的,例如Hough变换,傅里叶变换等
    • 基于区域的,例如矩不变量,几何矩特征,转动惯量等
    • 其他方法,例如有限元法,旋转函数和小波描述符等
    基于形状特征的检索方法都可以比较有效地利用图像中感兴趣的目标来进行检索 ,但也存在一些问题,例如当目标有变形时检索结果就不太可靠,且许多形状特征仅描述了目标的局部特征,对全面描述目标有较高的时间和空间要求等。

    5.基于空间关系的特征提取方法

    空间关系,是指图像中分割出来的多个目标之间的相互的空间位置或相对方向关系,这些关系可分为连接/邻接关系、交叠/重叠关系和包含/包容关系等。提取图像空间关系特征可以有两种方法:一种方法是首先对图像进行自动分割,划分出图像中所包含的对象或颜色区域,然后根据这些区域提取图像特征,并建立索引;另一种方法则简单地将图像均匀地划分为若干规则子块,然后对每个图像子块提取特征,并建立索引。
    空间关系特征的使用可加强对图像内容的描述区分能力,但空间关系特征常对图像或目标的旋转、反转、尺度变化等比较敏感。另外,实际应用中,仅仅利用空间信息往往是不够的,不能有效准确地表达场景信息。

    6.小结

    上述特征提取方法是图像特征的初步获取,其各有利弊。针对不同的实际问题,可选择适当的图像特征提取方法。但有时仅用单一的特征来进行图像检索或匹配,其结果准确度不高,为了提高准确度,有人提出了多特征融合的图像检索或匹配技术。

    二.特征提取

    对于初步获取的图像特征,可能维数依然很大,且可能包含一定的无关或冗余特征。这里的特征提取是指从初步获取的原始特征中通过一定的数学运算得到一组新的特征也称作特征变换,其可以有效的降低特征空间维数和消除特征之间可能存在的相关性,减少特征中的无用信息。

    1.特征提取的基本方法

    • 线性方法,如主成分分析法(PCA),线性判别分析法(LDA),多维尺度法(MDS)
    • 非线性方法,如核方法(KPCA,KDA),流型学习
    2.主成分分析法
    PCA方法是从一组特征中通过求解最优的正交变换,得到一组相互间方差最大的新特征,它们是原始特征的线性组合,且相互之间是不相关的,再对新特征进行重要性排序,选取前几个主成分。用较少的主成分来表示数据,可以实现特征的降维,还可以消除数据中的噪声。该算法不考虑样本的类别信息,是一种无监督的方法。
    3.线性判别方法
    该方法基本思想是将高维的数据样本投影到最佳判别的矢量空间,以达到提取分类信息和压缩特征空间维数的效果,投影后保证数据样本在新的子空间类间距离最大和类内距离最小,即样本数据在该空间中有最佳的可分离性。Fisher线性判别分析是最具有代表性的LDA 法。
    4.多维尺度法
    MDS是一种很经典的数据映射方法,其根据样本之间的距离关系或不相似度关系在低维空间里生成对样本的一种表示。MDS分为度量型和非度量型两种,度量型MDS把样本间的距离关系或不相似度关系看作一种定量的度量,尽可能的在低维空间里保持这种度量关系;非度量型MDS把样本间的距离关系或不相似度关系看作一种定性的关系,在低维空间里只需保持这种关系的顺序。
    5.核主成分分析法
    该方法对样本进行非线性变换,通过在变换空间进行主成分分析来实现在原空间的非线性主成分分析。根据可再生希尔伯特空间的性质,在变换空间中的协方差矩阵可以通过原空间中的核函数进行运算,从而绕过复杂的非线性变换。核方法对于不同的问题选择合适的核函数类型,不同的核函数类型反映了对数据分布的不同假设,也可以看作是对数据引入了一种非线性距离度量。
    6.基于流型学习的方法
    其基本思想是通过局部距离来定义非线性距离度量,在样本分布较密集的情况下可以实现各种复杂的非线性距离度量。具体方法有:
      • 等容特征映射(IsoMap)--欧氏距离累加
      • 局部线性嵌入(LLE)--近邻样本线性重构
      • 拉普拉斯特征映射(LE)--邻域选取和样本间相似度表达
      • 其他改进算法

    三.特征选择

    特征选择也是降低特征空间维数的一种基本方法,它是用计算的方法从一组给定的特征中选出能够有效识别目标的最小特征子集。与特征提取最本质的区别就是特征提取主要是从原特征空间到新特征空间的一种变换,特征提取到的子特征会失去对类别原有主观意义的具体解释,而特征选择可以保持对这中具体意义的解释。

    1.特征选择的基本步骤

    • 候选特征子集的生成(搜索策略)
    • 子集评价(评价准则)
    • 停止准则
    • 结果验证
    2.特征选择方法分类
    根据搜索策略和评价准则的不同,可对特征选择方法进行如下分类:

    按搜索策略分:

      • 基于全局寻优的分支定界法
    该方法是一种从包含所有候选特征开始,逐步去掉不被选中的特征的自顶向下的方法,具有回溯的过程,能够考虑到所有可能的组合。
    其基本思想是:设法将所有可能的特征组合构建成一个树状结构,按照特定的规律对树进行搜索,使得搜索过程尽可能早的达到最优解而不必遍历整棵树。
    要做到这一点必须要求准则判据对特征具有单调性,且当处理高维数据时,算法复杂度较高,所以很难广泛使用。
      • 基于启发式搜索的方法
    很多情况下,即使采取分支定界法,全局寻优的方法计算量可能仍然很大,因此提出了一些基于启发式搜索的次优选择算法:单独最优特征组合,序列前向选择(SFS)及广义的SFS(GSFS),序列后向选择(SBS)及广义的SBS(GSFS),增l去r选择及广义的增l去r选择方法,浮动搜索方法及浮动的广义后向选择方法(FGSBS)等。
      • 随机搜索方法
    该类方法在计算中将特征选择问题与遗传算法、模拟退火算法、粒子群优化算法,随机森林或一个随机重采样过程结合起来,以概率推理和采样过程作为算法基础,基于分类估计的有效性,在算法运行过程中对每个特征赋予一定的权重,再根据给定的或自适应的阈值对特征的重要性进行评价。例如,Relief及其扩展算法就是一种典型的根据权重选择特征的随机搜索方法,它能有效的去掉无关特征,但不能去除冗余特征,且只能用于两类分类问题。

    按评价准则分:

    特征选择方法依据是否独立于后续的学习算法可分为过滤式(Filter)和封装式(Wrapper)和嵌入式(Embedded)三种。Filter方式独立于学习算法,直接利用训练数据的统计特性来评估特征。Wrapper方式利用学习算法的训练准确率来评价特征子集。Embedded方式结合了Filter和Wrapper方式。
      • Filter方式
    Filter式的特征选择方法一般使用评价准则来使特征与类别间的相关性最大,特征间的相关性最小。该方式可以很快的排除掉很多不相关的噪声特征,缩小优化特征子集搜索的规模,计算效率高,通用性好,可用作特征的预筛选器。但当特征和分类器息息相关时,该方法不能保证选择出一个优化特征子集,即使能找到一个满足条件的优化子集,其计算规模也比较大。根据评价函数可分为四类:
    a.基于距离度量的
    常用的距离度量有:欧氏距离,Minkowski距离,Chebychev距离和平方距离等。
    Relief及其扩展算法ReliefF和RRelidfF,分支定界法和BFF算法都是基于距离度量的特征选择算法。
    b.基于信息度量的
    常用信息度量:信息增益与互信息信息增益:可以有效的选出关键特征,剔除无关特征;互信息:描述两个随机变量之间相互依存关系的强弱,常见算法如下:
      • 基于互信息的MIFS算法
      • 基于最小冗余最大相关(mRMR)的方法
      • 基于互信息的快速滤波算法FCBF
      • 基于条件互信息的CMIM算法
      • 基于动态互信息的特征选择算法
    由于信息熵理论不要求假定数据分布是已知的能够以量化的形式度量特征间的不确定程度,且能有效地度量特征间的非线性关系,基于信息度量的特征选择算法成为近年来研究的热点,提出了许多基于信息理论的改进算法。
    c.基于依赖性度量的
    该方法利用一些统计相关系数,如Pearson相关系数,Fisher得分,方差得分,t检验,秩和检验或Hilbert-Schmidt依赖性准则等来度量特征相对于类别可分离性间的重要性程度。有人提出了一种基于稀疏表示的特征选择方法,且在人脸图像聚类实验中取得了较好的结果。
    d.基于一致性度量的
    该方法其思想是寻找全集有相同区分能力的最小子集,尽可能保留原始特征的辨识能力。它具有单调、快速、去除冗余和不相关特征、处理噪声等优点,但其对噪声数据敏感,且只适合处理离散特征。
    典型的算法有Focus,LVF等。
      • Wrapper方式
    Wrapper方式依据选择子集最终被用于构造分类模型,把特征选择算法作为学习算法的一个组成部分,直接使用训练结果的准确率作为特征重要性程度的评价标准。该方法在速度上要比Filter方式慢,但它所选的优化特征子集规模相对要小的多,非常有利于关键特征的辨识;同时其准确率比较高,但泛化能力较差,时间复杂度较高。
    目前,关于Wrapper方式的研究也比较多,例如:
    Hsu等人用决策树来进行特征选择,采用遗传算法来寻找使得决策树分类错误率最小的一组特征子集
    Chiang等人将Fisher判别分析与遗传算法结合,用于化工故障过程中辨识关键变量,其效果也不错。
    Guyon等人利用支持向量机的分类性能衡量特征的重要性,最终构造了一个分类性能较高的分类器。
    Krzysztof提出了一种基于相互关系的双重策略的Wrapper特征选择方法FFSR(fast feature subset ranking),以特征子集作为评价单位,以子集收敛能力作为评价标准
    戴平等人提出了一种基于SVM的快速特征选择方法
      • Embedded方式
    针对Filter和Wrapper方式的利弊,提出了Embedded方式的特征选择方法,该方式先用filter方法初步去掉无关或噪声特征,只保留少量特征,减少后续搜索规模,然后再用Wrapper方法进一步优化,选择分类准确率最高的特征子集。例如,Li G-Z等人先使用互信息度量标准和随机重采样技术获取前k个重要特征,再使用SVM构造分类器。

    四.总结

    从图像中提取特征,首先根据具体的问题,判断选取的图像特征,如颜色或纹理。针对不同的特征选择具体的提取方法,如常用的基于颜色特征的颜色直方图或基于纹理的灰度共生矩阵和小波变换等。这是第一步对图像原始特征的提取。由于原始特征可能维数很高,或包含大量的冗余特征和无关特征,会使后续算法的计算复杂度变得很高,所以进一步进行特征提取和特征选择,抽取样本最相关特征,降低数据维数和消除不相关特征和冗余特征。
    统计意义上的特征提取是由获取到的原始特征经过线性或非线性变换得到较少数量且更具有的表达能力的新特征。常用的线性变换有PCA、LDA、MDS,非线性变换有KPCA、流型学习等。有时基本的特征提取方法由于自身的局限性或不能满足在某些具体问题中的要求,就需要对这些方法进行改进。例如,PCA不考虑样本类别,因此得到的低维空间相对判别分类而言不是最优的;在样本类内分布为高斯分布且协方差相同时,LDA可以得到最优线性判别分析转换矩阵,但现实世界中类内分布的复杂度远远超出了高斯分布;MDS方法中目标函数的定义及对该目标函数最小化选择适合的优化方法;KPCA方法中核函数的选择与核函数的参数设定等,都需要根据具体的情况选择与设定;关于流型学习中的各种方法,在样本分布较稀疏时,对近邻样本间距离的度量可能会有较大的偏差。
    特征提取技术很难解释新特征与样本类别之间的相互关系,但在某些领域内对这种相互关系的理解却很重要,所以,在这种情况下,特征选择就更加有效。特征选择是指从原始特征中选择最少的特征,使所选特征与类别之间具有最大相关度,特征与特征之间具有最小相关度。根据评价标准是否依赖于具体的学习算法,特征选择算法分为Filter,Wrapper,Embedded三种方式。Filter方式依据数据内在的结构特征选择最相关的特征,该方式主要是选取对样本距离及相关性的度量准则。直接依赖学习算法准确率的Wrapper方式,主要是对学习算法的选择,通常选择SVM作为评估标准。Embeded方式将特征选择视为学习算法的子系统,该算法计算复杂度介于Wrapper和Filter方式之间,选择的特征比Filter方式更准确,但需要与新设计的算法相结合。
    最后,获取特征子集的选择策略,在高维样本空间对所有候选子集进行评估测试是不实际的。最优特征选择算法-分支界定法不仅对准则判据有要求,且计算量还是很大,所以又提出了基于启发式的次优选择算法,还可以利用一些群智能的随机搜索算法,例如GA、PSO、SAA,可以更好的提高搜索效率。



    展开全文
  • 文本分类 特征选择

    2019-06-04 11:28:20
    特征选择技术比较:PSO,PCA和信息增益 作为与基于PSO的特征选择比较,我们利用PCA和信息增益来减少我们问题的特征空间维度。主成分分析(PCA)[51] 是一种有用的...特征向量对应于包含最重要模式最高特征...
  • 使用DTW测度 ,在标准英文数字语音库上实验表明 ,最有用的语音信息包含在MFCC分量C1到C12 之间 ,最有用的说话人信息包含在MFCC分量C2 到C16之间。MFCC分量C0 和C1包含有负作用说话人信息 ,将其作为特征会引起识别...
  • 最重要的是,在浏览器中使用时,该扩展程序不会尝试破坏我流程。 所呈现的信息需要在几秒钟之内就能被识别和记忆,因此我不会停留在开始页面上。 也是一个很好背景图像,可以激发创造力并带来镇定感觉。 ...
  • 深度学习是当前智能识别、数据挖掘等领域最重要的研究方向,通过组合低层特征,形成更加抽象高层表示属性类别或特征,以发现数据分布式特征表示.数据降维是深度学习过程中最为常见一种过程,通过降维,能够去除数据...
  • 鉴于互联网作为新闻来源的普及性以及互联网上信息的不断增长,自动识别谣言的重要性正变得越来越重要。 开发了一组定性和定量指标,以更好地了解每个搜索查询的特征及其生成的结果数据集。 定量指标表明数据集的...
  • 带有新变形触摸的最小型Android应用程序,可提供全球COVID-19案例的统计信息。 详细的累积和每日图表可用于所有国家,以及一些有用信息,例如重要的链接和注意事项。 这是我使用Flutter for android制作的第一个...
  • 卫星云图轮廓特征最重要的一种视觉特征,本文采用变分方法提取 卫星云图轮廓,系统分析了变分理论两大分支—参数活动轮廓模型和几 何活动轮廓模型特点,提出了两种轮廓提取算法,能够有效实现卫星云图 真实...
  • 然后讨论一些能使远程主机“在不知不觉间”泄露其信息的技术。最后主要是nmap扫描工具的一些实现细节。动机我想谁都已经非常清楚知道远程主机操作系统有多么重要,因此这里只是作一简单叙述。首先最有用的一点在于绝...
  • 但是,我们怀疑,学习ERP的最有用的方法只是在用户遇到它的地方。 仅关注某些地区或时刻(如实施)的一种含义是,分析中忽略了其他级别和时间框架的重要影响。 唯恐我们忘记,ERP通常是一项通用的全球性技术,其...
  • 信息论预编码答案

    2014-10-26 17:16:10
    边缘检测在计算机视觉、图象分析等应用中起着重要的作用,是图象分析与模式识别的重要环节和主要特征提取手段,这是因为图像边缘包含了用于识别的有用信息。经典简单边缘检测方法是对原始图像按像素某邻域...
  • 由于边缘是图象基本的特征, 边缘检测在计算机视觉、图象分析等应用中起着重要的作用,是图象分析与识别的重要环节,这是因为子图象边缘包含了用于识别的有用信息,因此进行边缘检测处理是图像分析和模式识别主要...
  • 但是,这些方法大多数都忽略了用户和项目之间社会上下文信息,这对于预测许多推荐问题中用户偏好非常重要有用。 此外,已经针对用户可以提供明确等级场景提出了大多数现有社交推荐方法。 但是实际上,...
  • 虹膜图像由于其强大而独特文本信息,是生物识别领域最重要、最独特的特征,是人类识别有力工具。 提取这些突出特征是识别虹膜生物特征模式主要进步。 我们在计算机视觉中面临问题可以通过深度学习技术成功...
  • .1 边缘检测技术概况 计算机视觉处理可以看作是为了实现某一任务从包含有大量的不相关的信息中抽出对我们有用信息。...边缘是图像的最基本特征。所谓边缘,是指图像中灰度发生急剧变化的区域,或者...
  • 边缘是图像的最基本特征,它包含了用于识别的有用信息,为人 们描述或识别目标以及解释图像提供了一个重要特征参数。边缘检 测是图像处理、图像分析和计算机视觉领域中最经典的研究内容之一, 是进行模式识别和...
  • 所谓边缘是指其周围像素灰度有阶跃变化或屋顶变化的那些像素的集合,边缘存在于目标、背景和区域之间,所以,它是图像分割所依赖的最重要的依据。由于边缘是位置的标志,对灰度的变化不敏感,,因此,边缘也是图像...
  • 直方图是图像一个重要特征,因为直方图用少量数据表达图像灰度统计特征。 图像灰度直方图性质: 1.灰度直方图只能反映图像灰度分布情况,而不能反映图像像素位置,即丢失了像素·位置信息。 2.一...
  • 最重要的信息,并帮助读者消化最难以理解概念。本书是一本友好而易于使用自学指南,适合用做编 程课程教材,也可供熟悉其他语言开发人员参考,以更深入地理解C++语言基本知识。 本书采用了各种教学技巧...
  • 最重要的信息,并帮助读者消化最难以理解概念。本书是一本友好而易于使用自学指南,适合用做编 程课程教材,也可供熟悉其他语言开发人员参考,以更深入地理解C++语言基本知识。 本书采用了各种教学技巧...
  • 最重要的信息,并帮助读者消化最难以理解概念。本书是一本友好而易于使用自学指南,适合用做编 程课程教材,也可供熟悉其他语言开发人员参考,以更深入地理解C++语言基本知识。 本书采用了各种教学技巧...
  • 最重要的信息,并帮助读者消化最难以理解概念。本书是一本友好而易于使用自学指南,适合用做编 程课程教材,也可供熟悉其他语言开发人员参考,以更深入地理解C++语言基本知识。 本书采用了各种教学技巧...
  • 全球经济结构调整是决定可持续发展未来的主要因素,人类行为、价值观和生活方式需要重大... 旅游统计用于研究旅游活动行为的最稳定特征。 这项研究将允许配置总体前景,这是在制定该领域的预测时做出最佳决策所必需的。
  • 近来,与仅考虑像素的光谱特征的方法相比,利用空间和光谱信息的方法更加充分,鲁棒,有用和准确。 在本文中,通过使用空间像素关联(SPA)处理从高光谱数据中提取区域纹理信息,以进一步提高SVM技术的分类性能。 ...
  • 滤波器可以说是信号处理中最重要的研究对象,滤波器可以将原始信号的有用信息通过各种组合来凸显出来,因此很多时候也将它们称为Neighborhood operators,基本上所有涉及到特征的应用场合都要考虑滤波器,即使是发展...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 147
精华内容 58
关键字:

有用信息的最重要特征