精华内容
下载资源
问答
  • 学习Raft算法的笔记

    2018-11-14 07:00:00
    Raft是一种为了管理日志复制的一致性算法。它提供了和Paxos算法相同的功能和性能,但是它的算法结构和Paxos不同,使得Raft算法更加容易理解并且更容易构建实际的系...
        

    Raft是一种为了管理日志复制的一致性算法。它提供了和Paxos算法相同的功能和性能,但是它的算法结构和Paxos不同,使得Raft算法更加容易理解并且更容易构建实际的系统。为了提升可理解性,Raft将一致性算法分解成几个关键的模块,例如领导选举,日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态和数量。从一个用户研究的结果可以证明,对于学生而言,Raft算法比Paxos算法更容易学。Raft算法还包括了新的机制来允许集群成员的动态改变,让利用重叠的大多数来保证安全性。

    0|1Raft算法概述



    Raft算法是从多副本状态机的角度提出,用于管理多副本状态机的日志复制,它一致性分解为多个子问题:领导选举(Leader election),日志复制(Log replication),安全性(Safety),日志压缩(Log compaction),成员变更(Menbership change)等。同时,Raft算法使用了更强的假设来减少需要考虑的状态,使之变得更加容易理解。
    Raft讲系统中的角色分为领导者(Leader),跟从者(Follower)和候选人(Candidate):
    Leader: 接收客户端请求,并向Follower同步请求日志。当日志同步到大都数节点上后告告诉Follower提交日志。
    Follower:接收并持久化Leader同步的日志,在Leader告诉它的日志提交之后,提交日志。
    Candidate:Leader选举过程中的临时角色。
    640?wx_fmt=png
    Raft要求系统在任意时刻最多只有一个Leader,正常工作期间Leader和Followers。
    Raft算法角色状态转换如下:
    640?wx_fmt=png

    跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息,那么它就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导者。在一个任期内,领导人直到自己宕机了。

    640?wx_fmt=jpeg

    Raft算法时间被划分成为一个个的任期(Term),每个任期(Term)开始都是一次Leader选举。选举成功后,领导人会管理整个集群直到任期(Term)结束。有时候会选举失败,那么任期(Term)就会没有领导者,而结束。任期(Term)之间的切换可以在不同的时间不同的服务器上观察到。

    Raft算法中服务器之间节点通信使用远程调用(RPCs).而在etcd的实现当中v2版本用的http,而v3版本采用的是grpc(本身是跨平台)。并且基本的一致性算法只是用了两种类型的Rpcs。请求投票(RequestVote)RPCs由候选人发起。然后附加条目数(AppendEntries)由Leader发起。用来复制日志和提供一种心跳机制。为了服务器之间传输快照增加了第三种RPCs。当服务器没有及时收到RPC的响应时,会进行重试,并且它们能够并行发起RPCs来获取最佳性能。

    0|1复制状态机



    一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如,大规模的系统中通常都有一个集群领导者,像 GFS、HDFS 和 RAMCloud,典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。
    640?wx_fmt=png

    复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。

    复制状态机通常都是基于复制日志实现的,如图 1。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。

    保证复制日志相同就是一致性算法的工作了。在一台服务器上,一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,尽管有些服务器会宕机。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成一个高可靠的状态机。

    实际系统中使用的一致性算法通常含有以下特性:

    安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
    可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
    不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟在可能只有在最坏情况下才会导致可用性问题。
    通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

    0|1Leader选举



    Raft使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化Follower。Leader向所有的Followers周期性的发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat,就会等待一段随机时间(150ms-300ms)发起一次选举。

    Follower先要增加自己的当前任期号,也就把当前的任期号加一并且转换到候选人状态。然后它们会并行的向集群中的其他服务器节点发起请求投票的RPCs来给自己投票。结果会有以下三种情况:

    1. 它自己赢得了这次选举

    2. 其他的服务器成为了领导者

    3. 一段世家之后没有人获取胜利的人。

    0|1日志复制

    Leader被选举出来后.它就开始为客户端提供服务,客户端每个请求都包含一条被复制状态机执行的命令。领导人将这条指令作为新的日志条目附加到日志中去。然后并行的发起附加条目RPCs给其他的服务器,让它们复制这个日志条目,当这条日志条目被安全的复制。领导人会应用这条日志条目到它的状态中然后把执行的结果返回客户端。如果Follower崩溃或者运行缓慢,再或者网络丢包,领导人会不断的尝试附加日志条目RPCs(尽管已经回复了客户端)直到所有Follower都最终存储了所有条目数。
    640?wx_fmt=png

    日志由有序编号(log index)的日志组成条目。每个日志条目包含它被创建的任期号(term),和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上,就被认为可以提交了(commit)了。

    640?wx_fmt=png

    Raft维护着一下特征:
    1.如果在不同的日志中的两个条目拥有相同的索引和任期号,那么它们存储了相同的指令。
    2.如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们的之前的所有日志条目也全部相同。

    第一个特新来这样的一个事实,领导人最多在一个任期里在指定的日志索引位置创建一条日志条目,同时日志条目在日志中的位置也从来不会改变。第二个特性由附加日志RPC的一个简单一致性检查保证。在发送附加日志RPC的时候,领导人会把新的日志条目紧接着之前的条目索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同的日志索引位置和任期号的条目,那么他就会拒绝接收新的条目日志。一致性检查就像一个归纳步骤:一开始空日志状态肯定是满足日志匹配特性的,然后一致性检查保护了日志匹配特性当日志扩展的时候。因此,每当附加日志RPC返回成功时,领导人就知道跟随着的日志时一样的了。
    640?wx_fmt=png

    当一个领导人成功当选时,跟随者可能是任何情况(a-f)。每一个盒子表示是一个日志条目,里面的数字表示任期号。跟随者可能缺少一些体制条目(a-b),可能会有一些未被提交的日志条目(c-d),或者两种情况都存在的(e-f)。例如,场景f可能会发生,某些服务器在任期号2的时候是领导人,已附加了一些日志条目到自己的日志中,但在提交之前就就崩溃了,很快这个机器就被重启了,在任期3重新被选为领导人,并且又增加了一些日志条目到自己的日志中,并且又增加了一些日志条目到自己的日志中,在任期2和任期3的日志被提交之前,这个服务器又宕机了,并且在接下来的几个任期里一直处于宕机状态。

    要使得跟随着的日志进入和自己一致的状态,领导人必须找到最后两者达成一致的地方,然后删除那个点之后的所有日志条目,发送自己的日志给跟随者。所有的这些日志操作都在进行附加日志RPCs的一致性检查时完成。领导人针对没一个维护者维护了一个nextIndex,这表示下一个发送给追随者的日志条目的索引地址。当一个领导人刚获得领导者的权利的时候,他初始化所有的nextIndex值作为自己的最后一条日志的index加1。如果一个跟随者的日志和领导人不一致,那么下一次日志附RPC时的一致性检查就会失败。在被跟随者拒绝之后,领导人就会减少nextIndex值并进行重试。最终nextIndex会在某个位置使得领导人和跟随者的日志达成一致。当这种情况发生,附加日志RPC就会成功,这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志RPC成功,那么跟随者的日志就会和领导人保持一直,并且在接下来的任期里一直继续保持。

    0|1安全性



    Raft增加了如下两条限制以保证安全性:
    1>拥有最新的已提交的log entry的Follower才有资格成为Leader。
    这个保证是在RequestVote RPC中做的,Candidate在发送RequestVote RPC时。要带上自己的最后一条日志的term和log Index。其他节点收到消息时,如果发现自己的日志请求中携带的更新,则拒绝投票。日志比较的原则是:如果本地的最后一条log entry的term更大,则term大更新,如果term一样大,则log Index更大的更新。

    2.Leader只能推进commit Index来提交当前term已经复制最到最大服务器上的日志,旧term日志的日志要等到提交当前的term的日志来间接提交(log Index 小于commit Index的日志被间接提交)
    之所以要这样,是因为可能会出现已提交的日志被覆盖的情况:
    640?wx_fmt=png

    如图的时间序列展示了领导人无法决定对老任期号的日志条目进行提交。在(a)中,S1是Leader,部分的是复制了索引的位置2的条目数目。(b)是时期,S1崩溃了,然后S5在任期3里通过S3,S4和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引2处。然后到(c),S5崩溃了,S1重新启动,选举成功,开始日志复制。在这个时候,来自任期2的那条日志已经被复制到了集群的大多数机器上,但是还没有被提交,如果S1在(d)时期中又崩溃了。S5可以重新被选举成功(通过来自S2,S3,S4的选票),然后覆盖了他门在索引2处的日志。反之,如果在崩溃之前,S1把自己主导的任期里产生的日志日条目复制到了大多数机器上,就如(e)中那样。那么在后面任期里面这些新的日志条目会被提交(因为S5就不可能选举成功)。这牙膏在同一时刻就同时保证了,之前的所有老的日志条目就会被提交。

    时间和可用性

    Raft的要求之一就是安全性不能依赖时间:整个系统不能因为某些事件运行的比预期快一点或者慢一点产生了错误的结果。但是,可用性(系统可以及时的响应客户端)不可避免的要依赖时间。例如,如果消息交换比服务器故障间隔时间长,候选人没有足够长的时间来赢得选举,没有一个稳定的领导人,Raft将无法工作。
    领导人选举时Raft中对时间要求最为关键的方面。Raft可以选举并维持一个稳定的领导人,只需要满足下面的时间要求:

    广播时间(broadcastTime) << 选举时间(election Timeout) << 平均故障时间(MTBF)

    在这个不等式中,广播时间指的时从一个服务器并行的发送RPCs给集群中的其他服务器并接收平均时间,选举超时时间(150ms-300ms)选举超时时间限制,然后平均故障时间就是对于一台服务器而言,两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级,这样领导人才能发送稳定的心跳消息来阻止跟随者开始进入选举状态,通过随机化选举超时时间的方法,整个不等式也使得选票瓜分的情况变成不肯能。选举选举超时时间要比平局故障时间间隔小上几个数量级,这样系统才能稳定的运行。当领导人崩溃后,整个系统会大约相当于超时时的时间里不可用。我们希望这种情况在系统中国运行很少出现。

    广播时间和平均故障间隔时间是由系统决定的,但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去,所以广播时间大约是 0.5 毫秒到 20 毫秒,取决于存储的技术。因此,选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长,很容易满足时间的需求。

    0|1成员变更



    成员变更是在集群运行过程中副本发生变化,如增加/减少副本数,节点替换等。
    成员变更也是一个分布式一致性的问题,既所有服务器对成员新成员达成一致。但是成员变更又有其特殊性,因为成员变更的一致性达成的过程中,参与投票的过程会发生变化。

    如果将成员变更当成一般的一致性问题,直接向Leader发送成员变更请求,Leader复制成员变更日志,达成多数之后提交,各个服务器提交成员变更日志后从日志成员(Cold)切换到最新成员配置(Cnew的时刻不同.

    成员变更不能影响服务的可用性,但是成员变更过程的某一时刻,可能出现Cold和Cnew中同时存在两个不相交的多数派,进而可能选出两个Leader,形成不同的决议,破坏安全性。
    640?wx_fmt=png
    由于成员变更的这一特殊性,成员变更不能当成一般的一致性问题去解决。

    为了解决这一问题.Raft提出了两段的成员变更方法。集群先成旧成员配置Cold切换到一个过度的配置,称为共同一致(joint consensus),共同一致时旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew,一旦共同一致Cold U Cnew被提交,系统在切换到新成员配置Cnew。
    640?wx_fmt=png

    一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的条目,实线表示最后被提交的日志条目。领导人首先创建了C-old
    ,new的配置条目在自己的日志中,并提交到C-old,new中(C-old的大多数和c-new的大多数)。然后他创建C-new条目并且提交到C-new的大多数。这样就不存在C-new和C-old同时做出决定的时间点。

    在关于重新配置还有三个问题需要提出,第一个问题是,新的服务器额能初始化没有存储任何的日志条目。当这些服务器以这种状态加入到集群中,那么它们需要一段时间来更新追赶。这时还不能提交新的日志条目。为了避免这种可用性的间隔时间Raft在配置更新的时候用了一种额外的阶段,在这种阶段,新的服务器以没有投票权的身份加入集群中来(领导人复制日志给它们。但是不考虑它们是大多数)。一旦新的服务器追赶上了集群中的集群,重新配置可以向上面描述一样处理。

    第二个问题,集群的领导人可能不是新配置的一员。在这种情况下,领导人就会在提交了C-new日志后退位(回到追随者状态)。这意味着有这样一段时间,领导人管理着集群,但是不包括他自己,他复制日志但是不把他自己算作大多数之一。当C-new被提交时,会发生领导人过度。因为这时时最新的配置可以独立工作时间点(将总是能够在C-new配置下选出新的Leader)。再此之前,可能只从C-old中选出领导人。

    第三个问题是:移除不再C-new中的服务器可能会扰乱集群。这些服务器将不会再接收心跳。当选举超时时,它们就会进行新的选举过程。它们会发送拥有新的任期号的请求投票RPCs,这样会导致当前的领导人退回成跟随者状态。新的领导人最终被选出来,但是被移除的服务器将会再次超时,然后这种过程再次重复,导致整体可用性大幅度下降。

    为了避免这个问题,当服务器确认当前领导人存在时,服务器会忽略投票RPCs。特别的,当服务器再当前最小选举超时时间内收到一个请求投票的RPC。他不会更新当前的任期号和投票号。这不会影响正常的选举,每个服务器在开始一次选举之前,至少等待一个最小选举超时时间。然后这有利于避免被移除的服务器的扰乱。如果领导人能够发送心跳给集群,那么他就不会更大的任期号废黜。

    0|1日志压缩



    在实际系统中,不能让日志无限增长,否则系统重启时需要花很长的时间回放,从而影响可用性。Raft采用对整个系统进行snapshot来解决,snapshot之前的日志都可以抛弃。
    每个副本独立的对自己系统状态进行snapshot,并且只能对已经提交的日志进行snapshot。
    Snapshot中包含以下内容:
    1>日志元数据:最后提交的log entry的log index和term。这两个值在snapshot之后的第一条log entry的AppendEntriesRPC的完整性检查的时候会被用上。
    2> 系统当前状态。

    当Leader要发给某个日志落后太多的Follower的log entry被丢弃,Leader会将snapshot发给Follower。或者新加入一台机器时,也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。

    640?wx_fmt=png

    一个服务器用新的快照替换了从1到5的条目数,快照存储了当前的状态。快照中包含了最后的索引位置和任期号

    做snapshot不要做的太频繁,否则消耗磁盘带宽,也不要做的太平凡,否则一点节点重启要回放大量日志,影响可用性。推荐当日组织达到某个固定的大小做一次snapshot。

    做一次snapshot可能耗时过长,会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常的日志同步过程。

    一个关于 Raft 一致性算法的浓缩总结(不包括成员变换和日志压缩)。

    640?wx_fmt=png

    参考:
    http://thesecretlivesofdata.com/raft/(Raft动画)
    https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md(Raft论文翻译)

    原文地址: https://www.cnblogs.com/WithLin/p/9947631.html


    .NET社区新闻,深度好文,欢迎访问公众号文章汇总 http://www.csharpkit.com

    640?wx_fmt=jpeg

    展开全文
  • 而排序算法也是各有千秋,每个都有自身优点和局限性。虽然这些算法平常根本就不用自己去编写,但作为一个有追求程序员,还是要了解它们从不同角度解决排序问题思想。 学习算法是枯燥,那怎么高效理解它...

    排序是一个经典的问题,它以一定的顺序对一个数组或列表中的元素进行重新排序。而排序算法也是各有千秋,每个都有自身的优点和局限性。虽然这些算法平常根本就不用自己去编写,但作为一个有追求的程序员,还是要了解它们从不同角度解决排序问题的思想。

    学习算法是枯燥的,那怎么高效的理解它的原理呢?显然,如果以动图的方式,生动形象的把算法排序的过程展示出来,非常有助于学习。visualgo.net 就是一个可视化算法的网站,第一次访问的时候,真的是眼前一亮。本文就对常用的排序进行下总结。

    1. 冒泡排序

    冒泡排序的基本思想就是:把小的元素往前调或者把大的元素往后调。假设数组有 N 个元素,冒泡排序过程如下:

    1. 从当前元素起,向后依次比较每一对相邻元素(a,b)
    2. 如果 a>b 则交换这两个数
    3. 重复步骤1和2,直到比较最后一对元素(第 N-2 和 N-1 元素)
    4. 此时最大的元素已位于数组最后的位置,然后将 N 减 1,并重复步骤1,直到 N=1

    冒泡排序

    冒泡排序的核心代码:

    public static void bubbleSort(int[] a, int n) {
      // 排序趟数,最后一个元素不用比较所以是 (n-1) 趟
      for (int i = 0; i < n - 1; i++) {
        // 每趟比较的次数,第 i 趟比较 (n-1-i) 次
        for (int j = 0; j < n - 1 - i; j++) {
          // 比较相邻元素,若逆序则交换
          if (a[j] > a[j+1]) {
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
          }
        }
      }
    }

    难点在于边界的确定,算法分析:

    • 平均时间复杂度是 O(n^2),最佳情况是 O(n),最差情况是 O(n^2)
    • 空间复杂度 O(1)
    • 稳定的排序算法(相等元素的前后顺序排序后不变)

    2. 选择排序

    选择排序的基本思想就是:每次从未排序的列表中找到最小(大)的元素,放到已排序序列的末尾,直到所有元素排序完毕。假设数组有 N 个元素且 L=0,选择排序过程如下:

    1. 从 [L...N-1] 范围中找到最小元素的下标 X
    2. 交换第 X 与第 L 位置的元素值
    3. L 加 1,重复以上步骤,直到 L=N-2

    选择排序

    选择排序的核心代码:

    public static void selectionSort(int[] a, int n) {
      // 排序趟数,最后一个元素是最大的不用比较所以是 (n-1) 趟
      for (int i = 0; i < n-1; i++) {
        int minIndex = i; // 无序列表中最小元素的下标
        for (int j = i+1; j < n; j++) {
          // 在无序列表中查找最小元素的小标并记录
          if (a[j] < a[minIndex]) {
            minIndex = j;
          }
        }// 将最小元素交换到本次循环的前端
        int tmp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = tmp;
      }
    }

    算法分析:

    • 平均时间复杂度是 O(n^2),最佳和最差情况也是一样
    • 空间复杂度 O(1)
    • 不稳定的排序算法(相等元素的前后顺序排序后可能改变)

    3. 插入排序

    插入排序的基本思想是:每次将待插入的元素,按照大小插入到前面已排序序列的适当位置上。插入排序过程如下:

    1. 从第一个元素开始,该元素可认为已排序
    2. 取出下一个元素,在已排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于待插入元素 ,把它移到下一个位置
    4. 重复步骤 3,直到找到一个小于或等于待插入元素的位置,将待插入元素插入到下一个位置
    5. 重复步骤 2~5,直到取完数组元素

    插入排序

    插入排序的核心代码:

    public static void insertionSort(int[] a, int n) {
      // a[0] 看做已排序
      for (int i = 1; i < n; i++) {
        int x = a[i]; // 待插入元素
        int j=i-1; // 插入的位置
        while (j >= 0 && a[j] > x) {
          a[j+1] = a[j]; // 为待插入元素腾地
          j--;
        }
        a[j+1] = x; // 插入到下一个位置 j+1
      }
    }

    算法分析:

    • 平均时间复杂度是 O(n^2),最佳情况是 O(n),最差情况是 O(n^2)
    • 空间复杂度 O(1)
    • 稳定的排序算法

    4. 希尔排序

    希尔排序也称为增量递减排序,是对直接插入算法的改进,基于以下两点性质:

    • 插入排序在对几乎已排好序的数据操作时,效率高,可以达到线性排序的效率
    • 但插入排序一般来说是低效的,因为插入排序每次只能移动一位数据

    希尔排序的改进是,使用一个增量将数组切分不同的分组,然后在组内进行插入排序,递减增量,直到增量为 1,好处就是数据能跨多个元素移动,一次比较就可能消除多个元素的交换。基本过程如下:

    1. 选取一个递增序列,一般使用x/2或者x/3+1
    2. 使用序列中最大的增量,对数组分组,在组内插入排序,递减增量,直到为 1

    希尔排序动图

    核心代码:

    public static void shellSort(int[] a, int n) {
      // 计算递增序列,3x+1 :  1, 4, 13, 40, 121, 364, 1093, ... 
      int h = 1;
      while (h < n/3) h = 3*h + 1; 
      while (h >= 1) {// 直到间隔为 1
        // 按间隔 h 切分数组
        for (int i = h; i < n; i++) {
          // 对 a[i], a[i-h], a[i-2*h], a[i-3*h]...使用插入排序
          int x = a[i]; // 待插入元素
          int j=i;
          while (j >=h && x < a[j-h]) {
            a[j] = a[j-h];// 为待插入元素腾地
            j -= h;
          }
          a[j] = x; // 插入 x
        }
        // 递减增量
        h /= 3;
      }
    }

    希尔排序数组拆分插入图解,上面的动图可以辅助理解,与下图数据不一致:

    希尔排序图解

    算法分析:

    • 时间复杂度与选择的增量序列有关,可能的值时 O(n^2) > O(n^1.5) > O(nlg2n)
    • 空间复杂度 O(1)
    • 不稳定的排序算法

    5. 归并排序(递归&非递归)

    归并排序是分而治之的排序算法,基本思想是:将待排序序列拆分多个子序列,先使每个子序列有序,再使子序列间有序,最终得到完整的有序序列。归并排序本质就是不断合并两个有序数组的过程,实现时主要分为两个过程:

    1. 拆分 - 递归的将当前数组二分(如果N是偶数,两边个数平等,如果是奇数,则一边多一个元素),直到只剩 0 或 1 个元素
    2. 归并 - 分别将左右半边数组排序,然后归并在一起形成一个大的有序数组

    归并排序

    二路归并递归实现,核心代码:

    public static void mergeSort(int[] a, int low, int high) {
      // 要排序的数组 a[low..high]
      if (low < high) {// 是否还能再二分 low >= high (0 或 1 个元素)
        int mid = low + (high - low) / 2; // 取中间值,避免 int 溢出
        mergeSort(a, low, mid); // 将左半边排序
        mergeSort(a, mid + 1, high); // 将右半边排序
        merge(a, low, mid, high); // 归并左右两边
      }
    }
    public static void merge(int[] a, int low, int mid, int high) {
      int n = high - low + 1; // 合并后元素总数
      int[] b = new int[n]; // 临时合并数组
      int left = low, // 左边有序序列起始下标
        right = mid + 1, // 右边有序序列起始下标
        bIdx = 0;
      // 按升序归并到新数组  b 中
      while (left <= mid && right <= high) {
        b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
      }
      // 右边序列已拷贝完毕,左边还有剩余,将其依次拷贝到合并数组中
      while (left <= mid) {
        b[bIdx++] = a[left++];
      }
      // 左边序列已拷贝完毕,右边还有剩余,将其依次拷贝到合并数组中
      while (right <= high) {
        b[bIdx++] = a[right++];
      }
      // 将归并后的数组元素拷贝到原数组适当位置
      for (int k = 0; k < n; k++) {
        a[low + k] = b[k];
      }
    }

    数组拆分和方法调用的动态情况如下图(右键查看大图):

    拆分和方法调用

    递归的本质就是压栈,对于 Java 来说,调用层次太深有可能造成栈溢出。一般的,递归都能转为迭代实现,有时迭代也是对算法的优化。

    归并排序中的递归主要是拆分数组,所以,非递归的重点就是把这部分改成迭代,它们的终止条件不同:

    • 递归是在遇到基本情况时终止,比如遇到了两个各包含1个元素的数组,从大数组到小数组,自顶向下
    • 迭代则相反,自底向上,它首先按 1 切分保证数组中的每2个元素有序,然后按 2 切分,保证数组中的每4个元素有序,以此类推,直到整个数组有序

    核心代码:

    public static void unRecursiveMergeSort(int[] a, int n) {
      int low = 0, high = 0, mid = 0;
      // 待归并数组长度,1 2 4 8 ...
      int len = 1; // 从最小分割单位 1 开始 
      while(len <= n) {
        // 按分割单位遍历数组并合并
        for (int i = 0; i + len <= n; i += len * 2) {
          low = i;
          // mid 变量主要是在合并时找到右半边数组的起始下标
          mid = i + len - 1;
          high = i + 2 * len - 1;
          // 防止超过数组长度
          if (high > n - 1) {
            high = n - 1;
          }
          // 归并两个有序的子数组
          merge(a, low, mid, high);
        }
        len *= 2; // 增加切分单位
      }
    }

    算法分析:

    • 平均时间复杂度,最佳和最差情况都是 O(nlgn)
    • 空间复杂度 O(n),需要一个大小为 n 的临时数组
    • 归并排序也是一个稳定的排序算法

    6. 快速排序

    快排可以说是应用最广泛的算法了,它的特点是使用很小的辅助栈原地排序。它也是一个分而治之的排序算法,基本思想是:选取一个关键值,将数组分成两部分,一部分小于关键值,一部分大于关键值,然后递归的对左右两部分排序。过程如下:

    1. 选取 a[low] 作为关键值-切分元素 p
    2. 使用两个指针遍历数组(既可一前一后,也可同方向移动),将比 p 小的元素前移,最后交换切分元素
    3. 递归的对左右部分进行排序

    快速排序

    递归实现快排核心代码:

    public static void quickSort(int[] a, int low, int high) {
      if (low < high) {
        int m = partition(a, low, high); // 切分
        quickSort(a, low, m-1);  // 将左半部分排序 
        quickSort(a, m+1, high); // 将右半部分排序 
      }
    }
    public static int partition(int[] a, int low, int high) {
      // 将数组切分为 a[low..i-1], a[i], a[i+1..high]
      int p = a[low]; // 切分元素
      int i = low; // 下一个小于切分元素可插入的位置
      // 从切分元素下一个位置开始,遍历整个数组,进行分区
      for (int j = low + 1; j <= high; j++) {
        // 往前移动比切分元素小的元素
        if (a[j] < p && (i++ != j)) {
          int tmp = a[j];
          a[j] = a[i];
          a[i] = tmp;
        }
      }
      // 交换中枢(切分)元素
      int tmp = a[low];
      a[low] = a[i];
      a[i] = tmp;
      return i;
    }

    算法分析:

    • 平均时间复杂度 O(nlgn),最佳情况 O(nlgn),最差情况是 O(n^2)
    • 空间复杂度 O(lgn),因为递归,占用调用栈空间
    • 快排是一个不稳定的排序算法

    7. 堆排序

    堆排序是利用这种数据结构设计的算法。堆可看作一个完全二叉树,它按层级在数组中存储,数组下标为 k 的节点的父子节点位置分别如下:

    • k 位置的父节点位置在 (k-1)/2 向下取整
    • k 位置的左子节点位置在 2k+1
    • k 位置的右子节点位置在 2k+2

    堆的表示如下:

    堆的表示

    堆有序的定义是每个节点都大于等于它的两个子节点,所以根节点是有序二叉堆中值最大的节点。堆排序就是一个不断移除根节点,使用数组剩余元素重新构建堆的过程,和选择排序有点类似(只不过按降序取元素),构建堆有序数组基本步骤如下:

    1. 首先使用 (N-1)/2 之前的元素构建堆,完成后,整个堆最大元素位于数组的 0 下标位置
    2. 把数组首尾数据交换,此时数组最大值以找到
    3. 把堆的尺寸缩小 1,重复步骤 1 和 2,直到堆的尺寸为 1

    堆排序动图

    核心代码:

    public static void heapSort(int[] a) {
      int n = a.length - 1;
      // 构建堆,一开始可将数组看作无序的堆
      // 将从下标为 n/2 开始到 0 的元素下沉到合适的位置
      // 因为 n/2 后面的元素都是叶子结点,无需下沉
      for (int k = n/2; k >= 0; k--)
        sink(a, k, n);
      
      // 下沉排序
      // 堆的根结点永远是最大值,所以只需将最大值和最后一位的元素交换即可
      // 然后再维护一个除原最大结点以外的 n-1 的堆,再将新堆的根节点放在倒数第二的位置,如此反复
      while (n > 0) {
        // 将 a[1] 与最大的元素 a[n] 交换,并修复堆
        int tmp = a[0];
        a[0] = a[n];
        a[n] = tmp;
        // 堆大小减1
        n--;
        // 下沉排序,重新构建
        sink(a, 0, n);
      }
    }
    /** 递归的构造大根堆 */
    private static void sink(int[] a, int k, int n) {
      // 是否存在左孩子节点
      while ((2*k+1) <= n) {
        // 左孩子下标
        int left = 2*k+1;
        
        // left < n 说明存在右孩子,判断将根节点下沉到左还是右
        // 如果左孩子小于右孩子,那么下沉为右子树的根,并且下次从右子树开始判断是否还要下沉
        if (left < n && a[left] < a[left + 1])
          left = left + 1;
        
        // 如果根节点不小于它的子节点,表示这个子树根节点最大
        if (a[k] >= a[left])
          break; // 不用下沉,跳出
        
        // 否则将根节点下沉为它的左子树或右子树的根,也就是将较大的值上调
        int tmp = a[k];
        a[k] = a[left];
        a[left] = tmp;
        
        // 继续从左子树或右子树开始,判断根节点是否还要下沉
        k = left;
      }
    }

    算法分析:

    • 平均时间复杂度、最佳和最坏均是 O(nlgn)
    • 空间复杂度 O(1),原地排序
    • 不稳定的排序算法

    8. 小结

    每次看了,过段时间就忘,这次总结起来,方便查看,也分享给大家,有问题欢迎交流。首发于公众号「顿悟源码」,搜索获取更多源码分析和造的轮子。

    如果你对编程感兴趣或者想往编程方向发展,可以关注微信公众号【筑梦编程】,大家一起交流讨论!小编也会每天定时更新既有趣又有用的编程知识!

    展开全文
  • 容易理解文档 快速获取算法的源代码 随时获取时间复杂度 安装 仅需在终端中执行以下命令: pip3 install pygorithm *如果你使用是Python 2.7,请使用pip来安装。如果存在用户权限限制,你可能需要使用...
  • 针对JSSP问题因其复杂度较高容易导致算法陷入局部最优不足,引入学习小组协同学习,通过组内学习和组内交流,使学习过程跳出当前局限.为了兼顾局部和全局搜索能力,引入基于学习能力深度和广度搜索策略,小组内学生...
  • 本文目的,是务实、简洁地盘点一番当前...机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最...

    5cc9d653737323573b7de4915a80d647.gif

    本文的目的,是务实、简洁地盘点一番当前机器学习算法。文中内容结合了个人在查阅资料过程中收集到的前人总结,同时添加了部分自身总结,在这里,依据实际使用中的经验,将对此类模型优缺点及选择详加讨论

    主要回顾下几个常用算法的适应场景及其优缺点!

    机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普遍认同的算法,诸如SVM,GBDT,Adaboost,现在深度学习很火热,神经网络也是一个不错的选择。

    假如你在乎精度(accuracy)的话,最好的方法就是通过交叉验证(cross-validation)对各个算法一个个地进行测试,进行比较,然后调整参数确保每个算法达到最优解,最后选择最好的一个。但是如果你只是在寻找一个“足够好”的算法来解决你的问题,或者这里有些技巧可以参考,下面来分析下各个算法的优缺点,基于算法的优缺点,更易于我们去选择它。

    1.天下没有免费的午餐

    在机器学习领域,一个基本的定理就是“没有免费的午餐”。换言之,就是没有算法能完美地解决所有问题,尤其是对监督学习而言(例如预测建模)。

    举例来说,你不能去说神经网络任何情况下都能比决策树更有优势,反之亦然。它们要受很多因素的影响,比如你的数据集的规模或结构。

    其结果是,在用给定的测试集来评估性能并挑选算法时,你应当根据具体的问题来采用不同的算法。

    当然,所选的算法必须要适用于你自己的问题,这就要求选择正确的机器学习任务。作为类比,如果你需要打扫房子,你可能会用到吸尘器、扫帚或是拖把,但你绝对不该掏出铲子来挖地。

    2. 偏差&方差

    在统计学中,一个模型好坏,是根据偏差和方差来衡量的,所以我们先来普及一下偏差(bias)和方差(variance):

    1. 偏差:描述的是预测值(估计值)的期望E’与真实值Y之间的差距。偏差越大,越偏离真实数据。

    cc7ec7e43bfb714d86dea4d1fa3a287d.png

    2. 方差:描述的是预测值P的变化范围,离散程度,是预测值的方差,也就是离其期望值E的距离。方差越大,数据的分布越分散。

    66e0898da571430e2f0903aa0829e063.png

    模型的真实误差是两者之和,如公式:

    64c490fc6e725979f07aea60d4252e91.png

    通常情况下,如果是小训练集,高偏差/低方差的分类器(例如,朴素贝叶斯NB)要比低偏差/高方差大分类的优势大(例如,KNN),因为后者会发生过拟合(overfiting)。然而,随着你训练集的增长,模型对于原数据的预测能力就越好,偏差就会降低,此时低偏差/高方差的分类器就会渐渐的表现其优势(因为它们有较低的渐近误差),而高偏差分类器这时已经不足以提供准确的模型了。

    为什么说朴素贝叶斯是高偏差低方差?

    首先,假设你知道训练集和测试集的关系。简单来讲是我们要在训练集上学习一个模型,然后拿到测试集去用,效果好不好要根据测试集的错误率来衡量。但很多时候,我们只能假设测试集和训练集的是符合同一个数据分布的,但却拿不到真正的测试数据。这时候怎么在只看到训练错误率的情况下,去衡量测试错误率呢?

    由于训练样本很少(至少不足够多),所以通过训练集得到的模型,总不是真正正确的。(就算在训练集上正确率100%,也不能说明它刻画了真实的数据分布,要知道刻画真实的数据分布才是我们的目的,而不是只刻画训练集的有限的数据点)。

    而且,实际中,训练样本往往还有一定的噪音误差,所以如果太追求在训练集上的完美而采用一个很复杂的模型,会使得模型把训练集里面的误差都当成了真实的数据分布特征,从而得到错误的数据分布估计。这样的话,到了真正的测试集上就错的一塌糊涂了(这种现象叫过拟合)。但是也不能用太简单的模型,否则在数据分布比较复杂的时候,模型就不足以刻画数据分布了(体现为连在训练集上的错误率都很高,这种现象较欠拟合)。过拟合表明采用的模型比真实的数据分布更复杂,而欠拟合表示采用的模型比真实的数据分布要简单。

    在统计学习框架下,大家刻画模型复杂度的时候,有这么个观点,认为Error = Bias + Variance。这里的Error大概可以理解为模型的预测错误率,是有两部分组成的,一部分是由于模型太简单而带来的估计不准确的部分(Bias),另一部分是由于模型太复杂而带来的更大的变化空间和不确定性(Variance)。

    所以,这样就容易分析朴素贝叶斯了。它简单的假设了各个数据之间是无关的,是一个被严重简化了的模型。所以,对于这样一个简单模型,大部分场合都会Bias部分大于Variance部分,也就是说高偏差而低方差。

    在实际中,为了让Error尽量小,我们在选择模型的时候需要平衡Bias和Variance所占的比例,也就是平衡over-fitting和under-fitting。

    当模型复杂度上升的时候,偏差会逐渐变小,而方差会逐渐变大。

    3. 常见算法优缺点

     3.1 朴素贝叶斯 

    朴素贝叶斯属于生成式模型(关于生成模型和判别式模型,主要还是在于是否需要求联合分布),比较简单,你只需做一堆计数即可。如果注有条件独立性假设(一个比较严格的条件),朴素贝叶斯分类器的收敛速度将快于判别模型,比如逻辑回归,所以你只需要较少的训练数据即可。即使NB条件独立假设不成立,NB分类器在实践中仍然表现的很出色。它的主要缺点是它不能学习特征间的相互作用,用mRMR中R来讲,就是特征冗余。引用一个比较经典的例子,比如,虽然你喜欢Brad Pitt和Tom Cruise的电影,但是它不能学习出你不喜欢他们在一起演的电影。

    优点:

    1. 朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率;

    2. 对大数量训练和查询时具有较高的速度。即使使用超大规模的训练集,针对每个项目通常也只会有相对较少的特征数,并且对项目的训练和分类也仅仅是特征概率的数学运算而已;

    3. 对小规模的数据表现很好,能个处理多分类任务,适合增量式训练(即可以实时的对新增的样本进行训练);

    4. 对缺失数据不太敏感,算法也比较简单,常用于文本分类;

    5. 朴素贝叶斯对结果解释容易理解。

    缺点:

    1. 需要计算先验概率;

    2. 分类决策存在错误率;

    3. 对输入数据的表达形式很敏感;

    4. 由于使用了样本属性独立性的假设,所以如果样本属性有关联时其效果不好。

    朴素贝叶斯应用领域

    1. 欺诈检测中使用较多;

    2. 一封电子邮件是否是垃圾邮件;

    3. 一篇文章应该分到科技、政治,还是体育类;

    4. 一段文字表达的是积极的情绪还是消极的情绪;

    5. 人脸识别。

     3.2 Logistic Regression(逻辑回归) 

    逻辑回归属于判别式模型,同时伴有很多模型正则化的方法(L0, L1,L2,etc),而且你不必像在用朴素贝叶斯那样担心你的特征是否相关。与决策树、SVM相比,你还会得到一个不错的概率解释,你甚至可以轻松地利用新数据来更新模型(使用在线梯度下降算法-online gradient descent)。如果你需要一个概率架构(比如,简单地调节分类阈值,指明不确定性,或者是要获得置信区间),或者你希望以后将更多的训练数据快速整合到模型中去,那么使用它吧。

    Sigmoid函数:表达式如下:

    e259efd4c5966fe42622c734c2ec698d.png

    优点:

    1. 实现简单,广泛的应用于工业问题上;

    2. 分类时计算量非常小,速度很快,存储资源低;

    3. 便利的观测样本概率分数;

    4. 对逻辑回归而言,多重共线性并不是问题,它可以结合L2正则化来解决该问题;

    5. 计算代价不高,易于理解和实现。

    缺点:

    1. 当特征空间很大时,逻辑回归的性能不是很好;

    2. 容易欠拟合,一般准确度不太高;

    3. 不能很好地处理大量多类特征或变量;

    4. 只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;

    5. 对于非线性特征,需要进行转换。

    logistic回归应用领域:

    1. 用于二分类领域,可以得出概率值,适用于根据分类概率排名的领域,如搜索排名等;

    2. Logistic回归的扩展softmax可以应用于多分类领域,如手写字识别等;

    3. 信用评估;

    4. 测量市场营销的成功度;

    5. 预测某个产品的收益;

    6. 特定的某天是否会发生地震。

     3.3 线性回归 

    线性回归是用于回归的,它不像Logistic回归那样用于分类,其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优化,当然也可以用normal equation直接求得参数的解,结果为: 

    210dbc61af08d891a603fda0642d309d.png

    而在LWLR(局部加权线性回归)中,参数的计算表达式为: 

    ee904804b2b835e3c224041437cb0cfc.png

    由此可见LWLR与LR不同,LWLR是一个非参数模型,因为每次进行回归计算都要遍历训练样本至少一次。

    优点: 实现简单,计算简单。

    缺点: 不能拟合非线性数据。

     3.4 最近邻算法——KNN 

    KNN即最近邻算法,其主要过程为:

    1. 计算训练样本和测试样本中每个样本点的距离(常见的距离度量有欧式距离,马氏距离等); 

    2. 对上面所有的距离值进行排序(升序);

    3. 选前k个最小距离的样本;

    4. 根据这k个样本的标签进行投票,得到最后的分类类别。

    如何选择一个最佳的K值,这取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响,但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取,比如,交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。近邻算法具有较强的一致性结果,随着数据趋于无限,算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值,K近邻保证错误率不会超过贝叶斯理论误差率。

    KNN算法的优点

    1. 理论成熟,思想简单,既可以用来做分类也可以用来做回归;

    2. 可用于非线性分类;

    3. 训练时间复杂度为O(n);

    4. 对数据没有假设,准确度高,对outlier不敏感;

    5. KNN是一种在线技术,新数据可以直接加入数据集而不必进行重新训练;

    6. KNN理论简单,容易实现。

    缺点

    1. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少)效果差;

    2. 需要大量内存;

    3. 对于样本容量大的数据集计算量比较大(体现在距离计算上);

    4. 样本不平衡时,预测偏差比较大。如:某一类的样本比较少,而其它类样本比较多;

    5. KNN每一次分类都会重新进行一次全局运算;

    6. k值大小的选择没有理论选择最优,往往是结合K-折交叉验证得到最优k值选择。

    KNN算法应用领域

    文本分类、模式识别、聚类分析,多分类领域

     3.5 决策树 

    决策树的一大优势就是易于解释。它可以毫无压力地处理特征间的交互关系并且是非参数化的,因此你不必担心异常值或者数据是否线性可分(举个例子,决策树能轻松处理好类别A在某个特征维度x的末端,类别B在中间,然后类别A又出现在特征维度x前端的情况)。它的缺点之一就是不支持在线学习,于是在新样本到来后,决策树需要全部重建。另一个缺点就是容易出现过拟合,但这也就是诸如随机森林RF(或提升树boosted tree)之类的集成方法的切入点。另外,随机森林经常是很多分类问题的赢家(通常比支持向量机好上那么一丁点),它训练快速并且可调,同时你无须担心要像支持向量机那样调一大堆参数,所以在以前都一直很受欢迎。

    决策树中很重要的一点就是选择一个属性进行分枝,因此要注意一下信息增益的计算公式,并深入理解它。

    信息熵的计算公式如下:

    2e2e9f74b8378a2b2c02562f4dc99272.png

    其中的n代表有n个分类类别(比如假设是二类问题,那么n=2)。分别计算这2类样本在总样本中出现的概率

    92d3526528974efde73611fb5ae99668.png

    833c3c7c3daeaa72fe6994babe00dc4b.png

    ,这样就可以计算出未选中属性分枝前的信息熵。

    现在选中一个属性

    fa13be0cfff8b629331afe2b94526272.png

    用来进行分枝,此时分枝规则是:如果

    996ffd6d5a34d79fb1f603d7f986c114.png

    的话,将样本分到树的一个分支;如果不相等则进入另一个分支。很显然,分支中的样本很有可能包括2个类别,分别计算这2个分支的熵

    8285aaf2b5600b9713a80c03c0b1da06.png

    和 

    dd87cae84c745422d8a9a0013d6cf2c1.png

    ,计算出分枝后的总信息熵

    d608f582a3beef692be9bf464d830a57.png

    ,则此时的信息增益

    27d6ab6473ded561957b631606ea39aa.png

    。以信息增益为原则,把所有的属性都测试一边,选择一个使增益最大的属性作为本次分枝属性。

    决策树自身的优点

    1. 决策树易于理解和解释,可以可视化分析,容易提取出规则;

    2. 可以同时处理标称型和数值型数据;

    3. 比较适合处理有缺失属性的样本;

    4. 能够处理不相关的特征;

    5. 测试数据集时,运行速度比较快;

    6. 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

    缺点

    1. 容易发生过拟合(随机森林可以很大程度上减少过拟合);

    2. 容易忽略数据集中属性的相互关联;

    3. 对于那些各类别样本数量不一致的数据,在决策树中,进行属性划分时,不同的判定准则会带来不同的属性选择倾向;信息增益准则对可取数目较多的属性有所偏好(典型代表ID3算法),而增益率准则(CART)则对可取数目较少的属性有所偏好,但CART进行属性划分时候不再简单地直接利用增益率尽心划分,而是采用一种启发式规则)(只要是使用了信息增益,都有这个缺点,如RF)。

    4. ID3算法计算信息增益时结果偏向数值比较多的特征。

    改进措施

    1. 对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法;

    2. 使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题。

    应用领域

    企业管理实践,企业投资决策,由于决策树很好的分析能力,在决策过程应用较多。

    3.5.1 ID3、C4.5算法

    ID3算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益,并选取具有最高增益的属性作为给定的测试属性。C4.5算法核心思想是ID3算法,是ID3算法的改进,改进方面有: - 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; - 在树构造过程中进行剪枝; - 能处理非离散的数据; - 能处理不完整的数据。

    优点

    产生的分类规则易于理解,准确率较高。

    缺点

    1. 在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效;

    2. C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

    3.5.2 CART分类与回归树

    是一种决策树分类方法,采用基于最小距离的基尼指数估计函数,用来决定由该子数据集生成的决策树的拓展形。如果目标变量是标称的,称为分类树;如果目标变量是连续的,称为回归树。分类树是使用树结构算法将数据分成离散类的方法。

    优点

    1. 非常灵活,可以允许有部分错分成本,还可指定先验概率分布,可使用自动的成本复杂性剪枝来得到归纳性更强的树;

    2. 在面对诸如存在缺失值、变量数多等问题时CART 显得非常稳健。

     3.6 Adaboosting 

    Adaboost是一种加和模型,每个模型都是基于上一次模型的错误率来建立的,过分关注分错的样本,而对正确分类的样本减少关注度,逐次迭代之后,可以得到一个相对较好的模型。该算法是一种典型的boosting算法,其加和理论的优势可以使用Hoeffding不等式得以解释。

    优点

    1. Adaboost是一种有很高精度的分类器;

    2. 可以使用各种方法构建子分类器,Adaboost算法提供的是框架;

    3. 当使用简单分类器时,计算出的结果是可以理解的,并且弱分类器的构造极其简单;

    4. 简单,不用做特征筛选;

    5. 不易发生overfitting。

    缺点

    对outlier比较敏感。

     3.7 SVM支持向量机 

    支持向量机,一个经久不衰的算法,高准确率,为避免过拟合提供了很好的理论保证,而且就算数据在原特征空间线性不可分,只要给个合适的核函数,它就能运行得很好。在动辄超高维的文本分类问题中特别受欢迎。可惜内存消耗大,难以解释,运行和调参也有些烦人,而随机森林却刚好避开了这些缺点,比较实用。

    优点

    1. 可以解决高维问题,即大型特征空间;

    2. 解决小样本下机器学习问题;

    3. 能够处理非线性特征的相互作用;

    4. 无局部极小值问题;(相对于神经网络等算法)

    5. 无需依赖整个数据;

    6. 泛化能力比较强。

    缺点

    1. 当观测样本很多时,效率并不是很高;

    2. 对非线性问题没有通用解决方案,有时候很难找到一个合适的核函数;

    3. 对于核函数的高维映射解释力不强,尤其是径向基函数;

    4. 常规SVM只支持二分类;

    5. 对缺失数据敏感。

    对于核的选择也是有技巧的(libsvm中自带了四种核函数:线性核、多项式核、RBF以及sigmoid核):

    第一,如果样本数量小于特征数,那么就没必要选择非线性核,简单的使用线性核就可以了;

    第二,如果样本数量大于特征数目,这时可以使用非线性核,将样本映射到更高维度,一般可以得到更好的结果;

    第三,如果样本数目和特征数目相等,该情况可以使用非线性核,原理和第二种一样。

    对于第一种情况,也可以先对数据进行降维,然后使用非线性核,这也是一种方法。

    SVM应用领域

    文本分类、图像识别(主要二分类领域,毕竟常规SVM只能解决二分类问题)

     3.8 人工神经网络的优缺点 

    人工神经网络的优点:

    1. 分类的准确度高;

    2. 并行分布处理能力强,分布存储及学习能力强;

    3. 对噪声神经有较强的鲁棒性和容错能力;

    4. 具备联想记忆的功能,能充分逼近复杂的非线性关系。

    人工神经网络的缺点:

    1. 神经网络需要大量的参数,如网络拓扑结构、权值和阈值的初始值;

    2. 黑盒过程,不能观察之间的学习过程,输出结果难以解释,会影响到结果的可信度和可接受程度;

    3. 学习时间过长,有可能陷入局部极小值,甚至可能达不到学习的目的。

    人工神经网络应用领域:

    目前深度神经网络已经应用与计算机视觉,自然语言处理,语音识别等领域并取得很好的效果。

     3.9 K-Means聚类 

    是一个简单的聚类算法,把n的对象根据他们的属性分为k个分割,k< n。 算法的核心就是要优化失真函数J,使其收敛到局部最小值但不是全局最小值。

    关于K-Means聚类的文章,参见机器学习算法-K-means聚类。关于K-Means的推导,里面可是有大学问的,蕴含着强大的EM思想。

    优点

    1. 算法简单,容易实现 ;

    2. 算法速度很快;

    3. 对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<

    4. 算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,且簇与簇之间区别明显时,聚类效果较好。

    缺点

    1. 对数据类型要求较高,适合数值型数据;

    2. 可能收敛到局部最小值,在大规模数据上收敛较慢;

    3. 分组的数目k是一个输入参数,不合适的k可能返回较差的结果;

    4. 对初值的簇心值敏感,对于不同的初始值,可能会导致不同的聚类结果;

    5. 不适合于发现非凸面形状的簇,或者大小差别很大的簇;

    6. 对于”噪声”和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。

     3.10 EM最大期望算法 

    EM算法是基于模型的聚类方法,是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量,M步估计其他参数,交替将极值推向最大。

    EM算法比K-means算法计算复杂,收敛也较慢,不适于大规模数据集和高维数据,但比K-means算法计算结果稳定、准确。EM经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。

     3.11 集成算法(AdaBoost算法) 

    AdaBoost算法优点:

    1. 很好的利用了弱分类器进行级联;

    2. 可以将不同的分类算法作为弱分类器;

    3. AdaBoost具有很高的精度;

    4. 相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重。

    Adaboost算法缺点:

    1. AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定;

    2. 数据不平衡导致分类精度下降;

    3. 训练比较耗时,每次重新选择当前分类器最好切分点。

    AdaBoost应用领域:

    模式识别、计算机视觉领域,用于二分类和多分类场景

     3.12 排序算法(PageRank) 

    PageRank是google的页面排序算法,是基于从许多优质的网页链接过来的网页,必定还是优质网页的回归关系,来判定所有网页的重要性。(也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。)

    PageRank优点

    完全独立于查询,只依赖于网页链接结构,可以离线计算。

    PageRank缺点

    1. PageRank算法忽略了网页搜索的时效性;

    2. 旧网页排序很高,存在时间长,积累了大量的in-links,拥有最新资讯的新网页排名却很低,因为它们几乎没有in-links。

     3.13 关联规则算法(Apriori算法) 

    Apriori算法是一种挖掘关联规则的算法,用于挖掘其内含的、未知的却又实际存在的数据关系,其核心是基于两阶段频集思想的递推算法 。

    Apriori算法分为两个阶段:

    1. 寻找频繁项集;

    2. 由频繁项集找关联规则。

    算法缺点:

    1. 在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;

    2. 每次计算项集的支持度时,都对数据库中 的全部记录进行了一遍扫描比较,需要很大的I/O负载。

    4. 算法选择参考

    之前笔者翻译过一些国外的文章,其中有一篇文章中给出了一个简单的算法选择技巧:

    1. 首当其冲应该选择的就是逻辑回归,如果它的效果不怎么样,那么可以将它的结果作为基准来参考,在基础上与其他算法进行比较;

    2. 然后试试决策树(随机森林)看看是否可以大幅度提升你的模型性能。即便最后你并没有把它当做为最终模型,你也可以使用随机森林来移除噪声变量,做特征选择;

    3. 如果特征的数量和观测样本特别多,那么当资源和时间充足时(这个前提很重要),使用SVM不失为一种选择。

    通常情况下:【GBDT>=SVM>=RF>=Adaboost>=Other…】,现在深度学习很热门,很多领域都用到,它是以神经网络为基础的,目前笔者自己也在学习,只是理论知识不扎实,理解的不够深入,这里就不做介绍了,希望以后可以写一片抛砖引玉的文章。

    算法固然重要,但好的数据却要优于好的算法,设计优良特征是大有裨益的。假如你有一个超大数据集,那么无论你使用哪种算法可能对分类性能都没太大影响(此时就可以根据速度和易用性来进行抉择)。

    编辑 ∑ Gemini

    来源:知乎

    推荐阅读

    b49efc5bc9e2b27743f780ee125b27e8.png

    今日问题

    逻辑回归和线性回归的区别和联系?

    PS:可以查阅资料后再回来答题

    打卡格式:打卡第n天,答:...

    487ed709167d7bbef076d07db4cb1452.png

    展开全文
  • 而排序算法也是各有千秋,每个都有自身优点和局限性。虽然这些算法平常根本就不用自己去编写,但作为一个有追求程序员,还是要了解它们从不同角度解决排序问题思想。学习算法是枯燥,那怎么高效理解它...

    排序是一个经典的问题,它以一定的顺序对一个数组或列表中的元素进行重新排序。而排序算法也是各有千秋,每个都有自身的优点和局限性。虽然这些算法平常根本就不用自己去编写,但作为一个有追求的程序员,还是要了解它们从不同角度解决排序问题的思想。

    学习算法是枯燥的,那怎么高效的理解它的原理呢?显然,如果以动图的方式,生动形象的把算法排序的过程展示出来,非常有助于学习。visualgo.net 就是一个可视化算法的网站,第一次访问的时候,真的是眼前一亮。本文就对常用的排序进行下总结。

    1. 冒泡排序

    冒泡排序的基本思想就是:把小的元素往前调或者把大的元素往后调。假设数组有 N 个元素,冒泡排序过程如下:

    1. 从当前元素起,向后依次比较每一对相邻元素(a,b)
    2. 如果 a>b 则交换这两个数
    3. 重复步骤1和2,直到比较最后一对元素(第 N-2 和 N-1 元素)
    4. 此时最大的元素已位于数组最后的位置,然后将 N 减 1,并重复步骤1,直到 N=1
    00c014531c95209feb81716001f014b7.gif

    冒泡排序的核心代码:

    public static void bubbleSort(int[] a, int n) { // 排序趟数,最后一个元素不用比较所以是 (n-1) 趟 for (int i = 0; i < n - 1; i++) { // 每趟比较的次数,第 i 趟比较 (n-1-i) 次 for (int j = 0; j < n - 1 - i; j++) { // 比较相邻元素,若逆序则交换 if (a[j] > a[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } }}

    难点在于边界的确定,算法分析:

    • 平均时间复杂度是 O(n^2),最佳情况是 O(n),最差情况是 O(n^2)
    • 空间复杂度 O(1)
    • 稳定的排序算法(相等元素的前后顺序排序后不变)

    2. 选择排序

    选择排序的基本思想就是:每次从未排序的列表中找到最小(大)的元素,放到已排序序列的末尾,直到所有元素排序完毕。假设数组有 N 个元素且 L=0,选择排序过程如下:

    1. 从 [L...N-1] 范围中找到最小元素的下标 X
    2. 交换第 X 与第 L 位置的元素值
    3. L 加 1,重复以上步骤,直到 L=N-2
    2a3687c6de7c79886b628818dcd712c9.gif

    选择排序的核心代码:

    public static void selectionSort(int[] a, int n) { // 排序趟数,最后一个元素是最大的不用比较所以是 (n-1) 趟 for (int i = 0; i < n-1; i++) { int minIndex = i; // 无序列表中最小元素的下标 for (int j = i+1; j < n; j++) { // 在无序列表中查找最小元素的小标并记录 if (a[j] < a[minIndex]) { minIndex = j; } }// 将最小元素交换到本次循环的前端 int tmp = a[minIndex]; a[minIndex] = a[i]; a[i] = tmp; }}

    算法分析:

    • 平均时间复杂度是 O(n^2),最佳和最差情况也是一样
    • 空间复杂度 O(1)
    • 不稳定的排序算法(相等元素的前后顺序排序后可能改变)

    3. 插入排序

    插入排序的基本思想是:每次将待插入的元素,按照大小插入到前面已排序序列的适当位置上。插入排序过程如下:

    1. 从第一个元素开始,该元素可认为已排序
    2. 取出下一个元素,在已排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于待插入元素 ,把它移到下一个位置
    4. 重复步骤 3,直到找到一个小于或等于待插入元素的位置,将待插入元素插入到下一个位置
    5. 重复步骤 2~5,直到取完数组元素
    d46eb301d1d97c16747352a0182d0e43.gif

    插入排序的核心代码:

    public static void insertionSort(int[] a, int n) { // a[0] 看做已排序 for (int i = 1; i < n; i++) { int x = a[i]; // 待插入元素 int j=i-1; // 插入的位置 while (j >= 0 && a[j] > x) { a[j+1] = a[j]; // 为待插入元素腾地 j--; } a[j+1] = x; // 插入到下一个位置 j+1 }}

    算法分析:

    • 平均时间复杂度是 O(n^2),最佳情况是 O(n),最差情况是 O(n^2)
    • 空间复杂度 O(1)
    • 稳定的排序算法

    4. 希尔排序

    希尔排序也称为增量递减排序,是对直接插入算法的改进,基于以下两点性质:

    • 插入排序在对几乎已排好序的数据操作时,效率高,可以达到线性排序的效率
    • 但插入排序一般来说是低效的,因为插入排序每次只能移动一位数据

    希尔排序的改进是,使用一个增量将数组切分不同的分组,然后在组内进行插入排序,递减增量,直到增量为 1,好处就是数据能跨多个元素移动,一次比较就可能消除多个元素的交换。基本过程如下:

    1. 选取一个递增序列,一般使用x/2或者x/3+1
    2. 使用序列中最大的增量,对数组分组,在组内插入排序,递减增量,直到为 1
    013f76c9a01b17b5f5ffe00319fba0c0.gif

    核心代码:

    public static void shellSort(int[] a, int n) { // 计算递增序列,3x+1 : 1, 4, 13, 40, 121, 364, 1093, ...  int h = 1; while (h < n/3) h = 3*h + 1;  while (h >= 1) {// 直到间隔为 1 // 按间隔 h 切分数组 for (int i = h; i < n; i++) { // 对 a[i], a[i-h], a[i-2*h], a[i-3*h]...使用插入排序 int x = a[i]; // 待插入元素 int j=i; while (j >=h && x < a[j-h]) { a[j] = a[j-h];// 为待插入元素腾地 j -= h; } a[j] = x; // 插入 x } // 递减增量 h /= 3; }}

    希尔排序数组拆分插入图解,上面的动图可以辅助理解,与下图数据不一致:

    8c244b31f536847fe60892ec69754e5a.png

    算法分析:

    • 时间复杂度与选择的增量序列有关,可能的值时 O(n^2) > O(n^1.5) > O(nlg2n)
    • 空间复杂度 O(1)
    • 不稳定的排序算法

    5. 归并排序(递归&非递归)

    归并排序是分而治之的排序算法,基本思想是:将待排序序列拆分多个子序列,先使每个子序列有序,再使子序列间有序,最终得到完整的有序序列。归并排序本质就是不断合并两个有序数组的过程,实现时主要分为两个过程:

    1. 拆分 - 递归的将当前数组二分(如果N是偶数,两边个数平等,如果是奇数,则一边多一个元素),直到只剩 0 或 1 个元素
    2. 归并 - 分别将左右半边数组排序,然后归并在一起形成一个大的有序数组
    16069f4150f8f5b3d4ca88005798b791.gif

    二路归并递归实现,核心代码:

    public static void mergeSort(int[] a, int low, int high) { // 要排序的数组 a[low..high] if (low < high) {// 是否还能再二分 low >= high (0 或 1 个元素) int mid = low + (high - low) / 2; // 取中间值,避免 int 溢出 mergeSort(a, low, mid); // 将左半边排序 mergeSort(a, mid + 1, high); // 将右半边排序 merge(a, low, mid, high); // 归并左右两边 }}public static void merge(int[] a, int low, int mid, int high) { int n = high - low + 1; // 合并后元素总数 int[] b = new int[n]; // 临时合并数组 int left = low, // 左边有序序列起始下标 right = mid + 1, // 右边有序序列起始下标 bIdx = 0; // 按升序归并到新数组 b 中 while (left <= mid && right <= high) { b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++]; } // 右边序列已拷贝完毕,左边还有剩余,将其依次拷贝到合并数组中 while (left <= mid) { b[bIdx++] = a[left++]; } // 左边序列已拷贝完毕,右边还有剩余,将其依次拷贝到合并数组中 while (right <= high) { b[bIdx++] = a[right++]; } // 将归并后的数组元素拷贝到原数组适当位置 for (int k = 0; k < n; k++) { a[low + k] = b[k]; }}

    数组拆分和方法调用的动态情况如下图(右键查看大图):

    780194d23420f68c3c5f4a2bd024373d.png

    递归的本质就是压栈,对于 Java 来说,调用层次太深有可能造成栈溢出。一般的,递归都能转为迭代实现,有时迭代也是对算法的优化。

    归并排序中的递归主要是拆分数组,所以,非递归的重点就是把这部分改成迭代,它们的终止条件不同:

    • 递归是在遇到基本情况时终止,比如遇到了两个各包含1个元素的数组,从大数组到小数组,自顶向下
    • 迭代则相反,自底向上,它首先按 1 切分保证数组中的每2个元素有序,然后按 2 切分,保证数组中的每4个元素有序,以此类推,直到整个数组有序

    核心代码:

    public static void unRecursiveMergeSort(int[] a, int n) { int low = 0, high = 0, mid = 0; // 待归并数组长度,1 2 4 8 ... int len = 1; // 从最小分割单位 1 开始  while(len <= n) { // 按分割单位遍历数组并合并 for (int i = 0; i + len <= n; i += len * 2) { low = i; // mid 变量主要是在合并时找到右半边数组的起始下标 mid = i + len - 1; high = i + 2 * len - 1; // 防止超过数组长度 if (high > n - 1) { high = n - 1; } // 归并两个有序的子数组 merge(a, low, mid, high); } len *= 2; // 增加切分单位 }}

    算法分析:

    • 平均时间复杂度,最佳和最差情况都是 O(nlgn)
    • 空间复杂度 O(n),需要一个大小为 n 的临时数组
    • 归并排序也是一个稳定的排序算法

    6. 快速排序

    快排可以说是应用最广泛的算法了,它的特点是使用很小的辅助栈原地排序。它也是一个分而治之的排序算法,基本思想是:选取一个关键值,将数组分成两部分,一部分小于关键值,一部分大于关键值,然后递归的对左右两部分排序。过程如下:

    1. 选取 a[low] 作为关键值-切分元素 p
    2. 使用两个指针遍历数组(既可一前一后,也可同方向移动),将比 p 小的元素前移,最后交换切分元素
    3. 递归的对左右部分进行排序
    93cacf45035cb03fb852994ba6d4301e.gif

    递归实现快排核心代码:

    public static void quickSort(int[] a, int low, int high) { if (low < high) { int m = partition(a, low, high); // 切分 quickSort(a, low, m-1); // 将左半部分排序  quickSort(a, m+1, high); // 将右半部分排序  }}public static int partition(int[] a, int low, int high) { // 将数组切分为 a[low..i-1], a[i], a[i+1..high] int p = a[low]; // 切分元素 int i = low; // 下一个小于切分元素可插入的位置 // 从切分元素下一个位置开始,遍历整个数组,进行分区 for (int j = low + 1; j <= high; j++) { // 往前移动比切分元素小的元素 if (a[j] < p && (i++ != j)) { int tmp = a[j]; a[j] = a[i]; a[i] = tmp; } } // 交换中枢(切分)元素 int tmp = a[low]; a[low] = a[i]; a[i] = tmp; return i;}

    算法分析:

    • 平均时间复杂度 O(nlgn),最佳情况 O(nlgn),最差情况是 O(n^2)
    • 空间复杂度 O(lgn),因为递归,占用调用栈空间
    • 快排是一个不稳定的排序算法

    7. 堆排序

    堆排序是利用这种数据结构设计的算法。堆可看作一个完全二叉树,它按层级在数组中存储,数组下标为 k 的节点的父子节点位置分别如下:

    • k 位置的父节点位置在 (k-1)/2 向下取整
    • k 位置的左子节点位置在 2k+1
    • k 位置的右子节点位置在 2k+2

    堆的表示如下:

    be03cd91b0aa7af39911443e740fc0d2.png

    堆有序的定义是每个节点都大于等于它的两个子节点,所以根节点是有序二叉堆中值最大的节点。堆排序就是一个不断移除根节点,使用数组剩余元素重新构建堆的过程,和选择排序有点类似(只不过按降序取元素),构建堆有序数组基本步骤如下:

    1. 首先使用 (N-1)/2 之前的元素构建堆,完成后,整个堆最大元素位于数组的 0 下标位置
    2. 把数组首尾数据交换,此时数组最大值以找到
    3. 把堆的尺寸缩小 1,重复步骤 1 和 2,直到堆的尺寸为 1
    cf74ce033fe8f54f79dfdf5023a0b51d.gif

    核心代码:

    public static void heapSort(int[] a) { int n = a.length - 1; // 构建堆,一开始可将数组看作无序的堆 // 将从下标为 n/2 开始到 0 的元素下沉到合适的位置 // 因为 n/2 后面的元素都是叶子结点,无需下沉 for (int k = n/2; k >= 0; k--) sink(a, k, n);  // 下沉排序 // 堆的根结点永远是最大值,所以只需将最大值和最后一位的元素交换即可 // 然后再维护一个除原最大结点以外的 n-1 的堆,再将新堆的根节点放在倒数第二的位置,如此反复 while (n > 0) { // 将 a[1] 与最大的元素 a[n] 交换,并修复堆 int tmp = a[0]; a[0] = a[n]; a[n] = tmp; // 堆大小减1 n--; // 下沉排序,重新构建 sink(a, 0, n); }}/** 递归的构造大根堆 */private static void sink(int[] a, int k, int n) { // 是否存在左孩子节点 while ((2*k+1) <= n) { // 左孩子下标 int left = 2*k+1;  // left < n 说明存在右孩子,判断将根节点下沉到左还是右 // 如果左孩子小于右孩子,那么下沉为右子树的根,并且下次从右子树开始判断是否还要下沉 if (left < n && a[left] < a[left + 1]) left = left + 1;  // 如果根节点不小于它的子节点,表示这个子树根节点最大 if (a[k] >= a[left]) break; // 不用下沉,跳出  // 否则将根节点下沉为它的左子树或右子树的根,也就是将较大的值上调 int tmp = a[k]; a[k] = a[left]; a[left] = tmp;  // 继续从左子树或右子树开始,判断根节点是否还要下沉 k = left; }}

    算法分析:

    • 平均时间复杂度、最佳和最坏均是 O(nlgn)
    • 空间复杂度 O(1),原地排序
    • 不稳定的排序算法

    8. 小结

    每次看排序,过段时间就忘,这次总结起来,方便查看,也分享给大家,有问题欢迎交流。首发于公众号「顿悟源码」,搜索获取更多源码分析和造的轮子。

    展开全文
  • 如果不接触一段时间的算法,真的很容易就忘了。不信?你现在想想你自己能不能手写一个堆排序。经历过校招的人都知道,算法和数据结构都是不可避免的。在笔试的时候,最主要的就是靠算法题。像拼多多、头条这种大公司...
  • 规则学习算法

    2019-02-17 17:35:54
    规则学习(独立而治之) 决策树会给任务带来一组特定偏差,而规则学习可通过直接识别规则...根据相同数据建立模型,规则学习结果往往比决策树结果更加简洁、直观、容易理解。规则学习算法数据利用基于先...
  • PID算法的学习

    2018-09-12 16:33:15
    PID算法中有三个非常重要参数: 1、比例系数Kp 2、积分作用系数Ki 3、微分系数Kd 1、比例系数Kp作用是加快系统响应速度,提高系统调节精度。Kp越大,系统响应速度越快,系统调节精度越高,但...
  • DES加密算法 DES加密算法即为数据加密标准,是一种使用密钥加密算法,1977年被美 国联邦政府国家标准局确定为联邦...DES密钥空间仅仅只有256次方,很容易被暴力破解; 步骤解读 1.将明文与密文用二进制表
  • 针对在不平衡分布数据中执行主动学习,其分类面容易形成偏倚,从而导致主动学习失效这一问题,拟采用采样技术作为学习过程平衡控制策略,在调查了几种已有采样算法的基础上,提出了一种边界过采样算法,并将其与...
  • 为了克服教与优化算法在求解高维函数问题时,容易早熟,收敛速度慢,解精度低弱点,提出一种引入竞争机制双种群教与优化算法。在该算法中设置两个教师,并基于帝国竞争优化机制将种群初始化成为两个学生种群...
  • 今天来学习归并算法的一个应用,求数组中逆序对数。 首先我们需要知道逆序对是什么东西:在一个数组中,有两个元素,索引小元素比索引大元素大,那这两个元素就构成一个逆序对。而一个数组中所有逆序对个数...
  • 一些理论算法的学习资源推荐

    千次阅读 2016-09-19 10:14:20
    学习一些经典的算法和理论毫无疑问是非常重要的,但又往往容易被忽视。其学习过程本就比较艰难,把所整理成文章更是一件费心费力的事儿。这里记录一些自己在学习过程中遇到的好资源。光流算法文章:《光流Optical ...
  • 欢迎关注”生信修炼手册”!KNN是一种分类算法,其全称为k-nearest neighbors, 所以也叫作K近邻算法。该算法是一种监督学习的算法,具体可以分为以下几个步骤1. 第一步,载...
  • 遗传学算法

    千次阅读 2016-08-20 20:45:18
    以一种比较偷懒的方式记录一下最近补学的几个算法,这几个算法之前都是只闻其名不知其义。看完这几个后这一阵的算法补习也告一段落,赶紧去把Introduction to IR啃完,在下一步啃NLP,再下一步啃Deep Learning。中间...
  • 学习排序算法简介

    千次阅读 2014-12-24 09:35:27
    而机器学习方法很容易融合多种特征,而且有成熟深厚理论基础,参数也是通过迭代计算出来,有一套成熟理论来解决稀疏、过拟合等问题。 LTR方法大致可以分成三类: 1) Pointwise 单文档方法 2) Pairwise ...
  • 对于解密算法的学习

    2018-06-15 17:07:59
    是计算机广泛使用杂凑算法之一(又译摘要算法、哈希算法),主流编程语言普遍已有MD5实现。将数据(如汉字)运算为另一固定长度值,是杂凑算法的基础原理,MD5前身有MD2、MD3和MD4。 MD5算法具有以下特点: 1...
  • 我们在控制移动机器人时,比较核心和基础问题是机构运动建模,一般常规可看到AGV都是差速轮机构,此种机构控制较为简单,运动学算法也很容易。但是此种结构AGV不适合在重载场合,抗打滑性能也较为不...
  • 贪心算法相对容易实现,但是很难给出一个确切证明,即贪心算法是合理,是问题最优解之一。贪心算法的证明通常涉及到两个步骤: 贪心选择性 最优子结构 贪心选择性指是,每次通过贪心选择得到了一个最优...
  • 递归算法的学习

    2018-07-19 14:36:00
    此外,有一类问题,其本身没有明显递归结构,但用递归程序求解比其他方法更容易编写程序,如八皇后问题、汉诺塔问题等。  正因为递归程序普遍性,我们应该学会使用递归来求解问题。直接递归程序与间接递归中都...
  • [计算机图形经典算法] 多边形扫描转换

    千次阅读 多人点赞 2018-01-27 10:44:52
    刚学习了计算机图形这门课程,为奠定根基的算法所倾倒,特此记录一二。 计算机图形中的一个重要问题是在一个区域的内部填上不同的色彩或灰度。这里的区域分为两类,一类是多边形;另一类是以像素点集合表示的...
  • 易于使用容易理解文档快速获取算法的源代码随时获取时间复杂度 安装 仅需在终端中执行以下命令: pip3 install pygorithm *如果你使用是Python 2.7,请使用pip来安装。如果存在用户权限限制,你可能需要...
  • 操作系统:下面是我在学习操作系统中用C语言编写一些操作系统常用算法,我对它们进行了整理一步一步敲完这些算法使你更容易理解操作系统原理

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,966
精华内容 1,986
关键字:

容易学的算法