16

我正在研究一个 python 项目，我在其中研究 RNA 结构进化（表示为字符串，例如：“（（（...））”，其中括号表示碱基对）。关键是我有一个理想的结构和一个朝着理想结构发展的人口。我已经实现了一切，但是我想添加一个功能，我可以在其中获得“桶数”，即每一代人口中最具代表性的 k 个结构。

我正在考虑使用 k-means 算法，但我不确定如何将它与字符串一起使用。我找到了 scipy.cluster.vq但我不知道如何在我的情况下使用它。

谢谢！

4

4 回答 4

12

如果使用，您将面临的一个问题scipy.cluster.vq.kmeans是该函数使用欧几里得距离来测量接近度。要将您的问题固定为可通过k-means聚类解决的问题，您必须找到一种方法将您的字符串转换为数值向量，并能够证明使用欧几里德距离作为接近度的合理衡量标准。

这似乎……很难。也许您正在寻找Levenshtein 距离？

请注意，K-means 算法的一些变体可以使用非欧几里德距离度量（例如 Levenshtein 距离）。K-medoids例如，（又名 PAM）可以应用于具有任意距离度量的数据。

例如，使用Pycluster的实现k-medoids，以及Levenshtein 距离nltk的实现，

import nltk.metrics.distance as distance
import Pycluster as PC

words = ['apple', 'Doppler', 'applaud', 'append', 'barker', 
         'baker', 'bismark', 'park', 'stake', 'steak', 'teak', 'sleek']

dist = [distance.edit_distance(words[i], words[j]) 
        for i in range(1, len(words))
        for j in range(0, i)]

labels, error, nfound = PC.kmedoids(dist, nclusters=3)
cluster = dict()
for word, label in zip(words, labels):
    cluster.setdefault(label, []).append(word)
for label, grp in cluster.items():
    print(grp)

产生类似的结果

['apple', 'Doppler', 'applaud', 'append']
['stake', 'steak', 'teak', 'sleek']
['barker', 'baker', 'bismark', 'park']
于 2011-06-09T13:47:46.207 回答
10

K-means 仅适用于欧式距离。编辑距离（例如 Levenshtein）甚至不服从三角不等式可能服从三角不等式，但不是欧几里得。对于您感兴趣的指标类型，您最好使用不同类型的算法，例如层次聚类：http ://en.wikipedia.org/wiki/Hierarchical_clustering

或者，只需将您的 RNA 列表转换为加权图，边缘带有 Levenshtein 权重，然后将其分解为最小生成树。从某种意义上说，该树中连接最多的节点将是“最具代表性的”。

于 2011-06-09T13:58:14.500 回答
2

K-means 并不真正关心所涉及的数据类型。做 K-means 所需要的只是某种方法来测量从一个项目到另一个项目的“距离”。它会根据距离来做它的事情，而不管它是如何从基础数据中计算出来的。

也就是说，我没有使用scipy.cluster.vq，所以我不确定你如何准确地告诉它项目之间的关系，或者如何计算从项目 A 到项目 B 的距离。

于 2011-06-09T13:40:15.757 回答
0

Kmeans 需要的是“距离”度量（代表向量的数字，因此它可以找到向量之间的距离并根据距离将它们聚集在质心周围）。以下是我为您编写的一些示例：

  • 假设您有代表日期的字符串，例如2019-06-27 15:52:41.623Z. 在这种情况下，您要做的是选择一个日期，比如 UTC 时间戳开始的时间。现在以开始日期和时间为参考，您可以计算到每个日期字符串的“距离”。

  • 相反，假设您有代码字符串，if(a == b)那么if(a == c) 您可能想要使用不同的“距离”，例如字符串之间不同的字符数。

  • 或者，如果您有 Html DOM 结构，而您可能不想计算字符，但有多少标签与您的“距离”不同<html></html>。 <html><head></head></html>

  • 或者对于数据库中的已知枚举，您可以根据自己对枚举之间“距离”的想法将每个键定义为不同的数字。例如，“男性”、“女性”、“中性”如果定义为向量 [0]、[1]、[2]，则意味着中性比男性更接近女性。所以你可能想做 [0],[2],[1] 或 [-1],[1],[0]。

  • 对于问题中提出的 RNA/DNA 结构，“距离”可能是链之间有多少碱基对不同。

我希望你能明白。因此，您需要考虑字符串的内容是什么，并考虑定义内容之间“距离”的最佳方式。简单的字符差异距离可以作为字符串之间的通用距离度量，但如果你有更好的距离想法，你的算法会更好。

于 2019-12-12T18:56:16.573 回答