精华内容
下载资源
问答
  • 关于算法的确定性特征
    千次阅读
    2019-07-04 19:55:24

    随机化算法是一种在算法中使用了随机函数,且随机函数的返回值直接或间接的影响了算法的执行流程或执行结果。而确定性算法是与随机化算法相对来说的。

     

    PCA:组成分分析,是常见的降维方法,是确定性算法,第一次运行结果和第n次结果一致,不会受运行次数的影响。

    K-means: 聚类算法,每次运行会随机初始化k个聚类中性点,因此算法结果具有随机性,不是确定性算法;K-means,在初始化聚类中心时,一般是通过随机函数选取随机的K个点作为聚类中心,是随机化算法。

     

    更多相关内容
  • 确定性算法 不确定的问题 (Undecidable Problems) An undecidable problem is a problem for which there is no algorithm that can solve it. Alan Turing proved that the famous halting problem is ...

    非确定性算法

    不确定的问题 (Undecidable Problems)

    An undecidable problem is a problem for which there is no algorithm that can solve it. Alan Turing proved that the famous halting problem is undecidable. The halting problem can be simply stated as follows - Given an input and a Turing machine, there is no algorithm to determine if the machine will eventually halt. There are several problems in mathematics and computer science that are undecidable.

    无法确定的问题是没有算法可以解决的问题。 艾伦·图灵(Alan Turing)证明了著名的停止问题尚不确定。 停止问题可以简单地描述如下-给定输入和Turing机器,没有算法确定机器是否最终停止。 在数学和计算机科学中存在一些无法确定的问题。

    多项式和非多项式时间算法 (Polynomial and Non - polynomial time algorithm)

    If the complexity of an algorithm is expressed as O (p(n)) where p(n) is some polynomial of n, then the algorithm is said to be a polynomial time algorithm. Generally, polynomial time algorithms are tractable. Any algorithm with a time complexity that cannot be bounded by such bound then this is known as non - polynomial algorithms.

    如果一种算法的复杂度被表示为O(P(N))其中p(n)是多项式的一些n个 ,则算法被认为是一个多项式时间算法。 通常,多项式时间算法很容易处理。 具有时间复杂度的任何算法都不能被这种限制所限制,这就是非多项式算法。

    确定性和非确定性算法 (Deterministic and Non - deterministic Algorithms)

    The algorithms in which the result of every algorithm is uniquely defined are known as the deterministic algorithm. In the theoretical framework, we can remove this restriction on the outcome of every operation. We can allow algorithms to contain operations whose outcomes are not uniquely defined but are limited to specified sets of possibilities. The machine executing each operation is allowed to choose any one of these outcomes subjects to a determination condition to be defined later. This leads to the concept of a Non-deterministic algorithm.

    唯一定义每个算法的结果的算法称为确定性算法 。 在理论框架中,我们可以消除对每个操作结果的限制。 我们可以允许算法包含操作,这些操作的结果不是唯一定义的,但仅限于指定的可能性集。 允许执行每个操作的机器选择这些结果对象中的任何一个,以决定条件以便稍后定义。 这导致了非确定性算法的概念。

    There are three new functions which specify such types of algorithms are:

    有三种指定这些算法类型的新功能是:

    1. Choice(S) arbitrarily chooses one of the elements of the set S.

      Choice(S)任意选择集合S的元素之一。

    2. Failure() signals an unsuccessful completion.

      Failure()表示未成功完成。

    3. Success() signals a successful completion.

      Success()表示成功完成。

    The assignments statement x: Choice (1, n) could result in x being assigned any one of the integers in the range [1, n]. There is no rule specifying how this choice is to be made. The Failure() and the Success() signals are used to define a computation of the algorithm. These statements cannot be used to effect a return. Whenever there is a set of the choices that lead to a successful completion, then one such set of the choices is always made and the algorithm terminates successfully. A non - deterministic algorithm terminates unsuccessfully if and only if there exists no set of the choices leading to a success signal. The computing times for the Choices, the Success, and the Failure are taken to be O (1). A machine capable of executing a non - deterministic algorithm in this way is called a non – deterministic machine.

    赋值语句x:Choice(1,n)可能导致x被赋值范围[1,n]中的任何整数。 没有规则指定如何进行此选择。 Failure()Success()信号用于定义算法的计算。 这些语句不能用于产生回报。 只要有一组选择导致成功完成,就总是做出这样一组选择,并且算法成功终止。 当且仅当不存在导致成功信号的选择集时, 非确定性算法才会失败终止。 选择,成功和失败的计算时间取为O(1) 。 能够以这种方式执行非确定性算法的机器称为非确定性机器。

    References:

    参考文献:

    翻译自: https://www.includehelp.com/algorithms/deterministic-and-non-deterministic.aspx

    非确定性算法

    展开全文
  • 确定性算法与非确定性算法

    千次阅读 2021-03-14 16:02:47
    1. 什么是确定性算法 若对于一个算法,给定当前状态和输入,若该算法只有一个动作可供选择,那么该算法是确定选择。 举例:快速排序算法; 2. 什么是非确定算法 若对于一个算法,给定当前状态和输入,若该算法

    非确定性和非确定是指在理论计算机科学中,针对各种计算机器模型(自动机),在每一时刻,根据当时的状态和输入,是否能够给出确定性动作的分类。
    若机器有多个动作可供选择时,则称机器为非确定性的;相反,若机器的动作可唯一确定时。且非确定性是相对于确定性来说,对于非确定性的机器,在性能各方面要高于确定性机器。

    1. 什么是确定性算法

    • 若对于一个算法,给定当前状态和输入,若该算法只有一个动作可供选择,那么该算法是确定选择。
    • 举例:快速排序算法;

    2. 什么是非确定算法

    • 若对于一个算法,给定当前状态和输入,若该算法只有一个动作可供选择,那么该算法是确定选择。
    • 举例:随机算法。

    4. 其他解释

    • 唯一定义每个算法的结果的算法称为确定性算法 。 在理论框架中,我们可以消除对每个操作结果的限制。 我们可以允许算法包含操作,这些操作的结果不是唯一定义的,但仅限于指定的可能性集。 允许执行每个操作的机器选择这些结果对象中的任何一个,以决定条件以便稍后定义。 这导致了非确定性算法的概念。
    展开全文
  • 遗传算法是一种基于自然选择的优化问题的技术。 在这篇文章中,我将展示如何使用遗传算法进行特征选择。 虽然 scikit-learn 中有许多...我们面临的问题是确定哪些特征与问题相关。 我们找寻目标是具有高质量的特征

    遗传算法是一种基于自然选择的优化问题的技术。 在这篇文章中,我将展示如何使用遗传算法进行特征选择。

    虽然 scikit-learn 中有许多众所周知的特征选择方法,但特征选择方法还有很多,并且远远超出了scikit-learn 提供的方法。特征选择是机器学习的关键方面之一。 但是因为技术的快速发展,现在是信息大爆炸的时代,有多余的可用数据,因此通常会出现多余的特征。许多特征都是多余的。 它们会为模型增加噪音,并使模型解释出现问题。

    我们面临的问题是确定哪些特征与问题相关。 我们找寻目标是具有高质量的特征。

    遗传算法

    本篇文章使用了“sklearn-genetic”包:

    该软件包与现有的sklearn模型兼容,并为遗传算法的特征选择提供了大量的功能。

    在这篇文章中,我使用遗传算法进行特征选择。但是,遗传算法也可以用于超参数优化。因为这些步骤非常简单和一般化,所以可以适用于许多不同的领域。

    特征选择

    选择特性是一个NP-Hard问题(所有NP问题都能在多项式时间复杂度内归遇到的问题)。给定一组特征,最优配置是这些特征的集合或子集。这种方法是离散选择。在可能性排列的情况下,确定最优特征集的成本是非常高的。

    遗传算法使用一种基于进化的方法来确定最优集。对于特征选择,第一步是基于可能特征的子集生成一个总体(种群)。

    从这个种群中,使用目标任务的预测模型对子集进行评估。一旦确定了种群的每个成员,就会进行竞赛以确定哪些子集将延续到下一代。下一代由竞赛获胜者组成并进行交叉(用其他获胜者的特征更新获胜特征集)和变异(随机引入或删除一些特征)。

    大致的步骤如下:

    1. 产生初始种群
    2. 对种群中的每个成员进行评分
    3. 通过竞赛选择子集进行繁殖
    4. 选择要传递的遗传物质(特征)
    5. 应用突变
    6. 以上步骤重复多次,每一次成为一代(generation)

    该算法运行一定数量的代之后,群体的最优成员就是选定的特征。

    实际操作

    实验基于 UCI 乳腺癌数据集,其中包含 569 个实例和 30 个特征。 使用这个数据集,我测试了几个分类器的所有特征、遗传算法的特征子集以及使用卡方检验的五个特征进行比较。

    下面是用于使用遗传算法选择最多五个特征的代码。

    from sklearn.datasets import load_breast_cancer
    from genetic_selection import GeneticSelectionCV
    from sklearn.tree import DecisionTreeClassifier
    import pandas as pd
    import numpy as npdata = load_breast_cancer()
    df = pd.DataFrame(data.data, columns=data.feature_names)
    df['target'] = data.target
    X = df.drop(['target'], axis=1)
    y = df['target'].astype(float)estimator = DecisionTreeClassifier()
    model = GeneticSelectionCV(
        estimator, cv=5, verbose=0,
        scoring="accuracy", max_features=5,
        n_population=100, crossover_proba=0.5,
        mutation_proba=0.2, n_generations=50,
        crossover_independent_proba=0.5,
        mutation_independent_proba=0.04,
        tournament_size=3, n_gen_no_change=10,
        caching=True, n_jobs=-1)
    model = model.fit(X, y)
    print('Features:', X.columns[model.support_])
    

    GeneticSelectionCV

    初始种群(大小为“n_population”)是从特征集的样本空间中随机生成的。 这些集合的范围受参数“max_features”的限制,该参数设置每个特征子集的最大大小。

    对于初始种群的每个成员,使用目标度量来衡量一个分数。 此度量是指定的估算器的性能。

    进行竞赛选择以确定哪些成员将继续到下一代。 竞赛中的成员数量由“tournament_size”设置。 竞赛规模是根据评分指标从总体中选出的几个成员相互竞争。获胜者被选为下一代的父母。

    参加竞赛的成员人数应该很少。 当值比较大时,通常选择当前最好的成员。 此行为不会导致选择任何较弱的成员。 对于较弱的成员,虽然提供了暂时的性能提升,但最终这会导致整体性能的降低,因为较弱的选项没有得到改进的机会。

    自然选择

    在自然选择中,遗传信息存储在染色体中。在繁殖过程中一些遗传物质从父母传给孩子。然后孩子包含来自父母双方的遗传物质。此属性用参数“crossover_proba”表示。指定的概率表示从一个生成交叉到下一个生成的机会。还有一个参数“crossover_independent_proba”,它是一个特征将交叉到子节点的概率。

    进化的一个关键方面是突变。变异降低了搜索陷入局部最优被卡住的风险。在每一代中除了交叉之外,还添加了一个随机突变。突变发生的概率由参数“mutation_prob”设置。此参数与“mutation_independent_proba”结合,这是向特征集添加特征的机会。

    值得注意的是,将此概率设置得太高会将算法转换为随机选择过程。因此将此值设置在相对较低的水平。在每一代中随机引入特征可以有效地作为遗传过程的正则化。

    此处使用的遗传搜索算法还有一个“n_gen_no_change”参数,用于监控种群中最好的成员是否在几代中没有发生变化。在这种情况下,搜索是否找到了一个最佳选择。是否考虑增加突变或交叉概率以进一步改变选择。

    结果

    遗传与卡方特征选择的结果如下所示。还列出了使用所有特性的基准性能。结果来自交叉验证,使用准确性作为度量标准,使用的特征数量在括号中显示。

    虽然这些结果不是决定性的,但它们显示了遗传算法的好处。 模型性能基于遗传算法的特征子集,该子集始终优于基线模型和卡方特征子集。 逻辑回归模型是一个例外,其结果仍然具有可比性。

    此外,产生的最佳特征子集小于五个特征的最大值。 具有较少特征的模型最终比较大的模型更受青睐,因为它们更简单且更易于解释。

    总结

    遗传算法非常通用,适用于广泛的场景。

    这篇文章探讨了如何使用 sklearn-genetic 包将遗传算法用于特征选择。 这些算法也已被证明在超参数搜索和生成式设计中是有效的。

    虽然不像 sklearn 中现成的方法那么传统,但遗传算法提供了一种独特而实用的特征选择方法。 这些算法优化的方式与大多数其他特征选择方法有很大不同。 该过程基于纯自然选择方法。

    我鼓励数据科学家花时间在他们的工作中理解和实施遗传算法。

    作者:Zachary Warnes

    展开全文
  • 算法(algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。此外,一个算法还具有下列5个重要特性: ...2) 确定性 算法中每一条指令必须有确切的含义,读者...
  • 什么是算法算法有哪些特征

    万次阅读 2019-11-11 07:44:45
    什么是算法算法有哪些特征算法定义:为解决一个问题而采取的方法和步骤,称为“算法”。 算法五大特征: ①有穷性 ②确定性 ③有零个或多个输入 ④有一个或多个输出 ⑤有效性 ...
  • 1.决策树使用基尼系数(GI)和信息增益(IG)为决策树计算特征重要。(1)信息增益(information gain)假定当前样本集合D中第k类样本所占我的比例为,则D的信息熵为 (1)的值越小,则D的纯度越高。假定离散属性a...
  • 专家将这些算法分为两种核心方法:几何方法侧重于区分特征,光度统计方法用于从图像中提取值。 然后将这些值与模板进行比较以消除差异。 这些算法还可以分为两个更一般的类别——基于特征的模型和整体模型。前者侧重...
  • 特征匹配算法

    千次阅读 2020-06-03 16:51:21
    看论文《特征匹配算法研究及其在目标跟踪上的应用》,感谢! 特征匹配算法 目前 SIFT 算法和 ORB 算法获得了研究者的青睐,但是因为 SIFT 算法是对图像进行全局的特征点检测耗时较长,造成算法的运行速度慢,达不到...
  • 数据结构与算法的关系:紧密相连,缺一不可。 算法的定义:        解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条...算法具有5个基本特征:输入、输出...
  • 特征选择算法综述

    千次阅读 2017-09-01 15:23:08
    特征选择(feature selection)作为一种常见的降维方法是模式识别的研究热点之一。 它是指从原始特征集中选择使某种评估标准最优的特征...在机器学习领域中,特征选择被认为是跟学习算法紧密联系的一个问题,可表述为:
  • 本文针对图像特征匹配算法—SIFT算法介绍了其算法原理,并贴出了代码。
  • 遗传算法特征选择的python实现

    千次阅读 热门讨论 2019-07-02 16:43:39
    遗传算法特征选择的基本原理是用遗传算法寻找一个最优的二进制编码, 码中的每一位对应一个特征, 若第i位为“1”, 则表明对应特征被选取, 该特征将出现在估计器中, 为“0”, 则表明对应特征未被选取,该特征将不出现在...
  • 算法的基本特征

    万次阅读 2017-09-27 09:37:34
    确定性:一个算法的每个步骤都必须精确地定义,可以严格地、无歧义地执行。 输入:一个算法在运行之前赋给它的量,或在运行过程中动态地赋给它的量。 输出:一个算法运行结束时的结果。 有效性:一个算法在运行...
  • 特征选择之遗传算法

    万次阅读 热门讨论 2018-07-31 22:11:08
    遗传算法的优点: ...5. 具有可扩展,容易与其他算法结合。 6. 遗传算法具有良好的全局搜索能力,可以快速地将解空间中的全体解搜索出,而不会陷入局部最优解的快速下降陷阱;是全局优化算法,一般...
  • 基于信息论的特征选择算法综述

    千次阅读 2019-09-03 17:31:45
    定义信息度量函数J(f),其目的是在原始特征集F内选择子集S,保证其与类别C之间相关性程度最大,同时又保证子集S内部的冗余最小。 为了方便起见,下面先对几个常用的符号做一简单约定:符号F和S分别表示未选的和已...
  • 我叫《数据结构与算法》,是计算机世界的四大基石之一。 想来我应该是惹人怜爱的吧(认真脸),因为我仿佛听到了无数个初入计算机世界的同学的呐喊声(????)。 我作为一门简单学科,看到有很多的在半途弃我而去,我...
  • 一致哈希算法原理详解

    万次阅读 多人点赞 2021-10-17 18:31:32
    (1)一致哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为 Hash 环; (2)接着将各个服务器使用 Hash 函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在...
  • 确定和非确定性算法

    千次阅读 2016-11-27 17:05:28
    本文摘自http://wenda.so.com/q/1465703473723556?src=140所谓非确定性是指在理论计算机...且非确定性是相对于确定性来说,对于非确定性的机器,在性能各方面要高于确定性机器。任意一种自动机,按其动作的确定程度,大
  • 用遗传算法进行特征选择

    万次阅读 多人点赞 2019-01-20 21:57:27
    文章目录一、问题举例二、算法描述1、基于类内类间距离的可分判据2、遗传算法(Genetic Algorithm)1) 初始化种群2)计算当前种群 M(t)中每条染色体的适应度值 f(m)3)基于适应度值的选择4)交叉5)变异6)...
  • 特征选择 ReliefF算法

    万次阅读 多人点赞 2018-05-18 21:43:12
    一、算法 Relief算法最早由Kira提出.基本内容:从训练集D中随机选择一个样本R,然后从和R同类的样本中寻找k最近邻样本H,从和R不同类的样本中寻找k最近邻样本M,最后按照公式更新特征权重. 算法: 1.置0所有特征...
  • 上一篇:图像特征算法(一)——SURF算法简述及Python标记SURF特征检测实践 下一篇:持续创作中… 目录计算机视觉专栏传送一、ORB算法1.算法简介2.FAST寻找特征点3.BRIEF 算法生成图像特征描述符4.满足缩放旋转不变...
  • 确定性加密方案 和 概率性加密方案

    千次阅读 2018-07-07 15:38:45
    确定性加密方案 加密方案是确定的,每一个明文对应一个密文。敌手在进行不可区分性攻击时,只需重新加密消息后与目标密文进行比对即可。如RSA加密。概率性加密方案 每次加密时首先选择一个随机数,再生成密文。...
  • 提出并讨论了几种比较标准,以突出每种算法的优缺点,包括速度、复杂、正确和精度。使用标准统计方法将算法的结果与基本事实进行比较。进行了扩展的案例研究,以进一步评估 SLAM 应用程序中的算法 1 介绍   ...
  • 本篇介绍确定性策略梯度算法,该算法主要用于off-policy(on-policy也能用)。在DQN等值函数估计算法中,最终策略的形式是需要对动作状态值函数取极大a=argmaxa′Q(s,a′)a={\rm argmax}_{a&#...
  • 特征选择-mRMR算法

    千次阅读 2019-10-21 13:29:08
    mRMR算法主要是为了解决通过最大化特征与目标变量的相关关系度量得到的最好的m个特征,并不一定会得到最好的预测精度的问题,因为这m个特征存在冗余特征的情况(是指该特征所包含的信息能从其他特征推演出来,如对于...
  • SIFT算法确定特征点方向

    千次阅读 2013-09-04 22:06:32
    SIFT算法确定特征点方向  SIFT算法特征描述子 【注】未经允许,本博客所有文章不得用于任何商业用途。转载请注明出处http://www.cnblogs.com/JiePro/ 目录: 1、计算邻域梯度方向和...
  • 常见的几种图像特征提取算法

    万次阅读 2019-07-01 09:08:00
    常见的几种特征提取算法1. LBP算法(Local Binary Patterns,局部二值模式)2.HOG特征提取算法(Histogram of Oriented Gradient)3.SIFT算子(Scale-invariant feature transform,尺度不变特征变换) 1. LBP算法...
  • 特征点检测FAST算法

    千次阅读 2018-03-22 23:45:13
    1.FAST基本算法 用一句话来讲FASTN算法的原理就是:若一个像素周围有一定数量的像素与该点像素值不同,则认为其为角点。步骤如下: 1)在图像中任选一点p, 假定其像素(亮度)值为 Ip 2)以r为半径画圆,覆盖p...
  • 什么是一致Hash算法

    万次阅读 多人点赞 2018-03-13 21:15:32
    最近有小伙伴跑过来问什么是Hash一致性算法,说面试的时候被问到了,因为不了解,所以就没有回答上,问我有没有相应的学习资料推荐,当时上班,没时间回复,晚上回去了就忘了这件事,今天突然看到这个,加班为大家...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 660,931
精华内容 264,372
热门标签
关键字:

关于算法的确定性特征