1. 大数据算法：分类算法
KNN算法，即K近邻（K Nearest Neighbour）算法，是一种基本的分类算法。其主要原理是：对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类数据的类别。下面我给你画了一个KNN算法的原理图。
图中，红蓝绿三种颜色的点为样本数据，分属三种类别 、 、 。对于待分类点 ，计算和它距离最近的5个点（即K为5），这5个点最多归属的类别为 （4个点归属 ，1个点归属 ），那么 的类别被分类为 。
KNN的算法流程也非常简单，请看下面的流程图。
KNN算法是一种非常简单实用的分类算法，可用于各种分类的场景，比如新闻分类、商品分类等，甚至可用于简单的文字识别。对于新闻分类，可以提前对若干新闻进行人工标注，标好新闻类别，计算好特征向量。对于一篇未分类的新闻，计算其特征向量后，跟所有已标注新闻进行距离计算，然后进一步利用KNN算法进行自动分类。
读到这你肯定会问，如何计算数据的距离呢？如何获得新闻的特征向量呢？
KNN算法的关键是要比较需要分类的数据与样本数据之间的距离，这在机器学习中通常的做法是：提取数据的特征值，根据特征值组成一个n维实数向量空间（这个空间也被称作特征空间），然后计算向量之间的空间距离。空间之间的距离计算方法有很多种，常用的有欧氏距离、余弦距离等。
对于数据 和 ，若其特征空间为n维实数向量空间 ，即 ， ，则其欧氏距离计算公式为
这个欧式距离公式其实我们在初中的时候就学过，平面几何和立体几何里两个点之间的距离，也是用这个公式计算出来的，只是平面几何（二维几何）里的n=2，立体几何（三维几何）里的n=3，而机器学习需要面对的每个数据都可能有n维的维度，即每个数据有n个特征值。但是不管特征值n是多少，两个数据之间的空间距离的计算公式还是这个欧氏计算公式。大多数机器学习算法都需要计算数据之间的距离，因此掌握数据的距离计算公式是掌握机器学习算法的基础。
欧氏距离是最常用的数据计算公式，但是在文本数据以及用户评价数据的机器学习中，更常用的距离计算方法是余弦相似度。
余弦相似度的值越接近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值越高。
词频：
IDF是逆文档频率（Inverse Document Frequency），表示这个单词在所有文档中的稀缺程度，越少文档出现这个词，IDF值越高。
逆文档频率：
TF与IDF的乘积就是TF-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%，具体算法是：
这个算法就利用了贝叶斯公式，贝叶斯公式的写法是：
意思是A发生的条件下B发生的概率，等于B发生的条件下A发生的概率，乘以B发生的概率，除以A发生的概率。还是上面这个例子，如果我问你迎面走来穿裙子的学生是女生的概率是多少。同样带入贝叶斯公式，可以计算出是女生的概率为100%。其实这个结果我们根据常识也能推断出来，但是很多时候，常识受各种因素的干扰，会出现偏差。比如有人看到一篇博士生给初中学历老板打工的新闻，就感叹读书无用。事实上，只是少见多怪，样本量太少而已。而大量数据的统计规律则能准确反映事物的分类概率。
贝叶斯分类的一个典型的应用场合是垃圾邮件分类，通过对样本邮件的统计，我们知道每个词在邮件中出现的概率 ，我们也知道正常邮件概率 和垃圾邮件的概率 ，还可以统计出垃圾邮件中各个词的出现概率 ，那么现在一封新邮件到来，我们就可以根据邮件中出现的词，计算 ，即得到这些词出现情况下，邮件为垃圾邮件的概率，进而判断邮件是否为垃圾邮件。
现实中，贝叶斯公式等号右边的概率，我们可以通过对大数据的统计获得，当有新的数据到来的时候，我们就可以带入上面的贝叶斯公式计算其概率。而如果我们设定概率超过某个值就认为其会发生，那么我们就对这个数据进行了分类和预测，具体过程如下图所示。
训练样本就是我们的原始数据，有时候原始数据并不包含我们想要计算的维度数据，比如我们想用贝叶斯公式自动分类垃圾邮件，那么首先要对原始邮件进行标注，需要标注哪些邮件是正常邮件、哪些邮件是垃圾邮件。这一类需要对数据进行标注才能进行的机器学习训练也叫作有监督的机器学习。
2. Spark笔记(1) ：余弦相似度计算
spark
在推荐系统中，基于物品的协同过滤算法是业界应用最多的算法，它的思想是给用户推荐那些和他们喜欢的物品相似的物品，主要分为两个步骤：一，计算物品之间的相似度；二，根据物品相似度和用户的历史行为给用户生成推荐列表。
其中物品的相似度的计算，可以通过余弦相似度计算。余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。
计算公式如下：
以文本相似度为例，用上述理论计算文本的相似性。
怎样计算上面两句话的相似程度？
基本思路是：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。
第一步，分词
第二步，列出所有的词
第三步，计算词频
第四步，写出词频向量
问题就变成了如何计算这两个向量的相似程度。可以想象成空间中的两条线段，都是从原点出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合,这是表示两个向量代表的文本完全相等；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。
使用上面的公式计算可得：
计算结果中夹角的余弦值为0.81非常接近于1，所以，上面的句子A和句子B是基本相似的。
spark例子：
运行结果：
3. 经典大规模文本相似识别架构和算法总结
在数据分析和挖掘领域，我们经常需要知道个体间差异大小，从而计算个体相似性。如今互联网内容爆发时代，针对海量文本的相似识别拥有极大需求。本文将通过识别两段文本是否相似，来看看常见的相似算法，及线上落地方案。
一般情况下，我们会将数据进行向量化，将问题抽象为数学问题。比如两个样本X、Y，X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）表示N维向量空间的两个样本，分析差异主要有距离度量和相似度度量。
文本向量化有很多方法，切词、ngram是最常用方法。一般的，分词加预处理能更好的表达语义，我们通过预处理，过滤掉无效字符及停用词。
对"组装衣柜，刚买不久" 和 "组装鞋柜，全新"向量化
距离（Distance）用于衡量样本在空间上的距离，距离越大，差异越大。
欧氏距离是最容易直观理解的距离度量方法，我们认知中两个点在空间中的距离就是欧氏距离。扩展到高维空间中，欧式距离的计算公式如图1：
图1 欧氏距离欧式距离因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，当不同维度单位不同将使距离失去意义。
余弦相似度用向量空间中两个向量夹角余弦值作为衡量两个个体间差异的大小。余弦相似度更加注重两个向量在方向上的差异，而非距离或长度。公式如图2：
图2 余弦相似度
通过三维坐标系可以很直观的看到两者的区别，如图3所示：
图3 欧式距离和余弦相似度区别
欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧式距离适应于需要从维度大小中体现差异的场景，余弦相似度更多的是方向上的差异。如果我们分词后，将每个词赋予一定的权重，那么可以使用欧氏距离。更多情况下，我们采用余弦相似度来计算两文本之间相似度。
上面的相似算法，适用于小量样本，两两计算。那么在大规模样本下，给定新的样本怎么找到相似的样本呢？
下面我们将引入 SimHash 算法。
SimHash是Google在2007年发表的一种指纹生成算法或者叫指纹提取算法（如图4），其主要思想是降维。
图4 SimHash算法
算法主要原理分为这几步：
大家可能存在疑问：生成一串二进制需要这么麻烦吗？直接用hash函数生成0和1的不是更简单。比如：md5和hashcode等。
可以看得出来，相似两个文本，simhash局部变化而普通的hashcode却天壤之别。文本转换为SimHash后，我们通过海明距离（Hamming distance）计算两个SimHash是否相似。
Google的论文给出的数据中，64位的签名，在汉明距离为3的情况下， 可认为两篇文档是相似。
为了查询相似，我们依然需要两两比较。但汉明距离算法给了我们降维的捷径。
可以证明，汉明距离小于3情况下，将hash code等分为4份，则必有一份完全相同。
基于上述特点，我们设计一个MySQL存储索引方案来实现，如图5所示。
图5 MySQL存储索引方案
4. 20-余弦相似度及其R实现
余弦相似度 (Cosine Similarity) 通过计算两个向量的夹角余弦值来评估他们的相似度。将向量根据坐标值，绘制到向量空间中，求得他们的夹角，并得出夹角对应的余弦值，此余弦值就可以用来表征这两个向量的相似性。夹角越小，余弦值越接近于1，它们的方向越吻合，则越相似。
以二维空间为例，上图的a和b是两个向量，我们要计算它们的夹角θ。余弦定理告诉我们，可以用下面的公式求得：
在文本处理中，要使用余弦相似度算法，首先得将文本向量化，将词用“词向量”的方式表示可谓是将 Deep Learning 算法引入 NLP 领域的一个核心技术。自然语言处理转化为机器学习问题的第一步都是通过一种方法将这些文本数学化。其思路如下：
举例：
句子A：这只皮靴号码大了。那只号码合适。
句子B：这只皮靴号码不小，那只更合适。
1、中文分词：
使用结巴分词对上面两个句子分词后，分别得到两个词集：
2、列出所有词，将listA和listB放在一个set中，构成词包：
3、使用词集分别对listA和listB计算词频。
4、对listA和listB进行oneHot编码后得到的结果如下：
listAcode = [1, 2, 1, 2, 1, 1, 1, 1, 0, 0]
listBcode = [1, 2, 1, 1, 0, 0, 1, 1, 1, 1]
5、得出两个句子的词频向量之后，就变成了计算两个向量之间夹角的余弦值，值越大相似度越高。
6、两个向量的余弦值为0.805823，接近1，说明两句话相似度很高。
两个句子的相似度计算步骤如下：
1.通过中文分词，把完整的句子分成独立的词集合；
2.求出两个词集合的并集(词包)；
3.计算各自词集的词频并将词频向量化；
4.代入余弦公式就可以求出文本相似度。
注意，词包确定之后，词的顺序是不能再修改的，不然会影响到向量的变化。
以上是对两个句子做相似度计算，如果是对两篇文章做相似度计算，步骤如下：
1.找出各自文章的关键词并合成一个词集合；
2.求出两个词集合的并集(词包)；
3.计算各自词集的词频并将词频向量化；
4.代入余弦公式就可以求出文本相似度。
句子的相似度计算只是文章相似度计算的一个子部分。文章的关键词提取可以通过其他的算法来实现。
词频TF(Term Frequency)，是一个词语在文章或句子中出现的次数。要在一篇很长的文章中寻找关键字（词），就一般的理解，一个词对文章越关键在文章中出现的次数就越多，于是我们就采用“词频”进行统计。
但是这也不是绝对的，比如“地”，“的”，“啊”等词，它们出现的次数对一篇文章的中心思想是没有帮助的，只是中文语法结构的一部分而已。这类词也被称为“停用词”，所以，在计算一篇文章的词频时，停用词是应该过滤掉的。
仅仅过滤掉停用词就能解决问题吗?也不一定。比如分析政府工作报告，“中国”这个词语必定在每篇文章中都出现很多次，但是对于每份报告的主干思想有帮助吗？对比“反腐败”、“人工智能”、“大数据”、“物联网”等词语，“中国”这个词语在文章中应该是次要的。
TF算法的优点是简单快速，结果比较符合实际情况。缺点是单纯以“词频”做衡量标准，不够全面，词性和词的出现位置等因素没有考虑到，而且有时重要的词可能出现的次数并不多。这种算法无法体现词的位置信息，位置靠前的词与位置靠后的词，都被视为重要性相同，这是不科学的。
联系到层次分析法的思想，可以赋予每个词特定的权重，给那类最常见的词赋予较小的权重，相应的较少见的词赋予较大的权重，这个权重叫做“逆文档频率”(Inverse Doucument Frequency，缩写为IDF)，它的大小与一个词的常见程度成反比。而TF-IDF值就是将词频TF和逆文档频率IDF相乘，值越大，说明该词对文章的重要性越高。这就是TF-IDF算法。