第九届机器学习理解相似度度量各种方法与相互

本次目 DensityPeak密度最大值考虑谱聚类和PCA的关聚类的无监相似度/距离计算方法总闵可夫斯基距离Minkowski/欧式距

distX,YAA

xi

1p杰卡德相似系数

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这即解释了为何文档间求距离使用夹角余弦——因为这一物量表征了文档去均值化后的随机向量间相关系数聚类的每一个簇至少包含一个对每一个对象属于且仅属于一个将满足上述条件的k个簇称作一个合理划k-Means算假定输入样本为S=x1,x2,...,xm，则算法步骤为选择初始的k个类别中心对于每个样本xi，将其标记为距离类别中心最近的类别，即

xi将每个类别中心更新为隶属该类别的所有样本的均jj|cj

重复最后两步，直到类别中心的变化小于某阈值k-Means过

对k-Means的思改成求数组的中位数3，在该实例中更为稳妥这种聚类方式即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聚类方法总优点缺可作为其他聚类方法的基础算法，如谱聚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轮廓系数etter.Rousseeuw于1986提出。aiai说明样本越应该被聚类到该簇。将ai称为样本的。计算样本到其他某簇jbj，j簇间不相似度

bi1,i轮廓系数根据样本i的簇内不相似度ai和簇间不相似度bi，义样本i的轮廓系数

ai,

aisi

bi

si

ai

ais-1，则说明i近似为0，则说所有样本的i层次聚类方到某种条件满足为止。具体又可分为：凝聚的层次聚类：AGNES算的层次聚类：DIANA算AGNES和DIANA算AGNES(AGglomerativeNESting)算法最初将每个对DIANA(DIvisive 层次聚AGNES中簇间距离的不同定最小距最大距离平均距离方差密度聚类方于某阈值，则将该样本添加到最近的簇中。(凸)的聚类的缺点，可发现任意形状的聚类，DBSCAN算 DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)DBSCAN算法的若对象的ε-邻域：给定对象在半径ε内的区 邻域至少包含m个对象，则称该对象为对象的ε-邻域内，而q是一个对象，我们说对象p从DBSCAN算法的若pi∈D，(1≤in)，pi+1是从pi关于ε和m直接密度可达的，则对DBSCAN算DBSCAN算法流程 寻找并合 有上述算法可知每个簇至少包含一 对象 参数

参数

密度最密度最大值聚类是一种简洁优美的聚类算法可以识别各种形状的类簇,并且参数很容易确定。定义：局部密度i

dij

其中，x

xdc是一个截断距离ρi即到对象i的距离小于dc的对象的个数。由于该算法只对ρi的相对值敏感,所以对dc的选择是定义：高局部密度点距离局部密度的其他定

其中，x

xj

2

i

exp ij

jIS

dci

KKjK

dij

di

di,K1高局部密度点距高局部密度点距离i

ijj:j簇中心的识DensityPeak与决策图Decision 的分布,右图是以ρ为横坐标,以δ为纵坐标绘制的决策图。可以看到，1和10边界和噪声的重认(borderregion)，亦即划分给该簇但是距离其他簇的 不同数据下密度最大值聚类的效AffinityAP算法调复习：实对称阵的特征值是实首

Ax

Ax

x因从

xTAxxTAx

xTAxxTxTATxAx

xT

xxTxT

xT

xTx而xT

nn

xi

nx0inx0i所 0实对称阵不同特征值的特征向量正λ1λ2μ1μ2都是实数或是实向量

A

T

T

1

1 1ATT1

212T12

T 1222 T 1222

T

T111222T 111222谱和谱方阵的谱半径为最大的特征矩阵A的谱半径：(ATA)的最大特征样本数据的拉斯矩阵的特征向量进行聚谱分析的整体过形成相似度图(similaritygraph)：G=(V,E)。若干概顶点的度di→度矩阵D对角阵若干概相似度图G的建立方xxix2高斯相似ε

,x

i i给定参数ε/如何选择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}，簇的数目计算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}，簇的数目计算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}，簇的数目 一个实

聚类效

聚类失进一步谱聚类中的K如何确定k

arg

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

k 未正则/对称/随机拉斯矩阵，首选哪个随机拉谱聚类可以用切割图/随机/扰动论等解释随 和 斯矩阵的关图论中的随机是一个随机过程，它从一图的一个划分，使得随机在相同的簇中停留而几乎不会到其他簇。

P传递算 传递算法(LabelPropagation传递过带宽/邻域影k- 谱聚类与图像切总降维、矩阵分解等内容的联系。在数据量极大的情况下，优先选择kMeans伸缩性好，时间复杂度为OtkN在需要给定Kelbow方法、轮廓系数、困惑度(perplexit等指标。聚类也有可能作为其他算法的实现，如矢量量参考文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