1. 基于實例的學習算法

0x1：數據挖掘的一些相關知識脈絡

本文是一篇介紹K近鄰數據挖掘算法的文章，而所謂數據挖掘，就是讨論如何在數據中尋找模式的一門學科。

其實人類的科學技術發展的曆史，就一直伴随着數據挖掘，人們一直在試圖中數據中尋找模式，

• 獵人在動物遷徙的行為中尋找模式
• 農夫在莊稼的生長中尋找模式
• 政客在選民的意見上尋找模式
• 戀人在對方的反應中尋找模式
• 企業家的工作是要辨别出機會，尋找出那些可以轉變為有利可圖的生意的行為中的一些模式，也即所謂的成功的模式，并且利用這些機會
• 科學家的工作是理解數據，從數據中尋找模式，并用它們來指導在真實世界中如何運作

所謂數據挖掘，本質上就是通過分析存在于數據庫裡的數據來解決問題， 數據挖掘被定義為找出數據中的模式的過程，這個過程必須是自動的或半自動的 。

接下來的問題就是，如何表示 數據模式 ？

有價值的數據模式能夠讓我們對新數據做出非凡的預測，表示一個數據模式有兩種極端的方法：

• 一種是 内部結構很難被理解的黑匣子
• 一種是 展示模式結構的透明結構 ，它的結構揭示了模式的結構

兩種方法可能都可以做出好的預測，它們的區别在于 被挖掘出的模式能否以結構的形式清晰地表現，這個結構是否經得起分析，理由是否充分，能否用來形成未來的決策 。

如果模式能夠以顯而易見的方法獲得決策結構，就稱為 結構模式（structural pattern） ，換句話說，結構模式能夠幫助解釋有關數據的一些現象，具備可解釋性。

更進一步地，機器學習從數據中挖掘結構模式的過程，稱為 知識表達 ，機器學習所能發現的模式有許多不同的表達方式，每一種方式就是一種推斷數據輸出結構的技術，包括：

• 表（table） ：所謂表，就是采用與輸入相同的形式，完整存儲所有的輸入數據。這是機器學習輸出結構的最簡單、最基本的方法，它本質上等于一種存儲與搜索技術
• 回歸表（regression table） ：線性回歸模型就是一種回歸表，回歸表的核心目标是如何進行特征選擇，形成一個比原始數據集更小的、扼要的決策表，關鍵問題是确定去除哪些屬性而不會影響最終的決策
• 決策表（decision table） ：決策樹模型就是一種決策表
• 實例表（instance table） ：本文要介紹的K近鄰就是一種基于實例的學習算法，它在傳統表的基礎上進行了優化，有效縮減了需要存儲和開銷以及優化了搜索效率

0x2：什麼是基于實例的學習算法？

了解了來龍去脈的知識脈絡之外，我們将視野縮小到”基于實例的機器學習“這個領域内。

在基于實例的學習中，訓練樣本被一字不差地保存，并且使用一個距離函數來判定訓練集中的哪個實例與一個未知的測試實例最靠近。一旦找到最靠近的訓練實例，那麼最靠近實例所屬的類就被預測為測試實例的類。

基于實例的算法，有時也稱為 基于記憶的學習 ，它不是明确歸納概率分布或者分界面，而是将新的問題例子與訓練過程中見過的例子進行對比，這些見過的例子就在存儲器中。

Relevant Link:

2. 從有效尋找最近鄰問題說起

我們先來看下面這張圖，

假設我們現在的目标是尋找圖中離綠色點最近的實例。這個問題的答案似乎是顯而易見的，很顯然是右下方向的紅色三角。

但是我們隻要對題目稍加改造，例如将空間維數從2維擴展到100維，圖上的點密度增加10倍，這個時候，答案還依然明顯嗎？顯然不是了！

最直觀的想法是，我們需要建一張表（table），将圖中所有的數據點的坐标都保存起來，例如：

點x 1......x nA1......2..N5......3

這樣，每輸入一個新的點時，我們就遍曆一遍整張表，根據一定的距離函數（例如歐氏距離）找出距離最近的1個或k個實例。

這個場景在現實中是非常常見的需求，例如：

• 相似文本發現
• 相似性聚類
• 目标分類
• .....

盡管上面描述的查表法非常簡單且有效，但是缺點是速度非常慢。這個過程與訓練實例的數量成線性關系，換句話說，就是一個單獨的預測所花費的時間與訓練實例的數量成比例關系。處理整個數據集所花費的時間與訓練集實例數量O(train)和測試集實例數量O(test)的乘積成正比。

如何解決這個關鍵矛盾呢？學者們從數據結構優化上入手，提出了一系列的高效數據結構與搜索算法，它們合稱為K近鄰算法，K近鄰算法要解決的最核心問題就是如何有效尋找到最近鄰的實例集，支撐這種搜索的結構就是一種知識表達。我們接下來來讨論它。

3. K近鄰法（k-nearest neighbor KNN）算法介紹

K近鄰法（k-nearest neighbor KNN）是一種數據驅動（基于實例的算法（Instance-based Algorithms））的 分類 與 回歸 方法。它屬于一種 判别模型。

0x1：适用場景

1. 多分類問題場景

在多分類問題中的k近鄰法，k近鄰法的輸入為實例的特征向量，對應于特征空間的點，輸出為實例的類别。

k近鄰法假設給定一個訓練數據集，其中的實例類别已定，分類時，對新的實例，根據其k個最近鄰的訓練實例的類别，通過多數表決等方式進行預測。因此，k近鄰法不具有顯示的學習過程（或者說是一種延遲學習），k近鄰法實際上利用訓練數據集對特征向量空間進行劃分，并作為其分類的“模型”。

2. 回歸問題的場景

KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，将這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。

更有用的方法是将不同距離的鄰居對該樣本産生的影響給予不同的權值(weight)，如權值與距離成正比。

0x2：算法模型

輸入訓練數據集

，其中

為實例的特征向量，

為實例的類别。

根據給定的 距離度量 ，在訓練集中找出與 x 最鄰近的 K（需要人工設定調參） 個點，在由這 K 個點組成的鄰域中根據 分類決策規則 決定 x 的類别 y

K近鄰法的特殊情況是k=1的情形，稱為最近鄰算法，即對于輸入的實例點（特征向量）x，最近鄰法将訓練數據集中與x最鄰近的類作為x的類。

Y = P(y | x)：這裡概率函數P指某種最小化距離判定公式

可以看到，K近鄰法沒有顯示的學習過程，作為判别模型的一種，k近鄰法的判别函數的具體形式也不是很明顯。

K近鄰法使用的模型實際上對應于特征空間的劃分，某種意義上來說，k近鄰的模型就是樣本特征空間本身。

在k近鄰法中，當下列基本要素：

• 訓練集
• 距離度量
• k值
• 分類決策規則

确定後，對于任何一個新的輸入實例，它所屬的類唯一地确定。這相當于根據上述基本要素将特征空間劃分為一些子空間，确定子空間裡的每個點所屬的類。

特征空間中，對每個訓練實例點x1，距離該點比其他點更近的所有點組成一個區域，叫作單元（cell）。每個訓練實例點擁有一個單元，所有訓練實例點的單元構成對特征空間的一個劃分：

K近鄰很好地體現了判别式模型的思想，k近鄰不生成概率分布函數，它隻是通過三個基本要素盡可能地“捕捉”訓練樣本中的概率密度特征。之所以輸入樣本會被分到不同的類别，其本質就在于在訓練樣本中存在不均勻的概率密度分布，即某一個區域某一個類别密度占比比其他的類多。

下面我們來具體談談K近鄰模型的幾個基本要素。

1. K值選擇

K值的選擇會對K近鄰法的結果産生重大影響。

• 如果選擇較小的K值，就相當于用較小的鄰域中的訓練實例進行預測“學習”的近似誤差（approximation error）會減少，隻有與輸入實例較近的（相似的、Lp距離較小的）訓練實例才會對預測結果起作用但缺點是“學習”的估計誤差（estimation error）會增大，預測結果會對近鄰的實例點非常敏感，如果近鄰的實例點恰巧是噪聲，預測就會出錯，可以理解為模型的容錯性較差換句話說，k值的減小就意味着整體模型變得複雜（因為搜索範圍小了，所以總的需要的搜索結果的存儲單元就變多了），容易發生過拟合。
• 如果選擇較大的K值，就相當于用較大鄰域中的訓練實例進行預測優點是可以減少學習的估計誤差，即不容易受到近鄰點的波動影響但缺點是學習的近似誤差會增大，這時與輸入實例較遠的（不相似的）訓練實例也會對預測其作用，使預測發生錯誤總體來說，K值的增大就意味着整體模型變得簡單

近似誤差和 估計誤差 的核心區别在于是假設臨近點的噪音擾動比較多還是遠點的噪音擾動比較多。

在實際應用中，K值一般選取一個比較小的數值，即我們基本上認為近鄰點的相關性是比較大的，而原點的相關性比較小

在實際項目中，K值的選擇和樣本中的概率密度分布有關，并沒有一個定式的理論告訴我麼該選什麼樣的K值，好在的是這個K值的搜索空間并不是很大，通常我們可以采取一個for循環交叉驗證來搜索所有可能的K值，通過重複進行多次實驗，每次随機選取不同的train set和validate set，查看KNN模型對train set和validate set的拟合和泛化能力來選擇一個最好的K值。

理論上分析 ：

理論上說，當 k 和實例的數量 n 都變成無窮大，使得 k/n -> 0 時，那麼在數據集上産生的誤差概率将達到理論上的最小值。

2. 距離度量

特征空間中兩個實例點的距離是兩個實例點相似程度的一種數字化度量。

K近鄰模型的特征空間一般是n維實數向量空間

，計算兩個向量之間的距離有很多種方法，注意這不是KNN獨有的算法，向量間距離模型是數學中的基礎概念：

設特征空間

是n維實數向量空間

：

，

的Lp距離定義為：

1）P = 1：曼哈頓距離（Manhattan distance）

2）P = 2：歐式距離（Euclidean distance）

3）P = 正無窮：各個坐标距離的最大值

下圖給出了二維空間中p取不同值時，與原點的Lp距離為1（Lp = 1）的點的集合圖形

這張圖很好地說明了取不同的距離策略對于KNN對于緊鄰點的搜索範圍是不同的，進而影響随後的判别分類結果

舉一個例子說明由不同的距離度量所确定的最近鄰點是不同的。已知二維空間的3個點

，我們來對比一下在p取不同的值時，Lp距離下X1的最近鄰點

P值和X2距離和X3距離146244.24343.78443.57

可以看到，p = 1/2時，X2是X1的最近鄰點；P >= 3，X3是X1的最近鄰點。

3. 分類決策規則

近鄰法中的分類決策規則往往是 多數表決 ，即由輸入實例的k個臨近的訓練實例中的多數的label決定輸入實例的類。當K=1時算法退化為最近鄰搜索。

多數表決規則（majority voting rule）本質也是最優化技術，它符合極大似然估計原則。

我們假設分類的損失函數為0-1損失函數為：

那麼誤分類的概率是：

對給定的實例

，其最近鄰的 k 個訓練實例點構成集合

，如果涵蓋

的區域的類别是Cj，那麼誤分類率是：

要使誤分類率最小，即經驗風險最小，就要使下式最大：

即模型對訓練樣本的預測準确度（拟合程度）最大。所以多數表決規則等價于經驗風險最小化。

0x3：學習策略

KNN的學習策略很簡單，就是在訓練集中尋找最近鄰的K個實例點，并進行voting，選擇最多類别的那個，即經驗風險最小化。這同樣體現了極大似然估計的核心思想。

0x4：學習算法

KNN的策略非常直觀易理解，算法要解決是具體的工程化問題，即如何在高維空間中選出 k 個近鄰點，當維度很高且樣本量很大的時候，如果不采取一些高效的算法而直接暴力搜索的話是非常耗時的。

解決該問題的思路就是利用特殊構造的存儲數據結構以及特殊的搜索方法來完成，這也是本文的重點讨論部分。

最先被提出的一種數據結構是樹結構，通過應用分治思想，樹結構将原始的O(N)複雜度降低為O(logN)複雜度，我們接下來來讨論它。

1. KD樹（kd tree）結構

KD樹是一種對K維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構。kd樹是一個 二叉樹 ，一棵KD樹就是一個超平面，表示對K維空間的一個劃分（partition）。構造KD樹相當于不斷地用垂直于坐标軸的超平面将K維空間切分，構成一系列的K維超矩形區域。KD樹的每個結點對應于一K維超矩形區域。

這裡K是數據集屬性的數量。

下圖展示了一個k=2的小例子：

樹不一定會發展到相同的深度，訓練集中的每一個實例與樹中的一個結點相對應，最多一半的結點是葉子節點。

2. 構建KD樹

輸入：k維空間數據集

（樣本數量是N），每個樣本的維度是k，

• 構造根節點，根節點對應于K維空間中包含所有實例點的超矩形區域
• 選擇 為坐标軸，以數據集T中所有實例的 坐标的 中位數 做 i 為 切分點 ，将根節點對應的超矩形區域切分為兩個子區域，切分由通過切分點并 與坐标軸 垂直的超平面 實現。由根節點生成深度為 1 的 左，右子節點 ：左子結點對應坐标 小于切分點的子區域右子節點對應于坐标 大于切分點的子區域
• 重複上述分裂過程，對深度為 j 的結點，選擇 為切分的坐标軸，（取模循環不斷根據每個維度進行二叉切分），以該節點的區域中所有實例的 坐标的 中位數 作為 切分點 ，将該結點對應的超矩形區域切分為兩個子區域。切分由通過切分點并與坐标軸 垂直的超平面實現。由該結點生成深度為 j 1 的左、右子節點：左子節點對應坐标 小于切分點的子區域；右子節點對應坐标 大于切分點的子區域；将剛好落在切分超平面上的實例點保存在該結點
• 直到兩個子區域 沒有 實例存在時停止（即所有實例點都被分到某個子空間中），從而形成KD樹的區域劃分，最後一次切分得到的左、右子矩形空間就是葉節點

用一個例子來說明kd樹構造過程 ，給定一個二維空間的數據集：

• 根節點對應包含數據集 T 的超矩形區域
• 選擇 軸，6個數據點的 坐标的中位數是7，以平面 将空間分為左、右量子子矩形（子結點）
• 接着，左矩形的第二個維度的中位數是4，所以以 再分為兩個子矩形；右矩形以 分為兩個子矩形
• 繼續切分，直到所有的實例點都被分到一個超平面上，所切出的空間是一個不包含任何實例點的純超矩形空間為止，最後一次切分得到的左、右子矩形空間就是葉節點

3. KD樹更新

與其他大部分機器學習方法相比，基于實例學習的一個優勢是新的實例可以在任何時候加入到訓練集裡。

新的數據來臨時，需要用新的數據點判斷其屬于哪個葉子節點，并且找出葉子節點的超矩形。如果超矩形為空，就将新數據點放置在那裡，否則分裂超矩形，分裂在最長的邊上進行，以保持方形。

這種簡單的探索式方法并不能保證在加入一系列點後，樹依然會維持平衡，也不能保證為搜索最近鄰塑造良好的超矩形。有時候從頭開始重建數不失為一個良策。例如，當樹的深度達到最合适的深度值的兩倍時。

4. 搜索KD樹

完成了KD樹建樹後，接下來讨論如何利用KD樹進行高效K近鄰搜索：

輸入：根據train set構造的kd樹；目标點x

輸出：x的最近鄰

• 在KD樹中找出包含目标點x的葉節點：從根節點出發，遞歸地向下訪問KD樹，若目标點x當前維的坐标小于切分點的坐标，則移動到左子結點，否則移動到右子節點，直到子節點為葉子節點（某個不含訓練實例的超矩形區域）為止
• 包含目标點的葉節點對應包含目标點的最小超矩形區域，以此葉節點的實例暫時作為“當前最近點“，注意這裡說暫時是因為不一定該葉節點的實例點就真的是最近鄰點了，理論上目标點的最近鄰一定在以目标點為中心并且圓周通過當前最近點的超球體内部(局部最優原理)，接下來的逆向回溯的目的就是嘗試尋找在這個超球體區域内是否還存在其他葉節點内的實例點比“當前最近點”更近
• 以此葉節點為"當前最近點"遞歸的向上回退，在每個結點(父節點)進行以下操作：重複此過程，依次回退到根節點，搜索結束，最後查看存儲的"當前最近點"即為x的最近鄰點如果該結點保存的實例點比當前最近點距離目标點更近，則已該實例點為"當前最近點"如果該結點的另一子結點的超矩形區域與超球體相交(可能存在另一個局部最優)，那麼在相交的區域内尋找與目标點更近的實例點。如果存在這樣的點，将此點作為新的當前最近鄰點，算法轉到更上一級的父節點如果父節點的另一個子結點的超矩形區域與超球體不相交，說明另一個分支不存在另一個局部最優，則繼續該分支的逆向回溯
• 在回退的過程中，不斷查找與目标點最鄰近的結點，當确定不存在更近的結點時終止。這樣搜索就被限制在空間的局部區域上，效率大為提高了(這也是二叉樹的核心思想 - 分而治之)

用下圖來說明kd樹的搜索過程，根節點為A，子節點是B，C，D，E，F，G；目标實例點S，求S的最近鄰

• 首先在KD樹中正向搜索，定位到最右下角那個矩形區域，随後開始逆向回溯過程
• 該矩形區域的實例點是D，所以暫時以D作為近似最近鄰。但是理論上最近鄰一定在以點S為中心通過點D的圓的内部(局部最優)，因此需要繼續逆向回溯
• 然後返回節點D的父節點B，在節點B的另一子結點F的區域内嘗試搜索，但是因為節點F的區域與超圓不相交，不可能有最近鄰點
• 繼續返回上一級父節點A，在節點A的另一子節點C的區域内嘗試搜索，結點C的區域與圓相交，在超矩形區域在園内的實例點有點E，點E比點D更近，因此成為新的最近似點
• 最後得到點E是點S的最近鄰

5. KD樹面臨的挑戰和困境

我們已經看到，KD樹是可用于有效尋找最近鄰的良好數據結構，但是，并不完美。當面對不均勻數據的數據集時，便面臨一些基本沖突和挑戰：

• 既要求樹有完美的平衡結構，又要求區域近似方形
• 更重要的是，矩形、正方形都不是最好的使用形狀，原因是它們都有角。處于邊界附近的實例點的近鄰搜索不太”柔和“，矩形的角是一個很難處理的問題

這裡所謂的平衡結構，就是指樹的兩邊分叉要盡量分布平均，這樣可以最大程度地發揮O(logN)的優化效果，但是如果數據點的分布非常不均衡，采用中值的方法也許會在同一個方向上産多多次後續分裂，從而産生瘦長型的超矩形。一個更好的解決方法是采用平均值作為分裂點而不是中位值。這樣産生的KD樹會更趨向于方形。

但是均值分裂點技術依然無法完全規避KD原生的問題，為此，學界提出了超球分界面代替超矩形分界面的改進方法。

6. Ball Tree搜索

KD tree的思想非常精妙，但是也存在一些問題， 形并不是用到這裡最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外，矩形甚至是正方形并不是用在這裡最完美的形狀，由于它的角。為了解決這些問題，引入了ball tree，即使用超球面而不是超矩形劃分區域

Ball Tree就是一個K維超球面來覆蓋訓練樣本點。

上圖（a）顯示了一個2維平面包含16個觀測實例的圖,圖（b）是其對應的ball tree，其中結點中的數字表示包含的觀測點數。

樹中的每個結點對應一個圓，結點的數字表示該區域保含的觀測點數，但不一定就是圖中該區域囊括的點數，因為有重疊的情況，并且一個觀測點隻能屬于一個區域。實際的ball tree的結點保存圓心和半徑。葉子結點保存它包含的觀測點。

1）構造ball tree

Ball tree的建樹過程和KD tree大體上一緻，區别在于ball tree每次的切分點都是當前超球體的圓心。

• 選擇一個距離當前圓心最遠的觀測點 i1，和距離i1最遠的觀測點 i2
• 将圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心
• 然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑，這樣，左、右子節點又分裂成了新的超球體。

2）搜索ball tree

使用Ball tree時：

• 先自上而下找到包含target的葉子結點，從此結點中找到離它最近的觀測點。這個距離就是最近鄰的距離的上界。
• 檢查它的兄弟結點中是否包含比這個上界更小的觀測點，和KD tree一樣，檢查的标準就是兄弟的超球體和當前結點的超球體是否有交集如果沒有交集，則這個兄弟結點不可能包含“更近鄰點”如果有交集，則繼續搜索兄弟節點

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!