Алгоритм строковой кластеризации - руководство

Question

Я пытаюсь сгруппировать группу строк, основываясь на их сходстве, заданном jaro-distance. Я вычисляю это с помощью JellyFish в python. Я изо всех сил пытаюсь понять, как сгруппировать данные. Я не эксперт в кластеризации, и это моя первая попытка выяснить, как это сделать.

В настоящее время я написал то, что я считаю, аппроксимирует метод Однопроходного метода разделения, который работает в мое понимание, как это:

1. Сделайте первую струну cnetroid для первого кластера
2. Для следующего строка вычисляет сходство с этим центроидом с использованием Jaro Distance.
3. Если они достаточно похожи, то добавьте строку в кластер в противном случае использовать строку, чтобы начать новый кластер с ним как центроида
4. Повторяйте, пока не строки не осталось оценить

Я хотел бы намеков о моем коде, но что более важно, если кто-нибудь знает о более эффективном методе для этого. Я читал о k-средствах, но я понятия не имею, как указать 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.