A. 常見的幾種聚類方法
作為無監督學習的一個重要方法，聚類的思想就是把屬性相似的樣本歸到一類。對於每一個數據點，我們可以把它歸到一個特定的類，同時每個類之間的所有數據點在某種程度上有著共性，比如空間位置接近等特性。多用於數據挖掘、數據分析等一些領域。
下面簡單介紹一下幾種比較常見的聚類演算法。
K-means聚類方法大家應該都聽說過，在各種機器學習書籍教程中也是無監督學習部分非常經典的例子。其核心主要為兩個部分：其一是K，K在這里代表著類的數目，我們要把數據聚為多少類。其二是means，表示在每一次計算聚類中心的時候採取的是計算平均值。
我們假設樣本總數為n，K-means聚類法可以簡單表示為一下幾個步驟：
1. 在樣本中隨機選取K個點，作為每一類的中心點。
2. 計算剩下 n-K 個樣本點到每個聚類中心的距離（距離有很多種，假設這里採用歐式距離）。對於每一個樣本點，將它歸到和他距離最近的聚類中心所屬的類。
3. 重新計算每個聚類中心的位置：步驟 2 中得到的結果是 n 個點都有自己所屬的類，將每一個類內的所有點取平均值（這里假設是二維空間，即對 x 和 y 坐標分別取平均），計算出新的聚類中心。
4. 重復步驟 2 和 3 的操作，直到所有的聚類中心不再改變。
分析一下，演算法本身的思想並不難。但是K值如何選擇就見仁見智了，這里可以引入類內距離 J，每一類都會對應一個 J 值，其計算就是把類內所有點之間的距離累加起來。我們肯定希望 J 越小越好，因為小的類內間距代表這一類樣本的相似程度更高（離得更近）。
如果 K 很小，則聚類可能不徹底，即隔著很遠的兩波點也被聚為一類，會使 J 變得很大；相反的，過大的 K 雖然會降低類內間距 J ，但有時候分得過細會對數據的泛化性造成損害，沒有必要弄這么多類。因此 K 的選擇應該是具體問題具體分析。
還有一個問題就是初始聚類中心的選擇。不當的初始化會給演算法的收斂帶來更多的計算開銷。試想一下，如果一開始把離得很近的 K 個點都設為聚類中心，那麼演算法的迭代次數會更多一些。
HAC也是一種比較經典的聚類方法，其主要思想是先把每一個樣本點歸為一類，再通過計算類間的距離，來對最相似或者距離最近的類進行歸並，合成位一個新的類。反復循環，直到滿足特定的迭代條件即可。
HAC的核心思想主要分為如下幾個步驟：
1. 將每個樣本點都視作一類，一共有n個類。
2. 計算所有類之間兩兩的類間距離（類間距離計算方式多種多樣，可以取最近、最遠、找重心等等，這里不做詳述），然後把距離最近的兩個類進行合並，組成一個新的更大的類。
3. 重復步驟 2 中的操作，直到達到特定的迭代條件（例如當前類的數目是初始時的 10% ，即 90% 的類都得到了合並；最小的類間距離大於預先設定的閾值等等），演算法結束。
和K-means演算法中的 K 值選取一樣，HAC中如何選擇迭代的終止條件也是一個比較復雜的問題，需要根據一定的經驗，並且具體問題具體分析。
這種方法的核心思想是先計算出聚類中心，再把所有的樣本點按照就近原則，歸到離自身最近的聚類中心所對應的類。最大最小是指在所有的最小距離中選取最大的。其主要的演算法步驟如下：
1. 隨機選擇一個點，作為第一個類的聚類中心 Z1。
2. 選擇與步驟 1 中距離最遠的樣本點，作為第二個類的聚類中心 Z2。
3. 逐個計算每個點到所有聚類中心的距離，並把所有的最短的距離記錄下來。
4. 在這些最短距離中挑選最大的值，如果這個最大值大於 ，其中 ,那麼將這個最大距離所對應的另一個樣本點作為新的聚類中心；否則整個演算法結束。
5. 重復步驟 3 和 4 的操作，直到 4 中不再出現新的聚類中心。
6. 將所有的樣本歸到與他自身最近的聚類中心。
參考：
https://www.jianshu.com/p/4f032dccdcef
https://www.jianshu.com/p/bbac132b15a5
https://blog.csdn.net/u011511601/article/details/81951939
B. 分類和聚類的區別及各自的常見演算法
1、分類和聚類的區別：
Classification (分類)，對於一個classifier，通常需要你告訴它「這個東西被分為某某類」這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行「學習」，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)，
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常並不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類，簡單來說，就是根據文本的特徵或屬性，劃分到已有的類別中。如在自然語言處理NLP中，我們經常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括：決策樹分類法，樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網路法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然，除此之外，還有很多諸如屬於劃分法K中心點（K-MEDOIDS）演算法、CLARANS演算法；屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等；基於密度的方法：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；基於網格的方法：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；基於模型的方法)。
C. 八：聚類演算法K-means（20191223-29)
學習內容：無監督聚類演算法K-Means
k-means：模型原理、收斂過程、超參數的選擇
聚類分析是在數據中發現數據對象之間的關系，將數據進行分組，組內的相似性越大，組間的差別越大，則聚類效果越好。
不同的簇類型： 聚類旨在發現有用的對象簇，在現實中我們用到很多的簇的類型，使用不同的簇類型劃分數據的結果是不同的。
基於原型的： 簇是對象的集合，其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近，如(b)所示的原型即為中心點，在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ，最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。
基於密度的 ：簇是對象的密度區域，(d)所示的是基於密度的簇，當簇不規則或相互盤繞，並且有早上和離群點事，常常使用基於密度的簇定義。
關於更多的簇介紹參考《數據挖掘導論》。
基本的聚類分析演算法
1. K均值： 基於原型的、劃分的距離技術，它試圖發現用戶指定個數(K)的簇。
2. 凝聚的層次距離： 思想是開始時，每個點都作為一個單點簇，然後，重復的合並兩個最靠近的簇，直到嘗試單個、包含所有點的簇。
3. DBSCAN: 一種基於密度的劃分距離的演算法，簇的個數有演算法自動的確定，低密度中的點被視為雜訊而忽略，因此其不產生完全聚類。
不同的距離量度會對距離的結果產生影響，常見的距離量度如下所示：
優點：易於實現
缺點：可能收斂於局部最小值，在大規模數據收斂慢
演算法思想：
選擇K個點作為初始質心
repeat
將每個點指派到最近的質心，形成K個簇
重新計算每個簇的質心
until 簇不發生變化或達到最大迭代次數
這里的「重新計算每個簇的質心」，是根據目標函數來計算的，因此在開始時要考慮 距離度量和目標函數。
考慮歐幾里得距離的數據，使用 誤差平方和（Sum of the Squared Error,SSE） 作為聚類的目標函數，兩次運行K均值產生的兩個不同的簇集，使用SSE最小的那個。
k表示k個聚類中心，ci表示第幾個中心，dist表示的是歐幾里得距離。
這里有一個問題就是為什麼，我們更新質心是讓所有的點的平均值，這里就是SSE所決定的。
k均值演算法非常簡單且使用廣泛，但是其有主要的兩個缺陷：
1. K值需要預先給定 ，屬於預先知識，很多情況下K值的估計是非常困難的，對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景，可以進行迭代運算，然後找出Cost Function最小時所對應的K值，這個值往往能較好的描述有多少個簇類。
2. K-Means演算法對初始選取的聚類中心點是敏感的 ，不同的隨機種子點得到的聚類結果完全不同
3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇，銀冠指定足夠大的簇的個數是他通常可以發現純子簇。
4. 對離群點的數據進行聚類時，K均值也有問題 ，這種情況下，離群點檢測和刪除有很大的幫助。
下面對初始質心的選擇進行討論：
當初始質心是隨機的進行初始化的時候，K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕，可能只能得到局部的最優解，而無法得到全局的最優解。
多次運行，每次使用一組不同的隨機初始質心，然後選擇一個具有最小的SSE的簇集。該策略非常的簡單，但是效果可能不是很好，這取決於數據集合尋找的簇的個數。
關於更多，參考《數據挖掘導論》
為了克服K-Means演算法收斂於局部最小值的問題，提出了一種 二分K-均值(bisecting K-means)
將所有的點看成是一個簇
當簇小於數目k時
對於每一個簇
計算總誤差
在給定的簇上進行K-均值聚類,k值為2 計算將該簇劃分成兩個簇後總誤差
選擇是的誤差最小的那個簇進行劃分
在原始的K-means演算法中，每一次的劃分所有的樣本都要參與運算，如果數據量非常大的話，這個時間是非常高的，因此有了一種分批處理的改進演算法。
使用Mini Batch（分批處理）的方法對數據點之間的距離進行計算。
Mini Batch的好處：不必使用所有的數據樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少，所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。
聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集，每個子集成為一個「簇」。通過這樣的劃分，每個簇可能對應於一些潛在的概念（也就是類別）；需說明的是，這些概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇對應的概念語義由使用者來把握和命名。
聚類是無監督的學習演算法，分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集（也就是說提前知道訓練集里的數據屬於哪個類別），機器學習演算法在訓練集上學習到相應的參數，構建模型，然後應用到測試集上。而聚類演算法是沒有標簽的，聚類的時候，需要實現的目標只是把相似的東西聚到一起。
聚類的目的是把相似的樣本聚到一起，而將不相似的樣本分開，類似於「物以類聚」，很直觀的想法是同一個簇中的相似度要盡可能高，而簇與簇之間的相似度要盡可能的低。
性能度量大概可分為兩類： 一是外部指標， 二是內部指標 。
外部指標：將聚類結果和某個「參考模型」進行比較。
內部指標：不利用任何參考模型，直接考察聚類結果。
對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大
初學者會很容易就把K-Means和KNN搞混，其實兩者的差別還是很大的。
K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。
當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。
優點：
簡單， 易於理解和實現 ；收斂快，一般僅需5-10次迭代即可，高效
缺點：
1，對K值得選取把握不同對結果有很大的不同
2，對於初始點的選取敏感，不同的隨機初始點得到的聚類結果可能完全不同
3，對於不是凸的數據集比較難收斂
4，對噪點過於敏感，因為演算法是根據基於均值的
5，結果不一定是全局最優，只能保證局部最優
6，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。
K-means演算法簡單理解，易於實現（局部最優），卻會有對初始點、雜訊點敏感等問題；還容易和監督學習的分類演算法KNN混淆。
參考閱讀：
1.《 深入理解K-Means聚類演算法 》
2.《 K-Means 》
D. 聚類演算法--KMeans
與分類、序列標注等任務不同，聚類是在事先並不知道任何樣本標簽的情況下，通過數據之間的內在關系把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。
聚類屬於非監督學習，K均值聚類是最基礎常用的聚類演算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。
其中 代表第i個樣本， 是 所屬的簇， 代表簇對應的中心點，M是樣本總數。
相關概念：
K值： 要得到的簇的個數。
質心： 每個簇的均值向量。即向量各維取平均即可。
距離量度： 常用歐幾里得距離和餘弦相似度(先標准化)。
KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。
KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：
（1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。
（2）從數據集中隨機選擇K個數據點作為質心。
（3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。
（4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。
（5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。
（6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。
KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。
KMeans的優點 ：
高效可伸縮，計算復雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。
收斂速度快，原理相對通俗易懂，可解釋性強。
當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。
缺點 ：
受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。
K是超參數，一般需要按經驗選擇。
對噪音和異常點比較的敏感，用來檢測異常值。
只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。
根據以上特點，我們可以從下面幾個角度對演算法做調優。
（1）數據預處理：歸一化和異常點過濾
KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些雜訊點最好能提前過濾。
（2）合理選擇K值
K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。
為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。
損失函數記為 ，當分為K類時，Gap Statistic定義為： 。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重復多次就可以計算出 的近似值。
的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨著K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關系，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。
（3）改進初始值的選擇
之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心盡可能遠離 ，效果往往更好。這類演算法中，以K-Means++演算法最具影響力。
（4）採用核函數
主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為准確的聚類結果。
(1）初始的K個質心怎麼選？
最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點
（2）關於離群值？
離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些"極大""極小"之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。
（3）單位要一致！
（4）標准化
數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。
K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。
E. 分類和聚類的區別及各自的常見演算法
1、分類和聚類的區別：
Classification (分類)，對於一個classifier，通常需要你告訴它「這個東西被分為某某類」這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行「學習」，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)，
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常並不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類，簡單來說，就是根據文本的特徵或屬性，劃分到已有的類別中。如在自然語言處理NLP中，我們經常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括：決策樹分類法，樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網路法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然，除此之外，還有很多諸如屬於劃分法K中心點（K-MEDOIDS）演算法、CLARANS演算法；屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等；基於密度的方法：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；基於網格的方法：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；基於模型的方法)。
F. 機器學習中演算法的優缺點之最近鄰演算法
機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為KNN。我們在學習機器學習知識的時候一定要學習這種演算法，其實不管是什麼演算法都是有自己的優缺點的，KNN演算法也不例外，在這篇文章中我們就詳細的給大家介紹一下KNN演算法的優缺點，大家一定要好好學起來喲。
說到KNN演算法我們有必要說一下KNN演算法的主要過程，KNN演算法的主要過程有四種，第一就是計算訓練樣本和測試樣本中每個樣本點的距離，第二個步驟就是對上面所有的距離值進行排序(升序)。第三個步驟就是選前k個最小距離的樣本。第四個步驟就是根據這k個樣本的標簽進行投票，得到最後的分類類別。
那麼大家是否知道如何選擇一個最佳的K值，這取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一般來說，一個較好的K值可通過各種啟發式技術來獲取，比如說交叉驗證。另外雜訊和非相關性特徵向量的存在會使K近鄰演算法的准確性減小。近鄰演算法具有較強的一致性結果，隨著數據趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。
那麼KNN演算法的優點是什麼呢？KNN演算法的優點具體體現在六點，第一就是對數據沒有假設，准確度高，對outlier不敏感。第二就是KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練。第三就是KNN理論簡單，容易實現。第四就是理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。第五就是可用於非線性分類。第六就是訓練時間復雜度為O(n)。由此可見，KNN演算法的優點是有很多的。
那麼KNN演算法的缺點是什麼呢？這種演算法的缺點具體體現在六點，第一就是樣本不平衡時，預測偏差比較大。第二就是KNN每一次分類都會重新進行一次全局運算。第三就是k值大小的選擇沒有理論選擇最優，往往是結合K-折交叉驗證得到最優k值選擇。第四就是樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）效果差。第五就是需要大量內存。第六就是對於樣本容量大的數據集計算量比較大。
正是由於這些優點和缺點，KNN演算法應用領域比較廣泛，在文本分類、模式識別、聚類分析，多分類領域中處處有KNN演算法的身影。
在這篇文章中我們給大家介紹了很多關於KNN演算法的相關知識，通過對這些知識的理解相信大家已經知道該演算法的特點了吧，希望這篇文章能夠幫助大家更好的理解KNN演算法。
G. K-means 與KNN 聚類演算法
K-means 演算法屬於聚類演算法的一種。聚類演算法就是把相似的對象通過靜態分類方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性。聚類演算法的任務是將數據集劃分為多個集群。在相同集群中的數據彼此會比不同集群的數據相似。通常來說，聚類演算法的目標就是通過相似特徵將數據分組並分配進不同的集群中。
K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。 演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：
每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci 屬於質心集合 C ，然後每個數據點 x 基於下面的公式被分配到一個集群中。
在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：
K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。
上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。
Elbow point 拐點方法
通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。
DBI（Davies-Bouldin Index）
DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。
還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。
需要提前確定 K 的選值或者需嘗試很多 K 的取值
數據必須是數字的，可以通過歐氏距離比較
對特殊數據敏感，很容易受特殊數據影響
對初始選擇的質心/中心（centers）敏感
之前介紹了 KNN （K 鄰近）演算法 ，感覺這兩個演算法的名字很接近，下面做一個簡略對比。
K-means ：
聚類演算法
用於非監督學習
使用無標簽數據
需要訓練過程
K-NN ：
分類演算法
用於監督學習
使用標簽數據
沒有明顯的訓練過程
鄰近演算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。Cover和Hart在1968年提出了最初的鄰近演算法。KNN是一種分類(classification)演算法，它輸入基於實例的學習（instance-based learning），屬於懶惰學習（lazy learning）即KNN沒有顯式的學習過程，也就是說沒有訓練階段，數據集事先已有了分類和特徵值，待收到新樣本後直接進行處理。與急切學習（eager learning）相對應。
KNN是通過測量不同特徵值之間的距離進行分類。
思路是：如果一個樣本在特徵空間中的k個最鄰近的樣本中的大多數屬於某一個類別，則該樣本也劃分為這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
提到KNN，網上最常見的就是下面這個圖，可以幫助大家理解。
我們要確定綠點屬於哪個顏色（紅色或者藍色），要做的就是選出距離目標點距離最近的k個點，看這k個點的大多數顏色是什麼顏色。當k取3的時候，我們可以看出距離最近的三個，分別是紅色、紅色、藍色，因此得到目標點為紅色。
演算法的描述：
1）計算測試數據與各個訓練數據之間的距離；
2）按照距離的遞增關系進行排序；
3）選取距離最小的K個點；
4）確定前K個點所在類別的出現頻率；
5）返回前K個點中出現頻率最高的類別作為測試數據的預測分類
二、關於 K 的取值
K：臨近數，即在預測目標點時取幾個臨近的點來預測。
K值得選取非常重要，因為：
如果當K的取值過小時，一旦有雜訊得成分存在們將會對預測產生比較大影響，例如取K值為1時，一旦最近的一個點是雜訊，那麼就會出現偏差，K值的減小就意味著整體模型變得復雜，容易發生過擬合；
如果K的值取的過大時，就相當於用較大鄰域中的訓練實例進行預測，學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用，使預測發生錯誤。K值的增大就意味著整體的模型變得簡單；
如果K==N的時候，那麼就是取全部的實例，即為取實例中某分類下最多的點，就對預測沒有什麼實際的意義了；
K的取值盡量要取奇數，以保證在計算結果最後會產生一個較多的類別，如果取偶數可能會產生相等的情況，不利於預測。
K的取法：
常用的方法是從k=1開始，使用檢驗集估計分類器的誤差率。重復該過程，每次K增值1，允許增加一個近鄰。選取產生最小誤差率的K。
一般k的取值不超過20，上限是n的開方，隨著數據集的增大，K的值也要增大。
三、關於距離的選取
距離就是平面上兩個點的直線距離
關於距離的度量方法，常用的有：歐幾里得距離、餘弦值（cos）, 相關度 （correlation）, 曼哈頓距離 （Manhattan distance）或其他。
Euclidean Distance 定義：
兩個點或元組P1=（x1，y1）和P2=（x2，y2）的歐幾里得距離是
距離公式為：（多個維度的時候是多個維度各自求差）
四、總結
KNN演算法是最簡單有效的分類演算法，簡單且容易實現。當訓練數據集很大時，需要大量的存儲空間，而且需要計算待測樣本和訓練數據集中所有樣本的距離，所以非常耗時
KNN對於隨機分布的數據集分類效果較差，對於類內間距小，類間間距大的數據集分類效果好，而且對於邊界不規則的數據效果好於線性分類器。
KNN對於樣本不均衡的數據效果不好，需要進行改進。改進的方法時對k個近鄰數據賦予權重，比如距離測試樣本越近，權重越大。
KNN很耗時，時間復雜度為O(n)，一般適用於樣本數較少的數據集，當數據量大時，可以將數據以樹的形式呈現，能提高速度，常用的有kd-tree和ball-tree。
H. 用於數據挖掘的聚類演算法有哪些，各有何優勢
聚類方法的分類，主要分為層次化聚類演算法，劃分式聚類演算法，基於密度的聚類演算法，基於網格的聚類演算法，基於模型的聚類演算法等。
而衡量聚類演算法優劣的標准主要是這幾個方面：處理大的數據集的能力；處理任意形狀，包括有間隙的嵌套的數據的能力；演算法處理的結果與數據輸入的順序是否相關，也就是說演算法是否獨立於數據輸入順序；處理數據雜訊的能力；是否需要預先知道聚類個數，是否需要用戶給出領域知識；演算法處理有很多屬性數據的能力，也就是對數據維數是否敏感。
.聚類演算法主要有兩種演算法，一種是自下而上法（bottom-up），一種是自上而下法（top-down）。這兩種路徑本質上各有優勢，主要看實際應用的時候要根據數據適用於哪一種，Hierarchical methods中比較新的演算法有BIRCH主要是在數據體量很大的時候使用；ROCK優勢在於異常數據抗干擾性強……
關於數據挖掘的相關學習，推薦CDA數據師的相關課程，課程以項目調動學員數據挖掘實用能力的場景式教學為主，在講師設計的業務場景下由講師不斷提出業務問題，再由學員循序漸進思考並操作解決問題的過程中，幫助學員掌握真正過硬的解決業務問題的數據挖掘能力。這種教學方式能夠引發學員的獨立思考及主觀能動性，學員掌握的技能知識可以快速轉化為自身能夠靈活應用的技能，在面對不同場景時能夠自由發揮。點擊預約免費試聽課。