K-NN聚類演算法的良好泛化，可用於數據簡化

GIF/1.7M

圖：pixabay

原文來源：atasciencecentral

作者：Vincent Granville

「機器人圈」編譯：嗯~阿童木呀、多啦A亮

在本文中我將描述一種有趣且直觀的聚類演算法（可以用於數據簡化），相較於傳統的分類器，它具有以下優勢：

?對異常值和錯誤數據具有更強的魯棒性。

?執行速度更快。

?泛化了一些知名的演算法。

對於本文所涉及的內容：

1.即使你對K-NN不是非常了解也沒關係，當然，如果你想了解更多信息，請點擊此處鏈接（http://www.datasciencecentral.com/page/search?q=k-nn）。

2.你不需要具備統計學的背景知識。

接下來，我們用簡單明了、通俗易通的語言來描述這個新演算法及其各個組成部分。

通用框架

我們將要處理的是一個監督學習問題，更具體地說，是聚類（也稱為監督分類）。特別地，我們要為一個不屬於訓練集的新觀察值分配一個類標籤。相較於檢查個別點（最近的鄰值），並使用多數（投票）規則，根據最近的鄰居數將新的觀察值分配給一個群集，我們的方法是檢查點的簇（簇s），並將關注點放在放在最近的簇中而不是最近的點。

簇和簇密度

此處所考慮的簇是由圓（二維）或球體（三維）進行定義的。在最基本的版本中，我們為每個集群提供一個簇，而簇被定義為最小的圓，它包含了上述集群中點的預定比例p。如果聚類能夠很好得進行分離，我們甚至可以使用p = 1。我們將簇的密度定義為單位面積上的點數。一般來說，我們想要建立的是具有高密度的簇。

理想情況下，我們希望訓練集中的每個集群都能夠被少量（可能是輕微重疊）的簇所覆蓋，且每一個都具有高密度。此外，作為通用規則，訓練集中的一個點只能屬於一個簇，（理想情況下）只能屬於一個集群。但是，與兩個簇相關聯的圓是允許重疊的。

分類規則，計算複雜性，內存需求

一旦我們為每個集群建立了一組簇集合，分類規則就很簡單了。構建這些簇是複雜的預處理步驟，但是正如上一所描述的那樣，我們只需要進行粗略的近似就可以了。分類規則如下：

?1-NC演算法：將新的觀察值分配給最接近最近簇的集群。

?K-NC演算法：在最接近問題中觀察值的K個簇（多數票選）中，將新的觀察值分配給具有最多個簇數量的集群。

需要注意的是，如果簇是由單個點組成的，則K-NN和K-NC演算法是相同的。還要注意的是，計算點和簇之間的距離是很直截了當的，因為簇是圓形的。你只需要知道上述中所討論的圓的圓心和半徑就可以了。

最後，為了將一個新的觀察值平分配到一個集群中，只需要檢查所有的簇，而不是所有的點。因此，K-NC演算法要比K-NN快v倍，其中v是訓練集中的點數除以所有集群的簇數。實際上，我們所擁有的簇數要遠小於訓練集中的點數，所以在處理非常大的訓練集時，v可能很大。特別是簇之間沒有太多的重疊的時候，更是如此。

簡而言之，這些簇整合了訓練集數據：一旦這些簇經過計算之後，我們便可以丟棄所有的數據，並且只保留簇（包括它們的中心、半徑、密度和集群標籤）。這也節省了大量的內存，本身也可以用作數據簡化技術。

簇構建和最小圓問題

在構建簇系統時，這個概念可被證明可能是有效的。最小圓問題（點擊此處查看詳細信息）涵蓋的是計算包含給定區域中所有點的最小圓。如下圖所示。

基於最小圓問題計算的簇

人們會認為這樣的簇是否具有最大的密度，一種理想的性能。現在有幾種非常有效的演算法可以解決這個問題。有些甚至允許你為每一個點添加一個權重。

集群產生的重力場

你可以選擇跳過本章節，如果你有興趣來進一步了解如何改進K-NC演算法，以及改進諸如K-NN等標準演算法，那麼你就該好好閱讀該章節了。另外，它強調了一個事實，即在計算點之間的平均距離時，相較於原始距離，距離的平方可能是一個更好的衡量指標（從建模的角度來看）。這就像許多物理定律種所涉及的「距離」，往往是兩個對象之間距離的平方，而不是距離本身。換句話說，你可以按照引力定律的思維方式來看待一個分類問題：（在分類背景中）哪個集群將「吸引」一個新的觀察值呢？就對應於（天體物理學背景中）哪個天體將吸引和吸附一個流星體。你會認為在這兩種情況下，類似的定理都是適用的。

對於每個點x（通常指的是我們要分類的新點）和集群G，潛在V（x，G）定義如下：

其中總和超過了G中的所有簇。其實一個更好的定義可能是僅在G中的k個最鄰近的簇中取總和，以獲得預定義的k值。潛在的分類規則是將點x分配給最大化v（x，G）的集群G。

最後的改進工作包括在上述總和中為每一項添加一個權重：權重是相應簇的密度。請注意，如果簇（它們所代表的圓）有著顯著的重疊情況，則應在潛在的定義V中加以解決。通常情況下，訓練集點只能屬於一個簇，（理想情況下）只能屬於一個集群。

創建有效的簇系統

這個數據預處理步驟是一個較為複雜的步驟。然而，易於獲取的近似解決方案實施效果非常好。畢竟，即使每個點都是一個簇（K-NN為特殊情況），我們也能得到非常理想的結果。

幾種不同的可行性方法：

?從每個訓練集點的一個簇開始，并迭代地合併這些簇。

?基於上述的最小圓問題，從每個集群的一個簇開始，然後對其進行收縮並移動中心，直到它包含訓練集點的比例p，且上述集群中簇的密度達到最大值（或者足夠接近最大值）。接下來對上述集群中剩餘的點重複此操作。假設每個集群中都有一個包含至少30%點數的圓形內核，那麼可以選擇p=30%。

?在每個群集中從預先指定數量的隨機簇（隨機半徑、隨機圓心、可能與訓練集中隨機選擇的點相對應）開始。每次調整一個簇的圓心和半徑，以優化一些下面所述的與密度相關的標準。此外，如果隨著時間的推進，使用生成和消亡過程來淘汰一些簇，並不斷創建新的，也是一個不錯的方法。

這些方法的目的是獲得儘可能少的簇，能夠覆蓋整個訓練集而不產生過多的重疊。每個簇必須具有高密度，且須包含超過（例如）上述集群中訓練集點數的1％。我們可以增加一個限制條件：每個簇必須至少含有兩個點。

非圓形簇

其實，測試簇的形狀是否重要也是一件很有意思的事情。只要我們有足夠多的簇，形狀可能就沒那麼重要了（這一點應該經過驗證），因此圓形—由於它在測量簇和點之間的距離時能夠極大地簡化計算—可以說是最為理想的選擇。請注意，如果一個點在一個簇內部（在其圓內），則簇和該點之間的距離為零。我們應該測試這個規則是否對異常值或錯誤數據具有更強的魯棒性。

源代碼

我希望在不久之後可以提供一段關於K-NC分類器的代碼，特別是建立一個運作良好的簇系統。而且很明顯的一點是，如果是基於它是一個泛化（也可以用於數據簡化）的意義上來講，這種演算法要比K-NN好得多，但是也可以去嘗試測試什麼樣的簇（小或大）能夠提供基於交叉驗證的最佳結果，且會有多大的改進程度，應該是很有趣的。

同時，我鼓勵讀者設計一個實現，也許在Python中。這將是一個偉大的數據科學項目。我將發布並提供這些解決方案，為作者提供支持（例如，在LinkedIn上），並向他/她發送我的Wiley book（http://www.datasciencecentral.com/profiles/blogs/my-data-science-book）的簽名副本。

潛在的增強、數據簡化和結論

對我們的方法的潛在改進包括：

?利用密度和鄰近性，在將一個新的觀察值分配給一個集群時，將重點放在更為密集的簇中。

?允許訓練集點屬於同一集群內的多個簇。

?允許訓練集點屬於多個集群。

?測試由最近鄰居組成的簇。

?減少簇之間的重疊。

此外，我們需要測試這個新演算法，並根據創建簇的方式來查看它在什麼時候能夠運行得更好。假設在每種情況下使用不同的K值，K-NC是不是就相當於K-NN？即使它們是等價的，K-NC有一個很大的好處就是：它可以用於數據簡化，而且與傳統的數據簡化技術是不一樣的。諸如PCA這樣的傳統數據簡化技術嘗試將數據集投影到具有較低維度的空間上。由K-NC生成的簇結構是一種數據簡化技術的結果，它不執行降維或投影，而是在相同的原始空間中執行類似於數據精簡或數據壓縮或熵減少的方法。

另一個好處是，得益於K-NC在構建簇結構時的預處理步驟，其運行速度要比K-NN快得多。它也更直觀，主要是因為它基於直觀的概念，每個集群由子集群簇組成。它確實與代表集群結構的隨機點過程的模型擬合相類似，例如奈曼-斯科特（Neyman-Scott）集群過程。

最後，在許多情況下，改進分類器的一種方法是通過重新縮放或轉換數據，例如使用對數刻度。大多數分類器是依賴於尺度的，我們正在開發不斷擴展的尺度分類器，就像我們引入尺度不變方差（scale-invariant variance）一樣。

想要了解更多詳細內容及相關學科知識，請點擊此處鏈接：http://www.datasciencecentral.com/profiles/blogs/my-data-science-machine-learning-and-related-articles。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！