第九屆機器學習理解相似度度量各種方法與相互

本次目 DensityPeak密度最大值考慮譜聚類和PCA的關聚類的無監(jiān)相似度/距離計算方法總閔可夫斯基距離Minkowski/歐式距

distX,YAA

xi

1p杰卡德相似系數(shù)

JA,B

A aTb余弦相似度(cosine

cos

an

Pearson相似系

XY

n

22

nn

相對熵(K-L距離

x

22

inger距

Dp||q

1

px

qx

inger

1

1

pxqx

2

DH

dx

ppxxqxqx

余弦相似度與Pearson相似系n

xT

xixnn xnn

xix

yiyn 2niXy2iYcovX,Y

EX Y

xi

X

YXY

X

XY這即解釋了為何文檔間求距離使用夾角余弦——因為這一物量表征了文檔去均值化后的隨機向量間相關系數(shù)聚類的每一個簇至少包含一個對每一個對象屬于且僅屬于一個將滿足上述條件的k個簇稱作一個合理劃k-Means算假定輸入樣本為S=x1,x2,...,xm，則算法步驟為選擇初始的k個類別中心對于每個樣本xi，將其標記為距離類別中心最近的類別，即

xi將每個類別中心更新為隸屬該類別的所有樣本的均jj|cj

重復最后兩步，直到類別中心的變化小于某閾值k-Means過

對k-Means的思改成求數(shù)組的中位數(shù)3，在該實例中更為穩(wěn)妥這種聚類方式即k-Mediods聚類(K中值距離如何避免k-Means是初值敏感二分k-k-Means的公式化解記K個簇中心為12,

N1N2,NN

1

2,

2

xi j1N對關于12,kN

N令令

xi

N N如果使用其他相似度/距離度xT如：余弦相似度：cosx,

xx xx NN

1

2 1,

2,

2cos

j1N對關于12,kN

令令

j

j

j？Mini-batchk-Means算法描Mini-batchk-Means效k-Means適用范

k-Means++算法測k-Means聚類方法總優(yōu)點缺可作為其他聚類方法的基礎算法，如譜聚Canopy算 出色，算法描述如下,x1x2xm形成列表L；構造xj1jm的空列表Cj計算L中樣本xj與c的距離d若djr1，則在Lxj，將Cj賦值為否則，若djr2，則將Cj增加Canopy的調

聚類的

ifHC

h

HC

一個簇只包含一個類別的樣本，則滿足均

ifHK

c

HK|CHK

同類別樣本被歸類到相同簇中，則滿足完

v

1hh均一性和完整性 平CCsumX1Xn21n22XrnrssumNXX1,X2,XrYY1,Y2,Ys

nijCCi,2C 2i2aCbjC2ni12 2iC2j 2C22ijijij

XiARI

Index MaxIndex互信息/MIX,Y

rr

ssj

Pi,jPiPj

NMIX,Y

MIX,YHXHXHYij

minai,bi

ai!bj

a!Nb EMI

PXxMIX,Y

MI

x!Nab xmax1,aibiN

x

MIX,YEMIX,YmaxHX,HYEMIX,Y輪廓系數(shù)etter.Rousseeuw于1986提出。aiai說明樣本越應該被聚類到該簇。將ai稱為樣本的。計算樣本到其他某簇jbj，j簇間不相似度

bi1,i輪廓系數(shù)根據(jù)樣本i的簇內不相似度ai和簇間不相似度bi，義樣本i的輪廓系數(shù)

ai,

aisi

bi

si

ai

ais-1，則說明i近似為0，則說所有樣本的i層次聚類方到某種條件滿足為止。具體又可分為：凝聚的層次聚類：AGNES算的層次聚類：DIANA算AGNES和DIANA算AGNES(AGglomerativeNESting)算法最初將每個對DIANA(DIvisive 層次聚AGNES中簇間距離的不同定最小距最大距離平均距離方差密度聚類方于某閾值，則將該樣本添加到最近的簇中。(凸)的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，DBSCAN算 DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)DBSCAN算法的若對象的ε-鄰域：給定對象在半徑ε內的區(qū) 鄰域至少包含m個對象，則稱該對象為對象的ε-鄰域內，而q是一個對象，我們說對象p從DBSCAN算法的若pi∈D，(1≤in)，pi+1是從pi關于ε和m直接密度可達的，則對DBSCAN算DBSCAN算法流程 尋找并合 有上述算法可知每個簇至少包含一 對象 參數(shù)

參數(shù)

密度最密度最大值聚類是一種簡潔優(yōu)美的聚類算法可以識別各種形狀的類簇,并且參數(shù)很容易確定。定義：局部密度i

dij

其中，x

xdc是一個截斷距離ρi即到對象i的距離小于dc的對象的個數(shù)。由于該算法只對ρi的相對值敏感,所以對dc的選擇是定義：高局部密度點距離局部密度的其他定

其中，x

xj

2

i

exp ij

jIS

dci

KKjK

dij

di

di,K1高局部密度點距高局部密度點距離i

ijj:j簇中心的識DensityPeak與決策圖Decision 的分布,右圖是以ρ為橫坐標,以δ為縱坐標繪制的決策圖?？梢钥吹?，1和10邊界和噪聲的重認(borderregion)，亦即劃分給該簇但是距離其他簇的 不同數(shù)據(jù)下密度最大值聚類的效AffinityAP算法調復習：實對稱陣的特征值是實首

Ax

Ax

x因從

xTAxxTAx

xTAxxTxTATxAx

xT

xxTxT

xT

xTx而xT

nn

xi

nx0inx0i所 0實對稱陣不同特征值的特征向量正λ1λ2μ1μ2都是實數(shù)或是實向量

A

T

T

1

1 1ATT1

212T12

T 1222 T 1222

T

T111222T 111222譜和譜方陣的譜半徑為最大的特征矩陣A的譜半徑：(ATA)的最大特征樣本數(shù)據(jù)的拉斯矩陣的特征向量進行聚譜分析的整體過形成相似度圖(similaritygraph)：G=(V,E)。若干概頂點的度di→度矩陣D對角陣若干概相似度圖G的建立方xxix2高斯相似ε

,x

i i給定參數(shù)ε/如何選擇k近鄰圖(k-nearestneighbor若vi的k最近鄰包含vj，vj的k最近鄰不一定包含vi：有忽略方向的圖，往往簡稱“k近鄰圖兩者都滿足才連接的圖，稱作“互k近鄰圖相似度圖G的舉 斯矩陣及其性 斯矩陣：L=D– fTLffTDffTWfdf2

ff1

n

i,j22di

2

fifj

djf

i,j

j n21n2

wff i,jL是對稱半正定矩陣，最小特征值是0向量。 斯矩陣的定計算點之間的鄰接相似度矩陣W的第i行元素的和為vi的度。形成頂點度對角陣dii表示第i未正則的 斯矩陣LD正則 斯矩對稱 斯矩

D

LD

ID

WD隨 斯矩Random

D1L

譜聚類算法：未正則 斯矩輸入：n個點{pi}，簇的數(shù)目計算n×n的相似度矩陣W和度矩陣計算 斯矩陣L=D-計算L的前k個特征向量將k個列向量u1,u2,...,uk組成矩陣對于i=1,2,...,n,令yi∈Rk是U的第i行的向量使用k-means算法將點(yi)i=1,2,...,n聚類成輸出簇A1,A2,...Ak，其中譜聚類算法：隨 斯矩輸入：n個點{pi}，簇的數(shù)目計算n×n的相似度矩陣W和度矩陣計算正則 斯矩陣Lrw=D-1(D-計算Lrw的前k個特征向量將k個列向量u1,u2,...,uk組成矩陣U，U∈Rn×k對于i=1,2,...,n,令yi∈Rk是U的第i行的向量使用k-means算法將點(yi)i=1,2,...,n聚類成C1,C2,...Ck輸出簇A1,A2,...Ak，其中譜聚類算法：對稱 斯矩輸入：n個點{pi}，簇的數(shù)目 一個實

聚類效

聚類失進一步譜聚類中的K如何確定k

arg

k最后一步K-Means的作用是什么

k 未正則/對稱/隨機拉斯矩陣，首選哪個隨機拉譜聚類可以用切割圖/隨機/擾動論等解釋隨 和 斯矩陣的關圖論中的隨機是一個隨機過程，它從一圖的一個劃分，使得隨機在相同的簇中停留而幾乎不會到其他簇。

P傳遞算 傳遞算法(LabelPropagation傳遞過帶寬/鄰域影k- 譜聚類與圖像切總降維、矩陣分解等內容的聯(lián)系。在數(shù)據(jù)量極大的情況下，優(yōu)先選擇kMeans伸縮性好，時間復雜度為OtkN在需要給定Kelbow方法、輪廓系數(shù)、困惑度(perplexit等指標。聚類也有可能作為其他算法的實現(xiàn)，如矢量量參考文AlexRodriguez,AlessandroLaio.Clusteringbyfastsearchandfindofdensitypeak.Science.2014UlrikevonLuxburg.Atutorialonspectralclustering.LangK.Fixin oweaknessesofthespectralmethod.AdvancesinNeuralInformationProcessingSystems18,715–722.MITPress,Cambridge,2006BachF,JordanM.Learningspectralclustering.AdvancesinNeuralProcessingSystems16(NIPS).305–312.MITPress,AndrewRosenberg,JuliaHirschberg,V-Measure:Aconditionalentropy-basedclusterevaluationmeasure,W.M.Rand.Objectivecriteriafortheevaluationofclusteringmethods.JournaloftheAmericanSta