K-means的缺點（優化不僅僅是最小化誤差）

?#轉載時，請注明英文原作David Robinson，譯者Ding Chao。#

我最近遇到一個交叉驗證的問題，我認為這個給我提供了一個很好的機會去用“R”和“ggplot2”探索下K-means算法的一些基本假設。

K-means方法廣泛用于聚類分析。可是在我看來，這個算法不需要任何假設啊，也就是說，給我一個數據集和一個預先指定的聚類數目k，然后我就可以應用這個算法去最小化SSE（誤差平方和）就行了嘛。

恩。。所以K-means本質上是一個優化問題。

我閱讀了一些關于K-means缺點的材料，他們大多指出如下幾點：

• K-means每個屬性（變量）的分布方差是球形的。
• 所有的變量有同樣的方差。
• 對于所有的的聚類來說先驗概率相等，也就是說，每一類有大致相等的觀測數量。如果以上3個任何一個被觸犯K-means就會失效。

我不太能理解這些觀點后面的邏輯。我認為K-means本質上是不該有假設的，它就最小化SSE而已，一下子還真看不出來最小化SSE和這3條有什么聯系。

我們將考慮假設中的兩個，我們來看看如果這個假設被打破這個算法會怎么樣。我們貼上2維數據，因為這個更直觀些。（感謝“curse of dimensionality”, 增加額外的維度會讓這個問題變得更嚴重）。我們將用統計語言R，全代碼在這里

分歧前奏：安斯庫姆四重奏

首先，來個類似的。想象有人討論下面這個：

我讀了一些關于線性回歸缺點的材料。但是所有的線性回歸都是在做基于預測（曲）線的SSE最小化問題。這是一個優化問題，不關乎曲線的形狀或者殘差值分布。因此，線性回歸不需要假設。

嗯，是的，線性回歸的工作原理是減少殘差平方的總和。但是，這本身并不是回歸的目標：我們所試圖做的是畫一條線，一個可靠的、無偏置的Y-X預測線。高斯 – 馬爾科夫定理告訴我們，盡量減少SSE就會達到目標 – 但這定理依賴于一些非常具體的假設。如果這些假設被打破，你仍然可以最小化SSE ，但它可能無任何效果。因為你可以試想一下，比如說說：“你腳推踏板開車。該踏板一直可以被推，不管有多少汽油在汽油罐里。因此，即使油箱是空的，你仍然可以推踏板，駕駛汽車“ 。

但是，說起來很輕松。讓我們來看看這冰冷的數據。實際上就是人工數據.

?

這是我最喜歡的人造數據：安斯庫姆四重奏。于1973年由統計學家Francis Anscombe提出。這個能證明盲目相信統計學方法是多么愚蠢的。每個數據集有同樣的回歸斜率、截距、p-值 和 $R^2$-而且可以瞟一下發現，里面只有?I?對于線性回歸來說是正確的。在?II?它表現出了錯誤的形狀, 在?III?它因為一個離群點彎了形狀，在?IV?壓根就沒有恰當的趨勢！

有人會說，“線性回歸在這些例子里依舊有效果，因為它在最小化殘差值的平方和“。多無聊。。線性回歸做了一個線，但是沒意義，有啥用？

所以，我們可以發現一個常理的優化可以被執行但是并不意味著達到了預先的目標。

如果打破第一個假設：非球面數據

你說k-means算法在非球面聚類上表現的很好？非球面聚類。。像這樣？

?

也許這不是你期待樣子，但它構建地完全合理。看著這個圖像，我們人類一眼就認出兩個群集。因此，讓我們來看看K-means做的咋樣：分配不同顏色：

你可能會說：“這不是一個公平的例子…沒有聚類方法能正確找到這樣怪異的cluster。 ”事實并非如此！嘗試下single linkagehierachical clustering：

看到了吧！這是因為single-linkage hierarchical clustering對這個數據集做了正確的假設。 （在很多其他的情形下他會失敗） 。

你可能會說：“這是一個單一的、極端的、病態的情況。 ” No！例如，可以使外組半圓，而不是一個圈，你會看到k均值仍然如此可怕的（hierarchical clustering仍然做得很好） 。我能想到很多其他情況下，不僅僅是二維的情況。當你集群是16維數據，有各種可能出現的病癥。

最后，我要指出， K-means仍然是可用的 ！如果您將您的數據轉化為極坐標，聚類會有效哦：

這就是為什么了解基本方法的假設是至關重要的：它不只是告訴你什么時候的方法也有缺點，它會告訴你如何解決這些問題。

?大小不均勻的集群

如果群集有不太均勻的分部，也能打破K-means聚類？好了，可以考慮這套集群，大小20 ， 100 ， 500。我從多元高斯函數生成的每個集：

這看起來像K-means或許可以找到這些集群，對不對？所以讓我們試試K-means：

哎喲！這里發生的事情是有點微妙。在尋求最大限度地減少內集平方和， K-means算法提供了更多的“權重”給較大的集群。在實踐中，要么小群遠離任何中心，否則大群就像黑洞，會更多的吞噬小群成員。

如果你試試看這些例子，你會看到，你可以構建k-means構建的一些更感概的場景。

結論：世上沒有免費的午餐

對不同的案例下的算法，我可以建造一些讓這些算法失效的情形。線性回歸假定你的數據沿著直線 – 但如果它遵循一個正弦波呢？ t檢驗假設每個樣本來自正態分布：如果你異常拋出個離群值呢？任何梯度上升算法可以得到被困在局部最大值，而任何監督分類可以被過度擬合。

這是什么意思？這意味著，”假設“是你力量的來源！當Netflix推薦給你電影，它是在假設，如果你喜歡一部電影，你會喜歡那些相似的（反之亦然）。難道可以認為：“他只要在最小化誤差，算法仍然是有效的”？如果不對用戶的口味做出合理的假設，你就不能做出推薦。所以，你也不能用好任何算法在你沒有對你的集合數據做出自然假設。

所以，有時候不要只是知道這些缺點。你要認識他們，這樣他們就可以告知你如何選擇算法。了解他們，你可以知道如何調整你的算法，并且如何轉換數據來解決這些問題。

英語原文：http://varianceexplained.org/r/kmeans-free-lunch/

翻譯：Ding Chao.

轉載于:https://www.cnblogs.com/yymn/p/4534209.html

總結

以上是生活随笔為你收集整理的K-means的缺点（优化不仅仅是最小化误差）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。