距离度量和链接标准
距离度量
距离度量是定义数据点之间相似度的方法。它是一种用来衡量两个数据点之间差异的函数。常见的距离度量包括:
-
欧氏距离(Euclidean distance):最常用的距离度量,它是两点之间的直线距离。
d(x,y)=i=1∑n(xi−yi)2.
-
曼哈顿距离(Manhattan distance):两点在标准坐标系上的绝对轴距总和。
d(x,y)=i=1∑n∣xi−yi∣.
-
余弦相似度(Cosine similarity):度量两个向量夹角的余弦值,常用于文本数据。
similarity(x,y)=∣x∣∣y∣x⋅y.
余弦距离通常用1减去余弦相似度来表示:
d(x,y)=1−similarity(x,y).
-
杰卡德相似系数(Jaccard similarity coefficient):用于度量集合相似度的一种指标。
如果将两个集合分别表示为A和B,则杰卡德相似系数定义为:
J(A,B)=∣A∪B∣∣A∩B∣.
杰卡德距离则为1减去杰卡德相似系数:
d(A,B)=1−J(A,B).
链接标准
链接标准(Linkage Criteria)是定义簇之间距离的方法,它是层次聚类算法中用来决定簇合并顺序的规则。主要的链接标准有:
-
最近邻链(Single Linkage): 簇间的距离定义为簇中最接近的两个点的距离。
dsingle(Ci,Cj)=x∈Ci,y∈Cjmind(x,y).
-
最远邻链(Complete Linkage):簇间的距离定义为簇中最远的两个点的距离。
dcomplete(Ci,Cj)=x∈Ci,y∈Cjmaxd(x,y).
-
平均链(Average Linkage): 簇间的距离定义为簇中所有点对距离的平均值。
daverage(Ci,Cj)=∣Ci∣∣Cj∣1x∈Ci∑y∈Cj∑d(x,y).
-
中心链(Centroid Linkage): 簇间的距离定义为簇中心点之间的距离。
dcentroid(Ci,Cj)=d(ci,cj).
其中 ci 和 cj 分别是簇 Ci 和簇 Cj 的中心。
-
Ward方法:簇间的距离定义为合并两个簇后总的方差增加量。
dWard(Ci,Cj)=∣Ci∣+∣Cj∣∣Ci∣∣Cj∣x∈Ci∪Cj∑(x−c)2.
其中 c 是合并后簇 Ci∪Cj 的中心。
在这些公式中,x 和 y 表示数据点,Ci 和 Cj 表示簇,d(x,y) 表示数据点 x 和 y 之间的距离,n 是特征的维度。对于集合型数据,A 和 B 表示两个数据集,∣A∩B∣ 表示集合 A 和 B 的交集的元素个数,∣A∪B∣ 集合 A 和 B 的并集的元素个数。