Кластеризация одномерной строки с произвольным расстоянием - ruby

Question

У меня есть массив строк, которые являются названиями продуктов из нескольких магазинов. Теперь мне нужно кластеризовать этот массив, чтобы получить кластеры, содержащие один и тот же продукт, независимо от магазина, который указан в списке.

Как пример:

data = ["Laptop Asus xd45jkl", 
        "Laptop Acer d3000",
        "Notebooh Hp hxsss", 
        "Laptop Asus xd45jkl intel core i7", 
        "Laptop Acer d3000 intel core i5 4gb RAM"
]
desired_output = [["Laptop Asus xd45jkl", Laptop Asus xd45jkl intel core i7],
          ["Laptop Acer d3000", "Laptop Acer d3000 intel core i5 4gb RAM"]
          [""Notebooh Hp hxsss""]
         ]

В качестве расстояния между названиями продуктов я подумал о JaroWinkler от amatch gem. Есть алгоритм k-средних типа или что-то еще, что может произвести кластеризацию этого массива строк?

Answer 1

Я подумал что-то вроде этого:

data = ["Laptop Asus xd45jkl", "Laptop Acer d3000", "Notebooh Hp hxsss", "Laptop Asus xd45jkl intel core i7", "Laptop Acer d3000 intel core i5 4gb RAM" ]
clusters = Hash.new

data.each do |item|
    brand =  item.split[1]
    clusters[brand] = [] if clusters[brand].nil?
    clusters[brand] << item
end

clusters.map! { |k, v| v }

Я не уверен, что это соответствует k-means и относительно его производительности на больших наборах данных.

Изменить: это займет около 2 секунд на 50000 предметов.