左耳听风 ARTS 打卡第十六周

正文

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Algorithm

3. Longest Substring Without Repeating Characters

题目：无重复字符的最长子串

难度：Medium

题意：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1：

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

示例 2：

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

示例 3：

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法：

构造一个起始计数点 start，需要返回的结果 max
构造一个字典 dict，对字符串中的每一个字符进行读取：
	如果这个字符在字典中，且它上一次出现在字符串中的位置比 start 要大[注1]，那么：
		将这个字符出现的位置置为 start（重新开始计数），并且将字典中这个字符的值修改为当前位置
	如果这个字符不在字典中，那么：
		将这个字符作为键，字符的位置作为值，加入到字典中去
		如果当前位置减去起始位置比 max 要大，即说明我们目前读取过的字符数是最大的，那么修改 max 的值为当点位置减去 start

注意，如果字符串为空，那么返回值需要是 1，所以应该设置起始点为 -1

代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        start = -1
        max = 0
        d = {}

        for i in range(len(s)):
            if s[i] in d and d[s[i]] > start:
                start = d[s[i]]
                d[s[i]] = i
            else:
                d[s[i]] = i
                if i - start > max:
                    max = i - start

        return max

注1：为什么这里一定要说明「读取到的字符上一次出现的位置比 start 要大」呢？

如果条件中没有 d[s[i]] > start，那么就不能保证计算的子字符串是从上一个子字符串之后重新开始计算的。

第一次做 Medium 难度的题目，感觉还是很有挑战的，这里参考了 B站up主 Michelle 小梦想家 的这个视频。

时间复杂度为 O(n)，空间复杂度也是 O(n)。

Review

Why IoT Needs Machine Learning to Thrive

本周阅读了 IoT for All 上的一篇文章，Why IoT Needs Machine Learning to Thrive，比较短小，但值得一读，尤其是物联网面临的几个关键挑战和机器学习能够应用的几个因素，非常有针对性。

文章从以下几个方面讲述了机器学习如何为 IoT 行业赋能：

机器学习的能力
物联网行业面临的关键挑战：
- 安全与隐私
- 操作的准确性
- 大数据的 3V：volume（数据的数量）、variety（数据的种类）、velocity（处理数据的速度）
- 互联性
机器学习能够在物联网领域应用的两个因素：
- 数据分析的自动化
- 机器学习的预测能力
如何起作用
从大数据到智能数据

Tips

vim 中的快速移动

大家知道，vim 的 normal 模式使用了 hjkl 这四个键来进行上下左右的移动，除了这四个键，Vim 其实还有很多其他的移动方式：

在单词之间进行移动：

w/W 移动到下一个 word/WORD 的开头，e/E 移动到下一个 word/WORD 的结尾
b/B 移动到上一个 word/WORD 的开头，你可以将它理解为 backward
word 是指以非空白符分割的单词，WORD 指以空白符分割的单词

行间搜索移动：

使用 f{char} 移动到该行第一个 char 字符上（f 可以理解为 find），使用 t{char} 移动到 char 的前一个字符上（t 可以理解为 till）
如有多个 char，那么可以使用分号 ; 跳转到下一个 char，逗号 , 跳转到上一个 char
如果光标在行尾，那么可以使用 F/T 来进行反向的查找，这时分号和逗号的作用也相反

水平移动：

0 移动到行首，^ 移动到第一个非空白字符（如果这时候本就在行首的话，直接使用 w 即可）
$ 移动到行尾，g_ 移动到行尾最后一个非空白字符

垂直移动：

使用括号 () 在句子间移动，使用花括号 {} 在段落间移动

页面移动：

gg 移动到文件开头，G 移动到文件结尾，使用 CTRL-o 回到上一次的位置
H/M/L 移动到开头（Head）、中间（Middle）和底部（Lower）
CRTL-u/f 翻页，zz 把当前行放到屏幕中间

以上这些命令，看不懂记不住的话，多用用多练习几次，这里附上一份 vim 命令速查表。

机器学习中的朴素贝叶斯分类

这篇内容是我学习的学习笔记，稍作整理，分享给大家。

贝叶斯定理

朴素贝叶斯算法起源于上世纪四五十年代，它基于的贝叶斯定理如下公式所示：

$$P(A|B) = \frac{P(B|A)*P(A)}{P(B)}$$

我们先来看一个例子：

一家生产某种产品的工厂有两台机床，也会生产出正品和次品，一共生产了 1000 个产品

机器一：30 个/小时，机器二：20 个/小时
所有的产品中有 1% 的次品
在所有次品中，50% 出自机器一，50% 出自机器二
问题：求生二号机床生产的产品是次品的概率？

解答：本题使用贝叶斯公式就能很好地解决问题

P(Mach 1) = 30/50 = 0.6
P(Mach 2) = 20/50 = 0.4
P(Defect) = 1%
P(Mach 1 | Defect) = 50%
P(Mach 2 | Defect) = 50%
P(Defect | Mach 2) = ?

$$P(Def | M2) = \frac{P(M2 | Def)*P(Def)}{P(M2)} = \frac{0.5 * 0.01}{0.4} = 0.0125$$

另一个角度（方法二）：

1000 个产品
400 个来自机器二
1000 个产品中 1% 的有问题 = 10 个
10 个中有 50% 来自机器二 = 5 个
机器二生产出来的产品是次品的概率 = 5/400 = 0.0125

其实就只是在贝叶斯公式的上下各乘了 1000，但胜在思路清晰：

$$P(Def|M2)=\frac{P(M2|Def)*P(Def)*1000}{P(M2)*1000}=1.25%$$

问题：为什么有方法二还要使用贝叶斯公式呢？

因为在实际生产过程中，概率是很方便知晓的，而总数中的个数是不太方便知道的
计算 P(Defect | Mach 1)

$$P(Def|M1) = \frac{P(M1|Def)P(Def)}{P(M1)} = \frac{0.50.01}{0.6} = 0.0083$$

朴素贝叶斯分类器 - 原理

首先我们看一下贝叶斯公式：

$$P(A|B) = \frac{P(B|A)*P(A)}{P(B)}$$

P(A|B) 称为条件概率，或者后验概率，而 P(B|A) 和 P(B) 并不完全是概率，因为它们表示的是特征，所以这两个概率又被称为“似然 Likelihood”。

我们再来看一个例子：

这个例子的问题是：根据年龄和薪水，判断一个新的员工是走路上班还是开车上班

步骤一

$$P(Walks|X) = \frac{P(X|Walks)*P(Walks)}{P(X)}$$
1. 求 P(Walks)，抽一个人他是走路上班的概率，这个概率被称为“先验概率 Prior Probability”
2. 求 P(X)，随机在数据空间中抽一个点，这个点和我们新用户之间的相似程度，即“似然 Likelihood”，似然是对特征的概率，或者叫对特征的可能性
3. 求 P(X|Walks)，已知一个用户是步行上班的，那么它的特征坐落在新用户特征周围的概率，即“边际似然 Marginal Likelihood”
4. 求 P(Walks|X)，后验概率 Posterior Probability
步骤二

$$P(Drives|X) = \frac{P(X|Drives)*P(Drives)}{P(X)}$$
1. P(Drives)
2. P(X)
3. P(X|Drives)
4. P(Drives|X)
步骤三

$$P(Walks|X)\ v.s.\ P(Drives|X)$$

已知一个新用户的特征，分别求出他步行和开车上班的概率，这两个概率哪个比较大，新用户就会被分到哪一组

我们使用这种思路来进行试验：

步骤一，计算 P(Walks|X)，即「已知这个人的特征值落在 X 中（即下图中圈里），求他步行上班的概率」
1. P(Walks)
  
  这个人走路上班的概率：
  
  $$P(Walks) = \frac{Number\ of\ Walkers}{Total\ Observations} = \frac{10}{30} = \frac{1}{3}$$
2. P(X)
  
  在新数据点附近画一个小圈（圈的半径是一个参数，在算法中可调），看看圈中的点（不包含新数据点）在整个数据空间中所占的比例：
  
  $$P(X) = \frac{Number\ of\ Similar\ Observations}{Total\ Observations} = \frac{4}{30} = \frac{2}{15}$$
3. P(X|Walks)
  
  已知这个人步行上班，求他的特征值落在图中圈里的概率：
  
  $$P(X|Walks) = \frac{Number\ of\ Similar\ Observations\ Among\ those\ who\ walk}{Total\ number\ of\ Walkers}\ = \frac{3}{10}$$
4. P(Walks|X)
  
  $$P(Walks|X) = \frac{\frac{3}{10}*\frac{10}{30}}{\frac{4}{30}} = 0.75$$
步骤二，计算 P(Drives|X) ，即「已知这个人的特征值落在 X 中（即下图中圈里），求他开车上班的概率」
1. P(Drives)
  
  $$P(Drives) = \frac{20}{30}$$
2. P(X) = 4/30
3. P(X|Drives)
  
  $$P(X|Drives) = \frac{1}{20}$$
4. P(Drives|X)
  
  $$P(X|Drives) = \frac{\frac{1}{20}*\frac{20}{30}}{\frac{4}{30}} = 0.25$$
步骤三，P(Walks|X) v.s. P(Drives|X)

$$P(Walks|X)\ v.s.\ P(Drives|X)$$

$$0.75\gt 0.25\rightleftharpoons P(Walks|X)\gt P(Drives|X)$$

因为 P(Walks|X) > P(Drives|X)，所以这个新数据点被分到了走路上班这个类

朴素贝叶斯的几个问题

为什么称为“朴素 Naïve”？在应用朴素贝叶斯之前，我们做了一个假设，即数据的所有特征都是相互独立的，但是在例子中，其实薪水和年龄之间并不是独立的（年龄越大经验越多薪水也就越来越高），但是在这个例子中这两个变量的相关性不是特别高，如果相关性很高的话，那么在计算圈中点的个数的时候，会有一点问题
似然函数 P(X) 的消去

似然的计算

$$P(X) = \frac{Number\ of\ Similar\ Observations}{Total\ Observations}$$

大于两类的情况，如何应用朴素贝叶斯？
- 假如有另外一群人坐公交去上班
- 同样对三个分类计算后验概率，然后把待分类目标分到最大的后验概率那一组去

Contents: