精华内容
下载资源
问答
  • 聚类算法中的距离度量
    千次阅读
    2021-03-04 09:59:09

    聚类算法性能度量

    该博客是基于python的机器学习包sklearn整理得到聚类算法的度量方式。是对sklearn包的用户文档的翻译并结合自己的一些理解。

    度量聚类算法的性能不是简单的统计错误的数量或计算监督分类算法中的准确率(precision)和召回率(recall)。 特别地,任何度量指标(evaluation metric)不应该考虑到簇标签的绝对值,而是如果这个聚类方式所分离数据类似于部分真实簇分类或者满足某些假设,在同于一个相似性度量(similarity metric)之下,使得属于同一个类内的成员比不同类的成员更加类似。也就是说:聚类作为无监督学习的一种方法,并不能单纯的以结果的准确性作为衡量算法好坏的唯一标准,没有绝对好的聚类算法,一个算法只需要以某一种特征作为类的划分准则,并将数据样本按照这一特征做出了划分,就是一个好的聚类算法。

    常用的度量聚类算法好坏的标准一共有10个,需要按照算法的特征选择合适的性能度量方法。

    一、兰德指数

    兰德指数分为调整的兰德指数和未调整的兰德指数。未调整的兰德指数类取值区间为 [ 0 , 1 ] [0,1] [0,1],没有一个固定的值表示两个随即标签的关系 ;调整的兰德指数将评分规范到了 [ − 1 , 1 ] [-1,1] [1,1]之间,以 0.0 0.0 0.0表示两个随机标签的关系。

    已知数据集真实簇标签分类labels_true,和我们的聚类算法基于相同样本所得到的预测标签分类labels_pred,兰德指数是一个函数,用于测量两个簇标签分配的值的相似度,忽略类簇的标识。

    from sklearn import metrics
    
    labels_true = [0, 0, 0, 1, 1, 1]
    labels_pred = [0, 0, 1, 1, 2, 2]
    metrics.adjusted_rand_score(labels_true, labels_pred) 
    
    print0.24...
    

    因为忽略类簇的标识,所以即使标识如下,得到的结果也是一样的

    labels_true = [0, 0, 0, 1, 1, 1]
    labels_pred = [1, 1, 3, 3, 5, 5]
    

    另外, adjusted_rand_score对称的,交换参数不会改变得分。

    metrics.adjusted_rand_score(labels_pred,labels_true) 
    

    完美的标签的得分为1.0,无相关标签的得分是负数或接近于0.0分。

    优点

    • 可解释性:未调整的兰德指数评分与labels_predlabels_true的数量成正比 。
    • 对于任意两个随机的标签组,其调整后的兰德系数接近0.0
    • 有界范围:调整或未调整的兰德指数,相似度越低得分越低,相似度越高,得分越高。
    • 无需对簇的结构进行任何假设**(就是上面解释的忽略类簇标识和参数对称)**:调整或未调整的兰德指数可用于比较各种聚类算法。

    缺点

    • 在无监督学习中,数据集一般是没有标注的,但是兰德系数要求数据有准确的标注。但是,兰德系数在纯无监督的环境中也可以用作共识索引的基础,该共识索引可以用于聚类模型选择(应该是对不同聚类算法的labels_pred之间进行评判,可以将结果更为相似的算法的labels_pred作为labels_true)。
    • 未经调整的兰德系数即使聚类本身存在显著差异,其结果也通常接近1.0。当将兰德系数解释为由聚类产生的结果labels_pred对标记labels_true的准确性时,更好理解。(应该是说在一个聚类算法中,当准确率取值大于0.5时,就用该数表示准确率;当准确率取值小于0.5时,就用1减去该数作为准确率)。

    数学公式

    如果C是一个真实簇的标签分配,K是簇的个数,我们定义ab如:

    • a为在C中的相同集合的与K中的相同集合中的元素对数
    • b为在C中的不同集合与K中的不同集合中的元素对数

    未经调整的兰德系数由下式给出:
    RI = a + b C 2 n s a m p l e s \text{RI} = \frac{a + b}{C_2^{n_{samples}}} RI=C2nsamplesa+b
    其中 C 2 n s a m p l e s C_2^{n_{samples}} C2nsamples为数据集中可能的数据对数**(不对数据进行排序,即将同一类放在一起)**。

    然而,RI 得分不能保证随机标签分配会获得接近零的值(特别是如果簇的数量与样本数量有着相同的规模排序)(所以要进行调整兰德系数)

    为了抵消这种影响,我们可以对预期的RI进行一种运算(discount) E [ RI ] E[\text{RI}] E[RI],通过如下定义调整后的兰德指数来设置随机标签:
    ARI = RI − E [ RI ] max ⁡ ( RI ) − E [ RI ] \text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]} ARI=max(RI)E[RI]RIE[RI]

    二、基于互信息的度量

    已知数据集真实簇标签分类labels_true,和我们的聚类算法基于相同样本所得到的预测标签分类labels_pred,互信息用于测量两个类簇标签的一致性,忽略标签的排列。这种测量方案有两个不同的标准化版本可用,Normalized Mutual Information(NMI) 和 Adjusted Mutual Information(AMI)(规范化互信息(NMI)和调整后的互信息(AMI))NMI在文献中经常使用,而AMI是最近才提出的,并针对偶然性进行了归一化

    from sklearn import metrics
    
    labels_true = [0, 0, 0, 1, 1, 1]
    labels_pred = [0, 0, 1, 1, 2, 2]
    metrics.adjusted_mutual_info_score(labels_true, labels_pred)
    
    print0.22504...
    
    • 在预测的标签列表中重新排列 0 和 1, 或把 2 重命名为 3, 得到相同的得分**(即忽略类簇标识和排列)**。
    • mutual_info_score(为上诉的MI),adjusted_mutual_info_score(为上述AMI)和 normalized_mutual_info_score(为上述NMI)三个函数的参数是对称的,互换位置不影响评测结果。
    • 完美标签得分为1.0,但是mutual_info_score(为上诉的MI)的完美标签得分不为1.0
    • mutual_info_score(为上诉的MI),adjusted_mutual_info_score(为上述AMI)和 normalized_mutual_info_score(为上述NMI)三种方法对随机标签的得分为负数。

    优点

    • 随机标签的AMI得分接近0.0
    • 数值趋近于零,是说明两个标签分配之间是独立,无关联;而数值趋近于一时, 表示两者之间有着极高的一致性。 甚至,当AMI的取值正好是 1 时, 说明两个标签分配时完全相等的**(无论是否排列过)**。

    缺点

    • 在无监督学习中,数据集一般是没有标注的,但是基于互信息的度量所使用的数据需要有标注
    • NMI 和 MI 不能进行使得随机标签度量的得分为0的调整**(可以理解为该性能度量即使对一个对标签预测完全错误的算法也不会得0分)**。

    数学公式

    假设有两个标签分配U和V(两个结果集),其中具有相同的标签对数N,它们的熵是分区集的不确定性量,其定义为:
    H ( U ) = − ∑ i = 1 ∣ U ∣ P ( i ) log ⁡ ( P ( i ) ) H(U) = - \sum_{i=1}^{|U|}P(i)\log(P(i)) H(U)=i=1UP(i)log(P(i))
    其中 P ( i ) = ∣ U i ∣ / N P(i) = |U_i| / N P(i)=Ui/N是从U中随机选取得对象,选取对象落入到类 U i U_i Ui的概率。

    同样,对于V:
    H ( V ) = − ∑ j = 1 ∣ V ∣ P ′ ( j ) log ⁡ ( P ′ ( j ) ) H(V) = - \sum_{j=1}^{|V|}P'(j)\log(P'(j)) H(V)=j=1VP(j)log(P(j))
    使用 P ′ ( j ) = ∣ V j ∣ / N P'(j) = |V_j| / N P(j)=Vj/N和V之间的mutual information (MI) 由下式计算:
    MI ( U , V ) = ∑ i = 1 ∣ U ∣ ∑ j = 1 ∣ V ∣ P ( i , j ) log ⁡ ( P ( i , j ) P ( i ) P ′ ( j ) ) \text{MI}(U, V) = \sum_{i=1}^{|U|}\sum_{j=1}^{|V|}P(i, j)\log\left(\frac{P(i,j)}{P(i)P'(j)}\right) MI(U,V)=i=1Uj=1VP(i,j)log(P(i)P(j)P(i,j))
    其中 P ( i , j ) = ∣ U i ∩ V j ∣ / N P(i, j) = |U_i \cap V_j| / N P(i,j)=UiVj/N是随机选择的对象同时落入两个类的概率 U i U_i Ui V i V_i Vi

    也可以用设定的基数表达式表示:
    MI ( U , V ) = ∑ i = 1 ∣ U ∣ ∑ j = 1 ∣ V ∣ ∣ U i ∩ V j ∣ N log ⁡ ( N ∣ U i ∩ V j ∣ ∣ U i ∣ ∣ V j ∣ ) \text{MI}(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \frac{|U_i \cap V_j|}{N}\log\left(\frac{N|U_i \cap V_j|}{|U_i||V_j|}\right) MI(U,V)=i=1Uj=1VNUiVjlog(UiVjNUiVj)
    归一化被定义为:
    NMI ( U , V ) = MI ( U , V ) mean ( H ( U ) , H ( V ) ) \text{NMI}(U, V) = \frac{\text{MI}(U, V)}{\text{mean}(H(U), H(V))} NMI(U,V)=mean(H(U),H(V))MI(U,V)
    mutual information(MI) 的值以及归一化变量的值都不会为随机标签度量而调整,但是会随着不同的簇标签数量的增加,不管标签分配之间的 mutual information(MI)的实际数量如何,都会趋向于增加。

    可以使用以下公式计算互信息的期望值在这个等式中 a i = ∣ U i ∣ a_i = |U_i| ai=Ui(中的元素数 U i U_i Ui) 和 b j = ∣ V j ∣ b_j = |V_j| bj=Vj (中的元素数 V j V_j Vj)。
    E [ MI ( U , V ) ] = ∑ i = 1 ∣ U ∣ ∑ j = 1 ∣ V ∣ ∑ n i j = ( a i + b j − N ) + min ⁡ ( a i , b j ) n i j N log ⁡ ( N . n i j a i b j ) a i ! b j ! ( N − a i ) ! ( N − b j ) ! N ! n i j ! ( a i − n i j ) ! ( b j − n i j ) ! ( N − a i − b j + n i j ) ! E[\text{MI}(U,V)]=\sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \sum_{n_{ij}=(a_i+b_j-N)^+ }^{\min(a_i, b_j)} \frac{n_{ij}}{N}\log \left( \frac{ N.n_{ij}}{a_i b_j}\right) \frac{a_i!b_j!(N-a_i)!(N-b_j)!}{N!n_{ij}!(a_i-n_{ij})!(b_j-n_{ij})! (N-a_i-b_j+n_{ij})!} E[MI(U,V)]=i=1Uj=1Vnij=(ai+bjN)+min(ai,bj)Nnijlog(aibjN.nij)N!nij!(ainij)!(bjnij)!(Naibj+nij)!ai!bj!(Nai)!(Nbj)!
    使用期望值,可以使用与调整后的兰德指数相似的形式来计算调整后的共同信息:
    AMI = MI − E [ MI ] mean ( H ( U ) , H ( V ) ) − E [ MI ] \text{AMI} = \frac{\text{MI} - E[\text{MI}]}{\text{mean}(H(U), H(V)) - E[\text{MI}]} AMI=mean(H(U),H(V))E[MI]MIE[MI]
    对于归一化的互信息和调整后的互信息,归一化值通常是每个聚类的熵的某个广义均值。存在各种广义的手段,并且不存在确定一种偏于另一种的坚决规则。该决定在很大程度上是逐个领域进行的;例如,在社区检测中,算术平均值是最常见的。每种归一化方法都提供“定性相似的行为”,在我们的实现中,这由average_method参数控制。

    三、同质性,完整性和 V-measure

    已知真实簇标签分配,可以使用 条件熵分析来定义一些直观的度量

    特别是 Rosenberg 和 Hirschberg (2007) 为任何簇分配定义了以下两个理想的目标:

    • 同质性(homogeneity): 每个簇只包含一个类的成员
    • 完整性(completeness): 给定类的所有成员都分配给同一个簇

    我们可以把这些概念转化为得分homogeneity_scorecompleteness_score。两者均在 0.0 以下 和 1.0 以上(越高越好):

    from sklearn import metrics
    
    labels_true = [0, 0, 0, 1, 1, 1]
    labels_pred = [0, 0, 1, 1, 2, 2]
    metrics.homogeneity_score(labels_true, labels_pred)
    print:0.66
    metrics.completeness_score(labels_true, labels_pred)
    print:0.42
    

    称为 V-measure 的调和平均数(harmonic mean)由以下函数计算 v_measure_score,该函数公式如下:
    v = ( 1 + β ) × homogeneity × completeness ( β × homogeneity + completeness ) v = \frac{(1 + \beta) \times \text{homogeneity} \times \text{completeness}}{(\beta \times \text{homogeneity} + \text{completeness})} v=(β×homogeneity+completeness)(1+β)×homogeneity×completeness
    beta默认值为1.0,但对于beta使用小于1的值,则为:

    metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
    print:0.54...
    

    更大的beta权重将提高同质性,当使用大于1的beta值时:

    metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
    print:0.48...
    

    进一步增大的beta权重将提高完整性。

    V-measure 实际上等于上面讨论的 mutual information (NMI) , 仅仅是聚合函数(aggregation function)是算术均值.

    同质性, 完整性 and V-measure 可以使用homogeneity_completeness_v_measure进行计算 如下:

    metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
    print:(0.66..., 0.42..., 0.51...)
    

    以下聚类分配稍微好一些,因为它是同质但并不完整:

    labels_pred = [0, 0, 0, 1, 2, 2]
    metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
    print:(1.0, 0.68..., 0.81...)
    

    注意: v_measure_score是对称的: 它可以用于评估同一数据集上两个 无相关标签分配(independent assignments)的 一致性completeness_score homogeneity_score却不适用于上述情况: 两者间存在下述约束:

    py homogeneity_score(a, b) == completeness_score(b, a)

    优点

    • Bounded scores(有界的分数): 0.0 是最坏的, 1.0 是一个完美的分数.
    • Intuitive interpretation(直观解释): 具有不良 V-measure 的聚类可以在同质性和完整性方面进行定性分析以更好地感知到标签分配过程中的错误类型。
    • No assumption is made on the cluster structure(对簇的结构没有作出任何假设): 可以用于比较不同类的聚类算法,例如: k-means 和 spectral clustering algorithms(谱聚类算法)间的比较。虽然,前者的簇是isotropic blob shapes, 后者的簇是 folded shapes。

    缺点

    • 之前介绍的度量标准(metrics)并不针对随机标记进行标准化(not normalized with regards to random labeling): 这意味着,依赖样本数量,簇数量和 标定过的真实数据类数量,完全随机的标注方式并不总是产生 同质性,完整性 和 v-measure 的相同值。特别是 随机标注不会产生零分,特别是当簇数量大时。

      当样本数量超过 1000,簇的数量小于 10 时,可以安全地忽略此问题。对于较小的样本数量或者较大数量的簇,使用 adjusted index 例如 Adjusted Rand Index (ARI))。

    在这里插入图片描述

    数学公式

    同质性和完整性的得分由下面公式给出:
    h = 1 − H ( C ∣ K ) H ( C ) h = 1 - \frac{H(C|K)}{H(C)} h=1H(C)H(CK)

    c = 1 − H ( K ∣ C ) H ( K ) c = 1 - \frac{H(K|C)}{H(K)} c=1H(K)H(KC)

    其中 H ( C ∣ K ) H(C|K) H(CK)是给定簇分配的类的条件熵,由下式给出:
    H ( C ∣ K ) = − ∑ c = 1 ∣ C ∣ ∑ k = 1 ∣ K ∣ n c , k n ⋅ log ⁡ ( n c , k n k ) H(C|K) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{n_{c,k}}{n} \cdot \log\left(\frac{n_{c,k}}{n_k}\right) H(CK)=c=1Ck=1Knnc,klog(nknc,k)
    并且 H ( C ) H(C) H(C)是已聚合的类的熵,并且由下式给出:
    H ( C ) = − ∑ c = 1 ∣ C ∣ n c n ⋅ log ⁡ ( n c n ) H(C) = - \sum_{c=1}^{|C|} \frac{n_c}{n} \cdot \log\left(\frac{n_c}{n}\right) H(C)=c=1Cnnclog(nnc)
    n n n 样本总数 n c n_c nc n k n_k nk 分别是属于类别的样本数 c c c 和集群 k k k的样本数,最后 n c , k n_{c,k} nc,k 分配给类 c c c 和簇 k k k 的样本数。

    给定类分配的簇的条件熵 H ( K ∣ C ) H(K|C) H(KC)和簇的熵 H ( K ) H(K) H(K)以对称的形式定义。

    Rosenberg 和 Hirschberg 进一步定义 V-measure 作为同质性和完整性的调和均值:
    v = 2 ⋅ h ⋅ c h + c v = 2 \cdot \frac{h \cdot c}{h + c} v=2h+chc

    四、Fowlkes-Mallows 得分

    当数据集的分类情况已知时,可以使用Fowlkes-Mallows得分(sklearn.metrics.fowlkes_mallows_score) 。Fowlkes-Mallows 得分 FMI 被定义为 成对的准确率和召回率的几何平均值:
    FMI = TP ( TP + FP ) ( TP + FN ) \text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP}) (\text{TP} + \text{FN})}} FMI=(TP+FP)(TP+FN) TP
    其中的 TP真正例(True Positive) 的数量(即,真实标签组和预测标签组中属于相同簇的点对数),FP假正例(False Positive) (即,在真实标签组中属于同一簇的点对数,而不在预测标签组中),FN假负例(False Negative) 的数量(即,预测标签组中属于同一簇的点对数,而不在真实标签组中)。

    • 得分范围为 0 到 1。较高的值表示两个簇之间的良好相似性。
    from sklearn import metrics
    
    labels_true = [0, 0, 0, 1, 1, 1]
    labels_pred = [0, 0, 1, 1, 2, 2]
    metrics.fowlkes_mallows_score(labels_true, labels_pred)
    print:0.47140...
    
    • 在预测的标签列表中重新排列 0 和 1, 或把 2 重命名为 3, 得到相同的得分**(即忽略类簇标识和排列)**。
    • 完美的标签得分是 1.0
    • 无相关标签的得分为 0

    优点

    • 随机标签的FMI得分接近0.0
    • 正好为0的值表示完全独立的标签分配
    • 对簇的结构没有任何要求,可以用于比较不同类的聚类算法

    缺点

    • 基于 FMI 的测量方案需要使用有标注的数据集

    五、 Silhouette 系数(轮廓系数)

    若数据集未标注,则聚类算法的性能必须使用模型本身进行评估。轮廓系数(sklearn.metrics.silhouette_score)是这种评估的一种方法 ,更好的聚类模型会得到更好地轮廓系数得分。为每个样本定义了轮廓系数,该系数由两个分数组成:

    • a:样本与同一类别中所有其他点之间的平均距离。
    • b:样本与下一个最近的簇中所有其他点之间的平均距离。

    单个样本的轮廓系数s标识为:
    s = b − a m a x ( a , b ) s = \frac{b - a}{max(a, b)} s=max(a,b)ba
    一组样本的轮廓系数作为每个样本轮廓系数的平均值给出。

    from sklearn import metrics
    from sklearn.metrics import pairwise_distances
    from sklearn import datasets
    
    X, y = datasets.load_iris(return_X_y=True)
    

    在正常使用中,轮廓系数将应用于聚类分析的结果。

    import numpy as np
    from sklearn.cluster import KMeans
    
    kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
    labels = kmeans_model.labels_
    metrics.silhouette_score(X, labels, metric='euclidean')
    print0.55
    

    优点

    • 对于不正确的聚类,分数为-1;对于高密度的聚类,分数为+1;0附近表示重叠的聚类。
    • 当簇密集且分离较好时,分数更高。
    • 无需使用有标注的数据集。

    缺点

    凸簇的轮廓系数通常比其他类型的簇更高

    六、Calinski-Harabaz 指数

    如果数据集没有标注,则可以使用Calinski-Harabasz指数(sklearn.metrics.calinski_harabasz_score)(也称为方差比标准)来评估模型,其中较高的Calinski-Harabasz得分与具有更好定义的群集的模型有关。

    该指数是所有集群的集群间离散度和集群内离散度之和的比值(其中,离散度定义为距离平方的总和):

    from sklearn import metrics
    from sklearn.metrics import pairwise_distances
    from sklearn import datasets
    
    X, y = datasets.load_iris(return_X_y=True)
    

    在正常使用中,将Calinski-Harabasz指数应用于聚类分析的结果:

    import numpy as np
    from sklearn.cluster import KMeans
    
    kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
    labels = kmeans_model.labels_
    metrics.calinski_harabasz_score(X, labels)
    print:561.62...
    

    优点

    • 当群集密集且间隔良好时,分数会更高。
    • 该分数可以快速计算。

    缺点

    • 凸聚类的Calinski-Harabasz索引通常比聚类的其他概念更高,例如基于密度的聚类(如通过DBSCAN获得的聚类)。

    数学公式

    已知数据集 E E E的大小为 n E n_E nE,被分 k k k个集群,Calinski-Harabasz得分 s s s定义为群集间分散度平均值与群集内分散度的比率:
    s = t r ( B k ) t r ( W k ) × n E − k k − 1 s = \frac{\mathrm{tr}(B_k)}{\mathrm{tr}(W_k)} \times \frac{n_E - k}{k - 1} s=tr(Wk)tr(Bk)×k1nEk
    其中 t r ( B k ) \mathrm{tr}(B_k) tr(Bk)为组间方差矩阵的迹, t r ( W k ) \mathrm{tr}(W_k) tr(Wk)是簇内方差矩阵的迹:
    W k = ∑ q = 1 k ∑ x ∈ C q ( x − c q ) ( x − c q ) T W_k = \sum_{q=1}^k \sum_{x \in C_q} (x - c_q) (x - c_q)^T Wk=q=1kxCq(xcq)(xcq)T

    B k = ∑ q = 1 k n q ( c q − c E ) ( c q − c E ) T B_k = \sum_{q=1}^k n_q (c_q - c_E) (c_q - c_E)^T Bk=q=1knq(cqcE)(cqcE)T

    N N N为数据集中的点数, C q C_q Cq为簇 q q q中的点集, c q c_q cq为簇 q q q的中心, c c c E E E的中心, n q n_q nq为簇 q q q中的点数。

    七、Davies-Bouldin 指数

    如果数据集有标签,sklearn.metrics.davies_bouldin_score则可以使用Davies-Bouldin指数评估模型,Davies-Bouldin指数越低,聚类的效果越好。

    该指数表示聚类之间的平均“相似度”,其中相似度是一种将聚类之间的距离与聚类本身的大小进行比较的度量。

    将Davies-Bouldin索引应用于聚类分析的结果,如下所示:

    from sklearn import datasets
    iris = datasets.load_iris()
    X = iris.data
    from sklearn.cluster import KMeans
    from sklearn.metrics import davies_bouldin_score
    kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
    labels = kmeans.labels_
    davies_bouldin_score(X, labels)
    print:0.6619...
    

    优点

    • Davies-Bouldin 指数的计算比轮廓系数更加简单
    • Davies-Bouldin 指数仅用于计算数据集内的数量和特征

    缺点

    • 凸簇的Davies-Bouldin 指数通常比其他类型的簇更高。
    • 在一般情况下, 质心距离只能使用欧氏空间内的距离度量来衡量。
    • 该方法得出的一个好的值并不意味着这是最好的信息检测技术。

    数学公式

    Davies-Bouldin 指数定义为每个聚类之间的平均相似度, C i C_i Ci 为了 i = 1 , . . . , k i=1, ..., k i=1,...,k和它最相似的一个 C j C_j Cj。在该指数中,相似度被定义为一个用于协调的度量:

    • s i s_i si,集群中每个点之间的平均距离 i i i 以及该簇的质心-也称为簇直径。
    • d i j d_{ij} dij,簇质心之间的距离 i i i 和$ j$。

    以下是一个简单构建 R i j R_{ij} Rij 的方法,使得它具有非负性和对称性:
    R i j = s i + s j d i j R_{ij} = \frac{s_i + s_j}{d_{ij}} Rij=dijsi+sj
    然后将Davies-Bouldin 指数定义为:
    D B = 1 k ∑ i = 1 k max ⁡ i ≠ j R i j DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij} DB=k1i=1ki=jmaxRij

    八、Contingency Matrix(可能性矩阵)

    可能性矩阵记录了每个真实/预测簇对之间的交叉基数。可能性矩阵为所有的聚合度量提供了足量的统计数据,在这些度量中样本是独立同分布的。

    from sklearn.metrics.cluster import contingency_matrix
    x = ["a", "a", "a", "b", "b", "b"]
    y = [0, 0, 1, 1, 2, 2]
    contingency_matrix(x, y)
    print:array([[2, 1, 0],
           [0, 1, 2]])
    

    输出数组的第一行指示存在三个样本,其真实簇为“ a”。其中两个在预测聚类0中,一个在1中,一个都不在2中。第二行表示存在三个样本,其真实聚类为“ b”。其中,没有一个在预测聚类0中,一个在1中,两个在2中。

    用于聚类的可能性矩阵是一个square contingency matrix,其中行和列的顺序对应于类别列表。

    优点

    • 允许检查每个真实簇在预测簇中的分布,反之亦然。
    • 计算得出的列联表通常用于计算两个聚类之间的相似性统计信息(如本文档中列出的其他相似性统计信息)。

    缺点

    • 权变矩阵对于少量的群集很容易解释,但是对于大量的群集则很难解释。
    • 它没有给出一个单一的指标来用作集群优化的目标。

    九、Pair Confusion Matrix(配对混淆矩阵)

    配对混淆矩阵(sklearn.metrics.cluster.pair_confusion_matrix)是2x2相似矩阵。
    C = [ C 00 C 01 C 10 C 11 ] C = \left[\begin{matrix} C_{00} & C_{01} \\ C_{10} & C_{11} \end{matrix}\right] C=[C00C10C01C11]
    通过考虑所有样本对并计算在真实和预测聚类下分配到相同或不同聚类中的对来计算两个聚类之间的差。

    各个元素的含义为:

    C 00 C_{00} C00 :具有两个聚类且样本未聚在一起的对的数量

    C 10 C_{10} C10 :具有真实标签聚类且样本聚在一起但其他聚类中样本不聚在一起的对的数量

    C 01 C_{01} C01 :具有真实标签聚类的对的数量,这些聚类没有将样本聚类在一起,但是将样本聚在一起的其他聚类

    C 11 C_{11} C11 :具有两个聚类且样本被聚在一起的对的数量

    考虑一对成对的正样本,那么在二元分类中,真正的负数为 C 00 C_{00} C00,假阴性为 C 10 C_{10} C10,真正的积极因素是 C 01 C_{01} C01误报是 C 11 C_{11} C11

    完全匹配的标签在对角线上具有所有非零的条目,而不管实际的标签值如何:

    from sklearn.metrics.cluster import pair_confusion_matrix
    pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])
    print:array([[8, 0],
           [0, 4]])
    
    pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0])
    print:array([[8, 0],
           [0, 4]])
    

    将所有类成员分配到同一集群的标签是完整的,但可能并不总是绝对的,因此会受到惩罚,并且具有一些非对角线的非零条目:

    pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1])
    print:array([[8, 2],
           [0, 2]])
    

    矩阵不对称:

    pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])
    print:array([[8, 0],
           [2, 2]])
    

    如果将类成员完全拆分为不同的群集,则分配完全不完整,因此矩阵的对角线条目全部为零:

    pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3])
    print:array([[ 0,  0],
           [12,  0]])
    
    更多相关内容
  • 高维数据的增量式聚类算法距离度量选择研究.pdf
  • 聚类算法中距离度量有哪些

    千次阅读 2018-07-27 10:56:00
    一、你知道聚类中度量距离的方法有哪些吗?  1)欧式距离  欧氏距离是最易于理解的一种距离计算方法,源自欧氏空间两点间的距离公式。即两点之间直线距离,公式比较简单就不写了  应用场景:适用于求解两点...

    一、你知道聚类中度量距离的方法有哪些吗?

     1)欧式距离

     欧氏距离是最易于理解的一种距离计算方法,源自欧氏空间中两点间的距离公式。即两点之间直线距离,公式比较简单就不写了

     应用场景:适用于求解两点之间直线的距离,适用于各个向量标准统一的情况

     

     2)曼哈顿距离(Manhattan Distance)

     从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源, 曼哈顿距离也称为城市街区距离(City Block distance)

     应用场景:主要应用场景,如棋盘、城市里两个点之间的距离等

     

     3)切比雪夫距离 (Chebyshev Distance )

     国际象棋玩过么?国王走一步能够移动到相邻的8个方格中的任意一个(国王可以直行、横行、斜行,但是每次只能动一个格。国王是生命的象征,国王死掉,棋局结束)。那么国王从格子\((x_1,y_1)\)走到格子\((x_1,y_1)\)最少需要多少步?自己走走试试。你会发现最少步数总是\(max(|x_2-x_1|,|y_2-y_1|)\)步 。有一种类似的一种距离度量方法叫切比雪夫距离,公式是:

    \( Cdist = max(|x_i - y_i)) \)

     应用场景:计算国际象棋中国王走步

     

     4) 夹角余弦相似度(Cosine)

     夹角越小越相似,\(cos\theta = \frac{a^Tb}{|a||b|}\)

     应用场景:常用于文本识别,比如新闻的挖掘

     举例:

      文本1中词语a,b分别出现100,50次,向量表示为(100,50)

      文本2中词语a,b分别出现50,25次,向量表示为(50,25)

      文本3中词语a,b分别出现10,0次,向量表示为(10,0)

      文本4中词语a,b分别出现2,0次,向量表示为(2,0)

      可以得知,1,2点向量平行(词频比例相同),3,4点向量平行,那么是不是可以判断1,2文本更相似,3,4文本更相似呢?

     

     5)Pearson相关系数

     皮尔逊相关系数考察两个变量的关系,值越大,两个变量越近强相关,即距离越近,所以距离:\(dist(X,Y) = 1 - \rho_{X,Y}\)

     \(\rho_{X,Y} = Cov(X, Y)/\sigma_X\sigma_Y = E((X-\mu_X)(Y-\mu_Y))/\sigma_X\sigma_Y\)

     

     6)马氏距离

     用来度量一个样本点P与数据分布为D的集合的距离。

     假设一个样点P为:\(x = (x_1,x_2,x_3,...,x_N)^T\)

     数据集D均值为:\(\mu = (\mu_1,\mu_2,\mu_3,...,\mu_N)^T\),协方差矩阵是\(S\)

     则这个样本点P与数据集合D的马氏距离为:\(D_M(x) = \sqrt{(x-\mu)^TS^{-1}(x-\mu)}\)

     马氏距离也可以衡量两个来自同一分布的样本x和y的相似性,其中x和y是向量:\(d(x,y) = \sqrt{(x-y)^TS^{-1}(x-y)}\)

     当样本集合的协方差矩阵是单位矩阵时,即样本的各个维度上的方差均为1.马氏距离就等于欧式距离相等。 

     不难发现,如果去掉马氏距离中的协方差矩阵,就退化为欧氏距离。那么我们就需要探究这个多出来的因子究竟有什么含义

     例子:

      如果我们以厘米为单位来测量人的身高,以克(g)为单位测量人的体重。每个人被表示为一个两维向量,如一个人身高173cm,体重50000g,表示为(173,50000),根据身高体重的信息来判断体型的相似程度。

      我们已知小明(160,60000);小王(160,59000);小李(170,60000)。根据常识可以知道小明和小王体型相似。但是如果根据欧几里得距离来判断,小明和小王的距离要远远大于小明和小李之间的距离,即小明和小李体型相似。这是因为不同特征的度量标准之间存在差异而导致判断出错。

      以克(g)为单位测量人的体重,数据分布比较分散,即方差大,而以厘米为单位来测量人的身高,数据分布就相对集中,方差小。马氏距离的目的就是把方差归一化,使得特征之间的关系更加符合实际情况。

      图(a)展示了三个数据集的初始分布,看起来竖直方向上的那两个集合比较接近。在我们根据数据的协方差归一化空间之后,如图(b),实际上水平方向上的两个集合比较接近

     

     为什么马氏距离是与尺度无关的?

      也许你认为那只要将数据标准化后,不就可以计算距离了吗?但是如果是单纯使每个变量先标准化,然后再计算距离,可能会出现某种错误,原因是可能在有些多维空间中,某个两个维之间可能是线性相关的,协方差矩阵的引入可以去除特征的线性相关性。

     

     7)海明距离

      在信息领域,两个长度相等的字符串的海明距离是在相同位置上不同的字符的个数,也就是将一个字符串替换成另一个字符串需要的替换的次数。

      例如:

       "toned" and "roses" is 3

       1011101 and 1001001 is 2

       2173896 and 2233796 is 3

      海明距离若用于分类变量,如果X与Y的值相同,距离D为0,否则D为1:

    \(D_H = \sum_{i=1}^{n}|x_i - y_i|\)

    \(x=y => D = 0\)

    \(x\neq y => D = 1\)

     

    转载于:https://www.cnblogs.com/always-fight/p/9375099.html

    展开全文
  • 自定义距离距离

    转自:https://blog.csdn.net/qq_38563206/article/details/120941479

    scikit-learn是非常漂亮的一个机器学习库,在某些时候,使用这些库能够大量的节省你的时间,至少,我们用Python,应该是很难写出速度快如斯的代码的.

    scikit-learn官方出了一些文档,但是个人觉得,它的文档很多东西都没有讲清楚,它说算法原理的时候,只是描述一下,除非你对这种算法已经烂熟于心,才会对它的描述会心一笑,它描述API的时候,很多时候只是讲了一些常见用法,一些比较高级的用法就语焉不详,虽然有很多人说,这玩意的文档写得不错,但是我觉得特坑.所以这篇博文,会记录一些我使用这个库的时候碰到的一些坑,以及如何跨过这些坑.慢慢来更新吧,当然,以后如果不用了,文章估计也不会更新了,当然,我也没有打算说,这篇文章有多少人能看.就这样吧.

    聚类
    坑1: 如何自定义距离函数?
    虽然说scikit-learn这个库实现了很多的聚类函数,但是这些算法使用的距离大部分都是欧氏距离或者明科夫斯基距离,事实上,根据我们教材上的描述,所谓的距离,可不单单仅有这两种,为了不同的目的,我们可以用不同的距离来度量两个向量之间的距离,但是很遗憾,我并没有看见scikit-learn中提供自定义距离的选项,网上搜了一大圈也没有见到.

    但是不用担心,我们可以间接实现这个东西.以DBSCAN算法为例,下面是类的一个构造函数:

    class sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', algorithm='auto', leaf_size=30, p=None, n_jobs=1)
    # eps表示两个向量可以被视作为同一个类的最大的距离
    # min_samples表示一个类中至少要包含的元素数量,如果小于这个数量,那么不构成一个类
    

    我们要特别注意一下metric这个选项,我们来看一下选项:

    metric : string, or callable
        The metric to use when calculating distance between instances in a feature array. If metric is a string or callable, it must be one of the options allowed by metrics.pairwise.calculate_distance for its metric parameter. 
        If metric is “precomputed”, X is assumed to be a distance matrix and must be square. X may be a sparse matrix, in which case only “nonzero” elements may be considered neighbors for DBSCAN.
        New in version 0.17: metric precomputed to accept precomputed sparse matrix.
    

    这段描述其实透露了一个很重要的信息,那就是其实你可以自己提前计算各个向量的相似度,构成一个相似度的矩阵,只要你设置metric='precomputedd’就行,那么如何调用呢?

    我们来看一下fit函数.

    fit(X, y=None, sample_weight=None)
    # X : array or sparse (CSR) matrix of shape (n_samples, n_features), or array of shape (n_samples, n_samples)
    # A feature array, or array of distances between samples if metric='precomputed'.
    

    上面的注释是什么意思呢,我翻译一下,如果你将metric设置成了precomputed的话,那么传入的X参数应该为各个向量之间的相似度矩阵,然后fit函数会直接用你这个矩阵来进行计算.否则的话,你还是要乖乖地传入(n_samples, n_features)形式的向量.

    这意味着什么,同志们.这意味着我们可以用我们自定义的距离事先计算好各个向量的相似度,然后调用这个函数来获得结果,是不是很爽.

    具体怎么来编程,我给个例子,抛个砖.

    import numpy as np
    from sklearn.cluster import DBSCAN
    if __name__ == '__main__':
        Y = np.array([[0, 1, 2],
                      [1, 0, 3],
                      [2, 3, 0]]) # 相似度矩阵,距离越小代表两个向量距离越近
        # N = Y.shape[0]
        db = DBSCAN(eps=0.13, metric='precomputed', min_samples=3).fit(Y)
        labels = db.labels_
        # 然后来看一下分类的结果吧!
        n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0) # 类的数目
        print('类的数目是:%d'%(n_clusters_))
    

    我们继续来看一下AP聚类,其实也很类似:

    class sklearn.cluster.AffinityPropagation(damping=0.5, max_iter=200, convergence_iter=15, copy=True, preference=None, affinity='euclidean', verbose=False)
    

    关键在这个affinity参数上:

    affinity : string, optional, default=``euclidean``
        Which affinity to use. At the moment precomputed and euclidean are supported. euclidean uses the negative squared euclidean distance between points.
    

    这个东西也支持precomputed参数.再来看一下fit函数:

    fit(X, y=None)
    # Create affinity matrix from negative euclidean distances, then apply affinity propagation clustering.
    # Parameters:   
    #   X: array-like, shape (n_samples, n_features) or (n_samples, n_samples) :
    #   Data matrix or, if affinity is precomputed, matrix of similarities / affinities.
    

    这里的X和前面是类似的,如果你将metric设置成了precomputed的话,那么传入的X参数应该为各个向量之间的相似度矩阵,然后fit函数会直接用你这个矩阵来进行计算.否则的话,你还是要乖乖地传入(n_samples, n_features)形式的向量.

    例子1

    """
        目标:
        ~~~~~~~~~~~~~~~~
        在这个文件里面,我最想测试一下的是,我前面的那些聚类算法是否是正确的.
        首先要测试的是AP聚类.
    """
    from sklearn.cluster import AffinityPropagation
    from sklearn import metrics
    from sklearn.datasets.samples_generator import make_blobs
    from sklearn.metrics.pairwise import euclidean_distances
    import matplotlib.pyplot as plt
    from itertools import cycle
     
    def draw_pic(n_clusters, cluster_centers_indices, labels, X):
        ''' 口说无凭,绘制一张图就一目了然. '''
        colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
        for k, col in zip(range(n_clusters), colors):
            class_members = labels == k
            cluster_center = X[cluster_centers_indices[k]] # 得到聚类的中心
            plt.plot(X[class_members, 0], X[class_members, 1], col + '.')
            plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
                     markeredgecolor='k', markersize=14)
            for x in X[class_members]:
                plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)
     
        plt.title('Estimated number of clusters: %d' % n_clusters)
        plt.show()
     
     
    if __name__ == '__main__':
        centers = [[1, 1], [-1, -1], [1, -1]]
        # 接下来要生成300个点,并且每个点属于哪一个中心都要标记下来,记录到labels_true中.
        X, labels_true = make_blobs(n_samples=300, centers=centers,
                                    cluster_std=0.5, random_state=0)
        af = AffinityPropagation(preference=-50).fit(X) # 开始用AP聚类
        cluster_centers_indices = af.cluster_centers_indices_ # 得到聚类的中心点
        labels = af.labels_ # 得到label
        n_clusters = len(cluster_centers_indices) # 类的数目
        draw_pic(n_clusters, cluster_centers_indices, labels, X)
     
        #===========接下来的话提前计算好距离=================#
        distance_matrix = -euclidean_distances(X, squared=True) # 提前计算好欧几里德距离,需要注意的是,这里使用的是欧几里德距离的平方
        af1 = AffinityPropagation(affinity='precomputed', preference=-50).fit(distance_matrix)
        cluster_centers_indices1 = af1.cluster_centers_indices_ # 得到聚类的中心
        labels1 = af1.labels_ # 得到label
        n_clusters1 = len(cluster_centers_indices1) # 类的数目
        draw_pic(n_clusters1, cluster_centers_indices1, labels1, X)
    

    两种方法都将产生这样的图:
    在这里插入图片描述
    例子2
    既然都到这里了我们索性来测试一下DBSCAN算法好了

    """
        目标:
        ~~~~~~~~~~~~~~
        前面已经测试过了ap聚类,接下来测试DBSACN.
    """
    import numpy as np
    from sklearn.cluster import DBSCAN
    from sklearn import metrics
    from sklearn.datasets.samples_generator import make_blobs
    from sklearn.preprocessing import StandardScaler
    import matplotlib.pyplot as plt
    from sklearn.metrics.pairwise import euclidean_distances
     
    def draw_pic(n_clusters, core_samples_mask, labels, X):
        ''' 开始绘制图片 '''
        # Black removed and is used for noise instead.
        unique_labels = set(labels)
        colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
        for k, col in zip(unique_labels, colors):
            if k == -1:
                # Black used for noise.
                col = 'k'
     
            class_member_mask = (labels == k)
     
            xy = X[class_member_mask & core_samples_mask]
            plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                     markeredgecolor='k', markersize=14)
     
            xy = X[class_member_mask & ~core_samples_mask]
            plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                     markeredgecolor='k', markersize=6)
     
        plt.title('Estimated number of clusters: %d' % n_clusters)
        plt.show()
     
    if __name__ == '__main__':
        #=========首先产生数据===========#
        centers = [[1, 1], [-1, -1], [1, -1]]
        X, labels_true = make_blobs(n_samples=750, centers=centers,
                                    cluster_std=0.4, random_state=0)
        X = StandardScaler().fit_transform(X)
        #=========接下来开始聚类==========#
        db = DBSCAN(eps=0.3, min_samples=10).fit(X)
        labels = db.labels_ # 每个点的标签
        core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
        core_samples_mask[db.core_sample_indices_] = True
        n_clusters = len(set(labels)) - (1 if -1 in labels else 0) # 类的数目
        draw_pic(n_clusters, core_samples_mask, labels, X)
        #==========接下来我们提前计算好距离============#
        distance_matrix =  euclidean_distances(X)
        db1 = DBSCAN(eps=0.3, min_samples=10, metric='precomputed').fit(distance_matrix)
        labels1 = db1.labels_ # 每个点的标签
        core_samples_mask1 = np.zeros_like(db1.labels_, dtype=bool)
        core_samples_mask1[db1.core_sample_indices_] = True
        n_clusters1 = len(set(labels1)) - (1 if -1 in labels1 else 0) # 类的数目
        draw_pic(n_clusters1, core_samples_mask1, labels1, X)
    

    在这里插入图片描述

    好吧,暂时介绍到这里吧,但是有意思的是,最简单的KMeans算法倒是不支持这样的干活.

    参考资料
    [1] K-means聚类自定义距离计算 2020.5

    展开全文
  • 文中提出了一种基于距离度量聚类算法,算法使用新的距离度量代替了K均值聚类算法的欧式距离,应用新的距离度量之后,数据点的权重不再只为1或0,而是由系数 来确定,这就将硬划分转化为软划分。最后经过实验证明了...
  • 传统的K-Modes聚类算法采用简单的0-1匹配差异方法来计算同一分类属性下两...并将提出的距离度量应用于传统K-Modes聚类算法中.通过与基于其他距离度量的K-Modes聚类算法进行实验比较,结果表明新的距离度量是更加有效的.
  • 为此,提出一种以轨迹子段为聚类目标的聚类算法CTIHD。给出一种新的轨迹子段距离度量方法,用以消除轨迹子段之间的公共偏差。利用特征点概念将轨迹划分成轨迹子段集,计算轨迹子段之间的相似度,由此实现聚类。实验结果...
  • 改进的基于距离度量的无迭代K-means聚类算法
  • K-Means聚类是最常用的聚类算法,最初起源于信号处理,其目标是将数据点划分为K个类簇,找到每个簇的中心并使其度量最小化。该算法的最大优点是简单、便于理解,运算速度较快,缺点是只能应用于连续型数据,并且要在...
  • 基于距离度量学习的半监督多视角谱聚类算法.pdf
  • K-Means算法是一种基于划分的聚类算法,以距离作为数据对象间相似性度量的标准,即数据对象间的距离越小,则它们的相似性越高,则它们越有可能在同一个类簇。数据对象间距离的计算有很多种,k-means算法通常采用欧氏...
  • 首先介绍传统距离计算方法在聚类应用的不足,并针对这点提出一种基于权重向量的相对距离计算方法。在应用DBSCAN算法的基础上,融入相对距离的计算及k-d树的范围查找的应用。该算法不仅能得到很好的聚类效果,而且...
  • 一种改进的距离度量聚类算法.pdf
  • 基于DTW距离度量的层次聚类算法.pdf
  • 聚类分析中距离度量方法比较

    万次阅读 2018-08-08 15:28:06
    聚类分析如何度量两个对象之间的相似性呢?一般有两种方法,一种是对所有对象作特征投影,另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系,而后者则是通过衡量对象之间的差异度来反应对象...

    聚类分析中如何度量两个对象之间的相似性呢?一般有两种方法,一种是对所有对象作特征投影,另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系,而后者则是通过衡量对象之间的差异度来反应对象之间的相似度关系。

              如图(1)所示:假设X坐标轴为时间,Y坐标轴为繁殖率,则可以看出三种不同的物种在不同时间段的繁殖情况,由于分别在10,40,80三个数值附近,因此根据繁殖率这一特征便可以分辨出三种物种。特征投影比较直观,但是对象之间的相似性直接的依赖于测量的特征,换一种特征可能会有相反的效果。

             距离计算是最为常见的相似度度量方法,通常的对象a,b之间的相似度为Sim(a,b),对象a,b的测量距离为d(a,b),则一般采取Sim(a,b) = 1/(1+d(a,b))得到相似度。常见的距离计算方法有:

            (1)欧氏距离:可以简单的描述为多维空间的点点之间的几何距离,,需要注意的是,欧式距离通常采用的是原始数据,而并非规划化后的数据,比如有一属性在1-100内取值,那么便可以直接使用,而并非一定要将其归一到[0,1]区间使用。这样的话,欧式距离的原本意义便被消除了,正是因为这样,所以其优势在于新增对象不会影响到任意两个对象之间的距离。然而,如果对象属性的度量标准不一样,如在度量分数时采取十分制和百分制,对结果影响较大。

            (2)曼哈顿距离:如果欧式距离看成是多维空间对象点点的直线距离,那么曼哈顿距离就是计算从一个对象到另一个对象所经过的折线距离,有时也可以进一步的描述为多维空间中对象在各维的平均差,取平均差之后的计算公式为,需要注意的是,曼哈顿距离取消了欧式距离的平方,因此使得离群点的影响减弱。

            (3)切比雪夫距离:切比雪夫距离主要表现为在多维空间中,对象从某个位置转移到另外一个对象所消耗的最少距离(这种距离更加形象的体现了第一节中提到的编辑距离概念),因此可以简单的描述为用一维属性决定某对象属于哪个簇,,这就好比我们去辨别一项罕见的现象一样,如果两个对象都存在这一罕见现象,那么这两个对象应该属于同一个簇。

            (4)幂距离:可以简单的描述为针对不同的属性给予不同的权重值,决定其属于那个簇,,r,p为自定义的参数,根据实际情况选择,其中,p是用来控制各维的渐进权重,r控制对象间较大差值的渐进权重。当r=p时,即为闵可夫斯基距离,当p=r=1时为曼哈顿距离,当p=r=2时为欧式距离,当p=r并趋于无穷时即为切比雪夫距离(可以用极限理论证明).因此,这几种距离统称为闵氏距离,闵氏距离的不足在于:从横向(各维)看,它等同的看待了不同不同的分量,这种缺陷从切比雪夫距离中可以明显看出,忽略了不同维的差异。从纵向(单维)看,它忽略了不同维的各对象的分布差异,这种差异在统计学中可以用期望,方差,标准差等度量。

            (5)余弦相似度:可以简单的描述为空间中两个对象的属性所构成的向量之间的夹角大小。,即当两个向量方向完全相同时,相似度为1,即完全相似,当两个向量方向相反时,则为-1,即完全不相似。

            (6)皮尔森相似度:可以描述为不同对象偏离拟合的中心线程度,可以进一步的理解为,许多对象的属性拟合成一条直线或者曲线,计算每个对象相对于这条线的各属性偏离程度,,其中c为共有属性

             (7)修正的余弦相似度:由(5)可以看出,如果对于不同维的计算尺度,则会有所偏差。

     

              (8)Jaccard相似度:Jaccard相似度常用于二值型数据的相似度计算。,在数据挖掘中,经常将属性值二值化,通过计算Jaccard相似度,可以简单快速的得到两个对象的相似程度。当然,对于不同的属性,这种二值型程度是不一样的,比如,在中国,熟悉汉语的两个人相似度与熟悉英语的两个人相似度是不同的,因为发生的概率不同。所以通常会对Jaccard计算变换,变换的目的主要是为了拉开或者聚合某些属性的距离

              (9)汉明距离:可以描述为将同等长度的字符串由其中一个变换到另一个的最小替换次数。如将a(11100)变换为b(00010),则其距离为4,汉明距离主要是为了解决在通信中数据传输时,改变的二进制位数,也称为信号距离。

              (10)加权的欧式距离:由上面的闵氏距离可知,其存在一定的缺陷,如何去减弱这种缺陷呢?一种简单的办法是对不同属性设置不同的权重,各权重之和为1,这样依然可以保证相似度的统一性,但是这种权重该如何选择呢?一种加权的欧式距离方法便可以将各维属性变换到标准化值。假设所有对象的X的均值为m,方差为s,则标准化后的值=(标准化前的值-各属性的均值)/各属性的标准差,所以加权的欧式距离为:

              (11)相关距离:相关距离是用来衡量随机变量X,Y之间的相关程度的一种方法,取值为[-1,1],且系数越大,相关度越高。当X,Y线性相关时,若为正线性相关时则为1,相关距离=1-相关系数,相关系数的计算为:         

                (12)马氏距离:即数据的协方差距离,与欧式距离不同的是它考虑到各属性之间的联系,如考虑性别信息时会带来一条关于身高的信息,因为二者有一定的关联度,而且独立于测量尺度。,其中,XY为样本中的对象,S为协方差矩阵。

                 通过以上方法的计算,便可以得到两个对象之间的相似度(距离),在实际的计算当中,应该根据不同的对象其属性特点进行有效选择,对象的距离计算对于聚类算法的过程十分重要,直接影响着算法的有效性,所以实际选择时应当仔细选择。

    展开全文
  • K-MEANS算法聚类问题,最简单,也是最实用的一个算法 基本概念 一个数据放进来,需要指定K值,来声明要得到簇的个数 质心:一个簇的数据均值,即向量各维取平均即可(迭代时使用) 距离度量:常用欧几里得距离...
  • 针对往复式压缩机故障数据空间分布复杂、常规算法不能有效聚类的问题,提出了一种改进的谱聚类算法.该算法使用新的相似度矩阵计算方式,根据故障数据流形分布的特点引入测地线距离取代欧氏距离作为数据间的关系度量;...
  • 基于量子计算的机理和特性,并结合进化计算,本文提出了一种新颖的量子进化聚类算法(QEAM),在该聚类算法中引入了一种新的距离测度函数——流形距离.新方法将聚类归属为优化问题,通过运用量子进化的机理更快...
  • K-means聚类距离度量方法小结

    万次阅读 2021-10-24 20:37:33
    kmeans算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。 其算法思想大致为:先从样本集中随机...
  • k-means聚类算法及matlab代码 数据挖掘实验 实验一:相似度、距离、最近邻分类器 1、实验目的 (1)理解相似度、距离度量方式。 (2)理解最近邻分类器的工作原理。 2、实验内容 (1)、实现任意给定两个相同维度...
  • 基于维度根距离相似度量方法对单值和区间中性的聚类算法进行聚类算法(英文).pdf
  • 基于融合欧氏距离与Kendall Tau距离度量的谱聚类算法(英文).pdf
  • 层次聚类算法-类间距离度量

    千次阅读 2019-12-03 20:47:26
    最短距离法 概述 关键词 层次聚类 两类 对象距离最短 类间距 流程 例题 最长距离法 概述 关键词 层次聚类 两类 对象距离最长 类间距 流程 与最短距离法一样 例题 ...
  • 聚类算法概述及相关距离度量公式

    千次阅读 2018-06-12 15:19:01
    一、概述首先:聚类算法是无监督学习算法;一般构建用户兴趣属性画像等可应用聚类算法;而一般的分类算法是有监督学习,基于有标注的历史数据进行算法模型构建定义:对大量未知标注的数据集,按照数据内部存在的数据...
  • 点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达 本文转自:磐创AI1. 典型聚类算法1.1 基于划分的方法代表:kmeans算法·指定k个聚类中心...
  • means聚类算法和模糊K-means聚类算法对中国A股市场约2 600支股票依据其财务指标进行聚类,以便进行股票板块的划分,并比较两种算法在不同距离度量方式下的迭代次数、执行时间、聚类间密度和聚类内密度。实验结果表明...
  • 为此,提出一种以轨迹子段为聚类目标的聚类算法CTIHD。给出一种新的轨迹子段距离度量方法,用以消除轨迹子段之间的公共偏差。利用特征点概念将轨迹划分成轨迹子段集,计算轨迹子段之间的相似度,由此实现聚类。实验...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,366
精华内容 7,346
热门标签
关键字:

聚类算法中的距离度量