Can you summarize the following document?
        
  已知觀測集formula_2,其中每個觀測都是一個formula_3-維實向量,"k"-平均聚類要把這formula_1個觀測劃分到"k"個集合中(k≤n),使得組內平方和(WCSS within-cluster sum of squares)最小。換句話說,它的目標是找到使得下式滿足的聚類formula_5, formula_6 其中formula_7是formula_5中所有點的均值。

  雖然其思想能夠追溯到1957年的Hugo Steinhaus,術語“"k"-均值”於1967年才被James MacQueen 首次使用。標準演算法則是在1957年被Stuart Lloyd作為一種脈衝碼調製的技術所提出,但直到1982年才被貝爾實驗室公開出版 。在1965年,E.W.Forgy發表了本質上相同的方法,所以這一演算法有時被稱為Lloyd-Forgy方法。更高效的版本則被Hartigan and Wong提出(1975/1979)

  

  最常用的演算法使用了迭代優化的技術。它被稱為"k"-平均演算法而廣為使用,有時也被稱為Lloyd演算法(尤其在電腦科學領域)。已知初始的"k"個均值點formula_9,演算法的按照下面兩個步驟交替進行 因為這一平方和就是平方後的歐氏距離,所以很直觀地把觀測分配到離它最近的均值點即可 。(數學上,這意味依照由這些均值點生成的Voronoi圖來劃分上述觀測)。 formula_10 其中每個formula_11都只被分配到一個確定的聚類formula_12中,儘管在理論上它可能被分配到2個或者更多的聚類。 formula_13 因為算術平均是最小平方估計,所以這一步同樣減小了目標函式組內平方和(WCSS)的值。  這一演算法將在對於觀測的分配不再變化時收斂。由於交替進行的兩個步驟都會減小目標函式WCSS的值,並且分配方案只有有限種,所以演算法一定會收斂於某一(區域性)最優解。注意:使用這一演算法無法保證得到全域性最優解。  這一演算法經常被描述為“把觀測按照距離分配到最近的聚類”。標準演算法的目標函式是組內平方和(WCSS),而且按照“最小平方和”來分配觀測,確實是等價於按照最小歐氏距離來分配觀測的。如果使用不同的距離函式來代替(平方)歐氏距離,可能使得演算法無法收斂。然而,使用不同的距離函式,也能得到"k"-均值聚類的其他變體,如球體"k"-均值演算法和"k"-中心點演算法。

  通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法  。Forgy方法隨機地從資料集中選擇"k"個觀測作為初始的均值點;而隨機劃分方法則隨機地為每一觀測指定聚類,然後執行“更新(Update)”步驟,即計算隨機分配的各聚類的圖心,作為初始的均值點。Forgy方法易於使得初始均值點散開,隨機劃分方法則把均值點都放到靠近資料集中心的地方。參考Hamerly et al的文章 ,可知隨機劃分方法一般更適用於"k"-調和均值和模糊"k"-均值演算法。對於期望-最大化(EM)演算法和標準"k"-均值演算法,Forgy方法作為初始化方法的表現會更好一些。  這是一個啟發式演算法,無法保證收斂到全域性最優解,並且聚類的結果會依賴於初始的聚類。又因為演算法的執行速度通常很快,所以一般都以不同的起始狀態執行多次來得到更好的結果。不過,在最差的情況下,"k"-均值演算法會收斂地特別慢:尤其是已經證明了存在這一的點集(甚至在2維空間中),使得"k"-均值演算法收斂的時間達到指數級(formula_14)  。好在在現實中,這樣的點集幾乎不會出現:因為"k"-均值演算法的平滑執行時間是多項式時間的  注:把“分配”步驟視為“期望”步驟,把“更新”步驟視為“最大化步驟”,可以看到,這一演算法實際上是廣義期望-最大化演算法(GEM)的一個變體。

  在formula_3維空間中找到"k"-均值聚類問題的最優解的計算複雜度:  相比之下,Lloyds演算法的執行時間通常為formula_19,"k"和formula_3定義如上,formula_21為直到收斂時的迭代次數。如果資料本身就有一定的聚類結構,那麼收斂所需的迭代數目通常是很少的,並且進行少數迭代之後,再進行迭代的話,對於結果的改善效果很小。鑑於上述原因,Lloyds演算法在實踐中通常被認為幾乎是線性複雜度的。  下面有幾個關於這一演算法複雜度的近期研究:

  使得"k"-均值演算法效率很高的兩個關鍵特徵同時也被經常被視為它最大的缺陷:  "k"-均值演算法的一個重要的侷限性即在於它的聚類模型。這一模型的基本思想在於:得到相互分離的球狀聚類,在這些聚類中,均值點趨向收斂於聚類中心。 一般會希望得到的聚類大小大致相當,這樣把每個觀測都分配到離它最近的聚類中心(即均值點)就是比較正確的分配方案。  "k"-均值聚類的結果也能理解為由均值點生成的Voronoi cells。

  "k"-均值聚類(尤其是使用如Lloyd's演算法的啟發式方法的聚類)即使是在巨大的資料集上也非常容易部署實施。正因為如此,它在很多領域都得到的成功的應用,如市場劃分、機器視覺、 地質統計學、天文學和農業等。它經常作為其他演算法的預處理步驟,比如要找到一個初始設定。

  "k"-均值起源於訊號處理領域,並且現在也能在這一領域找到應用。例如在計算機圖形學中,色彩量化的任務,就是要把一張影象的色彩範圍減少到一個固定的數目"k"上來。"k"-均值演算法就能很容易地被用來處理這一任務,並得到不錯的結果。其它得向量量化的例子有非隨機抽樣,在這裡,為了進一步的分析,使用"k"-均值演算法能很容易的從大規模資料集中選出"k"個合適的不同觀測。

  在聚類分析中,"k"-均值演算法被用來將輸入資料劃分到"k"個部分(聚類)中。 然而,純粹的"k"-均值演算法並不是非常靈活,同樣地,在使用上有一定侷限(不過上面說到的向量量化,確實是一個理想的應用場景)。特別是,當沒有額外的限制條件時,引數"k"是很難選擇的(正如上面討論過的一樣)。演算法的另一個限制就是它不能和任意的距離函式一起使用、不能處理非數值資料。而正是為了滿足這些使用條件,許多其他的演算法才被發展起來。

  在(半)監督學習或無監督學習中,"k"-均值聚類被用來進行特徵學習(或字典學習)步驟。基本方法是,首先使用輸入資料訓練出一個"k"-均值聚類表示,然後把任意的輸入資料投射到這一新的特徵空間。 "k"-均值的這一應用能成功地與自然語言處理和計算機視覺中半監督學習的簡單線性分類器結合起來。在物件識別任務中,它能展現出與其他複雜特徵學習方法(如自動編碼器、受限Boltzmann機等)相當的效果。然而,相比複雜方法,它需要更多的資料來達到相同的效果,因為每個資料點都只貢獻了一個特徵(而不是多重特徵)。

  "k"-均值聚類,以及它與EM演算法的聯絡,是高斯混合模型的一個特例。很容易能把"k"-均值問題一般化為高斯混合模型。另一個"k"-均值演算法的推廣則是"k"-SVD演算法,後者把資料點視為“編碼本向量”的稀疏線性組合。而"k"-均值對應於使用單編碼本向量的特殊情形(其權重為1)。

  基本的Mean Shift聚類要維護一個與輸入資料集規模大小相同的資料點集。初始時,這一集合就是輸入集的副本。然後對於每一個點,用一定距離範圍內的所有點的均值來迭代地替換它。與之對比,"k"-均值把這樣的迭代更新限制在(通常比輸入資料集小得多的)K個點上,而更新這些點時,則利用了輸入集中與之相近的所有點的均值(亦即,在每個點的Voronoi劃分內)。還有一種與"k"-均值類似的Mean shift演算法,即 似然Mean shift,對於迭代變化的集合,用一定距離內在輸入集中所有點的均值來更新集合裡的點。Mean Shift聚類與"k"-均值聚類相比,有一個優點就是不用指定聚類數目,因為Mean shift傾向於找到儘可能少的聚類數目。然而,Mean shift會比"k"-均值慢得多,並且同樣需要選擇一個“寬度”引數。和"k"-均值一樣,Mean shift演算法有許多變體。

  有一些研究表明,"k"-均值的放鬆形式解(由聚類指示向量表示),可由主成分分析中的主成分給出,並且主成分分析由主方向張成的子空間與聚類圖心空間是等價的。不過,主成分分析是"k"-均值聚類的有效放鬆形式並不是一個新的結果(如,見),並且還有的研究結果直接揭示了關於“聚類圖心子空間是由主成分方向張成的”這一論述的反例

  有研究表明,在稀疏假設以及輸入資料經過白化的預處理後,"k"-均值得到的解就是獨立成分分析的解。這一結果對於解釋"k"-均值在特徵學習方面的成功應用很有幫助。

  "k"-均值演算法隱含地假設輸入資料的順序不影響結果。雙向過濾與"k"-均值演算法和Mean shift演算法類似之處在於它同樣維護著一個迭代更新的資料集(亦是被均值更新)。然而,雙向過濾限制了均值的計算只包含了在輸入資料中順序相近的點,這使得雙向過濾能夠被應用在影象去噪等資料點的空間安排是非常重要的問題中。

  目標函式是使得聚類平方誤差最小化的演算法還有"k"-中心點演算法,該方法保持聚類的中心在一個真實資料點上,亦即使用中心而非圖心作為均值點。
K-平均演算法(英文:"k"-means clustering)源於訊號處理中的一種向量量化方法,現在則更多地作為一種聚類分析方法流行於資料探勘領域。"k"-平均聚類的目的是:把formula_1個點(可以是樣本的一次觀察或一個例項)劃分到"k"個聚類中,使得每個點都屬於離他最近的均值(此即聚類中心)對應的聚類,以之作為聚類的標準。這個問題將歸結為一個把資料空間劃分為Voronoi cells的問題。