相似性传播首选项初始化 [英] Affinity Propagation preferences initialization

问题描述

我需要在不预先知道群集数量的情况下执行群集.群集的数量可能是1到5，因为我可能会发现所有样本都属于同一实例或属于有限数量的组的情况. 我认为亲和力传播可能是我的选择，因为我可以通过设置首选项参数来控制群集的数量. 但是，如果我人工生成一个群集，并且将节点之间的最小欧几里德距离设置为优先级(以最小化群集数)，那么群集会变得很糟糕.

I need to perform clustering without knowing in advance the number of clusters. The number of cluster may be from 1 to 5, since I may find cases where all the samples belong to the same instance, or to a limited number of group. I thought affinity propagation could be my choice, since I could control the number of clusters by setting the preference parameter. However, if I have a single cluster artificially generated and I set preference to the minimal euclidean distance among nodes (to minimize number of clusters), I get terrible over clustering.

"""
=================================================
Demo of affinity propagation clustering algorithm
=================================================

Reference:
Brendan J. Frey and Delbert Dueck, "Clustering by Passing Messages
Between Data Points", Science Feb. 2007

"""
print(__doc__)
import numpy as np
from sklearn.cluster import AffinityPropagation
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from scipy.spatial.distance import pdist

##############################################################################
# Generate sample data
centers = [[0,0],[1,1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5,
                            random_state=0)
init = np.min(pdist(X))

##############################################################################
# Compute Affinity Propagation
af = AffinityPropagation(preference=init).fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_

n_clusters_ = len(cluster_centers_indices)

print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
      % metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
      % metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
      % metrics.silhouette_score(X, labels, metric='sqeuclidean'))

##############################################################################
# Plot result
import matplotlib.pyplot as plt
from itertools import cycle

plt.close('all')
plt.figure(1)
plt.clf()

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()

我使用亲和力传播的方法是否存在任何缺陷?相反，亲和力传播"是否不适合此任务，所以我应该使用其他东西吗?

Is there any flaw in my approach of using Affinity Propagation? Conversely, is Affinity Propagation unsuited for this task, so should I use something else?

推荐答案

不，没有缺陷. AP不使用距离，但要求您指定相似性.我不太了解scikit的实现，但是根据我的阅读，默认情况下，它使用 负平方欧几里德距离来计算相似度矩阵.如果将输入首选项设置为最小欧几里得距离，则将获得正值，而所有相似度均为负.因此，这通常会导致产生与样本数量一样多的聚类(请注意:输入首选项越高，聚类越多).我宁愿建议将输入偏好设置为最小的负平方距离，即数据集中最大距离的平方的-1倍.这将为您提供更少数量的群集，但不一定是一个群集.我不知道scikit实现中是否还存在preferenceRange()函数. AP主页上有Matlab代码，我正在维护的R包"apcluster"中也实现了该代码.此功能允许确定输入首选项参数的有意义的范围.希望对您有所帮助.

No, there is no flaw. AP does not use distances, but requires you to specify a similarity. I don't know the scikit implementation so well, but according to what I read, it uses negative squared Euclidean distances by default to compute the similarity matrix. If you set the input preference to the minimal Euclidean distance, you get a positive value, while all similarities are negative. So this will typically result in as many clusters as you have samples (note: the higher the input preference, the more clusters). I'd rather suggest to set the input preference to the minimal negative squared distance, i.e. -1 times the square of the largest distance in the data set. This will give you a much smaller number of clusters, but not necessarily one single cluster. I don't know whether the preferenceRange() function exists also in the scikit implementation. There is Matlab code on the AP homepage and it is also implemented in the R package 'apcluster' that I am maintaining. This function allows for determining meaningful bounds for the input preference parameter. I hope that helps.

这篇关于相似性传播首选项初始化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！