前段時間老師給我的任務是讓我使用MapReduces和Spark分別實現K-means算法來比較MapReduces和Spark。首先問題是K-means算法是什么？ K-means算法的中心思想其實就是迭代，通過不斷的迭代，使聚類效果達到局部最優，為什么我們說局部最優呢？因為K-means算法的

前段時間老師給我的任務是讓我使用MapReduces和Spark分別實現K-means算法來比較MapReduces和Spark。首先問題是K-means算法是什么？

K-means算法的中心思想其實就是迭代，通過不斷的迭代，使聚類效果達到局部最優，為什么我們說局部最優呢？因為K-means算法的效果的優劣性和最初選取的中心點是有莫大關系的，我們只能在初始中心點的基礎上達到局部最優解。K-means算法是基于距離的聚類算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度越大。該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。我感覺總的來說就是物以類聚。

對于聚類問題，我們事先并不知道給定的一個訓練數集到底有哪些類別（即沒有指定類標簽），而是根據需要設置指定個數類標簽的數量（但不知道具體的類標簽是什么），然后通過K-means算法將具有相同特征，或者基于一定規則認為某一些對象相似，與其它一些組明顯的不同的數據聚集到一起，自然形成分組。之后，我們可以根據每一組的數據的特點，給定一個合適的類標簽（當然，可能給出類標簽對實際應用沒有實際意思，例如可能我們就想看一下聚類得到的各個數據集的相似性）。

在這里我們首先說明一個概念：質心（Centroid）。質心可以認為就是一個樣本點，或者可以認為是數據集中的一個數據點P，它是具有相似性的一組數據的中心，即該組中每個數據點到P的距離都比到其它質心的距離近（與其它質心相似性比較低）。

K個初始類聚類質心的選取對聚類結果具有較大的影響，因為在該算法第一步中是隨機的選取任意k個對象作為初始聚類的質心，初始地代表一個聚類結果，當然這個結果一般情況不是合理的，只是隨便地將數據集進行了一次隨機的劃分，具體進行修正這個質心還需要進行多輪的計算，來進一步步逼近我們期望的聚類結果：具有相似性的對象聚集到一個組中，它們都具有共同的一個質心。另外，因為初始質心選擇的隨機性，可能未必使最終的結果達到我們的期望，所以我們可以多次迭代，每次迭代都重新隨機得到初始質心，直到最終的聚類結果能夠滿足我們的期望為止。

1. 首先輸入k的值，即我們希望將數據集D = {P1, P2, …, Pn}經過聚類得到k個分類（分組）。

2. 從數據集D中隨機選擇k個數據點作為質心，質心集合定義為：Centroid = {Cp1, Cp2, …, Cpk}，排除質心以后數據集O={O1, O2, …, Om}。

3. 對集合O中每一個數據點Oi，計算Oi與Cpj(j=1, 2, …,k)的距離，得到一組距離Si={si1, si2, …, sik}，計算Si中距離最小值，則該該數據點Oi就屬于該最小距離值對應的質心。
4. 每個數據點Oi都已經屬于其中一個質心，然后根據每個質心所包含的數據點的集合，重新計算得到一個新的質心。

5. 如果新計算的質心和原來的質心之間的距離達到某一個設置的閾值（表示重新計算的質心的位置變化不大，趨于穩定，或者說收斂），可以認為我們進行的聚類已經達到期望的結果，算法終止。

6. 如果新質心和原來之心距離變化很大，需要迭代2~5步驟。

這是之前整理的一份，剛剛翻出來，現在貼出來，以便之后查看。

原文地址：形象理解K-Means算法, 感謝原作者分享。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com