kmean聚類python

⑴ kmean演算法是干什麼的

聚類分析是一種靜態數據分析方法，常被用於機器學習，模式識別，數據挖掘等領域。通常認為，聚類是一種無監督式的機器學習方法，它的過程是這樣的：在未知樣本類別的情況下，通過計算樣本彼此間的距離（歐式距離,馬式距離，漢明距離，餘弦距離等）來估計樣本所屬類別。從結構性來劃分，聚類方法分為自上而下和自下而上兩種方法，前者的演算法是先把所有樣本視為一類，然後不斷從這個大類中分離出小類，直到不能再分為止；後者則相反，首先所有樣本自成一類，然後不斷兩兩合並，直到最終形成幾個大類。
常用的聚類方法主要有以下四種： //照搬的wiki，比較懶...
Connectivity based clustering（如hierarchical clustering 層次聚類法)
Centroid-based clustering(如kmeans)
Distribution-based clustering
Density-based clustering
Kmeans聚類是一種自下而上的聚類方法，它的優點是簡單、速度快；缺點是聚類結果與初始中心的選擇有關系，且必須提供聚類的數目。Kmeans的第二個缺點是致命的，因為在有些時候，我們不知道樣本集將要聚成多少個類別，這種時候kmeans是不適合的，推薦使用hierarchical 或meanshift來聚類。第一個缺點可以通過多次聚類取最佳結果來解決。
Kmeans的計算過程大概表示如下
隨機選擇k個聚類中心. 最終的類別個數<= k
計算每個樣本到各個中心的距離
每個樣本聚類到離它最近的中心
重新計算每個新類的中心
重復以上步驟直到滿足收斂要求。(通常就是中心點不再改變或滿足一定迭代次數).

⑵ 想了解機器學習，需要知道哪些基礎演算法

⑶ 聚類（Clustering）

無監督學習（Unsupervised learning） ：訓練樣本的標記信息是未知的，目標是為了揭露訓練樣本的內在屬性，結構和信息，為進一步的數據挖掘提供基礎。

· 聚類（clustering）

· 降維（dimensionality rection）

· 異常檢測（outlier detection）

· 推薦系統（recommendation system）

監督學習（supervised learning） ：訓練樣本帶有信息標記，利用已有的訓練樣本信息學習數據的規律預測未知的新樣本標簽

· 回歸分析（regression）

· 分類（classification）

聚類 ：物以類聚。按照某一個特定的標准（比如距離），把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不再同一個簇內的數據對象的差異性也盡可能的大。

簇 （或類cluster）：子集合。最大化簇內的相似性；最小化簇與簇之間的相似性。

聚類可以作為一個單獨過程，用於尋找數據內在分布結構，也可以作為其他學習任務前驅過程。

聚類和分類的區別：聚類是無監督學習任務，不知道真實的樣本標記，只把相似度搞得樣本聚合在一起；分類是監督學習任務，利用已知的樣本標記訓練學習器預測未知樣本的類別。

聚類相似度度量： 幾何距離

幾種距離度量方法：

· 歐式距離（Euclidean distance）:p=2的Minkowski距離， 

· Minkowoski距離：

  · 曼哈頓距離 （Manhattan distance）:p=1的Minkowski距離 

· 夾角餘弦 ：

` 相關系數 （Pearson correlation coefficient）： ,等式右面的x其實是 （x方向的均值），y其實是 （y方向的均值）,對於這個表達式很不友好，所以在此說明一下。

聚類類別：

· 基於劃分的聚類（partitioning based clustering）：k均值（K-means）, Mean shift

· 層次聚類（hierarchical clustering）：Agglomerative clustering, BIRCH

· 密度聚類（density based clustering）：DBSCAN

· 基於模型的聚類（model based clustering）：高斯混合模型（GMM）

· Affinity propagation

 · Spectral clustering

聚類原理：

劃分聚類（partition based clustering）：給定包含N個點的數據集，劃分法將構造K個分組；每個分組代表一個聚類，這里每個分組至少包含一個數據點，每個數據點屬於且只屬於一個分組；對於給定的K值，演算法先給出一個初始化的分組方法，然後通過反復迭代的的方法改變分組，知道准則函數收斂。

K均值演算法（Kmeans）:

` 給定樣本集：D={ , .... }, k均值演算法針對聚類所得簇：C={ , ... }

` 最小化平方差： ,其中：  簇 的質心，上面的2代表平方，下面的2代表范數2.

具體的K均值演算法過程 ：

1. 隨機選擇K個對子女給，每個對象出事地代表了一個簇的質心，即選擇K個初始質心；2. 對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；3. 重新計算每個簇的平均值。這個過程不斷重復，直到准則函數（誤差的平方和SSE作為全局的目標函數）收斂，直到質心不發生明顯的變化。

初始質心優化:Kmeans++：

輸入：樣本集D={ , ... } 聚類簇的數量K

選取初始質心的過程：

1. 隨機從m個樣本點中選擇一個樣本作為第一個簇的質心C1；2. 計算所有的樣本點到質心C1的距離： ;3. 從每個點的概率分布  中隨機選取一個點作為第二個質心C2。離C1越遠的點，被選擇的概率越大；4. 重新計算所有樣本點到質心的距離；5. 重復上述過程，直到初始的K個質心被選擇完成  ；按照Kmeans的演算法步驟完成聚類。

輸出：C= { , ... }

K均值演算法（Kmean）的優缺點 ：

優點：1. 簡單直觀，抑鬱理解實現；2. 復雜度相對比較低，在K不是很大的情況下，Kmeans的計算時間相對很短；3. Kmean會產生緊密度比較高的簇，反映了簇內樣本圍繞質心的緊密程度的一種演算法。

缺點：1. 很難預測到准確的簇的數目；2. 對初始值設置很敏感（Kmeans++）；3. Kmeans主要發現圓形或者球形簇，對不同形狀和密度的簇效果不好；4. Kmeans對雜訊和離群值非常敏感（Kmeadians對雜訊和離群值不敏感）

層次聚類（hierarchical clustering） ：

· 主要在不同層次對數據集進行逐層分解，直到滿足某種條件為止；

· 先計算樣本之間的距離。每次將距離最近的點合並到同一個類，然後再計算類與類之間的距離，將距離最近的類合並為一個大類。不停的合並，直到合成一個類。

· 自底向上（bottom-up）和自頂向下（top-down）兩種方法：

top-down： 一開始每個個體都是一個初始的類，然後根據類與類之間的鏈接（linkage）尋找同類，最後形成一個最終的簇

bottom-up：一開始所有樣本都屬於一個大類，然後根據類與類之間的鏈接排除異己，打到聚類的目的。

類與類距離的計算方法 ：

最短距離法，最長距離法，中間距離法，平均距離法

最小距離：

最大距離：

平均距離：

單鏈接（single-linkage）:根據最小距離演算法

全連接（complete-linkage）：根據最大距離演算法

均鏈接（average-linkage）：根據平均距離演算法

凝聚層次聚類具體演算法流程：

1. 給定樣本集，決定聚類簇距離度量函數以及聚類簇數目k；2. 將每個樣本看作一類，計算兩兩之間的距離；3. 將距離最小的兩個類合並成一個心類；4.重新計算心類與所有類之間的距離；5. 重復（3-4），知道達到所需要的簇的數目

層次聚類的優缺點：

優點：1.可以得到任意形狀的簇，沒有Kmeans對形狀上的限制；2. 可以發現類之間的層次關系；3.不要制定簇的數目

缺點：1. 通常來說，計算復雜度高（很多merge/split）；2.雜訊對層次聚類也會產生很大影響；3.不適合打樣本的聚類

密度聚類（density based clustering） :

  ` 基於密度的 方法的特點是不依賴於距離，而是依賴於密度，從而客服k均值只能發現「球形」聚簇的缺點

· 核心思想：只要一個區域中點的密度大於某個閾值，就把它加到與之相近的聚類中去

· 密度演算法從樣本密度的角度來考察樣本的可連接性，並基於可連接樣本不斷擴展聚類簇以獲得最終的聚類結果

· 對雜訊和離群值的處理有效

· 經典演算法：DBSCAN（density based spatial clutering of applications with noise）

DBSCAN 基於近鄰域（neighborhood）參數（ ）刻畫樣本分布的 緊密程度的一種演算法。

基本概念：

· 樣本集： D={ }

` 閾值： 

·  ：對樣本點 的 包括樣本集中與 距離不大於 的樣本

· 核心對象（core object）：如果 的 至少包含MinPts個樣本，那麼 就是一個核心對象 ,

假設MinPts=3,虛線標識為

·密度直達（directly density-reachable）:如果 位於 的 中，並且 是和新對象，那麼 由 密度直達

· 密度可達（density-reachable）：對 ,如果存在一串樣本點p1,p2.....pn =  ，pn =  ,且 由

` 密度直達,則稱 由 密度可達

· 密度相連：存在樣本集合中一點o,如果 和 均由O密度可達，那麼 和 密度相連

上圖中： 是核心對象，那麼從 出發， 由 密度直達； 由 密度可達； 與 密度相連。

DBSCAN演算法的過程：

1. 首先根據鄰域參數（ ）確定樣本集合D中所有的核心對象，存在集合P中。加入集合P的條件為 有不少於MinPts的樣本數。

2. 然後從核心對象集合P中任意選取一個核心對象作為初始點，找出其密度可達的樣本生成聚類簇，構成第一個聚類簇C1。

3. 將C1內多有核心對象從P中去除，再從更新後的核心對象集合任意選取下一個種子樣本。

4. 重復（2-3），直到核心對象被全部選擇完，也就是P為空集。

聚類演算法總結：

基於劃分的聚類：K均值（kmeans），kmeans++

層次聚類：Agglomerative聚類

密度聚類：DBSCAN

基於模型 的聚類：高斯混合模型（GMM）,這篇博客里咩有介紹

雖然稀里糊塗，但是先跟下來再說吧：