# 数据基础算法

> 本文档会介绍一些数据分析思维中的基本的算法思路。如果说[数据基础思维](数据基础思维.md)给出的是一些结论的话，
> 那么本文则是介绍如何得到这些结论。

![基础算法思想](img/data-thinking/基础算法思想.jpg)

官方把算法定义为一个计算过程，这个过程输入某一个值或一个值的集合，终会产生一个值和一个值的集合作输出，这就是一个算法。
官方的说法比较抽象，简单来说，你可以把算法当成一个具有科学依据的算命箱子，你给这个箱子输入你的面相、体重生辰八字，
最终它会根据你的需求给你算出一个很有可能的结果，比如最近你买比特币会发大财，生的孩子是男孩一类的。
这个输入输出的箱子就是一个算法，箱子里面装的我们就叫做算法模型。

我们在[数据基础思维](数据基础思维.md)里介绍的[拉普拉斯分布、正态分布](数据基础思维.md#信息越透明，越塔尖的个体越吸附资源——拉普拉斯分布)，
就是算法模型的一种。

本文会从大类上介绍几种**基础算法思想**：

- **[聚类算法](#聚类)** —— 物以类聚，让复杂事物简单化

- **[分类算法](#分类)** —— 分而治之，不断进化

- **[蒙特卡洛算法](#蒙特卡洛算法)** —— 有限时间内需求更优解

- **[拉斯维加斯算法](#拉斯维加斯算法)** —— 穷举寻找最优解

## 聚类

> 物以类聚，让复杂事物简单化

“物以类聚”这个成语想必你肯定不陌生，我们会自然地把很多类似的事物放到一起，给出一个统一的定义。因为我们的大脑空间有限，无法接收太多零碎的信息。
对于数据来说也是如此，如果大量的数据没有一个很好的算法来进行整理，那么这些数据可能我们就无法理解。
如何将大数据分门别类聚集起来让人理解，就是本节要给你讲的算法——**聚类**。

**聚类算法输入就是一群杂乱无章的数据，输出是若干个小组，并且这些小组里面会把数据都分门别类。组内的对象相互之间是相似的（内聚），
而不同组中的对象是不同的（分离）。组内的相似性越大，组间差别越大，聚类就越好。**

### 适用场景

数据、事情等细碎杂乱，毫无规则的情况，尝试对数据进行分析处理。

### 问题和场景

不同的花之间有一些比较相近的特性：花都有花瓣也有花蕊，颜色也都比较鲜艳。我们把这种现象叫做**内聚**。
而花和叶子相比，叶子在大多情况下形状不会特别复杂，并且大多是绿色，所以花和叶子之间的差异很大。我们把这个特性叫做**分离**。

**聚类**就是通过一些算法，把这些事物自动全都聚集起来，让这些聚好的类别（花类和叶子类）达到内聚和分离的特性。你可以从下面的图里更直观地看到，
一个好的聚类算法算出来以后，可以把相近的东西全都聚到一起，并且不相近的全都能区分开。

![聚类](img/data-thinking/聚类.png)

常见聚类算法有 `K-Means`、 `KNN`、`DBSCAN`、`EM` 等等，所有的这些聚类算法其实都可以简化成三种问题：

- 1. 选大哥，找聚类中心的问题；

- 2. 找小弟，解决距离表示的问题；

- 3. 帮派会议，聚类收敛方法问题。

这里要注意的是，使用聚类算法的时候要先把一些异常点尽量剔除掉，或者单独把它们单独聚成一类。否则有一些很异常的数据就会影响我们聚类算法最终的准确性。

具体的聚类算法案例介绍，可[点击查看](数据基础算法——聚类.md)

### 拓展
不知道你会不会有这样一种感觉：总是每天很忙，全都深入在不同的生活、业务细节里，但一天忙下来，却不知道自己到底忙了些什么。

你不妨试试用类似聚类算法的思路， 把你觉得纷纷扰扰一些小事统一归到一个篮子里去，用一整块的时间或者类似通用的方法去解决它们，说不定会有奇效。

**因为多用聚类算法的方式去思考，可以把你的思维锻炼得更加结构化，助你更快理清琐碎的生活。**

## 分类

> 分而治之，不断进化

这么一个段子：你去倒垃圾，一个阿姨就会在那里看着你，看到你就会问“你是什么垃圾？”你如果把垃圾分类做错了，她会告诉你榴莲壳属于干垃圾，
瓜子壳属于湿垃圾。下次如果你去倒垃圾还不对，她还会纠正你，直到你最后学会为止。这个例子就和本节的主角**分类算法**脱不开干系。

和[聚类算法](#聚类) 不同，分类算法是有训练数据集的，也就是我们在一开始就已知有一系列正确的数据和正确的分类结果。分类算法会不停告诉你这个分类是哪种，
直到你学会，最后再让你自己单独去进行区分。所以分类也叫做有监督学习，也就是得有人看着你做。

### 适用场景

希望利用已知的数据对未来趋势进行预测的场景。

### 问题和场景

比如现在你想知道有哪些客户可能会流失到竞争对手那里去。这个时候我们可以用叫“客户流失预警”的分类算法来解决这个问题，
也就是你的客户流失之前，算法会提前先给你一个预警。

具体是怎么做的呢？我们先是输入很多过去流失的客户信息，让这个算法学习大概哪些特征是流失客户会有的，这个分类器算法学会了分辨哪些客户会流失后，
你再来一个客户给它，算法就会告诉你这个人流失的概率有多大。这样你就可以有备无患，针对这些要流失的客户进行营销活动来挽留住他们。

具体聚类算法案例介绍，可[点击查看](数据基础算法——分类.md)

### 拓展

**分类算法的核心就是在于经验不断积累，不断迭代自己的规则，从而得到最好的答案。**

## 蒙特卡洛算法

> 每次计算都尽量尝试找【更好】的结果路径，但不保证是【最好】的结果路径。尝试次数越多，越有机会找到最优解。

蒙特卡洛算法和[拉斯维加斯算法](#拉斯维加斯算法)是一种算法思想，而不是具体的算法。
目标都是**"利用随机的方法来加速简化整体的算法过程，解决一些看上去我们没有办法通过正常算法解决的实际问题。"**

### 适用场景

在有限时间里，怎么样才能够获得比较好的分析答案。

### 问题和场景

找到一个有 500 个苹果的筐里，最大的苹果。正常来讲，我们每次从筐中拿一个苹果 A， 然后下一次再随机从筐中拿出另一个苹果 B， 
如果 B 比 A 大的话，就把 A 扔到另一个筐里，手里只拿着 B。这样如果我们拿了 500 次的话，最后留在手里的一定是最大的那个苹果。

但如果我们的时间和资源不够拿 500 次苹果呢？

我们就可以用蒙特卡洛算法，无论我们选择多少次，每次手里依然保留比较大的苹果，直到资源不够让我们截止的时候，留在我们手上的苹果也是我们力所能及接近最大的。
也就是说我们持续保留较好的答案，一直执行 N 次（N<500），最终拿到的一定近似正确解。N 越接近 500，我们的苹果越接近最大的那个。
其实蒙特卡洛方法的理论基础就是我们前面讲过的[大数定律](数据基础思维.md#随机样本越多越接近预期——大数定律)。
根据这个定律我们知道当随机事件发生的次数足够多时，发生的频率就会趋近于预期的概率。

具体蒙特卡洛算法的案例介绍，可[点击查看](数据基础算法——蒙特卡洛算法.md)

### 拓展

蒙特卡罗算法的基本思想是精益迭代，进行多次求解，最终让最后结果成为正确结果的可能性变高。

## 拉斯维加斯算法

> 每次计算都尝试找到【最好】的答案，但不保证这次计算就能找到【最好】的答案，尝试次数越多，越有机会找到最优解。

### 问题和场景

假如有一把锁，给我 100 把钥匙，其中只有 1 把钥匙可以开锁。于是我每次随机抽 1 把钥匙去试，打不开就再换 1 把。
我尝试的次数越多，打开锁的机会就越大。但在打开之前，那些错的钥匙都是没有用的。
这个挨个尝试换钥匙开锁的算法，就是拉斯维加斯算法。

具体拉斯维加斯算法的案例介绍，可[点击查看](数据基础算法——拉斯维加斯算法.md)

### 拓展

拉斯维加斯的算法是不断进行尝试，直到某次尝试结果让你自己满意，当然这个过程中也会一直产生你无法满意的随机值。

## 蒙特卡洛算法 VS 拉斯维加斯算法

![对比图](img/data-thinking/蒙特卡洛算法vs拉斯维加斯算法.png)

- 蒙特卡洛算法：相对正确，资源可控

- 拉斯维加斯算法：绝对正确，资源不可控

> 虽然蒙特卡洛算法和拉斯维加斯算法 是两个不同思路的算法，但他们有一个共同且重要的特性是："利用随机简化过程"。

## 总结

本文中分享了几种在数据分析中常用的算法思想，分别为：

- **[聚类算法](#聚类)** —— 物以类聚，让复杂事物简单化

- **[分类算法](#分类)** —— 分而治之，不断进化

- **[蒙特卡洛算法](#蒙特卡洛算法)** —— 有限时间内需求更优解

- **[拉斯维加斯算法](#拉斯维加斯算法)** —— 穷举寻找最优解

当拿到一堆杂乱的数据毫无头绪时，可以通过[聚类算法](#聚类)对数据进行聚类分组，从而让数据更具结构化，更易于处理；

当有确定的数据，希望进行规律总结，然后指导决策时，可以通过[分类]((#分类))不断迭代我们的规则，从而更好有更好的指导意义；

当在资源有限的情况下需要尽快找到解决方案时，可以考虑采用[蒙特卡洛算法](#蒙特卡洛算法)，迭代寻求更优解；

当资源有限但是需要最优解时，可以考虑采用[拉斯维加斯算法](#拉斯维加斯算法)，加速整个过程。

除了上述的算法外，还有我们在数学上比较熟悉的回归，以及马尔可夫链和协同过滤等，这些资料我在[推荐读物](#推荐读物)中给出了相关链接。

## 推荐读物

- [《数据分析思维课》13 | 趋势分析与回归：父母高，孩子一定高么？](https://time.geekbang.org/column/article/412094)

- [《数据分析思维课》16 | 关联规则：为什么啤酒和尿布一起卖？](https://time.geekbang.org/column/article/414442)

- [《数据分析思维课》18 | 马尔可夫链：你的未来，只取决于你当下做什么](https://time.geekbang.org/column/article/415893)

## 参考资料

- [《数据分析思维课》14 | 初识聚类算法：物以类聚，让复杂事物简单化](https://time.geekbang.org/column/article/412828)

- [《数据分析思维课》5 | 初识分类算法：分而治之，不断进化](https://time.geekbang.org/column/article/413734)

- [《数据分析思维课》17 | 蒙特卡洛与拉斯维加斯：有限时间内如何获得最优解？](https://time.geekbang.org/column/article/415120)