K-means聚類演算法如何應對數據的噪音和離散特徵處理的問題？

本人剛接觸機器學習，現重點在研究KMeans聚類演算法，有如下問題始終沒想明白，忘大神指點一下，謝謝。

我理解的KMeans演算法判斷異常數據的過程如下:

首先KMeans演算法將訓練數據分成多個簇，並將每一個簇中，離簇心最遠的樣本與簇心的距離作為該簇的一個閾值。

當新測試數據來後，模型將其劃歸到某一個簇，通過判斷測試數據離該簇心的距離是否大於閾值來判斷該測試數據是否異常。

如果以上我理解是正確的話有如下問題:

問題一:該演算法要求訓練數據中都是正向數據，如果訓練數據中包含了異常數據，會導致閾值的值過大，從而異常測試數據進來時可能會漏報。

現實中我們很難保證訓練數據中沒有異常數據，那在訓練過程中有沒有什麼方法可以減少異常數據對訓練結果的干擾？(例如可視化後肉眼識別一些離群的數據點，並把它們從樣本中去除？或者按比例縮小閾值？)

問題二:在特徵提取過程中對於一些離散值，我們會採用獨熱編碼將其轉換為一個固定長度的向量，這個長度是根據數據集中該欄位的所有值計算出來的(不同的值個數)。

例如有個特徵叫部門，樣本數據里有研發、測試、HR三種值，獨熱編碼後就會轉換為一個3維的向量，［100］［010］［001］，這是遍歷了整個樣本集後得出的向量長度。如果新來了一條測試數據，部門為研發，我怎麼根據這一條數據將研發這個特徵值轉換為［100］向量，從而保證訓練和測試的特徵數據維度一致。如果測試數據的部門值為財務，財務這個值不在訓練集中，這種情況又怎麼處理呢？

不請自來:)

先回答你的問題，再順道談談以K-means為原型的幾種針對不同數據類型的聚類演算法。

問題一:該演算法要求訓練數據中都是正向數據，如果訓練數據中包含了異常數據，會導致閾值的值過大，從而異常測試數據進來時可能會漏報。 現實中我們很難保證訓練數據中沒有異常數據，那在訓練過程中有沒有什麼方法可以減少異常數據對訓練結果的干擾？(例如可視化後肉眼識別一些離群的數據點，並把它們從樣本中去除？或者按比例縮小閾值？)

我的看法：聚類本身就是最常用的異常值檢測方法，大部分非監督的異常值檢測都依靠聚類。離群值（異常值）對非監督聚類的影響很明顯，因為需要一邊學習簇的特徵，一邊防止異常值的干擾。

並不是每一種聚類都擅長異常值檢測：K-means和層次聚類（hierarchical clustering）對離群值非常敏感，因為其要求將每個點都劃分到一個簇中(此處我們默認的K-means是hard assignment)。而且其相似度度量(Similarity Measure)默認是sum of euclidean squares，優化目標是將簇內差異最小化(minimize with-in clustering variation)，因此即使單個噪音點也可以對整個簇造成很大的擾動。 常見的解決方法有：

1. 改用密度聚類(Density based clustering)。這樣可以同時優化簇內的緊密度(最小化inter-cluster density)和簇之間的離散度(最大化intra-cluster density)。此時的目標函數 ，超過一定閾值的點可以被標記為異常值。
2. 使用混合模型（Finite Mixture Models）或者Soft K-means。人民群眾喜聞樂見的演算法包括高斯混合模型 (Gaussian Mixture Models)，從本質上說Soft K-means是一種高斯混合模型的特例。
3. 也可以通過對K-means的聚類結果做統計測試，設定p-value來決定聚類結果是否顯著，同時通過這個方法來去除每個簇中的異常值。然而這個方法有局限性，因為它的假設前提是當前的聚類結果是正確的，而你去除的異常值可能別的簇中的正常值。

問題二:在特徵提取過程中對於一些離散值，我們會採用獨熱編碼將其轉換為一個固定長度的向量，這個長度是根據數據集中該欄位的所有值計算出來的(不同的值個數)。

例如有個特徵叫部門，樣本數據里有研發、測試、HR三種值，獨熱編碼後就會轉換為一個3維的向量，［100］［010］［001］，這是遍歷了整個樣本集後得出的向量長度。如果新來了一條測試數據，部門為研發，我怎麼根據這一條數據將研發這個特徵值轉換為［100］向量，從而保證訓練和測試的特徵數據維度一致。如果測試數據的部門值為財務，財務這個值不在訓練集中，這種情況又怎麼處理呢？

我的看法：聚類問題中的特徵工程不單純是將離散變數轉化為連續變數這麼簡單，獨熱編碼要慎用。特徵轉化中包含了多種假設需要考慮，至少要確保在轉化過程中不丟失信息。

本題中你直接轉化為獨熱編碼就不是一個很好的方法，原因就是...先不談聚類中的距離（distance）在高維度中會喪失意義，只說任意兩點在「部門」這個維度上的幾何距離都是 ，因此相當於你人為的損失了信息。假設我有A,B,C三個點分別是[100],[010],[001]，那麼單純看幾何距離，我只能知道如果兩點相同應該為0，如果不同距離應該為 。但你並不知道這兩個點是A和B，還是B和C。在未轉換前我們有這個信息，但你轉換為我們無法再區分，因此這就是信息損失。為什麼獨熱編碼在這裡不再好用？因為我們使用了距離度量，也就是最終我們將一堆距離相加，而不是像決策樹那樣分開對待。

----------------------------------------------------------------------

一般我們在做聚類前做變數處理的方法如下：

1. 如果一個變數/特徵是連續實數，那麼大部分時候我們不做特別的處理。在特定的情況下，我們會做standardization或者normalization。
2. 如果是離散變數，一般分兩種：
1. 有序變數。比如小學，初中，高中，大學。又比如非常滿意，滿意，不滿意，極不滿意。這類變數中的可取值之間都有一種順序關係，因此不能單純的用 One-hot Encoding，也就是題主提到的獨熱編碼來轉化，因為在轉化過程中會失去一部分有用的信息。在這種情況下可以由來轉換 N代表該變數可取的值得總數。此處也要注意，不是每種順序都是有意義的。比如假設一個變數可以取三個值：「頭等艙」，「商務艙」，「經濟艙」，對於票價而言是有順序的，但對於到達時間，這三者是無序的（請不要非說頭等艙可以先下飛機....蟹蟹）
2. 無序變數。如題主描述的研發，測試，HR，我們一般希望度量其差異性，比較常見的是像@呼廣躍 提到的Value Difference Metrics (VDM)這一類。說白了就是直接看兩個點的這個維度是否相同，若有N個無序變數，我們一般構建一個 的矩陣來描述差異度（Degree of Difference）。
3. 對連續變數和離散變數都經過處理以後，就需要將各個變數合併來生成目標函數。在做這件事情前，有幾點需要考慮：
1. 是否每個變數的重要性都一樣，即是否權重相同。假設有N個變數， 。雖然我們一般默認相等的 可以保證每個變數對聚類的影響相同，但這假設不嚴謹。舉例，若聚類中有兩個變數，其中變數1在所有數據點中取值都相同，即使你使得 ，其對於聚類的貢獻值依然為0。不過在大部分時候，可以簡單粗暴的使用等權重。別忘了，我們還有調參工程...
2. 此時我們定義新的目標函數為 。C為連續變數的度量函數，如Euclidean Distance Square。而D為離散變數的度量函數，如Value Difference Metrics。還可以再在函數C和D中分別定義不同的變數權重，甚至在O中給C和D不同的權重。這些權重取決於我們對任務的了解，若一切未知可不賦值。

說了這麼多，有沒有簡單一些，不需要整這麼多花樣的的方法...？

答案是，還真有，在你了解問題的前提下可以愉快的掉包！我個人比較推薦的方法叫做 K-prototypes[1]，該方法就是一個基於K-means比較完整的處理混合數據類型（連續+離散）的演算法，基本的思路和我上面描述的是一樣的：）

所以基於K-means這種思路的演算法：

1. 處理連續變數的有K-means和K-means++[2]
2. 處理categorical變數的有K-modes[3]
3. 處理混合變數的有K-prototypes

K-means和K-means++在python機器學習庫sklearn中都有實現，K-modes和K-prototypes在GitHub和pipy上都有現成的庫（https://pypi.python.org/pypi/kmodes/）

不多說了，我去繼續煉丹了（滑稽）...(?????)

#知乎的公式編輯器簡直反人類#

---------------------------------------------------------------------------------------------------------

[1] Huang, Zhexue. "Extensions to the k-means algorithm for clustering large data sets with categorical values." Data mining and knowledge discovery 2.3 (1998): 283-304.

[2] Arthur, David, and Sergei Vassilvitskii. "k-means++: The advantages of careful seeding." Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2007.

[3] Huang, Zhexue, and Michael K. Ng. "A fuzzy k-modes algorithm for clustering categorical data." IEEE Transactions on Fuzzy Systems 7.4 (1999): 446-452.

謝邀。

關於離散特徵處理的問題，有一種方法叫VDM（value difference Metric），周志華老師《機器學習》書中第200頁有詳細介紹。也可自己去google，我這裡就不再贅述了。

中文名詞很多看不懂。 kmean是unsupervised learning. 所以overfit issue 大， 加variance 大，加穩定性不足。 和最初選origin 和k 的關聯都很大。 適合對training set 有 100%信心的,而且empirical distribution 掛不上套路的非線性 prediction。 一般用來初選可以，但最後model selection, 因為power太低，往往會被淘汰。