文章目錄

• • 1. 聚類基本概念
  • • 1.1 相似度、距離
    • 1.2 類、簇
    • 1.3 類之間的距離
  • 2. 層次聚類
  • 3. K均值聚類
  • • 3.1 模型
    • 3.2 策略
    • 3.3 算法
    • 3.4 算法特性
  • 4. sklearn.cluster
  • • 4.1 sklearn.cluster.KMeans k均值聚類
    • 4.2 Hierarchical clustering 層次聚類

• 聚類：依據樣本特征的相似度或距離，將其歸并到若干個“類”或“簇”的數據分析問題

• 聚類目的：通過得到的類或簇來發(fā)現數據的特點或對數據進行處理，在數據挖掘、模式識別等領域有著廣泛的應用

• 聚類 屬于無監(jiān)督學習，因為只是根據樣本的相似度或距離將其進行歸類，而類或簇事先并不知道

1. 聚類基本概念

1.1 相似度、距離

• 有多種相似度或距離的定義
• 相似度直接影響聚類的結果，其選擇很關鍵

閔可夫斯基距離 ：$d_{ij}=(\sum _{k=1}^m|x_{ki}?x_{kj}{|}^p{)}^{\frac{1}{p}}$ , 距離越大，相似度越小
$p=1$, 曼哈頓距離
$p=2$, 歐式距離
$p=\infty$, 切比雪夫距離，$d_{ij}=\underset{k}{\max }|x_{ki}?x_{kj}|$

---

馬哈拉諾比斯距離： 考慮各個分量（特征）之間的相關性，與各個分量的尺度無關，距離越大，相似度越小

$$d_{ij}=[(x_i?x_j{)}^T{S}^{?1}(x_i?x_j){]}^{1/2},S為樣本協方差矩陣$$
馬氏距離是歐氏距離的推廣。

---

相關系數：其絕對值越接近1，越相似；越接近0，越不相似
$$r_{ij}=\frac{\sum _{k=1}^m(x_{ki}?{\bar{x}}_i)(x_{kj}?{\bar{x}}_j)}{[\sum _{k=1}^m(x_{ki}?{\bar{x}}_i{)}^2\sum _{k=1}^m(x_{kj}?{\bar{x}}_j{)}^2{]}^{1/2}}$$

---

夾角余弦： 夾角余弦越接近于1，表示樣本越相似；越接近于0，表示樣本越不相似
$$s_{ij}=\frac{\sum _{k=1}^m{x}_{ki}{x}_{kj}}{[\sum _{k=1}^m{x}_{ki}^2\sum _{k=1}^m{x}_{kj}^2{]}^{1/2}}$$

• 從距離的角度看，A和B比A和C更相似
• 從相關系數的角度看，A和C比A和B更相似
• 進行聚類時，選擇適合的距離或相似度非常重要

1.2 類、簇

• 聚類得到的類或簇，本質是樣本的子集
• 如果假定一個樣本只能屬于一個類，或類的交集為空集，稱為硬聚類（hard clustering）
• 如果一個樣本可以屬于多個類，或類的交集不為空集，稱為軟聚類（soft clustering）

類、簇定義

$d_{ij}\le T$ ，最常用，且能推出下面的

$\frac{1}{n_G?1}\sum _{x_j\in G}{d}_{ij}\le T$

$\frac{1}{n_G(n_G?1)}\sum _{x_i\in G}\sum _{x_j\in G}{d}_{ij}\le T,d_{ij}\le V$

類的特征：

• 類的均值（中心）：${\bar{x}}_G=\frac{1}{n_G}\sum _{i=1}^{n_G}{x}_i$
• 類的直徑：$D_G=\underset{x_i,x_j\in G}{\max }{d}_{ij}$
• 類的樣本散布矩陣：$A_G=\sum _{i=1}^{n_G}(x_i?{\bar{x}}_G)(x_i?{\bar{x}}_G{)}^T$
• 類的樣本協方差矩陣：$S_G=\frac{1}{m?1}{A}_G=\frac{1}{m?1}\sum _{i=1}^{n_G}(x_i?{\bar{x}}_G)(x_i?{\bar{x}}_G{)}^T,m樣本維數$

1.3 類之間的距離

• 最短距離或單連接：$D_{pq}=\min \{d_{ij}|x_i\in G_p,x_j\in G_q\}$

• 最長距離或完全連接：$D_{pq}=\max \{d_{ij}|x_i\in G_p,x_j\in G_q\}$

• 中心距離：$D_{pq}=d_{{\bar{x}}_p{\bar{x}}_q}$

• 平均距離：$D_{pq}=\frac{1}{n_p{n}_q}\sum _{x_i\in G_p}\sum _{x_j\in G_q}{d}_{ij}$

2. 層次聚類

• 層次聚類 假設類別之間 存在層次結構，將樣本聚到層次化的類中
• 層次聚類：有聚合（agglomerative）或自下而上（bottom-up）聚類、分裂（divisive）或自上而下（top-down）聚類 兩種方法
• 每個樣本只屬于 一個類，所以層次聚類屬于 硬聚類

聚合聚類：

• 將每個樣本 各自分到一個類
• 之后將相距最近的兩類合并，建立一個新的類
• 重復上一步直到滿足停止條件；得到層次化的類別

分裂聚類：

• 將所有樣本分到一個類
• 之后將已有類中相距最遠的樣本分到兩個新的類
• 重復上一步直到滿足停止條件；得到層次化的類別。

聚合聚類的具體過程如下：

• 對給定的樣本集合，開始將每個樣本分到一個類
• 按照一定規(guī)則，例如 類間距離最小，將 最 滿足規(guī)則條件的兩個類進行合并
• 反復上一步，每次減少一個類，直到滿足停止條件，如 所有樣本聚為一類

聚合聚類需要預先確定三要素：

• （1）距離或相似度（閔可夫斯基距離、馬哈拉諾比斯距離、相關系數、夾角余弦）
• （2）合并規(guī)則（類間距離最小，可以是 最短距離、最長距離、中心距離、平均距離）
• （3）停止條件（類的個數達到閾值（極端情況類的個數是1）、類的直徑超過閾值）

3. K均值聚類

k均值 聚類：是基于樣本集合劃分的聚類算法

• 將樣本集合劃分為 k 個子集，構成 k 個類
• 將 n 個樣本分到 k 個類中，每個樣本到其所屬類的中心的距離最小
• 每個樣本只能屬于一個類，是硬聚類

3.1 模型

n 個樣本 劃分成 k 個類，類之間的交集為空（硬聚類）

3.2 策略

策略：通過損失函數的最小化 選取 最優(yōu)的劃分 或 函數 $C^{?}$

• 樣本距離：歐氏距離，$d(x_i,x_j)=||x_i?x_j|{|}^2$
• 損失函數：樣本與其類屬的中心的距離總和，
  $W(C)=\sum _{l=1}^k\sum _{C(i)=l}||x_i?{\bar{x}}_l|{|}^2$
• 本質：求解最優(yōu)化問題
  $C^{?}=\underset{C}{\mathrm{argmin}}W(C)=\underset{C}{\mathrm{argmin}}\sum _{l=1}^k\sum _{C(i)=l}||x_i?{\bar{x}}_l|{|}^2$

n 個樣本 劃分成 k 個類，組合數是指數級的，其最優(yōu)解求解是 NP 困難問題，常用迭代求解

3.3 算法

k均值聚類 的算法是迭代的過程，每次迭代包括兩個步驟

• 首先隨機選擇 k 個類的中心（選 k 個樣本），將其余樣本逐個指派到與其最近的中心的類中，得到一個聚類結果
• 然后更新每個類的樣本的均值，作為類的新的中心
• 重復以上步驟，直到收斂

3.4 算法特性

1. 總體特點

• 基于劃分的聚類方法
• 類別數 k 事先指定
• 以歐氏距離平方表示樣本之間的距離
• 以中心或樣本的 均值 表示類別
• 以 樣本 和 其所屬類的中心 之間的 距離的總和 為最優(yōu)化目標函數
• 得到的類別是平坦的、非層次化的
• 是迭代算法，不能 保證得到全局最優(yōu)

2. 收斂性

• k均值 聚類屬于啟發(fā)式方法，不能 保證收斂到全局最優(yōu)
• 初始中心的選擇 會 直接影響聚類結果
• 類中心在聚類的過程中會發(fā)生移動，但是往往不會移動太大，因為在每一步，樣本被分到與其最近的中心的類中

3. 初始類的選擇

• 選擇不同的初始中心，會得到不同的聚類結果
• 初始中心的選擇，比如 可以用層次聚類對樣本進行聚類，得到k個類時停止。然后從每個類中選取一個與中心距離最近的點

4. 類別數k的選擇

• k 值需要預先指定，而在實際應用中最優(yōu)k值是不知道的
• 解決方法：嘗試不同的k值，檢驗聚類的質量，推測最優(yōu)的k值
• 聚類結果的質量：可以用類的平均直徑來衡量
• 一般地，類別數變小時，平均直徑會增加；類別數變大超過某個值以后，平均直徑會不變；而這個值正是最優(yōu)的k值
• 可以采用二分查找，快速找最優(yōu)的k值

4. sklearn.cluster

sklearn.cluster 官網介紹了10種聚類算法。

4.1 sklearn.cluster.KMeans k均值聚類

sklearn.cluster.KMeans 官網參數介紹

class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=None, algorithm='auto')

主要參數：

• n_clusters, default=8
  類的個數，即k值

• init：{‘k-means++’, ‘random’}
  初始中心選擇，默認選項更好

• n_init, default=10
  多次初始化，然后聚類，最后取最好的聚類結果

• max_iter, default=300
  單次聚類的最大迭代次數

• tol, default=1e-4
  迭代停止精度

• precompute_distances：‘auto’ or bool, default=’auto’
  預先計算距離

• algorithm：{“auto”, “full”, “elkan”}, default=”auto”
  迭代算法.
  The classical EM-style algorithm is “full”.
  The “elkan” variation is more efficient by using the triangle inequality, but currently doesn’t support sparse data.
  “auto” chooses “elkan” for dense data and “full” for sparse data.

---

代碼示例：

from sklearn.cluster import KMeans import numpy as np # 書上例題 X = np.array([[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]]) kms = KMeans(n_clusters=2).fit(X) print(kms.labels_) print(kms.cluster_centers_)

運行結果：

[0 0 0 1 1] [[0.33333333 0.66666667][5. 1. ]]

4.2 Hierarchical clustering 層次聚類

sklearn.cluster.AgglomerativeClustering

class sklearn.cluster.AgglomerativeClustering(n_clusters=2, affinity='euclidean', memory=None, connectivity=None, compute_full_tree='auto', linkage='ward', distance_threshold=None)

官方代碼示例

總結

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

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