基于原型的聚類方法

文章目錄

• • 一、概念
  • 二、K-Means
  • • 2.1 算法流程
    • 2.2 超參數
    • 2.3 特性
    • 2.4 解析
    • 2.5 K-Means++
    • 2.6 Python實現
  • 三、K-Mediods
  • • 3.1 概念
    • 3.2 算法對比
  • 四、特性

一、概念

??原型”是指樣本空間中具有代表性的點。

??原型聚類假設聚類結構可以通過一組原型刻畫，這一方法在實際聚類任務中最為常用，理解起來也較簡單；通常算法先對原型進行初始化，然后對原型進行迭代更新求解。采用不同的原型表示，不同的求解方式，即會產生不同的聚類算法。最經典的原型聚類算法即：

• $K?Means$ 聚類算法：基于各個樣本點與各個聚集簇的中心點距離遠近，進行劃分的聚類算法。
• $K?Mediods$ 算法：在 $K?Means$ 基礎上改進的算法。

二、K-Means

2.1 算法流程

??算法思想

• 輸入聚類個數 $k$ ，以及包含 $n$ 個數據對象的數據集，輸出標準的 $k$ 個聚類的一種算法。
• 然后將 $n$ 個數據對象劃分為 $k$ 個聚類，而最終所獲得的聚類滿足:
  • 同一聚類中的對象相似度較高；
  • 而不同聚類中的對象相似度較小。

??$K$ 均值聚類的核心目標是將給定的數據集劃分成 $K$ 個簇，并給出每個數據對應的簇中心點。算法的具體步驟描述如下：

數據預處理，如歸一化、離群點處理等；

隨機選取 $K$ 個簇中心，記為 ${\mu }_1^0,{\mu }_2^0,\dots ,{\mu }_K^0$ ；

定義代價函數：$J(c,\mu )=\underset{\mu }{\min }\underset{c}{\min }\sum _{i=1}^M\Vert x_i?{\mu }_{ci}\Vert$;

令 $t=0,1,2,\dots$ 為迭代步數，重復下面過程直到 $J$ 收斂：

• 對于每一個樣本 $x_i$，將其分配到距離最近的簇
  $$c_i^t\leftarrow {\mathrm{argmin}}_k\Vert x_i?{\mu }_k^t{\Vert }^2$$

• 對于每一個類簇 $k$，重新計算該類簇的中心
  $${\mu }_k^{t+1}\leftarrow {\mathrm{argmin}}_{\mu }\sum _{i:c_i^t=k}\Vert x_i?\mu {\Vert }^2$$

??$K$ 均值算法在迭代時，假設當前 $J$ 沒有達到最小值，那么首先固定簇中心 $\{{\mu }_k\}$，調整每個樣例 $x_i$ 所屬的類別 $c_i$ 來讓 $J$ 函數減少；然后固定 $\{c_i\}$，調整簇中心 $\{{\mu }_k\}$ 使 $J$ 減少，這兩個過程交替循環，$J$ 單調遞減；當 $J$ 遞減到最小值時，$\{{\mu }_k\}$ 和 $\{c_j\}$ 也同時收斂。

??物理意義來說：質心就是質量中心，重心就是重力受力的集合點，形心就是幾何形狀的中心。質心一般和重心位置相同，看受重力情況來確定，形心則是一般為規則圖形，如果不規則，一般算不了。他們的區別：當質量均勻，形狀規則的物體，三個都在一點，若質量不均勻，那么形心和那兩個是分開的。

2.2 超參數

??$K?Means$ 算法首先選擇 $K$ 個初始質心，其中 $K$ 是用戶指定的參數，即所期望的簇的個數。這樣做的前提是已經知道數據集中包含多少個簇，但很多情況下，我們并不知道數據的分布情況。如何有效地確定$K$ 值，提供以下幾種方法：

• 從實際問題出發，人工指定比較合理的K值，通過多次隨機初始化聚類中心選取比較滿意的結果
• 均方根：假設我們有 $m$ 個樣本，該方法認為 $K=\sqrt{m/2}$
• 枚舉法：用不同的 $K$ 值進行聚類
  • 分別計算類內距離均值和類間距離均值之比，選擇最小的那個$K$ 值
  • 對不同 $K$ 值都產生 $2$ 次聚類，選擇兩次聚類結果最相似的 $K$ 值
• 手肘法（$Elbow$)、層次聚類法等

??用戶指定的參數也稱為超參數，該類參數無法通過模型對數據訓練獲得。

??核心指標：$SSE(sumofthesquarederrors$，誤差平方和) $SSE$ 是所有樣本的聚類誤差，代表了聚類效果的好壞。

??手肘法：隨著聚類數 $k$ 的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那么誤差平方和 $SSE$ 自然會逐漸變小。當k小于真實聚類數時，由于 $k$ 的增大會大幅增加每個簇的聚合程度，故 $SSE$ 的下降幅度會很大，而當 $k$ 到達真實聚類數時，再增加 $k$ 所得到的聚合程度回報會迅速變小，所以 $SSE$ 的下降幅度會驟減，然后隨著 $k$ 值的繼續增大而趨于平緩，也就是說 $SSE$ 和 $k$ 的關系圖是一個手肘的形狀，而這個肘部對應的 $k$ 值就是數據的真實聚類數。

2.3 特性

??優點

• 簡單、易于理解、運算速度快；
• 對處理大數據集，該算法保持可伸縮性和高效性；
• 當簇接近高斯分布時，它的效果較好。

??缺點

• 在 $K?Means$ 算法是局部最優的，容易受到初始質心的影響；
• 在 $K?Means$ 算法中 $K$ 值需要事先給定的，有時候 $K$ 值的選定非常難以估計；
• 在簇的平均值可被定義的情況下才能使用，只能應用連續型數據；
• 該算法需要不斷地進行樣本分類調整，不斷地計算調整后的新的聚類中心，因此當數據量非常大時，算法的性能（時間和計算資源）開銷是非常大的；
• 對噪聲和孤立點數據敏感。

歐幾里德距離是數學加減乘除算出來的距離，因此這就是只能用于連續型變量的原因。

2.4 解析

• 初始簇心的選擇
  • 有時候會影響最終的聚類結果，實際操作中，我們一般會選用不同的數據作為初始簇心，多次執行$K?Means$ 算法；
  • 新質心不一定是實際的一個數據點。
• $K?Means$ 算法超參數 $K$
  • $K$ 是用戶指定的參數，即所期望的簇的個數。$K$ 指定的前提是已知數據集中包含多少個簇，但很多情況下，并不知道數據的分布情況，需要憑借業務專家的經驗；
  • 常見做法是多嘗試幾個 $K$ 值，看分成幾類的結果更好解釋，更符合分析目的等；或者可以把各種 $K$ 值算出的 $SSE$ 做比較，取最小的 $SSE$ 的 $K$ 值。
• $K?Means$ 算法會不會陷入一直選質心的過程，永遠停不下來？
  • 不會。數學證明一定會收斂，目標函數 $SSE$ 是可收斂的函數，但數據量大時，收斂時間可能較長。

??業務專家的作用非常大，主要體現在聚類變量的選擇和對于聚類結果的解讀：

??比如要對于現有的客戶分群，那么就要根據最終分群的目的選擇不同的變量來分群，這就需要業務專家經驗支持。如果要優化客戶服務的渠道，那么就應選擇與渠道相關的數據；如果要推廣一個新產品，那就應該選用用戶目前的使用行為的數據來歸類用戶的興趣。算法是無法做到這一點的

??欠缺經驗的分析人員和經驗豐富的分析人員對于結果的解讀會有很大差異。其實不光是聚類分析，所有的分析都不能僅僅依賴統計學家或者數據工程師。

??最小化 $SSE$ 目標函數 誤差平方和函數（原本含義是擬合數據和原始數據對應點的誤差的平方和）

2.5 K-Means++

??$K?Means$ 與 $K?Means++$：

??不同于 $K?Means$ 算法第一次是隨機選擇 $K$ 個聚類中心，$K?Means++$ 是假設已經選取了 $p$ 個初始聚類中心 $(0<p<K)$，則在選取第 $p+1$ 個聚類中心時：距離當前 $p$ 個聚類中心越遠的點會有更高的概率被選為第 $p+1$ 個聚類中心。只有在選取第一個聚類中心 $(p=1)$ 時是通過隨機的方法。該改進方法符合一般的直覺：聚類中心互相之間距離得越遠越好。這個改進直觀簡單，也非常有效。
其他改進算法還有：

• $ISODATA$：對于高緯度的數據樣本，針對$K$值事先不一定能準確指定的情況，當屬于某個類別的樣本數過少時把這個類別去除，當屬于某個類別的樣本數過多、分散程度較大時把這個類別分為兩個子類別。

??$KMeans++$ 也是解決解決 $KMeans$ 的初值敏感的問題，它與二分 $K?Means$ 不同的是：在選擇兩個聚類點的時候不是隨機選擇，而是先隨機選擇一個點，第二個選擇距離該點最遠的點，再進行劃分。當然，為了避免異常點的存在，第二個點的選擇會選擇距離較遠的幾個點并進行加權選擇最終的第二個點。

??$K?Means$ ：隨機的選取初始質心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小 $SSE$（誤差的平方和）的簇集。

??$KMeans++$：隨機地選擇第一個點，或取所有點的質心作為第一個點。然后，對于每個后繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法可以用于抽樣和篩出離群點后的樣本數據上。

2.6 Python實現

import timeimport numpy as np import matplotlib.pyplot as pltfrom sklearn.cluster import MiniBatchKMeans, KMeans from sklearn.metrics.pairwise import pairwise_distances_argmin from sklearn.datasets import make_blobsnp.random.seed(42)batch_size = 45 centers = [[1, 1], [-1, -1], [1, -1]] n_clusters = len(centers) X, labels_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)k_means = KMeans(init="k-means++", n_clusters=3, n_init=10) t0 = time.time() k_means.fit(X) t_batch = time.time() - t0mbk = MiniBatchKMeans(init="k-means++",n_clusters=3,batch_size=batch_size,n_init=10,max_no_improvement=10,verbose=0, ) t0 = time.time() mbk.fit(X) t_mini_batch = time.time() - t0fig = plt.figure(figsize=(8, 3)) fig.subplots_adjust(left=0.02, right=0.98, bottom=0.05, top=0.9) colors = ["#4EACC5", "#FF9C34", "#4E9A06"]k_means_cluster_centers = k_means.cluster_centers_ order = pairwise_distances_argmin(k_means.cluster_centers_, mbk.cluster_centers_) mbk_means_cluster_centers = mbk.cluster_centers_[order]k_means_labels = pairwise_distances_argmin(X, k_means_cluster_centers) mbk_means_labels = pairwise_distances_argmin(X, mbk_means_cluster_centers)ax = fig.add_subplot(1, 3, 1) for k, col in zip(range(n_clusters), colors):my_members = k_means_labels == kcluster_center = k_means_cluster_centers[k]ax.plot(X[my_members, 0], X[my_members, 1], "w", markerfacecolor=col, marker=".")ax.plot(cluster_center[0],cluster_center[1],"o",markerfacecolor=col,markeredgecolor="k",markersize=6,)ax.set_title("KMeans") ax.set_xticks(()) ax.set_yticks(()) plt.text(-3.5, 1.8, "train time: %.2fs\ninertia: %f" % (t_batch, k_means.inertia_))ax = fig.add_subplot(1, 3, 2) for k, col in zip(range(n_clusters), colors):my_members = mbk_means_labels == kcluster_center = mbk_means_cluster_centers[k]ax.plot(X[my_members, 0], X[my_members, 1], "w", markerfacecolor=col, marker=".")ax.plot(cluster_center[0],cluster_center[1],"o",markerfacecolor=col,markeredgecolor="k",markersize=6,) ax.set_title("MiniBatchKMeans") ax.set_xticks(()) ax.set_yticks(()) plt.text(-3.5, 1.8, "train time: %.2fs\ninertia: %f" % (t_mini_batch, mbk.inertia_))different = mbk_means_labels == 4 ax = fig.add_subplot(1, 3, 3)for k in range(n_clusters):different += (k_means_labels == k) != (mbk_means_labels == k)identic = np.logical_not(different) ax.plot(X[identic, 0], X[identic, 1], "w", markerfacecolor="#bbbbbb", marker=".") ax.plot(X[different, 0], X[different, 1], "w", markerfacecolor="m", marker=".") ax.set_title("Difference") ax.set_xticks(()) ax.set_yticks(())plt.show()

三、K-Mediods

3.1 概念

??$K?Mediods$ 是基于原型的另一種聚類算法，也是對 $K?Means$ 算法的一種改進。

算法描述

隨機選取一組樣本作為中心點集；

每個中心點對應一個簇；

計算各樣本點到各個中心點的距離（如歐氏距離），將樣本點放入距離中心點最短的那個簇中；

計算各簇中，距簇內各樣本點距離的絕對誤差最小的點，作為新的中心點；

如果新的中心點集與原中心點集相同，算法終止；如果新的中心點集與原中心點集不完全相同，返回2)。

3.2 算法對比

??$K?Mediods$ 聚類算法原理和 $K?Means$ 大體相似，算法流程基本一致，不同的是:

• 質心的計算方式不同

  • $K?Means$ 聚類算法更新聚簇中心的時候直接計算均值，以均值點作為新的中心，可能是樣本點中不存在的點；而 $K?Mediods$更新聚簇中心是計算每一個點到簇內其他點的距離之和，選擇距離和最小的點來作為新的聚簇中心，質心必須是某些樣本點的值。

• $K?Mediods$ 可以避免數據中的異常值帶來的影響。

  • 如一個二維的樣本集劃分的簇是 $\{(1，1)，(1，2)，(2，1)，(1000，1000)\}$，其中 $(1000，1000)$ 是噪聲點。按照 $K?Means$ 算法，該樣本集的質心則為 $(502，502)$，但這個新的質心并不是該樣本集大多數正常樣本點圍繞的中心；如果是選擇 $K?Medoids$ 就可以避免這種情況，它會在 $\{(1，1)，(1，2)，(2，1)，(1000，1000)\}$中選出一個樣本點使它到其他所有點的距離之和絕對誤差最小，計算可知一定會在前三個點中選取。

• $K?Mediods$ 聚類算法原理和 $K?Means$ 大體相似，算法流程基本一致，不同的是:

  • 質心的計算復雜度更高：在質心的選取上，$K?Means$ 只需要計算每個劃分的簇均值中心點獲得新的質心，而 $K?Medoids$ 需要計算每個簇任兩點之間的距離，再對每個距離進行比較獲取新的質心，計算復雜度增加，運行速度會較慢；

  • 穩定性更高、執行速度變慢：對于有異常值的小樣本量數據集， $K?Mediods$ 比 $K?Means$ 效果更穩定，但是隨著數據集規模增加，$K?Mediods$ 算法的執行速度會慢很多；

  • 如果數據集本身不存在特別多的異常值，也不需要使用 $K?Mediods$ 替代 $K?Means$ 。

    ??$K?Mediods$ 每次迭代后的質點都是從聚類的樣本點中選取，而選取的標準就是當該樣本點成為新的質點后能提高類簇的聚類質量，使得類簇更緊湊。該算法使用絕對誤差標準來定義一個類簇的緊湊程度

四、特性

$K?Means$：

---

優點：

簡單，易于理解，運算速度快；

對處理大數據集，該算法可保持可伸縮性和高效性；

當簇接近高斯分布時，它的效果較好；

缺點：

$K?Means$ 算法是局部最優的，容易受到初始質心的影響；

在 $K?Means$ 算法中 $K$ 值是需要事先給定的，有時候 $K$ 值非常難以估計；

在簇的平均值可被定義的情況下才能使用，只能應用連續型數據；

大數據情況下算法的開銷是非常大的；

對噪聲和孤立點數據敏感。

---

$K?Medios$：

---

優點：

$K?Medios$ 算法具有處理大數據集的能力

結果簇相當緊湊，并且簇與簇之間明顯分明；

相比于 $K?Means$ 對噪聲點不敏感；

缺點：

只適用于連續型數據；

只適用于聚類結果為凸性的數據集等；

必須事先確定 $K$ 值；

一般在一個局部最優的解后就停止了。

---

區別：

與$K?Means$ 相比，$K?Medios$ 算法對于噪聲不那么敏感，這樣對于離群點就不會造成劃分的結果偏差過大，少數數據不會造成重大影響；

$K?Medios$ 由于上述原因被認為是對 $K?Means$ 改進，但由于中心點的選擇的方式進行計算，算法的時間復雜度也比 $K?Means$ 上升了 $O(n)$。

. 相比于 $K?Means$ 對噪聲點不敏感；

缺點：

只適用于連續型數據；

只適用于聚類結果為凸性的數據集等；

必須事先確定 $K$ 值；

一般在一個局部最優的解后就停止了。

---

區別：

與$K?Means$ 相比，$K?Medios$ 算法對于噪聲不那么敏感，這樣對于離群點就不會造成劃分的結果偏差過大，少數數據不會造成重大影響；

$K?Medios$ 由于上述原因被認為是對 $K?Means$ 改進，但由于中心點的選擇的方式進行計算，算法的時間復雜度也比 $K?Means$ 上升了 $O(n)$。

總結

以上是生活随笔為你收集整理的2.基于原型的聚类方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。