欠拟合和过拟合

欠拟合

高偏差：对于样本集，没有很好的拟合训练数据。

过拟合

高方差：如果拟合训练数据过于完美，代价函数J≈0，但是不能很好的预测新的样本，不具备泛化能力。

解决方法：

• 减少特征的数量，但也同时丢失了关于问题的一些信息：

  • 人工的选择保留一些合适的特征
  • 模型选择算法

• 正则化：

  • 保留所有的特征，减少参数θ的数量级或者大小

Logistic回归实际上是一种分类算法。

假设函数

因为应用于分类问题，想要使得假设函数的值域为[0, 1]。故在线性回归假设函数的基础上，外层再套一个logistic或者叫做sigmoid函数，作为logistic回归的假设函数：

sigmoid函数图型如下：

在logistic回归中，假设函数的输出h(x)的含义是当输入x时，预测y=1的可能性。

线性回归

线性回归是一种监督学习算法，我们需要对数据进行预测，以得到一条线性的假设函数h。其中定义函数J为代价函数（Cost Function，也叫代价函数），用于表示对于预测的参数，每一个样本输入值x和它所对应的结果值y之间的差距。我们的目标就是，尽量的优化参数，使得代价函数最小。

定义

一个经典的机器学习定义如下：

A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

比如对于一个垃圾邮件分类程序而言：

• T，识别一封电子邮件是否是垃圾邮件
• E，用户对于邮件的标记是否是垃圾邮件
• P，对垃圾邮件识别的准确率

机器学习算法分类

对于机器学习算法，可以分为：监督学习和非监督学习。简而言之，监督学习就是人为的去教计算机学习一些东西。非监督学习，就是让计算机自己去学习。

监督学习

在监督学习中，对于数据集中的每个样本都带有“正确答案”

• 回归（regression）：预测连续值的输出。
• 分类（classification）：预测离散值的输出。

一个监督学习的基本框架如下：将训练集输入到学习算法中，接着学习算法输出一个假设函数h，假设函数h的作用就是表达x与预测值y的映射关系（在图中，x为房屋的面积，y为预测出可以卖出的价格），简而言之就是进行预测的函数：

无监督学习

在无监督学习中，数据集中的每个样本都没有“正确答案”，要求算法找出数据的类型结构。

• 聚类（cluster）：在无标签的数据集中，其中的样本会天然的呈现出分类的结构，交给无监督学习算法就是去将这些样本自动的划分为不同的类别。

最接近的三数之和

最接近的三数之和

解题思路

首先对数组进行排序，接着遍历数组，用两个指针分别记录nums[i]之后的左右边界，令sum = nums[i]+nums[left]+nums[right]：

• 若sum<target，说明三数之和过小，left++
• 若sum>target，说明三数之和过大，right--

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func threeSumClosest(nums []int, target int) int {
    // 排序
    sort.Ints(nums)
    // 记录最接近的三叔之和
    closestSum := nums[0]+nums[1]+nums[len(nums)-1]  
    // 遍历数组
    for i := 0; i < len(nums); i++ {
        // 左右指针
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i]+nums[left]+nums[right]   // 三数之和
            if sum == target {
                return target
            } else {
                if abs(target-sum) < abs(target-closestSum) {
                    closestSum = sum
                }
                if sum < target {
                    // 左指针向右移动
                    left++
                } else {
                    // 右指针向左移动
                    right--
                }
            }
        }
    }

    return closestSum
}

func abs(n int) int {
    if n > 0 {
        return n
    }
    return -n
}

二叉树最大宽度

二叉树最大宽度

解题思路

层序遍历，在队列中同时记录每一个节点的位置信息，position值：

• 如果左子树入队，那么左子树的位置信息为2 * position
• 如果右子树入队，那么右子树的位置信息为2 * position + 1

盛最多水的容器

盛最多水的容器

解题思路

1. 暴力解法，双层for循环

2. 双指针法，设立两个指针left和right分别指向左右边界，水槽板高度分别为height[left]和height[right]。那么可容纳水的高度由两个板中的短板决定。在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度-1：

   • 若向内移动短板，水槽的短板可能变大，因此下个水槽的面积可能增大
   • 若向内移动长，水槽的短板不变或者变小，因此下个水槽的面积一定减小

   因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

另一个树的子树

另一个树的子树

解题思路

在root的每一个节点上，判断以这个节点为根的树是否与subRoot相同。

判断两个树是否相等的三个条件是与的关系，即：

1. 当前两个树的根节点值相等；
2. 并且，root1的左子树和root2的左子树相等；
3. 并且，root1的右子树和root2的右子树相等。

而判断 一棵树是否是另一棵树的子树的三个条件是或的关系，即：

1. 当前两棵树相等；
2. 或者，subRoot在root的左子树中；
3. 或者，subRoot在root的右子树中。

问题优化

如何防止消息丢失

• 生产者：把ACK设置为1（等待leader的ACK）或者ALL（leader及其follower同步之后返回ACK）

• 消费者：把自动提交设置为手动提交offset

如何防止消息重复消费

在防止消息丢失的⽅案中，如果生产者发送完消息后，因为网络抖动，没有收到ACK，但实际上broker已经收到了。此时生产者会进行重试，于是broker就会收到多条相同的消息，从而造成消费者的重复消费。

或者消费者已经消费了数据，但是offset没来得及提交，会导致重复消费。

解决方案，消费者保证幂等性：

• 在数据库中使用业务id作为唯一约束

顺序消费

• 生产者：在发送时将ACK不能设置0，关闭重试，使用同步发送，等到发送成功再发送下⼀条。确保消息是顺序发送的。
• 消费者：消息是发送到⼀个分区中，只能有⼀个消费组的消费者来接收消息。

在Kafka中若要实现顺序消费，会牺牲性能，但是Rocket MQ有专门的功能实现顺序消费。

解决消息积压问题

• 在⼀个消费者中启动多个线程，让多个线程同时消费。
• 可以创建多个消费组，创建多个消费者，部署在不同的服务器上。
• 创建⼀个消费者，该消费者另建一个主题，分配多个分区和多个消费者。消费者收到消息后，立即发往这个新的topic，此时，新的主题的多个分区的多个消费者就开始⼀起消费了。

延迟队列

订单创建后，超过30分钟没有⽀付，则需要取消订单，这种场景可以通过延时队列来实现。

具体方案

• Kafka中创建多个主题，每个topic表示延时的间隔，如topic_30m表示延时30分钟的延时队列
• 消费者消费该主题的消息
• 消费者消费消息时判断消息的创建时间和当前时间是否超过30分钟（前提是订单没支付）：
  • 若超过了30分钟，去数据库中修改订单状态为已取消
  • 若没有超过30分钟，记录当前消息的offset，并不再继续消费之后的消息。等待X分钟后，再次向kafka拉取该offset及之后的消息，继续进行判断，以此反复。

Controller

什么是Controller

在Kafka中，需要有一个管理者，称为Controller，它在ZooKeeper的帮助下管理和协调整个Kafka集群。Controller本身也是一台Broker节点，只不过需要负责一些额外的工作（追踪集群中的其他Broker，并在合适的时候处理新加入的和失败的Broker节点、Rebalance分区、分配新的leader分区等）。

Kafka集群中始终只有一个Controller Broker。

如何被选举出来

Broker 在启动时，会尝试去 ZooKeeper 中创建/controller的临时序号节点，获得的序号最小的那个broker将会作为集群中的controller。

Controller作用

Controller的作用：

• 当集群中有broker新增或减少，controller会同步信息给其他broker
• 当集群中有分区新增或减少，controller会同步信息给其他broker

处理下线的Broker

Controller可以依据ZooKeeper的Watch机制，来监听Broker的变化。

每个 Broker 启动后，会在zookeeper的/Brokers/ids下创建临时znode。当Broker宕机或主动关闭后，该Broker与ZooKeeper的会话结束，这个znode会自动删除。

ZooKeeper的Watch机制会将节点的变化情况推送给Controller，这样Controller就知道某个Broker宕机了，可以采取行动决定哪些Broker上的分区成为leader分区（选择isr列表中最靠前的作为新的leader）。然后，它会通知每个相关的Broker。

处理新加入到集群中的Broker

大部分情况下，Broker的失败很短暂，这意味着Broker通常会在短时间内恢复。所以当节点离开群集时，与其相关联的元数据并不会被立即删除。

当Controller注意到Broker已加入集群时，它将使用Broker ID来检查该Broker上是否存在分区，如果存在，则Controller通知新加入的Broker和现有的Broker，新的Broker上面的follower分区再次开始复制现有leader分区的消息。为了保证负载均衡，Controller会将新加入的Broker上的follower分区选举为leader分区。

脑裂问题

如果controller Broker 挂掉了，Kafka集群必须找到可以替代的controller，集群将不能正常运转。这里面存在一个问题，很难确定Broker是挂掉了，还是仅仅只是短暂性的故障。但是，集群为了正常运转，必须选出新的controller。如果之前被取代的controller又正常了，他并不知道自己已经被取代了，那么此时集群中会出现两台controller。

比如，某个controller由于GC而被认为已经挂掉，并选择了一个新的controller。在GC的情况下，在最初的controller眼中，并没有改变任何东西，该Broker甚至不知道它已经暂停了。因此，它将继续充当当前controller。现在，集群中出现了两个controller，它们可能一起发出具有冲突的命令，就会出现脑裂的现象。

epoch number

Kafka种，使用使用epoch number（纪元编号）来避免脑裂问题。epoch number只是单调递增的数字，第一次选出Controller时，epoch number值为1，如果再次选出新的Controller，则epoch number将为2，依次单调递增。

每个新选出的controller通过Zookeeper获得获得一个全新的、数值更大的epoch number 。其他Broker 在知道当前epoch number 后，如果收到由controller发出的包含较小epoch number的消息，就会忽略它们。

HW机制

LEO（Log End Offset）是某个副本最后消息的消息位置。

HW（High Watermark）高水位，是指已完成同步的位置。消费者最多只能消费到HW所在的位置。

另外，每一个leader和follower各⾃负责更新自己的HW的状态。对于leader新写⼊的消息，consumer不能立刻消费，leader会等待该消息被所有ISR中的副本同步后更新HW，此时消息才能被consumer消费。这样就保证了如果leader所在的broker失效，该消息仍然可以从新选举的leader中获取。