魏秀參

周旺第九章：聚類大綱聚類任務性能度量距離計算原型聚類密度聚類

層次聚類大綱聚類任務

性能度量距離計算原型聚類密度聚類

層次聚類聚類任務在“無監督學習”任務中研究最多、應用最廣.聚類目標：將數據集中的樣本劃分為若干個通常不相交的子集（“簇”，cluster）.聚類既可以作為一個單獨過程（用于找尋數據內在的分布結構），

也可作為分類等其他學習任務的前驅過程.聚類任務形式化描述

假定樣本集

包含個無標記樣本,每個樣本

是一個維的特征向量，聚類算法將樣本集

劃分成個不相交的簇

。其中，且

。。

相應地，用

表示樣本

的“簇標記”（即clusterlabel）,即

。于是，聚類的結果可用包含

個元素的簇標記向量表示。大綱

聚類任務性能度量距離計算原型聚類密度聚類

層次聚類性能度量聚類性能度量，亦稱為聚類“有效性指標”（validityindex）直觀來講：

我們希望“物以類聚”，即同一簇的樣本盡可能彼此相似，不同簇的樣本盡可能不同。換言之，聚類結果的“簇內相似度”（intra-clustersimilarity）高，且“簇間相似度”（inter-clustersimilarity）低，這樣的聚類效果較好.性能度量聚類性能度量：外部指標(externalindex)

將聚類結果與某個“參考模型”(referencemodel)進行比較。內部指標(internalindex)

直接考察聚類結果而不用任何參考模型。性能度量

對數據集，假定通過聚類得到的簇劃分為

，參考模型給出的簇劃分為 .相應地，令與分別表示與和對應的簇標記向量.

我們將樣本兩兩配對考慮，定義

性能度量-外部指標Jaccard系數（JaccardCoefficient,JC）FM指數（FowlkesandMallowsIndex,FMI）Rand指數（RandIndex,RI）[0,1]區間內,越大越好.性能度量–內部指標考慮聚類結果的簇劃分

，定義簇內樣本間的平均距離

簇內樣本間的最遠距離

簇與簇最近樣本間的距離簇

與簇中心點間的距離性能度量–內部指標DB指數（Davies-BouldinIndex,DBI）Dunn指數（DunnIndex,DI）越小越好.越大越好.大綱

聚類任務

性能度量

距離計算原型聚類密度聚類

層次聚類距離計算距離度量的性質：

非負性：

同一性：當且僅當

對稱性：

直遞性：距離計算距離度量的性質：

非負性：

同一性：當且僅當

對稱性：

直遞性：常用距離： 閔可夫斯基距離（Minkowskidistance）: p=2:歐氏距離（Euclideandistance）.

p=1：曼哈頓距離（Manhattandistance）.距離計算屬性介紹連續屬性(continuousattribute)

在定義域上有無窮多個可能的取值離散屬性(categoricalattribute)

在定義域上是有限個可能的取值距離計算屬性介紹連續屬性(continuousattribute)

在定義域上有無窮多個可能的取值離散屬性(categoricalattribute)

在定義域上是有限個可能的取值有序屬性(ordinalattribute)

例如定義域為{1,2,3}的離散屬性，“1”與“2”比較接近、與“3”比較遠，稱為“有序屬性”。無序屬性(non-ordinalattribute)

例如定義域為{飛機，火車，輪船}這樣的離散屬性，不能直接在屬性值上進行計算，稱為“無序屬性”。距離度量ValueDifferenceMetric,VDM（處理無序屬性）：

令表示屬性上取值為的樣本數，表示在第個樣本簇中在屬性上取值為的樣本數，為樣本數，則屬性上兩個離散值與之間的VDM距離為距離度量MinkovDMp（處理混合屬性）：加權距離（樣本中不同屬性的重要性不同時）：大綱

聚類任務

性能度量距離計算原型聚類密度聚類

層次聚類原型聚類原型聚類

也稱為“基于原型的聚類”(prototype-basedclustering)，此類算法假設聚類結構能通過一組原型刻畫。算法過程：

通常情況下，算法先對原型進行初始化，再對原型進行迭代更新求解。接下來，介紹幾種著名的原型聚類算法

k均值算法、學習向量量化算法、高斯混合聚類算法。原型聚類–k均值算法給定數據集

，

k均值算法針對聚類所得簇劃分

最小化平方誤差

其中，是簇的均值向量。

值在一定程度上刻畫了簇內樣本圍繞簇均值向量的緊密程度，值越小，則簇內樣本相似度越高。原型聚類–k均值算法給定數據集

，

k均值算法針對聚類所得簇劃分

最小化平方誤差

其中，是簇的均值向量。

值在一定程度上刻畫了簇內樣本圍繞簇均值向量的緊密程度，值越小，則簇內樣本相似度越高。算法流程（迭代優化）：初始化每個簇的均值向量repeat 1.（更新）簇劃分；

2.計算每個簇的均值向量until當前均值向量均未更新原型聚類–k均值算法算法偽代碼：原型聚類–k均值算法k均值算法實例

接下來以表9-1的西瓜數據集4.0為例，來演示k均值算法的學習過程。將編號為的樣本稱為.原型聚類–k均值算法k均值算法實例假定聚類簇數k=3，算法開始時，隨機選擇3個樣本

作為初始均值向量，即

。

考察樣本

，它與當前均值向量的距離分別為0.369，0.506，0.166，因此將被劃入簇中。類似的，對數據集中的所有樣本考察一遍后，可得當前簇劃分為

于是，可以從分別求得新的均值向量

不斷重復上述過程，如下圖所示。

原型聚類–k均值算法聚類結果：原型聚類–學習向量量化學習向量量化（LearningVectorQuantization,LVQ）

與一般聚類算法不同的是，LVQ假設數據樣本帶有類別標記，學習過程中利用樣本的這些監督信息來輔助聚類.

給定樣本集

，LVQ的目標是學得一組維原型向量，每個原型向量代表一個聚類簇。原型聚類–學習向量量化算法偽代碼：原型聚類–學習向量量化聚類效果：原型聚類–高斯混合聚類

與k均值、LVQ用原型向量來刻畫聚類結構不同，高斯混合聚類（Mixture-of-Gaussian）采用概率模型來表達聚類原型：多元高斯分布的定義對維樣本空間中的隨機向量，若服從高斯分布，其概率密度函數為

其中是維均值向量，

是的協方差矩陣。也可將概率密度函數記作。原型聚類–高斯混合聚類高斯混合分布的定義

該分布由個混合分布組成，每個分布對應一個高斯分布。其中，

與是第個高斯混合成分的參數。而為相應的“混合系數”，。

原型聚類–高斯混合聚類

原型聚類–高斯混合聚類模型求解：最大化（對數）似然令：高斯混合聚類–模型求解（續）令：高斯混合聚類算法偽代碼：高斯混合聚類聚類效果：大綱

聚類任務性能度量距離計算原型聚類

密度聚類

層次聚類密度聚類密度聚類的定義

密度聚類也稱為“基于密度的聚類”(density-basedclustering)。此類算法假設聚類結構能通過樣本分布的緊密程度來確定。

通常情況下，密度聚類算法從樣本密度的角度來考察樣本之間的可連接性，并基于可連接樣本不斷擴展聚類簇來獲得最終的聚類結果。

接下來介紹DBSCAN這一密度聚類算法。密度聚類DBSCAN算法：基于一組“鄰域”參數來刻畫樣本分布的緊密程度。基本概念：鄰域：對樣本，其鄰域包含樣本集

中與的距離不大于的樣本；核心對象：若樣本的鄰域至少包含MinPts個樣本，則該樣本點為一個核心對象；密度直達：若樣本位于樣本的鄰域中，且是一個核心對象，則稱樣本由密度直達；密度可達：對樣本與，若存在樣本序列，其中

且由密度直達，則該兩樣本密度可達；

密度相連：對樣本與，若存在樣本使得兩樣本均由密度可達，則稱該兩樣本密度相連。密度聚類

密度聚類

密度聚類DBSCAN算法偽代碼：密度聚類聚類效果：大綱

聚類任務性能度量距離計算原型聚類密度聚類

層次聚類層次聚類層次聚類試圖在不同層次對數據集進行劃分，從而形成樹形的聚類結構。數據集劃分既可采用“自底向上”的聚合策略