算法

Raft算法

Roy

相比与Paxos算法,Raft更容易理解。首先推荐个动画视频 (注意这个动画真的基于raft算法,所以每次选举出的节点都是不同的,我观看某些章节时候甚至出现过3次选举过程),然后是raft论文中文版raft主页,基本结合这3个网站就能理解raft了。

在Raft算法中,有3种角色:

  • Leader
  • Follower
  • Candidate

大体分为2个过程:

  1. 选举(Leader Election)
  2. 日志同步(Log Replication)

BasicPaxos算法

Roy

CPA理论

分布式系统中有个经典的CAP理论,就是说任何分布式系统最多满足一致性(Consistency),可用性(Availability),分区容错性(Partition Tolerance)这三者中的两个。

既然是分布式,必然将节点部署到不同的网络中,而这则会引起一致性问题。想解决一致性,就需要保证每次操作所有节点都成功执行,而这又会降低可用性。既然分区已经是事实,所以工程上应该尽量在保证一致性的前提下提高可用性。

而一致性又可以分为:

  • 强一致性:上次写什么,下次就一定能读到什么,这需要牺牲可用性。
  • 弱一致性:并不保证更新后所有线程都能读到最新值,需要一段时间进行同步。
  • 最终一致性:弱一致性的一种特例。

朴素贝叶斯

Roy

朴素贝叶斯是贝叶斯决策理论的一部分,贝叶斯概率引入先验知识和逻辑推理来处理不确定命题。又可以称为“条件概率”(Conditional probability),与之相对的则是“频数概率”(frequency probability)。

决策树

Roy

决策树是机器学习中一种简单明了的分类算法,用程序语言描述就是if...elif...else...,关键问题则是如何选择合适的特征对数据集进行切割,常见算法有: ID3、C4.5、CART等。

今天主要记录一下ID3这个算法,想使用这个算法首先要了解信息增益,想了解信息增益则要先明白什么是"熵"。熵描述了一个系统的混乱复杂程度,有一个理论叫做"熵增加",含义就是一个没有外力干涉的系统混乱程度总是增加的,比如一个房间如果没人打扫的话只会越来越混乱,而不会自己变得整洁。