聚類算法
任務：将資料集中的樣本劃分成若幹個通常不相交的子集，對特征空間的一種劃分。
性能度量：類内相似度高，類間相似度低。兩大類：1.有參考标簽，外部名額；2.無參照，内部名額。
距離計算：非負性，同一性（與自身距離為0），對稱性，直遞性（三角不等式）。包括歐式距離（二範數），曼哈頓距離（一範數）等等。
1、KNN
k近鄰（KNN)是一種基本分類與回歸方法。
其思路如下：給一個訓練資料集和一個新的執行個體，在訓練資料集中找出與這個新執行個體最近的k 個訓練執行個體，然後統計最近的k 個訓練執行個體中所屬類别計數最多的那個類，就是新執行個體的類。其流程如下所示：
- 計算訓練樣本和測試樣本中每個樣本點的距離（常見的距離度量有歐式距離，馬氏距離等）；
- 對上面所有的距離值進行排序；
- 選前k 個最小距離的樣本；
- 根據這k 個樣本的标簽進行投票，得到最後的分類類别；
KNN的特殊情況是k =1 的情況，稱為最近鄰算法。對輸入的執行個體點（特征向量）x ，最近鄰法将訓練資料集中與x 最近鄰點的類作為其類别。
（1）一般k 會取一個較小的值，然後用過交叉驗證來确定；
（2）距離度量：一般是歐式距離（二範數），或者曼哈頓距離（一範數）
（3）回歸問題：取K個最近樣本的平均，或者使用權重平均。
算法的優點：（1）思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；（2）可用于非線性分類；（3）訓練時間複雜度為O(n)；（4）準确度高，對資料沒有假設，對outlier不敏感。
缺點：計算量大；樣本不平衡問題（即有些類别的樣本數量很多，而其它樣本的數量很少）；需要大量的記憶體；
需要考慮問題：（1）KNN的計算成本很高；（2）所有特征應該标準化數量級，否則數量級大的特征在計算距離上會有偏移；（3）在進行KNN前預處理資料，例如去除異常值，噪音等。
KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進行快速檢索（那KNN計算的時候不需要對全樣本進行距離的計算了）。KD樹更加适用于執行個體數量遠大于空間次元的KNN搜尋，如果執行個體的空間次元與執行個體個數差不多時，它的效率基于等于線性掃描。
2、K-Means
K-Means算法是無監督的聚類算法，它實作起來比較簡單，聚類效果也不錯，是以應用很廣泛。
基本思想：對于給定的樣本集，按照樣本之間的距離大小，将樣本集劃分為K個簇。讓簇内的點盡量緊密的連在一起，而讓簇間的距離盡量的大。
算法步驟：1.随機選擇k個樣本作為初始均值向量；2.計算樣本到各均值向量的距離，把它劃到距離最小的簇；3.計算新的均值向量；4.疊代，直至均值向量未更新或到達最大次數。
時間複雜度：O(tkmn)，其中，t為疊代次數，k為簇的數目，m為記錄數，n為維數；
空間複雜度：O((m+k)n)，其中，k為簇的數目，m為記錄數，n為維數。
優點：原理比較簡單，實作也是很容易，收斂速度快；聚類效果較優；算法的可解釋度比較強；主要需要調參的參數僅僅是簇數k。
缺點： 1、聚類中心的個數K 需要事先給定，這個 K 值的標明是非常難以估計的。很多時候，事先并不知道給定的資料集應該分成多少個類别才最合适；一般通過交叉驗證确定；
2、不同的初始聚類中心可能導緻完全不同的聚類結果。算法速度依賴于初始化的好壞，初始質點距離不能太近；
3、如果各隐含類别的資料不平衡，比如各隐含類别的資料量嚴重失衡，或者各隐含類别的方差不同，則聚類效果不佳；
4、該方法不适于發現非凸面形狀的簇或大小差别很大的簇，對于不是凸的資料集比較難收斂；
5、對噪音和異常點比較的敏感。
6、需樣本存在均值（限定資料種類）。
7、采用疊代方法，得到的結果隻是局部最優。
K-Means算法改進：
1、K-Means++算法就是對K-Means随機初始化質心的方法的優化。
K-Means++的對于初始化質心的優化政策也很簡單，如下：
a) 從輸入的資料點集合中随機選擇一個點作為第一個聚類中心
b) 對于資料集中的每一個點，計算它與已選擇的聚類中心中最近聚類中心的距離
c) 選擇一個新的資料點作為新的聚類中心，選擇的原則是：距離較大的點，被選取作為聚類中心的機率較大
d) 重複b和c直到選擇出k個聚類質心
e) 利用這k個質心來作為初始化質心去運作标準的K-Means算法。
2、二分-K均值是為了解決k-均值的使用者自定義輸入簇值k所延伸出來的自己判斷k數目，針對初始聚類中心選擇問題，其基本思路是：
為了得到k個簇，将所有點的集合分裂成兩個簇，從這些簇中選取一個繼續分裂，如此下去，直到産生k個簇。
具體描述：比如要分成5個組，第一次分裂産生2個組，然後從這2個組中選一個目标函數産生的誤差比較大的，分裂這個組産生2個，這樣加上開始那1個就有3個組了，然後再從這3個組裡選一個分裂，産生4個組，重複此過程，産生5個組。這算是一中基本求精的思想。
二分k均值不太受初始化的困擾，因為它執行了多次二分試驗并選取具有最小誤差的試驗結果，還因為每步隻有兩個質心。
3、大樣本優化Mini Batch K-Means
也就是用樣本集中的一部分的樣本來做傳統的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。當然此時的代價就是我們的聚類的精确度也會有一些降低。一般來說這個降低的幅度在可以接受的範圍之内。
在Mini Batch K-Means中，我們會選擇一個合适的批樣本大小batch size，我們僅僅用batch size個樣本來做K-Means聚類。那麼這batch size個樣本怎麼來的？一般是通過無放回的随機采樣得到的。為了增加算法的準确性，我們一般會多跑幾次Mini Batch K-Means算法，用得到不同的随機采樣集來得到聚類簇，選擇其中最優的聚類簇。
3、 層次聚類
步驟：1.先将資料集中的每個樣本看作一個初始聚類簇；2.找到距離最近的兩個聚類簇進行合并。
優點：無需目标函數，沒有局部極小問題或是選擇初始點的問題。缺點：計算代價大。
4、密度聚類
DBSCAN既可以适用于凸樣本集，也可以适用于非凸樣本集。找到幾個由密度可達關系導出的最大的密度相連樣本集合。即為我們最終聚類的一個類别，或者說一個簇。
基本思想：它任意選擇一個沒有類别的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接着繼續選擇另一個沒有類别的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運作到所有核心對象都有類别為止。
步驟：1、找到任意一個核心點，對該核心點進行擴充；2、擴充方法是尋找從該核心點出發的所有密度相連的資料點；3、周遊該核心的鄰域内所有核心點，尋找與這些資料點密度相連的點。
優點：不需要确定要劃分的聚類個數，聚類結果沒有偏倚；抗噪聲，在聚類的同時發現異常點，對資料集中的異常點不敏感；處理任意形狀和大小的簇，相對的，K-Means之類的聚類算法一般隻适用于凸資料集。
缺點：資料量大時記憶體消耗大，相比K-Means參數多一些；樣本集的密度不均勻、聚類間距差相差很大時，聚類品質較差，這時用DBSCAN聚類一般不适合；
那麼我們什麼時候需要用DBSCAN來聚類呢？一般來說，如果資料集是稠密的，并且資料集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。如果資料集不是稠密的，則不推薦用DBSCAN來聚類。
面試問題：
1、K-Means與KNN差別
2、Kmeans的k值如何确定？
（1）枚舉，由于kmeans一般作為資料預處理，是以k一般不會設定很大，可以通過枚舉，令k從2到一個固定的值，計算目前k的所有樣本的平均輪廓系數，最後選擇輪廓系數最接近于1對應的k作為最終的叢集數目；（2）資料先驗知識，或者對資料進行簡單的分析或可視化得到。
3、初始點選擇方法？
初始的聚類中心之間互相距離盡可能遠。（1）kmeans++,随機選擇一個，對每一個樣本計算到他的距離，距離越大的被選中聚類中心的機率也就越大，重複。（2）選用層次聚類進行出初始聚類，然後從k個類别中分别随機選取k個點。
4、kmeans不能處理哪種資料？
（1）非凸（non-convex）資料。可以用kernal k均值聚類解決。
（2）非數值型資料。Kmeans隻能處理數值型資料。可以用k-modes。初始化k個聚類中心，計算樣本之間相似性是根據兩個樣本之間所有屬性，如屬性不同則距離加1，相同則不加，是以距離越大，樣本的不相關性越大。更新聚類中心，使用一個類中每個屬性出現頻率最大的那個屬性值作為本類的聚類中心。
（3）噪聲和離群值的資料。可以用kmedoids（根據中值而不是均值）。
（4）不規則形狀（有些部分密度很大，有些很小），可以用密度聚類DBSCAN解決。
5、kmeans如何處理大資料，幾十億？
并行計算。MapReduce,假設有H個Mapper，把資料集分為H個子集，分布到H個Mapper上，初始化聚類中心，并同時廣播到H個Mapper上。
參考資料：http://www.cnblogs.com/pinard/p/6164214.html
http://www.cnblogs.com/pinard/p/6208966.html
https://blog.csdn.net/sinat_35512245/article/details/55051306
轉載于:https://www.cnblogs.com/eilearn/p/9046940.html
![9.spark Core 進階2--Cashe[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)