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演算法。