KNN分类算法
KNN算法，即K近邻（K Nearest Neighbour）算法，是一种基本的分类算法。其主要原理是：对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类数据的类别。
KNN算法是一种非常简单实用的分类算法，可用于各种分类的场景，比如新闻分类、商品分类等，甚至可用于简单的文字识别。对于新闻分类，可以提前对若干新闻进行人工标注，标好新闻类别，计算好特征向量。对于一篇未分类的新闻，计算其特征向量后，跟所有已标注新闻进行距离计算，然后进一步利用KNN算法进行自动分类。
数据的距离
KNN算法的关键是要比较需要分类的数据与样本数据之间的距离，这在机器学习中通常的做法是：提取数据的特征值，根据特征值组成一个n维实数向量空间（这个空间也被称作特征空间），然后计算向量之间的空间距离。空间之间的距离计算方法有很多种，常用的有欧氏距离、余弦距离等。
对于数据$x_{i}$和$x_{j}$，若其特征空间为n维实数向量空间$R^{n}$，即$x_{i}=(x_{i1},x_{i2},…,x_{in})$，$x_{j}=(x_{j1},x_{j2},…,x_{jn})$，则其欧氏距离计算公式为
$$d(x_{i},x_{j})=\sqrt{\sum_{k=1}^{n}{(x_{ik}-x_{jk})^2}}$$
这个欧式距离公式其实我们在初中的时候就学过，平面几何和立体几何里两个点之间的距离，也是用这个公式计算出来的，只是平面几何（二维几何）里的n=2，立体几何（三维几何）里的n=3，而机器学习需要面对的每个数据都可能有n维的维度，即每个数据有n个特征值。但是不管特征值n是多少，两个数据之间的空间距离的计算公式还是这个欧氏计算公式。大多数机器学习算法都需要计算数据之间的距离，因此掌握数据的距离计算公式是掌握机器学习算法的基础。
欧氏距离是最常用的数据计算公式，但是在文本数据以及用户评价数据的机器学习中，更常用的距离计算方法是余弦相似度。
$$cos(\theta)=\frac{\sum_{k=1}^{n}{x_{ik}x_{jk}}}{\sqrt{\sum_{k=1}^{n}{x_{ik}^{2}}}\sqrt{\sum_{k=1}^{n}{x_{jk}^{2}}}}$$
余弦相似度的值越接近1表示其越相似，越接近0表示其差异越大，使用余弦相似度可以消除数据的某些冗余信息，某些情况下更贴近数据的本质。我举个简单的例子，比如两篇文章的特征值都是：“大数据”“机器学习”和“极客时间”，A文章的特征向量为（3, 3, 3），即这三个词出现次数都是3；B文章的特征向量为（6, 6, 6），即这三个词出现次数都是6。如果光看特征向量，这两个向量差别很大，如果用欧氏距离计算确实也很大，但是这两篇文章其实非常相似，只是篇幅不同而已，它们的余弦相似度为1，表示非常相似。
余弦相似度其实是计算向量的夹角，而欧氏距离公式是计算空间距离。余弦相似度更关注数据的相似性，比如两个用户给两件商品的打分分别是（3, 3）和（4, 4），那么两个用户对两件商品的喜好是相似的，这种情况下，余弦相似度比欧氏距离更合理。
文本的特征值
我们知道了机器学习的算法需要计算距离，而计算距离需要还知道数据的特征向量，因此提取数据的特征向量是机器学习工程师们的重要工作，有时候甚至是最重要的工作。不同的数据以及不同的应用场景需要提取不同的特征值，我们以比较常见的文本数据为例，看看如何提取文本特征向量。
文本数据的特征值就是提取文本关键词，TF-IDF算法是比较常用且直观的一种文本关键词提取算法。这种算法是由TF和IDF两部分构成。
TF是词频（Term Frequency），表示某个单词在文档中出现的频率，一个单词在一个文档中出现的越频繁，TF值越高。
词频： $$ TF=\frac{某个词在文档中出现的次数}{文档总词数}$$
IDF是逆文档频率（Inverse Document Frequency），表示这个单词在所有文档中的稀缺程度，越少文档出现这个词，IDF值越高。
逆文档频率：$$IDF=log(\frac{所有的文档总数}{出现该词的文档数})$$
TF与IDF的乘积就是TF-IDF。
$$TF-IDF=TF\times IDF$$
所以如果一个词在某一个文档中频繁出现，但在所有文档中却很少出现，那么这个词很可能就是这个文档的关键词。比如一篇关于原子能的技术文章，“核裂变”“放射性”“半衰期”等词汇会在这篇文档中频繁出现，即TF很高；但是在所有文档中出现的频率却比较低，即IDF也比较高。因此这几个词的TF-IDF值就会很高，就可能是这篇文档的关键词。如果这是一篇关于中国原子能的文章，也许“中国”这个词也会频繁出现，即TF也很高，但是“中国”也在很多文档中出现，那么IDF就会比较低，最后“中国”这个词的TF-IDF就很低，不会成为这个文档的关键词。
提取出关键词以后，就可以利用关键词的词频构造特征向量，比如上面例子关于原子能的文章，“核裂变”“放射性”“半衰期”这三个词是特征值，分别出现次数为12、9、4。那么这篇文章的特征向量就是（12, 9, 4），再利用前面提到的空间距离计算公式计算与其他文档的距离，结合KNN算法就可以实现文档的自动分类。
贝叶斯分类
贝叶斯公式是一种基于条件概率的分类算法，如果我们已经知道A和B的发生概率，并且知道了B发生情况下A发生的概率，可以用贝叶斯公式计算A发生的情况下B发生的概率。事实上，我们可以根据A的情况，即输入数据，判断B的概率，即B的可能性，进而进行分类。
举个例子：假设一所学校里男生占60%，女生占40%。男生总是穿长裤，女生则一半穿长裤一半穿裙子。假设你走在校园中，迎面走来一个穿长裤的学生，你能够推断出这个穿长裤学生是男生的概率是多少吗？
答案是75%，具体算法是：
$$穿长裤是男生的概率 = \frac{男生穿长裤的概率 \times 是男生的概率}{学生穿长裤的概率}$$
这个算法就利用了贝叶斯公式，贝叶斯公式的写法是：
$$P(B|A)= \frac{P(A|B)*P(B)}{P(A)}$$
意思是A发生的条件下B发生的概率，等于B发生的条件下A发生的概率，乘以B发生的概率，除以A发生的概率。还是上面这个例子，如果我问你迎面走来穿裙子的学生是女生的概率是多少。同样带入贝叶斯公式，可以计算出是女生的概率为100%。其实这个结果我们根据常识也能推断出来，但是很多时候，常识受各种因素的干扰，会出现偏差。比如有人看到一篇博士生给初中学历老板打工的新闻，就感叹读书无用。事实上，只是少见多怪，样本量太少而已。而大量数据的统计规律则能准确反映事物的分类概率。
贝叶斯分类的一个典型的应用场合是垃圾邮件分类，通过对样本邮件的统计，我们知道每个词在邮件中出现的概率$P(A_{i})$，我们也知道正常邮件概率$P(B_{0})$和垃圾邮件的概率$P(B_{1})$，还可以统计出垃圾邮件中各个词的出现概率$P(A_{i}|B_{1})$，那么现在一封新邮件到来，我们就可以根据邮件中出现的词，计算$P(B_{1}|A_{i})$，即得到这些词出现情况下，邮件为垃圾邮件的概率，进而判断邮件是否为垃圾邮件。
数据挖掘
搜索排序
我们说过Hadoop大数据技术最早源于Google，而Google使用大数据技术最重要的应用场景就是网页排名。
当我们使用Google进行搜索的时候，你会发现，通常在搜索的前三个结果里就能找到自己想要的网页内容，而且很大概率第一个结果就是我们想要的网页。而排名越往后，搜索结果与我期望的偏差越大。并且在搜索结果页的上面，会提示总共找到多少个结果。
PageRank 算法
Google使用了一种叫PageRank的算法，这种算法根据网页的链接关系给网页打分。如果一个网页A，包含另一个网页B的超链接，那么就认为A网页给B网页投了一票，以下面四个网页A、B、C、D举例，带箭头的线条表示链接。
B网页包含了A、D两个页面的超链接，相当于B网页给A、D每个页面投了一票，初始的时候，所有页面都是1分，那么经过这次投票后，B给了A和D每个页面1/2分（B包含了A、D两个超链接，所以每个投票值1/2分），自己从C页面得到1/3分（C包含了A、B、D三个页面的超链接，每个投票值1/3分）。
而A页面则从B、C、D分别得到1/2、1/3、1分。用公式表示就是
$$PR(A) = \frac{PR(B)}{2}+\frac{PR( C )}{3}+\frac{PR(D)}{1}$$
等号左边是经过一次投票后，A页面的PageRank分值；等号右边每一项的分子是包含A页面超链接的页面的PageRank分值，分母是该页面包含的超链接数目。
这样经过一次计算后，每个页面的PageRank分值就会重新分配，重复同样的算法过程，经过几次计算后，根据每个页面PageRank分值进行排序，就得到一个页面重要程度的排名表。根据这个排名表，将用户搜索出来的网页结果排序，排在前面的通常也正是用户想要的结果。
但是这个算法还有个问题，如果某个页面只包含指向自己的超链接，这样的话其他页面不断给它送分，而自己一分不出，随着计算执行次数越多，它的分值也就越高，这显然是不合理的。这种情况就像下图所示的，A页面只包含指向自己的超链接。
Google的解决方案是，设想浏览一个页面的时候，有一定概率不是点击超链接，而是在地址栏输入一个URL访问其他页面，表示在公式上，就是
$$PR(A) = \alpha(\frac{PR(B)}{2}+\frac{PR( C )}{3}+\frac{PR(D)}{1})+\frac{(1-\alpha)}{4}$$
上面$（1-\alpha）$就是跳转到其他任何页面的概率，通常取经验值0.15（即$\alpha$ 为0.85），因为有一定概率输入的URL是自己的，所以加上上面公式最后一项，其中分母4表示所有网页的总数。
那么对于$N$个网页，任何一个页面$P_{i}$的PageRank计算公式如下
$$PageRank（P_{i}）=\alpha \sum_{P_{j}\in M(P_{i})}^{}{\frac{PageRank(P_{j})}{L(P_{j})}} + \frac{1-\alpha}{N}$$
公式中，$P_{j}\in M(P_{i})$表示所有包含有$P_{i}$超链接的$P_{j}$，$L(P_{j})$表示$P_{j}$页面包含的超链接数，$N$表示所有的网页总和。
由于Google要对全世界的网页进行排名，所以这里的N可能是一个万亿级的数字，一开始将所有页面的PageRank值设为1，带入上面公式计算，每个页面都得到一个新的PageRank值。再把这些新的PageRank值带入上面的公式，继续得到更新的PageRank值，如此迭代计算，直到所有页面的PageRank值几乎不再有大的变化才停止。
在这样大规模的数据上进行很多次迭代计算，是传统计算方法根本解决不了的问题，这就是Google要研发大数据技术的原因，并因此诞生了一个大数据行业。而PageRank算法也让Google从众多搜索引擎公司脱颖而出，铸就了Google接近万亿级美元的市值，开创了人类科技的新纪元。
关联分析
关联分析是大数据计算的重要场景之一，我在专栏开篇的时候就讨论过一个经典案例，通过数据挖掘，商家发现尿不湿和啤酒经常会同时被购买，所以商家就把啤酒和尿不湿摆放在一起促进销售。这个案例曾经被质疑是假的，因为没有人见过超市把啤酒和尿布放在一起卖。
在传统商超确实没有见过把啤酒和纸尿裤放在一起的情况，可能是因为传统商超的物理货架分区策略限制它没有办法这么做，而啤酒和尿不湿存在关联关系则确实是大数据中存在的规律，在电子商务网站就可以轻易进行关联推荐。
通过商品订单，可以发现频繁出现在同一个购物篮里商品间的关联关系，这种大数据关联分析也被称作是“购物篮分析”，频繁出现的商品组合也被称作是“频繁模式”。
在深入关联分析前，你需要先了解两个基本概念，一个是支持度，一个是置信度。
支持度
支持度是指一组频繁模式的出现概率，比如（啤酒，尿不湿）是一组频繁模式，它的支持度是4%，也就是说，在所有订单中，同时出现啤酒和尿不湿这两件商品的概率是4%。
置信度
置信度用于衡量频繁模式内部的关联关系，如果出现尿不湿的订单全部都包含啤酒，那么就可以说购买尿不湿后购买啤酒的置信度是100%；如果出现啤酒的订单中有20%包含尿不湿，那么就可以说购买啤酒后购买尿不湿的置信度是20%。
Apriori 算法
大型超市的商品种类数量数以万计，所有商品的组合更是一个天文数字；而电子商务网站的商品种类更多，历史订单数据同样也非常庞大，虽然我们有大数据技术，但是资源依然是有限的。
那我们应该从哪里考虑着手，可以使用最少的计算资源寻找到最小支持度的频繁模式？寻找满足最小支持度的频繁模式经典算法是Apriori算法，Apriori算法的步骤是：
第1步：设置最小支持度阈值。
第2步：寻找满足最小支持度的单件商品，也就是单件商品出现在所有订单中的概率不低于最小支持度。
第3步：从第2步找到的所有满足最小支持度的单件商品中，进行两两组合，寻找满足最小支持度的两件商品组合，也就是两件商品出现在同一个订单中概率不低于最小支持度。
第4步：从第3步找到的所有满足最小支持度的两件商品，以及第2步找到的满足最小支持度的单件商品进行组合，寻找满足最小支持度的三件商品组合。
第5步：以此类推，找到所有满足最小支持度的商品组合。
Apriori算法极大地降低了需要计算的商品组合数目，这个算法的原理是，如果一个商品组合不满足最小支持度，那么所有包含这个商品组合的其他商品组合也不满足最小支持度。所以从最小商品组合，也就是一件商品开始计算最小支持度，逐渐迭代，进而筛选出所有满足最小支持度的频繁模式。
通过关联分析，可以发现看似不相关商品的关联关系，并利用这些关系进行商品营销，比如我上面提到的啤酒和尿不湿的例子，一方面可以为用户提供购买便利；另一方面也能提高企业营收。
聚类
上一期我们讨论了“分类”，分类算法主要解决如何将一个数据分到几个确定类别中的一类里去。分类算法通常需要样本数据训练模型，再利用模型进行数据分类，那么一堆样本数据又如何知道各自的类别呢？样本数据归类一方面可以通过人工手动打标签，另一方面也可以利用算法进行自动归类，即所谓的“聚类”。
聚类就是对一批数据进行自动归类
K-means 算法
K-means是一种在给定分组个数后，能够对数据进行自动归类，即聚类的算法。
第1步：随机在图中取K个种子点，图中K=2，即图中的实心小圆点。
第2步：求图中所有点到这K个种子点的距离，假如一个点离种子点X最近，那么这个点属于X点群。在图中，可以看到A、B属于上方的种子点，C、D、E属于中部的种子点。
第3步：对已经分好组的两组数据，分别求其中心点。对于图中二维平面上的数据，求中心点最简单暴力的算法就是对当前同一个分组中所有点的X坐标和Y坐标分别求平均值，得到的
第4步：重复第2步和第3步，直到每个分组的中心点不再移动。这时候，距每个中心点最近的点数据聚类为同一组数据。
K-means算法原理简单，在知道分组个数的情况下，效果非常好，是聚类经典算法。通过聚类分析我们可以发现事物的内在规律：具有相似购买习惯的用户群体被聚类为一组，一方面可以直接针对不同分组用户进行差别营销，线下渠道的话还可以根据分组情况进行市场划分；另一方面可以进一步分析，比如同组用户的其他统计特征还有哪些，并发现一些有价值的模式。