9.1 聚類任務(wù)

常見的無監(jiān)督學(xué)習(xí)任務(wù)

密度估計
異常檢測
聚類

聚類任務(wù)將數(shù)據(jù)集劃分為若干個不相交的子集，為每一個樣本標(biāo)上一個簇標(biāo)記(表示這個樣本屬于哪個簇)，于是得到一個簇標(biāo)記向量?

9.2 性能度量

在開始一項機(jī)器學(xué)習(xí)任務(wù)之前，首先必須要定義好性能度量指標(biāo)，以便量化的評估模型的好壞。

聚類性能度量的基本想法

“物以類聚”，相同簇內(nèi)的樣本應(yīng)該盡可能的相似；“人以群分”，不同簇內(nèi)的樣本應(yīng)該經(jīng)可能的不同。需要定義距離來度量相似性。

兩類度量指標(biāo)

外部指標(biāo)通過和一個參考模型比較（即和一個專家進(jìn)行比較）
內(nèi)部指標(biāo)不借助任何參考模型

外部指標(biāo)

假定通過聚類給出的簇劃分為 $C = \{C_1...C_K\}$ , 參考模型給出的簇劃分為 $C^* = \{C_1^*...C_K^*\}$ , 令 $\lambda$ 與 $\lambda^*$ 分別表示聚類給出的簇標(biāo)記向量以及參考模型給出的簇標(biāo)記向量, 定義如下量

其中 $a$ 表示在中屬于同一個簇的且在中也屬于同一個簇的點(diǎn)對的集合，其他依次類推。顯然我們希望 $a$ 和 $b$ 越大越好。

由于一個點(diǎn)對只能出現(xiàn)在一個集合中，共有個點(diǎn)對，所以 $a + b + c + d = \frac{m(m - 1) }{2}$

Jaccard系數(shù)

顯然當(dāng) $a$ 和 $b$ 越大時，該系數(shù)越大，直觀的表達(dá)了聚類性能度量的基本想法

$JC = \frac{a}{a + b + c} = \frac{a}{S - b}$
FM系數(shù)

$FMI = \sqrt{\frac{a}{a + b}\frac{a}{a +c}}$
Rand指數(shù)

$RI = \frac{2(a + d)}{m(m - 1)}$

內(nèi)部指標(biāo)

簇內(nèi)樣本間平均距離

描述簇內(nèi)的聚合程度

簇內(nèi)樣本間最大距離

描述簇內(nèi)的聚合程度

簇間樣本最小距離

描述兩簇之間的距離

兩簇間樣本中心距離

描述兩簇簇之間的距離

DB指數(shù)

顯然任意兩簇樣本內(nèi)平均距離越小，樣本中心越遠(yuǎn)越好，所以DB指數(shù)越小越好
Dunn指數(shù)

顯然任意兩簇，簇內(nèi)最遠(yuǎn)距離越小，簇間最小距離越大越好，所以該指數(shù)越大越好

9.4 原型聚類

此類算法假設(shè)聚類結(jié)構(gòu)能夠通過一組原型刻畫，在聚類任務(wù)中較為通用。一般先對原型進(jìn)行初始化，然后再對原型進(jìn)行迭代更新求解

9.4.1 k均值算法

給定樣本?,k均值算法針對聚類所得簇劃分?最小化平方誤差,?

$E = \sum^k_{i = 1}\sum_{x \in C_i}||x - \mu_i||^2_2$

E值越小，簇內(nèi)樣本相似程度越高，求解該最優(yōu)劃分為NP難問題，k均值算法采用貪心策略通過迭代優(yōu)化來近似求解

算法流程

image

可設(shè)定最大迭代次數(shù)，或?的最小更新幅度閾值來防止迭代過久

9.4.2 學(xué)習(xí)向量量化(Learning Vector Quantization)

LVQ假設(shè)數(shù)據(jù)樣本帶有類別標(biāo)記，利用這些監(jiān)督信息來輔助聚類

算法流程

image

初始化原型向量可如下操作，對第個簇，從類別標(biāo)記相同的樣本中隨機(jī)選取一個作為原型向量
LVQ根據(jù)樣本與原型向量的距離來劃分簇，因此學(xué)得一組原型向量后，就得到了樣本空間上的一組劃分，稱為"Voronoi"劃分
學(xué)習(xí)率?越大，每次原型向量更新的幅度就越大
若將簇?所對應(yīng)的劃分區(qū)域?中的樣本全用原型向量?表示，則可實(shí)現(xiàn)數(shù)據(jù)的有損壓縮，稱為“向量量化”

9.4.3 高斯混合聚類

k均值和LVQ通過原型向量來刻畫聚類結(jié)構(gòu)，而高斯混合聚類通過概率模型來表達(dá)聚類原型

高斯分布

由 $n$ 維均值向量和 $n \times n$ 的協(xié)方差矩陣決定

高斯混合分布

數(shù)據(jù)分布由k個高斯成分混合而成，每個高斯分布都有一個混合系數(shù) $\alpha_i$ ,且 $\sum_{i=1}^{k}\alpha_i = 1$ ，則為樣本在生成過程中，選擇第個高斯分布的概率 $P(z_j = i)$ 對應(yīng)與 $\alpha_i$

聚類

訓(xùn)練集，令 $z_j \in \{1,2....k\}$ 表示生成樣本的高斯混合成分, 設(shè)后驗概率為 $p_M(z_j = i | x_j)$ , 簡記為 $\gamma_{ji}$ 由貝葉斯定義得的后驗分布為

image

高斯混合聚類把樣本D劃分為k個簇（對應(yīng)k個混合成分），每個樣本的簇標(biāo)記如下確定，選取簇標(biāo)記后驗概率最大的一個做為樣本的簇標(biāo)記,

image

模型參數(shù)由EM算法求取

由表達(dá)式看，參數(shù)通過樣本加權(quán)平均來估計，權(quán)重為每個樣本屬于該成分的后驗概率

算法流程

image

9.5 密度聚類

密度聚類假設(shè)聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定。

DBSCAN聚類

使用一組“鄰域”參數(shù)來刻畫樣本分布的緊密程度,數(shù)據(jù)集 $D = \{x_1....x_m\}$

$\epsilon$ -鄰域

對于樣本 $x_j \in D$ , $N_\epsilon = \{x_i \in D | dist(x_i,x_j) \leq \epsilon\}$ , 即與樣本之間的距離小于 $\epsilon$ 的樣本的集合
核心對象

若 $x_j$ 的 $\epsilon$ -鄰域內(nèi)至少包含個 $MinPts$ 樣本，則 $x_j$ 是一個核心對象
密度直達(dá)

若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -鄰域中，且 $x_i$ 是核心對象，則 $x_j$ 由 $x_i$ 密度直達(dá)
密度可達(dá)

若存在樣本序列 $p_1....p_n$ , 其中 $p_1 = x_i, p_n = x_j$ ,且 $p_{i + 1}$ 由 $p_i$ 密度直達(dá)，則 $x_j$ 由 $x_i$ 密度可達(dá)

即存在一條路徑使得可以到達(dá)的 $x_i$ 的 $\epsilon-$ 鄰域內(nèi)
密度相連

若 $x_i$ 與 $x_j$ 存在 $x_k$ , 使的 $x_i$ 與 $x_j$ 均由 $x_k$ 密度可達(dá)，則稱 $x_i$ 與 $x_j$ 密度相連