使用Python实现基于余弦相似度的K-means算法

Question

我正在尝试在Python中实现Kmeans算法，该算法将使用余弦距离作为距离度量，而不是欧几里德距离。 我知道使用不同的距离函数可能会导致灾难性后果，因此应该小心处理。使用余弦距离作为度量强制我更改平均函数（根据余弦距离的平均值必须是规范化向量的逐元素平均值）。

我看到了这个手动覆盖sklearn距离函数的优雅解决方案，并且我想使用相同的技术来覆盖代码的平均部分，但是我找不到它。

有人知道如何做吗？ 距离度量不满足三角不等式有多重要？ 如果有人知道使用余弦度量或满足距离和平均函数的不同有效实现，则也会非常有帮助。

非常感谢！ 编辑： 在使用角距离而不是余弦距离之后，代码看起来像这样：

def KMeans_cosine_fit(sparse_data, nclust = 10, njobs=-1, randomstate=None):
    # Manually override euclidean
    def euc_dist(X, Y = None, Y_norm_squared = None, squared = False):
        #return pairwise_distances(X, Y, metric = 'cosine', n_jobs = 10)
        return np.arccos(cosine_similarity(X, Y))/np.pi
    k_means_.euclidean_distances = euc_dist
    kmeans = k_means_.KMeans(n_clusters = nclust, n_jobs = njobs, random_state = randomstate)
    _ = kmeans.fit(sparse_data)
    return kmeans

我注意到（通过数学计算）如果向量被标准化，标准平均值对于角度度量表现良好。据我所知，我需要在k_means_.py中更改_mini_batch_step()。但是这个函数相当复杂，我不知道该如何做。
有人知道替代方案吗？ 或者，有人知道如何使用一种总是强制质心标准化的函数来编辑此函数吗？

- ise372

---

请查看scikit-learn源代码中的k_means_.py。你提供的余弦距离示例只是用自定义函数替换了k_means_模块中的一个名为euclidean_distance的函数变量。如果您发布您的k-means代码以及要覆盖的函数，我可以给您更具体的答案。但是，如果您想自己完成，请在k_means_源代码中查找平均函数的名称并进行替换。 - charlesreid1

另外，一般来说，SO的问题应该包括一个最小、完整、可行的示例——如果您包含要修改的代码或出现问题的内容，您可以期望获得更多的帮助。 - charlesreid1

@charlesreid1 谢谢，我已经添加了代码。我的问题是我还没有完全理解k_means_.py中的平均函数是如何工作的，因此我无法理解如何更改它。 - ise372

有一个名为spherecluster的Python包，它在球面上实现了K-means算法（因此它基本上做的是您尝试做的相同的事情）。 - σηγ

尝试使用此链接 https://gist.github.com/mblondel/6230787 - Cătălin George Feștilă

你可以尝试使用k-medoids算法，它支持任何距离度量。它不使用“均值”作为中心点，而是使用现有数据点。https://scikit-learn-extra.readthedocs.io/en/latest/generated/sklearn_extra.cluster.KMedoids.html - Bert Kellerman

Answer 1

原来的 X 可以被标准化为单位长度，然后和正常一样使用 K-means。原因是如果 X1 和 X2 是单位向量，观察下面的等式，最后一行括号里的项就是余弦距离。

所以在使用 K-means 时，只需要执行以下步骤：

length = np.sqrt((X**2).sum(axis=1))[:,None]
X = X / length

kmeans = KMeans(n_clusters=10, random_state=0).fit(X)

如果您需要质心和距离矩阵，请执行以下操作：

len_ = np.sqrt(np.square(kmeans.cluster_centers_).sum(axis=1)[:,None])
centers = kmeans.cluster_centers_ / len_
dist = 1 - np.dot(centers, X.T) # K x N matrix of cosine distances

注意事项:

• 刚刚意识到您正在尝试将簇的平均向量与其成分之间的距离最小化。当您简单地对向量求平均值时，平均向量的长度小于1。但实际上，仍然值得运行常规的sklearn算法并检查平均向量的长度。在我的情况下，平均向量接近单位长度（大约平均为0.9，但这取决于您的数据有多密集）。 TLDR：如@σηγ所指出的那样，请使用spherecluster包。

- sachinruk

---

来自我们在Cross Validated上的朋友们的相关讨论--> https://stats.stackexchange.com/a/146279/243511 - timhealz

如果您使用sklearn.feature_extraction.text.TfidfVectorizer，似乎默认应用L2归一化，即向量化器的输出已经被归一化。 - tomas

Answer 2

您可以对数据进行归一化，然后使用KMeans。

from sklearn import preprocessing
from sklearn.cluster import KMeans

kmeans = KMeans().fit(preprocessing.normalize(X))

- ricecooker

Answer 3

很遗憾，目前Sklearn的K-means实现只使用欧几里得距离。原因是K-means包括计算聚类中心和将样本分配给最近中心的计算，而欧几里得距离仅在样本之间的中心具有意义。如果您想使用余弦距离的K-means，则需要编写自己的函数或类，或尝试使用其他聚类算法，如DBSCAN。

- Gilseung Ahn