核聚類演算法

A. dbscan聚類演算法是什麼

DBSCAN是基於密度空間的聚類演算法，與KMeans演算法不同，它不需要確定聚類的數量，而是基於數據推測聚類的數目，它能夠針對任意形狀產生聚類。

DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。

DBSCAN演算法需要首先確定兩個參數：

1、epsilon：在一個點周圍鄰近區域的半徑。

2、minPts：鄰近區域內至少包含點的個數。

通常根據以上兩個參數，結合epsilon-neighborhood的特徵，可以把樣本中的點分成核點、邊緣點、離群點三類。

B. 核k均值聚類演算法 核為什麼時與kmeans等價

一，K-Means聚類演算法原理 k-means 演算法接受參數 k ；然後將事先輸入的n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較校聚類相似度是利用各聚類中對象的均值所獲得一個「中心對 象」。

C. 聚類演算法概述及比較

其本質是：尋找聯系緊密的事物進行區分，將數據劃分為有意義或有用的簇

目標是：同簇內的數據對象的相似性盡可能大，不同簇間的數據對象的差異性盡可能大。

核心是：相似度計算

回顧一下：無監督學習(Unsupervised learning)：是否有監督（supervised），就看輸入數據是否有標簽（label）。輸入數據有標簽，則為有監督學習，沒標簽則為無監督學習。

具體包含：

K-means DIANA OPTICS Spectral STING COBWeb
K-medoids BIRCH DBSCAN CLIQUE CLASSIT
CLARANS Chameleon FDC WAVE-CLUSTER SOM

新發展的方法:

基於約束 基於模糊 基於粒度 量子聚類 核聚類 譜聚類
COD (Clustering
with Ob2structed
Distance) FCM SVDD/SVC 圖論中的譜圖

劃分法（Partitioning methods）:

層次法（Hierarchical Clustering）:

基於密度的聚類（density-based methods）:

基於圖的聚類（Graph-based methods）：

基於網格的方法（grid-based methods）:

基於模型的方法（model-based methods）:

map詳細: http://scikit-learn.org/stable/tutorial/machine_learning_map/

D. 聚類演算法

1. 概述

K-means聚類演算法也稱k均值聚類演算法，是集簡單和經典於一身的基於距離的聚類演算法。它採用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該演算法認為類簇是由距離靠近的對象組成的，因此把得到 緊湊且獨立的簇作為最終目標。

2. 演算法核心思想

K-means聚類演算法是一種迭代求解的聚類分析演算法，其步驟是隨機選取K個對象作為初始的聚類中心，然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

3. 演算法實現步驟

1、首先確定一個k值，即我們希望將數據集經過聚類得到k個集合。

2、從數據集中隨機選擇k個數據點作為質心。

3、對數據集中每一個點，計算其與每一個質心的距離（如歐式距離），離哪個質心近，就劃分到那個質心所屬的集合。

4、把所有數據歸好集合後，一共有k個集合。然後重新計算每個集合的質心。

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

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

4. 演算法步驟圖解

上圖a表達了初始的數據集，假設k=2。在圖b中，我們隨機選擇了兩個k類所對應的類別質心，即圖中的紅色質心和藍色質心，然後分別求樣本中所有點到這兩個質心的距離，並標記每個樣本的類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。

K-means術語：

簇：所有數據的點集合，簇中的對象是相似的。

質心：簇中所有點的中心（計算所有點的中心而來）

5. K-means演算法優缺點

優點：

1、原理比較簡單，實現也是很容易，收斂速度快。

2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

3、主要需要調參的參數僅僅是簇數k。

缺點：

1、K值需要預先給定，很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同 ，對結果影響很大。

3、對噪音和異常點比較的敏感。用來檢測異常值。

4、採用迭代方法，可能只能得到局部的最優解，而無法得到全局的最優解。

E. 學會用聚類演算法進行數據挖掘需要怎樣的數學基礎

會用聚類演算法進行數據挖掘需要線性代數, 變分演算，距離度量，距離矩陣等的數學知識基礎。

在數據科學中，我們可以通過聚類分析觀察使用聚類演算法後獲得一些有價值的信息，其中會涉及許多數學理論與實際計算。
主要有以下幾類演算法：
K-Means（k-平均或k-均值）是普遍知名度最高的一種聚類演算法，在許多有關數據科學和機器學習的課程中經常出現。
Mean shift演算法，又稱均值漂移演算法，這是一種基於核密度估計的爬山演算法，適用於聚類、圖像分割、跟蹤等
DBSCAN是一種基於密度的聚類演算法，它不需要輸入要劃分的聚類個數，對聚類的形狀沒有偏倚。
層次聚類會將每個數據點視為單個聚類，然後連續合並成對的聚類，直到所有聚類合並成包含所有數據點的單個聚類。

關於數據挖掘的相關學習，推薦CDA數據師的相關課程，課程內容兼顧培養解決數據挖掘流程問題的橫向能力以及解決數據挖掘演算法問題的縱向能力。要求學生具備從數據治理根源出發的思維，通過數字化工作方法來探查業務問題，通過近因分析、宏觀根因分析等手段，再選擇業務流程優化工具還是演算法工具，而非「遇到問題調演算法包」。點擊預約免費試聽課。

F. 聚類演算法（上）06

這篇文章的整體排版主要是根據個人的博客來噠，如果感興趣的話可以去我的自己搭建的個人博客看這篇 文章 。

聚類演算法很多，所以和講回歸演算法一樣，分成了上下，上中主要講了傳統的K-Means演算法以及其相應的優化演算法入K-Means++，K-Means||和Canopy等。下中主要講了另外兩種的思路的聚類演算法，即層次聚類和密度聚類。

聚類算就是懟大量未知標注的數據集，按照數據 內部存在的數據特徵 將數據集 劃分為多個不同的類別 ，使類別內的數據比較相似，類別之間的數據相似度比較小，屬於 無監督學習 。

從定義就可以看出，聚類演算法的關鍵在於計算樣本之間的 相似度 ，也稱為 樣本間的距離 。

說到聚類演算法，那肯定核心就是計算距離的公式了，目前常用的有以下幾種。
閔可夫斯基距離（Minkowski） ：公式2.1

KL距離（相對熵） ：
思考下條件熵的定義，簡單的來說就是在放生一件事情的時候，發生另一件事的概率。公式如下公式2.7.
註：這里書的概率不是實指概率，而是熵表達的含義。這個公式其實就是條件熵的公式。

傑卡德相似系數(Jaccard) ：
這個很好理解，它的核心就是使用兩個集合的交集和並集的比率來代表兩者的相似度，也就是說重合的越多越相似。公式如下，公式2.8.

Pearson相關系數 ：
這個就是考研數學中的相關系數，表達就是兩者之間的想關系，所以直接拿來用就好了，公式如下公式2.9。

給定一個有M個對象的數據集，構建一個具有k個簇的模型，其中k<=M。滿足 以下條件:

基本思想:
對於給定的類別數目k，首先給定初始劃分，通過迭代改變樣本和簇的隸屬關系，使的每次處理後得到的劃分方式比上一次的好，即 總的數據集之間的距離和變小了

K-means的核心演算法如下：

再循環中的第二步，我們移動了中心點的位置，把中心點移到了隸屬於該中心點類別的所有樣本的中間，並使用樣本的均值作為位置。這樣子看似是拍腦袋想的移動策略，其實是可以推導出來的。正如聚類演算法思想所指出的，我們要讓所有的點到自己的分類的中心點的歐幾里得距離最小，所以我們設置目標放稱為公式4.1，公式中的1/2是為了之後求導運算方便。我們為了讓目標函數盡可能的小，所以使用了之前一直在使用的思考方式，對其使用梯度下降演算法，求導後得到公式4.2，之後令其等於0，就得到了公式4.3。

最後這個看似不錯的演算法，其實有著不小的缺點，那就是 初值敏感 。我們來仔細想一想，如果兩個不小心隨機生成的初值落到了一個類別中，兩者的距離還特別近，這中情況下就很難正確分類了。除此之外，由於移動策略中使用的是均值，也就是說如果集合中含有非常大的誤差點的話，這樣子會是中心點的設置偏離正確點很遠，所以很多時候我們改用 中值來更新中心點 ，這就是我們說的K-Mediods聚類，即K中值聚類。

總結下K-means演算法
優點：

由於K-Means對初始中心點非常敏感，我們這里就嘗試著通過二分法弱化初始中心點。這種演算法的具體步驟如下：

我們在這個演算法中提到了SSE，這個可以是簇內所有樣本點，到其中心點的距離的總和，代表著簇內的點是不是高度相關。計算公式如下公式4.4。

可以看出在這種演算法下，很好的避開了，兩個中心點都在一起的情況。

K-Means++做的改善，是直接對初始點的生成位置的選擇進行優化的，他的初始點生成策略如下：

Canopy屬於一種「粗略地」聚類演算法，簡單的來說就是，不那麼追求自動獲得最優解，而是引入了一種人為規定的先驗值進行聚類，具體步驟如下：

註：Canopy演算法得到的最終結果的值，聚簇之間是可能存在重疊的，但是不會存在 某個對象不屬於任何聚簇的情況
顯然，這種演算法雖然快，但是很難生成滿足我們應用的模型，所以通常我們將它作為解決K-Means初值敏感的方案，他們合在一起就是Canopy+K-Means演算法。
順序就是先使用Canopy演算法獲得K個聚類中心，然後用這K個聚類中心作為K-Means演算法。這樣子就很好的解決了K-Means初值敏感的問題。

Mini Batch K-Means演算法是K-Means演算法的一種優化變種，採用小規模的數據子集，來減少計算時間。其中採用小規模的數據子集指的是每次訓練使用的數據集是在訓練演算法的時候隨機抽取的數據子集。Mini Batch K-Means演算法可以減少K-Means演算法的收斂時間，而且產生的結果效果只是略差於標准K-Means演算法。
它的演算法步驟如下：

聚類演算法的衡量標准有很多，包括均一性、完整性、V-measure、調整蘭德系數（ARI ，Adjusted Rnd Index）、調整互信息(AMI，Adjusted Mutual Information)以及輪廓系數等等。

均一性：一個簇中只包含一個類別的樣本，則滿足均一性。其實也可以認為就是正確率，即每個聚簇中正確分類的樣本數占該聚簇總樣本數的比例和。其公式如下公式5.1。

完整性：同類別樣本被歸類到相同簇中，則滿足完整性。每個聚簇中正確分類的樣本數占該類型的總樣本數比例的和，通俗的來說就是，我們已分類類別中，分類正確的個數。
其公式如下，公式5.2：

在實際的情況中，均一性和完整性是往往不能兼得的，就好像抓特務時的矛盾一樣，到底是保證每個抓的人都是特務，還是寧可錯抓也不放過一個特務，之間的取捨很難把握。所以再一次貫徹，魚和熊掌不可兼得，我們就加權，於是得到的就是V-measure，其公式如下公式5.3：

蘭德系數（RI，Rand index） ，我用中文看了不少講蘭德系數的博客，其中的文字說明幾乎都是相同的，對個人的理解幫助不是特別大，於是用英文查的。最終理解了這個系數的參數的意思，想看英文說明的，個人覺得還挺好懂的參考 這里 。以下是我個人的講解。

首先，將原數據集中的元素進行兩兩配對形成一個新的數據集，我們稱之為S數據集。這時候，我們將原數據集，根據兩種不同的策略分別劃分成r份和s份，並對這兩個數據集命名為X和Y。在這里我們可以看出，X和Y的元素是相同的，只是他們的劃分方式不同。
接下來我們來思考，S數據集中，每個元素中的兩個樣本，在X和Y中只有兩種可能，就是兩個樣本都在一個子集中，或者不在一個子集中，那麼對於S中的一個元素，只有四種可能性。

接下來引入， 調整蘭德系數(ARI，Adjusted Rnd Index) ，ARI取值范圍 ，值越大，表示聚類結果和真實情況越吻合。從廣義的角度來將，ARI是衡量兩個數據分布的吻合程度的，公式5.5如下：

調整互信息，整體的流程很像ARI，AMI則是對MI進行調整。而MI是使用信息熵來描述的。那麼互信息表示了什麼呢，首先先看下 維基網路的定義 ：

之前我們說到的衡量指標都是有標簽的，這里的輪廓系數則是不包含標簽的評價指標。

G. 常見的幾種聚類方法

作為無監督學習的一個重要方法，聚類的思想就是把屬性相似的樣本歸到一類。對於每一個數據點，我們可以把它歸到一個特定的類，同時每個類之間的所有數據點在某種程度上有著共性，比如空間位置接近等特性。多用於數據挖掘、數據分析等一些領域。

下面簡單介紹一下幾種比較常見的聚類演算法。

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

H. 常用的聚類方法有哪幾種

聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。

1、劃分法，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。

2、層次法，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。

3、基於密度的方法，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。

5、基於網格的方法，這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。

6、基於模型的方法，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。

(8)核聚類演算法擴展閱讀：

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。

它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

I. 聚類演算法--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個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。

J. K均值演算法

代價函數可以定義為各個樣本距離所屬簇中心點的誤差平方和

K均值演算法有一些缺點，例如受初值和離群點的影響每次的結果不穩定、結果 通常不是全局最優而是局部最優解、無法很好地解決數據簇分布差別比較大的情 況(比如一類是另一類樣本數量的100倍)、不太適用於離散分類等。但是瑕不掩 瑜，K均值聚類的優點也是很明顯和突出的，主要體現在:對於大數據集，K均值 聚類演算法相對是可伸縮和高效的，它的計算復雜度是O(NKt)接近於線性，其中N是 數據對象的數目，K是聚類的簇數，t是迭代的輪數。盡管演算法經常以局部最優結 束，但一般情況下達到的局部最優已經可以滿足聚類的需求。
其實書中也少講了缺點，那就是關於k的選擇，當維度很高的時候，你很難判斷選擇k多少比較合適。
不過書中在演算法調優中說了。所謂的調優其是也是變相的說那些缺點。

K均值演算法的調優一般可以從以下幾個角度出發。

(1)數據歸一化和離群點處理。
K均值聚類本質上是一種基於歐式距離度量的數據劃分方法，均值和方差大的 維度將對數據的聚類結果產生決定性的影響，所以未做歸一化處理和統一單位的 數據是無法直接參與運算和比較的。同時，離群點或者少量的雜訊數據就會對均 值產生較大的影響，導致中心偏移，因此使用K均值聚類演算法之前通常需要對數據 做預處理。

（2)合理選擇K值。
K值的選擇是K均值聚類最大的問題之一，這也是K均值聚類演算法的主要缺 點。實際上，我們希望能夠找到一些可行的辦法來彌補這一缺點，或者說找到K值 的合理估計方法。但是，K值的選擇一般基於經驗和多次實驗結果。例如採用手肘 法，我們可以嘗試不同的K值，並將不同K值所對應的損失函數畫成折線，橫軸 為K的取值，縱軸為誤差平方和所定義的損失函數，如圖5.3所示

由圖可見，K值越大，距離和越小;並且，當K=3時，存在一個拐點，就像人 的肘部一樣;當K (1,3)時，曲線急速下降;當K>3時，曲線趨於平穩。手肘法認 為拐點就是K的最佳值。
手肘法是一個經驗方法，缺點就是不夠自動化，因此研究員們又提出了一些 更先進的方法，其中包括比較有名的Gap Statistic方法[5]。Gap Statistic方法的優點 是，不再需要肉眼判斷，而只需要找到最大的Gap statistic所對應的K即可，因此該 方法也適用於批量化作業。在這里我們繼續使用上面的損失函數，當分為K簇時， 對應的損失函數記為Dk。Gap Statistic定義為
Gap(K)=E(logDk)−logDk

內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本
做K均值，得到一個Dk;重復多次就可以計算出E(logDk)的近似值。那麼Gap(K)有
什麼物理含義呢?它可以視為隨機樣本的損失與實際樣本的損失之差。試想實際 樣本對應的最佳簇數為K，那麼實際樣本的損失應該相對較小，隨機樣本損失與實 際樣本損失之差也相應地達到最小值，從而Gap(K)取得最大值所對應的K值就是最 佳的簇數。根據式(5.4)計算K =1,2,...,9所對應的Gap Statistic

(3)採用核函數。
採用核函數是另一種可以嘗試的改進方向。傳統的歐式距離度量方式，使得K 均值演算法本質上假設了各個數據簇的數據具有一樣的先驗概率，並呈現球形或者 高維球形分布，這種分布在實際生活中並不常見。面對非凸的數據分布形狀時， 可能需要引入核函數來優化，這時演算法又稱為核K均值演算法，是核聚類方法的一種 [6]。核聚類方法的主要思想是通過一個非線性映射，將輸入空間中的數據點映射到 高位的特徵空間中，並在新的特徵空間中進行聚類。非線性映射增加了數據點線 性可分的概率，從而在經典的聚類演算法失效的情況下，通過引入核函數可以達到 更為准確的聚類結果。

K均值演算法的主要缺點如下。
(1)需要人工預先確定初始K值，且該值和真實的數據分布未必吻合。
(2)K均值只能收斂到局部最優，效果受到初始值很大。
(3)易受到噪點的影響。
(4)樣本點只能被劃分到單一的類中。

■ K-means++演算法
K均值的改進演算法中，對初始值選擇的改進是很重要的一部分。而這類演算法 中，最具影響力的當屬K-means++演算法。原始K均值演算法最開始隨機選取數據集中 K個點作為聚類中心，而K-means++按照如下的思想選取K個聚類中心。假設已經 選取了n個初始聚類中心(0<n<K)，則在選取第n+1個聚類中心時，距離當前n個 聚類中心越遠的點會有更高的概率被選為第n+1個聚類中心。在選取第一個聚類中 心(n=1)時同樣通過隨機的方法。可以說這也符合我們的直覺，聚類中心當然是 互相離得越遠越好。當選擇完初始點後，K-means++後續的執行和經典K均值演算法 相同，這也是對初始值選擇進行改進的方法等共同點。

■ ISODATA演算法
當K值的大小不確定時，可以使用ISODATA演算法。ISODATA的全稱是迭代自 組織數據分析法。在K均值演算法中，聚類個數K的值需要預先人為地確定，並且在 整個演算法過程中無法更改。而當遇到高維度、海量的數據集時，人們往往很難准 確地估計出K的大小。ISODATA演算法就是針對這個問題進行了改進，它的思想也 很直觀。當屬於某個類別的樣本數過少時，把該類別去除;當屬於某個類別的樣 本數過多、分散程度較大時，把該類別分為兩個子類別。ISODATA演算法在K均值 演算法的基礎之上增加了兩個操作，一是分裂操作，對應著增加聚類中心數;二是 合並操作，對應著減少聚類中心數。ISODATA演算法是一個比較常見的演算法，其缺 點是需要指定的參數比較多，不僅僅需要一個參考的聚類數量Ko，還需要制定3個
閾值。下面介紹ISODATA演算法的各個輸入參數。
(1)預期的聚類中心數目Ko。在ISODATA運行過程中聚類中心數可以變 化，Ko是一個用戶指定的參考值，該演算法的聚類中心數目變動范圍也由其決定。 具體地，最終輸出的聚類中心數目常見范圍是從Ko的一半，到兩倍Ko。
(2)每個類所要求的最少樣本數目Nmin。如果分裂後會導致某個子類別所包 含樣本數目小於該閾值，就不會對該類別進行分裂操作。
(3)最大方差Sigma。用於控制某個類別中樣本的分散程度。當樣本的分散 程度超過這個閾值時，且分裂後滿足(1)，進行分裂操作。
(4)兩個聚類中心之間所允許最小距離Dmin。如果兩個類靠得非常近(即這 兩個類別對應聚類中心之間的距離非常小)，小於該閾值時，則對這兩個類進行
合並操作。
如果希望樣本不劃分到單一的類中，可以使用模糊C均值或者高斯混合模型， 高斯混合模型會在下一節中詳細講述。

K均值聚類的迭代演算法實際上是一種最大期望演算法 (Expectation-Maximization algorithm)，簡稱EM演算法。EM演算法解決的是在概率模 型中含有無法觀測的隱含變數情況下的參數估計問題。
EM演算法只保證收斂到局部最優解