本節內容：本節內容是根據上學期所上的模式識別課程的作業整理而來，第一道題目是Kmeans聚類算法，數據集是Iris(鳶尾花的數據集)，分類數k是3，數據維數是4。

關于聚類

    聚類算法是這樣的一種算法：給定樣本數據Sample，要求將樣本Sample中相似的數據聚到一類。有了這個認識之后，就應該了解了聚類算法要干什么了吧。說白了，就是歸類。
    首先，我們需要考慮的是，如何衡量數據之間的相似程度？比如說，有一群說不同語言的人，我們一般是根據他們的方言來聚類的（當然，你也可以指定以身高來聚類）。這里，語言的相似性（或者身高）就成了我們衡量相似的量度了。在考慮存在海量數據，如微博上各種用戶的關系網，如何根據用戶的關注和被關注來聚類，給用戶推薦他們感興趣的用戶？這就是聚類算法研究的內容之一了。
    Kmeans就是這樣的聚類算法中比較簡單的算法，給定數據樣本集Sample和應該劃分的類數K，對樣本數據Sample進行聚類，最終形成K個cluster，其相似的度量是某條數據i與中心點的”距離”(這里所說的距離，不止于二維)。

基本思想

KMeans算法的基本思想是初始隨機給定K個簇中心，按照最鄰近原則把待分類樣本點分到各個簇。然后按平均法重新計算各個簇的質心，從而確定新的簇心。一直迭代，直到簇心的移動距離小于某個給定的值。

基本步驟

K-Means聚類算法主要分為三個步驟：
1，初始化k個聚類中心。
2，計算出每個對象跟這k個中心的距離（相似度計算，這個下面會提到），假如x這個對象跟y這個中心的距離最小（相似度最大），那么x屬于y這個中心。這一步就可以得到初步的k個聚類 。
3，在第二步得到的每個聚類分別計算出新的聚類中心，和舊的中心比對，假如不相同，則繼續第2步，直到新舊兩個中心相同，說明聚類不可變，已經成功 。

復雜度分析

時間復雜度：O(tKmn)，其中，t為迭代次數，K為簇的數目，m為記錄數，n為維數
空間復雜度：O((m+K)n)，其中，K為簇的數目，m為記錄數，n為維數

初始質心的選擇

    選擇適當的初始質心是基本kmeans算法的關鍵步驟。常見的方法是隨機的選取初始質心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數據集和尋找的簇的個數。
     第二種有效的方法是，取一個樣本，并使用層次聚類技術對它聚類。從層次聚類中提取K個簇，并用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：