距離度量以及性能評估方法

一.距離度量

對于聚類，其實之前已經(jīng)有算法涉及了，比如GMM，這一章開始再次做系統(tǒng)介紹。聚類的核心思想套用一句俗語：“物以類聚，人與群分”，這里面首先有一個“距離”的概念，“聚”是因為“距離近”，“分”是因為“距離遠”，下面將常用的“距離”羅列一下，首先定義，樣本x_i=(x_{i1},x_{i2},...,x_{in})與樣本點x_j=(x_{j1},x_{j2},...,x_{jn})

明科夫斯基距離

d_{ij}=(\sum_{k=1}^n \left|x_{ik}-x_{jk}\right|^p)^{\frac{1}{p}}

這里，p\geq 1，當p=2時稱為歐氏距離，p=1稱為曼哈頓距離，p=\infty稱為切比雪夫距離，這時：

d_{ij}=\max_{k}\left|x_{ik}-x_{jk}\right|

馬氏距離

d_{ij}=\left[(x_i-x_j)^TS^{-1}(x_i-x_j)\right]^{\frac{1}{2}}

這里，S為整個樣本集X=(x_{ij})_{m\times n}的協(xié)方差矩陣

相關系數(shù)

r_{ij}=\frac{(x_i-\bar{x_i})^T(x_j-\bar{x_j})}{[(x_i-\bar{x_i})^T(x_i-\bar{x_i})\cdot (x_j-\bar{x_j})^T(x_j-\bar{x_j})]^{\frac{1}{2}}},\bar{x_i}=\frac{1}{n}\sum_{k=1}^nx_{ik},\bar{x_j}=\frac{1}{n}\sum_{k=1}^nx_{jk}\\ d_{ij}=1-r_{ij}

夾角余弦

s_{ij}=\frac{x_i^Tx_j}{[x_i^Tx_i\cdot x_j^Tx_j]^{\frac{1}{2}}}\\ d_{ij}=1-s_{ij}

二.類的定義

有了“距離”的定義，我們就可以進一步定義類了，設T為給定的正數(shù)，若樣本集合G中任意兩個樣本x_i,x_j，有：

d_{ij}\leq T

三.性能評估

接下來，我們繼續(xù)考慮聚類效果的好壞評估標準，顯然需要符合我們期望的“物以類聚，人以群分”，有了“距離”的定義之后，我們可以換一個表述：類內(nèi)距離盡可能小，類間距離盡可能大，所以我們進一步需要對類內(nèi)距離和類間距離做一個定義

類內(nèi)距離

類內(nèi)最大距離

類中任意兩個樣本之間的最大距離
diam(G)=\max_{x_i,x_j\in G}d_{ij}

類內(nèi)平均距離

類內(nèi)任意兩樣本之間距離的均值

avg(G)=\frac{1}{n_G(n_G-1)}\sum_{x_i\in G}\sum_{x_j\in G}d_{ij}

散布矩陣

A_G=\sum_{i=1}^{n_G}(x_i-\bar{x_G})(x_i-\bar{x_G})^T,\bar{x_G}=\sum_{i=1}^{n_G}x_i

協(xié)方差矩陣

S_G=\frac{1}{n-1}A_G

這里，n為樣本的維數(shù)

類間距離

設兩類分別為G_q和G_p

最短距離

d_{min}(G_p,G_q)=\min\{d_{ij}\mid x_i\in G_p,x_j\in G_q\}

最長距離

d_{max}(G_p,G_q)\max\{d_{ij}\mid x_i\in G_p,x_j\in G_q\}

中心距離

d_{cen}(G_p,G_q)=d_{\bar{x}_p\bar{x}_q}
這里，\bar{x}_p和\bar{x}_q分別為類G_p和G_q的中心點

平均距離

d_{avg}(G_p,G_q)=\frac{1}{n_{G_p}n_{G_q}}\sum_{x_i\in G_p}\sum_{x_j\in G_q}d_{ij}

性能評估

所以，我們在此基礎上可以構(gòu)造既能反映類內(nèi)距離，又能反映類間距離的指標

DB 指數(shù)

DBI=\frac{1}{k}\sum_{i=1}^k\max_{j\neq i}(\frac{avg(G_i)+avg(G_j)}{d_{cen}(G_i,G_j)})

顯然，DBI越小越好

Dunn指數(shù)

DI=\min_{1\leq i\leq k}\left\{\min_{j\neq i}(\frac{d_{min}(G_i,G_j)}{\max_{1\leq l\leq k}diam(G_l)})\right \}

顯然，DI越大越好

輪廓系數(shù)

SCI=\frac{1}{m}\sum_{i=1}^m\frac{b(x_i)-a(x_i)}{max(b(x_i),a(x_i))}

其中，a(\cdot)表示當前樣本與簇內(nèi)其他樣本的平均距離，所以a(\cdot)越小，反映了該簇越聚集，b(\cdot)表示當前樣本與其他簇的平均距離的最小值，所以b(\cdot)越大，表示與其他簇越分離，而輪廓系數(shù)SCI便是所有樣本輪廓系數(shù)的均值，可以看出SCI越大越好

則稱G為一個類（簇）

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容