K最近邻算法(K-nearest neighbours,KNN)
特征提取
假如我们要做一个电影推荐系统，那么我们可以首先计算用户喜好的相似程度，然后某一用户喜欢的电影推荐给和他喜好相似的用户。
那么，如何去计算用户的喜好相似度呢？
一种粗略的做法比如，在用户注册时，可以让他选择对不同类型电影的喜欢程度进行评星，此时我们可以获取一些数据，比如：
| 小A | 小B | 小C | |
|---|---|---|---|
| 喜剧片 | 2 | 1 | 3 |
| 剧情片 | 3 | 4 | 3 |
| 动作片 | 5 | 1 | 2 |
此时使用毕达哥拉斯公式可以计算用户之间的距离，距离越近，用户的喜好越相似，当然这是十分粗略的。当你给更多电影评分，系统拥有了更多关于你的数据，那么推荐也会变得更加精准。
回归
假如你要预测小A将会给甲电影的评分，那么可以先找到和他特征最相似的用户，再求出他们给这部电影打了多少分的平均值，这就是回归。
余弦相似度
之前计算用户相似程度的公式是距离公式，但其实余弦相似度在实际工作中更多地被使用，余弦相似度不计算用户的距离，而是比较他们的角度，更多需要自己去了解。
机器学习简介
KNN算法很有用，堪称进入机器学习的领路人。
OCR
我们常用的OCR是怎么实现的呢？可以使用KNN：浏览大量的文字图像，将文字图像的特征提取出来；遇到新图像时，找到与它最近的邻居是谁。
垃圾邮件过滤器
垃圾邮件过滤器使用一种简单的算法——朴素贝叶斯分类器
预测股票市场
股票市场很难提取特征，所以很难预测，这是几乎不可能完成的任务。
写在最后
二叉查找树
在大量数据中查找某一元素时，二分查找是一个很好的解决办法，但是注意二分法有一根前提：元素是有序的。假如我们在用户表里插入一名新用户，若查找用户使用的是二分法，那么则需要提前将用户表排序，如果这张用户表非常长，那么显然对效率影响很大。
此时可以使用二叉查找树，这个树中的每个节点，左节点的值都比它小，右节点的值都比它大。这几乎与二分查找法一样，不过二分法的最高复杂度为O(logn),而二叉查找树的平均复杂度为O(logn),最高复杂度为O(n)。那么是否就证明二叉查找树比二分法的效率更低呢？我们需要再看看插入和删除的复杂度。
| 数组 | 二叉查找树 | |
|---|---|---|
| 查找 | O(logn) | O(logn) |
| 插入 | O(n) | O(logn) |
| 删除 | O(n) | O(logn) |
平衡的二叉树的查找复杂度的平均时间为O(logn)，但是不平衡的二叉树对性能有一定影响。
B树
后续
红黑树
后续
堆
后续
伸展树
后续
傅里叶变换
傅里叶变换算法是优雅且运用广泛的算法之一，有一个有关于它的精妙的比喻：给它一杯冰沙，它能告诉你其中包含哪些成分。假如你给它一首歌，它能将其中包含哪些频率分析出来。
傅里叶变换非常适合处理各种信号。
并行算法
摩尔定律在我们这个时代已经渐渐失效了，现在更多地是使用多个处理器来提高计算的速度，所以为了提高算法的速度，需要让他们在多个处理器中并行。
比如快速排序在单核中运行的复杂度为O(nlogn),而在多核并行计算中，可以达到O(n)。
但是并行算法的设计难度比较高，速度的提升也不可能是线性的，因为：
- 并行性管理需要开销
- 负载均衡需要开销
MapReduce
分布式算法越来越流行，当需要几十上百上千个处理器时，可以在多台计算机上运行。MapReduce是一种流行的分布式算法。
为什么需要使用分布式算法？当数据量巨大时：
- 传统方式无法处理
- 传统方式非常耗时
分布式算法能在短时间内处理海量数据。ReduceMap基于两个理念：映射函数和并归函数。
布隆过滤器和HyperLogLog
给定一个元素，需要快速判断它是否存在于某个集合中，这时可以使用散列表，速度非常快。但是假如有数以亿计十亿计的元素呢？这个散列表将会非常长，将会占用大量的储存空间。
此时布隆过滤器提供了一个解决方案。布隆过滤器是一种概率性数据结构。他提供的答案可能不对，但很可能是正确的。有以下两种可能：
- 假如布隆过滤器说“该元素已存在”，那么可能不存在
- 假如布隆过滤器说“该元素不存在”，那么肯定不存在
假如Google要记录用户今日执行的不同搜索的数量，假如将他们记录在日志中，则需要大量的空间。此时可以使用HyperLogLog，这和布隆过滤器差不多，它不能给出完全准确的答案，但是八九不离十，占用空间也小得多。
SHA
SHA-安全散列算法
可以使用SHA来计算散列值来判断两个文件是否完全相同。
SHA是单向的，SHA是一系列算法，但是SHA-0,SHA-1被发现存在一些缺陷，可以使用SHA-3,SHA-4或bcrypt。
局部敏感的散列算法
比如Simhash算法，它十分有用。比如：
- Google使用Simhash来判断网页是否已经被搜集过
- 论文查重
Diffie-Hellman 密钥交换
Diffie-Hellman主要用于处理一个古老的问题：如何对消息加密？
Diffie-Hellman使用公钥和私钥。公钥是公开的，可以让任何人获得，私钥是私密的，需要好好保管。你的朋友通过公钥来加密信息发送给你，你获得后用自己的私钥解密来阅读。
这解决了两个关键问题：
- 双方不需要协商使用的加密算法
- 难以破解
如今Diffie-Hellman及其替代者RSA被广泛应用。
扫一扫，关注公众号
网友评论