什麼是聚類？
本次分享聚類中最常用的方法，K-means
所謂聚類，就是将對象，按照某種屬性進行劃分，使得同種類别之間有較高相似性，不同類别有較大區分。
在機器學習領域，屬于無監督模型，像之前的線性回歸，邏輯回歸，決策樹均是有監督學習，聚類是無監督學習，隻要根據有沒有目标作為參照學習就可以區分。
是以聚類算法，若要達到我們想要的目的，特征的選擇及相似性的度量标準，将是十分重要，也是十分考究功底的。
常用距離公式
我們用距離公式衡量相似性，常用的距離公式包括：闵科夫斯基距離(Minkowski distance)、餘弦距離(Cosine Similarity)、馬氏距離(Mahalanobis Distance)、KL散度(KL divergence)
1.闵科夫斯基距離(Minkowski distance)
當p=1時，闵科夫斯基距離即曼哈頓距離(Manhattan distance)
當p=2時，闵科夫斯基距離即歐式距離(Euclidean distance)
當p→∞時，闵科夫斯基距離即切比雪夫距離(Chebyshev Distance)
2.餘弦距離(Cosine Similarity)
利用闵可夫斯基度量對高維資料進行聚類通常是無效的，因為樣本之間的距離随着維數的增加而增加。餘弦距離測量兩個矢量之間的夾角，而不是兩個矢量之間的幅值差。它适用于高維資料聚類時相似度測量。
3.馬氏距離(Mahalanobis Distance)
馬氏距離，即資料的協方差距離，于歐式距離不同的是它考慮到各屬性之間的聯系，如考慮性别資訊時會帶來一條關于身高的資訊，因為二者有一定的關聯度，而且獨立于測量尺度。
當其中Σ是資料集x,y的協方差矩陣。馬氏距離在非奇異變換下是不變的，可用來檢測異常值需要注意的是：馬氏距離是建立在總體樣本的基礎上的，這一點可以從上述協方差矩陣的解釋中可以得出，也就是說，如果拿同樣的兩個樣本，放入兩個不同的總體中，最後計算得出的兩個樣本間的馬氏距離通常是不相同的，除非這兩個總體的協方差矩陣碰巧相同；其次要求總體樣本的協方差矩陣存在。
4.KL散度(KL divergence)
KL散度又稱為相對熵，它是描述對随機變量X的兩個機率分布PP和QQ差别的非對稱性度量，它不滿足距離基本性質中的對稱性和直遞性。特别的，在資訊論中，DKL(P(x)||Q(x))DKL(P(x)||Q(x))表示當機率分布Q(x)Q(x)來拟合真實分布P(x)P(x)時，産生的資訊損耗。
連續形式如下：
什麼是K-means？
不說那些複雜的概念，看下面的步驟，按着步驟，更新聚類中心，等聚類穩定之後，結果既所求：
步驟如下：
1.确定類k的數量；
2.随機選擇k個點，作為初始聚類中心；
3.計算每個樣本到k個點分别的距離；
4.将每個樣本分給最近的聚類中心點；
5.将樣本分好後，重新計算每個類的中心點；
6.重複2~5，直到樣本聚類結果沒有變化，則停止聚類；
K-means優點
1.是解決聚類問題的一種經典算法，簡單、快速
2.對處理大資料集，該算法保持可伸縮性和高效性
3.當簇接近高斯分布時，它的效果較好。
K-means缺點
在簇的平均值可被定義的情況下才能使用，可能不适用于某些應用；
在 K-means 算法中 K 是事先給定的，這個 K 值的標明是非常難以估計的。很多時候，事先并不知道給定的資料集應該分成多少個類别才最合适；
在 K-means 算法中，首先需要根據初始聚類中心來确定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果(可能會陷入死循環)；
該算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，是以當資料量非常大時，算法的時間開銷是非常大的；
若簇中含有異常點，将導緻均值偏離嚴重(即:對噪聲和孤立點資料敏感)；
不适用于發現非凸形狀的簇或者大小差别很大的簇。
如何選擇最佳K值？
聚類有一個評估方法最為常用，叫輪廓系數結合了凝聚度和分離度，其計算步驟如下：
對于第 i 個對象，計算它到所屬簇中所有其他對象的平均距離，記 ai (展現凝聚度)
對于第 i 個對象和不包含該對象的任意簇，計算該對象到給定簇中所有對象的平均距離，記 bi (展現分離度)
第 i 個對象的輪廓系數為 si = (bi-ai)/max(ai, bi)
從上面可以看出，輪廓系數取值為[-1, 1]，其值越大越好，且當值為負時，表明 ai
将每個樣本的輪廓系數求和取平均，即可獲得對應k的輪廓系數，選擇輪廓系數最高的k為最佳K值
如何優化k-means？
1. 确定類k的數量；
2.随機選擇k個點，作為初始聚類中心；(選擇機率較大的k個點可以提高疊代速度，後續有空專題分享)
3.計算每個樣本到k個點分别的距離(選擇合适的距離度量标準)；
4.将每個樣本分給最近的聚類中心點(一般用各個點的均值作為類中心點，但是可以通過權重平均，衆數等不同的方法獲得不一樣的聚類中心點)；
5.将樣本分好後，重新計算每個類的中心點；
6.重複2~5，直到樣本聚類結果沒有變化，則停止聚類；