KNN分類算法

KNN算法，即K近鄰（K Nearest Neighbour）算法，是一種基本的分類算法。其主要原理是：對于一個需要分類的數(shù)據(jù)，將其和一組已經(jīng)分類標注好的樣本集合進行比較，得到距離最近的K個樣本，K個樣本最多歸屬的類別，就是這個需要分類數(shù)據(jù)的類別。下面我給你畫了一個KNN算法的原理圖。

image

圖中，紅藍綠三種顏色的點為樣本數(shù)據(jù)，分屬三種類別、、 。對于待分類點 ，計算和它距離最近的5個點（即K為5），這5個點最多歸屬的類別為（4個點歸屬，1個點歸屬），那么的類別被分類為。

KNN的算法流程也非常簡單，請看下面的流程圖。

image

KNN算法是一種非常簡單實用的分類算法，可用于各種分類的場景，比如新聞分類、商品分類等，甚至可用于簡單的文字識別。對于新聞分類，可以提前對若干新聞進行人工標注，標好新聞類別，計算好特征向量。對于一篇未分類的新聞，計算其特征向量后，跟所有已標注新聞進行距離計算，然后進一步利用KNN算法進行自動分類。

讀到這你肯定會問，如何計算數(shù)據(jù)的距離呢？如何獲得新聞的特征向量呢？

數(shù)據(jù)的距離

KNN算法的關鍵是要比較需要分類的數(shù)據(jù)與樣本數(shù)據(jù)之間的距離，這在機器學習中通常的做法是：提取數(shù)據(jù)的特征值，根據(jù)特征值組成一個n維實數(shù)向量空間（這個空間也被稱作特征空間），然后計算向量之間的空間距離?？臻g之間的距離計算方法有很多種，常用的有歐氏距離、余弦距離等。

對于數(shù)據(jù)和，若其特征空間為n維實數(shù)向量空間，即，，則其歐氏距離計算公式為

這個歐式距離公式其實我們在初中的時候就學過，平面幾何和立體幾何里兩個點之間的距離，也是用這個公式計算出來的，只是平面幾何（二維幾何）里的n=2，立體幾何（三維幾何）里的n=3，而機器學習需要面對的每個數(shù)據(jù)都可能有n維的維度，即每個數(shù)據(jù)有n個特征值。但是不管特征值n是多少，兩個數(shù)據(jù)之間的空間距離的計算公式還是這個歐氏計算公式。大多數(shù)機器學習算法都需要計算數(shù)據(jù)之間的距離，因此掌握數(shù)據(jù)的距離計算公式是掌握機器學習算法的基礎。

歐氏距離是最常用的數(shù)據(jù)計算公式，但是在文本數(shù)據(jù)以及用戶評價數(shù)據(jù)的機器學習中，更常用的距離計算方法是余弦相似度。

余弦相似度的值越接近1表示其越相似，越接近0表示其差異越大，使用余弦相似度可以消除數(shù)據(jù)的某些冗余信息，某些情況下更貼近數(shù)據(jù)的本質(zhì)。我舉個簡單的例子，比如兩篇文章的特征值都是：“大數(shù)據(jù)”“機器學習”和“極客時間”，A文章的特征向量為（3, 3, 3），即這三個詞出現(xiàn)次數(shù)都是3；B文章的特征向量為（6, 6, 6），即這三個詞出現(xiàn)次數(shù)都是6。如果光看特征向量，這兩個向量差別很大，如果用歐氏距離計算確實也很大，但是這兩篇文章其實非常相似，只是篇幅不同而已，它們的余弦相似度為1，表示非常相似。

余弦相似度其實是計算向量的夾角，而歐氏距離公式是計算空間距離。余弦相似度更關注數(shù)據(jù)的相似性，比如兩個用戶給兩件商品的打分分別是（3, 3）和（4, 4），那么兩個用戶對兩件商品的喜好是相似的，這種情況下，余弦相似度比歐氏距離更合理。

文本的特征值

我們知道了機器學習的算法需要計算距離，而計算距離需要還知道數(shù)據(jù)的特征向量，因此提取數(shù)據(jù)的特征向量是機器學習工程師們的重要工作，有時候甚至是最重要的工作。不同的數(shù)據(jù)以及不同的應用場景需要提取不同的特征值，我們以比較常見的文本數(shù)據(jù)為例，看看如何提取文本特征向量。

文本數(shù)據(jù)的特征值就是提取文本關鍵詞，TF-IDF算法是比較常用且直觀的一種文本關鍵詞提取算法。這種算法是由TF和IDF兩部分構成。

TF是詞頻（Term Frequency），表示某個單詞在文檔中出現(xiàn)的頻率，一個單詞在一個文檔中出現(xiàn)的越頻繁，TF值越高。

詞頻：

IDF是逆文檔頻率（Inverse Document Frequency），表示這個單詞在所有文檔中的稀缺程度，越少文檔出現(xiàn)這個詞，IDF值越高。

逆文檔頻率：

TF與IDF的乘積就是TF-IDF。

所以如果一個詞在某一個文檔中頻繁出現(xiàn)，但在所有文檔中卻很少出現(xiàn)，那么這個詞很可能就是這個文檔的關鍵詞。比如一篇關于原子能的技術文章，“核裂變”“放射性”“半衰期”等詞匯會在這篇文檔中頻繁出現(xiàn)，即TF很高；但是在所有文檔中出現(xiàn)的頻率卻比較低，即IDF也比較高。因此這幾個詞的TF-IDF值就會很高，就可能是這篇文檔的關鍵詞。如果這是一篇關于中國原子能的文章，也許“中國”這個詞也會頻繁出現(xiàn)，即TF也很高，但是“中國”也在很多文檔中出現(xiàn)，那么IDF就會比較低，最后“中國”這個詞的TF-IDF就很低，不會成為這個文檔的關鍵詞。

提取出關鍵詞以后，就可以利用關鍵詞的詞頻構造特征向量，比如上面例子關于原子能的文章，“核裂變”“放射性”“半衰期”這三個詞是特征值，分別出現(xiàn)次數(shù)為12、9、4。那么這篇文章的特征向量就是（12, 9, 4），再利用前面提到的空間距離計算公式計算與其他文檔的距離，結合KNN算法就可以實現(xiàn)文檔的自動分類。

貝葉斯分類

貝葉斯公式是一種基于條件概率的分類算法，如果我們已經(jīng)知道A和B的發(fā)生概率，并且知道了B發(fā)生情況下A發(fā)生的概率，可以用貝葉斯公式計算A發(fā)生的情況下B發(fā)生的概率。事實上，我們可以根據(jù)A的情況，即輸入數(shù)據(jù)，判斷B的概率，即B的可能性，進而進行分類。

舉個例子：假設一所學校里男生占60%，女生占40%。男生總是穿長褲，女生則一半穿長褲一半穿裙子。假設你走在校園中，迎面走來一個穿長褲的學生，你能夠推斷出這個穿長褲學生是男生的概率是多少嗎？

答案是75%，具體算法是：

這個算法就利用了貝葉斯公式，貝葉斯公式的寫法是：

意思是A發(fā)生的條件下B發(fā)生的概率，等于B發(fā)生的條件下A發(fā)生的概率，乘以B發(fā)生的概率，除以A發(fā)生的概率。還是上面這個例子，如果我問你迎面走來穿裙子的學生是女生的概率是多少。同樣帶入貝葉斯公式，可以計算出是女生的概率為100%。其實這個結果我們根據(jù)常識也能推斷出來，但是很多時候，常識受各種因素的干擾，會出現(xiàn)偏差。比如有人看到一篇博士生給初中學歷老板打工的新聞，就感嘆讀書無用。事實上，只是少見多怪，樣本量太少而已。而大量數(shù)據(jù)的統(tǒng)計規(guī)律則能準確反映事物的分類概率。

貝葉斯分類的一個典型的應用場合是垃圾郵件分類，通過對樣本郵件的統(tǒng)計，我們知道每個詞在郵件中出現(xiàn)的概率，我們也知道正常郵件概率和垃圾郵件的概率，還可以統(tǒng)計出垃圾郵件中各個詞的出現(xiàn)概率，那么現(xiàn)在一封新郵件到來，我們就可以根據(jù)郵件中出現(xiàn)的詞，計算，即得到這些詞出現(xiàn)情況下，郵件為垃圾郵件的概率，進而判斷郵件是否為垃圾郵件。

現(xiàn)實中，貝葉斯公式等號右邊的概率，我們可以通過對大數(shù)據(jù)的統(tǒng)計獲得，當有新的數(shù)據(jù)到來的時候，我們就可以帶入上面的貝葉斯公式計算其概率。而如果我們設定概率超過某個值就認為其會發(fā)生，那么我們就對這個數(shù)據(jù)進行了分類和預測，具體過程如下圖所示。

image

訓練樣本就是我們的原始數(shù)據(jù)，有時候原始數(shù)據(jù)并不包含我們想要計算的維度數(shù)據(jù)，比如我們想用貝葉斯公式自動分類垃圾郵件，那么首先要對原始郵件進行標注，需要標注哪些郵件是正常郵件、哪些郵件是垃圾郵件。這一類需要對數(shù)據(jù)進行標注才能進行的機器學習訓練也叫作有監(jiān)督的機器學習。