python - 字符串聚类算法 - 指导

Question

我正在尝试根据 jaro 距离给出的相似性对一组字符串进行聚类。我正在用 python 中的 JellyFish 计算它。我一直在努力弄清楚如何对数据进行聚类。我不是集群方面的专家，这是我第一次尝试弄清楚如何做到这一点。

目前，我已经写了一些我认为近似于单 channel 分区方法的东西，按照我的理解，它是这样工作的:

1. 将第一个字符串作为第一个集群的 cnetroid
2. 对于下一个字符串，使用 Jaro Distance 计算与该质心的相似度。
3. 如果它们足够相似，则将字符串添加到集群中，否则使用该字符串以它作为质心开始一个新集群
4. 重复直到没有字符串可以评估

我想要有关我的代码的任何提示，但更重要的是，如果有人知道执行此操作的更好方法。我阅读了有关 k-means 的信息，但我不知道如何指定 k(更不用说如何实际实现了)。如果您确实决定提供建议，那么以通俗易懂的方式表达建议，并提供一些关于在哪里寻找指导的想法将非常受欢迎。谢谢。

关于代码的一些注释。1. 我随机播放列表，因为起点是任意的2. 如果一个匹配分数高于前一个匹配项，我会更新质心 - 这对于集群的第一个字符串是任意的，但它是试图获得“最真实”的字符串作为集群质心。

提前感谢任何指导

def SLINK(SList):
    shuffle(SList)
    Clusters = []
    Centroid = []
    Scores = []
    for string in SList:
    Matched = 0

    if len(Clusters) == 0:
        Clusters.append([string])
        Centroid.append([string])
        Scores.append([])
        continue

    for ClustNum in xrange(len(Clusters)):
        Dist = jf.jaro_distance(string, Centroid[ClustNum][0])

        if Dist > 0.8:
            Clusters[ClustNum].append(string)

            if len(Scores[ClustNum]) == 0:
                Scores[ClustNum].append(Dist)
            else:
                if Dist > Scores[ClustNum]:
                    Scores[ClustNum][0] = Dist
                    Centroid[ClustNum][0] = string

            Matched = 1
            break

    if Matched ==0:       
        Clusters.append([string])
        Centroid.append([string])
        Scores.append([])

return Clusters

Answer 1

如果您的问题只是关于集群的一般性问题，我建议您寻找比现有版本更直观、更容易实现的版本。具体来说，FLAME 聚类算法对如何在 wikipedia 上实现该算法有很好的解释。 .