串聚类算法

Question

我试图根据jaro距离给出的相似性来聚类一组字符串。我用Python中的水母来计算。我一直在努力想办法把数据聚集起来。我不是集群方面的专家，这是我第一次尝试找出如何做到这一点。在

目前，我已经写了一些东西，我相信这是一种近似于单遍方法的分区方法，我的理解是这样的：

1. 使第一个字符串成为第一个集群的cnetroid
2. 对于下一个字符串，使用Jaro距离计算与该质心的相似性。在
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上实现该算法有着奇妙的解释。在